廣工數(shù)據(jù)結(jié)構(gòu)課設(shè)

課程設(shè)計(jì)報(bào)告課程名稱 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)學(xué)院 計(jì)算機(jī)學(xué)院專業(yè)班級(jí) 學(xué)號(hào) 學(xué)生姓名 指導(dǎo)教師 蘇慶 2015年7月6日一、需求分析程序《平衡二叉樹的演示》是對(duì)平衡二叉樹的創(chuàng)建、插入、刪除、查找、合并、分裂功能的實(shí)現(xiàn)，以及用凹入表的形式將其展示給用戶。（1） 輸入的形式是數(shù)字，無論對(duì)功能的選則還是對(duì)數(shù)據(jù)的錄入，都是以數(shù)字的形式進(jìn)行輸入，無需使用文件保存數(shù)據(jù)。輸入值得范圍在使用過程中會(huì)有說明。（2） 輸出的形式是在Dos界面進(jìn)行輸出，（3） 程序所能達(dá)到的功能：創(chuàng)建一棵非空平衡二叉樹創(chuàng)建一棵空的平衡二叉樹向平衡二叉樹中添加結(jié)點(diǎn)從平衡二叉樹中刪除結(jié)點(diǎn)在平衡二叉樹中查找結(jié)點(diǎn)以凹入表的形式輸出一棵二叉樹以括號(hào)表示法輸出一棵二叉樹附加功能：F.合并兩棵平衡二叉樹分裂一棵平衡二叉樹二、概要設(shè)計(jì)（1） 本程序涉及到的數(shù)據(jù)類型有：鏈棧，鏈隊(duì)列，平衡二叉樹，結(jié)構(gòu)體數(shù)組（2） 主程序是負(fù)責(zé)對(duì)各個(gè)功能進(jìn)行展示，然后根據(jù)輸入來選擇進(jìn)行相對(duì)應(yīng)的功能，代碼如下：intmain（）｛intm;BBSTreeT=NULL;SetColor();InitView();printf("\n\t\t\t 請(qǐng)輸入你的選擇：，scanf("%d",&m);getchar();while(1){switch(m){case1:T=item_1();break;case2:item_2(T);break;case3:item_3(T);break;case4:item_4(T);break;case5:item_5(T);break;case6:item_6();break;case7:item_7();break;

if(m==8){item_8();break;}elseif(m>8llm<1){system("CLS");InitView();printf("\n\t\t\t 輸入錯(cuò)誤，請(qǐng)重新輸入!!\n");}printf("\n\t\t\t 請(qǐng)輸入你的選擇：")；scanf("%d",&m);getchar();}return0;}各模塊之間的關(guān)系主程序模塊創(chuàng)建非空

例創(chuàng)建空樹添加結(jié)點(diǎn)刪除結(jié)點(diǎn)查找結(jié)點(diǎn)合并平衡

二叉樹分裂平衡

