迷宮與棧問題等-數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(15級)

1、<p>　　選題一：迷宮與棧問題</p><p><b>　　【問題描述】</b></p><p>　　以一個mXn的長方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設(shè)計一個程序，對任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結(jié)論。</p><p><b>　　【實現(xiàn)提示】</b></p&

2、gt;<p>　　首先實現(xiàn)一個以鏈表作存儲結(jié)構(gòu)的棧類型，然后編寫一個求解迷宮的非遞歸程序。求得的通路以三元組（i，j，d）的形式輸出。其中：（i，j）指示迷宮中的一個坐標(biāo)，d表示走到下一坐標(biāo)的方向。如，對于下列數(shù)據(jù)的迷宮，輸出一條通路為：（1，1，1），（1，2，2），（2，2，2），（3，2，3），（3，1，2），…。</p><p>　　編寫遞歸形式的算法，求得迷宮中所有可能的通路。</p

3、><p>　　以方陣形式輸出迷宮及其通路。</p><p><b>　　【測試數(shù)據(jù)】</b></p><p>　　迷宮的測試數(shù)據(jù)如下：左上角（0，1）為入口，右下角（8，9）為出口。</p><p>　　選題二：算術(shù)表達式與二叉樹</p><p><b>　　【問題描述】</b>

4、</p><p>　　一個表達式和一棵二叉樹之間，存在著自然的對應(yīng)關(guān)系。寫一個程序，實現(xiàn)基于二叉樹表示的算術(shù)表達式的操作。</p><p><b>　　【實現(xiàn)提示】</b></p><p>　　假設(shè)算術(shù)表達式Expression內(nèi)可以含有變量（a～z）、常量（0～9）和二元運算符（+，-，*，/，^(乘冪)）。實現(xiàn)以下操作：</p>

5、<p>　　ReadExpre(E)—以字符序列的形式輸入語法正確的前綴表達式并構(gòu)造表達式E。</p><p>　　WriteExpre(E)—用帶括弧的中綴表達式輸出表達式E。</p><p>　　Assign(V,c)—實現(xiàn)對變量V的賦值（V=c），變量的初值為0。</p><p>　　Value(E)—對算術(shù)表達式E求值。</p>

6、<p>　　CompoundExpr（P，E1，E2）--構(gòu)造一個新的復(fù)合表達式（E1）P（E2）</p><p><b>　　【測試數(shù)據(jù)】</b></p><p>　　分別輸入0；a；-91；+a*bc；+*5^x2*8x；+++*3^x3*2^x2x6并輸出。</p><p>　　每當(dāng)輸入一個表達式后，對其中的變量賦值，然后對表達

7、式求值。</p><p>　　選題三：銀行業(yè)務(wù)模擬與離散事件模擬</p><p><b>　　【問題描述】</b></p><p>　　假設(shè)某銀行有4個窗口對外接待客戶，從早晨銀行開門（開門9：00am，關(guān)門5：00pm）起不斷有客戶進入銀行。由于每個窗口在某個時刻只能接待一個客戶，因此在客戶人數(shù)眾多時需要在每個窗口前順次排隊，對于剛進入銀行的

8、客戶（建議：客戶進入時間使用隨機函數(shù)產(chǎn)生），如果某個窗口的業(yè)務(wù)員正空閑，則可上前辦理業(yè)務(wù)；反之，若4個窗口均有窗戶所占，他便會排在人數(shù)最少的隊伍后面。</p><p><b>　　【實現(xiàn)提示】</b></p><p>　　編制一個程序以模擬銀行的這種業(yè)務(wù)活動并計算一天中客戶在銀行逗留的平均時間。</p><p><b>　　建議有如下

9、設(shè)置：</b></p><p>　　客戶到達時間隨機產(chǎn)生，一天客戶的人數(shù)設(shè)定為100人。</p><p>　　銀行業(yè)務(wù)員處理時間隨機產(chǎn)生，平均處理時間10分鐘。</p><p>　　將一天的數(shù)據(jù)（包括業(yè)務(wù)員和客戶）以文件方式輸出。</p><p><b>　　【測試數(shù)據(jù)】</b></p><

10、;p><b>　　由隨機數(shù)產(chǎn)生器生成</b></p><p>　　選題四：文學(xué)研究助手與模式匹配算法KMP</p><p><b>　　【問題描述】</b></p><p>　　文學(xué)研究人員需要統(tǒng)計某篇英文小說中某些形容詞的出現(xiàn)次數(shù)和位置。試寫一個實現(xiàn)這一目標(biāo)的文字統(tǒng)計系統(tǒng)</p><p>&

11、lt;b>　　【實現(xiàn)提示】</b></p><p>　　英文小說存于一個文本文件中。待統(tǒng)計的詞匯集合要一次輸入完畢，即統(tǒng)計工作必須在程序的一次運行之后就全部完成。程序的輸出結(jié)果是每個詞的出現(xiàn)次數(shù)和出現(xiàn)位置所在的行的行號，格式自行設(shè)計。待統(tǒng)計的“單詞”在文本串中不跨行出現(xiàn)，它或者從行首開始，或者前置以一個空格符。</p><p>　　模式匹配要基于KMP算法。</p&

