數(shù)據(jù)結(jié)構(gòu)課程方案任務(wù)書通信

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

<占

40%）<4）設(shè)計報告

<占

30%）注意：不得抄襲他人的報告 <或給他人抄襲），一旦發(fā)現(xiàn)，成績?yōu)榱惴?。個人資料整理 僅限學(xué)習(xí)使用<5）獨立完成情況<占10%）。1.3.3課程驗收要求<1）運行所設(shè)計的系統(tǒng)。<2）回答有關(guān)問題。<3）提交課程設(shè)計報告。<4）提交軟盤<源程序、設(shè)計報告文檔）。<5）依內(nèi)容的創(chuàng)新程度，完善程序情況及對程序講解情況打分。進度安排第20周：星期一8：00——12：00上課星期二8：00——12：00上機星期三14：30——18：30上機星期四 8：00——12：00 上機附：課程設(shè)計報告裝訂順序：封面、任務(wù)書、目錄、正文、評分表、附件 <A4大小的圖紙及程序清單）。正文的格式:一級標(biāo)題用 3號黑體,二級標(biāo)題用四號宋體加粗 ,正文用小四號宋體。行距為 22。正文的內(nèi)容:一、課題的主要功能；二、課題的功能模塊的劃分 <要求畫出模塊圖）；三、主要功能的實現(xiàn)<至少要有一個主要模塊的流程圖）；四、程序調(diào)試；五、總結(jié)；六、附件 <所有程序的原