第03章_棧和隊(duì)列B

1、3.2 隊(duì)列（隊(duì)列（Queue） 第三章第三章 棧和隊(duì)列棧和隊(duì)列1. 基本概念基本概念2. 邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)3. 存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)4. 運(yùn)算規(guī)則運(yùn)算規(guī)則5. 實(shí)現(xiàn)方式實(shí)現(xiàn)方式1第三章：棧和隊(duì)列隊(duì)列隊(duì)列 （Queue）是僅在表尾表尾進(jìn)行插入插入操作，在表頭表頭進(jìn)行刪除刪除操作的線性表。它是一種先進(jìn)先出（）的線性表。在在隊(duì)尾插入隊(duì)尾插入元素稱為元素稱為問(wèn)：為什么要設(shè)計(jì)隊(duì)列？它有什么用途？問(wèn)：為什么要設(shè)計(jì)隊(duì)列？它有什么用途？離散事件的模擬離散事件的模擬（模擬事件發(fā)生的先后順序 ）操作系統(tǒng)中的作業(yè)調(diào)度操作系統(tǒng)中的作業(yè)調(diào)度（一個(gè)CPU執(zhí)行多個(gè)作業(yè)） 簡(jiǎn)化程序設(shè)計(jì)。簡(jiǎn)化程序設(shè)計(jì)。23.2 隊(duì)列隊(duì)首隊(duì)首隊(duì)尾

2、隊(duì)尾a1 , a2 , a3 , .,an-1 , an 。在在隊(duì)首刪除隊(duì)首刪除元素稱為元素稱為與線性表相同，仍為一對(duì)一關(guān)系。與線性表相同，仍為一對(duì)一關(guān)系。順序隊(duì)順序隊(duì)或或鏈隊(duì)鏈隊(duì)，以，以循環(huán)順序隊(duì)循環(huán)順序隊(duì)更常見(jiàn)。更常見(jiàn)。只能在隊(duì)首和隊(duì)尾運(yùn)算，且訪問(wèn)結(jié)點(diǎn)時(shí)依照只能在隊(duì)首和隊(duì)尾運(yùn)算，且訪問(wèn)結(jié)點(diǎn)時(shí)依照先進(jìn)先出（先進(jìn)先出（FIFOFIFO）的原則。的原則。關(guān)鍵是掌握關(guān)鍵是掌握入隊(duì)入隊(duì)和和出隊(duì)出隊(duì)操作，具體實(shí)現(xiàn)依順操作，具體實(shí)現(xiàn)依順序隊(duì)或鏈隊(duì)的不同而不同。序隊(duì)或鏈隊(duì)的不同而不同。只能在表的一端進(jìn)行插入運(yùn)算，在表的另一只能在表的一端進(jìn)行插入運(yùn)算，在表的另一端進(jìn)行刪除運(yùn)算的線性表。端進(jìn)行刪除運(yùn)算的線性表

3、。 入隊(duì)或出隊(duì)，建空隊(duì)列，判隊(duì)空或隊(duì)滿等操作。入隊(duì)或出隊(duì)，建空隊(duì)列，判隊(duì)空或隊(duì)滿等操作。隊(duì)尾插入，隊(duì)尾插入，隊(duì)頭刪除隊(duì)頭刪除33.2 隊(duì)列操作結(jié)果：操作結(jié)果： 初始條件：初始條件： 操作結(jié)果：操作結(jié)果：初始條件：初始條件：操作結(jié)果：操作結(jié)果：初始條件：初始條件：操作結(jié)果：操作結(jié)果：初始條件：初始條件：操作結(jié)果：操作結(jié)果：( (教材教材p.59-60)p.59-60)：初始條件：初始條件：操作結(jié)果：操作結(jié)果：初始條件：初始條件：操作結(jié)果：操作結(jié)果：初始條件：初始條件：操作結(jié)果：操作結(jié)果：frontfrontrearrearfrontfront鏈鏈隊(duì)列隊(duì)列類型定義：類型定義： typedef st

4、ruct QueuePtr front ; /隊(duì)首指針隊(duì)首指針 QueuePtr rear ; /隊(duì)尾指針隊(duì)尾指針 LinkQueue;結(jié)點(diǎn)結(jié)點(diǎn)類型定義：類型定義： typedef Struct QNode QElemType data; /元素元素 QNode *next; /指向下一結(jié)點(diǎn)的指針指向下一結(jié)點(diǎn)的指針 Qnode , * QueuePtr ;關(guān)于整個(gè)鏈隊(duì)的關(guān)于整個(gè)鏈隊(duì)的總體描述總體描述鏈隊(duì)中任一鏈隊(duì)中任一結(jié)點(diǎn)的結(jié)構(gòu)結(jié)點(diǎn)的結(jié)構(gòu)63.2 隊(duì)列鏈隊(duì)列鏈隊(duì)列用鏈表實(shí)現(xiàn)的隊(duì)列，需要兩個(gè)分別指向隊(duì)頭的指針用鏈表實(shí)現(xiàn)的隊(duì)列，需要兩個(gè)分別指向隊(duì)頭的指針（頭指針）和指向?qū)ξ驳闹羔槪ㄎ仓羔槪?。（頭指

5、針）和指向?qū)ξ驳闹羔槪ㄎ仓羔槪??？真滉?duì)的特征？空鏈隊(duì)的特征？Q(隊(duì)尾隊(duì)尾)(隊(duì)首隊(duì)首)fronta1a2a3rearp 怎樣實(shí)現(xiàn)鏈隊(duì)的怎樣實(shí)現(xiàn)鏈隊(duì)的入隊(duì)和出隊(duì)操入隊(duì)和出隊(duì)操作？作？ 鏈隊(duì)會(huì)滿嗎？鏈隊(duì)會(huì)滿嗎？frontrearfront=rear一般不會(huì)，因?yàn)閯h除時(shí)有一般不會(huì)，因?yàn)閯h除時(shí)有free動(dòng)作。除非內(nèi)存不足！動(dòng)作。除非內(nèi)存不足！出隊(duì)（頭部刪除）：出隊(duì)（頭部刪除）：p=front-next; front-next=p-next; free(p);SD鏈隊(duì)示意圖：鏈隊(duì)示意圖：73.2 隊(duì)列入隊(duì)（尾部插入）：入隊(duì)（尾部插入）：rearnext=S; rear=S;鏈隊(duì)入隊(duì)出隊(duì)示意圖：鏈隊(duì)入隊(duì)出

