#一、绪论

#1.数据结构基本概念

• 数据：数据是信息的载体，是所有能输入到计算机并被计算机程序识别和处理的符号的集合。
• 数据元素：数据元素是数据的基本单位，由若干数据项组成。数据项是构成数据元素的不可分割的最小单位。
• 数据对象：是具有相同性质的数据元素的集合，是数据的一个子集，如整数数据对象就是整数数据集。
• 数据类型： 是一个值的集合和定义在此集合上的一组操作的总称。有原子类型，结构类型和抽象数据类型。
• 抽象数据类型（ADT）:不讨论存储结构，只关心逻辑结构和数据的运算。
• 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。

一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。

• 线性结构：1对1
• 树形结构：1对多
• 图状结构或网状结构：多对多

数据的存储结构： 顺序存储，链式存储，索引存储，散列存储。
数据结构的三要素： 逻辑结构，存储结构，数据的运算。
可以用抽象数据类型定义一个完整的数据结构
数据的逻辑结构独立于其存储结构，而存储结构是逻辑结构在计算机上的映射，不能独立与逻辑结构而存在。
链式存储设计时，各个不同结点的存储空间可以不连续，但结点内的存储单元必须连续。

#2.算法

算法是对特定问题求解步骤的一种描述，他是指定的有限序列。
算法的5个特性：有穷性，确定性，可行性，输入和输出。
好的算法要求：正确性，可读性，健壮性和效率与低存储量需求。
越高级的语言执行效率越低。
一般考虑最坏情况下的复杂度。
$O（1） < O（log_2n）< O（n）< O（nlon_2n）< O（n^2）< O（n^3）< O（2^n）< O（n!）< O（n^n）（常对幂指阶依次增大）$
算法原地工作是指辅助空间是常量。
时间复杂度是指渐进时间复杂度，指的是整体的效率，不能带入常量比较大小，即常对幂指阶效率必然逐渐递减。
斐波那契数列：该项等于前面两项之和：0，1，1，2，3，5…

#二、线性表

#1.线性表的定义和基本操作

线性表中的元素个数有限，有其先后顺序，数据类型都相同（占用相同大小的存储空间），具有抽象性。

#2.线性表的顺序表示（顺序表）

顺序表逻辑上相邻，物理上也相邻，常用数组表示线性表。
注：线性表的位序从1开始，而数组的元素下标从0开始。

线性表可以随机存取，随机访问，按位查找的时间复杂度为O（1），但插入和删除元素要移动大量元素。

顺序表存储密度高，每个节点只存储数据元素。

操作	平均时间复杂度	平均次数
插入	$O（n）$	n/2
删除	$O（n）$	$（n-1）/2$
按值查找	$O（n）$	$（n+1）/2$

顺序表满需要扩容时，是复制该顺序表的内容到一个新的（m+n）个连续地址块的地址上。

#3.线性表的链式表示（链表）

单链表逻辑结构相邻，物理结构不相邻。Data数据域，next存放后继结点的地址，存在浪费空间的缺点，是非随机存取。

通常用一个头指针来标识一个单链表，头指针为null时表示一个空表。为了操作方便，在单链表第一个结点之前附加一个结点，称为头结点。头结点数据域可以不存放任何数据，也可以存放链表长度等记录。

单链表操作	方法	描述	时间复杂度
建立链表	头插法	每次将S所指结点插在最前端。	$O（n）$
	尾插法	每次将S所指结点插在最末端。	$O（n）$
查找链表	按序号查找	第一个节点出发序号依次加1，没找到返回null	$O（n）$
	按值查找	第一个节点出发按值查找，没找到返回null	$O（n）$
插入结点	按序查找	按需查找第i-1个结点，用两个指针分别指向i和i-1结点*P和*S;P->next=S->next；S->next=P	$O（n）$
删除结点	按序查找	按序查找第i-1个结点，用两个指针分别指向i和i-1结点*P和*S;S->next=P->next；free（P）	$O（n）$
求表长	按序查找	表长是指表的数据结点的个数，不包含头结点	$O（n）$

删除结点*P，一般需要查找到其前驱结点在删除，这时时间复杂度O（n）；但还可以将该结点的后继节点的数据域放到该结点内，再删除下一节点，这时时间复杂度为O（1）

双链表： 在单链表的基础上增加了前驱结点指针prior。

双链表操作	描述	注意点
插入	*P之后插入*S；S->next=P->next；P->next->prior=S；S->prior=P；P->next=S	前两个操作必须在第四个操作前
删除	删除*p的后继节点*q；p->next=q->next；q->next->prior=p;Free（q）

循环链表：

循环链表类型	说明	时间复杂度
循环单链表	最后一个结点的指针不是null，而是头结点；判断链表是否为空不是头结点指针指向null，而是指向头指针	头指针：对表尾操作为$O（n）$；尾指针：对表头和表尾操作都为$O（1）$
循环双链表	头结点的prior还要只想表尾结点；判断链表为空，其头结点的prior域和next域都等于头指针

