棧和隊列課件

1、第三章 棧和隊列棧 棧的存儲結(jié)構(gòu)及應(yīng)用 隊列隊列的存儲結(jié)構(gòu)及應(yīng)用棧的基本概念定 義數(shù)據(jù)元素之間是一對一的關(guān)系 順序存儲或鏈?zhǔn)酱鎯?只能在棧頂運(yùn)算，且訪問結(jié)點(diǎn)時依照后進(jìn)先出（LIFO）或先進(jìn)后出（FILO）的原則存儲結(jié)構(gòu)運(yùn)算規(guī)則邏輯結(jié)構(gòu)只能在表的一端進(jìn)行插入和刪除的線性表基本操作建棧、判斷棧滿或?？?、入棧、出棧、取棧頂元素值棧的示意圖棧是僅在表尾進(jìn)行插入、刪除操作的線性表表尾(即 an 端)稱為棧頂 (top) 表頭(即 a1 端)稱為棧底(bottom)插入元素到棧頂?shù)牟僮?，稱為入棧從棧頂刪除元素的操作，稱為出棧棧 S= (a1 , a2 , a3 , .,an-1 , an )棧頂元素棧底元

2、素插入和刪除都只在表的一端（棧頂）進(jìn)行棧的基本操作 INISTACK(S)：初始化操作。設(shè)置一個空棧S。EMPTY(S)：判棧空函數(shù)。若S為空棧，函數(shù)值為1，否則為0SIZE(S)：求棧深函數(shù)。函數(shù)值為棧中當(dāng)前的元素個數(shù)。TOP(S)：讀棧頂元函數(shù)。若棧S不空，函數(shù)值為棧頂元素，否則為空元素NULL。PUSH(S,x)：進(jìn)棧操作。將元素x插入棧S中，使x成為棧S的棧頂元素。POP(S):出棧函數(shù)。若棧S不空，函數(shù)值為棧頂元素，且從棧中刪除當(dāng)前棧頂元素，否則函數(shù)值為空元素NULL。CLEAR(S):棧置空操作。不論棧S是否為空棧，將S置為空棧35178421011001余數(shù)結(jié)果：10011十進(jìn)制

3、數(shù)轉(zhuǎn)換成二進(jìn)制數(shù)把所有的余數(shù)按出現(xiàn)的逆序排列起來（先出現(xiàn)的余數(shù)排在后面，后出現(xiàn)的余數(shù)排在前面）,十進(jìn)制數(shù)35轉(zhuǎn)換成二進(jìn)制數(shù) 將帶頭結(jié)點(diǎn)的單鏈表（a1,a2,an）逆置 棧的順序存儲結(jié)構(gòu)(順序棧)順序棧:利用一組地址連續(xù)的存儲單元依次存放從棧底到棧頂?shù)臄?shù)據(jù)元素C語言中預(yù)設(shè)較大的數(shù)組空間棧底設(shè)為0棧頂隨插入和刪除元素而變化用一個整型變量top來指示棧頂?shù)奈恢?a1 a2 an順序棧S ai0n棧底棧頂top壓入(PUSH): Stop+=an+1彈出( POP) : e=S-top順序棧存儲結(jié)構(gòu)的描述#define MAXSIZE 100 typedef int elemtype;typedef

4、struct stack elemtype elemMAXSIZE; int top； /棧頂指針sqstacktp； /順序棧類型定義sqstacktp *s； /s為順序棧類型變量的指針s=(sqstacktp *)malloc(sizeof(sqstacktp);123450棧空棧頂指針top,可初始化為0，指向?qū)嶋H棧頂后的空位置.top123450進(jìn)棧Atop出棧BCDEF設(shè)數(shù)組大小為MAXSIZEs-top=0,?？眨藭r出棧則下溢s-top= MAXSIZE,棧滿，此時入棧上溢toptoptoptoptop123450ABCDEFtoptoptoptoptoptoptop設(shè)MAXS

5、IZE=6順序棧的幾種情況?？諚Mtop順序棧上實(shí)現(xiàn)的操作初始化（棧置空）操作void ini_sqstack(sqstacktp *s)；判?？蘸瘮?shù)int empty_sqstack(sqstacktp *s)；進(jìn)棧操作void push_sqstack(sqstacktp *s，elemtype x)；出棧函數(shù)elemtype pop_sqstack(sqstacktp *s) ；求棧深函數(shù)int size_sqstack(sqstacktp *s)；讀棧頂元函數(shù)elemtype top_sqstack(sqstacktp *s)；棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)定義棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)，簡稱鏈棧組織形式與單

