很多人学数据结构学到顺序表，第一反应基本都一样：这不就是数组吗？怎么还值得单独开一章笔记来写？我见过不少初学者就卡在这个认知上，结果一到自己动手写代码、做课程实验、备战考研的时候，才发现顺序表的应用远不是“开个数组”那么简单。下标到底从0还是1开始、插入元素要搬动几个位置、扩容时旧数据怎么无痛迁移、两个有序表怎么合并才不重复不遗漏，这些坑我几乎每年都能在答疑群里看一遍。这篇笔记归纳，核心就抓一个词：应用。我会把顺序表从“怎么封装”讲到“怎么用”，再讲到“什么时候不该用它”，最后把面试和考研里最常见的变形题和易错点一起盘掉。
1. 先搞清楚顺序表的“应用”到底指什么
1.1 顺序表在现实代码里的常见栖身之所
很多教材讲顺序表，开篇就是定义、结构体、插入删除的代码，学完以后你会背了，但不知道什么时候真正用它。顺序表的应用，往大了说就是“一块连续内存 + 随机访问下标”这一模型能覆盖的所有场景，往具体了说，日常代码里最常见的几类包括：
- 学生花名册、通讯录、商品列表这类“总量基本固定，中间不拼命插入删除”的数据集合；
- 需要频繁按位置取数据的场景，比如排行榜、游戏里的单位编队、GUI组件列表；
- 作为更复杂结构的底层存储，比如哈希表里的桶、堆（完全二叉树）的存储、并查集的父数组；
- 教材和算法题里更经典的：有序表合并、多项式表示、矩阵压缩存储。
你发现没有，这些场景有个共同特征：数据是“平铺”的，访问靠坐标，很少在中间动刀。顺序表最舒服的姿势就是把“连续”和“随机访问”这两个特性用到极致，而不是用它去模拟链表的插入删除。
1.2 选顺序表还是链表：先看数据怎么被访问
说到顺序表应用，绕不开和链表的对比。很多新手选数据结构是凭感觉：链表听起来高级，指针很酷，所以一律用链表。这是个大误区。我自己的选择标准很朴素：
如果这个集合的“读”远远多于“改”，尤其是按位置读，果断选顺序表；如果“改”的位置飘忽不定、频繁在中间插和删，再考虑链表。
顺序表按下标访问是O(1)，链表要走到第k个节点是O(k)。反过来，顺序表在头部插入要搬动整表，链表只需要改两个指针。所以“应用”的第一步不是写代码，而是判断该不该用它。判断错了，后面写再多代码都是在给性能挖坑。
2. 从零封装一个可靠可用的顺序表：C语言接口设计与踩坑
先把最有价值的实操部分放在前面。我建议初学阶段不要上来就用STL的vector做“黑盒”，先用C语言手写一个顺序表，你才能真正理解动态扩容、元素搬移和内存释放这些底层动作。下面的实现不追求花哨，追求的是能跑、能查错、能应付实验和考研手写代码。
2.1 结构体与初始化：别把容量和长度混为一谈
顺序表结构体看起来就几行，但“容量”和“长度”这两个概念是第一个分水岭。容量（capacity）是底层数组最多能装多少，长度（length）是当前实际存了多少。很多人只开一个size变量，结果插入到数组末尾时不知道数组满了，直接越界。
一个常见的基础定义：
#define DEFAULT_CAPACITY 8 typedef struct { int *data; // 底层数组基址 int length; // 当前元素个数 int capacity; // 当前容量 } SeqList; void initSeqList(SeqList *list) { list->data = (int *)malloc(DEFAULT_CAPACITY * sizeof(int)); list->length = 0; list->capacity = DEFAULT_CAPACITY; }注意两点：第一，data用malloc分配而不是定死一个int arr[100]，否则扩容无从谈起；第二，初始化后length一定是0，capacity一定是分配出来的真实大小，这两个值在调试时打印出来，能帮你避开一堆莫名奇妙的“越界”和“读取不到数据”的问题。
2.2 插入、删除、查找三个核心操作的正确写法
插入和删除是顺序表应用的灵魂，也是初学阶段最容易写错的代码。插入的核心逻辑是“从后往前搬”，删除的核心逻辑是“从前往后盖”，顺序反了就会把数据覆盖掉。
下面是一种经过反复检验的写法：
int insertElem(SeqList *list, int pos, int value) { if (pos < 0 || pos > list->length) return 0; // 位置非法 if (list->length >= list->capacity) { if (!expandSeqList(list)) return 0; // 扩容失败 } for (int i = list->length; i > pos; --i) { list->data[i] = list->data[i - 1]; // 从尾部开始后移 } list->data[pos] = value; list->length++; return 1; } int deleteElem(SeqList *list, int pos) { if (pos < 0 || pos >= list->length) return 0; for (int i = pos; i < list->length - 1; ++i) { list->data[i] = list->data[i + 1]; // 从删除点开始前盖 } list->length--; return 1; }这个写法的精妙之处在于边界条件极其可读：插入允许pos等于length，因为尾部追加是合法的；删除只允许到length-1，因为删最后一个元素是原地缩一位。很多教材的写法是if (pos >= length - 1)之类的怪判断，虽然也能跑，但不如上面这种清晰，考试手写代码的时候，清晰就是得分。
查找就简单了，按值找首个出现的下标，找不到返回-1，这也是后面很多变形题的基础：
int findElem(SeqList *list, int value) { for (int i = 0; i < list->length; ++i) { if (list->data[i] == value) return i; } return -1; }2.3 扩容策略与内存释放：顺序表最容易翻车的两个地方
动态扩容是顺序表应用里最容易被忽略的环节。我见过不少实验报告，capacity写死100，然后插入第101个元素时静默越界，程序不崩溃但结果全是垃圾值。正确的扩容思路是“翻倍”，不是“加固定值”，因为翻倍才能保证插入的时间复杂度均摊下来是O(1)。
int expandSeqList(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; }这里用realloc而不是malloc+手动拷贝，是因为realloc可能原地扩大，省一次数据搬移；就算搬移，也只是在底层做一次memcpy级别的工作，比手写for循环搬元素高效得多。不过realloc也有坑：如果它返回NULL，你原来的指针并没有被释放，所以一定不要写成list->data = (int *)realloc(...)，而是用临时指针接住返回值。
再有就是内存释放。写完整应用时，链表大家都会记得free节点，顺序表反而容易忘。删除整个顺序表只需要两步：
void destroySeqList(SeqList *list) { free(list->data); list->data = NULL; list->length = 0; list->capacity = 0; }顺序表的内存是“一块连续区域”，释放干净就是free一次的事，这也是它比链表好管理的地方，但也正因为是好管理，很多人在项目里用栈上数组替代，最后程序崩溃在堆区写越界，都是这一课没补上。
3. 三个拿来即用的真实案例：点名系统、有序表合并、稀疏多项式
代码封装得再漂亮，不落到场景里都是白搭。这一节我挑三个最典型、覆盖“查、改、合并、语义映射”多个方向的应用案例，全部按照可直接复现的思路写。
3.1 案例一：学生花名册的点名与修改
这个案例来自很多数据结构的课程实验，需求很简单：一个班50名学生，前期录入，中期支持按学号点名（标记出勤），支持修改成绩，最后统计。这个场景最合适的数据结构就是顺序表，原因有两条：
- 学生人数在学期内基本不变，中途不会频繁插删学生；
- 点名和查成绩本质上都是“按学号定位”，只需要一个按学号查找的映射。
我习惯把学号设计成数组下标，用“学号 = 下标 + 偏移”完成O(1)定位。比如学号从2025001开始，那我分配一个容量大于等于人数范围的数组，下标i存学号2025001+i的信息。这就是顺序表应用里的“直接定址法”思想，比每次都遍历一遍找学号快得多。
typedef struct { int studentId; int attendance; // 出勤次数 int score; // 成绩 } Student; SeqList students; // 容量按班级人数上限开点名时直接按下标定位，修改成绩也一样，根本不需要写查找循环。这个案例想说明的道理是：顺序表的下标本身就是一种“语义”，不要浪费它，能用下标表达的业务逻辑，就不要用线性查找去表达。
3.2 案例二：合并两个有序顺序表（考研高频算法）
这是一个每个考计算机的人都躲不过的算法题：两个非递减有序顺序表，合并成一个新的非递减有序顺序表。别小看它，这是归并排序的思想雏形，也是后面学“归并”系列的起点。
标准解法是双指针：
int mergeSeqList(SeqList *a, SeqList *b, SeqList *c) { if (a->length + b->length > c->capacity) return 0; int i = 0, j = 0, k = 0; while (i < a->length && j < b->length) { if (a->data[i] <= b->data[j]) c->data[k++] = a->data[i++]; else c->data[k++] = b->data[j++]; } while (i < a->length) c->data[k++] = a->data[i++]; while (j < b->length) c->data[k++] = b->data[j++]; c->length = k; return 1; }为什么用双指针而不是先把a放进去再把b插进去？因为双指针每次只比较两个“当前最小”，利用了两个表各自有序的性质，把复杂度控制在O(n+m)。如果硬插，每插一个元素还要搬动后续数据，复杂度直接退化到O(n*m)。这个案例的真正考点不是“你会不会写循环”，而是你能不能写出“每次只取两个序列当前最小值”的那个判断。
还有一个面试喜欢追问的点：如果要求结果中不含重复元素怎么办？很简单，在while里加一个“相等时只放一个”的判断，放完a的再跳过b里所有相等的值。这个变形一定要会，它和“合并两个有序数组并去重”是同一类题。
3.3 案例三：用顺序表存稀疏多项式（系数+指数的妙用）
多项式是顺序表应用中非常经典的一个例子，因为它的存储方式体现了“用下标隐含信息”的高级用法。以一元多项式P(x) = 3 + 2x + 5x^2为例，最直观的存法是顺序表下标就是指数，数组里存系数：
- 下标0存常数项系数3；
- 下标1存x的系数2；
- 下标2存x^2的系数5。
这样两个多项式相加，只需要把对应下标的系数加起来就行，一次循环O(n)搞定。
#define MAX_DEGREE 100 double poly1[MAX_DEGREE] = {0}; double poly2[MAX_DEGREE] = {0}; double result[MAX_DEGREE] = {0}; for (int i = 0; i < MAX_DEGREE; i++) { result[i] = poly1[i] + poly2[i]; }这段代码简单到有点不像算法，但它的思想很值钱：用下标代替显式存储指数，省掉了每一对“指数相等才相加”的判断。不过它有个明显的短板——如果多项式是稀疏的，比如只有x^0和x^99两项，用这种方案要开100个格子才存2个有效系数，空间浪费率极高。这也是顺序表和稀疏结构之间的典型博弈，后面学到稀疏矩阵、十字链表时你还会碰到同样的抉择。真正做题时，如果多项式的次数很密，就用下标映射方案；如果指数跨度巨大但项数不多，就得换成结构体数组去存(系数, 指数)二元组。
4. 性能账本：顺序表为什么“读快写慢”，以及什么时候该放弃
应用做多了你就会发现，选型不是玄学，本质是算账。这一节把这个账本摊开讲透。
4.1 按位置访问是O(1)，按值查找是O(n)：别被“数组很快”骗了
顺序表底层是连续内存，所以按下标访问data[i]时，CPU只需要做一次“基地址 + i × 元素大小”的地址计算，就能直接取到数据，这就是O(1)随机访问。这个特性让顺序表在榜单、队列、堆这种“按序取数”的场景里快得飞起。
但“按值查找”是另一笔账。如果你不知道元素在哪个位置，就只能从下标0开始一个个比对，最坏情况要扫完整个表，复杂度O(n)。很多初学者以为顺序表“有下标所以一定是O(1)”，这个误解会让你的算法分析整个废掉。考试里描述顺序表性能，必须分情况：按位置取是O(1)，按值查是O(n)，这是两个完全不同的操作，不能混为一谈。
4.2 插入和删除的代价：平均移动n/2个元素意味着什么
插入删除要移动元素，这一点大家都懂，但“平均移动多少个”才是关键。在长度为n的顺序表中，在位置i插入一个新元素，需要把从i到n-1的元素全部后移，移动次数是n-i；在位置i删除，需要把从i+1到n-1的元素全部前移，移动次数是n-1-i。位置可以是0到n之间的任意合法位置，各位置等概率时，平均移动次数就是n/2左右。
n/2这个数字单看不大，但放到应用里就很恐怖：如果你频繁在头部插入，每插入一个就要整体后移，10000个元素的表，往头部插一条数据要移10000次，插1000条就是1000万次搬移。实际工程里我见过有人用顺序表做“最近浏览记录”，每次把新浏览的条目插到最前面，然后列表越跑越慢，最后几乎卡死。这就是典型的“用错了地方”——浏览记录的“新数据往头部塞”操作，应该用链表或者循环数组来解决。
所以你需要一条很实用的判断规则：你的应用里“头部和中间”的操作多不多？多就别用顺序表。顺序表最舒服的更新场景是“只在尾部追加和弹出”，也就是栈的那个动作模式，其他更新都要在心里加一笔移动开销。
4.3 扩容摊销分析与实际建议：预留容量还是动态扩容
动态扩容又是一个账。假设每次容量不够就翻倍，那么初始化后连续插入n个元素的过程中，扩容发生的次数是log2(n)级别，每次扩容的搬移代价和当时的容量成正比。把所有搬移加起来，你会发现总和是一个关于n的常数倍，所以均摊下来每次插入的“搬移成本”是O(1)。这就是“均摊复杂度”的直观解释，也是STL vector敢放心自动扩容的底气。
不过均摊O(1)不代表没有瞬时卡顿。扩到一倍时刚好差一个元素，不知道的人会以为这是“刚刚好”，实际上如果你的应用对延迟极其敏感，比如实时渲染里保存一帧的点位，扩容瞬间的整块拷贝会导致那一帧卡一下。省事的做法是预先根据业务上限一次性开足容量，代价是内存浪费一点；稳妥的做法是扩容时预留缓冲，而不是每次触顶才扩。我个人在写实验和考试手写代码时，习惯“预留一半容量”，理由是既省去频繁realloc，又不会让capacity等于length的精确状态造成误判。
5. 面试、考研、期末卷上的顺序表：常见变形题与易错点清单
学完前面的实现和案例，最后一定要落到“题”上。顺序表初阶水平能见到的题目，翻来覆去就那么几类，掌握了套路，考场和面试都不慌。
5.1 五道必刷变形题：逆置、删值、去重、划分类、找中位数
第一类是逆置。把顺序表前k个元素与后n-k个元素整体互换位置，这种题就地操作，双指针从两头往中间swap，时间复杂度O(n)，空间O(1)。别去看那种“新建一个数组再拷回去”的写法，考试和面试都要求原地。
第二类是删除所有等于某个值的元素。要求不新建数组，只扫描一趟。正确思路是双指针：慢指针指向“保留区”末尾，快指针从头扫描，发现不等于目标值就把值写到慢指针位置，慢指针前进；等于目标值就跳过。这样一趟下来，所有等于目标值的元素都被“覆盖”掉了，时间复杂度O(n)，空间O(1)。
int removeAllValue(SeqList *list, int target) { int k = 0; for (int i = 0; i < list->length; ++i) { if (list->data[i] != target) { list->data[k++] = list->data[i]; } } list->length = k; return 1; }第三类是去重，把有序顺序表中重复的元素删掉，只留一个。思路和删特定值高度相似，区别在于判断条件从“不等于target”变成“与保留区最后一个元素不相等”，因为你面对的是有序表，重复元素必然相邻。这个题是考研408特别喜欢出的，本质上考的就是“原地覆盖+有序性利用”。
第四类是划分类，比如把负数放在正数前面，把奇数放在偶数前面。这类题的思想是快速排序中的partition：一个指针从左往右找，一个指针从右往左找，不符合条件的就交换，一趟扫完。它不需要真的排序，只需要“按某个性质分边”，这也是顺序表应用题里最需要理解“性质优先级”的一道题。
第五类是找中位数，两个等长有序顺序表合并后找中位数。最简单的做法是先归并再取中间，O(n)；如果为了高分，可以利用“比较两个序列中位数”的二分思路做到O(log n)。初阶阶段先把归并做法写对，这一步理解透了，进阶的二分做法会顺很多。
5.2 易错点盘点：从下标越界到循环边界，每年都有人栽跟头
下面这张表是我在答疑过程里整理出来的高频易错点，代码和试卷上都反复出现：
| 易错类型 | 错误表现 | 正确思路 |
|---|---|---|
| 容量与长度混淆 | 用capacity当length遍历，读到一堆空位和垃圾值 | 遍历和业务逻辑一律以length为准 |
| 插入位置边界 | pos > length还允许插入，数组出现空洞 | 非尾部插入必须满足pos <= length |
| 删除位置边界 | 删除最后一个元素时循环越界 | 循环条件用i < length - 1，不是i < length |
| 扩容返回处理 | realloc返回NULL时原指针丢失 | 用临时指针接收，失败时保留原数据 |
| 循环方向搞反 | 插入时从前往后移，把后一个元素盖掉了 | 插入必须从最后一个元素开始倒着挪 |
| 静态数组装动态数据 | 开了arr[100]却不知道什么时候会满 | 要么预留足够容量，要么实现扩容机制 |
| 忽略length更新 | 插入后没加、删除后没减 | 每个成功操作必须同步更新length |
这些错误有一个共同根源：初学顺序表时“脑中有数组，心中没有数据结构”。数组的物理结构是连续内存，数据结构的语义结构是“length个有效元素”。只要你在心里时刻记住“有效元素是前length个，下标0到length-1才是合法区间，尾插合法位是length”，90%的边界错误都能提前避免。
再分享一个我自己调代码的习惯：调试顺序表时，第一步永远是打印capacity和length这两个值。很多人一看到“越界”“乱码”就往元素搬运方向猜，其实很多时候只是length忘记更新或者扩容失败，打印出来一眼就能定位。把这两个值打出来，比盯着代码看半小时有效得多。
顺序表初阶应用的笔记归纳写到这里，我脑子里大概浮现出这些年带过的初学者踩过的坑：有用静态数组装动态数据的，有插入删除方向反了覆盖数据的，有在头部疯狂插入然后把程序跑成蜗牛的。这些坑并不高级，但每一届都在重演。把这篇笔记里的接口设计、应用场景和性能账本真正吃透，你的“初阶”这一页就算翻过去了。下一步可以拿着同样的思路去啃链表，你会发现，判断“该用什么结构”的能力，远比背诵某个结构本身的代码更有后劲。
