【正文】 組來表示。 棧的順序存儲結(jié)構(gòu)定義如下： ＃define TRUE 1＃define FALSE 0typedef struct { SElemType * base。 SElemType *top。 int stacksize。 //棧可使用的最大容量} Sqstack。 按初始分配量進行第一次存儲分配，base為棧底指針，始終指向棧底。top為棧頂指針，初值指向棧底，每插入一個元素，top增1；每刪除一個元素，top減1，top始終在棧頂元素的下一個位置上。 順序?；静僮鞯膶崿F(xiàn)如下:(1) 初始化。 Status InitStack (SqStack amp。S){ =(SElemType *)malloc (STACK_INIT_SIZE *sizeof(SElemType))。If (! ) exit (OVERFLOW)。=。 =STACK_INIT_SIZE。return OK。}(2) 取棧頂元素 Status GetTop(SqStack S, SElemType amp。e){ if ( == ) return ERROR。 e= * ()。 return OK。}(3) 入棧。 Status Push(SqStack amp。S, SElemType e){if ( = ){=(SElemType*)realloc(,(+STACKINCREMENT)*sizeof(SElemType))。if(!) exit(OVERFLOW)。=+。+=STACKINCREMENT。}*++=e。 return OK。} (4) 出棧 Status Pop(SqStack amp。S, SelemType amp。e){ If( ==) return ERROR。 e=*。 return OK。}在棧的共享技術(shù)中最常用的是兩個棧的共享技術(shù)：它主要利用了?！皸５孜恢貌蛔儯鴹ｍ斘恢脛討B(tài)變化”的特性。首先為兩個棧申請一個共享的一維數(shù)組空間S［M］，將兩個棧的棧底分別放在一維數(shù)組的兩端，分別是0，M1。 由于兩個棧頂動態(tài)變化，這樣可以形成互補，使得每個棧可用的最大空間與實際使用的需求有關(guān)。由此可見，兩棧共享比兩個棧分別申請M/2的空間利用率高。2. 鏈棧 棧的應(yīng)用舉例 1. 數(shù)制轉(zhuǎn)換 假設(shè)要將十進制數(shù)N轉(zhuǎn)換為d進制數(shù)，一個簡單的轉(zhuǎn)換算法是重復下述兩步，直到N等于零： X = N mod d (其中mod為求余運算)N = N div d (其中div為整除運算) 如(1348)10=(2504)8 void conversion(){ InitStack(S)。 scanf(“%d”,amp。N)。 while(N) { Push(s, N % 8 )。 N=N / 8。 } while( !StackEmpty) { Pop(S,e)。 printf(“%d”,e)。 }} 算法：作業(yè)1：1：、2：P47：?；静僮鞯乃惴枋觥ⅰ?4課時……………………………4. 迷宮求解拓展：填充算法 棧與遞歸的實現(xiàn) 棧非常重要的一個應(yīng)用是在程序設(shè)計語言中用來實現(xiàn)遞歸。 遞歸是指在定義自身的同時又出現(xiàn)了對自身的調(diào)用。 如果一個函數(shù)在其定義體內(nèi)直接調(diào)用自己，則稱其為直接遞歸函數(shù)；如果一個函數(shù)經(jīng)過一系列的中間調(diào)用語句， 通過其它函數(shù)間接調(diào)用自己，則稱其為間接遞歸函數(shù)。 1. 遞歸特性問題 1) 遞歸函數(shù)例如， 很多數(shù)學函數(shù)是遞歸定義的， 如二階Fibonacci數(shù)列： 遞歸過程的實現(xiàn) 一個函數(shù)調(diào)用另一個函數(shù)時，在運行被調(diào)用函數(shù)之前，系統(tǒng)做的工作有： (1) 保留本層參數(shù)與返回地址（將所有的實在參數(shù)、 返回地址等信息傳遞給被調(diào)用函數(shù)保存）；  (2) 給下層參數(shù)賦值（為被調(diào)用函數(shù)的局部變量分配存儲區(qū)）； (3) 將程序轉(zhuǎn)移到被調(diào)函數(shù)的入口。 而從被調(diào)用函數(shù)返回調(diào)用函數(shù)之前，系統(tǒng)也應(yīng)完成三件工作：  (1) 保存被調(diào)函數(shù)的計算結(jié)果；  (2) 恢復上層參數(shù)（釋放被調(diào)函數(shù)的數(shù)據(jù)區(qū)）；  (3) 依照被調(diào)函數(shù)保存的返回地址， 將控制轉(zhuǎn)移回調(diào)用函數(shù)。 當多個函數(shù)調(diào)用時按后調(diào)用先返回的原則。 例 求n的階乘＃include lang fac(int n){ lang L。 if(!n) L=1。 else L=n*fac(n1)。 return L。} int main(){ int n。 lang L。 scanf(“%d”,amp。n)。 L=fac(n)。 printf(“%ld”,L)。} 例32：n階Hanoi塔問題：假設(shè)有三個分別命名為X、Y和Z的塔座， 在塔座X上插有n個直徑大小各不相同、依小到大編號為1， 2, …， n的圓盤?，F(xiàn)要求將X軸上的n個圓盤移至塔座Z上并仍按同樣順序疊排，圓盤移動時必須遵循下列原則： (1) 每次只能移動一個圓盤；  (2) 圓盤可以插在X、 Y和Z中的任何一個塔座上； (3) 任何時刻都不能將一個較大的圓盤壓在較小的圓盤之上。 如何實現(xiàn)移動圓盤的操作呢？當n=1時，問題比較簡單，只要將編號為1的圓盤從塔座X直接移動到塔座Z上即可；當n1時， 需利用塔座Y作輔助塔座， 若能設(shè)法將壓在編號為n的圓盤上的n1個圓盤從塔座X(依照上述原則)移至塔座Y上， 則可先將編號為n的圓盤從塔座X 移至塔座Z上，然后再將塔座Y上的n1個圓盤(依照上述原則)移至塔座Z上。而如何將n1個圓盤從一個塔座移至另一個塔座問題是一個和原問題具有相同特征屬性的問題，只是問題的規(guī)模小個1，因此可以用同樣方法求解。 由此可得如下算法所示的求解n階Hanoi塔問題的函數(shù)。 void hanoi(int n,char x,char y,char z) /*將塔座X上按直徑由小到大且至上而下編號為1至n的n個圓盤按規(guī)則搬到塔座Z上， Y可用作輔助塔座 */ 1 {2 if(n==1) 3 move(x,1,z)。 /* 將編號為1的圓盤從X移動Z */4 else { 5 hanoi(n1,x,z,y)。 /* 將X上編號為1至n1的圓盤移到Y(jié),Z作輔助塔 */ 6 move(x,n,z)。 /* 將編號為n的圓盤從X移到Z */ 7 hanoi(n1,y,x,z)。 /* 將Y上編號為1至n1的圓盤移動到Z， X作輔助塔 */8 } 9 }  算法：下面給出三個盤子搬動時hanoi(3, A, B, C) 遞歸調(diào)用過程： hanoi(2,A,C,B): hanoi(1,A,B,C) move(AC) 1號搬到C move(AB) 2號搬到B hanoi(1,C,A,B) move(CB) 1號搬到B move(Ac) 3號搬到C hanoi(2,B,A,C): hanoi(1,B,C,A) move(BA) 1號搬到A move(Bc) 2號搬到C hanoi(1,A,B,C) move(AC) 1號搬到C 3) 遞歸問題的優(yōu)點 通過上面的例子可看出，遞歸既是強有力的數(shù)學方法， 也是程序設(shè)計中一個很有用的工具。其特點是對遞歸問題描述簡捷，結(jié)構(gòu)清晰，程序的正確性容易證明。 4) 遞歸算法求解問題的要素 遞歸算法就是算法中有直接或間接調(diào)用算法本身的算法。 遞歸算法的要點如下：  (1) 問題具有類同自身的子問題的性質(zhì)， 被定義項在定義中的應(yīng)用具有更小的尺度。  (2) 被定義項在最小尺度上有直接解。 設(shè)計遞歸算法的方法是：  (1) 尋找方法，將問題化為原問題的子問題求解（例n!=n*(n1)!）。 (2) 設(shè)計遞歸出口，確定遞歸終止條件 (例求解n!時，當n=1時，n! =1)。 作業(yè)2：1：2：、種子填充算法、兩種算法求解n!……………………………第56課時…………………………… 隊 列 隊列的定義 隊列 (Queue)是另一種限定性的線性表，它只允許在表的一端插入元素，而在另一端刪除元素，所以隊列具有先進先出(Fist In Fist Out， 縮寫為FIFO)的特性。在隊列中，允許插入的一端叫做隊尾(rear)，允許刪除的一端則稱為隊頭(front)。 假設(shè)隊列為q=(a1，a2，…，an)，那么a1就是隊頭元素，an則是隊尾元素。隊列中的元素是按照a1，a2，…，an的順序進入的， 退出隊列也必須按照同樣的次序依次出隊，也就是說，只有在a1，a2，…，an1都離開隊列之后，an才能退出隊列。 數(shù)據(jù)元素：可以是任意類型的數(shù)據(jù)，但必須屬于同一個數(shù)據(jù)對象。  關(guān)系： 隊列中數(shù)據(jù)元素之間是線性關(guān)系。  基本操作：  （1） InitQueue(amp。Q)： 初始化操作。 設(shè)置一個空隊列。 （2） QueueEmpty(Q)： 判空操作。 若隊列為空， 則返回TRUE， 否則返回FALSE。  （3）EnQueue(amp。Q，e)：進隊操作。在隊列Q的隊尾插入e。 （4） DeQueue(amp。Q,amp。e)： 出隊操作。使隊列Q的隊頭元素出隊， 并用e帶回其值。 （5） ClearQueue(amp。Q)： 隊列置空操作。 將隊列Q置為空隊列。  （6） DestroyQueue(amp。Q)： 隊列銷毀操作。 釋放隊列的空間。 隊列的表示和實現(xiàn) 鏈隊列 鏈隊列可以定義如下： ＃define TRUE 1＃define FALSE 0typedef struct Qnode{ QElemType data。 Struct Qnode *next。} Qnode, *QueuePtr。typedef struct{ QueuePtr front。 QueuePtr rear。} LinkQueue。（1） 初始化操作。 Status InitQueue(LinkQueue amp。Q){ = = (Queueptr) malloc(sizeof(Qnode))。 if(!) exit ( OVERFLOW)。 next = NULL。 return OK。} （2）銷毀隊列Status DestroyQueue(LinkQueue amp。Q){ while() { = next。 free ()。 = 。 } return OK。}（3） 入隊操作。 Status EnQueue (LinkQueue amp。Q, QelemType e){ p= (QueuePtr) malloc(sizeof(Qnode))。 if (!p) exit ( OVERFLOW)。 pdata = e。 pnext = NULL。 next =p。 = p。 return OK。}（4） 出隊操作。 Status DeQueue (LinkQueue amp。Q, QelemType amp。e){ If ( Qfront == ) return ERROR。 p=next。 e=pdata。 next =pnext。 If ( == p) = 。 free(p)。 return OK。}：循環(huán)隊列 頭、尾指針和隊列元素之間的關(guān)系 循環(huán)隊列的頭尾指針如何區(qū)分隊列“空”和“滿”1. 另設(shè)一個標志位以區(qū)分隊列是空還是滿；2. 少用一個元素空間，當隊列頭指針在隊列尾指針的下一個位置上時為“滿”。=；+1= 循環(huán)隊列滿足條件 (+1)%MAXQSIZE== 隊滿 循環(huán)隊列的類型定義： define MAXQSIZE 100 /*隊列的最大長度*/typedef struct { QElemType *base。 /* 隊列的元素空間*/ int front。