第2章之棧與隊(duì)列(編輯修改稿)
2024-11-03 16:23 本頁面
【文章內(nèi)容簡介】 后綴表達(dá)式求值 假定表達(dá)式是由加減乘除和數(shù)字構(gòu)成。最簡單的表達(dá)式為下列形式： (操作數(shù) S1)(運(yùn)算符 OP)(操作數(shù) S2) 三種不同的表示方法： 前綴表示法 OPS1S2 例如 6+3寫成 +63 中綴表示法 OPS1S2 例如 6+3寫成 63+ 后綴表示法 S1S2OP 例如 6+3寫成 63+ 下一頁 上一頁 停止放映 [第 27頁 /68頁 ] 同時(shí)，任何表達(dá)式都可分解為下列形式： (子表達(dá)式 E1)(運(yùn)算符 OP)(子表達(dá)式 E2) 它的后綴表示法應(yīng)寫成： (E1的后綴表示 )(E2的后綴表示 )OP 只要不斷對子表達(dá)式進(jìn)一步分解，總能將子表達(dá)式分解為最簡單形式，因此任何四則運(yùn)算表達(dá)式都可寫成前綴式或后綴式。 例如： 2*(6+3) ? 2(6+3)* ? 263+*。 (注意：轉(zhuǎn)化為后綴式后括號去掉 ) 下一頁 上一頁 停止放映 [第 28頁 /68頁 ] 用后綴式求值的算法為： 首先設(shè)立一個(gè)堆棧，依此讀取后綴式中的字符，若字符是數(shù)字，則進(jìn)棧并繼續(xù)讀取，若字符是運(yùn)算符，則連續(xù)出棧兩次得到數(shù)字 S1和 S2，計(jì)算表達(dá)式 S1OPS2并將結(jié)果入棧，繼續(xù)讀取后綴式。當(dāng)讀到結(jié)束符時(shí)停止讀操作，這時(shí)堆棧中只應(yīng)該有一個(gè)數(shù)據(jù)，即結(jié)果數(shù)據(jù)。 下一頁 上一頁 停止放映 [第 29頁 /68頁 ] 例如，后綴式 263+*的計(jì)算過程為 3依次入棧，讀 +號則令 3和 6依次出棧，計(jì)算 6+3后將結(jié)果 9入棧，讀 *號則令 9和 2依次出棧，計(jì)算 2*9后將結(jié)果 18入棧。這時(shí)18就是最終結(jié)果。 【 例 23】 假定表達(dá)式是由不超過四個(gè)實(shí)數(shù)進(jìn)行四則運(yùn)算構(gòu)成的算式，要編寫一個(gè)程序來求解該算式的結(jié)果。 下一頁 上一頁 停止放映 [第 30頁 /68頁 ] 舉例 2 遞歸過程實(shí)現(xiàn) 計(jì)算 5的階乘（ 5！ =5 4 3 2 1） fac(long n) { if ( n = = 1) return (1)。 else return ( n * fac(n1))。 } fac(1) fac(2) fac(3) fac(4) fac(5) top 1 fac(1)=1 2*fac(1) fac(2)=2*fac(1) 3*fac(2) fac(3)=3*fac(2) 4*fac(3) fac(4)=4*fac(3) 5*fac(4) fac(5)=5*fac(4) 下一頁 上一頁 停止放映 [第 31頁 /68頁 ] 舉例 3（子程序的嵌套調(diào)用） 有一主程序 main調(diào)用子程序示意圖如下： main sub1 sub2 sub3 end end end end sub3 sub2 sub1 main top 下一頁 上一頁 停止放映 [第 32頁 /68頁 ] 舉例 4 N階 Hanoi塔問題 假設(shè)有 A、 B、 C三座塔。在 A塔上插有 n個(gè)直徑大小不同、以小到大編號為 … 、 n的圓盤?，F(xiàn)要求將 A軸上的 n個(gè)圓盤移至 C塔上，并按同樣順序疊排。移動(dòng)圓盤的規(guī)則為： 1）每次只能移動(dòng)一個(gè)圓盤； 2）圓盤可以插在 A、 B、 C的任意一個(gè)上； 3）任何時(shí)刻都不能將較大的圓盤壓在較小的圓盤之上。 注：這是一個(gè)遞歸問題， n階問題可以分解為 n圓盤和 n1階問題。 下一頁 上一頁 停止放映 [第 33頁 /68頁 ] 算法分析 ? 將 n個(gè)盤子從 A軸移到 C軸可分為以下三個(gè)步驟 : ① 將 A上 n1個(gè)盤子移到 B上 (借助 C)； ② 把 A上剩下的一個(gè)盤子移到 C上； ③ 將 n1個(gè)盤子從 B移到 C上 (借助 A)。 事實(shí)上，上面三個(gè)步驟包括兩種操作： ① 將多個(gè)盤子從一處移到另一處，這是一個(gè)遞歸過程。 ② 將一個(gè)盤子從一處移到另一處。 設(shè)計(jì)兩個(gè)函數(shù)； hanoi函數(shù)實(shí)現(xiàn)第 1個(gè)操作， move函數(shù)實(shí)現(xiàn)第 2個(gè)操作。 例程序 下一頁 上一頁 停止放映 [第 34頁 /68頁 ] n=1的 Hanoi塔問題 A B C A C 下一頁 上一頁 停止放映 [第 35頁 /68頁 ] n=2的 Hanoi塔問題 A B C A B A C B C 下一頁 上一頁 停止放映 [第 36頁 /68頁 ] n=3的 Hanoi塔問題 A B C 變?yōu)?n1問題 A C A B C B A C B A B C A C 下一頁 上一頁 停止放映 [第 37頁 /68頁 ] 隊(duì)列定義 隊(duì)列是一種特殊的線性表，它只允許在表的前端（ front）進(jìn)行刪除操作，而在表的后端（ rear）進(jìn)行插入操作。 進(jìn)行插入操作的端稱為隊(duì)尾，進(jìn)行刪除操作的端稱為隊(duì)頭。 隊(duì)列中沒有元素時(shí)，稱為空隊(duì)列。 隊(duì)列具有先進(jìn)先出（ FIFO）的特點(diǎn)。 隊(duì)列空的條件： front = rear 隊(duì)列滿的條件： rear = MAXSIZE a b c front rear 入隊(duì) 出隊(duì) 隊(duì)列示意圖 maxsize 下一頁 上一頁 停止放映 [第 38頁 /68頁 ] 關(guān)于隊(duì)列表示的約定 約定： 隊(duì)頭指針 front總是指向隊(duì)頭元素的前一個(gè)位置； 隊(duì)尾指針 rear總是指向隊(duì)尾元素的位置。 front = front +1 ； x = queue [front ]； front rear a1 a2 … a n 下一頁 上一頁 停止放映 [第 39頁 /68頁 ] 問題： 讀第 1個(gè)元素時(shí)： front = front +1 x = queue[front]； front = front +1； 讀其它元素時(shí)： x = queue[front]； front = front +1； 顯然，對于第 1個(gè)元素和其它元素的讀操作，將出現(xiàn)不一致。 判別隊(duì)列為空的條件也將復(fù)雜化。 下一頁 上一頁 停止放映 [第 40頁 /68頁 ] 舉例：順序隊(duì)列的入隊(duì)、出隊(duì)操作 （ A）空隊(duì)列 （ B） A、
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1