2020-2021学年1.分析问题优秀课件ppt

这是一份2020-2021学年1.分析问题优秀课件ppt，文件包含项目四第一课时pptx、项目四第一课时doc等2份课件配套教学资源，其中PPT共24页， 欢迎下载使用。
第三单元 特殊的线性表项目四 探索电子排队预订功能的实现——队列的应用第一课时 分析问题 ❑教材分析本节的主要内容是分析问题。通过以探索电子排队预订功能的实现为主线，整个项目分为问题分析、设计算法和程序实现三个部分。本节课从分析电子排队预定功能中先来先服务的思想入手，结合活动帮助学生理解队列的概念以及“进队”“出队”。通过本节课的学习能培养学生的信息意识和计算思维能力。❑教学目标1.理解队列的概念和特征；2.理解队首、队尾指针的作用；3.理解顺序队列、链式队列存储的原理和特点；4.能用循环队列解决顺序队列可能出现的“假队满”和“假队空”问题；5.培养学生的信息意识和计算思维能力。❑教学重点1.理解队列的概念和特征。2.理解顺序队列、链式队列存储的原理和特点；❑教学难点1.能用循环队列解决顺序队列可能出现的“假队满”和“假队空”问题。2.培养学生的信息意识和计算思维能力。❑教学方法体验法、讲授法、讨论法、示例法❑教学准备　　计算机教室、多媒体设备、多媒体广播软件、教学课件、Python编程环境、学生上机练习的程序文件，预先编制的Python程序文件等。❑教学过程一、新课导入日常生活中，商品和服务需求大于供给的情况时有发生，例如限量商品发售、医院专家门诊号等。为了避免商场、医院或营业厅里人潮拥挤，等候的客户排起长龙，一些企事业单位在相应网站或手机App上提供了预约服务，如图3-1所示。客户输入身份、账号信息提交后自动进入电子排队预订系统。你知道电子排队预订系统是如何实现排队预约的吗？    图3-1电子排队预订系统 二、分析问题电子排队预订系统是计算机自动控制的排队系统，排队的特点是先来先服务，那计算机是怎么实现自动排队的呢？当客户在电子排队预订系统提交信息后，客户的预订数据就进入队列，称为进队(也称人队)，即在队尾(rear)插入个客户账号数据；当正式购买商品时就到队列中取出客户账号数据，称为出队，即在队首(front)取出一个客户账号数据(客户账号数据暂用A0001形式替代)，如图3-2所示。图3-2预订一购买队列用先进先出的数据结构来存储排队的客户账号数据，就可以方便地实现先来先服务，这种数据结构称为队列。 思考与讨论生活中还有其他类似的先进先出的例子吗？生活中需要排队的问题，如医院挂号看病、加油站排队加油、小孩子排队滑滑梯、一队人过独木桥等。 核心概念队列( queue)是一种只允许在表的前端(队头)进行删除操作，而在表的后端(队尾)进行插入操作的线性表。队列又称为先进先出( first in first out,fifo)表。 小贴士队列是一种操作上受限制的线性表，只允许在队首和队尾进行操作。 三、队列排队的队伍在计算机中称为队列，队列是一种只能在表的首端取出数据，在表的尾端添加数据的线性表，即队列是操作上有限制的线性表，队列是一种先进先出数据结构。队列的抽象数据类型表示如下：              ADT Queue数据对象：D={ ai｜ai ∈ ElemSet,i=1,2,…,n,n>=0}数据关系：R={<ai-1,ai>｜ai-1,ai∈D,i=2,…,n}基本操作:def_init_(self)  #初始化一个空队列 def QEmpty(self)  #若队列空，则返回True,否则返回 False        def QLength(self)  #返回队列的元素个数        def GetHeac(self)  #返回队列的队头元素        def EnQueue(self.e)  #e元素进队        def OutQueue(self)  #元素出队  队列有两种存储方式，一种是用数组存储，这种方式存储的队列称为顺序队列；另一种用链表存储，这种方式存储的队列称为链队列，如图3-4所示。元素插入队尾称为进队队首元素取出称为出队。队首用front指针指示，队尾用rear指针指示。图3-4链队列用数组存储队列元素时，会遇到指针溢出问题。即当队满时，再有元素进队，就会产生指针的溢出(上溢出)；当队空时，再要取出元素，也会产生指针的溢出(下溢出)。另外，还有“假溢出”问题。随着元素的进队和出队，整个队列是向数组下标较大的位置移动。当移动到数组中下标最大的位置后，队列空间就用尽了。此时，即使数组下标较小的位置处还有空闲空间，元素也无法进队了，这种现象就叫“假溢出”。解决以上问题可以有两种方法：一是每次队首元素出队后面的元素都向前移动一次。但这种做法会使出队效率较低。另一种方法是采用循环队列，即把队列的首尾相连，当队尾指针超出数组长度时，就将其设回到最初的队首位置(数组下标为0)。如图3-5所示图中为8个空间的队列形成的循环。为了能实现循环，可以采用指针加1除队列空间数后取余，替代指针加1的方法，即rear=(rear+ 1)%size(队尾指针循环)，front( (front+1)%size(队首指针循环)，其中，%就是取余运算，size为队列的空间数。图3-5  循环队列四、课后活动1.假设排队预订客户账号数据为A001、A002000、A000下面空的队列中依次A0001进队，A0002进队，A003进队，叫号出队，A004进队，叫号出队，叫号出队，叫号出队，画出队列的变化过程。(1)                 (2)                 (3)(4)                  (5)                 (6) 2.请尝试写出队列的抽象数据类型定义。 活动答案参考：1.  2. ADTQueue：数据对象：D={ai ｜ai, ∈ ElemSet, i=1, 2, 3,…,n, n>=0}数据关系：R={<ai-1,ai>｜ai-1,ai∈D,i=2,…，n}基本操作：           def InitQueue(self)   #建立一个空队列           def QEmpty(self)   #若空队列，则返回True,否则返回 Flase           def QLength(self)   #返回队列的元素个数            def GetHead(self)   #返回队列的队头元素           def EnQueue(self,e)   #e元素进队            def OutQueue(self)   #元素出队