数据结构(全)

线性结构, 树形结构, 图结构, 排序, 查找, 数据结构, 算法

文章共22,595字 · 阅读需要大约76分钟

一键AI生成摘要，助你高效阅读

问答

我要的图文并茂

55770人浏览 · 2023-06-21 21:36:45

我要的图文并茂 · 2023-06-21 21:36:45 发布

4.3.2 Kruskal 算法（克鲁斯卡尔）

第一章绪论

1.1 数据结构的基本概念

数据：所有能输入到计算机中并能被程序识别和处理的符号集合。包括: 数值数据：整数、实数等。非数值数据：图形、图象、声音、文字等。

数据元素：数据的基本单位，在程序中作为一个整体进行考虑和处理。

数据项：构成数据元素的最小单位

关系图:

数据类型：一组值的集合以及定义于这个值集上的一组操作（如：int）, 原子类,结构类

抽象数据类型(ADT)：一个数据模型以及定义在该模型上的一组操作, 也就是定义了一个数据结构。

1.2 数据结构的三要素

数据结构：相互之间存在一定关系的数据元素的集合, 如下为数据结构的三要素

1.2.1 数据的逻辑结构

数据元素之间逻辑关系的整体。

集合：数据元素之间没有关系

线性结构：数据元素之间是一对一的线性关系

树结构：数据元素之间是一对多的层次关系

图结构：数据元素之间是多对多的任意关系

1.2.2 数据的存储（物理）结构：

数据及其逻辑结构在计算机中的表示。

顺序存储结构：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置表示

链接存储结构：用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示

1.2.3 数据的运算

根据逻辑结构来定义, 根据存储结构来实现。

1.3 算法的基本概念

算法 : 是对特定问题求解步骤的一种描述，是指令的有限序列。程序 = 数据结构 + 算法; 算法必须是有穷的，而程序可以是无穷的

算法的基本特性：

有穷性: 有穷时间内能执行完
- 确定性: 相同输入只会有相同输出
  - 可行性: 可以用已有的基本操作实现算法

好算法的特点：

高效性
正确性
健壮性: 能处理一些异常
可理解性
抽象分级

算法分析：

时间复杂度：当问题规模充分大时，算法中基本语句的执行次数在渐近意义下的阶——关注的是增长趋势，用大O记号表示

常见的时间复杂度：Ο(1)＜O( $log_{2}^{n}$ )＜O(n)＜O( $nlog_{2}^{n}$ )＜O( $n^{2}$ )＜O( $2^{n}$ )＜O(n!)< O(nn) (常对幂指阶)

空间复杂度：算法在执行过程中需要的辅助空间数量, 递归程序看递归深度与问题规模n的关系。

第二章线性表

线性表的逻辑结构：n（n≥0）个具有相同类型的数据元素的有限序列。

2.1 线性表的存储结构

顺序表：静态存储分配，编译时确定容量，用一段地址连续的存储单元依次存储线性表的数据元素，逻辑关系通过存储位置（下标）来实现（随机存储）

链表：动态存储分配，运行时分配空间，用一组任意的存储单元存放线性表的元素，用指针来反映数据元素之间的逻辑关系（顺序存储）

上溢: 存储器满, 还往里写; 下溢: 存储器空,还往外读

备注: 位序从1开始。

顺序表与单链表图:

双链表示意图:

循环链表示意图:

静态链表示意图:

2.2 顺序表与链表的比较

存储密度比较：

顺序表：只存储数据元素、预分配存储空间
链表：指针的结构性开销、链表中的元素个数没有限制

按位查找：

顺序表：O(1)，随机存取
链表：O(n)，顺序存取

插入和删除：

顺序表：O(n)，平均移动表长一半的元素
链表：不用移动元素，合适位置的指针——Ｏ(1)

时间复杂度：

顺序表：若线性表频繁查找却很少进行插入和删除操作
链表：若线性表需频繁插入和删除时

空间复杂度：

顺序表：知道线性表的大致长度，空间效率会更高
链表：若线性表中元素个数变化较大或者未知

2.3 栈

定义：限定仅在一端（栈顶）进行插入和删除操作的线性表，后进先出。

栈示意图：

时间复杂度(插入与删除)：顺序栈与链栈均为O(1)

空间复杂度：链栈多一个指针域，结构性开销较大，使用过程中元素个数变化较大时，用链栈；反之顺序栈。

