数据结构学习笔记
第一章——绪论
1.数据类型：原子类型、结构类型、抽象数据类型
原子类型——不可分
结构类型——可再分解为若干成分的数据类型
抽象数据类型——由用户定义，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。
包括：逻辑结构+运算
①抽象数据结构可以定义一个完整的数据结构 。
②数据，数据元素(个体)，数据项 。
数据对象——同类型的数据元素的集合 。
2.数据结构：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
数据结构三要素——数据的逻辑结构，数据的存储结构，数据的运算
逻辑结构——
存储结构——顺序存储、链式存储、索引存储、散列存储
顺序存储：可以实现随机存取，每个元素占用最少的存储空间。
只能使用相邻的一整块存储单元，因此可能产生较多的外部碎片。
链式存储：不会出现碎片现象，能充分利用所有存储单元。
每个元素因存储指针而占用额外的存储空间，且只能实现顺序存储。
索引存储：检索速度快。
附加额外的索引表额外占用存储空间，增加删除数据时也花费较多时间。
散列存储：检索、增加和删除结点的速度很快。
若散列函数不好，可能出现元素存储单元的冲突。
①**同样的数据元素，可以组成不同的数据结构。不同的数据元素，可以组成相同的数据结构。
②链式存储中各个结点的存储空间可以不连续，但是结点内的存储单元地址必须连续。
③顺序存储结构和链式存储结构都可以进行顺序存取。
④算法的设计取决于逻辑结构，算法的实现取决于物理结构。
⑤对于两种不同的数据结构。二者的逻辑结构和物理结构可能相同**。
3.逻辑结构和存储结构
逻辑结构：结构定义中是对操作对象的描述，描述数据元素之间的逻辑关系。
例如，线性结构，树形结构，图状结构或网状结构。它们都属于逻辑结构。
存储结构：又称物理结构，是数据结构在计算机中的表示。例如，数组，指针。
1 | 线性表：线性表是具有相同特性的数据元素的一个有限序列。 |
线性表、有序表、栈、队列、二叉树是逻辑结构。
顺序表，链表，哈希表、数组、线索二叉树、循环队列是存储结构。
逻辑结构和存储结构的区别点在于
数据的逻辑结构是独立于在计算机中的存储结构的，数据的存储方式有多种不同的选择。
例如栈是一种逻辑结构，它可以用顺序存储也可以用链式存储。
存储结构是既可以描述逻辑结构又可以描述存储结构和数据运算，必须包含以上三种元素。
①**逻辑结构是独立于存储结构的。但是存储结构是逻辑结构在计算机上的映射，因此存储结构不能独立于逻辑结构** 。
②**循环队列是顺序表表示的队列。因此循环队列为存储结构** 。
③**链式存储结构比顺序存储结构能更方便地表示各种逻辑结构。
④XX是逻辑和存储结构。没有这一种说法**。
4.算法
程序=数据结构+算法
算法的特性：有穷性、确定性【相同输入只有相同输出】、可行性、输入、输出
算法的评判标准：正确性、可读性、健壮性、高效性、低存储需求
5.时间复杂度：
加法规则——T(n)=T1(n)+T2(n)=O(f(n))+O(g(n))=O(max(f,g)) 【只保留最高阶】
乘法规则——T(n)= T1(n)×T2(n)=O(fn))×O(g(n))= O(f×g) 【阶数相加】
一层循环：1.列出循环趟数t以及每轮循环i的变化值 2.找到t与i的关系① 3.确定循环停止条件②
4.联立①②两式，解方程 5.t为结果
二层循环：1.列出外层循环中i的变化值 2.列出内层语句的执行次数 3.求内层的执行次数的和，写结果
递归：将表达式列出根据表达式进行判断
PS：将n看作i，作为一重循环进行计算。
6.空间复杂度
空间复杂度——该算法所需的存储空间。
O(1)——算法原地工作，所需要的辅助空间为常量，问题规模与n无关。
第二章——线性表
顺序存储
1.线性表：相同数据类型、有限序列。
2.顺序表：线性表的顺序存储(逻辑上相邻的数据元素物理上也相邻)【数组】
实现方式——静态分配：使用静态数组实现，大小一旦确定就无法改变
动态分配：使用动态数组实现；顺序表存满时，可再用malloc动态扩展顺序表的最大容量；
需要将数据元素复制到新的存储区域，并用free函数释放原区域。
L.data = (int*)malloc(sizeof(int) * size);
特点——随机访问/随机存取/随机读写；存储密度高；
扩展容量不方便；插入、删除数据元素不方便；顺序存储需要一段连续的存储空间，不够灵活。
基本操作——插入：ListInster(&L,i,e)，将元素e插入到L的第i个位置。O(n)
插入位置之后的元素都要后移
删除：ListDelete(&L,i,&e)，将L的第i个元素删除，并用e返回。O(n)
删除位置之后的元素都要前移。
按位查找：GetElem(L,i)，获取表L中第i个位置的元素的值。O(1)
按值查找：LocateElem(L,e)，在顺序表L中查找第一个元素值等于e的元素，并返回其位序。O(n)
①**在顺序表和在链表上顺序输出前i个元素的效率相同。
交换第i号元素和第j号元素，则顺序表效率更高(链表找前驱后继) 。
②给定n个元素的一维数组，建立一个有序单链表的最低时间复杂度为O(nlog2n)** 。
③**data[3]。数组中最多存放3个元素** 。
长度为n的线性表有n个元素 。
数组A[n]的下标范围为0 ~ n-1，如果写出A[0…n]，则说明下标范围为0 ~ n。
链式存储
1.单链表：一个结点存储一个数据元素。
通常用头指针L来标识一个单链表。
实现方式：①不带头结点(空表判断L=NULL)②带头结点(空表判断L->next=NULL)
操作：插入、删除、查找、求表长、建表【头插法(常用于链表的逆置)、尾插法】
头结点：在单链表第一个结点之前附加一个结点，称为头结点。
头结点的数据域可以不设任何信息，也可以记录表长等信息
判空【有头结点(L==NULL)、不带头结点(L->next=NULL)】
头指针和头结点的区别：无论是否有头结点，头指针始终指向链表的第一个结点，通常用头指针标识一个单链表。
而头结点是带头结点的链表中的第一个结点
**结点指针：**若p为结点指针，*p为结点本身 。
p->data 等价于 ( *p).data
LNode * p = (LNode *)malloc(sizeof(LNode));
**建表：**头插法（逆置）、尾插法（顺序）
①**单链表的插入必须先让新结点插入，再让新结点被插入** 。
②**在带有头结点和尾指针的(循环)单链表中删除单链表中的最后一个元素。时间复杂度为O(n)** 。
因为删除最后一个元素后，要将其前驱结点的next设为NULL。
③**头结点不算线性表的长度** 。
④**将长度为n的单链表链接在长度为m的单链表后面，其时间复杂度为O(m)**。
扫描m找到尾结点连接起来。
2.双链表：
初始化——头结点的prior,next都指向NULL
操作——插入、删除、遍历
3.循环单链表：从头到尾时间复杂度为O(n)，从尾到头的时间复杂度为O(1)
空表：
非空：
循环双链表：
空表：
非空： 
①**有时对循环单链表不设头指针而只设尾指针** 。
若设头指针，对在表尾插入元素需要O(n)。
而若设尾指针，r->next即为头指针，对在表头或表尾插入元素都只需要O(1)。
②**判空：头指针的指针域与head的值相等**。
4.静态链表：用数组的方式实现的链表
优点：增删改查操作只需修改指针，不需要移动元素
缺点：不能随机存取，只能从头结点开始依次往后查找；容量固定不可变
PS：需要注意静态链表中数据和游标都占内存。因此地址为addres+8*2（int类型）
①**静态链表通常以next=-1作为结束的标志**。
1 |
|
5.顺序表与链表的对比
**逻辑结构：**都属于线性表
**存储结构：**顺序表：支持随机存取，存储密度高。但大片连续空间分配不方便，改变容量不方便
链表：离散的小空间分配方便，改变容量方便。但不可随机存取，存储密度低
**基本操作：**创建——顺序表的创建需要预分配一片连续空间
链表的创建只需分配一个头结点
销毁——顺序表静态分配的销毁由系统自动回收，动态分配的需要手动free(p)
链表的销毁free(p)
增删——顺序表插入/删除元素要将后续元素都后移/前移，时间复杂度为O(n)，时间开销主要在于移动元素
链表修改对应的指针即可，时间复杂度为O(n)，时间开销主要在于查找目标元素
查找——顺序表，按位查找O(1)；按值查找O(n)或O(log2n) (有序时折半查找)
链表，按位查找O(n)；按值查找：O(n)
逻辑结构与物理结构：顺序表逻辑上相邻的元素物理上也相邻
链表逻辑上相邻的元素，物理位置上不一定相邻
第三章——栈、队列
栈
1.栈是操作受限的线性表、只能在栈顶插入、删除(先进后出/后进先出LIFO)
2.顺序栈：顺序存储、用静态数组实现、并需要记录栈顶指针
PUSH——入栈，POP——出栈
两种实现：①初始化时top=-1，指针指向栈顶元素S.data[S.top] 。满栈——top=MaxSize-1。先加后入，先出后减。
②初始化时top=0，指针指向接下来要插入元素的位置。满栈——top=MaxSize。先入后加，先减后出。
共享栈：两个栈共享一片内存区域，两个栈从两边往中间增长。
初始化——0号栈栈顶指针初始时top0=-1，1号栈栈顶指针初始化时top1=MaxSize
栈满条件——top0+1=top1。
节省存储空间，防止发生上溢。
3.链栈：用链式存储方式实现的栈。
链栈没有头结点，Lhead指向栈顶元素。
①C语言标识符——以字母，数字，下划线组成；开头不能为数字
③系统调用时，系统要用栈保存必要的信息
②n个不同元素进栈，出栈元素不同队列的个数为
(catalan数)。
队列
1.队列是操作受限的线性表、只能在队尾插入、队头删除(先进先出FIFO)
为了区分队空或队满①牺牲一个存储空间来区分②增加一个表示元素个数的数据
③增设tag表示当前操作为出队列/入队列
2.顺序存储：
实现思想：用静态数组存放数据元素，设置队头(front)/队尾(rear)指针。
循环队列——用模运算(取余)将存储空间在逻辑上变为“环状”
Q.rear=(Q.rear+1)%MaxSize 【MaxSize为元素数量】
**两种实现：**①rear指向下一个要插入的位置（指向队尾元素的后一个位置）
初始化——Q.front=Q.rear=0
入队—— Q.data[Q.rear]=x；Q.rear=(Q.rear+1)%MaxSize 先入后加
出队—— x=Q.data[front]；Q.front=(Q.front+1)%MaxSize 先出后加
判空——Q.front=Q.rear
判满——(Q.rear+1)%MaxSize=Q.front
②rear指向队尾元素
初始化——Q.front=0；Q.rear=n-1【数组下标为0~n-1】
入队—— Q.rear=(Q.rear+1)%MaxSize；Q.data[Q.rear]=x 先加后入
出队—— x=Q.data[front]；Q.front=(Q.front+1)%MaxSize 先出后加
判空——(Q.rear+1)%MaxSize=Q.front
判满——(Q.rear+2)%MaxSize=Q.front
3.链式存储
链队有头指针和尾指针
插入——插入新数据后，将尾指针指向新插入的数据
删除——链队一般都有头结点
队头设置在链表链头的位置。
最适合作链队的链表是带队首指针和队尾指针的非循环单链表 。
4.双端队列：允许从两边插入、删除的队列
①输入受限的双端队列——允许从两端删除、一端输入
②输出受限的双端队列——允许从两端输入、一端删除
对输出序列的合法性判断(栈合法的一定合法)
①链式队列的长度也是有限的【内存空间限制】
链队不能根据队首指针和队尾指针计算队列的长度。
栈和队列的应用
1.表达式：中缀表达式、后缀表达式、前缀表达式
中缀表达式 后缀表达式 前缀表达式
a+b ab+ +ab
a+b-c ab+c- -+abc
a+b-c*d ab+cd *- -+ab *cd
后缀表达式考点：
中缀转后缀——①按“左优先原则”确定运算符的运算次序。【只要左边的运算符能先计算，就优先算左边】
【仍遵守先加后减的原则，但是若为A+B-C*D。 可以先进行A+B再进行C * D，然后二者相减】
②根据①中的次序，将各个运算符和与之相邻的两个操作数按<左操作数 右操作数 运算符>的规则合体。
后缀转中缀——从左往右扫描，每遇到一个运算符，就将<左操作数 右操作数 运算符>变为(左操作数 运算符 右操作数)
计算—— 从左往右扫描，遇到操作数入栈，遇到运算符则弹出两个栈顶元素运算后入栈 【先弹出的元素是“右操作符”】
前缀表达式：
中缀转前缀——①按“右优先”原则确定运算符的运算次序。【只要右边的运算符能先计算，就优先算右边】
②根据①中确定的次序，将各个运算符和与之相邻的两个操作数按<运算符 左操作数 右操作数>规则合体
计算—— 从右往左扫描，遇到操作数入栈，遇到运算符则弹出两个栈顶元素后入栈 【先弹出的元素是”左操作符”】
2.栈的应用：
在括号匹配中：依次扫描所有字符，遇到左括号入栈，遇到右括号出栈，检查是否匹配。
匹配失败情况——左括号单身；右括号单身；左右括号不匹配
在表达式中：先弹出后入栈
中缀转后缀：
①遇到操作数。直接加入到后缀表达式中
②遇到界限符。遇到”(“直接入栈，遇到”)”则依次弹出栈内运算符并加入后缀表达式，直到弹出”(“为止。
注意——“(“不加入后缀表达式。
③遇到运算符。依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式
若碰到”(“或栈空则停止。之后再把当前运算符入栈。
④按上述处理完所有字符后，将栈中剩余运算符依次弹出，并加入后缀表达式中。
中缀表达式的计算：
①初始化两个栈，操作数栈，运算符栈
②若扫描到操作数，压入操作数栈
③若扫描运算符\界限符，则按照“中缀转后缀”相同的逻辑压入运算符栈中
④期间也会弹出运算符，每弹出一个运算符，就需要再弹出两个操作数栈的栈顶元素并执行相应运算，运算结果再 压回操作数栈
在递归中：函数调用需要栈存储(调用返回地址、实参、局部变量)。
函数调用的特点——最后被调用的函数最先执行
3.队列的应用：
树的层次遍历：
图的广度优先遍历：
队列在操作系统中的应用：
多个进程争抢使用有限的系统资源时，FCFS(先来先服务)是一种常用策略(例:CPU的资源分配、打印数据缓存区)。 页面替换算法。
数组和特殊矩阵
1.数组定义：
除非特殊说明，数组下标默认从0开始
2.特殊矩阵和压缩存储
压缩存储：为多个值相同的元素只分配一个存储空间，对零元素不分配空间
特殊矩阵：对称矩阵、上下三角矩阵、对角矩阵
对称矩阵：
aij=aji
存储策略：只存储主对角阵+上/下三角区
三角矩阵：
下三角矩阵：除了主对角线和下三角区，其余的元素都相同
存储策略：下三角存储。一维数组的最后一个位置存储常量c
对角矩阵：
当|i - j|>1时，有aij=0
存储策略：只存储带状部分
3.稀疏矩阵
定义：非零元素个数远少于矩阵元素个数
存储策略：
顺序存储——三元组<行、列、值> 【行列标从1开始】
链式存储——十字链表法
①**稀疏矩阵采取压缩存储的缺点：丧失随机存取的特性**
②**采用三元组表存储稀疏矩阵M，除了三元组表，还需要M的行数和M的列数。 **
第四章——串
串的定义
串，即字符串由零个或多个字符组成的有限序列。一般记为S=’a1a2an‘
其中，S为串名，用单引号括起来串的值。
ai可以为字母、数字或其他字符。n为串的长度。n=0为空串。【每个空格字符占1B】
子串：串中任意个连续的字符组成的子序列。
主串：包含子串的串。
字符的主串中的位置：字符在主串中的序号【从1开始数】
子串的主串中的位置：子串第一个字符在主串中的序号【从1开始数】
串的数据对象限定为字符集【中文、英文、数字、标点】
采用不同的编码方式，每个字符所占空间不同。考研中默认每个字符占1B。
串的基本操作
串的基本操作，如：增删改查都以子串为操作对象
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值相同的子串，则返回它在主串中第一次出现的位置；否则函数值为0
StrCcompare(S,T)：比较操作。若S>T，则返回值>0。若S=T，则返回值=0。若S<T，则返回值<0。
串的存储结构
顺序存储
1 | //定长顺序存储 |
1 | //动态存储 |
链式存储
1 | //每个字符1B,每个指针4B。存储密度低 |
1 | //可以提高存储密度 |
基于顺序存储实现基本操作
串的模式匹配
朴素模式匹配
让主串中每个长度与模式串长度相同的子串进行匹配，若不匹配让下个子串继续匹配。
最坏时间复杂度=O(nm)【n为主串长度,m为模式长度】
KMP算法
算法思想：
利用已经匹配过的信息，尽量减少不必要的比较次数，从而提高字符串匹配的效率。
KMP算法构建一个部分匹配表（next数组），来记录模式串中每个位置之前的子串中，最长的相等前缀和后缀的长度。这样，在匹配过程中，当出现不匹配的情况时，可以根据部分匹配表中的信息，将模式串向右移动一定的距离，而无需从头开始重新匹配。
根据模式串T，求出next数组。利用next数组进行匹配（主串指针不回溯）
next数组：
next[1]=0 next[2]=1
在不匹配的位置前，划分界线。模式串一步一步往右移，直到分界线前面的都可以匹配上，或模式串跨过分界线为止。
此时j指向哪儿，next数组就是多少。
最坏时间复杂度=O(m+n)【next数组为O(m)，匹配过程为O(n)】
next数组的优化：
算法思想：
若当前不匹配的字符转换为next数组继续匹配时，二者的字符相同，则必然不匹配。
next数组所指字符与原本不匹配的字符是否相同。
若不相同，则next数组不变。若相同，则next数组的值等于失败的位置的next数组的值。
nextval[1]=0 
1 | if(T.ch[next[j]]==T.ch[j]) |
第五章——树
基本概念
1.基本术语
**结点之间的关系：**祖先结点——祖先是指，从根节点到该节点所经分支上的所有节点
子孙节点——子孙是指，以某节点为根的子树中任一节点都称为该节点的子孙
父节点、孩子节点
兄弟节点、堂兄弟结点——双亲在同一层的结点互为堂兄弟结点
**结点、树的属性：**结点的深度——从根节点开始自顶向下逐层累加 结点的高度——从叶节点开始自底向上逐层累加
树的深度——树中结点的最大层数
结点的度——一个结点的孩子数
树的度——树中结点的最大度数
结点之间的路径——只能从上往下
路径长度——路径上所经过的边的个数
树的路径长度——树根到每个结点的路径长度的总和
有序树 VS 无序树：从逻辑上看，各子树是否有序，位置是否可以互换。
森林：由m(m≥0)个互不相交的树组成森林。
2.树的性质
结点数=总度数+1。
度为m的树第i层至多有个m^(i-1)^结点。
高度为h、度为m的树，结点数最少为h+m-1个
具有n个结点的m叉树的最小高度为
高度为h的m叉树，结点数最少为h个
高度为h的m叉树，结点数最多为
3.度为m的树和m叉树的区别：
度为m的树：任意结点的度≤m、至少有一个结点度等于m。一定是非空树。至少有m+1个结点
m叉树：任意结点的度≤m、允许所有结点的度都≤m。可以是空树。m叉树的每个结点最多只能有m个孩子的树
二叉树
1.二叉树可为空树。
二叉树是有序树，左右子树不可颠倒。二叉树的孩子的左右次序是确定的，并不是相对于另一个结点而言的。
这与度为2的有序树不同，度为2的有序树的孩子的左右次序是相对于另一个孩子而言的，若只有一个孩子则无需区分.
2.特殊二叉树
满二叉树——高度为h，含有2^h^-1个结点的二叉树。 若有双亲，为⌊i/2⌋。左孩子为2i，右孩子为2i+1
完全二叉树——在满二叉树的基础上可去掉若干个编号更大的结点。最多只能有一个度为1的结点。
二叉排序树——左子树关键字<根节点关键字<右子树关键字。
平衡二叉树——左右子树深度差不超过1。
3.性质
二叉树—— n0=n2+1 (度为0的结点数=度为2的结点数+1)
第i层至多有2^i+1^个结点
高度为h的二叉树至多有2^h^-1个结点
完全二叉树——具有n个结点的完全二叉树的高度h=⌈log2(n+1)⌉或h=⌊log2(n)⌋+1
对于完全二叉树，可以由结点数n推出为0、1、2的结点个数为n0、n1和n2。
（突破点：完全二叉树最多只有一个度为1的结点）
4.存储结构
顺序存储结构——适合存储满二叉树或完全二叉树。
用一组地址连续的存储单元依次自下而上、自左至右存储完全二叉树上的结点元素。
0表示不存在的空结点。
链式存储结构——在含有n个结点的二叉链表中，含有n+1个空链表。
为了进一步寻找父指针——三叉链表【加一个指针指针指向父结点】空链表数**n+2**。
①在树的顺序存储中，即使无结点，也要补上。所需的存储空间的个数是完全二叉树的结点的个数。
5.遍历
三种方法：先序【根左右，前缀表达式】、中序【左根右，中缀表达式(无括号)】、后序【左右根，后缀表达式】。
三者都为O(h)。
层次遍历：①初始化一个辅助队列。
②根节点入队。
③若队列非空，队头结点出队，访问该结点，让其左右孩子依次入队，插入队尾。
④重复③直到队列为空
由遍历序列构造二叉树：前序+中序(根节点在最前面)、后序+中序(根节点在最后面)、层序+中序。
①先序序列为……的不同二叉树的个数 == 以序列……次序入栈，则出栈个数为多少。
②中序序列为……==以……为出栈次序。
③**在二叉树中有两个结点m,n。若m是n的祖先，则使用后序遍历可以找到从m到n的路径**。
线索二叉树
线索——指向前驱/后继的指针称为线索
**存储结构：**在普通二叉树结点的基础上。增加两个标志位ltag和rtag。
当ltag == 1时，表示lchild指向前驱；当ltag == 0时，表示lchild指向左孩子。
当rtag == 1时，表示rchild指向后继；当rtag == 0时，表示rchild指向右孩子。
第一个结点和最后一个结点的tag都为1。
三种线索二叉树：
中序线索二叉树——
先序线索二叉树——以先序遍历序列为依据进行”线索化”
后序线索二叉树——以后序遍历序列为依据进行”线索化”
易错点：第一个结点和最后一个结点的处理，NULL依然算；
在先序线索化中，要注意死循环问题。当ltag==0时，才能对左子树进行先序线索化。
线索二叉树找前驱/后继：
除非使用三链表二叉树
①**后序线索树的遍历需要栈的支持。
②一颗左子树为空的二叉树在先序线索化后，其中空的链域的个数是2。(首结点的左子树为空，尾结点为叶结点)**
一个二叉树，在线索化后，其中最多的空的链域的个数是2。
③并不是每个结点可以通过线索可以直接找到它的前驱或后继。
④**线索二叉树利用二叉树的n+1个空指针来存放结点的前驱和后继信息**。
树的存储
1.双亲表达法——顺序存储结点数据，结点中保存父节点在数组中的下标。
【适合找父亲、不适合找双亲】【适用场景：并查集】
孩子表达法——顺序存储结点数据，结点中保存孩子链表头指针(顺序+链式存储)。
【适合找孩子、不适合找双亲】【适用场景：服务流程树】
孩子兄弟表示法——用二叉链表存储树【左孩子、右兄弟】。
孩子兄弟表示法存储的树，从存储视角来看形式上和二叉树类似。
2.森林与二叉树的转换
本质：用二叉链表存储森林——左孩子、右兄弟。
森林中各树的根节点视为兄弟关系。
①以分支来考虑一个树的时候，一个分支代表一个叶结点，分支数=叶结点数=有兄弟的结点数+1。
②n个非终端结点——>会有n个结点没有右兄弟。因为这个非终端节点的最后边的那个孩子没有右兄弟。
树和森林的遍历
1.树的遍历
先根遍历：遍历序列与这颗树对应的二叉树的先序遍历相同。深度优先遍历。
后根遍历：遍历序列与这颗树对应的二叉树的中序遍历相同。深度优先遍历。
层次遍历：广度优先遍历。使用队列实现。
2.森林的遍历
先序遍历森林：等价于对各个子树做先根遍历
中序遍历森林：等价于对各个子树做后根遍历
哈夫曼树
1.概念
结点的权：某种特定含义的数值。
结点的带权路径长度=根到结点路径长度*该结点的权值。(根节点不算，因此要高度-1)
树的带权路劲长度(WPL)=树中所有叶子结点的带权路径长度之和。【WPL=非叶结点的权值之和】
加权平均长度：WPL /（叶结点之和）
哈夫曼树(最优二叉树)：在含有给定的n个带权叶节点的二叉树中，WPL最小的树。
2.构造哈夫曼树
每次选取两个根节点权值最下的树合并，并将二者权值之和作为新的根节点的权值。
哈夫曼树不唯一，但WPL必然都是最小值。
3.性质
哈夫曼树的值肯定是叶结点。
哈夫曼树的结点总数=2n-1【n为叶结点个数】
哈夫曼树不存在度为1的结点
3.哈夫曼编码
将字符频次作为字符结点权值，构造哈夫曼树，即可得哈夫曼编码，可用于数据压缩。
前缀编码：没有一个编码是另一个编码的前缀。
固定长度编码：每个字符用相等长度的二进制位表示。
可变长度编码：允许对不同字符用不等长的二进制位表示。
0转左孩子，1转右孩子。
①进行哈夫曼编码，可得到n个不同的码字【n为叶结点个数】。
②树的带权路径长度有两个计算方法a:叶子节点的带权路径长度。
b:所有分支结点的带权路径长度。
③在定长编码集中，所有字符都在同一层次，且都为叶结点。
并查集
用互不相交的树，表示多个集合。
如何判断两个元素是否属于同一个集合？
查明这两个元素的根节点是否相同
如何把两个集合合并？
让一棵树变为另一棵树的子树
使用双亲表示法来实现并查集。
Union操作优化：让小树合并到大树上，以保证树的高度增长缓慢。
可以让根结点保留，树的高度的负值。
该方法构造的树高不超过：⌊log2n⌋+1
优化后Find时间复杂度为O(log2n)
Find操作优化：压缩路径
压缩路径——Find操作先找到根节点，再将查找路径上所有结点都直接挂到根节点下
可以使树的高度不超过O(a(n))【a(n)是一个增长很慢的函数】
①可以使用并查集来检测图中是否存在环路。
②并查集可以用于实现克鲁斯卡尔算法。
③并查集可以用于判断无向图的连通性。
第六章——图
基本概念
1.定义：
G=(V,E)，顶点集V，边集E。顶点个数也称图的阶
无向图(无向边/边)——( )、有向图(有向边/弧)——< >
无向图——顶点的度【依附于顶点的边数】
有向图——顶点的度=出度【以顶点为起点】+入度【以顶点为终点】
2.点到点的关系：
路径、回路、简单路径【顶点不重复的路径】、简单回路
路径长度——路径上边的个数
点到点的距离——最短路径
无向图顶点的连通性、连通图
有向图顶点的连通性、强连通图——强连通：v->w和w->v都有路径
3.图的局部：
子图
连通分量——极大连通子图【极大连通子图：子图必须连通，且包含尽可能多的顶点和边】无向图
强连通分量——极大强连通子图【极大强连通子图：子图必须强连通，且包含尽可能多的顶点和边】有向图
连通无向图的生成树——包含全部顶点的极小连通子图(尽可能少的边)【减去一条边为非连通、加上一条边回路】
非连通无向图的生成森林——各连通分量的生成树
4.几种特殊形态的图：
完全图：
无向图——任意两个节点之间都有边
有向图——任意两个结点之间都存在方向相反的两条弧
稀疏图、稠密图【对边而言】
有向树——一个定点入度为0、其余顶点入度为1的有向图
生成树——包含全部顶点的极小连通子图【n-1条边，少一条边变非连通图，多一条边形成回路】
生成森林——多个生成树构成生成森林
简单图：不存在重复的边，不存在自身到自身的边
5.特点
①从无向图的任意顶点出发进行一次深度优先搜索即可访问所有顶点，则该图为连通图。
存储结构
1.邻接矩阵法
有边设为1，没边设为0。【有向图从行元素到列元素。出度：行中为1的元素数。入度：列中为1的元素数】
A^n^的元素A^n^[i][j]等于由顶点i到顶点j的长度为n的路径的数目
存储带权图：有边为权值，无边为0/∞
空间复杂度——O(V^2^)
2.邻接表法
并不是从1到2再到5，而是1号指向2号也指向5号。
顺序+链序；表示法不唯一，空间复杂度为
顶点表结点，边表结点。
3.邻接多重表法——链式存储无向图
表示法不唯一，空间复杂度为O(|V|+|E|)
4.十字链表法——链式存储有向图
表示法不唯一，空间复杂度为O(|V|+|E|)
①若一个有向图的邻接矩阵的对角线以下的元素为0，则该图的拓扑序列必定存在。
遍历
1.广度优先遍历(BFS)
类似于树的层序遍历
算法要点：需要一个辅助队列；如何从一个结点找到与之邻接的其他结点。visit数组防止重复访问。
如何处理非连通图——在BFS()外进行for循环，判断数组是否全部为true。
复杂度：空间复杂度——O(V)
时间复杂度——邻接矩阵O(V^2^) 邻接表O(V+E)
广度优先生成树：由广度优先遍历确定的树。
邻接矩阵存储的图表示方式唯一，遍历序列、生成树也唯一。
邻接表存储的图表示方式不唯一，遍历序列、生成树也不唯一。
遍历非连通图可得广度优先生成森林。
2.深度优先遍历(DFS)
算法要点：递归的深入探索未被访问过的邻接点(类似于树的先根遍历)；如何从一个结点找到与之邻接的其他结点。
visited数组防止重复访问。
如何处理非连通图——在DFS()外进行for循环，判断数组是否全部为true。【递归——栈】
复杂度：空间复杂度——O(V)
时间复杂度——邻接矩阵O(V^2^) 邻接表O(V+E)
深度优先生成树：由深度优先遍历确定的树。
邻接矩阵存储的图表示方式唯一，遍历序列、生成树也唯一。
邻接表存储的图表示方式不唯一，遍历序列、生成树也不唯一。
遍历非连通图可得深度优先生成森林。
深度优先走到头的时候，回溯到上一个结点而不是，从头开始。
3.图的遍历和图的连通性
无向图：DFS/BFS的调用次数=连通分量数（图必须连通，且包含尽可能多的顶点和边）。【若为连通图仅需一次】
有向图：若从起始顶点到其他顶点都有路径，则只需调用一次DFS/BFS函数。
对于强连通图，从任意结点出发都只需要调用一次DFS/BFS函数。
图的应用
最小生成树
树的权值之和最小的树。树形不唯一但权值和唯一。
普利姆算法(Prim)：选取与当前结点边权值最小的结点，然后加入其中。
时间复杂度——O(|V|^2^)。
适用于边稠密的图。
克鲁斯卡尔算法(Kruskal)：选取权值最小还未被选择的边，然后让两端结点连接。若两端结点已连通则选择下一条.
时间复杂度——O( |E| log2 |E| )
适用于边稀疏、顶点较多的图。
最短路径
单源最短路径
BFS算法
添加两个数组——记录最短路径长度d[]，记录前驱结点path[]。
时间复杂度——邻接矩阵O(V^2^) 邻接表O(V+E)
Dijkstra算法(带权图、无权图)
**算法思想：**两个辅助数组——dist[]【记录从源点到其他各点的最短路径长度。有弧为权值。无弧为∞】
path[]【从源点到顶点i之间的最短路径的前驱结点】
初始——若从Vo开始，令final[0]=ture; dist[0]=0; path[0]=-1。
其余顶点final[k]=false; dist[k]=arcs[0] [k]; path[k]=(arcs[0] [k] == ∞) ?-1 :0。
n-1轮循环——循环遍历所有顶点，找到还没确定最短路径，且dist最小的顶点Vi，令finali]=ture。
检查所有邻接自Vi的顶点，对于邻接自Vi的顶点Vj。
若final[j]==false且 dist[i]+arcs[i]j]< dist[j]，则令dist[j]=dist[i]+arcs[i][j]; path[j]=i。
(注: arcs[i]i]表示Vi到Vj的弧的权值)
**时间复杂度：**O(|V|^2^)
不适用于带负权值的情况
画图——
①Dijkstra算法也可以求所有顶点间的最短路径，重复|V|次，总的时间复杂度为O(|V|^3|^)。
②当带权连通图的任意一个环中包含的边的权值不同时，最小生成树唯一。
③Dijkstra算法可以得到生成树，但不一定使最小生成树。
各顶点间的最短路径
Floyd算法(带权图、无权图)
算法思想：
递推产生一个n阶方阵序列A^(-1)^，A^(0)^， A^(n-1)^， 其他A^(k)^[i][j]表示从顶点vi到顶点vj的路径长度，k表示绕行第k个结点的运算步骤。
初始——对于任意两个结点若有边记录权值，若无边记录∞
后续——加入第k个结点作为中转结点后，若路径长度缩短，则此路径代替新路径。改变A^(k)^和path中的值
两个辅助二维数组——A^(k)^【记录从点到点的最短路径长度】
path^(k)^【中转结点】
**空间复杂度：**O(|V|^2^)
**时间复杂度：**O(|V|^3^)
可解决边带负权值的情况，不适用于带负权值的边组成的回路的情况。
有向无环图(DAG)
有向无环图(DAG)：若一个有向图中不存在环，则称为有向无环图
解题步骤：把各个操作数不重复的排成一排。标出各个运算符的生效顺序（先后顺序有出入无所谓）。
按顺序加入运算符，注意分层。
从底向上逐层检查同层的运算符是否可以合体（合体要求：左右指向的都分别相同）
拓扑排序
AOV网——顶点代表活动，有向边<Vi,Vj>表示活动Vi必须先于Vj进行。
AOV网一定是DAG图，不能有环。
拓扑排序——从AOV网中选择一个没有前驱(入度为0)的顶点输出。从网中删除该顶点和所有以他为起点的有向边。
重复上述操作。
逆拓扑排序——从AOV网中选择一个没有后继(出度为0)的顶点输出。从网中删除该顶点和所有以他为终点的有向边
重复上述操作。
性质——拓扑排序、逆拓扑排序序列可能不唯一。
【若一个结点有多个后继则不唯一。若各个结点排在一个线性有序的序列中则唯一】
若图中有环，则不存在拓扑排序序列/逆拓扑排序序列。
时间复杂度——邻接矩阵O(V^2^) 邻接表O(V+E)
①**可以使用DFS来实现拓扑排序和逆拓扑排序**。
②若邻接矩阵为三角矩阵则存在拓扑排序，反之不成立。
若一个有向图具有拓扑序列，则其临界矩阵为三角矩阵。
③在拓扑排序中为暂存入度为零的点，可以使用栈，也可以使用队列。
④拓扑序列唯一也不可以确定为同一个图。
⑤为了检验图中是否有回路，可以采用拓扑排序和DFS以及关键路径。
关键路径
AOE网——在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销。
在AOE网中仅有一个入度为0的顶点，称为开始顶点(源点)，它表示整个工程的开始。
也仅有一个出度为0的顶点，称为结束顶点(汇点)，它表示整个工程的结束。
从源点到汇点的有向路径可能由多条。
所有路径中，具有最大路径长度的路径称为关键路径，把关键路径上的活动称为关键活动。
求解方法
ve是通过边的权值对结点来进行计算的，要求结点的值为最大值，顺序求得v0->vn.
vl是从vn开始反向计算结点的，要求结点值最小。
e=活动弧的开始结点的ve
l=就是此边指向的结点的vl-此边权值
时间余量=vl(i)-ve(i)-此边权值(边的终点的vl-边的起点的ve-边权值) 或者 l(i)-e(i)
特性
若关键活动耗时增加，则整个工程的工期将增长。
缩短关键活动的时间，可以缩短整个工程的工期。
当缩短到一定程度时，关键活动可能会变成非关键活动。
可能有多条关键路径，只提高一条关键路径上的关键活动并不能缩短整个工程的工期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的。
第七章——查找
1.静态查找表：只需要查找操作；顺序查找、折半查找、分块查找、散列查找
动态查找表：除了查找，还需要增/删数据元素；二叉排序树、二叉平衡树和B树
2.平均查找长度ASL——
，通常考虑查找成功、查找失败两种情况下的ASL。
顺序查找
1.算法思想：从头到尾依次查找。适用于顺序表、链表，表中元素有序无序都可。
可在0号位置存”哨兵”，从尾部到头部挨个查找。【优点：循环时无需判断下标是否超界】
2.ASL：
成功——需比较n-i+1次。ASL=(n+1)/2
失败——ASL=n+1
3.优化：
①若表中元素有序，当前关键字大于或小于目标关键字时，查找失败。
优点：ASL失败更少，ASL成功不变。
查找判定树：成功结点的关键字对比次数=结点所在层数。
失败结点的关键字对比次数=其父节点所在层数。
②若各个关键字被查概率不同，可按被查概率降序排列。
优点：ASL成功更少。
矩阵框为失败结点
4.时间复杂度——O(n)。
折半查找/二分查找
1.适用范围：只适用于有序的顺序表。
2.算法思想：①在[low,high]之间找关键字，每次检查mid=(low+high)/2。
②根据mid所指元素与目标关键字的大小调整low或high，不断缩小low和high范围.(low=mid+1/high=mid-1)
③若low>high则查找失败。
④当前mid大high左移，mid小low右移
3.ASL：log2(n+1) -1
4.判定树：
构造——由mid所指元素将原有元素分割到左右子树中。 key：右子树结点-左子树结点=0或1（平衡二叉树）。
因此，在画图时要注意先画右子树但同时也要注意左右子树结点的平衡。
特性——①折半查找的判定树是平衡的二叉排序树(左<中<右)。
②折半查找判定树，只有最下面一层是不满的。
③若查找表有n个元素，则失败结点为n+1【n+1为空链表数】。
④树高h=⌈log2(n+1)⌉ 不包括失败结点。若包括失败结点则h+1。
⑤比较次数≤树高。
⑥右子树比左子树多。
ASL——查找成功ASL=（圆形节点所在层数的个数 * 所在层数）/圆形节点个数
查找失败ASL=（矩形节点所在层数的个数 * 父节点所在层数）/矩形节点个数
5.时间复杂度——O(log2n)
概率相同的最佳二叉排序树：折半查找
①有n个元素的有序表。最多比较次数：树高 最少比较次数：树高-1。
②折半查找的ASL不一定小于顺序查找。
分块查找/索引顺序查找
1.算法思想：①索引表中记录每个分块的最大关键字、分块的区间。
【块内顺序可以无序，但块间必须有序。即第一个块中的最大关键字小于第二个块中的所有记录的关键字】
②先查索引表(顺序/折半)、再对分块内进行顺序查找。
2.ASL：
ASL=查索引表的平均查找长度+查分块的平均查找长度。
设n个元素，均匀分为b块，每块s个元素。——顺序查找索引表
——折半查找索引表
3.易错点：
对索引表进行折半查找时，若索引表中不包含目标关键字，则折半查找最终停在low>high，要在low所指的分块中进行查找。
二叉排序树BST
1.定义：左子树结点<根结点<右子树结点。默认不允许任意两个结点的关键字相同。
2.操作：
查找操作——从根结点开始，目标值更小往左找，目标值更大往右找。
插入操作——找到应该插入的位置(一定是叶子结点)，注意修改其父结点的指针。
删除操作——①若被删结点为叶子结点，直接删除。
②若被删结点只有左/右子树，用其子树替代其位置。
③若被删结点有左、右子树。用其后继节点代替，在删除后继节点。【后继：右子树中最左下的结点】
或用前驱结点代替，再删除前驱结点。【前驱：左子树中最右下的结点】
3.查找效率分析：
取决于树的高度——最好O(log2n)【平衡二叉树】。
最坏O(n)【只有左/右子树】。
ASL——与折半查找方式相同
①按中序遍历二叉排序树得到一个有序序列。
平衡二叉树AVL
1.定义：树上任一结点的左子树和右子树差不超过1。
结点的平衡因子=左子树高-右子树高。
2.插入：当在二叉排序树中插入一个结点，可能会引起不平衡。找到最小不平衡子树。调整最小不平衡子树A。
LL——在A的左孩子的左子树中插入导致不平衡。
调整：A的左孩子结点右上旋(右单旋转)。
RR——在A的右孩子的右子树中插入导致不平衡。
调整：A的右孩子结点左上旋(左单旋转)。
LR——在A的左孩子的右子树中插入导致不平衡。
调整：A的左孩子的右孩子先左旋，后右旋。
RL——在A的右孩子的左子树中插入导致不平衡。
调整：A的右孩子的左孩子先右旋，后左旋。
3.删除：删除结点(方法同二叉排序树)。
①向上找到最小的不平衡子树。
②找最小不平衡子树下，高度最大的儿子和孙子。
③根据孙子的位置（对于最小不平衡子树而言）调整平衡(LL/RR/LR/RL)。
孙子在LL：儿子右单旋
孙子在RR：儿子左单旋
孙子在LR：孙子先左旋再右旋
孙子在RL：孙子先右旋再左旋
④如果不平衡向上传导，继续③
4.查找效率：
高为h的平衡二叉树最少有几个结点——nh=nh-1+nh-2+1
【所有非叶节点的平衡因子为1】【n个结点的最大深度】
平衡二叉树的最大深度为log2n
平均查找长度/查找/删/插的时间复杂度O(log2n)
①平衡二叉树最后插入的元素也不一定是叶结点，因为会进行调整。
②平衡二叉树删除结点后再插入结点，什么样子都可能出现。因为会进行调整。
红黑树RBT
在平衡二叉树中，插入/删除一个结点容易破坏平衡形态。调整平衡的时间开销大。
红黑树：插入/删除很多时候不会破坏红黑特性，无需频繁调整树的形态。即便需要调整，一般在常数级时间内完成。
适用场景：
平衡二叉树——适用于以查为主，很少插入/删除
红黑树——适用于频繁插入/删除，实用性强
1.定义 【左根右、根叶黑、不红红、黑路同】
红黑树是二叉排序树——>左子树结点≤根结点≤右子树结点
与普通BST相比
①每个结点或是红色，或是黑色
②根结点是黑色的
③叶结点（外部结点、NULL结点、失败结点）均是黑色的
④不存在两个相邻的红结点（即红结点的父节点和孩子结点均为黑结点）
⑤对每个结点，从该结点到任意叶结点的简单路径上，所含黑结点的数目相同
结点的黑高bh：从某结点出发（不含该结点）到达任一空叶结点的路径上黑结点总数
根节点黑高为h的红黑树，内部结点数(关键字)至少为2^h^-1【所有结点都为黑的满二叉树】
2.性质
①从根结点到叶结点的最长路径不大于最短路径的2倍。
②有n个内部结点的红黑树高度h≤2log2(n+1)
红黑树的查/插/删——O(log2n)
3.插入
①先查找，确定插入位置（原理同二叉排序树），插入新结点
②新结点是根，染为黑色
新结点是非根，染为红色
③若插入新结点后依然满足红黑树定义，则插入结束
若插入新结点后不满足红黑树定义，需要调整，使其重新满足红黑树定义
④如何调整：看叔叔的颜色【染色——颜色取反】【LL和LR是相对于爷来说的】
黑叔——旋转+染色
LL：右单旋，父换爷+父爷染色
RR：左单旋，父换爷+父爷染色
LR：左、右旋，儿换爷+儿爷染色
RL：右、左旋，儿换爷+儿爷染色
红叔——染色+变新
叔父爷染色，爷变为新结点。根据爷结点是根/非根【②】
4.删除
①红黑树删除结点的操作与二叉排序树的删除一样
②破坏红黑树特性后，需要调整结点颜色和位置
①若红黑树的所有结点都是黑色的，则它一定是一颗满二叉树。
②红结点个数最多为黑结点的两倍。
B树和B+树
1.核心特性
B树是所有结点的平衡因子均为0的m路平衡查找树。对任一结点，其所有子树的高度都相等。
【最小高度和最大高度——看分叉数】
B树中所有结点的孩子数的最大值称为阶(m)；m路平衡树。
叶结点就是失败结点(外部结点)，不带信息。总叶结点数=总关键字数+1。
一个结点的孩子数=关键字数+1。
所有叶结点都在同一层次上。
2.插入
①通过”查找”确定插入位置(一定是在终端结点)。
②若插入后结点关键字个数未超过上限，则无需做其他处理。
③若插入后关键字超过上限，则需要将当前结点的中间元素放到父节点中，当前结点分裂为两个部分。
该操作会导致父节点关键字个数+1，若父节点关键字个数也超过上限，则需要再向上分配。
根节点的分裂会导致B树高度+1（奇数为中间元素，偶数为除2——4/2选第二个提出去）
④插入的位置一定是最底层的叶子结点
3.删除
非终端结点关键字——用其直接前驱或直接后继代其位置，转化为对“终端节点”的删除
【直接前驱：当前关键字左边指针所指子树中“最右下”的元素】
【直接后继：当前关键字右边指针所指子树中“最左下”的元素】
终端结点关键字——①若删除后结点关键字个数未低于下限，无需任何处理。
②若低于下限。
右兄弟够借，则用当前结点的后继、后继的后继依次顶替空缺。
左兄弟够借，则用当前结点的前驱，前驱的前驱依次顶替空缺。
左右兄弟都不够借，则需要与父节点内的关键字、左右兄弟进行合并。合并后导致父节点关键 字-1，则需要继续合并。
4.B+树
①B+树中，n个关键字的结点对应n棵子树。
B树中，n个关键字的结点对应n+1棵子树。
②B+树中，根节点的关键字数n∈[1, m]。
其他结点的关键字数n∈[⌈m/2⌉,m]。
B树中，根节点的子树数∈[2, m]，关键字数∈[1, m-1]。
其他结点的子树数∈[[m/2], m];关键字数∈[[m/2]-1, m-1]。
③B+树中，叶结点包含了所有的关键字，非叶结点中出现的关键字也会出现在叶结点中。
B树中，各结点中的关键字是不重复的。
④B+树中，叶结点包含信息，所有非叶结点仅起索引作用。
非叶结点的每个索引项只含有对应子树中的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址
B树的结点中都包含了关键字对应的记录的存储地址。
⑤可以使一个磁盘块
①B＋树的叶结点之间通过指针链接，B树没有。
②B+树更适合关系数据库中的索引。
③B+树支持顺序查找和随机查找，B仅支持随机查找。
④B+树的所有叶结点包含了全部的关键字信息，且叶结点本身依关键字从小到大链接，因此可以进行顺序查找。但是B树不支持顺序查找，只能多路查找。
⑤m阶B树之间不通过指针链接，B+树通过指针链接。
⑥非空B树，删除操作一定会导致叶结点的变化。
哈希表/散列表
1.基本概念
散列表建立了关键字和存储地址之间的一种直接映射关系。
查找长度——关键字对比次数。
散列函数——一个把查找表中的关键字映射到该关键字对应的地址的函数。
冲突——散列函数可能会把两个或两个以上的不同关键字映射到同一地址。
同义词——发生碰撞的不同关键字。
散列表——根据关键字而直接进行访问的数据结构。
散列表建立了关键字和存储地址之间的一种直接映射关系。
时间复杂度——O(1)。
2.散列函数
①除留余数法
H(key)=key%p
p为不大于表长但最接近表长的质数，可等于表长。
取质数是为了使各关键字的散列地址分布更均匀，冲突更少。
②直接定值法
H(key)=key 或 H(key)=a*key+b
适用于关键字的分布基本连续的情况。
若关键字不连续则空位较多，会造成存储空间的浪费。
③数字分析法
选取数码分布较为均匀的若干位作为散列地址。
适用于已知的关键字集合，若更改了关键字，则需要重新构造新的散列函数。
④平方取中法
取关键字的平方值的中间几位作为散列地址。
得到的散列地址与关键字的每位都有关系，因此使得散列地址分布比较均匀。
适用于关键字的每位取值都不均匀或均小于散列地址所需的位数。
3.解决冲突的方法
①拉链法(链地址法)
冲突会降低查找效率
装填因子α=表中记录数/散列表长度【装填因子越大，发生冲突的可能性越大】
存储效率=元素个数/(散列表长度+链表结点数)
优化：将链中的元素有序化
ps:对空指针的判断一般查找长度为0
②开放定址法
可存放新表项的空闲地址既向他的同义词开放，又向他的非同义词开放。
m为散列表的表长，di为增量序列，i为第i次发生冲突
di的冲突次数是对自己这个数而言，而不是对整体而言
删除操作——对已删除的元素做标记【避免再查询的时候无法找到删除元素后面的元素】
会产生堆积(聚集)。堆积的原因——同义词和非同义词之间发生冲突。
解决冲突的方法
线性探测法——发生冲突的时候，每次往后探测相邻的下一个单元是否为空
平方探测法——
散列表的长度必须是4j+3的质数，只有这样才能探测到所有位置
伪随机序列法——
di为一个伪随机序列
③再散列法(再哈希法)
除了原始的散列函数外，多准备几个散列函数，当散列函数冲突时，用下一个散列函数计算一个新的地址。
此方法不易产生聚集。
①**散列查找有顺序和链式两种方法。
②散列查找仍需要关键字的比较。
③采用链地址法解决冲突时，若限定在链首插入，则插入任意一个元素的时间相同。
④在散列表中，受堆积现象直接影响的是ASL，装填因子不受其影响。
⑤在散列表ASL与装填因子，散列函数，解决冲突的方法有关，与表长无关。
⑥冲突是不可避免的，与装填因子无关**。
⑦ 再散列法处理冲突时不易产生聚集。
⑧发生聚集的主要原因：解决冲突的方法选择不当。
ASL的计算
拉链法：
ASL成功=h * (h所在层的数)依次累加/k【k为已存关键字个数】。
ASL失败=累加链长 * 1/m【m为（key%m）中的m】
线性探测法：
ASL成功=找到到每个关键字需要的次数之和/k【k为已存关键字个数】
ASL失败=失败情况的查找次数求和/m【m为（key%m）中的m】
在链地址法中，空指针不记作查找失败中的一次。但是在线性探测法中，空的需要记作查找失败中的一次。
线性探测法中删除元素，也需要继续探测后面的，不能就此终止。
汇总
| 算法 | 适用范围 | ASL | 时间复杂度 |
|---|---|---|---|
| 顺序查找 | 顺序表，链表 | ASL |
O(n) |
| 折半查找 | 有序顺序表 | ASL=（圆形节点所在层数的个数 * 所在层数）/圆形节点个数 ASL=（矩形节点所在层数的个数 * 父节点所在层数）/矩形节点个数 |
O(log |
| 分块查找 | 块内无序、块间有序 | ASL=索引表的平均查找长度+查分块的平均查找长度 设n个元素，均匀分为b块，每块s个元素。 顺序查找索引表： 折半查找索引表： |
 |
| 二叉排序树 | 与折半查找方式相同 | O(log O(n)【只有左右子树】 |
|
| 平衡二叉 | O(log |
||
| 红黑树 | O(log |
完全二叉树的高度h=⌈log2(n+1)⌉或h=⌊log2(n)⌋+1
折半查找的树高——h=⌈log2(n+1)⌉
平衡二叉树的最大深度为log2n
有n个内部结点的红黑树高度h≤2log2(n+1)
第八章——排序
基本概念
1.评价标准
算法的稳定性：在待排序中x=y，x的位置在y的前面。使用某一排序算法后，x仍在y的前面称这个排序算法是稳定。
稳定性不能衡量一个算法的优劣，只是对算法的性质进行描述。
时间复杂度（由比较和移动的次数决定），空间复杂度
2.对任意n个关键字的排序的比较次数至少为 ⌈log2(n!)⌉
3.分类
内部排序：在排序期间元素全部存放在内存中的排序。
大多数的内部排序只适用于顺序存储的线性表。
外部排序：在排序期间元素无法全部同时存放在内存中，必须在排序的过程中，不断地在内、外存之间移动的排序。
①对同一线性表使用不同的排序方法进行排序，得到的排序结果可能不同【稳定性】
内部排序
插入排序
**1.算法思想：**每一次将一个待排序的元素按其关键字大小插入到前面已排好序的子序列中，直到全部记录插入完成。
**2.直接插入排序：**顺序查找找到插入的位置，适用于顺序表、链表。
3.折半插入排序：
折半查找找到插入的位置，仅适用于顺序表。
一直到low>high时才停止折半查找。当mid所指元素等于当前元素时，应继续令low=mid+1，以保证稳定性。
最终应将当前元素插入到low所指的地方(high+1)。
4.性能：
空间复杂度——O(1)
时间复杂度——最好O(n)【原本有序】 最坏O(n^2^)【原本逆序】 平均O(n^2^)
稳定性——稳定
5.折半插入排序与直接插入排序的比较
不同——元素之间的比较次数不同。
【折半插入的比较次数与序列初态无关，O(nlog2n)。直接插入的比较次数与序列初态有关，O(n^2^)】
相同——排序的总趟数。元素的移动次数。
希尔排序
**1.算法思想：**先追求表中元素部分有序，再追求表中全部有序。
先将待排序表分割成若干形如L[i,i+d,i+2d,……,i+kd]的特殊子表，对各个子表分别进行直接插入排序。
缩小增量d,重复上述过程，直到d=1为止。
2.性能：
空间复杂度——O(1)
时间复杂度——最坏O(n^2^)【d=1】
稳定性——不稳定
适用性——仅顺序表
①希尔排序的一趟是取不同的增量d，第一趟是d1，第二趟是d2。
交换排序
**1.定义：**根据序列中两个元素关键字的比较结果来对换这两个记录在序列中的位置。
2.冒泡排序
算法思想：从后往前(从前往后)两两比较相邻元素的值，若为逆序，则交换他们。
直到序列比较完成。称这样的过程为”一趟“冒泡排序。最多只需n-1趟排序。
每一趟排序都可以使一个元素的移动到最终位置，已经确定最终位置的元素在之后的处理中无需再对比。
若某一趟冒泡排序过程中没有发生交换，则算法可以提前结束。
性能：空间复杂度——O(1)
时间复杂度——最好情况 O(n)【有序】 最坏情况 O(n^2^)【逆序】
适用性——适用于顺序表和链表
稳定性——稳定
3.快速排序
算法思想：算法表现主要取决于递归深度，若每次划分越均匀，则递归深度越低。划分越不均匀，递归深度越深。
每趟排序将会把枢轴元素放到其最终位置。low=high的位置
性能：空间复杂度——最好O(log2n)【枢轴划分均匀】 最坏O(n)【有序】
来源递归工作栈
时间复杂度——最好O(nlog2n)【枢轴划分均匀】 最坏O(n^2^)【有序】
稳定性——不稳定
易错点：对所有尚未确定最终位置的所有元素进行一遍处理称为“一趟”排序。因此一次划分 ≠ 一趟排序。
一次划分可以确定一个元素的最终位置，而一趟排序可以确定多个元素的最终位置。
排序过程P323 T10（从后往前，依次比较，比基准元素小的删除，放到基准位置。再从前往后，依次比较，比基准元素大的，删除，元素放到刚刚删除小的位置。）
移动次数：几个x就移动了几次。
①就平均性能而言，最好的内部排序算法是快速排序。
②若第一趟在边界，两趟可以确定两个元素的位置。若第一趟不在边界，第二趟会确定3个元素的位置。
选择排序
1.定义：每一趟在待排序列中选择关键字最小(最大)的元素加入有序子序列
2.简单选择排序
算法思想：每一趟在待排序列中选择关键字最小(最大)的元素与前面的元素进行交换。
必须总共进行n-1趟处理。
性能：空间复杂度——O(1)
时间复杂度——O(n^2^)
稳定性——不稳定
适用性——顺序表，链表都可
移动次数——O(n)
比较次数——O(n^2^)
3.堆
大根堆：①L(i)≥L(2i)且L(i)≥L(2i+1) ②在完全二叉树中，根≥左、右 ③堆顶元素最大
小根堆：①L(i)≤L(2i)且L(i)≤L(2i+1) ②在完全二叉树中，根≤左、右 ③堆顶元素最小
可将堆视为一颗完全二叉树
4.堆排序(基于大根堆)
算法思想：
建堆
①把所有非终端节点都检查一遍，是否满足大根堆的要求，如果不满足，则调整。
非终端节点小于等于⌊n/2⌋。从后往前检查。
②检查当前结点是否满足根≥左、右。若不满足，将当前结点与更大的一个孩子互换。
③若元素破坏了下一级的堆，则采用相同的方法继续调整。
排序
①每一趟将堆顶元素加入到有序子序列中(即与待排序中的最后一个元素交换)。此时该元素会被移除堆。然后②
②将剩余待排序序列再次调整为大根堆。然后重复①操作
性能：
空间复杂度——O(1)
时间复杂度——建堆O(n)、排序O(nlog2n);总时间复杂度O(nlog2n)
稳定性——不稳定
插入：
将新元素放在表尾。若新元素比父节点大，二者互换。新元素上升，直到无法继续上升为止。**O(log2n) **
删除：
被删除的元素使用堆底元素替代，然后让该元素不断下坠，直到无法下坠为止。O(log2n)
关键字比较：
每次上升只需比较一次。
每次下坠可能比较一次，也可能比较2次
①基于大根堆进行排序得到递增序列，基于小根堆进行排序得到递减序列。
②一个结点每下坠一层，最多比较关键字2次。
③若树高h,某结点在第i层，则需要最多下坠h-1层，关键字对比次数不超过2(h-i)。
④将整棵树调整为大根堆，关键字对比次数不超过4n。
⑤**堆不用于查找，只用于排序**。
归并排序
1.归并
把两个或多个有序的子序列合并为一个
2路归并——二合一 多路归并——多合一
K路归并：每选出一个小元素需对比关键字K-1次
2.归并排序算法
①若low>high，则将序列分为从中间mid=(low+high)/2分开
②对左半部分[low,mid]递归地进行归并排序
③对右半部分[mid+1,high]递归地进行归并排序
④将左右两个有序子序列归并为一个
3.性能
空间复杂度——O(n)
时间复杂度——O(nlog2n)
稳定性——稳定
归并趟数——⌈log2n⌉
①对于归并排序，对于N个元素进行k路归并排序时，排序的趟数m满足 k^m^ = N。
②对于归并排序，当一个表的最小元素大于另一个表的最大元素的时候，比较次数最少为N。
当两个表的元素依次间隔大小的时候，比较次数最大为2N-1(N为一个表中的元素个数，并非两个表的总和)。
**基数排序 **
1.算法思想
①将整个关键字拆分为d组(d位)
②按照各个关键字位权重递增的次序，做d趟”分配”和”收集”，若当前处理的关键字位可能取得r个值
则需要建立r个队列
③分配：顺序扫描各个元素，根据当前处理的关键字位，将元素插入相应队列。一趟分配耗时O(n)
④收集：把各个队列中的结点依次出队并链接。一趟耗时O(r)
2.性能
空间复杂度——O(r)
时间复杂度——O(d(n+r))
稳定性——稳定
3.应用
数据元素的关键字可以方便地拆分为d组，且d较小
每组关键字的取值范围不大，即r较小
数据元素个数n较大
①基数排序中没有关键字的比较。
内部排序汇总
①在待排序的元素序列基本有序的前提下，效率最高的排序方法是直接插入排序。
②简单选择排序，堆排序，冒泡排序，快速排序每趟排序最少会有一个元素到达其最终位置。
③排序趟数与初始状态有关——快排、冒泡。
④比较次数与初始序列无关——简单选择排序、折半插入排序、基数排序。
⑤移动次数与初始序列无关——归并排序、基数排序。
⑥算法复杂度与初始序列无关——简单选择排序、堆排序、归并排序、基数排序。
⑦**由顺序表转变为链表时，插入排序、选择排序、冒泡排序的时间复杂度不变。希尔排序和堆排序的时间复杂度增加**。
⑧若某一趟冒泡排序过程中没有发生交换，则算法可以提前结束。
外部排序
外部排序
1.外存、内存之间的数据交换
外存通常指磁盘。操作系统以“块”为单位对磁盘存储空间进行管理。
磁盘的读写以块为单位，数据读入内存后才能被修改，修改完了还要写回磁盘
2.外部排序原理
原因：由于数据元素过多，无法一次全部读入内存进行排序
若要进行k路归并排序，则需要在内存中分配k个输入缓冲区和一个输出缓冲区【数据块的大小与缓冲区大小相同】
过程：
①根据内存缓冲区大小，将外存的文件分成若干长度为l的子文件，依次读入内存并利用内部排序算法堆它们进行排序
②将排序的得到有序子文件重新写回外存【这些有序子文件称为归并段/顺串】
③重复上述操作，使外存中全是归并段
④将归并段1与归并段2中的各自第一块读入内存，进行归并排序。
若缓冲区2空了，则将归并段2中的第二块读入内存，继续归并排序。
⑤重复④操作使12合并，34合并……
⑥继续第二趟归并，类④
构造初始归并段：需要K次读操作，K次写操作。【K为外存块数】还要进行内部排序
第X趟归并：需要K次读操作，K次写操作。【K为外存块数】还要进行内部归并
初始归并段数量=⌈N/L⌉【L为缓冲区大小】
3.影响外部排序因素
外部排序时间开销=读写外存时间+内部排序所需时间+内部归并所需时间
4.优化思路
多路归并：增加归并路数k， 进行多路平衡归并，减少归并趟数，从而减少磁盘I/O读写次数
代价一：需要增加相应的输入缓存区
代价二：每次从k个归并段中选一个最小元素需要(k-1)次关键字对比
减少初始归并段数量：输入缓冲区数量增加，使得归并段的内容尽可能的多
5.K路平衡归并
①最多只能有K个段归并为一个
②每一趟归并中，若有m个归并段参与归并，则经过这一趟处理得到⌈m/k⌉个新的归并段
败者树
1.问题：
使用多路平衡归并可减少归并趟数，但是从k个归并段选取一个最小/最大元素需要对比关键字k-1次。内部归并时间增加
构造败者树可以使关键字对比次数减少到 ⌈log2k⌉
2.概念：
败者树可以视为一颗完全二叉树(多了一个头)。
k个叶结点分别对应k个归并段中当前参加比较的元素，非叶子结点用来记忆左右子树的“失败者”，让胜者往上继续进行比较，一直到根结点。
败者树记录的是归并段号而非元素
关键字对比次数减少到 ⌈log2k⌉
总的比较次数 (n-1)⌈log2r⌉
比较次数与k无关。k值过大虽然使趟数减少，但读写外存的次数会增加
n是每趟归并的元素数
置换-选择排序
置换-选择排序：进一步减少初始归并段数量。
步骤：
①从待排序文件A中读取记录，放到内存工作区B中，用min记录数，若A中最小数更换，min值也更换。
（注意min的值只能增大不能减小，因为归并段为有序序列）
②若从A进入到B的数小于min，则将其锁死。然后继续①
③直到B的所有数都比min小，即全部锁死。解冻B中数据，并min清零。然后重复上述步骤
最佳归并树
使用置换-选择排序的时候得到的初始归并段中的元素个数不同。
1.理论基础
①每个初始归并段对应一个叶子结点，把归并段的块数作为叶子的权值
②归并树的WPL=树中所有叶结点的带权路径长度之和
③归并过程中的磁盘I/O次数=归并树的WPL*2
PS：k叉归并的最佳归并树一定是严格k叉树，即树中只有度为k、度为0的点
2.构造最佳归并树
二路归并的最佳归并树——哈夫曼树
多路归并的最佳归并树
若(初始归并段数量-1)%(k-1)=0，说明刚好可以构成严格k叉树，此时不需要添加虚段
若(初始归并段数量-1)%(k-1)=u≠0，则需要补充(k-1)-u个虚段【虚段：长度为0】
①在外部排序中内外存交换数据时间占比最大。
②败者树是一颗完全二叉树。
③败者树的每次维护，必定要从叶结点一直走到根节点，不可能在中间停止。
④在由k路归并构建的败者树中选取一个关键字最小的记录。所需时间为O(logk)。
⑤多路平衡归并的作用：减少归并趟数。
⑥在做m路平衡归并排序过程中，为实现输入/内部归并/输出的并行处理，需要设置2m个输入缓存区，2个输出缓存区 以便在执行内部归并时，能同时进行输入/输出操作。
汇总
卡特兰数
F(n)=
1.适用场景
栈——n个元素入栈，求出栈序列个数
二叉树——n个结点能构成多少种不同形状的二叉树
括号匹配——n对括号，有多少种括号匹配序列
PS：栈和二叉树不能有其他限制
时间复杂度
| 算法 | 时间复杂度 | 备注 | 11111111111111111111 |
|---|---|---|---|
| 朴素模式匹配 | O(nm) | ||
| KMP | O(n+m) | ||
| 并查集 | O(n)—>O(log |
||
| BFS | 邻接矩阵O(V^2^) 邻接表O(V+E) | 空间O(V) | |
| DFS | 邻接矩阵O(V^2^) 邻接表O(V+E) | 空间O(V) | |
| Prim | O(|V|^2^) | ||
| Kruskal | O( |E| log2 |E| ) | ||
| Dijkstra | O(|V|^2^) | 不可求负值 | |
| Floyd | O(|V|^3^) | 不可求负值回路 | |
| 拓扑排序 | 邻接矩阵O(V^2^) 邻接表O(V+E) | ||
| 顺序查找 | O(n) | ||
| 折半查找 | O(log |
||
| 二叉排序树 | 最好O(log |
||
| 平衡二叉树 | O(log |
||
| 红黑树 | O(log |
外部排序——读写外存的时间+内部排序的时间(对初始归并段)+内部归并的时间
平均查找长度ASL
ASL=找到第i个元素所需进行比较的时间*查找到第i个数据元素的概率（基本就是比较次数的总数/元素个数）
顺序查找——成功(n+1)/2；失败n+1
折半查找——log2(n+1) - 1
分块查找—— ASL=查索引表的平均查找长度+查分块的平均查找长度
设n个元素，均匀分为b块，每块s个元素。顺序查找索引表ASL = (b+1)/2 + (s+1)/2，当s=根号n的时候ASL最小为根号n+1
折半查找索引表ASL = ⌈ log2(b+1) ⌉ + (s+1)/2
平衡二叉树——O(log2n)
wechat