數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告-二叉樹根節(jié)點到指定節(jié)點的路徑

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告-二叉樹根節(jié)點到指定節(jié)點的路徑 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告 二叉樹根節(jié)點到指定節(jié)點的路徑 遞歸調(diào)用思想 班 級： 軟件092 姓名：_ 指導(dǎo)教師：成績：信息工程學(xué)院 2011年6月17日-2 -摘要（題目）：二 叉樹根節(jié)點到指定節(jié)點的路徑1.引言 二叉樹是n個結(jié)點的有窮個集合，它或者是空集（n=0 ）,或者同時滿足以下 兩個條件；（1）有且僅有一個稱為根的結(jié)點；（2）其余 結(jié)點分為兩個互不相交的集合 T1 , T2 ,并且T1 , T2 ,都是 二叉樹，分別 稱為根的左子樹和右子樹 。二叉樹形結(jié)構(gòu)在 客觀世界中大量存在，如行政組織機構(gòu)和人類社會的家譜關(guān) 系 等都可用二叉樹結(jié)構(gòu)形象

2、地表示。在計算機應(yīng)用領(lǐng)域， 二叉樹也被廣泛地應(yīng)用。例如在編譯程序中，可用二 叉樹 來表示源程序的語法結(jié)構(gòu)；在數(shù)據(jù)庫系統(tǒng)中，可用二叉樹來 表示組織信息；在計算機圖形學(xué)中，可用二叉樹來表示圖像關(guān)系等。因此對二叉樹的研究具有重要意義。2.需求分析利用一個簡單的菜單，通過菜單項進行選擇，實現(xiàn)和完成如 下功能：用先序輸入，建立二叉樹存儲結(jié)構(gòu)、求指定結(jié)點的路徑。 對于建立二叉樹存儲結(jié)構(gòu)，考慮到棧和隊列的存 儲結(jié)構(gòu)比較繁瑣，從而定義一指針數(shù)組來一一存儲該二叉樹先序遍歷過的結(jié)點，并對該結(jié)點進行判斷是否為指定的目 標(biāo)結(jié)點，并進行輸生等操作。3.概要設(shè)計 對二叉樹采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，其結(jié)構(gòu)定義如下：typedef

3、structnode DataType data; struct node*lchild,*rchild; BinTNode,*BinTree;每個結(jié)點中設(shè)置三個域,即值域data ,左指針域*lchild 和右指針域*rchild 。 本 程序分為6大模塊：全局變量定義、創(chuàng)建結(jié)構(gòu)體、創(chuàng)建二叉 鏈表存儲表示、查找目標(biāo)結(jié)點、求結(jié) 點路徑、主函數(shù)。(1) 全局變量定義(2)創(chuàng)建結(jié)構(gòu)體(3)創(chuàng)建二叉鏈表存儲表示：定義二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)，輸入數(shù)據(jù)生成二叉樹。(4)查找目標(biāo)結(jié)點：采用二叉鏈表作為存儲結(jié)構(gòu)，利用遞歸方法，對各個結(jié)點進行判斷改結(jié)點是否在二叉樹中。-3 -(5)求結(jié)點路徑：采用二叉鏈表作為存

4、儲結(jié)構(gòu)，利用先序遍歷二 叉樹方法以及指針數(shù)組的存儲結(jié)構(gòu)方法，對結(jié)點路徑的遍歷查找及輸由。(6)主函數(shù) 程序流程圖 重要函數(shù)有 主函數(shù)int main () 輸入函數(shù) scanf () 輸由函數(shù) printf () 二叉樹的先序建立函數(shù)CreateBiTree () 結(jié)點查找函數(shù)FindBT ()求結(jié)點路徑函數(shù)NodePath () 4.詳細(xì)設(shè)計 (1)定義二叉樹 用鏈?zhǔn)酱鎯Y(jié)構(gòu)存儲二叉樹。其中，了 lchild和rchild是分別指向該結(jié)點左孩子和右孩子的指針，data是數(shù)據(jù)元素的內(nèi)容。定義二叉樹結(jié)點值的類型為字符型且結(jié)點個 數(shù)不超過100個，具體實現(xiàn)方法如下：二叉樹的根節(jié)點到指定節(jié)點的路徑

