📖 数据结构（Data Structure）—— 408考研完全笔记

编写说明：本笔记严格依据全国硕士研究生招生考试计算机学科专业基础（科目代码：408/11408）考试大纲编写，结合王道考研教材体系与历年真题，力求概念严谨、解释通俗、解题实用。

考试概况：408统考满分150分，考试时间180分钟（3小时）。其中数据结构约占45分（30%），计算机组成原理约占45分（30%），操作系统约占35分（约23%），计算机网络约占25分（约17%）。题型包括：单项选择题（80分，40题×2分） 和 综合应用题（70分，7题）。数据结构通常占约10道选择题（20分）和2道大题（约25分）。

---

第一章 绪论

1.1 数据结构的基本概念

一、核心定义

数据（Data）：信息的载体，是对客观事物符号化的表示，能够被计算机识别、存储和加工处理。

🗣️ 大白话：数据就是计算机能认识的东西。你的名字、年龄、一张照片、一段视频，只要能存进电脑里的，都叫数据。

数据元素（Data Element）：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项（Data Item） 组成，数据项是构成数据元素的不可分割的最小单位。

🗣️ 大白话：好比一个学生信息表，每一行（一个学生的全部信息）就是一个数据元素，而"姓名""学号""成绩"这些列就是数据项。数据项是最小的，不能再拆了。

数据对象（Data Object）：性质相同的数据元素的集合，是数据的一个子集。

数据结构（Data Structure）：相互之间存在一种或多种特定关系的数据元素的集合。包含三个方面：

方面	含义	说明
逻辑结构	数据元素之间的逻辑关系	与存储无关，是从逻辑上描述数据
存储结构（物理结构）	数据结构在计算机中的表示	逻辑结构在计算机内存中的映像
数据的运算	施加在数据上的操作	运算的定义针对逻辑结构，实现针对存储结构

二、逻辑结构的分类

逻辑结构
├── 线性结构：元素之间是一对一的关系（如线性表、栈、队列）
└── 非线性结构
    ├── 集合结构：元素之间除"属于同一集合"外无其他关系
    ├── 树形结构：元素之间是一对多的关系（如二叉树、B树）
    └── 图状结构（网状结构）：元素之间是多对多的关系（如有向图、无向图）

🗣️ 大白话：

• 线性结构就像排队——每个人前面最多一个人，后面也最多一个人，一条线串起来。
• 树形结构就像家族族谱——一个爷爷可以有好几个儿子，但每个人只有一个亲爹。
• 图状结构就像微信朋友圈——你认识我，我认识他，他也可能认识你，关系错综复杂。
• 集合结构就像一筐苹果——它们之间没啥特别关系，只是放在了一起。

三、存储结构的四种基本方式

存储方式	特点	典型应用
顺序存储	逻辑上相邻的元素物理上也相邻，用一组连续的存储单元	数组、顺序表
链式存储	不要求物理相邻，通过指针表示逻辑关系	链表
索引存储	在存储元素信息的同时，建立附加的索引表	索引文件
散列存储	根据元素的关键字直接计算出存储地址	散列表（Hash表）

🗣️ 大白话：

• 顺序存储：就像图书馆的书架，书按编号挨个排好，找第5本直接数到第5个位置。
• 链式存储：就像寻宝游戏，每本书里夹了一张纸条，告诉你下一本书在哪。
• 索引存储：就像书的目录，先查目录找到页码，再翻到那一页。
• 散列存储：就像按名字首字母分类放东西，姓"张"的放到Z区，直接去那个区找。

四、数据类型与抽象数据类型

数据类型（Data Type）：一个值的集合和定义在此集合上的一组操作的总称。

抽象数据类型（ADT, Abstract Data Type）：一个数学模型以及定义在该模型上的一组操作。ADT的定义仅取决于它的一组逻辑特性，与其在计算机内部的表示和实现无关。

🗣️ 大白话：ADT就是"你只管用，不用管我怎么做到的"。就像你用手机打电话，你只知道拨号就能打通，至于信号怎么传输的你不需要管——这就是"抽象"。

---

1.2 算法与算法评价

一、算法的基本概念

算法（Algorithm）：对特定问题求解步骤的一种描述，是指令的有限序列。

算法的五个重要特性：

特性	含义	说明
有穷性	算法必须在执行有穷步之后结束，且每一步都在有穷时间内完成	程序可以不满足（如操作系统）
确定性	每条指令必须有确切含义，不产生二义性	相同输入只能得到相同输出
可行性	算法中的操作都可以通过已实现的基本运算执行有限次来实现	—
输入	零个或多个输入	可以没有输入
输出	一个或多个输出	必须有输出

⚠️ 考研高频考点：算法与程序的区别——算法必须是有穷的，而程序可以是无穷的（如操作系统是一直运行的程序）。

"好"算法的评价标准：

1. 正确性：能正确解决问题
2. 可读性：易于阅读理解
3. 健壮性：能对非法输入做出适当反应
4. 效率与低存储量：时间复杂度低、空间复杂度低

二、时间复杂度

定义：算法中基本操作的执行次数 $T(n)$ 是问题规模 $n$ 的函数，取 $T(n)$ 的数量级（最高阶项），记作：

$T(n) = O(f(n))$

表示当 $n$ 趋于无穷大时，$T(n)$ 的增长率与 $f(n)$ 的增长率相同。

常见时间复杂度排序（从低到高）：

$O(1) < O(\log_2 n) < O(\sqrt{n}) < O(n) < O(n\log_2 n) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)$

📝 记忆口诀："常对根线，线对平立，指阶阶阶"——常数、对数、根号、线性、线性对数、平方、立方、指数、阶乘。简化记为"常对幂指阶"（常数 < 对数 < 幂函数 < 指数函数 < 阶乘）。

⚠️ 注意 $O(\sqrt{n}) = O(n^{0.5})$ 介于 $O(\log n)$ 和 $O(n)$ 之间，考研真题偶尔出现。

🗣️ 大白话：时间复杂度就是衡量"当数据量变大时，算法变慢的速度"。$O(1)$ 意味着不管数据多少，速度都一样快（比如查数组的第k个元素）；$O(n)$ 意味着数据翻倍，时间也翻倍（比如遍历数组）；$O(n^2)$ 意味着数据翻倍，时间变4倍（比如冒泡排序）。

三种复杂度：

• 最坏时间复杂度：最不利情况下的时间复杂度（考研默认分析这个）
• 平均时间复杂度：所有可能输入的平均时间
• 最好时间复杂度：最理想情况下的时间复杂度（一般不讨论）

常见代码的时间复杂度分析方法：

// O(1) —— 常数阶
int x = 1;
int y = x + 1;

// O(n) —— 线性阶
for (int i = 0; i < n; i++)
    x++;

// O(n²) —— 平方阶
for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        x++;

// O(log₂n) —— 对数阶
while (n > 1)
    n = n / 2;

// O(n·log₂n) —— 线性对数阶
for (int i = 0; i < n; i++)
    for (int j = 1; j < n; j = j * 2)
        x++;

// O(1) —— 常数阶
int x = 1;
int y = x + 1;

// O(n) —— 线性阶
for (int i = 0; i < n; i++)
    x++;

// O(n²) —— 平方阶
for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        x++;

// O(log₂n) —— 对数阶
while (n > 1)
    n = n / 2;

// O(n·log₂n) —— 线性对数阶
for (int i = 0; i < n; i++)
    for (int j = 1; j < n; j = j * 2)
        x++;

三、空间复杂度

定义：算法所需存储空间 $S(n)$ 关于问题规模 $n$ 的数量级，记作：

$S(n) = O(g(n))$

⚠️ 注意：空间复杂度只计算算法额外使用的辅助空间，不包括输入数据本身占用的空间。

算法原地工作：指算法所需的辅助空间为常量，即 $S(n) = O(1)$。

🗣️ 大白话：空间复杂度就是你算法运行时"额外"需要多少空间。就像你收拾房间，你已有的东西不算，你额外需要买几个收纳箱——那就是空间复杂度。如果不需要额外买箱子就能搞定（原地工作），那就是 $O(1)$。

📝 真题剖析

【2011年408真题】 设 $n$ 是描述问题规模的非负整数，下面程序段的时间复杂度是（）。

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

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

A. $O(\log_2 n)$   B. $O(n)$   C. $O(n\log_2 n)$   D. $O(n^2)$

解题方法：

设循环执行 $t$ 次。每次 $x$ 变为 $2x$，初始 $x=2$。

• 第1次后：$x = 2 \times 2 = 4 = 2^2$
• 第2次后：$x = 2 \times 4 = 8 = 2^3$
• 第 $t$ 次后：$x = 2^{t+1}$

循环结束条件：$2^{t+1} \geq n/2$，即 $t+1 \geq \log_2(n/2) = \log_2 n - 1$

所以 $t = O(\log_2 n)$。答案选A。

💡 解题套路：看到变量成倍增长（$x = 2x$）或成倍缩减（$n = n/2$），八成就是 $O(\log n)$ 级别。

【2012年408真题】 求 $n!$ 的递归算法（fact(n)），其时间复杂度为（）。

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

A. $O(\log_2 n)$   B. $O(n)$   C. $O(n\log_2 n)$   D. $O(n^2)$

解：递推关系 $T(n) = T(n-1) + O(1)$（$n>1$），$T(1) = O(1)$。展开得 $T(n) = O(n)$。答案选B。

💡 递归时间复杂度分析套路：列出递推关系式，展开或用主定理求解。每层递归只做 $O(1)$ 工作、递归 $n$ 层 → $O(n)$。

【递归复杂度分析利器——主定理（Master Theorem）简化版】

对于形如 $T(n) = aT(n/b) + O(n^d)$ 的递推关系（$a \geq 1, b > 1, d \geq 0$）：

条件	结论	记忆
$a < b^d$（子问题增长慢于合并代价）	$T(n) = O(n^d)$	合并代价主导
$a = b^d$	$T(n) = O(n^d \log n)$	各层均等，乘以层数
$a > b^d$（子问题增长快于合并代价）	$T(n) = O(n^{\log_b a})$	叶子数量主导

常考实例：

递推关系	$a$	$b$	$d$	比较	复杂度
$T(n) = 2T(n/2) + O(n)$（归并排序）	2	2	1	$a = b^d$	$O(n \log n)$
$T(n) = 2T(n/2) + O(1)$（遍历二叉树）	2	2	0	$a > b^d$	$O(n^{\log_2 2}) = O(n)$
$T(n) = T(n/2) + O(1)$（折半查找）	1	2	0	$a = b^d$	$O(\log n)$
$T(n) = 2T(n/4) + O(1)$	2	4	0	$a > b^d$	$O(n^{\log_4 2}) = O(\sqrt{n})$
$T(n) = T(n-1) + O(1)$	—	—	—	不适用主定理（非 $n/b$ 形式），直接展开得 $O(n)$

⚠️ 注意：主定理仅适用于"规模缩小为 $n/b$"的递推关系。如 $T(n) = T(n-1) + O(n)$（如选择排序的递归版）属于递减型递推，需直接展开：$T(n) = n + (n-1) + \cdots + 1 = O(n^2)$。

【摊还分析（Amortized Analysis）——高级复杂度分析】

某些操作的单次最坏代价很高，但连续多次操作的平均代价很低。摊还分析给出的是操作序列的平均上界，比最坏情况分析更精确。

方法	思想	典型应用
聚合分析	计算 $n$ 次操作的总代价 $T(n)$，摊还代价 $= T(n)/n$	动态数组扩容
核算法	为"便宜操作"多收费存为"信用"，"贵操作"用信用支付	栈的 multipop
势能法	定义势函数 $\Phi$，摊还代价 $= c_i + \Phi_i - \Phi_{i-1}$	并查集、Splay树

🗣️ 大白话：就像你每月存100块钱，到年底一次性花1200修车。每次花钱看起来很"便宜"（月均100），但修车那次本身花了1200。摊还分析就是把1200分摊到12个月来看。

典型例子——动态数组扩容：顺序表满了就翻倍扩容，扩容时复制所有元素代价为 $O(n)$。但从空开始连续插入 $n$ 个元素，扩容总代价为 $1+2+4+\cdots+n = O(n)$。因此每次插入的摊还代价为 $O(1)$，而非最坏的 $O(n)$。

考试关键：并查集使用按秩合并 + 路径压缩后，$m$ 次操作的总代价为 $O(m \cdot \alpha(n))$，其中 $\alpha(n)$ 是反阿克曼函数（增长极慢，对所有实际情况 $\alpha(n) \leq 4$）。因此单次操作的摊还代价近似 $O(1)$。

【2017年408真题】 下面程序段的时间复杂度是（）。

int sum = 0, i = 1;
while (sum < n)
    sum += ++i;

A. $O(\log n)$   B. $O(\sqrt{n})$   C. $O(n)$   D. $O(n\log n)$

解：设循环执行 $t$ 次，则 $sum = 2+3+\cdots+(t+1) = \frac{(t+1)(t+2)}{2} - 1$。当 $sum \geq n$ 时结束，即 $t^2/2 \approx n$，解得 $t \approx \sqrt{2n}$。答案选B。

💡 解题套路：当累加和与 $n$ 比较时，累加量递增形成等差数列求和 → $O(\sqrt{n})$。

【2025年408真题】 下面程序段的时间复杂度是（）。

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

A. $O(\log n)$   B. $O(n)$   C. $O(n\log n)$   D. $O(n^2)$

解：外层循环 $i$ 从1到 $\sqrt{n}$，内层循环 $j$ 从1到 $i$。总执行次数 $T(n) = \sum_{i=1}^{\sqrt{n}} i = \frac{\sqrt{n}(\sqrt{n}+1)}{2} \approx \frac{n}{2}$。答案选B，$O(n)$。

⚠️ $\sqrt{n}$ 相关的时间复杂度是近年真题高频考点！ 常见模式：

• 循环条件含 i*i<=n 或 sum<n（sum等差递增）→ $O(\sqrt{n})$ 或 $O(n)$
• 2019真题：条件 n>=(x+1)*(x+1) 同理 → $O(\sqrt{n})$

【2014年408真题】 下面程序段的时间复杂度是（）。

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

A. $O(n)$   B. $O(n\log_2 n)$   C. $O(n^2)$   D. $O(n^2 \log_2 n)$

解：外层 $k$ 每次乘2，执行 $\log_2 n$ 次；内层 $j$ 每次执行 $n$ 次。总次数 $= n \cdot \log_2 n$。答案选B。

💡 解题套路：外层"乘2"→ $\log n$ 次；内层"加1"→ $n$ 次。相乘即得 $O(n\log n)$。

【2019年408真题】 下面程序段的时间复杂度是（）。

int x = 0;
while (n >= (x + 1) * (x + 1))
    x++;

A. $O(\log n)$   B. $O(\sqrt{n})$   C. $O(n)$   D. $O(n^2)$

解：循环执行 $t$ 次后 $x = t$，退出条件 $n < (t+1)^2$，即 $t \geq \lfloor\sqrt{n}\rfloor$，所以 $T(n) = O(\sqrt{n})$。答案选B。

💡 解题套路：循环条件含 $(x+1)^2 \leq n$，等价于 $x$ 从0增长到 $\sqrt{n}$，时间复杂度为 $O(\sqrt{n})$。

【2022年408真题】 下面程序段的时间复杂度是（）。

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

A. $O(\log_2 n)$   B. $O(n)$   C. $O(n\log_2 n)$   D. $O(n^2)$

解：外层 $i = 1, 2, 4, \ldots, 2^k$（其中 $2^k \leq n$），内层执行 $i$ 次。总次数：

$T(n) = 1 + 2 + 4 + \cdots + 2^k = 2^{k+1} - 1 \approx 2n - 1$

这是等比数列求和，结果为 $O(n)$。答案选B。

⚠️ 易错点：不要想当然地认为"外层 $\log n$ × 内层 $n$"就是 $O(n\log n)$。内层循环次数随外层变化（$j \leq i$，不是 $j \leq n$），必须用等比求和精确计算。这是区分 $O(n)$ 和 $O(n\log n)$ 的高频陷阱！

📌 第一章总结

核心知识点	考研要求
数据、数据元素、数据项、数据对象的概念层次	理解概念，区分层次
逻辑结构四种类型（集合、线性、树形、图状）	必须牢记
存储结构四种方式（顺序、链式、索引、散列）	必须牢记，理解各自特点
算法五大特性（有穷、确定、可行、输入、输出）	必须牢记，区分算法与程序
时间复杂度分析	重点！ 必须会分析代码的时间复杂度
常见复杂度大小排序	必须牢记 $O(1)<O(\log n)<O(n)<O(n\log n)<O(n^2)<O(n^3)<O(2^n)<O(n!)$
空间复杂度分析	理解概念，注意"原地工作"含义

---

第二章 线性表

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

一、线性表的定义

线性表（Linear List）：具有相同数据类型的 $n$（$n \geq 0$）个数据元素的有限序列，其中 $n$ 为表长，当 $n=0$ 时称为空表。记作：

$L = (a_1, a_2, \ldots, a_i, \ldots, a_n)$

• $a_1$ 是表头元素，$a_n$ 是表尾元素
• $a_{i-1}$ 是 $a_i$ 的直接前驱，$a_{i+1}$ 是 $a_i$ 的直接后继
• 除表头元素外，每个元素有且仅有一个直接前驱
• 除表尾元素外，每个元素有且仅有一个直接后继

🗣️ 大白话：线性表就是一排相同类型的东西排成一条线。就像食堂排队，每个人前面最多一个人（前驱），后面最多一个人（后继），第一个人没有前驱（他就是排头），最后一个人没有后继（他最后一个）。

线性表的特点：

1. 表中元素个数有限
2. 表中元素具有逻辑上的顺序性，有先后次序
3. 表中元素都是数据元素，每个元素都是单个元素
4. 表中元素的数据类型都相同，每个元素占有相同大小的存储空间
5. 表中元素具有抽象性（仅讨论逻辑关系，不考虑元素具体表示什么）

二、线性表的基本操作（9大操作）

操作	功能
InitList(&L)	初始化表，构造一个空的线性表
Length(L)	求表长，返回线性表的长度（元素个数）
LocateElem(L, e)	按值查找，在表中查找具有给定值的元素
GetElem(L, i)	按位查找，获取表中第 i 个位置的元素的值
ListInsert(&L, i, e)	插入操作，在第 i 个位置上插入元素 e
ListDelete(&L, i, &e)	删除操作，删除第 i 个位置的元素，并返回其值
PrintList(L)	输出操作，按前后顺序输出线性表所有元素值
Empty(L)	判空操作，判断线性表是否为空表
DestroyList(&L)	销毁操作，销毁线性表，释放内存空间

⚠️ 注意：& 表示C++中的引用，意味着函数内部对参数的修改会影响到实参。在C语言中需要使用指针实现。

---

2.2 顺序表（Sequential List）

一、顺序表的定义

顺序表：用顺序存储方式实现的线性表。把逻辑上相邻的元素存储在物理上也相邻的一组连续存储单元中。

随机存取特性：第 $i$ 个元素的地址为：

$LOC(a_i) = LOC(a_1) + (i-1) \times sizeof(ElemType)$

🗣️ 大白话：顺序表就是用数组存的线性表。就像宾馆房间号是连续的，知道1号房的位置和房间大小，就能直接算出第100号房的位置，不需要一个一个去找——这就是"随机存取"（也叫"直接存取"）。

🔗 【跨学科联动·计组】 顺序表的「随机存取」对应计组中 RAM（随机存取存储器） 的概念——给定地址即可在 $O(1)$ 时间内读写。上述地址计算公式本质上就是计组中「基址 + 偏移量」的寻址方式。数组在内存中按行优先或列优先存储的规则也与计组中的存储器编址方式直接相关。

静态分配 vs 动态分配：

// 静态分配：数组大小固定，一旦满了就溢出
#define MaxSize 50
typedef struct {
    ElemType data[MaxSize];  // 静态数组
    int length;
} SqList;

// 动态分配：空间不足时可以重新分配更大的空间
typedef struct {
    ElemType *data;   // 动态数组的指针
    int MaxSize;
    int length;
} SeqList;

// 静态分配
class SqList {
    static final int MaxSize = 50;
    int[] data = new int[MaxSize];  // 静态数组
    int length;
}

// 动态分配（Java中用ArrayList更常见）
class SeqList {
    int[] data;    // 动态数组
    int maxSize;
    int length;
    SeqList(int initSize) {
        data = new int[initSize];
        maxSize = initSize;
        length = 0;
    }
}

二、顺序表的基本操作

1. 插入操作

在第 $i$ 个位置（$1 \leq i \leq n+1$）插入元素 $e$，需要将第 $i$ 个及之后的元素后移一位。

bool ListInsert(SqList &L, int i, ElemType e) {
    if (i < 1 || i > L.length + 1)  return false;  // 判断i的范围是否有效
    if (L.length >= MaxSize)  return false;          // 存储空间已满
    for (int j = L.length; j >= i; j--)              // 将第i个及之后元素后移
        L.data[j] = L.data[j-1];
    L.data[i-1] = e;   // 在位置i处放入e
    L.length++;
    return true;
}

boolean listInsert(SqList L, int i, int e) {
    if (i < 1 || i > L.length + 1) return false;
    if (L.length >= SqList.MaxSize) return false;
    for (int j = L.length; j >= i; j--)
        L.data[j] = L.data[j - 1];
    L.data[i - 1] = e;
    L.length++;
    return true;
}

时间复杂度分析：

• 最好情况：在表尾插入（$i = n+1$），无需移动元素，$O(1)$
• 最坏情况：在表头插入（$i = 1$），需移动 $n$ 个元素，$O(n)$
• 平均情况：移动 $n/2$ 个元素，$O(n)$

2. 删除操作

删除第 $i$ 个位置（$1 \leq i \leq n$）的元素，需要将第 $i+1$ 个及之后的元素前移一位。

bool ListDelete(SqList &L, int i, ElemType &e) {
    if (i < 1 || i > L.length)  return false;  // 判断i的范围是否有效
    e = L.data[i-1];       // 将被删元素赋值给e
    for (int j = i; j < L.length; j++)   // 将第i个位置后的元素前移
        L.data[j-1] = L.data[j];
    L.length--;
    return true;
}

boolean listDelete(SqList L, int i, int[] e) {
    if (i < 1 || i > L.length) return false;
    e[0] = L.data[i - 1];  // Java用数组模拟引用传参
    for (int j = i; j < L.length; j++)
        L.data[j - 1] = L.data[j];
    L.length--;
    return true;
}

时间复杂度分析：

• 最好情况：删除表尾元素，$O(1)$
• 最坏情况：删除表头元素，$O(n)$
• 平均情况：$O(n)$

3. 查找操作

按位查找：$O(1)$（随机存取）

ElemType GetElem(SqList L, int i) {
    return L.data[i-1];  // 直接通过下标访问
}

int getElem(SqList L, int i) {
    return L.data[i - 1];  // 直接通过下标访问
}

按值查找（顺序查找）：$O(n)$

int LocateElem(SqList L, ElemType e) {
    for (int i = 0; i < L.length; i++)
        if (L.data[i] == e)  return i + 1;  // 返回位序（从1开始）
    return 0;  // 查找失败
}

int locateElem(SqList L, int e) {
    for (int i = 0; i < L.length; i++)
        if (L.data[i] == e) return i + 1;
    return 0;
}

三、顺序表的特点总结

优点	缺点
随机存取，$O(1)$ 时间按位查找	插入、删除需要移动大量元素
存储密度高（不需要额外指针空间）	需要预先分配连续空间，不够灵活
—	表的容量难以确定

🔗 【跨学科联动·计组/OS】 顺序表对应计组中的「连续存储分配」，类似 OS 中「连续内存分配」方案——优点是访问快、缺点是产生外部碎片（无法利用零散空间）。链表则类似 OS 的「链接分配」方案，不要求连续空间但需要额外指针开销。理解这对概念有助于在408四科之间融会贯通。

---

2.3 链表（Linked List）

一、单链表的定义

单链表：每个结点除了存放数据元素外，还存放一个指向下一个结点的指针。

typedef struct LNode {
    ElemType data;       // 数据域
    struct LNode *next;  // 指针域
} LNode, *LinkList;

class LNode {
    int data;       // 数据域
    LNode next;     // 指针域（引用下一个结点）
    LNode(int data) {
        this.data = data;
        this.next = null;
    }
}

🗣️ 大白话：单链表就像一群小朋友手拉手排队，每个人只拉着下一个人的手。你要找第5个人，必须从第1个人开始，沿着"手"一个一个摸过去。

带头结点 vs 不带头结点：

	带头结点	不带头结点
空表判断	L->next == NULL	L == NULL
优点	操作统一，不需要特殊处理第一个元素	节省一个结点的空间
考研常用	✅ 推荐	有时也会考

二、单链表的基本操作

1. 头插法建立单链表（逆序）

// 头插法：每次插入到头结点之后，最终顺序与输入相反
LinkList List_HeadInsert(LinkList &L) {
    LNode *s;
    int x;
    L = (LinkList)malloc(sizeof(LNode));  // 创建头结点
    L->next = NULL;
    scanf("%d", &x);
    while (x != 9999) {
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        s->next = L->next;
        L->next = s;
        scanf("%d", &x);
    }
    return L;
}

// 头插法：每次插入到头结点之后，最终顺序与输入相反
LNode listHeadInsert(Scanner sc) {
    LNode head = new LNode(0);  // 创建头结点
    head.next = null;
    while (sc.hasNextInt()) {
        int x = sc.nextInt();
        if (x == 9999) break;
        LNode s = new LNode(x);
        s.next = head.next;
        head.next = s;
    }
    return head;
}

💡 重要应用：头插法可用于链表的逆置（原地翻转链表）！

2. 尾插法建立单链表（正序）

// 尾插法：每次插入到表尾，最终顺序与输入相同
LinkList List_TailInsert(LinkList &L) {
    int x;
    L = (LinkList)malloc(sizeof(LNode));
    LNode *s, *r = L;  // r为表尾指针
    scanf("%d", &x);
    while (x != 9999) {
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;          // r指向新的表尾结点
        scanf("%d", &x);
    }
    r->next = NULL;
    return L;
}

// 尾插法：每次插入到表尾，最终顺序与输入相同
LNode listTailInsert(Scanner sc) {
    LNode head = new LNode(0);  // 创建头结点
    LNode r = head;  // r为表尾指针
    while (sc.hasNextInt()) {
        int x = sc.nextInt();
        if (x == 9999) break;
        LNode s = new LNode(x);
        r.next = s;
        r = s;
    }
    r.next = null;
    return head;
}

3. 按序号查找（$O(n)$）

LNode *GetElem(LinkList L, int i) {
    if (i < 0) return NULL;
    int j = 0;
    LNode *p = L;   // p指向头结点，头结点当第0个
    while (p != NULL && j < i) {
        p = p->next;
        j++;
    }
    return p;
}

LNode getElem(LNode L, int i) {
    if (i < 0) return null;
    int j = 0;
    LNode p = L;  // p指向头结点，头结点当第0个
    while (p != null && j < i) {
        p = p.next;
        j++;
    }
    return p;
}

4. 按值查找（$O(n)$）

LNode *LocateElem(LinkList L, ElemType e) {
    LNode *p = L->next;
    while (p != NULL && p->data != e)
        p = p->next;
    return p;
}

LNode locateElem(LNode L, int e) {
    LNode p = L.next;
    while (p != null && p.data != e)
        p = p.next;
    return p;
}

5. 插入操作

在第 $i$ 个位置插入：先找到第 $i-1$ 个结点，然后插入。

// 在p结点之后插入s结点
s->next = p->next;
p->next = s;

// 在p结点之后插入s结点
s.next = p.next;
p.next = s;

在p结点之前插入（技巧：偷天换日法）：

// 实际是在p之后插入s，然后交换p和s的数据
s->next = p->next;
p->next = s;
temp = p->data;
p->data = s->data;
s->data = temp;

// 实际是在p之后插入s，然后交换p和s的数据
s.next = p.next;
p.next = s;
int temp = p.data;
p.data = s.data;
s.data = temp;

🗣️ 大白话：如果要在某个人前面插队，你先站到他后面，然后你俩把衣服（数据）互换一下——外人看来你就排在他前面了。

6. 删除操作

删除第 $i$ 个结点：先找到第 $i-1$ 个结点，然后删除。

// 删除p的后继结点q
q = p->next;
p->next = q->next;
free(q);

// 删除p的后继结点q
LNode q = p.next;
p.next = q.next;
q = null;  // Java用置空代替 free

删除结点 p 本身（技巧：用后继替自己）：

// 用p的后继结点的值覆盖p，然后删除后继结点
q = p->next;
p->data = p->next->data;
p->next = q->next;
free(q);

// 用p的后继结点的值覆盖p，然后删除后继结点
LNode q = p.next;
p.data = p.next.data;
p.next = q.next;
q = null;

三、双链表

双链表：每个结点除了后继指针外，还有一个前驱指针。

typedef struct DNode {
    ElemType data;
    struct DNode *prior;  // 前驱指针
    struct DNode *next;   // 后继指针
} DNode, *DLinklist;

