二叉平衡排序樹

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 設(shè)計(jì)題目： 二叉平衡排序樹 姓名： 黃洪飛 學(xué)號(hào)： 211111014 專業(yè)： 嵌入式軟件 院系：計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 班級(jí)： 1103班 指導(dǎo)教師： 高秀梅2013年 1 月 30 日 摘要 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)是在學(xué)完數(shù)據(jù)結(jié)構(gòu)課程之后的實(shí)踐教學(xué)環(huán)節(jié)。該實(shí)踐教學(xué)是軟件設(shè)計(jì)的綜合訓(xùn)練，包括問(wèn)題分析、總體結(jié)構(gòu)設(shè)計(jì)、用戶界面設(shè)計(jì)、程序設(shè)計(jì)基本技能和技巧。要求學(xué)生在設(shè)計(jì)中逐步提高程序設(shè)計(jì)能力，培養(yǎng)科學(xué)的軟件工作方法。 數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)程序設(shè)計(jì)的重要理論技術(shù)基礎(chǔ)，它不僅是計(jì)算機(jī)科學(xué)的核心課程，而且也已經(jīng)成為其他理工專業(yè)的熱門選修課。隨著高級(jí)語(yǔ)言的發(fā)展，數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)

2、的研究和應(yīng)用中已展現(xiàn)出強(qiáng)大的生命力，它兼顧了諸多高級(jí)語(yǔ)言的特點(diǎn)，是一種典型的結(jié)構(gòu)化程序設(shè)計(jì)語(yǔ)言，它處理能力強(qiáng)，使用靈活方便，應(yīng)用面廣，具有良好的可移植性。英文摘要Data structure is a strong theoretical thinking, abstract and difficult course, is a bridge between fundamental course and specialized course. The course of the first course is basic computer, program design language, d

3、iscrete mathematics, etc, the subsequent course has operating system, compiling principle, principle of database, software engineering, etc. Through this course of study, we should be able to a thorough understanding of the characteristics of various data objects, and learn to data organization meth

4、od and implementation methods, and further cultivate good program design ability and the ability to solve practical problems. Data structure is a computer science and technology professional a core the basis of professional course, in the professional course system plays an essential role, learn dat

5、a structure to improve the cognitive level of theory and practice ability has a very important role. Learning data structure of the ultimate goal is to gain the ability of solving problem. For the real world problems, should be able to abstract out an appropriate mathematical model, the mathematical

6、 model in computer internal with the corresponding data structure to say, and then design a solution of the mathematical model of the algorithm, and then to programming debugging, and finally get the answer. In order to strengthen the practice course is programming ability training, and encourage st

7、udents to use the new programming language. We believe that through the data structure course practice, both theoretical knowledge and practical ability, or we will have different degree of increase 目 錄一、 問(wèn)題5二、需求分析5三、概要設(shè)計(jì)5四、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)6五、算法設(shè)計(jì)6六、程序測(cè)試與實(shí)現(xiàn)8七、調(diào)試分析11八、遇到的問(wèn)題及解決辦法11九、心得體會(huì)111、 問(wèn)題問(wèn)題描述：創(chuàng)建二叉平衡排序樹基本要

8、求：1.輸入數(shù)據(jù)的數(shù)量不得低于15個(gè)2.建立二叉平衡排序樹（要求包括LL型LR型RR型RL型四種調(diào)整方式）3.完成任意數(shù)據(jù)的查找（要求給出查找執(zhí)行的次數(shù)）二、需求分析1.本程序的功能包括二叉平衡排序樹的建立，二叉平衡排序樹的查詢，二叉平衡排序樹的輸出。2.程序運(yùn)行后顯現(xiàn)提示信息，等候用戶輸入1-3以進(jìn)入相應(yīng)的操作功能，以及控制程序循環(huán)的功能。3.用戶輸入數(shù)據(jù)完畢，程序?qū)⑤敵鲞\(yùn)行結(jié)束。4.測(cè)試數(shù)據(jù)應(yīng)為二叉平衡排序樹每個(gè)結(jié)點(diǎn)的數(shù)據(jù)。三、概要設(shè)計(jì)帶頭結(jié)點(diǎn)的單鏈表抽象數(shù)據(jù)類型定義為：ADT AVLtree屬性： AVLnode * root;操作集合： void insert(const T & x,

9、AVLnode * &t);/樹的建立void makeEmpty(AVLnode * &t)/樹的銷毀int height(AVLnode *t)constreturn t=NULL? -1:t-height;/樹的高度void LL(AVLnode * &t); /樹void LR(AVLnode * &t);/ 的void RL(AVLnode * &t); / 調(diào)void RR(AVLnode * &t);/ 整int max(int a,int b)return (ab)?a:b; /結(jié)點(diǎn)數(shù)值比大小void printin(AVLnode * t,int depth);/樹的打印AD

