隊(duì)列分析抽象數(shù)據(jù)類型

1第6章隊(duì)列(QUEUES)2本章內(nèi)容6.1抽象數(shù)據(jù)類型6.2公式化描述6.3鏈表描述6.4應(yīng)用2/6/20233隊(duì)列的實(shí)現(xiàn)隊(duì)列的應(yīng)用本章重點(diǎn)46.4應(yīng)用6.4.1火車車廂重排6.4.2電路布線6.4.3圖元識(shí)別6.4.4工廠仿真56.4.1火車車廂重排緩沖鐵軌位于入軌和出軌之間入軌右端->緩沖鐵軌入軌右端->出軌緩沖鐵軌右端->出軌

禁止

:將車廂從緩沖鐵軌移動(dòng)至入軌從出軌移動(dòng)車廂至緩沖鐵軌鐵軌Hk為可直接將車廂從入軌移動(dòng)到出軌的通道6車廂移動(dòng)到緩沖鐵軌的原則車廂c應(yīng)移動(dòng)到這樣的緩沖鐵軌中：該緩沖鐵軌中現(xiàn)有各車廂的編號(hào)均小于c；如果有多個(gè)緩沖鐵軌都滿足這一條件，則選擇一個(gè)左端車廂編號(hào)最大的緩沖鐵軌；否則選擇一個(gè)空的緩沖鐵軌（如果有的話）。2/6/20237從前至后依次檢查入軌上的所有車廂。如果正在檢查的車廂就是下一個(gè)滿足排列要求的車廂，可以直接把它放到出軌上去。如果不是，則把它移動(dòng)到緩沖鐵軌上，直到按輸出次序要求輪到它時(shí)才將它放到出軌上。重排演示?；疖囓噹嘏欧桨?火車車廂重排思路intNowOut=1；//NowOut:下一次要輸出的車廂號(hào)for（inti=1;i<=n;i++）//從前至后依次檢查的所有車廂{1.車廂p[i]從入軌上移出2.If(p[i]==NowOut)//NowOut:下一次要輸出的車廂號(hào)①使用緩沖鐵軌Hk把p[i]放到出軌上去;NowOut++;②while(minH(當(dāng)前緩沖鐵軌中編號(hào)最小的車廂)==NowOut）{把minH放到出軌上去;

更新minH,minQ（minH所在的緩沖鐵軌）;NowOut++;}else按照分配規(guī)則將車廂p[i]送入某個(gè)緩沖鐵軌}讀程序

6-76-82/6/20239boolRailroad(intp[],intn,intk){//k個(gè)緩沖鐵軌，車廂初始排序?yàn)閜[1:n]//如果重排成功，返回true，否則返回false//如果內(nèi)存不足，則引發(fā)異常NoMem。//創(chuàng)建與緩沖鐵軌對(duì)應(yīng)的堆棧LinkedQueue<int>*H;H=newLinkedQueue<int>[k];k--;intNowOut=1;//下一次要輸出的車廂intminH=n+l;//緩沖鐵軌中編號(hào)最小的車廂intminQ;//minH號(hào)車廂對(duì)應(yīng)的緩沖鐵軌火車車廂重排程序-隊(duì)列2/6/202310//車廂重排for(inti=1;i<=n;i++) if(p[i]==NowOut){//直接輸出t cout<<“將車廂”<<p[i]<<“從入軌移至出軌"<<endl;

NowOut++; //從緩沖鐵軌中輸出

while(minH==NowOut){

Output(minH,minQ,H,k,n); NowOut++; } }else{//將p[i]送入某個(gè)緩沖鐵軌

if(!Hold(p[i],minH,minQ,H,k)) returnfalse;}returntrue;}火車車廂重排程序2/6/202311voidOutput(int&minH,int&minQ,LinkedQueue<int>H[],intk,intn){//從緩沖鐵軌移動(dòng)到出軌，并修改minH和minQ. intc;//車廂編號(hào)

//從隊(duì)列minQ中刪除編號(hào)最小的車廂minH

H[minQ].Delete(c); cout<<"Movecar"<<minH<<"fromholdingtrack"<<minQ<<"tooutput"<<endl; //通過檢查所有隊(duì)列的首部，尋找新的minH和minQ minH=n+2; for(inti=1;i<=k;i++) if(!H[i].IsEmpty()&&c=H[i].First())<minH){ minH=c; minQ=i;}}Output函數(shù)2/6/202312boolHold(intc,int&minH,int&minQ,LinkedQueue<int>H[],intk){//把車廂c移動(dòng)到緩沖鐵軌中//如果沒有可用的緩沖鐵軌，則返回false，否則返回true//為車廂c尋找最優(yōu)的緩沖鐵軌//初始化intBestTrack=0,//目前最優(yōu)的鐵軌

BestLast=0,//BestTrack中最后一節(jié)車廂

x;//車廂編號(hào)Hold函數(shù)2/6/202313//掃描緩沖鐵軌for(inti=1;i<=k;i++) if(!H[i].IsEmpty()){//鐵軌i不為空

x=H[i].Last(); if(c>x&&x>BestLast){//鐵軌i尾部的車廂編號(hào)較大

BestLast=x; BestTrack=i;} }else//鐵軌i為空

