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

實(shí)驗(yàn)一實(shí)驗(yàn)四任選一題；實(shí)驗(yàn)五實(shí)驗(yàn)九任選一題。實(shí)驗(yàn)一運(yùn)動會分?jǐn)?shù)統(tǒng)計(jì)實(shí)驗(yàn)?zāi)康模?)熟練掌握線性表的兩種存儲方式(2)掌握鏈表的操作和應(yīng)用。(3)掌握指針、結(jié)構(gòu)體的應(yīng)用()按照不同的學(xué)校，不同項(xiàng)目和不同的名次要求，產(chǎn)生各學(xué)校的成績單、團(tuán)體總分報(bào)表。實(shí)驗(yàn)內(nèi)容：【問題描述】參加運(yùn)動會的個(gè)學(xué)校編號為。比賽分成m個(gè)男子項(xiàng)目和w個(gè)女子項(xiàng)目，項(xiàng)目編號分別為和ni++mwo由于各項(xiàng)目參加人數(shù)差別較大，有些項(xiàng)目取前五名，得分順序?yàn)椋?,2,；還有些項(xiàng)目只取前三名，得分順序?yàn)椋?,2。寫一個(gè)統(tǒng)計(jì)程序產(chǎn)生各種成績單和得分報(bào)表。【基本要求】產(chǎn)生各學(xué)校的成績單，內(nèi)容包括各校所取得的每項(xiàng)成績的項(xiàng)目號、名次(成績)、姓名和得分；產(chǎn)生團(tuán)體總分報(bào)表，內(nèi)容包括校號、男子團(tuán)體總分、女子團(tuán)體總分和團(tuán)體總分?！緶y試數(shù)據(jù)】對于=,m=3,w=2,編號為奇數(shù)的項(xiàng)目取前五名，編號為偶數(shù)的項(xiàng)目取前三名，設(shè)計(jì)一組實(shí)例數(shù)據(jù)?！緦?shí)現(xiàn)提示】可以假設(shè)mW20,m<30,w<20,姓名長度不超過20個(gè)字符。每一個(gè)項(xiàng)目結(jié)束時(shí)，將其編號、類型符(區(qū)分取前五名還是前三名)輸入，并按名次順序輸入運(yùn)動員姓名、校名(和成績)?！具x作內(nèi)容】允許用戶指定某些項(xiàng)目可采取其他名次取法。產(chǎn)生多種例如種不同的方案，并使方案之間的差異盡可能地大。實(shí)驗(yàn)九全國交通咨詢摹擬實(shí)驗(yàn)?zāi)康?)熟練掌握圖的創(chuàng)建及遍歷基本操作算法。()熟練掌握最短路徑算法。()利用圖的基本操作及求最短路徑等方法，設(shè)計(jì)一個(gè)全國城市間的交通咨詢程序，為旅客提供兩種或者三種最優(yōu)先決策的交通咨詢。實(shí)驗(yàn)內(nèi)容【問題描述】出于不同目的的旅客對交通工具有不同的要求。例如，因公出差的旅客希翼在旅途中的時(shí)間盡可能短，出門旅游的旅客則期望旅費(fèi)盡可能省，而老年旅客則要求中轉(zhuǎn)次數(shù)至少。編制一個(gè)全國城市間的交通咨詢程序，為旅客提供兩種或者三種最優(yōu)先決策的交通咨詢?！净疽蟆刻峁Τ鞘行畔⑦M(jìn)行編輯如：添加或者刪除的功能。城市之間有兩種交通工具：火車和飛機(jī)。提供對列車時(shí)刻表和飛機(jī)航班進(jìn)行編輯增設(shè)或者刪除的功能。提供兩種最優(yōu)決策：最快到達(dá)或者最省錢到達(dá)。全程只考慮一種交通工具。旅途中耗費(fèi)的總時(shí)間應(yīng)該包括中轉(zhuǎn)站的等候時(shí)間。咨詢以用戶和計(jì)算機(jī)的對話方式進(jìn)行。由用戶輸入起始站、終點(diǎn)站、最優(yōu)決策原則和交通工具，輸出信息：最快需要多長期才干到達(dá)或者至少需要多少旅費(fèi)才干到達(dá)，并詳細(xì)說明挨次于何時(shí)乘坐哪一趟列車或者哪一次班機(jī)到何地?！緶y試數(shù)據(jù)】參考下圖所示的全國交通圖，自行設(shè)計(jì)列車時(shí)刻表和飛機(jī)航班?！緦?shí)現(xiàn)提示】對全國城市交通圖和列車時(shí)刻表及飛機(jī)航班表的編輯，應(yīng)該提供文件形式輸入和鍵盤輸入兩種方式。飛機(jī)航班表的信息應(yīng)包括：起始站的出發(fā)時(shí)間、終點(diǎn)站的到達(dá)時(shí)間和票價(jià)；列車時(shí)刻表則需根據(jù)交通圖給出各個(gè)路段的詳細(xì)信息，例如：基于教科書節(jié)圖 的交通圖，對從北京到上海的火車，需給出北京至天津、天津至徐州及徐州至上海各段的出發(fā)時(shí)間、到達(dá)時(shí)間及票價(jià)等信息?！具x作內(nèi)容】增加旅途中轉(zhuǎn)次數(shù)至少的最優(yōu)先決策。實(shí)驗(yàn)二停車場管理實(shí)驗(yàn)?zāi)康模海ǎ┦炀氄莆諚ｍ槾婧玩湸鎯煞N存儲方式。（）掌握棧的基本操作及應(yīng)用。（）以棧摹擬停車場，以隊(duì)列摹擬車場外的便道，按照從終端讀入的輸入數(shù)據(jù)序列進(jìn)行摹擬管理。實(shí)驗(yàn)內(nèi)容：【問題描述】設(shè)停車場是一個(gè)可停放輛汽車的長通道，且惟獨(dú)一個(gè)大門可供汽車進(jìn)出。汽車在停車場內(nèi)按車輛到達(dá)時(shí)間的先后順序，挨次由北向南羅列（大門在最南端，最先到達(dá)的第一輛車信放在車場的最北端），若車場內(nèi)已停滿輛汽車，則后來的汽車只能在門外的便道上等候，一旦有車開走，則排在便道上的第一輛車即可開入；當(dāng)停車場內(nèi)某輛車要離開時(shí)，在它之后進(jìn)入的車輛必須先退出車場為它讓路，待該輛車開出大門外，其他車輛再按原次序進(jìn)入車場院，每輛停放在車場的車在它離開停車場時(shí)必須按它停留的時(shí)間長短交納費(fèi)用。試為停車場編制按上述要求進(jìn)行管理的摹擬程序。【基本要求】以棧摹擬停車場，以隊(duì)列摹擬車場外的便道，按照從終端讀入的輸入數(shù)據(jù)序列進(jìn)行摹擬管理。每一組輸入數(shù)據(jù)包括三個(gè)數(shù)據(jù)項(xiàng)：汽車“到達(dá)”或者“離去”信息、汽車牌照號碼以及到達(dá)或者離去的時(shí)刻。對每一組輸入數(shù)據(jù)進(jìn)行操作后的輸出信息為：若是車輛到達(dá)，則輸出汽車在停車場內(nèi)或者便道上的停車位置；若是車輛離去，則輸出汽車在停車場內(nèi)停留的時(shí)間和應(yīng)交納的費(fèi)用（在便道上停留的時(shí)間不收費(fèi)）。棧以順序結(jié)構(gòu)實(shí)現(xiàn)，隊(duì)列以鏈表結(jié)構(gòu)實(shí)現(xiàn)?！緶y試數(shù)據(jù)】設(shè)，輸入數(shù)據(jù)為：，，，（，，），（，，），（，，），（，，。其中：表示到達(dá)（ ）;表示離去（ ）；表示輸入結(jié)束（）o【實(shí)現(xiàn)提示】需另設(shè)一個(gè)棧，暫時(shí)停放為給要離去的汽車讓路而從停車場退出來的汽車，也用順序存儲結(jié)構(gòu)實(shí)現(xiàn)。輸入數(shù)據(jù)按到達(dá)或者離去的時(shí)刻有序。棧中每一個(gè)元素表示一輛汽車,包含兩個(gè)數(shù)據(jù)項(xiàng)：汽車的牌照號碼和進(jìn)入停車場的時(shí)刻?！具x作內(nèi)容】（） 兩個(gè)棧共享空間，思量應(yīng)開辟數(shù)組的空間是多少？（） 汽車可有不同種類，則他們的占地面積不同收費(fèi)標(biāo)準(zhǔn)也不同，如輛客車和輛小汽車的占地面積相同， 輛十輪卡車占地面積相當(dāng)于輛小汽車的占地面積。（） 汽車可以直接從便道開走，此時(shí)排在它前面的汽車要先開走讓路，然后再挨次排到隊(duì)尾。（） 停放在便道上的汽車也收費(fèi)，收費(fèi)標(biāo)準(zhǔn)比停放在停車場的車低，請思量如何修改結(jié)構(gòu)以滿足這種要求。實(shí)驗(yàn)三病人看病摹擬程序?qū)嶒?yàn)?zāi)康模?)熟練掌握隊(duì)列順存和鏈存兩種存儲方式。()掌握隊(duì)列的基本操作及應(yīng)用。()以隊(duì)列摹擬病人排隊(duì)，實(shí)現(xiàn)病人看病系統(tǒng)。實(shí)驗(yàn)內(nèi)容：【問題描述】摹擬病人到醫(yī)院看病，選擇看病的診室排隊(duì)看醫(yī)生的情況。在病人排隊(duì)過程中，主要重復(fù)兩件事：()病人到達(dá)診室，將病歷本交給護(hù)士，排到等待隊(duì)列中候診。()護(hù)士從等待隊(duì)列中取出下一位病人的病歷，該病人進(jìn)入診室就診【基本要求】要求摹擬病人等待就診這一過程。程序采用菜單方式，其選項(xiàng)及功能說明如下：()顯示可選擇的各診室。()排隊(duì)一一輸入排隊(duì)病人的病歷號，加入到某診室病人排隊(duì)隊(duì)列中。()就診一一該診室病人排隊(duì)隊(duì)列中最前面的病人就診，并將其從隊(duì)列中刪除。()查看各診室排隊(duì)一一從隊(duì)首到隊(duì)尾列出所有的該診室排隊(duì)病人的病歷號。()再也不排隊(duì)，余下挨次就診一一從隊(duì)首到隊(duì)尾列出所有的排隊(duì)病人的病歷號及就診診室，并退出運(yùn)行。()下班一一退出運(yùn)行?！緦?shí)現(xiàn)提示】采用鏈?zhǔn)疥?duì)列摹擬病人去醫(yī)院看病的過程。實(shí)驗(yàn)四航空客運(yùn)訂票系統(tǒng)實(shí)驗(yàn)?zāi)康模?)熟練掌握線性表基本操作及應(yīng)用。()熟練掌握隊(duì)列基本操作及應(yīng)用。()利用線性表和隊(duì)列實(shí)現(xiàn)航空客運(yùn)訂票系統(tǒng)。二、實(shí)驗(yàn)內(nèi)容：【問題描述】航空客運(yùn)訂票的業(yè)務(wù)活動包括；查詢航線、客票預(yù)訂和辦理退票等。試設(shè)計(jì)一個(gè)航空客運(yùn)訂票系統(tǒng)，以使上述業(yè)務(wù)可以借助計(jì)算機(jī)來完成。【基本要求】()每條航線所涉及的信息有：終點(diǎn)站名、航班名、飛機(jī)號、飛行周日(星期幾)、乘員定額、余票量、已訂票的客戶名單(包括姓名、訂票量、艙位等級，或者)以及等候替補(bǔ)的客戶名單(包括姓名、所需票量)；()作為示意系統(tǒng)，全部數(shù)據(jù)可以只放在內(nèi)存中；()系統(tǒng)能實(shí)現(xiàn)的操作和功能如下：①查詢航線：根據(jù)旅客提出的終點(diǎn)站名輸出下列信息：航班號、飛機(jī)號、星期兒飛行，最近一天航班的日期和余票額；②承辦訂票業(yè)務(wù)：根據(jù)客戶提出的要求(航班號、訂票數(shù)額)查詢該航班票額情況，若尚有余票，則為客戶辦理訂票手續(xù)，輸出坐位號；若已滿員或者余票額少于訂票額，則需重新問詢客戶要求。若需要，可登記排隊(duì)候補(bǔ)；③承辦退票業(yè)務(wù)：根據(jù)客戶提供的情況(日期、航班)，為客戶辦理退票手續(xù)，然后查詢該航班是否有人排隊(duì)候補(bǔ)，首先問詢排在第一的客戶，若所退票額能滿足客戶的要求，則為客戶辦理訂票手續(xù)，否則挨次問詢其他排隊(duì)候補(bǔ)的客戶?！緶y試數(shù)據(jù)】自行指定?！緦?shí)現(xiàn)提示】兩個(gè)客戶名單可分別由線性表和隊(duì)列實(shí)現(xiàn)。為查找方便，已訂票客戶的線性表應(yīng)按客戶姓名有序，并且為了插入和刪除方便，應(yīng)以鏈表作為存儲結(jié)構(gòu)。由于預(yù)約人數(shù)無法估計(jì)，隊(duì)列也應(yīng)以鏈表作存儲結(jié)構(gòu)。整個(gè)系統(tǒng)需匯總各條航線的情況登錄在一張線性表上，由于航線基本不變，可采用順序存儲結(jié)構(gòu)，并按航班有序或者按終點(diǎn)站名有序。每條航線是這張表上的一個(gè)記錄，包含上述個(gè)域、其中乘員名單域?yàn)橹赶虺藛T名單鏈表的頭指針，等候替補(bǔ)的客戶名單域?yàn)榉謩e指向隊(duì)頭和隊(duì)尾的指針?！具x作內(nèi)容】當(dāng)客戶訂票要求不能滿足時(shí)，系統(tǒng)可向客戶提供到達(dá)同一目的地的其他航線情況。還可充分發(fā)揮自己的想象力，增加你的系統(tǒng)的功能和其他服務(wù)項(xiàng)目。實(shí)驗(yàn)五文學(xué)研究助手一、 實(shí)驗(yàn)?zāi)康?) 熟練掌握串的基本操作及應(yīng)用。() 熟練掌握串的匹配操作算法。() 基于串的存儲和操作，實(shí)現(xiàn)對英文文章文字統(tǒng)計(jì)系統(tǒng)。實(shí)驗(yàn)內(nèi)容【問題描述】文學(xué)研究人員需要統(tǒng)計(jì)某篇英文小說中某些形容詞的浮現(xiàn)次數(shù)和位置。試寫一個(gè)實(shí)現(xiàn)這一目標(biāo)的文字統(tǒng)計(jì)系統(tǒng)，稱為“文學(xué)研究助手”?！净疽蟆坑⑽男≌f存于一個(gè)文本文件中。等待統(tǒng)計(jì)的詞匯集合要一次輸入完畢，即統(tǒng)計(jì)工作必須在程序的一次運(yùn)行之后就全部完成。程序的輸出結(jié)果是每一個(gè)詞的浮現(xiàn)次數(shù)和浮現(xiàn)位置所在行的行號，格式自行設(shè)計(jì)?！緶y試數(shù)據(jù)】以你的源程序摹擬英文小說， 語言的保留字集作為待統(tǒng)計(jì)的詞匯集?！緦?shí)現(xiàn)提示】約定小說中的詞匯一律不跨行。這樣。每讀入一行，就統(tǒng)計(jì)每一個(gè)詞在這行中的浮現(xiàn)次數(shù)。浮現(xiàn)位置所在行的行號可以用鏈表存儲。若某行中了現(xiàn)了不止一次，不必存多個(gè)相同的行號。如果讀者希翼達(dá)到選做部份()和()所提出的要求，則首先應(yīng)把算法改寫成如下的等價(jià)形式，再將它推廣到多個(gè)模式的情形。??()9或者每次進(jìn)入循環(huán)體， 只增加一次【選作內(nèi)容】()模式匹配要基于 算法。()整個(gè)統(tǒng)計(jì)過程中只對小說文字掃描一遍以提高效率。()假設(shè)小說中的每一個(gè)單詞或者從行首開始，或者前置一個(gè)空格符。利用單詞匹配特點(diǎn)另寫一個(gè)高效的統(tǒng)計(jì)程序，與 算法統(tǒng)計(jì)程序進(jìn)行效率比較。)o()推廣到更普通的模式集匹配問題，并設(shè)待查模式串并可以跨行(提示：定義操作)o實(shí)驗(yàn)六哈夫曼編譯碼器【問題描述】利用哈夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。但是，這要求在發(fā)送端通過一個(gè)編碼系統(tǒng)對待傳輸數(shù)據(jù)預(yù)先編碼，在接收端將傳來的數(shù)據(jù)進(jìn)行譯碼。對于雙工信道(即可以雙向傳輸信息的信道)，每端都需要一個(gè)完整的編譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫一個(gè)哈夫曼的編譯碼系統(tǒng)?！净疽蟆恳粋€(gè)完整的系統(tǒng)應(yīng)具有以下功能:():初始化()o從終端讀入字符集大小，以及個(gè)字符和個(gè)權(quán)值，建立哈夫曼柯():初始化()o從終端讀入字符集大小，以及個(gè)字符和個(gè)權(quán)值，建立哈夫曼柯.，并將它存于文件中。():編碼(中讀入)，對文件():譯碼(譯碼，結(jié)果存入文件():編碼(中讀入)，對文件():譯碼(譯碼，結(jié)果存入文件)o利用以建好的哈夫曼樹(如不在內(nèi)存，則從文件中的正文進(jìn)行編碼，然后將結(jié)果存入文件 中。)。利用已建好的哈夫曼樹將文件 中的代碼進(jìn)行中。()：印代碼文件( )o()：印代碼文件( )o將文件以緊湊格式顯示在終端上，每行個(gè)代碼。同時(shí)將此字符形式的編碼文件寫入文件中。():印哈夫曼樹()。將已在內(nèi)存中的哈夫曼樹以直觀的方式(樹個(gè)代碼。同時(shí)將此字符形式的編碼文件寫入文件中。():印哈夫曼樹()。將已在內(nèi)存中的哈夫曼樹以直觀的方式(樹或者凹入表形式)顯示在終端上，同時(shí)將此字符形式的哈夫曼樹寫入文件 中。【測試數(shù)據(jù)】利用下表給出的字符集和頻度的實(shí)際統(tǒng)計(jì)數(shù)據(jù)建立哈夫曼樹，并實(shí)現(xiàn)以下報(bào)文的編碼和譯碼:字符頻度字符頻度【實(shí)現(xiàn)提示】()編碼結(jié)果以文本方式存儲在文件 中。()用戶界面可以設(shè)計(jì)為“菜單”方式：顯示上述功能符號，再加之“”，表示退出運(yùn)行。請用戶輸入一個(gè)選擇功能符。此功能執(zhí)行完畢后再顯示此菜單，直至某此用戶選擇了“"為止。()在程序的一次執(zhí)行過程中，第一次執(zhí)行，或者命令之后，哈夫曼樹已經(jīng)在內(nèi)存了，不必再讀入。每次執(zhí)行中不一定執(zhí)行命令，因?yàn)槲募?可能早已建好?！具x做內(nèi)容】()上述文件 中的每一個(gè)“”或者"”實(shí)際上占用了一個(gè)字節(jié)的空間,只起到示意或者摹擬的作用。為最大限度地利用碼點(diǎn)存儲能力，試改寫你的系統(tǒng)，將編碼結(jié)果以二進(jìn)制形式存放在文件 中。()修改你的系統(tǒng)，實(shí)現(xiàn)對你的系統(tǒng)的源程序的編碼和譯碼。()實(shí)現(xiàn)各個(gè)轉(zhuǎn)換操作的源目文件，均由用戶在選擇此操作時(shí)指定。實(shí)驗(yàn)七校園導(dǎo)游咨詢實(shí)驗(yàn)?zāi)康?) 熟練掌握圖的創(chuàng)建及遍歷基本操作算法。() 熟練掌握最短路徑算法。() 利用圖的遍歷和最短路徑求解技術(shù)，設(shè)計(jì)一個(gè)校園導(dǎo)游程序，為來訪的客人提供各種信息查詢服務(wù)。實(shí)驗(yàn)內(nèi)容【問題描述】設(shè)計(jì)一個(gè)校園導(dǎo)游程序，為來訪的客人提供各種信息查詢服務(wù)?！净疽蟆吭O(shè)計(jì)你所在學(xué)校的校園平面圖，所含景點(diǎn)不少于個(gè)。以圖中頂點(diǎn)表示校內(nèi)各景點(diǎn)，存放景點(diǎn)名稱、代號、簡介等信息；以邊表示路徑，存放路徑長度等相關(guān)信息。為來訪客人提供圖中任意景點(diǎn)相關(guān)信息的查詢。為來訪客人提供圖中任意景點(diǎn)的問路查詢，即查詢?nèi)我鈨蓚€(gè)景點(diǎn)之間的一個(gè)最短的簡單路徑?！緶y試數(shù)據(jù)】根據(jù)實(shí)際情況指定?！緦?shí)現(xiàn)提示】普通情況下，校園的道路是雙向通行的，可設(shè)校園平面圖是一個(gè)無向網(wǎng)。頂點(diǎn)和邊均含有相關(guān)信息?！具x作內(nèi)容】求校園圖的關(guān)節(jié)點(diǎn)。提供圖中任意景點(diǎn)問路查詢，即求任意兩個(gè)景點(diǎn)之間的所有路徑。提供校園圖中多個(gè)景點(diǎn)的最佳訪問路線查詢，即求途經(jīng)這多個(gè)景點(diǎn)的最佳短路徑。校園導(dǎo)游圖的景點(diǎn)和道路的修改擴(kuò)充功能。擴(kuò)充道路信息，如道路類別車道、人行道等、沿途景色等級，以至可按客人所需分別查詢?nèi)诵新窂交蛘哕囆新窂交蛘哂^景路徑等。擴(kuò)充每一個(gè)景點(diǎn)的鄰接景點(diǎn)的方向等信息，使得路徑查詢結(jié)果能提供詳盡的導(dǎo)向信息。實(shí)現(xiàn)校園導(dǎo)游圖的仿真界面。實(shí)驗(yàn)八教學(xué)計(jì)劃編制問題實(shí)驗(yàn)?zāi)康?) 熟練掌握圖的創(chuàng)建及遍歷基本操作算法。() 熟練掌握拓樸排序算法。() 利用圖的基本操作及全羅列產(chǎn)生技術(shù)摹擬教學(xué)計(jì)劃編制程序。實(shí)驗(yàn)內(nèi)容【問題描述】大學(xué)的每一個(gè)專業(yè)都要制定教學(xué)