二叉樹退出三、詳細(xì)設(shè)計(jì)(1)數(shù)據(jù)類型的定義/*存放輸入數(shù)據(jù)的數(shù)組結(jié)構(gòu)體*/typedefstructArrayNode{RcdTypedata;ArrayNode*next;}ArrayNode,*Array;/*平衡二叉樹結(jié)構(gòu)體*/typedefstructBBSTNode{RcdTypedata;intbf;BBSTNode*lchild,*rchild;}BBSTNode,*BBSTree;/*鏈隊(duì)列結(jié)構(gòu)體*/typedefstructLQNode{BBSTreeelem;structLQNode*next;}LQNode,*QueuePtr;/*隊(duì)列結(jié)點(diǎn)結(jié)構(gòu)體*/typedefstruct{QueuePtrfront;QueuePtrrear;}LQueue;/*棧結(jié)點(diǎn)結(jié)構(gòu)體*/typedefstructLSNode{BBSTreedata; 〃數(shù)據(jù)域structLSNode*next;〃指針域}LSNode,*LStack; 〃結(jié)點(diǎn)和鏈棧類型(2)偽代碼：建樹操作beginBBSTreeTArrayaa=GetInputToArray();〃獲取到輸入的數(shù)組Whilea!=NULL{InsertAVL(T,a->data)a=>a->next}End插入結(jié)點(diǎn)beginif(NULL==T){T->data=eT->bf=EHT->lchild=NULLT->rchild=NULL}elseif(e==T->data){〃書中已存在和e相等的結(jié)點(diǎn)returnFALSE;}elseif(e<T->data){if(!InsertAVL(T->lchild,e))returnFALSE;if(TRUE==taller){switch(T->bf){caseLH:LeftBalance(T);taller=FALSE;break;caseEH:T->bf=LH;taller=TRUE;break;caseRH:T->bf=EH;taller=FALSE;break;}}}else{if(FALSE==InsertAVL(T->rchild,e))returnFALSE;if(TRUE==taller){switch(T->bf){caseLH:T->bf=EH;taller=FALSE;break;caseEH:T->bf=RH;taller=TRUE;break;caseRH:RightBalance(T);taller=FALSE;break;}}}returnTRUE;EndC.刪除操作begin〃當(dāng)被刪結(jié)點(diǎn)是有兩個(gè)孩子，且其前驅(qū)結(jié)點(diǎn)是左孩子時(shí)，tag=1staticinttag=0;if(t==NULL){returnFALSE; 〃如果不存在元素，返回失敗}elseif(e==t->data){BBSTNode*q=NULL;〃如果該結(jié)點(diǎn)只有一個(gè)孩子，則將自子樹取代該結(jié)點(diǎn)if(t->lchild==NULL){q=t;t=t->rchild;free(q);shorter=TRUE;}elseif(t->rchild==NULL){q=t;t=t->lchild;free(q);shorter=TRUE;}〃如果被刪結(jié)點(diǎn)有兩個(gè)孩子，則找到結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，〃并將前驅(qū)結(jié)點(diǎn)的值賦給該結(jié)點(diǎn)，然后刪除前驅(qū)結(jié)點(diǎn)else{q=t->lchild;while(q->rchild){q=q->rchild;}t->data=q->data;if(t->lchild->data==q->data){tag=1;}DeleteAVL(t->lchild,q->data,shorter);if(tag==1){BBSTreer=t->rchild;if(NULL==r)t->bf=0;else{switch(r->bf){caseEH:t->bf=-1;break;default:RightBalance(t);break;}}}elseif(e<t->data){ 〃左子樹中繼續(xù)查找if(!DeleteAVL(t->lchild,e,shorter)){returnFALSE;}〃刪除完結(jié)點(diǎn)之后，調(diào)整結(jié)點(diǎn)的平衡因子if(shorter&&(tag==0)){switch(t->bf){caseLH:t->bf=EH;shorter=TRUE;break;caseEH:t->bf=RH;shorter=FALSE;break;〃如果本來就是右子樹較高，刪除之后就不平衡，需要做右平衡操作caseRH:RightBalance(t); 〃右平衡處理if(t->rchild->bf==EH)shorter=FALSE;elseshorter=TRUE;break;}}}elseif(e>t->data){//右子樹中繼續(xù)查找if(!DeleteAVL(t->rchild,e,shorter)){returnFALSE;}〃刪除完結(jié)點(diǎn)之后，調(diào)整結(jié)點(diǎn)的平衡因子if(shorter&&(tag==0)){switch(t->bf){caseLH:LeftBalance(t); 〃左平衡處理if(t->lchild->bf==EH)shorter=FALSE;elseshorter=TRUE;break;caseEH:t->bf=LH;shorter=FALSE;break;caseRH:t->bf=EH;shorter=TRUE;break;}}if(tag==1){intdepthLeft=BBSTreeDepth(t->lchild);intdepthRight=BBSTreeDepth(t->rchild);t->bf=depthLeft-depthRight;}}returnTRUE;EndD.查找操作Beginif(T==NULL)returnNULL;if(e==T->data){returnT;}elseif(e>T->data){returnSearchAVL(T->rchild,e);}else{returnSearchAVL(T->lchild,e);}End合并操作BeginStatustaller=TRUE;Arraya=NULL;a=GetArrayFromTree(T2);while(a!=NULL){taller=TRUE;InsertAVL(T1,a->data,taller);a=a->next;}returnT1;End分裂操作BeginArraya=NULL;Statustaller;a=GetArrayFromTree(Tt1);//獲取到樹轉(zhuǎn)化為的數(shù)組if(Tt1==NULL)returnFALSE;else{while(a!=NULL){if(a->data<=x){taller=TRUE;InsertAVL(Tt2,a->data,taller);a=a->next;}else{taller=TRUE;InsertAVL(Tt3,a->data,taller);a=a->next;}}}returnTRUE;End(3)關(guān)系圖A.建樹操作結(jié)束B.添加結(jié)點(diǎn)操作C.刪除結(jié)點(diǎn)操作D.查找結(jié)點(diǎn)操作E.合并操作四、調(diào)試分析調(diào)試過程中所遇到的問題:運(yùn)行過程中程序停止運(yùn)行。遇到這個(gè)情況一開始我以為是編譯器有問題，但是換了個(gè)編譯器還是同樣的問題，后來我上網(wǎng)查詢了有關(guān)資料，大概明白了是自己的代碼出現(xiàn)了問題。所以只能將新增的代碼注釋掉，一條一條測(cè)試，調(diào)試過程很漫長(zhǎng)，最后才發(fā)現(xiàn)是內(nèi)存泄露和空指針異常，將指針不適用之后指向?yàn)镹ULL，才把問題解決了。經(jīng)驗(yàn)和體會(huì)a） 在做一個(gè)比較大的程序過程中，應(yīng)該學(xué)會(huì)邊編寫程序邊運(yùn)行，即當(dāng)你完成了一個(gè)比較小的功能時(shí)便對(duì)其調(diào)試，這樣有助于我們高效地完成項(xiàng)目，而且在調(diào)試BUG的過程也可以大大減小其難度。b） 必須要有良好的編程習(xí)慣。首先編碼風(fēng)格一定要規(guī)范，這樣不僅有利于讀者和編程者對(duì)代碼的閱讀，更有利于對(duì)代碼的維護(hù)。其次要對(duì)代碼要細(xì)心，比較一些指針的初始化和不需要時(shí)指為空，這些都是可以極大減少我們出現(xiàn)BUG的幾率。c） 寫的程序一定要人性化，現(xiàn)在的應(yīng)用都講究與人交互的重要性，其避免不了使用各種炫酷的圖形界面，但我們要考慮的是，即便是C語言，沒有什么圖形界面，我們也一定要考慮人性化的問題。五、使用說明本程序的可執(zhí)行文件是：平衡二叉樹的演示.exe雙擊exe文件，進(jìn)入主界面：

然后我們應(yīng)該先創(chuàng)建一棵非空二叉樹或者是空的二叉樹，輸入1或者2,按回車鍵，此處我們輸入1,如下:TOC\o"1-5"\h\z* 歡迎來到平衡二叉樹的演示界面 *1?創(chuàng)建一愣斐空二叉網(wǎng) *創(chuàng)建一棵空的二叉樹 *添加結(jié)點(diǎn)5二叉樹Z吾富蒯平1"5二叉樹am.說明：」夜捌EE德5地亟案坦差尊輸△昉直箍幽？am.一— — _ —E,系統(tǒng)自動(dòng)創(chuàng)建一棵空樹!功能六「七寫所能二；'二一蘭"西，五無關(guān)聯(lián)廠并相互獨(dú)豆，請(qǐng)輸入你的選擇：1請(qǐng)輸入生成樹的數(shù)字序列〈按，回車建結(jié)束》4.此時(shí)，程序提示我們輸入樹的序列，我們可以以此輸入數(shù)字，不同數(shù)字用空格隔開，按回車表示輸入完成，例如，我們輸入102030405060回車，得到如下，程序提示我們創(chuàng)建成功，并輸出了該平衡二叉樹，此時(shí)按任意鍵返回。**說明1234%*荻迎來到平衡二叉樹的演示界面12345&7S叉還叉叉----二二vffi1Epul-LL工TTT1ZC『裳3箱顆-建掛血舞并希創(chuàng)創(chuàng)漆ffll查合爭(zhēng)廠乂J二義**說明1234%*荻迎來到平衡二叉樹的演示界面12345&7S叉還叉叉----二二vffi1Epul-LL工TTT1ZC『裳3箱顆-建掛血舞并希創(chuàng)創(chuàng)漆ffll查合爭(zhēng)廠乂J二義虹系荽自動(dòng)創(chuàng)建一棵空樹!你的平衡二叉樹為,

4C2Cl.,35,5Ctt,B>>S*平衡二一叉樹展示**6<bfs0>5Ch￡s-l>4<bf：0>3<bf=0>2Ch￡=?>l(bf=0>?創(chuàng)建成功!請(qǐng)按任意鍵返回上一層.…

返回到了首頁，此時(shí)我們可以輸入3,往此樹中添加結(jié)點(diǎn)，按回車確認(rèn)。此時(shí)，程序會(huì)把平衡二叉樹展示出來，然后提示用戶輸入要?jiǎng)h除的元素，假如我們要添加5，輸入5，按回車。歡迎來到平衡二叉樹的演示界面說明，「本程序平衡二蓮寸的元素12345678平平霜點(diǎn)點(diǎn)點(diǎn)棵顆--結(jié)結(jié)結(jié)兩-建建如鑒并列茁添紫合盆.I:叉叉----空的悲工叉叉說明，「本程序平衡二蓮寸的元素12345678平平霜點(diǎn)點(diǎn)點(diǎn)棵顆--結(jié)結(jié)結(jié)兩-建建如鑒并列茁添紫合盆.I:叉叉----空的悲工叉叉----為釐仃三

均空進(jìn).一可密餐5意括”棵空樹'請(qǐng)輸入你的選擇：3你的平衡二叉樹為：4<2<1,3>,5<#,6)>6<bf：0>5<bf：-1>4<bf：0>3<bf：0>2<bf：0)l(b￡：0>請(qǐng)輸入要添加的元素：5添加失敗！

請(qǐng)輸入你的選擇:

此時(shí)提示添加失敗，是因?yàn)?重復(fù)了，假如我們重新添加，選擇功能3,此時(shí)添加8,按回車，得到如下：7.提示添加成功，此時(shí)我們?cè)俅藭r(shí)刪除功能，我們選擇功能4，得到如下界面，假如我們要?jiǎng)h除4，輸入4，按回車:得到界面如下，提示刪除成功，我們發(fā)現(xiàn)平衡二叉樹更新了，每個(gè)節(jié)點(diǎn)的平衡因子也更新了。你的平衡二叉樹為：3<2<1,#>,6<5,8>>8<bf：@>6<bf：0>5<bf：0>3<bf：0>2<bf：1>l<bf我們?cè)佥斎?，測(cè)試查找功能。提示輸入查找元素，我們輸入6。你的平衡二叉樹為中瞻瞞,0〉〉8<bf：0>6<bf；0>5<b￡：G>3<bf：0>2<bf：1>l<bfs0>平衡二又樹你的查找子樹為8<bf：0>6<bf：0>5<h￡:0>查找子樹請(qǐng)爵漓駕擇：■