6、隊(duì)示意圖：Status EnQueue ( LinkQueue &Q, QElemType e ) / 插入元素e為Q的新的隊(duì)尾元素 p = (QueuePtr) malloc (sizeof (Qnode); if (!p) exit(ERROR); /存儲(chǔ)分配失敗 p-data = e; p-next = NULL; return OK;鏈隊(duì)鏈隊(duì)入隊(duì)入隊(duì)的實(shí)現(xiàn)的實(shí)現(xiàn) （教材p62）：Status DeQueue ( LinkQueue &Q, QElemType &e ) /若隊(duì)列不空，則刪除Q的隊(duì)頭元素，用 e 返回其值， / 并返回TRUE；否則返回ERROR

7、if (Q.front = Q.rear) return ERROR; e = p-data; free (p); return OK;鏈隊(duì)鏈隊(duì)出隊(duì)出隊(duì)的實(shí)現(xiàn)的實(shí)現(xiàn) （教材p62）：采用動(dòng)態(tài)分配空間的形式采用動(dòng)態(tài)分配空間的形式順序隊(duì)類型定義順序隊(duì)類型定義 (教材p64):建隊(duì)建隊(duì)核心語(yǔ)句核心語(yǔ)句：q . base=(QElemType *) malloc(sizeof (QElemType)* MAXQSIZE); /分配空間分配空間關(guān)于整個(gè)順序關(guān)于整個(gè)順序隊(duì)的總體描述隊(duì)的總體描述#define MAXQSIZE 100 /最大隊(duì)列長(zhǎng)度typedef struct QElemType *bas

8、e; /隊(duì)列的基址 int front; /隊(duì)首指針,若隊(duì)列不為空， / 指向隊(duì)列頭元素 int rear; /隊(duì)尾指針,若隊(duì)列不為空， / 指向隊(duì)列尾元素的下一個(gè)位置SqQueue113.2 隊(duì)列Q(隊(duì)尾隊(duì)尾)(隊(duì)首隊(duì)首)front a1 a2 a3data a40.99rear 隊(duì)列會(huì)滿嗎？隊(duì)列會(huì)滿嗎？極易裝滿！極易裝滿！因?yàn)閿?shù)組通因?yàn)閿?shù)組通常有長(zhǎng)度限制，而其前常有長(zhǎng)度限制，而其前端空間無(wú)法釋放。端空間無(wú)法釋放。 空隊(duì)列的特征？空隊(duì)列的特征？ 約定：約定：front=rear隊(duì)尾后地址隊(duì)尾后地址入隊(duì)入隊(duì)(尾部插入尾部插入)： Qrear=e; rear+ ; 出隊(duì)出隊(duì)(頭部刪除頭部刪除)：

9、 e=Qfront; front+; 討論：討論：有有缺缺陷陷 怎樣實(shí)現(xiàn)入隊(duì)和出隊(duì)怎樣實(shí)現(xiàn)入隊(duì)和出隊(duì)操作？操作？核心語(yǔ)句如下核心語(yǔ)句如下：用用base做數(shù)組名做數(shù)組名e順序隊(duì)示意圖：順序隊(duì)示意圖：123.2 隊(duì)列基本操作的實(shí)現(xiàn)初始化空隊(duì)：初始化空隊(duì)： 入隊(duì)：入隊(duì)：出隊(duì)：出隊(duì)：隊(duì)空條件：隊(duì)空條件：隊(duì)滿條件：隊(duì)滿條件：?jiǎn)栴}：假上溢！順序隊(duì)操作示意圖：順序隊(duì)操作示意圖：順序隊(duì)操作示意圖：順序隊(duì)操作示意圖：解決假溢出的途徑解決假溢出的途徑采用循環(huán)隊(duì)列采用循環(huán)隊(duì)列答：答：在順序隊(duì)中，當(dāng)尾指針已經(jīng)到了數(shù)組的在順序隊(duì)中，當(dāng)尾指針已經(jīng)到了數(shù)組的上界，不能再有入隊(duì)操作，但其實(shí)數(shù)組中還上界，不能再有入隊(duì)操作，但其

10、實(shí)數(shù)組中還有空位置，這就叫有空位置，這就叫“假溢出假溢出”。問(wèn)：什么叫問(wèn)：什么叫“假溢出假溢出” ？如何解決？如何解決？153.2 隊(duì)列當(dāng)當(dāng)J6 J6 入隊(duì)后入隊(duì)后, , 隊(duì)尾指針隊(duì)尾指針Q.rearQ.rear越界越界, ,不可能不可能再插入新的隊(duì)尾元素再插入新的隊(duì)尾元素, ,但是另一方面但是另一方面, ,隊(duì)列的隊(duì)列的實(shí)際可用空間并未占滿。一個(gè)巧妙的辦法是實(shí)際可用空間并未占滿。一個(gè)巧妙的辦法是, ,將順序隊(duì)列設(shè)想為首尾相連的環(huán)狀空間將順序隊(duì)列設(shè)想為首尾相連的環(huán)狀空間, ,當(dāng)當(dāng)Q.rear Q.rear 值超出隊(duì)列空間的最大位置時(shí)值超出隊(duì)列空間的最大位置時(shí), ,令令Q.rear= 0,Q.re

