replaceselection.h

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

#ifndef REPLACESELECTION_H
#define REPLACESELECTION_H

#include"public.h"
#include<conio.h>
#include<stdlib.h>
#include<cstring>

bool less(node x, node y){
	return(x.key< y.key);
}

void swap(node * A, int i, int j){
	node temp;
	temp = A[i];
	A[i] = A[j];
	A[j] = temp;
}

class MinHeap{
private:

	int MaxSize;	//heapArray max MaxSize
	int CurrenSize;	//curren number of elements in the heapArray

public:
	node * heapArray;	//pointer to the heapArray array		
	//constructor
	MinHeap(node * h, int num, int max){
		heapArray = h;
		CurrenSize = num;
		MaxSize = max;
		BuildHeap();
	}

	//set the MaxSize of heapArray
	void setSize(int x){
		CurrenSize = x;
	}

	//put an elment in its correct place
	void SiftDown(int pos){
		while(!isLeaf(pos)){
			//get children
			int j = leftchild(pos);
			int rc = rightchild(pos);

			if((rc < CurrenSize) && (less(heapArray[rc], heapArray[j])))	//j is the less child
				j = rc;
			if(less(heapArray[pos], heapArray[j]))
				return;
			swap(heapArray, pos, j);
			pos = j;
		}
	}
	//MaxSize
	int heapsize() const{
		return CurrenSize;
	}

	//judge a leaf
	bool isLeaf(int pos) const{
		return (pos >= CurrenSize/2)&&(pos < CurrenSize);
	}

	//left child
	int leftchild(int pos) const{
		return 2*pos+1;
	}

	//right child
	int rightchild(int pos) const {
		return 2*pos+2;
	}

	//parent
	int parent(int pos) const{
		return (pos-1)/2;
	}

	node getmin(){
		return heapArray[0];
	}

	//minValue
	bool removemin(node & it){
		if(CurrenSize == 0)
			return false;

		//swap min with the last element
		swap(heapArray, 0, --CurrenSize);

		//shif down new root
		if(CurrenSize != 0)
			SiftDown(0);

		//return deleted value
		it = heapArray[CurrenSize];
		return true;

	}

	//bulid heapArray
	void BuildHeap(){
		for(int i = CurrenSize/2-1; i >= 0; i--){
			SiftDown(i);
//]			printf("%d ",i);
		}

	}

};

/****** 函数initRacer负责从输入文件中读取数据初始化racer *****/
int initRacer(FILE * inputFile,  Buffer& input, node * A, int n){
//	printf("%s\n","Originally the data in the array A are:");
	int i=0;
	for(int j = 0; j < n; j++){
		if(input.isEmpty() == false){	//输入缓冲不为空
			input.read(A[j]);	//读数据置入数组A
//			printf("%d %s\n",A[j].key,A[j].infor);
		}
		else{	//输入缓冲为空

			//往缓冲区中插入数据
			node read;

			while(i<MAX_BUFFER&&(!feof(inputFile))){
				fscanf(inputFile, "%d %s", &read.key,read.infor);
				input.insert(read);
				i++;
				//				_getch();
			}
			//读数据置入数组A
			if(input.isEmpty()==false){
				input.read(A[j]);
//				printf("%d %s\n",A[j].key,A[j].infor);
			}
		}
	}
	return (i<n?i:n);
}


/********* sendToOutputBuffer负责把mval送到输出缓冲区中 **********/
//若输出缓冲区满，把数据写进输出文件
//若输入缓冲区空，从输入文件读取数据
void sendToOutputBuffer(Buffer & input, Buffer & output, FILE * inputFile, FILE * outputFile,  node mval){

	node read;

	if(output.isFull()){//输出缓冲区为满
		output.flush(outputFile);//把数据写入输出文件
	}
	output.insert(mval);  //最小值输出到输出缓冲区	

	if(input.isEmpty()){//输入缓冲区为空
//		printf("%s\n","The new-read data into the input buffer are:");
		int m = 0;
		while((!feof(inputFile))&&(m < MAX_BUFFER)){
			fscanf(inputFile, "%d %s", &read.key,read.infor);
			input.insert(read);
			m++;
		}
//		input.list();
	}


}
void endUp(Buffer& output, FILE * & inputFile, FILE * & outputFile){
	
	//把输出缓冲区中剩余的内容flush到输出文件中
	output.flush(outputFile);
	fclose(inputFile);
	fclose(outputFile);
}


