/*
已知N个人围坐在一张圆桌周围，从编号为k的人开始报数，数到m的那个人出列，他的下
一个人又从1开始报数，数到m的那个人又出列，以此规则重复下去，直到圆桌周围的全
部出列.
基本思想
（1），建立一个具有n个链结点且不带头结点的循环链表
（2），确定第一个报数点的位置
（3），不断地从链表中删除一个链结点，直到链表中还有一个链结点止
*/
#include <stdio.h>
#include <malloc.h>
struct list
{
int data;
struct list *link;
};
void josephus(int n, int m, int k)
{
struct list *p, *r, *list = NULL;
int i;
//list 为第一个结点
for (i = 1; i <= n; i++)
{
p = (struct list *)malloc(sizeof(struct list));
p->data = i;
if (list == NULL)
list = p;
else
r->link = p;
r = p;
}
p->link = list;//建立一个循环链表 指向第一个结点
p = list;//p为首节点
for (i = 1; i < k; i++)
{
r = p;
p = p->link;
}//此时p指向第一个出发结点（即第k处）
while (p->link != p)//循环结束条件为只剩下最后一个节点
{
for (i = 1; i < m; i++)
{
r = p;
p = p->link;
}//p指向第m个结点，r指向第m-1个结点
r->link = p->link;//删除第M个结点
printf("%4i", p->data);
free(p);
p = r->link;
}
printf("/n最后被删除结点是%4i/n", p->data);
}
int main(void)
{
josephus(8, 4, 9);
return 0;
}