數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)三：BST動態(tài)查找表

1、hunan universitybst實(shí)現(xiàn)動態(tài)查找表課程實(shí)習(xí)報(bào)告題學(xué)生姓名:學(xué)生學(xué)號: 專業(yè)班級：指導(dǎo)老師：李曉鴻 完成日期：2015 11 21一、需求分析1、程序任務(wù)：本程序是利用二義查找樹（bst）來實(shí)現(xiàn)；二義樹使用鏈?zhǔn)浇Y(jié)構(gòu)（二義鏈表）實(shí)現(xiàn), 本程序要實(shí)現(xiàn)bst的構(gòu)建，查找bst樹中元索中兩個(gè)功能。2、輸入形式：輸入整數(shù)n/bst的節(jié)點(diǎn)個(gè)數(shù)no輸入n個(gè)數(shù)，其取值范圍為（），216）,對非法輸入做處理。3、輸出形式：若查找成功 整數(shù)m （次數(shù)）/返回成功和查找時(shí)比較的次數(shù) 若杳找不成功幣數(shù)m （次數(shù)）/返回不成功和杳找時(shí)比較的次數(shù) 若輸入錯(cuò)誤“輸入了無效的元素”4、測試數(shù)據(jù)：正常的輸入10

2、/bst的節(jié)點(diǎn)個(gè)數(shù)50 1 3 2 78 65 100 59 43 18 /10 個(gè)數(shù)據(jù)輸入：50輸出：查找成功，查找次數(shù)1輸入:1輸出：查找成功，查找次數(shù)6輸入：3輸出：查找成功，查找次數(shù)4輸入：100輸出：査找成功，查找次數(shù)5輸入:19輸出：杏找失敗.只有左子樹的情況10bst的節(jié)點(diǎn)個(gè)數(shù)100 1 12 35 43 95 54 82 78 93 /i0 個(gè)數(shù)據(jù)輸入：1輸出：查找成功，查找次數(shù)1輸入：12輸岀：杏找成功，杏找次數(shù)6輸入：35查找成功，查找次數(shù)4輸入：95輸出：查找成功，查找次數(shù)5輸入:19輸出：查找失敗 .錯(cuò)誤的節(jié)點(diǎn)數(shù)輸入-2/bst的節(jié)點(diǎn)個(gè)數(shù)輸出：錯(cuò)謀的結(jié)點(diǎn)數(shù)輸入 .錯(cuò)誤的

3、結(jié)點(diǎn)值的輸入(字母)10/bst的結(jié)點(diǎn)個(gè)數(shù)lq 2345678910 個(gè)數(shù)據(jù)輸出：無效的結(jié)點(diǎn)輸入 .錯(cuò)誤的結(jié)點(diǎn)值的輸入(負(fù)數(shù))10/bst的結(jié)點(diǎn)個(gè)數(shù)1 -2 234567 8910 個(gè)數(shù)據(jù)輸出：無效的結(jié)點(diǎn)輸入二叉樹中任意結(jié)點(diǎn)的值大于左節(jié)點(diǎn)的值，小于右節(jié)點(diǎn)的值，滿足bst樹的性質(zhì)，所以 用bst樹來實(shí)現(xiàn)。二. 概要設(shè)計(jì)1抽象數(shù)據(jù)類型二叉樹中任意結(jié)點(diǎn)的值人于左節(jié)點(diǎn)的值，小于右節(jié)點(diǎn)的值，滿足bst樹的性質(zhì)， 同時(shí)本題在建樹時(shí)需要大量的插入操作，運(yùn)用鏈?zhǔn)浇Y(jié)構(gòu)比較方便，所以用鏈?zhǔn)浇Y(jié)構(gòu)的二 叉樹來滿足bst樹的構(gòu)建。2.adt.二叉樹的adt：數(shù)據(jù)對象d： d是binnode類的數(shù)據(jù)元索的集合數(shù)據(jù)關(guān)系r：

