「杂文」数据结构 C 语言严蔚敏版 OIer 速成指南（雾）-526互联

写在前面

上课天天在最后排看马娘 live 导致的。

还有五天考，简单翻阅一下。

对本书和本课的评价挂在最后。

针对 OIer 的个人向本书学习建议

首先略读又臭又长的绪论部分。
然后直接上手把以下比较陌生的章节的代码，按照给定形式实现一遍（以下给出了可测试对应代码的模板题）。
如果所在高校有对应的实验课的话，写写实验题即可。
将 OI 中并不常见的知识，或是写法与 OI 有所出入的部分进行一个习的学（以下使用（*）标出）。
因为本书质量实在是欠佳，而且若某高校还在采用本书作为教材那么教学水平也应该欠佳，为了照顾满头雾水的大部分学生，考试题目大概不会很难。
然后随便考考应该就能 90+ 了（确信）。

一绪论

呃呃呃。

太傻逼了。

要考这种傻逼东西我直接呃呃。

1.1

写的太无聊了。
而且上课直接跳了。

1.2 基本概念术语

就怕考这种傻逼东西。

数据
- 数据元素：作为整体进行考虑的基本单位。
- 数据项：数据的不可分割的最小单位。
- 数据对象：性质相同的数据元素的集合。
- 数据结构：相互间存在一种或多种特定关系的数据元素的集合。
  - 集合
  - 线性结构：一对一
  - 树形结构：一对多
  - 图状结构、网状结构：多对多
逻辑结构
物理结构/存储结构：数据结构在计算机中的表示，包括元素的表示和关系的表示。
- 数据元素的表示：
  - 位
  - 元素/结点：一个表示一个数据元素的位串。
  - 数据域：由若干数据项组成的未传中对应于各个数据项的子位串。
  元素或结点可以看成数据元素在计算机中的映像。
- 数据元素之间的关系：
  - 顺序映像 \(\rightarrow\) 顺序存储结构：借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。
  - 非顺序映像 \(\rightarrow\) 链式存储结构：借助只是元素存储地址的指针表示数据元素之间的逻辑关系。
数据类型
- 非结构的原子类型：值不可分解
- 结构类型：若干成分按照某种结构组成，可分解，成分可以是非结构的也可以是结构的。
抽象数据类型（ADT）
- 原子类型：值不可分解。（整数）
- 结构类型：
  - 固定聚合类型：值由确定数目的成分按照某种结构构成。（复数，由两个有序实数组成）
  - 可变聚合类型：值的成分的数目不确定。（有序可变长度整数序列）
- 抽象数据类型可表述为 \((D,S,P)\)，\(D\) 位数据对象，\(S\) 为 \(D\) 上的关系集，\(P\) 为对 \(D\) 的基本操作集。
- 本书定义抽象数据类型的格式：
```
ADT 抽象数据类型名 {
  数据对象：
  数据关系：
  基本操作：
} 抽象数据类型名
```
  - 数据对象和数据关系的定义通过伪代码描述。
  - 基本操作的定义格式：
```
基本操作名(参数表)  
  初始条件：
  操作结果：
```
    参数包括赋值参数（仅提供输入值）、引用参数（以 & 打头，提供输入值外还可返回操作结果）
- 多形数据类型：值的成分不确定的数据类型。

1.3 抽象数据类型的表示与实现

本书采用类 C 语言。
预定义常量和类型。
数据结构的表示用类型定义 typedef 描述。

基本操作的算法用以下形式函数描述：

函数类型 函数名(函数参数表) {
  //算法说明
  语句序列
} //函数名

以下常用语句及其表示略。

1.4 算法和算法分析

算法：对特定问题求解步骤的一种描述，是指令的有限序列，每一条指令表示一个或多个操作。
- 具有以下 5 个重要特性
- 有穷性：步骤有穷，每一步时间有穷。
- 确定性：每一条指令含义确切，输入相同输出相同。
- 可行性：算法中描述的操作都是可以通过已经实现的基本运算执行有限次得到。
- 输入
- 输出
算法的设计要求
- 正确性
- 可读性
- 健壮性：可处理非法输入数据。
- 效率与低存储量需求
算法效率的度量
- 时间复杂度
  - \(T(n) = O(f(n))\)
  - 语句的频度：该语句被重复执行的次数
