replaceselection.h

队放置于硬盘上的文件进行外排序

#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <iostream.h>
#include <fstream.h>
#include <string.h>
#include "minheap.h"
#include "Buffer1.h"

//************************************* 置换选择算法 ************************************//
//变量说明：
//  i：顺串数
//  BUFarray: 用作输入缓冲 
//  n:为缓冲区开的内存
//  inputFile：原文件
//  input output：输入输出缓冲区
// 特别声明：部分代码根据书上代码和网站贴出代码编写


template <class Elem>
void replacementSelection(int& i, Elem * BUFarray, int n,  FILE *  inputFile, Buffer1<Elem> & input,Buffer1<Elem> & output)
{

	Elem mval;  //存放最小值堆的最小值
	Elem r;  //存放从输入缓冲区中读入的元素
	Elem read;

	//首先初始化输入数组
	int j=initRacer(inputFile, input, BUFarray, n);

	if(n!=j)//如果只生成一个顺串的话
	{
		n=j;
		MinHeap<Elem> H(BUFarray, n, n);//直接将这些记录建成堆,输出到“output.txt”
		
		ofstream outputFile1("output.txt",ios::out);	
		
		for(int last=n-1;last>=0;last--)
		{
		    mval = H.heapArray[0];  //堆的最小值
	    	sendToOutputBuffer(input, output, inputFile, outputFile1, mval);
			H.heapArray[0]=H.heapArray[last];
			H.setSize(last);				 
	        H.SiftDown(0);
		}
		output.flush(outputFile1);//把数据写入输出文件
	    outputFile1.close();
			
		return;
	}
	
 
    char  filename[20];
	while(1)//生成多个顺串的情况
	{

		MinHeap<Elem> H(BUFarray, n, n); //先建堆

		_itoa(i, filename, 10);//每一个顺串都放入“i.txt”文件中，先进行文件名转换
		strcat(filename, ".txt");

		ofstream outputFile(filename,ios::out);
		i++;

	
		for(int last = (n-1); last >= 0;)
		{   
			mval = H.heapArray[0];  //堆的最小值
			sendToOutputBuffer(input, output, inputFile, outputFile, mval);//把mval送到输出缓冲区，同时处理因缓冲区空或满造成的各种情形

			if(input.isEmpty())//如果输入缓冲区不为空
			{
                cout<<"No."<<i-1<<"顺串生成中..."<<endl;
				output.flush(outputFile);//把数据写入输出文件
				outputFile.close();
				cout<<"No."<<i-1<<"顺串已生成"<<endl;
        
				_itoa(i, filename, 10);
				strcat(filename, ".txt");
				ofstream outputFile(filename,ios::out);
				i++;

				last=n-1;
				BUFarray[0] = BUFarray[last];
				MinHeap<Elem> H(BUFarray, last, last); 
				
		
				for(last=last-1;last>=0;last--)
				{
					mval=H.heapArray[0];  //堆的最小值
	    			sendToOutputBuffer(input, output, inputFile, outputFile, mval);
					H.heapArray[0]=H.heapArray[last];
					H.setSize(last);				 
					H.SiftDown(0);
				}

				cout<<"No."<<i-1<<"顺串生成中..."<<endl;
				output.flush(outputFile);//把数据写入输出文件
				outputFile.close();
				cout<<"No."<<i-1<<"顺串已生成"<<endl;
			   return; 

			} 

			else//如果输入缓冲区为空
			{

				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--;
				}

			}  
			if(last >= 0)
			{
				H.SiftDown(0);
			}
            
		} 
		cout<<"No."<<i-1<<"顺串生成中..."<<endl;
		output.flush(outputFile);//把数据写入输出文件
		outputFile.close();
		cout<<"No."<<i-1<<"顺串已生成"<<endl;
	} 

}



/****** 函数initRacer负责从输入文件中读取数据初始化racer *****/
template <class Elem>

int initRacer( FILE *  inputFile, Buffer1<Elem> & input, Elem * BUFarray, int &n)
{
	
	for(int j = 0; j < n; j++)
	{
		if(input.isEmpty() == false)
		{	//输入缓冲不为空
			input.read(BUFarray[j]);
			
		}    
	
		else
			if(!feof(inputFile))//如果没到文件末尾
			{	
				char read[52];
				for(int i = 0; i < MEMORY3 && !feof(inputFile); i++ )
				{
					fgets(read,52, inputFile);
					node rec(read);	
					input.insert(rec);
		
				}

				input.read(BUFarray[j]);//将数据读入缓冲数组中
				if(feof(inputFile)&&i>0)
				{
					input.n--;
				}

			}
		else
			break;
			
	}

	return j;
	
}

/********* sendToOutputBuffer负责把mval送到输出缓冲区中 **********/


template <class Elem>
void sendToOutputBuffer(Buffer1<Elem> & input, Buffer1<Elem> & output,  FILE *  inputFile, ofstream outputFile, Elem mval){
	
	char read[52];

	if(output.isFull())//若输出缓冲区满，把数据写进输出文件
	{
		output.flush(outputFile);
	}

	output.insert(mval);//最小值输出到输出缓冲区
	
	if(input.isEmpty())//若输入缓冲区空，从输入文件读取数据
	{
		
		int m=0;
		while((!feof(inputFile))&&(m < MEMORY3))
		{
			fgets(read,52, inputFile);
			Elem temp(read);	
			input.insert(temp);
			m++;
		}
		if(feof(inputFile)&&m>0)
		{
			input.n--;
		}
	}

}