C语言实现顺序表：结构体定义、动态扩容与增删改查全解析

1. 为什么顺序表是数据结构的第一道坎

很多人在学数据结构时，习惯性地跳过线性表这一章，直接去看链表和二叉树，理由往往是“顺序表不就是数组嘛，有啥好学的”。这个想法我太熟悉了，因为我自己当年也是这么干的，结果在后来的期末上机和考研408真题里被反复教做人。

顺序表确实底层就是数组，但它是你第一次接触“用代码管理一组动态数据”的地方。数组是编程语言给你的静态容器，而顺序表是这个容器之上的一套完整的操作规范——什么时候扩容、什么时候缩容、插入元素要搬动哪些数据、删除元素后游标怎么走、参数不合法时怎么优雅地拒绝而不是让程序崩掉。这些细节，恰恰是面试和考试最爱挖坑的地方。

这篇内容我用纯C语言完整实现一遍顺序表的增删改查，把每一步代码背后的设计逻辑讲清楚。适合正在学数据结构的学生党、准备考研408的选手、以及从Java/Python转过来想补C语言功底的开发者。C语言的指针和内存管理是绕不开的坎，但正因为绕不开，把它啃下来之后你对计算机的理解会上一个台阶。

2. 顺序表的“地基”：结构体定义与全程容量管理

2.1 为什么C语言实现顺序表必须要结构体

先看一个反直觉的问题：既然数组本身就是顺序存储，为什么我们还要额外封装一个结构体？直接int arr[100];然后定义几个函数操作它不行吗？

不行，而且非常不行。裸数组最大的问题是“长度”和“容量”没有绑定在一起。你用int arr[100]，那么这个数组在任何函数里都只知道自己的容量是100，至于里面实际存了几个有效元素，编译器不管，你得靠另一个变量去维护。当你在多个函数之间传递时，这两个信息很容易脱节——要么忘记更新长度，要么把长度传错，最后越界访问直接Segment Fault。

结构体的价值就在这里：它把底层存储空间、当前有效元素个数、当前容量上限这三个信息打包成一个整体，所有操作函数都只接受这一个参数，内部状态不会散落各处。这跟面向对象里的“封装”思想本质一样，C语言用结构体也能做到。

#define INIT_CAPACITY 8 // 初始容量 typedef struct { int *data; // 指向堆区动态数组的指针 int length; // 当前有效元素个数 int capacity; // 当前容量上限 } SeqList;

这里我用的是int类型的元素。实际工程中，这个int完全可以换成结构体、指针、甚至另一个SeqList——顺序表的逻辑结构跟元素的具体类型无关，这也是它作为“线性表”通用性的体现。在C语言里，如果你想写一套通用的顺序表，可以用void*配合泛型宏，但那是进阶玩法，先把int版本吃透再说。

2.2 初始化函数：malloc分配内存的正确姿势

初始化是第一个坑点高发区。很多初学者图省事，直接在结构体里定义一个定长数组如int data[100]，然后初始化函数只负责把length设成0。这种做法在作业里能跑，但容量定死之后，后面所有“扩容逻辑”就全没了，你的顺序表退化成“定长数组套壳”，毫无实用价值。

正确的做法是：结构体里只保存一个int*指针，真正的数组空间在堆上用malloc动态申请。这样初始容量可以设置得很小，等元素多了再扩容，内存不会被浪费。