- 空间复杂度
  - \(S(n) = O(f(n))\)
  - 原地工作：额外空间相对于输入数据量来说为常数。

二线性表

2.1 线性表的类型定义

2.2 线性表的顺序表示和实现

满足：

\[\begin{aligned} &\operatorname{location}(a_{i+1}) = \operatorname{location}(a_i) + \operatorname{length}\\ &\operatorname{location}(a_{i}) = \operatorname{location}(a_1) + (i-1)\times \operatorname{length} \end{aligned}\]

2.3 线性表的链式表示和实现

特点
- 用一组任意的储存单元存储线性表的数据元素。
- 对于每个数据元素来说，除了存储器本身的信息之外，还需存储一个指示其直接后继的信息。
- 数据域：存储数据元素信息的域。
- 指针域：存储直接后继的信息的域。
头结点：单链表的第一个结点之前附设的结点。
- 信息域：可为空，可存长度等。
- 指针域：指向线性表第一个元素结点的存储位置。
循环链表：表中最后一个结点的指针域指向头结点。
- 遍历中止条件变为后继是否为头结点。
双向链表：两个指针域，一个指向前驱，一个指向后继。
- 也可以构成双向循环链表。

三栈和队列

3.1 栈

略。

3.2 栈的应用举例

略。
想必大家早就写过了。

3.3 栈与递归的实现

调用函数和被调用函数之间的链接及信息交换需通过栈来进行。

3.4 队列

双端队列
链队列：用链表表示的队列。
- 需要两个分别指示队头和队尾的指针才能唯一确定。
- 空队列判断条件：头指针尾指针均指向头结点（空结点）。
循环队列：空间上的最后一个结点指向空间上的第一个结点。
- 空队列判断条件：头指针等于尾指针。
- 满队列判断条件：头指针在尾指针的下一位。

四串

4.1 串类型的定义

由零个或多个字符组成有序序列。

4.2 串的表示和实现

定长顺序存储表示
堆分配存储表示
串的块链存储表示：每个结点允许存放多个字符

4.3 串的模式匹配算法（*）

暴力 \(O(n^2)\) 略。
以下介绍该书中描述的 KMP 算法与 OI 中常见写法的不同。
规定
- 下文中将在主串 \(s\) 中匹配模式串 \(t\)。
- 串的下标从 1 开始。
- \(s[i:j]\) ：字符串 \(s\) 的子串 \(s_i\cdots s_j\)
- 真前/后缀：字符串 \(s\) 的真前缀定义为满足不等于它本身的 \(s\) 的前缀。同理就有了真后缀的定义：满足不等于它本身的 \(s\) 的后缀。
OI 中常见写法
- 以博主撰写的 KMP 笔记为例：https://www.cnblogs.com/luckyblock/p/14245452.html。
- 定义 \(\operatorname{border}\)：字符串 \(t\) 的 \(\operatorname{border}\) 定义为，满足既是 \(t\) 的真前缀，又是 \(t\) 的真后缀的最长的字符串，如 \(\texttt{aabaa}\) 的 \(\operatorname{border}\) 为 \(\texttt{aa}\)。
  
  \(\operatorname{fail}\)：模式串 \(t\) 的 \(\operatorname{fail}\) 是一个长度为 \(|t|\) 的整数数组，它又被称为 \(s\) 的失配指针。\(\operatorname{fail}_i\) 表示前缀 \(t[1:i]\) 的 \(\operatorname{border}\) 的长度，即：
  
  \[\operatorname{fail}_i = \max{\{ j \}},\, (j<i)\land(s[1,{\color{red}{j}}] = s[i-j+1, {\color{red}{i}}]) \]
  特别的，若不存在这样的 \(j\)，则 \(\operatorname{fail}_i = 0\)。如 \(\texttt{abaabcac}\) 的 \(\operatorname{fail} = \{0, 0, 1, 1, 2, 0, 1, 0\}\)。
