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

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

1.同學(xué)必需認(rèn)真閱讀《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)方案，仔細(xì)主動完成課設(shè)的要求。有問題準(zhǔn)時主動通過各種方式與老師聯(lián)系溝通。

2.同學(xué)要發(fā)揮自主學(xué)習(xí)的力量，充分利用時間，支配好課設(shè)的時間方案，并在課設(shè)過程中不斷檢測自己的方案完成狀況，準(zhǔn)時向老師匯報(bào)。

3.課程設(shè)計(jì)根據(jù)教學(xué)要求需要兩周時間完成，兩周中每天（按每周5天）至少要上2小時的上機(jī)來調(diào)試C或C++語言設(shè)計(jì)的程序，總共至少要上機(jī)調(diào)試程序20小時。屬老師支配上機(jī)時間同學(xué)不得缺席。

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

1.運(yùn)動會分?jǐn)?shù)統(tǒng)計(jì)（限1人完成）

任務(wù)：參與運(yùn)動會有n個學(xué)校，學(xué)校編號為1……n。競賽分成m個男子項(xiàng)目，和w個女子項(xiàng)目。項(xiàng)目編號為男子1……m，女子m+1……m+w。不同的項(xiàng)目取前五名或前三名積分；取前五名的積分分別為：7、5、3、2、1，前三名的積分分別為：5、3、2；哪些取前五名或前三名由同學(xué)自己設(shè)定。（m<=20,n<=20）

功能要求：

1)可以輸入各個項(xiàng)目的前三名或前五名的成果；

2)能統(tǒng)計(jì)各學(xué)校總分，

3)可以按學(xué)校編號或名稱、學(xué)?？偡帧⒛信畧F(tuán)體總分排序輸出；

4)可以按學(xué)校編號查詢學(xué)校某個項(xiàng)目的狀況；可以按項(xiàng)目編號查詢?nèi)〉们叭蚯拔迕膶W(xué)校。

5)數(shù)據(jù)存入文件并能隨時查詢

6)規(guī)定：輸入數(shù)據(jù)形式和范圍：可以輸入學(xué)校的名稱，運(yùn)動項(xiàng)目的名稱

輸出形式：有中文提示，各學(xué)校分?jǐn)?shù)為整形

界面要求：有合理的提示，每個功能可以設(shè)立菜單，依據(jù)提示，可以完成相關(guān)的功能要求。

存儲結(jié)構(gòu)：同學(xué)自己依據(jù)系統(tǒng)功能要求自己設(shè)計(jì)，但是要求運(yùn)動會的相關(guān)數(shù)據(jù)要存儲在數(shù)據(jù)文件中。（數(shù)據(jù)文件的數(shù)據(jù)讀寫方法等相關(guān)內(nèi)容在c語言程序設(shè)計(jì)的書上，請自學(xué)解決）請?jiān)谧罱K的上交資料中指明你用到的存儲結(jié)構(gòu)；

測試數(shù)據(jù)：要求使用1、全部合法數(shù)據(jù)；2、整體非法數(shù)據(jù)；3、局部非法數(shù)據(jù)。進(jìn)行程序測試，以保證程序的穩(wěn)定。測試數(shù)據(jù)及測試結(jié)果請?jiān)谏辖坏馁Y料中寫明；

2.飛機(jī)訂票系統(tǒng)（限1人完成）

任務(wù)：通過此系統(tǒng)可以實(shí)現(xiàn)如下功能：

錄入：

可以錄入航班狀況（數(shù)據(jù)可以存儲在一個數(shù)據(jù)文件中，數(shù)據(jù)結(jié)構(gòu)、詳細(xì)數(shù)據(jù)自定）

查詢：

可以查詢某個航線的狀況（如，輸入航班號，查詢起降時間，起飛抵達(dá)城市，航班票價，票價折扣，確定航班是否滿倉）；

可以輸入起飛抵達(dá)城市，查詢飛機(jī)航班狀況；

訂票：（訂票狀況可以存在一個數(shù)據(jù)文件中，結(jié)構(gòu)自己設(shè)定）