出栈元素不同排列的个数: $\frac{1}{n+1}C_{2n}^{n}$ (卡特兰数)

共享栈: 两个栈共享一片内存空间, 两个栈从两边往中间增长。

卡特兰数的应用:

存储结构:

顺序栈初始化：top=-1
链栈初始化：top=NULL

栈的应用:

1) 括号匹配

2) 递归

3) 中缀表达式转后缀表达式

4) 中缀表达式：设两个栈（数据栈和运算符栈），根据运算符栈的优先级进行运算。

2.4 队列

定义: 只允许在一端插入, 在另一端删除。具有先进先出的特点。

队列示意图:

时间复杂度：均为O（1）

空间复杂度：链队列多一个指针域，结构性开销较大；循环队列存在浪费空间和溢出问题。使用过程中元素个数变化较大时，用链队列；反之循环队列。

双端队列: 只允许从两端插入、两端删除的线性表。

双端队列示意图：

存储结构:

链队列:队头指针指向队头元素的前一个位置，队尾指针指向队尾元素，先进先出。

循环队列：

1）队空：front=rear

2）队满：(rear+1)%QueueSize=front

3）队列元素个数：（队尾-队头+队长）%队长==(rear-front+QueueSize)%QueueSize

队列的应用:

1) 树的层次遍历

2) 图的广度优先遍历

2.4 数组与特殊矩阵

一维数组的存储结构：

二维数组的存储结构：

对称矩阵的压缩(行优先)：

下三角矩阵的压缩(行优先)：

上三角(行优先):

三对角矩阵的压缩(行优先)：

稀疏矩阵压缩：

十字链表法压缩稀疏矩阵：

2.5 串

串，即字符串（String）是由零个或多个字符组成的有限序列。串是一种特殊的线性表，数据元素之间呈线性关系。

字符串模式匹配：

1）朴素模式匹配算法

2）KMP算法

手算KMP的next数组示意图:

求next[2] :

求next[3]:

求next[4]:

求next[5]:

C语言求KMP的next数组代码示例:

void Createnext(char *sub, int *next){
    assert(sub != NULL && next != NULL);
    int j = 2;             //模式串的next指针
    int k = 0;             //next数组的回溯值,初始化为next[1]=0
    int lenSub = strlen(sub);
    assert(lenSub != 0);
    next[0] = -1;
    next[1] = 0;
    while (j < lenSub){
        if (sub[j-1] == sub[k]){
            next[j] = ++k;
            j++;
        }
        else{
            k = next[k];
            if (k == -1){
                k = 0;
                next[j] = k;
                j++;
            }
        }
    }
}

求nextValue:

void nextValue(char *sub, int *next) {
	int lenSub = strlen(sub);
	for(int j=2;j<lensub; j++){
		if(sub[j]==sub[next[j]])
			next[j]=next[next[j]]
	}
}

备注:

1) 实现next有多种不同方式, 对应不同的next数组使用

2) 根据实现方式不同, next数组整体+1不影响KMP算法。

第三章树和二叉树

3.1 树和森林

定义（树）：n（n≥0）个结点（数据元素）的有限集合，当 n＝0 时，称为空树。

3.1.1 树的基本术语

结点的度：结点所拥有的子树的个数。

叶子结点：度为 0 的结点，也称为终端结点。

分支结点：度不为 0 的结点，也称为非终端结点。

孩子：树中某结点子树的根结点称为这个结点的孩子结点。

双亲：这个结点称为它孩子结点的双亲结点。

兄弟：具有同一个双亲的孩子结点互称为兄弟。

路径：结点序列 n1, n2, …, nk 称为一条由 n1 至 nk 的路径，当且仅当满足结点 ni 是 ni+1 的双亲（1<=i<k）的关系。

路径长度：路径上经过的边的个数。

祖先、子孙：如果有一条路径从结点 x 到结点 y，则 x 称为 y 的祖先，而 y 称为 x 的子孙。

结点所在层数：根结点的层数为 1；对其余结点，若某结点在第 k 层，则其孩子结点在第 k+1 层。

树的深度（高度）：树中所有结点的最大层数。

树的宽度：树中每一层结点个数的最大值。

树的度：树中各结点度的最大值。

树的路径长度: 从根到每个结点的路径长度总和

备注: 在线性结构中，逻辑关系表现为前驱——后继,一对一; 在树结构中，逻辑关系表现为双亲——孩子,一对多。

