数据结构精讲

0.1数据结构在 408 里考什么、怎么考

408 是一张 150 分、3 小时的卷子，四门课合考。数据结构排在最前面：第 1~11 题是选择题，第 41、42 题是综合应用题。

全书地图：八篇知识 + 三篇实战

高频考点清单（按出现次数）

目标：数据结构 45 分拿 40 分

若 408 的目标是 125 分，数据结构这 45 分要拿到 40 分左右——它是四门里最“可练”的一门：题型固定、方法固定，花时间就有回报。40 分大致这样分配：

0.2C 语言（一）：变量、数组、循环、函数

先看一个完整的 C 程序，它求一个数组里所有数的和：

#include <stdio.h>            // 使用 printf 要包含这个头文件

int sum(int a[], int n) {        // 函数：接收数组 a 和它的长度 n，返回 int
    int s = 0;                   // 定义一个整型变量 s，初值 0
    for (int i = 0; i < n; i++)  // i 从 0 数到 n-1
        s = s + a[i];            // 把第 i 个元素加进来
    return s;                    // 把结果交回给调用者
}

int main() {                     // 程序从 main 开始执行
    int a[5] = {3, 1, 4, 1, 5};  // 一个有 5 个元素的数组
    printf("%d\n", sum(a, 5));   // 调用 sum，打印 14
    return 0;
}

考试只要求写函数（不用写 main、不用写 #include），但要看懂这个完整的样子。下面把用到的零件逐个讲。

变量：内存里一个有名字的格子

内存可以想成一长排带编号的小格子（每格 1 字节），编号就是地址。写 int x = 5; 就是：找 4 个连续的格子（int 一般占 4 字节），起名叫 x，里面放 5。之后写 x 就是读这个格子里的值，写 x = 7; 就是把 7 放进去（原来的 5 被覆盖）。

运算符里最容易错的几个

int 有多大：常见的 int 占 4 字节，能表示 −2147483648 ~ 2147483647（约 ±21 亿），头文件 limits.h 里叫 INT_MIN、INT_MAX。超出范围会“溢出”——INT_MAX 再加 1 会变成一个很大的负数，程序不会报错，只会悄悄算错。数据结构的代码里有两处要特别留心：① 用 INT_MAX 表示“无穷大”时，dist[u] + INF 会溢出成负数（第 6 篇 Dijkstra 专门讲了这个坑），所以要么先判断“有没有边”，要么把无穷大取成一个不会溢出的大数；② 折半查找的 (low + high) / 2 在下标特别大时也可能溢出（第 7 篇），考试中的数组都很小，一般不用担心。

三种控制结构

if (x > 0)
    y = 1;
else if (x == 0)
    y = 0;
else
    y = -1;

int i = 0;
while (i < n && a[i] != x)
    i++;
// 退出时：要么 i == n
// 要么 a[i] == x

for (int i = 0; i < n; i++) {
    // 循环体执行 n 次
    // i 依次取 0,1,…,n-1
}

for (初始化; 条件; 更新) 循环体 的执行顺序是：初始化 → 判断条件 → 为真就执行循环体 → 更新 → 再判断……条件为假时退出。它和下面的 while 完全等价，分析复杂度时常常要把 for 改写成 while 来数次数：

初始化;
while (条件) { 循环体; 更新; }

break 立即跳出所在的这一层循环；continue 跳过本次循环剩下的部分，直接进入下一次（for 循环会先执行“更新”）。

手动跟踪代码：跟踪表

看懂一段代码最可靠的办法是假装自己是计算机：列一张表，每一列是一个变量，每执行完一轮（或一句）就写一行。后面每一篇的“跟我做一遍”都是这种表，选择题“执行后 x 的值是多少”也这样做。

int i = 0, j = n - 1;
while (i < j) {
    int t = a[i]; a[i] = a[j]; a[j] = t;   // 交换两端
    i++; j--;                             // 两个指针向中间走
}

数组：一排连续的格子

int a[10]; 申请 10 个连续的 int，下标是 0 ~ 9（不是 1 ~ 10）。a[i] 的地址 = 首地址 + i × 4。正因为地址能直接算出来，访问任何一个元素都是一步完成——这叫随机存取，是顺序表、堆、散列表的基础。

二维数组 int b[3][4]; 是 3 行 4 列，在内存里按行一行接一行地放（C 语言是“行优先”）：b[i][j] 前面有 i 整行（每行 4 个）再加 j 个，所以地址 = 首地址 + (i × 4 + j) × 4。第 3 篇的特殊矩阵压缩就是在推这类公式。

数组当函数参数时传的是什么：写 void Clear(int a[], int n) 并调用 Clear(b, 5)，传过去的不是 5 个数的副本，而是数组 b 的首地址。所以函数里把 a[i] 改成 0，改的就是 b 本身——这和普通变量“传值改不动”正好相反（0.3 节三种传参）。也因为只传了地址，函数里不知道数组有多长，长度 n 必须另外作为参数传进去，这就是大题函数头里总有一个 n 的原因。（例子已编译运行。）

函数：把一件事打包

int max(int x, int y) {   // 返回类型 函数名(参数列表)
    if (x > y) return x;
    return y;
}
void swap(int x, int y) { // void 表示没有返回值
    int t = x; x = y; y = t;
}

注意第二个函数交换不了调用者的变量！C 语言调用函数时是值传递：把实参的值复制一份给形参 x、y，函数里改的是副本。要让函数改到外面的变量，必须传它的地址（0.3 节的指针），或者用 C++ 的引用。数组是例外：写 int a[] 当参数时传进去的其实是首地址，所以函数里改 a[i] 会改到外面的数组。

数学补课：后面会用到的五样高中数学

0.3C 语言（二）：指针、结构体、动态内存、typedef 与引用

链表、树、图这些结构全靠指针连起来。指针是零基础同学最大的坎，我们用“门牌号”来理解它。

指针 = 存放“地址”的变量

int x = 5;
int *p;        // p 是“指向 int 的指针”：它里面放一个 int 变量的地址
p = &x;        // &x：取 x 的地址（门牌号），放进 p
*p = 7;        // *p：按 p 里的地址找到那个格子（就是 x），把 7 放进去
printf("%d", x);   // 输出 7

现在可以写出真正能交换的 swap 了：把两个变量的地址传进去，函数里顺着地址去改。

void swap(int *a, int *b) {   // a、b 是地址
    int t = *a; *a = *b; *b = t;
}
// 调用：swap(&x, &y);

结构体：把几样东西捆成一个整体

一个链表结点要同时放“数据”和“下一个结点在哪”，C 语言用 struct 把它们捆在一起：

struct LNode {              // 定义一种新类型：struct LNode
    int data;               // 数据域
    struct LNode *next;     // 指针域：指向下一个同类结点
};

struct LNode a;             // 一个结点变量
a.data = 3;                 // 结构体变量用 . 访问成员
struct LNode *p = &a;       // p 指向 a
p->data = 5;                // 结构体指针用 -> 访问成员，等价于 (*p).data = 5

typedef：给类型起个短名字

typedef struct LNode {
    int data;
    struct LNode *next;
} LNode, *LinkList;         // LNode 是 struct LNode 的别名；LinkList 是 struct LNode * 的别名

LNode *p;                   // p 是指向结点的指针
LinkList L;                 // L 也是指向结点的指针，用这个名字强调“它代表一整条链表”

教材里 LNode * 和 LinkList 完全是一回事，只是习惯上用 LinkList 表示“链表的头指针”，用 LNode * 表示“某个结点”。考试时自己定义清楚、前后一致即可。如果题目已经给出了 typedef（近几年的图、树大题常这样），就直接用题目的类型名和成员名，不要另起一套名字，更不要重新定义一个同名的类型——阅卷老师是对照题目的定义来读你的代码的。

动态内存：malloc 和 free

数组的大小写死在代码里；链表要一个一个结点地“现要现拿”，这就要用动态分配：

#include <stdlib.h>
LNode *s = (LNode *)malloc(sizeof(LNode));  // 向系统要一块能放一个 LNode 的内存，返回它的地址
s->data = 10;
s->next = NULL;
free(s);                                     // 用完还给系统（删除结点时一定要写）

int *a = (int *)malloc(sizeof(int) * n);     // 要 n 个 int 的连续空间，当数组用：a[0] ~ a[n-1]
// C++ 写法：LNode *s = new LNode;  int *a = new int[n];  delete s;  delete[] a;

sizeof(LNode) 算出一个结点占多少字节；(LNode *) 把 malloc 返回的“无类型地址”转换成“结点指针”。算法题里需要一个大小为 n 的辅助数组时（例如 2018-41 找未出现的最小正整数），就这样申请；用 memset(a, 0, sizeof(int) * n) 或一个 for 循环把它清零。

C++ 的引用 &：为什么教材的函数参数里有 &

王道等教材的代码常写成 bool InitList(LinkList &L)。这里的 & 在参数声明里，是 C++ 的“引用”：L 成了调用者那个变量的别名，函数里改 L 就是改外面的变量。它的效果和传指针一样，但写起来不用到处加 *。

void InitList(LinkList *L) {
    *L = (LNode *)malloc(sizeof(LNode));
    (*L)->next = NULL;
}
// 调用：InitList(&L);

void InitList(LinkList &L) {
    L = (LNode *)malloc(sizeof(LNode));
    L->next = NULL;
}
// 调用：InitList(L);

一张图看懂三种传参

void f1(int x)  { x = 100; }    // 值传递
void f2(int *x) { *x = 100; }   // 传指针，调用写 f2(&v)
void f3(int &x) { x = 100; }    // 传引用（C++），调用写 f3(v)

0.4递归：函数调用自己

递归是树、图、快排、归并排序的核心写法，一定要真正想通。先看最简单的例子——阶乘 n! = n × (n−1)!：

int fact(int n) {
    if (n <= 1) return 1;          // ① 出口（边界）：规模小到可以直接回答
    return n * fact(n - 1);        // ② 递归：把 n 的问题交给 n-1 的问题，再加一步
}

递归在计算机里怎么执行：调用栈

每调用一次函数，系统就在一个叫调用栈的区域里压入一块“工作记录”（参数、局部变量、执行到哪一句）；函数返回时弹出这块记录，回到调用它的地方继续。递归调用就是一层层压进去，到出口后再一层层弹出来：

再看两个例子

// 返回 a[0..n-1] 的和
int sum(int a[], int n) {
    if (n == 0) return 0;              // 空数组和为 0
    return sum(a, n - 1) + a[n - 1];   // 前 n-1 个的和 + 最后一个
}

int fib(int n) {        // 1,1,2,3,5,8,…
    if (n <= 2) return 1;
    return fib(n - 1) + fib(n - 2);
}

树的递归是本书用得最多的：“对一棵树做某事 = 对根做一下 + 对左子树递归 + 对右子树递归”，出口是“空树”。第 5 篇的遍历、求高度、求 WPL，第 9 篇的二叉树算法题，全是这个套路。