6、鏈表類似，鏈表的尾部是棧底，鏈表的頭部是棧頂 FtopdatanextEDANULL棧頂棧底棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)鏈棧的類型定義：typedef struct stacknode elemtype data； struct stacknode *next； stacknode;typedef struct stacknode *top; /棧頂指針linkstack;linkstack *ls;ls=(linkstack *)malloc(sizeof(linkstack);ls-top=?初始化操作void init_linkstack(linkstack *ls)； 進(jìn)棧操作void push_

7、linkstack(linkstack *ls,elemtype x)；出棧操作elemtype pop_linkstack(linkstack *ls)；鏈棧上實(shí)現(xiàn)的操作對算術(shù)表達(dá)式求值： 1 + 2 * 4 - 9 / 3遵循先乘除后加減、先左后右及先括號內(nèi)，后括號外的四則運(yùn)算法則，其計算順序應(yīng)為：1 + 2 * 4 - 9 / 3 棧的應(yīng)用實(shí)例表達(dá)式求值采用“運(yùn)算符優(yōu)先數(shù)法” 對每種運(yùn)算符賦于一個優(yōu)先數(shù)，如：運(yùn)算符： * / + - #優(yōu)先數(shù)： 2 2 1 1 0其中 # 是表達(dá)式結(jié)束符對表達(dá)式求值時，一般設(shè)立兩個棧運(yùn)算符棧（OPTR)操作數(shù)棧(OPND)分別存放表達(dá)式中的運(yùn)算符和操作數(shù)

8、 步驟 OPTR棧 OPND棧 輸入字符 主要操作 1 # 1+2*4-9/3# PUSH(OPND,1) 2 # 1 +2*4-9/3# PUSH(OPTR,+) 3 # + 1 2*4-9/3# PUSH(OPND,2) 4 # + 1 2 *4-9/3# PUSH(OPTR,*) 5 # + * 1 2 4-9/3# PUSH(OPND,4) 6 # + * 1 2 4 -9/3# operate(2,*,4) 7 # + 1 8 -9/3# operate(1,+,8) 8 # 9 -9/3# PUSH(OPTR,-) 9 # - 9 9/3# PUSH(OPND,9) 10 # -

9、9 9 /3# PUSH(OPTR,/) 11 # - / 9 9 3# PUSH(OPND,3) 12 # - / 9 9 3 # operate(9,/,3) 13 # - 9 3 # operate(9,-,3) 14 # 6 # RETURN(TOP(OPND) 利用算法對算術(shù)表達(dá)式求值的操作過程棧在回溯法中的應(yīng)用在某些問題的求解過程中常常采用試探方法，當(dāng)某一路徑受阻時，需要逆序退回，重新選擇新路徑，這樣必須用棧記錄曾經(jīng)到達(dá)的每一狀態(tài)，棧頂狀態(tài)即是回退的第一站。 地圖四染色問題“四染色”定理可以用不多于四色對地圖著色，使相鄰的地區(qū)不重色算法思想 ：“回溯”法從第一號地區(qū)開始逐一染色，每

10、一個地區(qū)逐次用色數(shù)1、2、3、4進(jìn)行試探若當(dāng)前所取的色數(shù)與周圍已染色的地區(qū)不重色，則用棧記下該地區(qū)的色數(shù)，否則依次用下一色數(shù)進(jìn)行試探若出現(xiàn)用1.4色均與相鄰地區(qū)發(fā)生重色，則需退?；厮?，修改當(dāng)前棧頂?shù)纳珨?shù)。地圖四染色問題算法實(shí)現(xiàn)“四染色”定理數(shù)據(jù)結(jié)構(gòu)graphnnn*n的關(guān)系矩陣grphij=0表示地區(qū)i與地區(qū)j不相鄰graphij=1表示地區(qū)i與地區(qū)j相鄰。colorn顏色表：順序存儲colori表示i號地區(qū)的染色數(shù)。(1)(2)(4)(5)(6)(7)(3)r 7 7 1 2 3 4 5 6 71 2 3 4 5 6 7 1 0 0 0 0 1 00 1 1 1 1 1 01 0 1 0 1

11、 1 01 0 1 1 0 1 01 1 0 1 1 0 01 0 0 1 1 0 00 0 0 0 0 0 01 2 3 4 5 6 7 1223414334231# 紫色 2# 黃色 3# 紅色 4# 綠色地圖四染色算法棧與函數(shù)調(diào)用由于程序設(shè)計都采用模塊化程序設(shè)計方法，模塊（函數(shù)、過程）是完成功能相對獨(dú)立的一個程序段，在主函數(shù)（主程序）中調(diào)用模塊來解決復(fù)雜的實(shí)際問題由于函數(shù)調(diào)用后，需返回調(diào)用處，所以，在調(diào)用時，需用棧記錄斷點(diǎn)的地址以及有關(guān)信息，以便返回。 棧的應(yīng)用-函數(shù)調(diào)用int func_B(int x,int y) int z; z=x+y; return z; int func_A(