12、gt;<p>　　推廣到更一般的模式集匹配問題，并設(shè)待查模式串可以跨行（提示：定義操作GetAChar）。</p><p><b>　　【測試數(shù)據(jù)】</b></p><p>　　文本文件為testword.c</p><p>　　待統(tǒng)計的詞集：if、else、for、while、return、void、int、char、typed

13、ef、struct</p><p>　　選題五：瓊州學(xué)院校園導(dǎo)游咨詢與最短路徑</p><p><b>　　【問題描述】</b></p><p>　　從瓊州學(xué)院的平面圖中選取有代表性景點（10-15個），抽象成一個無向帶權(quán)圖。以圖中頂點表示景點，邊上的權(quán)值表示兩地之間距離。</p><p>　　本程序的目的是為用戶提供路

14、徑咨詢。根據(jù)用戶指定的始點和終點輸出相應(yīng)路徑，或者根據(jù)用戶指定的景點輸出景點的信息。</p><p><b>　　【實現(xiàn)提示】</b></p><p>　　從瓊州學(xué)院的平面圖中選取有代表性景點（10-15個），抽象成一個無向帶權(quán)圖。以圖中頂點表示校內(nèi)各景點，存放景點名稱、代號、簡介等信息；以邊表示路徑，存放路徑長度等信息。</p><p>　　

15、為來訪客人提供圖中任意景點相關(guān)信息的查詢。</p><p>　　為來訪客人提供圖中任意景點的問路查詢，即查詢?nèi)我鈨蓚€景點之間的一條最短的簡單路徑。</p><p>　　區(qū)分汽車線路與步行線路。</p><p><b>　　【測試數(shù)據(jù)】</b></p><p>　　瓊州學(xué)院導(dǎo)游圖（距離可估計）。</p>&l

16、t;p>　　選題六：設(shè)計一個計算機管理系統(tǒng)完成圖書管理基本業(yè)務(wù) </p><p><b>　　【實現(xiàn)提示】 </b></p><p>　　1)每種書的登記內(nèi)容包括書號、書名、著作者、現(xiàn)存量和庫存量； </p><p>　　2)對書號建立索引表（線性表）以提高查找效率（索引表采用樹表）； </p

17、><p>　　3)系統(tǒng)主要功能如下： </p><p>　　*采編入庫：新購一種書，確定書號后，登記到圖書帳目表中，如果表中已有，則只將庫存量增加； </p><p>　　*借閱：如果一種書的現(xiàn)存量大于0，則借出一本，登記借閱者的書證號和歸還期限，改變現(xiàn)存量； </p><p>　　*歸還：注銷對借閱者的登記，改變該

18、書的現(xiàn)存量。</p><p>　　選題七：哈夫曼(Huffman)編/譯碼器</p><p><b>　　【問題描述】</b></p><p>　　利用哈夫曼編碼進行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來的數(shù)據(jù)進行譯碼（復(fù)原）。對于雙工信道（即可以雙向傳

19、輸信息的信道），每端都需要一個完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫一個哈夫曼碼的編/譯碼系統(tǒng)。</p><p><b>　　【實現(xiàn)提示】</b></p><p>　　一個完整的系統(tǒng)應(yīng)具有以下功能：</p><p>　　I：初始化（Initialization）。從終端讀入字符集大小n，以及n個字符和n個權(quán)值，建立哈夫曼樹，并將它存于文件h

20、fmTree中。</p><p>　　E：編碼（Encoding）。利用以建好的哈夫曼樹（如不在內(nèi)存，則從文件hfmTree中讀入），對文件ToBeTran中的正文進行編碼，然后將結(jié)果存入文件CodeFile中。</p><p>　　D：譯碼（Decoding）。利用已建好的哈夫曼樹將文件CodeFile中的代碼進行譯碼，結(jié)果存入文件TextFile中。</p><p&

21、gt;　　P：印代碼文件（Print）。將文件CodeFile以緊湊格式顯示在終端上，每行50個代碼。同時將此字符形式的編碼文件寫入文件CodePrin中。</p><p>　　T：印哈夫曼樹（Tree Printing）。將已在內(nèi)存中的哈夫曼樹以直觀的方式（樹或凹入表形式）顯示在終端上，同時將此字符形式的哈夫曼樹寫入文件TreePrint中。</p><p><b>　　【測試

22、數(shù)據(jù)】</b></p><p>　　利用教科書例6-2（嚴蔚敏《數(shù)據(jù)結(jié)構(gòu)》P148）中的數(shù)據(jù)調(diào)試程序。</p><p>　　用下表給出的字符集和頻度的實際統(tǒng)計數(shù)據(jù)建立哈夫曼樹，并實現(xiàn)以下報文的編碼和譯碼：“THIS PROGRAM IS MY FAVORITE”。</p><p>　　選題八：內(nèi)部排序算法比較</p><p>&l

