東北大學(xué)數(shù)據(jù)結(jié)構(gòu)模擬隊(duì)列打印實(shí)驗(yàn)報(bào)告

1、實(shí)驗(yàn)報(bào)告課程名稱(chēng)：數(shù)據(jù)結(jié)構(gòu)班級(jí):會(huì)計(jì)1203實(shí)驗(yàn)成績(jī)：實(shí)驗(yàn)名稱(chēng)：打印機(jī)模擬程序的設(shè)計(jì)學(xué)號(hào):20120577批閱教師簽字：實(shí)驗(yàn)編號(hào)：實(shí)驗(yàn)一姓名:柳思楊實(shí)驗(yàn)日期：2014年06月22 指導(dǎo)教師：張明衛(wèi)組號(hào):實(shí)驗(yàn)時(shí)間：時(shí)分時(shí)分一、實(shí)驗(yàn)?zāi)康膶?xiě)出你認(rèn)為比較重要的實(shí)驗(yàn)?zāi)康?、了解和掌握隊(duì)列的數(shù)據(jù)類(lèi)型描述及其特點(diǎn)。2、掌握隊(duì)列初始化、入隊(duì)、出隊(duì)等相關(guān)基本操作的實(shí)現(xiàn)方法，從而達(dá)到能靈活運(yùn)用隊(duì) 列解決應(yīng)用問(wèn)題的目的。二、實(shí)驗(yàn)內(nèi)容與實(shí)驗(yàn)步驟(1) 簡(jiǎn)短明確地寫(xiě)出實(shí)驗(yàn)的內(nèi)容1. 首先，在一個(gè)名為fifo.h的文件聲明類(lèi)fifo。聲明類(lèi)fifo適當(dāng)模型下面的關(guān)系:一個(gè)fifo 是一種模擬器。2. 接下來(lái)，完整的實(shí)現(xiàn)f

2、ife:模擬。這個(gè)成員函數(shù)應(yīng)該首先使用繼承l(wèi)oadworkload加載數(shù) 據(jù)文件，那么它應(yīng)該實(shí)現(xiàn)仿真如上所述。使用繼承seconds_per_page數(shù)據(jù)成員，以幫助確 定打印作業(yè)需要打印多久。你的解決方案的輸出應(yīng)該匹配的輸出示例解決方案。為了清 楚起見(jiàn)，延遲秒數(shù)，間隔打印作業(yè)時(shí)，當(dāng)它到達(dá)開(kāi)始打印。總延遲是所有打印作業(yè)的總延遲， 和平均延遲是所有打印作業(yè)的平均延時(shí)。(2) 簡(jiǎn)短描述抽象數(shù)據(jù)類(lèi)型或設(shè)計(jì)的函數(shù)描述，說(shuō)明力什么要使用這種抽象數(shù)據(jù)類(lèi) 型，并說(shuō)明你的解決設(shè)想queue<event> a;建立一個(gè)存放event的隊(duì)列對(duì)象a。把按wait_until順序從workload中的ev

3、ent導(dǎo)出，再依次把event對(duì)應(yīng)的job任務(wù)計(jì)算岀 打印的時(shí)間點(diǎn)printtime,存入新構(gòu)造的event的wait_until域中，最后這些event按打印 時(shí)間將存入a隊(duì)列屮。(3) 簡(jiǎn)短明確地寫(xiě)出你實(shí)驗(yàn)所采用的存儲(chǔ)結(jié)構(gòu)及其川途，詳細(xì)說(shuō)明其中的屬性的含 義。存儲(chǔ)結(jié)構(gòu)：queue<event>o即存放event對(duì)象的隊(duì)列。用途：苒先進(jìn)先出的特點(diǎn)符合實(shí)際打印業(yè)務(wù)的需求。主要屬性：queue();/構(gòu)造函數(shù) queue();/析構(gòu)函數(shù) void push(t & e);/入隊(duì)void pop();/岀隊(duì) t front();/返冋第一個(gè)存儲(chǔ)對(duì)象 int size();/隊(duì)列

