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

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

2、</p><p><b>　　學(xué) 號(hào) ： </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)，簡(jiǎn)稱數(shù)據(jù)結(jié)構(gòu)。當(dāng)數(shù)據(jù)的邏輯結(jié)構(gòu)確定以后，數(shù)據(jù)在物理空間中的存儲(chǔ)方式，稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。同一邏輯結(jié)構(gòu)可以具有不同的存儲(chǔ)結(jié)構(gòu)，因而有不同的算法。本次課程設(shè)計(jì)，程序中的數(shù)據(jù)采用“二叉樹結(jié)構(gòu)”。具體采用的是“二叉排序樹”，并且使用“一維數(shù)組”作為其存儲(chǔ)結(jié)構(gòu)。一維數(shù)組順序表存儲(chǔ)結(jié)構(gòu)是用一組地址連續(xù)的存儲(chǔ)單元依次自左而右、自上而下存儲(chǔ)二叉排序樹的結(jié)點(diǎn)元素；本課程設(shè)計(jì)實(shí)現(xiàn)了二叉排序樹的創(chuàng)建、查找、插入、刪除，中序遍歷

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

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

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

7、結(jié)點(diǎn)至少包含3個(gè)域：數(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è)計(jì)：</p><p>　　本系統(tǒng)設(shè)置了5子功能菜單，5個(gè)子功能的設(shè)計(jì)描述如下。</p><p>　　建立二叉排序樹，由函

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

10、tree t,int k)來實(shí)現(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)過一個(gè)星期的課程設(shè)計(jì)，過程曲折可謂一語難盡。整天都是對(duì)著電腦，不然就是翻閱資料。在此期間我失落過，也曾一度熱情高漲。點(diǎn)點(diǎn)滴滴令我回味無窮。這次課程設(shè)計(jì)使我體會(huì)到只有做到細(xì)心耐心，恒心才能做好一件事。</p><p>　　這次的課程設(shè)計(jì)，加強(qiáng)了我們動(dòng)手、思考和解決問題的能力。鞏固和加深

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

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

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

16、解到數(shù)據(jù)結(jié)構(gòu)的重要性。此次課程設(shè)計(jì)，學(xué)到了很多課內(nèi)學(xué)不到的東西，比如獨(dú)立思考解決問題的能力，出現(xiàn)差錯(cuò)的隨機(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);<