导图社区 王道考研-数据结构
- 357
- 45
- 12
- 举报
王道考研-数据结构
计算机考研需要复习的内容非常的多，今天就带来学霸整理的王道考研的学习笔记，分享的就是数据结构的思维导图，还在为考研刷题苦恼的小伙伴，赶紧来试一试吧~
编辑于2022-10-18 17:34:34 江苏省
- 相似推荐
- 大纲
王道考研 数据结构学习笔记 ——学霸考研——
第一章 绪论
数据结构
数据结构的基本概念
数据
是信息的载体
是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合
数据元素
数据项
一个数据元素可由若干数据组成，数据项是构成数据元素的不可分割的最小单位
数据元素是数据的基本单位，通常作为一个整体进行考虑和处理
数据对象
具有相同性质的数据元素的集合，是数据的一个子集
数据结构
是相互之间存在一种或多种特定关系的数据元素的集合
同一个数据对象里的数据元素，可以组成不同的数据结构
不同的数据元素，可以组成相同的数据结构
数据类型
原子类型
bool类型
值的范围：true、false
可进行操作：与、或、非
int类型
值的范围：-2147483648 ~ 2147483647
可进⾏操作：加、减、乘、除、模运算
结构类型
struct结构体
抽象数据类型ADT
是抽象数据组织及与之相关的操作
定义一个ADT，就是在“定义”一种数据结构
数据结构三要素
1. 若采用顺序存储，则各个数据元素在物理上必须是连续的；若采用非顺序存储，则各个数据元素在物理上可以是离散的。
2. 数据的存储结构会影响存储空间分配的方便程度
3. 数据的存储结构会影响对数据运算的速度 (Eg：在b和d之间插入新元素c)
逻辑结构
线性结构（一对一）
一般线性表
受限线性表
栈
队列
串
线性表推广
数组
非线性结构
集合结构
各个元素同属一个集合，别无其他关系
树形结构（一对多）
一般树
二叉树
图状结构（多对多）
有向图
无向图
数据的运算
结合逻辑结构、实际需求来定义基本运算
存储结构（物理结构）
顺序存储
把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。
链式存储
索引存储
散列存储
非顺序存储
算法
什么是算法
程序=数据结构+算法
数据结构是要处理的信息
算法是处理信息的步骤
算法的五个特性
有穷性
有穷时间内能执行完
算法是有穷的
用有限步骤解决某个特定的问题
程序可以是无穷的
如：微信是程序，不是算法
确定性
相同输入只会产生相同输出
可行性
可以用已有的基本操作实现算法
输入
一个算法有零个或多个输入
丢给算法处理的结果
输出
一个算法有一个或多个输出
算法处理的结果
“好”好算法的特质
正确性
能正确解决问题
可读性
对算法的描述要让其他人也得看懂
健壮性
算法能处理一些异常状况
高效率与低存储量需求
即算法执行省时、省内存
时间复杂度低、空间复杂度低
效率的度量
时间复杂度
如何计算
1.找到一个基本操作（最深层循环）
2.分析该基本操作的执行次数x与问题规模n的关系x=f(n)
3.x的数量级O(x)就是算法时间复杂度T(n)
常用技巧
加法规则
多项相加，只保留最高阶的项，且系数变为1
乘法规则
多项相乘都保留
常对幂指阶
O(1) < O(log₂n) < O(n) < O(nlog₂n) < O(n²) <O(n³) < O(2ⁿ) < O(n!) < O(nⁿ)
三种复杂度
最坏时间复杂度
最坏情况下算法的时间复杂度
平均时间复杂度
所有输入示例等概率出现的情况下，算法的期望运行时间
最好时间复杂度
最好情况下算法的时间复杂度
空间复杂度
如何计算
普通程序
1.找到所占空间大小与问题规模相关的变量
2.分析所占空间x与问题规模n的关系x=f(n)
3.x的数量级O(n)就是算法空间的复杂度
递归程序
1.找到递归调用的深度x与问题规模n的关系x=f(n)
2.x的数量级O(n)就是算法空间复杂度S(n)
常用技巧
加法规则
T(n) = T₁(n) + T₂(n) = O(f(n)) + O(g(n)) = O(max(f(n), g(n)))
乘法规则
T(n) = T₁(n)×T₂(n) = O(f(n))×O(g(n)) = O(f(n)×g(n))
“常对幂指阶”
O(1) < O(log₂n) < O(n) < O(nlog₂n) < O(n²) <O(n³) < O(2ⁿ) < O(n!) < O(nⁿ)
第二章 线性表
定义（Linear List）
值得注意的特性
数据元素同类型、有限、有序
重要的术语
n为表长、当n=0时为空表
表头a₁、表尾aₙ
注意：位序从1开始数组下标从0开始
前驱、后继
除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继
数据元素的位序aᵢ（从1开始）
“逻辑结构”
a₁→ a₂→ a₃→ a₄→ a₅
基本操作
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语言函数的定义 —— <返回值类型> 函数名 (<参数1类型> 参数1，<参数2类型> 参数2，……)
③实际开发中，可根据实际需求定义其他的基本操作
④函数名和参数的形式、命名都可改变
函数命名要有可读性
什么时候要传入参数的引用“&”
对参数修改结果需要“带回来”
从无到有
增、删（"改"）
（“改”
判空、判长、打印输出（还可以自己根据实际需求增加其它基本操作）
线性表的实现
顺序存储
顺序表
链式存储
单链表
双链表
循环链表
静态链表（借助数组实现）
借助数组实现
线性表的应用
第二章 数据的表示和运算
数制与编码
进位计数制
常见进制
基数，每个数码位所用到的不同符号的个数，r进制的基数为r，逢r进1
十进制（D），二进制（B），八进制，十六进制（H，0x）
其他进制转为十进制
r进制数的数值=各数码位与位权的乘积之和
二进制，八进制，十六进制之间的相互转换
每三个二进制对应一个八进制位
每四个二进制位对应一个十六进制位
注意“补位”
十进制转为其他进制
整数部分
除基取余法：先取得的“余”是整数的低位
小数部分
乘基取整法：先取得的“整”是小数的高位
真值和机器数
真值：符合人类习惯的数字
机器数：数字实际存到机器里的形式，正负号需要被“数字化”
BCD码
8421码
每4个二进制位对应一个十进制位(有6个冗余状态)
8、4、2、1分别对应每一位的权值
0000~1001分别对应0~9，进行加法后若超出该范围，则需+0110进行修正(强制向高位进1)
余3码
8421码+(0011)
2421码
权值是2、4、2、1
2421码规定 0~4的第一位是0，5~9的第一位是1
无符号整数的表示和运算
无符号整数
全部二进制为都是数值位，没有符号位，第i位的位权是
n bit 无符号整数表示范围0~-1，超出即溢出，意味着该计算机无法一次处理这么多
可以表示的最小的数 全0，可以表示的最大的数 全1
计算机硬件如何做无符号整数的加法
从最低位开始，按位相加，并往更高位进位
计算机硬件如何做无符号整数的减法
“被减数”不变，“减数”全部位按位取反，末位+1，减法变加法
从最低位开始，按位相加，并往更高位进位
带符号整数的表示和运算
带符号整数的表示
原码
符号位“0/1”对应“正/负”，剩余的数值位表示真值的绝对值
若机器字长n+1位，带符号整数的原码表示范围：-(-1)≤x≤-1
真值0有两种表现形式
+0，[+0]=0,0000000；
-0，[-0]=1,0000000；
原码的缺点：符号位不能参与运算，需要设计复杂的硬件电路才能处理，费钱！贵！
补码
正数：补码和原码，反码一致
负数：反码的末位+1
更快速的方法（手算）
正数：不变
负数：从右往左找到第一个1，这个1左边的所有“数值位”按位取反
逆向转换，方法一样
补码的数值位不能解读为“位权”
反码
正数：反码和原码，补码一致
负数：原码的符号位不变，数值位取反
补码的加法运算
从最低位开始，按位相加（符号位参与运算）并往更高位进位，超出的部分舍弃
补码的减法运算
“被减数”不变，“减数”全部位按位取反、末位+1，减法变加法
从最低位开始，按位相加，并往最高位进位
原/反/补码的特性对比
常见考点
两个数A和B进行某种运算后，是否发生溢出？——手算做题可以带入十进制验证，是否超出合法范围
移码
补码的基础上，符号位取反
注意：移码只能用于表示整数
真值0只有一种表示形式 [0]=10000000
若机器字长n+1位，移码整数的表示范围：-2≤x≤2-1（与补码相同）
真值增大，移码增大
移码表示的整数很方便用于硬件串路比较大小
移码常用于浮点数阶码
定点小数的表示和运算
定点数
定点整数：带符号整数
定点小数
小数不可以用移码表示
表示方法，运算方法，各种码制的转换方式与整数相同
运算方法和运算电路
算数逻辑单元
ALU
实现算数运算、逻辑运算、辅助功能（移位、求补等)
基本结构：输入、输出、控制
电路基础知识
逻辑运算
与、或、非
与非、或非、异或、同或
门电路
最基础的逻辑元件,用于实现逻辑运算
逻辑表达式就是电路的数学化表示。根据逻辑运算的规则对逻辑表达式进行优化，也就是在优化电路
加法器的实现
一位全加器的设计
本位和
本位向高位的进位
串行加法器
一位全加器＋进位触发器，只能一位一位地加
串行进位的并行加法器
多个全加器简单串联,可多位同时加
计算速度取决于进位产生和传递的速度
回忆:各种门电路的图形，全加器的图形和输入输出信号
加法器、ALU的改进
串行进位的并行加法器
把n个全加器串接起来，就可进行两个n位数的相加。
如何更快的产生进位？
结论：第 i 位向更高位的进位 Ci可根据 被加数、加数的第 1~i 位, 再结合C0即可确定
并行加法器的优化
各级进位信号同时形成，又称为先行进位、同时进位
标志位的生成
OF（溢出标志）
有符号数的加减运算是否发生了溢出，OF=1时，说明发生了溢出
硬件的计算方法：OF=最高位产生的进位⊕次高位产生的进位
注意：OF位对无符号数的加减法无意义
SF（符号标志）
有符号数加减运算结果的正负性，SF=0表示运算结果为正数，SF=1表示运算结果为负数
硬件的计算方法：SF=最高位的本位和
注意：SF位对无符号数的加减法无意义
ZF（零标志）
表示运算结果是否为0.ZF=1表示运算结果为0，ZF=0表示运算结果非0
硬件的计算方法：两个数的运算结果为n bit，只有n bit全为0时，ZF=1
CF（进位/借位标志）
表示无符号数的加减法是否发生了进位或借位。当CF=1时，说明无符号数加减运算发生了进位或借位，也即发生了溢出
硬件的计算方法：CF=最高位产生的进位⊕sub
sub=1表示减法
sub=0表示加法
注意：CF位对有符号数的加减法无意义
仅对无符号数加减法有意义
仅对有符号数加减法有意义
定点数移位运算
通过改变各个数码位和小数点的相对位置，从而改变各数码位的位权
小数点后移1位相当于×10
小数点前移1位相当于÷10
算术移位
原码
符号位保持不变，仅对数值位进行移位
右移：高位补0，低位舍弃。若舍弃的位=0，则相当于÷2；若舍弃的位≠0，则会丢失精度
左移：低位补0，高位舍弃。若舍弃的位=0，则相当于×2；若舍弃的位≠0，则会出现严重误差
反码
正数：与原码相同
负数：
右移：高位补1，低位舍弃
左移：低位补1，高位舍弃
补码
正数：与原码相同
负数：
负数补码中，最右边的1及其右边同原码。最右边的1的左边同反码
右移：高位补1，低位舍弃
左移：低位补0，高位舍弃
逻辑移位
右移：高位补0，低位舍弃
左移：低位补0，高位舍弃
循环移位
不带进位位
用移出的位补上空缺
移出的位放到进位位
带进位位的循环左移
移出的位放到进位位
原进位位补上空缺
由于原、反、补码位数有限，因此某些时候算术移位不能精确等效乘法、除法
定点数的乘、除法运算
乘法运算
乘法运算的实现思想
原码的一位乘法
符号位单独处理：符号位=两个数符号位的异或
数值位取绝对值进行乘法计算
实现方法：先加法再移位，重复n次
机器实现原理
在正式进行乘法之前，ACC置0
判断MQ中，当前参与乘法的一个位
当前位=1，则ACC加上被乘数
当前位=0，则ACC加上0
算完一位后，将ACC和MQ逻辑右移一位
逻辑右移，高位补0
ACC的低位移到MQ
MQ原来的最低位用不到了，直接丢弃
重复第二步，直到MQ运算到乘数的符号位，乘数的符号位不参与计算
修改符号位为原两个符号位的异或
手算模拟
补码的一位乘法
补码乘法中使用“双符号位补码”
进行n轮加法、移位，最后再多来一次加法
在MQ增加了一位辅助位，根据MQ中的最低位和辅助位来确定加什么
手算模拟
除法运算
除法运算的思想
规律：忽略小数点，每确定一位商，进行一次减法，得到4位余数，在余数末尾补0，再确定下一位商。确定5位商即可停止（机器字长为5位）
原码除法：恢复余数法
符号位单独处理：符号位=两个数符号位的异或
数值位取绝对值进行乘法计算
实现方法：上商0/1，得到余数，余数末尾补0
机器实现原理
计算机很傻，会默认上商1，如果搞错了再改上商0，并“恢复余数”
首先上商1，让ACC与负除数的补码相加，如果此时符号位为1，说明搞错了，恢复余数
将ACC和MQ整体逻辑左移，ACC高位丢弃，MQ低位补0
重复上述步骤，直到MQ被商填满
余数是ACC剩下的数乘2
手算模拟
左移n次，上商n+1次，最后一次上商余数不左移
原码除法：加减交替法（不恢复余数法）
若余数为负，可直接商0，并让余数左移1位再加上|除数|，得到下一个新余数
若余数位正，则商1，让余数左移1位再减去|除数|，得到下一个新余数
手算模拟
余数的正负性与商相同
最后一步时若余数为负，需商0，并+[|y|]得到正确余数
加/减n+1次，每次加减确定一位商；左移n次（最后一次加减完不移位）最终可能还要再多一次加
补码除法：加减交替法
符号位参与运算
被除数/余数、除数采用双符号位
运算过程
最开始
被除数和除数同号，则被除数减去除数；
异号则被除数加上余数
余数和除数同号，商1，余数左移一位减去除数；
余数和除数异号，商0；余数左移一位加上除数；
重复n次
末位商恒置1
精度误差不超过2
浮点数的表示与运算
浮点数的表示
浮点数的作用和基本原理
阶码E反映浮点数的表示范围及小数点的实际位置
尾数M的数值部分的位数n反映浮点数的精度
阶码：常用补码或移码表示的定点整数
尾数：常用原码或补码表示的定点小数
浮点数规格化
规格化浮点数：规定尾数的最高数值位必须是一个有效值 。
左规：当浮点数运算的结果为非规格化时要进行规格化处理，
右规：当浮点数运算的结果尾数出现溢出（双符号为01或10）时，
注：采用“双符号位” ，当溢出发生时，可以挽救。更高的符号位是正确的符号位
规格化的原码尾数，最高数值位一定是1
规格化的补码尾数，符号位与最高数值位一定相反
浮点数的表示范围
IEEE754标准
阶码用移码表示
移码=真值+偏置值
令偏置值=127D，即2-1
浮点数的加减运算
加减运算
对阶
使两个数的阶码相等，小阶向大阶看齐，尾数每左移一位，阶码加1
求阶差
对阶
尾数加减
通常用双符号位，可以拯救溢出
规格化
左归
尾数最高数值位为无效位时，尾数左移，阶码减1
右归
尾数双符号位不同时，尾数右移，阶码加1
舍入
0舍1入法
在尾数右移时，被移去的最高数值位为0，则舍去
被移去的最高数值位为1，则在尾数的末位加1，这样做可能会使尾数又溢出，此时需再做一次右规
恒置1法
尾数右移时，不论丢掉的最高数值位是1还是0，都使右移的尾数末位横置1，这种方法同样有使尾数变大和变小的两种可能
溢出判断
阶码上溢
抛出异常(中断)
阶码下溢
按机器0处理
采用双符号位，可拯救尾数溢出
强制类型转换
char → int → long → double
float → double
int → float：可能会损失精度(float尾数的数值位有1+23位)
float → int：t可能会溢出，也可能会损失精度(如小数转整数)
精度从小到大，转换过程中没有损失
其余内容
C语言里的强制类型转换
C语言里的定点整数是用“补码”存储的
无符号数与有符号数：不改变数据内容，改变解释方式
长整数变短整数：高位截断，保留低位
短整数变长整数：符号扩展
数据的存储与排列
大小端模式
大端方式：高地址存最高有效字节，低地址存最低有效字节
小段方式：高地址存最低有效字节，低地址存最高有效字节
边界对齐
现代计算机通常是按字节编址，即每个字节对应一个地址
通常也支持按字，按半字，按字节寻址
第三章 栈和队列
栈(Stack)
定义
一种操作受限的线性表，只能在栈顶插入、删除
特性：先进后出（Last in first out,LIFO）
术语：栈顶、栈底、空栈
基本操作
创、销
增、删（元素进栈、出栈，只能在栈顶操作）
查(获得栈顶元素，但不删除）
判空
栈的顺序存储结构
顺序栈
顺序存储,用静态数组方式实现，并需要记录栈顶指针
基本操作
创（初始化）
增（进栈）
删（出栈）
查（获取栈顶元素）
判空、判满
都是O(1)时间复杂度
两种实现
初始化时 top = -1
入栈
出栈
获得栈顶元素
x=S.data[s.top] ;
栈空/栈满条件是?
栈空条件
S.top == -1;
栈满条件
S.top == MaxSize-1;
栈长
S.top + 1
初始化时 top = 0
入栈
出栈
获得栈顶元素
x=S.data[S.top-1];
栈空/栈满条件是?
栈空条件
S.top == 0;
栈满条件
S.top == MaxSize;
共享栈
两个栈共享同一片内存空间，两个栈从两边往中间增长
初始化
0号栈 栈顶指针初始化时 top1 = -1;
1号栈 栈顶指针初始化时 top1 = MaxSize;
栈满条件
top0 + 1 == top1;
栈的链式存储结构
用链式存储方式实现的栈
两中实现方式
带头结点
不带头结点
基本操作
创（初始化）
增（进栈）
删（出栈）
查（获取栈顶元素）
判空、判满
队列（Queue）
队列的基本概念
定义
一种操作受限的线性表，只能在队尾插入、在队头删除
特性：先进先出（first into first out,FIFO）
术语
队头、队尾、空队列、队头元素、队尾元素
基本操作
创、销
增、删（入队、出队，只能在规定的一端进行）
查（获得队头元素，但不删除）
判空
队列的顺序存储结构
用顺序存储实现队列
基本操作
创（初始化）
增（进队）
删（出队）
查（获取队头元素）
判空、判满（进行增/删/查操作前的必要判断）
循环队列
循环队列的操作
队列的链式存储结构
用链式存储实现队列
带头结点
不带头结点
基本操作
创（初始化）
增（进队）
注意一个元素入队
删（出队）
注意最后一个元素出队
查（获取队头元素）
判空、判满（进行增/删/查操作前的必要判断）
双端队列
双端队列
允许从两端插入、两端删除的队列
输入受限的双端队列
允许从两端删除、从另一端插入的队列
输出受限的双端队列
允许从两端插入、从另一端删除的队列
考点：对输出序列合法性的判断
栈和队列的应用
栈在括号匹配中的应用
用栈实现括号匹配：
依次扫描所有字符
遇到左括号入栈
遇到右括号则弹出栈顶元素检查是否匹配。
匹配失败情况：
①左括号单身
②右括号单身
③左右括号不匹配
栈在表达式求值中的应用
概念
运算符、操作数、界限符（DIY概念：左操作数/右操作数）
三种算数表达式
中缀表达式
运算符在操作树中间
后缀表达式（逆波兰式）
运算符在操作数后面
前缀表达式（波兰式）
运算符在操作数前面
后缀表达式相关考点
中缀表达式转后缀表达式
①按“左优先”原则确定运算符的运算次序
②根据①中确定的次序，依次将各个运算符和与之相邻的两个操作数按<左操作数 右操作数 运算符>的规则合体
后缀表达式求值
从左往右扫描，每遇到一个运算符，就将<左操作数 右操作数 运算符>变为<左操作数 运算符 右操作数>的形式
计算
从左往右扫描，遇到操作数入栈，遇到运算符则弹出两个栈顶元素运算后入栈（注意：先弹出的元素是“右操作数”）
前缀表达式相关考点
中缀表达式转前缀表达式
①按“右优先”原则确定运算符的运算次序
②根据①中确定的次序，依次将各个运算符和与之相邻的两个操作数按<运算符 右操作数 左操作数>的规则合体
前缀表达式求值（用栈实现）
从右往左扫描，遇到操作数入栈，遇到运算符则弹出两个栈顶元素运算后入栈（注意：先弹出的元素是“左操作数”）
栈在递归中的应用
函数调用的特点：
最后被调用的函数最先执行结束（LIFO）
函数调用时，需要用一个“函数调用栈” 存储：
递归调用时，函数调用栈可称为“递归工作栈”
缺点：效率低，太多层递归可能会导致栈溢出；可能包含很多重复计算
队列在遍历中的应用
树的层次遍历
图的广度优先遍历
队列在计算机系统中的应用
多个进程争抢着使用有限的系统资源时，FCFS（First Come First Service,先来先服务）是一种常用策略
矩阵的压缩存储
数组的存储结构
一维数组
二维数组
特殊矩阵
对称矩阵
特点：对方阵中的任意一个元素，有aᵢ,ⱼ=aⱼ,ᵢ
压缩：只存储主对角线+下三角区（或主对角线+上三角区）
三角矩阵
特点：上三角区全为常量（下三角矩阵）；或下三角区全为常量（上三角矩阵）
压缩：按行优先/列优先规则依次存储非常区域，并在最后一个位置存放常量c
三对角矩阵（带状矩阵）
特点：当|i-j|>1时，有aᵢ,ⱼ=0(1<=i,j<=n)
压缩：按行优先/列优先规则依次存储带状区域
稀疏矩阵
非零元素个数远小于零元素个数
压缩：只存储非零元素
顺序存储：顺序存储三元组<行，列，值>
链式存储：十字链表法
常见考题
矩阵的压缩存储需要多长的数组
由矩阵行列号<i,j>推出对应的数组下标号k
数列求和
由k推出<i,j>
如何处理不等式中的“刚好大于等于/小于等于”
向上取整/向下取整
易错点
存储上三角？下三角？
行优先？列优先
矩阵元素的下标从0？1？开始
数组下标从0？1？开始
第四章 串
串
定义
串，即字符串(String)是由零个或多个字符组成的有限序列
术语:串长、空串、空格串、子串、主串、字符在主串中的位置、子串在主串中的位置
串[VS]线性表
串的数据对象限定为字符集
串的基本操作大多以“子串”为操作对象
基本操作
lndex(S,T)，定位操作,找到串T在主串S中的位置
StrCompare(S,T):比较操作。若S>T，则返回值>0;若S=T，则返回值=0;若S<T，则返回值<0。
其他...
字符集编码
字符集
英文字符―—ASClI字符集
中英文―—Unicode字符集
每个字符在计算机中对应一个二进制数，比较字符的大小其实就是比较二进制数的大小
串的存储结构
顺序存储
静态数组
动态数组
malloc、free
链式存储
可让每个结点存多个字符，没有字符的位置用'#'或'\O'补足
王道教材采用静态数组
基于顺序存储实现基本操作
求子串: bool SubString(SString &Sub,SString S, int pos, int len)
串的比较:int StrCompare(SString S, SString T)
求串在主串中的位置:int Index(sString S, SString T)
串的模式匹配
朴素模式匹配算法
原理：暴力破解
算法思想
主串长度n,模式串长度m
将主串中所有长度为m的子串与模式串比对
找到第一个与模式串匹配的子串，并返回子串起始位置
若所有子串都不匹配，则返回0
最坏时间复杂度=O(nm)
KMP算法
不匹配的字符之前，一定是和模式串一致的
依赖于模式串，与主串没有关系
主要优点：主串指针不回溯
用一个next数组存储模式串指针
算法思想
根据模式串T，求出next数组
利用next数组进行匹配（主串指针不回溯）
对于每模式串 t 的每个元素 t j，都存在一个实数 k ，使得模式串 t 开头的 k 个字符（t 0 t 1…t k-1）依次与 t j 前面的 k（t j-k t j-k+1…t j-1，这里第一个字符 t j-k 最多从 t 1 开始，所以 k < j）个字符相同。如果这样的 k 有多个，则取最大的一个。模式串 t 中每个位置 j 的字符都有这种信息，采用 next 数组表示，即 next[ j ]=MAX{ k }
求next数组
next数组的作用：当模式串的第j个字符失配时，从模式串的第next[j]的继续向后匹配
next[1]无脑写0
next[2]无脑写1
其他next：在不匹配的位置前，划一根美丽的分界线
最坏时间复杂度=O(m+n)
KMP算法的优化
求nextval数组
先求next数组
若next数组所对应位置的字符和当前字符相等，将对应位置的next数组赋值到当前位置的nextval数组
子主题3
第五章 树与二叉树
树
基本概念
结点，根节点，分支结点，叶子结点，边，子树
空树：节点数为0的树
非空树的特性
有且仅有一个根节点
没有后继的结点称为叶子结点
有后继的结点称为分支结点
除了根节点外，任何一个结点都有且仅有一个前驱
树是一种递归定义的数据结构
基本术语
结点之间的关系描述
祖先结点/子孙结点
双亲结点（父节点）/孩子结点
兄弟结点/堂兄弟结点
两个节点之间的路径：只能从上往下
路径长度：路径上经过几条边
树的路径长度：从树根到每个结点的路径长度的总和
结点、树的属性描述
结点的层次（深度）：从上往下数
结点的高度：从下往上数
树的高度（深度）：总共多少层
结点的度：有几个孩子（分支）
非叶子节点的度>0
叶子结点的度=0
树的度：树中各结点的度的最大值
有序树，无序树
有序树：逻辑上看，树中节点的各子树从左至右是有次序的，不能互换
无序树：逻辑上看，树中节点的各子树从左至右是无次序的，可以互换
森林
森林是m（m≥0）棵互不相交的树的集合
树的常考性质
考点1
结点数=总度数+1
考点2
度为m的树
任意结点的度 ≤ m（最多m个孩子）
至少有一个结点度=m
一定是非空树
m叉树
任意结点的度 ≤ m（最多m个孩子）
允许所有结点的度都<m
可以是空树
考点3
度为m的树第i层至多有个结点（i ≥ 1）
m叉树的第i层至多有个结点（i ≥ 1）
考点4
高度为h的m叉树至多有个结点
高度为h的m叉树至少有h个结点
高度为h度为m的树至少有h+m-1个结点
考点5
具有n个结点的m叉树的最小高度为
树的存储结构
双亲表示法
每个结点中保存指向双亲的“指针”
根节点存储在0，-1表示没有双亲
新增数据元素无需按逻辑上的次序存储
优点：查指定结点的双亲很方便
缺点：查指定结点的孩子只能从头遍历
孩子表示法
顺序+链式存储
指针指向第一个孩子
优点︰找孩子方便
缺点:找父节点不方便
孩子兄弟表示法
用二叉链表存储树--左孩子右兄弟
孩子兄弟表示法存储的树，从存储视角来看形态上和二叉树类似
考点:树与二叉树的相互转换。本质就是用孩子兄弟表示法存储树
重要考点：树、森林与二叉树的转换
本质:用二叉链表存储森林--左孩子右兄弟
森林中各个树的根节点之间视为兄弟关系
树和森林的遍历
树的遍历
先根遍历
先根，后子树
树的先根遍历序列与这棵树相应二叉树的先序序列相同
后根遍历
先子树，后根
树的后根遍历序列与这棵树相应二叉树的中序序列相同
层序遍历（用队列实现）
广度优先遍历
深度优先遍历
森林的遍历
先序遍历
若森林为非空，则按如下规则进行遍历： 访问森林中第一棵树的根结点。 先序遍历第一棵树中根结点的子树森林。 先序遍历除去第一棵树之后剩余的树构成的森林。
效果等同于依次对各个树进行先根遍历
中序遍历
若森林为非空，则按如下规则进行遍历： 中序遍历森林中第一棵树的根结点的子树森林。 访问第一棵树的根结点。 中序遍历除去第一棵树之后剩余的树构成的森林。
效果等同于依次对各个树进行后根遍历
二叉树
基本概念
二叉树是n(n≥0)个结点的有限集合
或者为空二叉树，即n=0
或者由一个根结点和两个互不相交的被称作根的左子树和右子树组成。
特点
每个结点至多只有两棵子树
左右子树不能颠倒（二叉树是有序树）
二叉树是递归定义的数据结构
树转化为二叉树：左孩子，右兄弟
几种特殊的二叉树
满二叉树
一棵高度为h，且含有个结点的二叉树
特点
只有最后一层有叶子结点
不存在度为1的结点
按层序从1开始编号，结点i的左孩子为2i，右孩子为2i+1；结点i的父节点为i/2（如果存在的话）
完全二叉树
当且仅当其每个结点都与高度为h的满二叉树中编号为1-n的结点一一对应，称为完全二叉树
特点
只有最后两层可能有叶子结点
最多只有一个度为1的结点
按层序从1开始编号，结点i的左孩子为2i，右孩子为2i+1；结点i的父节点为[i/2]（如果存在的话）
i≤n/2为分支结点，i≥n/2为叶子结点
如果某个节点只有一个孩子，那这个孩子一定是左孩子
二叉排序树
左子树上所有结点的关键字均小于根节点的关键字；右节点上所有结点的关键字均大于根节点的关键字，左子树和右子树又各是一棵二叉排序树。
用于元素的排序，搜索
平衡二叉树
树上任一结点的左子树和右子树的深度之差不超过1
平衡二叉树能有更高的搜索效率
常见考点
考点1
设非空二叉树中度为0、1和2的结点个数分别为,和，则（叶子结点比二分支结点多一个）
考点2
二叉树第i层至多有个结点（i≥1）
考点3
高度为h的二叉树至多有个结点（满二叉树）
考点4
具有n个（n＞0）个结点的完全二叉树的高度h为[]或[]+1
编号为i的结点所在层次为[]或[]+1
考点5
对于完全二叉树，可以由结点数推出度为0，1和2的结点个数为,和
二叉树的存储结构
顺序存储
只适合存储完全二叉树
链式存储
n个结点的二叉链表共有n+1个空链域
二叉树的遍历
按照某种次序把所有节点都访问一遍
先序遍历
根左右
得到前缀表达式
中序遍历
左根右
得到中缀表达式（未加界限符）
后序遍历
左右根
得到后缀表达式
考点：求遍历序列
分支结点逐层展开法
从你的全世界路过法
先序——第一次路过时访问
中序——第二次路过时访问
后序——第三次路过时访问
脑补空结点，从根节点出发，画一条路： 如果左边还有没走的路，优先往左边走 走到路的尽头（空结点）就往回走 如果左边没路了，就往右边走 如果左、右都没路了，则往上面走
求树的深度
层次遍历
算法思想
初始化一个辅助队列
根节点入队
若队列非空，则队头结点出队，访问该结点，并将其左右孩子插入队尾（如果有的话）
重复上一步直至队列为空
由遍历序列构造二叉树
若只给出一个二叉树的前/中/后/层序遍历队列中的一种，不能唯一确定一棵二叉树
前序+中序遍历队列
后序+中序遍历队列
层序+中序遍历队列
前序、后序、层序
时间复杂度O(n)
线索二叉树
线索二叉树的作用
方便从一个指定结点出发，找到其前驱、后继；方便遍历
线索二叉树的存储结构
三种线索二叉树
先序线索二叉树——线索指向
中序线索二叉树——线索指向
后序线索二叉树——线索指向
几个概念
线索
指向前驱/后继的指针称为线索
中序前驱/中序后继;先序前驱/先序后继;后序前驱/后序后继
手算画出线索二叉树
①确定线索二叉树类型——中序、先序、or后序?
②按照对应遍历规则，确定各个结点的访问顺序，并写上编号
③将n+1个空链域连上前驱、后继
二叉树的线索化
中序线索化-得到中序线索二叉树
先序线索化-得到先序线索二叉树
后序线索化-得到后序线索二叉树
核心
中序/先序/后序遍历算法的改造，当访问一个结点时，连接该结点与前驱结点的线索信息
用一个指针pre记录当前访问结点的前驱结点
易错点
最后一个结点的rchild . rtag的处理
先序线索化中，注意处理爱滴魔力转圈圈问题，当ltag==0时，才能对左子树先序线索化
找前驱，找后继
中序线索二叉树
前驱
p的左子树中最右下结点
后继
p的右子树中最左下结点
先序线索二叉树
前驱
①如果能找到p的父节点，且p是左孩子，则p的父节点为其前驱
②如果能找到p的父节点，且p是右孩子，其左兄弟为空，则p的父节点即为其前驱
③如果能找到p的父节点，且p是右孩子，其左兄弟非空，则p的前驱为其左兄弟子树最后一个被先序遍历的结点
④如果p是根节点，则p没有先序前驱
后驱
①若p有左孩子，则先序后继为左孩子
②若p没有左孩子，则先序后继为右孩子
后序线索二叉树
后继
①如果能找到p的父节点，且p是右孩子，p的父节点即为其后继
②如果能找到p 的父节点，且p是左孩子，其右兄弟为空，p的父节点即为其后继
③如果能找到p 的父节点，且p是左孩子，其右兄弟非空，则p的后继为其右兄弟子树中第一个被后序遍历的结点
④如果p是根节点，则p没有后序后继
前驱
①若p有右孩子，则后序前驱为右孩子
②回若p没有右孩子，则后序前驱为左孩子
二叉树在线索化之后，仍不能有效求解的问题：后续线索二叉树中求后序后继，仍需要栈的支持
哈夫曼树
带权路径长度
结点的权:某种特定含义的数值
结点的带权路径长度：从树的根到该结点的路径长度（经过的边数）与该结点上权值的乘积
树的带权路径长度（WPL）：树中所有叶结点的带权路径长度之和
哈夫曼树（最优二叉树）的定义
在含有n个带权叶结点的二叉树中，其中带权路径长度（WPL）最小的二叉树称为哈夫曼树，也称最优二叉树
哈夫曼树的构造
每次选两个根节点权值最小的树合并，并将二者权值之和作为新的根节点的权值
哈夫曼树的特点
每个初始结点最终都成叶结点，且权值最小的结点到根节点的路径长度越长
哈夫曼树的结点总数为2n-1（n为叶结点数，也为初始结点数）
哈夫曼树中不存在度为1的结点
哈夫曼树不唯一，但WPL必然相同且为最优
哈夫曼编码
固定长度编码——每个字符用相等长度的二进制位表示
可变长度编码——允许对不同字符用不等长的二进制位表示
前缀编码——没有一个编码是另一个编码的前缀
将字符频次作为字符结点权值，构造哈夫曼树，按照左0右1构造编码，即可得哈夫曼编码，可用于数据压缩
并查集
如何表示集合关系
算法思想
将各个元素划分为若干个互不相交的子集
把同一个集合里的元素组织成一棵树
如何查一个元素到底属于哪个集合？
从指定元素出发，一路向北，找到根节点
如何判断两个元素是否属于同一个集合？
对比两个元素的根节点是否相同
如何把两个集合并为一个集合？
让一棵树成为另一棵树的子树
并查集的代码实现
双亲表示法
初始化
初始化并查集，将所有数组元素初始化为-1
Find(S[],x)
查，找到元素x所属集合
时间复杂度O(n)
Union(S[],root1,root2)
并，将两个集合并为一个集合
时间复杂度O(1)
并查集的优化
用根节点的绝对值表示一棵树（集合）的结点总数
Union操作合并两棵树时，小树并到大树
优化后，Find操作的时间复杂度优化为O()
并查集的进一步优化
优化Find
压缩路径
每次Find操作先找到x所属根节点，再将查找路径上的所有结点都直接挂在根结点下面
第六章 图
图
基本概念
定义：G=(V,E),顶点集V,边集E
图不可以是空图
无向图（无向边）/有向图（有向边/弧）
对于无向图：顶点v的度指依附于该顶点的边的条数，记为TD(v)
对于有向图
入度是以顶点v为终点的有向边的数目，记为ID(v)
出度是以顶点v为起点的有向边的数目，记为OD(v)
顶点v的度等于其入度和出度之和TD(v)=ID(v)+OD(v)
简单图/多重图
路径：从一个顶点到另一个顶点的顶点序列
简单路径：在路径序列中，顶点不重复出现的路径称为简单路径
路径长度：路径上边的数目
回路（环）：第一个顶点和最后一个顶点相同的路径称为回路或环
简单回路：除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简答回路
点到点的距离：从顶点u出发到顶点v的最短路径若存在，则此路径的长度称为从u到v的距离，若从u到v根本不存在路径，则记该距离为无穷
无向图中，若从顶点v到顶点w有路径存在，则称v和w是连通的
若图中任意两个顶点都是连通的，则称图为连通图，否则称为非连通图
有向图中，若从顶点v到顶点w既有正向路径又有逆向路径，则称v和w是强连通的
若图中任何一对顶点都是强连通的，则称此图为强连通图
子图/生成子图（子图包括所有顶点）
连通分量：无向图中的极大连通子图（必须连通且包含尽可能多的边和顶点）
强连通分量：有向图中的极大强连通子图（必须强连通且保留尽可能多的边）
连通图的生成树是包含图中全部顶点的一个极小连通子图（边尽可能的少但要保持连通）
若生成树有n个顶点，则必有n-1条边
在非连通图中，连通分量的生成树构成了非连通图的生成森林
边的权：边上有意义的数值
带权图：边上有权值的图
带权路径长度：当图是带权图时，一条路径上所有边的权值之和
常见考点：
几种特殊的图
无向完全图：无向图中任意两个顶点之间都存在边
n个顶点对应条边
有向完全图：有向图中任意两个顶点之间都存在方向相反的两条弧
n个顶点对应条边
稀疏图/稠密图
树：不存在回路，且连通的无向图
n个顶点的树必有n-1条边
常见考点：n个顶点的图，若|E|>n-1，则图中一定存在回路
有向树：一个顶点的入度为0，其余顶点的入度均为1的有向图
有向树不是强连通图
常见考点
图的存储
邻接矩阵
无向图
第i个结点的度 = 第i行（或第i列）的非零元素个数
有向图
第i个结点的出度 = 第i行的非零元素个数
第i个结点的入度 = 第i列的非零元素个数
第i个结点的度 = 第i行、第i列的非零元素个数之和
带权图
设图G的邻接矩阵为A（矩阵元素为0/1），则的元素等于由顶点i到顶点j的长度为n的路径的数目
要点回顾
邻接表
图的邻接表表示方式并不唯一
十字链表
邻接多重表
图的基本操作
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）
与树的广度优先遍历之间的联系
树：不存在回路，搜索相邻的结点时，不可能搜到已经访问过的结点
搜索相邻的顶点时，有可能搜到已经访问过的结点
算法实现
需要一个辅助队列
如何从一个顶点找到与之邻接的其他顶点
visited数组防止重复访问
如何处理非连通图
如果是非连通图，则无法遍历完所有顶点
对于无向图，调用BFS函数的次数=连通分量数
复杂度分析
空间复杂度
辅助队列：
时间复杂度
访问结点的时间+访问所有边的时间
邻接矩阵存储的图：
邻接表存储的图：
广度优先生成树
根据广度优先遍历的过程得到，去掉没有被遍历的边，就生成了一棵树
基于邻接表的广度优先遍历序列和生成树不唯一
广度优先生成森林
便利非连通图
深度优先遍历（DFS）
与树的深度优先遍历之间的联系
递归地深入探索未被访问过的邻接点（类似于树的先根遍历的实现）
算法实现
如何从一个顶点找到与之邻接的其他顶点
visited数组防止重复访问
如何处理非连通图
如果是非连通图则无法访问所有结点
复杂度分析
空间复杂度
函数调用栈：
时间复杂度
访问各结点所需时间+探索各条边所需时间
邻接矩阵存储的图：
邻接表存储的图：
深度优先生成树
由深度优先遍历确定的树
基于邻接表的深度优先遍历序列和生成树不唯一
深度优先遍历非连通图可得深度优先生成森林
图的遍历和图的连通性
无向图
DFS/BFS函数调用次数=连通分量数
有向图
若从起始顶点到其他顶点都有路径，则只需调用1次DFS/BFS函数
对于强连通图，从任一顶点出发都只需调用1次DFS/BFS函数
图的应用
最小生成树（最小代价树）
最小生成树（MST）的概念
对于一个带权连通无向图，生成树不同，每棵树的权也可能不同。
如果一个连通图本身就是一棵树，则其最小连通生成树就是它自身
只有连通图才有生成树，非连通图只有生成森林
Prim算法
从某一个顶点开始构建生成树；每次将代价最小的新顶点纳入生成树，直到所有顶点都纳入为止。
时间复杂度：
适用于边稠密图
Kruskal算法
每次选择一条权值最小的边，使这条边的两头连通（原本已经连通的就不选）直到所有结点都连通
时间复杂度：
适用于边稀疏图
考代码概率不高
最短路径问题
单源最短路径
BFS算法（无权图）
就是对BFS的小修改，在visit一个顶点时，修改其最短路径长度d[]，并在path[]记录前驱节点
Dijkstra算法（带权图，无权图）
算法思想
final[]：标记各顶点是否已找到最短路径
dist[]：最短路径长度
path[]：路径上的前驱
arcs[i][j]：到的弧的权值
初始： 若从开始，令final[0]=true;dist[0]=0;path[0]=-1。 其余顶点final[k]=false;disk[k]=arcs[0][k];path[k]=(acrs[0][k]==)?-1:0
n-1轮处理： 循环遍历所有顶点，找到还没确定最短路径，且dist最小的顶点， 令final[i]=true。并检查所有邻接自的顶点， 若final[j]=false且dist[i]+arcs[i][j]<dist[j]， 则令dist[j]=dist[i]+arcs[i][j];path[j]=i。
时间复杂度
总时间复杂度：
每一轮时间复杂度：
Dijkstra算法不适用于有负权值的带权图
各顶点间的最短路径
Floyd算法（带权图，无权图）
算法思想：动态规划
Floyd算法可以用于解决负权值带权图
Floyd算法不能解决带有“负权回路”的图（有负权值的边组成回路），这种图可能没有最短路径
有向无环图（DAG）的问题
有向无环图描述表达式
有向无环图（DAG）：
一个算术表达式可以表示为一棵树的形式
丢弃重复部分，进行合并
做题方法
原理：顶点中不可能出现重复的操作数
方法
Step1：把各个操作数不重复的排成一排
Step2：标出各个运算符的生效顺序（先后顺序有点出入无所谓）
Step3：按顺序加入运算符，注意“分层”
分层：上层的运算符要基于下一层的运算结果来进行
Step4：从底向上逐层检查的运算符是否可以合体
拓扑排序
AOV网（用顶点表示活动的网）：
AOV网一定是DAG图，不能有环
拓扑排序：
简单理解：拓扑排序就是要找到做事的先后顺序
每个AOV网都有一个或多个拓扑排序
拓扑排序的实现：
indegree[]：记录当前顶点入度
print[]：记录拓扑排序序列
S：保存度为0的顶点（可用栈，也可用队列）
时间复杂度
邻接表：
邻接矩阵：
逆拓扑排序
逆拓扑排序的实现：
第一种算法与拓扑排序类似，自行设计代码
DFS算法
性质
拓扑排序、逆拓扑排序序列可能不唯一
若图中有环，则不存在拓扑排序序列/逆拓扑排序序列
关键路径问题
AOE网
在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销（如完成活动所需的时间），称之为用边表示活动的网络，简称AOE网。
AOE网的两个性质
只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始。
只有在进入某顶点的个有向边所代表的活动都已结束时，该顶点所代表的事件才能发生。另外，有些活动是可以并行进行的。
在AOE网中仅有一个入度为0的顶点，称为开始顶点（源点），它表示整个工程的开始，也仅有一个出度为0的点，称为结束顶点（汇点），它表示整个工程的结束
从源点到汇点的有向路径可能有多条，所有路径中，具有最大路径长度的路径称为关键路径，而把关键路径上的活动称为关键活动
完成整个工程的最短时间就是关键路径的长度，若关键活动不能按时完成，则整个工程的完成时间就会延长。
一些概念
事件的最早开始时间ve(k)——决定了所有从开始的活动能够开工的最早时间
活动的最早开始时间e(i)——指该活动的起点所表示的事件的最早发生时间
事件的最迟开始时间ve(k)——它是指在不推迟整个工程完成的前提下，该事件最迟必须发生的时间
活动的最迟开始时间l(i)——它是指该活动弧的终点所表示事件的最迟发生时间与该活动所需时间之差
活动的时间余量d(i)=l(i)-e(i)——表示在不增加完成整个工程所需总时间的情况下，活动可以拖欠的时间
解题步骤
1.求所有事件的最早发生时间ve()
按拓扑排序序列，依次求各个顶点的ve(k): ve(源点)=0 ve(k) = Max{ve(j)+Weight(,)}，为的任意前驱
2.求所有事件的最迟发生时间vl()
按逆拓扑排序序列，依次求各个顶点的vl(k): vl(汇点)=ve(汇点) vl(k) = Min{vl(j)-Weight(,)}，为的任意后继
3.求所有活动的最早发生时间e()
若边表示活动，则有e(i)=ve(k)
4.求所有活动的最迟发生时间l()
若边表示活动，则有l(i)=vl(j)-Weight()
5.求所有活动的时间余量d()
d(i)=l(i)-e(i)
6.d(i)=0的活动就是关键活动，由关键活动可得关键路径
关键活动，关键路径的特性
若关键活动的耗时增加，则整个工程的工期将延长
缩短关键活动的时间，可以缩短整个工期
当缩短到一定程度时，关键活动可能会变成非关键活动
可能有多条关键路径，只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的
第七章 查找
查找的基本概念
基本概念
查找
在数据集合中寻找满⾜某种条件的数据元素的过程称为查找
查找表（查找结构）
⽤于查找的数据集合称为查找表，它由同⼀类型的数据元素（或记录）组成
关键字
数据元素中唯⼀标识该元素的某个数据项的值，使⽤基于关键字的查找，查找结果应该是唯⼀的。
对查找表的常见操作
查找符合条件的数据元素
只需要进行静态查找表
关注查找速度即可
插入、删除某个数据元素
需要动态查找表
除了查找速度，也要关注插、删是否方便实现
查找算法的效率评价
查找长度
在查找运算中，需要对⽐关键字的次数称为查找⻓度
平均查找⻓度（ASL, Average Search Length）
所有查找过程中进⾏关键字的⽐较次数的平均值
ASL 的数量级反应了查找算法时间复杂度
评价⼀个查找算法的效率时，通常考虑查找成功/查找失败两种情况的 ASL
通常认为查找任一元素的概率相同
顺序查找
算法思想
顺序查找，⼜叫“线性查找”，通常⽤于线性表。
从头到脚挨个找（或者从脚到头）
适用于顺序表、链表，表中元素有序无序都OK
算法实现
在0号位置存一个“哨兵”，从尾部向头部挨个查找
查找成功/查找失败：ASL都是O(n)数量级
算法优化
若表中元素有序
当前关键字大于(或小于)目标关键字时，查找失败
优点：查找失败时ASL更少
查找判定树
成功结点的关键字对比次数=结点所在层数
失败结点的关键字对比次数=其父节点所在层数
若各个关键字被查概率不同
被查概率大的放在靠前位置
优点︰查找成功时ASL更少
时间复杂度
O(n)
折半查找
算法思想
折半查找，⼜称“⼆分查找”，仅适⽤于有序的顺序表
在[low, high]之间找目标关键字，每次检查mid=(low+high)/2
根据mid所指元素与目标关键字的大小调整low或high，不断缩小low和high的范围
若low>high则查找失败
算法实现
查找判定树
构造
由mid所指元素将原有元素分割到左右子树中
Key：右子树结点数–左子树结点树=0或1
特性
如果当前low和high之间有奇数个元素，则 mid 分隔后，左右两部分元素个数相等
如果当前low和high之间有偶数个元素，则 mid 分隔后，左半部分⽐右半部分少⼀个元素
折半查找的判定树是平衡的二叉排序树（左<中<右）
折半查找判定树，只有最下面一层是不满的
若查找表有n个关键字，则失败结点有n+1个
ASL≤h
折半查找效率
时间复杂度
O()
大部分情况下，折半查找更有效率
分块查找
算法思想
用“索引表”保存每个分块的最大关键字和分块的存储区间
先查索引表（顺序或折半)、再对分块内进行顺序查找
对索引表进行折半查找时，若索引表中不包含目标关键字，
若low超出索引表，查找失败
特点：块内无序，块间有序
查找效率分析
ASL=查索引表的平均查找长度＋查分块的平均查找长度
设n个记录，均匀分为b块，每块s个记录
顺序查找索引表
折半查找索引表
若查找表是“动态查找表”，更好的实现方式
链式存储
二叉排序树
二叉排序树的定义
二叉排序树，又称二叉查找树（BST）
左子树结点值<根结点值<右子树结点值
进行中序遍历，可以得到一个递增的有序序列
二叉排序树可用于元素的有序组织、搜索
查找操作
若树非空，目标值与根结点的值比较：
插入操作
若原二叉排序树为空，则直接插入结点；
若关键字k小于根结点值，则插入到左子树；
若关键字k大于根结点值，则插入到右子树；
不同的关键字序列可能得到同款二叉排序树，也可能得到不同款二叉排序树
删除操作
先搜索找到目标结点：
1.若被删除结点z是叶子结点，则直接删除，不会破坏二叉排序树的性质；
2.若结点z只有一棵左子树或右子树，则让z的子树成为z父结点的子树，替代z的位置；
3.若结点z有左、右两棵子树，则令z的直接后继（或直接前驱）替代z，然后从二叉排序树中删去这个直接后继（或直接前驱），这样就转换成了第一或第二种情况。
查找效率分析
查找长度
在查找运算中，需要对比关键字的次数称为查找长度，反映了查找操作时间
取决于树的高度，最好，最坏O(h)
平均查找长度的计算
查找成功的情况
查找失败的情况（需补充失败结点）
平衡二叉树
定义
平衡二叉树（AVL树）：树上任一结点的左子树和右子树高度之差不超过1
结点的平衡因子=左子树高-右子树高
平衡二叉树结点的平衡因子的值只可能是-1，0，1
只要有任一结点的平衡因子绝对值大于1，就不是平衡二叉树
插入操作
从插入点往回找到第一个不平衡结点，调整以该结点为根的子树
每次调整的对象都是“最小不平衡子树”
在插入操作，只要将最小不平衡子树调整平衡，则其他祖先结点都会恢复平衡
插入新结点后如何调整“不平衡”问题
LL
在A的左孩子的左子树中插入导致不平衡
LL平衡旋转（右单旋转）
由于在结点A的左孩子（L）的左子树（L）上插入了新结点，A的平衡因子由1增至2，导致以A为根的子树失去平衡，需要一次向右的旋转操作。
将A的左孩子B向右上旋转代替A成为根节点
将A结点向右下旋转成为B的右子树的根结点
而B的原右子树则作为A结点的左子树
RR
在A的右孩子的右子树中插入导致不平衡
RR平衡旋转（左单旋转）
由于在结点A的右孩子（R）的右子树（R）上插入了新结点，A的平衡因子由-1减至-2，导致以A为根的子树失去平衡，需要一次向左的旋转操作。
将A的右孩子B向左上旋转代替A成为根节点
将A结点向左下旋转成为B的左子树的根结点
而B的原左子树则作为A结点的右子树
LR
在A的左孩子的右子树中插入导致不平衡
LR平衡旋转（先左后右双旋转）
由于在结点A的左孩子（L）的右子树（R）上插入了新结点，A的平衡因子由1增至2，导致以A为根的子树失去平衡，需要两次旋转操作，先左旋转再右旋转。
将A的左孩子B的右子树的根结点C向左上旋转提升至B结点的位置
然后再把该C结点向右上旋转提升到A结点的位置
RL
在A的右孩子的左子树中插入导致不平衡
LR平衡旋转（先右后左双旋转）
由于在结点A的右孩子（R）的左子树（L）上插入了新结点，A的平衡因子由-1减至-2，导致以A为根的子树失去平衡，需要两次旋转操作，先右旋转再左旋转。
将A的右孩子B的右子树的根结点C向右上旋转提升至B结点的位置
然后再把该C结点向左上旋转提升到A结点的位置
步骤
插入后计算平衡因子，找到最小不平衡树
判断不平衡类型，根据不平衡类型进行旋转
旋转结束后，根据最小排序树挂叶结点
只有左孩子才能右上旋
查找效率分析
高为h的平衡二叉树最少有几个结点--递推求解
平衡二叉树的最大深度为，平均查找长度/查找的时间复杂度为
删除操作
删除结点后，要保持二叉排序树的特性不变（左<中<右）
若删除节点导致不平衡，则需要调整平衡
具体步骤
1.删除结点（方法同“二叉排序树”）
2.一路向北找到最小不平衡子树
3.找最小不平衡子树下，“个头”最高的儿子、孙子
4.根据孙子的位置调整平衡（LL/RR/LR/RL）
5.如果不平衡向上传导，继续2
时间复杂度
红黑树（RBT）
定义、性质
插入/删除很多时候不会破坏“红黑”特性，无需频繁调整树的形态。
适用于频繁插入、删除的场景，实用性更强
红黑树是一棵二叉排序树
特性
每个结点或是红色，或是黑色的
根节点是黑色的
叶结点（外部结点、NULL结点、失败结点）均是黑色的
不存在两个相邻的红结点（即红结点的父节点和孩子结点均是黑色）
对每个结点，从该节点到任一叶结点的简单路径上，所含黑结点的数目相同
左根右，根叶黑
性质
从根节点到叶结点的最长路径不大于最短路径的2倍
有n个内部节点的红黑树高度h≤
红黑树查找操作时间复杂度是
结点的黑高bh
从某结点出发（不含该结点）到达任一空叶结点的路径上黑结点总数
插入
先查找，确定插入位置（原理同二叉树），插入新结点
新结点是根，染为黑色
新结点非根，染为红色
若插入新结点后，依然满足红黑树定义，则插入结束
若插入新结点后不满足红黑树定义，需要调整，使其满足红黑树定义
如何调整：看新结点叔叔的脸色
黑叔：旋转+染色
LL型：右单旋，父换爷+染色
RR型：左单旋，父换爷+染色
LR型：左、右双旋，儿换爷+染色
RL型：右、左双旋，儿换爷+染色
红叔：染色+变新
叔父爷染色，爷变为新结点
如果不是根节点，关注“不红红”特性
删除
重要考点
1.红黑树删除操作的时间复杂度
2.红黑树中删除结点的处理方式和“二叉排序树的删除”一样
3.按2删除结点后，可能破坏“红黑树特性”，此时需要调整结点颜色、位置，使其再次满足红黑树特性
B树
定义与概念
B树，又称多路平衡查找树，B树中所有结点的孩子个数的最大值称为B树的阶，通常用m表示。
一棵m阶B树或为空树，或为满足如下性质的m叉树
1.树中每个结点至多有m棵子树，即至多含有m-1个关键字
2.若根结点不是终端结点，则至少有两棵子树
3.除根节点外的所有非叶结点至少有[m/2]棵子树，即至少含有[m/2]-1个关键字
4.所有非叶结点的结构如上：
5.所有的叶结点都出现在同一层次上，并且不带信息（可视为外部结点或类似于折半查找判定树的查找失败结点，实际上这些结点不存在，指向这些结点的指针为空）。
m阶B树的核心特性
1.根节点的子树数∈[2,m]，关键字数∈[1,m-1]。
2.对任一结点，其所有子树高度都相同
3.关键字的值：子树0<关键字1<子树1<关键字2<子树2<...（类比二叉查找树 左<中<右）
高度
含n个关键字的m阶B树，最小高度，最大高度是多少？（不包括叶子结点（失败结点））
最小高度——让每个结点尽可能的满，有m-1个关键字，m个分叉，则有
最大高度——让各层的分叉尽可能的少，即根节点只有2个分叉，其他结点只有[m/2]个分叉，各层结点至少有：第一层1、第二层2、第三层2[m/2]、...、第h层2([m/2])、第h+1层共有叶子结点（失败结点）2([m/2])个
插入
在插入key后，若导致原结点关键字数超过上限，则从中间位置([m/2])将其中的关键字分为两部分，左部分包含的关键字放在原结点中，右部分包含的关键字放到新结点中，中间位置([m/2])的结点插入原结点的父结点
新元素一定是插入到最底层“终端节点”，用“查找”来确定插入位置
删除
若被删除关键字在终端节点，则直接删除关键字（要注意节点关键字个数是否低于下限[m/2]-1）
若被删除关键字在非终端节点，则用直接前驱或直接后继来代替被删除的关键字
直接前驱：当前关键字左侧指针所指子树中“最右下”的元素
直接后继：当前关键字右侧指针所指子树中“最左下”的元素
删除后低于下限的情况
兄弟够借。若被删除关键字所在结点删除前的关键字个数低于下限，且与此结点右（或左）兄弟结点的关键字还很宽裕，则需要调整该结点、右（或左）兄弟结点及其双亲结点及其双亲结点（父子换位法）
当左兄弟很宽裕时，用当前结点的前驱、前驱的前驱来填补空缺
当右兄弟很宽裕时，用当前结点的后继、后继的后继来填补空缺
本质：永远保证 子树0<关键字1<子树1<关键字2<子树2<...
兄弟不够借：若被删除关键字所在结点删除前的关键字个数低于下限，且此时与该结点相邻的左、右兄弟结点的关键字个数均=[m/2]-1，则将关键字删除后与左（或右）兄弟结点及双亲结点中的关键字进行合并
对非终端结点关键字的删除，必然可以转化为对终端结点的删除操作
B+树
一棵m阶的B+树需满足下列条件
每个分支结点最多有m棵子树（孩子结点）
非叶根结点至少有两棵子树，其他每个分支结点至少有[m/2]棵子树
结点的子树个数与关键字个数相等
所有的叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按大小顺序排列，并且相邻叶结点按大小顺序相互链接起来
所有分支结点中仅包含它的各个子结点中关键字的最大值及指向其叶结点的指针
查找
多路查找
顺序查找
B+树中，无论查找成功与否，最终一定都要走到最下面一层结点
B+树与B树对比
散列查找
散列表
散列表，又称哈希表
特点是：数据元素的关键字与存储地址直接相关
如何建立“关键字”与“存储地址”的联系关系？
通过“散列函数（哈希函数）”：Addr=H(key)
处理冲突的方法
拉链法
把所有“同义词”存储在一个链表中
开放定址法
所谓开放定址法，是指可存放新表项的空闲地址既向它的同义词表项开放，又向它的非同义词表项开放。
其数学递推公式为：=(H(key)+)%m =0,1,2,...,k(k≤m-1)
采用开放定址法时，删除结点不能简单地将被删结点的空间置为空，否则将截断在它之后填入散列表的同义词结点的查找路径，可以做一个“删除标记”，进行逻辑删除
线性探测法
=0,1,2,3,...,m-1；即发生冲突时，每次往后探测相邻的下一个单元是否为空
空位置的判断也要算作一次比较
越早遇到空位置，就可以越早判定查找失败
线性探测法很容易造成同义词，非同义词的“聚集（堆积）”现象，严重影响查找效率
平方探测法
当=,,,,,...,,时，称为平方探测法，又称二次探测法，其中k≤m/2
比起线性探测法，更不易产生“聚集（堆积）”问题
非重点小坑：散列表长度m必须是一个可以表示成4j+3的素数，才能探测到所有位置
伪随机序列法
是一个伪随机序列
查找长度
在查找运算中，需要对比关键字的次数
装填因子
表中记录数/散列表长度
常见的散列函数
除留余数法
H(key)=key%p
散列表表长为m，取一个不大于m但最接近或等于m的质数p
直接定址法
H(key)=key或H(key)=a*key+b
其中，a和b是常数。这种方法计算最简单，且不会产生冲突。它适合关键字的分布基本连续的情况，若关键字分布不连续，空位较多，则会造成存储空间的浪费
数字分析法
选取数码分布较为均匀的若干位作为散列地址
设关键字是r进制数，而r个数码在各位上出现的概率不一定相同，可能在某些数位上分布均匀一些，每种数码出现的机会均等；而在某些位上分布不均匀，只有某几种数码经常出现，此时可选取数码分布较为均匀的若干位作为散列地址。这种方法适合于已知的关键字集合，若更换了关键字免责需要重新构造新的散列函数。
平方取中法
取关键字的平方值的中间几位作为散列地址
具体取多少位要视实际情况而定。这种方法得到的散列地址与关键字的每位都有关系，因此使得散列地址分布比较均匀，适用于关键字的每位取值都不够均匀或小于散列地址所需的位数。
再散列法（再哈希法）
除了原始的散列函数H(key)之外，多准备几个散列函数，当散列函数冲突时，用下一个散列函数计算一个新地址，直到不冲突为止
第八章 排序
排序的基本概念
排序，就是重新排列表中的元素，使表中的元素满足按关键字有序的过程
评价指标
算法的稳定性，关键字相同的两个元素，在排序前后的相对位置不变，则称这个排序算法是稳定的，否则是不稳定的
时间、空间复杂度
排序算法
内部排序
关注如何使算法的时间复杂度和空间复杂度更低
外部排序
还要关注如何使读/写磁盘次数更少
内部排序
插入排序
算法思想
每次将一个待排序的记录按其关键字大小插入到前面已排好序的子序列中，直到全部记录插入完成
代码实现
性能分析
空间复杂度：O(1)
时间复杂度
最好时间复杂度：O(n)
最坏时间复杂度：O(n²)
平均时间复杂度：O(n²)
算法稳定性：稳定
优化
折半插入排序
折半查找找到应插入的位置，仅适用于顺序表
注意：一直到low>high时才停止折半查找。当mid所指元素等于当前元素时，应继续令low=mid+1，以保证“稳定性”。最终应将当前元素插入到low所指位置（即high+1）
比起直接插入排序，只减少了比较关键字的次数，时间复杂度仍是O(n²)
希尔排序
算法思想
先追求表中元素部分有序，再逐渐逼近全局有序
先将待排序表分割成若干形如L[i,i+d,i+2d,...,i+kd]的“特殊”子表，对各个子表分别进行直接插入排序。缩小增量d，重复上述过程，直到d=1为止。
代码实现
性能分析
空间复杂度：O(1)
时间复杂度：和增量序列的选择有关，目前无法用数学手段证明确切的时间复杂度，但优于插入排序
算法的稳定性：不稳定
适用性：仅可用于顺序表
交换排序
冒泡排序
算法思想
从后往前（或从前往后）两两比较相邻元素的值，若为逆序（即A[i-1]>A[i]），则交换它们，直到序列比较完。称这样过程为“一趟”冒泡排序。最多只需n-1趟排序
每一趟排序都可以使一个元素移动到最终位置，已经确定最终位置的元素在之后的处理中无需再次对比
如果某一趟排序过程中未发生“交换”，则算法可以提前结束
每次交换都要移动元素三次
代码实现
性能分析
空间复杂度：O(1)
时间复杂度
最好时间复杂度：O(n)
算法稳定性：稳定
适用性：顺序表，链表都可以
快速排序
算法思想
在待排序表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)上，这个过程称为一次“划分”。然后分别递归地对两个子表重复上述过程，直至每部分只有一个元素或空为止，即所有元素放在了其最终位置上。
算法表现主要取决于递归深度，若每次“划分”越均匀，则递归深度越低。 “划分”递归深度越深。
代码实现
性能分析
空间复杂度
最好：O(n)
最坏：O(log n)
时间复杂度
最好：O(n²)
稳定性：不稳定
408原题：一次划分≠一次排序
选择排序
简单选择排序
算法思想
每一趟在待排序元素中选取关键字最小的元素加入子序列
n个元素进行n-1次处理
代码实现
性能分析
空间复杂度：O(1)
时间复杂度：O(n²)
稳定性：不稳定
适用性：顺序表，链表都可以
堆排序
算法思想
顺序存储的“完全二叉树”
堆：若n个关键字序列L[1...n]满足下面某一条性质，则称为堆
1.若满足：L(i)≥L(2i)且L(i)≥L(2i+1) (1≤i≤n/2)——大根堆
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]
若元素互换破坏了下一级的堆，则采用相同的方法继续往下调整（小元素不断“下坠”）
堆排序：每一趟将堆顶元素加入有序子序列（与待排序序列中的最后一个元素交换），并将待排序元素序列再次调整为大根堆（小元素不断“下坠”）
基于大根堆的堆排序得到“递增序列”，基于小根堆的堆排序得到“递减序列”
代码实现
性能分析
空间复杂度：O(1)
时间复杂度
建堆的时候，关键字对比次数不超过4n，建堆时间复杂度=O(n)
堆排序的时间复杂度：O(n log n)
稳定性：不稳定
堆的插入删除
插入
对于小根堆，新元素放到表尾，与父节点对比，若新元素比父节点更小，则将二者互换。新元素就这样一路“上升”，直到无法继续上升为止
删除
被删除的元素用堆底元素替代，然后让该元素不断“下坠”，直到无法下坠为止
归并排序
算法思想
把两个或多个已经有序的序列合并成一个
2路归并的“归并树”——形态上就是一棵倒立的二叉树
n个元素进行2路归并排序，归并趟数=[log n]
实现步骤
若low<high，则将序列从中间mid=(low+high)/2分开
对左半部分[low,mid]递归地进行归并排序
对右半部分[mid+1,high]递归的进行归并排序
将左右两个有序子序列Merge为一个
代码实现
性能分析
空间复杂度：O(n)
时间复杂度
每趟归并的时间复杂度：O(n)
算法的时间复杂度：O(n log n)
稳定性：稳定
基数排序
算法思想
过程
第一趟分配：以“个位”进行“分配”
第一趟收集结束：得到按个位“递减”排序的序列
第二趟分配：以“十位”进行“分配”
第二趟收集结束：得到按“十位”递减排序的序列，十位相同的按个位递减排序
第二趟分配：以“百位”进行“分配”
第三趟收集结束：得到按“百位”递减排序的序列，百位相同的按十位递减排序，十位相同的按个位递减排序
假设长度为n的线性表中每个结点的关键字由d元组(,,,...,,)组成，其中0≤≤r-1(o≤k＜n,0≤i≤d-1)，r称为“基数”
基数排序得到递减序列的过程如下
初始化：设置r个空队列，,,...,
按照各个关键字位权重递增的次序（个，十，百），对d个关键字位分别做“分配”和收集
分配：顺序扫描各个元素，若当前处理的关键字位=x，则将元素插入队尾，一趟分配耗时O(n)
收集：把,,...,各个队列中的结点依次出队并链接，一趟收集耗时O(r)
代码实现
性能分析
空间复杂度：O(r)
时间复杂度：O(d(n+r))
稳定性：稳定
适用性：善于处理
1.数据元素的关键字可以方便地拆分为d组，且d较小
2.每组关键字的取值范围不大，即r较小
3.数据元素个数n较大
外部排序
外存与内存之间的数据交换
操作系统以“块”为单位对磁盘存储空间进行管理，如每块大小1KB，每个磁盘块内存放着各种而样的数据
磁盘的读/写以“块”为单位，数据读入内存后才能被修改，修改完了还要写回磁盘
外部排序
外部排序的原理
外部排序：数据元素太多，无法一次全部读入内存进行排序
若要进行k路归并排序，则需要在内存中分配k个输入缓冲区和1个输出缓冲区
步骤
生成r个初始归并段（对L个记录进行内部排序，组成一个有序的初始归并段）
进行S趟k路归并，S=[]
k越大，r越小，归并趟数越少，读写磁盘次数越少
如何进行k路归并
把k个归并段的块读入k个输入缓冲区
用“归并排序”的方法从k个归并段中选出几个最小记录暂存到输出缓冲区中
每当一个输入缓冲区为空时，立即输入下一块待排数据
当输出缓冲区满时，写出外存
外部排序时间开销
读写外存的时间
内部排序所需时间
内部归并所需时间
优化思路
多路归并
需要增加相应的输入缓冲区
每次从k个归并段中选一个最小元素需要（k-1）次关键字对比
采用多路归并可以减少归并趟数，从而减少磁盘I/O（读写）次数
减少初始归并段数量
若能增加初始归并段长度，则可减少初始归并段数量r
按照本节课介绍的方法生成的初始归并段，若共有N个记录，内存工作区可以容纳L个记录，则初始归并段数量r=N/L
纠错：k路平衡归并
1.最多只能有k个段归并为一个
2.每一趟归并中，若有m个归并段参与归并，则经过这一趟处理得到[m/k]个新的归并段
败者树
使用k路平衡归并策略，选出一个最小元素需要对比关键字（k-1）次，导致内部归并所需时间增加————————————可以用败者树解决！
什么是败者树
败者树——可视为一棵完全二叉树（多了一个头）。k个叶结点分别是当前参加比较的元素，非叶子结点用来记忆左右子树中的“失败者”，而让胜者往上继续进行比较，一直到根结点
原理
每个叶子结点对应一个归并段
分支结点记录失败败者来自哪个归并段
根节点记录冠军来自哪个归并段
性能分析
对于k路归并，第一次构造败者树需要对比关键字k-1次
有了败者树，选出最小元素，只需对比关键字[]次
置换-选择排序
若共有N个记录，内存工作区可以容纳L个记录，则初始归并段数量r=N/L———可用“置换-选择排序”进一步减少初始归并数量
设初始待排文件为FI，初始归并段输出文件为FO，内存工作区为WA，FO和WA的初始状态为空，WA可容纳w个记录。置换-选择算法的步骤如下
1.从FI输入w个记录到工作区WA
2.从WA中选出其中关键字取最小值的记录，记为MINIMAX记录
3.将MINIMAX记录输出到FO去
4.若FI不空，则从FI输入下一个记录到WA中
5.从WA中所有关键字比MINIMAX记录的关键字大的记录中选出最小关键字记录，作为新的MINIMAX记录
6.重复3-5，直至在WA中选不出新的MINIMAX记录为止，由此得到一个初始归并段，输出一个归并段的结束标志到FO中去
7.重复2-6，直至WA为空，由此得到全部初始归并段
最佳归并树
归并块的神秘性质
归并过程中的磁盘I/O次数=归并树的WPL*2
要让磁盘I/O次数最小，就要使归并树WPL最小——哈夫曼树
对于k叉归并，若初始归并段的数量无法构成严格的k叉排序树，则需要补充几个长度为0的“虚段”，再进行k叉哈夫曼树的构造
如何构造
补充虚段
1.若（初始归并段数量-1）%（k-1）=0，说明刚好可以构成严格k叉树，此时不需要添加虚段
2.若（初始归并段数量-1）%（k-1）=u≠0，则需要补充（k-1）-u个虚段
构造k叉哈夫曼树
每次选择k个根结点权值最小的树合并，并将k个根节点的权值之和作为新的根节点的权值