---

数据结构

前言

本数据结构笔记配合王道视频食用，效果更佳。若有条件，可彩印成册，涂写勾画，记出自己的笔记，内容若有错误，请见谅。

本数据结构笔记内容绝大部分来自王道数据结构视频，部分来自《大话数据结构》，希望能够帮助到在考研路上的诸位。

$一路生花吧！$

甲辰年三月廿一

第一章 绪论

1.1 基本概念

数据是信息的载体，是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。

数据元素是数据的基本单位

一个数据元素可由若干数据项组成，数据项是构成数据元素的不可分割的最小单位

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

数据对象是具有相同性质的数据元素的集合，是数据的一个子集。

数据类型 ：一个值的集合和定义在集合上的一组操作的总称

1. 原子类型 ：值不可再分
2. 结构类型：值可以再分
3. 抽象数据类型 ： 抽象数据组织及与之相关的操作

1.2 数据结构三要素

逻辑结构：数据元素之间的逻辑关系,与存储无关,独立于计算机（一个算法的设计）

1. 线性结构：一对一

   除了第一个元素，所有元素都有唯一前驱； 除了最后一个元素，所有元素都有唯一后继

2. 树形结构： 一对多

3. 网状/图状：多对多

4. 集合： 同属一个集合

存储结构：数据结构在计算机中的表示，又称映像/物理结构 （一个算法的实现）

1. 顺序存储：把逻辑上相邻的元素存储在物理位置 上也相邻的存储单元中，元素之间的关系由存储 单元的邻接关系来体现

   优点： 随机存取,元素占用最少存储空间

   缺点： 只能使用相邻的一整块存储单元,产生较多的外部碎片

2. 链式存储：逻辑上相邻的元素在物理位置上可以 不相邻，借助指示元素存储地址的指针来表示元 素之间的逻辑关系

   优点: 不会出现碎片现象

   缺点: 存储指针占用额外的存储空间; 只能顺序存取

3. 索引存储：建立附加 的索引表。索引表中的每项称为索引项，索引项 的一般形式是（关键字，地址）

   优点: 检索速度快

   缺点: 占用较多存储空间; 增加和删除数据要修改索引表,花费较多时间

4. 散列存储：根据元素的关键字直接计算出该元素 的存储地址，又称哈希（Hash）存储

   优点: 检索,增加和删除结点都很快

   缺点: 若散列函数不好,出现元素存储单元冲突,会增加时间和空间的开销

数据的运算

运算的定义是针对逻辑结构的， 指出运算的功能

运算的实现是针对存储结构的，指出运算的具体操作步骤。

易错点

1. 属于逻辑结构 有序表
2. 循环队列是用顺序表表示的队列,是数据结构,不是抽象数据结构
3. 不同结点的存储空间可以不连续,但结点内的存储空间必须连续
4. 两种不同的数据结构,逻辑结构和物理结构可以完全相同,但数据的运算不同
   

1.3 算法的概念

算法 ：对特定问题求解步骤的描述，是指令的有限序列，其中每条指令表示一个或多个操作

算法的特性

1. 有穷性：一个算法必须总在执行有穷步之后结束，且每一步都可在有穷时间内完成

   算法是有穷的，程序是无穷的。

2. 确定性：算法中每条指令必须有确切的含义，对于相同的输入只能得出相同的输出

3. 可行性 ：算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现

4. 输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合

5. 输出：一个算法有一个或多个输出，这些输出是与输入有着某种特定关系的量

对于一个好的算法应满足以下特点

1. 正确性
2. 可读性
3. 健壮性： 输入非法数据时，算法能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果
4. 高效率与低存储量需求 （时间复杂度低、空间复杂度低）

1.4 算法效率的度量

算法的时间复杂度

定义：事前预估算法时间开销T(n)与问题规模n的关系

衡量算法随着问题规模增大,算法执行时间增长的快慢

同一个算法,实现的语言的级别越高级,执行效率越低

利用大O法求时间复杂度

大O法：

1.用常数1取代运行时间中的所有加法常数。$O(3)=O(1)$

2.在修改后的运行次数函数中,只保留最高阶项。$O(4n+8)=O(n)$

3.如果最高阶项存在且不是1，则去除与这个项相乘的常数。得到的结果就是大О阶。 $O(3n^2+2)=O(n^2)$

对于大段程序来说，只要找到次幂最大的那段程序即可。找for嵌套或者是while类循环

顺序执行的代码只会影响常数项，可以忽略。

只需挑循环中的一个基本操作分析它的执行次数与n的关系即可

如果有多层嵌套循环，只需关注最深层循环循环了几次

常对幂指阶

算法的空间复杂度

衡量算法随着问题规模增大,算法所需空间增长的快慢

---

第二章 线性表

2.1 线性表的定义和基本操作

线性表的定义

线性表是具有相同数据类型的n（n≥0）个数据元素的有限序列，其中n为表长，当n = 0时线 性表是一个空表。若用L命名线性表，则其一般表示为 L = (a1, a2, … , ai , ai+1, … , an)
$a_i$是线性表中的“第i个”元素线性表中的位序

$a_1$是表头元素；$a_n$是表尾元素

除第一个元素外，每个元素有且仅有一个直接前驱；

除最后一个元素外，每个元素有且仅 有一个直接后继

线性表的基本操作

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个位置的元素的值。

& 表示C++中的引用,若传入指针型变量且在函数体内要进行改变,要用到指针变量的引用(C中用指针的指针也可以)

2.2 线性表的顺序表示

顺序表的定义

顺序表——用顺序存储的方式实现线性表

顺序存储：一维数组 把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关 系由存储单元的邻接关系来体现

线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。

顺序表的实现 ：静态分配、动态分配

typedef struct 
{
    int data[maxsize];//定义数组最大长度
    int length;		  //定义顺序表长度
}List;

动态分布语句：

 L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize)
//malloc函数申请一片连续的存储空间
//free函数释放原来的内存空间

动态分配不是链式存储,同样属于顺序存储结构,物理结构没有变化：随机存取方式。只是分配的空间大小可以在运行时决定

特点: 随机访问,存储密度高,插入和删除需要移动大量元素

顺序表的操作

1. 插入操作 平均时间复杂度O(n)
2. 删除操作 平均时间复杂度O(n)

3. 查找操作：按值查找、按位查找

2.3 线性表的链式表示

单链表

逻辑上连续，但物理上不连续。

链表有两部分，一个用来存数，一个用来存地址，我们称为数据域与指针域。

我们把链表第一个结点的存储位置叫做头指针。

为了方便操作，我们会在第一个结点前设一个结点，称为头结点，不存储任何信息。

头指针和头结点的区别：

（1）不管带不带头结点,头指针始终指向链表的第一个结点

（2）头结点是带头结点的链表中的第一个结点,通常不存储信息

引入头结点的优点： 无论链表是否为空,头指针都指向头结点的非空指针,空表和非空表处理一致

因此，对于一个链表，简化形式如下：

若带有头结点，则为：

判断单链表是否为空

头结点指向的是否为空，即L->next ==NULL;

单链表的操作

建立单链表

typedef struct 
{
    int data;
    struct LNode *next;//递归的思想
}LNode,*LinkList;

核心： 初始化操作、指定结点的后插操作

（1）头插法，链表的逆置

（2）尾插法，注意设置一个指向表尾结点的指针

插入结点操作

（1）按位序插入（带头结点）

（2）按为序插入（不带头结点）

（3）指定结点的前插操作: 先找到前一个结点,时间复杂度为O(n)

（4） 将前插操作转化为后插操作,然后交换两个结点的数据,时间复杂度为O(1)

//插入元素
void InsertList(LinkList *L,int i,int e)
{
    LinkList temp = L;
    int j = 1;
    while(j<i)//找到第i个的位置
    {
        temp = temp->next;
        j++;
    }
    LinkList p = (LinkList)malloc(sizeof(LNode));//申请内存空间
    //三者的顺序不能换
    p->data = e;
    p->next = temp->next;
    temp->next = p;
}

删除结点操作

（1）按位序删除（带头结点）

（2）指定结点的删除：先找到前驱节点,再删除结点,O(n)

//删除元素
void DeleteList(LinkList *L,int i)
{
    LinkList temp = L;
    int j = 1;
    while(j<i)//找到位置
    {
        temp = temp->next;
        j++;
    }
    LinkList p = temp->next;
    temp->next = p->next;//不可以是p->next->next
    free(p);
}

查找结点操作（都是$O(n)$）

（1）按位查找

（2）按值查找

双链表

删除很重要，不能把顺序搞反

循环链表

（1）循环单链表： 表尾结点的next指针指向头结点

对单链表在表头和表尾操作时: 不设头指针仅设尾指针,效率更高

可以从任意一个结点开始遍历整个链表

（2）循环双链表： 表头结点的prior指向表尾结点，表尾结点的next指向头结点

对于空的循环链表：

尾指针：rearA

rearA->next 指向的是头结点

合并两个循环链表

①p = rearA->next; //保存A的头结点

②rearA->next = rearB->next->next;//将B的第一个节点，注意不是头结点，赋值给A的next，链接起来

③rearB->next = p;//B尾指针的next指向A的头结点，实现一个循环

静态链表

用数组描述链式存储结构,也有数据域和指针域.指针是结点的相对地址(数组下标),又称游标

插入和删除只需要修改指针,不需要移动元素

顺序表和链表的比较

1. 逻辑结构 都属于线性表，都是线性结构

2. 存储结构 顺序表：顺序存储 链表：链式存储

3. 基本操作–初始化

   

4. 基本操作–增删

   

5. 基本操作–查

   

6. 如何选择

   （1）基于存储的考虑 ：难以估计长度和存储规模时用链表,但链表的存储密度较低

   （2）基于运算的考虑：经常做按序号访问数据元素用顺序表

   （3）基于环境的考虑：较稳定选顺序表,动态性较强选链表

