東北大學(xué)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告

1、課程編號(hào)：B080101050數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告姓名郝偉學(xué)號(hào)20144805班級(jí)軟工1409指導(dǎo)教師張莉?qū)嶒?yàn)名稱數(shù)據(jù)結(jié)構(gòu)綜合實(shí)驗(yàn)開(kāi)發(fā)與總結(jié)開(kāi)設(shè)學(xué)期2014-2015第二學(xué)期開(kāi)設(shè)時(shí)間第4周第18周報(bào)告日期評(píng)定成績(jī)?cè)u(píng)定人張莉評(píng)定日期2015-07-15東北大學(xué)軟件學(xué)院數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告 東北大學(xué)軟件學(xué)院1. 實(shí)驗(yàn)?zāi)康尼槍?duì)每次實(shí)驗(yàn)，寫出你認(rèn)為比較重要的實(shí)驗(yàn)?zāi)康膶?shí)驗(yàn)一：1、了解和掌握隊(duì)列的數(shù)據(jù)類型描述及其特點(diǎn)。2、掌握隊(duì)列初始化、入隊(duì)、出隊(duì)等相關(guān)基本操作的實(shí)現(xiàn)方法，從而達(dá)到能靈活運(yùn)用隊(duì)列解決應(yīng)用問(wèn)題的目的實(shí)驗(yàn)二：1、加深對(duì)圖的表示法和圖的基本操作的理解，并可初步使用及操作；2、掌握用圖對(duì)實(shí)際問(wèn)題進(jìn)行抽象方

2、法，可以解決基本的問(wèn)題；3、掌握利用鄰接表求解非負(fù)權(quán)值、單源最短路徑的方法，即利用迪杰斯特拉算法 求最短路徑，同時(shí)掌握鄰接表的建立以及使用方法，能夠解決相關(guān)的問(wèn)題。4、學(xué)會(huì)使用STL中的map抽象實(shí)際問(wèn)題，掌握map，List的應(yīng)用。2. 實(shí)驗(yàn)內(nèi)容與實(shí)驗(yàn)步驟2.1打印機(jī)模擬程序的內(nèi)容與步驟(1) 簡(jiǎn)短明確地寫出實(shí)驗(yàn)的內(nèi)容仿真一個(gè)網(wǎng)絡(luò)打印過(guò)程(2) 簡(jiǎn)短描述抽象數(shù)據(jù)類型或設(shè)計(jì)的函數(shù)描述，說(shuō)明為什么要使用這種抽象數(shù)據(jù)類型，并說(shuō)明你的解決設(shè)想使用隊(duì)列存放等待打印的作業(yè)序列 queue<event> wait; 因?yàn)殛?duì)列的特點(diǎn)就是先進(jìn)先出十分適合打印機(jī)的需求首先判斷作業(yè)是否到達(dá)，若到達(dá)輸出

3、相關(guān)信息，最后加入到wait中然后判斷打印機(jī)是否空閑，若空閑且wait中有作業(yè)的話，按照先后順序打印 (3) 簡(jiǎn)短明確地寫出你實(shí)驗(yàn)所采用的存儲(chǔ)結(jié)構(gòu)及其用途，詳細(xì)說(shuō)明其中的屬性的含義。存儲(chǔ)結(jié)構(gòu)：queue<event> wait;用途：存放等待打印的作業(yè)序列主要屬性：2.2歐洲旅行實(shí)驗(yàn)的內(nèi)容與步驟(1) 簡(jiǎn)短明確地寫出實(shí)驗(yàn)的內(nèi)容求兩個(gè)城市之間的最便宜的乘車路線(2) 簡(jiǎn)短描述你在實(shí)驗(yàn)中使用的數(shù)據(jù)結(jié)構(gòu)及算法的基本原理。數(shù)據(jù)結(jié)構(gòu)使用Map來(lái)實(shí)現(xiàn)圖的存貯 鍵：城市名，值：該城市與相鄰城市的邊的鏈表使用Map實(shí)現(xiàn)城市的存貯，鍵：城市名，值：該城市所對(duì)應(yīng)的實(shí)體類使用priority_queue

