數(shù)據(jù)結(jié)構(gòu)課設(shè)任務(wù)書(shū)

1、課 程 設(shè) 計(jì) 報(bào) 告課程名稱數(shù)據(jù)結(jié)構(gòu) 課題名稱二叉樹(shù)遍歷演示專 業(yè)網(wǎng)絡(luò)工程 班 級(jí)網(wǎng)絡(luò)工程1102 學(xué) 號(hào) 2 姓 名 吳琪 指導(dǎo)教師淑紅 曉清杰君2013年 7 月 3 日26 / 34工程學(xué)院課 程 設(shè) 計(jì) 任 務(wù) 書(shū)課程名稱 數(shù)據(jù)結(jié)構(gòu) 課 題 二叉樹(shù)遍歷演示 專業(yè)班級(jí) 網(wǎng)絡(luò)工程 學(xué)生 吳琪 學(xué) 號(hào) 1指導(dǎo)老師淑紅 曉清 杰君審 批 任務(wù)書(shū)下達(dá)日期 2013 年 6 月 25 日任務(wù)完成日期 2013年 7 月 3 日課程設(shè)計(jì)報(bào)告任務(wù)書(shū)1、設(shè)計(jì)容與設(shè)計(jì)要求 1.1設(shè)計(jì)容1.1.1 算術(shù)24游戲演示由系統(tǒng)隨機(jī)生成4撲克牌，用戶利用撲克牌的數(shù)字與運(yùn)算符號(hào)“+”、“”、“*”、“/”與括號(hào)“（

2、”和“）”從鍵盤(pán)上輸入一個(gè)計(jì)算表達(dá)式，系統(tǒng)運(yùn)行后得出計(jì)算結(jié)果，如果結(jié)果等于24，則顯示“Congratulation!”，否則顯示“Incorrect!”設(shè)計(jì)思路：從鍵盤(pán)輸入中綴表達(dá)式，然后將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式，利用后綴表達(dá)式求值。1.1.2 迷宮探索隨機(jī)生成一個(gè)迷宮圖，迷宮大小為N*N，N預(yù)定義為常數(shù)，修改N的值可以改變迷宮的大小。用白色表示可走的路，藍(lán)色表示墻壁不可以通過(guò)。系統(tǒng)設(shè)計(jì)兩種運(yùn)行方式：一種是系統(tǒng)自動(dòng)探索（用遞歸方法實(shí)現(xiàn)）；另一種是由人工操作探索通路。設(shè)計(jì)思路：程序首先要考慮迷宮的表示，這是一個(gè)二維關(guān)系圖，所以可選擇二維數(shù)組來(lái)存儲(chǔ)。數(shù)組元素只有兩種值0和1，分別代表通路和墻

3、壁。圖形的顯示可以根據(jù)數(shù)組元素的值來(lái)確定。如果是人工探索，則依據(jù)按鍵來(lái)確定探索物的位置坐標(biāo)，利用循環(huán)語(yǔ)句實(shí)現(xiàn)。如果是系統(tǒng)自動(dòng)探索，可采用遞歸算法實(shí)現(xiàn)。1.1.3 二叉樹(shù)遍歷演示演示遍歷二叉樹(shù)的過(guò)程，所以首先建立二叉樹(shù)，并用圖形顯示出樹(shù)的形狀。建立的過(guò)程是采用前序便利的方法來(lái)創(chuàng)建，設(shè)計(jì)兩種生成樹(shù)的方式：一種是系統(tǒng)隨機(jī)生成，另一種是人工輸入?？紤]到屏幕界面的有限性，限定二叉樹(shù)不超過(guò)5層，最多26個(gè)字符，輸入字符小數(shù)點(diǎn)“.”代表NULL。初始樹(shù)為某種顏色的結(jié)點(diǎn)，三種情況的遍歷采用填充另外一種醒目的顏色，來(lái)表示當(dāng)前遍歷的結(jié)點(diǎn)，同時(shí)顯示該結(jié)點(diǎn)的訪問(wèn)序號(hào)。同時(shí)在遍歷的過(guò)程中在遍歷圖形的下方顯示出遍歷序列。

4、1.1.4 拓?fù)渑判蜓菔狙菔就負(fù)渑判虻倪^(guò)程。按照有向圖給出的次序關(guān)系，將圖中頂點(diǎn)排成一個(gè)線性序列，對(duì)于有向圖中沒(méi)有限定次序關(guān)系的頂點(diǎn)，則可以人為加上任意的次序關(guān)系。要求每輸出一個(gè)頂點(diǎn)后就演示從圖中刪去此頂點(diǎn)以與所有以它為尾的弧。1.1.5 圖的遍歷演示圖的深度優(yōu)先, 廣度優(yōu)先遍歷過(guò)程，并輸出原圖結(jié)構(gòu)與遍歷結(jié)果。要求圖的結(jié)點(diǎn)數(shù)不能少于6個(gè)?？梢杂上到y(tǒng)隨機(jī)生成圖，也可以由用戶手動(dòng)輸入圖。報(bào)告中要寫(xiě)出畫(huà)圖的思路；畫(huà)出圖的結(jié)構(gòu)，有興趣的同學(xué)可以進(jìn)一步改進(jìn)圖的效果。1.1.6 雙鏈表創(chuàng)建演示建立一個(gè)遞增有序的雙鏈表。功能是隨機(jī)生成8個(gè)結(jié)點(diǎn)數(shù)據(jù)，每生成一個(gè)結(jié)點(diǎn)則申請(qǐng)空間得到一個(gè)指針，將數(shù)據(jù)存放到指針?biāo)傅?/p>

