棧及其應(yīng)用課件

棧的應(yīng)用梁音地球物理與空間信息學(xué)院地球信息科學(xué)與技術(shù)系棧的概念棧(stack)就是線性表特殊的線性表一般線性表：插入和刪除操作可以對(duì)線性表的任一元素進(jìn)行棧：插入和刪除操作只能在線性表的一端進(jìn)行，而另一端是固定的。棧的概念進(jìn)棧元素的順序和出棧元素的順序是相反的棧的很多應(yīng)用都是基于這一點(diǎn)棧的應(yīng)用數(shù)制轉(zhuǎn)換括號(hào)匹配表達(dá)式求值路徑搜索遞歸數(shù)制的轉(zhuǎn)換如何將十進(jìn)制數(shù)字N轉(zhuǎn)換成d進(jìn)制數(shù)字算法的基本原理N=(Ndivd)×d+Nmodd典型的輸入序列和輸出序列是相反的數(shù)制的轉(zhuǎn)換算法描述：(以8進(jìn)制數(shù)的轉(zhuǎn)換為例)(1)初始化一個(gè)空棧S，并輸入十進(jìn)制數(shù)N(2)N是否等于0？是的，轉(zhuǎn)到(3)；不是push(S,N%8)，N=N/8(3)棧S是否為空？不是，pop(S,e)，打印e的值；否則，結(jié)束。棧的應(yīng)用數(shù)制的轉(zhuǎn)換是棧最典型的應(yīng)用：輸入序列和輸出序列是反序的。但是并非關(guān)于棧的所有應(yīng)用都是這樣有著嚴(yán)格的反序關(guān)系。很多棧的高級(jí)應(yīng)用都是利用棧來實(shí)現(xiàn)某些狀態(tài)的還原。(路徑搜索和遞歸)括號(hào)匹配假設(shè)表達(dá)式中允許包含兩種括號(hào)：[]和(),并允許這兩種括號(hào)隨意嵌套比如：([]())或者[([][])]都是正確的格式而[(])或(()]等等都是不正確的格式括號(hào)匹配那么如何判斷一個(gè)括號(hào)表達(dá)式是否合法呢？利用棧來實(shí)現(xiàn)因?yàn)樽詈筮M(jìn)來的括號(hào)是最需要進(jìn)行匹配的那一個(gè)括號(hào)匹配算法描述：(1)表達(dá)式是否結(jié)束？(2)是的，棧S是否空？是的，輸出合法表達(dá)式，否則，括號(hào)表達(dá)式不合法；(3)否，該括號(hào)是“[”或者“(”嗎？是的，進(jìn)棧S，否則，棧S出棧；括號(hào)匹配算法：(4)出棧的元素和當(dāng)前表達(dá)式中的括號(hào)是否匹配？是的，跳到(1)，否則，表達(dá)式不合法。括號(hào)匹配假設(shè)現(xiàn)在表達(dá)式中只要是含有成對(duì)出現(xiàn)的括號(hào)，就認(rèn)為是合法的表達(dá)式？比如：([]())或者[([][])]或者[(])都是合理的，而(()]是不合理的。算法該如何設(shè)計(jì)？行編輯程序一個(gè)簡(jiǎn)單的行編輯程序：接受用戶從終端輸入程序和數(shù)據(jù)，并存入用戶數(shù)據(jù)區(qū)。用戶在終端上的輸入不能保證不出差錯(cuò)一個(gè)字符一個(gè)字符的存入數(shù)據(jù)區(qū)顯然是不合適的。行編輯程序一個(gè)簡(jiǎn)單的行編輯程序：加入兩個(gè)修改符號(hào)：#：表示前一個(gè)輸入的字符無效（校正前一個(gè)輸入字符）；@：表示當(dāng)前行中的字符都無效（退行符）行編輯程序一個(gè)簡(jiǎn)單的行編輯程序：那應(yīng)該如何進(jìn)行字符的接受呢？較好的方法是：建立一個(gè)緩沖區(qū)，接受用戶輸入的一行字符，確認(rèn)無誤后再逐行存入用戶數(shù)據(jù)區(qū)。行編輯程序一個(gè)簡(jiǎn)單的行編輯程序：那么這個(gè)緩沖區(qū)用什么樣的數(shù)據(jù)結(jié)構(gòu)呢？因?yàn)樾枰幚砬懊娴囊粋€(gè)字符或者一個(gè)字符行無效所以，棧是比較合適的行編輯程序一個(gè)簡(jiǎn)單的行編輯程序：將用戶輸入的字符先進(jìn)棧；如果輸入的字符是#，則，出棧一個(gè)字符；如果輸入的字符是@，則，清空棧。表達(dá)式求值表達(dá)式求值是程序設(shè)計(jì)語言編譯中的一個(gè)最基本問題它是棧應(yīng)用的又一個(gè)典型的例子算符優(yōu)先法表達(dá)式求值假設(shè)該表達(dá)式中只含有加、減、乘和除法運(yùn)算，可以含有括號(hào)；運(yùn)算規(guī)則：先乘除，后加減從左向右進(jìn)行先括號(hào)內(nèi)的，再括號(hào)外的表達(dá)式求值這里需要啟用兩個(gè)棧來完成這個(gè)任務(wù)：操作數(shù)棧（OPND）運(yùn)算符棧（OPTR）表達(dá)式求值操作數(shù)棧（OPND）：存儲(chǔ)表達(dá)式中的字符、數(shù)字或運(yùn)算結(jié)果等。運(yùn)算符棧（OPTR）：用以寄存運(yùn)算符。運(yùn)算符之間的優(yōu)先關(guān)系表。表達(dá)式求值基本算法思想：（1）表達(dá)式是否結(jié)束？是的，OPND棧底元素就是運(yùn)算結(jié)果；（2）否則，當(dāng)前的輸入是字符嗎？是的，字符進(jìn)棧OPND（3）否則，將該運(yùn)算符和棧OPTR的棧表達(dá)式求值頂元素進(jìn)行比較：A、如果OPTR棧頂元素優(yōu)先級(jí)別低，則將該元素進(jìn)棧OPTR；B、如果優(yōu)先級(jí)別相等，則OPTR出棧一次；C、如果OPTR棧頂元素優(yōu)先級(jí)別高，則表達(dá)式求值OPTR出棧一次，OPND出棧兩次，然后進(jìn)行運(yùn)算，將結(jié)果進(jìn)棧OPND。讀入下一個(gè)字符，跳到（1）。迷宮求解入口出口迷宮求解求迷宮從入口到出口的所有路徑是一個(gè)經(jīng)典的程序設(shè)計(jì)問題窮舉求解需要在任何位置上都能沿原路返回顯然需要一個(gè)后進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)來保存從入口到當(dāng)前位置的路徑背景資料MarsAutonomy（CarnegieMellonUniversity）ObstaclesAvoidancePathPlanningIntegrationPerceptionandMappingPathPlanningTwotypesofuncertainty:

Theenvironmentswillbeunknownorpartially-known.Thepositiononthesurfacewillbeknownonlyapproximately.TheyusetheD*algorithmToplanpathstothegoal

迷宮求解入口出口迷宮求解想法：從一個(gè)位置開始的下一步可以向4個(gè)方向前進(jìn)2314迷宮求解想法：這4個(gè)位置有的可通，有的不可通所求解的通路應(yīng)該是簡(jiǎn)單路徑，所以位置的可通和不可通都是動(dòng)態(tài)的若當(dāng)前位置不可通，則退到前一可通位置繼續(xù)搜索迷宮求解退到前一可通位置后要標(biāo)記前面的不可通的位置簡(jiǎn)單路徑上不能出現(xiàn)重復(fù)位置塊重復(fù)出現(xiàn)的位置塊也是不可通的塊搜索方向的問題：有時(shí)候會(huì)大大簡(jiǎn)化搜索的進(jìn)程