本文主要是介绍数据结构实践——败者树归并模拟，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
本文是针对[数据结构基础系列(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个初始文件,当前读记录号为-1F[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\n",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]的双亲节点while(t>0){if(b[s].key>b[ls[t]].key){i=s;s=ls[t]; //s指示新的胜者ls[t]=i;}t=t/2;}ls[0]=s;
}
void display(LoserTree ls) //输出败者树
{int i;printf("败者树:");for (i=0;i<K;i++)if (b[ls[i]].key==MAXKEY)printf("%d(∞) ",ls[i]);else if (b[ls[i]].key==MINKEY)printf("%d(-∞) ",ls[i]);elseprintf("%d(%d) ",ls[i],b[ls[i]].key);printf("\n");
}
void CreateLoserTree(LoserTree ls) //建立败者树
{int i;b[K].key=MINKEY; //b[K]置为最小关键字for (i=0;i<K;i++)ls[i]=K; //设置ls中“败者”的初值,全部为最小关键字段号for(i=K-1;i>=0;--i) //依次从b[K-1]，b[K-2]，…，b[0]出发调整败者Adjust(ls,i);
}
void K_Merge(LoserTree ls) //利用败者树ls将进行K路归并到输出
{int i,q;for(i=0;i<K;++i) //分别从k个输入归并段读入该段当前第一个记录的关键字到binput(i,b[i].key);CreateLoserTree(ls); //建败者树ls,选得最小关键字为b[ls[0]].keydisplay(ls);while(b[ls[0]].key!=MAXKEY){q=ls[0]; //q指示当前最小关键字所在归并段output(q); //将编号为q的归并段中当前（关键字为b[q].key）的记录输出input(q,b[q].key); //从编号为q的输入归并段中读人下一个记录的关键字if (b[q].key==MAXKEY)printf("从F[%d]中添加关键字∞并调整\n",q);elseprintf("从F[%d]中添加关键字%d并调整\n",q,b[q].key);Adjust(ls,q); //调整败者树，选择新的最小关键字display(ls);}
}
int main()
{LoserTree ls;initial();K_Merge(ls);printf("\n");return 0;
}这篇关于数据结构实践——败者树归并模拟的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
