#include<stdio.h>
#include<stdlib.h>
typedef struct LNode
{
   int number;   //编号
   int code;   //持有密码
   struct LNode *next;   //指向下一个结点的指针
}LNode,*LinkList;
void CreateList(LinkList L,int n);   //创建循环链表
void Joseph(LinkList L,int n);  //约瑟夫环解决方案
void DeleteList(LinkList L,int i,LinkList q);                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            L,int i;LinkList &q);   //删除以L为头第个结点，返回结点
int LengthList(LinkList L);   //求循环链表长度
void main()
{
    LinkList L;
    int n;
    printf("请输入人数:");
    scanf("%d",&n);  //设置人数
    CreateList(L,n);   //创建循环链表
    Joseph(L,n);   //约瑟夫环解决方案
}
void CreateList(LinkList L,int n)
{
    LinkList q;
    int i;
    printf("将这%d个人编号为1-%d号。\n:",n,n);
    printf("请依次输入这%d个人的密码:",n);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        LinkList p=(LinkList)malloc(sizeof(LNode));   //创建新结点用p指向它
        p->number=i;
        scanf("%d",&p->code);   //输入持有密码
        p->next=NULL;
        if(i==1) L=q=p;  //若是第一个结点，直接用头指针指向它。
        else
        {
            q->next=p;   //将p指向的结点加入链表
            q=q->next;   //q始终保持指向最后的结点
        }
    }
    q->next=L;   //q指向最后的结点指针域指向头结点，则成为循环链表
}
void DeleteList(LinkList L,int i,LinkList q)
{
    if(i==1)
    DeleteList(L,i+LengthList(L),q);   //i=1时需要特殊处理
    else
    {
       LinkList p=L;
       int j=0;
       while(j<i-2) {p=p->next;j++; }   //p指向第i-1个结点，即被删除结点的前驱结点
       q=p->next;   //p指向被删除结点，返回信息
       p->next=p->next->next;   //删除第i个结点
       L=p->next;   //修改头指针
       }
}
void Joseph(LinkList L,int n)
{
    int m;
    int i;
    LinkList q;
    printf("请输入第一个报数上限值:");   //设置第一轮报数上限值
    scanf("%d",&m);
    printf("\n出场顺序:\n");
   
    for(i=1;i<n;i++)
    {
       DeleteList(L,m,q);   //删除L开始第m个结点，修改头指针位置，q返回信息
       printf("%d.\t%d号\t他的密码为:%d\n",i,q->number,q->code);   //打印相关信息
       m=q->code;//修改报数上限值为被删除结点的密码值
       free(q);
     }
    printf("%d.\t%d号\t他的密码为:%d\n",n,L->number,L->code);
}
 int LengthList(LinkList L)
{  
    int i;
    LinkList p=L->next;
    while(p!=L)
    {
        i++;
        p=p->next;
    }
    return i;  //返回长度
}