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

第三单元 特殊的线性表

项目四 探索电子排队预订功能的实现

——队列的应用

第二课时 设计算法

❑教材分析

本节的主要内容是设计算法。通过以探索电子排队预订功能的实现为主线，整个项目分为问题分析、设计算法和程序实现三个部分。本节课根据进队、出队的过程设计进队、出队操作算法，研究队列两种存储结构，了解顺序存储结构的越界问题及解决越界问题采用的一般方法，即循环队列。通过本节课的学习能培养学生的信息意识和计算思维能力。

❑教学目标

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+1

return

2.出队

出队就是在队首取出数据的操作。

顺序队列出队的算法思想：若队列不空，则将队首指针 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.在算法流程框图中完成进队和出队操作(数组名和变量名可以自取)。

进队操作                     出队操作

活动答案参考：