C语言线性表顺序存储实现与避坑指南（含动态扩容）-开发者社区

简介：一份面向C语言初学者与数据结构学习者的专题讲解，系统梳理线性表顺序存储结构的核心知识点，包括顺序存储定义、结构体设计、初始化、获取元素、插入与删除操作等关键环节，并配有可直接参考的代码示例，适合正在学习线性表或复习数组存储应用的读者。包体为1个PDF文档，压缩包大小仅41KB，轻量便携，便于随时查阅。该资源已有4257人学习下载，属于入门级高人气资料。通过这份讲解，读者可以理解顺序存储的连续内存分配原理与动态扩容思路，掌握基于结构体和malloc的线性表实现方法，并学会处理位置合法性检查、元素移动等常见编程细节；同时，结合初始化、插入、删除等操作实例，还能熟悉动态内存管理和数组元素移动的典型写法，为后续链表、栈和队列等数据结构的学习打下扎实基础。

1. 线性表顺序存储结构：数组写死就容易翻车，这份实例把坑提前踩完了

用C语言写线性表，第一反应是“不就是个数组嘛”，可真到动手时才发现，容量怎么定、插到中间怎么挪、空间不够怎么扩，每个点都能让人卡住。这份实例讲的就是C语言线性表顺序存储结构的完整实现——用一段地址连续的存储单元依次存放数据元素，通过结构体把数组指针、当前长度、分配容量包在一起，再实现初始化、插入、删除、取值这些基本操作。它适合正在学数据结构、刚接触结构体和指针的读者，也适合想搞清楚动态数组到底怎么扩容的写代码的人。整个实例的代码量不大，但把顺序表最容易出错的环节都涉及了，值得跟着敲一遍再改一遍。

2. C语言顺序存储结构的设计：为什么是数组，以及结构体里三个成员各管什么

2.1 地址连续带来的访问特性与代价

顺序存储结构的核心特征是物理位置连续，也就是说，线性表里逻辑上相邻的元素，在内存里也相邻存放。这个特性带来的直接收益是随机访问效率高：想取第 i 个元素，不需要从头遍历，直接用数组下标就能拿到。在C语言里，数组恰好就是这种连续内存的天然载体，所以顺序表用数组实现最顺手。

第 i 个元素的地址 = 基地址 + (i - 1) * sizeof(元素类型)

这里的一个关键点在于：线性表的位序是从 1 开始计数的，而C语言数组下标从 0 开始，所以第 i 个元素实际存储在elem[i-1]。这个“差一位”的问题，在实际写代码时最容易出错，后面取值和插入删除都要盯着它。

连续存储的代价也很明显：插入或删除一个元素时，为了保持逻辑顺序，往往需要移动大量元素，平均时间复杂度是 O(n)。此外，初始化时必须预先分配一段连续空间，如果预估不准，后面要么浪费、要么不够用。

这份实例在设计上采用了一个比较实用的折中：先分配一个初始容量，不够时再按增量扩容，而不是一次性给够。这种动态数组的思路，在不需要频繁插入的场景下，比链表更省内存访问开销。

2.2 SqList 结构体：elem、length、size 的分工

实例中定义的结构体是整份代码的地基：

#define Max 80 // 存储空间初始分配量 #define Increment 10 // 存储空间分配增量 typedef struct { int *elem; // 存储空间基地址 int length; // 线性表当前长度 int size; // 当前分配的存储容量 } SqList;

三个成员的分工很明确：

成员	作用	说明
elem	指向动态数组的首地址	用 malloc 分配，类型可以换成其他数据类型的指针
length	当前表中元素个数	有效元素数，不是数组容量
size	当前分配的最大容量	length 永远小于等于 size

定义时把elem声明成int*，是因为这份实例里存的是整型数据。实际项目中如果换成学生信息、结构体记录，只需要把指针类型相应的结构体类型即可，其他逻辑基本不动。length和size分开记录，是为了让扩容判断有依据——判断length >= size就知道空间满了，该扩容了。

2.3 Max 与 Increment：预分配策略怎么选

宏定义Max 80表示初始化时分配 80 个int的空间，Increment 10表示每次扩容追加 10 个元素的空间。这个数值不是拍脑袋定的，而是针对“表长度变化不剧烈”的场景做的选择。

如果初始容量设置太小，比如 10，可能插入几十个元素就要连续扩容好几次，每次扩容都有数据搬运开销。如果设置太大，比如 1000，创建一个表就占掉 4KB 内存（1000 * 4 字节），在嵌入式或内存受限的环境下是浪费。增量 10 也是一个折中：每次扩容只多付出一小段内存搬运成本，又不至于频繁触发。