静态链表： 借助数组来描述线性表的链式存储结构，也有数据域data和指针域next，这里的next指的是相对位置（数组下标），又称游标，与顺序表逸一样需要预先分配一块连续的内存空间。以next=-1为结束标志。

删除循环单链表的第一个结点，一般不需要改变尾指针；但若该链表只有一个结点，即删除的是尾结点，尾指针需要指向头指针

#三、栈、队列和数组

#1.栈

栈定义：栈是一种线性表，但限定只能在一端进行插入或删除操作（后进先出）
卡兰特数：$\frac {1}{n+1} C_{2n}^{n}$ 是n各不同元素入栈，出站的不同排列数量

顺序栈
顺序栈采用顺序存储方式，一组连续的存储单元存放自栈底到栈顶的数据元素，附设一个栈顶指针top

初始化条件	说明	进栈	出栈
top=-1	栈顶指针指向栈顶元素	S.data（++top）	X=S.data（top++）
top=0	栈顶指针指向栈顶元素的下一个元素	S.data（top++）	X=S.data（++top）

共享栈： 利用栈底位置相对不变的特性，用两个顺序栈共享一个一维数组空间。栈底为该空间的两端，栈顶向中间延伸。Top0=-1时0号栈为空；Top1=maxsize时，1号栈为空；当top1-top0=1时判断为栈满；进栈

初始化条件	栈空	栈满	进栈	出栈
Top0=-1	Top0=-1	Top1-Top0=1	先+1再赋值	先出栈再-1
Top1=maxsize	Top1=maxsize		先-1再赋值	先出栈再+1

链栈： 采用链式存储结构，不存在栈满，所有操作在表头实现，栈顶可以没有头结点，头指针指向栈顶元素。有头结点出入栈操作不同。Top指针跟随栈顶移动，每插入一个元素移动一次。

#2.队列

队列简称队，操作受限的线性表，只允许一端插入，另一端删除，先进先出，队首/头删除，队尾插入。

队列的顺序存储： 队头指针front和队尾指针rear（可能指向队尾下一个元素）

初始状态	Front=rear=0
进队操作	队尾取值再＋1
出队操作	对头取值再+1

顺序存储存在假溢出，不太实用

循环队列： 将顺序队列臆造为一个环状的空间，把存储队列的元素的表从逻辑上视为一个环。
判断队满的三个方式：

牺牲一个单元	当队头指针在队尾指针的下一位置则满
增设元素个数记录	Size=0则队空；size=maxsize则满
增设tag数据成员	Tag=0，删除导致front=rear，则为队空Tag=1，插入导致front=rear，则队满

队列的链式存储（链队列）： 实际上是同时带有队头指针和队尾指针的单链表，头指针指向队头结点，尾指针指向队尾结点

Front=null且rear=null时，链式队列为空。插入第一个结点时，front和rear都指向这个结点（可添加头结节，当队列为空时都指向头结点，插入第一个结点时front指向头结点，rear指向新插入的结点）

双端队列： 允许两端都可以进行入队和出队的操作，也可进一步分为输出受限和输入受限的双端队列
出队或入队都是相应的指针＋1取最大值的余数

#3.栈和队列的应用

栈在括号匹配中的应用： 左括号压入栈，右括号则与栈顶括号匹配；最后匹配完判断是否栈空。
栈在表达式求值中的应用： 后缀表达式操作数和运算符分别入栈；操作数直接入栈，运算符先入栈的与后入栈的比较，若前者优先级高则出栈运算，反之入栈等待。
栈在递归中的应用： 外层递归先入栈，内层递归后入栈，最后内层递归先出栈运算。递归的效率低下但代码简单，容易理解。
栈的其他应用： 二进制转换，迷宫求解

队列在层次遍历中的应用： 根节点出队，左孩子和右孩子依次入队
队列在计算机系统中的应用： 主机与外部设备之间速度不匹配的问题（打印机缓冲区）；多用户引发的资源竞争问题
队列的其他应用： 页面替换算法

#4.数组

定义：由n（n≥1）个相同类型的数据元素构成的有序序列
数组除结构的初始化和销毁外，只有存取元素和修改元素的操作
数组的存储结构：行优先和列优先

特殊矩阵的压缩存储：
压缩存储：多个值相同的元素只分配一个存储空间，对零元素不分配存储空间，目的是节约存储空间
将一个二维数组（i，j）存放在一个一维数组（k）中

对称矩阵： $kmax=[n（n+1）]/2$
下三角阵：$K=1+2+3+…+（i-1）+（j-1）$（下标从0开始）
上三角阵：上述表达式i与j互换即可求出

下三角矩阵： $kmax=[n（n+1）]/2+1$
下三角阵：$K=1+2+3+…+（i-1）+（j-1）$
上三角阵：$k=[n（n+1）]/2$ （最后一个元素）

