數(shù)據(jù)結(jié)構(gòu)課程設(shè)計任務(wù)書通信1081.doc

課 程 設(shè) 計 報 告課程名稱 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 課題名稱 專 業(yè) 通信工程 班 級 通信工程1081 學(xué) 號 姓 名 指導(dǎo)教師 田娟秀 郭芳 2012年 7 月 6 日湖南工程學(xué)院課 程 設(shè) 計 任 務(wù) 書課程名稱 數(shù)據(jù)結(jié)構(gòu) 課 題 專業(yè)班級 學(xué)生姓名 學(xué) 號 指導(dǎo)老師 審 批 任務(wù)書下達(dá)日期 2012 年 7 月 1 日任務(wù)完成日期 2012 年 7 月 6 日1設(shè)計內(nèi)容與設(shè)計要求1.1設(shè)計內(nèi)容（1）課題一：中綴算術(shù)表達(dá)式求值我們很早就學(xué)習(xí)如何書寫及計算表達(dá)式，諸如：8+5*（7-3）之類的表達(dá)式，先算括號內(nèi)的7減去3，得到4，然后再算5乘以4，得到20，再計算8加上20，得到28，因此該表達(dá)式的值為28。這是人們熟悉的運(yùn)算規(guī)則額：有括號先算括號內(nèi)；無括號時，先做乘除法，后做加減法；對于相同級別的運(yùn)算按從左到右的次序運(yùn)算。而計算機(jī)是如何實(shí)現(xiàn)表達(dá)式的計算的呢？應(yīng)用棧的相關(guān)知識，編程序?qū)崿F(xiàn)之。設(shè)計思路：從鍵盤輸入中綴表達(dá)式，然后將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式，利用后綴表達(dá)式求值。要求以字符序列的形式從終端輸入語法正確的、不含變量的整數(shù)表達(dá)式，利用給定的算術(shù)符優(yōu)先關(guān)系，實(shí)現(xiàn)對算數(shù)四則混合運(yùn)算表達(dá)式的求值，并演示在求值過程中運(yùn)算符棧、操作符棧、輸入字符和主要操作的變化過程。（2）課題二：迷宮探索隨機(jī)生成一個迷宮圖，迷宮大小為N*N，N預(yù)定義為常數(shù)，修改N的值可以改變迷宮的大小。用白色表示可走的路，藍(lán)色表示墻壁不可以通過，箭頭表示走過的路徑。系統(tǒng)設(shè)計兩種運(yùn)行方式：一種是系統(tǒng)自動探索（用遞歸方法實(shí)現(xiàn)）；另一種是由人工操作探索通路。設(shè)計思路：程序首先要考慮迷宮的表示，這是一個二維關(guān)系圖，所以可選擇二維數(shù)組來存儲。數(shù)組元素只有兩種值0和1，分別代表通路和墻壁。圖形的顯示可以根據(jù)數(shù)組元素的值來確定。如果是人工探索，則依據(jù)按鍵來確定探索物的位置坐標(biāo)，利用循環(huán)語句實(shí)現(xiàn)。如果是系統(tǒng)自動探索，可采用遞歸算法實(shí)現(xiàn)。要求用Turbo C或VC6.0 MFC實(shí)現(xiàn)的迷宮探索問題的圖形程序。（3）課題三：漢諾塔問題界面劃出大小不等，顏色不同的矩形塊分別代表各盤子，盤子規(guī)模n為110，并可以選擇人工控制演示和系統(tǒng)自動運(yùn)行演示，如果是自動則還要輸入演示速度。在界面的上方顯示正在移動的盤子的源座和目標(biāo)座。用人工操作時，按任意鍵移動一個盤子，這樣可以清楚每一步過程。如果是自動運(yùn)行，可以選擇移動一步的暫停時間。要求用Turbo C或VC6.0 MFC實(shí)現(xiàn)的漢諾塔問題的圖形程序。設(shè)計思路：用棧存放塔，定義三個堆棧，用來表示三個塔座，棧的每個結(jié)點(diǎn)類型為結(jié)構(gòu)體，其中數(shù)據(jù)域存放盤子的代號，根據(jù)代號計算盤子的大小。Top為塔的棧頂指針，即每個塔的具體高度。例如，結(jié)構(gòu)體可以定義如下：Struct H int data15;/*存放每個盤的代號*/ int top;/*每個塔的具體高度*/num3;（4）課題四：八皇后問題演示八皇后問題是一個古老而著名的問題，是回溯算法的典型例題。該問題是十九世紀(jì)著名的數(shù)學(xué)家高斯1850年提出：在88格的國際象棋上擺放八個皇后，使其不能互相攻擊，即任意兩個皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法。高斯認(rèn)為有76種方案。1854年在柏林的象棋雜志上不同的作者發(fā)表了40種不同的解，后來有人用圖論的方法解出92種結(jié)果。設(shè)計思路：解決8皇后時，在安放第i行皇后時，需要在列的方向從1到n試探(j =1, n)：首先在第j列安放一個皇后，如果在列、主對角線、次對角線方向有其它皇后，則出現(xiàn)攻擊，撤消在第j列安放的皇后。如果沒有出現(xiàn)攻擊，在第j列安放的皇后不動，遞歸安放第i+1行皇后。 對于八皇后問題的實(shí)現(xiàn)，如果結(jié)合動態(tài)的圖形演示，則可以使算法的描述更形象、更生動。要求用Turbo C或VC6.0 MFC實(shí)現(xiàn)的八皇后問題的圖形程序，能夠演示全部的92組解。 （5）課題五：對電文中的字符串編碼和譯碼Huffman編碼是一種最優(yōu)變長碼，即帶權(quán)路徑最小。這種編碼有很強(qiáng)的應(yīng)用背景，是數(shù)據(jù)壓縮中的一個重要理論依據(jù)。對輸入的一串文字符號實(shí)現(xiàn)Huffman編碼，再對Huffman編碼生成的代碼串進(jìn)行譯碼，輸出電文字符串。要求完成以下功能：(a) 提供界面讓用戶輸入電文字符串或指定電文文件。(b) 生成相應(yīng)電文字符串或指定電文文件的Huffman編碼。(c) 提供界面讓用戶指定編碼文件,而后將其譯成電文。（6）課題六：交通咨詢系統(tǒng)在交通網(wǎng)絡(luò)非常發(fā)達(dá)的今天，人們出差、旅游或做其他出行時，不僅關(guān)心節(jié)省交通費(fèi)用，而且對里程和所需時間等問題也很感興趣。對于這樣一個人們關(guān)心的問題，可用一個圖結(jié)構(gòu)來表示交通網(wǎng)絡(luò)系統(tǒng)，利用計算機(jī)建立一個交通咨詢系統(tǒng)。圖中頂點(diǎn)表示城市，邊表示城市之間的交通關(guān)系。設(shè)計一個交通咨詢系統(tǒng)，能讓旅客咨詢從任一個城市頂點(diǎn)到達(dá)另外一個城市頂點(diǎn)之間的最短路徑（里程）的問題。 要求完成以下功能：(a) 以圖中頂點(diǎn)表示湖南省各市(至少包括8個以上的城市)，存放城市名稱、代號、簡介等信息，以邊表示路徑，存放路徑長度等有關(guān)信息，先建立交通網(wǎng)絡(luò)圖的存儲結(jié)構(gòu)；(b) 為用戶提供圖中任何城市有關(guān)信息的查詢；(c) 為用戶提供任意城市的交通查詢,即查詢?nèi)我鈨蓚€城市之間的一條最短路徑。(d) 為用戶提供指定城市的交通查詢，即查詢指定城市到其他城市之間的最短路徑。選做內(nèi)容：（1）提供圖的編輯功能：增、刪城市；增刪路徑；修改已有信息等；（2）交通圖的仿真界面。1.2 選題方案：所選題目根據(jù)學(xué)號確定，學(xué)號模6加1，即（學(xué)號%6+1）。如你的學(xué)號為9，則所選題目號為：9%6+1（題目4）。注意，所有的課題都要求用圖形方式演示步驟和結(jié)果。同學(xué)們可以自己針對數(shù)據(jù)結(jié)構(gòu)課程中所講算法來設(shè)計一個演示過程的算法。1.3設(shè)計要求：1.3.1 課程設(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）詳細(xì)設(shè)計a.采用C語言定義相關(guān)的數(shù)據(jù)類型。b 寫出各模塊的類C碼算法。c.畫出各函數(shù)的調(diào)用關(guān)系圖、主要函數(shù)的流程圖。（4）調(diào)試分析以及設(shè)計體會a.測試數(shù)據(jù)：準(zhǔn)備典型的測試數(shù)據(jù)和測試方案，包括正確的輸入及輸出結(jié)果和含有錯誤的輸入及輸出結(jié)果。b.程序調(diào)試中遇到的問題以及解決問題的方法。c.課程設(shè)計過程經(jīng)驗(yàn)教訓(xùn)、心得體會。（5）使用說明用戶使用手冊：說明如何使用你編寫的程序，詳細(xì)列出每一步的操作步驟。（6）書寫格式a.設(shè)計報告要求用A4紙打印成冊：b.一級標(biāo)題用3號黑體,二級標(biāo)題用四號宋體加粗,正文用小四號宋體;行距為22。（7）附錄源程序清單（帶注釋）1.3.2 考核方式指導(dǎo)老師負(fù)責(zé)驗(yàn)收程序的運(yùn)行結(jié)果，并結(jié)合學(xué)生的工作態(tài)度、實(shí)際動手能力、創(chuàng)新精神和設(shè)計報告等進(jìn)行綜合考評，并按優(yōu)秀、良好、中等、及格和不及格五個等級給出每位同學(xué)的課程設(shè)計成績。具體考核標(biāo)準(zhǔn)包含以下幾個部分：（1）平時出勤 （占10%）（2）系統(tǒng)需求分析、功能設(shè)計、數(shù)據(jù)結(jié)構(gòu)設(shè)計及程序總體結(jié)構(gòu)合理與否（占10%）（3）程序能否完整、準(zhǔn)確地運(yùn)行，個人能否獨(dú)立、熟練地調(diào)試程序（占40%）（4）設(shè)計報告（占30%）注意：不得抄襲他人的報告（或給他人抄襲），一旦發(fā)現(xiàn)，成績?yōu)榱惴帧＃?）獨(dú)立完成情況（占10%）。1.3.3 課程驗(yàn)收要求（1）運(yùn)行所設(shè)計的系統(tǒng)。（2）回答有關(guān)問題。（3）提交課程設(shè)計報告。（4）提交軟盤（源程序、設(shè)計報告文檔）。（5）依內(nèi)容的創(chuàng)新程度，完善程序情況及對程序講解情況打分。2 進(jìn)度安排第 20 周：星期一 8：0012：00 上課 星期二 8：0012：00 上機(jī) 星期三 14：3018：30 上機(jī)星期四 8：0012：00 上機(jī)附：課程設(shè)計報告裝訂順序：封面、任務(wù)書、目錄、正文、評分表、附件（A4大小的圖紙及程序清單）。 正文的格式:一級標(biāo)題用3號黑體,二級標(biāo)題用四號宋體加粗,正文用小四號宋體;行距為22。正文的內(nèi)容:一、課題的主要功能；二、課題的功能模塊的劃分（要求畫出模塊圖）；三、主要功能的實(shí)現(xiàn)（至少要有一個主要模塊的流程圖）；四、程序調(diào)試；五、總結(jié)；六、附件（所有