4、111存儲(chǔ)對(duì)象的數(shù)量 bool empty();/判斷是否為空三、實(shí)驗(yàn)環(huán)境操作系統(tǒng)、調(diào)試軟件名稱(chēng)、版本號(hào)，上機(jī)地點(diǎn)，機(jī)器臺(tái)號(hào)操作系統(tǒng)：win7旗艦版調(diào)試軟件名稱(chēng)：vs2010版本號(hào)：2010上機(jī)地點(diǎn)：寢室機(jī)器臺(tái)號(hào)：筆記本四、實(shí)驗(yàn)過(guò)程與分析(1) 描述你在進(jìn)行實(shí)現(xiàn)時(shí)，主要的函數(shù)或操作內(nèi)部的主要算法，分析這個(gè)算法的吋、 空復(fù)雜度，并說(shuō)明你設(shè)計(jì)的巧妙之處。第一步：定義一個(gè)int變量time，在大循環(huán)內(nèi)逐次加一，模擬時(shí)間的遞增。第二步：定義一個(gè)queque對(duì)象a，用于保存已到達(dá)并正在等待打印的event。定義一個(gè) int變:w: printtime,計(jì)算每一次到達(dá)的event的打印時(shí)問(wèn)點(diǎn)。當(dāng)time等

5、于workload屮頂 端元素的wait_until時(shí)，彈出event對(duì)象，在屏幕上打印出這項(xiàng)任務(wù)到達(dá)的信息，如： “arriving: 100 pages from giraffe at 1 seconds”。算出這個(gè) event 對(duì)應(yīng)的 job 的打印時(shí)間， 并保存在printtime變量里，在把這個(gè)job和printtime構(gòu)造成新的event吋間存入定義的 queue對(duì)象a中。第三步：當(dāng)time等于a中頂端元素的wait_until吋，說(shuō)明此項(xiàng)任務(wù)打印完畢，彈出event 對(duì)象，在屏幕上打印出這項(xiàng)任務(wù)己打印的信息，如：“servicing: 100 pages from giraffe

6、 at 1 seconds” o第四步：當(dāng)workload和a都為空了以后，以break退出循環(huán)。第五步：通過(guò)在循環(huán)|a)定義number, latency等int型變ft，累加算出total jobs, aggregate latency, mean latency 等值并打印在解幕上。時(shí)間復(fù)雜度：o(n)空間復(fù)雜度：0(n)巧妙之處：說(shuō)實(shí)話(huà)，不巧妙，算法性能還可以略微提高。(2) 你在調(diào)試過(guò)程中發(fā)現(xiàn)了怎樣的問(wèn)題？又做了怎樣的改進(jìn)(要求寫(xiě)出具體的事例) 有些event的wait_until是同時(shí)的，所以每次入隊(duì)后直接把time+1是不對(duì)的，4能漏掉 一個(gè)event。改進(jìn)，每次弾出一個(gè)even