4、若d為空集，則稱為空樹。否則：(1) 在d中存在唯一的稱為根的數(shù)據(jù)元素root；(2) 當(dāng)n>l時(shí),其余結(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的有限集t1,t2,tm,其 中每一棵了集本身又是一棵符合本定義的樹，稱為根root的子樹?；静僮鳎篵ool initbst(bst *b) /初始化二叉樹bool initbstnode(bstnode * &n)初始化節(jié)點(diǎn)bool clearbst(bstnode * &n) /銷毀 bst結(jié)點(diǎn)的adt數(shù)據(jù)對象：包含結(jié)點(diǎn)的值，同時(shí)包含結(jié)點(diǎn)的左右指針數(shù)據(jù)關(guān)系：每個(gè)結(jié)點(diǎn)都有各自的值若結(jié)點(diǎn)左右指針為空，則該節(jié)點(diǎn)稱為葉子結(jié)點(diǎn)基本操作：

5、結(jié)點(diǎn)的初始化binnodeptr() lc=rc=nullbinnodeptr(elem e,binnodeptr* l=null;binnodeptr* r=null)it=e;lc=l;rc=r;判斷是否是葉了結(jié)點(diǎn)bool isleafq return(lc=null)&&(rc=null);3 算法的基本思想構(gòu)建bst樹：輸入節(jié)點(diǎn)數(shù)后，依次輸入每個(gè)結(jié)點(diǎn)的值，將第一個(gè)結(jié)點(diǎn)作為根結(jié)點(diǎn)， 插入一個(gè)數(shù)，這個(gè)數(shù)與根節(jié)點(diǎn)先比較，若小于則再與根結(jié)點(diǎn)的左了樹相比較，若大于則與根 節(jié)點(diǎn)的右子樹相比較。比較時(shí)，若小于根結(jié)點(diǎn)且根結(jié)點(diǎn)的左子樹為空，則這個(gè)數(shù)為根結(jié)點(diǎn)左 子樹的值，若小于根結(jié)點(diǎn)乂大于

6、根結(jié)點(diǎn)的左子樹，則運(yùn)用指針將根結(jié)點(diǎn)的左指針指向這個(gè)值 得地址，這個(gè)值地址的指針再指向原來根結(jié)點(diǎn)左子樹；大于的情況同理。査找：設(shè)置一個(gè)計(jì)數(shù)器，每杏找一次則加一。從根節(jié)點(diǎn)開始，在bst屮檢索值ko 如果根節(jié)點(diǎn)存儲的值為k,則檢索結(jié)束。如果不是，必須檢索數(shù)的更深的一層。bst的效 率在于只需檢索兩棵子樹z-。如果k小于根節(jié)點(diǎn)的值，則只需檢索左子樹；若果k結(jié)點(diǎn) 大于根結(jié)點(diǎn)的值，則檢索右子樹。這個(gè)過程一直持續(xù)到k被知道或者遇到一個(gè)葉子結(jié)點(diǎn)為 止。如果葉子結(jié)點(diǎn)仍沒有發(fā)現(xiàn)k,那么k就不在bst屮。4 程序的流程程序由三個(gè)模塊組成：輸入模塊：輸入結(jié)點(diǎn)數(shù)冃初始數(shù)據(jù)，構(gòu)建二叉查找樹查找模塊：判斷需要查找的值是否在

7、該bst中 輸出模塊：輸出查找成功與否，并輸出比較的次數(shù)三、詳細(xì)設(shè)計(jì) 1物理數(shù)據(jù)類型動態(tài)查找表的數(shù)據(jù)為小數(shù)或整數(shù)，用float類型保存。樹的adt具體實(shí)現(xiàn)/初始化二叉樹bool initbst(bst *b) b->root = null;return true;銷毀bstbool clearbst(bstnode * &n)if(n)return false;if(n->lchild)clearbst(n->lchild);訐(n->rchild)clearbst(n->rchild);free(n);return true;初始化節(jié)點(diǎn)bool init

8、bstnode(bstnode * &n)n = (bstnode *)malloc(sizeof(bstnode); n->lchild = null;n->rchild = null;return true;結(jié)點(diǎn)的adt具體實(shí)現(xiàn)binnodeptr() lc=rc=null/ 結(jié)點(diǎn)的初始化binnodeptr(elem e,binnodeptr* l=null;binnodeptr* r=null)it=e;lc=l;rc=r;判斷是否是葉子結(jié)點(diǎn)bool isleaf()2 算法的具體步驟 .結(jié)點(diǎn)輸入操作：先輸入結(jié)點(diǎn)數(shù)，在輸入每個(gè)結(jié)點(diǎn)的值，通過循環(huán)調(diào)用insert函數(shù)將

9、每個(gè) 結(jié)點(diǎn)進(jìn)行插入cout « "bst 結(jié)點(diǎn)數(shù)目："endl;cin >> n;for (int i = 0; i<n; i+)cin » pi;if (pti <= 0)cout « "無效的結(jié)點(diǎn)輸入"« endl;system("pause");return;insert(&b, pi); .頭結(jié)點(diǎn)的建立：對于第一個(gè)調(diào)用insert函數(shù)插入的值，作為頭結(jié)點(diǎn)建立二叉樹if (b->root = null)b->root = n;return tru

10、e;.之后結(jié)點(diǎn)的插入：插入一個(gè)數(shù)，這個(gè)數(shù)根結(jié)點(diǎn)先比較，若小于則再為根結(jié)點(diǎn)的左子樹 相比較，若大于則與根節(jié)點(diǎn)的右了樹相比較。比較時(shí)，若小于根結(jié)點(diǎn)根結(jié)點(diǎn)的左了樹為空, 則這個(gè)數(shù)為根結(jié)點(diǎn)左子樹的值，若小于根結(jié)點(diǎn)乂人于根結(jié)點(diǎn)的左子樹，則運(yùn)川指針將根結(jié)點(diǎn) 的左指針指向這個(gè)值得地址，這個(gè)值地址的指針再指向原來根結(jié)點(diǎn)左子樹;大于的情況同理。 while (1)/循環(huán)比較if (e<m->data)/小丁根節(jié)點(diǎn)則插入左子樹 m - >lchild = n;/給左孩子賦值return true;if (m->lchild != null&&e>m->lchil

11、d->data)n->lchiid = m->lchild;m->lchild = n;return true;else m = m->lchild;continue;else/大于根節(jié)點(diǎn)則插入右子樹if (m->rchild = null)m->rchild = n; /給右孩了賦備return true;if (m->rchild != null&&e<m->rchild->data)n->rchild = m->rchild;m->rchild 二 n;return true;elsem

12、= m->rchild;continue;.完整的insert插入操作：插入元素e時(shí)，先判斷該二叉樹是否為空，若為空，將e作為 該二叉樹的根節(jié)點(diǎn)。否則，從根節(jié)點(diǎn)開始，比較e與節(jié)點(diǎn)n的大小。如果e的值更小，判斷 n的左了樹是否為空，若為空，將e作為節(jié)點(diǎn)n的左孩了并返冋e,否則比較e與n左孩了 的值，依此循環(huán)下去；如果e的值更人，判斷n的右子樹是否為空，若為空，將e作為節(jié)點(diǎn) n的右孩子并返回e,否則比較eljn右孩子的值，依此循環(huán)下去。bool insert(bst *b, elemtype e)把結(jié)點(diǎn)插入 bstbstnode *n, *m;initbstnode(n);n->dat

13、a = e;if (b->root = null)b->root = n;return true;m = b->root;wh訂e (1)/循環(huán)比較if (e<m->data)/小于根節(jié)點(diǎn)則插入左子樹if (m->lchild = null)m->lchid = n;/給左孩子賦值return true;if (m->lchild != null&&e>m->lch訂d-data) n->lchild = m->lchild;m->lchild = n;return true;else in 二 m-

14、>lchild;coni inue;el se/人于根節(jié)點(diǎn)則插入右子樹if (in->rchild 二二 null)m->rchild = n; /給右孩子賦值return true;if (in->rchild !二 null&&e<m->rchild->data) n->rchild = m->rchild;m->rchiid = n;return true;m = m->rchild;continuc;find查找操作，查找元素時(shí)，從根節(jié)點(diǎn)開始，比較e與節(jié)點(diǎn)x的大小，若相等，返回true； 如果e比節(jié)點(diǎn)x的

15、值小，判斷x的左子樹是否為空，若為空，返回false,不為空則比佼e 與x左孩了的值，依次循環(huán)下去；如果e比節(jié)點(diǎn)x的值人，判斷x的右了樹是否為空，若為 空，返回false,不為空則比較e與x右孩子的值，依次循環(huán)下去。bool find(bst *b, elemtype e) /查詢元素e,記錄比較的次數(shù)查詢成功返回true,否則返回falseint count = 0:bstnode *x = b->root;while (1)/循環(huán)比較count+;/設(shè)置計(jì)數(shù)器if (c<x->data)/小丁根節(jié)點(diǎn)則在左子樹中查找if (x->lchild = null)cout

16、« "杳找失敗，査找次數(shù)：" count « endl;return false;/左子樹為空則查找失敗x = x->lchild;/繼續(xù)與左孩子的值比較cont inue;if (e>x->data) /大于根節(jié)點(diǎn)則在右子樹屮查找if (x->rchild = null)cout « "杳找失敗，査找次數(shù)：" count « endl;return false;/右子樹為空則查找失敗x = x->rchild;/繼續(xù)與右孩子的值比較cont inue;if (e = x->da

17、ta)cout « "查找成功，查找次數(shù)："« count « endl;/cout « count:return true;3 算法的時(shí)空分析查找元素需要的比較次數(shù)由樹的深度決定杳找，最好時(shí)間復(fù)雜度o(logn),最壞時(shí)間 復(fù)雜度o(n)(只有左子樹或右子樹的情況)。4 輸入和輸出的格式輸入bst結(jié)點(diǎn)數(shù)bst結(jié)點(diǎn)數(shù)冃： 等待輸入cout << "bst 結(jié)點(diǎn)數(shù)："< endl;cin > n;輸入bst結(jié)點(diǎn)數(shù)據(jù)bst節(jié)點(diǎn)數(shù)拯：等待輸入for (int i = 0; i<n; i+)c

18、in >> pi;if (pil <= 0)cout « "無效的結(jié)點(diǎn)輸入"« endl;system ("pause");roturn;輸入要查找的數(shù)據(jù)cout « 輸入耍查找的數(shù)據(jù)(輸入-1結(jié)束査找)"« endl; cin » m;若bst結(jié)點(diǎn)數(shù)目輸入錯(cuò)誤：輸出“無效的結(jié)點(diǎn)數(shù)忖輸入”if (n <= 0)cout « "無效的結(jié)點(diǎn)數(shù)日輸入"« end!: system("pause");rcturn;若bs

19、t節(jié)點(diǎn)數(shù)據(jù)輸入錯(cuò)誤：輸出"無效的結(jié)點(diǎn)輸入”if (pi <= 0)cout « "無效的結(jié)點(diǎn)輸入"« endl;system("pause");return;若查找成功輸出查找次數(shù)：/輸出次數(shù)if (c = x->data)cout « "杳找成功，査找次數(shù)："<< count « endl; return true;査找失敗，查找次數(shù)：/輸出次數(shù)if (x->rchild = null)cout « "查找失敗，查找次數(shù)："

20、« count « endl: return false;/右子樹為空則查找失敗四. 調(diào)試分析1.本程序會將笫一個(gè)輸入的值作為root,如果第一個(gè)值輸入過大，導(dǎo)致所冇數(shù)據(jù)都被 存放進(jìn)左子樹，導(dǎo)致樹的長度n過長，接卜-來的查找效率過低，因?yàn)樽詈迷谳斎肭熬痛笾驴?慮一下中間值是多少，盡量避免樹過長。2.開始insert函數(shù)并沒冇考慮太多，后來發(fā)現(xiàn)再輸入節(jié)點(diǎn)的值時(shí)冇限制，必須輸入 比之前輸入所有節(jié)點(diǎn)值的最小值還小，或者比之前輸入最大值還要大。舉例輸入3142,此程序生成的樹為3/ 14,此時(shí)insert只能接在1后面，錯(cuò)誤，錯(cuò)誤結(jié)果如下經(jīng)過修改，3 的左指針指向 2,2 的左指針

21、指向1五. 測試結(jié)果第一組：輸入節(jié)點(diǎn)數(shù)10節(jié)點(diǎn)數(shù)據(jù) 50 1 3 2 78 65 100 59 43 18結(jié)果正確笫二組:e:my ccbst動態(tài)查找project1debugproject1.exe|bst結(jié)點(diǎn)數(shù)目:10bst節(jié)點(diǎn)數(shù)據(jù)：100 1 12 35 43 95 54 82 78 93 輸入要查找的數(shù)據(jù)（輸入-1結(jié)束查找）1查找成功，查找次數(shù)：10輸入要查找的數(shù)據(jù)（輸入-1結(jié)束查找）12查找成功，查找次數(shù)：9輸入要查找的數(shù)據(jù)（輸入-1結(jié)束查找）35查找成功，查找次數(shù)：8輸入要查找的數(shù)據(jù)（輸入-1結(jié)束查找）95查找成功，查找次數(shù)：2輸入要查找的數(shù)據(jù)（輸入-1結(jié)束查找）19查找失敗，查找

22、次數(shù)：9輸入要查找的數(shù)據(jù)（輸入-1結(jié)束查找）甘叟狗拼音輸入法全：結(jié)果正確第三組:結(jié)果正確第四組:結(jié)果正確第五組:結(jié)果正確六、用戶使用說明木程序會將第一個(gè)數(shù)作為root,所以輸入前大致想好范圍，笫一個(gè)數(shù)盡量輸入中間值，可以 減少查找的時(shí)間復(fù)雜度七. 試驗(yàn)心得1試驗(yàn)剛開始考慮過先將輸入的數(shù)進(jìn)行排序，后來覺得冒泡排序?qū)r(shí)間復(fù)雜度的影響是 0（22）,遠(yuǎn)人于杳找最人時(shí)間0（°.）,于是放棄，木程序通過bst樹，極人的優(yōu)化了時(shí)間復(fù)雜 度，數(shù)據(jù)結(jié)構(gòu)的魅力也就在此。2.由于對時(shí)間復(fù)雜度的不滿意，查閱了有關(guān)最優(yōu)二叉查找樹資料3動態(tài)規(guī)劃方法牛成最優(yōu)二叉杳找樹（參考csdn）基于統(tǒng)計(jì)先驗(yàn)知識，我們可統(tǒng)計(jì)

