1、數(shù) 據(jù) 結(jié) 構(gòu) Data Structure,主講人： 劉 瑋,第三章 棧和隊列,棧的應(yīng)用,3.2,遞歸,3.3,3.1 棧,限定只能在表的一端進行插入和刪除操作的線性表。,3.1.1 棧的定義,其中a1為棧底元素(bottom) an為棧頂元素(top),a1,a2,an,進 棧,出 棧,top,bottom,棧頂：允許插入和刪除的一端 棧底：不允許插入和刪除的一端,特點：先進后出(LIFO),例：有三個元素按a，b，c的次序依次進棧，且每個元素只允許進一次棧，則可能的出棧序列？,c b a,c a b,a b c,a c b,b c a,b a c,3.1 棧,3.1.2 棧的抽象數(shù)據(jù)類型

2、ADT,ADT Stack 數(shù)據(jù)對象: D ai | aiElemSet, i=1,2,.,n, n0 數(shù)據(jù)關(guān)系：R1 |ai-1 ,aiD, i=2,.,n 基本操作： InitStack ( typedef struct SElemType dataSTACK_INIT_SIZE； int top； SqStack,base,top,base,top,base,top,base,top,top=0,top=1,top=2,top=4,空棧,棧滿,1、順序棧,3) 基本操作的實現(xiàn) 棧的初始化 進棧（PUSH） 出棧（POP）, 棧的初始化 算法思想：構(gòu)造一個空棧，設(shè)置棧的參數(shù),Status