跟我做一遍：递归的“去”和“回”

void PrintRev(int a[], int n, int i) {   // 逆序打印 a[i..n-1]
    if (i == n) return;                   // 出口
    PrintRev(a, n, i + 1);                // 先把后面的都打印完
    printf("%d ", a[i]);                  // 回来以后再打印自己
}

0.5算法大题怎么答：结构、评分、书写规范

算法设计题的问法几乎一字不变：

评分细则长什么样

以 2013-41（找主元素，13 分）的官方评分说明为例，分数按“你的算法有多高效”分档：

答题卡上的三段式模板

1. 基本设计思想（4~5 行）：先用一句话说总体策略（“两个指针一前一后”“先逆置后半段再合并”“用计数数组标记出现过的数”），再用 2~3 句说关键步骤，必要时画一个小图或举一个小例子。
2. 代码：先写数据类型定义（题目给了就直接用题目的），再写函数。变量名有意义（count、pre、slow/fast），每个循环前面写一行注释说它在干什么，边界处写注释（“p 走到空说明 k 超过表长”）。
3. 复杂度：写“时间复杂度 O(n)，空间复杂度 O(1)”，并用半句话说明理由（“只扫描一趟数组”“只用了常数个辅助变量”）。

示范答卷：每一段的得分点在哪

void DelX(SqList &L, ElemType x) {
    int k = 0;                          // k：已经保留的元素个数
    for (int i = 0; i < L.length; i++)
        if (L.data[i] != x)             // 不是 x：保留，放到第 k 个位置
            L.data[k++] = L.data[i];
    L.length = k;                       // 新表长
}

代码书写规范与常见扣分点

读懂题目给的类型定义

近几年的图、树大题常常先给出一段 typedef，要求“基于这个定义写算法”。拿到它先做三件事：认出每个成员是什么、想好怎么访问、照着它的名字写。以图题常见的邻接矩阵定义为例：

typedef struct {                    // 题目常给的邻接矩阵定义
    int numVertices, numEdges;      // 顶点数、边数
    char VerticesList[MAXV];        // 顶点表
    int Edge[MAXV][MAXV];           // 邻接矩阵，Edge[i][j] == 1 表示有边
} MGraph;

int Degree(MGraph G, int v) {       // 无向图顶点 v 的度
    int d = 0;
    for (int j = 0; j < G.numVertices; j++)
        if (G.Edge[v][j] == 1) d++;
    return d;
}

1. 认成员：顶点个数是 G.numVertices，不是自己设的 n；“i 到 j 有没有边”是 G.Edge[i][j]；顶点的名字在 G.VerticesList[i]，题目要求“输出顶点”时输出它，而不是输出下标 i。
2. 想访问方式：参数是结构体变量 MGraph G 就用点号 G.Edge；若题目写的是 MGraph *G，就要用 G->Edge。一行里 1 的个数是度（有向图是出度），一列里 1 的个数是入度。
3. 照着名字写：成员名、函数名、参数类型都和题目一字不差。自己再定义新的结构体去“改造”题目，阅卷时很难给分。

验证一下：4 个顶点、边 a–b、a–c、b–c、c–d，用 Degree 算出的度依次是 2、2、3、1，加起来 8 = 2 × 边数——握手定理也顺手检查了代码。二叉树题同理：先看结点里有哪些域（data、weight、left、right……），叶结点怎么判断（左右孩子都为 NULL），再动笔。（代码已编译运行核对。）

考场上的顺序与检查

1. 先读完整道题，把所有限制条件圈出来：“时间尽可能高效”“空间 O(1)”“不能破坏原链表”“给出的类型定义”。漏看一个条件，后面全白写。
2. 先写思想再写代码：思想写清楚了，代码即使没写完，思想分也能拿到；思想里顺手写一个小例子，阅卷老师一眼就能看懂你的方法。
3. 代码写完立刻“跑”一遍：拿 2 ~ 3 个元素的小例子，在草稿纸上按跟踪表（0.2 节）走一遍，重点看边界：空表、只有一个元素、第一个和最后一个元素。
4. 最后写复杂度，并对照代码检查一致：几重循环、有没有辅助数组、有没有递归。
5. 时间不够时的取舍：宁可交一份完整、正确的较慢解法，也不要交一份写了一半的最优解——前者通常能拿到大部分分数，后者往往只有思想分。

本篇学完（勾选后目录打 ✓）

1.0本篇地图：概念 + 一把尺子

本篇 8 道选择题全是复杂度（几乎年年第 1 题），概念部分虽然没有单独考过，却是后面每一章都要用的“语言”。学法：概念部分理解即可，复杂度部分要练到看一眼代码就能写出执行次数。

为什么要先学绪论：后面每一章的结构都一样——先讲逻辑结构（元素之间什么关系、能做哪些操作），再讲存储结构（顺序存还是链式存），最后讲在这种存法上运算怎么实现、复杂度是多少。绪论就是这套“三段式”的说明书；复杂度则是比较各种方案的统一尺子。这两样一旦熟了，后面每章都只是往这个框架里填内容。

1.1基本概念：数据、数据结构的三要素

数据结构研究什么

同样一万个人的通讯录：按姓名排好，用折半查找最多比较 14 次就能找到一个人；乱放着，最坏要比较一万次。数据怎么组织，决定了处理它要花多少力气——这就是数据结构这门课要研究的。

先看一个生活里的例子：学校的学生信息表。

数据类型分三类：原子类型（值不可再分，如 int、char）、结构类型（值可以再分成若干成分，如结构体、数组）、抽象数据类型 ADT（一个数学模型 + 定义在模型上的一组操作，只描述“是什么、能做什么”，不管“怎么存、怎么实现”）。例如 ADT 栈：数据是一列元素，操作有 Push、Pop、GetTop、判空。用数组实现还是用链表实现，是存储层面的事。

ADT Complex {
    // 数据：一对实数 (re, im)，表示 re + im·i
    // 操作：
    Create(&z, a, b);    // 构造复数 z = a + b·i
    GetReal(z);           // 返回实部
    GetImag(z);           // 返回虚部
    Add(z1, z2);          // 返回 z1 + z2
    Multiply(z1, z2);     // 返回 z1 × z2
}

为什么要把逻辑结构和存储结构分开：同一个“线性表”，有时用数组存最合适（经常按位置找），有时用链表存最合适（经常插入删除）。如果把“元素之间是什么关系”和“内存里怎么放”绑在一起，换一种存法就得重新定义整个问题；分开以后，逻辑结构和操作的定义不变，只换实现——用户代码只调用 ListInsert，根本不用知道底下是数组还是链表。这和生活里“开车只管方向盘和油门，不管发动机怎么造”是一个道理。选择题里“逻辑结构独立于存储结构”“运算的定义依赖逻辑结构、实现依赖存储结构”这类说法，考的就是这一层意思。

数据结构的三要素

逻辑结构的四种基本类型

边界上的几个“归属”：栈、队列、串都是线性结构（只是限制了操作或元素类型）；一维数组是线性结构，二维、三维数组可以看成“元素本身又是一个线性表”的线性表，教材把它们算作线性表的推广；循环链表是线性表的一种存法，首尾相接并不改变“一对一”的逻辑关系。树也可以看成一种特殊的图（连通、无回路），但在逻辑结构的分类里，树和图分开算。

四种存储结构的对比

跟我做一遍：是逻辑结构还是存储结构

考纲补充（尚无真题）：逻辑结构与存储结构

数据结构的基本概念是考纲点，2009—2026 年没有单独出过选择题，下面一道按考纲自编。

1.2算法与算法评价

算法可以怎么写：自然语言（“先比较 a、b，大的再和 c 比……”）、流程图（下面的辗转相除法）、伪代码、真正的程序代码都可以描述同一个算法。考研大题要求“给出算法的基本设计思想”时用自然语言分步写清楚；要求“用 C 或 C++ 描述算法”时才写代码。

算法是对特定问题求解步骤的一种描述，是指令的有限序列，每条指令表示一个或多个操作。程序 = 数据结构 + 算法：数据结构决定“数据怎么放”，算法决定“怎么一步步处理”。

算法的五个特性（缺一不可）

“好”算法的四个目标

1. 正确性：能正确地解决问题。
2. 可读性：便于人理解（注释、有意义的变量名）。
3. 健壮性：输入非法数据时能适当地做出反应，而不是莫名其妙地崩溃（例如 k 大于表长时返回 0）。
4. 高效率与低存储量需求：执行时间短（时间复杂度低）、占用空间少（空间复杂度低）。

正确性和健壮性别混：正确性管的是“合法输入下答案对不对”，健壮性管的是“非法输入下会不会出乱子”。一个求平均分的程序，输入 3 个成绩算对了，是正确；输入 0 个成绩时不做“除以 0”而是给出提示，是健壮。408 大题写代码时，开头那句 if (i < 1 || i > L.length) return false; 体现的就是健壮性——评分时常常是单独的一个得分点。

为什么不直接“上机测时间”来比较算法？因为运行时间还受机器速度、编译器、输入数据的影响。我们要的是一个只和问题规模 n 有关、能在纸上算出来的指标——这就是复杂度。

408 大题要求“描述算法思想”时，用文字说清楚步骤就行，那是在写算法；要求“用 C 或 C++ 描述算法”时才是写程序。前者答清楚了，后者写不全也能拿到思想分。

跟我做一遍：在一个算法上看五个特性

考纲补充（尚无真题）：算法的特性

算法的五个特性是考纲点，尚无单独的真题，下面一道按考纲自编。

1.3时间复杂度：算法的“快慢”怎么算

从“语句频度”到大 O

一条语句在算法中被重复执行的次数叫它的频度。算法中所有语句的频度之和记为 T(n)，n 是问题规模（数组长度、结点个数……）。例如：

for (i = 0; i < n; i++)          // 条件判断执行 n+1 次
    for (j = 0; j < n; j++)      // 条件判断执行 n(n+1) 次
        c[i][j] = 0;             // 执行 n² 次 ← 最深层的“基本语句”

T(n) 是一个多项式（下面会具体算出它是 2n² + 2n + 1）。n 很大时，起决定作用的只有增长最快的那一项，而且系数也不重要（换台快一倍的机器，系数就变了）。于是只保留最高阶项、去掉系数，记作 T(n) = O(n²)。

用人话说：T(n) = O(n²) 的意思是“n 足够大以后，T(n) 不会超过 n² 的某个固定倍数”。上面的 T(n) = 2n² + 2n + 1，取 C = 3、n₀ = 3，当 n ≥ 3 时 2n² + 2n + 1 ≤ 3n² 都成立（n = 3 时 25 ≤ 27），所以它是 O(n²)。定义里“存在 C 和 n₀”的意思就是：允许忽略系数，也允许忽略 n 很小时的情况——这正是“只看最高阶、不看系数”的数学依据。

为什么只看最高阶：算一算就明白

