《算法與數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計題目及任務(wù)書

1、課程設(shè)計題目課程設(shè)計題一：學生成績管理系統(tǒng) 設(shè)計目的： 1. 掌握線性鏈表的建立。2. 掌握線性鏈表的基本操作。3. 掌握查找的基本算法。設(shè)計內(nèi)容： 利用線性鏈表實現(xiàn)學生成績管理系統(tǒng)，具體功能：輸入、輸出、插入、刪除、查找、追加、讀入、顯示、保存、拷貝、排序、索引、分類合計、退出，并能在屏幕上輸出操作前后的結(jié)果。設(shè)計要求：1. 寫出系統(tǒng)需求分析，并建模。2. 輸出操作前后的結(jié)果。課程設(shè)計題二：停車場管理系統(tǒng) 設(shè)計目的： 1. 掌握棧和隊列的建立。2. 掌握棧和隊列的基本操作。3. 深入了解棧和隊列的特性,以便在解決實際問題中靈活運用它們。4. 加深對棧和隊列的理解和認識。設(shè)計內(nèi)容：設(shè)有一個可以

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

3、計要求：1. 以棧模擬停車場,以隊列模擬車場外的便道,按照從終端讀入的輸入數(shù)據(jù)序列進行模擬管理。2. 每一組輸入數(shù)據(jù)包括三個數(shù)據(jù)項：汽車“到達”或“離去”信息、汽車牌照號碼以及到達或離去的時刻。3. 對每一組輸入數(shù)據(jù)進行操作后的輸出信息為：若是車輛到達,則輸出汽車在停車場或便道上的停車位置；若是車輛離去，則輸出汽車在停車場內(nèi)停留的時間和應(yīng)交納的費用(在便道上停留的時間不收費，功能可自己添加)。課程設(shè)計題三：家譜管理系統(tǒng) 設(shè)計目的： 1. 掌握樹的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其特點。2. 掌握樹的基本操作，并在在解決實際問題中靈活運用它們。3. 加深對棧和隊列的理解和認識。設(shè)計內(nèi)容：家譜（或稱族譜）是一

4、種以表譜形式，記載一個以血緣關(guān)系為主體的家族世系繁衍和重要人物事跡的特殊圖書體裁。家譜是中國特有的文化遺產(chǎn)，是中華民族的三大文獻（國史、地志、族譜）之一，屬珍貴的人文資料，對于歷史學、民俗學、人口學、社會學和經(jīng)濟學的深入研究，均有其不可替代的獨特功能。本課程設(shè)計對家譜管理進行簡單的模擬，以實現(xiàn)查看祖先和子孫個人信息、插入家族成員、刪除家族成員等功能。設(shè)計要求：完成對家譜成員信息的建立、查找、插入、修改、刪除等功能，可以首先定義家族成員的數(shù)據(jù)結(jié)構(gòu)，然后將每個功能寫成一個函數(shù)來完成對數(shù)據(jù)的操作，最后完成主函數(shù)以驗證各個函數(shù)功能并得出運行結(jié)果。課程設(shè)計題四：哈夫曼編/譯碼器 設(shè)計目的：1. 掌握建立

5、哈夫曼樹和哈夫曼編碼的方法。2. 掌握哈夫曼編碼的實際應(yīng)用方法。設(shè)計內(nèi)容：利用哈夫曼編碼進行通信可以大大提高信道利用率，縮短信息傳輸時間,降低傳輸成本。但是,這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)預先編碼,在接收端將傳來的數(shù)據(jù)進行譯碼。對于雙工信道(即可以雙向傳輸信息的信道),每端都需要一個完成的編譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫一個哈夫曼的編譯碼系統(tǒng)。設(shè)計要求：1. 初始化。根據(jù)上課時給出的英文字母的使用頻度，建立哈夫曼樹。2. 編碼。利用已建好的哈夫曼樹，對電報正文進行編碼。3. 譯碼。對編碼好的內(nèi)容進行譯碼。4. 打印編碼。5. 打印哈夫曼樹。 課程設(shè)計題五：交通咨詢系統(tǒng)設(shè)計 設(shè)計目的

