數(shù)據(jù)結(jié)構(gòu)算法與應(yīng)用語言描述06隊(duì)列

第6章 像堆棧一樣，隊(duì)列也是一種特殊的線性表。隊(duì)列的插入和刪除操作分別性表的兩端進(jìn)行，因此，隊(duì)列是一個(gè)先進(jìn)先出（first-in-first-out,FIFO）的線性表。盡管可以很容易地從線性表類LinearList見程序3-1）和鏈表類Chain見程序3-8）中派生出隊(duì)列類，但在本章中并沒有這樣做。出于對執(zhí)行效率的考慮，我們把隊(duì)列設(shè)計(jì)成一個(gè)基類，分別采用了化描述和5.5.3車廂重排問題。在本章中對這個(gè)問題做了修改，要求緩沖鐵軌按FIFO方式而不是LIFO方式工作；第二個(gè)應(yīng)用是關(guān)于尋找兩個(gè)給定點(diǎn)之間最短路徑的問題，這是一個(gè)經(jīng)典的問題。可以把這個(gè)應(yīng)用看成是5.5.6迷宮題的種化，尋找宮到迷出口最路徑。5.5.6中的代碼并不能保證得到一條最短的路徑，它只能保證如果存在一條從到出口的路徑，則一定能找到這樣一條路徑（沒有限定長度；第三個(gè)應(yīng)用選自計(jì)算機(jī)視覺領(lǐng)域，主要用于識別圖像中的圖元；最后一個(gè)應(yīng)用是一個(gè)工廠仿真程序。工廠內(nèi)有若干臺機(jī)器，每臺機(jī)器能夠執(zhí)行一道不同的工序。每一項(xiàng)任務(wù)都由一系列工序組成。我們給出了一個(gè)仿真程序，它能夠仿真工廠中的任務(wù)流。該程序能夠確定每項(xiàng)任務(wù)所花費(fèi)的總的等待時(shí)間以及每臺機(jī)器所產(chǎn)生的總的等待時(shí)間，可以根據(jù)這些信息來改進(jìn)工廠的設(shè)計(jì)。為了獲得較高的執(zhí)行效率，本章中每個(gè)應(yīng)用都采用了隊(duì)列。在后續(xù)章節(jié)中還會介 [隊(duì)列]隊(duì)列（quene）是一個(gè)線性表，其插入和刪除操作分別在表的不同端進(jìn)行。添加新元素的那一端被稱為隊(duì)尾(rear)，而刪除元素的那一端被成為隊(duì)首(front)。一個(gè)三元素的隊(duì)列如圖6-1aA之后將得到圖6-1b所示的隊(duì)列。如果要向圖6-1b的隊(duì)列中添加一個(gè)元素D，必須把它放在元素C的后面。添加D以后所得到的結(jié)果如圖6-1c所示。圖6-1所以，隊(duì)列是一個(gè)先進(jìn)先出（FIFO）的線性表，而堆棧是一個(gè)先進(jìn)后出（LIFO）的線性表。隊(duì)列的抽象數(shù)據(jù)類型描述見ADT6-1。190 抽象數(shù)據(jù)類型QueueCreate():IsEmpty():如果隊(duì)列為空，則返回true，否則返回false；IsFull():如果隊(duì)列滿，則返回true；否則返回false；First():返回隊(duì)列的第一個(gè)元素；Last():返回隊(duì)列的最后一個(gè)元素；Add(x):向隊(duì)列中添加元素x；Delete(x刪除隊(duì)首元素，并送入x;} location(i)=i- （6-這個(gè)在化描述的堆中工作得很好。果使（6-1把數(shù)組queue[MaxSize]成一個(gè)隊(duì)列，那么第一個(gè)元素為queue[0]，第二個(gè)元素為queue[1]，?。front總是為0，rear始終是最后一個(gè)元素的位置，隊(duì)列的長度為rear+1rear=－1。使用 圖6-2使用（6-1）描述圖6-1中的隊(duì)向隊(duì)列中添加一個(gè)元素時(shí)，需要把rear增1，并把新元素放入queue[rar]。這意味著一次添加操作所需要的時(shí)間為1)。刪除一個(gè)元素時(shí)，把位置1至位置n的元素分別左移一個(gè)位置，因此刪除一個(gè)元素所花費(fèi)的時(shí)間為(n)，其中n為刪除完成之后隊(duì)列中的元素?cái)?shù)。如此看來，公式（6-1）應(yīng)用于堆棧，可使堆棧的插入和刪除操作均耗時(shí)(1)，而應(yīng)用于隊(duì)列，則使隊(duì)列的(n)。如果采用（6-2），就可以使隊(duì)列的刪除操作所需要的時(shí)間減小至(1)location(i)=location(1)+i- （6-從隊(duì)列中刪除一個(gè)元素時(shí)，（6-2）不要求把所有的元素都左移一個(gè)位置，只需簡單 (1)增加1即可。圖6-3給出了在使用（6-2）時(shí)，圖6-1中各隊(duì)列的相應(yīng)描述。注意，在使用（6-2）時(shí)，front=location(1)，rear=location(最后一個(gè)元素)，一個(gè)空隊(duì)列第6章 如圖6-3b所示，每次刪除操作將導(dǎo)致front右移一個(gè)位置。當(dāng)rear<MaxSize-1時(shí)才可以直接在隊(duì)列的尾部添加新元素。若rear=MaxSize-1且front>0時(shí)（表明隊(duì)列未滿），為了能夠繼續(xù)向隊(duì)列尾部添加元素，必須將所有元素平移到隊(duì)列的左端（6-4所示），以便在隊(duì)列的右端留出空間。對于使用（6-1）的隊(duì)列來說，這種平移操作將使情況下的時(shí)間復(fù)雜性增加(1)，而對于使用（6-2）的隊(duì)列來說，情況下的時(shí)間復(fù)雜性則增加了(n)。所以，使用（6-2）在提高刪除操作執(zhí)行效率的同時(shí)，卻降低了添加操作的執(zhí)行效率。圖6-3使 圖6-4a)移位之前b) location(i)=(location(1)+i-1)%MaxSize 這時(shí)，用來描述隊(duì)列的數(shù)組被視為一個(gè)環(huán)（如圖6-5所示。在這種情況下，對front的約定發(fā)生了變化，它指向隊(duì)列首元素的下一個(gè)位置（逆時(shí)針方向），而rear的含義不變。向圖6-6-5b所示的隊(duì)列，而從圖6-5b的隊(duì)列中刪除一個(gè)元素則得到圖6-5c所示的隊(duì)列。 圖6-5a)初始狀態(tài)b)添加c) 當(dāng)且僅當(dāng)front=rear時(shí)隊(duì)列為空。初始條件front=rear=0定義了一個(gè)初始為空的隊(duì)列?，F(xiàn)在需要確定隊(duì)列為滿的條件。如果不斷地向圖6-5b的隊(duì)列添加元素，直到隊(duì)列滿為止，那么將看到圖6-6情形。這時(shí)有front=rear隊(duì)列添加一個(gè)元前，先判斷一下本次操作是否會大容量實(shí)際上是MaxSize-。