5、數(shù)據(jù)域中，然后將結(jié)點(diǎn)插入到已經(jīng)排好序的雙鏈表中。所以第一步工作是判斷新結(jié)點(diǎn)的插入位置，第二演示插入過(guò)程中指針的變化，第三步顯示插入后的鏈表結(jié)果。1.1.7 選作課題：公園導(dǎo)游圖給出一某公園的導(dǎo)游圖，游客通過(guò)終端詢問(wèn)可知：從某一景點(diǎn)到另一景點(diǎn)的最短路徑。游客從公園大門(mén)進(jìn)入，選一條最佳路線，使游客可以不重復(fù)地游覽各景點(diǎn)，最后回到出口（出口就在入口旁邊）。要求用圖示展示最佳路徑。1.1.8 最小生成樹(shù)算法演示隨機(jī)生成一個(gè)網(wǎng)，并用圖形展示，然后依據(jù)Prim算法或Kruskal算法求該圖的最小生成樹(shù)，并用圖形展示相應(yīng)的過(guò)程步驟。1.2 選題方案：所選題目根據(jù)學(xué)號(hào)確定，學(xué)號(hào)模6加1，即（學(xué)號(hào)%6+1）。如

6、你的學(xué)號(hào)為13，則所選題目號(hào)為：13%6+1（題目2）。注意，所有的課題都要求用圖形方式演示步驟和結(jié)果。有興趣的同學(xué)可以可以選擇選做課題七或課題八，也可以自己針對(duì)數(shù)據(jù)結(jié)構(gòu)課程中所講算法來(lái)設(shè)計(jì)一個(gè)演示過(guò)程的算法，但要預(yù)先告知老師，經(jīng)過(guò)審批，方可確定課題。1.3設(shè)計(jì)要求：1.3.1 課程設(shè)計(jì)報(bào)告規(guī)（1）需求分析a. 程序的功能。b. 輸入輸出的要求。（2）概要設(shè)計(jì)a. 程序由哪些模塊組成以與模塊之間的層次結(jié)構(gòu)、各模塊的調(diào)用關(guān)系；每個(gè)模塊的功能。b. 課題涉與的數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)庫(kù)結(jié)構(gòu)；即要存儲(chǔ)什么數(shù)據(jù)，這些數(shù)據(jù)是什么樣的結(jié)構(gòu)，它們之間有什么關(guān)系等。（3）詳細(xì)設(shè)計(jì)a. 采用C語(yǔ)言定義相關(guān)的數(shù)據(jù)類(lèi)型。b.

7、 寫(xiě)出各模塊的類(lèi)C碼算法。c. 畫(huà)出各函數(shù)的調(diào)用關(guān)系圖、主要函數(shù)的流程圖。（4）調(diào)試分析以與設(shè)計(jì)體會(huì)a. 測(cè)試數(shù)據(jù)：準(zhǔn)備典型的測(cè)試數(shù)據(jù)和測(cè)試方案，包括正確的輸入與輸出結(jié)果和含有錯(cuò)誤的輸入與輸出結(jié)果。b. 程序調(diào)試中遇到的問(wèn)題以與解決問(wèn)題的方法。c. 課程設(shè)計(jì)過(guò)程經(jīng)驗(yàn)教訓(xùn)、心得體會(huì)。（5）使用說(shuō)明用戶使用手冊(cè)：說(shuō)明如何使用你編寫(xiě)的程序，詳細(xì)列出每一步的操作步驟。（6）書(shū)寫(xiě)格式a. 設(shè)計(jì)報(bào)告要求用A4紙打印成冊(cè)：b. 一級(jí)標(biāo)題用3號(hào)黑體,二級(jí)標(biāo)題用四號(hào)宋體加粗,正文用小四號(hào)宋體;行距為22。（7）附錄a. 源程序清單（帶注釋）1.3.2 考核方式指導(dǎo)老師負(fù)責(zé)驗(yàn)收程序的運(yùn)行結(jié)果，并結(jié)合學(xué)生的工作態(tài)度

