一篇学完：王道考研408数据结构（全）-Toy模板网

这篇具有很好参考价值的文章主要介绍了一篇学完：王道考研408数据结构（全）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

笔记首发于：lengyueling.cn

PDF版本附在 lengyueling.cn 对应文章结尾，欢迎下载访问交流

绪论

数据结构在学什么

如何用程序代码把现实世界的问题信息化
如何用计算机高效地处理这些信息从而创造价值

数据结构的基本概念

什么是数据：

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

现代计算机处理的数据：

现代计算机——经常处理非数值型问题
对于非数值型的问题：
- 我们关心每个个体的具体信息
- 我们还关心个体之间的关系

数据元素：

数据元素是数据的基本单位，通常作为一个整体进行考虑和处理。

数据项：

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

数据对象：

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

数据结构：

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
数据结构这门课着重关注的是数据元素之间的关系，和对这些数据元素的操作，而不关心具体的数据项内容。

数据结构的三要素

三要素：

逻辑结构
- 集合结构，各个元素同属一个集合，别无其他关系
- 线性结构，一对一，顺序关系
- 树状结构，一对多
- 图状结构，多对多
数据的运算，针对某种逻辑结构，结合实际需求，定义基本运算（增删改查）
物理结构（储存结构），如何用计算机实现这种数据结构
- 顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的储存单元中，元素之间的关系由储存单元的邻接关系来体现
- 链式存储：把逻辑上相邻的元素存储在物理位置上可以不相邻，借助指示元素存储地址的指针来表示元素之间的逻辑关系。
- 索引存储：在储存元素信息的同时，还简历附加的索引表。索引表中的每项成为索引项，索引项的一般形式是（关键字，地址）
- 散列存储：根据元素的关键字直接计算出该元素的存储地址，又称哈希存储

总结：

若采用顺序存储，则各个数据元素在物理上必须是连续的；若采用非顺序存储则各个数据元素在物理上可以是离散的
数据的数据结构会影响存储空间分配的方便程度
数据的存储结构会影响对数据运算的速度
运算的定义是针对逻辑结构的，指出运算的功能
运算的实现是针对存储结构的，指出运算的具体步骤

数据类型：

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

原子类型：其值不可再分的数据类型（bool、int等）
结构类型：其值可以再分解为若干分量的数据类型（struct等）

抽象数据类型（ADT）：

是抽象数据组织及其相关的操作，定义了一个ADT就是在定义一种数据结构

算法的基本概念

什么是算法：

程序=数据结构+算法
算法（Algorithm）是对特定问题求解步骤的一种描述，它是指令的有限序列，其中的每条指令表示一个或多个操作

算法的特征：

算法必须拥有以下特性，否则不能被称为算法：
有穷性：一个算法必须总在执行有穷步之后结束，且每一步都可在有穷时间内完成。
确定性：算法中每条指令必须有确切的含义，对于相同的输入只能得出相同的输出。
可行性：算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。
输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合。
输出：一个算法有一个或多个输出，这些输出是与输入有着某种特定关系的量。

好算法的特质：

正确性：算法应能够正确地解决求解问题。
可读性：算法应具有良好的可读性，以帮助人们理解。
健壮性：输入非法数据时，算法能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果。
高效率：
花的时间少：时间复杂度低
低存储量需求：费内存，空间复杂度低

算法的时间复杂度

定义： 事前预估算法时间开销T(n)与问题规模n的关系（T表示“time”）

规则：

加法规则：T(n) = T1(n) + T2(n) = O(f(n)) + O(g(n)) = O(max(f(n), g(n))) （多项相加，只保留最高阶的项，且系数变为1）
乘法规则：T(n) = T1(n)×T2(n) = O(f(n))×O(g(n)) = O(f(n)×g(n))（多项相乘，都保留）
算法好坏：O(1) < O(log2n) < O(n) < O(nlog2n) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)（口诀：常对幂指阶）
数量级仅需考虑循环内，最深层嵌套的部分
最坏时间复杂度：最坏情况下算法的时间复杂度
平均时间复杂度：所有输入示例等概率出现的情况下，算法的期望运行时间
最好时间复杂度：最好情况下算法的时间复杂度
一般只考虑最坏和平均复杂度

算法的空间复杂度

定义：空间开销（内存开销，S(n)）与问题规模n之间的关系

算法原地工作： 算法所需内存空间为常量

规则：

只需关注存储空间大小与问题规模相关的变量
加法规则、乘法规则、算法好坏判定与时间复杂度一样
递归调用的大多数情况：空间复杂度=递归调用的深度

线性表

线性表的定义和基本操作

定义：

线性表(Linear List)是具有相同数据类型的n（n≥0）个数据元素的有限序列，其中n为表长，当n = 0时线性表是一个空表
若用L命名线性表，则其一般表示为L = (a1, a2, … , ai, ai+1, … , an)
a1是表头元素
an是表尾元素
除第一个元素外，每个元素有且仅有一个直接前驱
除最后一个元素外，每个元素有且仅有一个直接后继

基本操作：

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。
什么时候要传入参数的引用“&”：对参数的修改结果需要“带回来”，是引用类型而不是值类型

顺序表的定义

定义：

用顺序存储的方式实现线性表顺序存储，把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。

如何知道一个数据元素大小：

C语言sizeof(ElemType)

顺序表的实现-静态分配：

一篇学完：王道考研408数据结构（全）

如果“数组”存满了怎么办：

可以放弃治疗，顺序表的表长刚开始确定后就无法更改（存储空间是静态的），同时如果提前初始化太多的空间而不用，又会造成资源的浪费，因此动态分配应运而生。

动态申请和释放内存空间：

C：malloc、free函数
- L.data = (ElemType *) malloc (sizeof(ElemType) * InitSize);
- malloc函数返回一个指针，空间需要强制转型为你定义的数据元素类型指针
- malloc函数的参数，指明要分配多大的连续内存空间
C++： new、delete关键字

顺序表的实现-动态分配：

一篇学完：王道考研408数据结构（全）

顺序表的实现：

随机访问，即可以在O(1)时间内找到第i个元素。
存储密度高，每个结点只存储数据元素
拓展容量不方便（即便采用动态分配的方式实现，拓展长度的时间复杂度也比较高）
插入、删除操作不方便，需要移动大量元素

顺序表的插入、删除

顺序表的基本操作-插入：

一篇学完：王道考研408数据结构（全）

增加i的合法性判断：

一篇学完：王道考研408数据结构（全）

顺序表的基本操作-删除：

一篇学完：王道考研408数据结构（全）

插入和删除的时间复杂度：

最好时间复杂度= O(1)
最坏时间复杂度= O(n)
平均时间复杂度= O(n)

顺序表的查找

顺序表的按位查找：

一篇学完：王道考研408数据结构（全）

正是如此，在初始化顺序表时候malloc需要强制转换为与数据元素的数据类型相对应的指针
时间复杂度= O(1)
随机存取：由于顺序表的各个数据元素在内存中连续存放，因此可以根据起始地址和数据元素大小立即找到第i个元素，

顺序表的按值查找：

一篇学完：王道考研408数据结构（全）

结构类型的数据元素也能用 == 比较吗：不能！（C++可以用 == 的重载来实现）
更好的办法：定义一个函数
依次对比各个分量来判断两个结构体是否相等
最好时间复杂度= O(1)
最坏时间复杂度= O(n)
平均时间复杂度= O(n)

单链表的定义

顺序表：

每个结点中只存放数据元素
优点：可随机存取，存储密度高
缺点：要求大片连续空间，改变容量不方便

单链表：

每个结点除了存放数据元素外，还要存储指向下一个结点的指针
优点：不要求大片连续空间，改变容量方便
缺点：不可随机存取，要耗费一定空间存放指针

定义一个单链表：

typedef关键字：数据类型重命名
- typedef <数据类型> <别名>
- typedef struct LNode LNode;
- 之后可以用LNode代替struct LNode

一篇学完：王道考研408数据结构（全）

不带头结点的单链表：

一篇学完：王道考研408数据结构（全）

带头结点的单链表：

一篇学完：王道考研408数据结构（全）

区别：

不带头结点，写代码更麻烦
对第一个数据结点和后续数据结点的处理需要用不同的代码逻辑
对空表和非空表的处理需要用不同的代码逻辑
我们一般使用的都是带头结点的单链表

单链表的插入、删除

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

ListInsert(&L,i,e)：

插入操作，在表L中的第i个位置上插入指定元素e
找到第i-1个结点，将新结点插入其后
若带有头结点，插入更加方便，头结点可以看作“第0个”结点，直接做上面的操作即可

一篇学完：王道考研408数据结构（全）

若i插在表中则与插在表头一样进行操作，可以插入成功
若i插在表尾则s->next为NULL（在表的定义时规定的），可以插入成功
若i插在表外（i>Lengh）则p指针指向NULL（While循环一直指向p->next），不能插入成功
最好时间复杂度= O(1)
最坏时间复杂度= O(n)
平均时间复杂度= O(n)

按位序插入（不带头结点）：

ListInsert(&L,i,e)：

插入操作，在表L中的第i个位置上插入指定元素e
不存在“第0个”结点，因此i=1时需要特殊处理
找到第i-1个结点，将新结点插入其后

一篇学完：王道考研408数据结构（全）

若i!=1则处理方法和带头结点一模一样
值得注意的是int j =1而非带头结点的0（带头结点的头结点为第0个结点）
结论：不带头结点写代码更不方便，推荐用带头结点

指定结点的后插操作：

一篇学完：王道考研408数据结构（全）

这一段代码是按位序插入中插入的那一部分代码
也可以直接调用InsertNextNode来执行
封装代码，以此提高代码复用性，让代码更容易维护

指定结点的前插操作：

因为仅知道指定结点的信息和后继结点的指向，因此无法直接获取到前驱结点
方法1：获取头结点然后再一步步找到指定结点的前驱
方法2：将新结点先连上指定结点p的后继，接着指定结点p连上新结点s，将p中元素复制到s中，将p中元素覆盖为要插入的元素e

一篇学完：王道考研408数据结构（全）

（方法1）

一篇学完：王道考研408数据结构（全）

（方法2）

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

ListDelete(&L,i,&e)：

删除操作，删除表L中第i个位置的元素，并用e返回删除元素的值。
找到第i-1个结点，将其指针指向第i+1个结点，并释放第i个结点

一篇学完：王道考研408数据结构（全）

指定结点的删除：

删除结点p，需要修改其前驱结点的next指针，和指定结点的前插操作一样
方法1：传入头指针，循环寻找p的前驱结点
方法2：偷天换日，类似于结点前插的实现

一篇学完：王道考研408数据结构（全）

（方法2）

如果要删除的结点p是最后一个结点：

只能从表头开始依次寻找p的前驱，时间复杂度O(n)
这就体现了单链表的局限性：无法逆向检索，有时候不太方便

一篇学完：王道考研408数据结构（全）

单链表的查找

按位查找：

GetElem(L,i)：按位查找操作。获取表L中第i个位置的元素的值。
实际上单链表的插入中找到i-1部分就是按位查找i-1个结点，如下图

一篇学完：王道考研408数据结构（全）

因此查找第i个结点如下图

一篇学完：王道考研408数据结构（全）

如果i=0则直接不满足j<i则指针p直接返回头结点L
如果i超界则当时p指向了NULL，指针p返回NULL
平均时间复杂度：O(n)

按值查找：

LocateElem(L,e)：按值查找操作。在表L中查找具有给定关键字值的元素。

一篇学完：王道考研408数据结构（全）

能找到的情况：p指向了e值对应的元素，返回该元素
不能找到的情况：p指向了NULL，指针p返回NULL
平均时间复杂度：O(n)

求表的长度：

一篇学完：王道考研408数据结构（全）

平均时间复杂度：O(n)

单链表的建立

尾插法：

每次插入元素都插入到单链表的表尾
方法1：套用之前学过的位序插入，每次都要从头开始往后面遍历，时间复杂度为O(n^2)

一篇学完：王道考研408数据结构（全）

方法2：增加一个尾指针r，每次插入都让r指向新的表尾结点，时间复杂度为O(n)

一篇学完：王道考研408数据结构（全）

头插法：

每次插入元素都插入到单链表的表头
头插法和之前学过的单链表后插操作是一样的，可以直接套用
L->next=NULL;可以防止野指针

一篇学完：王道考研408数据结构（全）

总结：

头插法、尾插法：核心就是初始化操作、指定结点的后插操作
注意设置一个指向表尾结点的指针
头插法的重要应用：链表的逆置

双链表

为什么要要使用双链表：

单链表：无法逆向检索，有时候不太方便
双链表：可进可退，但是存储密度更低一丢丢

一篇学完：王道考研408数据结构（全）

双链表的初始化（带头结点）：

一篇学完：王道考研408数据结构（全）

双链表的插入：

一篇学完：王道考研408数据结构（全）

小心如果p结点为最后一个结点产生的空指针问题，因此循环链表应运而生（详见后面的循环链表插入删除）
注意指针的修改顺序

双链表的删除：

一篇学完：王道考研408数据结构（全）

