实现循环队列的入队出队等基本操作

《实现循环队列的入队出队等基本操作》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、循环队列的基本操作  　　一、实验目的　　1.理解并掌握队列的逻辑结构和顺序存储结构，了解循环队列的特点；　　2.掌握循环队列中基本操作的相关算法；　　3.编程实现相关算法；　　4.学会利用循环队列解决实际问题。　　二、实验条件　　VisualC++。　　三、实验原理及相关知识　　1.循环队列存储结构描述　　#defineMAXSIZE100//最大队列长度　　typedefstruct　　{　　QElemType*base;//存储空间基址　　intfront;//头指针　　intrear;//尾

2、指针　　}SqQueue;　　2.基本操作的算法描述　　设下标为index，队列长度为m，则下一个下标的累进循环计算公式为：　　index_next=(index+1)%m。　　实验中涉及的三个关键操作时循环队列中求队列长度、入队和出队操作。　　(1)求长度　　所谓求队列长度，即技术队列中元素的个数。　　算法思想：根据循环队列的结构特征，可以用公式（Q.rear-Q.front+MAXSIZE）%MAXSIZE直接计算出队列的长度。　　算法描述　　StatusQueueLength(SqQueueQ

3、)　　{　　return((Q.rear-Q.front+MAXSIZE)%MAXSIZE);　　}//QueueLength　　(2)入队　　入队运算实际上相当于顺序表中的插入运算，所不同的是这里只能在队尾插入元素。　　算法思想：①将元素e插入循环队列中队尾元素的下一个存储空间　　②修改队尾指针，根据循环累计公式计算出其新位置　　算法描述　　StatusEnQueue(SqQueue&Q,QElemTypee)　　{ 　　if((Q.rear+1)%MAXSIZE==Q.front)　　retur

4、nERROR;//队列满　　Q.base[Q.rear]=e;　　Q.rear=(Q.rear+1)%MAXSIZE;　　returnOK;　　}//EnQueue　　(3)出队　　出队运算实际上相当于顺序表中的删除运算，所不同的是这里只能在队头删除元素。　　算法思想：修改队头指针，根据循环累计公式计算出其新位置　　算法描述　　StatusDeQueue(SqQueue&Q,QElemType&e)　　{ 　　if(Q.rear==Q.front)returnERROR;//队列为空　　e=Q.ba

5、se[Q.front];　　Q.front=(Q.front+1)%MAXSIZE;　　returnOK;　　}//DeQueue　　　　四、实验步骤 　　1.使用C语言实现循环队列的初始化、计算长度、入队、出队和遍历算法　　2.用顺序存储方式构造一个循环队列Q，并输出构造好的队列和该队列的长度　　3.在第1步所构造的队列Q中将元素e入队，并将更新后的队列Q输出　　4.在第2步更新后所得到的队列Q中将队头元素出队，用变量e返回该元素，并将更新后的队列Q输出　　五、思考题及其它　　1.使用循环队列实现

6、输出杨辉三角的前N行　　2.如何使用循环队列解决“猴子选大王“问题　　　　【参考程序】　　#include"stdio.h"　　#include"malloc.h"　　#defineOK1　　#defineERROR0　　#defineMAXQSIZE10/*最大队列长度+1*/　　typedefintQElemType;　　typedefstruct{ 　　QElemType*base; 　　intfront; 　　intrear; 　　}SqQueue;　　intInitQueue(SqQueu

7、e*Q){　　Q->base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType));　　if(!Q->base)returnERROR;　　Q->front=Q->rear=0;　　returnOK;　　}　　intEnQueue(SqQueue*Q,QElemTypee){ 　　if((Q->rear+1)%MAXQSIZE==Q->front)//队列满　　returnERROR;　　Q->base[Q->rear]=e;　　　　Q->rear=(Q->r

8、ear+1)%MAXQSIZE;　　　　　　returnOK;　　}　　intDeQueue(SqQueue*Q,QElemType*e){ 　　if(Q->front==Q->rear)//队列空　　returnERROR;　　*e=Q->base[Q->front];　　Q->front=(Q->front+1)%MAXQSIZE;　　returnOK;　　}　　intQueueLength(SqQueueQ){ 　　return(Q.rear-Q.front+M