k_way.c

K路归并算法

/*============================k路归并算法实现==========================*/

/*算法思想：任意输入一组文件记录，要求用k路归并算法将其归并到一起 */
/*且达到最优效益，即记录的移动次数最少，算法中采用最优归并模式，类似*/
/*哈夫曼树的构造，最后的根结点即最终的记录移动次数*/


#include<stdio.h>                /*头文件包含*/
#include<stdlib.h>

typedef struct filerec{          /*文件记录结点结构*/
     int  recnum;                /*文件中的记录数*/
     int  bianhao;               /*文件的编号*/
     struct filerec * next;      /*指向下一个结点的执指针*/
     }Filerec;

struct filerec * sort( struct filerec * Head )           /*排序函数*/
{
    struct filerec * temp1, * temp2;
    int temp,tempbianhao;
    for( temp1 = Head -> next; temp1 != NULL; temp1 = temp1 -> next)       /*利用冒泡法对记录进行排序并返回头指针*/
       for( temp2 = temp1 -> next; temp2 != NULL; temp2 = temp2 -> next)
       {
          if ( (temp1 -> recnum) > (temp2 -> recnum) )   /*如果前一个结点的记录数大于后一个结点的文件记录数*/
          {                                              /*则交换它们的文件记录数和文件的编号*/
              temp = temp1 -> recnum;
              tempbianhao = temp1 -> bianhao;
              temp1 -> recnum = temp2 -> recnum;
              temp1 -> bianhao = temp2 -> bianhao;
              temp2 -> recnum = temp;
              temp2 -> bianhao = tempbianhao;
          }
       }
    return(Head);                                       /*返回文件序列头指针*/
}