11、ar= 0,使隊(duì)列空間能使隊(duì)列空間能“循環(huán)循環(huán)”使用。這使用。這種循環(huán)使用空間的隊(duì)列稱為循環(huán)隊(duì)列。種循環(huán)使用空間的隊(duì)列稱為循環(huán)隊(duì)列。循環(huán)隊(duì)列示意圖：循環(huán)隊(duì)列示意圖：存在問(wèn)題: 解決方案: 循環(huán)隊(duì)列基本思想：把隊(duì)列設(shè)想成環(huán)形，讓sq0接在sqM-1之后, 若rear+1=M,則令rear=0;循環(huán)隊(duì)列示意圖：循環(huán)隊(duì)列示意圖：假上溢的解決辦法基本操作的實(shí)現(xiàn)l入隊(duì)：l出隊(duì)：l隊(duì)空條件： l隊(duì)滿條件：?jiǎn)栴}：隊(duì)空和隊(duì)滿的判斷條件一樣 循環(huán)隊(duì)列示意圖：循環(huán)隊(duì)列示意圖：a3a2a10123N-1rearfront新問(wèn)題：新問(wèn)題：在循環(huán)隊(duì)列中，空隊(duì)特征是在循環(huán)隊(duì)列中，空隊(duì)特征是front=rear；隊(duì)滿時(shí)也會(huì)

12、有隊(duì)滿時(shí)也會(huì)有front=rear；判決條件將出現(xiàn)二義性！判決條件將出現(xiàn)二義性！解決方案有三：解決方案有三：使用一個(gè)使用一個(gè)計(jì)數(shù)器計(jì)數(shù)器記錄隊(duì)列中元素個(gè)數(shù)（即隊(duì)列長(zhǎng)度）；記錄隊(duì)列中元素個(gè)數(shù)（即隊(duì)列長(zhǎng)度）；加加設(shè)標(biāo)志位設(shè)標(biāo)志位，刪除時(shí)置刪除時(shí)置1,1,插入時(shí)置插入時(shí)置0,0,則可識(shí)別當(dāng)前則可識(shí)別當(dāng)前front=rear屬于何種情況屬于何種情況 人為人為浪費(fèi)一個(gè)單元浪費(fèi)一個(gè)單元，則隊(duì)滿特征可改為，則隊(duì)滿特征可改為front=(rear+1)%N；a3a2a1frontrear 0 1 2 3 . .N-1193.2 隊(duì)列隊(duì)空條件隊(duì)空條件 : front = rear (初始化時(shí)：初始化時(shí)：fron

13、t = rear )隊(duì)滿條件隊(duì)滿條件： front = (rear) % N (N=maxsize)隊(duì)列長(zhǎng)度隊(duì)列長(zhǎng)度（即數(shù)據(jù)元素個(gè)數(shù)）（即數(shù)據(jù)元素個(gè)數(shù)）：L=（Nrearfront）% N J2 J3J1 J4 J5frontrear 實(shí)際中常選用實(shí)際中常選用方案方案3（人為人為浪費(fèi)一個(gè)單元浪費(fèi)一個(gè)單元）：即即front和和rear二者之一指向?qū)嵲?，另一個(gè)指向空閑元素。二者之一指向?qū)嵲兀硪粋€(gè)指向空閑元素。 問(wèn)問(wèn)3： 在具有在具有n個(gè)單元的循個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有多少環(huán)隊(duì)列中，隊(duì)滿時(shí)共有多少個(gè)元素？個(gè)元素？ N-1個(gè)個(gè)6 問(wèn)問(wèn)1：左圖中隊(duì)列左圖中隊(duì)列maxsize N=？問(wèn)問(wèn)2：左

14、圖中左圖中隊(duì)列長(zhǎng)度隊(duì)列長(zhǎng)度L=？5203.2 隊(duì)列n 隊(duì)列存放數(shù)組被當(dāng)作首尾相接的表處理。隊(duì)列存放數(shù)組被當(dāng)作首尾相接的表處理。 n 隊(duì)頭、隊(duì)尾指針隊(duì)頭、隊(duì)尾指針加加1時(shí)從時(shí)從maxSize -1直接進(jìn)到直接進(jìn)到0，可用語(yǔ)言的取，可用語(yǔ)言的取模模(余數(shù)余數(shù))運(yùn)算實(shí)現(xiàn)。運(yùn)算實(shí)現(xiàn)。 循環(huán)隊(duì)列：循環(huán)隊(duì)列：/ 插入元素e為Q的新的隊(duì)尾元素/隊(duì)列滿循環(huán)隊(duì)列循環(huán)隊(duì)列入隊(duì)入隊(duì)的實(shí)現(xiàn)的實(shí)現(xiàn) （教材p65）：/ 若隊(duì)列不空，則刪除Q的隊(duì)頭元素， / 用e返回其值，并返回TRUE; 否則返回FALSE循環(huán)隊(duì)列循環(huán)隊(duì)列出隊(duì)出隊(duì)的實(shí)現(xiàn)的實(shí)現(xiàn) （教材p65）：（）（） rf （）（）（nfr）% n （）（）nrf （）

15、（） （nrf）% n要分析要分析4 4種公式哪種最合理？種公式哪種最合理？當(dāng)當(dāng) r f 時(shí)（時(shí)（A）合理；）合理；當(dāng)當(dāng) r f 時(shí)（時(shí)（C）合理；）合理；答：答：綜合綜合2種情況，以（種情況，以（D）的表達(dá)最為合理的表達(dá)最為合理例例2：在一個(gè)循環(huán)隊(duì)列中，若約定隊(duì)首指針指向隊(duì)首元素在一個(gè)循環(huán)隊(duì)列中，若約定隊(duì)首指針指向隊(duì)首元素的的前一個(gè)前一個(gè)位置。那么，從循環(huán)隊(duì)列中刪除一個(gè)元素時(shí)，其位置。那么，從循環(huán)隊(duì)列中刪除一個(gè)元素時(shí)，其操作是操作是 先先 移動(dòng)隊(duì)首指針移動(dòng)隊(duì)首指針取出元素取出元素，后，后。例例1：數(shù)組數(shù)組n用來(lái)表示一個(gè)循環(huán)隊(duì)列，用來(lái)表示一個(gè)循環(huán)隊(duì)列，f 為當(dāng)前隊(duì)列頭元為當(dāng)前隊(duì)列頭元素的素的前

