首页 > 编程笔记

C语言动态数组

在 C语言中，数组是一种非常常用的数据结构，可以用来存储一组相同类型的数据。但是，数组的长度是固定的，一旦定义了长度就不能改变。为了解决这个问题，C语言提供了动态数组的概念，它可以在程序运行时动态地分配和释放内存空间，使得数组长度可以动态改变。

动态数组的定义和初始化

动态数组的定义和初始化通常使用 malloc 函数实现。malloc 函数用于动态分配内存空间，它的原型如下：
void *malloc(size_t size);
其中，size_t 是一个无符号整型，表示需要分配的内存空间大小，malloc 函数返回一个 void 类型的指针，指向分配的内存空间的首地址。

例如，以下是一个动态数组的定义和初始化示例：
int n = 10; // 数组长度
int *arr = (int *)malloc(n * sizeof(int)); // 动态分配内存空间

for (int i = 0; i < n; i++) {
  arr[i] = i + 1; // 初始化数组元素
}
在这个例子中，我们首先定义了一个整型变量 n，表示数组的长度。然后，使用 malloc 函数动态分配了 n 个 int 类型的内存空间，并将返回的指针类型强制转换成 int 类型的指针。接着，使用 for 循环初始化数组的每个元素。

动态数组的使用和释放

使用动态数组和普通数组的使用方式相同，可以使用下标访问数组元素。例如：
for (int i = 0; i < n; i++) {
  printf("%d ", arr[i]); // 输出数组元素
}
需要注意的是，动态数组的内存空间是在程序运行时动态分配的，所以在使用完后需要手动释放内存空间，避免造成内存泄漏。

动态数组的内存释放使用 free 函数实现，它的原型如下：
void free(void *ptr);
其中，ptr 是需要释放的内存空间的指针。例如：
	free(arr); // 释放动态数组的内存空间
需要注意的是，动态数组的内存空间只能使用一次 free 函数释放，多次释放会导致程序出错。另外，释放动态数组的内存空间后，指向数组的指针将成为“野指针”，不应再使用。

动态数组的扩容和缩容

动态数组的一个重要优点就是它的长度可以动态改变，我们可以通过扩容和缩容来实现。

动态数组的扩容可以通过 realloc 函数实现，它的原型如下：
void *realloc(void *ptr, size_t size);
其中，ptr 是需要重新分配内存空间的指针，size 表示需要重新分配的内存空间大小。如果重新分配成功，返回一个指向重新分配内存空间的指针；否则返回 NULL。

例如，我们可以通过以下方式将动态数组的长度扩大至原来的两倍：
arr = (int *)realloc(arr, 2 * n * sizeof(int)); // 扩容为原来的两倍

for (int i = n; i < 2 * n; i++) {
  arr[i] = i + 1; // 初始化新增的数组元素
}

n *= 2; // 更新数组长度
在这个例子中，我们首先使用 realloc 函数将动态数组的长度扩大至原来的两倍，并重新分配内存空间。接着，使用 for 循环初始化新增的数组元素，然后更新数组长度。

动态数组的缩容也可以通过 realloc 函数实现。例如，以下代码将动态数组的长度缩小至原来的一半：
arr = (int *)realloc(arr, n / 2 * sizeof(int)); // 缩容为原来的一半

n /= 2; // 更新数组长度
在这个例子中，我们使用 realloc 函数将动态数组的长度缩小至原来的一半，并重新分配内存空间。接着，更新数组长度。

需要注意的是，动态数组的扩容和缩容可能会导致内存空间重新分配，所以需要注意对数组元素的访问和修改。

动态数组的插入和删除

动态数组的一个常见操作就是在指定位置插入一个元素或者删除一个元素。假设我们有一个动态数组 arr，长度为 n，要在第 k 个位置插入一个元素 x，我们可以按照以下步骤操作：
  1. 如果当前数组长度不足以容纳新元素，我们需要先对数组进行扩容；
  2. 从第 n-1 个元素开始，往后逐个将元素后移一位，直到第 k 个位置；
  3. 在第 k 个位置插入元素 x；
  4. 更新数组长度。

例如，以下代码在动态数组 arr 的第 k 个位置插入元素 x：
if (n >= capacity) {
  arr = (int *)realloc(arr, 2 * capacity * sizeof(int)); // 扩容为原来的两倍
  capacity *= 2; // 更新数组容量
}

for (int i = n - 1; i >= k; i--) {
  arr[i+1] = arr[i]; // 将元素后移一位
}

arr[k] = x; // 插入新元素

n++; // 更新数组长度
动态数组的删除操作类似，例如以下代码删除动态数组 arr 的第 k 个元素：
for (int i = k; i < n-1; i++) {
  arr[i] = arr[i+1]; // 将元素前移一位
}

n--; // 更新数组长度

if (n < capacity / 2) {
  arr = (int *)realloc(arr, capacity / 2 * sizeof(int)); // 缩容为原来的一半
  capacity /= 2; // 更新数组容量
}
在这个例子中，我们从第 k 个元素开始，将后面的元素依次前移一位，然后更新数组长度。如果当前数组长度小于容量的一半，我们需要对数组进行缩容。

需要注意的是，动态数组的插入和删除操作可能会导致内存空间重新分配，所以需要注意对数组元素的访问和修改。

动态数组的遍历

动态数组的遍历是对数组元素进行逐个访问的操作。我们可以使用 for 循环遍历动态数组的所有元素。例如：
for (int i = 0; i < n; i++) {
  printf("%d ", arr[i]);
}
这段代码使用 for 循环遍历动态数组 arr 的所有元素，并将它们依次打印出来。

动态数组的排序

动态数组的排序是将数组元素按照一定规则重新排列的操作。C语言中有许多常见的排序算法，例如冒泡排序、快速排序、插入排序等。我们可以使用这些排序算法对动态数组进行排序。

例如，以下代码使用冒泡排序对动态数组 arr 进行排序：
for (int i = 0; i < n - 1; i++) {
  for (int j = 0; j < n - i - 1; j++) {
    if (arr[j] > arr[j+1]) {
      int temp = arr[j];
      arr[j] = arr[j+1];
      arr[j+1] = temp;
    }
  }
}
这段代码使用了冒泡排序算法，将动态数组 arr 中的元素按照从小到大的顺序重新排列。我们可以看到，冒泡排序的时间复杂度为 O(n^2)，并不适合对大规模数据进行排序。

当然，C语言还提供了许多其他的排序算法，例如快速排序、插入排序、选择排序等。选择适合自己需求的排序算法是很重要的。

动态数组的优缺点

动态数组的优点是长度可以动态改变，比静态数组更加灵活。它可以在程序运行时动态地分配和释放内存空间，避免了在程序设计时预先分配内存空间的困扰。

动态数组的缺点是使用不当可能会导致内存泄漏和程序崩溃。动态数组的分配和释放需要程序员手动管理，如果程序员不小心造成内存泄漏，可能会导致程序占用过多的内存，甚至崩溃。因此，使用动态数组时需要特别注意内存管理。

另外，动态数组的性能可能会受到内存分配和释放的影响。每次动态分配和释放内存空间都需要耗费一定的时间，如果频繁操作可能会影响程序的性能。

总结

动态数组是 C语言中常见的数据结构之一，它可以在程序运行时动态地分配内存空间，可以根据需要动态地扩容或者缩容。动态数组的常见操作包括初始化、插入、删除、遍历和排序等。

当我们需要处理不确定数量的数据时，动态数组是一个非常方便的数据结构。不过，动态数组的使用也需要注意内存分配和释放的问题，避免出现内存泄漏或者越界等问题。

推荐阅读