最近有个学弟私信我说他数据结构实验卡在顺序表上了。老师给的题目看起来不难——初始化、插入、删除、求并集但一上机就报错不是越界就是乱码搞了一下午心态爆炸。我跟他说顺序表这玩意儿教材上写得云里雾里但本质上就是一个数组加一个长度变量的事。你把这两个东西的底层逻辑搞透了剩下全是套路。这篇文章我就按自己实际写代码、改代码的经验把顺序表从头到尾掰开揉碎讲一遍。内容包括顺序表底层的内存模型、初始化和输入操作的完整实现、插入删除时的数据搬移逻辑、动态扩容方案以及热搜里提到的用顺序表求解一般集合的并集的完整C代码。不管你是刚学数据结构的大一新生还是准备笔试面试的求职党这篇都能直接当参考抄。1. 顺序表的内存模型连续空间到底意味着什么先别急着敲代码把最底层的模型搞清楚。顺序表全称顺序存储的线性表说人话就是用一段地址连续的内存空间来存放数据元素。它的底层载体就是数组只不过在数组外面包了一层结构体多记录了一个当前长度。1.1 为什么顺序表能O(1)随机访问数组之所以能随机访问靠的是内存地址的连续性。假设数组的首地址是base每个元素占sizeof(ElemType)个字节那么第i个元素的地址就是addr(i) base i * sizeof(ElemType)这是个纯算术运算一次乘法和一次加法CPU几条指令就能算完。所以不管你要访问第0个还是第99999个元素耗时都一样时间复杂度是O(1)。这是顺序表最核心的优势也是后面所有讨论的出发点。1.2 逻辑上相邻物理上也相邻线性表要求元素之间有前驱、后继的逻辑关系。链表用指针来维系这种关系顺序表则直接靠物理位置——第i个元素旁边就是第i1个元素谁也不多占一个字节。这种逻辑相邻物理相邻的特性带来一个直观的后果插入和删除都要牺牲一部分元素的物理位置也就是整体搬移。我用一个生活例子帮你记电影院的连排座位。你买票时先到的都坐前排座位紧挨着。这时候新来一个人想插在第3个位置那第3个座位往后的所有人都得往右挪一个座。这就是顺序表插入的代价。如果座位之间留了空位且彼此通过绳线标记先后顺序——那就是链表的方式插人只需要解绳重系旁人不用动。1.3 顺序表 数组 长度变量记住这个公式顺序表的所有代码都不会跑偏。常规定义长这样#define MaxSize 100 typedef int ElemType; typedef struct { ElemType data[MaxSize]; // 数组存元素 int length; // 当前元素个数 } SqList;length就是当前表里实际存了多少个元素区分于MaxSize这个总容量。这是新手最容易搞混的两个概念length MaxSize满的时候length MaxSize再插就报错。后面所有操作的边界判断都是围绕这俩变量展开的。2. 初始化与输入实验题顺序表 - 10. 输入的完整落地方案热搜里有一条6-8 顺序表 - 10. 输入这类题目的习惯做法就是第一行输入元素个数n第二行输入n个数据元素。实操的时候很多同学栽在输入格式和异常处理上代码主逻辑反而没写对。2.1 标准初始化代码void InitList(SqList *L) { L-length 0; // 空表长度为0 }就这么简单。因为用的是静态数组空间编译期就分配好了初始化只需要把length归零。如果后续用到动态分配就要加malloc这个在第4节专门讲。2.2 从键盘向顺序表录入数据按照题目标准的输入格式完整代码如下void CreateList(SqList *L) { int n, i; printf(请输入元素个数); scanf(%d, n); if (n 0 || n MaxSize) { printf(输入元素个数不合法\n); return; } printf(请输入%d个元素, n); for (i 0; i n; i) { scanf(%d, L-data[i]); } L-length n; }这里有个非常容易踩的坑scanf输入两个数据时中间用什么分隔空格、Tab、换行都可以但你在控制台输完n之后按的那个回车不会被scanf(%d)吃掉。如果你紧接着用scanf(%c)去读字符就出问题了但读数字没影响因为%d会自动跳过空白符。2.3 输入越界的防御性处理我在批改同学代码时见过最典型的错误是用户输入n 120而MaxSize只有100然后for循环照跑不误直接把数据写进数组后面的内存区域。这在本地可能不报错但一旦跑到在线评测系统轻则数组越界报错重则悄悄覆盖别的变量导致结果莫名其妙。提示凡是涉及用户输入的代码第一件事就是做合法性校验。这不是多此一举是工程习惯。哪怕题目没要求你也得写因为线上评测的测试数据永远比你想象的刁钻。3. 插入与删除的搬家逻辑下标推算和边界处理插入和删除是顺序表的核心操作也是笔试大题的高频考点。很多同学把代码背下来了但换一个变体题目就懵。本质原因是没有推演清楚数据搬移的下标范围。3.1 插入操作从最后一个元素开始往后搬插入到第i个位置按教材习惯i从1开始计数对应数组下标i-1需要把第i个到第length-1个元素全部后移一位空出位置给新元素。代码和推演如下bool ListInsert(SqList *L, int i, ElemType e) { if (i 1 || i L-length 1) // 位置合法性 return false; if (L-length MaxSize) // 表满判断 return false; int j; for (j L-length; j i; j--) { L-data[j] L-data[j - 1]; // 从后往前搬 } L-data[i - 1] e; L-length; return true; }搬移的起始下标为什么是L-length而不是L-length - 1因为原来最后一个元素在length-1位置它要挪到length位置所以循环从length开始写。这一步想明白了整个插入就通了。举例表里有{10, 20, 30}length3要在第2个位置插25。循环执行j3data[3] data[2] 30j2data[2] data[1] 20最终数组变成{10, 20, 20, 30}然后data[1] 25得到{10, 25, 20, 30}。3.2 删除操作从前往后搬覆盖掉目标元素删除第i个元素就是把第i个后面的所有元素各前移一位。bool ListDelete(SqList *L, int i, ElemType *e) { if (i 1 || i L-length) return false; *e L-data[i - 1]; // 先取被删元素 for (int j i - 1; j L-length - 1; j) { L-data[j] L-data[j 1]; // 从前往后搬 } L-length--; return true; }3.3 时间复杂度平均搬多少元素插入到位置i需要搬动n - i 1个元素。插入位置有n1种可能表头到表尾后平均搬动次数是平均移动次数 1/(n1) * Σ(i1到n1) (n - i 1) n/2删除同理为(n-1)/2。所以顺序表插入删除的时间复杂度均为O(n)但常数系数约等于0.5n。这也是为什么顺序表适合读写多、增删少的场景。4. 动态扩容从固定数组到自动增长的进阶路线静态数组的硬伤是容量写死。MaxSize100数据一多就爆。在真实工程里没人这么干笔试面试也会追问如何扩容所以要掌握动态实现。4.1 动态顺序表的结构体设计#define InitSize 10 // 初始容量 typedef struct { ElemType *data; // 指针指向堆区内存 int MaxSize; // 当前最大容量 int length; // 当前元素个数 } SeqList;和静态版本的区别就是data从数组变成指针多了MaxSize。初始化用malloc申请堆内存void InitList(SeqList *L) { L-data (ElemType *)malloc(InitSize * sizeof(ElemType)); L-MaxSize InitSize; L-length 0; }注意:malloc之后要检查是否返回NULL。内存申请失败是可能的尤其当InitSize很大时。不检查直接往下写就是空指针解引用程序直接崩溃。4.2 扩容的标准姿势realloc或malloc拷贝插入时发现length MaxSize就要扩容。两种做法方式一reallocL-data (ElemType *)realloc(L-data, L-MaxSize * 2 * sizeof(ElemType)); L-MaxSize * 2;方式二手动搬移ElemType *p (ElemType *)malloc(L-MaxSize * 2 * sizeof(ElemType)); memcpy(p, L-data, L-MaxSize * sizeof(ElemType)); free(L-data); L-data p; L-MaxSize * 2;realloc更简洁但你需要知道它可能返回一个新地址原地址被系统收回重分配也可能原地扩容。所以必须用返回值接住别直接L-data realloc(...)后又拿旧指针操作。扩容的粒度一般是原来的2倍为什么不是1或10因为扩容要搬移所有数据代价是O(n)。用倍乘策略均摊到每次插入的成本是O(1)这个分析叫摊还分析。简单记扩容越频繁整体插入性能越差所以每次多扩点用空间换时间。4.3 别忘了销毁动态分配了堆内存程序结束前要释放否则内存泄漏void DestroyList(SeqList *L) { free(L-data); L-data NULL; L-length 0; L-MaxSize 0; }笔试填空里有不少题专门考这个配套意识malloc对应freenew对应delete。漏了就是扣分点。5. 求解一般集合的并集顺序表综合应用的完整C代码热搜里有一条求解一般集合的并集问题的用顺序表实现完整c代码详解这是顺序表很经典的综合应用题。考核点不只是插入删除还有查找和去重逻辑。5.1 问题定义与算法思路题目通常表述为有两个集合A和B求并集C要求结果不含重复元素。核心思路分三步先把A的所有元素复制进C。遍历B的每个元素用查找函数判断它是否已在C中。若不在就插入C的末尾。所以这道题实际上是查找 插入的组合应用也是用顺序表解集合问题的标准模板。5.2 完整C代码与逐段注释#include stdio.h #include stdlib.h #define MaxSize 100 typedef struct { int data[MaxSize]; int length; } SqList; // 初始化 void InitList(SqList *L) { L-length 0; } // 向表尾追加一个元素 bool Append(SqList *L, int e) { if (L-length MaxSize) return false; L-data[L-length] e; L-length; return true; } // 在顺序表中查找元素e返回下标找不到返回-1 int LocateElem(SqList *L, int e) { for (int i 0; i L-length; i) { if (L-data[i] e) return i; } return -1; } // 求并集将B中不在A里的元素追加到A末尾 void Union(SqList *A, SqList *B) { for (int i 0; i B-length; i) { int e B-data[i]; if (LocateElem(A, e) -1) { // A中不存在该元素 Append(A, e); // 插入A的末尾 } } } // 打印线性表 void PrintList(SqList *L) { printf(当前表); for (int i 0; i L-length; i) { printf(%d , L-data[i]); } printf(\n); } int main() { SqList A, B; InitList(A); InitList(B); // 给A输入 int na; printf(请输入集合A的元素个数); scanf(%d, na); printf(请输入A的元素); for (int i 0; i na; i) { int x; scanf(%d, x); Append(A, x); } // 给B输入 int nb; printf(请输入集合B的元素个数); scanf(%d, nb); printf(请输入B的元素); for (int i 0; i nb; i) { int x; scanf(%d, x); Append(B, x); } // 求并集并输出 Union(A, B); PrintList(A); return 0; }这段代码可以直接抄进你的实验报告但建议你至少手敲一遍。Union函数的核心就三行逻辑能默写出来说明入门的增查插删都过关了。5.3 复杂度分析与优化方向上面的解法时间复杂度是O(n*m)n是A的长度m是B的长度。因为B的每个元素都要在A里做一次线性查找。三种优化方向按适用场景排序方案思路时间复杂度适用条件双指针法两个表先排序有序后同时扫描去重O(nlogn mlogm n m)A、B允许改变顺序哈希表法用哈希集合记录A中已有元素O(n m)笔试时可用C STL纯C手写较繁琐当前线性查找不改变原表结构O(n*m)数据量小题目要求顺序表实现笔试时如果题目明说不能改变原集合元素顺序那就老老实实用线性查找。如果没说优先提双指针方案能体现你复杂度意识。6. 顺序表与链表的选型对比面试和笔试的常考点学顺序表时一定会被问什么时候用顺序表什么时候用链表这几乎是笔试简答题和面试必考题。我按自己的理解给一个清晰答案。6.1 核心对比表维度顺序表链表存储密度高无额外指针开销低每节点多一个next指针随机访问O(1)O(n)必须从头遍历插入删除平均O(n)主要花在搬移已知位置时O(1)只需改指针缓存友好性高连续内存有利于Cache命中低节点分散Cache命中率差扩容方式搬移全部数据天然动态按需申请节点空间预申请需预知规模不需要6.2 选型的实战判断我个人的选择逻辑是这样的场景1频繁按下标访问。比如实现一个排行榜按名次查分数秒选顺序表。链表从头数第500名是什么感觉你自己体会。场景2频繁在中间插入删除。比如维护一个实时任务队列随时插任务、抽走任务而且经常在中间操作那选链表或者用平衡树这类进阶结构。顺序表在这里就是灾难每插一个元素后面几万条数据全要移位。场景3数据量不可预估且变化剧烈。优先链表或者动态扩容的顺序表。注意动态扩容的顺序表虽然能扛但扩容瞬间有O(n)的卡顿极端场景下可能无法接受。场景4数据量明确且稳定以遍历为主。顺序表。原因就是那个容易被人忽略的缓存友好性。顺序表在内存里是连续一段CPU读数据时自动把相邻内存也拉进Cache遍历一遍几乎全部命中。链表节点东一个西一个每次访问都可能缺页或者Cache miss实际跑起来慢一个数量级都不奇怪。6.3 为什么很多教材默认用顺序表教材上线性表这一章往往先讲顺序表不是因为它更常用而是因为顺序表能让学生快速理解线性结构这个抽象概念——用最朴实的内存连续性实现逻辑相邻性。链表引入了指针和节点的间接层对初学者是额外负担。但实话说工程里链表的出场率比教材比例低很多。因为大多数场景数据量可控、靠索引访问为主顺序表的综合性能更稳定。你要是参加面试一定要能说出这层原因别只会背课本结论。7. 调试经验与高频扣分点写给正在写实验报告的你最后这部分是纯经验输出。我在帮人改代码和自己刷题过程中总结的顺序表最容易出错的7个地方以及调试建议。7.1 高频Bug清单扣分点1下标从1开始还是从0开始混为一谈。教材的插入位置i通常从1计数数组下标从0计数这两个中间隔了-1。我见过有人插入后忘记data[i-1] e写成data[i] e结果元素全错位。建议在函数头部注释里写清楚本函数i是逻辑位置从1开始。扣分点2忘记判满或判空。插入不判满直接越界写入删除不判空直接操作无效下标。这两种错误在OJ上基本必挖。无符号整数的坑也要注意i - 1当i0时会变成巨大的正数所以判断i 1必须放在i-1生效之前。扣分点3删除漏了修改length。插入了length删除却忘了length--。然后打印时多出一个垃圾值。这是最隐性也最丢分的错误看起来结果差不多点开一看最后一位是脏数据。7.2 我的调试三板斧第一写一个PrintList输出所有元素和length。我调试顺序表永远先打印这两样确认表状态符合预期。第二边界用例必测。空表插入、满表插入、表头插入、表尾插入、表尾删除、删除唯一个元素。不要管题目有没有要求自己写代码就得按这个强度测。大多数隐藏Bug都是边界条件没处理。第三用断言或者if日志打印关键路径。比如插入成功后printf一下insert ok, i%d, e%d, length%d。代码跑完看日志哪里执行到、哪里没有一目了然。7.3 在线评测的输入陷阱有些OJ题目的输入格式描述是输入若干个整数以0结束或者第一行T表示T组测试数据每组先输入个数n。这就意味着你的CreateList得写成可循环调用的模式每次读入T组然后分别建表。别把只处理一组写死在main里这是很多人样例通过、提交不过的原因。7.4 Java版思路简述热搜里有java顺序表代码这个词如果面试需要手写Java版本思路完全一致但要注意Java里的数组不能动态扩容扩容用Arrays.copyOfpublic class SeqList { private int[] data; private int length; public void grow() { data Arrays.copyOf(data, data.length * 2); } }本质没变依然是数组长度。别被语言换皮唬住。结尾写到这里顺序表的核心内容基本覆盖全了。我在这个专题里刻意把内存模型放在第一位是因为我见过太多同学能把插入删除代码背得滚瓜烂熟但问他为什么删除要前移而从后遍历插入要后移而从末尾开始就卡壳。真理解了数组地址连续这一件事顺序表的全部操作你都能自己推出来根本不用背。最后再分享一个排查问题的小技巧当你觉得代码逻辑完全正确却死活跑不对时把length和每个关键中间变量的值打印到屏幕上一步步对着推。顺序表没有复杂的指针关系Bug一般出在边界条件和下标转换上打印输出很快就能定位。这个专题后续还会更新查找、排序相关的内容如果这篇对你有帮助加个收藏多敲两遍数据结构的底子就是这么一点点磨出来的。