Wondershare EdrawMind
MindMap Gallery 数据结构综合
- 76
数据结构综合
这个是一个清晰的数据结构综合的思维导图，主要说明了数列结构、栈、队列等内容，每个内容下又分了好几个层级进行说明。思维导图是一种视觉化的思维工具，通过中心思想或问题的放射性结构展现出来。它由主题、分支和关键词组成，旨在模仿人脑的神经网络结构。这种图形化的方式有助于促进记忆、组织信息以及激发创意。
Edited at 2023-12-23 20:53:51
- Recommended to you
- Outline
数据结构综合
1. 绪论
数据结构三要素
逻辑结构
线性结构
线性表
栈
队列
串
注意点
数组是线性表在内存顺序存储的表现，不是逻辑结构
逻辑上的线性与非线性区别在于数据元素之间的关系，线性关注仅在前驱和后继（强调一对一的前后关系），而非线性的关注点不仅在前驱后继，强调的是一对多、多对多的关系
非线性结构：树、图
注意点
逻辑结构分为线性和非线性
线性再分为线性表，栈，队列，串
存储结构
顺序存储
优点
可实现随机存储
缺点
需要一块连续的空间
外部碎片大
注意点
不仅可以用来表示线性表，还可以表示树，图等
顺序表是顺序表，指的是在内存连续分配的一种数据结构
线性表是线性表，指的是在逻辑上是一维的只有前驱和后继关系的数据结构
链式存储
优点
无碎片现象，充分利用存储单元
缺点
每个元素浪费空间存储指针
只能顺序存储
注意点
链式存储的结点之间不一定连续
链式存储的结点内部不止一个存储地址，它们一定连续
索引存储
优点
检索速度快
缺点
索引表占用空间
增删数据需要修改索引表
散列存储
优点
检索，增删都很快
缺点
散列函数不好会引起冲突
冲突处理不好会增加时空开销
注意点
区别在于要通过不同的方法找到数据的存储地址的信息，顺序存储中某一数据元素的地址是逻辑关系上的上一个元素的地址加一个常数（数组的话就是下标直接加1就可以找到下一个元素的地址），链式存储中某一元素的地址存储在其前驱的地址指针里，索引存储的某一元素的地址存储在索引表中，散列存储的某一元素的地址与元素内的关键字直接相关，可以通过关键字直接找到地址。
数据的运算
组成
运算的定义
针对逻辑结构
运算的实现
针对存储结构
补充
算法的设计取决于所选的逻辑结构，算法的实现取决于存储结构
存储结构依赖于计算机语言
逻辑结构和存储结构的区别
逻辑结构只描述数据之间的关系，而不会暗含是如何存储的
比如
线性表
只描述了元素之间应该是前后连接的线性关系
是逻辑结构
顺序表
要求元素之间连续存储
是存储结构
算法效率的度量
时间复杂度
最坏时间复杂度
最好时间复杂度
平均时间复杂度
所有可能的输入在等概率出现的情况下，算法的期望运行时间
时间复杂度
讨论一个算法的时间复杂度，就是指最坏情况下估算算法执行时间的上界
影响因素
循环语句
递归层数
补充
要注意题目问的语句的执行次数还是算法的时间复杂度
估计复杂度时要慢慢地来，从多个角度分析
从代码分析
从运行结果分析
例如每执行一次就解决一个元素
可以说好的时间复杂度总是优于坏的时间复杂度，不过最好别说一定快于就行
空间复杂度
用问题规模的函数S(n)来描述
在递归调用时会关注空间复杂度多一点，这里就要先行理解一下递归调用栈
影响因素
除了题目给出的数据外，额外开辟的数组
最大递归层数
补充
空间复杂度为O(1)的意思是需要的辅助空间是常量级别，而不是不需要任何辅助空间
2. 线性表
线性表的定义
线性表的每个元素的元素类型都相同
线性表各种操作的实现与存储结构有关，不同的存储结构，会导致操作的实现形式不同
注意点
存储结构指的是在计算机中如何安排数据，这个有很多种方式，不只是顺序，链式，索引，散列这四种简单的，包括邻接表其实也是一种存储结构
顺序表示
线性表的顺序存储称为顺序表
特点
逻辑顺序和物理顺序相同
逻辑结构：线性结构
存储结构：顺序存储
静态分配
动态分配
特点
动态分配也是连续分配，只不过空间可以按需增加
静态和动态的区别首先在于存储类型的描述不同，初始动态分配语句为：L.data = (ElemType*)malloc(sizeof(ElemType)*InitSize);
注意点
顺序存储和顺序存取要区分开
顺序存储指的是内存中连续存放
顺序存取指的是链表这种
随机访问&随机存取
区别
一个只需要读
一个既要读还要写
例子
CD-ROM，可以随机访问，但是不能随机读取
不能随机访问的
磁带
基本操作的实现
插入操作
注意要先判断输入的i是否有效和存储空间是否有空余，元素后移和插入完成后，不要忘了将表长length加1
i表示的是第几个元素，与数组下标是有区别的，i等于数组下标加1
移动结点的平均次数
有n+1种插入可能，分别需要移动n次......0次
删除操作
同样要注意判断输入的i是否有效，删除和前移完成后，不要忘了将表长length减1
按值查找
按位查找
最好时间复杂度都是O(1)，最坏时间复杂度都是O(n)，平均时间复杂度都是O(n)
Remark
存取第i个元素，不是插入或者删除，注意！
链式表示
逻辑结构：线性结构
存储结构：链式存储
单链表
结点类型描述
Remark
注意这个结构体，在它里面定义下个结点时调用了自己，这时候还是需要写struct node* next，不能少了struct
头结点与头指针
头指针一定指向第一个结点
如果存在头结点，则头结点一定是第一个结点
头插法和尾插法
注意这个操作里蕴含的重要思想，不断更新维护边界结点
双链表
结点类型描述
循环链表
结点类型描述
循环单链表
循环双链表
Rmeark
尾结点的next指针指向
尾结点的next指针指向头结点，而不是NULL
循环链表的判空条件
不是头结点的指针指向NULL，而是它是否指向头结点
循环链表是否有指针为NULL的结点？
循环链表无指针为NULL的结点
头指针好还是尾指针好？
尾指针更好
循环链表可以从任意一个结点出发遍历整个链表，而单链表不行
静态链表
借助数组来描述链式存储结构
结点类型描述
特点
下标指的是什么？
这里的下标指的是数组下标，又称为游标
是否可以分散存储？
不行，因为还是通过数组下标索引进行链接
基本操作的实现
单链表
带头结点
建立单链表
头插法
注意插入的时候指针赋值的顺序（先瞻前后顾后）
尾插法
加入一个尾指针
每次插入操作的结束都要将插入结点指针赋给尾指针
按序查找
按值查找
插入结点
后插
先通过按序查找GetElem(L，i-1)查找到插入位置的前一个结点，然后再进行结点指针赋值
前插
先直接进行后插操作，然后再更改前后的数据（偷天换日）
删除结点
直接删
先通过按序查找GetElem(L，i-1)查找到插入位置的前一个结点，通过结点指针赋值进行逻辑上的删除后在进行物理结构上的删除
间接删
可转化为：交换该结点和后继结点的值，然后删除后继结点（省去了查找前驱结点的时间）
注意点
删最后一个节点
需要将其前驱结点的指针指向NULL
求表长
遍历链表
特点
无论是否为空，头指针都指向头结点
不带头结点
双链表
插入操作
注意结点指针赋值的顺序
删除操作
瞻前顾后原则，别忘了释放结被删除的结点指针空间
循环链表
循环单链表
尾指针优于头指针
若设立的尾指针为r，那么r->next就是头指针
循环双链表
如果循环单链表就可以实现，那么就没必要双链表，开销大
静态链表
指针与其他链表的指针不同，这里的指针存放的地址为下一个元素的数组下标，这样的指针又称为游标
Remark
如果题目没有特别说明，则默认使用的是头指针
带头结点的链表通常都使用头指针，但是这和它同时也使用尾指针也是不冲突的
双链表和单链表相比，虽然访问前后结点更加灵活，但是删除和插入操作更复杂
碰到链表的题目，小心分析，特别要小心是否可以方便访问前后的结点，这类题目不粗心，是不能失分的题目
3.栈和队列
栈
逻辑结构：线性结构
存储结构
顺序存储：顺序栈
存储类型的描述
链式存储：链栈
存储类型的描述
栈的基本操作
顺序栈
初始化
判栈空
进栈
先判栈满，再赋值，后top+1
出栈
先判栈空，在赋值，后top-1
读栈顶元素
链栈
应用
栈在括号匹配当中的应用
栈在表达式求值中的应用
1.掌握中缀表达式如何转化为按后缀表达式
操作数
直接写
运算符
非括号
若栈顶运算符的优先级高于或等于自己
则不断弹出
若栈顶运算符的优先级小于自己
则直接压入栈中
括号
左括号
直接压入栈中
右括号
不断将栈顶元素弹出，知道左括号
2.理解在计算后缀表达式时栈是如何工作的
操作数
直接压入栈
运算符
弹出两个操作数，注意运算顺序
栈在递归当中的应用
LIFO
队列
逻辑结构：线性结构
存储结构
顺序存储
存储类型的描述
顺序队列
循环队列
可以解决顺序队列假溢出的问题
三种方式处理队满或队空
留出一个空位
tag位标记插入还是删除
增加元素个数统计
入队出队特点
头尾指针永远都是在+1
增加元素，尾指针+1
减少元素，头指针+1
链式存储（链式队列）
存储类型的描述
双端队列
考点主要是输出序列的判断，只要看清输入输出端的限制条件，耐心分析应该问题不大
队列的基本操作
循环队列的基本操作
初始化
判队空
入队
先判队满，再赋值，最后Q.rear = (Q.rear + 1)%MaxSize;
出队
先判队空，再赋值，最后Q.front = (Q.front + 1)%MaxSize;
链式队列的基本操作
初始化
判队空
入队
赋值完毕后，需要将新结点指针指向空，在进行结点指针赋值（对尾指针指向新结点）
出队
带头结点
先判空，再分配一个结点使其指向要出队的元素，再通过指针赋值逻辑上删除结点（⚠️注意如果队列中只有一个元素，则还需要再判断p是否等于Q.rear，如果等于，则赋值Q.rear = Q.front是往后的判空操作能顺利进行），最后free(p)物理上删除结点。
不带头结点
注意头指针的位置是位于头结点的，以及特殊情况下front和rear的处理
应用
队列在层序遍历中的应用
理解层序遍历的过程
队列在计算系统中的应用
1.解决主机与外部设备之间的速度不匹配问题
2.解决由多用户引起的资源竞争问题
FIFO
特殊矩阵的压缩存储
对称矩阵
性质：上三角区中的所有元素和下三角区的所有元素相同（⚠️上三角区和下三角区都不包含主对角线上的元素）
存储：对于n阶对称矩阵，建立长度为n(n+1)/2的一维数组，找到数组下标k和矩阵元素下标（i、j）的关系
三角矩阵
性质：上三角矩阵的下三角区是相同的变量，下三角矩阵的上三角区是相同的变量
存储：对于n阶对称矩阵，建立长度为n(n+1)/2+1的一维数组，找到数组下标k和矩阵元素下标（i、j）的关系
三对角矩阵（带状矩阵）
性质：对于任一元素ai,j，当|i-j|>1时，有ai,j=0
存储：对于n阶对称矩阵，建立长度为3n-2的一维数组，找到数组下标k和矩阵元素下标（i、j）的关系
稀疏矩阵
性质：矩阵中非零元素个数为t，相对于矩阵的个数s来说非常少，即s>>t的矩阵称为稀疏矩阵
存储：将非零元素及其对应的行和列构成一个三元组（行标、列标、值），三元组既可以采用数组存储，也可以采用十字链表法存储
失去了随机存取的特性
注意点
注意这些结构的下表和数组下标的区别，数组是从0开始
稀疏矩阵的存储方法
三元组
十字链表
Remark
队列与链表
链表的头指针和尾指针是固定地指链头和链尾
队列的头和尾可以选择是链头和链尾，也可以相反的选择，所以队列的头可能位于链表
还有一个要注意的点是，队列的头是输出的一端，即减少的一端，反映在链式存储上就是失去结点
顺序表示
要注意题目给的到底是多少个元素，比如A[0...N]和A[0...N-1]分别是n+1和n个元素，小心坑
归根结底
基础的概念要清楚掌握
读题时要完全读懂再进行下一步
4.串（字符串）
逻辑结构：线性结构
存储结构
顺序存储
静态分配：定长顺序存储表示
存储类型描述
动态分配：堆分配存储表示
存储类型描述
链式存储
块链存储表示
基本操作
。。。
串的模式匹配
简单的模式匹配算法
匹配失败主串的指针会回退，子串的指针会回退到1
概要
改进的模式匹配算法--KMP算法
部分匹配值PM[j]，表示字符串的前缀和后缀的最长相等前后缀长度
PM表
匹配不成功时，子串的指针j应该回退的值为已匹配的字符数(j-1)减去已匹配部分的部分匹配值PM[j-1]
所以，匹配不成功时 next[j] = j - ((j-1)-PM[j-1]) = PM[j-1] + 1
next[j] 也可以直接用 PM[j-1] 表示
KMP算法的进一步优化
nextval[j]为next[j]数组的改进，改进方法见P111，一眼就能意会
5.树与二叉树
树和森林
概念
结点间的关系
祖先
子孙
双亲
孩子
兄弟
度
结点的度
孩子节点的数量
树的度
树中结点最大的度
节点的种类
分支结点（非终端结点）
叶子结点（终端结点）
结点的特性
结点的层次
从上往下
结点的高度
从下往上
结点的深度
树的高度和深度（数值相等）
有序树和无序树
有序树不可以交换子树位置
路径和路径长度
路径只能从上往下
路径长度代表经过了多少边
森林
常考性质
节点数等于总度数+1
n个结点的树有n-1条边
度为m的树和m叉树的区别
任意节点的度
均小于等于m
度的限制
度为m的树至少有一个度为m的结点
m叉树不一定有度为m的结点
可否为空
度为m的树至少有m+1个结点
m叉树可以是空树
总结，多叉树只对每个节点最多孩子数有限制，而不对最少做限制 度为m的树则一定存在一个有m个孩子的，注意区分
完全K叉树
要么没有孩子，只要有孩子就是有K个
第i层最多有多少个结点
高度为h的多叉树最多有多少结点
高度为h的多叉树最少有多少结点

