數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告---帶父親節(jié)點(diǎn)的平衡二叉樹的建立

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

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

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

文檔簡介

1、　　課程設(shè) 計(jì) 報(bào) 告　　課程設(shè)計(jì)名稱：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)　　課程設(shè)計(jì)題目：帶父親節(jié)點(diǎn)的平衡二叉樹的建立　　院（系）：計(jì)算機(jī)學(xué)院　　專業(yè)：網(wǎng)絡(luò)工程　　班級(jí)：

2、　　學(xué) 號(hào)：　　姓名：　　指導(dǎo)教師：　　目錄　　1 課

3、程設(shè)計(jì)介紹1　　1.1 課程設(shè)計(jì)內(nèi)容1　　1.2課程設(shè)計(jì)要求1　　2 課程設(shè)計(jì)原理2　　2.1 課設(shè)題目粗略分析2　　2.2 原理圖介紹2　　2.2.1 功能模塊圖2<

4、;/p>　　2.2.2 流程圖分析3　　3 數(shù)據(jù)結(jié)構(gòu)分析8　　3.1 存儲(chǔ)結(jié)構(gòu)8　　3.2 算法描述8　　4 調(diào)試與分析10　　4.1 調(diào)試過程10<p&g

5、t;　　1.2程序執(zhí)行過程11　　參考文獻(xiàn)12　　附錄（關(guān)鍵部分程序清單）13　　1 課程設(shè)計(jì)介紹　　1.1 課程設(shè)計(jì)內(nèi)容　　設(shè)計(jì)程序，建

6、立帶有父親結(jié)點(diǎn)的平衡二叉樹，系統(tǒng)主要功能是：從鍵盤上輸入一整數(shù)序列，建立一顆平衡二叉樹。　　1.2課程設(shè)計(jì)要求　　要能夠形象方便的觀察樹的結(jié)構(gòu)；　　要能夠形象的演示樹的平衡過程；　　課程設(shè)計(jì)報(bào)告必須符合課程設(shè)計(jì)報(bào)告規(guī)范；</p&

7、gt;　　提交合格的報(bào)告后，經(jīng)指導(dǎo)老師測試程序后，課設(shè)完成。　　2 課程設(shè)計(jì)原理　　2.1 課設(shè)題目粗略分析　　根據(jù)課設(shè)題目要求，我將整體程序分為四大模塊，這四個(gè)模塊相互獨(dú)立，沒有任何嵌套調(diào)用的情況，以下是四個(gè)模塊的大體分析：&

8、lt;p>　　(1)判斷模塊：在插入一個(gè)關(guān)鍵字時(shí)，首先先對該關(guān)鍵字進(jìn)行判斷，如果該關(guān)鍵字已經(jīng)存在則不插入，否則插入該關(guān)鍵字，調(diào)用函數(shù)InsertAVL（）。　　(2)左子樹插入模塊：如果判斷完的新關(guān)鍵字插在左子樹上，則對該以指針p所指結(jié)點(diǎn)為根的二叉樹作左平衡旋轉(zhuǎn)處理，本算法結(jié)束時(shí)，指針p指向新的根結(jié)點(diǎn)，調(diào)用函數(shù)LeftProcess（）。　　(3)

9、右子樹插入模塊：如果判斷完的新關(guān)鍵字插在右子樹上，則對該以指針p所指結(jié)點(diǎn)為根的二叉樹作右平衡旋轉(zhuǎn)處理，本算法結(jié)束時(shí)，指針p指向新的根結(jié)點(diǎn)，調(diào)用函數(shù)RightProcess（）。　　(4)輸出模塊：對建立完成的平衡二叉樹輸出，輸出格式為二叉樹的括號(hào)表示，且每一步插入操作對應(yīng)一次輸出，最后做一次總體輸出，調(diào)用函數(shù)，DispBSTree（）。

10、　　2.2 原理圖介紹　　主函數(shù)主要實(shí)現(xiàn)的功能是函數(shù)調(diào)用，主函數(shù)首先對輸入的關(guān)鍵字進(jìn)行判斷，調(diào)用函數(shù)InsertAVL（），若該關(guān)鍵字在已建樹中已經(jīng)存在，則返回主函數(shù)接著對下一個(gè)關(guān)鍵字進(jìn)行判斷。若該關(guān)鍵字在已建樹中不存在，則插入該數(shù)，若插入左子樹中則調(diào)用函數(shù)LeftProcess（）進(jìn)行插入操作，若插入右子樹中則調(diào)用函數(shù)DispBSTree（）進(jìn)行插入操作。當(dāng)所有的關(guān)鍵字都插

