優(yōu)先級(jí)作業(yè)調(diào)度系統(tǒng)試驗(yàn)報(bào)告

數(shù)據(jù)結(jié)構(gòu)大型試驗(yàn)報(bào)告優(yōu)先級(jí)作業(yè)調(diào)度系統(tǒng)的模擬課程名稱：數(shù)據(jù)結(jié)構(gòu)大型試驗(yàn)實(shí)驗(yàn)項(xiàng)目名稱：優(yōu)先級(jí)作業(yè)調(diào)度系統(tǒng)的模擬學(xué)院：計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院專業(yè)：物聯(lián)網(wǎng)工程班指導(dǎo)教師:黃偉報(bào)告人：李靖學(xué)號(hào)：201426811412班級(jí):物聯(lián)網(wǎng)1402目錄.實(shí)驗(yàn)內(nèi)容分析3實(shí)驗(yàn)?zāi)康膶?shí)驗(yàn)要求設(shè)計(jì)分析.試驗(yàn)驗(yàn)證分析輸入的形式及輸入值的范圍程序所能達(dá)到的結(jié)果測(cè)試數(shù)據(jù).測(cè)試分析基礎(chǔ)問題技術(shù)問題調(diào)試錯(cuò)誤.調(diào)試結(jié)果分析程序的運(yùn)行結(jié)果.附錄、實(shí)驗(yàn)內(nèi)容分析:實(shí)驗(yàn)?zāi)康模篧indowsLinux等操作系統(tǒng)都支持同時(shí)運(yùn)行多個(gè)作業(yè)，但作業(yè)的執(zhí)行順序卻因調(diào)度算法的不同而不同。通常，操作系統(tǒng)都采用優(yōu)先級(jí)作業(yè)調(diào)度，即操作系統(tǒng)根據(jù)作業(yè)的長(zhǎng)短來(lái)設(shè)置優(yōu)先級(jí)大小，優(yōu)先級(jí)高的作業(yè)先執(zhí)行，優(yōu)先級(jí)低的作業(yè)后執(zhí)行。作業(yè)調(diào)度的詳細(xì)情況如下描述：一個(gè)作業(yè)Ji的長(zhǎng)度為ti=（si,ei）,si為作業(yè)運(yùn)行的開始時(shí)間（進(jìn)入時(shí)間），ei為作業(yè)運(yùn)行的結(jié)束時(shí)間（離開時(shí)間），ti則為完成作業(yè)Ji所需要的執(zhí)行時(shí)間（單位：秒）。作業(yè)調(diào)度的基本任務(wù)是從作業(yè)隊(duì)列中選取一個(gè)來(lái)執(zhí)行，如果沒有作業(yè)則執(zhí)行空操作操作。而優(yōu)先級(jí)作業(yè)調(diào)度，是指每次選取優(yōu)先級(jí)最高的作業(yè)來(lái)調(diào)度，優(yōu)先級(jí)可以用優(yōu)先數(shù)（每個(gè)作業(yè)一個(gè)優(yōu)先數(shù)pi）來(lái)表示，優(yōu)先數(shù)越小，優(yōu)先級(jí)越高。作業(yè)Ji進(jìn)入系統(tǒng)時(shí)，即si時(shí)刻，系統(tǒng)給該作業(yè)指定其初始優(yōu)先數(shù)pi=ti,從而使越短的作業(yè)優(yōu)先級(jí)越高。該優(yōu)先數(shù)在作業(yè)等待調(diào)度執(zhí)行的過(guò)程中會(huì)不斷減小，調(diào)整公式為：pi=pi-wi,其中wi為作業(yè)Ji的等待時(shí)間：wi=當(dāng)前時(shí)間-si。一旦作業(yè)被調(diào)度，該作業(yè)就一直執(zhí)行，不能被搶占，只有當(dāng)前執(zhí)行的作業(yè)完成時(shí)，才產(chǎn)生下一輪調(diào)度。所以需要在每次調(diào)度前動(dòng)態(tài)調(diào)整各作業(yè)的優(yōu)先數(shù)。在每次調(diào)度的時(shí)候，如果出現(xiàn)相同優(yōu)先級(jí)的作業(yè)，則按照先進(jìn)先出（FIFO:FirstInFirstOut）的原則進(jìn)行調(diào)度。實(shí)驗(yàn)要求：.要求自己編程實(shí)現(xiàn)堆結(jié)構(gòu)及其相關(guān)功能，從而實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列，不允許使用標(biāo)準(zhǔn)模板類的堆函數(shù)和優(yōu)先級(jí)隊(duì)列；測(cè)試時(shí)，各種情況都需要測(cè)試，并附上測(cè)試截圖；.要求采用類的設(shè)計(jì)思路，不允許出現(xiàn)類以外的函數(shù)定義，但允許友元函數(shù)。主函數(shù)中只能出現(xiàn)類的成員函數(shù)的調(diào)用，不允許出現(xiàn)對(duì)其它函數(shù)的調(diào)用。.要求采用多文件方式：.h文件存儲(chǔ)類的聲明，.cpp文件存儲(chǔ)類的實(shí)現(xiàn)，主函數(shù)main存儲(chǔ)在另外一個(gè)單獨(dú)的cpp文件中。如果采用類模板，則類的聲明和實(shí)現(xiàn)都放在.h文件中。.要求源程序中有相應(yīng)注釋；.不強(qiáng)制要求采用類模板，也不要求采用可視化窗口；.要求測(cè)試?yán)右容^詳盡，各種極限情況也要考慮到，測(cè)試的輸出信息要詳細(xì)易懂，表明各個(gè)功能的執(zhí)行正確，包括何時(shí)作業(yè)進(jìn)入，何時(shí)調(diào)度哪個(gè)作業(yè)，何時(shí)離開，每個(gè)作業(yè)等待多長(zhǎng)時(shí)間，優(yōu)先數(shù)的動(dòng)態(tài)變化情況等；.要求采用VisualC++6.0及以上版本進(jìn)行調(diào)試；設(shè)計(jì)分析：類的設(shè)計(jì)'Work:自定義的作業(yè)類。《MyHeap自定義的優(yōu)先級(jí)隊(duì)列，幫助工程類的實(shí)現(xiàn)System：模擬作業(yè)調(diào)度系統(tǒng)定義的工程類，模擬處理作業(yè)的過(guò)程。

