08092數(shù)據(jù)結(jié)構(gòu)課程設(shè)計任務(wù)書網(wǎng)絡(luò)07級

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計任務(wù)書使用班級：網(wǎng)絡(luò)0701，0702，0703，0704使用學期：2008-2009學年第二學期指導老師：林芳、蔣建輝、肖琳2009年6月1日數(shù)據(jù)結(jié)構(gòu)課程設(shè)計任務(wù)書一、設(shè)計目的 算法與數(shù)據(jù)結(jié)構(gòu)是計算機專業(yè)的核心課程，是一門實踐性很強的課程。為了學好這門課程，必須在掌握理論知識的同時，加強上機實踐。課程設(shè)計是加強學生實踐能力的一個強有力手段，要求學生掌握數(shù)據(jù)結(jié)構(gòu)的應(yīng)用、算法的編寫、將算法轉(zhuǎn)換成程序并上機調(diào)試的基本方法，還要求學生在完成程序設(shè)計的同時能夠?qū)懗霰容^規(guī)范的設(shè)計報告。本課程設(shè)計的目的就是要達到理論與實際應(yīng)用相結(jié)合，使同學們能夠根據(jù)數(shù)據(jù)對象的特性，學會數(shù)據(jù)組織的方法，能把

2、現(xiàn)實世界中的實際問題在計算機內(nèi)部表示出來，并培養(yǎng)學生的基本程序設(shè)計素養(yǎng)和軟件工作者工作作風。二、設(shè)計內(nèi)容題目1：基本線性表的就地逆置 在基本線性表原有空間的基礎(chǔ)上，將線性表中的數(shù)據(jù)元素逆置，使新的順序序列與原來的順序序列剛好相反。如原來順序序列“abcdef”，逆置之后的新順序序列為”fedcba”。要求：數(shù)據(jù)結(jié)構(gòu)可以選擇順序結(jié)構(gòu)或鏈式結(jié)構(gòu)；操作過程必須在線性表的原有空間，不能借助臨時變量所申請的臨時空間，也不能借助其他形式的臨時空間。題目2：火車票銷售編制一個簡單的火車票銷售系統(tǒng)，可完成售票、退票、車票剩余情況查詢等功能。每張車票包含車次、座位信息。要求：在售票、退票、車票剩余情況查詢等環(huán)節(jié)

3、中，都必須顯示出車票的具體信息（車次、座位信息）；退票時，必須是車站售出的票才能退。題目3：簡單編譯器的實現(xiàn)將中綴表達式轉(zhuǎn)換為后綴表達式。假設(shè)輸入的算法表達式的運算符只有“、×、/、（、）”這幾種。要求：用棧完成；首先要判斷輸入的表達式括號是否配對，在正確表達式的基礎(chǔ)上轉(zhuǎn)換為后綴表達式。題目4：商品貨架管理 商店貨架以棧的方式擺放商品。商品貨架可以看成一個棧，棧頂商品的生產(chǎn)日期最早，棧底商品的生產(chǎn)日期最近。生產(chǎn)日期越接近的越靠棧底，出貨時從棧頂取貨。一天營業(yè)結(jié)束，如果貨架不滿，則需上貨。入貨直接將商品擺放到貨架上，則會使生產(chǎn)日期越近的商品越靠近棧頂。這樣就需要倒貨架，使生產(chǎn)日期越近的

4、越靠近棧底。請編寫程序模擬商品銷售，上架操作。（設(shè)有5種商品，每種商品至少有商品名和生產(chǎn)日期兩個屬性）題目5：模擬停車場管理的問題 設(shè)停車場只有一個可停放幾輛汽車的狹長通道，且只有一個大門可供汽車進出。汽車在停車場按車輛到來的先后順序依次排列，若車場內(nèi)已停滿幾輛汽車，則后來的汽車只能在門外的便道上等候，一旦停車場內(nèi)有車開走，則排在便道上的第一輛車即可進入；當停車場內(nèi)某輛車要離開時，由于停車場是狹長的通道，在它之后開入的車輛必須先退出車場為它讓路，待該輛車開出大門后，為它讓路的車輛在按原次序進入車場。每輛停放在車場的車在它離開停車場時必須按它停留的時間長短交納費用。試為停車場編制按上述要求進行管