上面三行代码，按“条件判断 + 赋值”数一数：外层条件判断 n + 1 次，内层条件判断共 n(n + 1) 次，赋值 n² 次，合计 T(n) = 2n² + 2n + 1。把它和 n² 比一比：

n 越大，低次项越无足轻重，T(n) 越来越像“2 倍的 n²”；而系数 2 又会因机器、编译器不同而变。所以只保留“n²”这个增长的形状，写成 O(n²)。（T(n) 由程序逐条计数核对。）

两条运算规则

常见的阶，从小到大

最好、最坏、平均

同一个算法，输入不同，执行次数可能不同。例如在数组中顺序查找 x：第一个就是 x，比较 1 次（最好）；x 在最后或不存在，比较 n 次（最坏）；各位置概率相等时平均比较 (n+1)/2 次（平均）。一般说的时间复杂度指最坏情况，它给出了运行时间的上限；平均复杂度是所有输入等概率时的期望。

有时三种情况差得很远，就要分开说：快速排序最坏 O(n²)（输入已经有序时，第 8 篇），平均却是 O(n log n)，而且实际中最坏情况很少碰到，所以介绍快排时总是“平均 O(n log n)、最坏 O(n²)”一起说。做题时题目问哪一种就答哪一种；没说明时按最坏情况答，因为最坏情况是一个“无论如何都不会更差”的保证。

做题套路：六种循环怎么数次数

算时间复杂度就是数“最内层基本语句执行了几次”。下面六种情形覆盖了全部真题：

跟着做一遍：套路 ②③④

for (i = 1; i <= n; i++)
    for (j = 1; j <= i; j++)
        x++;

for (i = 1; i < n; i *= 2)
    for (j = 0; j < i; j++)
        sum++;

x = 2;
while (x < n / 2)
    x = 2 * x;

int func(int n) {
    int i = 0, sum = 0;
    while (sum < n) sum += ++i;
    return i;
}

三类循环各两题：每题都有“执行次数表”

下面 6 段代码都在电脑上真的跑过，表里是 x++（或循环体）实际执行的次数，用来检验推导。

for (i = 1; i <= n; i++)
    for (j = 1; j <= i; j *= 2)
        x++;

倍增实验：把 n 翻倍，看次数怎么变

推出复杂度以后怎么检验？最简单的办法是把 n 翻一倍，看基本语句的次数变成原来的几倍：

规律：O(log n) 加常数、O(n) 乘 2、O(n log n) 乘略大于 2、O(n²) 乘 4、O(n³) 乘 8、O(2ⁿ) 则是平方——这就是 1.3 节各张“实际次数表”的读法。考场上推不出来时，把 n 代成 16 和 32（或 64）手数一下，比一比就能排除大部分选项。（表中数字由程序实际计数。）

规模有两个参数时：O(m + n) 还是 O(mn)

很多问题的规模不止一个数：两个链表长 m 和 n、图有 n 个顶点 e 条边。这时复杂度里要同时出现两个参数，判断方法还是“数基本语句”：

• 两段依次处理：先扫一遍长 m 的表，再扫一遍长 n 的表，是 m + n 次，写 O(m + n)。因为 max(m, n) ≤ m + n ≤ 2·max(m, n)，O(m + n) 和 O(max(m, n)) 是同一个阶——选项里出现哪种写法都对。
• 嵌套处理：对长 m 的表里每个元素，都去扫一遍长 n 的表，是 m × n 次，写 O(mn)。例如 i 从 0 到 29、j 从 0 到 49 的双重循环执行 1500 次 = 30 × 50。
• 不能随便“化成一个 n”：只有题目说明 m、n 同阶（或 m ≤ n）时，才可以把 O(m + n) 写成 O(n)。两个有序链表归并，每比较一次就有一个结点被摘下来，最多 m + n − 1 次比较——下面 2013-01 考的正是这一点。

真题怎么考：8 道题，3 种套路

秒杀法什么时候会失灵：① “外层 log n 次 × 内层 n 次 = n log n”只在内层次数与外层无关时成立，2022-01 就是专门设的陷阱；② “看到 i*i 就是 √n”要小心——2025-01 里外层确实只走 √n 次，但内层还要再跑 i 次，总次数是 1 + 2 + … + √n ≈ n/2，答案是 O(n) 而不是 O(√n)；③ 递归不能数代码行，要写递推式。拿不准时就把 n 代成 16、64 这样的数，实际数一数，用两个数的比值猜阶。

选择题变式：真题换个条件再做一遍

每道题都由一道真题改动一两个条件而来。先做本节的真题，再做这里的变式，最后看“变化点”：改了什么、答案为什么跟着变。

count = 0;
for (k = 1; k <= n; k *= 2)
    for (j = 1; j <= k; j++)
        count++;

int func(int n) {
    int i = 0, sum = 0;
    while (sum < n) {
        i++;
        sum += i * i;
    }
    return i;
}

int sum = 0;
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j += i)
        sum++;

1.4空间复杂度与递归算法的复杂度

空间复杂度

算法的空间复杂度 S(n) 是它所需的存储空间关于 n 的数量级。只算辅助空间：输入数据本身占的空间（题目给的数组）不算，因为无论什么算法都要存它。

递归的空间：工作栈有多深

递归调用时，系统为每一层调用在递归工作栈里压一个栈帧（参数、局部变量、返回地址），这一层返回时弹出（图见 3.6）。所以递归的空间复杂度 = 递归的最大深度 × 每层的空间，与总共调用了多少次无关：

斐波那契这一行最能说明问题：调用了指数多次，但任何时刻栈里最多 n 层，所以时间指数级、空间只是 O(n)。

空间复杂度按什么单位数：和时间一样只看数量级，“一个整数”“一个指针”“一个栈帧”都算常数个单位。所以开 3 个变量和开 30 个变量都是 O(1)，开一个长 n 的数组是 O(n)，开一个 n × n 的矩阵是 O(n²)；递归时用“深度 × 每层的常数”算。

递归算法的时间复杂度：写递推式

对递归算法，设规模为 n 时的执行时间为 T(n)，根据代码写出 T(n) 和更小规模的关系，再逐层展开：

以汉诺塔为例（3.6 节）：挪 n 个盘子 = 挪两次 n − 1 个 + 挪一次最大的，T(n) = 2T(n − 1) + 1，展开得 2ⁿ − 1。看递推式的“形状”就能大致判断阶：规模减 1、只调用一次是线性级，规模减 1、调用两次是指数级，规模减半是对数级（或配合每层工作量得到 n log n）。

递归树法：一层一层加起来

同一个式子用展开法：T(n) = 2T(n/2) + n = 4T(n/4) + 2n = 8T(n/8) + 3n = … = nT(1) + n·log₂n。设 T(1) = 1，得 T(n) = n log₂n + n（程序对 n = 2 ~ 2¹⁷ 逐个核对）。

void g(int n) {
    if (n <= 1) return;
    for (int i = 0; i < n; i++) x++;   // 本层做 n 次
    g(n / 2);                          // 规模减半，只递归一次
}

拓展 主定理：三种情况一眼看出

对 T(n) = aT(n/b) + f(n)（a ≥ 1，b > 1），把 f(n) 和 n^log_ba（叶子层的总工作量）比大小：

规律：谁大听谁的；一样大就再乘一个 log n。408 只要求会展开，主定理当作检验工具即可（严格的条件比这里写的多，不展开）。

拓展 本书会遇到的几种算法设计思想：复杂度只是“尺子”，真正决定算法好坏的是设计思想。后面各章的算法大致可以归成几类——分治（把问题切成几个同类的小问题，各自解决再合起来）：折半查找、归并排序、快速排序；贪心（每一步都选眼前最好的，并且能证明这样最后也是最好的）：哈夫曼树、Prim、Kruskal、Dijkstra；动态规划（把子问题的答案存起来，避免重复计算）：Floyd、关键路径的 ve 和 vl、记忆化的斐波那契；回溯（走不通就退回上一步换条路）：DFS、求所有简单路径；空间换时间：散列表、计数数组。学到这些算法时回头对照，能看出它们“为什么这样设计”。

int fact(int n) {
    if (n <= 1) return 1;
    return n * fact(n - 1);
}

选择题变式：真题换个条件再做一遍

每道题都由一道真题改动一两个条件而来。先做本节的真题，再做这里的变式，最后看“变化点”：改了什么、答案为什么跟着变。

int f(int n) {
    if (n <= 1) return 1;
    return f(n - 1) + f(n - 1);
}

int h(int n) {
    if (n <= 1) return 1;
    return h(n / 2) + h(n / 2);
}

1.5本篇总结：一页纸 + 必会题型

1.✎本篇真题闯关（8 题）

本篇各小节挂的真题全部在这里，按小节排好。可以展开后一道道做，也可以用弹窗模式连续做。做题记录（对/错）只保存在你这台电脑的浏览器里，小节标题下的题号会随之变绿或变红。

本篇学完（勾选后目录打 ✓）

2.0本篇地图：从“一队元素”到算法大题

选择题每年大约 1 道，考的是“某操作在某种存储下要多少时间”“这几句指针语句对不对”；真正的分量在算法大题——18 年里有 11 道是在数组或链表上做文章。所以本篇的学法是：前四节把每个操作画图、逐句跟踪弄熟，第 5 节练七个基本功和类似题。

2.1线性表的定义和基本操作

为什么先学线性表

生活里大量数据天然“排成一队”：学号表、购物车里的商品、一句话里的字、等着打印的文件……共同点是每个元素前面最多一个、后面最多一个。把这种“一个接一个”的关系抽出来，就是线性表。后面的栈、队列是“只能在端点操作”的线性表，串是“元素都是字符”的线性表，所以它是整门课的地基。

线性表是具有相同数据类型的 n（n ≥ 0）个数据元素的有限序列，记作 L = (a₁, a₂, …, aᵢ, …, aₙ)。n 叫表长，n = 0 时是空表。

• 相同类型：每个元素占同样大小的空间（这是顺序表能用公式算地址的前提）。
• 有限：元素个数有限。“所有整数”不是线性表。
• 序列：有先后次序。a₁ 叫表头元素，aₙ 叫表尾元素；除 a₁ 外每个元素有且仅有一个直接前驱，除 aₙ 外每个元素有且仅有一个直接后继。
• aᵢ 的“i”叫位序，从 1 开始；而 C 数组下标从 0 开始——写代码时第 i 个元素是 data[i-1]，这是最常见的错误来源。

线性表是一种逻辑结构；顺序表、链表是它的两种存储结构（实现方式）。

同一张表，两种存法

这一张图就是整篇的提纲：“线性表”说的是逻辑结构——元素排成一队、每个至多一个前驱和一个后继；“顺序表”“链表”说的是存储结构——这一队元素在内存里怎么放。同一个逻辑结构可以有不同的存法，不同存法在“找第 i 个”“插一个”“删一个”上的快慢正好相反：顺序表找得快、改得慢，链表改得快、找得慢。2.2 ~ 2.4 节分别讲两种存法，2.5 节教你按需要选，并把它们用到算法题里。

基本操作（ADT）