- 加速匹配的原理为利用了当前已匹配的部分。若当前匹配到主串 \(s\) 的位置 \(i\)，已匹配的长度为 \(j\)，匹配模式串位置 \(j+1\) 失败，则利用 border 前后缀相等的特性，即可在失配时不必抛弃当前已匹配的部分，跳回到主串当前已匹配部分开头的下一个位置再从开头进行匹配。而是令已匹配长度 \(j = {\color{red}\operatorname{fail}_j}\) 再比较主串的当前位置 \(i\) 与模式串位置 \(\color{red}j+1\) 是否相等，重复该过程直至匹配成功或 \(j=0\)。
- 求 \(\operatorname{fail}\) 的方法是在模式串自身上运行 KMP 匹配算法，并将匹配到当前位时的最大匹配前缀的长度作为该位的 \(\operatorname{fail}\) 的值。
本书中给出的写法：
- 定义：\(\operatorname{next}\)：模式串 \(t\) 的 \(\operatorname{next}\) 是一个长度为 \(|t|\) 的整数数组，\(\operatorname{next}\) 代表模式串中第 \(i\) 个字符与主串中相应字符失配时，在模式串中需要重新和主串中该字符进行比较的字符的位置，有：
  
  \[\operatorname{next}_i = \max\{j\}, ({\color{red}1<}j<i)\land(s[1,{\color{red}{j - 1}}] = s[i-j+1, {\color{red}{i-1}}])\]
  特别的，规定 \(\operatorname{next}_1 = 0\)，除此之外，若不存在这样的 \(j\)，则 \(\operatorname{next}_i = 1\)。如 \(\texttt{abaabcac}\) 的 \(\operatorname{next} = \{0, 1, 1, 2, 2, 3, 1, 2\}\)。
  
  可以认为若 \(\operatorname{next}_i = k\)，则前缀 \(t[1:i-1]\) 的 \(\operatorname{border}\) 的长度为 \(k - 1\)。
- 加速匹配的原理类似。但是定义有所改变：设当前匹配到主串 \(s\) 的位置 \(i\)，已匹配的长度为 \(j-1\) 待匹配的位置为 \(j\)，且匹配模式串位置 \(j\) 失败，则失配时令待匹配位置 \(j = {\color{red}\operatorname{next}_j}\) 再比较主串的当前位置 \(i\) 与模式串位置 \(\color{red}j\) 是否相等，重复该过程直至匹配成功或 \(j=0\)。
- 求 \(\operatorname{next}\) 的方法同样是在模式串自身上运行 KMP 匹配算法，但是将匹配到当前位时即将要匹配的位置作为该位的 \(\operatorname{next}\) 的值。
两者除定义稍有不同外基本一致，复杂度显然均为 \(O(|s|+|t|)\) 级别，证明详见上述博文链接。
KMP 的改进算法：仅仅是根据模式串可能存在的连续相等的情况提出的一种常数优化，空间换时间的且效率提升一般，并且本书并没有给出形式化的定义，认为不考，略。

4.4 串操作应用举例

略。

五数组和广义表

5.1 数组的定义

略。

5.2 数组的顺序表示和实现

\(n\) 维数组含有 \(\prod_{i=1}^{n} b_i\) 个数据元素，第 \(i\) 维的下标的取值范围为 \([0, b_i - 1]\)。
\(n\) 维数组中，\(a_{j_1, j_2, \dots, j_n}\) 的存储地址满足：

\[\operatorname{location}(a_{j_1, j_2, \dots, j_n}) = \operatorname{location}(a_{0, 0, \dots, 0}) + \left(\sum_{i=1}^{n-1}j_i\prod_{k=i+1}^{n}b_k + j_n\right)\times \operatorname{length} \]

5.3 矩阵的压缩储存

对称/三角矩阵只存上/下三角，按照某个顺序原则将其压缩储存到一维数组中。
稀疏矩阵：只储存非零元。
- 稀疏因子：\(n\times m\) 的矩阵有 \(t\) 个元素非零：\(\delta = \frac{t}{n\times m}\)，通常认为 \(\delta\le 0.05\) 时矩阵稀疏。
- 三元组顺序表实现：\((i, j, a_{i, j})\)。
  - 实现矩阵转置。（咕咕咕）
  - 快速转置。
- 行逻辑链接的顺序表实现。
- 十字链表实现。

5.4 及之后

上课直接没讲。
略。