23、t;b>　　【問題描述】</b></p><p>　　在教科書中，各種內(nèi)部排序算法的時間復(fù)雜度分析結(jié)果只給出了算法執(zhí)行時間的階，或大概執(zhí)行時間。試通過隨機數(shù)據(jù)比較各種算法的關(guān)鍵字比較次數(shù)和關(guān)鍵字移動次數(shù)，以取得直觀感受。</p><p><b>　　【實現(xiàn)提示】</b></p><p>　　對以下7種常用的內(nèi)部排序算法進行比較

24、：冒泡排序、直接插入排序、簡單選擇排序、希爾排序、堆排序、歸并排序、快速排序。</p><p>　　待排序表的表長不小于100；其中的數(shù)據(jù)要用偽隨機數(shù)程序產(chǎn)生；至少要用5組不同的輸入數(shù)據(jù)作比較；比較的指標(biāo)為有關(guān)鍵字參加的比較次數(shù)和關(guān)鍵字的移動次數(shù)（關(guān)鍵字交換計為3次移動）。</p><p>　　最后要對結(jié)果作出簡單分析，包括對各組數(shù)據(jù)得出結(jié)果波動大小的解釋。</p><

25、p><b>　　【測試數(shù)據(jù)】</b></p><p><b>　　由隨機數(shù)產(chǎn)生器生成</b></p><p>　　選題九：簡單行編輯程序</p><p><b>　　【問題描述】</b></p><p>　　文本編輯器程序是利用計算機進行文字加工的基本軟件工具，實現(xiàn)對文本

26、文件的插入、刪除等修改操作。限制這些操作以行為單位進行的編輯程序稱為行編輯程序。</p><p>　　被編輯的文本文件可能很大，全部讀入編輯程序的數(shù)據(jù)空間（內(nèi)存）的作法既不經(jīng)濟，也不總能實現(xiàn)。一種解決辦法是逐段地編輯。任何時刻只把待編輯文件的一段放在內(nèi)存，利為活區(qū)。試按照這種方法實現(xiàn)一個簡單的行編輯程序。設(shè)文件每行不超過320個字符，很少超過80個字符。</p><p><b>

27、　　【實現(xiàn)提示】</b></p><p>　　實現(xiàn)以下4條基本編輯命令：</p><p>　　行插入：格式：i<行號><回車><文本><回車></p><p>　　將<文本>插入活區(qū)中第<行號>行之后。</p><p>　　行刪除。格式：d<行號1>

28、;[<空格><行號2>]<回車></p><p>　　刪除活區(qū)中第<行號1>(到第<行號2>行)。例如“d10”和“d10 14”</p><p>　　活區(qū)切換。格式：n<回車></p><p>　　將活區(qū)寫入輸出文件，并從輸入文件中讀入下一段，作為新的活區(qū)。</p><p&

29、gt;　　活區(qū)顯示。模式：p<回車></p><p>　　逐頁地（每頁20行）顯示活區(qū)內(nèi)容，每顯示一頁之后請用戶決定是繼續(xù)顯示以后各頁（如果存在）。印出的每一行要前置行號和一個空格符，行號固定占4位，增量為1。</p><p>　　各條命令中的行號均須在活區(qū)中各行行號范圍之內(nèi)，只有插入命令的行號可以等于活區(qū)第一行行號減1，表示插入當(dāng)前屏幕中第一行之前，否則命令參數(shù)非法。<

30、/p><p><b>　　【測試數(shù)據(jù)】</b></p><p>　　自行設(shè)定，注意測試將活區(qū)刪空等特殊情況。</p><p>　　選題十：一元多項式計算</p><p><b>　　【問題描述】</b></p><p>　　1.能夠按照指數(shù)降序排列建立并輸出多項式；</p&

31、gt;<p>　　2.能夠完成兩個多項式的相加、相減，并將結(jié)果輸入；　　</p><p><b>　　【實現(xiàn)提示】</b></p><p><b>　　1.存儲結(jié)構(gòu);</b></p><p>　　2.多項式相加的基本過程的算法（可以使用程序流程圖）</p><p>　　3.可以提出算

32、法的改進方法；</p><p><b>　　【測試數(shù)據(jù)】</b></p><p>　　自行設(shè)定，注意邊界等特殊情況。</p><p>　　選題十一：集合的交、并、差運算</p><p><b>　　【問題描述】</b></p><p>　　編制一個能演示執(zhí)行集合的交、并和差運

33、算的程序。</p><p><b>　　【實現(xiàn)提示】</b></p><p>　　集合元素用小寫英文字母，執(zhí)行各種操作應(yīng)以對話方式執(zhí)行。</p><p>　　算法要點：利用單鏈表表示集合；理解好三種運算的含</p><p><b>　　【測試數(shù)據(jù)】</b></p><p>　

34、　自行設(shè)定，注意邊界等特殊情況。</p><p>　　選題十二：動態(tài)查找表</p><p><b>　　【問題描述】</b></p><p>　　利用二叉排序樹完成動態(tài)查找表的建立、指定關(guān)鍵字的查找、插入與刪除指定關(guān)鍵字結(jié)點。</p><p><b>　　【實現(xiàn)提示】</b></p>

