數(shù)據(jù)結(jié)構(gòu)課設題目

1、 TOC o 1-5 h z HYPERLINK l bookmark1 o Current Document 選題一：迷宮與棧問題2 HYPERLINK l bookmark10 o Current Document 選題二：算術(shù)表達式與二叉樹3 HYPERLINK l bookmark23 o Current Document 選題三：銀行業(yè)務模擬與離散事件模擬4 HYPERLINK l bookmark34 o Current Document 選題四：文學研究助手與模式匹配算法KMP5 HYPERLINK l bookmark45 o Current Document 選題五：湖北汽車

2、工業(yè)學院校園導游咨詢與最短路徑6 HYPERLINK l bookmark57 o Current Document 選題六：B-樹與B+樹及其操作7 HYPERLINK l bookmark65 o Current Document 選題七：哈夫曼(Huffman)編/譯碼器8 HYPERLINK l bookmark78 o Current Document 選題八：內(nèi)部排序算法比較9 HYPERLINK l bookmark87 o Current Document 選題九：簡單行編輯程序10 HYPERLINK l bookmark101 o Current Document 選題十：

3、一元多項式計算11 HYPERLINK l bookmark118 o Current Document 選題十一：集合的交、并、差運算12 HYPERLINK l bookmark126 o Current Document 選題十二：動態(tài)查找表13 HYPERLINK l bookmark132 o Current Document 選題十三：學生成績管理14 HYPERLINK l bookmark138 o Current Document 選題十四：馬踏棋盤15 HYPERLINK l bookmark144 o Current Document 選題十五： joseph環(huán)16 HY

4、PERLINK l bookmark150 o Current Document 選題十六：最小生成樹17 HYPERLINK l bookmark156 o Current Document 選題十七：通訊錄管理18 HYPERLINK l bookmark170 o Current Document 選題十八：運動會分數(shù)統(tǒng)計19 HYPERLINK l bookmark180 o Current Document 選題十九：航班信息的查詢與檢索20 HYPERLINK l bookmark186 o Current Document 選題二十：哈希表應用21 HYPERLINK l boo

5、kmark192 o Current Document 選題二十一：拓撲排序和關鍵路徑22 HYPERLINK l bookmark198 o Current Document 選題二十二：學生搭配問題23 HYPERLINK l bookmark206 o Current Document 選題二十三：表達式求值24 HYPERLINK l bookmark215 o Current Document 選題二十四：宿舍管理查詢軟件25選題一：迷宮與棧問題【問題描述】以一個mXn的矩陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設計一個程序， 對任意設定的迷宮，求出一條從入口到出口的通路，或得

6、出沒有通路的結(jié)論?！救蝿找蟆?）首先實現(xiàn)一個以鏈表作存儲結(jié)構(gòu)的棧類型，然后編寫一個求解迷宮的非遞歸程序。 求得的通路以三元組（i，j，d）的形式輸出。其中：（i，j）指示迷宮中的一個坐標， d表示走到下一坐標的方向。如，對于下列數(shù)據(jù)的迷宮，輸出一條通路為：（1，1， 1），（1，2，2），（2，2，2），（3，2，3），（3，1，2），。2）編寫遞歸形式的算法，求得迷宮中所有可能的通路。3）以方陣形式輸出迷宮及其通路。【測試數(shù)據(jù)】迷宮的測試數(shù)據(jù)如下：左上角（0，1）為入口，右下角（8，9）為出口。入口出口10111111111001000101100100010110000110011011