可以訂票，假如該航班已經(jīng)無票，可以供應(yīng)相關(guān)可選擇航班；

退票：可退票，退票后修改相關(guān)數(shù)據(jù)文件；

客戶資料有姓名，證件號，訂票數(shù)量及航班狀況，訂單要有編號。

修改航班信息：

當(dāng)航班信息轉(zhuǎn)變可以修改航班數(shù)據(jù)文件

要求：

依據(jù)以上功能說明，設(shè)計(jì)航班信息，訂票信息的存儲結(jié)構(gòu)，設(shè)計(jì)程序完勝利能；

3.文章編輯（限1人完成）

功能：輸入一頁文字，程序可以統(tǒng)計(jì)出文字、數(shù)字、空格的個數(shù)。

靜態(tài)存儲一頁文章，每行最多不超過80個字符，共N行；要求（1）分別統(tǒng)計(jì)出其中英文字母數(shù)和空格數(shù)及整篇文章總字?jǐn)?shù)；（2）統(tǒng)計(jì)某一字符串在文章中消失的次數(shù)，并輸出該次數(shù)；（3）刪除某一子串，并將后面的字符前移。

存儲結(jié)構(gòu)使用線性表，分別用幾個子函數(shù)實(shí)現(xiàn)相應(yīng)的功能；

輸入數(shù)據(jù)的形式和范圍：可以輸入大寫、小寫的英文字母、任何數(shù)字及標(biāo)點(diǎn)符號。

輸出形式：（1）分行輸出用戶輸入的各行字符；（2）分4行輸出"全部字母數(shù)"、"數(shù)字個數(shù)"、"空格個數(shù)"、"文章總字?jǐn)?shù)"（3）輸出刪除某一字符串后的文章；

4.紙牌嬉戲（限1人完成）

任務(wù)：編號為1-52張牌，正面對上，從第2張開頭，以2為基數(shù)，是2的倍數(shù)的牌翻一次，直到最終一張牌；然后，從第3張開頭，以3為基數(shù)，是3的倍數(shù)的牌翻一次，直到最終一張牌；然后…從第4張開頭，以4為基數(shù)，是4的倍數(shù)的牌翻一次，直到最終一張牌；...再依次5的倍數(shù)的牌翻一次，6的，7的直到以52為基數(shù)的翻過，輸出：這時正面對上的牌有哪些？

5.宿舍管理查詢軟件（限1人完成）

1)任務(wù)：為宿舍管理人員編寫一個宿舍管理查詢軟件,程序設(shè)計(jì)要求：

A.采納交互工作方式

B.建立數(shù)據(jù)文件，數(shù)據(jù)文件按關(guān)鍵字（姓名、學(xué)號、房號）進(jìn)行排序(冒泡、選擇、插入排序等任選一種)

2)查詢菜單:(用二分查找實(shí)現(xiàn)以下操作)

A.按姓名查詢

B.按學(xué)號查詢

C.按房號查詢

3)打印任一查詢結(jié)果（可以連續(xù)操作）

6.地圖著色問題（限1人完成）

設(shè)計(jì)要求：已知中國地圖，對各省進(jìn)行著色，要求相鄰省所使用的顏色不同，并保證使用的顏色總數(shù)最少。

7.校內(nèi)導(dǎo)航問題（限1人完成）

設(shè)計(jì)要求：設(shè)計(jì)你的學(xué)校的平面圖，至少包括10個以上的場所，每兩個場所間可以有不同的路，且路長也可能不同，找出從任意場所到達(dá)另一場所的最佳路徑（最短路徑）。

8.學(xué)校超市選址問題（帶權(quán)有向圖的中心點(diǎn)）（限1人完成）

設(shè)計(jì)要求：對于某一學(xué)校超市，其他各單位到其的距離不同，同時各單位人員去超市的頻度也不同。請為超市選址，要求實(shí)現(xiàn)總體最優(yōu)。

9.教學(xué)方案編制問題（限1人完成）

