队列的基本操作

《队列的基本操作》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、个下标的累进循环计算公式为：index_next=(index+1)%m。实验中涉及的三个关键操作时循环队列中求队列长度、入队和出队操作。(1)求长度所谓求队列长度，即技术队列中元素的个数。算法思想：根据循环队列的结构特征，可以用公式（Q.rear-Q.front+MAXSIZE）%MAXSIZE直接计算出队列的长度。算法描述StatusQueueLength(SqQueueQ){return((Q.rear-Q.front+MAXSIZE)%MAXSIZE);}//QueueLength(2)入队入队运算实际上相当于顺序表中的插入运算，所不同的是这里只

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

4、算法描述StatusDeQueue(SqQueue&Q,QElemType&e){if(Q.rear==Q.front)returnERROR;//队列为空e=Q.base[Q.front];Q.front=(Q.front+1)%MAXSIZE;returnOK;}//DeQueue四、实验步骤1.使用C语言实现循环队列的初始化、计算长度、入队、出队和遍历算法2.用顺序存储方式构造一个循环队列Q，并输出构造好的队列和该队列的长度3.在第1步所构造的队列Q中将元素e入队，并将更新后的队列Q输出4.在第2步更新后所得到的队列Q中将队头元素出队，用变量e返回

5、该元素，并将更新后的队列Q输出五、思考题及其它1.使用循环队列实现输出杨辉三角的前N行2.如何使用循环队列解决“猴子选大王“问题【参考程序】#include"stdio.h"#include"malloc.h"#defineOK1#defineERROR0#defineMAXQSIZE10/*最大队列长度+1*/typedefintQElemType;typedefstruct{QElemType*base;intfront;intrear;}SqQueue;intInitQueue(SqQueue*Q){Q->base=(QElemType*)mall

6、oc(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;⑴returnOK;}intDeQueue(SqQueue*Q,QElemType*e){if(Q->front==Q->rear)//队列空returnERROR;⑵returnOK;}intQueueLength(SqQ

7、ueueQ){return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;}voidQueueTraverse(SqQueueQ){/*从队头到队尾依次打印队列Q中每个元素*/⑶}voidmain(){intn,e,i;SqQueueq;⑷//初始化循环队列printf(“该循环队列最多可存放%d个元素”,MAXQSIZE-1);printf(“请输入数据元素的个数n”);scanf("%d",&n);printf(“请输入%d个整数”,n);/*创建队列*/for(i=1;i<=n;i++){scanf("%d",

8、&e);⑸//入队}printf(“q=”);⑹//输出循环队列q的内容fflu