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

1、1第 6 章隊列隊列(QUEUES)(QUEUES)2本章內(nèi)容6.1 6.1 抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型 6.2 6.2 公式化描述公式化描述6.3 6.3 鏈表描述鏈表描述6.4 6.4 應(yīng)用應(yīng)用3/23/20223隊列的實現(xiàn)隊列的應(yīng)用本章重點46.4 應(yīng)用6.4.1 6.4.1 火車車廂重排火車車廂重排6.4.2 電路布線6.4.3 圖元識別6.4.4 工廠仿真56.4.1 火車車廂重排緩沖鐵軌位于入軌和出軌之間 入軌右端-緩沖鐵軌入軌右端-出軌緩沖鐵軌右端-出軌 禁止禁止 :將車廂從緩沖鐵軌移動至入軌從出軌移動車廂至緩沖鐵軌1.鐵軌Hk 為可直接將車廂從入軌移動到出軌的通道6車廂移動到緩沖

2、鐵軌的原則車廂c應(yīng)移動到這樣的緩沖鐵軌中：該緩沖鐵軌中現(xiàn)有各車廂的編號均小于c；如果有多個緩沖鐵軌都滿足這一條件，則選擇一個左端車廂編號最大的緩沖鐵軌；否則選擇一個空的緩沖鐵軌（如果有的話）。3/23/20227n從前至后依次檢查入軌上的所有車廂。n如果正在檢查的車廂就是下一個滿足排列要求的車廂，可以直接把它放到出軌上去。n如果不是，則把它移動到緩沖鐵軌上，直到按輸出次序要求輪到它時才將它放到出軌上。n重排演示。火車車廂重排方案8火車車廂重排思路int NowOut=1； / NowOut:下一次要輸出的車廂號for （int i=1;i=n;i+）/從前至后依次檢查的所有車廂 1. 車廂 p

