《數(shù)據(jù)結構》實驗報告

1、數(shù)據(jù)結構實驗報告東北大學軟件學院課程編號：B0801010501 .實驗目的實驗一：1 .理解隊列的概念以及用法2 .掌握queue類的使用3 .熟練運用隊列先進先出，模擬打印機的工作過程實驗二：1 .理解圖的概念2 .理解并掌握圖的存儲，并利用鄰接表來存儲圖的信息3 .理解并掌握Dijkstra算法4 .運用Dijkstra算法解決最短路徑的問題針對每次實驗，寫出你認為比較重要的實驗目的2 .實驗內容與實驗步驟2.1 打印機模擬程序的內容與步驟(1)簡短明確地寫出實驗的內容模擬打印機打印的過程，以先來先服務的策略來完成打印工作。先從一個文件中讀取所有任務的大小與到達時間，并將其存儲在 wor

2、kload隊列中。使用一個計數(shù)器來模擬時間的流逝，當當前時間與 workload隊列中的一個任務的到達時間相等的 時候，該任務被彈出，并被壓入到另一個等待執(zhí)行的隊列中。該等待執(zhí)行的隊列以 先入先出的準則依次彈出任務并執(zhí)行。最后計算出任務總數(shù)與，總等待時間，平均 等待時間。(2)簡短描述抽象數(shù)據(jù)類型或設計的函數(shù)描述，說明為什么要使用這種抽象數(shù)據(jù)類 型，并說明你的解決設想一個simulator的抽閑類和它的實現(xiàn)類fifo類。該類的simulate函數(shù)用來實現(xiàn)先進先出策略的打印算法。兩個隊列，一個 workload隊列，一個是等待執(zhí)行隊列。 Workload隊列中存 放的是所有的打印任務，通過文件讀

3、取并保存。而等待執(zhí)行隊列則是為了實現(xiàn) FIFO 功能的隊列，即時間小的就先被壓入等待執(zhí)行隊列，自然也就先被pop并執(zhí)行。解決設想：利用一個int型變量模擬時間的流逝，然后當?shù)却龍?zhí)行隊列為空的時候，就不斷循環(huán)檢查workload隊列中是否有任務到達，若有則將其彈出并 push進等待執(zhí)行 隊列。而當?shù)却龍?zhí)行隊列中有任務時則執(zhí)行它，并且同時判斷workload隊列中是否有任務到達。若 workload和等待執(zhí)行隊列同時為空了，則程序結束。(3)簡短明確地寫出你實驗所采用的存儲結構及其用途，詳細說明其中的屬性的含 義。job類封裝了一個任務的所有屬性。包括任務的大小和該任務的用戶：任務 的大小即為該打

4、印任務一共需要打印的頁數(shù)，而該任務來自哪個計算機。event類封裝了一個打印事件的所有屬性。任務本身并不包含打印的信息，而一個打印事件則需要包含一個待執(zhí)行的任務和該任務到達的時間。打印的時候就是根據(jù)這些信息來執(zhí)行它。而待執(zhí)行的任務屬性即是一個任務對象，而該任務到達的時間即是該任務在某個時間到達打印機，并等待被執(zhí)行。simulator類封裝了所有打印機的操作，包括加載任務文件，執(zhí)行打印任務等。該類將從文件中加載的任務封裝成對象，并存儲于workload隊列中。然后待時間到時，將該任務 pop并push到等待執(zhí)行隊列中。在該隊列中自然就按FIFO的策略來執(zhí)行。2.2 歐洲旅行實驗的內容與步驟(1)

5、簡短明確地寫出實驗的內容該實驗就是在互相連接的城市中尋找給定兩個城市之間的費用最小的路徑。用鄰接表來存儲整個圖的信息，并用一個map對象來存儲各個城市的信息，包括它上一個城市，從起點到該城市的費用和距離。最后利用Dijkstra算法來對任意給定的兩個城市，計算他們之間的費用最小的路徑。(2)簡短描述你在實驗中使用的數(shù)據(jù)結構及算法的基本原理。在本實驗中，使用了鄰接表，map集合，list集合。鄰接表是用于存儲整個圖的信息的，即它用于存儲每一個點，有多少個點與它相連。即對于每一個點，它的名稱作為鍵，而有一個包含了與它相連的所有點的信息的list對象作為值。這樣就完全保存了該圖的全部信息。然后有了該