11、入完事之后，進(jìn)行輸出，調(diào)用函數(shù)，DispBSTree（）。　　2.2.1 功能模塊圖　　1.判斷模塊 　　若在平衡二叉排序樹b中不存在和e有相同關(guān)鍵字的結(jié)點(diǎn)，則插入一個(gè)數(shù)據(jù)元素為e的新結(jié)點(diǎn)，并返回1，否則返回0。若因插入而使二叉排序樹失去平衡，則作平衡旋轉(zhuǎn)處理，布爾變量ta

12、ller反映b長高與否。　　2.左子樹插入模塊　　對以指針p所指結(jié)點(diǎn)為根的二叉樹作左平衡旋轉(zhuǎn)處理，本算法結(jié)束時(shí)，指針p指向新的根結(jié)點(diǎn)，插入分三種情況：原本左右子樹等高，現(xiàn)因左子樹增高而使樹增；原本右子樹比左子樹高，現(xiàn)左右子樹等高；原本左子樹比右子樹高，須作左子樹的平衡處理。若新關(guān)鍵字插入在*p的左孩子的左子樹上，要做

13、LL調(diào)整，若新關(guān)鍵字插入在*p的左孩子的右子樹上，要做LR調(diào)整。　　3.右子樹子樹插入模塊　　對以指針p所指結(jié)點(diǎn)為根的二叉樹作右平衡旋轉(zhuǎn)處理，本算法結(jié)束時(shí)，指針p指向新的根結(jié)點(diǎn)，插入分三種情況：原本左右子樹等高，現(xiàn)因右子樹增高而使樹增；原本左子樹比右子樹高，現(xiàn)左右子樹等高；原本右子樹比左子樹高，須作右子樹的平衡處理。若新關(guān)鍵字插入在*p的右孩子的右子樹上

14、，要做RR調(diào)整，若新關(guān)鍵字插入在*p的右孩子的左子樹上，要做RL調(diào)整。　　2.2.2 流程圖分析　　1．主函數(shù)流程圖　　主函數(shù)主要實(shí)現(xiàn)的功能是函數(shù)調(diào)用，主函數(shù)首先對輸入的關(guān)鍵字進(jìn)行判斷，若該關(guān)鍵字在已建樹中已經(jīng)存在，則返回主函數(shù)接著對下一個(gè)關(guān)鍵字進(jìn)行判斷。若該關(guān)鍵字在已建樹中

15、不存在，則插入該數(shù)，當(dāng)所有的關(guān)鍵字都插入完事之后，進(jìn)行輸出。流程圖如圖2.1所示。　　圖2.1 主函數(shù)流程圖　　2．判斷模塊流程圖　　若在平衡二叉排序樹b中不存在和e有相同關(guān)鍵字的結(jié)點(diǎn)，則插入一個(gè)數(shù)據(jù)元素為e的新結(jié)點(diǎn)，并返回1，否則返回0。若因插入而使二叉排序樹失去平衡，則作

16、平衡旋轉(zhuǎn)處理，布爾變量taller反映b長高與否。流程圖如圖2.2所示。　　圖2.2 判斷模塊流程圖　　3．左子樹插入模塊流程圖 　　斷完的新關(guān)鍵字插在左子樹上，則對該以指針p所指結(jié)點(diǎn)為根的二叉樹作左平衡旋轉(zhuǎn)處理，本算法結(jié)束時(shí)，指針p指向新的根結(jié)針。流程圖如圖2.3所示。

17、　　圖2.3左子樹插入模塊流程圖　　4．右子樹插入模塊流程圖　　斷完的新關(guān)鍵字插在右子樹上，則對該以指針p所指結(jié)點(diǎn)為根的二叉樹作右平衡旋轉(zhuǎn)處理，本算法結(jié)束時(shí)，指針p指向新的根結(jié)針。流程圖如圖2.4所示。　　圖2.4 右子樹插入模塊流程圖　　3 數(shù)據(jù)結(jié)構(gòu)

18、分析　　3.1 存儲(chǔ)結(jié)構(gòu)　　定義一個(gè)關(guān)鍵字類型的字符數(shù)組，其空間足夠大，用來存放關(guān)鍵字。　　3.2 算法描述　　1．判斷關(guān)鍵字算法如下：

19、;　　{//若在平衡二叉排序樹b中不存在和e有相同關(guān)鍵字的結(jié)點(diǎn)，則插入一個(gè)數(shù)據(jù)元素為e的新結(jié)點(diǎn)，　　if(b==NULL) //原樹為空，插入新結(jié)點(diǎn)，樹長高，置taller為1　　{b=(BSTNode*)malloc(sizeof(BSTNode));　　b->key=e;</

20、b>　　b->lchild=b->rchild=NULL;　　b->bf=0;　　taller=1;}　　else　　{if(e=

21、=b->key) //樹中已存在和e有相同關(guān)鍵字的結(jié)點(diǎn)則不插入　　{taller=0;　　return 0;}　　if(e<b->key) //繼續(xù)在*b的左子樹中進(jìn)行搜索　　{if((InsertAVL(b->lchild,e,

22、taller))==0) //未插入　　return 0;　　if(taller==1) //已插入到*b的左子樹中且左子樹長高　　LeftProcess(b,taller);}　　else

