數(shù)據(jù)結(jié)構(gòu)——查找算法比較.doc

廣 西 大 學(xué) 實 驗 報 告 姓名_馬瑞良_學(xué)號_0807100333_計網(wǎng)_專業(yè)_083_班_2009_年_12_月_08_日實驗內(nèi)容 查找算法比較 指導(dǎo)教師 一、 實驗內(nèi)容對各種查找算法進(jìn)行比較二、實驗要求（1）任意輸入5組有序數(shù)據(jù)；（2）對順序查找、折半查找、分塊查找的查找次數(shù)進(jìn)行比較并輸出比較結(jié)果。三、所需主要儀器及現(xiàn)有套數(shù)：微機(jī) 臺軟件： 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分塊數(shù): 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請輸入數(shù)組元素: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查找次數(shù): 正向查找 sx0 次,反向查找 sx1 次,共 sx0+sx1 次nn;/折半查找k=efsrch(r,n,m,sx2);if(k=-1)cout查找失敗!n;else cout查找成功!n; cout位置: k+1endl; cout查找次數(shù): sx2 次nn;/分塊查找l=idxsrch(r,n,m,sx3,sx4);if(l=-1)cout查找失敗!n;else cout查找成功!n;cout位置: l+1endl;cout查找次數(shù): 調(diào)用索引表 s