工學(xué)數(shù)據(jù)結(jié)構(gòu)ppt課件-資料下載頁
2024-11-03 20:39本頁面
【正文】 case ?‘: Pop(OPTR ,theta)。 Pop(OPND,b)。a=Pop()。 Push(OPND, Operate(a, theta,b)) 。break。 。 } //switch }//while result=GetTop(OPND)。 }//EvaluateExpression Operate=a ? b 運(yùn)算符與棧頂比較并查 棧 ? 例五：表達(dá)式求值 例：對表達(dá)式 3*（ 7 – 2 ）求值 OPTR OPND INPUT OPERATE 3*(72) Push(opnd,’3’) *(72) 3 Push(optr,’*’) ,* 3 (72) Push(optr,’(’) ,*,( 3 72) Push(opnd,’7’) ,*,( 3,7 2) Push(optr,’’) ,*,(,－ 3,7 2) Push(opnd,’2’) ,*,(,－ 3,7,2 ) Operate(72) ,*,( 3,5 ) Pop(optr) ,* 3,5 Operate(3*5) 15 GetTop(opnd) 練習(xí)： 3+4(69/2)+7*5 (參照例 31) 棧 ? 例六：漢諾塔問題 ** 漢諾 （ Hanoi） 塔 傳說在創(chuàng)世紀(jì)時(shí)，在一個(gè)叫 Brahma的寺廟里，有三 個(gè)柱子，其中一柱上有 64個(gè)盤子從小到大依次疊放，僧 侶的工作是將這 64個(gè)盤子從一根柱子移到另一個(gè)柱子上。 移動(dòng)時(shí)的規(guī)則： ? 每次只能移動(dòng)一個(gè)盤子； ? 只能小盤子在大盤子上面； ? 可以使用任一柱子。 當(dāng)工作做完之后，就標(biāo)志著世界末日到來。 x y z n –1 n 棧 ? 例六：漢諾塔問題 ** 分析： 設(shè)三根柱子分別為 x, y, z , 盤子在 x 柱上，要移 到 z 柱上。 當(dāng) n=1 時(shí)，盤子直接從 x 柱移到 z 柱上； 當(dāng) n1 時(shí) , 則 : ① 設(shè)法將前 n –1 個(gè)盤子 從 x 移到 y 柱上（借助 z），則 盤子 n 就能從 x 移到 z 柱上； ② 再設(shè)法把 n –1 個(gè)盤子 從 y 移到 z 柱上 (這又是一 個(gè)與原來相同的問題，只是規(guī)模少１了） 。 x y z n –1 n 遞歸函數(shù) ：一個(gè)直接調(diào)用自己或通過一系列的調(diào)用語句間接調(diào)用自己的函數(shù) 棧 ? 例六：漢諾塔問題 ** 算法描述： Void Hanoi ( int n, char x, char y, char z ) 1 { //將 n個(gè)編號從上到下為 1… n的盤子從 x柱，借助 y柱移到 z柱 2 if ( n = = 1 ) 3 move ( x , 1 , z ) 。 //將編號為 1的盤子從 x柱移到 z柱 4 else { 5 Hanoi ( n1 , x , z , y ) 。 //將 n1個(gè)編號從上到下為 1… n1的盤子從 x柱，借助 z柱 ,移到 y柱 6 move ( x , n, z) 。 //將編號為 n的盤子從 x柱移到 z柱 7 Hanoi ( n1 , y , x , z )。 //將 n1個(gè)編號從上到下為 1… n1的盤子從 y柱，借助 x柱移到 z柱 8 } 9 } //Hanoi 棧 ? 例六：漢諾塔問題 ** 當(dāng)在一個(gè)函數(shù)的運(yùn)行期間 調(diào)用另一個(gè)函數(shù) 時(shí)，在 運(yùn)行 該被調(diào)用函數(shù)之前 ，需先完成三項(xiàng)任務(wù)： ? 將所有的實(shí)在參數(shù)、返回地址等 信息 傳遞給被調(diào)用函數(shù) 保存 。 ? 為被調(diào)用函數(shù)的局部變量 分配存儲區(qū) 。 ? 將 控制轉(zhuǎn)移 到被調(diào)用函數(shù)的入口。 從被調(diào)用函數(shù) 返回 調(diào)用函數(shù) 之前 ， 應(yīng)該完成下列三項(xiàng)任務(wù)： ? 保存 被調(diào)函數(shù)的 計(jì)算結(jié)果 。 ? 釋放 被調(diào)函數(shù)的 數(shù)據(jù)區(qū) 。 ? 依照被調(diào)函數(shù)保存的返回地址將 控制轉(zhuǎn)移 到調(diào)用函數(shù)。 棧 ?例六：漢諾塔問題 ** 函數(shù)調(diào)用過程： 后調(diào)用先返回 ！ ——“棧式管理” 棧 ? 例六：漢諾塔問題 ** ? 遞歸函數(shù)執(zhí)行的過程可視為同一函數(shù)進(jìn)行嵌套調(diào)用，系統(tǒng)用 遞歸工作棧 來完成。 遞歸過程是 后調(diào)用先返回 ，系統(tǒng)需設(shè)立一個(gè) “遞歸工作棧 ” ，每一層遞歸所需信息構(gòu)成一個(gè)“ 工作記錄 ” ， （包括所有的實(shí)參，所有的局部變量以及上一層的返回地址） 。 每 進(jìn)入 一層遞歸（即調(diào)用一次遞歸函數(shù)），就產(chǎn)生一個(gè)新的工作記錄 壓入棧頂 。 每 退出 一層遞歸（完成一次遞歸函數(shù)的調(diào)用），就 從棧頂彈出 一個(gè)工作記錄。 棧 ? 例六：漢諾塔問題 ** 漢諾塔的遞歸函數(shù)演示
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1