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

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

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