16、一前一位置，位置，r 為隊(duì)尾元素的位置。假定隊(duì)列中元素的個(gè)為隊(duì)尾元素的位置。假定隊(duì)列中元素的個(gè)數(shù)小于數(shù)小于n，計(jì)算隊(duì)列中元素的公式為，計(jì)算隊(duì)列中元素的公式為:243.2 隊(duì)列例例3： 一循環(huán)隊(duì)列如下圖所示，若先刪除一循環(huán)隊(duì)列如下圖所示，若先刪除4個(gè)元素，接著再個(gè)元素，接著再插入插入4個(gè)元素，請(qǐng)問(wèn)隊(duì)頭和隊(duì)尾指針?lè)謩e指向哪個(gè)位置個(gè)元素，請(qǐng)問(wèn)隊(duì)頭和隊(duì)尾指針?lè)謩e指向哪個(gè)位置? J2 J3J1 J4 J5front=2rear=1解：解：由圖可知，隊(duì)頭和隊(duì)尾指針的初態(tài)分別為由圖可知，隊(duì)頭和隊(duì)尾指針的初態(tài)分別為front=2和和rear=1。刪除刪除4個(gè)元素后個(gè)元素后， f= (2+4) %6=0再插入再

17、插入4個(gè)元素后，個(gè)元素后，r=(1+4)%6=5 front=0J6 J5J7J8 J9rear=5rear=1front=0253.2 隊(duì)列對(duì)這對(duì)這4 4個(gè)數(shù)據(jù)元素進(jìn)行的隊(duì)操作是個(gè)數(shù)據(jù)元素進(jìn)行的隊(duì)操作是進(jìn)隊(duì)進(jìn)隊(duì)2 2次，出隊(duì)次，出隊(duì)1 1次，再進(jìn)次，再進(jìn)隊(duì)隊(duì)2 2次，出隊(duì)次，出隊(duì)1 1次次；這時(shí)，第；這時(shí)，第1 1次出隊(duì)得到的元素是次出隊(duì)得到的元素是 ？ ，第第2 2次出隊(duì)得到的元素是次出隊(duì)得到的元素是 ？ 。經(jīng)操作后，最后在隊(duì)中的。經(jīng)操作后，最后在隊(duì)中的元素還有元素還有 ？ 個(gè)，隊(duì)尾指針指向個(gè)，隊(duì)尾指針指向 ？ 。 解：解：此題用此題用V4V4大小數(shù)組即可大小數(shù)組即可（V0V0V3 4V3

18、 4個(gè)單元有效）個(gè)單元有效） 。例例4 4：對(duì)對(duì)4 4個(gè)數(shù)據(jù)元素進(jìn)行隊(duì)操作。在進(jìn)隊(duì)操作時(shí)，按個(gè)數(shù)據(jù)元素進(jìn)行隊(duì)操作。在進(jìn)隊(duì)操作時(shí)，按a1a1、a2a2、a3a3、a4a4次序每次進(jìn)入一個(gè)元素（假設(shè)隊(duì)的初態(tài)為空）。次序每次進(jìn)入一個(gè)元素（假設(shè)隊(duì)的初態(tài)為空）。 進(jìn)隊(duì)進(jìn)隊(duì)2 2次次 出隊(duì)出隊(duì)1 1次次 再進(jìn)隊(duì)再進(jìn)隊(duì)2 2次次 出隊(duì)出隊(duì)1 1次次a1、a2 f=r=0 ; r+ ; r+ (f=0, r=2)a2、a3、a4 r+ ; r+ (f=1, r=4=0)a1 f+; (f=1, r=2) a2 f+ (f=2, r=0)答案：（a1） （a2) (2) (v0)263.2 隊(duì)列l(wèi)貨運(yùn)貨運(yùn)列車共

19、有列車共有n n節(jié)車廂，每節(jié)車廂節(jié)車廂，每節(jié)車廂將將停放在不同的車站：停放在不同的車站：假定假定m m個(gè)車站的編號(hào)分別為個(gè)車站的編號(hào)分別為1,2,3,1,2,3,m,m，貸運(yùn)列車按照第，貸運(yùn)列車按照第m m站至第站至第1 1站的次序經(jīng)過(guò)這些車站站的次序經(jīng)過(guò)這些車站。l車廂車廂到達(dá)某個(gè)目的地時(shí)，為了便于從列車上卸掉尾部的車到達(dá)某個(gè)目的地時(shí)，為了便于從列車上卸掉尾部的車廂，就是必須重新排列車廂，使各車廂排列為：靠近車頭廂，就是必須重新排列車廂，使各車廂排列為：靠近車頭的車廂是到達(dá)第的車廂是到達(dá)第1 1站（最后一站），而靠近車尾的車廂是站（最后一站），而靠近車尾的車廂是到達(dá)到達(dá)m m站（第一站）站（

20、第一站）。l如如在出發(fā)站時(shí)，準(zhǔn)備發(fā)出的車廂存儲(chǔ)在在出發(fā)站時(shí)，準(zhǔn)備發(fā)出的車廂存儲(chǔ)在r r數(shù)組中，數(shù)組中，riri的的值是車廂的編號(hào)，編號(hào)越小的，就是發(fā)往越遠(yuǎn)的車站，如值是車廂的編號(hào)，編號(hào)越小的，就是發(fā)往越遠(yuǎn)的車站，如，開(kāi)始，開(kāi)始r r中的次序是：中的次序是： 7 7，4 4，2 2，5 5，8 8，9 9，1 1，6 6，3 3。那。那么，在發(fā)出本站前，就要將車廂重新編排，按從么，在發(fā)出本站前，就要將車廂重新編排，按從1 1到到n n的次的次序與車頭相連接。序與車頭相連接。 當(dāng)所有的車廂按照這種次序排列時(shí)，當(dāng)所有的車廂按照這種次序排列時(shí)，在到達(dá)每個(gè)車站時(shí)，只需卸掉最后幾節(jié)車廂即可。在到達(dá)每個(gè)車站

