数据结构实验四

1、数据结构实验四1. 实验要求置换-选择排序的实现【问题描述】对文件中的记录的关键字采用外部排序的置换-选择算法实现。【实验要求】设计置换-选择排序的模拟程序。（1）记录存储在文件中。（2）采用多路归并算法实现。（3）采用置换-选择算法实现。2实验描述外部排序过程中，为了减少外存读写次数需要减小归并趟数（外部排序的过程中用到归并），外部排序1（其中k为归并路数，n为归并段的个数）。增加k和减小n都可以达到减小归并趟数的目的。置换-选择排序就是一种减小n的、在外部排序中创建初始归并段时用到的算法。它可以让初始归并段的长度增减，从而减小初始归并段的段数（因为总的记录数是一定的）。 置换-选择排序是在

2、树形选择排序的基础上得来的，它的特点是：在整个排序（得到初始归并段）的过程中，选择最小（或最大）关键值和输入、输出交叉或并行进行。它的主要思路是：用败者树从已经传递到内存中的记录中找到关键值最小（或最大）的记录，然后将此记录写入外存，再将外存中一个没有排序过的记录传递到内存（因为之前那个记录写入外存后已经给它空出内存），然后再用败者树的一次调整过程找到最小关键值记录（这个调整过程中需要注意：比已经写入本初始归并段的记录关键值小的记录不能参见筛选，它要等到本初始段结束，下一个初始段中才可以进行筛选），再将此最小关键值记录调出，再调入新的记录.依此进行指导所有记录已经排序过。内存中的记录就是所用败

