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

广 西 大 学 实 验 报 告 姓名_马瑞良_学号_0807100333_计网_专业_083_班_2009_年_12_月_08_日实验内容 查找算法比较 指导教师 一、 实验内容对各种查找算法进行比较二、实验要求（1）任意输入5组有序数据；（2）对顺序查找、折半查找、分块查找的查找次数进行比较并输出比较结果。三、所需主要仪器及现有套数：微机 台软件： visual C+四、程序源码：#include#includeusing namespace std;typedef int Key;typedef structKey key;Rec;typedef structint index;Key data;Index;templatevoid 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(ajamin)min=j;temp=ai;ai=amin;amin=temp;/正向顺序查找int srch0(Rec r,int n,Key k,int &m)cout顺序查找n;m=0;int i(0);while(m+,(ri.key!=k)&(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+,ri.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=rmid.key)return(mid);else if(krmid.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 Indexl;for(i=1;i=l;i+)indi.index=i*m-1;indi.data=ri*m-1.key;i=1;while(g+,il)if(indi.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=rmid.key)return(mid);else if(krmid.key)hig=mid-1;else low=mid+1;return(-1);void main()int n;int *a;coutn; a=new intn;int i,j,k,l,m,sx0,sx1,sx2,sx3,sx4;cout请输入数组元素:n;for(i=0;iai;px(a,n);Rec *r;r=new Recn;for(i=0;in;i+)ri.key=ai;for(i=0;in;i+)coutri.key ;coutendl;coutm;/顺序查找i=srch0(r,n,m,sx0);j=srch1(r,n,m,sx1); if(i=-1)cout查找失败!n;else cout查找成功!n;cout正向查出的位置: i+1endl反向查出的位置: j+1endl;cout查找次数: 正向查找 sx0 次,反向查找 sx1 次,共 sx0+sx1 次nn;/折半查找k=efsrch(r,n,m,sx2);if(k=-1)cout查找失败!n;else cout查找成功!n; cout位置: k+1endl; cout查找次数: sx2 次nn;/分块查找l=idxsrch(r,n,m,sx3,sx4);if(l=-1)cout查找失败!n;else cout查找成功!n;cout位置: l+1endl;cout查找次数: 调用索引表 s