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