數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-- 求二叉樹(shù)根結(jié)點(diǎn)到指定結(jié)點(diǎn)的路徑

1、<p><b>　　課程設(shè)計(jì)任務(wù)書(shū)</b></p><p><b>　　目 錄</b></p><p>　　1 需求分析…………………………………………………….. 1</p><p><b>　　2 概要設(shè)計(jì)</b></p><p>　　2.1 設(shè)計(jì)思想………

2、….…………………………….………1</p><p>　　2.2 設(shè)計(jì)說(shuō)明…………………………………….………….2</p><p>　　2.3 算法流程圖………………………………….………….2</p><p><b>　　3 詳細(xì)設(shè)計(jì)</b></p><p>　　3.1源代碼……………………………………….…….

3、..........4 </p><p>　　3.2實(shí)驗(yàn)結(jié)果………………………………….……...............7</p><p>　　4 調(diào)試分析………………………………………........…..……..9</p><p>　　5 課設(shè)總結(jié)………………………………………………..……..9</p><p>　　6 參考文獻(xiàn)………

4、………………………………………..……..10</p><p><b>　　1.需求分析</b></p><p>　　1、定義二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)中設(shè)置三個(gè)域，即值域、左指針域、右指針域。要建立二叉樹(shù)T的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，即建立二叉鏈表?？刹捎孟刃蛐蛄羞f歸建立二叉樹(shù)，建立如下圖所示的二叉樹(shù)。應(yīng)該在程序運(yùn)行窗口的主控菜單后，先選擇“1”并回車(chē)，緊接著在程序運(yùn)行窗口中提

5、示信息“輸入二叉樹(shù)的先序序列結(jié)點(diǎn)值:”之后，采用以下字符序列：ABC@@DE@G@@F@@@ （以@替代空格）作為建立二叉樹(shù)T的輸入字符序列并回車(chē)，窗口出現(xiàn)：二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)建立完成! </p><p>　　2、求二叉樹(shù)的指定結(jié)點(diǎn)路徑。在程序運(yùn)行窗口的主控菜單中選擇“2” 并回車(chē)，在程序運(yùn)行窗口中提示信息“輸入要求路徑的結(jié)點(diǎn)值:”輸入“G” 并回車(chē)，會(huì)得到結(jié)果為：→A→B→D→E→G如果輸入“I” 并回車(chē)，

6、會(huì)得到結(jié)果為：沒(méi)有要求的結(jié)點(diǎn)！ </p><p><b>　　2 .概要設(shè)計(jì)</b></p><p><b>　　2.1 設(shè)計(jì)思想</b></p><p>　　在二叉樹(shù)上無(wú)論采用哪種遍歷方法，都能夠訪問(wèn)遍樹(shù)中的所有結(jié)點(diǎn)。由于訪問(wèn)結(jié)點(diǎn)的順序不同，前序遍歷和中序遍歷都很難達(dá)到設(shè)計(jì)的要求；但采用后序遍歷二叉樹(shù)是可行的，因?yàn)楹笮虮?/p>

7、歷是最后訪問(wèn)根結(jié)點(diǎn)，按這個(gè)順序?qū)⒃L問(wèn)過(guò)的結(jié)點(diǎn)存儲(chǔ)到一個(gè)順序棧中，然后再輸出即可。因此，我們可以非遞歸地后序遍歷二叉樹(shù)T，當(dāng)后序遍歷訪問(wèn)到結(jié)點(diǎn)*p時(shí)，此時(shí)棧中存放的所有結(jié)點(diǎn)均為給定結(jié)點(diǎn)*p的祖先，而由這些祖先便構(gòu)成了一條從根結(jié)點(diǎn)到結(jié)點(diǎn)*p之間的路徑。</p><p><b>　　2.2設(shè)計(jì)說(shuō)明</b></p><p>　　為實(shí)現(xiàn)上述的設(shè)計(jì)思想，首先要定義二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)

8、結(jié)構(gòu)，采用二叉鏈表的方式，相應(yīng)的類(lèi)型說(shuō)明為：</p><p>　　typedef char DataType;</p><p>　　typedef struct node{</p><p>　　DataType data;</p><p>　　struct node *lchild,*rchild;</p><p>　

9、　}BinTNode,*BinTree;</p><p>　　函數(shù)調(diào)用關(guān)系如下圖所示：</p><p><b>　　函數(shù)接口說(shuō)明:</b></p><p>　　Status CreateBiTree(BinTree &bt) /*按照先序遍歷次序遞歸建立二叉樹(shù)*/</p><p>　　Void NodePath(

10、BinTree bt,BinTNode *ch) /*求二叉樹(shù)根結(jié)點(diǎn)到給定結(jié)點(diǎn)*p的路徑*/</p><p>　　BinTNode *Findx(BinTree bt,DataType x)/*按給定值查找結(jié)點(diǎn)*/</p><p><b>　　實(shí)現(xiàn)注釋?zhuān)?lt;/b></p><p>　　二叉樹(shù)的創(chuàng)建模塊: 按照先序遍歷次序遞歸建立二叉樹(shù),通過(guò)讀入的

