经典好文已翻新！Quick Tutorial of Data Structures and Algorithms New Edition！继承2312精神，深度修订，再创佳绩！本教程属于强化冲刺阶段专用复习教程，以原理剖析为主，大量使用叙述性的类C++伪代码或冗余编码，实际应用请参阅常用算法代码模板。

对比原版《数据结构强化笔记》，新版除了可利用HyPress平台随时在线阅读外，还存在如下主要变化：

修正大量错词错字（Typo）。
全面提升了表述规范性（定义、定理、总结等）和代码风格，力求无漏洞、易读、易懂。
追加全新章节——红黑树！其他各章亦有诸多扩充。
调整、简化了章节划分，部分“基础概念”“总结”性小节现已划至一级标题直属内容。
优化重点内容标注：全面取消“下划线”高亮，调整了部分“荧光笔”“加粗”“斜体”高亮，提升视觉体验。
暂不含原版中各章“编程练习”和OneNote版独占代码示例。

Hyplus目录

1 绪论

在开始前请先阅读附录B“C语言强化补充”

1.1 数据结构基础

数据结构的基本概念：

数据（Data）：一切可被计算机识别并加工处理的对象，如整型、实型、布尔型、图像、字符、声音等
数据元素：由数据组成的具有一定意义的基本单位
- 数据项：组成数据元素的不可分割的最小单位
数据对象：性质相同的数据类型的集合，是数据的一个子集
数据结构（Data Structure）：由某一数据对象及该对象中所有元素之间的关系组成
数据类型：性质相同的值的集合以及定义在该值集上的运算的集合（本文用ElemType表示数据结构中元素的预定义类型）
- 原子类型：不可再分
- 结构类型：可再分为若干份数据类型
抽象数据类型（Abstract Data Type，ADT）：一个数学模型以及定义在其上的运算的集合，可用 $(D,S,P)$ 三元组表示，其中 $D$ 是数据对象， $S$ 是 $D$ 上的关系集， $P$ 是对 $D$ 的基本操作集。ADT定义模板如下所示

ADT DataType {
    数据对象: <数据对象的定义>   // 伪代码实现
    数据关系: <数据关系的定义>   // 伪代码实现
    基本操作: <基本操作的定义>
    /* 基本操作定义格式：
        1. 基本操作名（参数表：赋值参数只为操作提供输⼊值；指针、引⽤参数分别以`*`、`&`开头）
        2. 初始条件（初始条件描述）
        3. 操作结果（操作结果描述）  */
} ADT DataType

数据结构三要素：

逻辑结构：从逻辑上描述数据，与数据的存储⽆关；数据元素 + 关系
- 线性结构：数据元素之间存在⼀对⼀的关系(1:1)
  1. 线性表：具有相同数据类型的 $n\ (n>0)$ 个数据元素的有限序列
  2. 特殊线性表
    1. 栈：只能在⼀端进⾏插⼊删除，具有先进后出（FILO）的特性
    2. 队列：只能在⼀端进⾏插⼊、在另⼀端进⾏删除，具有先进先出（FIFO）的特性
    3. 字符串：元素为字符的线性表
  3. 扩展线性表结构
    1. 数组、矩阵：通常规定数组下标从 $\text{0}$ 开始，矩阵下标从 $\text{1}$ 开始
    2. ⼴义表：数据元素可以是原⼦，也可以是⼴义表
- 非线性结构
  1. 集合结构：数据元素除了同属于⼀个集合外，没有其他的关系
  2. 树形结构：数据元素之间存在⼀对多的关系(1:n)
    - 根据树的特点，分为⼀般树与 $m$ 叉树（其中二叉树最为常用）
  3. 图结构（⽹状结构）：数据元素之间存在多对多的关系(m:n)
    - 根据边是否为双向（即为弧），分为有向图与⽆向图
存储结构（物理结构）：逻辑结构在计算机内的映像
1. 顺序存储结构：将逻辑上相关的数据元素依次存储在地址连续的存储空间中，需要占⽤连续的存储空间
  - 优点：可以实现随机存取；每个元素占⽤最少的存储空间
  - 缺点：只能使⽤相邻的⼀⽚存储空间，可能产⽣较多的外部碎⽚
2. 链式存储结构：数据元素可以存储在连续或不连续的存储空间中，⽤指针相连，⽆需占⽤连续的存储空间
  - 优点：能充分利⽤所有存储单元，不会出现碎⽚现象
  - 缺点：指针占⽤额外的存储空间；且不⽀持随机存取，只能顺序存取
3. 索引存储结构：分别存放数据元素和元素间关系，建⽴附加的索引表来标识结点的地址
  - 优点：检索速度快（分块查找）
  - 缺点：附加的索引额外占⽤存储空间，增、删操作也需修改索引表，时间开销较⼤
4. 散列存储结构（哈希存储）：在数据元素的关键字与存储位置之间建⽴散列表，利⽤散列函数，计算记录的散列地址
  - 优点：增、删、查操作都很快
  - 缺点：散列函数不佳时容易产⽣冲突，⽽解决冲突会增加时间与空间开销
数据的运算
- 定义——逻辑结构：运算功能
- 实现——存储结构：运算的操作步骤
- 按功能分类（增删改查，CRUD）
  1. 查找运算：在数据结构中搜索满⾜⼀定条件的元素
  2. 插⼊运算：在数据结构中插⼊新元素
  3. 删除运算：在数据结构中删除指定元素
  4. 更新运算：在数据结构中将指定元素更新为新的元素
- 按效果分类
  1. 加⼯型运算：改变原数据结构
  2. 引⽤型运算：不改变原数据结构

【总结与归纳】逻辑结构与存储结构的概念

分清逻辑结构与存储结构

有序表——只表示逻辑结构，意味数据元素有序的线性表

顺序表、哈希表、单链表——既表示存储结构⼜表示逻辑结构，且逻辑结构独⽴于存储结构

单独说栈、队列、树、图等——都只表示逻辑结构，但循环队列包括了存储结构

对于两种不同的数据结构，逻辑结构或存储结构可能相同

1.2 算法与算法分析

算法（Algorithm）：对特定问题的求解步骤的一种描述，是指令的有限序列。算法可以用自然语言、流程图、程序设计语言或伪代码描述。当一个算法用程序设计语言描述时，便成为程序。

算法的五个特征（所有算法都满⾜）：

输入：算法有0个或多个输入
输出：算法至少产生一个输出
可行性：算法的每一条指令都足够基本，可以实现
确定性：算法的每一条指令都必须有确切的定义，没有二义性
有穷性：算法必须总能在执行有限步之后终止

算法与程序的最显著区别：算法必须是有穷的，但程序不⼀定满⾜有穷性

算法的设计要求（优质算法特性）：

正确性：算法执⾏结果应当满⾜预先规定的功能和性能要求
可读性：⼀个算法应当思路清晰，层次分明，易于阅读、理解，便于分析
健壮性：当输⼊⾮法数据时，应当能做适当处理，不⾄于产⽣莫名其妙的结果
通⽤性：算法应具有⼀般性，即算法的处理结果对于⼀般的数据集合都成⽴
⾼效性：执⾏效率⾼（时间⾼效），占⽤存储空间少（空间⾼效）

正确性的4个层次：

程序不含语法错误

程序对于⼏组输⼊数据能够得出满⾜规格说明要求的结果

程序对于典型、苛刻、带有刁难性的输⼊数据能够得出满⾜规格说明要求的结果【衡量程序合格的标准】

程序对于⼀切合法的输⼊数据都能够得出满⾜规格说明要求的结果

效率的度量：衡量算法效率的⽅法

事前分析估算——根据算法的规模和复杂度分析，与算法本身有关
事后计算⽅法——与算法运⾏时的硬件有关，不易发现算法本身的优劣，同⼀算法，编译器不同运⾏时间也不同

算法复杂度分析：

时间复杂度T(n)：程序运⾏从开始到结束所需的时间。算法中语句的执⾏次数称为语句频度，常作为计算时间复杂度的依据。可分为最好（T_{\text{best}}）、最坏（T_{\text{worst}}）、平均（T_{\text{avg}}）时间复杂度
- 渐近时间复杂度：若T(n)=a_m n^m + a_{m-1} n^{m-1} + \cdots +a_1n+a_0为m次多项式，则T(n)=O(n^m)
  - $O(\cdot)$ 表示上界， $\Omega(\cdot)$ 表示下界， $\Theta(\cdot)$ 表示紧界。为表述方便，本文一律使用大O表示法。
- 比较： $O(1) \lt O(\log n) \lt O(n) \lt O(n \log n) \lt O(n^2) \lt O(n^3) \lt O(2^n) \lt O(n!) \lt O(n^n)$
- 计算⽅法：
  1. 直接计算法：列出变量变化序列，找出跳出循环的条件（最后⼀项），反解，再取⼤O即可（多层循环直接相乘）
  2. 变形法：不等式放缩 + 两边取大O（应舍弃所有次量级项和系数）。【例】 $m+n ≤ 2\max(m,n) \Rightarrow O(m+n)=O(\max(m,n))$
空间复杂度S(n)：程序运⾏从开始到结束所需的存储量，⼀般按最坏情况来分析
- 组成：
  1. 固定部分：主要包括程序代码、常量、简单变量、定⻓成分的结构变量所占的空间。【例】const int N = 100;、ElemType data[MAXSIZE];
  2. 可变部分：该部分空间⼤⼩与算法在某次执⾏中处理的特定数据的⼤⼩和规模有关。【例】for、while循环
- 原地⼯作：所需空间为常量，即 $S(n)=O(1)$ ，并非指不占⽤空间！

【例】（408真题改）将⻓度分别为 $m,n$ 的升序链表合并成长度为 $m+n$ 的降序链表，计算最坏、最好时间复杂度（变形至最简）

【解】最坏和最好时间复杂度均为 $O(\max(m,n))$ ！

最坏情况即两条链表均各遍历了⼀遍，交替头插⾄新链表， $m+n≤2\max(m,n)$ ，两边取大O即有 $O(m+n)=O(2\max(m,n))=O(\max(m,n))$

最好情况即全程只遍历其中⼀条链表，然⽽另⼀条最终仍需顺次头插⾄新链表，故复杂度仍为 $O(m+n)=O(\max(m,n))$ 与最坏一样！

2 线性表

线性表（Linear List）：具有相同类型的 $n\ (n≥0)$ 个数据元素的有限序列。当 $n=0$ 时，称为空表。第一个元素为表头，最后一个为表尾。除表头外元素都有一个直接前驱，除表尾外元素都有一个直接后继。

特点：

表中元素数量有限。
元素具有顺序性，表中元素具有先后次序。
表中元素数据类型相同，每个元素占用相同相同大小的空间。

抽象数据类型定义：

ADT List {
    数据对象：a_i
    数据关系：(a_{i-1}, a_i)
    基本操作：
        initList(&L)    // 构造⼀个空的表L
        clearList(&L)   // 将表L置为空表
        isEmpty(L)  // 判空操作
        getLength(L)    // 返回L中数据元素个数（表⻓）
        getElem(L, i, &e)   // 按位查找，⽤e返回表L中第i个数据元素的值
        locateElem(L, e)    // 按值查找，返回表L中第⼀个与e相同元素在表L中的位置
        insertElem(&L, i, e)    // 插⼊操作，在表L中第i个位置之前插⼊新数据元素e
        deleteElem(&L, i)   // 删除操作，删除表L中第i个数据元素
        printList(L)    // 遍历并打印表L中的每个数据元素
        destroyList(&L) // 销毁操作
} ADT List

2.1 顺序表

顺序表（Sequence List）：一种顺序存储结构，用一组连续地址的存储单元依次存储线性表中的元素，使逻辑上相邻的数据在物理位置上也相邻。

地址计算：已知第⼀个数据元素的起始地址为 $\text{LOC}(A)$ ，则

第 $i$ 个元素的起始地址： $\text{LOC}(A) + (i-1)\times \text{sizeof}(\text{ElemType})$
可存储的最后一个元素的起始地址： $\text{LOC}(A) + (\text{MAXSIZE}-1)\times \text{sizeof}(\text{ElemType})$

特点：

优点：
1. 既能顺序存取⼜能随机存取（随机访问），即通过⾸地址和元素序号可用 $O(1)$ 的时间复杂度按位查找元素
2. 存储密度⾼（元素连续分布，故存储密度等于1），对于单个元素空间利⽤率⾼
缺点：插⼊和删除需要移动⼤量元素，故对于需要反复插删的情形不适合⽤顺序表

2.1.1 顺序表的存储结构

静态分配存储：直接使⽤数组，容量事先固定，后期⽆法更改。有溢出的⻛险，当元素数量超出容量MAXSIZE时发生溢出

#define MAXSIZE 110 // 顺序表的最大容量

typedef struct SqList {
    ElemType data[MAXSIZE];
    int length;
} SqList;

动态分配存储：利⽤指针，C语⾔中由函数malloc()分配⼀块连续存储空间作为当前容量，⽆需⼀次性分配⼤量空间，也⽆需担⼼发⽣溢出，空间占满后可进行重分配操作，重新分配⼀块更⼤的空间

typedef struct SqList {
    ElemType *data;
    int length;
    int maxsize;    // 顺序表的当前最大容量
}

/* 重分配顺序表容量为n（n >= 当前表⻓） */
bool resize(SqList &L, int n) {
    if (n < L.length) return false;

    ElemType *temp = (ElemType*) malloc(n * sizeof ElemType)
    if (!temp) return false;

    for (int i = 0; i < L.length; i++)
        temp[i] = L.data[i];

    free(L.data);
    L.data = temp;
    L.maxsize = n;
    return true;
}

2.1.2 操作性能分析

设顺序表的长度为 $n$ ，数据从下标 $\text{0}$ 位置开始存储：

