1. 先搞懂为什么数组用着用着就难受了前几天有个读者在我的博客下面留言说他在 vscode 里配好了 C 语言环境正准备写一个通讯录小项目结果卡在了第一步不知道用数组还是用链表。这个问题特别有代表性很多初学 C 语言的同学都会在写类似学生成绩管理图书管理这类系统时遇到同样的纠结。实际上绝大多数人写的第一个通讯录底层就是一个顺序表只不过他自己没意识到。顺序表是什么简单说就是用一组地址连续的存储单元依次存放线性表中的数据元素。这里有两个关键点第一地址连续决定了它底层一定是用数组实现的第二线性表这个概念强调的是元素之间有一对一的逻辑关系也就是除了第一个和最后一个元素每个元素都有且仅有一个直接前驱和直接后继。我见过太多初学者把这个概念理解成顺序表就是数组这不算全错但也不对。数组是 C 语言自带的一种内置数据类型而顺序表是基于数组实现的一种数据结构。区别在哪里数组本身不关心元素之间的逻辑关系它只是给你一块连续的内存让你存东西而顺序表在这块连续内存之上定义了逻辑相邻的元素在物理位置上也相邻这样的规则并且提供了一套增删改查的操作方法。换句话说数组是原料顺序表是用原料做出来的一道菜。为了让你更直观地理解顺序表到底解决了什么问题我先讲一个翻车现场。假设你写了一个通讯录直接定义了一个固定大小的二维数组char names[10][50]; int phones[10];看起来挺直白十个联系人每个名字最多 49 个字符电话号码用整型存。结果运行一段时间后发现两个问题第一第 11 个联系人添加进来的时候数组已经放不下了程序直接越界写轻则数据错乱重则直接崩溃第二你想删除第 3 个人的信息剩下的人得一个一个往前挪代码写起来非常别扭而且容易漏掉某个元素。这时候你可能会想那把数组开大一点不就行了比如char names[1000][50]。但问题是如果实际只有 5 个联系人你就白白占用了接近 50KB 的内存非常浪费。而且就算你开到 1000万一哪天联系人超过 1000 了呢所以核心矛盾就是定长数组没办法同时满足够用和不浪费这两个要求。顺序表解决这个问题的思路也很朴素——用动态内存分配按需扩容。这就是为什么顺序表能成为数据结构初学者必须掌握的第一个数据结构它几乎涵盖了内存管理、指针操作、边界判断这些 C 语言的核心难点。2. 建表之前先想清楚结构体怎么设计、容量和长度到底哪不一样2.1 不要用裸数组把顺序表封装成结构体我在教学的时候发现一个规律很多人如果只是自己写着玩通常不会把顺序表封装成结构体而是直接定义全局数组和全局变量比如int data[100]; int length 0;这种写法在练习小例子的时候没什么问题但它有两个隐患第一如果程序里同时需要两个顺序表你就得定义 data1、data2、length1、length2代码会变得非常丑陋第二函数传参的时候你没办法把整个表作为一个整体传递只能分开传递数组和长度容易出错。所以正规的做法是把顺序表封装成一个结构体把数据存储在哪和已经存了多少这两个信息绑定在一起#define INIT_CAPACITY 10 typedef struct { int *data; // 指向动态分配的数组空间 int length; // 当前元素个数 int capacity; // 当前能容纳的最大元素个数 } SeqList;这里我用了三个字段前面两个好理解第三个capacity是很多新手容易忽略的。2.2 capacity 和 length 的区别用停车场类比一下就懂了我经常拿停车场打比方capacity相当于停车场总共有多少个车位这个数字在建停车场的时候就确定了length相当于当前实际停了多少辆车这个数字是动态变化的。你不能说停车场有 50 个车位就等于停了 50 辆车也不可能出现停了 60 辆车但停车场只有 50 个车位的情况——如果非要停第 51 辆就得先扩建停车场。对应到代码里就是往顺序表里插入元素之前必须检查length capacity如果不满足就得扩容。很多初学者写的顺序表代码插入几个元素之后就崩溃十有八九就是忘了做这一步检查。2.3 静态数组和动态数组实现优先选哪种顺序表用静态数组实现也有形式是这样的#define MAXSIZE 100 typedef struct { int data[MAXSIZE]; int length; } StaticSeqList;好处是代码简单不需要管内存分配适合应付考试题坏处我刚才已经说了空间固定无法扩容。动态版本用指针在堆上分配内存虽然多了一些 malloc、realloc、free 的操作但这才符合真实工程中的需求。你以后做项目不可能预测用户会录入多少条数据所以动态扩容几乎是必须的。这篇博文后面的所有讨论我都以动态版本为准。3. 核心操作图解插入、删除、查找背后的数据搬运逻辑3.1 插入从中间插进去后面的每个元素都得往后挪顺序表最核心的特征就是逻辑相邻的元素物理位置也相邻这个特征带来一个后果你往中间插入一个元素为了保持物理相邻这个位置之后的所有元素都得整体后移一格。举个例子假设当前顺序表的数据是[10, 20, 30, 40, 50]length 5现在要在下标 2也就是元素 30 的位置插入 25。操作过程如下第一步从最后一个元素 50 开始往后挪一格 [10, 20, 30, 40, 50, 50] 第二步元素 40 往后挪一格 [10, 20, 30, 40, 40, 50] 第三步元素 30 往后挪一格 [10, 20, 30, 30, 40, 50] 第四步把 25 写入下标 2 [10, 20, 25, 30, 40, 50] 第五步length 加 1变成 6注意移动的顺序一定是从最后一个元素开始依次从后往前移动不能反过来。如果从前往后移动前面的元素会把后面的覆盖掉数据就丢了。这个逻辑背下来容易但很多人手写代码的时候还是会错尤其是在循环边界上。对应的插入函数代码如下int seqlist_insert(SeqList *list, int pos, int value) { if (list NULL || pos 0 || pos list-length) { return -1; // 位置不合法 } if (list-length list-capacity) { if (seqlist_expand(list) ! 0) { return -1; // 扩容失败 } } // 从后往前挪元素 for (int i list-length - 1; i pos; i--) { list-data[i 1] list-data[i]; } list-data[pos] value; list-length; return 0; }这里最容易被忽略的是插入位置的合法范围pos可以从 0 到length注意是闭区间。pos等于length的时候相当于在末尾追加这其实是插入操作的一种特殊情况。很多教科书会单独研究头插中间插尾插三种情况其实它们的代码逻辑完全一样只是挪动的元素个数不同头插要挪 n 个中间插要挪 n-pos 个尾插一个都不用挪。3.2 删除本质是覆盖不是真的清零删除操作比插入好理解一些但有一个思维误区需要纠正很多初学者以为删除一个元素就是把那个位置的数据清零。实际上顺序表的删除核心动作是把后面的元素往前覆盖那个被删位置原来的数据是什么已经不重要了因为没有任何逻辑会再访问到它。还是用刚才的例子删除下标 2 的元素 25[10, 20, 25, 30, 40, 50]length 6 第一步把下标 3 的 30 往前覆盖到下标 2 [10, 20, 30, 30, 40, 50] 第二步把下标 4 的 40 往前覆盖到下标 3 [10, 20, 30, 40, 40, 50] 第三步把下标 5 的 50 往前覆盖到下标 4 [10, 20, 30, 40, 50, 50] 第四步length 减 1变成 5关键就在第四步length减 1 之后最后一个位置的旧数据虽然还躺在内存里但从逻辑上它已经不属于这个顺序表了。这就像你用一个记事本记了 5 条待办事项完成了 1 条之后你只需要把后面的条目往上提一行最后一行即使没擦掉你也不会再去读它。对应的删除函数int seqlist_delete(SeqList *list, int pos) { if (list NULL || pos 0 || pos list-length) { return -1; // 位置不合法注意这里是 而不是 } for (int i pos; i list-length - 1; i) { list-data[i] list-data[i 1]; } list-length--; return 0; }注意删除时pos的范围是0 pos length - 1比插入少了一个位置因为pos length时根本没有任何元素可以删。3.3 查找按位置是 O(1)按值是 O(n)顺序表有两种查找语义很多人混在一起导致分析时间复杂度的时候出问题。第一种是通过下标查值也就是int seqlist_get(const SeqList *list, int pos) { if (list NULL || pos 0 || pos list-length) { return -1; // 或者用一个额外的 int* 参数返回结果 } return list-data[pos]; }这本质上就是数组的下标访问编译器直接通过基地址 偏移量计算出目标地址一步到位时间复杂度 O(1)。这也是顺序表最大的优势——随机访问能力。第二种是按值查位置比如找到第一个值为 25 的元素的下标int seqlist_find(const SeqList *list, int value) { if (list NULL) { return -1; } for (int i 0; i list-length; i) { if (list-data[i] value) { return i; } } return -1; // 没找到 }这种查找在一个无序的顺序表里只能顺序遍历最好情况是第一个就命中最坏情况是遍历到最后一个才发现或者根本没找到平均时间复杂度 O(n)。如果你要求顺序表里的数据按某种顺序存放同时数据量很大那就要考虑二分查找了但这要求插入的时候必须维护有序性插入成本会进一步增加这里先不展开。3.4 这些操作的共同本质数据搬运把插入、删除放在一起看你会发现顺序表的核心操作本质上是数据搬运。插入往右搬删除往左搬。这个搬运过程决定了顺序表的时间复杂度操作最好情况最坏情况平均情况尾插O(1)O(1)O(1)头插/中间插O(1)O(n)O(n)尾删O(1)O(1)O(1)头删/中间删O(1)O(n)O(n)按下标查值O(1)O(1)O(1)按值查下标O(1)O(n)O(n)这张表非常值得反复看它几乎就是顺序表所有使用场景的判断依据。你可以把数据搬运想象成搬家住在一条连续的街道上如果有人在中间搬走了后面所有邻居都得往前面挪一个位置这是顺序表绕不开的成本。4. 扩容的秘密小数组如何变成大数组以及为什么有人会写崩4.1 动态内存是顺序表能长大的根源静态数组写死的顺序表永远长不大动态版本的核心在于使用malloc和realloc管理堆上的内存。初始化的时候我们按照初始容量分配一块空间void seqlist_init(SeqList *list) { list-data (int *)malloc(INIT_CAPACITY * sizeof(int)); list-length 0; list-capacity INIT_CAPACITY; }注意检查 malloc 的返回值如果返回 NULL说明内存分配失败int seqlist_init(SeqList *list) { list-data (int *)malloc(INIT_CAPACITY * sizeof(int)); if (list-data NULL) { list-length 0; list-capacity 0; return -1; } list-length 0; list-capacity INIT_CAPACITY; return 0; }4.2 realloc 到底做了什么三种可能的结果当length capacity时再插入元素就要扩容。扩容用的是realloc函数int seqlist_expand(SeqList *list) { if (list NULL) { return -1; } 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的行为很多人理解有偏差它实际上有三种可能第一种情况原内存块后面还有足够的连续空闲空间那么realloc直接就地扩展返回值就是原来的指针。第二种情况原内存块后面空间不够realloc会在堆里重新找一块更大的连续内存把原数据全部拷贝过去然后释放原来的内存块返回值是新地址。第三种情况内存不足realloc返回 NULL。这个时候要注意原来的内存块并没有被释放数据还在但你的指针如果直接赋值给list-data就会把原来的指针覆盖掉导致内存泄漏甚至彻底丢失。所以我上面的写法先把返回值存到一个临时变量new_data里判断不是 NULL 之后再赋值这是个典型的严谨写法。4.3 扩容倍数为什么选 2 而不是加 10再看一个细节扩容倍数为什么是 ×2而不是每次加 10假设顺序表初始容量为 10如果每次追加一个元素就扩容一次每次扩容都要把旧数据全部拷贝到新空间插入 n 个元素的总体复杂度会变成 O(n²)这是不可接受的。而如果按倍数扩容比如从 10 扩到 20、40、80那么数据被拷贝的次数是 O(log n)均摊到每次插入上复杂度接近 O(1)。这就是均摊复杂度的思想——虽然某一次扩容很痛但平摊到每一次插入上就显得微不足道。至于为什么是 2 而不是 1.5 或者其他倍数这是一个经验值。扩容倍数越大扩容次数越少但空间浪费可能更多倍数太小扩容次数多拷贝开销大。2 是一个在空间利用率和时间开销之间比较均衡的选择。4.4 销毁malloc 和 free 必须成对出现写完插入、删除、扩容之后很多初学者会忘了最后一个关键操作——销毁顺序表。C 语言没有垃圾回收你在堆上分配的内存必须自己释放void seqlist_destroy(SeqList *list) { if (list NULL) { return; } free(list-data); list-data NULL; list-length 0; list-capacity 0; }这里有一个好习惯free 之后顺手把指针置为 NULL可以防止后面不小心重复 free 导致程序崩溃也就是所谓的悬空指针问题。真实项目里内存泄漏往往不是一次性爆发的而是每运行一小时泄漏几 KB跑个几天才把内存耗光。顺序表这种基础数据结构更是要养成良好的释放习惯。5. 把顺序表用起来从玩具代码到能跑通的完整小项目5.1 用顺序表实现一个成绩管理核心模块光讲理论容易飘我用一个简单但完整的例子把前面所有函数串起来。场景是读入若干个学生的成绩存进顺序表支持插入、删除、查找、遍历和保存到文件。以下是完整的核心代码结构省略了错误处理细节以保持可读性#include stdio.h #include stdlib.h #define INIT_CAPACITY 10 typedef struct { int *data; int length; int capacity; } SeqList; int seqlist_init(SeqList *list); int seqlist_insert(SeqList *list, int pos, int value); int seqlist_delete(SeqList *list, int pos); int seqlist_find(const SeqList *list, int value); int seqlist_get(const SeqList *list, int pos); int seqlist_expand(SeqList *list); void seqlist_print(const SeqList *list); void seqlist_destroy(SeqList *list); int main(void) { SeqList scores; if (seqlist_init(scores) ! 0) { printf(初始化失败\n); return 1; } // 添加 15 个学生成绩触发扩容 for (int i 0; i 15; i) { if (seqlist_insert(scores, scores.length, 60 i) ! 0) { printf(插入失败\n); seqlist_destroy(scores); return 1; } } seqlist_print(scores); // 在第 5 个位置插入 100 seqlist_insert(scores, 4, 100); seqlist_print(scores); // 删除第 5 个位置 seqlist_delete(scores, 4); seqlist_print(scores); // 查找 70 int pos seqlist_find(scores, 70); printf(70 在第 %d 个位置\n, pos); seqlist_destroy(scores); return 0; }5.2 遍历打印为什么不直接访问 data[i]打印顺序表是调试时最常用的操作我建议把它封装成函数而不是每次手动 for 循环void seqlist_print(const SeqList *list) { if (list NULL) { return; } printf([); for (int i 0; i list-length; i) { printf(%d, list-data[i]); if (i ! list-length - 1) { printf(, ); } } printf(] length%d, capacity%d\n, list-length, list-capacity); }打印的时候我特意同时输出了length和capacity这是个调试小技巧。当你看到length永远不变但capacity越来越大那说明插入逻辑有问题当你看到length超过capacity那说明扩容或者边界判断出了问题。在开发阶段把内部状态打出来比出 bug 了再去猜要高效得多。5.3 加一点文件读写把顺序表存到磁盘顺序表的内容在程序退出后就会丢失所以真实项目里通常还需要持久化。把顺序表写入文件和从文件读入本质上就是把数组顺序写入/读出。这里用最简单的文本格式int seqlist_save(const SeqList *list, const char *filename) { FILE *fp fopen(filename, w); if (fp NULL) { return -1; } fprintf(fp, %d\n, list-length); for (int i 0; i list-length; i) { fprintf(fp, %d\n, list-data[i]); } fclose(fp); return 0; } int seqlist_load(SeqList *list, const char *filename) { FILE *fp fopen(filename, r); if (fp NULL) { return -1; } int n; if (fscanf(fp, %d, n) ! 1) { fclose(fp); return -1; } for (int i 0; i n; i) { int value; fscanf(fp, %d, value); seqlist_insert(list, list-length, value); } fclose(fp); return 0; }注意读文件的时候我用seqlist_insert在尾部追加数据这样复用已有逻辑不用再写一套边界检查。文件读写是很多 C 语言考试和工作中都会遇到的场景把顺序表和文件操作结合起来练一遍两个知识点都巩固了。6. 顺序表 vs 数组 vs 链表一眼看穿它们的本质差异6.1 一张表讲清三者的性能差异写 C 语言的人早晚会遇到用顺序表还是链表的选择题。我先把结论放在这里顺序表和链表不是谁替代谁的关系它们各有自己擅长的场景。维度静态数组动态顺序表链表空间是否固定固定可扩容按需分配随机访问按下标O(1)O(1)O(n)只能遍历头部插入/删除不可行/麻烦O(n)O(1)尾部插入/删除不可行O(1) 摊还O(n)单链表内存连续性连续连续不连续缓存友好性高高低额外空间开销几乎为 0少量每个节点多一个指针这张表里面最值得展开的是缓存友好性。现代 CPU 运行速度远快于内存访问速度所以 CPU 和内存之间有好几级缓存。一次内存访问会把相邻的一块数据都加载进缓存。顺序表在内存里是连续的遍历的时候 CPU 大概率已经在缓存里准备好了下一个元素速度极快。链表节点分散在堆的各个角落每次访问一个节点都可能要重新到内存里取数据缓存命中率低。所以你实际去测性能的时候即使是同样时间复杂度 O(n) 的遍历顺序表经常比链表快几倍到几十倍。6.2 什么时候千万别用顺序表上面的表格是理论落到实际开发中我总结了几种别用顺序表的情况第一元素本身非常大。比如你要存储一个结构体每个元素有几百字节甚至几 KB把它们整体放进一个连续数组里每次扩容都要拷贝整个结构体开销非常大。更合理的做法是用链表每个节点单独分配插入删除时只需要改指针。第二频繁在头部插入或删除。顺序表头插要搬动所有元素链表头插只需要改一个头指针O(1) 和 O(n) 的差距在数据量大的时候是质的差距。第三数据量完全无法预估而且波动剧烈。顺序表扩容虽然均摊成本低但如果发生几百次扩容每次都要搬数据还是会卡顿。链表没有这个问题永远按需分配。反过来如果你需要频繁按下标随机访问、或者你要把数据一次性加载完再批量操作顺序表往往更合适。就比如一个游戏里的怪物列表你只需要挨个遍历让它们行动那顺序表和链表都能用但如果你要做点击第 500 只怪物查看详情那顺序表的下标访问就完胜了。6.3 面试官真正想考你的边界条件顺序表和链表对比是数据结构面试的高频题但很多人背了数组查找快、链表增删快这样的口诀就以为自己会了一问细就露馅。面试官通常会追问几个问题如果频繁在尾部插入顺序表和链表谁快答案是顺序表摊还 O(1)单链表如果只有头指针的话需要遍历到尾才能插入反而是 O(n)。所以链表增删快这句话是不严谨的要看位置。删除一个元素后顺序表为什么不需要把最后一个位置的旧数据清掉因为顺序表的逻辑状态完全由length决定length减 1 之后越界的旧数据不会被任何接口访问到。但从安全角度看如果你存储的是指针最好主动置 NULL否则可能会造成隐性的引用问题。为什么插入位置合法范围是 0 到 length删除位置合法范围是 0 到 length-1因为插入可以在表尾追加一个元素而删除必须真的有一个元素可删。你要是能把这个边界解释清楚面试官就知道你真的写过去操代码而不只是背过概念。7. 实战踩坑记录三个让我调试到怀疑人生的 bug7.1 越界不会立刻崩但会悄悄破坏别人的数据我刚开始写顺序表的时候有一次扩容逻辑写错了插入第 11 个元素时实际分配了 20 个元素的空间但循环里不小心写成了i 20把 20 个位置全部赋值。程序没立刻崩溃因为这块内存后面还有空闲空间数据越界写到了相邻的堆内存上。结果就是后面 malloc 出来的另外一块内存数据被莫名其妙地改掉了表现在程序里就是一个无关的变量突然变成了垃圾值。这个 bug 最难查的地方在于错误发生的位置和表现的位置不在同一个地方。后面排查了很久最后在 insert 里加了边界检查的 assert 才发现。所以我后来写顺序表任何涉及下标的循环都会反复确认边界特别是从后往前搬移元素的时候i--的结束条件特别容易漏。7.2 对空表执行删除操作教科书代码不会告诉你的崩溃如果你把删除函数写成for (int i pos; i list-length - 1; i) { data[i] data[i 1]; } length--;然后对一个空表调用了delete(list, 0)会发生什么pos list-length这个判断会拦住它吗不会因为 0 0 是假条件不成立直接返回 -1看起来没问题。但如果你删除的 pos 恰好等于length - 1也就是删除最后一个元素循环条件i list-length - 1的结果是0 0为假循环体不会执行然后length--把长度减到 length-1整体逻辑是对的。真正危险的是另一种情况如果list-length已经是 0而你的边界判断写的是pos list-length - 1那么pos -1永远为假不会出错如果你写的是pos list-length那就麻烦了pos0 时 0 0 成立进入循环发生越界写。这种边界问题在顺序表里特别常见所以我一直建议初学者把边界检查写到函数第一行并且配合 assert 或自定义错误码尽早暴露问题而不是等到内存被写坏了才追悔莫及。7.3 用 GDB 和 Valgrind 排查顺序表问题最后分享两个非常好用的调试工具。第一个是 GDB它适合排查逻辑错误。比如你想看插入函数执行完之后顺序表内部的状态可以在插入后打断点然后(gdb) p *list $1 {data 0x5555555592a0, length 11, capacity 20} (gdb) p list-data[0]list-length $2 {10, 20, 25, 30, 40, 50, ...}这里的p list-data[0]list-length是 GDB 的一个小语法表示从data[0]开始连续打印length个元素非常适合看顺序表当前的内容。第二个是 Valgrind它适合排查内存问题。编译的时候加上-g选项保留调试信息然后运行valgrind --leak-checkfull ./a.out如果输出里有definitely lost: X bytes in Y blocks说明你的顺序表有内存泄漏十有八九是扩容失败后原来的指针被覆盖或者忘记调用 destroy。如果输出里有Invalid write of size 4说明有越界访问具体到代码行号都能给你标出来。我个人的经验是每写完一个顺序表操作函数就随手套上 Valgrind 跑一遍测试用例养成这个习惯之后内存相关的低级错误会大大减少。顺序表看起来简单但它几乎牵扯到了 C 语言所有重要的基本功结构体、指针、动态内存分配、函数封装、边界判断、文件操作。把它彻底吃透你后面学链表、栈、队列、二叉树都会轻松很多。
顺序表详解：从数组到动态扩容，彻底搞懂C语言数据结构核心
1. 先搞懂为什么数组用着用着就难受了前几天有个读者在我的博客下面留言说他在 vscode 里配好了 C 语言环境正准备写一个通讯录小项目结果卡在了第一步不知道用数组还是用链表。这个问题特别有代表性很多初学 C 语言的同学都会在写类似学生成绩管理图书管理这类系统时遇到同样的纠结。实际上绝大多数人写的第一个通讯录底层就是一个顺序表只不过他自己没意识到。顺序表是什么简单说就是用一组地址连续的存储单元依次存放线性表中的数据元素。这里有两个关键点第一地址连续决定了它底层一定是用数组实现的第二线性表这个概念强调的是元素之间有一对一的逻辑关系也就是除了第一个和最后一个元素每个元素都有且仅有一个直接前驱和直接后继。我见过太多初学者把这个概念理解成顺序表就是数组这不算全错但也不对。数组是 C 语言自带的一种内置数据类型而顺序表是基于数组实现的一种数据结构。区别在哪里数组本身不关心元素之间的逻辑关系它只是给你一块连续的内存让你存东西而顺序表在这块连续内存之上定义了逻辑相邻的元素在物理位置上也相邻这样的规则并且提供了一套增删改查的操作方法。换句话说数组是原料顺序表是用原料做出来的一道菜。为了让你更直观地理解顺序表到底解决了什么问题我先讲一个翻车现场。假设你写了一个通讯录直接定义了一个固定大小的二维数组char names[10][50]; int phones[10];看起来挺直白十个联系人每个名字最多 49 个字符电话号码用整型存。结果运行一段时间后发现两个问题第一第 11 个联系人添加进来的时候数组已经放不下了程序直接越界写轻则数据错乱重则直接崩溃第二你想删除第 3 个人的信息剩下的人得一个一个往前挪代码写起来非常别扭而且容易漏掉某个元素。这时候你可能会想那把数组开大一点不就行了比如char names[1000][50]。但问题是如果实际只有 5 个联系人你就白白占用了接近 50KB 的内存非常浪费。而且就算你开到 1000万一哪天联系人超过 1000 了呢所以核心矛盾就是定长数组没办法同时满足够用和不浪费这两个要求。顺序表解决这个问题的思路也很朴素——用动态内存分配按需扩容。这就是为什么顺序表能成为数据结构初学者必须掌握的第一个数据结构它几乎涵盖了内存管理、指针操作、边界判断这些 C 语言的核心难点。2. 建表之前先想清楚结构体怎么设计、容量和长度到底哪不一样2.1 不要用裸数组把顺序表封装成结构体我在教学的时候发现一个规律很多人如果只是自己写着玩通常不会把顺序表封装成结构体而是直接定义全局数组和全局变量比如int data[100]; int length 0;这种写法在练习小例子的时候没什么问题但它有两个隐患第一如果程序里同时需要两个顺序表你就得定义 data1、data2、length1、length2代码会变得非常丑陋第二函数传参的时候你没办法把整个表作为一个整体传递只能分开传递数组和长度容易出错。所以正规的做法是把顺序表封装成一个结构体把数据存储在哪和已经存了多少这两个信息绑定在一起#define INIT_CAPACITY 10 typedef struct { int *data; // 指向动态分配的数组空间 int length; // 当前元素个数 int capacity; // 当前能容纳的最大元素个数 } SeqList;这里我用了三个字段前面两个好理解第三个capacity是很多新手容易忽略的。2.2 capacity 和 length 的区别用停车场类比一下就懂了我经常拿停车场打比方capacity相当于停车场总共有多少个车位这个数字在建停车场的时候就确定了length相当于当前实际停了多少辆车这个数字是动态变化的。你不能说停车场有 50 个车位就等于停了 50 辆车也不可能出现停了 60 辆车但停车场只有 50 个车位的情况——如果非要停第 51 辆就得先扩建停车场。对应到代码里就是往顺序表里插入元素之前必须检查length capacity如果不满足就得扩容。很多初学者写的顺序表代码插入几个元素之后就崩溃十有八九就是忘了做这一步检查。2.3 静态数组和动态数组实现优先选哪种顺序表用静态数组实现也有形式是这样的#define MAXSIZE 100 typedef struct { int data[MAXSIZE]; int length; } StaticSeqList;好处是代码简单不需要管内存分配适合应付考试题坏处我刚才已经说了空间固定无法扩容。动态版本用指针在堆上分配内存虽然多了一些 malloc、realloc、free 的操作但这才符合真实工程中的需求。你以后做项目不可能预测用户会录入多少条数据所以动态扩容几乎是必须的。这篇博文后面的所有讨论我都以动态版本为准。3. 核心操作图解插入、删除、查找背后的数据搬运逻辑3.1 插入从中间插进去后面的每个元素都得往后挪顺序表最核心的特征就是逻辑相邻的元素物理位置也相邻这个特征带来一个后果你往中间插入一个元素为了保持物理相邻这个位置之后的所有元素都得整体后移一格。举个例子假设当前顺序表的数据是[10, 20, 30, 40, 50]length 5现在要在下标 2也就是元素 30 的位置插入 25。操作过程如下第一步从最后一个元素 50 开始往后挪一格 [10, 20, 30, 40, 50, 50] 第二步元素 40 往后挪一格 [10, 20, 30, 40, 40, 50] 第三步元素 30 往后挪一格 [10, 20, 30, 30, 40, 50] 第四步把 25 写入下标 2 [10, 20, 25, 30, 40, 50] 第五步length 加 1变成 6注意移动的顺序一定是从最后一个元素开始依次从后往前移动不能反过来。如果从前往后移动前面的元素会把后面的覆盖掉数据就丢了。这个逻辑背下来容易但很多人手写代码的时候还是会错尤其是在循环边界上。对应的插入函数代码如下int seqlist_insert(SeqList *list, int pos, int value) { if (list NULL || pos 0 || pos list-length) { return -1; // 位置不合法 } if (list-length list-capacity) { if (seqlist_expand(list) ! 0) { return -1; // 扩容失败 } } // 从后往前挪元素 for (int i list-length - 1; i pos; i--) { list-data[i 1] list-data[i]; } list-data[pos] value; list-length; return 0; }这里最容易被忽略的是插入位置的合法范围pos可以从 0 到length注意是闭区间。pos等于length的时候相当于在末尾追加这其实是插入操作的一种特殊情况。很多教科书会单独研究头插中间插尾插三种情况其实它们的代码逻辑完全一样只是挪动的元素个数不同头插要挪 n 个中间插要挪 n-pos 个尾插一个都不用挪。3.2 删除本质是覆盖不是真的清零删除操作比插入好理解一些但有一个思维误区需要纠正很多初学者以为删除一个元素就是把那个位置的数据清零。实际上顺序表的删除核心动作是把后面的元素往前覆盖那个被删位置原来的数据是什么已经不重要了因为没有任何逻辑会再访问到它。还是用刚才的例子删除下标 2 的元素 25[10, 20, 25, 30, 40, 50]length 6 第一步把下标 3 的 30 往前覆盖到下标 2 [10, 20, 30, 30, 40, 50] 第二步把下标 4 的 40 往前覆盖到下标 3 [10, 20, 30, 40, 40, 50] 第三步把下标 5 的 50 往前覆盖到下标 4 [10, 20, 30, 40, 50, 50] 第四步length 减 1变成 5关键就在第四步length减 1 之后最后一个位置的旧数据虽然还躺在内存里但从逻辑上它已经不属于这个顺序表了。这就像你用一个记事本记了 5 条待办事项完成了 1 条之后你只需要把后面的条目往上提一行最后一行即使没擦掉你也不会再去读它。对应的删除函数int seqlist_delete(SeqList *list, int pos) { if (list NULL || pos 0 || pos list-length) { return -1; // 位置不合法注意这里是 而不是 } for (int i pos; i list-length - 1; i) { list-data[i] list-data[i 1]; } list-length--; return 0; }注意删除时pos的范围是0 pos length - 1比插入少了一个位置因为pos length时根本没有任何元素可以删。3.3 查找按位置是 O(1)按值是 O(n)顺序表有两种查找语义很多人混在一起导致分析时间复杂度的时候出问题。第一种是通过下标查值也就是int seqlist_get(const SeqList *list, int pos) { if (list NULL || pos 0 || pos list-length) { return -1; // 或者用一个额外的 int* 参数返回结果 } return list-data[pos]; }这本质上就是数组的下标访问编译器直接通过基地址 偏移量计算出目标地址一步到位时间复杂度 O(1)。这也是顺序表最大的优势——随机访问能力。第二种是按值查位置比如找到第一个值为 25 的元素的下标int seqlist_find(const SeqList *list, int value) { if (list NULL) { return -1; } for (int i 0; i list-length; i) { if (list-data[i] value) { return i; } } return -1; // 没找到 }这种查找在一个无序的顺序表里只能顺序遍历最好情况是第一个就命中最坏情况是遍历到最后一个才发现或者根本没找到平均时间复杂度 O(n)。如果你要求顺序表里的数据按某种顺序存放同时数据量很大那就要考虑二分查找了但这要求插入的时候必须维护有序性插入成本会进一步增加这里先不展开。3.4 这些操作的共同本质数据搬运把插入、删除放在一起看你会发现顺序表的核心操作本质上是数据搬运。插入往右搬删除往左搬。这个搬运过程决定了顺序表的时间复杂度操作最好情况最坏情况平均情况尾插O(1)O(1)O(1)头插/中间插O(1)O(n)O(n)尾删O(1)O(1)O(1)头删/中间删O(1)O(n)O(n)按下标查值O(1)O(1)O(1)按值查下标O(1)O(n)O(n)这张表非常值得反复看它几乎就是顺序表所有使用场景的判断依据。你可以把数据搬运想象成搬家住在一条连续的街道上如果有人在中间搬走了后面所有邻居都得往前面挪一个位置这是顺序表绕不开的成本。4. 扩容的秘密小数组如何变成大数组以及为什么有人会写崩4.1 动态内存是顺序表能长大的根源静态数组写死的顺序表永远长不大动态版本的核心在于使用malloc和realloc管理堆上的内存。初始化的时候我们按照初始容量分配一块空间void seqlist_init(SeqList *list) { list-data (int *)malloc(INIT_CAPACITY * sizeof(int)); list-length 0; list-capacity INIT_CAPACITY; }注意检查 malloc 的返回值如果返回 NULL说明内存分配失败int seqlist_init(SeqList *list) { list-data (int *)malloc(INIT_CAPACITY * sizeof(int)); if (list-data NULL) { list-length 0; list-capacity 0; return -1; } list-length 0; list-capacity INIT_CAPACITY; return 0; }4.2 realloc 到底做了什么三种可能的结果当length capacity时再插入元素就要扩容。扩容用的是realloc函数int seqlist_expand(SeqList *list) { if (list NULL) { return -1; } 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的行为很多人理解有偏差它实际上有三种可能第一种情况原内存块后面还有足够的连续空闲空间那么realloc直接就地扩展返回值就是原来的指针。第二种情况原内存块后面空间不够realloc会在堆里重新找一块更大的连续内存把原数据全部拷贝过去然后释放原来的内存块返回值是新地址。第三种情况内存不足realloc返回 NULL。这个时候要注意原来的内存块并没有被释放数据还在但你的指针如果直接赋值给list-data就会把原来的指针覆盖掉导致内存泄漏甚至彻底丢失。所以我上面的写法先把返回值存到一个临时变量new_data里判断不是 NULL 之后再赋值这是个典型的严谨写法。4.3 扩容倍数为什么选 2 而不是加 10再看一个细节扩容倍数为什么是 ×2而不是每次加 10假设顺序表初始容量为 10如果每次追加一个元素就扩容一次每次扩容都要把旧数据全部拷贝到新空间插入 n 个元素的总体复杂度会变成 O(n²)这是不可接受的。而如果按倍数扩容比如从 10 扩到 20、40、80那么数据被拷贝的次数是 O(log n)均摊到每次插入上复杂度接近 O(1)。这就是均摊复杂度的思想——虽然某一次扩容很痛但平摊到每一次插入上就显得微不足道。至于为什么是 2 而不是 1.5 或者其他倍数这是一个经验值。扩容倍数越大扩容次数越少但空间浪费可能更多倍数太小扩容次数多拷贝开销大。2 是一个在空间利用率和时间开销之间比较均衡的选择。4.4 销毁malloc 和 free 必须成对出现写完插入、删除、扩容之后很多初学者会忘了最后一个关键操作——销毁顺序表。C 语言没有垃圾回收你在堆上分配的内存必须自己释放void seqlist_destroy(SeqList *list) { if (list NULL) { return; } free(list-data); list-data NULL; list-length 0; list-capacity 0; }这里有一个好习惯free 之后顺手把指针置为 NULL可以防止后面不小心重复 free 导致程序崩溃也就是所谓的悬空指针问题。真实项目里内存泄漏往往不是一次性爆发的而是每运行一小时泄漏几 KB跑个几天才把内存耗光。顺序表这种基础数据结构更是要养成良好的释放习惯。5. 把顺序表用起来从玩具代码到能跑通的完整小项目5.1 用顺序表实现一个成绩管理核心模块光讲理论容易飘我用一个简单但完整的例子把前面所有函数串起来。场景是读入若干个学生的成绩存进顺序表支持插入、删除、查找、遍历和保存到文件。以下是完整的核心代码结构省略了错误处理细节以保持可读性#include stdio.h #include stdlib.h #define INIT_CAPACITY 10 typedef struct { int *data; int length; int capacity; } SeqList; int seqlist_init(SeqList *list); int seqlist_insert(SeqList *list, int pos, int value); int seqlist_delete(SeqList *list, int pos); int seqlist_find(const SeqList *list, int value); int seqlist_get(const SeqList *list, int pos); int seqlist_expand(SeqList *list); void seqlist_print(const SeqList *list); void seqlist_destroy(SeqList *list); int main(void) { SeqList scores; if (seqlist_init(scores) ! 0) { printf(初始化失败\n); return 1; } // 添加 15 个学生成绩触发扩容 for (int i 0; i 15; i) { if (seqlist_insert(scores, scores.length, 60 i) ! 0) { printf(插入失败\n); seqlist_destroy(scores); return 1; } } seqlist_print(scores); // 在第 5 个位置插入 100 seqlist_insert(scores, 4, 100); seqlist_print(scores); // 删除第 5 个位置 seqlist_delete(scores, 4); seqlist_print(scores); // 查找 70 int pos seqlist_find(scores, 70); printf(70 在第 %d 个位置\n, pos); seqlist_destroy(scores); return 0; }5.2 遍历打印为什么不直接访问 data[i]打印顺序表是调试时最常用的操作我建议把它封装成函数而不是每次手动 for 循环void seqlist_print(const SeqList *list) { if (list NULL) { return; } printf([); for (int i 0; i list-length; i) { printf(%d, list-data[i]); if (i ! list-length - 1) { printf(, ); } } printf(] length%d, capacity%d\n, list-length, list-capacity); }打印的时候我特意同时输出了length和capacity这是个调试小技巧。当你看到length永远不变但capacity越来越大那说明插入逻辑有问题当你看到length超过capacity那说明扩容或者边界判断出了问题。在开发阶段把内部状态打出来比出 bug 了再去猜要高效得多。5.3 加一点文件读写把顺序表存到磁盘顺序表的内容在程序退出后就会丢失所以真实项目里通常还需要持久化。把顺序表写入文件和从文件读入本质上就是把数组顺序写入/读出。这里用最简单的文本格式int seqlist_save(const SeqList *list, const char *filename) { FILE *fp fopen(filename, w); if (fp NULL) { return -1; } fprintf(fp, %d\n, list-length); for (int i 0; i list-length; i) { fprintf(fp, %d\n, list-data[i]); } fclose(fp); return 0; } int seqlist_load(SeqList *list, const char *filename) { FILE *fp fopen(filename, r); if (fp NULL) { return -1; } int n; if (fscanf(fp, %d, n) ! 1) { fclose(fp); return -1; } for (int i 0; i n; i) { int value; fscanf(fp, %d, value); seqlist_insert(list, list-length, value); } fclose(fp); return 0; }注意读文件的时候我用seqlist_insert在尾部追加数据这样复用已有逻辑不用再写一套边界检查。文件读写是很多 C 语言考试和工作中都会遇到的场景把顺序表和文件操作结合起来练一遍两个知识点都巩固了。6. 顺序表 vs 数组 vs 链表一眼看穿它们的本质差异6.1 一张表讲清三者的性能差异写 C 语言的人早晚会遇到用顺序表还是链表的选择题。我先把结论放在这里顺序表和链表不是谁替代谁的关系它们各有自己擅长的场景。维度静态数组动态顺序表链表空间是否固定固定可扩容按需分配随机访问按下标O(1)O(1)O(n)只能遍历头部插入/删除不可行/麻烦O(n)O(1)尾部插入/删除不可行O(1) 摊还O(n)单链表内存连续性连续连续不连续缓存友好性高高低额外空间开销几乎为 0少量每个节点多一个指针这张表里面最值得展开的是缓存友好性。现代 CPU 运行速度远快于内存访问速度所以 CPU 和内存之间有好几级缓存。一次内存访问会把相邻的一块数据都加载进缓存。顺序表在内存里是连续的遍历的时候 CPU 大概率已经在缓存里准备好了下一个元素速度极快。链表节点分散在堆的各个角落每次访问一个节点都可能要重新到内存里取数据缓存命中率低。所以你实际去测性能的时候即使是同样时间复杂度 O(n) 的遍历顺序表经常比链表快几倍到几十倍。6.2 什么时候千万别用顺序表上面的表格是理论落到实际开发中我总结了几种别用顺序表的情况第一元素本身非常大。比如你要存储一个结构体每个元素有几百字节甚至几 KB把它们整体放进一个连续数组里每次扩容都要拷贝整个结构体开销非常大。更合理的做法是用链表每个节点单独分配插入删除时只需要改指针。第二频繁在头部插入或删除。顺序表头插要搬动所有元素链表头插只需要改一个头指针O(1) 和 O(n) 的差距在数据量大的时候是质的差距。第三数据量完全无法预估而且波动剧烈。顺序表扩容虽然均摊成本低但如果发生几百次扩容每次都要搬数据还是会卡顿。链表没有这个问题永远按需分配。反过来如果你需要频繁按下标随机访问、或者你要把数据一次性加载完再批量操作顺序表往往更合适。就比如一个游戏里的怪物列表你只需要挨个遍历让它们行动那顺序表和链表都能用但如果你要做点击第 500 只怪物查看详情那顺序表的下标访问就完胜了。6.3 面试官真正想考你的边界条件顺序表和链表对比是数据结构面试的高频题但很多人背了数组查找快、链表增删快这样的口诀就以为自己会了一问细就露馅。面试官通常会追问几个问题如果频繁在尾部插入顺序表和链表谁快答案是顺序表摊还 O(1)单链表如果只有头指针的话需要遍历到尾才能插入反而是 O(n)。所以链表增删快这句话是不严谨的要看位置。删除一个元素后顺序表为什么不需要把最后一个位置的旧数据清掉因为顺序表的逻辑状态完全由length决定length减 1 之后越界的旧数据不会被任何接口访问到。但从安全角度看如果你存储的是指针最好主动置 NULL否则可能会造成隐性的引用问题。为什么插入位置合法范围是 0 到 length删除位置合法范围是 0 到 length-1因为插入可以在表尾追加一个元素而删除必须真的有一个元素可删。你要是能把这个边界解释清楚面试官就知道你真的写过去操代码而不只是背过概念。7. 实战踩坑记录三个让我调试到怀疑人生的 bug7.1 越界不会立刻崩但会悄悄破坏别人的数据我刚开始写顺序表的时候有一次扩容逻辑写错了插入第 11 个元素时实际分配了 20 个元素的空间但循环里不小心写成了i 20把 20 个位置全部赋值。程序没立刻崩溃因为这块内存后面还有空闲空间数据越界写到了相邻的堆内存上。结果就是后面 malloc 出来的另外一块内存数据被莫名其妙地改掉了表现在程序里就是一个无关的变量突然变成了垃圾值。这个 bug 最难查的地方在于错误发生的位置和表现的位置不在同一个地方。后面排查了很久最后在 insert 里加了边界检查的 assert 才发现。所以我后来写顺序表任何涉及下标的循环都会反复确认边界特别是从后往前搬移元素的时候i--的结束条件特别容易漏。7.2 对空表执行删除操作教科书代码不会告诉你的崩溃如果你把删除函数写成for (int i pos; i list-length - 1; i) { data[i] data[i 1]; } length--;然后对一个空表调用了delete(list, 0)会发生什么pos list-length这个判断会拦住它吗不会因为 0 0 是假条件不成立直接返回 -1看起来没问题。但如果你删除的 pos 恰好等于length - 1也就是删除最后一个元素循环条件i list-length - 1的结果是0 0为假循环体不会执行然后length--把长度减到 length-1整体逻辑是对的。真正危险的是另一种情况如果list-length已经是 0而你的边界判断写的是pos list-length - 1那么pos -1永远为假不会出错如果你写的是pos list-length那就麻烦了pos0 时 0 0 成立进入循环发生越界写。这种边界问题在顺序表里特别常见所以我一直建议初学者把边界检查写到函数第一行并且配合 assert 或自定义错误码尽早暴露问题而不是等到内存被写坏了才追悔莫及。7.3 用 GDB 和 Valgrind 排查顺序表问题最后分享两个非常好用的调试工具。第一个是 GDB它适合排查逻辑错误。比如你想看插入函数执行完之后顺序表内部的状态可以在插入后打断点然后(gdb) p *list $1 {data 0x5555555592a0, length 11, capacity 20} (gdb) p list-data[0]list-length $2 {10, 20, 25, 30, 40, 50, ...}这里的p list-data[0]list-length是 GDB 的一个小语法表示从data[0]开始连续打印length个元素非常适合看顺序表当前的内容。第二个是 Valgrind它适合排查内存问题。编译的时候加上-g选项保留调试信息然后运行valgrind --leak-checkfull ./a.out如果输出里有definitely lost: X bytes in Y blocks说明你的顺序表有内存泄漏十有八九是扩容失败后原来的指针被覆盖或者忘记调用 destroy。如果输出里有Invalid write of size 4说明有越界访问具体到代码行号都能给你标出来。我个人的经验是每写完一个顺序表操作函数就随手套上 Valgrind 跑一遍测试用例养成这个习惯之后内存相关的低级错误会大大减少。顺序表看起来简单但它几乎牵扯到了 C 语言所有重要的基本功结构体、指针、动态内存分配、函数封装、边界判断、文件操作。把它彻底吃透你后面学链表、栈、队列、二叉树都会轻松很多。
