数据结构第十一章外部排序课件.ppt

1、 数据结构课程本章内容本章内容中国科大数据结构11-3 11.1 外存信息的存取中国科大数据结构11-4 11.1 外存信息的存取记录记录 1记录记录 3记录记录 2中国科大数据结构11-5 11.1 外存信息的存取中国科大数据结构11-6 11.1 外存信息的存取中国科大数据结构11-7 11.2 外部排序的方法中国科大数据结构11-8 11.2 外部排序的方法R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 R1 R2 R3 R4 R5 R1 R2 R3 R1 R2 有序文件有序文件中国科大数据结构11-9 11.2 外部排序的方法中国科大数据结构11-10 11.2 外部排序

2、的方法中国科大数据结构11-11 11.2 外部排序的方法R1 R2 R3 R4 R5R1 R2 R3 R4 R5 R6 R7 R8 R9 R10R6 R7 R8 R9 R10 R1 R2R1 R2 有序文件有序文件中国科大数据结构11-12 11.3 多路平衡归并的实现中国科大数据结构11-13 11.3 多路平衡归并的实现中国科大数据结构11-14 11.3 多路平衡归并的实现729597654挑出冠军挑出冠军需要进行需要进行 k-1 次次比较比较,此处需要此处需要比较比较 3 次次。9553205176543210559572995中国科大数据结构11-15 11.3 多路平衡归并的实现

3、7291697654挑出亚军挑出亚军需要进行需要进行 log2k 次比较次比较,此处需此处需要比较要比较 2次次。97732071765432107791672997中国科大数据结构11-16 11.3 多路平衡归并的实现中国科大数据结构11-17 11.3 多路平衡归并的实现中国科大数据结构11-18 11.3 多路平衡归并的实现中国科大数据结构11-19 11.3 多路平衡归并的实现920ls0ls1ls3ls2ls4b0b1b2b4b361525123748101515918202022402130612104中国科大数据结构11-20 11.3 多路平衡归并的实现中国科大数据结构11-

4、21 11.3 多路平衡归并的实现920ls0ls1ls3ls2ls4b0b1b2b4b315251237481015159182020224020141512103中国科大数据结构11-22 11.3 多路平衡归并的实现typedef int LoserTreek;/败者树是完全二叉树且不含叶子败者树是完全二叉树且不含叶子,可采用顺序存储结构可采用顺序存储结构typedef structKeyType key;ExNode,Externalk;/外结点外结点,只存放待归并记录的关键码只存放待归并记录的关键码中国科大数据结构11-23 11.3 多路平衡归并的实现void K_Merge(Lo

5、serTree*ls,External*b)/k-路归并处理程序利用败者树路归并处理程序利用败者树ls将编号从将编号从0到到k-1的的k个输入归并段中的记录归并到输出归并段个输入归并段中的记录归并到输出归并段b0/到到bk-1为败者树上的为败者树上的k个叶子结点个叶子结点,分别存放分别存放k个输入归并段中当前记录的关键码个输入归并段中当前记录的关键码for(i=0;i0)if(bs.keyblst.key)slst;/s指示新的胜者指示新的胜者 t=t/2;ls0=s;void CreateLoserTree(LoserTree*ls)/建立败者树建立败者树/已知已知b0到到bk-1为完全二叉

6、树为完全二叉树ls的叶子结点存有的叶子结点存有k个关个关/键码键码,沿从叶子到根的沿从叶子到根的k条路径将条路径将ls调整为败者树调整为败者树 bk.key=MINKEY;/设设MINKEY为关键码可能的最小值为关键码可能的最小值 for(i=0;i0;i-)Adjust(ls,i);/依次从依次从bk-1,bk-2,b0出发调整败者出发调整败者中国科大数据结构11-25 11.4 置换-选择排序中国科大数据结构11-26 11.4 置换-选择排序中国科大数据结构11-27 11.4 置换-选择排序中国科大数据结构11-28 11.4 置换-选择排序中国科大数据结构11-29 11.4 置换-

7、选择排序中国科大数据结构11-30 11.4 置换-选择排序最小值最小值 最大值最大值值递增值递增记录数记录数记录值分布按等概率记录值分布按等概率当前最小值当前最小值段分界值段分界值展开的环路均均 匀匀 下下 雪雪W积雪(内存容量)环路起、终点当前车位当前车位扫雪车在环形路上扫雪。将环路截断展开，扫雪车在环形路上扫雪。将环路截断展开，积雪截面为三角形如上图积雪截面为三角形如上图,其面积为其面积为W,则车走则车走一圈扫走的面积为一圈扫走的面积为2W.类比到置换类比到置换_选择排序选择排序如黄字所示。如黄字所示。中国科大数据结构11-31 11.5 最佳归并树93012511831738262432121中国科大数据结构11-32 11.5 最佳归并树23611309171824591211232中国科大数据结构11-33 11.5 最佳归并树2352491718124791620中国科大数据结构11-34 11.5 最佳归并树中国科大数据结构11-35 习题