35、<p>　　算法輸入：指定一組數(shù)據(jù)。</p><p>　　算法輸出：顯示二叉排序樹的中序遍歷結(jié)果、查找成功與否的信息、插入和刪除后的中序遍歷結(jié)果(排序結(jié)果)。</p><p>　　算法要點：二叉排序樹建立方法、動態(tài)查找方法,對樹進行中序遍歷。</p><p><b>　　【測試數(shù)據(jù)】</b></p><p>　

36、　自行設(shè)定，注意邊界等特殊情況。</p><p>　　選題十三：學(xué)生成績管理　</p><p><b>　　【問題描述】</b></p><p>　　本例對學(xué)生的成績管理做一個簡單的模擬，用菜單選擇方式完成下列功能： 登記學(xué)生成績；查詢學(xué)生成績；插入學(xué)生成績；刪除學(xué)生成績。</p><p><b>　　【實

37、現(xiàn)提示】</b></p><p>　　算法輸入：操作要求，學(xué)生信息</p><p><b>　　算法輸出：操作結(jié)果</b></p><p>　　算法要點：把問題看成是對線性表的操作。將學(xué)生成績組織成順序表，則登記學(xué)生成績即是建立順序表操作；查詢學(xué)生成績、插入學(xué)生成績、刪除學(xué)生成績即是在順序表中進行查找、插入和刪除操作。</p&

38、gt;<p><b>　　【測試數(shù)據(jù)】</b></p><p>　　自行設(shè)定，注意邊界等特殊情況。</p><p><b>　　選題十四：馬踏棋盤</b></p><p><b>　　【問題描述】</b></p><p>　　將馬隨機放在國際象棋的8* 8棋盤Bo

39、rd[8Ⅱ8]的某個方格中，馬按走棋規(guī)則進行移動。要求每個方格上只進入一次，走遍棋盤上全部64個方格。</p><p><b>　　【實現(xiàn)提示】</b></p><p>　　編制非遞歸程序，求出馬的行走路線 ，并按求出的行走路線，將數(shù)字1，2，…，64依次填入一個8* 8的方陣，輸出之。</p><p>　　測試數(shù)據(jù)：由讀者指定,可自行指定一個

40、馬的初始位置。</p><p>　　實現(xiàn)提示：每次在多個可走位置中選擇一個進行試探，其余未曾試探過的可走位置必須用適當(dāng)結(jié)構(gòu)妥善管理，以備試探失敗時的“回溯”(悔棋)使用。</p><p><b>　　【測試數(shù)據(jù)】</b></p><p>　　自行設(shè)定，注意邊界等特殊情況。</p><p>　　選題十五： joseph環(huán)&

41、lt;/p><p><b>　　【問題描述】</b></p><p>　　編號是1，2，……,n的n個人按照順時針方向圍坐一圈，每個人只有一個密碼（正整數(shù)）。一開始任選一個正整數(shù)作為報數(shù)上限值m,從第一個仍開始順時針方向自1開始順序報數(shù)，報到m時停止報數(shù)。報m的人出列，將他的密碼作為新的m值，從他在順時針方向的下一個人開始重新從1報數(shù)，如此下去，直到所有人全部出列為止。設(shè)

42、計一個程序來求出出列順序。</p><p><b>　　【實現(xiàn)提示】</b></p><p>　　利用單向循環(huán)鏈表存儲結(jié)構(gòu)模擬此過程，按照出列的順序輸出各個人的編號。</p><p>　　測試數(shù)據(jù)：　　m的初值為20，n=7 ,7個人的密碼依次為3，1，7，2，4，7，4，首先m=6,則正確的輸出是什么？　　 要求： 輸入數(shù)據(jù)：建立

43、輸入處理輸入數(shù)據(jù)，輸入m的初值，n ，輸入每個人的密碼，建立單循環(huán)鏈表?！　?輸出形式：建立一個輸出函數(shù)，將正確的輸出序列</p><p><b>　　【測試數(shù)據(jù)】</b></p><p>　　自行設(shè)定，注意邊界等特殊情況。</p><p>　　選題十六： 最小生成樹</p><p><b>　　【問題描述】

44、</b></p><p>　　在n個城市之間建設(shè)網(wǎng)絡(luò)，只需保證連通即可，求最經(jīng)濟的架設(shè)方法。</p><p>　　對于圖，其生成樹中的邊也帶權(quán)，將生成樹各邊的權(quán)值總和稱為生成樹的權(quán)，并將權(quán)值最小的生成樹稱為最小生成樹（Minimun Spanning Tree），簡稱為MST。有兩種非常典型的算法：Prim算法和kruskal算法。</p><p>&l

45、t;b>　　【實現(xiàn)提示】</b></p><p>　　設(shè)計程序完成如下功能：對給定的網(wǎng)和起點，用PRIM算法和kruskal算法的基本思想求解出所有的最小生成樹。存儲結(jié)構(gòu)可自行選擇。</p><p><b>　　【測試數(shù)據(jù)】</b></p><p>　　自行設(shè)定，注意邊界等特殊情況。</p><p>　