10、T AVLtree；四、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)元素類型，結(jié)點(diǎn)類型，指針類型 typedef struct AVLnode /結(jié)點(diǎn)類型定義 T data; /結(jié)點(diǎn)數(shù)據(jù)域 struct AVLnode *left; /結(jié)點(diǎn)左指針域 struct AVLnode *right; /結(jié)點(diǎn)右指針域 Int height/樹的高度AVLnode;五、算法設(shè)計(jì) 1、算法分析與實(shí)現(xiàn) template void AVLtree:insert(const T & x,AVLnode * &t) if(t=NULL)/空樹上插入 t=new AVLnode(x,NULL,NULL); else if(xdata)/在左子樹上

11、插入 insert(x,t-left);/從左邊插入 if(height(t-left)-height(t-right)=2)/t失去平衡 if(xleft-data)LL(t);else LR(t);/進(jìn)行調(diào)整 else if(t-dataright);/在右子樹上插入 if(height(t-right)-height(t-left)=2)/t失去平衡 if(t-right-dataheight=max(height(t-left),height(t-right)+1;/重新計(jì)算t的高度template void AVLtree:LL(AVLnode * &t)AVLnode *t1=t-

12、left;/定臨時(shí)變量t-left=t1-right;t1-right=t;t-height=max(height(t-left),height(t-right)+1;t1-height=max(height(t1-left),height(t)+1;t=t1;template void AVLtree:LR(AVLnode * &t)RR(t-left);LL(t);template bool AVLtree:find(const T &x)constint count=1;/計(jì)數(shù)變量AVLnode *t=root;/定義臨時(shí)變量while(t!=NULL & t-data!=x)count

13、+;計(jì)數(shù)邊量+1if(t-datax)t=t-left;elset=t-right; cout比較次數(shù):count;/輸出查找的次數(shù) cout查找結(jié)果:;if(t=NULL)return false;elsereturn true;template void AVLtree:printin(AVLnode * t,int depth=1)if(t!=NULL)printin(t-right,depth+1);/遞歸調(diào)用for(int i=0;i4*(depth-1);i+)coutright=NULL & t-left=NULL)coutdataendl;else coutdata left,

14、depth+1); 六、程序測(cè)試與實(shí)現(xiàn)1、函數(shù)之間的調(diào)用關(guān)系mainmenu insert()find()printin() Hieght() RR() LL() LR() RL() RR() LL() RR() LL() Max() 2、主程序 int main() AVLtree obj;while(true) meus(); coutn; switch(n) case 1: coutm; obj.insert(m); break; case 2: couti; coutobj.find(i); coutendl; break; case 3: cout打印結(jié)果為:endl;obj.pri

15、ntin(); break; default: cout您輸入的不正確!endl; coutch; if(ch=N | ch=n) return 0; return 0; 3、 測(cè)試數(shù)據(jù) 65,89,46,25,52,87,97,75 4、 測(cè)試結(jié)果 7、 調(diào)試分析1鏈表中的結(jié)點(diǎn)變量是通過(guò)指針變量來(lái)訪問(wèn)的。因?yàn)樵贑語(yǔ)言中是用P來(lái)表示P所指的變量，又由于結(jié)點(diǎn)類型是一個(gè)結(jié)構(gòu)類型，因此可用P data，Pleft，p-right 分別表示結(jié)點(diǎn)的數(shù)據(jù)域變量和指針域變量。指針變量的值要么為空(NULL)，不指向任何結(jié)點(diǎn)；要么其值為非空，即它的值是一個(gè)結(jié)點(diǎn)的存儲(chǔ)地址。注意，當(dāng)P為空值時(shí)，則它不指向任何結(jié)點(diǎn)

16、，此時(shí)不能通過(guò)P來(lái)訪問(wèn)結(jié)點(diǎn)，否則會(huì)引起程序錯(cuò)誤。2算法的時(shí)空分析： 二叉排序樹的查找 在二叉排序樹中進(jìn)行查找的過(guò)程和二分查找類似也是一個(gè)通過(guò)比較關(guān)鍵字逐步縮小查找范圍的過(guò)程。 若查找成功則是一條從根結(jié)點(diǎn)到待查結(jié)點(diǎn)的路徑若查找失敗則是一條根結(jié)點(diǎn)到某個(gè)葉子結(jié)點(diǎn)的路徑由上可知查找過(guò)程中和關(guān)鍵字比較的次數(shù)不超過(guò)樹的深度。 二 二叉排序樹查找的性能分析 由于所要查找的數(shù)據(jù)量不同則其查找的性能也不同。且二叉排序樹的平均查找長(zhǎng)度與樹的形態(tài)有關(guān)。最好情況是二叉排序樹和二叉判定樹形態(tài)相同最壞情況是二叉排序樹為單支樹則其平均查找長(zhǎng)度與順序查找相同。 分別輸入不同的二叉排序樹觀察并計(jì)算其平均查找長(zhǎng)度及時(shí)間空間復(fù)雜度

17、 將已給的信息建立二叉樹且根據(jù)學(xué)號(hào)查找數(shù)據(jù)并顯示并判斷此方法的性能。 八、遇到的問(wèn)題及解決辦法1.怎樣才能使得存儲(chǔ)在內(nèi)存中的數(shù)據(jù)結(jié)構(gòu)更加直觀的表現(xiàn)出來(lái)？ 解決方法：將二叉樹倒過(guò)來(lái)打印。2. 函數(shù)的遞歸調(diào)用不是很明白？ 解決方法：使用棧畫圖來(lái)理解。9、 心得體會(huì)回顧起此次課程設(shè)計(jì)，感慨頗多，從理論到實(shí)踐，在整整兩個(gè)星期的日子里，我學(xué)到很多很多的東西，不僅鞏固了以前所學(xué)過(guò)的知識(shí)，而且學(xué)到了很多在書本上所沒(méi)有學(xué)到過(guò)的內(nèi)容。通過(guò)這次課程設(shè)計(jì)使我懂得了理論與實(shí)際相結(jié)合是很重要的，只有理論知識(shí)是遠(yuǎn)遠(yuǎn)不夠的，只有把所學(xué)的理論知識(shí)與實(shí)踐相結(jié)合起來(lái)，從理論中得出結(jié)論，才是真正的知識(shí)，才能提高自己的實(shí)際動(dòng)手能力和

18、獨(dú)立思考的能力。在設(shè)計(jì)的過(guò)程遇到了各種各樣的問(wèn)題，同時(shí)在設(shè)計(jì)的過(guò)程中發(fā)現(xiàn)了自己的不足之處，對(duì)以前所學(xué)過(guò)的知識(shí)理解得不夠深刻，掌握得不夠牢固，通過(guò)這次課程設(shè)計(jì)，把以前所學(xué)過(guò)的知識(shí)重新溫故，鞏固了所學(xué)的知識(shí)。 課程設(shè)計(jì)是一門綜合性的實(shí)踐性課程，課程設(shè)計(jì)能夠培養(yǎng)我們發(fā)現(xiàn)問(wèn)題分析問(wèn)題和解決問(wèn)題的能力，對(duì)于我們編寫程序，合理運(yùn)用各種語(yǔ)法也有一定的提高。同時(shí)課程設(shè)計(jì)還有利于我們及時(shí)了解和掌握所學(xué)的相關(guān)知識(shí)。我一千次一萬(wàn)次的問(wèn)自己，怎么才能找到課堂所學(xué)與實(shí)際應(yīng)用的最佳結(jié)合點(diǎn)？怎么才能讓自己的程序在篇幅上簡(jiǎn)單，在使用價(jià)值上豐富？怎樣讓自己的業(yè)余更靠近專業(yè)？怎樣讓自己的計(jì)劃更具有序性，而不會(huì)忙無(wú)一用？機(jī)會(huì)是老師

19、，學(xué)校，以及無(wú)數(shù)代教育工作者給的，而能力是自己的，耐性是需要的。經(jīng)過(guò)自己的琢磨，聽取了師姐，師兄們的建議，還查閱了很多書籍，才做到了心中有數(shù)，才了解了算法設(shè)計(jì)與分析課程設(shè)計(jì)的真正用意培養(yǎng)自學(xué)能力，養(yǎng)成程序編輯的好習(xí)慣。我從來(lái)不相信車到山前必有路的說(shuō)法，認(rèn)為那只是懶惰者自尋懶惰的借口，我要積極，要把握，要努力。不知不覺(jué)，時(shí)間就迅速地渡過(guò)了，我開始慌張起來(lái)，因?yàn)槲疫€有許多程序代碼不太明白，我又急急的去圖書館查了更多相關(guān)資料，我才發(fā)現(xiàn)原來(lái)我所學(xué)的知識(shí)真的很有限，我試著去調(diào)試，結(jié)果失敗了好多次，我也不知道問(wèn)題出現(xiàn)在哪里，我問(wèn)了幾位同學(xué)，他們熱情地給我提供幫助，在他們的啟迪下，我經(jīng)過(guò)修改，終于通過(guò)的調(diào)試

