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

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

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

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

4、商品越靠近棧頂。這樣就需要倒貨架，使生產(chǎn) 日期越近的越靠近棧底。請(qǐng)編寫程序模擬商品銷售，上架操作。（設(shè)有5種商品，每種商品至少有商品名和生產(chǎn)日期兩個(gè)屬性）題目5:模擬停車場(chǎng)管理的問題設(shè)停車場(chǎng)只有一個(gè)可停放幾輛汽車的狹長(zhǎng)通道，且只有一個(gè)大門可供汽車進(jìn)出。汽車在停車場(chǎng)按車輛到來的先后順序依次排列，若車場(chǎng)內(nèi)已停滿幾輛汽車，則后來的汽車只能在門外的便道上等候，一旦停車 場(chǎng)內(nèi)有車開走，則排在便道上的第一輛車即可進(jìn)入；當(dāng)停車場(chǎng)內(nèi)某輛車要離開時(shí)，由于停車場(chǎng)是狹長(zhǎng)的通 道，在它之后開入的車輛必須先退出車場(chǎng)為它讓路，待該輛車開出大門后，為它讓路的車輛在按原次序進(jìn) 入車場(chǎng)。每輛停放在車場(chǎng)的車在它離開停車場(chǎng)時(shí)必須按

5、它停留的時(shí)間長(zhǎng)短交納費(fèi)用。試為停車場(chǎng)編制按上 述要求進(jìn)行管理的模擬程序。在這里假設(shè)汽車不能從便道上開走。試設(shè)計(jì)一個(gè)停車場(chǎng)管理程序。實(shí)現(xiàn)提示：以棧模擬停車場(chǎng)，以隊(duì)列模擬車場(chǎng)外的便道，按照從終端讀入的輸入數(shù)據(jù)序列進(jìn)行模擬管理。 每一組輸入數(shù)據(jù)包括三個(gè)數(shù)據(jù)項(xiàng)：汽車“到達(dá)”或“離去”信息、汽車牌照號(hào)碼及到達(dá)或離去的時(shí)刻，例 如：（'a',1,5） 表示一號(hào)牌照車愛 5這個(gè)時(shí)刻到達(dá)，而（'d',5,20） 表示5號(hào)牌照車在20這個(gè)時(shí)刻離去，整 個(gè)程序可以在輸入信息為（'e',0,0） 時(shí)結(jié)束。對(duì)每一組輸入數(shù)據(jù)進(jìn)行操作后的輸出數(shù)據(jù)為：若是車輛到達(dá)， 則輸出汽

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

7、nitialization）。從終端讀入字符集大小 n,以及n個(gè)字符和n個(gè)權(quán)值，建立哈夫曼樹，（ 選做：并將它存于文件 hfmtree 中） 。并顯示出每個(gè)字符的編碼。（ 2 ）編碼（ encoding ） 。利用已建好的哈夫曼樹（選做：如不在內(nèi)存，則從文件htmtree 中讀入） ，對(duì)輸入的字符串文本（選做：對(duì)文件tobetran 中的正文）進(jìn)行編碼， （選做：然后將結(jié)果存入文件codefile中。 ）并顯示在屏幕上。（ 3 ）譯碼（ decoding ） 。利用已建好的哈夫曼樹將輸入的代碼進(jìn)行譯碼（選做：將文件 codefile 中的 代碼進(jìn)行譯碼，結(jié)果存入文件 textfile 中。 ）

8、 ，并顯示在屏幕上。（ 4 ）打印哈夫曼樹（ tree printing ） 。將已在內(nèi)存中的哈夫曼樹以直觀的方式顯示在屏幕上。題目7 ：校園導(dǎo)游程序設(shè)計(jì)一個(gè)校園導(dǎo)游程序?yàn)閬碓L的客人提供各種信息查詢服務(wù)。基本要求：（ 1 ） ） 設(shè)計(jì)學(xué)校的旗山校區(qū)北區(qū)校園平面圖，所含場(chǎng)所不少于 10 個(gè)。以圖中頂點(diǎn)表示校內(nèi)各場(chǎng)所，存放場(chǎng)所名稱、代號(hào)、簡(jiǎn)介等信息；以邊表示路徑，存放路徑長(zhǎng)度等相關(guān)信息。（ 2 ）為來訪客人提供圖中任意場(chǎng)所相關(guān)信息的查詢。（ 3 ）為來訪客人提供圖中任意場(chǎng)所的問路查詢，即查詢?nèi)我鈨蓚€(gè)景點(diǎn)之間的一條最短的簡(jiǎn)單路徑。題目8 ：內(nèi)部排序算法比較各種內(nèi)部排序算法的時(shí)間復(fù)雜度分析結(jié)果只給出了

