數(shù)據(jù)結(jié)構(gòu)二叉排序樹課程設(shè)計(jì)報(bào)告

上傳人：奔*** IP屬地：河北更新時(shí)間：2024-04-02 格式：doc 頁數(shù)：17 大?。?40.50KB 人氣指數(shù)：12 舉報(bào) 版權(quán)申訴

數(shù)據(jù)結(jié)構(gòu)二叉排序樹課程設(shè)計(jì)報(bào)告_第1頁

已閱讀1頁，還剩16頁未讀，繼續(xù)免費(fèi)閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

1、　　課程設(shè) 計(jì) 報(bào) 告　　——數(shù)據(jù)結(jié)構(gòu)　　題目：二叉排序樹　　姓名： 　　學(xué) 號(hào)：</p&

2、gt;　　專業(yè)：　　班級(jí)： 　　指導(dǎo)老師： 　　年月日　　目錄&

3、lt;/p>　　一、課程設(shè)計(jì)簡介3　　二、原理分析及流程3　　2.1、原理分析............................................................................3　　2.2、流程圖................

4、................................................................4　　1、main()函數(shù)....................................................................4　　2、創(chuàng)建..........................

5、.....................................................4　　3、插入...............................................................................5　　4、查找................................

6、...............................................6　　5、中序遍歷輸出7　　三、算法描述8　　3.1、存儲(chǔ)結(jié)構(gòu)8　　3.2、插入算法8

7、3.3、查找算法9　　3.4、刪除算法10　　四、小結(jié)與體會(huì)12　　五、程序執(zhí)行過程13　　5.1、創(chuàng)建二叉排序樹并中序輸出.........................................13 5.2、插入并中序輸出..............

8、................................................13　　5.3、查找..................................................................................14　　六、程序清單14</p

9、>　　一、課程設(shè)計(jì)簡介　　1.1、題目：二叉排序樹相關(guān)操作　　1、創(chuàng)建二叉排序樹；2、插入給定值；　　3、查找給定值； 4、刪除給定值的結(jié)點(diǎn)。　　1.2、報(bào)告要求：

10、;　　1、封面; 2、題目與流程圖或模塊圖;　　3、程序清單和運(yùn)行結(jié)果; 4、小結(jié)(收獲和體會(huì));　　5、裝訂成冊(cè)。　　1.3、目的：<

11、;p>　　課程設(shè)計(jì)為學(xué)生提供了一個(gè)既動(dòng)手又動(dòng)腦，獨(dú)立實(shí)踐的機(jī)會(huì)，將課本上的理論知識(shí)和實(shí)際有機(jī)的結(jié)合起來，鍛煉學(xué)生的分析解決實(shí)際問題的能力。提高學(xué)生適應(yīng)實(shí)際，實(shí)踐編程的能力。　　二、原理分析及流程　　2.1、原理分析：　　根據(jù)題目要求

12、，要實(shí)現(xiàn)這些功能，就必須創(chuàng)建一個(gè)菜單。這個(gè)菜單設(shè)置在main（）函數(shù)里面，然后使用while()...switch()語句進(jìn)行循環(huán)調(diào)用相關(guān)函數(shù)，以達(dá)到實(shí)現(xiàn)相關(guān)功能的目的。　　2.2、流程圖：　　1、main（）函數(shù)：　　2、創(chuàng)建：<

13、/p>　　3、插入：　　N　　Y　　N　　Y</

14、p>　　4、查找：　　Y　　N　　YN　　5、中序遍歷輸出：</b

15、>　　三、算法描述　　3.1、存儲(chǔ)結(jié)構(gòu)　　定義一個(gè)鏈表式的二叉排序樹，用鏈表的方式構(gòu)造結(jié)點(diǎn)，存儲(chǔ)二叉排序樹中的結(jié)點(diǎn)、結(jié)點(diǎn)類型和指針類型如下：　　#include <stdio.h>

16、;　　#define null 0　　typedef int keytype;　　typedef struct node　　{　　keytype key;<p&g

