高中信息技术沪教版（2019）选修1 数据与数据结构1.分析问题完美版课件ppt

第三单元 特殊的线性表

项目五 模拟实现软件的撤消功能

——栈的应用

第一课时 分析问题

❑教材分析

本节的主要内容是分析问题。通过以模拟实现软件的撤消功能为主线，整个项目分为问题分析、设计算法和程序实现三个部分。本节课时是从“撤消字符操作”的实例中分析出后输入的字符先撤消的思想方法，将这一思想方法图形化后，引出另一种受限制的线性结构——“栈”的概念，并通过活动帮助学生加深理解。在这一课时过程中，进一步培养学生的信息意识和计算思维。

❑教学目标

1.理解栈的概念和特征；

2.理解栈顶指针的作用；

2.培养学生的信息意识和计算思维能力。

❑教学重点

1.理解栈的概念和特征。

❑教学难点

1.理解栈的概念和特征。

2.培养学生的信息意识和计算思维能力。

❑教学方法

体验法、讲授法、讨论法、示例法

❑教学准备

　　计算机教室、多媒体设备、多媒体广播软件、教学课件、Python编程环境、学生上机练习的程序文件，预先编制的Python程序文件等。

❑教学过程

一、新课导入

队列是一种操作受限制的线性表，只允许先进先出。还有一种操作受限制的线性表，即栈，它的特点和队列恰好相反，是后进先出。日常学习和工作中，人们使用的许多应用软件，如办公软件大多提供了“撤消”功能。该功能允许用户撤消有限的操作步骤，方便恢复到误操作之前的状态(图3-6)。而这一功能就可以借助栈来实现。

二、分析问题

要实现撤消功能，首先要思考操作的顺序问题。例如，输入 abcde的操作顺序是先输入a,然后是b,再是c……而撤消的时候是按逆序，先撤消e,再撤消d……可以看出，后输入的先撤消，先输入的后撤消，如图3-7所示。

如果用某种后进先出的数据结构来键入a存储a,b,c,d,e的话，可以方便地实1操作现撤消。这种数据结构称为栈。

图3-7撤消菜单

思考与讨论

生活中是否还有其他类似的后进先出的例子？

弹匣装子弹；“QQ音乐”在顺序播放模式下，最后选入播放列表的歌曲第一个播放，第一个进入列表的最后个播放等。

三、栈

核心概念

栈( stack)：是一种仅允许在表的一端进行插入或删除操作的线性表。这一端被称为栈顶(top)，栈也称为后进先出( last in first out,LIFO)线性表。

小贴士

栈属于线性表的一种，是操作上有限制的线性表，只允许在栈顶进行操作。

要理解栈这个概念，首先要明白“栈”这个字的字面意思，如此才能把握本质。“栈”的意思是存储货物或供旅客住宿的地方，可引申为仓库、中转站，所以引入到计算机领域里就是指数据暂时存储的地方，是一种只能在表的一端进行插入(进栈或人栈)和删除(出栈或是退栈)操作的线性表。它按照后进先出的原则存储数据，先进入的数据被压入栈底，最后进入的数据在栈顶，需要读数据的时候从栈顶开始弹出数据(最后进去的一个数据被第一个读出)。日常生活中有很多后进先出的例子，如碗柜里的一叠碗(图3-10)，先放进去的在下面，后放进去的在上面，取碗时只能从上面开始取，即先取到的是最后放上去的；又如冰糖葫芦串(图3-11)，先串进去的冰糖葫芦在下面，后串进去的冰糖葫芦在上面，吃的时候通常是后串进去的冰糖葫芦先吃到，而先串进去的冰糖葫芦后吃到。

图3-10碗柜里的碗                 图3-11冰糖葫芦串

栈的抽象数据类型表示如下：

栈有两种存储方式，一种是用数组存储，这种方式存储的栈称为顺序栈；另一种用链表存储，这种方式存储的栈称为链式栈。一般根据进栈元素个数是否确定来选择存储结构，元素个数确定的用顺序栈，不确定的用链式栈。             

四、课堂活动

1.请尝试写出栈的抽象数据类型定义。

2.网上搜索列车调度方法，根据图3-8画出用栈进行调度的过程示意图，并说

明调度的原理。

图3-8列车调度示意

参考答案：

1.

2.