淮陰工學院2008級
資料結構課程設計指導書
殷路王文豪
2023年4月10日
一．資料結構課程設計要求
學生必須仔細閱讀《資料結構》課程設計方案，認真主動完成課程設計的要求。有問題及時主動通過各種方式與教師聯絡溝通。
學生要發揮自主學習的能力，充分利用時間，安排好課程設計的時間計畫，設計程式並除錯。
在課程設計周，主要是進行課程設計的答辯工作，期間也繼續進行的除錯與完善工作，上機時數通常為12~15小時。
資料結構是一門涉及多門課程的課程，難度較大，需要較好的c/c++語言的程式設計和除錯能力，如果學生能夠按照要求，從時間和精力上保證完全的投入，相信能夠有很大的收穫，幾分投入幾分收穫。
二．資料結構課程設計題
每組至少完成乙個課題，多完成可加附加分。
1. 學生管理系統（7）
包括：主控程式、學生檔案管理子系統、學生成績管理子系統、學生宿舍管理子系統
人數：2人
要求：實用，各模組自成系統
2. 圖書館管理系統，包括：圖書管理子系統、圖書借閱子系統、還書子系統、借閱人管理子系統、圖書報損子系統等（8）
【基本要求】
(1)每種書的登記內容包括書號、書名、著作者、現存量和庫存量；
(2)對書號建立索引表（線性表）以提高查詢效率；
(3)系統主要功能如下：
*採編入庫：新購一種書，確定書號後，登記到圖書帳目表中，如果表中已有，則只將庫存量增加；
*借閱：如果一種書的現存量大於0，則借出一本，登記借閱者的書證號和歸還期限，改變現存量；
*歸還：登出對借閱者的登記，改變該書的現存量。
人數：3人
要求：實用
3. 航空售票處的服務系統（7）
任務：通過此系統可以實現如下功能：
（1） 錄入：可以錄入航班情況（資料可以儲存在乙個資料檔案中，資料結構、具體資料自定）
（2） 查詢：可以查詢某個航線的情況（如，輸入航班號，查詢起降時間，起飛抵達城市，航班票價，票價折扣，確定航班是否滿倉）；
（3） 可以輸入起飛抵達城市，查詢飛機航班情況；
（4） 訂票：（訂票情況可以存在乙個資料檔案中，結構自己設定）
可以訂票，如果該航班已經無票，可以提供相關可選擇航班；
（5） 退票：可退票，退票後修改相關資料檔案；
客戶資料有姓名，證件號，訂票數量及航班情況，訂單要有編號。
（6） 修改航班資訊：當航班資訊改變可以修改航班資料檔案。
要求：根據以上功能說明，設計航班資訊，訂票資訊的儲存結構，設計程式完成功能。
4. 跳馬問題,就是64個西洋棋格仔,任意位置放乙個馬,如何不重複地把格仔走完。（8）
人數：1人
要求：實用
5. 運動會（7）
題目描述：
參加運動會的n個學校編號為1—n。比賽分為m個男子專案和w個女子專案，專案編號分別為1—m和m+1—m+w。由於各項目的參加人數差別較大，有些專案取前五名，得分順序為7，5，3，2，1；還有些專案只取前三名，得分順序為5，3，2。
寫乙個統計程式產生各種成績單和得分報表。
基本要求：
產生各校的成績單，內容包括各學校所取得每項成績的專案號，名次（成績），姓名和得分；產生團體總分報表，內容包括校號，男子團體總分，女子團體總分和團體總分。
測試資料：
對於n=4，m=3，w=2，編號為奇數的專案取前5名，編號為偶數的專案取前3名，設計一組例項資料。
提示：可以假設n小於等於20，m小於等於30，w小於等於20，姓名長度不超過20個字元。每個專案結束時，將其編號，型別符（區分取前5名還是3名）輸入，並按名次順序輸入運動員姓名，校號（和成績）。
人數：2人
要求：實用
6.建通訊錄（7）
要求：第乙個模組——主函式main()的功能是：根據選單的選項呼叫各函式，並完成相應的功能。
第二個模組——menu()的功能是：顯示英文提示選單。
第三個模組——quit()的功能是：退出選單。
第四個模組——create()的功能是：建立新的通訊錄。
第五個模組——add()的功能是：在通訊錄的末尾，寫入新的資訊，並返回選單。
第六個模組——find()的功能是：查詢某人的資訊，如果找到了，則顯示該人的資訊，如果未找到，則提示通訊錄中沒有此人的資訊，並返回選單。
第七個模組——alter()的功能是：修改某人的資訊，如果未找到要修改的人，則提示通訊錄中沒有此人的資訊，並返回選單。
第八個模組——delete()的功能是：刪除某人的資訊，如果未找到要刪除的人，則提示通訊錄中沒有此人的資訊，並返回選單。
第九個模組——list()的功能是：顯示通訊錄中的所有記錄。
人數：2人
要求：實用
7. 用撲克牌實現24點遊戲。（8）
人數：1人
要求：實用
8. 哈夫曼編碼/解碼器1（8）
【問題描述】
設計乙個利用哈夫曼演算法的編碼和解碼系統，重複地顯示並處理以下專案，直到選擇退出為止。
【基本要求】
(1)初始化：鍵盤輸入字符集大小n、n個字元和n個權值，建立哈夫曼樹；
(2)編碼：利用建好的哈夫曼樹生成哈夫曼編碼；
(3)輸出編碼；
(4)解碼功能；
(5)設字符集及頻度如下表：
字元空格 a b c d e f g h i j k l m
頻度 186 64 13 22 32 103 21 15 47 57 1 5 32 20
字元 n o p q r s t u v w x y z
頻度 57 63 15 1 48 51 80 23 8 18 1 16 1
【選做內容】
(1) 顯示哈夫曼樹；
(2) 介面設計的優化。
(3) 哈夫曼編碼/解碼均用二進位制處理。（10）
9. 一元稀疏多項式計算器（8）
【問題描述】
設計乙個一元多項式加法器。
【基本要求】
(1)輸入並建立多項式；
(2)兩個多項式相加；
(3)輸出多項式：n, c1, e1, c2, e2, …cn , en, 其中，n是多項式項數，ci和ei分別是第 i 項的係數和指數，序列按指數降序排列。
(4)計算多項式在x處的值；
(5)求多項式的導函式。
人數：2人
要求：實用
10. 停車場管理1（8）
設有乙個可以停放n輛汽車的狹長停車場，它只有乙個大門可以供車輛進出。車輛按到達停車時間的早晚依次從停車場最裡面向大門口停放(最先到達的第一輛車放在停車場的最裡面)。如果停車場已放滿n輛車，則後來的車輛只能在停車場大門外的便道上等待，一旦停車場內有車開走，則排在便道上的第一輛車就進入停車場。
停車場內如有某輛車要開走，在它之後近來的車都必須先退出停車場為它讓路，待其開出停車場後，這些車輛再依原來的次序進場。每輛車在離開停車場時，都應根據它在停車場內停留的時間長短交費。如果停留在便道上的車未進停車場就要離去，允許其離去，不收停車費，並且仍然保持在便道上等待的車輛的次序。
編制一程式模擬停車場管理。
實現提示：汽車的模擬輸入資訊格式可以是：(到達/離去，汽車牌照號碼，到達/離去的時刻)。
例如：('a',1,5)表示一號牌照車愛5這個時刻到達，而('d',5,20)表示5號牌照車在20這個時刻離去，整個程式可以在輸入資訊為('e',0,0)時結束。
基本要求：要求程式輸出每輛車到達後的停車位置(停車場或便道上)，以及某輛車離開停車場時應交納的費用和它在停車場內停留的時間。
人數：1人
要求：實用
11.停車場管理2（9）
（1） 有乙個兩層的停車場, 每層有6個車位, 當第一層車停滿後才允許使用第二層. ( 停車場可用乙個二維陣列實現, 每個陣列元素存放乙個車牌號 ) 每輛車的資訊包括車牌號, 層號, 車位號, 停車時間共4項. 其中停車時間按分鐘計算
（2） 假設停車場初始狀態為第一層已經停有4輛車, 其車位號依次為1—4 , 停車時間依次為20, 15, 10 , 5 . 即先將這四輛車的資訊存入檔案」中( 陣列的對應元素也要進行賦值 )
（3） 停車操作: 當一輛車進入停車場時, 先輸入其車牌號, 再為它分配乙個層號和乙個車位號(分配前先查詢車位的使用情況, 如果第一層有空則必須停在第一層), 停車時間設為5 , 最後將新停入的汽車的資訊新增檔案」中, 並將在此之前的所有車的停車時間加5.
（4） 收費管理(取車): 當有車離開時, 輸入其車牌號, 先按其停車時間計算費用, 每5分鐘0.2元.
(停車費用可設定乙個變數進行儲存), 同時從檔案」中刪除該車的資訊, 並將該車對應的車位設定為可使用狀態(即二維陣列對應元素清零). 按使用者的選擇來判斷是否要輸出停車收費的總計.
（5） 輸出停車場中全部車輛的資訊.
（6） 退出系統.
人數：2人
要求：實用
12. 火車訂票系統 （8）
要求：有訂票子系統、售票子系統、退票子系統、統計子系統、查詢子系統、生成資料子系統
人數：3人
要求：實用
13.五子棋（9）
要求：人機對戰
人數：2人
要求：實用
14. 迷宮問題（7.5）
問題描述：迷宮實驗是取自心理學的乙個古典實驗。在該實驗中，把乙隻老鼠從乙個無頂大盒子的門放入，在盒中設定了許多牆，對行進方向形成了多處阻擋。
盒子僅有乙個出口，在出口處放置一塊乳酪，吸引老鼠在迷宮中尋找道路以到達出口。對同一只老鼠重複進行上述實驗，一直到老鼠從入口到出口，而不走錯一步。老鼠經多次試驗終於得到它學習走迷宮的路線。
設計乙個電腦程式對任意設定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結論。
要求：在給出入口和出口的前提下，給出動態的迷宮行走路線。
人數：1人
【選做內容】給出所有可行路線。（8）
15. 八皇后問題 （7）
要求：試編寫程式實現將八個皇后放置在西洋棋棋盤的無衝突的位置上的演算法，並給出所有的解。
提示：在西洋棋上放置皇后時，任何乙個皇后的水平、豎直和斜45都不能有另乙個皇后。解決該問題採用逐次試探的方法，即採用遞迴呼叫putchess函式的方法。
首先將第乙個皇后放於第一行第一列，然後開始向下一行遞迴。每一步遞迴中，首先檢測待放置位置是否與已放置的皇后衝突，如不衝突，則進行下一行的放置，否則，選擇該行的下乙個位置進行檢測。如整行的位置都衝突，則回到上一行，重新選擇位置。
人數：1人
16. 無向圖應用問題（7）
任務：如果以無向網表示n個城市之間通訊網路的建設計畫，頂點表示城市，邊上的權表示該線路的造價，設計乙個方案，使這個通訊網的總造價最低。
提示：這是乙個求最小生成樹的問題。n個城市名和各邊的權值由使用者輸入，建立圖的鄰接矩陣，然後以prim演算法來求最小生成樹，然後輸出方案。
人數：1人
17. 中國象棋（10）
要求：人機對戰
人數：3人（人人對戰為2人）
要求：實用
18. 二叉排序樹。用二叉鍊錶作儲存結構。（8）
要求：(1)以回車('\n')為輸入結束標誌,輸入數列l，生成一棵二叉排序樹t；
(2)對二叉排序樹t作中序遍歷，輸出結果；
(3)計算二叉排序樹t查詢成功的平均查詢長度,輸出結果；
(4)輸入元素x,查詢二叉排序樹t,若存在含x的結點,則刪除該結點,並作中序遍歷(執行操作2)；否則輸出資訊「無x」。
人數：2人
要求：實用
19. 二叉排序樹。用順序表(一維陣列)作儲存結構 （8）
(1)以回車('\n')為輸入結束標誌,輸入數列l，生成一棵二叉排序樹t；
(2)對二叉排序樹t作中序遍歷,輸出結果；
(3)計算二叉排序樹t查詢成功的平均查詢長度,輸出結果；
(4)輸入元素x,查詢二叉排序樹t:若存在含x的結點,則刪除該結點,並作中序遍歷(執行操作2)；否則輸出資訊「無x」；
資料結構課程設計指導2019
課程設計名稱 資料結構課程設計指導老師 歐陽勇 課程設計周 時 數 1周 指導方式 集體輔導與個別輔導相結合 課程設計適用專業 電腦科學與技術 課程設計教材及主要參考資料 1 資料結構 嚴蔚敏編著，清華大學出版社 一 課程設計教學目的及基本要求 1 了解並掌握資料結構與演算法的設計方法，具備初步的獨...
資料結構課程設計
指導書山東建築大學 電腦科學與技術學院 二 六年十二月 課程設計基本情況 課程名稱 資料結構課程設計 相關課程 c語言程式設計 visual c 程式設計 資料結構 適合專業 電腦科學與技術 網路工程 軟體工程 設計週數 2周 學分 2學分 開課學期 第4學期 開課單位 電腦科學與技術學院 一 課程...
資料結構課程設計
總結報告 專業軟體工程 班級軟體1007 學號 20103540 姓名 日期 2012.9.17 東北大學軟體學院 第一章需求分析 問題定義 實現乙個網上拍賣系統，根據需求描述和附加的框架 完成乙個網上拍賣系統。分析 整個系統執行於windows平台，是基於b s結構的商業應用程式，程式為使用者提供...