【正文】 t n,char x,char y,char z) (1) { (2) if(n==1) (3) move(1,x,z)。 (4) else{ (5) hanoi(n1,x,z,y)。 (6) move(n,x,z)。 (7) hanoi(n1,y,x,z)。 (8) } (9) } A B C 3 A B C 0 2 B A C 8 1 A B C 8 A B C 3 A B C 0 2 B A C 8 3 A B C 0 棧空 3 A B C 0 2 B A C 8 本節(jié)結(jié)束 第十四講 數(shù)據(jù)結(jié)構(gòu) 隊列及其實現(xiàn) 主講：劉立嘉 １、隊列定義 ３、存儲結(jié)構(gòu) ４、運算規(guī)則 ５、實現(xiàn)方式 ２、邏輯結(jié)構(gòu) 只能在表的一端進行插入操作，在表的另一端進行刪除操作的線性表。 隊尾插入 隊頭刪除 與線性表相同，仍為一對一關(guān)系。 順序隊列 或 鏈隊列 ，以 循環(huán)順序隊列 更常見。 只能在隊首和隊尾運算，且訪問結(jié)點時依照先進先出 （ FIFO） 的原則。 關(guān)鍵是掌握 入隊 和 出隊 操作，具體實現(xiàn)依順序隊或鏈隊的不同而不同。 基本操作 ： 入隊或出隊，建空隊列，判隊空或隊滿等操作。 隊列的定義 隊列：是先進先出（ FIFO）的線性表。只允許在表的一端進行插入，而在另一端進行刪除元素的線性表。 a1, a2, a3 , a4, …… an1,an 圖 隊列示意圖 隊頭 隊尾 允許插入的一端叫 隊尾 ，允許刪除的一端稱為 隊頭 。 假設(shè)隊列 q=(a1, a2, … ,an） a1是隊頭元素 ,an隊尾元素 。 出隊列 入隊列 注：隊列的 實現(xiàn)方式 是本節(jié)重點， 關(guān)鍵是掌握 入隊 和 出隊 操作。 具體實現(xiàn)依 存儲結(jié)構(gòu) （ 鏈隊列 或 順序隊列 ）的不同而不同。 1. 離散事件的模擬 （模擬事件發(fā)生的先后順序 ,例如 CPU芯片中的指令譯碼隊列） ； 2. 操作系統(tǒng)中的作業(yè)調(diào)度 （一個 CPU執(zhí)行多個作業(yè)） ； 3. 簡化程序設(shè)計。 答： 問：為什么要設(shè)計隊列？它有什么獨特用途？ 舉例 1：乘坐公共汽車，應(yīng)該在車站排隊，車來后，按順序上車。 舉例 2：在 Windows這類多任務(wù)的操作系統(tǒng)環(huán)境中，每個應(yīng)用程序響應(yīng)一系列的“消息”，像用戶點擊鼠標(biāo)，拖動窗口這些操作都會導(dǎo)致向應(yīng)用程序發(fā)送消息。為此，系統(tǒng)將為每個應(yīng)用程序創(chuàng)建一個隊列，用來存放發(fā)送給該應(yīng)用程序的所有消息，應(yīng)用程序的處理過程就是不斷地從隊列中讀取消息，并依次給予響應(yīng)。 ADT Queue { 數(shù)據(jù)對象： D＝ {ai | ai∈ ElemSet, i=1,2,...,n, n≥0} 數(shù)據(jù)關(guān)系： R1＝ { ai1,ai | ai1, ai ∈ D, i=2,...,n} 約定其中 a1 端為隊列頭， an 端為隊列尾 基本操作： InitQueue(amp。Q) DestroyQueue(amp。Q) ClearQueue(amp。Q) QueueEmpty(Q) QueueLength(Q) GetHead(Q, amp。e) EnQueue(amp。Q, e) DeQueue(amp。Q, amp。e) QueueTravers(Q, visit()) } ADT Queue InitQueue(amp。Q) 操作結(jié)果：構(gòu)造一個空隊列 Q。 DestroyQueue(amp。Q) 初始條件：隊列 Q已存在。 操作結(jié)果：隊列 Q被銷毀， 不再存在。 ClearQueue(amp。Q) 初始條件：隊列 Q已存在。 操作結(jié)果：將 Q清為空隊列。 QueueEmpty(Q) 初始條件：隊列 Q已存在。 操作結(jié)果：若 Q為空隊列，則返回 TRUE，否則返 回 FALSE。 QueueLength(Q) 初始條件：隊列 Q已存在。 操作結(jié)果：返回 Q的元素個數(shù)，即隊列的長度。 GetHead(Q, amp。e) 初始條件： Q為非空隊列。 操作結(jié)果：用 e返回 Q的隊頭元素。 a1 a2 an … … EnQueue(amp。Q, e) 初始條件：隊列 Q已存在。 操作結(jié)果：插入元素 e為 Q的新的隊尾元素。 a1 a2 an e … … DeQueue(amp。Q, amp。e) 初始條件： Q為非空隊列。 操作結(jié)果：刪除 Q的隊頭元素，并用 e返回其值。 a1 a2 an … … 隊列的主要運算： （ 1）設(shè)置一個空隊列； （ 2）讀取隊頭元素 。 （ 3）插入一個新的隊尾元素，稱為入隊； （ 4）刪除隊頭元素，稱為出隊。 一個鏈隊列顯然需要兩個分別指示隊頭和隊尾的指針 （ 頭指針 ， 尾指針 ）才能唯一確定 。 為了操作方便 ， 給鏈隊列添加一個頭結(jié)點 ， 并令頭指針指向頭結(jié)點 。 空的鏈隊列的判決條件為頭指針和尾指針均指向頭結(jié)點 。 鏈隊列 ：用鏈表表示的隊列。 鏈隊列 a1 ∧ an … ∧ 空隊列 鏈隊列 鏈隊列示意圖 隊頭 隊尾 front rear x入 隊 ^ x front rear y入 隊 x ^ y front rear x出 隊 x ^ y front rear 空隊 ^ front rear y出 隊 ^ typedef struct QNode {// 結(jié)點類型 QElemType data。 struct QNode *next。 } QNode, *QueuePtr。 typedef struct { // 鏈隊列類型 QueuePtr front。 // 隊頭指針 QueuePtr rear。 // 隊尾指針 } LinkQueue。 //單鏈隊列 ——隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu) //ADT Queue的表示和實現(xiàn) Status InitQueue (LinkQueue amp。Q) { // 構(gòu)造一個空隊列 Q == (QueuePtr)malloc(sizeof(QNode))。 if (!) exit (OVERFLOW)。 //存儲分配失敗 next = NULL。 return OK。 } //基本操作的算法描述 銷毀隊列 a1 a2 an Status DestroyQueue(LinkQueue amp。Q){ //銷毀隊列 while(){ =next。 // free()。 =。 //（隊頭元素） } return ok。 } 算法見下頁 插入一個元素（入隊） e ^a1 a2 an 算法見下頁 Status EnQueue (LinkQueue amp。Q, QElemType e) { // 插入元素 e為 Q的新的隊尾元素 p = (QueuePtr) malloc (sizeof (QNode))。 if (!p) exit (OVERFLOW)。 //存儲分配失敗 pdata = e。 pnext = NULL。 next = p。 = p。 return OK。 } an a2 a1 an a2 a1 刪除一個元素（出隊） 隊頭 隊尾 p 算法見下頁 Status DeQueue (LinkQueue amp。Q, QElemType amp。e) { //若隊列不空，則刪除 Q的隊頭元素， //用 e 返回其值，并返回 OK；否則返回 ERROR if ( == ) return ERROR。 p = next。 e = pdata。 next = pnext。 if ( == p) = 。//一個元素 free (p)。 return OK。 } 一般情況下，刪除隊頭元素僅需修改頭結(jié)點中的指針，但當(dāng)隊列中最后一個元素被刪后，隊列尾指針丟失，需對隊尾指針重新賦值（指向頭結(jié)點）。 本節(jié)結(jié)束 第十五講 數(shù)據(jù)結(jié)構(gòu) 順序循環(huán)隊列與隊列應(yīng)用 (1) 主講：劉立嘉 在隊列的順序存儲結(jié)構(gòu)中，除了用一組地址連續(xù)的存儲單元依次存放從隊列頭到隊列尾的元素之外，需附設(shè)兩個 front和 rear分別指示隊列頭元素及隊列尾元素的位置。 為在 c語言中描述方便起見，在此約定：初始化建空隊列時，令 front=rear=0,每當(dāng)插入新的隊列尾元素時，尾指針增 1；每當(dāng)刪除隊列頭元素時，頭指針增 1。 在非空隊列中，頭指針始終指向隊列頭元素，而尾指針始終指向隊列尾元素的下一個位置。 順序循環(huán)隊列 3 2 1 0 （ a)rear=front=0(隊空） e3 e4 (c)e1,e2出隊，e4入隊，隊滿 =4 e1 e2 e3 (b)e1,e2,e3入隊 隊空時， 令 rear=front=0， 當(dāng)有新元素入隊時，尾指針加 1，當(dāng)有元素出隊時，頭指針加 1。故在非空隊列中，頭指針始終指向隊頭元素，而尾指針始終指向隊尾元素的下一位置 不能繼續(xù)插入，數(shù)組會越界 順序隊列的 “ 假溢出 ” 問題 (1)假 溢出 順序隊列因多次入隊和出隊操作后出現(xiàn)的有存儲空間但不能進行入隊操作的溢出。 (2)如何解決順序隊列的假溢出問題？ 可采取四種方法： 1)采用循環(huán)隊列； 2)按最大可能的進隊操作次數(shù)設(shè)置順序隊列的最大元素個數(shù)； 3)修改出隊算法，使每次出隊列后都把隊列中剩余數(shù)據(jù)元素向隊頭方向移動一個位置； ４ )修改入隊算法，增加判斷條件，當(dāng)假 溢出時，把隊列中的數(shù)據(jù)元素向?qū)︻^移動，然后方完成入隊操作。 0 1 2 3 4 5 J4 J5 J6 0 1 2 3 4 5 J9 J8 J7 J4 J5 J6 0 1 2 3 4 5 隊空： front==rear 隊滿： front==rear 隊空 一般情況 隊滿 初始狀態(tài) 順序循環(huán)隊列的隊空和隊滿判斷問題 新問題： 在循環(huán)隊列中，空隊特征是 front=rear； 隊滿時也會有front=rear； 判決條件將出現(xiàn)二義性！ 解決方案有三： ①使用一個 計數(shù)器 記錄隊列中元素個數(shù)（即隊列長度）； 判隊滿： count0 amp。amp。 rear==front 判隊空： count==0 ② 加 設(shè)標(biāo)志位 ，出隊 時置０ ,入隊時置１ ,則可識別當(dāng)前front=rear屬于何種情況 判隊滿： tag==1 amp。amp。 rear==front 判隊空： tag==0 amp。amp。 rear==front ③ 少用 一個存儲單元 判隊滿： front=＝ (rear+1)%MaxQueueSize 判隊空： rear==front J4 J5 J6 0 1 2 3 4 5 rear front 初始狀態(tài) 0 1 2 3 4 5 rear front J4 J5 J6 0 1 2 3 4 5 rear front J8 J7 隊空 一般情況 解決方案： 、隊滿 ： 隊空： == 隊滿： (+1)%MAXQSIZE== 隊滿 define MAXQSIZE 100