武漢軟件工程職業(yè)學(xué)院《數(shù)據(jù)結(jié)構(gòu)講義》第09講-棧的應(yīng)用

1、第九講棧的應(yīng)用將十進制數(shù) 轉(zhuǎn)換方法如下：N3467433546所以：(3456)N % 8 (求余)316610我們看到所轉(zhuǎn)換的N / 8 (整除)4335460=(6563) 88進制數(shù)按底位到高位的順序產(chǎn)生的，而通常的輸出是從高位到低1 鞏固棧的定義及表示。2 掌握棧的應(yīng)用方法，理解棧的重要作用教學(xué)重點：利用棧實現(xiàn)表達(dá)式求值教學(xué)難點：利用棧實現(xiàn)表達(dá)式求值授課內(nèi)容3. 1.4 棧的應(yīng)用舉例由于棧的“先進先出”特點，在很多實際問題中都利用棧做一個輔助的數(shù)據(jù)結(jié)構(gòu)來進 行求解，下面通過幾個例子進行說明?！纠?.1】簡單應(yīng)用：數(shù)制轉(zhuǎn)換問題N轉(zhuǎn)換為r進制的數(shù)，其轉(zhuǎn)換方法利用輾轉(zhuǎn)相除法：以N=3456

2、, r=8為例typedef int datatype;void con vers ion (i nt N , int r) SeqStack s;datetype x;In it_SeqStack(&s);位的，恰好與計算過程相反，因此轉(zhuǎn)換過程中每得到一位8進制數(shù)則進棧保存，轉(zhuǎn)換完畢后依次出棧則正好是轉(zhuǎn)換結(jié)果。算法思想如下：當(dāng) N>0時重復(fù)1, 21 .若N豐0，則將N % r壓入棧s中，執(zhí)行2;若N=0 ,將棧s的內(nèi)容依次出棧，算 法結(jié)束。2. 用N / r代替N算法如下：#defi ne L10void conversion(int N , int r) int sL,to