設(shè)計(jì)要求：針對計(jì)算機(jī)系本科課程，依據(jù)課程之間的依靠關(guān)系（如離散數(shù)學(xué)應(yīng)在數(shù)據(jù)結(jié)構(gòu)之前開設(shè)）制定課程支配方案，并滿意各學(xué)期課程數(shù)目大致相同。

10.散列法的試驗(yàn)討論（限1人完成）

散列法中，散列函數(shù)構(gòu)造方法多種多樣，同時對于同一散列函數(shù)解決沖突的方法也可以不同。兩者是影響查詢算法性能的關(guān)鍵因素。對于幾種典型的散列函數(shù)構(gòu)造方法，做試驗(yàn)觀看，不同的解決沖突方法對查詢性能的影響。

11.圖書借閱管理系統(tǒng)（限1人完成）

主要分為兩大功能：

1)圖書管理(增加圖書、查詢圖書、刪除圖書、圖書借閱、還書)；

2)會員管理(增加會員、查詢會員、刪除會員、借書信息)；

12.同學(xué)成果管理（限1人完成）

實(shí)現(xiàn)功能：輸入、輸出、插入、刪除、查找、追加、讀入、顯示、保存、拷貝、排序、索引、分類合計(jì)、退出。

13.活期儲蓄帳目管理（限1人完成）

活期儲蓄處理中，儲戶開戶、銷戶、存入、支出活動頻繁，系統(tǒng)設(shè)計(jì)要求：

1)能比較快速地找到儲戶的帳戶，以實(shí)現(xiàn)存款、取款記賬；

2)能比較簡潔，快速地實(shí)現(xiàn)插入和刪除，以實(shí)現(xiàn)開戶和銷戶的需要。

14.二叉排序樹的實(shí)現(xiàn)（限1人完成）

用挨次和二叉鏈表作存儲結(jié)構(gòu)

1)以回車('\n')為輸入結(jié)束標(biāo)志,輸入數(shù)列L，生成一棵二叉排序樹T；

2)對二叉排序樹T作中序遍歷，輸出結(jié)果；

3)輸入元素x,查找二叉排序樹T,若存在含x的結(jié)點(diǎn),則刪除該結(jié)點(diǎn),并作中序遍歷(執(zhí)行操作2)；否則輸出信息“無x”；

15.最小生成樹問題（限1人完成）

設(shè)計(jì)要求：在n個城市之間建設(shè)網(wǎng)絡(luò)，只需保證連通即可，求最經(jīng)濟(jì)的架設(shè)方法。存儲結(jié)構(gòu)采納多種。求解算法多種。

16.通訊錄的制作（限1人完成）

設(shè)計(jì)目的：用〈〈數(shù)據(jù)結(jié)構(gòu)〉〉中的雙向鏈表作數(shù)據(jù)結(jié)構(gòu)，結(jié)合C語言基本學(xué)問。編寫一個通訊錄管理系統(tǒng)。以把所學(xué)數(shù)據(jù)結(jié)構(gòu)學(xué)問應(yīng)用到實(shí)際軟件開發(fā)中去。

設(shè)計(jì)內(nèi)容：本系統(tǒng)應(yīng)完成一下幾方面的功能：

1)輸入信息——enter;

2)顯示信息———display();

3)查找以姓名作為關(guān)鍵字———search();

4)刪除信息———delete();

5)存盤———save();

6)裝入———load();

設(shè)計(jì)要求：

1)每條信息至包含：姓名（NAME）街道（STREET）城市（CITY）郵編（EIP）國家（STATE）幾項(xiàng)

2)作為一個完整的系統(tǒng)，應(yīng)具有友好的界面和較強(qiáng)的容錯力量

3)上機(jī)能正常運(yùn)行，并寫出課程設(shè)計(jì)報(bào)告

17.哈夫曼編碼/譯碼器（限1人完成）

【問題描述】

設(shè)計(jì)一個利用哈夫曼算法的編碼和譯碼系統(tǒng)，重復(fù)地顯示并處理以下項(xiàng)目，直到選擇退出為止。

【基本要求】

1)將權(quán)值數(shù)據(jù)存放在數(shù)據(jù)文件(文件名為data.txt，位于執(zhí)行程序的當(dāng)前名目中)

