【正文】 } Printf(x)。 While ( !QueueEmpty(Q) ){ DeQueue(Q, y)。 DeQueue(Q, x)。 DeQueue(Q, x)。 EnQueue(Q, ?r‘)。 Char x=?e‘, y=?c‘。 void main( ){ Queue Q。 return OK。 e = []。Q, QelemType amp。 return OK。 [] = e。 } 福州大學至誠學院 循環(huán)隊列實現(xiàn) – EnQueue //入隊列 Status EnQueue(SqQueue amp。 = = 0。Q) { =(QElemType*)malloc(sizeof(QElemType)*MAXSIZE )。 // 隊尾指針 } SqQueue。 // 存儲空間基地址 int front。 front=(front+1)%M。 rear=(rear+1)%M。 福州大學至誠學院 1 2 3 4 5 0 空隊列 rear=0 front=0 J1 J2 J3 rear rear 1 2 3 4 5 0 J4,J5,J6入隊 J4 J5 J6 front rear rear 1 2 3 4 5 0 front J1,J1,J3入隊 rear 1 2 3 4 5 0 J1,J2,J3出隊 J1 J2 J3 front front front front ?存在問題： ?當 front=0,rear=M時再有元素入隊發(fā)生溢出 ——真溢出 ?當 front≠0,rear=M 時再有元素入隊發(fā)生溢出 ——假溢出 rear 福州大學至誠學院 ? 解決方案 ?隊首固定，每次出隊剩余元素向下移動 ——浪費時間 ?循環(huán)隊列 ? 基本思想：把隊列 設想成環(huán)形 ，讓 sq[0]接在 sq[M1]之后，若 rear+1==M,則令 rear=0。 // 頭指針，若隊列不空，指向隊列頭元素 int rear。 } 福州大學至誠學院 循環(huán)隊列－隊列的順序表示和實現(xiàn) define MAXQSIZE 100 //最大隊列長度 typedef struct { QElemType *base。 free(p)。 next = pnext。 p = next。Q, QelemType amp。 return OK。 next = p。 pdata = e。Q, QelemType e) { p = ( QueuePtr )malloc(sizeof(QNode))。 } return OK。 free()。 } // InitQueue 福州大學至誠學院 鏈隊列的操作實現(xiàn) – DestroyQueue //銷毀隊列 Q Status DestroyQueue(LinkQueue amp。 next = NULL。 = 。 data *next front rear front x入 隊 ^ x front rear y入 隊 x ^ y front rear y出 隊 ^ next=p =p p= next next = p next free(p) p rear rear p front rear x出 隊 ^ x y If( ==p) = 福州大學至誠學院 鏈隊列的操作實現(xiàn) —InitQueue //構造一個空的隊列 Q Status InitQueue(LinkQueue amp。 // 隊頭指針 QueuePtr rear。 }Qnode, *QueuePtr。 a1 ∧ an … ∧ 空隊列 福州大學至誠學院 typedef struct QNode{ QElemType data。顯然僅有單鏈表的頭指針 (front)不便于在表尾做插入操作，為此再增加一個尾指針 (rear)，指向鏈表的最后一個結點。 一旦 visit ()失敗 ， 則操作失敗 。 ? QueueTraverse(Q,visit ()) ?初始條件 : 隊列 Q已經(jīng)存在且非空 。e) ?初始條件 : 隊列 Q已經(jīng)存在且非空 。 ? DeQueue (amp。Q,e) ?初始條件 : 隊列 Q已經(jīng)存在 。 ?操作結果 :用 e返回隊列 Q中隊頭元素的值。 ? GetHead(Q,amp。 ? QueueLength(Q) ?初始條件 :隊列 Q已經(jīng)存在。 ?操作結果 :若隊列 Q為空隊列 ,則返回 TURE。 ? 操作結果 : 將隊列 Q重置為空隊列。 ? ClearQueue (amp。Q) ? 初始條件 : 隊列 Q已經(jīng)存在。Q) ? 操作結果 :構造一個空的隊列 Q。e)。 DeQueue (amp。 EnQueue (amp。 GetHead(Q,amp。 QueueEmpty(Q)。 ClearQueue (amp。 DestroyQueue (amp。 基本操作： InitQueue(amp。 ? 隊尾 （ rear） : 線性表的表尾端 ， 即可插入端 。 //將編號 1..n1的圓盤從 y移到 z,利用 x為輔助圓盤 7 hanoi(n1,y,x,z)。 4 else { 5 hanoi(n1,x,z,y)。 福州大學至誠學院 void main() { hanoi(3,‘a(chǎn)‘,‘b‘,‘c‘)。 福州大學至誠學院 ? 遞歸問題舉例 Hanoi塔問題：設 a,b,c是三個塔座，開始時在塔座 a上有一疊共 n個圓盤，這些圓盤自下而上，由大到小疊在一起，各圓盤從小到大編號為 1,2,…,n, 現(xiàn)要求將塔座 a上的這一疊圓盤移到塔座 c上，并按同樣順序疊置。為保證遞歸函數(shù)正確執(zhí)行，系統(tǒng)設立一個“遞歸工作?！弊鳛檎麄€遞歸函數(shù)運行期間使用的數(shù)據(jù)存儲區(qū)。因此，和每次調(diào)用相關的一個重要概念時遞歸函數(shù)運行的層次。調(diào)用函數(shù)和被調(diào)用函數(shù)之間的鏈接和信息交換需通過棧來進行。 福州大學至誠學院 ? 遞歸 :直接或間接調(diào)用自身的算法稱為遞歸算法，用函數(shù)自身給出定義的函數(shù)稱為遞歸函數(shù)。(3)依照被調(diào)函數(shù)保存的返回地址將控制轉移到調(diào)用函數(shù)。 (3) 將控制轉移到被調(diào)函數(shù)的入口 ? 從被調(diào)用函數(shù)返回調(diào)用函數(shù)之前，系統(tǒng)需要完成以下工作(1)保存被調(diào)函數(shù)的計算結果 。 } 對算術表達式 3*(72)求值 ? 步驟 OPTR棧 OPND棧 輸入字符 主要操作 ? 1 3 * ( 7 2 ) Push(OPND,‘3‘) ? 2 3 * ( 7 2 ) Push(OPTR,‘*‘) ? 3 * 3 ( 7 2 ) Push(OPTR,‘(‘) ? 4 * ( 3 7 2 ) Push(OPND,‘7‘) ? 5 * (