《数据结构[Python语言描述]》教案第6课栈和队列（3.3-3.4）.docx

课题第6课栈和队列(3.33.4)课时2课时(90min)教学目标知识目标：(1)掌握链栈的存储结构及其基本操作的实现(2)理解递归的定义并掌握递归的调用方法技能目标：能使用递归方法解决实际问题，并写出优雅、简洁的代码素质目标：理解递归的核心思想，学会用"分治法"解决实际生活中遇到的问题教学重难点教学重点：链栈的存储结构及其基本操作、递归的定义和调用方法教学难点：链栈的基本操作、递归的调用方法教学方法问答法、讨论法、讲授法、实践法教学用具电脑、投影仪、多媒体课件、教材教学过程主要教学内容及步骤考勤【教师】使用APP进行签到【学生】班干部报请假人员及原因问题导入【教师】提出以下问题：如便螂栈的链式存储?【蚂思考、传授新知【教师】通过学生的回答引入要讲的知识，介绍链栈的存储结构和基本操作、递归的定义和调用3.3栈的链式存储一链栈栈的链式存储是指，利用一个单链表依次存放自栈顶到栈底的数据元素，同时设置一个栈顶指针2P指示栈顶元素的当前位置。采用链式存储结构的栈称为链栈。3.3.1 倍栈的存储结构与单链表相同，链栈中元素的存储结构也称为结点，结点由数据域和指针域组成。通常，链栈中的第一个结点为栈顶元素，最后一个结点为栈底元素，故链表的头指针即为栈顶指针iop.*【教师】用多媒体展示“栈的链式存储结构”图，并介绍该结构topIlIII:IIIt1I的I；I【教师】随机邀请学生回答以下问题栈的顺序存储与链式存储有哪些区别?【学生】聆听、思考、回答在链栈中，假设每个结点为StaCkNOde类对象，则结点的定义如下。classStackNode:#链栈结点类def_init_(self,data):#构造方法self.data=data#data属才生self.next=None#next属寸生【提示】由于进栈和出栈操作只能在栈顶进行，不存在其他位置的插入和删除操作，所以链栈中不设置头结3.3.2链栈中基本操作的实现1 .初始化链栈初始化链栈就是构造一个空栈。【算法描述】classLinkStack:definit(self):self.top=None#将栈顶指针置为空2 .判断链栈是否为空【教师】随机邀请学生回答以下问题如何断链栈是否空？÷【学生】聆听、思考、回答判断链栈是否为空就是判断栈顶指针top是否为空.【算法描述】defStackEmpty(Self):returnself.topisNone3 .进栈链栈的进栈操作是指将元素为e的结点作为栈顶元素插入链栈中。÷【教师】用多媒体展示“链栈中元素的进栈过程“图(详见教材)，并介绍具体步骤和算法描述链栈中元素进栈的具体步骤如下。(1)生成一个新结点，并令其数据域为e(2)将松点的靛指针指向栈顶元素。(3)将栈顶指针指向新结点。【算法描述】defpush(self,e):s=StackNode(e)s.next=self.topself.top=s4.出栈链栈的出栈操作是指将栈顶结点从链栈中删除。÷【教师】用多媒体展示“链栈中元素的出栈过程“图(详见教材)，并介绍具体步骤和算法描述链栈中元素出栈的具体步骤如下。(1)判断链栈是否为空，若为空，则抛出异常。(2)将栈顶指针top指向当前栈顶结点的下一个结点。【算法描述】defpop(self):ifself.StackEmpty():raiseEXCePtiOn栈为空，无法删除！')temp=self.topself.top=self.top.nextreturntemp.data【算法分析】该算法的时间复杂度为0(1).【提示】链栈的进栈和出栈操作相当于单链表的头插入和头删除。5.取栈顶元素取栈顶元素就是获取链栈中最后进栈的元素，其具体步骤如下.(1)判断链栈是否为空，若为空，则抛出异常。(2)返回栈顶指针top所指栈顶结点的值。【算法描述】defgetTop(self):ifself.StackEmpty():raiseEXCePtion('栈为空！')returnself.top.data【算法分析】该算法的时间复杂度为0(1).*【教师】讲解实例3-5(详见教材)，并要求学生完成实例3-6(详见教材)【学生】聆听、思考、理解、记录任务实施任务利用建栈实现括号匹配的检验【教师】描述问题，分析问题，要求学生完成任务【问题描述】给定一个字符串sir,设计算法检验其中的圆括号"()"、花括号""和方括号"V是否匹配，规则如下.(1)左括号"(",'"T必须有对应的右括号")"""u"(2)右括号")"""必须有对应的所舌号"("T。(3)左括号"("''"T必须在对应的右括号")""""K'前面。(详见教材)【问题分析】使用栈存储字符串中的括号，当遇到左括号"("""T时进栈，当遇到右括号")"""'T时，首先判断当前栈是否为空。如果为空，则表示右括号多余，括号不匹配；如果非空，则判断当前栈顶元素是否为与之对应的左括号.如果是，则将当前栈顶元素出栈；如果不是，则表示括号不匹配.【学生】按照要求完成任务,如遇问题可询问老师【教师】巡堂辅导，及时解决学生遇到的问题3.4栈与递归÷【教师】随机邀请学生回答以下问题什么是递归？÷【学生】聆听、思考、回答栈有一个非常重要的应用是在程序设计中实现递归。递归既是强有力的数学方法，也是程序设计中一个很有用的工具，采用递归方法解决问题时编写的程序内容简洁、结构清晰且易于验证其正确性。3.4.1 递归的定义和调用递归是指一个函数在定义自身的同时又直接或间接地调用自身。÷【教师】随机邀请学生回答以下问题哪些情况下会使用到递归方法？÷【学生】聆听、思考、回答在很多情况下都会使用递归的方法，如函数的定义、问题的求解等。1.使用递归定义函数很多数学函数都是使用递归定义的，如阶乘函数和斐波那契数列。【教师】用多媒体展示“阶乘函数”图，并介绍实现代码flW=OFact(z)=I*FaC1(-1)n>0传授新知对于阶乘函数，使用递归方法实现的代码如下。defFact(n):ifn=0:return1returnn*Fact(n-1)print(Fact(3)阶乘函数的求解是分解为几个较简单的函数解决的，分解后的函数解法相同或类似，且有一个明确结束函数的条件，类似这种分步解决问题的方法称为“分治法"。【拓展阅读】使用递归解决问题的核心思想是“分治法"，也就是分而治之，即将一个问题拆分成多个更易解决的小问题，然后逐个解决。"分治法”是一种通用的问题解决方法。当遇到问题时，如果自身能力小于问题难度,则可以使用"分治法”的思想来解决。正如哲学家、物理学家笛卡尔所说："将面临的所有问题尽可能地细分，细至能用最佳的方式将其解决为止。”2.使用递归求解问题在实际应用中，有些问题使用递归求解更加简单，如迷宫问题、汉诺塔问题等。÷【教师】讲解实例3-7【实例3-7使用递归求解汉诺塔问题。#汉诺塔问题递归解法n=int(input(，请输入汉诺塔阶教：')#汉诺塔移动操作，表示将A上的圆盘借助塔座B移到塔座Cdefmove(nzA,B,C):ifn=1:#如果n=l,直接将圆盘从塔座A移到塔座C,递归结束Printr从塔座，+A+，移到塔座，+C)else:#递归#将A上编号为l-n-l的圆盘借助塔座C移到塔座Bmove(n-1,A,C,B)#将编号为n的圆盘从A移到CPrint从塔座，+A+，移到塔座，+C)#将B上编号为1n-l的圆盘借助塔座A移到塔座Cmove(n-1,B,A,C)move(nz,A,z,B,z,C,)对比利用顺序栈解决汉诺塔问题的代码可以发现，求解同一个问题时，使用递归方法编写的代码简洁明了且易于理解。3.4.2递归过程与递归栈为了保证递归函数的正确执行，系统须设立一个递归栈作为整个递归函数运行期间的数据存储区。每当递归函数被调用时，系统须保存函数的参数和返回地址(即执行进栈操作)，并向下一层函数传递参数、分配存储空间，从而控制程序转移到下层函数的入口。每当从被调用函数返回调用函数时，系统将保存被调用函数的计算结果，然后恢复上一层函数的参数(即执行出栈操作)，并控制程序转移到保存的返回地址处。÷【教师】用多媒体展示”阶乘函数Fact(3)在递归过程中的进栈和出栈情况”图(详见教材)，并介绍进栈出栈过程【学生】聆听、思考、理解、记录任务实施任务一利用递归实现斐波那契数列【教师】描述问题，分析问题，要求学生完成任务【问题描述】斐波那契数列是指这样一个数列：1、1、2、3、5、8、13、21、34、，这个数列从第3项开始，每一项等于前两项之和，其递推公式如图所示。1n=1或=2Fb(?)=«Fib("-1)+Fib(n-2)n>2给定一个整数n,设计算法输出斐波那契数列的前n项。【问题分析】由斐波那契数列递推公式可以看出，数列呈现的规律是第n(n>2)项的值为第n-1项与第n-2项之和，因此可以使用递归求解。【学生】按照要求完成任务，如遇问题可询问老师【教师】巡堂辅导，及时解决学生遇到的问Sg课堂小结【教师】简要总结本节课的要点链栈的存储结构及其基本操作递归的定义和调用递归过程与递归栈【学生】总结回顾知识点作业布置【教师】布置课后作业完成课后习题中的相关练习。【学生】完成课后任务教学反思