數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(二叉排序樹的相關(guān)操作)

1、<p>　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告</p><p>　　課程設(shè)計題目：二叉排序樹的相關(guān)操作 </p><p><b>　　學(xué)生姓名 ： </b></p><p><b>　　專 業(yè) ：</b></p><p><b>　　班 級 ： </b>

2、</p><p><b>　　學(xué) 號 ： </b></p><p><b>　　指導(dǎo)教師 ：</b></p><p>　　2012年06月23日</p><p><b>　　摘要：</b></p><p>　　數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)之間關(guān)系的一門科學(xué)，

3、我們稱這一關(guān)系為數(shù)據(jù)的邏輯結(jié)構(gòu)，簡稱數(shù)據(jù)結(jié)構(gòu)。當(dāng)數(shù)據(jù)的邏輯結(jié)構(gòu)確定以后，數(shù)據(jù)在物理空間中的存儲方式，稱為數(shù)據(jù)的存儲結(jié)構(gòu)。同一邏輯結(jié)構(gòu)可以具有不同的存儲結(jié)構(gòu)，因而有不同的算法。本次課程設(shè)計，程序中的數(shù)據(jù)采用“二叉樹結(jié)構(gòu)”。具體采用的是“二叉排序樹”，并且使用“一維數(shù)組”作為其存儲結(jié)構(gòu)。一維數(shù)組順序表存儲結(jié)構(gòu)是用一組地址連續(xù)的存儲單元依次自左而右、自上而下存儲二叉排序樹的結(jié)點(diǎn)元素；本課程設(shè)計實現(xiàn)了二叉排序樹的創(chuàng)建、查找、插入、刪除，中序遍歷

4、輸出等基本操作，完美地實現(xiàn)了二叉排序樹的大部分功能。</p><p>　　關(guān)鍵詞：二叉排序樹的創(chuàng)建；中序遍歷輸出；插入結(jié)點(diǎn)；查找結(jié)點(diǎn)；刪除結(jié)點(diǎn)</p><p><b>　　課程設(shè)計目的：</b></p><p>　　課程設(shè)計為學(xué)生提供了一個既動手又動腦，獨(dú)立實踐的機(jī)會，將課本上的理論知識和實際有機(jī)的結(jié)合起來，鍛煉學(xué)生的分析解決實際問題的能力。提

5、高學(xué)生適應(yīng)實際，實踐編程的能力。</p><p><b>　　內(nèi)容設(shè)計要求：</b></p><p>　　二叉排序樹的相關(guān)操作</p><p>　　要求：完成二叉排序樹的建立、查詢、插入和刪除操作</p><p><b>　　三、概要設(shè)計：</b></p><p><b

6、>　　1.菜單設(shè)計：</b></p><p>　　為了實現(xiàn)二叉排序樹相關(guān)操作的管理，設(shè)計一個包含多個子菜單項的主菜單，子程序以鏈接系統(tǒng)的各項子功能，方便用戶使用本程序。本系統(tǒng)主菜單界面如下圖所示：</p><p><b>　　2.存儲結(jié)構(gòu)設(shè)計：</b></p><p>　　用二叉鏈?zhǔn)酱鎯︻愋痛鎯Χ鏄涞慕Y(jié)點(diǎn)結(jié)構(gòu)。二叉樹的鏈表中

7、結(jié)點(diǎn)至少包含3個域：數(shù)據(jù)域、左孩子指針域和右孩子指針域。</p><p>　　typedef struct bitreenode// 二叉樹結(jié)點(diǎn)結(jié)構(gòu)類型</p><p><b>　　{</b></p><p><b>　　int data;</b></p><p>　　struct bitreeno

8、de *lchild;</p><p>　　struct bitreenode *rchild;</p><p>　　} bitreenode ,*bitree;</p><p>　　3. 系統(tǒng)功能設(shè)計：</p><p>　　本系統(tǒng)設(shè)置了5子功能菜單，5個子功能的設(shè)計描述如下。</p><p>　　建立二叉排序樹，由函

9、數(shù)void createbst( )來實現(xiàn)。</p><p>　　查找節(jié)點(diǎn)，由函數(shù)int searchbst(bitree root,int data)來實現(xiàn)。</p><p>　　插入節(jié)點(diǎn)，由函數(shù)void insertbst(bitree *root,int data)來實現(xiàn)。</p><p>　　刪除節(jié)點(diǎn)，由函數(shù)bitreenode *deletebst(bi

10、tree t,int k)來實現(xiàn)。</p><p><b>　　四、目與流程圖：</b></p><p>　　題目： 二叉排序樹的相關(guān)操作</p><p><b>　　流程圖：</b></p><p><b>　　五、運(yùn)行結(jié)果：</b></p><p>

11、<b>　　1.創(chuàng)建二叉樹：</b></p><p><b>　　查找結(jié)點(diǎn)：</b></p><p><b>　　插入結(jié)點(diǎn)：</b></p><p><b>　　刪除結(jié)點(diǎn)：</b></p><p><b>　　退出：</b></

