工學(xué)數(shù)據(jù)結(jié)構(gòu)ppt課件(參考版)
2024-11-06 20:39本頁面
【正文】 棧 ? 例六：漢諾塔問題 ** 漢諾塔的遞歸函數(shù)演示 。 每 進(jìn)入 一層遞歸（即調(diào)用一次遞歸函數(shù)），就產(chǎn)生一個新的工作記錄 壓入棧頂 。 棧 ?例六：漢諾塔問題 ** 函數(shù)調(diào)用過程： 后調(diào)用先返回 ！ ——“棧式管理” 棧 ? 例六：漢諾塔問題 ** ? 遞歸函數(shù)執(zhí)行的過程可視為同一函數(shù)進(jìn)行嵌套調(diào)用，系統(tǒng)用 遞歸工作棧 來完成。 ? 釋放 被調(diào)函數(shù)的 數(shù)據(jù)區(qū) 。 ? 將 控制轉(zhuǎn)移 到被調(diào)用函數(shù)的入口。 //將 n1個編號從上到下為 1… n1的盤子從 y柱，借助 x柱移到 z柱 8 } 9 } //Hanoi 棧 ? 例六：漢諾塔問題 ** 當(dāng)在一個函數(shù)的運(yùn)行期間 調(diào)用另一個函數(shù) 時，在 運(yùn)行 該被調(diào)用函數(shù)之前 ，需先完成三項任務(wù)： ? 將所有的實在參數(shù)、返回地址等 信息 傳遞給被調(diào)用函數(shù) 保存 。 //將 n1個編號從上到下為 1… n1的盤子從 x柱，借助 z柱 ,移到 y柱 6 move ( x , n, z) 。 x y z n –1 n 遞歸函數(shù) ：一個直接調(diào)用自己或通過一系列的調(diào)用語句間接調(diào)用自己的函數(shù) 棧 ? 例六：漢諾塔問題 ** 算法描述： Void Hanoi ( int n, char x, char y, char z ) 1 { //將 n個編號從上到下為 1… n的盤子從 x柱，借助 y柱移到 z柱 2 if ( n = = 1 ) 3 move ( x , 1 , z ) 。 x y z n –1 n 棧 ? 例六：漢諾塔問題 ** 分析： 設(shè)三根柱子分別為 x, y, z , 盤子在 x 柱上，要移 到 z 柱上。 移動時的規(guī)則： ? 每次只能移動一個盤子； ? 只能小盤子在大盤子上面； ? 可以使用任一柱子。 } //switch }//while result=GetTop(OPND)。break。a=Pop()。 case ?‘: Pop(OPTR ,theta)。c=getchar()。break。} else switch(precede(GetTop(OPTR) , c)) {case ?‘: Push(OPTR , c)。(GetTop(OPTR)!=?‘)) { if (!In(c,OP) { Push(OPND,c)。 while((c!=?‘)amp。Push(OPTR ,‘‘)。result) { InitStack(OPND)。 if（ 是操作數(shù)） → 則 PUSH（ OPND， 操作數(shù) ） ； if（ 是運(yùn)算符） → 則與 OPTR棧頂元素 ?1進(jìn)行比較，按優(yōu)先級 (規(guī)定詳見 P53表 ）進(jìn)行操作； if棧頂元素 輸入算符 ，則算符壓入 OPTR棧，并接收下一字符 if棧頂元素 =運(yùn)算符但 ≠ ‘ ’ ，則脫括號 (彈出左括號 )并收下一字； if棧頂元素 運(yùn)算符 ，則退棧、按棧頂計算，將結(jié)果壓入 OPND棧 。 + θ2 θ1 * / ( ) + * / ( ) = = 棧 ? 例五：表達(dá)式求值 為了實現(xiàn) 算符優(yōu)先算法 ，可以設(shè)定兩個工作棧： OPND—存放操作數(shù)或運(yùn)算結(jié)果， OPTR—存放運(yùn)算符號。 棧 ? 例五：表達(dá)式求值 表達(dá)式求值 是棧應(yīng)用的典型例子 (1)表達(dá)式求值必須滿足算術(shù)四則運(yùn)算規(guī)則： a. 先乘除，后加減 b. 從左算到右 c. 先括號內(nèi)，后括號外 (2)任何一個表達(dá)式由： 操作數(shù)、運(yùn)算符、界限符 組成 (3)運(yùn)算符和界限符統(tǒng)稱 算符 。 ? 若四周“均無通路”，則將當(dāng)前位置從路徑中刪除出去。 } 棧 ? 例四：迷宮求解 (窮舉求解 ) ? ? $ $ $ ? $ $ $ ? ? $ $ ? ? ? ? ? ? ? ? ? ? ? ? 出口 入口 1東 2南 3西 4北
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1