4、存放未被標(biāo)記為最短路徑的城市算法：使用 Dijkstra's shortest path algorithm 。1）待用戶輸入起點(diǎn)與終點(diǎn)城市后，調(diào)用reset方法重置Map中city中的信息 2） 首先將起點(diǎn)城市的標(biāo)記為最短路徑的城市，然后將它的相鄰城市加入priority_queue.3)開(kāi)始循環(huán)，更新最短路徑信息選出priority_queue中路徑最短的城市 a，。然后將它從priority_queue刪除。遍歷城市a的鄰接城市 如果該相鄰城市b不在最短路徑節(jié)點(diǎn)中， 則判斷 若起點(diǎn)城市到b城市原本無(wú)路可走，則添加此路徑，通 過(guò)a城市中轉(zhuǎn) 若原路徑費(fèi)用更大則修改為通過(guò)a城市中轉(zhuǎn) 最

5、后將此城市加入優(yōu)先級(jí)隊(duì)列中 直到priority_queue為空為止(3) 描述你采用STL中的什么容器或者類實(shí)現(xiàn)圖的存儲(chǔ)，在算法應(yīng)用過(guò)程中使用什么數(shù)據(jù)結(jié)構(gòu)或算法提高算法的效率。使用Map來(lái)實(shí)現(xiàn)圖的存貯 鍵：城市名，值：該城市與相鄰城市的邊的鏈表在計(jì)算最小路時(shí)使用priority_queue存放未被標(biāo)記為最短路徑的城市，因?yàn)閜riority_queue可以根據(jù)你寫的排序算法自動(dòng)將最小路徑的城市放在隊(duì)首的位置3. 實(shí)驗(yàn)環(huán)境操作系統(tǒng)、調(diào)試軟件名稱、版本號(hào)，上機(jī)地點(diǎn)，機(jī)器臺(tái)號(hào)操作系統(tǒng)：Windows 10調(diào)試軟件：Dev C+ 版本號(hào)5.9.2上機(jī)地點(diǎn)：信息樓A415 機(jī)器臺(tái)號(hào)：自帶筆記本4. 實(shí)驗(yàn)

6、過(guò)程與分析4.1打印機(jī)模擬程序的過(guò)程分析(1) 描述你在進(jìn)行實(shí)現(xiàn)時(shí)，主要的函數(shù)或操作內(nèi)部的主要算法，分析這個(gè)算法的時(shí)、空復(fù)雜度，并說(shuō)明你設(shè)計(jì)的巧妙之處。主要操作：首先判斷作業(yè)是否到達(dá)，若到達(dá)輸出相關(guān)信息，最后加入到wait隊(duì)列中然后判斷打印機(jī)是否空閑，若空閑且wait中有作業(yè)的話，按照先后順序打印由于等待與打印并發(fā)執(zhí)行：故空間復(fù)雜度為O（n）使用隊(duì)列存貯，故空間復(fù)雜度為O（n）(2) 你在調(diào)試過(guò)程中發(fā)現(xiàn)了怎樣的問(wèn)題？又做了怎樣的改進(jìn)（要求寫出具體的事例）一些打印任務(wù)是同時(shí)到達(dá)的，一開(kāi)始只取出一個(gè)任務(wù)后計(jì)時(shí)器便加一，由此漏掉了一些打印任務(wù)，經(jīng)過(guò)調(diào)試后，在一個(gè)while循環(huán)中加入打印任務(wù)，這樣便可