森林: 森林是m（m≥0）棵互不相交的树的集合, m可为0, 即空森林。

3.1.2 树的性质

结点数=总度数+1

度为m的树第 i 层至多有 $m^{i-1}$ 个结点（i≥1）

高度为h的m叉树至多有 $\frac{m^{h}-1}{m-1}$ 个结点

具有n个结点的m叉树的最小高度为 $\left \lceil log_{m}^{n(m-1)+1} \right \rceil$

最小高度推理过程图:

3.1.3 树与森林的遍历

树的遍历:

先根遍历(先根后子树)
后根遍历(先子树后根)
层序遍历

森林的遍历:

前序遍历(先根, 后子树)
中序遍历(先子树后根, 其实就是后序遍历树)

区别与联系:

1) 树的前序遍历等价于其树转化二叉树的前序遍历！

2) 树的后序遍历等价于其树转化二叉树的中序遍历！

3.1.4 树的存储结构

双亲表示法图:

孩子表示法图:

孩子兄弟表示法图(树/森林转化为二叉树):

3.1.5 树转二叉树

在树转为二叉树后, 有以下结论:

1) 树的叶子结点数量 = 二叉树左空指针数量(形象理解为树越宽, 兄弟越多, 越是向右长)

2) 树的非叶子结点数量 = 二叉树右空指针-1(非叶子必有儿子, 右指针由儿子提供, -1是根节点多了一个右空指针)

3.2 二叉树

3.2.1 二叉树的性质

斜树：

左斜树：所有结点都只有左子树的二叉树
右斜树：所有结点都只有右子树的二叉树

满二叉树：所有分支结点都存在左子树和右子树，且所有叶子都在同一层上的二叉树

完全二叉树：在满二叉树中，从最后一个结点开始，连续去掉任意个结点得到的二叉树

完全二叉树特点：

叶子结点只能出现在最下两层且最下层的叶子结点都集中在二叉树的左面
完全二叉树中如果有度为 1 的结点，只可能有一个，且该结点只有左孩子
深度为 k 的完全二叉树在 k-1 层上一定是满二叉树
在同样结点个数的二叉树中，完全二叉树的深度最小

性质：在二叉树中，如果叶子结点数为 n0，度为 2 的结点数为 n2，则有: n0＝n2+1

证明: 设 n 为二叉树的结点总数，n1 为二叉树中度为 1 的结点数，则有：

n＝n0＋n1＋n2

在二叉树中，除了根结点外，其余结点都有唯一的一个分枝进入，一个度为 1 的结点射出一个分枝，一个度为 2 的结点射出两个分枝，所以有：

n＝n1＋2n2＋1

性质：二叉树的第 i 层上最多有 $2^{i-1}$ 个结点（i≥1）

性质：一棵深度为 k 的二叉树中，最多有 $2^{k}-1$ 个结点

性质：具有 n 个结点的完全二叉树的深度为 $log_{2}^{n}$ 向下取整+1 (或 $log_{2}^{n+1}$ 向上取整)

证明：设具有 n 个结点的完全二叉树的深度为 k，则：

$2^{k-1}$ ≤n < $2^{k}$

对不等式取对数，有：

k-1 ≤ $log_{2}^{n}$ ＜k

即：

$log_{2}^{n}$ ＜k ≤ $log_{2}^{n}$ +1

由于 k 是整数，故必有

k＝ $log_{2}^{n}$ +1

性质：对一棵具有 n 个结点的完全二叉树中从 1 开始按层序编号，对于任意的序号为 i（1≤i≤n）的结点（简称结点 i），有：

如果 i＞1，则结点 i 的双亲结点的序号为 i/2，否则结点 i 无双亲结点
如果 2i≤n，则结点 i 的左孩子的序号为 2i，否则结点 i 无左孩子
如果 2i+1≤n，则结点 i 的右孩子的序号为2i+1，否则结点 i 无右孩子

性质：若已知一棵二叉树的前序序列和中序序列，或者中序序列和后序序列，能唯一确定一颗二叉树。

3.2.2 二叉树的遍历

从根结点出发，按照某种次序访问树中所有结点，并且每个结点仅被访问一次。

前序遍历（深度优先遍历）
中序遍历
后序遍历
层序遍历（广度优先遍历）

3.2.3 二叉树的存储

链式存储图:

顺序存储图:

3.2.4 线索二叉树