8、、實(shí)際動(dòng)手能力、創(chuàng)新精神和設(shè)計(jì)報(bào)告等進(jìn)行綜合考評(píng)，并按優(yōu)秀、良好、中等、與格和不與格五個(gè)等級(jí)給出每位同學(xué)的課程設(shè)計(jì)成績(jī)。具體考核標(biāo)準(zhǔn)包含以下幾個(gè)部分：（1）平時(shí)出勤 （占10%）（2）系統(tǒng)需求分析、功能設(shè)計(jì)、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)與程序總體結(jié)構(gòu)合理與否（占10%）（3）程序能否完整、準(zhǔn)確地運(yùn)行，個(gè)人能否獨(dú)立、熟練地調(diào)試程序（占40%）（4）設(shè)計(jì)報(bào)告（占30%）注意：不得抄襲他人的報(bào)告（或給他人抄襲），一旦發(fā)現(xiàn)，成績(jī)?yōu)榱惴?。?）獨(dú)立完成情況（占10%）。1.3.3 課程驗(yàn)收要求（1）運(yùn)行所設(shè)計(jì)的系統(tǒng)。（2）回答有關(guān)問(wèn)題。（3）提交課程設(shè)計(jì)報(bào)告。（4）提交軟盤(pán)（源程序、設(shè)計(jì)報(bào)告文檔）。（5）依容的創(chuàng)新程度

9、，完善程序情況與對(duì)程序講解情況打分。2 、進(jìn)度安排第 18 周：星期二14：3016：30 上課 星期二 18：0022：00 上機(jī)星期三 18：0022：00 上機(jī) 星期四 18：0022：00 上機(jī)第 19 周：星期一 14：0018：00 上機(jī) 星期二 14：0018：00 上機(jī) 星期三8：0012：00 上機(jī) 附：課程設(shè)計(jì)報(bào)告裝訂順序：封面、任務(wù)書(shū)、目錄、正文、評(píng)分、附件（A4大小的圖紙與程序清單）。 正文的格式:一級(jí)標(biāo)題用3號(hào)黑體,二級(jí)標(biāo)題用四號(hào)宋體加粗, 三級(jí)標(biāo)題用小四號(hào)宋體加粗，正文用小四號(hào)宋體;行距為22。正文的容:一、課題的主要功能；二、課題的功能模塊的劃分（要求畫(huà)出模塊圖）

10、；三、主要功能的實(shí)現(xiàn)（至少要有一個(gè)主要模塊的流程圖）；四、程序調(diào)試；五、總結(jié)；六、附件（所有程序的原代碼，要求對(duì)程序?qū)懗霰匾淖⑨專?。正文總字?jǐn)?shù)要求在5000字以上（不含程序原代碼）目錄一、需求分析：11.1功能需求：11.2輸入輸出的要求：11.2.2輸出：1二、概要設(shè)計(jì)：12.1數(shù)據(jù)結(jié)構(gòu)：12.2抽象數(shù)據(jù)類(lèi)型：22.3功能模塊圖：33.1流程圖43.1.1創(chuàng)建二叉樹(shù)：43.1.2先序遍歷：53.1.4中序遍歷：73.2.1創(chuàng)建二叉樹(shù)：73.2.2先序遍歷二叉樹(shù)：83.2.3中序遍歷二叉樹(shù)：83.2.4后序遍歷二叉樹(shù)：83.2.5人工輸入二叉樹(shù)：83.2.6隨機(jī)生成二叉樹(shù)：9四、調(diào)試與測(cè)試：

11、104.2.1程序調(diào)試與分析：104.2.2測(cè)試結(jié)果與分析：11五、心得體會(huì)：14六、參考文獻(xiàn)：15七、附錄：15課程設(shè)計(jì)報(bào)告一、需求分析：1.1功能需求：演示遍歷二叉樹(shù)的過(guò)程，所以首先建立二叉樹(shù)，并用圖形顯示出樹(shù)的形狀。建立的過(guò)程是采用前序便利的方法來(lái)創(chuàng)建，設(shè)計(jì)兩種生成樹(shù)的方式：一種是系統(tǒng)隨機(jī)生成，另一種是人工輸入?？紤]到屏幕界面的有限性，限定二叉樹(shù)不超過(guò)5層，最多26個(gè)字符，輸入字符小數(shù)點(diǎn)“.”代表NULL。初始樹(shù)為某種顏色的結(jié)點(diǎn)，三種情況的遍歷采用填充另外一種醒目的顏色，來(lái)表示當(dāng)前遍歷的結(jié)點(diǎn)，同時(shí)顯示該結(jié)點(diǎn)的訪問(wèn)序號(hào)。同時(shí)在遍歷的過(guò)程中在遍歷圖形的下方顯示出遍歷序列。1.2輸入輸出的要求

