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

《实验三循环队列基本操作.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验三循环队列基本操作一实验目的1．熟悉并能实现循环队列的定义和基本操作。2．了解用队列解决实际应用问题。二实验要求1．进行队列的基本操作时要注意队列“先进先出”的特性。2．复习关于队列操作的基础知识。3．编写完整程序完成下面的实验内容并上机运行。4．整理并上交实验报告。三实验内容1．任意输入队列长度和队列中的元素值，构造一个顺序循环队列，对其进行清空、插入新元素、返回队头元素以及删除队头元素操作。#include#include#include#defineMAXQSI

2、ZE100//最大队列长度#defineOK1#defineERROR0#defineOVERFLOW-2typedefstruct{int*base;//初始化的动态分配存储空间基址intfront;//头指针，若队列不空，指向队列头元素intrear;//尾指针，若队列不空，指向队列尾元素的下一个位置}SqQueue;//-----------------循环队列的基本操作---------------------intInitQueue(SqQueue&Q){//构造一个空队列QQ.base=(int*)malloc(MA

3、XQSIZE*sizeof(int));if(!Q.base)exit(OVERFLOW);//存储分配失败Q.front=Q.rear=0;returnOK;}intQueueLength(SqQueueQ){//返回Q的元素个数，即队列长度return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;}voiddisplay(SqQueueQ){//显示队列中的元素if(Q.front==Q.rear)printf("空队列，没有元素");for(inti=Q.front;i

4、ntf("%3d",Q.base[i]);printf("");}intEnQueue(SqQueue&Q,inte){//插入元素e为Q的新的队尾元素if((Q.rear+1)%MAXQSIZE==Q.front)returnERROR;Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXQSIZE;returnOK;}intDeQueue(SqQueue&Q,int&e){//若队列不空，则删除Q的队头元素，用e返回其值，并返回Ok，否则，返回ERRORif(Q.front==Q.rear)ret

5、urnERROR;e=Q.base[Q.front];Q.front=(Q.front+1)%MAXQSIZE;returnOK;}intGetHead(SqQueue&Q){if(Q.front==Q.rear)return0;elsereturnQ.base[Q.front];}voidclear(SqQueue*q){q->rear=q->front=0;}intmain(){intm,n,e;SqQueueQ;InitQueue(Q);printf("请输入要插入的元素个数：");scanf("%d",&m);for

6、(inti=1;i<=m;i++){printf("请输入要插入的元素：");scanf("%d",&n);EnQueue(Q,n);}printf("插入元素后,队列中的元素为:");display(Q);printf("队列的长度为:%d",QueueLength(Q));printf("队列的头元素为:%d",GetHead(Q));printf("删除队头元素后，队列中元素为:");DeQueue(Q,e);display(Q);printf("队列的长度为:%d",QueueLength(Q

7、));printf("队列的头元素为:%d",GetHead(Q));printf("被删除元素为:");printf("%d",e);printf("现在开始清空");clear(&Q);display(Q);printf("");return0;}2．约瑟夫环的实现：设有n个人围坐在圆桌周围，现从某个位置i上的人开始报数，数到m的人就站出来。下一个人，即原来的第m+1个位置上的人，又从1开始报数，再是数到m的人站出来。依次重复下去，直到全部的人都站出来，按出列的先后又可得到一个新的序列。由于该问题是由古罗

8、马著名的史学家Josephus提出的问题演变而来，所以通常称为Josephus问题。例如：当n=8,m=4,i=1时，得到的新序列为：4，8，5，2，1，3，7，6编写程序选择循环队列作为存储结构模拟整个过程，并依次输出出列的各人的编号。#include