i.cpp

实现外存程序的排序号 草操作 数据结构教材实验

#include<iostream.h>
#include<iomanip.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<fstream.h>

struct ElemType{
	int num;
	int stn;
	char bir[12];
};

int b=sizeof(ElemType);

void QuickSort(ElemType A[],int s,int t)
{
	int i=s,j=t+1;
	ElemType x=A[s];
	do{
		do i++;while(A[i].stn<x.stn);
		do j--;while(A[j].stn>x.stn);
		if(i<j)
		{
			ElemType temp=A[i];
			A[i]=A[j];A[j]=temp;
		}
	}while(i<j);
	A[s]=A[j];A[j]=x;
	if(s<j-1) QuickSort(A,s,j-1);
	if(j+1<t) QuickSort(A,j+1,t);
}
void FTwoMerge(fstream &A,fstream &R,int s,int m,int t)
{
	int i,j,k;
	ElemType a1,a2;
	i=s;j=m+1;k=s;
	R.seekg(k*b);
	while(i<=m && j<=t){
		A.seekg(i*b);
		A.read((char *)&a1,b);
		A.seekg(j*b);
		A.read((char *)&a2,b);
		if(a1.stn<=a2.stn){
			R.write((char*)&a1,b);
			i++;
		}
		else{
			R.write((char *)&a2,b);
			j++;
		}
	}
	A.seekg(i*b);
	while(i<=m){
		A.read((char *)&a1,b);
		R.write((char *)&a1,b);
		i++;
	}
	A.seekg(j*b);
	while(j<=t){
		A.read((char *)&a2,b);
		R.write((char *)&a2,b);
		j++;
	}
}
void FMergePass(fstream &A,fstream &R,int n,int len)
{
	ElemType x;
	int p=0;
	while(p+2*len-1<=n-1)
	{
		FTwoMerge(A,R,p,p+len-1,p+2*len-1);
		p+=2*len;
	}
	if(p+len-1<n-1)
		FTwoMerge(A,R,p,p+len-1,n-1);
	else{
		A.seekg(p*b);
		R.seekg(p*b);
		for(int i=p;i<=n-1;i++){
			A.read((char *)&x,b);
			R.write((char *)&x,b);
		}
	}
}
void FMergeSort(fstream &A,int BlockSize)
{
	fstream R("temp.dat",ios::in|ios::out|ios::binary);
	if(!R){
		cerr<<"temp.dat"<<' '<<"not found!"<<endl;
			exit(1);
	}
	int len=BlockSize;
	A.seekg(0,ios::end);
	int n=A.tellg()/b;
	while(len<n){
		FMergePass(A,R,n,len);
		len*=2;
		FMergePass(R,A,n,len);
		len*=2;
	}
	R.close();
	remove("temp.dat");
}
void Print(fstream &ff)
{
	ElemType x;
	ff.seekg(0,ios::end);
	int n=ff.tellg()/b;
	ff.seekg(0);
	for(int i=0;i<n;i++){
		ff.read((char *)&x,b);
		if(i%15==0)
			cout<<endl;
		cout<<setw(4)<<x.stn;
	}
	cout<<endl;
}
void LoadFile(char * fname,int n)
{
	fstream f(fname,ios::out|ios::binary);
	if(!f){
		cerr<<fname<<' '<<"not found!"<<endl;
		exit(1);
	}
	for(int i=0;i<n;i++)
	{
		ElemType x;
		x.stn=rand()%500;
		f.write((char *)&x,sizeof(ElemType));
	}
	f.close();
}
void main()
{
	int n;
	cout<<"输入存于文件的记录数：";
	cin>>n;
	cout<<endl;
	int BlockSize=10;
	LoadFile("file1.dat",n);
	fstream ff("file1.dat",ios::in|ios::out|ios::nocreate|ios::binary);
	if(!ff){
		cerr<<"File not open!";
		exit (1);
	}
	cout<<"排序前文件的数据:";
	Print(ff);
	cout<<endl;
	ff.seekg(0,ios::end);
	n=ff.tellg()/b;
	ff.seekg(0);
	if(n<=BlockSize)
	{
		ElemType *A=new ElemType[n];
		if (A==NULL){
			cerr<<"menory allocation failure!"<<endl;
			exit(1);
		}
		ff.read((char *)A,n*b);
		QuickSort(A,0,n-1);
		ff.seekg(0);
		ff.write((char *)A,n*b);
		delete []A;
	}
	else
	{
		ElemType *A=new ElemType[BlockSize];
		if(A==NULL){
			cerr<<"memory allocation failure!"<<endl;
			exit(1);
		}
		int k=n/BlockSize;
		int m=n%BlockSize;
		for(int i=0;i<k;i++)
		{
			ff.seekg(i*BlockSize*b);
			ff.read((char *)A,BlockSize*b);
			QuickSort(A,0,BlockSize-1);
			ff.seekg(i*BlockSize*b);
			ff.write((char*)A,BlockSize*b);
		}
		if(m>0){
			ff.read((char *)A,m*b);
			QuickSort(A,0,m-1);
			ff.seekg(k*BlockSize*b);
			ff.write((char *)A,m*b);
		}
		delete []A;
		FMergeSort(ff,BlockSize);
	}
	 cout<<"排序后文件中的数据：";
	Print(ff);
	cout<<endl;
	ff.close();
}