3、i 從入軌上移出 2. If (pi = NowOut)/ NowOut:下一次要輸出的車廂號 使用緩沖鐵軌Hk把pi放到出軌上去; NowOut+; while (minH(當(dāng)前緩沖鐵軌中編號最小的車廂)= NowOut ） 把minH放到出軌上去; 更新 minH,minQ（minH所在的緩沖鐵軌）; NowOut+; else 按照分配規(guī)則將車廂pi送入某個緩沖鐵軌 l讀程序 6-7 6-83/23/20229bool Railroad(int p, int n, int k)/ k 個緩沖鐵軌，車廂初始排序為p 1 : n / 如果重排成功，返回true，否則返回false/ 如果內(nèi)存

4、不足，則引發(fā)異常NoMem 。/創(chuàng)建與緩沖鐵軌對應(yīng)的堆棧LinkedQueue *H;H = new LinkedQueue k;k-;int NowOut = 1; /下一次要輸出的車廂int minH = n+l; /緩沖鐵軌中編號最小的車廂int minQ; /minH號車廂對應(yīng)的緩沖鐵軌火車車廂重排程序-隊列3/23/202210/車廂重排for(int i = 1; i = n; i+)if (pi = NowOut) / 直接輸出tcout“將車廂”pi“從入軌移至出軌endl;NowOut+ ;/從緩沖鐵軌中輸出while (minH = NowOut) Output(minH,

5、 minQ, H, k, n);NowOut+ ;else / 將pi 送入某個緩沖鐵軌if (!Hold(pi, minH, minQ, H, k)return false; return true; 火車車廂重排程序3/23/202211void Output(int& minH, int& minQ, LinkedQueue H, int k, int n) / /從緩沖鐵軌移動到出軌，并修改minH 和minQ .int c; / 車廂編號/ 從隊列minQ 中刪除編號最小的車廂minHHminQ.Delete(c) ;cout Move car minH from h

6、olding track minQ to output endl;/ 通過檢查所有隊列的首部，尋找新的minH和minQminH = n + 2;for (int i = 1; i = k; i+)if (!Hi.IsEmpty() & c = Hi.First() minH) minH = c;minQ = i;Output 函數(shù)3/23/202212bool Hold(int c, int& minH, int &minQ, LinkedQueue H, int k)/把車廂c 移動到緩沖鐵軌中/ 如果沒有可用的緩沖鐵軌，則返回false，否則返回true/ 為車廂

7、c 尋找最優(yōu)的緩沖鐵軌/ 初始化int BestTrack = 0, / 目前最優(yōu)的鐵軌 BestLast = 0, / BestTrack 中最后一節(jié)車廂 x; / 車廂編號Hold函數(shù)3/23/202213/ 掃描緩沖鐵軌for (int i = 1; i x & x BestLast) / 鐵軌i 尾部的車廂編號較大BestLast = x;BestTrack = i;else / 鐵軌i 為空if (!BestTrack) BestTrack = i;Hold函數(shù)3/23/202214if (!BestTrack) return false; /沒有可用的鐵軌/ 把c移動到最優(yōu)

8、鐵軌HBestTrack.Add(c) ;cout Move car c from input to holding track BestTrack endl;/ 如果有必要，則修改minH和minQif (c minH) minH = c; minQ = BestTrack ; return true;復(fù)雜性？Hold函數(shù)3/23/202215n在迷宮中尋找最短路徑的問題也存在于其他許多領(lǐng)域。n例如，在解決電路布線問題時，一種很常用的方法就是在布線區(qū)域疊上一個網(wǎng)格，該網(wǎng)格把布線區(qū)域劃分成nm個方格，就像迷宮一樣。n從一個方格a的中心點連接到另一個方格b的中心點時，轉(zhuǎn)彎處必須采用直角。如果已經(jīng)

9、有某條線路經(jīng)過一個方格，則封鎖該方格。我們希望使用a和b之間的最短路徑來作為布線的路徑，以便減少信號的延遲。6.4.2迷宮最短路徑問題擴展3/23/202216電路布線3/23/202217n為了找到網(wǎng)格中位置a和b之間的最短路徑，先從位置a 開始搜索，n把a 可到達的相鄰方格都標(biāo)記為1(表示與a 相距為1)n然后把標(biāo)號為1的方格可到達的相鄰方格都標(biāo)記為2(表示與a相距為2)n繼續(xù)進行下去n直到到達b或者找不到可到達的相鄰方格為止。方案3/23/202218方案演示3/23/202219n為了得到a與b之間的最短路徑，從b開始n首先移動到一個比b 的編號小的相鄰位置上。一定存在這樣的相鄰位置，

10、因為任一個方格上的標(biāo)號與它相鄰方格上的標(biāo)號都至少相差1。n接下來，從當(dāng)前位置開始，繼續(xù)移動到比當(dāng)前標(biāo)號小1的相鄰位置上。n重復(fù)這個過程，直至到達a為止。輸出方案3/23/202220bool FindPath(Position start, Position finish, int& PathLen, Position * &path) / /尋找從start到finish的路徑/ 如果成功，則返回true，否則返回false/ 如果空間不足，則引發(fā)異常NoMemif(start.row=finish.row)&(start.col = finish.col)PathL

11、en = 0; return true; / start = finish/ 初始化包圍網(wǎng)格的“圍墻”for (int i = 0; i = m+1; i+) grid0i = gridm+1i = 1; / 底和頂gridi0 = gridim+1 = 1; / 左和右尋找電路布線最短路徑3/23/202221/ 初始化offsetPosition offset 4 ;offset0.row = 0; offset0.col = 1; / 右offset1.row = 1; offset1.col = 0; / 下offset2.row = 0; offset2.col = -1; / 左o

12、ffset3.row = -1; offset3.col = 0; / 上int NumOfNbrs = 4; / 一個網(wǎng)格位置的相鄰位置數(shù)Position here, nbr;here.row = start.row;here.col = start.col;gridstart.rowstart.col = 2; / 封鎖尋找電路布線最短路徑3/23/202222/ 標(biāo)記可到達的網(wǎng)格位置LinkedQueue Q;do / 標(biāo)記相鄰位置for (int i = 0; i = 0; j-) pathj = here;/ 尋找前一個位置for (int i = 0; i NumOfNbrs; i

13、+) nbr.row = here.row + offseti.row;nbr.col = here.col + offseti.col;if (gridnbr.row nbr.col = j+2) break;here = nbr; / 移動到前一個位置 return true; 尋找電路布線最短路徑電路布線復(fù)雜度分析網(wǎng)格編號過程需耗時 O (m2 )重構(gòu)路徑的過程需耗時 Q（PathLen）3/23/2022313/23/202232n數(shù)字化圖像是一個mm 的像素矩陣。n單色圖像中，每個像素的值要么為 0，要么為1。n值為0的像素表示圖像的背景，而值為1的像素則表示圖元上的一個點，我們稱其

14、為圖元像素。n如果一個像素在另一個像素的左側(cè)、上部、右側(cè)或下部，則稱這兩個像素為相鄰像素。n識別圖元就是對圖元像素進行標(biāo)記，當(dāng)且僅當(dāng)兩個像素屬于同一圖元時，它們的標(biāo)號相同。6.4.3識別圖元識別圖元3/23/2022333/23/202234n一間工廠由m臺機器組成。n工廠中所執(zhí)行的每項任務(wù)都由若干道工序構(gòu)成，一臺機器用來完成一道工序，不同的機器完成不同的工序。n一旦一臺機器開始處理一道工序，它會連續(xù)不斷地進行處理，直到該工序被完成為止。6.4.4工廠仿真3/23/202235n對于一項任務(wù)中的每道工序來說，都有兩個屬性：一是工時（即完成該道工序需要多長時間），一是執(zhí)行該工序的機器。n一項任務(wù)

15、中的各道工序必須按照一定的次序來執(zhí)行。一項任務(wù)的執(zhí)行是從處理第一道工序的機器開始的，當(dāng)?shù)谝坏拦ば蛲瓿珊?，任?wù)轉(zhuǎn)至處理第二道工序的機器，依此進行下去，直到最后一道工序完成為止。n當(dāng)一項任務(wù)到達一臺機器時，若機器正忙，則該任務(wù)將不得不等待。工序?qū)傩?/23/202236n在工廠中每臺機器都可以有如下三種狀態(tài)：活動、空閑和轉(zhuǎn)換。n在活動狀態(tài)，機器正在處理一道工序。n在空閑狀態(tài)機器無事可做。n在轉(zhuǎn)換狀態(tài)，機器剛剛完成一道工序，并在為一項新任務(wù)的執(zhí)行做準(zhǔn)備，比如機器操作員可能需要清理機器并稍作休息等。每臺機器在轉(zhuǎn)換狀態(tài)期間所花費的時間可能各不相同。機器狀態(tài)3/23/202237n當(dāng)一臺機器可以處理一項新

