数据结构
2021-08-24 11:52:27 38 举报AI智能生成
查找、排序等知识点总结
作者其他创作
大纲/内容
图
基本概念
简单路径
在路径序列中，顶点不重复出现的路径
简单回路
在路径序列中，除第一个和最后一个顶点外，其余不重复出现的回路
图的应用
带权无向图
最小生成树
Prim(普里姆)算法
每次选点
初始任选一点加入树T，之后选择一个与当前T中顶点集合距离最近的顶点
时间复杂度
适合求解边稠密的图
Kruskal(克鲁斯卡尔)算法
每次选边
选择权值最小且未被选取过的边，若加入该边后形成回路则舍弃该边
时间复杂度
适合求解点稠密边稀疏的图
带权有向图
最短路径
求某顶点到其他各顶点的最短路径
Dijkstra(迪杰斯特拉)算法
dist[]
记录所求点v0到其他各顶点的当前最短路径长度
path[]
记录所求点v0到其他各顶点的最短路径的前驱结点
步骤
初始化dist数组，若v0到其他各点有弧，则将dist对应位置赋与对应的权值，否则设为∞（无穷可自己约定一个数字代表无穷）
从dist中选择数字最小且未被选择过的点vj，则此时认为已找到v0到vj的最短路径
已vj为中转点计算v0到其余各点距离，若小于dist中的值，则更新
重复2，3操作
与Prim普里姆算法类似，时间复杂度也为
边上带有负权值时不适用
求所有顶点间的最短路径
Floyd(弗洛伊德)算法
递推产生n阶方阵序列，存储顶点之间的最短路径长度
步骤
初始化，将该图的邻接矩阵赋值给方阵序列
依次将各顶点加入中间顶点，并更新方阵序列的值
时间复杂度
允许图中有带负权值的边，但不允许有包含带负权值的边组成的回路
Dijkstra和Floyd同样能求解带权无向图的最短路径，因为带权无向图可视为权值相同往返二重边的有向图
有向无环图(DAG图)
有向无环图描述表达式
描述含有公共子式的表达式的有效工具
共享相同子式，节省存储空间
所得有向无环图操作数不会重复
得到对应有向无环图的步骤
AOV网
拓扑排序
不断删除入度为0的顶点
拓扑排序算法可用于判断一个图是否有环
DFS实现
逆拓扑排序
不断删除出度为0的顶点
DFS实现
时间复杂度
邻接矩阵存储时为
邻接表存储时为
小结
若图有环则不存在拓扑排序、逆拓扑排序
若图的邻接矩阵是三角矩阵，则存在拓扑序列，反之不一定成成立。
若图的邻接矩阵为三角矩阵，且对角线以上的元素均为1，以下的均为0，则拓扑序列唯一。
每个顶点出入度最多唯一，则该图拓扑序列唯一，反之不一定成立
拓扑序列唯一，不能唯一确定该图
AOE网
开始顶点（源点）
表示工程的开始
结束顶点（汇点）
表示工程的结束
关键路径
求解步骤
求事件最早发生时间ve(k)
从源点出发，令ve(源点)=0，按拓扑排序求其余顶点ve()
求事件最晚发生时间vl(k)
从汇点出发，令vl(汇点)=ve(汇点)，按拓扑排序求其余顶点ve()
求活动最早开始时间e(i)
等于活动弧的起点事件的最早发生时间ve(k)
求活动最晚开始时间l(i)
等于活动弧的终点事件的最迟发生事件vl(k)减去该活动的权值
求活动的差额d()，d()=0的活动即为关键活动
用l(i)-e(i)
小结
工程完成的最短时间是关键路径的长度
可通过加快关键活动来缩短工期，但不能任意缩短，因为缩短到一定程度，关键活动可能变成非关键活动
若有几条关键路径，则加快包括在所有关键路径上的关键活动才能缩短工期
或者说只有所有关键路径上的活动时间同时减少时，才能缩短工期
或者说只有所有关键路径上的活动时间同时减少时，才能缩短工期
查找
基本概念
关键字
数据元素中唯一标识该元素的某个数据项的值
查找长度
在查找运算中，对比关键字的次数
查找算法评价指标
平均查找长度
静态查找表
对查找表无需进行动态地修改，则称为静态查找表，否则称为动态查找表
顺序查找
通常用于线性表
由于失败结点是虚构的空结点，故到达失败结点时所查找的长度等于它上面一个圆形结点所在的层数
若有n个结点，则有n+1个失败结点(空链域)
折半查找
仅适用于有序的顺序表
基本思想
指针low指向最小元素，high指向最大元素，mid指向
若查找元素大于mid，令low=mid+1
若查找元素小于mid，令high=mid-1
若查找元素小于mid，令high=mid-1
重复(1)(2)，直到查找成功或high小于low
判定树
若mid为向下取整，则对应的折半查找判定树，右子树结点数-左子树结点数=0或1
一定是平衡的二叉排序树
只有最下面一层会出现不满的情况
若有n个关键字，则失败结点有n+1个
树高
(不包括失败结点)
树的高度也是折半查找时进行关键字的比较最多的次数
(不包括失败结点)
树的高度也是折半查找时进行关键字的比较最多的次数
时间复杂度
分块查找
块内无序，块间有序
索引表
每个元素含有每块的最大（或最小）的数据
基本思想
在索引表中确定待查记录所在的块，可顺序查找或折半查找
使用折半查找时，若索引表中没有与待查记录相等的关键字，则当low大于high后，在low所指分块中进行查找
在块内顺序查找
平均查找长度
若顺序查找索引表，并将长度为n的查找表均匀分为b块，每块有s个记录
则
则
若，则取到最小值
拓展：若查找表是动态查找表，则可用链式存储来建立索引表以及查找表
B树和B+树
B树
基本概念
结点的孩子个数最大值称为B树的阶，记作m
终端结点
叶结点
核心特性
对任一结点，其所有子树高度都相同（绝对平衡）
结点中关键字的值是有序的（升序或降序）
关键字总会大于它左子树上的值，小于它右子树上的值
含有n个关键字的m叉B树的高度满足，
最小高度
每个结点关键字数量最大，子树数量也最大，则
每个结点关键字数量最大，子树数量也最大，则
最大高度
每个结点关键字数量最小，则每层结点数量也最少
则第一层有1个结点，第二层有2个结点，第3层有个，第h层有个
则叶结点数量大于等于高度+1层的最少数量即
每个结点关键字数量最小，则每层结点数量也最少
则第一层有1个结点，第二层有2个结点，第3层有个，第h层有个
则叶结点数量大于等于高度+1层的最少数量即
基本操作
查找
插入
插入后的结点关键字个数大于m-1时，需进行结点分裂
将中间位置的关键字插入原结点的父结点中，右部分放新结点中
若此时父结点也超出了上限，则继续分裂
将中间位置的关键字插入原结点的父结点中，右部分放新结点中
若此时父结点也超出了上限，则继续分裂
删除
被删关键字k在非终端结点
用关键字k的前驱或后继来替代k的位置
被删关键字k在终端结点
若删除后，结点中关键字个数仍满足B树特性，则直接删除
若删除后不满足B树特性
兄弟够借，结点的双亲结点关键字替代k的位置，兄弟的关键字顶替双亲的位置
兄弟不够借，则将结点与双亲结点中的关键字和兄弟结点结合起来
若双亲结点的关键字又不满足特性，则继续合并
若双亲结点的关键字又不满足特性，则继续合并
B+树
与B树主要差异
每个非叶结点中，关键字数等于子树数，即满足关键字数
所有叶结点包含了全部关键字及指向相应记录的指针，所有非叶结点仅起索引作用
非叶结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针
非叶结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针
叶结点中将关键字按大小顺序排序，并将相邻叶结点按大小顺序相互链接起来
B+树有两个头指针，一个指向根结点，一个指向关键字最小的叶结点。
因此可以对B+树进行从最小关键字开始的顺序查找和从根结点开始的多路查找
因此可以对B+树进行从最小关键字开始的顺序查找和从根结点开始的多路查找
无论查找成功与否，都最走到最后一层
散列表
概念
散列函数
冲突（碰撞）
同义词
装填因子
常见散列函数
除数留余法
直接定址法
数字分析法
设关键字是r进制数，取数码分布较为均匀的若干位作为散列地址
平方取中法
取关键字平方值的中间几位作为散列地址
冲突的处理
拉链法（链地址法）
将同义词串成一个链表
插入关键字时，保持链表有序，可以略微提高效率
开放定址法
线性探测法
会造成“聚集”（或堆积）现象
即大量元素在相邻的散列地址上，降低查找效率
即大量元素在相邻的散列地址上，降低查找效率
平方探测法
散列表长度必须是一个可以表示为4k+3的素数，才能探测到散列表上的所有单元
伪随机序列法
di为一个伪随机序列
使用开放定址法时，不能随便物理删除表中的已有元素，而是要做一个删除标记，进行逻辑删除
因为用开放定址进行散列查找时，会按照所选方法进行查找，一旦找到位置上无记录，则认为查找失败
因为用开放定址进行散列查找时，会按照所选方法进行查找，一旦找到位置上无记录，则认为查找失败
再散列法
准备多个散列函数，一个发生冲突了就用下一个
查找效率
取决于散列函数，处理冲突的方法，装填因子
平均查找长度ASL的计算
使用拉链法时，与空链域的比较不算入对比次数
使用开放定址法时，与空位置的比较需要算入对比次数
使用开放定址法时，与空位置的比较需要算入对比次数
排序
基本概念
稳定性
对任意n个关键字进行基于比较的排序，至少要进行次关键字之间的两两比较
插入排序
直接插入排序
将元素与前面已排好序的子序列中的元素进行比较，然后移动位置
即：第n次排序后，前n项子序列一定是局部有序的
即：第n次排序后，前n项子序列一定是局部有序的
时间复杂度
稳定
适用于顺序存储与链式存储的线性表
折半插入排序
通过折半查找确定元素插入子序列的位置，然后统一移动
注：直到low>high才停止折半查找
元素最终插入位置为low所指位置(即high+1)
注：直到low>high才停止折半查找
元素最终插入位置为low所指位置(即high+1)
时间复杂度
稳定
希尔排序
通过设置步长(增量)d，将待排序表划分为多个子表
每轮在子表内进行直接插入排序，然后取下一个更小的d
常用的方法是
每轮在子表内进行直接插入排序，然后取下一个更小的d
常用的方法是
时间复杂度未知，但优于直接插入排序，最坏情况是
不稳定
交换排序
冒泡排序
从后往前(或从前往后)两两比较相邻元素的值，若为逆序则交换位置
经过第n躺冒泡排序后，前n项(或后n项)一定是全局有序的
经过第n躺冒泡排序后，前n项(或后n项)一定是全局有序的
时间复杂度
稳定
适用于顺序存储、链式存储
交换一次位置需要移动元素3次
快速排序
递归算法，初始定义low、high指针
以low指针所指元素作为枢轴(基准)元素
一次划分后，将枢轴元素移动到其最终位置上
并且左边元素均小于它，右边元素均大于它
然后对左右子序列继续进行快速排序
以low指针所指元素作为枢轴(基准)元素
一次划分后，将枢轴元素移动到其最终位置上
并且左边元素均小于它，右边元素均大于它
然后对左右子序列继续进行快速排序
时间效率与递归深度有关，即划分是否对称
划分越对称，深度越浅
时间复杂度最坏
划分越对称，深度越浅
时间复杂度最坏
不稳定
每次划分都会将枢轴(基准)元素放到其最终位置上
所有内部排序算法中平均性能最优
选择排序
简单选择排序
每一趟选择最小的的元素加入有序子列中
即每一趟可以确定一个元素的最终位置
即每一趟可以确定一个元素的最终位置
时间复杂度
不稳定
适用于顺序存储与链式存储
元素间比较次数与序列初始状态无关
堆排序
时间复杂度
其中初始建堆O(n)
之后堆排序调整堆
其中初始建堆O(n)
之后堆排序调整堆
不稳定
对大根堆进行堆排序得到递增序列
对小根堆进行堆排序得到递减序列
对小根堆进行堆排序得到递减序列
基本概念
堆
插入
插入元素放在堆的末端，然后进行上升调整操作
每上升一层，会进行1次关键字对比（与父结点进行对比）
每上升一层，会进行1次关键字对比（与父结点进行对比）
删除
用堆底元素替代删除的位置，然后进行调整
元素每下坠一层，关键字对比次数最多为2次
（第1次左右孩子比较出最大的，第2次最大的与父结点进行比较）
（若只有一个孩子，则只需比较1次）
元素每下坠一层，关键字对比次数最多为2次
（第1次左右孩子比较出最大的，第2次最大的与父结点进行比较）
（若只有一个孩子，则只需比较1次）
大根堆：根结点左右孩子
小根堆：根结点左右孩子
建堆
从最后一个非终端结点开始建堆
算法思想
以大根堆为例
以大根堆为例
用含n个元素的序列建立大根堆，关键字的比较总次数不超过4n
输出堆顶元素，并由堆的最后一个元素代替其位置
（即此时输出的堆顶结点确定了最终位置）
（即此时输出的堆顶结点确定了最终位置）
重新建立大根堆
步骤2、3重复n-1次
归并排序和基数排序
归并排序
k路归并
构造辅助空间，将k个有序表和为1
每选出一个最小关键字需要对比k-1次
归并趟数
算法思想
若low<high，将序列从中间mid=(low+high)/2分开
对左右子序列递归地进行归并排序
将左右有序子序列进行2路归并为1个
时间复杂度
稳定
本章算法中，占辅助空间最多
基数排序
算法思想
将数据元素的关键字拆分为d组(位)
若关键字位可能取得r个值，则建立r个队列
按照关键字位的权重递增（如个十百）的次序，做d躺分配和收集
分配
顺序扫描各个元素，根据当前处理的关键字位，将元素插入相应队列
收集
将各个队列中的结点依次出队并链接
若想获得递减序列，则应从当前处理的关键字位，大的开始收集
递增则反之
若想获得递减序列，则应从当前处理的关键字位，大的开始收集
递增则反之
时间复杂度
稳定
适用于
数据关键字方便拆分位d组，且d较小
每组关键字取值范围不大，即r较小
数据元素个数n较大
不基于比较和移动进行排序
外部排序
外部排序的方法
根据内存缓冲区大小，生成初始归并段
败者树
置换-选择排序
最佳归并树
若(初始归并段数-1)%(归并路数-1)=u不为0
则需要添加长度为0的虚段
添加个数为k-1-u个
则需要添加长度为0的虚段
添加个数为k-1-u个
0 条评论
下一页