5、主程序代碼 輸入函數(shù)輸由函數(shù) 建立函數(shù)查找函數(shù)求路徑函數(shù)-4 - typedef struct node DataType data; struct node*lchild,*rchild; BinTNode,*BinTree; (2)建立二叉樹創(chuàng) 建二叉鏈表存儲的二叉樹。按二叉樹帶空指針的先序次序輸 入結(jié)點值，結(jié)點類型為字符型。按先序 次序輸入，其中“ 表示空結(jié)點。算法是按照先序遍歷思想設(shè)計的。構(gòu)造二叉鏈 表表示的二叉樹，符號 表示空樹。具體實現(xiàn)方法如下： Status CreateBiTree(BinTree &bt) char ch; printf(ch=); scanf(%c,&ch)

6、; getchar(); if (ch=) bt=NULL; else bt=(BinTNode *)malloc(sizeof(BinTNode); bt-data=ch; /生成根結(jié)點 CreateBiTree(bt-lchild); /構(gòu)造左子樹CreateBiTree(bt-rchild); / 構(gòu)造右子樹 return OK; (3)查找函數(shù)-5 -函數(shù)功能是用遞歸方法對二叉樹進行先序遍 歷查找，調(diào)用此函數(shù)可以返回二叉樹中指定目標(biāo)結(jié)點。算 法思想：若找到目標(biāo)結(jié)點，則返回該目標(biāo)結(jié)點；否則訪問二叉 樹的根結(jié)點；先序遍歷根的左子樹；先序遍歷根的右子樹。具體實現(xiàn)方法如下：void FindB

7、T(BinTree bt,DataType x) if(bt!=NULL) & !found) if(bt-data=x) p=bt;found=1; else FindBT(bt-lchild,x); /遍歷查找左子樹 FindBT(bt-rchild,x); /遍歷查找右子樹 BinTNode *Findx(BinTree bt,DataType x) /按給定值查找結(jié)點int found=0; / 用found來作為是否查找到的標(biāo)志 BinTree p=NULL; / 置空指針 FindBT(bt,x); return(p); 7)求指定結(jié)點路徑：該函數(shù)功能是根據(jù)已創(chuàng)建的二叉樹和輸入的目

8、標(biāo)結(jié)點，調(diào)用此函數(shù)可以查找并輸由目標(biāo)結(jié)點的路 徑。算法思想：根據(jù)先序遍歷二叉樹的遞歸定義，采用一 個指針數(shù)組來保存返回的結(jié)點。先掃描根結(jié)點的左子樹上的結(jié)點并寫入指針數(shù)組。判斷該結(jié)點是否與指定目標(biāo)結(jié)點相 等，若不相等，然后掃描該結(jié)點的右結(jié)點并寫-6-入指針數(shù)組，再掃描該右結(jié)點的所有左結(jié)點寫入指針數(shù)組。當(dāng)一個 結(jié)點的左孩子樹均訪問完后再訪問該結(jié)點，并與給定的結(jié)點比較。若相等，則循環(huán)輸由指針數(shù)組中的所有元素，而這 個順序值就是要求的路徑。若不相等，則繼續(xù)上述過程。具體實現(xiàn)方法如下：void NodePath(BinTree bt,BinTNode*ch) /求二叉樹根結(jié)點到給定結(jié)點*p的路徑type

9、defenum FALSE,TRUEboolean; BinTNode *stacknum; / 定 義指針數(shù)組 int tagnum; int i,top; boolean find; BinTNode*s; find=FALSE; top=0; s=bt; do while(s!=NULL) / 掃描 左子樹 top+; stacktop=s; tagtop=0; s=s-lchild;if(top0) s=stacktop; if(tagtop=1) - 7 - if(s=ch) 找到ch,則顯示從根結(jié)點到 ch的路徑 for(i=1;i%c,stacki-data);find=TRUE