int initList(SeqList *list) { // 为什么要用传入指针而不是返回结构体？ // 因为C语言的函数传参是值传递，直接 return 结构体副本， // 会对整个结构体做一次拷贝，浪费性能而且容易误操作。 list->data = (int*)malloc(INIT_CAPACITY * sizeof(int)); if (list->data == NULL) { return 0; // 内存分配失败，返回0表示失败 } list->length = 0; list->capacity = INIT_CAPACITY; return 1; }

两个细节值得展开说。

第一个细节：对malloc返回值的检查不能偷懒。malloc申请内存失败时会返回NULL，如果不加判断，后面的list->data[0]就是对空指针解引用，程序直接崩，排错的时候你根本不知道是哪行出的问题。加上这个判断，至少错误能被定位到初始化函数里。养成这个习惯，以后写链表、树、图那些需要大量动态内存的代码时会少掉很多头发。

第二个细节：为什么初始化容量是8而不是1或1000？设太小，比如1，那么插入第二个元素就要触发一次扩容；设太大，比如10000，如果实际只需存几个数，就白白浪费了约40KB内存。8是个经验值，因为哈希表、STL vector的第一块分配往往也是从很小的值开始，靠后续扩容翻倍增长。容量管理策略的合理性比初始值的大小更重要。

2.3 扩容机制：翻倍扩容为什么是主流

当length == capacity时再插入新元素，数组放不下了。顺序表不像链表那样可以随手new一个节点挂上去，它占用的是一块连续内存地址，容量不够只能另找一块更大的连续空间。这件事在C语言里用realloc完成。

int expandList(SeqList *list) { int newCapacity = list->capacity * 2; int *newData = (int*)realloc(list->data, newCapacity * sizeof(int)); if (newData == NULL) { return 0; // 扩容失败，但原空间依然有效，数据不丢 } list->data = newData; list->capacity = newCapacity; return 1; }

翻倍扩容的逻辑很简单，但背后有个摊还分析的思想挺有意思。假设初始容量8，扩容到16、32、64……插入第9、17、33个元素时各需要搬一次家。累计搬移的元素总数大约是8 + 16 + 32 + ... + n，这个和约为2n，平摊到每次插入操作，额外代价是常数量级的。也就是说，虽然单次扩容是O(n)，但一系列插入操作的平均复杂度依然是O(1)。

对比另一种策略：每次只扩一个位置。那么插入第n个元素时总共搬移了大约1 + 2 + 3 + ... + n次，平摊下来每次插入是O(n)，就非常拉了。这就是为什么所有主流动态数组扩容都采取倍增策略，而不是“加一”策略。

realloc还有个容易踩的坑：它可能会在原来的地址上直接扩展，也可能搬去一块全新的内存区域。无论哪种情况，原来的指针都不能再用了，必须使用realloc的返回值。如果你写成list->data = (int*)realloc(list->data, ...)，万一realloc失败返回NULL，你的原指针也被覆盖丢了，后续想访问原来的数据都不可能——内存泄漏加上数据丢失，双重灾难。所以一定要先暂存在临时变量里，判空后再赋值给list->data。

注意：realloc扩容失败时，原内存块不会被释放，这也是为什么必须用临时变量接住返回值的原因。直接覆盖原指针是新手最常见的致命错误。

2.4 销毁函数：谁说C语言不讲究内存管理

有malloc就一定要有free。很多作业级别的小程序跑完就退出了，操作系统会自动回收内存，所以你感觉不到free的必要性。但一旦你的数据模块被集成到某个常驻程序里，比如嵌入式设备上的菜单系统、服务器上的会话管理器，每次调用初始化都泄漏一块内存，程序跑一天就崩了。

void destroyList(SeqList *list) { if (list->data != NULL) { free(list->data); list->data = NULL; // 防止野指针，指针置空是必须的 } list->length = 0; list->capacity = 0; }

把data置空的作用是：如果之后不小心再次对list->data做free操作，free(NULL)是安全的、什么也不做。如果不置空，二次free就是典型的“double free”，glibc会直接给你报错崩溃。这条习惯可以延伸到C语言所有涉及指针释放的场景。

3. 插入操作：不只是赋值，数据搬移才是关键

3.1 插入的三步走：校验、搬移、写入

顺序表插入元素的核心逻辑是：把目标位置及其后面的所有元素整体向后移动一格，空出来的位置留给新元素。比如现在的数组是[10, 20, 30, 40]，要往下标1的位置插入99，那么先把203040全部往后挪一位，变成[10, 20, 20, 30, 40]，再把99写进下标1，最终[10, 99, 20, 30, 40]。

int insertList(SeqList *list, int index, int value) { // 第一步：参数合法性校验 if (index < 0 || index > list->length) { printf("插入位置非法：index=%d, length=%d\n", index, list->length); return 0; } // 第二步：容量检查，必要时扩容 if (list->length == list->capacity) { if (!expandList(list)) { printf("扩容失败，无法插入\n"); return 0; } } // 第三步：从后往前搬移元素 for (int i = list->length - 1; i >= index; i--) { list->data[i + 1] = list->data[i]; } // 第四步：写入新元素，更新长度 list->data[index] = value; list->length++; return 1; }

3.2 为什么必须从后往前搬移而不是从前往后

这是整个顺序表里最容易写反的一步。如果从前往后搬，比如for (int i = index; i < length; i++) data[i+1] = data[i];，那么第一次赋值就会把data[index]覆盖到data[index+1]，但下一次循环又读取data[index+1]作为新值继续往后覆盖——结果就是后面的元素全变成了同一个值，数据整个烂掉。

从后往前搬之所以安全，是因为每次赋值时，源位置都是尚未被覆盖的。你可以类比挪家具：要把客厅的沙发挪进卧室，你得先清空卧室门口的东西，从最里面开始往外腾，而不是从门口开始往里推，否则堵住了谁也进不去。

同样地，删除操作就是反过来，从前往后搬。如果删除也从后往前搬，你读到的是被覆盖之后的数据，同样会出问题。这两个方向可以总结成口诀：插入从后往前，删除从前往后。

3.3 尾部插入与头部插入：两个极端场景

• 尾部插入：index == length，for循环不执行，直接赋值，时间复杂度O(1)。
• 头部插入：index == 0，所有已有元素都要挪一遍，时间复杂度O(n)。

这个差异很重要。如果业务中频繁向头部插入数据，顺序表就不是一个好的选择，应该用链式存储或者双端队列。反过来，如果业务主要是尾部追加、偶尔按下标定位修改，顺序表则是最佳选择——内存连续，缓存命中率高，访问速度快得飞起。

我在实际工程项目里见过一种尴尬的用法：有人拿顺序表做队列，每次出队都把头部元素删除并搬移所有元素，结果数据量一上来程序卡成狗。这不是顺序表的问题，是数据结构选型没想清楚。先想清楚你的操作模式，再选择数据结构，顺序永远是前者。

4. 删除操作：移动方向错了，整个表就乱了

4.1 删除逻辑与方向问题

删除下标index处的元素，本质是把该位置后面的所有元素整体向前移动一格，然后把length减一。比如[10, 99, 20, 30, 40]，删除下标1的元素，先把20移到data[1]，30移到data[2]，40移到data[3]，最后length变成4。

int deleteList(SeqList *list, int index) { if (index < 0 || index >= list->length) { printf("删除位置非法：index=%d, length=%d\n", index, list->length); return 0; } for (int i = index; i < list->length - 1; i++) { list->data[i] = list->data[i + 1]; } list->length--; // 末尾的残留数据不需要清理，因为length已经说明了有效范围 return 1; }

这里有个细节值得思考：删除之后data[length]位置还残留着旧数据，要不要清掉？答案是不需要，因为顺序表的逻辑长度是length，所有操作都只在[0, length-1]范围内访问。残留数据不会有任何影响。与其画蛇添足地清空，不如把length作为唯一真理。这一点跟“删除数组元素需要把后面元素往前挪”是配套的思想，理解它你就不会在删除后纠结残留值。

4.2 按值删除与按位删除：使用场景的边界

很多教材在“删除”小节里同时列出两种删除方式：删除指定位置的元素，和删除第一个等于某值的元素。作业里你可能两种都要实现，但实际写的时候务必分清楚。

• 按位删除：参数是下标，时间复杂度O(n)，n为搬移的元素个数。
• 按值删除：先要做一次线性查找确定位置，再做搬移，时间复杂度O(n)+O(n)=O(n)。

按值删除通常以整型数据做参数，但如果元素是结构体怎么办？C语言里结构体不能直接用==比较（这跟Java不同），你需要自己写一个比较函数。比如元素是学生信息结构体，按学号匹配就要写if (arr[i].studentId == target)。这个边界别忽略，很多面试题就在这里埋坑，让你实现“删除指定成绩以下的全部学生”，此时你需要的是“删除所有满足条件的元素”，而不是删除第一个。

4.3 删除之后该不该缩容

插入时容量不够要扩容，那删除后容量空了很多，要不要缩容？这是面试里高频追问的问题。

我的建议是：大多数场景不缩容，用“懒缩容”策略。

理由明面上有两个：第一，频繁缩容会引发重复的内存搬移操作，极端场景下，你在某个位置反复插删元素，内存会不断realloc大块换小块、小块换大块，性能崩掉；第二，操作系统向chunk分配内存的策略是“宁多勿少”，你归还的内存未必能立刻用于别处，反而让下一次扩容再付出realloc的代价。

当然，如果明确知道顺序表的使用周期是“一次性大量插入，然后长期少量持有”，比如程序启动时加载配置表，之后只是偶尔查询，那删除到一定程度就可以缩容。更精细的做法是容量缩小到当前容量的四分之一时才触发一次减半操作，避免在临界点上来回抖动。

5. 查找与修改：按下标定位和按值查找的取舍

5.1 按下标查找：它为什么是O(1)

顺序表最引以为傲的能力就是把数组的随机访问特性完整保留下来。data[index]这条语句在底层被编译成*(data + index * sizeof(int))，也就是说，拿到基地址，加上偏移量，直接计算出目标内存地址，一步到位，无论查第1个元素还是第100万个元素，耗时都一样。

这个特性叫随机存取，是顺序存储结构区别于链式存储结构最核心的优势。链式存储里要查第100万个节点，必须从头节点一个个next过去，时间复杂度O(n)。

int getElement(SeqList *list, int index, int *value) { if (index < 0 || index >= list->length) { printf("下标越界：index=%d, length=%d\n", index, list->length); return 0; } *value = list->data[index]; return 1; }

为什么返回值用指针而不是直接return list->data[index]？因为C语言的函数返回值只能表达一个值，我需要同时表达“操作是否成功”和“查到的值”。让返回值表示成功/失败，查到的值通过指针参数带出去，这是C语言里非常常见的惯用法。你一看到这种签名，就该条件反射地想到：返回值是用来判断异常的，不是用来传输主数据的。

5.2 按值查找：遍历的循环不变式

按值查找的思想是扫描整个数组，找到第一个等于目标值的元素，返回它的下标；找不到就返回-1。这里有一个可以提炼的编程模式：

int findElement(SeqList *list, int value) { for (int i = 0; i < list->length; i++) { if (list->data[i] == value) { return i; } } return -1; }

逻辑很简单，但注意三点。

第一，for循环的边界条件必须是i < list->length，而不是i < list->capacity。用容量作为边界会把尚未使用的内存也扫描一遍，当初值为0的预留空间可能包含随机垃圾数据，导致误判。

第二，这个查找只能找到第一个匹配项。如果你要统计所有匹配项的数量，或者要返回所有匹配项的下标集合，它的返回值设计就不够用了。需要把-1约定改成别的方案，比如让你传入一个int results[]数组，返回匹配个数。

第三，因为data是连续内存，某些编译器会自动把这个循环向量化，用SIMD指令一次比较多条数据。这也是顺序表按值查找在工程上并不慢的原因之一——虽然理论复杂度O(n)，但常数因子非常小。考试题里非得把顺序表查找贬得一文不值，那是忽略了硬件加速的现实情况。

5.3 修改操作：定位优先于写值

修改操作的实现思路跟“按下标查找”基本一致，找到位置然后覆写。我这里给加一个保护性的断言：修改前先校验下标，防止越界写操作把不属于你的内存破坏掉。C语言没有数组越界检查，越界写是最难排查的bug之一，因为它常常不会立刻崩溃，而是过了一段时间在完全不相干的变量上报错。

int updateList(SeqList *list, int index, int newValue) { if (index < 0 || index >= list->length) { printf("修改位置非法：index=%d, length=%d\n", index, list->length); return 0; } list->data[index] = newValue; return 1; }

修改的复杂度是O(1)，因为它不需要搬移任何数据。沿着这个思路你会发现一个有趣的组合：“按下标直接改”适合低频小规模修改，“按值查找+修改”适合高频操作且数据有序的场景。如果数据有序，你还能用二分查找把按值查找从O(n)降到O(log n)，这个知识点是后续折半查找章节的敲门砖。

6. 完整测试代码与那些容易翻车的边界细节

6.1 测试主函数怎么设计才能覆盖所有分支

顺序表每个函数都有若干分支，测试用例必须把每个分支都跑一遍才叫覆盖完整。别觉得“这代码这么简单不需要测试”，我见过太多同学在实验报告里只验证了正常插入和正常删除，结果一上机验收，老师输入一个负下标、一个超大容量，程序当场崩掉。

我测试时习惯用一套标准的边界用例清单，按下面几个维度去打：

以上测试全部通过后，顺序表的基础版才算稳了。建议你把每个函数的printf都打上位置和实际参数值，这样出错时不用靠猜。

6.2 最容易翻车的三个边界，逐个排查

第一个翻车点是插入位置恰好等于length。这个场景是合法的（尾部插入），但很多新手写校验条件时写成index >= list->length就直接拒绝了，导致尾部插入永远失败。要记住：插入操作允许index == length，删除操作不允许index == length，这两个集合差一个位置，是日常最容易写混的。

第二个翻车点是扩容后忘记更新length的一致性。有时候测试过程中为了快速定位问题，会直接在list->data[list->length] = value; list->length++这种语句里跳过插入函数，结果后续某次触发扩容，搬移的长度还是旧的，数据错乱。任何绕过封装直接操作内部字段的行为，都是“拆东墙补西墙”。

第三个翻车点是表满与表空状态的判断。插入前判断容量：length == capacity表示满；删除前判断元素：length == 0表示空。如果你把两者搞混，空表里删除不报错，满表里插入也不扩容，所有逻辑全面紊乱。建议在调试时专门打印length和capacity这两个值，别只盯着data里的内容。

6.3 让顺序表真正可复用的两个进阶建议

基础版写完之后，你可以花十分钟做两个升级，把这套代码变成以后能反复使用的工具。

第一个升级是把元素类型抽象出来。在代码顶部写一行typedef int ElemType;，之后所有函数签名和数据字段都用ElemType。等到你在项目里需要存储结构体、字符串指针时，只改这一行加一个比较函数，整个顺序表模块就能复用到新项目里。这比每次遇到新场景就重写一遍整个顺序表要聪明得多。

第二个升级是增加调试函数。写一个printList(SeqList *list)，打印出length、capacity和每个元素的值。你可能会觉得这函数没什么技术含量，但在初始化、插入、删除、扩容之后各调用一次，你就能一眼看出哪个环节把数据弄坏了。我排查过很多链表和顺序表相关的bug，最后定位突破口几乎全靠这个不起眼的打印函数。

顺序表看起来短，但它是整个数据结构课程的第一个关卡。把这一段写扎实，后面学链表时你能自然对比出顺序存储和链式存储的性能差异，学字符串匹配时你能把KMP里的next数组理解成一种特殊的顺序表索引，学操作系统里的页表、文件系统里的目录项，到处都能看到顺序表的影子。从C语言基础语法到完整实现一遍增删改查，这个跨越对熟练度的要求远超你的想象——如果你看完这篇文章能自己独立写一遍并跑通所有边界测试，那顺序表这关就算真正过了。