第六章學(xué)生成績(jī)信息審核（隊(duì)列）教學(xué)目標(biāo)：掌握隊(duì)列的基本概念和基本操作循環(huán)隊(duì)列的基本概念和操作應(yīng)用循環(huán)隊(duì)列實(shí)現(xiàn)學(xué)生成績(jī)信息審核管理了解鏈?zhǔn)疥?duì)列實(shí)現(xiàn)原理重點(diǎn)：學(xué)生成績(jī)信息審核循環(huán)隊(duì)列實(shí)現(xiàn)難點(diǎn)：循環(huán)隊(duì)列的操作實(shí)現(xiàn)6.1學(xué)生成績(jī)審核功能描述學(xué)生成績(jī)信息審核界面實(shí)現(xiàn)如下：6.2隊(duì)列的基本概念隊(duì)列的定義和特點(diǎn)：定義：隊(duì)列是限定只能在表的一端進(jìn)行插入，在表的另一端進(jìn)行刪除的線性表隊(duì)尾(rear)——允許插入的一端隊(duì)頭(front)——允許刪除的一端

隊(duì)列特點(diǎn)：先進(jìn)先出(FIFO)a1a2a3…….an入隊(duì)出隊(duì)frontrear隊(duì)列Q=(a1,a2,……,an)6.2.1順序隊(duì)列的存儲(chǔ)隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)：用一維數(shù)組實(shí)現(xiàn)sq[M]123450front=0rear=0隊(duì)空設(shè)兩個(gè)指針front,rear,約定：rear指示隊(duì)尾元素的下一個(gè)位置；front指示隊(duì)頭元素初值front=rear=0空隊(duì)列條件：front==rear入隊(duì)列：sq[++rear]=x;出隊(duì)列：x=sq[++front];10rear=120rear=230rear=312345030rear=32010front=0123450front=0rear=0front=1front=212345030rear=3front=240rear=450rear=560rear=66.2.2順序隊(duì)列的存儲(chǔ)存在的問題存在問題設(shè)數(shù)組維數(shù)為M，則：當(dāng)front=0,rear=M-1時(shí)，再有元素入隊(duì)發(fā)生溢出——真溢出當(dāng)front0,rear=M-1時(shí)，再有元素入隊(duì)發(fā)生溢出——假溢出解決方案隊(duì)首固定，每次出隊(duì)剩余元素向下移動(dòng)——浪費(fèi)時(shí)間循環(huán)隊(duì)列基本思想：把隊(duì)列設(shè)想成環(huán)形，讓sq[0]接在sq[M-1]之后，若rear+1==M,則令rear=0;0M-11frontrear…...…...實(shí)現(xiàn)：利用“模”運(yùn)算入隊(duì)：rear=(rear+1)%M;sq[rear]=x;出隊(duì)：front=(front+1)%M;x=sq[front];隊(duì)滿、隊(duì)空判定條件6.2.3循環(huán)隊(duì)列012345rearfrontJ4J5J6012345rearfrontJ9J8J7J4J5J6012345rearfront初始狀態(tài)J4,J5,J6出隊(duì)J7,J8,J9入隊(duì)隊(duì)空：front==rear隊(duì)滿：front==rear解決方案：1.另外設(shè)一個(gè)標(biāo)志以區(qū)別隊(duì)空、隊(duì)滿2.少用一個(gè)元素空間：隊(duì)空：front==rear