按位查找：顺序表支持随机存取，故 $T(n)=O(1)$
按值查找：有效查找范围为[0,n-1]（共n个合法查找位置）
- 最好情况：查找元素在表头，仅需比较 $\text{1}$ 次， $T_{\text{best}}(n)=O(1)$
- 最坏情况：查找元素在表尾或不存在（查找失败），需比较 $n$ 次， $T_{\text{worst}}(n)=O(n)$
- 平均情况：在第 $i \in [0,n-1]$ 个位置上查找的概率 $p_i=\frac{1}{n}$ ，则共需比较 $\frac{(n+1)n}{2}$ 次，故平均查找长度 $\text{ASL}=\frac{n+1}{2}$ ， $T_{\text{avg}}(n)=O(n)$
- 若顺序表有序，则还可使用折半查找， $T(n)=O(\log_2 n)$
插入：有效插入范围为[0,n]（不溢出；包括表尾之后的位置，共 $n+1$ 个合法插入位置）
- 最好情况：在表尾之后插入，无需后移元素， $T_{\text{best}}(n)=O(1)$
- 最坏情况：在表头插入，所有元素均需后移 $\text{1}$ 位（共后移 $n$ 次）， $T_{\text{worst}}(n)=O(n)$
- 平均情况：在第 $i$ 个位置上插入的概率 $p_i=\frac1{n+1}$ ，从表头到表尾之后，各情况分别需后移 $n,n-1,\cdots,1,0$ 次，则共需比较 $\frac{n(n+1)}{2}$ 次，故平均后移次数为 $\frac{n}2$ ， $T_{\text{avg}}(n)=O(n)$
删除：有效删除范围为[0,n-1]（共n个合法删除位置）
- 最好情况：删除表尾元素，无需后移元素， $T_{\text{best}}(n)=O(1)$
- 最坏情况：删除表头元素，除表头外均需后移 $\text{1}$ 位（共后移 $n-1$ 次）， $T_{\text{worst}}(n)=O(n)$
- 平均情况：删除第第 $i$ 个位置上插入的概率 $p_i=\frac1{n}$ ，从表头到表尾，各情况分别需后移 $n-1,n-2,\cdots,1$ 次，则共需比较 $\frac{n(n-1)}{2}$ 次，故平均后移次数为 $\frac{n-1}{2}$ ， $T_{\text{avg}}(n)=O(n)$

由此可⻅，顺序表在最后进⾏插⼊删除操作效率依旧很⾼，与链表持平

2.2 单链表

单链表（Single Linked List）：由⼀组任意的存储结点存储元素，每个结点还存储指向后继结点的指针，因此相⽐顺序存储结构能更⽅便地表示各种逻辑结构

特点：

优点：
1. 与顺序表完全相反，进⾏插⼊和删除运算操作⽆需移动元素，只需改变指针， $T(n)=O(1)$
2. ⽆需提前分配⼤量连续空间，故当难以估计线性表的⻓度或存储规模时，宜采⽤链表
缺点：
1. 不⽀持随机访问，只能进⾏顺序存取
2. 存储密度低（存储密度⼩于1），且额外消耗空间存放指针

注：链表结点内存储单元地址⼀定连续，相邻结点存储空间不⼀定连续

2.2.1 单链表的存储结构

单链表的结构体如下所示：

typedef struct LNode {
    ElemType data;
    struct LNode *next; // 后继指针
} LNode, *LinkList;

特殊结构单元：

头结点：在第⼀个元素结点（开始结点）前附加的结点，使头指针指向它。可不记录信息（或记录表⻓），指针域指向开始结点
头指针：指向链表第⼀个结点的指针，通常⽤它来指代整个链表。当有头结点时指向头结点，⽆头结点时指向开始结点

根据有无头结点，单链表可分为两类：

带头链表：表空状态为L->next == NULL

无头链表：表空状态为L == NULL

2.2.2 链表基本操作

插⼊结点：将结点s插⼊单链表中结点p之后（或⽆头链表在表头插⼊）

插入节点时需保证不断链，故将更改p的后继指针（或无头的头指针）操作放到最后

对于带头链表，在表头或表中插入操作一致：

/* 将结点s插⼊带头单链表L中结点p之后（p可为头结点L） */
s->next = p->next;
p->next = s;

对于⽆头链表，需特判在表头插⼊的情况：

/* 1° 将结点s插⼊⽆头单链表L的表头 */
s->next = L;
L = s;
/* 2˚ 将结点s插⼊⽆头单链表L中结点p之后（同带头情况） */
s->next = p->next;
p->next = s;

删除结点：删除结点p的后继结点（或⽆头链表删除表头）

让⼀个指针指向待删结点，p的后继指针（或⽆头的头指针）指向待删结点的后继即可
注意！最后使⽤函数free()释放结点空间（C++中为delete关键字）

对于带头链表，在表头或表中删除操作⼀致：

/* 删除带头链表L中结点p的后继结点 */
q = p->next;
p->next = q->next;
free(q);

对于⽆头链表，需特判在表头删除的情况：

/* 1˚ 删除⽆头链表L的表头结点 */
p = L;
L = p->next;
/* 2˚ 删除⽆头链表L中结点p的后继结点（同带头情况） */
q = p->next;
p->next = q->next;
free(q);

建⽴链表：根据元素的存放顺序，存在两种建表方法，都极为重要

尾插法：元素存放顺序与输⼊顺序相同。需要⼀个总是指向表尾的尾指针r辅助

建⽴带头链表，操作全程统⼀：

LNode *r = L->next;
/* 尾插建⽴带头链表【局部操作】 */
s->next = r->next;
r = s;
/* 建表结束后将尾结点r的后继指针置空 */
r->next = NULL;

建⽴⽆头链表，需特判初次插⼊空表的情况：

LNode *r = NULL;
/* 尾插建⽴⽆头链表【局部操作】 */
if (!L) s->next = NULL;
else s->next = r->next;
r = s;
/* 将尾结点r的后继指针置空（此前已置空，故可不写这句） */
r->next = NULL;

头插法：元素存放顺序与输⼊顺序相反。始终在表头执⾏添加元素，故⽆需额外指针辅助。
- 建立带头链表：
```
s->next = L->next;
L->next = s;
```
- 建立无头链表：
```
s->next = L;
L = s;
```

2.2.3 操作性能分析

按位插⼊/删除结点：仅需修改指针即可，T(n)=O(1)
- 顺序表在表尾插⼊的时间复杂度同样为 $O(1)$
建⽴链表：相当于对⼀个空链表执⾏n次插⼊操作，T(n)=O(n)
- 建⽴有序单链表的时间复杂度为 $O(n^2)$
按位或按值查找结点：遍历单链表的操作与顺序表类似（实质都是顺序查找）， $T_{\text{avg}}(n)=O(n)$
按值、按给定序号插⼊/删除结点：插⼊/删除操作本身时间消耗仅为 $O(1)$ ，但每次操作需从头遍历查找结点，故 $T(n)=O(n)$

【例】给定有 $n$ 个元素的⼀维数组，建⽴⼀个有序单链表的最低时间复杂度是？

【解】 $O(n \log_2 n)$ 。将数组排序的最好时间复杂度为 $O(n \log_2 n)$ ，建⽴链表的时间复杂度为 $O(n)$ ，抓⼤头得总的时间复杂度为 $O(n \log_2 n)$ 。

2.3 其他链表结构

双链表为重点，其他了解为主。

2.3.1 双链表

双链表（Double Linked List）在单链表的基础上额外增加了⼀个指向前驱结点的指针域，因⽽实现了双⽅向遍历整个表。其他各种操作都类似单链表。

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

操作（以带头双链表为例，⽆头双链表与此类似）：

插⼊结点：将结点s插⼊双链表中结点p之后

类似单链表的插⼊操作，注意被插结点的后继指针p->next必须在待插结点s已完成双向链接p的后继结点后才能修改，否则会断链

/* 将结点s插⼊双链表中结点p之后 */
s->next = p->next;    // 1
p->next->prior = s;   // 2
p->next = s;     // 3（该操作3必须放在操作1、2后进⾏，与操作4可互换，否则会发⽣断链）
s->prior = p;        // 4

删除结点：删除结点p的后继结点
- 指针q指向该待删除结点（p的后继），让p的后继指针指向q的后继，q的后继结点的前驱指针q->next->prior指向p，最后释放结点空间
```
/* 删除双链表中结点p的后继结点 */
q = p->next;
q->next->prior = p;
p->next = q->next;
free(q);
```

2.3.2 循环链表

循环单链表（Circular Single Linked List）：在单链表的基础上，规定表尾的后继指针指向第⼀个结点（有头结点时指向头结点，⽆头结点时指向第⼀个元素结点）

循环双链表（Circular Double Linked List）：在双链表的基础上，规定表尾的后继指针指向第⼀个结点（同循环单链表），第⼀个结点的前驱指针指向表尾

常见考点：

当head->next->next == head时，循环单链表的长度为 $1$ 或 $2$ （假设表非空）

带头情况：有 $1$ 个元素结点，故⻓度为 $1$ （长度不计入头结点）

⽆头情况：有 $2$ 个元素结点，故⻓度为 $2$ （画图即可知）

循环单链表中设置尾指针⽐设置头指针好吗？
【解】循环单链表中设置尾指针要优于头指针，更⽅便查找链表的开始结点和终端结点，时间复杂度都为 $O(1)$ ；⽽头指针查找终端结点则需遍历整个表，时间复杂度为 $O(n)$

循环双链表中设置尾指针与设置头指针⼀样好吗？
【解】循环双链表中⽆论设置尾指针还是头指针，查找开始结点和终端结点都⼗分⽅便，时间复杂度都为 $O(1)$

2.3.3 静态链表

静态链表（Static Linked List）借助数组来表述线性表的链式存储，和顺序表⼀样，需预先分配⼀⽚连续的存储空间。和通常的动态链表⼀样，（逻辑上）不⽀持随机存储。插⼊/删除操作只需修改指针域（即数组下标，称为游标），⽆需移动元素

#define MAXSIZE 110

struct StaticList {
    ElemType data;
    int next;   // 存储后继结点的数组下标
} L[MAXSIZE];

受益于数组本身的随机存取特性，在算法题中常用于模拟各类容器，详见常用算法代码模板。

3 栈与队列

关于栈与队列在树、图中的应用详见各自篇章

3.1 栈

栈（Stack）：只允许在⼀端进⾏插⼊/删除操作的输⼊输出受限的线性表。允许进⾏插⼊/删除的⼀端称为栈顶（Top），不允许进⾏操作的⼀端称为栈底（Bottom）。不含任何元素的栈称为空栈。

栈的特性 ——先进后出（First In Last Out, FILO），因此栈具有记忆功能

ADT Stack {
    数据对象: a_i
    数据关系: <a_{i-1}, a_i>, 只允许在⼀端增加、减少
    基本操作:
        initStack(&S)   // 初始化⼀个空栈S
        isEmpty(S)  // 判空操作，判断⼀个栈是否为空
        push(&S, x) // 压栈操作，若栈未满，则将元素x押⼊栈中
        pop(&S, &x) // 出栈操作，若栈⾮空，则弹出栈顶元素并⽤x接收
        getTop(&S, &x)  // 读取栈顶元素，若栈⾮空，⽤x返回栈顶元素
        destroyStack(&S)    // 销毁操作
} ADT Stack

3.1.1 栈的存储结构

分为顺序栈和链栈，其中顺序栈还包含一种重要衍生扩展结构——共享栈。

3.1.1.1 顺序栈

顺序栈（Sequential Stack）：栈最常见的一种存储结构之一，利⽤⼀组连续地址的存储单元⾃栈底⾄栈顶存储元素，并使⽤栈顶指针top指示当前栈顶元素的位置。正常配置下，初始化top = -1。

#define MAXSIZE 110

typedef struct SqStack {
    ElemType data[MAXSIZE];
    int top;    // 栈顶指针，通常配置下初值为-1
} SqStack;

状态表示（正常配置）：

栈空/初始化状态：S.top == -1
栈满状态：S.top == MAXSIZE - 1
栈长：S.top + 1

基本操作（正常配置）：

压栈：S.data[++S.top] = x;
出栈：x = S.data[S.top--];
读取栈顶元素：x = S.data[S.top];

变式：当栈顶指针top初始化为0或MAXSIZE时，可由上推算出各种状态表示与基本操作

3.1.1.2 共享栈

共享栈（Shared Stack）：栈的⼀种特殊的顺序存储结构。利⽤栈底位置相对不变的特性，让两个顺序栈共享⼀个⼀维数组空间，两栈栈底分别位于数组两端，并分别设置1号栈、2号栈的栈顶指针top1、top2，相向而行。正常配置下，初始化top1 = -1、top2 = MAXSIZE。

优点：节省存储空间，减少引起上溢的可能（对于下溢则不变）

typedef struct SharedStack {
    ElemType data[MAXSIZE];
    int top1, top2; // top1、top2分别为1、2号栈的栈顶指针。亦可⽤数组top[2]实现
} SharedStack;

状态表示（正常配置）：

1号栈空/初始化状态：S.top1 == -1
1号栈长：S.top1 + 1
2号栈空/初始化状态：S.top2 == MAXSIZE
2号栈长：MAXSIZE - S.top2
共享栈满状态：S.top1 + 1 == S.top2

3.1.1.3 链栈

链栈（Linked Stack）：栈的⼀种链式存储结构。采⽤带有头指针的单链表实现。规定所有操作都在链表的表头进⾏，头指针即为栈顶指针。实际相当于只允许头插、头删的单链表。

优点：便于多个栈共享存储空间；提⾼其操作效率；且不存在栈满⾃溢的情况。

typedef struct StackNode {
    ElemType data;
    struct StackNode *next;
} StackNode, *LinkStack;

3.1.2 栈的性质

栈的实用性质：

出栈元素排列数： $n$ 个不同元素进栈，出栈元素不同排列的个数为卡特兰数：

 $\text{Catalan}(n)=\frac{\text{C}^{n}_{2n}}{n+1}$

由出栈序列判断容量相关问题：画图动态模拟即可，注意题设中可能的限制条件（如连续⼊栈/出栈次数上限等）
由升序⼊栈序列判断出栈元素相关问题：已知⼊栈序列为1,2,\cdots,n，出栈序列为p_1,p_2,\cdots,p_n，则
1. 题型1——最后进栈的元素 $n$ 最先出栈：若 $p_1=n$ ，则 $p_i=n-i+1$
  
  【证】最后进栈的元素最先出栈 $\Rightarrow$ 在其之前无人出栈 $\therefore p_2=n-1,p_3=n-2,\cdots,p_i=n-i+1$