46、　選題十七：通訊錄管理</p><p><b>　　【問題描述】</b></p><p>　　該設(shè)計采用菜單作為應(yīng)用程序的主要界面，用控制語句來改變程序執(zhí)行的順序，控制語句是實現(xiàn)結(jié)構(gòu)化程序設(shè)計的基礎(chǔ)。該設(shè)計的任務(wù)是利用一個簡單實用的菜單，通過菜單單項進行選擇，實現(xiàn)和完成通訊錄管理中常用的幾個不同的功能。</p><p>　　【實現(xiàn)提示】

47、 </p><p><b>　　菜單內(nèi)容</b></p><p><b>　　通訊錄鏈表的建立</b></p><p><b>　　通訊者結(jié)點的插入</b></p><p><b>　　通訊者結(jié)點的查詢</b></p><p>&

48、lt;b>　　通訊者結(jié)點的刪除</b></p><p><b>　　通訊錄鏈表的輸出</b></p><p><b>　　退出管理系統(tǒng)</b></p><p><b>　　請選擇0~5：</b></p><p><b>　　設(shè)計要求</b>

49、;</p><p>　　使用0~5來選擇菜單項，其他輸入則不起作用。</p><p><b>　　功能函數(shù)設(shè)計</b></p><p>　　5個不同功能的算法實現(xiàn)編程題，目的是練習(xí)利用鏈表結(jié)構(gòu)來解決實際應(yīng)用問題的能力，進一步理解和熟悉線形表的鏈?zhǔn)酱鎯Y(jié)構(gòu)。</p><p><b>　　【測試數(shù)據(jù)】</b&

50、gt;</p><p>　　自行設(shè)定，注意邊界等特殊情況。</p><p>　　選題十八：運動會分數(shù)統(tǒng)計</p><p><b>　　【問題描述】</b></p><p>　　參加運動會有n個學(xué)校，學(xué)校編號為1……n。比賽分成m個男子項目，和w個女子項目。項目編號為男子1……m，女子m+1……m+w。不同的項目取前五名或

51、前三名積分；取前五名的積分分別為：7、5、3、2、1，前三名的積分分別為：5、3、2；哪些取前五名或前三名由學(xué)生自己設(shè)定。（m<=20,n<=20）</p><p><b>　　【實現(xiàn)提示】</b></p><p>　　功能要求：1).可以輸入各個項目的前三名或前五名的成績；　　2)．能統(tǒng)計各學(xué)?？偡?，　　3)．可以按學(xué)校編號、學(xué)校總分、男女團體總分排

52、序輸出；　　4).可以按學(xué)校編號查詢學(xué)校某個項目的情況；可以按項目編號查詢?nèi)〉们叭蚯拔迕膶W(xué)校。 　　規(guī)定：輸入數(shù)據(jù)形式和范圍：20以內(nèi)的整數(shù)（如果做得更好可以輸入學(xué)校的名稱，運動項目的名稱）　　輸出形式：有中文提示，各學(xué)校分數(shù)為整形　　界面要求：有合理的提示，每個功能可以設(shè)立菜單，根據(jù)提示，可以完成相關(guān)的功能要求?！　〈鎯Y(jié)構(gòu)：學(xué)生自己根據(jù)系統(tǒng)功能要求自己設(shè)計，但是要求運動會的相關(guān)數(shù)據(jù)要存儲在數(shù)據(jù)文件中。（數(shù)據(jù)文件的數(shù)據(jù)讀

53、寫方法等相關(guān)內(nèi)容在c語言程序設(shè)計的書上，請自學(xué)解決）請在最后的上交資料中指明你用到的存儲結(jié)構(gòu)；測試數(shù)據(jù)：要求使用1、全部合法數(shù)據(jù)；2、整體非法數(shù)據(jù)；3、局部非法數(shù)據(jù)。進行程序測試，以保證程序的穩(wěn)定。測試數(shù)據(jù)及測試結(jié)果請在上交的資料中寫明；</p><p><b>　　【測試數(shù)據(jù)】</b></p><p>　　自行設(shè)定，注意邊界等特殊情況。</p>&l

54、t;p>　　選題十九：航班信息的查詢與檢索</p><p><b>　　【問題描述】</b></p><p>　　該設(shè)計要求對飛機航班信息進行排序和查找?？砂春桨嗟暮桨嗵枴⑵瘘c站、到達站、起飛時間以及到達時間等信息進行查詢。</p><p><b>　　【實現(xiàn)提示】</b></p><p>　

55、　對于本設(shè)計，可采用基數(shù)排序法對一組具有結(jié)構(gòu)特點的飛機航班號進行排序，利用二分查找法對排好序的航班記錄按航班號實現(xiàn)快速查找，按其他次關(guān)鍵字的查找可采用最簡單的順序查找方法進行，因此他們用得較少。</p><p>　　每個航班記錄包括八項，分別是：航班號、起點站、終點站、班期、起飛時間、到達時間、飛機型號以及票價等，假設(shè)航班信息表（8條記錄）</p><p>　　其中航班號一項的格式為：&l

56、t;/p><p>　　K0 K1 K2 K3 K4 K5</p><p>　　其中K0和K1的輸入值是航空公司的別稱，用兩個大寫字母標(biāo)示，后4位為航班號，這種航班號關(guān)鍵字可分成兩段，即字母和數(shù)字。其余七項輸入內(nèi)容因為不涉及本設(shè)計的核心，因此除了票價為數(shù)值型外，均定義為字符串即可。</

