一、实验目的
- 领会队列的存储结构特点
- 掌握环形队列中的各种基本运算算法设计
- 熟悉利用队列解决实际问题
二、实验要求
实现环形队列的定义，头文件命名”SqQueue.h”。 利用所定义的环形队列，设计一个算法实现下面问题的求解：
问题描述：设有n个人站成一排,从左向右的编号分别为1—n,现在从左往右报数“1,2,1,2,…数到“1”的人出列，数到“2”的立即站到队伍的最右端。报数过程反复进行，直到n个人出列为止。要求给出他们的出列顺序。
算法思想提示：先将n个人的编号进队,然后反复执行以下操作,直到队列为空。
(1)出队一个元素,输出其编号(报数为1 的人出列)。
(2)若队列不空,再出队一个元素,并将刚出列的元素进队(报数为2的人站到队伍的最右端,即队尾)。
三、实验环境
Windows+DEV C++( 或者其他编译工具)
四、实验步骤及结果
1. 环形队列结点类型声明
typedef int ElemType;
typedef struct
{
ElemType data[MaxSize]; //存放队中元素
int front,rear; //队头和队尾指针
} SqQueue;2.队列基本运算在环形队上的实现
//初始化队列
void InitQueue(SqQueue *&q)
{
q=(SqQueue *)malloc(sizeof(SqQueue));
q->front=q->rear=-1;
}
//判队列是否为空
bool QueueEmpty(SqQueue *q)
{
return (q->front==q->rear);
}
//进队
bool enQueue(SqQueue *&q,ElemType e)
{
if(q->rear==MaxSize-1)//队满上溢出
return false;
q->rear++;
q->data[q->rear] = e;
return true;
}
//出队
bool deQueue(SqQueue *&q,ElemType &e)
{
if(q->front==q->rear)//队空下溢出
return false;
q->front++;
e=q->data[q->front];
return true;
}
//销毁队列
void DestroyQueue(SqQueue *&q)
{
free(q);
}
//报数
void number(int n)
{
int i;
int count=1; //count用来记第几个元素
SqQueue *q; //环形队列指针q
InitQueue(q); //初始化队列q
for(i=1; i<=n; i++) //构建初始序列
{
enQueue(q,i);
}
while(!QueueEmpty(q)) //队列不空循环
{
deQueue(q,i);
if(count%2==0) //第偶数个元素时，进队
enQueue(q,i);
else
printf("%d\t",i); //第奇数个元素时，出队输出
count++;
}
printf("\n");
DestroyQueue(q);
}SqQueue.h：
#include<stdio.h>
#include<malloc.h>
#define MaxSize 100
typedef int ElemType;
typedef struct
{
ElemType data[MaxSize]; //存放队中元素
int front,rear; //队头和队尾指针
} SqQueue;
//初始化队列
void InitQueue(SqQueue *&q)
{
q=(SqQueue *)malloc(sizeof(SqQueue));
q->front=q->rear=-1;
}
//判队列是否为空
bool QueueEmpty(SqQueue *q)
{
return (q->front==q->rear);
}
//进队
bool enQueue(SqQueue *&q,ElemType e)
{
if(q->rear==MaxSize-1)//队满上溢出
return false;
q->rear++;
q->data[q->rear] = e;
return true;
}
//出队
bool deQueue(SqQueue *&q,ElemType &e)
{
if(q->front==q->rear)//队空下溢出
return false;
q->front++;
e=q->data[q->front];
return true;
}
//销毁队列
void DestroyQueue(SqQueue *&q)
{
free(q);
}
//报数
void number(int n)
{
int i;
int count=1; //count用来记第几个元素
SqQueue *q; //环形队列指针q
InitQueue(q); //初始化队列q
for(i=1; i<=n; i++) //构建初始序列
{
enQueue(q,i);
}
while(!QueueEmpty(q)) //队列不空循环
{
deQueue(q,i);
if(count%2==0) //第偶数个元素时，进队
enQueue(q,i);
else
printf("%d\t",i); //第奇数个元素时，出队输出
count++;
}
printf("\n");
DestroyQueue(q);
}3. 编写程序exp3-2.cpp，实现上述问题的求解
#include"SqQueue.h"
int main()
{
int n;
printf("请输入n的个数：");
scanf("%d",&n);
number(n);
return 0;
}4.实验结果截图