程序便把原來的平衡二叉樹和以查找結(jié)點(diǎn)為根節(jié)點(diǎn)的子樹都輸出來。此時(shí)我們?cè)龠\(yùn)行合并平衡二叉樹的功能。選擇6,回車。歡迎來到平衡二叉樹的演示界面W添〃合盆123456781=80*加結(jié)點(diǎn)W伊口杼*開兩棵平食二叉岐裂一顆平稀二叉樹:1234二K建與需創(chuàng)七眉丁、一^■.'■■115序警六程入不能本薯功-RI數(shù)訴添，為釐仃二均空進(jìn)，M一小加四歡迎來到平衡二叉樹的演示界面W添〃合盆123456781=80*加結(jié)點(diǎn)W伊口杼*開兩棵平食二叉岐裂一顆平稀二叉樹:1234二K建與需創(chuàng)七眉丁、一^■.'■■115序警六程入不能本薯功-RI數(shù)訴添，為釐仃二均空進(jìn)，M一小加四鼬遍互獨(dú)立i假系統(tǒng)自動(dòng)創(chuàng)建一棵空樹!請(qǐng)輸入你的選擇：6請(qǐng)輸人樹口的數(shù)字序列《按，回車躇結(jié)束》11.此時(shí)系統(tǒng)提示我們輸入第一棵樹的序列，假如我們輸入12345然后系統(tǒng)會(huì)提示我們輸入第二棵樹的序列，假如我們輸入789請(qǐng)輸入樹T1的教字序列〈按」回車鍵，結(jié)束“123456請(qǐng)輸入樹塑的救字序列〈按』回車鍵，結(jié)束789_12.程序會(huì)把12.程序會(huì)把T1T2T3用括號(hào)表示法輸出此時(shí)提示按回車會(huì)輸出要合并的兩棵樹和合并后的樹的凹入表平衡二叉樹T1為:9Cbf：0>8<bf：0>7<bf：0>6<bf：-1>5<bf：0>4<bf：-l>3<bf：0>2<bf：0>l<bf：0>平衡二叉樹T2為:9<bf：0>8<bf：0>7<bf：0>合并后的平彳野二叉樹T3為:9<bf：0>8<bf：0>7<bf：0>6<bf：-1>5<bf：0>4<bf：-1>3<bf：0>2<bf：0>l<bf：0>請(qǐng)按任意鍵返回上一層…