57、p><p><b>　　【測試數(shù)據(jù)】</b></p><p>　　自行設(shè)定，注意邊界等特殊情況。</p><p>　　選題二十：哈希表應(yīng)用</p><p><b>　　【問題描述】</b></p><p>　　利用哈希表進行存儲。</p><p><

58、b>　　【實現(xiàn)提示】 </b></p><p>　　任務(wù)要求：針對一組數(shù)據(jù)進行初始化哈希表，可以進行顯示哈希表，查找元素，插入元素，刪除元素，退出程序操作。</p><p>　　設(shè)計思想：哈希函數(shù)用除留余數(shù)法構(gòu)造，用線性探測再散列處理沖突。</p><p>　　設(shè)計目的：實現(xiàn)哈希表的綜合操作</p><p>　　簡體中文控

59、制臺界面：用戶可以進行創(chuàng)建哈希表，顯示哈希表，查找元素，插入元素，刪除元素。</p><p>　　顯示元素：顯示已經(jīng)創(chuàng)建的哈希表。</p><p>　　查找元素：查找哈希表中的元素，分為查找成功和查找不成功。</p><p>　　插入元素：在哈希表中，插入一個元素，分為插入成功和失敗。</p><p>　　刪除元素：在已有的數(shù)據(jù)中，刪除一個元

60、素。</p><p>　　退出系統(tǒng)：退出程序。</p><p><b>　　【測試數(shù)據(jù)】</b></p><p>　　自行設(shè)定，注意邊界等特殊情況。</p><p>　　選題二十一：拓撲排序和關(guān)鍵路徑</p><p><b>　　【問題描述】</b></p>&

61、lt;p>　　拓撲排序可判斷AOV網(wǎng)絡(luò)中是否存在回路，使的所有活動可排成一個線性序列，使用每個活動的所有前驅(qū)活動都排在該活動的前面。</p><p>　　關(guān)鍵路徑的工期決定了整個項目的工期。任何關(guān)鍵路徑上的終端元素的延遲將直接影響項目的預(yù)期完成時間（例如在關(guān)鍵路徑上沒有浮動時間）。</p><p><b>　　【實現(xiàn)提示】 </b></p>&

62、lt;p>　　構(gòu)建AOV網(wǎng)絡(luò)，并輸出其拓撲序列結(jié)果，輸出該圖的關(guān)鍵路徑和關(guān)鍵活動，存儲結(jié)構(gòu)自行選擇。</p><p><b>　　【測試數(shù)據(jù)】</b></p><p>　　自行設(shè)定，注意邊界等特殊情況。</p><p>　　選題二十二：倉庫管理系統(tǒng)</p><p><b>　　【問題描述】</b&g

63、t;</p><p>　　建立一個倉庫管理程序，可以按順序和貨物名稱查詢倉庫存儲情況，也可以增加或刪除貨物以及建立新的倉庫存儲系統(tǒng)。</p><p>　　【實現(xiàn)提示】可以采用雙向鏈表的存儲結(jié)構(gòu)，如可定義如下的存儲結(jié)構(gòu)：</p><p>　　typedef struct dnode /*定義雙向鏈表結(jié)構(gòu)體*/</p><p>　　{int

64、 number; /*貨物編號*/</p><p>　　char name[max]; /*貨物名稱*/</p><p>　　int counter; /*貨物數(shù)量*/</p><p>　　struct dnode *prior,*next; /*定義兩指針，分別指向其前驅(qū)和后繼*/</p><p><b&g

65、t;　　}dlnode;</b></p><p>　　選題二十三：單位員工通訊錄管理系統(tǒng)</p><p><b>　　【問題描述】</b></p><p>　　為某個單位建立一個員工通訊錄管理系統(tǒng)，可以方便查詢每一個員工的辦公室電話、手機號、及電子郵箱。其功能包括通訊錄鏈表的建立、員工通訊信息的查詢、修改、插入與刪除、以及整個通訊錄

66、表的輸出。</p><p>　　【實現(xiàn)提示】可以采用單鏈表的存儲結(jié)構(gòu)，如可定義如下的存儲結(jié)構(gòu)：</p><p>　　typedef struct { /*員工通訊信息的結(jié)構(gòu)類型定義*/</p><p>　　char num[5]; /*員工編號*/</p><p>　　char name[10]; /*員工姓名*/ &

67、lt;/p><p>　　char phone[15]; /*辦公室電話號碼*/</p><p>　　char call[15]; /*手機號碼*/</p><p>　　}DataType;</p><p>　　/*通訊錄單鏈表的結(jié)點類型*/</p><p>　　typedef struct node<

68、/p><p>　　{ DataType data; /*結(jié)點的數(shù)據(jù)域*/</p><p>　　struct node *next; /*結(jié)點的指針域*/</p><p>　　}ListNode,*LinkList;</p><p>　　選題二十四: 哈夫曼編碼/譯碼系統(tǒng)</p><p><b>　　【問題

