hugefilesorter.cpp

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

// 我们真诚地保证：
    
// 我们独立地完成了整个程序从分析、设计到编码的所有工作。
// 如果在上述过程中，我们遇到了什么困难而求教于人，那么，我们将在程序实习报告中
// 详细地列举我所遇到的问题，以及别人给我的提示。

 
// 我们的程序里中凡是引用到其他程序或文档之处，
// 例如教材、课堂笔记、网上的源代码以及其他参考书上的代码段,
// 我们都已经在程序的注释里很清楚地注明了引用的出处。

// 我们从未抄袭过别人的程序，也没有盗用别人的程序，
// 不管是修改式的抄袭还是原封不动的抄袭。

// 我们编写这个程序，从来没有想过要去破坏或妨碍其他计算机系统的正常运转。
    
// 00548261 王璐
// 00548316 赵旭婷

//文件名称：hugefilesorter

//项目名称：外排序

//创建者：赵旭婷 王璐

//创建时间：2006.12.15

//最后修改时间：2006.12.21

//功能：对于一个较大的含有多个记录的文件进行排序 

//头文件有"replaceselection.h"，"loserTree.h"，"buffer1.h","buffer.h","replaceselection.h"

#include "replaceselection.h"
#include "losertree.h"
#include<ctime>
#include<stdlib.h>
#include<memory.h>

int MEMORY1=2000*64;//申请的一个输入缓冲区的大小
int MEMORY2 ;//一个顺串的空间
int MEMORY3=4000*64 ;//一个Buffer的大小

int branches=1;//生成顺串的个数

clock_t CLOCK ;//计时器

class node//结点类
{
public:
	char key[6];//关键码
	char content[52];//记录的内容
	
	node()//构造函数
	{
		memset(content,0,52);
		memset(key,0,6);
	}
	
	node(char * input)//构造函数
	{
		strcpy(content,input);
		strncpy(key,input,5);		
	}

	//运算符重载
	operator <(node obj)
	{
		return (strcmp(key,obj.key)<0);
	}
	operator =(node obj)
	{
		strcpy(content,obj.content);
		strcpy(key,obj.key);
	}
	operator ==(node obj)
	{
		
		return (strcmp(key,obj.key)==0);
	}
	operator !=(node obj)
	{
		
		return (strcmp(key,obj.key)!=0);
	}
};

node NO_MEANING;

//美化界面的函数
void Screen();

void main()
{
 	int i;
	Screen();

	//为NO_MEANING赋值
	for(i=0;i<5;i++)
	{
		NO_MEANING.key[i]=127;
	}

	NO_MEANING.key[5]='\0';

	//打开待排序文件
	char name[20]="input.txt";
	FILE * inputFile = fopen(name,"r");
		
	CLOCK = clock(); //开始计时	
    
	Buffer1<node> input;
	Buffer1<node> output;
	//一个输入缓冲区
	node* BUFarray=new node[MEMORY1];
	
	//置换选择排序
	replacementSelection<node>(branches, BUFarray, MEMORY1, inputFile, input, output);
	
	delete []BUFarray;

    //如果文件够大，生成的顺串数已经多于一个了，就进行归并
	if(branches>=2)
	{
		MEMORY2=64*10000/branches;//每一个顺串占有的空间

		//句柄数组，每个文件句柄的空间是MEMORY1
		//f[0]对应"output.txt",是输出句柄，f[i]对应"i.txt"是输入句柄
		FILE * *f=new FILE*[branches];

		Buffer<node>* bufferPool=new Buffer<node> [branches];//缓冲池
	
		f[0] = fopen("output.txt", "w+");//打开输出文件

		char filename [20];	//含有顺串文件名
		int i,j;
		for(i=1;i<branches;i++)
		{
			//第i个顺串存储在"i.txt"文档中,建立i.txt文档
	    	_itoa(i,filename,10);
			strcat(filename,".txt");
			f[i]=fopen(filename,"r");
			
			char tempread[52];	
		
			//从文件中读入数据并放到缓冲区中
			for(j=0;j<MEMORY2 && !feof(f[i]);j++)
			{
				fgets(tempread,52,f[i]);
				node temp(tempread);
				bufferPool[i].insert(temp);
			}

			if(feof(f[i]) && j>0)
				bufferPool[i].n--;
		}

	
		LoserTree<node> lt;	//败者树
	
		node *racer=new node[branches];//败者树的叶子结点，即所有顺串
	//***********************开始归并**************************//
		multiMerge<node>(lt, racer, bufferPool, f);
	//*********************************************************//
		for(i=0;i<branches;i++)//关闭所有文件句柄
		{
			fclose(f[i]);
		} 
		cout<<"******************************************************************************"<<endl;
		cout<<"排序完成，用时"<<(clock() - CLOCK)<<"ms"<<endl;
		cout<<"******************************************************************************"<<endl;
		exit(1);
	}//if
	else
	{
		cout<<"******************************************************************************"<<endl;
		cout<<"排序完成，用时"<<(clock() - CLOCK)<<"ms"<<endl;
		cout<<"******************************************************************************"<<endl;
	}
}

//为了美化界面所加的函数
void Screen()
{
	cout<<"******************************************************************************"<<endl;
	cout<<"欢迎光临"<<endl;
	cout<<"本程序的功能是排序文件内纪录"<<endl;
	cout<<"版权所有 程序设计者：赵旭婷 王璐"<<endl;
	cout<<"****************************************************************************** "<<endl;
	cout<<"  \\/\\/    *            *  ※              \\/\\/"<<endl;
    cout<<"  \\/\\/  //╱      ﹡                 \//\//  \//\//  //╱             "<<endl;
   cout<<"  //╱╭⊙╲           \\/\\/    \//\//  //╱ //╱╭⊙╲                ︵︵"<<endl;
 cout<<"╭⊙╲╰╯\\ ╲   \/\/  //╱     //╱╭⊙╲╭⊙╲╰╯\\ ╲              |/╱"<<endl;
 cout<<"╰╯\\ ╲  │, ￣//╱╭⊙╲  ╭⊙╲╰╯\\ ╰╯\\ ╲  │  ￣￣\\      ╱￣￣│"<<endl;
  cout<<"   │  ￣￣\\-╭⊙╲ ╰╯\\ ╲╰╯\\ ╲  │,  ╭│  ￣￣\\─-╲│_ // ＊ ☆│"<<endl;
  cout<<"   /╱─-╲│╰╯\\ ╲  │, ￣￣│  ￣￣\\ ╯/╱─-╲│─╮\\╱//   \  ☆ ╱"<<endl;
   cout<<" //   ◆  \\\\   │  ￣￣╲ -╭ /╱─-╲│ //   ◆  \\  ╰─\╰┬┬┬┬┐"<<endl;
  cout<<" ◆         ◆  /╱─-╲│ ╯//   ◆ // ◆         ◆      ￣￣￣￣￣￣"<<endl;
   cout<<"      ※         \\\\      \\\\  ◆      ◆       ﹡ ＊      ﹡"<<endl;
   cout<<"                 ◆  ﹡  ◆                                   ＊    ·"<<endl;
    cout<<" ＊       *                           ※﹡        ＊"<<endl;
  }