資源簡(jiǎn)介

(共26張PPT)
選擇性必修1《數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)》
第三章 字符串、隊(duì)列和棧
3.3 棧的概念、特性及基本操作
情境導(dǎo)入
消毒桶的餐盤
知識(shí)講解
1.棧的概念【一種受限的線性表，僅允許在一端插入或刪除】
棧頂：
棧底：
李嵐
張棟
陳思思
劉力源
棧頂：
棧底：
允許插入或刪除的一端
表的另一端
2.棧的特性
李覽
張棟
陳思思
劉力源
棧頂：
棧底：
（1）先進(jìn)后出、后進(jìn)先出
最后入棧的棧頂元素“李覽”最先出棧；
最先入棧的棧底元素“劉力源”最后出棧。
（2）有限序列性
棧可以為空，也可以包含多個(gè)元素。
棧中元素存在線性關(guān)系，棧頂元素有一個(gè)前驅(qū)點(diǎn)，棧底元素有一個(gè)后繼點(diǎn)。
其他元素既有一個(gè)前驅(qū)又有一個(gè)后繼。
？
問(wèn)題與討論
棧與隊(duì)列有什么相同點(diǎn)和不同點(diǎn)？
不同點(diǎn) 相同點(diǎn)
棧 先進(jìn)后出、后進(jìn)先出； 只允許在一端進(jìn)行操作 一種受限制的線性表
只允許在端點(diǎn)操作
隊(duì)列 先進(jìn)先出、后進(jìn)后出； 出隊(duì)（隊(duì)首）、入隊(duì)（隊(duì)尾）
3.3.2 棧的基本操作
棧可用數(shù)組實(shí)現(xiàn)的原因——按順序結(jié)構(gòu)存儲(chǔ)
C
B
A
棧頂：top=2
棧底
A B C
數(shù)組st 0 1 2
①圖為棧結(jié)構(gòu)
②圖為用數(shù)組st存儲(chǔ)該棧
當(dāng)top=0時(shí)，st[top]存儲(chǔ)棧底元素“A”
top=1時(shí)，st[top]存儲(chǔ)棧中第2個(gè)元素“B”
top=2時(shí)，st[top]存儲(chǔ)棧頂元素“C”
棧頂元素有一個(gè)前驅(qū)點(diǎn)，棧底元素有一個(gè)后繼點(diǎn)
使用top變量來(lái)記錄棧頂元素【在數(shù)組中的位置——棧頂元素的位置會(huì)變】
拓展鏈接
棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
利用鏈?zhǔn)酱鎯?chǔ)方式實(shí)現(xiàn)的棧稱為鏈棧。它可以用單鏈表的方式實(shí)現(xiàn)。如圖3.3.3所示，棧頂指針top為鏈棧的頭指針。鏈棧的優(yōu)點(diǎn)在于它克服了用數(shù)組實(shí)現(xiàn)的順序棧空間利用率不高的缺點(diǎn),但是要為每個(gè)棧元素分配額外的指針空間。
D
C
B
A ^
top
棧的基本操作
入棧
建棧
知識(shí)講解
1.建棧
在Python中，當(dāng)要存儲(chǔ)n個(gè)元素的棧時(shí)，可以用列表創(chuàng)建一個(gè)長(zhǎng)度為n的棧。例如，要使4個(gè)字母“A”“B”“C”“D’按序人棧、出棧,可以建一個(gè)長(zhǎng)度為4的棧st，元素初始值均為空串。為了操作方便，把指向棧頂元素的指針變量top值設(shè)置為-1。
Python 代碼實(shí)現(xiàn)如下:
top=-1
st=[“ ”]*4
建隊(duì)與建棧的區(qū)別？
2.入棧、出棧
入棧又叫壓棧操作，把數(shù)據(jù)元素壓人棧頂。每次入棧時(shí)，棧頂指針變量top值加1,再給st[top]賦值。字母“A”“B”“C”“D”按序入棧的過(guò)程如圖3.3.4所示。
A
top=0
top=1
C
B
A
B
A
top=3
D
C
B
A
top=2

圖3.3.4 st棧中的入棧過(guò)程
top=1
C
B
A
B
A
top=3
D
C
B
A
top=2

