循环链表实现删除数据小孩转圈淘汰游戏（循环链表实现）

深藏阁楼爱情的钟 2022-05-17 12:57 171阅读 0赞

因为我使用了分开写的文件，把类的声明放在了头文件中，下面是类的定义

#include<iostream>
    #include"Cycling_Link.h"
    using namespace std;
    #define TRUE 1
    #define ERROR 0
    int Link::Initlist()
    {
    	head=new Data;
    	if(NULL==head)return ERROR;
    	head->data=0;
    	head->next=head;
    	length=0;
    	return TRUE;
    }
    void Link::Destorylist()
    {
    	int i;
    	Data *temp;
    	for(i=0;i<=length;i++)
    	{
    		temp=head;
    		head=head->next;
    		delete temp;
    	}
    }
    void Link::output()
    {
    	if(length==0)
    	{
    	 cout<<"当前链表为空"<<endl;
    	 return;
    	}
    	cout<<"当前链表长度为:"<<length<<endl;
    	cout<<"所有孩子的编号为:";
    	Data *temp=head->next;
    	for(int i=0;i<length;i++)
    	{
    	cout<<temp->data<<" ";
    	temp=temp->next;
    	}
    	cout<<endl;		
    }
    int Link::Listlength()
    {
    	return length;
    }
    int Link::Insert(int s,int n)//当链表中没有数据，则不执行循环
    {
    	if(s<1||s>length+1) return ERROR;
    	Data *t=new Data;
    	if(t==NULL)return ERROR;
    	t->data=n;
    	Data *p=head;
    	int i;
    	for(i=0;i<s-1;i++)
    	p=p->next;
    	t->next=p->next;
    	p->next=t;
    	length++;
    	return TRUE;
    }
    int Link::Listdelete(int s,int n,int z)
    {
    	if(length==0&&s==0) return ERROR;
    	int i;
    	if(z==1)record=head;
    	//else
    		//record=record->next;
    	for(i=0;i<s-1;i++)
    	{
    		record=record->next;
    	if(record->data==0)record=record->next;
    	}
    	Data *temp;
    	temp=record->next;
    	if(temp->data==0)//注意改变当指针指为0的时候，不能计算在内，因此必须把它放在改变指针的循环内
    	{
    		temp=record->next->next;
    		record->next->next=temp->next;//注意当循环链表的时候，当头指针直接指向的数据被删除的时候，一定要改变头指针的指向
    	}
    	else
    	record->next=record->next->next;
    	n=temp->data;
    	delete temp;
    	length--;
    	return n;
    }

类的声明，头文件中

struct Data
    {
    	int data;
    	Data *next;
    };
    
    class Link
    {
    private:
    	Data *head;
    	Data *record;
    	int length;
    public:
    	int Initlist();
    	void Destorylist();
    	void output();
    	int Listlength();
    	int Insert(int s,int n);
    	int Listdelete(int s,int n,int z);
    };

实现

#include<iostream>
    #include"Cycling_Link.h"
    using namespace std;
    
    int main()
    {
    	int Game1(Link a,int m,int k);
    	int m,n,k;
    	cout<<"请输入小孩的个数为:";
    		cin>>n;
    	cout<<"请输入你要删除的间隔数:";
    	cin>>m;
    	cout<<"请输入你想要获胜者的数量:";
    	cin>>k;
    	Link child;
    	child.Initlist();
    	int i;
    	//for(j=1;j<3;j++)循环链表
    	for(i=1;i<=n;i++)
    		child.Insert(child.Listlength()+1,i);
    	child.output();
    	Game1(child,m,k);
    	return 0;
    }
    int Game1(Link a,int m,int k) //对象的传递是双向的
    {
    	int t,s=0;
    	while(a.Listlength()>k) //在这改变获胜者的数量
    	{
    		s++;
    		//cout<<"ufhe";
    		t=a.Listdelete(m,t,s);
    		cout<<"删除的数字为:"<<t<<endl;
    		a.output();
    	}
    	a.output();
    	return 0;
    }