17、t;　　struct node *lchild,*rchild;　　}bstnode,*bstree;　　3.2、插入算法　　在二叉排序樹中插入一個(gè)新節(jié)點(diǎn)，首先要查找該節(jié)點(diǎn)在二叉排序樹中是否已經(jīng)存在。若二叉排序樹中不存在關(guān)鍵字等于x的節(jié)點(diǎn)，則插入。&l

18、t;p>　　將一個(gè)關(guān)鍵字值為x的節(jié)點(diǎn)s插入到二叉排序樹中，可以用下面的方法：　?。?）若二叉排序樹為空，則關(guān)鍵字為x的節(jié)點(diǎn)s成為二叉排序樹的根　?。?）若二叉排序樹非空，則將x與二叉排序樹根進(jìn)行比較，如果x的值等于根節(jié)點(diǎn)關(guān)鍵值，則停止插入；如果x的根節(jié)點(diǎn)值小于根節(jié)點(diǎn)關(guān)鍵值，則將x插入左子樹；如果x的值大于根節(jié)點(diǎn)關(guān)鍵字的值，則將x插入右子樹。在左右兩

19、個(gè)子樹的插入方法與整個(gè)二叉排序樹相同。　　算法如下：　　void insert(bstree *t,keytype x)　　{　　bstree s;</

20、p>　　if(*t==null)　　{　　s=(bstree)malloc(sizeof(bstnode));　　s->key=x;　　s->lchild=

21、null;　　s->rchild=null;　　*t=s;　　}　　else if(x<(*t)->key)　　insert(&

22、((*t)->lchild),x);　　else if(x>(*t)->key)　　insert(&((*t)->rchild),x);　　} 　　3.3、查找算法

23、　　（1）若二叉排序樹不為空，將根結(jié)點(diǎn)的關(guān)鍵字與待查關(guān)鍵字進(jìn)行比較，若相等，則查找成功；若根節(jié)點(diǎn)關(guān)鍵字大于待查值，則進(jìn)入左子樹重復(fù)次步驟，否則，進(jìn)入右子樹進(jìn)行此步驟；若在查找過程中遇到二叉排序樹的葉子節(jié)點(diǎn)時(shí)，還沒有找到待查節(jié)點(diǎn)，則查找不成功。　?。?）否則，查找失敗，返回null。　　算法如下：

24、　　bstree search(bstree t,keytype x)　　{　　bstree p;　　p=t;&l

25、t;p>　　if(p!=null)　　{　　if (x==p->key) return p->key;　　else if(x<p->key) return search(p->lchild,x);

26、　else return search(p->rchild,x);　　}　　else　　{ printf("%d can not be found\n",x);return null;&l

27、t;p>　　}　　}　　3.4、刪除算法　　在二叉排序樹中刪除節(jié)點(diǎn)，首先要確定被刪除的節(jié)點(diǎn)是否在二叉排序樹中。　　若不在，則不做任何操作；否則，假設(shè)要?jiǎng)h

28、除的節(jié)點(diǎn)為p，節(jié)點(diǎn)p的父節(jié)點(diǎn)為r，并假設(shè)p是r的左孩子。根據(jù)被刪除節(jié)點(diǎn)p有無孩子，刪除部分可做以下3中情況討論：　?。?）若p為葉子節(jié)點(diǎn)，則可令其父節(jié)點(diǎn)r的左孩子指針域?yàn)榭?，直接將其刪除。　?。?）若p節(jié)點(diǎn)只有右子樹或左子樹，則可以將p的左子樹或右子樹直接改為其雙親節(jié)點(diǎn)r的左子樹。　?。?）若p既有左子樹又有右子

