// 約瑟夫環(huán)1.30修正版.cpp : 定義控制臺(tái)應(yīng)用程序的入口點(diǎn)。
//測試數(shù)據(jù)：n=5 key=5,4,3,2,1 m=1  輸出 1 2 3 4 5 all out！
//第二組：n=7 key= 3,1,7,2,4,8,4  m=6 輸出 6 1 4 7 2 3 5 all out！


//#include "stdafx.h"

#include <iostream>
#include <cstdlib>
using namespace std;

//約瑟夫環(huán)的實(shí)現(xiàn)：一群人圍成一圈，這群人共有 n個(gè)人，
//每個(gè)人身上都一個(gè)key，依次給這圈人編號：
//1，2，n 一開始報(bào)數(shù)的上限值為m從第一個(gè)人（編號：1）
//自一開始報(bào)數(shù)報(bào)到m時(shí)停止報(bào)數(shù)，報(bào)到m的人出列，
//將他的密碼做為新的m值，
//從他的順時(shí)針方向開始的下個(gè)人開始從新從一報(bào)數(shù)，
//如此下去，直至所有的人出列為止 

typedef struct Node
{
    int key;//每個(gè)人身上帶的key 
    int NUM;//每個(gè)人的編號 
    struct Node *next;
	//Node():next(0){};
}Node;
//=========================
int n;//總的人數(shù)。
//=========================
Node* InitList(int x)//初始化第一個(gè)節(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)有實(shí)際的意義 
{
    Node *L=NULL;//循環(huán)鏈表指針 
    L = new Node;   
    L->NUM=1;
    L->key=x;
	L->next=L;
	//L->next=L;
	return L;
}
//===========================================
void DelNode(Node *p_front)//p_front指向的是p的前一個(gè)節(jié)點(diǎn)，刪除的是p  
{
    Node  *tmp=p_front->next;
    p_front->next = tmp->next;
    delete (tmp);
} 
//============================================
Node* CreateList(void)//創(chuàng)建循環(huán)鏈表 
{ 
	Node *L=NULL;//循環(huán)鏈表指針 
    cout<<"Players n=";
    cin>>n;
	cout<<endl;
    
    int key_tmp;//密碼
    cout<<"NUM=1  key=";
    cin>>key_tmp;
    //Node  *L; 
    L=InitList(key_tmp);//輸入密碼
    int i;
    Node *s,*p=L;
    for( i=2;i<=n;i++)
    {
        s=new Node;//構(gòu)建鏈表，存儲(chǔ)數(shù)據(jù)
        
        cout<<"NUM="<<i<<"  key="; 
        cin>>key_tmp;
           
        s->key=key_tmp;
        s->next=L;//構(gòu)成循環(huán)鏈表的next指針賦值 
        p->next=s;
        s->NUM=i;
        p=s;//指針p往前移動(dòng) 
    }
	return L;
}
//=============================================
void PlayGame(Node* L)//開始！報(bào)數(shù) 
{
    Node   *p=L;
    Node  *p_front=L;

	for(int j=0;j<n-1;++j)
		p_front=p_front->next;//循環(huán)到頭結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)，即最后一個(gè)結(jié)點(diǎn)。

    int m;
    cout<<"start!"<<endl;
    cout<<"m=";
    cin>>m;
    
    int i;
    int count = n;

	while(count--)
	{
		for(i=1;i<m;i++)
			p_front=p_front->next;//移動(dòng)指針

		p=p_front->next;//
		m=p->key;
		

		cout<<p->NUM<<" ";

		DelNode(p_front);

		p=p_front->next;
		
        if(count==1)
        {       
             cout<<p->NUM;                            
             cout<<" all out !"<<endl;
                 //system("PAUSE");    
             return ;
        }     		
		
    }p_front=p;
	
}
//==================================================
int main()//運(yùn)行！ 
{
    Node* L=CreateList();
    PlayGame(L);
    system("pause");    
    return 0;
}