数据结构实践——败者树归并模拟-白红宇

数据结构实践——败者树归并模拟

阅读量：4583 次

发布时间：2019-06-09

本文共 1361 字，大约阅读时间需要 4 分钟。

本文是针对[]中的实践项目。

【项目】败者树归并模拟

　　编敲代码，模拟改者树实现5路归并算法的过程。

　　设有5个文件。当中的记录的关键字例如以下：

　　F0:{17,21,∞}　F1:{5,44,∞}　F2:{10,12,∞}F3: {29,32,∞} F4: {15,56,∞}

　　要求将其归并为一个有序段并输出。

　　如果这些输入文件数据保存在内存中。输出结果也不必输出到文件，而是在屏幕上输出就可以。

#include 
      
       #define MaxSize 20          //每一个文件里最多记录#define K 5                 //5路平衡归并#define MAXKEY 32767        //最大关键字值∞#define MINKEY -32768       //最小关键字值-∞typedef int InfoType;typedef int KeyType;typedef struct              //记录类型{    KeyType key;            //关键字项    InfoType otherinfo;     //其它数据项,详细类型在主程中定义} RecType;typedef struct{    RecType recs[MaxSize];    int currec;} FileType;                 //文件类型typedef int LoserTree[K];   //败者树是全然二叉树且不含叶子RecType b[K];               //b中存放各段中取出的当前记录FileType F[K];              //存放文件记录的数组void initial(){    int i;                  //5个初始文件,当前读记录号为-1    F[0].recs[0].key=17;    F[0].recs[1].key=21;    F[0].recs[2].key=MAXKEY;    F[1].recs[0].key=5;    F[1].recs[1].key=44;    F[1].recs[2].key=MAXKEY;    F[2].recs[0].key=10;    F[2].recs[1].key=12;    F[2].recs[2].key=MAXKEY;    F[3].recs[0].key=29;    F[3].recs[1].key=32;    F[3].recs[2].key=MAXKEY;    F[4].recs[0].key=15;    F[4].recs[1].key=56;    F[4].recs[2].key=MAXKEY;    for (i=0;i