9、算法執(zhí)行時(shí)間的階， 或大概執(zhí)行時(shí)間。 試通過隨機(jī)的數(shù)據(jù)比較各算法的關(guān)鍵字比較次數(shù)和關(guān)鍵字移動(dòng)次數(shù)，以取得直觀感受?；疽螅海?1 ） 從以下常用的內(nèi)部排序算法至少選取5 種進(jìn)行比較：直接插入排序；折半折入排序；希爾排序；起泡排序；快速排序；簡(jiǎn)單選擇排序；堆排序；歸并排序。（ 2 ） 待排序表的表長(zhǎng)為 20000 ；其中的數(shù)據(jù)要用偽隨機(jī)數(shù)產(chǎn)生程序產(chǎn)生；至少要用 5 組不同的輸入數(shù)據(jù)作比較；比較的指標(biāo)為有關(guān)鍵字參加的比較次數(shù)和關(guān)鍵字移動(dòng)次數(shù)（關(guān)鍵字交換計(jì)為 3 次移動(dòng)） 。題目9 ：哈希表設(shè)計(jì)針對(duì)同班同學(xué)信息設(shè)計(jì)一個(gè)通訊錄，學(xué)生信息有姓名，學(xué)號(hào)，電話號(hào)碼等。以學(xué)生姓名為關(guān)鍵字設(shè)計(jì)哈希表，并完成相

10、應(yīng)的建表和查表程序?；疽螅盒彰詽h語拼音形式，待填入哈希表的人名約 30 個(gè)，自行設(shè)計(jì)哈希函數(shù)，用線性探測(cè)再散列法或鏈地址法處理沖突；在查找的過程中給出比較的次數(shù)。完成按姓名查詢的操作。題目 10：平衡二叉樹二叉排序樹的查找效率取決于二叉樹的形態(tài)，而二叉排序樹的形態(tài)與生成樹時(shí)結(jié)點(diǎn)的插入次序有關(guān)，而結(jié)點(diǎn)的插入次序往往不能預(yù)先確定，這就需要在生成二叉排序樹的過程中進(jìn)行動(dòng)態(tài)調(diào)整，以構(gòu)造形態(tài)勻稱的平衡二叉樹。設(shè)計(jì)實(shí)現(xiàn)按輸入的序列構(gòu)造平衡二叉樹。要求：對(duì)構(gòu)造好的平衡二叉樹進(jìn)行先序和中序遍歷；或者圖示平衡二叉樹的形態(tài)。三、設(shè)計(jì)要求1、每人至少選擇一題完成，每道題每個(gè)班選擇人數(shù)不能超過5 人。2、獨(dú)立思

11、考，獨(dú)立完成：課程設(shè)計(jì)中各任務(wù)的設(shè)計(jì)和調(diào)試要求獨(dú)立完成，遇到問題可以討論，但不可以拷貝，不允許雷同。3、在處理每個(gè)題目時(shí)，要求從分析題目的需求入手，按設(shè)計(jì)抽象數(shù)據(jù)類型、構(gòu)思算法、通過類的設(shè)計(jì)實(shí)現(xiàn)抽象數(shù)據(jù)類型、編制上機(jī)程序和上機(jī)調(diào)試等若干步驟完成題目，最終寫出完整的分析報(bào)告。前期準(zhǔn)備工作完備與否直接影響到后序上機(jī)調(diào)試工作的效率。在程序設(shè)計(jì)階段應(yīng)盡量利用已有的標(biāo)準(zhǔn)函數(shù)，加大代碼的重用率。4、設(shè)計(jì)出的系統(tǒng)要有一個(gè)易于使用人機(jī)界面。5、源程序中應(yīng)對(duì)重要程序?qū)懗鲎⑨屨Z句四、應(yīng)提交的作品1. 設(shè)計(jì)報(bào)告（電子稿） ，文檔書寫格式可參看附錄。2. 源程序。五、提交方式及要求每個(gè)人以自己的“學(xué)號(hào)姓名”形式建立文

