约瑟夫环

一、头文件（队列结构）

/*
Cycle.h使用注意事项：
    MAXSIZE-1为队列长度，可根据自己需求修改。默认MAXSIZE为5
    QElemType为存储数据类型，可根据自己需求修改。默认为int型

    void InitQueue(Queue* Q)                    初始化队列
    int InsertQueue(Queue* Q, QElemType e)      若队列未满，则插入元素e为Q的新的队尾元素
    int DeleteQueue(Queue*	Q, QElemType* e)    出队,删除队头的元素，用e返回其值
    int QueueLength(Queue* Q)                   计算队当前的长度
    QElemType GetQueueTop(Queue* Q)             获取队头元素
*/

#ifndef CYCLE_H
#define CYCLE_H
#define MAXSIZE 9			   //队列长度为MAXSIZE-1

typedef int QElemType;         //QElemType根据实际情况而定，这里是int


//定义队列结构
typedef struct
{
	QElemType data[MAXSIZE];
	int front;					//队头
	int rear;					//队尾
}Queue;

//初始化队列
void InitQueue(Queue* Q)
{
	Q->front = 0;
	Q->rear = 0;
}

//若队列未满，则插入元素e为Q的新的队尾元素
int InsertQueue(Queue* Q, QElemType e)
{
	if ((Q->rear+1)%MAXSIZE == Q->front)              //队满的判断
	{
		printf("队已满!\n");
		return 0;
	}
	Q->data[Q->rear] = e;							  //将元素e赋值给队尾
	Q->rear = (Q->rear+1)%MAXSIZE;					  //将rear指针向后移一位
	return 1;
}

//出队,删除队头的元素，用e返回其值
int DeleteQueue(Queue*	Q, QElemType* e)
{
	if (Q->front == Q->rear)					      //判断队是否为空
	{
		printf("队已空!\n");
		return 0;
	}
	*e = Q->data[Q->front];							  //将队头的元素赋值给e
	Q->front = (Q->front+1)%MAXSIZE;				  //front指针向后移一位
	return 1;
}

//计算队当前的长度
int QueueLength(Queue* Q)
{
	return (Q->rear + MAXSIZE - Q->front) % MAXSIZE;
}

//获取队头元素
QElemType GetQueueTop(Queue* Q)
{
    return Q->data[Q->front];
}



#endif

二、实现源代码

#include <stdio.h>
#include <stdlib.h>
#include <cycle.h>

int main()
{
	Queue* Q = (Queue*)malloc(sizeof(Queue));
	Queue* M = (Queue*)malloc(sizeof(Queue));
	int i, m;                           //数到m的人就站出来，从i开始报数
	int j, index;                //j用于循环遍历计数
	int time=0;
	int num;


	printf("从位置i的人开始报数，数到m的人站出来。");
	printf("\ni:");
	scanf("%d", &i);
	printf("m:");
	scanf("%d", &m);


	InitQueue(Q);   //初始化队列
	InitQueue(M);   //初始化队列M，用于排序后的入队


	//将1到MAXSIZE-1存到队列中
	for(j=0 ; j<MAXSIZE-1 ; j++)
    {
        InsertQueue(Q, j+1);
    }

    index = i-1;
    while(1)
    {
        for(j=0 ; j<m ; j++)
        {
            //如果上一次遍历时时队尾，则将index置为0
            if(index>MAXSIZE-2)
            {
                index = 0;
            }
            //遍历到这个-1时，直接跳过
            if(Q->data[index] == -1)
            {
                index++;
                j--;
                continue;
            }
            num = Q->data[index];
            index++;
            //如果报数到第m个时，将这个元素入队到新的队列M中，并将原队列Q中这个元素改为-1
            if(j == m-1)
            {
                InsertQueue(M, num);
                Q->data[index-1] = -1;
            }
        }
        time++;
        if(time == MAXSIZE-1)
        {
            break;
        }
    }

    for(j=0 ; j<MAXSIZE-1 ; j++)
    {
        printf("%d\t",  M->data[j]);
    }
    printf("\n");
}