2020-2021学年2.设计算法优质ppt课件
展开第三单元 特殊的线性表
项目五 模拟实现软件的撤消功能
——栈的应用
第二课时 设计算法
❑教材分析
本节的主要内容是设计算法。通过以模拟实现软件的撤消功能为主线，整个项目分为问题分析、设计算法和程序实现三个部分。本节课时是通过分析撤消字符操作实例中输入、撤消两个操作，理解栈的“进栈（入栈）”“出栈”两大基本操作，通过活动让学生自行设计进栈、出栈操作和算法。在这一课时过程中，进一步培养学生的信息意识和计算思维。
❑教学目标
1.理解顺序栈存储的原理和特点；
2.能设计进栈、出栈的算法；
3.培养学生的信息意识和计算思维能力。
❑教学重点
1.理解栈后进先出的特点；
2.理解进栈、出栈操作的原理。
❑教学难点
1.理解进栈、出栈操作的原理。
2.培养学生的信息意识和计算思维能力。
❑教学方法
体验法、讲授法、讨论法、示例法
❑教学准备
计算机教室、多媒体设备、多媒体广播软件、教学课件、Python编程环境、学生上机练习的程序文件，预先编制的Python程序文件等。
❑教学过程
一、新课导入
复习上堂的内容——栈
1.核心概念
栈( stack)：是一种仅允许在表的一端进行插入或删除操作的线性表。这一端被称为栈顶(top)，栈也称为后进先出( last in first out,LIFO)线性表。
2.栈的抽象数据类型表示：
ADT Stack：
数据对象：D={ai｜ai,∈ ElemSet,i=l,2,…,n,n>=0}
数据关系：R={ai-1,ai>｜ai-1,ai ∈ D,i=2,…,n} #an为栈顶
基本操作：
def _init_(self) #初始化一个空栈
def SEmpty(self) #若栈空，则返回True,否则返回False
def GetTop(self) #返回栈的栈顶元素
def Push(self, e) #e元素进栈
def Pop(self) #返回出栈元素
二、设计算法
在文档中依次输入a,b,c,d,e后，这些字母会依次进栈点击一下“撤消”按钮，栈内最后一个字母就会出栈。
栈可以用数组来存储元素，也可以用链表存储元素。假设用数组存储元素，即用数组存放输入的字母，用一个变量作为栈顶指针，如图3-9中的top。栈顶指针始终指向栈内的最后的元素。
图3-9进栈示意
进栈和出栈的操作就可以用算法来描述了。
思考与讨论
栈与队列的操作有何不同？
栈的进栈出栈都从栈顶经过，栈底是封闭的；队列进队是在队尾进，出队是在队首出，队首与队尾都是不封闭的。
栈的操作特点是后进先出；队列的操作特点是先进先出。
栈在操作过程中只需要使用一个指针top；队列需要使用两个 front、rear。
三、栈的常用基本操作
进栈(push)：也称入栈，是向栈插入新元素，即把新元素插入到栈顶元素的上面，使之成为新的栈顶元素。
出栈(pop)：也称退栈，是删除栈顶元素，使其相邻的后一个元素成为新的栈顶
小贴士
用数组存储的栈称为顺序栈。为方便理解，本项目只存储字母。
1.进栈
进栈就是从栈底开始，按顺序逐步向栈内添加数据。
算法思想：若栈不满，则先将栈顶指针增1，然后送入进栈元素。栈满不能进栈。
def Push(self, e)：
#e为进栈元素，假设栈的容量为size
if (self. top==self. size-1）：
print("栈满，不能进栈")
else:
self. top=self. top+1
self.stack[self. top]=e
return
2.出栈
出栈就是从栈顶开始，按逆序逐步将栈内数据取出算法思想：若栈不空，则将栈顶指针所指空间内容取出赋予变量，然后将栈顶指针减1。栈空则没有元素可出。
def Pop(self):
if self. top==-1:
print(“栈空，没有元素出栈")
else:
e=self. Stack[self top]
self. top=self.top-1
return e
四、课堂活动
在算法流程框图中完成进栈和出栈操作(数组名和变量名可以自取)。
参考答案：
沪教版（2019）2.体验使用二分查找法查找商品精品ppt课件： 这是一份沪教版（2019）2.体验使用二分查找法查找商品精品ppt课件，文件包含项目九第二课时pptx、项目九第二课时doc等2份课件配套教学资源，其中PPT共44页， 欢迎下载使用。
沪教版（2019）3.程序实现评优课ppt课件： 这是一份沪教版（2019）3.程序实现评优课ppt课件，文件包含项目五第三课时pptx、项目五第三课时doc等2份课件配套教学资源，其中PPT共14页， 欢迎下载使用。
高中信息技术沪教版（2019）选修1 数据与数据结构1.分析问题完美版课件ppt： 这是一份高中信息技术沪教版（2019）选修1 数据与数据结构1.分析问题完美版课件ppt，文件包含项目五第一课时pptx、项目五第一课时doc等2份课件配套教学资源，其中PPT共23页， 欢迎下载使用。