2. 题型2——推算最后进栈的元素 $n$ 出栈后其与之后出栈元素⼤⼩关系：若 $p_i=n\ (1\lt i \lt n)$ ，则 $p_i,p_{i+1},\cdots,p_n$ 的大小关系为 $p_i\gt p_{i+1} \gt \cdots \gt p_n$ ，即最后进栈元素出栈后出栈降序
  
  【证】由题知，⼊栈升序，且 $n$ 进栈后不可能出现进栈操作。⼜根据上⼀题的结论可得， $n$ 出栈后元素出栈降序。

口诀：若1、2、3，则无3、1、2！

实际解题时强烈推荐多⽤特值法（其他数值计算题同理）

3.1.3 栈的应⽤

在DFS中的实际应用见后述。

根据运算方向，表达式可分为3种类型：前缀（Prefix）、中缀（Infix）、后缀（Postfix）

所使用的辅助栈包括操作数（Operand）栈、运算符（Operator）栈、结果栈

3.1.3.1 表达式的转换

根据实际情况，通常使用两种转换方法：

⼿⼯求解法（括号法）：对中缀式中所有⼦表达式按运算优先级添加括号，从⾥到外将所有运算符提到对应的括号前/后，即将中缀式转化成前/后缀式，最后去除所有括号即可。
堆栈求解法：使⽤辅助运算符栈和结果栈

中缀转后缀（逆波兰式）：从左⾄右遍历中缀表达式串

遇到操作数：直接输出
遇到左括号：直接⼊栈
遇到运算符
1. 栈空、栈顶为左括号：直接⼊栈
2. 栈顶为运算符：【⽐较】当前运算符与栈顶运算符的优先级——当前运算符的优先级更⼤则⼊栈，否则弹出并输出栈顶运算符，并继续【⽐较】下⼀个栈顶运算符，指针i不后移
  - 原理：⾼优先级的先算（输出）
遇到右括号：顺序弹出并输出栈顶运算符直⾄栈顶为左括号，然后弹出栈顶左括号
遍历结束后，运算符栈顺序弹出并输出剩余栈顶运算符；将结果栈中元素顺序弹出即为后缀式

/* 返回运算符的优先级：运算优先级越⾼，返回值越⼤ */
int getPriority(char op) {
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
    return -1;
}

/* 中缀式转后缀式 */
void infixToPostfix(char infix[], Stack &res) {
    Stack S;    // 操作符栈
    initStack(S);
    for (int i = 0; infix[i] != '\0';) {
        if ('0' <= infix[i] && infix[i] <= '9') {
            res.data[++res.top] = infix[i];
        } else if (infix[i] == '(') {
            S.data[++S.top] = '(';
        } else if (infix[i] == ')') {
            while (S.data[S.top] != '(') {
                res.data[++res.top] = S.data[S.top--];
            }
            S.top--;
        } else if (infix[i] == '+' || infix[i] == '-' || infix[i] == '*' || infix[i] == '/') {
            if (S.top == -1 || S.data[S.top] == '(' || getPriority(infix[i]) > getPriority(S.data[S.top])) {
                S.data[++S.top] = infix[i];
            } else {
                res.data[++res.top] = S.data[S.top--];
                continue;   // 指针不后移
            }
        }
        i++;
    }
    while (S.top != -1) {
        res.data[++res.top] = S.data[S.top--];
    }
}

中缀转前缀（波兰式）：操作与中缀转后缀极为相似，但存在以下⼏点重要区别

从右⾄左遍历中缀表达式串，故需知道串的⻓度
左、右括号效果互换
【⽐较】条件修改：当前运算符的优先级⼤于等于栈顶运算符
- 原理：当前 > 栈顶轮换变量得栈顶 > 当前取反得栈顶 <= 当前即当前 >= 栈顶
将结果栈中元素顺序弹出并进⾏逆序后才成为前缀式

【代码实现待更新】

3.1.3.2 表达式的计算

计算中缀表达式——使用使⽤辅助操作数栈与运算符栈：从左⾄右遍历中缀表达式串（操作及原理均与中缀转后缀极为相似）

遇到操作数：直接⼊操作数栈
遇到左括号：直接⼊运算符栈
遇到运算符
1. （运算符栈）栈空、栈顶为左括号：直接⼊栈
2. 栈顶为运算符：【⽐较】当前运算符与栈顶运算符的优先级——当前运算符的优先级更⼤则⼊栈，否则弹出栈顶运算符并进行【运算】：
  1. 计算⼦表达式：弹出两个（操作数栈）栈顶操作数，与操作符组合：先出的数在右、后出的数在左、运算符在中间
  2. 做完运算后的结果押回操作数栈，并让当前运算符继续【⽐较】下⼀个运算符栈顶运算符，指针i不后移
遇到右括号：顺序弹出栈顶运算符并分别执行一次上述【运算】直⾄栈顶为左括号，然后弹出栈顶左括号
遍历结束后，运算符栈顺序弹出剩余栈顶运算符并分别执行一次上述【运算】；最后操作数栈所剩的那个数即为结果

【代码实现待更新】

计算后缀表达式——只需使⽤操作数栈：从左⾄右遍历后缀表达式（极为简单）

遇到操作数：⼊栈
遇到运算符：执⾏同中缀计算所述两步【运算】；运算结果押回栈，继续遍历
遍历结束之时即运算结束之时

/* ⼦表达式求值：通过res传回结果，函数返回值表示计算成功与否 */
bool calSub(float x, char op, float y, float *res);

/* 计算后缀表达式 */
float calPostfix(char exp[]) {
    Stack S;    // 操作数栈
    initStack(S);
    for (int i = 0; exp[i] != '\0'; i++) {
        if ('0' <= exp[i] && exp[i] <= '9') {
            S.data[++S.top] = (float) (exp[i] - '0');
        } else {
            float x, y, res;
            y = S.data[S.top--];
            x = S.data[S.top--];
            bool flag = calSub(x, exp[i], y, &res); // 子表达式求值
            if (!flag) {
                puts("ERROR");
                return ERROR;
            } else {
                S.data[++S.top] = res;
            }
        }
    }
    return S.data[S.top];
}

计算前缀表达式：操作与计算后缀表达式极为相似，只存在以下两点细微区别

从右⾄左遍历前缀表达式串，故需知道串的⻓度
微调【运算】操作：先出的数在左、后出的数在右

【代码实现待更新】

3.1.3.3 括号匹配

括号表达式的合法性判定：每⼀摞括号（某⼀对左右括号及其之间的括号）必须严格对称；⼩括号可套在⼤括号外。【例】 $\{[]\}[()](\{[]\})$ 是合法的，而 $()[(])\}$ 、 $[)\{](\}$ 是不合法的。

括号匹配⽅法——利⽤左括号栈：遍历括号表达式

遇到左括号：⼊栈
遇到右括号：与栈顶左括号做配对⽐较——配对则弹出栈顶左括号并继续遍历，不配对则⽴刻结束遍历并返回false
遍历结束时若栈⾮空则匹配失败，否则匹配成功

/* 检查括号匹配 */
bool checkBrackets(char a[]) {
    Stack S;    // 左括号栈
    initStack(S);
    char match[128] = {0};
    match[')'] = '(', match[']'] = '[', match['}'] = '{';
    for (int i = 0; a[i] != '\0'; i++) {
        switch (a[i]) {
            case '(':
            case '[':
            case '{':
                S.data[++S.top] = a[i];
                break;
            case ')':
            case ']':
            case '}':
                if (isEmpty(S)) return false;
                if (S.data[S.top--] != match[a[i]]) return false;
                break;
        }
    }
    if (isEmpty(S)) return true;
    return false;
}

3.1.3.4 递归

递归（Recursion）：若某函数、过程或数据结构在其定义中调⽤了其⾃身，则称其为递归定义的。递归需要调⽤系统⼯作栈。

所有的递归都满⾜两部分：递归表达式（递归体）、递归出⼝（递归边界）

递归的特点：

优点：将复杂问题分解为属性相同、操作重复的⼦问题，⼤幅减少思考需求与代码量
缺点：通常时空效率不⾼，且计算量过⼤时易造成栈溢出

递归的应⽤：

进制转换、迷宫求解、计算规律序列（如斐波那契数列）、DFS、DP
调⽤函数时，其局部变量⼀般采⽤栈结构进⾏存储

3.2 队列

队列（Queue，简称队）：只允许在一端进行插入、在另一端进行删除的输入输出受限的线性表。进行插入的一端称为队尾（Rear），插入操作称为入队（Enqueue）；进行删除的一端称为队首（Front），删除操作称为出队（Dequeue）。

队列的特性——先进先出（First In First Out，FIFO）

ADT Queue {
    数据对象: a_i
    数据关系: <a_{i-1}, a_i>, 只允许在⼀端增加，在另⼀端减少
    基本操作:
        initQueue(&Q)   // 初始化⼀个空队Q
        isEmpty(Q)  // 判空操作，判断⼀个队是否为空
        push(&Q, x) // ⼊队操作，若队未满，则让元素x⼊队
        pop(&Q, &x) // 出队操作，若队⾮空，则队⾸元素出队并⽤x接收
        getFront(&Q, &x)    // 读取队⾸元素，若队⾮空，⽤x返回队⾸元素
        getRear(&Q, &x) // 读取队尾元素，若队⾮空，⽤x返回队尾元素
        destroyQueue(&Q)    // 销毁操作
} ADT Queue

3.2.1 队列的存储结构

其中顺序队又分为非循环队列与循环队列。

本节中的所有队列均为正常配置。

3.2.1.1 顺序队

顺序队（Sequetial Queue）：队列的一种顺序存储结构，利用一组连续地址的存储单元自队首至队尾存储元素，用队首指针front、队尾指针rear指示队列的首尾位置。

#define MAXSIZE 110

typedef struct Queue {
    ElemType data[MAXSIZE];
    int front, rear;
} Queue;

非循环队列（正常配置）：

缺陷：指针无脑前进，易造成假溢出，浪费大量存储空间。
状态表示
- 初始化：Q.front = Q.rear = 0;——双指针同时指向0号位置
- 队空：Q.front == Q.rear——双指针同时指向同一位置
- 队满：无法明确判定
- 队长：Q.rear - Q.front
操作——先操作元素，再移动指针
- 入队：Q.data[Q.front++] = x;
- 出队：Q.data[Q.rear++] = x;

循环队列（正常配置）：

改进：定义在逻辑上的环状队列，移动指针时对数组容量取余，有效规避了假溢出的风险。
状态表示
- 初始化：Q.front = Q.rear = 0;——双指针同时指向0号位置（同非循环队列）
- 队满队空（三种方案）
  1. 牺牲一个单元来特判队满，队尾入队时少用一个单元（正常配置，最为常用）：
    - 队空：Q.front == Q.rear——双指针同时指向同一位置（同非循环队列）
    - 队满：(Q.rear + 1) % MAXSIZE == Q.front——队头位于队尾后第1个位置
  2. 结构体增设一个表示元素个数的数据成员Q.size：
    - 队空：Q.size == 0
    - 队满：Q.size == MAXSIZE
  3. 结构体增设一个区分队满与队空的标记成员Q.tag：
    - 每次执行删除时置为0，执行插入时置为1（无论当前状态如何）
    - Q.tag == 0时，因删除导致Q.front == Q.rear，则队空
    - Q.tag == 1时，因插入导致Q.front == Q.rear，则队满
- 队长：(Q.rear - Q.front + MAXSIZE) % MAXSIZE
操作——先操作元素，再移动指针
- 入队：Q.data[Q.rear] = x; Q.rear = (Q.rear + 1) % MAXSIZE;
- 出队：x = Q.data[Q.front]; Q.front = (Q.front + 1) % MAXSIZE;

3.2.1.2 链队

链队（Linked Queue）：队列的⼀种链式存储结构。采⽤同时带有头指针、尾指针的单链表实现。规定表头为允许进⾏删除操作的队⾸，表尾为允许进⾏插⼊操作的队尾。实际相当于只允许头删、尾插的单链表。

通常带有链队头结点，且封装了队⾸指针Q.front（所指结点通常不存储数据元素，参考链表⾥的头结点）、队尾指针Q.rear

typedef struct QueueNode {
    ElemType data;
    struct QueueNode *next;
} QueueNode;    // 队列元素结点

typedef struct QueueHead {
    QueueNode *front;   // 队⾸指针，操作上相当于单链表的头结点指针
    QueueNode *rear;    // 队尾指针
} LinkQueue;    // 链队头结点

状态表示（正常配置）：

队空/初始化状态：Q.front == Q.rear
队满：链表⽆表满状态

基本操作：

⼊队：相当于将新结点s尾插至链表尾的操作

/* 新结点s⼊队 */
s->next = Q.rear->next;
Q.rear->next = s;

出队：相当于带头链表删除表头元素的操作；当删除链队中最后⼀个元素时需同时修改头尾指针Q.rear = Q.front;，使得队被完全清空
```
/* 队⾸结点出队 */
p = Q.front->next;
Q.front->next = p->next;
if (p == Q.rear) Q.rear = Q.front;
free(p);
```

3.2.2 循环队列的配置问题

本文规定满⾜以下特征的配置为循环队列的正常配置：

队⾮空时双指针重合
牺牲⼀个空间表示队满
先操作元素、再移动指针

特点：front始终指向元素，rear始终指向空位

两种常见的⾮正常配置修改⽅式：

修改操作顺序——先移动指针、再操作元素
- 入队：Q.rear = (Q.rear + 1) % MAXSIZE; Q.data[Q.rear] = x;
- 出队：Q.front = (Q.front + 1) % MAXSIZE; x = Q.data[Q.front];

特点：front始终指向空位，rear始终指向元素，其余与正常配置完全一致

