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

这是一份高中信息技术沪教版（2019）选修1 数据与数据结构1.分析问题完美版课件ppt，文件包含项目五第一课时pptx、项目五第一课时doc等2份课件配套教学资源，其中PPT共23页， 欢迎下载使用。
第三单元 特殊的线性表项目五 模拟实现软件的撤消功能——栈的应用第一课时 分析问题 ❑教材分析本节的主要内容是分析问题。通过以模拟实现软件的撤消功能为主线，整个项目分为问题分析、设计算法和程序实现三个部分。本节课时是从“撤消字符操作”的实例中分析出后输入的字符先撤消的思想方法，将这一思想方法图形化后，引出另一种受限制的线性结构——“栈”的概念，并通过活动帮助学生加深理解。在这一课时过程中，进一步培养学生的信息意识和计算思维。❑教学目标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冰糖葫芦串栈的抽象数据类型表示如下：   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)   #返回出栈元素  栈有两种存储方式，一种是用数组存储，这种方式存储的栈称为顺序栈；另一种用链表存储，这种方式存储的栈称为链式栈。一般根据进栈元素个数是否确定来选择存储结构，元素个数确定的用顺序栈，不确定的用链式栈。                四、课堂活动1.请尝试写出栈的抽象数据类型定义。2.网上搜索列车调度方法，根据图3-8画出用栈进行调度的过程示意图，并说明调度的原理。图3-8列车调度示意    参考答案：1.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)   #返回出栈元素 2.