参数前的 & 是 C++ 引用（见 0.3）：凡是要修改表本身的操作都要加。

怎么读这张表：InitList、ListInsert、ListDelete、DestroyList 会改变表（长度、内容或存储空间），所以 L 前有 &；LocateElem、GetElem、Length 只是“看一看”，L 前没有 &。ListDelete 的 e 前也有 &，因为要把删掉的值“带回”给调用者。这组操作是线性表的“接口”：后面不管用顺序表还是链表实现，名字和参数都一样，只是函数里面的写法不同——这就是“逻辑结构定义操作，存储结构决定实现”的意思。

跟我做一遍：哪些是线性表

考纲补充（尚无真题）：线性表的定义

线性表的定义与逻辑特征是考纲点，2009—2026 年没有单独出过选择题，下面一道按考纲自编。

2.2顺序表：用数组存线性表

把线性表的元素依次存放在一组地址连续的存储单元里，逻辑上相邻的元素物理上也相邻。第 i 个元素的地址：

两种定义方式

#define MaxSize 50
typedef struct {
    ElemType data[MaxSize];  // 静态数组
    int length;              // 当前长度
} SqList;

#define InitSize 100
typedef struct {
    ElemType *data;          // 指向动态数组
    int MaxSize, length;
} SeqList;
// 初始化：
L.data = (ElemType *)malloc(sizeof(ElemType) * InitSize);

顺序表的特点：① 随机访问；② 存储密度高（只存数据本身）；③ 扩充容量不方便；④ 插入、删除要移动大量元素。

顺序表和数组是一回事吗：不完全是。数组是 C 语言提供的“一块连续内存 + 按下标访问”的机制，长度在定义时就定了；顺序表是“用数组来存线性表”，还要多一个 length 记录当前用了几个格子，并约定元素必须从头开始连续存放、中间不能有空位。所以 MaxSize 是“最多能放几个”，length 是“现在放了几个”——判满看 length == MaxSize，判空看 length == 0。

“随机访问”为什么是 O(1)：元素一个挨一个地放，第 i 个元素的地址 = 第 1 个元素的地址 + (i − 1) × 每个元素的大小。例如 int 占 4 字节、表从地址 1000 开始，第 5 个元素就在 1000 + 4 × 4 = 1016，一次乘法加法就算出来了，不管表有多长。这里的“随机”是“想访问哪个就直接访问哪个”的意思，不是“碰运气”。链表做不到，是因为第 i 个结点的地址只记在第 i − 1 个结点的 next 里，只能一个个顺着找。

动态分配：满了怎样“扩容”

void IncreaseSize(SeqList &L, int len) {      // 把容量增加 len
    ElemType *p = L.data;                         // ① 记住旧数组
    L.data = (ElemType *)malloc(sizeof(ElemType) * (L.MaxSize + len));   // ② 申请更大的新数组
    for (int i = 0; i < L.length; i++)            // ③ 逐个复制：O(n)
        L.data[i] = p[i];
    L.MaxSize += len;
    free(p);                                      // ④ 释放旧数组
}

易错：“动态分配”只是说容量可以在运行时改，它仍然是顺序存储、仍然支持随机存取；扩容时不能“在原地变长”，因为旧数组后面的内存可能已经被别的变量占用。拓展 如果每次扩成原来的 2 倍，连续在表尾插入 n 个元素，复制的总次数不超过 2n，平均到每次插入只是 O(1)。（代码与“不超过 2n”均由程序验证。）

插入：把后面的元素往后挪一格

bool ListInsert(SqList &L, int i, ElemType e) {
    if (i < 1 || i > L.length + 1) return false;   // i 的合法范围是 1 ~ length+1
    if (L.length >= MaxSize) return false;         // 表满
    for (int j = L.length; j >= i; j--)            // 从最后一个开始，依次后移
        L.data[j] = L.data[j - 1];
    L.data[i - 1] = e;                             // 位序 i 对应下标 i-1
    L.length++;
    return true;
}

为什么必须从后往前移：在 a, b, c, d 的第 2 个位置插入 x。若从前往后移，先做 data[2] = data[1]，c 就被 b 盖掉了；接着 data[3] = data[2]，又把刚复制来的 b 抄过去……最后得到 a, x, b, b, b——c、d 全丢了。从后往前移则是先把 d 挪到空位、再挪 c、再挪 b，每次都往一个“已经腾出来”的格子里写，谁也不会被覆盖。记法：往哪边挪，就先动那一头的元素——后移先动最后一个，前移（删除）先动最前面那个。

i 的合法范围为什么是 1 ~ length + 1：可以插在第 1 个元素之前（i = 1），也可以接在最后一个元素之后（i = length + 1），但不能“隔空”插到 length + 2——顺序表中间不能有空位。删除时 i 只能是 1 ~ length，因为只有这么多元素。代码第一句先判 i，第二句判表满，先判合法再动数据，是写所有修改操作的好习惯。（覆盖的例子由程序模拟。）

删除：把后面的元素往前挪一格

bool ListDelete(SqList &L, int i, ElemType &e) {
    if (i < 1 || i > L.length) return false;       // 合法范围 1 ~ length
    e = L.data[i - 1];                             // 带回被删元素
    for (int j = i; j < L.length; j++)             // 从被删位置的后一个开始，依次前移
        L.data[j - 1] = L.data[j];
    L.length--;
    return true;
}

删除第 i 个要前移 n − i 个元素；可删位置 n 个，平均移动 (n − 1)/2 次。最好 O(1)（删表尾），最坏 O(n)（删表头），平均 O(n)。注意删除要从前往后移，方向和插入相反。

平均移动次数：画成阶梯一眼看懂

概率不相等时就做“加权平均”：每个位置的移动次数乘以它的概率再相加。例如插入时有一半的机会插在表尾（不用移），另一半平均分给前 n 个位置，则平均移动 = ½ × 0 + (1/2n) × (n + n − 1 + … + 1) = (n + 1)/4。（各公式由程序对 n = 1 ~ 39 逐一核对。）

查找

ElemType GetElem(SqList L, int i) { return L.data[i - 1]; }   // 按位查找：O(1)

int LocateElem(SqList L, ElemType e) {                        // 按值查找：返回位序，失败返回 0
    for (int i = 0; i < L.length; i++)
        if (L.data[i] == e) return i + 1;
    return 0;
}

按值查找最好 1 次、最坏 n 次，平均 (n + 1)/2 次，O(n)。如果顺序表有序，按值查找可以用折半查找做到 O(log n)（第 7 篇），但插入、删除仍然是 O(n)——找到位置很快，挪元素还是慢。

跟我做一遍：插入、删除各一次

选择题变式：真题换个条件再做一遍

每道题都由一道真题改动一两个条件而来。先做本节的真题，再做这里的变式，最后看“变化点”：改了什么、答案为什么跟着变。

2.3单链表：用指针串起来

顺序表插删要挪一大片，扩容要整体搬家。链表换个思路：每个元素单独找个地方放，再用指针记住“下一个在哪”。

typedef struct LNode {
    ElemType data;           // 数据域
    struct LNode *next;      // 指针域：指向后继结点
} LNode, *LinkList;

头指针、头结点、首元结点

引入头结点的两个好处：① 第一个数据结点也有前驱（头结点），在表头插入、删除和在其他位置的代码完全一样；② 空表和非空表的处理统一（头指针永远非空）。算法大题的链表几乎都带头结点。

带不带头结点，代码差在哪

bool ListInsertNH(LinkList &L, int i, ElemType e) {
    if (i < 1) return false;
    if (i == 1) {                 // 插在表头：要改头指针 L 本身
        LNode *s = (LNode *)malloc(sizeof(LNode));
        s->data = e;  s->next = L;  L = s;
        return true;
    }
    LNode *p = L;  int j = 1;     // p 指向第 j 个结点
    while (p != NULL && j < i - 1) { p = p->next; j++; }
    if (p == NULL) return false;  // i 太大
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;  s->next = p->next;  p->next = s;
    return true;
}

bool ListInsertH(LinkList L, int i, ElemType e) {
    if (i < 1) return false;
    LNode *p = L;  int j = 0;     // 头结点算第 0 个
    while (p != NULL && j < i - 1) { p = p->next; j++; }
    if (p == NULL) return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;  s->next = p->next;  p->next = s;
    return true;
}

两个版本已编译，对随机表和随机位置（含非法位置）与标准答案逐一对拍。

建立单链表：头插法与尾插法

LinkList HeadInsert(LinkList &L, int a[], int n) {
    L = (LNode *)malloc(sizeof(LNode));
    L->next = NULL;                  // 空表
    for (int i = 0; i < n; i++) {
        LNode *s = (LNode *)malloc(sizeof(LNode));
        s->data = a[i];
        s->next = L->next;           // ① 新结点指向原来的第一个
        L->next = s;                 // ② 头结点指向新结点
    }
    return L;
}

LinkList TailInsert(LinkList &L, int a[], int n) {
    L = (LNode *)malloc(sizeof(LNode));
    LNode *r = L;                    // r 始终指向表尾
    for (int i = 0; i < n; i++) {
        LNode *s = (LNode *)malloc(sizeof(LNode));
        s->data = a[i];
        r->next = s;                 // 接到表尾
        r = s;                       // r 移到新的表尾
    }
    r->next = NULL;                  // 表尾置空，千万别忘
    return L;
}

两种方法都是每个元素 O(1)，建表 O(n)。

尾插法最后那句 r->next = NULL 为什么不能忘：malloc 出来的结点，next 里是一个不确定的值（“野指针”）。不置空，表尾后面就“接”着一块不知道是哪里的内存，之后遍历时 while (p != NULL) 停不下来，程序可能崩溃。头插法不需要这句，因为第一个插入的结点继承了 L->next 的 NULL，它自然成为表尾。选用哪一种看题目要的次序：要保持输入次序用尾插，要倒过来用头插。

查找：只能从头一个个走

LNode *GetElem(LinkList L, int i) {      // 按位查找第 i 个结点（带头结点），i = 0 返回头结点
    if (i < 0) return NULL;
    LNode *p = L;  int j = 0;            // p 指向第 j 个结点，头结点算第 0 个
    while (p != NULL && j < i) {
        p = p->next;  j++;
    }
    return p;                            // i 超过表长时 p 走到 NULL
}
LNode *LocateElem(LinkList L, ElemType e) {   // 按值查找
    LNode *p = L->next;
    while (p != NULL && p->data != e) p = p->next;
    return p;                            // 找不到返回 NULL
}

按位、按值查找都是 O(n)：链表不能随机存取，只能顺序存取。求表长也要从头数到尾，O(n)（除非额外维护一个 length）。

int Length(LinkList L) {                  // 带头结点：数据结点的个数
    int len = 0;
    for (LNode *p = L->next; p != NULL; p = p->next) len++;
    return len;
}