23、出一個(gè)數(shù)表（集合）屮各元索的查找概率，理解為集合各元索的 出現(xiàn)頻率。比如中文輸入法字庫中各詞條（單字、詞組等）的先驗(yàn)概率，針對用戶習(xí)慣可以口動調(diào)整 詞頻一所謂動態(tài)調(diào)頻、高頻先現(xiàn)原則，以減少用戶翻查次數(shù)。這就是放優(yōu)二叉查找樹問題：查找過 程中鍵值比較次數(shù)最少,或者說希塑用最少的鍵值比較次數(shù)找到毎個(gè)關(guān)鍵碼（鍵值）o為解決這樣的 問題,顯然需要對集合的每個(gè)元索賦了一個(gè)特殊屬性杳找概率。這樣我們就需要構(gòu)造一顆最優(yōu)二 義查找樹。n個(gè)鍵a1,a2,a3an,其相應(yīng)的査找概率為php2,p3pn。構(gòu)成最優(yōu)bst,表示為tin ,求 這棵樹的平均查找次數(shù)c1,n（耗費(fèi)放低）。換言之，如何構(gòu)造這棵最優(yōu)bst,使

24、得c1,n最小。動態(tài)規(guī)劃法策略是將問題分成多個(gè)階段，逐段推進(jìn)計(jì)算，后繼實(shí)例解由其直接前趨實(shí)例解計(jì)算得 到。對于最優(yōu)bst問題，利用減一技術(shù)和最優(yōu)性原則，如果前n1個(gè)節(jié)點(diǎn)構(gòu)成最優(yōu)bst,加入一個(gè) 節(jié)點(diǎn)an后要求構(gòu)成規(guī)模n的最優(yōu)bst。按n-1, n-2 , 2,1遞歸，問題可解。自底向上計(jì)算：c1, 2hc1,3為不失一般性用ci,j表示fha1,a2,a3.an構(gòu)成的bst的耗費(fèi)。其中1<i<j<no這棵樹表示為tij。從中選擇一個(gè) 鍵ak作根節(jié)點(diǎn)，它的左子樹為tik-1,右子樹為tk+1j。要求選擇的k使得整棵樹的平均杳找次數(shù) ci,j最小。左右了樹遞歸執(zhí)行此過程。（根的生

