binary.cpp

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

#include <stdlib.h>
#include <iostream.h>
#include <time.h>
#include "sqlist.h"
void main(void)
{ void  BinarySort(recordfile ,int ); //二分法插入排序
  int n, i;  time_t t;
  recordfile r;   
  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;
     }  
  BinarySort(r,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  BinarySort(recordfile r,int n )
 { int  i,l,u,m;   
   for(i=2;i<=n;i++)                          // 从第二个记录起逐个插入
      { r[0]=r[i]; l=1; u=i-1;                      // l 和 u 为二分查找的上下界
        while(l<=u){m=(l+u)/2;                   // 用二分查找寻找插入位置
                    if(r[0].key<r[m].key)u=m-1;  else l=m+1;
                   }//end_while
        for(m=i-1;m>=l;m--) r[m+1]=r[m];         // 记录后移
        r[l]=r[0];                                  // 将第i个记录插入
      } // end_for i
}