上三角矩阵： $kmax=[n（n+1）]/2+1$
上三角阵：$k=n+（n-1）+（n-2）+…+（n-i+2）+（n-i+1）-1$
下三角阵：$k=[n（n+1）]/2$ （最后一个元素）

三对角矩阵:
K=2i+j-3（1≤i，j≤n，| i-j |≤1）

稀疏矩阵:
稀疏矩阵三元组（i，j及其非零值）可以采用数组存储或者十字链表存储
十字链表： 每个元素包含三元组以及指向同行下一个元素和同列下一个元素的两个指针
稀疏矩阵压缩存储失去了随机存取特性

#四、串

#1.串的存储结构

定长顺序存储
用一组连续的存储单元存储串值的字符序列，即定长数组
堆分配存储
仍用一组连续的存储单元存储串值，但存储空间可动态分配
在C语钟存在一个称之“堆”的自由存储区，用malloc（）和free（）函数来动态存储管理
块链存储表示
类似于线性表的链式存储结构，每个结点既可以存放一个字符，也可以存放多个字符，每个结点称为块

#2.串的摸式匹配

• 简单的摸式匹配算法（O（nm））
  匹配失败，指针后退重新开始匹配，i=i-j+2，j=1，时间复杂度为O（nm）
• KMP算法
  next（j）数组为摸式串每一个字符设置一个数量，为最大公共前后缀数量+1
  next（1）=0，为了区分其他字符，因为只有第一个字符匹配失败需耍将指针移到主串下一位置
• KMP算法实现思想（$O（m+n）$）
  比较当前值与公共前缀后一位进行比较，相同则next[j+1]=j+1；不用则与第j位的公共前缀进行比较，以此类推（类似于二分法）
• next数组优化nextval
  若next[j]字符与当前符相同，则修改next[j]=next[next[j]]

#五、树与二叉树

#1.树的概念

树是n（n≥0）个结点的有限集，n=0为树
结点数=结点的度数+1
$n_0+n_1+n_2+…+n_n=n_1+2n_2+…+nn_n+1$

#2.二叉树

二叉树可以为空，而度为2的树至少有3个结点

几个特殊的二叉树

• 满二叉树
  高度为h，含有$2^h$-1个结点，每层有$2^{h-1}$结点，叶子结点集中在最下一层，只有度为0或2的结点，编号为i的结点左孩子为2i，右孩子为2ⅰ+1
• 完全二叉树
  若有度为1的结点，则只可能有1个，且该结点只有左孩子，没有右孩子
• 二叉排序树
  左子树<根结点<右子树
• 平衡二叉树
  树上任一结点左右子树的深度之差不超过1

二叉树的性质

• $n_0=n_2+1$
• $n_1=0或1$
• 双亲结点为i/2向下取整
• 结点i所在层次$\log _ { 2 } i$向下取整+1

二叉树的存储结构
顺序存储结构:适合存储完全二叉树知满二叉树（建议从数组下标1开始存储）
链式存储结构:二叉树一般采用链式存储，二叉链表一般包含3个域:数据域data、左指针域lchild和右指针域rchild
在含有n个结点的二叉链表中，含n+1个空链域

#3.二叉树的遍历

二叉树的遍历

• 先序遍历$（根→左→右）$栈
• 中序遍历$（左→根→右）$栈
• 后序遍历$（左→右→根）$栈
• 层次遍历$（队列）$

先序，中序和后序属于深度优先算法，利用了辅助工作栈。
先序是访问后入栈，中序是出找后访问。故先序是入栈序列，中序则是出栈序列

#4.线索二叉树

基本概念
利用链式存储二叉树的空指针来存放指向其前驱和后继的指针，加快了查找结点前驱和后继的速度
若无左子树，lchⅰld指向其前驱结点；若无右子树，rchild向后继结点
引入ltag和rtag标识指针域是指向左（右）孩子（0）还是前驱（后继）（1）

中序线索二叉树的遍历
先找到第一个结点，然后依次找结点的后继，直至后继为空

#5.树，森林

树的存储结构

• 双亲表示法
  连续空间存储，增设一个伪指针指方其双亲结点在数组中的位置
  根结点下标为o，其伪指针为-1
  客易寻找双亲结点，但寻找孩子结点需要遍历整个结构
• 孩子表示法
  将每个结点的孩子结点都用都用单链表连接起来，每个结点都有一个孩子链表
  寻找子女非常方便，寻找双亲需要遍历n个结点的n个孩子链表
• 孩子兄弟表示法（二叉树表方法）
  二叉链表作为树的存储结构，每个结点包括节点值，指向第一个孩子的结点指针和指向结点下一个兄弟的结点指针
  这种存储比较灵话，最大的优点是可以方便实现树与二叉树的转换，易于查找结点的孩子等

树、森林与二叉树的转换