7、解決。(3) 你的實(shí)現(xiàn)是否具有可擴(kuò)展性，如針對(duì)多個(gè)打印隊(duì)列的仿真程序？不能，程序中沒(méi)有涉及過(guò)同步的有關(guān)內(nèi)容4.2歐洲旅行實(shí)驗(yàn)的過(guò)程分析(1) 描述你在進(jìn)行實(shí)現(xiàn)時(shí)，主要的函數(shù)或操作內(nèi)部的主要算法，分析這個(gè)算法的時(shí)、空復(fù)雜度，并說(shuō)明你設(shè)計(jì)的巧妙之處。void RailSystem:reset(void)：遍歷map類cities中的對(duì)象，將以前產(chǎn)生的信息清除，重新初始化。時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(1)。 void RailSystem:load_services(string const &filename)：導(dǎo)入文件，構(gòu)建鐵路系統(tǒng)的模擬圖。時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(1)。

8、pair<int, int> RailSystem:calc_route(string from, string to)：實(shí)現(xiàn)最小路徑算法，把信息存儲(chǔ)在map<string,City*>中。時(shí)間復(fù)雜度O(n2)，空間復(fù)雜度O(1)。string RailSystem:recover_route(const string& city)：還原從from到to的最小費(fèi)用路徑的路線。時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(1)(2) 你在調(diào)試過(guò)程中發(fā)現(xiàn)了怎樣的問(wèn)題？又做了怎樣的改進(jìn)？一開(kāi)始沒(méi)想明白 reset()的作用，后來(lái)仔細(xì)研究了一下實(shí)際應(yīng)用，就想明白了。(3) 你的實(shí)驗(yàn)

9、在解決類似問(wèn)題時(shí)是否具有靈活的可修改性、可擴(kuò)展性？有一定的可修改性，因?yàn)槲业某绦蚨际且徊讲降慕鉀Q問(wèn)題，較好的實(shí)現(xiàn)了模塊化，并且關(guān)鍵步驟都有注釋5.實(shí)驗(yàn)結(jié)果總結(jié)5.1打印機(jī)模擬程序的結(jié)果總結(jié)回答以下問(wèn)題：(1) 你的測(cè)試充分嗎？為什么？你是怎樣考慮的？充分，與給出的實(shí)驗(yàn)結(jié)果一模一樣(2) 為什么你要選用隊(duì)列作為你應(yīng)用的數(shù)據(jù)結(jié)構(gòu)？因?yàn)殛?duì)列的特點(diǎn)就是先進(jìn)先出十分適合打印機(jī)的需求(3) 用一段簡(jiǎn)短的代碼及說(shuō)明論述你的應(yīng)用中主要的函數(shù)的主要處理部分。(4) 用結(jié)構(gòu)化圖表或者結(jié)構(gòu)化代碼描述源程序的大致的執(zhí)行過(guò)程。等待作業(yè)到達(dá)，若到達(dá)輸出相關(guān)信息，并加入到等待列表中若打印機(jī)空閑且wait中有作業(yè)的話，打印，

10、然后更新所有作業(yè)等待的總時(shí)間，并且計(jì)算出下一次的空閑時(shí)間 計(jì)時(shí)器加一5.2歐洲旅行實(shí)驗(yàn)的的結(jié)果總結(jié)回答以下問(wèn)題：(1) 你的測(cè)試充分嗎？為什么？你是怎樣考慮的？我測(cè)試了多個(gè)城市，結(jié)果都正確(2) 在你的問(wèn)題解決方案中，為圖選取了順序的還是鏈?zhǔn)降拇鎯?chǔ)結(jié)構(gòu)？為什么要選取這種存儲(chǔ)結(jié)構(gòu)？鏈?zhǔn)降拇鎯?chǔ)，因?yàn)榇鎯?chǔ)數(shù)量未知，鏈?zhǔn)街С謩?dòng)態(tài)存儲(chǔ)(3) 用一段簡(jiǎn)短的代碼及說(shuō)明論述你的應(yīng)用中主要的函數(shù)的主要處理部分。(4) 在你的圖中使用了怎么樣數(shù)據(jù)結(jié)構(gòu)來(lái)優(yōu)化算法的性能？在計(jì)算最小路時(shí)使用priority_queue存放未被標(biāo)記為最短路徑的城市，因?yàn)閜riority_queue可以根據(jù)你寫的排序算法自動(dòng)將最小路徑的城