21、時(shí)，只需卸掉最后幾節(jié)車廂即可。27 9,8,7 9,8,7 6,5,4 6,5,4 入軌入軌出軌出軌緩沖鐵軌緩沖鐵軌3,6,1,9,8,5,2,4,73,6,1,9,8,5,2,4,73,2,1 3,2,1 圖圖 車廂調(diào)度轉(zhuǎn)軌車廂調(diào)度轉(zhuǎn)軌 車廂重排問(wèn)題車廂重排問(wèn)題：28l為了重排車廂，需按車廂到達(dá)入軌的先后，從前至后依次檢為了重排車廂，需按車廂到達(dá)入軌的先后，從前至后依次檢查入軌上的所有車廂。如果正在檢查的車廂就是下一個(gè)滿足查入軌上的所有車廂。如果正在檢查的車廂就是下一個(gè)滿足排列要求的車廂，可以直接把它放到出軌上去。排列要求的車廂，可以直接把它放到出軌上去。l如果不是，則把它移動(dòng)到緩沖鐵軌上，

22、再按輸出次序要求輪如果不是，則把它移動(dòng)到緩沖鐵軌上，再按輸出次序要求輪到它時(shí)才將它放到出軌上。緩沖鐵軌是按照到它時(shí)才將它放到出軌上。緩沖鐵軌是按照FIFO（隊(duì)列）的（隊(duì)列）的方式使用的。方式使用的。lRearrangementTrack重排重排n個(gè)車廂，它最多可使用個(gè)車廂，它最多可使用k個(gè)緩沖鐵個(gè)緩沖鐵軌軌，如果緩沖鐵軌不足，就不能成功地重排，則返回，如果緩沖鐵軌不足，就不能成功地重排，則返回false，否，否則返回則返回true。l開(kāi)始時(shí)創(chuàng)建一個(gè)指向開(kāi)始時(shí)創(chuàng)建一個(gè)指向k個(gè)隊(duì)列的表頭數(shù)組個(gè)隊(duì)列的表頭數(shù)組Qk，其中，其中，Qi（i=1,2,k）表示第）表示第i個(gè)緩沖鐵軌（隊(duì)列）。個(gè)緩沖鐵軌（隊(duì)列

23、）。NowOut是下一個(gè)是下一個(gè)要輸出至出軌的車廂號(hào)。要輸出至出軌的車廂號(hào)。minH是已進(jìn)入各緩沖鐵軌中最小的是已進(jìn)入各緩沖鐵軌中最小的車廂號(hào)，車廂號(hào)，minQ是是minH號(hào)車廂所在的緩沖鐵軌（即隊(duì)列編號(hào)）號(hào)車廂所在的緩沖鐵軌（即隊(duì)列編號(hào)）。29車廂重排問(wèn)題車廂重排問(wèn)題：lRearrangementTrackRearrangementTrack調(diào)用調(diào)用OutputOutput和和HoldHold兩個(gè)算法。兩個(gè)算法。l算法算法OutputOutput用于將當(dāng)前在緩沖鐵軌中，可以送到出軌的車廂送至出軌，用于將當(dāng)前在緩沖鐵軌中，可以送到出軌的車廂送至出軌，它同時(shí)再尋找緩沖鐵軌中最小的車廂編號(hào)，修改它

24、同時(shí)再尋找緩沖鐵軌中最小的車廂編號(hào)，修改minQminQ和和minHminH。l算法算法HoldHold根據(jù)車廂調(diào)度規(guī)則，把某個(gè)車廂根據(jù)車廂調(diào)度規(guī)則，把某個(gè)車廂currentcurrent送入一個(gè)緩沖鐵軌，送入一個(gè)緩沖鐵軌，如果如果currentcurrent可以成為緩沖鐵軌中新的最小車廂，就修改可以成為緩沖鐵軌中新的最小車廂，就修改minQminQ和和 minHminH。l在把一節(jié)車廂移動(dòng)到緩沖鐵軌中時(shí)，采用如下的原則來(lái)確定應(yīng)該把這節(jié)在把一節(jié)車廂移動(dòng)到緩沖鐵軌中時(shí)，采用如下的原則來(lái)確定應(yīng)該把這節(jié)車廂移動(dòng)到哪一個(gè)緩沖鐵軌，這個(gè)原則可以減少緩沖鐵軌的使用，車廂車廂移動(dòng)到哪一個(gè)緩沖鐵軌，這個(gè)原則可

25、以減少緩沖鐵軌的使用，車廂currentcurrent應(yīng)移動(dòng)到這樣的緩沖鐵軌中：應(yīng)移動(dòng)到這樣的緩沖鐵軌中：l該緩沖鐵軌中現(xiàn)有各車廂的編號(hào)均小于該緩沖鐵軌中現(xiàn)有各車廂的編號(hào)均小于currentcurrent；l如果有多個(gè)緩沖鐵軌都滿足這一條件，則選擇一個(gè)緩沖鐵軌隊(duì)尾（如果有多個(gè)緩沖鐵軌都滿足這一條件，則選擇一個(gè)緩沖鐵軌隊(duì)尾（左端）車廂編號(hào)最大的緩沖鐵軌；左端）車廂編號(hào)最大的緩沖鐵軌；l如果已有車廂的緩沖鐵軌中，隊(duì)尾車廂編號(hào)都大于如果已有車廂的緩沖鐵軌中，隊(duì)尾車廂編號(hào)都大于currentcurrent，則，則currentcurrent選擇一個(gè)空的緩沖鐵軌（如果存在）進(jìn)入。選擇一個(gè)空的緩沖鐵軌（如

