




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
1、精選優(yōu)質(zhì)文檔-傾情為你奉上 棧的應(yīng)用 教學(xué)設(shè)計(jì)課程名稱數(shù)據(jù)結(jié)構(gòu)授課內(nèi)容數(shù)據(jù)結(jié)構(gòu)第三章第二節(jié)授課時(shí)間13-14分鐘授課題目棧的應(yīng)用所屬學(xué)科計(jì)算機(jī)課程類型本科生專業(yè)必修課適用對(duì)象工科計(jì)算機(jī)相關(guān)專業(yè)本科生使用教具投影儀、激光筆教學(xué)背景在現(xiàn)實(shí)生活中,棧的應(yīng)用十分廣泛,如數(shù)制轉(zhuǎn)換,迷宮求解,背包問題等。棧是一種特殊的線性表,限定僅在表尾進(jìn)行插入或刪除操作。棧的特點(diǎn)是“后進(jìn)先出”。教學(xué)目的知識(shí)目標(biāo):理解棧的定義和特點(diǎn);掌握用堆棧進(jìn)行中綴表達(dá)式求值的實(shí)現(xiàn)方法和算法思想;熟悉算符之間的優(yōu)先關(guān)系。能力目標(biāo):通過求解棧的出棧序列、通過堆棧求值中綴表達(dá)式等實(shí)例分析,讓學(xué)生學(xué)會(huì)運(yùn)用棧的知識(shí)解決如中綴表達(dá)式求值、后綴表
2、達(dá)式等實(shí)際問題,提高學(xué)生的認(rèn)識(shí)能力和實(shí)踐能力,培養(yǎng)創(chuàng)新精神。情感目標(biāo):通過棧在計(jì)算機(jī)、工程實(shí)踐及生活中的應(yīng)用,培養(yǎng)學(xué)生舉一反三,學(xué)以致用的意思,讓學(xué)生感受探索的樂趣和成功地喜悅,充分體會(huì)教學(xué)知識(shí)在實(shí)際生活中的廣泛應(yīng)用。教學(xué)重點(diǎn)和難點(diǎn)重點(diǎn): 棧的特點(diǎn)“后進(jìn)先出”、應(yīng)用棧解決實(shí)際問題。難點(diǎn): 運(yùn)用棧進(jìn)行中綴表達(dá)式求值。思路設(shè)計(jì)問題引入通過數(shù)制轉(zhuǎn)換,迷宮求解,背包問題實(shí)例,引入新課。棧的定義.棧是一種特殊的線性表,是限定在表的一端進(jìn)行插入和刪除操作的線性表。棧的特點(diǎn)棧的特點(diǎn)是“后進(jìn)先出”。棧的出棧序列通過實(shí)例,輔助flash動(dòng)畫求解棧的出棧序列。棧的應(yīng)用舉例通過實(shí)例,通過堆棧實(shí)現(xiàn)中綴表達(dá)式求值。思考
3、題.用棧如何將中綴表達(dá)式轉(zhuǎn)為后綴表達(dá)式? 小結(jié).內(nèi)容總結(jié)方法手段教學(xué)方法: “問題鏈?zhǔn)健苯虒W(xué)法、啟發(fā)式教學(xué)法教學(xué)手段: 多媒體、flash動(dòng)畫、算法演示系統(tǒng)輔助教學(xué)所用教材李春葆,數(shù)據(jù)結(jié)構(gòu),清華大學(xué)出版社,2013年。教學(xué)過程設(shè)計(jì)步驟時(shí)間主要內(nèi)容及任務(wù)教師及學(xué)生活動(dòng)安排目標(biāo)第一步(5分鐘)通過數(shù)制轉(zhuǎn)換等實(shí)例,引入棧的定義和特點(diǎn),采用“問題鏈?zhǔn)健?教學(xué)法,通過舉例、flash動(dòng)畫等教學(xué)輔助手段,講解棧的出棧序列如何求解?老師講解,采取提問,舉例等方式,與學(xué)生的雙向互動(dòng)交流。1、提出問題“棧的出棧序列如何求解?”2、通過flah動(dòng)畫演示出棧序列,師生互動(dòng)。3、解決問題。使學(xué)生了解棧的定義和特點(diǎn)。第
4、二步(7分鐘)主要采用啟發(fā)式教學(xué)法和“問題鏈?zhǔn)健苯虒W(xué)法,并通過重點(diǎn)講解、算法演示系統(tǒng)、課堂討論等教學(xué)方法,講解中綴表達(dá)式求值如何通過堆棧來實(shí)現(xiàn)? 老師講解,采取提問,舉例等方式,與學(xué)生的雙向互動(dòng)交流。1、首先提出問題“中綴表達(dá)式求值如何通過堆棧來實(shí)現(xiàn)? ”2、采用啟發(fā)式教學(xué)法,重點(diǎn)講解用堆棧進(jìn)行中綴表達(dá)式求值的實(shí)現(xiàn)方法、算符之間的優(yōu)先關(guān)系以及算法思想。3、通過算法演示系統(tǒng)演示求解過程,師生互動(dòng)。4、最后得到結(jié)論。使學(xué)生掌握用堆棧進(jìn)行中綴表達(dá)式求值的實(shí)現(xiàn)方法和算法思想。第三步(2分鐘)進(jìn)行本次課的小結(jié)首先進(jìn)行本次課的小結(jié),然后思考“用棧如何將中綴表達(dá)式轉(zhuǎn)為后綴表達(dá)式? ”加強(qiáng)學(xué)生對(duì)堆棧的理解和應(yīng)
5、用??偨Y(jié)分析通過本次教學(xué),采用“問題鏈?zhǔn)健焙蛦l(fā)式教學(xué)法,使學(xué)生了解棧的定義和特點(diǎn);掌握用堆棧進(jìn)行中綴表達(dá)式求值的實(shí)現(xiàn)方法和算法思想;熟悉算符之間的優(yōu)先關(guān)系。教學(xué)內(nèi)容課堂組織 第二節(jié) 棧的應(yīng)用一、問題引入 在現(xiàn)實(shí)生活中,棧的應(yīng)用十分廣泛,如數(shù)制轉(zhuǎn)換,迷宮求解,背包問題等。本次課程的教學(xué)要求是理解棧的定義和特點(diǎn);理解表達(dá)式求值的實(shí)現(xiàn)。重點(diǎn)內(nèi)容是棧的特點(diǎn)和棧的應(yīng)用。難點(diǎn)是中綴表達(dá)式求值。二、棧的定義和特點(diǎn)棧是一種特殊的線性表,是限定在表的一端進(jìn)行插入和刪除操作的線性表。棧的表尾稱為棧頂,表頭稱為棧底,不含元素的空表稱為空棧。棧的特點(diǎn)是“后進(jìn)先出”。(動(dòng)畫演示)通過實(shí)例講解順序棧的表示:利用一組地址
6、連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素,同時(shí)附設(shè)指針top指示棧頂元素在順序棧中的位置。例如:這個(gè)堆棧是用一維數(shù)組表示的,top指針指向-1,現(xiàn)在有一個(gè)序列進(jìn)行進(jìn)棧操作,a,b,c依次進(jìn)棧,大家判斷一下,它們可能的出棧序列。三、棧的出棧序列例1、已知a,b,c順序入棧,求出所有可能的出棧序列。分析:條件:先是top指針加1,元素a進(jìn)棧,top指針加1,b進(jìn)棧,top指針加1,c進(jìn)棧, 結(jié)果1:現(xiàn)在開始出棧,以c作為第一個(gè)出棧序列的開始元素,判斷出棧序列。首先,c出棧,top指針減1,b出棧,top指針減1,a出棧,top指針減1,得到第一種可能性是c,b,a。結(jié)果2:如果清空之后,以b作
7、為第一個(gè)出棧元素,可能的出棧序列。a進(jìn)棧,然后b進(jìn)棧,b先出棧,a出棧,c進(jìn)棧,c出棧,這是第二種可能性,b,a,c,依次類推,得到其它的幾種可能性。答:有五種可能性,如下所示:1. c b a ;2. b a c ;3. b c a ; 4. a c b ;5. a b c 。思考:出棧順序有可能出現(xiàn)c a b的情況嗎?方法:總結(jié)分析學(xué)生回答結(jié)果,給出正確結(jié)論:是不可能出現(xiàn)c a b的情況。因?yàn)樗`背了棧的特點(diǎn)“后進(jìn)先出”。四、棧的應(yīng)用舉例任何一個(gè)表達(dá)式都是由操作數(shù)、運(yùn)算符和界限符組成的。后兩項(xiàng)統(tǒng)稱為算符,算符集合命名為OP。引入問題:如何用堆棧實(shí)現(xiàn)表達(dá)式求值?表達(dá)式求值有三種形式。1) 中
8、綴表示:<操作數(shù)><運(yùn)算符><操作數(shù)>2) 前綴表示:<運(yùn)算符><操作數(shù)><操作數(shù)>3) 后綴表示:<操作數(shù)><操作數(shù)><運(yùn)算符>以中綴表達(dá)式為例,進(jìn)行重點(diǎn)講解。例2、用棧求解表達(dá)式21+44-3*6的值。 # 21+44-3*6#實(shí)現(xiàn)方法:設(shè)置一個(gè)運(yùn)算符棧和一個(gè)操作數(shù)棧。1、 算符間的優(yōu)先關(guān)系求值規(guī)則:1)先乘除,后加減;2)先括號(hào)內(nèi),后括號(hào)外;3)同類運(yùn)算,從左至右。約定: q1-棧頂?shù)倪\(yùn)算符 q2-當(dāng)前的運(yùn)算符 當(dāng)q1=#,為開始符 當(dāng)q2=#,為結(jié)束符根據(jù)上述優(yōu)先關(guān)系表,可見21
9、+44-3*6#中- <*, * >#。2、算法基本思想1)首先置#為運(yùn)算符棧的棧底元素, 操作數(shù)棧為空棧;2) 依次讀入表達(dá)式中各個(gè)字符,如果判斷為操作數(shù)則OPND棧,如21,44,進(jìn)操作數(shù)棧;若為運(yùn)算符2,則和OPTR的棧頂元素1比較優(yōu)先級(jí),1和2進(jìn)行比較。 當(dāng)1 < 2 ,2 進(jìn)棧; 當(dāng)1 = 2 ,1 出棧; 若1 > 2 ,1 出棧,先進(jìn)行操作數(shù)求值;然后運(yùn)算結(jié)果再進(jìn)棧。3、算法編程實(shí)現(xiàn)OperandType EvaluateExpression ( ) InitStack(OPTR); push(OPTR,#);InitStack(OPND);read(w)
10、; While NOT (w=#)AND (GetTop(OPTR)= #) ) IF w NOT IN op THEN push(OPND,w); read(w); ELSE CASE Precede(GetTop(OPTR),w) OF <: push(OPTR,c); read(w);=: pop(OPTR,x); if x=FUNCTION thenPUSH(OPND,x(POP(OPNE);read(w); >: b:= pop(OPND);a:= pop(OPND);theta:= pop(OPTR); push(OPND,Operate(a,theta,b);ENDC
11、; RETURN( POP(OPND)ENDF;4、算法執(zhí)行過程# 21+44-3*6# 1)“#”先壓入到運(yùn)算符棧,即push(OPTR,#); OPTR OPND 2)push(OPND,21) 2)# <+, push(OPTR, + ); 3)push(OPND,44) 4)* >-, b:= pop(OPND);a:= pop(OPND);theta:= pop(OPTR); 即 b= 44; a=21;21+44=65; push (OPND,65) 5)# <-, push(OPTR, - ); 6)push(OPND,3) 7)- <*, push(OP
12、TR, * ); 8)push(OPND,6) 9)* >#,b:= pop(OPND); a:= pop(OPND); theta:= pop(OPTR); 即 b= 3; a=6;3*6=18; push (OPND,18) 10)- >#,b:= pop(OPND); a:= pop(OPND); theta:= pop(OPTR); 即 b= 18; a=65; 65-18=47; push (OPND,47) 11)push(OPTR, + ); 12)# =#, pop(OPTR,x); RETURN( POP(OPND) 即 47出堆棧,結(jié)果為47。 算法演示結(jié)束。小
13、結(jié): 1) 棧是限定在表的一端進(jìn)行插入和刪除操作的線性表;棧的特點(diǎn)是“后進(jìn)先出” 。 2) 棧的順序存儲(chǔ)結(jié)構(gòu)是用一維數(shù)組來實(shí)現(xiàn)的。 3) 棧的應(yīng)用主要有中綴表達(dá)式求值、后綴表達(dá)式求值、數(shù)制轉(zhuǎn)換等。思考:用棧如何將中綴表達(dá)式轉(zhuǎn)為后綴表達(dá)式? 問題引入1分鐘通過如數(shù)制轉(zhuǎn)換,迷宮求解,背包問題等問題,引導(dǎo)大家形象地思考棧的概念。重點(diǎn)講解1分鐘通過動(dòng)畫演示,引導(dǎo)學(xué)生理解棧的定義和棧的特點(diǎn)。 重點(diǎn)講解2分鐘 通過動(dòng)畫演示,重點(diǎn)講解棧的出棧序列。 使學(xué)生熟練理解棧的定義、特點(diǎn)及基本操作。 課堂提問1分鐘 通過提問,引導(dǎo)學(xué)生求解棧的出棧序列。重點(diǎn)講解1分鐘 講解表達(dá)式求值的三種形式。以中綴表達(dá)式為例,進(jìn)行重點(diǎn)講解。 重點(diǎn)講解
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- “春瓶”名稱的釋義及其原始功能探究
- 新媒體裝置交互-洞察及研究
- 培訓(xùn)機(jī)構(gòu)績效管理辦法
- 公益放映預(yù)算管理辦法
- 隱私保護(hù)成本效益-洞察及研究
- 社會(huì)治理:近二十年國內(nèi)社會(huì)治理創(chuàng)新研究
- 2025版生產(chǎn)安全事故應(yīng)急預(yù)案5匯編
- 檔案耗材供應(yīng)管理辦法
- 構(gòu)成一般事故的指標(biāo)是
- 航空應(yīng)急救援體系
- 2025至2030中國直聯(lián)式真空泵行業(yè)市場現(xiàn)狀分析及競爭格局與投資發(fā)展報(bào)告
- 2025至2030中國無源光分路器行業(yè)發(fā)展趨勢分析與未來投資戰(zhàn)略咨詢研究報(bào)告
- 痛風(fēng)治療與護(hù)理課件
- T/CCBD 19-2022品牌餐廳評(píng)價(jià)規(guī)范
- 河南省南陽市內(nèi)鄉(xiāng)縣2025屆數(shù)學(xué)七下期末調(diào)研試題含解析
- 校際結(jié)對(duì)幫扶協(xié)議書
- 第四版(2025)國際壓力性損傷潰瘍預(yù)防和治療臨床指南解讀
- 企業(yè)電工面試題及答案
- 倉庫與生產(chǎn)線的有效對(duì)接計(jì)劃
- 《心律失常患者的護(hù)理》課件
- 2025江蘇省惠隆資產(chǎn)管理限公司招聘30人易考易錯(cuò)模擬試題(共500題)試卷后附參考答案
評(píng)論
0/150
提交評(píng)論