6、圖，就可以利用 Dijkstra算法來計算任意兩點之間 的距離。而Dijkstra算法的基本思想就是，循環(huán)找出下一個離起點距離最短的點，并 標上標記，納入以找出最短路徑的點的集合。而當找到的下一個里起點最近的點就是目的地，則循環(huán)結束，最短路徑則通過 map集合中每一個 City對象的from_city屬性 來找到。(3)描述你采用STL中的什么容器或者類實現(xiàn)圖的存儲，在算法應用過程中使用什么 數(shù)據(jù)結構或算法提高算法的效率。我們使用STL中的map對象來存儲圖。即map中的每一個鍵都為一個城市名，然后它的值為與該城市直接相連的所有城市所形成的list對象。我們使用了鄰接表的數(shù)據(jù)結構，并使用了優(yōu)先

7、級隊列來實現(xiàn)下一個最短路徑的點的快速查找，極大地提高了算法的效率。并且使用了 Dijkstra算法，利用優(yōu)先級 隊列逐漸尋找下一個里起點最短的點，并將它的visited屬性標記為true,表示已經(jīng)訪問過，并在每一次訪問后，都會更新剩余點的費用和距離的值。然后再利用優(yōu)先 級隊列計算新一輪的距離最短的點。3 .實驗環(huán)境操作系統(tǒng)、調試軟件名稱、版本號，上機地點，機器臺號操作系統(tǒng)：Windows 8.1調試軟件名稱： Codeblocks 12.114 .實驗過程與分析4.1 打印機模擬程序的過程分析(1)描述你在進行實現(xiàn)時，主要的函數(shù)或操作內部的主要算法，分析這個算法的時、空 復雜度，并說明你設計的

8、巧妙之處。simulate函數(shù)為主要的執(zhí)行 FIFO打印的函數(shù)。該算法首先是一個while循環(huán)，該循環(huán)中的部分，由三個判斷與語句組成，如果 workload隊列和等待執(zhí)行隊列都為空，則可 以斷定所有任務全部執(zhí)行完；而如果等待執(zhí)行隊列為空，則表名現(xiàn)在還沒有任務到達打 印機，此時需要循環(huán)判斷是否有任務到達，并且計數(shù)器也循環(huán)+1 ;而如果等待執(zhí)行隊列不為空，就意為著，需要執(zhí)行任務，那么則立即執(zhí)行當前隊列頂部任務，計算該任務的 等待時間，加到總等待時間上，并把當前計數(shù)器時間加上該任務執(zhí)行的時間。然后在 workload隊列中把任務的執(zhí)行時間 <=當前時間的任務給彈出并壓入到等待執(zhí)行隊列中。 等著

9、三個判斷語句結束后進入while的下一次循環(huán)。該算法具有很小的時間復雜度，O(n) = 2n +打印機空閑的秒數(shù)。因為對于執(zhí)行打印任務的時候，該算法是直接在計數(shù)器上加上該任務消耗的時間，而對于 pop出workload的 時間則是等于任務的個數(shù)，然后剩余消耗的時間就是在等待執(zhí)行隊列為空的時候，循環(huán)判斷workload隊列中是否有任務到達了，所以此時消耗的循環(huán)次數(shù)為打印機空閑的秒數(shù)。而空間復雜度為：n+2。也就是任務的個數(shù)+隊列個數(shù)。此算法的巧妙之處就在于，并沒有以計數(shù)器逐漸遞增的方式來模擬時間的流逝，而 是消耗多少時間，計數(shù)器直接加上該值，并不是等待計數(shù)器累加到該值才執(zhí)行任務。(2)你在調試過