高度为h的完全k叉树最少有多少结点
具有n个结点的m叉树的最小高度
逻辑结构
非线性结构，是一种递归的数据结构（定义上就是递归的）
存储结构
顺序存储结构
双亲表示法
存储结构描述
代码思想
定义存储结构时，先定义单个节点的结构体，再定义一个树的结构体
顺序+链式存储
孩子表示法
存储结构描述
代码思想
整个树一个大的结构体，主体是一个数组，数组每个元素代表了一个结点
数组的元素一个结构体，也就是具体的每个结点，包含了这个节点的值，以及这个结点的第一个儿子
树的边需要一个结构体，包含了儿子的序号，以及连接下一个儿子的边
每个结点的孩子都用单链表链接起来形成一个线性结构，此时n个结点就有n个孩子链表
链式存储结构
孩子兄弟表示法（二叉树表示法）
存储结构描述
所有的结点都要使用左孩子右兄弟的规则
操作
树、森林和二叉树的转换
遵循“左孩子右兄弟”的规则，每个结点的左指针指向它的第一个孩子，有指针指向它的相邻的兄弟。由于根结点没有兄弟，所以对应的二叉树没有右子树，所以将森林转换为二叉树时，将各树之间视为兄弟
树和森林的遍历
树的遍历
先根遍历
与其对应的二叉树的先序遍历序列相同
后根遍历
与其对应的二叉树的中序遍历序列相同
森林的遍历
先序遍历森林
与其对应的二叉树的先序遍历序列相同
中序遍历森林（部分教材也称后根遍历）
与其对应的二叉树的中序遍历序列相同
特点
转换过程的特点
左孩子右兄弟的转化只发生在相邻的兄弟结点之间
不会跨父亲相连
一个结点相比于之前，最多多了一个右孩子
每个非终端节点，都会导致一个右指针为空的结点出现
二叉树与对应森林中树数量的关系
只有满二叉树，高度为h，对应的森林就有h个树
通过定义理解
森林中非终端节点数目 与 二叉树中右指针为空（无右孩子）的结点数目
h+1
森林中叶节点的数目 与 二叉树的关系
森林的叶节点的数目 和 二叉树中左孩子为空的节点个数相同
树的应用
*并查集
Remark
树的路径长度是什么？
树根到每个结点的路径长度之和
树转换为二叉树时的注意点
一定会执行左孩子右兄弟策略，即任何分支结点在转换之后左指数一定非空，即左子树为0一定代表没有孩子
碰到比较难的题目的时候，想一下基本原理，根据原理去推导，可能比较轻松
二叉树
概念
二叉树是有序树，左右节点不能交换，二叉树可以为空，结点的度可以为0、1、2，不存在度大于2的结点，⚠️注意与度为2的有序树区分开来
几种特殊的二叉树
满二叉树
每一层都有最多数量的结点
完全二叉树
编号1～n的结点与满二叉树中编号1～n的结点一一对应
分支结点编号i小于等于n/2的向下取整
注意分支结点的概念，要敏感
二叉排序树
左子树上的所有结点的关键字均小于根结点的关键字，右子树上的所有结点的关键字均大于根结点的关键字
平衡二叉树
树上任意一个结点的左右子树的深度之差不超过1
二叉树常考性质
叶子结点比二分支结点多一个
第i层最多有多少个元素
高度为h的多叉树最多有多少个结点
具有n个结点的完全二叉树的高度
完全二叉树结点的性质
度为0和度为1的结点数相加一定是奇数