10、; else top-; s=stacktop; /endif if(top0& !find) if(tagtop!=1) s=s-rchild; /掃描右子樹tagtop=1; else s=NULL; /endif /endlif while(!find& top!=0); (8)主函數(shù)：-8 -該函數(shù)為程序的主函數(shù)功能是循環(huán)輸由菜單，功能界面；從界面獲取功能菜單中對 應(yīng)的字符，通過 switch()語句實現(xiàn)對函數(shù)的調(diào)用，進而實現(xiàn) 功能。具體代碼如下： int main() bool isStop; BinTree bt; char ch1; int xz=1; printf(t *n);

11、 printf(t *ttttttt *n); printf(t*tt歡迎來到這里 tt *n); printf(t * t t建立二叉樹并求指定結(jié)點路徑 t t *n); printf(t *ttttttt *n);printf(t*n); while(xz) /*輸由菜單，功能*/printf(n n); printf(=n); - 9 - printf( 1.建立二叉樹的存儲結(jié)構(gòu)n); printf( 2.求二叉樹指定結(jié)點的路徑n);printf( O.Exit System!n); printf(=n); printf( 請選擇:(0-2)n);scanf(%d”,&xz); getc

12、har(); switch(xz) case 1:printf( 輸 入二叉樹的先序序列結(jié)點值:n); CreateBiTree(bt); printf(二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)建立完成！ n); printf(n); break;case 2:printf(路徑的節(jié)點值是：n); ch1=getchar();p=NULL; found=0; Findx(bt,ch1); if(p!=NULL) - 10 - NodePath(bt,p); else printf(沒有要求的節(jié)點!n);printf(n); break; / switch / while 源程序：#include #include

13、 #define num 100 #define OK 1 typedef int Status; typedef char DataType; typedef struct node DataType data; struct node*lchild,*rchild; BinTNode,*BinTree; int found; BinTNode*p; Status CreateBiTree(BinTree &bt) - 11 - char ch;printf(ch=); scanf(%c”,&ch); getchar(); if (ch=)bt=NULL; else bt=(BinTNode

14、 *)malloc(sizeof(BinTNode); bt-data=ch; /生成根結(jié)點 CreateBiTree(bt-lchild); / 構(gòu)造左子樹 CreateBiTree(bt-rchild); /構(gòu)造右子樹 returnOK; void NodePath(BinTree bt,BinTNode *ch) / 求二叉 樹根結(jié)點到給定結(jié)點 *p的路徑typedef enum FALSE,TRUEboolean; BinTNode *stacknum; / 定義棧 int tagnum; int i,top; boolean find; BinTNode *s;find=FALSE;

15、 top=0; s=bt; - 12 - do while(s!=NULL) / 掃描左子樹 top+; stacktop=s; tagtop=0;s=s-lchild; if(top0) s=stacktop; if(tagtop=1) if(s=ch) / 找到ch,則顯示從根結(jié)點到 ch的路徑 for(i=1;i%c,stacki-data);find=TRUE; else top-; s=stacktop; /endif if(top0& !find) - 13 - if(tagtop!=1) s=s-rchild; /掃描右子樹 tagtop=1; elses=NULL; /endi

16、f /endlif while(!find & top!=0); void FindBT(BinTree bt,DataType x) if(bt!=NULL) & !found) if(bt-data=x) p=bt;found=1; else FindBT(bt-lchild,x); /遍歷查找左子樹FindBT(bt-rchild,x); / 遍歷查找右子樹 - 14 - BinTNode *Findx(BinTree bt,DataType x) /按給定值查找結(jié)點int found=0; / 用found來作為是否查找到的標(biāo)志 BinTree p=NULL; / 置空指針 FindB

