數(shù)據(jù)結構參與命題課件第3章棧

1、 算 法 與 數(shù) 據(jù) 結 構 Algorithms and Data Structures第3章棧3.1 ADT 棧3.2 ADT棧的實現(xiàn)3.3 ADT棧的應用2011-9-291吳英杰 算 法 與 數(shù) 據(jù) 結 構 Algorithms and Data Structures3.1 ADT棧（stack）1、棧的定義和特點定義：限定僅在表首進行或刪除操作的線性表，表首棧頂，表尾棧底，不含元素的空表稱空棧特點：先進后出（FILO）或后進先出（LIFO）進棧棧頂出棧棧S=(a1,a2,an)棧底2011-9-292.ana2a1 算 法 與 數(shù) 據(jù) 結 構 Algorithms a d Data

2、Structures3.1ADT棧(Stack)2、ADT棧上定義的常用的基本運算：StackEmpty(S): 判斷棧空StackFull(S):判斷棧滿(3) StackTop(S): 返回棧頂元素(4) Push(x, S):將元素入棧(5) Pop(S):出棧，刪除并返回棧S的棧頂元素2011-9-293 算 法 與 數(shù) 據(jù) 結 構 Algorithms a d Data StructuresADT棧(Stack)3.13、棧應用的簡單例子：(1)程序編譯時的表達式或字符串的括號匹配問題。例如，算術表達式(x*(x+y)-z)，其中位置1和4處有號，而位置8和11處有右括號，滿足配對要

