（C语言）数据结构-线性表之队列实现约瑟夫环_c语言利用队列实现约瑟夫环问题

题目描述：

约瑟夫环是有n个人围坐在圆桌周围，现在从某个位置i上的人开始报数，数到m的人就站出来，离开。下一个人，就是原来的第m+1个位置上的人，又从1开始报数，再次数到m的人站出来。依次重复下去，直到全部的人都站出来。按出列的先后又可以得到一个新的序列。例如，当n=8,m=4,i=1时，得到的新序列为：4、8、5、2、1、3、7、6。请编写程序用循环队列作为其储存结构模拟整个过程，并依次输出出列的各人的编号。

样例代码:

#include<stdio.h>
#include<stdlib.h>
#define FALSE 0
#define TRUE 1
typedef int QueueElementType;

//定义一个动态循环队列 
typedef struct{
	QueueElementType *element;	//元素空间 
	int front;	//头指针 
	int rear;	//尾指针 
}SeqQueue;

//初始化一个循环队列
void InitQueue(SeqQueue *Q){
	Q->front = Q->rear = 0;
} 

//循环队列入队操作,将元素x入队 
int EnterQueue(SeqQueue* Q, QueueElementType x){
	//尾指针+1追上头指针，标志队列已经满了 
	if((Q->rear+1) % MAXSIZE == Q->front){
		return FALSE;
	}
	//将元素x插入队尾
	Q->element[Q->rear] = x;
	//重新设置队尾指针
	Q->rear = (Q->rear + 1) % MAXSIZE;
	return TRUE;
} 

//循环队列出队操作,删除队列的队头元素，用x返回其值 
int DeleteQueue(SeqQueue* Q, QueueElementType *x){
	//队列不能为空 
	if(Q->front == Q->rear) return FALSE;
	//获取队头元素
	*x = Q->element[Q->front];
	//更改队头指针的指向
	Q->front = (Q->front + 1) % MAXSIZE;
	return TRUE; 
}

//打印队列内的元素 
int PrintQueue(SeqQueue *Q){
	//队列不能为空 
	if(Q->front == Q->rear) return FALSE;
	
	int i = 0;
	int front = Q->front;
	while(front < Q->rear){
		printf("%d ",Q->element[front]);
		front++;
	}
}
//计算约瑟夫环的结果 
void joseph(SeqQueue* Q,int n, int m, int i){
	int x,j,k;
	//通过循环生成一个从1到n的队列 
	for(j = 1; j <= n; j++){
		EnterQueue(Q,j);
	} 
	//通过删除和插入位移指针，让开始位置出现在第一个 
	for(k = 1; k < i; k++){
		DeleteQueue(Q,&x);
		EnterQueue(Q,x);
	} 
	//控制要输出的数据个数 (人数)
	for(j = 1; j <= n; j++) {
		//循环删除和插入用于移动指针指向
		for(k = 1; k < m; k++){
			DeleteQueue(Q,&x);
			EnterQueue(Q,x);
		}
		//当到m个时，取出其值并输出 
		DeleteQueue(Q,&x);
		printf("%d ",x);
	} 
}

int main(){
	int n;	//总人数 
	int m;	//数到第m个人 
	int i;	//开始位置 
	printf("请输入n m i对应的值：");
	scanf("%d%d%d",&n,&m,&i); 
	SeqQueue *Q;
	Q = (SeqQueue*)malloc(sizeof(SeqQueue));
	//开辟队列Q所存储的元素空间 
	Q->element = (QueueElementType*)malloc(sizeof(QueueElementType) * n);
	InitQueue(Q);
	joseph(Q,n,m,i);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

样例输出：