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

本文是针对[数据结构基础系列(10)：外部排序]中的实践项目。

【项目】败者树归并模拟
　　编敲代码，模拟改者树实现5路归并算法的过程。
　　设有5个文件。当中的记录的关键字例如以下：
　　F0:{17,21,∞}　F1:{5,44,∞}　F2:{10,12,∞}F3: {29,32,∞} F4: {15,56,∞}
　　要求将其归并为一个有序段并输出。
　　如果这些输入文件数据保存在内存中。输出结果也不必输出到文件，而是在屏幕上输出就可以。

參考解答

#include <stdio.h>
#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<K;i++)
        F[i].currec=-1;
}
void input(int i,int &key)  //从F[i]文件里读一个记录到b[i]中
{
    F[i].currec++;
    key=F[i].recs[F[i].currec].key;
}
void output(int q)      //输出F[q]中的当前记录
{
    printf("输出F[%d]的关键字%d
",q,F[q].recs[F[q].currec].key);
}
void Adjust(LoserTree ls,int s)
//沿从叶子节点b[s]到根节点ls[0]的路径调整败者树
{
    int i,t;
    t=(s+K)/2;          //ls[t]是b[s]的双亲节点