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

循环队列的基本操作一、实验目的1. 理解并掌握队列的逻辑结构和顺序存储结构，了解循环队列的特点；2. 掌握循环队列中基本操作的相关算法；3. 编程实现相关算法；4. 学会利用循环队列解决实际问题。二、实验条件Visual C+。三、实验原理及相关知识1. 循环队列存储结构描述#define MAXSIZE 100 /最大队列长度typedef struct QElemType *base; /存储空间基址 int front; /头指针 int rear; /尾指针SqQueue;2. 基本操作的算法描述设下标为index，队列长度为m，则下一个下标的累进循环计算公式为： index_next = ( index+1 ) % m。实验中涉及的三个关键操作时循环队列中求队列长度、入队和出队操作。(1) 求长度所谓求队列长度，即技术队列中元素的个数。算法思想：根据循环队列的结构特征，可以用公式（Q.rear-Q.front+ MAXSIZE）%MAXSIZE直接计算出队列的长度。算法描述Status QueueLength(SqQueue Q) return ( ( Q.rear-Q.front+ MAXSIZE) %MAXSIZE); /QueueLength(2) 入队入队运算实际上相当于顺序表中的插入运算，所不同的是这里只能在队尾插入元素。算法思想： 将元素e插入循环队列中队尾元素的下一个存储空间 修改队尾指针，根据循环累计公式计算出其新位置算法描述Status EnQueue(SqQueue &Q, QElemType e)if ( ( Q.rear + 1 ) % MAXSIZE = Q.front ) return ERROR; /队列满 Q.baseQ.rear = e; Q.rear = ( Q.rear + 1 ) % MAXSIZE; return OK;/ EnQueue(3) 出队出队运算实际上相当于顺序表中的删除运算，所不同的是这里只能在队头删除元素。算法思想：修改队头指针，根据循环累计公式计算出其新位置算法描述Status DeQueue(SqQueue &Q, QElemType &e)if (Q.rear = Q.front ) return ERROR; /队列为空 e = Q.baseQ.front; Q.front = ( Q.front + 1 ) % MAXSIZE; return OK;/ DeQueue四、实验步骤1. 使用C语言实现循环队列的初始化、计算长度、入队、出队和遍历算法2. 用顺序存储方式构造一个循环队列Q，并输出构造好的队列和该队列的长度3. 在第1步所构造的队列Q中将元素e入队，并将更新后的队列Q输出4. 在第2步更新后所得到的队列Q中将队头元素出队，用变量e返回该元素，并将更新后的队列Q输出五、思考题及其它1. 使用循环队列实现输出杨辉三角的前N行2. 如何使用循环队列解决“猴子选大王“问题【参考程序】#include stdio.h#include malloc.h#define OK 1#define ERROR 0#define MAXQSIZE 10 /*最大队列长度+1*/typedef int QElemType;typedef struct QElemType *base; int front; int rear; SqQueue;int InitQueue(SqQueue *Q) Q-base=(QElemType *)malloc(MAXQSIZE*sizeof(QElemType); if(!Q-base) return ERROR; Q-front = Q-rear = 0; return OK;int EnQueue(SqQueue *Q,QElemType e) if( (Q-rear+1)%MAXQSIZE=Q-front ) / 队列满 return ERROR; Q-baseQ-rear=e; Q-rear=(Q-rear+1)%MAXQSIZE ; return OK;int DeQueue(SqQueue *Q, QElemType *e) if(Q-front = Q-rear) / 队列空 return ERROR; *e=Q-baseQ-front; Q-front=(Q-front+1)%MAXQSIZE; return OK;int QueueLength(SqQueue Q) return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;void QueueTraverse(SqQueue Q) /*从队头到队尾依次打印队列Q中每个元素*/ int i,k; k=QueueLength(Q); for(i=1;i=k;i+) printf(%d ,Q.baseQ.front); Q.front=(Q.front+1)%MAXQSIZE; void main() int n,e,i;SqQueue q; InitQueue(&q); /初始化循环队列 printf(该循环队列最多可存放%d个元素n,MAXQSIZE-1); printf(请输入数据元素的个数n n); scanf(%d,&n); printf(n请输入%d个整数n,n); /*创建队列*/ for(i=1;i=n;i+) scanf(%d,&e); EnQueue(&q, e); /入队 printf(q=); QueueTraverse(q); /输出循环队列q的内容 fflush(stdin);/刷新缓冲区 printf(n请输入入队元素en); scanf(%d,&e); EnQueue(&q, e); /入队 printf(q=); QueueTraverse(q); /输出循环队列q的内容 f