《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報(bào)告

1、數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告東北大學(xué)軟件學(xué)院課程編號(hào)：B0801010501 .實(shí)驗(yàn)?zāi)康膶?shí)驗(yàn)一：1 .理解隊(duì)列的概念以及用法2 .掌握queue類的使用3 .熟練運(yùn)用隊(duì)列先進(jìn)先出，模擬打印機(jī)的工作過(guò)程實(shí)驗(yàn)二：1 .理解圖的概念2 .理解并掌握?qǐng)D的存儲(chǔ)，并利用鄰接表來(lái)存儲(chǔ)圖的信息3 .理解并掌握Dijkstra算法4 .運(yùn)用Dijkstra算法解決最短路徑的問(wèn)題針對(duì)每次實(shí)驗(yàn)，寫(xiě)出你認(rèn)為比較重要的實(shí)驗(yàn)?zāi)康? .實(shí)驗(yàn)內(nèi)容與實(shí)驗(yàn)步驟2.1 打印機(jī)模擬程序的內(nèi)容與步驟(1)簡(jiǎn)短明確地寫(xiě)出實(shí)驗(yàn)的內(nèi)容模擬打印機(jī)打印的過(guò)程，以先來(lái)先服務(wù)的策略來(lái)完成打印工作。先從一個(gè)文件中讀取所有任務(wù)的大小與到達(dá)時(shí)間，并將其存儲(chǔ)在 wor

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

17、不一樣，所 以選取鏈?zhǔn)降拇鎯?chǔ)結(jié)構(gòu)。(3)用一段簡(jiǎn)短的代碼及說(shuō)明論述你的應(yīng)用中主要的函數(shù)的主要處理部分。City *from_city = citiesfrom;/先把起點(diǎn)城市push到優(yōu)先級(jí)隊(duì)列中。candidates.push(from_city);/如果優(yōu)先級(jí)隊(duì)列中為空，則退出循環(huán)while (!candidates.empty()/取出里起點(diǎn)最短的那個(gè)城市，作為此次選取出的城市，并標(biāo)記為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)遍歷與該點(diǎn)相連的所有的點(diǎn)，并重新計(jì)算它的距離和費(fèi)用屬性，并將 其push到優(yōu)先級(jí)隊(duì)列中。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)遍歷過(guò)的點(diǎn)彈出優(yōu)先級(jí)隊(duì)列。candidates.pop();(4)在你的圖

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