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

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

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

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

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

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

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

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

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

編號(hào)是1，2，……，n的n個(gè)人按照順時(shí)針?lè)较驀蝗Γ總€(gè)人只有一個(gè)密碼(正整數(shù))。一開(kāi)始任選一個(gè)正整數(shù)作為報(bào)數(shù)上限值m，從第一個(gè)仍開(kāi)始順時(shí)針?lè)较蜃?開(kāi)始順序報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)。報(bào)m的人出列，將他的密碼作為新的m值，從他在順時(shí)針?lè)较虻南乱粋€(gè)人開(kāi)始重新從1報(bào)數(shù)，如此下去，直到所有人全部出列為止。請(qǐng)?jiān)O(shè)計(jì)一個(gè)程序求出出列順序。

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

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

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

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

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

設(shè)計(jì)一個(gè)稀疏矩陣的運(yùn)算器。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

承辦訂票業(yè)務(wù)：根據(jù)客戶提出的要求(航班號(hào)、訂票數(shù)額)查詢?cè)摵桨嗥鳖~情況。

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

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

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

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

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

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