void merge(struct filerec * head, int n, int k)
{                                                      /*totalrecords记录一次归并的文件记录总数,fictitious为需要加的虚结点数*/
    int totalrecords=0,fictitious;
    int times,t,i,j = 1,m=0;                         /*times记录需进行归并的次数，m为某次归并操作中归并的文件数，j为第j次归并*/
    int conjion,conjion1;                                     /*合成新文件的编号，在原文件之后的编号*/
    int filenum[100];                                      /*记录每次归并的文件编号*/
    struct filerec *head1,*fic, *mergenode,*emp,*rm;
    conjion = n + 1;
    if( k == 1 )                                       /*当为1路归并时没必要加虚结点，归并的次数即文件总数*/
    {
       fictitious = 0;
       times = n;
    }
    else if ( k == 2 )                                 /*当结点数为2时也没必要加虚结点，归并次数即文件总数减一*/
    {
       fictitious = 0;
       times = n - 1;
    }
    else                                              /*结点数大于2时要考虑需要加的结点数以及归并的次数*/
    {
      t = (n-1)%(k-1);                                /*判断是否需要加虚结点的标志，为0不需要加虚结点，否则要加虚结点*/
      if( t )
      {
        fictitious = (( k - 1) - t);                    /*加入的虚结点数*/                                               /*加入虚结点后需要归并的次数*/
        times = ( ( n - 1 )/( k - 1 ) ) + 1;
      }
      else
      {
        fictitious = 0;
        times =  ( n - 1 )/( k - 1 );                 /*不加虚结点时要归并的次数*/
      }
     }
     printf("\nIt has to add %d virtual nodes here.\n",fictitious);
    if( k >= n )                                      /*当归并的间隔数不小于文件总数时不需要进行归并，即为原序列*/
    {
       printf(" The interval is too large, there sis no necessary to do complicated process.\nJust merge all the records at one deed. ");
       for ( head1 = head; head1 != NULL;head1 = head1 -> next)    /*计算总的文件记录数并输出结果*/
          totalrecords += head1 -> recnum;
       printf(" The result is:  %d\n",totalrecords );
    }
    else                                              /*当归并的间隔小于文件的总数时考虑的情况*/
    {
       for( i = 0; i < fictitious; i++ )              /*加入计算出来的一定数量的虚结点到序列的首部*/
       {
          fic =  (struct filerec *) malloc (sizeof(struct filerec));
          fic -> recnum = 0;
          fic -> bianhao = -1;
          fic -> next = head -> next;
          head -> next = fic;
       }

       while(times)                                  /*完成所需的一定次数的归并操作*/
       {
          head1 = head -> next;
          if(j == 1)                                 /*第一次归并情况单独考虑*/
          {
            for( i= 0; i < k; i++ )                  /*掠过序列前面的虚结点*/
            {
              if( ( head1 -> bianhao ) > 0 )
              {
                 filenum[m] = head1 -> bianhao;    /*遇到非虚结点时将其编号存入数组，同时合计文件记录的总数用totalrecords记录*/
                 m++;
                 totalrecords += head1 -> recnum;
              }
              rm = head1;                          /*头指针后移，同时把归并过的文件结点释放*/
              head1 = head1 -> next;
              free( rm );
            }
          }
          else                                    /*第二，三，四......次归并的情况*/
          {
            for( i= 0; i < k; i++ )
           {
                filenum[m] = head1 -> bianhao;   /*将结点时将其编号存入数组，同时合计文件记录的总数用totalrecords记录*/
                m++;
                totalrecords += head1 -> recnum;
                rm = head1;                      /*头指针后移，同时把归并过的文件结点释放*/
                head1 = head1 -> next;
                free( rm );
           }
          }
          printf("Process %d :",j);             /*将第J次归并的情况输出*/
          printf("\n Files merged in this process:");
          for( i = 0; i < m; i++ )              /*输出第J次归并操作中归并入的文件的编号*/
             printf( " %3d ",filenum[i] );
          printf("-->merge to file %d",conjion);
          mergenode =  (struct filerec *) malloc (sizeof(struct filerec));  /*将归并的文件用新建的文件结点统计记录*/
          mergenode -> recnum = totalrecords;        /*记录中将归并的文件的记录总数用recnum记录，将新结点的编号置成0 */
          mergenode -> bianhao = conjion;            /*表示该新结点是树型结构的内部结点*/
          mergenode -> next = head1;                 /*将新结点加入文件序列中*/
          head -> next = mergenode;
          m = 0;                                    /*记录文件编号的数组记录重置*/
          conjion1 = totalrecords;
          totalrecords = 0;                         /*归并文件记录数的重置*/
          times--;                                  /*归并次数减一*/
          j++;                                      /*归并记录数加1*/
          conjion++;                                /*下一个合成文件的编号*/
          head = sort( head );                      /*调用排序函数对新的序列重新排序*/
          printf("\n");
          printf("File NO.");                         
          for( emp = head->next ; emp != NULL; emp = emp -> next)      /*输出剩余的文件记录编号*/
          {
            printf("%5d",emp->bianhao);
          }
          printf("\nSize    ");                                       /*输出各文件对应的文件记录数*/
          for( emp = head->next ; emp != NULL; emp = emp -> next)
          {
            printf("%5d",emp->recnum);
          }
          printf("\n\n");
          getch();
       }
      printf("\nThe result is :%d",conjion1);
    }
}

void main()
{
    int  totalnumber,k,re,i,j;                               /*total记录要输入的总的文件数，k为归并的间隔数*/
    struct filerec * head, *recinf, *emp;
    emp = (struct filerec *) malloc (sizeof(struct filerec));/*创建一个空结点便于后面的操作，其后继指针为空，记录数置成最大*/
    emp -> next = NULL;                                      /*编号置成0，将头指针指向它*/
    emp -> recnum = 65533;
    emp -> bianhao = 0;
    head  = emp;
    printf( "\n Input the total number of files records: "); /*输入要进行归并的总文件数，用totalnumber记录*/
    scanf( "%d", &totalnumber );
    printf( " Input the mergesize(k): ");                       /*输入归并的间隔数，用k标志*/
    scanf( "%d", &k );
    printf( " Now input the size of each file:\n" );         /*依次输入各文件的记录总数*/
    for( i = 1;i <=totalnumber; i++)
    {
       recinf = (struct filerec *) malloc (sizeof(struct filerec));   /*创建文件结点记录其属性参数*/
       printf("The size of file %d is :",i);                          /*输入该文件的记录数*/
       scanf( "%d",&( recinf -> recnum ));
       recinf -> bianhao = i;                                         /*记录文件的编号*/
       recinf -> next = emp -> next;                                  /*链入文件序列*/
       emp -> next = recinf;
       emp = recinf;
    }
    head = sort( head );                                              /*调用排序函数进行排序*/
    merge(head,totalnumber,k);                                        /*调用归并函数进行归并操作*/
    getch();
}