東北大學數(shù)據(jù)結構實驗報告

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

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

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

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

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

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

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

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

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

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

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

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