/* algo11-2.c 通過(guò)置換－選擇排序產(chǎn)生不等長(zhǎng)的初始?xì)w并段文件 */
 #include"c1.h"
 typedef int InfoType; /* 定義其它數(shù)據(jù)項(xiàng)的類(lèi)型 */
 #include"c10-1.h" /* 定義KeyType、RedType及SqList */
 #define MAXKEY INT_MAX
 #define RUNEND_SYMBOL INT_MAX
 #define w 6 /* 內(nèi)存工作區(qū)可容納的記錄個(gè)數(shù) */
 #define M 10 /* 設(shè)輸出M個(gè)數(shù)據(jù)換行 */
 #define N 24 /* 設(shè)大文件有N個(gè)數(shù)據(jù) */

 typedef int LoserTree[w]; /* 敗者樹(shù)是完全二叉樹(shù)且不含葉子，可采用順序存儲(chǔ)結(jié)構(gòu) */
 typedef struct
 {
   RedType rec; /* 記錄 */
   KeyType key; /* 從記錄中抽取的關(guān)鍵字 */
   int rnum; /* 所屬歸并段的段號(hào) */
 }RedNode,WorkArea[w]; /* 內(nèi)存工作區(qū)，容量為w */

 void Select_MiniMax(LoserTree ls,WorkArea wa,int q) /* 算法11.6 */
 { /* 從wa[q]起到敗者樹(shù)的根比較選擇MINIMAX記錄，并由q指示它所在的歸并段 */
   int p,s,t;
   for(t=(w+q)/2,p=ls[t];t>0;t=t/2,p=ls[t])
     if(wa[p].rnum<wa[q].rnum||wa[p].rnum==wa[q].rnum&&wa[p].key<wa[q].key)
     {
       s=q;
       q=ls[t]; /* q指示新的勝利者 */
       ls[t]=s;
     }
   ls[0]=q;
 }

 void Construct_Loser(LoserTree ls,WorkArea wa,FILE *fi)
 { /* 輸入w個(gè)記錄到內(nèi)存工作區(qū)wa,建得敗者樹(shù)ls,選出關(guān)鍵字最小的記錄并由s指示 */
   /* 其在wa中的位置。算法11.7 */
   int i;
   for(i=0;i<w;++i)
     wa[i].rnum=wa[i].key=ls[i]=0; /* 工作區(qū)初始化 */
   for(i=w-1;i>=0;--i)
   {
     fread(&wa[i].rec,sizeof(RedType),1,fi); /* 輸入一個(gè)記錄 */
     wa[i].key=wa[i].rec.key; /* 提取關(guān)鍵字 */
     wa[i].rnum=1; /* 其段號(hào)為＂1＂ */
     Select_MiniMax(ls,wa,i); /* 調(diào)整敗者 */
   }
 }

 void get_run(LoserTree ls,WorkArea wa,int rc,int *rmax,FILE *fi,FILE *fo)
 { /* 求得一個(gè)初始?xì)w并段，fi為輸入文件指針，fo為輸出文件指針。算法11.5 */
   int q;
   KeyType minimax;
   while(wa[ls[0]].rnum==rc) /* 選得的MINIMAX記錄屬當(dāng)前段時(shí) */
   {
     q=ls[0]; /* q指示MINIMAX記錄在wa中的位置 */
     minimax=wa[q].key;
     fwrite(&wa[q].rec,sizeof(RedType),1,fo); /* 將剛選得的MINIMAX記錄寫(xiě)入輸出文件 */
     fread(&wa[q].rec,sizeof(RedType),1,fi); /* 從輸入文件讀入下一記錄(改) */
     if(feof(fi))
     { /* 輸入文件結(jié)束，虛設(shè)記錄（屬＂rmax+1＂段） */
       wa[q].rnum=*rmax+1;
       wa[q].key=MAXKEY;
     }
     else
     { /* 輸入文件非空時(shí) */
       wa[q].key=wa[q].rec.key; /* 提取關(guān)鍵字 */
       if(wa[q].key<minimax)
       { /* 新讀入的記錄屬下一段 */
         *rmax=rc+1;
	 wa[q].rnum=*rmax;
       }
       else /* 新讀入的記錄屬當(dāng)前段 */
	 wa[q].rnum=rc;
     }
     Select_MiniMax(ls,wa,q); /* 選擇新的MINIMAX記錄 */
   }
 }

 void Replace_Selection(LoserTree ls,WorkArea wa,FILE *fi,FILE *fo)
 { /* 在敗者樹(shù)ls和內(nèi)存工作區(qū)wa上用置換－選擇排序求初始?xì)w并段，fi為輸入文件 */
   /* (只讀文件)指針,fo為輸出文件(只寫(xiě)文件)指針,兩個(gè)文件均已打開(kāi)。算法11.4 */
   int rc,rmax;
   RedType j;
   j.key=RUNEND_SYMBOL;
   Construct_Loser(ls,wa,fi); /* 初建敗者樹(shù) */
   rc=rmax=1; /* rc指示當(dāng)前生成的初始?xì)w并段的段號(hào)，rmax指示wa中關(guān)鍵字所屬初始?xì)w并段的最大段號(hào) */
   while(rc<=rmax) /* ＂rc=rmax+1＂標(biāo)志輸入文件的置換－選擇排序已完成 */
   {
     get_run(ls,wa,rc,&rmax,fi,fo); /* 求得一個(gè)初始?xì)w并段 */
     j.otherinfo=rc;
     fwrite(&j,sizeof(RedType),1,fo); /* 將段結(jié)束標(biāo)志寫(xiě)入輸出文件 */
     rc=wa[ls[0]].rnum; /* 設(shè)置下一段的段號(hào) */
   }
 }

 void print(RedType t)
 {
   printf("(%d,%d)",t.key,t.otherinfo);
 }

 void main()
 {
   RedType b,a[N]={{51,1},{49,2},{39,3},{46,4},{38,5},{29,6},{14,7},{61,8},{15,9},{30,10},{1,11},{48,12},{52,13},{3,14},{63,15},{27,16},{4,17},{13,18},{89,19},{24,20},{46,21},{58,22},{33,23},{76,24}};
   FILE *fi,*fo;
   LoserTree ls;
   WorkArea wa;
   int i,k,j=RUNEND_SYMBOL;
   char s[3],fname[4];
   fo=fopen("ori","wb"); /* 以寫(xiě)的方式打開(kāi)大文件ori */
   fwrite(a,sizeof(RedType),N,fo); /* 將數(shù)組a寫(xiě)入大文件ori */
   fclose(fo);
   fi=fopen("ori","rb"); /* 以讀的方式重新打開(kāi)大文件ori */
   printf("大文件的記錄為:\n");
   for(i=1;i<=N;i++)
   {
     fread(&b,sizeof(RedType),1,fi); /* 依次將大文件ori的數(shù)據(jù)讀入b */
     print(b); /* 輸出b的內(nèi)容 */
     if(i%M==0)
       printf("\n");
   }
   printf("\n");
   rewind(fi); /* 使fi的指針重新返回大文件ori的起始位置，以便重新讀入內(nèi)存，產(chǎn)生有序的子文件 */
   fo=fopen("out","wb"); /* 以寫(xiě)的方式打開(kāi)初始?xì)w并段文件out */
   Replace_Selection(ls,wa,fi,fo); /* 用置換－選擇排序求初始?xì)w并段 */
   fclose(fo);
   fclose(fi);
   fi=fopen("out","rb"); /* 以讀的方式重新打開(kāi)初始?xì)w并段文件out */
   printf("初始?xì)w并段文件的記錄為:\n");
   i=1;
   do
   {
     k=fread(&b,sizeof(RedType),1,fi); /* 依次將大文件out的數(shù)據(jù)讀入b */
     if(k==1)
     {
       print(b); /* 輸出b的內(nèi)容 */
       if(i++%M==0)
         printf("\n");
     }
   }while(k==1);
   printf("\n");
   rewind(fi); /* 使fi的指針重新返回大文件ori的起始位置，以便重新讀入內(nèi)存，產(chǎn)生有序的子文件 */
   k=0;
   while(!feof(fi)) /* 按段輸出初始?xì)w并段文件out */
   {
     itoa(k,s,10); /* 依次生成文件名f0,f1,… */
     strcpy(fname,"f");
     strcat(fname,s);
     fo=fopen(fname,"wb"); /* 依次以寫(xiě)的方式打開(kāi)文件f0,f1,… */
     do
     {
       i=fread(&b,sizeof(RedType),1,fi);
       if(i==1) /* fread()調(diào)用成功 */
       {
	 fwrite(&b,sizeof(RedType),1,fo); /* 將b寫(xiě)入文件f0,f1,… */
         if(b.key==j) /* 1個(gè)歸并段結(jié)束 */
         {
           k++;
           fclose(fo);
           break;
         }
       }
     }while(i==1);
   };
   fclose(fi);
   printf("共產(chǎn)生%d個(gè)初始?xì)w并段文件\n",k);
 }