数据结构与算法 课件 第6、7章 图结构、 内部排序.ppt

考虑图中从顶点vi到顶点vj的一条最短路径，中间经过或不经过一些顶点如果最短路径不经过任何中间顶点，则这条最短路径就是从vi到vj的边反之，假设中间经过顶点k，则vi到vj的最短路径分为从vi到vk及从vk到vj的两段，并且这两段分别都是相应顶点间的最短路径，否则可以用更短的路径来分别替代它们，从而组成从vi到vj之间更短的路径显然，从vi到vj的最短路径不包含回路，否则可以去掉回路，找到一条更短的路径设图G中顶点序列为v1,v2,…,vn，带权邻接矩阵为A，A[i][j]中保存从vi到vj边的权值，仍设权值为非负值现在限制最短路径所经过中间顶点的编号初始时，规定最短路径中间不允许经过任何顶点，则从vi到vj的路径就是从vi到vj的边，其路径长度即为A[i][j]现在允许最短路径中间经过编号不大于v1的顶点，如果从vi到vj有最短路径的话，则最短路径只有以下两种可能①从vi到vj的原有最短路径，即从vi到vj的边，A[i][j]为路径长度②从vi到v1的路径加上从v1到vj的路径，A[i][v1]+A[v1][j]为路径长度判断上述两值，取较小者作为新的A[i][j]值，此时A中保存的是允许经过v1后顶点之间最短路径的长度为了区别，标记为A(1)，初始的带权邻接矩阵可以表示为A(0)Floyd算法定义A(k-1)[i][j]表示从顶点vi到顶点vj的中间顶点序号不大于vk-1的最短路径之长度，A(0)[i][j]即是cost[i][j]从A(0)[i][j]出发，逐次计算从顶点vi到顶点vj的中间顶点序号不大于k（1≤k≤n）的最短路径之长度，即在A(k-1)的基础上计算A(k)，递推地产生一个矩阵序列：A(0),A(1),…,A(k),…,A(n)，A(n)[i][j]表示的就是从顶点vi到vj的最短路径的长度设目前已求出A(k-1)[i][j]，求A(k)[i][j]时分两种情况：①如果从顶点vi到vj的最短路径不经过顶点vk，则由A(k)[i][j]的定义可知，从vi到vj的中间顶点序号不大于k的最短路径长度就是A(k-1)[i][j]，即A(k)[i][j]=A(k-1)[i][j]。②如果从顶点vi到vj的最短路径经过顶点vk，则由vi到vk和由vk到vj两条路径组成从vi到vj的路径。由于A(k-1)[i][k]和A(k-1)[k][j]分别代表从vi到vk和从vk到vj的中间顶点序号不大于vk-1的最短路径的长度，则A(k)[i][j]=A(k-1)[i][k]+A(k-1)[k][j]。由此得到A(k)[i][j]的迭代计算公式：最后得到的A(n)[i][j]就是从顶点vi到vj的最短路径的长度Floyd算法中计算cost的循环例6-19全国高等教育自学考试指定教材

计算机及应用专业（本科段）数据结构与算法第七章内部排序学习目标理解排序的基本概念。掌握各种排序方法及其特点。掌握各种排序算法的实现过程，能够对其进行复杂度分析。能够对各种排序方法进行比较，理解各排序方法的使用条件。本章主要内容排序的基本概念12交换排序3插入排序选择排序4归并排序56排序算法的比较7分配排序第一节排序的基本概念定义7.1给定一组记录r1,r2,…,rn，其关键字分别为 k1,k2,…,kn将这些记录排成顺序为rs1,rs2,…,rsn的一个序列S，满足条件 ks1≤ks2≤…≤ksn或是ks1≥ks2≥…≥ksn此过程称为排序若关键字值依从小到大的顺序排列，则称为升序若依从大到小的顺序排列，则称为降序内部排序对不同类型的关键字而言，“大”、“小”的含义可能不一样对于数值型的关键字，可按一般意义的“大”、“小”来理解对于字符型的关键字，往往按其对应的ASCII码来定义大小次序把能唯一标识记录的关键字称为主关键字，其余的称为次关键字主关键字值不允许有重复计算机中存放待排序数据的存储介质可以分为内存和外存当待排序的数据量不大，全部数据都可以放入内存，排序操作也完全在内存中进行时，相应的排序称为内部排序或内排序内排序因为不涉及内外存数据交换的问题所以一般来讲，排序速度较快当待排序的数据量大，全部数据不能同时放在内存中，需要借助外存完成排序过程时，相应的排序称为外部排序或外排序外排序中，排序的具体操作在内存完成，且仅能对部分数据进行排序过程中需要多次分批在内存、外存之间进行数据交换，从而完成全部数据的排序任务减少数据内外存交换次数定义7.2具有相等关键字的两个记录R1和R2，在排序之前，R1位于R2之前，在排序之后，R1仍然位于R2之前，即排序并没有