实际使用中，我会按数据规模来调整这两个值：如果知道表大概会存几百个元素，初始容量直接给到 200 或 300，增量给到 50；如果完全不确定，就保持小步快跑，增量给 10 或 20。这份实例把两个值独立成宏，改起来很方便，不需要动函数内部逻辑，这是设计上一个值得借鉴的地方。

3. 初始化与建表：malloc 判空、参数传引用、输入边界一次讲清

3.1 InitList 初始化：先分配内存，再判断是否成功

初始化顺序表的目的是分配一块连续内存，并把长度置为 0、容量设为初始值。实例里给出的 InitList 代码如下：

#include <stdio.h> #include <stdlib.h> #define Max 80 #define Increment 10 #define OK 1 #define ERROR 0 int InitList(SqList *L) { L->elem = (int *)malloc(Max * sizeof(int)); if (L->elem == NULL) { printf("内存分配失败\n"); return ERROR; } L->length = 0; L->size = Max; return OK; }

这段代码的逻辑顺序很重要：先调用 malloc 分配空间，紧接着判断返回值是否为 NULL，只有分配成功后才设置length和size。malloc 在内存不足时返回 NULL，如果不判空就直接往下写，程序会访问空指针，结果就是段错误。

关于返回值这里要解释一下，原实例里有几处直接写return;，但函数返回类型是int，这是编译不过的。正确做法是return ERROR;，调用方才能根据返回值判断初始化是否成功。另外，SqList &L这种写法是 C++ 的引用语法，在纯 C 环境下不支持，所以我在上面改成了SqList *L，实参传&L即可。

3.2 CreatList 建表：输入长度和数据时的自我保护

初始化之后就是建表操作，也就是从键盘读入元素。原实例里的 CreatList 在输入长度之前没有判断length是否超过size，如果输入一个超大的数，后面循环写入数组就会越界，这是隐患。我补上了检查：

