第1页共21页数据结构实验四1.实验要求置换-选择排序的实现【问题描述】对文件中的记录的关键字采用外部排序的置换-选择算法实现。【实验要求】设计置换-选择排序的模拟程序。（1）记录存储在文件中。（2）采用多路归并算法实现。（3）采用置换-选择算法实现。第2页共21页2实验描述外部排序过程中，为了减少外存读写次数需要减小归并趟数（外部排序的过程中用到归并），外部排序1（其中k为归并路数，n为归并段的个数）。增加k和减小n都可以达到减小归并趟数的目的。置换-选择排序就是一种减小n的、在外部排序中创建初始归并段时用到的算法。它可以让初始归并段的长度增减，从而减小初始归并段的段数（因为总的记录数是一定的）。置换-选择排序是在树形选择排序的基础上得来的，它的特点是：在整个排序（得到初始归并段）的过程中，选择最小（或最大）关键值和输入、输出交叉或并行进行。它的主要思路是：用败者树从已经传递到内存中的记录中找到关键值最小（或最大）的记录，然后将此记录写入外存，再将外存中一个没有排序过的记录传递到内存（因为之前那个记录写入外存后已经给它空出内存），然后再用败者树的一次调整过程找到最小关键值记录（这个调整过程中需要注意：比已经写入本初始归并段的记录关键值小的记录不能参见筛选，它要等到本初始段结束，下一个初始段中才可以进行筛选），再将此最小关键值记录调出，再调入新的记录.......依此进行指导所有记录已经排序过。内存中的记录就是所用败者树的叶子节点。开发环境：VC6.0。3.置换-选择排序的实现//A是从外存读入n个元素后所存放的数组templatevoidreplacementSelection(Elem*A,intn,constchar*in,constchar*out){Elemmval;//存放最小堆的最小值Elemr;//存放从输入缓冲区中读入的元素FILE*iptF;//输入文件句柄FILE*optF;//输出文件句柄Bufferinput;//输入bufferBufferoutput;//输出buffer//初始化输入输出文件initFiles(inputFile,outputFile,in,out);//初始化堆的数据，读入n个数据initMinHeapArry(inputFile,n,A);//建立最小值堆MinHeapH(A,n,n);//初始化inputbuffer，读入部分数据initInputBuffer(input,inputFile);for(intlast=(n-1);last>=0;){mval=H.heapArray[0];//堆的最小值sendToOutputBuffer(input,output,iptF,optF,mval);input.read(r);//从输入缓冲区读入一个记录if(!less(r,mval))H.heapArray[0]=r;else{//否则用last位置记录代替根结点，把r放到lastH.heapArray[0]=H.heapArray[last];H.heapArray[last]=r;第3页共21页H.setSize(last);last--;}if(last!=0)H.SiftDown(0);}endUp(output,inputFile,outputFile);}4详细设计设计思想:1.初始化最小堆：目的是提高RAM中排序的效率(a)从缓冲区读M个记录放到数组RAM中(b)设置堆尾标志：LAST＝M－1(c)建立一个最小值堆2.重复以下步骤，直至堆空（结束条件）（即LAST<0）(a)把具有最小关键码值的记录(根结点)送到输出缓冲区(b)设R是输入缓冲区中的下一条记录1.如0果R的关键码不小于刚输出的关键码值，则把R放到根结点2.否则，使用数组中LAST位置的记录代替根结点，然后把R放到LAST位置。设置LAST＝LAST-1(c)重新排列堆，筛出根结点算法结束后，RAM中也填满了不能处理的数据，直接建成堆，留待下一顺串来处理大小是M的堆，最小顺串的长度为M的记录至少原来堆中的那些记录将成为顺串的一部分最好情况下，如输入已经被排序，有可能一次就把整个文件生成为一个顺串平均长度2M文件保存，读取函数#defineMAXKEYINT_MAX#defineRUNEND_SYMBOLINT_MAX#definew6#defineM10#defineN24第4页共21页typedefintKeyType;//定义关键字类型为整型typedefintInfoType;//定义其它数据项的类型//记录类型typedefstruct{KeyTypekey;InfoTypeotherinfo;}RedType;typedefintLoserTree[w];typedefstruct{RedTyperec;KeyTypekey；intrnum;}RedNode,WorkArea[w];主函数第5页共21页intmain(){RedTypea[N]={{51,1},{49,2},{39,3},{46,4},{38,5},{29,6},{14,7},{61,8},{15,9},{30,10},{1,11},{48,12},{52,13},{3,14},{63,15},{27,16},{4,17},{13,18},{89,19},{24,20},...