11、字符，分配存儲(chǔ)空間生成新結(jié)點(diǎn)后再逐個(gè)構(gòu)建根結(jié)點(diǎn)、左子樹(shù)和右子樹(shù)。</p><p>　　二叉樹(shù)指定結(jié)點(diǎn)路徑模塊：該模塊由NodePath、FindBT、Findx三個(gè)函數(shù)體構(gòu)成，main函數(shù)通過(guò)先調(diào)用Findx 函數(shù)來(lái)查找結(jié)點(diǎn)，F(xiàn)indx又通過(guò)逐步調(diào)用FindBT函數(shù)遍歷查找結(jié)點(diǎn)的路徑，最后main函數(shù)再通過(guò)調(diào)用NodePath函數(shù)得到給定結(jié)點(diǎn)的路徑。該模塊需定義全局變量p和found以方便查找，否則容易出錯(cuò)，出錯(cuò)

12、情況見(jiàn)調(diào)試報(bào)告。</p><p><b>　　2.3算法流程圖</b></p><p><b>　　top--</b></p><p><b>　　Y</b></p><p><b>　　N</b></p><p><b>

13、;　　Y</b></p><p>　　圖1——指定結(jié)點(diǎn)路徑流程圖</p><p>　　圖2——程序主流程圖</p><p><b>　　詳細(xì)設(shè)計(jì)</b></p><p><b>　　3.1源代碼</b></p><p>　　#include <stdio.h

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

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

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

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

18、t;</p><p>　　bt=(BinTNode *)malloc(sizeof(BinTNode));</p><p>　　bt->data=ch; //生成根結(jié)點(diǎn)</p><p>　　CreateBiTree(bt->lchild); //構(gòu)造左子樹(shù)</p><p>　　CreateBiTree(bt->rchil

19、d); //構(gòu)造右子樹(shù)</p><p><b>　　}</b></p><p>　　return OK;</p><p><b>　　}</b></p><p>　　void NodePath(BinTree bt,BinTNode *ch)</p><p>　　{//求

20、二叉樹(shù)根結(jié)點(diǎn)到給定結(jié)點(diǎn)*p的路徑</p><p>　　typedef enum {FALSE,TRUE}boolean;</p><p>　　BinTNode *stack[num]; //定義棧</p><p>　　int tag[num];</p><p>　　int i,top;</p><p>　　boolea

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

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

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

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

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

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

27、;rchild; //掃描右子樹(shù)</p><p>　　tag[top]=1;</p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　s=NULL;</b></p><p><b>　　

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

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

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

31、lt;p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　BinTNode *Findx(BinTree bt,DataType x)</p><p>　　{//按給定值查找結(jié)點(diǎn)</p>

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

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

34、;b>　　while(xz)</b></p><p><b>　　{</b></p><p>　　printf("建立二叉樹(shù)并求指定結(jié)點(diǎn)路徑\n");</p><p>　　printf(" 歡 迎 光 臨\n");</p><p>　　printf(

35、"===========================\n");</p><p>　　printf("1.建立二叉樹(shù)的存儲(chǔ)結(jié)構(gòu) \n");</p><p>　　printf("\n");</p><p>　　printf("2.求二叉樹(shù)指定結(jié)點(diǎn)的路徑 \n");</p>

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

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

38、序序列結(jié)點(diǎn)值:\n");</p><p>　　CreateBiTree(bt);</p><p>　　printf("二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)建立完成! \n");</p><p>　　printf("\n");</p><p><b>　　break;</b></p&

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

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

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

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

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

44、在的結(jié)點(diǎn)時(shí)，found被賦值成1，所以導(dǎo)致接下來(lái)的查找過(guò)程中在FindBT函數(shù)中：if((bt!=NULL) && !found)，因?yàn)閒ound已被賦值為1，所以，直接跳出查找退出FindBT函數(shù)，也就是沒(méi)進(jìn)行查找，顯示的結(jié)果均為沒(méi)有找到！實(shí)際上根本就沒(méi)進(jìn)行查找！所以應(yīng)補(bǔ)充語(yǔ)句found=0；以恢復(fù)初值。到此，程序正確！</p><p><b>　　5 課程總結(jié)</b>&l

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

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

47、指導(dǎo)老師和熱心的同學(xué)們，謝謝大家，我也會(huì)繼續(xù)努力。</p><p><b>　　6.參考文獻(xiàn)：</b></p><p>　　[1]嚴(yán)蔚敏,吳偉民數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版).北京:清華大學(xué)出版社,2006.7</p><p>　　[2]嚴(yán)蔚敏,吳偉民等.數(shù)據(jù)結(jié)構(gòu)題集(C語(yǔ)言版).北京:清華大學(xué)出版社,2005.11</p><p&g