度为1的节点数要么是0要么是1
若完全二叉树有偶数个结点，则一定存在一个度为1的结点
若完全二叉树有奇数个结点，则一定不存在度为1的结点
逻辑结构
非线性结构
存储结构
顺序存储结构
适合存储完全二叉树和满二叉树（对于一般的二叉树，为了能让每个结点与完全二叉树上的结点相对应，只能添加一些空结点来反映二叉树中结点之间的逻辑关系）
链式存储结构（二叉链表）
存储结构描述
在含有n个结点的二叉链表中，将会含有（n+1）个空链域
操作
二叉树的遍历
三种遍历方式
先序遍历NLR
中序遍历LNR
后序遍历LRN
递归和非递归函算法的转换（非递归算法需要使用栈）
先序遍历非递归算法见P133
中序遍历非递归算法见P134
层次遍历
算法见P134
由遍历二叉树构造二叉树
已知中序和后序遍历序列
后序遍历序列最后一个为根结点，然后再中序中分除左子树和右子树，再根据后序遍历序列分别在左右子树中找出根结点，以这种递归的形式构造出二叉树
已知中序和先序遍历序列
先序遍历序列的第一个为根结点，然后再中序中分除左子树和右子树，再根据先序遍历序列分别在左右子树中找出根结点，以这种递归的形式构造出二叉树
已知中序和层序遍历序列
层序遍历序列的第一个为根结点，然后再中序中分除左子树和右子树，再根据层序遍历序列分别在左右子树中找出根结点，以这种递归的形式构造出二叉树
线索二叉树
存储结构描述
ltag或rtag==0则代表lchild或rchild指针指示的是孩子结点，如果ltag或rtag==1则代表lchild或rchild指针指示的是其前驱或者后继
中序线索二叉树的构造
步骤
递归中序访问
先建立左子树的前驱
再建立前驱结点的后继
很好的递归思想
可以新增一个头结点，实现二叉树的双向遍历
中序线索二叉树的遍历
求中序遍历的第一个结点
一直递归找到最左下角的itag==0的结点
求结点的后继
如果它有右孩子，则找右孩子中序遍历的第一个结点
如果它没有右孩子，直接返回后继
先序和后序线索二叉树
根据遍历的特性来考虑前驱后继
注意点
主要是方便寻找前驱和后继
根据遍历方式的性质，如果能够直接找到那就递归找，如果找不到，那肯定直接返回线索二叉树记录的值
二叉树的应用
二叉排序树BST
性质
左子树的值小于根结点的值，右子树的值大于根结点的值
普通排序二叉树
操作
查找
插入
构造
删除
查找效率分析
最坏时间复杂度O(n)
平衡二叉树
概念
定义
保证任意结点的左右子树高度差的绝对值不超过1
平衡因子
左右子树的高度差为该结点的平衡因子
操作
插入（四种情况下为保持平衡二叉树的平衡的四种操作）
LL平衡旋转（右单旋转）
在结点的左孩子的左子树上插入了新结点，导致了不平衡
RR平衡旋转（左单旋转）
在结点的右孩子的右子树上插入了新结点，导致了不平衡
LR平衡旋转（先左旋后右旋）
在结点的左孩子的右子树上插入了新结点，导致了不平衡
RL平衡旋转（先右旋后左旋）
在结点的右孩子的左子树上插入了新结点，导致了不平衡
每次旋转操作的对象都是最小的不平衡树（示意图看一遍就明白P177，比较简单）
查找
比较关键字的次数不超过平衡二叉树的深度，含有n个结点的平衡二叉树的最大深度为O(log2n)，因此平衡二叉树的平均查找长度为O(log2n)
哈夫曼树和哈夫曼编码
概念
权
结点的带权路径长度
树的带权路径长度WPL
哈夫曼树的定义
带权路径长度（WPL）最小的二叉树称为哈夫曼树，也称最优二叉树
哈夫曼树的构造
每次选剩下的结点和已生成的根结点中最小的两个作为左右子树生成新的根结点
哈夫曼编码
概念
固定长度编码
每个字符采用相同长度的二进制位表示
可变长度编码
允许对不同字符采用不同长度的二进制位表示
前缀编码
⚠️没有一个编码是另一个编码的前缀
注意点
哈夫曼树需要额外造n-1个结点
哈夫曼树只有度为0和度为k的结点！！！
哈夫曼树不唯一，因为左子树右子树随便定
Remark
第i个结点的左孩子编号一定为2i吗？
可能没那么多结点，即不存在
后序线索树能用常规的二叉链表实现吗？
不能，要用三叉链表
一棵树的中序遍历的起点一定是叶节点吗？
当然不是，注意选择题有时候会偷偷给这个条件，是错的
线索二叉树是逻辑结构吗？
不是，是物理结构
线索二叉树有空的链域吗？
有，如果没有前驱且没有后继且没有孩子，则是空的
什么是树的带权路径长度？
所有叶节点的带权路径长度之和
二叉树的顺序存储结构一定要留出空位吗？
一定要留出空位，并且要满足这一层最多的节点数
6.图
概念
图的定义
由顶点集V和边集E组成，记为G = (V,E)，顶点集V非空，边集E可以是空
注意点
树可以是空树，但图的顶点集一定非空
术语
有向图
有向边（弧）
弧的表示<v,w>，v到w的弧或称v邻接到w
弧尾、弧头
无向图
无向边（边）
无向边的表示(v,w)
邻接点、依附、相关联
简单图、多重图
是否有重复边
是否有自己到自己的边，即<a,a>
完全图
有向完全图：满边（含有n(n-1)条边）
无向完全图：满边（含有n(n-1)/2条边）
即每个点都有到其他点的直接边
子图
注意首先必须是图，其次子图G'的顶点集和边集分别是图G的顶点集和边集的子集
生成子图
顶点集合相同
连通
无向图
连通
在无向图中，若顶点v和w之间有路径存在，则称v和w是连通的
连通图
若图中任意两个顶点都是连通的，则称图为连通图
连通分量
无向图的极大连通子图（包含所有边）称为连通分量
注意点
极大连通子图
从某个点出发，能碰到的所有边和点，就是一个极大连通子图
相关计算
n个顶点的无向图的边数问题
若连通
至少n-1条边
若不连通
最多
即n-1个点全联通，剩下一个孤零零
有向图
强连通
在有向图中，如果有一对顶点v和w，从v到w和w到v都有路径，则称这两个顶点是强连通的
强连通图
若图中任意一对顶点都是强连通的，则称此图为强连通图
强连通分量
有向图中的极大强连通子图称为有向图的强连通分量
相关计算
n个顶点有向图的边数问题
若强联通
则至少n条边，刚好形成回路
注意点
顶点数大于1的强联通分量意味着有环
可以和拓扑排序一起考察
生成树、生成森林
连通图的生成树
包含图中全部顶点的一个极小连通子图（包含所有顶点但边数最少）
若图中顶点数为n，那么它的生成树含有n-1条边
生成森林
在非连通图中，连通分量的生成树构成了非连通图的生成森林
生成树与连通分量的区别
生成树是极小连通分量，包含尽可能多的点和尽可能少的边，并且保持连通的图
连通分量是极大联通子图，包含尽可能多的边，并且保持联通的图
定点的度，入度，出度
无向图
度是指依附于该点的边数
所有顶点的度加起来是边数的两倍
有向图
入度是指以该点为终点的边的数目
出度是指以该点为起点的边的数目
顶点的度是入度和出度之和
边的权和网
每条边都可以标上具有某种含义的数值，该数值称为该边上的权值
边上带权值的图称为带权图，也称网
稠密图、稀疏图
边数很少的图称为稀疏图，反之，边数很多的称为稠密图
顶点的关系描述
路径
从一点到另外一点之间的顶点序列
路径长度
路径上边的数目称为路径长度
回路
第一个顶点和最后一个顶点相同的路径称为回路或环
简单路径
顶点不重复出现的路径称为简单路径
简单回路
除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路
距离
两顶点之间最短路径的长度
有向树
一个顶点的入度为0，其余顶点的入度为1的有向图，称为有向树
Remark
图的点集可以为空吗？边集呢？
点集不可以为空，边集可以
什么是完全图？
任何点都有到任意其他点的边
只要顶点和边都是A的子集，那就是子图吗？
不一定，可能顶点和边都无法构成一个图
什么是连通图？什么是连通分量？
如果一个图中任意两个点是连通的，则称为连通图
一个连通图的极大连通子图称为连通分量
一个图可能有多个连通分量
n个顶点构成的图，连通的最少要求边数和不连通的最多边数分别是多少？
如果连通，至少n-1
如果不连通，最多(n-1)(n-2)/2
什么是生成树和生成森林？和连通分量有什么关系？
生成树是极小连通子图，如果再去掉一个边则不连通，如果再增加一个边，则形成环路，若有n个点，则又n-1条边
连通分量是极大连通子图，要求尽量包含多的边
什么是度？什么又是入度和出度？
度是对于无向图而言的，这个点牵扯到底的所有边数之和称为这个点的度，而所有节点的度之和为边的两倍
入度和出度是对于有向图而言的
什么是路径，什么是路径长度，如何判断是否有回路？
路径即点的序列，路径长度即边的数目
如果有n个点，有超过n-1条边，则一定有环
n个顶点，有向图中，每个顶点的度数最多为多少
2（n-1）
因为有向图中，两个顶点之间可以互相指向，即存在两条边
做题的时候完全看懂题目，不要怕，只要你完全按照题目意思来，就不会有做不出来的，你怕啥呢，题目充分读懂，选出正确的选项，做出来之后你就是最牛逼的，绝对正确
逻辑结构
非线性结构
存储结构
邻接矩阵法（顺序存储）
存储结构描述
使用一个二维数组，1则表示两顶点之间存在边，0则表示两顶点之间不存在边
邻接矩阵法所需的存储空间为O(|V|平方)
邻接表法（顺序存储+链式存储）
存储结点描述
图
顶点表结点
边表结点
代码思想
一个整体的图的结构体，存储这个数组和当前定点数（数组），边数
一个顶点的结构体，存储这个顶点的数据（数据），和这个顶点的第一个出边（边指针）
一个边的结构体，用来存储当前这个边的终点是哪个顶点（数组索引），以及下一个边的指针（边指针）
总结
树的孩子表示法，图的邻接表法，散列表的拉链法，以及基数排序，均是使用这种思想
需要三个结构体
第一个是整体的，包含一个数组以及一些数量信息
第二个是这个数组元素的结构体，包含这个节点的value值和这个节点的孩子的链接
第三个是边的结构体
包含这个边指向的终点是哪个顶点（通常就是数组的一个下标），加上指向下一个兄弟的指针
所谓邻接表，是指对图G中每个顶点vi建立一个单链表，第i个链表的结点表示依附于顶点vi的边（对于有向图而言则是以顶点vi为尾的弧），这个单链表就叫做顶点vi的边表（对于有向图则称为出边表）
对于无向图来说，邻接表法所需空间为O(|V|+2|E|)；对于有向图来说，邻接表法所需空间为O(|V|+|E|)
十字链表法（链式存储）
只用来存储有向图
十字链表法所需空间为O(|V|+|E|)
邻接多重表（链式存储）
只用来存储无向图
邻接多重表所需空间为O(|V|+|E|)
Remark
图的邻接表表示唯一吗？
不唯一，顺序可以打乱
图的特殊存储方式
十字链表
不唯一，但是可以确定一张图
邻接多重表
同一个结点在邻接多重表只出现一次，但是在邻接表出现多次
邻接表的访问时间复杂度
n+e
一个节点在邻接表中出现的次数取决于什么？
取决于它的入度
一定要想清楚，不能稀里糊涂的做，那肯定是稀里糊涂的错
操作
基本操作
P209
图的遍历
广度优先搜索BFS
代码实现
算法性能分析
空间复杂度
最坏空间复杂度为O(V)
时间复杂度
采用邻接矩阵存储
O(|V|平方)
采用邻接表存储
O(|V|+|E|)
BFS算法求解单源最短路径问题
广度优先生成树
图的广度优先遍历序列就是其广度优先生成树的层序遍历序列
是否唯一
取决于存储方式
如果是邻接矩阵，则唯一
如果是邻接表，不唯一
演示
深度优先搜索DFS
代码实现
性能分析
空间复杂度O(|V|)
时间复杂度
采用邻接矩阵存储
O(|V|平方)
采用邻接表存储
O(|V|+|E|)
深度优先生成树和生成森林
图的深度优先遍历序列就是其深度优先生成树的先序遍历序列
唯一与否取决于存储方式，若是邻接矩阵存储则是唯一的（因为邻接矩阵存储结果是唯一的），若是邻接表存储的则可能不唯一（因为邻接表存储的结果不是唯一的）
注意点
可以用来判断回路，BFS不行
图的遍历与图的连通性
对于无向图来说，若无向图是连通的，则从任意结点出发都只需要一次遍历就能访问完所有结点，若无向图是非连通的，则需要多次从不同结点出发再次开始遍历，故在遍历算法中BFSTraverse()或DFSTraverse()中调用BFS()或DFS()的次数等于该图的连通分量数
对于有向图来说，一个连通的图分为强连通的和非强连通的，它的连通子图也分为强连通分量和非强连通分量，非强连通分量无法通过一次遍历访问到所有的结点
Remark
BFS的时空复杂度
空间复杂度
V
时间复杂度
邻接表
V+E
邻接矩阵
V^2
DFS的时空复杂度
与BFS一样
搜索得到的生成树都一样吗？
如果是邻接表存储，则可能不同
对于无向图，调用几次dfs就有几个连通分量吗？对于有向图呢？
对于无向图是
对于有向图不是
dfs递归访问一个有向无环图，每次退出时打印，是拓扑序列吗？
不是，是逆拓扑序列
每次都dfs到一个没有后继的结点
图的应用
最小生成（代价）树
一个图的生成树可能有很多种，各边权值之和最小的那棵生成树称为最小生成树MST
Prim算法
算法描述
初始时从图中任取一个顶点加入树T，此时树中只含有一个顶点，之后选择一个与当前T中顶点集合距离最近的顶点，并将该顶点和相应的边加入T，每次操作后T中地顶点数和边数都增1
时间复杂度
O(|V|平方)
Kruskal算法
算法描述
每次选择权值最小的边，是这条边的两头连通（原本已经连通的就不选）
时间复杂度
O(|E|log|E|)
注意点
最小生成树的唯一性
如果每个边的权值都不同，则最小生成树唯一
什么时候最小生成树不唯一？
存在边的权值相同
不一定不唯一
例如最小生成树，已经是唯一的一棵树了，就算存在相同的边权，也改变不了
存在边权相同，且满足某种关系
才不唯一
最短路径
带权路径长度最短的那条路径
Dijkstra算法求单源最短路径问题
算法描述
开始时先选出与已知顶点邻接的边中权值最小那条边，将这条边邻接的另一个顶点并入集合S，然后更新与已并入集合S的每个顶点的邻接顶点到初始顶点的距离，并找出新并入的顶点邻接的边中权值最小的那条，将这条边邻接的另一个顶点并入集合S，再次更新已并入集合S的每个顶点的邻接顶点到初始顶点的距离（过程见P229）
时间复杂度
邻接矩阵法和邻接表法存储的时间复杂度都是O(|V|平方)
Floyd算法求各顶点之间最短路径问题
有向无环图描述表达式
概念
有向无环图
若一个有向图中不存在环，则称为有向无环图，简称DAG（Directed Acyclic Graph）图
二叉树描述表达式 VS 有向无环图描述表达式
有向无环图可实现相同子式的共享
拓扑排序
每个AOV（Activity On Vertex Network）网都有一个或多个拓扑排序序列
每次找到入度为0的顶点并将其取出，并删除它和它的所有相关弧，再从剩下的图中找到入度为0的顶点并将其取出，然后删除它和它的所有相关弧，以此类推，知道没有顶点剩余
注意点
有向无环图的拓扑序列不能唯一确定一张图
关键路径
从源点到汇点的所有路径中，具有最大路径长度的路径称为关键路径，而把关键路径上的活动称为关键活动
缩短工期
若关键路径不止一条，必须缩短所有关键路径
如果只缩短一条关键路径，则无作用
缩短单一的关键活动
有可能无用，因为可能导致这条路不是关键路径了
概念
源点（开始顶点）
汇点（结束顶点）
事件vk的最早发生时间ve(k)
max()
事件vk的最迟发生时间vl(k)
min()根，据结果的时间倒推
活动ai的最早开始时间e(i)
等于事件的最早发生时间
活动ai的最迟开始时间l(i)
终点时间减持续时间
活动可以推迟的时间
d(i)=l(i)-e(i)
Remark
最小生成树什么时候唯一，什么时候不唯一
如果每个边的 权都不相同，则唯一
如果存在边的权相同，也不一定不唯一
prim算法的基本过程
选择一个离当前区域最近的点加入
prim算法的时间复杂度
V^2，与E无关系，适合稠密图
kruskal算法的时间复杂度
ElogE，适合稀疏图
dijkstra的缺点
不能处理负边权
Floyd的特点
可以处理负边权，但是不能处理带负边的环
拓扑排序唯一吗？
当然不唯一
拓扑排序的时间复杂度
V+E
如果一个节点有唯一的前驱或者后继，那拓扑排序唯一吗？
当然唯一
存在拓扑排序，一定是三角矩阵吗？
不一定
AOE网存在多个起点或者终点吗？
不存在，都只有一个
关键路径上的活动都是关键活动吗？
是的
加快关键活动能缩短工期吗？
缩短一条的没用，必须把每条关键路径都缩短才能缩短工期
一直缩短一个也没用，可能搞成不是关键活动了
最短路径一定是简单路径吗？
是的，无重复的点
拓扑排序中暂存入度为0的点，可以用栈吗？
可以的，栈和队列都可以
有序的拓扑序列的邻接矩阵一定是三角矩阵吗？
一定是
一个拓扑序列可以对应多个图吗？
当然可以
把算法的过程回想清楚再去做题，把会的全部发挥出来，要不然只能拿最简单的题目
7.查找
概念
静态查找表、动态查找表
静态查找表
查找表的操作只涉及查找
动态查找表
查找表的操作不仅涉及查找，还涉及插入和修改
关键字
数据元素中唯一标识该元素的某个数据项的值
平均查找长度
所有查找过程中进行关键字的比较次数的平均值，是衡量查找算法效率的最主要的指标
Remark
基于关键字的查找结果会有多个吗？
不会，关键字唯一标识
衡量查找算法的效率的指标是什么？
平均查找长度
平均查找长度
关键字的比较次数
按存储结构分类
线性结构
顺序查找
一般线性表的查找
算法描述
查找成功和查找失败的平均查找长度
ASL成功=(n+1)/2
ASL不成功=n+1（注意是n+1次比较才能判断不存在）
可以通过将概率较大的放在前面，减小平均查找长度
优缺点
优点
对数据存储没有要求，无论是顺序存储还是链式存储皆可，对表中记录的有序性也没有要求，无论记录的关键字是否有序，均可应用
缺点
当n较大时，平均查找长度较大，效率低
有序表的顺序查找
前提：查找之前就已经知道表是关键字有序的，查找失败时不需要查找整个表就可以得知查找失败，从而提高查找效率
判定树：用来描述有序表的查找过程，圆形结点表示已存在的元素，矩形结点称为失败结点（由n个圆形结点，代表判定树中有n+1个失败的结点）
查找失败的平均查找长度
n/2+n/(n+1)
存储结构的要求
可以是顺序存储（按照数组下标递增来顺序扫描每个元素
可以是链式存储（通过指针next来依次扫描每个元素）
折半查找
定义
折半查找又称二分查找，它仅适用于有序的顺序表，并且要求很方便的定位查找区域，所以它要求线性表必须具有随机存取的特性，所以此查找法只适用于顺序存储结构，且要求元素按关键字有序排列
算法描述
判定树
是一棵平衡二叉树
特点
由于折半查找的特点，每一次会有一个偏好选择，那就是选择上面的那个还是下面的那个
时间复杂度
O（log2n）
平均情况下效率高于顺序查找，但不是所有情况下都高于
存储结构的要求
只适用于顺序存储的存储结构（要求有随机存储的特性）
分块查找
定义和基本思想
又称索引顺序查找
吸收了顺序查找和折半查找各自的优点
既有动态结构，又适合快速查找
实现思想
将查找表分为若干块，块内元素可以有序也可以无序
在建立一个索引表
索引表包含每一个块的最大元素，以及第一个元素的地址
索引表按关键字有序排列
特点
第一个块的最大元素小于第二个块的最小元素
索引块包含两个信息
最大元素的值
索引块代表的第一个块的位置
查找过程
第一步先在索引表中确认代查记录所在的块，可以用顺序查找或折半查找来查找索引表，第二步在找着的块内进行顺序查找
平均查找长度
将长度为n的查找表均匀的分为b块，每块有s个记录，等概率情况下，其平均查找长度需要分如下情况考虑
当块内和索引表中均采用顺序查找
当对索引表采用折半查找，块内进行顺序查找
Remark
顺序查找的ASL
成功(n+1)/2
失败n+1，因为每次都是从第一个开始找，而且要对第n+1个查找之后才能确定查找失败
顺序查找可以如何优化？
按查找概率由大到小排列，性能可能很好
n个结点会有多少个查找失败情况？
n+1个
有序线性表的ASL
记住那棵树
折半查找适用于有序线性表吗？
不一定，线性表可以使用顺序表实现，也可使用链表实现
折半查找的左右指针是怎么变的？
左右指针一定有一个等于mid-1或者mid+1，不能等于mid，会有问题的
折半查找的判定树一定是平衡二叉树吗？
一定是平衡二叉树，故也是二叉排序树
mid指针对折半查找树的影响
相邻节点是大的在上面还是小的在上面
折半查找树的树高为多少？
按完全二叉树的来算
分块查找是什么意思？
块内无序，块间有序
索引表记录每一块最大的关键字和该块第一个元素的地址
分块查找的时间复杂度
顺序+顺序
b+1/2+s+1/2
二分+顺序
树高+s+1/2
树形结构
二叉排序树
删除操作
叶节点
直接删除
只有左子树或右子树
子树直接顶上
既有左子树又有右子树
寻找前驱或者后继，也就是左子树中最大的或者右子树中最小的
二叉平衡树
旋转
LL
将第一个不平衡的结点 的 引起不平衡的那个孩子 右旋到最上面
RR
LR
将第一个不平衡的结点 的 引起不平衡的孩子 的 引起不平衡的孙子先左旋到上面，再右旋到上面
RL
注意点
LL或者RR处理的是第一个不平衡的结点的那个引起不平衡的孩子
LR或者RL处理的是第一个不平衡的结点的那个引起不平衡的孩子的引起不平衡的孙子
树高与结点个数
红黑树
B树
定义
B树，又称多路平衡查找树，B树中所有结点的孩子个数的最大值称为B树的阶，通常用m表示
性质
一棵m阶B树或为空树，或为满足以下特性的m叉树
根节点
至少有一个关键字
两个子树
非根节点
至少有m/2上取整个孩子
m/2上取整减一个关键字
叶子结点
B树所有叶结点都在同一层
叶子结点不带任何信息，可以视作查找失败点
特殊性质
B树是所有结点的平衡因子都为0的多路平衡树
子树个数一定是关键字个数加1，即便没有真正的子树，那也有一个指向空节点的
结点内部关键字有序排列，关键字的两侧均有指向子树的指针
所有叶节点都落在最后一层，并且叶节点的个数为n+1（n是关键字的个数）
基本操作
B树的高度
即最长路径的长度，以结点数为度量，磁盘读取的次数
最小高度
满m叉树
最小高度
根节点仅一个，第二层仅两个， 之后的每个节点都有最小限额关键字数
通过第h+1层至少要包含n+1叶节点的关系来推
B树的查找
B树的查找包括两个基本操作
1)在B树中找结点（磁盘中进行）
2)在结点内找关键字（内存中进行）
可以顺序查找，也可以二分查找
查到叶节点时，代表失败
B树的插入
1）定位。插入位置一定是最低层的某个非叶结点
2）插入。当插入后的结点关键字个数大于m-1，则必须对结点进行分裂
分裂的方法
在插入后的结点中，从中间位置（m/2向上取整）将其中的关键字分为两部分，左半部分包含的关键字放在原结点中，右半部分形成兄弟结点，中间的（m/2向上取整）的结点放入父结点
概括
分裂成左右两个，中间的那个上去当爹
B树的删除
删除的关键字k不在终端结点中
用k的前驱或后继k'来替代k，而k'一定是在终端结点中，所以就把问题转化为了被删关键字在终端结点中的情形
删除的关键字k在终端结点中
1) 直接删除关键字
若删除后结点的关键字个数仍满足B树的特性，则直接删除
2) 兄弟够借 即大于等于m/2上取整
右兄弟结点最小的关键字（或左兄弟中最大的关键字）移到父结点中，父结点中的关键字移动到被删的结点中
概括
下来一个爹当补充，上去一个兄弟当爹
3) 兄弟不够借
将其与左兄弟（或者右兄弟）的关键字及其父结点中对应的关键字全部合并为一个结点
双亲结点的关键字会减一
概括
将爹和兄弟都合并到自己这里来
注意点
叶节点的个数
叶节点就是失败结点，n个数有n+1种失败的可能
结点个数与层数的关系
极端情况下根节点可以取一个或者取满都行，不用管下面怎么样
随机查找和顺序查找
随机查找和随机访问不是一个意思，随机查找的意思是下一个访问的序号是不确定的，而随机访问指的是给出下标可以O(1)读取元素
顺序查找就是每次只能从头开始访问，顺序访问更强调一种顺序性
B+树
定义
B+树中所有结点的孩子个数的最大值称为B+树的阶，通常用m表示
性质
根节点
至少两个孩子
至少两个关键字
非根节点
至少m/2上取整个关键字
至少m/2上取整个孩子
只包含所有子节点中关键字的最大值及指向该结点的指针
结点的关键字个数和孩子个数相等
叶节点
B+树的叶节点不是B树的那种失败叶节点，而是有实际意义的叶节点
叶节点都包含关键字和指向记录的指针
B+树的每个结点都是实打实指向孩子结点的，而不是像B树那样只是指向一个区间
叶节点中关键字按大小顺序排列
相邻叶节点之间通过指针连接
B+树和B树的主要差异
B+树中关键字是重复的，非叶结点的关键字都会出现在叶结点中；而在B树中，叶结点包含的关键字和其他结点包含的关键字是不重复的
子树个数与关键字个数的关系不同，相应的关键字个数范围也不同
B+树中，叶结点包含信息，所有非叶结点仅起索引作用，每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址
通常在B+树中有两个头指针，一个指向根结点，一个指向关键字最小的叶结点。因此，可以对B+树进行两种查找运算：一种是从最小关键字开始的顺序查找，另一种是从根结点开始的多路查找
B+树的查找，无论成功与否，都是一条从根节点到叶节点的路径
Remark
二叉排序树可以是空树吗？
可以
对二叉排序树进行前序遍历得到有序序列吗？
不对，是通过中序遍历
二叉树排序树的删除怎么进行
叶节点直接删除
一个孩子则直接继承
两个孩子则需要找直接前驱或者后继，即左孩子的最右下结点，或者右孩子的最左下结点
若被删除的结点的前驱或者后继还有子节点怎么办？
将前驱或者后继的子节点直接连到其的父节点上
二叉排序树结点删除后再插入一定一样吗？
如果是叶节点，则一定一样
如果不是叶节点，则一定不一样
相同的关键字不同的插入顺序会导致二叉排序树不同吗？
会，所以二叉排序树不唯一，但是二分查找的判定树唯一
平衡因子是什么？
左子树和右子树的高度差
平衡二叉树调整的对象？
第一个不平衡的结点
平衡二叉树旋转的类型怎么判断？
根据第一个不平衡点的儿子和孙子的方向得到旋转类型
与真正插入的那个节点的方向其实没直接关系
LL或者RR的旋转过程
不平衡点的儿子去当爸爸，注意旋转的名字和旋转的方向是相反的
LR或者RL的旋转过程
不平衡点的孙子去当爸爸，注意旋转的名字和旋转的方向是相同的
平衡二叉树的插入最多引起多少次调整？删除呢？
插入最多引起一次调整，删除可能引起多次调整
平衡二叉树高度和最少节点数的关系
0 1 2 a+b+1
用来判断给定节点数的平衡二叉树的最多查找次数
红黑树的要求
只有红结点或者黑结点
根节点为黑结点
叶子结点为黑结点
红结点不能相邻
任何一条路径的黑结点数目相同
红黑树的结论
最长路径不超过最短路径的两倍
红黑树的树高是平衡二叉树的两倍，即任一结点的左右子树的高度不超过两倍
红黑树的调整
如果叔叔结点是红色
父亲结点和叔叔结点变成黑色
爷爷结点变成红色
如果叔叔结点是黑色
如果自己是右孩子
通过左旋自己当爹
如果自己是左孩子
父亲和爷爷变色，再右旋
红黑树的时间复杂度和AVL树相同吗？
全部相同
红黑树如果只有黑色结点，则一定是满二叉树
B树的阶是孩子的个数还是关键字的个数？
是孩子的个数
B树根节点一定有两个子树吗？
不对，根节点最少有两个子树，最多应该是m-1
B树除了根节点的分支节点的孩子个数
最少为m/2上取整个孩子
最多为m个
B树的叶节点都携带信息，并且出现在最后一层吗？
都不携带信息，不过确实都出现在最后一层
B树每个节点的平衡因子都是0吗？
对的，都是0
有哪些结构不能为空？
度为k的树
图的点不能为空
B树中的关键字一定有序吗？
一定有序
B树的结点数与层数的关系
最多结点数，则每一层都是满的
最少节点数，根节点两个孩子，其他的都是最低限额
B树的查询过程
先找到一个节点，在结点内进行二分查找，可能找到，也可能通过指针找到子树
如果指向了叶节点，则代表查询失败
B树的插入过程
找到最底层的某个非叶节点
插入后如果结点个数不合法，则需要进行分裂
B树的分裂
第m/2上取整个元素提取到父节点，左边的作为左孩子，右边的加入一个新节点作为中间节点的右孩子
B树的删除
若删除结点不是叶节点，则将它的前驱或者后继填入当前节点，最后一定要对叶节点进行删除操作
若兄弟够借
则父亲下来一个，兄弟上去一个当爹
若兄弟不够借
则自己和兄弟加上一个父亲组成新的节点
B+树
父子节点的关系
每个关键字指向一个子节点，所以关键字个数和孩子个数相同
父节点的每个关键字指向一个子节点，这个子节点的最大关键字即父节点的关键字（B+树中的关键字重复出现很多次）
结点内部关键字有序
节点关键字个数
非叶根节点最少两个，普通分支结点为m/2上取整个，最多为m个
叶节点
叶节点包含所有的关键字，并含有指向相应记录的指针
叶节点按大小排序，并且所有叶节点之间还有指针连接，可以通过顺序访问
与B树的对比
B树的内部节点的叶节点就是一个普通的结点，再往下就是失败结点
B+树的叶节点不仅包括所有的关键字，还包括指向该关键字的记录
头指针
B+树有两个头指针，一个指向根节点，一个指向关键字最小的结点
B+树的查找过程
B+树查找到了关键字后不会停止，而是一直往下找，直到叶节点
即无论成功与否，都是一条从根到叶节点的路径
B树和B+树的使用场景
B树更多用于磁盘IO中
B+树更多用于数据库中
散列结构
散列表
基本概念
散列函数：一个把查找表中的关键字映射成该关键字对应的地址的函数，记为Hash(key)=Addr（这里的地址可以是数组下标、索引或内存地址等）
冲突：散列函数可能会把两个或两个以上的不同关键字映射到同一个地址
同义词：这些发生冲突的不同关键字称为同义词
散列表：可以根据关键字直接进行访问的数据结构，也就是说，散列表建立了关键字和存储地址之间的一种直接映射关系
理想情况下，散列表的查找时间复杂度是O(1)
散列函数的构造方法
直接定址法
取关键字的某个线性函数值为散列地址，散列函数为H(key)=key或H(key)=a*key +b
优点：不会发生冲突；缺点：若关键字分布不连续，会造成许多的浪费
除留余数法
假定散列表表长为m，取一个不大于m但最接近或等于m的质数p，利用公式H(key)=key%p 把关键字转换为散列地址
最简单、最常用的方法
数字分析法
平方取中法
处理冲突的方法
开放定址法
散列函数：Hi = (H(key) +di) % m，i表示第几次发生冲突，di为增量序列
1.线性探测法
di = 0,1,2,3,...,m-1
2.平方探测法
di = 0,1的平方,-1的平方,2的平方,-2的平方,...,k的平方,-k的平方
3.再散列法
准备多个散列函数，当冲突发生时用另一个散列函数计算一个新地址，直到不发生冲突
4.伪随机序列法
di = 伪随机序列
注意点
删除元素时不能直接删除，做一个删除标记即可
本质区别在于增量序列di的取值方法不同
拉链法
对于不同关键字可能会通过散列函数映射到同一地址，为了避免非同义词发生冲突，可以把所有的同义词存储在一个线性链表中
适用于经常进行查找和删除的情况
查找长度ASL
成功
当然只有在散列表里的会成功
失败
注意，一般是根据余数来决定位置，所以若对m取模，最多有m种余数的情况
如果发生冲突，则按照冲突处理方法继续探测，直到探测位置为空，此时也算一次比较
越早遇到空位置，越早确定失败
性能分析
散列表的查找效率取决于三个因素：散列函数、处理冲突的方法和装填因子（表中记录的个数n与散列表的长度m的比值）
散列表的平均查找长度依赖于散列表的装填因子（使用/容量），而不直接依赖于n或m
Remark
查找一定基于比较吗？
不一定，散列表不是
散列函数
关键字->地址
散列函数的问题
可能会有冲突
需要有处理冲突的方法
散列表的时间复杂度
O(1)
与元素个数无关
堆积现象
大量元素在相邻的地址分布
有哪些处理冲突的方法？
开放定址法
拉链法
开放定址法能直接删除元素吗？
不可以，开放定址法让一个关键字可以出现在任意位置，如果随意删除截断，会有问题
拉链法是什么？适合什么情况使用？
经常插入删除
散列表的成功和失败查找有什么特点？
成功查找只会出现在那几个关键字的情况，均匀计算即可
失败查找只会出现在可能出现在的几个关键字，均匀计算即可
散列表的时间复杂度？
理想情况下是1，但是因为存在冲突，所以并不一定
散列表的平均查找长度依赖于什么？
散列函数
处理冲突的方法
装填因子
不直接依赖于m或n，由他们共同决定
8.排序
基本概念
排序：就是重新排列表中的元素，是表中的元素满足按关键字有序的过程
算法的稳定性：两个不同元素具有相同的关键字，在排序的前后，两个元素的相对位置不变，则称该算法是稳定的，否则，称该算法是不稳定的
内部排序的性能
比较次数
移动次数
Reamrk
算法的稳定性与优劣无关
并非所有的排序算法都基于比较
基数排序就不基于比较
内部排序
排序过程中数据元素全部存放在内存中
插入排序
基本思想
每次将一个待排序的记录按其关键字大小插入前面已经排好的序的子序列
直接插入排序
基本思想
比较关键字的过程中将大于关键字L(i)的元素依次后移一个位置，直到查找出第一个小于L(i)的元素，其后一个位置就是需要插入的位置k，将L(i)复制到L(k)
算法实现
边查找边后移
性能分析
空间效率
O(1)
时间效率
最好情况下，表中的元素已经有序，每插入一个元素都只需要比较一次而不用移动元素，因而时间复杂度为O(n)；最坏情况下，表中的元素顺序刚好与排序结果中的元素顺序相反，因而时间复杂度为O(n的平方)
稳定性
直接插入排序是稳定的
适用性
直接插入排序适用于顺序存储和链式存储的线性表，且基本有序、数据量不大的排序表
折半插入排序
基本思想
将比较与后移操作分离，查找的过程可以用折半查找来实现，先通过折半查找来查找到插入位置k，再将关键字插入到这个位置
算法实现
性能分析
空间效率
O(1)
时间效率
比较次数相比于直接插入排序减少了，约为O(nlog2n)
但移动次数并未改变，它依赖于待排序表的初始状态，最坏情况为O(n的平方)
所以，折半插入排序的时间复杂度仍为O(n的平方)
稳定性
折半插入排序是稳定的
适用性
数据量不很大的顺序表
希尔排序
基本思想
将表按照位置间隔分为几个子序列，对子序列分别进行直接插入排序，该过程称为一趟排序，之后，缩小位置间隔d(i+1)=di/2向下取余，再次对子序列分别进行直接插入排序。（第一趟的位置间隔为d1=n/2）
算法实现
一目了然的实例过程见P298
性能分析
空间效率
O(1)
时间效率
n在某个特定范围的时候，时间复杂度为O(n的1.3次方)；最坏情况下，时间复杂度为O(n的平方)
稳定性
不稳定
适用性
仅适用于线性表为顺序存储的情况
交换排序
根据序列中两个元素关键字的比较结果来对换两个记录在序列中的位置
冒泡排序
基本思想
从后往前，比较相邻的两个元素的关键字，若为逆序，则交换两个元素的位置后继续比较下一对相邻元素，若为正序，则直接比较下一相邻的元素，直到比较完毕。每一次冒泡排序的结果是将剩下的序列中最小的放到它最终的位置上，所以每次排序都至少有一个元素被放到它最终的位置，结果只需要最多n-1次排序就可以完成排序
算法实现
性能分析
空间效率
O(1)
时间效率
最好情况下，初始序列本来就是有序的，所以一趟排序过后，比较次数为n，移动次数为0，故时间复杂度为O(n)；最坏情况下，时间复杂度为O(n的平方)
稳定性
冒泡排序是稳定的
适用性
顺序和链式都可以
若一次过程中一次都没有发生交换，代表已经有序，可以结束了(可能提前结束)
快速排序
基本思想
基于分治法的，在待排序表中任取一个元素pivot作为基准（通常取首元素），经过一趟排序后，使得基准的右边全部大于等于pivot，基准的左边全部小于pivot，每次排序结束时，基准元素都会位于其最终的位置上
生成一个递归树！！！每次都处理更小的问题
所以第一轮会确定一个数的最终位置，第二轮又会确定两个数的最终位置，并且这两个数应该一个大于，一个小于第一个数
算法实现
一目了然的实例过程见P304
性能分析
空间效率
最好情况下为O(log2n)，最坏情况下为O(n)，平均情况下为O(log2n)
时间效率
最坏情况下为O(n的平方)，最好情况下为O(nlog2n)，快速排序平均情况下的运行时间与其最佳情况下的运行时间很接近，而不是接近其最坏情况。快速排序是所有内部排序算法中平均性能最优的排序算法
稳定性
快速排序算法是不稳定的
选择排序
基本思想是每一趟（如第i趟）在后面n-i+1个待排序元素中选取关键字最小的元素，作为有序字序列的第i个元素，直到第n-1趟做完，待排序元素只剩下一个就不用再选了
简单选择排序
基本思想
第i趟排序从L[i...n]中选择关键字最小的元素与L(i)交换，每一趟排序可以确定一个元素的最终位置，这样经过n-1趟排序就可以使得整个排序表有序
算法实现
性能分析
空间效率
O(1)
时间效率
移动的操作不会超过3(n-1)次，最好情况是0次；比较次数与序列的初始情况无关，始终是n(n-1)/2次，因此时间复杂度始终是O(n的平方)
稳定性
简单选择排序是不稳定的
堆排序
基本概念
堆
大根堆（大顶堆）
小根堆（小顶堆）
基本思想
首先将存放在L[1...n]中的n个元素建成初始堆，由于堆本身（以大根堆）的特点，堆顶元素就是最大值；输出堆顶元素后，通常将堆底元素送入堆顶，此时堆已被破坏，将堆顶元素向下调整使其再次保持大顶堆的特性，再输出堆顶元素，如此重复
构造初始堆
从第(n/2向下取整)个结点的开始向上调整直到根结点，比较结点值与其孩子的值大小，若大于其左右结点的值，则调整下一个结点，若不都大于其孩子结点的值，则将其与孩子结点中的最大值与之交换
线性时间构成一个堆
算法实现
构建大顶堆
堆排序算法
性能分析
空间效率
O(1)
时间效率
O(nlog2n)
稳定性
堆排序是不稳定的
归并排序
将两个或两个以上的有序表组合成一个新的有序表
基本思想
假定待排序表含有n个记录，则可将其视为n个有序的子表，每个字表的长度为1，然后两两合并，得到（n/2向上取整）个长度为2或1的有序表，如此重复，继续两两归并，这种排序方法称为2路归并排序
算法实现
性能分析
空间效率
O(n)
时间效率
每趟归并的时间复杂度为O(n)，共需进行（log2n向上取整）趟归并，所以算法的时间复杂度为O(nlog2n)
稳定性
归并排序是稳定的
基数排序
是一种很特别的排序方法，它不基于比较和移动进行排序，而是基于关键字各位的大小进行排序
基本思想
按照最高位优先（MSD）法或者最低位优先（LSD）法，按关键字位权重递减或递增依次划分，每次划分时，先是分配，后是收集，一目了然的实例过程见P323
性能分析
空间效率
O(r)，r为需要队列的个数
时间效率
O(d*(n+r))，与初始状态无关，d为分配收集的次数，一趟分配的时间复杂度为O(n)，一趟收集所需的时间复杂度为O(r)
稳定性
基数排序是稳定的
Remark
折半插入排序的比较次数与初始排列有关吗？插入排序呢？
折半插入排序的比较次数与初始序列无关
插入排序的比较次数与初始序列有关
插入排序在什么情况下效果特别好？
在待排序列比较有序的时候，复杂度接近O(n)
希尔排序的设计思想
利用了插入排序适合在数据量小且比较有序的情况下工作
希尔排序的间距n是什么意思？
每n个挑一个
冒泡排序最快几趟可以结束？
如果初始序列有序，则只需要一趟
注意各种排序都有从小到大或者从大到小两种，考试时别被这些小把戏骗了
快排的空间复杂度
最好
logn
最坏
n
平均
logn
快排最好和最坏的情况
最坏
划分的特别不均匀
即基本有序的情况
最好
能用pivot划分的特别均匀
平均性能最好的排序是哪个？
快排
时间复杂度一般指的是平均还是最坏？
最坏
快排的速度不仅取决于第一次的划分，同样取决于后序的划分！
如果发现排序的题目很奇怪，那可能是方向反了，不一定是传统的选小的达成从小到大
选择排序的特点
比较次数
固定位n(n-1)/2
移动次数
最少为0次，最多也就是3(n-1)次
堆是一个完全二叉树吗？
是的
建堆的时间复杂度
O(n)
堆排序的适用情况
适合关键字特别多的情况
堆排序的最好，最坏和时间复杂度
均为nlogn
两个长度分别为m和n的有序段进行归并时，最多比较多少次，最少呢？
最多m+n-1次
最少min(m,n)次
归并排序每一趟要进行多少次合并？
n/2h上取整，h为归并段的长度
归并排序总共要进行多少次归并？
logn上取整次，即通过叶节点的数目推树的高度
k路归并排序的归并趟数
logk(n)上取整
多关键字比较排序的要点
先按权值低的来排序
对权值高的排序时一定要使用稳定的排序算法
基于比较的排序算法最低复杂度是多少？
nlogn
堆排序可以使用链式存储实现吗？
可以，但是会慢很多，包括希尔排序也是这样
冒泡排序的比较次数
冒泡排序是当发现有序时则停止，不是一趟就可以停止，这个性质要注意一下，碰到排序算法的题目，想一想具体的过程，不能空想
排序算法归总
子主题
排序算法 时间复杂度 空间复杂度 稳定性 适用情况 插入排序 n^2 1 稳定 顺序+链式 折半插入排序 n^2 1 稳定 顺序 希尔排序 \ 1 不稳定 顺序 冒泡排序 n^2 1 稳定 顺序+链式 快速排序 nlogn logn 不稳定 顺序+链式 选择排序 n^2 1 不稳定 顺序+链式 堆排序 nlogn 1 不稳定 顺序+链式 归并排序 nlogn n 稳定 顺序+链式 基数排序 d(n+r) r 稳定 \
各种内部排序算法的比较及应用
比较
应用
考虑因素
待排序的数目
待排序元素的信息量
关键字的结构及其分布
稳定性的要求
存储结构，辅助空间的要求
选择
若n较小
插入排序或者选择排序都可以
选择排序由于移动次数更少，所以在元素信息量很大时，更好
若元素基本有序
插入排序或者冒泡排序都可以
若n比较大
当关键词平均分布时，快排平均时间最好
堆排序需要的空间小于快排，并且不会出现快排的最坏时间
堆排序的平均比较次数最少
均不稳定
归并排序
稳定，且时间复杂度也稳定
基于比较的排序算法中，至少需要nlogn的复杂度
若n比较大，且关键字位数少可分解时，基数排序较好
若记录本身信息量大，为了避免大量移动，可以使用链表
外部排序
基本概念
需要将待排序的记录存储在内存上，排序时再把数据一部分一部分地掉入内存进行排序，在排序过程中需要多次进行内存和外存之间的交换
主要考虑IO次数
外部归并的主要时间
内部排序
IO读写
若有n个磁盘块，则每次需要读n次，写n次
内部归并
K路平衡归并
平衡归并排序与归并排序区分开来，一个是严格k叉树一个是k叉树
对于r个初始段，进行K路平衡归并，归并趟数为树的高度减1，即logk(r)上取整次
为了减少IO次数
增大归并路数
带来了一个问题，内部排序的比较次数大大增加
需要进行S趟归并
每次归并需要处理n个元素
每个元素需要进行k-1从比较
故总比较次数为S*(N-1)*(K-1)
可以看出，总比较次数随着归并路数的增加而增加
引入败者树
首次建立需要k-1次比较
后续每次只需要log2(k)上取整次
故总比较次数为(n-1)log2(r)
优点
内部比较次数与k无关
缺点
需要很大的缓冲区
减少初始归并段
归并段的大小依赖于内存工作区的大小
引入置换选择算法
优点
可以生成大于内存工作区的初始归并段，减少后序归并时的IO次数
缺点
每个归并段的长度不同
引入最佳归并树
目的
组织不同长度的初始归并段，使得IO次数最少
特点
叶节点到根节点的路径长度就是趟数
树的WPL就是记录的读取次数
所以IO次数应该是WPL*2
必须是严格K叉树
若结点数不够
添加虚段
令u=(n-1)%(k-1)
若u是0
正好可以
若u不是0
添加k-1-u个初始零归并段
败者树
引入原因
增加归并路数k能减少归并趟数S，进而减少I/O次数，然而，增加归并路数k，会使内部归并的时间增加，比较次数为S(n-1)(k-1)，其中S=(logkr向上取整)，为了使内部归并的比较次数不受k的影响，引入了败者树。使用败者树后，每次归并需要比较的次数为（log2k向上取整），所以比较次数变为(n-1)(log2r向上取整)，与k无关，因此只要内存空间允许，增大归并路数能有效地减少归并树的高度，从而减少I/O次数，见书P336
定义
在比较关键字时引入败者树，k个叶结点分别存放k个归并段在归并过程中当前参加比较的记录，内部结点用来记忆左右子树中的失败者，而让胜利者往上继续比较，一直到根结点
过程(书P336)
特点
置换-选择排序（生成初始归并段）
增大归并段长度，从而减少归并段个数r，从而减少归并的趟数S
实例排序过程：见P337
最佳归并树
定义
经过置换-选择排序之后，得到的是长度不等的初始归并段，所以最佳归并树解决的是如何组织长度不等的初始归并段的归并顺序使得I/O次数最少，为此将哈夫曼树的思想推广到k叉树
过程
当初始归并段个数可以正好构成一个严格的k叉树时
应用哈夫曼树的思想构造最佳归并树
（结点的值为归并段的长度）
当初始归并段个数不足以构成一个严格的k叉树时
添加(k-u-1)个长度为0的"虚段"，其中u=(n0-1)%(k-1)，n0为初始归并段个数，k为归并的路数
（结点的值为归并段的长度）
Remark
外部排序的问题及解决方法
多次IO开销大，要降低IO次数
主要途径
增大归并路数
减少初始初试归并段个数
外部排序各种问题的解决
败者树
减少内部归并的比较次数
置换选择排序
增大初始归并段
最佳归并树
解决长度不同的归并段的归并顺序
外部排序的IO次数
内部排序-N*2
外部归并-N*2*k
归并树
是完全K叉树吗？
是的，只有度为0和K的树
归并趟数与树高的关系
归并趟数为树高减1
归并趟数
logk(N)上取整
败者树
是完全二叉树吗？
是的
败者树的深度
log2(K)上取整
败者树的比较次数
之前是k-1，如今是log2(K)，正好和归并趟数抵消了
优点
内部归并的比较次数与k无关
归并路数越大越好吗？
不是，还要考虑缓冲区的大小和个数
所以一直增大归并路数（缓冲区个数变多），可能导致IO次数变多（缓冲区变小）
置换选择排序的本质
不断选，直到不能选出为止
最佳归并树
归并趟数
叶节点到根节点的路径长度
IO次数
2*树的WPL
归并策略
小的先归并
虚段个数
u=n-1%k-1
n-1-u个虚段
外部排序的总比较次数
比较趟数
元素个数
每次比较的个数
树的带权路径长度
叶节点的权值乘路径长度
一定要做到问啥答啥，有理有据，不要犯低级错误