修改状态表示——队⾮空时双指针都指向元素
- 队空/初始化状态：(Q.rear + 1) % MAXSIZE == Q.front——队头位于队尾后第1个位置（恰好为正常配置的队满条件）
- 队满：(Q.rear + 2) % MAXSIZE == Q.front——队头位于队尾后第2个位置（比正常配置后移一位）
- 队长：(Q.rear - Q.front + 1 + MAXSIZE) % MAXSIZE

特点：初始状态双指针不重合

多画图，多体会。这些配置在本站各处皆有广泛应用。

3.2.3 队列的扩展与应用

队列的简单应⽤：BFS，拓扑排序；缓冲区、⻚⾯调度算法……

详见后述

3.2.3.1 双端队列

双端队列（Double-ended Queue，Deque）：两端都可进⾏元素的插⼊和删除操作的线性结构。对双端队列左右两端进⾏各种输⼊、输出限制，即输⼊受限、输出受限，可使其退化为线性表、栈、队列或其他特殊结构。

验证出队序列的合法性：

输出受限（仅⼀端可输出）：按输出序列填充队列，再模拟⼊队过程是否可⾏
`1. 先按输出序列根据出⼝⽅向在队列中填好元素
1. 遍历输⼊序列，模拟各元素⼊队情形，同时随时按输出序列让两端应出队元素出队，若⽆法从两端⼊队（有⼈想"插队"）则直接判⾮法

输⼊受限（仅⼀端可输⼊）：全体⼊队，根据输出逐⼀出队
1. 先直接按输⼊序列让所有元素从入口⼊队
2. 遍历输出队列中各元素，检查应出队元素是否出现在队列两端：是则出队并继续，否则直接判⾮法

输出受限的情形比输入受限要复杂、灵活得多，故请仔细体会。

3.2.3.2 ⽤栈模拟队列

使用两个并排放置的栈s1与s2模拟队列，操作与状态如下：

元素入队：
1. 若s1未满，则让该元素直接入s1
2. 若s1满、s2空，则将s1中全部元素逐一出栈进入s2，然后让该元素入s1
元素出队：
1. 若s2非空，则直接s2弹出栈顶元素
2. 若s2空，则将s1中元素全部出栈倒入s2，然后s2弹出栈顶元素
队满：s2满且s1非空，则不能继续入队

【代码实现待更新】

4 字符串

字符串（String，简称串)：由零个或多个字符（Character）组成的有限序列，实际相当于元素为特定类型（字符型）的线性表。串中字符的个数 $n$ 称为串长，串长 $n=0$ 的串称为空串（用 $\empty$ 表示）

4.1 串的存储结构

顺序存储：分为以下两种，常为⾼级程序设计语⾔所采⽤

定⻓存储结构：相当于线性表中顺序表的静态分配存储，C语言中在表示字符串的字符数组结尾通常有⼀个结束标记字符'\0'。使用scanf()读取字符串时，超过预定义串⻓MAXSIZE的串值会被舍去，称为截断。

# define MAXSIZE 1010
typedef struct String {
    char str[MAXSIZE + 1];  // 多定义一个空间，留给结束标记'\0'
    int length;
} String;

变⻓存储结构：相当于线性表中顺序表的动态分配存储，⼜称堆分配存储表示<，最为常用。C语言中使用malloc()和free()函数在自由存储区（堆）中动态管理串的存储，仍以连续地址存储。

typedef struct String {
    char *ch;
    int length;
} String;

块链存储结构：相当于线性表的链式存储结构，即链表。每个结点称为块，可设定最多存储⼀个或多个字符；整个链表称为块链结构。最后⼀个结点存储不满时通常⽤'#'补上。

【串的各种操作代码实现待更新】

4.2 模式匹配

在模式匹配算法中，所有串的字符数组均从下标1开始存储，注意与上⼀节区分。

可通过如下方式从下标1开始读取主串和模式串：

scanf("%s%s", S.ch + 1, P.ch + 1)

4.2.1 暴⼒匹配算法

暴⼒匹配算法（Brute Force，BF）：使⽤双指针逐⼀⽐较主串与模式串，同时记录主串上⼀次匹配的起始位置，发⽣不匹配则回溯。

性能： $T(m,n)=O(m \cdot n)$ ，其中 $m,n$ 分别为主串与子串的长度

/* 主串S与模式串P的暴⼒模式匹配 */
int index(String S, String P) {
    int i = 1, j = 1, pos = i;  // i、j分别作为主串和模式串的索引，pos记录⽐较的开始位置
    while (i <= S.length && j <= P.length) {
        if (S.ch[i] == P.ch[j]) {   // 遍历字符相同，则同时后移
            i++;
            j++;
        } else {    // 不同则主串索引i回溯，模式串索引j重置为1，更新pos
            i = pos + 1;
            j = 1;
            pos = i;
        }
    }
    if (j > P.length) return pos;    // 模式串遍历结束，模式匹配成功，返回模式串所在位置
    return 0;   // 模式匹配失败，返回0
}

4.2.2 KMP算法

详细定义略

性能： $T(m,n)=O(m+n)$

KMP算法提⾼模式匹配效率的⽅法：主串位置 $i$ ⽆需回退，即尽可能利⽤匹配失败的信息，尽量减少主串与模式串的匹配次数。

手工模式匹配步骤：

顺次匹配主串与模式串，当出现不匹配时往前找主串与模式串不匹配点之前真子串的最⼤公共前后缀
将模式串的串头从最⼤前缀处平移⾄最⼤后缀处，继续第1步操作
- 特别地，当公共前后缀为空时（缀⻓为0），串头直接移⾄不匹配点处
当模式串遍历结束则表示匹配成功，否则匹配失败

求解next数组：对着模式串 $P$ 操作

令 $\text{next}[1]=0$ ，易得 $\text{next}[2]=1$
当 $j>1$ 时， $\text{next}[j]=$ $P[j]$ 的最大公共前后缀长度 $+1$

虽然极为罕见，但早年统考题亦有过令串从下标0开始存储，此时应取 $\text{next}[0]=-1$ ，则当 $j>1$ 时 $\text{next}[j]$ 直接为最大公共前后缀长度

求解nextval数组：对着求得的next数组与模式串 $P$ 操作

令 $\text{nextval}[1]=0$ ，易得 $\text{nextval}[2]=1$
当j>1时，比较当前位置字符P[j]与其next值所指示的字符P[\text{next}[j]]
- 若两者相同，则直接与之相同，即 $\text{nextval}[j]=\text{nextval}[\text{next}[j]]$
- 若两者不同，则沿用自己的next值，即 $\text{nextval}[j]=\text{next}[j]$

口诀：相同则相同，不同则不同（沿用自己）！

代码实现【改进版待更新】：

/* 获取next数组 */
void getNext(String P, int next[]) {
    int i = 0, j = 0;   // i为主串后缀结束位置，j为模式串前缀结束位置（初值0）
    next[1] = 0;
    while (i < P.length) {
        if (j == 0 || P.ch[i] == P.ch[j]) { // 遍历字符相同或j回溯到头，则更新next数组
            i++;
            j++;
            next[i] = j;
        } else {    // 遍历字符不同，则j回溯
            j = next[j];
        }
    }
}

/* KMP算法 */
int KMP(String S, String P, int next[]) {
    int i = 1, j = 1;   // i、j分别为主串和模式串的索引
    while (i <= S.length && j <= P.length) {
        if (j == 0 || S.ch[i] == P.ch[j]) { // 遍历字符相同或j回溯到头，则同时后移
            i++;
            j++;
        } else {    // 遍历字符不同，则j回溯
            j = next[j];
        }
    }
    if (j > P.length) return i - P.length;   // 模式串遍历结束，模式匹配成功，返回模式串所在位置
    return 0;   // 模式匹配失败，返回0
}

【例】模式串ababcabc的next数组与nextval数组（串下标从1开始）：

下标 1 2 3 4 5 6 7 8

$P[j]$ a b a b c a b c

$\text{next}[j]$ 0 1 1 2 3 1 2 3

$\text{nextval}[j]$ 0 1 0 1 3 0 1 3

下标	1	2	3	4	5	6	7	8
$P[j]$	a	b	a	b	c	a	b	c
$\text{next}[j]$	0	1	1	2	3	1	2	3
$\text{nextval}[j]$	0	1	0	1	3	0	1	3

5 扩展线性表结构

数组、矩阵、广义表

5.1 数组

数组（Array）：线性表的推⼴，结构中的元素本身可以是具有某种结构的数据，但应属于同⼀数据类型。

⼆维数组（2D Array）：元素为⼀维数组的数组，但在内存中依旧连续存储。

数组的正常配置：从下标开始存储元素，即起始下标为 $\text{0}$ ，如A[0]、A[0][0]

写法：A[n]、A[n][m]分别等价于A[0...n-1]、A[0...n-1][0...m-1]；A[1...n]、A[1...n][1...m]表示指定从下标 $1$ 开始存储元素的非正常配置

元素存储地址计算：设 $L$ 为每个数组元素所占的存储单元大小

一维数组计算式： $\text{LOC}(a_i)=\text{LOC}(a_0)+i\times L$
二维数组存储/映射方式若二维数组A的行数为r、列数为c，则存储结构计算式为
- 行优先存储： $\text{LOC}(a_{i,j})=\text{LOC}(a_{0,0})+(i\times c + j)\times L$
- 列优先存储： $\text{LOC}(a_{i,j})=\text{LOC}(a_{0,0})+(i+j\times r) \times L$

【总结与归纳】巧算二维数组/矩阵元素地址：

“○”优先，则“另一个”乘向“○”的下标

对于从下标 $1$ 开始存元素的二维数组（即矩阵），改写成数组的正常配置再套公式，若要算“之前有多少元素”则⽆需修缮直接结果

5.2 矩阵

矩阵（Matrix）：⼆维数组的代数表示。

矩阵的正常配置：从下标 $1$ 开始存储元素，即起始坐标为 $a_{11}$

上述的数组元素地址计算式同样适⽤于矩阵（需先改写成数组的正常配置）

5.2.1 特殊矩阵的压缩存储

将矩阵通过某种⽅式⽤更少的空间存储称为矩阵的压缩存储，通常用⼀维数组B[0...MAXSIZE]或类似结构。思想：相同元素只存储⼀份。

对称矩阵：n阶方阵A_{n\times n}中，满足a_{ij}=a_{ji}
- 压缩存储方法：只将下三⻆（含对⻆线）的元素存⼊⼀维数组，所需存储空间为 $\frac{(1+n)n}{2}$
- 下三角部分：设a_{ij}在一维数组B[0...MAXSIZE]中对应的下标为k，则
```
 $k=\frac{i(i-1)}{2}+j-1$ 
```
  推导：对 $1,\cdots,i-1$ 求和，加上自身列标；数组从下标0开始存储故减1（若从下标1开始存储则无需减）
- 上三角部分：因为 $a_{ji}=a_{ij}$ ，故将上式的 $i,j$ 直接轮换即可

上/下三角矩阵：主对角线的一侧全为常数c（可为\text{0}）
- 压缩存储方法：与对称矩阵类似，将非 $c$ 三角的元素存⼊⼀维数组，常数 $c$ 非零时可存于表尾 $\frac{(1+n)n}{2}$ （零元素则无需存储），故所需存储空间为 $\frac{(1+n)n}{2}+1$
- 下三角矩阵：同对称矩阵下三角部分
- 上三角矩阵：设a_{ij}在一维数组B[0...MAXSIZE]中对应的下标为k，则
```
 $k=\frac{(i-1)(2n-i+2)}{2}+(j-i)$ 