類的關(guān)系圖Work數(shù)據(jù)類型(作業(yè)類)r類的關(guān)系圖Work數(shù)據(jù)類型(作業(yè)類)r.System(工程類)實(shí)現(xiàn)工匕/MyHeapf(優(yōu)先級(jí)隊(duì)列類)/j基本數(shù)據(jù)結(jié)構(gòu)類的設(shè)計(jì):MyHeap優(yōu)先級(jí)隊(duì)列)：利用自定義的最小堆實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列，實(shí)現(xiàn)主要的功能，包括作業(yè)的插入、最小優(yōu)先級(jí)作業(yè)的提取和刪除、各個(gè)作業(yè)優(yōu)先級(jí)的修改等，優(yōu)先級(jí)隊(duì)列采用的是模板類MyHeap();//隊(duì)列的構(gòu)造函數(shù)voidpop();//刪除隊(duì)首元素,并更新隊(duì)列voidpush(constDATA&item);//DATAtop();//返回隊(duì)首的元素voidpush(constDATA&item);//DATAtop();//返回隊(duì)首的元素在隊(duì)列中加入新項(xiàng)，并更新隊(duì)列boolempty();//判斷隊(duì)列知否為空intsize();//返回隊(duì)列的中元素的個(gè)數(shù)voidupdate();//將隊(duì)列中每一項(xiàng)的優(yōu)先級(jí)減一voidshow();//顯示隊(duì)列的所有信息

