二叉樹(shù)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

1、<p><b>　　目 錄</b></p><p>　　第一章 需求分析1</p><p>　　1.1課程設(shè)計(jì)題目1</p><p>　　1.2 課程設(shè)計(jì)任務(wù)及要求1</p><p>　　1.21 課程設(shè)計(jì)目的1</p><p>　　1.22 設(shè)計(jì)要求1</p&g

2、t;<p>　　1.3課程設(shè)計(jì)思想2</p><p>　　1.4 軟件運(yùn)行環(huán)境及開(kāi)發(fā)工具2</p><p>　　第二章概要設(shè)計(jì)3</p><p>　　2.1 數(shù)據(jù)結(jié)構(gòu)3</p><p>　　2.2 所用方法及其原理說(shuō)明3</p><p>　　第三章 詳細(xì)設(shè)計(jì)4</p><

3、;p>　　3.1 詳細(xì)設(shè)計(jì)方案4</p><p>　　3.2 模塊設(shè)計(jì)4</p><p>　　3.21 二叉樹(shù)定義4</p><p>　　3.22 樹(shù)狀顯示二叉樹(shù)設(shè)計(jì)7</p><p>　　3.22 主函數(shù)設(shè)計(jì)10</p><p>　　第四章 調(diào)試和操作說(shuō)明11</p><p&g

4、t;<b>　　4.1 調(diào)試11</b></p><p>　　4.2 操作說(shuō)明12</p><p>　　第五章 總結(jié)與體會(huì)12</p><p>　　5.1 本文的主要工作12</p><p>　　5.2 存在問(wèn)題12</p><p>　　5.3 心得體會(huì)12</p>&

5、lt;p><b>　　致 謝13</b></p><p><b>　　參考文獻(xiàn)14</b></p><p>　　第一章 需求分析</p><p><b>　　1.1課程設(shè)計(jì)題目</b></p><p>　　樹(shù)狀顯示二叉樹(shù)：編寫(xiě)函數(shù)displaytree(二叉樹(shù)

6、的根指針，數(shù)據(jù)值寬度，屏幕的寬度)輸出樹(shù)的直觀示意圖。輸出的二叉樹(shù)是垂直打印的，同層的節(jié)點(diǎn)在同一行上。[問(wèn)題描述] 假設(shè)數(shù)據(jù)寬度datawidth=2,而屏幕寬度screenwidth為64=26,假設(shè)節(jié)點(diǎn)的輸出位置用（層號(hào)，須打印的空格數(shù)）來(lái)界定。第0層：根在（0，32）處輸出；第1層：因?yàn)楦?jié)點(diǎn)縮進(jìn)了32個(gè)空格，所以下一層的偏移量（offset）為32/2=16=screenwidth/22。即第一層的兩個(gè)節(jié)點(diǎn)的位

7、置為（1，32-offset）,(1,32+offset)即（1，16），（1，48）。第二層：第二層的偏移量offset為screenwidth/23。第二層的四個(gè)節(jié)點(diǎn)的位置 分別是（2，16-offset），（2，16+offset），（2，48-offset），（2，48+offset）即（2，8），（2，24），（2，40），（2，56）?！趇層：第i層的偏移量offset為screenwidth/2i+1。第i層

8、的每個(gè)節(jié)點(diǎn)的位置是訪問(wèn)第i-1層其雙親節(jié)點(diǎn)時(shí)確定的。假設(shè)其雙親的</p><p>　　1.2 課程設(shè)計(jì)任務(wù)及要求</p><p>　　1.21 課程設(shè)計(jì)目的</p><p>　　據(jù)結(jié)構(gòu)是計(jì)算機(jī)專(zhuān)業(yè)的核心課程，是一門(mén)實(shí)踐性很強(qiáng)的課程。課程設(shè)計(jì)是加強(qiáng)學(xué)生實(shí)踐能力的一個(gè)強(qiáng)有力手段，要求學(xué)生掌握數(shù)據(jù)結(jié)構(gòu)的應(yīng)用、算法的編寫(xiě)、類(lèi)C語(yǔ)言的算法轉(zhuǎn)換成C（C++）程序并上機(jī)調(diào)試的基本

9、方法，還要求學(xué)生在完成程序設(shè)計(jì)的同時(shí)能夠?qū)懗霰容^規(guī)范的設(shè)計(jì)報(bào)告。嚴(yán)格實(shí)施課程設(shè)計(jì)這一環(huán)節(jié)，對(duì)于學(xué)生基本程序設(shè)計(jì)素養(yǎng)的培養(yǎng)和軟件工作者工作作風(fēng)的訓(xùn)練，將起到顯著的促進(jìn)作用。</p><p><b>　　1.22 設(shè)計(jì)要求</b></p><p>　　1、課程設(shè)計(jì)題目每組一題，每個(gè)學(xué)生必須獨(dú)立完成；</p><p>　　2、課程設(shè)計(jì)時(shí)間為2周；&l

