数据结构：约瑟夫环

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

typedef struct node                             /*头指针型约瑟夫环*/
{
    int item;
    struct node *next;
}node;

node *head = NULL;  /*头空*/
node *tail = NULL;  /*尾空*/

node *mk_node(int item) //分配地址空间，创建节点
{
	node *p = (node *)malloc(sizeof(node));
	if (p == NULL)
	{
		printf("malloc failed\n");
		exit(1);
	}

	p->item = item;
	p->next = NULL;

	return p;
}

void free_node(node *p) //释放节点
{
	free(p);
}

void traverse() //遍历
{
	node *p = head;

	while (p->next != head)
	{
		printf("%d ", p->item);
		p = p->next;
	}
	printf("%d ", p->item);
	printf("\n");
}

void joseph_init(int n)  /*约瑟夫环初始化*/
{
	int i;

	node *p = mk_node(1);
	head = p;
	tail = p;

	for (i = 2; i <= n; i++)
	{
		p = mk_node(i);

		tail->next = p;
		tail = p;
	}

	tail->next = head;
	traverse();
}

int joseph(int n)  /*踢人算法*/
{
	int total = 0;
	node *p ;
	node *pre;
	int surv;
	
	joseph_init(n);
	p = head;
	pre = tail;

	while (p->next != p)
	{
		total++;

		if (total == 3)
		{
			pre->next = p->next;
			p->next = NULL;
			printf("%d\n", p->item);
			free_node(p);
			p = pre->next;
			total = 0;

			continue;
		}

		p = p->next;
		pre = pre->next;
	}
	surv = p->item;
	free_node(p);

	return surv;
}

int main()
{
	printf("the last is %d\n",  joseph(5));

	return 0;
}