6、： 1. 熟練掌握迪杰斯特拉算法和費洛伊德算法，能夠利用它們解決最短路徑問題。設(shè)計內(nèi)容：設(shè)計一個交通咨詢系統(tǒng)，能讓旅客咨詢從任一個城市頂點到另一個城市頂點之間的最短路徑問題（可參考教材P187交通圖實例建立無向圖）。設(shè)計分三個部分，一是建立交通網(wǎng)絡(luò)圖的存儲結(jié)構(gòu)；二是解決單源最短路徑問題；最后再實現(xiàn)兩個城市頂點之間的最短路徑問題。最短路徑問題的提出隨著計算機的普及以及地理信息科學的發(fā)展，GIS因其強大的功能得到日益廣泛和深入的應(yīng)用。網(wǎng)絡(luò)分析作為GIS最主要的功能之一，在電子導航、交通旅游、城市規(guī)劃以及電力、通訊等各種管網(wǎng)、管線的布局設(shè)計中發(fā)揮了重要的作用。而網(wǎng)絡(luò)分析中最基本和關(guān)鍵的問題是最短路徑

7、問題。最短路徑不僅僅指一般地理意義上的距離最短，還可以引申到其他的度量，如時間、費用、線路容量等。相應(yīng)地，最短路徑問題就成為最快路徑問題、最低費用問題等。由于最短路徑問題在實際中常用于汽車導航系統(tǒng)以及各種應(yīng)急系統(tǒng)等（110報警、119火警以及醫(yī)療救護系統(tǒng)），這些系統(tǒng)一般要求計算出到出事地點的最佳路線的時間一般在1s-3s，在行車過程中還需要實時計算出車輛前方的行駛路線，這就決定了最短路徑問題的實現(xiàn)應(yīng)該是高效率的。最優(yōu)路徑問題不僅包括最短路徑問題，還有可能涉及到最少時間問題、最少收費（存在收費公路）問題、或者是幾個問題的綜合，這時將必須考慮道路級別、道路流量、道路穿越代價（如紅燈平均等待時間）等

8、諸多因素。但是必須指出的是，一般來說最優(yōu)路徑在距離上應(yīng)該是最短的，但最短路徑在行駛時間和能源消耗的意義上未必是最優(yōu)的。其實，無論是距離最短、時間最快還是費用最低，它們的核心算法都是最短路徑算法。設(shè)計要求： 1. 建立交通網(wǎng)絡(luò)網(wǎng)的存儲結(jié)構(gòu)。2. 總體設(shè)計要畫流程圖。3. 提供程序測試方案。4. 界面友好。課程設(shè)計題六：列車管理系統(tǒng)設(shè)計目的： 綜合運用鏈表知識解決實際問題的能力。設(shè)計內(nèi)容： 設(shè)計火車售票處的計算機系統(tǒng)可以為客戶提供下列各項服務(wù)：1. 查詢列車信息：根據(jù)旅客提出的起始站和終點站名輸出下列信息，列車車次、發(fā)車時刻、到達時刻、運行時間、硬座票價、硬臥票價（分為上中下鋪三種情況）

9、、軟臥票價（分上下兩種情況），以及每個途經(jīng)站點的站名、到達時間、發(fā)車時間、運行里程等信息；2.錄入列車信息；3. 修改列車信息；4. 刪除列車信息；5. 瀏覽所有列車信息；6. 其它必要功能。設(shè)計要求： 1. 要求采用鏈表方式存儲所有列車車次基本信息（如車次名稱等），對于其中的每個列車車次，也采用鏈表方式存儲各個途經(jīng)站點信息；2. 能夠支持查詢、修改、增加、刪除等信息；3. 建議提供保存和打開功能，用戶可以把所有信息保存到硬盤文件上，也可以從硬盤文件上讀取信息；4. 界面要友好。課程設(shè)計題七：尋找關(guān)鍵路徑設(shè)計目的： 1. 熟練掌握圖的存儲表示方法；2. 熟練掌握在AOE和AOV中進行拓撲排序以

