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