利用二叉树中n+1个空指针, 将指针指向结点的前驱和后继。线索二叉树是加上线索的链表结构, 是一种物理结构

存储结构:

示例图:

三种线索化的对比图:

各自特点:

3.3 哈夫曼树和哈夫曼编码

带权路径长度(WPL)：从根结点到各个叶子结点的路径长度与相应叶子结点权值的乘积之和

最优二叉树（哈夫曼树）：给定一组具有确定权值的叶子结点，带权路径长度最小的二叉树

特点：

权值越大的叶子结点越靠近根结点
只有度为 0 和度为 2 的结点，不存在度为 1 的结点
构造过程中共新建了n-1个结点, 因此总结点数为2n-1

前缀编码：在一组编码中，任一编码都不是其它任何编码的前缀, 前缀编码保证了在解码时不会有多种可能。

度为m的哈夫曼树: 通过只有度为m和度为0求解非叶子结点

3.4 并查集

存储结构: 双亲表示法

实现功能: 并查(并两个集合, 查根结点)

优化: 小树并到大树, "高树变矮树"(压缩路径)

第四章图

定义：顶点集V和边集E组成，记为G = (V, E)

注意：线性表可以是空表，树可以是空树，但图不可以是空，即V一定是非空集, 边集E可以为空

子图：若图G=(V, E)，G'=(V', E')，如果V' 属于 V 且E' 属于E，则称图G'是G的子图

4.1 图的基本概念

图的分类:

无向边：表示为(vi,vj)，顶点vi和vj之间的边没有方向

有向边（弧）：表示为<vi,vj>，从vi 到vj 的边有方向, vi为弧尾, vj为弧头

稠密图：边数很多的图

稀疏图：边数很少的图

无向完全图：无向图中，任意两个顶点之间都存在边

有向完全图：有向图中，任意两个顶点之间都存在方向相反的两条弧

度、入度和出度：

顶点的度：在无向图中，顶点 v 的度是指依附于该顶点的边数，通常记为TD (v)

顶点的入度：在有向图中，顶点 v 的入度是指以该顶点为弧头的弧的数目，记为ID (v)；

顶点的出度：在有向图中，顶点 v 的出度是指以该顶点为弧尾的弧的数目，记为OD (v)；

握手定理:

路径：

回路（环）：第一个顶点和最后一个顶点相同的路径

简单路径：序列中顶点不重复出现的路径

简单回路（简单环）：除第一个和最后一个顶点外，其余顶点不重复出现的回路。

路径长度：非带权图——路径上边的个数

路径长度：带权图——路径上边的权值之和

极大连通子图: 连通的情况下, 包含尽可能多的边和顶点, 也称连通分量

极小连通子图: 删除该子图中任何一条b边, 子图不再连通, 如生成树

无向连通图：

连通顶点：在无向图中，如果顶点vi和顶点vj(i≠j)之间有路径，则称顶点vi和vj是连通的

连通图：在无向图中，如果任意两个顶点都是连通的，则称该无向图是连通图

连通分量：非连通图的极大连通子图、连通分量是对无向图的一种划分

连通分量示意图:

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

强连通顶点：在有向图中，如果从顶点vi到顶点vj和从顶点vj到顶点vi均有路径，则称顶点vi和vj是强连通的

强连通图：在有向图中，如果任意两个顶点都是强连通的，则称该有向图是强连通图

强连通分量：非强连通图的极大连通子图

强连通分量示意图:

子图与生成子图:

常考点

无向图:

所有顶点的度之和=2|E|

若G是连通图，则最少有 n-1 条边（树），若 |E|>n-1，则一定有回路

若G是非连通图，则最多可能有 $C_{n-1}^{2}$ 条边 (n-1个完全图+1个孤点)

无向完全图共有 $C_{n}^{2}$ 条边

有向图:

所有顶点的出度之和=入度之和=|E|

所有顶点的度之和=2|E|

若G是强连通图，则最少有 n 条边（形成回路）

有向完全图共有 $2C_{n}^{2}$ 条边

图的遍历：从图中某一顶点出发访问图中所有顶，并且每个结点仅被访问一次。

深度优先遍历序列（dfs）
广度优先遍历序列（bfs）

备注: 调⽤BFS/DFS函数的次数 = 连通分量数

4.2 图的存储结构

邻接矩阵：

一维数组：存储图中顶点的信息
二维数组（邻接矩阵）：存储图中各顶点之间的邻接关系

