1. 为什么教程都在让你手写顺序表——我理解的三个真实理由很多人第一次接触数据结构看到“手写顺序表”这个练习时第一反应往往是C语言数组不是已经能存数据了吗为什么非要自己封装一层甚至有人直接把int arr[100]玩得溜熟觉得顺序表就是个换皮数组。这个想法非常正常但只对了一半。我先说个结论数组是顺序表的底层存储手段但数组自己不负责“管理容量”这件事。你申请一个int arr[100]从那一刻起它的上限就被写死了。你要是存到第101个元素C语言不会报错恭喜你你踩到了“缓冲区溢出”的地雷——程序可能当时没事然后在你完全不相关的地方突然崩溃这种问题最难排查。顺序表就是给原始数组包了一层“管家”它记住当前存了多少个元素、总容量是多少存满了就自动开辟一块更大的内存把旧数据搬过去然后把旧内存释放干净。我理解手写顺序表的第一个真实理由是让你亲眼看到“扩容”是怎么发生的。很多人背八股文能背出“动态扩容”“搬移元素”“时间复杂度 O(n)”但你问他realloc到底干了啥、为什么扩容后旧指针不能继续用他就卡住了。手写一遍这些问题就再也不需要背。第二个理由是把“逻辑结构”和“物理存储”之间的差别钉进脑子里。顺序表在逻辑上是连续的、有序的序列在物理上就是一段连续内存加一个计数器。你亲手维护这个计数器你会比任何时候都清楚“数组越界”不是编译器的错而是你对边界的理解有漏洞。第三个理由比较现实——笔试和面试真考这个。某公司的笔试环节就考过一道题实现一个支持任意插入位置的顺序表要求插入第 n 个元素时时间复杂度 O(1)。基本功不扎实的人当场就懵了。不是说题目多难而是你平时不是真的自己写过你对“尾部插入”和“头部插入”的代价没有肌肉记忆。所以这篇我打算拿一个最典型的场景做主线从零实现一个支持动态扩容的 Seqlist用它存整型数据实现初始化、尾插、任意位置插入、删除、查找、清空、销毁并配一组完整的测试。我会把容量判断、扩容倍率、内存搬移、数据丢失这些细节全部掰开讲。2. 扩容逻辑的源头设计容量判断、扩容时机与增长倍率手写顺序表之前先想清楚几个关键问题。不然代码写一半你会发现全是 patch这里忘了判断满、那里忘了释放、扩容倍率拍脑袋定了个 1.5 倍结果频繁扩容性能稀烂。这些决策都应该在动手前做掉。2.1 为什么必须记录“容量”和“长度”两个字段一个合格的结构体至少要有三个成员typedef struct { int *data; // 指向底层数组的指针 int size; // 当前元素个数逻辑长度 int capacity; // 当前能容纳的最大元素个数物理容量 } Seqlist;初学者最容易犯的错误是只留一个length每次要判断“是否满”时就去sizeof(arr)/sizeof(int)——这招对真实指针完全无效。data是指针不是数组名sizeof(data)返回的是指针大小在 64 位机器上恒等于 8你算出来的容量永远是 2。所以capacity这个字段不是可有可无的它让程序在任意时刻都知道“我有多少空间”而不是去猜。size和capacity的语义也必须分清楚size表示“已用”即逻辑上有多少个有效元素它决定了遍历、查找、删除的边界。capacity表示“可用”即内存块最多能装多少元素它决定了什么时候需要触发扩容。两者相等时就是“满了”。这是扩容的唯一触发条件。2.2 扩容的两种策略增量扩容与倍数扩容扩容不是“每次加 10 个”或者“每次翻倍”拍脑袋决定的它背后是“摊还分析”的权衡。增量扩容每次扩容固定增加E个元素比如 capacity 10。这种策略的优点是内存利用率高几乎不浪费空间缺点是如果插入次数特别多每次扩容都要搬移一批元素累计搬移次数约为n^2 / (2E)数据量大了以后非常吃亏。比如你插了 10000 个元素每次加 10你可能要扩容 1000 次每次搬移几百上千个元素耗时呈二次增长。倍数扩容每次扩容后 capacity 变成原来的k倍常见倍率是 1.5 或 2。这种策略的优点是搬移总次数大幅下降插入 n 个元素累计搬移约(k/(k-1))*n次摊到每个元素上是常数级所以均摊时间复杂度是 O(1)。缺点是如果你只插入了 11 个元素capacity 却翻到了 16浪费了 5 个“空位”。这一点点浪费对现代机器完全不是事所以主流动态数组的实现基本都用倍数扩容。我自己的实践建议是初学阶段用 2 倍扩容生产级代码建议用 1.5 倍。2 倍逻辑简单好想好写1.5 倍是把 capacity 和已释放的旧内存复用率之间做平衡——翻倍扩容时你新申请的内存永远比所有旧内存加起来还大导致旧内存几乎不可能被新分配复用内存碎片问题更明显。1.5 倍则给系统留了复用旧内存块的机会整体内存利用率更高。这个细节初学不用太纠结但要知道不同倍率背后的取舍。2.3 何时分配、何时搬移、何时释放确定了倍率还得敲定扩容动作本身。我的expand函数内部逻辑是这样设计的static int seqlist_expand(Seqlist *list) { int new_capacity list-capacity * 2; int *new_data (int *)realloc(list-data, new_capacity * sizeof(int)); if (new_data NULL) { return -1; } list-data new_data; list-capacity new_capacity; return 0; }这里我用的是realloc不是先malloc再memcpy再free。原因在于realloc在底层优先尝试在原有内存块后面“续租”如果后面空间够它直接扩大并返回原地址数据都不用搬只有后面不够时才申请新内存、搬数据、释放旧内存。你手动写三步也能实现同样的效果但多了一轮无意义的数据搬运和两次内存操作代码也啰嗦。但realloc有个陷阱它可能返回新地址并把旧地址释放掉。所以你不能写成list-data (int *)realloc(list-data, new_capacity * sizeof(int));一旦realloc失败它会返回 NULL但同时保留旧内存块不释放问题来了——你原来的list-data已经被 NULL 覆盖了旧内存的地址也丢了这叫做“内存泄漏 数据丢失”双杀。正确写法就是先存到临时变量new_data判断非空后再赋给list-data。说完扩容插入前的判断逻辑也清晰了if (list-size list-capacity) { seqlist_expand(list); }这段代码要出现在每次插元素之前而不是某个统一入口。否则你可能会漏掉“中间插入”这条路径。3. 手写一份可运行还带容量保护的 Seqlist 实现理论铺垫完直接上完整代码。这一段我尽量把注释写清楚但读的时候不要只抄注释要想清楚每句话对应的就是前面讨论的哪个决策。3.1 结构体与基础 api 的完整代码#include stdio.h #include stdlib.h #include string.h #define INIT_CAPACITY 4 typedef struct { int *data; int size; int capacity; } Seqlist; // 初始化分配初始内存size 清零 void seqlist_init(Seqlist *list) { list-data (int *)malloc(INIT_CAPACITY * sizeof(int)); if (list-data NULL) { fprintf(stderr, init: malloc failed\n); exit(EXIT_FAILURE); } list-size 0; list-capacity INIT_CAPACITY; } // 扩容容量翻倍失败返回 -1 int seqlist_expand(Seqlist *list) { int new_capacity list-capacity * 2; int *new_data (int *)realloc(list-data, new_capacity * sizeof(int)); if (new_data NULL) { return -1; } list-data new_data; list-capacity new_capacity; return 0; } // 尾插最常用、均摊 O(1) int seqlist_push_back(Seqlist *list, int value) { if (list-size list-capacity) { if (seqlist_expand(list) ! 0) { return -1; } } list-data[list-size] value; list-size; return 0; } // 任意位置插入pos 从 0 开始[0, size] 合法 int seqlist_insert(Seqlist *list, int pos, int value) { if (pos 0 || pos list-size) { return -1; } if (list-size list-capacity) { if (seqlist_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 范围 [0, size-1] int seqlist_erase(Seqlist *list, int pos) { if (pos 0 || pos list-size) { return -1; } // 从前往后覆盖把 pos 后面的元素整体前移 for (int i pos; i list-size - 1; i) { list-data[i] list-data[i 1]; } list-size--; return 0; } // 查找返回下标找不到返回 -1 int seqlist_find(Seqlist *list, int value) { for (int i 0; i list-size; i) { if (list-data[i] value) { return i; } } return -1; } // 按位置访问 int seqlist_at(Seqlist *list, int pos, int *out) { if (pos 0 || pos list-size) { return -1; } *out list-data[pos]; return 0; } // 清空只把 size 归零不释放内存方便复用 void seqlist_clear(Seqlist *list) { list-size 0; } // 销毁释放底层内存指针置空防止野指针 void seqlist_destroy(Seqlist *list) { free(list-data); list-data NULL; list-size 0; list-capacity 0; } // 打印当前状态调试利器 void seqlist_print(Seqlist *list) { printf(size%d, capacity%d\n, list-size, list-capacity); for (int i 0; i list-size; i) { printf(%d , list-data[i]); } printf(\n); }代码量不长但每一段都有讲究。seqlist_insert里的 for 循环从list-size往pos1方向倒着搬移这个顺序如果反了正着从前往后搬你会把data[i]的值写到data[i1]上接着再用data[i1]去覆盖data[i2]——所有元素都会变成同一个值数据直接毁掉。删除时则必须从前往后搬因为覆盖方向是向前的从后往前搬反而会丢数据。这个“方向感”就是顺序表最核心的基本功。3.2 为什么初始化容量设为 4 而不是 1 或 100容量初始值是个好问题。设成 1第一次插就扩容能省内存但这省法毫无意义设成 100如果实际只用 5 个元素白占 95 个int的空间。我见过不少用 100 起步的教程代码那只是图省事谈不上设计。选 4 的理由是第一它足够小任何场景都不会浪费太多第二它很快触达“第一次扩容”让你做实验时立刻能看到扩容日志第三倍增后依次变成 8、16、32、64内存增长速度平滑不会因为初始值太大而掩盖了扩容代码的 bug。初学阶段建议就按 4 来后续想调大一点改成 8 也无妨。3.3 从 main 函数跑通一个完整流程写完 API 还不算完你得真的跑起来。下面这段主函数演示了用法int main(void) { Seqlist list; seqlist_init(list); // 尾插 10 个元素故意超过初始容量 4触发至少两次扩容 for (int i 0; i 10; i) { seqlist_push_back(list, i); } seqlist_print(list); // size10, capacity16 // 在第 2 个位置插 99 seqlist_insert(list, 2, 99); seqlist_print(list); // 0 1 99 2 3 4 5 6 7 8 9 // 删除第一个元素 seqlist_erase(list, 0); seqlist_print(list); // 1 99 2 3 4 5 6 7 8 9 // 查找 6 int idx seqlist_find(list, 6); printf(index of 6 %d\n, idx); seqlist_destroy(list); return 0; }跑这个程序的时候注意观察每次seqlist_print打印的capacity。你会发现第一次是size4, capacity4插入第 5 个元素时 capacity 变成 8插入第 9 个元素时 capacity 变成 16。这个变化过程就是“动态扩容”最直观的证据。4. 把动态扩容完整跑一遍插入、越界、缩容怎么看代码能跑了但我还是建议你亲手做几件事“折腾”一下因为这些折腾最能暴露理解漏洞。4.1 扩容前后地址变化亲眼看看 realloc 做了什么在seqlist_expand里加一行打印printf(expand: old%p, new%p, old_cap%d, new_cap%d\n, (void *)list-data, (void *)new_data, list-capacity, new_capacity);然后重新编译运行。你会看到两种情况某些扩容后新旧地址相同。这是realloc在原内存块后面直接扩展成功的表现数据根本没搬。某些扩容后新旧地址不同。这是系统当前内存碎片化原内存后面空间不够只能另找一块更大的地方然后把旧数据搬过去。不管是哪种扩容完成后旧指针都不能再用了。如果你的代码里某个地方偷偷保存了一份Seqlist里data的旧地址扩容之后那个旧地址指向的内存可能已经被释放你再去访问它属于典型的 use-after-free 错误崩溃和乱数据都算轻的。这也能解释为什么很多人写着写着突然发现“数组越界还能撑一会儿”因为内存没有立刻被覆盖旧地址里的数据还残留着一份副本程序就跑得看似正常实际上全是指向已释放内存的悬垂指针。所以我自己的习惯是——扩容后马上在注释里标注“旧指针作废所有指向 data 的临时变量都需要重新获取”。4.2 越界插入、越界删除、空表操作的统一拦截写进 API 的参数校验不是摆设。我把三种典型情况都列在这里方便你自己测试操作错误示例预期结果中间插入seqlist_insert(list, -1, 10)返回 -1不修改 size不修改数组尾部越界插入seqlist_insert(list, list.size 1, 10)返回 -1拒绝插入删除空表seqlist_erase(list, 0)且 size 0返回 -1不崩不退出访问越界seqlist_at(list, list.size, x)返回 -1out不被写入这里最需要强调的是访问越界如果seqlist_at不校验pos list-size它可能会返回一块未初始化的内存里的“垃圾值”。表面上看程序没崩但实际上你读了不该读的内存。C 语言不像其它语言会给你抛异常它是无声的这比崩溃更危险。所以我要求自己的所有顺序表查询接口必须带返回值表示成功与否把结果写到out指针里。这样调用方可以通过返回值判断是否安全而不是直接拿返回值当有效数据。4.3 缩容该做还是不该做删除了大量元素之后capacity 还是 16但 size 只有 2这种“内存闲置”的情况要不要缩容我的答案分两派。如果是教学练习不做缩容。理由是缩容本身也是一次 O(n) 的搬移操作如果你的程序接下来又要插入新数据缩完还得扩容一缩一扩之间白搬两次数据性能反而更差这叫“抖动”。教学场景里让 size 和 capacity 的差距保持可见反而能让你意识到动态数组的内存管理是“只增不减”的惯性设计。如果是实际项目规定一个“缩容阈值”是可以的比如size capacity / 4时才缩容到一半。而且缩容也必须用realloc缩容失败时要容忍——因为缩容只是优化不是功能。缩容失败不应该让你认为的操作本身失败所以返回码要和真正的错误路径区分清楚。int seqlist_shrink(Seqlist *list) { if (list-size list-capacity / 4) { return 0; // 还没到缩容线不动作 } int new_capacity list-capacity / 2; int *new_data (int *)realloc(list-data, new_capacity * sizeof(int)); if (new_data NULL) { return -1; // 缩容失败最坏情况是继续用原内存 } list-data new_data; list-capacity new_capacity; return 0; }注意缩容里面的“阈值”既划在了capacity / 4缩到capacity / 2而不是一掉到一半立刻缩到一半这就是为了防抖动。你能想到这一步才算真的理解了动态扩容背后的性能逻辑。5. 实测中最容易翻车的三个隐蔽问题代码跑通只是起点。我在给别人 review 代码的时候以下三个问题出现的频率最高而且个个隐蔽编译不报错跑小数据也不崩数据量大点才暴露。5.1 插入元素的数量超过 INT_MAX / 2 时的溢出风险倍增扩容有个隐藏 bug如果 capacity 已经很大了new_capacity list-capacity * 2可能会溢出 int变成负数。realloc收到负数长度后会认为参数非法直接返回 NULL程序就卡在扩容失败上。正常场景里没人会往顺序表里塞 10 亿个元素但作为健壮性设计这一步最好加上if (list-capacity 1024 * 1024 * 1024) { return -1; // 防止溢出也防止无意义扩容 }或者直接把 capacity 改成size_t类型从根上消除溢出问题。初学阶段用int做容量字段更方便打印但要知道它是有天花板的。5.2seqlist_destroy被连续调用两次的崩溃free一个已经释放的指针是未定义行为多数情况下直接崩溃。很多初学者在写完seqlist_destroy之后没有把data置 NULL导致销毁后没有任何标记表示这块内存“没了”。正确做法就是我代码里写的data NULL; size 0; capacity 0;。这样你再调一次free(list-data)时free(NULL)是合法的空操作不会崩。顺便也把capacity置零这样后续如果误操作插入也会在扩容前因为 capacity0 触发异常路径而不会悄悄写内存。5.3 扩容失败但调用方直接忽略返回值看这段代码if (seqlist_expand(list) ! 0) { return -1; }问题是有些人在插入函数里把seqlist_expand的返回值丢了直接继续在后面写list-data[list-size] value。万一内存不足扩容失败data还是原来的容量这一写就越界了。C 语言没有自动帮你处理“扩容失败应该怎么办”的机制所以返回码检查绝对不能省。我的统一约定是所有可能失败的操作一律返回-1表示失败成功返回0。调用方至少要做一次判断。5.4 用 valgrind 验证字节级的正确性光靠肉眼和测试用例还不够我强烈建议你跑一遍内存检测工具。Linux 下可以用valgrindgcc -g -o seqlist_demo seqlist.c valgrind --leak-checkfull --show-leak-kindsall ./seqlist_demo正常的输出应该是All heap blocks were freed -- no leaks are possible。如果它报出Invalid write、Invalid read或者definitely lost那就说明某个位置越界了或者内存没释放干净。我见过有人自信满满地写完代码一查valgrind发现destroy之前某个分支直接 return 了内存泄漏这种问题代码 review 很难看出来工具一抓一个准。6. 把这份代码扩展成“教学级”的进阶方向写完基本版不要急着关掉编辑器。我建议你顺手做三个小扩展每一个都会击中一个盲区总共花不了半小时。6.1 加一个 resize 接口不让容量只管不降int seqlist_reserve(Seqlist *list, int new_capacity) { if (new_capacity list-capacity) { return 0; } int *new_data (int *)realloc(list-data, new_capacity * sizeof(int)); if (new_data NULL) { return -1; } list-data new_data; list-capacity new_capacity; return 0; }这个接口的用处是如果我知道接下来要插入 10000 个数据我可以先seqlist_reserve(list, 10000)一次性把内存分配到位后续 10000 次插入完全不会触发扩容性能提升是可感知的。6.2 让 Seqlist 支持泛型内存块不只用 intC 语言没有模板但我们可以用void *和memcpy实现泛型顺序表。核心思路是底层不再存int*而是存void*的裸内存块插入时传入“元素地址”和“元素大小”扩容时按元素大小 * capacity计算字节数。这个扩展比较费劲但它会逼着你搞明白 C 语言里“类型不过是内存的解读方式”这句话。写过一次void*版本之后你再回去看 STL 的vector思路就通了。6.3 写一组辅助断言让测试跑得更安心除了一堆printf还可以加几个assert检查#include assert.h void assert_seqlist_ok(Seqlist *list) { assert(list-size 0); assert(list-capacity list-size); assert(list-data ! NULL); }然后在每个 API 的开头和结尾各调一次。这样任何一步出错程序会第一时间停下来告诉你“某一刻不变量被破坏了”这个定位成本比崩溃后猜要低得多。我在实际调试过程中发现最初那个“扩容完打印地址”的小实验帮我建立了对realloc最直观的信任——你看着地址变化和数据完整才知道内存里发生的事和教科书上写的一样。这份代码看起来简单但每一次扩容、每一次搬移、每一次释放背后都有值得你反复推敲的内存语义。把它吃透后面学链表、队列、栈都会省力不少。