losertree.h

使用置换选择排序和多路归并实现的外排序程序

#ifndef LOSERTREE_H
#define LOSERTREE_H

#include"public.h"
#define NO_MEANING 99999999	//当某顺串已经全部处理完时，给败方树外部节点填充这个超大值


/*************** 从文件读入一批数据进入缓冲区 *****************/
//输入参数分别是：
//f - 输入文件句柄, b - 输入缓冲区
void fillBuffer(FILE * f, Buffer & b){
	int m = 0;
	node read;  //读出的数据置放在里面
	while((!feof(f))&&(m < MAX_BUFFER)){
		fscanf(f,"%d %s",&read.key,read.infor);
		b.insert(read);
		m++;
	}//while
}


/******** 全局Winner函数，确认A[b]和A[c]的胜者，返回其下标，为b和c之一 ********/
//这里取值小的为胜者
int Winner(node A[], int b, int c){
	//注意：这里我假定T是内建类型，这样才能直接比较大小
	if(A[b].key < A[c].key)
		return b;
	else return c;
}


/********* 全局Loser函数，确认A[b]和A[c]的败者，返回其下标，为b和c之一 **********/
//这里取值大的为败者
int Loser(node A[], int b, int c){
	//注意：这里我假定T是内建类型，这样才能直接比较大小
	if(A[b].key >= A[c].key)
		return b;
	else return c;
}


/**************** 败方树的实现 ***************/
class LoserTree{
	private:
		int MaxSize;	//最大选手数
		int n;	//当前选手数
		int LowExt;	//最底层外部节点数
		int offset;	//最底层外部节点之上的节点总数
		int * B;	//赢者树数组，实际存放的是下标
		node * L;	//元素数组
		void Play(int p, int lc, int rc, int(* winner)(node A[], int b, int c), int(* loser)(node A[], int b, int c));

	public:
		LoserTree(int Treesize);
		~LoserTree(){delete [] B;}
		//初始化败方树
		void Initialize(node A[], int size,int (*winner)(node A[], int b, int c), int(*loser)(node A[], int b, int c));
		//返回最终胜者索引
		int Winner();
		//位置i的选手改变后重构败方树
		void RePlay(int i, int(*winner)(node A[], int b, int c), int (*loser)(node A[], int b, int c));
};

LoserTree::LoserTree(int TreeSize){
	MaxSize = TreeSize;
	B = new int[MaxSize];
	n = 0;
}


//成员函数Winner，返回最终胜者的索引
int LoserTree::Winner(){
	return (n)?B[0]:0;
}


//成员函数Initilalize负责初始化败者树
void LoserTree::Initialize(node A[], int size, int(*winner)(node A[], int b, int c), int(*loser)(node A[], int b, int c)) {

	//能否处理size个选手的数组a[]
	if(size > MaxSize || size < 2){
		printf("%s\n\n","Bad Input!");
		return;
	}

	//初始化成员变量
	n = size;
	L = A;

	//计算s=2^log(n-1)
	int i,s;
	for(s = 1; 2*s <= n-1; s+=s);

	LowExt = 2*(n-s);
	offset = 2*s-1;

	//最底层外部节点的比赛
	for(i = 2; i <= LowExt; i+=2)
		Play((offset+i)/2, i-1, i, winner, loser);
	//处理其余外部节点
	if(n%2){//n为奇数，内部节点和外部节点比赛
		//这里用L[LowExt+1]和它的父节点比赛
		//因为此时它的父节点中存放的是其兄弟节点处的比赛胜者索引
		Play(n/2, B[(n-1)/2], LowExt+1, winner, loser);
		i = LowExt+3;
	}
	else i = LowExt+2;

	//剩余外部节点的比赛
	for(; i<=n; i+=2)
		Play((i-LowExt+n-1)/2, i-1, i, winner, loser);

}



