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

《《数据结构[Python语言描述]》教案第7课栈和队列（3.5-3.7）.docx》由会员分享，可在线阅读，更多相关《《数据结构[Python语言描述]》教案第7课栈和队列（3.5-3.7）.docx（8页珍藏版）》请在课桌文档上搜索。

1、课题第7课栈和队列（3.53.7）课时2课时(90min)教学目标知识目标：（1）理解队列的定义及其基本操作（2）掌握队列的顺序和链式两种存储结构及其基本操作的实现技能目标：能使用队列解决程序设计中的问题素质目标：理解队列的原则，养成遵守规则的良好习惯教学重难点教学重点：队列的定义及其基本操作、队列的顺序和链式两种存储结构及其基本操作教学难点：队列的顺序和链式两种存储结构及其基本操作教学方法问答法、讨论法、讲授法、实践法教学用具电脑、投影仪、多媒体课件、教材教学过程主要教学内容及步骤考勤【教师】使用APP进行签到【学生】班干部报请假人员及原因问题导入【教师】提出以下问题：如何理队列？【蚂思考、

2、传授新知【教师】通过学生的回答引入要讲的知识，介绍队列概述、队列的顺序存储、队列的链式存储3.5队列概述3.5.1 队列的定义【教师】随机邀请学生回答以下问题栈与队列有什么区别？【学生】聆听、思考、回答与栈狗以，队列也是一种操作受限的线性表，不同的是，队列只允许在表的一端进行插入操作，而在另一端进行删除操作。通常将表中允许进行插入操作的一端称为队尾，允许进行删除操作的一端称为队头,队列的插入操作称为进队（或入队），队列的删除操作称为出队（或退队）.当队列中没有元素时称为空队。*【教师】用多媒体展示“队列的存储结构”图，并介绍该结构进队队尾1gn-队头一H的41出队元素的进队和出队是按照先进先出

3、（fi115tinfirstout,FIFO）”的原则进行的，因此,队列又称为先进先出的线性表。【拓展阅读】稍有礼仪讲究的地方，通常先来者都会优先于后来者。例如，在餐厅排队打饭时，应遵循先到先得的原则；购买火车票时，也应遵循先到先得的原则等。（详见教材）【教师】讲解实例3-8【实例3-8】已知元素的进队顺序为A、B、C、D,写出可能的出队序列。【问题分析】队列遵循先进先出的原则，因此进队顺序为A、B、C、D时只有一种出队序列，即A、B、C、De3.5.2队列的基本操作【教师】用多媒体展示“队列基本操作的定义”表格，并介绍基本操作基本操作说明_init_()初始化队列，即构造一个空队列queue

4、Empty()队列已存在的前提下，判断队列是否为空inQueue(e)队列已存在的前提下，插入数据元素“成为新的队尾元素deQueue()队列已存在的前提下，删除队头元素getHead()队列已存在的前提下，返回队头元素length()队列已存在的前提下，返回队列中实际元素的个数3.6队列的顺序存储顺序队列【教师】随机邀请学生回答以下问题什么是队列的顺序存储？【学生】聆听、思考、回答队列的顺序存储是指，在内存中用一组地址连续的存储单元依次存放从队头到队尾的数据元素。采用顺序存储结构的队列称为顺序队列。3.6.1 顺序队列与循环队列由于队列中插入和删除操作分别在表的两端进行，因此需要增加队头指针

5、front和队尾指针rear。其中，from指针指向队头元素的位置，rear指针指向队尾元素存储位置的下一个存储位置。【教师】用多媒体展示“顺序队列中front指针、rear指针和队列中元素之间的关系”图（详见教材），并介绍三者的关系初始化队列时front和rear都为Oe当有新的元素进队时，新元素存入rear所指的存储位置，并且rear加1；当元素出队时，front所指存储位置的元素出队，并且front加1。【教师】随机邀请学生回答以下问题队列的顺序存储的缺点是什么？【学生】聆听、思考、回答随着元素的进队和出队，front指针和rear指针都在增加。但是，当达到最大容量时已经满足队满条件，此

6、时，即使有元素出队而空出存储空间，也无法进行元素的进作，从而造成存储空间的浪费，这种现象称为“假溢出。为了使存储空间得到充分利用，于是引入了循环队列。将队列的存储空间看作一个环状的空间，即将队列的首、尾位置连接起来，这样的结构为循环队列.【教师】用多媒体展示“循环队列中front指针、rear指针和队列中元素之间的关系”图(详见教材)，并介绍三者的关系循环队列为空和为满的判断条件都是front=rear,所以无法根据该条件判断当前队列状态。为此，可规定少用一个元素的存储空间，当rear指针的下一个位置是front指针时，则停止进队操作，此时队列已满，判断条件为(rear+l)%max=fron

7、t3.6.2循环队列中基本操作的实现1.初始化循环队列初始化循环队列是为循环队列动态分配存储空间，其具体步骤如下。(1)设置循环队列的最大容量。(2)设置循环队列的存储空间。(3)将循环队列设置为空。【算法描述】class CirQueue:def _init_(self, max): self.max = maxself.data = None * self.maxself. front = 0self. rear = 0#循环队列结点类#构造方法# 设置循环队列的最大容量# 设置循环队列的存储空间# 将循环队列设置为空2判断队列是否为空判断循环队列是否为空就是判断队列中元素个数是否为0,可

