目录
第一章 数据结构绪论
1.1 数据结构的基本概念
1.2 数据结构的三要素
1.2.1. 数据的逻辑结构
1.2.2. 数据的存储结构（物理结构）
1.2.3. 数据的运算
1.2.4. 数据类型和抽线数据类型
1.3 算法的基本概念
1.4 算法的时间复杂度
1.5 算法的空间复杂度
第二章 线性表
2.1 线性表的定义和基本操作
2.1.1 线性表的定义
2.1.2 线性表的基础操作
2.2 顺序表
2.2.1 顺序表的概念
2.2.2. 顺序表的实现编辑
2.2.3 顺序表的基本操作
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. 静态链表
2.3.10. 顺序表和链表的比较
第三章 栈和队列
3.1. 栈
3.1.1. 栈的基本概念
3.1.2. 栈的基本操作
3.1.3. 栈的顺序存储实现
3.1.4. 栈的链式存储
3.2. 队列
3.2.1. 队列的基本概念
3.2.2. 队列的基本操作
3.2.3. 队列的顺序存储实现
3.2.4. 队列的链式存储实现
3.2.5. 双端队列
3.3. 栈与队列的应用
3.3.1 栈在括号匹配中的应用
3.3.2. 栈在表达式求值中的应用
3.3.3. 栈在递归中的应用
3.3.4. 队列的应用
3.4. 特殊矩阵的压缩存储
3.4.1 数组的存储
3.4.2 对称矩阵的压缩存储
3.4.3 三角矩阵的压缩存储
3.4.4 三对角矩阵的压缩存储
3.4.5 稀疏矩阵的压缩存储
第四章 串
4.1. 串的基本概念
4.2. 串的基本操作
4.3. 串的存储实现
4.3.1 静态数组实现
4.3.2 基本操作的实现
4.4. 串的朴素模式匹配
4.5. KPM算法
第五章 图
5.1. 树的概念
5.1.1. 树的基本定义
5.1.2. 树的常考性质
5.2. 二叉树
5.2.1. 二叉树的定义
5.2.2. 特殊二叉树
5.2.3. 二叉树的性质
5.2.4. 二叉树存储实现
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.5. 应用
5.5.1. 二叉排序树
5.5.2. 平衡二叉树
5.5.3. 哈夫曼树
第六章 图
6.1. 图的基本概念
6.2. 图的存储
6.2.1. 邻接矩阵
6.2.2. 邻接表
6.2.3. 十字链表、临接多重表
6.2.4. 图的基本操作
6.3. 图的遍历
6.3.1. 广度优先遍历
6.3.2. 深度优先遍历
6.4. 图的应用
6.4.1. 最小生成树
6.4.2. 无权图的单源最短路径问题——BFS算法
6.4.3. 单源最短路径问题——Dijkstra算法
6.4.4. 各顶点间的最短路径问题——Floyd算法
6.4.5. 有向⽆环图描述表达式
6.4.6. 拓扑排序
6.4.7. 关键路径
第七章 查找
7.1 查找概念
7.2 顺序查找
7.3 折半查找
7.4 分块查找
7.5 红黑树
7.5.1 为什么要发明红黑树？
7.5.2 红黑树的定义
7.5.3 红黑树的插入
7.6 B树和B+树
7.6.1 B树
7.6.2 B树的基本操作
7.6.3 B+树
7.6.4 B树和B+树的比较
7.7 散列查找及其性能分析
7.7.1 散列表的基本概念
7.7.2 散列查找及性能分析
第八章 排序
8.1. 排序的基本概念
8.2. 插入排序
8.2.1. 直接插入排序
8.2.2. 折半插入排序
8.2.3. 希尔排序
8.3. 交换排序
8.3.1. 冒泡排序
8.3.2. 快速排序
8.4. 选择排序
8.4.1. 简单选择排序
8.4.2. 堆排序
8.5. 归并排序
8.6. 基数排序
8.7. 内部排序算法总结
8.7.1. 内部排序算法比较
8.7.2. 内部排序算法的应用
8.8. 外部排序
8.8.1. 外部排序的基本概念和方法
8.8.2. 败者树
8.8.3. 置换-选择排序（生成初始归并段）
8.8.4. 最佳归并树
第一章 数据结构绪论
1.1 数据结构的基本概念
- 数据：数据是信息的载体，符号的集合、所有能输入到计算机中并能被计算机程序处理的符号的集合，数据是计算机程序加工的原料。
- 数据元素：数据的基本单位，通常作为一个整体进行考虑和处理。一个数据元素可由若干数据项组成。
- 数据项：构成数据元素的不可分割的最小单位。
- 数据对象：数据对象是具有相同性值的数据元素的集合，是数据的一个子集。
- 数据结构：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
举例需要理解几点:
- 学校里的好多类型的表：数据
- 单独的一张成绩单表：数据对象
- 成绩单中每一行有姓名、课程、班级、成绩：数据元素
- 成绩单中每一行的每一个表格姓名等都是一个个的数据项
1.2 数据结构的三要素
1.2.1. 数据的逻辑结构
逻辑结构是指数据元素之间的逻辑关系，即从逻辑关系上描述数据。
逻辑结构包括：
- 集合结构：结构中的数据元素之间除“同属一个集合”外，别无其它关系（例如：一群羊）。
- 线性结构：结构中的数据元素之间只存在一对一的关系，除了第一个元素，所有元素都有唯一前驱；除了最后一个元素，所有元素都有唯一后继（例如：排队取号）。
- 树形结构：结构中数据元素之间存在一对多的关系（例如：思维导图）。
- 图状结构：数据元素之间是多对多的关系（例如：道路信息）。
1.2.2. 数据的存储结构（物理结构）
如何用计算机表示数据元素的逻关系?
存储结构是指数据结构在计算机中的表示（又称映像），也称物理结构。
存储结构包括：
- 顺序存储：把逻辑上相邻的元素存储在物理位置也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。
- 链式存储：逻辑上相邻的元素在物理位置上可以不相邻，借助指示元素存储地址的指针来表示元素之间的逻辑关系。
- 索引存储：在存储元素信息的同时，还建立附加的索引表，索引表中的每项称为索引项，索引项的一般形式是（关键字，地址）。
- 散列存储：根据元素的关键字直接计算出该元素的存储地址，又称哈希（Hash）存储。
需要理解几点:
- 若采用顺序存储，则各个数据元素在物理上必须是连续的;若采用非顺序存储，则各个数据元素在物理上可以是离散的。
- 数据的存储结构会影响存储空间分配的方便程度。
- 数据的存储结构会影响对数据运算的速度
1.2.3. 数据的运算
- 数据上的运算包括运算的定义和实现。
- 运算的定义是针对逻辑结构指出运算的功能。
- 运算的实现是针对存储结构的，指出运算的具体操作步骤。
针对于某种逻辑结构，结合实际需求，定义基本运算。
例如:逻辑结构->线性结构
基本运算:
1.查找第i个数据元素
2.在第i个位置插入新的数据元素
3.删除第i个位置的数据元素......1.2.4. 数据类型和抽线数据类型
数据类型是一个值的集合和定义在此集合上的一组操作的总称。例如：定义int整形，我们就可以把他们加减乘除等操作。
- 原子类型。其值不可再分的数据类型。如bool 和int 类型。
- 结构类型。其值可以再分解为若干成分（分量）的数据类型（例如：结构体）。
抽象数据类型（Abstract Data Type，ADT）是抽象数据组织及与之相关的操作。ADT 用数学化的语言定义数据的逻辑结构、定义运算。与具体的实现无关。
在探讨一种数据结构时理解几点:
- 定义逻辑结构(数据元素之间的关系)
- 定义数据的运算(针对现实需求应该对这种逻辑结构进行什么样的运算)
- 确定某种存储结构，实现数据结构，并实现一些对数据结构的基本运算
1.3 算法的基本概念
程序 = 数据结构+算法
数据结构：如何用数据正确地描述现实世界的问题，并存入计算机。
算法：如何高效地处理这些数据，以解决实际问题
算法(Algorithm)是对特定问题求解步骤的一种描述，它是指令的有限序列，其中的每条指令表示一个或多个操作。
算法的特性：
- 有穷性：一个算法必须总在执行有穷步之后结束，且每一步都可在有穷时间内完成。
- 确定性：算法中每条指令必须有确定的含义，对于相同的输入只能得到相同的输出。
- 可行性：算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。
- 输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合。
- 输出：一个算法有一个多个输出，这些输出是与输入有着某种特定关系的量。
我们可以类比：y = f（x）函数，其中x就是输出，y就是输出，这个函数就是算法。
好的算法达到的目标：
- 正确性：算法应能够正确的求解问题。
- 可读性：算法应具有良好的可读性，以帮助人们理解。
- 健壮性：输入非法数据时，算法能适当地做出反应或进行处理，而不会产生莫名奇妙地输出结果。
- 效率与低存储量需求：花的时间少即：时间复杂度低。不费内存即：空间复杂度低。
1.4 算法的时间复杂度
- 顺序执行的代码只会影响常数项，可以忽略。
- 只需挑循环中的一个基本操作分析它的执行次数与 n 的关系即可。
- 如果有多层嵌套循环只需关注最深层循环循环了几次。
- 事前预估算法时间开销T(n)与问题规模 n 的关系 (T 表示“time“）
1.5 算法的空间复杂度
- 指算法消耗的存储空间(即算法除本身所需存储外的辅助空间)
- 算法的空间复杂度S(n)定义为该算法所耗费的存储空间，它是问题规模n的函数。
记为S(n)=O(g(n))
第二章 线性表
2.1 线性表的定义和基本操作
2.1.1 线性表的定义
-
线性表是具有相同数据类型的n(n>0)个数据元素的有限序列。
(其中n为表长，当n=0时线性表是一个空表。若用L命名线性表，则其一般表示为)
-
特点：
1. 存在惟一的第一个元素。
2. 存在惟一的最后一个元素。
3. 除第一个元素之外，每个元素均只有一个直接前驱。
4. 除最后一个元素之外，每个元素均只有一个直接后继 -
几个概念:
1. 是线性表中的“第i个”元素线性表中的位序。
2. 是表头元素;是表尾元素。
3. 除第一个元素外，每个元素有且仅有一个直接前驱:除最后一个元素外，每个元素有且仅有一个直接后继。 -
存储结构：
1. 顺序存储结构：顺序表
2. 链式存储结构：链表
2.1.2 线性表的基础操作
- InitList(&L)：初始化表。构造一个空的线性表L，分配内存空间。
- DestroyList(&L)： 销毁操作。销毁线性表，并释放线性表L所占用的内存空间。
- ListInsert(&L;i,e)：插入操作。在表L中的第i个位置上插入指定元素e。
- ListDelete(&L,i,&e)：删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。
- LocateElem(L,e)：按值查找操作。在表L中查找具有给定关键字值的元素。
- GetElem(L,i): 按位查找操作。获取表L中第i个位置的元素的值。
- Length(L)：求表长。返回线性表L的长度，即L中数据元素的个数。
- PrintList(L)：输出操作。按前后顺序输出线性表L的所有元素值。
- Empty(L)：判空操作。若L为空表，则返回true，否则返回false。
什么时候要传入参数的引用“&“-- 对参数的修改结果需要“带回来”看下面举例：
- 首先是传值调用：
#include<stdio.h>
void test(int x) //形参是实参的临时拷贝
{
x = 1024;
printf("test函数内部 x=%d\n",x);
}
int main()
{
int x = 1;
printf("调用test前 x=%d\n",x);
test(x); //这里的x改变了并没有传回来
printf("调用test后 x=%d\n",x);
return 0;
}
//输出为：
//调用test前 x=1
//test函数内部 x=1024
//调用test后 x=1
//请按任意键继续. . .
- 然后再看传址调用
#include<stdio.h>
void test(int &x) //把x的地址传到函数
{
x = 1024;
printf("test函数内部 x=%d\n",x);
}
int main()
{
int x = 1;
printf("调用test前 x=%d\n",x);
test(x); //这里的x通过函数传回来值改变了
printf("调用test后 x=%d\n",x);
return 0;
}
//输出为：
//调用test前 x=1
//test函数内部 x=1024
//调用test后 x=1024
//请按任意键继续. . .2.2 顺序表
我们看完线性表的逻辑结构和基本运算，现在继续学习物理结构：顺序表
2.2.1 顺序表的概念
- 顺序表：用顺序存储的方式实现线性表顺序存储。把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。
-
顺序表的特点：
1. 随机访问，即可以在时间内找到第 i 个元素。
2. 存储密度高，每个节点只存储数据元素。
3. 拓展容量不方便（即使使用动态分配的方式实现，拓展长度的时间复杂度也比较高，因为需要把数据复制到新的区域）。
5. 插入删除操作不方便，需移动大量元素：。
2.2.2. 顺序表的实现
-
顺序表的静态分配
顺序表的表长刚开始确定后就无法更改(存储空间是静态的)
//顺序表的实现--静态分配
#include<stdio.h>
#define MaxSize 10 //定义表的最大长度
typedef struct{
int data[MaxSize]; //用静态的"数组"存放数据元素
int length; //顺序表的当前长度
}SqList; //顺序表的类型定义（静态分配方式）
void InitList(SqList &L){
for(int i=0;i<MaxSize;i++){
L.data[i]=0; //将所有数据元素设置为默认初始值
}
L.length=0;
}
int main(){
SqList L; //声明一个顺序表
InitList(L); //初始化一个顺序表
for(int i=0;i<MaxSize;i++){ //顺序表的打印
printf("data[%d]=%d\n",i,L.data[i]);
}
return 0;
}
- 顺序表的动态分配
//顺序表的实现——动态分配
#include<stdio.h>
#include<stdlib.h> //malloc、free函数的头文件
#define InitSize 10 //默认的初始值
typedef struct{
int *data; //指示动态分配数组的指针
int MaxSize; //顺序表的最大容量
int length; //顺序表的当前长度
}SeqList;
void InitList(SeqList &L){ //初始化
//用malloc 函数申请一片连续的存储空间
L.data =(int*)malloc(InitSize*sizeof(int)) ;
L.length=0;
L.MaxSize=InitSize;
}
void IncreaseSize(SeqList &L,int len){ //增加动态数组的长度
int *p=L.data;
L.data=(int*)malloc((L.MaxSize+len)*sizeof(int));
for(int i=0;i<L.length;i++){
L.data[i]=p[i]; //将数据复制到新区域
}
L.MaxSize=L.MaxSize+len; //顺序表最大长度增加len
free(p); //释放原来的内存空间
}
int main(){
SeqList L; //声明一个顺序表
InitList(L); //初始化顺序表
IncreaseSize(L,5);//增加顺序表的长度
return 0;
}
2.2.3 顺序表的基本操作
-
顺序表的插入操作
ListInsert(&L,i,e)：插入操作。在表L中的第i个位置上插入指定元素e。
平均时间复杂度 =
#define MaxSize 10 //定义最大长度
typedef struct{
int data[MaxSize]; //用静态的数组存放数据
int length; //顺序表的当前长度
}SqList; //顺序表的类型定义
bool ListInsert(SqList &L, int i, int e){
if(i<1||i>L.length+1) //判断i的范围是否有效
return false;
if(L.length>=MaxSize) //当前存储空间已满，不能插入
return false;
for(int j=L.length; j>=i; j--){ //将第i个元素及其之后的元素后移
L.data[j]=L.data[j-1];
}
L.data[i-1]=e; //在位置i处放入e
L.length++; //长度加1
return true;
}
int main(){
SqList L; //声明一个顺序表
InitList(L);//初始化顺序表
//...此处省略一些代码；插入几个元素
ListInsert(L,3,3); //再顺序表L的第三行插入3
return 0;
}
-
顺序表的删除操作
ListDelete(&Li,&e): 删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。
平均时间复杂度 =
#define MaxSize 10
typedef struct {
int data[MaxSize];
int length;
} SqList;
// 删除顺序表i位置的数据并存入e
bool ListDelete(SqList &L, int i, int &e) {
if (i < 1 || i > L.length) // 判断i的范围是否有效
return false;
e = L.data[i-1]; // 将被删除的元素赋值给e
for (int j = i; j < L.length; j++) //将第i个位置后的元素前移
L.data[j-1] = L.data[j];
L.length--;
return true;
}
int main() {
SqList L;
InitList(L);
int e = -1;
if (ListDelete(L, 3, e))
printf("已删除第3个元素，删除元素值为%d\n", e);
else
printf("位序i不合法，删除失败\n");
return 0;
}
- 顺序表的查找
-
顺序表的按位查找
GetElem(L,):按位查找操作。获取表L中第i个位置的元素的值
平均时间复杂度
// 静态分配的按位查找
#define MaxSize 10
typedef struct {
ElemType data[MaxSize];
int length;
}SqList;
ElemType GetElem(SqList L, int i) {
return L.data[i-1];
}
// 动态分配的按位查找
#define InitSize 10
typedef struct {
ElemType *data;
int MaxSize;
int length;
}SeqList;
ElemType GetElem(SeqList L, int i) {
return L.data[i-1];
}
-
顺序表的按值查找
LocateElem(L,e): 按值查找操作。在表L中查找具有给定关键字值的元素
平均时间复杂度 =
#define InitSize 10 //定义最大长度
typedef struct{
ElemTyp *data; //用静态的“数组”存放数据元素
int Length; //顺序表的当前长度
}SqList;
//在顺序表L中查找第一个元素值等于e的元素，并返回其位序
int LocateElem(SqList L, ElemType e){
for(int i=0; i<L.lengthl i++)
if(L.data[i] == e)
return i+1; //数组下标为i的元素值等于e，返回其位序i+1
return 0; //推出循环，说明查找失败
}
//调用LocateElem(L,9)2.3 线性表的链式表示
以上我们看完顺序表的物理存储了，然后我们学习单链表
2.3.1. 单链表的基本概念
- 单链表：用链式存储实现了线性结构。一个结点存储一个数据元素，各结点间的前后关系用一个指针表示。
- 特点：
优点：不要求大片连续空间，改变容量方便。
缺点：不可随机存取，要耗费一定空间存放指针。 - 两种实现方式：
带头结点，写代码更方便。头结点不存储数据，头结点指向的下一个结点才存放实际数据。
不带头结点，麻烦。对第一个数据结点与后续数据结点的处理需要用不同的代码逻辑，对空表和非空表的处理需要用不同的代码逻辑。
typedef struct LNode
{ //定义单链表结点类型
ElemType data; //数据域
struct LNode *next;//指针域
}LNode, *LinkList;- 强调这是一个单链表--使用 LinkList
- 强调这是一个结点--使用 LNode*
2.3.2. 单链表的实现
- 不带头节点
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode, *LinkList;
//初始化一个空的单链表
bool InitList(LinkList &L){
L = NULL; //空表，暂时还没有任何结点
return true;
}
void test(){
LinkList L; //声明一个指向单链表的头指针
//初始化一个空表
InitList(L);
...
}
//判断单链表是否为空
bool Empty(LinkList L){
return (L==NULL)
}
- 带头节点
typedef struct LNode
{
ElemType data;
struct LNode *next;
}LNode, *LinkList;
//初始化一个单链表（带头结点）
bool InitList(LinkList &L)
{
L = (LNode*) malloc(sizeof(LNode)); //头指针指向的结点——分配一个头结点（不存储数据）
if (L == NULL) //内存不足，分配失败
return false;
L -> next = NULL; //头结点之后暂时还没有结点
return true;
}
void test()
{
LinkList L; //声明一个指向单链表的指针: 头指针
//初始化一个空表
InitList(L);
//...
}
//判断单链表是否为空（带头结点）
bool Empty(LinkList L)
{
if (L->next == NULL)
return true;
else
return false;
}
带头结点和不带头结点的比较：
- 不带头结点：写代码麻烦！对第一个数据节点和后续数据节点的处理需要用不同的代码逻辑，对空表和非空表的处理也需要用不同的代码逻辑; 头指针指向的结点用于存放实际数据;
- 带头结点：头指针指向的头结点不存放实际数据,头结点指向的下一个结点才存放实际数据;
2.3.3. 单链表的插入
-
按位序插入（带头结点）
Listlnsert(&Li,e): 插入操作。在表L中的第i个位置上插入指定元素e
找到第i-1个结点(前驱结点)，将新结点插入其后；其中头结点可以看作第0个结点，故i=1时也适用。
平均时间复杂度:
typedef struct LNode
{
ElemType data;
struct LNode *next;
}LNode, *LinkList;
//在第i个位置插入元素e（带头结点）
bool ListInsert(LinkList &L, int i, ElemType e)
{
//判断i的合法性, i是位序号(从1开始)
if(i<1)
return False;
LNode *p; //指针p指向当前扫描到的结点
int j=0; //当前p指向的是第几个结点
p = L; //L指向头结点，头结点是第0个结点（不存数据）
//循环找到第i-1个结点
while(p!=NULL && j<i-1){ //如果i>lengh, p最后会等于NULL
p = p->next; //p指向下一个结点
j++;
}
if (p==NULL) //如果p指针知道最后再往后就是NULL
return false;
//在第i-1个结点后插入新结点
LNode *s = (LNode *)malloc(sizeof(LNode)); //申请一个结点
s->data = e;
s->next = p->next;
p->next = s; //将结点s连到p后,后两步千万不能颠倒qwq
return true;
}- 按位序插入（不带头结点）
Listlnsert(&L,i,e): 插入操作。在表L中的第i个位置上插入指定元素e。将新结点插入其后;
因为不带头结点，所以不存在“第0个”结点，因此！i=1 时，需要特殊处理——插入(删除)第1个元素时，需要更改头指针L;
typedef struct LNode
{
ElemType data;
struct LNode *next;
}LNode, *LinkList;
bool ListInsert(LinkList &L, int i, ElemType e)
{
if(i<1)
return false;
//插入到第1个位置时的操作有所不同！
if(i==1){
LNode *s = (LNode *)malloc(size of(LNode));
s->data =e;
s->next =L;
L=s; //头指针指向新结点
return true;
}
//i>1的情况与带头结点一样！唯一区别是j的初始值为1
LNode *p; //指针p指向当前扫描到的结点
int j=1; //当前p指向的是第几个结点
p = L; //L指向头结点，头结点是第0个结点（不存数据）
//循环找到第i-1个结点
while(p!=NULL && j<i-1){ //如果i>lengh, p最后会等于NULL
p = p->next; //p指向下一个结点
j++;
}
if (p==NULL) //i值不合法
return false;
//在第i-1个结点后插入新结点
LNode *s = (LNode *)malloc(sizeof(LNode)); //申请一个结点
s->data = e;
s->next = p->next;
p->next = s;
return true;
}-
指定结点的后插操作
InsertNextNode(LNode *p, ElemType e)；
给定一个结点p，在其之后插入元素e; 根据单链表的链接指针只能往后查找，故给定一个结点p，那么p之后的结点我们都可知，但是p结点之前的结点无法得知
typedef struct LNode
{
ElemType data;
struct LNode *next;
}LNode, *LinkList;
bool InsertNextNode(LNode *p, ElemType e)
{
if(p==NULL){
return false;
}
LNode *s = (LNode *)malloc(sizeof(LNode));
//某些情况下分配失败，比如内存不足
if(s==NULL)
return false;
s->data = e; //用结点s保存数据元素e
s->next = p->next;
p->next = s; //将结点s连到p之后
return true;
} //平均时间复杂度 = O(1)
//有了后插操作，那么在第i个位置上插入指定元素e的代码可以改成：
bool ListInsert(LinkList &L, int i, ElemType e)
{
if(i<1)
return False;
LNode *p; //指针p指向当前扫描到的结点
int j=0; //当前p指向的是第几个结点
p = L; //L指向头结点，头结点是第0个结点（不存数据）
//循环找到第i-1个结点
while(p!=NULL && j<i-1){ //如果i>lengh, p最后4鸟会等于NULL
p = p->next; //p指向下一个结点
j++;
}
return InsertNextNode(p, e)
}
-
指定结点的前插操作
设待插入结点是s，将s插入到p的前面。我们仍然可以将s插入到*p的后面。然后将p->data与s->data交换，这样既能满足了逻辑关系，又能是的时间复杂度为
//前插操作：在p结点之前插入元素e
bool InsertPriorNode(LNode *p, ElenType e){
if(p==NULL)
return false;
LNode *s = (LNode *)malloc(sizeof(LNode));
if(s==NULL) //内存分配失败
return false;
//重点来了！
s->next = p->next;
p->next = s; //新结点s连到p之后
s->data = p->data; //将p中元素复制到s
p->data = e; //p中元素覆盖为e
return true；
} 2.3.4. 单链表的删除
-
按位序删除节点
ListDelete(&L, i, &e): 删除操作，删除表L中第i个位置的元素，并用e返回删除元素的值;头结点视为“第0个”结点；
思路：找到第i-1个结点，将其指针指向第i+1个结点，并释放第i个结点
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode, *LinkList;
bool ListDelete(LinkList &L, int i, ElenType &e){
if(i<1) return false;
LNode *p; //指针p指向当前扫描到的结点
int j=0; //当前p指向的是第几个结点
p = L; //L指向头结点，头结点是第0个结点（不存数据）
//循环找到第i-1个结点
while(p!=NULL && j<i-1){ //如果i>lengh, p最后会等于NULL
p = p->next; //p指向下一个结点
j++;
}
if(p==NULL)
return false;
if(p->next == NULL) //第i-1个结点之后已无其他结点
return false;
LNode *q = p->next; //令q指向被删除的结点
e = q->data; //用e返回被删除元素的值
p->next = q->next; //将*q结点从链中“断开”
free(q) //释放结点的存储空间
return true;
}
- 指定结点的删除
bool DeleteNode(LNode *p){
if(p==NULL)
return false;
LNode *q = p->next; //令q指向*p的后继结点
p->data = p->next->data; //让p和后继结点交换数据域
p->next = q->next; //将*q结点从链中“断开”
free(q);
return true;
} //时间复杂度 = O(1)
2.3.5. 单链表的查找
-
单链表的按位查找
GetElem(L, i): 按位查找操作，获取表L中第i个位置的元素的值;
平均时间复杂度
LNode * GetElem(LinkList L, int i){
if(i<0) return NULL;
LNode *p; //指针p指向当前扫描到的结点
int j=0; //当前p指向的是第几个结点
p = L; //L指向头结点,头结点是第0个结点(不存数据)
while(p!=NULL && j<i){ //循环找到第i个结点
p = p->next;
j++;
}
return p; //返回p指针指向的值
}
-
单链表的按值查找
LocateElem(L, e):按值查找操作，在表L中查找具有给定关键字值的元素;
平均时间复杂度:
LNode * LocateElem(LinkList L, ElemType e){
LNode *P = L->next; //p指向第一个结点
//从第一个结点开始查找数据域为e的结点
while(p!=NULL && p->data != e){
p = p->next;
}
return p; //找到后返回该结点指针，否则返回NULL
}
-
求单链表的长度
Length(LinkList L)：计算单链表中数据结点（不含头结点）的个数，需要从第一个结点看是顺序依次访问表中的每个结点。
算法的时间复杂度为
int Length(LinkList L){
int len=0; //统计表长
LNode *p = L;
while(p->next != NULL){
p = p->next;
len++;
}
return len;
}2.3.6. 单链表的建立
- Step 1:初始化一个单链表
- Step 2:每次取一个数据元素，插入到表尾/表头
-
尾插法建立单链表
平均时间复杂度
思路：每次将新节点插入到当前链表的表尾，所以必须增加一个尾指针r,使其始终指向当前链表的尾结点。好处：生成的链表中结点的次序和输入数据的顺序会一致。
// 使用尾插法建立单链表L
LinkList List_TailInsert(LinkList &L){
int x; //设ElemType为整型int
L = (LinkList)malloc(sizeof(LNode)); //建立头结点(初始化空表)
LNode *s, *r = L; //r为表尾指针
scanf("%d", &x); //输入要插入的结点的值
while(x!=9999){ //输入9999表示结束
s = (LNode *)malloc(sizeof(LNode));
s->data = x;
r->next = s;
r = s; //r指针指向新的表尾结点
scanf("%d", &x);
}
r->next = NULL; //尾结点指针置空
return L;
}
-
头插法建立单链表
平均时间复杂度
LinkList List_HeadInsert(LinkList &L){ //逆向建立单链表
LNode *s;
int x;
L = (LinkList)malloc(sizeof(LNode)); //建立头结点
L->next = NULL; //初始为空链表,这步不能少！
scanf("%d", &x); //输入要插入的结点的值
while(x!=9999){ //输入9999表结束
s = (LNode *)malloc(sizeof(LNode)); //创建新结点
s->data = x;
s->next = L->next;
L->next = s; //将新结点插入表中，L为头指针
scanf("%d", &x);
}
return L;
}
-
链表的逆置
算法思想：逆置链表初始为空，原表中结点从原链表中依次“删除”，再逐个插入逆置链表的表头（即“头插”到逆置链表中），使它成为逆置链表的“新”的第一个结点，如此循环，直至原链表为空；
LNode *Inverse(LNode *L)
{
LNode *p, *q;
p = L->next; //p指针指向第一个结点
L->next = NULL; //头结点指向NULL
while (p != NULL){
q = p;
p = p->next;
q->next = L->next;
L->next = q;
}
return L;
2.3.7. 双链表
- 双链表中节点类型的描述
typedef struct DNode{ //定义双链表结点类型
ElemType data; //数据域
struct DNode *prior, *next; //前驱和后继指针
}DNode, *DLinklist;
- 双链表的初始化（带头结点）
typedef struct DNode{ //定义双链表结点类型
ElemType data; //数据域
struct DNode *prior, *next; //前驱和后继指针
}DNode, *DLinklist;
//初始化双链表
bool InitDLinkList(Dlinklist &L){
L = (DNode *)malloc(sizeof(DNode)); //分配一个头结点
if(L==NULL) //内存不足，分配失败
return false;
L->prior = NULL; //头结点的prior指针永远指向NULL
L->next = NULL; //头结点之后暂时还没有结点
return true;
}
void testDLinkList(){
//初始化双链表
DLinklist L; // 定义指向头结点的指针L
InitDLinkList(L); //申请一片空间用于存放头结点，指针L指向这个头结点
//...
}
//判断双链表是否为空
bool Empty(DLinklist L){
if(L->next == NULL) //判断头结点的next指针是否为空
return true;
else
return false;
}-
双链表的插入操作
后插操作
InsertNextDNode(p, s): 在p结点后插入s结点
bool InsertNextDNode(DNode *p, DNode *s){ //将结点 *s 插入到结点 *p之后
if(p==NULL || s==NULL) //非法参数
return false;
s->next = p->next;
if (p->next != NULL) //p不是最后一个结点=p有后继结点
p->next->prior = s;
s->prior = p;
p->next = s;
return true;
}-
双链表的删除操作
删除p节点的后继节点
//删除p结点的后继结点
bool DeletNextDNode(DNode *p){
if(p==NULL) return false;
DNode *q =p->next; //找到p的后继结点q
if(q==NULL) return false; //p没有后继结点;
p->next = q->next;
if(q->next != NULL) //q结点不是最后一个结点
q->next->prior=p;
free(q);
return true;
}
//销毁一个双链表
bool DestoryList(DLinklist &L){
//循环释放各个数据结点
while(L->next != NULL){
DeletNextDNode(L); //删除头结点的后继结点
free(L); //释放头结点
L=NULL; //头指针指向NULL
}
}
-
双链表的遍历操作
前向遍历
while(p!=NULL){
//对结点p做相应处理，eg打印
p = p->prior;
}后向遍历
while(p!=NULL){
//对结点p做相应处理，eg打印
p = p->next;
}注意：双链表不可随机存取，按位查找和按值查找操作都只能用遍历的方式实现，时间复杂度为
2.3.8. 循环链表
-
循环单链表
最后一个结点的指针不是NULL,而是指向头结点
typedef struct LNode{
ElemType data;
struct LNode *next;
}DNode, *Linklist;
/初始化一个循环单链表
bool InitList(LinkList &L){
L = (LNode *)malloc(sizeof(LNode)); //分配一个头结点
if(L==NULL) //内存不足，分配失败
return false;
L->next = L; //头结点next指针指向头结点
return true;
}
//判断循环单链表是否为空（终止条件为p或p->next是否等于头指针）
bool Empty(LinkList L){
if(L->next == L)
return true; //为空
else
return false;
}
//判断结点p是否为循环单链表的表尾结点
bool isTail(LinkList L, LNode *p){
if(p->next == L)
return true;
else
return false;
}单链表和循环单链表的比较：
单链表：从一个结点出发只能找到该结点后续的各个结点；对链表的操作大多都在头部或者尾部；设立头指针，从头结点找到尾部的时间复杂度=O(n)，即对表尾进行操作需要O(n)的时间复杂度;
循环单链表：从一个结点出发，可以找到其他任何一个结点；设立尾指针，从尾部找到头部的时间复杂度为O(1)，即对表头和表尾进行操作都只需要O(1)的时间复杂度;
循环单链表优点：从表中任一节点出发均可找到表中其他结点。
-
循环双链表
表头结点的prior指向表尾结点，表尾结点的next指向头结点
typedef struct DNode{
ElemType data;
struct DNode *prior, *next;
}DNode, *DLinklist;
//初始化空的循环双链表
bool InitDLinkList(DLinklist &L){
L = (DNode *) malloc(sizeof(DNode)); //分配一个头结点
if(L==NULL) //内存不足，分配失败
return false;
L->prior = L; //头结点的prior指向头结点
L->next = L; //头结点的next指向头结点
}
void testDLinkList(){
//初始化循环单链表
DLinklist L;
InitDLinkList(L);
//...
}
//判断循环双链表是否为空
bool Empty(DLinklist L){
if(L->next == L)
return true;
else
return false;
}
//判断结点p是否为循环双链表的表尾结点
bool isTail(DLinklist L, DNode *p){
if(p->next == L)
return true;
else
return false;
}
- 循环链表的插入
bool InsertNextDNode(DNode *p, DNode *s){
s->next = p->next;
p->next->prior = s;
s->prior = p;
p->next = s;- 循环链表的删除
//删除p的后继结点q
p->next = q->next;
q->next->prior = p;
free(q);2.3.9. 静态链表
-
单链表：各个结点散落在内存中的各个角落，每个结点有指向下一个节点的指针(下一个结点在内存中的地址);
-
静态链表：用数组的方式来描述线性表的链式存储结构: 分配一整片连续的内存空间，各个结点集中安置，包括了——数据元素and下一个结点的数组下标(游标)
- 静态链表用代码表示
#define MaxSize 10 //静态链表的最大长度
struct Node{ //静态链表结构类型的定义
ElemType data; //存储数据元素
int next; //下一个元素的数组下标(游标)
};
//用数组定义多个连续存放的结点
void testSLinkList(){
struct Node a[MaxSize]; //数组a作为静态链表, 每一个数组元素的类型都是struct Node
//...
}或者是：
#define MaxSize 10 //静态链表的最大长度
typedef struct{ //静态链表结构类型的定义
ELemType data; //存储数据元素
int next; //下一个元素的数组下标
}SLinkList[MaxSize];
void testSLinkList(){
SLinkList a;
}相当于：
#define MaxSize 10 //静态链表的最大长度
struct Node{ //静态链表结构类型的定义
ElemType data; //存储数据元素
int next; //下一个元素的数组下标(游标)
};
typedef struct Node SLinkList[MaxSize]; //重命名struct Node，用SLinkList定义“一个长度为MaxSize的Node型数组;
2.3.10. 顺序表和链表的比较
【逻辑结构】
- 顺序表和链表都属于线性表，都是线性结构
【存储结构】
-
顺序表：顺序存储
- 优点：支持随机存取，存储密度高
- 缺点：大片连续空间分配不方便，改变容量不方便
-
链表：链式存储
- 优点：离散的小空间分配方便，改变容量方便
- 缺点：不可随机存取，存储密度低
【基本操作 - 创建】
- 顺序表：需要预分配大片连续空间。若分配空间过小，则之后不方便拓展容量；若分配空间过大，则浪费内存资源；
- 静态分配：静态数组，容量不可改变
- 动态分配：动态数组，容量可以改变，但是需要移动大量元素，时间代价高（malloc(),free()）
- 链表：只需要分配一个头结点或者只声明一个头指针
【基本操作 - 销毁】
- 静态数组——系统自动回收空间
- 动态分配：动态数组——需要手动free()
【基本操作-增/删】
-
顺序表：插入/删除元素要将后续元素后移/前移；时间复杂度=O(n)，时间开销主要来自于移动元素；
-
链表：插入/删除元素只需要修改指针；时间复杂度=O(n)，时间开销主要来自查找目标元素
【基本操作-查】
顺序表
- 按位查找：O(1)
- 按值查找：O(n)，若表内元素有序，可在O(log2n)时间内找到
链表
- 按位查找：O(n)
- 按值查找：O(n)
顺序、链式、静态、动态四种存储方式的比较
顺序存储的固有特点：
- 逻辑顺序与物理顺序一直，本质上是用数组存储线性表的各个元素（即随机存取）；存储密度大，存储空间利用率高。
链式存储的固有特点：
- 元素之间的关系采用这些元素所在的节点的“指针”信息表示（插、删不需要移动节点）。
静态存储的固有特点：
- 在程序运行的过程中不要考虑追加内存的分配问题。
动态存储的固有特点：
- 可动态分配内存；有效的利用内存资源，使程序具有可扩展性。
第三章 栈和队列
3.1. 栈
3.1.1. 栈的基本概念
- 只允许在一端(栈顶top)进行插入或删除操作的受限的线性表。
- 后进先出（Last In First Out）LIFO。
- 进栈顺序：a1 > a2 > a3 > a4 > a5
- 出栈顺序：a5 > a4 > a3 > a2 > a1
3.1.2. 栈的基本操作
- InitStack(&S)：初始化栈。构造一个空栈 S，分配内存空间。
- DestroyStack(&S)：销毁栈。销毁并释放栈 S 所占用的内存空间。
- Push(&S, x)：进栈。若栈 S 未满，则将 x 加入使其成为新的栈顶元素。
- Pop(&S, &x)：出栈。若栈 S 非空，则弹出（删除）栈顶元素，并用 x 返回。
- GetTop(S, &x)：读取栈顶元素。若栈 S 非空，则用 x 返回栈顶元素。
- StackEmpty(S)：判空。断一个栈 S 是否为空，若 S 为空，则返回 true，否则返回 false。
3.1.3. 栈的顺序存储实现
【顺序栈的定义】
#define MaxSize 10 //定义栈中元素的最大个数
typedef struct{
ElemType data[MaxSize]; //静态数组存放栈中元素
int top; //栈顶元素
}SqStack;
void testStack(){
SqStack S; //声明一个顺序栈(分配空间)
//连续的存储空间大小为 MaxSize*sizeof(ElemType)
}【顺序栈的初始化】
#define MaxSize 10
typedef struct{
ElemType data[MaxSize];
int top;
}SqStack;
// 初始化栈
void InitStack(SqStack &S){
S.top = -1; //初始化栈顶指针
}
// 判断栈是否为空
bool StackEmpty(SqStack S){
if(S.top == -1)
return true;
else
return false;
}
【顺序栈的入栈出栈】
// 新元素进栈
bool Push(SqStack &S, ElemType x){ // 判断栈是否已满
if(S.top == MaxSize - 1)
return false;
S.data[++S.top] = x;
return true;
}
// 出栈
bool Pop(SqStack &x, ElemType &x){ // 判断栈是否为空
if(S.top == -1)
return false;
x = S.data[S.top--];
return true;
}
【读取栈顶元素】
// 读栈顶元素
bool GetTop(SqStack S, ElemType &x){
if(S.top == -1)
return false;
x = S.data[S.top];
return true;
}
- 进栈操作：栈不满时，栈顶指针先加1，再送值到栈顶元素。
S.data[++S.top] = x - 出栈操作：栈非空时，先取栈顶元素值，再将栈顶指针减1。x = S.data[S.top--]
- 栈空条件：S.top==-
- 栈满条件：S.top==MaxSize-1
- 栈长：S.top+1
【共享栈(两个栈共享同一片空间)】
- 共享栈--特殊的顺序栈
- 将栈底设计在共享空间的两端，栈顶向中间靠拢
#define MaxSize 10 //定义栈中元素的最大个数
typedef struct{
ElemType data[MaxSize]; //静态数组存放栈中元素
int top0; //0号栈栈顶指针
int top1; //1号栈栈顶指针
}ShStack;
//初始化栈
void InitSqStack(ShStack &S){
S.top0 = -1; //初始化栈顶指针
S.top1 = MaxSize;
}3.1.4. 栈的链式存储
【链栈的定义】
- 定义：采用链式存储的栈称为链栈。
- 优点：链栈的优点是便于多个栈共享存储空间和提高其效率，且不存在栈满上溢的情况。
- 特点：进栈和出栈都只能在栈顶一端进行(链头作为栈顶)
链表的头部作为栈顶，意味着：
- 1. 在实现数据"入栈"操作时，需要将数据从链表的头部插入；
- 2. 在实现数据"出栈"操作时，需要删除链表头部的首元节点；
因此，链栈实际上就是一个只能采用头插法插入或删除数据的链表;
栈的链式存储结构可描述为：
【链栈的定义】
typedef struct Linknode{
ElemType data; //数据域
Linknode *next; //指针域
}Linknode,*LiStack;
void testStack(){
LiStack L; //声明一个链栈
}
【链栈的初始化】
typedef struct Linknode{
ElemType data;
Linknode *next;
}Linknode,*LiStack;
// 初始化栈
bool InitStack(LiStack &L){
L = (Linknode *)malloc(sizeof(Linknode));
if(L == NULL)
return false;
L->next = NULL;
return true;
}
// 判断栈是否为空
bool isEmpty(LiStack &L){
if(L->next == NULL)
return true;
else
return false;
}
【入栈出栈】
// 新元素入栈
bool pushStack(LiStack &L,ElemType x){
Linknode *s = (Linknode *)malloc(sizeof(Linknode));
if(s == NULL)
return false;
s->data = x;
// 头插法
s->next = L->next;
L->next = s;
return true;
}
// 出栈
bool popStack(LiStack &L, int &x){
// 栈空不能出栈
if(L->next == NULL)
return false;
Linknode *s = L->next;
x = s->data;
L->next = s->next;
free(s);
return true;
}
3.2. 队列
3.2.1. 队列的基本概念
- 只允许在表的一端(队尾)插入，表的另一端(队头)进行删除操作的受限的线性表。
- 特点：先进先出（先入队的元素先出队）、FIFO（First In First Out）。
3.2.2. 队列的基本操作
- InitQueue(&Q)：初始化队列，构造一个空队列Q。
- QueueEmpty(Q)：判队列空，若队列Q为空返回true，否则返回false。
- EnQueue(&Qx)：入队，若队列Q未满，则将x加入使之成为新的队尾。
- DeQueue(&Q&x)：出队，若队列Q非空，则删除队头元素，并用x返回。
- GetHead(Q&x)：读队头元素，若队列Q非空则用x返回队头元素。
- ClearQueue(&Q)：销毁队列，并释放队列Q占用的内存空间。
3.2.3. 队列的顺序存储实现
- 队头指针：指向队头元素
- 队尾指针：指向队尾元素的下一个位置
【顺序队列的定义】
#define MaxSize 10; //定义队列中元素的最大个数
typedef struct{
ElemType data[MaxSize]; //用静态数组存放队列元素
int front, rear; //队头指针和队尾指针
}SqQueue;
void test{
SqQueue Q; //声明一个队列
}
【顺序队列的初始化】
#define MaxSize 10;
typedef struct{
ElemType data[MaxSize];
int front, rear;
}SqQueue;
// 初始化队列
void InitQueue(SqQueue &Q){
// 初始化时，队头、队尾指针指向0
// 队尾指针指向的是即将插入数据的数组下标
// 队头指针指向的是队头元素的数组下标
Q.rear = Q.front = 0;
}
// 判断队列是否为空
bool QueueEmpty(SqQueue Q){
if(Q.rear == Q.front)
return true;
else
return false;
}
【入队出队（循环队列）】
// 新元素入队
bool EnQueue(SqQueue &Q, ElemType x){
// 如果队列已满直接返回
if((Q.rear+1)%MaxSize == Q.front) //牺牲一个单元区分队空和队满
return false;
Q.data[Q.rear] = x;
Q.rear = (Q.rear+1)%MaxSize;
return true;
}
// 出队
bool DeQueue(SqQueue &Q, ElemType &x){
// 如果队列为空直接返回
if(Q.rear == Q.front)
return false;
x = Q.data[Q.front];
Q.front = (Q.front+1)%MaxSize;
return true;
}
【获得队头元素】
// 获取队头元素并存入x
bool GetHead(SqQueue &Q, ElemType &x){
if(Q.rear == Q.front)
return false;
x = Q.data[Q.front];
return true;
}
- 循环队列不能使用Q.rear == Q.front作为判空的条件，因为当队列已满时也符合该条件，会与判空发生冲突！
解决方法一：牺牲一个单元来区分队空和队满，即将(Q.rear+1)%MaxSize == Q.front作为判断队列是否已满的条件。（主流方法）
解决方法二：设置 size 变量记录队列长度。
#define MaxSize 10;
typedef struct{
ElemType data[MaxSize];
int front, rear;
int size;
}SqQueue;
// 初始化队列
void InitQueue(SqQueue &Q){
Q.rear = Q.front = 0;
Q.size = 0;
}
// 判断队列是否为空
bool QueueEmpty(SqQueue 0){
if(Q.size == 0)
return true;
else
return false;
}
// 新元素入队
bool EnQueue(SqQueue &Q, ElemType x){
if(Q.size == MaxSize)
return false;
Q.size++;
Q.data[Q.rear] = x;
Q.rear = (Q.rear+1)%MaxSize;
return true;
}
// 出队
bool DeQueue(SqQueue &Q, ElemType &x){
if(Q.size == 0)
return false;
Q.size--;
x = Q.data[Q.front];
Q.front = (Q.front+1)%MaxSize;
return true;
}
解决方法三：设置 tag 变量记录队列最近的操作。（tag=0：最近进行的是删除操作；tag=1 ：最近进行的是插入操作）
#define MaxSize 10;
typedef struct{
ElemType data[MaxSize];
int front, rear;
int tag;
}SqQueue;
// 初始化队列
void InitQueue(SqQueue &Q){
Q.rear = Q.front = 0;
Q.tag = 0;
}
// 判断队列是否为空，只有tag==0即出队的时候才可能为空
bool QueueEmpty(SqQueue 0){
if(Q.front == Q.rear && Q.tag == 0)
return true;
else
return false;
}
// 新元素入队
bool EnQueue(SqQueue &Q, ElemType x){
if(Q.rear == Q.front && tag == 1)
return false;
Q.data[Q.rear] = x;
Q.rear = (Q.rear+1)%MaxSize;
Q.tag = 1;
return true;
}
// 出队
bool DeQueue(SqQueue &Q, ElemType &x){
if(Q.rear == Q.front && tag == 0)
return false;
x = Q.data[Q.front];
Q.front = (Q.front+1)%MaxSize;
Q.tag = 0;
return true;
}
3.2.4. 队列的链式存储实现
【链队列的定义】
// 链式队列结点
typedef struct LinkNode{
ElemType data;
struct LinkNode *next;
}
// 链式队列
typedef struct{
// 头指针和尾指针
LinkNode *front, *rear;
}LinkQueue;
【 链队列的初始化（带头结点）】
typedef struct LinkNode{
ElemType data;
struct LinkNode *next;
}LinkNode;
typedef struct{
LinkNode *front, *rear;
}LinkQueue;
// 初始化队列
void InitQueue(LinkQueue &Q){
// 初始化时，front、rear都指向头结点
Q.front = Q.rear = (LinkNode *)malloc(sizeof(LinkNode));
Q.front -> next = NULL;
}
// 判断队列是否为空
bool IsEmpty(LinkQueue Q){
if(Q.front == Q.rear)
return true;
else
return false;
}
【入队出队（带头结点）】
// 新元素入队
void EnQueue(LinkQueue &Q, ElemType x){
LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
s->data = x;
s->next = NULL;
Q.rear->next = s;
Q.rear = s;
}
// 队头元素出队
bool DeQueue(LinkQueue &Q, ElemType &x){
if(Q.front == Q.rear)
return false;
LinkNode *p = Q.front->next;
x = p->data;
Q.front->next = p->next;
// 如果p是最后一个结点，则将队头指针也指向NULL
if(Q.rear == p)
Q.rear = Q.front;
free(p);
return true;
}
【不带头结点的链队列操作】
typedef struct LinkNode{
ElemType data;
struct LinkNode *next;
}LinkNode;
typedef struct{
LinkNode *front, *rear;
}LinkQueue;
// 初始化队列
void InitQueue(LinkQueue &Q){
// 不带头结点的链队列初始化，头指针和尾指针都指向NULL
Q.front = NULL;
Q.rear = NULL;
}
// 判断队列是否为空
bool IsEmpty(LinkQueue Q){
if(Q.front == NULL)
return true;
else
return false;
}
// 新元素入队
void EnQueue(LinkQueue &Q, ElemType x){
LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
s->data = x;
s->next = NULL;
// 第一个元素入队时需要特别处理
if(Q.front == NULL){
Q.front = s;
Q.rear = s;
}else{
Q.rear->next = s;
Q.rear = s;
}
}
//队头元素出队
bool DeQueue(LinkQueue &Q, ElemType &x){
if(Q.front == NULL)
return false;
LinkNode *s = Q.front;
x = s->data;
if(Q.front == Q.rear){
Q.front = Q.rear = NULL;
}else{
Q.front = Q.front->next;
}
free(s);
return true;
}
3.2.5. 双端队列
双端队列定义
- 双端队列是允许从两端插入、两端删除的线性表。
- 如果只使用其中一端的插入、删除操作，则等同于栈。
- 输入受限的双端队列：允许一端插入，两端删除的线性表。
- 输出受限的双端队列：允许两端插入，一端删除的线性表。
双端队列考点：判断输出序列的合法化
- 例：数据元素输入序列为 1，2，3，4，判断 4! = 24 个输出序列的合法性
输入受限的双端队列：只有 4213 和 4231 不合法
输出受限的双端队列：只有 4132 和 4231 不合法
3.3. 栈与队列的应用
3.3.1 栈在括号匹配中的应用
-
用栈实现括号匹配：
- 最后出现的左括号最先被匹配 （栈的特性——LIFO）。
- 遇到左括号就入栈。
- 遇到右括号，就“消耗”一个左括号（出栈）。
-
匹配失败情况：
- 扫描到右括号且栈空，则该右括号单身。
- 扫描完所有括号后，栈非空，则该左括号单身。
- 左右括号不匹配。
#define MaxSize 10
typedef struct{
char data[MaxSize];
int top;
}SqStack;
void InitStack(SqStack &S);
bool StackEmpty(SqStack &S);
bool Push(SqStack &S, char x);
bool Pop(SqStack &S, char &x);
// 判断长度为length的字符串str中的括号是否匹配
bool bracketCheck(char str[], int length){
SqStack S;
InitStack(S);
// 遍历str
for(int i=0; i<length; i++){
// 扫描到左括号，入栈
if(str[i] == '(' || str[i] == '[' || str[i] == '{'){
Push(S, str[i]);
}else{
// 扫描到右括号且栈空直接返回
if(StackEmpty(S))
return false;
char topElem;
// 用topElem接收栈顶元素
Pop(S, topElem);
// 括号不匹配
if(str[i] == ')' && topElem != '(' )
return false;
if(str[i] == ']' && topElem != '[' )
return false;
if(str[i] == '}' && topElem != '{' )
return false; }
}
// 扫描完毕若栈空则说明字符串str中括号匹配
return StackEmpty(S);
}
3.3.2. 栈在表达式求值中的应用
- 中缀表达式：中缀表达式是一种通用的算术或逻辑公式表示方法，运算符以中缀形式处于操作数的中间。对于计算机来说中缀表达式是很复杂的，因此计算表达式的值时，通常需要先将中缀表达式转换为前缀或后缀表达式，然后再进行求值。
- 前缀表达式（波兰表达式）：前缀表达式的运算符位于两个操作数之前。
- 后缀表达式（逆波兰表达式）：后缀表达式的运算符位于两个操作数之后。
中缀表达式转后缀表达式-手算
步骤1： 确定中缀表达式中各个运算符的运算顺序
步骤2： 选择下一个运算符，按照[左操作数 右操作数 运算符]的方式组合成一个新的操作数
步骤3： 如果还有运算符没被处理，继续步骤2
“左优先”原则: 只要左边的运算符能先计算，就优先算左边的 (保证运算顺序唯一)；
中缀：A + B - C * D / E + F
① ④ ② ③ ⑤
后缀：A B + C D * E / - F +
后缀表达式的计算—手算:
从左往右扫描，每遇到一个运算符，就让运算符前面最近的两个操作数执行对应的运算，合体为一个操作数
后缀表达式的计算—机算
用栈实现后缀表达式的计算（栈用来存放当前暂时不能确定运算次序的操作数）
步骤1: 从左往后扫描下一个元素，直到处理完所有元素;
步骤2: 若扫描到操作数，则压入栈，并回到步骤1;否则执行步骤3;
步骤3: 若扫描到运算符，则弹出两个栈顶元素，执行相应的运算，运算结果压回栈顶，回到步骤1;
中缀表达式转后缀表达式(机算)
初始化一个栈，用于保存暂时还不能确定运算顺序的运算符从左到右处理各个元素，直到末尾。可能遇到三种情况:
1.遇到操作数：直接加入后缀表达式。
2.遇到界限符：遇到“(”直接入栈；遇到“)”则依次弹出栈内运算符并加入后缀表达式，直到 弹出“(”为止。注意：“(”不加入后缀表达式。
3.遇到运算符：依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式， 若碰到“(” 或栈空则停止。之后再把当前运算符入栈。
#define MaxSize 40
typedef struct{
char data[MaxSize];
int top;
}SqStack;
typedef struct{
char data[MaxSize];
int front,rear;
}SqQueue;
void InitStack(SqStack &S);
bool StackEmpty(SqStack S);
bool Push(SqStack &S, char x);
bool Pop(SqStack &S, char &x);
void InitQueue(SqQueue &Q);
bool EnQueue(LQueue &Q, char x);
bool DeQueue(LQueue &Q, char &x);
bool QueueEmpty(SqQueue Q);
// 判断元素ch是否入栈
int JudgeEnStack(SqStack &S, char ch){
char tp = S.data[S->top];
// 如果ch是a~z则返回-1
if(ch >= 'a' && ch <= 'z')
return -1;
// 如果ch是+、-、*、/且栈顶元素优先级大于等于ch则返回0
else if(ch == '+' && (tp == '+' || tp == '-' || tp == '*' || tp == '/'))
return 0;
else if(ch == '-' && (tp == '+' || tp == '-' || tp == '*' || tp == '/'))
return 0;
else if(ch == '*' && (tp == '*' || tp == '/'))
return 0;
else if(ch == '/' && (tp == '*' || tp == '/'))
return 0;
// 如果ch是右括号则返回2
else if(ch == ')')
return 2;
// 其他情况ch入栈，返回1
else return 1;
}
// 中缀表达式转后缀表达式
int main(int argc, char const *argv[]) {
SqStack S;
SqQueue Q;
InitStack(S);
InitQueue(Q);
char ch;
printf("请输入表达式，以“#”结束：");
scanf("%c", &ch);
while (ch != '#'){
// 当栈为空时
if(StackEmpty(&S)){
// 如果输入的是数即a~z，直接入队
if(ch >= 'a' && ch <= 'z')
EnQueue(Q, ch);
// 如果输入的是运算符，直接入栈
else
Puch(S, ch);
}else{
// 当栈非空时，判断ch是否需要入栈
int n = JudgeEnStack(S, ch);
// 当输入是数字时直接入队
if(n == -1){
EnQueue(Q, ch);
}else if(n == 0){
// 当输入是运算符且运算符优先级不高于栈顶元素时
while (1){
// 取栈顶元素入队
char tp;
Pop(S, tp);
EnQueue(Q, tp);
// 再次判断是否需要入栈
n = JudgeEnStack(S, ch);
// 当栈头优先级低于输入运算符或者栈头为‘)’时，入栈并跳出循环
if(n != 0){
EnStack(S, ch);
break;
}
}
}else if(n == 2){
// 当出现‘)’时 将()中间的运算符全部出栈入队
while(1){
char tp;
Pop(S, tp);
if(tp == '(')
break;
else
EnQueue(Q, tp);
}
}else{
// 当运算符优先级高于栈顶元素或出现‘(’时直接入栈
Push(S, ch);
}
}
scanf("%c", &ch);
}
// 将最后栈中剩余的运算符出栈入队
while (!StackEmpty(S)){
char tp;
Pop(S, tp);
EnQueue(Q, tp);
}
// 输出队中元素
while (!QueueEmpety(Q)){
printf("%c ", DeQueue(Q));
}
return 0;
}
用栈实现中缀表达式的计算:
1.初始化两个栈，操作数栈和运算符栈；
2.若扫描到操作数，压入操作数栈；
3.若扫描到运算符或界限符，则按照“中缀转后缀”相同的逻辑压入运算符栈(期间也会弹出运算符，每当弹出一个运算符时，就需要再弹出两个操作数栈的栈顶元素并执行相应运算，运算结果再压回操作数栈)
3.3.3. 栈在递归中的应用
函数调用的特点：最后被调用的函数最先执行结束(LIFO)
函数调用时，需要用一个栈存储：
- 调用返回地址
- 实参
- 局部变量
递归调用时，函数调用栈称为 “递归工作栈”:
- 每进入一层递归，就将递归调用所需信息压入栈顶；
- 每退出一层递归，就从栈顶弹出相应信息；
缺点：太多层递归可能回导致栈溢出；适合用“递归”算法解决：可以把原始问题转换为属性相同，但规模较小的问题
3.3.4. 队列的应用
- 队列应用：树的层次遍历
- 队列应用：图的广度优先遍历
- 队列应用：操作系统中多个进程争抢着使用有限的系统资源时，先来先服务算法（First Come First Service）是是一种常用策略。
3.4. 特殊矩阵的压缩存储
3.4.1 数组的存储
一维数组的存储：各数组元素大小相同，且物理上连续存放。设起始地址为LOC，则数组元素的存放地址 = LOC + i * sizeof(ElemType) (0≤i<10)
二维数组的存储 ：
1. M行N列的二维数组中，设起始地址为LOC，若按行优先存储，则的存储地址 =
2. M行N列的二维数组中，设起始地址为 LOC，若按列优先存储，则的存储地址 =
3.4.2 对称矩阵的压缩存储
对称矩阵的压缩存储：若n阶方阵中任意一个元素,都有则该矩阵为对称矩阵，对于对称矩阵，只需存储主对角线+下三角区。若按照行优先原则将各元素存入一维数组中，即存入到数组中，那么数组共有个元素。对于k，有：
3.4.3 三角矩阵的压缩存储
-
下三角矩阵：除了主对角线和下三角区，其余的元素都相同。
-
上三角矩阵：除了主对角线和上三角区，其余的元素都相同。
-
压缩存储策略：按行优先原则将主对角线+下三角区存入一维数组中，并在最后一个位置存储常量。即存入到数组中，那么数组共有
个元素。对于k，有：
3.4.4 三对角矩阵的压缩存储
三对角矩阵，又称带状矩阵: 当时，有。对于三对角矩阵，按行优先原则，只存储带状部分，即存入到数组中，那么。若已知数组下标k，则
。
3.4.5 稀疏矩阵的压缩存储
稀疏矩阵的非零元素远远少于矩阵元素的个数。压缩存储策略：
- 顺序存储：三元组 <行，列，值>
- 链式存储：十字链表法
第四章 串
4.1. 串的基本概念
- 串，即字符串 (String) 是由零个或多个字符组成的有限序列。一般记为S='a1a2.....·an'(n>=0)
- 其中，S是串名，单引号括起来的字符序列是串的值;a;可以是字母、数字或其他字符;串中字符的个数n称为串的长度。n =0时的串称为空串 。
例:
S="HelloWorld!"
T='iPhone 11 Pro Max?'- 子串:串中任意个连续的字符组成的子序列。
- 主串:包含子串的串。
- 字符在主串中的位置:字符在串中的序号。子串在主串中的位置:子串的第一个字符在主串中的位置。
- 串是一种特殊的线性表，数据元素之间呈线性关系
- 串的数据对象限定为字符集（如中文字符、英文字符、数字字符、标点字符等）
- 串的基本操作，如增删改查等通常以子串为操作对象。
4.2. 串的基本操作
假设有串 T = '', S = 'iPhone 11 Pro Max?', W = 'Pro'
- StrAssign(&T, chars)： 赋值操作，把串T赋值为chars。
- StrCopy(&T, S):：复制操作，把串S复制得到串T。
- StrEmpty(S)：判空操作，若S为空串，则返回TRUE，否则返回False。
- StrLength(S)：求串长，返回串S的元素个数。
- ClearString(&S)：清空操作，将S清为空串。
- DestroyString(&S)：销毁串，将串S销毁（回收存储空间）。
- Concat(&T, S1, S2)：串联接，用T返回由S1和S2联接而成的新串。
- SubString(&Sub, S, pos, len)求子串，用Sub返回串S的第pos个字符起长度为len的子串.
- Index(S, T)：定位操作，若主串S中存在与串T值相同的子串，则返回它再主串S中第一次出现的位置，否则函数值为0.
- StrCompare(S, T)：串的比较操作，参照英文词典排序方式；若S > T,返回值>0; S = T,返回值=0 (需要两个串完全相同) ; S < T,返回值<0.
4.3. 串的存储实现
4.3.1 静态数组实现
静态数组实现(定长顺序存储)
#define MAXLEN 255 //预定义最大串长为255
typedef struct{
char ch[MAXLEN]; //静态数组实现（定长顺序存储）
//每个分量存储一个字符
//每个char字符占1B
int length; //串的实际长度
}SString;
动态数组实现( 堆分配存储)
typedef struct{
char *ch; //按串长分配存储区，ch指向串的基地址
int length; //串的实际长度
}HString;
HString S;
S.ch = (char*)malloc(MAXLEN *sizeof(char));
S.length = 0;4.3.2 基本操作的实现
#define MAXLEN 255
typedef struct{
char ch[MAXLEN];
int length;
}SString;
// 1. 求子串
bool SubString(SString &Sub, SString S, int pos, int len){
//子串范围越界
if (pos+len-1 > S.length)
return false;
for (int i=pos; i<pos+len; i++)
Sub.cn[i-pos+1] = S.ch[i];
Sub.length = len;
return true;
}
// 2. 比较两个串的大小
int StrCompare(SString S, SString T){
for (int i; i<S.length && i<T.length; i++){
if(S.ch[i] != T.ch[i])
return S.ch[i] - T.ch[i];
}
//扫描过的所有字符都相同，则长度长的串更大
return S.length - T.length;
}
// 3. 定位操作
int Index(SString S, SString T){
int i=1;
n = StrLength(S);
m = StrLength(T);
SString sub; //用于暂存子串
while(i<=n-m+1){
SubString(Sub,S,i,m);
if(StrCompare(Sub,T)!=0)
++i;
else
return i; // 返回子串在主串中的位置
}
return 0; //S中不存在与T相等的子串
}
4.4. 串的朴素模式匹配
- 串的模式匹配：在主串中找到与模式串相同的子串，并返回其所在主串中的位置。
朴素模式匹配算法(简单模式匹配算法) 思想:
- 将主串中与模式串长度相同的子串搞出来，挨个与模式串对比当子串与模式串某个对应字符不匹配时，就立即放弃当前子串，转而检索下一个子串。
- 若模式串长度为m，主串长度为n，则直到匹配成功/匹配失败最多需要(n-m+1)*m 次比较最坏时间复杂度: 0(nm)
- 最坏情况:每个子串的前m-1个字符都和模式串匹配，只有第m个字符不匹配。
- 比较好的情况:每个子串的第1个字符就与模式串不匹配
串的朴素模式匹配算法代码实现：
// 在主串S中找到与模式串T相同的子串并返回其位序，否则返回0
int Index(SString S, SString T){
int k=1;
int i=k, j=1;
while(i<=S.length && j<=T.length){
if(S.ch[i] == T.ch[j]){
++i; ++j;
}else{
k++; i=k; j=1;
}
}
if(j>T.length)
return k;
else
return 0;
}
或者不用k的方式：
int Index(SString S, SString T){
int i=1; //扫描主串S
int j=1; //扫描模式串T
while(i<=S.length && j<=T.length){
if(S.ch[i] == T.ch[j]){
++i;
++j; //继续比较后继字符
}
else{
i = i-j+2;
j=1; //指针后退重新开始匹配
}
}
if(j>T.length)
return i-T.length;
else
return 0;
}
时间复杂度：设模式串长度为m，主串长度为n
- 匹配成功的最好时间复杂度：
- 匹配失败的最好时间复杂度：
- 最坏时间复杂度：
4.5. KPM算法
算法思想
- 朴素模式匹配算法的缺点:当某些子串与模式串能部分匹配时，主串的扫描指针 i 经常回溯，导致时间开销增加。最坏时间复杂度。
- KMP算法:当子串和模式串不匹配时，主串指针i不回溯，模式串指针j = next[ j ]算法平均时间复杂度：
。
求模式串的next数组
- 串的前缀:包含第一个字符，且不包含最后一个字符的子串。
- 串的后缀:包含最后一个字符，且不包含第一个字符的子串。
- 当第i个字符匹配失败，由前 1~j-1 个字符组成的串记s，next[i]= S的最长相等前后缀长度+1特别地，next[1]=0。
KPM 算法代码实现：
// 获取模式串T的next[]数组
void getNext(SString T, int next[]){
int i=1, j=0;
next[1]=0;
while(i<T.length){
if(j==0 || T.ch[1]==T.ch[j]){
++i; ++j;
next[i]=j;
}else
j=next[j];
}
}
// KPM算法，求主串S中模式串T的位序，没有则返回0
int Index_KPM(SString S, SString T){
int i=1, j=1;
int next[T.length+1];
getNext(T, next);
while(i<=S.length && j<=T.length){
if(j==0 || S.ch[i]==T.ch[j]){
++i; ++j;
}else
j=next[j];
}
if(j>T.length)
return i-T.length;
else
return 0;
}
int main() {
SString S={"ababcabcd", 9};
SString T={"bcd", 3};
printf("%d ", Index_KPM(S, T)); //输出9
}
KPM 算法的进一步优化：改进 next 数组：
void getNextval(SString T, int nextval[]){
int i=1,j=0;
nextval[1]=0;
while(i<T.length){
if(j==0 || T.ch[i]==T.ch[j]){
++i; ++j;
if(T.ch[i]!=T.ch[j])
nextval[i]=j;
else
nextval[i]=nextval[j];
}else
j=nextval[j];
}
}
第五章 图
5.1. 树的概念
5.1.1. 树的基本定义
树:n(n>=0)个节点的有限集合，是一种逻辑结构，当n=0时为空树，且非空树满足:
- 有且仅有一个特定的称为根的节点.
- 当n>1时，其余结点可分为m (m >0) 个互不相交的有限集合，其中每个集合本身又是一棵树，并且称为根结点的子树。
树是一种递归的数据结构
非空树特点：
- 有且仅有一个根节点
- 没有后继的结点称为“叶子结点”（或终端节点）
- 有后继的结点称为“分支结点” (或非终端结点)
- 除了根节点外，任何一个结点都有且仅有一个前驱
- 每个结点可以有0个或多个后继
基本术语
- 祖先结点：自己的之上都是祖先节点。
- 子孙结点：自己的之下都是子孙节点。
- 双亲结点 (父节点) ：和自己相连的上一个就是父节点。
- 孩子结点：和自己相连的下面一个。
- 兄弟结点：我自己同一个父节点的。
- 堂兄弟结点：同一层的节点。
属性:
- 结点的层次(深度)--从上往下数
- 结点的高度-一从下往上数
- 树的高度 (深度)-一总共多少层
- 结点的度--有几个孩子(分支)
- 树的度一-各结点的度的最大值
有序树和无序树
- 有序树--逻辑上看，树中结点的各子树从左至右是有次序的，不能互换
- 无序树--逻辑上看，树中结点的各子树从左至右是无次序的，可以互换
森林是m(>=0)棵互不相交的树的集合。
5.1.2. 树的常考性质
- 常见考点1: 树中的结点数=总度数+1
- 常见考点2:度为m的树、m叉树的区别：树的度--各结点的度的最大值；m叉树--每个结点最多只能有m个孩子的树
- 常见考点3: 度为m的树第 i 层至多有个结点
- 常见考点4: 高度为h的m叉树至多有个结点。
- 常见考点5: 高度为h的m叉树至少有h个结点；高度为h、度为m的树至少有h+m-1个结点。
-
常见考点6: 具有n个结点的m叉树的最小高度为
5.2. 二叉树
5.2.1. 二叉树的定义
二叉树是n (n>=0)个结点的有限集合:
- 或者为空二叉树，即n =0。
- 或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。
特点：
- 每个结点至多只有两棵子树
- 左右子树不能颠倒 (二叉树是有序树)
- 二叉树可以是空集合，根可以有空的左子树和空的右子树
5.2.2. 特殊二叉树
满二叉树：一棵深度为k且有个结点的二叉树称为满二叉树。特点：
- 每一层上的结点数都达到最大
- 叶子全部在最低层。
- 按层序从1开始编号，结点i的左孩子为 2i，右孩子为 2i+1;结点i的父节点为[i/2]
完全二叉树：
深度为k的具有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应时，称之为完全二叉树。特点：
- 只有最后两层可能有叶子结点
- 最多只有一个度为1的结点
- 按层序从1开始编号，结点i的左孩子为 2i，右孩子为 2i+1;结点i的父节点为[i/2]
- i<=[n/2]为分支结点，i>[n/2]为叶子结点
二叉排序树：一棵二叉树或者是空二叉树，或者是具有如下性质的二叉树:
- 左子树上所有结点的关键字均小于根结点的关键字;
- 右子树上所有结点的关键字均大于根结点的关键字;
- 左子树和右子树又各是一棵二叉排序树。
平衡二叉树：树上任一结点的左子树和右子树的深度之差不超过1。
5.2.3. 二叉树的性质
常见考点1：设非空二叉树中度为0、1和2的结点个数分别为、,和，则(叶子结点比二分支结点多一个)
常见考点2：二叉树第层至多有个结点 (>=1)；m叉树第层至多有个结点 (>=1)
常见考点3：高度为h的二叉树至多有个结点(满二叉树)；高度为h的m叉树至多结点
常见考点4：具有 n 个（n>0）结点的完全二叉树的高度 h 为或者
。
常见考点5：对于完全二叉树，可以由总结点数 n 推出度为 0、1 和 2 的结点个数、、
推导过程：
因为：:所以
为奇数
又因为：
所以：若完全二叉树有偶数n个节点，则为1；为；为
若完全二叉树有奇数n个节点，则为0；为；为
5.2.4. 二叉树存储实现
二叉树的顺序存储：
二叉树的顺序存储中，一定要把二叉树的结点编号与完全二叉树对应起来；
几个重要常考的基本操作：
- i 的左孩子：2i
- i 的右孩子：2i+1
- i 的父节点：i/2
- i 所在的层次：
或者
若完全二叉树中共有n个结点，则
- 判断i是否有左孩子? ？
- 判断i是否有右孩子?
？
- 判断i是否是叶子/分支结点? ?
#define MaxSize 100
struct TreeNode{
ElemType value; //结点中的数据元素
bool isEmpty; //结点是否为空
}
main(){
TreeNode t[MaxSize];
for (int i=0; i<MaxSize; i++){
t[i].isEmpty = true;
}
}链式存储
//二叉树的结点
struct ElemType{
int value;
};
typedef struct BiTnode{
ElemType data; //数据域
struct BiTNode *lchild, *rchild; //左、右孩子指针
}BiTNode, *BiTree;
//定义一棵空树
BiTree root = NULL;
//插入根节点
root = (BiTree) malloc (sizeof(BiTNode));
root -> data = {1};
root -> lchild = NULL;
root -> rchild = NULL;
//插入新结点
BiTNode *p = (BiTree) malloc (sizeof(BiTNode));
p -> data = {2};
p -> lchild = NULL;
p -> rchild = NULL;
root -> lchild = p; //作为根节点的左孩子
- 二又树的顺序存储中，一定要把二叉树的结点编号与完全二叉树对应起来
- 最坏情况:高度为 h 且只有 h 个结点的单支树 (所有结点只有右孩子)，也至少需要 2^h-1个存储单元
- 结论:二叉树的顺序存储结构，只适合存储完全二叉树
5.3. 二叉树的遍历和线索二叉树
5.3.1. 二叉树的先中后序遍历
- 遍历：按照某种次序把所有结点都访问一遍。
- 层次遍历:基于树的层次特性确定的次序规则
二又树的递归特性:
【1】要么是个空二叉树
【2】要么就是由“根节点+左子树+右子树”组成的二叉树
【二叉树的先中后遍历】
- 先序遍历:根左右(NLR)
typedef struct BiTnode{
ElemType data;
struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
void PreOrder(BiTree T){
if(T!=NULL){
visit(T); //访问根结点
PreOrder(T->lchild); //递归遍历左子树
PreOrder(T->rchild); //递归遍历右子树
}
}
- 中序遍历:左根右 (LNR)
typedef struct BiTnode{
ElemType data;
struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
void InOrder(BiTree T){
if(T!=NULL){
InOrder(T->lchild); //递归遍历左子树
visit(T); //访问根结点
InOrder(T->rchild); //递归遍历右子树
}
}
- 后序遍历:左右根(LRN)
typedef struct BiTnode{
ElemType data;
struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
void PostOrder(BiTree T){
if(T!=NULL){
PostOrder(T->lchild); //递归遍历左子树
PostOrder(T->rchild); //递归遍历右子树
visit(T); //访问根结点
}
}
5.3.2. 二叉树的层序遍历
算法思想:
- 1.初始化一个辅助队列
- 2.根结点入队
- 3.若队列非空，则队头结点出队，访问该结点，并将孩子插入队尾(如果有的话)
- 4.重复3直至队列为空
//二叉树的结点(链式存储)
typedef struct BiTnode{
ElemType data;
struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
//链式队列结点
typedef struct LinkNode{
BiTNode * data;
typedef LinkNode *next;
}LinkNode;
typedef struct{
LinkNode *front, *rear;
}LinkQueue;
//层序遍历
void LevelOrder(BiTree T){
LinkQueue Q;
InitQueue (Q); //初始化辅助队列
BiTree p;
EnQueue(Q,T); //将根节点入队
while(!isEmpty(Q)){ //队列不空则循环
DeQueue(Q,p); //队头结点出队
visit(p); //访问出队结点
if(p->lchild != NULL)
EnQueue(Q,p->lchild); //左孩子入队
if(p->rchild != NULL)
EnQueue(Q,p->rchild); //右孩子入队
}
}
5.3.3. 由遍历序列构造二叉树
- 一个前序遍历序列可能对应多种二叉树形态。同理，一个后序遍历序列、一个中序遍历序列、一个层序遍历序列也可能对应多种二叉树形态。即：若只给出一棵二叉树的 前/中/后/层序遍历序列 中的一种，不能唯一确定一棵二叉树。
由二叉树的遍历序列构造二叉树：
1. 前序+中序遍历序列
2. 后序+中序遍历序列
3. 层序+中序遍历序列
- 由 前序+中序遍历序列 构造二叉树：由前序遍历的遍历顺序（根节点、左子树、右子树）可推出根节点，由根节点在中序遍历序列中的位置即可推出左子树与右子树分别有哪些结点。
- 由 后序+中序遍历序列 构造二叉树：由后序遍历的遍历顺序（左子树、右子树、根节点）可推出根节点，由根节点在中序遍历序列中的位置即可推出左子树与右子树分别有哪些结点。
- 由 层序+中序遍历序列 构造二叉树：由层序遍历的遍历顺序（层级遍历）可推出根节点，由根节点在中序遍历序列中的位置即可推出左子树与右子树分别有哪些结点。
5.3.4. 线索二叉树的概念
线索二叉树的概念与作用
- n 个结点的二叉树，有 n+1 个空链域，可用来记录前驱、后继的信息。指向前驱、后继的指针被称为“线索”，形成的二叉树被称为线索二叉树。
- 在二叉树的结点上加上线索的二叉树称为线索二叉树，对二叉树以某种遍历方式（如先序、中序、后序或层次等）进行遍历，使其变为线索二叉树的过程称为对二叉树进行线索化。
- 线索二叉树的结点在原本二叉树的基础上，新增了左右线索标志 tag。当 tag == 0 时，表示指针指向孩子；当 tag == 1 时，表示指针是“线索”。
//线索二叉树结点
typedef struct ThreadNode{
ElemType data;
struct ThreadNode *lchild, *rchild;
int ltag, rtag; // 左、右线索标志
}ThreadNode, *ThreadTree;
中序线索化的存储
先序线索化的存储
后序线索化的存储
5.3.5. 二叉树的线索化
中序线索化：
typedef struct ThreadNode{
int data;
struct ThreadNode *lchild, *rchild;
int ltag, rtag; // 左、右线索标志
}ThreadNode, *ThreadTree;
//全局变量pre, 指向当前访问的结点的前驱
TreadNode *pre=NULL;
void InThread(ThreadTree T){
if(T!=NULL){
InThread(T->lchild); //中序遍历左子树
visit(T); //访问根节点
InThread(T->rchild); //中序遍历右子树
}
}
void visit(ThreadNode *q){
if(q->lchid = NULL){ //左子树为空，建立前驱线索
q->lchild = pre;
q->ltag = 1;
}
if(pre!=NULL && pre->rchild = NULL){
pre->rchild = q; //建立前驱结点的后继线索
pre->rtag = 1;
}
pre = q;
}
//中序线索化二叉树T
void CreateInThread(ThreadTree T){
pre = NULL; //pre初始为NULL
if(T!=NULL);{ //非空二叉树才能进行线索化
InThread(T); //中序线索化二叉树
if(pre->rchild == NULL)
pre->rtag=1; //处理遍历的最后一个结点
}
}
先序线索化：
typedef struct ThreadNode{
int data;
struct ThreadNode *lchild, *rchild;
int ltag, rtag; // 左、右线索标志
}ThreadNode, *ThreadTree;
//全局变量pre, 指向当前访问的结点的前驱
TreadNode *pre=NULL;
//先序遍历二叉树，一边遍历一边线索化
void PreThread(ThreadTree T){
if(T!=NULL){
visit(T);
if(T->ltag == 0) //lchild不是前驱线索
PreThread(T->lchild);
PreThread(T->rchild);
}
}
void visit(ThreadNode *q){
if(q->lchid = NULL){ //左子树为空，建立前驱线索
q->lchild = pre;
q->ltag = 1;
}
if(pre!=NULL && pre->rchild = NULL){
pre->rchild = q; //建立前驱结点的后继线索
pre->rtag = 1;
}
pre = q;
}
//先序线索化二叉树T
void CreateInThread(ThreadTree T){
pre = NULL; //pre初始为NULL
if(T!=NULL);{ //非空二叉树才能进行线索化
PreThread(T); //先序线索化二叉树
if(pre->rchild == NULL)
pre->rtag=1; //处理遍历的最后一个结点
}
}
后序线索化：
typedef struct ThreadNode{
int data;
struct ThreadNode *lchild, *rchild;
int ltag, rtag; // 左、右线索标志
}ThreadNode, *ThreadTree;
//全局变量pre, 指向当前访问的结点的前驱
TreadNode *pre=NULL;
//先序遍历二叉树，一边遍历一边线索化
void PostThread(ThreadTree T){
if(T!=NULL){
PostThread(T->lchild);
PostThread(T->rchild);
visit(T); //访问根节点
}
}
void visit(ThreadNode *q){
if(q->lchid = NULL){ //左子树为空，建立前驱线索
q->lchild = pre;
q->ltag = 1;
}
if(pre!=NULL && pre->rchild = NULL){
pre->rchild = q; //建立前驱结点的后继线索
pre->rtag = 1;
}
pre = q;
}
//先序线索化二叉树T
void CreateInThread(ThreadTree T){
pre = NULL; //pre初始为NULL
if(T!=NULL);{ //非空二叉树才能进行线索化
PostThread(T); //后序线索化二叉树
if(pre->rchild == NULL)
pre->rtag=1; //处理遍历的最后一个结点
}
}
5.3.6. 在线索二叉树中找前驱/后继
中序线索二叉树找到指定结点 * p 的中序后继 next：
- 若
p->rtag==1，则next = p->rchild； - 若
p->rtag==0，则 next 为 p 的右子树中最左下结点。
// 找到以p为根的子树中，第一个被中序遍历的结点
ThreadNode *FirstNode(ThreadNode *p){
// 循环找到最左下结点（不一定是叶结点）
while(p->ltag==0)
p=p->lchild;
return p;
}
// 在中序线索二叉树中找到结点p的后继结点
ThreadNode *NextNode(ThreadNode *p){
// 右子树中最左下的结点
if(p->rtag==0)
return FirstNode(p->rchild);
else
return p->rchild;
}
// 对中序线索二叉树进行中序循环（非递归方法实现）
void InOrder(ThreadNode *T){
for(ThreadNode *p=FirstNode(T); p!=NULL; p=NextNode(p)){
visit(p);
}
}
中序线索二叉树找到指定结点 * p 的中序前驱 pre：
- 若
p->ltag==1，则pre = p->lchild； - 若
p->ltag==0，则 next 为 p 的左子树中最右下结点。
// 找到以p为根的子树中，最后一个被中序遍历的结点
ThreadNode *LastNode(ThreadNode *p){
// 循环找到最右下结点（不一定是叶结点）
while(p->rtag==0)
p=p->rchild;
return p;
}
// 在中序线索二叉树中找到结点p的前驱结点
ThreadNode *PreNode(ThreadNode *p){
// 左子树中最右下的结点
if(p->ltag==0)
return LastNode(p->lchild);
else
return p->lchild;
}
// 对中序线索二叉树进行中序循环（非递归方法实现）
void RevOrder(ThreadNode *T){
for(ThreadNode *p=LastNode(T); p!=NULL; p=PreNode(p))
visit(p);
}
先序线索二叉树找到指定结点 * p 的先序后继 next：
- 若
p->rtag==1，则next = p->rchild； - 若
p->rtag==0：- 若 p 有左孩子，则先序后继为左孩子；
- 若 p 没有左孩子，则先序后继为右孩子。
先序线索二叉树找到指定结点 * p 的先序前驱 pre：
- 前提：改用三叉链表，可以找到结点 * p 的父节点。
- 如果能找到 p 的父节点，且 p 是左孩子：p 的父节点即为其前驱；
- 如果能找到 p 的父节点，且 p 是右孩子，其左兄弟为空：p 的父节点即为其前驱；
- 如果能找到 p 的父节点，且 p 是右孩子，其左兄弟非空：p 的前驱为左兄弟子树中最后一个被先序遍历的结点；
- 如果 p 是根节点，则 p 没有先序前驱。
后序线索二叉树找到指定结点 * p 的后序前驱 pre：
- 若p->ltag==1，则pre = p->lchild；
- 若p->ltag==0：
- 若 p 有右孩子，则后序前驱为右孩子；
- 若 p 没有右孩子，则后续前驱为右孩子。
后序线索二叉树找到指定结点 * p 的后序后继 next：
- 前提：改用三叉链表，可以找到结点 * p 的父节点。
- 如果能找到 p 的父节点，且 p 是右孩子：p 的父节点即为其后继；
- 如果能找到 p 的父节点，且 p 是左孩子，其右兄弟为空：p 的父节点即为其后继；
- 如果能找到 p 的父节点，且 p 是左孩子，其右兄弟非空：p 的后继为右兄弟子树中第一个被后序遍历的结点；
- 如果 p 是根节点，则 p 没有后序后继。
5.4. 树和森林
5.4.1. 树的存储结构
双亲表示法（顺序存储）：每个结点中保存指向双亲的“指针”。
//数据域：存放结点本身信息。
//双亲域：指示本结点的双亲结点在数组中的位置。
#define MAX_TREE_SIZE 100 //树中最多结点数
typedef struct{ //树的结点定义
ElemType data;
int parent; //双亲位置域
}PTNode;
typedef struct{ //树的类型定义
PTNode nodes[MAX_TREE_SIZE]; //双亲表示
int n; //结点数
}PTree;
增：新增数据元素，无需按逻辑上的次序存储；（需要更改结点数n）
删：（叶子结点）：
① 将伪指针域设置为-1；
②用后面的数据填补；（需要更改结点数n）
查询：
①优点-查指定结点的双亲很方便；
②缺点-查指定结点的孩子只能从头遍历，空数据导致遍历更慢；
优点: 查指定结点的双亲很方便
缺点:查指定结点的孩子只能从头遍历
孩子表示法（顺序+链式存储）
孩子表示法:顺序存储各个节点，每个结点中保存孩子链表头指针。
struct CTNode{
int child; //孩子结点在数组中的位置
struct CTNode *next; // 下一个孩子
};
typedef struct{
ElemType data;
struct CTNode *firstChild; // 第一个孩子
}CTBox;
typedef struct{
CTBox nodes[MAX_TREE_SIZE];
int n, r; // 结点数和根的位置
}CTree;
孩子兄弟表示法（链式存储）
用孩子兄弟表示法可以将树转换为二叉树的形式。
//孩子兄弟表示法结点
typedef struct CSNode{
ElemType data;
struct CSNode *firstchild, *nextsibling; //第一个孩子和右兄弟结点
}CSNode, *CSTree;
5.4.2. 树和森林的遍历
树的先根遍历
若树非空，先访问根结点，再依次对每棵子树进行先根遍历；（与对应二叉树的先序遍历序列相同）
树的先根遍历序列与这棵树相应二叉树的先序序列相同。
void PreOrder(TreeNode *R){
if(R!=NULL){
visit(R); //访问根节点
while(R还有下一个子树T)
PreOrder(T); //先跟遍历下一个子树
}
}
树的后根遍历
若树非空，先依次对每棵子树进行后根遍历，最后再访问根结点。（深度优先遍历）
树的后根遍历序列与这棵树相应二叉树的中序序列相同。
void PostOrder(TreeNode *R){
if(R!=NULL){
while(R还有下一个子树T)
PostOrder(T); //后跟遍历下一个子树
visit(R); //访问根节点
}
}
层序遍历（队列实现）
- 若树非空，则根结点入队；
- 若队列非空，队头元素出队并访问，同时将该元素的孩子依次入队；
- 重复以上操作直至队尾为空；
森林的遍历
- 先序遍历：等同于依次对各个树进行先根遍历；也可以先转换成与之对应的二叉树，对二叉树进行先序遍历；
- 中序遍历：等同于依次对各个树进行后根遍历；也可以先转换成与之对应的二叉树，对二叉树进行中序遍历；
5.5. 应用
5.5.1. 二叉排序树
二又排序树，又称二叉查找树(BST，Binary Search Tree)棵二叉树或者是空二叉树，或者是具有如下性质的二叉树:
- 左子树上所有结点的关键字均小于根结点的关键字；
- 右子树上所有结点的关键字均大于根结点的关键字；
- 左子树和右子树又各是一棵二叉排序树；
- 左子树结点值< 根结点值< 右子树结点值；
- 进行中序遍历，可以得到一个递增的有序序列。
【二叉排序树的查找】
- 若树非空，目标值与根结点的值比较；
- 若相等，则查找成功；
- 若小于根结点，则在左子树上查找；
- 否则在右子树上查找；
- 查找成功，返回结点指针;查找失败返回NULL 。
typedef struct BSTNode{
int key;
struct BSTNode *lchild, *rchild;
}BSTNode, *BSTree;
//在二叉排序树中查找值为key的结点（非递归）
//最坏空间复杂度：O(1)
BSTNode *BST_Search(BSTree T, int key){
while(T!=NULL && key!=T->key){ //若树空或等于跟结点值，则结束循环
if(key<T->key) //值小于根结点值，在左子树上查找
T = T->lchild;
else //值大于根结点值，在右子树上查找
T = T->rchild;
}
return T;
}
//在二叉排序树中查找值为key的结点（递归）
//最坏空间复杂度：O(h)
BSTNode *BSTSearch(BSTree T, int key){
if(T == NULL)
return NULL;
if(Kry == T->key)
return T;
else if(key < T->key)
return BSTSearch(T->lchild, key);
else
return BSTSearch(T->rchild, key);
}【二叉排序树的插入操作】
- 若原二叉排序树为空，则直接插入结点;否则；
- 若关键字k小于根结点值，则插入到左子树；
- 若关键字k大于根结点值，则插入到右子树。
//在二叉排序树中插入关键字为k的新结点（递归）
//最坏空间复杂度：O(h)
int BST_Insert(BSTree &T, int k){
if(T==NULL){ //原树为空，新插入的结点为根结点
T = (BSTree)malloc(sizeof(BSTNode));
T->key = k;
T->lchild = T->rchild = NULL;
return 1; //插入成功
}
else if(K == T->key) //树中存在相同关键字的结点，插入失败
return 0;
else if(k < T->key)
return BST_Insert(T->lchild,k);
else
return BST_Insert(T->rchild,k);
}
【二叉排序树的构造】
//按照str[]中的关键字序列建立二叉排序树
void Crear_BST(BSTree &T, int str[], int n){
T = NULL; //初始时T为空树
int i=0;
while(i<n){
BST_Insert(T,str[i]); //依次将每个关键字插入到二叉排序树中
i++;
}
}
【二叉排序树的删除】
先搜索找到目标结点:
- 若被删除结点z是叶结点则直接删除，不会破坏二叉排序树的性质；
- 若结点z只有一棵左子树或右子树，则让z的子树成为z父结点的子树，替代z的位置；
- 若结点z有左、右两棵子树，则令z的直接后继 (或直接前驱) 替代z，然后从二叉排序树中删去这个直接后继(或直接前驱)，这样就转换成了第一或第二种情况。
查找长度：在查找运算中，需要对比关键字的次数称为查找长度，反映了查找操作时间复杂度
5.5.2. 平衡二叉树
平衡二叉树(Balanced Binary Tree)，简称平衡树(AVL树)--上任一结点的左子树和右子树的高度之差不超过1。
结点的平衡因子 = 左子树高 - 右子树高
//平衡二叉树结点
typedef struct AVLNode{
int key; //数据域
int balance; //平衡因子
struct AVLNode *lchild; *rchild;
}AVLNode, *AVLTree;平衡二叉树的插入
- 每次调整的对象都是“最小不平衡子树“
- 在插入操作中，只要将最小不平衡子树调整平衡，则其他祖先结点都会恢复平衡。
调整最小不平衡子树（LL）：由于在结点 A 的左孩子（L）的左子树（L）上插入了新结点，A的平衡因子由1增至 2，导致以 A 为根的子树失去平衡，需要一次向右的旋转操作。将 A 的左孩子 B 向右上旋转代替 A 成为根结点，将 A 结点向右下旋转成为 B 的右子树的根结点，而 B 的原右子树则作为 A 结点的左子树。
调整最小不平衡子树（RR）：由于在结点 A 的右孩子（R）的右子树（R）上插入了新结点，A的平衡因子由 -1 减至 -2，导致以 A 为根的子树失去平衡，需要一次向左的旋转操作。将 A 的右孩子 B 向左上旋转代替 A成为根结点，将 A 结点向左下旋转成为 B 的左子树的根结点，而 B 的原左子树则作为 A 结点的右子树。
调整最小不平衡子树（LR）：由于在 A 的左孩子（L）的右子树（R）上插入新结点，A 的平衡因子由 1 增至 2，导致以 A 为根的子树失去平衡，需要进行两次旋转操作，先左旋转后右旋转。先将 A 结点的左孩子 B 的右子树的根结点 C 向左上旋转提升到 B 结点的位置，然后再把该 C 结点向右上旋转提升到 A 结点的位置。
调整最小不平衡子树（RL）：由于在 A 的右孩子（R）的左子树（L）上插入新结点，A 的平衡因子由 -1 减至 -2，导致以 A 为根的子树失去平衡，需要进行两次旋转操作，先右旋转后左旋转。先将A 结点的右孩子 B的左子树的根结点 C 向右上旋转提升到 B 结点的位置，然后再把该 C 结点向左上旋转提升到 A 结点的位置。
查找效率分析：若树高为h，则最坏情况下，查找一个关键字最多需要对比 h 次，即查找操作的时间复杂度不可能超过 O(h)。
由于平衡二叉树上任一结点的左子树和右子树的高度之差不超过 1，假如以表示深度为 h 的平衡树中含有的最少结点数，则有:
;且有：
5.5.3. 哈夫曼树
1、哈夫曼树定义
- 结点的权:有某种现实含义的数值(如:表示结点的重要性等)
- 结点的带权路径长度：从树的根到该结点的路径长度(经过的边数)与该结点上权值的乘积。
- 树的带权路径长度:树中所有叶结点的带权路径长度之和 (WPL,Weighted Path Length)。
- 哈夫曼树的定义：在含有n个带权叶结点的二叉树中，其中带权路径长度(WPL) 最小的二叉树，也称最优二叉树。
2、哈夫曼树的构造（重点）
给定n个权值分别为w1, W2,..., w,的结点，构造哈夫曼树的算法描述如下:
- 将这n个结点分别作为n棵仅含一个结点的二叉树，构成森林F。
- 构造一个新结点，从F中选取两棵根结点权值最小的树作为新结点的左、右子树，并且将新 结点的权值置为左、右子树上根结点的权值之和。
- 从F中删除刚才选出的两棵树，同时将新得到的树加入F中
- 重复步骤2和3，直至F中只剩下一棵树为止。
构造哈夫曼树的注意事项：
- 每个初始结点最终都成为叶结点，且权值越小的结点到根结点的路径长度越大
- 哈夫曼树的结点总数为2n - 1
- 哈夫曼树中不存在度为1的结点。
- 哈夫曼树并不唯一，但WPL必然相同且为最优
3、哈杜曼编码（重点）
- 固定长度编码：每个字符用相等长度的二进制位表示
- 可变长度编码：允许对不同字符用不等长的二进制位表示
- 若没有一个编码是另一个编码的前缀，则称这样的编码为前缀编码
曼树得到哈夫曼编码--字符集中的每个字符作为一个叶子结点，各个字符出现的频度作为结点的权值，根据之前介绍的方法构造哈夫曼树 。
第六章 图
6.1. 图的基本概念
（1）图G由顶点集V和边集E组成，记为G=(V,E)，其中V(G)表示图G中顶点的有限非空集；E(G)表示图G中顶点之间的关系 (边) 集合。若V={V, V2,...,Vn}，则用V表示图G中顶点的个数，也称图G的阶，E={(u, v) l uV, vV}，用|E|表示图G中边的条数。
（2）无向图：若E是无向边 （简称边) 的有限集合时，则图G为无向图。边真是顶点的无序对，记为(v,w)或(w,v)，因为（v,w)=(w,v)，其中v、w是顶点。可以说顶点w和顶点v互为邻援点。边(v,w)依附于顶点w和v，或者说边(v,w)和顶点v、w相关联。
（3）有向图：若E是有向边(也称弧)的有限集合时，则图G为有向图弧是顶点的有序对，记为<v.w>，其中v、w是顶点，v称为弧尾，w称为弧头，<v.w>称为从顶点v到顶点w的弧，也称v邻接到w，或w邻接自v。<v, w> f <w, v
（4）简单图：① 不存在重复边； ② 不存在顶点到自身的边。
（5）多重图：图G中某两个结点之间的边数多于一条，又允许顶点通过同一条边和自己关联,则G为多重图。
（6）顶点的度
① 对于无向图：顶点v的度是指依附于该顶点的边的条数，记为TD(v)。
② 对于有向图：入度是以顶点v为终点的有向边的数目，记为ID(v);出度是以顶点v为起点的有向边的数目，记为OD(v)，顶点v的度等于其入度和出度之和，即TD(v) = ID(v) + OD(v)。
（7）其他的概念
- 路径：顶点v,到顶点v之间的一条路径是指顶点序列。
- 回路：第一个顶点和最后一个顶点相同的路径称为回路。
- 简单路径：在路径序列中，顶点不重复出现的路径称为简单路径。
- 简单回路：除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。
- 路径长度：路径上边的数目。
- 无穷：点到点的距离从顶点u出发到顶点v的最短路径若存在，则此路径的长度称为从u到v的距离若从u到v根本不存在路径，则记该距离为无穷。
- 连通：无向图中，若从顶点v到顶点w有路径存在，则称v和w是连通的。
- 强连通：有向图中，若从顶点v到贝点w和从顶点w到顶点v之间都有路径则称这两个顶点是强连通的。
- 非连通图：若图G中任意两个顶点都是连通的，则称图G为连通图，否则称为非连通图。
- 强连通图：若图中任何一对顶点都是强连通的，则称此图为强连通图。
- 连通分量：无向图的极大连通子图称为连通分量。
- 强连通分量：有向图中的极大强连通子图称为有向图的强连通分量。
- 极小连通子图：连通图的生成树是包含图中全部顶点的一个极小连通子图。
- 连通图的生成树：包含图中全部顶点的一个极小连通子图。若图中顶点数为n，则它的生成树含有 n-1 条边。对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路。
- 边的权：在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。
- 带权图/网：边上带有权值的图称为带权图，也称网。
- 带权路径长度：当图是带权图时，一条路径上所有边的权值之和，称为该路径的带权路径长度。
6.2. 图的存储
6.2.1. 邻接矩阵
- 图的邻接矩阵(Adjacency Matrix) 存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。
- 度：第个结点的度 = 第行（或第列）的非零元素个数；
- 出度：第行的非零元素个数；
- 入度：第 i 列的非零元素个数。
邻接矩阵法代码实现
#define MaxVertexNum 100 //顶点数目的最大值
typedef char VertexType; //顶点的数据类型
typedef int EdgeType; //带权图中边上权值的数据类型
typedef struct{
VertexType Vex[MaxVertexNum]; //顶点表
EdgeType Edge[MaxVertexNum][MaxVertexNum]; //邻接矩阵，边表
int vexnum, arcnum; //图的当前顶点数和弧树
}MGraph;
性能分析：
（1）空间复杂度：，只和顶点数相关，和实际的边数无关。
（2）适合用于存储稠密图。
（3）无向图的邻接矩阵是对称矩阵，可以压缩存储 (只存储上三角区或者下三角区)。
邻接矩阵的性质：设图 G 的邻接阵为 (矩阵元素为0或1)，则的元素等于由点到顶点的长度为的路径的数目。
6.2.2. 邻接表
代码实现
#define MAXVEX 100 //图中顶点数目的最大值
type char VertexType; //顶点类型应由用户定义
typedef int EdgeType; //边上的权值类型应由用户定义
/*边表结点*/
typedef struct EdgeNode{
int adjvex; //该弧所指向的顶点的下标或者位置
EdgeType weight; //权值，对于非网图可以不需要
struct EdgeNode *next; //指向下一个邻接点
}EdgeNode;
/*顶点表结点*/
typedef struct VertexNode{
Vertex data; //顶点域，存储顶点信息
EdgeNode *firstedge //边表头指针
}VertexNode, AdjList[MAXVEX];
/*邻接表*/
typedef struct{
AdjList adjList;
int numVertexes, numEdges; //图中当前顶点数和边数
}
邻接表的特点：
- 对于无向图，存储空间为
；对于有向图，存储空间为
；
- 更适合用于稀疏图；
- 若G为无向图，则顶点的度为该顶点边表的长度若G为有向图，则顶点的出度为该顶点边表的长度，计算入度需要遍历整个邻接表；
- 邻接表不唯一，边表结点的顺序根据算法和输入不同可能会不同。
邻接表对比邻接矩阵：
| 邻接矩阵 | 邻接表 | |
|---|---|---|
| 空间复杂度 | 无向图 |
|
| 适用场景 | 存储稠密图 | 存储稀疏图 |
| 表示方式 | 唯一 | 不唯一 |
| 计算度、入度、出度 | 遍历对应行或列 | 计算有向图的度、入度不方便，其余很方便 |
| 找相邻的边 | 遍历对应行或列 | 找有向图的入边不方便，其余很方便 |
6.2.3. 十字链表、临接多重表
【十字链表】
- 十字链表是有向图的一种链式存储结构。
#define MAX_VERTEX_NUM 20 //最大顶点数量
struct EBox{ //边结点
int i,j; //该边依附的两个顶点的位置（一维数组下标）
EBox *ilink,*jlink; //分别指向依附这两个顶点的下一条边
InfoType info; //边的权值
};
struct VexBox{
VertexType data;
EBox *firstedge; //指向第一条依附该顶点的边
};
struct AMLGraph{
VexBox adjmulist[MAX_VERTEX_NUM];
int vexnum,edgenum; //无向图的当前顶点数和边数
};
【邻接多重表】
邻接多重表是无向图的另一种链式存储结构。
四种存储方法比较：
6.2.4. 图的基本操作
Adjacent(G, x, y)：判断图 G 是否存在边 < x , y > 或 ( x , y )。
Neighbors(G, x)：列出图 G 中与结点 x 邻接的边。
InsertVertex(G, x)：在图 G 中插入顶点 x 。
DeleteVertex(G, x)：从图 G 中删除顶点 x。
AddEdge(G, x, y)：若无向边 ( x , y ) 或有向边 < x , y > 不存在，则向图 G 中添加该边。
RemoveEdge(G, x, y)：若无向边 ( x , y ) (x, y)(x,y) 或有向边 < x , y > <x,y><x,y> 存在，则从图 G 中删除该边。
FirstNeighbor(G, x)：求图 G 中顶点 x 的第一个邻接点，若有则返回顶点号。若 x 没有邻接点或图中不存在 x，则返回 -1。
NextNeighbor(G, x, y)：假设图 G 中顶点 y 是顶点 x 的一个邻接点，返回除 y 之外顶点 x 的下一个邻接点的顶点号，若 y 是 x 的最后一个邻接点，则返回 -1。
Get_edge_value(G, x, y)：获取图 G 中边 ( x , y )或 < x , y > 对应的权值。
Set_edge_value(G, x, y, v)：设置图 G 中边 ( x , y )或 < x , y >对应的权值为 v。
6.3. 图的遍历
6.3.1. 广度优先遍历
1、广度优先遍历 (Breadth-First-Search,BFS)要点:
（1）找到与一个顶点相邻的所有顶点；
（2）标记哪些顶点被访问过；
（3）需要一个辅助队列。
2、广度优先遍历用到的操作：
FirstNeighbor(G, x)：求图 G 中顶点 x 的第⼀个邻接点，若有则返回顶点号；若 x 没有邻接点或图中不存在 x，则返回 -1。
NextNeighbor(G, x, y)：假设图 G 中顶点 y 是顶点 x 的⼀个邻接点，返回除 y 之外顶点 x 的下⼀个邻接点的顶点号，若 y 是 x 的最后⼀个邻接点，则返回 -1。
3、广度优先遍历代码实现：
/*邻接矩阵的广度遍历算法*/
void BFSTraverse(MGraph G){
int i, j;
Queue Q;
for(i = 0; i<G,numVertexes; i++){
visited[i] = FALSE;
}
InitQueue(&Q); //初始化一辅助用的队列
for(i=0; i<G.numVertexes; i++){
//若是未访问过就处理
if(!visited[i]){
vivited[i] = TRUE; //设置当前访问过
visit(i); //访问顶点
EnQueue(&Q, i); //将此顶点入队列
//若当前队列不为空
while(!QueueEmpty(Q)){
DeQueue(&Q, &i); //顶点i出队列
//FirstNeighbor(G,v):求图G中顶点v的第一个邻接点，若有则返回顶点号，否则返回-1。
//NextNeighbor(G,v,w):假设图G中顶点w是顶点v的一个邻接点，返回除w外顶点v
for(j=FirstNeighbor(G, i); j>=0; j=NextNeighbor(G, i, j)){
//检验i的所有邻接点
if(!visited[j]){
visit(j); //访问顶点j
visited[j] = TRUE; //访问标记
EnQueue(Q, j); //顶点j入队列
}
}
}
}
}
}
4、复杂度分析：
（1）空间复杂度: 最坏情况，辅助队列大小为 。
（2）对于邻接矩阵存储的图，访问个顶点需要的时间，查找每个顶点的邻接点都需要 的时间，而总共有个顶点，时间复杂度为。
（3）对于邻接表存储的图，访问个顶点需要的时间，查找各个顶点的邻接点共需要的时间，时间复杂度为。
5、⼴度优先⽣成树：⼴度优先⽣成树由⼴度优先遍历过程确定。由于邻接表的表示⽅式不唯⼀，因此基于邻接表的⼴度优先⽣成树也不唯⼀。
6.3.2. 深度优先遍历
1、深度优先遍历(Depth First Search)，也有称为深度优先搜索，简称为DFS。
代码实现：文章来源：https://www.toymoban.com/news/detail-476177.html
bool visited[MAX_VERTEX_NUM]; //访问标记数组
/*从顶点出发，深度优先遍历图G*/
void DFS(Graph G, int v){
int w;
visit(v); //访问顶点
visited[v] = TRUE; //设已访问标记
//FirstNeighbor(G,v):求图G中顶点v的第一个邻接点，若有则返回顶点号，否则返回-1。
//NextNeighbor(G,v,w):假设图G中顶点w是顶点v的一个邻接点，返回除w外顶点v
for(w = FirstNeighbor(G, v); w>=0; w=NextNeighor(G, v, w)){
if(!visited[w]){ //w为u的尚未访问的邻接顶点
DFS(G, w);
}
}
}
/*对图进行深度优先遍历*/
void DFSTraverse(MGraph G){
int v;
for(v=0; v<G.vexnum; ++v){
visited[v] = FALSE; //初始化已访问标记数据
}
for(v=0; v<G.vexnum; ++v){ //从v=0开始遍历
if(!visited[v]){
DFS(G, v);
}
}
}
2、复杂度分析：
（1）空间复杂度主要来自来⾃函数调⽤栈，最坏情况下递归深度为 ；最好情况为。
（2）对于邻接矩阵存储的图，访问个顶点需要的时间，查找每个顶点的邻接点都需要 的时间，而总共有个顶点，时间复杂度为。
（3）对于邻接表存储的图，访问个顶点需要的时间，查找各个顶点的邻接点共需要的时间，时间复杂度为。
3、深度优先遍历序列：
- 从 2 出发的深度优先遍历序列：2, 1, 5, 6, 3, 4, 7, 8
- 从 3 出发的深度优先遍历序列：3, 4, 7, 6, 2, 1, 5, 8
- 从 1 出发的深度优先遍历序列：1, 2, 6, 3, 4, 7, 8, 5
4、深度优先⽣成树：
- 同⼀个图的邻接矩阵表示⽅式唯⼀，因此深度优先遍历序列唯⼀，深度优先⽣成树也唯⼀；
- 同⼀个图的邻接表表示⽅式不唯⼀，因此深度优先遍历序列不唯⼀，深度优先⽣成树也不唯⼀。
5、深度优先⽣成深林：
6.4. 图的应用
6.4.1. 最小生成树
1、生成树：连通图的生成树是包含图中全部顶点的一个极小连通子图。 若图中顶点数为 n，则它的生成树含有 n-1 条边。对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路。
2、最⼩⽣成树（最⼩代价树）：对于一个带权连通无向图，生成树不同，每棵树的权(即树中所有边上的权值之和)也可能不同。设R为G的所有生成树的集合，若T为R中边的权值之和最小的生成树，则T称为G的最小生成树(Minimum-Spannino-Tree,MST).。
- 最小生成树可能有多个，但边的权值之和总是唯一且最小的。
- 最小生成树的边数 =顶点数 -1。砍掉一条则不连通，增加一条边则会出现回路。
- 如果一个连通图本身就是一棵树，则其最小生成树就是它本身。
- 只有连通图才有生成树，非连通图只有生成森林。
3、求最小生成树的两种方法
- Prim算法
- Kruskal算法
Prim算法(普里姆)：从某一个顶点开始构建生成树;每次将代价最小的新顶点纳入生成树，直到所有顶点都纳入为止。时间复杂度: O(V2)适合用于边稠密图。
Kruskal算法(克鲁斯卡尔)：每次选择一条权值最小的边，使这条边的两头连通(原本已经连通的就不选)直到所有结点都连通。时间复杂度: O(lEllog2lEl )适合用于边稀疏图。
| Prim 算法（普⾥姆） | Kruskal 算法（克鲁斯卡尔） | |
|---|---|---|
| 时间复杂度 | $O( | V |
| 适用场景 | 稠密图 | 稀疏图 |
6.4.2. 无权图的单源最短路径问题——BFS算法
1、使用 BFS算法求无权图的最短路径问题，需要使用三个数组
-
d[]数组用于记录顶点 u 到其他顶点的最短路径。 -
path[]数组用于记录最短路径从那个顶点过来。 -
visited[]数组用于记录是否被访问过。
2、代码实现：
#define MAX_LENGTH 2147483647 //地图中最大距离，表示正无穷
// 求顶点u到其他顶点的最短路径
void BFS_MIN_Disrance(Graph G,int u){
for(i=0; i<G.vexnum; i++){
visited[i]=FALSE; //初始化访问标记数组
d[i]=MAX_LENGTH; //初始化路径长度
path[i]=-1; //初始化最短路径记录
}
InitQueue(Q); //初始化辅助队列
d[u]=0;
visites[u]=TREE;
EnQueue(Q,u);
while(!isEmpty[Q]){ //BFS算法主过程
DeQueue(Q,u); //队头元素出队并赋给u
for(w=FirstNeighbor(G,u);w>=0;w=NextNeighbor(G,u,w)){
if(!visited[w]){
d[w]=d[u]+1;
path[w]=u;
visited[w]=TREE;
EnQueue(Q,w); //顶点w入队
}
}
}
}
6.4.3. 单源最短路径问题——Dijkstra算法
- BFS算法的局限性：BFS算法求单源最短路径只适⽤于⽆权图，或所有边的权值都相同的图。
- Dijkstra算法能够很好的处理带权图的单源最短路径问题，但不适⽤于有负权值的带权图。
- 使用 Dijkstra算法求最短路径问题，需要使用三个数组：
-
final[]数组用于标记各顶点是否已找到最短路径。 -
dist[]数组用于记录各顶点到源顶点的最短路径长度。 -
path[]数组用于记录各顶点现在最短路径上的前驱。
代码实现
#define MAX_LENGTH = 2147483647;
// 求顶点u到其他顶点的最短路径
void BFS_MIN_Disrance(Graph G,int u){
for(int i=0; i<G.vexnum; i++){ //初始化数组
final[i]=FALSE;
dist[i]=G.edge[u][i];
if(G.edge[u][i]==MAX_LENGTH || G.edge[u][i] == 0)
path[i]=-1;
else
path[i]=u;
final[u]=TREE;
}
for(int i=0; i<G.vexnum; i++){
int MIN=MAX_LENGTH;
int v;
// 循环遍历所有结点，找到还没确定最短路径，且dist最⼩的顶点v
for(int j=0; j<G.vexnum; j++){
if(final[j]!=TREE && dist[j]<MIN){
MIN = dist[j];
v = j;
}
}
final[v]=TREE;
// 检查所有邻接⾃v的顶点路径长度是否最短
for(int j=0; j<G.vexnum; j++){
if(final[j]!=TREE && dist[j]>dist[v]+G.edge[v][j]){
dist[j] = dist[v]+G.edge[v][j];
path[j] = v;
}
}
}
}
6.4.4. 各顶点间的最短路径问题——Floyd算法
-
Floyd算法：求出每⼀对顶点之间的最短路径，使⽤动态规划思想，将问题的求解分为多个阶段。
-
Floyd算法可以⽤于负权值带权图，但是不能解决带有“负权回路”的图（有负权值的边组成回路），这种图有可能没有最短路径。
-
Floyd算法使用到两个矩阵：
-
dist[][]：目前各顶点间的最短路径。 -
path[][]：两个顶点之间的中转点。
-
-
代码实现：
int dist[MaxVertexNum][MaxVertexNum];
int path[MaxVertexNum][MaxVertexNum];
void Floyd(MGraph G){
int i,j,k;
// 初始化部分
for(i=0;i<G.vexnum;i++){
for(j=0;j<G.vexnum;j++){
dist[i][j]=G.Edge[i][j];
path[i][j]=-1;
}
}
// 算法核心部分
for(k=0;k<G.vexnum;k++){
for(i=0;i<G.vexnum;i++){
for(j=0;j<G.vexnum;j++){
if(dist[i][j]>dist[i][k]+dist[k][j]){
dist[i][j]=dist[i][k]+dist[k][j];
path[i][j]=k;
}
}
}
}
}
4.最短路径算法比较：
| BFS算法 | Dijkstra算法 | Floyd算法 | |
|---|---|---|---|
| 无权图 | ✔ | ✔ | ✔ |
| 带权图 | ✘ | ✔ | ✔ |
| 带负权值的图 | ✘ | ✘ | ✔ |
| 带负权回路的图 | ✘ | ✘ | ✘ |
| 时间复杂度 | O(|V|^2)或(|V|+|E|) | O(|V|^2) | O(|V|^3) |
| 通常⽤于 | 求⽆权图的单源最短路径 | 求带权图的单源最短路径 | 求带权图中各顶点间的最短路径 |
6.4.5. 有向⽆环图描述表达式
1、有向⽆环图：若⼀个有向图中不存在环，则称为有向⽆环图，简称 DAG图（Directed Acyclic Graph）。
DAG描述表达式：((a+b)*(b*(c+d))+(c+d)*e)*((c+d)*e)
2、有向无环图描述表达式的解题步骤：
- Step 1:把各个操作数不重复地排成一排
- Step 2:标出各个运算符的生效顺序 (先后顺序有点出入无所谓)
- Step 3:按顺序加入运算符，注意“分层”
- Step 4:从底向上逐层检查同层的运算符是否可以合体
6.4.6. 拓扑排序
1、AOV网(Activity on Vertex Network，用顶点表示活动的网)：用DAG图(有向无环图)表示一个工程。顶点表示活动，有向边<Vi,Vj>表示活动Vi必须先于活动Vj进行。
2、拓扑排序：在图论中，由⼀个有向⽆环图的顶点组成的序列，当且仅当满⾜下列条件时，称为该图的⼀个拓扑排序：
- 每个顶点出现且只出现⼀次；
- 若顶点 A 在序列中排在顶点 B 的前⾯，则在图中不存在从顶点 B 到顶点 A 的路径。
- 或定义为：拓扑排序是对有向⽆环图的顶点的⼀种排序，它使得若存在⼀条从顶点 A 到顶点 B 的路径，则在排序中顶点 B 出现在顶点 A 的后⾯。每个 AOV ⽹都有⼀个或多个拓扑排序序列。
3、拓扑排序的实现:
- 从AOV网中选择一个没有前驱 (入度为0) 的顶点并输出
- 从网中删除该顶点和所有以它为起点的所有边。
- 重复1和2直到当前的AOV网为空或当前网中不存在无前驱的顶点为止。
4、代码实现拓扑排序（邻接表实现）：
#define MaxVertexNum 100 //图中顶点数目最大值
typedef struct ArcNode{ //边表结点
int adjvex; //该弧所指向的顶点位置
struct ArcNode *nextarc; //指向下一条弧的指针
}ArcNode;
typedef struct VNode{ //顶点表结点
VertexType data; //顶点信息
ArcNode *firstarc; //指向第一条依附该顶点的弧的指针
}VNode,AdjList[MaxVertexNum];
typedef struct{
AdjList vertices; //邻接表
int vexnum,arcnum; //图的顶点数和弧数
}Graph; //Graph是以邻接表存储的图类型
// 对图G进行拓扑排序
bool TopologicalSort(Graph G){
InitStack(S); //初始化栈，存储入度为0的顶点
for(int i=0;i<g.vexnum;i++){
if(indegree[i]==0)
Push(S,i); //将所有入度为0的顶点进栈
}
int count=0; //计数，记录当前已经输出的顶点数
while(!IsEmpty(S)){ //栈不空，则存入
Pop(S,i); //栈顶元素出栈
print[count++]=i; //输出顶点i
for(p=G.vertices[i].firstarc;p;p=p=->nextarc){
//将所有i指向的顶点的入度减1，并将入度为0的顶点压入栈
v=p->adjvex;
if(!(--indegree[v]))
Push(S,v); //入度为0，则入栈
}
}
if(count<G.vexnum)
return false; //排序失败
else
return true; //排序成功
}
6.4.7. 关键路径
1、AOE 网：在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销（如 完成活动所需的时间），称之为⽤边表示活动的⽹络，简称 AOE ⽹ (Activity On Edge NetWork)。
2、AOE⽹具有以下两个性质：
- 只有在某顶点所代表的事件发⽣后，从该顶点出发的各有向边所代表的活动才能开始；
- 只有在进⼊某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发⽣。 另外，有些活动是可以并⾏进⾏的。
3、在 AOE ⽹中仅有⼀个⼊度为 0 的顶点，称为开始顶点（源点），它表示整个⼯程的开始； 也仅有⼀个出度为 0 的顶点，称为结束顶点（汇点），它表示整个⼯程的结束。
- 从源点到汇点的有向路径可能有多条，所有路径中，具有最⼤路径⻓度的路径称为关键路径，⽽把关键路径上的活动称为关键活动。
- 完成整个⼯程的最短时间就是关键路径的⻓度，若关键活动不能按时完成，则整个 ⼯程的完成时间就会延⻓。
4、求和活动和事件的最早和最迟发生时间
1.求所有事件的最早发生时间ve(): 按拓扑排序序列，依次求各个顶点的 ve(k)即事件的关键路劲。
2.求所有事件的最迟发生时间 vl(): 按逆拓扑排序序列，依次求各个顶点的 vl(k)即从后往前推（最后一个点的最早和最迟相等）。
3.求所有活动的最早发生时间 e(): 若边 < vk,v; > 表示活动 ai，则有 e(i) = ve(k)。
4.求所有活动的最迟发生时间 1(): 若边 < Vk,v; > 表示活动 a，则有 l(i) = vlj)- Weight(vk,v;).
5.求所有活动的时间余量 d(): d() =l() - e(i)=最早-最迟。
5、关键活动、关键路径的特性：
若关键活动耗时增加，则整个⼯程的⼯期将增⻓。
缩短关键活动的时间，可以缩短整个⼯程的⼯期。
当缩短到⼀定程度时，关键活动可能会变成⾮关键活动。
可能有多条关键路径，只提⾼⼀条关键路径上的关键活动速度并不能缩短整个⼯程的⼯期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短⼯期的⽬的。
第七章 查找
7.1 查找概念
- 查找：在数据集合中寻找满足某种条件的数据元素的过程称为查找。
- 查找表(查找结构)：用于查找的。数据集合称为查找表，它由同一类型的数据元素 (或记录)组成。
- 关键字：数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的。
- 对查找表的常⻅操作：
- 查找符合条件的数据元素
- 插⼊、删除某个数据元素
如下举例：
- 查找长度：在查找运算中，需要对比关键字的次数称为查找长度。
- 平均查找长度(ASL，Average Search Length)： 所有查找过程中进行关键字的比较次数的平均值。
7.2 顺序查找
-
顺序查找，又叫“线性查找”，通常用于线性表算法。
-
思想：从头到 jio 个找 (或者反过来也OK)
代码实现：
typedef struct{ //查找表的数据结构（顺序表）
ElemType *elem; //动态数组基址
int TableLen; //表的长度
}SSTable;
//顺序查找
int Search_Seq(SSTable ST,ElemType key){
int i;
for(i=0;i<ST.TableLen && ST.elem[i]!=key;++i);
// 查找成功返回数组下标，否则返回-1
return i=ST.TableLen? -1 : i;
}
哨兵方式代码实现：
typedef struct{ //查找表的数据结构（顺序表）
ElemType *elem; //动态数组基址
int TableLen; //表的长度
}SSTable;
//顺序查找
int Search_Seq(SSTable ST,ElemType key){
ST.elem[0]=key;
int i;
for(i=ST.TableLen;ST.elem[i]!=key;--i)
// 查找成功返回数组下标，否则返回0
return i;
}
用查找判定树分析ASL
-
一个成功结点的查找长度=自身所在层数
-
一个失败结点的查找长度 =其父节点所在
-
层数默认情况下，各种失败情况或成功情况都等概率发生
7.3 折半查找
【折半查找概念】
- 折半查找，又称“二分查找”，仅适用于有序的顺序表
折半查找代码实现：
typedef struct{
ElemType *elem;
int TableLen;
}SSTable;
// 折半查找
int Binary_Search(SSTable L,ElemType key){
int low=0,high=L.TableLen,mid;
while(low<=high){
mid=(low+high)/2;
if(L.elem[mid]==key)
return mid;
else if(L.elem[mid]>key)
high=mid-1; //从前半部分继续查找
else
low=mid+1; //从后半部分继续查找
}
return -1;
}
- 折半查找判定树的构造：
，如果当前 low 和 high 之间有奇数个元素，则 mid 分隔后，左右两部分元素个数相等；如果当前 low 和 high 之间有偶数个元素，则 mid 分隔后，左半部分⽐右半部分少⼀个元素。
- 折半查找的判定树中，若
- 折半查找的判定树⼀定是平衡⼆叉树。折半查找的判定树中，只有最下⾯⼀层是不满的。因此，元素个数为 n 时树⾼
。
- 判定树结点关键字：左<中<右，满⾜⼆叉排序树的定义。失败结点：
个（等于成功结点的空链域数量）
- 折半查找的查找效率：折半查找的时间复杂度 = 。
7.4 分块查找
分块查找所针对的情况：块内无序、块间有序。
索引表及顺序表代码
// 索引表
typedef struct{
ElemType maxValue;
int low,high;
}Index;
// 顺序表存储实际元素
ElemType List[100];
- 查找目标关键字所在分块可使用顺序查找和折半查找两种方式。
- 若使用折半查找且索引表中不包含⽬标关键字，则最终要停在 low > high，要在 low 所指分块中查找目标关键字。
- 查找效率分析（ASL）：假设⻓度为 n 的查找表被均匀地分为 b 块，每块 s 个元素。设索引查找和块内查找的平均查找⻓度分别为 ASL=LI+LS
7.5 红黑树
7.5.1 为什么要发明红黑树？
- 平衡二又树AVL：插入/删除 很容易破坏“平衡”特性，需要频繁调整树的形态。如:插入操作导致平衡，则需要先计算平衡因子，找到最小不平衡子树 (时间开销大)，再进行L/RR/LR/RL调整；
- 红黑树 RBT：插入/删除 很多时候不会破坏“红黑”特性，无需频繁调整树的形态。即便需要调整,般都可以在常数级时间内完成；
- 平衡二叉树：适用于以查为主、很少插入/删除的场景；
红黑树：适用于频繁插入、删除的场景，实用性更强。
7.5.2 红黑树的定义
- 必须是二叉排序树且每个结点或是红色，或是黑色的；
- 根节点是黑色的；
- 叶结点 (外部结点、NULL结点、失败结点) 均是黑色的；
- 不存在两个相邻的红结点(即红结点的父节点和孩子结点均是黑色)；
- 对每个结点，从该节点到任一叶结点的简单路径上，所含黑结点的数目相同。
- 结点的黑高bh --从某结点出发 (不含该结点)到达任一空叶结点的路径上黑结点总数。
- 性质1:从根节点到叶结点的最长路径不大于最短路径的2倍。
-
性质2:有n个内部节点的红黑树高度
。
7.5.3 红黑树的插入
- 先查找，确定插入位置(原理同二叉排序树)，插入新结点
- 新结点是根-一染为黑色
- 新结点非根一一染为红色
- 若插入新结点后依然满足红黑树定义，则插入结束
- 若插入新结点后不满足红黑树定义，需要调整，使其重新满足红黑树定义
- 黑叔:旋转+染色
- LL型:右单旋，父换爷+染色
- RR型:左单旋，父换爷+染色
- LR型:左、右双旋，儿换爷+染色
- RL型:右、左双旋，儿换爷+染色
- 红叔:染色+变新
- 叔父爷染色，爷变为新结点
7.6 B树和B+树
7.6.1 B树
B树，⼜称多路平衡查找树，B树中所有结点的孩⼦个数的最⼤值称为B树的阶，通常⽤m表示。⼀棵m阶B树或为空树，或为满⾜如下特性的m叉树：
- 树中每个结点⾄多有 m 棵⼦树，即⾄多含有 m-1 个关键字。
- 若根结点不是终端结点，则⾄少有两棵⼦树。
- 除根结点外的所有⾮叶结点⾄少有 ⌈ m / 2 ⌉棵⼦树，即⾄少含有 ⌈ m / 2 ⌉ - 1个关键字。（为了保证查找效率，每个结点的关键字不能太少）
-
所有的叶结点都出现在同⼀层次上，并且不带信息（可以视为外部结点或类似于折半查找判定树的查找失败结点，实际上这些结点不存在，指向这些结点的指针为空）。
m阶B树的核⼼特性：
- 根节点的⼦树数∈ [ 2 , m ] ∈[2, m]∈[2,m]，关键字数 ∈ [ 1 , m − 1 ] ∈[1, m-1]∈[1,m−1]。
- 其他结点的⼦树数∈ [ ⌈ m / 2 ⌉ , m ] ∈[⌈m/2⌉ , m]∈[⌈m/2⌉,m]；关键字数∈ [ − 1 , m − 1 ] ∈[ -1, m-1]∈[−1,m−1]。
- 对任⼀结点，其所有⼦树⾼度都相同。
- 关键字的值：⼦树0 < 关键字1 < ⼦树1 < 关键字2 < ⼦树2 <…. (类⽐⼆叉查找树左<中<右)
B树的⾼度：含 n 个关键字的 m叉B树，最⼩⾼度、最⼤⾼度是多少？
- logmn+1≤h≤log⌈m/2⌉2n+1+1
7.6.2 B树的基本操作
B树的查找：
- B树的查找操作与二叉查找树类似。B树的查找包含两个基本操作：① 在B树中找结点；② 在结点中找关键字。B树常存储在磁盘上，因此前一个查找操作在磁盘上进行，后一个查找操作在内存中进行。在B树中查找到某个结点后，先在有序表中进行查找，若找到则查找成功，否则按照对应指针信息到所指的子树中去查找。查找到叶子结点（对应指针为空指针），则说明树中没有对应的关键字，查找失败。
B树的插入：将关键字 key 插入到B树的过程：
- 定位：利用B树的查找算法，找到插入该关键字的最底层中的某个非叶子结点。（插入位置一定是最底层的某个非叶子结点！）
- 插入：B树中，每个非失败节点的关键字个数都在区间[ ⌈ m / 2 ⌉ − 1 , m − 1 ] [⌈m/2⌉- 1,m-1][⌈m/2⌉−1,m−1]内。若插入关键字 key 之后结点关键字个数小于m，则可以直接插入；否则必须对结点进行分裂。
- 分裂：从结点的中间位置（⌈ m / 2 ⌉ ⌈m/2⌉⌈m/2⌉）将其中的关键字分为两部分，左半部分包含的关键字放到原结点中，右半部分包含的关键字放到新节点中，中间位置（⌈ m / 2 ⌉ ⌈m/2⌉⌈m/2⌉）的关键字则插入原节点的父节点。若此时父节点的关键字也超过了上限，则对父节点继续进行分裂操作，直到这个过程传到根节点为止，进而导致B树的高度增加。
B树的删除：
- 非终端结点的删除：使用直接前驱或者直接后继来代替被删除的关键字，转换为删除终端结点。
- 终端结点的删除，具体分为三种情况
- 直接删除关键字：若删除关键字所在结点关键字个数 ≥ ⌈ m / 2 ⌉ ≥⌈m/2⌉≥⌈m/2⌉，则可直接删除。
- 兄弟够借：若删除关键字所在结点关键字个数 = ⌈ m / 2 ⌉ − 1 =⌈m/2⌉-1=⌈m/2⌉−1，且与此结点相邻的左（或右）兄弟结点关键字个数 ≥ ⌈ m / 2 ⌉ ≥⌈m/2⌉≥⌈m/2⌉，则需调整该节点、左（或右）兄弟结点及其双亲结点（父子换位法）以达到新的平衡。
- 兄弟不够接：若删除关键字所在结点关键字个数 = ⌈ m / 2 ⌉ − 1 =⌈m/2⌉-1=⌈m/2⌉−1，且与此结点相邻的左（或右）兄弟结点关键字个数 = ⌈ m / 2 ⌉ − 1 =⌈m/2⌉-1=⌈m/2⌉−1，则将该节点、左（或右）兄弟结点及其双亲结点中的关键字进行合并。
7.6.3 B+树
一棵m阶的B+树需满足以下条件：
- 每个分支节点最多有m棵子树（孩子结点）。
- 非叶根结点至少有两颗子树，其他每个分支结点至少有⌈ m / 2 ⌉ ⌈m/2⌉⌈m/2⌉棵子树。
- 结点的子树个数与关键字个数相同。
- 所有叶子结点包含所有关键字及指向相应记录的指针，叶子结点中将关键字按大小排列，并且相邻叶子结点按大小顺序相互链接起来。（说明B+树支持顺序查找）
- 所有分支节点仅包含它的各个节点中关键字的最大值及指向其子节点的指针。
7.6.4 B树和B+树的比较
（1）m阶B树：结点中的n个关键字对应n+1棵子树；
m阶B+树：结点中的n个关键字对应n棵子树。
（2）m阶B树：根节点的关键字数n[1,m-1]。其他结点的关键字数n[[m/2]-1,m-1];
m阶B+树：根节点的关键字数n[1,m]其他结点的关键字数n[[m/2],m]。
（3）m阶B树：在B树中，各结点中包含的关键字是不重复的；
m阶B+树：在B+树中，叶结点包含全部关键字非叶结点中出现过的关键字也会出现在叶结点中。
（4）m阶B树：B树的结点中都包含了关键字对应的记录的存储地址；
m阶B+树：在B+树中，叶结点包含信息，所有非叶结点仅起索引作用，非叶结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址。
7.7 散列查找及其性能分析
7.7.1 散列表的基本概念
- 散列函数：一个把查找表中的关键字映射成该关键字对应的地址的函数，记作H a s h ( k e y ) = A d d r Hash(key)=AddrHash(key)=Addr。
- 散列函数可能会把两个或两个以上的不同关键字映射到同一地址，称这种情况为冲突。发生碰撞的不同关键字称为同义词。
- 散列表：根据关键字而直接进行访问的数据结构。散列表建立了关键字和存储地址之间的一种直接映射关系。
散列函数的构造方法
- 直接定址法：直接取关键字的某个线性函数值为散列地址，散列函数为 H ( k e y ) = k e y 或 H ( k e y ) = a × k e y + b 。这种方法计算简单，不会产生冲突。缺点是空位较多，会造成存储空间浪费。
- 除留余数法：假定散列表表长 m，取一个不大于但最接近 m 的质数 p，利用散列函数 H ( k e y ) = k e y % p将关键字转换为散列地址。p取质数是因为这样可以使关键字通过散列函数转换后等概率地映射到散列空间上的任一地址。
- 数字分析法：假设关键字是 r进制数，而r个数码在个位上出现的频率不一定相同，可能在某些位上分布的均匀一些，而在某些位分布的不均匀。此时应选数码分布均匀的若干位作为散列地址。
- 平方取中法：这种方法取关键字平方值的中间几位作为散列地址，具体取多少位视具体情况而定。这种方法得到的散列地址与关键字的每一位都有关系，因此使得散列地址分布比较均匀。适用于关键字每位取值都不够均匀或均小于散列地址所需的位数。
7.7.2 散列查找及性能分析
散列查找执行步骤如下
- 初始化：A d d r = H a s h ( k e y )
- 检测查找表中地址为 Addr 的位置上是否有记录，若无记录，返回查找失败；若有记录，比较它和 key 的值，若相等则返回查找成功，否则执行步骤③。
- 用给定的处理冲突方式计算“下一个散列表地址”，并把 Addr 置为此地址，转入步骤②。
平均查找长度（ASL）：散列表查找成功的平均查找长度即找到表中已有表项的平均比较次数；散列表查找失败的平均查找长度即找不到待查的表项但能找到插入位置的平均比较次数。
第八章 排序
8.1. 排序的基本概念
- 排序：重新排列表中的元素，使表中元素满足按关键字有序的过程。
- 输入：n个记录 ，对应的关键字为 。
- 输出：输入序列的一个重排 ，使得 。
- 算法的稳定性：若待排序表中有两个元素和，其对应的关键字相同即 = ，且在排序前在的前面，若使用某一排序算法排序后，仍然在的前面，则称这个排序算法是稳定的，否则称排序算法是不稳定的。
- 排序算法的评价指标：时间复杂度、空间复杂度、稳定性。
- 排序算法的分类：
内部排序： 排序期间元素都在内存中——关注如何使时间、空间复杂度更低。
外部排序： 排序期间元素无法全部同时存在内存中，必须在排序的过程中根据要求不断地在内、外存之间移动——关注如何使时间、空间复杂度更低，如何使读/写磁盘次数更少。
8.2. 插入排序
8.2.1. 直接插入排序
- 算法思想：每次将一个待排序的记录按其关键字大小，插入到前面已经排好序的子序列中，直到全部记录插入完成。
代码实现（不带哨兵）:
// 对A[]数组中共n个元素进行插入排序
void InsertSort(int A[],int n){
int i,j,temp;
for(i=1; i<n; i++){
if(A[i]<A[i-1]){ //如果A[i]关键字小于前驱
temp=A[i];
for(j=i-1; j>=0 && A[j]>temp; --j)
A[j+1]=A[j]; //所有大于temp的元素都向后挪
A[j+1]=temp;
}
}
}
代码实现（带哨兵）：
// 对A[]数组中共n个元素进行插入排序
void InsertSort(int A[], int n){
int i,j;
for(i=2; i<=n; i++){
if(A[i]<A[i-1]){
A[0]=A[i]; //复制为哨兵，A[0]不放元素
for(j=i-1; A[0]<A[j]; --j)
A[j+1]=A[j];
A[j+1]=A[0];
}
}
}
- 算法效率分析：
- 时间复杂度：最好情况 O(n)，最差情况O()，平均情况 O()。
- 空间复杂度：O(1)。
- 算法稳定性：稳定。
- 适用性：适用于顺序存储和链式存储的线性表。
对链表进行插入排序代码实现：
//对链表L进行插入排序
void InsertSort(LinkList &L){
LNode *p=L->next, *pre;
LNode *r=p->next;
p->next=NULL;
p=r;
while(p!=NULL){
r=p->next;
pre=L;
while(pre->next!=NULL && pre->next->data<p->data)
pre=pre->next;
p->next=pre->next;
pre->next=p;
p=r;
}
}
8.2.2. 折半插入排序
- 算法思路： 每次将一个待排序的记录按其关键字大小，使用折半查找找到前面子序列中应该插入的位置并插入，直到全部记录插入完成。
- 注意：一直到low>high 时才停止折半查找。当mid所指元秦等于当前元素时，应继续令low=mid+1，以保证“稳定性”。最终应将当前元素插入到low 所指位置 (即 high+1)
代码实现：
//对A[]数组中共n个元素进行折半插入排序
void InsertSort(int A[], int n){
int i,j,low,high,mid;
for(i=2; i<=n; i++){
A[0]=A[i]; //将A[i]暂存到A[0]
low=1; high=i-1;
while(low<=high){ //折半查找
mid=(low+high)/2;
if(A[mid]>A[0])
high=mid-1;
else
low=mid+1;
}
for(j=i-1; j>high+1; --j)
A[j+1]=A[j];
A[high+1]=A[0];
}
}
- 与直接插入排序相比，比较关键字的次数减少了，但是移动元素的次数没有变。时间复杂度仍为 O(n²)。
8.2.3. 希尔排序
- 算法思路：先追求表中元素的部分有序，再逐渐逼近全局有序，以减小插入排序算法的时间复杂度。
-
具体实施：希尔排序:先将待排序表分割成若干形如
的“特殊”子表，对各个子表分别进行直接插入排序。缩小增量d，重复上述过程，直到d=1为止。
希尔排序代码实现：
// 对A[]数组共n个元素进行希尔排序
void ShellSort(ElemType A[], int n){
int d,i,j;
for(d=n/2; d>=1; d=d/2){ //步长d递减
for(i=d+1; i<=n; ++i){
if(A[i]<A[i-d]){
A[0]=A[i]; //A[0]做暂存单元，不是哨兵
for(j=i-d; j>0 && A[0]<A[j]; j-=d)
A[j+d]=A[j];
A[j+d]=A[0];
}
}
}
}
-
算法效率分析：
- 时间复杂度：希尔排序时间复杂度依赖于增量序列的函数。最差情况O()，n在某个特顶范围时可达O() 。
- 空间复杂度：O(1)
- 算法稳定性：不稳定。
8.3. 交换排序
8.3.1. 冒泡排序
- 算法思路：从后往前（或从前往后）两两比较相邻元素的值，若为逆序（即 A [ i − 1 ] > A [ i ]) ，则交换它们，直到序列比较完。如此重复最多 n-1 次冒泡就能将所有元素排好序。为保证稳定性，关键字相同的元素不交换。
冒泡排序代码实现：
// 交换a和b的值
void swap(int &a, int &b){
int temp=a;
a=b;
b=temp;
}
// 对A[]数组共n个元素进行冒泡排序
void BubbleSort(int A[], int n){
for(int i=0; i<n-1; i++){
bool flag = false; //标识本趟冒泡是否发生交换
for(int j=n-1; j>i; j--){
if(A[j-1]>A[j]){
swap(A[j-1],A[j]);
flag=true;
}
}
if(flag==false)
return; //若本趟遍历没有发生交换，说明已经有序
}
}
-
算法效率分析：
- 时间复杂度：最好情况O(n) ，最差情况O()，平均情况O()。
- 空间复杂度：O(1)。
- 稳定性：稳定。
- 适用性：冒泡排序可以用于顺序表、链表。
8.3.2. 快速排序
- 算法思路：在待排序表 L [ 1... n ] 中任选一个元素 pivot 作为枢轴（通常取首元素），通过一趟排序将待排序表分为独立的两部分 L [ 1... k − 1 ] 和 L [ k − 1... n ] 。使得 L [ 1... k − 1 ] 中的所有元素小于 pivot，L [ k − 1... n ]中的所有元素大于等于 pivot，则 pivot 放在了其最终位置 L [ k ]上。重复此过程直到每部分内只有一个元素或空为止。
- 快速排序是所有内部排序算法中性能最优的排序算法。
- 在快速排序算法中每一趟都会将枢轴元素放到其最终位置上。（可用来判断进行了几趟快速排序）
- 快速排序可以看作数组中n个元素组织成二叉树，每趟处理的枢轴是二叉树的根节点，递归调用的层数是二叉树的层数。
快速排序代码实现：
// 用第一个元素将数组A[]划分为两个部分
int Partition(int A[], int low, int high){
int pivot = A[low];
while(low<high){
while(low<high && A[high]>=pivot)
--high;
A[low] = A[high];
while(low<high && A[low]<=pivot)
++low;
A[high] = A[low];
}
A[low] = pivot;
return low;
}
// 对A[]数组的low到high进行快速排序
void QuickSort(int A[], int low, int high){
if(low<high){
int pivotpos = Partition(A, low, high); //划分
QuickSort(A, low, pivotpos - 1);
QuickSort(A, pivotpos + 1, high);
}
}
-
算法效率分析：
- 时间复杂度：快速排序的时间复杂度 = O ( n × 递 归 调 用 的 层 数 ) 。最好情况 O(),最差情况 O() ，平均情况O()。
- 空间复杂度：快速排序的空间复杂度 = O ( 递 归 调 用 的 层 数 ) O(递归调用的层数)O(递归调用的层数)。最好情况O()，最差情况 O(n)，平均情况 O()。
8.4. 选择排序
- 选择排序思想： 每一趟在待排序元素中选取关键字最小（或最大）的元素加入有序子序列。
8.4.1. 简单选择排序
- 算法思路：每一趟在待排序元素中选取关键字最小的元素与待排序元素中的第一个元素交换位置。
简单选择排序代码实现：
// 交换a和b的值
void swap(int &a, int &b){
int temp = a;
a = b;
b = temp;
}
// 对A[]数组共n个元素进行选择排序
void SelectSort(int A[], int n){
for(int i=0; i<n-1; i++){ //一共进行n-1趟，i指向待排序序列中第一个元素
int min = i;
for(int j=i+1; j<n; j++){ //在A[i...n-1]中选择最小的元素
if(A[j]<A[min])
min = j;
}
if(min!=i)
swap(A[i], A[min]);
}
}
-
算法效率分析：
- 时间复杂度：无论待排序序列有序、逆序还是乱序，都需要进行 n-1 次处理，总共需要对比关键字(n−1)+(n−2)+. . .+1=n( n−1) /2 次，因此时间复杂度始终是O() 。
- 空间复杂度：O(1) 。
- 稳定性：不稳定。
- 适用性：适用于顺序存储和链式存储的线性表。
对链表进行简单选择排序：
void selectSort(LinkList &L){
LNode *h=L,*p,*q,*r,*s;
L=NULL;
while(h!=NULL){
p=s=h; q=r=NULL;
while(p!=NULL){
if(p->data>s->data){
s=p; r=q;
}
q=p; p=p->next;
}
if(s==h)
h=h->next;
else
r->next=s->next;
s->next=L; L=s;
}
}
8.4.2. 堆排序
- 算法思路：首先将存放在 L [ 1... n ] 中的n个元素建成初始堆，由于堆本身的特点，堆顶元素就是最大值。将堆顶元素与堆底元素交换，这样待排序列的最大元素已经找到了排序后的位置。此时剩下的元素已不满足大根堆的性质，堆被破坏，将堆顶元素下坠使其继续保持大根堆的性质，如此重复直到堆中仅剩一个元素为止。
- 在顺序存储的完全二叉树中：
- 非终端结点的编号 ：i ≤ [ n / 2 ]
- i 的左右孩子 ：2i 和 2i+1
- i 的父节点：[ i / 2 ]
堆排序代码实现：
// 对初始序列建立大根堆
void BuildMaxHeap(int A[], int len){
for(int i=len/2; i>0; i--) //从后往前调整所有非终端结点
HeadAdjust(A, i, len);
}
// 将以k为根的子树调整为大根堆
void HeadAdjust(int A[], int k, int len){
A[0] = A[k];
for(int i=2*k; i<=len; i*=2){ //沿k较大的子结点向下调整
if(i<len && A[i]<A[i+1])
i++;
if(A[0] >= A[i])
break;
else{
A[k] = A[i]; //将A[i]调整至双亲结点上
k=i; //修改k值，以便继续向下筛选
}
}
A[k] = A[0]
}
// 交换a和b的值
void swap(int &a, int &b){
int temp = a;
a = b;
b = temp;
}
// 对长为len的数组A[]进行堆排序
void HeapSort(int A[], int len){
BuildMaxHeap(A, len); //初始建立大根堆
for(int i=len; i>1; i--){ //n-1趟的交换和建堆过程
swap(A[i], A[1]);
HeadAdjust(A,1,i-1);
}
}
-
算法效率分析：
- 时间复杂度：O()。建堆时间 O(n) ，之后进行 n-1 次向下调整操作，每次调整时间复杂度为O()。
- 空间复杂度：O(1)。
- 稳定性：不稳定。
-
堆的插入：对于大（或小）根堆，要插入的元素放到表尾，然后与父节点对比，若新元素比父节点更大（或小），则将二者互换。新元素就这样一路==“上升”==，直到无法继续上升为止。
-
堆的删除：被删除的元素用堆底元素替换，然后让该元素不断==“下坠”==，直到无法下坠为止。
8.5. 归并排序
- 归并（Merge）：把两个或多个已经有序的序列合并成一个新的有序表。k路归并每选出一个元素，需对比关键字k-1次。
- 算法思想：先将数组进行拆分，每次拆成两份，然后继续拆分直到一组有两个元素为止，然后再进行两两整合排序，重复两两整合排序直至数组元素排序完成。
代码实现：
// 辅助数组B
int *B=(int *)malloc(n*sizeof(int));
// A[low,...,mid]，A[mid+1,...,high]各自有序，将这两个部分归并
void Merge(int A[], int low, int mid, int high){
int i,j,k;
for(k=low; k<=high; k++)
B[k]=A[k];
for(i=low, j=mid+1, k=i; i<=mid && j<= high; k++){
if(B[i]<=B[j])
A[k]=B[i++];
else
A[k]=B[j++];
}
while(i<=mid)
A[k++]=B[i++];
while(j<=high)
A[k++]=B[j++];
}
// 递归操作
void MergeSort(int A[], int low, int high){
if(low<high){
int mid = (low+high)/2;
MergeSort(A, low, mid);
MergeSort(A, mid+1, high);
Merge(A,low,mid,high); //归并
}
}
- 算法效率分析：
- 时间复杂度为O()。
- 空间复杂度：O(n)。
- 稳定性：稳定。
8.6. 基数排序
- 算法思想：把整个关键字拆分为d位，按照各个关键字位递增的次序（比如：个、十、百），做d趟“分配”和“收集”，若当前处理关键字位可能取得r个值，则需要建立r个队列。
- 分配：顺序扫描各个元素，根据当前处理的关键字位，将元素插入相应的队列。一趟分配耗时
- 收集：把各个队列中的结点依次出队并链接。一趟收集耗时。
文章来源地址https://www.toymoban.com/news/detail-476177.html
- 基数排序擅长处理的问题：
- 数据元素的关键字可以方便地拆分为d组，且d较小。
- 每组关键字的取值范围不大，即r较小。
- 数据元素个数n较大。
- 算法效率分析：算法效率分析：
- 时间复杂度：一共进行d趟分配收集，一趟分配需要，一趟收集需要，时间复杂度为
，且与序列的初始状态无关。
- 空间复杂度，其中为辅助队列数量。
- 稳定性：稳定。
- 时间复杂度：一共进行d趟分配收集，一趟分配需要，一趟收集需要，时间复杂度为
8.7. 内部排序算法总结
8.7.1. 内部排序算法比较
| 算法种类 | 最好时间复杂度 | 最坏时间复杂度 | 平均时间复杂度 | 空间复杂度 | 稳定性 |
| 直接插入排序 | 稳定 | ||||
| 冒泡排序 | 稳定 | ||||
| 简单选择排序 | 不稳定 | ||||
| 希尔排序 | 不稳定 | ||||
| 快速排序 | 不稳定 | ||||
| 堆排序 | 不稳定 | ||||
| 2路归并排序 | 稳定 | ||||
| 基数排序 | 稳定 |
8.7.2. 内部排序算法的应用
-
选取排序方法需要考虑的因素：
- 待排序的元素数目n。
- 元素本身信息量的大小。
- 关键字的结构及其分布情况。
- 稳定性的要求。
- 语言工具的条件，存储结构及辅助空间的大小等。
-
排序算法的选择：
- 若n较小，可采用 直接插入排序 或 简单选择排序。由于直接插入排序所需的记录移动次数较简单选择排序的多，因而当记录本身信息量较大时，用简单选择排序较好。
- 若文件的初始状态已按关键字基本有序，则选用直接插入排序或冒泡排序为宜。
- 若n较大，则应采用时间复杂度为的排序方法：快速排序、堆排序 或 归并排序。快速排序被认为是目前基于比较的内部排序方法中最好的方法，当待排序的关键字随机分布时，快速排序的平均时间最短。堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况，这两种排序都是不稳定的。若要求排序稳定且时间复杂度为，则可选用归并排序。但本章介绍的从单个记录起进行两两归并的排序算法并不值得提倡，通常可以将它和直接插入排序结合在一起使用。先利用直接插入排序求得较长的有序子文件，然后两两归并。直接插入排序是稳定的，因此改进后的归并排序仍是稳定的。
- 在基于比较的排序方法中，每次比较两个关键字的大小之后，仅出现两种可能的转移，因此可以用一棵二叉树来描述比较判定过程，由此可以证明：当文件的n个关键字随机分布时，任何借助于“比较”的排序算法，至少需要的时间。
- 若n很大，记录的关键字位数较少且可以分解时，采用 基数排序 较好。
- 当记录本身信息量较大时，为避免耗费大量时间移动记录，可用链表作为存储结构。
8.8. 外部排序
8.8.1. 外部排序的基本概念和方法
- 外部排序：对大文件进行排序时，因为文件中的记录很多、信息量庞大，无法将整个文件复制进内存中进行排序。因此需要将待排序的记录存储在外存上，排序时再把数据一部分一部分地调入内存进行排序，在排序过程中需要多次进行内存和外存之间的交换。
- 外部排序的步骤：
① 跟据内存缓冲区大小，将外存上的文件分成 r 个子文件，依次读入内存并利用内部排序方法对它们进行排序，并将排序后得到的有序子文件重新写回外存（归并段）。
② 对这些归并段进行 S 趟 k 路归并，使归并段（有序子文件)逐渐由小到大，直至得到整个有序文件为止，其中（需要在内存中分配k个输入缓冲区和1个输出缓冲区） - 如何进行 k 路归并：
① 把k个归并段的块读入k个输入缓冲区。
② 用“归并排序”的方法从k个归并段中选出几个最小记录暂存到输出缓冲区中。
③ 当输出缓冲区满时，写出外存。 - 外部排序时间开销 = 读写外存的时间 + 内部排序所需时间＋内部归并所需时间
- 优化：
①增加归并路数k，但是需要增加相应的输入缓冲区，且每次从k个归并段中选出一个最小元素需要对比 (k-1) 次。
② 减少初始归并段数量r。
8.8.2. 败者树
- 败者树解决的问题：使用多路平衡归并可以减少归并趟数，但是从 k 个归并段选出一个最小元素需要对比关键字 (k-1) 次，构造败者树可以使关键字对比次数减少到。
- 败者树可视为一棵完全二叉树（多了一个头头）。k个叶结点分别对应k个归并段中当前参加比较的元素，非叶子结点用来记忆左右子树中的“失败者”，而让胜者往上继续进行比较，一直到根结点。
8.8.3. 置换-选择排序（生成初始归并段）
- 置换-选择排序：产生更长的初始归并段，从而减少初始归并段数量。
- 设初始待排文件为FI，初始归并段输出文件为FO，内存工作区为WA，FO和WA的初始状态为空，WA可容纳w个记录，置换-选择算法的步骤如下：
- 从FI输入w个记录到工作区WA。
- 从WA中选出其中关键字取最小值的记录，记为MINIMAX记录。
- 将MINIMAX记录输出到FO中去。
- 若FI不空，则从FI输入下一个记录到WA中。
- 从WA中所有关键字比MINIMAX记录的关键字大的记录中选出最小关键字记录，作为新的MINIMAX记录。
- 重复③~⑤，直至在WA中选不出新的MINIMAX记录为止，由此得到一个初始归并段，输出一个归并段的结束标志到FO中去。
- 重复②~⑥，直至WA为空。由此得到全部初始归并段。
8.8.4. 最佳归并树
- 最佳归并树：调整多个初始归并段进行多路归并时的顺序，从而减少多路归并时I/O次数。
- 理论基础：每个初始归并段对应一个叶子结点，把归并段的块数作为叶子的权值，归并树的WPL= 树中所有叶结点的带权路径长度之和。归并过程中的磁盘I/O次数 = 归并树的WPL* 2。
- 注意：k叉归并的最佳归并树一定是严格k叉树，即树中只有度为k、度为0的结点。
- 构造k叉哈夫曼树：每次选择k个根节点权值最小的树合并，并将k个根节点的权值之和作为新的根节点的权值。
- 补充虚段：
① (初始归并段数量 -1) % (k-1)= 0，说明刚好可以构成严格k叉树，此时不需要添加虚段
② (初始归并段数量 -1) % (k-1) = 0，则需要补充(k-1) - u 个虚段
到了这里，关于【王道考研】王道数据结构与算法详细笔记（全）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