2)分別采納動態(tài)和靜態(tài)存儲結(jié)構(gòu)

3)初始化：鍵盤輸入字符集大小n、n個字符和n個權(quán)值，建立哈夫曼樹；

4)編碼：利用建好的哈夫曼樹生成哈夫曼編碼；

5)輸出編碼；

6)設(shè)字符集及頻度如下表：

字符空格ABCDEFGHIJKLM

頻度1866413223210321154757153220

字符NOPQRSTUVWXYZ

頻度5763151485180238181161

【進(jìn)一步完成內(nèi)容】

1)譯碼功能；

2)顯示哈夫曼樹；

3)界面設(shè)計(jì)的優(yōu)化。

18.圖書管理系統(tǒng)（限1人完成）

【問題描述】

設(shè)計(jì)一個計(jì)算機(jī)管理系統(tǒng)完成圖書管理基本業(yè)務(wù)。

【基本要求】

1)每種書的登記內(nèi)容包括書號、書名、著、現(xiàn)存量和庫存量；

2)對書號建立索引表（線性表）以提高查找效率；

3)系統(tǒng)主要功能如下：

*采編入庫：新購一種書，確定書號后，登記到圖書帳目表中，假如表中已有，則只將庫存量增加；*借閱：假如一種書的現(xiàn)存量大于0，則借出一本，登記借閱者的書證號和歸還期限，轉(zhuǎn)變現(xiàn)存量；*歸還：注銷對借閱者的登記，轉(zhuǎn)變該書的現(xiàn)存量。

【進(jìn)一步完成內(nèi)容】

1)系統(tǒng)功能的進(jìn)一步完善；

2)索引表采納樹表。

3)設(shè)計(jì)內(nèi)容

4)程序流程圖

5)源程序

6)軟件測試報(bào)告（包括所用到的數(shù)據(jù)及結(jié)果）

19.散列表的設(shè)計(jì)與實(shí)現(xiàn)（限1人完成）

【問題描述】

設(shè)計(jì)散列表實(shí)現(xiàn)電話號碼查找系統(tǒng)。

【基本要求】

1)設(shè)每個記錄有下列數(shù)據(jù)項(xiàng)：電話號碼、用戶名、地址；

2)從鍵盤輸入各記錄，分別以電話號碼和用戶名為關(guān)鍵字建立散列表；

3)采納肯定的方法解決沖突；

4)查找并顯示給定電話號碼的記錄；

5)查找并顯示給定用戶名的記錄。

【進(jìn)一步完成內(nèi)容】

1)系統(tǒng)功能的完善；

2)設(shè)計(jì)不同的散列函數(shù)，比較沖突率；

3)在散列函數(shù)確定的前提下，嘗試各種不同類型處理沖突的方法，考察平均查找長度的變化。

20.走迷宮嬉戲（限1人完成）

程序開頭運(yùn)行時顯示一個迷宮地圖，迷宮中心有一只老鼠，迷宮的右下方有一個糧倉。嬉戲的任務(wù)是使用鍵盤上的方向鍵操縱老鼠在規(guī)定的時間內(nèi)走到糧倉處。

要求：

1)老鼠形象可辨認(rèn)，可用鍵盤操縱老鼠上下左右移動；

2)迷宮的墻足夠牢固，老鼠不能穿墻而過；

3)正確檢測結(jié)果，若老鼠在規(guī)定時間內(nèi)走到糧倉處，提示勝利，否則提示失??；

4)添加編輯迷宮功能，可修改當(dāng)前迷宮，修改內(nèi)容：墻變路、路變墻；

5)找出走出迷宮的全部路徑，以及最短路徑。

利用序列化功能實(shí)現(xiàn)迷宮地圖文件的存盤和讀出等功能

21.挨次結(jié)構(gòu)、動態(tài)鏈表結(jié)構(gòu)下的一元多項(xiàng)式的加法、減法、乘法的實(shí)現(xiàn)。（限1人完成）

設(shè)有一元多項(xiàng)式Am(x)和Bn(x).

Am(x)=A0+A1x1+A2x2+A3x3+…+Amxm