3、者树的叶子节点。开发环境：VC6.0。3.置换-选择排序的实现 /A是从外存读入n个元素后所存放的数组template void replacementSelection(Elem * A, int n, const char * in, const char * out)Elem mval; /存放最小堆的最小值Elem r; /存放从输入缓冲区中读入的元素FILE * iptF; /输入文件句柄FILE * optF; /输出文件句柄Buffer input; /输入 bufferBuffer output; / 输出buffer/初始化输入输出文件initFiles(inputFile,

4、 outputFile, in, out); /初始化堆的数据，读入n个数据initMinHeapArry(inputFile, n, A); /建立最小值堆MinHeap H(A, n, n); /初始化inputbuffer，读入部分数据initInputBuffer(input, inputFile); for(int last = (n-1); last = 0;)mval = H.heapArray0; /堆的最小值sendToOutputBuffer(input,output,iptF,optF, mval);input.read(r); /从输入缓冲区读入一个记录if(!less

5、(r, mval) H.heapArray0 = r;else /否则用last位置记录代替根结点，把r放到lastH.heapArray0 = H.heapArraylast;H.heapArraylast = r;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.重复以下步骤，直至堆空（结束条件）（即

6、LAST 0）(a) 把具有最小关键码值的记录(根结点)送到输出缓冲区(b)设R是输入缓冲区中的下一条记录1. 如0果R的关键码不小于刚输出的关键码值，则把R 放到根结点2. 否则，使用数组中LAST位置的记录代替根结点， 然后把R放到LAST位置。设置LAST LAST-1(c)重新排列堆，筛出根结点算法结束后，RAM中也填满了不能处理的数据，直接建成堆，留待下一顺串来处理大小是M的堆，最小顺串的长度为M的记录至少原来堆中的那些记录将成为顺串的一部分最好情况下，如输入已经被排序，有可能一次就把整个文件生成为一个顺串平均长度2M文件保存，读取函数 #define MAXKEY INT_MAX#

7、define RUNEND_SYMBOL INT_MAX#define w 6#define M 10#define N 24typedef int KeyType;/ 定义关键字类型为整型typedef int InfoType;/ 定义其它数据项的类型/ 记录类型typedef structKeyType key;InfoType otherinfo;RedType;typedef int LoserTreew; typedef structRedType rec;KeyType key；int rnum;RedNode, WorkAreaw; 主函数int main()RedType a

8、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,46,21,58,22,33,23,76,24;RedType b;/ 中介FILE *fi,/输入文件*fo;/输出文件LoserTree ls;/ 败者树WorkArea wa;/ 内存工作区int i, k, j = RUNEND_SYMBOL;char s3, fname4;fo = fopen(ori,wb);fwrite(a, sizeof(

9、RedType), N, fo);fclose(fo);fi = fopen(ori,rb);printf(大文件的记录为:n);for(i = 1; i = N; i+)fread(&b,sizeof(RedType),1,fi);print(b);if(i % M = 0)printf(n);printf(nn);rewind(fi);fo = fopen(out,wb);/ 用置换选择排序求初始归并段Replace_Selection(ls, wa, fi, fo);fclose(fo);fclose(fi);fi = fopen(out,rb);printf(初始归并段文件的记录为:n

10、);i = 1;dok = fread(&b, sizeof(RedType), 1, fi);if(k = 1)print(b);if(b.key = j)printf(nn);while(k = 1);printf(n);rewind(fi);k = 0;while(!feof(fi)itoa(k,s,10);strcpy(fname,f);strcat(fname,s);fo = fopen(fname,wb);doi = fread(&b,sizeof(RedType),1,fi);if(i = 1)fwrite(&b,sizeof(RedType),1,fo);if(b.key =

11、j) / 1个归并段结束k+;fclose(fo);break;while(i=1);fclose(fi);printf(共产生%d个初始归并段文件n, k);system(pause);return 0; 5 程序编码#include #include #include #include #include #define MAXKEY INT_MAX#define RUNEND_SYMBOL INT_MAX#define w 6#define M 10#define N 24typedef int KeyType;typedef int InfoType;typedef structKeyT

12、ype key;InfoType otherinfo; RedType;typedef int LoserTreew; typedef structRedType rec;KeyType key;int rnum;RedNode, WorkAreaw;void Select_MiniMax(LoserTree ls,WorkArea wa,int q)int p, s, t;t = (w+q)/2;p = lst;for(; t 0;)if(wap.rnum waq.rnum | wap.rnum = waq.rnum& wap.key waq.key)s=q;q=lst;lst=s;t =

13、t/2;p = lst;ls0 = q;void Construct_Loser(LoserTree ls, WorkArea wa, FILE *fi)int i;for(i = 0; i = 0; -i)fread(&wai.rec, sizeof(RedType), 1, fi);wai.key = wai.rec.key;/ 提取关键字wai.rnum = 1;/ 其段号为1Select_MiniMax(ls,wa,i);/ 调整败者树void get_run(LoserTree ls,WorkArea wa,int rc,int *rmax,FILE *fi,FILE *fo)int

14、 q;KeyType minimax;while(wals0.rnum = rc)q = ls0;minimax = waq.key;fwrite(&waq.rec, sizeof(RedType), 1, fo);fread(&waq.rec,sizeof(RedType),1,fi);if(feof(fi)waq.rnum = *rmax+1;waq.key = MAXKEY;elsewaq.key = waq.rec.key;if(waq.key minimax)*rmax = rc+1;waq.rnum = *rmax;elsewaq.rnum = rc;Select_MiniMax(

15、ls, wa, q);void Replace_Selection(LoserTree ls, WorkArea wa, FILE *fi, FILE *fo)int rc, rmax;RedType j;j.key = RUNEND_SYMBOL;/ 初建败者树Construct_Loser(ls, wa, fi);rc = rmax =1;while(rc = rmax)get_run(ls, wa, rc, &rmax, fi, fo);j.otherinfo=rc;fwrite(&j,sizeof(RedType),1,fo);rc = wals0.rnum; void print(R

16、edType t)printf(%d,%d) ,t.key,t.otherinfo);int main()RedType aN=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,46,21,58,22,33,23,76,24;RedType b;/ 中介FILE *fi,/输入文件*fo;/输出文件LoserTree ls;/ 败者树WorkArea wa;/ 内存工作区int i, k, j = RUNE

17、ND_SYMBOL;char s3, fname4;/ 文件名fo = fopen(ori,wb);fwrite(a, sizeof(RedType), N, fo);fclose(fo);fi = fopen(ori,rb);printf(大文件的记录为:n);for(i = 1; i = N; i+)fread(&b,sizeof(RedType),1,fi);print(b);if(i % M = 0)printf(n);printf(nn);。rewind(fi);fo = fopen(out,wb);Replace_Selection(ls, wa, fi, fo);fclose(f

18、o);fclose(fi);fi = fopen(out,rb);printf(初始归并段文件的记录为:n);i = 1;dok = fread(&b, sizeof(RedType), 1, fi);if(k = 1)print(b);if(b.key = j)printf(nn);while(k = 1);printf(n);rewind(fi);k = 0;while(!feof(fi)itoa(k,s,10);strcpy(fname,f);strcat(fname,s);fo = fopen(fname,wb);doi = fread(&b,sizeof(RedType),1,fi);if(i = 1)fwrite(&b,sizeof(RedType),1,f