---

第三章 栈、队列和数组

3.1 栈

定义

只允许在一端进行插入或删除操作的线性表 先进后出(First In Last Out)

特点：先进后出，后进先出

栈顶、栈底、空栈

基本操作

InitStack(&S)：初始化栈。构造一个空栈 S，分配内存空间。

DestroyStack(&S)：销毁栈。销毁并释放栈 S 所占用的内存空间。

Push(&S,x)：进栈，若栈S未满，则将x加入使之成为新栈顶。

Pop(&S,&x)：出栈，若栈S非空，则弹出栈顶元素，并用x返回。

GetTop(S, &x)：读栈顶元素。若栈 S 非空，则用 x 返回栈顶元素

栈的顺序存储结构

实现

1. 栈顶指针: S.top

   栈顶元素: S.data[S.top]

2. 进栈: 指针先加1,再送值到栈顶元素

3. 出栈: 先取栈顶元素值,再将栈顶指针减1

#define maxsize 20

//顺序栈的定义
typedef struct
{
    int data[maxsize];//最大元素个数
    int top;//top游标
}Stack;

共享栈

1. 定义: 将两个栈的栈底设置在共享空间的两端,两个栈顶向中间延伸
2. 判空: top0=-1 top1=MaxSize
3. 判满: top1-top0=1
4. 进栈: top0先加1再赋值,top1先减1再赋值,出栈相反

#define maxsize 20

typedef struct 
{
    int data[maxsize];
    int top1;//栈1的top指针
    int top2;//栈2的top指针
}Stack;

栈的链式存储结构

栈空： top = NULL;

优点: 便于多个栈共享储存空间,提高其效率,不会栈满上溢

特点：所有操作在表头进行,通常没有头结点,将头指针作为栈顶指针,便于结点插入/删除

//链栈结构
typedef struct
{
	int data;//数据域
	struct Node *next;//指针域
}Node;

3.2 队列

定义

队列（Queue）是只允许 在一端进行插入（入队），在另一端删除（出队） 的线性表

队头、队尾、空队列

特点：先进先出

队列的基本操作

InitQueue(&Q)：初始化队列，构造一个空队列Q。

DestroyQueue(&Q)：销毁队列。销毁并释放队列Q所占用的内存空间。

EnQueue(&Q,x)：入队，若队列Q未满，将x加入，使之成为新的队尾。

DeQueue(&Q,&x)：出队，若队列Q非空，删除队头元素，并用x返回。

GetHead(Q,&x)：读队头元素，若队列Q非空，则将队头元素赋值给x

队列的顺序存储结构

#define MAX 100
typedef struct
{
    int data[MAX];
    int front;
    int rear;
}SqQueue

实现

1. 两个指针: front指示队头元素,rear指向队尾元素下一个位置

2. 初始状态(队空):

   Q.front== Q.rear==0

3. 进队: 先送值到队尾元素,再将队尾指针加1

4. 出队: 先取队头元素值,再将队头指针加1