12、) int x=10,y=20,k; k=func_B(x,y); return k;void main() printf(“%d”,func_A(); 函數(shù)調(diào)用棧與函數(shù)堆棧是存儲器的一個區(qū)域編譯器一般使用堆棧實(shí)現(xiàn)函數(shù)調(diào)用函數(shù)占用的區(qū)域被稱作函數(shù)的棧幀 函數(shù)調(diào)用時，為被調(diào)用的函數(shù)分配棧幀，存放函數(shù)的參數(shù)、局部變量等信息函數(shù)嵌套調(diào)用時，堆棧中會同時存在多個函數(shù)的棧幀，每個函數(shù)占用一個連續(xù)的區(qū)域函數(shù)獨(dú)占自己的棧幀空間當(dāng)前正在運(yùn)行的函數(shù)的棧幀總是在棧頂兩個特殊的寄存器ESP，EBP棧與函數(shù)棧幀中的信息局部變量棧幀狀態(tài)值保存前一棧幀的頂部和底部函數(shù)返回地址保存函數(shù)調(diào)用前的指令位置棧與函數(shù)r主程序srr

13、rs子過程1rst子過程2rst子過程3棧與函數(shù)調(diào)用的圖示遞歸的定義若一個對象部分地包含它自己,或用它自己給自己定義,則稱這個對象是遞歸的二叉樹是結(jié)點(diǎn)的有限集合，這個集合或者是空的，或者由一個根結(jié)點(diǎn)或兩棵互不相交的稱為左子樹的和右子樹的二叉樹組成 若一個過程直接地或間接地調(diào)用自己,則稱這個過程是遞歸的過程。 直接遞歸fun_a() fun_a() 間接遞歸fun_a() fun_b() fun_b() fun_a() 遞歸的定義遞歸條件解決問題時，可以把一個問題轉(zhuǎn)化為一個新的問題，這個新問題的解決方法，與原問題的解法相同，只是所處理的對象有所不同。這些被處理的對象之間有規(guī)律的遞增或遞減要有一個

14、明確的結(jié)束遞歸的條件，否則遞歸將會無止境地進(jìn)行下去，直到耗盡系統(tǒng)資源.必須要有終止遞歸的條件適用遞歸技術(shù)的問題以下三種情況常常用到遞歸方法定義是遞歸的數(shù)據(jù)結(jié)構(gòu)是遞歸的問題的解法是遞歸的求解階乘函數(shù)的遞歸算法long Factorial ( long n ) if ( n = 0 ) return 1; else return n * Factorial (n-1);例如，階乘函數(shù)定義是遞歸的 例如，單鏈表結(jié)構(gòu)f f 數(shù)據(jù)結(jié)構(gòu)是遞歸的一個結(jié)點(diǎn)，它的指針域?yàn)镹ULL，是一個單鏈表一個結(jié)點(diǎn)，它的指針域指向單鏈表，仍是一個單鏈表打印單鏈表最后一個結(jié)點(diǎn)的值void Print ( ListNode *f

15、 ) if ( f -link = NULL ) printf(“%dn”, f -data); else Print ( f -link );f f f f a0a1a2a3a4f 遞歸找鏈尾數(shù)據(jù)結(jié)構(gòu)是遞歸的1 3 3 21 31 22 12 31 3源中間目的 1 2 3源中間目的64個 a b cmove(n,a,b,c)move(n-1,a,c,b)a cmove(n-1,b,a,c)64個64個問題的解法是遞歸的hanoi(3,1,2,3)n=3 a=1 b=2 c=3hanoi(n-1,a,c,b); move(a,c); hanoi(n-1,b,a,c);hanoi(2,1,3,

16、2)n=2 a=1 b=3 c=2hanoi(n-1,a,c,b); move(a,c); hanoi(n-1,b,a,c);hanoi(1,1,2,3)n=1 a=1 b=2 c=3 move(a,c); 1-3 1-2 1-3hanoi(1,3,1,2)n=1 a=3 b=1 c=2move(a,c); 3-2hanoi(2,2,1,3)n=2 a=2 b=1 c=3hanoi(n-1,a,c,b); move(a,c); hanoi(n-1,b,a,c);hanoi(1,2,3,1)n=1 a=2 b=3 c=1move(a,c); 2-1 2-3hanoi(1,1,2,3)n=1 a=

17、1 b=2 c=3move(a,c); 1-3void hanoi(int n,int a,int b,int c) if( n = 1) move(a,c); else hanoi(n-1,a,c,b); move(a,c); hanoi(n-1,b,a,c); 1-3 1-2 3-2 2-1 2-3 1-3 1-3遞歸模型 遞歸是把一個不能或不好直接求解的“大問題”轉(zhuǎn)化為一個或幾個“小問題”再把這些“小問題”進(jìn)一步分解成更小的“小問題”來解決直到遞歸出口為止遞歸模型反映一個遞歸問題的遞歸結(jié)構(gòu)遞歸模型由遞歸出口和遞歸體兩部分組成前者確定遞歸到何時為止后者確定遞歸的方式 遞歸模型 遞歸出口的一般格式為f(s0)=m0這里的s0與m0均為常量，有的遞歸問題可能有幾個遞歸出口。遞歸體的一般格式為f(s)=g(f(s1), f(s2), f(sn),c1, c2,，cm)s是一個遞歸“大問題”s1, s2, sn是遞歸“小問題”c1, c2,，cm是若干個可以直接（用非遞歸方法）解決的問題g是一個非遞歸函數(shù)，反映了遞歸問題的結(jié)構(gòu)。 遞歸模型 例如，階乘函數(shù)遞歸出口遞歸體主程序 main : fact(4)參數(shù) 4 計算 4*fact(3) 參數(shù) 3 計算 3*fact(2) 參數(shù) 2 計算 2*fact(1)