《數(shù)據(jù)結構》課程設計題目課程設計題一：學生成績管理系統(tǒng)

設計目的：掌握線性鏈表的建立。掌握線性鏈表的基本操作。掌握查找的基本算法。設計內(nèi)容：

利用線性鏈表實現(xiàn)學生成績管理系統(tǒng)，具體功能：輸入、輸出、插入、刪除、查找、追加、讀入、顯示、保存、拷貝、排序、索引、分類合計、退出，并能在屏幕上輸出操作前后的結果。

設計要求：寫出系統(tǒng)需求分析，并建模。編程實現(xiàn)，界面友好。輸出操作前后的結果。課程設計題二：停車場管理系統(tǒng)

設計目的：掌握棧和隊列的建立。掌握棧和隊列的基本操作。深入了解棧和隊列的特性，以便在解決實際問題中靈活運用它們。加深對棧和隊列的理解和認識。設計內(nèi)容：

設有一個可以停放n輛汽車的狹長停車場，它只有一個大門可以供車輛進出。車輛按到達停車場時間的早晚依次從停車場最里面向大門口處停放(最先到達的第一輛車放在停車場的最里面)。如果停車場已放滿n輛車，則后來的車輛只能在停車場大門外的便道上等待，一旦停車場內(nèi)有車開走，則排在便道上的第一輛車就進入停車場。停車場內(nèi)如有某輛車要開走，在他之后進入停車場的車都必須先退出停車場為它讓路，待其開出停車場后，這些車輛在依原來的次序進場。每輛車在離開停車場時，都應依據(jù)它在停車場內(nèi)停留的時間長短交費。如果停留在便道上的車未進停車場就要離去，允許其離去，不收停車費，并且仍然保持在便道上等待的車輛的次序。編制程序模擬該停車場的管理。

設計要求：以棧模擬停車場，以隊列模擬車場外的便道，按照從終端讀入的輸入數(shù)據(jù)序列進行模擬管理。每一組輸入數(shù)據(jù)包括三個數(shù)據(jù)項：汽車“到達”或“離去”信息、汽車牌照號碼以及到達或離去的時刻。對每一組輸入數(shù)據(jù)進行操作后的輸出信息為：若是車輛到達，則輸出汽車在停車場或便道上的停車位置；若是車輛離去，則輸出汽車在停車場內(nèi)停留的時間和應交納的費用(在便道上停留的時間不收費，功能自己添加)。課程設計題三：約瑟夫(Joseph)環(huán)

設計目的：掌握單向循環(huán)鏈表的建立。掌握單向循環(huán)鏈表的操作。設計內(nèi)容：

編號是1，2，……，n的n個人按照順時針方向圍坐一圈，每個人只有一個密碼(正整數(shù))。一開始任選一個正整數(shù)作為報數(shù)上限值m，從第一個仍開始順時針方向自1開始順序報數(shù)，報到m時停止報數(shù)。報m的人出列，將他的密碼作為新的m值，從他在順時針方向的下一個人開始重新從1報數(shù)，如此下去，直到所有人全部出列為止。請設計一個程序求出出列順序。

設計要求：利用單向循環(huán)鏈表存儲結構模擬此過程，按照出列的順序輸出各個人的編號。測試數(shù)據(jù)：m的初值為20，n=7，7個人的密碼依次為3，1，7，2，4，7，4，首先m=6，則正確的輸出是什么？輸入數(shù)據(jù)：建立輸入函數(shù)處理輸入的數(shù)據(jù)，輸入m的初值n，輸入每個人的密碼，建立單向循環(huán)鏈表。輸出形式：建立一個輸出函數(shù)，將正確的出列順序輸出。課程設計題四：文學研究助手的實現(xiàn)

設計目的：熟悉串類型的實現(xiàn)方法和文本匹配方法。熟悉一般文字處理軟件的設計方法。設計內(nèi)容：

文學研究人員需要統(tǒng)計某篇英文小說中某些形容詞的出現(xiàn)次數(shù)和位置。試寫一個實現(xiàn)這一目標的文字統(tǒng)計系統(tǒng)，稱為“文學研究助手”。

設計要求：英文小說存于一個文本文件中。待統(tǒng)計的詞匯集合要一次輸入完畢。程序的輸出結果是每個詞的出現(xiàn)次數(shù)和出現(xiàn)位置所在行的行號，格式自行設計。設計題五：稀疏矩陣的運算

