algo11-2.cpp

高一凡的数据结构源码

 // algo11-2.cpp 通过置换－选择排序产生不等长的初始归并段文件
 #include"c1.h"
 typedef int InfoType; // 定义其它数据项的类型
 #include"c10-1.h" // 定义KeyType、RedType及SqList
 #define MAX_KEY INT_MAX
 #define RUNEND_SYMBOL INT_MAX
 #define w 6 // 内存工作区可容纳的记录个数
 #define M 10 // 设输出M个数据换行
 #define N 24 // 设大文件有N个数据

 typedef int LoserTree[w]; // 败者树是完全二叉树且不含叶子，可采用顺序存储结构
 typedef struct
 {
   RedType rec; // 记录
   KeyType key; // 从记录中抽取的关键字
   int rnum; // 所属归并段的段号
 }RedNode,WorkArea[w]; // 内存工作区，容量为w

 void Select_MiniMax(LoserTree ls,WorkArea wa,int q) // 算法11.6
 { // 从wa[q]起到败者树的根比较选择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个记录到内存工作区wa，建得败者树ls，选出关键字最小的记录并由s指示
   // 其在wa中的位置。算法11.7
   int i;
   for(i=0;i<w;++i)
     wa[i].rnum=wa[i].key=ls[i]=0; // 工作区初始化
   for(i=w-1;i>=0;--i)
   {
     fread(&wa[i].rec,sizeof(RedType),1,fi); // 输入一个记录
     wa[i].key=wa[i].rec.key; // 提取关键字
     wa[i].rnum=1; // 其段号为＂1＂
     Select_MiniMax(ls,wa,i); // 调整败者
   }
 }

 void get_run(LoserTree ls,WorkArea wa,int rc,int &rmax,FILE *fi,FILE *fo)
 { // 求得一个初始归并段，fi为输入文件指针，fo为输出文件指针。算法11.5
   int q;
   KeyType minimax;
   while(wa[ls[0]].rnum==rc) // 选得的MINIMAX记录属当前段时
   {
     q=ls[0]; // q指示MINIMAX记录在wa中的位置
     minimax=wa[q].key;
     fwrite(&wa[q].rec,sizeof(RedType),1,fo); // 将刚选得的MINIMAX记录写入输出文件
     fread(&wa[q].rec,sizeof(RedType),1,fi); // 从输入文件读入下一记录(改)
     if(feof(fi))
     { // 输入文件结束，虚设记录(属＂rmax+1＂段)
       wa[q].rnum=rmax+1;
       wa[q].key=MAX_KEY;
     }
     else
     { // 输入文件非空时
       wa[q].key=wa[q].rec.key; // 提取关键字
       if(wa[q].key<minimax)
       { // 新读入的记录属下一段
         rmax=rc+1;
	 wa[q].rnum=rmax;
       }
       else // 新读入的记录属当前段
	 wa[q].rnum=rc;
     }
     Select_MiniMax(ls,wa,q); // 选择新的MINIMAX记录
   }
 }

 void Replace_Selection(LoserTree ls,WorkArea wa,FILE *fi,FILE *fo)
 { // 在败者树ls和内存工作区wa上用置换－选择排序求初始归并段，fi为输入文件
   // (只读文件)指针，fo为输出文件(只写文件)指针，两个文件均已打开。算法11.4
   int rc,rmax;
   RedType j;
   j.key=RUNEND_SYMBOL;
   Construct_Loser(ls,wa,fi); // 初建败者树
   rc=rmax=1; // rc指示当前生成的初始归并段的段号，rmax指示wa中关键字所属初始归并段的最大段号
   while(rc<=rmax) // ＂rc=rmax+1＂标志输入文件的置换－选择排序已完成
   {
     get_run(ls,wa,rc,rmax,fi,fo); // 求得一个初始归并段
     j.otherinfo=rc;
     fwrite(&j,sizeof(RedType),1,fo); // 将段结束标志写入输出文件
     rc=wa[ls[0]].rnum; // 设置下一段的段号
   }
 }

 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"); // 以写的方式打开大文件ori
   fwrite(a,sizeof(RedType),N,fo); // 将数组a写入大文件ori
   fclose(fo);
   fi=fopen("ori","rb"); // 以读的方式重新打开大文件ori
   printf("大文件的记录为:\n");
   for(i=1;i<=N;i++)
   {
     fread(&b,sizeof(RedType),1,fi); // 依次将大文件ori的数据读入b
     print(b); // 输出b的内容
     if(i%M==0)
       printf("\n");
   }
   printf("\n");
   rewind(fi); // 使fi的指针重新返回大文件ori的起始位置，以便重新读入内存，产生有序的子文件
   fo=fopen("out","wb"); // 以写的方式打开初始归并段文件out
   Replace_Selection(ls,wa,fi,fo); // 用置换－选择排序求初始归并段
   fclose(fo);
   fclose(fi);
   fi=fopen("out","rb"); // 以读的方式重新打开初始归并段文件out
   printf("初始归并段文件的记录为:\n");
   i=1;
   do
   {
     k=fread(&b,sizeof(RedType),1,fi); // 依次将大文件out的数据读入b
     if(k==1)
     {
       print(b); // 输出b的内容
       if(i++%M==0)
	 printf("\n");
     }
   }while(k==1);
   printf("\n");
   rewind(fi); // 使fi的指针重新返回大文件ori的起始位置，以便重新读入内存，产生有序的子文件
   k=0;
   while(!feof(fi)) // 按段输出初始归并段文件out
   {
     itoa(k,s,10); // 依次生成文件名f0，f1，…
     strcpy(fname,"f");
     strcat(fname,s);
     fo=fopen(fname,"wb"); // 依次以写的方式打开文件f0，f1，…
     do
     {
       i=fread(&b,sizeof(RedType),1,fi);
       if(i==1) // fread()调用成功
       {
	 fwrite(&b,sizeof(RedType),1,fo); // 将b写入文件f0，f1，…
	 if(b.key==j) // 1个归并段结束
         {
           k++;
           fclose(fo);
           break;
         }
       }
     }while(i==1);
   };
   fclose(fi);
   printf("共产生%d个初始归并段文件\n",k);
 }