首页 > 代码库 > 数据结构实践——败者树归并模拟
数据结构实践——败者树归并模拟
本文是针对[数据结构基础系列(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\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]的双亲节点数据结构实践——败者树归并模拟
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。