作業(yè)類以及工程類的設(shè)計(jì)operator=operator>operator=operator>ostream&=Lintnumints;//作業(yè)進(jìn)入的時(shí)間intt;//作業(yè)的執(zhí)行時(shí)間intp;//作業(yè)的優(yōu)先級(jí)intnum;//作業(yè)標(biāo)號(hào)Work();//無(wú)參構(gòu)造函數(shù)Work(intn,inta,intb);//有參構(gòu)造函數(shù)Work&operator--();////自減操作重載Work&operator=(constWork&a);//賦值操作重載輸出流重重定義小于輸出流重重定義小于friendbooloperator<(constWork&a,constWork&b);//booloperator<(constWork&a,constWork&b){//重定義小于if(a.p!=b.p)returna.p<b.p;//先按優(yōu)先級(jí)排，優(yōu)先級(jí)小的小returna.s<b.s;//否則，先進(jìn)入的小//因?yàn)閯?chuàng)建的是最小堆，所以在隊(duì)首的是優(yōu)先級(jí)小的，符合題目要求}System(工程類)：模擬優(yōu)先級(jí)作業(yè)調(diào)度系統(tǒng)的運(yùn)行的過(guò)程，并設(shè)計(jì)調(diào)試程序代碼函數(shù)MyHeap<Work>mwrSystemWorkwk;數(shù)據(jù)成員MyHeap<Work>mwrSystemWorkwk;數(shù)據(jù)成員boolisworkJintT,end,SIZErun()voidrun();//自動(dòng)運(yùn)作的工程{srand(time(0));//把時(shí)間作為種子，若不調(diào)用此函數(shù)，產(chǎn)生的隨機(jī)數(shù)都是偽隨機(jī)的，每次程序運(yùn)行的結(jié)果都一樣inttol=0;//表示作業(yè)的編號(hào)for(T=0;T<SIZE;T++){//這段時(shí)間會(huì)隨機(jī)產(chǎn)生新的作業(yè)mw.update();//因?yàn)榈却龝r(shí)間+1,所以隊(duì)列里所有的作業(yè)的優(yōu)先級(jí)-1if(iswork&&end==T){//如果正在運(yùn)行的作業(yè)結(jié)束了iswork=false;//表示沒有作業(yè)在運(yùn)行cout<<”***程序運(yùn)行時(shí)間為"<<T<<",作業(yè)"<<wk.num<<”處理完畢,用時(shí)"<<wk.t<<”,等待"<<T-wk.t-wk.s<<"\n\n";//輸出信息}if(iswork){//若有程序在運(yùn)行cout<<"程序運(yùn)行時(shí)間為"<<T<<",正在執(zhí)行作業(yè)"<<wk.num<<"…\n";Sleep(500);//滯留0.5s,表示正在運(yùn)行}if(T%10==0){//如果是10的倍數(shù)intnum=rand()%3+1,t;//隨機(jī)產(chǎn)生1-3個(gè)新作業(yè)printf("***新加入％d作業(yè)：\n",num);for(inti=0;i<num;i++){t=rand()%20+1;//隨機(jī)產(chǎn)生作業(yè)的執(zhí)行時(shí)間mw.push(Work(++tol,T,t));//調(diào)用構(gòu)造函數(shù)printf("作業(yè)％~,進(jìn)入時(shí)間為％d,需執(zhí)行時(shí)間為％d優(yōu)先級(jí)為％d\n",tol,T,t,t);//輸出新作業(yè)的信息}printf("\n");//輸出更新后的隊(duì)列的信息printf("***此時(shí)共有％d(乍業(yè)等彳^處理\n{\n",mw.size());mw.show();//輸出隊(duì)列里的所有的作業(yè)信息，無(wú)序printf("}\n\n");)if(!iswork&&!mw.empty()){wk=mw.top();mw.pop();//取出隊(duì)首元素printf("***開始執(zhí)行作業(yè)％d進(jìn)入時(shí)間為％d等待時(shí)間為％d需執(zhí)行時(shí)間％d,優(yōu)先級(jí)為％d\n",wk.num,wk.s,T-wk.s,wk.t,wk.p);end=T+wk.t;//更新結(jié)束時(shí)間iswork=true;}}while(!mw.empty()||iswork){//不再加入新作業(yè)，將剩余的所有作業(yè)運(yùn)行完二、實(shí)驗(yàn)驗(yàn)證分析輸入形式：需要輸入4個(gè)整型數(shù)據(jù)，分別是時(shí)間問隔、工作時(shí)間、作業(yè)長(zhǎng)度上限以及每個(gè)問隔產(chǎn)生的作業(yè)上限。輸出形式：模擬系統(tǒng)運(yùn)行過(guò)程，詳細(xì)顯示運(yùn)行過(guò)程中系統(tǒng)內(nèi)各個(gè)作業(yè)的信息，以及新加入作業(yè)組的信息，加入新作業(yè)后系統(tǒng)內(nèi)作業(yè)組的信息。每個(gè)作業(yè)運(yùn)行結(jié)束，顯示當(dāng)前作業(yè)等待時(shí)間和運(yùn)行時(shí)間。程序所能達(dá)到的結(jié)果：能使模擬系統(tǒng)根據(jù)作業(yè)的優(yōu)先級(jí)大小順序處理作業(yè)，原始優(yōu)先級(jí)只與作業(yè)的長(zhǎng)度相關(guān)，但運(yùn)行過(guò)程的優(yōu)先級(jí)要根據(jù)系統(tǒng)運(yùn)行的時(shí)間發(fā)生改變，以實(shí)現(xiàn)先入先出的原則。運(yùn)行過(guò)程中，系統(tǒng)會(huì)隨機(jī)產(chǎn)生作業(yè)組加到系統(tǒng)中，系統(tǒng)將新的工作組按照優(yōu)先級(jí)大小進(jìn)行排序。系統(tǒng)能隨時(shí)提取出，當(dāng)前正在處理的作業(yè)的詳細(xì)信息，以及系統(tǒng)內(nèi)正在等待處理的作業(yè)組的信息。測(cè)試數(shù)據(jù)：1.正確輸入：輸入：1060103輸出間T0呈□工呈口王呈□王M21業(yè)業(yè)3079青青青青”79級(jí)級(jí)00e?bQ16靈士一iiiid一:?上產(chǎn)■度圾招4長(zhǎng)間作爵個(gè)冬入時(shí)工售鱉進(jìn)入入入需需**009燃姆97仇先級(jí)為7*二二二%,111111士兀區(qū)業(yè)業(yè)業(yè)業(yè)業(yè)業(yè)理、：—一丁亍-丁一工工丁zlka執(zhí)fck執(zhí)執(zhí)執(zhí)整在在在在在彳迪正正正正正正乙1----，比123456司為為班執(zhí)貧作業(yè)2,進(jìn)人時(shí)間才。，等待時(shí)間為？，需執(zhí)行時(shí)間9,優(yōu)先級(jí)為2□ris-、二ri-X7G1L.-2-需執(zhí)行時(shí)間9,優(yōu)先級(jí)為3000-IT丸丸JIW需需du0，19為為為為"/089100i1亍一Tllr那執(zhí)正正正□MnHMnnL1T1T,仃圖圜矽3,4,業(yè)業(yè)D王0王口王ftt—1010二：二畢2.2.2.2.2.士兀業(yè)業(yè)業(yè)業(yè)業(yè)理“作咋乍^,止-1處一丁丁一丁一工丁12現(xiàn)仇決仇在在在在在作正正正正正16,12345UZ11111為司司司司司FB仃BB日BB云-fT-Tf丁逢閭和囹凰琳□土□王口王口王□王川等待時(shí)間為6,>444410業(yè)業(yè)業(yè)業(yè)-VLVL七LV1時(shí)決aa^A入專在在進(jìn)正正正正47890L1112nnnHUDunn邙一丁一丁-丁一丁4nv/;6/>2>2-也運(yùn)運(yùn)運(yùn)運(yùn)M0王口王呈口王*-^1—可.用.國(guó).聞.Jnnmmm2L*22220111154業(yè)業(yè)ii業(yè)i1II丁LF?./I、一■-5-IJ:2J〉\在在在在都+正正正正用也心7,8,斯%F151555^iI”40,等待時(shí)間為20,需執(zhí)行時(shí)間九優(yōu)先級(jí)為-1回0用在在在套在在在一正正正正正正正正.1，下?■,，■即tJL11234567^SEEbH&66.兀乍力夕夕夕力力力夕里-m=m~1nr?vlnrrTFFr._m.-JJ..阡.hunn0nnBnnnn001若lItT,.lI,(I,!T!I1T_,IT漢理運(yùn)運(yùn)運(yùn)一E，程程，程gHg基業(yè)程i于--11---II---I.-；*ii---11---?---1!■4丁-丁-|-4丁-丁-丁-1—f-XT-VA4二，H/l■丸-9JyJiJ*lrrl.-.+''JyJ二dJ>-J'J.2.錯(cuò)誤輸入輸入的數(shù)據(jù)都要大于0.r圓BC:\Windcw式5y5tlem32\cmd.exe三、調(diào)試分析基礎(chǔ)問題l.vector的運(yùn)用：①end()的誤用解決：end()返回的向量中最后一個(gè)元素后面位置的指針②earse()函數(shù)的調(diào)用解決：函數(shù)括號(hào)內(nèi)是迭代器，不是下標(biāo)2.sleep()的用法Sleep函數(shù)//S要大寫頭文件#include<windows.h>③函數(shù)調(diào)用形式Sleep(500);//單位是毫秒技術(shù)問題.作業(yè)關(guān)系大小的設(shè)計(jì)錯(cuò)誤理解：以為只要比較作業(yè)的優(yōu)先級(jí)就可以了，這樣設(shè)計(jì)無(wú)法實(shí)現(xiàn)先進(jìn)先出的原則解決：設(shè)計(jì)作業(yè)大小比較時(shí)，優(yōu)先考慮作業(yè)的優(yōu)先級(jí)，如果優(yōu)先級(jí)一樣的話，再根據(jù)作業(yè)的num值比較大小(即進(jìn)入系統(tǒng)的先后順序).優(yōu)先隊(duì)列的設(shè)計(jì)

