简单外存文件的排序操作

#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(); }