Bn(x)=B0+B1x1+B2x2+B3x3+…+Bnxn

請實(shí)現(xiàn)求M(x)=Am(x)+Bn(x)、M(x)=Am(x)-Bn(x)和M(x)=Am(x)×Bn(x)。

要求：

1)首先判定多項(xiàng)式是否稀疏

2)分別采納挨次和動態(tài)存儲結(jié)構(gòu)實(shí)現(xiàn)；

3)結(jié)果M(x)中無重復(fù)階項(xiàng)和無零系數(shù)項(xiàng)；

4)要求輸出結(jié)果的升冪和降冪兩種排列狀況

22.利用棧求表達(dá)式的值，可供學(xué)校生作業(yè)，并能給出分?jǐn)?shù)。（限1人完成）

要求：建立試題庫文件，隨機(jī)產(chǎn)生n個題目；題目涉及加減乘除，帶括弧的混合運(yùn)算；隨時可以退出；保留歷史分?jǐn)?shù)，能回顧歷史，給出與歷史分?jǐn)?shù)比較后的評價

23.簡易文本編輯器（限1人完成）

要求：

1)具有圖形菜單界面；

2)查找，替換（等長，不等長），插入（插串，文本塊的插入）、塊移動（行塊，列塊移動），刪除

3)可正確存盤、取盤；

4)正確顯示總行數(shù)。

24.二叉樹的中序、前序、后序的遞歸、非遞歸遍歷算法，層次序的非遞歸遍歷算法的實(shí)現(xiàn)，應(yīng)包含建樹的實(shí)現(xiàn)。（限1人完成）

要求：遍歷的內(nèi)容應(yīng)是千姿百態(tài)的。

五、樹與二叉樹的轉(zhuǎn)換的實(shí)現(xiàn)。以及樹的前序、后序的遞歸、非遞歸遍歷算法，層次序的非遞歸遍歷算法的實(shí)現(xiàn)，應(yīng)包含建樹的實(shí)現(xiàn)。

要求：遍歷的內(nèi)容應(yīng)是千姿百態(tài)的。

25.同學(xué)搭配問題（限1人完成）

一班有m個女生,有n個男生(m不等于n),現(xiàn)要開一個舞會.男女生分別編號坐在舞池的兩邊的椅子上.每曲開頭時,依次從男生和女生中各出一人配對跳舞,本曲沒勝利配對者坐著等待下一曲找舞伴.

請?jiān)O(shè)計(jì)一系統(tǒng)模擬動態(tài)地顯示出上述過程,要求如下:

1)輸出每曲配對狀況

2)計(jì)算出任何一個男生(編號為X)和任意女生(編號為Y),在第K曲配對跳舞的狀況.至少求出K的兩個值.

3)盡量設(shè)計(jì)出多種算法及程序,可視狀況適當(dāng)加分

提示:用隊(duì)列來解決比較便利.

26.敢死隊(duì)問題（限1人完成）

有M個敢死隊(duì)員要炸掉敵人的一碉堡，誰都不想去，排長打算用輪回?cái)?shù)數(shù)的方法來打算哪個戰(zhàn)士去執(zhí)行任務(wù)。假如前一個戰(zhàn)士沒完成任務(wù)，則要再派一個戰(zhàn)士上去?，F(xiàn)給每個戰(zhàn)士編一個號，大家圍坐成一圈，任憑從某一個戰(zhàn)士開頭計(jì)數(shù)，當(dāng)數(shù)到5時，對應(yīng)的戰(zhàn)士就去執(zhí)行任務(wù)，且此戰(zhàn)士不再參與下一輪計(jì)數(shù)。假如

此戰(zhàn)士沒完成任務(wù)，再從下一個戰(zhàn)士開頭數(shù)數(shù)，被數(shù)到第5時，此戰(zhàn)士接著去執(zhí)行任務(wù)。以此類推，直到任務(wù)完成為止。

排長是不情愿去的，假設(shè)排長為1號，請你設(shè)計(jì)一程序，求出從第幾號戰(zhàn)士開頭計(jì)數(shù)才能讓排長最終一個留下來而不去執(zhí)行任務(wù)。