26、果存在）進(jìn)入。l如果也無(wú)空緩沖鐵軌，則無(wú)法調(diào)度。如果也無(wú)空緩沖鐵軌，則無(wú)法調(diào)度。30車廂重排問(wèn)題車廂重排問(wèn)題：車廂重排算法（車廂重排算法（RearrangementTrackRearrangementTrack）bool bool RearrangementTrackRearrangementTrack (int r, int n, int k) (int r, int n, int k) / / 車廂初始排列為車廂初始排列為r1:nr1:n，如果重排成功返回，如果重排成功返回true ,true ,否則，返回否則，返回 falsefalse Queue Queue * *Q = new Qu

27、eue k; Q = new Queue k; / / 創(chuàng)建創(chuàng)建k k個(gè)緩沖鐵軌隊(duì)列個(gè)緩沖鐵軌隊(duì)列H Hint NowOut = 1; int NowOut = 1; / / 當(dāng)前應(yīng)該輸出的車廂編號(hào)當(dāng)前應(yīng)該輸出的車廂編號(hào)int minH = n+1; int minH = n+1; / / 緩沖鐵軌中編號(hào)最小的車廂編號(hào)，目前假設(shè)為緩沖鐵軌中編號(hào)最小的車廂編號(hào)，目前假設(shè)為n+1n+1int minQ; int minQ; / minH/ minH車廂對(duì)應(yīng)的緩沖鐵軌編號(hào)車廂對(duì)應(yīng)的緩沖鐵軌編號(hào)for (int i=1; i = n; i+) for (int i=1; i = n; i+) / /

28、重排車廂重排車廂 if (ri = NowOut) if (ri = NowOut) / / 調(diào)度的車廂編號(hào)是剛剛出站的車廂編號(hào)后一個(gè)，直接輸出調(diào)度的車廂編號(hào)是剛剛出站的車廂編號(hào)后一個(gè)，直接輸出 cout cout 從入軌輸出車廂從入軌輸出車廂 ri ri 到出軌到出軌 endl; endl; NowOut+; NowOut+; while (minH = NowOut) while (minH = NowOut) / / 從緩沖鐵軌中輸出從緩沖鐵軌中輸出minHminH Output(minH, minQ, Q, k, n); Output(minH, minQ, Q, k, n); Now