GetElem 里的 j 怎么理解：j 始终表示“p 指向第几个结点”，头结点算第 0 个。循环条件 j < i 让 p 停在第 i 个；若中途 p 变成 NULL，说明表不够长，返回 NULL。这种“指针 + 计数器同步走”的写法是链表题的基本动作，删除、插入都先用它找到第 i − 1 个（前驱）。数表长时从 L->next 开始数，不要把头结点也算进去——带头结点的空表长度是 0。

插入：顺序很重要

bool ListInsert(LinkList &L, int i, ElemType e) {    // 在第 i 个位置插入（带头结点）
    LNode *p = GetElem(L, i - 1);                    // 找到第 i-1 个结点：O(n)
    if (p == NULL) return false;                     // i 不合法
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;                               // ①
    p->next = s;                                     // ②
    return true;
}

插入本身（① ②）是 O(1)，时间花在找前驱上，所以“在第 i 个位置插入”是 O(n)，而“在已知结点 p 之后插入”是 O(1)。

① ② 颠倒会怎样：先执行 p->next = s，p 原来的后继就再也找不到了（唯一记着它地址的就是 p->next）；接着 s->next = p->next 得到的是 s 自己，s 指向自己形成一个小环，后半个链表全部丢失。所以口诀“先连后面、再连前面”的本质是：任何一个指针被改写之前，它指向的结点必须已经有别的指针记住。双链表的四句、链表逆置的 r，都是这一条原则。

s->next = p->next;  p->next = s;             // s 插到 p 之后
ElemType t = p->data;  p->data = s->data;  s->data = t;   // 交换数据

删除

bool ListDelete(LinkList &L, int i, ElemType &e) {  // 删除第 i 个结点
    LNode *p = GetElem(L, i - 1);                   // 找前驱
    if (p == NULL || p->next == NULL) return false; // i 不合法
    LNode *q = p->next;                             // q 指向被删结点
    e = q->data;
    p->next = q->next;                              // 前驱“跨过”q
    free(q);                                        // 释放。先改指针再 free，顺序不能反
    return true;
}

删除的顺序也有讲究：必须先 p->next = q->next 再 free(q)。若先 free(q)，q 指向的内存已经还给系统，再读 q->next 就是读一块“作废”的内存，结果不可预料；而 e = q->data 也要在 free 之前取出。free 之后最好不要再碰 q。

同理，删除已知结点 p 而不知道前驱时，可以把后继的数据复制到 p，再删掉后继（O(1)）；但如果 p 是最后一个结点就不行，只能从头找前驱。

按值删除：pre、p 两个指针一起走。删除的关键是拿到被删结点的前驱，所以遍历时让 pre 永远跟在 p 后面一步：

bool DeleteFirstX(LinkList L, ElemType x) {   // 带头结点：删除第一个值为 x 的结点
    LNode *pre = L, *p = L->next;               // pre 始终是 p 的前驱
    while (p != NULL && p->data != x) { pre = p; p = p->next; }
    if (p == NULL) return false;                // 没找到
    pre->next = p->next;  free(p);
    return true;
}

带头结点的好处在这里又显出来：要删的若是第一个数据结点，它的前驱就是头结点，pre 从 L 出发正好覆盖这种情况，不用特判。要删除所有值为 x 的结点，只需把 if 改成循环里的分支：找到 x 就 pre->next = p->next; free(p); p = pre->next;（pre 不动），否则 pre、p 一起后移。（DeleteFirstX 与数组模型随机对拍 5 万组。）

两个 O(1) 技巧：偷梁换柱

void InsertBefore(LNode *p, ElemType e) {   // 在 p 之前插入 e
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->next = p->next;  p->next = s;        // s 先插到 p 之后
    s->data = p->data;  p->data = e;        // 再把数据换一下
}
bool DeleteNode(LNode *p) {                 // 删除 p 自己；p 是尾结点时做不到
    LNode *q = p->next;
    if (q == NULL) return false;            // 没有后继可借
    p->data = q->data;                      // 后继的数据搬到 p
    p->next = q->next;                      // 再删掉后继
    free(q);
    return true;
}

跟我做一遍：逐句执行指针语句

选择题变式：真题换个条件再做一遍

每道题都由一道真题改动一两个条件而来。先做本节的真题，再做这里的变式，最后看“变化点”：改了什么、答案为什么跟着变。

2.4双链表、循环链表、静态链表

双链表：多一个指向前驱的指针

单链表只能往后走，找前驱要从头开始。双链表的结点多一个 prior 指针，可以双向走，代价是每个结点多占一个指针的空间。

typedef struct DNode {
    ElemType data;
    struct DNode *prior, *next;    // 前驱、后继
} DNode, *DLinkList;

// 删除 p 的后继 q
DNode *q = p->next;
p->next = q->next;
if (q->next != NULL) q->next->prior = p;   // q 不是最后一个结点时才需要
free(q);

// 删除 p 自己（双链表可以直接删，不用找前驱）
p->prior->next = p->next;      // 前驱的 next 跨过 p
p->next->prior = p->prior;     // 后继的 prior 跨过 p（p 是尾结点时要判空）
free(p);

边界一定要想到：带头结点的双链表里，p 的前驱至少是头结点，所以 p->prior->next 总能写；但 p 若是最后一个结点，p->next 是 NULL，第二句 p->next->prior 就会访问空指针而崩溃，必须先判断 if (p->next != NULL)。循环双链表没有 NULL（尾结点的 next 指回头结点），这两句永远成立，所以考题里常用循环双链表来“省掉边界判断”。

跟我做一遍：四句话的顺序到底哪些能换

循环链表：尾巴接回头

int LengthC(LinkList L) {                 // 带头结点的循环单链表求表长
    int len = 0;
    for (LNode *p = L->next; p != L; p = p->next) len++;   // 回到头结点才停
    return len;
}

把普通单链表的代码照搬过来、仍写 p != NULL，在循环链表上就是死循环——循环链表里根本没有 NULL。判空也跟着变：带头结点的循环单链表为空时 L->next == L（头结点自己指向自己）。凡是“从头走到尾”的代码，换到循环链表上第一件事就是改终止条件。（代码对 0 ~ 49 个结点核对。）

为什么循环单链表常常只设尾指针：有了尾指针 r，表尾就是 r，表头（头结点）就是 r->next，两头都是 O(1)；只设头指针的话，找表尾要走一遍。一个典型用法是把两个循环单链表首尾相接，只改几根指针：

LinkList Join(LinkList ra, LinkList rb) {   // ra、rb 分别指向两个带头结点的循环单链表的尾结点
    LNode *ha = ra->next;                    // A 的头结点
    ra->next = rb->next->next;               // A 的尾接到 B 的第一个数据结点
    free(rb->next);                          // 释放 B 的头结点
    rb->next = ha;                           // B 的尾接回 A 的头结点
    return rb;                               // 新表的尾指针
}

四句话的顺序有讲究：第一句先用 ha 记住 A 的头结点，因为第二句会把 ra->next 改掉；第三句 free 的是 B 的头结点，必须在第二句用完 rb->next->next 之后、第四句改写 rb->next 之前。时间 O(1)。同样的事情用只有头指针的单链表做，得先走到 A 的表尾，O(n)。（代码随机对拍 2 万组。）

大横评：哪种链表做哪件事最快

下表 n 为元素个数。判断的诀窍只有一句：要动某个结点，先问它的前驱能不能 O(1) 拿到（删尾结点要尾的前驱，所以只有双链表能 O(1)）。

带尾指针 r 时：带头结点的首元是 r->next->next，不带头结点的首元是 r->next；表尾插入就是插在 r 之后再让 r 后移。

* 不带头结点时，第一个结点变了，尾结点的 next 也要跟着改，而只有头指针找不到尾，所以按常规做法是 O(n)（用“交换数据”的技巧可以绕过去，但题目一般按常规做法算）。结论：只要涉及“表头 + 表尾”的插入和删首，选“带尾指针的循环单链表”；还要删尾，就只能用循环双链表。

静态链表：用数组模拟链表

有些语言（或场合）没有指针，可以用一个结构体数组来模拟链表：每个元素存数据和“下一个元素的数组下标”（叫游标），用 −1 表示结束。0 号单元充当头结点。

从 0 出发：0 → 2(a) → 1(b) → 4(c) → 3(d) → −1，逻辑顺序是 a、b、c、d。插入、删除只改游标，不移动元素；但和顺序表一样要预先分配一块连续空间，容量固定，而且不能随机存取（要按游标一个个走）。操作系统里文件分配表 FAT 就是静态链表。

它像谁（三句话记住静态链表）：从“改游标、不挪元素”看，它继承了链表插删方便的优点；从“一次开好一整块数组、容量固定”看，它又带着顺序表空间不灵活的缺点；同时它既不能随机存取（要顺着游标走），每个元素还多存一个游标——所以静态链表只在“没有指针可用”或“想把链表整个存进一块连续空间（比如写进磁盘）”时才用。选择题考它，几乎都在考这几条优缺点；题目给出一张“下标—数据—游标”表让你写出逻辑顺序时，就从 0 号单元的游标出发一格格往下跳，直到 −1。

#define MaxSize 50
typedef struct {
    ElemType data;
    int next;          // 下一个元素的数组下标，-1 表示表尾
} SLinkList[MaxSize];

静态链表的“空闲链”：数组里的 malloc 和 free

静态链表没有 malloc，空位从哪来？办法是把所有空闲单元也用游标串成一条链（空闲链），插入时从空闲链头上取一个，删除时把单元还回空闲链。于是一个数组里同时有两条链：

#define SMAX 8
typedef struct { ElemType data; int next; } SNode;
SNode S[SMAX];
int freeHead;                       // 空闲链第一个下标，-1 表示没有空位
void InitSList() {
    S[0].next = -1;                 // 0 号：数据链的头结点，空表
    for (int i = 1; i < SMAX - 1; i++) S[i].next = i + 1;   // 1→2→…→SMAX-1 串成空闲链
    S[SMAX - 1].next = -1;
    freeHead = 1;
}
int AllocNode() {                   // 从空闲链取一个下标（相当于 malloc）
    int k = freeHead;
    if (k != -1) freeHead = S[k].next;
    return k;
}
void FreeNode(int k) {              // 把下标 k 还给空闲链（相当于 free）
    S[k].next = freeHead;  freeHead = k;
}
bool SInsert(int i, ElemType e) {   // 在第 i 个位置插入
    int p = 0, j = 0;
    while (p != -1 && j < i - 1) { p = S[p].next; j++; }   // 找第 i-1 个
    if (i < 1 || p == -1) return false;
    int k = AllocNode();
    if (k == -1) return false;      // 没有空位
    S[k].data = e;  S[k].next = S[p].next;  S[p].next = k;  // 和单链表的插入一模一样
    return true;
}
bool SDelete(int i, ElemType &e) {  // 删除第 i 个
    int p = 0, j = 0;
    while (p != -1 && j < i - 1) { p = S[p].next; j++; }
    if (i < 1 || p == -1 || S[p].next == -1) return false;
    int q = S[p].next;
    e = S[q].data;  S[p].next = S[q].next;
    FreeNode(q);                    // 单元还给空闲链
    return true;
}