7、10000110001000011010001001101110110111000000001111111111入口:0123456789出口選題二：算術(shù)表達式與二叉樹【問題描述】一個表達式和一棵二叉樹之間，存在著自然的對應關系。寫一個程序，實現(xiàn)基于二叉樹 表示的算術(shù)表達式的操作。【任務要求】假設算術(shù)表達式Expression內(nèi)可以含有變量(az)、常量(09)和二元運算符(+,-,*, /,人(乘冪)。實現(xiàn)以下操作：ReadExpre(E)以字符序列的形式輸入語法正確的前綴表達式并構(gòu)造表達式E。WriteExpre(E)用帶括弧的中綴表達式輸出表達式E。Assign(V,c)實現(xiàn)對變量V的賦

8、值(V=c),變量的初值為0。Value(E)對算術(shù)表達式E求值。CompoundExpr (P, E1, E2)-構(gòu)造一個新的復合表達式(E1) P (E2)【測試數(shù)據(jù)】分別輸入 0； a； -91； +a*bc； +*5M2*8x； +*3Ax3*2Ax2x6 并輸出。每當輸入一個表達式后，對其中的變量賦值，然后對表達式求值。選題三：銀行業(yè)務模擬與離散事件模擬【問題描述】假設某銀行有4個窗口對外接待客戶，從早晨銀行開門（開門9： 00am，關門5： 00pm） 起不斷有客戶進入銀行。由于每個窗口在某個時刻只能接待一個客戶，因此在客戶人數(shù)眾多 時需要在每個窗口前順次排隊，對于剛進入銀行的客戶

9、（建議：客戶進入時間使用隨機函數(shù) 產(chǎn)生），如果某個窗口的業(yè)務員正空閑，則可上前辦理業(yè)務；反之，若4個窗口均有窗戶所 占，他便會排在人數(shù)最少的隊伍后面。【任務要求】1）編制一個程序以模擬銀行的這種業(yè)務活動并計算一天中客戶在銀行逗留的平均時 間。2）建議有如下設置：a）客戶到達時間隨機產(chǎn)生，一天客戶的人數(shù)設定為100人。b）銀行業(yè)務員處理時間隨機產(chǎn)生，平均處理時間10分鐘。3）將一天的數(shù)據(jù)（包括業(yè)務員和客戶）以文件方式輸出。【測試數(shù)據(jù)】由隨機數(shù)產(chǎn)生器生成選題四：文學研究助手與模式匹配算法KMP【問題描述】文學研究人員需要統(tǒng)計某篇英文小說中某些形容詞的出現(xiàn)次數(shù)和位置。試寫一個實現(xiàn)這 -目標的文字統(tǒng)計

10、系統(tǒng)【任務要求】1）英文小說存于一個文本文件中。待統(tǒng)計的詞匯集合要一次輸入完畢，即統(tǒng)計工作必 須在程序的一次運行之后就全部完成。程序的輸出結(jié)果是每個詞的出現(xiàn)次數(shù)和出現(xiàn) 位置所在的行的行號，格式自行設計。待統(tǒng)計的“單詞”在文本串中不跨行出現(xiàn)， 它或者從行首開始，或者前置以一個空格符。2）模式匹配要基于KMP算法。3）推廣到更一般的模式集匹配問題，并設待查模式串可以跨行（提示：定義操作 GetAChar）。【測試數(shù)據(jù)】1）文本文件為testword.c2）彳寺統(tǒng)計的詞集：if、else、for、while、return、void、int、char、typedef、struct選題五：湖北汽車工業(yè)學

11、院校園導游咨詢與最短路徑【問題描述】1）從湖北汽車工業(yè)學院的平面圖中選取有代表性景點（10-15個），抽象成一個無向 帶權(quán)圖。以圖中頂點表示景點，邊上的權(quán)值表示兩地之間距離。2）本程序的目的是為用戶提供路徑咨詢。根據(jù)用戶指定的始點和終點輸出相應路徑， 或者根據(jù)用戶指定的景點輸出景點的信息?！救蝿找蟆?）從湖北汽車工業(yè)學院的平面圖中選取有代表性景點（10-15個），抽象成一個無向 帶權(quán)圖。以圖中頂點表示校內(nèi)各景點，存放景點名稱、代號、簡介等信息；以邊表 示路徑，存放路徑長度等信息。2）為來訪客人提供圖中任意景點相關信息的查詢。3）為來訪客人提供圖中任意景點的問路查詢，即查詢?nèi)我鈨蓚€景點之間的一