• 左孩子右兄弟（左孩子依然是左孩子，右兄弟变为右孩子）
• 树转换成二叉树:步骤:①兄弟结点之间加一条线②保留第一个孩子，与其他孩子的连线抹掉③以树根为中心顺时针旋转45°
• 森林转换成二叉树:①将每棵树都转换成二叉树②每棵树的根都视作兄弟用一根线连线（全部视为右孩子）③以第一棵树根为中心顺时针旋转90°（第一棵树转换成左子树，剩余森林转换成右子树）
• 二叉树转换成森林:二叉树非空，则二叉树的根及左子树视为第一棵树，直到最后只剩一棵没有存子树对止，最后将二叉树转换成树即可

树与森林的遍历

• 树的遍历
  先根遍历:遍历序列与对应二叉树的先序遍历相同
  后根遍历:遍历序列与对应二叉树的相同
• 森林的遍历
  先序遍历:①访问第一棵树的根节点②先序遍历第一棵树中根节点的子森林③先序遍历除第一棵树之后剩余的树构成的森林
  中序遍历:①中序遍历第一棵树根结点的子树森林②第一棵树根结点③中序遍历剩余的树构成的森
  对应二叉树的先序遍历和中序遍历

#6.树与二叉树的应用

哈夫曼树和哈夫曼编码

• 带权路经长度:WPL=Σwl，w为叶结点的权重，l为路径长度（从根到该结点经过的边数）
• 带权路经长度最短的二叉树即为哈夫曼树
• 哈夫曼树的构造:选择两个权重最小的结合构成一个二叉树，权重为右孩子权重和；以以类推
• 哈夫曼树是最优（严格）二（m）叉树,只有度为0和2（m）的结点，即$n_0+n_2（或n_m）=2n_2（或mn_m）+1$
• 哈夫曼编码:0表示左子树，1表示右子树（或相反，没有规定）
  固定长度编码（每个字符的编码等长），可变长度编码（每个字符的编码可不等长）
  前缀编码:没有一个编码是另一个编码的前缀
  利用哈夫曼树可设计出总长度最短的二进制前缀编码

并查集

• 每个集合一棵树表示存储

• 使用双亲表示法（利用数组顺序存储，数组值为双亲结点的数组下标，根结点数组值为-1）：容易找到根结点

• 并（Union）:将根结点指向被合并的根结点

• 查（Find）:查找到该结点所属的根结点即可

• 初始化（Initial）:初始化查集，将所有数组元素初始化为-1

并查集的进一步优化

• Find操作的优化，压缩路径
  先找到根结点，再将经过的路径全部都挂到根结点上
• Union优化
  小树合到大树，这样合并后的树高度不会变大。将根结点的值设为树高的相反数

#六、图

#1.图的基本概念

• 有向图:v指向u，<v，u>，v为弧尾，u为弧头
  ID（v）:入度，以顶点v为终点的边的个数
  OD（ⅴ）:出度，以顶点v为起点的边的个数
  TD（v）=入度+出度
• 无向图:（v，u）
  TD（ⅴ）:顶点v的度，依附于该顶点的边的条数
  <br>
• 简单图:①不存在重复的边②不存在顶点到自身的边
• 多重图:与简单图相对，都存在和无向
  <br>
• 路径，回路，简单路经，简单回路，路径长度
• 点到点的距离:最短路径长度，若在在路径则长度为∞
  <br>
• 连通:无向图中，v到w存在路径
• 强连通:有向图中，v到w和w到ⅴ都有路经
  <br>
• 连通图:无向图中，任意两个顶点都连通（最少有n-1条边）
• 强连通图:有向图中，任意两个顶点都强连通（最少有n条边）
  <br>
• 子图:取出任意个顶点和顶点相关的边构成的图
• 生成子图:取出全部顶点和任意条边（不一定构成图）
  <br>
• 极大连通分量：无向图中的极大连通子图
• 强连通分量：有向图中的极大强连通子图
  <br>
• 生成树：连通图（无向图）的生成树包括图中的全部顶点的一个极小连通子图（有n个顶点则必有n-1条边），若砍去它的一条边，则会变成非连通图；加上一条边，则会变成一个回路
• 生成森林：在非连通图中，连通分量的生成树构成了非连通图的生成森林
  <br>
• 边的权、带权图/网、带权路径长度
• 无向完全图、有向完全图、稀疏图、稠密图
• 树:不存在回路、且连通的无向图
• 有向树:一个顶点的入度为0，其余顶点的入读均为1的有向图

#2.图的存储及基本操作

邻接矩阵法

• 用一个一维数组存储图中各顶点的信息，用一个二维数组（顶点数*顶点数）存储各顶点的邻接关系
• 无向图邻接矩阵为对称矩阵，规模较大时可采用压缩存储
  <br>
• 无向图：度为i行1的个数
• 有向图：度为i行+i列1的个数
  <br>
• 稠密图适合用邻接矩阵
• $A^n[i][j]$，表示从i到j，路径长度为n路径的数目

邻接表法