設計目的：掌握稀疏矩陣的壓縮存儲方法。掌握稀疏矩陣的基本操作。設計內(nèi)容：

設計一個稀疏矩陣的運算器。

設計要求：動態(tài)創(chuàng)建稀疏矩陣。實現(xiàn)稀疏矩陣的輸出顯示。實現(xiàn)稀疏矩陣的加法。實現(xiàn)稀疏矩陣的減法。實現(xiàn)稀疏矩陣的轉置。

課程設計題六：哈夫曼樹及其應用

設計目的：熟悉樹的各種存儲結構及其特點。掌握建立哈夫曼樹和哈夫曼編碼的方法及帶權路徑長度的計算。設計內(nèi)容：

欲發(fā)一封內(nèi)容為AABBCAB……(共長100字符，其中:A、B、C、D、E、F分別有7、9、12、22、23、27個)的電報報文，實現(xiàn)哈夫曼編碼。

設計要求：分析系統(tǒng)需求。建立哈夫曼樹。進行哈夫曼編碼，并求出平均編碼長度。編程實現(xiàn)2、3步驟。課程設計題七：哈夫曼編/譯碼器

設計目的：掌握建立哈夫曼樹和哈夫曼編碼的方法。掌握哈夫曼編碼的實際應用方法。設計內(nèi)容：

利用哈夫曼編碼進行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)預先編碼，在接收端將傳來的數(shù)據(jù)進行譯碼。對于雙工信道(即可以雙向傳輸信息的信道)，每端都需要一個完成的編\譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫一個哈夫曼的編\譯碼系統(tǒng)。

設計要求：初始化。從終端讀入字符集大小n，以及n個字符和n個權值，建立哈夫曼樹。編碼。利用已建好的哈夫曼樹，對正文進行編碼。譯碼。對編碼好的內(nèi)容進行譯碼。打印編碼。打印哈夫曼樹。課程設計題八：圖的遍歷演示

設計目的：理解圖的基本概念。熟悉圖的各種存儲結構及其構造算法。掌握圖的遍歷方法。設計內(nèi)容：

實現(xiàn)圖的深度優(yōu)先、廣度優(yōu)先遍歷算法，并輸出原圖結構及遍歷結果。

設計要求：兩種遍歷方法必須都要實現(xiàn)。界面友好，函數(shù)功能要劃分合理。程序要加必要的注釋。提供程序測試方案。課程設計題九：交通咨詢系統(tǒng)設計

設計目的：熟練掌握迪杰斯特拉算法熟練費洛伊德求最短路徑算法。能夠解決工程項目實施過程中的關鍵路徑問題。設計內(nèi)容：

設計一個交通咨詢系統(tǒng)，能讓旅客咨詢從任一個城市定點到另一個城市定點之間的最短路徑或最低花費或最少時間等問題。對于不同的咨詢要求、可輸入城市間的路程或所需時間或所需花費。

設計要求：建立交通網(wǎng)絡網(wǎng)的存儲結構?？傮w設計要畫流程圖。提供程序測試方案。界面友好。課程設計題十：航班信息的查詢與檢索

設計目的：深刻理解排序的定義和各種排序方法的特點，并能靈活的應用；掌握描述查找過程的判定樹的構造方法。設計內(nèi)容：

設計民航售票處的計算機系統(tǒng)可以為客戶提供下列各項服務：查詢航線：根據(jù)旅客提出的終點站名輸出下列信息：航班號、飛機號、星期幾飛行、最近一天航班的日期和余票額；

承辦訂票業(yè)務：根據(jù)客戶提出的要求(航班號、訂票數(shù)額)查詢該航班票額情況。

設計要求：對飛機航班信息進行排序和查找?？砂春桨嗟暮桨嗵枴⑵瘘c站、到達站、起飛時間以及到達時間等信息進行查詢。采用基數(shù)排序法對一組具有結構特點的飛機航班號進行排序。利用二分查找法對排好序的航班記錄按航班號實現(xiàn)快速排序。每個航班記錄包括八項，分別為：航班號、起點站、終點站、班期、起飛時間、到達時間、飛機型號以及票價等。課程設計題十一、算術表達式求值設計目的：掌握棧的建立。掌握棧的基本操作。深入了解棧的特性，以便在解決實際問題中靈活運用它們。加深對棧的理解和認識。設計內(nèi)容：對帶括號的任意算術表達式求值。設計要求：利用棧判斷表達式的正確性，括號是否匹配。利用棧進行任意帶括號的算術表達式的四則混合運算。數(shù)據(jù)類型為浮點型。課程設計題十二：一元多項式相加設計目的：掌握線性鏈表的建立。掌握線性鏈表的基本操作。掌握線性鏈表合并的算法。設計內(nèi)容：

