数据结构(05中文)教案第3章队列相关6990-1

数据结构1栈(Stack)队列(Queue)数据结构23.4队列(Queue)定义–队列是只允许在一端删除，在另一端插入的线性结构–允许删除的一端叫做队头(front)，允许插入的一端叫做队尾(rear)。特性–先进先出(FIFO,FirstInFirstOut)数据结构3队列的抽象数据类型ADTQueue{D={ai|aiElemSet,i=1,2,…n}R={ai-1,ai|ai-1,aiD,i=2,…n}约定a1端为队首，an端为队尾P:InitQueue(&Q)DestroyQueue(&Q)ClearQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q,&e)EnQueue(&Q,e)DeQueue(&Q,&e)QueueTraverse(Q,visit())}ADTQueue数据结构4队列的表示和实现队列的顺序表示---顺序队列–用一组连续的存储单元依次存放从队首到队尾的元素，附设两个指针front和rear分别指向队首元素和队尾元素的位置#defineMAXQSIZE100typedefstruct{QElemType*base;intfront;intrear}SqQueue;SqQueueQ;012345Q.frontQ.rear空队列数据结构5顺序队列的实现–当front=rear=0时表示空队列–当插入新元素到队尾时，rear加1–当删除队首元素时，front加1–这种顺序队列空间利用率低，每个位置只能使用一次012345Q.frontQ.rear空队列012345Q.frontQ.rearJ1,J2,J3相继入队J1J2J3012345Q.frontQ.rearJ1,J2相继出队J3012345Q.frontQ.rear队列满J4J5J6数据结构6队列的进队和出队进队时队尾指针先进一rear=rear+1，再将新元素按rear指示位置加入。出队时队头指针先进一front=front+1，再将下标为front的元素取出。队满时再进队将溢出出错；队空时再出队将队空处理。数据结构7循环队列及其实现循环队列–为了提高队列的空间利用率，提出循环队列–结构与顺序队列相同，只是界线处理稍有不同数据结构8循环队列的进队和出队队头指针进1:front=(front+1)%maxSize;队尾指针进1:rear=(rear+1)%maxSize;数据结构9存储队列的数组被当作首尾相接的表处理。队头、队尾指针加1时从maxSize-1直接进到0，可用语言的取模(余数)运算实现。队头指针进1:front=(front+1)%maxSize;队尾指针进1:rear=(rear+1)%maxSize;队列初始化：front=rear=0;队空条件：front==rear;队满条件：(rear+1)%maxSize==front–front=rear可能表示队空，也可能表示队满–应另设标志以便区别队空状态–或少用一个位置循环队列(CircularQueue)数据结构10循环队列及其实现循环队列–为了提高队列的空间利用率，提出循环队列–结构与顺序队列相同，只是界线处理稍有不同StatusInitQueue(SqQueue&Q){Q.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType));if(!Q.base)exit(OVERFLOW);Q.front=Q.rear=0;returnOK;}数据结构11循环队列及其实现intQueueLength(SqQueueQ){return(Q.rear–Q.front+MAXQSIZE)%MAXQSIZE;}StatusEnQueue(SqQueue&Q,QElemTypee){if((Q.rear+1)%MAXQSIZE==Q.front)returnERROR;Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXQSIZE;returnOK;}StatusDeQueue(SqQueue&Q,QElemType&e){if(Q.front==Q.rear)returnERROR;e=Q.base[Q.front];Q.front=(Q.front+1)%MAXSIZE;returnOK;}第三种方法：使用一个计数器记录队列中元素的总数（实际上是队列长度）。下面是实现循环队列上的六种基本操作，为此先给出循环队列的类型定义。#defineQueueSize100typedefcharDataType;typedefStruct{intfront;intrear;intcount;datatypedata[queuesize]}cirqueue;（1）置空队voidinitqueue(cirqueue*q){q–front=q–rear=0;q–count=0;}（2）判断队空intqueueempty(cirqueue*q){returnq–count==0;}（3）判断队满intqueuefull(cirqueue*q){returnq–count==queuesize;}（4）入队voidenqueue(cirqueue*q,datatypex){if(queuefull(q))error(“queueoverflow”);q–count++;q–data[q–rear]=x;q–rear=(q–rear+1)%queuesize;}（5）出队datatypedequeue(cirqueue*q){datatypetemp;if(queueempty(q))error(“queueunderflow”);temp=q–data[q–front];q–count--;q–front=(q–front+1)%queuesize;returntemp;}（6）取队首元素datatypequeuefront(cirqueue*q){if(queueempty(q))error(“queueisempty.”);returnq–data[q–front];}1、循环队列的优点是什么？如何判断它的空和满？2、设长度为n的链队列用单循环链表表示，若只设头指针，则怎样进行入队和出队操作；若只设尾指针呢？3、用第一种、第二种方法，即设状态标示、少用一个元素空间的方法来区别循环队列的队空和队满，试设计置空队、判队空、判队满、出队、入队及取队头元素等六个基本操作。4、如果头指针、尾指针、队列长度中只能选两个来实现队列，你使用哪两个？思考、练习题1假设循环队列只设rear和quelen来分别指示队尾元素的位置和队中元素的个数，试给出判断此循环队列的队满条件，并写出相应的入队算法。作业2出队算法？要求出队时需返回队头指针。习题数据结构19队列的链接表示—链式队列队头在链头，队尾在链尾。链式队列在进队时无队满问题，但有队空问题。队空条件为front==NULL3.4.3链队列和顺序队列类似，我们也是将这两个指针封装在一起，将链队列的类型LinkQueue定义为一个结构类型：typedefstructqueuenode{datatypedata;structqueuenode*next;}queuenode;typedefstruct{queuenode*front;queuenode*rear;}linkqueue;下面给出链队列上实现的基本运算：voidinitqueue(linkqueue*q){q–front=q–rear=null;}intqueueempty(linkqueue*q){returnq–front==null&&q–rear==null;}voidenqueue(linkqueue*q,datatypex){queuenode*pp=(queuenode*)malloc(sizeof(queuenode));p–data=x;p–next=null;if(queueempty(q))q–front=q–rear=p;else{q–rear–next=p;q–rear=p;}}Datatypedequeue(linkqueue*q){datatypex;queuenode*pif(queueempty(q))error(“queueunderflow”);p=q–front;x=p–data;q–front=p–next;if(q–rear==p)q–rear=null;free(p);returnx;}datatypequeuefront(linkqueue*q){if(queueempty(q))error(“queueisempty.”);returnq–front–data;}注意：在出队算法中，一般只需修改队头指针。但当原队中只有一个结点时，该结点既是队头也是队尾，故删去此结点时亦需修改尾指针，且删去此结点后队列变空。数据结构26队列的表示和实现队列的链式表示---链队列–用链表表示队列，附设队首指针front和队尾指针reartypedefstruct{QElemTypedata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;QueuePtrrear;}LinkQueue;LinkQueueQ;Q.frontQ.reardatanext队首队尾头结点数据结构27链队列的实现StatusInitQueue(LinkQueue&Q){Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));if(!Q.front)exit(OVERFLOW);Q.front-next=NULL;returnOK;}StatusDestroyQueue(LinkQueue&Q){while(Q.front){Q.rear=Q.front-next;free(Q.front);Q.front=Q.rear;}returnOK;}数据结构28链队列的实现Q.frontQ.rearQ.frontQ.rearx空队元素x入队Q.frontQ.rearxy元素y入队Q.frontQ.rearxy元素x出队数据结构29链队列的实现StatusEnQueue(LinkQueue&Q,QElemTypee){p=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(OVERFLOW);P-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;returnOK;}Q.frontQ.rearxe元素e入队P数据结构30StatusDeQueue(LinkQueue&Q,QElemType&e){if(Q.front==Q.rear)returnERROR;p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear==p)Q.rear=Q.front;//当最后一个元素被删除后，//队尾指针将丢失，故需对队尾指针重新赋值free(p);returnOK;}Q.frontQ.rearey元素e出队数据结构31队列应用1）解决计算机主机与外设不匹配的问题；2）解决由于多用户引起的资源竞争问题；3）离散事件的模拟----模拟实际应用中的各种排队现象；4）用于处理程序中具有先进先出特征的过程；在操作系统课程中会讲到数据结构32任务编号12345优先权200403010执行顺序31542优先级队列(PriorityQueue)？优先级队列是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素例如下表：任务的优先权及执行顺序的关系数字越小，优先权越高数据结构33习题3.1链栈中为何不设置头结点?3.2循环队列的优点是什么?