栈和队列教案

教案课程名称：数据结构（C语言版）授课班级：技校二年级学生授课学时：1学时授课章节：第三章栈和队列课型：理论课任课教师：***§3.1栈1教材分析名称《数据结构（C语言版）》编者：严蔚敏吴伟民等出版社：清华大学出版社特点“数据结构”是一门专业技术基础课。它的教学要求是：学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据结构选择适当的逻辑结构、存储结构及其相应的算法。地位“数据结构”是计算机程序设计的重要理论技术基础，它不仅是计算机学科的核心课程，而且已成为其他理工专业的热门选修课。本书是为“数据结构”课程编写的教材，其内容选取符合教学大纲要求。学情分析知识基础技本学生普遍基础薄弱，除了少数几个同学之外，普遍学习起点能力低于普通高中生源的学生。在教学中学生可能会遇到的最大问题是对符号化的东西没有感觉。因此，在授课过程中应注意放慢速度，通过理论联系实际，从生活中寻找科学原型，培养学生对符号化和图形的认知能力。学习态度由于技校学生没有升学压力,竞争意识薄弱,导致他们的学习态度不端正,不思进取、得过且过、目标不明确、缺乏学习兴趣。再加上现在很多职业技校仍在走传统教育的老路子,教学课程枯燥乏味,使得学生逐渐产生厌倦、逃避、无聊的心理。因此，在授课过程中应注意培养学生的学习习惯和学习方法，与学习的自制力。思维状态观察力和动手能力强，形象思维发展的很好，但抽象思维和归纳概括能力较差。因此，要注意培养学生的抽象思维能力，让学生学会联系学习法、归纳学习法、合作学习法和反思学习法等。教学目标知识1.理解栈的特点。2.掌握栈的使用方法，能够对栈进行入栈、出栈。3.能够根据栈的出栈顺序还原入栈顺序。技能1.能应用栈的知识解决实际问题。2.学会多种学习方法，提高抽象思维和举一反三能力。情感1.提高对《数据结构》课程的学习兴趣，认识到栈在显示问题进行抽象中的重要作用。2.培养理论联系实际、积极思考和自主训练的精神。3.培养主动从生活中寻找科学原型的习惯。重点与难点重点：栈的特点，栈的基本操作的实现算法。依据：课程大纲。处理：通过简单有趣的汉诺塔游戏来说明栈的特点。以课堂讲授为主，采用多媒体教学方式以增大信息量，对重点部分通过动画演示和板书进行深入分析，通过提问启发学生思考。难点：解决栈的应用问题依据：多次给同学们讲课经验，总结出来同学们对解决应用上有点吃力处理：授人以鱼不如授人以渔，更要授人以欲。课堂上留几分钟时间让学生思考。§3.1栈2首先，启发学生对栈的特点进行分析；然后，能根据给出的一串出栈顺序推导出入栈顺序，根据对栈的特点的理解，分析在实际生活中的应用。方法手段理论指导：以内容为主线，以教师为主导，学生为主体，职业能力为目标，社会需求为背景。教法：讲授法，演示法，探究法，讲练结合法学法：项目教学法，情景模拟教学法教学手段：板书、动态多媒体课件教学过程环节主要内容设计意图回顾与导入（6分钟）今天我们一起学习的内容是3.1栈，可以说栈是《栈和队列》这一章节的基础，也是《数据结构》这门课的核心思想之一。掌握这个思想对与整门课程的学习都有重要影响。前面我们已经学过线性表，请大家回顾一下，栈和队列与线性表有哪些相同点呢？栈和队列是两种重要的线性结构。从数据结构角度看，栈和队列也是线性表，其特殊性在于栈和队列的基本操作是线性表操作的子集，它们是操作受限的线性表，因此可称为限定性的数据结构。那它们的主要区别又是什么呢？但从数据类型角度看，它们是和线性表大不相同的两类重要的抽象数据类型。由于它们广泛应用在各种软件系统中，因此，在面向对象的程序设计中，它们是多型数据类型。那大家有没有想过，在现实中我们并没有听说过栈，为什么《数据结构》中却有栈呢？在我们日常生活中听到最多的就是排队列，就像我们去车站买票，先排队的人先买上票先出队列，但我们忽略还有另外一种线性结构——栈。那么栈是如何表示和实现的呢？激发学生学习动机，培养其学会目标学习法。回顾旧知识引导学生一起回答设疑启发激发学生的好奇心和学习兴趣，培养其学会联系学习法。提出问题（3分钟）一个现实当中的问题：地铁到达终点站时的入站出站问题。如图1所示，假设这张图表示地铁到站后再出站的图示。大家想一下，地铁到终点站后想要再原路返回，向另一个方向出发，地铁是怎样调整方向的呢？大家可以先在心里想一下，看是否与我们这节课所介绍的方法一致。再比如我们餐厅中一叠一叠的盘子，如果它们是按任务驱动提出问题培养学生学会问题学习法。图1地铁站入站出站§3.1栈3提出问题（3分钟）1,2,3，……，n的次序往上叠的话，那么使用的次序应该是什么样的？必然是依从上往下的次序，，即n，......，3,2,1。它们遵循的是规律正是本节课要讨论的“栈”的结构特点。对图1进行抽象，用地铁的每节车厢表示栈中每个元素这样就得到一个栈的示意图，如图2所示从图2中可以看出第一个进栈的a1为栈底元素，最后一个进栈的an为栈顶元素，进栈和出栈也是同一个方向。这也是最基本的栈的示意图。需要同学们熟知。其实，要解决这个出站问题就离不开我们今天将要学习的进栈、出栈技术，这节课我们将从如下三个方面来掌握它：栈的定义、栈的表示和实现、栈的应用与练习。其中栈的表示与实现是本节的重点。抽象思维激发学生的学习兴趣讲授新课（30分钟）一、抽象数据类型栈的定义（6分钟）1.定义：栈（stack）是限定仅在表尾进行插入或删除操作的线性表。因此，对栈来说，表尾端有其特殊含义，称为栈顶（top），相应地，表头端称为栈底（bottom）。不含元素的空表称为空栈。2.引出特点：假设栈S=（a1,a2,∙∙∙∙∙,an）,则称a1为栈底元素，an为栈顶元素。栈中元素按a1,a2,∙∙∙∙∙,an的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按照后进先出的原则进行的。因此，栈又称为后进先出的线性表。3.目的：根据入栈顺序得到出栈序列，以及能够在实际生活中运用栈，为栈的操作打基础。我们回到定义：出栈序列如何确定呢？根据给出的几组出栈序列如何判断哪些可以由入栈序列得到，哪些序列由入栈序列得不到。这就是入栈方法的问题。下面我们来做一个简单的小实验更深入的了解站的特暗示启发多种字体提示学生主动思考，培养其速记学习的能力。设疑启发图2栈的示意图§3.1栈4讲授新课（30分钟）点。二、介绍栈的定义类型（8分钟）ADTStack{数据对象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{ai-1,ai|ai-1,ai∈D,i=2,...,n}约定an端为栈顶，a1端为栈底。基本操作：InitStack(&S)操作结果：构造一个空栈S。DestroyStack(&S)初始条件：栈S已存在。操作结果：栈S被销毁。StackEmpty(S)初始条件：栈S已存在。操作结果：若栈S为空栈，则返回TRUE，否则FALE。GetTop(S,&e)初始条件：栈S已存在且非空。操作结果：用e返回S的栈顶元素。StackLength(S)初始条件：栈S已存在。操作结果：返回S的元素个数，即栈的长度。ClearStack(&S)初始条件：栈S已存在。操作结果：将S清为空栈。Push(&S,e)初始条件：栈S已存在。提出疑问，引起学生对接下来的内容产生好奇心，对接下来要讲的内容产生浓厚的兴趣。联系实际根据定义给出在编程中对栈进行操作是可以实现哪些功能。讲授操作讲解栈的基本操作中插入图示，可以更直观的看出栈的每个操作实现的最终结果。§3.1栈5讲授新课（30分钟）操作结果：插入元素e为新的栈顶元素。Pop(&S,&e)初始条件：栈S已存在且非空。操作结果：删除S的栈顶元素，并用e返回其值。StackTraverse(S,visit())初始条件：栈S已存在且非空。操作结果：从栈底到栈顶依次对S的每个数据元素调用函数visit（）。一旦visit（）失败，则操作失效。}ADTStrack三、练习与拓展（16分钟）1.练习（解决问题）回到地铁到达终点站时的入站出站问题。请同学们对右图栈的示意图中进栈序列依次为{a1,a2,a3,a4,a5,a6}，进行出栈序列排序。根据前面提出的栈的特点是不是可以很容易的得出这个序列的出栈序列呀。出栈序列为：a6,a5,a4,a3,a2,a1大家可以看看现在的解决方案与提出规划的方法是否一致。由此也可以看出该技术的重要。同学有没有觉得出栈序列还是很容易得到的，有没有感觉栈的知识也没有很难呀？根据以上对栈的理解，现在提出一个进栈出栈更宽泛的规则，让同学们感受到栈的知识的有趣性和多变性。注：进栈时除了一次性全部进栈之后再出栈的规则之外，其实还可以进栈元素进去一个或两个之后直接出栈，出栈可以不必都出完，接着进栈随时可以出栈。任务驱动解决问题练习法学以致用，当堂巩固。知识补充根据前面提出的问题进行解答。最后对栈的知识没有讲解到的加以补充。使同学们更深入的理解栈。设疑启发提示同学们观察栈和线性表的相似点与不同点。有助于§3.1栈6讲授新课（30分钟）比如上述题中出栈序列也可以为如下序列：序列1：a1,a2,a3,a4,a5,a6序列2：a2,a1,a4,a3,a5,a6序列3：a4,a5,a3,a6,a2,a1∙∙∙∙∙∙同学们有没有感觉根据栈的入栈方式不同可以产生不同的出栈序列，是不是栈的出栈序列很灵活，就像我们生活中的趣事一般。同学们发现栈和线性表的相似了没有呢？下面我画一个顺序存储结构的线性表线性表，同学们观察一下它们是不是很相似呢？2.拓展（1）设依次进入一个栈的元素序列为c，a，b，d，则可得到出栈的元素序列是：Ａ）a，b，c，dＢ）c，d，a，bＣ）b，c，d，aＤ）a，c，d，b请同学们想一下上面的序列哪些可以根据进栈顺序得到，哪些得不到呢？解：A、D可以（B、C不行）同学们对一下看看给出的答案跟你们心中的答案是否一致呢？有不理解的同学可以举手提问哦。下面再来解答一个题，巩固巩固今天所学过的知识。（2）数制转换算法基于原理：N=(Ndivd)×d+Nmodd提高学习效率和质量。最终使同学们喜欢上这门课。反思学习法学以致用从本节课的难点出发设置两个例题，让同学们思考一下，学以致用，会使用所学的知识解决实际生活中的问题。§3.1栈7讲授新课（30分钟例如：（1348)10=(2504)8，其运算过程如下：同学们想到答案了吗？3.思考栈往往用单链表实现。可以用双链表吗？哪个更好？这个问题同学们课后思考一下，下节课我们来解答。小结（3分钟）1）理解栈和线性表的异同点。2）掌握栈的特点，根据特点能够解决入栈出栈顺序，以及可以根据入栈得到多种入栈序列。3）能够利用栈知识解决实际生活中的问题。大家要掌握栈的特点，这是栈的重点。大家只要多练习、多思考、多归纳、多总结，就一定能熟练掌握。我们学过的知识。同学们加油哦！知识总结课堂总结可以把学过的知识整理成一个系统的体系，有助于提高学习效率和质量。布置作业（3分钟）1.书面作业：设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4,s6,s5,s1,则栈的容量至少应该是（）A.2B.3C.5D.62.思考：hanoi塔问题传说在创世纪时，在一个叫Brahma的寺庙里，有三个柱子，其中一柱上有64个盘子从小到大依次叠放，僧侣的工作是将这64个盘子从一根柱子移到另一个柱子上。移动时的规则：每次只能移动一个盘子；只能小盘子在大盘子上面；可以使用任一柱子。当工作做完之后，就标志着世界末日到来。动手动脑，全面发展。培养学生独立思考能力，学会合作学习法§3.1栈8板书设计§3.1栈一、定义：限定仅在表尾进行插入或删除操作的线性表。先进后出二、特点：后进先出三、练习与拓展四、小结反思课程结束后，反思整个教学过程，通过课堂提问和学生作业检查教学目标的实现情况，及时总结经验和教训。配合课件的板书区