【正文】 課 程 設(shè) 計 報 告課程名稱 數(shù)據(jù)結(jié)構(gòu) 課題名稱 二叉樹遍歷演示 專 業(yè) 網(wǎng)絡(luò)工程 班 級 網(wǎng)絡(luò)工程1102 學(xué) 號 201103120202 姓 名 吳琪 指導(dǎo)教師 陳淑紅 張曉清 李杰君 2013年 7 月 3 日湖南工程學(xué)院課 程 設(shè) 計 任 務(wù) 書課程名稱 數(shù)據(jù)結(jié)構(gòu) 課 題 二叉樹遍歷演示 專業(yè)班級 網(wǎng)絡(luò)工程 學(xué)生姓名 吳琪 學(xué) 號 201103120201 指導(dǎo)老師 陳淑紅 張曉清 李杰君 審 批 任務(wù)書下達日期 2013 年 6 月 25 日任務(wù)完成日期 2013年 7 月 3 日 課程設(shè)計報告任務(wù)書設(shè)計內(nèi)容與設(shè)計要求 算術(shù)24游戲演示由系統(tǒng)隨機生成4張撲克牌，用戶利用撲克牌的數(shù)字及運算符號“+”、“—”、“*”、“/”及括號“（”和“）”從鍵盤上輸入一個計算表達式，系統(tǒng)運行后得出計算結(jié)果，如果結(jié)果等于24，則顯示“Congratulation!”，否則顯示“Incorrect!”設(shè)計思路：從鍵盤輸入中綴表達式，然后將中綴表達式轉(zhuǎn)換為后綴表達式，利用后綴表達式求值。 迷宮探索隨機生成一個迷宮圖，迷宮大小為N*N，N預(yù)定義為常數(shù)，修改N的值可以改變迷宮的大小。用白色表示可走的路，藍色表示墻壁不可以通過。系統(tǒng)設(shè)計兩種運行方式：一種是系統(tǒng)自動探索（用遞歸方法實現(xiàn)）；另一種是由人工操作探索通路。設(shè)計思路：程序首先要考慮迷宮的表示，這是一個二維關(guān)系圖，所以可選擇二維數(shù)組來存儲。數(shù)組元素只有兩種值0和1，分別代表通路和墻壁。圖形的顯示可以根據(jù)數(shù)組元素的值來確定。如果是人工探索，則依據(jù)按鍵來確定探索物的位置坐標，利用循環(huán)語句實現(xiàn)。如果是系統(tǒng)自動探索，可采用遞歸算法實現(xiàn)。 二叉樹遍歷演示演示遍歷二叉樹的過程，所以首先建立二叉樹，并用圖形顯示出樹的形狀。建立的過程是采用前序便利的方法來創(chuàng)建，設(shè)計兩種生成樹的方式：一種是系統(tǒng)隨機生成，另一種是人工輸入。考慮到屏幕界面的有限性，限定二叉樹不超過5層，最多26個字符，輸入字符小數(shù)點“.”代表NULL。初始樹為某種顏色的結(jié)點，三種情況的遍歷采用填充另外一種醒目的顏色，來表示當(dāng)前遍歷的結(jié)點，同時顯示該結(jié)點的訪問序號。同時在遍歷的過程中在遍歷圖形的下方顯示出遍歷序列。 拓撲排序演示演示拓撲排序的過程。按照有向圖給出的次序關(guān)系，將圖中頂點排成一個線性序列，對于有向圖中沒有限定次序關(guān)系的頂點，則可以人為加上任意的次序關(guān)系。要求每輸出一個頂點后就演示從圖中刪去此頂點以及所有以它為尾的弧。 圖的遍歷演示圖的深度優(yōu)先, 廣度優(yōu)先遍歷過程，并輸出原圖結(jié)構(gòu)及遍歷結(jié)果。要求圖的結(jié)點數(shù)不能少于6個。可以由系統(tǒng)隨機生成圖，也可以由用戶手動輸入圖。報告中要寫出畫圖的思路；畫出圖的結(jié)構(gòu)，有興趣的同學(xué)可以進一步改進圖的效果。 雙鏈表創(chuàng)建演示建立一個遞增有序的雙鏈表。功能是隨機生成8個結(jié)點數(shù)據(jù)，每生成一個結(jié)點則申請空間得到一個指針，將數(shù)據(jù)存放到指針所指的數(shù)據(jù)域中，然后將結(jié)點插入到已經(jīng)排好序的雙鏈表中。所以第一步工作是判斷新結(jié)點的插入位置，第二演示插入過程中指針的變化，第三步顯示插入后的鏈表結(jié)果。 選作課題：公園導(dǎo)游圖給出一張某公園的導(dǎo)游圖，游客通過終端詢問可知：從某一景點到另一景點的最短路徑。游客從公園大門進入，選一條最佳路線，使游客可以不重復(fù)地游覽各景點，最后回到出口（出口就在入口旁邊）。要求用圖示展示最佳路徑。 最小生成樹算法演示隨機生成一個網(wǎng)，并用圖形展示，然后依據(jù)Prim算法或Kruskal算法求該圖的最小生成樹，并用圖形展示相應(yīng)的過程步驟。 選題方案：所選題目根據(jù)學(xué)號確定，學(xué)號模6加1，即（學(xué)號%6+1）。如你的學(xué)號為13，則所選題目號為：13%6+1＝（題目2）。注意，所有的課題都要求用圖形方式演示步驟和結(jié)果。有興趣的同學(xué)可以可以選擇選做課題七或課題八，也可以自己針對數(shù)據(jù)結(jié)構(gòu)課程中所講算法來設(shè)計一個演示過程的算法，但要預(yù)先告知老師，經(jīng)過審批，方可確定課題。： 課程設(shè)計報告規(guī)范（1）需求分析a. 程序的功能。b. 輸入輸出的要求。（2）概要設(shè)計a. 程序由哪些模塊組成以及模塊之間的層次結(jié)構(gòu)、各模塊的調(diào)用關(guān)系；每個模塊的功能。b. 課題涉及的數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)庫結(jié)構(gòu)；即要存儲什么數(shù)據(jù)，這些數(shù)據(jù)是什么樣的結(jié)構(gòu)，它們之間有什么關(guān)系等。（3）詳細設(shè)計a. 采用C語言定義相關(guān)的數(shù)據(jù)類型。b. 寫出各模塊的類C碼算法。c. 畫出各函數(shù)的調(diào)用關(guān)系圖、主要函數(shù)的流程圖。（4）調(diào)試分析以及設(shè)計體會a. 測試數(shù)據(jù)：準備典型的測試數(shù)據(jù)和測試方案，包括正確的輸入及輸出結(jié)果和含有錯誤的輸入及輸出結(jié)果。b. 程序調(diào)試中遇到的問題以及解決問題的方法。c. 課程設(shè)計過程經(jīng)驗教訓(xùn)、心得體會。（5）使用說明用戶使用手冊：說明如何使用你編寫的程序，詳細列出每一步的操作步驟。 （6）書寫格式a. 設(shè)計報告要求用A4紙打印成冊：b. 一級標題用3號黑體,二級標題用四號宋體加粗,正文用小四號宋體。行距為22。（7）附錄a. 源程序清單（帶注釋） 考核方式指導(dǎo)老師負責(zé)驗收程序的運行結(jié)果，并結(jié)合學(xué)生的工作態(tài)度、實際動手能力、創(chuàng)新精神和設(shè)計報告等進行綜合考評，并按優(yōu)秀、良好、中等、及格和不及格五個等級給出每位同學(xué)的課程設(shè)計成績。具體考核標準包含以下幾個部分：（1）平時出勤 （占10%）（2）系統(tǒng)需求分析、功能設(shè)計、數(shù)據(jù)結(jié)構(gòu)設(shè)計及程序總體結(jié)構(gòu)合理與否（占10%）（3）程序能否完整、準確地運行，個人能否獨立、熟練地調(diào)試程序（占40%）（4）設(shè)計報告（占30%）注意：不得抄襲他人的報告（或給他人抄襲），一旦發(fā)現(xiàn)，成績?yōu)榱惴?。?）獨立完成情況（占10%）。 課程驗收要求（1）運行所設(shè)計的系統(tǒng)。（2）回答有關(guān)問題。（3）提交課程設(shè)計報告。（4）提交軟盤（源程序、設(shè)計報告文檔）。（5）依內(nèi)容的創(chuàng)新程度，完善程序情況及對程序講解情況打分。2 、進度安排第 18 周：星期二 14：30——16：30 上課 星期二 18：00——22：00 上機星期三 18：00——22：00 上機 星期四 18：00——22：00 上機第 19 周：星期一 14：00——18：00 上機 星期二 14：00——18：00 上機 星期三 8：00——12：00 上機 附：課程設(shè)計報告裝訂順序：封面、任務(wù)書、目錄、正文、評分、附件（A4大小的圖紙及程序清單）。 正文的格式:一級標題用3號黑體,二級標題用四號宋體加粗, 三級標題用小四號宋體加粗，正文用小四號宋體。行距為22。正文的內(nèi)容:一、課題的主要功能；二、課題的功能模塊的劃分（要求畫出模塊圖）；三、主要功能的實現(xiàn)（至少要有一個主要模塊的流程圖）；四、程序調(diào)試；五、總結(jié)；六、附件（所有程序的原代碼，要求對程序?qū)懗霰匾淖⑨專?。正文總字?shù)要求在5000字以上（不含程序原代碼） 目錄一、需求分析： 1： 1： 1： 1二、概要設(shè)計： 1： 1： 2： 3 4： 4： 5： 7： 7： 8： 8： 8： 8： 9四、調(diào)試與測試： 10： 10： 11五、心得體會： 14六、參考文獻： 15七、附錄： 15 課程設(shè)計報告一、需求分析： ： 演示遍歷二叉樹的過程，所以首先建立二叉樹，并用圖形顯示出樹的形狀。建立的過程是采用前序便利的方法來創(chuàng)建，設(shè)計兩種生成樹的方式：一種是系統(tǒng)隨機生成，另一種是人工輸入?？紤]到屏幕界面的有限性，限定二叉樹不超過5層，最多26個字符，輸入字符小數(shù)點“.”代表NULL。初始樹為某種顏色的結(jié)點，三種情況的遍歷采用填充另外一種醒目的顏色，來表示當(dāng)前遍歷的結(jié)點，同時顯示該結(jié)點的訪問序號。同時在遍歷的過程中在遍歷圖形的下方顯示出遍歷序列。 ： ： （1）人工輸入二叉樹的序列； （2）隨機產(chǎn)生二叉樹的序列。 ： 用圖形的方式演示二叉樹的三種遍歷： ?先序遍歷、?中序遍歷、?后序遍歷。 二、概要設(shè)計： ：typedef struct node{ char data。 struct node*lchild。 struct node*rchild。 int x。