23、 //繼續(xù)在*b的右子樹中進(jìn)行搜索　　{if((InsertAVL(b->rchild,e,taller))==0) //未插入　　return 0;　　if(taller==1) //已插入到*

24、b的右子樹中且右子樹長高 　　RightProcess(b,taller);}}　　return 1;}　　2.左平衡處理算法如下：　　{//對以指針p所指結(jié)點(diǎn)為根的二叉樹作左平衡旋轉(zhuǎn)處理，本算法結(jié)束時(shí)，　　//指針p指向新的根

25、結(jié)點(diǎn)　　BSTNode *p1,*p2;　　if(p->bf==0) //原本左右子樹等高，現(xiàn)因左子樹增高而使樹增高　　{p->bf=1;　　taller=1;}

26、;　　else if(p->bf==-1) //原本右子樹比左子樹高，現(xiàn)左右子樹等高　　{p->bf=0;　　taller=0;}　　else //原本左子樹比右子樹高，須作左子樹的平衡處理&l

27、t;p>　　{p1=p->lchild; //p指向*p的左子樹根節(jié)點(diǎn)　　if(p1->bf==1) //新結(jié)點(diǎn)插入在*p的左孩子的左子樹上，要做LL調(diào)整　　{p->lchild=p1->rchild;　　p1->rchild=p;

28、　　p->bf=p1->bf=0;　　p=p1; }　　else if(p1->bf==-1) //新結(jié)點(diǎn)插入在*p的左孩子的右子樹上，要做LR調(diào)整　　{p2=p1->rchild;　　p1

29、->rchild=p2->lchild;　　p2->lchild=p1;　　p->lchild=p2->rchild;　　p2->rchild=p;　　if(p2->bf==0) //新結(jié)點(diǎn)插入在*p2處作為葉子結(jié)點(diǎn)的情

30、況　　p->bf=p1->bf=0;　　else if(p2->bf==1) /新結(jié)點(diǎn)插在*p2的左子樹上的情況　　{p1->bf=0;　　p->bf=-1;}　　else //

31、新結(jié)點(diǎn)插在*p2的右子樹上的情況　　{p1->bf=1;　　p->bf=0;}　　p=p2;　　p->bf=0; //仍將p指向新的根結(jié)點(diǎn)，并置其bf值為

32、0 　　taller=0;}　　}　　4 調(diào)試與分析　　4.1 調(diào)試過程　　在調(diào)試程序是主要遇到一下幾類問題：&l

33、t;/p>　　本程序用到指針的地方特別多，由于指針那部分知識(shí)我掌握的不是很好，故而在這方面有困難。后來我通過在圖書館查資料、看書解決了這方面問題。　　對二叉樹的左右子樹進(jìn)行插入調(diào)整的操作時(shí)，由于考慮問題不夠全面而導(dǎo)致輸出結(jié)果出現(xiàn)錯(cuò)誤，在查質(zhì)料重新學(xué)習(xí)二叉樹后，解決了此問題。　　4.1程序執(zhí)行過程</b&

34、gt;　　圖4.1 第一組輸入執(zhí)行結(jié)果　　圖4.2 第二組輸入執(zhí)行結(jié)果　　參考文獻(xiàn)　　[1] 嚴(yán)蔚敏.吳偉民.數(shù)據(jù)結(jié)構(gòu)[M].北京：清華大學(xué)出版社，2007.　　[2] 張長海.陳娟.C程序設(shè)

35、計(jì)[M].北京：高等教育出版社，2004. 　　[3] 譚浩強(qiáng).C程序設(shè)計(jì)[M].北京：清華大學(xué)出版社，2005.　　[4] 徐孝凱.數(shù)據(jù)結(jié)構(gòu)實(shí)用教程.[M].北京：清華大學(xué)出版社，2006.　　[5] 張秉權(quán).數(shù)據(jù)結(jié)構(gòu)（C語言描述）.[M].北京：中國輕工業(yè)出版社，2004.<p&

36、gt;　　附錄（關(guān)鍵部分程序清單）　　程序代碼　　#include<stdio.h>　　#include<malloc.h>　　typedef int KeyType<p&g

37、t;　　typedef struct node　　{KeyType key;　　int bf;　　struct node *lchild,*rchild;　　}BSTNode;