12、：1.2.1輸入：（1）人工輸入二叉樹(shù)的序列； （2）隨機(jī)產(chǎn)生二叉樹(shù)的序列。1.2.2輸出：用圖形的方式演示二叉樹(shù)的三種遍歷：先序遍歷、中序遍歷、后序遍歷。二、概要設(shè)計(jì)：2.1數(shù)據(jù)結(jié)構(gòu)：typedef struct nodechar data;struct node*lchild;struct node*rchild;int x;int y;int num;BTNode;2.2抽象數(shù)據(jù)類(lèi)型：數(shù)據(jù)對(duì)象D：D是具有一樣特性的數(shù)據(jù)元素的集合。各個(gè)數(shù)據(jù)元素均含有類(lèi)型一樣，可惟一標(biāo)識(shí)數(shù)據(jù)元素的關(guān)鍵字。 數(shù)據(jù)關(guān)系R：數(shù)據(jù)元素同屬一個(gè)集合。 基本操作P： node*createBTNode(BTNode*&

13、amp;t,char*str) 操作結(jié)果：先序遍歷創(chuàng)建二叉樹(shù)。 PreOrder(BTNode*t,int m,int v) 初始條件：二叉樹(shù)存在； 操作結(jié)果：先序遍歷二叉樹(shù)。 inOrder(BTNode*t,int m,int v) 初始條件：二叉樹(shù)存在； 操作結(jié)果：中序遍歷二叉樹(shù)。 postOrder(BTNode*t,int w,int v) 初始條件：二叉樹(shù)存在； 操作結(jié)果：后序遍歷二叉樹(shù)。 node*DrawOriginTree(BTNode*t,char*str,int x,int y) 初始條件：二叉樹(shù)存在； 操作結(jié)果：將二叉樹(shù)用圖形表示出來(lái)。 rgcreate() 操作結(jié)果：

14、人工輸入二叉樹(shù)序列。 sjcreate() 操作結(jié)果：隨機(jī)生成二叉樹(shù)序列。2.3功能模塊圖：用戶在主界面中選擇出輸入模塊，繼續(xù)執(zhí)行小界面中的其他模塊。2.3.1系統(tǒng)總模塊： 主界面 1、人工輸入 2、隨機(jī)生成 3、退出 用戶提示界面3、后序遍歷2、中序遍歷1、先序遍歷2.3.2模塊功能說(shuō)明：主界面：main() 用戶選擇界面 人工輸入模塊： rgcreate() 用戶手動(dòng)輸入二叉樹(shù)序列 隨機(jī)生成模塊： sjcreate() 系統(tǒng)隨機(jī)產(chǎn)生二叉樹(shù)序列 先序遍歷模塊： PreOrder(） 系統(tǒng)界面用圖的形式將二叉樹(shù)的先 序遍歷顯示出來(lái) 中序遍歷模塊： inOrder() 系統(tǒng)界面用圖的形式將二叉樹(shù)

15、的中序遍歷顯示出來(lái) 后序遍歷模塊： postOrder() 系統(tǒng)界面用圖的形式將二叉樹(shù)的后序遍歷顯示出來(lái) 退出模塊： exit（0） 退出程序三、詳細(xì)設(shè)計(jì)：3.1流程圖3.1.1創(chuàng)建二叉樹(shù)： 開(kāi)始int top=-1,k,j=0;charch;t=NULL;ch=*str; ch!='0'No Yesdefault:p=(BTNode*)malloc(sizeof(BTNode);p->lchild=p->rchild=NULL;p->data=chcase ',': k=2;case ')': top-;case(':

16、top+;sttop=p;k=1; t=NULL Yes t=p; Nocase2:sttop->rchild=p;case1:sttop->lchild=p; str+;ch=*str; return t; 結(jié)束3.1.2先序遍歷： 開(kāi)始int i=0,x=90,x1,x2,y1,y2; char ch;int top=-1,c,w,d; t!=NULL No Yes top+; sttop=t; top>-1 No Yes p=sttop;top-;ch=p->data;i+;p->rchild!=NULL top+; sttop=p->rchild;p

17、->lchild!=NULL top+;sttop=p->lchild; 結(jié)束3.1.3后序遍歷： 開(kāi)始int flag,top=-1;char ch; t!=NULLNotop+;sttop=t;Yest->lchild!=NULL t=t->lchild; No Yesp=NULL；flag=1;top!=-1 && flagNot=sttop;t->rchild=pYesNoch=t->data;i+;top-;p=t;t->rchild!=NULLt=t->rchild;flag=0; top!=-1Yes 結(jié)束3.1.4

18、中序遍歷： int top=-1; 開(kāi)始 b!=NULL? No top>-1top>-1|p!=NULL Yes p=sttop;top-;p=p->rchild;printf("%c",p->data);p=p->rchild;printf("%c",p->data);p=p->rchild;top+;sttop=p;p=p->lchild; 結(jié)束3.2設(shè)計(jì)思路：3.2.1創(chuàng)建二叉樹(shù)：（1)創(chuàng)建二叉樹(shù)的部分，用ch掃描str，有四種字符：1、ch='(':表示前面剛創(chuàng)建的節(jié)點(diǎn)*p存在孩子

19、節(jié)點(diǎn)，需要將其進(jìn)棧，以便建立它和其孩子節(jié)點(diǎn)的關(guān)系，然后開(kāi)始處理左孩子，k=1，其后創(chuàng)建的節(jié)點(diǎn)作為它的左孩子節(jié)點(diǎn)。2、ch=')':表示創(chuàng)建完畢，將其退棧。3、ch=',':開(kāi)始處理?xiàng)ｍ敼?jié)點(diǎn)的右孩子結(jié)點(diǎn)。3.2.2先序遍歷二叉樹(shù)：(1)先序遍歷過(guò)程是先訪問(wèn)根節(jié)點(diǎn)，在訪問(wèn)左子樹(shù)，最后才是右子樹(shù)。因此，先將根節(jié)點(diǎn)進(jìn)棧，在棧不空的情況下循環(huán)：出棧p,訪問(wèn)*p節(jié)點(diǎn)，若其右孩子結(jié)點(diǎn)不空將右孩子節(jié)點(diǎn)進(jìn)棧，若其左孩子節(jié)點(diǎn)不空再將其左孩子節(jié)點(diǎn)進(jìn)棧。3.2.3中序遍歷二叉樹(shù)： （1）中序遍歷過(guò)程是先訪問(wèn)二叉樹(shù)的最左下方節(jié)點(diǎn)，其基本思路是先找到二叉樹(shù)的開(kāi)始節(jié)點(diǎn)，將其訪問(wèn)，再處理其右子

