考研数据结构考前辅导串讲.ppt

快速排序 起泡排序： 思想：逐次抽出最大、次大、次次大---。 具体做法：依次比较第i个关键字和第i+1个关键字，大者排后，一趟得到最大值。（i=1,2,3,4,---n-1) 起泡排序是稳定的排序方法 快速排序： 思想：一趟排序将序列分成两个部分，前者小于某个值，后者大于某个值。之后再次分别快速排序。 做法：选取任意记录为“枢轴”，如序列的第一个记录为“枢轴”。 快速排序是不稳定的排序方法 归并排序 思想：将两个或两个以上的有序表组合成一个新的有序表。 做法：先认为原始序列中每个关键字是一个序列，两两有序归并，逐步扩大子序列尺寸 二路归并排序是稳定的排序方法 * * 给出带有“头结点”的示意图 邻接多重表（2） 边结点的结构 其中，mark 是记录是否处理过的标记；vertex1和vertex2是依附于该边的两顶点位置。path1域是链接指针，指向下一条依附于顶点vertex1的边；path2也是链接指针，指向下一条依附于顶点vertex2的边。 顶点结点的结构 存储顶点信息的结点表以顺序表方式组织，每一个顶点结点有两个数据成员：其中，data 存放与该顶点相关的信息，Firstedge 是指示第一条依附于该顶点的边的指针。 mark vertex1 vertex2 path1 path2 data Firstedge 邻接多重表（3） 最小生成树 构成连通图网络的最小代价生成树 基本算法 普里姆(Prim)算法 克鲁斯卡尔 (Kruskal) 算法 普里姆(Prim)算法（1） 普里姆算法的基本思想： 从连通网络 N = { V, E }中的某一顶点 u0 出发，选择与它关联的具有最小权值的边(u0, v)，将其顶点加入到生成树的顶点集合U中。 以后每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(u, v),把它的顶点加入到集合U中。如此继续下去，直到网络中的所有顶点都加入到生成树顶点集合U中为止。 普里姆(Prim)算法（2） 克鲁斯卡尔 (Kruskal) 算法(1) 克鲁斯卡尔算法的基本思想： 设有一个有 n 个顶点的连通网络 N = { V, E },最初先构造一个只有 n 个顶点，没有边的非连通图 T = { V, ? }, 图中每个顶点自成一个连通分量。当在 E 中选到一条具有最小权值的边时,若该边的两个顶点落在不同的连通分量上，则将此边加入到 T 中；否则将此边舍去，重新选择一条权值最小的边。如此重复下去，直到所有顶点在同一个连通分量上为止。 克鲁斯卡尔 (Kruskal) 算法(2) 比较 Prim算法： 时间复杂度为O(n2)，与边数量无关 适合于求边稠密的网的最小生成树 Kruskal算法： 时间复杂度为O(eloge) 适合于求边稀疏的网的最小生成树 最短路径 (Shortest Path) 最短路径问题：如果从图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小。 问题解法 单源最短路径问题 — Dijkstra算法 所有顶点之间的最短路径 — Floyd算法 单源最短路径问题（1） 问题的提法： 给定一个带权有向图D与源点v，求从v到D中其它顶点的最短路径。限定各边上的权值大于或等于0。 为求得这些最短路径，Dijkstra提出按路径长度的递增次序，逐步产生最短路径的算法。首先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从顶点v到其它各顶点的最短路径全部求出为止。 单源最短路径问题（2） 该算法的基本思想是： 设置两个顶点的集合 S：存放已找到最短路径的顶点 T＝V－S：存放当前还未找到最短路径的顶点。 初始状态时，集合S中只包含源点v0，然后不断从集合T中选取到顶点v0路径长度最短的顶点u加入到集合S中，集合S每加入一个新的顶点u，都要修改顶点v0到集合T中剩余顶点的最短路径长度值，集合T中各顶点新的最短路径长度值为原来的最短路径长度值与顶点u的最短路径长度值加上u到该顶点的路径长度值中的较小值。此过程不断重复，直到集合T的顶点全部加入到S中为止。 单源最短路径问题（3） 第九章 查找 有序表的查找（1） 有序表即是表中数据元素按关键码升序或降序排列。 折半查找的思想为：在有序表中，取中间元素作为比较对象，若给定值与中间元素的