8、以通过front指针和rear指针是否相等来判断.【算法描述】defqeeEmpty(self):returnself.front=self.rear3 .进队循环队列的进队操作是指将新的元素从队尾插入队列中，其具体步骤如下。(1)判断循环队列的存储空间是否已满，若已满，则抛出异常。(2)将新的元素插入rear所指的存储位置。(3)rear加1。【算法描述】definQueue(self,e):if(self.rear+1)%self.max=self.front:raiseEXCePtiOn(循环队列已满，无法插入！，)self.dataself.rear=e#插入新的元素eself.rea

9、r=(self.rear+1)%self.max【算法分析】该算法的时间复杂度为0(1).4 .出队循环队列的出队操作是指将元素从队头删除，其具体步骤如下。(1)判断循环队列是否为空，若为空，则抛出异常。(2)保存front所指存储位置元素的值。(3)front加Ie【算法描述】defdeQueue(self):ifself.rear=self.front:raiseEXcePtiOn循环队列为空，无法删除！，)e=self.dataself,front#保存删除前的队头元素self.front=(self.front+1)%self.maxreturne【算法分析】该算法的时间复杂度为0(1

10、).5 .取队头j三取队头元素就是获取循环队列中front所指存储位置元素的值(但并不删除)，其具体步骤如下.(1)判断循环队列是否为空，若为空，则抛出异常。(2)返回front所指存储位置元素的值。【算法描述】defgetHead(self):ifself.rear=self.front:raiseEXCePtion(循环队列为空！!)returnself.dataself.front【算法分析】该算法的时间复杂度为O(I)06 .求循环队列的长度求循环队列的长度就是返回队列中实际元素的个数。【算法描述】deflength(self):return(self.rear-self.front+

11、self.max)%self.max【算法分析】该算法的时间复杂度为0(1).【教师】讲解实例3-9(详见教材)7 .7队列的链式存储一飕队【教师】随机邀请学生回答以下问题什么是队列的链式存储？【学生】聆听、思考、回答队列的链式存储是指，利用一个单链表依次存放自队头到队尾的数据元素，同时设置一个用于指示队头结点的队头指针from和一个用于指示队尾结点的队尾指针rear.采用链式存储结构的队列称为链队。3.7.1链队的存储结构链队中每个元素分别对应链表中的一个结点。链队的队头指针front指向首元结点,队尾指针rear指向链表中最后一个结点。【教师】用多媒体展示“队列的链式存储结构”图，并介绍该

12、结构front!a()II队头1,I0_!I_IIIIITIeaIAl11在链队中，假设每个结点为QueueNode类对象，则结点的定义如下.classQueueNode:#def_init_(self,data):self.data=data#self.next=None#链队结点类#构造方法data属性next属性3.7.2链队中基本操作的实现1.初始化链队初始化链队就是构造一个空队列。【算法描述】classLinkQueue:def_init_(self):self.front=None#self.rear=None#将队头指针置为空将队尾指针置为空2.判断链队是否为空判断链队是否为空就

13、是判断队头指针front是否为空。【算法描述】defqueueEmty(self):returnself.frontisNone3.进队链队的进队操作是指将元素为e的结点插入队尾。链队中元素进队的具体步骤如下。(1)生成一个新结点，并令其数据域为“(2)将新结点插入队尾。(3)修改队尾指针。【算法描述】definQueue(self,e):s=QueueNode(e)#生成新名吉点、ifnotself.queueEmpty():#若原队列不为空，将新结点插入队尾self.rear.next=selse:self,front=s#若原队列为空，将队头指针指向Sself.rear=s#将队尾指针指

14、向新结点【算法分析】该算法的时间复杂度为O(I)e4.出队链队的出队操作是指删除队头结点。链队中元素出队的具体步骤如下。(1)判断链队是否为空，若为空，则抛出异常。(2)若链队中只有一个结点，则删除该结点并修改队尾指针rear.(3)若链队中有多个结点，则将队头指针front指向队头结点的下一个结点。【教师】讲解算法描述、算法分析(详见教材)5.取队头元素取队头元素就是获取链队中最先进队的元素，其具体步骤如下。(1)判断链队是否为空，若为空，则抛出异常。(2)返回队头指针front所指队头结点的值。【算法描述】defgetHead(self):ifself.queeEmpty():raiseE

15、XCePtion(,队列为空！)returnself.front.data【算法分析】该算法的时间复杂度为O(I)e【教师】讲解实例3-10.3-11(详见教材)【学生】聆听、思考、理解、记录任务实施任务一利用循环队列打印杨辉三角【教师】描述问题，分析问题，安排学生扫描微课二维码观看视频“利用循环队列打印杨辉三角“(详见教材)，要求学生设计算法【问题描述】杨辉三角是一个由数字排列而成的三角形数表，它描述的是两个未知数之和的幕次方运算后的系数问题。例如，+y)2=2+2y+V,其中系数是121,这就是杨辉三角的其中一行。以此类推，a+、必等的运算结果的各项系数就构成了杨辉三角的其他行.(详见教材)【问题分析】杨辉三角的特点是两侧最外层的数字都是I,从第2行开始，其他位置上的数字是其上一行中与之相邻的两个数字之和，因此第n行的n-1个数字可以利用第n-1行的数字得到。(详见教材)【学生】自行扫码观看配套微课，按照要求完成任务，如遇问题可询问老师【教师】巡堂辅导，及时解决学生遇到的问题课堂小结【教师】简要总结本节课的要点队列的定义和基本操作顺序队列与循环队列循环队列中基本操作的实现链队的存储结构及其基本操作【学生】总结回顾知识点作业布置【教师】布置课后作业完成课后习题中的剩余练习。【学生】完成课后任务教学反思