• 图的邻接表法结合了顺序存储和链式存储，适合存储稀疏矩阵
• 顶点表：data和firstarc
• 边表：adjvex和nextarc
• 每个顶点都有一个链表，存储的是以该顶点为顶点的边的另一顶点（有向图是以该顶点为出度的边的另一顶点）
• 寻找一个顶点入度的顶点很难

十字链表法

• 有向图的链式存储
• 数据结构：
  弧结点：tailvex（弧尾）、beadvex（弧头）、hlink（下一个弧头）、tlink（下一个弧尾）、info（相关信息）
  顶点结点：data（数据）、firsttil（该弧作为弧头的第一个弧结点）、firstout（该弧作为弧尾的第一个弧结点）
  沿着firsttil可以找到以该顶点为最终目的地的所有路径
  沿着firstout可以找到以该顶点为起点的所有路径
  <br>
• 十字链表法：1，2，3，4四个指针域
  1和2表示1指向2的弧，4指向顶点节点的另一条出度直到^（从顶点域第二个域firstout开始），3指向在哪些结点的2是自己结点（即自己是哪些结点的入度，从顶点第一个域firsttil开始）
  https://www.bilibili.com/video/BV1hV411t7SC?spm_id_from=333.880.my_history.page.click&vd_source=d6171ece387ad032b9676729d086d450

邻接多重表

• 无向图的链式存储
• 优化邻接表对边执行删除等操作时效率较低
• 类似于十字链表法
  https://www.bilibili.com/video/BV1TL411b7V3?spm_id_from=333.880.my_history.page.click&vd_source=d6171ece387ad032b9676729d086d450

#3.图的遍历

定义:从一个顶点出发，对图中所有顶点访问一次且仅访问一次

广度优先搜索（BFS）（队列）

• 广度优先类似于二叉树的层序遍历算法
• visited数组防止重复访问、
• 当各边权值相等时，BFS可以解决单源最短路径问题
• 性能分析

存储结构	空间复杂度（辅助队列）	时间复杂度
邻接矩阵	O（|V|）	O（$V^2$）
邻接表	O（|V|	O（|V|+|E|）

注：V是点数，E是边数

• 广度优先生成树：
  邻接矩阵表示唯一，则广度优先生成数唯一；、
  邻接表法表示不唯一，则广度优先生成树不唯一

深度优先搜索（DFS）（栈）

• 类似于二叉树的先序遍历
• 性能分析

存储结构	空间复杂度（递归工作栈）	时间复杂度
邻接矩阵	O（|V|）	O（$V^2$）
邻接表	O（|V|	O（|V|+|E|）

• 若有向图不连通，则会生成生成森林

图的遍历与图的连通性

• 图的遍历可以判断图的连通性
• 无向图连通，有向图强连通才能一次遍历到所有的顶点

#4.图的应用

最小生成树（MST）

• 包括图中的全部顶点和尽可能少的边
• 所有带权连通无向图的生成树中权值之和最小的生成树（可能有多个）

1.Prim算法
从某个顶点开始构建生成树，依次将代价最小的新顶点纳入生成树，直到所有顶点都纳入为止
2.Kruskal算法
每次选择一条权值最小的边，使这条边的两头连接（原本已连接的不选），直到所有结点都连通

算法比较：

算法	时间复杂度	适合场景
Prim	$O（V^2）$	边稠密图
Kruskal	$O（|E|log_2|E|$）	边稀疏而顶点较多图

最短路径问题
1.Dijkstra算法

• 求解带权有向图（或无向图）单源最短路径
• 时间复杂度$O（V^2）$
• 不适用于有负权值的带权图

2.Floyd算法

• 求出每一对顶点之间的最短路径
• 依次加入顶点1，2…n为中转站，找出最短路程
• 时间的复杂度$O（|V|^3）$
• 空间的复杂度$O（|V|^2）$
• 可以用于负权值的带权图
• 不能解决带有负权回路的带权图

有向无环图（DAG）的应用
1.描述表达式

• 合并表达式中的重复值（二叉树指向相同的值（每个数都要出现一次））

2.拓扑排序

• AOV网：用顶点表示活动的网（做一件事的操作顺序）（有向图表示各个事件的先后顺序）
• 依次删除入度为0的顶点，直到AOV网为空（或当前网中不存在入度为0的顶点）
• 可用于验证网是否有回路
• 邻接矩阵存储，时间复杂度为$O（V^2）$
  邻接表存储，时间复杂度为$0（|V|+|E|）$

3.逆拓扑排序

• 与拓扑排序相反，依次删除出度为0的顶点
• 拓扑排序和逆拓扑排序都不唯一

关键路径（运筹学）

• AOE网：顶点表示事件，有向边表示活动，边上的权值表示完成该活动的开销
• 关键路径：完成一个流程的最短时间
• 最早发生时间：正向
• 最迟发生时间：逆向

#七、查找

#1.查找基本概念

