13-14-1 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計題目

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

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

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

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

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

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

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

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

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

設(shè)計要求：利用單向循環(huán)鏈表存儲結(jié)構(gòu)模擬此過程，按照出列的順序輸出各個人的編號。測試數(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ù)，將正確的出列順序輸出。課程設(shè)計題四：文學(xué)研究助手的實現(xiàn)

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

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

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

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

設(shè)計一個稀疏矩陣的運算器。

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

課程設(shè)計題六：哈夫曼樹及其應(yīng)用

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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