if(!BestTrack)BestTrack=i;Hold函數(shù)2/6/202314if(!BestTrack)returnfalse;//沒有可用的鐵軌//把c移動(dòng)到最優(yōu)鐵軌H[BestTrack].Add(c);cout<<"Movecar"<<c<<"frominput"<<"toholdingtrack"<<BestTrack<<endl;//如果有必要，則修改minH和minQif(c<minH){minH=c;minQ=BestTrack;}returntrue;}復(fù)雜性？Hold函數(shù)2/6/202315在迷宮中尋找最短路徑的問題也存在于其他許多領(lǐng)域。例如，在解決電路布線問題時(shí)，一種很常用的方法就是在布線區(qū)域疊上一個(gè)網(wǎng)格，該網(wǎng)格把布線區(qū)域劃分成n×m個(gè)方格，就像迷宮一樣。從一個(gè)方格a的中心點(diǎn)連接到另一個(gè)方格b的中心點(diǎn)時(shí)，轉(zhuǎn)彎處必須采用直角。如果已經(jīng)有某條線路經(jīng)過一個(gè)方格，則封鎖該方格。我們希望使用a和b之間的最短路徑來(lái)作為布線的路徑，以便減少信號(hào)的延遲。6.4.2迷宮最短路徑問題擴(kuò)展2/6/202316電路布線2/6/202317為了找到網(wǎng)格中位置a和b之間的最短路徑，先從位置a開始搜索，把a(bǔ)可到達(dá)的相鄰方格都標(biāo)記為1(表示與a相距為1)然后把標(biāo)號(hào)為1的方格可到達(dá)的相鄰方格都標(biāo)記為2(表示與a相距為2)繼續(xù)進(jìn)行下去直到到達(dá)b或者找不到可到達(dá)的相鄰方格為止。方案2/6/202318方案演示2/6/202319為了得到a與b之間的最短路徑，從b開始首先移動(dòng)到一個(gè)比b的編號(hào)小的相鄰位置上。一定存在這樣的相鄰位置，因?yàn)槿我粋€(gè)方格上的標(biāo)號(hào)與它相鄰方格上的標(biāo)號(hào)都至少相差1。接下來(lái)，從當(dāng)前位置開始，繼續(xù)移動(dòng)到比當(dāng)前標(biāo)號(hào)小1的相鄰位置上。重復(fù)這個(gè)過程，直至到達(dá)a為止。輸出方案2/6/202320boolFindPath(Positionstart,Positionfinish,int&PathLen,Position*&path){//尋找從start到finish的路徑//如果成功，則返回true，否則返回false//如果空間不足，則引發(fā)異常NoMemif((start.row==finish.row)&&(start.col==finish.col)) {PathLen=0;returntrue;}//start=finish//初始化包圍網(wǎng)格的“圍墻”for(inti=0;i<=m+1;i++){ grid[0][i]=grid[m+1][i]=1;//底和頂