25、成過程）遞推計(jì)算式k-l = it左了樹縮為單節(jié)點(diǎn)。 k+1=j：右了樹縮為單節(jié)點(diǎn)。 k<i：左子樹為空樹a 右子樹為空樹。概率：pl5 pk，以+1，二7 pj鍵值：勺,9"1、"k+i，aj* i左升i右自頂向卜分析舁丿二四鶉八1 +工必（£）+ 1）+工必（厶（礙）+ 1）&子材（城姐找）石子材（蔽查找）it-ij、*-i）u卿幾+刃+ x a+仏）+-z心+1嚴(yán)*+1一 ' 錨節(jié)若升評scg.； j®推計(jì)鼻式j(luò)ha/ = min5,zr-lj + c + lj +仁i 旨勿基本算法c/j-l<-0;cijpi:甬元a/

26、,/<-/； 叮 t(?”十 1“jo;ti;:for (d to ft-i) dofor(i<-to n-d)do f ;-1j ji+d;出 i、minval <-qo;for (a <- i to j) dok人匕+ c吐1j <minval) mimal c/,a-1 + c +l,j; av/i/zz < k:rij<-kmbk 4 亍 £ i f 鋁 sum <-piifor ($<-/+l to j) do sum <- sum + ps; cij =ifiinval + sum; return r);2345