特点：一个图能唯一确定一个邻接矩阵，存储稀疏图时，浪费空间。空间复杂度为: O( $n^{2}$ )。

示意图:

性质 (行*列) :

邻接表：

顶点表：所有边表的头指针和存储顶点信息的一维数组
边表（邻接表）：顶点 v 的所有邻接点链成的单链表

示意图:

特点：空间复杂度为：O（n+e）, 适合存储稀疏图。

两者区别:

十字链表法图:

备注:

1) 十字链表只用于存储有向图

2) 顺着绿色线路找: 找到指定顶点的所有出边

3) 顺着橙色线路找: 找到指定顶点的所有入边

4) 空间复杂度：O(|V|+|E|)

邻接多重表图:

备注:

1) 邻接多重表只适用于存储无向图

2) 空间复杂度：O(|V|+|E|)

四者区别:

4.3 最小生成树

生成树：连通图的生成树是包含全部顶点的一个极小连通子图, 可用DFS和BFS生成。

生成树的代价：在无向连通网中，生成树上各边的权值之和

最小生成树：在无向连通网中，代价最小的生成树

性质: 各边权值互不相等时, 最小生成树是唯一的。边数为顶点数-1

生成森林示意图:

4.3.1 Prim算法

从某⼀个顶点开始构建⽣成树；每次将代价最⼩的新顶点纳⼊⽣成树，直到所有顶点都纳⼊为⽌。基于贪心算法的策略。

时间复杂度：O(|V|2) 适合⽤于边稠密图。

4.3.2 Kruskal 算法（克鲁斯卡尔）

每次选择⼀条权值最⼩的边，使这条边的两头连通（原本已经连通的就不选）, 直到所有结点都连通。基于贪心算法的策略。

时间复杂度：O( |E|log2|E| ) 适合⽤于边稀疏图。

4.4 最短路径

非带权图: 边数最少的路径（广度优先遍历）

带权图: 边上的权值之和最少的路径

4.4.1 Dijkstra算法

时间复杂度：O(n2)

备注: Dijkstra 算法不适⽤于有负权值的带权图

4.4.2 Floyd算法

核心代码:

时间复杂度：O(n3)

备注: 可以⽤于负权值带权图, 不能解决带有“负权回路”的图

三者区别:

4.5 有向⽆环图（DAG）

描述表达式 (简化前) :

描述表达式 (简化后) :

4.6 拓扑排序

AOV⽹(Activity On Vertex NetWork，⽤顶点表示活动的⽹)：⽤DAG图（有向⽆环图）表示⼀个⼯程。顶点表示活动，有向边表示活动Vi必须先于活动Vj进⾏

如图:

拓扑排序的实现：

① 从AOV⽹中选择⼀个没有前驱（⼊度为0）的顶点并输出。

② 从⽹中删除该顶点和所有以它为起点的有向边。

③ 重复①和②直到当前的AOV⽹为空或当前⽹中不存在⽆前驱的顶点为⽌。

逆拓扑排序（可用DFS算法实现）:

① 从AOV⽹中选择⼀个没有后继（出度为0）的顶点并输出。

② 从⽹中删除该顶点和所有以它为终点的有向边。

③ 重复①和②直到当前的AOV⽹为空

备注: 上三角(对角线为0)矩阵, 必不存在环, 拓扑序列必存在, 但拓扑不唯一。(拓扑唯一, 图不唯一)

4.7 关键路径

在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销（如完成活动所需的时间），称之为⽤边表示活动的⽹络，简称AOE⽹

示意图:

关键活动: 从源点到汇点的有向路径可能有多条，所有路径中，具有最⼤路径⻓度的路径称为关键路径，⽽把关键路径上的活动称为关键活动。

事件vk的最早发⽣时间: 决定了所有从vk开始的活动能够开⼯的最早时间。

活动ai的最早开始时间: 指该活动弧的起点所表⽰的事件的最早发⽣时间。

事件vk的最迟发⽣时间: 它是指在不推迟整个⼯程完成的前提下，该事件最迟必须发⽣的时间。

活动ai的最迟开始时间: 它是指该活动弧的终点所表示事件的最迟发⽣时间与该活动所需时间之差。

活动ai的时间余量：表⽰在不增加完成整个⼯程所需总时间的情况下，活动ai可以拖延的时间。d(k)=0的活动就是关键活动, 由关键活动可得关键路径。