• 静态查找:①查询特定数据元素②查找满足条件的数据元素
• 动态查找：在静态查找的基础上加上③插入一个数据元素④删除某个数据元素怒
• 查找的使用范围

查找类型	查找方法
静态查找	顺序查找、折半查找、散列查找等
动态查找	二叉排序树的查找、散列查找等

• 平均查找长度：$ASL=P_iC_i（i从1到n求和）$，P是查找元素i的概率（一般认为查找概率相同，即$P=\frac{1}{n}$），C是找到元素i所需比较的次数

#2.顺序查找和折半查找

顺序查找

• 适用于顺序表和链表

（1）一般线性表的顺序查找

• 从一端查找到另一端
• 在数组下标为0处引入哨兵（值取表中没有的值），可以不必判断数组是否越界，当值为哨兵时，一定会退出循环
• $ASL_{成功}=\frac{n+1}{2}$
• $ASL_{不成功}=n+1$
• 若能预知表中记录的概率，应按从大到小的顺序排列，ASL会减小

（2）有序表的顺序查找

• 若从小到大排列，则当需要查找的数据大于某个顶点时退出查找
• $ASL_{成功}=\frac{n+1}{2}$
• $ASL_{不成功}=\frac{n}{2} +\frac{n}{n+1}$

折半查找

• 适用于有序的顺序表
• 若值大于mid值，则low=mid+1，high不动
• 若值小于mid值，则high=mid-1，low不动
• mid=（low+high）/2或者mid=（low+high）/2+1（一个算法的向上还是向下取整是一定的）
• 当low＞high时退出循环
• 折半查找的过程可描述成判定树，是个平衡二叉树
• 二叉排序树最优解是折半查找的平衡二叉树
• 判定树叶子节点是查找失败的数据范围（方形），比较次数最多不超过树的高度
• $ASL_{成功}=log_2（n+1）-1$,时间复杂度为：O（$log_2n$）

分块查找（索引顺序查找）

• 吸取了顺序查找和折半查找的优点，既有动态结构有能快速查找
• 将查找表分为若干子块，块内元素可以无序，块间元素必须有序
• 块间按块内最大关键字的大小从小到大排序
• 步骤：①在索引表中确定关键字所在块（可以顺序查找，也可以折半查找）②块内顺序查找

注：

• 当各数据查找概率不同时，折半查找法不一定比顺序查找更优，反而按概率从大到小排列的顺序查找更优，或者利用二叉排序树

#3.树形查找

二叉排序树（BST）

• 左子树结点值＜根结点结点值＜右子树结点值
• 中序遍历是有序序列
• 不同的排序序列得到的二叉排序树不一定相同
• 叶子节点处插入
• 删除结点：
  ①叶子节点，直接删除
  ②只有左子树或右子树，则删除后用左子女或右子女代替
  ③左子树和右子树均不为空，则删除后用右子树最小的结点代替（右子树中序遍历第一个结点）/或者用左子树最大的结点代替（左子树中序遍历最后一个节点）

平衡二叉树（AVL）

• 左子树和右子树深度之差不超过1
• 平衡因子=左子树高-右子树高
• 平衡二叉树的插入：调整第一个不平衡的结点为根的树（最小不平衡子树）
• 插入调整：
  LL：右旋
  RR：左旋
  LR：R左旋，L右旋
  RL：L右旋，R左旋
  注：不论删除的是叶结点还是非叶节点，在插入相同的结点，与之前的AVL可能相同也可能不相同

红黑树

• 由于平衡二叉树的插入和删除很容易破坏平衡特性，需要频繁调整。而红黑树的插入和删除很多时候不会破坏“红黑”特性，即便破坏也在常数级时间内完成调整
• 平衡二叉树适用于以查为主，而红黑树适用于频繁插入、删除的场景
• 红黑树是一种二叉排序树：左子树结点值＜根结点结点值＜右子树结点值
• 红黑树要求：①根节点是黑色②叶节点（外部节点、NULL结点、失败结点）均是黑色③不存在两个相邻的红结点④每个结点到任一空叶节点的简单路径上的黑节点数目相同
• 黑高bh：该结点到空叶节点的黑结点数
• 红黑树的性质：①从根节点到叶结点的最长路径不大于最短路径的2倍②有n个内部节点的红黑树高度h≤$2log_2（n+1）$
• 红黑树的查找与二叉排序树和平衡二叉树一样
• 红黑树的插入：
  ①先查找，确定插入位置
  ②新节点是根–染为黑色
  ③新节点是非根–染为红色
  ④若插入新节点满足红黑树定义，则插入结束；反之，需要调整
  调整：①叔叔是黑色的：LL,RR,LR,RL与AVL相同同时需要染色（父爷结点颜色取反）
  ②叔叔是红色的：染色+变新
  （叔父爷取反色，爷爷视为新结点重新调整）

#4.B树和B+树

