AcWing《考研算法辅导课》讲义
考纲：
一、线性表
（一）线性表的定义和基本操作
（二）线性表的实现
1. 顺序存储
2. 链式存储
3. 线性表的应用
二、栈、队列和数组
（一）栈和队列的基本概念
（二）栈和队列的顺序存储结构
（三）栈和队列的链式存储结构
（四）栈和队列的应用
（五）特殊矩阵的存储和压缩
三、树与二叉树
（一）树的基本概念
（二）二叉树
1. 二叉树的定义及其主要特征
2. 二叉树的顺序存储结构和链式存储结构
3. 二叉树的遍历
4. 线索二叉树的基本概念和构造
（三）树、森林
1. 树的存储结构
2. 森林与二叉树的转换
3. 树和森林的遍历
（四）树与二叉树的应用
1. 二叉排序树
2. 平衡二叉树
3. 哈夫曼（Huffman）树的哈弗曼编码
四、图
（一）图的基本概念
（二）图的存储及基本操作
1. 邻接矩阵法
2. 邻接表法
3. 邻接多重表、十字链表
（三）图的遍历
1. 深度优先搜索
2. 广度优先搜索
（四）图的基本应用
1. 最小（代价）生成树
2. 最短路径
3. 拓扑排序
4. 关键路径
五、查找
（一）查找的基本概念
（二）顺序查找法
（三）分块查找法
（四）折半查找法
（五）B树及其基本操作、B+树及其基本概念
（六）散列（Hash）表
（七）字符串模式匹配（KMP）
（八）查找算法的分析及应用
六、排序
（一）排序的基本概念
（二）插入排序
1. 直接插入排序
2. 折半插入排序
（三）起泡排序（bubble sort）
（四）简单选择排序
（五）希尔排序（shell sort）
（六）快速排序
（七）堆排序
（八）二路归并排序（merge sort）
（九）基数排序
（十）外部排序
（十一）各种内部排序算法的比较
（十二）排序算法的应用
第1讲 时间复杂度、矩阵展开
一、时间、空间复杂度
只考虑次数，不考虑常数。常见复杂度有：O(1)、O(n)、O(sqrt(n))、O(n^k)、O(logn)、O(nlogn)
考题：2011-1、2012-1、2013-1、2014-1、2017-1、2019-1
二、矩阵展开
矩阵的按行展开、按列展开，展开后下标从0开始。
数组公式
●假设a[i][];
●行优先: A0+ [i列+(j)1占用空间
●列优先: A0+[j行 +(i)]占用空间
中
考题：2016-4、2018-3、2020-1
第2讲 线性表
1. 将具有线性关系的数据存储到计算机中所使用的存储结构称为线性表。
2. 对于线性表中的数据来说，位于当前数据之前的数据统称为“前趋元素”，前边紧挨着的数据称为“直接前趋”；同样，后边的数据统称为“后继元素”，后边紧挨着的数据称为“直接后继”。
3. 线性表的分类
(1) 数据元素在内存中集中存储，采用顺序表示结构，简称“顺序存储”；
例如：数组
(2) 数据元素在内存中分散存储，采用链式表示结构，简称“链式存储”。
例如：单链表、双链表、循环单（双）链表
4. 不同实现方式的时间复杂度（不要硬背结论、要从实现方式入手分情况讨论，下述为特定情况下的时间复杂度）
(1) 数组：随机索引O(1)、插入O(n)、删除O(n)
(2) 单链表：查找某一元素O(n)、插入O(1)、删除O(n)
(3) 双链表：查找某一元素O(n)、插入O(1)、删除O(1)
5. 考题：2016-1、2016-2、2012-42、2015-41、2019-41
6. 押题：AcWing 34、AcWing 1451
第3讲 栈与队列
1. 栈和队列的基本概念
2. 栈和队列的顺序存储结构
(1) 栈：栈顶元素位置：指向最后一个元素、指向最后一个元素的下一个位置
(2) 队列：一般采用循环队列。
(a) 队头元素位置：指向第一个元素、指向第一个元素的前一个位置。
(b) 队尾元素位置：指向队尾元素、指向队尾元素的下一个位置。
3. 栈和队列的链式存储结构
4. 栈和队列的应用
(1) 栈的应用：表达式求值（中缀表达式转后缀表达式、括号匹配）、DFS
(2) 队列的应用：BFS
- 考题：2011-2、2011-3、2012-2、2013-2、2014-2、2014-3、2015-1、2016-3、2017-2、2018-1、2018-2、2019-42、2020-2
- 押题：AcWing 3302
第4讲 树的基本概念、二叉树、树和森林
1. 树的基本概念
(1) 树是由
根节点和若干颗子树构成的。树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的节点，所定义的关系称为父子关系。父子关系在树的节点之间建立了一个层次结构。在这种层次结构中有一个节点具有特殊的地位，这个节点称为该树的根节点，或称为树根。(2) 空集合也是树，称为空树。空树中没有节点；
(3) 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；
(4) 节点的度：一个节点含有的
子节点的个数称为该节点的度；(5) 叶节点或终端节点：
度为0的节点称为叶节点；(6) 非终端节点或分支节点：
度不为0的节点；(7) 双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；
(8) 兄弟节点：具有相同父节点的节点互称为兄弟节点；
(9) 树的度：一棵树中，最大的节点的度称为树的度；
(10) 节点的层次：从根开始定义起，
根为第1层，根的子节点为第2层，以此类推；
(11) 树的高度或深度：树中节点的最大层次；(12) 节点的祖先：从根到该节点
所经分支上的所有节点；(13) 子孙：以某节点为根的子树中任一节点都称为该节点的子孙；
(14) 森林：由棵互不相交的树的集合称为森林。
2. 二叉树
(1) 二叉树的定义及其主要特征
a. 二叉树的基本形态：空二叉树、单节点二叉树、左子树、右子树
b. 性质：
[1] 在非空二叉树中，第i层上至多== $2^{i-1}$ ==个结点。
[2] 深度为k的二叉树至多有$2^{k}-1$个结点
[3] 对任何一棵二叉树，若其叶子结点数为n0，度为2的结点数为n2，则n0 = n2 + 1。
[4] n个结点的完全二叉树深度为：log2(n)向下取整 + 1。
[5] 二叉树的堆式存储: 节点p的左儿子:2x，右儿子：2x+1。
c. 两种特殊的二叉树
[1] 满二叉树：一颗深度为k且有2^k-1个结点的二叉树
[2] 如果深度为k,有n个结点的二叉树，当且仅当其每个结点都与深度为k的满二叉树中编号从1到n的结点一一对应，该二叉树称为完全二叉树
(2) 二叉树的顺序存储结构和链式存储结构
(3) 二叉树的遍历
a. 前序遍历
b. 中序遍历
c. 后序遍历
d. 根据前序 + 中序重建二叉树（AcWing 18)
(4) 线索二叉树的基本概念和构造
对二叉树节点的指针域做如下规定：
a. 若节点有左孩子，则Lchild指向左孩子，否则指向直接前驱；右孩子同理；
b. 增加两个标志域，Ltag表示指向的是子节点还是前驱；Rtag同理
c. 指向前驱和后继的指针叫做线索。按照某种次序遍历，加上线索的二叉树称之为线索二叉树
3. 树、森林
(1) 树的存储结构
a. 只存父节点
b. 邻接表存储所有子节点
c. 左儿子右兄弟
(2) 森林F与二叉树T的转换
a. 原树中叶子节点数 = 转换后的树中有右儿子的节点数 + 1
b. F的前序遍历就是T的前序遍历
c. F的后序遍历就是T的中序遍历
(3) 树和森林的遍历
a. 前序遍历
b. 后序遍历
- 考题：2011-4、2011-5、2011-6、2012-3、2013-5、2014-4、2014-5、2014-41、2015-2、2016-5、2016-42、2017-4、2017-5、2018-4、2019-2、2020-3、2020-4
- 押题：AcWing 18、AcWing 19
第5讲 二叉排序树、平衡树、表达式树
1. 二叉排序树
2. 平衡树——AVL
(1) 定义：满足如下条件的树：
a. 是二叉查找树
b. 每个节点的左子树和右子树的高度差最多为1
(2) 平衡因子：一个结点的左子树的高度减去右子树的高度，可取-1、0、1三种值
(3) 平衡操作
3. 表达式树
- 考题：2011-7、2012-4、2013-3(PDF中的分析有误，以上课讲解为准)、2013-6、2015-4、2018-6、2019-4、2019-6、2020-5、2017-41
第6讲 Huffman编码和Huffman树
1. Huffman编码和Huffman树
(1) Huffman编码
a. 前缀编码: 是指对字符集进行编码时，要求字符集中任一字符的编码都不是其它字符的编码的前缀。
b. 树的带权路径长度(WPL)
c. 构造过程
(2) Huffman树
(3) 应用
- 考题：2012-41、2013-4、2014-6、2015-3、2017-6、2018-5、2019-3、2020-42
第7讲 图的基本概念、存储、遍历、拓扑排序
1. 图的基本概念
(1) 有向图、无向图
(2) 度数（出度、入度）
(3) 简单图：不存在顶点到其自身的边，且同一条边不重复出现
(4) 路径、环、简单路径
(5) 无向完全图：任意两个顶点之间都存在边，有n个顶点的无向完全图有 n × (n - 1) / 2条边
(6) 有向完全图：任意两个顶点之间都存在方向护卫相反的两条弧，有n个顶点的无向完全图有 n × (n - 1) 条弧
(7) 稀疏图&稠密图：有很少条边或弧的图称为稀疏图，反之称为稠密图，相对的概念。
2. 图的存储及基本操作
(1) 邻接矩阵：适用于稠密图，可存有向图、无向图。常用。空间复杂度：O(n^2)。无法存重边。
(2) 邻接表：适用于稀疏图，可存有向图、无向图。常用。空间复杂度：O(n + m)。可存重边。
(3) 邻接多重表，适用于稀疏图，可存无向图。不常用。空间复杂度：O(n + m)。可存重边。
(4) 十字链表，适用于稀疏图，可存有向图、无向图。不常用。空间复杂度：O(n + m)。无法存重边
(5) 三元组表，适用于稀疏图，可存有向图，无向图。常用于Bellman-Ford算法、Kruskal算法。空间复杂度：O(m)。可存重边。
3. 图的遍历
(1) 深度优先搜索。邻接表存储的时间复杂度：O(n + m)。邻接矩阵存储的时间复杂度：O(n^2)
(2) 广度优先搜索。邻接表存储的时间复杂度：O(n + m)。邻接矩阵存储的时间复杂度：O(n^2)
4. 拓扑排序
- 考题：2011-8、2012-5、2012-6、2013-7、2013-8、2014-7、2015-5、2016-6、2016-7、2017-3、2017-7、2018-7、2020-6
第8讲 最小生成树、最短路、关键路径
1. 最小生成树
(1) Prim
(2) Kruskal
2. 最短路
(1) 单源最短路 Dijkstra
(2) 多源汇最短路 Floyd
3. 关键路径
- 考题：2011-41、2012-7、2012-8、2013-9、2015-6、2015-42、2016-8、2017-42、2018-42、2019-5、2020-7、2020-8
第9讲 基本概念、顺序、折半、分块查找法、B/B+树
1. 查找的基本概念
(1) 平均查找长度 ASL = 每个元素 查找概率 * 找到第i个元素需要进行的比较次数 的和。
(2) 决策树(判定树)
2. 顺序查找法
(1) 一般线性表的顺序查找
a. 若每个元素查找概率相同，则 ASL(成功) = (1 + 2 + ... + n) / n = (n + 1) / 2
b. ASL(失败) = n或n+1，取决于代码写法。
(2) 有序表的顺序查找
a. 若每个元素查找概率相同，则 ASL(成功) = (1 + 2 + ... + n) / n = (n + 1) / 2
b. ASL(失败) = (1 + 2 + ... + n + n) / (n + 1) = n / 2 + n / (n + 1)
3. 折半查找法
(1) ASL = log(n + 1) - 1
4. 分块查找法
设共n个元素，每块s个元素，共b = n / s块。块内无序，块间有序。
(1) 顺序查找确定块：ASL(成功) = (s^2 + 2s + n) / (2s)，s = sqrt(n)时取最小值
(2) 二分查找确定块：log(n/s + 1) + (s - 1)/2
5. B树及其基本操作、B+树及其基本概念
(1) B树
[1] m阶B树，每个节点最多有m个孩子。
[2] 每个节点最多有m-1个关键字（可以存有的键值对）。
[3] 根节点最少可以只有1个关键字。
[4] 非根节点至少有m/2个关键字。
[5] 每个节点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它。
[6] 所有叶子节点都位于同一层，或者说根节点到每个叶子节点的长度都相同。
[7] 每个节点都存有索引和数据，也就是对应的key和value。
[8] 所以，根节点的关键字数量范围：1 <= k <= m-1，非根节点的关键字数量范围：m/2 <= k <= m-1。
(2) B+树
[1] B+跟B树不同B+树的非叶子节点不保存关键字记录的指针，只进行数据索引，这样使得B+树每个非叶子节点所能保存的关键字大大增加；
[2] B+树叶子节点保存了父节点的所有关键字记录的指针，所有数据地址必须要到叶子节点才能获取到。所以每次数据查询的次数都一样；
[3] B+树叶子节点的关键字从小到大有序排列，左边结尾数据都会保存右边节点开始数据的指针。
(3) 参考链接：https://blog.csdn.net/Fmuma/article/details/80287924
- 考题：2011-42、2012-9、2013-10、2013-42、2014-9、2015-7、2016-9、2016-10、2017-8、2017-9、2018-8、2020-10
第10讲 散列（Hash）表、字符串模式匹配（KMP）
1. 散列（Hash）表
(1) 负载因子
(2) 哈希函数
[1] 除余法 h(x) = x % M
[2] 乘余取整法 h(x) = floor(n * (A * x的小数部分))
[3] 平方取中法 先平方，然后取中间几位
[4] 基数转换法 换成其他进制，然后取其中几位
[5] ELFhash字符串
(3) 解决冲突的方式
[1] 开散列方法（拉链法）
[2] 闭散列方法（开放寻址法）
聚集和二级聚集
a. 线性探查法 d(i) = (d(0) + i * c) % M。易产生聚集问题。
b. 二次探查法。易产生二级聚集问题。
d(2i - 1) = (d(0) + i^2) % M
d(2i) = (d(0) - d ^2) % M
c. 随机探查法。易产生二级聚集问题。
d. 双散列探查法
2. 字符串模式匹配（KMP）
- 考题：2011-9、2014-8、2015-8、2018-9、2018-41、2019-8、2019-9
第11讲 基本概念、插入、冒泡、选择、希尔、快速、堆、归并排序
1. 排序的基本概念
(1) 内排序和外排序
(2) 算法的稳定性
2. 插入排序
(1) 直接插入排序
a. 时间复杂度
[1] 最好情况：O(n)
[2] 平均情况：O(n^2)
[3] 最坏情况：O(n^2)
b. 辅助空间复杂度
O(1)
c. 稳定
(2) 折半插入排序
a. 时间复杂度
[1] 最好情况：O(n)
[2] 平均情况：O(n^2)
[3] 最坏情况：O(n^2)
b. 辅助空间复杂度
O(1)
c. 稳定
3. 冒泡排序（bubble sort）
(1) 时间复杂度
a. 最好情况：O(n)
b. 平均情况：O(n^2)
c. 最坏情况：O(n^2)
(2) 空间复杂度
O(1)
(3) 稳定
4. 简单选择排序
(1) 时间复杂度
a. 最好情况：O(n^2)
b. 平均情况：O(n^2)
c. 最坏情况：O(n^2)
(2) 空间复杂度
O(1)
(3) 不稳定
5. 希尔排序（shell sort）
(1) 时间复杂度
O(n^(3/2))
(2) 空间复杂度
O(1)
(3) 不稳定
6. 快速排序
(1) 时间复杂度
a. 最好情况：O(nlogn)
b. 平均情况：O(nlogn)
c. 最坏情况：O(n^2)
(2) 空间复杂度
O(logn)
(3) 不稳定
7. 堆排序
(1) 时间复杂度
a. 最好情况：O(nlogn)
b. 平均情况：O(nlogn)
c. 最坏情况：O(nlogn)
(2) 空间复杂度
O(logn)
(3) 不稳定
8. 二路归并排序（merge sort）
(1) 时间复杂度
a. 最好情况：O(nlogn)
b. 平均情况：O(nlogn)
c. 最坏情况：O(nlogn)
(2) 空间复杂度
O(n)
(3) 稳定
第12讲 桶排序、基数排序、外部排序
1. 桶排序
(1) 时间复杂度
a. 最好情况：O(n + m)
b. 平均情况：O(n + m)
c. 最坏情况：O(n + m)
(2) 空间复杂度
O(n + m)
(3) 稳定
2. 基数排序
(1) 时间复杂度
a. 最好情况：O(d(n + r))
b. 平均情况：O(d(n + r))
c. 最坏情况：O(d(n + r))
(2) 空间复杂度
O(n + r)
(3) 稳定
3. 外部排序
(1) 置换选择排序
(2) 归并排序
a. 胜者树
b. 败者树
c. huffman树
- 考题：2011-10、2011-11、2012-10、2012-11、2013-11、2014-10、2014-11、2015-9、2015-10、2015-11、2016-11、2016-43、2017-10、2017-11、2018-10、2018-11、2019-7、2019-10、2019-11、2020-9、2020-11、2020-41
第21讲 红黑树和并查集
1. 红黑树
1.1 定义
(1) 结点是红色或黑色。
(2) 根结点是黑色。
(3) 所有叶子都是黑色。（叶子是NIL结点）
(4) 每个红色结点的两个子结点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色结点）
(5) 从任一节结点其每个叶子的所有路径都包含相同数目的黑色结点。
1.2 性质
从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。
1.3 平衡操作
1.3.1 插入
1.3.1.1 被插入的节点是根节点。
直接把此节点涂为黑色。
1.3.1.2 被插入的节点的父节点是黑色。
什么也不需要做。
1.3.1.3 被插入的节点的父节点是红色。
[1] 当前节点的祖父节点的另一个子节点（叔叔节点）也是红色。
(1) 将“父节点”设为黑色。
(2) 将“叔叔节点”设为黑色。
(3) 将“祖父节点”设为“红色”。
(4) 将“祖父节点”设为“当前节点”(红色节点)；即，之后继续对“当前节点”进行操作。
[2] 叔叔节点是黑色，且当前节点是其父节点的右孩子
(1) 将“父节点”作为“新的当前节点”。
(2) 以“新的当前节点”为支点进行左旋。
[3] 叔叔节点是黑色，且当前节点是其父节点的左孩子
(1) 将“父节点”设为“黑色”。
(2) 将“祖父节点”设为“红色”。
(3) 以“祖父节点”为支点进行右旋。
1.3.2 删除
1.3.2.1 x指向一个"红+黑"节点。
将x设为一个"黑"节点即可。
1.3.2.2 x指向根。
将x设为一个"黑"节点即可。
1.3.2.3
[1] x的兄弟节点是红色。
(1) 将x的兄弟节点设为“黑色”。
(2) 将x的父节点设为“红色”。
(3) 对x的父节点进行左旋。
(4) 左旋后，重新设置x的兄弟节点。
[2] x的兄弟节点是黑色，x的兄弟节点的两个孩子都是黑色。
(1) 将x的兄弟节点设为“红色”。
(2) 设置“x的父节点”为“新的x节点”。
[3] x的兄弟节点是黑色；x的兄弟节点的左孩子是红色，右孩子是黑色的。
(1) 将x兄弟节点的左孩子设为“黑色”。
(2) 将x兄弟节点设为“红色”。
(3) 对x的兄弟节点进行右旋。
(4) 右旋后，重新设置x的兄弟节点。
[4] x的兄弟节点是黑色；x的兄弟节点的右孩子是红色的，x的兄弟节点的左孩子任意颜色。
(1) 将x父节点颜色 赋值给 x的兄弟节点。
(2) 将x父节点设为“黑色”。
(3) 将x兄弟节点的右子节设为“黑色”。
(4) 对x的父节点进行左旋。
2. 并查集
2.1 定义
用森林维护集合关系，支持合并、查询等操作。
2.2 优化
(1) 路径压缩
(2) 按秩合并