5. 存在假溢出(用循环队列解决）

循环队列

队满的条件为：(rear + 1)%maxsize == front;

队空的条件为:Q.front== Q.rear==0

计算队列长度公式为:(rear- front +maxsize)%maxsize

队首指针进1：Q.front = (Q.front + 1)%maxsize

队尾指针进1：Q.rear = (Q.rear + 1)%maxsize

队列的链式存储结构

适合数据元素变动较大的情形,不存在队满溢出,多个队列不存在存储分配不合理

typedef struct
{
    int data;
    struct QNode *next;
}QNode;

typedef struct
{
    QNode *front;//头指针
    QNode *rear;//尾指针
}SqQueue;

双端队列

允许从两端插入、两端删除的线性表

输入受限的双端队列：只允许从一端插入、两端删除的线性表

输出受限的双端队列：只允许从两端插入、一端删除的线性表

3.3 栈和队列的应用

3.3.1 栈在括号匹配中的应用

最后出现的左括号最先被匹配

1. 设置一个空栈,顺序读入括号

2. 若为 ) ,与栈顶 ( 配对出栈或者不合法

3. 若为 ( ,作为新的更急迫的期待压入栈中

4. 算法结束,栈为空,否则括号序列不匹

3.3.2 栈在表达式求值中的应用

中缀转后缀

中缀转后缀的手算方法

① 确定中缀表达式中各个运算符的运算顺序

② 选择下一个运算符，按照==「左操作数 右操作数 运算符」==的方式组合成一个新的操作数

③ 如果还有运算符没被处理，就继续 ②

“左优先”原则：只要左边的运算符能先计算，就优先算左边的 可保证运算顺序唯一

后缀表达式的手算方法： 从左往右扫描，每遇到一个运算符，就让运算符前面最近的两个操作数执行对应运算， 合体为一个操作数

中缀转后缀的机算方法

初始化一个栈，用于保存暂时还不能确定运算顺序的运算符。

从左到右处理各个元素，直到末尾。可能遇到三种情况：

① 遇到操作数。直接加入后缀表达式。

② 遇到界限符。 遇到“(”直接入栈；遇到“)”则依次弹出栈内运算符并加入后缀表达式，直到 弹出“(”为止。注意：“(”不加入后缀表达式。

③ 遇到运算符。 依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式， 若碰到“(” 或栈空则停止。之后再把当前运算符入栈

后缀表达式计算（算法实现）

用栈实现后缀表达式的计算：

**规则:**从左到右遍历表达式的每个数字和符号，遇到是数字就进栈，遇到是符号，就将处于栈顶两个数字出栈，进行运算，运算结果进栈，一直到最终获得结果。

例，9 3 1 - 3 * + 10 2 / +

①初始化一个空栈。

②后缀表达式前三个都是数字，所以都进栈。

③接下来是“-”，所以将栈中的1出栈作为减数，3出栈作为被减数，并运算3-1，得到2，再将2进栈,如左图所示。
④接着是数字3进栈,如右图所示。

⑤后面是“*”，也就意味着栈中3和⒉出栈，2与3相乘，得到6，并将6进栈，如左图所示。
⑥下面是“+”，所以栈中6和9出栈，9与6相加，得到15，将15进栈，如图右图所示。

⑦接着是10与2两数字进栈，如左图所示。
⑧接下来是符号“/”，因此，栈顶的2与10出栈，10与2相除，得到5，将5进栈，如右图所示。

⑨最后一个是符号“+”，所以15与5出栈并相加，得到20，将20进栈，如左图所示。
⑩结果是20出栈，栈变为空，如右图所示。

中缀表达式计算（栈实现） 中缀转后缀+后缀表达式求值

**规则:**从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后缀表达式的一部分;若是符号，则判断其与栈顶符号的优先级，是右括号或优先级低于栈顶符号（乘除优先加减）则栈顶元素依次出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式为止。

①初始化一个空栈

②第一个字符是数字9，输出9，后面是符号“+”，进栈。

③第三个字符是“(”，依然是符号，因其只是左括号，还未配对，故进栈。如左图

④第四个字符是数字3，输出，总表达式为9 3，接着是“一”，进栈。如右图

⑤接下来是数字1，输出，总表达式为9 3 1，后面是符号“)”，此时，我们需要去匹配此前的“(”，所以栈顶依次出栈，并输出，直到“(”出栈为止。此时左括号上方只有“ - ”，因此输出“ - ”。总的输出表达式为9 3 1 - 。如左图所示。

⑥接着是数字3，输出，总的表达式为9 3 1- 3。紧接着是符号“×”，因为此时的栈顶符号为“+”号，优先级低于“×”，因此不输出，“*”进栈。如右图。

⑦之后是符号“+”，此时当前栈顶元素“ * ”比这个“+”的优先级高，因此栈中元素出栈并输出（没有比“+”号更低的优先级，所以全部出栈)，总输出表达式为93 1-3*+。然后将当前这个符号“+”进栈。

⑧紧接着数字10，输出，总表达式变为9 3 1-3 * +10。后是符号“÷”，所以“/”进栈。如右图所示。

⑨最后一个数字2，输出，总的表达式为9 3 1 - 3 * +10 2。如左图所示。
⑩因已经到最后，所以将栈中符号全部出栈并输出。最终输出的后缀表达式结果为9 3 1-3*+10 2/+。如右图所示。

中缀转前缀

中缀转前缀的手算方法：

① 确定中缀表达式中各个运算符的运算顺序

② 选择下一个运算符，按照==「运算符 左操作数 右操作数」==的方式组合成一个新的操作数

③ 如果还有运算符没被处理，就继续 ②

“右优先”原则：只要右边的运算符能先计算，就优先算右边的

前缀表达式计算（算法实现）

用栈实现前缀表达式的计算：

①从右往左扫描下一个元素，直到处理完所有元素

②若扫描到操作数则压入栈，并回到①；否则执行③

③若扫描到运算符，则弹出两个栈顶元素（先弹出的为左操作数），执行相应运算，运算结果压回栈顶，回到①

3.3.3 栈在递归中的应用

在高级语言中，调用自己和其他函数并没有本质的不同。我们把一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称做递归函数。

递归的结构：

每个递归定义必须至少有一个条件，满足时递归不再进行，即不再引用自身而是返回值退出。

函数调用的特点： 最后被调用的函数最先执行结束（LIFO）

函数调用时，需要用一个栈存储： ① 调用返回地址 ② 实参 ③ 局部变量

递归 ：可以把原始问题转换为属性相同，但规模较小的问题

两个条件 1.递归表达式(递归体) 2.边界条件(递归出口)

递归调用时，函数调用栈可称为“递归工作栈” 每进入一层递归，就将递归调用所需信息压入栈顶 每退出一层递归，就从栈顶弹出相应信

缺点：效率低，太多层递归可能会导致栈溢出；可能包含很多重复计算

​递归过程退回的顺序是它前行顺序的逆序。 在退回过程中，可能要执行某些动作，包括恢复在前行过程中存储起来的某些数据。

​就是在前行阶段，对于每一层递归，函数的局部变量、参数值以及返回地址都被压入栈中。在退回阶段，位于栈顶的局部变量、参数值和返回地址被弹出，用于返回调用层次中执行代码的其余部分，也就是恢复了调用的状态。

3.3.4 队列的应用

在层次遍历中的应用

1. 树的遍历
2. 图的广度优先遍历

在计算机系统中的应用

1. FCFS 先来先服务

2. 解决主机与外部设备之间速度不匹配的问题

3. 解决由多用户引起的资源竞争问题

3.4 数组和特殊矩阵

3.4.1 数组

数组 ：由n（n>=1）个相同类型的数据元素构成的有限序列，每个数据元素称为一个数组元素

数组是线性表的推广

数组地址计算

1. 一维数组

2. 二维数组–行优先

3. 二维数组–列优先

3.4.2 特殊矩阵的压缩存储

压缩存储: 多个值相同的元素只分配一个空间,0不分配空间

对称矩阵的压缩存储

若 n 阶方阵中任意一个元素 ai,j都有 ai,j = aj,i 则该矩阵为对称矩阵

三角矩阵的压缩存储

下三角矩阵：除了主对角线和下三角区，其余的 元素都相同

上三角矩阵：除了主对角线和上三角区，其余的 元素都相同

三对角矩阵的压缩存储

稀疏矩阵的压缩存储

压缩存储策略：

1. 顺序存储——三元组 <行，列，值>
2. 链式存储——十字链表法

---

第四章 串

4.1 定义和实现

4.1.1 定义

串，即字符串（String）是由零个或多个字符组成的有限序列。

T=‘iPhone 11 Pro Max?’

子串： 串中任意个连续的字符组成的子序列。 Eg：’iPhone’，’Pro M’ 是串T 的子串

主串： 包含子串的串。 Eg：T 是子串’iPhone’的主串

字符在主串中的位置： 字符在串中的序号。 Eg：’1’在T中的位置是8(第一次出现)

子串在主串中的位置： 子串的第一个字符在主串中的位置 。 Eg：’11 Pro’在 T 中的位置为

串的数据对象限定为字符集（如中文字符、英文字符、数字字符、标点字符等）

串的基本操作，如增删改查等通常以子串为操作对象

串的基本操作

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

4.1.2 串的存储结构

顺序存储

4.1.3 基本操作

1. 求子串

2. 比较

3. 定位

4.2 串的模式匹配

4.2.1 简单的模式匹配算法

串的模式匹配：在主串中找到与模式串相同的子串，并返回其所在位置

n为主串长度 m为模式串长度

朴素模式匹配算法 ：将主串中所有长度为m的子串依次与模式串对比，直到找到一个完全匹配的或所有的子串都不匹配为止

当前子串匹配失败：主串指针i指向下一个子串的第一个位置，模式串指针j回到模式串的第一个位置

当前子串匹配成功：返回当前子串第一个字符的位置

直到匹配成功/匹配失败最多需要 (n-m+1)*m 次比较

最坏时间复杂度：O(nm)

4.2.2 KMP算法

主串指针不回溯，只有模式串回溯

next[j]： 当子串的第j个位置与主串失配时，则j跳到next[j]位置

next[1]无脑写0，next[2]无脑写1

$$\mathrm{next}[j]=\{\begin{array}{l}-1\text{ ，当 }j=0\text{ 时 }\\ Max\left\{k\mid 1<k<j，{\text{ 且 }}^{\prime }{p}_1{\cdots }_{k-1}^{\prime }={}^{\prime }{p}_{j-k+1}\cdots p_{j-1}^{\prime }\right\}\text{ 当此集合不空时 }\\ 0,\text{ 其他情况 }\end{array}$$
在不匹配的位置前，画一个分界线，模式串一步一步向后退，直到分界线之前“能对上”，或模式串完全跨过分界线为止。此时，j指向哪，next数组值就是多少

最坏时间复杂度：O(m+n)

对于改进过的 KMP算法，它是在计算出next值的同时，如果a位字符与它next值指向的b位字符相等，则该a位的nextval就指向b位的nextval 值，如果不等，则该a位的nextval值就是它自己a位的next 的值。

---

第五章 树与二叉树

5.1 树的基本概念

5.1.1 树的定义

树（Tree )是n (n≥0）个结点的有限集。n=0时称为空树。

在任意一棵非空树中应满足：

1）有且仅有一个特定的称为根的结点。

2）当n > 1时，其余结点可分为m（m > 0）个互不相交的有限集合T1, T2,…, Tm，其中每个集合本身又是一棵树，并且称为根结点的子树。

非空树的特性：

1. 有且仅有一个根节点
2. 没有后继的结点称为“叶子结点”（或终端结点）
3. 有后继的结点称为“分支结点”（或非终端结点）
4. 除了根节点外，任何一个结点都有且仅有一个前驱
5. 每个结点可以有0个或多个后继。

树是一种递归定义的数据结构

5.1.2 基本术语

1. 结点的度 一个结点的子结点个数
2. 树的度 树中结点的最大度数
3. 结点的深度 从根结点开始自顶向下逐层累加
4. 结点的高度 从叶结点开始自底向上逐层累加
5. 树的高度(深度) 树中结点的最大层数
6. 两结点之间的路径 两结点之间经过的结点序列
7. 路径长度 路径上经过的边的个数
8. 注意 树中的分支是有向的(双亲指向孩子),路径从上向下,两个孩子之间不存在路径

有序树——逻辑上看，树中结点的各子树从左至右是有次序的，不能互换

无序树——逻辑上看，树中结点的各子树从左至右是无次序的，可以互换

森林：森林是m（m≥0）棵互不相交的树的集合

5.1.3 树的性质

1. 结点数=总度数+1
2. 度为m的树、m叉树 的区别

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

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

4. 高度为h的m叉树至少有 h 个结点

   高度为h、度为m的树至少有 h+m-1 个结点

5. 高度为h的m叉树至多有 $(m^h-1)/m-1$ 个结点

6. 具有n个结点的m叉树的最小高度为 $\lceil {\log }_m\left[n(m-1)+1\right]\rceil$

   

5.2 二叉树的概念

5.2.1 二叉树的定义及主要特征

二叉树(Binary Tree)是n(n≥0)个结点的有限集合,该集合或者为空集（称为空二叉树),或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。

特点：①每个结点至多只有两棵子树 ②左右子树不能颠倒（二叉树是有序树）

二叉树与度为2的有序树的区别

1. 度为2的树至少有3个结点,二叉树可为空

2. 度为2的有序树的孩子的左右次序相对于另一个孩子无须区分左右

   二叉树是有序树

特殊的二叉树

1. 满二叉树： 一棵高度为h，且含有$2^h-1$个结点的二叉树

   树中的每层都含有最多的结点，只有最后一层有叶子结点且不存在度为 1 的结点

2. 完全二叉树： 当且仅当其每个结点都与高度为h的满二叉树中编号为1～n的结点一一对应时，称为完全二叉树

   叶子结点只在最大的两层上 ，若有度为1的结点,只有一个,该结点只能是左孩子

3. 二叉排序树

   （1）左子树上所有结点的关键字小于根结点

   （2）右子树上所有结点的关键字大于根结点

   （3）左右子树又各是一颗二叉排序树

   

4. **平衡二叉树：**树上任一结点的左子树和右子树的深度之差不超过1（搜索效率高）

5.2.2 二叉树的性质

1. 设非空二叉树中度为0、1和2的结点个数分别为$n_0$、$n_1$和$n_2$，则 $n_0=n_2+1$ 。（叶子结点比二分支结点多一个）

2. 在二叉树的第i层，至多有$2^{i-1}$个结点 (i≥1)。

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

3. 高度为k的二叉树至多有 $2^k-1$ 个结点 (k≥1)。

   高度为h的m叉树至多有 $(m^h-1)/m-1$ 个结点

完全二叉树的常见考点

1. 具有n个结点的完全二叉树的高度为$\lfloor {\log }_{2}n\rfloor +1$（其中，$\lfloor X\rfloor$表示向下取整，即表示不大于X的最大整数）。

2. 对于完全二叉树，可以由的结点数 n 推出度为0、1和2的结点个数为$n_0$、$n_1$和$n_2$，

   若完全二叉树有2k个（偶数）个结点，则 必有$n_1=1，n_0=k，n_2=k-1$

   若完全二叉树有2k-1个（奇数）个结点，则 必有 $n_1=0，n_0=k，n_2=k-1$

如果对于一颗有n个结点的完全二叉树的结点按层次编号，即完全二叉树的判定编号方法，对任一结点i（1≤i≤n）都有：

1.如果$i=1$，则结点i是二叉树的根，无双亲；若$i>1$，则其双亲结点为$\lfloor i/2\rfloor$。

2.如果$2i>n$，则结点i无左孩子(结点主为叶子结点);否则其左孩子是结点$2i$。

3.如果$2i+1>n$，则结点i无右孩子;否则其右孩子是结点$2i+1$。

4.结点$i$ 所在层次为$\lfloor {\log }_{2}i\rfloor +1$

几个重要常考的基本操作：

1. i 的左孩子 ——2i
2. i 的右孩子 ——2i+1
3. i 的父节点—— i/2
4. i 所在的层次 —— ${\log }_{2}i+1$或${\log }_{2}i+1$

5.2.3 二叉树的存储结构

顺序存储

二叉树的顺序存储中，一定要把二叉 树的结点编号与完全二叉树对应起来

最坏情况： 高度为 h 且只有 h 个结点的单支树（所有结点只有右孩子），也至少需要$2^h-1$个存储单元

结论： 二叉树的顺序存储结构，只适合存储完全二叉树和满二叉树

链式存储

1. 二叉链表3个域: data,lchild,rchild

2. n个结点的二叉链表有n+1个空链域(根结点不用指针)形成线索链表

5.3 二叉树的遍历和线索二叉树

5.3.1 二叉树的遍历

遍历：按照某种次序把所有结点都访问一遍

先序遍历：根左右（NLR）

中序遍历：左根右（LNR）

后序遍历：左右根（LRN）

层序遍历

算法思想：

①初始化一个辅助队列

②根结点入队

③若队列非空，则队头结点出队，访问该结点，并将其左、右孩子插入队尾（如果有的话）

④重复③直至队列为空

由遍历序列构造二叉树

二叉树遍历的两个性质：

• 已知前序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。
• 已知后序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。

前序中序，确定一棵；后序中序，确定一棵。

已知前序和后序，是不能确定一棵二叉树的。

1. 先序和中序

（1）先序中: 第一个为根结点

（2）中序中: 根结点分割成两个子序列,前左子树,后右子树

（3）先序中: 找到两个子序列,各自的第一个结点又是根结点

2. 后序和中序 后序最后一个结点相当于先序第一个结点

   

3. 层序和后序不可以

   

5.3.2 线索二叉树

目的: 加快查找结点前驱和后继的速度

线索: 指向前驱和后继的指针

线索化: 对二叉树以某种次序遍历使其成为线索二叉树的过程

无左子树,令lchild指向前驱结点;

无右子树,令rchild指向后继结点的前驱,后继由具体的遍历方式决定

我们需要一个区分标志，来决定和区分lchild和rchild的指向。因此，我们需要在每个结点增设两个标志域lTag和rTag

其中：

• ltag 为0时指向该结点的左孩子，为1时指向该结点的前驱。

• rtag为0时指向该结点的右孩子，为1时指向该结点的后继。

线索二叉树的构造方式：在原来二叉树的基础上，对于空指针域进行判断，并改变Tag值，结合遍历的结果，使得空指针域进行重新指向。

线索化的实质就是将二叉链表中的空指针改为指向前驱或后继的线索。

二叉树线索化

5.4 树、森林

5.4.1 树的存储结构

双亲表示法（顺序存储）

1. 定义: 连续空间存储,每个结点增设一个伪指针,指示双亲在数组中位置,根结点下标为0,其伪指针为-1

2. 特点: 可以很快得到双亲,但求孩子要遍历整个结构

   

孩子表示法（顺序+链式存储）

1. 定义：顺序存储各个节点，每个结点中保存孩子链表头指针

2. 特点: 求孩子很方便,求双亲不方便

孩子兄弟表示法（链式存储）

1. 定义: 左指针指向第一个孩子,右指针指向第一个兄弟,二叉链表作为存储结构
2. 优点: 方便实现树转化为二叉树,易于查找孩子
3. 缺点: 查找双亲麻烦,若增设parent指向双亲,会方便

5.4.2 树、森林和二叉树的转换

树转换为二叉树

将树转换为二叉树的步骤如下：
1．加线。在所有兄弟结点之间加一条连线。
2．去线。对树中每个结点，只保留它与第一个孩子结点的连线，删除它与其他孩子结点之间的连线。
3．层次调整。以树的根结点为轴心，将整棵树顺时针旋转一定的角度，（旋转45°）使之结构层次分明。注意第一个孩子是二叉树结点的左孩子，兄弟转换过来的孩子是结点的右孩子。

森林转化为二叉树

1．把每个树转换为二叉树。
2．第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为
前一棵二叉树的根结点的右孩子，用线连接起来。当所有的二叉树连接起来后就得到了由森林转换来的二叉树。

二叉树转化为森林

​ 判断一棵二叉树能够转换成一棵树还是森林，标准很简单，**那就是只要看这棵二叉树的根结点有没有右孩子，有就是森林，没有就是一棵树。**那么如果是转换成森林，步骤如下:

​ 1.从根结点开始，若右孩子存在，则把与右孩子结点的连线删陈，再查看分离后的二叉树，若右孩子存在，则连线删除……，直到所有右孩子连线都删除为止，得到分离的二叉树。

​ 2.再将每棵分离后的二叉树转换为树即可。

5.4.3 树和森林的遍历

树的先根遍历（深度优先遍历）

先访问根,再从左到右遍历每棵子树,与相应二叉树的先序序列相同

树的后根遍历（深度优先遍历）

从左到右遍历每棵子树,再访问根，与这棵树相应二叉树的 中序序列相同

树的层次遍历（广度优先遍历）

①若树非空，则根节点入队

②若队列非空，队头元素出队并访问，同 时将该元素的孩子依次入队

③重复②直到队列为空

森林的先序遍历==依次对各个子树进行先序遍历

若森林为非空，则按如下规则进行遍历：

(1)访问森林中第一棵树的根结点。

(2)先序遍历第一棵树中根结点的子树森林。

(3)先序遍历除去第一棵树之后剩余的树构成的森林。

森林的中序遍历==依次对各个子树进行中序遍历

若森林为非空，则按如下规则进行遍历：

（1） 中序遍历森林中第一棵树的根结点的子树森林。

（2） 访问第一棵树的根结点。

（3）中序遍历除去第一棵树之后剩余的树构成的森林

5.5 树与二叉树的应用

5.5.1 哈夫曼树和哈夫曼编码

结点的权： 有某种现实含义的数值（如：表示结点的重要性等）

结点的带权路径长度： 从树的根到该结点的路径长度（经过的边数）与该结点上权值的乘积

树的带权路径长度： 树中所有叶结点的带权路径长度之和

定义： 在含有n个带权叶结点的二叉树中，其中带权路径长度（WPL）最小的二叉树称为哈夫曼树，也称最优二叉树

哈夫曼树的构造

1.根据给定的n个权值 { w 1 , w 2 , w 3 , . . . , w n } \left \{ w_{1},w_{2},w_{3},...,w_{n} \right \} {w1​,w2​,w3​,...,wn​}构成n棵二叉树的集合 F = { T 1 , T 2 , T 3 , . . . , T n } F = \left \{ T_{1},T_{2},T_{3},...,T_{n} \right \} F={T1​,T2​,T3​,...,Tn​}其中每棵二叉树$T_i$中只有一个带权为$w_i$根结点，其左右子树均为空。

2.在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。

3.在F中删除这两棵树，同时将新得到的二叉树加入F中。

4.重复2和3步骤,直到F只含一棵树为止。这棵树便是哈夫曼树。

特点

1. 每个初始结点最终都成为叶结点，且权值越小的结点到根结点的路径长度越大
2. 哈夫曼树的结点总数为$2n-1$
3. 哈夫曼树中不存在度为1的结点。
4. 哈夫曼树并不唯一，但WPL必然相同且为最优

哈夫曼编码

固定长度编码: 每个字符用相等长度的二进制位表示

可变长度编码：允许对不同字符用不等 长的二进制位表示

前缀编码 :没有一个编码是另一个编码的前缀

构造哈夫曼编码：

（1）字符集中的每个字符作为一个叶子结点，各个字符出现的频度作为结点的权值，根据之前介绍的方法构造哈夫曼树

（2）从根结点到叶子结点的路径上标记序列,0转向左孩子,1转向右孩子

5.5.2 并查集

---

第六章 图

6.1 图的基本概念

图的定义

图G由顶点集V和边集E组成，记为G = (V, E)。

其中，V(G)表示图G中顶点的有限非空集；E(G) 表示图G中顶点之间的关系（边）集合。

若V = {v1, v2, … , vn}，则用==|V|表示图G中顶点的个数==，也称图G的阶。

E = {(u, v) | u∈V, v∈V}，用==|E|表示图G中边的条数==。

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

有向图： 若E是有向边（也称弧）的有限集合时，则图G为有向图。 弧是顶点的有序对，记为==<v,w>，其中v、w是顶点，v称为 弧尾，w称为弧头==，称为从顶点v到顶点w的弧，也称 v邻接到w，或w邻接自v。 <v,w> ≠<w,v>

无向图： 若E是无向边（简称边）的有限集合时，则图G为无向图。边 是顶点的无序对，记为(v, w)或(w, v)，因为==(v, w) = (w, v)，其 中v、w是顶点==。可以说顶点w和顶点v互为邻接点。边(v, w) 依附于顶点w和v，或者说边(v, w)和顶点v、w相关联。

简单图：① 不存在重复边； ② 不存在顶点到自身的边

多重图：图G中某两个结点之间的边数多于 一条，又允许顶点通过同一条边和自己关联， 则G为多重图

顶点的度、入度、出度

无向图：

顶点v的度是指依附于该顶点的边的条数，记为TD(v)。

无向图的全部顶点的度的和等于边数的2倍

有向图：

入度是以顶点v为终点的有向边的数目，记为ID(v)；

出度是以顶点v为起点的有向边的数目，记为OD(v)。

顶点v的度等于其入度和出度之和，即 TD(v) = ID(v) + OD(v)

顶点-顶点的关系描述

1. 路径——顶点vp到顶点vq之间的一条路径是指顶点序列 ，
2. 回路——第一个顶点和最后一个顶点相同的路径称为回路或环
3. 简单路径——在路径序列中，顶点不重复出现的路径称为简单路径。
4. 简单回路——除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。
5. 路径长度——路径上边的数目
6. 点到点的距离——从顶点u出发到顶点v的最短路径若存在，则此路径的长度称为从u到v的距离。 若从u到v根本不存在路径，则记该距离为无穷（∞）
7. 无向图中，若从顶点v到顶点w有路径存在，则称v和w是连通的
8. 有向图中，若从顶点v到顶点w和从顶点w到顶点v之间都有路径，则称这两个顶点是强连通的
9. 若图G中任意两个顶点都是连通的，则称图G为 连通图，否则称为非连通图
10. 若图中任何一对顶点都是强连通的，则称此图为 强连通图

11. 子图： 设有两个图G = (V, E)和G’ = (V’,E’)，若V’是V的子集，且E’是 E的子集，则称G’是G的子图。

12. 生成子图：满足==V(G’) = V(G)==的子图G’

13. 连通分量： 无向图中的极大连通子图称为连通分量。

    极大连通子图：子图必须连通，且包含 尽可能多的顶点和边

14. 强连通分量: 有向图中的极大强连通子图称为有向图的强连通分量

15. 连通图(无向)的生成树是包含图中全部顶点的一个极小连通子图

    极小： 边尽可能的少，但要保持连通，包含尽可能多的顶点

    若图中顶点数为n，则它的生成树含有 n-1 条边。

16. 在非连通图中，连通分量的生成树构成了非连通图的生成森林。

边的权、带权图/网

边的权——在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。

带权图/网——边上带有权值的图称为带权图，也称网。

带权路径长度——当图是带权图时，一条路径上所有边的权值之和，称为该路径的带权路径长度

特殊形态的图

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

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

边数很少的图称为稀疏图，反之称为稠密图

树——不存在回路，且连通的无向图

n个顶点的树，必有n-1条边

有向树——一个顶点的入度为0、其余顶点的 入度均为1的有向图，称为有向树

6.2 图的存储及基本操作

6.2.1 邻接矩阵法

无向图：

第$i$个结点的度 = 第$i$行（或第$i$列）的非零元素个数

有向图：

第$i$个结点的出度 = 第$i$行的非零元素个数

第$i$个结点的入度 = 第$i$列的非零元素个数

第$i$个结点的度 = 第$i$行、第$i$列的非零元素个数之和

邻接矩阵法求顶点的度/出度/入度的时间复杂度为 O(|V|)

空间复杂度：$O(|V{|}^2)$ ——只和顶点数相关，和实际的边数无关

邻接矩阵法的性质

设图G的邻接矩阵为A（矩阵元素为0/1），则$A^n$ 的元素$A^n[i][j]=由顶点i到顶点j的长度为n的路径的数目$

6.2.2 邻接表法

1.图中顶点用一个一维数组存储，同时，每个数据元素还需要存储指向第一个邻接点的指针。

2.图中每个顶点$V_i$的所有邻接点构成一个线性表，用单链表存储。

6.2.3 邻接多重表

6.2.4 十字链表

6.2.5 图的基本操作

• Adjacent(G,x,y)：判断图G是否存在边或(x, y)。

• Neighbors(G,x)：列出图G中与结点x邻接的边。

• InsertVertex(G,x)：在图G中插入顶点x。

• DeleteVertex(G,x)：从图G中删除顶点x。

• AddEdge(G,x,y)：若无向边(x, y)或有向边不存在，则向图G中添加该边。

• RemoveEdge(G,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)或对应的权值。

• Set_edge_value(G,x,y,v)：设置图G中边(x, y)或对应的权值为v。

6.3 图的遍历

6.3.1 广度优先遍历BFS

队列

bool visited[MaxVertexNum];//访问标记数组

void BFS(Graph G,int v){//从顶点v出发，广度优先遍历图G
    visit(v);//访问初始顶点v
    visited[v] = true;//做已访问标记
    Enqueue(Q,v);//入队
    while(!IsEmpty(Q))
    {
        DeQueue(Q,v);
        for(w = FirstNeighbor(G,v);w>=0;w = NextNeighbor(G,v,w))//返回除w外的v的其他邻接点
        {
            if(!visited[w])//若w为尚未访问的结点
            {
                visit(w);//访问结点
                visited[w] = true;//标记为已访问
                Enqueue(Q,w);//w入队
            }
        }
    }
}

步骤：

1. 选择一个起始节点作为当前节点，并将其标记为已访问。

2. 将起始节点加入一个队列中。

3. 当队列不为空时，执行以下步骤：

   ​ a. 从队列中取出一个节点作为当前节点。 b. 遍历当前节点的所有邻居节点：

   • 如果邻居节点未被访问过，则将其标记为已访问，并将其加入队列中。 c. 标记当前节点为已处理。

4. 重复步骤3直到队列为空，即所有节点都被访问过。

同⼀个图的邻接矩阵表示⽅式唯⼀，因此⼴度优先遍历序列唯⼀

同⼀个图邻接表表示⽅式不唯⼀，因此⼴度优先遍历序列不唯⼀

存在的问题：如果是⾮连通图，则⽆法遍历完所有结点

性能分析 ：空间复杂度: O(|V|)

时间复杂度：邻接表:O(|V|+|E|) 邻接矩阵:O(|V|²)

广度优先生成树

定义: 广度遍历过程中,得到的一颗遍历树

特点: 邻接矩阵中唯一,邻接表中不唯一

对⾮连通图的⼴度优先遍历，可得到⼴度优先⽣成森林

6.3.2 深度优先遍历DFS

回溯、递归

bool visited[MaxVertexNum];//访问标记数组

void DFS(Graph G,int v)//从v出发，深度优先图G
{
    visit(v);
    visited[v] = true;
    for(w = FirstNeighbor(G,v);w>=0;w = NextNeighbor(G,v,w))
        if(!visited[w])
        {
            DFS(G,w);
        }
}
void DFSTraverse(Graph G)
{
    for(int v = 0;v<G.vexnum;v++)//初始化标记数组
        visited[v] = false;
    for(int v = 0;v<G.vexnum;v++)//从v = 0开始遍历
        if(!visited[v])
            DFS(G,v);
}

步骤：

1. 首先访问起始顶点v
2. 访问v的未访问过的任一邻接顶点w
3. 再访问w的未访问过的任一邻接顶点w2
4. 重复下去,直到不能继续向下访问,依次退回到最近被访问的顶点

存在的问题：如果是非连通图，则无法遍历完所有结点

性能分析：

空间复杂度：来⾃函数调⽤栈，最坏情况，递归深度为O(|V|)

时间复杂度=访问各结点所需时间+探索各条边所需时间

邻接表:O(|V|+|E|)， 邻接矩阵: O(|V|²)

同⼀个图的邻接矩阵表示⽅式唯⼀，因此深度优先遍历序列唯⼀，深度优先⽣成树也唯⼀

同⼀个图邻接表表示⽅式不唯⼀，因此深度优先遍历序列不唯⼀，深度优先⽣成树也不唯⼀

6.3.3 图的遍历与图的连通性

对⽆向图进⾏BFS/DFS遍历 调⽤BFS/DFS函数的次数=连通分量数

对于连通图，只需调⽤1次 BFS/DFS

对于强连通图，从任⼀结点出发都只需调⽤1次 BFS/DFS

6.4 图的应用

6.4.1 最小生成树

​ 对于⼀个带权连通⽆向图G = (V, E)，⽣成树不同，每棵树的权（即树中所有边上的权值 之和）也可能不同。设R为G的所有⽣成树的集合，若T为R中边的权值之和最⼩的⽣成 树，则T称为G的最⼩⽣成树（Minimum-Spanning-Tree, MST）。

• 最小生成树可能有多个，但边的权值之和总是唯⼀且最小的

• $最⼩⽣成树的边数=顶点数-1$。砍掉⼀条则不连通，增加⼀条边则会出现回路

• 如果⼀个连通图本身就是⼀棵树，则其最小生成树就是它本身

• 只有连通图才有生成树，非连通图只有生成森林

Prim 算法（普⾥姆）

从某⼀个顶点开始构建生成树；

每次将代价最小的新顶点纳入生成树，直到所有顶点都纳入为止。

步骤：

1. 初始化: 先任选一个顶点作为初始顶点
2. 循环(直到包含所有顶点): 再选择这个顶点的邻边中权值最小的边且不会构成回路
3. 再选择这两个顶点的邻边中权值最小的边且不会构成回路

特点： 时间复杂度:$O(|V{|}^2)$,不依赖于|E|,适合边稠密的图

Kruskal 算法（克鲁斯卡尔）

每次选择⼀条权值最小的边，使这条边的两头连通（原本已经连通的就不选）直到所有结点都连通

步骤：

1. 初始化: 先包含所有的顶点,没有边
2. 循环(直到成为一棵树): 按权值递增的顺序选择边且不构成回路,直到包含n-1条边

特点： 采用堆存放边集合,时间复杂度$O(|E|log|E|)$,适合边稀疏而顶点较多的图

6.4.2 最短路径

BFS求⽆权图的单源最短路径

⽆权图可以视为⼀种特殊的带权图，只是每条边的权值都为1

BFS算法求单源最短路径只适⽤于⽆ 权图，或所有边的权值都相同的图

Dijkstra算法求单源最短路径

1. 初始化: 集合S为{0},dist[]为初始顶点0到各个顶点的距离,没有为无穷 path[]中初始顶点0为-1(一直不变),0到其他点有距离为0,没有为无穷
2. 在dist[]中选剩下值最小的点j,若dist[j]+arcs[j] [k] <dist[k],则更新dist[k] 在集合S中加入此点,若更新了dist[k],则令path[k]=j
3. 再在集合S中剩下的点中重复操作,直到S包含所有点

单源时间复杂度为O(|V|²),所有结点对为O(|V|³)

Floyd算法法求各顶点间最短路径

1. 递推产生一个n阶方阵序列,从$A^{-1}$开始到$A^{n-1}$

2. 初始时: 若任意两个顶点存在边,权值作为最短路径,不存在为无穷

3. 以后逐步在原路径中加入顶点k(k从0到n-1)作为中间顶点,若路径减少,则替换原路径

4. A(k)[i][j]: 从顶点i到顶点j,中间结点的序号不大于k的最短路径的长度

   $若A^{(k-1)}[i][j] > A^{{(k-1)}[i][k]+A}{(k-1)}[k][j] $

   $则A^k[i][j]=A^{(k-1)}[i][k]+A^{(k-1)}[k][j]$ $Pat{h}^k[i][j]=k$

   否则$A^k和pat{h}^k保持原值$

特点：

1. 时间复杂度: O(|V|³)
2. 允许带负权值的边,不允许包含负权值的边组成回路
3. 适用于带权无向图,视为有往返二重边的有向图

6.4.3 有向无环图DAG

有向⽆环图： 若⼀个有向图中不存在环，则称为有向⽆环图，简称DAG图

结题步骤：

Step 1： 把各个操作数不重复地排成⼀排

Step 2： 标出各个运算符的⽣效顺序（先 后顺序有点出⼊⽆所谓）

Step 3： 按顺序加⼊运算符，注意“分层”

Step 4： 从底向上逐层检查同层的运算符 是否可以合体

6.4.4 拓扑排序

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

拓扑排序：在图论中，由⼀个有向⽆环图 的顶点组成的序列，当且仅当满⾜下列条 件时，称为该图的⼀个拓扑排序： ① 每个顶点出现且只出现⼀次。 ② 若顶点A在序列中排在顶点B的前⾯，则 在图中不存在从顶点B到顶点A的路径。

或定义为：拓扑排序是对有向⽆环图的顶 点的⼀种排序，它使得若存在⼀条从顶点A 到顶点B的路径，则在排序中顶点B出现在 顶点A的后⾯。每个AOV⽹都有⼀个或多个 拓扑排序序列。

拓扑排序的实现：

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

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

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

对⼀个AOV⽹，如果采⽤下列步骤进⾏排序，则称之为逆拓扑排序：

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

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

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

6.4.5 关键路径

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

AOE⽹具有以下两个性质：

① 只有在某顶点所代表的事件发⽣后，从该顶点出发的各有向边所代表的活动才能开始；

② 只有在进⼊某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发⽣。 另外，有些活动是可以并⾏进⾏的

在AOE⽹中仅有⼀个⼊度为0的顶点，称为开始顶点（源点），它表示整个⼯程的开始； 也仅有⼀个出度为0的顶点，称为结束顶点（汇点），它表示整个⼯程的结束。

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

求关键路径步骤

① 求所有事件的最早发⽣时间 ve( ) --决定了所有从vk开始的活动能够开⼯的最早时间

② 求所有事件的最迟发⽣时间 vl( ) --它是指在不推迟整个⼯程完成的前提下，该事件最迟必须发⽣的时间

③ 求所有活动的最早发⽣时间 e( ) – 指该活动弧的起点所表⽰的事件的最早发⽣时间

④ 求所有活动的最迟发⽣时间 l( ) --它是指该活动弧的终点所表示事件的最迟发⽣时间与该活动所需时间之差

⑤ 求所有活动的时间余量 d( ) –时间余量d(i)=l(i)-e(i)

d(i)=0的活动就是关键活动, 由 关键活动可得关键路径

1. 求所有事件的最早发⽣时间 ve( )

   从源点开始往后加上权值,取不同路径的最大值

2. 求所有事件的最迟发⽣时间 vl( )

   Vl(汇点)=Ve(汇点),从汇点往前依次减去权值,取不同路径最小值

3. 求所有活动的最早发⽣时间 e( )

   若边表⽰活动ai，则有e(i) = ve(k)

4. 求所有活动的最迟发⽣时间 l( )

   若边表⽰活动ai，则有l(i) = vl(j) - Weight(vk, vj)

5. 求所有活动的时间余量 d( )

   d(i) = l(i) - e(i)

若关键活动耗时增加，则整个⼯程的⼯期将增⻓

缩短关键活动的时间，可以缩短整个⼯程的⼯期

当缩短到⼀定程度时，关键活动可能会变成⾮关键活动

---

第七章 查找

7.1 查找的基本概念

查找 —— 在数据集合中寻找满⾜某种条件的数据元素的过程称为查找

查找表（查找结构）—— ⽤于查找的数据集合称为查找表，它由同⼀类型的数据元素（或记录）组成

关键字 —— 数据元素中唯⼀标识该元素的某个数据项的值，使⽤基于关键字的查找，查找结果应该是 唯⼀的

对查找表的常⻅操作

①查找符合条件的数据元素 ②插⼊、删除某个数据元素

只需进⾏操作① —— 静态查找表 仅关注查找速度

也要进⾏操作② —— 动态查找表 除了查找速度，也要关注插/删操作是否⽅便实现

适合静态查找表: 顺序查找,折半查找,散列查找

适合动态查找表: 二叉排序树,散列查找,二叉平衡树和B树都是二叉排序树的改进

查找算法的评价指标

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

平均查找长度（ASL, Average Search Length）—— 所有查找过程中进行关键字的比较次数的平均值

7.2 顺序查找和折半查找

7.2.1 顺序查找

顺序查找，⼜叫“线性查找”，通常⽤于线性表

ASL成功=$(n+1)/2$ ASL失败=n+1

7.2.2 折半查找（二分查找）

折半查找，⼜称“⼆分查找”，仅适⽤于有序的顺序表。

折半查找判定树的构造

如果当前low和high之间有奇数个元素，则 mid 分隔后，左右两部分元素个数相等

如果当前low和high之间有偶数个元素，则 mid 分隔后，左半部分⽐右半部分少⼀个元素

折半查找的判定树中，若 mid = $\lfloor (low+high)/2\rfloor$，则对于任何⼀个结点，必有： $右⼦树结点数-左⼦树结点数=0或1$

折半查找的判定树⼀定是平衡⼆叉树

折半查找的判定树中，只有最下⾯⼀层是不满的 因此，元素个数为n时树⾼h = $\left \lceil \log_{2}{(n+1)} \right \rceil $= $\lfloor {\log }_{2}n\rfloor +1$

折半查找的时间复杂度 = $O({\log }_{2}n)$

7.2.3 分块查找

分块查找，⼜称索引顺序查找，算法过程如下：

①在索引表中确定待查记录所属的分块（可顺序、可折半）

②在块内顺序查找

特点：块内⽆序、块间有序

算法思想：

1. 分为若干子块,块内可以无序,块之间有序
2. 第一块中最大关键字<第二块中所有记录,以此类推
3. 建立一个索引表,含有各块最大关键字和各块第一个元素的地址,按关键字有序排列

若索引表中不包含⽬标关键字，则折半查找索引表最终停在 low>high，要在low所指分块中查找

low超出索引表范 围，查找失败

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

$s=\sqrt{2}时，AS{L}_{min}=\sqrt{n}+1$

7.3 树型查找

7.3.1 二叉排序树BST

二叉排序树，又称二叉查找树（BST，Binary Search Tree）

二叉排序树可用于元素的有序组织、搜索。

具有如下性质：

①左子树上所有结点的关键字均小于根结点的关键字；

②右子树上所有结点的关键字均大于根结点的关键字。

③左子树和右子树又各是一棵二叉排序树。

④左子树结点值 < 根结点值 < 右子树结点值

⑤进行中序遍历，可以得到一个递增的有序序列

二叉排序树的删除：

① 若 被删除结点z是叶结点，则直接删除， 不会破坏二叉排序树的性质。

② 若结点z只有一棵左子树或右子树，则 让z的子树成为z父结点的子树，替代z的位置

③ 若结点z有左、右两棵子树，则 令z的直接后继（或直接前驱）替代z，然后从二叉排序树中直接删去这个直接后继（或直接前驱），这样就转换成了第一或第二种情况

查找效率分析：

1. 平均查找长度$ASL=(每层个数\ast 对应层数)/总个数$
2. 最坏情况: 类似有序单链表$O(n)$
3. 最好情况: 平衡二叉树$O({\log }_{2}n)$
4. 查找过程: 与二分查找类似,但二分查找的判定树唯一

7.3.2 平衡二叉树AVL

平衡二叉树（Balanced Binary Tree），简称平衡树（AVL树）——树上任一结点的左子树和右子树的高度之差不超过1

$结点的平衡因子=左子树高-右子树高$

平衡二叉树的插入： 从插入点往回 找到第一个不平衡结点，调整以该结点为 根的子树，每次调整的对象都是 “最小不平衡子树”

调整最小不平衡子树方法的本质就是要满足平衡二叉树的特性，即：左子树<根<右子树

LL平衡旋转（右单旋转）

​ 由于在结点A的左孩子（L）的左子树（L）上插入了新结点，A的平衡因子由1增至2，导致以A为根的子树失去平衡，需要一次向右的旋转操作。

1. 将A的左孩子B向右上旋转代替A成为根结点
2. 将A结点向右下旋转成为B的右子树的根结点
3. 而B的原右子树则作为A结点的左子树

RR平衡旋转（左单旋转）

​ 由于在结点A的右孩子（R）的右子树（R）上插入了新结点，A的平衡因 子由-1减至-2，导致以A为根的子树失去平衡，需要一次向左的旋转操作。

1. 将A的右孩子B向左上旋转代替 A成为根结点
2. 将A结点向左下旋转成为B的左子树的根结点
3. 而B的原左子树则作为A结点的右子树

LR平衡旋转（先左后右双旋转）

​ 由于在A的左孩子（L）的右子树（R）上插入新结点，A的平衡因子由1增至2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先左旋转后右旋转。

1. 先将A结点的左孩子B的右子树的根结点C向左上旋转提升到B结点的位置，
2. 然后再把该C结点向右上旋转提升到A结点的位置

RL平衡旋转（先右后左双旋转）。

​ 由于在A的右孩子（R）的左子树（L）上插入新结点，A的平衡 因子由-1减至-2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先右旋转后左旋转。

1. 先将A结点的右孩子B的左子树的根结点C向右上旋转提升到B结点的位置
2. 然后再把该C结点向左上旋转提升 到A结点的位置

含有n个结点的平衡二叉树的最大深度为 $O({\log }_{2}n)$ ，平衡二叉树的平均查找长度为 $O({\log }_{2}n)$

7.4 散列表

7.4.1 散列表的基本概念

散列表（Hash Table），⼜称哈希表。是⼀种数据结构。

特点： 数据元素的关键字与其存储地址直接相关

同义词：不同的关键字通过散列函数映射到同⼀个值

冲突： 通过散列函数确定的位置已经存放了其他元素

处理冲突的⽅法——拉链法（⼜称链接法、链地址法）：把所有“同义词”存储在⼀个链表中

7.4.2 散列函数的构造方法

1. 除留余数法

   $H(key)=key\%p$

   P的选取: 不大于m(散列表长)但最接近或等于m的质数

2. 直接定址法

   $H(key)=key或H(key)=a\ast key+b$ 其中，a和b是常数。

   这种⽅法计算最简单，且不会产⽣冲突。它适合关键字的分布基本连续的情况，若关键字分布不连续，空位较多，则会造成存储空间的浪费

3. 数字分析法

   选取数码分布较为均匀的若⼲位作为散列地址

   ​ 设关键字是r进制数（如⼗进制数），而r个数码在各位上出现的频率不⼀定相同，可能在某些位上分布均匀⼀些，每种数码出现的机会均等；而在某些位上分布不均匀，只有某⼏种数码经常出现，此时可选取数码分布较为均匀的若⼲位作为散列地址。这种⽅法适合于已知的关键字集合， 若更换了关键字，则需要重新构造新的散列函数

4. 平方取中法

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

   ​ 具体取多少位要视实际情况⽽定。这种⽅法得到的散列地址与关键字的每位都有关系，因此使得 散列地址分布⽐较均匀，适⽤于关键字的每位取值都不够均匀或均⼩于散列地址所需的位数

5. 折叠法

   关键字分割成位数相同的几部分,取叠加和作为散列地址

   适用于位数很多且每位上数字分布大致均匀

7.4.3 处理冲突的方法

1. ⽤拉链法（⼜称链接法、链地址法）处理“冲突”：把所有“同义词”存储在⼀个链表中

   // 定义哈希表中的节点结构
   typedef struct Node {
       char* key;
       char* value;
       struct Node* next;
   } Node;
   
   // 定义哈希表结构
   typedef struct HashTable {
       int size;
       Node** table;
   } HashTable;
   

   

2. 开放定址法（重点）

   是指可存放新表项的空闲地址既向它的同义词表项开放，⼜向它的⾮同义词表项开放。

   其数学递推公式为：$H_i=(H(key)+d_i)\%m$

   $H(key)为散列函数，i=0,1,2,...,k(k\le m-1)$ m表示散列表表⻓；$d_i$为增量序列；i 可理解为“第i次发⽣冲突“

   ①线性探测法—— $d_i$ = 0, 1, 2, 3, …, m-1；

   ​ 即发⽣冲突时，每次往后探测相邻的下⼀个单元是否为空。

   线性探测法很容易造成同义词、⾮同义词的“聚集（堆积）”现象，严重影响查找效率

   产⽣原因——冲突后再探测⼀定是放在某个连续的位置

   

   平方探测法

   ​ 当$d_i=0^2,1^2,-1^2,2^2,-2^2,\dots ,k^2,-k^2$时，称为平方探测法，⼜称⼆次探测法其中k≤m/2

   优点: 可以避免出现堆积问题

   缺点: 只能探测一半单元

   ③伪随机序列法

   $d_i$ 是⼀个伪随机序列，如$d_i$= 0, 5, 24, 11, …

   

注意：

1. 不能随便物理删除已有元素,会截断其他相同散列地址元素的查找地址
2. 可做删除标记,逻辑删除
3. 副作用: 多次删除后,表面上散列表很满,其实还有很多位置未用,需定期维护

7.4.4 散列查找及性能分析

散列查找执行步骤如下：

1. 初始化：$Addr=Hash(key)$
2. 检测查找表中地址为 Addr 的位置上是否有记录，若无记录，返回查找失败；若有记录，比较它和 key 的值，若相等则返回查找成功，否则执行步骤③。
3. 用给定的处理冲突方式计算“下一个散列表地址”，并把 Addr 置为此地址，转入步骤②。

**平均查找长度（ASL）：**散列表查找成功的平均查找长度，即找到表中已有表项的平均比较次数；

散列表查找失败的平均查找长度即找不到待查的表项但能找到插入位置的平均比较次数。

查找效率：

1. 取决于: 散列函数,处理冲突的方法,装填因子
2. 装填因子(α): 定义一个表的装满程度α = 表中记录数n/散列表长度m
3. 平均查找长度依赖于α,不直接依赖于n或m

易错点：

1. K个同义词采用线性探测填入散列表,需要探测K(K+1)/2次
2. 冲突产生的概率与装填因子的大小成正比 越满越容易冲突
3. 不能用随机数函数构造散列函数,无法进行正常的查找

注意点:

1. $AS{L}_{成功查找次数}$=冲突次数+1
2. 根据散列函数确定一共需要的查找的位置,对每个位置查找直到为空时结束,不为空时用相应的冲突 处理方法再进行查找,为空时也需要比较一次

• 例：现有长度为11且初始为空的散列表HT，散列函数$H(key)=key$%7，采用线性探查法解决冲突。

  将关键字序列87，40，30，6，11，22，98，20 ，38依次插入HT后，HT的查找失败的平均长度是多少？ 查找成功的平均查找长度又是多少？

  答：关键字序列依次插入后，散列表HT如下所示：

  

  $ASL查找成功=(1+1+1+1+1+1+1+2+6)/9=5/3$

  $ASL查找失败=(10+9+8+7+6+5+4)/7=7$

---

第八章 排序

8.1 排序的基本概念

排序（Sort），就是重新排列表中的元素，使表中的元素满足按关键字有序的过程。

算法的稳定性：若待排序表中有两个元素$R_i$和$R_j$，其对应的关键字相同即$ke{y}_i$ = $ke{y}_j$，且在排序前$R_i$在$R_j$的前⾯，若使⽤某⼀排序算法排序后，$R_i$仍然在$R_j$的前⾯，则称这个排序算法是稳定的，否则称排序算法是不稳定的。

8.2 插入排序

8.2.1 直接插入排序

算法思想：

​ 每次将⼀个待排序的记录按其关键字大小插入到前面已排好序的子序列中， 直到全部记录插⼊完成

• 时间复杂度：最好情况$O(n)$ ，最差情况 $O(n^2)$，平均情况 $O(n^2)$。
• 空间复杂度： $O(1)$ 。
• 算法稳定性：稳定。
• 适用性：适用于顺序存储和链式存储的线性表。

对链表的插入排序：

// 对链表L进行插入排序
void InsertSort(LinkList &L) {
    LNode *p = L->next, *pre;  // 定义指针p指向链表第一个结点，pre指向p的前一个结点
    LNode *r = p->next;  // 定义指针r指向p的下一个结点
    p->next = NULL;  // 将p的next指针置为空，即将p作为新链表的第一个结点
    p = r;  // 将p指向原链表的第二个结点，即将r作为新链表的第一个待插入结点

    while (p != NULL) {  // 遍历原链表的剩余结点
        r = p->next;  // 将r指向p的下一个结点，保存待插入结点的下一个结点
        pre = L;  // 将pre指向链表的头结点，即从头开始查找待插入位置

        while (pre->next != NULL && pre->next->data < p->data)  // 在新链表中找到待插入位置的前一个结点pre
            pre = pre->next;

        p->next = pre->next;  // 将待插入结点p的next指针指向pre的next指针指向的结点，即将p插入到pre之后
        pre->next = p;  // 将pre的next指针指向p，即将p插入到pre之后
        p = r;  // 将p指向原链表的下一个待插入结点
    }
}

8.2.2 折半插入排序

算法思路： 每次将一个待排序的记录按其关键字大小，使用折半查找找到前面子序列中应该插入的位置并插入，直到全部记录插入完成。

先⽤折半查找找到应该插⼊的位置，再移动元素

当 low>high 时折半查找停⽌，应将 [low, i-1] 内的元素全部右移，并将 A[0] 复制到 low 所指位置

当 A[mid]==A[0] 时，为了保证算法的“稳定性”，应继续在 mid 所指位置右边寻找插⼊位置

注意： 为了保证稳定性，当查找到和插入元素关键字一样的元素时，应该在这个元素的右半部分继续查找以确认位置。 即当 A[mid] == A[0] 时，应继续在mid所指位置右边寻找插入位置。

仅减少了比较元素的次数,移动的次数并未改变

8.2.3 希尔排序

1. 算法思路： 先追求表中元素的部分有序，再逐渐逼近全局有序，以减小插入排序算法的时间复杂度。

先将待排序表分割成若干形如$L[i,i+d,i+2d,\dots ,i+kd]$的“特殊”⼦表，对各个子表 分别进⾏直接插⼊排序。缩小增量d，重复上述过程，直到d=1为⽌。

空间复杂度：O(1)

时间复杂度：和增量序列 d1, d2, d3… 的选择有关，目前无法用数学手段证明确切的时间复杂度

稳定性：不稳定

适用性：仅适用于顺序表，不适用于链表

8.3 交换排序

8.3.1 冒泡排序

冒泡排序： 从后往前（或从前往后）两两⽐较相邻元素的值，若为逆序（即A[i-1]>A[i]），则交换它们，直到序列比较完。如此重复最多 n-1 次冒泡就能将所有元素排好序。

​ 为保证稳定性，关键字相同的元素不交换。

实现步骤：

1. 从最后一个元素开始,两两相邻进行比较,若为逆序,则交换它们
2. 一趟冒泡,结果将最小的元素交换到第一个位置
3. 下一趟冒泡,前一趟确定的最小元素不再参与,待排序列减少一个元素
4. 每趟冒泡的结果是序列中最小元素放到最终位置,最多n-1此完成

8.3.2 快速排序

算法思路：在待排序表L[n] 中任选一个元素 pivot 作为枢轴（通常取首元素），通过一趟排序将待排序表分为独立的两部分 L[1…k-1]和L[k−1…n]。 使得左边部分中的所有元素小于pivot，右边部分中的所有元素大于等于 pivot，则 pivot 放在了其最终位置 L[k]上。重复此过程直到每部分内只有一个元素或空为止。

​ 更小的元素都交换到左边 更大的元素都交换到右边

实现步骤：

1. 每次取当前表中第一个元素作为基准pivot(枢轴值)对表进行划分
2. $i$指向第一个元素(基准),$j$指向最后一个元素
3. 先从$j$开始,从后往前找到第一个比基准小的元素,$j$指向此元素位置,用此元素替换掉$i$所指元素
4. 再从$i$开始,从前往后找到第一个比基准大的元素,$i$指向此元素位置,用此元素替换掉$j$所指元素
5. 再次从$j$开始,循环往复,直到$i$与$j$接触停止,将基准值放到接触位置,将序列划分为两块,前面小于基准值,后面大于基准值
6. 分别取两个子序列的第一个元素作为基准值,重复操作

时间复杂度=O(n*递归层数)

最好时间复杂度=$O(n{\log }_{2}n)$

最坏时间复杂度=$O(n^2)$

空间复杂度=O(递归层数)

最好空间复杂度=$O(n{\log }_{2}n)$

最坏空间复杂度=O(n)

快速排序是所有内部排序算法中平均性能最优的排序算法

稳定性：不稳定

8.4 选择排序

8.4.1 简单选择排序

选择排序：每⼀趟在待排序元素中选取关键字最小（或最大）的元素加⼊有序子序列

简单选择排序： 每⼀趟在待排序元素中选取关键字最小的元素加⼊有序子序列

空间复杂度：O(1)

时间复杂度=$O(n^2)$

稳定性：不稳定

适⽤性：既可以⽤于顺序表，也可⽤于链表

简单选择排序和冒泡排序的区别：

简单选择排序和冒泡排序都属于简单的排序算法，它们的主要区别在于排序过程中的比较和交换操作的方式。

1. 简单选择排序：
   • 每次从未排序的元素中选择最小（或最大）的元素，与未排序部分的第一个元素交换位置。
   • 每次只进行一次交换操作，即找到最小（或最大）元素后立即交换。
   • 每轮排序只需要一次比较操作，找到最小（或最大）元素。
2. 冒泡排序：
   • 每次从最后开始比较相邻的两个元素，如果它们的顺序不正确，则交换它们的位置。
   • 每轮排序可能进行多次交换操作，直到将最大（或最小）元素移动到正确的位置。
   • 每轮排序需要多次比较操作，直到找到当前轮次的最大（或最小）元素。

总结：

• 简单选择排序每轮只进行一次交换操作，而冒泡排序可能进行多次交换操作。
• 简单选择排序每轮只需要一次比较操作，而冒泡排序每轮需要多次比较操作。
• 冒泡排序相对于简单选择排序来说，交换次数更多，但是比较次数相对较少。而简单选择排序的交换次数相对较少，但是比较次数较多。
• 两种排序算法的时间复杂度都为$O(n^2)$，但是冒泡排序的性能相对较差，因为它每轮排序都要进行多次比较和交换操作。

简单选择排序和冒泡排序在一些方面确实有相似之处:

1. 排序方式：两种排序算法都是通过比较相邻的元素来进行排序的。
   • 简单选择排序：每次选择未排序部分中的最小（或最大）元素，并将其与未排序部分的第一个元素交换位置。
   • 冒泡排序：每次比较相邻的两个元素，如果它们的顺序不正确，则交换它们的位置。
2. 时间复杂度：两种排序算法的时间复杂度都为$O(n^2)$。
   • 简单选择排序：每轮排序只需要一次比较操作，总共需要n-1轮排序，每轮排序需要n-i次比较操作，所以总的比较次数为$(n-1)+(n-2)+...+1=n\ast (n-1)/2$，即$O(n^2)$。
   • 冒泡排序：每轮排序需要多次比较操作，总共需要n-1轮排序，每轮排序需要n-i次比较操作，所以总的比较次数为$(n-1)+(n-2)+...+1=n\ast (n-1)/2$，即$O(n^2)$。

尽管它们有相似之处，但它们的具体实现和排序过程中的交换操作方式是不同的:

​ 简单选择排序每轮只进行一次交换操作，而冒泡排序可能进行多次交换操作。此外，简单选择排序每轮只需要一次比较操作，而冒泡排序每轮需要多次比较操作。

8.4.2 堆排序

若n个关键字序列L[1…n] 满⾜下⾯某⼀条性质，则称为堆（Heap）：

本质即：顺序存储的完全二叉树 （当且仅当其每个结点都与高度为h的满二叉树中编号为1～n的结点一一对应的树）

① 若满⾜：$L(i)≥L(2i)且L(i)≥L(2i+1) $（1 ≤ i ≤n/2）—— 大根堆（⼤顶堆）

② 若满⾜：$L(i)≤L(2i)且L(i)≤L(2i+1) $（1 ≤ i ≤n/2）—— 小根堆（⼩顶堆）

堆排序：

每⼀趟将堆顶元素加入有序⼦序列 （与待排序序列中的最后⼀个元素交换）并将待排序元素序列再次调整为⼤根堆 （小元素不断“下坠”）

基于小根堆排序代码

void BuildMinHeap(int A[], int len){
    for(int i=len/2; i>0; i--) 		// 从后往前调整所有非终端结点
        HeadAdjust(A, i, len);       // 调用HeadAdjust函数进行堆调整
}

void HeadAdjustMin(int A[], int k, int len){
    A[0] = A[k];                    // 将当前节点保存到A[0]
    for(int i=2*k; i<=len; i*=2){    // 沿k较大的子节点向下调整
        if(i<len && A[i] > A[i+1])   // 找到k较大的子节点
            i++;
        if(A[0] <= A[i])            // 如果当前节点小于等于k较大的子节点，结束循环
            break;
        else{
            A[k] = A[i];            // 将k较大的子节点调整至双亲节点上
            k=i;                    // 修改k值，以便继续向下筛选
        }
    }
    A[k] = A[0];                    // 将保存在A[0]的节点放到最终位置
}

void HeapSortMin(int A[], int len){
    BuildMinHeap(A, len);           // 初始建立小根堆
    for(int i=len; i>1; i--){       // n-1趟的交换和建堆过程
        swap(A[i], A[1]);           // 将当前最小值（根节点）与最后一个节点交换
        HeadAdjustMin(A,1,i-1);     // 对剩余节点进行堆调整
    }
}

与大根堆堆排序代码的区别：

• 在HeadAdjustMin函数中，比较的条件由A[0] >= A[i]改为A[0] <= A[i]，这是因为小根堆需要保证父节点的值小于等于子节点的值。

堆排序的时间复杂度 = $$O(n{\log }_{2}n)$$

堆排序的空间复杂度 = $O(1)$

稳定性： 不稳定

堆排序算法：

// 堆排序算法
void heapSort(int arr[], int n)
{
    // 首先建立大根堆
    buildMaxHeap(arr, n);
    // 依次将堆顶元素（最大值）与末尾元素交换，并调用maxHeapify维护大根堆性质
    for (int i = n - 1; i > 0; i--)
    {
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        maxHeapify(arr, i, 0);
    }
}

需要注意的是，堆排序的讲解中大幅讲解了大、小根堆的构造思想，但是未给出具体详细的堆排序的算法，在此补充。同时，各位正在学习的同学，学完了堆排序请思考这样一个问题：从大到小排序要用什么堆，从小到大呢？如果你能够清晰地思考出这个问题，恭喜，堆排序的算法思想你是完全没问题的。

8.4.3 堆的插入和删除

8.5 归并排序和基数排序

8.5.1 归并排序

算法思想： 把待排序表看作 n 个有序的长度为1的子表，然后两两合并，得到$\lceil n/2\rceil $个长度为2或1的有序表……如此重复直到合并成一个长度为n的有序表为止。

归并：把两个或多个已经有序的序列合并成⼀个新的有序表。k路归并每选出一个元素，需对比关键字k-1次。

8.5.2 基数排序

1. 算法思想： 把整个关键字拆分为d位，按照各个关键字位递增的次序（比如：个、十、百），做d趟“分配”和“收集”，若当前处理关键字位可能取得r个值，则需要建立r个队列。
2. 分配： 顺序扫描各个元素，根据当前处理的关键字位，将元素插入相应的队列。一趟分配耗时$O(n)$。
3. 收集： 把各个队列中的结点依次出队并链接。一趟收集耗时$O(r)$。

空间复杂度 = O ®

时间复杂度=O(d(n+r)）

稳定性：稳定

基数排序擅长解决的问题：

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

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

③数据元素个数 n 较⼤

8.6 内部排序算法比较与应用

算法种类	最好情况	平均情况	最坏情况	空间复杂度	是否稳定
直接插入	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	是
冒泡排序	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	是
简单选择	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	是
希尔排序				$O(1)$	否
快速排序	$O(n{\log }_{2}n)$	$O(n{\log }_{2}n)$	$O(n^2)$	$O({\log }_{2}n)$	否
堆排序	$O(n{\log }_{2}n)$	$O(n{\log }_{2}n)$	$O(n{\log }_{2}n)$	$O(1)$	否
2路归并	$O(n{\log }_{2}n)$	$O(n{\log }_{2}n)$	$O(n{\log }_{2}n)$	$O(n)$	是
基数排序	$O(d(n+r))$	$O(d(n+r))$	$O(d(n+r))$	$O(r)$	是