《常用软件算法基础》课件-第6章 学生成绩信息审核（队列）

第六章学生成绩信息审核（队列）教学目标：掌握队列的基本概念和基本操作循环队列的基本概念和操作应用循环队列实现学生成绩信息审核管理了解链式队列实现原理重点：学生成绩信息审核循环队列实现难点：循环队列的操作实现6.1学生成绩审核功能描述学生成绩信息审核界面实现如下：6.2队列的基本概念队列的定义和特点：定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表队尾(rear)——允许插入的一端队头(front)——允许删除的一端

队列特点：先进先出(FIFO)a1a2a3…….an入队出队frontrear队列Q=(a1,a2,……,an)6.2.1顺序队列的存储队列的顺序存储结构实现：用一维数组实现sq[M]123450front=0rear=0队空设两个指针front,rear,约定：rear指示队尾元素的下一个位置；front指示队头元素初值front=rear=0空队列条件：front==rear入队列：sq[++rear]=x;出队列：x=sq[++front];10rear=120rear=230rear=312345030rear=32010front=0123450front=0rear=0front=1front=212345030rear=3front=240rear=450rear=560rear=66.2.2顺序队列的存储存在的问题存在问题设数组维数为M，则：当front=0,rear=M-1时，再有元素入队发生溢出——真溢出当front0,rear=M-1时，再有元素入队发生溢出——假溢出解决方案队首固定，每次出队剩余元素向下移动——浪费时间循环队列基本思想：把队列设想成环形，让sq[0]接在sq[M-1]之后，若rear+1==M,则令rear=0;0M-11frontrear…...…...实现：利用“模”运算入队：rear=(rear+1)%M;sq[rear]=x;出队：front=(front+1)%M;x=sq[front];队满、队空判定条件6.2.3循环队列012345rearfrontJ4J5J6012345rearfrontJ9J8J7J4J5J6012345rearfront初始状态J4,J5,J6出队J7,J8,J9入队队空：front==rear队满：front==rear解决方案：1.另外设一个标志以区别队空、队满2.少用一个元素空间：队空：front==rear

队满：(rear+1)%M==front队空：front==rear队满：front==rear3业务实现—总体描述学生基本成绩审核模块，假想学生的成绩单，放在一个队列里，先来的先审核，后来的后审核。用过循环队列实现学生成绩信息审查、修改、保存的功能。整个模块的设计和实现的思路如下：创建学生成绩信息顺序队列类，用以记录要进行审核学生的成绩信息。创建学生成绩信息业务类，用以实现学生成绩信息显示，入队、出队以及审核后的保存。从数据控制层中，获取学生成绩信息，并放入到学生信息数组sx[]中，供表现层调用。在入队方法中，从表现层中将要进行审核的学生成绩信息压入到循环队列中。在出队方法中，从循环队列中获取要进行审核的学生成绩信息，并返回给表现层。在保存方法中，从表现层将进行修改的学生成绩信息传入，调用数据控制层的方法实现学生信息的保存。3.1业务实现—成绩审核顺序队列类该类是利用循环队列的思想，来保存需要进行审核的学生成绩信息，其主要的成员有：Student_info[]Data：用以记录需要进行审核的学生成绩信息intfront，rear：队头、队尾指针变量具体代码实现如下：publicclassQueue_node{ publicStudent_info[]Data;//学生成绩顺序队列

publicintfront,rear; //队头、队尾指针}

3.2业务实现—成绩信息审核业务类该类用以实现学生基本信息的初始化，并实现学生成绩信息审核的入队、出队以及修改后的学生成绩信息的保存。具体的成员和方法如下：publicclassQueue{ StudentMangerBa=newStudentManger();//创建数据控制层对象

publicQueue_nodes=newQueue_node();//申明学生队列对象

publicintMax=0; //记录学生信息的人数，为顺序队列分配空间

publicStudent_info[]sx; //记录要进行审核的学生成绩信息，供界面使用

publicQueue() { Init(); //初始化方法

} publicvoidInit() publicvoidInitQue()//初始化队列

publicintEnQue(Student_infoelem)//入队操作

publicStudent_infoDeQue()//出队操作

publicintsave(Student_infoelem)//保存学生成绩信息}

3.3业务实现—成绩顺序队列初始化该方法是在业务对象实例化时，实现调用，进行必要的初始化，步骤如下：从数据控制层获取学生基本信息的长度。初始化学生基本信息数组以及每个成员，供表现层调用和学生成绩信息保存时使用。初始化循环队列数组的大小以及队头、队尾指针变量的值。publicvoidInit(){ Max=Ba.Max; sx=newStudent_info[Max]; //初始化学生信息数组

s.Data=newStudent_info[Max]; //初始化队列 s.front=0; s.rear=0;for(inti=0;i<Max;i++) //逐个初始化学生信息数组元素

{ sx[i]=Ba.base_info[i]; }}

3.4业务实现—成绩信息入队实现学生成绩信息入队的操作，实现步骤如下：从应用界面中传入要进行入队的学生信息。进行顺序队列是否已满。若满返回不成功标志0。进行学生信息元素入队操作，修改队尾指针值。并返回成功标志1。publicintEnQue(Student_infoelem){//元素入队

if((s.rear+1)%Max==s.front) //队列为满

return0; s.Data[s.rear]=elem; //元素入队

s.rear=(s.rear+1)%Max; //修改队尾值

return1;}

3.5业务实现—成绩信息出队实现学生成绩信息出队的操作，实现步骤如下：进行顺序队列是否已空。进行学生信息出队操作，修改队尾头指针值。并返回在循环队列中的位置和出队的学生成绩信息。publicStudent_infoDeQue() {//元素出队

Student_infotemp=newStudent_info(); if(s.front==s.rear)returnnull; //队列为空

temp=s.Data[s.front]; //元素出队

s.front=(s.front+1)%Max; //修改队头值

returntemp; }

3.6业务实现—成绩信息保存用以实现学生成绩信息修改的保存，具体步骤如下：从界面中传入所进行修改的学生成绩信息。调用数据控制层对象的方法实现修改后的学生成绩信息保存。。 publicintsave(Student_infoelem) {//保存所修改的学生成绩信息

returnBa.Save_Data(elem,2); }

4、知识扩展：链式队列链队列结点定义：用链式存储表示的队列，称为链队列，简称链队头结点