【正文】 return temp。 /*若刪除后鏈隊變?yōu)榭?，則需同時使隊尾指針變?yōu)榭?*/ if(HQfront==NULL) HQrear=NULL。 /*暫存隊首指針以便回收隊首結(jié)點 */ p=HQfront。 exit(1)。 ElemType temp。 /*若鏈隊非空，則依次修改隊尾結(jié)點的指針域和隊尾指針， 使之指向新的隊尾結(jié)點 */ else HQrear=HQrearnext=newp。 newpnext=NULL。 exit(1)。 newp=malloc(sizeof(struct sNode))。 ...frontreara1 a 2an在類型為 QueueLk的鏈隊 HQ上進行隊列的各種操作的算法如下： 1. 初始化鏈隊 void InitQueue(struct QueueLk* HQ) { /*把隊首和隊尾指針置為空 */ HQfront=HQrear=NULL。 /*鏈接指針域 */ }。 其中 sNode結(jié)點類型重寫如下： struct sNode { ElemType data。 //隊首指針 sNode* rear。 ?用于存儲隊列的單鏈表簡稱 鏈接隊列 或 鏈隊 。 } 隊列的鏈接存儲結(jié)構(gòu)和操作實現(xiàn) ?隊列的鏈接存儲結(jié)構(gòu)也是通過由結(jié)點構(gòu)成的單鏈表實現(xiàn)的，此時只允許在單鏈表的表頭進行刪除和在單鏈表的表尾進行插入，因此它需要使用兩個指針：隊首指針 front和隊尾指針 rear。 } /*使隊首指針指向下一個位置 */ Qfront=(Qfront+1)%QMaxSize。 } 3. 從隊列中刪除元素并返回 ElemType OutQueue(struct QueueSq* Q) { /*若隊列為空則終止運行 */ if(Qfront==Qrear) { printf(隊列已空，無法刪除 !\n)。 Qrear+=QMaxSize。 i=Qrear。 /*把原隊列的尾部內(nèi)容向后移動 MaxSize個位置 */ if(Qrear!=QMaxSize1) { int i。 exit(1)。 p=realloc(Qqueue, 2*QMaxSize*sizeof(ElemType))。 /*把 item的值賦給新的隊尾位置 */ Qqueue[Qrear]=x。 2. 向隊列插入元素 void EnQueue(struct QueueSq* Q, ElemType x) { /*當隊列滿時進行動態(tài)重分配 */ if((Qrear+1)%QMaxSize==Qfront) againMalloc(Q)。 exit(1)。 /*動態(tài)存儲空間分配，若分配失敗則退出運行 */ Qqueue=malloc(ms*sizeof(ElemType))。 exit(1)。實用中使用任一種初始化算法均可。 /*置隊列為空 */ Qfront=Qrear=0。 void InitQueue(struct QueueSq* Q) { /*置隊列空間初始最大長度為 10*/ QMaxSize=10。 /*queue數(shù)組長度 */ }。 /*指向存儲隊列的數(shù)組空間 */ int front, rear, len。 }。 ⑵ 隊列的記錄定義 隊列的順序存儲結(jié)構(gòu)同樣可以被定義在一個記錄類型中，假定該記錄類型用 QueueSq表示，則定義為： struct QueueSq { ElemType queue[MaxSize]。 /* MaxSize為已定義的常量*/ int front, rear, len。 此法優(yōu)點：僅根據(jù) front、 rear指針就可做判斷 ,算法較簡單。 ai ai+1 … … aq 0 1 2 3 4 m1 max front rear 可采取的辦法有： (1)每退隊一元素，剩余元素向隊頭方向平移 —— 費時 (2)當不能入隊時，檢查隊列中是否有空，若有則平移 —— 耗時 有效辦法：使 0單元接在 MaxSize1單元后 (邏輯上 )， 形成環(huán)形結(jié)構(gòu) —— 循環(huán)隊列 循環(huán)隊列 : ? 在循環(huán)隊列中，其存儲空間是首尾循環(huán)利用的，當隊尾指針rear指向最后一個存儲位置時，下一個所求的位置自動為數(shù)組空間的開始位置（即下標為 0的位置） m1 0 1 2 3 …… 隊列的初始狀態(tài) front rear 循環(huán)隊列的運算 設(shè) 以 Queue(0:MaxSize1)為循環(huán)隊列的存儲空間 初始隊空時， front=rear=0 入隊指針操作： rear= (rear+1)% MaxSize 退隊指針操作： front= (front+1)% MaxSize 在隊列操作時，由于有兩個指針，而且這兩個指針都會移動，因此判斷其隊空和隊滿的方法與普通的線性表的判斷方法有較大的不同，特別是在循環(huán)隊列。 順序隊列 —— 隊列的順序存儲結(jié)構(gòu)： 例 : 0 1 2 n 一、循環(huán)隊列 一般順序隊列存在的問題：假溢出。 a0 a2 a3 … an front rear 設(shè)定 : 隊首指針 front —— 指向隊頭元素的前一個位置； 元素退隊， front后移。 ? 隊列的順序存儲結(jié)構(gòu)可由一個數(shù)組和兩至三個整形變量來實現(xiàn)。 (6) 清除隊列 Q中的所有元素，使之成為一個空隊 void ClearQueue(Q)。 (4) 返回隊首元素，但不改變隊列狀態(tài) ElemType PeekQueue(Q)。 (2) 將新元素 x的值插入到隊尾 void EnQueue(Q, ElemType x)。若從此隊中刪除一個元素，此隊列變?yōu)?(b,c,d)；若接著向該隊列插入一個字符 e，則 e成為新的隊尾元素，此隊列變?yōu)?(b,c,d,e)；若接著做三次刪除操作，則隊列變?yōu)?(e)，此時只有一個元素 e，它既是隊首元素又是隊尾元素，當它被刪除后隊列變?yōu)榭铡? 隊列所針對問題：按先后順序處理 (先到先服務(wù) ) 隊列的例子 ：生活中的排隊、打印隊列、作業(yè)隊列等。向隊列中插入新元素稱為 進隊 或 入隊 ，新元素進隊后就成為新的隊尾元素；從隊列中刪除元素稱為 離隊 或 出隊 ，元素離隊后，其后繼元素就成為隊首元素。 { 隊列 隊列的定義 ? 隊列 （ queue）簡稱 隊 ，它也是一種運算受限的線性表，其限制是僅允許在表的一端進行插入，而在表的另一端進行刪除。 分析重復(fù)調(diào)用在什么條件下終止 —— 確定遞歸邊界， ? 確定遞歸調(diào)用參數(shù)，寫出遞歸調(diào)用形式。 設(shè)計步驟： ? 分析問題，歸納出解決問題的基本規(guī)律（基本操作）。 遞歸算法設(shè)計的基本方法 : 歸納項 —— 重復(fù)調(diào)用的基本操作。 /*最后把 n1個盤子由值參 b所表示的柱子搬到由值參 c所表示 的柱子上，用值參 a所表示的柱子作為過渡 */ Hanoi(n1,b,a,c)。 /*當多于一個盤子時，向下遞歸 */ else { /*首先把 n1個盤子由值參 a所表示的柱子搬到由值參 b所表示 的柱子上，用值參 c所表示的柱子作為過渡 */ Hanoi(n1,a,c,b)。 2→3。 1→3。 1→2。 B→C。 A→C。 A→B。 對于第 3步也需要遞歸完成，具體為以下 3步： () 把 B柱上的 1個圓盤直接移到此時的過渡柱 A上； () 把 B柱上剩余的 1個圓盤直接移到此時的目的柱 C上； () 把此時的過渡柱 A上的 1個圓盤直接移到此時的目的柱 C上。 n1個盤子 第 n號盤子 n1個盤子 移動盤子的基本規(guī)律（歸納）： 例如，當 A柱上有 3個圓盤，要求把它移動到 C柱上，則需要以下 3步完成： (1) 把 A柱上的 2個圓盤移到過渡柱 B上； (2) 把 A柱上剩下的 1個圓盤直接移到目的柱 C上； (3) 把過渡柱 B上的 2個圓盤移到目的柱 C上。大意是：有三個臺柱，分別編號為 A,B,C或 1,2,3；在 A柱上穿有 n個圓盤，每個圓盤的直徑均不同，并且按照直徑從大到小的次序疊放在柱子上；要求把 A柱上的 n個圓盤搬移到 C柱上， B柱可以作為過渡，并且每次只能搬動一個圓盤，同時必須保證在任何柱子上的圓盤在任何時候都要按序碼放，即大的在下，小的在上；當把若干個圓盤從一個柱子搬到另一個柱子時，第三個柱子作為過渡使用；題目要求編寫出一個算法，輸出搬動圓盤的過程。 } } } /*從當前位置 (x,y)沒有通向終點的路徑，應(yīng)返回 0*/ return 0。 /*當條件成立時，表明從 (g,h)到終點存在通路，應(yīng)輸出該位置坐標，同時返回 1結(jié)束遞歸，否則進入下一輪循環(huán)，向下一個方向試探 */ if(SeekPath(g,h)) // r2 返回點 { printf((%d,%d), ,g,h)。amp。 h=y+move[i][1]。 i4。(y==n)) return 1。 /*到達出口點返回 1結(jié)束遞歸 */ if((x==m)amp。 int SeekPath(int x,int y) /*從迷宮中坐標點 (x,y)的位置尋找通向終點 (m,n)的路徑， 若找到則返回 1，否則返回 0， (x,y)的初始值通常為 (1,1)*/ { /*i作為循環(huán)變量，代表從當前位置移到下一個位置的方向 */ int i。 （基本項） ● 已回退到入口處，未走通，結(jié)束試探 。 搜尋路徑 ： ● 若下個位置通且未試過，則前進一步，記錄走過的位置與 標志； （歸納項） ● 若下個試探位置不能走，對當前位置的下一個方向試 探；