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

1、實(shí)驗(yàn)報(bào)告姓課程名稱：院(系專業(yè)/年級(jí)：實(shí)驗(yàn)四一一查找一、實(shí)驗(yàn)?zāi)康?. 掌握順序表的查找方法，尤其是折半查找方法；2. 掌握二叉排序樹的查找算法。二、實(shí)驗(yàn)預(yù)習(xí)內(nèi)容請(qǐng)?jiān)谏蠙C(jī)前認(rèn)真閱讀教材及實(shí)驗(yàn)指導(dǎo)書，并在以下空白處填寫相應(yīng)的內(nèi)容。1. 請(qǐng)寫出簡單順序查找算法。int seq_search(eleme nttype A,i nt n, keytype x) _i=n ;AO.key=x;while(Ai.key=x) i-；return i;2. 請(qǐng)寫出有序表二分(折半)查找算法。(1)非遞歸算法int bin _search(eleme nttype A,i nt n ,keytype x) in

2、t 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;求解中間元素的下標(biāo)if( x=Amid.key ) return mid;/查找成功else if( xkeykey)insert (T-lchild,S);插入到T的左子樹中else insert(T-rchild,S);插入到 T 的右子樹中3) 請(qǐng)寫出二叉排序樹構(gòu)造的算法。void create_bst(B nod

3、e *&T);通過插入結(jié)點(diǎn)構(gòu)造二叉排序樹的算法Bnode * u;eleme nttype x;T=NULL;c in x;/初始化根指針并讀入第一個(gè)元素值While (x!=e nd_of_ num)/x不是結(jié)束符時(shí) u=new Bno de; u-data=x;產(chǎn)生新結(jié)點(diǎn)并裝入數(shù)據(jù)u-lchild=NILL;u-rchild=NULL;設(shè)置左、右孩子指針為空insert (T,u);插入結(jié)點(diǎn)到二叉排序樹T中cin x;/讀入下一個(gè)元素的值4) 請(qǐng)寫出二叉排序樹查找的算法。 非遞歸算法：Bnode * bst_search(B node * T,keytype x) Bnode * P=T;

4、while (p!=NULL)P指向根if( x=p-key) retur n p;查找成功else if( xkey=p-lchild);/ 到左子樹中繼續(xù)查找else p=p-rchild;/到右子樹中繼續(xù)查找return p;/返回結(jié)果可能為空，也可能非空遞歸算法：Bnode * bst_search(B node * T,keytype x)if (T=NULL | t-key=x)return T;/子樹為空或已經(jīng)找到時(shí)均可結(jié)束else if(xkey)return bst_search(T-lchild, x);左子樹中查找的結(jié)果就是函數(shù)的結(jié)果else return bst_sea

5、rch(T-rchild, x);右子樹中查找的結(jié)果就是函數(shù)的結(jié)果三、上機(jī)實(shí)驗(yàn)1. 實(shí)驗(yàn)內(nèi)容。1）建立一個(gè)順序表，用順序查找的方法對(duì)其實(shí)施查找；2）建立一個(gè)有序表，用折半查找的方法對(duì)其實(shí)施查找；3）建立一個(gè)二叉排序樹，根據(jù)給定值對(duì)其實(shí)施查找；4）對(duì)同一組數(shù)據(jù)，試用三種方法查找某一相同數(shù)據(jù)，并嘗試進(jìn)行性能分析2. 實(shí)驗(yàn)源程序。(1) #in clude #in clude #defi ne max 100int x;typedef structint datamax;int listle n;seqlist;void in itial_list(seqlist *L)L-listle n=0;v

6、oid list_creat(seqlist *L)int i;L-listle n+;i=L-listle n;L-datai=x;in t last_search(seqlist *L)int i;i=L-listle n;L-dataO=x;while(L-datai!=x)i-;return i;int first_search(seqlist *L)int i,n;n=L-listle n;for(i=1;idatai=x)return i;return -1;int bin _search(seqlist *L)int mid,low=1,high=L-listle n; whil

7、e(lowdatamid) return mid;else if(xdatamid) high=mid-1;elselow=mid+1;return -1;int main(v oid)seqlist *L;L=(seqlist*)malloc(sizeof(seqlist);int a,b,c;ini tial_list(L);printf(你想創(chuàng)建有序的查找表(以-1結(jié)束):); sca nf(%d, &x);while(x!=-1)list_creat(L);scan f(%d, &x);printf(請(qǐng)輸入你想查找的數(shù)：)；sea nf(%d, &x);printf(順序查找-你所要找

8、數(shù)的下標(biāo)號(hào)：);a=first_search(L);if(a=-1)printf(沒有你所要查的數(shù)!);elseprin tf(%d,a);prin tf(n);printf(倒序查找-你所要找數(shù)的下標(biāo)號(hào)：);b=last_search(L);if(b=0)printf(沒有你所要查的數(shù)!);elseprin tf(%d,b);prin tf(n);printf(折半查找-你所要找數(shù)的下標(biāo)號(hào)：);c=b in search(L);if(c=-1)printf(沒有你所要查的數(shù)!);elseprin tf(%d,c);prin tf(n);return 0;#i nclude#i ncludev

9、stri ng.h#i ncludetypedef struct BTnodeint data;struct BTnode *lchild,*rchild; BT node,*B node;void in sert(B node & T,B node S) if(T=NULL)T=S;else if(S-datadata)in sert(T-lchild,S);else in sert(T-rchild,S);void create_bat(B node &T)Bnode u;int x;T=NULL;prin tf(put a nu mber:);sca nf(%d, &x);while(x

10、!=-1)u=(BT no de*)malloc(sizeof(BT no de); u-data=x;u-lchild=NULL;u-rchild=NULL;in sert(T,u);prin tf(put a nu mber:);sca nf(%d, &x);Bnode bst_search(B node T,i nt 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 mai n()int x;Bnode T,p

11、;printf(請(qǐng)先建立一棵二叉排序樹:);prin tf(n);create_bat(T);printf(請(qǐng)輸入你要查找的數(shù)字:);sca nf(%d, &x);p=bst_search(T,x);if(p!=NULL)printf(已找到你要查找的數(shù)!);elseprintf(對(duì)不起！沒有你要查找的數(shù)!);prin tf(n);return 0;3.實(shí)驗(yàn)結(jié)果* C:U sersstuDes kopDebugshu nxu bi ao.exeMS3回一二|=數(shù)數(shù)數(shù) 查查查 要要要 .1 1 1. 有有有:1沒沒沒 VW- * -Z 束 號(hào)號(hào)號(hào) T 下卡ue lrt 環(huán)48數(shù)釵隸nt EK爛要要要 1一 Futtkn t JT査 ke 有 想-一一 y 建 g我戎an 創(chuàng) 入杳香查容 你沙時(shí)l-lwlpr* C:Use rsskto pDf b uge rchhu.exe=1 回2S贋先建立一棵二叉排序桝=wit d nurtbcr：45l)ut a nunbe