资源简介
vc++实现使用败者树实现外排序
vc++实现使用败者树实现外排序
代码片段和文件信息
#include
#include
#include
#include
#include
const int MAXN = 10000; //内排序最大容量
const int MAXM = MAXN; //最多分成MAXM个文件
const int MAXV = 99999999; //最大整数
FILE *fIn;
FILE *fOut;
FILE* fTemp[MAXM];
char filename[MAXM][20];
int fCount[MAXM];
int run;
typedef struct tagData
{
int key;
char s[10];
int run;
}Data;
int ls[MAXN]; //败者树中间节点,存放败者的下标
Data d[MAXN]; //败者树叶节点,存放排序数据
int cmp1(int a int b)
{
if(d[a].run == d[b].run) return d[a].key else return d[a].run }
//败者树共n个叶节点,d[x]更新了,调整败者树
bool AdjustLS(int nint x int (*cmp)(intint))
{
if(x<0 || x>=n) return false;
int f; //x的父节点在ls中的下标
int winter = x;
int temp;
for(f=(n+x)/2; f>0; f/=2)
{
if(cmp(ls[f] winter) > 0)
{
temp = winter;
winter = ls[f];
ls[f] = temp;
}
}
ls[0] = winter;
return true;
}
//从文件读数据到d[x]
int ReadData(FILE *fp int x)
{
return fscanf(fp“%d %s“ &d[x].key &d[x].s);
}
//写d[x]到文件
int WriteData(FILE *fp int x)
{
return fprintf(fp “%d %s\n“ d[x].key d[x].s);
}
//初始化败者树叶节点个数为n
int intiLS(int n)
{
memset(d0sizeof(d));
memset(ls0sizeof(ls));
int i;
bool ef = false;
d[0].key = -MAXV; //人为制造d[0]为胜者便于初始化LS
for(i=1; i {
if(ef || ReadData(fIni)==EOF)
{
ef =true;
d[i].run = MAXV;
}
AdjustLS(nicmp1);
}
return n;
}
int initLS2(FILE **fT int k)
{
memset(d0sizeof(d));
memset(ls0sizeof(ls));
int i;
d[0].key = -MAXV; //人为制造d[0]为胜者便于初始化LS
for(i=1; i {
if(ReadData(fT[i]i)==EOF)
{
d[i].run = MAXV;
}
AdjustLS(kicmp1);
}
if(ReadData(fT[0]0)==EOF)
{
d[0].run = MAXV;
}
AdjustLS(k0cmp1);
return k;
}
//把fp分解成若干个有序的文件fT[i]返回文件数
int divide(FILE *fp FILE **fT)
{
int n = intiLS(MAXN); //败者树的叶子数
int run = -1;
bool ef = false;
int i = ls[0];
if(ReadData(fpi)==EOF) //读出人造的第一个胜者
{
ef = true;
d[i]
评论
共有 条评论