20、樹(shù)。用指針指向當(dāng)前要處理的節(jié)點(diǎn)。先掃描根節(jié)點(diǎn)的所有左節(jié)點(diǎn)，并將它們一一進(jìn)棧，當(dāng)無(wú)左節(jié)點(diǎn)時(shí)表示棧頂節(jié)點(diǎn)無(wú)左子樹(shù)，然后出棧這個(gè)節(jié)點(diǎn)，并訪問(wèn)，將p指向剛出棧節(jié)點(diǎn)的右孩子，對(duì)右子樹(shù)進(jìn)行同樣的處理。如此重復(fù)操作，直到?？諡橹?。3.2.4后序遍歷二叉樹(shù)： （1）后序遍歷過(guò)程是先訪問(wèn)左子樹(shù)，然后訪問(wèn)右子樹(shù)，最后訪問(wèn)根節(jié)點(diǎn)。采用一個(gè)棧保存需要返回的節(jié)點(diǎn)指針，先掃描根節(jié)點(diǎn)的所有左孩子節(jié)點(diǎn)并一一進(jìn)棧，出棧一個(gè)節(jié)點(diǎn)*t作為當(dāng)前節(jié)點(diǎn),然后掃描該節(jié)點(diǎn)的右子樹(shù)。當(dāng)一個(gè)節(jié)點(diǎn)的左右子樹(shù)節(jié)點(diǎn)均訪問(wèn)后再訪問(wèn)該節(jié)點(diǎn)，如此重復(fù)操作，直到棧空為止。3.2.5人工輸入二叉樹(shù)： (1)算法演示：void rgcreate()char s1

21、00;char*str,tmp='y',ti100; InputBox(ti,100 ,"請(qǐng)輸入節(jié)點(diǎn)表達(dá)式");sscanf(ti,"%s",&s);str=s;BTNode *h,*t;h=createBTNode(h,str);initgraph(950,800);setcolor(RED);setbkcolor(BLACK);cleardevice();t=DrawOriginTree(h,str,500,120);menu(h); InputBox(ti,100 ,"繼續(xù)嗎？繼續(xù)輸入Y或y");ssca

22、nf(ti,"%c",&tmp);if(tmp='Y'|tmp='y') rgcreate();else if (tmp='n'|tmp='N')close();3.2.6隨機(jī)生成二叉樹(shù)：(1)算法演示：void sjcreate()int tem10;char a,b,c,d,e,f,g,h,i,j,I;char si100,tmp='y',ti100;char*str;BTNode*k,*t; srand(unsigned)time(NULL);for(I=0;I<10;I+)

23、temI=(rand()%26+65);a=tem0; b=tem1; c=tem2; d=tem3; e=tem4; f=tem5; g=tem6; h=tem7;i=tem8;j=tem9 ; si0=a;si1='('si2=b;si3='('si4=d;si5='('si6=j;si7=','si8=h; si9=')'si10=','si11=e;si12='('si13=i;si14=','si15=')'si16=')'