12、條最短的 簡單路徑。4）區(qū)分汽車線路與步行線路?！緶y試數(shù)據(jù)】湖北汽車工業(yè)學院導游圖（距離可估計）。選題六：8-樹與8+樹及其操作【問題描述】學習并研究B-樹與B+樹，并編寫演示它們操作的程序?！救蝿找蟆緽-樹構(gòu)建、查找、插入和刪除操作程序。B+樹構(gòu)建、查找、插入和刪除操作程序?！緶y試數(shù)據(jù)】選題七：哈夫曼（Huffman ）編/譯碼器【問題描述】利用哈夫曼編碼進行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。 但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)預先編碼，在接收端將傳來的數(shù)據(jù)進行 譯碼（復原）。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個完整的編/譯 碼系統(tǒng)

13、。試為這樣的信息收發(fā)站寫一個哈夫曼碼的編/譯碼系統(tǒng)。【任務要求】一個完整的系統(tǒng)應具有以下功能：1）I：初始化（Initialization）。從終端讀入字符集大小n，以及n個字符和n個權(quán)值， 建立哈夫曼樹，并將它存于文件hfmTree中。2）E：編碼（Encoding）。利用以建好的哈夫曼樹（如不在內(nèi)存，則從文件hfmTree中 讀入），對文件ToBeTran中的正文進行編碼，然后將結(jié)果存入文件CodeFile中。3）D：譯碼（Decoding）。利用已建好的哈夫曼樹將文件CodeFile中的代碼進行譯碼， 結(jié)果存入文件TextFile中。4）P：印代碼文件（Print）。將文件CodeFil

14、e以緊湊格式顯示在終端上，每行50個代 碼。同時將此字符形式的編碼文件寫入文件CodePrin中。5）T：印哈夫曼樹（Tree Printing）。將已在內(nèi)存中的哈夫曼樹以直觀的方式（樹或凹 入表形式）顯示在終端上，同時將此字符形式的哈夫曼樹寫入文件TreePrint中?！緶y試數(shù)據(jù)】1）利用教科書例6-2 （嚴蔚敏數(shù)據(jù)結(jié)構(gòu)P148）中的數(shù)據(jù)調(diào)試程序。2）用下表給出的字符集和頻度的實際統(tǒng)計數(shù)據(jù)建立哈夫曼樹，并實現(xiàn)以下報文的編碼和譯碼：“THIS PROGRAM IS MY FAVORITE字符頻度空格 186A64B13C22D32E103F21G15H47I57J 1K5L32M20字符NOP

15、QRSTUVWXYZ頻度5763151485180238181161選題八：內(nèi)部排序算法比較【問題描述】在教科書中，各種內(nèi)部排序算法的時間復雜度分析結(jié)果只給出了算法執(zhí)行時間的階次， 或大概執(zhí)行時間。試通過隨機數(shù)據(jù)比較各種算法的關鍵字比較次數(shù)和關鍵字移動次數(shù)，以取 得直觀感受?！救蝿找蟆?）對以下7種常用的內(nèi)部排序算法進行比較：冒泡排序、直接插入排序、簡單選擇排 序、希爾排序、堆排序、歸并排序、快速排序。2）待排序表的表長不小于100；其中的數(shù)據(jù)要用偽隨機數(shù)程序產(chǎn)生；至少要用5組不 同的輸入數(shù)據(jù)作比較；比較的指標為有關鍵字參加的比較次數(shù)和關鍵字的移動次數(shù)（關鍵字交換計為3次移動）。3）最后要對

16、結(jié)果作出簡單分析，包括對各組數(shù)據(jù)得出結(jié)果波動大小的解釋?！緶y試數(shù)據(jù)】由隨機數(shù)產(chǎn)生器生成選題九：簡單行編輯程序【問題描述】文本編輯器程序是利用計算機進行文字加工的基本軟件工具，實現(xiàn)對文本文件的插入、 刪除等修改操作。限制這些操作以行為單位進行的編輯程序稱為行編輯程序。被編輯的文本文件可能很大，全部讀入編輯程序的數(shù)據(jù)空間（內(nèi)存）的作法既不經(jīng)濟， 也不總能實現(xiàn)。一種解決辦法是逐段地編輯。任何時刻只把待編輯文件的一段放在內(nèi)存，即 為活區(qū)。試按照這種方法實現(xiàn)一個簡單的行編輯程序。設文件每行不超過320個字符，很少 超過80個字符。【任務要求】實現(xiàn)以下4條基本編輯命令：1）行插入：格式：i行號回車文本 回

