DS
考试内容
一、数据结构的有关概念
考纲要求：
1．掌握数据结构的有关概念，理解逻辑结构与物理结构之间的关系。
2．掌握数据结构的几种基本结构。
3．掌握抽象数据类型的表示与实现方法。
4．熟悉算法分析的分析方法。
考点总结：
数据结构的几种基本结构
- 集合（不常考）
- 线性结构（1:1）
- 树形结构（1:n）
- 图形结构（m:n）
数据结构的基本概念和术语
标识符只能以英文字母或下画线开头，不能以数字开头。
数据结构包括逻辑结构和存储结构两个层次
线性结构：线性表 ，栈， 队列 ，双队列，串。
非线性结构：二维数组，树，图。
它们都可以顺序存储和链式存储。
- 数据
数据适用以描述客观食物且能够输入到计算机储存介质中能被计算机程序识别和处理的符号的总称，它是计算机加工的“原料”。
- 数据元素
数据元素是数据的基本单位。在计算机程序中常作为一个整体进行考虑和处理。
有时一个数据元素可以由若干数据项组成（此时往往把一个数据元素称为一条记录），数据项是具有独立含义的最小标识单位。
在某些情况下，往往也把数据元素简称为元素或结点。
- 数据项
数据项是数据结构中讨论的最小单位，是数据记录中最基本、不可分的数据单位。
- 数据对象
具有相同性质的数据元素的集合，是数据的一个子集。
例如：整数数据对象：$N={0,1,2,…}$
字母字符数据对象：C={‘A’,‘B’,‘C’,…‘F’}
- 数据的逻辑结构
（1）定义：逻辑结构用以描述某一数据对象的所有数据元素之间存在的固有逻辑关系。
（2）逻辑结构的二元组描述方法：
Data_Structure={D,R}，（$D$是某一数据对象，$R$是该对象中所有数据元素之间的关系的有限集合）。
- 逻辑结构的分类
（1）线性结构（线性表、栈、队列）
（2）非线性结构（树、图）
- 数据的存储结构（物理结构）
（1）定义：数据的存储结构是数据的逻辑结构在计算机中的存储方式或表示方式。
（2）存储结构的分类：一、顺序存储结构
循环队列使用顺序表表示的队列。二、链式存储结构
链式存储设计时，结点内的存储单元地址一定连续。三、散列存储结构（哈希表）
四、索引存储结构
[注]：栈是一种抽象数据结构，可采用顺序存储或链式存储，只表示逻辑结构。
- 数据类型
（1）定义：数据类型是一个值的集合和定义在这个集合上的一组操作的总称，可分为简单的数据类型（基本数据类型）和抽象数据类型两大类。
（2）$C$语言中的基本数据类型（固有数据类型）：
int（整型，占4个字节），char（字符型，占1个字节），float（浮点型，占4个字节），double（双精度浮点型，占8个字节），void（空型，占0个字节），long(长整型数据类型，占8个字节)；注意1字节（Byte）等于8比特（bit），或者说1字节占8位（3）抽象数据结构类型：是以基本数据类型或已定义好的其他抽象数据类型为基础，采用数据结构的技术进一步构造出来的复杂数据类型。
抽象数据类型
抽象数据类型的三个组成部分：数据对象、数据关系和基本操作
1.定义：抽象数据类型是指数据逻辑结构及与之相关的操作
例如：矩阵$+$（求转置、矩阵加、矩阵乘、求逆、求特征向量）$=$矩阵的抽象数据类型。
2.抽象数据类型的三元组表示方法：
抽象数据类型可用三元组$(D,R,P)$表示。
其中：$D$是数据对象，$R$是$D$上若干关系的集合，$P$是定义在$D$上的基本操作的集合。
一般用如下$ADT$格式来描述
2
3
4
5
数据对象D：<数据对象的定义>
数据关系R：<数据关系的定义>
基本操作P：<数据关系的定义>
}3.抽象数据类型的表示和实现
在高级语言中：抽象数据类型可以利用基本拿数据结构和已经定义好的其他抽象数据类型来实现。
在$C$语言中，用结构体(
structure)类型结合函数或子程序来实现抽象数据类型的定义。在$C++$语言中，是用类（
class）来定义抽象数据类型的。其中的成员函数就是用来定义抽象数据类型中的"操作"的。
关于三元组表的题目
一个$100\times 90$的整型稀疏矩阵有$10$个非零元素，设每个整型数占$2$个字节，则用三元组表存储该矩阵时，所需的字节数是？
【答】：<行(2B)，列(2B)，元素(2B)>，一共十个，所以这里是60B，再加上一个三元组表示行有多少，列有多少，元素总共有多少，又是一个6B，加一起66B。
用三元组表表示该数据：
(0,0,3)、(0,3,5)、(1,1,-1)、(2,0,2)
【注意】行表、列表从$0$开始
- 数据结构
- 相互之间存在一种或多种特定关系的 数据元素 的集合。
- 数据结构三要素：逻辑结构、存储结构、数据的运算
- 数据的逻辑结构独立于其存储结构
算法的有关概念及其分析
- 算法的定义：
- 为了解决某个问题而规定的一个有限长的操作序列。
- 一个算法应该是问题求解步骤的描述。
- 算法的特性：
以下特性是算法的必要条件，而非充分条件。
（1）有穷性：算法在执行有穷步能结束。
（2）确定性：算法中的每一步操作的定义都无二义性。
（3）可行性：每一条运算都能用已经实现的基本运算来实现。
（4）输入：有0个或者多个输入。
（5）输出：有一个或者多个输出。
- 算法的设计要求
（1）正确性：算法能够正确执行预先规定的功能要求。
（2）可读性：算法要易于理解。
（3）健壮性：算法具有很好的容错率。
- 算法的空间复杂度
主要在以下两个方面：
（1）存储空间的固定部分
（2）可变部分
尺寸大小在使用过程中是动态变化的，例如：动态栈或动态队列所用空间；通过
new和delete命令动态使用存储空间。
- 算法的时间复杂度（小题考试重点）
（1）算法中每条语句的运行时间
语句的执行时间$=$该语句执行次数（语句频率）$\times$语句执行一次所需时间
（2）算法的运行时间$T$
算法的运行时间$T=$算法中所有语句的语句频率之和。
（3）常用的时间复杂度比较关系为：
$O(1)\le O(log_{2}n)\le O(nlog_{2}n)\le O(n^2) \le … \le O(2^n)$
（4）算法的运行时间$T$的求解
- 存储密度
存储密度$\displaystyle =\frac{存储数据的空间}{存储数据的空间+其他空间}$
【例】
已知链表定义如下
2
3
4
char data[16];
struct node *next;
} LinkStrNode;如果每个字符占$1$个字节，指针占$4$个字节，则该链表的存储密度是？
【答】$\displaystyle \frac{16}{16+4}=0.8$
二、线性表
考纲要求：
1．掌握线性表的顺序存储方法及链式存储方法。
2．熟悉线性表的建立、插入、删除、搜索与归并算法。
3．了解一元多项式的表示方法及其应用。
考点总结：
线性表的基本概念
（1）线性表示具有相同数据类型的$n(n\ge0)$个数据元素的有限序列，通常记为：$L=(\alpha_1,\alpha_2,…,\alpha_{i-1},\alpha_{i},\alpha_{i+1},…,a_n)$，其中$L$是表名，$n$为表长，$n=0$时称为空表。
（2）运用在一个非空的线性表中，存在唯一的一个被称为"第一个"的数据元素（$a_1$）；存在唯一的一个被称做"最后一个"的数据元素$a_n$；除第一个元素以外，每个元素$a_i(i\not= 1)$都有且仅有一个直接前驱$a_{i-1}$；除最后一个元素以外，每个元素$a_i(i\not= n)$都有且仅有一个直接后继$a_{i+1}$。
顺序表的定义及相关算法
（1） 线性表的顺序存储：在内存中用一段地址连续的存储空间来依次顺序存放线性表中各元素，通常称其为顺序表。
（2） 元素$a_i$的地址：设$a_1$的存储地址的首地址为$Loc(a_i)$，且设每个数据元素占用$k$个存储单元，则第$i$个数据元素的存储地址首址为：$Loc(a_i)=Loc(a_1)+(i-1)\times k(2\le i\le n)$，类似于等差数列。
（3）顺序表的定义：可将data和len封装成一个结构体：
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
typedef struct
{
datatype data[MAXSIZE]; // 存放顺序表元素的数组
int len; // 顺序表长度
}SeqList;
// 声明
int main()
{
SeqList l;
...
// 进行操作
Init_SeqList(l);
Insert_SeqList(l, 1, 2);
...
return 0;
}（4）顺序表的初始化 Init_SeqList
2
3
4
{
L.len = 0;
}（5）插入操作 Insert_SeqList
插入前：$\alpha_1,\alpha_2,…,\alpha_{i-1},\alpha_{i},\alpha_{i+1},…,a_n$
插入后：$\alpha_1,\alpha_2,…,\alpha_{i-1},e,\alpha_{i},\alpha_{i+1},…,a_n$
注意问题：
- 顺序表中数据区域分配有
MAXSIZE个存储单元，做插入操作时需要先检验表空间是否已满，表满的情况下不能再做插入。- 要检验插入位置的有效性，这里$i$的有效范围是：$0\le i\le n$，其中$n$为原表长。
- 将$a_n \sim a_i$依次顺序向后移动一个位置。
- 将$e$存放在腾出来的第$i$个位置上（即原来的）$a_i$的位置。
更新len值，即len ++,使len的数值加$1$。
2
3
4
5
6
7
8
9
10
11
{
int j;
if(i < 0 || i > L.len || L.len == MAXSIZE)
return 0;
for(j = L.len - 1; j >= i; -- j)
L.data[j + 1] = L.data[j];
L.data[i] = e;
++ L.len;
return 1;
}平均数据移动次数：$\frac{n}{2}$。
（6）删除操作 Delete_SeqList
删除前：$\alpha_1,\alpha_2,…,\alpha_{i-1},\alpha_{i},\alpha_{i+1},…,a_n$
删除后：$\alpha_1,\alpha_2,…,\alpha_{i-1},\alpha_{i+1},…,a_n$
注意问题：
- 删除第$i$个元素时候，要删除的元素必须真实存在，所以必须要检查$i$的取值是否有效，$i$的有效取值范围为$0\le i\le n-1$，否则第$i$个元素不存在。
- 空表时不能执行删除操作。
- 将$a_{i+1} \sim a_n$顺序向前移动一个位置。
- 更新$len$值，即
len --，使$len$数值减少$1$。
2
3
4
5
6
7
8
9
10
11
12
13
14
{
int j;
if(i < 0 || i > L->len - 1)
{
cout << "不存在第" << i << "个元素" << endl;
return 0;
}
// 如果存在进行删除操作
for(j = i; j <= L.len; j ++ )
L.data[j] = L.data[j + 1];
-- L.len;
return 1;
}平均数据移动次数为$\frac{n-1}{2}$。
（7）按值查找 Locate_SeqList
功能：在线性表中查找是否存在与给定值$e$相等的数据元素。
实现方法：从第一个元素$a_1$开始一次和$e$比较，知道找到一个与$e$相等的数据元素，则返回它在顺序表中的存储位置的下标值（注意：第一个元素的存储位置的下标值为0）；若查遍整个表都没有找到与$e$相等的元素，则返回$0$，表示查找失败。
2
3
4
5
6
7
8
{
int i = 0;
while(i <= L.len && L.data[i] != e)
i ++ ;
if(i > L.len) return 0;
else return (i + 1);
}（8）取表中元素 Get_SeqList
功能：根据所给序号$i$在线性表中查找相应的数据元素。
实现方法：首先确认所查找的数据元素序号是否合法，若合法则直接返回对应的元素值。否则报错。
2
3
4
5
6
7
8
9
{
if(i < 1 || i > L.len + 1)
{
cout "不存在第" << i << "个元素" << endl;
return 0;
}
else return L.data[i - 1];
}顺序表是随机存储结构，具有按数据元素的序号随机存取数据的特点，存储数据的时间复杂度与数据元素所在的位置无关，即通过首地址和元素序号可在时间$O(1)$内找到指定的元素。
链表的定义及相关算法
（一）单链表的定义
（1） 线性表链式存储结构的特点是：用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。因此，为了表示每个数据元素$a_i$与其直接后继数据元素$a_{i+1}$之间的逻辑关系，对数据元素$a_i$来说，除了存储其本身的信息之外，还需要存储一个其直接后继的信息（即直接后继的存储位置）。这两部分信息组成数据元素$a_i$的存储映射，称为结点(node)。它包括两个域：其中存储数据元素信息的域称为数据域；存储直接后继存储位置的域称为指针域。指针域中存储的信息称作指针或链。$n$个结点($a_i(1\le i\le n)$的存储映射)链结成一个链表，即为线性表。$$(a_1,a_2,…,a_n)$$
线性表默认从1开始，数组默认从0开始
（2） 链表可以分为单链表、循环链表、二向链表、二叉链表、十字链表、邻接表、邻接多重表等。
其中单链表、循环链表和双向链表用于实现线性表的链式存储结构，其他形式多用于实现树和图等非线性结构。
稀疏矩阵一般采用的压缩存储方法为：三元组和十字链表。
稀疏矩阵的三元组表示顺序存储结构。
（3） 链表增加头结点作用如下：
- 便于首元结点的处理
增加了头结点后，首元结点的地址保存在头结点（即其"前驱"）结点的指针域中，则对链表的一个数据元素的操作与其他数据元素相同，无需进行特殊处理。 - 便于空表和非空表的统一处理
当链表不设头结点时，假设$L$为单链表的头指针，它应该指向首元结点，则当单链表为长度$n$为$0$的空表时，$L$指针为空（判定空表的条件可记为：$L==NULL$ ）
增加头结点后，无论链表是否为空，头指针都是指向头结点的非空指针。如图$2.10(a)$所示的非空单链表，头指针指向头结点。如图$2.10(b)$所示，若为空表，则头结点的指针域为空（判定空表的条件可记为$L->next==NULL$）。
（二）单链表的操作
定义
1 | struct Node |
①在主函数中操作
1 | // 单链表的定义 |
②在自定义函数中操作
注意：传参的时候一定要用Node* &head，如果用Node* head那么传入的指针就变为形参了。
1 |
|
（三）双链表的操作
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
>struct Node
>{
int val;
Node *prev, *next; // 多一个指向前面的点prev
// 两个构造函数，根据传入的参数，用于初始化
Node(): prev(NULL), next(NULL) {}
Node(int _val): val(_val), prev(NULL), next(NULL) {}
>};
>void print(Node* head) // 用于打印输出
>{
// auto:c++11的关键字实现类型推导
// 如果p不为空，也就是p；那么p就接着向后遍历
for(auto p = head; p; p = p->next)
cout << p->val << ' ';
cout << endl;
>}
>int main()
>{
// 双链表一般在实现的时候都会存在两个哨兵，防止越界。
// head 最左边的，tail最右边的
Node *head = new Node(), *tail = new Node();
head->next = tail, tail->prev = head; // 初始化哨兵
print(head);
// 双链表的添加
// 添加一个节点
// 注意顺序问题！！！
// 先添加新的边，再删去旧的边
// 在head - tail 之间插入一个节点
auto a = new Node(1);
a->next = head->next, a->prev = head;
head->next->prev = a, head->next = a;
print(head);
// head - 1 - tail，在head和1之间插入一个节点
auto b = new Node(2);
b->next = head->next, b->prev = head;
head->next->prev = b, head->next = b;
print(head);
// head - 1 - 2 - tail，在2和tail之间插入一个节点
auto c = new Node(3);
c->next = b->next, c->prev = b;
b->next->prev = c, b->next = c;
print(head);
// 双链表的删除操作
// 删除b这个节点
b->prev->next = b->next;
b->next->prev = b->prev;
delete b;
print(head);
return 0;
>}
（四）循环链表的操作
循环链表没有使用到哨兵。
循环链表只需要head和tail都指向同一个节点即可。
其余操作和双链表相同。
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
>{
int val;
Node *prev, *next;
Node(): prev(NULL), next(NULL) {}
Node(int _val): val(_val), prev(NULL), next(NULL) {}
>};
>void print(Node* head)
>{
for(auto p = head->next ; p != head; p = p->next) // 从head->next开始出发，再走回head
cout << p->val << ' ';
cout << endl;
>}
>int main()
>{
// 循环链表没有使用到哨兵。
// 循环链表只需要head和tail都指向同一个节点即可。
Node *head = new Node(), *tail = head; // 需要变动这里，注意head，tail都是指针不是节点。
head->next = tail, tail->prev = head;
// 与双链表进行区分
// head 最左边的，tail最右边的
// Node *head = new Node(), *tail = new Node();
// head->next = tail, tail->prev = head; // 初始化哨兵
print(head);
auto a = new Node(1);
a->next = head->next, a->prev = head;
head->next->prev = a, head->next = a;
print(head);
// head - 1 - tail，在head和1之间插入一个节点
auto b = new Node(2);
b->next = head->next, b->prev = head;
head->next->prev = b, head->next = b;
print(head);
// head - 1 - 2 - tail，在2和tail之间插入一个节点
auto c = new Node(3);
c->next = b->next, c->prev = b;
b->next->prev = c, b->next = c;
print(head);
// 删除b这个节点
b->prev->next = b->next;
b->next->prev = b->prev;
delete b;
print(head);
return 0;
>}
头指针为$L$的带头结点的双循环链表，结点的前驱指针域为prior，后继指针域为next，判断该链表为空的条件是：L->prior == L
（五）静态链表
使用结构体数组来构造静态链表，结构体数组内的每一个元素充当静态链表的结点。每个结点都包含数据域与游标这两部分，数据域用来存放数据、游标用来指示该结点的下一个结点对应的数组下标。
定义：
1 |
|
链表的相关选项
- 静态链表中指针表示的是：下一个元素在数组中的位置。
- 一般来说，线性表的第$i$个数据元素$a_i$的存储位置为：
$$LOC(a_i)=LOC(a_1)+(i-1)\times l$$ - 线性表的顺序储存结构中，数据元素的逻辑位置和物理位置的关系是一致的
总结
三、栈和队列
考纲要求
1．掌握栈和队列的顺序存储方法及链式存储方法。
2．熟悉进栈、出栈、进队、出队的实现方法。
3．栈和对列的简单应用。
4．递归的实现。
考点总结
栈的逻辑结构
定义：栈（stack），是限定仅在表的一端进行插入和删除的特殊的线性表。允许插入、删除的这一端称为栈顶，另一端称为栈底。表中没有元素时称为空栈。
栈被称为后进先出的线性表（$Last In First Out$），简称$FIFO$表，或者被称为先进后出的线性表$First In Last Out$，简称$FILO$表。
堆栈是操作受限的线性结构。
栈与数据存储结构无关
栈的顺序存储结构——顺序栈
（1）顺序栈的存储结构的实现
1 | const int N = 110; |
栈的链式存储结构——链栈
1 | struct Node |
栈的简单应用
【注】所有递归都需要用到栈，除了尾递归
非尾递归：
1 | function fibonacci(n) { |
尾递归：
1 | function fibonacci(n, prev = 0, next = 1) { |
队列的逻辑结构
线性结构
队列的顺序存储结构
注：队列是在队尾$rear$插入，在队头弹出$front$。
循环队列
1 | const int N = 110; |
队列的链式存储结构（带头结点）
1 | struct Node |
循环队列的图示
循环队列入队操作：Q[rear] = e; rear = (rear + 1) % MAXSIZE
循环队列出队操作：front = (front + 1) % MAXSIZE
队满条件：(rear + 1) % MAXSIZE == front
【注】这里点的MAXSIZE是数组的大小，若题目中说了：队列最多能容纳MAXSIZE - 1个元素，为干扰条件，队满判定还是用(rear + 1) % MAXSIZE == front
队空条件：front == rear
队列中一共有多少个元素：(rear - front + MAXSIZE) % MAXSIZE
栈与队列相关示意图
栈
队列
带头结点和不带头结点循环队列
栈与递归问题
一、汉诺塔(Hanoi)问题
【问题描述】
假设有$3$个分别命名为$A$,$B$,和$C$的塔座，在塔座$A$上插有$n$个直径大小各不同，从小到大编号为$1,2,…,n$的圆盘。现要求将塔座$A$上的$n$的圆盘移至塔座$C$上，并按照相同的顺序叠排，圆盘移动时必须遵循一下规则：
（1）每次只能移动一个圆盘；
（2）圆盘可以插在$A$，$B$和$C$中的任一塔座上；
（3）任何时刻都不能将一个较大的圆盘按在较小的圆盘之上。
【题目分析】
假设$n=2$，那么只需要将$A$柱上最上的一块圆盘$disk_1$移动到$B$柱上，再将$A$柱上最下面一块$disk_2$移动到$C$柱上，然后将$B$柱上的一块$disk_1$移动到$C$柱上。
过程为
1 | A -> B |
若$n>2$，那么只需要将$A$柱上$n-1$块圆盘$disk_{(1\sim n-1)}$移动到$B$柱上，再将$A$柱最下面一块$block_n$移动到$C$柱上，然后将$B$柱上的$disk_{(1\sim n-1)}$移动到$C$柱上。
代码
1 | void move(int n, char A, char C) |
二、表达式求值
https://www.jasonqian.com/2022/10/26/AcWing-3302-表达式求值/
四、串
考纲要求
1．掌握串的有关概念，了解顺序存储方法及链式存储方法。
2．了解串的有关操作的实现方法。
3．了解串的模式匹配算法。
4．串的简单应用。
考点总结
串的定义以及相关术语
- 串是由零个或多个任意字符所组成的有限字符序列，记作"$a_1,a_2,…,a_n$"
- '$a_i$‘的含义：’$a_i(1\le i\le n)$'是字符型数据，是构成串的基本单位。
- $a_i$的位置：$i$称为$a_i$在串中的位置或序号。
- 串的长度：$n$称为串的长度；当$n=0$时，称为空串。
- 子串与主串：串中任意连续的字符所组成的子序列称为该串的子串。包含子串的串相对应地称为主串。
- 子串的位置：子串的第一个字符在主串中的序号称为子串在母串中的位置。
- 串相等：称两个串是相等的，是指两个串的长度相等且对应位置上字符都相等。
- 空格串：由一个或多个空格组成的串称为空格串，其长度为空格字符的个数。
- 注意：每个串后面都有一个
'\0'作为串的终结符。 - 存储密度$=\displaystyle\frac{串值所占的存储位}{实际分配的存储位}$。
若字符串"ABCDEFG"采用链式存储，假设每个字符(结点)占1个字节，每个指针占2个字节，则该字符串的存储密度为$\displaystyle \frac{1}{3}$。
也就是$\displaystyle=\frac{字符(结点)占的字节数}{字符(结点)占的字节数+指针占的字节数}$。 - 串的特殊性体现在：数据元素类型是字符型。
substr函数
1 | string str = "abcdefg"; |
五、数组与广义表
考纲要求
1． 掌握数组的顺序存储方法及矩阵的压缩存储方法。
2． 掌握矩阵的转置算法和矩阵的相加算法的实现。
3． 了解广义表在m元多项式中的简单应用。
考点总结
数组以及相关操作的实现
- 数组时由类型相同的数据元素构成的有序集合，每个数据元素称为一个数组元素（简称元素），每个元荤受$n(n\ge 1)$个线性关系的约束，每个元素在$n$个线性关系中的序号称为该元素的下标，并称该元素为$n$维数组，$n$称为该数组的维数($n=1$时称为一维数组，也称为线性表)。
- 数组特点：①数组的数据元素具有相同数据类型；②给定一个确定的下标值就指定了一个具体的数据元素。③数组中的数据元素个数是固定的。一旦定义了一个数组，它的维数和元素数目也就确定了。
- 数组中最常用的两种操作：①存储：给定下标值，存取相应的数据元素；②修改：给定下标值，修改相应的数据元素的值。
- 数组的顺序表示：数组一般都是采用顺序存储结构来表示。一下用二维数组为例，讨论数组的顺序存储方式。
- 以行顺序为主存放：将数组的每一行视为一个行向量元素，第$i+1$个行向量元素存储在第$i$个行向量元素的后面，构成一个行向量元素的线性表。
- 以列顺序为主存放：将数组的每一列视为一个列向量元素，第$i+1$个列向量元素存储在第$i$个列向量元素的后面，构成一个列向量元素的线性表。
- 存储数据时$a_{ij}$的地址计算公式：设二维数组$A[1…m,1…n]$（即$m$行$n$列），其每一个元素$a_{ij}$占用$L$存储单元，$a_{11}$为该数组的第一个元素，设已知$a_{11}$的首地址为$LOC[a_{11}]$（也即存放空间的首地址）。
压缩存储
压缩存储：指为多个值相同的元素只分配一个存储空间，对零元素不分配存储空间。其目的是节省存储空间。
例：对称矩阵，上/下三角矩阵，只存储一半的值即可。
注：稀疏矩阵经过压缩存储后，会失去随机存取的功能。
三对角矩阵
【注】
若为$n$（$n$为大于等于$3$的奇数）对角矩阵，第一排有$\displaystyle \frac{n+1}{2}$个元素。
一个$m$阶的$2n+1,n\in {1,2,3,…}$对角矩阵化为一维数组大小至少为：$m(2n+1)-2\displaystyle \sum_{i=1}^{n}i$
例：
$n$阶$3$对角矩阵压缩为一维至少要：$n\times 3-2\displaystyle\sum_{i=1}^{1}i=3n-2$
$n$阶$5$对角矩阵压缩为一维至少要：$n\times 5-2\displaystyle\sum_{i=1}^{2}i=5n-6$
广义表
概念：
广义表（Lists，又称列表）是线性表的推广。在前面的章节中，我们把线性表定义为$n\ge 0$个元素$a_1,a_2,a_3,…,a_n$的有限序列。线性表的元素仅限于原子项，原子是作为结构上不可分割的成分，它可以是一个数或一个结构，若放松对表元素的这种限制，容许它们具有其自身结构，这样就产生了广义表的概念。
广义表是$n(n\ge 0)$个元素$a_1,a_2,a_3,…,a_n$的有限序列，其中$a_i$或者是原子项，或者是一个广义表。通常记作$LS=（a_1,a_2,a_3,…,a_n)$。$LS$是广义表的名字，$n$为它的长度。若$a_i$是广义表，则称它为$LS$的子表。
表头、表尾的定义：当广义表LS非空时，称第一个元素为LS的表头；称广义表LS中除去表头后其余元素组成的广义表为LS的表尾。例如，广义表(a, (b))的表头是单元素a，表尾是广义表((b))。
通常用圆括号将广义表括起来，用逗号分隔其中的元素。为了区别原子和广义表，书写时用大写字母表示广义表，用小写字母表示原子。若广义表$LS（n\ge 1)$非空，则$a_1$是$LS$的表头，其余元素组成的表$(a_1,a_2,a_3,…,a_n)$称为LS的表尾。
显然广义表是递归定义的，这是因为在定义广义表时又用到了广义表的概念。广义表的例子如下：
- A=（）——A是一个空表，其长度为零。
- B=（e）——表B只有一个原子e，B的长度为1。
- C=（a,(b,c,d))——表C的长度为2，两个元素分别为原子a和子表(b,c,d)。
- D=（A，B，C）——表D的长度为3，三个元素都是广义表。显然，将子表的值代入后，则有D=(( ),(e),(a,(b,c,d)))。
- E=（E）——这是一个递归的表，它的长度为2，E相当于一个无限的广义表E=(a,(a,(a,(a,…)))).
从上述定义和例子可推出广义表的三个重要结论：
- 广义表的元素可以是子表，而子表的元素还可以是子表。由此，广义表是一个多层次的结构，可以用图形象地表示。
- 广义表可为其它表所共享。例如在上述例（4）中，广义表A，B，C为D的子表，则在D中可以不必列出子表的值，而是通过子表的名称来引用。
- 广义表的递归性。
综上所述，广义表不仅是线性表的推广，也是树的推广。由表头、表尾的定义可知：任何一个非空广义表其表头可能是广义表，也可能是广义表，而其表尾必定是广义表。
注意广义表（ ）和( ( ) )不同。前者是长度为0的空表，对其不能做求表头的和表尾的运算；而后者是长度为1的非空表（只不过该表中唯一的一个元素是空表）。对其可进行分解，得到表头和表尾均为空表（ ）。
转自https://zhuanlan.zhihu.com/p/35200103
例题1：
广义表A=(a,b,(c,d),(e,(f,g)))，则Head(Tail(Head(Tail(Tail(A)))))的值为？
tail第一步： (b,(c,d),(e,(f,g)))
tail第二步：((c,d),(e,(f,g)))
head第三步：（c,d）
tail第四步：（d）
head第五步：d
注：(d)是列表，b是元素
例题2：
广义表的深度定义为广义表中括号对的嵌套层数.
广义表A=(a,(c,d),(e,(f,(g,(h,i)))))的深度为？
(e,(f,(g,(h,i))))深度为：1
(f,(g,(h,i)))深度为：2
(g,(h,i))深度为：3
(h,i)深度为：4
h,i深度为：5
故为5
例题3
去除广义表LS=($a_1,a_2,…,a_n$)中的第$1$个元素，由其余元素构成的广义表称为LS的表尾
例题4
广义表L=(a,(b,()))的深度为$3$
例题5
已知广义表A=(x,((a,b),c))，函数head(head(tail(A)))的运算结果是：
tail(A)=(((a,b),c))，注意此处外套一层括号，详情见例题1
head(tail(A))=((a,b),c)
head(head(tail(A)))=(a,b)
例题6
已知广义表G，head(G)与tail(G)的深度分别为4和6，则G的深度为？
假设A=(((a)),((b)))
- tail(A)=(((b)))深度为3，A的深度也是3.原因是tail(A)取的时候外面包了一层皮。
- head(A)=((a))深度为2，A的深度为3.head(A)取的时候外面没有一层皮。
对于此类问题，G的深度就是Max(head(G)的深度 + 1,tail(G)的深度)。
此题答案$\max{(4+1,6)}=6$
例题7
广义表A=(a,(b,d,(e,f,g,h)))，head(tail(A))=?
tail(A)=((b,d,(e,f,g,h)))
head(tail(A))=(b,d,(e,f,g,h))
例题8
例题9
- 广义表的表尾是指除第一个元素之外，其余元素组成的表
- 广义表简称表，是由零个或多个原子或子表组成的有序序列，原子与表的差别仅在于表的长度是指原子（氮元素）是结构上不可再分的，可以是一个数或一个结构；而表带结构，本质就是广义表，因作为广义表的元素故称为子表。为了区分原子和表，一般用大写字母表示表，用小写字母表示原子，一个表的长度是指表中元素的个数，而表的深度是指表展开后所含括号的层数
例题10
设广义表L=((),())，则head(L)=()，tail(L)=(())，L的长度是2，L的深度是2
六、树和二叉树
考纲要求
1． 熟悉树和二叉树的有关定义，掌握二叉树的顺序存储结构和链式存储结构的实现方法。
2．掌握二叉树的建立及二叉树的几种遍历算法，了解树和森林的遍历方法。
3．了解最优二叉树和哈夫曼树的应用。
4．其他简单应用。
考点总结
树的基本概念
-
树是由根节点和若干颗子树构成的。树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的节点，所定义的关系称为父子关系。父子关系在树的节点之间建立了一个层次结构。在这种层次结构中有一个节点具有特殊的地位，这个节点称为该树的根节点，或称为树根。
-
空集合也是树，称为空树。空树中没有节点；
-
孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；
-
节点的度：一个节点含有的子节点的个数称为该节点的度；
-
叶节点或终端节点：度为0的节点称为叶节点；
-
非终端节点或分支节点：度不为0的节点；
-
双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；
-
兄弟节点：具有相同父节点的节点互称为兄弟节点；
-
树的度：一棵树中，最大的节点的度称为树的度；
【例题】
设树$T$的度为$4$，其中度为$1,2,3,4$的结点个数分别为$6,4,1,1$。其中叶子结点个数为？
解：度的总数$-$结点个数$+1$
$(1\times 6+2\times 4+3\times 1+4\times 1) -(6+4+1+1)+1=10$ -
节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
-
树的高度或深度：树中节点的最大层次；
-
节点的祖先：从根到该节点所经分支上的所有节点；
-
子孙：以某节点为根的子树中任一节点都称为该节点的子孙；
-
森林：由棵互不相交的树的集合称为森林。
-
有序树、无序树：如果一棵树中节点的各子树从左到右是有次序的，不能交换的，则称这棵树为有序树；否则称为无序树。
-
节点编号：从1开始将树中的节点依次编号，编号的原则是：从第一层开始往下，每层从左至右依次对节点进行编号。
-
同构：对两棵树而言，若通过对节点重新命名，就可以使这两棵树完全相等（节点对应相等，节点对应关系也相等），则称这两棵树同构。
二叉树
- 二叉树的定义及其主要特征
a. 二叉树的基本形态：空二叉树、单节点二叉树、左子树、右子树
b. 性质：
[1] 在非空二叉树中，第$i$层上至多有$2^{(i-1)}$ 个结点。
[2] 深度为$k$的二叉树至多有$2^k - 1$个结点
[3] 对任何一棵二叉树，若其叶子结点数为$n_0$，度为$2$的结点数为$n_2$，则$n_0 = n_2 + 1$。
[4] $n$个结点的完全二叉树深度为：$\lfloor log_2n\rfloor$ $+ 1$
[5] 二叉树的堆式存储: 结点$p$的左儿子：$2p$，右儿子：$2p +1$
[6] 二叉树的顺序存储：结点$p$的左儿子：$2p+1$，右儿子：$2(p+1)$
c. 三种特殊的二叉树
[1] 满二叉树：一颗深度为$k$且有$2^k-1$个结点的二叉树
[2] 完全二叉树：如果深度为$k$,有$n$个结点的二叉树，当且仅当其每个结点都与深度为k的满二叉树中编号从$1$到$n$的结点一一对应。深度为$n$的完全二叉树结点范围：$[2^{n-1},2^{n}-1]$
【例题1】
一棵完全二叉树中有$n$个结点，若用二叉链表作为该完全二叉树的存储结构，则共有$n+1$个空指针域,$n-1$个非空指针域
【证明】
$n$个结点，有$2n$个指针域，占了$(n-1)$个指针域[因为树根结点不占用指针域，所以要-1]，剩$2n-(n-1)=n+1$个空指针
【例题2】
完全二叉树的叶节点个数为$\lceil \frac{n}{2}\rceil$
设有一棵完全二叉树具有$1001$个结点，则该完全二叉树有$\lceil \frac{1001}{2}\rceil=501$个叶子节点。
【例题3】
[3] 斜树或单支二叉树：所有节点都只有左子树的二叉树统称为左斜树；所有节点都只有右子树的二叉树称为右斜树；左斜树和右斜树统称为斜树，也称为单枝二叉树。 - 二叉树的顺序存储结构和链式存储结构
二叉树有不同的链式存储结构，其中最常用的是二叉链表与三叉链表 - 二叉树的遍历
a. 前序遍历 根左右
b. 中序遍历 左根右
c. 后序遍历 左右根
d. 根据前序 + 中序重建二叉树(AcWing 18) - $n$层满$2$叉树结点总数 对应公式为$(2^n-1)/1$
$n$层满$3$叉树结点总数 对应公式为$(3^n-1)/2$
$n$层满$4$叉树结点总数 对应公式为$(4^n-1)/3$
…
$n$层$k$叉树，对应公式为$(k^n-1)/(k-1)$ - 严格二叉树：每个非叶节点包含非空的左和右子树。 换句话说，每个非叶节点的等级将始终为$2$。具有$n$个叶子的严格二叉树将具有$(2n-1)$个节点。
线索二叉树
二叉树的线索链表利用空指针域存放遍历时得到的前驱或后继结点的指针。
树、森林
- 树的存储结构
a. 只存父节点（应用：并查集）
b. 邻接表存储所有子节点
c. 左儿子右兄弟（本质上就是邻接表） - 森林F与二叉树T的转换（用左儿子右兄弟转换）
a. 原树中叶子节点数 = 转换后的树中有右儿子的节点数 + $1$
b. F的前序遍历就是T的前序遍历
c. F的后序遍历就是T的中序遍历
真题：15.6
树转二叉树：左孩子右兄弟。
- 树和森林的遍历
a. 前序遍历：先遍历根节点，再遍历子树。
b. 后序遍历：先遍历子树，再遍历根节点。 - 森林的一些性质
a. 在$n$个结点的树中有个$n-1$条边，那么对于每棵树，其结点数比边数多$1$。也就是说若森林中有$15$条边，$25$个结点，森林包含的树的个数为$25-15=10$棵树。
b. 有序树$T$转化为森林、二叉树遍历之间的关系树 森林 二叉树 先 先 先 后 中 中
树、森林的转换：https://zhuanlan.zhihu.com/p/134251528
证明题方法
节点计算的方法一般有两种：①数学归纳法，②解方程
例一：证明在非空二叉树中，第$i$层上至多有$2^{(i-1)}$ 个结点。
$$
设k=1时，成立。\\
设k=n时成立，2^{n-1} \\
设k=n+1时，由于n_k\le 2n_{k-1}=2\times 2^{n-1}=2^n，也成立。
$$
例二：证明对任何一棵二叉树，若其叶子结点数为n0，度为2的结点数为n2，则n0 = n2 + 1。
$$
假设n_0为度数为0的点的数量，n_1为度数为1的点的数量，n_2为度数为2的点的数量 \\
从点来考虑n=n_0+n_1+n_2 \\
从边来考虑n-1=0\times n_0+1\times n_1+ 2\times n_2 \\
联立两个等式就可以的到n_0=n_2+1
$$
此结论可以推广至$n$叉树中：
【例】已知一棵度为$3$的树，有$2$个度为$1$的结点，$3$个度为$2$的结点，$4$个度为$3$的结点，则该树中一共有多少个叶子节点？
度为$3$的树$\Longrightarrow$为$3$叉树
设$n_i$为度为$i$的结点，于是$n_1=2，n_2=3，n_4=3$
设一共有$n$个点。
- 从点考虑$n_0+n_1+n_2+n_3=n$
- 从边考虑$0\times n_0+1\times n_1+2\times n_2+3\times n_3=n-1$
解得$n=21,n_0=12$
哈夫曼编码、哈夫曼树
哈夫曼树相关概念
- 节点的路径长度：从根节点沿某条路径到某个节点途中所经历的弧的条数称为该节点的路径长度。
- 数的路径长度：从根节点到每一个叶子节点的路径长度之和。
- 节点的带权路径长度：某节点的路径长度与该节点上的带权的乘积称为该节点的带权路径长度。
- 数的带权路径长度（WPL）：树中所有叶子节点的带权路径长度之和称为树的带权路径长度。
- 哈夫曼树的度只有0或2
哈夫曼树的定义：
设有$n$个叶子节点的二叉树，其第$i$个叶子节点的权值为$w_i(i=1,2,…,n)$，且第$i$个叶子节点的路径长度为$l_i$，则使得$WPL=\displaystyle\sum w_i*l_i$达到最小的二叉树称为"最优二叉树"或者称为"哈夫曼树"。
按Huffman编码压缩正文共需要$\displaystyle\frac{WPL}{字符个数}$个字节。
哈夫曼树特点、试图达到的目的
特点：哈夫曼编码是最优前缀编码。
目的：对于包括$n$个字符的数据文件，分别以它们出现的次数为权值构造哈夫曼树，则利用该树对应的哈夫曼树编码对文件进行编码，能使该文件压缩后对应的二进制文件的长度最短。
编码
有关编码的概念
- 编码对应叶节点左零右一，将左边权值设为$0$，右边权值设为$1$。
- 前缀编码：在一个编码方案中，任何一个编码都不是其他任何编码的前缀。比如$0, 10, 110, 111$是前缀编码，$0, 01, 010, 111$就不是前缀编码，由于$0$是$01,010$的前缀。
- 哈夫曼编码：对于一颗具有$n$个叶子的哈夫曼树，若对树中的每个左分支赋予$0$，右分支赋予$1$，则从根到每个叶子的路径上，各分支的赋值分别构成一个二进制串，该二进制串就是哈夫曼编码。
哈夫曼编码的两个性质
- 哈夫曼编码是前缀编码。
- 哈夫曼编码是最优前缀编码。
哈夫曼树初态和终态
哈夫曼树例题
前序遍历与中序遍历栈的关系
此方法可以求给定一个先序序列，如$a,b,c, d$，求不同的二叉树个数
就可以将问题转换为：对于$n$个元素进栈，出栈序列的个数为多少？
答：$\displaystyle\frac{1}{n+1}C_{2n}^{n}=14$
根据前序/后序/层次遍历，中序遍历求二叉树
方法一：
方法二：
二叉排序树（BST）
具有的性质
- 若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 左、右子树也分别为二叉排序树；
- 当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。
- 中序遍历是有序的，可以左边节点小于当前节点，右边节点大于当前节点；也可以左边节点大于当前节点，右边节点小于当前节点。【下面举个例子】
二叉排序树
二叉排序树的路径
二叉排序树的查找路径：是查找过程中走过的节点序列。
比如$(8,3,6,4)、(8,10,14,13)$就是两条查找路径。
折半查找判定树：是一棵二叉排序树，其中序序列是一个有序序列。
支持操作
- 插入$O(h)$
- 删除$O(h)$
- 查找$O(h)$
二叉排序树题目：https://www.jasonqian.com/2022/11/08/AcWing-3786-二叉排序树/
平衡树——AVL
定义：
- 是二叉排序树
- 每个节点的左子树和右子树的高度差最多为$1$
- 树的高度$log_2{n}$
- 平衡因子：一个结点的左子树的高度减去右子树的高度，可取$-1、0、1$三种值
- 理想平衡树：若二叉树有$h$层，上面$h-1$层都是满的
平衡因子
根结点$45$的平衡因子为$-1$ (左子树高度$2$，右子树高度$3$)
$50$结点的平衡因子为$-2$ (左子树高度$0$，右子树高度$2$)
$40$结点的平衡因子为$0$ (左子树高度$1$，右子树高度$1$)
根据定义这颗二叉排序树中有结点的平衡因子超过1，所以不是一颗AVL树。
若平衡二叉树的高度为$n$，且所有非叶子结点的平衡因子均为$1$，则该平衡二叉树的结点总数为？
平衡二叉树插入
平衡二叉树删除
删除叶节点
删除非叶节点
平衡操作
- 左旋、右旋（旋转完后保证中序遍历不改变）
性质
- 平衡二叉树的结点数的递推公式为$\displaystyle n_0=0, n_1=1, n_2=2,n_{h}=1+n_{h-1}+n_{h-2}$，其中$n_{h}$表示构造此高度的平衡二叉树所需的最小结点数。
表达式树
计算表达式树的时候：运算时要用第二个数栈的值处理第一个数栈的值
特点：所有分叉结点都是运算符，所有叶节点都是数。
表达式树的应用：https://www.jasonqian.com/2022/10/26/AcWing-3302-表达式求值/
表达式树：https://www.jasonqian.com/2022/12/20/AcWing-3765-表达式树/
七、图
考纲要求
1． 熟悉图的有关定义，掌握图的数组存储结构和邻接表存储结构的实现方法。
2．了解图的深度优先遍历算法和广度优先算法。
3．了解最小生成树、拓扑排序、关键路径的有关算法。
4．其他简单应用。
考点分析
图的逻辑结构
图的定义
图$(Graph)$是由定点的非空集合和定点之间的关系（边或者弧的集合）组成的一种非线性结构。
图的有关术语
-
图中的数据元素称为顶点。
-
有向图中有弧。
-
无向图中有边。
定理： $E$是图$G$中所有弧或边的集合，若用$e$表示图中弧的条数或边的条数，也即$e=|E|$，则有：
[1]在有向图中：$0\le e\le n(n-1)$
[2]在无向图中：$0\le e\le \frac{n(n-1)}{2}$
[3]具有$n(n-1)$条边的有向图称为有向完全图
[4]具有$\frac{n(n-1)}{2}$条边的无向图称为完全图。 -
有向图中顶点的度：是该顶点的入度与出度之和。
-
无向图中顶点的度：是与该顶点相关联的边的条数。
-
子图：对于$G_1=(V_1,E_1),G_2=(V_2,E_2)$，若$V_2\in V_1,E_2\in E_1$，则称$G_2$是$G_1$的子图。
-
路径与回路：若图中两顶点是连通的，则从一个顶点到达另一个顶点一次所经历的边或弧称为一条路径；除了起点和终点相同外，路径上的其他顶点均不相同的路径称为一个回路或环。
-
无向图中，若图任意两个顶点都是连通的，则称图为连通图。
-
无向图中的极大连通子图（包括尽可能多的顶点和边）称为连通分量。
-
有向图中，如果任何一对顶点$v$和$w$，从$v$到$w$和从$w$到$v$之间都有路径，则称这个图是强联通图。
【判断】$n$个结点的有向图，若它有$n(n-1)$条边，则它一定是强联通的
（正确），这里不考虑重边，因为在数据结构中进讨论简单图。 -
有向图中的极大强联通子图（包括尽可能多的顶点和边）称为有向图的强联通分量。
-
一个连通无向图的生成树是该图的一个极小连通子图，它包含有该图的素有$n$个顶点的$n-1$条边。
-
边或弧上带权值的图称为网（分为无向网和有向网）。
-
一个无向图的所有生成树中，边上的权值之和最小的生成树称为该图的最小生成树或最小代价生成树。
-
【补充】
-
对于具有$n$个顶点，$e$条边的无向图，它的度的总数为$2e$。
-
回路$\Longleftrightarrow$路径、简单回路$\Longleftrightarrow$简单路径。
-
一个图有$n$个顶点，如果边数小于$n-1$，那么此图必是非连通图。
-
如果图示非连通图，那么最多可以有$C_{n-1}^{2}=\frac{(n-1)(n-2)}{2}$
-
如果图是强联通图，那么最少需要$n$条边，用于形成回路
-
顶点$a$与顶点$b$是连通的：$a$与$b$之间存在路径。
-
若有向图中存在拓扑排序，则该图一定不存在回路。
-
有向图$E_1={<1,2>,<2,3>}$用的尖括号
-
无向图$E_2={(1,2),(2,3)}$用的圆括号
强联通分量及个数
图的遍历
- 图的遍历：有两种遍历算法：深度优先遍历算法$（DFS）$，宽度优先算法$（BFS）$。
- 生成子树与生成森林：对于非连通图而言，可对其某个连通分量求生成树，求的生成子树称为该非连通图的一个生成子树；分别对每个连通分量求一次生成树可得到该非连通图的生成森林。
图的存储结构
图的数组表示法
(1) 邻接矩阵：适用于稠密图，可存有向图、无向图。常用。空间复杂度：$O(n^2)$。无法存重边。
1 | const int N = 10010; |
(2) 邻接表：适用于稀疏图，可存有向图、无向图。常用。空间复杂度：$O(n + m)$。可存重边。
1 | // 定义邻接表 |
add函数：
顶点节点与边表结点
(3) 邻接多重表，适用于稀疏图，可存无向图。不常用。空间复杂度：$O(n + m)$。可存重边。
1 | // 定义邻接多重表，建立无向图的时候用 |
(4) 十字链表，适用于稀疏图，可存有向图。不常用。空间复杂度：$O(n + m)$。无法存重边
(5) 三元组表，适用于稀疏图，可存有向图，无向图。常用于$Bellman-Ford$算法、$Kruskal$算法。空间复杂度：$O(m)$。可存重边。
稀疏矩阵一般采用的压缩存储方法有两种即：三元组表和十字链表
(6) 逆邻接表：邻接表虽然在空间上有很大的优势，但是对于一个有向图，如果需要查找每个顶点的入度就需要遍历整个邻接表，在效率上很低下的。因此才有了逆邻接表的诞生。
邻接表：反映的是顶点出度的情况。
逆邻接表：反映的是顶点的入度情况。
转自：https://blog.csdn.net/ASJBFJSB/article/details/100887364
图的遍历
(1) 深度优先搜索。邻接表存储的时间复杂度：$O(n + m)$。邻接矩阵存储的时间复杂度：$O(n^2)$
(2) 广度优先搜索。邻接表存储的时间复杂度：$O(n + m)$。邻接矩阵存储的时间复杂度：$O(n^2)$
最小生成树(MST)
概念
生成树的代价：设$G=（V，E）$是一个无向连通网，生成树上各边的权值之和称为该生成树的代价。
MST唯一
当带权连通图的任意一个环中所包含的边的权值均不相同时，其 MST 是唯一的
题目
给定一个 $n$ 个点 $m$ 条边的无向图，图中可能存在重边和自环，边权可能为负数。
求最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。
给定一张边带权的无向图 $G=(V, E)$，其中 $V$ 表示图中点的集合，$E$ 表示图中边的集合，$n=|V|$，$m=|E|$。
由 $V$ 中的全部 $n$ 个顶点和 $E$ 中 $n-1$ 条边构成的无向连通子图被称为 $G$ 的一棵生成树，其中边的权值之和最小的生成树被称为无向图 $G$ 的最小生成树。
输入格式
第一行包含两个整数 $n$ 和 $m$。
接下来 $m$ 行，每行包含三个整数 $u,v,w$，表示点 $u$ 和点 $v$ 之间存在一条权值为 $w$ 的边。
输出格式
共一行，若存在最小生成树，则输出一个整数，表示最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。
数据范围
$1 \le n \le 500$,
$1 \le m \le 10^5$,
图中涉及边的边权的绝对值均不超过 $10000$。
输入样例：
4 5
1 2 1
1 3 2
1 4 3
2 3 2
3 4 4
输出样例：
6
朴素版prim算法 $O(n^2)$
prim算法的思想就是：先使得一个顶点在一个集合中，然后从这个顶点出发更新其他点到集合中的最小距离，再从集合中选取一个到集合中最短且没有使用过的顶点来更新其他点到集合中的距离。时间复杂度由于有$n$个点，每个点要更新$n$次，所以是$O(n^2)$的复杂度
类似于dijkstra
$Code$
1 |
|
kruskal算法思想：将所有边按照边权按照从小到大排序，然后遍历所有的边，如果当前边的两个点不在同一个集合中，就将它们加入同一个集合中（使用并查集），最后判断加入的边是否为$n$，进行判断是否为连通图。时间复杂度瓶颈在排序上故为$O(mlog_2m)$
$Code$
1 |
|
最短路算法
给定一个 $n$ 个点 $m$ 条边的有向图，图中可能存在重边和自环，所有边权均为正值。
请你求出 $1$ 号点到 $n$ 号点的最短距离，如果无法从 $1$ 号点走到 $n$ 号点，则输出 $-1$。
输入格式
第一行包含整数 $n$ 和 $m$。
接下来 $m$ 行每行包含三个整数 $x,y,z$，表示存在一条从点 $x$ 到点 $y$ 的有向边，边长为 $z$。
输出格式
输出一个整数，表示 $1$ 号点到 $n$ 号点的最短距离。
如果路径不存在，则输出 $-1$。
数据范围
$1 \le n \le 500$,
$1 \le m \le 10^5$,
图中涉及边长均不超过10000。
输入样例：
3 3
1 2 2
2 3 1
1 3 4
输出样例：
3
参考文献： 最短路笔记
最短路中各个算法的原理
①dijkstra
时间复杂度$O(n^2)$
dijkstra是根据每次找出距离起点最近的一个点，然后用着一个点来更新其他距离，每个点只会被更新一次，用st[]进行判重
可以求有环的图
②dijkstra堆优化
时间复杂度$O(mlogn)$
堆优化的dijkstra就是用c++自带的priority_queue优先队列对每个点i以及起点到i的距离dist进行储存，并按照距离dist进行排序
1 | priority_queue定义: priority_queue<PII, vector<PII>, greater<PII>> heap; |
③bellman_ford
时间复杂度$O(nm)$
1 | 通过循环点的个数n，边的个数m，来更新所有点到起点的距离 |
bellman_ford可以用于求有边数限制的最短路
AcWing 853.有边数限制的最短路
④spfa
时间复杂度平均$O(km)$线性，最坏情况下$O(nm)$
1 | spfa就是对bellman_ford做了一个优化 |
⑤floyd
时间复杂度$O(n^3)$
1 | for(int k = 1; k <= n; k ++ ) // 将其分为[i, k]和[k, j]两段，基于动态规划 |
注意事项
稀疏图和稠密图
1 | 稠密图 稀疏图 |
朴素版dijkstra：$Code$
1 |
|
$floyd$算法$Code$
1 |
|
拓扑排序
给定一个 $n$ 个点 $m$ 条边的有向图，点的编号是 $1$ 到 $n$，图中可能存在重边和自环。
请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出 $-1$。
若一个由图中所有点构成的序列 $A$ 满足：对于图中的每条边 $(x, y)$，$x$ 在 $A$ 中都出现在 $y$ 之前，则称 $A$ 是该图的一个拓扑序列。
输入格式
第一行包含两个整数 $n$ 和 $m$。
接下来 $m$ 行，每行包含两个整数 $x$ 和 $y$，表示存在一条从点 $x$ 到点 $y$ 的有向边 $(x, y)$。
输出格式
共一行，如果存在拓扑序列，则输出任意一个合法的拓扑序列即可。
否则输出 $-1$。
数据范围
$1 \le n,m \le 10^5$
输入样例：
3 3
1 2
2 3
1 3
输出样例：
1 2 3
思想：将每个点的入度数记录下来，再将入度数为$0$的点入队，每次从队列中取出一个点，将它能够到达的所有点的入度数--，如果此时，入度数为$0$，则将它加入队列中。
最后判断是否所有点都入队了，也就是队的长度(队尾tt)是否等于点的个数tt == n - 1。如果是，队列的输出就是拓扑排序。否则就不是。
$Code$：
1 |
|
拓扑排序：每次将入度为零的点取出，用于更新其他点的信息。
逆拓扑排序：每次将出度为零的点取出，用于更新其他点的信息。
关键路径
AOV（Activity On Vertex Network）网
在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系。这样的有向图为顶点表示活动的网，我们称为AOV网
- 无边权值的有向图
- 定义：在现代化管理中，人们常用有向图来描述和分析一项工程的计划和实施过程，一个工程常被分为多个小的子工程，这些子工程被称为活动（Activity)，在有向图中若以顶点表示活动，有向边表示活动之间的先后关系，这样的图简称为AOV网。
AOE（Activity On Edge Network）网
- 有边权值的有向图
- 定义：在现代化管理中，人们常用有向图来描述和分析一项工程的计划和实施过程，一个工程常被分为多个小的子工程，这些子工程被称为活动（Activity)，在带权有向图中若以顶点表示事件，有向边表示活动，边上的权值表示该活动持续的时间，这样的图简称为AOE网。
几个定义：
- 事件(点)最早发生时间ve()：决定了所有从$V_k$开始的活动能够开工的最早时间，要求在这个活动之前的的所有活动都已经完成了。比如说$V_3=4$，因为要等待前面的
打鸡蛋，洗番茄，切番茄都完成以后。（就是取到达这个事件的最大值）
求法：找到到当前点最大的从起始点出发的路径权值和。 - 活动(边)最早发生时间e()：等于当前边指向结点的最早发生时间。比如说
切番茄这个活动的最早开始时间就是$V_2$可以切了这个事件结束后，因此它的$e_3=1$ - 事件(点)最晚发生时间vl()：它是指在不推迟整个工程完成的前提下，该时间最迟必须发生的时间。比如说，结束的时间为$6$，因此到
可以炒了这个事件就必须在$4$这个时刻开始，而它前面的可以切了这个事件就必须在$1$这个时刻开始。（就是取最小值） - 活动(边)最晚发生时间l()：活动弧的终点所表示时间的最迟发生时间与该活动所需时间之差。比如说，
打鸡蛋这个活动要花费两分钟，而可以炒了这个事件的最早发生时间为四分钟，因此打鸡蛋这个活动最晚可以在两分钟后开始（当然打鸡蛋也可以从$1$或$0$分钟开始，但是不是最晚发生时间） - 活动(边)$a_i$的时间余量$d(i)=l(i)-e(i)$，表示在不增加完成整个工程所需总时间的情况下，活动$a_i$可以拖延的时间。比如说
打鸡蛋可以在$[0\sim 2]$之间开始。因此它的时间余量$d(3)=2$。
若一个活动的时间余量为零，则说明该活动必须要如期完成，$d(i)=0$即$l(i)=e(i)$的活动是$a_i$的关键路径。有关键活动组成的路径就是关键路径。 - 正常情况下（网中无回路），AOE网中只有一个入度为0的顶点，称之为源点；有一个出度为0 的顶点，称之为终点。
- 关键路径：从源点到汇点的有向路径可能有多条，所有路径中，具有最大路径长度的路径称为关键路径，而这条关键路径上的活动称为关键活动。
【注】关键路径是最长的路径 - 关键活动：完成整个工程的最短时间就是关键路径的长度，若关键活动不能按时完成，则整个工程的完成时间就会延长。
- 只有关键路径上的活动时间同时减少，才能缩短工期。
八、查找
考纲要求
1．掌握静态查找表的几种查找方法。
2．掌握哈希表的构造方法及其冲突处理方法。
考点总结
查找的基本概念
(1) 平均查找长度 $ASL$ = 每个元素 查找概率 $\times$找到第$i$个元素需要进行的比较次数 的和。
平均查找长度$ASL$和数据元素个数无关的查找方法所使用的数据结构是散列表。
(2) 决策树(判定树)：类似于如下图的一棵树。
顺序查找法
(1) 一般线性表的顺序查找
- 若每个元素查找概率相同，则 $ASL$(成功) $= \frac{(1 + 2 + … + n)}{n} = \frac{(n + 1)}{2}$
- $ASL$(失败)$ = n$或$n+1$，取决于代码写法。
1 | // 若设置哨兵，则ASL失败是n+1 |
- 顺序查找算法的平均时间复杂度为：$O(n)$
(2) 有序表的顺序查找
- 若每个元素查找概率相同，则 $ASL$(成功) $= \frac{(1 + 2 + … + n)}{n} = \frac{(n + 1)}{2}$
- $ASL$(失败) $= \frac{(1 + 2 + … + n + n)}{(n + 1)} = \frac{n}{2} + \frac{n}{(n + 1)}$
(3)折半查找法
- $ASL = log_2(n + 1) - 1$（记住就行了）
- 折半查找对应的判定树是一棵平衡二叉树、二叉排序树，其中序序列是一个有序序列。
- 有$n$个记录的顺序表中进行折半查找，最大比较次数为$\lceil \log_{2}(n) \rceil$，理解如下图(一共$11$个元素)。
- 有$n$个记录的顺序表中进行折半查找，失败的最小比较次数为$\lfloor \log_{2}(n+1) \rfloor$，理解如下图(一共$11$个元素)。
- $Code$
1 | //折半查找算法 |
- 折半查找的决策树
- 具有$12$个关键字的有序表中，对每个关键字的查找概率相同，折半查找算法查找成功的平均查找长度为（），折半查找查找失败的平均查找长度为（）
【注】查找成功分母是元素个数，查找失败分母是元素个数加一
(4)分块查找法
分块查找既能较快的查找，又能适应动态变化。
设共$n$个元素，每块$s$个元素，共$b = \frac{n}{s}$块。块内无序，块间有序。
- 顺序查找平均查找长度：$ASL$(成功) $=\frac{\frac{n}{s}+1}{2}+\frac{s+1}{2}= \frac{s^2 + 2s + n}{2s}$，$s = \sqrt{n}$时取最小值
- 二分查找平均查找长度：$ASL$(成功)$=\lceil log_{2}(\frac{n}{s} + 1)\rceil + \frac{s + 1}{2}$
- 对于长度为$n$的表，如果采用分块查找，每块的最佳长度应该是$\sqrt{n}$
B/B+树
B树及其基本操作、B+树及其基本概念
- B树
[1] $m$阶$B$树，每个节点最多有$m$个孩子。
[2] 每个节点最多有$m-1$个关键字（可以存有的键值对）。
[3] 根节点最少可以只有$1$个关键字。
[4] 非根节点至少有$\frac{m}{2}$或者$\lceil \frac{m}{2} \rceil - 1$个关键字。
[5] 每个节点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它。
[6] 所有叶子节点都位于同一层，或者说根节点到每个叶子节点的长度都相同。
[7] 每个节点都存有索引和数据，也就是对应的$key$和$value$。
[8] 所以，根节点的关键字数量范围：$1 \le k
\le m-1$，非根节点的关键字数量范围：$\frac{m}{2} \le k \le m-1$。
[9] $n$阶$m$个关键字的B树高度范围：$\displaystyle\log_{n}(m+1)\le h\le \log_{\lceil \frac{n}{2}\rceil }(\frac{m+1}{2})+1$ - B+树
[1] B+跟B树不同B+树的非叶子节点不保存关键字记录的指针，只进行数据索引，这样使得B+树每个非叶子节点所能保存的关键字大大增加；
[2] B+树叶子节点保存了父节点的所有关键字记录的指针，所有数据地址必须要到叶子节点才能获取到。所以每次数据查询的次数都一样；
[3] B+树叶子节点的关键字从小到大有序排列，左边结尾数据都会保存右边节点开始数据的指针。 - B/B+树的添加和删除：参考链接：https://www.cnblogs.com/nullzx/p/8729425.html
B树\B+树的比较
- B树的结点中$n$个关键字对应$n+1$棵子树
B+树的结点中$n$个关键字对应$n$棵子树 - $m$阶B树
根节点的关键字数$n\in [1,m-1]$
其他结点的关键字数$n\in [\lceil m/2\rceil-1,m-1]$
最多$m$个分支
$m$阶B+树
根节点的关键字数$n\in [1,m]$
其他结点的关键字数$n\in [\lceil m/2\rceil,m]$ - 在B树中，各结点中包含的关键字是不重复的
在B+树中，叶结点包括全部关键字，非叶结点中出现过的关键字也会出现在叶结点中 - B树的结点中都包含了关键字对应的记录的存储地址
在B+树中，叶结点包含信息，所有非叶结点仅起索引作用，不含该关键字对应记录的存储地址 - B树仅支持随机查找
B+树支持随机查找和顺序查找
散列（Hash）表、字符串模式匹配（KMP）
散列（Hash）表
-
负载因子$=\frac{已有元素数}{数组长度}$，负载因子越低，效率越高。
-
离散函数（哈希函数）构造方法
[1] 数字分析法(数字选择法)：提前知道数据，选取数据中几乎随机的值进行构造。比如手机号前三位是电信商的，中间四位是分地区的，最后四位是随机的，如果给定一串手机号码，可以采取使用手机号码最后四位进行构造离散函数。
[2] 平方取中法：将编码平方后取中间一部分。如：内部编码 内部编码的平方 散列地址 09040101 081723426090201 426 09040202 081725252200804 252 24090403 580347516702409 516 25090404 629538372883216 372 [3] 折叠法：
折叠法适用的情况：散列地址的位数较少，而关键字的位数较多，且难于直接从关键字中找到取值较分散的几位。
[4] 处留余数法（最常用）：假设散列表表长为$m$，选择一个不大于$m$的最大质数$p$,用$p$去除关键字，除后所得余数为散列地址，即$$H(key)=key% p$$ -
解决冲突的方式
[1] 开散列方法（拉链法）：如果一个位置有多个元素，开一个链表，将所有元素都存储下来。
[2] 闭散列方法（开放寻址法）：$H_i=(H(key)+d_i)%m$，其中$H(key)$为散列函数，$i=0,1,2,…,k(k\le m-1)$，$m$表示散列表表长，$d_i$为增量序列。下面介绍几种增量的取法。- 线性探测法：当发生冲突的时候，看下一个位置是否有冲突，如果走到最后一个位置还是有冲突时，从开头继续判断。
- 平方探测法（二次探查法）：$d_i=0^2,1^2,-1^2,2^2,-2^2,…$就这样加上$d_i$进行判断是否位置上发生冲突。缺点是不能探测到散列表上个所有单元，但是至少能探测到一半单元。
- 双散列法：使用两个哈希函数。
- 伪随机序列法：当$d_i=$伪随机数序列时，称为伪随机序列法。
[3] 代码详见$AcWing.840$模拟散列表: https://www.jasonqian.com//2022/11/05/AcWing-840-模拟散列表/
【注】：采用开放定址法处理散列表的冲突时，其平均查找长度高于链接法处理冲突。
-
聚集/二级聚集
- 线性探查法 $d(i) = (d(0) + i * c) % M$。易产生聚集问题。
- 二次探查法。易产生二级聚集问题。二次聚集：
- 随机探查法。易产生二级聚集问题。
- 双散列探查法
-
哈希表的平均查找长度不是表长 (节点个数)n的函数，而是哈希表装填因子alpha的函数，与节点个数无关。
-
装填因子：$\displaystyle \alpha=\frac{n}{m}$ 其中$n$为关键字个数，$m$为表长。
平均查找长度与装填因子$\alpha$直接相关。
加载因子是表示Hsah表中元素的填满的程度。若：加载因子越大，填满的元素越多，好处是空间利用率高了，但冲突的机会加大了。反之，加载因子越小，填满的元素越少，好处是：冲突的机会减小了，但空间浪费多了。 -
同义词：产生冲突现象的两个关键字。
【例题】
KMP
匹配串长度$n$，模式串长度$m$
时间复杂度：预处理部分$O(m)$，匹配过程$O(n)$，总的时间复杂度$O(n+m)$
-
next[i]：前$i$个字母构成的字符串中（下标从$0$开始，也可能从$1$开始），最长的与前缀相等的后缀长度（非平凡，就是前缀长度与后缀长度都不能等于字符串长度）。 -
定义
字符串的前缀：符号串左部的任意子串（或者说是字符串的任意首部）
字符串的后缀：符号串右部的任意子串（或者说是字符串的任意尾部）
举例：比如说有一个长度为5字符串 x =ababc，其中前缀有ε（空串），a，ab，aba，abab，ababc；后缀有ε（空串），c，bc，abc，babc，ababc。 -
应用
手求next数组时：恒有next[1] = 0,next[2] = 1
比如我们的Q串为：abaabc
$Q:ababaa$
- 当遍历到$Q[1]$时，规定
nextval[1] = 0 - 当遍历到$Q[2]$时，由于
next[2] = 1，$Q[2]=b \not= Q[1]=a$，故nextval[2] = next[2] = 1 - 当遍历到$Q[3]$时，由于
next[3] = 1，$Q[3]=a=Q[1]=a$，$Q[1]$跳转到$0$，故nextval[3] = 0 - 当遍历到$Q[4]$时，由于
next[4] = 2，$Q[4]=b =Q[2]=b$，$Q[2]$跳转到$Q[1]$，$Q[4]=b \not= Q[1]=a$，故nextval[4] = 1 - 当遍历到$Q[5]$时，由于
next[5] = 3，$Q[5]=a=Q[3]=a$，$Q[3]$跳转到$Q[1]$，$Q[5]=a=Q[1]=a$，$Q[1]$跳转到$0$，故nextval[5] = 0 - 遍历到$Q[6]$时，由于
next[6] = 4，$Q[6]=a\not= Q[4]=b$，故nextval[6] = next[6] = 4
故nextval[] = {0, 1, 0, 1, 0, 4}
参考「辰佬」的文章
原文链接：https://blog.csdn.net/qq_52156445/article/details/130274070
九、内部排序和外部排序
考纲要求
1． 掌握内部排序和外部排序的概念。
2． 熟悉插入排序、选择排序及常用的几种排序方法。
能分析几种常用的排序算法的时间复杂度与空间复杂度。
考点分析
排序的基本概念
内排序和外排序
内排序：数据量不是很大，可以存储在内存当中，就是内排序。
外排序：数据量很大，内存存储不下来，需要借助于外存（硬盘）来进行存储，就是外排序。
运行效率：①时间复杂度，②空间复杂度，③稳定性。
其中时间复杂度包括：最好情况，平均情况，最坏情况。
时间复杂度包括：①比较次数，②移动次数。
算法的稳定性
排序过程不改变关键字相同记录之间的相对次序，则称该排序是稳定的。
定义：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，A1=A2，且A1在A2之前，而在排序后的序列中，A1仍在A2之前，则称这种排序算法是稳定的；否则称为不稳定的
一般情况下基于相邻关键字比较的排序算法是稳定的。
假设如下情况：
存在数组：$2,1_1,1_2,3$，排序后：$1_1,1_2,2,3$，则称为稳定的。如果排序后：$1_2,1_1,2,3$则称不稳定的。
排序的一些性质
- 茶(插入)几(基数)稳定冒(冒泡)鬼(归并)
- 对于任意序列进行基于比较的排序，求至少的比较次数应考虑最坏情况。对任意$n$个关键字排序的比较次数至少为$\displaystyle\lceil\log_{2}(n!) \rceil$
各种排序趟数的结果
直接插入排序
算法思路：将待排序的序列分成两个序列，使得前面一个有序，每一次从后面一个序列中拿第一个元素$t$，在第前面的元素中从大到小与$t$进行比较，每次比较时，如果当前元素$>t$，就将当前元素的值赋给它之后的元素，直到当前元素$<t$，最后将$t$的值赋值给当前元素。（从大到小的原因是为了移动排序后的元素方便，更高效）。
【注】直接插入排序前面的序列一定是有序的
时间复杂度
[1] 最好情况：$O(n-1)=O(n)$
[2] 平均情况：$O(n^2)$
[3] 最坏情况：$O(\frac{n(n-1)}{2})=O(n^2)$
辅助空间复杂度：$O(1)$
稳定
【例题】
若序列的原始状态为$(1,2,3,4,5,10,6,7,8,9)$，要使得排序过程中元素比较次数最少，应采用（A）
A. 插入排序
B. 选择排序
C. 希尔排序
D. 冒泡排序
解析：插入排序和序列初态无关，直接排除。初始序列基本有序时，插入排序比较次数较少。本题中插入排序仅需要比较n - 1 + 4次，而希尔、冒泡远大于
$Code$
1 | // 数组从1开始，0位置作为哨兵单元 |
样例：
折半插入排序
算法思路：对于直接插入排序，计算每一次插入的位置可以进行优化，因为前面序列是有序的，因此可以使用二分来确定需要插入的位置在哪。优化比较次数，不能优化移动次数，因此不会对时间复杂度产生重大影响，头头在移动次数。
时间复杂度
[1] 最好情况：$O(n)$
[2] 平均情况：$O(n^2)$
[3] 最坏情况：$O(n^2)$
辅助空间复杂度：$O(1)$
稳定
$Code$
1 | // 数组从1开始，0位置作为哨兵单元 |
样例：
1 | 2 7 6 1 4 3 5 |
冒泡排序（bubble sort）
算法思想：一共比较$n-1$次，每次比较区间为$[0,n-1]$，$[1,n-1]$，…，$[n-2,n-1]$。每次比较时相邻两个元素，从后往前遍历或者从前往后遍历，相邻的两个数如果不满足要求，就进行交换。
下面代码是从前往后。
自底向上就是从后往前遍历。
冒泡排序：排序趟数与序列的初始状态有关的排序。
时间复杂度
a. 最好情况：$O(n)$
b. 平均情况：$O(n^2)$
c. 最坏情况：$O(n^2)$
空间复杂度：$O(1)$
稳定
$Code$
1 | // q[],下标从0开始 |
样例：
简单(直接)选择排序
算法思路：一开始往后面遍历，用$k$记录当前排序区间$[i,n-1]$中的最小元素的下标，遍历完区间$[i,n-1]$后，交换$q[i]、q[k]$的值，这样算一次排序。需要从第一个元素一直重复以上排序直到最后一个元素下标$-1$（因为遍历到最后一个元素前一个位置的时候一定是有序的）。
直接选择排序在每一趟都能选出一个元素放到其最终位置。
时间复杂度
a. 最好情况：$O(n^2)$
b. 平均情况：$O(n^2)$
c. 最坏情况：$O(n^2)$
空间复杂度：$O(1)$
不稳定
$Code$
1 | // q[],下标从0开始 |
样例：
希尔排序（shell sort）
算法思想：首先定义一个公差将数组内的元素进行分组，对每组进行插入排序，紧接着减少公差，再对分好组的每一组元素进行插入排序。最后当公差为$1$的时候，此时再进行插入排序整个序列就是有序的了。最后一个增量必须是$1$。
公差的减少是自定义的，比如说第一次是$5$，第二次可以是$2，3，4$都可以。
比如公比$n=3$，对$a_1,a_2,a_3,a_4,a_5,a_6,a_7$进行一次希尔排序，就是分别对$(a_1,a_4,a_7)$、$(a_2,a_5)$、$(a_3,a_6)$进行插入排序。
时间复杂度
$O(n^{\frac{3}{2}})$
空间复杂度
$O(1)$
不稳定
$Code$
1 | // q[],下标从0开始 |
样例：
1 | 2 7 6 1 4 3 5 |
快速排序
算法思想：
样例：
对$49,38,68,97,76,13,27$进行排序。
第一次排序过程：
选择$q[0]=49$为枢轴，缓冲值为$q[0]$。
49 38 65 97 76 13 27
第一次交换：在区间$[0,6]$中从右往左$\longleftarrow$进行遍历，找到第一个小于或者等于$49$的值，也就是$q[6]=27$，将$q[6]$的值赋给缓冲值$q[0]$，q[0]=q[6]，此时缓冲值变为$q[6]$。
27 38 65 97 76 13 __
第二次交换：在区间$[0,5]$中从左往右$\longrightarrow$进行遍历，找到第一个大于$49$的值，也就是$q[2]=65$，将$q[2]$的值赋给缓冲区$q[6]$，q[6]=q[2]，此时缓冲区变为$q[2]$。
27 38 __ 97 76 13 65
第三次交换：在区间$[3,5]$中从右往左$\longleftarrow$进行遍历，找到第一个小于或者等于$49$的值，也就是$q[5]=13$，将$q[5]$的值赋值给缓冲区$q[2]$，q[2]=q[5]，此时缓冲区变为$q[5]$。
27 38 13 97 76 __ 65
第四次交换：在区间$[3,4]$中从左往右$\longrightarrow$进行遍历，找到第一个大于$49$的值，也就是$q[3]=97$，将$q[3]$的值赋给缓冲区$q[5]$，q[5]=q[3]，此时缓冲区变为$q[3]$。
由于$l=r$，此时不在进行交换，而是将枢轴的值赋值给缓冲区，也就是q[3]=49。
27 38 13 __ 76 97 65
$\Longrightarrow$ 27 38 13 49 76 97 65
时间复杂度
a. 最好情况：$O(nlogn)$
b. 平均情况：$O(nlogn)$
c. 最坏情况：$O(n^2)$
空间复杂度：平均：$O(logn)$，最坏情况下：$O(n)$
不稳定
性质：
- 在第$i$趟，至少有$i$个元素在正确的位置上（左边的元素都$\le$它，右边的元素都$\ge$它）。用于判断快速排序第几趟结果是否正确。
- 在快速排序中，序列约接近无序，效率越高，若序列约接近有序，效率越低。
- 当表本身已经有序或者逆序时，速度最慢。
- 当每次枢轴都把表等分为长度相近的两个子表时，速度是最快的
例：$A={21,25,5,17,9,23,90}、B={21,9,17,30,25,23,5}、C={25,23,30,17,21,5,9}$中$A$速度最快。
$A$第一次：9 17 5 21 25 23 90
$B$第一次：5 9 17 21 25 23 30 (两个子表有序，因此速度慢)
$C$第一次：9 23 5 17 21 25 30 （长度不相近） - 快速排序过程构成一个递归树，递归深度即递归树的高度。枢轴值每次都将子表等分时，递归树的高为$log_{2}n$；枢轴值每次都是子表的最大值或最小值时，递归树退化为单链表，树高为$n$。
$Code$
1 | // 左边都小于枢轴记录的关键字 |
堆排序
时间复杂度
a. 最好情况：O(nlogn)
b. 平均情况：O(nlogn)
c. 最坏情况：O(nlogn)
空间复杂度
$O(1)$
不稳定
筛选法建堆的最坏情况：$C(n)\le O(n)$
插入法建堆的最坏情况：$C(n)\le O(n\log_{2}n)$
综上：堆排序最坏复杂度为$O(n\log_{2}(n))$。
堆分为：小根堆、大根堆
完全二叉树，高度$log_2n$，这是时间复杂度的关键
是一个递归定义的数据结构
大根堆：满足某个根节点的值大于左右两个结点的值
存储：顺序存储比链式存储好
- 用下标从$1$开始的数组来存储。
- 由于某个结点编号为$x$，那么它的左儿子结点为$2x$，右儿子为$2x+1$
- 某个结点$y$的父节点为$y/2$向下取整
筛选法建堆：
对关键字序列$（12，13，11，18，60，15，7，18，25，100）$，用筛选法建堆，则开始节点的值必须为（C）
A.100 B.12 C.60 D.15
【解答】：$\displaystyle \lfloor \frac{9}{2} \rfloor=4$
对${15,9,7,8,20,-1,7,4}$用堆排序的筛选方式创建初始小根堆为：${-1,4,7,8,20,15,7,9}$
【解答】
1 | int size; |
样例：
1 | 2 7 6 1 4 3 5 |
堆的插入删除操作
二路归并排序（merge sort）
算法思想：平均分成两份，通过递归，从而从$n^2$层开始排序，递归至最高层
对于$N$个元素进行$k$路归并排序时，排序的趟数$m$满足$k^{m}=N$，所以$m=\lceil log_{k}N \rceil$。
若是二路归并，$m=\lceil log_{2}N \rceil$
占用辅助空间最多
时间复杂度
a. 最好情况：$O(nlogn)$
b. 平均情况：$O(nlogn)$
c. 最坏情况：$O(nlogn)$
空间复杂度：$O(n)$
稳定
【注】
$Code$
1 | int q[N], temp[N]; // temp是辅助数组，用来存储排序后的数据 |
样例：
1 | 2 7 6 1 4 3 5 |
桶排序（计数排序）
时间复杂度
a. 最好情况：$O(n + m)$
b. 平均情况：$O(n + m)$
c. 最坏情况：$O(n + m)$
空间复杂度
$O(n + m)$
稳定
思想：桶排序不是基于比较的排序。
对于每一个$a_i$，直接计算出它在数组中排好序的位置。
这个位置就是：小于$a_i$的元素个数$+$等于$a_i$且在$a_i$左边的元素个数。
如何计算呢？
开$m$个桶，将每个元素出现的次数相加
c[i]：表示$i$出现的次数
s[i]：表示小于等于$i$的数有多少个，也就是c[i]的前缀和。
这样当需要查询某一个数应该在哪个位置直接用s[i - 1]即可。
瓶颈在数值很大，若最大数为$1e^{10}$，那么就需要开$1e^{10}$个数组作为桶
如果有相等的元素，规定相对顺序不发生变化，因此这个排序是稳定的 ，在摆放的时候从后往前摆放
$Code$
1 | int q[N], s[N], w[N]; // q存放数据，s前缀和数组，w临时数组 |
基数排序(基于桶排序)
时间复杂度
a. 最好情况：$O(d(n + r))$，一趟分配$O(n)$，一趟收集$O®$，总共$d$趟分配、收集。
b. 平均情况：$O(d(n + r))$
c. 最坏情况：$O(d(n + r))$
空间复杂度
$O(n + r)$
稳定
思想：
将每个数看作$r$进制的数，转化完后将每一位数开拆，化为有序数组，进行多关键字排序
【注】：
如果没有特殊说明的话，认为是10进制。
基数排序不是基于"比较"的排序算法
擅长处理$\begin{cases}数据元素的关键字可以方便地拆分为d组，且d较小 \\ 每组关键字的取值范围不大，即r较小 \\ 数据元素个数n较大 \end{cases}$
$Code$
1 | int q[N], s[N], w[N]; // q存放数据，s前缀和数组，w临时数组 |
外排优化内容
外部排序
定义：在排序过程中，如果需要在内、外存之间交换数据就称为外部排序。
(1) 置换选择排序
(2) 归并排序
- 胜者树
- 败者树
- huffman树
由于外部排序的瓶颈在于读写速度，也就是$I/O$，因此要想办法减少读写次数，由于外部排序一共排$log_{k}{m}$轮，每一轮读写为整个数组的长度，为了使读写次数减少，就可以增加$k$，或者减少$m$。
