工學數據結構ppt課件-wenkub.com
2024-10-31 20:39 本頁面
【正文】 每 退出 一層遞歸（完成一次遞歸函數的調用），就 從棧頂彈出 一個工作記錄。 ? 依照被調函數保存的返回地址將 控制轉移 到調用函數。 ? 為被調用函數的局部變量 分配存儲區(qū) 。 //將編號為 1的盤子從 x柱移到 z柱 4 else { 5 Hanoi ( n1 , x , z , y ) 。 當工作做完之后，就標志著世界末日到來。 。 Pop(OPND,b)。 case ?=‘: Pop(OPTR)。 c=getchar()。c=getchar()。 判 C是否操作符 棧 ? 例五：表達式求值 算法描述： Status EvaluateExpression( OperandType amp。 根據上面的運算規(guī)則，在運算的每一步中，任意兩個 相繼出現的算符 ?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ī)則 得出：‘ （ ’ = ‘ ） ’ 表明括號內的運算已完成； ‘ ’ =‘ ’ 表明表達式求值完畢。 ? 若當前位置“不可通”，則后退，換方向繼續(xù)探索 。 } ch = getchar()。: ClearStack(S)。 : Pop(S, c)。 棧 ? 例三：行編輯程序 假設從終端接受了這樣兩行字符： whliilre（ s*s) outchaputchar(*s=++)。如果在棧頂的那個左括弧正好和它匹配，就可將它從棧頂刪除。 ? “ 期待的急迫程度 ” :即后出現的 “ 左括弧 ” ，它等待與其匹配的 “ 右括弧 ” 出現的 “ 急迫 ”心情要比先出現的左括弧高。 } while (!StackEmpty(S)) { Pop(S,e)。 棧 棧的應用舉例 例一：數制轉換 例二：括號匹配的檢驗 例三：行編輯程序 例四：迷宮求解 例五：表達式求值 例六：漢諾塔問題 ** 設計思路： 用棧暫存低位值 棧 ? 例一：數制轉換 算法基于原理： N = (N div d) d + N mod d 求商 求余 進制 例如： （ 1348)10 = (2504)8 ，其運算過程如下 ： N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2 計算順序 輸出順序 棧 算法描述： void conversion () { //對于輸入的十進制非負整數，輸出對應的八進制數 InitStack(S)。 q=top。 }//GetPop 棧 鏈棧 (補充 ): 用鏈式結構來表示的棧就是 鏈棧 (1)鏈棧的構造方式 : 以頭指針為棧頂， 在頭指針處 插入或刪除 S next data ^ an an1 a1 a2 棧頂元素 棧底元素 注意指針方向 通常鏈棧不設 頭結點 ，因為棧頂 (表頭）操作頻繁 基本操作 ： pdata=e。 }//Pop 棧頂指針減 1，取所指元素 棧 棧的表示和實現 ? 取棧頂元素 算法描述： Status GetTop(SqStack S， SElemType amp。S, SElemType amp。 }//Push e插入后棧頂指針加 1 if ( = ){ //棧滿 ,追加存儲空間 = (SElemType *)relloc( , (STACK_INI_SIZE+STACKINCREMENT)* sizeof (SElemType))。 return OK。S){ // 構造一個空順序棧 S = (SElemType *)malloc(STACK_INI_SIZE* sizeof (SElemType))。S， e) // 入棧 Pop(amp。 s的存儲空間為： s. stacksize [0] [stac
教學課件相關推薦
鄂ICP備17016276號-1