实验三循环队列基本操作.doc

实验三 循环队列基本操作一 实验目的1熟悉并能实现循环队列的定义和基本操作。2了解用队列解决实际应用问题。二 实验要求1进行队列的基本操作时要注意队列“先进先出”的特性。2复习关于队列操作的基础知识。3编写完整程序完成下面的实验内容并上机运行。4整理并上交实验报告。三 实验内容1任意输入队列长度和队列中的元素值，构造一个顺序循环队列，对其进行清空、插入新元素、返回队头元素以及删除队头元素操作。#include #include #include #define MAXQSIZE 100 /最大队列长度#define OK 1#define ERROR 0#define OVERFLOW -2typedef struct int *base; /初始化的动态分配存储空间基址 int front; /头指针，若队列不空，指向队列头元素 int rear; /尾指针，若队列不空，指向队列尾元素的下一个位置SqQueue;/-循环队列的基本操作-int InitQueue (SqQueue &Q) /构造一个空队列Q Q.base = (int *)malloc(MAXQSIZE * sizeof(int); if(!Q.base) exit (OVERFLOW);/存储分配失败 Q.front = Q.rear = 0; return OK;int QueueLength (SqQueue Q)/返回Q的元素个数，即队列长度 return (Q.rear - Q.front + MAXQSIZE)% MAXQSIZE;void display(SqQueue Q)/显示队列中的元素 if(Q.front=Q.rear) printf(空队列，没有元素); for(int i=Q.front;irear = q-front = 0;int main() int m,n,e; SqQueue Q; InitQueue(Q); printf(请输入要插入的元素个数：n); scanf(%d,&m); for(int i=1; i=m; i+) printf(请输入要插入的元素：n); scanf(%d,&n); EnQueue(Q,n); printf(插入元素后,队列中的元素为:n); display(Q); printf(队列的长度为:%dn,QueueLength(Q); printf(队列的头元素为:%dn,GetHead(Q); printf(n删除队头元素后，队列中元素为:n); DeQueue(Q,e); display(Q); printf(队列的长度为:%dn,QueueLength(Q); printf(队列的头元素为:%dn,GetHead(Q); printf(被删除元素为:n); printf(%dn,e); printf(现在开始清空n); clear(&Q); display(Q); printf(n); return 0;2约瑟夫环的实现：设有n个人围坐在圆桌周围，现从某个位置 i 上的人开始报数，数到 m 的人就站出来。下一个人，即原来的第m+1个位置上的人，又从1开始报数，再是数到m的人站出来。依次重复下去，直到全部的人都站出来，按出列的先后又可得到一个新的序列。由于该问题是由古罗马著名的史学家Josephus提出的问题演变而来，所以通常称为Josephus 问题。 例如：当n=8,m=4,i=1时，得到的新序列为： 4，8，5，2，1，3，7，6 编写程序选择循环队列作为存储结构模拟整个过程，并依次输出出列的各人的编号。 #include #include #include #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -2 #define INFEASIBLE -1 typedef int Status; int MAXQSIZE; typedef struct int *base; int front; int rear; SqQueue; Status InitQueue(SqQueue& Q) Q.base = (int*)malloc(MAXQSIZE*sizeof(int); if(!Q.base) exit(OVERFLOW); Q.front = Q.rear = 0; return OK; Status EnQueue(SqQueue& Q,int e) if(Q.rear+1)%MAXQSIZE = Q.front) return ERROR; Q.baseQ.rear = e; Q.rear = (Q.rear+1)%MAXQSIZE; return OK; Status DeQueue(SqQueue& Q,int& e) if (Q.front = Q.rear) return ERROR; e = Q.baseQ.front; Q.baseQ.front = 0; Q.front = (Q.front+1)%MAXQSIZE; return OK; Status Josephus(SqQueue& Q,int m) printf(The Josephus Ring Count:n); while(TRUE) int i = 1; int num = 0; while (i+ != m) DeQueue(Q,num); EnQueue(Q,num); DeQueue(Q,num); printf(%d ,num); if (Q.front = Q.rear) break; printf(n); return OK; int main() SqQueue que; int m,n; printf(Please input the n:); scanf(%d,&n); printf(Pl