我們?cè)佥斎?來此時(shí)分裂一棵平衡二叉樹的功能歡迎來到平梅二叉樹的演示界面一：----空的普一：----空的普一：一.：,叉叉----flfl平平疆占苫g點(diǎn)棵顆--結(jié)結(jié)菁-建建加雋開列茁耳添耍合八縣12345678:1透建慶芳街*鳩元素起為此時(shí)輸出的是:分割后小于等于S:1透建慶芳街*鳩元素起為此時(shí)輸出的是:分割后小于等于S的平衡二叉樹T2為:2<1,4<3,5?思住瞰嘻找操作，系第自動(dòng)創(chuàng)建一棵空樹!,四，五無天聯(lián)，開相互獨(dú)豆？請(qǐng)輸入你的選擇：？請(qǐng)輸入樹的數(shù)子序列〈按，回車鍵，結(jié)束n此時(shí)提示我們輸入樹的序列，輸入完將提示我們輸入x的值，即樹T將分裂成一棵均是小于等于x的樹，和一棵均大于x的樹。假如我們測(cè)試數(shù)據(jù)是：T:12345678910 x:5分菖房壬于曲平衡二叉祐3彖按回車鍵查看T1,T2,T3的凹入表….分割前的平衡二叉.樹T1為:4<2<1,3>,8<6<5,7),9<#,10>?一務(wù)曲奇南港三反&去二19Cb￡：0>9<bF：-l>BClifs0>7Cbf：B>6<bf：9)5<bf：B>4<hf：-t>3<bf：9>2Cbf：0>l<bf：0)分割后小于等于5的平衢二叉樹T2為:4<2<1,3>^<6<5.7>?9<#?10>?芬菖房不葦至等:而蘋新三靈兩；；；5<bf：B)4(1]￡:0)3<h￡s0)2CJjf：-1>l<hf=3)分割后大于S的平衡二叉樹T3為：4<2(1.3>,8<6<5.7>.9<?.10>?10<hf：0>9<h￡:-l>BCb￡：0>7<hf=0>6<hf=-1>甬茹蓄嬴云百工二直二最后便是退出功能，選擇8,程序提示我們是否退出，輸入Y(y)退出程序，輸入N(n)返回主界面歡迎來到平衡二叉樹的演示界面說明12345678XX--空的非空X民----說明12345678XX--空的非空X民----平平黑點(diǎn)占罟g棵顆--結(jié)結(jié)結(jié)兩-建建加嚎開番添馨一合蕾:1.本程序平衡元素均為數(shù)字工—素可可用；工格W隔2?鯉入乾據(jù)甲..=一 4?功能K,壬與功能一，一，二，四,果5-

IfeS找案目互獨(dú)立?拒，系綠自動(dòng)創(chuàng)建一棵空樹!請(qǐng)輸爾的詵擇，8請(qǐng)選澤:請(qǐng)選澤:六、測(cè)試結(jié)果測(cè)試數(shù)據(jù)：平衡二叉樹T:12345678910添加元素：11刪除元素：5查找元素：8你的平衡二叉樹為:4<2<1,3>,8<6<5,7>,9<#,10>>>g平衡二叉甜展