17、車將文本插入活區(qū)中第 行號行之后。2）行刪除。格式：d行號1空格行號2回車刪除活區(qū)中第行號1（到第行號2行）。例如“d10”和“d10 14”3）活區(qū)切換。格式：n回車將活區(qū)寫入輸出文件，并從輸入文件中讀入下一段，作為新的活區(qū)。4）活區(qū)顯示。模式：p回車逐頁地（每頁20行）顯示活區(qū)內(nèi)容，每顯示一頁之后請用戶決定是繼續(xù)顯示 以后各頁（如果存在）。印出的每一行要前置行號和一個空格符，行號固定占 4位，增量為1。各條命令中的行號均須在活區(qū)中各行行號范圍之內(nèi)，只有插入命令的行號可以等于活區(qū) 第一行行號減1，表示插入當前屏幕中第一行之前，否則命令參數(shù)非法?！緶y試數(shù)據(jù)】自行設定，注意測試將活區(qū)刪空等特殊情

18、況。選題十：一元多項式計算【問題描述】能夠按照指數(shù)降序排列建立并輸出多項式；能夠完成兩個多項式的相加、相減，并將結(jié)果輸入；【任務要求】存儲結(jié)構(gòu)；多項式相加的基本過程的算法（可以使用程序流程圖）可以提出算法的改進方法；【測試數(shù)據(jù)】自行設定，注意邊界等特殊情況。選題十一：集合的交、并、差運算【問題描述】編制一個能演示執(zhí)行集合的交、并和差運算的程序?！救蝿找蟆?）集合元素用小寫英文字母，執(zhí)行各種操作應以對話方式執(zhí)行。2）算法要點：利用單鏈表表示集合；理解好三種運算的含義【測試數(shù)據(jù)】自行設定，注意邊界等特殊情況。選題十二：動態(tài)查找表【問題描述】利用二叉排序樹完成動態(tài)查找表的建立、指定關鍵字的查找、插

19、入與刪除指定關鍵字結(jié) 點?！救蝿找蟆克惴ㄝ斎耄褐付ㄒ唤M數(shù)據(jù)。算法輸出：顯示二叉排序樹的中序遍歷結(jié)果、查找成功與否的信息、插入和刪除后的中 序遍歷結(jié)果（排序結(jié)果）。算法要點：二叉排序樹建立方法、動態(tài)查找方法，對樹進行中序遍歷?！緶y試數(shù)據(jù)】自行設定，注意邊界等特殊情況。選題十三：學生成績管理【問題描述】本例對學生的成績管理做一個簡單的模擬，用菜單選擇方式完成下列功能：登記學生 成績；查詢學生成績；插入學生成績；刪除學生成績。【任務要求】算法輸入：操作要求，學生信息算法輸出：操作結(jié)果算法要點：把問題看成是對線性表的操作。將學生成績組織成順序表，則登記學生成績 即是建立順序表操作；查詢學生成績、插入

20、學生成績、刪除學生成績即是在順序表中進行查找、 插入和刪除操作?！緶y試數(shù)據(jù)】自行設定，注意邊界等特殊情況。選題十四：馬踏棋盤【問題描述】將馬隨機放在國際象棋的8* 8棋盤Bord8 II8的某個方格中，馬按走棋規(guī)則進行移動。 要求每個方格上只進入一次，走遍棋盤上全部64個方格?！救蝿找蟆烤幹品沁f歸程序，求出馬的行走路線，并按求出的行走路線，將數(shù)字1, 2, 64依 次填入一個8* 8的方陣，輸出之。測試數(shù)據(jù)：由讀者指定，可自行指定一個馬的初始位置。實現(xiàn)提示：每次在多個可走位置中選擇一個進行試探，其余未曾試探過的可走位置必 須用適當結(jié)構(gòu)妥善管理，以備試探失敗時的“回溯”（悔棋）使用?！緶y試數(shù)據(jù)