29、樹；將節(jié)點(diǎn)s為p的中序前驅(qū)。首先找到p的中序前驅(qū)節(jié)點(diǎn)s，然后用節(jié)點(diǎn)s的值代替節(jié)點(diǎn)p的值，再將節(jié)點(diǎn)s刪除，節(jié)點(diǎn)s的原左子樹改為s的雙親節(jié)點(diǎn)q的右子樹。　　算法如下：　　bstree delete(bstree t,keytype x)　　{

30、　　bstree p,q,r,s;　　p=t;　　r=null;　　while(p)　　{<

31、/b>　　if(x==p->key) break;　　r=p;　　if(x<p->key) p=p->lchild;　　else p=p->rchild;

32、;　　}　　if(p==null) {printf("%d is not exist!\n",x);return t;}　　if((p->lchild==null)||(p->rchild==null))<b&g

33、t;　　{　　if(r==null)　　if(p->lchild==null)　　t=p->rchild;　　else t=p->lchild;　　else if(p->lchild=

34、=null)　　if(r->lchild==p)　　r->lchild=p->rchild;　　else r->rchild=p->rchild;　　else if(r->lchild==p)

35、　r->lchild=p->lchild;　　else r->lchild=p->lchild;　　free(p);　　}　　else

36、　　{　　q=p;　　s->lchild;　　while(s->rchild)　　{q=s;s->rchild;}

37、　　if(q==p) q->lchild=s->lchild;　　else p->key=s->key;　　free(s);　　}<b

38、>　　return t;　　}　　四、小結(jié)與體會(huì)　　經(jīng)過一個(gè)多星期來夜以繼日的努力，終于把課程設(shè)計(jì)——二叉排序樹的相關(guān)算法全部完成！在編寫程序過程中，讓我對(duì)二叉排序樹的創(chuàng)建、插入、查找、刪除算法有了較系統(tǒng)的認(rèn)識(shí)，

39、也發(fā)現(xiàn)了一些以前紙上談兵時(shí)的思想誤區(qū)。比如實(shí)現(xiàn)插入功能時(shí)，從根節(jié)點(diǎn)開始比較；當(dāng)實(shí)現(xiàn)刪除功能時(shí)，如果待刪除結(jié)點(diǎn)p左、右子樹齊全，首先找到p的中序前驅(qū)節(jié)點(diǎn)s（p的中序前驅(qū)），然后用節(jié)點(diǎn)s的值代替節(jié)點(diǎn)p的值，再將節(jié)點(diǎn)s刪除，節(jié)點(diǎn)s的原左子樹改為s的雙親節(jié)點(diǎn)q的右子樹。實(shí)現(xiàn)中序遍歷功能時(shí)，采用遞歸思想......　　這是第一次關(guān)于編寫程序的課程設(shè)計(jì)。雖然上機(jī)安排只有兩天時(shí)間，可卻并不像平時(shí)上機(jī)實(shí)驗(yàn)一樣，

40、離開了機(jī)房就不用再對(duì)著電腦屏幕編寫代碼，更多的工作實(shí)在離開機(jī)房后完成的。一遍一遍地按F9調(diào)試程序，error從幾十個(gè)減少到幾個(gè)，再到只剩幾個(gè)warring，當(dāng)按下Ctrl+F9，那精心設(shè)計(jì)的“菜單”出現(xiàn)在屏幕上時(shí)，那一刻的心情無以言表！涌上心頭的除了自豪感、成就感之外，還有對(duì)編程工作之辛苦的慨嘆！因?yàn)樽约簩I(yè)將來的方向與這有關(guān)，不免讓我考慮起畢業(yè)后的發(fā)展方向。如果朝這方面發(fā)展的話，我是否可以勝任這樣的工作？如果不是，又該選擇什么？<

41、;/p>　　程序執(zhí)行過程　　5.1、創(chuàng)建二叉排序樹并中序輸出　　5.2插入并中序輸出　　5.3、查找　　5.4、刪除并中序輸出

42、　　六、程序清單　　#include <stdio.h>　　#define null 0　　typedef int keytype;　　typedef struct node<

43、;b>　　{　　keytype key;　　struct node *lchild,*rchild;　　}bstnode,*bstree;　　void insert(bstree *t,keytype x);<p&g