10、t;/p><p>　　3、設(shè)計(jì)語(yǔ)言C（C++）不限；</p><p><b>　　4、上機(jī)任務(wù)</b></p><p>　　1）選擇合適的數(shù)據(jù)結(jié)構(gòu)，并定義數(shù)據(jù)結(jié)構(gòu)的結(jié)構(gòu)體；</p><p>　　2）根據(jù)程序所要完成的基本要求，設(shè)計(jì)出完整的算法；</p><p>　　3）設(shè)計(jì)出主程序（main函數(shù)），使

11、其成為完整的程序。 </p><p>　　6、上機(jī)時(shí)間：按照實(shí)驗(yàn)室上機(jī)時(shí)間安排計(jì)劃執(zhí)行 </p><p>　　7、無(wú)論在校外、校內(nèi)，都要嚴(yán)格遵守學(xué)校和所在單位的學(xué)習(xí)和勞動(dòng)紀(jì)律、規(guī)章制度，學(xué)生有事離校必須請(qǐng)假。課程設(shè)計(jì)期間，無(wú)故缺席按曠課處理；缺席時(shí)間達(dá)四分之一以上者，其成績(jī)按不及格處理。</p><p><b>　　1.3課程設(shè)計(jì)思想</b>&

12、lt;/p><p>　　二叉樹(shù)是一種樹(shù)形結(jié)構(gòu)，它的特點(diǎn)是每個(gè)結(jié)點(diǎn)至多有兩棵子樹(shù)，即二叉樹(shù)中不存在度大于2的結(jié)點(diǎn)，并且二叉樹(shù)的子樹(shù)有左右之分，其次序不能任意顛倒。</p><p>　　本設(shè)計(jì)主要根據(jù)二叉樹(shù)的性質(zhì)原理為設(shè)計(jì)的主體思路，二叉樹(shù)的性質(zhì)如下:</p><p>　　性質(zhì)1：在二叉樹(shù)的第i層上至多有2i-1個(gè)結(jié)點(diǎn)（i>=1）；</p><p&

13、gt;　　性質(zhì)2：深度為K的二叉樹(shù)至多有2k-1個(gè)結(jié)點(diǎn)（K>=1）；</p><p>　　性質(zhì)3：如果一棵有n各結(jié)點(diǎn)的完全二叉樹(shù)的結(jié)點(diǎn)按層次編號(hào)，則對(duì)任一結(jié)點(diǎn)i(1<=i<=n),有：</p><p>　?。?）若2i>n,則結(jié)點(diǎn)無(wú)左孩子，否則其左孩子是結(jié)點(diǎn)2i；</p><p>　?。?）若2i+1>n,則結(jié)點(diǎn)i無(wú)右孩子，否則其右孩子

14、為2i+1；</p><p>　　另外，本設(shè)計(jì)利用二叉樹(shù)的廣度優(yōu)先搜索算法實(shí)現(xiàn)。利用兩個(gè)隊(duì)列Q，QI。隊(duì)列Q中存放節(jié)點(diǎn)信息，隊(duì)列QI中存相應(yīng)于隊(duì)列Q中的節(jié)點(diǎn)的位置信息，包括層號(hào)和需要打印節(jié)點(diǎn)值時(shí)需要打印的空格數(shù)。當(dāng)節(jié)點(diǎn)被加入到Q時(shí)，相應(yīng)的打印信息被存到QI中。二叉樹(shù)本身采用二叉鏈表存儲(chǔ)。本設(shè)計(jì)應(yīng)用了C語(yǔ)言中的類(lèi)來(lái)自定義頭文件，將任務(wù)分成多個(gè)的模塊，增強(qiáng)了可讀性和簡(jiǎn)單性，同時(shí)為日后的編寫(xiě)，調(diào)試，維護(hù)提供了極大地方便

15、。</p><p>　　1.4 軟件運(yùn)行環(huán)境及開(kāi)發(fā)工具</p><p>　　本設(shè)計(jì)用到的軟件是Microsoft Visual C++ 6.0程序開(kāi)發(fā)軟件，Microsoft Visual C++ 6.0是20世紀(jì)90年代中期由美國(guó)微軟公司推出的一個(gè)強(qiáng)大的Windows應(yīng)用程序開(kāi)發(fā)平臺(tái)，是“真正的程序員”首選的開(kāi)發(fā)工具之一，也是有志于程序設(shè)計(jì)的程序員、大中專(zhuān)院校學(xué)生進(jìn)入高級(jí)程序設(shè)計(jì)領(lǐng)域的首

16、選軟件之一。</p><p>　　Microsoft Visual C++ 6.0程序開(kāi)發(fā)軟件提供了一個(gè)可視化集成編程環(huán)境，能自動(dòng)生成Windows應(yīng)用程序的共有部分，幫助程序設(shè)計(jì)人員直接切入實(shí)際功能部分的代碼編制主題，從而大大簡(jiǎn)化了復(fù)雜的Windows應(yīng)用程序開(kāi)發(fā)過(guò)程，極大的提高了程序設(shè)計(jì)的效率，其次， VC++功能強(qiáng)大，內(nèi)容浩瀚在該環(huán)境下用戶可以開(kāi)發(fā)有關(guān)C和C++的各種應(yīng)用程序，應(yīng)用程序的開(kāi)發(fā)包括建立、編輯、

