yuesefu_ring.txt

约瑟夫环实现

// 约瑟夫环1.30修正版.cpp : 定义控制台应用程序的入口点。
//测试数据：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;

//约瑟夫环的实现：一群人围成一圈，这群人共有 n个人，
//每个人身上都一个key，依次给这圈人编号：
//1，2，n 一开始报数的上限值为m从第一个人（编号：1）
//自一开始报数报到m时停止报数，报到m的人出列，
//将他的密码做为新的m值，
//从他的顺时针方向开始的下个人开始从新从一报数，
//如此下去，直至所有的人出列为止 

typedef struct Node
{
    int key;//每个人身上带的key 
    int NUM;//每个人的编号 
    struct Node *next;
	//Node():next(0){};
}Node;
//=========================
int n;//总的人数。
//=========================
Node* InitList(int x)//初始化第一个节点，这个节点有实际的意义 
{
    Node *L=NULL;//循环链表指针 
    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的前一个节点，删除的是p  
{
    Node  *tmp=p_front->next;
    p_front->next = tmp->next;
    delete (tmp);
} 
//============================================
Node* CreateList(void)//创建循环链表 
{ 
	Node *L=NULL;//循环链表指针 
    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;//构建链表，存储数据
        
        cout<<"NUM="<<i<<"  key="; 
        cin>>key_tmp;
           
        s->key=key_tmp;
        s->next=L;//构成循环链表的next指针赋值 
        p->next=s;
        s->NUM=i;
        p=s;//指针p往前移动 
    }
	return L;
}
//=============================================
void PlayGame(Node* L)//开始！报数 
{
    Node   *p=L;
    Node  *p_front=L;

	for(int j=0;j<n-1;++j)
		p_front=p_front->next;//循环到头结点的前一个结点，即最后一个结点。

    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;//移动指针

		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()//运行！ 
{
    Node* L=CreateList();
    PlayGame(L);
    system("pause");    
    return 0;
}