44、t;　　bstree search(bstree t,keytype x);　　void display(bstree t);　　void create(bstree *t)　　{　　keytype x;<

45、;p>　　*t=null;　　scanf("%d",&x);　　while(x!=-1)　　{　　insert(t,x);

46、;　　scanf("%d",&x);　　}　　}　　void insert(bstree *t,keytype x)　　{<

47、/p>　　bstree s;　　if(*t==null)　　{　　s=(bstree)malloc(sizeof(bstnode));　　s->

48、key=x;　　s->lchild=null;　　s->rchild=null;　　*t=s;　　}　　else if(x

49、<(*t)->key)　　insert(&((*t)->lchild),x);　　else if(x>(*t)->key)　　insert(&((*t)->rchild),x);　　}

50、;　　bstree search(bstree t,keytype x)　　{　　bstree p;　　p=t;

51、if(p!=null)　　{　　if (x==p->key) return p->key;　　else if(x<p->key) return search(p->lchild,x);　　else ret

52、urn search(p->rchild,x);　　}　　else　　{ printf("%d can not be found\n",x);　　return null;

53、　　}　　}　　bstree delete(bstree t,keytype x)　　{　　bstree p,q,r

54、,s;　　p=t;　　r=null;　　while(p)　　{　　if(x==

55、p->key) break;　　r=p;　　if(x<p->key) p=p->lchild;　　else p=p->rchild;　　}&

56、lt;/p>　　if(p==null) {printf("%d is not exist!\n",x);return t;}　　if((p->lchild==null)||(p->rchild==null))　　{

57、;　　if(r==null)　　if(p->lchild==null)　　t=p->rchild;　　else　　t=p->lchild;　　else if(p->lc

58、hild==null)　　if(r->lchild==p)　　r->lchild=p->rchild;　　else　　r->rchild=p->rchild;

59、else if(r->lchild==p)　　r->lchild=p->lchild;　　else　　r->lchild=p->lchild;　　free(p);&l

60、t;/p>　　}　　else　　{　　q=p;　　s->lchild;</p&g

61、t;　　while(s->rchild)　　{q=s;s->rchild;}　　if(q==p)　　q->lchild=s->lchild;　　else

62、;　　p->key=s->key;　　free(s);　　}　　return t;

63、}　　void display(bstree t)　　{　　if(t!=null)　　{　　display(t->lchild)

64、;　　printf("%5d",t->key);　　display(t->rchild);　　}　　}　　void mai

65、n(void)　　{　　bstree t,b;　　int i=1,j;　　keytype x;　　while(i)

66、;　　{　　printf("\n* * * * * * * * * * * * * * * *\n");　　printf("\n* MENU OF BSTREE *\n");　　printf("\n*

67、 1.create 2.insert *\n");　　printf("\n* 3.search 4.delete *\n");　　printf("\n* 5.exit *\n");

68、　printf("\n* * * * * * * * * * * * * * * *\n");　　printf(" what do you want to do? :");scanf("%d",&j);　　switch(j)&

69、lt;p>　　{　　case 1: printf("input bstree's values,end with -1:\n");create(&t);　　printf("bstree's root is %d\n",t->key);di

70、splay(t);break;　　case 2: printf("input the insert value:");scanf("%d",&x);　　insert(&t,x);display(t);break;　　case 3: printf(&q

71、uot;input the search value:");scanf("%d",&x);　　printf("result is: %d",search(t,x));break;　　case 4: printf("input the delete value:");scan

72、f("%d",&x);　　delete(t,x);display(t);break;　　case 5: i=0;break;　　}　　}&l

眾賞文庫> 全部分類> 畢業(yè)設(shè)計(jì)

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲(chǔ)空間，僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請(qǐng)與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

數(shù)據(jù)結(jié)構(gòu)二叉排序樹課程設(shè)計(jì)報(bào)告

文檔簡介

溫馨提示

最新文檔

評(píng)論

數(shù)據(jù)結(jié)構(gòu)二叉排序樹課程設(shè)計(jì)報(bào)告

文檔簡介

溫馨提示

最新文檔

評(píng)論

免費(fèi)下載