難點(diǎn)：①調(diào)整節(jié)點(diǎn)條件的分析當(dāng)二叉樹只有一個(gè)節(jié)點(diǎn)時(shí)，不需要進(jìn)行下調(diào)工作因?yàn)檫M(jìn)行下調(diào)操作的是一個(gè)最小堆，只要被調(diào)整元素比它的兩個(gè)子節(jié)點(diǎn)都小，就可以直接跳出循環(huán)節(jié)點(diǎn)比較不需要考慮相等的情況，因?yàn)槊總€(gè)作業(yè)的num值一定是不一樣的，所以就算優(yōu)先級(jí)一樣，也一定不會(huì)相等調(diào)試錯(cuò)誤.編寫最小堆的時(shí)候，有幾個(gè)函數(shù)不小心寫成了最大堆的效果，找了好久的錯(cuò)誤.Work類,在編寫賦值操作符重載時(shí)，用的是成員函數(shù)，卻在函數(shù)里新創(chuàng)了個(gè)對(duì)象，結(jié)果出現(xiàn)了錯(cuò)誤四、測(cè)試結(jié)果分析:程序的運(yùn)行結(jié)果痢C：V//indowsVsystem3-2\cmd.exe旬為為為為為為為為為：間hMnn000conHHm00Du111-11...鏗運(yùn)運(yùn)運(yùn)運(yùn)運(yùn)運(yùn)運(yùn)運(yùn)運(yùn)一前.田口王口王匚王口王口王口石口王口三□王口±得度熠間聘長(zhǎng)間作時(shí)間1個(gè)S日工塞必人人?￡」請(qǐng)請(qǐng)剛開始只產(chǎn)生了一個(gè)作業(yè)，所以就執(zhí)行改作業(yè)在在在在在在在在在正正正正正正正正正序運(yùn)行時(shí)間為正程序運(yùn)行時(shí)間為22完畢，用時(shí)2?等待0產(chǎn)生了兩個(gè)作業(yè)，且此時(shí)沒有作業(yè)在執(zhí)行，作業(yè)4的優(yōu)先級(jí)比作業(yè)3大，所以先執(zhí)行作業(yè)43345上222A-二耳./耳/^，x^-_uunnnn堂u耳書運(yùn)運(yùn)運(yùn)1口五口王口王M-聚*4,茁機(jī)機(jī)需需酒0>22為為;二LMHH曰-T--T口正□壬0200212:為為作爵父-AE輪進(jìn)力,k此時(shí)共有Z作業(yè)等待處理,進(jìn)入時(shí)間為等待時(shí)間為明需執(zhí)行時(shí)間“優(yōu)先級(jí)為2穌愉，…耕AFd向小70笛在口寸同小92214

