#include <iostream.h>
#include <string.h>
#include <stdlib.h>
using namespace std;

class node
{
	friend class linklist;
	private:	
		long int ID;
		char *Name;
		long int Tel;
		node *next;	
	public:	
		node()
		{
			next=NULL;				
		}
		node(long int &a,char *b,long int &c)
		{
			ID=a;strcpy(Name,b);Tel=c;
			next=NULL;	
		}
		~node(){}
};

class linklist
{
	private:
		node *head;//头指针 
		node *p;//p始终指向当前节点
		int length; 
	public:	
		linklist();
		~linklist();
		void Freelist();//释放链表内存 			
		void insertBefore ();
		void deletedata(int &i); 
		void output();//返回输出猴子或猴子大王的相关信息
		void clearlist();
		void chooseking();		 
};

linklist::linklist()
{
	head=p=new node();
	head->next=head;
	length=0; 
}
linklist::~linklist()
{
	Freelist();
}
void linklist::Freelist()
{
	clearlist();
	delete head;
}
void linklist::clearlist()
{
	node *p;
	while (head->next!=NULL)
	{
		p=head->next;
		head->next=p->next;
		delete []p;
		length--;
	}
	
}
void linklist::insertBefore()
{
	long int a;char *b;long int c;
	//cout<<"分配内存失败!"<<endl;		
	cout<<"请输入猴子的ID,name,Tel:(中间用空格隔开)"<<endl;
	cin>>a>>b>>c;
	node *q=new node(a,b,c);
	cout<<q->ID<<q->Name<<q->Tel;
	if(head->next==head)
	{
		q->next=head;
		head->next=q;
		p=q;
	}
	else
	{
		q->next=p;
		head->next=q;
		p=q;	
	}
	length++;
	cout<<q->ID<<q->Name<<q->Tel;	
}
void linklist::deletedata(int &i)
{
	if (i>=1)
	{
		node *q=head->next,*q1;
		for (int j=1;j<i-1;j++)
		{
			q=q->next;
		}
		q1=q->next;
		q->next=q->next->next;
		delete q1;	
		length--;
	}
	else
	cout<<"输入数据错误!"<<endl;	
}
void linklist::output()
{
		node *q=head->next;
		if (length==1)
		{
			cout<<"猴子的大王是:"<<endl;
			cout<<"猴王的ID: "<<q->ID<<endl;
			cout<<"猴王的名字:"<<q->Name<<endl;
			cout<<"猴王的Tel:"<<q->Tel;
		}
		else
		{
			for (int i=1;i<=length;i++)
			{
				cout<<"第"<<i<<"只猴子的信息是:"<<endl;
				cout<<"ID "<<q->ID<<"  "<<"name "<<q->Name<<"  "<<"Tel "<<q->Tel<<endl;
				q=q->next;
			}
		}
		
}
void linklist::chooseking()
{
	node *q=head->next,*q1;
	int a;
	do
	{		
		cout<<"你想用那个数作为筛选的基数:"<<endl;
		cin>>a;
	}while (a<=0);
	
	while (head->next->next!=head)
	{
		for (int i=1;i<a-1;i++)
		{
			q=q->next;
			if (q->next==head)
				q->next=q->next->next;
			if (q==head)
				q=q->next;	
		}
		q1=q->next;
		q->next=q->next->next;
		delete q1;
		q=q->next;
	}
}

int main ()
{
	linklist monkey;
//	monkey.linklist();
	int n,i;
	cout<<"请输入猴子的只数:"<<endl;
	cin>>n;	
	for(i=1;i<=n;i++)
	{
		cout<<i<<endl;
		monkey.insertBefore();
	}
	monkey.output();
	monkey.chooseking();
	monkey.output();
	monkey.~linklist();	
	return 0;
}