可用程序6-1所示的C+類來實(shí)現(xiàn)抽象數(shù)據(jù)類型uue。在實(shí)現(xiàn)化描述的堆棧時(shí)（見程序51，為了簡化代碼的設(shè)計(jì)，重用了ieaLit類（見程序3-1）的定義。然而不能通過使用同樣的方法來實(shí)現(xiàn)ee類，因?yàn)閡eue的實(shí)現(xiàn)基（6-3），而Lnarit的實(shí)現(xiàn)基于公式（6-1。程序6-2和程序6-3給出了ueue成員函數(shù)的代碼。注意觀察ueue的構(gòu)造函數(shù)是怎112個(gè)整數(shù)隊(duì)列的成員函數(shù)與堆棧的對應(yīng)函數(shù)相類似，因此這里不再具體介紹這些函數(shù)。當(dāng)T是一個(gè)內(nèi)部數(shù)據(jù)類型時(shí)，隊(duì)列構(gòu)造函數(shù)和析構(gòu)函數(shù)的復(fù)雜性均為(1)；而當(dāng)T是一個(gè)用戶定義的類時(shí)，構(gòu)造函數(shù)和析構(gòu)函數(shù)的復(fù)雜性均為O(MaxStackSize)。其他隊(duì)列操作的復(fù)雜性均為(1)。程序6-1化類classQueue{//FIFOQueue(intMaxQueueSize=~Queue(){delete[]boolIsEmpty()const{returnfront==rear;}boolIsFull()const{return(((rear+1)%MaxSize==front)?1:0);}TFirst()const;//返回隊(duì)首元素TLast()const;//Queue<T>&Add(constT&x);Queue<T>&Delete(T&x);intfront與第一個(gè)元素在反時(shí)針方向上相差一個(gè)位置intrear;//指向最后一個(gè)元素intMaxSize;//T*queue;//程序6-2Queuetemte<class第6章 Queue<T>::Queue(intMaxQueueSize的空隊(duì)列MaxSize=MaxQueueSize+1;queue=newT[MaxSize];front=rear=0;}temte<classTQueue<T>::First(){////如果隊(duì)列為空，則異常OutOfBoundsif(IsEmpty())throwOutOfBounds();returnqueue[(front+1)%MaxSize];}temte<classTQueue<T>::Last(){////如果隊(duì)列為空，則異常OutOfBoundsif(IsEmpty())throwOutOfBounds();returnqueue[rear];}程序6- temte<classQueue<T>&Queue<T>::Add(constT&{//x//如果隊(duì)列滿，則異常NoMemif(IsFull())throwNoMem();rear=(rear+1)%MaxSize;queue[rear]=x;return}temte<classQueue<T>&Queue<T>::Delete(T&{//刪除第一個(gè)元素，并將其送入//如果隊(duì)列為空，則異常OutOfBoundsif(IsEmpty())throwOutOfBounds();front=(front+1)%MaxSize;x=queue[front];return*this;}194把一個(gè)隊(duì)列分解成兩個(gè)隊(duì)列，其中一個(gè)隊(duì)列包含原隊(duì)列中的第1、3、5、?個(gè)元素，另合并兩個(gè)隊(duì)列（稱隊(duì)列1和隊(duì)列2，在新隊(duì)列中，從隊(duì)列1開始，兩個(gè)隊(duì)列的元素輪流排列，若某個(gè)隊(duì)列中的元素先用完，則將另一個(gè)隊(duì)列中的剩余元素依次添加在新隊(duì)列的尾部。合并完成后，各元間的相對次序應(yīng)與合并前的相對次序相同。修改程序6-1中的Queue類，使得隊(duì)列的容量與數(shù)組queue的大小相同。為此，可引入另外一個(gè)私有成員LastOp來最后一次隊(duì)列操作?？梢钥隙ǎ绻詈笠淮侮?duì)列操作為Add，則隊(duì)列一定不為空；如果最后一次隊(duì)列操作為Delete，則隊(duì)列一定不會滿。因此，當(dāng)front=rear時(shí)，可使用LastOp給出雙端隊(duì)列的抽象數(shù)據(jù)類型描述，要求包含以下操作：Create，IsEmpty，IsFull，采用（6-3）來描述雙端隊(duì)列。設(shè)計(jì)一個(gè)與雙端隊(duì)列抽象數(shù)據(jù)類型描述相對應(yīng)的front和rear隊(duì)列的兩端，這時(shí)有兩種可能的情形：從fron開始到rear如圖6-7a示）或從rear開鏈接到front（如圖6-7所示。不的方向使添和刪除作的易程有所同。圖6-8和6-9分別演示了添加元素和刪除元素的過程?？梢钥吹?，兩種方向都很適合于添加操作，而從front到rear的更便于刪除操作的執(zhí)行。因此，采用從front到rear的模?？梢匀〕踔礷ront=rear=0，并且認(rèn)定當(dāng)且僅當(dāng)隊(duì)列為空時(shí)front=0。利用3.4.3節(jié)的擴(kuò)展，可以把類LinkedQueue定義為Chain類（見程序3-8）的一個(gè)派生類，練習(xí)6即按照這種方式來實(shí)現(xiàn)程序6-4給出了一個(gè)鏈表隊(duì)列的類定義，程序6-5和程序6-6給出了相應(yīng)的成員函數(shù)。Node類與自定義鏈表堆棧（見程序5-4）于成員函數(shù)的實(shí)現(xiàn)，可把定義為Node的?？梢苑謩e采用空蹤LinkedQueue均為(1)。圖6-7第6章第6章 圖6-8a)向圖6-7a的隊(duì)列添加元素b)向圖6-7ba)從圖6-7a的隊(duì)列中刪除元素b)從圖6-7b程序6-4temte<classT>classLinkedQueue{LinkedQueue(){front=rear=0;}//~LinkedQueue();//boolIsEmpty(){return((front)?false:true);}boolIsFull()const;TFirst()const;//TLast()const;//返回最后一個(gè)元素LinkedQueue<T>&Add(constT&x);LinkedQueue<T>&Delete(T&x);Node<T>*front;//Node<T>*rear;// 程序6-5temte<classT>{//while(front){next=front->link;deletefront;front=}}temte<classboolLinkedQueue<T>::IsFull(){//Node<T>try{p=newNode<T>;deletep;returncatch(NoMem){return}temte<classTLinkedQueue<T>::First(){////如果隊(duì)列為空，則異常OutOfBoundsif(IsEmpty())throwOutOfBounds();returnfront->data;}temte<classTLinkedQueue<T>::Last(){////如果隊(duì)列為空，則異常OutOfBoundsif(IsEmpty())throwOutOfBounds();returnrear->data;}程序6-6temte<classLinkedQueue<T>&LinkedQueue<T>::Add(constT&{//x//不捕獲可能由new的NoMem異Node<T>*p=newNode<T>;p->data=x;p->link=第6章 第6章 //if(front)rear->link=p;//隊(duì)列不為空elsefront=p; //隊(duì)列為空rear=p;return} te<classLinkedQueue<T>&LinkedQueue<T>::Delete(T&{{//刪除第一個(gè)元素，并將其放入//如果隊(duì)列為空，則 if(IsEmpty())throwOutOfBounds();刪除第一個(gè)節(jié)點(diǎn)Node<T*pfront;front=front->link;deletep;return}利用3.4.3節(jié)Chain類的擴(kuò)充版本（Append，從Chain類中派生出鏈表隊(duì)列類采用鏈表隊(duì)列來完成練習(xí)2，所不同的是，要求各操作均就地進(jìn)行而不得使用新節(jié)點(diǎn)。下面來重新一下5.5.3節(jié)的火車車廂重排問題。如圖6-10所示，假定緩沖鐵軌位于入軌FIFO的方式運(yùn)作，因此可將它們視為隊(duì)列。與5.5.3節(jié)一樣，將車廂從緩沖鐵軌移動至入軌，也從出軌移動車廂至緩沖鐵軌。所有的車廂移動都按照圖6-10中箭頭所示的方向進(jìn)行。鐵軌Hk數(shù)目為k-1假定重排9節(jié)車廂，其初始次序?yàn)?,8,1,7,4,2,9,6,3，同時(shí)令k=3。3 圖6-10動到出軌，因?yàn)?號車廂和2號車廂必須排在3號車廂之前。因此，把3號車廂移動至H1。6號車廂可放在H1中36號車廂將在39號車廂可以繼續(xù)放在H1中6號車廂之后，而接下來的2號車廂不可放在9號車廂之后，因?yàn)?號車廂必須在9前輸出。因此，應(yīng)把2號車廂放在H2的首部。之后4號車廂被放在H2中27又被放在41號車廂可通過H3直接移動至出軌，然后從2移動2軌，從H1移動3號車廂至出軌，從H2移動4號車廂至出軌。由于5號車廂此時(shí)仍位于入軌之中，所以把8號車廂移動至H2，這樣就可以把5號車廂直接從入軌移動至出軌。這之后，可依次從緩沖鐵軌中輸出6號、7號、8號和9在把一節(jié)車廂移動到緩沖鐵軌中時(shí)，可以采用如下的原則來確定應(yīng)該把這節(jié)車廂移動到哪一個(gè)緩沖鐵軌。車廂cc；如果有多個(gè)緩沖鐵軌都滿足這一條件，則選擇一個(gè)左端車廂編號最大的緩沖鐵軌；否則選擇一個(gè)空的緩沖鐵軌（如果有的話?？梢圆捎面湵黻?duì)列來實(shí)現(xiàn)車廂重排算法，其中，用鏈表隊(duì)列來表示k-1個(gè)緩沖鐵軌?？梢园凑粘绦?-8、程序-9和程序5-0的模式來設(shè)計(jì)該算法。程序6-7給出了函數(shù)tpt和ld的新代碼。對于程序5-8Railroad，應(yīng)做以下修改：1)將k減1；2)HLinedeu<it>*；3)把in改為in；4)從od的調(diào)用中刪除最后一個(gè)參數(shù)(n)。完成車廂重排所需要的時(shí)間為nk)。借助于L（見第1章），(logk。程序6-7voidOutput(int&minH,int&minQ,LinkedQueue<int>H[],intk,int{//從緩沖鐵軌移動到出軌，并修改minHminQ.intc;//車廂編號從隊(duì)列minQ中刪除編號最小的車廂minHcout<<"Movecar"<<minH<<"fromholdingtrack"<<minQ<<"tooutput"<<通過檢查所有隊(duì)列的首部，尋找新的minH和minQminH=n+2;for(inti=1;i<=k;i++)if(!H[i].IsEmpty()&&(c=H[i].First())<{minH=第6章 minQ=}boolHold(intc,int&minH,int&minQ,LinkedQueue<int>H[],int{//把車廂c//如果沒有可用的緩沖鐵軌，則返回false，否則返回cintBestTrack=0,//目前最優(yōu)的鐵軌BestLast=0,//BestTrack中最后一節(jié)車廂 //車廂編號//for(inti=1;i<=k;if(!H[i].IsEmpty()){//ix=if(c>x&&x>BestLast){//iBestLast=BestTrack=}else//鐵軌iif(!BestTrack)BestTrack=if(!BestTrack)returnfalse;////把ccout<<"Movecar"<<c<<"frominput"<<"toholdingtrack"<<BestTrack<<//如果有必要，則修改minH和if(c<minH){minH=c;minQ=return}如果只是為了簡單地輸出車廂重排過程中所必要的車廂移動次序，那么只需了解每個(gè)緩沖鐵軌的最后一個(gè)成員是誰以及每節(jié)車廂當(dāng)前位于哪個(gè)鐵軌即可。如果緩沖鐵軌i為空，則令lat[i]=0，否則令lat[i]為鐵軌中最后一節(jié)車廂的編號。如果車廂i位于入軌之中，令track[i]=0；否則，令track[i]為車廂所在的緩沖鐵軌。在起始時(shí)有l(wèi)ast[i]=0，1≤i＜k，track[i]=，1≤i≤n。程序6-86-7所產(chǎn)生的輸出完全相同，二者均具有相同程序6- voidOutput(intNowOut,intTrack,int&{//將車廂NowOut從緩沖鐵軌移動到出軌，并修改200cout<<"Movecar"<<NowOut<<"fromholdingtrack"<<Track<<"tooutput"<<endl;if(NowOut==Last)Last=0;}boolHold(intc,intlast[],inttrack[],int{//把車廂c//如果沒有可用的緩沖鐵軌，則返回false，否則返回//c//intBestTrack=0,//BestLast=0,//BestTrack//for(inti=1;i<=k;i++)//findbesttrackif(last[i]){//鐵軌i不為空if(c>last[i]&&last[i]>BestLast){//iBestLast=last[i];BestTrack=i;}}else//iif(!BestTrack)BestTrack=if(!BestTrack)returnfalse;////把c移動到最優(yōu)鐵軌track[c]=BestTrack;last[BestTrack]=c;cout<<"Movecar"<<c<<"frominput"<<"toholdingtrack"<<BestTrack<<return}boolRailroad(intp[],intn,int{//用k//如果重排成功，則返回true，否則返回//如果空間不足，則異常//對數(shù)組last和trackint*last=newint[k+1];int*track=newint[n+1];for(inti=1;i<=k;i++)last[i]=0;//ifor(inti=1;i<=n;i++)track[i]=0;k--;//鐵軌k第6章第6章 intNowOut=for(inti=1;i<=n;if(p[i]==NowOut){//cout<<"Movecar"<<p[i]<<"frominputtooutput"<<endl;while(NowOut<=n&&track[NowOut]){Output(NowOut,track[NowOut],last[NowOut]);}}elsep[i]移動到緩沖鐵軌if(!Hold(p[i],last,track,k))returnfalse;}}在5.5.6節(jié)中，對迷宮老鼠問題的解決方案并不能保證找到一條從迷宮到迷宮出口的最短路徑。而借助于隊(duì)列，可以找到這樣的路徑（如果有的話。在迷宮中尋找最短路徑的問題也存在于其他許多領(lǐng)域。例如，在解決電路布線問題時(shí)，一種很常用的方法就是在布線區(qū)域疊n×m個(gè)方格，就像迷宮一樣，如圖6-1a方格a的中心點(diǎn)連接到另一個(gè)方格b6-1b某線經(jīng)過個(gè)格則方格我望使用a和b之間的最短路徑來作為布線的路徑，以便減少信號的延遲。圖6-11a7×7網(wǎng)格ba與b 先從位置a開始搜索，把a(bǔ)可到達(dá)的相鄰方格都標(biāo)記為1（表示與a相距為1），然后把標(biāo)號為12（表示與a相距為2）b或者找不到可到達(dá)的相鄰方格為止。圖6-12a演示了這種搜索過程，其中a=(3,2)，b=(4,6)。圖中的陰影圖6-12a)標(biāo)識間距b)按照上述搜索過程，當(dāng)我們到達(dá)b時(shí)，就可以在b上標(biāo)出b與a之間的距離，在圖6-12a中，b上的標(biāo)號為9。為了得到a與b之間的最短路徑，從b開始，首先移動到一個(gè)比b位置上。一定存在這樣的相鄰位置，因?yàn)槿我粋€(gè)方格上的標(biāo)號與它相鄰方格上的標(biāo)號都至少相差1。在圖6-1a中，可從b(5,6)1的相鄰位置上，重復(fù)這個(gè)過程，直至到達(dá)a為止。在圖6-12a的例子中，從(5,6)移動到(6,6)，(6,4)，(5,4)，?。圖-12b給出了所得到的路徑?，F(xiàn)來看樣現(xiàn)策，設(shè)出最路的C++代碼。從5.5.6的迷宮解決方案中吸取很多思想。一個(gè)m×0置，1。格在由1構(gòu)成的“墻”中。數(shù)組offets用幫助我們從一個(gè)位置移動到其相鄰位置。用一個(gè)鏈表隊(duì)列來這樣的方格：該方格本身已被編號，而它的相鄰位置尚未被編號。也可以采用化隊(duì)列，所不同的是必須估計(jì)隊(duì)列的最大長度，就像在求解迷宮問題時(shí)估計(jì)堆棧的大小一樣。見程序6-9。程序6- boolFindPath(Positionstart,Positionfinish,int&PathLen,Position*{//尋找從start到finish//如果成功，則返回true，否則返回//如果空間不足，則異常if((start.row==finish.row)&&(start.col==finish.col)){PathLen=0;returntrue;}//start=//第6章 for(inti=0;i<=m+1;i++)grid[0][i]=grid[m+1][i]=1;//grid[i][0]=grid[][m+1]=1;//}//初始化Positionoffset[0].row=0;offset[0].col=1;//右offset[1].row=1;offset[1].col=0;//下offset[2].row=0;offset[2].col=-1;//左offset[3].row=-1;offset[3].col=0;//上intNumOfNbrs=4;//Positionhere,nbr;here.row=start.row;here.col=start.col;grid[start.row][start.col]=2;//標(biāo)記可到達(dá)的網(wǎng)格位置do{//標(biāo)記相鄰位置for(inti=0;i<NumOfNbrs;{nbr.row=here.row+offset[i].row;nbr.col=here.col+offset[i].col;if(grid[nbr.row][nbr.col]==0){//unlabelednbr,labelitgrid[nbr.row][nbr.col]=grid[here.row][here.col]+1;if((nbr.row==finish.row)&&(nbr.col==finish.col))break;//Q.Add(nbr);}//if}//for//已到達(dá)finish嗎if((nbr.row==finish.row)(nbr.col==finish.col))break;////未到達(dá)finish，可移動到nbr嗎if(Q.IsEmpty())returnfalse;//Q.Delete(here);//}PathLen=grid[finish.row][finish.col]-2;path=newPosition[PathLen];here=finish;for(intj=PathLen-1;j>=0;j--{path[j]=// for(inti=0;i<NumOfNbrs;{nbr.row=here.row+offset[i].row;nbr.col=here.col+offset[i].col;if(grid[nbr.row][nbr.col]==j+2)}here=nbr;//}return}在程序6-9的代中，定起位置結(jié)束置均被。程首先查start和finish是否相同，如果相同，則路徑長度為0，程序止否設(shè)一由置的圍”網(wǎng)格包圍起來。然后對offset2（所有標(biāo)號都增加了2，因?yàn)閿?shù)組中采用0和1表位為到圖6-12a所示的標(biāo)號，必須把程序中的每個(gè)標(biāo)號減去2。借助于隊(duì)列Q并從位置tart開始，首先移動到與start相距為1置，然后移動到與tart相距為2finish或者無法繼續(xù)移動到一個(gè)新的、空白的位置。在后一種情況下，將不存在到達(dá)位置finish的路徑，而一種情況下，位置finish將得到一個(gè)相應(yīng)的編號，如果到達(dá)了位置finish，則可以利用網(wǎng)格上的標(biāo)號來重構(gòu)路徑。路徑上的位置（start除外）由于任意一個(gè)網(wǎng)格位置都至多在隊(duì)列中出現(xiàn)1次，所以完成網(wǎng)格編號過程需耗時(shí)O(m2（對一個(gè)m×m的網(wǎng)格來說。而重構(gòu)路徑的過程需耗時(shí)（PathLen，其中PathLen為最短路個(gè)m×m的像素矩。在單像中每個(gè)像素的值要么為0，要么為1，值為01的像素則表示圖元上的一個(gè)點(diǎn)，我們稱其為圖元像素。如果一個(gè)像素在另一個(gè)像素的左側(cè)、上部、右側(cè)或下部，則稱這兩個(gè)像素為相鄰像素。識別圖元就是對圖元像素進(jìn)行標(biāo)記，當(dāng)且僅當(dāng)兩個(gè)像素屬于同一圖元時(shí)，它們的標(biāo)號相同。圖6-13a7×7圖像?？瞻追礁翊肀尘跋袼?，而標(biāo)記為1的方格則代表圖元像素。像素(1,3)和(2,3)(2,4)與（2,3)是相鄰的，它們也同樣屬于同一圖元，因此，三個(gè)像素(1,3)，(2,3)和(2,4)屬于同一圖元。由于沒有其他的像素與這三個(gè)像素相鄰，因此這三個(gè)像素定義了一個(gè)圖元。圖6-13a的圖像中存在4個(gè)圖元，分別是{(1,3),(2,3),(2,4)，{(3,5),(4,4),(4,5),(5,5)，{(5,2),(6,1),(6,2),(6,3),(7,1),(7,2),(7,3)}，{(5,7),(6,7),(7,6),(7,7)}。在圖6-13b中，屬于同一圖元的像素被編上相同的在識別圖元的程序中，采納了許多在解決電路布線問題時(shí)所使用的策略。為了輕松地在圖像中移動，在圖像周圍包上一圈空白像素（即0像素。采用數(shù)組offset來確定與一個(gè)給定像素相鄰的像素。通過逐行掃描像素來識別圖元。當(dāng)遇到一個(gè)沒有標(biāo)號的圖元像素時(shí)，就給它指定一個(gè)圖元編號（使用數(shù)字2,3,?作為圖元編號，該像素就成為一個(gè)新圖元的。通過識別和標(biāo)記與相鄰的所有元像素，可以確圖元中的他像素。我們把與鄰的像素稱為1-1-間距像素相鄰的所有無標(biāo)記圖元像素，這些像素被稱為第6章 第6章 間距像素。之后繼續(xù)識別和標(biāo)記與圖6-13程序6-10首先在圖像周圍包上一圈背景像素（即0像素，并對數(shù)組offset進(jìn)行初始化。接下來的兩個(gè)for環(huán)通過掃描圖像尋找下一個(gè)圖。應(yīng)是一個(gè)無記的圖元像素，對來說，有pixel[r][c]=1。將pixel[r][c]從1變成id（圖元編號，即可把圖元編號設(shè)置為種子的標(biāo)號。接下來借助于鏈表隊(duì)列的幫助（也可以使用化隊(duì)列、鏈表堆?；蚧褩?，可以識別出該圖元中的其余像素。當(dāng)函數(shù)Label結(jié)束時(shí)，所有的圖元像素都已經(jīng)獲得了一個(gè)標(biāo)號。初始化“圍墻”需耗時(shí)()，初始化offet需耗時(shí)(1)。盡管條件pixel[r][c]==1被檢查了m2次，但它為true的次數(shù)只有num次，其中cnm為圖像中圖元的總數(shù)。對于任一圖來說，識別并標(biāo)記該圖元的每個(gè)像素（除外）所需要的時(shí)間為(cnum)。由于任意一個(gè)像素都不會同時(shí)屬于兩個(gè)以上的圖元，因此，識別并標(biāo)記所有非圖元像素所需要的總時(shí)間為(圖像中圖元像素總數(shù))= 輸入圖像中值為1的像素?cái)?shù)目= m2)。因此，函數(shù)Labl時(shí)間復(fù)雜性為(m2)。程序6-10void{//for(inti=0;i<=m+1;i++)pixel[0][i]=pixel[m+1][i]=0;//pixel[i][0]=pixel[i][m+1]=0;//}初始化offsetPositionoffset[4];offset[0].row=0;offset[0].col=1;// offset[1].row=1;offset[1].col=0;//下offset[2].row=0;offset[2].col=-1;//左offset[3].row=-1;offset[3].col=0;//上intNumOfNbrs=4;//intid=1;//圖元idPositionhere,//for(intr=1;r<=m;r圖像的第r行for(intc=1;c<=m;c++)//圖像的第c列if(pixel[r][c]==1){//新圖元}pixel[r][cididhere.row=r;here.col=c;do{//for(inti=0;i<NumOfNbrs;i++)檢查當(dāng)前像素的所有相鄰像素nbr.rowhere.rowoffset[i].row;nbr.col=here.col+offset[i].col;if(pixel[nbr.row][nbr.col]==1)pixel[nbr.row][nbr.col]=id;Q.Add(nbr);}}//endofifandif(Q.IsEmpty())Q.Delete(here);}}//結(jié)束if和}一間工廠由m臺機(jī)器組成。工廠中所執(zhí)行的每項(xiàng)任務(wù)都由若干道工序構(gòu)成，一臺機(jī)器用來完成一道工序，不同的機(jī)器完成不同的工序。一旦一臺機(jī)器開始處理一道工序，它會連續(xù)不斷地進(jìn)行處理，直到該工序被完成為止。例6-1一個(gè)生產(chǎn)金屬片的工廠可能對于如下每道工序都有一臺相應(yīng)的機(jī)器：設(shè)計(jì)、切割、鉆每項(xiàng)任務(wù)都包含若干道工序。例如，為了在一個(gè)新房子內(nèi)安裝暖氣管道和空調(diào)管道，首先需要花一些時(shí)間來進(jìn)行設(shè)計(jì)，然后根據(jù)設(shè)計(jì)要求把整塊的金屬片切割成各種尺寸的金屬片，在金屬片上鉆孔或挖孔（取決于孔的大小，把金屬片塑造成管道，焊接管縫，并對粗糙的邊進(jìn)第6章 間，一是執(zhí)行該工序的機(jī)器。一項(xiàng)任務(wù)中的各道工序必須按照一定的次序來執(zhí)行。一項(xiàng)任務(wù)的執(zhí)行是從處理第一道工序的機(jī)器開始的，當(dāng)?shù)谝坏拦ば蛲瓿珊?，任?wù)轉(zhuǎn)至處理第二道工序的則該任務(wù)將不得不等待。事實(shí)上，很可能有多項(xiàng)任務(wù)同時(shí)在同一臺機(jī)器旁等待。在工廠中每臺機(jī)器都可以有如下三種狀態(tài)：活動、空閑和轉(zhuǎn)換。在活動狀態(tài)，機(jī)器正在處理一道工序，而在空閑狀態(tài)機(jī)器無事可做。在轉(zhuǎn)換狀態(tài)，機(jī)器剛剛完成一道工序，并在為一項(xiàng)新任務(wù)的執(zhí)行做準(zhǔn)備，比如機(jī)器操作員可能需要清理機(jī)器并稍作休息等。每臺機(jī)器在轉(zhuǎn)換狀態(tài)期間所花費(fèi)的時(shí)間可能各不相同。當(dāng)一臺機(jī)器可以處理一項(xiàng)新任務(wù)時(shí)，它可能需要從各個(gè)等待者中挑選一項(xiàng)任務(wù)來執(zhí)行。在這里，每臺機(jī)器都按照FIFO的方式來處理等待者，因此每臺機(jī)器旁的等待者構(gòu)成了一個(gè)FIFO隊(duì)列。在其他類型的工廠中，可以為每項(xiàng)任務(wù)指定不同的優(yōu)先權(quán)，當(dāng)機(jī)器變成空閑時(shí)，從等待者中首先選擇具有最高優(yōu)先權(quán)的任務(wù)來執(zhí)行。一項(xiàng)任務(wù)最后一道工序的完成時(shí)間被稱為任務(wù)完成時(shí)間。一項(xiàng)任務(wù)的長度等于其所有工序l的任務(wù)在0時(shí)刻到達(dá)工廠并在f時(shí)刻結(jié)束，那么它在各機(jī)器f－l。為了讓顧客滿意，希望盡量減少任務(wù)在機(jī)器隊(duì)列中的等待時(shí)間。如果能夠知道每項(xiàng)任務(wù)所花費(fèi)的等待時(shí)間是多少，并且知道哪些機(jī)器所導(dǎo)致的等待時(shí)間最多，就可以據(jù)此來改進(jìn)和提高工廠的效能。在對工廠進(jìn)行仿真時(shí)，我們只是讓任務(wù)在機(jī)器間流動，并沒有實(shí)際執(zhí)行任何工序，而是采用一個(gè)模擬時(shí)鐘來進(jìn)行仿真計(jì)時(shí)，每當(dāng)一道工序完成或一項(xiàng)新任務(wù)到達(dá)工廠時(shí)，模擬時(shí)鐘就推我們稱發(fā)生了一個(gè)（event。另外，還存在一個(gè)啟動（startevent，用來啟動仿真過程。下面的例子演示了在仿真期間沒有新任務(wù)到達(dá)工廠時(shí)的仿真過程。 一間工廠，它由m=3臺機(jī)器構(gòu)成，可以處理n=4項(xiàng)任務(wù)。假定所有四項(xiàng)任務(wù)都在0三臺機(jī)器M1、M2和M3的轉(zhuǎn)換狀態(tài)所花費(fèi)的時(shí)間分別為2、0和1。因此，當(dāng)一道工序完成時(shí)，機(jī)器M1在啟動下一道工序之前必須等待2M2可以立即啟動下一道工序，機(jī)器M3必須等待16-14a分別列出了四項(xiàng)任務(wù)的特征。例如，1號任務(wù)有3道工序。每道工序用形如（machine，time）的值對來描述。1號任務(wù)的第一道工序?qū)⒃贛1上完成，需花費(fèi)的時(shí)間為2個(gè)時(shí)間單元，第二道工序?qū)⒃贛2上完成，需花費(fèi)的時(shí)間為4個(gè)時(shí)間單元，第三道工序?qū)⒃贛1上完成，需花費(fèi)的時(shí)間為1個(gè)時(shí)間單元。各項(xiàng)任務(wù)的長度分別為圖6-14b41號任務(wù)和3M1上執(zhí)行，因此這兩項(xiàng)任務(wù)被放入M1的隊(duì)列中。2號任務(wù)和4號任務(wù)的第一道工序?qū)⒃贛3上執(zhí)行，因此這兩項(xiàng)任務(wù)被放入M3的隊(duì)列中。M2的隊(duì)列為空。在啟動仿真過程之初，所有3I表示機(jī)器處于空閑狀態(tài)。若一臺機(jī)器處于空閑狀態(tài)，那么該機(jī)器完成當(dāng)前工序（實(shí)際上不存在）的時(shí)間沒有定義，可用符號L來表示。仿真從0時(shí)刻開始，即第一個(gè)——啟動 的第一個(gè)任務(wù)被調(diào)度到相應(yīng)的機(jī)器上執(zhí)行。因此，1號任務(wù)的第一道工序被調(diào)度到M1上執(zhí)行，208 圖6-14a)任務(wù)特征b)包含4M21號任務(wù)成為M12號任務(wù)成為M3上下一個(gè)在時(shí)刻2出現(xiàn)，這個(gè)時(shí)刻是根據(jù)最小的機(jī)器完成時(shí)間來確定的。在時(shí)刻2，M1完成了它的當(dāng)前活動工序，它是1號任務(wù)的工序。此后1號任務(wù)將被移動到M2上以執(zhí)行下一道工序。由于M2是空閑的，因此1號任務(wù)的第二道工序?qū)⒘⒓撮_始執(zhí)行，這道工序?qū)⒃诘?個(gè)時(shí)刻完成（當(dāng)前時(shí)刻2+工時(shí)4。從時(shí)刻2開始，M1進(jìn)入轉(zhuǎn)換狀態(tài)并將持續(xù)2個(gè)時(shí)間單元，這期間，在時(shí)刻4，M1和M3都完成了它們自己的當(dāng)前工序。由于M1完成的是一個(gè)“轉(zhuǎn)換”工序，所以它開始執(zhí)行新的任務(wù)。為此，從M1的隊(duì)列中選擇第一個(gè)任務(wù)——3號任務(wù)。3號任務(wù)第一個(gè)工序的長度為4，所以該工序的結(jié)束時(shí)間為8，8也同時(shí)成為M1的完成時(shí)間。M3上的2號任務(wù)依此類推能夠給出后續(xù)的序列。2號和4號任務(wù)在第12時(shí)刻完成，1號任務(wù)在第15時(shí)刻完成，3號任務(wù)在第19時(shí)刻完成。由于2號任務(wù)的長度為6，而它的完成時(shí)刻為12，所以2在隊(duì)列中所花費(fèi)的等待時(shí)間為12-6=6個(gè)時(shí)間單元。類似地，4號任務(wù)在隊(duì)列中的等待時(shí)間為12-4=8個(gè)時(shí)間單元，號和號任務(wù)的等待時(shí)間分別為個(gè)時(shí)間單元?？偟牡却龝r(shí)間為個(gè)時(shí)間第6章 可以確定這33個(gè)單元等待時(shí)間在3臺機(jī)器上的具體分布。例如，4號任務(wù)在0時(shí)刻進(jìn)入M3的隊(duì)列，直到時(shí)刻5才開始被執(zhí)行，所以該項(xiàng)任務(wù)在M3的隊(duì)列中所花費(fèi)的等待時(shí)間為5個(gè)時(shí)間單14b，可以計(jì)算出在M1和M2上所花費(fèi)的等待時(shí)間分別為18和10個(gè)時(shí)間單元。正如我們所預(yù)料的，各任務(wù)的等待時(shí)間之和（33）就等于在各機(jī)器上所花費(fèi)的等待時(shí)間之和。由于仿真器是一個(gè)相當(dāng)復(fù)雜的程序，因此可以把它分解成若干個(gè)模塊。仿真器所執(zhí)行的主要任務(wù)是：輸入數(shù)據(jù)，把各任務(wù)按其第一道工序放入相應(yīng)隊(duì)列；執(zhí)行啟動（即裝入初始任務(wù)）；處理所有（即執(zhí)行實(shí)際仿真）和輸出隊(duì)列待時(shí)間分別用一個(gè)++函數(shù)實(shí)現(xiàn)真項(xiàng)每都如NoMem和BadInput（的輸入數(shù)據(jù)）的異常。主函數(shù)見程序6-11，其中的catch語句可用若干條catch語句來替代，每條catch語句用于一種異常，并輸出不同的信息。練習(xí)19要求你完成這項(xiàng)工作。程序6-11voidtry{ //StartShop();// //OutputStats();}//catch(...)cout<<"Anexceptionhasoccurred"<<}類在設(shè)計(jì)程序6-11中所調(diào)用的四個(gè)函數(shù)之前，必須設(shè)計(jì)所需要的數(shù)據(jù)對象，這些數(shù)據(jù)對象包括工序、任務(wù)、機(jī)器和表。每個(gè)工序都由兩部分構(gòu)成：machine（該工序?qū)⒃谶@臺機(jī)器上處理）和time（完成該工序所需要的時(shí)間。程序6-12給出了類Task的定義。由于對機(jī)器從1至m編號，所以machine是int類型（也可使用類型unsigned。假定所有的時(shí)間都是整數(shù)，time的類型被定義為long以便于執(zhí)行長時(shí)間的仿真。類Task有兩個(gè)：類Job和函數(shù)MoveToNextMachine。把Job定義為Task的是因?yàn)镴ob需要Task的私有成員。也可以避免這種，方法是為Task定義一些共享成員函數(shù)，用以設(shè)置和獲取machine和time類每項(xiàng)任務(wù)都有一個(gè)相關(guān)的工序表，每道工序按表中的次序執(zhí)行。因此，工序表可以被描述成一個(gè)隊(duì)列askQ。為了確定一項(xiàng)任務(wù)所花費(fèi)的總共的等待時(shí)間，需要知道該任務(wù)的長度和完成時(shí)間。完成時(shí)間由計(jì)時(shí)來確定，而長度則為各工序的工時(shí)之和。為了確定任務(wù)的長度，我們?yōu)镴ob定義了一個(gè)私有數(shù)據(jù)成員Length。210askQ定義成一個(gè)指針，以便動態(tài)構(gòu)造一個(gè)足夠大的化隊(duì)列，以容納所期望數(shù)量的工序。對于這種受限制的仿真器來說，這個(gè)定義工作得很好，因?yàn)槲覀兗俣ㄔ诜抡骈_始之后不再有新的任務(wù)進(jìn)入工廠。若使用鏈表隊(duì)列，則只要完成一道工序，即可釋放該工序所占用的隊(duì)列節(jié)點(diǎn)，被釋放的節(jié)點(diǎn)可重新用來構(gòu)造新任務(wù)的工序隊(duì)列。若使用化隊(duì)列，則僅當(dāng)整個(gè)任務(wù)都已經(jīng)完成時(shí)才釋放空間，因此，仿真很可能因?yàn)榭臻g不足而失敗，即使中只剩下很少量的工序未被完成。私有成員Arriveime用于記錄一項(xiàng)任務(wù)進(jìn)入當(dāng)前機(jī)器隊(duì)列的時(shí)間，可用來確定任務(wù)在這個(gè)隊(duì)列中的等待時(shí)間。任務(wù)標(biāo)識符在ID之中，僅在輸出任務(wù)的總等待時(shí)間時(shí)，才會使用該標(biāo)識符。共享成員函數(shù)ddTakp需要t個(gè)時(shí)間單元。該函數(shù)僅用于數(shù)據(jù)輸入過程。當(dāng)從一個(gè)機(jī)器隊(duì)列中移出一項(xiàng)任務(wù)并將其變DeleteTak。該函數(shù)從工序隊(duì)列（工序隊(duì)列用于保存尚未被處理的工序）中刪除排在隊(duì)首的工序，然后返回該工序的時(shí)間并將其加入所屬任務(wù)的長度Lngth程序6-12類Task和classTaskfriendclassfriendboolMoveToNextMachine(Job*);longtime;intmachine;classJobfriendboolMoveToNextMachine(Job*);friendJob*ChangeState(int);friendvoidSimulate();friendclassMachine;Job(longid){ID=Length=ArriveTime=0;}voidAddTask(intp,longt){Taskx;x.machine=p;x.time=t;longDeleteTask(){//Taskx;Length+=x.time;returnx.time;}LinkedQueue<TaskTaskQ;longLength; 工序時(shí)間longArriveTime;//第6章 long5.類每臺機(jī)器都包含如下三個(gè)屬性：轉(zhuǎn)換時(shí)間、當(dāng)前任務(wù)和等待隊(duì)列。由于任務(wù)是一個(gè)相當(dāng)大的對象（有自己的工序隊(duì)列和其他數(shù)據(jù)成員，因此把保存等待任務(wù)的隊(duì)列定義成一個(gè)指針隊(duì)列（每個(gè)指針指向一個(gè)任務(wù)）可以大大提高處理效率，這樣每個(gè)機(jī)器隊(duì)列的操作處理的是指針由于每項(xiàng)任務(wù)任意時(shí)刻只會在一臺機(jī)器上，所以所有隊(duì)列總的空間需求與任務(wù)的數(shù)目直接相關(guān)。不過，任務(wù)在各個(gè)機(jī)器隊(duì)列中的分布會隨著仿真的進(jìn)行而不斷變化。某一時(shí)刻出現(xiàn)幾個(gè)很長的隊(duì)列是完全可能的，而稍后這些隊(duì)列可能會變短，其他隊(duì)列會變長。如果采用化隊(duì)列，則必須把每個(gè)機(jī)器隊(duì)列的大小都定義成最大可能的值。（否則必須動態(tài)調(diào)整隊(duì)列所在數(shù)組的大小，此時(shí)，需要m*(n-1)（m是機(jī)器的數(shù)目，n是任務(wù)的數(shù)目第6章 long5.類每臺機(jī)器都包含如下三個(gè)屬性：轉(zhuǎn)換時(shí)間、當(dāng)前任務(wù)和等待隊(duì)列。由于任務(wù)是一個(gè)相當(dāng)大的對象（有自己的工序隊(duì)列和其他數(shù)據(jù)成員，因此把保存等待任務(wù)的隊(duì)列定義成一個(gè)指針隊(duì)列（每個(gè)指針指向一個(gè)任務(wù)）可以大大提高處理效率，這樣每個(gè)機(jī)器隊(duì)列的操作處理的是指針由于每項(xiàng)任務(wù)任意時(shí)刻只會在一臺機(jī)器上，所以所有隊(duì)列總的空間需求與任務(wù)的數(shù)目直接相關(guān)。不過，任務(wù)在各個(gè)機(jī)器隊(duì)列中的分布會隨著仿真的進(jìn)行而不斷變化。某一時(shí)刻出現(xiàn)幾個(gè)很長的隊(duì)列是完全可能的，而稍后這些隊(duì)列可能會變短，其他隊(duì)列會變長。如果采用化隊(duì)列，則必須把每個(gè)機(jī)器隊(duì)列的大小都定義成最大可能的值。（否則必須動態(tài)調(diào)整隊(duì)列所在數(shù)組的大小，此時(shí)，需要m*(n-1)（m是機(jī)器的數(shù)目，n是任務(wù)的數(shù)目用鏈表隊(duì)列，則只需要n個(gè)任務(wù)指針和n個(gè)共享成員函數(shù)IEpty當(dāng)且僅當(dāng)任務(wù)隊(duì)列為空時(shí)返回tr。共享成員函數(shù)dJo中添加一項(xiàng)任務(wù)。函數(shù)tChnge用于在輸入期間設(shè)置haneie的值。函數(shù)atu用于返回該所有機(jī)器的完成時(shí)間被在一個(gè)表中。為了從一個(gè)轉(zhuǎn)向下一個(gè)，必須確定最小的機(jī)器完成時(shí)間。仿真器還需要一個(gè)設(shè)置一臺機(jī)器的完成時(shí)間的操作，每當(dāng)一個(gè)新任務(wù)被調(diào)度到一臺機(jī)器上運(yùn)行時(shí)就要執(zhí)行該操作。當(dāng)一臺機(jī)器變成空閑時(shí)，其完成時(shí)間被設(shè)置成一個(gè)程序6-13類classMachinefriendJob*ChangeState(int);Machine(){TotalWait=NumTasks=0;Active=0;}boolIsEmpty(){returnJobQ.IsEmpty();}voidAddJob(Job*x){JobQ.Add(x);}voidSetChange(longw){ChangeTime=w;}voidStats(long&tw,long&nt){tw=TotalWait;nt=NumTasks;}LinkedQueue<Job*JobQ等待隊(duì)列l(wèi)ongChangeTime;//機(jī)器轉(zhuǎn)換時(shí)間longTotalWait;//機(jī)器總的等待時(shí)間longNumTasks;//Job 2126.類程序6-14給出了類EventList的定義，它用一個(gè)一維數(shù)組Finishime來處理，其中FinishTime[p]表示機(jī)器p的完成時(shí)間。初始化時(shí)，所有的機(jī)器都是空閑的，它們的完成時(shí)間都被設(shè)置為BigT。機(jī)器數(shù)目用變量NumMachine函數(shù)NextEvent用于返回下一個(gè)對應(yīng)的機(jī)器p和完成時(shí)間t。對于一個(gè)有m臺機(jī)器的工廠， (m)，因此函數(shù)NextEvent的復(fù)雜性為 (m)。函數(shù)SetFinishTime用來設(shè)置一臺機(jī)器的完成時(shí)間，其復(fù)雜性為 ——堆和最左樹，也可以用它們來描述。如果使用堆或最左樹， NextEventetiihie的雜性變成(ogm。如所有務(wù)工序總為，真器分別用T)次exEent和 (次etiniTm。在程序6-14調(diào)用etEen和tiniTm所花的時(shí)間為()，使用或最樹，需要時(shí)間為Tlom)雖然或最樹更雜，當(dāng)較它大仿。程序6-14類class{EventList(intm,long~EventList(){delete[]FinishTime;}voidNextEvent(int&p,long&t);longNextEvent(intp){returnFinishTime[p];}voidSetFinishTime(intp,longt){FinishTime[p]=long*FinishTime;//intNumMachines;//EventList::EventList(intm,longif(m<1)throwBadInitializers();FinishTime=newlong[m+1];NumMachines=m;for(inti=1;i<=m;i++)FinishTime[i]=BigT;}voidEventList::NextEvent(int&p,long&{//返回下一個(gè)所對應(yīng)的機(jī)器和完成時(shí)//p=t=for(inti=2;i<=NumMachines;i++)if(FinishTime[i]<t){//i較早完成p=t=}第6章 第6章 7.程序6-11的四個(gè)函數(shù)中所使用的全局變量見程序6-15。多數(shù)全局變量的含義從變量名中就可以看出來。NowNow的值。程序6- longNow=0;intm;longlongLargeTime=10000;EventList*EL;Machine8.函數(shù)(machine,time)的形式輸入每個(gè)工序。任務(wù)的第一道工序所對應(yīng)的機(jī)器記錄在變量p中。當(dāng)一個(gè)任務(wù)的所有工序都已輸入完畢時(shí)，該任務(wù)（實(shí)際上是指向該任務(wù)的指針）p的隊(duì)程序6- void{//cout<<"Enternumberofmachinesandjobs"<<endl;cin>>m>>n;if(m<1||n<1)throw//創(chuàng)建表和機(jī)器隊(duì)EL=newEventList(m,LargeTime);M=newMachine[m+1];//cout<<"Enterchange-overtimesformachines"<<endl;for(intj=1;j<=m;j++){longct;//cin>>if(ct<0)throwBadInput();}//輸入nJobfor(inti=1;i<=n;i++)coutEnternumberoftasksforjobiendl;inttasks;//工序數(shù)目214intfirst;//cin>>if(tasks<1)throwBadInput();J=newJob(i);cout<<"Enterthetasks(machine,time)"<<"inprocessorder"<<endl;for(intj=1;j<=tasks;j++){//輸入工序intp;//longtt;//cin>>p>>if(p<1||p>m||tt<1)throwBadInput();if(j==1)first=p;//任務(wù)的第一臺機(jī)器J->AddTask(p,tt);//}M[first].AddJob(J);//}}為了啟動仿真，需要從每個(gè)機(jī)器任務(wù)隊(duì)列中取出第一個(gè)任務(wù)并放到該機(jī)器上執(zhí)行。由于每臺機(jī)器的初始狀態(tài)為空閑狀態(tài)，為了加載初始任務(wù)，需要把機(jī)器從空閑狀態(tài)變成活動狀態(tài)（在仿真進(jìn)行過程中也如此。函數(shù)ChangeState(i)可用來轉(zhuǎn)換機(jī)器i的狀態(tài)。在程序6-17中，為了啟動仿真，只需對每臺機(jī)器調(diào)用ChangeState即可