1、3.2 隊列（隊列（Queue） 第三章第三章 棧和隊列棧和隊列1. 基本概念基本概念2. 邏輯結構邏輯結構3. 存儲結構存儲結構4. 運算規則運算規則5. 實現方式實現方式1第三章：棧和隊列隊列隊列 （Queue）是僅在表尾表尾進行插入插入操作，在表頭表頭進行刪除刪除操作的線性表。它是一種先進先出（）的線性表。在在隊尾插入隊尾插入元素稱為元素稱為問：為什么要設計隊列？它有什么用途？問：為什么要設計隊列？它有什么用途？離散事件的模擬離散事件的模擬（模擬事件發生的先后順序 ）操作系統中的作業調度操作系統中的作業調度（一個CPU執行多個作業） 簡化程序設計。簡化程序設計。23.2 隊列隊首隊首隊尾

2、隊尾a1 , a2 , a3 , .,an-1 , an 。在在隊首刪除隊首刪除元素稱為元素稱為與線性表相同，仍為一對一關系。與線性表相同，仍為一對一關系。順序隊順序隊或或鏈隊鏈隊，以，以循環順序隊循環順序隊更常見。更常見。只能在隊首和隊尾運算，且訪問結點時依照只能在隊首和隊尾運算，且訪問結點時依照先進先出（先進先出（FIFOFIFO）的原則。的原則。關鍵是掌握關鍵是掌握入隊入隊和和出隊出隊操作，具體實現依順操作，具體實現依順序隊或鏈隊的不同而不同。序隊或鏈隊的不同而不同。只能在表的一端進行插入運算，在表的另一只能在表的一端進行插入運算，在表的另一端進行刪除運算的線性表。端進行刪除運算的線性表

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

4、ruct QueuePtr front ; /隊首指針隊首指針 QueuePtr rear ; /隊尾指針隊尾指針 LinkQueue;結點結點類型定義：類型定義： typedef Struct QNode QElemType data; /元素元素 QNode *next; /指向下一結點的指針指向下一結點的指針 Qnode , * QueuePtr ;關于整個鏈隊的關于整個鏈隊的總體描述總體描述鏈隊中任一鏈隊中任一結點的結構結點的結構63.2 隊列鏈隊列鏈隊列用鏈表實現的隊列，需要兩個分別指向隊頭的指針用鏈表實現的隊列，需要兩個分別指向隊頭的指針（頭指針）和指向對尾的指針（尾指針）。（頭指

5、針）和指向對尾的指針（尾指針）。空鏈隊的特征？空鏈隊的特征？Q(隊尾隊尾)(隊首隊首)fronta1a2a3rearp 怎樣實現鏈隊的怎樣實現鏈隊的入隊和出隊操入隊和出隊操作？作？ 鏈隊會滿嗎？鏈隊會滿嗎？frontrearfront=rear一般不會，因為刪除時有一般不會，因為刪除時有free動作。除非內存不足！動作。除非內存不足！出隊（頭部刪除）：出隊（頭部刪除）：p=front-next; front-next=p-next; free(p);SD鏈隊示意圖：鏈隊示意圖：73.2 隊列入隊（尾部插入）：入隊（尾部插入）：rearnext=S; rear=S;鏈隊入隊出隊示意圖：鏈隊入隊出

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

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

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

9、 e=Qfront; front+; 討論：討論：有有缺缺陷陷 怎樣實現入隊和出隊怎樣實現入隊和出隊操作？操作？核心語句如下核心語句如下：用用base做數組名做數組名e順序隊示意圖：順序隊示意圖：123.2 隊列基本操作的實現初始化空隊：初始化空隊： 入隊：入隊：出隊：出隊：隊空條件：隊空條件：隊滿條件：隊滿條件：問題：假上溢！順序隊操作示意圖：順序隊操作示意圖：順序隊操作示意圖：順序隊操作示意圖：解決假溢出的途徑解決假溢出的途徑采用循環隊列采用循環隊列答：答：在順序隊中，當尾指針已經到了數組的在順序隊中，當尾指針已經到了數組的上界，不能再有入隊操作，但其實數組中還上界，不能再有入隊操作，但其

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

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

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

13、t = rear )隊滿條件隊滿條件： front = (rear) % N (N=maxsize)隊列長度隊列長度（即數據元素個數）（即數據元素個數）：L=（Nrearfront）% N J2 J3J1 J4 J5frontrear 實際中常選用實際中常選用方案方案3（人為人為浪費一個單元浪費一個單元）：即即front和和rear二者之一指向實元素，另一個指向空閑元素。二者之一指向實元素，另一個指向空閑元素。 問問3： 在具有在具有n個單元的循個單元的循環隊列中，隊滿時共有多少環隊列中，隊滿時共有多少個元素？個元素？ N-1個個6 問問1：左圖中隊列左圖中隊列maxsize N=？問問2：左

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

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

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

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

