高中信息技術(shù)第三章 字符串、隊(duì)列和棧3.3 棧優(yōu)秀課件ppt

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