12、件夾，每個(gè)人的文檔及源程序存放在自己的文件夾內(nèi)。答辯時(shí)拷貝給指導(dǎo)教師檢查、答辯。答辯結(jié)束后拷給學(xué)習(xí)委員，學(xué)習(xí)委員將全班的設(shè)計(jì)報(bào)告和程序收集齊后交給指導(dǎo)教師。六、時(shí)間安排第20周的星期一至星期五。時(shí)間內(nèi)容星期一選定題目：明確題bw、確定數(shù)據(jù)結(jié)構(gòu)、算法描述， 準(zhǔn)備測(cè)試數(shù)據(jù)等星期二至星期四上午完成要求問題并測(cè)試、歸檔星期四卜午、星期五演示回答教師提問文檔及程序的整理并提交作品課程設(shè)計(jì)期間不遲到， 不早退，有特殊情況要事先請(qǐng)假，并經(jīng)有關(guān)老師批準(zhǔn)方能有效，無故缺席者作曠 課處理。進(jìn)入機(jī)房，應(yīng)遵守機(jī)房規(guī)定的各項(xiàng)制度。附錄課程設(shè)計(jì)課程：題目：專業(yè)：班級(jí)：座 號(hào)：姓名：實(shí)驗(yàn)題目：求迷宮的最短路徑一、要解決的問

13、題這是實(shí)驗(yàn)心理學(xué)中的一個(gè)經(jīng)典問題，心理學(xué)家把一只老鼠從一個(gè)無頂蓋的大盒子的入口 處趕進(jìn)迷宮。迷宮中設(shè)置很多隔壁，對(duì)前進(jìn)方向形成了多處障礙，心理學(xué)家在迷宮的唯一出 口處放置了一塊奶酪，吸引老鼠在迷宮中尋找通路以達(dá)到出口。我們要解決的是如何找到了 一條迷宮的最短路徑。二、算法基本思想描述：要用到回溯的思想。從迷宮入口點(diǎn)出發(fā)，向四周搜索，記下所有一步能到達(dá)的坐標(biāo)點(diǎn)；然后依次從這些點(diǎn)出發(fā)，再記下所有一步能到達(dá)的坐標(biāo)點(diǎn)，一依此類推，直到到達(dá)迷宮的出口點(diǎn)為止，然后從迷宮出口點(diǎn)沿搜索路徑回溯。這樣就找到了一條迷宮的最短路徑，否 則迷宮無路徑。由于先到達(dá)的點(diǎn)先搜索，故用先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)一一隊(duì)列來保存已到達(dá)的

14、 坐標(biāo)點(diǎn)。三、設(shè)計(jì)1.數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)(1)迷宮的表示設(shè)迷宮為m行n歹！j,利用mazemn來表示迷宮，mazemn=0或1,其中0表示通路，1 表示不通。入口坐標(biāo)(1, 1),出口坐標(biāo)(m,n).迷宮定義如下：#define m 6#define n 8int mazem+2n+2；(2)試探方向的表示在迷宮中有8個(gè)方向可以試探，規(guī)定：從當(dāng)前位置向前試探的方向?yàn)閺恼龞|開始沿順時(shí)針方向進(jìn)行。為了簡(jiǎn)化問題，將這 8個(gè)方向的坐標(biāo)增量放在一個(gè)結(jié)構(gòu)數(shù)組 move8中。在move 數(shù)組中，每個(gè)元素有兩個(gè)域組成，x：橫坐標(biāo)增量；y:縱坐標(biāo)增量。(x-1,y-1)(x,y-11)(x+1,y)序號(hào)xy0011

15、1121031p -140-15-1p -16-107-11move數(shù)組定義如下：typedef structint x,y;item;item move8= 0,1, 1,1, 1,0, 1,-1,0,-1,-1,-1,-1,0,-1,1 ;(3)隊(duì)列的表示在找到出口點(diǎn)之后，需要沿搜索路徑回溯，所以到達(dá)某點(diǎn)時(shí)，不僅要記下該點(diǎn)的坐標(biāo)，還要記下該點(diǎn)的前驅(qū)。用一個(gè)結(jié)構(gòu)數(shù)組sqnum作為隊(duì)列的存儲(chǔ)空間。sq的每一個(gè)結(jié)構(gòu)有三個(gè)域：x,y,pre,其中x,y分別為所到達(dá)的點(diǎn)的坐標(biāo)，pre為前驅(qū)點(diǎn)的坐標(biāo)。還設(shè)隊(duì)頭front 和隊(duì)尾rear指針。#define num 50typedef structint