代码已编译；对随机插入、删除序列与“数组模型”逐步比对，并检查“数据链结点数 + 空闲链结点数 = 7”始终成立。本表就是程序运行的结果。

选择题变式：真题换个条件再做一遍

每道题都由一道真题改动一两个条件而来。先做本节的真题，再做这里的变式，最后看“变化点”：改了什么、答案为什么跟着变。

2.5顺序表 vs 链表，以及算法题的七个基本功

怎么选存储结构

基本功 ①：原地逆置（两端交换）

void Reverse(int a[], int left, int right) {     // 逆置 a[left..right]
    while (left < right) {
        int t = a[left];  a[left] = a[right];  a[right] = t;
        left++;  right--;
    }
}

时间 O(n)，空间 O(1)。2010-42 循环左移 p 位就是连做三次：逆置前 p 个、逆置后 n − p 个、逆置全部（见第 9 篇 t1）。

类似题 ①：数组循环右移 k 位

题目：把 a[0..n−1] 循环右移 k 位（例如 1 2 3 4 5 6 7 右移 3 位得 5 6 7 1 2 3 4），要求空间 O(1)。思路：右移 k 位 = 后 k 个整体搬到前面。先整体逆置（7 6 5 4 3 2 1），再分别逆置前 k 个（5 6 7）和后 n − k 个（1 2 3 4）。

void RotateRight(int a[], int n, int k) {
    if (n == 0) return;
    k = k % n;                      // 右移 n 位等于没动
    Reverse(a, 0, n - 1);           // 整体逆置
    Reverse(a, 0, k - 1);           // 前 k 个再逆置
    Reverse(a, k, n - 1);           // 后 n-k 个再逆置
}

时间 O(n)、空间 O(1)。与 2010-42 循环左移对比：左移 p 位是“先分别逆置两段，再整体逆置”，两者只是三次逆置的分段位置不同。

基本功 ②：一趟扫描删除所有值为 x 的元素（“保留下来的往前放”）

void DelX(SqList &L, ElemType x) {
    int k = 0;                              // k：已经保留下来的元素个数
    for (int i = 0; i < L.length; i++)
        if (L.data[i] != x)
            L.data[k++] = L.data[i];        // 不是 x 就放到第 k 个位置
    L.length = k;
}

如果每遇到一个 x 就调用一次 ListDelete，每次都要移动后面所有元素，是 O(n²)；上面的写法每个元素最多移动一次，O(n)、O(1)。“把要保留的元素按顺序写回前面”这个思路也用于：删除有序表中的重复元素、删除值在 [s, t] 之间的元素、把数组按条件划分。

基本功 ② 的应用：删除重复元素

有序表：相同的元素一定挨在一起，只要和“已保留的最后一个”比较。

void DelDupSorted(SqList &L) {
    if (L.length == 0) return;
    int k = 1;                      // data[0..k-1] 是已保留的结果
    for (int i = 1; i < L.length; i++)
        if (L.data[i] != L.data[k - 1])   // 与已保留的最后一个不同才保留
            L.data[k++] = L.data[i];
    L.length = k;
}

void DelDupSortedList(LinkList L) {
    LNode *p = L->next, *q;
    if (p == NULL) return;
    while (p->next != NULL) {
        q = p->next;
        if (q->data == p->data) {   // 与 p 相同：删掉，p 不动
            p->next = q->next;  free(q);
        } else p = q;               // 不同：p 往后走
    }
}

上表是对 1 1 2 2 2 3 5 5 的跟踪。两种写法都是 O(n)、O(1)。

无序表（保留第一次出现的）：相同元素不一定挨着，有两种做法——

void DelDupUnsorted(SqList &L) {
    int k = 0;
    for (int i = 0; i < L.length; i++) {
        int j = 0;
        while (j < k && L.data[j] != L.data[i]) j++;  // 在已保留的里找
        if (j == k) L.data[k++] = L.data[i];          // 没找到：保留
    }
    L.length = k;
}

void DelDupFlag(SqList &L, int m) {
    int *flag = (int *)calloc(m + 1, sizeof(int));  // 全部置 0
    int k = 0;
    for (int i = 0; i < L.length; i++)
        if (!flag[L.data[i]]) {                     // 第一次见到
            flag[L.data[i]] = 1;
            L.data[k++] = L.data[i];
        }
    L.length = k;  free(flag);
}

四段代码均已编译，与“集合去重”的标准答案随机对拍 2 万组。右边就是基本功 ⑦“空间换时间”，2015-41 链表按绝对值去重是同一个思路。

类似题 ②：把所有 0 移到末尾

题目：数组中所有 0 移到末尾，非 0 元素保持原来的相对次序，空间 O(1)。例：0 3 0 5 7 0 2 → 3 5 7 2 0 0 0。思路：和 DelX 一模一样——“非 0 的往前放”，最后把剩下的位置补成 0。

void MoveZeros(int a[], int n) {
    int k = 0;
    for (int i = 0; i < n; i++)
        if (a[i] != 0) a[k++] = a[i];   // 非 0 的往前放
    while (k < n) a[k++] = 0;           // 剩下的位置补 0
}

O(n)、O(1)。若改成“奇数放前面、偶数放后面，且不要求保持次序”，用第 8 篇快排的“两端向中间交换”更省（见 8.5 划分的用法）。

基本功 ③：两个有序表的归并（双指针）

// 把有序数组 A[0..m-1]、B[0..n-1] 合并成有序数组 C
void Merge(int A[], int m, int B[], int n, int C[]) {
    int i = 0, j = 0, k = 0;
    while (i < m && j < n)                 // 两个都没取完：取较小者
        C[k++] = (A[i] <= B[j]) ? A[i++] : B[j++];
    while (i < m) C[k++] = A[i++];          // 剩下的直接照抄
    while (j < n) C[k++] = B[j++];
}

时间 O(m + n)，最多比较 m + n − 1 次。归并排序（第 8 篇）、2011-42 两序列中位数、2020-41 三元组最小距离，都是“多个有序序列，每次移动当前最小的那个指针”的变形。

基本功 ③ 的链表版：两个有序链表合并

LinkList MergeList(LinkList La, LinkList Lb) {   // 两个递增链表合并为递增链表，用原结点
    LNode *pa = La->next, *pb = Lb->next, *r = La; // r 指向结果表的表尾
    while (pa != NULL && pb != NULL) {
        if (pa->data <= pb->data) { r->next = pa; r = pa; pa = pa->next; }
        else { r->next = pb; r = pb; pb = pb->next; }
    }
    r->next = (pa != NULL) ? pa : pb;              // 剩下的整段接上，不用逐个处理
    free(Lb);                                      // Lb 的头结点不再需要
    return La;
}

La = 1 4 7、Lb = 2 3 8 9。和数组版相比，链表版不需要新空间：只是重新“穿针引线”，剩下的一段整体接上，O(1)。时间 O(m + n)。变式：要求合并成递减，就把“接到 r 后面”改成“头插到 La 之后”，最后剩下的那段也要逐个头插。

类似题 ③：两个有序数组的交集

题目：A、B 都严格递增，求公共元素。例：A = 1 3 4 6 9，B = 2 3 6 7 9 10 → 3 6 9。思路：两个指针比大小，小的那个不可能在另一边出现（另一边后面的只会更大），直接跳过；相等就是公共元素，两边一起走。

int Intersect(int A[], int m, int B[], int n, int C[]) {   // 返回交集元素个数
    int i = 0, j = 0, k = 0;
    while (i < m && j < n) {
        if (A[i] < B[j]) i++;
        else if (A[i] > B[j]) j++;
        else { C[k++] = A[i]; i++; j++; }
    }
    return k;
}

O(m + n)。暴力做法（对 A 的每个元素在 B 里找一遍）是 O(mn)——考场上写出暴力也能拿大部分分，但“有序”这个条件就是提示你用双指针。

基本功 ④：链表原地逆置（头插法）

void ReverseList(LinkList L) {              // L 带头结点
    LNode *p = L->next, *r;
    L->next = NULL;                         // 先把头结点摘下来，当成一个空表
    while (p != NULL) {
        r = p->next;                        // r 记住 p 的后继，防止断链
        p->next = L->next;                  // 把 p 头插到 L 之后
        L->next = p;
        p = r;
    }
}

另一种写法：三指针原地逆置

void Reverse3(LinkList L) {         // L 带头结点
    LNode *pre = NULL, *p = L->next, *r;
    while (p != NULL) {
        r = p->next;                // ① r 记住后继，防止断链
        p->next = pre;              // ② p 掉头指向前驱
        pre = p;  p = r;            // ③ 三个指针一起右移
    }
    L->next = pre;                  // ④ 头结点指向原来的尾结点
}

两种写法都已编译，与“数组倒过来”的结果随机对拍。

类似题 ④：只逆置第 m 到第 n 个结点

题目：带头结点的单链表，逆置第 m ~ n 个结点（1 ≤ m ≤ n ≤ 表长），其余不动。例：1 2 3 4 5 6 7，m = 2，n = 5 → 1 5 4 3 2 6 7。思路：找到第 m − 1 个结点 pre，把它当成“局部头结点”，对后面 n − m 个结点做头插。

void ReverseMN(LinkList L, int m, int n) {
    LNode *pre = L;
    for (int i = 1; i < m; i++) pre = pre->next;   // pre 指向第 m-1 个
    LNode *p = pre->next, *q;      // p 是第 m 个，逆置后它会成为这一段的最后一个
    for (int i = m; i < n; i++) {
        q = p->next;               // 把 p 后面的结点摘下
        p->next = q->next;
        q->next = pre->next;       // 头插到 pre 之后
        pre->next = q;
    }
}

跟踪：pre = 1，p = 2。第 1 次把 3 摘下插到 1 后：1 3 2 4 5 6 7；第 2 次摘 4：1 4 3 2 5 6 7；第 3 次摘 5：1 5 4 3 2 6 7。p 始终是 2，它一路被“挤”到这一段的末尾。O(n)、O(1)。

基本功 ⑤：快慢指针

LNode *slow = L, *fast = L;
while (fast != NULL && fast->next != NULL) {
    slow = slow->next;
    fast = fast->next->next;
}
// 快指针到尾时，slow 在中间

LNode *p = L->next, *q = L->next;
int cnt = 0;
while (p != NULL) {
    if (cnt < k) cnt++;      // p 先走 k 步
    else q = q->next;        // 之后 q 跟着走
    p = p->next;
}
// cnt < k：表长不足 k；否则 q 是倒数第 k 个

为什么快慢指针能找中点：fast 的速度是 slow 的 2 倍，同时出发，fast 走完全程时 slow 恰好走了一半。具体停在哪个结点要看循环条件：本书的写法（都从头结点出发，fast 能再走两步才继续）在 n = 6 时停在第 3 个、n = 7 时停在第 4 个，即第 ⌈n/2⌉ 个。2019-41 要把链表从中间断开，正好用“前半段最后一个”。