3、p;/*定義一個順序棧*/int x;top =-1;/*初始化棧*/ Push_SeqStack ( &s , N % r ); N=N / r;while( Empty_SeqStack( & s ) Pop_SeqStack (&s , &x );printf ( “d ”，x );算法3.1(a)算法3.1(a)是將對棧的操作抽象為模塊調(diào)用, s+top=N%r;/* 余數(shù)入棧 */N=N / r ;/*商作為被除數(shù)繼續(xù)*/while (top!=-1) x=stop-;printf(“ d' ,x);算法3.1(b)使問題的層次更加清楚。而算法

4、3.1(b)中的直接用int向量S和int變量top作為一個棧來使用，往往初學(xué)者將棧視為一個很復(fù)雜的東西，不知道如何使用，通過這個例子可以消除棧的“神秘”，當(dāng)應(yīng)用程序中需要一個與數(shù) 據(jù)保存時相反順序使用數(shù)據(jù)時，就要想到棧。通常用順序棧較多，因為很便利。在后面的例子中，為了在算法中表現(xiàn)出問題的層次，有關(guān)棧的操作調(diào)用了的相關(guān)函數(shù)，如象算法3.1（a）那樣，對余數(shù)的入棧操作：Push_SeqStack （ &s ，N % r ）;因為是用c語言描述，第一個參數(shù)是棧的地址才能對棧進行加工。在后面的例子中，為了算法的清楚易讀， 在不至于混淆的情況下，不再加地址運算符，請讀者注意。【例3.2】利用

5、棧實現(xiàn)迷宮的求解。問題：這是實驗心理學(xué)中的一個經(jīng)典問題，心理學(xué)家把一只老鼠從一個無頂蓋的大盒 子的入口處趕進迷宮。迷宮中設(shè)置很多隔壁， 對前進方向形成了多處障礙，心理學(xué)家在迷宮的唯一出口處放置了一塊奶酪，吸引老鼠在迷宮中尋找通路以到達(dá)出口。求解思想：回溯法是一種不斷試探且及時糾正錯誤的搜索方法。下面的求解過程采用回溯法。從入口出發(fā)，按某一方向向前探索，若能走通（未走過的），即某處可以到達(dá)，貝U到達(dá)新點，否則試探下一方向；若所有的方向均沒有通路，則沿原路返回前一點，換下一個方向再繼續(xù)試探，直到所有可能的通路都探索到，或找到一條通路，或無路可走又返回到入口點。在求解過程中，為了保證在到達(dá)某一點后不

6、能向前繼續(xù)行走（無路）時，能正確返回 前一點以便繼續(xù)從下一個方向向前試探，則需要用一個棧保存所能夠到達(dá)的每一點的下標(biāo)及從該點前進的方向。需要解決的四個問題：1 表示迷宮的數(shù)據(jù)結(jié)構(gòu)：設(shè)迷宮為m行n列，利用mazemn來表示一個迷宮， mazeij=0或1;其中：0表示 通路，1表示不通，當(dāng)從某點向下試探時，中間點有8個方向可以試探，（見圖3.4）而四個角點有3個方向，其它邊緣點有5個方向，為使問題簡單化我們用mazem+2n+2來表示迷宮，而迷宮的四周的值全部為1。這樣做使問題簡單了，每個點的試探方向全部為8，不用再判斷當(dāng)前點的試探方向有幾個，同時與迷宮周圍是墻壁這一實際問題相 一致。如圖3.4

7、表示的迷宮是一個 6 >8的迷宮。入口坐標(biāo)為（1, 1）,出口坐標(biāo)為（m, n） o入口（1,1）出口 （6,8）（x-1，y-1）（x，y-1）（x，y）（x+1，y-1）（x-1，y+1）（x+1，y）* （x，y+1）（x+1，y+1）圖3.5與點（x，y）相鄰的8個點及坐標(biāo)0111101-10-1-1-1-10-11012347563.棧的設(shè)計： 當(dāng)?shù)竭_(dá)了某點 而無路可走時需返 回前一點，再從前一 點開始向下一個方 向繼續(xù)試探。因此， 壓入棧中的不僅是 順序到達(dá)的各點的 坐標(biāo)，而且還要有從x y1111111111101110111111010111111010000011101

8、110111111001100011011001101111111111101234567891234567圖3.4 用mazem+2n+2表示的迷宮迷宮的定義如下：#define m6 /*迷宮的實際行*/#defi ne n8/* 迷宮的實際列 */int maze m+2n+2;2.試探方向：在上述表示迷宮的情況下，每個點有8個方向去試探，女口當(dāng)前點的坐標(biāo)（x,y），與其相鄰的8個點的坐標(biāo)都可根據(jù)與該點的相鄰方位而得到，如圖3.5所示。因為出口在（m, n），因此試探順序規(guī)定為：從當(dāng)前位置向前試探的方向為從正東沿順時針方向進行。為了簡化問題，方便的求出新點的坐標(biāo)，將從正東開始沿順時針進行

9、的這8個方向的坐標(biāo)增量放在一個結(jié)構(gòu)數(shù)組move 8 中，在move數(shù)組中，每個元素有兩個域組成，x:橫坐標(biāo)增量，y:縱坐標(biāo)增量。move數(shù)組如圖3.6所示。Move數(shù)組定義如下：typedef struct intx ， y item ;item move8;這樣對move的設(shè)計會很方便地求出從某點（x，y）按某一方向v （0<=v<=7）到達(dá)的新點（i，j）的坐標(biāo)：i=x+movev.x ; j=y+movev.y ;（x-1，y）棧中每一組數(shù)據(jù)是所到達(dá)的每點的坐標(biāo)及從該點沿哪個方向向下走的，對于圖3.4迷宮，走的路線為：（1,1）1 （2,2）1 （3,3）0 （3,4）0 （

10、3,5）0 （3,6）0 （下腳標(biāo)表示方向），當(dāng)從點（3,6） 沿方向0到達(dá)點（3,7）之后，無路可走，則應(yīng)回溯，即退回到點（3,6），對應(yīng)的操作是出棧，沿下一個方向即方向1繼續(xù)試探，方向1、2試探失敗，在方向3上試探成功，因此將 （3,6,3） 壓入棧中，即到達(dá)了（4,5）點。棧中元素是一個由行、列、方向組成的三元組，棧元素的設(shè)計如下：typedef structint x , y , d ;/* 橫縱坐標(biāo)及方向*/datatype ;棧的定義仍然為：SeqStack s ;4.如何防止重復(fù)到達(dá)某點，以避免發(fā)生死循環(huán)：一種方法是另外設(shè)置一個標(biāo)志數(shù)組markmn，它的所有元素都初始化為0, 一

11、旦到達(dá)了某一點（i , j ）之后，使markij置1,下次再試探這個位置時就不能再走了。另一種方 法是當(dāng)?shù)竭_(dá)某點（i , j）后使mazeij置-1，以便區(qū)別未到達(dá)過的點，同樣也能起到防止 走重復(fù)點的目的，本書采用后者方法，算法結(jié)束前可恢復(fù)原迷宮。迷宮求解算法思想如下：1. 棧初始化；2. 將入口點坐標(biāo)及到達(dá)該點的方向（設(shè)為一1）入棧3. while （棧不空）棧頂元素=（x , y , d ）出棧；求出下一個要試探的方向d+ ;while（還有剩余試探方向時） if （ d方向可走）則（x , y , d ）入棧;求新點坐標(biāo)（i, j ）;將新點（i , j）切換為當(dāng)前點（x , y）;i