18、 4個單元有效）個單元有效） 。例例4 4：對對4 4個數據元素進行隊操作。在進隊操作時，按個數據元素進行隊操作。在進隊操作時，按a1a1、a2a2、a3a3、a4a4次序每次進入一個元素（假設隊的初態為空）。次序每次進入一個元素（假設隊的初態為空）。 進隊進隊2 2次次 出隊出隊1 1次次 再進隊再進隊2 2次次 出隊出隊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 隊列l貨運貨運列車共

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

20、第一站）。l如如在出發站時，準備發出的車廂存儲在在出發站時，準備發出的車廂存儲在r r數組中，數組中，riri的的值是車廂的編號，編號越小的，就是發往越遠的車站，如值是車廂的編號，編號越小的，就是發往越遠的車站，如，開始，開始r r中的次序是：中的次序是： 7 7，4 4，2 2，5 5，8 8，9 9，1 1，6 6，3 3。那。那么，在發出本站前，就要將車廂重新編排，按從么，在發出本站前，就要將車廂重新編排，按從1 1到到n n的次的次序與車頭相連接。序與車頭相連接。 當所有的車廂按照這種次序排列時，當所有的車廂按照這種次序排列時，在到達每個車站時，只需卸掉最后幾節車廂即可。在到達每個車站

21、時，只需卸掉最后幾節車廂即可。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 圖圖 車廂調度轉軌車廂調度轉軌 車廂重排問題車廂重排問題：28l為了重排車廂，需按車廂到達入軌的先后，從前至后依次檢為了重排車廂，需按車廂到達入軌的先后，從前至后依次檢查入軌上的所有車廂。如果正在檢查的車廂就是下一個滿足查入軌上的所有車廂。如果正在檢查的車廂就是下一個滿足排列要求的車廂，可以直接把它放到出軌上去。排列要求的車廂，可以直接把它放到出軌上去。l如果不是，則把它移動到緩沖鐵軌上，

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

23、）。NowOut是下一個是下一個要輸出至出軌的車廂號。要輸出至出軌的車廂號。minH是已進入各緩沖鐵軌中最小的是已進入各緩沖鐵軌中最小的車廂號，車廂號，minQ是是minH號車廂所在的緩沖鐵軌（即隊列編號）號車廂所在的緩沖鐵軌（即隊列編號）。29車廂重排問題車廂重排問題：lRearrangementTrackRearrangementTrack調用調用OutputOutput和和HoldHold兩個算法。兩個算法。l算法算法OutputOutput用于將當前在緩沖鐵軌中，可以送到出軌的車廂送至出軌，用于將當前在緩沖鐵軌中，可以送到出軌的車廂送至出軌，它同時再尋找緩沖鐵軌中最小的車廂編號，修改它

24、同時再尋找緩沖鐵軌中最小的車廂編號，修改minQminQ和和minHminH。l算法算法HoldHold根據車廂調度規則，把某個車廂根據車廂調度規則，把某個車廂currentcurrent送入一個緩沖鐵軌，送入一個緩沖鐵軌，如果如果currentcurrent可以成為緩沖鐵軌中新的最小車廂，就修改可以成為緩沖鐵軌中新的最小車廂，就修改minQminQ和和 minHminH。l在把一節車廂移動到緩沖鐵軌中時，采用如下的原則來確定應該把這節在把一節車廂移動到緩沖鐵軌中時，采用如下的原則來確定應該把這節車廂移動到哪一個緩沖鐵軌，這個原則可以減少緩沖鐵軌的使用，車廂車廂移動到哪一個緩沖鐵軌，這個原則可

25、以減少緩沖鐵軌的使用，車廂currentcurrent應移動到這樣的緩沖鐵軌中：應移動到這樣的緩沖鐵軌中：l該緩沖鐵軌中現有各車廂的編號均小于該緩沖鐵軌中現有各車廂的編號均小于currentcurrent；l如果有多個緩沖鐵軌都滿足這一條件，則選擇一個緩沖鐵軌隊尾（如果有多個緩沖鐵軌都滿足這一條件，則選擇一個緩沖鐵軌隊尾（左端）車廂編號最大的緩沖鐵軌；左端）車廂編號最大的緩沖鐵軌；l如果已有車廂的緩沖鐵軌中，隊尾車廂編號都大于如果已有車廂的緩沖鐵軌中，隊尾車廂編號都大于currentcurrent，則，則currentcurrent選擇一個空的緩沖鐵軌（如果存在）進入。選擇一個空的緩沖鐵軌（如