3、求。但算術表達式有可與之配對的對的右號。(x+y)*z)(，其中位置8處的右括號沒號，而位置9處的號沒有可與之配2011-9-294 算 法 與 數(shù) 據(jù) 結 構 Algorithms and Data Structures表達式括號匹配算法void Parenthesis(char *expr)/ 表達式括號匹配i,n;Stack ss=StackInit(); n=strlen(expr);for(i=1;idataS-top- ;void Push(StackItem x, Stack S)if( StackFull(S) Error(Stack is full); else S-data

4、+ S-top = x; 算 法 與 數(shù) 據(jù) 結 構 Algorithms and Data Structures(2)棧的數(shù)組實現(xiàn)的優(yōu)缺點優(yōu)點：所列的7個基本運算都可在O(1)的時間里完成，效率高。缺點：為了使每個棧在算法運行過程中不會溢出，通常要為每個棧預置一個較大的?？臻g。另一方面，由于各個棧的實際大小在算法運行過程中不斷變化。經(jīng)常會發(fā)生其中一個棧滿，而另一個棧空的情形，空間利用率低。2011-9-2910 算 法 與 數(shù) 據(jù) 結 構 Algorithms and Data Structures(3) 兩個棧共用一個數(shù)組利用棧底位置不變的特性，可以將2個棧的棧底分別設在數(shù)組stack的兩

5、端。然后各自向數(shù)組stack的中間伸展，如下圖所示。好處：提高空間利用率，減少棧發(fā)生上溢的可能性。2011-9-2911 算 法 與 數(shù) 據(jù) 結 構 Algorithms and Data Structures2、鏈棧用指針實現(xiàn)棧(1)鏈棧的結點類型定義：2011-9-2912typedef struct snode *slink; typedef struct snode StackItem element; slink next;StackNode; 算 法 與 數(shù) 據(jù) 結 構 Algorithms and Data Structures2、鏈棧用指針實現(xiàn)棧(2)用指針實現(xiàn)的鏈棧定義：20

6、11-9-2913typedef struct lstack *Stack; typedef struct lstackslink top; /棧頂結點指針Lstack; 算 法 與 數(shù) 據(jù) 結 構 Algorithms and Data Structures(2)入棧、出棧算法實現(xiàn)及演示：入棧算法Push.txttoptop棧底p.出棧算法Pop.txtptop棧底top.2011-9-2914返回章目錄 算 法 與 數(shù) 據(jù) 結 構 Algorithms and Data Structures3.3 棧的應用1、過程的嵌套調(diào)用：子過程子過程子過程主程序rst2011-9-2915321rsr

7、rsrtsr 算 法 與 數(shù) 據(jù) 結 構 Algorithms and Data Structures2、遞歸過程及其實現(xiàn)：遞歸：函數(shù)直接或間接的調(diào)用自身叫遞歸實現(xiàn)：建立遞歸工作棧例遞歸的執(zhí)行情況分析2011-9-2916運行結果：1，2，2，3，3，3， 算 法 與 數(shù) 據(jù) 結 構 Algorithms andwData Structuresw遞歸調(diào)用執(zhí)行情況如下：ww主程序pr(1)pr(2);w=3;pr(w) (1)結束2011-9-2917(2) 輸出：3, 3, 3(3) 輸出：2, 2返回toptoptoptop(4)0(3)1(3)1(2)2(2)2(2)2(1 )3(1)3(

8、1)3(1)332pr(0);(4)輸出：101 算 法 與 數(shù) 據(jù) 結 構 Algorithms and Data Structures棧的應用算術表達式求值1、算術表達式的定義在計算機中，表達式都是由操作數(shù)(operand)、運算符(operator)和界限符(delimiter)組成。只含二元運算符的算術表達式可定義為：表達式:=作數(shù):=作數(shù)運算符作數(shù)簡單變量|表達式常數(shù)簡單變量:=標識符例1：Exp = 3*5+(6-8/4)*7#2011-9-2919 算 法 與 數(shù) 據(jù) 結 構 Algorithms and Data Structures棧的應用算術表達式求值2、算術表達式的表示方

9、式假設 Exp = S1OPS2S1 S1OPOP S2S1S2 稱為表達式的中綴表示法（簡稱中綴式）OP 稱為表達式的后綴表示法（簡稱后綴式）S2 稱為表達式的前綴表示法（簡稱前綴式）例2：若Exp= ab+(c-d/e)后綴式為：abcde/-f+前綴式為：+ab-c/def動畫演示2011-9-2920 算 法 與 數(shù) 據(jù) 結 構 Algorithms and Data Structures棧的應用算術表達式求值2011-9-2922 算 法 與 數(shù) 據(jù) 結 構 Algorithms and Data Structures棧的應用算術表達式求值2011-9-2923 算 法 與 數(shù) 據(jù)

10、結 構 Algorithms and Data Structures棧的應用算術表達式求值3、后綴表達式求值利用棧進行后綴表達式求值的基本：(1)(2)(3)從左到右讀入后綴表達式，若讀入的是一個操作數(shù)，就將它壓入棧；若讀入的是一個運算符op，就從棧出兩個操作數(shù)，設為x和y，計算表達式x op y的值，并將計算結果壓入棧；對整個后綴表達式讀入結束時，棧頂元素就是計算結果。例4：求后綴表達式 3 56 8 4/-7+#動畫演示的值2011-9-2924 算 法 與 數(shù) 據(jù) 結 構 Algorithms and Data Structures棧的應用算術表達式求值2011-9-2927 算 法 與

11、 數(shù) 據(jù) 結 構 Algorithms and Data Structures棧的應用算術表達式求值282011-9-29 算 法 與 數(shù) 據(jù) 結 構 Algorithms and Data Structures4、地圖四染色問題7 7 (7)R (3)(4)(2)(1)(6)(5)12345672011-9-2929123 45 673#紅色4#藍色0111110100001010011001010110101101011011000000000 算 法 與 數(shù) 據(jù) 結 構 Algorithms and Data Structures5、等價類劃分問題問題的提出給定集合S及一系列形如“x等價

12、于y”的等價性條件，要求給出S的滿足所列等價性條件的等價類劃分。其中x和 y是S中的元素。復習:集合上的等價關系和集合關于某一等價關系的等價類劃分等概念;舉出3個你熟悉的等價關系和等價類劃分。2011-9-2930 算 法 與 數(shù) 據(jù) 結 構 Algorithms and Data Structures(2) 問題的數(shù)學化總可以用整數(shù)來表示集合中的元素。因此，如果集合S中共有n個元素，則可將集合S表示為，n，而元素i和j的等價性條件可表示為ij，1i，jn。這樣，問題可一般地表述為：已知S=，2，n上的個等價性條件itjt, 1it，jtn, t=1,2,3,r一個等價關系由 r來表示。要求該

13、等價關系所確定的等價類劃分。2011-9-2931 算 法 與 數(shù) 據(jù) 結 構 Algorithms and Data Structures(3) 舉例給定集合 S =1，2，7，及等價性條件：12， 56，34，14。則集合S的等價類劃分如下：首先將S的每一個元素看成一個等價類。然后順序地處理所給的等價性條件。每處理一個等價性條件，就得到一個相應的等價類劃分：12563414，；，；，；，。最終所得到的集合S的等價類劃分為：，。2011-9-2932 算 法 與 數(shù) 據(jù) 結 構 Algorithms and Data Structures6、電路板布線2011-9-2933 算 法 與 數(shù)

14、據(jù) 結 構 Algorithms a d Data Structures用深度優(yōu)先搜索的方法解布線問題。從起始位置a開始將它作為第一個搜索方格。依次從與該方格相鄰并且可達的方格中選擇一個方格成為下一個搜索方格，并將此方格作記后加入到一個棧path中，繼續(xù)向深度搜索。標一旦不能繼續(xù)搜索，算法從棧path中取出棧頂方格，搜索其下一個相鄰方格。這個過程一直繼續(xù)到算法搜索到目標方格b或棧為空時為止。2011-9-2934 算 法 與 數(shù) 據(jù) 結 構 Algorithms a d Data Structuresbool find_path(postart,pofinish)/ 搜索從起點start到終點

15、finish的布線路徑/ 找到布線路徑則返回true,否則返回falseif(start.row=finish.row)& (start.col=finish.col)return true;/ 無須搜索for(i=0;i=m+1;i+)grid0i=gridm+1i=1;/ 頂部和底部gridi0=gridim+1=1;/和右翼/ 初始化相對位移pooffset4;offset0.row=0;offset0.col=1;/ 右 offset1.row=1;offset1.col=0;/ 下 offset2.row=0;offset2.col=-1;/ 左 offset3.row=-1;off

16、set3.col=0;/ 上2011-9-2935 算 法 與 數(shù) 據(jù) 結 構 Algorithms ad Data Structurespohere;/ 當前位置here.row=start.row; here.col=start.col; gridhere.rowhere.col=1;/dir=0,dir1=3;/ 開始搜索標記while(here.row!=finish.row | here.col!=finish.col)/ 未達目標/ 找相鄰方格r,c; while(dir=dir1)r=here.row+offsetdir.row; c=here.col+offsetdir.col; if(gridrc=0)break; dir+;/ 下一方向2011-9-2936 算 法 與 數(shù) 據(jù) 結 構 Algorithms ad Data Structures/ 可達相鄰方格if(dir=dir1)/ 移至gridrcpath.push(here); here.row=r;here.col=c;gridrc=1;/