17、瀏覽、鏈接和調(diào)試等操作。</p><p><b>　　第二章概要設(shè)計(jì)</b></p><p><b>　　2.1 數(shù)據(jù)結(jié)構(gòu)</b></p><p>　　樹(shù)狀顯示二叉樹(shù)是二叉樹(shù)的一種自然顯示方法，本設(shè)計(jì)結(jié)果將二叉樹(shù)形象的顯示在屏幕上，直觀易懂。因此本設(shè)計(jì)將對(duì)樹(shù)狀顯示二叉樹(shù)的設(shè)計(jì)步驟進(jìn)行詳細(xì)說(shuō)明。</p>&

18、lt;p>　　首先得構(gòu)造一個(gè)數(shù)組來(lái)存儲(chǔ)整個(gè)二叉樹(shù)的結(jié)點(diǎn)信息，建立兩個(gè)隊(duì)列Q和QI，隊(duì)列Q中存放節(jié)點(diǎn)信息，隊(duì)列QI中存相應(yīng)于隊(duì)列Q中的節(jié)點(diǎn)的位置信息，包括層號(hào)和需要打印節(jié)點(diǎn)值時(shí)需要打印的空格數(shù)。當(dāng)節(jié)點(diǎn)被加入到Q時(shí)，相應(yīng)的打印信息被存到QI中。然后通過(guò)插入排序算法來(lái)構(gòu)造一個(gè)二叉樹(shù)，并用二叉樹(shù)的層次遍歷來(lái)使二叉樹(shù)有順序的存入隊(duì)列Q，最后通過(guò)隊(duì)列QI使得二叉樹(shù)樹(shù)狀的顯示在屏幕上。</p><p>　　該程序的主要流

19、程圖如圖2-1所示。</p><p>　　2.2 所用方法及其原理說(shuō)明</p><p>　　本設(shè)計(jì)主要運(yùn)用了樹(shù)的廣度優(yōu)先搜索和隊(duì)列的先進(jìn)先出的特點(diǎn)，樹(shù)的廣度優(yōu)先搜索功能如下：</p><p>　　假設(shè)從圖中某頂點(diǎn)v出發(fā)，在訪問(wèn)了v的各個(gè)未曾訪問(wèn)過(guò)的鄰接點(diǎn)，然后分別從這些鄰接點(diǎn)出發(fā)依次訪問(wèn)它們的鄰接點(diǎn)，并使“先被訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)”先于“后被訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)”被訪問(wèn)

20、，直至圖中所有已被訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)都被訪問(wèn)到。若此時(shí)圖中尚有頂點(diǎn)未被訪問(wèn)，則另選圖中一個(gè)未曾被訪問(wèn)的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪問(wèn)到為止。</p><p>　　隊(duì)列是一種先進(jìn)先出的線性表，它只允許在表的一端進(jìn)行插入，而在另一端刪除元素。在隊(duì)列中允許插入的一端叫隊(duì)尾，允許刪除的一端叫對(duì)頭。隊(duì)列的示意圖如下：</p><p>　　圖1 二叉樹(shù)示意圖</p>

21、<p><b>　　第三章 詳細(xì)設(shè)計(jì)</b></p><p>　　3.1 詳細(xì)設(shè)計(jì)方案</p><p>　　本設(shè)計(jì)利用兩個(gè)隊(duì)列Q，QI，隊(duì)列Q中存放結(jié)點(diǎn)信息，隊(duì)列QI中存相應(yīng)于隊(duì)列Q中的節(jié)點(diǎn)的位置信息，包括層號(hào)和需要打印節(jié)點(diǎn)值時(shí)需要打印的空格數(shù)。當(dāng)節(jié)點(diǎn)被加入到Q時(shí)，相應(yīng)的打印信息被存到QI中。用二叉樹(shù)（二叉樹(shù)本身采用二叉鏈表存儲(chǔ)）的層次遍歷算法實(shí)現(xiàn)了二叉

22、樹(shù)的樹(shù)狀顯示。本設(shè)計(jì)應(yīng)用了C語(yǔ)言中的類(lèi)來(lái)自定義頭文件，將任務(wù)分成多個(gè)的模塊，增強(qiáng)了可讀性和簡(jiǎn)單性，同時(shí)為日后的編寫(xiě)，調(diào)試，維護(hù)提供了極大地方便。</p><p><b>　　3.2 模塊設(shè)計(jì)</b></p><p>　　本程序包括三部分，即二叉樹(shù)定義部分（MyHeap.h），樹(shù)狀顯示二叉樹(shù)的實(shí)現(xiàn)（MyHeap.cpp）部分以及最重要的主函數(shù)部分(main.cpp)。下