29、Out+; NowOut+; else else / / 將將riri送入某個(gè)緩沖鐵軌送入某個(gè)緩沖鐵軌 if (!Hold(ri, minH, minQ, Q, k, n) if (!Hold(ri, minH, minQ, Q, k, n)/ Hold/ Hold返回返回truetrue表示送入成功表示送入成功 return false; return false; return true;return true; 31車廂重排問(wèn)題車廂重排問(wèn)題：車廂重排算法（車廂重排算法（RearrangementTrackRearrangementTrack）void Output(int &mi

30、nH, int &minQ, Queue Q, int k, int n)void Output(int &minH, int &minQ, Queue Q, int k, int n) / / 從從minQminQ中輸出最小車廂中輸出最小車廂minHminH，并尋找下一個(gè)最小的，并尋找下一個(gè)最小的 minHminH和和minQ.minQ.int current; int current; / / 當(dāng)前車廂編號(hào)當(dāng)前車廂編號(hào)DeQueue(QminQ, minH); DeQueue(QminQ, minH); / 從隊(duì)列從隊(duì)列minQ minQ 出隊(duì)編號(hào)最小的車廂出隊(duì)編號(hào)

31、最小的車廂minHminHcout cout 從從 minQ minQ緩沖鐵軌輸出緩沖鐵軌輸出 minH minH 到出軌到出軌 endl; endl;minH = n + 1;minH = n + 1;/假設(shè)一個(gè)最小車廂編號(hào)，它比實(shí)際車廂號(hào)大，以后替換假設(shè)一個(gè)最小車廂編號(hào)，它比實(shí)際車廂號(hào)大，以后替換for (int i = 1; i = k; i+)for (int i = 1; i = k; i+) / / 通過(guò)檢查所有隊(duì)列的首部，尋找新的通過(guò)檢查所有隊(duì)列的首部，尋找新的minH minH 和和minQminQcurrent =GetFront(Qi,x);current =GetFron

32、t(Qi,x);if (!IsEmpty(Qi) & current minHif (!IsEmpty(Qi) & current minH minH = current; minH = current; minQ = i;minQ = i; /if/if / /for/for 32車廂重排問(wèn)題車廂重排問(wèn)題：車廂重排算法（車廂重排算法（RearrangementTrackRearrangementTrack）bool Hold(int current, int& minH, int &minQ, Queue Q, int k)bool Hold(int curr

33、ent, int& minH, int &minQ, Queue Q, int k) /為車廂為車廂 currentcurrent尋找最優(yōu)的緩沖鐵軌，如果沒(méi)有，則返回尋找最優(yōu)的緩沖鐵軌，如果沒(méi)有，則返回false false ，否則返回，否則返回truetrueint int BestCushion = 0, BestCushion = 0, / / 目前最優(yōu)的緩沖鐵軌，為目前最優(yōu)的緩沖鐵軌，為0 0時(shí)表示還未找到最優(yōu)的緩沖鐵軌時(shí)表示還未找到最優(yōu)的緩沖鐵軌BestLast = 0, BestLast = 0, / BestCushion/ BestCushion中最后一節(jié)車廂的

34、編號(hào)中最后一節(jié)車廂的編號(hào)intint x; x; / / 車廂的編號(hào)車廂的編號(hào)for (int i = 1; i = k; i+)for (int i = 1; i x & x BestLast)if (current x & x BestLast)/ x/ x成為新的最大車廂成為新的最大車廂BestLast = x;BestLast = x;BestCushion = i;BestCushion = i; else if (!BestCushion) else if (!BestCushion) / current/ current小于已使用的緩沖鐵軌中最后一節(jié)車廂的編號(hào)，小

35、于已使用的緩沖鐵軌中最后一節(jié)車廂的編號(hào)， BestCushion = i; BestCushion = i; / / 則進(jìn)入未使用的緩沖鐵軌則進(jìn)入未使用的緩沖鐵軌i iif (!BestCushion) if (!BestCushion) return false; return false; / / 沒(méi)有可用的緩沖鐵軌沒(méi)有可用的緩沖鐵軌, ,無(wú)法調(diào)度，失敗。無(wú)法調(diào)度，失敗。EnQueue( QBestCushion, current ); EnQueue( QBestCushion, current ); / / 把把currentcurrent進(jìn)入最優(yōu)鐵軌隊(duì)列進(jìn)入最優(yōu)鐵軌隊(duì)列cout co

36、ut 從入軌將從入軌將 current current 移到最優(yōu)緩沖鐵軌移到最優(yōu)緩沖鐵軌 BestCushion endl; BestCushion endl;if (current minH) if (current minH) / / 檢查檢查currentcurrent可否成為新的可否成為新的minH minH 和和minQminQ，如果是就修改，如果是就修改minH = current; minH = current; minQ = BestCushion;minQ = BestCushion; return true;return true; 33車廂重排問(wèn)題車廂重排問(wèn)題：企業(yè)已擁有

37、定量資金，準(zhǔn)備將這部分資金投資于多個(gè)項(xiàng)目，并且可預(yù)知可供企業(yè)已擁有定量資金，準(zhǔn)備將這部分資金投資于多個(gè)項(xiàng)目，并且可預(yù)知可供投資的項(xiàng)目的資金需求及投資回報(bào)率。可是，面臨的問(wèn)題是由于資金有投資的項(xiàng)目的資金需求及投資回報(bào)率?？墒牵媾R的問(wèn)題是由于資金有限，不可能同時(shí)投資于幾個(gè)較高回報(bào)率的項(xiàng)目，只能從較高回報(bào)率項(xiàng)目限，不可能同時(shí)投資于幾個(gè)較高回報(bào)率的項(xiàng)目，只能從較高回報(bào)率項(xiàng)目和較低回報(bào)率項(xiàng)目中選擇項(xiàng)目進(jìn)行組合投資，以使投資回報(bào)最大化，同和較低回報(bào)率項(xiàng)目中選擇項(xiàng)目進(jìn)行組合投資，以使投資回報(bào)最大化，同時(shí)不再追加資金。這樣就可能產(chǎn)生多種組合方案，進(jìn)而從多種組合方案時(shí)不再追加資金。這樣就可能產(chǎn)生多種組合方案，

38、進(jìn)而從多種組合方案中選擇一種組合的處理。中選擇一種組合的處理。為解決此類問(wèn)題，首先決定哪些項(xiàng)目可以組合。對(duì)于不能同時(shí)選擇的投資項(xiàng)為解決此類問(wèn)題，首先決定哪些項(xiàng)目可以組合。對(duì)于不能同時(shí)選擇的投資項(xiàng)目稱為沖突項(xiàng)目。然后再核算各種項(xiàng)目組合的資金需求總量，如某種項(xiàng)目稱為沖突項(xiàng)目。然后再核算各種項(xiàng)目組合的資金需求總量，如某種項(xiàng)目組合的資金需求總量超過(guò)已擁有的定量資金，則認(rèn)為該種組合不可行目組合的資金需求總量超過(guò)已擁有的定量資金，則認(rèn)為該種組合不可行；如存在多個(gè)組合方案的資金需求總量都不超過(guò)已擁有的資金總量，則；如存在多個(gè)組合方案的資金需求總量都不超過(guò)已擁有的資金總量，則企業(yè)經(jīng)營(yíng)者再?gòu)闹羞x擇投資回報(bào)率最大

39、化的投資組合。企業(yè)經(jīng)營(yíng)者再?gòu)闹羞x擇投資回報(bào)率最大化的投資組合。這類問(wèn)題又稱為這類問(wèn)題又稱為劃分子集劃分子集問(wèn)題。問(wèn)題。 34將將a1，a2，. ，an項(xiàng)目作為投資侯選項(xiàng)目，這里項(xiàng)目作為投資侯選項(xiàng)目，這里ai 表示侯選項(xiàng)目的表示侯選項(xiàng)目的項(xiàng)目編號(hào)，抽象為項(xiàng)目集合項(xiàng)目編號(hào)，抽象為項(xiàng)目集合A=a1,a2,.,an。不能歸入某投資。不能歸入某投資組合方案的項(xiàng)目，表現(xiàn)為集合中的某些元素之間會(huì)發(fā)生沖突組合方案的項(xiàng)目，表現(xiàn)為集合中的某些元素之間會(huì)發(fā)生沖突，可表示為集合上的關(guān)系，可表示為集合上的關(guān)系R=(ai,aj)，如，如(ai ，aj)屬于屬于R集合，集合，則表示則表示ai與與aj之間存在沖突。之間存在沖

40、突。根據(jù)根據(jù)R R關(guān)系將關(guān)系將A A集合劃分成不沖突的若干個(gè)組合，即劃分為不相交集合劃分成不沖突的若干個(gè)組合，即劃分為不相交的子集的子集A A1 1, A, A2 2,.,A,.,Ak k (k=n)(k=n)，使任何子集上的元素均無(wú)沖突，使任何子集上的元素均無(wú)沖突。 如共設(shè)個(gè)投資項(xiàng)目，項(xiàng)目編號(hào)以整數(shù)如共設(shè)個(gè)投資項(xiàng)目，項(xiàng)目編號(hào)以整數(shù)1n1n表示，則：表示，則： 集合集合A=1,2,3,4,5,6,7,8,9A=1,2,3,4,5,6,7,8,9，另根據(jù)調(diào)研，存在項(xiàng)目沖突關(guān)系：，另根據(jù)調(diào)研，存在項(xiàng)目沖突關(guān)系：R=(2,8),(4,9),(2,9),(2,1),(2,5),(2,6),(5,9),

41、(5,6),(4,5),(5,7),(6,7)R=(2,8),(4,9),(2,9),(2,1),(2,5),(2,6),(5,9),(5,6),(4,5),(5,7),(6,7),(3,7),(3,6),(3,7),(3,6)由此由此R R集合，則可得出的可行子集劃分為：集合，則可得出的可行子集劃分為： A A1 1=1,3,4,8 A=1,3,4,8 A2 2=2,7 A=2,7 A3 3=5 A=5 A4 4=6,9=6,935投資組合問(wèn)題投資組合問(wèn)題：根據(jù)沖突關(guān)系集合導(dǎo)出一個(gè)沖突關(guān)系矩陣根據(jù)沖突關(guān)系集合導(dǎo)出一個(gè)沖突關(guān)系矩陣r。如關(guān)系矩陣中。如關(guān)系矩陣中ai與與aj對(duì)應(yīng)位置值對(duì)應(yīng)位置值為

42、為1，則表示沖突，則表示沖突，ai與與aj對(duì)應(yīng)位置值為對(duì)應(yīng)位置值為0，表示不沖突。如上面給出的例子，表示不沖突。如上面給出的例子，可導(dǎo)出如下沖突關(guān)系矩陣：，可導(dǎo)出如下沖突關(guān)系矩陣：圖圖 沖突關(guān)系矩陣沖突關(guān)系矩陣r =00000110000100010101101101010010110010000010001101234567345671201000008010110090000001800011000190036投資組合問(wèn)題投資組合問(wèn)題：l設(shè)一狀態(tài)數(shù)組，用于記下各項(xiàng)目經(jīng)過(guò)劃分后所屬的設(shè)一狀態(tài)數(shù)組，用于記下各項(xiàng)目經(jīng)過(guò)劃分后所屬的子集編號(hào)。仍以上面的例子說(shuō)明，最終可得出的可子集編號(hào)。仍以上面的例

43、子說(shuō)明，最終可得出的可行子集劃分為：行子集劃分為： A1=1,3,4,8 A2=2,7 A3=5 A4=6,9 A1=1,3,4,8 A2=2,7 A3=5 A4=6,9 即即s1=s3=s4=s8=1s1=s3=s4=s8=1，也就是項(xiàng)目，也就是項(xiàng)目a1,a3,a4,a8a1,a3,a4,a8屬于同一子集，其子集編號(hào)是屬于同一子集，其子集編號(hào)是1 1；s2=s7=2s2=s7=2，也就，也就是項(xiàng)目是項(xiàng)目a2,a7a2,a7屬于同一子集，其子集編號(hào)是屬于同一子集，其子集編號(hào)是2 2；等等。；等等。12113421234567S184937投資組合問(wèn)題投資組合問(wèn)題：隊(duì)列的變化過(guò)程是：隊(duì)列的變化過(guò)

44、程是：將隊(duì)列中的所有元素逐個(gè)出隊(duì)一次，每次第一個(gè)出隊(duì)將隊(duì)列中的所有元素逐個(gè)出隊(duì)一次，每次第一個(gè)出隊(duì)的項(xiàng)目編號(hào)作為進(jìn)入新子集的第一個(gè)項(xiàng)目，以后出隊(duì)的項(xiàng)目編號(hào)作為進(jìn)入新子集的第一個(gè)項(xiàng)目，以后出隊(duì)的元素與已進(jìn)入當(dāng)前子集的項(xiàng)目進(jìn)行比較，如不與進(jìn)的元素與已進(jìn)入當(dāng)前子集的項(xiàng)目進(jìn)行比較，如不與進(jìn)入當(dāng)前子集的任何項(xiàng)目發(fā)生沖突，則作為進(jìn)入當(dāng)前子入當(dāng)前子集的任何項(xiàng)目發(fā)生沖突，則作為進(jìn)入當(dāng)前子集的項(xiàng)目，凡是屬于當(dāng)前子集的項(xiàng)目不再進(jìn)隊(duì)，不屬集的項(xiàng)目，凡是屬于當(dāng)前子集的項(xiàng)目不再進(jìn)隊(duì)，不屬于當(dāng)前子集的就再次進(jìn)入隊(duì)列于當(dāng)前子集的就再次進(jìn)入隊(duì)列Q Q。Q Q中的元素全部出隊(duì)一次，就篩選出一個(gè)子集，重新入中的元素全部出隊(duì)一次，

45、就篩選出一個(gè)子集，重新入隊(duì)的元素構(gòu)成再次篩選的初始隊(duì)列元素，由于形成某隊(duì)的元素構(gòu)成再次篩選的初始隊(duì)列元素，由于形成某一子集的元素不再入隊(duì)，隊(duì)列元素在不斷減少，直至一子集的元素不再入隊(duì)，隊(duì)列元素在不斷減少，直至隊(duì)列中無(wú)出隊(duì)元素，子集劃分過(guò)程完成隊(duì)列中無(wú)出隊(duì)元素，子集劃分過(guò)程完成 38投資組合問(wèn)題投資組合問(wèn)題：劃分子集算法（劃分子集算法（DivisionDivision）void Division (int r , int n )void Division (int r , int n ) / n/ n個(gè)項(xiàng)目劃分不沖突的子集，沖突關(guān)系在個(gè)項(xiàng)目劃分不沖突的子集，沖突關(guān)系在r r數(shù)組中表示數(shù)組中表示QueueQueue Q; Q;int int rearkeep; rearkeep;intint current; current;/項(xiàng)目編號(hào)項(xiàng)目編號(hào)for (i=1, i=n,i