數據結構課程設計-- 求二叉樹根結點到指定結點的路徑

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數：12 大?。?45.86KB 人氣指數：12 舉報 版權申訴

已閱讀1頁，還剩11頁未讀，繼續(xù)免費閱讀

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

1、　　課程設計任務書　　目錄　　1 需求分析…………………………………………………….. 1　　2 概要設計　　2.1 設計思想………

2、….…………………………….………1　　2.2 設計說明…………………………………….………….2　　2.3 算法流程圖………………………………….………….2　　3 詳細設計　　3.1源代碼……………………………………….…….

3、..........4 　　3.2實驗結果………………………………….……...............7　　4 調試分析………………………………………........…..……..9　　5 課設總結………………………………………………..……..9　　6 參考文獻………

4、………………………………………..……..10　　1.需求分析　　1、定義二叉樹的存儲結構，每個結點中設置三個域，即值域、左指針域、右指針域。要建立二叉樹T的鏈式存儲結構，即建立二叉鏈表?？刹捎孟刃蛐蛄羞f歸建立二叉樹，建立如下圖所示的二叉樹。應該在程序運行窗口的主控菜單后，先選擇“1”并回車，緊接著在程序運行窗口中提

5、示信息“輸入二叉樹的先序序列結點值:”之后，采用以下字符序列：ABC@@DE@G@@F@@@ （以@替代空格）作為建立二叉樹T的輸入字符序列并回車，窗口出現：二叉樹的鏈式存儲結構建立完成! 　　2、求二叉樹的指定結點路徑。在程序運行窗口的主控菜單中選擇“2” 并回車，在程序運行窗口中提示信息“輸入要求路徑的結點值:”輸入“G” 并回車，會得到結果為：→A→B→D→E→G如果輸入“I” 并回車，

6、會得到結果為：沒有要求的結點！ 　　2 .概要設計　　2.1 設計思想　　在二叉樹上無論采用哪種遍歷方法，都能夠訪問遍樹中的所有結點。由于訪問結點的順序不同，前序遍歷和中序遍歷都很難達到設計的要求；但采用后序遍歷二叉樹是可行的，因為后序遍

7、歷是最后訪問根結點，按這個順序將訪問過的結點存儲到一個順序棧中，然后再輸出即可。因此，我們可以非遞歸地后序遍歷二叉樹T，當后序遍歷訪問到結點*p時，此時棧中存放的所有結點均為給定結點*p的祖先，而由這些祖先便構成了一條從根結點到結點*p之間的路徑。　　2.2設計說明　　為實現上述的設計思想，首先要定義二叉樹的鏈式存儲

8、結構，采用二叉鏈表的方式，相應的類型說明為：　　typedef char DataType;　　typedef struct node{　　DataType data;　　struct node *lchild,*rchild;

9、　}BinTNode,*BinTree;　　函數調用關系如下圖所示：　　函數接口說明:　　Status CreateBiTree(BinTree &bt) /*按照先序遍歷次序遞歸建立二叉樹*/　　Void NodePath(

10、BinTree bt,BinTNode *ch) /*求二叉樹根結點到給定結點*p的路徑*/　　BinTNode *Findx(BinTree bt,DataType x)/*按給定值查找結點*/　　實現注釋：　　二叉樹的創(chuàng)建模塊: 按照先序遍歷次序遞歸建立二叉樹,通過讀入的

11、字符，分配存儲空間生成新結點后再逐個構建根結點、左子樹和右子樹。　　二叉樹指定結點路徑模塊：該模塊由NodePath、FindBT、Findx三個函數體構成，main函數通過先調用Findx 函數來查找結點，Findx又通過逐步調用FindBT函數遍歷查找結點的路徑，最后main函數再通過調用NodePath函數得到給定結點的路徑。該模塊需定義全局變量p和found以方便查找，否則容易出錯，出錯

12、情況見調試報告。　　2.3算法流程圖　　top--　　Y　　N

13、;　　Y　　圖1——指定結點路徑流程圖　　圖2——程序主流程圖　　詳細設計　　3.1源代碼　　#include <stdio.h

14、>　　#include <stdlib.h>　　#define num 100　　#define OK 1　　typedef int Status;　　typedef char DataType;</p&g

15、t;　　typedef struct node{　　DataType data;　　struct node　　*lchild,*rchild;　　}BinTNode,*BinTree;　　int found;

16、　　BinTNode *p;　　Status CreateBiTree(BinTree &bt)　　//ABC@@DE@G@@F@@@ 　　{char ch;　　printf("ch=");</

17、p>　　scanf("%c",&ch);　　getchar();　　if (ch=='@')bt=NULL;　　else　　{</b&g

18、t;　　bt=(BinTNode *)malloc(sizeof(BinTNode));　　bt->data=ch; //生成根結點　　CreateBiTree(bt->lchild); //構造左子樹　　CreateBiTree(bt->rchil

19、d); //構造右子樹　　}　　return OK;　　}　　void NodePath(BinTree bt,BinTNode *ch)　　{//求

20、二叉樹根結點到給定結點*p的路徑　　typedef enum {FALSE,TRUE}boolean;　　BinTNode *stack[num]; //定義棧　　int tag[num];　　int i,top;　　boolea

21、n find;　　BinTNode *s;　　find=FALSE;　　top=0;　　s=bt;　　do</

