C语言实现动态顺序表的示例代码

下面是关于C语言实现动态顺序表的示例代码的完整攻略。

什么是动态顺序表？

动态顺序表是一种可以动态扩容的线性表，它的底层实现采用数组实现。相对于静态顺序表而言，在使用过程中更加灵活，可以在容量不够时自动扩容，节省了空间，同时又可以随着数据的增加而自动增长容量，保证数据的完整性。

如何实现动态顺序表？

1. 动态顺序表实现的数据结构

动态顺序表的底层数据结构是数组，同时还需要维护当前表的长度Length和容量Capacity，数据结构如下：

typedef struct dynamic_array {
  int *data;
  int Length;
  int Capacity;
} DynamicArray;

其中，data为数组指针，Length为当前表中元素的数量，Capacity为当前表的容量。

2. 动态扩容

当动态顺序表需要扩容时，需要实现一个自动扩容的函数，这个函数首先需要判断当前表的长度和容量的关系，当表的长度超过容量时需要将表的容量进行扩增，并将原有数据复制到新的内存空间中，在扩容完成后，释放原有的内存空间。

扩容函数的实现如下：

void ExpandSpace(DynamicArray *pArray) {
  if (pArray == NULL) return;

  // 当前长度小于容量，不需要扩容
  if (pArray->Length < pArray->Capacity) return;

  // 扩容至原有容量的两倍
  int newCapacity = pArray->Capacity << 1;
  int *newData = (int *)malloc(newCapacity * sizeof(int));

  // 将原有数据复制到新的内存空间中
  if (pArray->data) {
    memcpy(newData, pArray->data, pArray->Length * sizeof(int));
    free(pArray->data);
  }

  // 更新数据结构
  pArray->data = newData;
  pArray->Capacity = newCapacity;
}

3. 插入操作

当动态顺序表需要插入数据时，需要保证当前数组的容量足够，如果容量不够需要进行扩容。插入操作可以实现在指定位置i插入元素，同时也可以实现在表的末尾插入数据。

插入操作的实现如下：

void Insert(DynamicArray *pArray, int index, int value) {
  if (pArray == NULL) return;

  // 当前数组已满，需要扩容
  ExpandSpace(pArray);

  // 插入位置大于表的长度，插入到表的末尾
  if (index > pArray->Length) {
    pArray->data[pArray->Length++] = value;
  } else if (index >= 0) {
    // 在指定位置插入元素

    // 将index之后的所有元素向后移动一位
    for (int i = pArray->Length; i > index; i--) {
      pArray->data[i] = pArray->data[i - 1];
    }

    // 插入元素到指定位置
    pArray->data[index] = value;
    pArray->Length++;
  }
}

示例说明

示例1：在表末插入元素

对于下面的动态顺序表：

DynamicArray arr = {NULL, 0, 0};

我们可以通过以下代码在顺序表的末尾插入元素：

Insert(&arr, 0, 1);
Insert(&arr, 1, 2);

接下来，我们可以遍历数组进行输出：

for (int i = 0; i < arr.Length; i++) {
  printf("%d ", arr.data[i]);
}

输出结果为：

1 2

示例2：在指定位置插入元素