1. 今天要完成的目标清单顺序表学习计划进入第二天昨天我把顺序表的基本概念、静态存储结构、初始化和遍历操作过了一遍整理了一份基础笔记。今天的内容安排是继续往深处走动态扩容机制、插入删除的完整实现、复杂度分析验证以及把前几天容易踩的坑统一用代码实测一遍。如果你也是跟着计划自学数据结构可能和我昨天的感受一样看书的时候觉得顺序表很简单不就是数组吗但真到了亲手实现的时候会发现边角情况特别多。尤其是插入删除的边界判断、扩容的时机和容量策略这些细节才是让程序“能用”和“好用”的分水岭。day2 的核心任务就是把这些细节彻底搞清楚。今天预计需要 3 到 4 小时不需要一次性做完可以分成两段上午 1.5 小时实现动态扩容和插入删除下午 1.5 小时做复杂度验证和调试记录。建议你给这些操作都配上运行日志后面排查问题会轻松很多。1.1 先花 15 分钟快速复习昨天的核心结论顺序表的本质是用一块连续的内存来存储一组元素元素之间是物理上相邻的。也就是说第 i 个元素在内存中的地址可以这样算起始地址 i * sizeof(元素类型)。这个公式就是顺序表支持随机访问的根本原因——访问任何位置的时间复杂度都是 O(1)不需要像链表那样从头遍历。昨天总结的三个关键点今天还会用到顺序表需要一个记录当前元素个数的变量一般叫size它和数组容量capacity是两个概念。遍历输出、清空、销毁是顺序表的基本操作难度不高重点在于空表情况的处理。静态数组方案有个硬伤容量在编译期就固定了无法在运行时扩展。这直接引出今天的动态扩容实现。我建议你直接打开昨天的代码文件把创建和遍历的函数过目一遍确认没有语法错误后再开始今天的修改。因为今天的代码是基于昨天的结构体扩展的底层字段不变只是增加了容量管理和重新分配逻辑。1.2 今天重点攻克的两大模块今天的学习范围我拆成了两大模块每一块都有明确的验收标准模块一是“动态扩容机制”。静态数组变成动态数组核心区别就是在插入元素发现空间不足时能够重新申请一块更大的内存把旧数据搬过去然后释放旧内存。验收标准是连续插入超过初始容量的数据后程序不崩溃且所有元素正确可达。模块二是“插入与删除的完整实现”。包括按位置插入、按位置删除、按值查找三个核心操作。验收标准是头插、尾插、中间插入三种场景都正确删除后size正确递减且未删除元素的前后顺序不被打乱。复杂度分析方面今天会用实际运行数据来验证教科书结论尾部插入接近 O(1)头部插入是 O(n)扩容虽然偶尔是 O(n)但摊还下来仍然可以接受。后面我会详细展开这部分。2. 动态扩容顺序表的“接口升级”2.1 静态数组与动态数组的本质差异昨天用的顺序表结构体可能是这样定义的#define MAX_SIZE 100 typedef struct { int data[MAX_SIZE]; int size; } SeqList;MAX_SIZE一旦定死这张表最多只能存 100 个元素。如果你尝试插入第 101 个要么直接报错要么因为越界写出未定义行为。实际项目里数据规模往往要到运行时才知道写死容量是非常别扭的方案。动态版本的核心改动是把定长数组换成一个指针typedef struct { int *data; int size; int capacity; } SeqList;capacity表示当前总共能容纳多少元素size表示已经存了多少个。data在初始化时通过malloc申请一块初始容量大小的堆内存。这样当size capacity时我们就知道表满了可以调用扩容函数“升级接口”。注意malloc申请的内存是在堆上需要手动释放。昨天用静态数组时没有这个顾虑今天开始每个创建出来的顺序表都要对应一次destroy操作否则会内存泄漏。顺带说一下为什么用指针替代定长数组这件事很关键定长数组的容量是编译器在栈上分配的栈空间本身有限几兆字节就可能溢出。堆空间则大得多而且可以在程序运行期灵活伸缩。这让顺序表从“写死的纸箱”变成了“可以拼装的收纳柜”。2.2 扩容的完整流程和容量选择策略扩容的实现流程官方说法叫“重新分配”步骤拆开看就三步申请一块新内存容量是原来的 k 倍。把旧内存里的size个元素按顺序复制到新内存。释放旧内存更新data指针和capacity字段。用代码写出来长这样int expand(SeqList *list) { int new_capacity list-capacity * 2; int *new_data (int *)malloc(new_capacity * sizeof(int)); if (new_data NULL) { return -1; // 扩容失败 } for (int i 0; i list-size; i) { new_data[i] list-data[i]; } free(list-data); list-data new_data; list-capacity new_capacity; return 0; }这里有几个细节值得单独说明。第一为什么扩容倍数通常是 2而不是 1.5 或者固定加 100原因在于复杂度分析如果每次扩容固定增加 100那么插入 n 个元素时扩容次数大约是 n/100而每次扩容要复制所有旧元素总复制次数是100 200 300 ... n数量级是 O(n²)。如果每次翻倍扩容次数是 log n 次总复制次数是1 2 4 8 ... capacity约等于 2n数量级是 O(n)。也就是说翻倍扩容能把“累积复制成本”摊到每次插入上让单次插入的摊还复杂度接近 O(1)。这一点如果你不亲手算一遍看多少教程都容易忘。第二realloc函数能不能直接用能用但有一个行为需要清楚realloc可能原地扩展也可能把数据搬到另一块新内存。在前一种情况下旧指针保持有效后一种情况下旧指针自动失效。所以如果realloc失败返回 NULL你手里的旧指针依然有效但代码里如果把返回值直接赋给list-data旧指针就丢了。安全写法是先用临时指针接收返回值判断非空后再赋值int *new_data (int *)realloc(list-data, new_capacity * sizeof(int)); if (new_data NULL) { return -1; } list-data new_data;这个技巧在很多场景下通用不只是顺序表。凡是涉及“重新申请 原指针可能失效”的地方都建议先用临时变量中转。第三扩容时是否要检查new_capacity是否溢出当capacity接近INT_MAX / sizeof(int)时乘法结果会溢出变成负数导致malloc申请一个荒谬的尺寸。虽然实际练习很难碰到但作为一个合格的程序员在接口里加一道防御逻辑是值得的if (list-capacity INT_MAX / 2) { return -1; }不少生产级代码里就藏着这种判断看着不起眼关键时刻能救命。2.3 扩容触发时机与“懒扩容”思路扩容不是每次插入都做。插入函数里先判断size capacity不相等就直接写数据相等才调用expand。这个设计叫做“懒扩容”不提前多申请也不频繁申请只在满了的瞬间翻倍兼顾了空间利用率和时间成本。还有一个思路是“预留容量”。比如你知道接下来要批量插入 1000 条数据而表里现在只有 100 个位置就可以先调用一个reserve函数把容量直接扩到 1200避免插入过程中反复扩容。这个函数本质上就是一次“未满时的提前扩容”int reserve(SeqList *list, int target_capacity) { if (target_capacity list-capacity) { return 0; } int *new_data (int *)malloc(target_capacity * sizeof(int)); if (new_data NULL) { return -1; } for (int i 0; i list-size; i) { new_data[i] list-data[i]; } free(list-data); list-data new_data; list-capacity target_capacity; return 0; }批量导入数据的场景下reserve的价值非常明显。它和realloc的区别在于你想把容量扩到任意指定大小而不是固定按倍数走。这个函数在很多高级语言的标准库里都存在比如某些动态数组容器里的reserve方法理解了原理你就知道那个方法内部在做什么。3. 插入与删除边界才是重头戏3.1 插入操作的四种位置分类顺序表的插入操作逻辑上要处理四种情况合法位置中间插入、头部插入、尾部插入、非法位置插入。绝大多数初学者写得不好的原因是把这四种情况混在一起没有先做合法性检查。完整版插入函数我建议这样写int insert(SeqList *list, int pos, int value) { if (list NULL || pos 0 || pos list-size) { return -1; // 位置不合法 } if (list-size list-capacity) { if (expand(list) ! 0) { return -1; } } for (int i list-size; i pos; i--) { list-data[i] list-data[i - 1]; } list-data[pos] value; list-size; return 0; }合法性判断为什么是pos list-size而不是pos list-size因为顺序表允许在末尾追加元素此时pos size插入后新元素正好落在合法范围内。如果写成pos list-size尾插功能就废了这是个非常经典的边界错误。搬移元素时为什么要从后往前循环因为如果从前往后前面的元素会先覆盖掉后面的元素数据就乱了。从后往前搬移每个位置先腾空再接收前一个元素的值才能保住顺序。这个细节是插入操作最容易出错的地方建议你在草稿纸上画一遍 5 个元素的搬移过程胜过背十遍代码。头部插入是插入操作里最耗费时间的操作所有元素都要向后挪一位时间复杂度 O(n)。尾部插入不涉及搬移时间复杂度 O(1)。插入到中间则取决于插入位置平均要搬移一半的元素。这也是为什么顺序表适合“随机访问频繁、插入删除少”的场景而不适合“频繁在头部插入”的场景。3.2 删除操作与元素搬移方向删除函数的合法范围是0 pos size注意这里和插入不同pos size时指向的是表中不存在的位置非法。删除逻辑里最关键的细节是搬移方向删除第 pos 个元素后应该把pos1到size-1的元素都向前挪一位。int removeAt(SeqList *list, int pos) { if (list NULL || pos 0 || pos list-size) { return -1; } for (int i pos; i list-size - 1; i) { list-data[i] list-data[i 1]; } list-size--; return 0; }这里有两个容易被忽略的点。第一搬移是data[i] data[i1]方向是从前向后拿数据。第二搬移结束后最后一个位置上的旧值不会被真正“清零”只是size--之后它已经不在有效范围内了。有些初学同学会在删除后手动把data[size] 0这不算错但如果你存的是复杂对象这么做反而可能掩盖问题。对于基本类型不需要清理。关于删除后的容量策略有个我踩过的坑想单独拿出来说。有些教程建议当size capacity / 2时就缩容一半省内存。但在实际使用中如果用户刚好在临界值附近反复插入、删除就会导致扩一次、缩一次、再扩一次形成“抖动”。这个问题在数据库缓冲池、动态数组容器里都有名叫 shrink 抖动。初学者阶段我的建议是先不要缩容把内存还给系统这件事交给destroy统一处理就够了。等到你做内存敏感的项目再研究左倾右倾缩容阈值的调优方案。删除操作的时间复杂度是 O(n)原因同样是元素搬移。删除尾部元素不需要搬移是 O(1)。所以“栈”这个数据结构如果用顺序表实现入栈出栈都是在表尾操作效率非常高。这个思想你在后面学栈的时候会再见到现在先有个印象。3.3 按值查找与返回位置的实现按值查找的逻辑比较简单从头到尾遍历找到第一个值相等的元素返回下标找不到返回 -1。int search(SeqList *list, int value) { for (int i 0; i list-size; i) { if (list-data[i] value) { return i; } } return -1; }这里演了一遍才发现单纯按值查找的时间复杂度是 O(n)。这也是顺序表的劣势之一随机访问快按值搜索慢。如果数据量很大且查找频繁应该引入哈希表或者排序后二分查找但那属于后面的内容今天不做展开。顺序表查找的一个优势是在数据有序的情况下你可以用二分查找把复杂度降到 O(log n)不过那要求插入时维护有序性插入成本会进一步增加。今天先把基础版写对把“线性查找”的特征记录下来后面学查找和排序时再对比。4. 复杂度分析亲手验证 O(1) 和 O(n)4.1 时间复杂度的推导过程教科书上写“顺序表的插入和删除是 O(n)”这个结论需要真正理解才能变成自己的东西。我习惯从“操作的代价”角度去推一次插入操作的总时间 定位时间 搬移时间 写入时间。定位时间是 O(1)写入时间是 O(1)搬移时间取决于插入位置到表尾的距离。插入到头部搬移 n 个元素代价是 n插入到尾部搬移 0 个元素代价是 1。所以“最坏情况 O(n)、最好情况 O(1)”这个说法本质就是看搬移了多少个元素。平均情况呢假设插入到每个位置的概率相等那么插入到位置 i 需要搬移n - i个元素取平均得到(n n-1 ... 0) / (n1) n/2。常数因子 1/2 在时间复杂度里被忽略所以平均复杂度还是 O(n)。复杂度里隐藏的一个要点是“大 O 记号”丢弃的是常数倍和低阶项。这个习惯在算法题里非常好用但到了实际工程里一个常数因子为 100 的 O(n) 算法可能比一个常数因子为 1 的 O(n²) 算法在 n 较小的时候更慢。所以“大 O 快”不等于“实际上快”要结合数据规模看。这个观点我是在做某跨平台系统的数据同步模块时才有切身体会的当时为了追求 O(log n) 的算法引入了一棵复杂的树结果在小数据集上性能反而不如线性扫描。现在想起来依然觉得这个取舍值得记录。4.2 扩容的摊还复杂度到底怎么算扩容操作本身是 O(n)因为它要把所有元素复制一遍。如果每次扩容都是 O(n)那插入操作是不是也应该算 O(n)这里就用到“摊还分析”的思想了。摊还分析不看单次操作而是看一个连续操作序列的总代价。假设初始容量是 1连续插入 n 个元素。扩容发生在第 1、2、4、8 ... 次插入时每次扩容的复制量分别是 1、2、4、8 ...直到超过 n。所有扩容的总复制量是1 2 4 ... n/2 n - 1量级。普通插入不扩容时每次代价是 O(1)n 次插入的普通代价是 n。总代价就是 n (n-1) ≈ 2n摊到 n 次插入上每次大约 O(1)。这个结论非常重要动态数组的尾部插入在摊还意义上是 O(1) 的扩容偶尔带来的卡顿可以被其他快速操作吸收。这也是为什么很多高级语言的动态数组容器在大量尾部插入时依然表现良好。理解摊还分析后你不会再因为“扩容是 O(n)”而不使用动态数组。我用一个生活类比扩容就像你每隔一段时间要搬一次家。平时住小房子很省租金但每搬一次家都要打包所有行李很痛苦。可如果搬家次数足够少翻倍扩容相当于东西越多搬得越不频繁平均下来每次入住新东西的成本就很低。你要是每次只多放一个柜子就搬家那才是灾难。4.3 用运行数据验证理论推导看书推导是一回事亲手跑数据是另一回事。我建议你写一个测试函数分别统计头部插入和尾部插入的实际耗时差异以及扩容次数。一个简单的验证思路是初始化容量为 8 的顺序表连续插入 100 万个元素记录扩容次数并统计尾部插入的总耗时。理论预测是扩容次数约为log2(1000000/8)大约 17 次。实测下来次数应该完全一致。再对比头部插入每次插入都要搬移全部元素插入 100 万个头部元素的总代价大约是n² / 2这个量级。你会发现头部插入的耗时会比尾部插入高好几个数量级。这就是复杂度分析对实际工程的意义——不是什么玄学是真的能在数据上看到差距。我写测试时习惯在expand函数里加一个全局计数器或者打印语句记录扩容前后的容量变化和复制元素个数。这样做的好处是如果程序中途崩溃你能从日志里看到最后一次扩容发生在哪里快速定位问题。5. 常见问题与排查技巧实录5.1 空表和容量为零的极端情况动态数组初始化时capacity可以设成 0让第一次插入时自动触发扩容。但这样写有一个坑expand里执行capacity * 2时0 乘 2 还是 0扩容永远失败。所以要么初始化容量至少为 1要么在扩容时对 0 容量单独处理int expand(SeqList *list) { int new_capacity list-capacity 0 ? 1 : list-capacity * 2; ... }这个问题我第一次实现时没遇到因为我把初始容量设成了 8。但后来给同学 review 代码时发现他们把初始容量设为 0结果插一个元素失败一次。这个坑值得记下来属于“边界初始化”问题面试时也偶尔会被问。空表情况下执行删除操作pos list-size会直接拦截因为size为 0任何非负的 pos 都越界所以删除空表不会崩溃。插入操作如果合法位置是 0且表为空这是正常的第一个元素插入。测试用例里建议把“空表头插”“空表尾插”“空表删除”“空表查找”四个场景都跑一遍一道也不放过。5.2 扩容后指针失效问题动态扩容后data指针可能指向新内存旧地址已经释放。如果代码里有一个辅助指针还保存着旧地址然后用它访问元素就会出现“悬空指针”轻则读到随机值重则段错误。我在某图像处理 Demo 的开发中遇到过这个问题图像像素数据用顺序表管理另一个模块缓存了指向像素数组的指针扩容一次后那个缓存指针就变成野指针了图像显示出现随机花斑。排查了很久才发现是扩容后指针未同步更新。这个问题的教训是凡是保存了指向内部缓冲区的指针都必须保证在扩容后重新获取最新地址或者干脆不要长期持有内部指针。所以在设计接口时我强烈建议不要向外暴露data的原始指针。外部代码需要访问元素时通过类似get(list, index)的接口来取这样扩容时内部怎么变化外部无感知。5.3 缩容抖动的实战教训前面提到缩容抖动这里讲一个实际案例。某跨平台系统里有一段日志缓冲代码最初是按“低于一半容量就缩容”的策略写的。表现是数据量在临界值附近波动时缓冲区频繁重新分配性能下降非常明显CPU 峰值比正常多了 30%。后来改成“低于四分之一容量才缩容并且一次缩到一半”抖动才消失。这个经验其实在很多开源库里都能看到比如某些动态数组容器就是缩容阈值比例设为容量的一小部分而不是二分之一。背后的逻辑很简单容忍一定的空间浪费换取操作稳定性。程序员的直觉常常是“省内存优先”但真实场景里内存和性能的平衡点才是最终指标。如果你现在写练习代码我建议不要实现缩容注释里写清楚“预留缩容接口后续优化时实现”这也是一种专业性的体现。知道什么功能现在不做和知道什么功能要做同样重要。5.4 关于程序崩溃的几个快速定位方法要说我最常用的调试技巧就是在关键函数入口用fprintf(stderr, ...)打印日志。顺序表代码量不大用打印大法其实很快。插入函数入口可以打printf(insert: pos%d, value%d, size%d, capacity%d\n, pos, value, list-size, list-capacity);扩容函数里可以打printf(expand: %d - %d, size%d\n, old_capacity, new_capacity, list-size);这样一旦程序崩溃你能直接看到是插入前崩溃还是插入后size没更新还是扩容时内存不够。配合gdb做断点调试更好不过在工程规模不大时打印日志往往更快。等你工作了在大型系统里排查问题第一件事往往也是看日志从这点看数据结构学习阶段养成的打日志习惯会伴随你整个职业生涯。还有一个细节打印size_t类型的字段时注意使用%zu而不是%d否则在 64 位系统上可能打印出错误值。这个坑不大但遇到了会迷惑一阵子。5.5 测试用例设计清单手工测试顺序表我建议固定测这组用例测试场景输入预期结果实际常见错误空表尾插空表insert(0, 10)size1, data[0]10扩容函数容量为 0 导致失败满表扩容插入容量 4连续插 5 个第 5 个成功capacity 变为 8忘记判断 size capacity头部插入表 [2,3]insert(0, 1)表 [1,2,3]搬移方向错误导致元素覆盖尾部插入表 [1,2]insert(2, 3)表 [1,2,3]合法性判断写成 pos size中间插入表 [1,3]insert(1, 2)表 [1,2,3]搬移起点/终点错误非法位置插入表 [1]insert(5, 9)返回 -1表不变没有合法性检查直接越界写头部删除表 [1,2,3]removeAt(0)表 [2,3]搬移循环边界写错删除后 size 更新表 [1]removeAt(0)size0后续插入正常size 递减忘记导致伪满每一条用例跑完后都检查一遍size和capacity的值这才是真正的“亲手验证”。我在学习阶段会用assert在关键位置做自动检查比如插入后assert(list-size list-capacity)。如果你不想手工核对可以在代码里加一堆断言让程序替你检查。写在后面的一些私人体会两天学下来我对顺序表最大的体会是它看起来简单但所有“基础数据结构”里的坑它一个都不少。边界检查、资源管理、复杂度权衡、调试方法这些能力都能在顺序表这个小型项目里得到一轮完整的锻炼。如果直接把顺序表代码背下来换不来这些能力那损失就大了。今天最后还想分享一个小技巧学习数据结构时每个结构学完都画一张“操作耗时表”把头部插入、尾部插入、中间插入、按位置访问、按值查找这些操作的复杂度写在同一张表里。后面学链表、栈、队列、树的时候把这表格横向对比你会发现所有结构的取舍逻辑都串起来了。这个方法我用了很多年每次复习都靠它快速进入状态。day2 的内容到这里就收尾了。明天进入顺序表和链表的关键对比我会把两者在真实业务场景里的选型逻辑拆开再讲一遍到时候这张操作耗时表就是最重要的参考工具。