12、f （ （x , y ）= =（ m ,n）結(jié)束;else 重置 d=0 ;else d+ ;算法如下：int path(maze, move)int mazem n;item move8; SeqStack s ; datetype temp ;int x, y, d, i, j ;temp.x=1 ; temp.y=1 ; temp.d=-1 ;Push_SeqStack (s, temp);while (! Empty_SeqStack (s ) Pop_SeqStack (s,& temp);x=temp.x ; y=temp.y ; d=temp.d+1 ;while (d&

13、lt;8) i=x+moved.x ; j=y+moved.y ;if ( mazeij= =0 ) temp=x, y, d;Push_SeqStack ( s, temp );x=i ; y=j ; mazexy= -1 ;if (x=m&&y= =n) return 1 ; /* 迷宮有路 */ else d=0 ;else d+ ; /*while (d<8)*/ /*while */return 0 ;/*迷宮無路*/算法3.2棧中保存的就是一條迷宮的通路?！厩纠?.3】表達(dá)式求值表達(dá)式求值是程序設(shè)計語言編譯中一個最基本的問題。它的實現(xiàn)也是需要棧的加入。 下面

14、的算法是由算符優(yōu)先法對表達(dá)式求值。表達(dá)式是由運算對象、 運算符、括號組成的有意義的式子。 運算符從運算對象的個數(shù)上 分，有單目運算符和雙目運算符；從運算類型上分，有算術(shù)運算、關(guān)系運算、邏輯運算。在 此僅限于討論只含二目運算符的算術(shù)表達(dá)式。1.中綴表達(dá)式求值：中綴表達(dá)式：每個二目運算符在兩個運算量的中間，假設(shè)所討論的算術(shù)運算符包括：+、-、*、/、A （乘方）和括號（）。設(shè)運算規(guī)則為：.運算符的優(yōu)先級為：（）> A> *、/、%> +、-;有括號出現(xiàn)時先算括號內(nèi)的，后算括號外的，多層括號，由內(nèi)向外進行；.乘方連續(xù)出現(xiàn)時先算最右面的；表達(dá)式作為一個滿足表達(dá)式語法規(guī)則的串存儲，如表

15、達(dá)式“3*2A （ 4+2*2- 1 *3 ） -5” ,它的的求值過程為：自左向右掃描表達(dá)式， 當(dāng)掃描到3*2時不能馬上計算，因為后面可能還 有更高的運算，正確的處理過程是：需要兩個棧：對象棧si和算符棧S2。當(dāng)自左至右掃描表達(dá)式的每一個字符時，若當(dāng)前字符是運算對象，入對象棧，是運算符時，若這個運算符比棧頂運算符高則入棧，繼續(xù)向后處理，若這個運算符比棧頂運算符低則從對象棧出棧兩個運 算量，從算符棧出棧一個運算符進行運算，并將其運算結(jié)果入對象棧，繼續(xù)處理當(dāng)前字符， 直到遇到結(jié)束符。根據(jù)運算規(guī)則，左括號“（”在棧外時它的級別最高，而進棧后它的級別則最低了；乘方運算的結(jié)合性是自右向左，所以，它的棧

16、外級別高于棧內(nèi)；就是說有的運算符棧內(nèi)棧外的級別是不同的。當(dāng)遇到右括號“）”時，一直需要對運算符棧出棧，并且做相應(yīng)的運算，直 到遇到棧頂為左括號“（”時，將其出棧，因此右括號“）”級別最低但它是不入棧的。對象 棧初始化為空，為了使表達(dá)式中的第一個運算符入棧，算符棧中預(yù)設(shè)一個最低級的運算符“（”。根據(jù)以上分析，每個運算符棧內(nèi)、棧外的級別如下：算符棧內(nèi)級別棧外級別A34*、/、%22+、-11(04)-1-1中綴表達(dá)式表達(dá)式“ 3*2A （4+2*2- 1 *3 ） -5”求值過程中兩個棧的狀態(tài)情況見圖3.7所示。讀字符對象棧si算符棧s2說明33(3入棧s1*3(*入棧s223, 2(*2入棧s1

17、A3, 2(*Aa入棧s2(3, 2(*A(（入棧s243, 2, 4(*A(4入棧s1+3, 2, 4(*A(+入棧s223, 2, 4, 2(*A(+2入棧s1*3, 2, 4, 2(*A(+*入棧s223, 2, 4, 2, 2(*A(+*2入棧s13, 2, 4, 4(*A(+做2+2=4 ,結(jié)果入棧s13, 2, 8(*A(做4+4=8 ,結(jié)果入棧s23, 2, 8(*A(-入棧s213, 2, 8, 1(*AC1入棧s1*3 , 2 , 8 , 1(*A(-*入棧s233 , 2 , 8, 1, 3(*A(-*3入棧s1)3 , 2 , 8 , 3(*A(-做1*3 ,結(jié)果3入棧s

18、13, 2, 51(*a(做8-3,結(jié)果5入棧s23, 2, 5(*A(出棧3, 32(*做2A5，結(jié)果32入棧si96(做3*32，結(jié)果96入棧si96(-入棧s2596, 5(-5入棧si結(jié)束符91(做96-5,結(jié)果91入棧si圖3.7中綴表達(dá)式 3*2A (4+2*2- 1 *3) -5 的求值過程為了處理方便，編譯程序常把中綴表達(dá)式首先轉(zhuǎn)換成等價的后綴表達(dá)式，后綴表達(dá)式 的運算符在運算對象之后。在后綴表達(dá)式中，不在引入括號，所有的計算按運算符出現(xiàn)的順序，嚴(yán)格從左向右進行，而不用再考慮運算規(guī)則和級別。中綴表達(dá)式“3*2A(4+2*2-1*3)-5 ”的后綴表達(dá)式為：“32422*+13*

19、-a*5- ”。2.后綴表達(dá)式求值計算一個后綴表達(dá)式，算法上比計算一個中綴表達(dá)式簡單的多。這是因為表達(dá)式中即無括號又無優(yōu)先級的約束。具體做法：只使用一個對象棧，當(dāng)從左向右掃描表達(dá)式時，每遇到 一個操作數(shù)就送入棧中保存，每遇到一個運算符就從棧中取出兩個操作數(shù)進行當(dāng)前的計算， 然后把結(jié)果再入棧，直到整個表達(dá)式結(jié)束，這時送入棧頂?shù)闹稻褪墙Y(jié)果。下面是后綴表達(dá)式求值的算法，在下面的算法中假設(shè)，每個表達(dá)式是合乎語法的，并且假設(shè)后綴表達(dá)式已被存入一個足夠大的字符數(shù)組A中，且以#'為結(jié)束字符，為了簡化問題，限定運算數(shù)的位數(shù)僅為一位且忽略了數(shù)字字符串與相對應(yīng)的數(shù)據(jù)之間的轉(zhuǎn)換的問題。typedef cha

20、r datetype ;double calcul_exp(char *A)/*本函數(shù)返回由后綴表達(dá)式A表示的表達(dá)式運算結(jié)果*/Seq_Starck s ;ch=*A+ ; Ini t_SeqStack(s);while ( ch !=' #')if (ch!=運算符)Push_SeqStack (s , ch);else Pop_SeqStack (s , &a);Pop_SeqStack (s , &b) ; /*取出兩個運算量 */switch (ch). case ch= ='： +' c =a+b ; break ;case ch= =

21、 - '：'c=a-b ; break ;case ch= = ' *' c=a*b ; break ;case ch= = ' / c=a/b ; break ; case ch= =' ： % c=a%b ; break ;Push_SeqStack (s, c);ch=*A+ ;Pop _SeqStack ( s , result );return result ;算法3.3棧中狀態(tài)變化情況：當(dāng)前字符棧中數(shù)據(jù)說明333入棧23,22入棧43, 2, 44入棧23, 2, 4, 22入棧23, 2, 4, 2, 22入棧*3, 2, 4, 4

22、計算2*2,將結(jié)果4入棧+3, 2, 8計算4 + 4,將結(jié)果8入棧13, 2, 8, 11入棧33, 2, 8, 1 , 33入棧*3 , 2 , 8 , 3計算1*3,將結(jié)果4入棧一3 , 2 , 5計算8-5,將結(jié)果5入棧A3 , 32計算2A5 ,將結(jié)果32入棧*96計算3* 32 ,將結(jié)果96入棧596 , 55入棧-96計算96-5 ,結(jié)果入棧結(jié)束符空結(jié)果出棧圖3.8后綴表達(dá)式求值過程3. 中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式：將中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)示和前述對中綴表達(dá)式求值的方法完全類似，但只需要運算符棧，遇到運算對象時直接放后綴表達(dá)式的存儲區(qū)，假設(shè)中綴表達(dá)式本身合法且在字符數(shù)組A中，轉(zhuǎn)換后的后綴表達(dá)式存儲在字符數(shù)組B中。具體做法：遇到運算對象順序向存儲后綴表達(dá)式的B數(shù)組中存放，遇到運算符時類似于中綴表達(dá)式求值時對運算符的處理過程， 但運算符出棧后不是進行相應(yīng)的運算，而是將其送入B中存放。讀者不難寫出算法，在此不在贅述?！纠?.4】 棧與遞歸：棧的一個重要應(yīng)用是在程序設(shè)計語言中實現(xiàn)遞歸過程?，F(xiàn)實中，有許多實際問題是遞 歸定義的，這時用遞歸方法可以使許多問題的結(jié)果大大簡化，以n!為例：n!的定義為：n!=1n=0n*(n-1)n>0/*遞歸終止條件*/*遞歸步驟*/根據(jù)定義可以很自然的寫出相應(yīng)的遞歸函數(shù)int fact (i n