工學數(shù)據(jù)結構ppt課件(已改無錯字)
2022-12-04 20:39:12 本頁面
【正文】 ，繼續(xù)前進 。 ? 若當前位置“不可通”，則后退，換方向繼續(xù)探索 。 ? 若四周“均無通路”，則將當前位置從路徑中刪除出去。 棧 ? 例四：迷宮求解 設定當前位置的初值為入口位置； do｛ 若 當前位置可通 ， 則｛ 將當前位置 插入棧頂 ； 若 該位置是出口位置， 則 算法結束； 否則切換 當前位置的東鄰方塊為新的當前位置； ｝ 否則 { …… ｝ ｝ while (棧不空） ； 棧 ? 例四：迷宮求解 若 棧不空且棧頂位置尚有其他方向未被探索， 則 設定新的當前位置為 : 沿順時針方向旋轉 找到的 棧頂位置的下一相鄰塊； 若 棧不空但棧頂位置的四周均不可通， 則 ｛刪去棧頂位置； // 從路徑中刪去該通道塊 若 棧不空， 則 重新測試新的棧頂位置， 直至 找到一個可通的相鄰塊或出棧至?？眨? ｝ 若 ?？?，則表明迷宮沒有通路。 棧 ? 例五：表達式求值 表達式求值 是棧應用的典型例子 (1)表達式求值必須滿足算術四則運算規(guī)則： a. 先乘除，后加減 b. 從左算到右 c. 先括號內，后括號外 (2)任何一個表達式由： 操作數(shù)、運算符、界限符 組成 (3)運算符和界限符統(tǒng)稱 算符 。 根據(jù)上面的運算規(guī)則，在運算的每一步中，任意兩個 相繼出現(xiàn)的算符 ?1和 ?2之間的優(yōu)先關系至多是下面 三 種關系 之一： ?1 ?2 : ?1的優(yōu)先權低于 ?2 ?1 = ?2 : ?1的優(yōu)先權等于 ?2 ?1 ?2 : ?1的優(yōu)先權高于 ?2 棧 ? 例五：表達式求值 （下表給出了算符之間的優(yōu)先級） ? 由上表可看出，右括號 ‘ )’ 和井號 ‘ ’ 作為 ?2時 級別最低； ? 由 c 規(guī)則 得出： * ， /， + ， 為 ?1時的優(yōu)先權低于‘ （ ’，高于‘ ） ’ ? 由 b 規(guī)則 得出：‘ （ ’ = ‘ ） ’ 表明括號內的運算已完成； ‘ ’ =‘ ’ 表明表達式求值完畢。 + θ2 θ1 * / ( ) + * / ( ) = = 棧 ? 例五：表達式求值 為了實現(xiàn) 算符優(yōu)先算法 ，可以設定兩個工作棧： OPND—存放操作數(shù)或運算結果， OPTR—存放運算符號。 算法思想： 1）首先置 操作數(shù)棧 OPND為空棧，表達式的起始符 為運算符棧OPTR的棧底元素； 2）依次讀入表達式中的每個字符， 若運算符是 ‘ ’ 或棧頂是 ‘ ’ ，結束計算，返回 OPND棧頂值。 if（ 是操作數(shù)） → 則 PUSH（ OPND， 操作數(shù) ） ； if（ 是運算符） → 則與 OPTR棧頂元素 ?1進行比較，按優(yōu)先級 (規(guī)定詳見 P53表 ）進行操作； if棧頂元素 輸入算符 ，則算符壓入 OPTR棧，并接收下一字符 if棧頂元素 =運算符但 ≠ ‘ ’ ，則脫括號 (彈出左括號 )并收下一字； if棧頂元素 運算符 ，則退棧、按棧頂計算，將結果壓入 OPND棧 。 判 C是否操作符 棧 ? 例五：表達式求值 算法描述： Status EvaluateExpression( OperandType amp。result) { InitStack(OPND)。 InitStack(OPTR)。Push(OPTR ,‘‘)。c=getchar()。 while((c!=?‘)amp。amp。(GetTop(OPTR)!=?‘)) { if (!In(c,OP) { Push(OPND,c)。 c=getchar()。} else switch(precede(GetTop(OPTR) , c)) {case ?‘: Push(OPTR , c)。 c=getchar()。break。 case ?=‘: Pop(OPTR)。c=getchar()。break。
教學課件相關推薦
鄂ICP備17016276號-1