廣工數(shù)據(jù)結構課設

課程設計報告課程名稱 數(shù)據(jù)結構課程設計學院 計算機學院專業(yè)班級 學號 學生姓名 指導教師 蘇慶 2015年7月6日一、需求分析程序《平衡二叉樹的演示》是對平衡二叉樹的創(chuàng)建、插入、刪除、查找、合并、分裂功能的實現(xiàn)，以及用凹入表的形式將其展示給用戶。（1） 輸入的形式是數(shù)字，無論對功能的選則還是對數(shù)據(jù)的錄入，都是以數(shù)字的形式進行輸入，無需使用文件保存數(shù)據(jù)。輸入值得范圍在使用過程中會有說明。（2） 輸出的形式是在Dos界面進行輸出，（3） 程序所能達到的功能：創(chuàng)建一棵非空平衡二叉樹創(chuàng)建一棵空的平衡二叉樹向平衡二叉樹中添加結點從平衡二叉樹中刪除結點在平衡二叉樹中查找結點以凹入表的形式輸出一棵二叉樹以括號表示法輸出一棵二叉樹附加功能：F.合并兩棵平衡二叉樹分裂一棵平衡二叉樹二、概要設計（1） 本程序涉及到的數(shù)據(jù)類型有：鏈棧，鏈隊列，平衡二叉樹，結構體數(shù)組（2） 主程序是負責對各個功能進行展示，然后根據(jù)輸入來選擇進行相對應的功能，代碼如下：intmain（）｛intm;BBSTreeT=NULL;SetColor();InitView();printf("\n\t\t\t 請輸入你的選擇：，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 輸入錯誤，請重新輸入!!\n");}printf("\n\t\t\t 請輸入你的選擇：")；scanf("%d",&m);getchar();}return0;}各模塊之間的關系主程序模塊創(chuàng)建非空

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

二叉樹分裂平衡

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

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

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

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

均空進.一可密餐5意括”棵空樹'請輸入你的選擇：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>請輸入要添加的元素：5添加失??！

請輸入你的選擇:

此時提示添加失敗，是因為5重復了，假如我們重新添加，選擇功能3,此時添加8,按回車，得到如下：7.提示添加成功，此時我們再此時刪除功能，我們選擇功能4，得到如下界面，假如我們要刪除4，輸入4，按回車:得到界面如下，提示刪除成功，我們發(fā)現(xiàn)平衡二叉樹更新了，每個節(jié)點的平衡因子也更新了。你的平衡二叉樹為：3<2<1,#>,6<5,8>>8<bf：@>6<bf：0>5<bf：0>3<bf：0>2<bf：1>l<bf我們再輸入5，測試查找功能。提示輸入查找元素，我們輸入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>查找子樹請爵漓駕擇：■

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

我們再輸入7來此時分裂一棵平衡二叉樹的功能歡迎來到平梅二叉樹的演示界面一：----空的普一：----空的普一：一.：,叉叉----flfl平平疆占苫g點棵顆--結結菁-建建加雋開列茁耳添耍合八縣12345678:1透建慶芳街*鳩元素起為此時輸出的是:分割后小于等于S:1透建慶芳街*鳩元素起為此時輸出的是:分割后小于等于S的平衡二叉樹T2為:2<1,4<3,5?思住瞰嘻找操作，系第自動創(chuàng)建一棵空樹!,四，五無天聯(lián)，開相互獨豆？請輸入你的選擇：？請輸入樹的數(shù)子序列〈按，回車鍵，結束n此時提示我們輸入樹的序列，輸入完將提示我們輸入x的值，即樹T將分裂成一棵均是小于等于x的樹，和一棵均大于x的樹。假如我們測試數(shù)據(jù)是：T:12345678910 x:5分菖房壬于曲平衡二叉祐3彖按回車鍵查看T1,T2,T3的凹入表….分割前的平衡二叉.樹T1為:4<2<1,3>,8<6<5,7),9<#,10>?一務曲奇南港三反&去二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民----平平黑點占罟g棵顆--結結結兩-建建加嚎開番添馨一合蕾:1.本程序平衡元素均為數(shù)字工—素可可用；工格W隔2?鯉入乾據(jù)甲..=一 4?功能K,壬與功能一，一，二，四,果5-

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