11、市放在隊(duì)首的位置(5) 源程序的大致的執(zhí)行過(guò)程是怎樣的？Reset（刷新）>load(載入文件，構(gòu)建鐵路系統(tǒng)模擬圖)>cac_route(計(jì)算兩城市之 間最短路徑)>print(打印總費(fèi)用和總距離，以及路線)6.附錄(1) 回答思考題a) 棧和隊(duì)列在計(jì)算機(jī)系統(tǒng)中有哪些應(yīng)用？寫出你知道的系統(tǒng)中，這兩種抽象數(shù)據(jù)類型的應(yīng)用。隊(duì)列：處理機(jī)調(diào)度中的fifo算法棧：遞歸時(shí)，將函數(shù)狀態(tài)壓入中b) 在程序調(diào)用的時(shí)侯，需要進(jìn)行函數(shù)的切換，你認(rèn)為函數(shù)在進(jìn)行切換時(shí)系統(tǒng)要做那些工作？當(dāng)調(diào)用一個(gè)函數(shù)時(shí)，將把本函數(shù)的參數(shù)、返回位置、返回值打包壓入棧中。這樣，每退出一個(gè)函數(shù)的調(diào)用，就會(huì)從棧中彈出一條工作記

12、錄，里面記錄了返回值和返回位置，可以使函數(shù)使用完畢后回到本次調(diào)用語(yǔ)句的后繼語(yǔ)句中。類似遞歸工作棧c) 隊(duì)列在系統(tǒng)的設(shè)計(jì)中都起到什么樣的作用？舉出你所熟悉的一些隊(duì)列的應(yīng)用例子。處理機(jī)調(diào)度中的fifo算法d) 在你的兩次實(shí)驗(yàn)中分別使用了STL中的哪些容器？有什么用途？Map存放鍵值對(duì)List 相當(dāng)于動(dòng)態(tài)數(shù)組quene 一種先到先出的存貯結(jié)構(gòu)prority_quene 堆結(jié)構(gòu)e) 假設(shè)一個(gè)圖采用鄰接表存儲(chǔ)結(jié)構(gòu)進(jìn)行存儲(chǔ)，在某一個(gè)結(jié)點(diǎn)的鄰接結(jié)點(diǎn)鏈表中，結(jié)點(diǎn)的順序是否會(huì)影響到最短路徑算法的結(jié)果？不會(huì)，遲早都要被遍歷到，只要路徑不是最短就一定會(huì)被改動(dòng)(2) 列出實(shí)驗(yàn)參考的資料一些網(wǎng)上資料以及C+ API(3) 如果你對(duì)這兩次實(shí)驗(yàn)還有其他的解決方案或設(shè)想，或?qū)ξ覀兊膶?shí)驗(yàn)方案有什么意見(jiàn)，請(qǐng)?jiān)诖嗣枋觥?實(shí)驗(yàn)二中圖也可以試試用矩陣存放。- 5 -附錄 數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)成績(jī)?cè)u(píng)定表 附錄：數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)成績(jī)?cè)u(píng)定表評(píng)價(jià)內(nèi)容具 體 要 求分值得分平時(shí)表現(xiàn)實(shí)驗(yàn)過(guò)程中，無(wú)缺勤現(xiàn)象，態(tài)度積極，具有嚴(yán)謹(jǐn)?shù)膶W(xué)習(xí)態(tài)度和認(rèn)真、踏實(shí)、一絲不茍的科學(xué)作風(fēng)。10提交材料能夠按時(shí)規(guī)范提交實(shí)驗(yàn)要求的所有材料（要求在以“學(xué)號(hào)-姓