示例图:

第五章查找

静态查找：不涉及插入和删除操作的查找

动态查找：涉及插入和删除操作的查找

查找⻓度: 在查找运算中，需要对⽐关键字的次数称为查找⻓度

平均查找长度：衡量查找算法的效率

公式:

5.1 顺序查找（线性查找）：

顺序查找适合于存储结构为顺序存储或链接存储的线性表。

　　基本思想：从数据结构线形表的一端开始，顺序扫描，依次将扫描到的结点关键字与给定值k相比较，若相等则表示查找成功；若扫描结束仍没有找到关键字等于k的结点，表示查找失败。

时间复杂度: O(n)。

有序顺序查找的ASL图:

无序查找失败时的平均查找长度: n+1次 (带哨兵的情况)

5. 2 折半查找：

元素必须是有序的，顺序存储结构。判定树是一颗平衡二叉树, 树高 $\left \lceil (log_{2}^{n+1}) \right \rceil$ (由n= $2^{h}$ -1得来)。

基本思想：用给定值k先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；若不相等，再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表。

公式：mid=(low+high)/2, 即mid=low+1/2*(high-low);

　　 1）相等，mid位置的元素即为所求

　　2）>，low=mid+1;

3）<，high=mid-1。

时间复杂度: $O(log_{2}^{n})$

二叉判定树的构造:

备注：对于静态查找表，一次排序后不再变化，折半查找能得到不错的效率。但对于需要频繁执行插入或删除操作的数据集来说，不建议使用。失败结点的ASL不是方形结点, 而是其父节点。

5.3 分块查找

分块查找，⼜称索引顺序查找。

基本思想：将查找表分为若干子块, 块内的元素可以无序, 块间的元素是有序的, 即前一个快的最大元素小于后一个块的最大元素。再建立索引表, 索引表中的每个元素含有各块的最大关键字和第一个元素的地址。索引表按关键字有序排列。

示意图:

备注:

1) 设索引查找和块内查找的平均查找⻓度分别为LI、LS，则分块查找的平均查找⻓度为

ASL=LI + LS

2) 将长度为n的查找表均匀分为b块, 每块s个记录, 在等概率情况下, 若在块内和索引表中均采用顺序查找, 则平均查找长度为:

5.4 二叉排序树

又称二叉查找树（BST，Binary Search Tree）, 是具有如下性质的二叉树：左子树结点值 < 根结点值 < 右子树结点值

二叉排序树的插入: 新插入的结点一定是叶子。

二叉排序树的删除

1) 情况一, 删除叶结点, 直接删除

2) 情况二, 待删除结点只有一颗子树, 让子树代替待删除结点

3) 情况三, 待删除结点有左, 右子树, 则令待删除的直接前驱(或直接后继(中序遍历))代替待删除结点。

示意图: (30为直接前驱, 60为直接后继)

平均查找效率: 主要取决于树的高度。

时间复杂度: $O(log_{2}^{n})$

5.5 平衡二叉树

简称平衡树（AVL树）, 树上任一结点的左子树和右子树的高度之差不超过1。结点的平衡因子=左子树高-右子树高。

平衡二叉树的插:

LL型:

RR型:

RL型:

LR型:

平衡二叉树的删除: 同上

考点:

假设以 $n_{h}$ 表示深度为h的平衡树中含有的最少结点数。则有 $n_{0}$ = 0, $n_{1}$ = 1, $n_{2}$ = 2，并且有 $n_{h}$ = $n_{h-1}$ + $n_{h-2}+1$

时间复杂度: $O(log_{2}^{n})$

5.6 红黑树

与AVL树相比, 插入/删除很多时候不会破坏“红黑”特性，无需频繁调整树的形态。因为AVL是高度差严格要求不超过1, 红黑树高度差不超过2倍, 较为宽泛。

定义:

①每个结点或是红色，或是黑色的

②根节点是黑色的

③叶结点（外部结点、NULL结点、失败结点）均是黑色的

④不存在两个相邻的红结点（即红结点的父节点和孩子结点均是黑色）

⑤对每个结点，从该节点到任一叶结点的简单路径上，所含黑结点的数目相同

口诀: 左根右，根叶黑不红红，黑路同

示例图:

性质:

性质1：从根节点到叶结点的最长路径不大于最短路径的2倍 (红结点只能穿插在各个黑结点中间)

性质2：有n个内部节点的红黑树高度 $h\leq 2log_{2}^{n+1}$

