棧的應(yīng)用教學(xué)設(shè)計(jì)

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)講解