10、及尋找關(guān)鍵路徑的算法。設(shè)計內(nèi)容：建立圖的存儲結(jié)構(gòu)，能夠輸入圖的頂點和邊的信息，并存儲到相應(yīng)存儲結(jié)構(gòu)中，再編寫函數(shù)實現(xiàn)圖的關(guān)鍵路徑尋找方法。設(shè)計要求：1. 選擇鄰接矩陣作為有向圖的存儲結(jié)構(gòu)模擬整個過程，并輸出關(guān)鍵路徑。2. 自行設(shè)計數(shù)據(jù)調(diào)試程序課程設(shè)計題八：教學計劃編制問題設(shè)計內(nèi)容：大學的每個專業(yè)都要制訂教學計劃。假設(shè)任何專業(yè)都有固定的學習年限，每學年含兩學期，每學期的時間長度和學分上限均相等。每個專業(yè)開設(shè)的課程都是確定的，而且課程在開設(shè)時間的安排必須滿足先修關(guān)系。每門課程有哪些先修課程是確定的，可以有任意多門，也可以沒有。每門課恰好占一個學期。試在這樣的前提下設(shè)計一個教學計劃編制程序。設(shè)計要求

11、：1. 輸入?yún)?shù)包括：學期總數(shù)，一學期的學分上限，每門課的課程號（固定占3位的字母數(shù)字串）、學分和直接先修課的課程號。2. 允許用戶指定下列兩種編排策略之一：一是使學生在各學期中的學習負擔盡量均勻；二是使課程盡可能地集中在前幾個學期中。3. 若根據(jù)給定的條件問題無解，則報告適當?shù)男畔?；否則，將教學計劃輸出到用戶指定的文件中。計劃的表格格式自行設(shè)計。課程設(shè)計題九：電梯模擬系統(tǒng)（1）模擬某校五層教學樓的電梯系統(tǒng)。該樓有一個自動電梯，能在每層停留。五個樓層由下至上依次稱為地下層、第一層、第二層、第三層和第四層，其中第一層是大樓的進出層，即是電梯的“本壘層”，電梯“空閑”時，將來該層候命。五個樓層從下

12、到上的編號為：0、1、2、3、4。除了地下層外，每一層都有一個要求向下的按鈕除了第四層外，每一層都有一個要求向上的按鈕。對應(yīng)的變量為：CallUp0.3和CallDown1.4。電梯內(nèi)的五個目標層按鈕對應(yīng)的變量為：CallCar0.4。（2）電梯一共有七個狀態(tài)，即正在開門（Opening）、已開門（Opened）、正在關(guān)門（Closing）、已關(guān)門（Closed）、等待（Waiting）、移動（Moving）、減速（Decelerate）。（3）乘客可隨機地進出于任何層。對每個人來說，他有一個能容忍的最長等待時間，一旦等候電梯時間過長，他將放棄。對于在樓層內(nèi)等待電梯的乘客，將插入在等候隊列里，

13、每一層有兩個等候隊列，一隊要求向上，一隊要求向下，用鏈隊列來實現(xiàn)。對于在電梯內(nèi)的乘客，用五個乘客棧來實現(xiàn)，該乘客要去哪一層，就把他放在相應(yīng)編號的棧中，對應(yīng)變量為EleStack04。（4）模擬時鐘從0開始，時間單位為0.1秒。人和電梯的各種動作均要耗費一定的時間單位（簡記為t）：有人進出時，電梯每隔40t測試一次，若無人進出，則關(guān)門關(guān)門和開門各需要20t每個人進出電梯均需要25t電梯加速需要15t上升時，每一層需要51t，減速需要14t下降時，每一層需要61t，減速需要23t如果電梯在某層靜止時間超過300t，則駛回1層候命。（5）按時序顯示系統(tǒng)狀態(tài)的變化過程：發(fā)生的全部人和電梯的動作序列。課