26、果存在）進入。l如果也無空緩沖鐵軌，則無法調度。如果也無空緩沖鐵軌，則無法調度。30車廂重排問題車廂重排問題：車廂重排算法（車廂重排算法（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; / / 創建創建k k個緩沖鐵軌隊列個緩沖鐵軌隊列H Hint NowOut = 1; int NowOut = 1; / / 當前應該輸出的車廂編號當前應該輸出的車廂編號int minH = n+1; int minH = n+1; / / 緩沖鐵軌中編號最小的車廂編號，目前假設為緩沖鐵軌中編號最小的車廂編號，目前假設為n+1n+1int minQ; int minQ; / minH/ minH車廂對應的緩沖鐵軌編號車廂對應的緩沖鐵軌編號for (int i=1; i = n; i+) for (int i=1; i = n; i+) / /

28、重排車廂重排車廂 if (ri = NowOut) if (ri = NowOut) / / 調度的車廂編號是剛剛出站的車廂編號后一個，直接輸出調度的車廂編號是剛剛出站的車廂編號后一個，直接輸出 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送入某個緩沖鐵軌送入某個緩沖鐵軌 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車廂重排問題車廂重排問題：車廂重排算法（車廂重排算法（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，并尋找下一個最小的，并尋找下一個最小的 minHminH和和minQ.minQ.int current; int current; / / 當前車廂編號當前車廂編號DeQueue(QminQ, minH); DeQueue(QminQ, minH); / 從隊列從隊列minQ minQ 出隊編號最小的車廂出隊編號

31、最小的車廂minHminHcout cout 從從 minQ minQ緩沖鐵軌輸出緩沖鐵軌輸出 minH minH 到出軌到出軌 endl; endl;minH = n + 1;minH = n + 1;/假設一個最小車廂編號，它比實際車廂號大，以后替換假設一個最小車廂編號，它比實際車廂號大，以后替換for (int i = 1; i = k; i+)for (int i = 1; i = k; i+) / / 通過檢查所有隊列的首部，尋找新的通過檢查所有隊列的首部，尋找新的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車廂重排問題車廂重排問題：車廂重排算法（車廂重排算法（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尋找最優的緩沖鐵軌，如果沒有，則返回尋找最優的緩沖鐵軌，如果沒有，則返回false false ，否則返回，否則返回truetrueint int BestCushion = 0, BestCushion = 0, / / 目前最優的緩沖鐵軌，為目前最優的緩沖鐵軌，為0 0時表示還未找到最優的緩沖鐵軌時表示還未找到最優的緩沖鐵軌BestLast = 0, BestLast = 0, / BestCushion/ BestCushion中最后一節車廂的

34、編號中最后一節車廂的編號intint x; x; / / 車廂的編號車廂的編號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小于已使用的緩沖鐵軌中最后一節車廂的編號，小

35、于已使用的緩沖鐵軌中最后一節車廂的編號， BestCushion = i; BestCushion = i; / / 則進入未使用的緩沖鐵軌則進入未使用的緩沖鐵軌i iif (!BestCushion) if (!BestCushion) return false; return false; / / 沒有可用的緩沖鐵軌沒有可用的緩沖鐵軌, ,無法調度，失敗。無法調度，失敗。EnQueue( QBestCushion, current ); EnQueue( QBestCushion, current ); / / 把把currentcurrent進入最優鐵軌隊列進入最優鐵軌隊列cout co

36、ut 從入軌將從入軌將 current current 移到最優緩沖鐵軌移到最優緩沖鐵軌 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車廂重排問題車廂重排問題：企業已擁有

37、定量資金，準備將這部分資金投資于多個項目，并且可預知可供企業已擁有定量資金，準備將這部分資金投資于多個項目，并且可預知可供投資的項目的資金需求及投資回報率。可是，面臨的問題是由于資金有投資的項目的資金需求及投資回報率。可是，面臨的問題是由于資金有限，不可能同時投資于幾個較高回報率的項目，只能從較高回報率項目限，不可能同時投資于幾個較高回報率的項目，只能從較高回報率項目和較低回報率項目中選擇項目進行組合投資，以使投資回報最大化，同和較低回報率項目中選擇項目進行組合投資，以使投資回報最大化，同時不再追加資金。這樣就可能產生多種組合方案，進而從多種組合方案時不再追加資金。這樣就可能產生多種組合方案，