3、InitStack(SqStack , 進棧（PUSH） 算法思想 首先判斷棧滿？ 若棧滿，則不能進棧操作; 數(shù)據(jù)元素入棧; 棧頂指針加1。,top,a6,base,Status Push(SqStack *(S.top+)=e； return OK； ,1、順序棧, 出棧（POP） 算法思想 首先判斷?？?？ 棧頂指針減1，數(shù)據(jù)元素出棧,top,a6,Status Pop(SqStack return OK； ,2、鏈棧,1）存儲特點 是一種特殊形式的單鏈表（插入、刪除操作限定在表一端進行） 鏈?zhǔn)綏o棧滿問題，空間可擴充,2、鏈棧,2) 鏈棧的表示（C語言描述）,typedef struct

4、int len； SNode *top； LStack；,typedef struct SNode SElemType data； struct SNode *next； SNode；,進棧（PUSH）,. . .,top,p=(SNode *)malloc(sizeof(SNode);,p,e,p-data = e;,p-next = top;,top = p;,top,出棧（POP）,. . .,top,e = p-data;,S.top = p-next;,free(p);,p = S.top;,if(!StackEmpty(S) return ERROR;,p,e,top,順序棧和鏈棧

5、的比較,時間性能: 相同，都是常數(shù)時間O(1)。,空間性能：,順序棧:有元素個數(shù)的限制和空間浪費的問題。 鏈棧：沒有棧滿的問題，只有當(dāng)內(nèi)存沒有可用空間時才會出現(xiàn)棧滿，但是每個元素都需要一個指針域，產(chǎn)生結(jié)構(gòu)性開銷。,總之，當(dāng)棧的使用過程中元素個數(shù)變化較大時或不清楚棧元素個數(shù)時，用鏈棧適宜；反之，應(yīng)該采用順序棧。,3.2 棧的應(yīng)用,3.2.1 數(shù)制轉(zhuǎn)換問題,對于輸入的任意一個非負(fù)十進制整數(shù)，打印輸出與其等值的N進制數(shù)。,原理：即用該十進制數(shù)值除以n，并保留其余數(shù)；重復(fù)此操作，直到該十進制數(shù)值為0。最后將所有的余數(shù)反向輸出就是所對應(yīng)的N進制數(shù)值。,（692）10 = （1010110100）2,（1

6、59）10 = （237）8,例：把十進制數(shù)159轉(zhuǎn)換成八進制數(shù)。,void Decimal_Binary() ListStack S; InitStack( printf(“%d”,data) ,3.2.2 回文游戲（順讀與逆讀字符串一樣）,算法思想:,讀入字符串； 去掉空格（原串）； 壓入棧 原串字符與出棧字符依次比較；,若不等，非回文； 若直到?？斩枷嗟?，則為回文。,3.2.3 括號匹配的檢驗,括號匹配檢驗算法，即檢查表達式或者語句中的 , ,( )等括號是否成對出現(xiàn)。其算法是各種編譯器中的基本組成部分。,例如：表達式 a=a+b-(d-c(b+d),設(shè)置一個工作棧,工作棧stack,依

7、次讀入表達式中的每個字符,若是左括號（(,），則將其入棧； 若是右括號（），）：,若工作棧stack為空棧，則錯誤返回； 若工作棧stack不為空：若棧頂元素與當(dāng)前字符不匹配則錯誤退出；否則將棧頂元素出棧；,算法思想：,表達式讀取完畢，若棧非空則錯誤退出；,3.2.4 表達式求值,表達式的組成：,操作數(shù)（operand）：常數(shù)、變量。 運算符（operator）: 算術(shù)運算符、關(guān)系運算符和邏輯運算符。 界限符（delimiter）：左右括弧和表達式結(jié)束符。,算術(shù)運算的規(guī)則：,先乘除后加減 先左后右 先括弧內(nèi)后括弧外,例：4+2*3-10/5 =4+6-10/5 =10-10/5 =10-2 =

8、8,設(shè)置兩個工作棧,運算符棧OPTR，運算符棧的棧底為表達式的起始符#。 操作數(shù)棧OPND，操作數(shù)為空棧。,依次讀入表達式中的每個字符,若是操作數(shù)則進OPND棧； 若是運算符，則和OPTR中的棧頂元素做比較在操作。,若運算符優(yōu)先級高于OPTR中的棧頂元素，則運算符入棧； 若運算符優(yōu)先級低于OPTR中的棧頂元素，則從OPND棧頂彈出兩個操作數(shù)，與OPTR中的棧頂元素做運算，并將運算結(jié)果入OPND； 若運算符優(yōu)先級等于OPTR中的棧頂元素，則將OPTR中的棧頂元素出棧。,算法思想：,直至表達式求值完畢。,例：計算2+4-3*6,OperandType Evaluate_Expression() I

9、nitStack(OPTR); Push(OPTR,#); InitStack(OPND); c = getchar(); while(c!=# | GetTop(OPTR)!=#) if(!In(c,OP) Push(OPND,c); c=getchar(); else switch (Precede(GetTop(OPTR),c) case : Pop(OPTR,theta); break; Pop(OPND,b); Pop(OPND,a); Push(OPND，Operate(a,theta,b); break; /switch return GetTop(OPND); ,3.2.5 迷

10、宮求解,1,2,3,4,5,6,7,8,9,10,y,x,算法思想：,當(dāng)一個函數(shù)在運行期間調(diào)用另一個函數(shù)時，在運行該被調(diào)用函數(shù)之前，需先完成三件事：,將所有的實參、返回地址等信息傳遞給被調(diào)用函數(shù)保存； 為被調(diào)用函數(shù)的局部變量分配存儲區(qū)； 將控制轉(zhuǎn)移到被調(diào)用函數(shù)的入口。,而從被調(diào)用函數(shù)返回調(diào)用函數(shù)之前，應(yīng)該完成：,保存被調(diào)用函數(shù)的計算結(jié)果； 釋放被調(diào)用函數(shù)的數(shù)據(jù)區(qū)； 依照被調(diào)函數(shù)保存的返回地址將控制轉(zhuǎn)移到調(diào)用函數(shù)。,由于函數(shù)的運行規(guī)則是：后調(diào)用先返回，因此各函數(shù)占有的存儲管理應(yīng)實行“棧式管理”。,3.2.6 函數(shù)的調(diào)用,3.3 遞歸,3.3.1 遞歸的概念,遞歸的定義 若一個對象部分地包含它自己

11、, 或用它自己給自己定義, 則稱這個對象是遞歸的；若一個過程直接地或間接地調(diào)用自己, 則稱這個過程是遞歸的過程。 以下三種情況常用到遞歸方法。 定義是遞歸的 數(shù)據(jù)結(jié)構(gòu)是遞歸的 問題的解法是遞歸的,3.3 遞歸,3.3.2 定義遞歸,求解階乘函數(shù)的遞歸算法 long Factorial ( long n ) if ( n = 0 ) return 1; else return n*Factorial (n-1); ,例如，階乘函數(shù),3.3 遞歸,3.3.3 數(shù)據(jù)結(jié)構(gòu)遞歸,某些數(shù)據(jù)結(jié)構(gòu)就是遞歸的。例如，鏈表就是一種遞歸的數(shù)據(jù)結(jié)構(gòu)。鏈表結(jié)點LNode的定義由數(shù)據(jù)域data和指針域next組成；而指針

12、域next則又由LNode定義。,不僅單鏈表，廣義表、樹和圖也都是遞歸結(jié)構(gòu)。所以關(guān)于它們的一些算法，也需要用遞歸思想實現(xiàn)。,3.3 遞歸,3.3.4 解法遞歸,有些問題只能用遞歸方法來解決，若不用遞歸就只能用枚舉法了。,一個典型的例子就是“Tower of Hanoi”問題：婆羅門神廟里有一個塔臺，臺上有3根柱子(假設(shè)叫x,y,z)。在x柱上有64個金盤，每一個都比下面的小。把x柱上的金盤全部移到z柱上，移動的條件是：一次只能移動一個金盤，移動過程中大盤子只能放在小盤子下面。,漢諾塔(Tower of Hanoi)問題,有A、B、C三個塔座，A上套有n個直徑不同的圓盤，按直徑從小到大疊放，形如

13、寶塔，編號1,2,3n。要求將n個圓盤從A移到C，疊放順序不變，移動過程中遵循以下原則：,每次只能移動一個圓盤； 圓盤可在三個塔座上任意移動； 任何時刻，每個塔座上不能將大盤壓倒小盤上。,算法思想,n=1時，直接把圓盤從A移到C。,把上面n-1個圓盤從A移動到B； 然后將n號盤從A移到C； 將n-1個盤從B移到C。,n1時，,即把求解n個圓盤的Hanoi問題轉(zhuǎn)化為求解n-1個圓盤的Hanoi問題，依次類推，直至轉(zhuǎn)化成只有一個圓盤的Hanoi問題。,main() int m; printf(“Input number of disks”); scanf(“%d”, (8) (9),遞歸的思想,我

14、們把這種解決問題的“先分解再求解”的策略稱為“分而治之”(divide and conquer)的策略，簡稱“分治法”。一個問題如能用“分治法”解決，就可以用遞歸算法實現(xiàn)。,前面看到的階乘函數(shù)、冪函數(shù)、單鏈表的、漢諾塔等問題的求解過程都蘊含著分而治之或先分解再求解的思想，因此都能用遞歸方法解決。而在其他學(xué)科中，如“運籌學(xué)”和“現(xiàn)代控制論”中的“動態(tài)規(guī)劃”也是采用了分治的思想。,遞歸的結(jié)構(gòu),遞歸本身具有一定的特點，它是自己調(diào)用自己的過程，只不過每次調(diào)用時，問題的規(guī)模更小而已。,任何一個遞歸函數(shù)都由兩部分組成,初始情況：又叫結(jié)束條件或終止條件，即可以直接解決而無需再做遞歸的簡單輸入,遞歸部分：包含

15、對本算法的遞歸調(diào)用，但每次調(diào)用時傳遞進去的參數(shù)較上次調(diào)用時傳遞進去的參數(shù)更接近于初始情況。,遞歸函數(shù)的基本結(jié)構(gòu)就非常清晰了，它是一個if-else結(jié)構(gòu)。,3.4 隊列,限定只能在表的一端進行插入，在表另一端進行刪除。,3.4.1 隊列的定義,約定其中a1為隊頭元素(front) an為隊尾元素(rear),隊尾：允許插入的一端 隊頭：允許刪除的一端,特點：先進先出(FIFO),出隊列,入隊列,隊頭,隊尾,3.4 隊列,3.4.2 隊列的抽象數(shù)據(jù)類型ADT,ADT Queue 數(shù)據(jù)對象: D ai | aiElemSet, i=1,2,.,n, n0 數(shù)據(jù)關(guān)系：R1 |ai-1 ,aiD, i=

16、2,.,n 基本操作： InitQueue ( struct Qnode *next; Qnode,*Queueptr;,鏈隊列類型 typedef struct Queueptr front; Queueptr rear; LinkQueue;,1、鏈隊列,基本操作的實現(xiàn) 構(gòu)造隊列,1、鏈隊列,入隊列 分析 首先為插入隊列元素p分配空間； 為插入隊列元素賦值； 數(shù)據(jù)元素入隊尾 Q.rear-next = p; Q.rear = p;,p,1、鏈隊列,出隊列 分析 首先判斷隊列是否為空？ 刪除隊頭第一個元素； p = Q.front-next; Q.front-next = p-next; 若

17、只有一個元素，刪除后為空隊列， 需修改隊尾指針； Q.rear = Q.front;,2、線性隊列,1）存儲特點 利用地址連續(xù)的存儲單元依次存放隊列各元素。 設(shè)置兩個指示器 front, rear 分別指示隊頭、隊尾。 2）線性隊列的表示,#define MAXQSIZE 100 typedef struct QElemtyope *base; int front; int rear; SqQueue;,2、線性隊列,存在問題：“假溢出”現(xiàn)象！,解決方法：循環(huán)隊列,front,rear,G,3、循環(huán)隊列,1）存儲特點 同上,存儲隊列的數(shù)組被當(dāng)作首尾相接的表處理。 隊頭、隊尾指針加1時從 Max

18、Size -1直接進到0，可用C語言的取模(余數(shù))運算實現(xiàn)。,補充：,出隊:隊頭指針進1 front = (front + 1) % MaxSize; 入隊:隊尾指針進1 rear = (rear + 1) % MaxSize; 隊列初始化：front=rear= 0;,3、循環(huán)隊列,隊空條件：,(rear + 1) % MaxSize = front ;,front = rear ;,B,A,C,D,E,F,front,rear,隊滿條件：,rear,3、循環(huán)隊列,2）循環(huán)隊列的表示,#define MAXQSIZE 100 typedef struct QElemtyope *base; int front; int rear; SqQueue;,3、循環(huán)隊列,3）基本操作的實現(xiàn), 初始化（置空隊）,算法, 入隊（插入）,算法, 出隊（刪除）,算法,循環(huán)隊列和鏈隊列的比較,時間性能: 相