约瑟夫环

约瑟夫环
      是一个数学的应用问题：
      已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。

   这个就是约瑟夫环问题的实际场景，有一种是要通过输入n,m,k三个正整数，来求出列的序列。这个问题采用的是典型的循环链表的数据结构，就是将一个链表的尾元素指针指向队首元素。 s->next=head

   解决问题的核心步骤：
       1.建立一个具有n个链结点，无头结点的循环链表
       2.确定第1个报数人的位置
       3.不断地从链表中删除链结点，直到链表为空

void JOSEPHUS(int n,int k,int m) //n为总人数，k为第一个开始报数的人，m为出列者喊到的数
{
    /* s为当前结点  r为辅助结点，指向p的前驱结点  head为头节点*/
          LinkList     head;//头指针
          ListNode   *s,*r;  //工作指针
          head=NULL;    //链表开始为空
          r=NULL;//尾指针初值为空

    /*建立循环链表*/
    for(int i=0,i<n,i++)
    {
        s=(ListNode *)malloc(sizeof(ListNode));//生成新结点
        s>data=i;

        if (head!=NULL)
               head=s;//新结点插入空表
           else
               r->next=s;//将新结点插到*r之后
               r=s;//尾指针指向新表尾

          s->next=head; /*使链表循环起来*/
          s=head; /*使p指向头节点*/

    /*把当前指针移动到第一个报数的人*/
    for(i=0;i<k;i++)
    {
        r=s；//r节点为s的前驱
       s=s->next;
    }

    /*循环地删除队列结点*/
    while(s->next!=s) //空链表
    {
        for(i=0;i<m;i++)
        {
            r=s;
            s=s->next;
        }
        r->next=s->next; //删除s节点
        printf("被删除的元素：%4d ",s->data);
        free(s);
        s=r->next;
    }
    printf("\n输出仅剩的结点：％4d",s->data);
}