新手向超详细的C语言实现动态顺序表

当初步学习C语言之后，常常将动态内存管理作为初学者的第一个难点。本文将向新手讲解实现动态顺序表的过程，以及如何使用动态内存管理API来解决动态分配和释放内存的问题。本攻略使用C语言编写，通过动态分配内存的方式来模拟实现动态顺序表。

实现步骤

1. 定义数据结构

首先，需要定义一个结构体，来表示这个动态顺序表的数据结构。结构体中至少需要包含如下信息：
- 存储元素的数组（使用指针）
- 表的元素总数
- 表的容量
- 每个元素的大小（字节数）

如下是动态顺序表结构体的定义方式：

struct DynamicArray {
  void *elements;
  int size;
  int capacity;
  size_t element_size;
};

2. 初始化动态顺序表

对于任何动态数据结构来说，初始化操作都是必不可少的。初始化动态顺序表主要是为了给结构体中的指针分配一块空间，并且给定容量和元素大小。初始化的代码如下：

struct DynamicArray *create_dynamic_array(int capacity, size_t element_size) {
  struct DynamicArray *array = malloc(sizeof(struct DynamicArray));
  if (array == NULL) {
    fprintf(stderr, "Memory allocation failed.\n");
    exit(1);
  }

  array->elements = malloc(capacity * element_size);
  if (array->elements == NULL) {
    fprintf(stderr, "Memory allocation failed.\n");
    free_array(array);
    exit(1);
  }

  array->size = 0;
  array->capacity = capacity;
  array->element_size = element_size;

  return array;
}

3. 插入元素

动态顺序表最重要的功能之一是插入元素。这就需要使用指针来插入一个元素，并且需要考虑到扩容的问题。在这个代码里，如果当前元素数量已经达到了容量的上限，就需要对表进行扩容的操作。

void push_back(struct DynamicArray *array, void *element) {
  if (array->size == array->capacity) {
    int new_capacity = array->capacity * 2;
    void *new_elements = realloc(array->elements, new_capacity * array->element_size);
    if (new_elements == NULL) {
      fprintf(stderr, "Memory allocation failed.\n");
      exit(1);
    }

    array->elements = new_elements;
    array->capacity = new_capacity;
  }

  memcpy(array->elements + array->size * array->element_size, element, array->element_size);
  array->size++;
}

4. 释放内存

动态顺序表在使用完毕后，还需要释放内存。释放内存是为了避免内存泄漏，它需要释放元素指向一片内存的指针，以及结构体的指针。

void free_array(struct DynamicArray *array) {
  free(array->elements);
  free(array);
}

示例

下面通过两个示例来说明如何使用动态顺序表。

示例1：向动态顺序表中插入三个整数

#include <stdio.h>
#include "dynamic_array.h"

int main() {
  struct DynamicArray *array = create_dynamic_array(10, sizeof(int));

  int x = 1, y = 2, z = 3;
  push_back(array, &x);
  push_back(array, &y);
  push_back(array, &z);

  int *p = (int*)array->elements;
  for (int i = 0; i < array->size; i++) {
    printf("%d ", p[i]);
  }

  free_array(array);

  return 0;
}

输出结果：

1 2 3

示例2：向动态顺序表中插入三个字符串

#include <stdio.h>
#include <string.h>
#include "dynamic_array.h"

int main() {
  struct DynamicArray *array = create_dynamic_array(10, sizeof(char)*20);

  char s1[] = "hello", s2[] = "world", s3[] = "!";
  push_back(array, &s1);
  push_back(array, &s2);
  push_back(array, &s3);

  char *p = (char*)array->elements;
  for (int i = 0; i < array->size; i++) {
    printf("%s ", p+i*20);
  }

  free_array(array);

  return 0;
}