• B树又称多路平衡查找树，叶子结点为失败结点，最后一层数据称为终端结点
• 定义:设m阶B树①至多m个分支，m-1个关键字②若根结点不是终端结点，则至少有2个子树③除根结点外的所有非叶结点至少有m/2向上取整个分支，m/2向上取整-1个关键字④所有叶结点（失败结点）都在同一层，并且不带信息
• 多数情况下B树的高度不包括失败结点
• B树的高度:$log_m（n+1）≤h≤log_{m/2向上取整}（（n+1）/2）+1$

B树的插入

• 每次插入到终端结点
• 若超过结点关键字上限，则从中间位置（m/2自上取整）裂开为2个结点，中间结点插入父结点（父结点满则继续向上新建结点插入）

B树的删除

• 若是终端结点，直接删除；若不是终端结点，则删除后用直接前躯或后继代替
• 若破坏B树的规则则需要调整
  ①若兄弟可借，借父结点，兄弟结点代替父结点
  ②若兄弟不可借，则将该结点、全部兄弟结点和父结点融合为一个结点

B+树

• 类似于分块查找（分支结点关键字是对应叶结点块内的最大值）
• 每个分支结点最多有m棵子树
• 非叶根结点至少有2棵子树，其他每个分支支结点至少有m/2自上取整棵子树
• 结点的子树个数与关键字个数相同（B树结点的子树个数=关键字个数+1）
• 所有叶结点（B树叶结点为null，B+树叶结点是全部关键字）包含全部关键字及指向相应记录的指针
• B树查找成功可在任何一层，而B+树查找成功只能在叶子结点
• B+树叶结点由一个p指针连接而成，而叶结点顺序排列，支持顺序查找
• 非叶结点只起索引作用，只包含叶结点最大值和对应的指针，不包括对应记录的存储地址

#5.散列表

• 散列表又称哈希表，是一种数据结构，其数据元素的关键字与其存储地址直接相关
• 通过哈希函数建立关键字与存储地址的联系
• 若不同关键字通过哈希函数映射到同一个值，称其为"同义词″，称这种情况为"冲突"

处理冲突的方法:
①拉链法:把所有"同义词"存放在一个链表中
装填因子:表中记录数/散列表长度过
②开放定址法:H_i=（H（key）+d）%m
d的确定:
1）线性探测法:每次向后探测相邻的下一个单元是否为空
$d_i=0，1，2，3…$

• 删除结点不能简单置空，应做一个"删除标记″，进行逻辑删除
• 容易造成同义词，非同义词"聚积（堆积）"现象，严重影响查找效率
• 线性探测法计算查找失败的平均查找长度时，空指针的比较也算做一次比较，同时地址等于m的位置无法通过计算进行比较

2）平方探测法:
$d_ⅰ$=+1，-1，$+2^2$，$-2^2$。。。$+k^2$，$-k^2$
散列表长度m必须是一个可以表示成4j+3的素数，才探测到所有位置
3）伪随机序列法
$d_ⅰ$=某个伪随机序列

③再散列法（再哈希法）
当散列函数冲突时，用下一个散列函数计算一个新地址，直到不冲突
$H_i=RH_i（Key）$,i=1,2,3…,k

常见的散列函数:
①除留余数法:H（key）=key%p
p取一个不大于表长的最大质数
②直接定址法:H（key）=a*key+b或直接=key
适合关键字的分布基本连续
③数字分析法:选取数码分布较为均匀（无规律）的若干位地址
④平方取中法:取关键字的平方值的中间几位作为散列地址
这种方法得到的散列地址与关键字的每位都有关系

#八、排序

#1.排序基本概念

• 算法的稳定性：若$R_i和R_j$对应的关键字相同，排序前后$R_i和R_j$的先后顺序不变则称其是稳定的
• 内部排序：排序期间元素全部存放在内存中
• 外部排序：排序期间元素无法全部同时存放在内存中，需要在内、外存之间移动
• 大多数排序算法都仅适用于顺序存储的线性表

#2.插入排序

直接插入排序

• 直接插入元素，后排元素依次后移
• 空间复杂度O（1），时间复杂度O（$n^2$）
• 是稳定的
• 适用于基本有序的排序表和数据量不大的排序表
• 适用于顺序存储和链式存储

折半插入排序

• 折半查找元素带插入位置，再移动后排元素
• 时间复杂度O（$n^2$）
• 是稳定的
• 对于数据量不是很大的排序表，折半插入排序性能较好
• 适用于顺序存储

希尔排序

• 希尔排序根据折半插入排序改进而来，又称缩小增量排序
• 排序步骤:
  ①第一趟：$d_1=n/2$，将距离为$d_1$的元素视为同一子表
  ②对相应子表进行直接插入排序
  ③$d_2=d_1/2$，将距离为$d_2$的元素视为同一子表
  以此类推直到$d_i=1$
• 希尔本人推荐增量d每次缩小一半，但实际可能存在不同的增量d的变化
• 空间复杂度O（1）
• 时间复杂度最坏为O（$n^2$）,n再一定范围内时为O（$n^{1.3}$）
• 是不稳定的
• 适用于顺序存储

