栈和队列教案.docx_咨信网zixin.com.cn

资源描述

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

展开阅读全文