试验 循环队列的基本操作及应用

1、数据结构实验报告-试验三 循环队列的基本操作及应用一、 问题描述：熟悉并掌握循环队列的相关操作，自己设计程序，实现循环队列的构造、清空、销毁及队列元素的插入和删除等相关操作。二、 数据结构设计： #define MAXQSIZE 10 /最大队列长度 struct SqQueue QElemType *base; /初始化动态分配存储空间 Int front; / 头指针，若队列不空，只想对列头元素 int rear; /尾指针，若队列不空，指向队列尾元素的 /下一个位置 ;三、功能设计： 程序中所涉及到的函数如下： Status InitQueue(SqQueue &Q) /构造一个

2、空队列Q Status DestroyQueue(SqQueue &Q) /销毁队列Q,Q不再存在 Status ClearQueue(SqQueue &Q) /将Q清为空队列 Status QueueEmpty(SqQueue Q) /若队列Q为空队列，则 /返回TRUE，否则返回FALSE int QueueLength(SqQueue Q) /返回Q的元素个数，即队列长度Status GetHead(SqQueue Q,QElemType &e)/若队列不空，则用e返回Q的对 /头元素，并返回OK，否则返回ERROR Status EnQueue(SqQueue

3、&Q,QElemType e)/插入元素e为Q的新的队尾元素Status DeQueue(SqQueue &Q,QElemType &e)/若队列不空，则删除Q的队头 /元素，用e返回其值，并返回 /OK，否则返回ERRORStatus QueueTraverse(SqQueue Q,void(*vi)(QElemType)/从队头到队尾依次 /对队列Q中每个元素调用函数 /vi()。一旦vi失败，则操作失败四、源程序：/ c1.h (程序名) #include<string.h> #include<ctype.h> #include<ma

4、lloc.h> / malloc()等 #include<limits.h> / INT_MAX等 #include<stdio.h> / EOF(=Z或F6),NULL #include<stdlib.h> / atoi() #include<io.h> / eof() #include<math.h> / floor(),ceil(),abs() #include<process.h> / exit() #include<iostream.h> / cout,cin / 函数结果状态代码 #defin

5、e TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 / #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此 /行 typedef int Status; / Status是函数的类型,其值是函数结果状态代码，如OK等 typedef int Boolean; / Boolean是布尔类型,其值是TRUE或FALSE/ c3-3.h#define MAXQSIZE 10struct SqQueueQElemType *base;int front;

6、int rear;#include"c1.h"typedef int QElemType;#include"c3-3.h"Status InitQueue(SqQueue &Q) /构造一个空队列QQ.base=(QElemType *)malloc(MAXQSIZE*sizeof(QElemType);if(!Q.base)/储存分配失败exit(OVERFLOW);Q.front=Q.rear=0;return OK;Status DestroyQueue(SqQueue &Q)/销毁队列Q,Q不再存在if(Q.base)free(Q

7、.base);Q.base=NULL;Q.front=Q.rear=0;return OK;Status ClearQueue(SqQueue &Q)/将Q清为空队列Q.front=Q.rear=0;return OK;Status QueueEmpty(SqQueue Q)/若队列Q为空队列，则返回TREU，否则返回FALSEif(Q.front=Q.rear)/队列空的标志return TRUE;elsereturn FALSE;int QueueLength(SqQueue Q)/Qreturn(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;Status G

8、etHead(SqQueue Q,QElemType &e)/if(Q.front=Q.rear)/队列空return ERROR;e=*(Q.base+Q.front);return OK;Status EnQueue(SqQueue &Q,QElemType e)if(Q.rear+1)%MAXQSIZE=Q.front)/队列满return ERROR;Q.baseQ.rear=e;Q.rear=(Q.rear+1)%MAXQSIZE;returnOK;Status DeQueue(SqQueue &Q,QElemType &e)if(Q.front=Q.

9、rear)/队列空return ERROR;e=Q.baseQ.front;Q.front=(Q.front+1)%MAXQSIZE;return OK;Status QueueTraverse(SqQueue Q,void(*vi)(QElemType)int i;i=Q.front;while(i!=Q.rear)vi(*(Q.base+i);i=(i+1)%MAXQSIZE;printf("n");return OK;void visit(QElemType i)cout<<"t"<<i;void main()int i=0

10、,a; QElemType d;SqQueue Q;InitQueue(Q);cout<<"初始化队列后,队列空否?(1:空 0:否)"<<QueueEmpty(Q)<<"n"cout<<"请输入整型队列元素,-1为提前结束符:n"docin>>d;if(d=-1)break;i+;EnQueue(Q,d);while(i<MAXQSIZE-1);cout<<"队列长度为:"<<QueueLength(Q)<<&q

11、uot;n"cout<<"现在队列空否?(1:空 0:否)"<<QueueEmpty(Q)<<"n"for(i=1;i<=QueueLength(Q);i+)DeQueue(d);cout<<"删除的元素为:"<<d<<"请输入待插入的元素:"cin>>a;EnQueue(Q,a);cout<<"现在队列中的元素为:n"QueueTraverse(Q,visit); cout<<"n" GetHead(Q,a);cout<<"现在对头元素为:"<<a<<"n" ClearQueue(); cout<<"清空队列后