69、描述】</b></p><p>　　利用哈夫曼編碼進行通信，可以壓縮通信的數(shù)據(jù)量，提高傳輸效率，縮短信息的傳輸時間，還有一定的保密性?，F(xiàn)在要求編寫一程序模擬傳輸過程，實現(xiàn)在發(fā)送前將要發(fā)送的字符信息進行編碼，然后進行發(fā)送，接收后將傳來的數(shù)據(jù)進行譯碼，即將信息還原成發(fā)送前的字符信息。</p><p><b>　　【實現(xiàn)提示】</b></p>&l

70、t;p>　　在本例中設(shè)置發(fā)送者和接受者兩個功能，</p><p><b>　　發(fā)送者的功能包括：</b></p><p>　?、佥斎氪齻魉偷淖址畔?；</p><p>　?、诮y(tǒng)計字符信息中出現(xiàn)的字符種類數(shù)和各字符出現(xiàn)的次數(shù)（頻率）；</p><p>　?、诟鶕?jù)字符的種類數(shù)和各自出現(xiàn)的次數(shù)建立哈夫曼樹；</p&

71、gt;<p>　?、劾靡陨瞎蚵鼧淝蟪龈髯址墓蚵幋a；</p><p>　?、軐⒆址畔⑥D(zhuǎn)換成對應(yīng)的編碼信息進行傳送。</p><p><b>　　接受者的功能包括：</b></p><p>　?、俳邮瞻l(fā)送者傳送來的編碼信息；</p><p>　?、诶蒙鲜龉蚵鼧鋵幋a信息進行翻譯，即將編碼信息還原

72、成發(fā)送前的字符信息。</p><p>　　從以上分析可發(fā)現(xiàn)，在本例中的主要算法有三個：</p><p>　?。?）哈夫曼樹的建立；</p><p>　　（2）哈夫曼編碼的生成；</p><p>　?。?）對編碼信息的翻譯。</p><p>　　選題二十五:教學(xué)計劃編制問題</p><p><

73、;b>　　【問題描述】</b></p><p>　　大學(xué)的每個專業(yè)都要制定教學(xué)計劃。假設(shè)任何專業(yè)都有固定的學(xué)習(xí)年限，每學(xué)年含兩學(xué)期，每學(xué)期的時間長度和學(xué)分上限值均相等。每個專業(yè)開設(shè)的課程都是確定的，而且課程在開設(shè)時間的安排必須滿足先修關(guān)系。每門課程有哪些先修課程是確定的，可以有任意多門，也可以沒有。每門課恰好占一個學(xué)期。試在這樣的前提下設(shè)計一個教學(xué)計劃編制程序。</p><p

74、><b>　　【實現(xiàn)提示】</b></p><p>　　輸入?yún)?shù)應(yīng)包括：學(xué)期總數(shù)，一學(xué)期的學(xué)分上限，每門課的課程號（可以是固定占3位的字母數(shù)字串）、學(xué)分和直接先修課的課程號。</p><p>　　應(yīng)允許用戶指定下列兩種編排策略之一：一是使學(xué)生在各學(xué)期中的學(xué)習(xí)負擔(dān)盡量均勻；二是使課程盡可能地集中在前幾個學(xué)期中。</p><p>　　若根據(jù)給

75、定的條件問題無解，則報告適當(dāng)?shù)男畔?；否則將教學(xué)計劃輸出到用戶指定的文件中。計劃的表格格式可以自己設(shè)計。</p><p>　　可設(shè)學(xué)期總數(shù)不超過12，課程總數(shù)不超過100。如果輸入的先修課程號不在該專業(yè)開設(shè)的課程序列中，則作為錯誤處理。</p><p>　　選題二十六：圖書管理系統(tǒng)</p><p><b>　　【問題描述】</b></p&g

76、t;<p>　　圖書管理基本業(yè)務(wù)活動包括：對一本書的采編入庫、清除庫存、借閱和歸還等等。試設(shè)計一個圖書管理系統(tǒng)，將上述業(yè)務(wù)活動借助于計算機系統(tǒng)完成。</p><p><b>　　【實現(xiàn)提示】</b></p><p>　　每種書的登記內(nèi)容至少包括書號、書名、著者、現(xiàn)存量和總庫存量等五項。</p><p>　　由于圖書管理的基本業(yè)務(wù)活

77、動都是通過書號（即關(guān)鍵字）進行的，所以要用對書號 索引，以獲得高效率。</p><p>　　系統(tǒng)應(yīng)實現(xiàn)的基本功能有：</p><p>　　采編入庫：新購入一種書，經(jīng)分類和確定書號之后登記到圖書帳目中去。如果這兩種書在帳中已有，則只將總庫存量增加。</p><p>　　清除庫存：某種書已無保留價值，將它從圖書帳目中注銷。</p><p>　　借

78、閱：如果一種書的現(xiàn)存量大于零，則借出一本，登記借閱者的圖書證號和歸還期限。</p><p>　　歸還：注銷對借閱者的登記，改變該書的現(xiàn)存量。</p><p>　　顯示：以凹入表的形式顯示B樹。這個操作是為了調(diào)試和維護的目的而設(shè)置的。</p><p>　　選題二十七： 通信錄查詢系統(tǒng)</p><p><b>　　【問題描述】</