5、理的模擬程序。在這里假設(shè)汽車不能從便道上開走。試設(shè)計一個停車場管理程序。實現(xiàn)提示：以棧模擬停車場，以隊列模擬車場外的便道，按照從終端讀入的輸入數(shù)據(jù)序列進行模擬管理。每一組輸入數(shù)據(jù)包括三個數(shù)據(jù)項：汽車“到達”或“離去”信息、汽車牌照號碼及到達或離去的時刻，例如：('A',1,5)表示一號牌照車愛5這個時刻到達，而('D',5,20)表示5號牌照車在20這個時刻離去，整個程序可以在輸入信息為('E',0,0)時結(jié)束。對每一組輸入數(shù)據(jù)進行操作后的輸出數(shù)據(jù)為：若是車輛到達，則輸出汽車在停車場內(nèi)或便道上的停車位置；若是車離去；則輸出汽車在停車場內(nèi)停留的時間

6、和應(yīng)交納的費用（在便道上停留的時間不收費）。棧以順序結(jié)構(gòu)實現(xiàn)，隊列以鏈表實現(xiàn)。需另設(shè)一個棧，臨時停放為給要離去的汽車讓路而從停車場退出來的汽車，題目6：哈夫曼編碼和譯碼 利用哈夫曼編碼進行信息通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來的數(shù)據(jù)進行譯碼（復(fù)原）。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫一個哈夫曼編/譯碼系統(tǒng)。基本要求:一個完整的系統(tǒng)應(yīng)具有以下功能：（1）初始化（Initialization）。從終端讀入字符集大小n，以及n個字符和n個權(quán)值

7、，建立哈夫曼樹，(選做：并將它存于文件hfmTree中）。并顯示出每個字符的編碼。（2）編碼（Encoding）。利用已建好的哈夫曼樹（選做：如不在內(nèi)存，則從文件htmTree中讀入），對輸入的字符串文本（選做：對文件ToBeTran中的正文）進行編碼，（選做：然后將結(jié)果存入文件CodeFile中。）并顯示在屏幕上。（3）譯碼（Decoding）。利用已建好的哈夫曼樹將輸入的代碼進行譯碼（選做：將文件CodeFile中的代碼進行譯碼，結(jié)果存入文件TextFile中。），并顯示在屏幕上。（4）打印哈夫曼樹（Tree Printing）。將已在內(nèi)存中的哈夫曼樹以直觀的方式顯示在屏幕上。題目7：校園

8、導游程序 設(shè)計一個校園導游程序為來訪的客人提供各種信息查詢服務(wù)?；疽螅海?）)設(shè)計學校的旗山校區(qū)北區(qū)校園平面圖，所含場所不少于10個。以圖中頂點表示校內(nèi)各場所，存放場所名稱、代號、簡介等信息；以邊表示路徑，存放路徑長度等相關(guān)信息。（2）為來訪客人提供圖中任意場所相關(guān)信息的查詢。（3）為來訪客人提供圖中任意場所的問路查詢，即查詢?nèi)我鈨蓚€景點之間的一條最短的簡單路徑。題目8：內(nèi)部排序算法比較 各種內(nèi)部排序算法的時間復(fù)雜度分析結(jié)果只給出了算法執(zhí)行時間的階，或大概執(zhí)行時間。試通過隨機的數(shù)據(jù)比較各算法的關(guān)鍵字比較次數(shù)和關(guān)鍵字移動次數(shù)，以取得直觀感受?；疽螅海?） 從以下常用的內(nèi)部排序算法至少選取

9、5種進行比較：直接插入排序；折半折入排序；希爾排序；起泡排序；快速排序；簡單選擇排序；堆排序；歸并排序。（2） 待排序表的表長為20000；其中的數(shù)據(jù)要用偽隨機數(shù)產(chǎn)生程序產(chǎn)生；至少要用5組不同的輸入數(shù)據(jù)作比較；比較的指標為有關(guān)鍵字參加的比較次數(shù)和關(guān)鍵字移動次數(shù)（關(guān)鍵字交換計為3次移動）。題目9：哈希表設(shè)計 針對同班同學信息設(shè)計一個通訊錄，學生信息有姓名，學號，電話號碼等。以學生姓名為關(guān)鍵字設(shè)計哈希表，并完成相應(yīng)的建表和查表程序。基本要求：姓名以漢語拼音形式，待填入哈希表的人名約30個，自行設(shè)計哈希函數(shù)，用線性探測再散列法或鏈地址法處理沖突；在查找的過程中給出比較的次數(shù)。完成按姓名查詢的操作。題

