武漢軟件工程職業(yè)學(xué)院數(shù)據(jù)結(jié)構(gòu)講義第09講-棧的應(yīng)用-免費(fèi)閱讀
【正文】 遞歸工作棧示意圖 R2: return f 。在每次調(diào)用時(shí)系統(tǒng)將屬于各個(gè)遞歸層次的信息組成一個(gè)活動(dòng)記錄（ActivaTion Record），這個(gè)記錄中包含著本層調(diào)用的實(shí)參、返回地址、局部變量等信息，并將這個(gè)活動(dòng)記錄保存在系統(tǒng)的“遞歸工作棧”中，每當(dāng)遞歸調(diào)用一次，就要在棧頂為過(guò)程建立一個(gè)新的活動(dòng)記錄，一旦本次調(diào)用結(jié)束，則將棧頂活動(dòng)記錄出棧，根據(jù)獲得的返回地址信息返回到本次的調(diào)用處。}棧中狀態(tài)變化情況：當(dāng)前字符 棧中數(shù)據(jù) 說(shuō)明３3３入棧２3，２２入棧４3，2，4４入棧２3，2，4，2２入棧２3，2，4，2，2２入棧＊3，2，4，4計(jì)算２＊２，將結(jié)果４入棧＋3，2，8計(jì)算４＋４，將結(jié)果８入棧１3，2，8，1１入棧３3，2，8，1，3３入棧＊3，2，8，3計(jì)算１＊３，將結(jié)果４入棧－3，2，5計(jì)算８－５，將結(jié)果５入棧^ 3，32計(jì)算2^5，將結(jié)果32入棧*96計(jì)算３＊32，將結(jié)果96入棧596，55入棧96計(jì)算965，結(jié)果入棧結(jié)束符空結(jié)果出棧圖 后綴表達(dá)式求值過(guò)程3． 中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式：將中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)示和前述對(duì)中綴表達(dá)式求值的方法完全類(lèi)似，但只需要運(yùn)算符棧，遇到運(yùn)算對(duì)象時(shí)直接放后綴表達(dá)式的存儲(chǔ)區(qū)，假設(shè)中綴表達(dá)式本身合法且在字符數(shù)組A中，轉(zhuǎn)換后的后綴表達(dá)式存儲(chǔ)在字符數(shù)組B中。 case ch= =’/ ’： c=a/b 。 Pop_SeqStack (s , amp。下面是后綴表達(dá)式求值的算法，在下面的算法中假設(shè)，每個(gè)表達(dá)式是合乎語(yǔ)法的，并且假設(shè)后綴表達(dá)式已被存入一個(gè)足夠大的字符數(shù)組A中，且以‘’為結(jié)束字符，為了簡(jiǎn)化問(wèn)題，限定運(yùn)算數(shù)的位數(shù)僅為一位且忽略了數(shù)字字符串與相對(duì)應(yīng)的數(shù)據(jù)之間的轉(zhuǎn)換的問(wèn)題。對(duì)象棧初始化為空，為了使表達(dá)式中的第一個(gè)運(yùn)算符入棧，算符棧中預(yù)設(shè)一個(gè)最低級(jí)的運(yùn)算符“（”。在此僅限于討論只含二目運(yùn)算符的算術(shù)表達(dá)式。} else d++ 。 Push_SeqStack ( s, temp ) 。 Push _SeqStack (s，temp) 。 } } 算法如下： int path(maze，move) int maze[m][n] 。2． 將入口點(diǎn)坐標(biāo)及到達(dá)該點(diǎn)的方向（設(shè)為－１）入棧3． while (棧不空){ 棧頂元素＝＞（x , y , d）出棧 。(3,5)0224。這樣對(duì)move的設(shè)計(jì)會(huì)很方便地求出從某點(diǎn) (x，y) 按某一方向 v (0=v=7) 到達(dá)的新點(diǎn)（i，j）的坐標(biāo)：i=x+move[v].x 。 8的迷宮。求解思想：回溯法是一種不斷試探且及時(shí)糾正錯(cuò)誤的搜索方法。通常用順序棧較多，因?yàn)楹鼙憷?s ) ) while (top!=1) { Pop_SeqStack (amp。s)。算法思想如下：當(dāng)N0時(shí)重復(fù)1，21． 若 N≠0，則將N % r 壓入棧s中 ，執(zhí)行2。第三章 棧和隊(duì)列第九講 棧的應(yīng)用 1．鞏固棧的定義及表示。若N=0，將棧s的內(nèi)容依次出棧，算法結(jié)束。 top =1。s ，amp。在后面的例子中，為了在算法中表現(xiàn)出問(wèn)題的層次，有關(guān)棧的操作調(diào)用了的相關(guān)函數(shù)，(a)那樣，對(duì)余數(shù)的入棧操作：Push_SeqStack ( amp。下面的求解過(guò)程采用回溯法。 入口坐標(biāo)為（1，1），出口坐標(biāo)為（m，n）。 j=y+move[v].y 。(3,6)0（下腳標(biāo)表示方向），當(dāng)從點(diǎn)(3,6)沿方向0到達(dá)點(diǎn)(3,7)之后，無(wú)路可走，則應(yīng)回溯，即退回到點(diǎn)(3,6)，對(duì)應(yīng)的操作是出棧，沿下一個(gè)方向即方向1繼續(xù)試探，方向１、２試探失敗，在方向３上試探成功，因此將(3,6,3)壓入棧中，即到達(dá)了（4,5）點(diǎn)。求出下一個(gè)要試探的方向d++ 。 item move[8] 。 while (! Empty_SeqStack (s ) ) { Pop_SeqStack (s,＆temp) 。 x=i 。} /*while (d8)*/ } /*while */ return 0 。1． 中綴表達(dá)式求值：中綴表達(dá)式：每個(gè)二目運(yùn)算符在兩個(gè)運(yùn)算量的中間，假設(shè)所討論的算術(shù)運(yùn)算符包括：+ 、 、*、/、
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1