14、程設(shè)計題十：公交線路管理設(shè)計目的本項目是對公交車線路信息的簡單模擬，以完成建立公交路線信息、修改公交路線信息和刪除公交路線信息等功能。設(shè)計思路本項目的實質(zhì)是完成對公交線路信息的建立、查找、插入、修改、刪除等功能，可以首先定義項目的數(shù)據(jù)結(jié)構(gòu)，然后將每個功能寫成一個函數(shù)來完成對數(shù)據(jù)的操作，最后完成主函數(shù)以驗證各個函數(shù)功能并得出運行結(jié)果。數(shù)據(jù)結(jié)構(gòu)公交站點之間的關(guān)系可以是任意的，任意兩個站點之間都可能相關(guān)。而在圖形結(jié)構(gòu)中，結(jié)點之間的關(guān)系可以是任意的，圖中任意兩個數(shù)據(jù)元素之間都可能相關(guān)。所以可以用圖形結(jié)構(gòu)來表示n個公交站點之間以及站點之間可能設(shè)置的公交路線，其中網(wǎng)的頂點表示公交站點，邊表示兩個站點之間的

15、路線，賦予邊的權(quán)值表示相應(yīng)的距離。因為公交路線是有一定的連續(xù)關(guān)系的，如果想輸出從某一個起始點開始到某一終點結(jié)束的公交路線，就需要找到從某一頂點開始的第一個鄰接點和下一個鄰接點。因為在鄰接表中容易找到任一頂點的第一個鄰接點和下一個鄰接點，所以本項目使用了圖的鄰接表存儲結(jié)構(gòu)。鄰接表是圖的一種鏈式存儲結(jié)構(gòu)。在鄰接表中，對圖的每一個頂點建立一個單鏈表，第i個單鏈表中的結(jié)點表示依附于頂點vi的邊（對有向圖是以頂點vi為尾的?。Ｃ總€結(jié)點由三個域組成，其中鄰接點域(adjvex)指示與頂點vi鄰接的點在圖中的位置，鏈域(nextarc)指示下一條邊或弧的結(jié)點；數(shù)據(jù)域(info)存儲和邊或弧相關(guān)的信息，如權(quán)

16、值等。每個鏈表上附設(shè)一個表頭結(jié)點，在表頭結(jié)點中，除了設(shè)有鏈域(firstarc)指向鏈表中第一個結(jié)點之外，還設(shè)有存儲頂點vi的名或其它有關(guān)信息的數(shù)據(jù)域(data)。這些表頭結(jié)點通常以順序結(jié)構(gòu)的形式存儲，以便隨機訪問任意頂點的鏈表。圖的鄰接表存儲表示結(jié)構(gòu)可形式的說明如下：#define MAX_VERTEX_NUM 20 typedef struct ArcNode /弧的結(jié)構(gòu) int adjvex; /該弧所指向的頂點的位置 struct ArcNode *nextarc; /指向下一條弧的指針 InfoType *info; /該弧相關(guān)信息的指針 ArcNode; typedef struct VNode /頂點結(jié)構(gòu) VertexType data; /頂點信息 ArcNode *firstarc; /指向第一條依附該頂點的弧的指針 VNode, AdjListMAX_VERTEX_NUM; typedef struct /圖的結(jié)構(gòu) AdjList vertices; int vexnum, arcnum; /圖的當前頂點數(shù)和弧數(shù) int kind; /圖的種類標志 ALGraph; 課程設(shè)計題十一：智能計算器具體要求是以字符序列的形式從終端輸入語法正確的、不含變量的表達式，并利用給定的優(yōu)先關(guān)系實現(xiàn)對算術(shù)四則混合表達式的求值，并演