grid[i][0]=grid[i][m+1]=1;//左和右}尋找電路布線最短路徑2/6/202321//初始化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;//一個(gè)網(wǎng)格位置的相鄰位置數(shù)Positionhere,nbr;here.row=start.row;here.col=start.col;grid[start.row][start.col]=2;//封鎖尋找電路布線最短路徑2/6/202322//標(biāo)記可到達(dá)的網(wǎng)格位置LinkedQueue<Position>Q;do{//標(biāo)記相鄰位置

for(inti=0;i<NumOfNbrs;i++){ nbr.row=here.row+offset[i].row; nbr.col=here.col+offset[i].col; if(grid[nbr.row][nbr.col]==0){//新位置

grid[nbr.row][nbr.col]=grid[here.row][here.col]+1; if((nbr.row==finish.row)&&(nbr.col==finish.col)) break;//完成

Q.Add(nbr);}//if結(jié)束

}//for結(jié)束尋找電路布線最短路徑2/6/202323 //已到達(dá)finish嗎? if((nbr.row==finish.row)&& (nbr.col==finish.col)) break;//完成

//未到達(dá)finish，可移動(dòng)到nbr嗎? if(Q.IsEmpty())returnfalse;//沒有路徑

Q.Delete(here);//到下一位置}while(true);尋找電路布線最短路徑電路布線過程-隊(duì)列狀態(tài)2/6/2023243，34，23，12，2rearfront

4，23，12，2rearfront

3，44，33，12，2front

3，44，3rear5，24，12，2front

3，44，3rear5，24，12，1front

3，44，3rear5，24，12，11，2電路布線過程-隊(duì)列狀態(tài)2/6/202325front

4，3rear5，24，12，11，2front

rear5，24，12，11，25，3front

rear4，12，11，25，3front

rear2，11，25，3front

rear1，25，31，1電路布線過程-隊(duì)列狀態(tài)2/6/202326front

rear5，31，1front

rear1，15，4front

rear5，4front

rear6，4front

rear6，57，4電路布線過程-隊(duì)列狀態(tài)2/6/202327front

rear7，46，67，5front

rear6，67，5front

rear7，56，77，65，6front

rear6，77，65，6front

rear7，65，67，75，7電路布線過程-隊(duì)列狀態(tài)2/6/202328front

rear5，67，75，7front

