joseph.cpp

约瑟夫环,&#61548 任务：编号是1

#include<iostream>
using namespace std;
struct node
{
	int code;
	int id;
	node * next;
}head;//head 为头节点，有头结点的链表比较好控制
int main()
{
	int m,n;
	cout<<"请输入初始值m:"<<endl;
	cin>>m;
	cout<<"请输入人数n:"<<endl;
	cin>>n;
	head.code = -1;
	head.next = NULL;
	cout<<"请输入每个人的密码，并以空格隔开:"<<endl;
	//输入说明和出入初始数据
	node * p = &head ;//建立一个指针p指向头结点
    for(int i = 0; i < n; ++i)
	{
		node * s = new node;
		cin>>s->code ;
		s->id = i+1;
		s->next = NULL;
		p->next = s;
		p = s;		
    }
	//循环出入每个人的密码并且依次连接到链表上
    p->next = head.next ;//将尾指针指向头节点的下一个节点（即第一个人）
    while(p->next != p)//当只剩下一个节点的时候不必循环，直接输出即可
	{
	    for(int i = 0; i< m-1; ++i)
		p=p->next ;
		//循环找出目标节点
		node *q = p->next;
        p->next = q->next ;
		m = q->code ;
		cout<<q->id<<" ";
		delete q;
		//删除目标节点并连接该节点的前后节点
    }
	cout<<p->id<<endl;//输出最后一个人的密码
    system("pause");
	return 0;
}