```

（三）对角矩阵（带状矩阵）：除主对⻆线及其上下两条斜向带状区域内元素外，其余元素全为常数c（可为\text{0}）
- 压缩存储方法：类似三角矩阵，常数 $c$ 非零时可存于表尾，计算方式也类似（注意最上、下两⾏元素仅含2个非 $c$ 元素）【详细计算式待更新】

5.2.2 稀疏矩阵的存储⽅法

稀疏矩阵：⾮零元素远少于零元素的矩阵，可以利用零元素节约大量存储、运算和程序运行时间。

常见的稀疏矩阵存储方法如下所示：

三元组表示法：根据⾏优先或列优先，⽤三元数对(i,j,v)的三元组矩阵存储⾮0元素的特征。在节省大量存储空间的同时，会使得稀疏矩阵失去随机存取的特性
- 0行特殊存储稀疏矩阵信息：行数、列数、非零元个数
- 其余每行代表一个非零元素：行标、列标、值

【例】如图为以⾏优先存储将稀疏矩阵 $M$ ⽤三元组矩阵表示：

伪地址法：按元素在矩阵中⾏优先或列优先存储的相对位置计算得出其伪地址（同5.1中数组的元素存储地址计算）
邻接表表示法：⽤存图的⽅式存储（详见7.2.2邻接表）
⼗字链表表示法：使⽤⼗字链表存储，结构体如下

typedef struct OLNode {
    int row, col;   // ⾏号、列号
    struct OLNode *right, *down;    // 指向右边结点、下⽅结点
    ElemType val;   // 若为元素结点则储存元素值，若为表最左边、最上边的头结点则不存储数据
} OLNode;   // 链表结点

typedef struct OLHead {
    OLNode *rhead, *chead;  // 指向⾏、列头结点数组
    int m, n, k;    // 矩阵⾏数、列数、⾮零结点总数
} CrossList;

5.3 广义表

⼴义表（Generalized List）：表元素可以是原⼦或者⼴义表的线性表扩展结构。

5.3.1 广义表的重要概念

⻓度（Length）：表直接包含的元素（原子或子表）的个数，即广义表表达式中最上层元素的个数。长度为0的表称为空表，用 $()$ 表示。

深度（Depth）：广义表表达式中嵌套括号的最⼤层数。特别地，原子的深度为0，空表的深度为1。

【例1】写出下列⼴义表的⻓度与深度

$A=(())$ ：元素为空表的表。⻓度为1，深度为2

$B=(d,e)$ ：元素全为原⼦。⻓度为2，深度为1

$C=(b,(c,d))$ ：第⼆个元素为另⼀个⼴义表 $(c,d)$ 。⻓度为2，深度为1

$D=(B,C)$ ：引⽤了已有⼴义表 $B,C$ ，展开可得 $((d,c),(b,(c,d)))$ ，⻓度为2，深度为3

$E=(a,E)$ ：长度为2；由递归定义，展开可得 $(a,(a,(a,(a,\cdots))))$ ，深度无限

$F=((a))$ ：元素为“元素只含原子 $a$ 的表”的表。⻓度为1，深度为2

表头（Head）：第⼀个元素（既可为原⼦也可为表）

表尾（Tail）：其余所有元素组成的表（只可为表）

常⽤操作：取表头 $\text{GetHead}(\cdot)$ 、取表尾 $\text{GetTail}(\cdot)$

【例2】对例1中出现的部分表执⾏各种取表头尾操作：
$\text{GetHead}(B)=d,\ \text{GetTail}(B)=(e),\ \text{GetHead}(D)=B,\ \text{GetTail}(D)=(C),\ \text{GetHead}(F)=(a),\ \text{GetTail}(F)=()$

5.3.2 广义表的存储结构

头尾链表存储结构：如图所示

基本结点结构：
- 原子结点：标记域（0）、数据域
- 广义表结点：标记域（1）、头指针域（指向原子或广义表结点）、尾指针域（非空则指向本层下一个广义表结点）
特点（类似无头单链表）：
1. 链表主体都是⼴义表结点，原⼦结点只能从⼴义表结点头指针域引出
2. 广义表结点的头指针域可直接指向现有⼴义表（与其头指针汇合来引⽤），也可指向本表结点表示递归

扩展线性表存储结构（同层结点链存储结构）：如图所示

对比头尾链表存储结构，结点结构变化：原⼦结点追加尾指针域（作⽤同⼴义表结点）
特点（类似带头结点的单链表）：
1. 以⼴义表头结点开头：其头指针域为空，尾指针指向第⼀个数据结点
2. 链表主体既可为⼴义表亦可为原⼦（形式与数学式完全⼀致）
  - 注：⼦表⽆⼴义表头结点。故引⽤已有⼴义表时头指针指向被引用表的⼴义表头结点的尾指针所指的第⼀个数据结点

6 树与二叉树

树（Tree）：含有 $n\ (n≥0)$ 个结点的非线性结构，当 $n=0$ 时，称为空树；非空树有且仅有一个称为根（Root）的特殊结点；当 $n>1$ 时，非根结点可分成 $m\ (m>0)$ 个互不相交的有限集，称为子树。

6.1 树的重要性质

树的理论性质（适用于任何树）：

树的结点数等于分支数 + 1，即 $|V|=|E|+1$

$m$ 棵树的森林有 $k$ 条边（分支），则这 $m$ 棵树共有 $m+k$ 个结点
树的结点数等于所有结点度数之和 + 1，即 $|V|=\sum\limits_i \text{TD}(v_i)+1$

其中 $\text{TD}(v)$ 表示顶点 $v$ 的度数，详见第七章“图”
$m$ 叉树的结点数 $=n_0+n_1+n_2+\cdots+n_m$
$m$ 叉树的分支数 $=n_1+2n_2+\cdots+mn_m$

其中 $n_i$ 表示度为 $i$ 的结点的个数
度为 $m$ 的树的第 $i$ 层上：至多有 $m^{i-1}$ 个结点

满二叉树的第 $i$ 层上有 $2^{i-1}$ 个结点
高度为 $h$ 的 $m$ 叉树：至多有 $\frac{m^h-1}{m-1}$ 个结点

推导：等比数列求和 $S=m^{h-1}+m^{h-2}+\cdots+m+1=\frac{m^h-1}{m-1}$
具有 $n$ 个结点的 $m$ 叉树的最小高度： $h_{\min}=\left \lceil \log_{m} (n(m-1)+1) \right \rceil$
部分最⼩⾼度问题：树越胖越矮，越矮越胖。每层顶点分布尽可能多，故满⼆叉树最矮；⾼度越⼩时，每层顶点分布数越多，就越宽
部分最⼤⾼度问题：树越瘦越⾼，越⾼越瘦。与上同理

6.2 二叉树

⼆叉树（Binary Tree）：⼀种特殊的有序树，要么为空树，要么每个结点最多只有两棵⼦树，即结点的度只能为 $0,1,2$ ，子树严格区分左右顺序。

⼆叉树具有5种基本形态：

【辨析】⼆叉树与⼀般的每个结点⾄多有两棵⼦树的有序树的区别？

如果有序树中的⼦树只有⼀个孩⼦时，这个孩⼦结点就⽆须区分其左右次序；⽽⼆叉树中的孩⼦⽆论如何都明确区分左、右！

特殊⼆叉树：

满⼆叉树（Full Binary Tree）：所有分⽀结点都有左右孩⼦，叶结点集中在最后⼀层，且含有 $2^h-1$ 个结点（ $h$ 为高度）

完全⼆叉树（Complete Binary Tree，CBT）：由满⼆叉树从右⾄左、从下⾄上修剪⽽来，结点特征为都尽可能靠上、靠左集中，因此适合⽤顺序存储结构（⼀维数组）存储

6.2.1 ⼆叉树的重要性质

⼆叉树的特有性质：

二叉树中度的性质：
n_0=1+n_2
- 推广至 $m$ 叉树： $n_0=1+n_2+2n_3+\cdots+(m-1)n_m$
- 由定义可知，完全二叉树中 $n_1\leq1$
非空二叉树的第 $i$ 层上：至多有 $2^{i-1}$ 个结点
高度为 $h$ 的二叉树：至多有 $2^h-1$ 个结点，即为满二叉树时

以上两条均为非空 $m$ 叉树的特例； $\frac{2^h-1}{2-1}=2^{h}-1$
具有 $n$ 个结点的完全⼆叉树的⾼度： $h=\left \lceil \log_2 (n+1) \right \rceil = \left \lfloor \log_2 n \right \rfloor + 1$
对完全⼆叉树从上到下、从左到右顺次编号1,2,\cdots,n，根结点为第1层，则对编号为i的结点：
1. 非叶结点： $i≤\left \lfloor \frac{n}{2} \right \rfloor$
  - 编号最⼤的⾮叶结点： $\left \lfloor \frac{n}{2} \right \rfloor$ ，在其之后均为叶结点
  - 由此可得完全二叉树叶结点个数公式： $n-\left \lfloor \frac{n}{2} \right \rfloor$
2. 由结点i反推其他属性：
  - 双亲结点： $\left \lfloor \frac{i}{2} \right \rfloor$ $(i>1)$
  - 左孩子： $2i$ $(2i\leqn)$
  - 右孩子： $2i+1$ $(2i+1\leqn)$
  - 结点 $i$ 所在层次： $\left \lfloor \log_2 i \right \rfloor + 1$
    
    若层次编号从 $\text{0}$ 开始，则为 $\left \lfloor \log_2 (i+1) \right \rfloor + 1$
3. 若 $n$ 为奇数，则每个分支结点都有左右孩子
4. 若 $n$ 为偶数，则编号最⼤的⾮叶结点 $\left \lfloor \frac{n}{2} \right \rfloor$ 只有左孩子，没有右孩子，其余分⽀结点都有左右孩⼦
  
  变式：从0开始编号时依旧可推出左右孩⼦，在原有结论上+1即可

6.2.2 ⼆叉树的存储结构

孩子存储结构：二叉树的顺序存储结构，对⼆叉树按从上到下、从左到右顺序依次编号，使⽤顺序表（⼀维数组）直接存储，通常从下标 $1$ 开始存储结点

缺点：存储普通⼆叉树会造成⼤量空间浪费（不存在的孩⼦需补0）
优点：⾮常适合存储完全⼆叉树，特别是堆（详见第九章“排序”），可根据下标快速推算出结点在⼆叉树中的位置

#define MAXSIZE 1010    // ⼆叉树的最⼤结点数
int SqBiTree[MAXSIZE];

⼆叉链表存储结构：二叉树的链式存储结构，使用二叉链表存储信息，优劣与单链表相同，也可追加双亲指针变成三叉链表

性质： $n$ 个结点的二叉链表中，含有 $n+1$ 个空链域（空指针，空分枝）

计算过程：由每个叶结点有2个空指针、每个度为1的结点有1个空指针，得空指针总数为 $2n_0+n_1$ ；又由 $n_0=1+n_2$ ，可得空指针数 $=n_0+n_1+n_2+1=n+1\ (n_0+n_1+n_2=n)$

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

6.2.3 ⼆叉树的遍历

深度优先遍历（DFS）：分为先序遍历（NLR）、中序遍历（LNR）、后序遍历（LRN）等（此处的“序”指的是根结点（N）在何时被访问，实际还可有RNL、NRL等变形次序遍历）

性能： $T(n)=O(n)$ ， $S(n)=O(n)$ （使用了递归工作栈）

/* 二叉树的递归版先序、中序、后序遍历示例，其中visit()为预定义的访问函数 */
void dfs(BiTree T) {
    if (T) {
        // visit(p);        // 先序遍历
        DFS(T->lchild);
        // visit(p);        // 中序遍历
        DFS(T->rchild);
        // visit(p);        // 后序遍历
    }
}

层序遍历（Level Order）：对⼆叉树从左⾄右、从上⾄下依次遍历，相当于对⼆叉树编号的顺序

性能： $T(n)=O(n)$ ， $S(n)=O(n)$ （使用了队列）

/* 二叉树的层序遍历 */
void levelOrder(BiTree T) {
    Queue Q;    // 辅助队列
    initQueue(Q);
    BiTNode *p = T; // 遍历指针，初始指向根结点
    push(Q, p); // 根结点⼊队
    while (!isEmpty(Q)) {   // 循环条件：队列⾮空
        pop(Q, p);  // 队⾸出队（并执行其他操作）
        visit(p);
        if (p->lchild) push(Q, p->lchild);    // 左孩⼦⾮空则⼊队
        if (p->rchild) push(Q, p->rchild);    // 右孩⼦⾮空则⼊队
    }
}

【总结与归纳】⼆叉树DFS、BFS的性质：

对不同的遍历序列，相对次序发⽣变化的都是⼦树的根，即分⽀结点，叶结点的相对次序不变！

通过遍历实现各种操作：

⾮递归求⾼度与宽度问题、判断完全⼆叉树：层次遍历

祖先路径问题：后序⾮递归

求叶结点数、求⾼度：先序遍历（⽆限制就⽤递归版，容易书写）

层次遍历反转、Z型遍历（PAT甲级例题）：栈 + 队列，改造层次遍历

6.2.3.1 DFS非递归化

⾮递归化⽅法：使⽤栈来模拟递归⼯作栈的作⽤

中序⾮递归：设置初始指向根结点的遍历指针p
- 算法步骤：在栈⾮空或当前所指⾮空时循环——
  1. 当前所指⾮空时⼊栈、往左⾛
  2. 为空时则栈顶元素出栈并接收，访问它、往右⾛
- 特点：中序⾮递归的辅助栈栈顶结点为当前所指结点的⽗结点

void inOrder(BiTree T) {
    Stack S;    // 辅助栈
    initStack(S);
    BiTNode *p = T; // p为遍历指针，初始指向根结点
    while (p || !isEmpty(S)) {  // 循环条件：p⾮空或栈⾮空
        if (p) {    // p⾮空时：p⼊栈，⼀路沿左⾛
            push(S, p);
            p = p->lchild;
        } else {    // p为空时：栈顶出栈，访问之，再往其右孩⼦⾛
            pop(S, p);
            visit(p);
            p = p->rchild;
        }
    }
}

先序⾮递归：与⾮递归中序⼏乎⼀致，将访问时机提前⾄p所指⾮空时第⼀步即可

void preOrder(BiTree T) {
    Stack S;
    initStack(S);
    BiTNode *p = T;
    while (p || !isEmpty(S)) {
        if (p) {
            visit(p);   // 先序变化：⼀开始就"先"访问
            push(S, p);
            p = p->lchild;
        } else {
            pop(S, p);
            p = p->rchild;
        }
    }
}

后序⾮递归：除了遍历指针p外，还增设⽤于标记上⼀次访问的结点的标记指针r。
- 算法流程：同中序非递归，在栈⾮空或当前所指⾮空时循环
  1. 同中序非递归，当前所指⾮空时⼊栈、往左⾛
  2. 为空时读取栈顶结点先不出栈，若存在右⼦树且不是上⼀次访问过的结点r则往右走，否则此时再出栈，访问它、更新标记指针r、重置遍历指针p为空
- 特点：后序⾮递归的栈内全部结点实为当前所指结点的全部祖先（栈顶至底恰好为由近至远顺序）

void postOrder(BiTree T) {
    Stack S;    // 辅助栈中元素恰好为p所指结点的全部祖先
    initStack(S);
    BiTNode *p = T, *r = NULL;  // r标记上⼀次访问过的结点
    while (p || !isEmpty(S)) {
        if (p) {
            push(S, p);
            p = p->lchild;
        } else {    // p为空时：检查右孩⼦
            getTop(S, p);
            if (p->rchild && p->rchild != r) {    // 若右孩⼦未被遍历，则往右⾛（若存在）
                p = p->rchild;
            } else {    // 否则正常执⾏栈顶出栈，访问之，更新指针
                pop(S, p);
                visit(p);
                r = p;  // 更新记录指针r为刚访问过的p
                p = NULL;   // p置空！
            }
        }
    }
}

注：为便于正向、反向遍历，实际应⽤时常直接使⽤数组现场定义简单栈、⾮循环队列

6.2.3.2 ⼆叉树的确定

设先序、中序、后序遍历子序列分别为pre[preL...preR]、in[inL...inR]、post[postL...postR]，由“先序和中序”或“后序和中序”确定⼆叉树的通用方法如下：

根：先序的首元素pre[preL] / 后序的尾元素post[postR]
左右子树：中序对应的根位k两侧的左、右子区间（不含k）分别为左右子树；同时可在先/后序中标出这两段子树区间，统一左子树在左、右子树在右
子树根：回到先/后序，站在根处看向剩余序列，两段子树区间离根最近的结点即为⼦树根

代码化要点：注意递归⼊⼝参数表区间⻓度⼀致；可事先建立“先/后序 → 中序”的结点位置映射表，将顺序查找替换为哈希

/* 由先序和中序序列确定⼆叉树 */
BiTNode *build1(ElemType pre[], int preL, int preR, ElemType in[], int inL, int inR) {
    BiTNode *root = (BiTNode*)malloc(sizeof(BiTNode));  // 建⽴⼦树根结点
    root->data = pre[preL];  // 赋值为先序序列⾸元素

    int k;  // k记录根在中序序列中对应的位置
    for (k = inL; k <= inR && in[k] != root->data; k++);  // 在中序序列中顺序查找（或改为哈希映射）

    if (inL < k) // 递归构建左⼦树
        root->lchild = build1(pre, preL + 1, preL + 1 + (k - 1 - inL), in, inL, k - 1);
    else
        root->lchild = NULL;

    if (k < inR) // 递归构建右⼦树
        root->rchild = build1(pre, preL + 1 + (k - 1 - inL) + 1, preR, in, k + 1, inR);
    else
        root->rchild = NULL;

    return root;
}

/* 由后序和中序序列确定⼆叉树 */
BiTNode *build2(ElemType post[], int postL, int postR, ElemType in[], int inL, int inR) {
    BiTNode *root = (BiTNode*)malloc(sizeof(BiTNode));
    root->data = post[postL];    // 赋值为后序序列尾元素

    int k;
    for (k = inL; k <= inR && in[k] != root->data; k++);

    if (inL < k)
        root->lchild = build2(post, postL, postL + (k - 1 - inL), in, inL, k - 1);
    else
        root->lchild = NULL;

    if (k < inR)
        root->rchild = build_2(post, postL + (k - 1 - inL) + 1, postR - 1, in, k + 1, inR);
    else
        root->rchild = NULL;

    return root;
}

仅靠“前序和后序”序列无法唯一确定⼆叉树，但可以确定部分信息：

确定祖先关系：当结点 $v_1,v_2$ 在前序、后序序列中顺序相反（前序中 $v_1$ 在 $v_2$ 之前，后序中 $v_2$ 在 $v_1$ 之前）时， $v_1$ 为 $v_2$ 的祖先
前序与后序序列正好相反的⼆叉树只有⼀个叶⼦（例如单分⽀⼆叉树）

6.2.4 线索⼆叉树

线索⼆叉树（Thread Binary Tree）：树的⼀种特殊的存储结构。追加两个线索标记ltag、rtag，通过某种遍历序列，利⽤空的孩⼦指针（空分支，图示中常用^表示）将⼆叉树中每⼀个结点排成⼀个线性序列，除头尾外都有⼀个直接前驱和直接后继。此时该孩⼦指针被称为线索

ltag == 0：lchild指向结点的左孩子；ltag == 1：lchild指向结点的前驱
rtag == 0：rchild指向结点的右孩子；rtag == 1：lchild指向结点的后继

typedef struct TBiTNode {
    ElemType data;
    struct TBiTNode *lchild, *rchild;
    int ltag, rtag; // 左、右线索标记
} TBiTNode, *TbiTree;   // 线索链表存储结构

核⼼操作——建⽴线索（适⽤于任何遍历序列）：需要增设遍历指针p与前驱指针pre【完整代码待更新】

/* 线索化核⼼操作，使⽤某序遍历就在对应位置执⾏以下过程
 * 指针p为遍历指针，前驱指针pre指向结点p前⼀个被遍历的结点（初始为NULL）
 */
 if (!p->lchild) {   // 建⽴前驱线索
    p->lchild = pre;
    p->ltag = 1;
 }
 if (pre && !pre->rchild) {  // 建⽴前驱结点的后继线索，注意pre需⾮空
    pre->rchild = p;
    pre->rtag = 1;
 }
 pre = p;

注：前序线索化时递归⼊⼝前需特判⾮线索！

遍历过程：

for (TBTNode *p = First(TBT); p; p = Next(p))
    visit(p);

常用操作：

中序线索⼆叉树
- first(p)（求⼦树中第⼀个结点）：从根结点往左⼀直⾛直⾄左指针为左线索，即为序列第⼀个结点
- last(p)（求子树中最后一个结点）：同上，改成往右⼀直⾛并遇⻅右线索
  
  联系中序⾮递归流程中"当前所指⾮空"时⼀直左⾛的操作！
- next(p)（求结点的后继）：若右指针⾮线索，则返回其所指的右⼦树的第⼀个结点；否则直接返回右线索所指的后继
- prior(p)（求结点的前驱）：同时，改成左指针所指的左子树的最后一个结点；否则直接返回左线索所指的前驱
  
  与BST查找操作极为相似，若⽆法直接根据线索返回，则"拐"⼀下⾛⾄尽头
先序线索⼆叉树
- 找⼦树中第⼀个结点：显然为根结点
- 找结点的后继：【从左开始看】
  1. 有左孩⼦：后继是左孩⼦
  2. ⽆左孩⼦但有右孩⼦：后继是右孩⼦
  3. 为叶结点：后继如右线索所指示
后序线索⼆叉树
- 仅考察找结点的后继：【从右开始看】
  1. 为根结点：后继为空
  2. 为父结点的右孩⼦，或为父结点的左孩⼦且父结点⽆右孩⼦：后继为父结点
  3. 为父结点的左孩⼦且父结点有右孩⼦：后继为父结点右⼦树上的第⼀个结点

6.3 树与森林

森林（Forest）：多棵互不相交的树的集合

6.3.1 树与森林的存储结构

双亲表示法：⼀种顺序存储结构，使⽤顺序表（⼀维数组）实现，下标对应结点，每个空间存储下标对应结点的父结点的下标

#define MAXSIZE 1010

typedef struct Tree {
    ElemType data;
    int parent;
} Tree;

Tree T[MAXSIZE];

孩⼦表示法：直接⽤图的邻接表结构存储各结点的孩⼦（树可视作一类特殊的图），详⻅第七章"图"

孩⼦兄弟表示法：使⽤⼆叉链表存储树，将树与森林⼆叉树化（见下一节）。child、sibling分别指向结点的第⼀个孩⼦、兄弟

typedef struct CSTNode {
    ElemType data;
    struct CSTNode *child, *sibling;
} CSTNode, *CSTree;

6.3.2 树、森林与⼆叉树的转换

树与⼆叉树互相转换：

树 → ⼆叉树：
1. 把互为兄弟的孩⼦们连起来
2. 每个⽗结点只保留⼀条与孩⼦的连线（通常选择最左的孩⼦），删除多余的线
还原为树：
1. 把孩⼦们与其⽗结点连起来（即与最左兄弟相连的那位）
2. 删除所有孩⼦之间的线

森林与⼆叉树互相转换

森林 → ⼆叉树：
1. 先将森林中的每棵树分别转化成⼆叉树（根结点只允许有左分枝，右分枝需为空）
2. 利⽤各个根的右空分枝，将所有根结点顺次连起来
还原为森林：
1. 删除各根结点右分枝的线（根结点即第⼀“斜层”的结点）
2. 将各⼆叉树还原为树

6.3.3 树与森林的遍历

树、森林与⼆叉树的深度优先遍历对应关系：

树	森林	二叉树
先根遍历：根 → ⼦树	先序遍历	先序遍历
后根遍历：⼦树 → 根	后序遍历（又称中序遍历）	中序遍历

注意！对于森林，有时也称后序遍历为中序遍历，记住两者是⼀回事即可，名称只是形式！

层序遍历：同⼆叉树的层序遍历，使⽤队列

6.4 树与二叉树的应用

"堆"位于第⼋章"搜索"之"堆排序"

"⼆叉排序树"与"平衡⼆叉树"位于第九章"查找"

6.4.1 表达式⼆叉树

表达式⼆叉树：⽤⼆叉树表示表达式的运算规则

建树：叶结点均为操作数；⾮叶结点均为运算符，左、右⼦树为参与该运算的⼦表达式（正好按中缀摆放），该⼦树即表示⼀个⼦表达式
还原：遍历可得前缀（前序遍历）、中缀（中序遍历）、后缀（后序遍历）表达式

求值：递归求值，遇到操作符则递归计算⼦表达式，遇到操作数则直接返回

double calSub(double A, char op, double B); // 子树求值函数，返回运算结果（即子树表达式的值，必合法）

double calExpTree(BiTree T) {
    if (!T) return 0;   // ⼦树为空则返回0

    if (T->lchild || T->rchild) { // 当前为⾮叶结点（操作符结点）则递归计算
        double A = calExpTree(T->lchild);    // 递归计算左⼦树
        double B = calExpTree(T->rchild);    // 递归计算右⼦树
        return calSub(A, T->data, B);    // 返回计算结果
    } else {
        return T->data - '0';  // 当前为叶结点（操作数结点）则返回其数值
    }
}

【例】表达式a+b*(c-d)-e/f可表示成如下所示的表达式二叉树

6.4.2 哈夫曼树与哈夫曼编码

带权树的核心概念：

结点的路径⻓度：从根结点到某结点途中经过的边数
结点的带权路径⻓度：某结点的路径⻓度 $l$ 与该结点上权值 $w$ 的乘积
树的带权路径⻓度：所有叶结点的带权路径⻓度之和，记为
```
 $\text{WPL}=\sum\limits_{i=1}^n w_i l_i$ 