16、任務(wù)時，它可能需要從各個等待者中挑選一項任務(wù)來執(zhí)行。n在這里，每臺機器都按照FIFO的方式來處理等待者，因此每臺機器旁的等待者構(gòu)成了一個FIFO隊列。n在其他類型的工廠中，可以為每項任務(wù)指定不同的優(yōu)先權(quán)，當(dāng)機器變成空閑時，從等待者中首先選擇具有最高優(yōu)先權(quán)的任務(wù)來執(zhí)行。任務(wù)隊列3/23/202238n為了讓顧客滿意，希望盡量減少任務(wù)在機器隊列中的等待時間。n如果能夠知道每項任務(wù)所花費的等待時間是多少n并且知道哪些機器所導(dǎo)致的等待時間最多n就可以據(jù)此來改進和提高工廠的效能。目標(biāo)3/23/202239n在對工廠進行仿真時，采用一個模擬時鐘來進行仿真計時，每當(dāng)一道工序完成或一項新任務(wù)到達工廠時，模擬時

17、鐘就推進一個單位。在完成老任務(wù)時，將產(chǎn)生新的任務(wù)。每當(dāng)一道工序完成或一項新任務(wù)到達工廠時，稱發(fā)生了一個事件(event)。n另外，還存在一個啟動事件(start event)，用來啟動仿真過程。工廠仿真實現(xiàn)3/23/202240n三臺機器M1、M2和M3的轉(zhuǎn)換狀態(tài)所花費的時間分別為2、0和1。n因此，當(dāng)一道工序完成時n機器M1在啟動下一道工序之前必須等待2個時間單元n機器M2可以立即啟動下一道工序n機器M3必須等待1個時間單元示例3/23/202241n每道工序用形如(machine，time)的值對來描述。n各項任務(wù)的長度分別為7，6，8和4。四項任務(wù)的特征3/23/202242仿真3/23/202243n2號和4號任務(wù)在第12時刻完成，1號任