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

一、什么是顺序表顺序表是最简单的一种线性结构。用一段地址连续的存储单元依次存储数据元素。你可以把它理解为一个可以自动扩容的数组。C语言的原生数组长度是固定的不够用的时候只能重新申请更大的数组把数据搬过去。顺序表封装了这个过程让使用者不用操心容量问题。顺序表的特点逻辑上相邻的元素物理位置上也相邻可以通过下标直接访问时间复杂度O(1)插入和删除操作需要移动元素时间复杂度O(n)二、顺序表的结构定义我们需要用一个结构体来管理顺序表ctypedef struct { int *data; // 指向动态数组的指针 int size; // 当前元素个数 int capacity; // 总容量 } SeqList;data指向一块连续内存的指针真正存数据的地方size当前有多少个元素capacity当前最多能存多少个元素不一定是内存的实际字节数三、基本操作实现3.1 初始化cvoid 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设为0capacity就是申请的大小。3.2 销毁cvoid destroySeqList(SeqList *list) { if (list-data ! NULL) { free(list-data); list-data NULL; } list-size 0; list-capacity 0; }用完一定要释放内存避免泄漏。3.3 扩容扩容是顺序表的核心。当size等于capacity时再插入新元素就需要扩容。cvoid 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 插入在指定位置插入元素这是顺序表最复杂的操作。cint 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] size4 插入位置2值25 第一步从最后一个开始往后移 [10, 20, 30, 40, 40] i从4移到3 [10, 20, 30, 30, 40] i移到2时停止 第二步插入 [10, 20, 25, 30, 40] size变成53.5 删除删除指定位置的元素同样需要移动数据。cint delete(SeqList *list, int pos) { // 检查位置是否合法 if (pos 0 || pos list-size) { printf(删除位置不合法\n); return -1; } // 保存被删除的值如果需要的话 int value list-data[pos]; // 移动元素从pos1开始往前移 for (int i pos; i list-size - 1; i) { list-data[i] list-data[i 1]; } list-size--; return value; }删除比插入简单移动方向是从前往后。3.6 查找按值查找返回第一个匹配的位置。cint find(SeqList *list, int value) { for (int i 0; i list-size; i) { if (list-data[i] value) { return i; } } return -1; }3.7 打印cvoid 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 size3, capacity3, [10, 20, 30] size4, capacity6, [10, 20, 30, 40] size5, capacity6, [10, 20, 25, 30, 40] 删除的值: 25 size4, capacity6, [10, 20, 30, 40] 30的位置: 2五、复杂度分析操作时间复杂度说明按索引访问O(1)直接通过下标计算地址插入O(n)平均移动n/2个元素删除O(n)平均移动n/2个元素查找按值O(n)最坏情况遍历全部扩容均摊O(1)翻倍扩容平均每次插入的扩容成本很低关于扩容的均摊分析假设初始容量为1翻倍扩容到n的过程中总共移动的次数约为2n平均到n次插入每次插入的扩容成本是O(1)。六、顺序表的优缺点优点支持随机访问按下标取元素是O(1)空间连续CPU缓存友好尾插尾删效率高不需要移动元素缺点中间插入和删除需要移动大量元素效率低扩容时需要重新申请内存并拷贝数据有开销可能浪费空间capacity size的部分适用场景需要频繁随机访问主要在尾部操作元素个数大致可预估七、小结这一篇我们实现了顺序表要点总结要点说明结构data指针 size capacity扩容realloc实现翻倍扩容策略插入从后往前移动元素删除从前往后移动元素复杂度随机访问O(1)插入删除O(n)下一篇我们会讲单链表它解决了顺序表插入删除慢的问题但失去了随机访问的能力。没有完美的数据结构只有合适的选择。八、思考题如果每次扩容只增加10个位置而不是翻倍会有什么问题插入操作中如果插入位置是末尾还需要移动元素吗写一个函数删除顺序表中所有等于某个值的元素要求时间复杂度O(n)。为什么顺序表不适合在头部频繁插入欢迎在评论区讨论你的答案。