10、目10：平衡二叉樹 二叉排序樹的查找效率取決于二叉樹的形態(tài)，而二叉排序樹的形態(tài)與生成樹時結(jié)點的插入次序有關(guān)，而結(jié)點的插入次序往往不能預(yù)先確定，這就需要在生成二叉排序樹的過程中進行動態(tài)調(diào)整，以構(gòu)造形態(tài)勻稱的平衡二叉樹。設(shè)計實現(xiàn)按輸入的序列構(gòu)造平衡二叉樹。要求：對構(gòu)造好的平衡二叉樹進行先序和中序遍歷；或者圖示平衡二叉樹的形態(tài)。三、設(shè)計要求1、每人至少選擇一題完成，每道題每個班選擇人數(shù)不能超過5人。2、獨立思考，獨立完成：課程設(shè)計中各任務(wù)的設(shè)計和調(diào)試要求獨立完成，遇到問題可以討論，但不可以拷貝，不允許雷同。3、在處理每個題目時，要求從分析題目的需求入手，按設(shè)計抽象數(shù)據(jù)類型、構(gòu)思算法、通過類的設(shè)計實現(xiàn)

11、抽象數(shù)據(jù)類型、編制上機程序和上機調(diào)試等若干步驟完成題目，最終寫出完整的分析報告。前期準備工作完備與否直接影響到后序上機調(diào)試工作的效率。在程序設(shè)計階段應(yīng)盡量利用已有的標準函數(shù)，加大代碼的重用率。4、設(shè)計出的系統(tǒng)要有一個易于使用人機界面。5、源程序中應(yīng)對重要程序?qū)懗鲎⑨屨Z句四、應(yīng)提交的作品1. 設(shè)計報告（電子稿），文檔書寫格式可參看附錄。2. 源程序。五、提交方式及要求每個人以自己的“學號姓名”形式建立文件夾，每個人的文檔及源程序存放在自己的文件夾內(nèi)。答辯時拷貝給指導教師檢查、答辯。答辯結(jié)束后拷給學習委員，學習委員將全班的設(shè)計報告和程序收集齊后交給指導教師。六、時間安排第20周的星期一至星期五。時

12、間內(nèi)容星期一選定題目：明確題目要求、確定數(shù)據(jù)結(jié)構(gòu)、算法描述，準備測試數(shù)據(jù)等星期二至星期四上午完成要求問題并測試、歸檔星期四下午、星期五演示回答教師提問文檔及程序的整理并提交作品課程設(shè)計期間不遲到，不早退，有特殊情況要事先請假，并經(jīng)有關(guān)老師批準方能有效，無故缺席者作曠課處理。進入機房，應(yīng)遵守機房規(guī)定的各項制度。<附錄>課程設(shè)計課 程： 題 目： 專 業(yè)： 班 級： 座 號： 姓 名： 年 月 日實驗題目：求迷宮的最短路徑一、要解決的問題 這是實驗心理學中的一個經(jīng)典問題，心理學家把一只老鼠從一個無頂蓋的大盒子的入口處趕進迷宮。迷宮中設(shè)置很多隔壁，對前進方向形成了多處障礙，心理學家在迷宮

13、的唯一出口處放置了一塊奶酪，吸引老鼠在迷宮中尋找通路以達到出口。我們要解決的是如何找到了一條迷宮的最短路徑。二、算法基本思想描述： 要用到回溯的思想。從迷宮入口點出發(fā)，向四周搜索，記下所有一步能到達的坐標點；然后依次從這些點出發(fā)，再記下所有一步能到達的坐標點，.依此類推，直到到達迷宮的出口點為止，然后從迷宮出口點沿搜索路徑回溯。這樣就找到了一條迷宮的最短路徑，否則迷宮無路徑。由于先到達的點先搜索，故用先進先出的數(shù)據(jù)結(jié)構(gòu)隊列來保存已到達的坐標點。三、設(shè)計1. 數(shù)據(jù)結(jié)構(gòu)的設(shè)計 （1）迷宮的表示設(shè)迷宮為m行n列，利用mazemn來表示迷宮，mazemn=0或1，其中0表示通路，1表示不通。入口坐標（

