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

课题第5课栈和队列（3.1-3.2）课时2课时(90min)教学目标知识目标：（1）理解栈定义及其基本操作（2）掌握顺序栈的存储结构及其基本操作的实现技能目标：能使用栈解决程序设计中的问题素质目标：培养科学严谨、精益求精的工匠精神教学重难点教学重点：栈定义及其基本操作、顺序栈的存储结构及其基本操作教学难点：顺序栈的存储结构及其基本操作教学方法问答法、讨论法、讲授法、实践法教学用具电脑、投影仪、多媒体课件、教材教学过程主要教学内容及步骤考勤【教师】使用APP进行签到【学生】班干部报请假人员及原因问题导入【教师】提出以下问题：日常生活中，栈的应用场景有哪些？【蚂思考、传授新知【教师】通过学生的回答引入要讲的知识，介绍栈的定义和基本操作、顺序栈的存储结构和基本操作3.1 栈概述在日常生活中，栈的例子比比皆是，如圆柱形容器中乒乓球的装入和取出过程、摞盘子和取盘子的过程等，它们都遵循"后进先出"的规律.3.1.1 栈的定义栈是一种只允许在表的一端进行插入和删除操作的线性表。通常将表中允许进行插入和删除操作的一端称为栈顶，另一端称为栈底。栈的插入操作称为进栈（或入栈），栈的删除操作称为出栈（或退栈）.当栈中没有元素时称为空栈。进栈出栈由于元素的插入和删除操作都是在栈顶进行，故栈顶元素的位置是动态变化的，它由一个称为栈顶指针的位置指示器指示。最先进栈的元素最后出栈，即元素的进栈和出栈是按照"后进先出（IaStinfirstout,LIFO）”的原则进行的，因此，栈又称为“后进先出"的线性表。*【教师】讲解实例3-1,并邀请学生思考实例3-2（详见教材）【实例3-1】已知元素的进栈顺序为A、B、C、D,得到的出栈序列为B、C、D、Ae若用I表示进栈操作，O表示出栈操作，求元素执行的操作序列.【问题分析】如果元素的进栈顺序为A、B、C、D,要想B出栈，首先须A和B进栈并B出栈；然后C进栈，C出栈；接着D进栈，D出栈；最后A出栈，这样就得到了出栈序列B、C、D、Ae所以，元素执行的操作序列为IlOIO100e3.1.2栈的基本操作【教师】用多媒体展示“栈基本操作的定义”表，并说明各基本操作基本操作说明初始化栈，即构造一个空栈StackEmptyO栈已存在的前提下，判断栈是否为空push(e)栈已存在的前提下，插入数据元素e成为新的栈顶元素pop()栈已存在的前提下，删除栈顶元素getTop()栈已存在的前提下，返回栈顶元素，即最后进栈的元素length()栈已存在的前提下，返回栈中实际元素的个数3.2栈的顺序存储顺序栈【教师】随机邀请学生回答以下问题如彳可理解栈的顺序存储？÷【学生】聆听、思考、回答栈的顺序存储是指，在内存中用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。采用顺序存储结构的栈称为顺序栈。3.2.1 顺序栈的存储结构在采用顺序存储结构存储栈中的元素时，由于进栈和出栈操作都是在栈的一端(栈顶)进行，因此需要增加一个栈顶指针top,用于指示某一时刻栈顶元素的位置。top指针指向栈顶元素存储位置的上一个存储位置，当t。P=O时为空栈。÷【教师】用多媒体展示“栈顶指针和栈中元素之间的关系”图片(详见教材)，并进行讲解由图3-2可以看出，初始化栈时top=0,当有新的元素进栈时，新元素存入top所指的存储位置，并且top加1；当出栈时，top减1,栈顶元素出栈，3.2.2 顺序栈中基本操作的实现1 .初始化JlI刻字栈初始化顺序栈是为顺序栈动态分配存储空间，其具体步骤如下。(1)设置JI酹栈的最大容量。(2)设置I耐栈的存储空间。(3)将JI砺栈设置为空。【算法描述】classSqStack:#顺序栈类definit(self,max):#构造方法，定义变量并赋初值self.max=max#设置顺序栈的最大容量self.data=None*self.max#设置顺序栈的存储空间self.top=0#将顺序栈设置为空2 .判断栈是否为空判断顺序栈是否为空就是判断顺序栈中元素个数是否为0,可以通过top指针是否为0来判断。【算法描述】defStackEmpty(self):returnself.top=0题3.进栈顺序栈的进栈操作是指将新的元素作为栈顶元素插入顺序栈中。÷【教师】用多媒体展示“顺序栈中元素的进栈过程”图(详见教材)，随机邀请学生回答以下问结合图片，简述顺序栈中元素进栈的步骤。÷【学生】聆听、观察、思考、回答顺序栈中元素进栈的具体步骤如下。(1)判断顺序栈的存储空间是否已满，若已满，则抛出异常。(2)将新的元素插入op所指的存储位置。(3)8加1。【算法描述】defpush(self,e):ifself.top=self.max:raiseEXCePtLionr栈满，无法插入！')self.dataself.top=e#插入新的元素eself.top+=1#top加1题【算法分析】该算法的时间复杂度为0(1).【提示】顺序栈中元素的进栈操作可以直接使用Python列表的叩PendO函数实现。4.出栈顺序栈的出栈操作是指将栈顶元素从顺序栈中删除。÷【教师】用多媒体展示“顺序栈中元素的出栈过程”图(详见教材)，随机邀请学生回答以下问结合图片，简述顺序栈中元素出栈的步骤.【学生】聆听、观察、思考、回答顺序栈中元素出栈的具体步骤如下。(1)判断顺序栈是否为空，若为空，则抛出异常。(2)K)P减1.(3)返回top所指存储位置元素的值。【算法描述】defpop(self):ifself.top=0:raiseEXCePtiOnr栈为空，无法删除！，)self.top-=1#top减1returnself.dataself.top#返回top所指存储位置元素的值【算法分析】该算法的时间复杂度为O(I)e【提示】顺序栈中元素的出栈操作可以直接使用Python列表的pop()函数实现。5 .取栈顶元素取栈顶元素就是获取顺序栈中最后进栈的元素(但并不删除)。【教师】用多媒体展示”顺序栈中取栈顶元素”图(详见教材)，并介绍具体步骤和算法描述顺序栈中取栈顶元素的具体步骤如下。(1)判断顺序栈是否为空，若为空，则抛出异常。(2)返回top所指存储位置的下一个存储位置元素的值。【算法描述】defgetTop(self):ifself.top=0:raiseEXCePtiOnr栈为空！!,)returnself.dataself.top-1#取栈顶元素【算法分析】该算法的时间复杂度为O(I)e6 .求JII旃栈的长度求顺序栈的长度就是返回顺序栈中实际元素的个数。【算法描述】deflength(self):returnself.top【算法分析】该算法的时间复杂度为O(I)e÷【教师】讲解实例3-3(详见教材)，并要求学生完成实例3-4(详见教材)【学生】聆听、思考、理解、记录任务实施任务利用顺序栈解决汉诺塔问题【教师】描述问题，分析问题，要求学生完成任务【问题描述】已知有3个塔座A、B、C,在塔座A上插有n个直径各不相同的圆盘，并按从大到小的顺序叠放。这些圆盘从小到大依次编号为1、2、3、n.现要将塔座A上的n个圆盘全部移到塔座C上，且使它们仍按原来的顺序叠放。圆盘在移动时必须遵循如下规则.(1)每次只允许移动一个圆盘。(2)圆盘可以放置在A、B、C中的伊可一个塔座上。(3)较小圆盘必须放置在较大圆盘上。这就是著名的汉诺塔问题。【问题分析】解决汉诺塔问题是需要移动圆盘的，移动规律如下.(1)最小圆盘(I号圆盘)的移动须与其他大圆盘(2n号圆盘)的移动交叉进行，即移动一次最小圆盘，就要移动一次其他大圆盘。(2)圆盘的移动方向由汉诺塔阶数(圆盘总数)决定。当汉诺塔阶数为奇数时，奇数号的圆盘向左移动(即A-C-B-A-C-B.),偶数号的圆盘向右移动(即A-BTC-A-B-C.)；当汉诺塔阶数为偶数时，奇数号的圆盘向右移动(即A-B-C-ATBTC.),偶数号的圆盘向左移动(即A-CTBTA-CTB.）。同时，最下面的圆盘只移动一次，并且是从A号塔座移到C号塔座（向左移）。（详见教材）【学生】按照要求完成任务，如遇问题可询问老师【教师】巡堂辅导，及时解决学生遇到的问题课堂小结【教师】简要总结本节课的要点栈的定义和基本操作顺序栈的存储结构和基本操作【学生】总结回顾知识点作业布置【教师】布置课后作业完成课后习题中的相关练习。【学生】完成课后任务教学反思