查找實驗報告.doc

實驗報告 姓 課程名稱： 院（系 專業(yè)/年級：實驗四 查找一、 實驗目的1. 掌握順序表的查找方法，尤其是折半查找方法；2. 掌握二叉排序樹的查找算法。二、 實驗預習內容請在上機前認真閱讀教材及實驗指導書，并在以下空白處填寫相應的內容。1. 請寫出簡單順序查找算法。int seq_search(elementtype A,int n, keytype x) i=n;A0.key=x; while(Ai.key=x) i-； return i;2. 請寫出有序表二分（折半）查找算法。(1) 非遞歸算法int bin_search(elementtype A,int n,keytype x) int mid,low=0,high=n-1; /初始化查找區(qū)域 while(low=high) mid=(low+high)/2; if(x=Amid.key return mid; else if(xhigh) return -1;/查找失敗 else mid=(low+high)/2;/求解中間元素的下標 if( x=Amid.key ) return mid;/查找成功 else if( xkeykey) insert (T-lchild,S); /插入到T的左子樹中 else insert(T-rchild,S); /插入到T的右子樹中 3）請寫出二叉排序樹構造的算法。void create_bst(Bnode *&T); /通過插入結點構造二叉排序樹的算法 Bnode * u;elementtype x; T=NULL;cinx; /初始化根指針并讀入第一個元素值 While (x!=end_of_num) /x不是結束符時 u=new Bnode; u-data=x; /產(chǎn)生新結點并裝入數(shù)據(jù) u-lchild=NILL;u-rchild=NULL; /設置左、右孩子指針為空 insert (T,u); /插入結點到二叉排序樹T中 cinx; /讀入下一個元素的值 4） 請寫出二叉排序樹查找的算法。 非遞歸算法：Bnode * bst_search(Bnode * T,keytype x) Bnode * P=T; /P指向根 while (p!=NULL) if( x=p-key) return p; /查找成功 else if( xkey=p-lchild); /到左子樹中繼續(xù)查找 else p=p-rchild; /到右子樹中繼續(xù)查找 return p; /返回結果可能為空，也可能非空遞歸算法：Bnode * bst_search(Bnode * T,keytype x) if (T=NULL | t-key=x) return T; /子樹為空或已經(jīng)找到時均可結束 else if(xkey) return bst_search(T-lchild, x); /左子樹中查找的結果就是函數(shù)的結果 else return bst_search(T-rchild, x); /右子樹中查找的結果就是函數(shù)的結果三、 上機實驗1. 實驗內容。1）建立一個順序表，用順序查找的方法對其實施查找；2）建立一個有序表，用折半查找的方法對其實施查找；3）建立一個二叉排序樹，根據(jù)給定值對其實施查找；4） 對同一組數(shù)據(jù)，試用三種方法查找某一相同數(shù)據(jù)，并嘗試進行性能分析。2. 實驗源程序。(1)#include #include #define max 100int x;typedef structint datamax;int listlen;seqlist;void initial_list(seqlist *L)L-listlen=0;void list_creat(seqlist *L)int i;L-listlen+;i=L-listlen;L-datai=x;int last_search(seqlist *L)int i;i=L-listlen;L-data0=x;while(L-datai!=x)i-;return i;int first_search(seqlist *L)int i,n;n=L-listlen;for(i=1;idatai=x)return i;return -1;int bin_search(seqlist *L)int mid,low=1,high=L-listlen;while(lowdatamid)return mid;else if(xdatamid)high=mid-1;elselow=mid+1;return -1;int main(void)seqlist *L;L=(seqlist*)malloc(sizeof(seqlist);int a,b,c;initial_list(L);printf(你想創(chuàng)建有序的查找表(以-1結束):);scanf(%d,&x);while(x!=-1)list_creat(L); scanf(%d,&x); printf(請輸入你想查找的數(shù):);scanf(%d,&x); printf(順序查找-你所要找數(shù)的下標號:);a=first_search(L);if(a=-1)printf(沒有你所要查的數(shù)!);elseprintf(%d,a); printf(n); printf(倒序查找-你所要找數(shù)的下標號:); b=last_search(L); if(b=0)printf(沒有你所要查的數(shù)!);elseprintf(%d,b); printf(n); printf(折半查找-你所要找數(shù)的下標號:); c=bin_search(L); if(c=-1)printf(沒有你所要查的數(shù)!);elseprintf(%d,c); printf(n);return 0;(2)#include#include#includetypedef struct BTnodeint data;struct BTnode *lchild,*rchild; BTnode,*Bnode;void insert(Bnode &T,Bnode S)if(T=NULL)T=S;else if(S-datadata)insert(T-lchild,S); else insert(T-rchild,S);void create_bat(Bnode &T)Bnode u;int x;T=NULL;printf(put a number:);scanf(%d,&x);while(x!=-1)u=(BTnode*)malloc(sizeof(BTnode);u-data=x;u-lchild=NULL;u-rchild=NULL;insert(T,u); printf(put a number:); scanf(%d,&x);Bnode bst_search(Bnode T,int x)if(T=NULL|T-data=x)return T;else if(T-data)x) return bst_search(T-lchild,x);elsereturn bst_search(T-rchild,x); int main()int x;Bnode T,p;printf(請先建立一棵二叉排序樹:);printf(n);create_bat(T);printf(請輸入你要查找的數(shù)字:); scanf(%d,&x);p=bst_search(T,x);if(p!=NULL)prin