24、si17=','si18=c;si19='('si20=f;si21=','si22=g;si23=')'si24=')'str=si;k=createBTNode(k,str);initgraph(950,800);setcolor(RED);setbkcolor(BLACK);cleardevice();t=DrawOriginTree(k,str,500,120);menu(k); InputBox(ti,100 ,"繼續(xù)嗎？繼續(xù)輸入Y或y");sscanf(ti,"%c&quo

25、t;,&tmp);if(tmp='Y'|tmp='y') sjcreate();else if (tmp='n'|tmp='N')close();四、調(diào)試與測(cè)試：4.1測(cè)試數(shù)據(jù)：(1)人工輸入1-26個(gè)字母建立的二叉樹(shù)。(2)隨機(jī)生成1-26個(gè)字母建立的二叉樹(shù)。4.2調(diào)試結(jié)果與分析：4.2.1程序調(diào)試與分析： 開(kāi)始調(diào)試程序時(shí)，遇到的問(wèn)題主要是不會(huì)用程序語(yǔ)言清楚的表達(dá)出自己的意思，而且思路也不是特別的清晰，雖然能了解二叉樹(shù)的一些基本算法，但是對(duì)這些基本算法的圖形的表示卻不是很了解，所以導(dǎo)致編寫(xiě)的程序總是不能達(dá)到預(yù)期的效果，就

26、比如說(shuō)在中序遍歷二叉樹(shù)的序列演示時(shí)，所顯示的界面位置就不是很準(zhǔn)確，在源代碼的中序遍歷模塊過(guò)調(diào)整其坐標(biāo)將界面位置改了過(guò)來(lái)，而且最初在圖形演示二叉樹(shù)的遍歷時(shí)，每進(jìn)行完一次訪問(wèn)，程序會(huì)自動(dòng)退出，因此程序的遍歷的演示就不連貫，而且也不方便。于是，我就在人工輸入和隨機(jī)生成模塊里設(shè)立了一個(gè)“繼續(xù)/返回”提示，當(dāng)輸入“y”時(shí)，繼續(xù)二叉樹(shù)的遍歷，當(dāng)輸入“n”時(shí)，返回到主界面。雖然程序不是特別的完美，并且有些算法是直接從課本里弄下來(lái)的，但是通過(guò)調(diào)整解決了一些問(wèn)題，還是特別的有成就感。4.2.2測(cè)試結(jié)果與分析：首先運(yùn)行程序，進(jìn)入到主界面，如圖4.2.1所示；4.2.1 主界面根據(jù)主界面的提示，輸入序號(hào)1、人工輸入

27、，2、隨機(jī)生成，3、退出；按序號(hào)1進(jìn)入人工輸入界面，根據(jù)提示，輸入要?jiǎng)?chuàng)建的二叉樹(shù)序列，并按Enter鍵進(jìn)入圖形輸出界面，如圖4.2.2，圖4.2.3所示；4.2.2人工輸入數(shù)據(jù)界面4.2.3人工輸入圖形表示界面 根據(jù)提示，輸入序號(hào)1、先序遍歷，2、中序遍歷，3、后序遍歷；按序號(hào)1進(jìn)入人工輸入二叉樹(shù)的先序遍歷，按Enter鍵進(jìn)入界面，如圖4.2.4所示；4.2.4人工輸入的先序遍歷界面 根據(jù)提示，繼續(xù)則輸入“y”或“Y”,若退回主界面則按“N”或“n”,并按Enter鍵進(jìn)入下一界面，返回到三種遍歷提示界面，選擇序號(hào)3進(jìn)入到人工輸入的后序遍歷界面，如圖4.2.5所示； 4.2.5人工輸入的后序遍歷

28、界面根據(jù)提示，繼續(xù)則輸入“y”或“Y”,若退回主界面則按“N”或“n”,并按Enter鍵進(jìn)入下一界面，返回主界面，并選擇主界面序號(hào)2、隨機(jī)生成二叉樹(shù)界面，如圖4.2.6所示；4.2.6隨機(jī)生成二叉樹(shù)的圖形展示界面 選擇序號(hào)2按Enter鍵進(jìn)入中序遍歷二叉樹(shù)界面，如圖4.2.7所示；4.2.7隨機(jī)生成的中序遍歷界面根據(jù)提示，繼續(xù)則輸入“y”或“Y”,若退回主界面則按“N”或“n”,并按Enter鍵進(jìn)入下一界面，返回主界面，并選擇主界面序號(hào)3，退出主界面。五、心得體會(huì)：本次課程設(shè)計(jì)我做的是二叉樹(shù)遍歷演示，這次的課程設(shè)計(jì)和以往的實(shí)驗(yàn)有很大的差別，無(wú)論是easyx的使用,還是圖形的表示方法，都是我們從