要求：至少采納兩種不同的數(shù)據(jù)結(jié)構(gòu)的方法實(shí)現(xiàn)。假如采納三種以上的方法者，可加分。

27.猴子吃桃子問題（限1人完成）

有一群猴子摘了一堆桃子，他們每天都吃當(dāng)前桃子的一半且再多吃一個，到了第10天就只余下一個桃子。用多種方法實(shí)現(xiàn)求出原來這群猴子共摘了多少個桃子。

要求：

1)采納數(shù)組數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)上述求解

2)采納鏈數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)上述求解

3)采納遞歸實(shí)現(xiàn)上述求解

4)假如采納4種方法者,適當(dāng)加分

28.數(shù)制轉(zhuǎn)換問題（限1人完成）

任意給定一個M進(jìn)制的數(shù)x，請實(shí)現(xiàn)如下要求

1)求出此數(shù)x的10進(jìn)制值（用MD表示）

2)實(shí)現(xiàn)對x向任意的一個非M進(jìn)制的數(shù)的轉(zhuǎn)換。

3)至少用兩種或兩種以上的方法實(shí)現(xiàn)上述要求（用棧解決，用數(shù)組解決，其它方法解決）。

29.排序綜合（限1人完成）

利用隨機(jī)函數(shù)產(chǎn)生N個隨機(jī)整數(shù)（20000以上），對這些數(shù)進(jìn)行多種方法進(jìn)行排序。

要求：

1)至少采納三種方法實(shí)現(xiàn)上述問題求解（提示，可采納的方法有插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序）。并把排序后的結(jié)果保存在不同的文件中。

2)統(tǒng)計(jì)每一種排序方法的性能（以上機(jī)運(yùn)行程序所花費(fèi)的時間為準(zhǔn)進(jìn)行對比），找出其中兩種較快的方法。

3)假如采納4種或4種以上的方法者，可適當(dāng)加分。

30.同學(xué)成果管理系統(tǒng)（限1人完成）

現(xiàn)有同學(xué)成果信息文件1（1.txt），內(nèi)容如下

姓名學(xué)號語文數(shù)學(xué)英語

張明明01677882

李成友02789188

張輝燦03688256

王露04564577

陳東明05673847

….......…

同學(xué)成果信息文件2（2.txt）,內(nèi)容如下:

姓名學(xué)號語文數(shù)學(xué)英語

陳果31576882

李華明32889068

張明東33484256

李明國34504587

陳道亮35475877

….......…

試編寫一管理系統(tǒng),要求如下:

1)實(shí)現(xiàn)對兩個文件數(shù)據(jù)進(jìn)行合并,生成新文件3.txt

2)抽取出三科成果中有補(bǔ)考的同學(xué)并保存在一個新文件4.txt

3)對合并后的文件3.txt中的數(shù)據(jù)按總分降序排序(至少采納兩種排序方法實(shí)現(xiàn))

4)輸入一個同學(xué)姓名后,能查找到此同學(xué)的信息并輸出結(jié)果(至少采納兩種查找方法實(shí)現(xiàn))

5)要求使用結(jié)構(gòu)體,鏈或數(shù)組等實(shí)現(xiàn)上述要求.

6)采納多種方法且算法正確者,可適當(dāng)加分.

31.圖的遍歷和生成樹求解實(shí)現(xiàn)（限1人完成）

要求：

1)先任意創(chuàng)建一個圖；

2)圖的DFS,BFS的遞歸和非遞歸算法的實(shí)現(xiàn)

3)最小生成樹（兩個算法）的實(shí)現(xiàn)，求連通重量的實(shí)現(xiàn)

4)要求用鄰接矩陣、鄰接表、十字鏈表多種結(jié)構(gòu)存儲實(shí)現(xiàn)

32.線索二叉樹的應(yīng)用（限1人完成）

要求：實(shí)現(xiàn)線索樹建立、插入、刪除、恢復(fù)線索的實(shí)現(xiàn)。

33.稀疏矩陣應(yīng)用（限1人完成