中小学教育资源及组卷应用平台
第三单元
特殊的线性表
项目四
探索电子排队预订功能的实现
——队列的应用
第二课时
设计算法
?教材分析
本节的主要内容是设计算法。通过以探索电子排队预订功能的实现为主线，整个项目分为问题分析、设计算法和程序实现三个部分。本节课根据进队、出队的过程设计进队、出队操作算法，研究队列两种存储结构，了解顺序存储结构的越界问题及解决越界问题采用的一般方法，即循环队列。通过本节课的学习能培养学生的信息意识和计算思维能力。
?教学目标
1.能设计进队、出队的算法；
2.培养学生的信息意识和计算思维能力。
?教学重点
1.进队、出队的算法设计。
?教学难点
1.能设计进队、出队的算法。
2.培养学生的信息意识和计算思维能力。
?教学方法
体验法、讲授法、讨论法、示例法
?教学准备
计算机教室、多媒体设备、多媒体广播软件、教学课件、Python编程环境、学生上机练习的程序文件，预先编制的Python程序文件等。
?教学过程
一、新课导入
完成下面的任务：
假设排队预订客户账号数据为A001、A002000、A000下面空的队列中依次A0001进队，A0002进队，A003进队，叫号出队，A004进队，叫号出队，叫号出队，叫号出队，画出队列的变化过程。
(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.在算法流程框图中完成进队和出队操作(数组名和变量名可以自取)。
进队操作
出队操作
活动答案参考：
21世纪教育网
www.21cnjy.com
精品试卷·第
2
页
（共
2
页）
HYPERLINK
"http://21世纪教育网(www.21cnjy.com)
"
21世纪教育网(www.21cnjy.com)(共29张PPT)
第二课时
设计算法
信息技术沪教版
选择性必修1
第三单元
特殊的线性表
项目四
探索电子排队预订功能的实现
——队列的应用
A
B
C
D
四、课后活动
一、新课导入
三、队列的常用基本操作
二、设计算法
一、新课导入
假设排队预订客户账号数据为A001、A002000、A000下面空的队列中依次A0001进队，A0002进队，A003进队，叫号出队，A004进队，叫号出队，叫号出队，叫号出队，画出队列的变化过程。
完成下面的任务
（1）
（3）
（2）
（4）
（6）
（5）
二、设计算法
排队预订的队列变化过程如图所示（为图示方便暂定图中队列空间只有4个）。客户预订即为进队，假设A0001表示第一个客户账号数据，购买即为队首出队。图中rear指向队列的尾端，图中
front指向队列的首端。
排队预订的队列变化过程如图所示（为图示方便暂定图中队列空间只有4个）。客户预订即为进队，假设A0001表示第一个客户账号数据，购买即为队首出队。图中rear指向队列的尾端，图中
front指向队列的首端。
思考与讨论
1.队尾指针是否一定要指向队尾下一个元素？
思考与讨论
1.顺序队列队尾指针一般情况下是指向队尾下个元素的。但当队列满时，队尾指针会出现出界的情况；循环队列尾指针指向第一个元素；链队列队尾指针存储的是“NULL”。队列指针表示方法还有另种，即尾指针指向最后一个元素而不是最后一个元素的下一个元素。
思考与讨论
2.队列在反复进队、出队后会出现尾指针rear和头指针front出界的情况，有什么解决方法？
思考与讨论
2.用顺序队列可采用循环队列的方式或每次队首元素出队，后面元素都向前移动一次的方式解决这问题(效率较低)；用链表存储队列时须先增加结点，再将原队尾指针指向新的元素，最后更改队尾指针。
队列在计算机里怎样表示呢？队列是操作上有限制的线性表，既可以用数组表示一个队列，也可以用链表表示个队列。一般若问题规模已知，即总的进队元素个数已知的话，队列可以用顺序存储结构存储，即用数组表示队列；若进队元素个数无法预计，则队列可以用链式存储结构存储，即用链表表示队列。
思考与讨论
用数组方式和用链表方式存储队列，队列指针的形式有何不同？
思考与讨论
用数组方式，队列指针实际存放的是数组元素的下标；用链表方式，队列指针实际存放的是链表结点的地址。
用数组存储队列时，可能会遇到指针溢出的问题，最简单的解决方法是将rear增1改成rear=(rear+1)%M；front的增1改成
front=(
front+1)%M。其中M为队列的空间数，%是取余运算符，这时的顺序队列被称为循环队列。
为了操作方便增加一个计数器
number，记录队列中的元素个数。
●小贴士
三、队列的常用基本操作
1
进队
进队就是从队尾添加数据的操作。
顺序队列进队的算法思想：若队列不满，则将进队的元素送入尾指针rear所指空间，元素个数计数器增1,然后将尾指针rear往尾部方向移动一位即指向新的队尾。
1
进队
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往后移动一位即指向新的首端。
2
出队
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.在算法流程框图中完成进队和出队操作(数组名和变量名可以自取)。
1.在算法流程框图中完成进队和出队操作(数组名和变量名可以自取)。
1.在算法流程框图中完成进队和出队操作(数组名和变量名可以自取)。
1.在算法流程框图中完成进队和出队操作(数组名和变量名可以自取)。
谢谢
21世纪教育网（www.21cnjy.com)
中小学教育资源网站
有大把高质量资料？一线教师？一线教研员？
欢迎加入21世纪教育网教师合作团队！！月薪过万不是梦！！
详情请看：
https://www.21cnjy.com/help/help_extract.php
