栈的应用教学设计(共7页)

1、 栈的应用 教学设计课程名称数据结构授课内容数据结构第三章第二节授课时间13-14分钟授课题目栈的应用所属学科计算机课程类型本科生专业必修课适用对象工科计算机相关专业本科生使用教具投影仪、激光笔教学背景在现实生活中，栈的应用十分广泛,如数制转换，迷宫求解，背包问题等。栈是一种特殊的线性表，限定仅在表尾进行插入或删除操作。栈的特点是“后进先出”。教学目的知识目标：理解栈的定义和特点；掌握用堆栈进行中缀表达式求值的实现方法和算法思想；熟悉算符之间的优先关系。能力目标：通过求解栈的出栈序列、通过堆栈求值中缀表达式等实例分析，让学生学会运用栈的知识解决如中缀表达式求值、后缀表达式等实际问题，提高学生的

2、认识能力和实践能力，培养创新精神。情感目标：通过栈在计算机、工程实践及生活中的应用，培养学生举一反三，学以致用的意思，让学生感受探索的乐趣和成功地喜悦，充分体会教学知识在实际生活中的广泛应用。教学重点和难点重点: 栈的特点“后进先出”、应用栈解决实际问题。难点: 运用栈进行中缀表达式求值。思路设计问题引入通过数制转换，迷宫求解，背包问题实例，引入新课。栈的定义.栈是一种特殊的线性表，是限定在表的一端进行插入和删除操作的线性表。栈的特点栈的特点是“后进先出”。栈的出栈序列通过实例，辅助flash动画求解栈的出栈序列。栈的应用举例通过实例，通过堆栈实现中缀表达式求值。思考题.用栈如何将中缀表达式转

3、为后缀表达式？ 小结.内容总结方法手段教学方法: “问题链式”教学法、启发式教学法教学手段: 多媒体、flash动画、算法演示系统辅助教学所用教材李春葆，数据结构，清华大学出版社，2013年。教学过程设计步骤时间主要内容及任务教师及学生活动安排目标第一步（5分钟）通过数制转换等实例，引入栈的定义和特点，采用“问题链式” 教学法，通过举例、flash动画等教学辅助手段，讲解栈的出栈序列如何求解？老师讲解，采取提问，举例等方式，与学生的双向互动交流。1、提出问题“栈的出栈序列如何求解？”2、通过flah动画演示出栈序列，师生互动。3、解决问题。使学生了解栈的定义和特点。第二步（7分钟）主要采用启发

4、式教学法和“问题链式”教学法，并通过重点讲解、算法演示系统、课堂讨论等教学方法，讲解中缀表达式求值如何通过堆栈来实现？ 老师讲解，采取提问，举例等方式，与学生的双向互动交流。1、首先提出问题“中缀表达式求值如何通过堆栈来实现？ ”2、采用启发式教学法，重点讲解用堆栈进行中缀表达式求值的实现方法、算符之间的优先关系以及算法思想。3、通过算法演示系统演示求解过程，师生互动。4、最后得到结论。使学生掌握用堆栈进行中缀表达式求值的实现方法和算法思想。第三步（2分钟）进行本次课的小结首先进行本次课的小结，然后思考“用栈如何将中缀表达式转为后缀表达式？ ”加强学生对堆栈的理解和应用。总结分析通过本次教学，

5、采用“问题链式”和启发式教学法，使学生了解栈的定义和特点；掌握用堆栈进行中缀表达式求值的实现方法和算法思想；熟悉算符之间的优先关系。教学内容课堂组织 第二节 栈的应用一、问题引入 在现实生活中，栈的应用十分广泛,如数制转换，迷宫求解，背包问题等。本次课程的教学要求是理解栈的定义和特点；理解表达式求值的实现。重点内容是栈的特点和栈的应用。难点是中缀表达式求值。二、栈的定义和特点栈是一种特殊的线性表，是限定在表的一端进行插入和删除操作的线性表。栈的表尾称为栈顶，表头称为栈底，不含元素的空表称为空栈。栈的特点是“后进先出”。（动画演示）通过实例讲解顺序栈的表示：利用一组地址连续的存储单元依次存放自栈

