merge.cpp

这是本人精心搜集的关于常用图论算法的一套源码

#include <stdlib.h>
#include <iostream.h>
#include <time.h>
#include "sqlist.h"
void main(void)
{ void mergesort(recordfile r, recordfile r1,int n);   // //2-路归并排序
  int n,i;  time_t t;
  recordfile r,r1;
  cout<<" Please input sorted elements number=? ";  cin>>n; 
  srand((unsigned)time(&t));
  for(i=1;i<=n; i++) r[i].key=rand() % 83 +10;
  cout<<" origil array is\n";
  for(i=1;i<=n; i++)
     { cout<<r[i].key<<"  ";
       if(i%10==0)cout<<endl;
     }  
  mergesort(r,r1,n);
  cout<<"\n sort array is\n";
  for(i=1;i<=n; i++)
     { cout<<r[i].key<<"  ";
       if(i%10==0)cout<<endl;
     }  
  cout<<endl;
}

void merge(recordfile r,recordfile r1,int s,int m,int t)   // 两相邻文件归并过程
// 将有序子文件r[s]～r[m] 及r[m+1]～r[t] 合并成一个有序文件存入r1[s]～r1[t]
{ int  i=s,j=m+1,k=s-1;
  while((i<=m) && j<=t)
        if (r[i].key<=r[j].key) r1[++k]=r[i++];
         else   r1[++k]=r[j++];
  if(i>m) for (; j<=t; j++)  r1[++k]=r[j];
   else   for (; i<=m;i++)  r1[++k]=r[i];
}
void  mergepass(recordfile r, recordfile r1,int n,int l)    // 一趟归并过程
{ int  p=1;
 while(n-p+1>=2*l)
   { merge(r,r1,p,p+l-1,p+2*l-1);     // 将 r 中长度为 l 的两个子文件合并
       // 第 1 个文件下标从 p 到 (p+l-1),第 2 个文件下标从 p+l 到 p+2*l-1
     p+=2*l;                         // p向后移2*l，准备下一次合并
   } // end_while
if(n-p+1>l)merge(r,r1,p,p+l-1,n);    //一个长度为 l 的文件与一个长度小于 l 的文件合并
 else for(; p<=n; p++) r1[p]=r[p];  //只剩下一个长度不大于 l  的子文件将其复抄到r1
}
void mergesort(recordfile r, recordfile r1,int n)   // 归并排序
{ int   l=1;
  while(l<n){ mergepass(r,r1,n, l); l*=2;             // 从r归并至r1
              mergepass(r1,r,n, l); l*=2;             // 从r1归并至r
            }
}