数据结构实验四1.实验要求置换-选择排序的实现【问题描述】对文件中的记录的关键字采用外部排序的置换-选择算法实现。

【实验要求】设计置换-选择排序的模拟程序。

（1）记录存储在文件中。

（2）采用多路归并算法实现。

（3）采用置换-选择算法实现。

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; //输出文件句柄Buffer<Elem> input; //输入bufferBuffer<Elem> output; // 输出buffer//初始化输入输出文件initFiles(inputFile, outputFile, in, out);//初始化堆的数据，读入n个数据initMinHeapArry(inputFile, n, A);//建立最小值堆MinHeap<Elem> 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放到lastH.heapArray[0] = H.heapArray[last];H.heapArray[last] = 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. 重复以下步骤，直至堆空（结束条件）（即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#define RUNEND_SYMBOL INT_MAX#define w 6#define M 10#define N 24typedef int KeyType; // 定义关键字类型为整型typedef int InfoType; // 定义其它数据项的类型// 记录类型typedef struct{KeyType key;InfoType otherinfo;}RedType;typedef int LoserTree[w];typedef struct{RedType rec;KeyType key；int rnum;}RedNode, WorkArea[w];主函数int main(){RedType a[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 s[3],fname[4];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("\n\n");rewind(fi);fo = fopen("out","wb");// 用置换－选择排序求初始归并段Replace_Selection(ls, wa, fi, fo);fclose(fo);fclose(fi);fi = fopen("out","rb");printf("初始归并段文件的记录为:\n");i = 1;do{k = fread(&b, sizeof(RedType), 1, fi);if(k == 1){print(b);if(b.key == j)printf("\n\n");}}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");do{i = fread(&b,sizeof(RedType),1,fi);if(i == 1){fwrite(&b,sizeof(RedType),1,fo);if(b.key == j) // 1个归并段结束{k++;fclose(fo);break;}}}while(i==1);};fclose(fi);printf("共产生%d个初始归并段文件\n", k);system("pause");return 0;}5 程序编码#include <stdio.h>#include <malloc.h>#include <limits.h>#include <stdlib.h>#include <string.h>#define MAXKEY INT_MAX#define RUNEND_SYMBOL INT_MAX #define w 6#define M 10#define N 24typedef int KeyType;typedef int InfoType;typedef struct{KeyType key;InfoType otherinfo;}RedType;typedef int LoserTree[w];typedef struct{RedType rec;KeyType key;int rnum;}RedNode, WorkArea[w];void Select_MiniMax(LoserTree ls,WorkArea wa,int q){int p, s, t;t = (w+q)/2;p = ls[t];for(; t > 0;){if(wa[p].rnum < wa[q].rnum || wa[p].rnum == wa[q].rnum && wa[p].key < wa[q].key){s=q;q=ls[t];ls[t]=s;}t = t/2;p = ls[t];}ls[0] = q;}void Construct_Loser(LoserTree ls, WorkArea wa, FILE *fi){int i;for(i = 0; i < w; ++i)wa[i].rnum = wa[i].key = ls[i] = 0;for(i = w - 1; i >= 0; --i){fread(&wa[i].rec, sizeof(RedType), 1, fi);wa[i].key = wa[i].rec.key; // 提取关键字wa[i].rnum = 1; // 其段号为＂1＂Select_MiniMax(ls,wa,i); // 调整败者树}}void get_run(LoserTree ls,WorkArea wa,int rc,int *rmax,FILE *fi,FILE *fo){int q;KeyType minimax;while(wa[ls[0]].rnum == rc){q = ls[0];minimax = wa[q].key;fwrite(&wa[q].rec, sizeof(RedType), 1, fo);fread(&wa[q].rec,sizeof(RedType),1,fi);if(feof(fi)){wa[q].rnum = *rmax+1;wa[q].key = MAXKEY;}else{wa[q].key = wa[q].rec.key;if(wa[q].key < minimax){*rmax = rc+1;wa[q].rnum = *rmax;}elsewa[q].rnum = rc;}Select_MiniMax(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 = wa[ls[0]].rnum;}}void print(RedType t){printf("(%d,%d) ",t.key,t.otherinfo);}int main(){RedType a[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 s[3],fname[4]; // 文件名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("\n\n");。