【数据结构与算法】第5篇：线性表（一）：顺序表（ArrayList）的实现与应用

一、什么是顺序表

顺序表是最简单的一种线性结构。用一段地址连续的存储单元依次存储数据元素。

你可以把它理解为一个可以自动扩容的数组。C语言的原生数组长度是固定的，不够用的时候只能重新申请更大的数组，把数据搬过去。顺序表封装了这个过程，让使用者不用操心容量问题。

顺序表的特点：

• 逻辑上相邻的元素，物理位置上也相邻

• 可以通过下标直接访问，时间复杂度O(1)

• 插入和删除操作需要移动元素，时间复杂度O(n)

二、顺序表的结构定义

我们需要用一个结构体来管理顺序表：

c

typedef struct { int *data; // 指向动态数组的指针 int size; // 当前元素个数 int capacity; // 总容量 } SeqList;

• data：指向一块连续内存的指针，真正存数据的地方

• size：当前有多少个元素

• capacity：当前最多能存多少个元素（不一定是内存的实际字节数）

三、基本操作实现

3.1 初始化

c

void initSeqList(SeqList *list, int initCapacity) { list->data = (int*)malloc(initCapacity * sizeof(int)); if (list->data == NULL) { printf("初始化失败\n"); exit(1); } list->size = 0; list->capacity = initCapacity; }

初始化时先申请一块内存，size设为0，capacity就是申请的大小。

3.2 销毁

c

void destroySeqList(SeqList *list) { if (list->data != NULL) { free(list->data); list->data = NULL; } list->size = 0; list->capacity = 0; }

用完一定要释放内存，避免泄漏。

3.3 扩容

扩容是顺序表的核心。当size等于capacity时，再插入新元素就需要扩容。

c

void expand(SeqList *list) { int newCapacity = list->capacity * 2; // 翻倍扩容 int *newData = (int*)realloc(list->data, newCapacity * sizeof(int)); if (newData == NULL) { printf("扩容失败\n"); return; } list->data = newData; list->capacity = newCapacity; printf("扩容到 %d\n", newCapacity); }

扩容策略：这里用的是翻倍扩容。也可以每次增加固定大小（比如+10）。翻倍扩容的优点是，随着容量变大，扩容次数越来越少，平均时间复杂度更低。

3.4 插入

在指定位置插入元素，这是顺序表最复杂的操作。

c

int insert(SeqList *list, int pos, int value) { // 检查位置是否合法（可以插在末尾，所以pos可以从0到size） if (pos < 0 || pos > list->size) { printf("插入位置不合法\n"); return -1; } // 满了就扩容 if (list->size == list->capacity) { expand(list); } // 移动元素：从最后一个开始往后移，给新元素腾位置 for (int i = list->size; i > pos; i--) { list->data[i] = list->data[i - 1]; } // 插入新元素 list->data[pos] = value; list->size++; return 0; }

关键点：移动元素必须从后往前移。如果从前往后移，前面的元素会把后面的覆盖掉。

画个图理解一下，在位置2插入一个元素：

text

插入前：[10, 20, 30, 40] size=4 插入位置2，值25 第一步：从最后一个开始往后移 [10, 20, 30, 40, 40] i从4移到3 [10, 20, 30, 30, 40] i移到2时停止 第二步：插入 [10, 20, 25, 30, 40] size变成5

3.5 删除

删除指定位置的元素，同样需要移动数据。

c

int delete(SeqList *list, int pos) { // 检查位置是否合法 if (pos < 0 || pos >= list->size) { printf("删除位置不合法\n"); return -1; } // 保存被删除的值（如果需要的话） int value = list->data[pos]; // 移动元素：从pos+1开始往前移 for (int i = pos; i < list->size - 1; i++) { list->data[i] = list->data[i + 1]; } list->size--; return value; }

删除比插入简单，移动方向是从前往后。

3.6 查找

按值查找，返回第一个匹配的位置。

c

int find(SeqList *list, int value) { for (int i = 0; i < list->size; i++) { if (list->data[i] == value) { return i; } } return -1; }

3.7 打印

c

void print(SeqList *list) { printf("size=%d, capacity=%d, [", list->size, list->capacity); for (int i = 0; i < list->size; i++) { printf("%d", list->data[i]); if (i < list->size - 1) printf(", "); } printf("]\n"); }

四、完整代码演示

c

#include <stdio.h> #include <stdlib.h> typedef struct { int *data; int size; int capacity; } SeqList; void initSeqList(SeqList *list, int initCapacity) { list->data = (int*)malloc(initCapacity * sizeof(int)); if (list->data == NULL) { printf("初始化失败\n"); exit(1); } list->size = 0; list->capacity = initCapacity; } void destroySeqList(SeqList *list) { if (list->data != NULL) { free(list->data); list->data = NULL; } list->size = 0; list->capacity = 0; } void expand(SeqList *list) { int newCapacity = list->capacity * 2; int *newData = (int*)realloc(list->data, newCapacity * sizeof(int)); if (newData == NULL) { printf("扩容失败\n"); return; } list->data = newData; list->capacity = newCapacity; printf("扩容到 %d\n", newCapacity); } int insert(SeqList *list, int pos, int value) { if (pos < 0 || pos > list->size) { printf("插入位置不合法\n"); return -1; } if (list->size == list->capacity) { expand(list); } for (int i = list->size; i > pos; i--) { list->data[i] = list->data[i - 1]; } list->data[pos] = value; list->size++; return 0; } int delete(SeqList *list, int pos) { if (pos < 0 || pos >= list->size) { printf("删除位置不合法\n"); return -1; } int value = list->data[pos]; for (int i = pos; i < list->size - 1; i++) { list->data[i] = list->data[i + 1]; } list->size--; return value; } int find(SeqList *list, int value) { for (int i = 0; i < list->size; i++) { if (list->data[i] == value) { return i; } } return -1; } void print(SeqList *list) { printf("size=%d, capacity=%d, [", list->size, list->capacity); for (int i = 0; i < list->size; i++) { printf("%d", list->data[i]); if (i < list->size - 1) printf(", "); } printf("]\n"); } int main() { SeqList list; initSeqList(&list, 3); // 插入几个元素，观察扩容 insert(&list, 0, 10); insert(&list, 1, 20); insert(&list, 2, 30); print(&list); // 再插一个，触发扩容 insert(&list, 3, 40); print(&list); // 中间插入 insert(&list, 2, 25); print(&list); // 删除 int val = delete(&list, 2); printf("删除的值: %d\n", val); print(&list); // 查找 int pos = find(&list, 30); printf("30的位置: %d\n", pos); destroySeqList(&list); return 0; }

运行结果：

text

扩容到 6 size=3, capacity=3, [10, 20, 30] size=4, capacity=6, [10, 20, 30, 40] size=5, capacity=6, [10, 20, 25, 30, 40] 删除的值: 25 size=4, capacity=6, [10, 20, 30, 40] 30的位置: 2

五、复杂度分析

关于扩容的均摊分析：假设初始容量为1，翻倍扩容到n的过程中，总共移动的次数约为2n，平均到n次插入，每次插入的扩容成本是O(1)。

六、顺序表的优缺点

优点：

1. 支持随机访问，按下标取元素是O(1)

2. 空间连续，CPU缓存友好

3. 尾插尾删效率高（不需要移动元素）

缺点：

1. 中间插入和删除需要移动大量元素，效率低

2. 扩容时需要重新申请内存并拷贝数据，有开销

3. 可能浪费空间（capacity > size的部分）

适用场景：

• 需要频繁随机访问

• 主要在尾部操作

• 元素个数大致可预估

七、小结

这一篇我们实现了顺序表，要点总结：

下一篇我们会讲单链表，它解决了顺序表插入删除慢的问题，但失去了随机访问的能力。没有完美的数据结构，只有合适的选择。

八、思考题

1. 如果每次扩容只增加10个位置，而不是翻倍，会有什么问题？

2. 插入操作中，如果插入位置是末尾，还需要移动元素吗？

3. 写一个函数，删除顺序表中所有等于某个值的元素（要求时间复杂度O(n)）。

4. 为什么顺序表不适合在头部频繁插入？

欢迎在评论区讨论你的答案。