14、1，1），出口坐標（m,n）.迷宮定義如下： #define m 6 #define n 8 int mazem+2n+2； （2）試探方向的表示 在迷宮中有8個方向可以試探，規(guī)定：從當前位置向前試探的方向為從正東開始沿順時針方向進行。為了簡化問題，將這8個方向的坐標增量放在一個結(jié)構(gòu)數(shù)組move8中。在move數(shù)組中，每個元素有兩個域組成，X：橫坐標增量；Y：縱坐標增量。序號 XY00111121031-140-15-1-16-107-11(x,y)(x-1,y)(x+1,y)(x-1,y+1)(x,y+1)(x+1,y+1)(x-1,y-1)(x,y-1)(x+1,y-1)Move數(shù)組定義如

15、下：typedef struct int x,y;item;item move8= 0,1, 1,1, 1,0, 1,-1,0,-1, -1,-1,-1,0,-1,1 ;（3）隊列的表示 在找到出口點之后，需要沿搜索路徑回溯，所以到達某點時，不僅要記下該點的坐標，還要記下該點的前驅(qū)。用一個結(jié)構(gòu)數(shù)組sqnum作為隊列的存儲空間。Sq的每一個結(jié)構(gòu)有三個域：x,y,pre,其中x，y分別為所到達的點的坐標，pre為前驅(qū)點的坐標。還設(shè)隊頭front和隊尾rear指針。 #define num 50typedef struct int x,y； int pre; SqType;SqType sqnum；

16、int front，rear；2. 算法的設(shè)計（1）求最短路徑的算法設(shè)計 初始狀態(tài)，隊列中只有一個元素sq1,記錄的是入口點的坐標（1，1），因為該點是出發(fā)點，因此沒有直接前驅(qū)點，pre域為-1，隊頭指針front的隊尾指針rear均指向它，此后搜索時都是以front所指點為搜索的出發(fā)點，即將該點的坐標及front所指點的位置入隊，這樣不但記下了到達點的坐標，還記下了它的前驅(qū)點。Front所指向點的8個方向搜索完畢后，則出隊，繼續(xù)對下一點搜索。搜索過程中遇到出口點則成功，搜索結(jié)束，打印出迷宮的最短路徑，算法結(jié)束；或者當前隊空，既沒有搜索點了，表明沒有路徑，算法也結(jié)束。（2）防止重復(fù)到達某點的考

17、慮 為避免發(fā)生死循環(huán)，當?shù)竭_某點（i，j）后，使mazeij置-1，以便區(qū)分未到達過的頂點。算法結(jié)束前可恢復(fù)原迷宮。（3）隊列頭、尾指針的指向 隊頭指針指向搜索的出發(fā)點，當找到一個可到達點，就入隊；當8個方位都搜索完畢，隊頭指針往后移一個（出隊，但原位置值依然存在，方便最后回溯）。 （4）模塊結(jié)構(gòu)及功能：主程序隊列初始化打印路徑入隊迷宮初始化求最短路經(jīng)出隊判隊空a) void main() /主程序b) viod init_maze(int) /迷宮的初始化c) void init_queue(SqType) /隊列的初始化d) int path(int,int) /求迷宮的最短路徑e) vo

18、id print_path(SqType,rear) /打印路徑f) void in_queue(SqType ,datatype) /入隊操作g) void out_queue(SqType) /出隊操作h) int empty_queue(SqType) /判隊空（5）主要模塊算法描述求迷宮最短路徑的算法描述：path(int maze,int move) 隊列頭、尾指針初始化（=-1）； 將入口點的前驅(qū)設(shè)置為-1，入隊； 將入口點設(shè)置為已走過； 將是否找到出口點信息found賦值為0（未找到）； while（未找到&&隊列非空） 隊頭指針后移指向當前搜索點，并將它賦值給x； for i=1 to 8 搜索x點的8個方向 if（找到一個可走點） 就將該點坐標及前驅(qū)值（front）入隊； 將該點設(shè)置為已走過； if（該點是出口點）found=1； if(找到) 回溯打印最短路徑； else 打印“該迷宮沒有路徑”; 四、源程序清單：（略）五、測試數(shù)據(jù)及測試結(jié)果： 例如：測試數(shù)據(jù)：mazem+2n+2=1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,1