17、T(bt,x); return(p); int main() bool isStop; BinTree bt; char ch1; int xz=1;printf(t*n，)； printf(t *ttttttt *n); printf(t*tt 歡迎來到這里 tt *n); printf(t * t t建立二叉樹并求指定結(jié)點路徑 t t *n); printf(t *ttttttt *n);printf(t*n); - 15 - while(xz) /*輸生菜單，功能* printf(n n); printf(=n); printf( 1.建立二叉樹的存儲結(jié)構(gòu)n); printf( 2.求二

18、叉樹指定結(jié)點的路徑n); printf(0.Exit System!n); printf(=n); printf( 請選擇:(0-2)n);scanf(%d,&xz); getchar(); switch(xz) case 1:printf( 輸 入二叉樹的先序序列結(jié)點值 :n); CreateBiTree(bt); printf( 二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)建立完成！ n); printf(n); break;-16 - case 2:printf( 路徑的節(jié)點值是：n); ch1=getchar();p=NULL; found=0; Findx(bt,ch1); if(p!=NULL) Node

19、Path(bt,p); else printf(沒有要求的節(jié)點!n);printf(n); break; switch while 5. 測試結(jié)果 -17 -18 - 6.調(diào)試分析 本設(shè)計是先序輸入的，當(dāng)然也可以中序和 后序輸入，為了減小時間和空間復(fù)雜度，所以只設(shè)計了先序 輸入。對于先序，中序，后序等訪問，需要的話，也可以 按要求加入。本設(shè)計的缺點是，輸錯了的話，要重新輸入。7.設(shè)計體會 雖然都說 程序=數(shù)據(jù)結(jié)構(gòu)+算法”，但我們在學(xué) 習(xí)運用數(shù)據(jù)結(jié)構(gòu)編程之前，并沒能深刻體會到這一點，直到 這次課設(shè)實踐。我們感受最深的一點是：以 前用C編程， 只是注重如何編寫函數(shù)能夠完成所需要的功能，似乎沒有明

20、確的戰(zhàn)術(shù)，只是憑單純的意識和簡單的語句來堆砌由一段程 序。還體會到深刻理解數(shù)據(jù)結(jié)構(gòu)的重要性。只有真正理解 這樣定義數(shù)據(jù)類型的好處，才能用好這樣一種數(shù)據(jù)結(jié)構(gòu)。了解典型數(shù)據(jù)結(jié)構(gòu)的性質(zhì)是非常有用的，它往往是編寫程序的關(guān)鍵。以前對遞歸算法一直很害怕，總是看不明白究竟這 遞歸是怎么進行的。在這次實驗中終于克服了這一障礙，一 次次單步執(zhí)行書中遞歸函數(shù)的例子，并一遍遍在心中自己默默的走，終于弄明白了，真的是功夫不負(fù)有心人??！同時 還根據(jù)自己的理解寫生了類似的遞歸函數(shù)實現(xiàn)了新的功能， 真是受 益良多??！在這次實驗中，對參數(shù)的調(diào)用也進行了 很多種嘗試，已差不多經(jīng)能夠選擇合適的參數(shù)形式來實現(xiàn)函 數(shù)之間的數(shù)據(jù)傳輸交

21、互了。這次實驗中也由現(xiàn)過一些比較嚴(yán)重的錯誤。在主函數(shù)調(diào)用CreateBiTree (&bt)的參數(shù)&bt誤 寫成元素bt,在調(diào)試程序時給我們團隊帶來一定的封面山東建筑大學(xué)2009級工程造價專業(yè)畢業(yè)設(shè)計任務(wù)書題 目：山東省職業(yè)技術(shù)學(xué)院辦公樓工程項目商務(wù)標(biāo)書設(shè)計期限：自2011年7月至2011年10月班 級： 0720913141學(xué)生姓名：學(xué) 號：指導(dǎo)教師（簽字）：任成友莊春華山東建筑大學(xué)畢業(yè)設(shè)計任務(wù)書班級學(xué)生姓名指導(dǎo)教師張琳設(shè)計題目山東省職業(yè)技術(shù)學(xué)院辦公樓工程項目商務(wù)標(biāo)書計始數(shù) 設(shè)原參1、工程概況山東省職業(yè)技術(shù)學(xué)院辦公樓項目概況：(1)建設(shè)單位：建達房地產(chǎn)升發(fā)有限公司2)本工程為辦公樓，具體位置

22、詳見規(guī)劃總平面圖3)本工程總建筑面積5195.74平方米4)本工程五層，一層層圖4.2m,二-四層圖3.9m,五層層圖4.2m, 建度 29.74m,室內(nèi)外展 0.60m。5)本工程結(jié)構(gòu)形式：框架結(jié)構(gòu)，抗震設(shè)防烈度：6度6)本工程建筑等級：三級；耐火等級：為二級。7)本工程設(shè)計使用年限：3類(合理使用50年)8)屋間防水等級：二級2、工程特點本工程為重點工程，業(yè)主要求盡量采用施工新技術(shù)并要求必須按合 同工期完工。施工現(xiàn)場狹小，應(yīng)考慮合理利用現(xiàn)場空間。3、資金籌措條件(D工程合同價c=a程報價；(2)開工前業(yè)主撥付工程備料款 A=20% C;(3)工程進度款，每月末按形象進度延遲一個月?lián)芨叮?4

23、)不足部分通過銀行貸款補足，貸款利率 =12%(單利)；(5) /、考慮保修金的留設(shè)。(6)現(xiàn)場條件：已實現(xiàn)三通一平.(7)工程量清單(8)施工圖(另附)設(shè)計 工作 內(nèi)容1、撰寫招標(biāo)文件，編制工程量清單以施工圖紙為依據(jù)，根據(jù)國家標(biāo)準(zhǔn)建設(shè)工程工程量清單計價規(guī) 范、及山東省現(xiàn)行消耗量定額進行編制。鼓勵學(xué)生在完成手工預(yù)算的 全部工作的基礎(chǔ)上，另用工程造價編制軟件對手算的結(jié)果進行校審復(fù) 核。工程量清單編制的內(nèi)容后；(1)均回；(2)總說明；(3)分部分項，程量清單；(4)措施項目清單；(5)其他項目清單；2、編制投標(biāo)文件投標(biāo)文件只編寫商務(wù)標(biāo)部分(1)商務(wù)部分主要包括卜列內(nèi)容：1)投標(biāo)函：2)建安工程唱

24、標(biāo)單；3）法定代表人資格證明書；4）法定代表人授權(quán)書；5）投標(biāo)保證金。6）報價單（2）商務(wù)標(biāo)編制：計算工程量；確定綜合單價；進行投標(biāo)報價；編制 報價匯總表，和各類投標(biāo)報價單價表。投標(biāo)報價說明；投標(biāo)報價匯總表；主要材料清單報價表；分部分項 工程量清單報價表；措施項目報價表；其他項目報價表；規(guī)費與稅金工 程量清單項目報價表。1、畢業(yè)設(shè)計程序的要求（1）設(shè)計準(zhǔn)備階段畢業(yè)設(shè)計題目選定后，應(yīng)由指導(dǎo)教師向?qū)W生下達畢業(yè)設(shè)計指導(dǎo)書。 學(xué)生根據(jù)畢業(yè)設(shè)計指導(dǎo)書的選題和指導(dǎo)教師的安排，應(yīng)該做好如下的準(zhǔn) 備，包括：認(rèn)真閱讀畢業(yè)設(shè)計任務(wù)書的內(nèi)容，熟悉施工圖紙，調(diào)查了解 與設(shè)計內(nèi)容相關(guān)的資料；收集相關(guān)的工具書。包括設(shè)計規(guī)范、施工規(guī)范、 預(yù)算定額、工程估價