6、底到栈顶的数据元素,同时附设指针top指示栈顶元素在顺序栈中的位置。例如：这个堆栈是用一维数组表示的，top指针指向-1，现在有一个序列进行进栈操作，a，b，c依次进栈，大家判断一下，它们可能的出栈序列。三、栈的出栈序列例1、已知a，b，c顺序入栈，求出所有可能的出栈序列。分析：条件：先是top指针加1，元素a进栈，top指针加1，b进栈，top指针加1，c进栈， 结果1：现在开始出栈，以c作为第一个出栈序列的开始元素，判断出栈序列。首先，c出栈，top指针减1，b出栈，top指针减1，a出栈，top指针减1，得到第一种可能性是c,b,a。结果2：如果清空之后，以b作为第一个出栈元素，可能的出

7、栈序列。a进栈，然后b进栈，b先出栈，a出栈，c进栈，c出栈，这是第二种可能性，b,a,c,依次类推，得到其它的几种可能性。答：有五种可能性，如下所示：1. c b a ；2. b a c ；3. b c a ； 4. a c b ；5. a b c 。思考：出栈顺序有可能出现c a b的情况吗？方法：总结分析学生回答结果，给出正确结论：是不可能出现c a b的情况。因为它违背了栈的特点“后进先出”。四、栈的应用举例任何一个表达式都是由操作数、运算符和界限符组成的。后两项统称为算符，算符集合命名为OP。引入问题：如何用堆栈实现表达式求值？表达式求值有三种形式。1) 中缀表示：<操作数&g

8、t;<运算符><操作数>2) 前缀表示：<运算符><操作数><操作数>3) 后缀表示：<操作数><操作数><运算符>以中缀表达式为例，进行重点讲解。例2、用栈求解表达式21+44-3*6的值。 # 21+44-3*6#实现方法：设置一个运算符栈和一个操作数栈。1、 算符间的优先关系求值规则：1）先乘除,后加减；2）先括号内,后括号外；3）同类运算,从左至右。约定： q1-栈顶的运算符 q2-当前的运算符 当q1=#，为开始符 当q2=#，为结束符根据上述优先关系表，可见21+44-3*6#中- &l

9、t;*， * >#。2、算法基本思想1）首先置#为运算符栈的栈底元素, 操作数栈为空栈；2) 依次读入表达式中各个字符，如果判断为操作数则OPND栈，如21，44，进操作数栈；若为运算符2，则和OPTR的栈顶元素1比较优先级，1和2进行比较。 当1 < 2 ，2 进栈； 当1 = 2 ，1 出栈； 若1 > 2 ，1 出栈，先进行操作数求值；然后运算结果再进栈。3、算法编程实现OperandType EvaluateExpression ( ) InitStack(OPTR); push(OPTR,#);InitStack(OPND);read(w); While NOT (

10、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; RETURN( POP

11、(OPND)ENDF;4、算法执行过程# 21+44-3*6# 1）“#”先压入到运算符栈，即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(OPTR, * ); 8）pu

12、sh(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出堆栈，结果为47。 算法演示结束。小结: 1) 栈是限定在表的一端进行插入和删除操作的线性表；栈的特点是“后进先出” 。 2) 栈的顺序存储结构是用一维数组来实现的。 3) 栈的应用主要有中缀表达式求值、后缀表达式求值、数制转换等。思考：用栈如何将中缀表达式转为后缀表达式？ 问题引入1分钟通过如数制转换，迷宫求解，背包问题等问题，引导大家形象地思考栈的概念。重点讲解1分钟通过动画演示，引导学生理解栈的定义和栈的特点。 重点讲解2分钟 通过动画演示，重点讲解栈的出栈序列。 使学生熟练理解栈的定义、特点及基本操作。 课堂提问1分钟 通过提问，引导学生求解栈的出栈序列。重点讲解1分钟 讲解表达式求值的三种形式。以中缀表达式为例，进行重点讲