结论: 若根节点黑高为h，内部结点数（关键字）最多有 $2^{2h}-1$ , 最少有 $2^{h}-1$

示例图:

红黑树的插入操作:

红黑树的插入示例图:

红黑树的删除: 和“二叉排序树的删除”一样! 具体还是算了吧, 放过自己。。。

时间复杂度: $O(log_{2}^{n})$

5.7 B树

B树，⼜称多路平衡查找树，B树中所被允许的孩⼦个数的最⼤值称为B树的阶，通常⽤m表示。

m阶B树的特性:

1）树中每个结点⾄多有m棵⼦树，即⾄多含有m-1个关键字。

2）若根结点不是终端结点，则⾄少有两棵⼦树。

3）除根结点外的所有⾮叶结点⾄少有 $\left \lceil m/2 \right \rceil$ 棵⼦树，即⾄少含有 $\left \lceil m/2 \right \rceil-1$ 个关键字。

4) 所有的叶结点都出现在同⼀层次上，并且不带信息, ( 指向这些结点的指针为空 ) 。

5) 最小高度: $log_{m}^{n+1}\leqslant h$ (n为关键字, 注意区分结点)

6) 最大高度: $h\leqslant log_{\left \lceil m/2 \right \rceil}^{\frac{n+1}{2}}+1$

7) 所有⼦树⾼度要相同

8) 叶结点对应查找失败的情况, 即n个关键字有n+1个叶子结点

示例图:

B树的插入(5阶为例):

B树的删除:

1) 若被删除关键字在终端节点，则直接删除该关键字（要注意节点关键字个数是否低于下限 ⌈m/2⌉ − 1）

2) 若被删除关键字在⾮终端节点，则⽤直接前驱或直接后继来替代被删除的关键字

删除77:

删除38:

删除90:

3) 若被删除关键字所在结点删除前的关键字个数低于下限，且此时与该结点相邻的左、右兄弟结点的关键字个数均=⌈m/2⌉ − 1，则将关键字删除后与左（或右）兄弟结点及双亲结点中的关键字进⾏合并

删除49:

5.8 B+树

⼀棵m阶的B+树需满⾜下列条件

1）每个分⽀结点最多有m棵⼦树（孩⼦结点）。

2）⾮叶根结点⾄少有两棵⼦树，其他每个分⽀结点⾄少有 ⌈m/2⌉ 棵⼦树。

3）结点的⼦树个数与关键字个数相等。

4）所有叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按⼤⼩顺序排列，并且相邻叶结点按⼤⼩顺序相互链接起来

5）所有分⽀结点中仅包含它的各个⼦结点中关键字的最⼤值及指向其⼦结点的指针。所有⾮叶结点仅起索引作⽤，

6) 所有⼦树⾼度要相同

B+树示例图:

B+树与B树的对比图:

5.9 哈希表（Hash）

根据数据元素的关键字计算出它在散列表中的存储地址。

哈希函数： 建⽴了“关键字”→“存储地址”的映射关系。

冲突（碰撞）：在散列表中插⼊⼀个数据元素时，需要根据关键字的值确定其存储地址，若该地址已经存储了其他元素，则称这种情况为“冲突（碰撞）”

同义词：若不同的关键字通过散列函数映射到同⼀个存储地址，则称它们为“同义词”

复杂度分析：对于无冲突的Hash表而言，查找复杂度为O(1)

5.9.1 构造哈希函数

1) 除留余数法 —— H(key) = key % p, 取⼀个不⼤于m但最接近或等于m的质数p

适⽤场景：较为通⽤，只要关键字是整数即可

2) 直接定址法 —— H(key) = key 或 H(key) = a*key + b

适⽤场景：关键字分布基本连续

3) 数字分析法 —— 选取数码分布较为均匀的若⼲位作为散列地

适⽤场景：关键字集合已知，且关键字的某⼏个数码位分布均匀

4) 平⽅取中法——取关键字的平⽅值的中间⼏位作为散列地址

适⽤场景：关键字的每位取值都不够均匀。

5.9.2 处理冲突

拉链法示意图:

开放定址法:

1) 线性探测法

2) 平⽅探测法

3) 双散列法

4) 伪随机序列法

示意图:

删除操作: 采用开放定址法时, 只能逻辑删除。

装填因子: 表中记录数 / 散列表长度。