22、p>　　{　　while(s!=NULL)　　{//掃描左子樹　　stack[top]=s;　　tag[top]=0;　　s=

23、s->lchild;　　}　　if(top>0)　　{　　s=stack[top];　　if(tag[t

24、op]==1)　　{if(s==ch)　　{//找到ch,則顯示從根結點到ch的路徑　　for(i=1;i<=top;i++)　　printf("->%c",stack[i]->data);

25、　find=TRUE;　　}　　else　　top--;　　s=stack[top];　　}//e

26、ndif　　if(top>0 && !find)　　{　　if(tag[top]!=1)　　{　　s=s->

27、;rchild; //掃描右子樹　　tag[top]=1;　　}　　else　　s=NULL;

28、}//endif　　}//endlif　　}while(!find && top!=0);　　}　　void FindBT(BinTree bt,DataTyp

29、e x)　　{　　if((bt!=NULL) && !found)　　{　　if(bt->data==x)　　{p=bt;found

30、=1;}　　else　　{　　FindBT(bt->lchild,x); //遍歷查找左子樹　　FindBT(bt->rchild,x); //遍歷查找右子樹&

31、lt;p>　　}　　}　　}　　BinTNode *Findx(BinTree bt,DataType x)　　{//按給定值查找結點

32、;　　int found=0; //用found來作為是否查找到的標志　　BinTree p=NULL; //置空指針　　FindBT(bt,x);　　return(p);　　}<p

33、>　　void main()　　{　　BinTree bt;　　char ch1;　　int xz=1;<

34、;b>　　while(xz)　　{　　printf("建立二叉樹并求指定結點路徑\n");　　printf(" 歡迎光臨\n");　　printf(

35、"===========================\n");　　printf("1.建立二叉樹的存儲結構 \n");　　printf("\n");　　printf("2.求二叉樹指定結點的路徑 \n");

36、　　printf("\n");　　printf("0. 退出系統(tǒng) \n");　　printf("===========================\n");　　printf("請選擇:(0-2) \n&qu

37、ot;);　　scanf("%d",&xz);　　getchar();　　switch(xz)　　{ //輸入:ABC@@DE@G@@F@@@ 　　case 1:printf("輸入二叉樹的先

38、序序列結點值:\n");　　CreateBiTree(bt);　　printf("二叉樹的鏈式存儲結構建立完成! \n");　　printf("\n");　　break;</p&

39、gt;　　//輸出: CBEGDFA　　case 2:printf("路徑的節(jié)點值是：\n"); 　　ch1=getchar();　　p=NULL;　　found=0;<

40、;/b>　　Findx(bt,ch1);　　if(p!=NULL)　　NodePath(bt,p);　　else　　printf("沒有要求的節(jié)點!\n");<

41、/p>　　printf("\n");　　break;　　}// switch　　}// while　　} &l

42、t;/p>　　3.2 實驗結果　　4.調試分析　　編程的最初階段，在case3語句中，缺少p=NULL;和found=0;兩個語句，得到的結果不管查找的結點是否存在，其結果均顯示為G結點的路徑，后經設置斷點、調試，發(fā)現p指針在更換查找結點時，指向的地址

43、始終與第一個查找的結點（即G）的地址相同，導致結果出錯，所以應在ch1=getchar();獲取新結點之后令p指針為空。　　在編程的后期，暫未考慮到found為全局變量，因此即使加上p=NULL;這條語句，得到的結果為第一次查找G結點正確、第二次查找I結點也正確，此后繼續(xù)查找不管是否存在的結點，其結果均與第二次的結果一致，顯然此為錯誤的結果。經過調試判斷后，得出found為全局變量，第一次查找存

44、在的結點時，found被賦值成1，所以導致接下來的查找過程中在FindBT函數中：if((bt!=NULL) && !found)，因為found已被賦值為1，所以，直接跳出查找退出FindBT函數，也就是沒進行查找，顯示的結果均為沒有找到！實際上根本就沒進行查找！所以應補充語句found=0；以恢復初值。到此，程序正確！　　5 課程總結&l

45、t;/p>　　課設即將結束，好高興哦。這兩周從開始的確定命題，到搜集資料，到初步編程，到修改代碼，到最終完成代碼，這是一個學習的過程，一個升華的過程。我想課設的意義也是在于此吧。剛開始接觸到課題感覺到無從下手，不知道二叉樹尋找路徑要從那方面入手，后來通過逐步的思考，認真的研究逐步的建立了整個宏觀的流程，然后就是一段時間的埋頭苦干，狂敲代碼?，F在，一切都結束了，感覺這個命題其實也不難的。這就告訴我們理論與實踐的

46、關系。想到不一定能做到，但做到了一定會想到，做到不一定有想象的那么難。只要你愿意做，就一定能做到。放手去做吧。當然課設也有很多的不足，由于剛學完數據結構沒多久，因此沒有建立一個系統(tǒng)的知識框架，在編程時大體上還是延續(xù)C的思路，并沒有過多的采用數據結構在算法和效率上進行優(yōu)化，這是此次最大的不足，最大的遺憾，也將會是今后學習的重點。　　當然，我的成功也離不開大家的幫助，所以，在此我要感謝給于過我?guī)椭?/p>

47、指導老師和熱心的同學們，謝謝大家，我也會繼續(xù)努力。　　6.參考文獻：　　[1]嚴蔚敏,吳偉民數據結構(C語言版).北京:清華大學出版社,2006.7　　[2]嚴蔚敏,吳偉民等.數據結構題集(C語言版).北京:清華大學出版社,2005.11<p&g

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

溫馨提示

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

數據結構課程設計-- 求二叉樹根結點到指定結點的路徑

文檔簡介

溫馨提示

最新文檔

評論

數據結構課程設計-- 求二叉樹根結點到指定結點的路徑

文檔簡介

溫馨提示

最新文檔

評論

免費下載