10、程中發(fā)現(xiàn)了怎樣的問題？又做了怎樣的改進(要求寫出具體的事例) 在算平均等待時間的時候，把該總時間的類型設置成了整型，導致平均等待時間 算錯。(3)你的實現(xiàn)是否具有可擴展性，如針對多個打印隊列的仿真程序？本實現(xiàn)具有可擴展性，即只要在原來判斷單個打印隊列是否為空的基礎上，加上&&語句，即同時判斷是否所有打印隊列同時為空，如果都為空，則循環(huán)判斷所有workload隊列中任務是否已到達時間，若到達了時間則彈出并push到相應的打印隊列中，這就是由原來的單個 workload判斷變成了循環(huán)判斷多個workload。而如果有任一一個打印隊列不為空，那么則和原來一樣進入第三個判斷中，執(zhí)行該打

11、印任務，且循環(huán)所有打印隊列并執(zhí)行任務。4.2 歐洲旅行實驗的過程分析(1)描述你在進行實現(xiàn)時，主要的函數(shù)或操作內部的主要算法，分析這個算法的時、空 復雜度，并說明你設計的巧妙之處。主要函數(shù)為calc_route函數(shù)。該函數(shù)運用的算法為Dijkstra算法，算出最小路徑。該算法從起點開始遍歷，然后重新計算與該點相連的所有點到起始點的距離，然后把這些點都push到優(yōu)先級隊列中，利用優(yōu)先級隊列的排序功能，我們只需要取出優(yōu)先級隊列中頂部 的點，并將其標記為已訪問過，然后在訪問與該點相連的所有點，再次重復上述過程。 即不斷尋找下一個離起點最近的點，并將其標記為true。該算法的時間復雜度為 O(n) =

12、 2n (n為邊數(shù))。即每次都要循環(huán)遍歷與該點相連的所有 點，所以對于兩個點之間的那條邊需要被遍歷兩次，雖然只有其中一次才會執(zhí)行其中的語句。而空間復雜度為：2倍點的個數(shù)+2倍邊數(shù)。此算法的巧妙之處在于利用了優(yōu)先級隊列，這可以很方便地選取出下一個離起點最短 的點。(2)你在調試過程中發(fā)現(xiàn)了怎樣的問題？又做了怎樣的改進？問題1:訪問過的點沒有標記為true,使得進入死循環(huán)。解決之道：將其標記為true。問題2：在reset()方法中初始化的時候，將點的total_fee屬性初始化為了 INT_MAX ,使得永遠無法計算出最短路徑。解決之道：將其屬性初始化為0。問題3:創(chuàng)建鄰接表的時候，先創(chuàng)建一個l

13、ist<Service *>的變量，然后把outgoing_servicesfrom賦值給它，然后在調用該變量的push_back方法。而這樣永遠找不出最短路徑。解決之道：直接調用outgoing_servicesfrom的 push_back 方法將 Service 對象 push進去。(3)你的實驗在解決類似問題時是否具有靈活的可修改性、可擴展性？具有可擴展性，因為可以在優(yōu)先級隊列的比較方法中設置不同的比較算法。這樣權值 的比較具有任意性，只要更改此比較方法，就可以求出任意形式的最短的路徑了。5 .實驗結果總結5.1 打印機模擬程序的結果總結回答以下問題：(1)你的測試充分嗎？