23、面將對(duì)各模塊設(shè)計(jì)思想及設(shè)計(jì)方法進(jìn)行詳細(xì)的說(shuō)明。</p><p>　　3.21 二叉樹(shù)定義</p><p>　　需要顯示的二叉樹(shù)的示意圖如下：</p><p><b>　　圖2 樹(shù)狀二叉樹(shù)</b></p><p>　　#include <stdio.h></p><p>　　#incl

24、ude <stdlib.h></p><p>　　#include <malloc.h></p><p>　　#define TElemType char</p><p>　　#define OK 1</p><p>　　#define ERROR 0</p><p>　　#define

25、OVERFLOW -2</p><p>　　#define TRUE 1</p><p>　　#define FALSE 0</p><p>　　typedef int Status ; </p><p>　　#define MAXQSIZE 100 </p><p>　　typedef struct BiNo

26、de</p><p><b>　　{</b></p><p>　　int data;</p><p>　　struct BiNode *lchild;</p><p>　　struct BiNode *rchild;</p><p>　　}BiNode, *BiTree;</p>

27、<p>　　typedef int ElemType;</p><p>　　typedef struct</p><p><b>　　{ </b></p><p>　　ElemType *base; /*數(shù)組首地址*/</p><p>　　int front; /*頭指針,若隊(duì)列不空，指向隊(duì)列頭元素

28、*/</p><p>　　int rear; /*尾指針,若隊(duì)列不空，指向隊(duì)列尾元素的下一個(gè)位置*/</p><p><b>　　}SqQueue;</b></p><p>　　typedef struct </p><p><b>　　{</b></p><p>

29、　　int level;</p><p><b>　　int pos;</b></p><p>　　bool enter;</p><p>　　int spaceNum;</p><p>　　}DisplayInfo;</p><p>　　Status insert(BiTree bt,int k

30、ey)</p><p><b>　　{</b></p><p>　　BiTree p,q,newNode;</p><p>　　newNode=(BiTree)malloc(sizeof(BiNode));</p><p><b>　　p=NULL;</b></p><p>

31、<b>　　q=bt;</b></p><p><b>　　while(q)</b></p><p><b>　　{</b></p><p><b>　　p=q;</b></p><p>　　if(key<q->data)</p>

32、<p>　　q=q->lchild;</p><p><b>　　else </b></p><p>　　q=q->rchild;</p><p><b>　　}</b></p><p><b>　　if(p)</b></p><p&

33、gt;<b>　　{</b></p><p>　　if(key<p->data)</p><p>　　p->lchild=newNode;</p><p><b>　　else</b></p><p>　　p->rchild=newNode;</p><p

34、><b>　　}</b></p><p><b>　　else</b></p><p>　　bt=newNode;</p><p><b>　　}</b></p><p>　　Status InitQueue(SqQueue *Q)</p><p>

35、;<b>　　{ </b></p><p>　　Q->base=(ElemType *)malloc(MAXQSIZE*sizeof(ElemType));</p><p>　　if (!Q->base)</p><p><b>　　{</b></p><p>　　printf(&quo

36、t;分配空間失敗!");</p><p>　　return OVERFLOW;</p><p><b>　　}</b></p><p>　　Q->front=0;</p><p>　　Q->rear=0;</p><p>　　return OK;</p><

37、;p><b>　　}</b></p><p>　　EnQueue(SqQueue *Q, ElemType e)</p><p><b>　　{</b></p><p>　　/* 插入元素e為新的隊(duì)尾元素 */</p><p>　　if ( (Q->rear+1)%MAXQSIZE==Q

38、->front )</p><p><b>　　{</b></p><p>　　printf("隊(duì)列滿了!");</p><p>　　return ERROR;</p><p><b>　　} </b></p><p>　　Q->base[

39、Q->rear]=e;</p><p>　　Q->rear=(Q->rear+1)%MAXQSIZE;</p><p><b>　　}</b></p><p>　　DeQueue(SqQueue *Q, ElemType *e)</p><p><b>　　{</b></p&

40、gt;<p>　　/* 刪除隊(duì)頭元素，并由e返回其值 */</p><p>　　if (Q->front==Q->rear) return ERROR;</p><p>　　*e=Q->base[Q->front];</p><p>　　Q->front=(Q->front+1)%MAXQSIZE;</p&g

41、t;<p><b>　　}</b></p><p>　　Status IsEmpty(SqQueue *Q)</p><p><b>　　{</b></p><p>　　if (Q->front==Q->rear) return OK;</p><p>　　else ret

42、urn ERROR;</p><p><b>　　} </b></p><p>　　BiTree CreateBiTree(BiTree bt)</p><p><b>　　{</b></p><p><b>　　char ch;</b></p><p>

43、;　　scanf("%c",&ch);</p><p>　　if(ch=='.') bt=NULL;</p><p><b>　　else </b></p><p><b>　　{</b></p><p>　　bt=(BiTree)malloc(sizeo

44、f(BiNode)); /* 生成根結(jié)點(diǎn) */</p><p>　　bt->data=ch;</p><p>　　bt->lchild=CreateBiTree(bt->lchild); /* 生成左子樹(shù) */</p><p>　　bt->rchild=CreateBiTree(bt->rchild); /* 生成右子樹(shù) */</

45、p><p><b>　　}</b></p><p>　　return bt;</p><p><b>　　}</b></p><p><b>　　程序功能說(shuō)明：</b></p><p>　　該段程序分別用三個(gè)結(jié)構(gòu)體定義了二叉樹(shù)、隊(duì)列和樹(shù)的顯示信息，還包含&l

46、t;/p><p>　　該程序需要用到C語(yǔ)言頭文件、數(shù)據(jù)定義和二叉樹(shù)的建立、隊(duì)列的插入與刪除等函數(shù)，是整個(gè)程序的基礎(chǔ)。</p><p>　　3.22 樹(shù)狀顯示二叉樹(shù)設(shè)計(jì)</p><p>　　主要運(yùn)用樹(shù)的廣度優(yōu)先搜索，樹(shù)的廣度優(yōu)先搜索功能如下：</p><p>　　假設(shè)從圖中某頂點(diǎn)v出發(fā)，在訪問(wèn)了v的各個(gè)未曾訪問(wèn)過(guò)的鄰接點(diǎn)，然后分別從這些鄰接點(diǎn)出發(fā)依

47、次訪問(wèn)它們的鄰接點(diǎn)，并使“先被訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)”先于“后被訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)”被訪問(wèn)，直至圖中所有已被訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)都被訪問(wèn)到。若此時(shí)圖中尚有頂點(diǎn)未被訪問(wèn)，則另選圖中一個(gè)未曾被訪問(wèn)的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪問(wèn)到為止。廣度優(yōu)先搜索的過(guò)程如下：</p><p>　　圖 3 廣度優(yōu)先搜索二叉樹(shù)</p><p>　

