#include<iostream.h>
struct Node
{
int data;
Node *pNext;
};
void main()
{
//1定义环的相关参数
//a.环的节点数
//b.开始点数的位置
//c.出环间距。
int n,k,m,i;
Node *p,*q,*head; //p为一个中间变量，用来临时处理
cout<<"输入n的值:";
cin>>n;
cout<<"输入起始报数人号码k的值:";
cin>>k;
cout<<"输入 数到m出列的m的值:";
cin>>m;
//2生成约瑟夫环
//a.头节点
//b.中间变量
//c.每一个环节点操作
//d.将最后一个换节点的下一个指针的地址指向头节点
head=(Node*)new Node; //确定头结点
p=head; //为临时变量赋初值
for(i=1;i<=n-1;i++)
{
p->data=i;
p->pNext=(Node*)new Node; //为下一个新建内存
p=p->pNext; //将下一个节点的地址赋给临时变量，准备下一步的处理
}
p->data=n; //最后一个单独处理
p->pNext=head; //指向头，形成循环链表
p=head;
while(p->data!=(p->pNext)->data)//p->data==(p->pNext)->data表示只剩下一个结点的
{
//3.找到开始数数的位置
p = head; //将p指向Head，表示从N开始
while(p->data !=k) //寻找编号为k的结点,最后两步 k=(q->pNext)->data和 p->pNext=q->pNext跟这里呼应，以免每次都进入这个循环
p=p->pNext;
//4.如果步长为1则，直接输出
//否则：（因为这一步首先报到m-1，所以上一个步骤就有必要了（步长为1的情况））
//a.找到出列环的前一个节点p
//b.找到出列环的节点n
//c.报数
//d.将出列环的上一个节点p的next指针指向n的next。
//e.删除该出列环节点
if(m==1)
{
for(i=1;i<=n;i++)
{
cout<<p->data<<'\t' ;
p=p->pNext ;
}
cout<<'\n';
return;
}
else
{
for(i=1;i<m-1;i++) //开始报数
{
p=p->pNext;
} //找到报m-1的结点
q=p->pNext; //q为报m的结点
cout<<q->data<<"\t"; //输出报m的结点的值
k=(q->pNext)->data; //k为下一个报数的起点
p->pNext=q->pNext; //删除报m的结点
}
}
cout<<p->data<<'\n'; //输出最后一个结点的值
}