高中信息技术教科版 (2019)选修1 数据与数据结构5.1 栈结构及其实现教案及反思

课 题

5-1栈结构及其实现

课时安排

1

课型

素养目标

课程标准要求：1.理解栈的基本概念及其特征。

2. 理解符号匹配的基本原理。
3. 理解算术表达式求值的基本原理。
4. 掌握栈的抽象数据类型的定义。

信息意识：信息意识：能够根据解决问题的需要，自觉、主动地寻求恰当的方式获取与处理信息；在合作解决问题的过程中，愿意与团队成员共享信息，实现信息的更大价值。

计算思维：针对给定的任务进行需求分析，明确需要解决的关键问题。能提取问题的基本特征，进行抽象处理，并用形式化的方法表述问题。运用队列结构设计解决问题的方案，结合队列的相关操作，编程实现。

数字化学习与创新：1.理解栈的基本概念及其特征，掌握栈的抽象数据类型的定义。

 2.熟练运用数据结构解决生活中的真实问题，并在此过程中自主或协作探究；能够评估常见的数字化资源与工具对学习数据结构的价值，根据需要合理选择。

信息社会责任：能够分析数据与社会各领域间的关系，自觉遵守相应的理论道德和法律法规。

教学重点

1.理解栈的基本概念及其特征。

2.理解符号匹配的基本原理。

教学难点

1. 理解栈的基本概念及其特征。
2. 掌握栈的抽象数据类型的定义。

教学方法

讲解法、互动法，启发式教学法

学习方法

互动、讨论

教学过程

个别化教案

一、考勤。

二、课前测评。

三、引入

栈，是一种特殊的线性表，其插入及删除的操作都在线性表的同一端进行。这一端称为栈顶，另一端称为栈底。就类似于餐厅里的一摞盘子，后放的盘子在上方，也会先被人拿走。栈具有“后进先出”的逻辑特性。栈在计算机科学中有着广泛的应用，递归函数的实现就利用了栈这种数据结构，在递归时，计算机会维护一个递归工作栈，当一个递归函数被调用时，被调函数的局部变量、形参的值以及一个返回地址就会储存在递归工作栈中。运行时按照后进先出的顺序，进行函数执行，完成递归操作。

浏览网页时，单击一个个超链接，可以不断打开新的页面，单击浏览器上的“后退”按钮，又可以一步步返回到浏览过的网页。类似地，各类编辑软件也大都提供编辑操作的历史记录功能，保存用户的每次编辑操作，如果出现错误操作，单击“撤销”按钮，就可以一步步返回到此前的编辑状态。在这些习以为常的操作行为中，蕴含着一个基础但影响深远的数据结构——栈。

栈：栈是一种出人有序的数据集合。作为一种操作受限的线性结构，数据元素的插人和删除都仅发生在同一端，这一端为栈顶(Top)， 相应地，另一端则为栈底(Bottom)。数据元素的插入操作一般称为人栈(Push)，又称进栈；删除操作则称为出栈(Pop)，又称退栈。

栈的特征：
出数据元素人栈和出栈的次序正好相反，并且所有操作都是对栈顶数据元素进行。距离栈底越近的数据元素，留在栈中的时间就越长，而最新加入栈的数据元素会被最先移除，这种特点通常称为“后进先出”， 即Last In图5.1.5栈示意First Out， 简称LIFO。
栈抽象数据类型：
从以上活动可以看出，栈的基本操作主要包括创建空栈、人栈、出栈、查看栈顶数据元素及判断栈是否为空。为了便于在程序中使用栈解决问题，需要定义栈抽象数据类型(ADT Stack)。
栈抽象数据类型的接口如下。
DtaStack:
· StackO：创建并返回一个不包含任何数据元素的空栈。
· push(item)： 将数据元素item压入栈顶，无返回值。
· popO：弹出并返回栈顶的数据元素。
· peek()：查看、返回但不移除栈顶的数据元素。
·isEmpty(：判断是否为空栈，返回布尔型的值。
· size(：计算并返回栈中数据元素的个数。

符号匹配:
符号的使用需要遵循一定的平衡原则：首先，每个左符号要恰好对应一个右符号；其次，每对左右符号要正确地嵌套，不能互相交错。如图5.2.1所示，符号串中每个左符号都有对应的右符号，且左右符号配对次序正确，因此该符号串符号匹配正确。

通过活动1，我们可以总结出以下符号匹配失败的三种可能：(1)左右符号配对次序不正确；
(2)右符号多于左符号；
(3)左符号多于右符号。

算术表达式求值：

表达式求值，就是计算表达式的值。在程序设计中，表达式求值的应用非常普遍，例如，在程序中通过求根公式可以算出一元二次方程的根。怎样编程计算一个字符串表达式的值?计算机利用了栈结构来进行表达式求值。

通过活动可以发现，先进入数字区的数后运算，后进入数字区的数先运算；先进入符号区的运算符后计算，后进入符号区的运算符先计算，就像两个栈一样，所以可以利用栈来实现表达式求值。

四、总结

1.栈的基本概念及其特征。

2.栈抽象数据类型。

3.符号匹配问题。

4.算术表达式求值。

作 业

板

书

设

计

1.栈的基本概念及其特征。

2.栈抽象数据类型。

3.符号匹配问题。

4.算术表达式求值。

教

学

反

思

教案查阅签字