六树和二叉树

常识！

6.1 树的定义和基本术语

子树
结点：包含一个数据元素及若干指向其子树的分支。
结点的度：结点拥有的子树的个数。
叶子/终端结点：度为 0 的结点。
非终端结点/分支结点
树的度：树内各结点的度的最大值。
双亲/父亲
孩子
兄弟
堂兄弟
树的深度：树中结点的最大层次。
有序树、无序树
森林

6.2 二叉树

显然的结论：
- 第 \(i\) 层上至多有 \(2^{i-1}\) 个结点。
- 深度为 \(k\) 的二叉树至多有 \(2^{k}-1\) 个结点。
- 二叉树叶结点数为 \(n_0\)，度为 2 结点数为 \(n_2\)，则 \(n_0 = n_2 + 1\)。
满二叉树：深度为 \(k\) 且有 \(2^k - 1\) 个结点的二叉树。
完全二叉树：深度为 \(k\) 且至少有 \(2^{k-1}\) 个结点的二叉树。
- 叶节点只可能出现在 \(k\)、\(k-1\) 层。
- \(n\) 个结点的完全二叉树深度为 \(\left\lfloor\log_2 n\right\rfloor + 1\)。
- 对于第 \(i\) 个结点，其父亲为 \(\left\lfloor\frac{i}{2}\right\rfloor\)，左儿子为 \(2\times i\)，右儿子为 \(2\times i+1\)（如果存在）。

6.3 遍历二叉树和线索二叉树

先序遍历：根左右。
中序遍历：左根右。
后序遍历：左右根。

6.4 树和森林

双亲表示法
孩子表示法
孩子兄弟表示法
森林转化为二叉树 \(F = \{T_1, T_2, \dots, T_m\}\rightarrow B\)：
- \(F\) 为空则 \(B\) 为空。
- 否则 \(B\) 的根为 \(F\) 中第一棵树 \(T_1\) 的树根，左子树为去掉 \(T_1\) 的根节点后 \(T_1\) 形成的子树森林构成的二叉树，右子树为 \(\{T_2, T_3, \dots, T_m\}\) 构成的二叉树。
二叉树转化为森林 \(B \rightarrow F = \{T_1, T_2, \dots, T_m\}\)
- \(B\) 为空，则 \(T\) 为空。
- 否则 \(F\) 中第一颗树的根 \(T_1\) 根为 \(B\) 的根，\(T_1\) 根的子树森林为 \(B\) 的左子树转换形成的森林，\(\{T_2, T_3, \dots, T_m\}\) 为 \(B\) 的右子树转换形成的森林。
遍历森林：按照树的顺序进行单棵树的遍历。

6.5 树和等价关系

略。

6.6 赫夫曼树及其应用（*）

路径长度：路径上的分支数目。
树的路径长度：从树根到每个结点的路径长度之和。
带权路径长度：根节点到该节点路径长度与结点权值乘积。
树的带权路径长度 \(\operatorname{WPL}\)：树中所有叶子结点的带权路径长度之和。
赫夫曼树/最优二叉树：一棵有 \(n\) 个带权叶子结点的二叉树，且在所有树的形态中带权路径长度 \(\operatorname{WPL}\) 最短的二叉树。
赫夫曼算法贪心地构造赫夫曼树
- 给定 \(n\) 个叶子节点的权值 \(w_1, w_2\dots w_n\)。
- 首先利用给定条件构成 \(n\) 棵二叉树的集合 \(F = \{T_1, T_2, \dots, T_n\}\)，其中每棵二叉树仅有根节点且权值为对应权值。
- 每次选取两棵根节点权值最小的树作为左右子树构造一棵新的二叉树，新的二叉树根节点权值为选择的两棵树根节点权值之和，在 \(F\) 中删除被选择的两棵树并将新的二叉树加入 \(F\) 中。
- 重复上述过程直至只含一棵树。
赫夫曼编码
- 前缀编码：任一个编码都不是另一个编码的前缀。
- 出现次数为权值 \(w_i\)，编码长度为 \(l\)，构造出赫夫曼树。从根向叶节点移动，路径上向左儿子移动代表 0，向右儿子移动代表 1，构成的串即赫夫曼编码。