第三章棧與隊列(已修改)
2025-09-11 21:46 本頁面
【正文】 第 三 章 棧與隊列 東南大學計算機學院 方效林 本課件借鑒了清華大學殷人昆老師 和哈爾濱工業(yè)大學張巖老師的課件 本章主要內(nèi)容 ? 棧 ? 棧的應用：表達式求值 ? 棧與遞歸 ? 隊列 ? 隊列的應用：電路布線 2 棧 ? 定義：只允許在表的末端進行插入和刪除的線性表 ? 特點：先進后出 ? 棧的操作 ? 進棧 push() ? 出棧 pop() ? 棧頂 top() ? 置空 setEmpty() ? 判斷是否為空 isEmpty() ? 棧滿 isFull() 3 棧 ? 棧的數(shù)組表示 ? 棧的操作 ? 進棧 push() ? 出棧 pop() ? 棧頂 top() ? 置空 makeEmpty() ? 判斷是否為空 isEmpty() ? 棧滿 isFull() 4 top a b top c top 空棧 top 棧 ? 棧的單鏈表表示 ? 棧的數(shù)組表示可能棧滿 ? 棧的單鏈表表示無棧滿問題 ? 入棧在表頭進行插入操作 ? 出棧在表頭進行刪除操作 5 top c b a null 棧 ? 進棧順序為 (1,2,3)，出棧順序能否為 (3,1,2)? ? 不能， 3出棧時，說明 2和 1都在棧里，而且 2必須先于 1出棧 6 3 2 1 top 作業(yè)： 1， 2， 3， 4， 5， 6依次進棧，若出棧順序為 2， 3， 4， 6， 5， 1 則棧大小至少為多少？ 棧的應用：表達式求值 ? 一個表達式由操作數(shù) (亦稱運算對象 )、操作符 (亦稱運算符 ) 和分界符組成。 ? 算術(shù)表達式三種表示 ? 中綴 (infix)表示 ? 操作數(shù) 操作符 操作數(shù) ，如 A+B； ? 前綴 (prefix)表示 ? 操作符 操作數(shù) 操作數(shù) ，如 +AB； ? 后綴 (postfix)表示 ? 操作數(shù) 操作數(shù) 操作符 ，如 AB+； 7 棧的應用：表達式求值 ? 中綴表達式： A + B * ( C D ) E / F ? 后綴表達式： A B C D * + E F / ? 表達式中相鄰兩個操作符的計算次序為： ? 優(yōu)先級高的先計算； ? 優(yōu)先級相同的自左向右計算； ? 當使用括號時從最內(nèi)層括號開始計算。 ? 前綴和中綴表達式求值需要兩個棧；后綴表達式求值只需一個棧，相對簡單些。 8 棧的應用：表達式求值 ? 從左向右掃描表達式，用一個棧暫存掃描到的操作數(shù)或計算結(jié)果。 ? 后綴表達式的計算順序中已隱含了加括號的優(yōu)先次序，括號在后綴表達式中不出現(xiàn) 9 R1 R2 R3 R4 R5 A B C D * + E F / R1 R2 R3 R4 R5 A+B*(CD)E/F 中綴表達式： 后綴表達式： 10 作業(yè)： 寫出下列中綴表達式的后綴表達式 1. A*B*C 2. A+BC+D 3. A*(B)+C 4. (A+B)*D+E/(F+A*D)+C 5. Aamp。amp。B||!(EF) 6. !(A amp。amp。 !((BC) || (CD))) || (CE) 棧的應用：表達式求值 ? 后綴表達式求值過程 ? 順序掃描后綴表達式每一項 ? 若該項是 操作數(shù) ，則進棧 ? 若該項是 操作符 op， ?若是單目運算符，則出棧一個操作數(shù) X，并將計算結(jié)果 opX進棧 ?若是雙目運算符，則連續(xù)出棧兩個操作數(shù) X和 Y，并將計算結(jié)果 X op Y進棧 ? 當表達式的所有項都掃描并處理完后，棧頂存放的就是最后的計算結(jié)果。 11 棧的應用：表達式求值 12 步 輸入 類型 動作 棧中內(nèi)容 1 置空棧 2 A 操作數(shù) 進棧 A 3 B 操作數(shù) 進棧 A B 4 C 操作數(shù) 進棧 A B C 5 D 操作數(shù) 進棧 A B C D 6 操作符 D、 C退棧，計算 R1=CD進棧 A B R1 7 * 操作符 R B退棧，計算 R2=B*R1進棧 A R2 8 + 操作符 R A退棧，計算 R3=A+R2進棧 R3 9 E 操作數(shù) 進棧 R3 E 10 F 操作數(shù) 進棧 R3 E F 11 / 操作符 F、 E退棧，計算 R4=E / F進棧 R3 R4 12 操作符 R R3退棧，計算 R5=R3R4進棧 R5 top 空棧 top B A C D top top top A B C D * + E F / 后綴表達式求值過程： 棧的應用：表達式求值 13 步 輸入 類型 動作 棧中內(nèi)容 1 置空棧 2 A 操作數(shù) 進棧 A 3 B 操作數(shù) 進棧 A B 4 C 操作數(shù) 進棧 A B C 5 D 操作數(shù) 進棧 A B C D 6 操作符 D、 C退棧，計算 R1=CD進棧 A B R1 7 * 操作符 R B退棧，計算 R2=B*R1進棧 A R2 8 + 操作符 R A退棧，計算 R3=A+R2進棧 R3 9 E 操作數(shù) 進棧 R3 E 10 F 操作數(shù) 進棧 R3 E F 11 / 操作符 F、 E退棧，計算 R4=E / F進棧 R3 R4 12 操作符 R R3退棧，計算 R5=R3R4進棧 R5 B A C D top top top R1=CD A B C D * + E F / 后綴表達式求值過程： 棧的應用：表達式求值 14 步 輸入 類型 動作 棧中內(nèi)容 1 置空棧 2 A 操作數(shù) 進棧 A 3 B 操作數(shù) 進棧 A B 4 C 操作數(shù) 進棧 A B C 5 D 操作數(shù) 進棧 A B C D 6 操作符 D、 C退棧，計算 R1=CD進棧 A
教學課件相關(guān)推薦
鄂ICP備17016276號-1