查找實(shí)驗(yàn)報(bào)告

1、實(shí)驗(yàn)報(bào)告姓課程名稱：院（系專業(yè)/年級(jí)：實(shí)驗(yàn)四查找一、實(shí)驗(yàn)?zāi)康?.掌握順序表的查找方法，尤其是折半查找方法；2.掌握二叉排序樹(shù)的查找算法。二、實(shí)驗(yàn)預(yù)習(xí)內(nèi)容請(qǐng)?jiān)谏蠙C(jī)前認(rèn)真閱讀教材及實(shí)驗(yàn)指導(dǎo)書(shū)，并在以下空白處填寫(xiě)相應(yīng)的內(nèi)容。1.請(qǐng)寫(xiě)出簡(jiǎn)單順序查找算法。intseq_search(elementtypeA,intn,keytypex)i=n;A0.key=x;while(Ai.key=x)i-；returni;2.請(qǐng)寫(xiě)出有序表二分（折半）查找算法。(1)非遞歸算法intbin_search(elementtypeA,intn,keytypex)intmid,low=0,high=n-1;/初始化查找區(qū)

2、域while(low=high)mid=(low+high)/2;if(x=Amid.keyreturnmid;elseif(xhigh)return-1;/查找失敗elsemid=(low+high)/2;/求解中間元素的下標(biāo)if(x=Amid.key)returnmid;/查找成功elseif(xkeykey)insert(T-lchild,S);/插入到T的左子樹(shù)中elseinsert(T-rchild,S);/插入到T的右子樹(shù)中3）請(qǐng)寫(xiě)出二叉排序樹(shù)構(gòu)造的算法。voidcreate_bst(Bnode*&T);/通過(guò)插入結(jié)點(diǎn)構(gòu)造二叉排序樹(shù)的算法Bnode*u;elementtypex;T

3、=NULL;cinx;/初始化根指針并讀入第一個(gè)元素值While(x!=end_of_num)/x不是結(jié)束符時(shí)u=newBnode;u-data=x;/產(chǎn)生新結(jié)點(diǎn)并裝入數(shù)據(jù)u-lchild=NILL;u-rchild=NULL;/設(shè)置左、右孩子指針為空insert(T,u);/插入結(jié)點(diǎn)到二叉排序樹(shù)T中cinx;/讀入下一個(gè)元素的值）請(qǐng)寫(xiě)出二叉排序樹(shù)查找的算法。非遞歸算法：Bnode*bst_search(Bnode*T,keytypex)Bnode*P=T;/P指向根while(p!=NULL)if(x=p-key)returnp;/查找成功elseif(xkey=p-lchild);/到左子

4、樹(shù)中繼續(xù)查找elsep=p-rchild;/到右子樹(shù)中繼續(xù)查找returnp;/返回結(jié)果可能為空，也可能非空遞歸算法：Bnode*bst_search(Bnode*T,keytypex)if(T=NULL|t-key=x)returnT;/子樹(shù)為空或已經(jīng)找到時(shí)均可結(jié)束elseif(xkey)returnbst_search(T-lchild,x);/左子樹(shù)中查找的結(jié)果就是函數(shù)的結(jié)果elsereturnbst_search(T-rchild,x);/右子樹(shù)中查找的結(jié)果就是函數(shù)的結(jié)果三、上機(jī)實(shí)驗(yàn)1.實(shí)驗(yàn)內(nèi)容。1）建立一個(gè)順序表，用順序查找的方法對(duì)其實(shí)施查找；2）建立一個(gè)有序表，用折半查找的方法對(duì)其

5、實(shí)施查找；3）建立一個(gè)二叉排序樹(shù)，根據(jù)給定值對(duì)其實(shí)施查找；4）對(duì)同一組數(shù)據(jù)，試用三種方法查找某一相同數(shù)據(jù)，并嘗試進(jìn)行性能分析。2.實(shí)驗(yàn)源程序。(1)#include#include#definemax100intx;typedefstructintdatamax;intlistlen;seqlist;voidinitial_list(seqlist*L)L-listlen=0;voidlist_creat(seqlist*L)inti;L-listlen+;i=L-listlen;L-datai=x;intlast_search(seqlist*L)inti;i=L-listlen;L-dat

6、a0=x;while(L-datai!=x)i-;returni;intfirst_search(seqlist*L)inti,n;n=L-listlen;for(i=1;idatai=x)returni;return-1;intbin_search(seqlist*L)intmid,low=1,high=L-listlen;while(lowdatamid)returnmid;elseif(xdatamid)high=mid-1;elselow=mid+1;return-1;intmain(void)seqlist*L;L=(seqlist*)malloc(sizeof(seqlist);i

7、nta,b,c;initial_list(L);printf(你想創(chuàng)建有序的查找表(以-1結(jié)束):);scanf(%d,&x);while(x!=-1)list_creat(L);scanf(%d,&x);printf(請(qǐng)輸入你想查找的數(shù):);scanf(%d,&x);printf(順序查找-你所要找數(shù)的下標(biāo)號(hào):);a=first_search(L);if(a=-1)printf(沒(méi)有你所要查的數(shù)!);elseprintf(%d,a);printf(n);printf(倒序查找-你所要找數(shù)的下標(biāo)號(hào):);b=last_search(L);if(b=0)printf(沒(méi)有你所要查的數(shù)!);else

8、printf(%d,b);printf(n);printf(折半查找-你所要找數(shù)的下標(biāo)號(hào):);c=bin_search(L);if(c=-1)printf(沒(méi)有你所要查的數(shù)!);elseprintf(%d,c);printf(n);return0;(2)#include#include#includetypedefstructBTnodeintdata;structBTnode*lchild,*rchild;BTnode,*Bnode;voidinsert(Bnode&T,BnodeS)if(T=NULL)T=S;elseif(S-datadata)insert(T-lchild,S);els

9、einsert(T-rchild,S);voidcreate_bat(Bnode&T)Bnodeu;intx;T=NULL;printf(putanumber:);scanf(%d,&x);while(x!=-1)u=(BTnode*)malloc(sizeof(BTnode);u-data=x;u-lchild=NULL;u-rchild=NULL;insert(T,u);printf(putanumber:);scanf(%d,&x);Bnodebst_search(BnodeT,intx)if(T=NULL|T-data=x)returnT;elseif(T-data)x)returnbst_search(T-lchild,x);elsereturnbst_search(T-rchild,x);intmain()intx;BnodeT,p;printf(請(qǐng)先建立一棵二叉排序樹(shù):);printf(n);create_bat(T);printf(請(qǐng)輸入你要查找的數(shù)字:);scanf(%d,&x);p=bst_search(T,x);if(p!=NULL)printf(已找到你