20、。當(dāng)我把調(diào)好的程序拿去給老師看是否合理時(shí)，老師給我提出了用鍵盤輸入數(shù)據(jù)的靈活運(yùn)用方法。在老師的指導(dǎo)下，更新后的程序就初見眉目。這更加強(qiáng)了我的信心，我時(shí)常去上機(jī)調(diào)試程序，運(yùn)行程序，修改程序。不懂時(shí)及時(shí)請(qǐng)教指導(dǎo)老師，老師便會(huì)認(rèn)真負(fù)責(zé)耐心的講解起來(lái)。我想要是沒(méi)有老師的幫助，我的此次課設(shè)就不會(huì)順利完成。在此，我很誠(chéng)摯地謝謝指導(dǎo)過(guò)我的老師們， 在我程序混亂時(shí)，老師沒(méi)有批評(píng)我，而是很耐心的給我講解哪些是重復(fù)的，哪些是錯(cuò)誤的，哪些是必要的，老師就是世界上最最偉大的人。謝謝你！我的老師們。從拿到題目到完成整個(gè)編程，從理論到實(shí)踐，可以學(xué)到很多很多的的東西，同時(shí)不僅可以鞏固了以前所學(xué)過(guò)的知識(shí)，而且學(xué)到了很多在書本

21、上所沒(méi)有學(xué)到過(guò)的知識(shí)。通過(guò)這次課程設(shè)計(jì)使我懂得了理論與實(shí)際相結(jié)合是很重要的，只有理論知識(shí)是遠(yuǎn)遠(yuǎn)不夠的，只有把所學(xué)的理論知識(shí)與實(shí)踐相結(jié)合起來(lái)，從理論中得出結(jié)論，才能真正為社會(huì)服務(wù)，從而提高自己的實(shí)際動(dòng)手能力和獨(dú)立思考的能力。在設(shè)計(jì)的過(guò)程中遇到問(wèn)題，可以說(shuō)得是困難重重，這畢竟第一次做的，難免會(huì)遇到過(guò)各種各樣的問(wèn)題，同時(shí)在設(shè)計(jì)的過(guò)程中發(fā)現(xiàn)了自己的不足之處，對(duì)以前所學(xué)過(guò)的知識(shí)理解得不夠深刻，掌握得不夠牢固，通過(guò)這次課程設(shè)計(jì)之后，一定把以前所學(xué)過(guò)的知識(shí)重新溫故。沒(méi)有辛苦的歷程就無(wú)法感受甜美的收獲。在此次課程設(shè)計(jì)中，我不但運(yùn)用了算法設(shè)計(jì)與分析的思想，還利用了C+語(yǔ)言方面的知識(shí)。這對(duì)于我來(lái)說(shuō)是一個(gè)突破。從中我也學(xué)習(xí)到