/*---------约瑟夫环---------*/  
/*---------问题描述---------*/  
/*编号为1，2，…，n的n个人围坐一圈，每人持一个密码（正整数）。 
一开始任选一个正整数作为报数上限值m， 
从第一个人开始自1开始顺序报数，报到m时停止。 
报m的人出列，将他的密码作为新的m值，从他的下一个人开始重新从1报数， 
如此下去，直至所有人全部出列为止。试设计一个程序求出列顺序。*/  
  
/*---------问题分析---------*/  
/*n个人围坐一圈，且不断有人出列，即频繁删除，应用单循环链表。 
有因为报数的过程是计数的过程，每个数据结点计1，因此不带头结点合适。 
又因为第一次报数的上限是任选的正整数，有可能报到第一个人时出列，为删除第一个结点， 
须知其前驱结点的位置，即尾结点的位置，因此应设尾指针，不设头指针*/  
  
#include<stdio.h>  
#include<stdlib.h>  
  
typedef struct lnode{  
    int num;    //序号  
    int key;    //密码  
    struct lnode *next;  
}LNode,*LinkList;  
  
void CreatList(LinkList &L)  
{//建立含有n个结点的不带头结点的单循环链表，L为尾指针  
    int n;  
    int i;  
    LinkList s,p;  
    printf("请输入人数：");  
    scanf("%d",&n);  
    while(n<=0)  
    {  
        printf("人数太少！请重新输入：");  
        scanf("%d",&n);  
    }  
    L=(LinkList)malloc(sizeof(LNode));  //建立第一个结点，输入第一个人的信息  
    L->num=1;  
    printf("请输入第1个人的密码：");  
    scanf("%d",&L->key);  
    p=L;//p指向目前链表的尾结点，之后新建结点均插入表尾  
    for(i=2;i<=n;i++)  
    {  
        s=(LinkList)malloc(sizeof(LNode));  
        s->num=i;  
        printf("请输入第%d个人的密码：",i);  
        scanf("%d",&s->key);  
        p->next=s;   //将新结点*s插入链表尾部，p指向新结点  
        p=s;  
    }  
    p->next=L;   //尾结点的next指向表首结点，构成循环链表  
    L=p;        //L指向尾结点，即链表为设尾指针的链表  
}  
  
void Joseph(LinkList &L)  
{  
      
    int key,i;  
    LinkList p,q;  
    printf("请输入正整数:");  
    scanf("%d",&key);  
    p=L;  
    while(p->next!=p)  
    {  
        for(i=1;i<key;i++)  
        {  
            p=p->next;  
        }  
        q=p->next;  
        printf("%d ",p->num);  
        p->next=q->next;  
        key=q->key;  
        free(q);   
    }  
    printf("%d ",p->num);  
}  
  
int main()  
{  
    LinkList L;  
    printf("-----------------------------约瑟夫环-----------------------------\n");  
      
    CreatList(L);  
    Joseph(L);  
}