约瑟夫环原理运作如下：
- N个人围在一起坐成环状
- 从K编号开始报数
- 数到某个数M的时候，此人出列，下一个人重新报数
- 一直循环，直到所有人出列，约瑟夫环结束
joselooplink.c（编译环境： Ubuntu18.04 ，Vim）
代码语言：javascript复制#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 failedn");
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("%dn", 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 %dn", joseph(5));
return 0;
}