类似题 ⑤：判断链表有没有环，并找出环的入口

LNode *CycleEntry(LinkList L) {     // 有环返回入口，无环返回 NULL
    LNode *slow = L, *fast = L;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;  fast = fast->next->next;
        if (slow == fast) {         // 相遇：一定有环
            LNode *p = L;
            while (p != slow) { p = p->next; slow = slow->next; }   // 同速前进
            return p;               // 再次相遇处就是入口
        }
    }
    return NULL;
}

为什么第二阶段能在入口相遇：设 L 到入口 a 步，入口到相遇点 b 步，环长 c。相遇时 slow 走了 a + b，fast 走了 2(a + b)，多走的 a + b 恰是整数圈 kc，所以 a = kc − b：从相遇点再走 a 步，相当于绕整数圈再退回 b 步，正好停在入口。O(n)、O(1)。（对随机长度、随机入口的链表共 2 万组验证。）

基本功 ⑥：长度差对齐（找两链表的第一个公共结点）

两个单链表从某个结点开始合为一条（像字母 Y），后面部分完全共享。先各自求长度 m、n，让长的先走 |m − n| 步，然后两个指针同步前进，第一次指向同一个结点（比较的是指针，不是数据）时就是公共部分的起点。时间 O(m + n)，空间 O(1)。2012-42 共同后缀原题。

LNode *SearchCommon(LinkList A, LinkList B) {   // 带头结点，返回第一个公共结点（没有则 NULL）
    int m = Length(A), n = Length(B);            // Length 见 2.3 节
    LNode *p = A->next, *q = B->next;
    for (; m > n; m--) p = p->next;              // 长的先走 |m − n| 步
    for (; n > m; n--) q = q->next;
    while (p != q) { p = p->next; q = q->next; } // 同步前进，比较的是地址
    return p;
}

为什么先对齐：公共部分在两条链的尾部，长度相同。把长的那条多出来的头部跳过以后，两个指针离公共起点的距离就一样了，同步走必然同时到达。例：A = a1 a2 a3 c1 c2（长 5）、B = b1 c1 c2（长 3），p 先走 2 步到 a3，之后 p、q 同步：a3 与 b1 不同，c1 与 c1 相同，返回 c1。没有公共部分时两人同时走到 NULL，循环同样结束，返回 NULL。（代码与“构造好的公共部分”随机对拍 5 万组。）

类似题 ⑥：不求长度，找两链表的第一个公共结点

思路：设 A 独有部分长 a、B 独有部分长 b、公共部分长 c。指针 p 走完 A 再去走 B，q 走完 B 再去走 A：两人都走了 a + c + b 步后，正好同时到达公共部分的起点；没有公共部分时两人同时走到 NULL。

LNode *FirstCommon(LinkList A, LinkList B) {    // 带头结点
    LNode *p = A->next, *q = B->next;
    while (p != q) {                         // 比较的是地址，不是数据
        p = (p != NULL) ? p->next : B->next;  // 走完 A 就去走 B
        q = (q != NULL) ? q->next : A->next;  // 走完 B 就去走 A
    }
    return p;                                // 公共结点，或者 NULL
}

例：A 独有 a1 a2，B 独有 b1 b2 b3，公共 c1 c2 c3。p 依次经过 a1 a2 c1 c2 c3 (空) b1 b2 b3 c1，q 依次经过 b1 b2 b3 c1 c2 c3 (空) a1 a2 c1，第 10 个位置同时到 c1。和基本功 ⑥ 一样 O(m + n)、O(1)，只是不用先数长度。

基本功 ⑦：空间换时间（辅助数组做标记 / 计数）

当元素的取值范围已知且不大（例如 |data| ≤ n、值在 0 ~ n−1 之间），开一个大小为 n + 1 的数组 flag[]，用值当下标：flag[x] = 1 表示 x 出现过。这样“判断某个值是否出现过”只要 O(1)，整个算法一趟扫描 O(n)，空间 O(n)。2015-41 链表绝对值去重、2018-41 未出现的最小正整数、2013-41 主元素的计数解法都是它。

int FindDup(int a[], int n) {               // 返回一个重复的数
    int *flag = (int *)calloc(n, sizeof(int));   // flag[x] = 1 表示 x 出现过（calloc 自动清 0）
    int dup = -1;
    for (int i = 0; i < n; i++) {
        if (flag[a[i]]) { dup = a[i]; break; }   // 第二次见到 a[i]
        flag[a[i]] = 1;
    }
    free(flag);
    return dup;
}

类似题 ⑦：找出没出现的数

题目：n 个整数，每个都在 1 ~ n 之间（可能重复），找出 1 ~ n 中没出现的。例：n = 8，4 3 2 7 8 2 3 1 → 5 6。思路：值的范围已知且不大，开 flag[1..n] 做标记。

int Missing(int a[], int n, int out[]) {       // 返回没出现的个数，结果放在 out
    int *flag = (int *)calloc(n + 1, sizeof(int));
    for (int i = 0; i < n; i++) flag[a[i]] = 1; // 出现过就做标记
    int k = 0;
    for (int v = 1; v <= n; v++)
        if (!flag[v]) out[k++] = v;
    free(flag);
    return k;
}

O(n) 时间、O(n) 空间。2018-41“未出现的最小正整数”就是它的变形：只要输出第一个没被标记的数，值超出 1 ~ n 的直接忽略。

真题怎么考：线性表大题用到哪个基本功

完整解答、评分细则和“只会暴力解时怎么拿分”见第 9 篇 9.1、9.2。

2.6本篇总结：一页纸 + 必会题型

表 1：各操作的时间

表 2：判空条件

表 3：必会题型

2.✎本篇真题闯关（17 题）

本篇各小节挂的真题全部在这里，按小节排好。可以展开后一道道做，也可以用弹窗模式连续做。做题记录（对/错）只保存在你这台电脑的浏览器里，小节标题下的题号会随之变绿或变红。

本篇学完（勾选后目录打 ✓）

3.0本篇地图：四类固定题型

本篇 26 道选择题，几乎每年 2 道，而且题型极其固定：出栈序列、循环队列公式、中缀转后缀、特殊矩阵下标。每类都有“标准做法”，练熟了就是送分题。下表的真题数按“挂在哪一节”统计（一题可能同时挂两节）。

3.1栈：只能在一端进出的线性表

为什么要“限制”：栈在解决什么问题

先看几个生活里的例子。写文档时按 Ctrl + Z 撤销，撤销的总是最近一次的修改；浏览器点“后退”，回到的总是刚刚离开的那个页面；做数学题时遇到嵌套的括号，总是先算最里面那一层。它们有一个共同点：最后发生的事最先被处理。

如果用普通的线性表来记这些事，每次都要找到“最后一个”，还可能误删中间的；而栈干脆规定只能在一端操作，“最后一个”永远就在栈顶，O(1) 就能拿到，也不可能弄乱中间的次序。限制越少，能做的事越多，出错的机会也越多；栈用“只能在一端进出”换来了简单、安全、高效。本篇后面的括号匹配、表达式求值、函数调用，都是“后来的先处理”这一规律的应用。

栈是只允许在一端进行插入和删除的线性表。允许操作的一端叫栈顶，另一端叫栈底；插入叫进栈（入栈、压栈，Push），删除叫出栈（弹栈，Pop）。

顺序栈

#define MaxSize 50
typedef struct {
    ElemType data[MaxSize];
    int top;                    // 栈顶指针：栈顶元素的下标
} SqStack;

void InitStack(SqStack &S) { S.top = -1; }             // 空栈 top = -1
bool StackEmpty(SqStack S) { return S.top == -1; }

bool Push(SqStack &S, ElemType x) {
    if (S.top == MaxSize - 1) return false;            // 栈满
    S.data[++S.top] = x;                               // 先加 1，再放入
    return true;
}
bool Pop(SqStack &S, ElemType &x) {
    if (S.top == -1) return false;                     // 栈空
    x = S.data[S.top--];                               // 先取出，再减 1
    return true;
}

++S.top 和 S.top++ 的区别（C 语言基础）：S.data[++S.top] = x 是“先把 top 加 1，再用加过的 top 当下标”；x = S.data[S.top--] 是“先用当前的 top 当下标取数，取完再减 1”。前置 ++/−− 先改后用，后置 ++/−− 先用后改。把这两句拆开写就是 S.top = S.top + 1; S.data[S.top] = x; 和 x = S.data[S.top]; S.top = S.top - 1;，考场上拆开写更不容易错。

跟我做一遍：同一串操作，两种约定下 top 怎么变

跟我做一遍：用栈做进制转换

void Convert(int n, int b) {          // 把十进制正整数 n 转成 b 进制输出（2 ≤ b ≤ 10）
    int st[32], top = -1;             // 顺序栈
    while (n > 0) {
        st[++top] = n % b;            // 余数进栈：先得到的是最低位
        n /= b;
    }
    while (top >= 0) printf("%d", st[top--]);   // 出栈顺序 = 从最高位到最低位
}

共享栈：两个栈共用一个数组

省在哪里：两个栈各开 5 格，0 号栈要放 7 个、1 号栈只放 2 个——0 号栈第 6 个就上溢了，而 1 号栈还空着 3 格。共用 10 格的数组，7 + 2 = 9 个都放得下。两个栈的用量往往此消彼长（一个忙时另一个闲），共享就能“互相借地方”。代价是只适合两个栈：三个栈就没有第三个“端点”可以往里长了。

typedef struct { ElemType data[MaxSize]; int top0, top1; } ShStack;   // 初始 top0 = -1，top1 = MaxSize
bool Push(ShStack &S, int i, ElemType x) {   // i = 0 或 1：压入哪个栈
    if (S.top1 - S.top0 == 1) return false;   // 两个栈顶相邻：满
    if (i == 0) S.data[++S.top0] = x;         // 0 号栈往右长
    else        S.data[--S.top1] = x;         // 1 号栈往左长
    return true;
}
bool Pop(ShStack &S, int i, ElemType &x) {
    if (i == 0) { if (S.top0 == -1) return false;       x = S.data[S.top0--]; }
    else        { if (S.top1 == MaxSize) return false;  x = S.data[S.top1++]; }
    return true;
}

链栈

用单链表实现栈，表头作栈顶（在表头插入、删除都是 O(1)），通常不带头结点。进栈就是头插，出栈就是删除第一个结点。链栈的好处是不存在栈满上溢（只要内存够），便于多个栈共享存储空间。

typedef struct LinkNode { ElemType data; struct LinkNode *next; } LinkNode, *LiStack;
void InitStack(LiStack &S) { S = NULL; }           // 不带头结点：空栈就是 NULL
bool StackEmpty(LiStack S) { return S == NULL; }
void Push(LiStack &S, ElemType x) {                // 头插：新结点成为栈顶
    LinkNode *p = (LinkNode *)malloc(sizeof(LinkNode));
    p->data = x;  p->next = S;  S = p;
}
bool Pop(LiStack &S, ElemType &x) {                // 删除第一个结点
    if (S == NULL) return false;
    LinkNode *p = S;  x = p->data;  S = S->next;  free(p);
    return true;
}

