廣工數(shù)據(jù)結(jié)構(gòu)課設(shè)-平衡二叉樹演示(文檔尾部含源碼下載地址)

課程設(shè)計(jì)報(bào)告課程名稱數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)學(xué)院計(jì)算機(jī)學(xué)院專業(yè)班級(jí)計(jì)科9班學(xué)號(hào)學(xué)生姓名指導(dǎo)教師蘇慶2023年7月6日需求分析程序《平衡二叉樹的演示》是對(duì)平衡二叉樹的創(chuàng)立、插入、刪除、查找、合并、分裂功能的實(shí)現(xiàn)，以及用凹入表的形式將其展示給用戶。輸入的形式是數(shù)字，無論對(duì)功能的選那么還是對(duì)數(shù)據(jù)的錄入，都是以數(shù) 字的形式進(jìn)行輸入，無需使用文件保存數(shù)據(jù)。輸入值得范圍在使用過程 中會(huì)有說明。輸出的形式是在Dos界面進(jìn)行輸出，程序所能到達(dá)的功能：A.創(chuàng)立一棵非空平衡二叉樹B.創(chuàng)立一棵空的平衡二叉樹C.向平衡二叉樹中添加結(jié)點(diǎn)D.從平衡二叉樹中刪除結(jié)點(diǎn)E.在平衡二叉樹中查找結(jié)點(diǎn)F.以凹入表的形式輸出一棵二叉樹G.以括號(hào)表示法輸出一棵二叉樹附加功能：F.合并兩棵平衡二叉樹H.分裂一棵平衡二叉樹概要設(shè)計(jì)本程序涉及到的數(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>8||m<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)系三、詳細(xì)設(shè)計(jì)數(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)和鏈棧類型偽代碼：建樹操作beginBBSTreeTArrayaa=GetInputToArray();//獲取到輸入的數(shù)組Whilea!=NULL{InsertAVL(T,a->data)a=>a->next}EndB.插入結(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);}EndE.合并操作BeginStatustaller=TRUE;Arraya=NULL;a=GetArrayFromTree(T2);while(a!=NULL){taller=TRUE;InsertAVL(T1,a->data,taller);a=a->next;}returnT1;EndF.分裂操作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關(guān)系圖建樹操作B.添加結(jié)點(diǎn)操作C.刪除結(jié)點(diǎn)操作D.查找結(jié)點(diǎn)操作E.合并操作F.分裂操作調(diào)試分析調(diào)試過程中所遇到的問題：運(yùn)行過程中程序停止運(yùn)行。遇到這個(gè)情況一開始我以為是編譯器有問題，但是換了個(gè)編譯器還是同樣的問題，后來我上網(wǎng)查詢了有關(guān)資料，大概明白了是自己的代碼出現(xiàn)了問題。所以只能將新增的代碼注釋掉，一條一條測試，調(diào)試過程很漫長，最后才發(fā)現(xiàn)是內(nèi)存泄露和空指針異常，將指針不適用之后指向?yàn)镹ULL，才把問題解決了。經(jīng)驗(yàn)和體會(huì)在做一個(gè)比擬大的程序過程中，應(yīng)該學(xué)會(huì)邊編寫程序邊運(yùn)行，即當(dāng)你完成了一個(gè)比擬小的功能時(shí)便對(duì)其調(diào)試，這樣有助于我們高效地完成工程，而且在調(diào)試BUG的過程也可以大大減小其難度。必須要有良好的編程習(xí)慣。首先編碼風(fēng)格一定要標(biāo)準(zhǔn)，這樣不僅有利于讀者和編程者對(duì)代碼的閱讀，更有利于對(duì)代碼的維護(hù)。其次要對(duì)代碼要細(xì)心，比擬一些指針的初始化和不需要時(shí)指為空，這些都是可以極大減少我們出現(xiàn)BUG的幾率。寫的程序一定要人性化，現(xiàn)在的應(yīng)用都講究與人交互的重要性，其防止不了使用各種炫酷的圖形界面，但我們要考慮的是，即便是C語言，沒有什么圖形界面，我們也一定要考慮人性化的問題。使用說明本程序的可執(zhí)行文件是：平衡二叉樹的演示.exe雙擊exe文件，進(jìn)入主界面：然后我們應(yīng)該先創(chuàng)立一棵非空二叉樹或者是空的二叉樹，輸入1或者2， 按回車鍵，此處我們輸入1，如下：此時(shí)，程序提示我們輸入樹的序列，我們可以以此輸入數(shù)字，不同數(shù)字用 空格隔開，按回車表示輸入完成，例如，我們輸入102030405060回車， 得到如下，程序提示我們創(chuàng)立成功，并輸出了該平衡二叉樹，此時(shí)按任意 鍵返回。返回到了首頁，此時(shí)我們可以輸入3，往此樹中添加結(jié)點(diǎn)，按回車確認(rèn)。此時(shí)，程序會(huì)把平衡二叉樹展示出來，然后提示用戶輸入要?jiǎng)h除的元素