12、p><p><b>　　六、小結(jié)：</b></p><p>　　經(jīng)過一個星期的課程設(shè)計，過程曲折可謂一語難盡。整天都是對著電腦，不然就是翻閱資料。在此期間我失落過，也曾一度熱情高漲。點(diǎn)點(diǎn)滴滴令我回味無窮。這次課程設(shè)計使我體會到只有做到細(xì)心耐心，恒心才能做好一件事。</p><p>　　這次的課程設(shè)計，加強(qiáng)了我們動手、思考和解決問題的能力。鞏固和加深

13、了對數(shù)據(jù)結(jié)構(gòu)的理解，提高綜合運(yùn)用本課程所學(xué)知識的能力，培養(yǎng)了我查找參考書，及文獻(xiàn)資料的能力。培養(yǎng)獨(dú)立思考，深入研究，分析問題、解決問題的能力。通過實際編譯系統(tǒng)的分析設(shè)計、編程調(diào)試，掌握應(yīng)用軟件的分析方法和工程設(shè)計方法。通過課程設(shè)計，培養(yǎng)了我嚴(yán)肅認(rèn)真的學(xué)習(xí)態(tài)度，逐步建立正確的局部觀念和全局觀念的關(guān)系。而且做課程設(shè)計同時也是對課本知識的鞏固和加強(qiáng)，平時看課本時，有些問題就不是很能理解，做完課程設(shè)計，那些問題就迎刃而解了。認(rèn)識來源于實踐，實踐

14、是認(rèn)識的動力和最終目的，實踐是檢驗真理的唯一標(biāo)準(zhǔn)。所以這個期末測試之后的課程設(shè)計對我們的作用是非常大的。</p><p>　　這次的課程設(shè)計使我懂得了理論與實際相結(jié)合是很非常重要的，只有理論知識是遠(yuǎn)遠(yuǎn)不夠的，只有把所學(xué)的理論知識與實踐相結(jié)合起來，從理論中得出結(jié)論，從實踐中檢驗理論，從而提高自己的實際動手能力和獨(dú)立思考的能力。在整個設(shè)計過程中，構(gòu)思是很重要的。調(diào)試時經(jīng)常會遇到這樣那樣的錯誤，有的是因為粗心造成的語法

15、錯誤。當(dāng)然，也有方法錯誤之類的，總是需要花費(fèi)很多時間來檢查錯誤。同時在設(shè)計的過程中發(fā)現(xiàn)了自己的許多不足之處，對以前所學(xué)過的知識理解得不夠深刻，掌握得不夠牢固。</p><p>　　每個細(xì)節(jié)問題通常都要花費(fèi)很長的時間才能理清程序的思路，而且要不斷的調(diào)試程序才能把程序調(diào)試正確，同時還要做到界面的輸出也是需要美化的。這次課程設(shè)計終于順利完成了。</p><p>　　通過這次的課程設(shè)計，讓我更加了

16、解到數(shù)據(jù)結(jié)構(gòu)的重要性。此次課程設(shè)計，學(xué)到了很多課內(nèi)學(xué)不到的東西，比如獨(dú)立思考解決問題的能力，出現(xiàn)差錯的隨機(jī)應(yīng)變能力，這些都讓我受益非淺，今后的制作應(yīng)該能夠更輕松。</p><p><b>　　附錄：</b></p><p><b>　　1.源代碼：</b></p><p>　　# include<stdio.h>

17、;</p><p>　　# include<stdlib.h></p><p>　　#define null 0</p><p>　　typedef struct bitreenode</p><p><b>　　{</b></p><p><b>　　int data;&l

18、t;/b></p><p>　　struct bitreenode *lchild;</p><p>　　struct bitreenode *rchild;</p><p>　　}bitreenode,*bitree;</p><p>　　int searchbst(bitree root,int data)</p>&

19、lt;p><b>　　{</b></p><p><b>　　bitree p;</b></p><p><b>　　p=root;</b></p><p><b>　　while(p)</b></p><p><b>　　{</b&

20、gt;</p><p>　　if (p->data==data)</p><p>　　return p->data;</p><p>　　if(p->data>data)</p><p>　　p=p->lchild;</p><p>　　else p=p->rchild;</p

21、><p><b>　　}</b></p><p>　　return 1000;</p><p><b>　　}</b></p><p>　　void insertbst(bitree *root,int data)</p><p><b>　　{</b>&l

22、t;/p><p><b>　　bitree s;</b></p><p>　　if(*root==null)</p><p><b>　　{</b></p><p>　　s=(bitree)malloc(sizeof(bitreenode));</p><p>　　s->d

23、ata=data;</p><p>　　s->lchild=s->rchild=null;</p><p><b>　　*root=s;</b></p><p><b>　　}</b></p><p>　　else if(data<(*root)->data)</p&g

24、t;<p>　　insertbst(&((*root)->lchild),data);</p><p>　　else if(data>(*root)->data)</p><p>　　insertbst(&((*root)->rchild),data);</p><p><b>　　}</b>

