学步园

输入n个数，围城一圈，输入数字m，从第一个数开始数，数到第m个数删除这个数，然后继续数，数到下一个第m个数时，删除该数，直到剩下最后一个数。输出最后一个数。

利用双向循环链表实现：

LinkNode.h

#include<iostream>
using namespace std;
template<typename Type>class LinkNode
{
public:
	Type m_data;
	LinkNode<Type>*m_next;
	LinkNode<Type>*m_pre;
public:
	LinkNode(Type item):m_data(item)
	{
		m_next=this;
		m_pre=this;
	}
	Type GetData()
	{
		return this->m_data;
	}
};

DoubleLink.h

#include<iostream>
#include"LinkNode.h"
using namespace std;
#define Defaultsize 100;
template<typename Type>class DoubleLink
{
private:
	LinkNode<Type>*head;
	int m_cursize;
	int m_maxsize;
public:
	DoubleLink(Type item)
	{
		m_maxsize=Defaultsize;
		m_cursize=1;
		head=new LinkNode<Type>(item);
	}
	~DoubleLink()
	{
		while(head->m_next!=NULL&&head->m_next!=head)
		{
			LinkNode<Type>*temp;
			temp=head->m_next;
			head->m_next=temp->m_next;
			delete temp;
		}
		delete head;
	}
	int GetSize()
	{
		return this->m_cursize;
	}
	bool Insert(Type item);
	bool Delete(Type item);
	int GetData(LinkNode<Type> *Node)
	{
		return Node->m_data;
	}
	Type Jsf(int m);
	void Print()
	{
		if(this->m_cursize==0)
		{
			cout<<"the link is empty!"<<endl;
			return ;
		}
		LinkNode<Type>*temp=this->head->m_next;
		cout<<"head ("<<head->m_data<<")-->";
		while(temp!=head)
		{
			cout<<temp->m_data<<"-->";
			temp=temp->m_next;
		}
		cout<<"head"<<endl;
	}
};
template<typename Type>bool DoubleLink<typename Type>::Insert(Type item)
{
	if(this->m_cursize==this->m_maxsize)
	{
		cout<<"the Doublelink is full!"<<endl;
		return 0;
	}
	LinkNode<Type>*temp=new LinkNode<Type>(item);
	LinkNode<Type>*p=this->head;
	while(p->m_next!=head)
	{
		p=p->m_next;
	}
	temp->m_next=p->m_next;
	p->m_next->m_pre=temp;
	p->m_next=temp;
	temp->m_pre=p;
	this->m_cursize++;
	return 1;
}
template<typename Type>bool DoubleLink<typename Type>::Delete(Type item)
{
	if(this->m_cursize==0)
	{
		cout<<"the DoubleLink is empty!"<<endl;
		return 0;
	}
	while(this->head->m_data==item)
	{
		if(this->m_cursize==1)
		{
			cout<<"the node of item is head,can't be deleted!"<<endl;
			return 0;
		}
		else
		{
			this->m_cursize--;
			LinkNode<Type>*q=this->head->m_next;
			this->head->m_pre->m_next=q;
			q->m_pre=head->m_pre;
			delete head;
			head=q;
		}
	}
	LinkNode<Type>*temp=this->head,*p=this->head;
	while(temp->m_next!=head)
	{
		p=temp;
		temp=temp->m_next;
		if(temp->m_data==item)
		{
			this->m_cursize--;
			p->m_next=temp->m_next;
			temp->m_next->m_pre=p;
			delete temp;
		}
	}
	return 1;
}
template<typename Type>Type DoubleLink<typename Type>::Jsf(int m)
{
	LinkNode<Type>*temp=this->head;
	int j=1;
	while(this->m_cursize>1)
	{
		if(j==m)
		{
			LinkNode<Type>*p=temp->m_next;
			if(temp==head)
			{
				head=p;
			}
			temp->m_pre->m_next=temp->m_next;
			temp->m_next->m_pre=temp->m_pre;
			delete temp;
			temp=p;
			j=1;
			this->m_cursize--;
		}
		else
		{
			temp=temp->m_next;
			j++;
		}	
	}
	return head->m_data;
}

test.cpp

#include<iostream>
#include"DoubleLink.h"
using namespace std;
int main()
{	
	int n,m;
	while(cin>>n>>m)
	{
		DoubleLink<int> Link(1);
		for(int i=2;i<=n;i++)
		{
			Link.Insert(i);
		}
		Link.Print();
		cout<<"the winner is :"<<Link.Jsf(m)<<endl;
	}
	return 0;
}