search.cpp

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

#include <stdlib.h>
#include <time.h>
#include "Search.h"
void visit(Record &);

void main()
{ Ordered_list L; int n, i, j, pos;  Record x;  char answer;
  time_t t;   srand((unsigned)time(&t)); //初始化随时间变化的随机数种子
  cout<<" Please enter List Size=?(<=30) ";  cin>>n; 
  cout<<" Generate Random sequence is: \n{ ";
  for(i=0; i<n; )  // 产生n个互不相等的整数,插入表,使有序             
     { j = rand() % 100;  
       if(binary_search(L, j,pos)==not_present)  // 产生的整数不在表中，插入
         { x=j;  L.insert(x); i++; cout<<j<<' '; } 
     }   
  cout<<"}\n Ordered_list L is:\n { ";   L.traverse(visit);  cout<<"}\n";
  do { cout<<"\n Please enter search key :  ";   cin>>i; 
       Key::comparisons = 0; 
       if(binary_search(L, i,pos)==success)  // 用二分查找
          cout<<"\n Recorg Position ="<<pos<<"\t binary_search comparisons="<<Key::comparisons;
        else cout<<"\n Recorg not present"<<"\t  binary_search comparisons="<<Key::comparisons;     
       if(sequential_search(L, i,pos)==success)  // 用顺序查找
          cout<<"\n Recorg Position ="<<pos<<"\t sequential_search comparisons="<<pos+1;
        else cout<<"\n Recorg not present"<<"\t  sequential_search comparisons="<<pos;     
       cout<<"\n\n Continue search (y/n) ? ";   cin>>answer;
     }while(answer=='y' || answer=='Y');
  do{  cout<<"\n Please enter replaced position  key :  ";   cin>>i>>j; x=j;
       if(L.replace(i,x)==success)
         { cout<<" Ordered_list L is:\n { ";   L.traverse(visit);  cout<<"}\n"; }
        else cout<<" fail: position error!\n";     
       cout<<"\n\n Continue replace (y/n) ? ";   cin>>answer;
     }while(answer=='y' || answer=='Y');  
 cout<<endl;
} 

void visit(Record &r)
 { cout<<r.the_key( )<<' '; }