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