數(shù)據(jù)結(jié)構(gòu)課程設(shè)計---二叉樹和中序遍歷的演示

1、<p><b>　　課 程 設(shè) 計</b></p><p><b>　　課程設(shè)計任務(wù)書</b></p><p>　　題 目: 二叉樹的建立和中序遍歷的演示</p><p><b>　　課程設(shè)計要求:</b></p><p>　　1、熟練掌握基本的數(shù)據(jù)結(jié)構(gòu)；<

2、/p><p>　　2、熟練掌握各種算法；</p><p>　　3、運用高級語言編寫質(zhì)量高、風(fēng)格好的應(yīng)用程序。</p><p><b>　　課程設(shè)計任務(wù): </b></p><p>　　1、系統(tǒng)應(yīng)具備的功能：</p><p>　　（1）以二叉鏈為存儲結(jié)構(gòu),建立二叉樹</p><p&

3、gt;　?。?）用遞歸算法和非遞歸算法實現(xiàn)二叉樹的中序遍歷</p><p>　?。?）二叉樹中序遍歷的演示</p><p><b>　　2、數(shù)據(jù)結(jié)構(gòu)設(shè)計；</b></p><p><b>　　3、主要算法設(shè)計；</b></p><p>　　4、編程及上機實現(xiàn)；</p><p>

4、;　　5、撰寫課程設(shè)計報告，包括：</p><p><b>　?。?）設(shè)計題目；</b></p><p>　?。?）摘要和關(guān)鍵字；</p><p>　?。?）正文，包括引言、需求分析、數(shù)據(jù)結(jié)構(gòu)設(shè)計、算法設(shè)計、程序?qū)崿F(xiàn)及測試、不足之處、設(shè)計體會等；</p><p><b>　?。?）結(jié)束語；</b>&

5、lt;/p><p><b>　?。?）參考文獻。</b></p><p>　　時間安排： 2008年7月5日－9日 （第19周）</p><p>　　7月5日 查閱資料</p><p>　　7月6日 系統(tǒng)設(shè)計，數(shù)據(jù)結(jié)構(gòu)設(shè)計，算法設(shè)計</p><p>　　7月7日 -8日 編程并上機調(diào)

6、試</p><p>　　7月9日 撰寫報告</p><p>　　7月10日 驗收程序，提交設(shè)計報告書。</p><p>　　指導(dǎo)教師簽名： 2010年7月4日 </p><p>　　系主任（或責(zé)任教師）簽名： 2010年7月4日</p><p&

7、gt;　　二叉樹和中序遍歷的演示</p><p>　　摘要：有n個村莊，現(xiàn)在從這n個村莊中選擇一個村莊新建一所醫(yī)院，使其余的村莊到這所醫(yī)院的距離總體來說較短，設(shè)計較合理?？梢詫栴}抽象為有n個接點，在這n個接點之間建立一個無向圖，邊上的權(quán)值w（i，j）表示村莊i到j(luò)之間道路的長度，我們知道，在無向圖n個接點之間，最多可能設(shè)置n（n-1）/2條線路，如何在這些線路中選擇n-1條線路，以使得總的線路最短？對于n個定點

8、的連接圖可以建立許多不同的無向圖，每一個無向圖都可以表示一個道路網(wǎng)，其中要選擇一個最優(yōu)圖，使圖上各邊最小。</p><p>　　關(guān)鍵字：節(jié)點，連通圖，最小生成樹，定點，鄰接點</p><p>　　Abstract: n village, now there from the n village choose a village a new hospital, make the rest o

9、f the village to the hospital's distance is short, the overall design more reasonable. Can be abstracted as have n contact, in the n contacts between a directed graph, on the edge of the weights, j w (I) says the vil

10、lage the length of the road between j, we know, in the graph, n contacts may set up between n (n) / 2 line in these lines, how to select n - 1 line, to make the general line is the short</p><p>　　Key words:

11、node, connected graph, minimum </p><p><b>　　1 引言</b></p><p>　　圖是建立和處理離散數(shù)學(xué)模型的一個重要工具，它是一門狠重要的學(xué)科，也是一門很實用的學(xué)科，例如在社會科學(xué)，語言學(xué)，計算機科學(xué)，信息論等各個方面都有著廣泛的應(yīng)用，圖有許多種表示方法，但是當(dāng)圖中的接點和邊的數(shù)目都很大時，圖的另一種方便的表示方法是用

12、相應(yīng)的矩陣表示，這種表示方法有很多優(yōu)點，它使得圖的有關(guān)信息能以矩陣的形式在計算機中存儲起來并加以變換，利用矩陣的表示方法及其運算還可以得到圖的一些有關(guān)行質(zhì)，在這個程序中，用到了圖論中的樹的有關(guān)知識，醫(yī)院選址這個問題有著明顯的實際背景，例如要在n個城市之間鋪設(shè)光纜，如何才能使付出的代價最小等問題，都要用到圖的有關(guān)知識。在信息高速發(fā)展的今天，濟濟全球化已經(jīng)呈明顯的趨勢，如何在不同的提放建立最優(yōu)的道路網(wǎng)和信息網(wǎng)，已成為社會競爭力中很重要的因素