rear7，75，7(nbr.row==finish.row)&&(nbr.col==finish.col)尋找電路布線最短路徑2/6/2023291、從b開始，首先移動(dòng)到一個(gè)比b的編號(hào)小的相鄰位置上?？蓮腷移動(dòng)到(5,6）2、從當(dāng)前位置開始，繼續(xù)移動(dòng)到比當(dāng)前標(biāo)號(hào)小1的相鄰位置上，重復(fù)這個(gè)過程，直至到達(dá)a為止。(5,6)，(6,6)，(6,4)，(5,4)，…（3,2）。2/6/202330//構(gòu)造路徑PathLen=grid[finish.row][finish.col]-2;path=newPosition[PathLen];here=finish;//回溯至finishfor(intj=PathLen-1;j>=0;j--){ path[j]=here; //尋找前一個(gè)位置

for(inti=0;i<NumOfNbrs;i++){ nbr.row=here.row+offset[i].row; nbr.col=here.col+offset[i].col; if(grid[nbr.row][nbr.col]==j+2)break; }

here=nbr;//移動(dòng)到前一個(gè)位置

}returntrue;}尋找電路布線最短路徑電路布線復(fù)雜度分析網(wǎng)格編號(hào)過程需耗時(shí)O(m2)重構(gòu)路徑的過程需耗時(shí)Q（PathLen）2/6/2023312/6/202332數(shù)字化圖像是一個(gè)m×m的像素矩陣。單色圖像中，每個(gè)像素的值要么為0，要么為1。值為0的像素表示圖像的背景，而值為1的像素則表示圖元上的一個(gè)點(diǎn)，我們稱其為圖元像素。如果一個(gè)像素在另一個(gè)像素的左側(cè)、上部、右側(cè)或下部，則稱這兩個(gè)像素為相鄰像素。識(shí)別圖元就是對(duì)圖元像素進(jìn)行標(biāo)記，當(dāng)且僅當(dāng)兩個(gè)像素屬于同一圖元時(shí)，它們的標(biāo)號(hào)相同。6.4.3識(shí)別圖元識(shí)別圖元2/6/2023332/6/202334一間工廠由m臺(tái)機(jī)器組成。工廠中所執(zhí)行的每項(xiàng)任務(wù)都由若干道工序構(gòu)成，一臺(tái)機(jī)器用來(lái)完成一道工序，不同的機(jī)器完成不同的工序。一旦一臺(tái)機(jī)器開始處理一道工序，它會(huì)連續(xù)不斷地進(jìn)行處理，直到該工序被完成為止。6.4.4工廠仿真2/6/202335對(duì)于一項(xiàng)任務(wù)中的每道工序來(lái)說，都有兩個(gè)屬性：一是工時(shí)（即完成該道工序需要多長(zhǎng)時(shí)間），一是執(zhí)行該工序的機(jī)器。一項(xiàng)任務(wù)中的各道工序必須按照一定的次序來(lái)執(zhí)行。一項(xiàng)任務(wù)的執(zhí)行是從處理第一道工序的機(jī)器開始的，當(dāng)?shù)谝坏拦ば蛲瓿珊?，任?wù)轉(zhuǎn)至處理第二道工序的機(jī)器，依此進(jìn)行下去，直到最后一道工序完成為止。當(dāng)一項(xiàng)任務(wù)到達(dá)一臺(tái)機(jī)器時(shí)，若機(jī)器正忙，則該任務(wù)將不得不等待。工序?qū)傩?/6/202336在工廠中每臺(tái)機(jī)器都可以有如下三種狀態(tài)：活動(dòng)、空閑和轉(zhuǎn)換。在活動(dòng)狀態(tài)，機(jī)器正在處理一道工序。在空閑狀態(tài)機(jī)器無(wú)事可做。在轉(zhuǎn)換狀態(tài)，機(jī)器剛剛完成一道工序，并在為一項(xiàng)新任務(wù)的執(zhí)行做準(zhǔn)備，比如機(jī)器操作員可能需要清理機(jī)器并稍作休息等。每臺(tái)機(jī)器在轉(zhuǎn)換狀態(tài)期間所花費(fèi)的時(shí)間可能各不相同。機(jī)器狀態(tài)2/6/202337當(dāng)一臺(tái)機(jī)器可以處理一項(xiàng)新任務(wù)時(shí)，它可能需要從各個(gè)等待者中挑選一項(xiàng)任務(wù)來(lái)執(zhí)行。在這里，每臺(tái)機(jī)器都按照FIFO的方式來(lái)處理等待者，因此每臺(tái)機(jī)器旁的等待者構(gòu)成了一個(gè)FIFO隊(duì)列。在其他類型的工廠中，可以為每項(xiàng)任務(wù)指定不同的優(yōu)先權(quán)，當(dāng)機(jī)器變成空閑時(shí)，從等待者中首先選擇具有最高優(yōu)先權(quán)的任務(wù)來(lái)執(zhí)行。任務(wù)隊(duì)列2/6/202338為了讓顧客滿意，希望盡量減少任務(wù)在機(jī)器隊(duì)列中的等待時(shí)間。如果能夠知道每項(xiàng)