约瑟夫环问题（C语言数组和循环链表）

本文将用两种方式（数组和循环链表）求解约瑟夫环问题，为了更好理解，本文将从洛谷的P1996 约瑟夫问题出发。

题目描述

n个人围成一圈，从第一个人开始报数,数到 m的人出列，再由下一个人重新从1开始报数，数到 m的人再出圈，依次类推，直到所有的人都出圈，请输出依次出圈人的编号。

输入格式

输入两个整数 n,m。

输出格式

输出一行 n个整数，按顺序输出每个出圈人的编号。

输入输出样例

输入

10 3

输出

3 6 9 2 7 1 8 5 10 4

说明/提示

1≤m,n≤100

方法一（数组）：

解题思路：创建一个大小为n的数组用来表示n个人，同时用给数组元素赋值0或1表示该人的生死状态（0为生，1为死），同时设置一个flag用来表示当前淘汰的人数，当淘汰人数为n-1个人就跳出循环。

代码实现：

#include <stdio.h>
int main() {
	int n, q, i = 0, count = 1, flag = 0;
	printf("人数：");
	scanf("%d", &n);//输入人数
	getchar();
	printf("报到哪个数被杀死：");
	scanf("%d", &q);//输入报到哪个数死
	int a[n];
	for (i = 0; i < n; i++) {//给每个人设置“生”的状态
		a[i] = 0;
	}
	i = 0;
	printf("杀死顺序(下标)：");
	while (1) {
		if (flag == n - 1) break;//当只剩下一个人时，跳出循环
		if (a[i] == 1) i++;//如果该人为死亡的状态，则跳过该人
		else {
			if (count == q) {//满足被杀死的条件
				a[i] = 1;//设置死亡状态
				flag++;//死亡人数加一
				printf("%d ", i);//输出这一次死亡的人的编号
				count = 1;//重置报数
				i++;//移动到下一个人开始
			} else {//不满足被杀死的状态
				count++;//继续报数
				i++;
			}
		}
		if (i == n) i = 0;//由于数组下标从0开始，所以当i=n时，应该是移动到第一个人了
	}
	printf("\n存活（下标）：");
	for (i = 0;; i++) {
		if (a[i] != 1) {//输出最后存活的人
			printf("%d", i);
			break;
		}
	}
	return 0;
}

该方法一般为约瑟夫环问题的常见方法，但时间复杂度较高，而下面的方法可以帮助我们更好的理解循环链表的结构。

方法二（循环链表）：

解题思路：

创建一个循环链表，这样可以看成一群人围成一圈的状态，并在头结点开始给人从1开始赋值表示编号，另外创建一个大小为n的数组用来储存死亡顺序（编号），每当有人死亡时，就把该人的编号储存到数组中，同时把该人从链表中删去。还需设计一个flag来表示死亡人数，当死亡人数为n-1人时就跳出循环。

代码实现：

创建循环链表函数Creat:

LINK* Creat(int n) {//该函数用来创建一个循环链表并返回该链表的尾结点
	LINK *head = NULL,*p = NULL, *pr = NULL;//head用来表示头节点，p用来申请内存空间，pr用来表示当前链表的尾结点
	int i;
	for(i = 1;i <= n;i++)//从1开始创建n个链表结点并依次赋值为i
	{
		p = (LINK*)malloc(sizeof(LINK));//申请动态内存
		if(p == NULL)
		{
			printf("ERROR");
			return NULL;
		}
		p->id = i;
		if(head == NULL)//如果头节点为空指针，则把p赋给head
		{
			head = p;
		} else {//否则就用尾插法创建链表
			pr->next = p;
		}
		pr = p;//将pr赋值为指向当前链表最后一个结点
	}
	pr->next = head;//将最后一个节点的next指向head以构成循环链表
	return pr;//返回尾结点
}

用于确定出圈顺序的函数YueSeFu：

void YueSeFu(LINK* tail, int n, int m, int* a) {
	int count = 0,  flag = 0;//设置报数值和死亡人数值
	LINK* p = tail->next, *q = tail;//定义p为头指针，q为p前一个结点的指针
	while (flag < n - 1) {//死亡人数没有达到n-1
		count++;//报数
		if (count == m) {//满足出圈条件
            *a = p->id;//记录当前出圈者的编号
            a++;//让数组移向下一个值
			q->next = p->next;//让p的上一个结点的指针指向p的下一个结点
			free(p);//释放当前结点
			p = q->next;//p移动到下一个人
			count = 0;//重新开始报数
			flag++;//死亡人数加一
		} else {//不满足就移向下一个人
			q = p;
			p = p->next;
		}
	}
	*a = p->id;//记录最后一个人的编号
	free(p);
}

完整代码：

#include <stdio.h>
#include <stdlib.h>
typedef struct link {
	int id;
	struct link* next;
} LINK;

LINK* Creat(int n);
void YueSeFu(LINK* head, int n, int m, int* a);
void DisplyLINK (LINK *head);

int main(void) {
	int n, m;//n为总人数，m为出圈时报的数
	scanf("%d%d", &n, &m);
	int a[n];
	LINK* tail = NULL;//定义尾指针
	tail = Creat(n);//创建一个循环链表并得到尾指针
	YueSeFu(tail, n, m, a);
	for (int i = 0; i < n; i++) {//打印出圈顺序（编号）
		printf("%d ", a[i]);
	}
}

LINK* Creat(int n) {
	LINK *head = NULL,*p = NULL, *pr = NULL;
	int i;
	for(i = 1;i <= n;i++)
	{
		p = (LINK*)malloc(sizeof(LINK));
		if(p == NULL)
		{
			printf("动态内存分配失败");
			return NULL;
		}
		p->id = i;
		if(head == NULL)
		{
			head = p;
		}
		else
		{
			pr->next = p;
		}
		pr = p;
	}
	p->next = head;
	return pr;
}

void YueSeFu(LINK* tail, int n, int m, int* a) {
	int count = 0, sum = 0;
	LINK* p = tail->next, *q = tail;
	while (sum < n - 1) {
		count++;
		if (count == m) {
			q->next = p->next;
			*a = p->id;
			free(p);
			p = q->next;
			count = 0;
			sum++;
			a++;
		} else {
			q=p;
			p=p->next;
		}
	}
	*a = p->id;
	free(p);
}