資源簡(jiǎn)介

(共26張PPT)
棧（第九課時(shí)）
想一想：子彈是如何進(jìn)出彈匣的呢？它有哪些特點(diǎn)？
棧思想
子彈進(jìn)出彈匣的過(guò)程有下列特點(diǎn)：
①整個(gè)裝置只有一端開(kāi)放(最上端)，而且進(jìn)、出只能在這一端進(jìn)行。
②彈匣中的子彈成一縱隊(duì)排列。
③任何子彈進(jìn)出彈匣的規(guī)律是“先進(jìn)后出、后進(jìn)先出” 。
棧思想
a4
a3
a2
a1
棧頂
棧底
入棧
出棧
棧的概念
1.棧是一種先進(jìn)后出的線性表。
2.允許出入、刪除的一端稱為棧頂，
不能操作的稱為棧底。
3.兩大特性：
①先進(jìn)后出，后進(jìn)先出
②有限序列性
棧思想
生活中還有哪些類似的例子？
棧思想
建棧
top:記錄棧頂元素在數(shù)組中的位置
棧的基本操作
列表模擬實(shí)現(xiàn)
棧思想如何程序?qū)崿F(xiàn)？
棧的順序存儲(chǔ)結(jié)構(gòu)：利用數(shù)組存放元素。
top=-1
st=[“”]*4
3
2
1
0
top
入棧
top
A
top
B
top
C
top
D
棧的基本操作
top+=1
st[top]=“A”
top+=1
st[top]=“B”
top+=1
st[top]=“C”
top+=1
st[top]=“D”
3
2
1
0
top
出棧
A
B
C
D
棧的基本操作
while top>=0:
print(st[top])
top-=1
3
2
1
0
top
思考1：同學(xué)們，你能描述出棧的過(guò)程嗎？
棧的基本操作
1.元素A、C、D、G、K、L、M依次入棧，則不可能的出棧順序是：
A.CDKGAML B.GDACLMK C.AKGLDMC D.GDLKCAM
答案：B
規(guī)律：一個(gè)元素出棧后，下一個(gè)出棧的元素只能是它已經(jīng)入棧的相鄰元素或者是未入棧的任一個(gè)元素。B中的A不可能在C前先出棧。
棧
同學(xué)們，棧的思想理解了嗎？我們?cè)囈辉嚄５牡湫蛻?yīng)用
棧的典型應(yīng)用：進(jìn)制轉(zhuǎn)換
入棧過(guò)程:
①top記錄棧頂元素在數(shù)組中的位置,初始值為-1
②除2取余，若商不為0，余數(shù)入棧,商作為新的被除數(shù)。
若商為0，余數(shù)出棧，輸出結(jié)果。用棧st存儲(chǔ)每次得到
的余數(shù)，num存儲(chǔ)被除數(shù)。
0
1
0
top=0
top=1
top=2
0
1
1
棧的典型應(yīng)用：進(jìn)制轉(zhuǎn)換
0
1
0
top=0
top=1
top=2
0
1
1
top=-1
活動(dòng)1：編寫(xiě)進(jìn)制轉(zhuǎn)換的程序
棧的典型應(yīng)用：進(jìn)制轉(zhuǎn)換
分享：
num=int(input(“輸入一個(gè)十進(jìn)制數(shù):"))
sta=[] #空棧
top=-1 #棧頂指針
while num>0: #入棧
a=num%2
sta.append(a)
top+=1
num=num//2
while top>-1: #出棧
print(sta[top],end="")
top=top-1
棧的實(shí)踐與體驗(yàn)
數(shù)學(xué)運(yùn)算表達(dá)式在計(jì)算機(jī)中是如何處理的呢？
例如：3+4*2-7
棧的典型應(yīng)用
思考2：人是如何計(jì)算數(shù)學(xué)表達(dá)式的呢？（完成學(xué)習(xí)任務(wù)單，請(qǐng)描述如何計(jì)算）
3
+
4*2
-
7
8
11
4
1.眼睛從左往右掃過(guò)表達(dá)式
2.發(fā)現(xiàn)乘號(hào)運(yùn)算符等級(jí)最高，
計(jì)算4*2=8
3.比較運(yùn)算符優(yōu)先級(jí)，計(jì)算3+8=11
4.比較運(yùn)算符優(yōu)先級(jí)，計(jì)算11-7=4
實(shí)踐與體驗(yàn)
思考3：計(jì)算機(jī)是如何計(jì)算表達(dá)式的呢？
①.從左到右，逐個(gè)遍歷算式
3+4*2-7
3
+
4
*
2
-
②.取出運(yùn)算數(shù)3
③.取出運(yùn)算符+
④.取出運(yùn)算數(shù)4，能不能計(jì)算結(jié)果
⑤.取出運(yùn)算符*，比較運(yùn)算符優(yōu)先級(jí)
⑥.取出運(yùn)算數(shù)2，能不能計(jì)算結(jié)果
⑦.取出運(yùn)算符-，比較運(yùn)算符優(yōu)先級(jí)，比乘號(hào)低，先計(jì)算乘號(hào)。將之前的數(shù)重新拿出來(lái)。符合了先進(jìn)后出，后進(jìn)先出的特點(diǎn)，所以是棧的數(shù)據(jù)結(jié)構(gòu)
-
實(shí)踐與體驗(yàn)
為什么使用逆波蘭表達(dá)式？
①在數(shù)學(xué)運(yùn)算表達(dá)式中，運(yùn)算符總是置于與之相關(guān)的兩個(gè)運(yùn)算對(duì)象之間，在計(jì)算結(jié)果時(shí)，要考慮括號(hào)、運(yùn)算符號(hào)的優(yōu)先性。
②為了程序?qū)崿F(xiàn)的方便，波蘭邏輯學(xué)家J.Lukasiewicz提出了另一種表示法，將運(yùn)算符置于其運(yùn)算對(duì)象之后，沒(méi)有括號(hào)，不用考慮運(yùn)算符號(hào)的優(yōu)先性。這種表達(dá)式稱為后綴表達(dá)式，又叫逆波蘭表達(dá)式，如表達(dá)式“682-2*3÷+”是“6+(8-2)*2÷3”的逆波蘭表達(dá)式
數(shù)學(xué)運(yùn)算表達(dá)式
逆波蘭表達(dá)式
逆波蘭表達(dá)式的值
轉(zhuǎn)換
計(jì)算
實(shí)踐與體驗(yàn)
如何轉(zhuǎn)換逆波蘭表達(dá)式？
體驗(yàn)獲取3+4*2-7的逆波蘭表達(dá)式
逆波蘭表達(dá)式結(jié)果是：
實(shí)踐與體驗(yàn)
動(dòng)畫(huà)演示:
體驗(yàn)獲取3+4*2-7的逆波蘭表達(dá)式
運(yùn)算符棧
表達(dá)式：
3
+
4
*
2
7
-
結(jié)果：
設(shè)計(jì)算法：如何將中綴表達(dá)式轉(zhuǎn)為后綴表達(dá)式（無(wú)括號(hào)）
1、初始化運(yùn)算符棧S1
2、依次從數(shù)組中取出各個(gè)字符，根據(jù)字符做不同處理
3、遇到運(yùn)算數(shù)時(shí)，將其輸出
4、遇到運(yùn)算符時(shí)，比較其與S1棧頂運(yùn)算符的優(yōu)先級(jí):
5、重復(fù)步驟2至4，直到表達(dá)式遍歷結(jié)束
6、將S1中剩余的運(yùn)算符依次彈出
實(shí)踐與體驗(yàn)
活動(dòng)2：逆波蘭式的算法設(shè)計(jì)
設(shè)計(jì)算法：如何將中綴表達(dá)式轉(zhuǎn)為后綴表達(dá)式（無(wú)括號(hào)）
1、初始化運(yùn)算符棧S1
2、依次從數(shù)組中取出各個(gè)字符，根據(jù)字符做不同處理
3、遇到運(yùn)算數(shù)時(shí)，將其輸出
4、遇到運(yùn)算符時(shí)，比較其與S1棧頂運(yùn)算符的優(yōu)先級(jí):
如果運(yùn)算符棧S1為空，則直接將此運(yùn)算符入棧；否則如果優(yōu)先級(jí)比棧頂運(yùn)算符的高，也將運(yùn)算符壓入S1；否則將S1棧頂?shù)倪\(yùn)算符彈出。再次轉(zhuǎn)到4與S1中新的棧頂運(yùn)算符相比較。
5、重復(fù)步驟2至4，直到表達(dá)式遍歷結(jié)束
6、將S1中剩余的運(yùn)算符依次彈出
實(shí)踐與體驗(yàn)
活動(dòng)3：逆波蘭式的算法設(shè)計(jì)
活動(dòng)3：體驗(yàn)算術(shù) 6+(5*2+8)/9的逆波蘭表達(dá)式的轉(zhuǎn)化過(guò)程
6
*
5
*
2
結(jié)果：
9
/
運(yùn)算符棧
如何轉(zhuǎn)換逆波蘭表達(dá)式
實(shí)踐與體驗(yàn)
（
)
活動(dòng)3：體驗(yàn)算術(shù) 6+(5*2+8)/9的逆波蘭表達(dá)式的轉(zhuǎn)化過(guò)程
6
+
5
*
2
結(jié)果：
9
/
運(yùn)算符棧
如何轉(zhuǎn)換逆波蘭表達(dá)式
實(shí)踐與體驗(yàn)
（
)
+
8
6 5 2 * 8 + 9 / +
6
5
2
*
8
+
+
+
/
9
(
*
/
+
活動(dòng)4設(shè)計(jì)算法：如何將中綴表達(dá)式轉(zhuǎn)為后綴表達(dá)式（有括號(hào)）
1、初始化運(yùn)算符棧S1
2、依次從數(shù)組中取出各個(gè)字符，根據(jù)字符做不同處理
3、遇到操作數(shù)時(shí)，將其輸出
4、遇到運(yùn)算符時(shí)，比較其與S1棧頂運(yùn)算符的優(yōu)先級(jí):
5 、遇到括號(hào)時(shí):
6、重復(fù)步驟2至5，直到表達(dá)式遍歷結(jié)束
7、將S1中剩余的運(yùn)算符依次彈出;
實(shí)踐與體驗(yàn)
活動(dòng)4設(shè)計(jì)算法：如何將中綴表達(dá)式轉(zhuǎn)為后綴表達(dá)式（有括號(hào)）
1、初始化運(yùn)算符棧S1
2、依次從數(shù)組中取出各個(gè)字符，根據(jù)字符做不同處理
3、遇到操作數(shù)時(shí)，將其輸出
4、遇到運(yùn)算符時(shí)，比較其與S1棧頂運(yùn)算符的優(yōu)先級(jí):
若S1為空，或棧頂運(yùn)算符為左括號(hào)“(”,則直接將此運(yùn)算符入棧;否則，若優(yōu)先級(jí)比棧頂運(yùn)算符的高，也將運(yùn)算符壓入S1(注意必須是高，相同和低于都不行);否則，將S1棧頂?shù)倪\(yùn)算符彈出，再次轉(zhuǎn)到4與S1中新的棧頂運(yùn)算符相比較.
5 、遇到括號(hào)時(shí):
如果是左括號(hào)“(”，則直接壓入S1;如果是右括號(hào)“)”，則依次彈出S1棧頂?shù)倪\(yùn)算符，直到遇到左括號(hào)為止，此時(shí)將這一對(duì)括號(hào)丟棄
6、重復(fù)步驟2至5，直到表達(dá)式遍歷結(jié)束
7、將S1中剩余的運(yùn)算符依次彈出
實(shí)踐與體驗(yàn)
實(shí)踐與小結(jié)
1.通過(guò)子彈進(jìn)出彈匣理解棧的概念，棧的基本操作
2.通過(guò)活動(dòng)一“進(jìn)制轉(zhuǎn)換”，實(shí)踐與體驗(yàn)“轉(zhuǎn)換逆波蘭表達(dá)式”
理解用棧思想解決問(wèn)題的過(guò)程
棧是一種先進(jìn)后出，后進(jìn)先出的線性表

展開(kāi)更多......

收起↑