查找算法比较.docx

数据结构C+实验报告广西大学计电学院计网103班数据结构实验报告（四）姓名梁田班级计网103班学号1007300340指导教师李静滨日期2011/12/26实验名称查找算法比较实验目的：熟练掌握各种静态查找表的查找方法（顺序查找法、折半查找法、分块查找）的操作及实现。实验内容：对各种查找算法进行比较。要求：（1）任意输入1组50个有序数据；（2）对顺序查找、折半查找、分块查找的查找次数进行比较并输出比较结果。实验环境与设备： PC Windows7系统 Microsoft Visual C+ 6.0源程序代码：#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);elsereturn(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;elselow=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+;elsebreak;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;elselow=mid+1;return(-1);void main()int n,num;int *a;coutn; a=new intn;int i,j,k,l,m,sx0,sx1,sx2,sx3,sx4;cout请输入n个数组元素: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 ;num+;if(num%10=0)coutendl;coutendl;coutm;coutendl;/顺序查找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;elsecout查找成功!n;cout位置: l+1endlendl;cout查找次数: 调用索引表 sx3 次,调用顺序表 sx4 次,共 sx3+sx4 次nn;运行结果： 查找成功： 查找失败：实验分析：1、 顺序查找过程：从表中的最后一个记录开始，逐个进行记录的关键字与给定值进行比较，若某个记录的关键字与给定值相等，则查找成功，找到所查的记录；反之，若直到第一个记录，其关键字和给定值比较都不相等，则表明表中没有所查的记录，查找失败。2、 折半查找也称二分查找，其算法思路：首先，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。3、 分块查找又称索引顺序查找，它是顺序查找的一种改进方法。其方法描述：将n个数据元素按块有序划分为m块（m n）。每一块中的结点不必有序，但块与块之间必须按块有序；即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字；而第2块中任一元素又都必须小于第