数据结构实验四概览.docx

第 第 PAGE 10 页 共 21 页 数据结构实验四 实验要求 置换-选择排序的实现 【问题描述】 对文件中的记录的关键字采用外部排序的置换-选择算法实现。 【实验要求】 设计置换-选择排序的模拟程序。 记录存储在文件中。 采用多路归并算法实现。 采用置换-选择算法实现。 2 实验描述 外部排序过程中，为了减少外存读写次数需要减小归并趟数（外部排序的过程中用到归并），外部排序 1（其中k 为归并路数，n 为归并段的个数）。增加 k 和减小n 都可以达到减小归并趟数的目的。置换-选择排序就是一种减小 n 的、在外部排序中创建初始归并段时用到的算法。它可以让初始归并段的长度增减，从而减小初始归并段的段数（因为总的记录数是一定的）。 置换-选择排序是在树形选择排序的基础上得来的，它的特点是：在整个排序（得到初 始归并段）的过程中，选择最小（或最大）关键值和输入、输出交叉或并行进行。它的主要思路是：用败者树从已经传递到内存中的记录中找到关键值最小（或最大）的记录，然后将 此记录写入外存，再将外存中一个没有排序过的记录传递到内存（因为之前那个记录写入外存后已经给它空出内存），然后再用败者树的一次调整过程找到最小关键值记录（这个调整过程中需要注意：比已经写入本初始归并段的记录关键值小的记录不能参见筛选，它要等到本初始段结束，下一个初始段中才可以进行筛选），再将此最小关键值记录调出，再调入新的记录 依此进行指导所有记录已经排序过。内存中的记录就是所用败者树的叶子节点。 开发环境：VC6.0。 3.置换-选择排序的实现 //A 是从外存读入 n 个元素后所存放的数组template class Elem void replacementSelection(Elem * A, int n, const char * in, const char * out){ Elem mval; //存放最小堆的最小值 Elem r; //存放从输入缓冲区中读入的元素FILE * iptF; //输入文件句柄 FILE * optF; //输出文件句柄 BufferElem input; // 输 入 buffer BufferElem output; // 输出 buffer //初始化输入输出文件initFiles(inputFile, outputFile, in, out); //初始化堆的数据，读入 n 个数据initMinHeapArry(inputFile, n, A); //建立最小值堆MinHeapElem H(A, n, n); //初始化 inputbuffer，读入部分数据initInputBuffer(input, inputFile); for(int last = (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 放到 last H.heapArray[0] = H.heapArray[last]; H.heapArray[last] = r; H.setSize(last); last--; } if (last!=0) H.SiftDown(0); } endUp(output,inputFile,outputFile); } 详细设计 设计思想: 初始化最小堆：目的是提高RAM 中排序的效率 从缓冲区读M 个记录放到数组RAM 中 设置堆尾标志：LAST ＝ M － 1 建立一个最小值堆 重复以下步骤，直至堆空（结束条件）（即 LAST 0） 把具有最小关键码值的记录(根结点)送到输出缓冲区 设 R 是输入缓冲区中的下一条记录 如0果R 的关键码不小于刚输出的关键码值，则把R 放到根结点 否则，使用数组中LAST 位置的记录代替根结点， 然后把R 放到 LAST 位置。设置LAST ＝ LAST-1 (c)重新排列堆，筛出根结点 算法结束后，RAM 中也填满了不能处理的数据，直接建成堆，留待下一顺串来处理大小是M 的堆，最小顺串的长度为M 的记录 至少原来堆中的那些记录将成为顺串的一部分 最好情况下，如输入已经被排序，有可能一次就把整个文件生成为一个顺串平均长度2M 文件保存，读取函数 #define MAXKEY INT_MAX #define RUNEND_SYMBOL INT_MAX #define w 6 #define M 10 #define N 24 t