利用鏈表實現(xiàn)一元多項式相加。設計要求：一元多項式需要動態(tài)建立?；仫@一元多項式的具體表達式。一元多項式的項數(shù)不能是固定值，由鍵盤任意輸入。程序應能進行循環(huán)運算，不需運算時，選擇相應退出功能。課程設計題十三：二叉樹基本操作設計目的：掌握二叉樹的二叉鏈表存儲方式。掌握二叉樹的建立。掌握二叉樹的遍歷方法：先序、中序、后序遍歷。掌握二叉樹的基本性質(zhì)。設計內(nèi)容：

利用二叉鏈表建立二叉樹并實現(xiàn)其基本操作。設計要求：按先序次序輸入二叉樹中節(jié)點的值，動態(tài)建立二叉樹。輸出二叉樹的先序、中序、后序遍歷序列。輸出二叉樹中結點個數(shù)。輸出二叉樹的深度。課程設計題十四：拓撲排序的應用設計目的：掌握有向圖鄰接表存儲結構掌握AOV網(wǎng)深刻理解拓撲排序設計內(nèi)容：以本專業(yè)課程系統(tǒng)為例，以本專業(yè)課程系統(tǒng)為例，根據(jù)課程之間的依賴關系制定課程安排計劃，并滿足各學期課程數(shù)目大致相同。設計要求：輸入本專業(yè)在大學期間的所有課程，并顯示課程之間的關系。按8學期計算，使課程盡可能安排在前幾個學期，課程數(shù)不少于16門。給出教學計劃，即每學期應該如何安排課程，才能滿足課程間的依賴關系。課程設計題十五：圖書管理系統(tǒng)

設計目的：掌握順序表的堆分配存儲方式。掌握順序表的基本操作。正確應用查找算法。正確應用排序算法。設計內(nèi)容：

利用順序表實現(xiàn)圖書管理系統(tǒng)。

設計要求：實現(xiàn)圖書信息的基本操作輸入、輸出、插入、刪除、追加、顯示、保存、實現(xiàn)查找功能（按不同關鍵字查找）。實現(xiàn)排序功能（按不同關鍵字排序）。具有分類統(tǒng)計功能。課程設計題十六：宿舍管理查詢系統(tǒng)設計目的：掌握順序表的存儲方式。掌握基本的排序算法。掌握二分查找等查找算法。設計內(nèi)容：為學生宿舍管理人員編寫一個能進行宿舍管理、查詢軟件。設計要求：建立關于宿舍及學生的數(shù)據(jù)文件，數(shù)據(jù)文件按關鍵字（姓名、學號、房號）進行排序(冒泡、選擇、插入排序等任選一種)查詢菜單：用二分查找實現(xiàn)按姓名查詢、按學號查詢、按房號查詢。課程設計題十七：構造可以使n個城市連接的最小生成樹（限1人完成）設計目的：掌握圖的鄰接矩陣的存儲方式掌握Prim或Kruskal最小生成樹的算法設計內(nèi)容：給定一個地區(qū)的n個城市間的距離網(wǎng)，用Prim算法或Kruskal算法建立最小生成樹，并計算得到的最小生成樹的代價。設計要求：城市間的距離網(wǎng)采用鄰接矩陣表示，鄰接矩陣的存儲結構定義采用課本中給出的定義，若兩個城市之間不存在道路，則將相應邊的權值設為自己定義的無窮大值。要求在屏幕上顯示得到的最小生成樹中包括了哪些城市間的道路，并顯示得到的最小生成樹的代價。表示城市間距離網(wǎng)的鄰接矩陣（要求至少6個城市，10條邊）最小生成樹中包括的邊及其權值，并顯示得到的最小生成樹的代價。課程設計題十八：文本文件單詞的檢索與計數(shù)設計目的：熟悉串類型的實現(xiàn)方法和文本匹配方法。熟悉一般文字處理軟件的