7、t后不要立即改變time值，當(dāng)下一循環(huán)time不再 等于頂端元素的wait_until時(shí)再加1.(3) 你的實(shí)現(xiàn)是否具有可擴(kuò)展性，如針對(duì)多個(gè)打印隊(duì)列的仿真程序？稍微改一下是可以的。五、實(shí)驗(yàn)結(jié)果總結(jié) 冋荇以下問(wèn)題：(1) 你的測(cè)試充分嗎？為什么？你是怎樣考慮的？川丫試驗(yàn)給出的arbitrary和btgetrst兩組數(shù)據(jù)，結(jié)果均正確。(2) 為什么你要選用隊(duì)列作為你應(yīng)用的數(shù)據(jù)結(jié)構(gòu)？其先進(jìn)先出的特性符合打印業(yè)務(wù)的要求。(3) 用一段簡(jiǎn)短的代碼及說(shuō)明論述你的應(yīng)用中主要的函數(shù)的主要處理部分。 while(true) if (! work load, empty () if(time=workload.

8、front 0. arrival_time()cout<” arriving:，z<<workload, front (). getjob(). getnumpages ()<<，z pages from /z«workload. front (). get job (). gctuscr () <</z at <workloacl front(). arrival time()<secondsendl;/當(dāng)time等于workload屮頂端元素的wait_until時(shí)，彈出event對(duì)象，在屏幕上打印出這項(xiàng)任務(wù) 到達(dá)的信息，如：

9、“arriving: 100 pages from giraffe at 1 seconds”。a. push (event (job (workload, front (). get job (). getnumpages (), workload, front (). get job (). getuser0), printtime);/算出這個(gè)event對(duì)成的job的打印時(shí)ixi,并保存在printtime變量里，在把這個(gè)job和printtime構(gòu) 造成新的event時(shí)間存入定義的queue對(duì)象a中。number+=l;latency-二workload front(). arriva

10、l_timc(); printtime=pri ntt i me+workload. front(). getjob(). getnumpages()seconds per page; workload, pop (): time ;/當(dāng)time等于a中頂端元素的wait_until(即它的printtime)時(shí)，說(shuō)明此項(xiàng)任務(wù)打印完畢，彈出event 對(duì)象，在屏幕上打印山這項(xiàng)任務(wù)己打印的信息，如：“servicing: 1 ()0 pages from giraffe at 1 seconds if (a. empty 0) time+; continue; if (time=a. front

11、 (). arrival_time () cout«，z servicing:/z<<a. front (). get job(). getnumpages ()pages from z，«a. front (). get job (). getuser () <<z，at "<i<seconds"<endl;latency+=a. front (). arrival time(); a. pop ();if (a. empty () && workload, empty () ) break;/

12、通過(guò)在循環(huán) lal 定義 number，latency 等 int 型變:w:，累加算出 total jobs，aggregate latency， mean latency等值并打印在屏幕上。c()uttotal jobs: numberendl;coutaggregate latency: latency secondsendl; coutz，mcan latency: (double) latency/numbcr)" sccondscndl:(4) 用結(jié)構(gòu)化圖表或者結(jié)構(gòu)化代碼描述源程序的大致的執(zhí)行過(guò)程。queue workloadqueue awai t_untilnumbe

13、r_of一pagesuserwai t_untilnumber_of一pagesuser51giraffe41falcon36herring22platypusqueue workloadqueue await_untilnumber, of一pagesuserwait_untilnumber, of一pagesuser51giraffe41falcon36herring22platypusarriving: 2 pages from platypus at 2 secondsqueue workloadqueue awaituntilnumber of一pagesuserwaituntiln

14、umber of一pagesuser51giraffe41falcon36herringqueue workloadqueue awaitnumbcr_ofuserwaitnumbcr_ofuseruntilpagesuntilpages51giraffe41falcon66herringarriving: 6 pages from herring at 3 secondsqueue workloadqueue awaituntilnumber_of一pagesuserwaituntilnumber_of一pagesuser51giraffe181falcon66herringarriving

15、: 1 page from falcon at 4 secondsqueue workloadqueue awaituntilnumber of一pagesuserwaituntilnumber of一pagesuser201giraffe181falcon66herringqueue workloadqueue await_untilnumbcr_ofpagesuserwait_untilnumbcr_ofpagesuser201giraffe181falconqueue workloadqueue awaituntilnumber_of一pagesuserwaituntilnumber_o

16、f一pagesuser201giraffeservicing: 1 page from falcon at 18 secondsqueue workloadqueue awaituntilnumber of一pagesuserwaituntilnumber of一pagesuserservicing: 6 pages from herring at 6 secondsservicing: 1 page from giraffe at 20 seconds請(qǐng)淸晰、準(zhǔn)確、詳細(xì)地回答上而的問(wèn)題，要求標(biāo)點(diǎn)符號(hào)正確無(wú)誤，圖表表示符合規(guī) 范。你的報(bào)告應(yīng)至少超出一貞的文字描述，注意你描述的文字一定要敘述流暢，具有較 好的邏輯性。六、附錄(1) 如果你對(duì)這個(gè)實(shí)驗(yàn)還有其他的解決方案或設(shè)想，或?qū)ξ覀兊膶?shí)驗(yàn)方案有什么意 見(jiàn)，清在此描述。無(wú)。(2) 實(shí)驗(yàn)參考的資料數(shù)據(jù)結(jié)構(gòu)(而14對(duì)象方法與c+i?i言描述)第2版百度文庫(kù)(3) 回答思考題a) 棧和隊(duì)列在u算機(jī)系統(tǒng)中有哪些應(yīng)用？寫(xiě)出你知道的系統(tǒng)中，這兩種抽象數(shù)據(jù) 類(lèi)型的應(yīng)用。不太淸楚?；蛟S在俄羅斯方塊游戲中運(yùn)用了棧，而在網(wǎng)絡(luò)下載屮運(yùn)用了