13、，這不僅關(guān)系到要付出的經(jīng)濟代價，而且也關(guān)系到誰先占有主動權(quán)的問題。有鑒于此，我就做了這個程序，一則為了完成課程設(shè)計，而則也為了鍛煉自己，多學(xué)點東西</p><p><b>　　2 需求分析</b></p><p>　　數(shù)據(jù)的讀入，存儲，生成文件，將鍵盤輸入的信息存入指定的文件中；設(shè)計一程序求解詞問題。圖的存儲結(jié)構(gòu)和選取應(yīng)和所操作相適應(yīng)。為了便于選擇權(quán)值最小的邊。此題的

14、存儲結(jié)構(gòu)既不選用鄰接矩陣的數(shù)組表示法，也不選用鄰接表，而是以存儲的數(shù)組表示圖?；疽笕缦拢河绵徑泳仃嚤硎緹o向圖，應(yīng)顯示所選中的村莊到各村莊的最短距離。假設(shè)i到j(luò)直接路徑的距離為a，如果在一接點k，使i到k的距離b，k到j(luò)的距離c，且b+c<a,那么就選擇i--k--j這條路徑而不選擇的i和j的直接路徑</p><p><b>　　3數(shù)據(jù)結(jié)構(gòu)設(shè)計</b></p><

15、p>　　<stiob.h>,<string,h>,<iomanip.h>,<iostream.h>為包含的庫函數(shù)</p><p>　　const int MAX_VEXNUM=30;圖的最大頂點數(shù)</p><p>　　const intLARGEST=43526; 定義無窮大</p><p>　　vexnum ，

16、arcnum ； 圖中當(dāng)前頂點數(shù)和弧數(shù)</p><p>　　vexs[MAX_VEXNUM];頂點向量，用于存儲頂點的信息</p><p>　　arcs[MAX_VEXNUM][MAX_VEXNUM]; 鄰接矩陣，用于存儲邊的信息 </p><p><b>　　4 算法設(shè)計 </b></p><p>　　采用最短路徑算