79、b></p><p>　　設(shè)計散列表實現(xiàn)通訊錄查找系統(tǒng)。</p><p>　　(1) 設(shè)每個記錄有下列數(shù)據(jù)項：電話號碼、用戶名、地址；(2) 從鍵盤輸入各記錄，分別以電話號碼為關(guān)鍵字建立散列表；(3) 采用二次探測再散列法解決沖突；(4) 查找并顯示給定電話號碼的記錄；</p><p>　　(5) 通訊錄信息文件保存；</p><p&

80、gt;　　(6) 要求人機界面友好，使用圖形化界面；【實現(xiàn)提示】</p><p>　　主函數(shù)：根據(jù)選單的選項調(diào)用各函數(shù)，并完成相應(yīng)的功能。</p><p>　　Menu()的功能：顯示英文提示選單。</p><p>　　Quit()的功能：退出選單。</p><p>　　Create()的功能：創(chuàng)建新的通訊錄。</p><

81、;p>　　Append()的功能：在通訊錄的末尾寫入新的信息，并返回選單。</p><p>　　Find()：查詢某人的信息，如果找到了，則顯示該人的信息，如果沒有則提示通訊錄中沒有此人的信息，并返回選單。</p><p>　　Alter()的功能：修改某人的信息，如果未找到要修改的人，則提示通訊錄中沒有此人的信息，并返回選單。</p><p>　　Delet

82、e()的功能：刪除某人的信息，如果未找到要刪除的人，則提示通訊錄中沒有此人的信息，并返回選單。</p><p>　　List()的功能：顯示通訊錄中的所有記錄。</p><p>　　Save()的功能：保存通訊錄中的所有記錄到指定文件中。</p><p>　　Load()的功能：從指定文件中讀取通訊錄中的記錄。</p><p>　　選題二十八

83、 藥店的藥品銷售統(tǒng)計系統(tǒng)</p><p><b>　　【問題描述】</b></p><p>　　設(shè)計一系統(tǒng)，實現(xiàn)醫(yī)藥公司定期對銷售各藥品的記錄進行統(tǒng)計，可按藥品的編號、單價、銷售量或銷售額做出排名。</p><p><b>　　【實現(xiàn)提示】</b></p><p>　　在本設(shè)計中，首先從數(shù)據(jù)文件中讀

84、出各藥品的信息記錄，存儲在順序表中。各藥品的信息包括：藥品編號、藥名、藥品單價、銷出數(shù)量、銷售額。藥品編號共4位，采用字母和數(shù)字混合編號，如：A125，前一位為大寫字母，后三位為數(shù)字，按藥品編號進行排序時，可采用基數(shù)排序法。對各藥品的單價、銷售量或銷售額進行排序時，可采用多種排序方法，如直接插入排序、冒泡排序、快速排序，直接選擇排序等方法。在本設(shè)計中，對單價的排序采用冒泡排序法，對銷售量的排序采用快速排序法，對銷售額的排序采用堆排序法。

85、</p><p>　　藥品信息的元素類型定義：</p><p>　　typedef struct node</p><p>　　{ char num[4]; /*藥品編號*/</p><p>　　char name[10]; /*藥品名稱*/</p><p>　　float price; /*藥品單價*/</

86、p><p>　　int count; /*銷售數(shù)量*/</p><p>　　float sale; /*本藥品銷售額*/</p><p>　　}DataType;</p><p>　　存儲藥品信息的順序表的定義：</p><p>　　typedef struct</p><p>　　{ Da

87、taType r[MaxSize]; </p><p>　　int length;</p><p>　　}SequenList;</p><p>　　選題二十九 電視大賽觀眾投票及排名系統(tǒng)</p><p><b>　　【問題描述】</b></p><p>　　在很多的電視大賽中，通常當(dāng)選手表演結(jié)

88、束后，現(xiàn)場觀眾通過手中的按鍵對參賽選手進行投票，然后對選手獲得的票數(shù)進行統(tǒng)計，從高到低進行降序排序，從而自動產(chǎn)生冠軍、亞軍和季軍?，F(xiàn)在要求編寫一程序模擬實現(xiàn)上述系統(tǒng)的功能。</p><p><b>　　【實現(xiàn)提示】</b></p><p>　　在本例中，首先輸入?yún)①愡x手的人數(shù)（范圍為1-9個），然后根據(jù)人數(shù)通過malloc函數(shù)來開辟存放選手信息的順序表。將選手的編號和

89、姓名依此存入順序表單元中，觀眾通過按鍵進行投票，按’1’為1號選手投票，按’2’為2號選手投票，以此類推，以按’0’作為投票結(jié)束標(biāo)志。投票結(jié)束后進行排序，在此采用希爾排序，然后為每個選手計算名次，得票相同的名次也相同， </p><p>　　（1）存儲類型的定義</p><p>　　參賽選手信息存儲類型的定義：</p><p>　　typedef struct no

90、de{</p><p>　　char name[8]; /*選手姓名*/</p><p>　　int num; /*選手編號*/ </p><p>　　int score; /*選手得分*/</p><p>　　int tax; /*選手名次*/</p><p><b>　　}Node;</b&