//成员函数Play负责在内部节点B[p]处开始比赛
void LoserTree::Play(int p, int lc, int rc, int(* winner)(node A[], int b, int c), int(* loser)(node A[], int b, int c)){
	
		B[p] = loser(L, lc, rc);//败者索引放在B[p]中
			
		int temp1, temp2;
		temp1 = winner(L, lc, rc);//p处的胜者索引

		while(p>1 && p%2){//右孩子，需要沿路径继续向上比赛
							  //和B[p]的父结点所标识的外部结点相比较
			temp2 = winner(L, temp1, B[p/2]);//p的胜者和p的父结点比较，赢者暂存在temp2中
			B[p/2] = loser(L, temp1, B[p/2]);//败者索引放入B[p/2]
			temp1 = temp2;
			p/=2;
		}//while

		//结束循环(B[p]是左孩子，或者B[1])之后，在B[p]的父结点写入胜者索引
		B[p/2] = temp1; 

}



//成员函数RePlay负责选手i的值改变后重新开始比赛
void LoserTree::RePlay(int i, int (*winner)(node A[], int b, int c), int (*loser)(node A[], int b, int c)){
	if(i <= 0 || i > n){
		printf("%s\n\n","Out of Bounds!");
		return;
	}

	int p;
	//确定父节点的位置
	if(i <= LowExt)
		p = (i+offset)/2;
	else
		p = (i-LowExt+n-1)/2;

	//这里有修改
	//B[0]中始终保存胜者的索引
	B[0] = winner(L, i, B[p]);
	//B[p]中保存败者的索引
	B[p] = loser(L, i, B[p]);

	//这里有修改
	//沿路径向上比赛
	for(; (p/2)>=1; p/=2){
		int temp;//临时存放赢者的索引
		temp = winner(L,B[p/2], B[0]);
		B[p/2] = loser(L,B[p/2], B[0]);	
		B[0] = temp;
	}
}





/******************** 多路归并算法 ********************/
//输入参数分别是：
//lt－败方树，racer－最初的竞赛者，bufferPool－缓冲池，f－输入/输出文件句柄数组
//这里输出文件句柄是f[0]，输入文件句柄是f[1]到f[outfilenum]，outfilenum为输入文件的数目
//NO_MEANING宏代表一个极大值

void multiMerge(LoserTree & lt,node * racer, Buffer * bufferPool, FILE * * f,int outfilenum){
	
	int winner;	//最终胜者索引

	//初始化败方树
	lt.Initialize(racer, outfilenum, Winner, Loser);

	////以下处理f[1]到f[outfilenum]所代表的outfilenum个输入顺串，并把结果输出到f[0]所代表的输出顺串中
	
	//取得最终胜者索引
	winner = lt.Winner();
	
	while(racer[winner].key != NO_MEANING){//循环退出时胜者为NO_MEANING，所有的输入顺串都已经处理完毕
		

		//把胜者插入到输出缓冲区中
		if(bufferPool[0].isFull())//输出缓冲区满，flush到磁盘文件去
			bufferPool[0].flush(f[0]);
		bufferPool[0].insert(racer[winner]);
	
		//从输入缓冲区读入一个新的竞赛者
		if(bufferPool[winner].isEmpty()==false)//输入缓冲区不为空
			bufferPool[winner].read(racer[winner]);//从缓冲区读入值放进racer[winner]
		else{//输入缓冲区为空
				
				if(!feof(f[winner])){//如果对应的输入文件还有数据){//如果对应的输入文件还有数据
				//	
					//从输入文件读入一批数据到输入缓冲区
					fillBuffer(f[winner], bufferPool[winner]);

					//从缓冲区读数据放进racer[winner]
					bufferPool[winner].read(racer[winner]);
				}
				else{//对应的输入文件没有数据
					//在racer[winner]位置放NO_MEANING
					racer[winner].key = NO_MEANING;
				}//else		
		}//else

		//重新进行比赛，取得胜者索引
		lt.RePlay(winner, Winner, Loser);
		winner = lt.Winner();
//		_getch();

	}//while
	 
	//把输出缓冲区中剩余的数据写进磁盘文件
	bufferPool[0].flush(f[0]);

}
#endif