1. 顺序表应用的整体思路顺序表这块基础内容前面两篇笔记把定义、初始化、增删查改都过了一遍。但学数据结构最忌讳的就是只背接口、不碰场景——你背完了插入删除的代码遇到真实问题照样不知道怎么下手。这篇笔记就是集中整理顺序表最常见的几个应用场景从“能用”到“会用”的过程。先交代一下我的背景我是计算机科班出身现在做后端开发数据结构这块从考研复习到工作面试顺序表是最基础也最容易被忽略的一块。很多人觉得顺序表简单就不太重视它在实际问题中的应用结果一到期末考试或者面试问答遇到“什么时候用顺序表”“顺序表的优缺点怎么分析”这类问题就开始卡壳。这篇笔记正好帮你把这些点都串起来。先聊一个核心观念顺序表适合什么场景一句话解释顺序表适合“存得整、查得多、改得少”的场景。为什么因为顺序表的底层是一块连续内存数组本身的随机访问特性让它可以在 O(1) 时间拿到任意位置的元素但代价是为了维持“连续”这个性质插入和删除往往需要搬动大量元素平均时间复杂度 O(n)。所以如果你的操作是以“查”和“改”为主插入删除不频繁顺序表就是最合适的选择反过来如果插入删除特别频繁链表会更合适。这个判断不只是理论在实际开发里也经常用到。比如你要做一个用户积分排行榜数据量不大、经常要查某个名次的分数、偶尔更新一下分数这种情况下用顺序表或数组比用链表舒服得多再比如你要做一个文本编辑器的撤销栈、或者浏览器的后退历史这些本身就是栈结构底层用顺序表实现栈也是最自然的选择。2. 顺序表实现集合运算集合运算可以说是顺序表应用里最经典的教学案例。很多学校的实验课都会布置这道题给定两个集合 A 和 B用顺序表存储求它们的并集、交集、差集。而网上搜“求解一般集合的并集问题的用顺序表实现完整c代码详解”搜出来大概率就是这个题目。2.1 场景描述与算法分析集合有三个基本特征确定性、互异性、无序性。用顺序表存集合的时候互异性元素不重复是需要自己维护的因为顺序表本身并没有“去重”的机制。具体到各个运算并集A ∪ B就是把 B 中不在 A 里的元素追加到 A 后面。核心操作是“查重后追加”。交集A ∩ B就是找出同时出现在 A 和 B 中的元素。差集A − B就是找出在 A 里但不在 B 里的元素。这几种运算本质上都绕不开一个核心动作——判断一个元素是否在一个集合中。在顺序表里做判断只能遍历时间复杂度 O(n)。假设两个集合长度分别为 m 和 n对 A 中每个元素都去 B 里查一遍最坏情况就是 O(m×n)。2.2 完整C代码实现我直接给一份完整可运行的 C 语言代码。这份代码我当年写实验报告时反复调过现在整理出来注释写得比较全因为实验课老师是要看注释的。#include stdio.h #include stdlib.h #define MAXSIZE 100 // 顺序表最大容量 typedef struct { int data[MAXSIZE]; int length; // 当前长度 } SeqList; // 初始化长度为0 void InitList(SeqList *L) { L-length 0; } // 在末尾追加元素自动去重返回1成功0表长溢出-1元素已存在 int Append(SeqList *L, int e) { // 去重检查 for (int i 0; i L-length; i) { if (L-data[i] e) { return -1; } } if (L-length MAXSIZE) { return 0; } L-data[L-length] e; return 1; } // 判断元素 e 是否在顺序表 L 中 int LocateElem(SeqList L, int e) { for (int i 0; i L.length; i) { if (L.data[i] e) { return i; // 返回下标 } } return -1; // 不存在 } // 并集A A ∪ B把B中A没有的元素追加到A末尾 void Union(SeqList *A, SeqList B) { for (int i 0; i B.length; i) { Append(A, B.data[i]); } } // 交集把A中也在B里的元素放入C void Intersection(SeqList A, SeqList B, SeqList *C) { InitList(C); for (int i 0; i A.length; i) { if (LocateElem(B, A.data[i]) ! -1) { Append(C, A.data[i]); } } } // 差集把A中不在B里的元素放入C void Difference(SeqList A, SeqList B, SeqList *C) { InitList(C); for (int i 0; i A.length; i) { if (LocateElem(B, A.data[i]) -1) { Append(C, A.data[i]); } } } void PrintList(SeqList L) { printf([); for (int i 0; i L.length; i) { if (i 0) printf(, ); printf(%d, L.data[i]); } printf(]\n); } int main() { SeqList A, B, C; InitList(A); InitList(B); // 构造集合 A {1, 3, 5, 7, 9} int a[] {1, 3, 5, 7, 9}; for (int i 0; i 5; i) Append(A, a[i]); // 构造集合 B {2, 3, 4, 7, 8} int b[] {2, 3, 4, 7, 8}; for (int i 0; i 5; i) Append(B, b[i]); printf(集合 A ); PrintList(A); printf(集合 B ); PrintList(B); // 并集直接修改A Union(A, B); printf(A ∪ B ); PrintList(A); // 交集和差集结果存入C Intersection(A, B, C); printf(A ∩ B ); PrintList(C); Difference(A, B, C); printf(A − B ); PrintList(C); return 0; }运行结果集合 A [1, 3, 5, 7, 9] 集合 B [2, 3, 4, 7, 8] A ∪ B [1, 3, 5, 7, 9, 2, 4, 8] A ∩ B [3, 7] A − B [1, 5, 9]2.3 容易翻车的3个细节这块代码看起来不难但实验报告里扣分点基本都藏在细节里。第一并集是原地修改还是另建新表我的 Union 函数是直接原地修改 A这在语义上没问题A A ∪ B但你得意识到这会改变原集合 A 的内容。如果你后面还要用原来的 A就得先拷贝一份或者像 Intersection 和 Difference 那样另建一张表存结果。实验报告里最好在注释里说明你选的是哪种策略。第二去重检查不能省。集合要求互异性如果你直接把 B 的元素往 A 后面怼遇到 A 和 B 有重复元素的时候结果里就会出重复值那就不叫集合了。很多同学第一次写并集代码栽就栽在“忘了查重”。第三Append 的返回值处理。我的 Append 区分了“表满”“元素已存在”“插入成功”三种情况这在函数设计上是个好习惯。你的主函数可以根据返回值决定要不要报错而不是让函数默默失败。我见过有人把 Append 写成 void 函数表满了懒得管结果数据悄悄丢了调试的时候要多痛苦有多痛苦。提示做交集运算的时候A ∩ B 的结果一定不会比短的那张表更长所以初始化的 C 表容量理论上只需要 min(A.len, B.len)写成 MAXSIZE 纯粹是图省事。想秀操作的话可以先用 malloc 按实际需要分配这也顺便把动态内存的知识点复习了。3. 顺序表应用场景之二有序表归并再来看一个特别常见的应用场景——有序表的归并。两个已经排好序的顺序表合并成一个仍然有序的新顺序表。这不仅是数据结构课的必考题也是归并排序的核心操作面试里考归并排序时本质就是在考这个。3.1 为什么用顺序表做归并很合适归并操作的基本思路是双指针两个指针分别指向两个有序表的开头谁小就先把谁放进新表然后对应指针后移。最后把剩余元素全部搬进新表。这个操作的性质是两个表的元素都是“从头到尾只走一遍”不涉及随机插入只需要在末尾追加所以完全避开了顺序表插入操作 O(n) 的短板。时间复杂度稳定在 O(mn)空间上需要一个额外的表存结果O(mn) 也躲不掉。3.2 归并代码实现// 归并两个有序顺序表 A 和 B结果存入 C void MergeList(SeqList A, SeqList B, SeqList *C) { InitList(C); int i 0, j 0; while (i A.length j B.length) { if (A.data[i] B.data[j]) { C-data[C-length] A.data[i]; } else { C-data[C-length] B.data[j]; } } // 处理剩余元素 while (i A.length) { C-data[C-length] A.data[i]; } while (j B.length) { C-data[C-length] B.data[j]; } }注意一个细节归并时用 而不是 这个选择决定了当 A 和 B 里有相等元素时谁排在前面。如果题目要求相同元素保持原顺序稳定排序那 A 的排在 B 的前面才能保证归并后的顺序稳定。408 统考或者面试里问你“归并排序稳不稳定”答案就是“看归并时相等元素怎么处理”用 就是稳定的。实操心得如果不想申请额外空间可以从后往前归并把结果直接覆盖到较长的那个表里。具体做法是先给长表扩容然后从末尾开始比较、从后往前放元素这样就不会覆盖还没处理的数据。这个技巧在“原地归并”的题目里经常用到思路和顺序表插入元素时“从后往前搬”是一个道理。4. 顺序表应用场景之三约瑟夫环约瑟夫环Josephus Circle是顺序表应用里一道绕不开的经典题。问题描述是这样的n 个人围成一圈从第一个人开始报数每次报到 m 的人出局然后从下一个人重新开始报数问最后剩下的是几号。这道题教学价值在于它模拟的是一个动态删除的过程而顺序表做删除操作时恰好能让你直观感受到“元素搬移”的开销——这是理解顺序表和链表差异最好的方式之一。4.1 用顺序表模拟约瑟夫环思路不复杂用顺序表存这 n 个人用一个变量 cur 记录当前报数位置。每次找到要出局的人的下标把这个人移除后面的元素整体前移然后从移除位置继续报数。核心代码如下#include stdio.h #include stdlib.h #define MAXSIZE 100 typedef struct { int data[MAXSIZE]; int length; } SeqList; void InitList(SeqList *L) { L-length 0; } // 约瑟夫环n个人报数到m出局返回最后剩下的人 int Josephus(int n, int m) { SeqList L; InitList(L); for (int i 1; i n; i) { L.data[L.length] i; // 编号从1到n } int cur 0; // 当前报数起点下标 // 循环删除直到只剩一个人 while (L.length 1) { // 报数报到 m 的人的下标当前起点往后数 m-1 个人 int idx (cur m - 1) % L.length; printf(出局: %d\n, L.data[idx]); // 删除下标为idx的元素后面的往前搬 for (int i idx; i L.length - 1; i) { L.data[i] L.data[i 1]; } L.length--; // 下一次报数从 idx 位置开始因为 idx 处现在是原来 idx1 的元素 cur idx; } return L.data[0]; } int main() { int last Josephus(8, 3); printf(最后留下: %d\n, last); return 0; }运行结果出局: 3 出局: 6 出局: 1 出局: 5 出局: 2 出局: 8 出局: 4 最后留下: 74.2 这份代码的坑与优化空间约瑟夫环用顺序表实现最大的坑就是下标计算。很多人上来就是cur m没有减 1结果总是偏差一位或者直接数组越界。我的建议是拿小数据手动推一遍n5, m2从 0 下标开始第一次出局的人应该是 2 号下标 1而(0 2 - 1) % 5 1刚好对上。从复杂度角度看这个算法每次删除都是 O(n)一共要删 n-1 次所以总复杂度 O(n²)。如果把 n 放大到 10 万这个顺序表版本的约瑟夫环就明显变慢了。这也解释了为什么这个题如果用链表做删除是 O(1)总复杂度能降到 O(n)。但你也不用觉得顺序表版本就白学了。恰恰相反正是因为写过这个 O(n²) 版本你才能直观体会到为什么链表的删除性能在循环删除场景下如此重要。学数据结构很多时候不是要学会“用最好的方案”而是通过不同方案的对比把“为什么好”理解透。实操心得约瑟夫环还有一个 O(n) 的递推公式解法f(1)0; f(i)(f(i-1)m)%i。笔试的时候能用公式就写公式面试官让你讲的时候再把模拟版本说出来。我的经验是两种都要会因为面试官很可能问“这个模拟版本如果数据量很大怎么办”。5. 顺序表应用场景之四多项式的存储多项式运算是另一个体现顺序表价值的场景。你要存储一个多项式比如 3x⁵ 2x³ x 5有两种方案第一种是只存系数数组下标就是指数第二种是存“系数-指数”对的列表。在初阶阶段我们通常只讨论第一种。5.1 系数数组方案用一个数组存放系数下标是幂次对应位置的值是系数那么上面的多项式就可以表示成{5, 1, 0, 2, 0, 3} // 下标0对应常数项下标1对应x下标2对应x²...这里 length6表示最高是 5 次。多项式加法就是把两个数组对应下标相加多项式乘法就是两层循环结果数组下标 ij 累加 a[i]*b[j]。这种方式的好处是直观加法复杂度 O(n)乘法复杂度 O(n²)都能直接套用顺序表的结构。缺点是如果多项式非常稀疏比如只有 x¹⁰⁰ 一项数组就得开 101 个位置浪费严重。遇到稀疏多项式就得换“系数-指数”对方案那本质上是顺序表存储结构体的问题属于进阶阶段的内容了。我考研复习到这里的时候一度觉得多项式存储有点无聊后来做算法题遇到大整数乘法突然意识到所谓“乘法的竖式”本质上就是多项式乘法的特例数组下标就是位权乘法时下标相加的规律完全一致。所以顺序表存储多项式不只是一个孤立的知识点它能为后面学字符串、大数运算、卷积等一堆内容打底。5.2 多项式加法的代码骨架// C[i] A[i] B[i]取两者较大长度 void PolyAdd(int A[], int lenA, int B[], int lenB, int C[], int *lenC) { *lenC lenA lenB ? lenA : lenB; for (int i 0; i *lenC; i) { int a i lenA ? A[i] : 0; int b i lenB ? B[i] : 0; C[i] a b; } }注意这里处理了长度不一致的情况短数组越界的地方按 0 算。这是多项式运算里容易犯的错——两个多项式次数不同循环次数如果按短的来高次项的系数就丢了。6. 顺序表实现栈与队列看图说话的应用这个应用看起来平凡但其实是顺序表最日常的使用方式。“用顺序表实现栈”说白了就是只在一个端点进行插入和删除的受限顺序表“用顺序表实现循环队列”就是加上头尾指针的顺序表。这道题在期末考试和考研初试里几乎必考。6.1 顺序栈顺序栈的思路极简一个数组加一个 top 指针入栈就是data[top] e出栈就是return data[--top]。由于栈的操作只发生在栈顶完全避开了顺序表插入删除的 O(n) 短板。所以顺序栈和链栈的区别主要在“空间是否连续、是否需要额外指针字段”上时间复杂度几乎一样。6.2 循环队列的坑循环队列是用顺序表实现“循环利用空间”的典型代表。核心公式是两个取模操作队尾入队: rear (rear 1) % MAXSIZE; 队头出队: front (front 1) % MAXSIZE; 判空: front rear 判满: (rear 1) % MAXSIZE front注意那个“牺牲一个存储单元”的判满方式。如果不牺牲这个单元判空和判满就都会变成front rear没法区分。这也是许多初学者理解不了“为什么循环队列最多只能存 MAXSIZE-1 个元素”的原因——就是为了让判空和判满的条件不冲突。你如果亲眼写过一段循环队列的实现体验过“明明数组没满入队却失败”的诡异问题就会对顺序表的边界条件有更深体会。在我面试别人的时候循环队列的判满条件是我最常考察的细节之一能答清楚的人对边界问题的敏感度通常不会太差。注意循环队列取出元素时要先判断front ! rear否则空队列出队会返回一个没意义的值。很多人写代码时只记得判满不记得判空这里出 bug 的概率很高。7. 顺序表应用中的常见问题与调试经验最后把做题和实验过程中最常踩的坑整理成一张表方便你自查。问题现象根本原因解决方案插入元素后尾部的数据丢失插入位置非法或未做越界判断插入前检查 i1删除元素后长度没减少只做了元素搬运忘记L.length--删除成功后必须修改 length 字段并集结果出现重复元素元素插入前没有查重写一个 LocateElem 函数先查再插约瑟夫环出局的人不对下标计算没有取模或忘了减 1用(cur m - 1) % L.length并用小数据手推验证循环队列“没满但加不进去”判满逻辑写错或没牺牲一个存储单元确认判满条件是(rear1)%MAXSIZE front扩容后原数据丢失直接用 realloc 但使用方式错误用临时指针接 realloc 返回值失败时原指针不受影响访问越界数组下标落到负值或 length 以上所有使用下标前先确认 0 ≤ idx length关于动态扩容如果你用的是静态数组data[MAXSIZE]那容量写死不存在扩容问题但表满时插入会失败。如果你用动态内存模拟顺序表就要注意 realloc 的使用姿势。我在实际做项目时是这么处理的int *newData (int *)realloc(L.data, newCapacity * sizeof(int)); if (newData NULL) { // 扩容失败保留原数组 return 0; } L.data newData; L.capacity newCapacity;为什么一定要先把 realloc 的返回值存到临时指针因为 realloc 失败时会返回 NULL同时原内存仍然有效。如果你直接写成L.data realloc(...)一旦失败L.data 就被赋成 NULL原来的数据地址就丢了而且还造成内存泄漏。这个小细节不亲手踩一次坑是不会长记性的。实操心得排查顺序表问题的时候我的习惯是先打印三个值——length、capacity、要操作的 index。大量实验证明90% 的 bug 都在这三个值的边界上。打印出来之后bug 原因基本一眼就能看出来比盯着代码反复看高效得多。