```
哈夫曼树（Huffman Tree）：带权路径最短的树，可以为⼆叉树，亦可为多叉树

哈夫曼树的构造（以⼆叉树为例）：

将 $n$ 个结点分别作为 $n$ 棵仅含1个结点的二叉树，形成一片森林
构造新结点：从森林中挑出两棵权值最⼩的树（可以事先按权值大小排序），作为新结点的左右⼦树，新结点的权值为左右⼦树的权值之和，然后将新结点加⼊森林中。
- 若结点数不够，则在最开始时补上权值为0的结点（不影响WPL）
重复第 2 步操作，直⾄森林中只剩下⼀棵树为⽌

哈夫曼树的性质：

所有初始结点最终均成为叶结点，且权值越⼩的结点WPL越⼤，反之越⼩
所有新结点均为双分⽀结点，故哈夫曼树不存在度为1的结点（ $n_1=0$ ），这种⼆叉树称为正则（严格）⼆叉树
构造过程中共新建了 $n-1$ 个结点，故哈夫曼树的总结点数为 $2n-1$

各种编码的核心概念：

固定⻓度编码：每个字符⽤相等⻓度的⼆进制位表示
可变⻓度编码：对不同字符⽤不等⻓的⼆进制位表示：⾼频字符赋以短编码，低频字符赋以较⻓编码，使得字符的平均编码⻓度减短，起到压缩数据的效果（例如哈夫曼编码）
前缀码：没有⼀个编码是另⼀个编码的前缀的编码。【例】 $0,101,110$ 是前缀码
哈夫曼编码（Huffman Coding）：⽤哈夫曼树对字符（叶结点）按出现频度（权值）进⾏编号的⼀种前缀码

哈夫曼编码过程：

将每个出现的字符以其出现频度（或次数）为结点权值构造哈夫曼树
标记所有边，通常规定左分枝标记 $\text{0}$ 、右分枝标记 $\text{1}$
从根⾛到某叶结点，记录路径上的编号，即为哈夫曼编码，其WPL即为⼆进制编码⻓度

哈夫曼树、哈夫曼编码不唯⼀，但各树的WPL必定相同且为最优，且哈夫曼树的最大高度为哈夫曼编码的最大长度 + 1。

【例】字符集{a, b, c, d, e, f}所对应的权值集合为 $\{8, 3, 4, 6, 5, 5\}$ ，以此构造的⼀棵哈夫曼树为

所构造的哈夫曼树的 $WPL=6\times 2 + 3\times 3+ 4\times 3 + 8\times 2 + 5\times 3 + 5\times 3 = 79$

字符集{a, b, c, d, e, f}中各字符所对应的哈夫曼编码分别为： $00,010,011,10,110,111$

6.4.3 并查集

并查集（Disjoint-Set）：双亲表示法的应⽤，通常规定元素存储范围为 $[1, n]$ ，祖宗存储元素为其⾃身（或规定为其他特定标记如-1、0）

基本操作：

初始化

int p[MAXSIZE], n;  // p[1...n]

for (int i = 1; i <= n; i++)
    p[i] = i;

查找操作：查找元素x的祖宗结点，同时更新沿路祖宗信息， $T(n)=O(n)$

int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

合并操作：合并两个元素所在的集合，同时更新祖宗信息

p[find(a)] = find(b);

判断两个结点是否属于同一集合的条件：p[find(a)] == find(b)

本文仅介绍朴素并查集，对于维护更多关系的复杂并查集详见常用算法代码模板。

7 图

图（Graph）由顶点集和边集组成，记为 $G=\{V,E\}$ 。边集 $E$ 可以为空，但顶点集 $V$ 一定非空，即图至少要有一个顶点（因此无“空图”这种说法）。图中的一部分顶点与边构成的图称为子图（Subgraph，又称生成图）。边上赋予的数值称为边的权值，带权的图称为⽹（Network）。

根据边有无方向划分：

有向图（Directed Graph）：边为有向边（弧）的图，从顶点 $u$ 至 $v$ 的弧记为 $\left \langle u,v \right \rangle$ ，两端分别称为弧头和弧尾
无向图（Undirected Graph）：边为⽆向边的图，顶点 $u$ 与 $v$ 的边是顶点的无序对，记为 $(u,v)$

简单图与多重图：⽆重边、⽆⾃环的图称为简单图，否则称为多重图【数据结构通常只研究简单图】

稀疏图与稠密图：边数⼩于 $n\log n$ 的图称为稀疏图，否则称为稠密图

更多定义详见下文

7.1 图的重要性质

顶点的度：

⽆向图中，顶点的度 $\text{TD}(v)$ 为邻接于顶点 $v$ 的边的条数，全部顶点的度数之和等于边数的2倍，即 $\sum\limits_i \text{TD}(v_i)=2|E|$
有向图中，顶点的⼊度 $\text{ID}(v)$ 为指入顶点 $v$ 的边（入边）的条数，顶点的出度 $\text{OD}(v)$ 为从顶点 $v$ 指出的边（出边）的条数，顶点的度 $\text{TD}(v)=\text{ID}(v)+\text{OD}(v)$ ，全部顶点的入度之和等于出度之和，且都等于边数，即 $\sum\limits_i \text{ID}(v_i)=\sum\limits_i \text{OD}(v_i)=|E|$

【总结与归纳】图的度相关计算

由度与边数的关系可知：⽆向图中，所有顶点度的和必为偶数

任何图中度为奇数的顶点个数为偶数个

路径、环、路径⻓度：

路径：由⼀些顶点及对应的边组成的顶点序列。若第⼀个顶点与最后⼀个顶点相同则称为回路（环）
- 判断环的方法：DFS、拓扑排序、求关键路径…
简单路径、简单回路：顶点不重复出现的路径、回路。当 $|E|>|V|-1$ 时，必定有回路
路径长度：路径中的边数或边权之和
距离：两个顶点的最短路径⻓度称为两点间的距离，若不存在路径，则记距离为⽆穷（ $\infty$ ）或其他特殊记号

完全图：

无向完全图：任意两个顶点之间都存在边的⽆向图，有 $\frac{n(n-1)}{2}$ 条边
有向完全图：任意两个顶点之间都存在⽅向相反的两条弧的有向图，有 $n(n-1)$ 条弧

连通、连通图、连通分量：

连通：⼀对顶点 $u$ 与 $v$ 之间，从顶点 $u$ 到 $v$ 有路径存在
连通图：任意两个顶点都是连通的⽆向图。 $n$ 个顶点的连通图至少有 $n-1$ 条边，至多有 $\frac{n(n-1)}{2}$ 条边
连通分量：⾮连通图中的极⼤连通⼦图（包含边数最多）

强连通、强连通图、强连通分量：

强连通：⼀对顶点 $u$ 与 $v$ 之间，从 $u$ 到 $v$ 和从 $v$ 到 $u$ 都有路径存在
强连通图：任意两个顶点都是强连通的有向图。 $n$ 个顶点的强连通图至少有 $n$ 条边，至多有 $n(n-1)$ 条边
强连通分量：⾮强连通图中的极⼤强连通⼦图

⽣成树（⽆向树）：连通图/连通分量中包含图中全部顶点的⼀个极⼩连通⼦图（边数最少）。生成树的性质如下

对于 $n$ 个顶点的图，生成树有且仅有 $n-1$ 条边；故对⽣成树⽽⾔，砍去⼀条边则变为⾮联通图，加上⼀条边则构成环
只要⽆向连通图中没有权值相同的边，则其最⼩⽣成树必唯⼀；但当存在权值相同的边时，其最⼩⽣成树可能唯⼀也可能不唯⼀（因为可能该图本身就是树）

有向树：⼀个顶点的⼊度为0、其余顶点的⼊度均为1的有向图，若⼲棵不相交的有向树组成⽣成森林

【总结与归纳】图的综合计算题

有28条边的⾮连通⽆向图⾄少有多少个顶点？

【分析】先套完全图边数公式算出顶点数 $n$ ，再加1即可

【解】当图为完全图时，解 $\frac{n(n-1)}{2}=28$ 得 $n=8$ ，则⾮连通图的最少顶点数为 $8+1=9$

要保证含有 $n$ 个顶点的无向图 $G$ 在任何情况下（即任意变动图中的边）都是连通的，则需要的边数最少是？

【解】先取其中任意 $n-1$ 个顶点构成完全连通子图，即产生 $\frac{n(n-1)}{2}$ 条边，再将该子图与剩下的顶点添1条边即可，故总计至少需要 $\frac{n(n-1)}{2}+1$ 条边

7.2 图的存储结构

预定义两种类型：

VexType：顶点信息的类型，可为int（序号）、double（操作数）、char（运算符、字母）等
EdgeType：边信息的类型，无权图中可用bool或int指示边是否存在，带权图中可用int或double存储权值（无边则为 $\infty$ ）

⽆向图可以⽤存两条有向边的⽅式存储，故以下在存储结构中不作区分

边的结构体详见7.4.1.2“Kruskal算法”。

7.2.1 邻接矩阵

邻接矩阵（Adjacent Matrix）：⽤⼆维数组（邻接矩阵）存储图中的边的信息。

无权图： $\text{1}$ 表示存在边， $\text{0}$ 表示不存在边
带权图：存在边则存储边的权值（⾃身到⾃身可记为 $\text{0}$ ），不存在边则记 $\infty$ 或其他特殊记号

#define MAXSIZE 55

typedef struct MGraph {
    VexType vex[MAXSIZE];   // 顶点信息数组
    EdgeType edge[MAXSIZE][MAXSIZE];    // 邻接矩阵，存储边的信息
    int v, e;   // 图的基本信息：顶点数、边数
} MGraph;   // 邻接矩阵图

特点：

空间复杂度： $O(|V|^2)$
稠密图适合⽤邻接矩阵存储
寻找给定点的邻边需遍历⼀整⾏/列；但可随机存取，能⽴刻判断边的存在性
⽆向图的邻接矩阵是对称矩阵且唯⼀，故实际只需存储上/下三⻆部分的元素（详见5.2.1“特殊矩阵的压缩存储”）
度的计算
- ⽆向图中：第 $i$ 行/列非零非 $\infty$ 元素的个数为顶点 $v_i$ 的度 $\text{TD}(v_i)$
- 有向图中：G->edge[i][j]表示弧\left \langle v_i,v_j \right \rangle，第1维射出，第2维射⼊
  - 第 $i$ 行非零非 $\infty$ 元素的个数为顶点 $i$ 的出度 $\text{OD}(v_i)$
  - 第 $j$ 列非零非 $\infty$ 元素的个数为顶点 $v_j$ 的入度 $\text{ID}(v_j)$

7.2.2 邻接表

邻接表（Adjacent List）：对每个顶点建⽴⼀条单链表存储该顶点出边的信息，头指针采⽤顺序存储（一维数组），整个结构即为邻接表

边表：结点结构与单链表完全相同，记录了出边的弧尾结点以及边的权值
顶点表：将各链表的头指针与对应的顶点信息存于⼀维数组中

#define MAXSIZE 55

typedef struct ArcNode {
    EdgeType data;  // 边的信息
    int adjvex; // 邻接顶点的序号
    struct ArcNode *nextarc;    // 后继指针
} ArcNode;  // 边表结点

typedef struct VNode {
    VexType data;   // 顶点信息
    ArcNode *firstarc;  // 指向边表的第⼀条边（相当于头指针）
} VNode;    // 顶点结点

typedef struct AGraph {
    VNode adjlist[MAXSIZE]; // 顶点表，存放各边表的头指针
    int v, e;   // 图的基本信息：顶点数、边数
} AGraph;   // 邻接表图

特点：

空间复杂度：无向图为O(|V|+2|E|)，有向图为O(|V|+|E|)
- 对于⽆向图，相当于每条“有向边”出现了两次，故为如此
稀疏图适合⽤邻接表存储，时空效率上远优于邻接矩阵
寻找给定点的邻边只需遍历边表即可；但⽆法随机存取，判断边的存在性亦需进⾏遍历
度的计算：出度直接等于顶点边表的⻓度，⼊度则需遍历全表统计
- 改进⼊度的计算：再建⽴⼀个逆邻接表
根据存图时的遍历顺序，邻接表的表示⽅式不唯⼀

7.2.3 其他存储结构

⼗字链表：存储有向图。与5.2.2中稀疏矩阵的存储⽅法略有不同，存图时的结构体特点如下：

弧结点：tailvex、headvex分别存储弧尾、弧头顶点编号，hlink、tlink分别指向弧头、弧尾相同的下一个弧，info存储弧的相关信息（如权值）
顶点结点：data存储顶点数据，firstin、firstout分别指向以该顶点为弧头、弧尾的第一个弧结点

邻接多重表：存储⽆向图，每条边只需⼀个结点存储（了解即可）

表结点：mark、ivex、ilink、jvex、jlink、info
顶点结点：data、firstedge

7.3 图的遍历

图的遍历⽅式同样适⽤于树，但遍历图需使⽤访问标记数组visited[]标记已被遍历过的顶点。

DFS与BFS的应用极为广泛，并不局限于图。限于篇幅，本文暂仅给出图的遍历代码示例。

7.3.1 广度优先遍历

⼴度优先遍历（Breadth-First-Search，BFS）：类似于树的层序遍历，使⽤了辅助队列

性能：
- 时间复杂度：邻接矩阵图为 $O(|V|^2)$ ，邻接表图为 $O(|V|+|E|)$
- 空间复杂度： $O(|E|)$ （使用了队列）
图的BFS代码示例：

/* 邻接矩阵图的BFS算法 */
void bfs(MGraph *G, int v, bool visited[]) {
    Queue Q;
    initQueue(Q);
    visit(v);   // 访问起点
    visited[v] = true;  // 置访问标记为true
    push(Q, v); // 将起点⼊队
    while (!isEmpty(Q)) {
        pop(Q, v);
        for (int i = 0; i < G.v; i++) {  // 遍历邻接矩阵的第v⾏
            if (G->edge[v][i] && !visited[i]) {
                visit(i);   // 访问邻接顶点
                visited[i] = true;  // 置访问标记为true
                push(Q, i); // 将邻接顶点⼊队
            }
        }
    }
}

/* 邻接表图的BFS算法 */
void bfs(AGraph *G, int v, bool visited[]) {
    Queue Q;
    initQueue(Q);
    visit(v);   // 访问起点
    visited[v] = true;  // 置访问标记为true
    push(Q, v); // 将起点v⼊队
    while (!isEmpty(Q)) {
        pop(Q, v);
        ArcNode *p = G->adjlist[v].firstarc;
        while (p) { // 沿着链表访问未访问过的顶点
            int k = p->adjvex;
            if (!visited[k]) {
                visit(k);   // 访问邻接顶点
                visited[k] = true;  // 置访问标记为true
                push(Q, k); // 将邻接顶点⼊队
            }
            p = p->nextarc;
        }
    }
}

/* 封装BFS函数（两种图皆适⽤） */
void bfsTraverse(Graph *G, int v) {
    bool visited[MAXSIZE] = {0};    // 访问标记数组，初始化全为false，被访问则置true
    bfs(G, v, visited); // 从起点v开始遍历
    for (int i = 0; i < G.v; i++)    // 检查是否有未被遍历到的顶点
        if (!visited[i])
            bfs(G, i, visited)
}

7.3.2 深度优先遍历

深度优先遍历（Depth-First-Search，DFS）：类似于树的先序遍历，常⽤递归

效率：
- 时间复杂度：邻接矩阵图为 $O(|V|^2)$ ，邻接表图为 $O(|V|+|E|)$
- 空间复杂度： $O(|V|)$ （使用了递归工作栈）
图的DFS代码示例：

/* 邻接矩阵图的DFS算法 */
void dfs(MGraph *G, int v, bool visited[]) {
    visit(v);   // 访问顶点
    visited[v] = true;  // 置访问标记为true
    for (int i = 0; i < G->v; i++)    // 遍历邻接矩阵的第v⾏
        if (G->edge[v][i] && !visited[i])
            dfs(G, i, visited);
}

/* 邻接表图的DFS算法 */
void dfs(AGraph *G, int v, bool visited[]) {
    visit(v);   // 访问顶点
    visited[v] = true;  // 置访问标记为true
    ArcNode *p = G->adjlist[v].firstarc;
    while (p) { // 沿着链表访问未访问过的顶点
        if (!visited[p->adjvex]) dfs(G, p->adjvex, visited);
        p = p->nextarc;
    }
}

/* 封装DFS函数（两种图皆适⽤） */
void dfsTraverse(Graph *G, int v) {
    bool visited[MAXSIZE] = {0};    // 访问标记数组，初始化全为false，被访问则置true
    dfs(G, v, visited); // 从起点v开始遍历
    for (int i = 0; i < G.v; i++)    // 检查是否有未被遍历到的顶点
        if (!visited[i])
            dfs(G, i, visited);
}

7.3.3 BFS、DFS的应用

判断图的连通性：从任意顶点出发遍历⼀次，检查标记数组是否全标记即可

连通分量的计算：计算总计有⼏个顶点作为起点进⾏了遍历即可

DFS⽣成树、BFS⽣成树：根据DFS、BFS的轨迹所得的⽣成树，⾮连通图的⽣成树组成⽣成森林

⽣成树的⾼度⽐较：
- 对于⼀些特殊的图（例如只有⼀个顶点的图），其BFS⽣成树的树⾼和DFS⽣成树的树⾼相等。
- 对于⼀般的图，根据图的BFS⽣成树和DFS树的算法思想， BFS⽣成树⽐DFS⽣成树矮。综上， $h_{\text{BFS树}}≤h_{\text{DFS树}}$
邻接矩阵图的⽣成树是唯⼀的，邻接表图的⽣成树根据链表初始化⽅式⽽变

计算单源最短路径：当图中各边权值相等时（例如迷宫），可⽤BFS计算单源最短路径

7.4 图的应用

最小生成树、最短路径、DAG存储表达式、拓扑排序、关键路径…

7.4.1 最小生成树

最⼩⽣成树（Minimum Spanning Tree，MST）：带权⽆向连通图中权和（代价）最⼩的⽣成树

7.4.1.1 Prim算法

Prim算法：“加点法”，每次迭代选择代价最⼩的边对应的点。常使用邻接矩阵图进行计算。与Dijstral算法极为相似。

辅助变量：

lowcost[]：最小代价数组，存储其他点到当前⽣成树的最短距离（邻接则为出边权，不邻接则为\infty）
- 注：与Dijstra算法的距离数组不同，Prim算法的最⼩代价数组记录的是到整棵树的距离
visited[]：标记数组，标记点是否已经在⽣成树中

算法过程：

第⼀次代谢：任取⼀顶点（常为序号 $1$ ）作为⽣成树 $T$
选择剩余顶点中与当前⽣成树距离最近（lowcost值最小）的顶点，将该顶点与对应的边（权值）并⼊ $T$ （权和）
从新并⼊顶点出发，更新lowcost[]（注：为到整棵树的距离，故无需累加至历史值）；反复执⾏2、3两步，共 $|V|-1$ 次

算法性能分析：时间复杂度为 $O(|V|^2)$ ，只跟顶点数有关，因此适⽤于稠密图，即边稠密⽽顶点较少

/* 计算从顶点v出发构建的最⼩⽣成树的最⼩代价，⽤sum返回结果 */
void Prim(MGraph *G, int v, EdgeType *sum) {
    EdgeType lowcost[MAXSIZE];  // 最⼩代价数组，记录当前⽣成树到其他各顶点的最短距离
    bool visited[MAXSIZE] = {0};    // 标记数组，记录顶点是否并⼊⽣成树，初始均为未并⼊状态
    for (int i = 0; i < G->v; i++) {
        lowcost[i] = G->edge[v][i];  // 初始化最⼩代价为源点v的出边权（或⽆穷）
    }
    *sum += G->vex[v];   // 并⼊源点
    visited[v] = true;
    for (int i = 0; i < G->v - 1; i++) {  // 进⾏(|V| - 1)次循环，每轮并⼊⼀个顶点⾄⽣成树
        EdgeType min = INF; // 记录当前⽣成树到其他顶点的最⼩距离
        for (int j = 0; j < G->v; j++) {  // 寻找剩余顶点中最⼩⽣成树最近的顶点
            if (!visited[j] && lowcost[j] < min) {
                min = lowcost[j];
                v = j;
            }
        }
        *sum += G->vex[v];   // 并⼊该顶点
        visited[v] = true;
        for (int j = 0; j < G->v; j++) {  // 更新当前最⼩⽣成树到剩余顶点的最⼩距离
            if (!visited[j] && G->edge[v][j] < lowcost[j]) {
                lowcost[j] = G->edge[v][j];  // 注：lowcost为到整棵树的距离
            }
        }
    }
}

7.4.1.2 Kruskal算法

Kruskal算法：“加边法”，按权值递增次序，每次迭代选择最⼩代价边。⾮常适合⼿⼯操作。

辅助变量：

p[]：并查集数组，检查顶点是否属于不同集合（树）时使⽤
edges[]：Kruskal算法的存图⽅式为边的结构体，存储所有边的信息

typedef struct Edge {
    int a, b;   // 边的起点与终点
    EdgeType w; // 边的权值（Weight）
} Edge;

算法过程：

将图中的所有边按代价从⼩到⼤排序；将图中的 $n$ 个顶点看成独⽴的 $n$ 棵树组成的森林
从⼩到⼤选择边，所选的边的两个端点应属于两棵不同的树，则成为⽣成树的⼀条边，并将这两颗树合并作为⼀颗树
重复第2步，直至所有顶点都在⼀棵树内，或有 $n-1$ 条边为⽌

算法性能分析：时间复杂度为 $O(|E|\log_2 |E|)$ ，只跟边数有关，因此适⽤于稀疏图，即边稀疏⽽顶点较多

【代码实现待更新】

注：使⽤Prim算法和Dijstral算法⽣成的MST是相同的

7.4.2 最短路径

7.4.2.1 Dijkstra算法

7.4.2.2 Floyd算法

7.4.3 有向无环图存储表达式

7.4.4 拓扑排序

7.4.5 关键路径

8 查找

8.1 简单查找

8.1.1 顺序查找

8.1.2 折半查找

8.1.3 分块查找

8.2 树型查找

8.2.1 二叉排序树

8.2.2 平衡二叉树

8.2.3 红黑树

8.3 B树与B+树

8.3.1 B树

8.3.2 B+树的基本概念

8.4 散列表

8.4.1 散列函数与冲突

8.4.2 散列性能分析

9 排序

9.1 插入类排序

9.1.1 直接插入排序

9.1.2 折半插入排序

9.1.3 希尔排序

9.2 交换类排序

9.2.1 起泡排序

9.2.2 快速排序

9.3 选择类排序

9.3.1 简单选择排序

9.3.2 堆排序

9.4 归并排序

9.5 基数排序

9.6 外部排序

A 参考文献

WIP

B C语言强化补充

源自“第0章 C语⾔强化补充笔记”，运算符优先级表新增了部分C++内容（范围解析）。

B.1 数据类型的⻓度

以下几类常用数据类型的长度随操作系统而变：

操作系统\数据类型	int	long	long long	指针
16位	2B	4B	-	2B
32位	4B	4B	8B	4B
64位	4B	8B	8B	8B

以下几类数据类型在任意操作系统均为固定长度：

数据类型	char	short	float	double
固定长度	1B	2B	4B	8B

结构体补齐：结构体变量的总大小为结构体变量中最大基本数据类型成员所占字节数的整数倍

B.2 运算符优先级

下表中数字越⼩，优先级越⾼（即“越先算”）：

优先级	运算符	结合方向
0	`::`（C++范围解析）	自左向右
1	`i++`（后缀自增） `i--`（后缀自减） `()`（圆括号/函数调用运算符） `[]`（数组下标） `.`（成员） `->`（指向成员）	`++` `--`：自右向左其他：自左向右
2	`++i`（前缀自增） `--`（前缀自减） `+`（正号） `-`（负号） `!`（逻辑非） `~`（按位取反） `(type)`（强制类型转换） `*`（指针） `&`（取地址/C++引用） `sizeof`（按字节确定大小）	自右向左
3	`*`（乘） `/` `%`	自左向右
4	`+`（加） `-`（减）	自左向右
5	`<<`（按位左移） `>>`（按位右移）	自左向右
6	`<` `<=` `>` `>=`	自左向右
7	`==` `!=`	自左向右
8	`&`（按位与）	自左向右
9	`^`（按位异或）	自左向右
10	`\|`（按位或）	自左向右
11	`&&`（逻辑与）	自左向右
12	`\|\|`（逻辑或）	自左向右
13	`? :`（三目条件运算符）	自右向左
14	`=` `+=` `-=` `*=` `/=` `%=` `&=` `^=` `\|=` `<<=` `>>=`	自右向左
15	`,`（逗号运算符）	自左向右

B.3 数据的输⼊输出

格式化输⼊（scanf）：格式字符串为%[*][宽度][类型长度]类型

类型（Type）：常用的格式类型如下表所示

数据类型格式	说明	进制数与特殊表示格式	说明
`%d`	整型（int）	`%o`	八进制
`%ld`	长整型（long int）	`%#o`	带前导的八进制
`%f`	单精度浮点型（float）	`%x`	十六进制
`%lf`	双精度浮点型（double）	`%#x`	带前导的十六进制
`%c`	字符（char）	`%s`	字符串