备注: 平均查找长度的查找失败包含不放元素的情况。(特殊: 根据散列函数来算: 2010真题)

聚集: 处理冲突的方法选取不当,而导致不同关键字的元素对同一散列地址进行争夺的现象

第六章排序

稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；

内排序 ：所有排序操作都在内存中完成；

外排序 ：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行。

参考博客：

超详细十大经典排序算法总结（java代码）c或者cpp的也可以明白_Top_Spirit的博客-CSDN博客

6.1 直接插入排序

动图演示：

优化: 折半插入排序

6.2 希尔排序

又称缩小增量排序, 先将待排序表分割成若⼲形如 L[i, i + d, i + 2d,…, i + kd] 的“特殊”⼦表，对各个⼦表分别进⾏直接插⼊排序。缩⼩增量d，重复上述过程，直到d=1为⽌。建议每次将增量缩⼩⼀半。

示例图:

6.3 冒泡排序

动图演示:

6.4 快速排序

算法思想：

1) 在待排序表L[1…n]中任取⼀个元素pivot作为枢轴（或基准）

2) 通过⼀趟排序将待排序表划分为独⽴的两部分L[1…k-1]和L[k+1…n]，使得L[1…k-1]中的所有元素⼩于pivot，L[k+1…n]中的所有元素⼤于等于 pivot，则pivot放在了其最终位置L(k)上，这个过程称为⼀次“划分”。

3) 然后分别递归地对两个⼦表重复上述过程，直每部分内只有⼀个元素或空为⽌，即所有元素放在了其最终位置上。

示例图:

6.5 简单选择排序

算法思想: 每⼀趟在待排序元素中选取关键字最⼩的元素加⼊有序⼦序列。

动画演示:

6.6 堆排序

⼤根堆: 若满⾜：L(i)≥L(2i)且L(i)≥L(2i+1) （1 ≤ i ≤n/2 ）

⼩根堆: 若满⾜：L(i)≤L(2i)且L(i)≤L(2i+1) （1 ≤ i ≤n/2 ）

大根堆示例图:

6.6.1 建立大根堆

思路：从 $\left \lfloor len/2 \right \rfloor$ 开始, 把所有⾮终端结点都检查⼀遍，是否满足大根堆的要求，如果不满⾜，则进⾏调整。若元素互换破坏了下⼀级的堆，则采⽤相同的方法继续往下调整（⼩元素不断“下坠”）

小元素下坠示例图:

结论: 建堆的过程，关键字对⽐次数不超过4n，建堆时间复杂度=O(n)

6.6.2 堆的插入与删除

插入: 将新增元素放到表尾, 而后根据大小根堆进行上升调整。

删除: 被删除的元素⽤堆底元素替代，然后让该元素不断“下坠”，直到⽆法下坠为⽌

排序动图演示:

6.7 归并排序

该算法是采用分治法, 把两个或多个已经有序的序列合并成⼀个。

2路归并图:

结论：n个元素进⾏k路归并排序，归并趟数= $\left \lceil log_{k}^{n} \right \rceil$

6.8 基数排序 (低位优先)

基数排序是非比较的排序算法，对每一位进行排序，从最低位开始排序，复杂度为O(kn),为数组长度，k为数组中的数的最大的位数；

动图演示:

时间复杂度: ⼀趟分配O(n)，⼀趟收集O(r)，总共 d 趟分配、收集，总的时间复杂度=O(d(n+r)） , 其中把d为关键字拆为d个部分, r为每个部分可能取得 r 个值。

基数排序适用场景:

①数据元素的关键字可以⽅便地拆分为 d 组，且 d 较⼩

②每组关键字的取值范围不⼤，即 r 较⼩

③数据元素个数 n 较⼤

如:

内部排序总结:

基本有序: 直接插入(比较最少), 冒泡(趟数最少)

6.9 外部排序

数据元素太多，⽆法⼀次全部读⼊内存进⾏排序, 读写磁盘的频率成为衡量外部排序算法的主要因素。

示例图:

多路归并:

结论: 采⽤多路归并可以减少归并趟数，从⽽减少磁盘I/O(读写)次数。对 r 个初始归并段，做k路归并，则归并树可⽤ k 叉树表示若树⾼为h，则归并趟数 = h-1 = $\left \lceil log_{k}^{r} \right \rceil$ 。K越大, r越小, 读写磁盘次数越少。(缺点: k越大, 内部排序时间越大)