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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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