25、;</p><p>　　void display(bitree root)</p><p><b>　　{</b></p><p>　　if(root!=null)</p><p><b>　　{</b></p><p>　　display(root->lchild);

26、</p><p>　　printf("%5d",root->data);</p><p>　　display(root->rchild);</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　bi

27、treenode *deletebst(bitree t,int k)</p><p><b>　　{</b></p><p>　　bitreenode *p,*f,*s,*q;</p><p><b>　　p=t;</b></p><p><b>　　f=null;</b>&

28、lt;/p><p><b>　　while(p)</b></p><p><b>　　{</b></p><p>　　if(p->data==k) break;</p><p><b>　　f=p;</b></p><p>　　if(p->dat

29、a>k)</p><p>　　p=p->lchild;</p><p>　　else p=p->rchild;</p><p><b>　　}</b></p><p>　　if(p==null)</p><p><b>　　{</b></p>

30、<p>　　printf("The key to search does not exist!\n");</p><p><b>　　return t;</b></p><p><b>　　}</b></p><p>　　if(p->lchild==null)</p>&l

31、t;p><b>　　{</b></p><p>　　if(f==null)</p><p>　　t=p->rchild;</p><p>　　else if(f->lchild==p)</p><p>　　f->lchild=p->rchild;</p><p>　　

32、else f->rchild=p->rchild;</p><p><b>　　free(p);</b></p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p&

33、gt;<p><b>　　q=p;</b></p><p>　　s=p->lchild;</p><p>　　while(s->rchild)</p><p><b>　　{</b></p><p><b>　　q=s;</b></p>

34、<p>　　s=s->rchild;</p><p><b>　　}</b></p><p><b>　　if(q==p)</b></p><p>　　q->lchild=s->lchild;</p><p>　　else q->rchild=s->lchil

35、d;</p><p>　　p->data=s->data;</p><p><b>　　free(s);</b></p><p><b>　　}</b></p><p><b>　　return t;</b></p><p><b>

36、;　　}</b></p><p>　　void createbst(bitree *root)</p><p><b>　　{</b></p><p><b>　　int data;</b></p><p>　　*root=null;</p><p>　　prin

37、tf("Please input the data: ");</p><p>　　scanf("%d",&data);</p><p>　　while(data!=1000)</p><p>　　{ insertbst(root,data);</p><p>　　scanf("%d&q

38、uot;,&data);</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void table()</p><p><b>　　{</b></p><p>　　printf("\t**

39、***********Welcome to use!*************\n");</p><p>　　printf("\t* 1. create bitree *\n");</p><p>　　printf("\t* 2. search bitreenode *\n&

40、quot;);</p><p>　　printf("\t* 3. insert bitreenode *\n");</p><p>　　printf("\t* 4. delete bitreenode *\n");</p><p>　　printf("

41、;\t* 0. exit *\n");</p><p>　　printf("\t*****************************************\n");</p><p><b>　　}</b></p><p>　　void main()

42、</p><p><b>　　{</b></p><p>　　int data,menu;bitree root;</p><p><b>　　table();</b></p><p>　　printf("Please input your action number(0-4):"

43、;);</p><p>　　scanf("%d",&menu);</p><p>　　while(!(menu>=0 && menu<=4))</p><p><b>　　{</b></p><p>　　printf("Your choice number

44、 is not exist,please choose your act number again(0-4):");</p><p>　　scanf("%d",&menu);</p><p><b>　　}</b></p><p>　　while(menu!=0)</p><p>&

45、lt;b>　　{</b></p><p>　　switch(menu)</p><p><b>　　{</b></p><p><b>　　case 1:</b></p><p><b>　　{</b></p><p>　　printf

46、("create bitree(1000 is the end number): \n");</p><p>　　createbst(&root);</p><p>　　display(root);</p><p>　　printf("\n");</p><p><b>　　table

47、();</b></p><p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　case 2:</b></p><p><b>　　{</b></p><p>　　p

48、rintf("Please input key word which you want to search:");</p><p>　　scanf("%d",&data);</p><p>　　printf("%d\n",searchbst(root,data));</p><p>　　printf

49、("(1000 stand for failing to search the key number)\n");</p><p><b>　　table();</b></p><p><b>　　break;</b></p><p><b>　　}</b></p>&

50、lt;p><b>　　case 3:</b></p><p><b>　　{</b></p><p>　　printf("Please the key word you want to insert:");</p><p>　　scanf("%d",&data);<

51、;/p><p>　　insertbst(&root,data);</p><p>　　display(root);</p><p>　　printf("\n");table();</p><p><b>　　break;</b></p><p><b>　　}&l

52、t;/b></p><p><b>　　case 4:</b></p><p><b>　　{</b></p><p>　　printf("Please input the key word you want to delete:");</p><p>　　scanf(&q

53、uot;%d",&data);</p><p>　　deletebst(root,data);</p><p>　　display(root);</p><p>　　printf("\n");table();</p><p><b>　　break;</b></p>&

54、lt;p><b>　　}</b></p><p><b>　　}</b></p><p>　　printf("please continue to choose your action number:");</p><p>　　scanf("%d",&menu);<