為為為為

及及及及

w+-mt￡*:-

先先先先睡C:\V/indowsVsystem52\cmd.exe?>■/3J2三111AAAA進(jìn)進(jìn)進(jìn)進(jìn)2214「m_xm、-m、-m00@01111為為為為-1J.-m.-m…開埴執(zhí)行作業(yè)3,進(jìn)入中間為也等待時(shí)間為%霄執(zhí)行時(shí)間工，優(yōu)先級(jí)為i岸運(yùn)檸時(shí)間為H恒山處理完單，用毗.等制嚼轆黑,懿翳為椒等待時(shí)間為卻需執(zhí)行時(shí)間會(huì).優(yōu)先級(jí)為］三客y婚彳霸五軍％感理器電用時(shí)2.等待1—開陽(yáng)拉正作業(yè)5,進(jìn)入時(shí)間為1M等待時(shí)間為露需執(zhí)行時(shí)間入優(yōu)先級(jí)為程序運(yùn)打;詢?yōu)?4,正在就行待業(yè)5…程序運(yùn)四間夕??凡作必居里完畢，用時(shí)2.等待3運(yùn)運(yùn)運(yùn)口王口王口王1亡4天運(yùn)運(yùn)運(yùn)口王口王口王1亡4天丸日00中亍亍一丁^Rzn.1i■:等二年，4.4,4.?■10業(yè)業(yè)業(yè)理5-T-1T4-寸丸丸日一匕一匕一人在進(jìn)正正正以*KFKhj467B11isJr—-LMJ.一---t,用用即:B-TUMLT優(yōu)先級(jí)為T作業(yè)2、5的優(yōu)先級(jí)是相同的，而作業(yè)2先進(jìn)入隊(duì)列，所以先執(zhí)行作業(yè)2作業(yè)執(zhí)行時(shí)，輸出執(zhí)行語(yǔ)句，并調(diào)用Sleep函數(shù)，表示正在執(zhí)行34為34為為-日ial?HQHQ-1T——J-需需0055為為-miTm力力日日進(jìn)進(jìn)0055為為一m一日入次1TAh.Ta**12i1日B五、附錄Heap.h#include<iostream>#include<vector>usingnamespacestd;#ifndefMYHEAP#defineMYHEAP//防止因頭文件被反復(fù)調(diào)用，而導(dǎo)致重復(fù)定義//應(yīng)用模板類template<typenameDATA>classMyHeap{vector<DATA>mh;//用向量實(shí)現(xiàn)堆public:MyHeap();//構(gòu)造函數(shù)boolempty();//判空函數(shù)DATAtop();//取隊(duì)首元素voidpop();//刪除隊(duì)首元素voidpush(constDATA&item);//壓入元素voidupdate();//所有元素-1intsize();//獲取元素個(gè)數(shù)voidshow();//調(diào)用graph()private:voidpush_down();//向下更新voidpush_up();//向上更新voidswap(DATA&a,DATA&b);//交換兩個(gè)元素boolcan_push(intpos);//判斷是否需要向下更新voidgraph(ints);//輸出隊(duì)列的所有信息};template<typenameDATA>MyHeap<DATA>二MyHeap(){mh.clear();//清空隊(duì)列}template<typenameDATA>boolMyHeap<DATA>二empty(){returnmh.size()==0;//判斷向量里是否有元素}template<typenameDATA>DATAMyHeap<DATA>::top(){returnmh[0];//向量的第一個(gè)元素就是隊(duì)首}template<typenameDATA>voidMyHeap<DATA>::swap(DATA&a,DATA&b){DATAc=a;a=b;b=c;}template<typenameDATA>boolMyHeap<DATA>::can_push(intpos){intl=mh.size();//若沒有左節(jié)點(diǎn)或當(dāng)前節(jié)點(diǎn)小于左節(jié)點(diǎn)且沒有右節(jié)點(diǎn)或當(dāng)前節(jié)點(diǎn)小于右節(jié)點(diǎn)，那么就不需要再下移if((pos*2+1>=l||mh[pos]<mh[pos*2+1])&&(pos*2+2>=l||mh[pos]<mh[pos*2+2]))returnfalse;returntrue;}template<typenameDATA>voidMyHeap<DATA>二push_down(){intpos=0,l=mh.size();while(can_push(pos)){//若需要下移，則一定有左兒子，因?yàn)槎咽且粋€(gè)完全二叉樹inttar=pos*2+1;//tar先指向左節(jié)點(diǎn)if(pos*2+2<l&&mh[pos*2+2]<mh[pos*2+1])//若有右節(jié)點(diǎn)且右節(jié)點(diǎn)比左節(jié)點(diǎn)小tar++;//則tar指向右節(jié)點(diǎn)swap(mh[pos],mh[tar]);//交換當(dāng)前節(jié)點(diǎn)和他左右節(jié)點(diǎn)中較小的那個(gè)pos=tar;//當(dāng)前節(jié)點(diǎn)移到交換的子節(jié)點(diǎn)處}}template<typenameDATA>voidMyHeap<DATA>二pop(){swap(mh[0],mh[mh.size()-1]);//將隊(duì)首元素放到最后vector<DATA>::iteratorit=mh.end();//迭代器先指向end();it--;//自減操作，此時(shí)it指向最后一個(gè)元素mh.erase(it);//刪除最后一個(gè)元素，即刪除了原隊(duì)首元素push_down();//從隊(duì)首向下更新}template<typenameDATA>voidMyHeap<DATA>二push_up(){intnow=mh.size()-1,tar;while(now>0){//從最后一個(gè)元素開始，直到隊(duì)首tar=(now-1)/2;//tar指向當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)if(mh[tar]<mh[now])break;//如果父節(jié)點(diǎn)是小于當(dāng)前節(jié)點(diǎn)，則不用再上移swap(mh[tar],mh[now]);//否則交換父節(jié)點(diǎn)和當(dāng)前節(jié)點(diǎn)now=tar;//當(dāng)前節(jié)點(diǎn)改為父節(jié)點(diǎn)}}template<typenameDATA>voidMyHeap<DATA>二push(constDATA&item){mh.push_back(item);//先將新節(jié)點(diǎn)加到最后push_up();//再向上更新}template<typenameDATA>voidMyHeap<DATA>二update(){//所有元素-1for(inti=0;i<mh.size();i++)mh[i]--;

