【正文】 ? 遞歸函數(shù)的執(zhí)行過程：在遞歸函數(shù)的執(zhí)行函數(shù)中，需多次進行自我調(diào)用。遞歸函數(shù)的運行過程類似于多個函數(shù)的嵌套調(diào)用，只是調(diào)用函數(shù)和被調(diào)用函數(shù)是同一個函數(shù)。 ? 假設(shè)調(diào)用該遞歸函數(shù)的主函數(shù)時第 0層，則從主函數(shù)調(diào)用遞歸函數(shù)為進入第 1層，從第 i層遞歸調(diào)用本函數(shù)為進入“下一層”，即第 i+1層，反之，退出第 i層遞歸應(yīng)返回上一層，即第 i1層。每一層遞歸所需信息構(gòu)成一個“工作記錄”，其中包括所有的實參、所有的局部變量以及上一層的返回地址，每進入一層遞歸，就產(chǎn)生一個新的工作記錄壓入棧頂，每退出一層遞歸，就從棧頂彈出一個工作記錄。移動圓盤需遵循如下規(guī)則： (1) 每次只能移動一個圓盤 (2) 任何時刻都不能允許將較大的圓盤壓在較小的圓盤上 (3) 在滿足移動規(guī)則 (1)和 (2)的前提下，可將圓盤移至 a,b,c中任一塔座上。 } // 將 n個棋盤從 x移到 z void hanoi (int n, char x, char y, char z ) 1 { 2 if(n==1) 3 move(x,1,z)。 //將編號 1..n1的圓盤從 x移到 y,利用 z作為輔助圓盤 //將編號為 n的圓盤從 x移到 z 6 move(x,n,z)。 8 } 9 } 福州大學(xué)至誠學(xué)院 福州大學(xué)至誠學(xué)院 福州大學(xué)至誠學(xué)院 福州大學(xué)至誠學(xué)院 隊列 ? 隊列（ Queue） :僅在隊尾進行插入和隊頭進行刪除操作的線性表，先進先出線性表 (FIFO) ? 隊頭 （ front） : 線性表的表頭端 ， 即可刪除端 。 隊頭 隊尾 ...... a1 a2 a3 an1 an 入隊列 (Enqueue) 出隊列 (Dequeque) 福州大學(xué)至誠學(xué)院 抽象數(shù)據(jù)類型隊列的定義 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,3,… ,n)} 約定 an為隊尾 , a1為隊頭 。Q)。Q)。 Q)。 QueueLength(Q) 。e)。Q,e)。Q,amp。 QueueTraverse(Q,visit ()) }ADT Queue 隊列 福州大學(xué)至誠學(xué)院 隊列的基本操作 (之一 ) ? InitQueue (amp。 ? DestroyQueue (amp。 ? 操作結(jié)果 : 銷毀隊列 Q。Q) ? 初始條件 : 隊列 Q已經(jīng)存在。 福州大學(xué)至誠學(xué)院 隊列的基本操作 (之二 ) ? QueueEmpty(Q) ?初始條件 :隊列 Q已經(jīng)存在。否則返回FALSE。 ?操作結(jié)果 :返回隊列 Q中的數(shù)據(jù)元素個數(shù) ,即隊列 Q的長度。e) ?初始條件 :隊列 Q已經(jīng)存在且非空。 福州大學(xué)至誠學(xué)院 隊列的基本操作 (之三 ) ? EnQueue (amp。 ?操作結(jié)果 : 插入元素 e為新的隊尾元素 。Q,amp。 ?操作結(jié)果 : 刪除隊列 Q 的隊頭元素并用 e返回其值 。 ?操作結(jié)果 : 從隊頭到隊尾依次對隊列 Q的每個元素調(diào)用函數(shù) visit ()。 福州大學(xué)至誠學(xué)院 鏈隊列 隊列的鏈?zhǔn)奖硎九c實現(xiàn) ? 鏈隊列：隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)簡稱為鏈隊列，它是限制僅在表頭刪除和表尾插入的單鏈表。鏈隊列無隊列滿的問題，空間可擴充。 struct QNode *next。 typedef struct { QueuePtr front。 // 隊尾指針 }LinkQueue。Q) { =(QueuePtr)malloc(sizeof(QNode) )。 if(!) return(OVERFLOW)。 return OK。Q) { while( ){ = next。 = 。 } 福州大學(xué)至誠學(xué)院 鏈隊列的操作實現(xiàn) – EnQueue //插入元素 e為新的隊尾元素 Status EnQueue(LinkQueue amp。 if(!p) return(OVERFLOW)。 p next = NULL。 = p。 } 福州大學(xué)至誠學(xué)院 鏈隊列的操作實現(xiàn) —DeQueue //刪除隊列 Q 的隊頭元素并用 e返回其值 Status DeQueue(LinkQueue amp。e) { if( == ) retrun ERROR。 e = pdata。 if( == p) = 。 return OK。 // 動態(tài)分配存儲空間 int front。 // 尾指針 ,若隊列不空指向 隊列尾元素的下一個位置 } SqQueue。 ? 實現(xiàn)：利用 “ 模 ” 運算 ? 入隊 : base[rear]=x。 ? 出隊： x=base[front]。 ? 隊滿、隊空判定條件 福州大學(xué)至誠學(xué)院 0 1 2 3 4 5 rear front J5 J6 J7 0 1 2 3 4 5 rear front J4 J9 J8 隊空： front==rear 隊滿： front==rear J5 J6 0 1 2 3 4 5 rear front 初始狀態(tài) J4 福州大學(xué)至誠學(xué)院 解決方案 ? 設(shè)一個布爾變量以區(qū)別隊列的空和滿 ? 使用一個計數(shù)器記錄隊列中元素的總數(shù) ? 少用一個元素空間，約定當(dāng)循環(huán)數(shù)組中元素個數(shù)達到maxsize1時隊列為滿，即以隊列頭指針指向隊列尾指針的下一位置（指環(huán)的下一位置 )上作為隊列呈 ” 滿 “ 的標(biāo)志 隊空： front==rear 隊滿： (rear+1)%M==front 福州大學(xué)至誠學(xué)院 循環(huán)隊列空或滿的判斷 0 1 2 3 4 5 J3 J4 J5 (a)一般隊列 0 1 2 3 4 5 (c)空隊列 J6 J3 J4 J5 0 1 2 3 4 5 J7 (b)滿隊列 福州大學(xué)至誠學(xué)院 循環(huán)隊列實現(xiàn) define MAXSIZE 100 typedef struct { QElemType *base。 // 隊頭指針 int rear。 福州大學(xué)至誠學(xué)院 循環(huán)隊列實現(xiàn) – InitQueue //初始化空隊列 Status InitQueue(SqQueue amp。 if(!) return(OVERFLOW)。 return OK。Q, QelemType e) { if((+1)% MAXSIZE == ) return(ERROR)。 = (+1) % MAXSIZE。 } 福州大學(xué)至誠學(xué)院 循環(huán)隊列實現(xiàn) – DeQueue //出隊列 Status DeQueue(SqQueue amp。e) { if( == ) retrun ERROR。 = (+1) % MAXSIZE。 } 福州大學(xué)至誠學(xué)院 寫出以下程序段的輸出結(jié)果（隊列中的元素類型 QElemType 為 char）。 InitQueue(Q)。 EnQueue(Q, ?h‘)。 EnQueue(Q, y)。 EnQueue(Q, x)。 EnQueue(Q, ?a‘)。 Printf(y)。 }