數(shù)據(jù)結(jié)構(gòu)A課程設(shè)計(jì)

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)題目列表PAGE13 數(shù)據(jù)結(jié)構(gòu)A課程設(shè)計(jì)題目1、題目一集合的并、交和差運(yùn)算【問題描述】編制一個(gè)能演示執(zhí)行集合的并、交和差運(yùn)算的程序?！净疽蟆考系脑叵拮孕卸x。演示程序以用戶和計(jì)算機(jī)的對話方式執(zhí)行?！緶y試數(shù)據(jù)】自行建立?！緦?shí)現(xiàn)提示】無?！具x做內(nèi)容】集合的元素判定和子集判定運(yùn)算。求集合的補(bǔ)集。集合的混合運(yùn)算表達(dá)式求解。集合的元素類型推廣到其他類型，甚至任一類型。2、題目二算術(shù)表達(dá)式計(jì)算【問題描述】表達(dá)式計(jì)算是實(shí)現(xiàn)程序設(shè)計(jì)語言的基本問題之一，也是棧的應(yīng)用的一個(gè)典型例子。設(shè)計(jì)一個(gè)程序，演示用算符優(yōu)先法對算術(shù)表達(dá)式求值的過程?！净疽蟆恳宰址蛄械男问綇慕K端輸入語法正確的、不含變量的整數(shù)表達(dá)式。利用運(yùn)算符優(yōu)先關(guān)系，實(shí)現(xiàn)對算術(shù)四則混合運(yùn)算表達(dá)式的求值?！緶y試數(shù)據(jù)】（1）能夠判斷表達(dá)式中的括號是否匹配，測試的表達(dá)式中括號不匹配，可以重新輸入。（2）能夠處理多位整數(shù)以及浮點(diǎn)數(shù)。（3）具體測試數(shù)據(jù)自定義。【實(shí)現(xiàn)提示】設(shè)置運(yùn)算符棧和運(yùn)算數(shù)棧輔助分析算符優(yōu)先關(guān)系；在讀入表達(dá)式的字符序列的同時(shí)，完成運(yùn)算符和運(yùn)算數(shù)（整數(shù)）的識別處理，以及相應(yīng)的運(yùn)算；在程序的適當(dāng)位置輸出運(yùn)算符棧、運(yùn)算數(shù)棧、輸入字符和主要操作等內(nèi)容?！具x做內(nèi)容】擴(kuò)充運(yùn)算符集，如增加乘方、單目減、賦值等運(yùn)算。3、題目三貪吃蛇游戲開發(fā)【問題描述】貪吃蛇游戲是一個(gè)深受人們喜歡的游戲，編程實(shí)現(xiàn)該游戲?！净疽蟆恳粭l蛇在密閉的圍墻內(nèi)，在圍墻內(nèi)隨機(jī)出現(xiàn)一個(gè)食物，通過鍵盤上的四個(gè)光標(biāo)鍵控制蛇向上下左右四個(gè)方向移動，蛇頭撞到食物，則表示食物被吃掉，這時(shí)蛇的身體長一節(jié)，同時(shí)計(jì)1分；接著又出現(xiàn)食物，等待被蛇吃掉，如果蛇在移動過程中，撞到墻壁或身體交叉（蛇頭撞到自己的身體）游戲結(jié)束?！緶y試數(shù)據(jù)】自定義?！緦?shí)現(xiàn)提示】（1）圍墻區(qū)域可以用二維數(shù)組實(shí)現(xiàn)；（2）食物隨機(jī)產(chǎn)生；（3）蛇的身體使用鏈表；（4）蛇的游動采用插入頭結(jié)點(diǎn)，刪除尾結(jié)點(diǎn)的方法實(shí)現(xiàn)?！具x做內(nèi)容】可以根據(jù)情況，自行添加完善。4、題目四航空訂票模擬【問題描述】航空客運(yùn)訂票的業(yè)務(wù)活動包括：查詢航線、客票預(yù)定和辦理退票等。設(shè)計(jì)一個(gè)航空訂票模擬程序，以使上述業(yè)務(wù)可以借助計(jì)算機(jī)來完成。（難度系數(shù)：0.73）【基本要求】每條航線所涉及的信息有：終點(diǎn)站名、航班號、飛機(jī)號、飛行周日（星期幾）、乘員定額、余票量、訂票的客戶名單（包括姓名、訂票量、艙位等級1，2或3）以及等候替補(bǔ)的客戶名單（包括姓名、所需數(shù)量）。系統(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ù)無法預(yù)計(jì)，隊(duì)列也應(yīng)以鏈表作存儲結(jié)構(gòu)。整個(gè)系統(tǒng)需匯總各條航線的情況登陸在一張線性表上，由于航線基本不變，可采用順序存儲結(jié)構(gòu)，并按航班有序或按終點(diǎn)站名有序。每條航線是這張表上的一個(gè)記錄，包含上述8個(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)目。5、題目五哈希查找【問題描述】若要在n個(gè)城市間建設(shè)通信網(wǎng)路，只需要架設(shè)n-1條線路即可。如何以最低的經(jīng)濟(jì)代價(jià)建設(shè)這個(gè)通信網(wǎng)，是一個(gè)網(wǎng)的最小生成樹問題。（難度系數(shù)：0.78）【基本要求】利用普里姆算法和克魯斯卡爾算法求網(wǎng)的最小生成樹。以文本形式輸出生成樹中各條邊以及他們的權(quán)值?！緶y試數(shù)據(jù)】自行建立。【實(shí)現(xiàn)提示】通信線路一旦建立，必然是雙向的。因此，構(gòu)造最小生產(chǎn)樹的網(wǎng)一定是無向網(wǎng)。設(shè)圖的頂點(diǎn)數(shù)不超過30個(gè)，并為簡單起見，網(wǎng)中邊的權(quán)值設(shè)成小于100的整數(shù)，可利用隨機(jī)數(shù)函數(shù)產(chǎn)生?！具x做內(nèi)容】利用堆排序選擇實(shí)現(xiàn)權(quán)值最小的邊。6、題目六哈夫曼編/譯碼器設(shè)計(jì)【問題描述】利用哈夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。但是，這要求在發(fā)送端通過一個(gè)編碼系統(tǒng)對待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來的數(shù)據(jù)進(jìn)行譯碼（復(fù)原）。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個(gè)完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫一個(gè)哈夫曼的編/譯碼系統(tǒng)。（難度系數(shù)：0.82）【基本要求】一個(gè)完整的系統(tǒng)應(yīng)該具有以下功能：I：初始化（Initialization）。從終端讀入字符集大小n，以及n個(gè)字符和n個(gè)權(quán)值，建立哈夫曼樹，并將它存于文件hfmTree中；E：編碼（Encoding）。利用已建立好的哈夫曼樹（如不在內(nèi)存，則從文件hfmTree中讀入），對文件ToBeTran中的正文進(jìn)行編碼，然后將結(jié)果存入文件CodeFile中；D：譯碼（Decoding）。利用已建好的哈夫曼樹將文件CodeFile中的代碼進(jìn)行譯碼。結(jié)果存入文件TectFile中?！緶y試數(shù)據(jù)】自行建立?！緦?shí)現(xiàn)提示】編碼結(jié)果以文本方式存儲在文件CodeFile中；用戶界面可以設(shè)計(jì)為“菜單”方式。【選做內(nèi)容】文本壓縮解壓。7、題目七校園導(dǎo)游系統(tǒng)模擬【問題描述】設(shè)計(jì)一個(gè)校園導(dǎo)游程序，為來訪的客人提供各種信息查詢服務(wù)?！净疽蟆吭O(shè)計(jì)學(xué)校的校園平面圖，所含景點(diǎn)不少于6個(gè)。以圖中頂點(diǎn)表示校內(nèi)各景點(diǎn)，存放景點(diǎn)名稱、代號、間介等信息；以邊表示路徑，存放路徑長度等相關(guān)信息。為來訪客人提供圖中任意景點(diǎn)相關(guān)信息的查詢。提供途中任意景點(diǎn)問路查詢，即求任意兩個(gè)景點(diǎn)間的一條最短的簡單路徑?！緶y試數(shù)據(jù)】自行建立。【實(shí)現(xiàn)提示】無【選做內(nèi)容】提供途中任意景點(diǎn)問路查詢，即求任意兩個(gè)景點(diǎn)間的所有路徑。提供校園圖中多個(gè)景點(diǎn)的最佳訪問路線查詢，即求途經(jīng)這多個(gè)景點(diǎn)的最佳（短）路徑。8、題目八教學(xué)計(jì)劃編制問題【問題描述】大學(xué)的每個(gè)專業(yè)都要制定教學(xué)計(jì)劃。假設(shè)任何專業(yè)都有固定的學(xué)習(xí)年限，每學(xué)年含兩學(xué)期，每學(xué)期的時(shí)間長度和學(xué)分上限值均相等。每個(gè)專業(yè)開設(shè)的課程都是確定的，而且課程在開設(shè)時(shí)間的安排必須滿足先修關(guān)系。每門課程有哪些先修課程是確定的，可以有任意多門，也可以沒有。每門課恰好占一個(gè)學(xué)期。試在這樣的前提下設(shè)計(jì)一個(gè)教學(xué)計(jì)劃編制程序?！净疽蟆浚?）輸入?yún)?shù)包括：學(xué)期總數(shù)，一學(xué)期的學(xué)分上限，每門課的課程號（固定占3位的字母數(shù)字串）、學(xué)分和直接先修課的課程號。（2）允許用戶指定下列兩種編排策略之一：一是使學(xué)生在各學(xué)期中的學(xué)習(xí)負(fù)擔(dān)盡量均勻；二是使課程盡可能地集中在前幾個(gè)學(xué)期中。（3）若根據(jù)給定的條件問題無解，則報(bào)告適當(dāng)?shù)男畔ⅲ环駝t將教學(xué)計(jì)劃輸出到用戶指定的文件中。計(jì)劃的表格格式自行設(shè)計(jì)?！緶y試數(shù)據(jù)】學(xué)期總數(shù)：6；學(xué)分上限：10；該專業(yè)共開設(shè)12門課，課程號從C01到C12，學(xué)分順序?yàn)?，3，4，3，2，3，4，4，7，5，2，3。先修關(guān)系見圖1?！緦?shí)現(xiàn)提示】可設(shè)學(xué)期總數(shù)不超過12，課程總數(shù)不超過100。如果輸入的先修課程號不在該專業(yè)開設(shè)的課程序列中，則作為錯(cuò)誤處理。應(yīng)建立內(nèi)部課程號與課程號之間的對應(yīng)關(guān)系。圖1課程先修關(guān)系9、題目九成績分析問題【問題描述】錄入、保存一個(gè)班級學(xué)生多門課程的成績，并對成績進(jìn)行分析?！净疽蟆浚?）通過鍵盤輸入各學(xué)生的多門課程的成績，建立相應(yīng)的文件input.dat。（2）對文件input.dat中的數(shù)據(jù)進(jìn)行處理，要求具有如下功能：按各門課程成績排序，并生成相應(yīng)的文件輸出。計(jì)算每人的平均成績，按平均成績排序，并生成文件。求出各門課程的平均成績、最高分、最低分、不及格人數(shù)、60~69分人數(shù)、70~79分人數(shù)、80~89分人數(shù)、90分以上人數(shù)。根據(jù)姓名或?qū)W號查詢某人的各門課成績，重名情況也能處理。【測試數(shù)據(jù)】測試數(shù)據(jù)自定義，參考格式如表2所示。表2成績表學(xué)號姓名數(shù)學(xué)英語計(jì)算機(jī)001王放787790002張強(qiáng)896788003李浩566678004黃鸝兵898685005李浩678876006陳利風(fēng)455467007尚曉78767010、題目十迷宮問題【問題描述】以一個(gè)m*n的長方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設(shè)計(jì)一個(gè)程序，對任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結(jié)論?！净疽蟆浚?）編程求出迷宮的一個(gè)解。（2）編寫遞歸形式的算法，求得迷宮中所有可能的通路（選作）。【測試數(shù)據(jù)】自定義?！緦?shí)現(xiàn)提示】計(jì)算機(jī)解迷宮通常用的是“窮舉求解”方法，即從入口出發(fā)，順著某一個(gè)方向進(jìn)行探索，若能走通，則繼續(xù)往前進(jìn)；否則沿著原路退回，換一個(gè)方向繼續(xù)探索，直至出口位置，求得一條通路。假如所有可能的通路都探索到而未能到達(dá)出口，則所設(shè)定的迷宮沒有通路?？梢远S數(shù)組存儲迷宮數(shù)據(jù)，通常設(shè)定入口點(diǎn)的下標(biāo)為（1，1），出口點(diǎn)的下標(biāo)為（m,n）。為處理方便起見，可在迷宮的四周加一圈障礙。對于迷宮中任一位置，均可約定有東、南、西、北四個(gè)方向可通。11、題目十一小型書店的圖書信息管理模擬【問題描述】小型書店的圖書信息管理的功能包括圖書信息的增加、刪除、更新和查詢等。設(shè)計(jì)一個(gè)小型書店的圖書信息管理模擬程序，以使上述業(yè)務(wù)可以借助計(jì)算機(jī)來完成。【基本要求】每一類圖書所涉及的信息有：圖書的ISBN號、圖書名稱、作者、出版社、價(jià)格、庫存數(shù)量。系統(tǒng)能實(shí)現(xiàn)的操作和功能如下：（1）查詢圖書信息：根據(jù)輸入的圖書信息（ISBN號或名稱）輸出下列信息：圖書的ISBN號、圖書名稱、作者、出版社、價(jià)格、庫存數(shù)量。（2）圖書信息增加或更新：根據(jù)每次采購圖書的信息要求實(shí)現(xiàn)對相應(yīng)圖書信息的增加或更新。（3）圖書信息刪除：對于部分圖書的信息需要進(jìn)行刪除操作?！緶y試數(shù)據(jù)】自行建立?！緦?shí)現(xiàn)提示】圖書信息建議以文件方式存放，便于數(shù)據(jù)操作。數(shù)據(jù)查詢時(shí)建議使用順序或折半查找。

