//外存文件的排序操作WSort1.h
typedef struct
  {int key;
   int stn;}ElemType;
int b=sizeof(ElemType);//b表示ElemType記錄類型的大小
//類定義
class LoadFile
{public:
  //構造函數
  //向物理文件名為fname指針所指文件中輸出n個記錄
  LoadFile(char* fname,int n);
  //把文件A中兩個相鄰位置s?m和m+1?t的有序表歸并為
  //文件R中對應位置s?t上的一個有序表
  void FTwoMerge(fstream &A,fstream &R,int s,int m,int t);
  //對文件A進行一趟二路歸并的算法
  void FMergePass(fstream &A,fstream &R,int n,int len);
  //對磁盤文件進行二路歸并排序的算法
  void FMergeSort(fstream &A, int BlockSize);
  //順序打印ff文件中每個記錄
  void Print(fstream &ff);
};
//類的實現
//向物理文件名為fname的指針所指文件中輸出n個記錄
LoadFile::LoadFile(char* fname, int n)
{ofstream f(fname,ios::out|ios::binary);
 //用所給的物理文件名定義一個輸出文件
 //流對象f是與物理文件相對應的邏輯文件
 if(!f) {
  cerr<<fname<<' '<<"not found!"<<endl;exit(1);}
 for(int i=0; i<n; i++)
 {//假定向每個記錄的排序碼域的數據由隨機產生
  ElemType x;
  x.key=i;x.stn=rand()%100;
  f.write((char *)&x,b);}
}
//把文件A中兩個相鄰位置s?m和m+1?t的有序表歸并為
//文件R中對應位置s?t上的一個有序表
void LoadFile::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);  //將文件R中的文件指針移到記錄下標為k的位置,
 //兩個有序表中同時存在未歸并元素時的處理過程
 while(i<=m && j<=t)
  {A.seekg(i*b);
   //從文件A的記錄下標為s開始的歸并段中讀出一個記錄到a1中
   A.read((char*)&a1,b);
  //從文件A的記錄下標為m+1開始的歸并段中讀出一個記錄到a2中
   A.seekg(j*b);
   A.read((char*)&a2,b);
  //將a1和a2中排序碼較小的記錄寫入到R文件中
  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++;
}}
//對文件A進行一趟二路歸并的算法
void LoadFile::FMergePass(fstream &A,fstream &R,int n,int len)
//把文件A中每個長度為len的有序表兩兩歸并到文件R中
{ElemType x;
 int p=0;//p用于指向每一對歸并段的首記錄位置,初值為0
 while(p+2*len-1<=n-1)
  {//兩兩歸并長度均為len的有序表
   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 { //把剩下的最后一個有序表復制到R中
   A.seekg(p*b);  //移動文件A中的指針到規定的位置
   R.seekg(p*b);  //移動文件R中的指針到對應位置
   for(int i=p; i<=n-1; i++) {
     A.read((char*)&x,b);
     R.write((char*)&x,b);}
}}
//對磁盤文件進行二路歸并排序的算法
void LoadFile::FMergeSort(fstream &A, int BlockSize)
//采用歸并排序的方法對文件A中的每個有序
//子表長度為BlockSize的記錄進行排序
{char *ff=".\\temp.dat";
 fstream R(ff,ios::in|ios::out|ios::binary|ios::trunc);
 //定義一個能夠按塊隨機存取的輔助文件R
 if(!R) {
  cerr<<"temp.dat"<<' '<<"not open!"<<endl;exit(1);}
 int len=BlockSize;  
 //從有序表長度為給定值BlockSize開始歸并
 A.seekg(0,ios::end);  
 //將文件A中的指針移到文件的末尾
 int n=A.tellg()/b;
 //用n表示文件中所含的記錄個數,b為記錄的大小
 while(len<n) {
   FMergePass(A,R,n,len); 
 //從A歸并到R中,得到每個有序表的長度為2*len
 len*=2;
 //修改len的值為R中的每個有序表的長度
 FMergePass(R,A,n,len);
 //從R歸并到A中,得到每個有序表的長度為2*len
 len*=2;}
 //修改len的值為A中的每個有序表的長度
 R.close();//關閉輔助文件R
 //從磁盤上刪除R所對應的物理文件
 remove(ff);
}
//順序打印出ff文件中每個記錄
void LoadFile::Print(fstream &ff)
{ElemType x;
 ff.seekg(0,ios::end);//將文件指針移至文件未
 int n=ff.tellg()/b; //用n表示文件所含的記錄數
 ff.seekg(0);  //將文件指針移至文件首
 for(int i=0;i<n;i++) {
  ff.read((char*) &x, b);//從文件中讀一記錄到x中
  if(i%10==0)//每行顯示10個數據
   cout<<endl;//每個數據占4個字符顯示位置
   cout<<setw(4)<<x.stn;}
 cout<<endl;
}