数组在手天下我有真不一定。很多C语言初学者写着写着就会碰到一个尴尬场景一开始定义个int arr[100]数据一多就慌少了又觉得浪费后续插入、删除还得手动挪位置整个代码像挤牙膏。这时候顺序表就该登场了。它是数据结构这门课的第一课本质就是把数组“封装”一下让数组具备动态增删改查的能力同时还能自动管理容量。这篇文章就聊聊怎么用C语言从零写一个能用的顺序表包含结构体怎么设计、插入删除怎么挪数据、扩容机制怎么做、还有哪些坑我在实际跑代码时踩过。要说清楚顺序表得先把它和裸数组分开看。裸数组是C语言提供的原生类型而顺序表是在数组基础上抽象出来的线性表实现。你调arr[3]是直接访问内存顺序表则是通过函数接口去操作内部数组外部不用关心数据到底存在哪、容量够不够。这套封装思路在C语言里极其重要后面学栈、队列、哈希表本质上都是同一套手法。所以这篇不只是讲顺序表还在讲一种“如何把数据结构写成可复用模块”的思考方式。1. 顺序表的核心思路为什么不能直接用数组1.1 数组的“硬伤”和顺序表的解法数组最大的问题在于“定死”了。你写int arr[100]意味着最多只能存100个整数。哪天业务数据变成101个程序要么崩溃要么你得手动把数组改成200再重新编译。这在工程里是不可接受的。顺序表的解决思路很直接结构体里存一个指针指向堆上动态分配的内存。每次容量不够了就用realloc开一块更大的内存把旧数据搬过去。这个过程对使用者是透明的——你只管调用seqListInsert(list, pos, val)内部有没有扩容、扩容了多少你不需要知道。关键点顺序表虽然叫“表”物理上还是一块连续内存。它和数组的唯一区别是“能自己长大”而长大这件事通过封装隐藏了。1.2 逻辑结构和物理结构先分清初学者最容易被这个概念绕晕。逻辑结构是“这些数据看起来是什么关系”物理结构是“这些数据在内存里怎么排”。顺序表的逻辑结构是线性的——一个接一个有唯一前驱和后继。物理结构也是连续存储——数组就是连续内存。举例子更直观。你去食堂排队打饭队伍里的人是逻辑上的线性关系你前面是谁、后面是谁。但物理上大家站在不同位置不一定是内存连续的。顺序表相当于让所有人必须用绳拴在一条直线上谁都不能乱跑。链表则是另一个人格大家分散站着但每个人手里拿张纸条写着下一个人在哪。顺序表因为这个物理连续性随机访问特别快——list.elem[i]直接算地址时间复杂度O(1)。但插入删除就惨了因为要保持连续你得把后面的元素全部往后挪最坏情况O(n)。理解了这个后面写代码心里就有数了。1.3 动态扩容的取舍扩容看起来简单实际有讲究。每次扩容扩多少扩太小频繁realloc性能稀碎扩太大浪费内存。常见的做法是容量不够时翻倍也就是newCapacity list.capacity * 2。这个策略在工业界很常用因为均摊下来每次插入的代价是O(1)。为什么翻倍不是“加固定值”假如每次加100一个顺序表从100扩到10万要realloc将近1000次每次还得搬运旧数据累计搬运量是O(n^2)。翻倍的话扩容次数只有10次左右累计搬运量是O(n)均摊到每次插入就是O(1)。这就是“均摊复杂度”的思想面试的时候经常拿来考人。2. 结构体设计C语言封装的起点2.1 结构体的选择三段式设计顺序表的结构体一般长这样typedef struct { ElemType *elem; // 指向数据元素的基地址 int length; // 当前长度 int capacity; // 当前容量 } SeqList;这里用ElemType而不是写死int是一个特别重要的习惯。平时练习时ElemType先用int代替但项目里你得用typedef把元素类型抽出来将来改成结构体、字符串只改一行typedef就行。2.2 为什么需要 capacity 这个字段很多新手写顺序表只存length然后发现插入的时候没法判断要不要扩容。length只能告诉你“目前有几个元素”但“最多还能放几个”你得单独记。capacity就是这个上限。类比一下length 是你现在盘子里的包子数量capacity 是蒸笼最多能放多少个。包子数永远不能超过蒸笼容量不然要么加蒸笼扩容要么包子摞不下越界。2.3 三种变量传递方式值、指针、引用这是C语言的经典考点。初始化顺序表的时候千万不能这么写void initSeqList(SeqList list) { list.elem (ElemType*)malloc(10 * sizeof(ElemType)); list.length 0; list.capacity 10; }为什么不行因为C语言函数的参数是值传递函数内部拿到的是list的副本你改了副本的elem、length外面的原变量一点没变。这就是数组元素改了外面能看到、但指针本身改了外面看不到的原因。正确做法是传入指针void initSeqList(SeqList *list) { list-elem (ElemType*)malloc(10 * sizeof(ElemType)); list-length 0; list-capacity 10; }list-elem等价于(*list).elem先解引用再取字段。从这开始你写顺序表的所有操作都要保持一致统一用指针传入否则很容易出现改了个寂寞的情况。3. 核心操作实现插入、删除、查找的细节与边界3.1 初始化与销毁内存管理的开与合初始化除了分配内存还要做一个关键动作把capacity设置成多少。这直接关系到后续扩容频率。作为练习初始容量设10比较合理。太小频繁realloc太大练习场景浪费。#define INIT_CAPACITY 10 void initSeqList(SeqList *list) { list-elem (ElemType*)malloc(INIT_CAPACITY * sizeof(ElemType)); if (list-elem NULL) { printf(内存分配失败\n); exit(1); } list-length 0; list-capacity INIT_CAPACITY; }有了创建就得有销毁。很多初学者漏了这一步导致内存泄漏。C语言和Java、Python不一样没有垃圾回收malloc出来的内存不主动free程序跑多久就占多久内存。在实际项目里内存泄漏积累起来非常可怕。void destroySeqList(SeqList *list) { free(list-elem); list-elem NULL; list-length 0; list-capacity 0; }注意free之后要把elem置空这是个好习惯。指针不置空就成了“悬空指针”一旦误用可能踩到已经被系统回收的内存产生极其诡异的问题。面试官问到内存泄漏这行代码就是加分项。3.2 插入操作先判满再挪位后赋值顺序表最核心的操作是插入。假设要在下标pos的位置插入元素x整个逻辑分四步int insertSeqList(SeqList *list, int pos, ElemType x) { if (pos 0 || pos list-length) { return 0; // 位置不合法 } if (list-length list-capacity) { expandSeqList(list); // 容量不够就扩容 } for (int i list-length; i pos; i--) { list-elem[i] list-elem[i - 1]; // 从后往前挪 } list-elem[pos] x; list-length; return 1; }这里有两个最重要的边界问题。第一个是pos的范围。合法的插入位置是从0到length不包括length之外。特别注意pos length是合法的这相当于尾插。很多同学只允许pos length结果尾部插入反而成了违规操作这不对。第二个是循环挪数据的方向。一定要从后往前挪也就是先移动最后一个元素再往前逐个移动。如果从前往后挪后面的元素会被前面的覆盖数据直接丢。比如原数组[1, 2, 3, 4]在位置1插入0如果从前往后先把1挪到位置2位置2变成了原来的1再把位置2的值挪到位置3这时候挪的已经不是原来的2了整个数组全乱套。反过来从后往前就安全。3.3 删除操作向前覆盖比“清空”更重要删除下标pos的元素核心思路是把后面的元素往前挪覆盖被删的位置int deleteSeqList(SeqList *list, int pos) { if (pos 0 || pos list-length) { return 0; } for (int i pos; i list-length - 1; i) { list-elem[i] list-elem[i 1]; } list-length--; return 1; }删完之后length--就完事了elem[length]那个槽位还存着旧数据但已经接触不到了——所有操作都通过length来限制范围所以不影响。不需要手动把这个位置清零那是多余操作。不过有一种情形要格外当心如果ElemType是结构体类型且里面含有动态分配的指针删除时得先把指针维护的堆内存释放掉否则也会泄漏。这一点进阶后再踩但思想上要有个数。3.4 查找与修改一处下标两种结果按位置查找很简单就是返回elem[i]但要注意越界检查。按值查找则要遍历整个顺序表找到第一个匹配的位置int findSeqList(SeqList *list, ElemType x) { for (int i 0; i list-length; i) { if (list-elem[i] x) { return i; } } return -1; }按值查找的时间复杂度是O(n)看起来低效但顺序表的优势本就不在这里。线性结构的基础查找就是逐个看关键是要写得干净利落。修改操作则是先find或直接检查pos合法性再重新赋值。这里我得提醒一句C语言比较两个结构体能不能直接用不行。结构体变量之间不能直接用比较需要挨个字段比较或者用memcmp。所以顺序表存整型没问题存结构体时按值查找这一块得重写比较逻辑。这个细节面试经常被挖坑。3.5 扩容函数realloc 到底怎么安全用扩容是顺序表最得意的地方也是最容易泄漏内存的地方。realloc的安全写法void expandSeqList(SeqList *list) { int newCapacity list-capacity * 2; ElemType *newElem (ElemType*)realloc(list-elem, newCapacity * sizeof(ElemType)); if (newElem NULL) { printf(扩容失败\n); return; } list-elem newElem; list-capacity newCapacity; }注意这里先用临时指针newElem接住realloc的结果确认不是 NULL 再赋值给list-elem。为什么不能直接list-elem realloc(...)因为realloc失败时返回 NULL原来的内存不会被释放如果你直接覆盖了list-elem旧指针就找不到了内存泄漏且数据全丢。先用临时变量兜底失败还能保住旧数据。这是教科书式的安全写法。注意realloc如果失败原内存还活着只是没扩容成。所以处理里要明确是直接退出还是保留原状态。练习时为了省事可以exit(1)工程里通常要让它返回错误码。扩容翻倍之后capacity 可能溢出。整型溢出的场景不多见但当你连续插入上千万条数据时capacity * 2会变成负数realloc 申请一块负数大小的内存直接崩掉。严谨的写法要判断newCapacity INT_MAX之类的边界。初学者可以不写但要心里有数。4. 完整代码实现与测试用例直接从能跑到能用4.1 可复制的完整顺序表实现把以上函数拼在一起写一个可运行的完整版本。为演示方便ElemType用int。文件顺序是结构体定义、函数声明、初始化/销毁、扩容、插入、删除、查找、打印、主函数测试。#include stdio.h #include stdlib.h #define INIT_CAPACITY 10 typedef int ElemType; typedef struct { ElemType *elem; int length; int capacity; } SeqList; void initSeqList(SeqList *list) { list-elem (ElemType*)malloc(INIT_CAPACITY * sizeof(ElemType)); if (list-elem NULL) { printf(内存分配失败\n); exit(1); } list-length 0; list-capacity INIT_CAPACITY; } void destroySeqList(SeqList *list) { free(list-elem); list-elem NULL; list-length 0; list-capacity 0; } void expandSeqList(SeqList *list) { int newCapacity list-capacity * 2; ElemType *newElem (ElemType*)realloc(list-elem, newCapacity * sizeof(ElemType)); if (newElem NULL) { printf(扩容失败\n); return; } list-elem newElem; list-capacity newCapacity; } int insertSeqList(SeqList *list, int pos, ElemType x) { if (pos 0 || pos list-length) return 0; if (list-length list-capacity) expandSeqList(list); for (int i list-length; i pos; i--) { list-elem[i] list-elem[i - 1]; } list-elem[pos] x; list-length; return 1; } int deleteSeqList(SeqList *list, int pos) { if (pos 0 || pos list-length) return 0; for (int i pos; i list-length - 1; i) { list-elem[i] list-elem[i 1]; } list-length--; return 1; } int findSeqList(SeqList *list, ElemType x) { for (int i 0; i list-length; i) { if (list-elem[i] x) return i; } return -1; } void printSeqList(SeqList *list) { printf(length%d, capacity%d, [, list-length, list-capacity); for (int i 0; i list-length; i) { printf(%d, list-elem[i]); if (i list-length - 1) printf(, ); } printf(]\n); } int main() { SeqList list; initSeqList(list); for (int i 0; i 15; i) { insertSeqList(list, i, i * 10); } printSeqList(list); insertSeqList(list, 3, 99); printSeqList(list); deleteSeqList(list, 5); printSeqList(list); int idx findSeqList(list, 50); printf(find 50 - index %d\n, idx); destroySeqList(list); return 0; }这段代码可以直接编译运行gcc seqlist.c -o seqlist ./seqlist。主函数里插入15个元素初始容量10跑一次就能看到自动扩容的效果。4.2 测试用例设计思路边界值优先我在调试顺序表时会刻意设计这几类测试数据在头部插入、在尾部插入、在中间插入删除头部、删除尾部、删除中间把一个不存在的值拿去查找第一次插入就触发扩容删除降到空表。边界值是最容易暴露Bug的比如pos length尾部插入、pos 0头插、删除最后一个元素、查找返回 -1 的情况。学习阶段强烈建议自己写个测试函数把这些场景全跑一遍。不要只测主流程。很多时候你在OJ上判题错不是不熟悉操作而是没照顾到边界。这些边界恰恰就是笔试和面试爱考的地方。5. 常见问题与排查技巧从调试器到内存检查5.1 最常见的段错误下标越界顺序表用起来最容易挂在越界上。插入时pos length删除时pos length查找时访问了elem[i]但i超出 length 范围。C语言数组越界不会报错只会悄无声息地读写到相邻内存这也是顺序表调试起来最难受的地方——内存被改坏了崩的地方离出事的地方已经隔了十万八千里。排查越界的一个技巧写个checkValid的内部函数在每个操作入口处打印或断言当前length、capacity、pos。我在练习时会在关键操作前插一行printf(pos%d length%d\n, pos, list.length);定位到具体是哪一步传入了非法下标比对着代码干瞪眼有效得多。5.2 内存泄漏用工具而不只靠眼睛疑似内存泄漏时Visual Studio 里可以用_CrtDumpMemoryLeaks()Linux 下用valgrind --leak-checkfull ./seqlist。这两个工具一跑泄露的位置直接给你标出来。初学阶段为什么会漏大多是因为要么忘了写destroy要么扩容时没用临时指针接住realloc返回值要么删除的是结构体元素却没释放内部自由存储区。我的习惯是写完一组增删操作后先跑一遍valgrind确认 All heap blocks were freed 再继续写下一个功能别等整个程序写完再排查不然问题混在一起脑壳疼。5.3 与数组、链表的选型对比别杀鸡用牛刀顺序表不是万能灵药。它适合“多读少写、随机访问多”的场景比如根据下标查成绩、批量遍历数据。如果业务里插入删除极其频繁比如维护实时的内存碎片列表那还是选链表更好。链表插入删除是O(1)但随机访问是O(n)各有长短。从数据规模看顺序表对缓存特别友好因为连续内存可以有效利用 CPU 缓存预取机制。链表每个节点散落在堆里遍历一轮缓存命中率低数据量大时反而慢。很多初学者觉得链表是高级货其实同等数据量下顺序表往往表现更好。面试时如果你能聊到“缓存局部性”会显得比别人多想了一层。5.4 一个容易被忽略的细节length 和 capacity 要区分清楚导航里反复强调length是实际元素个数capacity是内存容量。别看这俩简单很多段错误都是把length当capacity用、把capacity当length用导致的。一个很典型的问题打印顺序表时用capacity作为循环上限结果把没初始化的内存打出来出现一堆奇怪的数字。记得这两个字段别混。心里默念三遍length才是真正有效的数据边界。5.5 顺带提一下 gdb 调试写C语言不会用调试器等于裸奔。编译时加-g选项然后gdb ./seqlist在可疑的操作函数处设断点比如break insertSeqList运行后用print list.length、print list.capacity、print list.elem[i]看状态next单步走跟一遍就明白问题出在哪了。有些同学喜欢全用 printf 打印数据量小还行数据一大输出刷屏反而不容易看清。gdb 更适合定位逻辑问题printf 适合确认最终结果两个配合着用才是正经工程方式。6. 顺序表之上后续还能怎么扩展写完了顺序表它只是一个起点。后面学数据结构很多地方会复用这套思路。第一个扩展方向是做“线性表的泛型封装”。C语言没有 C 的 template但可以用void*指针 函数指针实现伪泛型让顺序表既能存整型又能存结构体。涉及memcpy做元素拷贝elemSize记录单个元素字节数。这个难度直接飙升但做出来会很有成就感。第二个方向是实现“有序表”和“集合容器”。在插入时做一个二分定位把元素保持有序查找时用二分查找时间复杂度从O(n)降到O(log n)。这就是很多数据库索引的雏形。第三个方向是结合 C 语言文件操作把顺序表的数据持久化到磁盘。用fprintf按行写入再通过fscanf读回。这就是一个简化版的“存储引擎”雏形还能顺手练一下文件缓冲区刷新的知识点。我个人的体会是顺序表这种东西看着简单真正手写了才发现坑都在细节里值传递和指针传递搞混、边界判断少一个等号、realloc 失败处理不到位。建议你照着这篇文章敲一遍再自己跑一遍测试然后关掉代码从头默写一遍。三遍之后C语言的指针、结构体、动态内存管理基本就过关了。这一步踏踏实实迈过去后面学栈、队列、二叉树你会发现自己顺了很多。