*：表示该输入项读入后不赋予相应变量，即跳过该输入值
- 【例】scanf("%d %*d %d", &a, &b);：输入1 2 3，使得a赋1，2被跳过，b赋3
宽度：用十进制整数指定输入的宽度（字符数）
- 【例】scanf("%4d%4d", &a, &b);：输入12345678，把1234赋给a、5678赋给b
类型长度：格式符有l（对应%ld、%lf）和h（对应%hd短整型数据）
- 注：scanf无法控制精度

格式化输出（printf）：格式字符串为%[标志][宽度][.精度][类型长度]类型，用*表示未指定

类型（Type）：常用的格式类型如下表所示

基本数据类型格式	说明	进制数与特殊表示格式	说明
`%u`	无符号整数（unsigned）	`%o`	八进制
`%d`	整型（int）	`%x` `%X`	十六进制
`%ld`	长整型（long int）	`%e`	以指数形式表示浮点数
`%f`	单精度浮点型（float）	`%p`	指针的值（地址）
`%lf`	双精度浮点型（double）	`%s`	字符串
`%c`	字符（char）

标志（Flags）：常用的标志格式如下表所示

标志	中文名	说明
`-`	减号	在给定的字段宽度内左对齐，右边填空格（无减号的默认情况为右对齐，左边填空格）
`+`	加号	强制显示符号（正号或负号）
	空格	输出为正时加上空格，为负时加上负号
