數(shù)據(jù)結(jié)構(gòu)參與命題課件第3章棧

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

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

3、求。但算術(shù)表達(dá)式有可與之配對(duì)的對(duì)的右號(hào)。(x+y)*z)(，其中位置8處的右括號(hào)沒(méi)號(hào)，而位置9處的號(hào)沒(méi)有可與之配2011-9-294 算 法 與 數(shù) 據(jù) 結(jié) 構(gòu) Algorithms and Data Structures表達(dá)式括號(hào)匹配算法void Parenthesis(char *expr)/ 表達(dá)式括號(hào)匹配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ù) 結(jié) 構(gòu) Algorithms and Data Structures(2)棧的數(shù)組實(shí)現(xiàn)的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：所列的7個(gè)基本運(yùn)算都可在O(1)的時(shí)間里完成，效率高。缺點(diǎn)：為了使每個(gè)棧在算法運(yùn)行過(guò)程中不會(huì)溢出，通常要為每個(gè)棧預(yù)置一個(gè)較大的?？臻g。另一方面，由于各個(gè)棧的實(shí)際大小在算法運(yùn)行過(guò)程中不斷變化。經(jīng)常會(huì)發(fā)生其中一個(gè)棧滿(mǎn)，而另一個(gè)棧空的情形，空間利用率低。2011-9-2910 算 法 與 數(shù) 據(jù) 結(jié) 構(gòu) Algorithms and Data Structures(3) 兩個(gè)棧共用一個(gè)數(shù)組利用棧底位置不變的特性，可以將2個(gè)棧的棧底分別設(shè)在數(shù)組stack的兩

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

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

7、rsrtsr 算 法 與 數(shù) 據(jù) 結(jié) 構(gòu) Algorithms and Data Structures2、遞歸過(guò)程及其實(shí)現(xiàn)：遞歸：函數(shù)直接或間接的調(diào)用自身叫遞歸實(shí)現(xiàn)：建立遞歸工作棧例遞歸的執(zhí)行情況分析2011-9-2916運(yùn)行結(jié)果：1，2，2，3，3，3， 算 法 與 數(shù) 據(jù) 結(jié) 構(gòu) Algorithms andwData Structuresw遞歸調(diào)用執(zhí)行情況如下：ww主程序pr(1)pr(2);w=3;pr(w) (1)結(jié)束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ù) 結(jié) 構(gòu) Algorithms and Data Structures棧的應(yīng)用算術(shù)表達(dá)式求值1、算術(shù)表達(dá)式的定義在計(jì)算機(jī)中，表達(dá)式都是由操作數(shù)(operand)、運(yùn)算符(operator)和界限符(delimiter)組成。只含二元運(yùn)算符的算術(shù)表達(dá)式可定義為：表達(dá)式:=作數(shù):=作數(shù)運(yùn)算符作數(shù)簡(jiǎn)單變量|表達(dá)式常數(shù)簡(jiǎn)單變量:=標(biāo)識(shí)符例1：Exp = 3*5+(6-8/4)*7#2011-9-2919 算 法 與 數(shù) 據(jù) 結(jié) 構(gòu) Algorithms and Data Structures棧的應(yīng)用算術(shù)表達(dá)式求值2、算術(shù)表達(dá)式的表示方

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

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

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

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

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

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

15、finish的布線路徑/ 找到布線路徑則返回true,否則返回falseif(start.row=finish.row)& (start.col=finish.col)return true;/ 無(wú)須搜索for(i=0;i=m+1;i+)grid0i=gridm+1i=1;/ 頂部和底部gridi0=gridim+1=1;/和右翼/ 初始化相對(duì)位移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ù) 結(jié) 構(gòu) Algorithms ad Data Structurespohere;/ 當(dāng)前位置here.row=start.row; here.col=start.col; gridhere.rowhere.col=1;/dir=0,dir1=3;/ 開(kāi)始搜索標(biāo)記while(here.row!=finish.row | here.col!=finish.col)/ 未達(dá)目標(biāo)/ 找相鄰方格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ù) 結(jié) 構(gòu) Algorithms ad Data Structures/ 可達(dá)相鄰方格if(dir=dir1)/ 移至gridrcpath.push(here); here.row=r;here.col=c;gridrc=1;/