本笔记为博主2021计算机专业考研408科目的数据结构个人笔记，由于本来就具有一定的数据结构经验（毕竟也是计院人），所以笔记是十分简要的，仅供参考。
杂项
逻辑结构
线性结构
- 顺序表
- 栈
- 队列
非线性结构
- 集合
- 树形结构
- 图状结构
存储结构（物理结构）
- 顺序存储
- 链式存储
- 索引存储
- 散列存储（哈希存储）
线性表
顺序表（数组）
- 逻辑结构：线性表
- 存储结构：顺序存储
链表
- 逻辑结构：线性表
- 存储结构：链式存储
单链表、双链表
循环单链表、循环双链表
静态链表
借助数组来表述链表，链表指针即结点相对地址（数组下标）。
| 下标 | 元素 | 指针 |
|---|---|---|
| 0 | 头结点 | 2 |
| 1 | b | 3 |
| 2 | a | 1 |
| 3 | c | -1 |
| 4 | - | - |
栈
- 逻辑结构：线性表（限定操作）
- 排列个数：n个不同元素进栈，出栈元素不同排列的个数为\(\frac{1}{n+1}C^{n}_{2n}\)
- 应用：括号匹配、算术表达式（中缀转后缀）、递归转非递归、DFS
顺序栈
- 存储结构：顺序存储
链栈
- 存储结构：链序存储
共享栈
- 顺序栈的双向存储
队列
- 逻辑结构：线性表（限定操作）
- 应用：层序遍历、BFS
循环队列
- 存储结构：顺序存储
链式队列
- 存储结构：链式存储
双端队列
- 存储结构：顺序存储、链式存储
需会判断序列是否满足题设条件（输入受限、输出受限）
多维数组（矩阵）
压缩存储
- 对称矩阵：存储对角线和一个三角区的元素
- 三角矩阵：存储对角线和一个三角区的元素
- 三对角矩阵：存储三条对角线的元素
稀疏矩阵
将非0元素及其对应行和列构成三元组，可用以下方法存储这些三元组：
- 采用数组存储
- 采用十字链表法
串
串的存储方式
- 定长顺序存储
- 堆分配存储
- 块链存储
暴力模式匹配算法
- 时间复杂度：\(O(mn)\)
KMP算法
- 时间复杂度：\(O(m+n)\)
- 优势：不回溯主串指针
构造next数组
- s为空时，最长相等前后缀长度 = -1
- s为单个字符时，前缀为空，后缀为空，最长相等前后缀长度 = 0
- s为'ab'时，前缀为a，后缀为b，最长相等前后缀长度 = 0
- s为'aba'时，前缀为a、ab，后缀为ba、a，最长相等前后缀长度 = 1
- next[k] = s[1~k-1]的最长相等前后缀长度。
例如：对s[1~5] = 'abcac'，next[4] = s[1~3]的最长相等前后缀长度。
| 编号 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 模式 | a | b | c | a | c |
| next | -1 | 0 | 0 | 0 | 1 |
为了方便计算，也可让next数组元素均+1（方便直接索引）：
| 编号 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 模式 | a | b | c | a | c |
| next | 0 | 1 | 1 | 1 | 2 |
next数组构造实现：
int i=1,j=0;
next[1] = 0;
while(i<m){
if(j==0||p[i]==p[j]){
++i;++j;
next[i] = j;
}
else{
j=next[j];
}
}
匹配过程
- 设置双指针：i指针用于遍历主串，j指针用于遍历模式。
- 当s[i]==p[j]，则i++，j++；若匹配失败，i指针不用回退，j指针则回退至next[j]位置。
- 若j先达到模式尾，证明匹配成功。若i先到达主串尾，证明匹配失败。
构造nextval数组
可能出现连续多次匹配失败，模式指针多次回退相同字符的情况：
| j | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| 主串 | a | a | a | b | a | a | a | a | b |
| 模式 | a | a | a | a | b | ||||
| next[j] | 0 | 1 | 2 | 3 | 4 | ||||
| nextval[j] | 0 | 0 | 0 | 0 | 4 |
构造next数组时，加入判断：
if(p[i]!=p[j]) nextval[i] = j;
else nextval[i] = nextval[j]; //相同字符，因此i失败时可以回退到nextval[j]的位置
树
树的性质
度：
- 结点的度 = 该结点的孩子个数
- 树的度 = 树中结点的最大度数
- 树的结点数 = 所有结点的度数 + 1
- 二叉树使用二叉链表存储：n个结点有n+1个空指针
- AVL深度h最低数量的结点：N(h) = 1 + N(h-1) + N(h-2); N(0)=1, N(1)=1
路径：
- 路径：树中某两个节点之间所经过的节点序列构成
- 路径长度：路径上所经过的边的个数
- 树的路径长度：树根到各个节点的路径长度之和
二叉树的遍历方式（前序、中序、后序、层序）
- 前序遍历：注意非递归实现
- 中序遍历：注意非递归实现
- 后序遍历：注意非递归实现
- 层序遍历
- 遍历序列构造二叉树：中序序列和（前序序列|后序序列|层序序列）可以唯一确定一棵二叉树。
线索二叉树
利用传统二叉树的空指针，指向遍历前驱或后驱的结点，从而加快查找前驱或后驱结点和遍历的速度。
- 需要引入2个额外标记位
class Node{
Node* lchild;
int ltag; //若为0，lchild表示结点左孩子。若为1，表示前驱结点。
Node* rchild;
int rtag; //若为0，rchild表示结点右孩子。若为1，表示后继结点。
Data data;
};
中序线索二叉树、前序线索二叉树
- 构造
- 找结点前驱和后继
后序线索二叉树
- 构造：使用三叉链才可支持找后驱，否则需借助栈的支持才可找后驱
- 找结点前驱和后继
排序二叉树、平衡二叉树
排序二叉树
- 查找最坏时间复杂度：\(O(n)\) （最坏情况为退化成一条链表）
平衡二叉树
- 查找时间复杂度：\(O(nlogn)\)
- 平衡因子：左子树与右子树的高度差（注意不是数量差）
- h层深度的平衡二叉树最少结点数 \(n_h=n_{h-1}+n_{h-2}+1\)（其中\(n_0=0，n_1=1\)）
哈夫曼树
带权路径长度
- 结点的带权路径长度：从树根到结点的路径长度（经过的边数）与该结点上权值的乘积。
- 树的带权路径长度：所有叶结点的带权路径长度之和。
哈夫曼编码
- 哈夫曼编码：没有一个编码是另一个编码的前缀
构造哈夫曼树
每次选取两个最小权值的结点，生成一个父结点，其权值为两子节点权值相加；重复直到生成最后一个父结点。
哈夫曼树带权路径长度 = 所有叶结点的带权路径长度之和 = 所有非叶节点的权值之和
B树（多路平衡查找树）
一棵m阶（最多m棵子树，即最多m-1个关键字）B树：
- 所有非叶节点至少有\(\lceil{m/2}\rceil\)棵子树，即至少有\(\lceil{m/2}\rceil-1\)个关键字（根节点不算入此规则）
- 树所有结点的平衡因子均等于0
- 所有叶节点为寻找失败的情况，但是不算入B树的高度
注意插入、删除过程
支持随机访问（从根节点开始向下找），但不支持顺序查找
B+树
一棵m阶B+树（最多m棵子树，即最多m个关键字）：
- 所有非叶节点至少有\(\lceil{m/2}\rceil\)棵子树，即至少有\(\lceil{m/2}\rceil\)个关键字。（根节点不算入此规则）
- 树所有结点的平衡因子均等于0
- 非叶节点仅有索引作用，标识其中子结点中最大（或最小）关键字以表示范围。
- 叶节点才包含信息，且额外用一条链将所有叶节点链接起来（优势：天然有序，可直接遍历...）
树和森林
树的存储结构
- 双亲表示法：每个结点用1个指针指向双亲结点。
- 孩子表示法：每个结点用n个指针指向n个孩子。
- 孩子兄弟表示法（二叉树表示法）：第一个指针指向第一个孩子，第二个指针指向下一个兄弟
与二叉树的转换
树与森林的遍历方式（先根遍历、后根遍历）
- 先根遍历：对应二叉树形式的先序遍历
- 后根遍历：对应二叉树形式的中序遍历
并查集
- Union操作
- Find操作
图
图的性质
- 完全图（简单完全图）：无向完全图拥有n(n-1)/2条边。有向完全图拥有n(n-1)条弧
- 极大连通子图：保持图连通且包含所有边的子图
- 极小连通子图：保持图连通且边数量最少的子图
- 连通图（无向图情况）：任何顶点之间都有路径可以到达的图
- 连通分量（无向图情况）：每个极大连通子图都是该图的一个连通分量
- 强连通图（有向图情况）：任何顶点之间相互都有路径可以到达的图
- 强连通分量（有向图情况）：每个极大强连通子图都是该图的一个强连通分量（特殊地，单个结点也可为一个强连通分量）
- 生成树：包含图中所有顶点的极小连通子图
- 生成森林：图中所有连通分量的生成树
- 简单路径：顶点不重复出现的路径
- 简单回路：除了第一个顶点和最后一个顶点，其余顶点不重复出现的回路
- 有向树：一个顶点入度为0、其余顶点入度均为1的有向图
- 有向图的度：分为入度和出度
- 无向图的度：只有单个度
图的存储方式
邻接矩阵法
- 空间占用：\(O(|V|^2)\)
- 无向图的邻接矩阵是对称矩阵，可以用压缩存储。
邻接表法
- 空间占用：无向图为\(O(|V|+2|E|)\)，有向图为\(O(|V|+|E|)\)
邻接多重表（无向图）
class Vertex{
int data;
Edge* firstEdge;
}
//顶点i和j的边
class Edge{
int ivex; //顶点i的位置
Edge* ilink; //i的下一个边
int jvex; //顶点j的位置
Edge* jlink; //j的下一个边
};
十字链表（有向图）
class Vertex{
int data;
Edge* firstEdge;
}
//顶点i和j的边
class Edge{
int ivex; //顶点i的位置
Edge* ilink; //i为边入口的下一个边
int jvex; //顶点j的位置
Edge* jlink; //j为边出口的下一个边
};
图的十字链表表示不是唯一的，但一个十字链表表示可以确定一个图。
深度优先遍历、广度优先遍历
深度优先遍历（DFS）
使用邻接矩阵：
- 时间复杂度：\(O(|V|^2)\)
- 空间复杂度：\(O(|V|)\) （必须递归空间）
使用邻接表：
- 时间复杂度：\(O(|V|+|E|)\)
- 空间复杂度：\(O(|V|)\) （必须递归空间）
应用：
- 可用DFS遍历得到生成树
广度优先遍历（BFS）
使用邻接矩阵：
- 时间复杂度：\(O(|V|^2)\)
- 空间复杂度：\(O(|V|)\) （必须借助队列）
使用邻接表：
- 时间复杂度：\(O(|V|+|E|)\)
- 空间复杂度：\(O(|V|)\) （必须借助队列）
应用：
- 可用BFS求解单源最短路径问题（只允许权值相等）
- 可用BFS遍历得到生成树
Prim算法（最小生成树）
- 每次选择权值最小边对应的顶点。
- 时间复杂度：\(O(|V|^2)\)，适用边稠密的图
Kruskal算法（最小生成树）
- 每次选权值最小边。使用 堆 存放边的集合，可将选择最小边时间降为\(O(\log_{2}|E|)\)
- 时间复杂度：\(O(|E|\log_{2}|E|)\)，适用边稀疏顶点较多的图
Dijstra算法（单源最短路径）
- 每次选取边权值+结点已有代价之和最低的边，并设置对应目标点代价。重复直到所有点顶点都已被设置。
- 时间复杂度：\(O(|V|^2)\)
- 注意：不允许边带负权值。
Floyd算法（多源最短路径）
\(A^{(-1)}[i][j] = arcs[i][j]\)
\(A^{(k)}[i][j] = Min\{A^{(k-1)}[i][k]+ A^{(k-1)}[k][j]\}\)
(\(k=0,1,..,n-1\))
计算\(A^{(-1)},A^{(0)},...,A^{(n-1)}\)，\(A^{(k)}\)
- 时间复杂度：\(O(|V|^3)\)
- 注意：允许带负权值，但不允许有包含负权值边组成的回路。
for(int k = 0;k<n;++k)
for(int i = 0;i<n;++i)
for(int j = 0;j<n;++j)
if(A[i][j] > A[i][k]+A[k][j])
A[i][j] = A[i][k] + A[k][j];
有向无环图描述表达式
相同子式的共享：
拓扑排序（AOV网）
每次选择入度为0的点，选择后删除该点和以它为起点边（使相连的其他点入度-1），然后进行下一轮选择。
- 时间复杂度：\(O(|V|+|E|)\)
- 逆拓扑排序：与拓扑排序类似，但选择的为出度为0的点。
关键路径（AOE网）
- 事件\(v_k\)（点）最早发生时间：\(ve(k)=Max\{ve(j)+Weight(v_j,v_k)\}\)
- 事件\(v_k\)（点）最迟发生时间：\(vl(k)=Min\{vl(j)-Weight(v_k,v_j)\}\)
- 活动\(a_k\)（边）最早开始时间：\(e(i) = ve(k)\)
- 活动\(a_j\)（边）最晚开始时间：\(l(i) = vl(j)-Weight(v_k,v_j)\)
- 一个活动\(a_i\)最迟开始时间与最晚开始时间差额 \(d(i)=l(i)-e(i)\) 若为0，则该活动为关键活动。
关键路径：
- 完成整个工程最短时间就是关键路径的长度。
- 关键路径上的所有活动（边）都是关键活动。
- 关键路径并不一定唯一（但长度都是工程最短时间）。对于多条关键路径的AOE网，只加快一条关键路径是不会缩短工期的，只有加快全部关键路径才能达到缩短工期的目的。
查找
顺序查找
- 无序表
- 有序表（可减少失败平均比较次数，但成功平均比较次数与无序表相等）
折半查找
- 有序表
- 判定树：平衡二叉树，做某些判断题需要编排序号模拟下标
分块查找
- 索引表 + 查找表：先在索引表（块间有序）查找，再在查找表（块内无序）查找
散列结构
散列函数（哈希函数）
装填因子：\(a=\frac{表中记录数n}{散列表长度m}\)
开放定址法
\(H_i=(H(key) + d_i)\%m\)
- 线性探测法：\(d_i = 0,1,2,...,m-1\)；可能发生聚集现象，导致查找效率降低。
- 平方探测法：\(d_i = 0^2,1^2,-1^2,2^2,-2^2,..,k^2,-k^2\)；可有效避免聚集现象。
- 再散列法：利用第二个散列函数再计算\(H_i=(H(key) + i*H_2(key))\%m\)
- 伪随机法
拉链法
排序
- 稳定排序：插入、冒泡、归并、基数
- 不稳定排序：希尔、选择、快速、堆排
- 时间复杂度与初始排列状态有关：插入、希尔、冒泡、快速
直接插入排序
- 时间复杂度：平均\(O(n^2)\)，最好\(O(n)\)
- 空间复杂度：\(O(1)\)
- 稳定
折半插入排序
相比直接插入排序，只是减少了比较元素的次数，约为\(O(n\log_{2}n)\)
- 时间复杂度：平均\(O(n^2)\)，最好\(O(n)\)
- 空间复杂度：\(O(1)\)
- 稳定
希尔排序
通过增量划分子数组，然后使用插入排序算法分别排序，最后整体得到基本有序的数组，整体再用一次插入排序算法。
- 时间复杂度：平均约为\(O(n^{1.3})\)，最坏\(O(n^2)\)
- 空间复杂度：\(O(1)\)
- 不稳定
冒泡排序
注意需设置flag，如果一趟排序中没有发生交换，则可以提前终止排序。
- 时间复杂度：\(O(n^2)\)
- 空间复杂度：\(O(1)\)
- 稳定
简单选择排序
- 时间复杂度：\(O(n^2)\)
- 空间复杂度：\(O(1)\)
- 不稳定
快速排序
- 时间复杂度：平均\(O(n\log_{2}n)\)，最坏\(O(n^2)\)
- 空间复杂度：平均\(O(\log_{2}n)\)，最坏\(O(n)\) （即取决于递归的栈空间）
- 不稳定
划分：首先左指针指向枢纽元，轮流使用右/左指针，每轮只让其中一个指针移动到第一个不符合区间条件的位置，然后左右指针指向的值（总有一个指向枢纽元）交换，下一轮使用另一个指针。
堆排序
- 时间复杂度：\(O(n\log_{2}n)\)
- 空间复杂度：\(O(1)\)
- 不稳定
堆操作：
- 堆构造（自底向上选择非叶节点，选择后自顶向下更新） 时间复杂度：\(O(n)\)
- 堆插入（自底向上） 时间复杂度：\(O(\log_{2}n)\)
- 堆顶删除（自顶向下） 时间复杂度：\(O(\log_{2}n)\)
归并排序
- 时间复杂度：\(O(n\log_{2}n)\)
- 空间复杂度：\(O(n)\)
- 稳定
基数排序
需借助r个辅助存储队列，进行d趟分配和收集。
- 时间复杂度：\(O(d(n+r))\)
- 空间复杂度：\(O(r)\)
- 稳定
多路归并排序（外部排序）
败者树
- 败者树是一棵完全树，有2k个结点（k为路数），其中k个结点存储胜败者信息，k个结点存储有序路的索引
- 根节点为胜者，其余非叶结点为败者。
- 更新后，需要自下往上重新比较胜负者，从而更新败者树。
生成初始归并段
根据可用内存区大小，来对同等大小的记录集进行排序，生成长度一样的初始归并段。
多趟归并排序
例子，2路归并：
在k路归并中，归并趟数为S，初始段记录数量为r
- 所需内存缓冲区：k个输入缓冲区，1个输出缓冲区（大小不一定与输入缓冲区一致，例如只占1个记录）
- 直接比较：
- 每次比较需 \(k-1\) 次
- \(总比较次数 = S(n-1)(k-1) = \lceil{log_{k}r}\rceil(n-1)(k-1)\)
- 败者树法：
- 每次比较只需 \(\lceil{log_{2}k}\rceil\) 次
- \(总比较次数 = S(n-1)\lceil{log_{2}k}\rceil = \lceil{log_{k}r}\rceil(n-1)\lceil{log_{2}k}\rceil =(n-1)\lceil{log_{2}r}\rceil\)
置换-选择排序（生成不等长度初始归并段）
- 先读入一个记录作为初始段的第一个元素。
- 每次读入一个记录到内存工作区，若有MINIMAX值（即比输出初始段的末尾值还大），则该记录添入到初始端文件尾，并从内存工作区中移除。
- 当内存工作区满额且无MINIMAX值时，则认为完成一个初始段生成。
最佳归并树（不等长度归并段多趟归并排序）
- 类似k阶哈夫曼树
- 若结点有n个，\((n-1)\%(k-1)=u\neq 0\)，则证明有u个多余结点，需要添加 k-u-1 个权值（长度）为0的虚段
1个完整哈夫曼树 + u个多余结点 + k-u-1个虚段 = 新的1个完整哈夫曼树