Python代碼實(shí)現(xiàn)如下：
top=top+1 #top=0
st[top]="A" #字母A入棧
top=top+1 #top=1
st[top]="B" #字母B入棧
top=top+1 #top=2
st[top]="C" #字母C入棧
top=top+1 #top=3
st[top]="D" #字母D入棧
A
top=0
問(wèn)題與討論
編號(hào)為1、2、3、4的4列火車，按順序開(kāi)進(jìn)一個(gè)棧式結(jié)構(gòu)的站點(diǎn)。問(wèn):開(kāi)出火車站的順序有多少種 請(qǐng)寫出所有可能的出棧序列。
出棧順序：1234 1243 1324 1342 1432
2134 2143 2314 2341 2431
3214 3241 3421
4321
共14種出棧方式
Python程序編寫：十進(jìn)制n轉(zhuǎn)二進(jìn)制
n=int(input("請(qǐng)輸入任意十進(jìn)制數(shù)n："))
number=n
s=""
while n!=0:
r=n%2
s=str(r)+s
n=n//2
print("十進(jìn)制數(shù)%d的二進(jìn)制數(shù)是:%s"%(number,s))
輸出格式要求
對(duì)于第一章項(xiàng)目挑戰(zhàn)中的“用戶角色特征值”轉(zhuǎn)換成二進(jìn)制，可以采用“除二取余法”，并利用棧結(jié)構(gòu)存儲(chǔ)每次轉(zhuǎn)換過(guò)程中得到的余數(shù)。
以特征值6為例，轉(zhuǎn)成二進(jìn)制的過(guò)程如圖3.3.5所示。
除二取余數(shù)的過(guò)程中:
特征值的變化為6→3→1→0;
每一步得到的余數(shù)為0→1→1;
按序人棧，當(dāng)特征值變?yōu)?時(shí)，依次取出棧中元素，得到對(duì)應(yīng)的二進(jìn)制數(shù)“110”。
【變量意義】
棧st:每次得到的余數(shù)，
number:特征值，
top:棧頂位置。
“除二取余數(shù)” 的入棧和出棧過(guò)程
0
top=0
top=1
1
1
0
1
0
top=2
number=3 number=1 number=0
入棧
1
1
0
top=2
top=1
1
0
0
top=0
top=-1
出棧
程序 測(cè)試結(jié)果
st=[-1]*100 top=-1 number=int(input("請(qǐng)輸入十進(jìn)制數(shù)：")) while number>0: x=number % 2 top=top+1 st[top]=x #入棧 number=number//2 while top>=0: #棧空標(biāo)志top=-1 print(st[top],end=“”) #輸出棧元素 top=top-1 請(qǐng)輸入十進(jìn)制數(shù)：13
輸出：
1101
例1 括號(hào)匹配
數(shù)學(xué)計(jì)算式： （ a ÷（ b – c ）+ d ）× e
1 2 3 4 5 6 7 8 9 10 11 12 13
位置1 位置11
位置4 位置8
數(shù)學(xué)計(jì)算式： a ÷（ b – c ））
1 2 3 4 5 6 7 8
位置8無(wú)匹配括號(hào)！！！
（1）抽象與建模
數(shù)學(xué)計(jì)算式中既有數(shù)字，又有加減乘除等運(yùn)算符號(hào)，判斷括號(hào)是否匹配時(shí)，可以忽略這些括號(hào)以外的數(shù)字和運(yùn)算符號(hào)。
對(duì)于數(shù)學(xué)計(jì)算式: (a÷(b-c)+d)x e，括號(hào)的序列如圖3.3.8所示:
（ （ ） ）
1 2 3 4
匹配標(biāo)準(zhǔn)：左右括號(hào)數(shù)量相等 and 位置匹配
棧結(jié)構(gòu)設(shè)計(jì)：
遇到左括號(hào)出棧；遇到右括號(hào)，將棧頂?shù)淖罄ㄌ?hào)出棧
判斷步驟如下：
①棧空，出現(xiàn)右括號(hào)時(shí)，不匹配。
②掃描結(jié)束，棧中還有左括號(hào)時(shí)，不匹配。
③掃描結(jié)束，棧空，則匹配。
！！！
（2）設(shè)計(jì)算法 ------ (a÷(b-c)+d)x e
設(shè)置一個(gè)棧st和棧頂指針top，從左往右逐步處理數(shù)學(xué)計(jì)算式。
若是左括號(hào)，棧頂指針 top值加1，并將其壓入棧中。【入棧操作】
若是右括號(hào):
如果top大于-1，那么棧中有元素，把棧頂?shù)淖罄ㄌ?hào)彈出，top值減1，表示該右括號(hào)與彈出的左括號(hào)相匹配;
如果top等于-1，棧為空，表示沒(méi)有與該右括號(hào)相匹配的左括號(hào)，是不匹配的數(shù)學(xué)計(jì)算式。
如果數(shù)學(xué)計(jì)算式處理完畢，棧中還有左括號(hào)，那么它也是不匹配的數(shù)學(xué)計(jì)算式。
（
下標(biāo)
1
top 0
下標(biāo)
top 1
0
（
（
（
下標(biāo)
1
top 0
下標(biāo)
1
0
top=-1
”(” ”(” ”)” ”)”
！！！
程序 測(cè)試結(jié)果
st=[""]*100 top=-1 flag=True #標(biāo)記是否有不匹配的情況 s=input("請(qǐng)輸入數(shù)學(xué)計(jì)算式：") for i in range(len(s)): if s[i]=="(": top=top+1 st[top]=s[i] elif s[i]==")": if top==-1: flag=False break else: top=top-1 if top>=0: #棧中還有做括號(hào) flag=False if flag: print("括號(hào)匹配") else: print("括號(hào)不匹配") 請(qǐng)輸入數(shù)學(xué)計(jì)算式：(((a+b)*(c-d)-e)/f)
括號(hào)匹配
請(qǐng)輸入數(shù)學(xué)計(jì)算式：((a+b)*c-d)+(e
括號(hào)不匹配
拓展鏈接
用列表自帶的函數(shù)和方法實(shí)現(xiàn)的棧
Python中用列表自帶的函數(shù)和方法可以實(shí)現(xiàn)建棧、入棧、出棧、棧中元素個(gè)數(shù)的統(tǒng)計(jì)等操作。例如：
stacklist=[] #建立一個(gè)空棧
stacklist.append("A") #字母A入棧
stacklist.append("B") #字母B入棧
print(stacklist[1]) #輸出棧頂元素，為字母B
print(len(stacklist)) #輸出棧中元素的個(gè)數(shù)，為2
stacklist.pop() #彈出棧頂元素
print(len(stacklist)) #輸出棧中元素的個(gè)數(shù)，為1，是字母A
實(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í)踐內(nèi)容:
輸入逆波蘭表達(dá)式，寫一個(gè)程序，輸出該逆波蘭表達(dá)式的值。
實(shí)踐步驟:
1.分析逆波蘭表達(dá)式的計(jì)算方法。根據(jù)題意中的計(jì)算過(guò)程，用一個(gè)棧存儲(chǔ)數(shù)字。從左往右掃描該表達(dá)式，遇到數(shù)字時(shí)，入棧;遇到運(yùn)算符號(hào)時(shí)，把處于棧最上方的兩個(gè)元素依次出棧，用運(yùn)算符計(jì)算，并把計(jì)算結(jié)果壓入棧中。如此反復(fù)操作，直至表達(dá)式掃描結(jié)束。
2.根據(jù)算法分析，設(shè)計(jì)程序。
結(jié)果呈現(xiàn)：
輸入 輸出
6 8 2 – 2 * 3 ÷ + 10
思考與練習(xí)
1.如何區(qū)分取棧頂元素與出棧操作 用程序如何實(shí)現(xiàn)
2.元素a, b, c, d,e按序入棧,在所有的出棧序列中,以元素d開(kāi)頭的出棧序列是哪些
出棧：原來(lái)的棧頂元素被刪掉，由下一個(gè)替代；
取棧頂元素：只是獲取棧頂元素的值，不刪除該元素；
d c b a
decba
dceba
dcbea
dcbae 一共4種出棧順序
棧的概念
棧的特性
棧的基本操作
棧的簡(jiǎn)單應(yīng)用
課堂小結(jié)
學(xué)習(xí)評(píng)價(jià)
對(duì)自己和同伴的表現(xiàn)進(jìn)行客觀的評(píng)價(jià)，并思考后續(xù)完善的方向。（5=優(yōu)秀，4=超出一般水平，3=滿意，2=有待改進(jìn)，1=不太理想）
評(píng)分項(xiàng) 自我評(píng)價(jià) 同學(xué)互評(píng)
能從新課導(dǎo)入中的感知棧結(jié)構(gòu)的應(yīng)用 5 4 3 2 1 5 4 3 2 1
能理解棧的概念、特性。 5 4 3 2 1 5 4 3 2 1
能自主學(xué)習(xí)教材中“棧的基本操作”，并遷移完成棧的出隊(duì)操作。 5 4 3 2 1 5 4 3 2 1
能利用棧的基本操作，解決一些簡(jiǎn)單的含有棧結(jié)思想的問(wèn)題。 5 4 3 2 1 5 4 3 2 1
謝謝觀看

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

收起↑