双链表的遍历：

一篇学完：王道考研408数据结构（全）

循环链表

循环单链表与单链表的区别：

单链表：

表尾结点的next指针指向NULL
从一个结点出发只能找到后续的各个结点

循环单链表：

表尾结点的next指针指向头结点
从一个结点出发可以找到其他任何一个结点

循环单链表初始化：

一篇学完：王道考研408数据结构（全）

从头结点找到尾部，时间复杂度为O(n)
如果需要频繁的访问表头、表尾，可以让L指向表尾元素（插入、删除时可能需要修改L）
从尾部找到头部，时间复杂度为O(1)

循环双链表与双链表的区别：

双链表：

表头结点的prior指向NULL
表尾结点的next指向NULL

循环双链表：

表头结点的prior指向表尾结点
表尾结点的next指向头结点

循环双链表的初始化：

一篇学完：王道考研408数据结构（全）

循环链表的插入：

对于双链表来说如果p结点为最后一个结点，因为next结点为null，p->next->prior=s会产生的空指针问题
循环链表规避因为最后结点的next结点为头结点因此不会发生问题

一篇学完：王道考研408数据结构（全）

循环链表的删除：

与循环链表的插入相同。

一篇学完：王道考研408数据结构（全）

注意点：

写代码时候注意以下几点，以此规避错误：

如何判空
如何判断结点p是否是表尾/表头元素（后向/前向遍历的实现核心）
如何在表头、表中、表尾插入/删除一个结点

静态链表

什么是静态链表：

分配一整片连续的内存空间，各个结点集中安置
每个结点由两部分组成：data（数据元素）和next（游标）
0号结点充当“头结点”，不具体存放数据
游标为-1表示已经到达表尾
游标充当“指针”，表示下个结点的存放位置，下面举一个例子：
每个数据元素4B，每个游标4B（每个结点共8B），设起始地址为addr，e1的存放地址为addr + 8*2（游标值）

定义静态链表：

方法1：

一篇学完：王道考研408数据结构（全）

方法2：

一篇学完：王道考研408数据结构（全）

基本操作：

初始化：

把a[0]的next设为-1
把其他结点的next设为一个特殊值用来表示结点空闲，如-2

插入位序为i的结点：

找到一个空的结点，存入数据元素（设为一个特殊值用来表示结点空闲，如-2）
从头结点出发找到位序为i-1的结点
修改新结点的next
修改i-1号结点的next

删除某个结点：

从头结点出发找到前驱结点
修改前驱结点的游标
被删除结点next设为-2

总结：

静态链表：用数组的方式实现的链表
优点：增、删操作不需要大量移动元素
缺点：不能随机存取，只能从头结点开始依次往后查找；容量固定不可变
适用场景：①不支持指针的低级语言；②数据元素数量固定不变的场景（如操作系统的文件分配表FAT）

顺序表和链表的比较

逻辑结构：

都属于线性表，都是线性结构

存储结构：

顺序表：

优点：支持随机存取、存储密度高
缺点：大片连续空间分配不方便，改变容量不方便

链表：

优点：离散的小空间分配方便，改变容量方便
缺点：不可随机存取，存储密度低

基本操作：

顺序表：

创建
- 需要预分配大片连续空间。
- 若分配空间过小，则之后不方便拓展容量；
- 若分配空间过大，则浪费内存资源
- 静态分配：静态数组实现，容量不可改变
- 动态分配：动态数组（malloc、free）实现，容量可以改变但需要移动大量元素，时间代价高
销毁
- 修改Length = 0
- 静态分配：静态数组，系统自动回收空间
- 动态分配：动态数组（malloc、free），需要手动free
增删
- 插入/删除元素要将后续元素都后移/前移
- 时间复杂度O(n)，时间开销主要来自移动元素
- 若数据元素很大，则移动的时间代价很高
查
- 按位查找：O(1)
- 按值查找：O(n)若表内元素有序，可在O(log2n)时间内找到

链表：

创建
- 只需分配一个头结点（也可以不要头结点，只声明一个头指针），之后方便拓展
销毁
- 依次删除各个结点（free）
增删
- 插入/删除元素只需修改指针即可
- 时间复杂度O(n)，时间开销主要来自查找目标元素
- 查找元素的时间代价更低
查
- 按位查找：O(n)
- 按值查找：O(n)

用哪个：

表长难以预估、经常要增加/删除元素——链表
表长可预估、查询（搜索）操作较多——顺序表

开放式问题的解题思路：

问题：请描述顺序表和链表的bla bla bla…实现线性表时，用顺序表还是链表好？

答案：

顺序表和链表的逻辑结构都是线性结构，都属于线性表。
但是二者的存储结构不同，顺序表采用顺序存储…(特点，带来的优点缺点)；链表采用链式存储…（特点、导致的优缺点）。
由于采用不同的存储方式实现，因此基本操作的实现效率也不同。
当初始化时…；当插入一个数据元素时…；当删除一个数据元素时…；当查找一个数据元素时…

栈和队列

栈的基本概念

栈的定义：

栈（Stack）是只允许在一端进行插入或删除操作的线性表
逻辑结构：与普通线性表相同
数据的运算：插入、删除操作有区别
栈顶：允许插入和删除的一端，对应元素被称为栈顶元素
栈底：不允许插入和删除的一端，对应元素被称为栈底元素
特点：后进先出Last In First Out（LIFO）

栈的基本操作：

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。

出栈顺序数量：

n个不同元素进栈，出栈元素不同排列的个数为
上述公式称为卡特兰（Catalan）数，可采用数学归纳法证明

栈的顺序存储结构

顺序栈的定义和初始化：

一篇学完：王道考研408数据结构（全）

进栈操作：

一篇学完：王道考研408数据结构（全）

出栈操作：

一篇学完：王道考研408数据结构（全）

读取栈顶元素：

一篇学完：王道考研408数据结构（全）

注意：也可以让栈顶指针top先指向0，每次进栈S.top++，出栈--S.top

共享栈：

使用静态数组要求提前规定好栈的大小，容易造成内存资源的浪费因此共享栈应运而生
两个栈共享同一片空间，0、1号栈朝着同一方向进栈
栈满的条件：top0 + 1 == top1

一篇学完：王道考研408数据结构（全）

栈的链式存储结构

栈的链式存储实质：

进栈：头插法建立单链表，也就是对头结点的后插操作
出栈：单链表的删除操作，对头结点的“后删”操作
推荐使用不带头结点的链栈
创销增删查的操作参考链表

链栈的定义：

一篇学完：王道考研408数据结构（全）

队列的基本概念

队列的定义：

栈（Stack）是只允许在一端进行插入或删除操作的操作受限的线性表
队列（Queue）是只允许在一端进行插入，在另一端删除的线性表
队头：允许删除的一端，对应的元素被称为队头元素
队尾：允许插入的一端，对应的元素被称为队尾元素
队列的特点：先进先出First In First Out（FIFO）

队列的基本操作：

InitQueue(&Q)：初始化队列，构造一个空队列Q。
DestroyQueue(&Q)：销毁队列。销毁并释放队列Q所占用的内存空间。
EnQueue(&Q,x)：入队，若队列Q未满，将x加入，使之成为新的队尾。
DeQueue(&Q,&x)：出队，若队列Q非空，删除队头元素，并用x返回。
GetHead(Q,&x)：读队头元素，若队列Q非空，则将队头元素赋值给x。
QueueEmpty(Q)：判队列空，若队列Q为空返回true，否则返回false。

队列的顺序存储结构

队列的定义和初始化：

一篇学完：王道考研408数据结构（全）

入队操作：

一篇学完：王道考研408数据结构（全）

通过取余操作，只要队列不满，就可以一直利用之前已经出队了的空间，逻辑上实现了循环队列的操作
于是，队列已满的条件：队尾指针的再下一个位置是队头，即(Q.rear+1)%MaxSize==Q.front
代价：牺牲了一个存储单元，因为如果rear和front相同，与判空的条件相同了

出队操作：

一篇学完：王道考研408数据结构（全）

实际上获取队头元素的值就是出队操作去掉队头指针后移的代码

判断队列已满/已空：

方案1：

使用前面讲的牺牲一个存储空间的方式来解决
初始化时rear=front=0
队列元素个数：(rear+MaxSize-front)%MaxSize
队列已满的条件：队尾指针的再下一个位置是队头，即(Q.rear+1)%MaxSize==Q.front
队空条件：Q.rear==Q.front

方案2：

不牺牲一个存储空间，在结构体中多建立一个变量size
初始化时rear=front=0；size = 0;
队列元素个数= size
插入成功size++；删除成功size--;
此时队满条件：size==MaxSize
队空条件：size == 0;

方案3：

不牺牲一个存储空间，在结构体中多建立一个变量tag
初始化时rear=front=0；tag = 0;
因为只有删除操作，才可能导致队空，只有插入操作，才可能导致队满因此
每次删除操作成功时，都令tag=0；
每次插入操作成功时，都令tag=1；
队满条件：front==rear && tag == 1
队空条件：front==rear && tag == 0
队列元素个数：(rear+MaxSize-front)%MaxSize

队列的链式存储结构

初始化（带头结点）：

一篇学完：王道考研408数据结构（全）

初始化（不带头结点）：

一篇学完：王道考研408数据结构（全）

入队（带头结点）：

一篇学完：王道考研408数据结构（全）

入队（不带头结点）：

一篇学完：王道考研408数据结构（全）

出队（带头结点）：

一篇学完：王道考研408数据结构（全）

出队（不带头结点）：

一篇学完：王道考研408数据结构（全）

队列满的条件：

顺序存储：预分配的空间耗尽时队满
链式存储：一般不会队满，除非内存不足
因此一般不用考虑队满

双端队列

定义：

双端队列：只允许从两端插入、两端删除的线性表
输入受限的双端队列：只允许从一端插入、两端删除的线性表
输出受限的双端队列：只允许从两端插入、一端删除的线性表
不管是怎么样的双端队列实际都是栈和队列的变种

考点：

判断输出序列合法性
在栈中合法的输出序列，在双端队列中必定合法

栈在括号匹配中的应用

括号匹配问题：

一篇学完：王道考研408数据结构（全）

若有括号无法被匹配则出现编译错误
遇到左括号就入栈
遇到右括号，就“消耗”一个左括号

代码实现：

一篇学完：王道考研408数据结构（全）

栈在表达式求值中的应用

算数表达式：

由三个部分组成：操作数、运算符、界限符
我们平时写的算术表达式都是中缀表达式
如何可以不用界限符也能无歧义地表达运算顺序
Reverse Polish notation（逆波兰表达式=后缀表达式）
Polish notation（波兰表达式=前缀表达式）

中缀、后缀、前缀表达式：

一篇学完：王道考研408数据结构（全）

中缀转后缀的方法（手算）：

确定中缀表达式中各个运算符的运算顺序
选择下一个运算符，按照「左操作数右操作数运算符」的方式组合成一个新的操作数
如果还有运算符没被处理，就继续第二步
注意：运算顺序不唯一，因此对应的后缀表达式也不唯一
“左优先”原则：只要左边的运算符能先计算，就优先算左边的，保证手算和机算是一致的

一篇学完：王道考研408数据结构（全）

中缀表达式转后缀表达式（机算，用栈实现）：

