circularlist.cpp

约瑟夫问题

//CircularList.cpp文件
#include<iostream.h>
#include"CircularList.h"
#include<stdlib.h>


template<class T>   //循环链表类中申请结点空间的函数
CircularNode<T> *CircularList<T>::GetNode(const T&item,const T&passwrod)
{
	CircularNode<T>*newNode=new CircularNode<T>(item,passwrod);

	if(!newNode)	//若动态内存申请失败，则给出相应提示并返回空指针
	{
		cerr<<"GetNode:Memory allocation failed!"<<endl;
		return NULL;
	}

	return newNode;	  //返回指向新生成结点的指针
}


template<class T>    //链表类中释放结点空间的函数
void CircularList<T>::FreeNode(CircularNode<T>*ptr)
{

	if(!ptr)   	  //若ptr为空，则给出相应提示并返回
	{
		cerr<<"FreeNode: invalid node pointer!"<<endl;
		return ;
	}
   
	delete ptr;   //释放结点占用的内存空间  
}


template<class T>  //链表类的构造函数（建立一个空链表）
CircularList<T>::CircularList(void)
{
    	frist=new CircularNode<T>;
		rear=new CircularNode<T>;
		prevPtr=new CircularNode<T>;
		currPtr=new CircularNode<T>;
       	currPtr=frist;
		size=0;
        position=0;

}


template<class T>  //链表类的析构函数
CircularList<T>::~CircularList(void)
{
	Clear();	//清空链表，释放所有结点空间
}


template<class T>//链表类中取表大小的函数
int CircularList<T>::Size(void) const
{
	return size;
}



template<class T>//循环链表类中重置当前位置的函数
int CircularList<T>::SetPosition(int pos)
{
	

	for(int k=1;k<pos;k++)
	{
		position++;
		prevPtr=currPtr;
		currPtr=currPtr->NextNode();

		if(currPtr==frist)
		{   
			prevPtr=currPtr;
	        currPtr=currPtr->NextNode();
         }
	}

	return position;	//返回当前结点位置
}


template<class T>   //循环链表类中取当前结点位置的函数
int CircularList<T>::GetPosition(void) const
{
	return position;
}


template<class T>   //循环链表类中在当前结点后插入新结点的函数
void CircularList<T>::InsertAfter(const T&item,const T&passwrod)
{  

	CircularNode<T>*newNode=new CircularNode<T>(item,passwrod);
	currPtr->InsertAfter(newNode);
	currPtr=newNode;
	rear=newNode;
    size++;
	
}


template<class T>   //循环链表类中删除当前结点的函数
void CircularList<T>::DeleteAt(void)
{
	 CircularNode<T> *OldNode;
     OldNode=currPtr;

     currPtr=currPtr->NextNode();
     prevPtr->DeleteAfter();

	 FreeNode(OldNode);

      if(currPtr==frist)
	  {     
			prevPtr=currPtr;
	        currPtr=currPtr->NextNode();
      }

	//链表大小减1
	size--;
}



template<class T>
T CircularList<T>::GetID(void)const //访问个人编号的函数
{
	
	if(currPtr==frist)       
	{
		cerr<<"The Circular List is  Header, The ID Is Empty!"<<endl;
		exit(1);
	}
	return currPtr->ID ;
}


template<class T>
T CircularList<T>::GetPassWord(void)const //访问个人密码的函数的实现
{
	
	if(currPtr==frist)
	{
		cerr<<"The Circular List is Header, The PassWord Is Empty!"<<endl;
		exit(1);
	}
	return currPtr->PassWord;
}



//循环链表类中修改当前结点数据的函数
template<class T>
void CircularList<T>::SetData(const T&item,const T&passwrod)
{

	if(currPtr==frist)
	{
		cerr<<"The Circular List is Header, The PassWord Is Empty!"<<endl;
		exit(1);
	}
	//修改当前结点的值
    currPtr->PassWord=passwrod;
	currPtr->ID=item;
}


template<class T>							  
void CircularList<T>::Clear(void)	//循环链表类中清空链表的函数
{
	CircularNode<T>*currNode=frist,*nextNode;
	while(currNode!=frist)
	{
		nextNode=currNode->NextNode();	//保存后继结点指针
		FreeNode(currNode);	//释放当前结点
		currNode=nextNode;//原后继结点成为当前结点
	}
	frist=rear=prevPtr=currPtr=NULL;	//修改循环链表数据
	size=0;position=0;
}


template<class T>	
void CircularList<T>::JosePhusFristWay(int n,int m)   //用方法一实现约瑟夫问题
{	
	prevPtr=frist;
	currPtr=frist->NextNode(); //定位第一个结点的位置
	position=1;   

	for(int i=1;i<=n;++i)
	{
	   	 SetPosition(m);  //设置当前要删除的位置
	cout<<"**-----------------------------------------------------------------------**"<<endl;
    cout<<"The "<<"^"<<i<<"^"<<"Person Which Is Deleted Is-- "<<GetID()<<
			"--******--"<<"This Person Of PassWord Is"<<GetPassWord()<<endl;
         DeleteAt(); //删除要删除的结点

	}
	
}


template<class T>
void CircularList<T>::JosePhusSecondWay(int n,int m)    //用方法二实现约瑟夫问题

{
	prevPtr=frist;
	currPtr=frist->NextNode(); //定位第一个结点的位置
	position=1; 

	for(int i=1;i<=n;++i)
	{
	   	SetPosition(m);  //设置当前要删除的位置
	cout<<"**-----------------------------------------------------------------------**"<<endl;
        cout<<"The "<<"^"<<i<<"^"<<"Person Which Is Deleted Is-:"<<GetID()<<
			"--****--"<<"This Person Of PassWord Is-:"<<GetPassWord()<<endl;
         m=GetPassWord();  //获取密码当前要删除的人的密码 作为新的出局的位置
        DeleteAt(); //删除要删除的结点
       

	}
}