template<typenameDATA>intMyHeap<DATA>::size(){returnmh.size();//返回向量的大小}template<typenameDATA>voidMyHeap<DATA>::show(){graph(0);}遞歸調(diào)用，輸出以s遞歸調(diào)用，輸出以s為根節(jié)點(diǎn)的子樹先輸出左子樹若當(dāng)前節(jié)點(diǎn)存在，輸出當(dāng)前節(jié)輸出右子樹voidMyHeap<DATA>::graph(ints){//if(s*2+1<mh.size())graph(s*2+1);//if(s<mh.size())cout<<mh[s]<<"\n";//點(diǎn)的信息if(s*2+2<mh.size())graph(s*2+2);//}#endifWork.h#include<iostream>usingnamespacestd;#ifndefMYWORK#defineMYWORKclassWork{public:ints,t,p,num;Work();Work(intn,inta,intb);friendbooloperator<(constWork&a,constWork&b);//重定義小于Work&operator--();////自減操作重載Work&operator=(constWork&a);//賦值操作重載friendostream&operator<<(ostream&out,constWork&a);//輸出流重載};#endifSystem.h#ifndefMYSYSTEM#defineMYSYSTEM#include<iostream>#include<stdio.h>#include<vector>#include<time.h>//系統(tǒng)自帶的頭文件都可以#include"Heap.h"http://自己寫的頭文件，要用引號(hào)#include"Work.h"#include<windows.h>usingnamespacestd;classSystem{MyHeap<Work>mw;//隊(duì)列，存儲(chǔ)所有工作intT;//記錄系統(tǒng)運(yùn)行的時(shí)間intend;//如果有作業(yè)在運(yùn)行，記錄該作業(yè)結(jié)束時(shí)的系統(tǒng)時(shí)間booliswork;//是否有作業(yè)正在運(yùn)行Workwk;〃若有作業(yè)在運(yùn)行，記錄該作業(yè)的信息intSIZE;//系統(tǒng)允許新增工作的時(shí)間，超過(guò)此時(shí)間后，系統(tǒng)執(zhí)行完所有作業(yè)后，就結(jié)束public:System();//構(gòu)造函數(shù)，在創(chuàng)建變量時(shí)才會(huì)調(diào)用boolrun();//執(zhí)行函數(shù)，模擬作業(yè)的調(diào)度};#endifWork.cpp#include"Work.h"Work::Work(){}Work::Work(intn,inta,intb){//構(gòu)造函數(shù)num=n;//作業(yè)的編號(hào)s=a;//作業(yè)進(jìn)入的時(shí)間t=p=b;〃作業(yè)的執(zhí)行時(shí)間和優(yōu)先級(jí)}booloperator<(constWork&a,constWork&b){//重定義小于if(a.p!=b.p)returna.p<b.p;//先按優(yōu)先級(jí)排，優(yōu)先級(jí)小的小returna.num<b.num;//否貝U,先進(jìn)入的小//因?yàn)閯?chuàng)建的是最小堆，所以在隊(duì)首的是優(yōu)先級(jí)小的，符合題目要求)Work&Work::operator--(){//自減操作重載P--；return*this;)Work&Work::operator=(constWork&a){//賦值操作重載s=a.s;t=a.t;P=a.p;num=a.num;return*this;)ostream&operator<<(ostream&out,constWork&a){//輸出流重載returnout<<"作業(yè)"<<a.num<<”進(jìn)入時(shí)間為"<<a.s<<"執(zhí)行時(shí)間"<<a.t<<"優(yōu)先級(jí)為“<<a.p;)System.cpp#include"System.h"System::System(){T=0;//初始系統(tǒng)時(shí)間為0iswork=false;//初始沒有作業(yè)在運(yùn)行SIZE=60;)boolSystem::run(){system("cls");intD,L,N;cout<<"請(qǐng)輸入時(shí)間問隔：";cin>>D;if(D<=0){printf("時(shí)間間隔要大于0!!!\n");Sleep(500);returnfalse;)cout<<"請(qǐng)輸入工作時(shí)間：";cin>>SIZE;if(SIZE<=0){printf("工作時(shí)間要大于0!!!\n");Sleep(500);returnfalse;)cout<<”請(qǐng)輸入作業(yè)長(zhǎng)度上限：";cin>>L;if(L<=0){printf("作業(yè)長(zhǎng)度要大于0!!!\n");Sleep(500);returnfalse;)cout<<"請(qǐng)輸入每個(gè)間隔產(chǎn)生的作業(yè)數(shù)的上限：";cin>>N;if(N<=0){printf("產(chǎn)生作業(yè)數(shù)的上限要大于0!!!\n");Sleep(500);returnfalse;)srand(time(0));〃把時(shí)間作為種子，若不調(diào)用此函數(shù)，產(chǎn)生的隨機(jī)數(shù)都是偽隨機(jī)的，每次程序運(yùn)行的結(jié)果都一樣inttol=0;//表示作業(yè)的編號(hào)for(T=0;T<SIZE;T++){〃這段時(shí)間會(huì)隨機(jī)產(chǎn)生新的作業(yè)mw.update();//因?yàn)榈却龝r(shí)間+1,所以隊(duì)列里所有的作業(yè)的優(yōu)先級(jí)-1if(iswork&&end==T){//如果正在運(yùn)行的作業(yè)結(jié)束了iswork=false;//表示沒有作業(yè)在運(yùn)行cout<<"***程序運(yùn)行時(shí)間為"<<T<<",