29、來(lái)沒(méi)有接觸過(guò)的知識(shí)，對(duì)于C語(yǔ)言、數(shù)據(jù)結(jié)構(gòu)算法的要求就更高了，像二叉樹(shù)的三種遍歷，因?yàn)樵谡n堂上都已經(jīng)講過(guò)，所以就不是那么的陌生，在編寫(xiě)程序的時(shí)候就比較順手。但是，當(dāng)二叉樹(shù)的三種遍歷加入了圖形的演示的時(shí)候，很多地方就變得復(fù)雜，像需要設(shè)置樹(shù)節(jié)點(diǎn)的坐標(biāo)，填充樹(shù)節(jié)點(diǎn)的顏色，畫(huà)線，畫(huà)圓等等。有時(shí)候可能思路是對(duì)的，但就是無(wú)法用程序語(yǔ)言表達(dá)出來(lái)。而有的時(shí)候，甚至連思路都沒(méi)有。本次實(shí)驗(yàn)，對(duì)我來(lái)說(shuō)是一個(gè)巨大的挑戰(zhàn)，但又讓我進(jìn)一步了解了C的相關(guān)知識(shí)，甚至讓我第一次感覺(jué)到程序是個(gè)特別好玩而且神奇的東西，可能是因?yàn)槊看谓佑|到的都是相對(duì)比較死板的東西，程序表達(dá)的功能性也沒(méi)有那么的強(qiáng)，不是像這次一樣的程序的直觀演示。而本次

30、的實(shí)驗(yàn)，就比如課程設(shè)計(jì)中運(yùn)用到的隨機(jī)生成二叉樹(shù)、圖形的演示二叉樹(shù)的遍歷等等都讓我覺(jué)得特別的新鮮，讓我有想進(jìn)一步了解的欲望。而通過(guò)本次試驗(yàn)，使我更加意識(shí)到C語(yǔ)言的重要性與它強(qiáng)大的功能性，而我還需要更加努力的學(xué)習(xí)，進(jìn)一步去了解C，學(xué)習(xí)C，以與掌握C，也許將會(huì)收獲到更多意想不到的驚喜。我想，無(wú)論做什么事，只要用心了就一定能夠做好，即使會(huì)遇到很多的困難，也一定可以突破。六、參考文獻(xiàn)：1春葆，數(shù)據(jù)結(jié)構(gòu)教程（第四版）。：清華大學(xué)，2013.七、附錄：6.1源程序：#include<stdio.h>#include<stdlib.h>#include<malloc.h>#

31、include<conio.h>#include<time.h>#include<graphics.h>#define Maxsize 50typedef struct nodechar data;struct node*lchild;struct node*rchild;int x; int y;int num;BTNode;void close();/創(chuàng)建二叉樹(shù)struct node*createBTNode(BTNode*&t,char*str)BTNode*stMaxsize,*p;int top=-1,k,j=0;char ch;t=NUL

