• 大小: 4KB
    文件类型: .cpp
    金币: 1
    下载: 0 次
    发布日期: 2021-05-26
  • 语言: C/C++
  • 标签:

资源简介

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]

评论

共有 条评论

相关资源