// 约瑟夫问题.cpp : Defines the entry point for the console application.
/*问题描述：
    设有N个人围坐一圈，现从某个人开始数，数到M的人出列，
    接着从出列的下一个人开始重新报数，数到M的人又出列，
    如此下去，直到所有人都出列为止。求出列次序及最后的
    出列者。
*/
#include "stdafx.h"
#include "iostream.h"

struct MYLINK
{
    int data;
    MYLINK *next;
}*head,*s,*end;  //头指针，搜索指针，尾指针

void CreatLink(int n);  //建立链表
MYLINK *Show();  //显示链表
void  Search(int n,int d,int m);  //出列算法

int main(int argc, char* argv[])
{
    cout<<"===========约瑟夫问题============="<<endl;
    cout<<"输入人数："<<endl;
    int n;
    cin>>n;
    CreatLink(n);
    cout<<"链表建成!"<<endl;
    Show();
    cout<<"输入出列数："<<endl;
    int m;
    cin>>m;
    cout<<"输入从第几个人开始数？"<<endl;
    int d;
    cin>>d;
    while(d>n)
    {
        cout<<"输入的数大于总人数，请重新输入!"<<endl;
        cin>>d;
    }
    cout<<"人数为 "<<n<<" 从第 "<<d<<" 个人开始,报到 "<<m<<" 者将出列"<<endl;

    Search(n,d,m);

    return 0;
}

void CreatLink(int n)
{    
    head=end=new MYLINK;  //产生表头监督元节点
    head->data =1;
    MYLINK *p;  //新节点指针

    for(int i=2;i<=n;i++)
    {
        p=new MYLINK;  
        p->data =i;  //新节点值
        end->next =p;  //插入到表尾
        end=end->next;  //移动表尾指针
    }
    end->next =head;  //尾指针指向头节点
}

MYLINK *Show()
{
    s=head;  //从表头开始

    do
    {
        cout<<s->data<<endl;  //输出指针所指的值
        s=s->next ;  //移动搜索指针
    }while(s!=head);

    return head;  //返回表头指针
}

void  Search(int n,int d,int m)
{
    MYLINK *q;  //记忆指针
    q=s=head;   //指针从表头开始
    int add=1;  //从1开始报数
  
    while(true)
    {
        if(s->data ==d)
        {
            q=s;  //指向开始数的人
            break;
        }
        else  //移动指针
        {
            s=s->next ;
            q=q->next ;
        }
    }
    while(n !=0)
    {
        add++;  //报数
        s=s->next ;  //这样s的前驱为q
        if(add%m==0)
        {
            q->next =s->next ;
            cout<<s->data <<endl;
            n--;  //人数减1
            if(n==0){cout<<"最后出列的人是 "<<s->data <<" 号。"<<endl;}
            delete s;
            s=q;  //s指针回到q指的节点(删除节点的原前驱)
        }
        else
        {
          q=q->next ;
        }
    }

}