C语言循环链表求解约瑟夫环问题（循环方式）

/**************************************************************************************************
* @brief:	使用链表和循环求解约瑟夫环问题。找出每次出局者的编号。
* @author:	wuchuan <[email protected]>.
* @date:	2013-4-23.
**************************************************************************************************/
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>

using namespace std;

typedef struct YSF_LINK_T
{
	int number;
	struct YSF_LINK_T *next;
}ysf_link_t;

//根据人数n创建单向环形链表，编号从1到n。
ysf_link_t *create_link(int n)
{
	if (n < 2)
		return NULL;

	int i = 0;
	ysf_link_t *head = NULL;
	ysf_link_t *cur = NULL;
	ysf_link_t *ptr = NULL;

	for (i=0; i<n; i++)
	{
		ptr = (ysf_link_t *)malloc(sizeof(ysf_link_t));
		if (ptr)
		{
			ptr->number = i + 1;
			ptr->next = NULL;
			if (NULL == head)
				head = cur = ptr;
			else
			{
				cur->next = ptr;
				cur = cur->next;
			}
		}
		ptr = NULL;
	}
	//尾节点与首节点相连，形成环
	cur->next = head;
	
	return head;
}

//create_link()测试
void print_link(void)
{
	ysf_link_t *pup = NULL;
	ysf_link_t *head = create_link(5);

	cout << head->number << endl;
	for (pup=head->next; pup!=head; pup=pup->next)
		cout << pup->number << endl;
	return;
}

//compile: vs2010
//求解约瑟夫环过程
int main(int argc, char *argv[])
{
	//print_link();

	int i = 0;
	int n, k, m;

	cout << "input n(n>=3):";
	cin >> n;
	cout << "input k(1<=k<=n):";
	cin >> k;
	cout << "input m(m>=2):";
	cin >> m;
	cout << "you input: n=" << n << ", k=" << k << ", m=" << m << endl;
	if (n<3 || k<1 || k>n || m<2)
		exit(1);

	ysf_link_t *cur = NULL;
	ysf_link_t *prev = NULL;
	ysf_link_t *head = create_link(n);

	cur = head;
	while ((++i < k) && cur)
		cur = cur->next;
	
	i = 0;
	while (cur)
	{
		if (++i == m)
		{
			//输出每次出局者的编号
			cout << cur->number << ", ";
			//如果已经是最后一个节点，释放后跳出循环
			if (cur == cur->next)
			{
				free(cur);
				cur = NULL;
				break;
			}
			//释放出局者节点，重新开始计数
			prev->next = cur->next;
			free(cur);
			cur = prev->next;
			i = 0;
			continue;
		}
		prev = cur;
		cur = cur->next;
	}
	cout << endl;
	prev = cur = NULL;

	return 0;
}