class DNode {
    int data;
    DNode prior;  // 前驱指针
    DNode next;   // 后继指针
    DNode(int data) {
        this.data = data;
        this.prior = null;
        this.next = null;
    }
}

双链表插入操作（在p结点之后插入s结点）：

// 关键：注意赋值顺序，不能断链
s->next = p->next;       // ①
if (p->next != NULL)
    p->next->prior = s;  // ②
s->prior = p;            // ③
p->next = s;             // ④

⚠️ 顺序问题：①②必须在④之前，否则 p->next 被修改后找不到原来的后继了。

双链表删除操作（删除p的后继结点q）：

q = p->next;
p->next = q->next;
if (q->next != NULL)
    q->next->prior = p;
free(q);

// 双链表删除：删除p的后继结点q
DNode q = p.next;
p.next = q.next;
if (q.next != null)
    q.next.prior = p;
q = null;

四、循环链表

循环单链表：表尾结点的 next 指向头结点（而非 NULL），形成一个环。

• 空表判断：L->next == L
• 优势：从任一结点出发都能找到其他所有结点

循环双链表：头结点的 prior 指向表尾结点，表尾结点的 next 指向头结点。

• 空表判断：L->prior == L && L->next == L

五、静态链表

静态链表：用数组模拟链表。每个数组元素包含一个数据域和一个游标（cursor），游标充当"指针"的角色，指示下一个元素在数组中的下标。

#define MaxSize 50
typedef struct {
    ElemType data;
    int next;   // 下一个元素的数组下标（游标）
} SLinklist[MaxSize];

class SLinkNode {
    int data;
    int next;   // 下一个元素的数组下标（游标）
}
// Java中用 SLinkNode[] sLinklist = new SLinkNode[MaxSize]; 表示静态链表

🗣️ 大白话：在没有指针的语言（如早期BASIC、Fortran）中，用数组下标代替指针，模拟出链表的效果。

静态链表的特点：

• 以 next == -1 作为链表结束标志（类似单链表的 NULL）
• 插入和删除时只需修改游标，不需要移动元素（保留链表的优势）
• 但容量固定，且没有顺序表的随机存取特性（查找仍需从头遍历）
• 实际应用：操作系统的文件分配表FAT就是一种静态链表

六、顺序表 vs 链表

比较项	顺序表	链表
逻辑结构	都属于线性表	都属于线性表
存储结构	顺序存储	链式存储
存取方式	随机存取 $O(1)$	顺序存取 $O(n)$
按位查找	$O(1)$	$O(n)$
按值查找	$O(n)$，有序时可折半 $O(\log n)$	$O(n)$
插入删除	需要移动元素 $O(n)$	只需修改指针 $O(1)$（找到位置后）
空间分配	需要预先分配连续空间	动态分配，按需申请
存储密度	高（不需要额外存储指针）	低（需要额外存储指针域）
空间利用	可能造成浪费（预分配多）或溢出	不浪费但指针开销大
适用场景	表长可预估、频繁按位查找	频繁插入删除、表长难以预估

💡 选择建议：

• 频繁查找（按位序）→ 顺序表
• 频繁插入/删除 → 链表
• 表长难以预估 → 链表
• 存储空间紧张 → 顺序表（存储密度高）

📝 真题剖析

【2019年408真题】 已知一个带有表头结点的单链表，结点结构为 [data|next]。在不改变链表的前提下，设计一个尽可能高效的算法，查找链表中倒数第 $k$ 个位置上的结点（$k$ 为正整数）。若查找成功，输出该结点的 data 值，并返回1；否则返回0。

解题方法：双指针法（快慢指针）

int Search_k(LinkList L, int k) {
    LNode *p = L->next, *q = L->next;
    int count = 0;
    // p指针先走k步
    while (p != NULL) {
        if (count < k)
            count++;
        else
            q = q->next;  // p走了k步后，q开始走
        p = p->next;
    }
    if (count < k) return 0;  // k超过了链表长度
    else {
        printf("%d", q->data);
        return 1;
    }
}

int searchK(LNode L, int k) {
    LNode p = L.next, q = L.next;
    int count = 0;
    while (p != null) {
        if (count < k)
            count++;
        else
            q = q.next;
        p = p.next;
    }
    if (count < k)
        return 0;
    else {
        System.out.println(q.data);
        return 1;
    }
}

💡 核心思路：让快指针 $p$ 先走 $k$ 步，然后 $p$ 和 $q$ 同时走。当 $p$ 到达表尾（NULL）时，$q$ 正好指向倒数第 $k$ 个结点。就像两个人隔着固定距离走路，前面的人到终点时，后面的人离终点恰好差那么远。

⚠️ 评分标准揭秘（2009真题原题）：一遍扫描满分15分，两遍扫描最高10分。所以一定要追求 $O(n)$ 一遍扫描的解法！

---

【2010年408真题】 将 $n$（$n>1$）个整数存放到一维数组 $R$ 中，将 $R$ 中的序列循环左移 $p$（$0<p<n$）个位置，即由 $(X_0, X_1, \ldots, X_{n-1})$ 变换为 $(X_p, X_{p+1}, \ldots, X_{n-1}, X_0, X_1, \ldots, X_{p-1})$。要求时间复杂度 $O(n)$，空间复杂度 $O(1)$。

解题方法：三次翻转法（Reverse 法）

设计思想：将数组 $ab$ 变为 $ba$（$a$ 代表前 $p$ 个元素，$b$ 代表后 $n-p$ 个元素）：

1. 先将 $a$ 逆置得到 $a^{-1}b$
2. 再将 $b$ 逆置得到 $a^{-1}b^{-1}$
3. 最后将整体逆置得到 $(a^{-1}b^{-1})^{-1} = ba$

例：abcdefgh 循环左移 3 位：

• Reverse(0,2) → cba|defgh
• Reverse(3,7) → cba|hgfed
• Reverse(0,7) → defghabc ✓

void Reverse(int R[], int from, int to) {
    int temp;
    for (int i = 0; i < (to - from + 1) / 2; i++) {
        temp = R[from + i];
        R[from + i] = R[to - i];
        R[to - i] = temp;
    }
}

void Converse(int R[], int n, int p) {
    Reverse(R, 0, p - 1);      // 翻转前p个
    Reverse(R, p, n - 1);      // 翻转后n-p个
    Reverse(R, 0, n - 1);      // 整体翻转
}

void reverse(int[] R, int from, int to) {
    for (int i = 0; i < (to - from + 1) / 2; i++) {
        int temp = R[from + i];
        R[from + i] = R[to - i];
        R[to - i] = temp;
    }
}

void converse(int[] R, int n, int p) {
    reverse(R, 0, p - 1);
    reverse(R, p, n - 1);
    reverse(R, 0, n - 1);
}

💡 三次 Reverse 的时间复杂度分别为 $O(p/2)$、$O((n-p)/2)$、$O(n/2)$，合计为 $O(n)$，空间复杂度为 $O(1)$。此题是经典的空间换时间思维的反面——用巧妙的翻转避免额外空间。

---

【2012年408真题】 假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时可共享后缀存储空间（如"loading"和"being"共享"ing"）。设 str1 和 str2 分别指向两个单词所在单链表的头结点，找出共同后缀的起始位置。

解题方法：等长对齐法

设计思想：

1. 分别求出两个链表的长度 $m$ 和 $n$
2. 让较长链表的指针先走 $|m-n|$ 步，使两个指针到表尾的距离相等
3. 两个指针同步后移，第一次指向同一结点时即为共同后缀的起始位置

LinkNode* Find_1st_Common(LinkList str1, LinkList str2) {
    int len1 = Length(str1), len2 = Length(str2);
    LinkNode *p, *q;
    for (p = str1; len1 > len2; len1--)
        p = p->next;
    for (q = str2; len1 < len2; len2--)
        q = q->next;
    while (p->next != NULL && p->next != q->next) {
        p = p->next;
        q = q->next;
    }
    return p->next;
}

ListNode find1stCommon(ListNode str1, ListNode str2) {
    int len1 = length(str1), len2 = length(str2);
    ListNode p = str1, q = str2;
    for (; len1 > len2; len1--) p = p.next;
    for (; len1 < len2; len2--) q = q.next;
    while (p.next != null && p.next != q.next) {
        p = p.next;
        q = q.next;
    }
    return p.next;
}

💡 时间复杂度 $O(m+n)$，空间复杂度 $O(1)$。核心技巧：尾部对齐，同步前进。

---

【2011年408真题】 两个等长升序序列 $A$ 和 $B$ 各有 $n$ 个元素，找出 $A$ 和 $B$ 的中位数（合并后升序序列的第 $\lceil n \rceil$ 个元素）。

解题方法：折半淘汰法

设计思想：分别取 $A$、$B$ 的中位数 $a$、$b$：

• 若 $a = b$，则 $a$ 即为所求
• 若 $a < b$，舍弃 $A$ 的较小半部分和 $B$ 的较大半部分（保留长度相等）
• 若 $a > b$，舍弃 $A$ 的较大半部分和 $B$ 的较小半部分

重复上述过程，直到两序列各剩一个元素，较小者即为中位数。

💡 时间复杂度 $O(\log_2 n)$，空间复杂度 $O(1)$。本质是二分思想的双序列应用。

⚠️ 易错点：奇数个元素时中位数所在元素需保留，偶数个元素时可舍弃中位数位置。

---

【2018年408真题·应用题】 给定一个含 $n$ 个整数的数组 A[n]，设计一个算法，找出数组中未出现的最小正整数。要求时间上尽可能高效。

设计思想：分配一个标记数组 B[n]（初始全0），扫描 A，若 0 < A[i] <= n 则令 B[A[i]-1] = 1。再扫描 B，第一个 B[i]==0 的位置即对应缺失的最小正整数 i+1；若全部为1则返回 n+1。

int findMissMin(int A[], int n) {
    int *B = (int *)malloc(sizeof(int) * n);
    memset(B, 0, sizeof(int) * n);
    for (int i = 0; i < n; i++)
        if (A[i] > 0 && A[i] <= n)
            B[A[i] - 1] = 1;          // 标记出现过
    for (int i = 0; i < n; i++)
        if (B[i] == 0) { free(B); return i + 1; }
    free(B);
    return n + 1;
}

💡 时间复杂度 $O(n)$，空间复杂度 $O(n)$。经典的空间换时间——打标记法。

⚠️ 关键洞察：$n$ 个整数中，缺失的最小正整数一定在 $[1, n+1]$ 范围内。

---

【2019年408真题·应用题】 设线性表 $L = (a_1, a_2, \ldots, a_n)$（链式存储），设计就地算法将 $L$ 重排为 $(a_1, a_n, a_2, a_{n-1}, \ldots)$。

设计思想（三步法）：

1. 找中间结点：快慢指针法（fast走两步，slow走一步），slow停在中间位置
2. 逆置后半段：将链表后半段原地逆置
3. 交替合并：前半段与逆置后半段交替合并

void reorder(LinkList L) {
    // Step 1: 快慢指针找中间
    LNode *fast = L, *slow = L;
    while (fast->next != NULL) {
        slow = slow->next;
        fast = fast->next;
        if (fast->next != NULL) fast = fast->next;
    }
    // Step 2: 逆置后半段
    LNode *p = slow->next, *r;
    slow->next = NULL;
    while (p != NULL) {
        r = p->next;
        p->next = slow->next;
        slow->next = p;
        p = r;
    }
    // Step 3: 交替合并
    LNode *p1 = L->next, *p2 = slow->next, *q;
    slow->next = NULL;
    while (p2 != NULL) {
        q = p2->next;
        p2->next = p1->next;
        p1->next = p2;
        p1 = p2->next;
        p2 = q;
    }
}

💡 时间复杂度 $O(n)$，空间复杂度 $O(1)$。三大经典链表子操作的综合运用：快慢指针 + 链表逆置 + 链表合并。

---

【2013年408真题·应用题】 已知一个整数序列 $A = (a_0, a_1, \ldots, a_{n-1})$，其中 $0 \leq a_i < n$（$0 \leq i < n$）。若存在 $a_{p_1} = a_{p_2} = \cdots = a_{p_m} = x$，且 $m > n/2$（$0 \leq p_k < n$，$1 \leq k \leq m$），则称 $x$ 为 $A$ 的主元素。设计算法找出主元素，若存在输出该元素，否则输出 $-1$。

解题方法：Boyer-Moore 投票算法（$O(n)$ 时间 $O(1)$ 空间）

设计思想：

1. 候选阶段：设 $c$ 为候选主元素，$count$ 为计票器。遍历数组，若 $count = 0$ 则令 $c = a_i$, $count = 1$；否则若 $a_i = c$ 则 $count$++，否则 $count$--。遍历结束后 $c$ 是"可能的主元素"。
2. 验证阶段：再扫描一遍数组，统计 $c$ 实际出现次数，若 $> n/2$ 则 $c$ 是主元素，否则不存在。

int majority(int A[], int n) {
    int c = A[0], count = 1;
    // 候选阶段
    for (int i = 1; i < n; i++) {
        if (A[i] == c) count++;
        else if (count > 0) count--;
        else { c = A[i]; count = 1; }
    }
    // 验证阶段
    count = 0;
    for (int i = 0; i < n; i++)
        if (A[i] == c) count++;
    return (count > n / 2) ? c : -1;
}

int majority(int[] A, int n) {
    int c = A[0], count = 1;
    // 候选阶段
    for (int i = 1; i < n; i++) {
        if (A[i] == c) count++;
        else if (count > 0) count--;
        else { c = A[i]; count = 1; }
    }
    // 验证阶段
    count = 0;
    for (int i = 0; i < n; i++)
        if (A[i] == c) count++;
    return (count > n / 2) ? c : -1;
}

💡 核心思想："多数派投票"——把不同的元素两两抵消，最后剩下的就是候选主元素。若主元素存在（占一半以上），它一定不会被完全抵消。

⚠️ 为什么需要验证阶段？ 因为当主元素不存在时（如 {1,2,3}），投票法仍会返回一个候选值（最后一个赋值的），但它不是主元素。所以必须再验证一遍。

---

【2020年408真题·应用题】 三个升序整数数组 $A[l_1]$、$B[l_2]$、$C[l_3]$，找 $a \in A, b \in B, c \in C$ 使得 $D = |a-b| + |b-c| + |c-a|$ 最小，输出最小的 $D$。

设计思想：三指针法

关键公式推导：$|a-b| + |b-c| + |c-a| = 2(\max(a,b,c) - \min(a,b,c))$

证明：不妨设 $a \leq b \leq c$，则 $|a-b| + |b-c| + |c-a| = (b-a) + (c-b) + (c-a) = 2(c-a) = 2(\max - \min)$。

因此问题转化为：最小化三者中最大值与最小值的差。

三指针策略：

1. 三个指针分别指向三个数组的开头
2. 每次计算 $D$，更新最小值
3. 将最小元素所在数组的指针右移（尝试缩小 $\max - \min$）
4. 当任一指针越界时停止

int findMinD(int A[], int l1, int B[], int l2, int C[], int l3) {
    int i = 0, j = 0, k = 0, minD = INT_MAX;
    while (i < l1 && j < l2 && k < l3) {
        int D = abs(A[i]-B[j]) + abs(B[j]-C[k]) + abs(C[k]-A[i]);
        if (D < minD) minD = D;
        // 移动最小值的指针
        int minVal = min3(A[i], B[j], C[k]);
        if (A[i] == minVal) i++;
        else if (B[j] == minVal) j++;
        else k++;
    }
    return minD;
}

int findMinD(int[] A, int[] B, int[] C) {
    int i = 0, j = 0, k = 0;
    int minD = Integer.MAX_VALUE;
    while (i < A.length && j < B.length && k < C.length) {
        int D = Math.abs(A[i]-B[j]) + Math.abs(B[j]-C[k]) + Math.abs(C[k]-A[i]);
        minD = Math.min(minD, D);
        int minVal = Math.min(A[i], Math.min(B[j], C[k]));
        if (A[i] == minVal) i++;
        else if (B[j] == minVal) j++;
        else k++;
    }
    return minD;
}

💡 时间复杂度 $O(l_1 + l_2 + l_3)$，空间复杂度 $O(1)$。核心技巧：将绝对值之和化简为 $2(\max - \min)$，将三元问题转化为极差最小化问题，然后用贪心策略——每次移动最小值指针。

---

【2024年408真题】 带头结点的链表L，指针p指向中间的结点，执行：q=p->next; p->next=q->next; q->next=L->next; L->next=q;，功能是将p的后继结点q移动到表头（头插）。

⚠️ 链表指针操作题是选择题必考内容！解题技巧：画图模拟每一步指针变化，标注清楚修改顺序。

📌 第二章总结

核心知识点	考研要求
线性表的定义与特点	理解概念
顺序表的随机存取特性、地址计算公式	重点
顺序表的插入、删除、查找的时间复杂度	高频考点
单链表的头插法与尾插法	必须掌握，大题常考
单链表的插入、删除操作（指针操作）	重中之重
双链表的插入、删除（注意指针顺序）	需要掌握
循环链表的特点、空表判断	理解记忆
静态链表的概念	了解即可
顺序表 vs 链表的比较	必须掌握
链表的综合应用（双指针、链表逆置等）	大题必考

典型应用：链表重排（L0→Ln→L1→Ln-1...）

---

第三章 栈、队列和数组

3.1 栈（Stack）

一、栈的基本概念

栈（Stack）：只允许在一端进行插入和删除操作的线性表。允许操作的一端称为栈顶（top），不允许操作的一端称为栈底（bottom）。

核心特征：后进先出（LIFO, Last In First Out）

🗣️ 大白话：栈就像一摞盘子——你只能从最上面放盘子（入栈/压栈），也只能从最上面拿盘子（出栈/弹栈）。最后放上去的盘子最先被拿走，这就叫"后进先出"。

🔗 【跨学科联动·OS/计组】 栈在操作系统中无处不在：

• 函数调用栈：每次函数调用时，OS 将返回地址、局部变量、参数压入栈帧（Stack Frame），函数返回时弹出恢复现场。这就是为什么递归过深会导致栈溢出（Stack Overflow）。
• 中断处理：CPU 响应中断时，自动将 PC（程序计数器）和 PSW（程序状态字） 压栈保存现场，中断返回时弹栈恢复。
• 表达式求值：编译原理中用栈实现中缀→后缀表达式转换，本质是利用栈的 LIFO 特性处理运算符优先级。
• 计组中的堆栈寻址方式（SP 寄存器指向栈顶）也与此直接相关。

基本操作：

• Push(&S, x)：入栈（压栈），将元素 x 加入栈顶
• Pop(&S, &x)：出栈（弹栈），弹出栈顶元素
• GetTop(S, &x)：读栈顶元素（不删除）
• StackEmpty(S)：判断栈是否为空

二、栈的顺序存储实现

#define MaxSize 50
typedef struct {
    ElemType data[MaxSize];
    int top;   // 栈顶指针
} SqStack;

class SqStack {
    static final int MaxSize = 50;
    int[] data = new int[MaxSize];
    int top = -1;   // 栏顶指针

    boolean isEmpty() { return top == -1; }
    boolean isFull()  { return top == MaxSize - 1; }
    void push(int x)  { data[++top] = x; }
    int pop()         { return data[top--]; }
    int getTop()      { return data[top]; }
}

初始化：S.top = -1（栈空时 top 为 -1）

操作	代码	说明
栈空判断	S.top == -1
栈满判断	S.top == MaxSize - 1
入栈	S.data[++S.top] = x	先移动指针，再存入元素
出栈	x = S.data[S.top--]	先取出元素，再移动指针
读栈顶	x = S.data[S.top]	不修改栈顶指针

⚠️ 另一种初始化：S.top = 0（top 指向栈顶元素的下一个位置）

• 栈空：S.top == 0
• 入栈：S.data[S.top++] = x
• 出栈：x = S.data[--S.top]

共享栈：两个栈共享同一片存储空间，一个从底部向上长，一个从顶部向下长：

• 栈1的栈顶指针 top0 从 -1 开始增长
• 栈2的栈顶指针 top1 从 MaxSize 开始减小
• 栈满条件：top0 + 1 == top1

三、栈的链式存储实现

typedef struct Linknode {
    ElemType data;
    struct Linknode *next;
} *LiStack;

class LiStackNode {
    int data;
    LiStackNode next;
    LiStackNode(int data) {
        this.data = data;
        this.next = null;
    }
}
// 链式栈的入栈和出栈都在链表头部进行（头插法/头删法）

通常以链表头部作为栈顶，入栈和出栈都在链表头部进行（便于操作，$O(1)$）。

四、栈的出栈序列问题（卡特兰数）

$n$ 个不同元素依次进栈，合法出栈序列的总数为卡特兰数：

$\frac{1}{n+1}C_{2n}^{n} = \frac{(2n)!}{(n+1)! \cdot n!}$

$n$	合法出栈序列数
1	1
2	2
3	5
4	14
5	42

🗣️ 大白话：3个元素（1,2,3）依次入栈，问有多少种合法的出栈顺序？答案是5种。不合法的例子：3,1,2 是不可能的——因为3先出来意味着1,2都在栈里，此时2在1上面，所以2必须先于1出栈。

---

3.2 队列（Queue）

一、队列的基本概念

队列（Queue）：只允许在一端插入（队尾 rear）、另一端删除（队头 front）的线性表。

核心特征：先进先出（FIFO, First In First Out）

🗣️ 大白话：队列就像排队买饭——先来的先买，后来的排后面。从队尾进来，从队头出去。

🔗 【跨学科联动·OS/计网】 队列在其他学科中的应用：

• OS·进程调度：就绪队列（FCFS 调度）、多级反馈队列调度都基于队列
• OS·磁盘调度：FCFS 磁盘调度算法就是一个请求队列
• OS·缓冲区：生产者-消费者模型中的缓冲池本质是循环队列
• 计网·分组交换：路由器的输入/输出缓冲区就是队列（FIFO），队列满时发生丢包
• BFS 使用队列而 DFS 使用栈——这是考试中要求区分的核心对比点

二、队列的顺序实现——循环队列

问题：用普通数组实现队列时会出现"假溢出"（数组前面有空位但无法使用）。

解决方案：循环队列——把数组首尾相连，形成逻辑上的"环"。

#define MaxSize 50
typedef struct {
    ElemType data[MaxSize];
    int front, rear;  // 队头和队尾指针
} SqQueue;

class SqQueue {
    static final int MaxSize = 50;
    int[] data = new int[MaxSize];
    int front = 0, rear = 0;

    void enQueue(int x) {
        data[rear] = x;
        rear = (rear + 1) % MaxSize;
    }
    int deQueue() {
        int x = data[front];
        front = (front + 1) % MaxSize;
        return x;
    }
    int size() {
        return (rear - front + MaxSize) % MaxSize;
    }
    boolean isEmpty() { return front == rear; }
    boolean isFull()  { return (rear + 1) % MaxSize == front; }
}

关键操作（用取模运算实现循环）：

操作	公式/代码
初始化	Q.front = Q.rear = 0
入队	Q.data[Q.rear] = x; Q.rear = (Q.rear + 1) % MaxSize
出队	x = Q.data[Q.front]; Q.front = (Q.front + 1) % MaxSize
队列长度	(Q.rear - Q.front + MaxSize) % MaxSize

如何区分队空和队满？（三种方法）

方法	队空条件	队满条件
牺牲一个单元（常用）	Q.front == Q.rear	(Q.rear + 1) % MaxSize == Q.front
增设 size 变量	Q.size == 0	Q.size == MaxSize
增设 tag 标志	Q.front == Q.rear && tag == 0	Q.front == Q.rear && tag == 1

⚠️ 2011年真题考点：当 front 和 rear 分别指向队头元素和队尾元素（而非队尾元素的下一个位置）时，初始化需要特殊处理。

若要求第1个入队元素存储在 A[0]，且入队操作为 rear = (rear+1)%n; A[rear] = x（先移动再存值），则初始时 front = 0, rear = n-1。这样第一次入队时 rear = (n-1+1)%n = 0，元素存入 A[0]。

💡 记忆：rear 指向队尾元素（而非下一个位置）的方案中，rear 初值 = front 前一个位置。

🗣️ 大白话：最常用的是"牺牲一个位置"。就像圆形跑道上有50个座位，我们只坐49个，留一个空座位——如果队尾追上队头（差一个位置），就说明满了；如果队头等于队尾，就说明空了。

三、队列的链式实现

typedef struct LinkNode {   // 链式队列结点
    ElemType data;
    struct LinkNode *next;
} LinkNode;
typedef struct {            // 链式队列
    LinkNode *front, *rear; // 队头和队尾指针
} LinkQueue;

class LinkNode {
    int data;
    LinkNode next;
    LinkNode(int data) {
        this.data = data;
        this.next = null;
    }
}
class LinkQueue {
    LinkNode front, rear;  // 队头和队尾指针
    LinkQueue() {
        front = rear = new LinkNode(0);  // 带头结点
    }
    void enQueue(int x) {
        LinkNode s = new LinkNode(x);
        rear.next = s;
        rear = s;
    }
    int deQueue() {
        LinkNode p = front.next;
        int x = p.data;
        front.next = p.next;
        if (rear == p) rear = front;  // 最后一个元素出队
        return x;
    }
    boolean isEmpty() { return front == rear; }
}

• 带头结点：Q.front == Q.rear 时为空（都指向头结点）
• 不带头结点：Q.front == NULL 时为空

四、双端队列

双端队列（Deque）：两端都允许进行插入和删除操作的队列。

• 输出受限的双端队列：一端允许插入和删除，另一端只允许插入
• 输入受限的双端队列：一端允许插入和删除，另一端只允许删除

⚠️ 考研爱考：给定输入序列，判断某个输出序列是否可能通过双端队列实现。

判断方法：

• 普通队列：只能产生 FIFO 顺序
• 普通栈：只能产生 LIFO 顺序（可用卡特兰数计算总数）
• 输入受限的双端队列：能产生的序列 ⊇ 栈能产生的序列（因为两端都可以输出）
• 输出受限的双端队列：能产生的序列 ⊇ 栈能产生的序列（因为两端都可以输入）
• 某些序列既不能由栈产生也不能由队列产生，但可以由双端队列产生

💡 考研选择题通常给出4个序列，问哪些不能由某种双端队列产生。解题方法：逐个模拟，用草稿纸画出双端队列的操作过程。

---

3.3 栈和队列的应用

一、栈在括号匹配中的应用

算法思路：依次扫描每个字符：

1. 遇到左括号——入栈
2. 遇到右括号——检查栈顶是否配对
   • 配对成功——弹出栈顶元素
   • 配对失败——匹配失败
3. 扫描完毕后栈空——匹配成功

二、栈在表达式求值中的应用

三种表达式：

类型	示例（$A+B \times C$）	运算符位置
中缀表达式	$A + B \times C$	运算符在操作数中间
后缀表达式（逆波兰式）	$A\ B\ C \times +$	运算符在操作数后面
前缀表达式（波兰式）	$+\ A\ \times\ B\ C$	运算符在操作数前面

中缀转后缀（手工方法）：

1. 按运算符优先级对中缀表达式加括号
2. 将运算符移到对应括号的后面
3. 去掉所有括号

例：$A + B \times C - D$ → $((A + (B \times C)) - D)$ → $((A\ (B\ C\times)+)\ D-)$ → $A\ B\ C \times + D -$

中缀转后缀（机器算法，用运算符栈）：

从左到右扫描中缀表达式：

