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

沈陽(yáng)航空沈陽(yáng)航空航天大學(xué)航天大學(xué) 課課 程程 設(shè)設(shè) 計(jì)計(jì) 報(bào)報(bào) 告告 課程設(shè)計(jì)名稱：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 課程設(shè)計(jì)題目：帶父親節(jié)點(diǎn)的平衡二叉樹(shù)的帶父親節(jié)點(diǎn)的平衡二叉樹(shù)的 建立建立 院（系）：計(jì)算機(jī)學(xué)院 專 業(yè)：網(wǎng)絡(luò)工程 班 級(jí)： 學(xué) 號(hào)： 姓 名：夏媛 指導(dǎo)教師：鄭志勇 沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 i 目目 錄錄 1 1 課程設(shè)計(jì)介紹課程設(shè)計(jì)介紹.1 1.1 課程設(shè)計(jì)內(nèi)容1 1.2 課程設(shè)計(jì)要求.1 2 2 課程設(shè)計(jì)原理課程設(shè)計(jì)原理.2 2.1 課設(shè)題目粗略分析2 2.2 原理圖介紹2 2.2.1 功能模塊圖2 2.2.2 流程圖分析3 3 數(shù)據(jù)結(jié)構(gòu)分析數(shù)據(jù)結(jié)構(gòu)分析.8 3.1 存儲(chǔ)結(jié)構(gòu)8 3.2 算法描述8 4 4 調(diào)試與分析調(diào)試與分析.10 4.1 調(diào)試過(guò)程10 4.1 程序執(zhí)行過(guò)程11 參考文獻(xiàn)參考文獻(xiàn).12 附附 錄（關(guān)鍵部分程序清單）錄（關(guān)鍵部分程序清單）.13 沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 1 1 1 課程設(shè)計(jì)介紹課程設(shè)計(jì)介紹 1.11.1 課程設(shè)計(jì)內(nèi)容課程設(shè)計(jì)內(nèi)容 設(shè)計(jì)程序，建立帶有父親結(jié)點(diǎn)的平衡二叉樹(shù)，系統(tǒng)主要功能是：從鍵盤 上輸入一整數(shù)序列，建立一顆平衡二叉樹(shù)。 1.21.2 課程設(shè)計(jì)要求課程設(shè)計(jì)要求 (1) 要能夠形象方便的觀察樹(shù)的結(jié)構(gòu)； (2) 要能夠形象的演示樹(shù)的平衡過(guò)程； (3) 課程設(shè)計(jì)報(bào)告必須符合課程設(shè)計(jì)報(bào)告規(guī)范； (4) 提交合格的報(bào)告后，經(jīng)指導(dǎo)老師測(cè)試程序后，課設(shè)完成。 沈陽(yáng)航空工業(yè)學(xué)院課程設(shè)計(jì)報(bào)告 2 2 2 課程設(shè)計(jì)原理課程設(shè)計(jì)原理 2.12.1 課設(shè)題目粗略分析課設(shè)題目粗略分析 根據(jù)課設(shè)題目要求，我將整體程序分為四大模塊，這四個(gè)模塊相互獨(dú)立，沒(méi) 有任何嵌套調(diào)用的情況，以下是四個(gè)模塊的大體分析： (1)判斷模塊：在插入一個(gè)關(guān)鍵字時(shí)，首先先對(duì)該關(guān)鍵字進(jìn)行判斷，如果該關(guān) 鍵字已經(jīng)存在則不插入，否則插入該關(guān)鍵字，調(diào)用函數(shù) insertavl（） 。 (2)左子樹(shù)插入模塊：如果判斷完的新關(guān)鍵字插在左子樹(shù)上，則對(duì)該以指針 p 所指結(jié)點(diǎn)為根的二叉樹(shù)作左平衡旋轉(zhuǎn)處理，本算法結(jié)束時(shí)，指針 p 指向新的根 結(jié)點(diǎn)，調(diào)用函數(shù) leftprocess（） 。 (3)右子樹(shù)插入模塊：如果判斷完的新關(guān)鍵字插在右子樹(shù)上，則對(duì)該以指針 p 所指結(jié)點(diǎn)為根的二叉樹(shù)作右平衡旋轉(zhuǎn)處理，本算法結(jié)束時(shí)，指針 p 指向新的根 結(jié)點(diǎn)，調(diào)用函數(shù) rightprocess（） 。 (4)輸出模塊：對(duì)建立完成的平衡二叉樹(shù)輸出，輸出格式為二叉樹(shù)的括號(hào)表 示，且每一步插入操作對(duì)應(yīng)一次輸出，最后做一次總體輸出，調(diào)用函數(shù)， dispbstree（） 。 2.22.2 原理圖介紹原理圖介紹 主函數(shù)主要實(shí)現(xiàn)的功能是函數(shù)調(diào)用，主函數(shù)首先對(duì)輸入的關(guān)鍵字進(jìn)行判斷， 調(diào)用函數(shù) insertavl（） ，若該關(guān)鍵字在已建樹(shù)中已經(jīng)存在，則返回主函數(shù)接著對(duì) 下一個(gè)關(guān)鍵字進(jìn)行判斷。若該關(guān)鍵字在已建樹(shù)中不存在，則插入該數(shù)，若插入左 子樹(shù)中則調(diào)用函數(shù) leftprocess（）進(jìn)行插入操作，若插入右子樹(shù)中則調(diào)用函數(shù) dispbstree（）進(jìn)行插入操作。當(dāng)所有的關(guān)鍵字都插入完事之后，進(jìn)行輸出，調(diào) 用函數(shù)，dispbstree（） 。 .1 功能模塊圖功能模塊圖 1.判斷模塊 沈陽(yáng)航空工業(yè)學(xué)院課程設(shè)計(jì)報(bào)告 3 若在平衡二叉排序樹(shù) b 中不存在和 e 有相同關(guān)鍵字的結(jié)點(diǎn)，則插入一個(gè)數(shù)據(jù) 元素為 e 的新結(jié)點(diǎn)，并返回 1，否則返回 0。若因插入而使二叉排序樹(shù)失去平衡， 則作平衡旋轉(zhuǎn)處理，布爾變量 taller 反映 b 長(zhǎng)高與否。 2.左子樹(shù)插入模塊 對(duì)以指針 p 所指結(jié)點(diǎn)為根的二叉樹(shù)作左平衡旋轉(zhuǎn)處理，本算法結(jié)束時(shí)，指針 p 指向新的根結(jié)點(diǎn)，插入分三種情況：原本左右子樹(shù)等高，現(xiàn)因左子樹(shù)增高而使 樹(shù)增；原本右子樹(shù)比左子樹(shù)高，現(xiàn)左右子樹(shù)等高；原本左子樹(shù)比右子樹(shù)高，須作 左子樹(shù)的平衡處理。若新關(guān)鍵字插入在*p 的左孩子的左子樹(shù)上，要做 ll 調(diào)整， 若新關(guān)鍵字插入在*p 的左孩子的右子樹(shù)上，要做 lr 調(diào)整。 3.右子樹(shù)子樹(shù)插入模塊 對(duì)以指針 p 所指結(jié)點(diǎn)為根的二叉樹(shù)作右平衡旋轉(zhuǎn)處理，本算法結(jié)束時(shí)，指針 p 指向新的根結(jié)點(diǎn)，插入分三種情況：原本左右子樹(shù)等高，現(xiàn)因右子樹(shù)增高而使 樹(shù)增；原本左子樹(shù)比右子樹(shù)高，現(xiàn)左右子樹(shù)等高；原本右子樹(shù)比左子樹(shù)高，須作 右子樹(shù)的平衡處理。若新關(guān)鍵字插入在*p 的右孩子的右子樹(shù)上，要做 rr 調(diào)整， 若新關(guān)鍵字插入在*p 的右孩子的左子樹(shù)上，要做 rl 調(diào)整。 .2 流程圖分析流程圖分析 1主函數(shù)流程圖 主函數(shù)主要實(shí)現(xiàn)的功能是函數(shù)調(diào)用，主函數(shù)首先對(duì)輸入的關(guān)鍵字進(jìn)行判斷， 若該關(guān)鍵字在已建樹(shù)中已經(jīng)存在，則返回主函數(shù)接著對(duì)下一個(gè)關(guān)鍵字進(jìn)行判斷。 若該關(guān)鍵字在已建樹(shù)中不存在，則插入該數(shù)，當(dāng)所有的關(guān)鍵字都插入完事之后， 進(jìn)行輸出。流程圖如圖 2.1 所示。 沈陽(yáng)航空工業(yè)學(xué)院課程設(shè)計(jì)報(bào)告 4 開(kāi)始 bstnode *b=null; int i,j; keytype a=6,1,2,3,4,5,0,7,8,9,n=10; y key存在 y insertavl(b,ai,j); dispbstree(b); n for(i=0;ikey y taller=0; return 0; ekey y leftprocess(b,taller) n 結(jié)束 rightprocess(b,taller) 圖 2.2 判斷模塊流程圖 3左子樹(shù)插入模塊流程圖 斷完的新關(guān)鍵字插在左子樹(shù)上，則對(duì)該以指針 p 所指結(jié)點(diǎn)為根的二叉樹(shù)作左 平衡旋轉(zhuǎn)處理，本算法結(jié)束時(shí)，指針 p 指向新的根結(jié)針。流程圖如圖 2.3 所示。 沈陽(yáng)航空工業(yè)學(xué)院課程設(shè)計(jì)報(bào)告 6 開(kāi)始 bstnode *p1,*p2 bstnode * y n y n y p-bf=0 p-bf=1; taller=1 p-bf=-1 p-bf=0; taller=0 p1-bf=1 n p1=p-lchild; p-lchild=p1-rchild; p1-rchild=p; p-bf=p1-bf=0; p=p1; p-bf=p1-bf=0 p2-bf=0 y n p2-bf=1 n y p1-bf=0; p-bf=-1 n p1-bf=1; p-bf=0; p2=p1-rchild; p1-rchild=p2-lchild; p2-lchild=p1; p-lchild=p2-rchild; p2-rchild=p; p1-bf=-1 y taller=0p=p2; p-bf=0; ; taller=0 結(jié)束 圖 2.3 左子樹(shù)插入模塊流程圖 4右子樹(shù)插入模塊流程圖 斷完的新關(guān)鍵字插在右子樹(shù)上，則對(duì)該以指針 p 所指結(jié)點(diǎn)為根的二叉樹(shù)作右 平衡旋轉(zhuǎn)處理，本算法結(jié)束時(shí)，指針 p 指向新的根結(jié)針。流程圖如圖 2.4 所示。 沈陽(yáng)航空工業(yè)學(xué)院課程設(shè)計(jì)報(bào)告 7 開(kāi)始 bstnode *p1,*p2 bstnode * y n y n y p-bf=-1 p-bf=1; taller=1 p-bf=1 p-bf=0; taller=0 1-bf=-1 n p1=p-rchild p-rchild=p1-lchild; p1-lchild=p; p-bf=p1-bf=0; p=p1; p-bf=p1-bf=0; p2-bf=0 y n p2-bf=-1 n y p1-bf=0; p-bf=1 n p1-bf=-1; p-bf=0 p2=p1-lchild; p1-lchild=p2-rchild; p2-rchild=p1; p-rchild=p2-lchild; p2-lchild=p; p1-bf=1 y p=p2; p-bf=0; taller=0 結(jié)束 圖 2.4 右子樹(shù)插入模塊流程圖 沈陽(yáng)航空工業(yè)學(xué)院課程設(shè)計(jì)報(bào)告 8 3 數(shù)據(jù)結(jié)構(gòu)分析數(shù)據(jù)結(jié)構(gòu)分析 3.13.1 存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu) 定義一個(gè)關(guān)鍵字類型的字符數(shù)組，其空間足夠大，用來(lái)存放關(guān)鍵字。 3.23.2 算法描述算法描述 1判斷關(guān)鍵字算法如下： /若在平衡二叉排序樹(shù) b 中不存在和 e 有相同關(guān)鍵字的結(jié)點(diǎn)，則插入一個(gè) 數(shù)據(jù)元素為 e 的新結(jié)點(diǎn)， if(b=null) /原樹(shù)為空，插入新結(jié)點(diǎn)，樹(shù)長(zhǎng)高，置 taller 為 1 b=(bstnode*)malloc(sizeof(bstnode); b-key=e; b-lchild=b-rchild=null; b-bf=0; taller=1; else if(e=b-key) /樹(shù)中已存在和 e 有相同關(guān)鍵字的結(jié)點(diǎn)則不插入 taller=0; return 0; if(ekey) /繼續(xù)在*b 的左子樹(shù)中進(jìn)行搜索 if(insertavl(b-lchild,e,taller)=0) /未插入 return 0; if(taller=1) /已插入到*b 的左子樹(shù)中且左子樹(shù)長(zhǎng)高 leftprocess(b,taller); else /繼續(xù)在*b 的右子樹(shù)中進(jìn)行搜索 if(insertavl(b-rchild,e,taller)=0) /未插入 return 0; if(taller=1) /已插入到*b 的右子樹(shù)中且右子樹(shù)長(zhǎng)高 沈陽(yáng)航空工業(yè)學(xué)院課程設(shè)計(jì)報(bào)告 9 rightprocess(b,taller); return 1; 2.左平衡處理算法如下： /對(duì)以指針 p 所指結(jié)點(diǎn)為根的二叉樹(shù)作左平衡旋轉(zhuǎn)處理，本算法結(jié)束時(shí)， /指針 p 指向新的根結(jié)點(diǎn) bstnode *p1,*p2; if(p-bf=0) /原本左右子樹(shù)等高，現(xiàn)因左子樹(shù)增高而使樹(shù)增高 p-bf=1; taller=1; else if(p-bf=-1) /原本右子樹(shù)比左子樹(shù)高，現(xiàn)左右子樹(shù)等高 p-bf=0; taller=0; else /原本左子樹(shù)比右子樹(shù)高，須作左子樹(shù)的平衡處理 p1=p-lchild; /p 指向*p 的左子樹(shù)根節(jié)點(diǎn) if(p1-bf=1) /新結(jié)點(diǎn)插入在*p 的左孩子的左子樹(shù)上，要做 ll 調(diào)整 p-lchild=p1-rchild; p1-rchild=p; p-bf=p1-bf=0; p=p1; else if(p1-bf=-1) /新結(jié)點(diǎn)插入在*p 的左孩子的右子樹(shù)上，要做 lr 調(diào)整 p2=p1-rchild; p1-rchild=p2-lchild; p2-lchild=p1; p-lchild=p2-rchild; p2-rchild=p; if(p2-bf=0) /新結(jié)點(diǎn)插入在*p2 處作為葉子結(jié)點(diǎn)的情況 p-bf=p1-bf=0; else if(p2-bf=1) /新結(jié)點(diǎn)插在*p2 的左子樹(shù)上的情況 沈陽(yáng)航空工業(yè)學(xué)院課程設(shè)計(jì)報(bào)告 10 p1-bf=0; p-bf=-1; else /新結(jié)點(diǎn)插在*p2 的右子樹(shù)上的情況 p1-bf=1; p-bf=0; p=p2; p-bf=0; /仍將 p 指向新的根結(jié)點(diǎn)，并置其 bf 值為 0 taller=0; 4 4 調(diào)試與分析調(diào)試與分析 4.14.1 調(diào)試過(guò)程調(diào)試過(guò)程 在調(diào)試程序是主要遇到一下幾類問(wèn)題： 1. 本程序用到指針的地方特別多，由于指針那部分知識(shí)我掌握的不是很好， 故而在這方面有困難。后來(lái)我通過(guò)在圖書館查資料、看書解決了這方面問(wèn)題。 2. 對(duì)二叉樹(shù)的左右子樹(shù)進(jìn)行插入調(diào)整的操作時(shí)，由于考慮問(wèn)題不夠全面而 導(dǎo)致輸出結(jié)果出現(xiàn)錯(cuò)誤，在查質(zhì)料重新學(xué)習(xí)二叉樹(shù)后，解決了此問(wèn)題。 沈陽(yáng)航空工業(yè)學(xué)院課程設(shè)計(jì)報(bào)告 11 4.1 程序執(zhí)行過(guò)程程序執(zhí)行過(guò)程 圖 4.1 第一組輸入執(zhí)行結(jié)果 圖 4.2 第二組輸入執(zhí)行結(jié)果 沈陽(yáng)航空工業(yè)學(xué)院課程設(shè)計(jì)報(bào)告 12 參考文獻(xiàn)參考文獻(xiàn) 1 嚴(yán)蔚敏.吳偉民. .數(shù)據(jù)結(jié)構(gòu)m.北京：清華大學(xué)出版社，2007. 2 張長(zhǎng)海.陳娟. .c 程序設(shè)計(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 語(yǔ)言描述）.m.北京：中國(guó)輕工業(yè)出版社，2004. 沈陽(yáng)航空工業(yè)學(xué)院課程設(shè)計(jì)報(bào)告 13 附附 錄（關(guān)鍵部分程序清單）錄（關(guān)鍵部分程序清單） 程序代碼程序代碼 #include #include typedef int keytype typedef struct node keytype key; int bf; struct node *lchild,*rchild; bstnode; void leftprocess(bstnode * if(p-bf=0) p-bf=1; taller=1; else if(p-bf=-1) p-bf=0; taller=0; else p1=p-lchild if(p1-bf=1) p-lchild=p1-rchild; p1-rchild=p; p-bf=p1-bf=0; p=p1; else if(p1-bf=-1) p2=p1-rchild; p1-rchild=p2-lchild; p2-lchild=p1; p-lchild=p2-rchild; p2-rchild=p; if(p2-bf=0) p-bf=p1-bf=0; else if(p2-bf=1) 沈陽(yáng)航空工業(yè)學(xué)院課程設(shè)計(jì)報(bào)告 14 p1-bf=0; p-bf=-1; else p1-bf=1; p-bf=0; p=p2; p-bf=0; taller=0; void rightprocess(bstnode * if(p-bf=0) p-bf=-1; taller=1; else if(p-bf=1) p-bf=0; taller=0; else p1=p-rchild; if(p1-bf=-1) p-rchild=p1-lchild; p1-lchild=p; p-bf=p1-bf=0; p=p1; else if(p1-bf=1) p2=p1-lchild; p1-lchild=p2-rchild; p2-rchild=p1; p-rchild=p2-lchild; p2-lchild=p; if(p2-bf=0) p-bf=p1-bf=0; else if(p2-bf=-1) 沈陽(yáng)航空工業(yè)學(xué)院課程設(shè)計(jì)報(bào)告 15 p1-bf=0; p-bf=1; else p1-bf=-1; p-bf=0; p=p2; p-bf=0; taller=0; int insertavl(bstnode* b-key=e; b-lchild=b-rchild=null; b-bf=0; taller=1; else if(e=b-key) taller=0; return 0; if(ekey) if(insertavl(b-lchild,e,taller)=0) return 0; if(taller=1) leftprocess(b,taller); else if(insertavl(b-rchild,e,taller)=0) return 0; if(taller=1) rightprocess(b,taller); 沈陽(yáng)航空工業(yè)學(xué)院課程設(shè)計(jì)報(bào)告 16 return 1; void dispbstree(bstnode *b) /*以括號(hào)表示法輸出 avl*/ if(b!=null) printf(“%d“,b-key); if(b-lchild!=null|b-rchild!=null) printf(“(“); dispbstree(b-lchild); if(b-rchild!=null)printf(“,“); dispbstree(b-rchild); printf(“)“); int main() bstnode *b=null; int i,j; keytype a=6,1,2,3,4,5,0,7,8,9,n=10; printf(“創(chuàng)建一棵 avl 樹(shù):n“); for(i