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

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

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

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

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

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

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

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

8、的連接圖可以建立許多不同的無向圖，每一個(gè)無向圖都可以表示一個(gè)道路網(wǎng)，其中要選擇一個(gè)最優(yōu)圖，使圖上各邊最小。</p><p>　　關(guān)鍵字：節(jié)點(diǎn)，連通圖，最小生成樹，定點(diǎn)，鄰接點(diǎn)</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é)模型的一個(gè)重要工具，它是一門狠重要的學(xué)科，也是一門很實(shí)用的學(xué)科，例如在社會(huì)科學(xué)，語言學(xué)，計(jì)算機(jī)科學(xué)，信息論等各個(gè)方面都有著廣泛的應(yīng)用，圖有許多種表示方法，但是當(dāng)圖中的接點(diǎn)和邊的數(shù)目都很大時(shí)，圖的另一種方便的表示方法是用

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

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

14、存儲(chǔ)結(jié)構(gòu)既不選用鄰接矩陣的數(shù)組表示法，也不選用鄰接表，而是以存儲(chǔ)的數(shù)組表示圖?；疽笕缦拢河绵徑泳仃嚤硎緹o向圖，應(yīng)顯示所選中的村莊到各村莊的最短距離。假設(shè)i到j(luò)直接路徑的距離為a，如果在一接點(diǎn)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è)計(jì)</b></p><

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

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

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

18、<p>　　for（u=0；u<GRA.vexnum;++u）// 求各對(duì)頂點(diǎn)的最短路徑</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; //圖的最大頂點(diǎn)數(shù)</p><p>　　const int LARGEST=43526; //無窮大量 </p><p>　　struct VAGraph //存儲(chǔ)頂點(diǎn)信息和邊的信息</p><p><

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

22、t;<p><b>　　}</b></p><p><b>　　6程序設(shè)計(jì)及實(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é)點(diǎn)類型*/</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é)點(diǎn)*/</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é)點(diǎn)*/</p><p>　　{ if(!(*Thrt=(BiThrTree)malloc(sizeof(BiThrNode)))) exit(0);</p><p>　　(*Thrt)->LTag=Link;(*Thrt)->RTag=Thread;/*建頭結(jié)點(diǎn)*/</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);/*中序遍歷進(jìn)行中序線索化*/</p><p>　　pre->rchild=*Thrt;pre->RTag=Thread;/*最后一個(gè)結(jié)點(diǎn)線索化*/</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é)點(diǎn)，頭結(jié)點(diǎn)的左鏈lchild指向根結(jié)點(diǎn)，中序遍厲二叉樹*/</p><p>　　{BiThrTree p;</p><p>　　p=T->lchild;/*p指向根結(jié)點(diǎn)*/<

37、;/p><p>　　while(p!=T)/*空樹或遍厲結(jié)束時(shí)，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é)點(diǎn)*/</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>　　{ /*測(cè)試程序*/</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è)計(jì)體會(huì)：在設(shè)計(jì)過程中，對(duì)中序遍歷和先序，后序容易弄混淆，需仔細(xì)弄懂 。方正確運(yùn)用。</p><p>　　8結(jié)束語：在編程過程中，了解到了一些算法的重要性和實(shí)用性，對(duì)遍歷有了更深入的了解。</p><p>　　深深的體會(huì)到，在編程的道路上，自己還有很長(zhǎng)的道路要走，雖然自己實(shí)力有限，但是我相信，我會(huì)在編程這條道路上走的更遠(yuǎn) <

42、/p><p><b>　　9參考文獻(xiàn)</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><