14、為什么？你是怎樣考慮的？充分。不管是任意順序的任務，還是大的任務先執(zhí)行，都可以得到正確的結果。(2)為什么你要選用隊列作為你應用的數(shù)據(jù)結構？因為該題是FIFO,而隊列也正是先入先出的數(shù)據(jù)結構。(3)用一段簡短的代碼及說明論述你的應用中主要的函數(shù)的主要處理部分。while (1)/*如果兩個隊列同時為空，則退出*/if (workload.empty() && print.empty()break;/如果等待執(zhí)行隊列為空，則循環(huán)判斷是否有任務到達else if (print.empty() while (!workload.empty()if (workload.front().

15、arrival_time() = count_time) /*如果時間到了則pop*/break;else count_time+;else/執(zhí)行任務while (!workload.empty()if (workload.front().arrival_time() <= count_time)/把workload中的任務添加到等待執(zhí)行隊列else break;(4)用結構化圖表或者結構化代碼描述源程序的大致的執(zhí)行過程。-5 -數(shù)據(jù)結構實驗報告東北大學軟件學院loadworkload(file);如果workload隊列和等待執(zhí)行隊 列同時為空是循環(huán)判斷workload隊列中是否 有任

16、務到達，并且每一次循環(huán)計數(shù)器+1。若有任務到達，則push 進等待執(zhí)行隊列，并 break,進入while的下一次循環(huán)執(zhí)行等待執(zhí)行隊列中頂部的那個任務，并把計數(shù)器直接加上該 任務執(zhí)行的秒數(shù)，并把在任務執(zhí)行這段時間內到達的任務全部 彈出，并push到任務執(zhí)行隊列 中-6 -程序結束數(shù)據(jù)結構實驗報告東北大學軟件學院5.2歐洲旅行實驗的的結果總結回答以下問題：(1)你的測試充分嗎？為什么？你是怎樣考慮的？充分。對于圖中任意兩點，都可以計算出它的最短路徑。(2)在你的問題解決方案中，為圖選取了順序的還是鏈式的存儲結構？為什么要選取這種存儲結構？鏈式存儲結構因為如果是數(shù)組的話，那么每行含有的元素數(shù)可能會

17、不一樣，所 以選取鏈式的存儲結構。(3)用一段簡短的代碼及說明論述你的應用中主要的函數(shù)的主要處理部分。City *from_city = citiesfrom;/先把起點城市push到優(yōu)先級隊列中。candidates.push(from_city);/如果優(yōu)先級隊列中為空，則退出循環(huán)while (!candidates.empty()/取出里起點最短的那個城市，作為此次選取出的城市，并標記為true。City* f_city = candidates.top();if (f_city->visited = false)f_city->visited = true;list<

18、Service*> f_city_service = outgoing_servicesf_city->name;list<Service*>:iterator iter = f_city_service.begin();/循環(huán)遍歷與該點相連的所有的點，并重新計算它的距離和費用屬性，并將 其push到優(yōu)先級隊列中。for (; iter != f_city_service.end(); iter+)if (cities(*iter)->destination->visited = false)cities(*iter)->destination->

19、;total_fee = f_city->total_fee+ (*iter)->fee;cities(*iter)->destination->total_distance =f_city->total_distance + (*iter)->distance;cities(*iter)->destination->from_city = f_city->name;candidates.push(cities(*iter)->destination);/將已經(jīng)遍歷過的點彈出優(yōu)先級隊列。candidates.pop();(4)在你的圖

20、中使用了怎么樣數(shù)據(jù)結構來優(yōu)化算法的性能？使用了鏈接表來存儲圖的結構，并使用了優(yōu)先級隊列來將其它城市到起點城市的距離進行排序，然后選取出距離最短的那個城市，作為下一個標記為已訪問過的那 個城市。這樣極大的簡化了代碼。(5)源程序的大致的執(zhí)行過程是怎樣的？load_services/讀取數(shù)據(jù)初始化所有城市的信息息Reset/初始化所有城市的屬性，將總費用和總路程都置為 0把起點push進優(yōu)先級隊列While循環(huán)For循環(huán)遍歷與優(yōu)先級隊列頂部 的相連的點，并重新計算與起點 的距離和費用 把它push到優(yōu)先級隊列 把該頂部的點彈出根據(jù)終點城市回退，推算出整個最短路徑所包括的城市)6.附錄（1）回答思考題a）棧和隊列在計算機系統(tǒng)中有哪些應用？寫出你知道的系統(tǒng)中，這兩種抽象數(shù)據(jù)類型的應用。Android系統(tǒng)中的Activity 是用棧來管理的。Linux的CPU度算法就是用隊列來完成的。b）在程序調用的時侯，需要進行函數(shù)的切換，你認為函數(shù)在進行切換時系統(tǒng)要做那些工作？把此時運行的位置進棧跳轉到函數(shù)的位置，執(zhí)行函數(shù)彈