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

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