17、法 ，求各村莊之間的最短路徑，這是該程序的核心算法。</p><p>　　void FloydGetRsult （VAGraph GAR）</p><p>　　{//用Floyed算法求有向圖網(wǎng)G中個對頂點的最短路徑長度D[v][w]</p><p>　　int D [MAX_VEXNUM][MAX_VEXNUM];//最短路徑的帶權(quán)長度矩陣</p>

18、<p>　　for（u=0；u<GRA.vexnum;++u）// 求各對頂點的最短路徑</p><p>　　for（w=0；w<GRA.vexnum;++w)</p><p>　　if(D[v][u]+D[u][w]<D[v][w])</p><p>　　D[v][w]=D[v][u]+D[u][w]</p><p&

19、gt;　　//從v徑u到w的一條路徑更短</p><p>　　5 引用庫函數(shù)及變量的定義</p><p>　　#include <stdlib.h></p><p>　　#include <string.h></p><p>　　#include <iomanip.h></p><p&g

20、t;　　#include <iostream.h></p><p>　　const int MAX_VEXNUM=30; //圖的最大頂點數(shù)</p><p>　　const int LARGEST=43526; //無窮大量 </p><p>　　struct VAGraph //存儲頂點信息和邊的信息</p><p><

21、;b>　　{ </b></p><p>　　int vexnum ,arcnum; //圖中當(dāng)前頂點數(shù)和弧數(shù)</p><p>　　char*vexs[MAX_VEXNUM]； //頂點向量，用于存儲頂點的信息</p><p>　　int arcs [MAX_VEXNUM][MAX_VEXNUM]; //鄰接矩陣，用于存儲邊的信息</p&g

22、t;<p><b>　　}</b></p><p><b>　　6程序設(shè)計及實現(xiàn)</b></p><p>　　#include <stdio.h></p><p>　　#include <malloc.h></p><p>　　#include<stdli

23、b.h></p><p>　　typedef char DataType;/*定義DataType類型*/</p><p>　　typedef enum {Link,Thread}PointerTag;</p><p>　　typedef struct node{</p><p>　　DataType data;</p>

24、<p>　　struct node *lchild, *rchild;/*左右孩子子樹*/</p><p>　　PointerTag LTag,RTag;</p><p>　　}BiThrNode; /*結(jié)點類型*/</p><p>　　typedef BiThrNode *BiThrTree ;/*二叉樹類型*/</p><p>

25、　　void CreatBinTree(BiThrTree *T)</p><p>　　{ /*構(gòu)造二叉鏈表,注意:輸入序列是先序序列*/</p><p><b>　　char ch;</b></p><p>　　if ((ch=getchar())==' ')</p><p><b>　　*

26、T=NULL;</b></p><p>　　else{ /*生成結(jié)點*/</p><p>　　*T=(BiThrNode *)malloc(sizeof(BiThrNode));</p><p><b>　　/*讀入非空格*/</b></p><p>　　(*T)->data=ch;</p>

27、<p>　　(*T)->LTag=Link;</p><p>　　(*T)->RTag=Link;</p><p>　　CreatBinTree(&(*T)->lchild); /*構(gòu)造左子樹 */</p><p>　　printf("\ngood\n");</p><p>　

28、　CreatBinTree(&(*T)->rchild); /*構(gòu)造右子樹*/</p><p>　　printf("\ngood1\n");</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　BiThrTree pr

29、e;/*全局變量*/</p><p>　　void InThreading(BiThrTree p)</p><p><b>　　{ </b></p><p><b>　　if(p)</b></p><p>　　{InThreading(p->lchild);/*左子樹線索化*/</p&

30、gt;<p>　　if(!p->lchild){p->LTag=Thread;p->lchild=pre;}/*前驅(qū)線索*/</p><p>　　if(!pre->rchild){pre->RTag=Thread;pre->rchild=p;}/*后繼線索*/</p><p>　　pre=p;/*保持pre指向p*/</p>

31、<p>　　InThreading(p->rchild);/*右子樹線索化*/</p><p><b>　　}</b></p><p><b>　　} </b></p><p>　　int InOrderThreading(BiThrTree *Thrt,BiThrTree T)</p>&l

32、t;p>　　/*中序遍厲二叉樹T，并將其中序線索化，Thrt指向頭結(jié)點*/</p><p>　　{ if(!(*Thrt=(BiThrTree)malloc(sizeof(BiThrNode)))) exit(0);</p><p>　　(*Thrt)->LTag=Link;(*Thrt)->RTag=Thread;/*建頭結(jié)點*/</p><p>

33、;　　(*Thrt)->rchild=*Thrt;/*右指針回指*/</p><p>　　if(!T) (*Thrt)->lchild=*Thrt;</p><p><b>　　else</b></p><p>　　{ (*Thrt)->lchild=T;pre=*Thrt;</p><p>　　InT

34、hreading(T);/*中序遍歷進行中序線索化*/</p><p>　　pre->rchild=*Thrt;pre->RTag=Thread;/*最后一個結(jié)點線索化*/</p><p>　　(*Thrt)->rchild=pre;</p><p><b>　　}</b></p><p><b&

35、gt;　　return 1;</b></p><p><b>　　}</b></p><p>　　int print(BiThrTree e)</p><p>　　{printf("%d %c %d\n",e->LTag,e->data,e->RTag);return 1;}</p&g

36、t;<p>　　int InOrderTraverse(BiThrTree T,int (* visit)(BiThrTree e))</p><p>　　/*T指向頭結(jié)點，頭結(jié)點的左鏈lchild指向根結(jié)點，中序遍厲二叉樹*/</p><p>　　{BiThrTree p;</p><p>　　p=T->lchild;/*p指向根結(jié)點*/<

37、;/p><p>　　while(p!=T)/*空樹或遍厲結(jié)束時，p==T*/</p><p>　　{while(p->LTag==Link) p=p->lchild;</p><p>　　if(!visit(p)) return 0;/*打印*/</p><p>　　while(p->RTag==Thread&&

38、p->rchild!=T)</p><p>　　{p=p->rchild;visit(p);}/*訪問后繼結(jié)點*/</p><p>　　p=p->rchild;</p><p><b>　　}</b></p><p><b>　　return 1;</b></p>&

39、lt;p><b>　　}</b></p><p>　　void main()</p><p>　　{ /*測試程序*/</p><p>　　BiThrTree T,Thrt;</p><p>　　if(Link==0)printf("yes");</p><p>　　if

40、(Thread==1)printf("yes");</p><p>　　CreatBinTree(&T);</p><p>　　InOrderThreading(&Thrt,T);</p><p>　　InOrderTraverse(Thrt,print);</p><p><b>　　}<

41、/b></p><p>　　7設(shè)計體會：在設(shè)計過程中，對中序遍歷和先序，后序容易弄混淆，需仔細弄懂 。方正確運用。</p><p>　　8結(jié)束語：在編程過程中，了解到了一些算法的重要性和實用性，對遍歷有了更深入的了解。</p><p>　　深深的體會到，在編程的道路上，自己還有很長的道路要走，雖然自己實力有限，但是我相信，我會在編程這條道路上走的更遠 <

42、/p><p><b>　　9參考文獻</b></p><p>　　[1] C++ 編程思想，劉宗田等 譯</p><p>　　[2] C++程序語言經(jīng)典本，葉秉哲 譯，儒林 1999</p><p>　　[3]標(biāo)準(zhǔn)C++寶典，林麗閩等 譯，766頁[4]C++語言核心，張銘澤 譯 ，236頁</p><