Southwestuniversityofscienceandtechnology數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)課題名稱專業(yè)名稱學(xué)生姓名學(xué)號+電話指導(dǎo)教師評分項(xiàng)（30分）具體評分項(xiàng)得分【1】設(shè)計(jì)過程學(xué)習(xí)態(tài)度（3分）設(shè)計(jì)能力（4分）設(shè)計(jì)效果（4分）【2】報(bào)告格式規(guī)范（3分）內(nèi)容充實(shí)（4分）測試數(shù)據(jù)合理（4分）【3】答辯敘述清楚與否（3分）課題演示效果（4分）能否正確回答提問（4分）總分評閱教師蔡茂蓉□曾立勝□李學(xué)俊□何剛□評分細(xì)則

目錄一、課題描述編制一個(gè)演示單鏈表插入、刪除、查找等操作的程序。二、需求分析本設(shè)計(jì)程序用C編寫，完成單鏈表的生成，任意位置的插入、刪除，以及確定某一元素在單鏈表中的位置。①輸入的形式和輸入值的范圍：插入元素時(shí)需要輸入插入的位置和元素的值；刪除元素時(shí)輸入刪除元素的位置；查找操作時(shí)需要輸入元素的值。在所有輸入中，元素的值都是整數(shù)。②輸出的形式：在所有三種操作中都顯示操作是否正確以及操作后單鏈表的內(nèi)容。其中刪除操作后顯示刪除的元素的值，查找操作后顯示要查找元素的位置。③程序所能達(dá)到的功能：完成單鏈表的生成（通過插入操作）、插入、刪除、查找操作。三、概要設(shè)計(jì)1）數(shù)據(jù)邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)分析：（補(bǔ)充完成）2）本程序包含6個(gè)函數(shù)：（1）顯示操作菜單函數(shù)menu()（2）初始化單鏈表函數(shù)InitLinkList()補(bǔ)充:參數(shù)描述、功能描述（3）顯示單鏈表內(nèi)容函數(shù)dispLinkList()補(bǔ)充:參數(shù)描述、功能描述（4）插入元素函數(shù)InsLinkList()補(bǔ)充:參數(shù)描述、功能描述（5）刪除元素函數(shù)DelLinkList()補(bǔ)充:參數(shù)描述、功能描述（6）查找元素函數(shù)LocLinkList()補(bǔ)充:參數(shù)描述、功能描述各函數(shù)間關(guān)系如下：Menu()M