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

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

Theenvironmentswillbeunknownorpartially-known.Thepositiononthesurfacewillbeknownonlyapproximately.TheyusetheD*algorithmToplanpathstothegoal

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