27、00.1041700.20.81400.41.000.30立方塑效率r刖可以限定在之冋，效季降至 平方乩八. 附錄#includeiostream>#include<stdlib.h>using namespacc std;# i nc 1 ude，zal gor i t hnttypedef float elemtype;typedef struct bstnodeelemtype data;struct bstnode *lchild, *rchild;bstnode;typedef struct bstbstnode *root; bst;bool initbst(bs

28、t *b) /初始化二叉樹ib->root = null;return true;bool initbstnode (bstnode * &n) 初始化節(jié)點(diǎn) n = (bstnode *)ma1loc(sizeof(bstnode); n->lchiid = null;n->rchild = null;return true;bool clearbst(bstnode * &n) /銷毀 bstiif (n)return false;if (n->lchiid)clearbst(n->lchiid);if (n->rchild) clearb

29、st(n->rchild);free (n);return true;bool insert (bst *b, elemtype e)/把結(jié)點(diǎn)插入 bstbstnode *n, *m;initbstnodc (n);n->data = e;if (b->root = null)b->root = n;return true;m = b->root;while (1)/循環(huán)比較i f (e<m->da13) /小于根節(jié)點(diǎn)則插入左了樹if (m->lchiid = null)im->lchild二n;/給左孩子賦值return true;if (m->lchild != null&&e>m->lchild->data)in->lchild 二 m->lchild;ni->lchiid 二 n;return true;else m = m->lchild;continue;else/大于根節(jié)點(diǎn)則插入右子樹nr>rchild = n; /給右孩子賦值return true;if (m->rchild != null&&e<m->rchild->data)n->rchiid = m*>rchiid;m->r