`#`	井号	类型为`o`、`x`、`X`时，增加前缀`0`、`0x`、`0X`（同scanf）
`0`	数字零	使用前导零填充字段宽度，若出现了减号或指定了精度则忽略该标记

宽度：控制显示字段的宽度（包括小数点、正负号）
精度：指定输出精度（保留n位小数）
类型长度：同scanf的两种字符

转义字符：在字符串中会被自动转换为相应的特殊字符，常用的如下表所示

转义字符	说明	转义字符	说明
`\n` `\r`	回车换行	`\\`	反斜杠符（`\`）
`\t`	水平制表符	`\'`	单引号符（`'`）
`\v`	垂直制表符	`\"`	双引号符（`"`）
`\b`	退格	`\ddd`	1~3位八进制数（`ddd`）所代表的字符
`\f`	走纸换页	`\xhh`	1~2位十六进制数（`hh`）所代表的字符
`\a`	鸣铃

B.4 文件操作

文件指针：FILE *fp;

文件的打开与关闭
- fopen("文件名", "操作方式")：打开数据文件。打开失败返回NULL，否则返回指向该文件的指针。操作方式及增强符见下表
- fclose(fp)：关闭数据文件。正常关闭返回O，否则返回1

操作方式	名称	说明
`r`	读（read）	文件必须已存在，只能读出已有文件
`w`	写（write）	文件已存在，则删除原文件再重建一个新文件从头写数据文件不存在，则以指定文件名建立该文件从头写数据
`a`	追加（append）	文件必须已存在，只能在已有文件未追加数据

增强符	名称	说明
`t`	文本文件（text）	`rt`、`wt`、`at`，可省略不写
`b`	二进制文件（binary）	`rb`、`wb`、`ab`
`+`	读和写	`r+`、`wb+`、…

读写字符/字符串
- fputc('字符', fp)：将1个字符写进文件
- fgetc(fp)：从文件中输出当前所指的1个字符，直接返回它
- fputs("字符串", fp)：将字符串写进文件
- fgets("字符串", n, fp)：从文件中输出当前所指的n - 1个字符+字符串结束标记'\0'，赋值给字符数组
读取连续的数据块（按二进制）
- fread(数据地址, 每次读写的字节数size, 读写次数count, fp)
- fwrite(数据地址, 每次读写的字节数size, 读写次数count, fp)
格式化读写数据
- fprintf(fp, "格式说明", [输出列表])：将输出列表按格式说明输出至文件
- fscanf(fp, "格式说明", [输入列表])：从文件中按格式说明输入至输入列表
文件位置相关函数
- feof(fp)：测试文件位置指针（文件当前读写位置）是否在文件末尾，是则返回1，否则返回0
- rewind(fp)：将文件位置指针拨回开头，无返回值
- fseek(fp, 位移量, 起始点)：将文件位置指针从指定的起始点按指定位移量（长整型，数值后需加L或l）移动。相关常量如下表所示

起始点常量	值	说明
`SEEK_SET`	0	文件开头
`SEEK_CUR`	1	当前位置
`SEEK_END`	2	文档末尾

获取⽂件⻓度 ftell(fp)：返回当前位置相对⽂件头的位移量，返回-1L表示出错。如下例所示

/* 求文件a.txt的长度 */
FILE *fp = fopen("a.txt", "r");
fseek(fp, 0L, 2);
int fileLength = ftell(fp);

读取打开文件的内容 read(待读取文件, 保存读取内容的缓冲区, 读取文件的长度len)：返回实际读取的字节数

综合大模型

控制台

实用工具

信息检索

其他资源

非常规搜索引擎

Hyplus服务

1 绪论

1.1 数据结构基础

1.2 算法与算法分析

2 线性表

2.1 顺序表

2.1.1 顺序表的存储结构

2.1.2 操作性能分析

2.2 单链表

2.2.1 单链表的存储结构

2.2.2 链表基本操作

2.2.3 操作性能分析

2.3 其他链表结构

2.3.1 双链表

2.3.2 循环链表

2.3.3 静态链表

3 栈与队列

3.1 栈

3.1.1 栈的存储结构

3.1.1.1 顺序栈

3.1.1.2 共享栈

3.1.1.3 链栈

3.1.2 栈的性质

3.1.3 栈的应⽤

3.1.3.1 表达式的转换

3.1.3.2 表达式的计算

3.1.3.3 括号匹配

3.1.3.4 递归

3.2 队列

3.2.1 队列的存储结构

3.2.1.1 顺序队

3.2.1.2 链队

3.2.2 循环队列的配置问题

3.2.3 队列的扩展与应用

3.2.3.1 双端队列

3.2.3.2 ⽤栈模拟队列

4 字符串

4.1 串的存储结构

4.2 模式匹配

4.2.1 暴⼒匹配算法

4.2.2 KMP算法

5 扩展线性表结构

5.1 数组

5.2 矩阵

5.2.1 特殊矩阵的压缩存储

5.2.2 稀疏矩阵的存储⽅法

5.3 广义表

5.3.1 广义表的重要概念

5.3.2 广义表的存储结构

6 树与二叉树

6.1 树的重要性质

6.2 二叉树

6.2.1 ⼆叉树的重要性质

6.2.2 ⼆叉树的存储结构

6.2.3 ⼆叉树的遍历

6.2.3.1 DFS非递归化

6.2.3.2 ⼆叉树的确定

6.2.4 线索⼆叉树

6.3 树与森林

6.3.1 树与森林的存储结构

6.3.2 树、森林与⼆叉树的转换

6.3.3 树与森林的遍历

6.4 树与二叉树的应用

6.4.1 表达式⼆叉树

6.4.2 哈夫曼树与哈夫曼编码

6.4.3 并查集

7 图

7.1 图的重要性质

7.2 图的存储结构

7.2.1 邻接矩阵

7.2.2 邻接表

7.2.3 其他存储结构

7.3 图的遍历

7.3.1 广度优先遍历

发表评论取消回复