为什么栈顶放在表头而不放表尾：出栈要删除栈顶，删表尾结点得先找它的前驱，O(n)；删表头 O(1)。所以链栈的进出都在表头做。

链栈若带头结点，栈顶是头结点后面的第一个结点，空栈条件变成 S->next == NULL，代码多一层“->next”。408 默认不带头结点，题目说明了就按题目来。

选择题变式：真题换个条件再做一遍

每道题都由一道真题改动一两个条件而来。先做本节的真题，再做这里的变式，最后看“变化点”：改了什么、答案为什么跟着变。

3.2出栈序列：判断合法性与计数（卡特兰数）

元素按固定顺序进栈，但进栈和出栈可以交替进行，于是出栈序列有很多种可能。这类题每年几乎必出一道，有三种问法：判断某个序列是否可能、求栈的最小容量、数有多少种可能。

方法一：模拟（万能）

对要检验的出栈序列，从左到右依次处理每个要输出的元素 x：

1. 如果 x 还没进栈：把输入序列中 x 之前（含 x）还没进栈的元素全部依次进栈，然后弹出 x。
2. 如果 x 已经在栈里：它必须正好在栈顶，弹出；如果不在栈顶，这个序列就不可能。

同时记录栈中元素个数的最大值，就是栈的最小容量。

方法二：看“三元组”规律（秒杀）

用它检验 3, 1, 2, 5, 4：3 后面比 3 小的是 1, 2，是升序 ⇒ 不可能。2026-42 第 (2) 问考的就是这个结论。

跟我做一遍：栈至少要多大

已知前几个出栈元素，下一个可能是谁

原则只有一句：下一个出栈的，要么是当前栈顶，要么是还没进栈的元素（先把它前面的都压进去，再弹出它）。栈顶以下的元素被压着，一个也出不来。

计数：n 个元素有多少种出栈序列

递推式是怎么来的：按“元素 1 是第几个出栈的”分类。若 1 是第 k 个出栈的，那么在它之前出栈的恰好是 2, 3, …, k 这 k − 1 个元素（它们在 1 上面进栈，必须在 1 出栈前全部出完），它们之间的出栈方式有 C_k−1 种；1 出栈后栈空了，剩下的 k + 1, …, n 这 n − k 个元素重新开始，有 C_n−k 种。两边独立，相乘再按 k 加起来。n = 3：1 第 1 个出栈 C₀C₂ = 2 种，第 2 个 C₁C₁ = 1 种，第 3 个 C₂C₀ = 2 种，共 5 种；n = 4：5 + 2 + 2 + 5 = 14。（程序对 n = 3、4、5 按 1 的位置分类计数核对。）

为什么是卡特兰数：每种出栈序列对应一个由 n 次 Push、n 次 Pop 组成的操作串，要求任何前缀里 Pop 的次数都不超过 Push 的次数。这样的串的个数就是 Cₙ。同样的数也出现在“n 个结点的不同二叉树的个数”（5.5 节，2015-02）、“先序序列固定的二叉树个数”等问题里。

为什么这些问题的答案都一样：它们都能和“n 对括号的合法排列”一一对应。进栈记成“(”、出栈记成“)”，合法的操作串就是一串配得上的括号；给定先序序列的二叉树，用“进入一个结点 / 离开一个结点”也能写成一串括号。只要两个问题之间能建立一一对应，答案的个数就一定相同——这是数学里证明计数问题最常用的办法，上面的翻折法也是这个思路。

为什么是 C(2n, n)/(n + 1)：翻折法

把一次进栈画成“往右上走一步”（U），一次出栈画成“往右下走一步”（D）。n 个元素全部进出一次，就是一条从高度 0 出发、走 2n 步、回到高度 0 的折线。合法的要求是：任何时刻出栈次数不超过进栈次数，即折线从不低于 0。

1. 全部折线：2n 步里挑 n 步向上，共 C(2n, n) 条。
2. 不合法的折线一定在某一刻第一次碰到 −1。把这一刻之后的每一步上下颠倒，终点从 0 变成 −2；反过来，任何一条终点为 −2 的折线都必然碰过 −1，再翻回去就得到一条不合法折线。所以“不合法折线”和“终点为 −2 的折线”一一对应。
3. 终点为 −2 的折线有 n − 1 步向上、n + 1 步向下，共 C(2n, n + 1) 条。
4. 合法的 = C(2n, n) − C(2n, n + 1)。因为 C(2n, n + 1) = C(2n, n) × n/(n + 1)，所以结果是 C(2n, n)/(n + 1)。

n = 3：全部 20 条，不合法 C(6, 4) = 15 条，合法 5 条，正是 C₃ = 5。（程序对 n = 1 ~ 8 穷举全部折线，确认“不合法数 = C(2n, n + 1)”且翻折是一一对应。）

五类题型一张表

以上数字全部由程序枚举所有出栈序列统计；并验证了“312 规则”与模拟法对 n ≤ 7 的全部排列判断一致。

真题怎么考

• 某个序列能不能得到（2010-01 附加了“不允许连续三次退栈”、2022-02 问输入输出排列的一般性质）：模拟法最稳，312 规则最快。但附加了操作限制时只能模拟——312 规则只回答“栈能不能做到”，管不了“连续出栈几次”这类限制。
• 栈的最小容量（2009-02，栈和队列配合）：先看清“出队顺序 = 出栈顺序”（每个元素出栈后立即进队），再像上面那样数“输出前”栈里有几个。
• 计数（2011-02 以某元素开头、2013-02 已知 p₂ 求 p₃ 的可能个数）：画出“此刻栈里有谁、谁在栈顶、谁还没进栈”，用“栈顶或未进栈”的原则数；问总数时用卡特兰数。
• 给出操作串求输出（2020-02 给出 Push / Pop 的次序）：照着操作逐个执行，Pop 弹出的是栈顶，不是最早进栈的那个。
• 栈与队列组合（2018-02：队头元素可以直接输出，也可以先进栈）：相当于“一个栈 + 一条可以直接输出的通道”，逐个选项模拟。
• 大题（2026-42）：出栈序列合法的条件与计数，第 9 篇 t8 有完整解答。

选择题变式：真题换个条件再做一遍

每道题都由一道真题改动一两个条件而来。先做本节的真题，再做这里的变式，最后看“变化点”：改了什么、答案为什么跟着变。

3.3队列与循环队列

为什么需要队列：栈处理的是“最近的先办”，可很多事情讲究公平——先来的先办。打印店接了一串打印任务，总该按交来的先后打；网卡收到的数据包，要按到达的先后交给程序；操作系统里排队等 CPU 的进程，最朴素的规则也是先来先服务。这些场景只需要“在一头加、在另一头取”，队列就是为它们量身定做的。哪里不像：食堂排队可以有人插队、中途离开，队列不行——除了队头，谁也不能出来。

队列是只允许在一端插入（队尾 rear，入队 EnQueue）、在另一端删除（队头 front，出队 DeQueue）的线性表。操作系统中打印机的缓冲区、进程的就绪队列、树的层次遍历、图的广度优先搜索都用队列。

顺序队列的“假溢出”

用数组存队列，front 指向队头元素，rear 指向队尾元素的下一个位置。入队 Q.data[Q.rear++] = x，出队 x = Q.data[Q.front++]。问题是 front 和 rear 只增不减：出队后前面空出来的位置再也用不上，rear 到了数组末尾就无法入队，尽管数组前面还有空位——这叫假溢出。

循环队列：把数组首尾接起来

bool EnQueue(SqQueue &Q, ElemType x) {
    if ((Q.rear + 1) % MaxSize == Q.front) return false;   // 队满
    Q.data[Q.rear] = x;
    Q.rear = (Q.rear + 1) % MaxSize;                       // 队尾指针后移，到末尾就绕回 0
    return true;
}
bool DeQueue(SqQueue &Q, ElemType &x) {
    if (Q.front == Q.rear) return false;                   // 队空
    x = Q.data[Q.front];
    Q.front = (Q.front + 1) % MaxSize;
    return true;
}

补课：取模怎样让下标“绕回来”

元素个数公式为什么要“+ M”：队列绕了一圈以后，可能出现 rear < front。例如 M = 6、front = 4、rear = 1，队中的元素在 4、5、0 号单元，共 3 个。直接算 rear − front = −3，不对；加上一圈的长度 M：−3 + 6 = 3 ✓。而 rear ≥ front 时，加了 M 会多出一圈，再 % M 去掉。所以 (rear − front + M) % M 两种情况都对。

还有一个只在 C 语言里才有的坑：C 的 % 对负数的结果带负号，(1 − 4) % 6 在 C 里得 −3，不是数学上的 3。所以代码里必须写成 (rear − front + M) % M，先把它变成非负数再取模；省掉 + M 的写法在 rear < front 时会算出负数。（两种写法的差别由程序按 C 的取模规则核对。）

四种约定的公式对照表（M = MaxSize）

记法：约定④只是把①的 rear 整体往回挪了一格，所以①里出现 rear 的地方都换成 rear + 1。（四种写法都已编成代码，与一个“标准队列”模型随机对拍 2 万组，含队空、队满边界。）

跟我做一遍：M = 6 的循环队列

链队列

用带头结点的单链表，front 指向头结点，rear 指向最后一个结点。入队在 rear 后面插入；出队删除头结点后的第一个结点。

typedef struct LinkNode { ElemType data; struct LinkNode *next; } LinkNode;
typedef struct { LinkNode *front, *rear; } LinkQueue;

void EnQueue(LinkQueue &Q, ElemType x) {
    LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
    s->data = x;  s->next = NULL;
    Q.rear->next = s;  Q.rear = s;
}
bool DeQueue(LinkQueue &Q, ElemType &x) {
    if (Q.front == Q.rear) return false;          // 队空
    LinkNode *p = Q.front->next;
    x = p->data;
    Q.front->next = p->next;
    if (Q.rear == p) Q.rear = Q.front;            // 删的是最后一个元素：rear 要退回头结点
    free(p);
    return true;
}

不带头结点时，front、rear 都直接指向数据结点，空队列时两者都是 NULL。入队、出队都要多处理一种情况：

void EnQueue(LinkQueue &Q, ElemType x) {          // 不带头结点
    LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
    s->data = x;  s->next = NULL;
    if (Q.front == NULL) { Q.front = Q.rear = s; }   // 空队列：新结点既是队头也是队尾
    else { Q.rear->next = s;  Q.rear = s; }
}
bool DeQueue(LinkQueue &Q, ElemType &x) {
    if (Q.front == NULL) return false;
    LinkNode *p = Q.front;  x = p->data;
    Q.front = p->next;
    if (Q.rear == p) Q.rear = NULL;                   // 删的是最后一个：队列变空
    free(p);  return true;
}