數(shù)據(jù)結(jié)構(gòu)課程設(shè)計要求

《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計一、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計要求學(xué)生應(yīng)認真主動完成課程設(shè)計的要求。有問題及時通過各種方式與教師聯(lián)系溝通。學(xué)生要發(fā)揮自主學(xué)習(xí)的能力，充分利用時間，安排好課程設(shè)計的時間計劃，并在課程設(shè)計過程中不斷檢測自己的計劃完成情況，及時向教師匯報。課余時間完成源程序和課程設(shè)計報告等文檔書寫工作，上機時間只能做調(diào)試工作。上機時帶上源程序（自備U盤）、數(shù)據(jù)結(jié)構(gòu)教材、實驗指導(dǎo)書、C語言教材。第17周收集課程設(shè)計報告等文檔資料，并進行面試，學(xué)生要能夠說明自己的設(shè)計思路和具體實現(xiàn)方法。二、 上交相關(guān)內(nèi)容要求上交的成果的內(nèi)容必須由以下三部分組成，缺一不可。源程序：學(xué)生按照課程設(shè)計的具體要求所開發(fā)的所有源程序（應(yīng)該放到一個文件夾中），若有必要，請加入程序說明文件；課程設(shè)計報告：要求提交課程設(shè)計報告的word文檔電子稿和打印稿，word文件名要求按照”學(xué)號-姓名-課程設(shè)計報告題目”起名，如文件名為"001-張三-利用棧求表達式的值".doc。課程設(shè)計報告內(nèi)容主要包括：項目研究背景與意義需求分析：在該部分中敘述，每個模塊的功能要求；概要設(shè)計：在此說明每個部分的算法設(shè)計說明（可以是描述算法的流程圖）每個程序中使用的存儲結(jié)構(gòu)設(shè)計說明（如果指定存儲結(jié)構(gòu)請寫出該存儲結(jié)構(gòu)的定義。詳細設(shè)計：各個算法實現(xiàn)的源程序，對每個題目要有相應(yīng)的源程序（可以是一組源程序，每個功能模塊采用不同的函數(shù)實現(xiàn)）源程序要按照寫程序的規(guī)則來編寫。要結(jié)構(gòu)清晰，重點函數(shù)的重點變量，重點功能部分要加上清晰的程序注釋。調(diào)試分析測試數(shù)據(jù)，測試輸出的結(jié)果，時間復(fù)雜度分析，和每個模塊設(shè)計和調(diào)試時存在問題的思考（問題是哪些？問題如何解決？），算法的改進設(shè)想。總結(jié)總結(jié)可以包括課程設(shè)計過程中的收獲、遇到問題、遇到問題解決問題過程的思考、程序調(diào)試能力的思考、對數(shù)據(jù)結(jié)構(gòu)這門課程的思考、在課程設(shè)計過程中對《數(shù)據(jù)結(jié)構(gòu)》課程的認識等內(nèi)容。三、 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計題目1、用單鏈表實現(xiàn)一個簡易通訊錄。基本要求：程序功能包括通訊錄的的建立和顯示、聯(lián)系人的插入、刪除、修改和查詢等幾種操作功能。程序應(yīng)提供菜單界面，主界面的菜單請參考如下形式設(shè)計：

*********************************************************************TOC\o"1-5"\h\z通訊錄管理系統(tǒng) *1.添加聯(lián)系人信息 *2.查詢聯(lián)系人信息 *3.修改聯(lián)系人信息 *4.刪除聯(lián)系人信息 *0.退出通訊錄管理系統(tǒng) **********************************************************************請選擇0—4：2、利用棧求表達式的值編寫程序?qū)崿F(xiàn)表達式求值，即驗證某算術(shù)表達式的正確性，若正確，則計算該算術(shù)表達式的值。主要功能描述如下：1） 從鍵盤上輸入表達式。2） 分析該表達式是否合法：（1） 是數(shù)字，則判斷該數(shù)字的合法性。若合法，則壓入數(shù)據(jù)到堆棧中。（2） 是規(guī)定的運算符，則根據(jù)規(guī)則進行處理。在處理過程中，將計算該表達式的值。（3） 若是其它字符，則返回錯誤信息。3） 若上述處理過程中沒有發(fā)現(xiàn)錯誤，則認為該表達式合法，并打印處理結(jié)果。3、迷宮問題以一個m*n的長方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設(shè)計一個程序，對任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結(jié)論?；疽螅海?）實現(xiàn)一個棧類型，然后編寫一個求解迷宮的程序。求得的通路以三元組（i,j,d）的形式輸出，其中：（i,j）指示迷宮中的一個坐標(biāo)，d表示走到下一坐標(biāo)的方向。（2） 求得迷宮中所有可能的通路；（3） 以方陣形式輸出迷宮及其通路。（選做）測試數(shù)據(jù)：迷宮的測試數(shù)據(jù)如下：左上角（1，1）為入口，右下角（9，8）為出口。1 2 3 4 5 6 7 800001000100000011100010100011111001100001000101101001000000101100101010000實現(xiàn)提示：計算機解迷宮通常用的是“窮舉求解”方法，即從入口出發(fā)，順著某一個方向進行探索，若能走通，則繼續(xù)往前進；否則沿著原路退回，換一個方向繼續(xù)探索，直至出口位置，求得一條通路。假如所有可能的通路都探索到而未能到達出口，則所設(shè)定的迷宮沒有通路?？梢远S數(shù)組存儲迷宮數(shù)據(jù)，通常設(shè)定入口點的下標(biāo)為（1，1），出口點的下標(biāo)為（m,n）。為處理方便起見，可在迷宮的四周加一圈障礙。對于迷宮中任一位置，均可約定有東、南、西、北四個方向可通。4、 哈夫曼編碼/譯碼器設(shè)計一個利用哈夫曼算法的編碼和譯碼系統(tǒng)，重復(fù)地顯示并處理以下項目，直到選擇退出為止。1） 將權(quán)值數(shù)據(jù)存放在數(shù)據(jù)文件（文件名為data.txt，位于執(zhí)行程序的當(dāng)前目錄中）2） 采用靜態(tài)存儲結(jié)構(gòu)3） 初始化：鍵盤輸入字符集大小n、n個字符和n個權(quán)值，建立哈夫曼樹；4） 編碼：利用建好的哈夫曼樹生成哈夫曼編碼；5） 輸出編碼；6） 設(shè)字符集及頻度如下表：字符空格ABCDEFGHIJKLM頻度1866413223210321154757153220字符NOPQRSTUVWXYZ頻度57631514851802381811615、 校園導(dǎo)航問題設(shè)計要求：設(shè)計你的學(xué)校的平面圖，至少包括8個以上的場所，每兩個場所間可以有不同的路，且路長也可能不同，找出從任意場所到達另一場所的最佳路徑（最短路徑）。1） 基本要求：（1） 設(shè)計校園平面圖，在校園景點選10個左右景點。以圖中頂點表示校園內(nèi)各景點，存放景點名稱、代號、簡介等信息；以邊表示路徑，存放路徑長