1. 遇到操作数——直接加入后缀表达式
2. 遇到左括号 (——入栈
3. 遇到右括号 )——依次弹出栈中运算符加入后缀表达式，直到遇到左括号（左括号出栈但不加入）
4. 遇到运算符——与栈顶运算符比较优先级：
   • 若栈空、栈顶为 ( 、或当前运算符优先级高于栈顶运算符 → 入栈
   • 否则 → 弹出栈顶运算符加入后缀表达式，重复比较新栈顶，直到可以入栈
5. 扫描完毕 → 依次弹出栈中所有运算符加入后缀表达式

💡 优先级规则：× / 高于 + -。相同优先级时弹出栈顶（左结合）。

详细示例：中缀 A*(B+C)-D → 后缀

步骤	扫描	操作	栈	后缀表达式
1	A	输出	空	A
2	*	栈空，入栈	*	A
3	(	入栈	*(	A
4	B	输出	*(	AB
5	+	栈顶为(，入栈	*(+	AB
6	C	输出	*(+	ABC
7	)	弹出+，弹出(	*	ABC+
8	-	优先级≤栈顶*，弹出*，入栈	-	ABC+*
9	D	输出	-	ABC+*D
10	结束	弹出-	空	ABC+*D-

中缀转前缀：从右到左扫描，规则类似但方向相反。

【2012年408真题】 含复杂嵌套括号的完整示例：a+b-a*((c+d)/e-f)+g → ab+acd+e/f-*-g+

步骤	扫描	操作	运算符栈（底→顶）	后缀输出
1	a	输出	#	a
2	+	入栈	#+	a
3	b	输出	#+	ab
4	-	弹出+，入栈	#-	ab+
5	a	输出	#-	ab+a
6	*	优先级>栈顶-，入栈	#-*	ab+a
7	(	入栈	#-*(	ab+a
8	(	入栈	#-*((	ab+a
9	c	输出	#-*((	ab+ac
10	+	栈顶(，入栈	#-*((+	ab+ac
11	d	输出	#-*((+	ab+acd
12	)	弹出+，弹出(	#-*(	ab+acd+
13	/	栈顶(，入栈	#-*(/	ab+acd+
14	e	输出	#-*(/	ab+acd+e
15	-	弹出/，入栈	#-*(-	ab+acd+e/
16	f	输出	#-*(-	ab+acd+e/f
17	)	弹出-，弹出(	#-*	ab+acd+e/f-
18	+	弹出*、弹出-，入栈	#+	ab+acd+e/f-*-
19	g	输出	#+	ab+acd+e/f-*-g
20	结束	弹出+	#	ab+acd+e/f-*-g+

💡 栈中操作符最大同时存在数为5（步骤8~10：#-*((+）。这是2012年真题考查的核心点。

后缀表达式求值（用栈）：

1. 从左到右扫描后缀表达式
2. 遇到操作数——入栈
3. 遇到运算符——弹出两个操作数，计算结果入栈
4. 最终栈中唯一元素就是结果

🗣️ 大白话：后缀表达式对计算机很友好——不需要考虑优先级和括号，从左到右扫一遍就算完了。这就是为什么编译器内部都先把表达式转成后缀的。

三、栈在递归中的应用

系统在执行递归函数时，会使用一个递归工作栈。每次递归调用时，将当前函数的局部变量、返回地址等信息压入系统栈中，形成一个栈帧（Stack Frame）；递归返回时弹出栈帧恢复现场。

递归工作栈中每个栈帧包含：

• 局部变量
• 形参
• 返回地址
• （其他现场信息）

递归的空间复杂度 = 递归调用的最大深度（即递归栈的最大长度）

⚠️ 递归的缺点：

• 递归层数太深 → 栈溢出（Stack Overflow）
• 重复计算（如朴素的 Fibonacci 递归 → 指数级时间复杂度）→ 可用记忆化搜索或动态规划优化
• 递归效率通常低于等价的迭代实现（因为函数调用开销）

💡 递归转非递归：可以利用显式栈模拟系统递归栈来消除递归（如非递归DFS、非递归中序遍历）。

四、队列的应用

1. 层次遍历（如二叉树的层序遍历）
2. 计算机系统中的应用：
   • CPU 调度中的就绪队列
   • 打印机的打印缓冲区
   • 消息队列

---

3.4 数组和特殊矩阵的压缩存储

一、数组

多维数组的存储：

• 行优先存储：一行一行地按顺序存储（C语言采用）
• 列优先存储：一列一列地按顺序存储（Fortran采用）

二维数组 $A[m][n]$ 按行优先存储，元素 $A[i][j]$ 的地址为：

$LOC(A[i][j]) = LOC(A[0][0]) + (i \times n + j) \times sizeof(ElemType)$

二、特殊矩阵的压缩存储

⚠️ 审题陷阱：矩阵元素下标通常从 1 开始（$a_{1,1}$），数组下标默认从 0 开始（$B[0]$）。题目如果说"数组下标从1开始"，公式需要调整！

对称矩阵（$a_{ij} = a_{ji}$）：只存储下三角区（含主对角线），$n$ 阶对称矩阵只需 $\frac{n(n+1)}{2}$ 个存储单元。

元素 $a_{ij}$（$i \geq j$）在一维数组 $B[0, \ldots]$ 中的下标 $k$：

$k = \frac{i(i-1)}{2} + j - 1 \quad (i \geq j)$

若 $i < j$，则 $k = \frac{j(j-1)}{2} + i - 1$（利用对称性 $a_{ij} = a_{ji}$）

下三角矩阵（上三角区元素全为常量 $c$）：

• 下三角区（$i \geq j$）：$k = \frac{i(i-1)}{2} + j - 1$
• 常量 $c$ 统一存放在最后：$k = \frac{n(n+1)}{2}$
• 共需 $\frac{n(n+1)}{2} + 1$ 个存储单元

上三角矩阵（下三角区元素全为常量 $c$）：

• 上三角区（$i \leq j$）：$k = \frac{(i-1)(2n-i+2)}{2} + j - i$
• 常量 $c$ 存在最后

三对角矩阵（带状矩阵）：

• 元素 $a_{ij}$ 只在 $|i-j| \leq 1$ 时非零
• 按行优先存储时，$a_{ij}$ 的下标 $k = 2i + j - 3$（行列号从1开始，$k$ 从0开始）
• 反向公式（已知 $k$ 求 $i,j$）：$i = \lfloor(k+1)/3\rfloor + 1$，$j = k - 2i + 3$

稀疏矩阵：非零元素远少于矩阵元素总数。

• 三元组表表示：(行号, 列号, 值)，此外还需存储矩阵的总行数和总列数（2023年真题考点）
• 十字链表表示：每行一个链表、每列一个链表，交叉组成十字形

⚠️ 2018年408真题：上三角矩阵按行存入一维数组 $N$，元素 $m_{6,6}$ 在 $N$ 中的下标为50。上三角公式关键：第 $i$ 行有 $n-i+1$ 个元素（$i$ 从1开始），$m_{i,j}$ 的下标 $k = \frac{(i-1)(2n-i+2)}{2} + j - i$。

⚠️ 2021年408真题：下三角矩阵行优先存储，已知 $A[3][3]$ 地址为220，求 $A[5][5]$ 地址。用公式计算二者之间的元素个数即可。

📝 真题剖析

【2014年408真题】 一个栈的入栈序列为 1, 2, 3, ..., n，其出栈序列为 $p_1, p_2, p_3, \ldots, p_n$。若 $p_2 = 3$，则 $p_3$ 可能的取值个数为（）。

A. $n-3$   B. $n-2$   C. $n-1$   D. 无法确定

解析：

$p_2 = 3$ 意味着第2个出栈的元素是3。

分析 $p_1$ 的可能值：

• 若 $p_1 = 1$：先入1出1，再入2入3，出3。此时栈中有2，接下来可入4,5,...再出，$p_3$ 可以是 2, 4, 5, ..., n 中的任一个。
• 若 $p_1 = 2$：先入1入2，出2，再入3，出3。此时栈中有1，$p_3$ 可以是 1, 4, 5, ..., n。
• 若 $p_1 = 4$：先入1入2入3入4，出4出3。此时栈中有1和2，$p_3$ 可以是 2, 5, 6, ..., n。

综合分析，$p_3$ 不可能是 3（已出栈），可以是 1, 2, 4, 5, ..., n 中的任一个，共 $n-1$ 个。

答案选C。

📌 第三章总结

核心知识点	考研要求
栈的LIFO特性、基本操作	必须牢记
顺序栈的实现（两种 top 初始值）	高频考点
共享栈的栈满条件	需要掌握
出栈序列的合法性判断 + 卡特兰数	常考
队列的FIFO特性、基本操作	必须牢记
循环队列的实现（取模运算）	重点
队空队满的判断（三种方法）	必须掌握
栈在括号匹配中的应用	需要掌握
中缀、后缀、前缀表达式及相互转换	重中之重
后缀表达式求值	必须掌握
矩阵压缩存储（对称、三角、三对角、稀疏）	高频考点

---

第四章 串（String）

4.1 串的定义和基本操作

串（String）：由零个或多个字符组成的有限序列。记作 $S='a_1a_2\ldots a_n'$，其中 $n$ 为串长。$n=0$ 时称为空串（用 $\varnothing$ 表示）。

⚠️ 空串 vs 空格串：空串长度为0（无任何字符），空格串 " " 长度为1（包含一个空格字符），二者不同！

子串：串中任意个连续字符组成的子序列。空串是任何串的子串，任何串是自身的子串。

子串位置：子串在主串中第一次出现时第一个字符的位置（位序从1开始）。

串 vs 线性表：

• 串是特殊的线性表——数据对象限定为字符集
• 串的操作对象通常是子串（而非单个元素）——如求子串、模式匹配、串联接等
• 线性表的操作多针对单个元素——如查找、插入、删除某个元素

串的比较：按字典序逐字符比较。字符的大小由其编码值决定（ASCII码、Unicode等）。若所有对应字符相同但长度不同，则较短串更小。

基本操作：

• StrAssign(&T, chars)：赋值（生成串T）
• StrCopy(&T, S)：复制
• StrEmpty(S)：判空
• StrLength(S)：求串长
• ClearString(&S)：清空
• DestroyString(&S)：销毁
• Concat(&T, S1, S2)：串联接
• SubString(&Sub, S, pos, len)：求子串
• StrCompare(S, T)：串比较
• Index(S, T, pos)：定位（模式匹配）

🗣️ 大白话：串就是一串字符，比如 "hello" 就是一个长度为5的串。"ell" 就是 "hello" 的子串。

串的存储结构

1. 定长顺序存储：用固定长度数组存储，有4种方案记录串长：

方案	说明	特点
ch[0] 存储串长	串内容存在 ch[1] ~ ch[MAXLEN]	串长受限于 ch[0] 类型（如 char 最大255）
额外变量 length	串内容存在 ch[0] ~ ch[length-1]	常用方案
\0 结尾	类似C语言字符串	求串长需遍历 $O(n)$
ch[0] 不用 + length	串内容存在 ch[1] ~ ch[length]	便于与教材位序从1开始对应

2. 堆分配存储：用 malloc 动态分配空间，串长不受限

3. 块链存储：用链表存储，每个结点存多个字符（存储密度 = 实际字符数 / 链表总容量）

⚠️ 块链存储操作不方便、存储密度低，实际中很少使用。

---

4.2 串的模式匹配

一、朴素模式匹配算法（BF算法）

问题：主串 $S$ 中查找模式串 $T$ 的位置。

思路：从主串第1个字符开始，依次与模式串对齐比较，失败就回溯到主串的下一个位置重新比较。

int Index(SString S, SString T) {
    int i = 1, j = 1;
    while (i <= S.length && j <= T.length) {
        if (S.ch[i] == T.ch[j]) {
            i++; j++;           // 匹配成功，继续比较后续
        } else {
            i = i - j + 2;     // i回溯
            j = 1;              // j归位
        }
    }
    if (j > T.length) return i - T.length;  // 匹配成功
    else return 0;                           // 匹配失败
}

// BF朴素模式匹配（Java下标从0开始）
int indexBF(String S, String T) {
    int i = 0, j = 0;
    while (i < S.length() && j < T.length()) {
        if (S.charAt(i) == T.charAt(j)) {
            i++; j++;
        } else {
            i = i - j + 1;  // i回溯
            j = 0;           // j归位
        }
    }
    if (j >= T.length()) return i - T.length();  // 匹配成功
    else return -1;                               // 匹配失败
}

时间复杂度：

• 最好情况：$O(m)$（第一次就匹配成功，$m$ 为模式串长度）
• 最坏情况：$O(nm)$（$n$ 为主串长度，$m$ 为模式串长度）
• 最坏情况示例：$S$ = "aaa...aab"，$T$ = "aab" → 每次前 $m-1$ 个字符都匹配，到最后一个才失配
• 实际应用中平均接近 $O(n+m)$（因为自然语言中连续部分匹配的概率很低）

🗣️ 大白话：BF算法就像笨办法找人——你拿着一张照片从人群第一个人开始一个个比对。如果发现"不是"，你就回到下一个人重新开始比对。虽然简单但是慢。

二、KMP算法

核心思想：当发生不匹配时，主串指针 $i$ 不回溯，只让模式串指针 $j$ 回退到一个合适的位置。这个"合适的位置"由 next数组 决定。

next数组的含义：next[j] 表示当模式串第 $j$ 个字符与主串发生不匹配时，模式串需要回退到的位置。也就是模式串 $T[1 \ldots j-1]$ 中最长相等真前后缀的长度加1。

next数组的手工求法：

对模式串的每个位置 $j$，求 $T[1 \ldots j-1]$ 的最长相等真前后缀长度，加1。

例：模式串 $T = "abaabcac"$

$j$	1	2	3	4	5	6	7	8
模式串	a	b	a	a	b	c	a	c
$T[1..j-1]$	∅	"a"	"ab"	"aba"	"abaa"	"abaab"	"abaabc"	"abaabca"
最长相等前后缀长度	0	0	0	1	1	2	0	1
next[j]	0	1	1	2	2	3	1	2

📏 规则：next[1] 固定为 0。

【KMP 匹配过程完整手工模拟】

以主串 $S$ = "abaabcac"，模式串 $T$ = "abaabc" 为例，next = [0, 1, 1, 2, 2, 3]。

步骤	$i$	$j$	比较	结果	动作
1	1	1	S[1]='a' vs T[1]='a'	✓	i++, j++
2	2	2	S[2]='b' vs T[2]='b'	✓	i++, j++
3	3	3	S[3]='a' vs T[3]='a'	✓	i++, j++
4	4	4	S[4]='a' vs T[4]='a'	✓	i++, j++
5	5	5	S[5]='b' vs T[5]='b'	✓	i++, j++
6	6	6	S[6]='c' vs T[6]='c'	✓	i++, j++, j=7 > T.length=6 → 匹配成功！

匹配位置 = $i - T.length = 7 - 6 = 1$。

再举一个需要回退的例子：$S$ = "abaacababc"，$T$ = "ababc"，$\text{next} = [0, 1, 1, 2, 1]$。

步骤	$i$	$j$	比较	结果	动作
1	1	1	a = a	✓	i=2, j=2
2	2	2	b = b	✓	i=3, j=3
3	3	3	a = a	✓	i=4, j=4
4	4	4	a ≠ b	✗	j = next[4] = 2（i 不动！利用已知 "a" 匹配信息）
5	4	2	a ≠ b	✗	j = next[2] = 1
6	4	1	a = a	✓	i=5, j=2
7	5	2	c ≠ b	✗	j = next[2] = 1
8	5	1	c ≠ a	✗	j = next[1] = 0，故 j==0 → i++, j++
9	6	1	a = a	✓	i=7, j=2
10	7	2	b = b	✓	i=8, j=3
11	8	3	a = a	✓	i=9, j=4
12	9	4	b = b	✓	i=10, j=5
13	10	5	c = c	✓	j=6 > 5 → 匹配成功！位置 = 10 - 5 = 6

💡 手算要诀：

1. 先单独求出 next 数组（对模式串 $T$ 逐位求最长相等真前后缀 + 1）
2. 模拟匹配时，$i$ 永远只增不减，失配时只动 $j$（$j = \text{next}[j]$）
3. 当 $j = 0$ 时，说明模式串第1个字符就不匹配，此时 $i$ 和 $j$ 都加1（开始新一轮比较）
4. 考试中常考比较次数：上例中匹配成功共比较了 13 次

⚠️ 2019年真题：KMP 匹配主串 S 和模式串 T，问比较次数。答案是 10 次——关键是准确执行上述步骤表。

KMP算法代码：

int Index_KMP(SString S, SString T, int next[]) {
    int i = 1, j = 1;
    while (i <= S.length && j <= T.length) {
        if (j == 0 || S.ch[i] == T.ch[j]) {
            i++; j++;
        } else {
            j = next[j];   // 模式串向右滑动，i不回溯
        }
    }
    if (j > T.length) return i - T.length;
    else return 0;
}

// KMP算法（Java下标从0开始）
// ⚠️ 考研代码陷阱⚠️：Java/C++代码题目中，字符串和next数组下标通常从0开始（next[0]=-1）。
// 而在考研理论选择题/填空题中，默认下标从1开始（next[1]=0）。
// 两者next值恰好差1。务必看清题目要求！
int indexKMP(String S, String T, int[] next) {
    int i = 0, j = 0;
    while (i < S.length() && j < T.length()) {
        if (j == -1 || S.charAt(i) == T.charAt(j)) {
            i++; j++;
        } else {
            j = next[j];  // 模式串向右滑动，i不回溯
        }
    }
    if (j >= T.length()) return i - T.length();
    else return -1;
}

// 求next数组（Java版，下标从0开始）
int[] getNext(String T) {
    int[] next = new int[T.length()];
    next[0] = -1;
    int i = 0, j = -1;
    while (i < T.length() - 1) {
        if (j == -1 || T.charAt(i) == T.charAt(j)) {
            i++; j++;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
    return next;
}

时间复杂度：$O(n+m)$

三、KMP的进一步优化——nextval数组

当 $T[j] = T[next[j]]$ 时，回退后仍然会失配，造成不必要的比较。优化后使用 nextval数组：

nextval 手工求法（先求 next，再优化）：

例：模式串 $T$ = "abaabcac"，next = [0, 1, 1, 2, 2, 3, 1, 2]

$j$	1	2	3	4	5	6	7	8
T[j]	a	b	a	a	b	c	a	c
next[j]	0	1	1	2	2	3	1	2
T[next[j]]	—	a	a	b	a	a	a	b
T[j]==T[next[j]]?	—	b≠a	a=a	a≠b	b≠a	c≠a	a=a	c≠b
nextval[j]	0	1	0	2	1	3	0	2

💡 手算规则：逐列检查 $T[j]$ 是否等于 $T[\text{next}[j]]$：

• 若不等：$\text{nextval}[j] = \text{next}[j]$（不优化）
• 若相等：$\text{nextval}[j] = \text{nextval}[\text{next}[j]]$（递归取值，因为回退后一定还会失配）
• $\text{nextval}[1]$ 固定为 0

// KMP nextval数组优化（Java版，下标从0开始）
int[] getNextVal(String T) {
    int[] next = getNext(T);
    int[] nextval = new int[T.length()];
    nextval[0] = -1;
    for (int j = 1; j < T.length(); j++) {
        if (T.charAt(j) == T.charAt(next[j]))
            nextval[j] = nextval[next[j]];
        else
            nextval[j] = next[j];
    }
    return nextval;
}

🗣️ 大白话：KMP算法的精髓是"别做无用功"。当你发现不匹配时，你已经知道前面一段是匹配的，所以不用从头来过，只需要利用模式串自身的重复结构"滑动"到合适位置继续比较。

📝 真题剖析

【2015年408真题】 已知字符串 $S$ 为 "abaabaabcabaabc"，模式串 $T$ 为 "abaabc"，采用KMP算法进行匹配，第一次出现"失配"（$S[i] \neq T[j]$）时，$i = j =$（）；

A. 3, 3   B. 5, 5   C. 6, 6   D. 4, 4

解析：

$S$: a b a a b a a b c a b a a b c $T$: a b a a b c

从 $i=1, j=1$ 开始逐字符比对：

• $i=1,j=1$: a=a ✓
• $i=2,j=2$: b=b ✓
• $i=3,j=3$: a=a ✓
• $i=4,j=4$: a=a ✓
• $i=5,j=5$: b=b ✓
• $i=6,j=6$: a≠c ✗ → 第一次失配，$i=6, j=6$

答案选C。

📌 第四章总结

核心知识点	考研要求
串的定义、子串概念	理解概念
朴素模式匹配（BF算法）	理解原理和复杂度
KMP算法原理	重中之重，必须完全掌握
next数组的手工求法	每年必考（选择题或大题）
nextval数组的求法	高频考点
KMP的时间复杂度 $O(n+m)$	牢记

---

第五章 树与二叉树

5.1 树的基本概念

一、树的定义

树（Tree）：$n$（$n \geq 0$）个结点的有限集合。$n=0$ 时称为空树。在任一非空树中：

1. 有且仅有一个特定的称为**根（Root）**的结点
2. 当 $n>1$ 时，其余结点可分为 $m$（$m>0$）个互不相交的有限集合 $T_1, T_2, \ldots, T_m$，其中每一个集合本身又是一棵树，称为根的子树（SubTree）

🗣️ 大白话：树就像一棵倒过来的真实的树——根在最上面，树枝往下分叉。一个根可以有很多树枝（子树），每个树枝又可以继续分叉。

二、基本术语

术语	定义	大白话
结点的度	结点拥有的子树数目	这个人有几个亲儿子
树的度	树中结点的最大度数	整棵树里儿子最多的那个人有几个儿子
叶子结点	度为0的结点	"绝后"的结点，没有儿子
分支结点	度不为0的结点	有儿子的结点
结点的层次	根为第1层，根的孩子为第2层，以此类推	第几代
树的高度（深度）	结点的最大层次	一共有几代人
路径	从结点 $a$ 到结点 $b$ 所经过的结点序列	从祖先到子孙走的路
路径长度	路径上经过的边的条数	走了几步
森林	$m$（$m \geq 0$）棵互不相交的树的集合	多棵树组成的树林

三、树的重要性质

1. 树中的结点数 $=$ 所有结点的度数之和 $+ 1$（即总边数 $+ 1$）

   证明：每条边对应一个非根结点（边连接父→子），故边数 = $n - 1$。又边数 = 所有结点度数之和（每条边由父结点的度贡献）。因此 $n - 1 = \sum d_i$，即 $n = \sum d_i + 1$。

2. 度为 $m$ 的树中第 $i$ 层上至多有 $m^{i-1}$ 个结点（$i \geq 1$）

3. 高度为 $h$ 的 $m$ 叉树至多有 $\frac{m^h - 1}{m - 1}$ 个结点（等比数列求和）

4. 具有 $n$ 个结点的 $m$ 叉树的最小高度为 $\lceil \log_m(n(m-1)+1) \rceil$

树的6个重要性质总结：

性质	公式/说明
结点数 = 总度数 + 1	$n = 1 + \sum_{i=1}^{m} i \cdot n_i$（$n_i$ 为度为 $i$ 的结点数）
第 $i$ 层最多结点数	$m^{i-1}$
高 $h$ 的 $m$ 叉树最多结点	$(m^h - 1)/(m-1)$
$n$ 个结点的 $m$ 叉树最小高	$\lceil \log_m(n(m-1)+1) \rceil$
叶子结点数公式	$n_0 = 1 + \sum_{i=2}^{m}(i-1)n_i$（由性质1推导）
$n$ 个结点的树边数	$n - 1$

⚠️ 度为 $m$ 的树 vs $m$ 叉树：

• 度为 $m$ 的树：至少有一个结点的度为 $m$（树中确实存在度为 $m$ 的结点）
• $m$ 叉树：每个结点的度最多为 $m$（允许所有结点度都小于 $m$，甚至可以是空树）
• 度为 $m$ 的树至少有 $m+1$ 个结点（根结点+$m$ 个孩子）；$m$ 叉树可以是空树

---

5.2 二叉树

一、二叉树的定义

二叉树（Binary Tree）：每个结点最多只有两棵子树，且子树有左右之分，次序不能颠倒。

五种基本形态：

1. 空二叉树
2. 只有根结点
3. 只有左子树
4. 只有右子树
5. 左右子树都有

特殊二叉树：

类型	定义	特点
满二叉树	所有分支结点都有两个孩子且叶子都在同一层	高度为 $h$ 的满二叉树有 $2^h - 1$ 个结点
完全二叉树	与满二叉树对比，只有最后一层可能不满，且最后一层结点从左到右连续	若有度为1的结点，则只有一个且它只有左孩子
二叉排序树（BST）	左子树所有结点值 < 根 < 右子树所有结点值	中序遍历得到递增序列
平衡二叉树（AVL）	任意结点的左右子树高度差的绝对值 ≤ 1	保证查找效率

二、二叉树的性质（高频考点！）

1. 非空二叉树上，叶子结点数 $n_0$ 与度为2的结点数 $n_2$ 的关系：

$n_0 = n_2 + 1$

🗣️ 大白话：叶子结点数 = 双分支结点数 + 1。这是二叉树最重要的公式之一！

证明：设 $n_0, n_1, n_2$ 分别为度为 0、1、2 的结点数。

• 结点总数：$n = n_0 + n_1 + n_2$
• 边数：$n - 1 = n_1 + 2n_2$（每个度为1的结点贡献1条边，度为2的贡献2条边）
• 两式相减：$1 = n_0 - n_2$，即 $n_0 = n_2 + 1$。

2. 非空二叉树第 $i$ 层上至多有 $2^{i-1}$ 个结点（$i \geq 1$）
3. 高度为 $h$ 的二叉树至多有 $2^h - 1$ 个结点
4. 完全二叉树的性质：
   • 具有 $n$ 个结点的完全二叉树的高度为 $\lfloor \log_2 n \rfloor + 1$ 或 $\lceil \log_2(n+1) \rceil$
   • 对完全二叉树按层序编号（从1开始），对于结点 $i$：
     • 其父结点为 $\lfloor i/2 \rfloor$（$i \neq 1$ 时）
     • 左孩子为 $2i$（$2i \leq n$ 时存在）
     • 右孩子为 $2i+1$（$2i+1 \leq n$ 时存在）
   • 若 $i \leq \lfloor n/2 \rfloor$，则结点 $i$ 是分支结点；否则是叶结点

💡 完全二叉树推算 $n_0, n_1, n_2$ 的技巧：

• 完全二叉树中，度为1的结点 $n_1$ 只可能是0或1
• 若 $n$ 为奇数：$n_1 = 0$，$n_0 = (n+1)/2$，$n_2 = (n-1)/2$
• 若 $n$ 为偶数：$n_1 = 1$，$n_0 = n/2$，$n_2 = n/2 - 1$
• 简记：$n_0 = \lceil n/2 \rceil$（完全二叉树的叶子数始终占总结点数的一半左右）

⚠️ 更快捷的方法（2011年真题）：完全二叉树的叶结点数 $= n - \lfloor n/2 \rfloor$。

• 例：768个结点的完全二叉树，最后一个分支结点序号 = $\lfloor 768/2 \rfloor = 384$，叶结点数 = $768 - 384 = 384$。

💡 度 $m$ 树求叶结点数公式：设度为 $i$ 的结点有 $n_i$ 个，总结点 $n = \sum n_i$，边数 $= n-1 = \sum i \cdot n_i$，可解出 $n_0$。

• 例（2010真题）：度4的树，$n_1=1, n_2=2, n_3=3, n_4=4$，边 $n-1 = 1+4+9+16=30$，$n=31$，$n_0=31-1-2-3-4=21$。⟹ 利用 $n_0 = 1 + \sum_{i=2}^{m}(i-1)n_i$ 快速计算。

三、二叉树的存储结构

顺序存储：用数组按层序编号存储（适合完全二叉树）

链式存储（二叉链表，最常用）：

typedef struct BiTNode {
    ElemType data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

class BiTNode {
    int data;
    BiTNode lchild, rchild;
    BiTNode(int data) {
        this.data = data;
        this.lchild = null;
        this.rchild = null;
    }
}

⚠️ 含 $n$ 个结点的二叉链表中有 $n + 1$ 个空链域（可利用这些空链域构成线索二叉树）。

⚠️ 完全二叉树编号陷阱（高频选择题！）：

• 结点 $i$ 的左孩子编号为 $2i$，右孩子为 $2i+1$，父结点为 $\lfloor i/2 \rfloor$
• 但上述公式仅适用于编号从1开始的情况！若编号从0开始，则左孩子 $2i+1$，右孩子 $2i+2$，父结点 $\lfloor (i-1)/2 \rfloor$
• 考试中必须注意题目编号起始是0还是1，否则全盘出错
• 判断结点 $i$ 是叶子：$2i > n$（编号从1开始时）
• 完全二叉树中度为1的结点最多1个，且若存在则只有左孩子

🔗 【跨学科联动·OS】 树结构在操作系统中常见应用：

• 文件系统目录结构：就是一棵树（根目录→子目录→文件），ls -R/tree 命令本质是树的遍历
• 进程树：Linux 中所有进程构成一棵以 init/systemd 为根的进程树，fork() 创建子进程就是添加子结点
• 页表：多级页表本质是一棵多叉树（如 x86 的 4 级页表）

---

5.3 二叉树的遍历

一、先序、中序、后序遍历

遍历方式	访问顺序	递归过程
先序遍历（Pre-order）	根→左→右	NLR
中序遍历（In-order）	左→根→右	LNR
后序遍历（Post-order）	左→右→根	LRN

// 先序遍历
void PreOrder(BiTree T) {
    if (T != NULL) {
        visit(T);            // 访问根结点
        PreOrder(T->lchild); // 递归遍历左子树
        PreOrder(T->rchild); // 递归遍历右子树
    }
}

// 中序遍历
void InOrder(BiTree T) {
    if (T != NULL) {
        InOrder(T->lchild);
        visit(T);
        InOrder(T->rchild);
    }
}

// 后序遍历
void PostOrder(BiTree T) {
    if (T != NULL) {
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        visit(T);
    }
}

// 先序遍历
void preOrder(BiTNode T) {
    if (T != null) {
        visit(T);
        preOrder(T.lchild);
        preOrder(T.rchild);
    }
}

// 中序遍历
void inOrder(BiTNode T) {
    if (T != null) {
        inOrder(T.lchild);
        visit(T);
        inOrder(T.rchild);
    }
}

// 后序遍历
void postOrder(BiTNode T) {
    if (T != null) {
        postOrder(T.lchild);
        postOrder(T.rchild);
        visit(T);
    }
}

时间复杂度：$O(n)$，空间复杂度：$O(h)$（$h$ 为树高，递归栈深度）

二、层序遍历（借助队列）

void LevelOrder(BiTree T) {
    InitQueue(Q);
    BiTree p;
    EnQueue(Q, T);           // 根结点入队
    while (!IsEmpty(Q)) {
        DeQueue(Q, p);       // 出队
        visit(p);
        if (p->lchild != NULL)  EnQueue(Q, p->lchild);
        if (p->rchild != NULL)  EnQueue(Q, p->rchild);
    }
}

void levelOrder(BiTNode T) {
    Queue<BiTNode> queue = new LinkedList<>();
    queue.offer(T);              // 根结点入队
    while (!queue.isEmpty()) {
        BiTNode p = queue.poll(); // 出队
        visit(p);
        if (p.lchild != null) queue.offer(p.lchild);
        if (p.rchild != null) queue.offer(p.rchild);
    }
}

三、由遍历序列构造二叉树（重要！）

已知哪些序列可以唯一确定一棵二叉树？

组合	能否唯一确定
先序 + 中序	✅ 能
后序 + 中序	✅ 能
层序 + 中序	✅ 能
先序 + 后序	❌ 不能

💡 核心规律：中序序列是必需的！因为中序序列能帮助确定左右子树的划分。先序/后序/层序确定根结点，中序确定左右子树范围。

⚠️ 先序 + 后序虽不能唯一确定二叉树，但能确定祖先关系：对于两个结点 $X$、$Y$，若前序中 $X$ 在 $Y$ 前且后序中 $Y$ 在 $X$ 前（即前序 $XY$，后序 $YX$），则 $X$ 是 $Y$ 的祖先。

• 2012年真题应用：前序 a,e,b,d,c，后序 b,c,d,e,a。前序 ae/后序 ea，可知 $a$ 是 $e$ 的祖先；前序 eb/后序 be，可知 $e$ 是 $b$ 的祖先。由此推出根 $a$ 的孩子只有 $e$。
• 特殊情况：若前序与后序恰好相反（如 1,2,3,4 和 4,3,2,1），则每个结点最多只有一个孩子，二叉树高度等于结点数。

构造方法（以"先序+中序"为例）：

1. 先序的第一个元素是根
2. 在中序中找到根，根左边是左子树，右边是右子树
3. 递归处理左右子树

---

5.4 线索二叉树

一、线索化的目的

普通二叉链表中有很多空指针（$n+1$ 个）。线索二叉树利用这些空指针存储前驱/后继信息，加速遍历。

typedef struct ThreadNode {
    ElemType data;
    struct ThreadNode *lchild, *rchild;
    int ltag, rtag;  // 0=指向孩子，1=指向线索（前驱/后继）
} ThreadNode, *ThreadTree;

class ThreadNode {
    int data;
    ThreadNode lchild, rchild;
    int ltag, rtag;  // 0=指向孩子，1=指向线索（前驱/后继）
    ThreadNode(int data) {
        this.data = data;
        this.lchild = null;
        this.rchild = null;
        this.ltag = 0;
        this.rtag = 0;
    }
}

• 当 ltag = 0 时，lchild 指向左孩子；当 ltag = 1 时，lchild 指向中序前驱
• 当 rtag = 0 时，rchild 指向右孩子；当 rtag = 1 时，rchild 指向中序后继

🗣️ 大白话：线索二叉树就是把原来浪费的空指针利用起来，存上"前一个是谁""后一个是谁"的信息，这样遍历时就不需要递归（不需要栈）了。

在线索二叉树中找前驱/后继的方法总结：

线索类型	找后继	找前驱
中序线索	若 rtag=1，后继 = rchild；若 rtag=0，后继 = 右子树最左下结点	若 ltag=1，前驱 = lchild；若 ltag=0，前驱 = 左子树最右下结点
先序线索	若 rtag=1，后继 = rchild；若有左孩子则后继 = 左孩子；否则后继 = 右孩子	较复杂，可能需要从根重新遍历或使用三叉链表
后序线索	较复杂，可能需要从根重新遍历或使用三叉链表	若 ltag=1，前驱 = lchild；若有右孩子则前驱 = 右孩子；否则前驱 = 左孩子

⚠️ 考研重点：中序线索二叉树的操作最常考。先序线索找前驱、后序线索找后继比较困难，可能需要三叉链表（增加parent指针）。有时考题会问"哪种线索二叉树不能直接找到某类前驱/后继"。

"三次路过"法理解遍历：在二叉树的递归遍历过程中，每个结点会被"路过"三次：

1. 第一次路过时访问 → 先序遍历
2. 第二次路过时访问 → 中序遍历
3. 第三次路过时访问 → 后序遍历

💡 用"三次路过"法可以快速确定任意遍历序列：沿着树的外轮廓画一条线，每个结点被线"路过"三次，按照先/中/后的规则决定何时访问即可。

---

5.5 树、森林

一、树的存储结构

存储方式	说明
双亲表示法	每个结点存储其父结点的位置（数组实现），找父亲 $O(1)$，找孩子 $O(n)$
孩子表示法	每个结点有一个链表指向所有孩子
孩子兄弟表示法	每个结点有两个指针：一个指向第一个孩子，一个指向下一个兄弟

💡 孩子兄弟表示法本质上就是用二叉树来存储树/森林！

二、树、森林与二叉树的转换

树 → 二叉树：

1. 在所有兄弟之间加一条连线
2. 对每个结点，只保留与第一个孩子的连线，删除与其他孩子的连线
3. 以根为轴心顺时针旋转 45°

森林 → 二叉树：

1. 先把每棵树转换为二叉树
2. 把每棵二叉树的根相连（后一棵作为前一棵根的右子树）

⚠️ 树转二叉树后"无右孩子"的结点数（2011年真题核心考点）：

在孩子兄弟法中，右指针指向"下一个兄弟"。无右孩子 = 没有下一个兄弟 = 每组兄弟中的最后一个。设树有 $n$ 个结点、$p$ 个分支结点（非叶结点），则有 $p$ 组兄弟（每个分支结点的所有孩子构成一组），每组最后一个没有右兄弟，加上根结点也没有右兄弟，所以：

$\text{无右孩子的结点数} = p + 1 = \text{分支结点数} + 1$

例：2011 年真题——2011个结点、116个叶结点的树，分支结点数 $= 2011 - 116 = 1895$，无右孩子结点数 $= 1895 + 1 = 1896$。

三、树和森林的遍历

树的遍历	对应的二叉树遍历
树的先根遍历	对应二叉树的先序遍历
树的后根遍历	对应二叉树的中序遍历

森林的遍历	对应的二叉树遍历
森林的先序遍历	对应二叉树的先序遍历
森林的中序遍历	对应二叉树的中序遍历

---

5.6 哈夫曼树与哈夫曼编码

一、哈夫曼树（最优二叉树）

带权路径长度WPL：

$WPL = \sum_{i=1}^{n} w_i \times l_i$

其中 $w_i$ 是第 $i$ 个叶子结点的权值，$l_i$ 是该叶子到根的路径长度。

哈夫曼树：在含有 $n$ 个带权叶子结点的二叉树中，WPL最小的二叉树称为哈夫曼树。

构造方法（贪心策略）：

1. 将 $n$ 个权值作为 $n$ 棵只含根结点的树，构成森林 $F$
2. 从 $F$ 中选取权值最小的两棵树，合并为一棵新树（根的权值为两棵子树之和）
3. 从 $F$ 中删除这两棵树，加入新树
4. 重复2-3，直到只剩一棵树

哈夫曼树的特点：

• 没有度为1的结点（每个内部结点的度都为2）
• $n$ 个叶子结点的哈夫曼树共有 $2n-1$ 个结点
• 哈夫曼树不唯一（左右子树可以互换），但WPL唯一
• 哈夫曼树不一定是完全二叉树（2010年真题考点！）
• 两个权值最小的结点一定是兄弟结点
• 任一非叶结点的权值一定不小于下一层任一结点的权值（因为非叶结点权值 = 左右子树权值之和）

二、哈夫曼编码

• 将字符的使用频率作为权值构建哈夫曼树
• 左分支标记为0，右分支标记为1
• 从根到叶子的路径上标记序列即为该字符的编码
• 哈夫曼编码是前缀编码（任何一个编码都不是其他编码的前缀）

🗣️ 大白话：使用频率高的字符用短编码，频率低的用长编码。这样总的编码长度最短——这就是数据压缩的基本原理。

📝 树的真题高频考点汇编

【WPL计算】 2021年真题：$n$ 个叶子权值 $\{10, 12, 16, 21, 30\}$，最小WPL？

构造哈夫曼树：$10+12=22$，$16+21=37$，$22+30=52$，$37+52=89$？不对。实际最优：$WPL = 2\times(16+21+30) + 3\times(10+12) = 134+66 = 200$。答案200。

💡 WPL 计算也可用"内结点权值之和"法：每个内部结点权值 = 左右子树的权值之和，WPL = 所有内部结点的权值之和。

【哈夫曼编码平均长度】 2023年真题：频次 $\{3,4,5,6,8,10\}$，加权平均编码长度？

$\frac{(3+4+5+6)\times 3 + (8+10)\times 2}{3+4+5+6+8+10} = \frac{54+36}{36} = 2.5$

【$k$ 叉哈夫曼树（多叉哈夫曼树）】 2013年真题考点：

⚠️ $k$ 叉哈夫曼树的构造要点：

1. 虚段补充判断：若 $(n_0 - 1) \% (k-1) \neq 0$，需补 $(k-1) - (n_0-1)\%(k-1)$ 个权值为0的虚叶结点
2. 每次从当前所有结点中选取权值最小的 $k$ 个合并
3. 第一次合并时，若需补虚段，先合并虚段+最小权值结点

例：权值 $\{1, 3, 5, 7, 9\}$，构造三叉哈夫曼树。$n_0=5$，$(5-1)\%(3-1)=0$，无需补虚段。

• 第1次合并：$\{1, 3, 5\}$ → $9'$，剩余 $\{7, 9, 9'\}$，WPL贡献 $(1+3+5)\times$ 深度
• 第2次合并：$\{7, 9, 9'\}$ → $25$
• WPL = $(1+3+5)\times 2 + (7+9)\times 1 = 18 + 16 = 34$

【2013年408真题】 在 BST 中删除某结点后再将其插入，是否能恢复原来的 BST？

答案：不一定能恢复。 若被删除的结点有两个子树，删除操作会用中序后继（或前驱）替代该结点，树的结构已经改变。重新插入原结点后，它会被插入为叶结点（BST插入总是在叶结点位置），树的形态与原来不同。

💡 只有被删结点是叶结点或仅有一个子树时，删后重新插入才能恢复原树。

【BST的顺序存储验证】 2022年真题·应用题：用数组保存二叉树（data[]），空节点值为-1，判断是否为BST。

方法：中序遍历检查是否升序。数组中第 $i$ 个结点的左/右孩子分别在 $2i+1$ 和 $2i+2$（下标从0开始）。用递归中序遍历即可实现。

【完全二叉树的数组编号】 考研高频考点：

• 结点 $i$ 的父结点：$\lfloor (i-1)/2 \rfloor$（下标从0开始）或 $\lfloor i/2 \rfloor$（下标从1开始）
• 结点 $i$ 的左孩子：$2i+1$（从0）或 $2i$（从1）
• 结点 $i$ 的右孩子：$2i+2$（从0）或 $2i+1$（从1）

【森林中树的棵数的确定】 2021年真题：森林 $F$ 对应的二叉树 $T$，已知 $T$ 的后序遍历和中序遍历，求 $F$ 中树的棵数。

关键公式：由二叉树的后序+中序可唯一确定二叉树结构。确定 $T$ 后，$T$ 的根的右子树链长度 $+1$ = 森林中树的棵数（根的右链对应森林中各棵树的根）。

【度为 $k$ 的正则树的叶结点数公式】 2016年真题考点：

设度为 $k$ 的正则树有 $m$ 个非叶结点（每个非叶结点的度恰好为 $k$），则叶结点数为：

$n_0 = (k-1) \times m + 1$

💡 利用 $n = n_0 + m$ 和 $n - 1 = k \times m$（总边数），联立即得。

【二叉树先序=中序 → 仅有右子女】 2017年真题考点：若一棵二叉树的先序遍历和中序遍历完全相同，则该树中任何结点都没有左孩子（退化为右斜树）。

---

5.7 并查集

并查集（Union-Find）：一种用于管理元素分组的数据结构，支持两种操作：

• Find(x)：查找元素 $x$ 属于哪个集合（返回根结点）
• Union(x, y)：将 $x$ 和 $y$ 所在的集合合并

用双亲表示法（数组）实现：

int UFSets[SIZE];  // 初始化:每个元素的父结点为-1(自己是根)

// 查找x所属集合(返回根)
int Find(int UFSets[], int x) {
    while (UFSets[x] >= 0)
        x = UFSets[x];
    return x;
}

// 合并x和y所在的集合
void Union(int UFSets[], int Root1, int Root2) {
    UFSets[Root2] = Root1;  // 将Root2连到Root1下面
}

class UnionFind {
    int[] parent;  // 初始化每个元素的父结点为-1(自己是根)

    UnionFind(int size) {
        parent = new int[size];
        Arrays.fill(parent, -1);
    }

    // 查找x所属集合(返回根)
    int find(int x) {
        while (parent[x] >= 0)
            x = parent[x];
        return x;
    }

    // 合并x和y所在的集合
    void union(int root1, int root2) {
        parent[root2] = root1;
    }
}

优化：

1. 按秩合并（Union by Rank）：小树合并到大树下，避免退化为链
2. 路径压缩（Path Compression）：查找时将路径上的结点直接连到根下

// 路径压缩的Find
int Find(int UFSets[], int x) {
    int root = x;
    while (UFSets[root] >= 0)
        root = UFSets[root];
    while (x != root) {
        int t = UFSets[x];
        UFSets[x] = root;  // 路径上所有结点直接指向根
        x = t;
    }
    return root;
}

// 路径压缩的Find
int findWithPathCompression(int x) {
    int root = x;
    while (parent[root] >= 0)
        root = parent[root];
    while (x != root) {
        int t = parent[x];
        parent[x] = root;  // 路径上所有结点直接指向根
        x = t;
    }
    return root;
}

优化后 Find 和 Union 的时间接近 $O(1)$（严格来说是 $O(\alpha(n))$，其中 $\alpha$ 是阿克曼函数的反函数，对任何实际可能的 $n$，$\alpha(n) \leq 4$，可视为常数）。

💡 并查集优化效果对比：

实现方式	Find 时间	Union 时间
无优化	$O(n)$（最坏，退化为链）	$O(1)$
仅按秩合并	$O(\log n)$	$O(1)$
仅路径压缩	均摊 $O(\alpha(n))$	$O(1)$
按秩合并 + 路径压缩	均摊 $O(\alpha(n))$	$O(1)$

⚠️ 考研注意：并查集中 Union 操作的时间复杂度取决于 Find（需要先找到根才能合并），严格来说 Union 的时间 = 两次 Find 时间 + $O(1)$。

📝 真题剖析

【2017年408真题】 对于一棵有 $n$ 个结点、度为4的树，若用孩子兄弟表示法转换为二叉树 $T_b$，则 $T_b$ 中无右孩子的结点个数为（）。

A. 1   B. $n/2$   C. $n/4$   D. 与树的形态有关

解析：

在孩子兄弟表示法中：

• 左指针指向"第一个孩子"
• 右指针指向"下一个兄弟"

无右孩子的结点 = 没有"下一个兄弟"的结点。在原树中，每组兄弟中最后一个没有下一个兄弟。

树中有 $n$ 个结点，边数 = $n - 1$。每条边对应一个"孩子"关系。在兄弟链中，每组兄弟的第一个不通过"兄弟"关系连接，而是通过"孩子"关系。

设树中有 $p$ 个分支结点（有孩子的结点），那就有 $p$ 组兄弟。每组兄弟中最后一个结点无右孩子，加上根结点也无右孩子（根没有兄弟），所以无右孩子的结点 = 分支结点数 + 1。

但实际上更直接的分析：在原树中，每个结点要么有下一个兄弟（有右孩子），要么没有。没有下一个兄弟的结点 = 每组兄弟中的最后一个。树中共有 $n$ 个结点，其中 $n-1$ 个结点有"上一个兄弟或是父亲的第一个孩子"关系。每组兄弟的最后一个结点就是"没有下一个兄弟"的。设分支结点数为 $p$，则这样的结点有 $p$ 个（每个分支结点的最后一个孩子）加上根结点 = $p + 1$。但这与树的具体形态有关吗？

实际上，$n$ 个结点的树转成的二叉树中，没有右孩子的结点恰好等于原树中每个结点的最后一个孩子的数量 + 根结点 = 分支结点数 + 1。而不同形态的树会有不同的分支结点数。

不过，本题答案为 A. 1 吗？不，仔细看——原题说的是"$n$ 个结点"的树。

重新分析：无右孩子 = 没有下一个兄弟的结点个数。每个非叶结点有若干孩子，最后一个孩子没有下一个兄弟。所以无右孩子结点数 = 非叶结点数（即分支结点数）$+ 1$（根也没有右兄弟）。但 $n_0 + n_1 + n_2 + n_3 + n_4 = n$ 且边数 $= n-1 = n_1 + 2n_2 + 3n_3 + 4n_4$，这与具体形态有关。

答案选A（无右孩子的结点个数 = $n$ 减去有右兄弟的结点数 = $n - (n-1-$ 叶子结点中非末尾的$)$...）

实际本题的正确答案考虑到无右孩子的结点 = 有"最后一个孩子"身份的结点 + 根结点。

本题答案与树的形态有关，答案是A不对。实际上应该是每个节点的最后一个孩子没有右兄弟，因此没有右孩子的节点个数=分支结点个数+1（根也没有右兄弟）。答案为 $n-$ 非最后孩子节点数。这与具体的树的形态有关。但正确答案应该是 A：1（不对）。让我们重新查看：实际上无右孩子指的是没有下一个兄弟。总结点数 $n$，有兄弟关系的边数 = $n - 1 -$ 分支结点数（每个分支结点贡献"孩子数-1"条兄弟边）。所以有右孩子的结点 = $\sum(d_i - 1) =$ 边数 $-$ 分支结点数 $= n - 1 - p$，无右孩子 = $n - (n-1-p) = p + 1$。这取决于分支结点数 $p$。所以答案选D。

📌 第五章总结

核心知识点	考研要求
树的定义、基本术语	必须牢记
二叉树的性质（$n_0 = n_2 + 1$ 等）	高频考点，每年必考
完全二叉树的性质（父子编号关系）	必须掌握
二叉树的先中后序遍历（递归实现）	重中之重
层序遍历（借助队列）	需要掌握
由遍历序列构造二叉树	大题常考
线索二叉树	理解概念，掌握构造方法
树、森林与二叉树的转换	高频考点
树/森林的遍历与对应二叉树遍历的关系	必须掌握
哈夫曼树的构造与WPL计算	常考
哈夫曼编码	需要掌握
并查集（Find & Union 操作）	近年热门考点

---

第六章 图

6.1 图的基本概念

一、图的定义

图（Graph）：由顶点集 $V$ 和边集 $E$ 组成。记作 $G=(V, E)$，其中 $V(G)$ 是顶点的有穷非空集合，$E(G)$ 是边的有穷集合。

⚠️ 注意：图的顶点集 $V$ 必须非空（至少有一个顶点），但边集 $E$ 可以为空。

有向图 vs 无向图：

类型	边的表示	特点
无向图	$(v_i, v_j)$	边没有方向，$(v_i, v_j) = (v_j, v_i)$
有向图	$\langle v_i, v_j \rangle$	弧有方向，$\langle v_i, v_j \rangle \neq \langle v_j, v_i \rangle$

🗣️ 大白话：无向图就像微信好友——你加了我，我们互相是好友；有向图就像微博关注——我关注你，但你不一定关注我。

二、图的基本术语

术语	定义
邻接	有边/弧相连的两个顶点
度	与该顶点关联的边数。有向图分入度和出度
路径	从顶点 $v_p$ 到 $v_q$ 的顶点序列
路径长度	路径上边的数目
回路（环）	起点和终点相同的路径
简单路径	路径中顶点不重复出现
连通	无向图中两顶点有路径
强连通	有向图中两顶点互有路径
连通图	图中任意两顶点都连通
连通分量	无向图的极大连通子图
强连通分量	有向图的极大强连通子图
生成树	连通图的极小连通子图（包含全部顶点和 $n-1$ 条边）

重要公式：

• 无向图：$\sum\limits_{i=1}^{n} TD(v_i) = 2|E|$（每条边贡献两个端点各1度）
• 有向图：$\sum ID(v_i) = \sum OD(v_i) = |E|$
• 无向完全图边数：$C_n^2 = \frac{n(n-1)}{2}$
• 有向完全图弧数：$2C_n^2 = n(n-1)$
• 连通图至少需要 $n-1$ 条边（即生成树）
• 强连通图至少需要 $n$ 条弧（形成一个环）
• 若无向图边数 $|E| > n-1$，则图中一定有回路
• $n$ 个顶点的连通图最多 $\frac{(n-1)(n-2)}{2} + 1$ 条边（$n-1$ 个顶点完全图 + 1个顶点连1条边）

⚠️ 2010年真题考点：$n$ 个顶点的无向图要保证在任何情况下都连通（即无论边怎么分布都连通），最少需要 $C_{n-1}^2 + 1 = \frac{(n-1)(n-2)}{2} + 1$ 条边。

思路：先让 $n-1$ 个顶点构成完全图 $K_{n-1}$（需 $\frac{(n-1)(n-2)}{2}$ 条边），此时第 $n$ 个顶点还是孤立的。再加1条边将第 $n$ 个顶点连上，共 $\frac{(n-1)(n-2)}{2}+1$ 条边。例如7个顶点时：$C_6^2 + 1 = 15 + 1 = 16$。

特殊图：

• 简单图：不存在重复边，也不存在顶点到自身的边（考研中只讨论简单图）
• 多重图：两个顶点之间边数多于一条或有顶点到自身的边
• 完全图：任意两个顶点之间都存在边
• 稀疏图：边数很少（$|E| < |V| \log |V|$），用邻接表存储
• 稠密图：边数很多，用邻接矩阵存储
• 有向无环图（DAG）：没有环路的有向图
• 树：不存在回路且连通的无向图。$n$ 个顶点的树有且仅有 $n-1$ 条边
• 有向树：一个顶点入度为0，其余顶点入度为1的有向图

⚠️ 易错点：连通分量是无向图的极大连通子图（不能再加入任何顶点/边仍连通）；生成树是连通图的极小连通子图（再删任何一条边就不连通）。

---

6.2 图的存储结构

一、邻接矩阵

用二维数组 $A[n][n]$ 存储图，$A[i][j] = 1$ 表示存在边，$A[i][j] = 0$ 表示不存在。

#define MaxVertexNum 100
typedef struct {
    char Vex[MaxVertexNum];                   // 顶点表
    int Edge[MaxVertexNum][MaxVertexNum];      // 邻接矩阵
    int vexnum, arcnum;                        // 顶点数和边数
} MGraph;

class MGraph {
    static final int MaxVertexNum = 100;
    char[] vex = new char[MaxVertexNum];                       // 顶点表
    int[][] edge = new int[MaxVertexNum][MaxVertexNum];        // 邻接矩阵
    int vexnum, arcnum;                                        // 顶点数和边数
}

特点：

• 空间复杂度：$O(|V|^2)$，与边数无关
• 无向图的邻接矩阵是对称矩阵，可采用压缩存储（只存下三角）
• 无向图第 $i$ 行（或列）非零元素个数 $=$ 顶点 $v_i$ 的度
• 有向图第 $i$ 行非零元素个数 $=$ $OD(v_i)$；第 $i$ 列非零元素个数 $=$ $ID(v_i)$
• 适合稠密图
• 求度的时间复杂度：$O(|V|)$

💎 重要性质：设 $A$ 为图 $G$ 的邻接矩阵，则 $A^n[i][j]$ 等于从顶点 $i$ 到顶点 $j$ 的长度为 $n$ 的路径的数目。这是一个经典的考点。

⚠️ 2012年真题考点：若用邻接矩阵存储有向图，且主对角线以下的元素均为零（即上三角矩阵），则：

• 该图一定无环（不存在从编号大的顶点到编号小的顶点的边）
• 一定存在拓扑序列
• 但拓扑序列可能不唯一（多个顶点可能同时入度为0）

反之，若图存在拓扑序列，通过适当调整顶点编号，总可以使邻接矩阵满足上三角形式。

二、邻接表

为每个顶点建立一个单链表，链表中的结点表示与该顶点邻接的顶点。

// 边表结点
typedef struct ArcNode {
    int adjvex;            // 邻接点在数组中的位置
    struct ArcNode *next;
} ArcNode;

// 顶点表结点
typedef struct VNode {
    char data;             // 顶点信息
    ArcNode *first;        // 指向第一个邻接点
} VNode, AdjList[MaxVertexNum];

// 用邻接表存储的图
typedef struct {
    AdjList vertices;
    int vexnum, arcnum;
} ALGraph;

// 边表结点
class ArcNode {
    int adjvex;         // 邻接点在数组中的位置
    ArcNode next;
}
// 顶点表结点
class VNode {
    char data;          // 顶点信息
    ArcNode first;      // 指向第一个邻接点
}
// 用邻接表存储的图
class ALGraph {
    VNode[] vertices = new VNode[100];
    int vexnum, arcnum;
}

特点：

• 空间复杂度：无向图 $O(|V|+2|E|)$（每条边存两次），有向图 $O(|V|+|E|)$
• 适合稀疏图
• 邻接表不唯一（各边结点的链接顺序可以不同）
• 对于有向图，求顶点入度需遍历整个邻接表（不方便），求出度只需遍历该顶点的边链表

三、十字链表与邻接多重表

• 十字链表：有向图的一种链式存储，方便求顶点的入度和出度。空间 $O(|V|+|E|)$
• 邻接多重表：无向图的一种链式存储，方便对边的删除等操作。空间 $O(|V|+|E|)$

十字链表结点结构（有向图专用）：

弧结点：| tailvex | headvex | hlink | tlink | info |
         弧尾顶点   弧头顶点  弧头相同   弧尾相同  权值
                             的下条弧   的下条弧

顶点结点：| data | firstin | firstout |
                  第一条     第一条
                  入弧       出弧

💡 沿 firstout→tlink 链可遍历该顶点所有出弧（求出度）；沿 firstin→hlink 链可遍历该顶点所有入弧（求入度）。

邻接多重表结点结构（无向图专用）：

边结点：| mark | ivex | ilink | jvex | jlink | info |
        访问标记  顶点i  依附i的   顶点j  依附j的   权值
                       下条边          下条边

💡 每条边只存一个边结点（vs 邻接表中无向边存两次），删边只需 $O(1)$。mark 字段用于标记该边是否已被搜索过。

四种存储结构对比：

	邻接矩阵	邻接表	十字链表	邻接多重表
适用图	有向/无向	有向/无向	有向图	无向图
空间	$O(\|V\|^2)$	$O(\|V\|+\|E\|)$	$O(\|V\|+\|E\|)$	$O(\|V\|+\|E\|)$
适合	稠密图	稀疏图	稀疏有向图	稀疏无向图
表示唯一？	✅ 唯一	❌ 不唯一	✅ 唯一	❌ 不唯一
删边方便？	✅ $O(1)$	❌ 需遍历	✅ 方便	✅ 方便
求度方便？	需遍历行/列	出度方便，入度不便	入度出度都方便	度方便

图的基本操作时间复杂度对比：

操作	邻接矩阵	邻接表
判断边是否存在	$O(1)$	$O(1)\sim O(\|V\|)$
求某顶点的所有邻接点	$O(\|V\|)$	$O(该顶点的度)$
插入/删除顶点	$O(\|V\|)$	$O(1)\sim O(\|E\|)$
插入边	$O(1)$	$O(1)$
删除边	$O(1)$	$O(\|V\|)$

---

6.3 图的遍历

一、广度优先搜索（BFS）

思想：类似于层序遍历。从某个顶点出发，先访问所有邻接点，再访问邻接点的邻接点。借助队列实现。

void BFS(Graph G, int v) {
    visit(v);
    visited[v] = TRUE;
    EnQueue(Q, v);
    while (!IsEmpty(Q)) {
        DeQueue(Q, v);
        for (w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)) {
            if (!visited[w]) {
                visit(w);
                visited[w] = TRUE;
                EnQueue(Q, w);
            }
        }
    }
}

// BFS（邻接表实现）
void bfs(List<List<Integer>> graph, int v, boolean[] visited) {
    Queue<Integer> queue = new LinkedList<>();
    visited[v] = true;
    queue.offer(v);
    while (!queue.isEmpty()) {
        int u = queue.poll();
        visit(u);
        for (int w : graph.get(u)) {
            if (!visited[w]) {
                visited[w] = true;
                queue.offer(w);
            }
        }
    }
}

时间复杂度：

• 邻接矩阵：$O(|V|^2)$
• 邻接表：$O(|V|+|E|)$

空间复杂度：$O(|V|)$（队列大小）

BFS的应用：

1. BFS 求无权图的单源最短路径（核心应用）

在 BFS 过程中维护两个辅助数组：

• d[]：记录各顶点到源点的最短路径长度（初始化为 $\infty$）
• path[]：记录最短路径上的前驱顶点（初始化为 -1）

void BFS_MIN_Distance(Graph G, int u) {
    // d[i]表示从u到i的最短路径长度
    for (int i = 0; i < G.vexnum; i++) {
        d[i] = INF;       // 初始化为无穷
        path[i] = -1;     // 前驱初始化为-1
    }
    d[u] = 0;
    visited[u] = TRUE;
    EnQueue(Q, u);
    while (!IsEmpty(Q)) {
        DeQueue(Q, v);
        for (w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)) {
            if (!visited[w]) {
                d[w] = d[v] + 1;     // 路径长度加1
                path[w] = v;          // 记录前驱
                visited[w] = TRUE;
                EnQueue(Q, w);
            }
        }
    }
}

void bfsMinDist(List<List<Integer>> graph, int u) {
    int n = graph.size();
    int[] d = new int[n];
    int[] path = new int[n];
    boolean[] visited = new boolean[n];
    Arrays.fill(d, Integer.MAX_VALUE);
    Arrays.fill(path, -1);
    d[u] = 0;
    visited[u] = true;
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(u);
    while (!queue.isEmpty()) {
        int v = queue.poll();
        for (int w : graph.get(v)) {
            if (!visited[w]) {
                d[w] = d[v] + 1;
                path[w] = v;
                visited[w] = true;
                queue.offer(w);
            }
        }
    }
}

通过 path[] 数组可以逆序追溯得到完整最短路径。

2. BFS 生成树与生成森林

• 对连通图进行 BFS，可得到一棵BFS 生成树（即广度优先生成树）

• 对非连通图，每个连通分量调用一次 BFS，得到BFS 生成森林

• 邻接矩阵存储的图，BFS 生成树唯一；邻接表存储的图，BFS 生成树不唯一

3. 判断连通分量数

BFS 函数的调用次数 = 连通分量的个数（无向图）

二、深度优先搜索（DFS）

思想：类似于先序遍历。从某个顶点出发，沿着一条路径走到底，走不下去了就回溯。借助栈（递归即隐式栈）实现。

void DFS(Graph G, int v) {
    visit(v);
    visited[v] = TRUE;
    for (w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)) {
        if (!visited[w])
            DFS(G, w);
    }
}

// DFS（邻接表实现）
void dfs(List<List<Integer>> graph, int v, boolean[] visited) {
    visit(v);
    visited[v] = true;
    for (int w : graph.get(v)) {
        if (!visited[w])
            dfs(graph, w, visited);
    }
}

时间复杂度：

• 邻接矩阵：$O(|V|^2)$
• 邻接表：$O(|V|+|E|)$

空间复杂度：$O(|V|)$（递归栈深度）

DFS的特性：

• 对连通图 DFS → DFS 生成树；对非连通图 → DFS 生成森林
• DFS 的调用次数 = 连通分量个数（无向图）
• DFS 可用于判断图中是否有回路
• DFS 算法的逆后序就是有向无环图的拓扑排序
• 对有向图 DFS，在顶点退栈前输出，得到的序列是逆拓扑排序序列

BFS vs DFS 对比：

	BFS	DFS
数据结构	队列	栈（递归栈）
类似树遍历	层序遍历	先根遍历
适合问题	最短路径、层次相关	连通性、回路检测
空间复杂度	$O(\|V\|)$	$O(\|V\|)$
生成树特点	高度最小	高度可能较大

🗣️ 大白话：BFS 就像水波扩散——从石头入水的地方一圈一圈往外扩；DFS 就像走迷宫——一条路走到黑，走不通就退回来换一条路。BFS生成树是从起点出发"最矮"的树（高度最小）。

🔗 【跨学科联动·计网/OS】 图的算法在408其他学科中有大量应用：

• 计网·路由算法：OSPF 协议使用 Dijkstra 算法求最短路径；RIP 协议使用距离向量算法（类似 Bellman-Ford）
• 计网·网络拓扑：计算机网络本身就是一张图，交换机/路由器是顶点，链路是边
• OS·死锁检测：用资源分配图（有向图）检测死锁——找图中是否有环（DFS 检测）
• OS·进程调度：优先级队列（堆）用于调度，而拓扑排序可用于任务依赖分析

---

6.4 图的应用

一、最小生成树（MST）

定义：连通图的生成树中，边的权值之和最小的生成树。

Prim算法：从某顶点开始，每次选择一条连接已选顶点集与未选顶点集的最小权值边。

• 时间复杂度：$O(|V|^2)$
• 适合稠密图

【Prim 算法手工模拟示例】

设图有 5 个顶点 $V_0 \sim V_4$，从 $V_0$ 出发。邻接矩阵（∞ 表示不相邻）：

	$V_0$	$V_1$	$V_2$	$V_3$	$V_4$
$V_0$	0	4	3	∞	7
$V_1$	4	0	2	5	∞
$V_2$	3	2	0	1	8
$V_3$	∞	5	1	0	6
$V_4$	7	∞	8	6	0

轮次	已选集合 $S$	各未选顶点的 lowCost（到 $S$ 的最短边）	选中顶点	选中边权
初始	{$V_0$}	$V_1$:4, $V_2$:3, $V_3$:∞, $V_4$:7	$V_2$	3
1	{$V_0, V_2$}	$V_1$:2(←$V_2$), $V_3$:1(←$V_2$)... 实际 $V_3$:1	$V_3$	1
2	{$V_0, V_2, V_3$}	$V_1$:2(←$V_2$), $V_4$:6(←$V_3$)	$V_1$	2
3	{$V_0, V_2, V_3, V_1$}	$V_4$:6(←$V_3$)	$V_4$	6

MST 边集：{$(V_0,V_2,3)$, $(V_2,V_3,1)$, $(V_2,V_1,2)$, $(V_3,V_4,6)$}，总权值 = 3+1+2+6 = 12

💡 手算要点：每轮更新 lowCost 时，只需检查新加入顶点的邻边是否比当前 lowCost 更小。

Kruskal算法：将所有边按权值从小到大排序，依次选择不构成环的最小边。

• 时间复杂度：$O(|E| \log |E|)$
• 适合稀疏图

🗣️ 大白话：

• Prim：从一个城市出发，每次修一条到最近的还没连通的城市的路。（以"点"为核心）
• Kruskal：把所有可能修的路按长度排序，从最短的开始修，但不能修出环路。（以"边"为核心）

二、最短路径

1. BFS算法（无权图）

适用于求无权图的单源最短路径，时间 $O(|V|+|E|)$。就是对 BFS 的小修改：在 visit 一个顶点时，修改其最短路径长度 d[] 并在 path[] 记录前驱结点（详见 6.3 节 BFS 应用部分）。

2. Dijkstra算法（单源最短路径）

适用：边权值非负的带权图（有向/无向均可）

思想：贪心。维护三个辅助数组：

• final[]：标记各顶点是否已找到最短路径（布尔数组）
• dist[]：当前已知的从源点到各顶点的最短路径长度
• path[]：各顶点最短路径上的前驱

算法步骤（设从 $V_0$ 出发）：

1. 初始化：final[0]=true; dist[0]=0。对其余顶点 $k$：final[k]=false; dist[k]=arcs[0][k]; path[k]=(arcs[0][k]<∞)?0:-1
2. 循环 $n-1$ 轮：
   • 从所有 final[i]==false 的顶点中选 dist 值最小的顶点 $V_i$，令 final[i]=true
   • 检查 $V_i$ 的所有邻接点 $V_j$：若 final[j]==false 且 dist[i]+arcs[i][j]<dist[j]，则更新 dist[j]=dist[i]+arcs[i][j]; path[j]=i

// Dijkstra算法（邻接矩阵）
void Dijkstra(MGraph G, int v0) {
    int n = G.vexnum;
    for (int i = 0; i < n; i++) {
        final_arr[i] = FALSE;
        dist[i] = G.Edge[v0][i];
        path[i] = (dist[i] < INF) ? v0 : -1;
    }
    final_arr[v0] = TRUE; dist[v0] = 0; path[v0] = -1;
    for (int i = 1; i < n; i++) {       // n-1轮
        int min = INF, u = -1;
        for (int j = 0; j < n; j++)     // 找dist最小的未确定顶点
            if (!final_arr[j] && dist[j] < min) { min = dist[j]; u = j; }
        if (u == -1) return;
        final_arr[u] = TRUE;
        for (int w = 0; w < n; w++)     // 更新邻接点
            if (!final_arr[w] && dist[u] + G.Edge[u][w] < dist[w]) {
                dist[w] = dist[u] + G.Edge[u][w];
                path[w] = u;
            }
    }
}

void dijkstra(int[][] graph, int v0) {
    int n = graph.length;
    boolean[] fin = new boolean[n];
    int[] dist = new int[n];
    int[] path = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    Arrays.fill(path, -1);
    for (int i = 0; i < n; i++)
        if (graph[v0][i] != Integer.MAX_VALUE) { dist[i] = graph[v0][i]; path[i] = v0; }
    fin[v0] = true; dist[v0] = 0;
    for (int i = 1; i < n; i++) {
        int min = Integer.MAX_VALUE, u = -1;
        for (int j = 0; j < n; j++)
            if (!fin[j] && dist[j] < min) { min = dist[j]; u = j; }
        if (u == -1) return;
        fin[u] = true;
        for (int w = 0; w < n; w++)
            if (!fin[w] && graph[u][w] != Integer.MAX_VALUE && dist[u] + graph[u][w] < dist[w]) {
                dist[w] = dist[u] + graph[u][w];
                path[w] = u;
            }
    }
}

时间复杂度：$O(|V|^2)$（可用堆优化为 $O(|E| \log |V|)$）

【Dijkstra 算法手工模拟示例】

使用与 Prim 相同的图（$V_0 \sim V_4$），从 $V_0$ 出发求单源最短路径：

轮次	选中顶点	dist[$V_0$]	dist[$V_1$]	dist[$V_2$]	dist[$V_3$]	dist[$V_4$]	说明
初始	$V_0$	0 ✓	4	3	∞	7	源点确定
1	$V_2$	0 ✓	4→3+2=5? 不更新保持4	3 ✓	3+1=4	3+8=11→保持7	选 dist 最小的未确定点 $V_2$
2	$V_1$	0 ✓	4 ✓	3 ✓	4+5=9→保持4	7	选 $V_1$(dist=4)，更新邻接点
3	$V_3$	0 ✓	4 ✓	3 ✓	4 ✓	4+6=10→保持7	选 $V_3$(dist=4)
4	$V_4$	0 ✓	4 ✓	3 ✓	4 ✓	7 ✓	选 $V_4$(dist=7)

最终结果：$V_0 \to V_1$: 距离 4（直达），$V_0 \to V_2$: 距离 3（直达），$V_0 \to V_3$: 距离 4（$V_0→V_2→V_3$），$V_0 \to V_4$: 距离 7（直达）

⚠️ Dijkstra 手算步骤（考试模板）：

1. 画表，列出所有顶点的 dist 列，初始为邻接矩阵第一行
2. 每轮选 dist 最小的未确定顶点 $u$，标记 ✓
3. 用 $u$ 的出边更新所有未确定顶点：若 $\text{dist}[u] + w(u,v) < \text{dist}[v]$，则更新
4. 重复直到所有顶点确定
5. 追问最短路径时：通过 path[] 数组逆序回溯

⚠️ Dijkstra 不适用于有负权值边的图！ 因为贪心策略在负权边下可能导致已确定的"最短路径"被后续更短路径推翻。

⚠️ 最短路径算法选择陷阱（高频选择题）：

算法	适用范围	不适用
BFS	无权图单源最短路径	带权图
Dijkstra	非负权带权图单源最短路径	❌ 负权边（计算结果错误）
Floyd	任意权多源最短路径	❌ 负权回路（死循环/无穷小）
Bellman-Ford	可处理负权边的单源最短路径	❌ 负权回路

陷阱警告：Dijkstra 无法处理负权边的根本原因是它的贪心策略：一旦选定一个顶点的最短路径，就认为已经确定，不再回头更新。而负权边可能让"回头路"变得更短。

💡 Dijkstra 与 Prim 算法的类比：两者结构几乎完全相同！Prim 每次选 lowCost 最小、Dijkstra 每次选 dist 最小，都是 $O(|V|^2)$。区别在于 Prim 的 lowCost[j] 是 $j$ 到当前生成树集合的最近距离，而 Dijkstra 的 dist[j] 是从源点经 $S$ 到 $j$ 的最短路径长度。

3. Floyd算法（各顶点间最短路径）

适用：带权图（可以有负权边，但不能有负权回路）

思想：动态规划。维护两个矩阵：

• $A^{(k)}[i][j]$：从 $V_i$ 到 $V_j$，中间顶点编号不超过 $k$ 的最短路径长度
• $path^{(k)}[i][j]$：对应最短路径上的中转顶点

递推公式： $A^{(k)}[i][j] = \min\{A^{(k-1)}[i][j],\ A^{(k-1)}[i][k] + A^{(k-1)}[k][j]\}$

若经过 $V_k$ 中转更短，则 $path^{(k)}[i][j] = k$；否则保持不变。

初始化：$A^{(-1)}$ 为邻接矩阵，$path^{(-1)}$ 全部设为 $-1$。

// Floyd算法核心
// A[][] 初始化为邻接矩阵, path[][] 初始化为-1
for (int k = 0; k < n; k++)          // 中转点
    for (int i = 0; i < n; i++)      // 起点
        for (int j = 0; j < n; j++)  // 终点
            if (A[i][k] + A[k][j] < A[i][j]) {
                A[i][j] = A[i][k] + A[k][j];
                path[i][j] = k;       // 记录中转点
            }

// Floyd算法核心
for (int k = 0; k < n; k++)
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (A[i][k] != INF && A[k][j] != INF && A[i][k] + A[k][j] < A[i][j]) {
                A[i][j] = A[i][k] + A[k][j];
                path[i][j] = k;
            }

通过 path 矩阵递归追溯完整路径：查找 $V_i$ 到 $V_j$ 的路径时，先查 path[i][j]=k，再递归查 $V_i$ 到 $V_k$、$V_k$ 到 $V_j$ 的中转点。

时间复杂度：$O(|V|^3)$，空间复杂度：$O(|V|^2)$

🗣️ 大白话：Floyd的思想很简单——"我从 $i$ 到 $j$ 直接走会不会比绕道 $k$ 更远？如果绕道更近就更新路线"。把所有可能的中转站都试一遍，需要 $n$ 轮递推。

4. Bellman-Ford算法（可处理负权边的单源最短路径）

适用：带权有向图（允许负权边，但不能有负权回路）

思想：对所有边进行 $|V|-1$ 轮"松弛"操作。每轮遍历所有边 $(u,v)$，如果 $\text{dist}[u] + w(u,v) < \text{dist}[v]$，则更新 $\text{dist}[v]$。

🗣️ 大白话：Dijkstra 像个"近视眼贪心"——只看眼前最近的点，遇到负权边就会犯错。而 Bellman-Ford 像个"全面撒网"——不管远近，每轮把所有边都试一遍、看看有没有更短的路，做够 $|V|-1$ 轮就能保证找到最短路径。

核心代码：

// Bellman-Ford 算法
bool BellmanFord(int n, int edges[][3], int edgeNum, int src, int dist[]) {
    for (int i = 0; i < n; i++) dist[i] = INF;
    dist[src] = 0;
    // 松弛 |V|-1 轮
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < edgeNum; j++) {
            int u = edges[j][0], v = edges[j][1], w = edges[j][2];
            if (dist[u] != INF && dist[u] + w < dist[v])
                dist[v] = dist[u] + w;
        }
    }
    // 检测负权回路：第 |V| 轮若仍能松弛，说明存在负权回路
    for (int j = 0; j < edgeNum; j++) {
        int u = edges[j][0], v = edges[j][1], w = edges[j][2];
        if (dist[u] != INF && dist[u] + w < dist[v])
            return false;  // 存在负权回路
    }
    return true;
}

// Bellman-Ford 算法（Java版）
boolean bellmanFord(int n, int[][] edges, int src, int[] dist) {
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;
    for (int i = 1; i < n; i++) {
        for (int[] e : edges) {
            int u = e[0], v = e[1], w = e[2];
            if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v])
                dist[v] = dist[u] + w;
        }
    }
    // 负权回路检测
    for (int[] e : edges) {
        if (dist[e[0]] != Integer.MAX_VALUE && dist[e[0]] + e[2] < dist[e[1]])
            return false;
    }
    return true;
}

分析项	值
时间复杂度	$O(\|V\| \cdot \|E\|)$
空间复杂度	$O(\|V\|)$
可处理负权边	✅
可检测负权回路	✅（第 $\|V\|$ 轮仍能松弛 → 存在负权回路）

⚠️ 为何恰好 $|V|-1$ 轮？ 若图中无负权回路，最短路径最多经过 $|V|-1$ 条边（经过所有顶点）。第 $k$ 轮松弛后，至少能正确求出经过不超过 $k$ 条边的最短路径。因此 $|V|-1$ 轮后所有最短路径均已确定。

🔗 【跨学科联动·计算机网络】 Bellman-Ford 算法是 RIP 协议（距离向量路由）的理论基础：

• RIP 中每个路由器维护到各目的网络的"距离"（跳数），定期与邻居交换路由表
• 本质就是分布式的 Bellman-Ford：每个路由器收到邻居的距离向量后执行松弛操作
• RIP 限制最大跳数为 15（16 = 不可达），正是为了限制 Bellman-Ford 的收敛轮数
• RIP 的"慢收敛/路由环路"问题（Count to Infinity）是 Bellman-Ford 分布式执行的固有缺陷
• 对应地，OSPF 协议（链路状态路由）基于 Dijkstra 算法

四种最短路径算法完整对比（⭐ 高频选择题考点）：

	BFS	Dijkstra	Bellman-Ford	Floyd
无权图	✅	✅	✅	✅
正权图	❌	✅	✅	✅
负权边	❌	❌	✅	✅
负权回路检测	❌	❌	✅	❌（需额外判断）
类型	单源	单源	单源	多源
时间复杂度	$O(\|V\|+\|E\|)$	$O(\|V\|^2)$	$O(\|V\| \cdot \|E\|)$	$O(\|V\|^3)$
贪心/DP	BFS	贪心	DP（松弛迭代）	DP
网络协议	—	OSPF	RIP	—

💡 也可用 Dijkstra 求所有顶点间最短路径：重复 $|V|$ 次，总时间 $O(|V|^3)$，但不如 Floyd 简洁。

三、拓扑排序

适用：有向无环图（DAG）

AOV网：用DAG表示工程，顶点表示活动，有向边 $\langle V_i, V_j \rangle$ 表示活动 $V_i$ 必须先于 $V_j$ 进行。

拓扑排序定义：将所有顶点排成线性序列，使得若存在边 $\langle u, v \rangle$，则 $u$ 在序列中排在 $v$ 前面。

算法步骤：

1. 选择一个入度为0的顶点输出
2. 删除该顶点及其所有出边（即将其邻接点入度减1）
3. 重复1-2直到所有顶点输出，或发现不存在入度为0的顶点（说明图中有回路）

时间复杂度：邻接表 $O(|V|+|E|)$，邻接矩阵 $O(|V|^2)$

逆拓扑排序：

1. 选择一个出度为0的顶点输出
2. 删除该顶点及所有以它为终点的有向边
3. 重复直到图空

DFS 实现逆拓扑排序：对有向无环图进行 DFS，在顶点退栈前输出（即后序输出），得到的序列即为逆拓扑排序序列。

⚠️ 重要应用：拓扑排序可用于判断有向图是否有环——若排序过程中输出的顶点数少于图中顶点总数，则存在环。

DAG 描述表达式（用有向无环图描述表达式，消除公共子表达式）：

1. 把各个操作数不重复地排成一排（作为叶结点）
2. 按运算符生效顺序标出各运算符
3. 按顺序加入运算符结点，注意"分层"
4. 从底向上逐层检查同层运算符是否可以合体（共享公共子表达式）

💡 DAG 的顶点中不可能出现重复的操作数——这是DAG表示与二叉树表示的关键区别。

四、关键路径

用于：AOE网（Activity On Edge NetWork，以边表示活动、以顶点表示事件的网络），求工程的最短完成时间。

AOE网性质：

• 只有某顶点代表的事件发生后，从该顶点出发的各活动才能开始
• 进入某顶点的所有活动都完成后，该顶点代表的事件才能发生
• 源点：入度为0（工程开始），汇点：出度为0（工程结束）

核心概念：

概念	含义	计算方法
$ve(k)$：事件最早发生时间	从源点到顶点 $k$ 的最长路径长度	按拓扑排序序列正向递推
$vl(k)$：事件最迟发生时间	不推迟工期前提下事件 $k$ 最迟必须发生的时间	按逆拓扑排序序列反向递推
$e(i)$：活动最早开始时间	活动弧的起点的最早发生时间	$e(i) = ve(k)$，边 $\langle v_k,v_j \rangle$ 表示活动 $a_i$
$l(i)$：活动最迟开始时间	终点最迟发生时间 $-$ 活动持续时间	$l(i) = vl(j) - Weight(v_k, v_j)$
$d(i) = l(i) - e(i)$	活动的时间余量	$d(i)=0$ 的就是关键活动

5步计算过程：

① $ve(源点) = 0$；按拓扑排序序列递推：$ve(k) = \max\{ve(j) + Weight(v_j, v_k)\}$（$v_j$ 为 $v_k$ 的任意前驱）

② $vl(汇点) = ve(汇点)$；按逆拓扑排序序列递推：$vl(k) = \min\{vl(j) - Weight(v_k, v_j)\}$（$v_j$ 为 $v_k$ 的任意后继）

③ 若边 $\langle v_k, v_j \rangle$ 表示活动 $a_i$，则 $e(i) = ve(k)$

④ $l(i) = vl(j) - Weight(v_k, v_j)$

⑤ $d(i) = l(i) - e(i)$；$d(i)=0$ 的活动是关键活动，由关键活动组成关键路径

关键路径：从源点到汇点的最长路径。关键路径长度 = 工程的最短完成时间。

重要性质：

• 关键路径上所有活动的时间余量为0
• 缩短关键活动的时间可以缩短工期
• 当缩短到一定程度时，关键活动可能变成非关键活动（原来的非关键路径可能成为新的关键路径）
• 可能存在多条关键路径，此时只有加快所有关键路径上共有的关键活动才能缩短工期

⚠️ 缩短关键活动不一定缩短工期——当存在多条关键路径且该活动不在所有关键路径上时。

📝 真题剖析

【2016年408真题】 使用 Dijkstra 算法求图中从顶点1到其他各顶点的最短路径，依次求得的各最短路径的目标顶点是？

解题方法：

1. 初始化：$dist[1]=0$，其余顶点 $dist=\infty$
2. 每次从未确定最短路径的顶点中选 $dist$ 最小的加入集合 $S$
3. 更新其邻接点的 $dist$ 值
4. 重复直到所有顶点加入 $S$

💡 Dijkstra 三步曲：选最近、加入、更新。每次确定一个顶点的最短路径。

【2022年408真题】 无向连通图边数 $|E|$ 与顶点数 $|V|$ 的关系？

💡 核心结论：无向连通图至少需要 $|V|-1$ 条边（树）。若 $|E| < |V|-1$，则图一定不连通。

【2021年408应用题】 判断无向图中是否存在欧拉回路/欧拉路径。

欧拉路径/回路条件（充要条件）：

1. 欧拉回路（一笔画回到原点）：图连通 + 所有顶点度数为偶数
2. 欧拉路径（一笔画不回原点）：图连通 + 恰好有0个或2个奇度数顶点

算法设计：

1. 用BFS/DFS判断图是否连通
2. 统计所有顶点的度数，计算奇度数顶点个数 $count$
3. 若 $count = 0$：存在欧拉回路；若 $count = 2$：存在欧拉路径；否则：不存在

// 判断无向图是否存在欧拉路径/回路（邻接矩阵）
boolean hasEulerPath(int[][] graph, int n) {
    // Step1: BFS 判连通
    boolean[] visited = new boolean[n];
    Queue<Integer> queue = new LinkedList<>();
    visited[0] = true; queue.offer(0);
    int cnt = 1;
    while (!queue.isEmpty()) {
        int v = queue.poll();
        for (int w = 0; w < n; w++)
            if (graph[v][w] != 0 && !visited[w]) {
                visited[w] = true; queue.offer(w); cnt++;
            }
    }
    if (cnt != n) return false; // 不连通
    // Step2: 统计奇度数顶点
    int oddCount = 0;
    for (int i = 0; i < n; i++) {
        int degree = 0;
        for (int j = 0; j < n; j++) if (graph[i][j] != 0) degree++;
        if (degree % 2 != 0) oddCount++;
    }
    return oddCount == 0 || oddCount == 2;
}

【2023年408应用题】 有向图以邻接矩阵存储，找所有"K-顶点"（出度 > 入度的顶点）。

方法：遍历邻接矩阵，对每个顶点分别统计出度（第 $i$ 行非零元素个数）和入度（第 $i$ 列非零元素个数），比较即可。

// 找所有K-顶点（出度 > 入度），邻接矩阵A[n][n]
List<Integer> findKVertices(int[][] A, int n) {
    List<Integer> result = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        int outDeg = 0, inDeg = 0;
        for (int j = 0; j < n; j++) {
            if (A[i][j] != 0) outDeg++;  // 第i行：出度
            if (A[j][i] != 0) inDeg++;   // 第i列：入度
        }
        if (outDeg > inDeg) result.add(i);
    }
    return result;
}

💡 时间复杂度 $O(|V|^2)$——恰好等于邻接矩阵存储的标准复杂度。

【2024年408应用题】 判断有向图是否存在唯一的拓扑排序序列。

充要条件：拓扑排序过程中，每一步恰好只有一个入度为0的顶点。

// 判断DAG是否有唯一拓扑排序
boolean hasUniqueTopoSort(List<List<Integer>> graph, int n) {
    int[] inDeg = new int[n];
    for (int u = 0; u < n; u++)
        for (int v : graph.get(u)) inDeg[v]++;
    Queue<Integer> q = new LinkedList<>();
    for (int i = 0; i < n; i++)
        if (inDeg[i] == 0) q.offer(i);
    int count = 0;
    while (!q.isEmpty()) {
        if (q.size() > 1) return false; // 不唯一！
        int u = q.poll(); count++;
        for (int v : graph.get(u))
            if (--inDeg[v] == 0) q.offer(v);
    }
    return count == n; // count<n说明有环
}

⚠️ 若每步恰有1个入度为0的顶点 → 拓扑排序唯一；若某步有多个 → 拓扑排序不唯一。

【2025年408应用题】 AOE网求关键路径，压缩关键活动后分析工期变化。

解题模板（5步法）：

步骤	操作	说明
①	求所有事件 $ve(k)$	拓扑排序正向递推，取 max
②	求所有事件 $vl(k)$	逆拓扑排序反向递推，取 min
③	求所有活动 $e(i)$	$e(i) = ve(起点)$
④	求所有活动 $l(i)$	$l(i) = vl(终点) - Weight$
⑤	求 $d(i)=l(i)-e(i)$	$d(i)=0$ → 关键活动

典型追问："将活动 $X$ 压缩2个时间单位，工期能缩短多少？"

• 若 $X$ 在所有关键路径上：工期缩短2（但不能缩短超过 $X$ 本身的持续时间）
• 若 $X$ 只在部分关键路径上：工期不缩短
• 缩短后可能产生新的关键路径，需要重新计算验证

⚠️ 2025年真题实例：AOE网最短完成时间=12，关键活动为 $a,e,m,n$。当压缩 $e$ 时需检查是否出现新关键路径。

【图的高频选择题考点汇总】：

考点	关键结论	真题年份
连通图最少边数	无向连通图至少 $\|V\|-1$ 条边	2022
强连通图最少边数	有向强连通图至少 $\|V\|$ 条边（构成环）	2016
邻接矩阵 $A^n$	$A^n[i][j]$ = 从 $v_i$ 到 $v_j$ 长度为 $n$ 的路径条数	2014
邻接多重表	无向图中删除某边只需 $O(1)$	2024
生成树边数	连通图的生成树恰有 $\|V\|-1$ 条边	常考
Prim vs Kruskal	稠密图用 Prim $O(\|V\|^2)$，稀疏图用 Kruskal $O(\|E\|\log\|E\|)$	常考
BFS 生成树高度	BFS 生成树高度 ≤ DFS 生成树高度（邻接表下）	2021
非连通图 DFS	调用 DFS 的次数 = 连通分量数	2017

📌 第六章总结

核心知识点	考研要求
图的基本概念（度、连通性等）	必须牢记
邻接矩阵与邻接表	必须掌握，高频考点
BFS 和 DFS 的实现与复杂度	必须掌握
BFS 和 DFS 的对比	需要理解
Prim 和 Kruskal 算法	常考，需会手动模拟
Dijkstra 算法	重中之重，大题常考
Floyd 算法	必须掌握
Dijkstra 不能处理负权边	⚠️ 常考陷阱
拓扑排序	需要掌握
关键路径	大题常考

---

第七章 查找

7.1 查找的基本概念

查找表：同一类型数据元素的集合。

关键字：数据元素中唯一标识该元素的某个数据项。

查找成功/失败：在查找表中找到/未找到给定关键字的记录。

平均查找长度ASL：

$ASL = \sum_{i=1}^{n} P_i C_i$

其中 $P_i$ 是查找第 $i$ 个元素的概率，$C_i$ 是找到第 $i$ 个元素需要比较的次数。

🗣️ 大白话：ASL 就是"平均要比较多少次才能找到"。ASL 越小，查找效率越高。

---

7.2 线性表的查找

一、顺序查找

思路：从头到尾一个一个比较。

$ASL_{成功} = \frac{n+1}{2}, \quad ASL_{失败} = n+1$

哨兵：将待查找关键字放在表的一端（0号位置），从另一端开始查找，避免每次循环都检查是否越界。

有序表的顺序查找：若表已有序，查找失败时可以提前终止（遇到比目标大的元素即可停止）。

用判定树分析有序表顺序查找：

• 成功结点有 $n$ 个（圆形结点），失败结点有 $n+1$ 个（方形结点/外部结点）
• $ASL_{成功} = \frac{1+2+\cdots+n}{n} = \frac{n+1}{2}$（与无序表相同）
• $ASL_{失败} = \frac{1+2+\cdots+n+n}{n+1} = \frac{n}{2} + \frac{n}{n+1}$（优于无序表的 $n+1$）

二、折半查找（二分查找）

前提：有序顺序表（必须是顺序存储！链式存储不行！）

int Binary_Search(SeqList L, ElemType key) {
    int low = 0, high = L.length - 1, mid;
    while (low <= high) {
        mid = (low + high) / 2;
        if (L.elem[mid] == key) return mid;
        else if (L.elem[mid] > key) high = mid - 1;
        else low = mid + 1;
    }
    return -1;  // 查找失败
}

int binarySearch(int[] arr, int length, int key) {
    int low = 0, high = length - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (arr[mid] == key) return mid;
        else if (arr[mid] > key) high = mid - 1;
        else low = mid + 1;
    }
    return -1;  // 查找失败
}

时间复杂度：$O(\log_2 n)$

判定树分析：

• 折半查找的过程可以用一棵判定树来描述
• 判定树是一棵平衡二叉排序树（注意：不一定是AVL树，但高度差不超过1）
• 判定树的形态只与 $n$ 有关，与关键字的具体值无关
• 查找成功的 $ASL \leq \lfloor \log_2 n \rfloor + 1$
• $ASL_{成功} = \frac{1}{n} \sum_{i=1}^{n} l_i$（$l_i$ 是第 $i$ 个元素在判定树中的层次）
• 查找失败的ASL：失败结点（叶结点以下的外部结点）在判定树的第 $\lfloor \log_2 n \rfloor + 1$ 或 $\lfloor \log_2 n \rfloor + 2$ 层
• 判定树中，右子树结点数 ≥ 左子树结点数（因为 $mid = \lfloor (low+high)/2 \rfloor$ 取下整）
• 失败结点有 $n+1$ 个（代表 $n+1$ 个查找失败的区间）

🗣️ 大白话：折半查找就像猜数字游戏——主持人告诉你"大了"或"小了"，你每次猜中间值，很快就能猜到。

三、分块查找（索引顺序查找）

思路：将表分成若干块。块间有序（后一块所有元素都大于前一块），块内无序。

• 索引表：记录每块的最大关键字和起始位置
• 先在索引表中查找确定在哪一块（可用折半查找），再在块内顺序查找

$ASL = ASL_{索引} + ASL_{块内}$

均匀分块时（$n$ 个元素分成 $b = \lceil n/s \rceil$ 块，每块 $s$ 个元素）：

• 索引表顺序查找：$ASL = \frac{b+1}{2} + \frac{s+1}{2}$
• 当 $s = \sqrt{n}$ 时，$ASL$ 最小，约为 $\sqrt{n}+1$

⚠️ 索引表用折半查找时的特殊规则：折半查找索引表时，若查找失败（key不等于任何索引项），则目标元素在 low 所指的分块中（而非 mid 或 high）。因为折半查找结束时 low > high，low 恰好指向第一个最大关键字 $\geq key$ 的块。

折半查找索引的ASL：$ASL = \lceil\log_2(b+1)\rceil + \frac{s+1}{2}$（索引折半 + 块内顺序）

---

7.3 树形查找

一、二叉排序树（BST）

定义：

1. 若左子树非空，则左子树上所有结点值 $<$ 根结点值
2. 若右子树非空，则右子树上所有结点值 $>$ 根结点值
3. 左右子树也分别是二叉排序树

💡 中序遍历BST得到递增有序序列！

查找操作：

BSTNode *BST_Search(BiTree T, ElemType key) {
    while (T != NULL && key != T->data) {
        if (key < T->data) T = T->lchild;
        else T = T->rchild;
    }
    return T;
}

BiTNode bstSearch(BiTNode T, int key) {
    while (T != null && key != T.data) {
        if (key < T.data) T = T.lchild;
        else T = T.rchild;
    }
    return T;
}

插入操作：

• 若树为空，创建新结点
• 若 key < 根，递归插入左子树
• 若 key > 根，递归插入右子树

删除操作（三种情况）：

1. 被删结点是叶子结点：直接删除
2. 被删结点只有一棵子树：用子树替代
3. 被删结点有两棵子树：用其中序前驱（左子树最右结点）或中序后继（右子树最左结点）替代，然后删除替代结点

BST的查找效率：

• 最好情况（平衡BST）：$O(\log_2 n)$
• 最坏情况（退化为链表）：$O(n)$

⚠️ 2011年真题考点：判断序列是否可能构成BST中的一条查找路径。

关键规则：在BST查找路径上，一旦从某结点 $X$ 进入左子树，之后查找到的所有值都必须 < $X$；进入右子树后，所有值都必须 > $X$。

例：序列 95, 22, 91, 24, 94, 71 不可能是查找路径——因为从22到91是走右子树（后续值应 >91），但之后出现了24（<91），矛盾！

二、平衡二叉树（AVL树）

定义：任意结点的左右子树高度差（平衡因子）的绝对值不超过1。

$平衡因子 = 左子树高度 - 右子树高度 \in \{-1, 0, 1\}$

四种旋转调整：

失衡类型	旋转操作	说明
LL型	右旋	在左孩子的左子树上插入
RR型	左旋	在右孩子的右子树上插入
LR型	先左旋再右旋	在左孩子的右子树上插入
RL型	先右旋再左旋	在右孩子的左子树上插入

🗣️ 大白话：AVL树就是一棵"始终保持平衡"的BST。每次插入或删除后如果"歪了"（不平衡了），就通过旋转把它"扳正"。

AVL树的删除操作（2026王道新增重点）：

具体步骤：

1. 删除结点（方法同BST删除）
2. 一路向上找到最小不平衡子树，找不到则结束
3. 找最小不平衡子树中**"个头"最高的儿子、孙子**
4. 根据孙子位置执行 LL/RR/LR/RL 旋转调整
5. 不平衡可能向上传导——调整后如果上层不平衡，继续步骤2

⚠️ 插入 vs 删除的关键区别：

• 插入只需一次调整（旋转）即可恢复平衡
• 删除可能需要多次调整（不平衡向上传导）——因为旋转可能导致子树变矮，从而使上层祖先也不平衡

AVL树的查找效率：$O(\log_2 n)$（始终保持平衡）

含有 $n$ 个结点的AVL树的最大高度为 $O(\log_2 n)$。

高度为 $h$ 的AVL树的最少结点数 $C_h$（2012年真题核心，所有非叶结点平衡因子均为1）：

$C_h = C_{h-1} + C_{h-2} + 1, \quad C_1 = 1, C_2 = 2$

$h$	1	2	3	4	5	6	7
$C_h$	1	2	4	7	12	20	33

💡 递推规律类似 Fibonacci 数列。高度为6、所有非叶结点平衡因子为1的AVL树，恰好有20个结点（2012年真题答案）。

三、红黑树（RBT）

红黑树的性质（口诀：左根右，根叶黑，不红红，黑路同）：

1. 每个结点非红即黑
2. 根结点是黑色（"根叶黑"）
3. 叶结点（外部的NULL结点、失败结点）是黑色（"根叶黑"）
4. 不存在两个相邻的红色结点（红结点的父、孩子必须是黑色）（"不红红"）
5. 从任一结点到其任一叶结点的所有简单路径上，黑色结点数目相同（"黑路同"）

结点的黑高 $bh$：从某结点出发（不含该结点）到达任一空叶结点的路径上黑结点总数。

红黑树的重要性质：

• 性质1：从根到叶的最长路径不大于最短路径的 2倍
  • 最短路径：全黑，长度 = $bh$
  • 最长路径：黑红交替，长度 = $2 \times bh$
• 性质2：有 $n$ 个内部结点的红黑树，高度 $h \leq 2\log_2(n+1)$
• 查找效率 = $O(\log_2 n)$，与AVL同数量级

红黑树的插入操作：

• 新结点非根染红色（若染黑必然破坏"黑路同"，而染红只可能破坏"不红红"，更容易修复）
• 新结点是根则染黑色
• 调整策略：看叔叔（父的兄弟）的脸色——

情况	叔叔颜色	操作
黑叔/NULL (LL型)	叔叔是黑色/NULL	右旋 + 变色（P变黑，G变红）
黑叔/NULL (RR型)	叔叔是黑色/NULL	左旋 + 变色（P变黑，G变红）
黑叔/NULL (LR/RL)	叔叔是黑色/NULL	双旋（先转为LL/RR，再处理）
红叔	叔叔是红色	染色 + 变新（叔、父染黑，爷染红，爷变为新的当前结点继续调整）

💡 黑叔旋转口诀：LL右旋"父换爷"、RR左旋"父换爷"、LR双旋"儿换爷"、RL双旋"儿换爷"，换后染色。

⚠️ 秒杀模型：看到叔叔是红色 -> 变色继续往上看；看到叔叔是黑色 -> 旋转变色完工！

⚠️ 红黑树删除的核心考点：删除操作时间复杂度 = $O(\log_2 n)$，处理方式与BST删除相同，之后调整颜色。

红黑树的删除操作（⭐ 2022考纲正式收录后，删除调整已可命题）：

第一步：按BST规则定位并删除（与BST删除完全相同）

• 叶子结点 → 直接删除
• 仅有一个孩子 → 孩子替代
• 有两个孩子 → 用中序后继（右子树最小）替换关键字，转为删除后继结点

🗣️ 大白话：红黑树删除分两步——先像普通BST一样把结点拿掉，然后调整颜色和结构来修复被破坏的红黑性质。

第二步：根据被删结点与替代结点的颜色决定是否调整

被删/替代结点实际颜色	处理方式	原因
删红色叶子	✅ 直接删除，无需任何调整	不影响黑高，不破坏任何性质
删黑色，替代结点红色	✅ 将替代结点染黑即可	补偿该路径上丢失的一个黑结点
删黑色，替代结点黑色/NULL	❌ 产生**"双重黑色"**问题，需复杂调整	该路径黑高减1，违反性质5（黑路同）

"双重黑色"调整框架（看兄弟脸色，与插入"看叔叔脸色"对偶）：

设 $x$ 为替代结点（双重黑色），$s$ 为 $x$ 的兄弟，$p$ 为父结点：

Case	兄弟 $s$ 颜色	兄弟孩子情况	操作	效果
1	红	—	$s$ 变黑、$p$ 变红，朝 $x$ 方向旋转	转为 Case 2/3/4
2	黑	两个孩子均黑	$s$ 变红，双重黑上移到 $p$	若 $p$ 原为红 → $p$ 变黑完工；否则继续调整
3	黑	近侄红、远侄黑	近侄变黑、$s$ 变红，朝 $s$ 方向旋转	转为 Case 4
4	黑	远侄红	$s$ 取 $p$ 色、$p$ 变黑、远侄变黑，朝 $x$ 旋转	✅ 调整完成！

💡 删除记忆口诀："红兄先旋→黑兄看侄→远红一旋收工！"

• Case 1 红兄：旋转降级为 Case 2~4
• Case 2 黑兄双黑侄：染色上传（类似插入的"红叔变色上传"）
• Case 3 近侄红：旋转调整为 Case 4
• Case 4 远侄红：终结操作——一次旋转+染色即可解决

⚠️ 考试中红黑树删除的考法：

1. 判断"删除某结点后红黑树是否仍满足全部5条性质"（选择题）
2. 判断删除操作最多旋转几次（答：最多3次，远少于AVL可能的 $O(\log n)$ 次）
3. 结合性质5（黑路同）判断"删除后某路径黑高是否变化"
4. 不会要求写出完整代码，但需理解调整框架

红黑树 vs AVL树：

对比项	AVL树	红黑树
发明年份	1962	1972
平衡标准	严格（$\|BF\| \leq 1$）	宽松（黑路同 + 不红红）
查找	$O(\log n)$，略优	$O(\log n)$
插入	$O(\log n)$，可能旋转	$O(\log n)$，旋转更少
删除	$O(\log n)$，可能多次旋转	$O(\log n)$，最多3次旋转
适用场景	以查为主，少插入删除	频繁插入、删除，实用性更强
实际应用	——	Java TreeMap、C++ map/set、Linux进程调度

---

7.4 B树和B+树

一、B树（多路平衡查找树）

$m$ 阶B树的定义：

1. 每个结点最多有 $m$ 棵子树（最多 $m-1$ 个关键字）
2. 根结点至少有2棵子树（至少1个关键字），除非是叶子
3. 非根非叶结点至少有 $\lceil m/2 \rceil$ 棵子树（至少 $\lceil m/2 \rceil - 1$ 个关键字）
4. 所有叶结点都出现在同一层
5. 结点内关键字有序排列

🗣️ 大白话：B树就是一棵"矮胖"的查找树。普通二叉树每个结点只存一个值，B树每个结点可以存很多值，所以树的高度大大降低。高度低意味着查找时磁盘I/O次数少——这就是数据库索引用B树的原因。

🔗 【跨学科联动·OS/计组】 B 树和 B+ 树是 408 跨学科考点的"桥梁"：

• OS·文件系统索引：Unix/Linux 的 inode 索引结构（直接索引→一级间接→二级间接→三级间接）本质思想与 B 树类似——通过多级索引减少磁盘 I/O
• OS·磁盘调度：B 树节点大小通常设计为一个磁盘块/页面的大小（如 4KB），每次读一个结点恰好对应一次磁盘 I/O。因此 B 树高度 = 查找所需的磁盘 I/O 次数
• 计组·Cache 原理：B 树的设计理念与 Cache 类似——利用局部性原理，将频繁访问的数据（索引）集中存放以减少慢速存储的访问次数
• 实际应用：MySQL InnoDB 引擎使用 B+ 树做聚簇索引，叶结点链表支持高效范围查询

B树的插入：

1. 找到应插入的叶子结点
2. 如果关键字个数未满，直接插入
3. 如果满了（达到 $m-1$ 个），执行分裂：
   • 取中间关键字上提到父结点
   • 左右两半各形成一个新结点

B树的删除（分三种情况）：

情况1：直接删除 —— 被删关键字在终端结点中，且该结点关键字个数 $> \lceil m/2\rceil - 1$，直接删除。

情况2：兄弟够借 —— 被删关键字所在结点删后关键字不够（$= \lceil m/2\rceil - 1$），但左/右兄弟结点关键字数 $\geq \lceil m/2\rceil$。处理方法：

• 父结点中对应关键字下移到被删结点
• 兄弟结点中最大（左兄弟）或最小（右兄弟）关键字上移到父结点

💡 2012年真题：3阶B树删除78，左兄弟有2个关键字 $\geq \lceil 3/2\rceil = 2$，属"兄弟够借"。左兄弟最大关键字上移到父结点，父结点对应关键字下移。

情况3：兄弟不够借 —— 左右兄弟关键字数都 $= \lceil m/2\rceil - 1$。处理方法：

• 将被删结点、父结点中对应关键字、兄弟结点三者合并为一个结点
• 合并后若父结点关键字不够，继续向上合并（合并可能向上传播直到根结点）

非终端结点中的删除：用该关键字的直接前驱（左子树中最右下的关键字）或直接后继（右子树中最左下的关键字）替换，转化为终端结点的删除。

补充：B树高度范围的推导（⭐常考计算）

$n$ 个关键字的 $m$ 阶B树，高度 $h$ 的范围：

$\log_m(n+1) \leq h \leq \log_{\lceil m/2 \rceil}\frac{n+1}{2} + 1$

下界推导（树最"胖"时高度最小）：

• 每个结点最多 $m-1$ 个关键字，$h$ 层最多 $(1 + m + m^2 + \cdots + m^{h-1}) \times (m-1) = m^h - 1$ 个关键字
• 故 $n \leq m^h - 1$，即 $h \geq \log_m(n+1)$

上界推导（树最"瘦"时高度最大）：

• 根结点至少 1 个关键字、2 棵子树
• 非根非叶结点至少 $\lceil m/2 \rceil$ 棵子树
• 第 $h+1$ 层为叶结点层（失败结点层），至少有 $2 \times \lceil m/2 \rceil^{h-1}$ 个结点
• 叶结点数 = $n+1$（$n$ 个关键字对应 $n+1$ 个查找失败区间）
• 故 $n+1 \geq 2 \times \lceil m/2 \rceil^{h-1}$，即 $h \leq \log_{\lceil m/2 \rceil}\frac{n+1}{2} + 1$

📝 例题：3阶B树存储20个关键字，高度范围？

• 下界：$h \geq \log_3 21 = \lceil 2.77 \rceil = 3$
• 上界：$h \leq \log_2 \frac{21}{2} + 1 = \lceil 3.39 \rceil + 1 = 5$
• 答：$3 \leq h \leq 5$

二、B+树

B+树与B树的区别：

特点	B树	B+树
关键字与子树数目	$n$ 个关键字，$n+1$ 棵子树	$n$ 个关键字，$n$ 棵子树
关键字分布	非叶结点和叶结点都包含数据	数据只在叶结点中
叶结点	不含信息	包含全部关键字且按顺序链接
查找过程	可能在任意结点停止	必须到叶结点才能找到数据
叶结点链表	无	叶结点通过指针链成有序链表

🗣️ B+树的优势：叶结点形成有序链表，支持高效的范围查询。这就是为什么MySQL的InnoDB引擎用B+树做索引。

---

7.5 散列表（Hash表）

一、基本概念

散列函数：$H(key)$ 把关键字映射到存储地址。

散列表：根据散列函数建立的查找表。

冲突：两个不同关键字映射到同一个地址：$H(key_1) = H(key_2)$，$key_1 \neq key_2$

同义词：发生冲突的两个关键字互称同义词。

二、散列函数的构造方法

散列函数的设计原则（4条）：

1. 定义域必须包含全部可能的关键字，值域不超过散列表地址范围
2. 散列函数计算出的地址应尽可能均匀地分布在整个地址空间
3. 散列函数应尽量简单，在较短时间内计算出结果
4. 尽量减少冲突（冲突不可能完全避免，但好的散列函数能使冲突尽量少）

方法	公式	特点
除留余数法	$H(key) = key \% p$（$p$ 取不大于表长的最大质数）	最常用；$p$ 取质数能减少冲突
直接定址法	$H(key) = a \times key + b$	不会冲突，但要求关键字分布基本连续，否则空间浪费
数字分析法	取关键字某些分布均匀的位	适合关键字位数多且事先知道分布
平方取中法	取 $key^2$ 的中间几位	适用范围广，不需要知道关键字分布

三、处理冲突的方法

1. 开放定址法

发生冲突时，在散列表中寻找下一个空闲地址。

$H_i = (H(key) + d_i) \% m$

$d_i$ 的取值方法	名称	探查序列
$d_i = 0, 1, 2, \ldots$	线性探测法	顺序往后找
$d_i = 0, 1^2, -1^2, 2^2, -2^2, \ldots$	平方探测法	左右跳着找
$d_i$ 由另一个散列函数决定	双散列法	用第二个函数决定步长
伪随机数	伪随机序列法	—

⚠️ 线性探测法会导致"聚集"（堆积/Clustering）：

• 初级聚集（Primary Clustering）：线性探测中，冲突的元素和非同义词都聚集在一起。例如地址2已满，关键字映射到地址2的和映射到地址3的都堆在一起，导致"滚雪球"效应。
• 二级聚集（Secondary Clustering）：平方探测法中，同义词的探测序列相同，仍会发生一定程度的聚集。
• 双散列法可以有效减少聚集现象。

⚠️ 开放定址法中的删除问题：

• 开放定址法中不能直接物理删除元素！因为删除后留下的空位会使后续查找误认为"查找失败"而提前终止。
• 解决方案：使用逻辑删除（设置删除标记），查找时遇到删除标记继续探测，插入时遇到删除标记可以覆盖。
• 缺点：多次删除后，表中会积累大量"已删除"标记，降低查找效率，需定期重建散列表。

2. 拉链法（链地址法）

将所有同义词存储在同一个链表中。散列表的每个位置是一个链表的头指针。

🗣️ 大白话：拉链法就像多个抽屉——算出来放第5个抽屉，但第5个抽屉已经有东西了？没关系，在这个抽屉里排成一排就行了。

🔗 【跨学科联动·OS/计组】 散列（Hash）思想在 408 其他学科中的体现：

• OS·页表：虚拟地址到物理地址的映射本质是一种散列——通过页号直接计算页表项地址
• OS·快表（TLB）：TLB 就是页表的"散列缓存"，利用相联存储器实现快速查找
• 计组·Cache 映射：直接映射 $\text{Cache行号} = \text{主存块号} \% \text{Cache总行数}$ 本质就是散列函数
• 计网·校验码：CRC 校验、MD5/SHA 等哈希函数用于数据完整性检验

四、散列查找的性能分析

装填因子：$\alpha = \frac{表中记录数}{散列表长度}$

$\alpha$ 越大，冲突越多，查找效率越低。

ASL 与装填因子 $\alpha$ 有关，与表中记录数 $n$ 无直接关系（这是散列表与其他查找表的重要区别）。

⚠️ 2011年真题考点：提高散列表查找效率的正确措施是——

• ✅ 设计冲突少的散列函数
• ✅ 处理冲突时避免产生聚集（堆积）
• ❌ 增大装填因子（$\alpha$ 增大会增加冲突，降低效率！）

方法	$ASL_{成功}$	特点
线性探测法	约 $\frac{1}{2}(1 + \frac{1}{1-\alpha})$	$\alpha < 1$ 时有效
平方探测法	约 $-\frac{1}{\alpha}\ln(1-\alpha)$	性能优于线性探测
拉链法	约 $1 + \frac{\alpha}{2}$	性能最好，$\alpha$ 可大于1

📝 真题剖析

【2010年408真题】 将关键字序列 (7, 8, 30, 11, 18, 9, 14) 散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组，散列函数为 $H(key) = (key \times 3) \% 7$，处理冲突采用线性探测法，要求装填（载）因子为0.7。

（1）请画出散列表；（2）分别计算等概率情况下查找成功和不成功的的 ASL。

解：

表长 $m = n / \alpha = 7 / 0.7 = 10$，即散列表下标 0~9。

依次计算各关键字的散列地址并插入：

关键字key	H(key) = (key×3)%7	实际存储位置	比较次数
7	(21)%7 = 0	0	1
8	(24)%7 = 3	3	1
30	(90)%7 = 6	6	1
11	(33)%7 = 5	5	1
18	(54)%7 = 5 → 冲突，探测6→冲突，探测7	7	3
9	(27)%7 = 6 → 冲突，探测7→冲突，探测8	8	3
14	(42)%7 = 0 → 冲突，探测1	1	2

散列表：

下标	0	1	2	3	4	5	6	7	8	9
关键字	7	14		8		11	30	18	9

$ASL_{成功} = \frac{1+2+1+1+3+3+1}{7} = \frac{12}{7} \approx 1.71$

$ASL_{失败}$：计算每个散列地址（0~6）查找失败需要的比较次数（从该地址开始探测直到遇到空位置），然后取平均。

散列地址 $H$	探测序列	到空位置的比较次数
0	0(7) → 1(14) → 2(空)	3
1	1(14) → 2(空)	2
2	2(空)	1
3	3(8) → 4(空)	2
4	4(空)	1
5	5(11) → 6(30) → 7(18) → 8(9) → 9(空)	5
6	6(30) → 7(18) → 8(9) → 9(空)	4

$ASL_{失败} = \frac{3+2+1+2+1+5+4}{7} = \frac{18}{7} \approx 2.57$

⚠️ 注意：$ASL_{失败}$ 的分母是散列函数值域的大小（即 $p$ 的值 = 7，对应地址06），而不是表长10。因为任何关键字通过 $H(key) = (key \times 3) \% 7$ 只会映射到 06。

【2024年408应用题】 散列函数 $H(key) = (key \times 3) \% 11$，表长 $m=11$，采用平方探测法（二次探测法）处理冲突，$H_k = (H_0 + k^2) \% m$（$k=1,2,3,\ldots$），依次插入一组关键字并计算 ASL。

平方探测法要点：

• 探测序列：$H_0, H_0+1^2, H_0+2^2, H_0+3^2, \ldots$（均对 $m$ 取余）
• 注意：标准平方探测是 $d_i = 0, 1, -1, 4, -4, 9, -9, \ldots$（正负交替），但真题中可能只取正平方（需看题意）
• 表长 $m$ 必须是 $4k+3$ 形式的素数才能保证探测到所有位置

⚠️ 手动建表步骤：

1. 算 $H_0 = H(key)$
2. 若位置空，插入；若冲突，依次尝试 $(H_0 + 1) \% m$, $(H_0 + 4) \% m$, $(H_0 + 9) \% m, \ldots$
3. 记录每个关键字的比较次数
4. $ASL_{成功}$ = 所有关键字比较次数之和 / 关键字个数

【2023年408真题】 对含 600 个元素的有序表进行折半查找，最多需要比较多少次？

$\text{最多比较次数} = \lfloor \log_2 n \rfloor + 1 = \lfloor \log_2 600 \rfloor + 1 = 9 + 1 = 10$

💡 公式记忆：折半查找判定树的高度 $h = \lfloor \log_2 n \rfloor + 1$，最多比较次数就等于树高。等价于 $\lceil \log_2(n+1) \rceil$。

【2025年408真题】 分块查找中，$n$ 个元素等分为若干块，使 ASL 最小的最优块大小？

$\text{最优块大小} = \sqrt{n}$

• 设共 $b$ 块，每块 $s$ 个元素，则 $b = n/s$
• 顺序查找索引 + 顺序查找块内：$ASL = \frac{b+1}{2} + \frac{s+1}{2} = \frac{n/s+1}{2} + \frac{s+1}{2}$
• 由均值不等式，$s = \sqrt{n}$ 时 $ASL$ 取最小值 $\approx \sqrt{n} + 1$

例：$n=400$，最优分 $\sqrt{400}=20$ 块，每块 20 个元素。

【B树高频考点汇总】（2023、2025年多次出题）：

考点	结论	年份
B树插入	插入只在叶结点（最底层非叶结点）进行	2023
B树插入可能增加高度	根结点分裂 → 高度+1	2023
B树删除	删除可能导致非叶结点变化（替换+合并）	2023
4阶B树7个关键字	可能的树形态不止一种（取决于插入顺序）	2025
$m$ 阶B树最少关键字	根: $1$; 非根非叶: $\lceil m/2 \rceil - 1$	常考
B树高度计算	$n$ 个关键字的 $m$ 阶B树高度 $h$: $\log_m(n+1) \leq h \leq \log_{\lceil m/2 \rceil}\frac{n+1}{2} + 1$	常考

【散列表ASL计算中的"逻辑删除"陷阱】（2023年考点）：

散列表中执行逻辑删除后，被删位置标记为"已删除"，查找时仍需越过该位置继续探测。因此：

• 删除元素后，$ASL_{成功}$（针对剩余元素）可能不变或不减
• $ASL_{失败}$ 不受影响（因为失败查找必须到空位停止，已删标记不是空位）

📌 第七章总结

核心知识点	考研要求
ASL的概念及计算	高频考点
顺序查找	了解即可
折半查找及判定树	重中之重，选择题和大题都常考
分块查找	理解概念
二叉排序树（BST）的查找、插入、删除	必须掌握
平衡二叉树（AVL）的旋转调整	高频考点
红黑树的性质	近年新考点，需掌握
B树的定义、插入（分裂）	重点
B+树与B树的区别	高频选择题
散列表的构造（除留余数法）	必须掌握
线性探测法解决冲突	大题常考
拉链法	需要掌握
散列表的ASL计算	重中之重

---

第八章 排序

8.1 排序的基本概念

排序：将一组无序数据按照关键字递增（或递减）排列。

稳定性：若排序前两个相等的元素 $R_i$ 和 $R_j$（$i < j$），排序后 $R_i$ 仍在 $R_j$ 前面，则称排序算法是稳定的，否则是不稳定的。

🗣️ 大白话：假设班里有两个学生都叫"张三"，排序前 A张三 在 B张三 前面。如果排序后 A张三 还在前面，这种排序就是"稳定"的。

内部排序 vs 外部排序：

• 内部排序：数据全部在内存中
• 外部排序：数据量大，需借助外存

🔗 【跨学科联动·OS/计组】 排序算法的选择与 OS 和计组紧密关联：

• OS·外部排序：当数据无法全部装入内存时，需要利用 OS 的文件系统和缓冲区管理进行外部归并排序。归并路数受内存缓冲区数量限制
• OS·虚拟内存：排序时若访问模式不佳（如快排的随机跳转访问），可能导致大量缺页中断，严重影响性能
• 计组·Cache 友好性：归并排序的顺序访问模式比快排的随机访问更Cache 友好，但快排的常数因子更小。实际工程中常在小规模子问题切换为插入排序以提升 Cache 命中率
• OS·进程调度：优先级队列调度本质就是用堆排序的思想——每次取出优先级最高的进程执行

---

8.2 插入排序

一、直接插入排序

思想：将待排序元素插入到已排好的有序子序列中的适当位置。

void InsertSort(ElemType A[], int n) {
    int i, j;
    for (i = 2; i <= n; i++) {      // 从第2个元素开始
        if (A[i] < A[i-1]) {        // 若当前元素小于前驱
            A[0] = A[i];            // 复制为哨兵
            for (j = i - 1; A[0] < A[j]; j--)
                A[j+1] = A[j];      // 记录后移
            A[j+1] = A[0];          // 复制到插入位置
        }
    }
}

// 直接插入排序（Java版，下标从0开始）
void insertSort(int[] A, int n) {
    for (int i = 1; i < n; i++) {
        if (A[i] < A[i - 1]) {
            int temp = A[i];
            int j;
            for (j = i - 1; j >= 0 && temp < A[j]; j--)
                A[j + 1] = A[j];   // 记录后移
            A[j + 1] = temp;        // 复制到插入位置
        }
    }
}

分析项	值
时间复杂度（最好）	$O(n)$（已有序）
时间复杂度（最坏）	$O(n^2)$（逆序）
时间复杂度（平均）	$O(n^2)$
空间复杂度	$O(1)$
稳定性	✅ 稳定
适用场景	基本有序、数据量小

二、折半插入排序

思想：在直接插入排序的基础上，用折半查找来确定插入位置（减少比较次数，但移动次数不变）。

void InsertSort_Binary(ElemType A[], int n) {
    int i, j, low, high, mid;
    for (i = 2; i <= n; i++) {
        A[0] = A[i];             // 暂存到哨兵
        low = 1; high = i - 1;
        while (low <= high) {    // 折半查找插入位置
            mid = (low + high) / 2;
            if (A[mid] > A[0]) high = mid - 1;
            else low = mid + 1;  // A[mid] <= A[0] → 右半区（保证稳定性）
        }
        for (j = i - 1; j >= high + 1; j--)
            A[j+1] = A[j];       // 统一后移
        A[high+1] = A[0];        // 插入
    }
}

// 折半插入排序（Java版，下标从0开始）
void insertSortBinary(int[] A, int n) {
    for (int i = 1; i < n; i++) {
        int temp = A[i];
        int low = 0, high = i - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (A[mid] > temp) high = mid - 1;
            else low = mid + 1;  // 保证稳定性
        }
        for (int j = i - 1; j >= high + 1; j--)
            A[j + 1] = A[j];
        A[high + 1] = temp;
    }
}

⚠️ 注意：折半查找中，当 A[mid] == A[0] 时，应继续在右半区查找（low = mid + 1），这样才能保证排序的稳定性。

分析项	值
时间复杂度	$O(n^2)$（移动次数与直接插入排序相同）
比较次数	$O(n \log n)$（优化了比较）
稳定性	✅ 稳定
适用	数据量不大的排序；对链表无法使用（需折半查找）

三、希尔排序（缩小增量排序）

思想：将序列按增量 $d$ 分成若干组，对每组进行直接插入排序；逐步减小增量直到 $d=1$。

例：增量序列 d = {5, 3, 1}，序列 = {49, 38, 65, 97, 76, 13, 27, 49, 55, 4}
第1趟：d=5，分5组 {49,13} {38,27} {65,49} {97,55} {76,4}
       组内排序后：13 27 49 55 4 49 38 65 97 76
第2趟：d=3，分3组 {13,55,38,76} {27,4,65} {49,49,97}
       组内排序后：13 4 49 38 27 49 55 65 97 76
第3趟：d=1，整体插入排序（此时已基本有序，很快）
       最终结果：4 13 27 38 49 49 55 65 76 97

void ShellSort(ElemType A[], int n) {
    int d, i, j;
    for (d = n/2; d >= 1; d = d/2) {     // 增量变化
        for (i = d + 1; i <= n; i++) {    // 对每个组进行插入排序
            if (A[i] < A[i-d]) {
                A[0] = A[i];              // 暂存（A[0]仅作暂存，不做哨兵）
                for (j = i - d; j > 0 && A[0] < A[j]; j -= d)
                    A[j+d] = A[j];        // 记录后移
                A[j+d] = A[0];
            }
        }
    }
}

// 希尔排序（Java版，下标从0开始）
void shellSort(int[] A, int n) {
    for (int d = n / 2; d >= 1; d /= 2) {
        for (int i = d; i < n; i++) {
            if (A[i] < A[i - d]) {
                int temp = A[i];
                int j;
                for (j = i - d; j >= 0 && temp < A[j]; j -= d)
                    A[j + d] = A[j];
                A[j + d] = temp;
            }
        }
    }
}

⚠️ 增量序列的选择：希尔提出的 $d_1 = n/2, d_{i+1} = \lfloor d_i/2 \rfloor$ 在最坏情况下仍为 $O(n^2)$。Hibbard增量序列 $\{1, 3, 7, 15, \ldots, 2^k-1\}$ 可达 $O(n^{3/2})$。增量序列的最后一个值必须为1。各增量值应互质，否则前面趟次的排序工作可能被"浪费"。

分析项	值
时间复杂度	取决于增量序列，最坏 $O(n^2)$，某些增量序列可达 $O(n^{1.3})$
空间复杂度	$O(1)$
稳定性	❌ 不稳定（相同关键字可能被分到不同子表，相对位置改变）
适用	仅适用于顺序表（需随机访问）

---

8.3 交换排序

一、冒泡排序

思想：从后往前（或从前往后）两两比较相邻元素，如果逆序就交换。每趟确定一个元素的最终位置。

void BubbleSort(ElemType A[], int n) {
    for (int i = 0; i < n - 1; i++) {
        bool flag = false;
        for (int j = n - 1; j > i; j--) {
            if (A[j-1] > A[j]) {
                swap(A[j-1], A[j]);
                flag = true;
            }
        }
        if (flag == false) return;  // 没有交换，已经有序
    }
}

void bubbleSort(int[] A, int n) {
    for (int i = 0; i < n - 1; i++) {
        boolean flag = false;
        for (int j = n - 1; j > i; j--) {
            if (A[j - 1] > A[j]) {
                int temp = A[j - 1]; A[j - 1] = A[j]; A[j] = temp;
                flag = true;
            }
        }
        if (!flag) return;  // 没有交换，已经有序
    }
}

分析项	值
时间复杂度（最好）	$O(n)$（已有序，只需一趟扫描）
时间复杂度（最坏）	$O(n^2)$（逆序）
时间复杂度（平均）	$O(n^2)$
空间复杂度	$O(1)$
稳定性	✅ 稳定

冒泡排序特征：每趟排序至少确定一个元素的最终位置。

二、快速排序（⭐ 最重要的排序算法）

思想：分治法。选择一个枢轴（pivot），将序列分成两部分——小于枢轴的放左边，大于枢轴的放右边，然后递归处理左右两部分。

void QuickSort(ElemType A[], int low, int high) {
    if (low < high) {
        int pivotpos = Partition(A, low, high);
        QuickSort(A, low, pivotpos - 1);   // 排左半部分
        QuickSort(A, pivotpos + 1, high);  // 排右半部分
    }
}

int Partition(ElemType A[], int low, int high) {
    ElemType pivot = A[low];  // 取第一个元素为枢轴
    while (low < high) {
        while (low < high && A[high] >= pivot) high--;
        A[low] = A[high];     // 比枢轴小的移到左端
![快速排序Partition过程](图表/DS/DS-17_QuickSortPartition.png)
        while (low < high && A[low] <= pivot) low++;
        A[high] = A[low];     // 比枢轴大的移到右端
    }
    A[low] = pivot;           // 枢轴元素存放到最终位置
    return low;
}

void quickSort(int[] A, int low, int high) {
    if (low < high) {
        int pivotpos = partition(A, low, high);
        quickSort(A, low, pivotpos - 1);   // 排左半部分
        quickSort(A, pivotpos + 1, high);  // 排右半部分
    }
}

int partition(int[] A, int low, int high) {
    int pivot = A[low];  // 取第一个元素为枢轴
    while (low < high) {
        while (low < high && A[high] >= pivot) high--;
        A[low] = A[high];     // 比枢轴小的移到左端
        while (low < high && A[low] <= pivot) low++;
        A[high] = A[low];     // 比枢轴大的移到右端
    }
    A[low] = pivot;           // 枢轴元素存放到最终位置
    return low;
}

分析项	值
时间复杂度（最好）	$O(n \log n)$（每次枢轴都恰好在中间）
时间复杂度（最坏）	$O(n^2)$（已有序或逆序，退化为冒泡）
时间复杂度（平均）	$O(n \log n)$（所有内部排序中平均性能最优）
空间复杂度	$O(\log n)$（递归栈深度），最坏 $O(n)$
稳定性	❌ 不稳定

🗣️ 大白话：快速排序像分苹果——先选一个标准苹果（枢轴），比它小的放左边筐，比它大的放右边筐，然后对两个筐分别重复这个过程。

⚠️ 快排的关键：枢轴的选择。如果每次都选到最大或最小的元素，效率退化为 $O(n^2)$。

枢轴优化策略：

• 三数取中法（Median-of-Three）：取 A[low]、A[mid]、A[high] 三者的中间值作为枢轴，可以有效避免退化
• 随机选枢轴：在 [low, high] 中随机选取一个元素与 A[low] 交换，再按常规方法划分
• 当子序列很短（如 n ≤ 10）时切换为直接插入排序，减少递归开销

⚠️ 区分概念：一次划分（Partition）确定一个元素的最终位置 ≠ 一趟排序。"一趟排序"指的是对当前递归层的所有子表各进行一次划分。例如第2趟排序可能同时对左右两个子表进行划分，确定2个元素的最终位置。

快速排序的重要特征：

• 每次Partition都能确定一个元素（枢轴）的最终位置
• 快速排序是所有内部排序中平均性能最好的
• 快排的递归栈深度：最好 $O(\log n)$，最坏 $O(n)$
• 快排不产生有序子序列（不像冒泡/选择那样每趟生成全局最值），但每趟排序后枢轴元素一定在最终位置
• 若要判断某序列是否可能是快排某趟后的结果，可检查是否恰好有对应个数的元素已到了最终位置

---

8.4 选择排序

一、简单选择排序

思想：每趟从待排序元素中选出最小的元素，放到已排序序列的末尾。

void SelectSort(ElemType A[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min = i;
        for (int j = i + 1; j < n; j++)
            if (A[j] < A[min]) min = j;
        if (min != i) swap(A[i], A[min]);
    }
}

void selectSort(int[] A, int n) {
    for (int i = 0; i < n - 1; i++) {
        int min = i;
        for (int j = i + 1; j < n; j++)
            if (A[j] < A[min]) min = j;
        if (min != i) {
            int temp = A[i]; A[i] = A[min]; A[min] = temp;
        }
    }
}

分析项	值
时间复杂度	始终 $O(n^2)$（无论是否有序，比较次数相同）
空间复杂度	$O(1)$
稳定性	❌ 不稳定（例：$\{2, 2, 1\}$）
移动次数	最好 $0$，最坏 $3(n-1)$

二、堆排序（⭐ 重要）

堆的定义：

• 大根堆（最大堆）：$L[i] \geq L[2i]$ 且 $L[i] \geq L[2i+1]$（每个结点 ≥ 其孩子）
• 小根堆（最小堆）：$L[i] \leq L[2i]$ 且 $L[i] \leq L[2i+1]$（每个结点 ≤ 其孩子）

🗣️ 大白话：大根堆就像公司的层级结构——老板（根）的工资最高，每个经理的工资都比手下高。

建堆：从最后一个非叶子结点 $\lfloor n/2 \rfloor$ 开始，自下而上下滤调整。时间复杂度：$O(n)$

💡 建堆 $O(n)$ 的证明：设完全二叉树高度为 $h = \lfloor \log_2 n \rfloor$，第 $i$ 层最多有 $2^{i-1}$ 个结点，每个结点最多下滤 $h-i$ 层。总比较次数 $\leq \sum_{i=1}^{h} 2^{i-1}(h-i)$。令 $j = h-i$，得 $\sum_{j=0}^{h-1} 2^{h-1-j} \cdot j = 2^{h-1} \sum_{j=0}^{h-1} \frac{j}{2^j}$。由差比数列求和知 $\sum_{j=0}^{\infty} \frac{j}{2^j} = 2$，故总次数 $\leq 2^{h-1} \times 2 = 2^h \leq n$，即 $O(n)$。

🗣️ 大白话：建堆之所以是 $O(n)$ 而不是 $O(n \log n)$，是因为大部分结点都在底层、需要调整的层数很少，而少数结点在顶层虽然需要调整很多层但数量极少。

// 大根堆的下滤调整（将以k为根的子树调整为大根堆）
void HeapAdjust(ElemType A[], int k, int len) {
    A[0] = A[k];  // 暂存
    for (int i = 2*k; i <= len; i *= 2) {
        if (i < len && A[i] < A[i+1])
            i++;          // 选较大的孩子
        if (A[0] >= A[i])
            break;        // 已经满足堆性质
        else {
            A[k] = A[i];  // 将孩子上移
            k = i;
        }
    }
    A[k] = A[0];
}

// 大根堆的下滤调整（Java版，下标从1开始）
void heapAdjust(int[] A, int k, int len) {
    int temp = A[k];  // 暂存
    for (int i = 2 * k; i <= len; i *= 2) {
        if (i < len && A[i] < A[i + 1])
            i++;              // 选较大的孩子
        if (temp >= A[i])
            break;            // 已经满足堆性质
        else {
            A[k] = A[i];      // 将孩子上移
            k = i;
        }
    }
    A[k] = temp;
}

堆排序过程（升序用大根堆）：

1. 建立大根堆
2. 将堆顶元素（最大值）与末尾元素交换
3. 对剩余 $n-1$ 个元素重新调整为大根堆
4. 重复2-3

void HeapSort(ElemType A[], int len) {
    // 建堆
    for (int i = len/2; i > 0; i--)
        HeapAdjust(A, i, len);
    // 排序
    for (int i = len; i > 1; i--) {
        swap(A[1], A[i]);        // 堆顶与末尾交换
        HeapAdjust(A, 1, i-1);  // 调整剩余元素
    }
}

void heapSort(int[] A, int len) {
    // 建堆
    for (int i = len / 2; i > 0; i--)
        heapAdjust(A, i, len);
    // 排序
    for (int i = len; i > 1; i--) {
        int temp = A[1]; A[1] = A[i]; A[i] = temp;  // 堆顶与末尾交换
        heapAdjust(A, 1, i - 1);                     // 调整剩余元素
    }
}

分析项	值
时间复杂度	始终 $O(n \log n)$（建堆 $O(n)$ + 调整 $O(n \log n)$）
空间复杂度	$O(1)$
稳定性	❌ 不稳定

堆的插入和删除：

• 插入：将新元素放在末尾，然后上滤调整（Sift Up） $O(\log n)$
• 删除堆顶：将末尾元素替换堆顶，然后下滤调整（Sift Down） $O(\log n)$
• 删除任意位置：将末尾元素替换到删除位置，然后视情况上滤或下滤

// 大根堆的上滤操作（插入新元素后，从末尾向上调整）
void SiftUp(ElemType A[], int k) {
    // k为新元素下标（已放置在末尾）
    A[0] = A[k];           // 暂存
    int i = k / 2;         // 父结点
    while (i > 0 && A[i] < A[0]) {
        A[k] = A[i];       // 父结点下移
        k = i;
        i = k / 2;
    }
    A[k] = A[0];
}

// 大根堆的上滤操作（Java版，下标从1开始）
void siftUp(int[] A, int k) {
    int temp = A[k];
    int i = k / 2;
    while (i > 0 && A[i] < temp) {
        A[k] = A[i];
        k = i;
        i = k / 2;
    }
    A[k] = temp;
}

⚠️ 注意：对堆进行插入/删除操作后，调整的时间复杂度为 $O(\log n)$，而非 $O(n)$。建堆才是 $O(n)$，不要混淆！

💡 堆可以用于：优先队列（任务调度）、Top-K 问题（从海量数据中找前K个最大/最小值）

---

8.5 归并排序与基数排序

一、归并排序（2路归并）

思想：分治法。将序列分成两半，分别排序，然后将两个有序序列合并成一个有序序列。

void MergeSort(ElemType A[], int low, int high) {
    if (low < high) {
        int mid = (low + high) / 2;
        MergeSort(A, low, mid);       // 排左半部分
        MergeSort(A, mid + 1, high);  // 排右半部分
        Merge(A, low, mid, high);      // 合并
    }
}

void mergeSort(int[] A, int low, int high) {
    if (low < high) {
        int mid = (low + high) / 2;
        mergeSort(A, low, mid);        // 排左半部分
        mergeSort(A, mid + 1, high);   // 排右半部分
        merge(A, low, mid, high);       // 合并
    }
}

// 合并操作
void merge(int[] A, int low, int mid, int high) {
    int[] temp = new int[high - low + 1];
    int i = low, j = mid + 1, k = 0;
    while (i <= mid && j <= high) {
        if (A[i] <= A[j]) temp[k++] = A[i++];
        else temp[k++] = A[j++];
    }
    while (i <= mid)  temp[k++] = A[i++];
    while (j <= high) temp[k++] = A[j++];
    System.arraycopy(temp, 0, A, low, temp.length);
}

合并操作：需要一个辅助数组。

分析项	值
时间复杂度	始终 $O(n \log n)$
空间复杂度	$O(n)$（需要辅助数组）
稳定性	✅ 稳定

🗣️ 大白话：归并排序就像两队已经排好队的人合并成一队——每次从两队头部各看一个人，较小的先站过来，直到两队都站完。

二、基数排序

思想：不比较关键字大小。把关键字拆成若干"位"（如个位、十位、百位），按位进行分配和收集。

**LSD（最低位优先）**方法：

1. 先按个位分配到0~9号桶，再按顺序收集
2. 再按十位分配和收集
3. 再按百位……直到最高位

**MSD（最高位优先）**方法：先按最高位分组，各组内递归。

LSD示例：对 {278, 109, 063, 930, 589, 184, 505, 269, 008, 083} 排序

初始：278 109 063 930 589 184 505 269 008 083

按个位分配（d=1）：
桶0: 930
桶1: 
桶2: 
桶3: 063, 083
桶4: 184
桶5: 505
桶6: 
桶7: 
桶8: 278, 008
桶9: 109, 589, 269

收集：930 063 083 184 505 278 008 109 589 269

按十位分配（d=2）：
桶0: 505, 008, 109
桶6: 063, 269
桶7: 278
桶8: 083, 184, 589
桶9: 930

收集：505 008 109 930 063 269 278 083 184 589

按百位分配（d=3）：
桶0: 008, 063, 083
桶1: 109, 184
桶2: 269, 278
桶5: 505, 589
桶9: 930

收集：008 063 083 109 184 269 278 505 589 930 ✅

时间复杂度：$O(d(n+r))$（$d$ 是位数，$n$ 是元素个数，$r$ 是基数，如十进制 $r=10$）

空间复杂度：$O(r)$（$r$ 个桶/队列）

稳定性：✅ 稳定

⚠️ 基数排序的适用条件：

• 关键字可以方便地拆分成 $d$ 个"组"，且 $d$ 较小
• 每个"组"的取值范围 $r$ 不大
• 关键字之间的比较困难但拆分容易（如字符串、日期）
• 当 $n$ 很大、$d$ 很小、$r$ 较小时效率极高

不适用：关键字取值范围很大、无法拆分为有限位的浮点数等

三、计数排序

思想：统计每个元素出现的次数，然后直接确定每个元素的位置。

三步法：

1. 统计：遍历数组，用辅助数组 C[k] 记录值为 $k$ 的元素个数
2. 累加：$C[i] = C[i] + C[i-1]$，此时 C[k] 表示 $\leq k$ 的元素个数
3. 放置：逆序扫描原数组，将 A[i] 放到 B[C[A[i]]-1] 位置，同时 C[A[i]]--（逆序扫描保证稳定性）

// 计数排序（Java版）
void countingSort(int[] A, int n, int maxVal) {
    int[] C = new int[maxVal + 1];  // 计数数组
    int[] B = new int[n];           // 输出数组
    // 第1步：统计每个值出现次数
    for (int i = 0; i < n; i++) C[A[i]]++;
    // 第2步：累加
    for (int i = 1; i <= maxVal; i++) C[i] += C[i - 1];
    // 第3步：逆序放置（保证稳定性）
    for (int i = n - 1; i >= 0; i--) {
        B[C[A[i]] - 1] = A[i];
        C[A[i]]--;
    }
    System.arraycopy(B, 0, A, 0, n);
}

时间复杂度：$O(n+k)$（$k$ 是数据范围）

空间复杂度：$O(n+k)$（输出数组 + 计数数组）

稳定性：✅ 稳定

⚠️ 适用条件：数据范围 $k$ 不能太大。当 $k > n\log_2 n$ 时，不如基于比较的排序 $O(n\log n)$。适合数据范围有限的非负整数排序。

---

8.6 内部排序算法总结与比较（⭐ 超级重要！）

各排序算法综合对比表

排序算法	最好时间	平均时间	最坏时间	空间	稳定性
直接插入排序	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	✅ 稳定
折半插入排序	$O(n\log n)$	$O(n^2)$	$O(n^2)$	$O(1)$	✅ 稳定
希尔排序	—	—	$O(n^2)$	$O(1)$	❌ 不稳定
冒泡排序	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	✅ 稳定
快速排序	$O(n\log n)$	$O(n\log n)$	$O(n^2)$	$O(\log n)$	❌ 不稳定
简单选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	❌ 不稳定
堆排序	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$	$O(1)$	❌ 不稳定
归并排序	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$	$O(n)$	✅ 稳定
基数排序	$O(d(n+r))$	$O(d(n+r))$	$O(d(n+r))$	$O(r)$	✅ 稳定
计数排序	$O(n+k)$	$O(n+k)$	$O(n+k)$	$O(n+k)$	✅ 稳定

记忆口诀

不稳定排序："快希选堆"（快速排序、希尔排序、简单选择排序、堆排序）

🗣️ 记忆法：想象一个人"快些选堆"（快点儿选那堆东西），但他比较急躁所以不稳定。

重要结论

1. 没有一种排序在任何情况下都最优
2. 快速排序的平均性能最好（内部排序中）
3. 基于比较的排序算法的时间复杂度下界为 $\Omega(n \log n)$

💡 判定树下界定理（CLRS 定理 8.1）严格证明：

• 任何基于比较的排序算法都可以用一棵**判定树（Decision Tree）**表示：内部结点对应一次 $a_i : a_j$ 的比较，叶结点对应排序结果（排列）
• $n$ 个元素有 $n!$ 种排列，故判定树至少有 $n!$ 个叶结点
• 高度为 $h$ 的二叉树最多有 $2^h$ 个叶结点，因此 $2^h \geq n!$，即 $h \geq \lceil \log_2(n!) \rceil$
• 由 Stirling 公式 $n! \approx \sqrt{2\pi n}\left(\frac{n}{e}\right)^n$，得 $\log_2(n!) = \Theta(n \log_2 n)$
• 因此最坏情况下比较次数的下界为 $\Omega(n \log n)$

推论：归并排序和堆排序已达到此下界，是渐近最优的基于比较的排序算法。

突破下界：计数排序、基数排序、桶排序等非比较排序可以绕开判定树下界，达到 $O(n)$，但需要对输入数据有额外约束（如数据范围有限）。

4. 堆排序和归并排序在最坏情况下仍为 $O(n \log n)$，但常数因子不同
5. 当序列基本有序时，直接插入排序最快 $O(n)$；而此时快速排序最慢 $O(n^2)$
6. 当 $n$ 较小时，直接插入排序或简单选择排序效率高
7. 稳定排序：直接插入、冒泡、归并、基数、计数
8. 每趟排序能确定一个元素最终位置的：选择排序、快速排序、冒泡排序、堆排序
9. 排序趟数与初始序列有关的：冒泡排序（可提前终止）、快速排序（递归树结构依赖划分）
10. 排序趟数与初始序列无关的：直接插入排序（始终 $n-1$ 趟）、简单选择排序（始终 $n-1$ 趟）、归并排序（始终 $\lceil \log_2 n \rceil$ 趟）、基数排序（始终 $d$ 趟）
11. 比较次数与初始序列无关的：简单选择排序（始终 $n(n-1)/2$ 次）、折半插入排序（仅比较次数无关）、归并排序、基数排序
12. 关键字比较次数和移动次数都与初始序列无关的：基数排序、归并排序、简单选择排序（比较次数无关，移动次数有关）
13. 不适用于链表存储的排序算法：希尔排序（需要按增量随机访问）、堆排序（需要按下标访问父/子结点）、折半插入排序（需要随机访问中间元素）。直接插入排序、冒泡排序、归并排序、基数排序均可用于链表。
14. 排序算法选择决策：
    • $n$ 较小（$\leq 50$）：直接插入排序或简单选择排序
    • $n$ 较大且要求稳定：归并排序
    • $n$ 较大且不要求稳定：快速排序（平均最优）或堆排序（最坏稳定 $O(n\log n)$）
    • 基本有序的序列：直接插入排序（$O(n)$，避免快排退化）
    • 数据范围有限的整数：计数排序或基数排序（$O(n)$ 级别）

算法设计范式总结（⭐ 贯穿全书的思想框架）

💡 408 数据结构中的所有算法，都可以归入以下几大设计范式。掌握范式后，遇到新问题能快速确定解题方向。

设计范式	核心思想	数据结构中的典型应用	跨学科联动
分治法（Divide & Conquer）	大问题分解为相同类型的子问题，递归求解后合并	归并排序、快速排序、折半查找、二叉树遍历、线段树	—
贪心法（Greedy）	每步做局部最优选择，期望全局最优	Prim、Kruskal、Dijkstra、哈夫曼编码、简单选择排序、拓扑排序（取入度为0的顶点）	OSPF路由（计网）
动态规划（DP）	重叠子问题 + 最优子结构 → 记录中间结果避免重复计算	Floyd最短路径、Bellman-Ford、最优BST、最佳归并树（哈夫曼）、矩阵链乘法、KMP 中 next 数组的递推	—
回溯法（Backtracking）	DFS + 剪枝	图的 DFS 遍历、八皇后、迷宫求解	—
迭代/松弛	不断逼近最优解直到收敛	Bellman-Ford 松弛迭代、并查集路径压缩、堆调整	RIP 路由（计网）
哈希/散列	由关键字直接计算存储地址	散列表、布隆过滤器	Cache映射（计组）、页表（OS）
空间换时间	额外存储加速查询	散列表、后缀数组/树、判定树、邻接矩阵 vs 邻接表	Cache（计组）、TLB（OS+计组）

⚠️ 考试中的"设计一个高效算法"：

• 题目要求 $O(n)$ → 考虑一趟扫描（双指针/三指针/打标记法/Boyer-Moore投票）
• 题目要求 $O(n\log n)$ → 考虑分治或排序后处理
• 题目要求 $O(\log n)$ → 考虑折半查找/平衡树操作
• 题目有"最优/最小/最大" → 考虑贪心或DP
• 题目涉及"连通/可达/路径" → 考虑BFS/DFS/最短路径

根据排序结果判断排序算法（高频选择题技巧）

⚠️ 2010年真题考法：给出初始序列和前几趟排序结果，判断使用的排序方法。

判断技巧：

特征现象	对应排序算法
每趟结果有一个元素到达最终位置（末尾）	冒泡排序（每趟将最大元素"冒泡"到末尾）
每趟结果有一个元素到达最终位置（前端）	简单选择排序（每趟选最小放到前端）
前 $k$ 趟后前 $k+1$ 个元素有序	直接插入排序（前面有序区逐步扩大）
长度为2的子段有序→长度为4→长度为8...	归并排序（子段长度按2的幂增长）
不相邻元素发生交换，整体部分有序	希尔排序（按增量分组排序）
每趟枢轴元素到达最终位置，左小右大	快速排序

例（2010真题）：对 (2, 12, 16, 88, 5, 10)：

• 第1趟：2, 12, 16, 5, 10, 88 → 仅88移到末尾 ✓冒泡
• 验证排除：若希尔排序则 (12, 88, 10) 应变为 (10, 12, 88)，不符；若归并则长度2子段应有序，不符。
• 答案：冒泡排序

折半插入排序 vs 直接插入排序的区别（2012年真题）：

• 排序趟数相同（都是 $n-1$）
• 移动次数相同（取决于初始序列）
• 比较次数不同！折半插入与序列初态无关 $O(n\log n)$，直接插入与序列初态有关 $O(n) \sim O(n^2)$
• 辅助空间都是 $O(1)$

---

8.7 外部排序

一、外部排序的基本概念

问题：数据量太大，无法全部装入内存，需要借助外存（磁盘）进行排序。

基本方法：归并排序的思想

1. 把文件分成若干段，每段读入内存排序（生成初始归并段/顺串）
2. 对初始归并段进行多趟归并，直到整个文件有序

外部排序时间 = 读写外存时间（主要矛盾！）+ 内部排序时间 + 内部归并时间

🗣️ 大白话：外存（磁盘）读写速度比内存慢几个数量级，所以外部排序的核心优化目标就是减少磁盘I/O次数。

详细分析示例：设文件有2000个记录，内存工作区可容纳500个记录。

• 第一步：分4段，每段500个记录 → 生成4个初始归并段（$r=4$）
• 第二步：2路归并 → 归并趟数 $S = \lceil \log_2 4 \rceil = 2$ 趟

每个记录占1个磁盘块，初始4个归并段分布在两个磁盘上：

步骤	读磁盘块数	写磁盘块数	总I/O次数
生成初始归并段	2000	2000	4000
第1趟归并	2000	2000	4000
第2趟归并	2000	2000	4000
总计			12000

若改用4路归并：$S = \lceil \log_4 4 \rceil = 1$ 趟，总I/O = 4000 + 4000 = 8000，显著减少！

性能瓶颈：磁盘I/O次数（读/写磁盘的时间远大于内存中排序的时间）

减少I/O次数的关键：减少归并趟数

$归并趟数 S = \lceil \log_k m \rceil$

其中 $k$ 为归并路数，$m$ 为初始归并段个数。

提高效率的两个方向：

1. 增大归并路数 $k$ → 多路归并（但 $k$ 增大会导致每次选最小元素的比较次数增加 → 用败者树优化）
2. 减少初始归并段个数 $m$ → 使初始归并段更长（用置换-选择排序实现）

二、多路归并与败者树

问题：$k$ 路归并时，每次从 $k$ 个段中选出最小元素需要比较 $k-1$ 次。增大 $k$ 虽然减少趟数，但增加了每趟的比较次数，总比较次数可能不降反升。

败者树（Loser Tree）：一种特殊的完全二叉树，可以将每次选最小值的比较次数从 $k-1$ 降低到 $\lceil \log_2 k \rceil$。

败者树的结构：

• $k$ 个叶结点：存放 $k$ 个归并段的当前元素
• $k-1$ 个内部结点：记录"比赛的失败者"（较大的元素）
• 额外根结点 $ls[0]$：记录"冠军"（最小元素所在归并段编号）

工作原理：

1. 初始化：$k$ 个叶结点两两比较，败者留在父结点，胜者继续向上比较
2. 每次取出最小元素后，从该元素所在归并段读入下一个元素到对应叶结点
3. 仅需沿该叶结点到根的路径重新比较，路径长度 $= \lceil \log_2 k \rceil$

🗣️ 大白话：败者树就像淘汰赛——每次比赛的失败者被记录在结点中，胜利者继续向上比赛。最终冠军就是最小元素。当冠军的归并段送来新选手时，只需沿着"往届对手"重新比赛即可确定新冠军。

败者树的关键性能：

• 构建败者树：$O(k)$ 次比较
• 此后每选一个最小元素：仅需 $\lceil \log_2 k \rceil$ 次比较
• $n$ 个元素、$k$ 路归并的总比较次数：$O(n \log_2 k)$，与 $k$ 无关的量级！
• 每趟归并比较次数：$(n-1) \times \lceil \log_2 k \rceil$（$n$ 个元素选出 $n$ 个最小值，第一个用 $O(k)$ 次建树，此后每次 $\lceil \log_2 k \rceil$ 次）
• 因此增大 $k$ 不会增加总比较次数，只会减少归并趟数

⚠️ 注意：$k$ 也不能无限增大。$k$ 路归并需要 $k$ 个输入缓冲区，受内存限制。实际中常取 $k = 4 \sim 16$。

三、置换-选择排序（生成更长的初始归并段）

问题：内存工作区大小为 $w$，传统方法生成的初始归并段长度也是 $w$。

置换-选择排序可以生成比工作区更长的初始归并段（平均长度为 $2w$）。

算法步骤（设工作区WA容量为 $w$）：

1. 从文件读入 $w$ 个记录到工作区WA
2. 从WA中选出关键字最小的记录 MINIMAX，输出到当前归并段RUN
3. 若文件不空，从文件读入下一个记录补入WA
4. 从WA中所有关键字 $\geq$ MINIMAX 的记录中，选出最小者作为新的MINIMAX输出
5. 重复3-4，直到WA中没有 $\geq$ MINIMAX 的记录
6. 结束当前归并段，开启新的归并段，转步骤2

详细示例（$w = 3$，输入：{17, 21, 05, 44, 10, 12, 56, 32, 29}）：

WA初始：{17, 21, 05}，文件：44 10 12 56 32 29

RUN1：
  选min{17,21,05}=05 → 输出05，读入44 → WA={17,21,44}
  选min{17,21,44}=17 → 输出17，读入10 → WA={10,21,44}
  选≥17的min{21,44}=21 → 输出21，读入12 → WA={10,12,44}
  选≥21的min{44}=44 → 输出44，读入56 → WA={10,12,56}
  选≥44的min{56}=56 → 输出56，读入32 → WA={10,12,32}
  选≥56的：无 → RUN1结束 → 输出：{05,17,21,44,56}（长度5 > w=3!）

RUN2：
  选min{10,12,32}=10 → 输出10，读入29 → WA={29,12,32}
  选min{12,29,32}=12 → 输出12，文件空 → WA={29,32}
  选≥12的min{29,32}=29 → 输出29 → WA={32}
  选≥29的min{32}=32 → 输出32 → WA为空
  → RUN2结束 → 输出：{10,12,29,32}（长度4 > w=3!）

最终生成2个归并段（传统方法需要3个），减少了归并趟数！

四、最佳归并树

问题：初始归并段长度不同时，如何安排归并顺序使磁盘I/O次数最少？

解决方案：用哈夫曼树的思想构造最佳归并树——短的归并段放在树的低层（多归并几次），长的放在高层（少归并几次）。

$总I/O次数 = 2 \times WPL$

其中 WPL 为带权路径长度，权值为各归并段的长度（记录数）。

对于 $k$ 路归并，构造 $k$ 叉哈夫曼树：

⚠️ 虚段补充规则（非常重要！）：

对于 $k$ 路归并，设有 $n_0$ 个初始归并段（叶结点）。严格 $k$ 叉树满足 $n_0 = (k-1) \cdot n_{k} + 1$（$n_k$ 为度为 $k$ 的结点数），即 $(n_0 - 1) \% (k-1) = 0$。

若 $(n_0 - 1) \% (k-1) = u \neq 0$，则需补充 $(k-1-u)$ 个长度为0的虚段（不增加I/O，仅占位），使得 $(n_0 + 补充数 - 1) \% (k-1) = 0$。

虚段在哈夫曼树中一定处于最底层（权值为0，最先被选中合并）。

示例：3路归并，8个初始归并段（长度分别为 2, 3, 6, 7, 9, 12, 18, 24）

• $(8-1) \% (3-1) = 7 \% 2 = 1 \neq 0$，需补充 $(3-1-1) = 1$ 个虚段（长度0）
• 9个段构造3叉哈夫曼树：每次选3个最小的合并
  • 第1次：{0, 2, 3} → 合并为5
  • 第2次：{5, 6, 7} → 合并为18'
  • 第3次：{9, 12, 18} → 合并为39
  • 第4次：{18', 24, 39} → 合并为81
• $WPL = 0 \times 3 + 2 \times 3 + 3 \times 3 + 6 \times 2 + 7 \times 2 + 9 \times 2 + 12 \times 2 + 18 \times 2 + 24 \times 2$

💡 最佳归并树 = k叉哈夫曼树。它使得长度短的归并段被多次读写（在深层），长度长的归并段被少次读写（在浅层），从而总I/O次数最少。

📝 真题剖析

【2012年408真题】 在内部排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一"趟"。下列排序方法中，每一趟处理都能确保将一个尚未确定最终位置之的元素放到其最终位置上的是（）。

Ⅰ. 简单选择排序   Ⅱ. 希尔排序   Ⅲ. 快速排序   Ⅳ. 堆排序   Ⅴ. 二路归并排序

A. 仅Ⅰ、Ⅲ、Ⅳ   B. 仅Ⅰ、Ⅱ、Ⅲ   C. 仅Ⅱ、Ⅲ、Ⅳ   D. 仅Ⅲ、Ⅳ、Ⅴ

解析：

• 简单选择排序 ✅：每趟选出最小/最大的放到最终位置
• 希尔排序 ❌：每趟只是让序列"基本有序"，不保证任何元素到最终位置
• 快速排序 ✅：每趟确定枢轴的最终位置
• 堆排序 ✅：每趟将堆顶（最大/最小值）放到最终位置
• 二路归并排序 ❌：直到最后一趟合并完成前，元素位置可能还会变化

答案选A。

---

【2012年408真题·综合题】 设有6个有序表 $A(10)$、$B(35)$、$C(40)$、$D(50)$、$E(60)$、$F(200)$（括号内为元素个数），通过5次两两合并最终合成1个升序表，求最坏情况下比较总次数最少的合并方案。

解题方法：哈夫曼树（最佳归并树）思想

两个长度为 $m$、$n$ 的有序表合并，最坏情况下比较 $m + n - 1$ 次。为使总比较次数最少，每次选最短的两个表合并（贪心思想）：

第几次合并	合并内容	新表长度	最坏比较次数
1	$A(10) + B(35)$	45	$10+35-1=44$
2	$AB(45) + C(40)$	85	$45+40-1=84$
3	$D(50) + E(60)$	110	$50+60-1=109$
4	$ABC(85) + DE(110)$	195	$85+110-1=194$
5	$ABCDE(195) + F(200)$	395	$195+200-1=394$

$\text{总比较次数} = 44 + 84 + 109 + 194 + 394 = \mathbf{825}$

💡 推广：$N$（$N \geq 2$）个不等长升序表的合并策略——借用哈夫曼树构造思想，每次选最短的两个表合并，可获得最坏情况下的最佳合并效率。本题考点横跨了排序（归并）和树（哈夫曼）两大知识板块。

【2021年408应用题】 实现"比较计数排序"并使其稳定。

**比较计数排序（Comparison Counting Sort）**思想：对每个元素，统计序列中比它小的元素个数 $count[i]$，则 $count[i]$ 就是该元素在有序序列中的最终下标。

// 比较计数排序（不稳定版）
void compCountSort(int[] A, int[] B, int n) {
    int[] count = new int[n]; // count[i] = A中比A[i]小的元素个数
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (A[i] < A[j]) count[j]++;
            else count[i]++;            // A[i] >= A[j]
    for (int i = 0; i < n; i++)
        B[count[i]] = A[i];
}

⚠️ 稳定性修复：上述代码中 A[i] >= A[j] 时 count[i]++，等值元素中先出现的被计数更多，导致先出现的反而排在后面 → 不稳定。

修复方法：将 else count[i]++ 改为严格地只在 A[i] > A[j] 时 count[i]++，并对 A[i] == A[j] 时按原始下标顺序决定谁的 count 更大：

if (A[i] < A[j]) count[j]++;
else if (A[i] > A[j]) count[i]++;
// A[i] == A[j] 时：j > i，不操作 → count[j] 自然较大 → j 排在 i 后面 → 稳定

时间复杂度 $O(n^2)$，空间复杂度 $O(n)$。

【2023年408应用题】 置换-选择排序：内存工作区大小 $m=4$，输入 $n=19$ 个元素，生成初始归并段。

解题要点：

• 初始读入 $m=4$ 个元素到工作区
• 每次从工作区中选 $\geq$ 当前归并段已输出最大值 的最小元素输出
• 工作区中无满足条件的元素时，结束当前归并段，开始新的归并段
• 该题生成了 3 个初始归并段

💡 置换-选择排序的性质：

• 初始归并段平均长度 = $2m$（$m$ 为工作区大小）
• 初始归并段最小长度 = $m$（输入完全逆序时）
• 初始归并段最大长度 = $n$（输入完全升序时，所有元素构成一个归并段）

【2024年408真题】 大根堆 $\{28, 22, 20, 19, 8, 12, 15, 5\}$，连续删除两次堆顶后的结果？

堆删除步骤（大根堆）：

1. 将堆顶（最大值）与最后一个元素交换
2. 堆的规模减1
3. 从堆顶开始向下调整（siftDown）：与较大的子结点交换，直到满足堆的性质

第1次删除堆顶28：

初始：{28, 22, 20, 19, 8, 12, 15, 5}
交换28和5：{5, 22, 20, 19, 8, 12, 15, | 28}
下调5：5<22→交换 → {22, 5, 20, 19, 8, 12, 15}
      5<19→交换 → {22, 19, 20, 5, 8, 12, 15}
结果：{22, 19, 20, 5, 8, 12, 15}

第2次删除堆顶22：

交换22和15：{15, 19, 20, 5, 8, 12, | 22}
下调15：15<20→交换 → {20, 19, 15, 5, 8, 12}
       15>12→停止
结果：{20, 19, 15, 5, 8, 12}

【2024年408真题】 败者树（Loser Tree）中，"冠军"结点 $ls[0]$ 存储的是什么？

💡 $ls[0]$ 存储的是最小关键字所在归并段的段号（不是关键字值本身！）。败者树中间结点存"失败者"（较大值的段号），而 $ls[0]$ 存"冠军"（最小值的段号）。

【2018年408真题】 根据希尔排序某趟结果判断增量。

方法：比较排序前后的序列，找出哪些位置的元素发生了交换。如果间隔为 $d$ 的位置发生了子序列排序，则该趟的增量就是 $d$。

【2025年408应用题】 数组问题 CalMulMax：给定数组 $a[0..n-1]$，求 $f(i) = a[i] \times \max(a[i+1..n-1])$ 的最大值。

三种解法对比：

方法	时间	空间	思路
暴力枚举	$O(n^2)$	$O(1)$	双重循环求每个 $f(i)$
后缀数组	$O(n)$	$O(n)$	预处理 suffixMax/suffixMin 数组
后缀变量	$O(n)$	$O(1)$	仅用两个变量维护后缀 max/min

最优解法（后缀变量，$O(n)$ 时间 $O(1)$ 空间）：

// CalMulMax：求 a[i] × max(a[i+1..n-1]) 的最大值
int calMulMax(int[] a, int n) {
    int suffMax = a[n - 1]; // 后缀最大值
    int suffMin = a[n - 1]; // 后缀最小值（处理负数×负数情况）
    int ans = Integer.MIN_VALUE;
    for (int i = n - 2; i >= 0; i--) {
        // a[i] > 0 时乘 suffMax 最大；a[i] < 0 时乘 suffMin 可能更大
        int cand1 = a[i] * suffMax;
        int cand2 = a[i] * suffMin;
        ans = Math.max(ans, Math.max(cand1, cand2));
        suffMax = Math.max(suffMax, a[i]);
        suffMin = Math.min(suffMin, a[i]);
    }
    return ans;
}

💡 关键技巧：从右往左扫描，同时维护后缀最大值和最小值。考虑负数乘负数为正的情况，因此需要同时维护 suffMax 和 suffMin。

【排序方法识别——根据中间结果反推排序算法】（高频选择题）：

线索	对应排序算法
每趟确定一个元素的最终位置（最大/最小）	简单选择排序 / 堆排序
第 $k$ 趟后前 $k$ 个元素有序	直接插入排序
第 $k$ 趟后最小的 $k$ 个元素已就位	简单选择排序
第 $k$ 趟后最大的 $k$ 个元素已就位	冒泡排序（大值上浮）
枢轴元素在最终位置，左小右大	快速排序
间隔 $d$ 的子序列分别有序	希尔排序（增量=d）
子序列长度翻倍逐步有序	归并排序（子表从2到4到8...）
按位/数位分配	基数排序

📌 第八章总结

核心知识点	考研要求
排序的稳定性概念	必须理解
直接插入排序	必须掌握
折半插入排序	了解与直接插入的区别
希尔排序	理解思想，考选择题
冒泡排序	必须掌握
⭐ 快速排序（Partition过程）	重中之重，大题必考
简单选择排序	必须掌握
⭐ 堆排序（建堆、调整）	重中之重，大题常考
⭐ 归并排序	必须掌握
基数排序	理解思想，考选择题
⭐ 内部排序大比较表	必须完全熟记
不稳定排序口诀"快希选堆"	必须牢记
外部排序的基本概念	理解
败者树	理解其优化作用
置换-选择排序	理解思想
最佳归并树（哈夫曼思想）	需要掌握

---

📋 数据结构全书终极总结

一、各章节在408考试中的分值分布（近年趋势）

章节	常考题型	预估分值
第一章 绪论	选择题	2~4分
第二章 线性表	选择题 + 大题	6~10分
第三章 栈/队列/数组	选择题	4~6分
第四章 串	选择题（KMP）	2~4分
第五章 树与二叉树	选择题 + 大题	8~12分
第六章 图	选择题 + 大题	6~10分
第七章 查找	选择题 + 大题	6~8分
第八章 排序	选择题 + 大题	6~10分

二、高频考点清单（必须重点突破）

1. 时间复杂度分析（选择题必考）——注意 $O(\sqrt{n})$、嵌套 $i \times i \leq n$ 等变形（2017, 2019, 2025）
2. 链表的基本操作（大题高频）——快慢指针、反转、合并三板斧（2018, 2019, 2024）
3. 栈的出入序列判断 / 表达式转换（选择题常考）
4. KMP的next数组求解（选择题必考）——比较次数计算（2019年：10次）
5. 二叉树遍历 + 由遍历序列构造二叉树（大题常考）
6. 二叉树性质（$n_0 = n_2 + 1$ 等）（选择题必考）
7. 哈夫曼树的构造与WPL（选择题常考）——WPL计算（2021）、平均编码长度（2023）
8. 图的遍历（BFS/DFS）（选择题常考）
9. Dijkstra / Floyd 最短路径（大题常考）
10. 拓扑排序 / 关键路径（选择题+大题）——唯一拓扑排序的判定（2024）、AOE工期压缩（2025）
11. BST的操作 / AVL的旋转（选择题常考）——BST顺序存储验证（2022）
12. AVL树的删除（不平衡向上传导，新增考点）
13. 红黑树的定义、性质与插入（2013/2015真题，近年热点）
14. B树的插入（分裂）与删除（兄弟借/合并）（选择题常考）——B树高度范围（2023, 2025）
15. 散列表的构建与ASL计算（大题高频）——平方探测法（2024）、逻辑删除影响（2023）
16. 快速排序Partition过程（大题高频）
17. 堆排序的建堆与调整（大题高频）——连续删除堆顶的过程（2024）
18. 各排序算法综合比较（选择题必考）——根据中间结果反推排序算法
19. 排序稳定性判断（选择题必考）——比较计数排序的稳定性修复（2021）
20. 外部排序（置换-选择排序生成归并段（2023）、败者树冠军含义（2024）、最佳归并树虚段补充）

三、2009-2025年真题应用题考点一览（数据结构部分）

年份	题号	考点	时间要求
2009	Q42	单链表查找倒数第k个结点（双指针法）	$O(n)$
2010	Q42	数组循环左移p位（三次翻转法）	$O(n)$
2011	Q42	两等长升序序列求中位数（折半淘汰法）	$O(\log n)$
2012	Q42	两链表求公共后缀起始位置（等长对齐法）	$O(m+n)$
2013	Q41	主元素查找（Boyer-Moore投票算法）	$O(n)$
2013	Q42	查找方法比较（ASL计算）	—
2014	Q41	WPL算法（二叉树遍历求加权路径长度）	$O(n)$
2014	Q42	邻接矩阵 $A^2$ 含义	—
2015	Q41	删除链表中绝对值重复结点	$O(n)$
2015	Q42	$A^m$ 矩阵幂的物理意义	—
2016	Q42	$k$ 叉正则树的叶结点公式	—
2016	Q43	数组划分（Partition变形）	$O(n)$
2017	Q41	表达式树→中缀表达式（加括号）	—
2018	Q41	找未出现的最小正整数	$O(n)$
2018	Q42	MST（最小生成树）	—
2019	Q41	链表后半段逆置后交叉合并	$O(n)$
2019	Q42	循环链式队列	—
2020	Q41	三个升序数组求 $\min(\|a-b\|+\|b-c\|+\|c-a\|)$	$O(l_1+l_2+l_3)$
2020	Q42	哈夫曼编码解码	—
2021	Q41	欧拉路径（BFS+奇度数顶点统计）	$O(V+E)$
2021	Q42	比较计数排序（稳定性修复）	$O(n^2)$
2022	Q41	BST顺序存储验证（中序递归/前序递归）	$O(n)$
2022	Q42	从10万+元素中选最小的10个	$O(n)$
2023	Q41	K-顶点（出度>入度）邻接矩阵	$O(V^2)$
2023	Q42	置换-选择排序生成初始归并段	—
2024	Q41	唯一拓扑排序判定	$O(V+E)$
2024	Q42	散列表平方探测法建表+ASL	—
2025	Q41	CalMulMax（后缀最值优化）	$O(n)$
2025	Q42	AOE关键路径+活动压缩	—

四、408考纲数据结构部分重要变化

年份	变化内容	影响
2022年	新增红黑树（定义、性质、插入操作）	2013/2015年已考过选择题，正式入纲后考频会增加
2022年	新增并查集（Find、Union、路径压缩）	在图论和集合操作中考查
2022年	BST、AVL 从"树"章移至"查找"章	章节归属变化，不影响考查内容
2025年	"堆及其应用"表述更明确	强调堆的应用场景（优先队列、topK等）

⚠️ 备考提示：红黑树和并查集是2022年新入纲的内容，近年出题概率高。红黑树重点掌握5条性质和插入时的调整规则（黑叔旋转、红叔变色上传）；并查集重点掌握按秩合并+路径压缩的优化。

五、应试技巧

1. 选择题：熟记性质和公式，快速计算。注意"陷阱选项"（如Dijkstra不能用于负权图、快排最坏$O(n^2)$等）
2. 大题（算法设计题）：
   • 先用自然语言描述算法思想（4~5分）
   • 再写出代码（C/C++皆可）（7~8分）
   • 最后分析时间和空间复杂度（2~3分）
   • 注意边界条件的处理
   • ⚠️ 追求一遍扫描的 $O(n)$ 解法而非两遍扫描，评分标准差异大（如2009年倒数第k个结点题：一遍扫描15分，两遍扫描最高10分）
3. 历年真题反复练习：408真题的复现率很高，历年真题是最好的复习资料
4. 画图辅助理解：树、图、排序过程等，一定要多画图
5. 经典算法设计题型总结：

题目类型	核心技巧	真题年份
链表找倒数第k个结点	双指针（快慢指针）	2009
数组循环左移	三次翻转法（Reverse）	2010
两等长升序序列求中位数	折半淘汰法	2011
两链表求公共后缀起始点	等长对齐+同步前进	2012
多个有序表最优合并	哈夫曼树思想	2012
主元素查找	Boyer-Moore投票算法	2013
散列表构造+ASL计算	线性/平方探测法	2010, 2024
删除链表重复元素	标记数组 $O(n)$	2015
数组划分	Partition 变形	2016
表达式树→中缀	中序遍历+括号处理	2017
找未出现最小正整数	标记数组原地标记	2018
链表后半逆置交叉合并	快慢指针+反转+合并	2019
三升序数组最小距离	三指针+绝对值化简	2020
欧拉路径判定	BFS连通性+奇度数统计	2021
BST顺序存储验证	中序/前序递归	2022
K-顶点查找	邻接矩阵行列遍历	2023
唯一拓扑排序判定	每步检查0-入度顶点数	2024
后缀最值数组优化	后缀max/min + 一趟扫描	2025

---

六、408 跨学科联动速查表

数据结构是408四门课的「公共语言」。以下是数据结构知识点在其他三门课中的高频联动点，在选择题和大题中经常作为跨学科综合考查依据。

数据结构知识点	计算机组成原理	操作系统	计算机网络
顺序表/数组	基址+偏移寻址；行优先/列优先存储	连续内存分配；外部碎片	—
链表	指针=内存地址	链接文件分配；空闲链表	—
栈	堆栈寻址（SP寄存器）；中断现场保护	函数调用栈帧；递归→栈溢出	—
队列	—	就绪队列（FCFS调度）；缓冲池	路由器缓冲队列；FIFO页面置换
树	—	文件目录树；多级页表	—
二叉树/堆	—	优先级调度（堆）	—
图	—	死锁检测（资源分配图环路检测）	网络拓扑；路由算法
BFS/DFS	—	死锁检测（DFS找环）	OSPF洪泛
Dijkstra	—	—	OSPF协议（链路状态路由）
Bellman-Ford	—	—	RIP协议（距离向量路由）
B树/B+树	磁盘块大小=结点大小	文件系统索引（inode多级索引）	—
散列表	Cache直接映射（取余）	页表映射；TLB（快表）	CRC/MD5校验
排序	Cache命中率（顺序vs随机访问）	外部排序（磁盘I/O）；缺页率	—
哈夫曼编码	变长操作码编码（扩展操作码）	文件压缩	数据压缩传输

七、408数据结构高频失分陷阱速查表（⭐ 考前必看）

⚠️ 以下是历年真题中考生失分率最高的知识点陷阱，逐条列出以供考前快速核查。

#	陷阱描述	正确结论	相关真题
1	认为 $O(\log n)$ 中的底数重要	$\log_a n = \log_a b \cdot \log_b n$，底数之差是常数因子，大 $O$ 下底数无关	Ch1
2	混淆"最好/最坏/平均"时间复杂度	$O$ 是上界，$\Omega$ 是下界，$\Theta$ 是紧界。"平均 $O(n^2)$"≠"每次 $O(n^2)$"	Ch1
3	认为循环队列必须空一个位置	空一个位置只是3种判空/满方法之一，也可用计数或 tag 标志	Ch3
4	KMP 中 next 数组下标从 0 或 1 开始时结果不同	下标起点不同 → next 值差1，需看清题目约定。王道从1开始。严蔚敏原版也从1开始	Ch4
5	认为 Dijkstra 可处理负权边	Dijkstra 不能处理负权边（贪心策略在负权下失效），需用 Bellman-Ford	Ch6
6	认为"每趟确定一个元素最终位置" = 冒泡	选择排序、堆排序、快排的 Partition 也能每趟确定一个元素最终位置	Ch8/2012
7	快排"一趟排序" ≠ 一次 Partition	一趟 = 当前递归层所有子表各执行一次 Partition	Ch8
8	认为建堆时间 = $O(n\log n)$	自底向上建堆 = $O(n)$，不是 $O(n\log n)$	Ch8
9	折半插入排序的比较次数与初始序列无关，但移动次数有关	总时间仍 $O(n^2)$（移动次数决定了量级）	Ch8/2012
10	散列表逻辑删除后，$ASL_{\text{成功}}$ 可能不减	被删位置标记"已删"，查找时仍需越过，比较次数不减	Ch7/2023
11	AVL树删除只需一次旋转	AVL 删除可能导致不平衡向上传导，最坏需 $O(\log n)$ 次旋转	Ch7
12	红黑树中 NULL 结点（外部结点）算黑色	性质3"叶结点（NIL）为黑色"中的叶结点是外部 NULL 结点，不是通常意义的叶子	Ch7
13	B树插入只影响叶结点	插入导致分裂可能逐层上传至根，使树高增1	Ch7/2023
14	归并排序"每趟"后子段长度翻倍只适用于自底向上归并	自顶向下递归归并的子段变化规律不同	Ch8
15	认为"稳定排序"不会改变相等元素的相对顺序	稳定排序只保证相等元素的相对顺序不变，不同元素的相对顺序当然会变	Ch8
16	图的 BFS/DFS 序列唯一	邻接表存储时，邻接顶点的访问顺序取决于链表中的排列顺序，序列不唯一	Ch6
17	大题算法只追求正确性	一遍扫描 $O(n)$ 方案满分，两遍扫描方案最多得 2/3 分（2009年明确如此）	历年大题
18	置换-选择排序生成的归并段长度固定	平均长度 $2m$（$m$=工作区），最小 $m$（全逆序）、最大 $n$（全升序）	Ch8/2023

📝 后记：数据结构是408的基石和得分大户。掌握好数据结构不仅能在初试中拿到高分，更是今后从事计算机相关工作的核心基础。希望这份笔记能帮助你建立清晰的知识体系，在考研中充分发挥实力！

加油，未来的北大学子！💪