#3.交换排序

冒泡排序

• 从前往后（或从后往前）两两比较相邻元素的值，若为逆序，则交换他们，直到序列比较完。第二趟从下一个元素再依次比较相邻元素
• 空间复杂度O（1），时间复杂度O（$ n^2 $）
• 是稳定的

快速排序

• 待排序表中任取一个元素作为枢轴（或基准，通常取首元素），通过一趟排序将待排序表划分为两个部分，前半部分比该基准小，后半部分比该基准大
  再分别递归的对两个子表重复上述过程，直到每部分只有一个元素或空为止
• 空间复杂度平均O（$log_2n$），最坏位O（n）（递归栈占O（n）位）；时间复杂度最坏O（n^2）,最好和平均O（$nlog_2n$）
• 若每一次选中的基准将排序序列划为均匀的两个部分，则递归深度最小，算法效率最高
• 是不稳定的

#4.选择排序

简单选择排序

• 每次选择最小的元素与未排序的首位交换
• 空间复杂度0（1），时间复杂度O（$ n^2 $）
• 是不稳定的

堆排序

• 大根堆（根≥左、右孩子结点），小根堆相反
• 把所有非终端结点都检查一遍，不满足大根堆的要求，则进行调整，当前结点与最大的一个孩子互换
• 空间复杂度O（1）；时间复杂度，建堆O（n），排序$nlog_2n$，总的时间复杂度为$nlog_2n$
• 是不稳定的
• 堆排序的插入：
  插入表尾，依次与父节点比较，表现为沿着二叉树一路上升
• 堆排序的删除：
  被删除元素用最后一个元素代替，然后依次比较左、右孩子，表现为一路下坠

#5.归并排序和基数排序

归并排序

• 将两个或两个以上的有序表组合成一个新的有序表
• 从小大大依次比较，较小的依次放入一个新的有序表里，以此类推
• 2路归并（归并2个有序序列）（常用），4路归并（归并4个有序序列）等
• 空间复杂度O（n），时间复杂度O（$nlog_2n$）
• 是稳定的

基数排序

• 基于关键字各位大小进行排序
• 依次按个位、十位、百位构造递减队列
• 按关键字位权重递增的次序进行分配和收集（一趟）
• 最高位关键字（百位），最低位关键字（个位），基数r（关键字可能的取值数量）
• 空间复杂度O（r），时间复杂度O（d（n+r））（d是分配的趟数，三位数就是三趟…）
• 是稳定的

#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（nlog_2n）$	$O（nlog_2n）$	$O（n^2）$	$O（nlog_2n）$	否
堆排序	$O（nlog_2n）$	$O（nlog_2n）$	$O（nlog_2n）$	$O（1）$	否
2路归并排序	$O（nlog_2n）$	$O（nlog_2n）$	$O（nlog_2n）$	$O（n）$	是
基数排序	$O（d（n+r））$	$O（d（n+r））$	$O（d（n+r））$	$O（r）$	是

#7.外部排序

外存、内存之间以“块”位单位进行数据交换
外部排序：数据元素太多，无法一次全部读入内存进行排序
外部排序时间开销：读写外存的时间（主要时间）+内部排序所需时间+内部归并所需时间
时间优化：（增加归并路数、减少归并趟数以减少读写外存时间）

• 多路归并
• 减少初始归并段数量

多（k）路平衡归并（增加归并路数）：

• 最多只有k个段归并位一个
• 每一趟归并，若有m个归并段参与归并，则经过这一趟处理得到m/k向上取整个新的归并段

败者树

• 可视为一颗完全二叉树（多了一个根）。k个叶子节点分别是当前参与比较的元素，非叶子节点用来记忆左右子树中的“失败者”，而让胜者往上继续进行比较，一直到根结点
• 对于k路归并，第一次构造败者树需要对比关键字k-1次；有了败者树，选出最小元素，只需比较关键字$log_2k向上取整$次

置换-选择排序（生成初始归并段）

• 内存工作区选出最小的写入第一个归并段，并记录这个最小值MINIMAX，每当内存工作区有空位就输入下一个待排序文件
• 选出内存工作取中的最小值与MINIMAX进行比较，若大于MINIMAX，则进入归并段1；否则待定，选出第二大的元素与MINIMAX进行比较。
• 若内存工作区所有元素都比MINIMAX都小，则开辟归并段2，再如上比较

最佳归并树

• 归并树的带权路径长度WPL=读磁盘次数=写磁盘次数=$\frac{1}{2}$I/O次数
• 最佳归并书构造：先归并少的，后归并多的（哈夫曼树构造）
• 注意 ：对于k叉归并，若初始归并段数量无法构成严格的k叉归并树，则需要补充几个长度位0的“虚段”，在进行k叉哈夫曼树的构造（补充$（n_0-1）$%（k-1））