48、　void BFSDisplayTree(BiTree bt)</p><p><b>　　{</b></p><p>　　SqQueue Q;</p><p>　　BiTree curNode;</p><p>　　printf("BFS Display Tree:\n");</p>

49、<p>　　EnQueue(&Q,curNode); </p><p>　　while(!IsEmpty(&Q))</p><p><b>　　{</b></p><p>　　DeQueue(&Q,&curNode);</p><p>　　*curNode=Q.front;<

50、;/p><p>　　if(curNode->lchild)</p><p>　　EnQueue(&Q, curNode->lchild);</p><p>　　if(curNode->rchild)</p><p>　　EnQueue(&Q, curNode->rchild);</p><

51、;p>　　printf("%d ",curNode->data);</p><p><b>　　}</b></p><p>　　printf("\n");</p><p><b>　　}</b></p><p>　　void NatureDisp

52、layTree(BiTree bt)</p><p><b>　　{</b></p><p><b>　　int i;</b></p><p>　　SqQueue Q;</p><p>　　SqQueue QI;</p><p>　　int screenWidth=64;&l

53、t;/p><p>　　int dataWidth=2;</p><p>　　DisplayInfo info;</p><p>　　DisplayInfo preInfo;</p><p>　　BiTree curNode;</p><p>　　DisplayInfo curInfo;</p><p&g

54、t;<b>　　if(!bt)</b></p><p><b>　　{</b></p><p>　　printf("Tree is empty !\n");</p><p><b>　　return;</b></p><p><b>　　}<

55、/b></p><p>　　printf("Nature Display Tree:\n");</p><p>　　EnQueue(&Q, bt); /* 若二叉樹(shù)bt非空，則根結(jié)點(diǎn)bt入隊(duì)，開(kāi)始層次遍歷 info.level=1;</p><p>　　info.enter=true;</p><p>

56、　　info.spaceNum=screenWidth>>info.level;</p><p>　　info.pos=info.spaceNum;</p><p>　　EnQueue(&QI,info);</p><p>　　preInfo=info;</p><p>　　while(!IsEmpty(&Q))&

57、lt;/p><p><b>　　{</b></p><p>　　curNode=Q.front;</p><p>　　DeQueue(&Q,&e);</p><p>　　curNode=QI.front;</p><p>　　if(!curInfo.enter) </p>

58、<p>　　printf("\n\n");</p><p>　　for (i=0;i<curInfo.spaceNum;i++)</p><p>　　printf(" ");</p><p>　　printf("%2d",curNode->data);</p><

59、p>　　DeQueue(&QI,&curNode);</p><p>　　if(!curNode->lchild)</p><p><b>　　{</b></p><p>　　EnQueue(&Q, curNode->lchild);</p><p>　　Info.level=c

60、urInfo.level+1;</p><p>　　Info.pos=curInfo.pos-(screenWidth>>Info.level);</p><p>　　if(Info.level>preInfo.level)</p><p><b>　　{</b></p><p>　　Info.ente

61、r=true;</p><p>　　Info.spaceNum=Info.pos;</p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　Info.enter=f

62、alse;</p><p>　　Info.spaceNum=Info.pos-preInfo.pos;</p><p><b>　　}</b></p><p>　　Info.spaceNum-=dataWidth;</p><p>　　EnQueue(&QI, Info);</p><p>

63、;　　preInfo=Info;</p><p><b>　　}</b></p><p>　　if(!curNode->rchild)</p><p><b>　　{</b></p><p>　　EnQueue(&Q, curNode->rchild);</p>&

64、lt;p>　　info.level=curInfo.level+1;</p><p>　　Info.pos=curInfo.pos+(screenWidth>>info.level);</p><p>　　if(info.level>preinfo.level)</p><p><b>　　{</b></p>

65、<p>　　info.enter=true;</p><p>　　info.spaceNum=info.pos;</p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p>&

66、lt;p>　　info.enter=false;</p><p>　　info.spaceNum=info.pos-preInfo.pos;</p><p><b>　　}</b></p><p>　　info.spaceNum-=dataWidth;</p><p>　　EnQueue(&QI, info

67、);</p><p>　　preinfo=info;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　printf("\n");</p><p><b>　　}</b></p&

68、gt;<p>　　void Display(int *A,int n)</p><p><b>　　{</b></p><p><b>　　int i;</b></p><p>　　printf("Array Info:\n");</p><p>　　for (i=

69、0;i<n;i++)</p><p><b>　　{</b></p><p>　　printf("%d\t",A[i]);</p><p><b>　　}</b></p><p>　　printf("\n");</p><p>&

70、lt;b>　　}</b></p><p><b>　　程序功能說(shuō)明：</b></p><p>　　程序先用廣度優(yōu)先搜索遍歷二叉樹(shù)（類(lèi)似于二叉樹(shù)的按層次遍歷），使二叉樹(shù)的各結(jié)點(diǎn)依次進(jìn)入隊(duì)列Q，然后定義了另一個(gè)隊(duì)列QI，它和隊(duì)列Q形成一一對(duì)應(yīng)關(guān)系，其中存放Q中結(jié)點(diǎn)的打印信息，每次從Q中取出一個(gè)節(jié)點(diǎn)curNode, 對(duì)應(yīng)的打印信息為curInfo，當(dāng)結(jié)點(diǎn)的

71、輸出位置用層號(hào)level（需打印的空格數(shù)）來(lái)界定，當(dāng)level和….不同時(shí)，換行，通過(guò)Q與QI的結(jié)合，最后使二叉樹(shù)樹(shù)狀的顯示在屏幕上。</p><p>　　3.22 主函數(shù)設(shè)計(jì)</p><p>　　主函數(shù)是一個(gè)程序最重要的部分，本程序也不例外。</p><p>　　void main()</p><p><b>　　{</b&

72、gt;</p><p>　　BiTree bt,t;</p><p><b>　　int i;</b></p><p>　　int data[9]={5,4,2,7,1,9,3,0,6};</p><p>　　Display(data,9); //打印數(shù)組</p><p>　　for (i=0

73、;i<9;i++)</p><p>　　insert(bt,data[i]);</p><p>　　bt=CreateBiTree(bt); </p><p>　　BFSDisplayTree(bt); //廣度優(yōu)先打印二叉樹(shù)</p><p>　　NatureDisplayTree(bt); //自然顯示打印二叉樹(shù)&

74、lt;/p><p><b>　　}</b></p><p><b>　　程序功能說(shuō)明：</b></p><p>　　該主函數(shù)首先定義了存儲(chǔ)二叉樹(shù)結(jié)點(diǎn)的數(shù)組，并將數(shù)組打印出來(lái)，然后定義了一個(gè)二叉樹(shù)對(duì)象myBST，調(diào)用函數(shù)insert(data[i])將數(shù)組中的樹(shù)依次插入到二叉樹(shù)中，最后用隊(duì)列Q和QI實(shí)現(xiàn)了二叉樹(shù)的廣度優(yōu)先搜索，把

75、二叉樹(shù)以樹(shù)狀的形式顯示到屏幕上。</p><p>　　第四章 調(diào)試和操作說(shuō)明</p><p><b>　　4.1 調(diào)試</b></p><p>　　1．在課程設(shè)計(jì)的過(guò)程中，寫(xiě)代碼是一個(gè)方面，程序的調(diào)試才是最重要的，它是一個(gè)相當(dāng)繁瑣的過(guò)程，有許多新的問(wèn)題需要被解決；但是同時(shí)它也是一個(gè)比較重要的過(guò)程，因?yàn)樵诔绦蛘{(diào)試的過(guò)程中你可以學(xué)到很多新的知識(shí)，

76、從而增加你編程的經(jīng)驗(yàn)。</p><p>　　在程序中有下面的代碼：if(np->key==1)，剛開(kāi)始做的時(shí)候，寫(xiě)成了if (np->key = 1)，錯(cuò)誤不太容易發(fā)現(xiàn)，主要是混淆了判斷語(yǔ)句與賦值語(yǔ)句的區(qū)別。查到一個(gè)小小的建議，變量和常量比較時(shí)，把常量放在 = = 號(hào)的左邊，這樣如果你錯(cuò)寫(xiě)為 = 時(shí)，編譯器就會(huì)報(bào)出禁止為常量賦值的錯(cuò)。因此，好的編程習(xí)慣的很重要。</p><p>

77、;　　2、程序編寫(xiě)好后將程序在VC++環(huán)境中經(jīng)過(guò)編譯確認(rèn)無(wú)誤后調(diào)試并運(yùn)行，得運(yùn)行結(jié)果如下圖。</p><p><b>　　圖4 運(yùn)行結(jié)果1</b></p><p><b>　　4.2 操作說(shuō)明</b></p><p>　　程序還提供二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)及結(jié)點(diǎn)值的修改，若想修改結(jié)點(diǎn)的個(gè)數(shù)和結(jié)點(diǎn)的值，只需找到主函數(shù)（main()

78、）中的“int data[9]={5,4,2,7,1,9,3,0,6}”語(yǔ)句，把數(shù)組個(gè)數(shù)“9”改成結(jié)點(diǎn)的個(gè)數(shù)，把數(shù)組元素改成需要的結(jié)點(diǎn)值即可。如把主函數(shù)中“int data[9]={5,4,2,7,1,9,3,0,6}”改成“int data[12]={6,8,4,3,1,7,9,5,2,10,12,15}”后的輸出結(jié)果如下：</p><p><b>　　圖5 運(yùn)行結(jié)果2</b></

79、p><p>　　第五章 總結(jié)與體會(huì)</p><p>　　5.1 本文的主要工作</p><p>　　本設(shè)計(jì)的主要難點(diǎn)在于二叉樹(shù)的層次遍歷、隊(duì)列模型的建立及隊(duì)列與隊(duì)列之間建立聯(lián)系的設(shè)計(jì)與分析，以及程序的編譯與運(yùn)行。</p><p><b>　　5.2 存在問(wèn)題</b></p><p>　　雖然經(jīng)過(guò)努力

80、，最終完成了樹(shù)狀顯示二叉樹(shù)的設(shè)計(jì)，但是我覺(jué)得在設(shè)計(jì)過(guò)程中還存在很多不足，例如：對(duì)一些C語(yǔ)言的編程思路不清楚，對(duì)實(shí)驗(yàn)軟件運(yùn)行步驟方法不熟悉，使得我在設(shè)計(jì)過(guò)程中遇到很多困難。</p><p><b>　　5.3 心得體會(huì)</b></p><p>　　緊張的兩周數(shù)據(jù)結(jié)構(gòu)實(shí)訓(xùn)很快過(guò)去了，通過(guò)這周的學(xué)習(xí)使我鞏固了以前的知識(shí)并在此基礎(chǔ)上對(duì)數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)和算法有了更深的了解， 數(shù)據(jù)

81、結(jié)構(gòu)是計(jì)算機(jī)程序設(shè)計(jì)的重要理論技術(shù)基礎(chǔ)，它不僅是計(jì)算機(jī)科學(xué)的核心課程，而且已經(jīng)成為其他理工專(zhuān)業(yè)的熱門(mén)選修課。從設(shè)計(jì)中我學(xué)到了很多東西，最重要的是去做好一件事的心態(tài)，拿到題目的時(shí)候也許你覺(jué)得很難，但是只要你充滿信心，一步一個(gè)腳印去實(shí)現(xiàn)它，不要怕麻煩，功夫不怕有心人，相信你一定會(huì)成功的。所以說(shuō)，坐而言不如立而言，對(duì)于這些編程設(shè)計(jì)還是應(yīng)該自己動(dòng)手實(shí)際操作才會(huì)有深刻理解。</p><p>　　首先這兩周的學(xué)習(xí)，使我在鞏固

82、了原有的理論知識(shí)上，培養(yǎng)了我靈活運(yùn)用和組合集成所學(xué)過(guò)知識(shí)及技能來(lái)分析、解決實(shí)際問(wèn)題的能力，使我體會(huì)到自身知識(shí)和能力在實(shí)際中的應(yīng)用和發(fā)揮。其次，激發(fā)了我創(chuàng)新意識(shí)，開(kāi)發(fā)創(chuàng)造的能力和培養(yǎng)溝通能力。另外，讓我進(jìn)一步熟悉了數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)應(yīng)用。每一處編碼都是在反復(fù)的熟悉數(shù)據(jù)結(jié)構(gòu)的結(jié)構(gòu)特性，及其語(yǔ)法、函數(shù)和程序設(shè)計(jì)思想的過(guò)程，對(duì)我數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)和提高很有益處，并且使我明白了程序設(shè)計(jì)過(guò)程有如解決一實(shí)際問(wèn)題，從解決實(shí)際問(wèn)題的角度，我們可以這樣來(lái)看：第一要

83、了解這個(gè)問(wèn)題的基本要求，即輸入、輸出、完成從輸入到輸出的要求是什么；第二，從問(wèn)題的要害入手，從前到后的解決問(wèn)題的每個(gè)方面，即從輸入開(kāi)始入手，著重考慮如何從輸入導(dǎo)出輸出，在這個(gè)過(guò)程中，可確定所需的數(shù)據(jù)結(jié)構(gòu)的基本類(lèi)型——線性表、棧、隊(duì)列、串、數(shù)組、廣義表、樹(shù)和二叉樹(shù)以及圖等，然后確定處理過(guò)程——算法，可得最后結(jié)論。最后，在這次實(shí)訓(xùn)過(guò)程中，我深刻的認(rèn)識(shí)到了自己在學(xué)習(xí)方面的不足之處，我知道我還有太多的基本的思想沒(méi)有真正的理解，當(dāng)然我不會(huì)灰心，我

84、會(huì)在以后的日子里努力彌補(bǔ)我的不足。</p><p>　　總之，兩個(gè)禮拜的課程設(shè)計(jì)讓我受益匪淺。要學(xué)好一門(mén)學(xué)科，沒(méi)有刻苦鉆研的精神是不行的，只有在不斷的嘗試中，不斷經(jīng)歷失敗，然后又不斷的嘗試才能獲得成功。兩個(gè)多禮拜中，我有過(guò)山窮水盡的困惑；有過(guò)柳暗花明的驚喜；有過(guò)唇槍舌劍的辯論；有過(guò)相互鼓勵(lì)的安慰。兩個(gè)禮拜的時(shí)間我經(jīng)歷了很多，也收獲了很多。與其說(shuō)它是體力與腦力的作業(yè)，不如說(shuō)它是合作精神和毅力的考驗(yàn)。經(jīng)過(guò)這次課程設(shè)計(jì)

85、，我不僅學(xué)到了很多知識(shí)和技能，更重要的是我們學(xué)會(huì)了如何運(yùn)用所學(xué)知識(shí)去解決實(shí)際問(wèn)題。</p><p><b>　　致 謝</b></p><p>　　在我們課程設(shè)計(jì)完善過(guò)程中，我也遇到了這樣或那樣的技術(shù)問(wèn)題，但經(jīng)過(guò)自己的不懈努力及查閱大量的資料，最終都得到了基本滿意的答案。同時(shí)，其他同學(xué)也給了我許多有益的啟示，促動(dòng)和幫助，使我能夠順利的完成課題。</p>

86、<p>　　感謝所有給予我?guī)椭睦蠋?，他們辛勤耕作，傳道授業(yè)，不僅使我們開(kāi)闊了視野，拓寬了思路，增長(zhǎng)了學(xué)識(shí)，而且為我們今后的工作和學(xué)習(xí)打下了牢固的基礎(chǔ)，也使增強(qiáng)我們對(duì)計(jì)算機(jī)的興趣。是老師給予我無(wú)限的創(chuàng)造力和奮斗力，使我有無(wú)限的信心和希望來(lái)完成本次的實(shí)訓(xùn)內(nèi)容。</p><p>　　同時(shí)也感謝學(xué)校給了我們這次難得的實(shí)訓(xùn)機(jī)會(huì)，實(shí)訓(xùn)的過(guò)程讓我們看到了自己理論知識(shí)上的不足，已掌握的知識(shí)也在這次的實(shí)訓(xùn)中有了質(zhì)的飛躍

87、，知識(shí)能夠應(yīng)用了才是真正掌握了，也希望學(xué)校多給我們一些這樣的機(jī)會(huì)。</p><p>　　在最后，再次感謝我們的老師，如果沒(méi)有老師的耐心指導(dǎo)，就不會(huì)有我們的成果。在我做論文期間，兩位老師淵博的學(xué)識(shí)、嚴(yán)謹(jǐn)求實(shí)的科學(xué)精神、一絲不茍的治學(xué)態(tài)度和高尚的品格，深深的感染了我。程序的每次改動(dòng)都離不開(kāi)老師的辛勤工作，從各個(gè)方面來(lái)說(shuō)，審查的工作往往比編寫(xiě)任務(wù)更復(fù)雜。正是老師百忙中不辭勞苦的幫助，才使我能夠順利完成這篇論文，在這里，

88、對(duì)您衷心的表示感謝。</p><p>　　本次實(shí)訓(xùn)中，老師對(duì)我的指導(dǎo)，我將永遠(yuǎn)感激在心，我相信這是我人生中寶貴的財(cái)富。老師，謝謝您！祝老師在今后的工作中，一帆風(fēng)順，事事順利。</p><p><b>　　參考文獻(xiàn)</b></p><p>　　[1] 佟偉光，楊政 《實(shí)用數(shù)據(jù)結(jié)構(gòu)》（第二版） 科學(xué)出版社</p><p>　

89、　[2] 嚴(yán)蔚敏 《數(shù)據(jù)結(jié)構(gòu)》（C語(yǔ)言版） 清華大學(xué)出版社</p><p>　　[3] 李保春編著，《數(shù)據(jù)結(jié)構(gòu)習(xí)題與解析》，清華大學(xué)出版 2001年第一版</p><p>　　[4] 徐孝凱編著，《數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn)》，清華大學(xué)出版 2002年第一版</p><p>　　[5] 張乃笑編著，《數(shù)據(jù)結(jié)構(gòu)與算法》，電子工業(yè)出版社 2004年10月</p>&