序
现代编程语言大都实现了动态数组，比如 python 的 list 和 C++ 的 vector。但是像 C 语言便没有这种好用的东西，都得自己实现，此文便是来介绍动态数组的实现，同时展开 C 语言内存管理中的 malloc() 和 realloc() 函数。
动态数组关键在于动态。相较于普通的静态数组而言，动态数组能够根据我们的需要扩展数组大小，灵活的添加元素。
定义动态数组结构体
对于一个动态数组，所需要包含的结构有堆数组本身、数组元素数量以及数组当前容量。使用 typedef 定义一个结构体数据结构:
1
2
3
4
5
6
|
typedef struct
{
int *array;
size_t size;
size_t capacity;
} dynamic_array;
|
array
array 是 int 类型的指针，指向动态分配的内存区域，这个区域存储了数组的元素。通过这个指针可以访问和直接地操作元素。
size
需要注意的是 size_t 实际是 unsigned long 的别名，使用这样的数据类型足以容纳各种数组类型大小的存放了。
size 用于存储动态数组当前容量，使得我们可以获取数组当前有多少元素，对于数组的操作非常重要。
capacity
capacity 存储数组当前容量，就是当前数组最大可容纳的元素数量。而当元素数量达到 capacity 时，如果还要添加新元素就要重新分配更大的内存空间，并更新 capacity。
创建动态数组
创建动态数组需要为结构体分配内存，而后还需要为其内部的数组分配内存并初始化结构体内容。这两者都存储在堆内存中。需要注意的是要检查是否分配成功，如果出现错误要及时打印出来方便排错。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
// 用于创建一个动态数组并进行初始化
dynamic_array *create_array(size_t initial_capatity)
{
// 为 dynamic_array 结构体分配内存，并将返回的指针赋给 arr
dynamic_array *arr = (dynamic_array *)malloc(sizeof(dynamic_array));
if (arr == NULL)
{
printf("Error: Failed to allocate memory for dynamic array structure.\n");
return NULL;
}
// 为内部整数数组分配内存
// 内存大小根据 initial_capatity * sizeof(int) 得出
arr->array = (int *)malloc(initial_capatity * sizeof(int));
if (arr->array == NULL)
{
printf("Error: Failed to allocate memory for the internal integer array.\n");
// 如果为 array 成员分配内存失败就会释放为 dynamic_array 结构体的内存防止内存泄漏
free(arr);
return NULL;
}
// 初始化 size 为 0，表示动态数组目前为空
arr->size = 0;
// 将 initial_capatity 赋给 capacity，记录数组的初始容量
arr->capacity = initial_capatity;
// 返回指向新创建的 dynamic_array 结构体指针 arr
return arr;
}
|
需要注意的是，因为其直接地操作内存，需要注意是否创建成功，如果 malloc() 返回了 NULL 就表面其没有创建成功。
malloc()
这里就要讲到 malloc() 函数。
1
|
void *malloc(unsigned long);
|
malloc() 用于分配新的内存空间。函数输入所需内存大小，返回指向新创建内存块的指针。如果创建失败就返回 NULL。在这里，使用 malloc 创建结构体时，输入的 sizeof(dynamic_array) ，一般来说，malloc 和 sizeof 组合使用,sizeof 输出数据的内存大小，比如输出了 dynamic_array 的内存大小。
对于 array 堆数组的创建，malloc 的参数为 (initial_capatity * sizeof(int)) 这里将 int 的内存大小乘以所需数组大小就很方便的创建了堆变量。
因为 malloc() 返回的是 void* 类型的指针，因而我们还需要对指针类型进行转换，也就是 malloc 前面用括号的类型: (dynamic_array*) 和 (int*)。
读取指定元素
数组比较快速的地方就在于随机读取。其复杂度为 $O(1)$。
1
2
3
4
5
6
7
8
9
10
11
12
|
// 用于从动态数组中读取指定索引处的元素
// 如果索引超出数组范围,就会打印错误信息并返回 -1
int read_array(dynamic_array *arr, size_t index)
{
if (index < arr->size)
return arr->array[index];
else
{
printf("Error: index out of bound: %ld.\n", index);
return -1;
}
}
|
没什么难理解的，index 为索引号。
更新动态数组内容
对于其内容的更新，复杂度和读取一样为 $O(1)$。
1
2
3
4
5
6
7
8
9
|
// 用于更新动态数组中指定索引处的元素。
// 如果索引超出数组范围，就会打印错误信息并返回
void update_array(dynamic_array *arr, size_t index, int value)
{
if (index < arr->size) // 检查索引的有效性
arr->array[index] = value; // 更新索引处的元素
else // 如果索引超出数组边界
printf("Error: index out of bounds>: %ld.\n", index);
}
|
追加内容
在这里就涉及到了数组的扩容，我们先处理扩容的相关代码。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
// 检查容量
if (arr->size >= arr->capacity) // 如果数组已满
{
// 计算新容量：通常新的容量是原容量的两倍。
// 以减少因重新分配内存而导致的性能开销
size_t new_capatity = arr->capacity * 2;
// 调用 realloc ，尝试将 arr->array 指向的内存扩展到 new_capatity * sizeof(int) 大小
int *new_array = (int *)realloc(arr->array, new_capatity * sizeof(int));
if (new_array == NULL)
{
printf("Error: Failsed to reallocate memory for the internal integer array.\n");
return -1;
}
// 如果内存重新分配成功，将 arr->array 更新为新内存块的指针,并更新 capacity
arr->array = new_array;
arr->capacity = new_capatity;
}
|
检查容量不必多说，当元素数量与数组容量相同时，再添入新的元素就需要扩容了。一般扩容是直接将容量翻倍，以减少因重新分配内存而导致的性能开销。
我们使用 realloc() 来进行扩容。。
realloc()
realloc() 用于重新分配内存块，调整已分配的内存大小。这在动态数组中极为重要。
1
|
void *realloc(void *, unsigned long);
|
有两个参数，第一个参数传递指向需要重新分配内存的指针，第二个参数为新内存块的大小。
需要注意错误检查，因为程序可能会因为没有足够大的空闲内存空间导致分配失败。
分配完成内存后，将 arr->array 指向的内存改为 new_array 并调整容量。
在处理完内存空间问题后，就可以开始进行追加了，只需要在索引为 size 的位置添加新的元素并增加 arr->size 的大小。
插入元素
动态数组的元素插入和静态数组是类似的，都需要进行元素右移操作。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
// 在动态数组的指定位置插入一个新的元素
int insert_array_element(dynamic_array *arr, size_t index, int value)
{
// 检查索引是否有效
if (index > arr->size)
{
printf("Error: index out of bound for insertion:%ld.\n", index);
return -1;
}
// 如果是末尾插入，直接调用上面写的追加函数
if (index == arr->size)
return append_array(arr, value);
// 检查容量
if (arr->size >= arr->capacity)
{
size_t new_capatity = arr->capacity * 2;
int *new_array = (int*)realloc(arr->array, new_capatity * sizeof(int));
if (new_array == NULL)
{
printf("Error: Failed to reallocate memory for the internal integer array.\n");
return -1;
}
arr->array = new_array;
arr->capacity = new_capatity;
}
// 元素右移腾出空间
for (size_t i = arr->size;i > index;i--)
arr->array[i] = arr->array[i-1];
//插入新的元素
arr->array[index] = value;
arr->size++;
return 0;
}
|
如果插入的位置恰好为末尾，可以使用追加函数进行优化。检查容量已经在上文解释清楚了。
我们需要对插入位置右侧的元素向右移动以空出一块地方插入新的元素。代码如下：
1
2
3
|
// 元素右移腾出空间
for (size_t i = arr->size;i > index;i--)
arr->array[i] = arr->array[i-1];
|
这里从数组末尾空闲的空间(arr->size) 开始，向左做自减直到到达要插入位置的后一个元素。在此过程中，不断将 i 赋值给前一个元素，这样就完成了右移，此时 index 的内容为空。
删除元素
删除元素比插入元素简单多了，不需要判断容量，只需要进行左移覆盖原来的元素即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
// 在动态数组移除元素
int remove_array_element(dynamic_array *arr, size_t index)
{
if (index > arr->size)
{
printf("Error: index out of bounds: %ld\n", index);
return -1;
}
// 元素左移
for (size_t i = index; i < arr->size;i++)
arr->array[i] = arr->array[i+1];
// 更新数组大小
arr->size--;
return 0;
}
|
左移与右移相反，从需要删除的位置开始自增到最后一个元素。将 i 处元素赋值给后一个元素，以此来覆盖需要删除的元素。最后别忘了更新数组大小。
打印动态数组
打印动态数组和普通数组一样，遍历数组即可：
1
2
3
4
5
6
|
// 打印动态数组中的所有元素
void print_array(dynamic_array* arr){
for (size_t i = 0;i < arr->size;i++)
printf("%d ", arr->array[i]);
printf("\n");
}
|
删除动态数组
动态数组不能像静态数组那样随意的防止，这样很容易造成内存泄漏。
在初始化的时候我们申请了两个内存空间分别是结构体和数组的，我们需要一一释放并将指针变量指向空指针。
1
2
3
4
5
6
7
|
// 删除动态数组
void delete_array(dynamic_array* arr){
free(arr->array);
arr->array = NULL;
free(arr);
arr = NULL;
}
|