资源简介

中小学教育资源及组卷应用平台
第三单元
特殊的线性表
项目五
模拟实现软件的撤消功能
——栈的应用
第二课时
设计算法
?教材分析
本节的主要内容是设计算法。通过以模拟实现软件的撤消功能为主线，整个项目分为问题分析、设计算法和程序实现三个部分。本节课时是通过分析撤消字符操作实例中输入、撤消两个操作，理解栈的“进栈（入栈）”“出栈”两大基本操作，通过活动让学生自行设计进栈、出栈操作和算法。在这一课时过程中，进一步培养学生的信息意识和计算思维。
?教学目标
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
四、课堂活动
在算法流程框图中完成进栈和出栈操作(数组名和变量名可以自取)。
参考答案：
21世纪教育网
www.21cnjy.com
精品试卷·第
2
页
（共
2
页）
HYPERLINK
"http://21世纪教育网(www.21cnjy.com)
"
21世纪教育网(www.21cnjy.com)(共22张PPT)
第二课时
设计算法
信息技术沪教版
选择性必修1
第三单元
特殊的线性表
项目五
模拟实现软件的撤消功能
——栈的应用
01
02
03
04
04
课堂活动
03
栈的常用基本操作
02
设计算法
01
新课导入
一、新课导入
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后，这些字母会依次进栈点击一下“撤消”按钮，栈内最后一个字母就会出栈。
栈可以用数组来存储元素，也可以用链表存储元素。假设用数组存储元素，即用数组存放输入的字母，用一个变量作为栈顶指针，如图中的top。栈顶指针始终指向栈内的最后的元素。
思考与讨论
栈与队列的操作有何不同？
思考与讨论
栈的进栈出栈都从栈顶经过，栈底是封闭的；
队列进队是在队尾进，出队是在队首出，队首与队尾都是不封闭的。
思考与讨论
栈的操作特点是后进先出；队列的操作特点是先进先出。
栈在操作过程中只需要使用一个指针top；队列需要使用两个
front、rear。
三、栈的常用基本操作
栈的常用基本操作
进栈(push)：也称入栈，是向栈插入新元素，即把新元素插入到栈顶元素的上面，使之成为新的栈顶元素。
进栈
出栈(pop)：也称退栈，是删除栈顶元素，使其相邻的后一个元素成为新的栈顶
出栈
进栈
进栈就是从栈底开始，按顺序逐步向栈内添加数据。
算法思想：若栈不满，则先将栈顶指针增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
出栈
出栈就是从栈顶开始，按逆序逐步将栈内数据取出。
算法思想：若栈不空，则将栈顶指针所指空间内容取出赋予变量，然后将栈顶指针减1。栈空则没有元素可出。
def
Pop(self):
if
self.
top==-1:
print(“栈空，没有元素出栈")
else:
e=self.
Stack[self
top]
self.
top=self.top-1
return
e
课堂活动
在算法流程框图中完成进栈和出栈操作（数组名和变量名可以自取）。
开始
栈不满吗？
否
是
结束
进栈操作
在算法流程框图中完成进栈和出栈操作（数组名和变量名可以自取）。
开始
栈不满吗？
否
是
结束
进栈操作
Strck[top]←e
top←top+1
在算法流程框图中完成进栈和出栈操作（数组名和变量名可以自取）。
开始
栈不空吗？
否
是
结束
出栈操作
在算法流程框图中完成进栈和出栈操作（数组名和变量名可以自取）。
开始
栈不空吗？
否
是
结束
出栈操作
e←Strck[top]
top←top-1
谢谢
21世纪教育网（www.21cnjy.com)
中小学教育资源网站
有大把高质量资料？一线教师？一线教研员？
欢迎加入21世纪教育网教师合作团队！！月薪过万不是梦！！
详情请看：
https://www.21cnjy.com/help/help_extract.php

展开更多......

收起↑