21、】自行設定，注意邊界等特殊情況。選題十五： joseph 環(huán)【問題描述】編號是1，2,，的n個人按照順時針方向圍坐一圈，每個人只有一個密碼（正整 數(shù)）。一開始任選一個正整數(shù)作為報數(shù)上限值m,從第一個仍開始順時針方向自1開始順序報 數(shù)，報到m時停止報數(shù)。報m的人出列，將他的密碼作為新的m值，從他在順時針方向的 下一個人開始重新從1報數(shù)，如此下去，直到所有人全部出列為止。設計一個程序來求出出 列順序?！救蝿找蟆坷脝蜗蜓h(huán)鏈表存儲結(jié)構(gòu)模擬此過程，按照出列的順序輸出各個人的編號。測試數(shù)據(jù)：m的初值為20，n=7 ,7個人的密碼依次為3，1，7，2，4，7，4，首先m =6,則正確的輸出是什么？要求

22、：輸入數(shù)據(jù)：建立輸入處理輸入數(shù)據(jù)，輸入m的初值，n，輸入每個人的密碼，建立單 循環(huán)鏈表。輸出形式：建立一個輸出函數(shù)，將正確的輸出序列【測試數(shù)據(jù)】自行設定，注意邊界等特殊情況。選題十六：最小生成樹【問題描述】在n個城市之間建設網(wǎng)絡，只需保證連通即可，求最經(jīng)濟的架設方法。對于圖，其生成樹中的邊也帶權(quán)，將生成樹各邊的權(quán)值總和稱為生成樹的權(quán)，并將權(quán) 值最小的生成樹稱為最小生成樹(Minimun Spanning Tree)，簡稱為MST。有兩種非常典型 的算法：Prim算法和kruskal算法。【任務要求】設計程序完成如下功能：對給定的網(wǎng)和起點，用PRIM算法和kruskal算法的基本思想 求解出所有

23、的最小生成樹。存儲結(jié)構(gòu)可自行選擇?！緶y試數(shù)據(jù)】自行設定，注意邊界等特殊情況。選題十七：通訊錄管理【問題描述】該設計采用菜單作為應用程序的主要界面，用控制語句來改變程序執(zhí)行的順序，控制語 句是實現(xiàn)結(jié)構(gòu)化程序設計的基礎。該設計的任務是利用一個簡單實用的菜單，通過菜單單項 進行選擇，實現(xiàn)和完成通訊錄管理中常用的幾個不同的功能。【任務要求】（1）菜單內(nèi)容1、通訊錄鏈表的建立2、通訊者結(jié)點的插入3、通訊者結(jié)點的查詢4、通訊者結(jié)點的刪除5、通訊錄鏈表的輸出0、退出管理系統(tǒng)請選擇05：（2）設計要求使用05來選擇菜單項，其他輸入則不起作用。（3）功能函數(shù)設計5個不同功能的算法實現(xiàn)編程題，目的是練習利用鏈表結(jié)

24、構(gòu)來解決實際應用問題的能 力，進一步理解和熟悉線形表的鏈式存儲結(jié)構(gòu)。【測試數(shù)據(jù)】自行設定，注意邊界等特殊情況。選題十八：運動會分數(shù)統(tǒng)計【問題描述】參加運動會有n個學校，學校編號為1n。比賽分成m個男子項目，和w個女子項 目。項目編號為男子1m，女子m+1m+w。不同的項目取前五名或前三名積分；取前 五名的積分分別為：7、5、3、2、1，前三名的積分分別為：5、3、2；哪些取前五名或前 三名由學生自己設定。(m=20,n=20)【任務要求】功能要求：.可以輸入各個項目的前三名或前五名的成績；.能統(tǒng)計各學?？偡郑?可以按學校編號、學?？偡帧⒛信畧F體總分排序輸出；.可以按學校編號查詢學校某個項目的情