38、進而從多種組合方案中選擇一種組合的處理。中選擇一種組合的處理。為解決此類問題，首先決定哪些項目可以組合。對于不能同時選擇的投資項為解決此類問題，首先決定哪些項目可以組合。對于不能同時選擇的投資項目稱為沖突項目。然后再核算各種項目組合的資金需求總量，如某種項目稱為沖突項目。然后再核算各種項目組合的資金需求總量，如某種項目組合的資金需求總量超過已擁有的定量資金，則認為該種組合不可行目組合的資金需求總量超過已擁有的定量資金，則認為該種組合不可行；如存在多個組合方案的資金需求總量都不超過已擁有的資金總量，則；如存在多個組合方案的資金需求總量都不超過已擁有的資金總量，則企業經營者再從中選擇投資回報率最大

39、化的投資組合。企業經營者再從中選擇投資回報率最大化的投資組合。這類問題又稱為這類問題又稱為劃分子集劃分子集問題。問題。 34將將a1，a2，. ，an項目作為投資侯選項目，這里項目作為投資侯選項目，這里ai 表示侯選項目的表示侯選項目的項目編號，抽象為項目集合項目編號，抽象為項目集合A=a1,a2,.,an。不能歸入某投資。不能歸入某投資組合方案的項目，表現為集合中的某些元素之間會發生沖突組合方案的項目，表現為集合中的某些元素之間會發生沖突，可表示為集合上的關系，可表示為集合上的關系R=(ai,aj)，如，如(ai ，aj)屬于屬于R集合，集合，則表示則表示ai與與aj之間存在沖突。之間存在沖

40、突。根據根據R R關系將關系將A A集合劃分成不沖突的若干個組合，即劃分為不相交集合劃分成不沖突的若干個組合，即劃分為不相交的子集的子集A A1 1, A, A2 2,.,A,.,Ak k (k=n)(k=n)，使任何子集上的元素均無沖突，使任何子集上的元素均無沖突。 如共設個投資項目，項目編號以整數如共設個投資項目，項目編號以整數1n1n表示，則：表示，則： 集合集合A=1,2,3,4,5,6,7,8,9A=1,2,3,4,5,6,7,8,9，另根據調研，存在項目沖突關系：，另根據調研，存在項目沖突關系：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投資組合問題投資組合問題：根據沖突關系集合導出一個沖突關系矩陣根據沖突關系集合導出一個沖突關系矩陣r。如關系矩陣中。如關系矩陣中ai與與aj對應位置值對應位置值為

42、為1，則表示沖突，則表示沖突，ai與與aj對應位置值為對應位置值為0，表示不沖突。如上面給出的例子，表示不沖突。如上面給出的例子，可導出如下沖突關系矩陣：，可導出如下沖突關系矩陣：圖圖 沖突關系矩陣沖突關系矩陣r =00000110000100010101101101010010110010000010001101234567345671201000008010110090000001800011000190036投資組合問題投資組合問題：l設一狀態數組，用于記下各項目經過劃分后所屬的設一狀態數組，用于記下各項目經過劃分后所屬的子集編號。仍以上面的例子說明，最終可得出的可子集編號。仍以上面的例

43、子說明，最終可得出的可行子集劃分為：行子集劃分為： 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，也就是項目，也就是項目a1,a3,a4,a8a1,a3,a4,a8屬于同一子集，其子集編號是屬于同一子集，其子集編號是1 1；s2=s7=2s2=s7=2，也就，也就是項目是項目a2,a7a2,a7屬于同一子集，其子集編號是屬于同一子集，其子集編號是2 2；等等。；等等。12113421234567S184937投資組合問題投資組合問題：隊列的變化過程是：隊列的變化過

44、程是：將隊列中的所有元素逐個出隊一次，每次第一個出隊將隊列中的所有元素逐個出隊一次，每次第一個出隊的項目編號作為進入新子集的第一個項目，以后出隊的項目編號作為進入新子集的第一個項目，以后出隊的元素與已進入當前子集的項目進行比較，如不與進的元素與已進入當前子集的項目進行比較，如不與進入當前子集的任何項目發生沖突，則作為進入當前子入當前子集的任何項目發生沖突，則作為進入當前子集的項目，凡是屬于當前子集的項目不再進隊，不屬集的項目，凡是屬于當前子集的項目不再進隊，不屬于當前子集的就再次進入隊列于當前子集的就再次進入隊列Q Q。Q Q中的元素全部出隊一次，就篩選出一個子集，重新入中的元素全部出隊一次，

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