32、L;ch=*str;while(ch!='0')switch(ch)case '(':top+;sttop=p;k=1;break;case ')':top-;break;case ',':k=2;break;default:p=(BTNode*)malloc(sizeof(BTNode); p->data=ch;p->lchild=p->rchild=NULL; if(t=NULL) t=p; else switch(k) case 1:sttop->lchild=p;break; case 2:stto

33、p->rchild=p;break;str+;ch=*str;return t;/先序遍歷void PreOrder(BTNode*t,int m,int v)int i=0;int x=90;int w;int x1,x2,y1,y2;int top=-1;char ch;int c,d;BTNode*stMaxsize,*p;outtextxy(0,400,"先序遍歷是:");if(t!=NULL)top+;t->x=m; t->y=v;sttop=t;t->num=1;while (top>-1) /棧不為空p=sttop;top-; c

34、h=p->data； outtextxy(x+10*i,400,ch); c=p->x; d=p->y;setbkcolor(YELLOW); clearcircle(c+2,d,25);setbkcolor(YELLOW); outtextxy(c,d-7,ch); Sleep(600);i+； if (p->rchild!=NULL) top+;sttop=p->rchild;if (p=t)sttop->num=t->num+1;w=140;elsesttop->num=p->num+1; if (p->num=2) w=110

35、; if (p->num=3) w=80; if (p->num=4) w=50; if (p->num=5) w=20;x1=p->x+2; y1=p->y+13;x2=x1+w; y2=y1+35;sttop->x=x2-3; sttop->y=y2; if (p->lchild!=NULL) top+;sttop=p->lchild;if (p=t)sttop->num=t->num+1;w=140;else sttop->num=p->num+1;if (p->num=2) w=110;if (p-&g

36、t;num=3) w=80;if (p->num=4) w=50;if (p->num=5)w=20; x1=p->x+2; y1=p->y+13;x2=x1-w; y2=y1+35;sttop->x=x2-3; sttop->y=y2; printf("n");/中序遍歷void inOrder(BTNode*t,int m,int v) BTNode*stMaxsize,*p,*q;int top=-1,x=90,i=0;int c,d;char ch;int w;int x1,x2,y1,y2;outtextxy(0,415,&qu

37、ot;中序遍歷是:");if(t!=NULL)t->x=m; t->y=v;t->num=1;p=t; while (top>-1 | p!=NULL)while (p!=NULL) top+;sttop=p; if(p=t） t->num=1;p=t;q=p;p=p->lchild;elseif(p!=NULL)p->num=q->num+1; q=p; p=p->lchild; if (q->num=1)w=140; if (q->num=2) w=110; if (q->num=3) w=80; if (q

38、->num=4)w=50; if (q->num=5) w=20; if (q->lchild!=NULL) x1=q->x+2; y1=q->y+13;x2=x1-w; y2=y1+35;p->x=x2-3;p->y=y2; if (top>-1) p=sttop;q=sttop;top-;ch=p->data; outtextxy(x+10*i,415,ch); c=p->x; d=p->y;setbkcolor(YELLOW); clearcircle(c+2,d,25);setbkcolor(YELLOW); outte

39、xtxy(c,d-7,ch);Sleep(600);i+; if(p->rchild!=NULL)p->rchild->num=p->num+1; if (p->num=1)w=140; if (p->num=2) w=110; if (p->num=3) w=80; if (p->num=4) w=50; if (p->num=5) w=20; if (p->rchild!=NULL) x1=p->x+2; y1=p->y+10;x2=x1+w; y2=y1+35; p=p->rchild;p->x=x2;p

40、->y=y2; else p=p->rchild; /后序遍歷void postOrder(BTNode*t,int w,int v)BTNode*stMaxsize,*p;int flag,top=-1,i=0,x=90;char ch;int c,d;int x1,x2,y1,y2;outtextxy(0,430,"后序遍歷是:");if(t!=NULL)t->x=w; t->y=v;t->num=1;do while (t!=NULL) top+;sttop=t; if (t->lchild!=NULL)t->lchild-&

41、gt;num=t->num+1; if (t->num=1)w=140; if (t->num=2)w=110; if (t->num=3)w=80; if (t->num=4)w=50; if (t->num=5)w=30; x1=t->x+2; y1=t->y+13;x2=x1-w; y2=y1+35; t->lchild->x=x2-3;t->lchild->y=y2;t=t->lchild;p=NULL；flag=1;while (top!=-1 && flag)t=sttop;if (t-&

42、gt;rchild=p)ch=t->data;outtextxy(x+10*i,430,ch);c=t->x; d=t->y; setbkcolor(YELLOW);clearcircle(c+2,d,25);setbkcolor(YELLOW);outtextxy(c,d-7,ch); Sleep(600);Sleep(10);i+;top-;p=t;elseif (t->rchild!=NULL)t->rchild->num=sttop->num+1;if (sttop->num=1)w=140; if (sttop->num=2)w=

43、110; if (sttop->num=3) w=80; if (sttop->num=4) w=50; if (sttop->num=5) w=20; x1=sttop->x+2; y1=sttop->y+13;x2=x1+w; y2=y1+35; t->rchild->x=x2-3; t->rchild->y=y2;t=t->rchild;flag=0; while(top!=-1);/圖形輸出二叉樹(shù)struct node*DrawOriginTree(BTNode*t,char*str,int x,int y)BTNode*st

44、Maxsize,*p;int top=-1,k,j=0;int x1,y1,x2=0,y2=0;int w;char ch;t=NULL;ch=*str;while(ch!='0')switch(ch)case '(':top+;sttop=p;k=1;break;case ')':top-;break;case ',':k=2;break;default:p=(BTNode*)malloc(sizeof(BTNode); p->data=ch;p->lchild=p->rchild=NULL; if(t=NUL

45、L)t=p;t->x=x;t->y=y;t->num=1;circle(x+2,y+7,15); outtextxy(x,y,t->data);elseswitch(k) case 1: sttop->lchild=p; if (p=t->lchild) p->num=t->num+1;w=140; else p->num=sttop->num+1; if (p->num=3) w=110; if (p->num=4)w=80; if (p->num=5)w=50; if (p->num=6) w=20; x1

46、=sttop->x+6; y1=sttop->y+14; x2=x1-w; y2=y1+30;line(x1,y1+7,x2,y2); clearcircle(x2-2,y2+7,15);circle(x2-2,y2+7,15); outtextxy(x2-3,y2,p->data);sttop->lchild->x=x2-3; sttop->lchild->y=y2;break; case 2: sttop->rchild=p; if (p=t->rchild)p->num=t->num+1;w=140; else p->

47、;num=sttop->num+1; if (p->num=3)w=110; if (p->num=4) w=80; if (p->num=5)w=50; if (p->num=6) w=20; x1=sttop->x+2; y1=sttop->y+13;x2=x1+w; y2=y1+35; line(x1,y1+7,x2,y2); clearcircle(x2-2,y2+7,15); circle(x2-2,y2+7,15); outtextxy(x2-3,y2,p->data); sttop->rchild->x=x2-3; st

48、top->rchild->y=y2; break;str+;ch=*str;return t;/提示界面void menu(BTNode*h)int choice;char ch3;int x=500,y=120; InputBox(ch,2,"-1.先序遍歷-n-2.中序遍歷-n-3.后序遍歷-n");sscanf(ch,"%d",&choice);switch(choice)case 1:PreOrder(h,x,y); break;case 2:inOrder(h,x,y); break;case 3:postOrder(h,x,y);