16、 x,y ；int pre;sqtype;sqtype sqnum；int front , rear ；2.算法的設(shè)計(jì)(1)求最短路徑的算法設(shè)計(jì)1 2 3 4 5 6 781234560、0t”1011011 0 06) ( 5, 6)7)(6, 5)(4 ,6 , 4)初始狀態(tài)，隊(duì)列中只有一個(gè)元素 sq1,記錄的是入口點(diǎn)的坐標(biāo)(1, 1),因?yàn)樵擖c(diǎn)是出 發(fā)點(diǎn)，因此沒有直接前驅(qū)點(diǎn)，pre域?yàn)?1,隊(duì)頭指針front的隊(duì)尾指針rear均指向它，此后 搜索時(shí)都是以front所指點(diǎn)為搜索的出發(fā)點(diǎn)，即將該點(diǎn)的坐標(biāo)及front所指點(diǎn)的位置入隊(duì)，這樣不但記下了到達(dá)點(diǎn)的坐標(biāo)，還記下了它的前驅(qū)點(diǎn)。front所

17、指向點(diǎn)的8個(gè)方向搜索完畢后，則出隊(duì)，繼續(xù)對(duì)下一點(diǎn)搜索。搜索過程中遇到出口點(diǎn)則成功，搜索結(jié)束，打印出迷宮的 最短路徑，算法結(jié)束；或者當(dāng)前隊(duì)空，既沒有搜索點(diǎn)了，表明沒有路徑，算法也結(jié)束(2)防止重復(fù)到達(dá)某點(diǎn)的考慮為避免發(fā)生死循環(huán)，當(dāng)?shù)竭_(dá)某點(diǎn)(i , j )后，使maze皿置-1 ,以便區(qū)分未到達(dá)過的 頂點(diǎn)。算法結(jié)束前可恢復(fù)原迷宮。(3)隊(duì)列頭、尾指針的指向隊(duì)頭指針指向搜索的出發(fā)點(diǎn)，當(dāng)找到一個(gè)可到達(dá)點(diǎn)，就入隊(duì)；當(dāng)8個(gè)方位都搜索完畢，隊(duì)頭指針往后移一個(gè)(出隊(duì)，但原位置值依然存在，方便最后回溯)。(4)模塊結(jié)構(gòu)及功能： 主程序隊(duì)列初始化迷宮初始化求最短路經(jīng)打印路徑出隊(duì)判隊(duì)空a)void main()/主

18、程序b)viod init_maze(int)/迷宮的初始化c)void init_queue(sqtype)/隊(duì)列的初始化d)int path(int,int)/求迷宮的最短路徑e)void print_path(sqtype,rear) /打印路徑f)void in_queue(sqtype ,datatype) /入隊(duì)操作g)void out_queue(sqtype)/出隊(duì)操作h)int empty_queue(sqtype)/判隊(duì)空5)主要模塊算法描述求迷宮最短路徑的算法描述：path(int maze,int move)隊(duì)列頭、尾指針初始化(=-1);將入口點(diǎn)的前驅(qū)設(shè)置為 -1 ，

19、入隊(duì)；將入口點(diǎn)設(shè)置為已走過；將是否找到出口點(diǎn)信息 found 賦值為 0(未找到) ； while (未找到&&隊(duì)列非空) 隊(duì)頭指針后移指向當(dāng)前搜索點(diǎn)，并將它賦值給x；for i=1 to 8搜索 x 點(diǎn)的 8 個(gè)方向if (找到一個(gè)可走點(diǎn))就將該點(diǎn)坐標(biāo)及前驅(qū)值( front )入隊(duì)；將該點(diǎn)設(shè)置為已走過；if (該點(diǎn)是出口點(diǎn)) found=1 ； if( 找到 ) 回溯打印最短路徑；else 打印“該迷宮沒有路徑”;四、源程序清單： (略)五、測(cè)試數(shù)據(jù)及測(cè)試結(jié)果：例如：測(cè)試數(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