隊(duì)滿：(rear+1)%M==front隊(duì)空：front==rear隊(duì)滿：front==rear3業(yè)務(wù)實(shí)現(xiàn)—總體描述學(xué)生基本成績(jī)審核模塊，假想學(xué)生的成績(jī)單，放在一個(gè)隊(duì)列里，先來的先審核，后來的后審核。用過循環(huán)隊(duì)列實(shí)現(xiàn)學(xué)生成績(jī)信息審查、修改、保存的功能。整個(gè)模塊的設(shè)計(jì)和實(shí)現(xiàn)的思路如下：創(chuàng)建學(xué)生成績(jī)信息順序隊(duì)列類，用以記錄要進(jìn)行審核學(xué)生的成績(jī)信息。創(chuàng)建學(xué)生成績(jī)信息業(yè)務(wù)類，用以實(shí)現(xiàn)學(xué)生成績(jī)信息顯示，入隊(duì)、出隊(duì)以及審核后的保存。從數(shù)據(jù)控制層中，獲取學(xué)生成績(jī)信息，并放入到學(xué)生信息數(shù)組sx[]中，供表現(xiàn)層調(diào)用。在入隊(duì)方法中，從表現(xiàn)層中將要進(jìn)行審核的學(xué)生成績(jī)信息壓入到循環(huán)隊(duì)列中。在出隊(duì)方法中，從循環(huán)隊(duì)列中獲取要進(jìn)行審核的學(xué)生成績(jī)信息，并返回給表現(xiàn)層。在保存方法中，從表現(xiàn)層將進(jìn)行修改的學(xué)生成績(jī)信息傳入，調(diào)用數(shù)據(jù)控制層的方法實(shí)現(xiàn)學(xué)生信息的保存。3.1業(yè)務(wù)實(shí)現(xiàn)—成績(jī)審核順序隊(duì)列類該類是利用循環(huán)隊(duì)列的思想，來保存需要進(jìn)行審核的學(xué)生成績(jī)信息，其主要的成員有：Student_info[]Data：用以記錄需要進(jìn)行審核的學(xué)生成績(jī)信息intfront，rear：隊(duì)頭、隊(duì)尾指針變量具體代碼實(shí)現(xiàn)如下：publicclassQueue_node{ publicStudent_info[]Data;//學(xué)生成績(jī)順序隊(duì)列

publicintfront,rear; //隊(duì)頭、隊(duì)尾指針}

3.2業(yè)務(wù)實(shí)現(xiàn)—成績(jī)信息審核業(yè)務(wù)類該類用以實(shí)現(xiàn)學(xué)生基本信息的初始化，并實(shí)現(xiàn)學(xué)生成績(jī)信息審核的入隊(duì)、出隊(duì)以及修改后的學(xué)生成績(jī)信息的保存。具體的成員和方法如下：publicclassQueue{ StudentMangerBa=newStudentManger();//創(chuàng)建數(shù)據(jù)控制層對(duì)象

publicQueue_nodes=newQueue_node();//申明學(xué)生隊(duì)列對(duì)象

publicintMax=0; //記錄學(xué)生信息的人數(shù)，為順序隊(duì)列分配空間

publicStudent_info[]sx; //記錄要進(jìn)行審核的學(xué)生成績(jī)信息，供界面使用

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

} publicvoidInit() publicvoidInitQue()//初始化隊(duì)列

publicintEnQue(Student_infoelem)//入隊(duì)操作

publicStudent_infoDeQue()//出隊(duì)操作

publicintsave(Student_infoelem)//保存學(xué)生成績(jī)信息}

3.3業(yè)務(wù)實(shí)現(xiàn)—成績(jī)順序隊(duì)列初始化該方法是在業(yè)務(wù)對(duì)象實(shí)例化時(shí)，實(shí)現(xiàn)調(diào)用，進(jìn)行必要的初始化，步驟如下：從數(shù)據(jù)控制層獲取學(xué)生基本信息的長(zhǎng)度。初始化學(xué)生基本信息數(shù)組以及每個(gè)成員，供表現(xiàn)層調(diào)用和學(xué)生成績(jī)信息保存時(shí)使用。初始化循環(huán)隊(duì)列數(shù)組的大小以及隊(duì)頭、隊(duì)尾指針變量的值。publicvoidInit(){ Max=Ba.Max; sx=newStudent_info[Max]; //初始化學(xué)生信息數(shù)組

s.Data=newStudent_info[Max]; //初始化隊(duì)列 s.front=0; s.rear=0;for(inti=0;i<Max;i++) //逐個(gè)初始化學(xué)生信息數(shù)組元素

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

3.4業(yè)務(wù)實(shí)現(xiàn)—成績(jī)信息入隊(duì)實(shí)現(xiàn)學(xué)生成績(jī)信息入隊(duì)的操作，實(shí)現(xiàn)步驟如下：從應(yīng)用界面中傳入要進(jìn)行入隊(duì)的學(xué)生信息。進(jìn)行順序隊(duì)列是否已滿。若滿返回不成功標(biāo)志0。進(jìn)行學(xué)生信息元素入隊(duì)操作，修改隊(duì)尾指針值。并返回成功標(biāo)志1。publicintEnQue(Student_infoelem){//元素入隊(duì)

if((s.rear+1)%Max==s.front) //隊(duì)列為滿

return0; s.Data[s.rear]=elem; //元素入隊(duì)

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

return1;}

3.5業(yè)務(wù)實(shí)現(xiàn)—成績(jī)信息出隊(duì)實(shí)現(xiàn)學(xué)生成績(jī)信息出隊(duì)的操作，實(shí)現(xiàn)步驟如下：進(jìn)行順序隊(duì)列是否已空。進(jìn)行學(xué)生信息出隊(duì)操作，修改隊(duì)尾頭指針值。并返回在循環(huán)隊(duì)列中的位置和出隊(duì)的學(xué)生成績(jī)信息。publicStudent_infoDeQue() {//元素出隊(duì)

Student_infotemp=newStudent_info(); if(s.front==s.rear)returnnull; //隊(duì)列為空

temp=s.Data[s.front]; //元素出隊(duì)

s.front=(s.front+1)%Max; //修改隊(duì)頭值

returntemp; }

3.6業(yè)務(wù)實(shí)現(xiàn)—成績(jī)信息保存用以實(shí)現(xiàn)學(xué)生成績(jī)信息修改的保存，具體步驟如下：從界面中傳入所進(jìn)行修改的學(xué)生成績(jī)信息。調(diào)用數(shù)據(jù)控制層對(duì)象的方法實(shí)現(xiàn)修改后的學(xué)生成績(jī)信息保存。。 publicintsave(Student_infoelem) {//保存所修改的學(xué)生成績(jī)信息

returnBa.Save_Data(elem,2); }

4、知識(shí)擴(kuò)展：鏈?zhǔn)疥?duì)列鏈隊(duì)列結(jié)點(diǎn)定義：用鏈?zhǔn)酱鎯?chǔ)表示的隊(duì)列，稱為鏈隊(duì)列，簡(jiǎn)稱鏈隊(duì)頭結(jié)點(diǎn)