數據結構二叉排序樹課程設計報告

上傳人：奔*** IP屬地：河北更新時間：2024-04-02 格式：doc 頁數：17 大?。?40.50KB 人氣指數：12 舉報 版權申訴

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

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

1、　　課程設計報告　　——數據結構　　題目：二叉排序樹　　姓名： 　　學號：</p&

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

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

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

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

6、...............................................6　　5、中序遍歷輸出7　　三、算法描述8　　3.1、存儲結構8　　3.2、插入算法8

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

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

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

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

11、;p>　　課程設計為學生提供了一個既動手又動腦，獨立實踐的機會，將課本上的理論知識和實際有機的結合起來，鍛煉學生的分析解決實際問題的能力。提高學生適應實際，實踐編程的能力。　　二、原理分析及流程　　2.1、原理分析：　　根據題目要求

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

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

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

15、>　　三、算法描述　　3.1、存儲結構　　定義一個鏈表式的二叉排序樹，用鏈表的方式構造結點，存儲二叉排序樹中的結點、結點類型和指針類型如下：　　#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、插入算法　　在二叉排序樹中插入一個新節(jié)點，首先要查找該節(jié)點在二叉排序樹中是否已經存在。若二叉排序樹中不存在關鍵字等于x的節(jié)點，則插入。&l

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

19、個子樹的插入方法與整個二叉排序樹相同。　　算法如下：　　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、　?。?）若二叉排序樹不為空，將根結點的關鍵字與待查關鍵字進行比較，若相等，則查找成功；若根節(jié)點關鍵字大于待查值，則進入左子樹重復次步驟，否則，進入右子樹進行此步驟；若在查找過程中遇到二叉排序樹的葉子節(jié)點時，還沒有找到待查節(jié)點，則查找不成功。　?。?）否則，查找失敗，返回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é)點，首先要確定被刪除的節(jié)點是否在二叉排序樹中。　　若不在，則不做任何操作；否則，假設要刪

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

29、樹；將節(jié)點s為p的中序前驅。首先找到p的中序前驅節(jié)點s，然后用節(jié)點s的值代替節(jié)點p的值，再將節(jié)點s刪除，節(jié)點s的原左子樹改為s的雙親節(jié)點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;　　}　　四、小結與體會　　經過一個多星期來夜以繼日的努力，終于把課程設計——二叉排序樹的相關算法全部完成！在編寫程序過程中，讓我對二叉排序樹的創(chuàng)建、插入、查找、刪除算法有了較系統(tǒng)的認識，

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

40、離開了機房就不用再對著電腦屏幕編寫代碼，更多的工作實在離開機房后完成的。一遍一遍地按F9調試程序，error從幾十個減少到幾個，再到只剩幾個warring，當按下Ctrl+F9，那精心設計的“菜單”出現在屏幕上時，那一刻的心情無以言表！涌上心頭的除了自豪感、成就感之外，還有對編程工作之辛苦的慨嘆！因為自己專業(yè)將來的方向與這有關，不免讓我考慮起畢業(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è)設計

溫馨提示

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

數據結構二叉排序樹課程設計報告

文檔簡介

溫馨提示

最新文檔

評論

數據結構二叉排序樹課程設計報告

文檔簡介

溫馨提示

最新文檔

評論

免費下載