考试周捋一捋数据结构的知识点，我的学校（BIT）的数据结构包含：数据结构、算法设计、计算理论。
本次考试已然转为线上，不擅长线上考试的我现如今看淡分数了，知识学到家才是最重要的。
本文内容就是无脑捋目录，会加杂些网络资源，就不放文档资源了（但是无耻搬运了一些内容，但很少✿(。◕ᴗ◕。)✿）。
有些错别字请理解一下，比如“结点”单独打出来是可以的，但是如果打一整句话就会变成“节点”。
数据结构
2 线性表
2.1 线性表
2.1.1 线性表的定义和特点：
线性表是一种最简单的线性结构，线性结构一个数据元素的有序集。它的特点就是每个关键元素（头、尾、前驱、后继）都是唯一的，而且每个元素特性相同。
2.1.2 线性表的主要操作：
略
2.2 顺序表
2.2.1 顺序表的定义与特点：
一段顺序的地址来存储
2.2.2 顺序表的结构定义：
分为静态定义和动态定义，静态定义是定长的，动态定义可以增加长度（也就是在结构中记录长度，地址就往下用呗）。
2.2.3 顺序表查表操作的实现：
略
2.2.4 顺序表插入和删除操作的实现：
略
2.2.5 顺序表的应用：集合运算：
没必要看
2.3 单链表（重点）
2.3.1 单链表的定义和特点：
链表是用一组任意的存储单元来存放线性表的元素，这组存储单元既可以是连续的，也可以是不连续的。
存储数据元素信息的域称作数据域；存储后继元素存储位置的域称作指针域，指针域中存储的信息称指针或链。
链表的每个结点中只包含一个指针域，故将这种链表称为单链表。
2.3.2 单链表的结构定义：
特点和线性表一样，静态定义限制了长度（很少用，基本没用过），动态定义则没有对长度的限制（是我们所熟知的链表定义）。
2.3.3 单链表的插入与删除：
略
2.3.4 带头结点的单链表：
就是头节点不存东西，而且有一个专门的变量存储头节点的地址。统一了空表与非空表的操作，使得插入与删除更简单了。
2.3.5 单链表的建立与创建：
略
2.3.6 单链表的应用：集合运算：
没必要看
2.3.7 循环链表：
就是尾接头，如果是带头结点的，那么尾接到头节点就行（描述一下结构，没别的意思，为了遏制尾接到有实参的第一个节点的怪操作）。
2.3.8 双向链表：
略
2.3.9 静态链表：
开两个数组（数据类型），一个存数据，另一个存数据对应的index。（我没细看）
2.4 顺序表与线性链表的比较
在这里接触了时间复杂度的大欧表示法，这里可以粗浅地把大欧表示法理解为最坏情况的同类操作的执行次数，比如删除顺序表的第一个元素，要更改全部n个元素的值，所以复杂度为\(O(n)\)。
2.5 线性表的应用：一元多项式及其运算
没啥意思，也不过多展开了。
3 栈和队列（重点）
3.1 栈
3.1.1栈的概念：
栈(Stack)是只允许在一端进行插入或删除操作的线性表。首先栈是一种线性表，但限定这种线性表只能在某一端进行插入和删除操作。
3.1.2 顺序栈：
借助一维数组（数据类型）来实现栈。
3.1.3 扩展阅读：多栈处理：
两个栈：首尾开凿法
多个栈：使用栈浮动技术，栈i满，先后向左右找空栈，找到则向其所属的那一侧移动，为栈i腾出空间。评价是没啥用，为了一点点空间牺牲了巨大的时间成本。
3.1.4 链式栈：
要存头尾指针。
3.1.5 拓展阅读：栈的混洗
固定的一些元素都经历进退栈后得到的推展序列的可能情况，排列组合问题。
一般地，设有n个元素按序号1,2,...,n进栈，轮流让1在退栈序列的第1,2,...,n位，则可能的退栈序列数为
\(m_{n}= \sum_{i=0}^{n} m_{i} m_{n-i-1}=\frac{1}{n+1} C_{2n}^{n} = \frac{2n(2n-1) \cdots (n+2) }{n!}\)3.2 队列：
3.2.1 队列的概念：
队列(Queue)简称队，也是一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除。
3.2.2 循环队列：
如果想存储顺序栈一样存储队列，若不加维护，那么front会上浮直到和rear一起浮到最末。循环队列是一种维护方法，记录数组（数据类型）长度进行取余，它通过模加法的方式使数组头尾相连，无限上浮，解决了上浮的问题。
3.2.3 链式队列：
要存头尾指针。
3.3 栈的应用
3.3.1 数制转换：
略
3.3.2 括号匹配：
略
3.3.3 表达式的计算与优先级处理：
略
3.3.4 栈与递归的实现：
略
3.4 队列的应用
略
3.6 拓展阅读：双端队列
3.6.1 双端队列的概念：
双端队列为普通队列开放了两个接口，一个是队首插入，一个是队尾删除，满足一个及以上接口的队列即为双端队列。
3.6.2 输入受限的双端队列：
就是只实现了队尾删除一个接口的队列。
3.6.3 输出受限的双端队列：
就是只实现了队首插入一个接口的队列。
3.6.4 双端队列的存储表示：
使用循环存储或者链式存储，不赘述了。
4 数组、串和广义表
4.1 数组
说明：这里的数组是数据结构而非数据类型。
数组是由n(n≥1)个相同类型的数据元素构成的有限序列，每个数据元素称为一个数组元素，每个元素在个线性关系中的序号称为该元素的下标，下标的取值范围称为数组的维界。
数组与线性表的关系：数组是线性表的推广。一维数组可视为一个线性表；二维数组可视为其元素也是定长线性表的线性表，以此类推。数组一旦被定义，其维数和维界就不再改变。因此，除结构的初始化和销毁外，数组只会有存取元素和修改元素的操作。
4.1.1 一维数组：
以一维数组A[0…n-1]为例，其存储结构关系式为LOC(ai)=LOC(a0)+i×L (0≤i<n)。其中，L是每个数组元素所占的存储单元。
4.1.2 二维数组：
有两种映射方法：按行优先和按列优先。以二维数组为例，按行优先存储的基本思想是：先行后列，先存储行号较小的元素，行号相等先存储列号较小的元素。设二维数组的行下标与列下标的范围分别为[0，h1]与[0，h2],则存储结构关系式为LOC(a_{i,j})=LOC(a_{0,0})+[i×(h_2+1)+j]×L与LOC(a_{i,j})=LOC(a_{0,0})+[j×(h_1+1)+i]×L。
4.2 特殊矩阵的压缩存储
4.2.1 对称矩阵的压缩矩阵：
在这里为了方便说明选用按行优先存储，只存储下半三角，那么直观上看我们存储的元素都是i是大于等于j的。但是\(a_{m,n}=a_{n,m}\)这样相当于存储了整个矩阵。
很容易就可以推出对应的索引函数\(\begin{eqnarray}k=\begin{cases}\frac{i(i-1)}{2}+j-1& i\ge j\\\frac{j(j-1)}{2}+i-1& i\le j\end{cases}\end{eqnarray}\)唉敲公式太麻烦了先不敲了，有机会补。
如果本身就是三角矩阵，还是一样的存储方式，不过常数的那一半要单独存储，通常到最末尾。
4.2.2 三对角矩阵的压缩存储：
逐行存储或逐列存储，注意，三对角矩阵的第一行和最后一行都只有两个元素，推导索引函数的时候不要忘了。
4.3 稀疏矩阵
4.3.1 稀疏矩阵的概念：
矩阵中非零元素的个数t，相对矩阵元素的个数s来说非常少，即s>>t的矩阵称为稀疏矩阵。例如，一个矩阵的阶为100×100，该矩阵中只有少于100个非零元素。
4.3.2 稀疏矩阵的顺序存储表示：
若采用常规的方法存储稀疏矩阵，则相当浪费存储空间，因此仅存储非零元素。但通常零元素的分布没有规律，所以仅存储非零元素的值是不够的，还要存储它所在的行和列。因此，将非零元素及其相应的行和列构成一个三元组（行标，列标，值）。然后按照某种规律存储这些三元组。稀疏矩阵压缩存储后便失去了随机存取特性。
除了三元组顺序表之外，还有行逻辑链接顺序表。
4.3.3 稀疏矩阵的链表表示：
简单链式存储
4.5 广义表
4.5.1 广义表的概念：
广义表是一种不同构的数据结构\(LS=(\alpha_{1} ,\alpha_{2},\dots,\alpha_{n})\)。其中\(\alpha_{i}\)为原子或者广义表。
4.5.2 广义表的性质：
广义表的定义是一个递归定义，在描述广义表的时候又用到了广义表。在线性表中数据元素是单个元素，而在广义表中，元素可以是单个元素称为原子，也可以是广义表，称为广义表的子表。当每个元素均为原子且类型相同时，就是线性表。
4.5.3 广义表的链接表示（次要）：
这么好出题的东西竟然是次要。
头尾链表结构
拓展线型链表表示
5. 树与二叉树
5.1 树的基本概念
5.1.1 树的定义和术语：
每棵非空树都由一个根结点和它的子（非空）树组成（子树数量可为零）。
每棵子树的根节点有且仅有一个直接前趋（即它的上层结点），但可以有0个或多个直接后继（即它的下层结点）。称（非空）子树的个数为其根节点的分支数。
树有很多种表示方法，比如示意图、目录结构表示、集合文氏图表示、凹入表表示、广义表表示等。
结点：由单个字母表示，包含值以及指向其它结点的分支指针。
结点的度：指节点所拥有的（非空）子树棵数。（以后说子树就都是非空的了）
叶结点：即度为零的点。
分支结点：除叶结点外的其他节点，又称为终端结点。
子女结点：子树的根结点。
双亲结点：某个子树根节点的直接前趋为该根节点的双亲节点。
兄弟结点：同一双亲的子女互称为兄弟。
祖先结点：从该节点到整棵树的根节点所经分支上的所有节点。真祖先不包括该结点本身。
子孙结点：以该节点为根节点的树的所有节点。真子孙不包括该节点本身。如果不加说明，所谓“子孙”都指真子孙。
结点间的路径：从某节点到另一节点所经历的所有节点（包括端点）。
结点的深度：即结点所在层次，简称节点的层次，某节点的深度是根节点到该节点间的路径的结点数。
节点的高度：空树的高度为零，叶节点的高度为一，非叶结点的高度等于他子女节点高度中的最大值加一。
树的深度：树中距离根节点最远的结点所处层次，也就是一棵树中节点的深度的最大值。
树的高度：根节点的高度。注意：树的高度与树的深度的值相等，但高度与深度计算的方向不同。
树的宽度：树中一层的最大结点数。
树的度：树中节点的度的最大值。
有序树：树中节点的各棵子树是有次序的。
无序树：树中各节点的各棵子树之间的次序是不重要的，可以互相交换位置。
森林：是m棵树的集合。
5.1.2 树的基本操作：
略
5.2 二叉树及其存储表示（重点）
5.2.1 二叉树的概念：
二叉树是度小于等于二的树，这样好理解。
书上说二叉树不是树，说是在图论中树被视作n-1条边连接n的定点的特殊的图，顶点非空；而图论中N叉树可以是空树，二叉树属于N叉树。并且二叉树严格分左右，而树不是这样。
5.2.2 二叉树的性质：
性质1：在二叉树的第\(i(i\ge 1)\)层最多有\(2^{i-1}\)个节点。
性质2：深度为\(k(k \ge 0)\)的二叉树最少有\(k\)个节点，最多有\(2^{k}-1\)个节点。
性质3：对于任意一棵非空二叉树，若其叶子结点数为\(n_{0}\)，度为2的非叶子结点数为\(n_{2}\)，则\(n_{0}=n_{2}+1\)。
满二叉树：每一层的节点都达到了最大个数的二叉树。
完全二叉树：如果一棵具有n个节点的深度为k的二叉树，它的每一个节点都与高度为k的满二叉树中编号为1~n的节点一一对应，则称这棵二叉树为完全二叉树。其特点是：上面从第1层到第k-1层的所有各层的结点数都是满的，仅最下面第k层或是满的，或从右向左连续缺失若干结点。
性质4：具有n个节点的挖完全二叉树的深度为\(\left \lceil \log_{2}(n+1) \right \rceil\)。
性质5：如果将一棵有n个节点的完全二叉树自顶向下，同一层自左向右连续给节点编号1,2,...,n，然后按此结点编号将树中各节点顺序地存放于一个一维数组中，并简称编号为i的节点为节点\(i(1\le i \le n)\)。则有以下关系：
若i=1则为根，则无双亲，反之i的双亲为节点\(\left \lfloor i/2 \right \rfloor\)
若\(2i\le n\)，则节点i的左子女为节点2i。
若\(2i+1 \le n\)，则节点i的右子女为节点2i+1。
若i为奇数，且\(i\ne 1\)，它处于右兄弟位置，则它的左兄弟为节点i-1。
若i为偶数，且\(i\ne n\)，它处于左兄弟位置，则它的右兄弟为节点i+1。
节点i所在的层次为\(\left \lfloor \log_{2}i \right \rfloor+1\)。
5.2.3 二叉树的主要操作：
略
5.2.4 二叉树的顺序存储表示：
如果是完全二叉树，就直接按序号存储，运用性质5推导出index公式进行二叉树的操作。注意数组是自0起的。
如果是一般二叉树，为了能够在操作上更加简便，也要像完全二叉树那样存，把没有的位置空出来即可。
5.2.5 二叉树的链表存储表示：
略
5.3 二叉树的遍历（重点）
5.3.1 二叉树遍历的递归算法：
略
5.3.2 递归遍历算法的应用举例：
略
5.3.3 二叉树遍历的非递归算法：
略
5.3.4 利用队列实现二叉树的层次序遍历：
略
5.3.5 非递归遍历算法的应用举例：
略
5.3.6 二叉树的计数：
和栈的混洗是一样的。这里会涉及通过遍历序列确定唯一二叉树的问题。能确定唯一一棵二叉树的序列组合如下：先序&中序、中序&后序、中序&层次、中序&各结点所处层次、中序&各节点左子女、中序&各节点的右子女、先序&各节点的右子女、后序&各节点的左子女。
对于二叉树的计数，还有一种问题就是通过一种序列可以确定多少棵不同的二叉树。这方面的题我还没做过，对于重要性暂时无法评估，后序会留意一下。递推公式是超纲的，就不写了。
5.4 线索二叉树
5.4.1 线索二叉树的概念：
在二叉树中加入指向某种特定序列的前趋/后继的指针，每个节点会增加两个指针域。
5.4.2 线索二叉树的种类：
每种遍历序列都对应着一种线索二叉树。
5.4.3 中序线索二叉树的建立和遍历：
类似遍历时的算法，不过要保存下指针。
5.4.4 先序与后序线索二叉树：
略
5.5 树与森林
5.5.1 树的存储表示：
双亲表示法：使用线性表存储，一个节点有两个域，一个存放值，另一个存放该节点的双亲的index。
子女链表表示法：设置一个线性表，一个节点有两个域，一个存放值，一个存放指针，指针指向的节点是其子女的index，该节点具有一个指针，指向带有下一个子女index的节点。
广义表表示法：最直观的存储方法之一。
子女-兄弟链表表示法：一个节点有三个域，一个存储值，一个存储兄弟，一个存储子女，这样的节点编织成的网可以完整表达一棵树。
5.5.2 森林与二叉树的转换：
树、森林转换为二叉树
二叉树节点本身就是一个三域节点，通过数据抽象可以模拟树和森林。左子树代表第一个子女，右子树代表第一个兄弟就可以表示出来，很像“子女-兄弟链表表示法”。
二叉树转换为树和森林
逆操作，将兄弟链断开接到共同双亲上，将子女链拆散连到一起。
5.5.3 树与森林的深度优先遍历：
对于树的深度优先遍历，只要在先序和后序两种方法中选其一即可。
对于森林的深度优先遍历，就是一棵一棵地遍历，不过在书中写到的深度优先遍历有先序和中序两种，不知道为啥。另外，森林按照本文方法转换成二叉树直接先序和中序遍历，得到的遍历序列与遍历森林得到的序列相同。
5.5.4 树与森林的广度优先遍历：
注意森林的广度优先遍历不是一棵一棵来的，而是一上来就依次访问各树的根节点，其他的没什么了。
5.5.5 树遍历算法的应用举例：
略
5.6 Huffman树
5.6.1 带权路径长度的概念：
树的路径长度（PL）：从树的根结点到每一个结点的路径长度之和。
完全二叉树可以让一定结点个数的所组成的树具有最短路径长度。
树的带权路径长度（WPL）：从树的根节点到每一个叶子结点的路径长度乘其对应权值的积之和。
5.6.2 Huffman树的概念：
带权路径长度最短的二叉树就是Huffman树，给定带权节点生成Huffman树的算法被称为Huffman算法。
从3:10开始看。
另外，书中这里展示了一次时间复杂度比较详细的计算方法。
5.6.3 拓展阅读：最优判定树：
说人话：Huffman树的应用。
5.6.4 Huffman编码：
Huffman树最经典的应用在通信领域。采用Huffman编码的信息消除了冗余数据，极大地提高了通信信道的传输效率。目前，Huffman编码技术还是数据压缩的重要方法。
从头看上面的视频即可，没啥用。
5.7 堆
用于实现优先队列。
5.7.1 小根堆和大根堆：
如果有一个关键码集合\(K=\{k_{0},k_{2},\cdots,k_{n-1}\}\)，把它的所有元素按完全二叉树的顺序存储方式存放在一个一维数组中。并且满足
\(k_{i}\le k_{2i+1}\)且\(k_{i}\le k_{2i+2}\)（或者\(k_{i}\ge k_{2i+1}\)且\(k_{i}\ge k_{2i+2}\)）\(i=0,1,\cdots,\left \lfloor (n-2)/2\right \rfloor\)
就是比每个节点都比两个子女小（或大）则称这个集合为小根堆（或大根堆）。
在堆中，所有的记录具有成为堆序的关系，分为大根堆序和小根堆序。
5.7.2 堆的建立：
使用Robert Floyd提出的算法，其中要用到一个调整算法siftDown。
书中代码(H.curSize-2)/2是深度最深的非叶子结点的index，从这个结点往上依次使用siftDown。
siftDown中，自上至下地让当前位置和左右子女进行比较，如果不符合小（或大）根堆的规则就跟子女进行交换，然后对子女进行相同的操作，直到符合规则或者不再有子女。
5.7.3 堆的插入：
使用siftUp算法，因为插入都是先插到末尾。自下至上地让当前位置和双亲节点进行比较，如果不符合规则就进行交换，然后对双亲进行相同的操作，直到符合规则或者已经迭代到根节点位置。
5.7.4 堆的删除：
把堆的最后一个节点填补到取走的位置，然后进行siftDown，时间复杂度为\(O(\log_{2}n)\)。
5.9 拓展阅读：八皇后问题与树的剪枝
5.9.1 八皇后问题的提出：
八皇后问题（Eight queens），是由国际象棋棋手马克斯·贝瑟尔于1848年提出的问题，是回溯算法的典型案例。问题表述为：在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案，实际答案为92。
5.9.2 八皇后问题的状态树：
每一层摆放一个皇后，就可以得到八皇后问题的状态树，对于建树过程中不符合八皇后共存条件的分支，可以直接剪掉，不考虑后续。
5.9.3 八皇后问题算法：
从4:43开始看。
6 图
6.1 图的基本概念
6.1.1 与图有关的若干概念：
完全图：每两个顶点都直接可达。
权值：在一些图中边具有的与之相关的数值
网络：带权图。
邻接顶点：亦称相邻顶点，顾名思义为一条边相连的顶点。
子图：比原始图少0~n个顶点和少0~n条边的图。
顶点的度：依附于顶点的边数。
稠密图和稀疏图：如果用n表示顶点数，用e表示边数，则：若\(e<n\log_{2}n\)，则称该图为稀疏图；若\(e\ge n\log_{2}n\)，则称该图为稠密图。
路径：从某个顶点到某个顶点的路径顶点序列（仅本书如此定义，其他书或有不同）。
路径长度：路径上边的条数或者带权边的权值和。
简单路径与回路：顶点序列不重复的路径被定义为简单路径。若一条路径的始点和终点相同，则称其为回路或环，如果回路序列除了始点和终点没有重复的点了，就称其为简单回路。
连通图与连通分量：无向图的一对点之间有路径，则称这对点是连通的，如果一个图里的所有点对都是连通的，则该图为连通图。非联通图的极大连通子图叫做连通分量。
强连通图与强连通分量：在有向图中，每一个点对都互相可达，则该图为强连通图。非强连通图的极大强连通子图叫做强连通分量。
生成树：去掉连通图多余的边，使得每一对顶点之间有且仅有一条通路。若连通图有n个顶点，则其生成树由n-1条边构成。对于非连通图，有其生成森林。关于强连通图的生成树的讨论还需要再看几道题。
6.1.2 图的基本操作：
略
6.2 图的存储结构（重点）
6.2.1 图的邻接矩阵表示：
有权图中，不连通记为无穷。
6.2.2 图的邻接表表示：
略
6.2.3 邻接矩阵表示与邻接表表示的比较：
图越稠密邻接矩阵利用率越高，图越稀疏邻接表越好。在时间效率方面，邻接表往往是更好的。
6.2.4 图的邻接多重表和十字链表表示：
这里主要为了解决无向图邻接表二重存储在操作上带来的麻烦。
无向图的邻接多重表表示：图的每一条边用一个边节点表示[mark,vertex1,vertex2,path1,path2]，mark是标记域，标记该边是否已接受过处理；vertex1和vertex2是顶点域，指明该边所依附的两个顶点；path1和path2是链接指针域，指明vertex1和vertex2所依附的下一条边；如有必要，还可以设置一个域cost来存放权值。顶点节点可以存在线性表里，顶点节点有两个域，一个存值，一个是指针，指向依附于该顶点的第一条边。
有向图的十字链表：结合邻接表（入边表）和逆邻接表（出边表）。每个边界点和无向图的邻接多重表一样，不过规定好vertex1中存始点，vertex2中存终点；path1指向vertex1的另一条出边，path2指向vertex2的另一条入边。顶点节点要新增一个指针域，因为两个指针与一个要指向第一个出边，一个要指向第一个入边。
6.3 图的遍历（重点）
6.3.1 深度优先搜索：
略
6.3.2 广度优先搜索：
略
6.3.3 连通分量：
从一个顶点出发进行遍历，遍历完成后被访问到的点就是一个连通分量；如果有点没被访问到，那就选一个没访问过的点开始遍历，本次遍历访问到的点又组成一个连通分量，以此类推，可以求出所有连通分量。
6.4 最小生成树
6.4.1 最小生成树求解和贪心法：
典型的最小生成树算法都采用了贪心策略，即逐步求解，局部最优。
6.4.2 Kruskal算法：
从头开始看。
6.4.3 Prim算法：
上面的视频也讲解了Prim算法，但是讲得比较乱，其实就是任选一点，然后加上与之相连的最短边，然后该点和刚刚连上的边另一侧的顶点组层广义点，继续进行相同操作即可。
6.5 最短路径
6.5.1 非负权值的单源最短路径：
这里介绍了Dijkstra算法。
从头开始看。
6.5.3 所有顶点之间的最短路径：
这里也要求边的权值非负，可以使用n次Dijkstra算法，时间复杂度\(O(n^{3})\)。这里要介绍的是Floyd算法，使用动态规划的思想，时间复杂度也是\(O(n^{3})\)。
从头开始看。
6.5.4 无权值的最短路径：
使用广度优先搜索。
6.6 活动网络
6.6.1 AOV网络与拓扑排序：
通常把计划、施工过程、生产流程、程序流程等都当做一个工程。除了很小的工程外，一般都把工程分为若干个叫做“活动”的子工程。每个活动不是并列的，一些活动需要在完成了一些其他活动的前提下才能进行。完成了这些活动，这个工程就可以完成了。
AOE网络是子工程通过一定规则生成的有向图，这个规则是一个活动v有铺垫活动a、b、c……，那么就要有a->v、b->v、c->v的有向边。
AOV网络不能有有向环，这样的话整个工程将无法完成。检测有向环的方法是对AOV网络构造它的拓扑有序序列，即将各个顶点（代表各个活动）排列成一个线性有序的序列，使得AOV网络中所有应存在的前驱和后继关系都能得到满足，得不到这个序列，证明有环。
因为拓扑排序人为地给没有约束关系的活动排了先后，所以拓扑排序序列往往不唯一。
拓扑排序的步骤：
（1）输入AOV网络。令n为顶点个数。
（2）在AOV网络中选一个没有直接前趋的顶点，并输出之。
（3）从图中删去该顶点，同时删除所有他发出的边。
（4）重复（2）、（3），直到全部顶点均已输出或者没全部输出但跳出了处理循环（证明有有向环）。
具体代码实现可以借助入度为零节点栈。
DFS也可以实现拓扑排序，就是把AOE网的箭头反向进行DFS访问到某个节点没有未访问过的后继了就把这个节点入队，全遍历完了依次出队即可。
6.6.2 AOE网络与关键路径法（次要）：
如果在无有向环的带权有向图中用用有向边表示一个工程中的各项活动，用有向边上的权值表示活动的持续时间，用顶点表示事件，则这样的有向图叫做用边表示活动的网络，简称AOE网络。
因为是次要的，关键路径法就先不看了。
7 查找
7.1 查找的概念及简单查找方法（重点）
7.1.1 查找的基本概念：
略
7.1.2 顺序查找法：
略
7.1.3 折半查找法：
就是二分法。
7.2 二叉查找树（重点）
7.2.1 二叉查找树的概念：
二叉查找树的每个节点都有一个作为查找依据的关键码（Key），不同节点的关键码各不相同
。左子树上所有节点的关键码都小于根节点的关键码，右子树上所有节点的关键码都大于根节点的关键码。左子树和右子树也是二叉查找树。
7.2.2 二叉查找树的查找：
从根开始逐层向下进行比较，可以递归，非递归更好。
7.2.3 二叉查找树的插入：
略
7.2.4 二叉查找树的删除：
如果所删节点无子女，直接删就好。
如果所删节点有一个子女，那让子女取代所删节点的位置。
如果所删节点左右子树都不为空，可以在被删节点的右子树进行中序遍历，中序遍历的第一个节点（再右子树中的Key最小）把要删除节点的Key值改为这个节点的Key值，然后去删除这个节点（递归）。
7.2.5 二叉查找树的性能分析：
扩充二叉树：设树的每个节点为内结点，即已有的节点，假定每个内结点的空子女指向虚拟的外节点，他们代表查找树中没有的Key，代表一个Key取值区间，这种二叉树为扩充二叉树。
使用平均查找长度（ASL）来分析二叉查找树的性能，\(ASL=ASL_{success}+ASL_{fail}\)。
\(ASL_{success}=\sum_{i=1}^{n}p[i]\times l[i]\)，其中l[i]是第i个内结点的层次号，p[i]是该节点的查找概率。
\(ASL_{fail}=\sum_{j=0}^{n}q[j]\times (l'[j]-1)\)，其中q[j]是外节点的查找概率，l'[j]是第j个外节点的层次号。
ASL最小的二叉查找树是最优二叉查找树。
在各节点查找概率相等的情形，高度最小的二叉查找树具有最小的平均查找长度。
对于等概率最优二叉查找树，\(ASL_{success}=\sum_{i=1}^{n}(\left \lfloor \log_{2}i\right \rfloor+1)\quad ASL_{fail}=\sum_{i=n+1}^{2n+1}\left \lfloor \log_{2}i\right \rfloor\)。
设一棵二叉查找树有n个节点，则高度最大为n，最小为\(\left \lceil \log_{2}(n+1)\right \rceil\)类似于完全二叉树。在随机情况下，二叉查找树的各种操作平均时间复杂度为\(O(\log_{2}n)\)。
7.3 AVL树
7.3.1 AVL树的概念：
AVL树是高度平衡的二叉查找树。一棵AVL树或者是空树，或者是具有下列性质的二叉查找树：它的左子树和右子树都是AVL树，且左子树和右子树的高度之差的绝对值不超过1。
7.3.2 平衡化旋转：
左单旋转（RR）、右单旋转（LL）、先左后右双旋转（LR）、先右后左双旋转（RL）。可以看出，中文名字表示了这个旋转本身的方向，而英文名字表示了不平衡因素的方位。
7.3.3 AVL树的插入：
从头开始看，前面讲了下概念和平衡化旋转。
7.3.4 AVL树的删除：
从头开始看。
铺垫知识：二叉搜索树的删除操作。
另外，这里的判定条件和插入是不一样的，要多看看，理解一下。
7.3.5 AVL树的性能分析：
这里求了一定高度AVL树的最少结点数，感觉不会考。另外，向AVL树插入节点的时间复杂度为\(O(n)\)，和一般的二叉搜索树相同。在AVL树删除一个节点并做平衡化旋转所需的时间为\(O(\log_{2}n)\)。
7.4 B树（次要）
时间原因，先不捋了，之后看看有没有题目再说。
7.6 散列表及其查找（次要）
时间原因，先不捋了，之后看看有没有题目再说。
8 排序
8.1 排序的概念
8.1.1 排序的相关概念：
数据表：待排序元素的有限集合。
排序码：执行排序算法就是比较排序码的大小进行排序。
排序的确切定义：略
原地排序：只是用了常数个额外存储空间，排序结果仍然保留在原来的数据表内。
排序算法的稳定性：如果有两个元素排序码相同，那么排序后相对位置不变则这个排序算法是稳定的，反之这个排序算法是不稳定的。
排序方法分类：一共有两大类，有序区增长：将数据表分为有序区和无序区，在排序过程中逐步扩大有序区，缩小无序区，直到有序区扩大到整个数据表为止。有序程度增长：数据表不能明确区分有序区和无序区，随着排序过程的执行，逐步调整表中元素的排列，使得表中的有序程度不断提高，直到完全有序。
内排序与外排序：内排序是指在排序期间数据元素全部存放在内存的排序。外排序是指在排序期间全部元素个数太多，不能同时存放在内存，必须根据排序过程的要求，不断在内存和外存之间移动的排序。
静态排序和动态排序：静态排序有两类，一类是采用顺序表存储待排序元素，在排序过程中重排数据元素的顺序，经过比较和判断，将元素移到合适的位置；另一类是采用静态链表存储，给每个元素增加一个链接指针或位置信息，在排序的过程中不移动元素或传送数据，仅通过修改链接指针或位置信息来改变元素之间的逻辑顺序，从而达到排序的目的。动态排序采用动态链表存储排序元素，在排序的过程中也是通过修改链接指针来改变元素之间的逻辑顺序，从而达到排序目的，但表的结构在排序过程中不断改变。
8.1.2 排序算法的性能分析：
时间衡量，直接插入排序、起泡排序和选择排序的时间代价为\(O(n)\)，快速排序、归并排序和堆排序的时间代价是\(O(n\log_{2}n)\)。
所需额外的内存空间是衡量算法性能的另一重要特征，有三种基本类型：（1）除使用有限的几个负责元素交换的工作单元外，不需要使用其他额外空间。（2）使用链表指针或数组下标表明元素的逻辑顺序，指针或下标需要额外的内存空间。（3）需要额外空间来存储待排序元素序列的副本或排序的中间结果。
8.1.3 数据表的结构定义：
略
8.2 插入排序（重点）
8.2.1 直接插入排序：
从头开始看。
直接插入排序是一种稳定的排序算法。
8.2.3 折半插入排序：
从头开始看，这个讲得不太好，看懂啥意思就得了。
折半插入排序是一种稳定的排序算法。
8.2.4 希尔排序：
又称缩小增量排序
从头开始看。
视频中的增量序列是Shell本人提出的也就是除以二向下取整。但是Hibbard、Sedgewick、Knuth等人提出一系列其他增量序列，可以使时间复杂度更低。
Shell增量的时间复杂度是\(O(n^{2})\)。
希尔排序是一种不稳定的排序算法。
8.3 交换排序（重点）
8.3.1 起泡排序：
起泡排序又称冒泡排序，是一种原地排序。
从头开始看。
时间复杂度为\(O(n^{2})\)。由于起泡排序通常比直接插入排序和简单选择排序需要移动更多次数的记录，所以起泡排序是所有简单排序算法中最慢的一个。
起泡排序是稳定的排序算法。
8.3.2 快速排序：
快速排序也叫分区排序，它采用分治法进行排序。
从头开始看。
这里讲的划分方法是Hoare划分，也就是两遍交替向中间扫描。还有一Rowe划分，是沿着一个方向扫描。
两种划分的时间代价都是\(O(n)\)。
快速排序的时间复杂度为\(O(n\log_{2}n)\)。
快速排序是不稳定的排序算法。
8.3.3 快速排序的改进算法：
快速-直接插入混合排序：在递归调用的过程中，当待排序的子序列规模小于预先确定的阈值时，程序调用直接插入排序算法对此子序列进行排序。
选基准记录的三者取中快速算法：在去pivot时选取序列左端点、右端点、中间点的中间值，把这个值与左端点交换，再对整个序列进行划分。
8.4 选择排序（重点）
8.4.1 简单选择排序：
简单选择排序又称直接选择排序。
从头开始看。
简单选择排序是一种不稳定的排序算法。
8.4.2 锦标赛排序：
锦标赛排序又称树形选择排序。
从头开始看。
时间复杂度\(O(n\log_{2}n)\)。
锦标赛排序是不稳定的排序算法。
8.4.3 堆排序：
看前面的思路介绍即可，后面的讲解有一些错误。
时间复杂度为\(O(nlog_2{n})\)。
堆排序是一种不稳定的排序算法。
8.5 归并排序（重点）
8.5.1 二路归并排序的设计思路：
从头开始看。
8.5.2 二路归并排序的递归算法：
略
8.6 基数排序（次要）
先不介绍了。
8.7 内排序算法的分析和比较
8.7.1 排序方法的下界：
借助判定树描述和分析不同排序算法的比较次数。
这个值用大欧表示是\(O(n\log_{2}n)\)。
8.7.2 各种内排序的方法比较：
当n不是很大（小于10240）时，采用简单排序与改进排序差距不大。如果元素本身的体积就不小，还是可以考虑下改进排序的，来减小元素移动次数。
另外，排序方法的选择还取决于元素排序码的分布情况：当个数n比较大，排序码比较随机，且对稳定性不做要求时，采用快速排序为宜；当个数n比较大，要求稳定排序且内存空间允许，采用归并排序为宜；当个数n较大，排序码可能有正序或逆序的情况，且不要求稳定性时，采用堆排序或归并排序为宜；当个数n较大，只需找出最小的前几个元素，采用堆排序或简单选择排序为宜；当个数n比较小，元素基本有序且要求稳定时，采用直接插入排序为宜；当个数n较小，且元素体积较大，采用简单选择排序为宜。
混合排序是一个很好的思路，就如快速排序中的快速-直接插入混合排序，或者也可以先使用插入排序，然后进行归并。
8.8 外排序
8.8.1 常用的外存储器与缓冲区：
略
8.8.2 基于磁盘的外排序过程：
使用归并排序，在缓冲区进行操作。
8.8.3 m路归并排序：
在时间复杂度上m路归并排序和二路归并排序相同，m路归并排序的好处主要是减少归并趟数，从而减少访外次数，因为访外效率相较内部处理是非常低的。
算法设计
暂略
计算理论
1 有限自动机
1.1 问题与决定性问题
决定性问题是只需回答是与否的问题，一般问题总能转化为决定性问题。
决定性问题的每一个输入都是一个01串，任何01串都可以是一个输入。
字母表：任意一个有限集。
符号：字母表中的元素。
字符串：字母表中符号组成的有限序列。
串的长度｜·｜：字符串中符号的个数。
串的连接＊：相当于Java中的＋。
串的反转R：反序的串。
空词：记为\(\varepsilon\)，长度为0。
语言：给定字母表上一些字符串的集合。决定性问题与01语言一一对应。P集合被称为幂集，同离散数学。
全体01串的字典序：长度从小到大，同长按数大小排列。
无限长01串可看作是自然数集的映射。
等势：两集合之间存在一一对应。
可数：集合元素可以按次序列出。（自然数集就是可数的）
不可数：可数的反义词。无限长01串集（全体决定性问题）是不可数的。
1.2 确定型有限自动机（DFA）的概念
图灵机：一个人拿着笔在纸上进行。他根据眼睛看到的纸上符号和脑中的若干法则在纸上擦掉或写上一些符号，再改变他所看到的范围，一直进行，直到认为计算结束。
在这里，脑代表控制器，纸代表存储带，眼镜和笔代表读写头，法则代表转移函数。
有限自动机：简化的图灵机，是只读的，而且只能往后读，读完停机。一台有限自动机由状态集Q，字母表，转移函数\(\delta\)，和包括在Q中的起始状态s和接受状态集F完全决定，是一个五元组。
有限自动机的语言是可以落入其接受域的语言。
正则语言：至少含一个1的01串，且最后一个1后面有偶数个0
1.3 非确定型有限自动机（NFA）的概念
这是一种每步可以0～n种状态进入下一步的有限自动机。这里涉及到了状态的副本分裂，不仅仅是异步造成的分裂更有相同识别符号从同一状态指向不同状态的转移函数。
接受语言：最后一个字符读完各状态副本中有至少一个处于接受域。
NFA和DFA是等价的。
正则语言对并/连接/星号运算封闭（就是说运算完了还是正则的）。
1.3 正则表达式
正则表达式是单个符号、空语言、空集或者由正则封闭运算得来的表达式，每个正则表达式都表示一个语言。
语言是正则的则一定可以用正则表达式描述，可以用正则表达式表达的一定是正则语言
1.4 正则语言的泵原理
若A是正则语言，则存在p大于0，任意从属于A的，长度大于p的语言w＝xyz，存在可以满足下列条件的w，其中y的长度大于0，xy的长度小于等于w的长度，这个w满足对于任意的非负数i，\(xy^{i}z\epsilon A\)。若找不到这样的p中有这样的w，则A不是正则语言（这是逆否命题）。
2 图灵机
2.1 图灵机的概念
概念在上文已经写过，这里深化一下。
图灵机的输入长度是无限的，可以改写，可以向后移动。图灵机是一个七元组，其中有状态集、字母表、起始状态，这和有限自动机都是一样的。不过，图灵机还有带字母表（存储带上的字母表），和对应的转移函数，而且，图灵机有单一的接受状态和拒绝状态，且两者不重合。。
2.2 图灵机的运作流程
初始化：将输入的语言靠左填写到输入带里，输入带其余空的部分补上空格，读写头放在输入带的最左端。
图灵机的运行：根据函数进行移动，移动指明方向，可以改写刚刚扫描的内容。
2.3 图灵机的相关概念
图灵机的格局：就是给图灵机一个快照。将语言写下来，在把状态插到读写头所指符号的紧前面。
图灵机的语言：该图灵机接受的所有字符串的集合。
判定器：对所有输入都停机（接受或拒绝）的图灵机
图灵可判定语言：某个判定器的语言（也称递归语言）。
图灵可识别语言：某个图灵机的语言（也称为递归可枚举语言）。
图灵可识别语言包含可判定语言包含上下无关语言包含正则语言
2.4 图灵机的描述
形式水平的描述：状态图或转移函数。
实现水平的描述：读写头的移动、改写。
高水平描述：使用日常语言，一般会使用带引号的文段来表示图灵机。
对于已知的文段，可以描述其语言（接受的输入）即可。
2.5 图灵机的变形
图灵机有多种变形，例如多带图灵机，非确定图灵机，还有枚举器，带停留的图灵机等等。只要满足必要特征，它们都与这里定义的图灵机等价。
对于非确定的图灵机（NTM），和非确定型有限自动机可以类比，只不过，非确定型图灵机不允许空串的状态转移箭头。
若运行中出现了接受分支，则称NTM接受该串。
当一非确定型图灵机对所有输入，所有分支都停机，则称其是判定的，每一个判定的非确定型图灵机都有一个等价的确定型图灵机（普通的图灵机）。
0 条评论