数据结构实践——置换-选择算法模拟

发布时间:2017-09-10 10:51:43
数据结构实践——置换-选择算法模拟

【项目 】置换-选择算法模拟
  编写程序,模拟置换-选择算法生成初始归并段的过程。
  设大文件中的记录共有18个: 15 4 97 64 17 32 108 44 76 9 39 82 56 31 80 73 255 68
  内存工作区可以容纳5个记录,输出产生的归并段文件。
  在模拟中,输入文件数据和输出的归并段数据均直接置在内存中即可。

参考解答

#include #include #include #include #define MaxSize 50 //每个文件最多记录数 #define MAXKEY 32767 //最大关键字值∞ #define W 5 //内存工作区可容纳的记录个数 typedef int LoserTree[W]; //败者树是完全二叉树且不含叶子,可采用顺序存储结构 typedef int InfoType; //定义其他数据项的类型 typedef int KeyType; //定义关键字类型为整型 typedef struct //记录类型 { KeyType key; //关键字项 InfoType otherinfo; //其他数据项,具体类型在主程中定义 } RecType; typedef struct { RecType rec; //存放记录 int rnum; //所属归并段的段号 } WorkAreaType; typedef WorkAreaType WorkArea[W]; //内存工作区,容量为W typedef struct { RecType recs[MaxSize]; //存放文件中的数据项 int length; //存放文件中实际记录个数 int currec; //存放当前位置 } FileType; //文件类型 FileType Fi; //定义输入文件,为全局变量 FileType Fo; //定义输出文件,为全局变量 void initial() //输入输出文件初始化 { int n=19,i; KeyType a[]= {15,4,97,64,17,32,108,44,76,9,39,82,56,31,80,73,255,68,MAXKEY}; for (i=0; i0; t=t/2,p=ls[t]) if ((wa[p].rnum=0; i--) { Fi.currec++; //从输入文件读入一个记录 wa[i].rec=Fi.recs[Fi.currec]; wa[i].rnum=1; //其段号为1 Select_MiniMax(ls,wa,i); //调整败者 } } void get_run(LoserTree ls,WorkArea wa,int rc,int &rmax) //求得一个初始归并段 { int q; KeyType minimax; //当前最小关键字 while (wa[ls[0]].rnum==rc) //选得的当前最小记录属当前段时 { q=ls[0]; //q指示当前最小记录在wa中的位置 minimax=wa[q].rec.key; Fo.currec++; //将刚选得的当前最小记录写入输出文件 Fo.length++; Fo.recs[Fo.currec]=wa[q].rec; Fi.currec++; //从输入文件读入下一记录 wa[q].rec=Fi.recs[Fi.currec]; if (Fi.currec>=Fi.length-1) //输入文件结束,虚设记录(属rmax+1段) { wa[q].rnum=rmax+1; wa[q].rec.key=MAXKEY; } else //输入文件非空时 { if(wa[q].rec.key

企业建站2800元起,携手武汉肥猫科技,做一个有见地的颜值派!更多优惠请戳:黄石网站制作 http://huangshi.666rj.com