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

class node
{
	friend class linklist;
	private:
                enum{len=64}	
		long int ID;
		char Name[len];
		long int Tel;
		node *next;	
	public:	
		node()
		{
			next=NULL;				
		}
		node(long int &a,char *b,long int &c)
		{
			ID=a;strncpy(Name,b,len);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=nullptr;
	length=0; 
}
linklist::~linklist()
{
	Freelist();
}
void linklist::Freelist()
{
	clearlist();
	delete head;
}
void linklist::clearlist()
{
	node *p;
	while (head!=NULL)
	{
		p=head;
		head=head->next;
		delete p;
		length--;
	}
	
}
void linklist::insertBefore()
{
	long int a;
        char b[len];
        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==nullptr)
		head=q;
	else
		p->next=q;
	p=q;	
	length++;
	cout<<q->ID<<q->Name<<q->Tel;	
}
bool linklist::deletedata(void)
{    
        node *q1;
    	if (head==nullptr)
           {
            cout<<"没有猴子的信息！\n";
            return false;
           }
        else
           {
            q1=head;
            while(q1->next != p)
               q1=q1->next;
            delete p;
            q1->next=nullptr;
            p=q1;
            return true;       
           }
}
void linklist::output()
{
		node *q=head;
		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;
}