25、況；可以按項目編號查詢?nèi)〉们叭蚯拔迕?的學校。規(guī)定：輸入數(shù)據(jù)形式和范圍：20以內(nèi)的整數(shù)(如果做得更好可以輸入學校的名稱，運 動項目的名稱)輸出形式：有中文提示，各學校分數(shù)為整形界面要求：有合理的提示，每個功能可以設立菜單，根據(jù)提示，可以完成相關的功能要 求。存儲結(jié)構(gòu)：學生自己根據(jù)系統(tǒng)功能要求自己設計，但是要求運動會的相關數(shù)據(jù)要存儲在 數(shù)據(jù)文件中。(數(shù)據(jù)文件的數(shù)據(jù)讀寫方法等相關內(nèi)容在c語言程序設計的書上，請自學解決) 請在最后的上交資料中指明你用到的存儲結(jié)構(gòu)；測試數(shù)據(jù)：要求使用1、全部合法數(shù)據(jù)；2、整體非法數(shù)據(jù)；3、局部非法數(shù)據(jù)。進行程序測 試，以保證程序的穩(wěn)定。測試數(shù)據(jù)及測試結(jié)果請在上交的資

26、料中寫明?！緶y試數(shù)據(jù)】自行設定，注意邊界等特殊情況。選題十九：航班信息的查詢與檢索【問題描述】該設計要求對飛機航班信息進行排序和查找?？砂春桨嗟暮桨嗵?、起點站、到達站、 起飛時間以及到達時間等信息進行查詢。【任務要求】對于本設計，可采用基數(shù)排序法對一組具有結(jié)構(gòu)特點的飛機航班號進行排序，利用二 分查找法對排好序的航班記錄按航班號實現(xiàn)快速查找，按其他次關鍵字的查找可采用最簡單 的順序查找方法進行，因此他們用得較少。每個航班記錄包括八項，分別是：航班號、起點站、終點站、班期、起飛時間、到達時 間、飛機型號以及票價等，假設航班信息表（8條記錄）航班號起點站終點站班期起飛時間到達時間機型票價CA1544

27、合肥北京1.2.4.510551240733960MU5341上海廣州每日14201615M901280CZ3869重慶深圳2.4.6085510357331010MU3682桂林南京2.3.4.6.720502215M901380HU1836上海北京每日094011207381250CZ3528成都廈門1.3.4.5.715101650CRJ1060MU4594昆明西安1.3.5.6101511403281160SC7425青島?？?.3.619202120DH41630其中航班號一項的格式為:K0K1K2K3K4K5CZ3869其中K0和K1的輸入值是航空公司的別稱，用兩個大寫字母標示，后

28、4位為航班號， 這種航班號關鍵字可分成兩段，即字母和數(shù)字。其余七項輸入內(nèi)容因為不涉及本設計的核心， 因此除了票價為數(shù)值型外，均定義為字符串即可?！緶y試數(shù)據(jù)】自行設定，注意邊界等特殊情況。選題二十：哈希表應用【問題描述】利用哈希表進行存儲?！救蝿找蟆咳蝿找螅横槍σ唤M數(shù)據(jù)進行初始化哈希表，可以進行顯示哈希表，查找元素，插入元 素，刪除元素，退出程序操作。設計思想：哈希函數(shù)用除留余數(shù)法構(gòu)造，用線性探測再散列處理沖突。設計目的：實現(xiàn)哈希表的綜合操作簡體中文控制臺界面：用戶可以進行創(chuàng)建哈希表，顯示哈希表，查找元素，插入元素， 刪除元素。顯示元素：顯示已經(jīng)創(chuàng)建的哈希表。查找元素：查找哈希表中的元素，分為查找成功和查找不成功。插入元素：在哈希表中，插入一個元素，分為插入成功和失敗。刪除元素：在已