Josephus 约瑟夫问题

去年学数据结构时写的,不考虑时间/空间复杂度

/************************************************************************/
/* 已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。       
/* 从编号为k的人开始报数，数到m的那个人出列；
/* 他的下一个人又从1开始报数，数到m的那个人又出列；
/* 依此规律重复下去，直到圆桌周围的人全部出列。
/* 
/*           n = 9(人数)
/*           k = 1(第一次开始的编号)
/*           m = 5(出列的报数)
/* 出局人的顺序为:
/*           5, 1, 7, 4, 3, 6, 9, 2, 8
/*
/* 作    者: tjm
/* 运用知识: 数据结构(不带头结点的单向循环链式线性表)
/* 编写时间: 2012年8月8日
/************************************************************************/

typedef struct Node
{
	int ID;		// 编号
	int Num;	// 报数
	Node * pNext;//
} * PLINK, NODE;

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

PLINK CreateList()	// 无头结点
{
	int n;	//参与人数
	printf("总人数(n): ");
	scanf("%d", &n);
	if (n <= 0)	//如果参与人数小于等于 0, 直接返回空
	{
		return NULL;
	}

	PLINK pTail = (PLINK)malloc(sizeof(NODE));	//指向尾节点
	PLINK p = pTail;	//指向首节点
	p->ID = 1;

	for (int i = 2; i <= n; i++)	// i 的作用: a.计数 b.给参与者编号
	{
		PLINK pNew = (PLINK)malloc(sizeof(NODE));
		pNew->ID = i;
		pTail->pNext = pNew;
		pTail = pNew;
	}
	pTail->pNext = p;	// 尾节点 的 指针域 指向 首节点
	
	return pTail; // 返回指向尾节点的指针便于操作(尾节点 充当 头结点)
}

void PlayGame(PLINK pTail)
{
	if (!pTail)
	{
		printf("\n人数不足!\n");
		return;
	}

	int k;	//开始编号
	int m;	//出列的数字
	PLINK p = pTail; //游标
	PLINK q;	//指向要离开的

	printf("\n从哪个编号开始报数(k), k∈[1,n]: ");
	scanf("%d", &k);
	printf("报什么数的人离开(m), m∈[1,+∞]: ");
	scanf("%d", &m);

	while ( k<1 || m<1 )
	{
		if(k<1)
		{
			printf("\nk不能小于1,请重新输入:\n\n");
			scanf("%d", &k);
		}
		if(m<1)
		{
			printf("\nm不能小于1,请重新输入:\n\n");
			scanf("%d", &m);
		}
	}

	while (p->pNext->ID != k)	//寻找 k (开始编号)
	{
		p = p->pNext;
	}

	for (int i = 1; true; i++)	// 游戏的核心过程
	{
		if (p == p->pNext)                                      /****************************************/
		{                                                       /* 此判断本来在 for语句 最后面,         */
			printf("\n游戏结束!编号<%d>是胜利者!\n\n", p->ID);  /* 但是如果只有1人玩游戏,则一开始就死了,*/
			free(p); //释放离开者占用的内存空间                 /* 所以要在游戏开始之前应该先结束游戏,  */
			return;                                             /* 世界是美好的, 请珍惜生命!!!          */
		}                                                       /****************************************/

		p->pNext->Num = i;
		if (p->pNext->Num == m) // 选出离开者
		{
			q = p->pNext;
			printf("编号 %2d 自杀了!\n", q->ID);
			p->pNext = q->pNext;
			free(q);	//释放离开者占用的内存空间
			i = 1;		//下一个从1开始报数
			p->pNext->Num = i;	// 1
		}
		p = p->pNext; //在剩下最后1个人的时候, 永远指向自己
		if (p->pNext->Num == m) //在剩下1个人 或 m=1时, 此判断非常重要, for语句的i++会把i变成2,3,4,5... 进入死循环, 永远找不到报数是m的人
		{
			i = 0;
		}
	}

	return;
}

int main(void)
{
	PlayGame(CreateList());

	return 0;
}