初始化一个栈，用于保存暂时还不能确定运算顺序的运算符。
从左到右处理各个元素，直到末尾。可能遇到三种情况：
- 遇到操作数。直接加入后缀表达式。
- 遇到界限符。遇到“(”直接入栈；遇到“)”则依次弹出栈内运算符并加入后缀表达式，直到弹出“(”为止。注意：“(”不加入后缀表达式。
- 遇到运算符。依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，若碰到“(”或栈空则停止。之后再把当前运算符入栈。
按上述方法处理完所有字符后，将栈中剩余运算符依次弹出，并加入后缀表达式。

后缀表达式的计算（手算）：

从左往右扫描，每遇到一个运算符，就让运算符前面最近的两个操作数执行对应运算，合体为一个操作数
注意：两个操作数的左右顺序
特点：最后出现的操作数先被运算，LIFO（后进先出），可以使用栈来完成这个步骤
“左优先”原则：只要左边的运算符能先计算，就优先算左边的

后缀表达式的计算（机算，用栈实现）：

从左往右扫描下一个元素，直到处理完所有元素
若扫描到操作数则压入栈，并回到第一步；否则执行第三步
若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶，回到第一步
注意：先出栈的是“右操作数”
若表达式合法，则最后栈中只会留下一个元素，就是最终结果
后缀表达式适用于基于栈的编程语言（stack-orientedprogramming language），如：Forth、PostScript

中缀表达式转前缀表达式（手算）：

确定中缀表达式中各个运算符的运算顺序
选择下一个运算符，按照「运算符左操作数右操作数」的方式组合成一个新的操作数
如果还有运算符没被处理，就继续第二步
“右优先”原则：只要右边的运算符能先计算，就优先算右边的

中缀表达式的计算（机算，用栈实现）：

中缀表达式的计算=中缀转后缀+后缀表达式求值，两个算法的结合
用栈实现中缀表达式的计算：
- 初始化两个栈，操作数栈和运算符栈
- 若扫描到操作数，压入操作数栈
- 若扫描到运算符或界限符，则按照“中缀转后缀”相同的逻辑压入运算符栈（期间也会弹出运算符，每当弹出一个运算符时，就需要再弹出两个操作数栈的栈顶元素并执行相应运算，运算结果再压回操作数栈）

栈在递归中的应用

函数调用的特点：

最后被调用的函数最先执行结束（LIFO）
函数调用时，需要用一个栈（函数调用栈）存储，里面包含以下信息：
- 调用返回地址
- 实参
- 局部变量
适合用“递归”算法解决：可以把原始问题转换为属性相同，但规模较小的问题

栈在递归中的应用：

计算正整数的阶乘n!
求斐波那契数列
......

栈在递归中过程：

递归调用时，函数调用栈可称为“递归工作栈”
每进入一层递归，就将递归调用所需信息压入栈顶
每退出一层递归，就从栈顶弹出相应信息
缺点：
- 太多层递归可能会导致栈溢出
- 可能包含很多重复计算

队列的应用

树的层次遍历
图的广度优先遍历
操作系统中的应用
- 多个进程争抢着使用有限的系统资源时，FCFS（First Come First Service，先来先服务）是一种常用策略。可以用队列实现
- CPU资源的分配
- 打印数据缓冲区

特殊矩阵的压缩储存

一维数组的存储结构：

起始地址：LOC
各数组元素大小相同，且物理上连续存放。
数组元素a[i]的存放地址= LOC + i * sizeof(ElemType)

二维数组的存储结构：

分为行优先和列优先，本质就是把二维的逻辑视角转换为内存中的一维储存
M行N列的二维数组b[M][N]中，若按行优先存储，则b[i][j]的存储地址= LOC + (i*N + j) * sizeof(ElemType)
M行N列的二维数组b[M][N]中，若按列优先存储，则b[i][j]的存储地址= LOC + ( j*M+ i ) * sizeof(ElemType)
二维数组也有随机存储的特性

普通矩阵的存储：

可用二维数组存储
注意：描述矩阵元素时，行、列号通常从1开始；而描述数组时通常下标从0开始
某些特殊矩阵可以压缩存储空间（比如对称矩阵）

对称矩阵的压缩存储：

若n阶方阵中任意一个元素ai,j都有ai,j = aj,i则该矩阵为对称矩阵
普通存储：n*n二维数组
压缩存储策略：只存储主对角线+下三角区（或主对角线+上三角区），按行优先原则将各元素存入一维数组中
数组大小应为多少：(1+n)*n/2
站在程序员的角度，对称矩阵压缩存储后怎样才能方便使用：可以实现一个“映射”函数矩阵下标->一维数组下标
按行优先的原则，ai,j是第几个元素：

三角矩阵的压缩存储：

下三角矩阵：除了主对角线和下三角区，其余的元素都相同
上三角矩阵：除了主对角线和上三角区，其余的元素都相同
压缩存储策略：按行优先原则将橙色区元素存入一维数组中，并在最后一个位置存储常量c
下三角矩阵，按行优先的原则，ai,j是第几个元素：
上三角矩阵，按行优先的原则，ai,j是第几个元素：

三对角矩阵的压缩存储：

三对角矩阵，又称带状矩阵：当|i - j|>1时，有ai,j = 0 （1≤ i, j ≤n）
压缩存储策略：按行优先（或列优先）原则，只存储带状部分
按行优先的原则，ai,j是第几个元素：

稀疏矩阵的压缩存储：

稀疏矩阵：非零元素远远少于矩阵元素的个数
压缩存储策略1：顺序存储——三元组<i（行），j（列），v（值）>，失去了数组随机存储的特性
压缩存储策略2：链式存储，十字链表法

串

串的定义和基本操作

定义：

串，即字符串（String）是由零个或多个字符组成的有限序列。一般记为S = ‘a1a2······an' （n ≥0）
其中，S是串名，单引号括起来的字符序列是串的值；ai可以是字母、数字或其他字符；串中字符的个数n称为串的长度。n = 0时的串称为空串（用∅表示）。
有的地方用双引号（如Java、C），有的地方用单引号（如Python）
例如：S=”HelloWorld!”T=‘iPhone 11 Pro Max?’
子串：串中任意个连续的字符组成的子序列。Eg：’iPhone’，’Pro M’是串T的子串
主串：包含子串的串。Eg：T是子串’iPhone’的主串
字符在主串中的位置：字符在串中的序号。Eg：’1’在T中的位置是8(第一次出现)
子串在主串中的位置：子串的第一个字符在主串中的位置。Eg：’11 Pro’在T中的位置为8
每个空格字符占1B，不是空串
串的位序从1开始而不是从0开始
串是一种特殊的线性表，数据元素之间呈线性关系
串的数据对象限定为字符集（如中文字符、英文字符、数字字符、标点字符等）
串的基本操作，如增删改查等通常以子串为操作对象，因为人类的语言通常要多个字符组成的序列才有现实意义

串的基本操作：

假设有串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。
- 从第一个字符开始往后依次对比，先出现更大字符的串就更大
- 长串的前缀与短串相同时，长串更大
- 只有两个串完全相同时，才相等

字符集编码：

任何数据存到计算机中一定是二进制数。
需要确定一个字符和二进制数的对应规则这就是“编码”
“字符集”：英文字符，ASCII字符集，中英文，Unicode字符集
基于同一个字符集，可以有多种编码方案，如：UTF-8，UTF-16
注：采用不同的编码方式，每个字符所占空间不同，考研中只需默认每个字符占1B即可

串的储存结构

顺序存储：

一篇学完：王道考研408数据结构（全）

方案一：一个数组来储存字符，一个int变量length储存实际长度
方案二：数组的ch[0]来充当length，优点：字符的位序和数组下标相同
方案三：没有Length变量，以字符’\0’表示结尾（对应ASCII码的0），缺点：获取字符串长度需要遍历，时间复杂度高
方案四：数组的ch[0]废弃不用，从看开始储存字符，外加一个int变量length储存实际长度

链式存储：

一篇学完：王道考研408数据结构（全）

推荐使用第二种方式，存储密度较高，ch数组未必一定是4个字符，也可以比4多

基本操作的实现（使用第四种方案）：

一篇学完：王道考研408数据结构（全）

朴素模式匹配算法

字符串模式匹配：

在主串中找到与模式串相同的子串，并返回其所在位置。
子串：主串的一部分，一定存在
模式串：不一定能在主串中找到
要掌握朴素模式匹配算法、KMP算法两种方法

朴素模式匹配算法（两种实现方法）：

将主串中所有长度为m的子串依次与模式串对比，直到找到一个完全匹配的子串，或所有的子串都不匹配为止。
主串长度为n，模式串长度为 m，最多对比 n-m+1 个子串
上节讲的index定位操作就是朴素模式匹配算法中其中一种实现方法
也可以使用两个指针i和j来进行匹配。若当前子串匹配失败，则主串指针 i 指向下一个子串的第一个位置，模式串指针 j 回到模式串的第一个位置，即i = i - j + 2; j = 1;
若 j > T.length，则当前子串匹配成功，返回当前子串第一个字符的位置即i - T.length
设主串长度为 n，模式串长度为 m，则最坏时间复杂度 = O(n*m)，最好时间复杂度 = O(n)

KMP算法的概念

由D.E.Knuth，J.H.Morris和V.R.Pratt提出，因此称为 KMP算法
是对朴素模式匹配算法的优化
优化的原理就是减少了i指针的回溯，通过已经计算好的next指针，提高算法的整体运行效率
next数组记录了当第几个元素匹配失败时候，j的取值例如：
- 对于模式串 T = ‘abaabc’
- 当第6个元素匹配失败时，可令主串指针 i 不变，模式串指针 j=3
- 当第5个元素匹配失败时，可令主串指针 i 不变，模式串指针 j=2
- 当第4个元素匹配失败时，可令主串指针 i 不变，模式串指针 j=2
- 当第3个元素匹配失败时，可令主串指针 i 不变，模式串指针 j=1
- 当第2个元素匹配失败时，可令主串指针 i 不变，模式串指针 j=1
- 当第1个元素匹配失败时，匹配下一个相邻子串，令 j=0, i++, j++
next数组只和短短的模式串有关，和长长的主串无关（重要）
之所以只和模式串有关，是因为如果在哪里匹配失败，同时说明在这之前的部分主串和模式串是相同的
KMP算法，最坏时间复杂度 O(m+n)，其中，求 next 数组时间复杂度 O(m)，模式匹配过程最坏时间复杂度 O(n)
KMP算法精髓：利用好已经匹配过的模式串的信息

一篇学完：王道考研408数据结构（全）

步骤：
- 根据模式串T，求出 next 数组
利用next数组进行匹配（主串指针不回溯）

一篇学完：王道考研408数据结构（全）

KMP算法之求next数组

next数组的作用：

当模式串的第 j 个字符失配时，从模式串的第 next[j] 的继续往后匹配

next数组的求法：

任何模式串都一样，第1个字符不匹配时，只能匹配下一个子串，因此next[1]都无脑写 0（if(j==0) {i++; j++;}）
任何模式串都一样，第2个字符不匹配时，应尝试匹配模式串的第1个字符，因此next[2]都无脑写 1
每一个模式串不一样，对于第3个字符及之后的字符串，在不匹配的位置前边，划一根美丽的分界线模式串一步一步往后退，直到分界线之前“能对上”，此时 j 指向哪儿，next数组值就是多少

KMP算法之求nextval数组

定义：

nextval数组是对next数组的优化，用nextval替代next数组，减少了无意义的对比

nextval数组的求法：

先根据上面的方法算出next数组
先令nextval[1]=0
再根据下面代码算出后面的nextval数组

for(int j = 2; j <= T.length; j++)
{
    //让第next值个元素的值和当前元素比较
    if(T.ch[next[j]] == T.ch[j])
    {
        //若相等则让第next值个元素的nextval值复制给当前元素的nextval值
        nextval[j] = nextval[next[j]];
    }
    else
    {
        //若不等则让当前元素的next值赋值给当前元素的nextval值
        nextval[j] = next[j];
    }
}

树

树的定义和基本术语

空树：

结点数为0的树

非空树的特性：

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

树的定义：

树是n（n≥0）个结点的有限集合，n = 0时，称为空树，这是一种特殊情况。
在任意一棵非空树中应满足：
- 有且仅有一个特定的称为根的结点。
- 当n > 1时，其余结点可分为m（m > 0）个互不相交的有限集合T1, T2,…, Tm，其中每个集合本身又是一棵树，并且称为根结点的子树。

结点之间的关系描述：

什么是祖先结点？比自己深度低的结点
什么是子孙结点？比自己深度高的结点
什么是双亲结点（父结点）？自己的根结点
什么是孩子结点？自己作为根结点的儿子
什么是兄弟结点？与自己拥有相同父结点结点
什么是堂兄弟结点？与自己同一层的结点
什么是两个结点之间的路径？能从上往下前往的两个结点被称为有路径
什么是路径长度？经过几条边

结点、树的属性描述：

结点的层次（深度）：从上往下数，默认从1开始
结点的高度：从下往上数
树的高度（深度）：总共多少层
结点的度：有几个孩子（分支）
树的度：各结点的度的最大值

有序数和无序树：

有序树：逻辑上看，树中结点的各子树从左至右是有次序的，不能互换
无序树：逻辑上看，树中结点的各子树从左至右是无次序的，可以互换
是否是什么，具体看你用树存什么，是否需要用结点的左右位置反映某些逻辑关系

树和森林：

森林是m（m≥0）棵互不相交的树的集合
考点：树和森林的相互转换

树的性质

树的总结点数=树的总度数+1
度数为m的树和m叉树的区别
度为m的树第i 层至多有m^i-1 个结点（i≥1）
m叉树第i 层至多有m^i-1 个结点（i≥1）
高度为h的m叉树至多有((m^h)-1)/m-1个结点
高度为h的m叉树至少有h 个结点
高度为h、度为m的树至少有h+m-1 个结点
具有n个结点的m叉树的最小高度为logm(n(m - 1) + 1)
高度最小的情况：所有结点都有m个孩子

二叉树的定义和基本术语

定义：

二叉树是n（n≥0）个结点的有限集合
- 或者为空二叉树，即n = 0。
- 或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。
特点：
- 每个结点至多只有两棵子树
- 左右子树不能颠倒（二叉树是有序树）

二叉树的五种状态：

空二叉树
只有左子树
只有右子树
只有根结点
左右子树都有

几个特殊的二叉树：

满二叉树：一棵高度为h，且含有2^h - 1个结点的二叉树
- 特点：
  - 只有最后一层有叶子结点
  - 不存在度为1 的结点
  - 按层序从1 开始编号，结点i 的左孩子为2i，右孩子为2i+1；结点i 的父结点为𝑖/2 （如果有的话）
完全二叉树：当且仅当其每个结点都与高度为h的满二叉树中编号为1～n的结点一一对应时，称为完全二叉树
- 特点：
  - 只有最后两层可能有叶子结点
  - 最多只有一个度为1的结点
  - 按层序从1 开始编号，结点i 的左孩子为2i，右孩子为2i+1；结点i 的父结点为𝑖/2 （如果有的话）
  - i≤ n/2 为分支结点， i> n/2 为叶子结点
  - 如果某结点只有一个孩子，那么一定是左孩子
是满二叉树一定是完全二叉树，是完全二叉树不一定是满二叉树
二叉排序树：一棵二叉树或者是空二叉树，或者是具有如下性质的二叉树：
- 左子树上所有结点的关键字均小于根结点的关键字
- 右子树上所有结点的关键字均大于根结点的关键字
- 左子树和右子树又各是一棵二叉排序树
二叉排序树可用于元素的排序、搜索
平衡二叉树：树上任一结点的左子树和右子树的深度之差不超过1。
- 平衡二叉树能有更高的搜索效率
- 又宽又胖的树

各种二叉树的性质

二叉树的性质：

设非空二叉树中度为0、1和2的结点个数分别为n0、n1和n2，则n0 = n2 + 1（叶子结点比二分支结点多一个）
二叉树第i 层至多有2^(i-1)个结点（i≥1）
高度为h的2叉树至多有(2^h)-1个结点（满二叉树）

完全二叉树的性质：

具有n个（n>0）结点的完全二叉树的高度h为log2(n + 1) 或[log2n] + 1
对于完全二叉树，可以由的结点数n 推出度为0、1和2的结点个数为n0、n1和n2（突破点：完全二叉树最多只会有一个度为1的结点）

二叉树的储存结构

顺序存储：

一篇学完：王道考研408数据结构（全）

常用的基本操作：

i的左孩子：2i
i的右孩子：2i+1
i的父结点：⌊i/2⌋
i所在的层次：⌈log2(n+1)⌉或者⌊log2n⌋+1

若完全二叉树中共有n个结点，则：

判断i是否有左孩子：2i ≤ n ?
判断i是否有右孩子：2i+1 ≤ n ?
判断i是否是叶子/分支结点：i > ⌊n/2⌋ ?

储存非完全二叉树：

一篇学完：王道考研408数据结构（全）

二叉树的链式存储：

定义和初始化：

一篇学完：王道考研408数据结构（全）

这样的方法可以很简单的找到p结点的左右孩子，但是只能通过从根开始遍历查找找到结点p的父结点
可以通过多定一个父结点的指针来方便的查找父结点（三叉链表）

一篇学完：王道考研408数据结构（全）

n个结点的二叉链表共有n+1 个空链域（可以用来构建线索二叉树）

二叉树的先中后序遍历

遍历：

遍历：按照某种次序把所有结点都访问一遍
层序遍历：基于树的层次特性确定的次序规则
先/中/后序遍历：基于树的递归特性确定的次序规则

二叉树的遍历：

二叉树的递归特性：
- 要么是个空二叉树
- 要么就是由“根结点+左子树+右子树”组成的二叉树
先序遍历：根左右（NLR）
中序遍历：左根右（LNR）
后序遍历：左右根（LRN）

一篇学完：王道考研408数据结构（全）

先序遍历（代码）：

一篇学完：王道考研408数据结构（全）

中序遍历（代码）：

一篇学完：王道考研408数据结构（全）

后序遍历（代码）：

一篇学完：王道考研408数据结构（全）

二叉树遍历总结：

空间复杂度为O(h)，h为树的高度
每个结点都会被路过3次

求树的深度：

一篇学完：王道考研408数据结构（全）

是后序遍历的变种
先后访问左右儿子，得出对应深度返回左右儿子深度更高的那个就是树的深度

二叉树的层序遍历

层序遍历：

基于树的层次特性确定的次序规则

算法思想：

初始化一个辅助队列
根结点入队
若队列非空，则队头结点出队，访问该结点，并将其左、右孩子插入队尾（如果有的话）
重复第三步直至队列为空

代码实现：

一篇学完：王道考研408数据结构（全）

由遍历序列构造二叉树

结论：

一个前/中/后/层序遍历序列可能对应多种二叉树形态
只有至少同时拥有两种遍历序列才能确定二叉树的形态
结论：前序、后序、层序序列的两两组合无法唯一确定一科二叉树

通过两种遍历序列确定二叉树：

前序+中序：

一篇学完：王道考研408数据结构（全）

中序+后序：

一篇学完：王道考研408数据结构（全）

层序+中序：

一篇学完：王道考研408数据结构（全）

线索二叉树的概念

中序遍历的问题：

如何找到指定结点p在q 中序遍历序列中的前驱？
如何找到p的中序后继？
能否从一个指定结点开始中序遍历？
完成上述需求的思路：
- 从根结点出发，重新进行一次中序遍历，指针q记录当前访问的结点，指针pre记录上一个被访问的结点
- 当q == p时，pre为前驱
- 当pre == p时，q为后继
缺点：找前驱、后继很不方便；操作必须从根开始

中序线索二叉树：

一篇学完：王道考研408数据结构（全）

线索二叉树的存储结构：

一篇学完：王道考研408数据结构（全）

先/中/后序线索二叉树同理

三种线索二叉树的对比：

一篇学完：王道考研408数据结构（全）

二叉树的线索化

通过头结点找到中序前驱：

一篇学完：王道考研408数据结构（全）

中序二叉树线索化：

一篇学完：王道考研408数据结构（全）

先序二叉树线索化：

一篇学完：王道考研408数据结构（全）

由于先序遍历先遍历根结点然后再遍历左结点，若左孩子为空，通过线索化后会指回前驱结点（他的根结点）
这时在此访问左孩子时候会又访问回根结点，因此需要增加一个判断来确定左孩子不是真正的左孩子而是线索化后的前驱结点
因此PreThread函数需要优化为：

一篇学完：王道考研408数据结构（全）

后序二叉树线索化：

一篇学完：王道考研408数据结构（全）

在线索二叉树中找前驱后驱

中序线索二叉树找中序前驱后继：

在中序线索二叉树中找到指定结点*p的中序后继next
- 若p->rtag == 1，则next = p->rchild
- 若p->rtag == 0，说明p必定有右孩子，next = （p的右子树中最左下的结点）

一篇学完：王道考研408数据结构（全）

在中序线索二叉树中找到指定结点*p的中序前驱pre
- 若p->ltag == 1，则pre = p->lchild
- 若p->ltag == 0，说明p必定有左孩子，pre = （p的左子树中最右下的结点）

一篇学完：王道考研408数据结构（全）

先序线索二叉树找先序前驱后继：

在先序线索二叉树中找到指定结点*p的先序后继next
- 若p->rtag == 1，则next = p->rchild
- 若p->rtag == 0，说明p必定有右孩子
  - 若p有左孩子，则先序后继为左孩子
  - 若p没有左孩子，则先序后继为右孩子
在先序线索二叉树中找到指定结点*p的先序前驱pre
- 若p->ltag == 1，则pre = p->lchild
- 若p->ltag == 0，说明p必定有左孩子
  - 先序遍历中，左右子树中的结点只可能是根的后继，不可能是前驱
  - 方法1：用土办法从头开始先序遍历
  - 方法2：可以改用三叉链表以找到父结点

后序线索二叉树找后序前驱后继：

在后序线索二叉树中找到指定结点*p的后序前驱pre
- 若p->ltag == 1，则pre = p->lchild
- 若p->ltag == 0，说明p必有左孩子
  - 若p有右孩子，则后序前驱为右孩子
  - 若p没有右孩子，则后序前驱为左孩子
在后序线索二叉树中找到指定结点*p的后序后继next
- 若p->rtag == 1，则next = p->rchild
- 若p->rtag == 0，说明p必定有右孩子
  - 后序遍历中，左右子树中的结点只可能是根的前驱，不可能是后继
  - 方法1：用土办法从头开始先序遍历
  - 方法2：可以改用三叉链表以找到父结点

一篇学完：王道考研408数据结构（全）

树的储存结构

双亲表示法（顺序存储）：

每个结点中保存指向双亲的“指针”，data，parrent
根结点固定存储在0，-1表示没有双亲

一篇学完：王道考研408数据结构（全）

新增数据元素，无需按逻辑上的次序存储，只需说明新增元素的data，parrent即可
删除数据元素
- 方案1：把要删除的数据元素data设为空，parent设为-1
- 方案2：将数组尾部的数据元素覆盖要删除的数据元素
查询数据元素
- 优点：查指定结点的双亲很方便
- 缺点：查指定结点的孩子只能从头遍历

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

一篇学完：王道考研408数据结构（全）

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

一篇学完：王道考研408数据结构（全）

规则：

左指针指向第一个孩子
右指针指向自己的第一个兄弟

森林和二叉树的转换：

本质：用二叉链表存储森林
规则：
- 各个树的根结点视为兄弟关系
- 左指针指向第一个孩子
- 右指针指向自己的第一个兄弟

树和森林的遍历

树的先根遍历：

先根遍历：若树非空，先访问根结点，再依次对每棵子树进行先根遍历。
树的先根遍历序列与这棵树相应二叉树的先序序列相同。

一篇学完：王道考研408数据结构（全）

树的后根遍历：

后根遍历：若树非空，先依次对每棵子树进行后根遍历，最后再访问根结点
树的后根遍历序列与这棵树相应二叉树的中序序列相同
也被称为深度优先遍历

一篇学完：王道考研408数据结构（全）

树的层次遍历：

用队列实现，又被称为广度优先遍历
步骤
- 若树非空，则根结点入队
- 若队列非空，队头元素出队并访问，同时将该元素的孩子依次入队
- 重复第二步直到队列为空

森林的先序遍历：

若森林为非空，则按如下规则进行遍历：
- 访问森林中第一棵树的根结点。
- 先序遍历第一棵树中根结点的子树森林。
- 先序遍历除去第一棵树之后剩余的树构成的森林。
效果等同于依次对各个树进行先根遍历
用孩子兄弟表示法转换为二叉树，效果等同于依次对二叉树的先序遍历

森林的中序遍历：

若森林为非空，则按如下规则进行遍历：
- 中序遍历森林中第一棵树的根结点的子树森林。
- 访问第一棵树的根结点。
- 中序遍历除去第一棵树之后剩余的树构成的森林。
效果等同于依次对各个树进行后根遍历
用孩子兄弟表示法转换为二叉树，效果等同于依次对二叉树的中序遍历

二叉排序树（BST）

定义：

二叉排序树，又称二叉查找树（BST，Binary Search Tree）
一棵二叉树或者是空二叉树，或者是具有如下性质的二叉树：
- 左子树上所有结点的关键字均小于根结点的关键字
- 右子树上所有结点的关键字均大于根结点的关键字
- 左子树和右子树又各是一棵二叉排序树
即左子树结点值< 根结点值< 右子树结点值
进行中序遍历，可以得到一个递增的有序序列
二叉排序树可用于元素的有序组织、搜索

BST的查找：

若树非空，目标值与根结点的值比较：
- 若相等，则查找成功
- 若小于根结点，则在左子树上查找，否则在右子树上查找。
- 查找成功，返回结点指针；
- 查找失败返回NULL
递归实现的最坏空间复杂度为O(h),普通实现的最坏空间复杂度为O(1)

一篇学完：王道考研408数据结构（全）

BST的插入：

若原二叉排序树为空，则直接插入结点；
否则，若关键字k小于根结点值，则插入到左子树，若关键字k大于根结点值，则插入到右子树
递归实现的最坏空间复杂度为O(h)

一篇学完：王道考研408数据结构（全）

二叉排序树的构造：

一篇学完：王道考研408数据结构（全）

注意：不同的关键字序列可能得到同款二叉排序树，也可能得到不同款二叉排序树

二叉排序树的删除：

先搜索找到目标结点：
- 若被删除结点z是叶结点，则直接删除，不会破坏二叉排序树的性质。
- 若结点z只有一棵左子树或右子树，则让z的子树成为z父结点的子树，替代z的位置。
- 若结点z有左、右两棵子树，则令z的直接后继（或直接前驱）替代z，然后从二叉排序树中删去这个直接后继（或直接前驱），这样就转换成了第一或第二种情况。
  - z的后继：z的右子树中最左下结点，是右子树最小的结点（该结点一定没有左子树）
  - z的前驱：z的左子树中最右下结点，是左子树中最大的结点（该结点一定没有右子树）

查找效率分析：

查找长度：在查找运算中，需要对比关键字的次数称为查找长度，反映了查找操作时间复杂度
查找成功的平均查找长度ASL（Average Search Length）：（各层（层数*层结点个数）相加）/总结点个数
最坏情况：每个结点只有一个分支，树高h=结点数n。平均查找长度=O(n)
最好情况：n个结点的二叉树最小高度为(log2n)+ 1。平均查找长度= O(log2n)

平衡二叉树（AVL）

定义：

平衡二叉树（Balanced Binary Tree），简称平衡树（AVL树）——树上任一结点的左子树和右子树的高度之差不超过1
结点的平衡因子=左子树高-右子树高
平衡二叉树结点的平衡因子的值只可能是−1、0或1
只要有任一结点的平衡因子绝对值大于1，就不是平衡二叉树

平衡二叉树的插入：

在二叉排序树中插入新结点后，如何保持平衡？
- 查找路径上的所有结点都有可能受到影响
- 从插入点往回找到第一个不平衡结点，调整以该结点为根的子树
- 每次调整的对象都是“最小不平衡子树”
- 在插入操作中，只要将最小不平衡子树调整平衡，则其他祖先结点都会恢复平衡
- 插入操作导致“最小不平衡子树”高度+1，经过调整后高度恢复
调整最小不平衡子树

一篇学完：王道考研408数据结构（全）

调整最小不平衡子树：

只有假设所有子树的高度都是H才能保证出现最小不平衡子树恒定
目标：
- 恢复平衡
- 保持二叉排序树特性
二叉排序树的特性：左子树结点值< 根结点值< 右子树结点值
LL平衡旋转（右单旋转）
- 由于在结点A的左孩子（L）的左子树（L）上插入了新结点，A的平衡因子由1增至2，导致以A为根的子树失去平衡，需要一次向右的旋转操作
- 将A的左孩子B向右上旋转代替A成为根结点，将A结点向右下旋转成为B的右子树的根结点，而B的原右子树则作为A结点的左子树

一篇学完：王道考研408数据结构（全）

RR平衡旋转（左单旋转）
- 由于在结点A的右孩子（R）的右子树（R）上插入了新结点，A的平衡因子由-1减至-2，导致以A为根的子树失去平衡，需要一次向左的旋转操作
- 将A的右孩子B向左上旋转代替A成为根结点，将A结点向左下旋转成为B的左子树的根结点，而B的原左子树则作为A结点的右子树

一篇学完：王道考研408数据结构（全）

右旋和左旋的代码实现思路

一篇学完：王道考研408数据结构（全）

LR平衡旋转（先左后右双旋转）
- 由于在A的左孩子（L）的右子树（R）上插入新结点，A的平衡因子由1增至2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先左旋转后右旋转
- 先将A结点的左孩子B的右子树的根结点C向左上旋转提升到B结点的位置，然后再把该C结点向右上旋转提升到A结点的位置

一篇学完：王道考研408数据结构（全）

RL平衡旋转（先右后左双旋转）
- 由于在A的右孩子（R）的左子树（L）上插入新结点，A的平衡因子由-1减至-2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先右旋转后左旋转
- 先将A结点的右孩子B的左子树的根结点C向右上旋转提升到B结点的位置，然后再把该C结点向左上旋转提升到A结点的位置

一篇学完：王道考研408数据结构（全）

查找效率分析：

若树高为h，则最坏情况下，查找一个关键字最多需要对比h次，即查找操作的时间复杂度不可能超过O(h)
平衡二叉树——树上任一结点的左子树和右子树的高度之差不超过1
假设以nh表示深度为h的平衡树中含有的最少结点数。
则有n0 = 0, n1 = 1, n2 = 2，并且有nh = n(h−1) + n(h−2) + 1
可以证明含有n个结点的平衡二叉树的最大深度为O(log2n) ，平衡二叉树的平均查找长度为O(log2n)

哈夫曼树

带权路径长度：

结点的权：有某种现实含义的数值（如：表示结点的重要性等）
结点的带权路径长度：从树的根到该结点的路径长度（经过的边数）与该结点上权值的乘积
树的带权路径长度：树中所有叶结点的带权路径长度之和（WPL, Weighted Path Length）

哈夫曼树的定义：

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

一篇学完：王道考研408数据结构（全）

哈夫曼树的构造：

给定n个权值分别为w1, w2,…, wn的结点，构造哈夫曼树的算法描述如下：
- 将这n个结点分别作为n棵仅含一个结点的二叉树，构成森林F。
- 构造一个新结点，从F中选取两棵根结点权值最小的树作为新结点的左、右子树，并且将新结点的权值置为左、右子树上根结点的权值之和。
- 从F中删除刚才选出的两棵树，同时将新得到的树加入F中。
- 重复步骤2和3，直至F中只剩下一棵树为止。
每个初始结点最终都成为叶结点，且权值越小的结点到根结点的路径长度越大
哈夫曼树的结点总数为2n − 1
哈夫曼树中不存在度为1的结点。
哈夫曼树并不唯一，但WPL必然相同且为最优

一篇学完：王道考研408数据结构（全）

哈夫曼编码：

固定长度编码：每个字符用相等长度的二进制位表示
可变长度编码：允许对不同字符用不等长的二进制位表示
若没有一个编码是另一个编码的前缀，则称这样的编码为前缀编码，如果没有前缀编码容易出现歧义
由哈夫曼树得到哈夫曼编码：字符集中的每个字符作为一个叶子结点，各个字符出现的频度作为结点的权值，根据之前介绍的方法构造哈夫曼树

并查集

定义：

并查集（Disjoint Set）是逻辑结构集合的一种具体实现，只进行“并”和“查”两种基本操作

并查集的基本操作：

Find：查操作，确定一个指定元素所属集合
Union：并操作，将两个不相交的集合合并为一个

初始化：

一篇学完：王道考研408数据结构（全）

S[]实际上就是树的双亲表示法，里面的值就是自己对应根结点的下标

并、查：

一篇学完：王道考研408数据结构（全）

时间复杂度分析：

Find操作最坏时间复杂度O(n)
Union操作时间复杂度O(1)

Union操作的优化：

在每次Union操作构建树的时候，尽量让树不长高
用根结点的绝对值表示树的结点总数（根结点从-1改成-（树的总结点））
Union操纵，让小树合并到大树
该方法构造的树高不超过[log2n]+1
Find最坏时间复杂度变为O(log2n)

一篇学完：王道考研408数据结构（全）

并查集的压缩路径

核心想法就是让树越来越“矮”
Find操作先找到根结点，再将查找路径上所有结点都挂到根结点下

一篇学完：王道考研408数据结构（全）

这样的操纵可以让树的告诉不超过O(α(n))
O(α(n))是一个增长很缓慢的函数，对于常见的n值，O(α(n))通常<=4
因此优化后的并查集Find、Union操作时间开销都很低

图

图的基本概念

定义：

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

有向图：

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

简单图、多重图：

数据结构课程只探讨“简单图”

简单图：

不存在重复边
不存在顶点到自身的边

多重图：

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

顶点的度、入度、出度：

对于无向图：
- 顶点v的度是指依附于该顶点的边的条数，记为TD(v)。
- 在具有n个顶点、e条边的无向图中，无向图的全部顶点的度的和等于边数的2倍
对于有向图：
- 入度是以顶点v为终点的有向边的数目，记为ID(v)；
- 出度是以顶点v为起点的有向边的数目，记为OD(v)。
- 顶点v的度等于其入度和出度之和，即TD(v) = ID(v) + OD(v)。

顶点-顶点的关系描述：

路径：顶点vp到顶点vq之间的一条路径是指顶点序列，
回路：第一个顶点和最后一个顶点相同的路径称为回路或环
简单路径：在路径序列中，顶点不重复出现的路径称为简单路径。
简单回路：除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。
路径长度：路径上边的数目
点到点的距离：从顶点u出发到顶点v的最短路径若存在，则此路径的长度称为从u到v的距离。若从u到v根本不存在路径，则记该距离为无穷（∞）。
无向图中，若从顶点v到顶点w有路径存在，则称v和w是连通的
有向图中，若从顶点v到顶点w和从顶点w到顶点v之间都有路径，则称这两个顶点是强连通的

连通图、强连通图：

若图G中任意两个顶点都是连通的，则称图G为连通图，否则称为非连通图。
对于n个顶点的无向图G，
- 若G是连通图，则最少有n-1条边
- 若G是非连通图，则最多可能有
  
  条边
若图中任何一对顶点都是强连通的，则称此图为强连通图。
对于n个顶点的有向图G，
若G是强连通图，则最少有n条边（形成回路）

研究图的局部——子图：

设有两个图G = (V, E)和G¢ = (V', E')，若V¢是V的子集，且E'是E的子集，则称G'是G的子图
若有满足V(G') = V(G)的子图G'，则称其为G的生成子图
注意：并非任意挑几个点、几条边都能构成子图

连通分量：

无向图中的极大联通子图称为连通分量
子图必须连通，且包含尽可能多的顶点和边

强连通分量：

有向图中的极大强联通子图成为有向图的强连通分量
子图必须强连通，同时保留尽可能多的边

生成树：

连通图的生成树是包含图中全部顶点的一个极小连通子图
边尽可能的少，但要保持连通
若图中顶点数为n，则它的生成树含有n-1条边。对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路。

生成森林：

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

边的权、带权图/网：

边的权：在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。
带权图/网——边上带有权值的图称为带权图，也称网。
带权路径长度——当图是带权图时，一条路径上所有边的权值之和，称为该路径的带权路径长度

几种特殊形态的图：

无向完全图：无向图中任意两个顶点之间都存在边
有向完全图：有向图中任意两个顶点之间都存在方向相反的两条弧
边数很少的图称为稀疏图
反之称为稠密图
没有绝对的界限，一般来说|E| < |V|log|V|时，可以将G视为稀疏图
树：不存在回路，且连通的无向图
有向树：一个顶点的入度为0、其余顶点的入度均为1的有向图，称为有向树
- n个顶点的树，必有n-1条边。
- n个顶点的图，若|E|>n-1，则一定有回路

邻接矩阵法

定义：

一篇学完：王道考研408数据结构（全）

无向图：
- 第i个结点的度=第i行（或第i列）的非零元素个数
有向图：
- 第i个结点的出度=第i行的非零元素个数
- 第i个结点的入度=第i列的非零元素个数
- 第i个结点的度=第i行、第i列的非零元素个数之和
邻接矩阵法求顶点的度/出度/入度的时间复杂度为O(|V|)

邻接矩阵法存储带权图（网）：

一篇学完：王道考研408数据结构（全）

邻接矩阵法的性能分析：

空间复杂度：O(|V|^2) ——只和顶点数相关，和实际的边数无关
适合用于存储稠密图
无向图的邻接矩阵是对称矩阵，可以压缩存储（只存储上三角区/下三角区）

邻接矩阵法的性质：

一篇学完：王道考研408数据结构（全）

邻接表法

为什么要使用邻接表：

邻接矩阵是使用数组实现的顺序存储，空间复杂度高，不适合存储稀疏图
邻接表是顺序+链式存储

定义：

一篇学完：王道考研408数据结构（全）

其实这和树的孩子表示法是类似的，孩子表示法：顺序存储各个结点，每个结点中保存孩子链表头指针
边结点的数量是2|E|，整体空间复杂度为O(|V| + 2|E|)
边结点的数量是|E|，整体空间复杂度为O(|V| + |E|)
只要确定了顶点编号，图的邻接矩阵表示方式唯一，图的邻接表表示方式并不唯一

邻接矩阵和邻接表的对比：

一篇学完：王道考研408数据结构（全）

十字链表、邻接多重表

关系：

十字链表储存有向图
邻接多重表储存无向图

十字链表存储有向图：

一篇学完：王道考研408数据结构（全）

空间复杂度：O(|V|+|E|)
如何找到指定顶点的所有出边？顺着绿色线路找
如何找到指定顶点的所有入边？顺着橙色线路找

邻接矩阵、邻接表存储无向图：

邻接表每条边对应两份冗余信息，删除顶点、删除边等操作时间复杂度高
临接矩阵空间复杂度高O(|V|2)

临接多重表储存无向图：

一篇学完：王道考研408数据结构（全）

空间复杂度：O(|V|+|E|)
删除边、删除结点等操作很方便，只需要让各指针指向下一个对应的指向即可

总结：

一篇学完：王道考研408数据结构（全）

图的基本操作

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>存在，则从图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。
注意：上面的操作都只针对邻接矩阵和邻接表

图的广度优先遍历（BFS）

树和图的广度优先遍历：

树的广度优先遍历：通过根结点，可以找到下一层的结点2，3，4.通过234又可以找到再下一层的结点5678
- 若树非空，则根结点入队
- 若队列非空，队头元素出队并访问，同时将该元素的孩字依次入队
- 重复第二步直到队列为空
图的广度优先遍历类似于树的广度优先遍历（层序遍历）
区别：
- 树不存在“回路”，搜索相邻的结点时，不可能搜到已经访问过的结点
- 图搜索相邻的顶点时，有可能搜到已经访问过的顶点

代码实现：

找到与一个顶点相邻的所有顶点
- FirstNeighbor(G,x)：求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点或图中不存在x，则返回-1。
- NextNeighbor(G,x,y)：假设图G中顶点y是顶点x的一个邻接点，返回除y之外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1。
- 使用上面两个基本操作
标记哪些顶点被访问过
- 都初始化为false
需要一个辅助队列

一篇学完：王道考研408数据结构（全）

遍历序列的可变性：

同一个图的邻接矩阵表示方式唯一，因此广度优先遍历序列唯一
同一个图邻接表表示方式不唯一，因此广度优先遍历序列不唯一

算法存在的问题和解决方案：

如果是非连通图，则无法遍历完所有结点

一篇学完：王道考研408数据结构（全）

空间复杂度：最坏情况，辅助队列大小为 O(|V|)
邻接矩阵存储的图：
- 访问 |V| 个顶点需要O(|V|)的时间
- 查找每个顶点的邻接点都需要O(|V|)的时间，而总共有|V|个顶点
- 时间复杂度= O(|V|^2)
邻接表存储的图：
- 访问 |V| 个顶点需要O(|V|)的时间
- 查找各个顶点的邻接点共需要O(|E|)的时间
- 时间复杂度= O(|V|+|E|)

广度优先生成树：

一篇学完：王道考研408数据结构（全）

广度优先生成树由广度优先遍历过程确定。
由于邻接表的表示方式不唯一，因此基于邻接表的广度优先生成树也不唯一
对非连通图的广度优先遍历，可得到广度优先生成森林

图的深度优先遍历（DFS）

树和图的深度优先遍历：

树的深度优先遍历（先根、后根）：
- 从根结点出发，能往更深处走就尽量往深处走。
- 每当访问一个结点的时候，要检查是否还有与当前结点相邻的且没有被访问过的结点，如果有的话就往下一层钻。
图的深度优先遍历类似于树的先根遍历。
图的深度优先遍历是递归实现的，广度优先办理是队列实现的

图的深度优先遍历：

一篇学完：王道考研408数据结构（全）

算法存在的问题和解决方案：

如果是非连通图，则无法遍历完所有结点

一篇学完：王道考研408数据结构（全）

复杂度分析：

空间复杂度：
- 来自函数调用栈，最坏情况，递归深度为O(|V|)
- 最好情况，O(1)
时间复杂度：
- 时间复杂度=访问各结点所需时间+探索各条边所需时间
- 邻接矩阵存储的图：
  - 访问 |V| 个顶点需要O(|V|)的时间
  - 查找每个顶点的邻接点都需要O(|V|)的时间，而总共有|V|个顶点
  - 时间复杂度= O(|V|^2)
- 邻接表存储的图：
  - 访问 |V| 个顶点需要O(|V|)的时间
  - 查找各个顶点的邻接点共需要O(|E|)的时间
  - 时间复杂度= O(|V|+|E|)

深度优先序列：

一篇学完：王道考研408数据结构（全）

和图的邻接表是一个原理，树中各个孩子结点在邻接表中出现的顺序是可变的
因此如果采用这种数据结构存储树，那么可能会有不同的遍历序列

深度优先生成树：

同一个图的邻接矩阵表示方式唯一，因此深度优先遍历序列唯一，深度优先生成树也唯一
同一个图邻接表表示方式不唯一，因此深度优先遍历序列不唯一，深度优先生成树也不唯一
对无向图进行BFS/DFS遍历

图的遍历与图的连通性：

调用BFS/DFS函数的次数=连通分量数
对于连通图，只需调用1次 BFS/DFS
对有向图进行BFS/DFS遍历
调用BFS/DFS函数的次数要具体问题具体分析，若起始顶点到其他各顶点都有路径，则只需调用1次BFS/DFS 函数
对于强连通图，从任一结点出发都只需调用1次 BFS/DFS

最小生成树

生成树：

连通图的生成树是包含图中全部顶点的一个极小连通子图。
若图中顶点数为n，则它的生成树含有n-1条边。对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路

最小生成树（最小代价树）：

对于一个带权连通无向图G = (V, E)，生成树不同，每棵树的权（即树中所有边上的权值之和）也可能不同
设R为G的所有生成树的集合，若T为R中边的权值之和最小的生成树，则T称为G的最小生成树（Minimum-Spanning-Tree, MST）
最小生成树可能有多个，但边的权值之和总是唯一且最小的
最小生成树的边数 = 顶点数 - 1
砍掉一条则不连通，增加一条边则会出现回路
如果一个连通图本身就是一棵树，则其最小生成树就是它本身
只有连通图才有生成树，非连通图只有生成森林

Prim 算法（普里姆）：

算法思想：

从某一个顶点开始构建生成树；
每次将代价最小的新顶点纳入生成树，直到所有顶点都纳入为止。
时间复杂度：O(|V|^2)，适合用于边稠密图

数据结构：

一篇学完：王道考研408数据结构（全）

实现步骤：

从V0开始，总共需要 n-1 轮处理
循环遍历所有个结点，找到lowCost最低的，且还没加入树的顶点，isJoin对应结点标记为true
再次循环遍历，更新还没加入的各个顶点的lowCost值
重复上面步骤，直到所有结点都加入树，生成的树即为最小生成树

Kruskal 算法（克鲁斯卡尔）

算法思想：

每次选择一条权值最小的边，使这条边的两头连通（原本已经连通的就不选）
直到所有结点都连通
时间复杂度：O( |E|log2|E| )，适合用于边稀疏图

数据结构：

一篇学完：王道考研408数据结构（全）

让各条边按照权值顺序排序

实现步骤：

共执行 e 轮，每轮判断两个顶点是否属于同一集合
检查第e条边的两个顶点是否连通（是否属于同一个集合）
若不联通则连起来
若联通则不操作
重复上面的步骤直到所有边都被遍历过

最短路径问题之BFS算法

介绍：

无权图可以视为一种特殊的带权图，只是每条边的权值都为1
BFS一般只适用于无权图的最短路径问题

代码实现：

一篇学完：王道考研408数据结构（全）

d数组表示u到各个结点的最短路径
path数组表示该结点回到u结点的最短前驱结点
由此生成的生成树同时也反应了起点到任意结点的距离

最短路径问题之Dijkstra算法

BFS算法的局限性：

带权路径长度——当图是带权图时，一条路径上所有边的权值之和，称为该路径的带权路径长度
BFS算法求单源最短路径只适用于无权图，或所有边的权值都相同的图

算法思想：

一篇学完：王道考研408数据结构（全）

初始：从V0开始，初始化三个数组信息
循环遍历所有结点，找到还没确定最短路径，且dist 最小的顶点Vi，令final[i]=ture。
检查所有邻接自 Vi 的顶点，若其 final 值为false，则更新 dist 和 path 信息
重复上述步骤，知道所有结点的final都标记为true

代码实现思路：

初始：
- 若从V0开始，令 final[0]=ture; dist[0]=0; path[0]=-1。
n-1轮处理
- 循环遍历所有顶点，找到还没确定最短路径，且dist 最小的顶点Vi，令final[i]=ture。
- 并检查所有邻接自Vi 的顶点，对于邻接自Vi 的顶点 Vj ，若 final[j]==false 且 dist[i]+arcsi < dist[j]，则令 dist[j]=dist[i]+arcsi; path[j]=i。
- 注：arcsi表示Vi 到Vj 的弧的权值
时间复杂度：O(n2)即O(|V|2)

用于负权值带权图：

Dijkstra 算法不适用于有负权值的带权图

最短路径问题之Floyd算法

算法思想：

Floyd算法：求出每一对顶点之间的最短路径
使用动态规划思想，将问题的求解分为多个阶段
对于n个顶点的图G，求任意一对顶点 Vi —> Vj 之间的最短路径可分为如下几个阶段：
- 初始：不允许在其他顶点中转，最短路径是？
- 0：若允许在 V0 中转，最短路径是？
- 1：若允许在 V0、V1 中转，最短路径是？
- 2：若允许在 V0、V1、V2 中转，最短路径是？
- …
- n-1：若允许在 V0、V1、V2 …… Vn-1 中转，最短路径是？

实现步骤：

一篇学完：王道考研408数据结构（全）

代码实现：

一篇学完：王道考研408数据结构（全）

注意点：

Floyd算法可以用于负权图
Floyd 算法不能解决带有“负权回路”的图（有负权值的边组成回路），这种图有可能没有最短路径（每走一圈路径越小）

总结：

一篇学完：王道考研408数据结构（全）

有向无环图（DAG图）的描述表达式

定义：

若一个有向图中不存在环，则称为有向无环图，简称DAG图（Directed Acyclic Graph）

例子：

转换前：

一篇学完：王道考研408数据结构（全）

转换后：

一篇学完：王道考研408数据结构（全）

解题方法：

把各个操作数不重复地排成一排
标出各个运算符的生效顺序（先后顺序有点出入无所谓）
按顺序加入运算符，注意“分层”
从底向上逐层检查同层的运算符是否可以合体

拓扑排序

AOV网：

AOV网(Activity On Vertex NetWork，用顶点表示活动的网)
用DAG图（有向无环图）表示一个工程。顶点表示活动，有向边<Vi, Vj>表示活动Vi必须先于活动Vj进行

拓扑排序：

拓扑排序：在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序：
- 每个顶点出现且只出现一次。
- 若顶点A在序列中排在顶点B的前面，则在图中不存在从顶点B到顶点A的路径。
或定义为：
- 拓扑排序是对有向无环图的顶点的一种排序，它使得若存在一条从顶点A到顶点B的路径，则在排序中顶点B出现在顶点A的后面。
每个AOV网都有一个或多个拓扑排序序列。
简单来说拓扑排序就是找到做事的先后顺序
拓扑排序的实现：
- 从AOV网中选择一个没有前驱（入度为0）的顶点并输出。
- 从网中删除该顶点和所有以它为起点的有向边。
- 重复前面的步骤直到当前的AOV网为空或当前网中不存在无前驱的顶点为止。

代码实现：

一篇学完：王道考研408数据结构（全）

时间复杂度：O(|V|+|E|)
若采用邻接矩阵，则需O(|V|^2)

逆拓扑排序：

对一个AOV网，如果采用下列步骤进行排序，则称之为逆拓扑排序：
- 从AOV网中选择一个没有后继（出度为0）的顶点并输出。
- 从网中删除该顶点和所有以它为终点的有向边。
- 重复上面步骤直到当前的AOV网为空。
用邻接表实现会更简单一些
使用逆邻接表：邻接表的顶点对应储存的信息是指向该顶点的边的信息
使用深度优先算法实现逆拓扑排序，顶点输出的序列就是逆拓扑排序序列

一篇学完：王道考研408数据结构（全）

DFS实现逆拓扑排序：在顶点退栈前输出

关键路径

AOE网：

在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销（如完成活动所需的时间）
称之为用边表示活动的网络，简称AOE网 (Activity On Edge NetWork)
AOE网具有以下两个性质：
- 只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始；
- 只有在进入某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发生。
- 另外，有些活动是可以并行进行的

一篇学完：王道考研408数据结构（全）

关键路径：

从源点到汇点的有向路径可能有多条，所有路径中，具有最大路径长度的路径称为关键路径，而把关键路径上的活动称为关键活动
完成整个工程的最短时间就是关键路径的长度，若关键活动不能按时完成，则整个工程的完成时间就会延长
事件vk的最早发生时间ve(k)：决定了所有从vk开始的活动能够开工的最早时间
活动ai的最早开始时间e(i)：指该活动弧的起点所表示的事件的最早发生时间
事件vk的最迟发生时间vl(k)：它是指在不推迟整个工程完成的前提下，该事件最迟必须发生的时间。
活动ai的最迟开始时间l(i)：它是指该活动弧的终点所表示事件的最迟发生时间与该活动所需时间之差。
活动ai的时间余量d(i)=l(i)-e(i)，表示在不增加完成整个工程所需总时间的情况下，活动ai可以拖延的时间
若一个活动的时间余量为零，则说明该活动必须要如期完成，d(i)=0即l(i) = e(i)的活动ai是关键活动，
由关键活动组成的路径就是关键路径

求关键路径的步骤：

求所有事件的最早发生时间 ve( )
- 按拓扑排序序列，依次求各个顶点的 ve(k):
- ve(源点) = 0
- ve(k) = Max{ve(j) + Weight(vj, vk)}, vj为vk 的任意前驱
求所有事件的最迟发生时间 vl( )
- 按逆拓扑排序序列，依次求各个顶点的 vl(k):
- vl(汇点) = ve(汇点)
- vl(k) = Min{vl(j) - Weight(vk, vj)} , vj为vk的任意后继
求所有活动的最早发生时间 e( )
- 若边<vk, vj>表示活动ai，则有e(i) = ve(k)
求所有活动的最迟发生时间 l( )
- 若边<vk, vj>表示活动ai，则有l(i) = vl(j) - Weight(vk, vj)
求所有活动的时间余量 d( )
- d(i) = l(i) - e(i)
d(i)=0的活动就是关键活动, 由关键活动可得关键路径

关键活动、关键路径的特性：

若关键活动耗时增加，则整个工程的工期将增长
缩短关键活动的时间，可以缩短整个工程的工期
当缩短到一定程度时，关键活动可能会变成非关键活动
可能有多条关键路径，只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的。

查找

查找的基本概念

查找：在数据集合中寻找满足某种条件的数据元素的过程称为查找
查找表（查找结构）：用于查找的数据集合称为查找表，它由同一类型的数据元素（或记录）组成
关键字：数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的。

对查找表的常见操作：

查找符合条件的数据元素
- 静态查找表
- 仅关注查找速度即可
插入、删除某个数据元素
- 动态查找表
- 除了查找速度，也要关注插/删操作是否方便实现

查找算法的评价指标：

查找长度：在查找运算中，需要对比关键字的次数称为查找长度
平均查找长度（ASL, Average Search Length ）：所有查找过程中进行关键字的比较次数的平均值
ASL的数量级反应了查找算法的时间复杂度
评价一个查找算法的效率时，通常考虑查找成功、查找失败两种情况的ASL

一篇学完：王道考研408数据结构（全）

顺序查找

定义：

顺序查找，又叫“线性查找”，通常用于线性表。

算法思想：从头到尾依次往后找

顺序查找的实现：

一篇学完：王道考研408数据结构（全）

顺序查找的实现（哨兵）：

一篇学完：王道考研408数据结构（全）

优点：无需判断是否越界，效率更高

一篇学完：王道考研408数据结构（全）

顺序查找的优化（对有序表）：

一篇学完：王道考研408数据结构（全）

用查找判定树分析ASL：

一个成功结点的查找长度 = 自身所在层数
一个失败结点的查找长度 = 其父结点所在层数
默认情况下，各种失败情况或成功情况都等概率发生

顺序查找的优化（被查概率不相等）：

一篇学完：王道考研408数据结构（全）

折半查找

算法思想：

折半查找，又称“二分查找”，仅适用于有序的顺序表。

查找成功：

注意：下面的mid向下取整

一篇学完：王道考研408数据结构（全）

查找失败：

一篇学完：王道考研408数据结构（全）

代码实现：

一篇学完：王道考研408数据结构（全）

查找效率分析：

一篇学完：王道考研408数据结构（全）

折半查找判定树的构造：

如果当前low和high之间有偶数个元素，则 mid 分隔后，左半部分比右半部分少一个元素
如果当前low和high之间有奇数个元素，则 mid 分隔后，左右两部分元素个数相等
折半查找的判定树中,mid = [(low + high)/2]则对于任何一个结点，必有：右树结点数-左子树结点数=0或1
折半查找的判定树一定是平衡二叉树
折半查找的判定树中，只有最下面一层是不满的因此，元素个数为n时树高h = [log2(n + 1)]
判定树结点关键字：左<中<右，满足二叉排序树的定义
失败结点：n+1个（等于成功结点的空链域数量）
折半查找的时间复杂度 = O(log2n)

分块查找

算法思想：

一篇学完：王道考研408数据结构（全）

特点：块内无序、块间有序
分块查找，又称索引顺序查找，算法过程如下：
- 在索引表中确定待查记录所属的分块（可顺序、可折半）
- 在块内顺序查找

用折半查找查索引：

若查找目标与索引表值相同：

一篇学完：王道考研408数据结构（全）

若查找目标与索引值不同：

一篇学完：王道考研408数据结构（全）

若索引表中不包含目标关键字，则折半查找索引表最终停在 low>high，要在low所指分块中查找
原因：最终low左边一定小于目标关键字，high右边一定大于目标关键字。而分块存储的索引表中保存的是各个分块的最大关键字

查找失败的例子：

一篇学完：王道考研408数据结构（全）

查找效率分析：

一篇学完：王道考研408数据结构（全）

B树

m叉查找树：

实际上就是二叉查找树的拓展，结点多少有多少个分叉就是多少叉查找树
每个结点关键字的查找可以用顺序查找也可以用折半查找

一篇学完：王道考研408数据结构（全）

如何保证查找效率：

若每个结点内关键字太少，导致树变高，要查更多层结点，效率低
- 策略：m叉查找树中，规定除了根结点外，任何结点至少有⌈m/2⌉个分叉，即至少含有⌈m/2⌉ − 1 个关键字
- 为什么不能保证根结点至少有⌈m/2⌉个分叉：如果整个树只有1个元素，根结点只能有两个分叉
不够“平衡”，树会很高，要查很多层结点
- 策略：m叉查找树中，规定对于任何一个结点，其所有子树的高度都要相同。

B树的定义：

B树，又称多路平衡查找树，B树中所有结点的孩子个数的最大值称为B树的阶，通常用m表示。一棵m阶B树或为空树，或为满足如下特性的m叉树：
- 树中每个结点至多有m棵子树，即至多含有m-1个关键字。
- 若根结点不是终端结点，则至少有两棵子树。
- 除根结点外的所有非叶结点至少有⌈m/2⌉棵子树，即至少含有 ⌈m/2⌉-1个关键字。
- 所有非叶结点的结构如下：
  - 其中，Ki（i = 1, 2,…, n）为结点的关键字，且满足K1 < K2 <…< Kn；Pi（i = 0, 1,…, n）为指向子树根结点的指针，且指针Pi-1所指子树中所有结点的关键字均小于Ki，Pi所指子树中所有结点的关键字均大于Ki，n（⌈m/2⌉- 1≤n≤m - 1）为结点中关键字的个数。
- 所有的叶结点都出现在同一层次上，并且不带信息（可以视为外部结点或类似于折半查找判定树的查找失败结点，实际上这些结点不存在，指向这些结点的指针为空）。

B树的高度：

一篇学完：王道考研408数据结构（全）

最大高度的另一种推导方法：

一篇学完：王道考研408数据结构（全）

B树的插入删除

B树的插入：

新元素一定是插入到最底层“终端结点”，用“查找”来确定插入位置
在插入key后，若导致原结点关键字数超过上限，则从中间位置（⌈m/2⌉）将其中的关键字分为两部分
左部分包含的关键字放在原结点中，右部分包含的关键字放到新结点中，中间位置（⌈m/2⌉）的结点插入原结点的父结点
若此时导致其父结点的关键字个数也超过了上限，则继续进行这种分裂操作，直至这个过程传到根结点为止，进而导致B树高度增1。

B树的删除：

若被删除关键字在终端结点，则直接删除该关键字（要注意结点关键字个数是否低于下限 ⌈m/2⌉ − 1）
若被删除关键字在非终端结点，则用直接前驱或直接后继来替代被删除的关键字
- 直接前驱：当前关键字左侧指针所指子树中“最右下”的元素
- 直接后继：当前关键字右侧指针所指子树中“最左下”的元素
若被删除关键字所在结点删除前的关键字个数低于下限，且与此结点右（或左）兄弟结点的关键字个数还很宽裕，则需要调整该结点、右（或左）兄弟结点及其双亲结点（父子换位法）
- 当右兄弟很宽裕时，用当前结点的后继（比当前结点大一位）、后继的后继（比当前结点大两位）来填补空缺
- 当左兄弟很宽裕时，用当前结点的前驱（比当前结点小一位）、前驱的前驱（比当前结点小两位）来填补空缺
若被删除关键字所在结点删除前的关键字个数低于下限，且此时与该结点相邻的左、右兄弟结点的关键字个数均=⌈m/2⌉ − 1，则将关键字删除后与左（或右）兄弟结点及双亲结点中的关键字进行合并

B+树

定义和性质：

一篇学完：王道考研408数据结构（全）

一棵m阶的B+树需满足下列条件：

每个分支结点最多有m棵子树（孩子结点）。
非叶根结点至少有两棵子树，其他每个分支结点至少有⌈m/2⌉棵子树。
- 可以理解为：要追求“绝对平衡”，即所有子树高度要相同
结点的子树个数与关键字个数相等。
所有叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按大小顺序排列，并且相邻叶结点按大小顺序相互链接起来。
所有分支结点中仅包含它的各个子结点中关键字的最大值及指向其子结点的指针。

B+树的查找：

B+树中，无论查找成功与否，最终一定都要走到最下面一层结点，因为只有叶子结点才有关键字对应的记录

B+树和B树区别：

一篇学完：王道考研408数据结构（全）

典型应用：关系型数据库的“索引”（如MySQL）
在B+树中，非叶结点不含有该关键字对应记录的存储地址。
可以使一个磁盘块可以包含更多个关键字，使得B+树的阶更大，树高更矮，读磁盘次数更少，查找更快

散列（哈希）查找

定义：

散列表（Hash Table），又称哈希表
是一种数据结构，特点是：数据元素的关键字与其存储地址直接相关
通过哈希函数建立关键字和存储地址的联系
若不同的关键字通过散列函数映射到同一个值，则称它们为“同义词”
通过散列函数确定的位置已经存放了其他元素，则称这种情况为“冲突”

处理冲突的方法——拉链法：

一篇学完：王道考研408数据结构（全）

用拉链法（又称链接法、链地址法）处理“冲突”：把所有“同义词”存储在一个链表中
最理想情况：散列查找时间复杂度可到达O(1)
“冲突”越多，查找效率越低
实际上就是顺序表和链表的结合结合两者优点，比如顺序表的随机存取，然后用链表的解决冲突问题，又规避了顺序表的一系列缺点
在插入新元素时，保持关键字有序，可微微提高查找效率

常见的散列函数：

散列函数的设计目的：
- 让不同关键字的冲突尽可能的少
- 散列查找是典型的“用空间换时间”的算法，只要散列函数设计的合理，则散列表越长，冲突的概率越低。
除留余数法：H(key) = key % p
- 散列表表长为m，取一个不大于m但最接近或等于m的质数p
- 质数又称素数。指除了1和此整数自身外,不能被其他自然数整除的数
- 用质数取模，分布更均匀，冲突更少。参见《数论》
- 注意：散列函数的设计要结合实际的关键字分布特点来考虑，不要教条化
直接定址法： H(key) = key 或 H(key) = a*key + b
- 其中，a和b是常数。这种方法计算最简单，且不会产生冲突。它适合关键字的分布基本连续的情况，若关键字分布不连续，空位较多，则会造成存储空间的浪费。
- 例如：存储同一个班级的学生信息
数字分析法：选取数码分布较为均匀的若干位作为散列地址
- 设关键字是r进制数（如十进制数），而r个数码在各位上出现的频率不一定相同，可能在某些位上分布均匀一些，每种数码出现的机会均等；
- 而在某些位上分布不均匀，只有某几种数码经常出现，此时可选取数码分布较为均匀的若干位作为散列地址。这种方法适合于已知的关键字集合，若更换了关键字，则需要重新构造新的散列函数。
- 例如：以“手机号码”作为关键字设计散列函数
平方取中法：取关键字的平方值的中间几位作为散列地址。
- 具体取多少位要视实际情况而定。
- 这种方法得到的散列地址与关键字的每位都有关系，因此使得散列地址分布比较均匀，适用于关键字的每位取值都不够均匀或均小于散列地址所需的位数。
- 例如：要存储整个学校的学生信息，以“身份证号”作为关键字设计散列函数

处理冲突的方法——开放定址法：

所谓开放定址法，是指可存放新表项的空闲地址既向它的同义词表项开放，又向它的非同义词表项开放。其数学递推公式为：
- Hi = (H(key) + di) % m
- i = 0, 1, 2,…, k（k≤m - 1），m表示散列表表长；di为增量序列；
- i 可理解为“第i次发生冲突”
线性探测法
- di = 0, 1, 2, 3, …, m-1；即发生冲突时，每次往后探测相邻的下一个单元是否为空，为空则可以插入数值
- 查找也是类似，先通过公式得到Hi再依次往后查找，若遇到空的位置则说明查找失败，所以越早遇到空位置，就可以越早确定查找失败
- 删除结点不能简单地将被删结点的空间置为空，否则将截断在它之后填入散列表的同义词结点的查找路径，可以做一个“删除标记”，进行逻辑删除
- 线性探测法由于冲突后再探测一定是放在某个连续的位置，很容易造成同义词、非同义词的“聚集（堆积）”现象，严重影响查找效率
平方探测法
- 当di = 0^2, 1^2, -1^2, 2^2, -2^2, …, k^2, -k^2时，称为平方探测法，又称二次探测法，其中k≤m/2
- 比起线性探测法更不易产生“聚集（堆积）”问题
- 注意：负数的模运算，(-3)%27 = 24，而不是3
- 模运算的规则：a MOD m == (a+km) MOD m , 其中，k为任意整数
- 散列表长度m必须是一个可以表示成4j + 3的素数，才能探测到所有位置
伪随机序列法
- di 是一个伪随机序列，如 di= 0, 5, 24, 11, …

处理冲突的方法——再散列法：

除了原始的散列函数 H(key) 之外，多准备几个散列函数
当散列函数冲突时，用下一个散列函数计算一个新地址，直到不冲突为止：
Hi = RHi(Key)
i=1,2,3….,k

排序

排序的基本概念

定义：

排序（Sort），就是重新排列表中的元素，使表中的元素满足按关键字有序的过程。
输入：n个记录R1, R2,…, Rn，对应的关键字为k1, k2,…, kn。
输出：输入序列的一个重排R1ʹ, R2ʹ,…, Rnʹ，使得有k1ʹ≤k2ʹ≤…≤knʹ（也可递减）

排序算法的评价指标：

时间复杂度
空间复杂度
算法的稳定性：
- 若待排序表中有两个元素Ri和Rj，其对应的关键字相同即keyi = keyj，且在排序前Ri在Rj的前面
- 若使用某一排序算法排序后，Ri仍然在Rj的前面
- 则称这个排序算法是稳定的，否则称排序算法是不稳定的。

排序算法的分类：

内部排序：数据都在内存中，关注如何使算法时、空复杂度更低
外部排序：数据太多，无法全部放入内存，还要关注如何使读/写磁盘次数更少

插入排序

算法思想：

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

代码实现：

一篇学完：王道考研408数据结构（全）

算法效率分析：

空间复杂度：O(1)
时间复杂度：主要来自对比关键字、移动元素，若有 n 个元素，则需要 n-1 趟处理
- 最好时间复杂度：O(n) 共n-1趟处理，每一趟只需要对比关键字1次，不用移动元素
- 最坏时间复杂度：O(n^2) 共n-1趟处理，每一趟都需要从尾移到到头（全部逆序）
算法稳定性：稳定

优化——折半插入排序：

思路：

先用折半查找找到应该插入的位置，再移动元素
当 low>high 时折半查找停止，应将 [low, i-1] 内的元素全部右移，并将 A[0] 复制到 low 所指位置
当 A[mid]==A[0] 时，为了保证算法的“稳定性”，应继续在 mid 所指位置右边寻找插入位置

代码实现：

一篇学完：王道考研408数据结构（全）

比起“直接插入排序”，比较关键字的次数减少了，但是移动元素的次数没变，整体来看时间复杂度依然是O(n^2)

对链表进行插入排序：

使用链表不需要对序列进行依次友谊，移动元素的次数变少了
但是关键字对比的次数依然是O(n^2) 数量级，整体来看时间复杂度依然是O(n^2)

希尔排序

算法思想：

先追求表中元素部分有序，再逐渐逼近全局有序
先将待排序表分割成若干形如 L[i, i + d, i + 2d,…, i + kd] 的“特殊”子表，对各个子表分别进行直接插入排序。缩小增量d，重复上述过程，直到d=1为止。

一篇学完：王道考研408数据结构（全）

代码实现：

一篇学完：王道考研408数据结构（全）

算法性能分析：

空间复杂度：O(1)
时间复杂度：
- 和增量序列 d1, d2, d3… 的选择有关，目前无法用数学手段证明确切的时间复杂度
- 最坏时间复杂度为 O(n^2)，当n在某个范围内时，可达O(n^1.3)
稳定性：不稳定
适用性：仅适用于顺序表，不适用于链表

冒泡排序

交换排序分类：

冒泡排序
选择排序

算法思想：

从后往前（或从前往后）两两比较相邻元素的值，若为逆序（即A[i-1]>A[i]），则交换它们，直到序列比较完
这样过程称为“一趟”冒泡排序
第n趟结束后，最小的n个元素会“冒”到最前边
若某一趟排序没有发生“交换”，说明此时已经整体有序。
可以从后往前冒泡，也可以冲前往后冒泡

代码实现：

一篇学完：王道考研408数据结构（全）

算法性能分析：

空间复杂度：O(1)
时间复杂度：
- 最好情况（有序）：O(n)
- 最坏情况（逆序）：O(n^2)
- 平均情况：O(n^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)上，这个过程称为一次“划分”
然后分别递归地对两个子表重复上述过程，直至每部分内只有一个元素或空为止，即所有元素放在了其最终位置上

代码实现：

一篇学完：王道考研408数据结构（全）

算法性能分析：

一篇学完：王道考研408数据结构（全）

n个结点的二叉树
- 最小高度 = ⌊log2n⌋ + 1
- 最大高度 = n
时间复杂度=O(n*递归层数)
- 最好时间复杂度=O(nlog2n)
  - 每次选的枢轴元素都能将序列划分成均匀的两部分
- 最坏时间复杂度=O(n^2)
  - 若序列原本就有序或逆序，则时、空复杂度最高（可优化，尽量选择可以把数据中分的枢轴元素。）
空间复杂度=O(递归层数)
- 最好空间复杂度=O(log2n)
- 最坏空间复杂度=O(n)
若每一次选中的“枢轴”将待排序序列划分为很不均匀的两个部分，则会导致递归深度增加，算法效率变低
若初始序列有序或逆序，则快速排序的性能最差（因为每次选择的都是最靠边的元素）
快速排序算法优化思路：尽量选择可以把数据中分的枢轴元素。
- 选头、中、尾三个位置的元素，取中间值作为枢轴元素；
- 随机选一个元素作为枢轴元素
快速排序是所有内部排序算法中平均性能最优的排序算法
稳定性：不稳定

简单选择排序

选择排序分类：

简单选择排序
堆排序

算法思想：

每一趟在待排序元素中选取关键字最小（或最大）的元素（每一趟待排序序列长度-1）加入有序子序列（每一趟有序序列长度+1）

代码实现：

一篇学完：王道考研408数据结构（全）

算法性能分析：

无论有序、逆序、还是乱序，一定需要 n-1 趟处理
总共需要对比关键字 (n-1)+(n-2)+…+1=[n(n-1)]/2次
元素交换次数 < n-1
空间复杂度：O(1)
时间复杂度=O(n^2)
稳定性：不稳定
适用性：既可以用于顺序表，也可用于链表

堆排序

堆的定义：

若n个关键字序列L[1…n] 满足下面某一条性质，则称为堆（Heap）：
- 若满足：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 ）则为小根堆（小顶堆）
  - 即完全二叉树中，任意根≤左、右

建立大根堆：

把所有非终端结点都检查一遍，是否满足大根堆的要求，如果不满足，则进行调整
- 在顺序存储的完全二叉树中，非终端结点编号 i≤⌊n/2⌋
- 检查当前结点是否满足根≥左、右，若不满足，将当前结点与更大的一个孩子互换
  - i的左孩子：2i
  - i的右孩子：2i+1
  - i的父结点：⌊i/2⌋
- 若元素互换破坏了下一级的堆，则采用相同的方法继续往下调整（小元素不断“下坠”）

建立大根堆（代码）：

一篇学完：王道考研408数据结构（全）

基于大根堆进行排序：

选择排序：每一趟在待排序元素中选取关键字最大的元素加入有序子序列
堆排序每一趟完成以下工作：
- 将堆顶元素（就是最大的元素）加入有序子序列（与待排序序列中的最后一个元素交换）
- 并将待排序元素序列再次调整为大根堆（小元素不断“下坠”）
注意：大根堆获得的排序序列是递增序列，小跟堆相反，获得的是递减序列

代码实现（大根堆排序）：

一篇学完：王道考研408数据结构（全）

堆排序的效率分析：

建堆的过程，关键字对比次数不超过4n，建堆时间复杂度=O(n)
堆排序的时间复杂度 =O(n) + O(nlog2n) = O(nlog2n)
堆排序的空间复杂度 =O(1)
稳定性：不稳定

堆的插入删除

基本操作：

i的左孩子：2i
i的右孩子：2i+1
i的父结点：⌊i/2⌋

在堆中插入新元素：

对于小根堆，新元素放到表尾，与父节点对比，若新元素比父节点更小，则将二者互换。
新元素就这样一路“上升”，直到无法继续上升为止

在堆中删除元素：

被删除的元素用堆底元素替代
然后让该元素不断“下坠”，直到无法下坠为止

关键字对比次数：

每次“上升”调整只需对比关键字1次
每次“下坠”调整可能需要对比关键字2次，也可能只需对比1次

归并排序

算法思想：

把两个或多个已经有序的序列合并成一个
对于两个有序序列，将i、j指针指向序列的表头，选择更小的一个放入k所指的位置
k++，i/j指向更小元素的指针++
只剩一个子表未合并时，可以将该表的剩余元素全部加到总表
m路归并：每选出一个小的元素，需要对比关键字m-1次
核心操作：把数组内的两个有序序列归并为一个

一篇学完：王道考研408数据结构（全）

代码实现：

一篇学完：王道考研408数据结构（全）

low是数组中第一个有序序列的开始
mid是数组中第一个有序序列的结尾
high是数组中第二个有序序列的结尾
辅助数组B临时存放这两段有序序列

算法效率分析：

2路归并的“归并树”形态上就是一棵倒立的二叉树
二叉树的第h层最多有2 ^ (h-1)个结点，若树高为h，则应满足n <= 2 ^ (h-1)，即h − 1 = ⌈log2n⌉
n个元素进行2路归并排序，归并趟数=⌈log2n⌉
每趟归并时间复杂度为O(n)，则算法时间复杂度O(nlog2n)
空间复杂度=O(n)，来自于辅助数组B
稳定性：稳定

基数排序

算法思想：

一篇学完：王道考研408数据结构（全）

基数排序得到递减序列的过程如下：

初始化：设置 r 个空队列，Qr-1, Qr-2,…, Q0
按照各个关键字位权重递增的次序（个、十、百），对 d 个关键字位分别做“分配”和“收集”
分配：顺序扫描各个元素，若当前处理的关键字位=x，则将元素插入 Qx 队尾
收集：把 Qr-1, Qr-2,…, Q0 各个队列中的结点依次出队并链接

基数排序得到递增序列的过程如下：

初始化：设置 r 个空队列，Q0, Q1,…, Qr−1
按照各个关键字位权重递增的次序（个、十、百），对 d 个关键字位分别做“分配”和“收集”
分配：顺序扫描各个元素，若当前处理的关键字位=x，则将元素插入 Qx 队尾
收集：把 Q0, Q1,…, Qr−1 各个队列中的结点依次出队并链接

算法效率分析：

需要r个辅助队列，空间复杂度 = O(r)
一趟分配O(n)，一趟收集O(r)，总共 d 趟分配、收集，总的时间复杂度=O(d(n+r)）
稳定性：稳定

基数排序的应用：

例如：
- 某学校有10000名学生，将学生信息按照年龄递减排序
- 给十亿人的身份证号排序
基数排序擅长解决的问题：
- 数据元素的关键字可以方便地拆分为 d 组，且 d 较小
- 每组关键字的取值范围不大，即 r 较小
- 数据元素个数 n 较大

外部排序

外存、内存的数据交换：

外存：
- 操作系统以“块”为单位对磁盘存储空间进行管理
- 如：每块大小 1KB各个磁盘块内存放着各种各样的数据
内存：
- 磁盘的读/写以“块”为单位
- 数据读入内存后才能被修改
- 修改完了还要写回磁盘

外部排序原理：

数据元素太多，无法一次全部读入内存进行排序
使用“归并排序”的方法，最少只需在内存或只能怪分配3块大小的缓冲区即可对任意一个大文件进行排序
”归并排序“要求各个子序列有序，每次读入两个块的内容，进行内部排序后写回磁盘

构造初始“归并段”：

一篇学完：王道考研408数据结构（全）

若有N个记录，内存工作区可以容纳L个记录，则初始归并段数量=r=N/L

第一趟归并：

一篇学完：王道考研408数据结构（全）

第二趟归并：

一篇学完：王道考研408数据结构（全）

第三趟归并：

一篇学完：王道考研408数据结构（全）

时间开销分析：

外部排序时间开销=读写外存的时间+内部排序所需时间+内部归并所需时间

优化思路：

多路归并
- 采用多路归并可以减少归并趟数，从而减少磁盘I/O(读写)次数
- 对 r 个初始归并段，做k路归并，则归并树可用 k 叉树表示，若树高为h，则归并趟数 = h-1 = ⌈logkr⌉
- 推导：k叉树第h层最多有k^(h−1) 个结点，则r ≤ kh−1， (h-1)最小 = ⌈logkr⌉
- k越大，r越小，归并趟数越少，读写磁盘次数越少
- 多路归并带来的负面影响：
  - k路归并时，需要开辟k个输入缓冲区，内存开销增加
  - 每挑选一个关键字需要对比关键字（k-1）次，内部归并所需时间增加（可使用败者树优化）
减少初始归并段数量
- 生成初始归并段的“内存工作区”越大，初始归并段越长

败者树

定义：

可视为一棵完全二叉树（多了一个头头）
k个叶结点分别是当前参加比较的元素，非叶子结点用来记忆左右子树中的“失败者”，而让胜者往上继续进行比较，一直到根结点。
即失败者留在这一回合，胜利者进入下一回合比拼

败者树在多路平衡归并中的应用：

一篇学完：王道考研408数据结构（全）

败者树的存储结构：

一篇学完：王道考研408数据结构（全）

置换-选择排序

使用置换-选择排序，可以让每个初始归并段的长度超过内存工作区大小的限制
设初始待排文件为FI，初始归并段输出文件为FO，内存工作区为WA，FO和WA的初始状态为空，WA可容纳w个记录。
置换-选择算法的步骤如下：
- 从FI输入w个记录到工作区WA。
- 从WA中选出其中关键字取最小值的记录，记为MINIMAX记录。
- 将MINIMAX记录输出到FO中去。
- 若FI不空，则从FI输入下一个记录到WA中。
- 从WA中所有关键字比MINIMAX记录的关键字大的记录中选出最小关键字记录，作为新的MINIMAX记录。
- 重复3）～5），直至在WA中选不出新的MINIMAX记录为止，由此得到一个初始归并段，输出一个归并段的结束标志到FO中去。
- 重复2）～6），直至WA为空。由此得到全部初始归并段。