约瑟夫环问题（C语言，单循环链表实现）_综合

约瑟夫环问题：

n 个人的编号是 1~n，如果他们依编号按顺时针排成一个圆圈，从编号是1的人开始顺时针报数。

（报数是从1报起）当报到 k 的时候，这个人就退出游戏圈。下一个人重新从1开始报数。
求最后剩下的人的编号。这就是著名的约瑟夫环问题。

解决约瑟夫环问题首先要考虑如何表示n个人围成一圈。n个人围成一圈意味着1号后面是2号，2号后面是3号,..............,n-1后面是n号。这正好用一个单循环链表表示，而且该单循环链表不需要表头。

当输入n=5,k=3的时候

删除2 0 4 1

最后剩下的是： 3

解决约瑟夫环的问题分成两个阶段：首先根据n创建一个单循环链表，然后模拟报数过程，逐个删除结点，直到只剩下一个结点为止。创建一个循环链表和创建一个单链表基本类似，只有两个小区别：

一是约瑟夫环不需要头节点，有了头节点反而会增加报数阶段的复杂性；

二是最后一个结点的next指针不在为NULL,而是指向第一个结点。

报数阶段本质上是结点的删除,报到3的结点从环上删除。报数的过程就是指针移动的过程，让指针停留在被删除结点的前一结点。

#include <stdio.h>
#include <stdlib.h>
struct node{int data;struct node *next;
};
int main(){struct node *head,*p,*q;            //head为链表头int n,i,k;//输入nprintf("input n and k:");scanf("%d %d",&n,&k);//建立链表head = p =(struct node *)malloc(sizeof(struct node));           //创建第一个结点， head 指向表头结点,p指向表尾结点p->data=1;for( i=2;i<=n;i++){                                             //构建单循环链表q = (struct node *)malloc(sizeof(struct node));            //q为当前正在创建的的结点q ->data = i;p ->next = q;  p=q;                                        //将q链入表尾}p->next = head;                                                 //头尾相连//删除过程q=head;                                                       //head报数为1while(q->next != q){                                          //表中元素多于一个if(k%2 !=0){for ( i= 0; i < k/2; i++) {p = q->next;q = p->next;}//删除qp->next = q->next;                                 //绕过结点qprintf("%d\t",q->data);                         //显示被删除的编free(q) ;                                        //回收被删除的空间q = p->next;                                     //让q指向报1的结点} else if(k%2 ==0){for(i=0;i<k/2-1;i++){p = q->next;q = p->next;}p=q->next;//删除pq->next=p->next;                                      //绕过结点qprintf("%d\t",p->data);                           //显示被删除的编free(p);                                           //回收被删除的空间q=q->next;                                        //让q指向报1的结点}}//打印结果printf("最后剩下:%d\n",q->data);return 0;
}