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

数据结构实验报告-试验三 循环队列的基本操作及应用一、 问题描述：熟悉并掌握循环队列的相关操作，自己设计程序，实现循环队列的构造、清空、销毁及队列元素的插入和删除等相关操作。二、 数据结构设计： #define MAXQSIZE 10 /最大队列长度 struct SqQueue QElemType *base; /初始化动态分配存储空间 Int front; / 头指针，若队列不空，只想对列头元素 int rear; /尾指针，若队列不空，指向队列尾元素的 /下一个位置 ;三、功能设计： 程序中所涉及到的函数如下： Status InitQueue(SqQueue &Q) /构造一个空队列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 &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 #include #include / malloc()等 #include / INT_MAX等 #include / EOF(=Z或F6),NULL #include / atoi() #include / eof() #include / floor(),ceil(),abs() #include / exit() #include / cout,cin / 函数结果状态代码 #define 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;int rear;#includec1.htypedef int QElemType;#includec3-3.hStatus 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.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 GetHead(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.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)coutti;void main()int i=0,a; QElemType d;SqQueue Q;InitQueue(Q);cout初始化队列后,队列空否?(1:空 0:否)QueueEmpty(Q)n;coutd;if(d=-1)break;i+;EnQueue(Q,d);while(iMAXQSIZE-1);cout队列长度为:QueueLength(Q)n;cout现在队列空否?(1:空 0:否)QueueEmpty(Q)n;for(i=1;i=QueueLength(Q);i+)DeQueue(d);cout删除的元素为:da;EnQueue(Q,a);cout现在队列中的元素为:n;QueueTraverse(Q,visit); coutn; GetHead(Q,a);cout现在对头元素为:an; ClearQueue(); cout清空队列后,对