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

1、1第 6 章隊(duì)列隊(duì)列(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隊(duì)列的實(shí)現(xiàn)隊(duì)列的應(yīng)用本章重點(diǎn)46.4 應(yīng)用6.4.1 6.4.1 火車車廂重排火車車廂重排6.4.2 電路布線6.4.3 圖元識(shí)別6.4.4 工廠仿真56.4.1 火車車廂重排緩沖鐵軌位于入軌和出軌之間 入軌右端-緩沖鐵軌入軌右端-出軌緩沖鐵軌右端-出軌 禁止禁止 :將車廂從緩沖鐵軌移動(dòng)至入軌從出軌移動(dòng)車廂至緩沖鐵軌1.鐵軌Hk 為可直接將車廂從入軌移動(dòng)到出軌的通道6車廂移動(dòng)到緩沖

2、鐵軌的原則車廂c應(yīng)移動(dòng)到這樣的緩沖鐵軌中：該緩沖鐵軌中現(xiàn)有各車廂的編號均小于c；如果有多個(gè)緩沖鐵軌都滿足這一條件，則選擇一個(gè)左端車廂編號最大的緩沖鐵軌；否則選擇一個(gè)空的緩沖鐵軌（如果有的話）。3/23/20227n從前至后依次檢查入軌上的所有車廂。n如果正在檢查的車廂就是下一個(gè)滿足排列要求的車廂，可以直接把它放到出軌上去。n如果不是，則把它移動(dòng)到緩沖鐵軌上，直到按輸出次序要求輪到它時(shí)才將它放到出軌上。n重排演示?；疖囓噹嘏欧桨?火車車廂重排思路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送入某個(gè)緩沖鐵軌 l讀程序 6-7 6-83/23/20229bool Railroad(int p, int n, int k)/ k 個(gè)緩沖鐵軌，車廂初始排序?yàn)閜 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)的緩沖鐵軌火車車廂重排程序-隊(duì)列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 送入某個(gè)緩沖鐵軌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) / /從緩沖鐵軌移動(dòng)到出軌，并修改minH 和minQ .int c; / 車廂編號/ 從隊(duì)列minQ 中刪除編號最小的車廂minHHminQ.Delete(c) ;cout Move car minH from h

6、olding track minQ to output endl;/ 通過檢查所有隊(duì)列的首部，尋找新的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 移動(dòng)到緩沖鐵軌中/ 如果沒有可用的緩沖鐵軌，則返回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移動(dòng)到最優(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例如，在解決電路布線問題時(shí)，一種很常用的方法就是在布線區(qū)域疊上一個(gè)網(wǎng)格，該網(wǎng)格把布線區(qū)域劃分成nm個(gè)方格，就像迷宮一樣。n從一個(gè)方格a的中心點(diǎn)連接到另一個(gè)方格b的中心點(diǎn)時(shí)，轉(zhuǎn)彎處必須采用直角。如果已經(jīng)

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

10、因?yàn)槿我粋€(gè)方格上的標(biāo)號與它相鄰方格上的標(biāo)號都至少相差1。n接下來，從當(dāng)前位置開始，繼續(xù)移動(dòng)到比當(dāng)前標(biāo)號小1的相鄰位置上。n重復(fù)這個(gè)過程，直至到達(dá)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; / 一個(gè)網(wǎng)格位置的相鄰位置數(shù)Position here, nbr;here.row = start.row;here.col = start.col;gridstart.rowstart.col = 2; / 封鎖尋找電路布線最短路徑3/23/202222/ 標(biāo)記可到達(dá)的網(wǎng)格位置LinkedQueue Q;do / 標(biāo)記相鄰位置for (int i = 0; i = 0; j-) pathj = here;/ 尋找前一個(gè)位置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; / 移動(dòng)到前一個(gè)位置 return true; 尋找電路布線最短路徑電路布線復(fù)雜度分析網(wǎng)格編號過程需耗時(shí) O (m2 )重構(gòu)路徑的過程需耗時(shí) Q（PathLen）3/23/2022313/23/202232n數(shù)字化圖像是一個(gè)mm 的像素矩陣。n單色圖像中，每個(gè)像素的值要么為 0，要么為1。n值為0的像素表示圖像的背景，而值為1的像素則表示圖元上的一個(gè)點(diǎn)，我們稱其

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

15、中的各道工序必須按照一定的次序來執(zhí)行。一項(xiàng)任務(wù)的執(zhí)行是從處理第一道工序的機(jī)器開始的，當(dāng)?shù)谝坏拦ば蛲瓿珊螅蝿?wù)轉(zhuǎn)至處理第二道工序的機(jī)器，依此進(jìn)行下去，直到最后一道工序完成為止。n當(dāng)一項(xiàng)任務(wù)到達(dá)一臺(tái)機(jī)器時(shí)，若機(jī)器正忙，則該任務(wù)將不得不等待。工序?qū)傩?/23/202236n在工廠中每臺(tái)機(jī)器都可以有如下三種狀態(tài)：活動(dòng)、空閑和轉(zhuǎn)換。n在活動(dòng)狀態(tài)，機(jī)器正在處理一道工序。n在空閑狀態(tài)機(jī)器無事可做。n在轉(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)3/23/202237n當(dāng)一臺(tái)機(jī)器可以處理一項(xiàng)新

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

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