数据结构——查找算法比较.docVIP

姓名__马瑞良_______________学号___0807100333_______ ____计网_______专业__083______班 ______2009______年____12_____月_____08____日 实验内容 查找算法比较 指导教师 实验内容 对各种查找算法进行比较 二、实验要求 （1）任意输入5组有序数据； （2）对顺序查找、折半查找、分块查找的查找次数进行比较并输出比较结果。 三、所需主要仪器及现有套数： 微机 台 软件： visual C++ 四、程序源码： #includeiostream #includecmath using namespace std; typedef int Key; typedef struct { Key key; } Rec; typedef struct { int index; Key data; } Index; templatetypename Telem void px(Telem a[],int n) { int min,i,j; Telem temp; for(i=0;in-1;i++) { min=i; for(j=i+1;jn;j++) if(a[j]a[min]) min=j; temp=a[i]; a[i]=a[min]; a[min]=temp; } }; //正向顺序查找 int srch0(Rec r[],int n,Key k,int m) { cout顺序查找\n; m=0; int i(0); while(m++,(r[i].key!=k)(i=n)) i++; if(in) return(-1); else return(i); }; //逆向顺序查找 int srch1(Rec r[],int n,Key k,int m) { m=0; int i(n); r[-1].key=k; while(m++,r[i].key!=k) i--; return(i); }; //折半查找 int efsrch(Rec r[],int n,Key k,int m) { m=0; cout二分查找\n; int low,hig,mid; low=0; hig=n; while(m++,low=hig) { mid=(low+hig)/2; if(k==r[mid].key) return(mid); else if(kr[mid].key) hig=mid-1; else low=mid+1; } return(-1); }; //分块查找(二分查找) int idxsrch(Rec r[],int n,Key k,int g,int h) { cout分块查找\n; g=0; h=0; int i; int l=(int)sqrt(n); int m=(n+l-1)/l; cout分块数: lendl; Index *ind; ind=new Index[l]; for(i=1;i=l;i++) { ind[i].index=i*m-1; ind[i].data=r[i*m-1].key; } i=1; while(g++,il) { if(ind[i].datak) i++; else break; } int low,hig,mid; low=i*m-m; hig=i*m-1; while(h++,low=hig) { mid=(low+hig)/2; if(k==r[mid].key) return(mid); else if(kr[mid].key) hig=mid-1; else low=mid+1; } return(-1); } void main() { int n; int *a; cout请输入数组长度: ; cinn; a=new int[n]; int i,j,k,l,m,sx0,sx1,sx2,sx3,sx4; cout请输入数组元素:\n; for(i=0;in;i++) cina[i]; pxint(a,n); Rec *r; r=new Rec[n]; for(i=0;in;i++) r[i].key=a[i]; for(i=0;in;i++) coutr[i].key ; coutendl; cout请输入要查询的数字: ; ci