38、　　void LeftProcess(BSTNode *&p,int &taller)　　{ /*對以指針p所指結(jié)點(diǎn)為根的二叉樹作左平衡旋轉(zhuǎn)處理，本算法結(jié)束時(shí)指針p指向新結(jié)點(diǎn)*/　　BSTNode *p1,*p2;<p&

39、gt;　　if(p->bf==0)　　{p->bf=1;　　taller=1;　　}　　else if(p->bf==-1)</p&g

40、t;　　{p->bf=0;　　taller=0;　　}　　else　　{p1=p->l

41、child　　if(p1->bf==1)　　{p->lchild=p1->rchild;　　p1->rchild=p;　　p->bf=p1->bf=0;　　p=p1;</

42、b>　　}　　else if(p1->bf==-1)　　{p2=p1->rchild;　　p1->rchild=p2->lchild;　　p2->lchil

43、d=p1;　　p->lchild=p2->rchild;　　p2->rchild=p;　　if(p2->bf==0)　　p->bf=p1->bf=0;　　else if(p2->bf==1

44、)　　{p1->bf=0;　　p->bf=-1;　　}　　else　　{p1->bf=1;<

45、/p>　　p->bf=0;　　}　　p=p2;　　p->bf=0;<b&g

46、t;　　}　　taller=0;　　}　　}　　void RightProcess(BSTNode *&p,int &ta

47、ller)　　{ /*對以指針p所指結(jié)點(diǎn)為根的二叉樹作右平衡旋轉(zhuǎn)處理，本算法結(jié)束時(shí)，指針p指向新的根結(jié)點(diǎn)*/　　BSTNode *p1,*p2;　　if(p->bf==0)　　{p-&

48、gt;bf=-1;　　taller=1;　　}　　else if(p->bf==1)　　{p->bf=0;

49、;　　taller=0;　　}　　else　　{p1=p->rchild;　　if(p1->bf==-1)

50、;　　{p->rchild=p1->lchild;　　p1->lchild=p;　　p->bf=p1->bf=0;　　p=p1;　　}<

51、p>　　else if(p1->bf==1)　　{p2=p1->lchild;　　p1->lchild=p2->rchild;　　p2->rchild=p1;　　p->rchild=p2->lchild;

52、　　p2->lchild=p;　　if(p2->bf==0)　　p->bf=p1->bf=0;　　else if(p2->bf==-1)　　{p1->bf=0;<b&

53、gt;　　p->bf=1;　　}　　else　　{p1->bf=-1;　　p->bf=0;<

54、;p>　　}　　p=p2;　　p->bf=0;　　taller=0;　　}</b&g

55、t;　　}　　int InsertAVL(BSTNode*&b,KeyType e,int &taller)　　{ /*若在平衡二叉排序樹b中不存在和e有相同關(guān)鍵字的結(jié)點(diǎn)，則插入一個(gè)

56、數(shù)據(jù)元素為e的新結(jié)點(diǎn)，并返回1，否則返回0。若因插入而使二叉排序樹失去平衡，則作平衡旋轉(zhuǎn)處理，布爾變taller　　反映b長高與否*/　　if(b==NULL)　　{b=(BSTNode*)malloc(sizeof(BSTNode));<p&g

57、t;　　b->key=e;　　b->lchild=b->rchild=NULL;　　b->bf=0;　　taller=1;<b&

58、gt;　　}　　else　　{if(e==b->key)　　{taller=0;　　return 0;　　}&

59、lt;/b>　　if(e<b->key)　　{if((InsertAVL(b->lchild,e,taller))==0)　　return 0;　　if(taller==1)<p&

60、gt;　　LeftProcess(b,taller);　　}　　else 　　{if((InsertAVL(b->rchild,e,taller))==0)　　return

61、 0;　　if(taller==1)　　RightProcess(b,taller);　　}　　}　　return

62、1;　　}　　void DispBSTree(BSTNode *b)　　{ /*以括號(hào)表示法輸出AVL*/　　if(b!=NULL)

63、　　{printf("%d",b->key);　　if(b->lchild!=NULL||b->rchild!=NULL)　　{printf("(");　　DispBSTree(b->lchild);<

64、p>　　if(b->rchild!=NULL)printf(",");　　DispBSTree(b->rchild);　　printf(")");　　}　　}

65、　　}　　int main()　　{　　BSTNode *b=NULL;　　int i,j;&l

66、t;/p>　　KeyType a[]={6,1,2,3,4,5,0,7,8,9},n=10;　　printf("創(chuàng)建一棵AVL樹:\n");　　for(i=0;i<n;i++)　　{printf("第%d步，插入%d元素:",i+1,a[i

67、]);　　InsertAVL(b,a[i],j);　　DispBSTree(b);　　printf("\n");　　}　　printf("AVL:");

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

溫馨提示

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

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告---帶父親節(jié)點(diǎn)的平衡二叉樹的建立

文檔簡介

溫馨提示

最新文檔

評論

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告---帶父親節(jié)點(diǎn)的平衡二叉樹的建立

文檔簡介

溫馨提示

最新文檔

評論

免費(fèi)下載