高中信息技术沪教版（2019）选修1 数据与数据结构2.设计算法优秀ppt课件

这是一份高中信息技术沪教版（2019）选修1 数据与数据结构2.设计算法优秀ppt课件，文件包含项目四第二课时pptx、项目四第二课时doc等2份课件配套教学资源，其中PPT共28页， 欢迎下载使用。
第三单元 特殊的线性表项目四 探索电子排队预订功能的实现——队列的应用第二课时 设计算法 ❑教材分析本节的主要内容是设计算法。通过以探索电子排队预订功能的实现为主线，整个项目分为问题分析、设计算法和程序实现三个部分。本节课根据进队、出队的过程设计进队、出队操作算法，研究队列两种存储结构，了解顺序存储结构的越界问题及解决越界问题采用的一般方法，即循环队列。通过本节课的学习能培养学生的信息意识和计算思维能力。❑教学目标1.能设计进队、出队的算法；2.培养学生的信息意识和计算思维能力。❑教学重点1.进队、出队的算法设计。❑教学难点1.能设计进队、出队的算法。2.培养学生的信息意识和计算思维能力。❑教学方法体验法、讲授法、讨论法、示例法❑教学准备　　计算机教室、多媒体设备、多媒体广播软件、教学课件、Python编程环境、学生上机练习的程序文件，预先编制的Python程序文件等。❑教学过程一、新课导入完成下面的任务：假设排队预订客户账号数据为A001、A002000、A000下面空的队列中依次A0001进队，A0002进队，A003进队，叫号出队，A004进队，叫号出队，叫号出队，叫号出队，画出队列的变化过程。(1)                 (2)                 (3)                     (4)                 (5)                 (6) 二、设计算法排队预订的队列变化过程如图3-3所示(为图示方便暂定图中队列空间只有4个)。客户预订即为进队，假设A0001表示第一个客户账号数据，购买即为队首出队。图中rear指向队列的尾端，图中 front指向队列的首端。 图3-3进队、出队的过程示意 思考与讨论1.队尾指针是否一定要指向队尾下一个元素？2.队列在反复进队、出队后会出现尾指针rear和头指针front出界的情况，有什么解决方法？ 参考：1.顺序队列队尾指针一般情况下是指向队尾下个元素的。但当队列满时，队尾指针会出现出界的情况；循环队列尾指针指向第一个元素；链队列队尾指针存储的是“NULL”。队列指针表示方法还有另种，即尾指针指向最后一个元素而不是最后一个元素的下一个元素。2.用顺序队列可采用循环队列的方式或每次队首元素出队，后面元素都向前移动一次的方式解决这问题(效率较低)；用链表存储队列时须先增加结点，再将原队尾指针指向新的元素，最后更改队尾指针。 队列在计算机里怎样表示呢？队列是操作上有限制的线性表，既可以用数组表示一个队列，也可以用链表表示个队列。一般若问题规模已知，即总的进队元素个数已知的话，队列可以用顺序存储结构存储，即用数组表示队列；若进队元素个数无法预计，则队列可以用链式存储结构存储，即用链表表示队列。 思考与讨论用数组方式和用链表方式存储队列，队列指针的形式有何不同？用数组方式，队列指针实际存放的是数组元素的下标；用链表方式，队列指针实际存放的是链表结点的地址。●小贴士用数组存储队列时，可能会遇到指针溢出的问题，最简单的解决方法是将rear增1改成rear=(rear+1)%M；front的增1改成 front=( front+1)%M。其中M为队列的空间数，%是取余运算符，这时的顺序队列被称为循环队列。为了操作方便增加一个计数器 number，记录队列中的元素个数。 三、队列的常用基本操作1.进队进队就是从队尾添加数据的操作。    顺序队列进队的算法思想：若队列不满，则将进队的元素送入尾指针rear所指空间，元素个数计数器增1,然后将尾指针rear往尾部方向移动一位即指向新的队尾。                   def EnQueue(self,e):       if(self.number==self.size):print(“队满，不能进")      else：self.queue[self.rear]=e          self. rear=(self. rear+ 1)%self.size          self.number=self.number+1return2.出队出队就是在队首取出数据的操作。顺序队列出队的算法思想：若队列不空，则将队首指针 f front所指空间的内容取出赋予变量，元素个数计数器减1，然后将首指针front往后移动一位即指向新的首端。                 def OutQueue(self):     if(self.number==0):print(“队空") else:e=self.queue[self.front]      self.front=(self. front+1)%self.size      self.number=self.number-1      return e 四、课后活动1.在算法流程框图中完成进队和出队操作(数组名和变量名可以自取)。    进队操作                     出队操作 活动答案参考：