int CreatList(SqList *L) { int i; if (L->elem == NULL) { return ERROR; // 尚未初始化 } printf("请输入表的长度: "); scanf("%d", &L->length); if (L->length < 0 || L->length > L->size) { printf("长度超出容量范围\n"); return ERROR; } printf("请输入%d个数: ", L->length); for (i = 0; i < L->length; i++) { scanf("%d", &L->elem[i]); } return OK; }

这里有几个容易忽略的点。第一，输入长度用%d，如果用户输入了负数，length会被赋成负数，循环直接跳过，表变成空表，但这种错误不应该被静默接受，所以加了范围判断。第二，scanf写入&L->elem[i]时，elem 是动态数组基址，下标从 0 开始，正好对应线性表的第 1 个元素。第三，CreatList依赖 InitList 先执行，否则elem还是野指针，所以函数开头要检查elem是否为 NULL，这是健壮性的一部分。

实际运行时，输入数据的个数必须和前面填的长度一致，这个约束在代码层面没法强制校验，只能靠使用者的习惯。我一般会在循环里顺便打印已接收的个数，方便对照。

3.3 GetElem 取值：为什么下标要减一

取值操作是根据位序 i 返回元素值，核心就是处理“位序从 1 开始、下标从 0 开始”的映射：

int GetElem(SqList *L, int i, int *e) { if (i < 1 || i > L->length) { return ERROR; } *e = L->elem[i - 1]; return OK; }

这里的边界判断i < 1 || i > L->length必须两个都写。只查上界不查下界，传入 i = 0 或负数时，会访问到elem[-1]甚至更前面的非法地址，轻则读到脏数据，重则直接把程序打崩。参数e用指针而不是返回值，是为了支持“返回一个值同时还要返回成功与否”的需求——只返回元素值的话，遇到非法位序就没法区分“返回了 0”和“出错”了。调用方式如下：

int e; if (GetElem(&L, 3, &e) == OK) { printf("第3个元素是: %d\n", e); }

4. 插入与删除：元素移动方向、扩容时机、边界条件全解析

4.1 插入操作：位置合法性是第一个坑

插入操作要做两件事：把插入位置及其后的元素右移一个位置，腾出空位，然后把新元素放进去。原实例里的插入判断是i<1||i>L.length，这里有个隐蔽的问题：在线性表末尾追加元素时，位置应该是L.length + 1，但上面的判断把这种情况给堵死了。修正后的代码如下：

int Insert(SqList *L, int i, int e) { int j; // 位置合法范围：1 到 length+1（允许在表尾追加） if (i < 1 || i > L->length + 1) { printf("插入位置不合法\n"); return ERROR; } // 空间已满，先扩容 if (L->length >= L->size) { printf("容量已满，触发扩容\n"); if (ExpandList(L) != OK) { return ERROR; } } // 右移元素：从最后一个元素开始往前搬，避免覆盖 for (j = L->length - 1; j >= i - 1; j--) { L->elem[j + 1] = L->elem[j]; } L->elem[i - 1] = e; L->length++; return OK; }

移动方向是插入操作最容易翻车的地方。如果写成从前往后搬，比如先用elem[i] = elem[i-1]，那么原来的elem[i]会在下一轮被自己的拷贝覆盖，整个表后半段数据全乱掉。必须从最后一个元素开始，逐个往后挪，才能保证每个值都安全“让位”。

L->length + 1作为上界还有一层意义：它天然兼容了“表空时插入第 1 个位置”和“表满时追加到末尾”两种情况。比如表是空的，length = 0，合法插入位置只有 1，正好对应i <= 1的判断。这段逻辑是顺序表里真正需要多写几遍才能顺手的地方。

4.2 动态扩容：realloc 的正确用法与判空时机

当length == size时，表已经存满，需要扩容。原实例里给的是“重新 malloc 一块更大的空间再手动搬数据”，思路是对的，但实现上直接写成了malloc(L.elem, ...)，这在 C 语言里是语法错误。更稳妥的做法是使用realloc，把扩容单独抽成一个函数：

int ExpandList(SqList *L) { int *new_elem; new_elem = (int *)realloc(L->elem, (L->size + Increment) * sizeof(int)); if (new_elem == NULL) { printf("扩容失败\n"); return ERROR; } L->elem = new_elem; L->size += Increment; return OK; }

使用 realloc 时有一个必须养成的习惯：不要直接写L->elem = realloc(L->elem, ...)。因为 realloc 失败时会返回 NULL，但原内存块依然有效，如果直接覆盖指针，原地址就丢了，既没法释放，也没法继续使用。正确做法是先存到临时变量里，判空成功后再赋值给L->elem，这就是上面代码里new_elem存在的意义。

扩容时size增加Increment，也就是 10 个元素的空间。这样做的依据是：如果只扩一个元素的空间，下次插入马上又要扩容，搬数据的花费会很高；一次性扩 10 个，摊还下来每次插入的成本就接近 O(1) 了。

以Max=80, Increment=10为例，表从空到插入 100 个元素，总共触发 2 次扩容，每次搬运不超过 90 个元素，开销完全可以接受。

4.3 删除操作：前移从前往后，别覆盖了没处理的数据

删除位置 i 的元素，需要把 i 之后的元素整体前移一位，然后length--。前移的方向和插入正好相反，必须从前往后搬：

int ListDelete(SqList *L, int i, int *e) { int k; if (L->length == 0) { return ERROR; // 空表不能删 } if (i < 1 || i > L->length) { return ERROR; } *e = L->elem[i - 1]; // 前移元素：从被删位置的下一个开始，逐个往前盖 for (k = i; k < L->length; k++) { L->elem[k - 1] = L->elem[k]; } L->length--; return OK; }

为什么前移不能从后往前？因为从后往前搬时，后面的元素会覆盖掉前面还没搬的元素，数据就坏了。删除这里用从前往后，每一步都是“用下一个覆盖当前”，被覆盖的位置已经取走保存到*e了，所以是安全的。

删除后length减一，但size不变，也就是说容量没有回缩。这在频繁插入删除交替的场景下会造成内存浪费，比如一个表最多存过 1000 个元素，后来删到只剩 10 个，但它仍占着 4000 字节的空间。常见的做法是：当length < size / 4时缩容一次，避免反复横跳。这也是顺序表相对链表的一个明确短板，链表删除节点即释放，顺序表做不到。

5. C语言线性表顺序存储避坑：五个最容易翻车的现场

5.1 传参写成 C++ 引用，纯 C 环境下编译失败

现象：代码里写int InitList(SqList &L)，在.c文件里编译直接报错，说&符号不能这么用。

原因：SqList &L是 C++ 的引用语法，C 语言没有引用类型，只有指针。网上不少代码是在 C++ 编译器里跑的，拿过来直接在 C 环境用就翻车。

解决：统一改成指针传参，形参写SqList *L，函数内用L->访问成员，调用时传&L。这份实例里的所有函数都应该按这个风格写，避免 C/C++ 混用。

5.2 realloc 返回值直接覆盖原指针，失败后数据全丢

现象：写完扩容函数，插入第 81 个元素时程序崩溃，或者更隐蔽——扩容失败后，原表数据还能用，但指针已经变成 NULL 了。

原因：直接写L->elem = (int *)realloc(L->elem, new_size)，如果 realloc 失败返回 NULL，赋值后L->elem就变成了 NULL，原来那块内存既没有释放，也失去了引用，成了内存泄漏加数据丢失双重事故。

解决：先用临时指针接住 realloc 的返回值，判空之后再赋给L->elem。我在第 4 章的ExpandList里就是这样处理的，这也是 C 语言内存管理的标准姿势。

5.3 插入位置的上界漏掉 length + 1

现象：想在表尾追加一个元素，程序提示“插入位置不合法”，死活插不进去。

原因：插入判断写成了i < 1 || i > L->length，漏掉了i == L->length + 1这种合法情况。在表尾追加是顺序表最常见的操作之一，这个边界漏掉会让表的增长能力直接废掉。

解决：上界改为L->length + 1，同时意识到这个上界也是循环移动次数和下标计算的依据。在写插入函数时，先把位置合法范围写在注释里，再写判断条件，能少踩一半的坑。

5.4 插入右移循环方向写反，数据全被覆盖

现象：在第 2 和第 3 个元素之间插入新值后，第 3 个元素之后的数据全变成了同一个值。

原因：右移时从插入位置开始往后搬，比如先执行elem[2] = elem[1]、elem[3] = elem[2]，每一步都在覆盖还没搬走的原始数据。

解决：右移必须从最后一个元素开始往前搬，即j = L->length - 1递减到i - 1。删除的前移则反过来，必须从前往后。我常用一句口诀记：插入倒着搬，删除顺着搬。每次写完再对照口诀走读一遍循环边界，基本就不会再犯。

5.5 初始化之后没有检查返回状态，空指针直接往里写

现象：程序一运行就在 InitList 之后的某个赋值语句崩溃，用调试器看，L.elem是 NULL。

原因：malloc 失败返回 NULL，但代码没有判断，直接执行L->length = 0; L->size = Max;，这些赋值还好，问题是后面的插入操作拿 NULL 当数组用，必崩。

解决：每次调用 InitList 后都要检查返回值，失败就立即退出或者提示用户。同理，CreatList 开头也应该判断elem是否为空。内存分配失败在桌面环境少见，但在嵌入式或紧张的内存环境下很常见，不判断等于埋雷。从那以后我写的每个 Init 函数都会强制过一遍“分配—判空—赋值”这三步，顺序一步都不能省。

6. 验证顺序表：用断言、内存检查和性能走读把代码跑稳

6.1 最小回归测试：用 assert 覆盖关键边界

写完插入删除，别急着去写业务逻辑，先写一个小测试函数，把边界情况跑一遍：

#include <assert.h> void TestSqList() { SqList L; int e; assert(InitList(&L) == OK); // 空表时插入到第 1 个位置 assert(Insert(&L, 1, 10) == OK); assert(Insert(&L, 2, 20) == OK); // 在中间插入 assert(Insert(&L, 2, 15) == OK); // 在表尾追加 assert(Insert(&L, L.length + 1, 30) == OK); // 取值验证 assert(GetElem(&L, 2, &e) == OK && e == 15); assert(GetElem(&L, 4, &e) == OK && e == 30); // 删除中间元素 assert(ListDelete(&L, 2, &e) == OK && e == 15); assert(L.length == 3); // 越界操作必须返回错误 assert(ListDelete(&L, 5, &e) == ERROR); assert(GetElem(&L, 0, &e) == ERROR); printf("全部测试通过\n"); free(L.elem); }

这段测试覆盖了空表插入、中间插入、表尾追加、越界取值、越界删除五个典型场景。assert 的好处是一旦条件不满足，程序立刻停在出错那一行，定位非常快。注意测试结束要free(L.elem)，释放由 malloc 分配的内存，否则 valgrind 会报泄漏。

编译时有个细节：release 版本如果定义了NDEBUG，assert 会被整体剔除。所以这个测试函数适合在调试阶段用-g选项编译，发布前再决定要不要保留。

6.2 编译检查与内存泄漏检查

调试编译命令和内存检查命令如下：

gcc -Wall -Wextra -g sqlist.c -o sqlist valgrind --leak-check=full ./sqlist

-Wall -Wextra会把隐式类型转换、未使用变量、可能有问题的比较都警告出来。把警告清零比通过断言更重要——C 语言的警告里藏着一半的未定义行为。valgrind 是一个内存检测工具，--leak-check=full会在程序退出时报告每一处泄漏。因为顺序表用了 malloc、realloc、free，这是最能暴露问题的检测点。

6.3 性能走读表：顺序表在什么场景下值得用

操作	时间复杂度	说明
按下标取值	O(1)	数组直接寻址，顺序表的最大优势
在表尾插入	O(1) 摊还	不需要移动元素，偶尔触发扩容
在表中插入	O(n)	平均移动 n/2 个元素
删除元素	O(n)	平均移动 (n-1)/2 个元素
扩容	O(n)	每次扩容搬一次数据，但摊还成本低