/****************** 置换选择算法 *********************/
//A是从外存读入n个元素后所存放的数组，n是数组元素的个数
//inputFile和outputFile分别是指向输入和输出文件结构体的指针
//input和output分别是输入和输出缓冲区
int replacementSelection(node * A, int n, FILE *  inputFile, Buffer& input,Buffer& output){
	int outfilecur=1;
	char fname[20];
	int current=initRacer(inputFile, input, A, n);
//	printf("%d\n",current);
	bool go=true;
	while(go){
		for(int k=0;k<20;k++)
			fname[k]='\0';
		_itoa(outfilecur, fname, 10);
		strcat(fname,".txt");
		FILE *outputFile=fopen(fname,"w+");
		outfilecur++;
		node mval;  //存放最小值堆的最小值
		node r;  //存放从输入缓冲区中读入的元素
		/****************** 算法主体部分 *******************/
		//初始化堆的数据，从磁盘文件中读入n个数据置入数组A
		//建立最小值堆
		int emptyrest=n;
		bool emptyflag=false;
		MinHeap H(A, current, n);  
//		printf("%s\n","The data in the MinHeap are:");
//			for(int t = 0; t < current; t++)
//				printf("%d ",H.heapArray[t].key);
//			printf("\n");
//			_getch();
		for(int last = (current-1); last >= 0;){//堆不为空，就作这个循环
			mval = H.heapArray[0];  //堆的最小值
			sendToOutputBuffer(input, output, inputFile, outputFile, mval);//把mval送到输出缓冲区，同时处理因缓冲区空或满造成的各种情形
			if(input.isEmpty()==false){
				input.read(r);  //从输入缓冲区读入一个记录
				if(!less(r, mval)){//如果r的关键码值大于刚才输出缓冲区记录的关键码值，把r放到根结点
					H.heapArray[0] = r;
				}
				else{  //否则用last位置的记录代替根结点，把r放到last位置
					H.heapArray[0] = H.heapArray[last];
					H.heapArray[last] = r;
					H.setSize(last);
					last--;
				}
			}
			else{
				go=false;
				if(!emptyflag)
					emptyrest=last+1;
				emptyflag=true;
				H.heapArray[0]=H.heapArray[last];
				H.setSize(last);
				last--;
			}
			if(last >= 0){//重新排列堆
				H.SiftDown(0);  //把根结点记录下降到合适的位置
				
			}			
		} //for

		endUp(output, inputFile,outputFile);
		fclose(outputFile);
		if(current==MAX&&emptyrest<n){
			for(int k=0;k<20;k++)
				fname[k]='\0';
			_itoa(outfilecur, fname, 10);
			strcat(fname,".txt");
			outputFile=fopen(fname,"w+");
			outfilecur++;
			for(int i=0;i<n-emptyrest;i++)
				A[i]=H.heapArray[emptyrest+i];
			MinHeap h(A,n-emptyrest,n);
			node temp;
			h.removemin(temp);
			for(int k=n-emptyrest-2;k>=0;k--){
				temp=h.heapArray[0];
				sendToOutputBuffer(input,output,inputFile,outputFile,temp);
				h.heapArray[0]=h.heapArray[k];
				h.setSize(k);
				if(k>0)
					h.SiftDown(0);
			}
			endUp(output, inputFile,outputFile);
			fclose(outputFile);
		}
	}//while(go)
	return outfilecur-1;
}


#endif