#include <iostream>
using namespace std;
class Node{
private:
public:
int password; //人的密码
int number; //人的密码
Node* next; //结点后继
Node(){
}
//结点的构造函数
Node( int elem,int x ){
password = elem;
number = x;
}
virtual ~Node(){
}
};
class LinkList{
private:
public:
Node* rear; //链表的尾指针
LinkList(){ //链表的构造函数
rear = new Node();
rear ->next = rear; //尾结点的后继是尾结点，表示链表为空
}
void insert_elem( int elem,int x ){ //在链表中插入一个password = elem，number = x的结点
Node* p = new Node( elem, x ); //为插入的结点分配空间
p ->next = rear ->next; //插入的结点指向“头结点”
rear ->next = p; //尾指针指向新插入的结点
rear = p; //维护尾指针的位置
}
void delete_elem( Node* &p ){ //删除p结点
Node* q = rear ->next; //定义一个结点指针变量，并赋初值为“头结点”
while( q ->next != p ){ //找到p结点的前驱
q = q ->next;
}
q ->next = p ->next; //p的前驱指向p的后继
delete p; //释放p结点的内存空间
}
virtual ~LinkList(){
delete rear; //
}
};
void Josephus( LinkList& L ){ //约瑟夫环的实现
int m; //limit
cout << "Please input the limit:";
cin >> m;
L.rear ->password = m;
cout << "Please input the number of people:";
int n; //number of people
cin >> n;
cout <<"Please input password: ";
int password;
for( int i = 1; i <= n; ++ i ){ //初始化链表
cin >> password;
L.insert_elem( password, i ); //
}
Node* q = L.rear ->next;
int nn = q ->password; //取得初始密码
while( L.rear ->next != L.rear ->next ->next ){ //头结点的后继不等于头结点，即链表不为空
Node* p = q;
int count = 0;
while( count != nn ){ //未数到密码的个数
q = p; //保留p的前驱
p = p ->next;
if( p != L.rear ->next ){ //如果当前结点为“头结点”，则跳过
++ count;
}
}
cout << " " << p ->number; //输出人的编号
if( p == L.rear ){ //此时p要删除，如果p为尾结点，则让尾结点前移
L.rear = q;
}
nn = p ->password; //把此人的密码作为新的密码
L.delete_elem( p ); //删除已输出的结点
}
}
int main(){
LinkList L;
Josephus( L );
system("pause");
return 0;
}
