新建 文本文档.txt

约瑟夫问题

//linkedlist.h文件
#include<iostream.h>
#include "node.cpp"

template <class T>

class LinkedList
{
private:
	//指向表头和表尾的指针
	Node<T>  *front, *rear;
	//用于访问数据，插入和删除结点的指针
	Node<T>  *prevPtr, *currPtr;
	//表中的结点数
	int size;
	//表中当前结点位置计数
	int position;
	//申请及释放结点空间的函数
	Node<T> *GetNode(const T& item ,Node<T> *ptr=NULL);
	void FreeNode(Node<T> *p);
public:
	//构造函数和析构函数
	LinkedList(void);
	~LinkedList(void);
	//重载的赋值运算符
	LinkedList<T> & operator = (const LinkedList<T> &orgList) ;
    //取表的大小
	int Size(void) const ;
	//判断表是否为空
	bool IsEmpty(void) const;
	//重定位当前结点
	int NextNode(void) ;
	int SetPosition(int pos);
    int GetPosition(void) const; 
	//插入结点的函数
	void InsertAt(const T& item);
	void InsertAfter(const T& item);
	//删除结点的函数
	void DeleteAt(void);
	void DeleteAfter(void);
	//修改和访问数据的函数
	T GetData(void) const;
	void SetData(const T& item);
	//清空链表的函数
	void Clear(void);
};

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

//链表类中申请结点空间的函数
template <class T>
Node<T> *LinkedList<T>::GetNode(const T& item,Node<T> *ptr)
{
	Node<T> *newNode=new Node<T> (item,ptr);
	//若动态内存申请失败，则给出相应提示并返回空指针
	if(!newNode)
	{
		cerr<<"GetNode:Memory allocation failed!"<<endl;
		return NULL;
	}
	//返回指向新生成结点的指针
	return newNode;
}

//链表类中释放结点空间的函数
template <class T>
void LinkedList <T>::FreeNode(Node<T> *ptr)
{
	//若ptr为空，则给出相应提示并返回
	if(!ptr)
	{
		cerr<<"FreeNode: invalid node pointer!"<<endl;
		return ;
	}
   //释放结点占用的内存空间
	delete ptr;
}

//链表类的构造函数（建立一个空链表）
template <class T>
LinkedList<T>::LinkedList(void): front(NULL),rear(NULL),prevPtr(NULL),currPtr(NULL),size(0),position(-1)
{}

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

//链表类中重载赋值运算符的函数
template <class T>
LinkedList<T> & LinkedList<T>::operator = (const LinkedList<T> &orgList)
{
	Node<T> *p=orgList.front;
	//清空本链表
	Clear();
	//将表orgList中的元素复制到本表
	while(p)
	{
		InsertAfter(p->date);
		p=p->NextNode();
	}
	//设置当前结点
	SetPosition(orgList.position);
	return *this;
}

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

//链表类中判断是否为空的函数
template<class T>
bool LinkedList<T>::IsEmpty(void) const
{
	return size?false:true ;
}

//链表类中将后继结点设置为当前结点的函数
template <class T>
int LinkedList<T>::NextNode(void) 
{
	//若当前结点存在，则将其后继结点设置为当前结点
	if((position>=0)&&(position<size))
	{
		position++;
		prevPtr=currPtr;
		currPtr=currPtr->NextNode();
	}
	else
	{
		//否则将当前位置设为表尾后
		position=size;
	}
	//返回新位置
	return position;
}

//链表类中重置当前位置的函数
template <class T>
int LinkedList<T>::SetPosition(int pos)
{
	//若链表为空，则返回
	if(!size) return -1;
	//若链表为空，则返回
	if(pos<0 || pos>size-1)
	{
		cerr<<"position error"<<endl;
		return -1;
	}
	//寻找对应结点
	prevPtr=NULL;
	currPtr=front;
	position=0;
	for(int k=0;k<pos ;k++)
	{
		position++;
		prevPtr=currPtr;
		currPtr=currPtr->NextNode();
	}
	//返回当前结点位置
	return position;
}

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

//链表类中在当前结点处插入新结点的函数
template <class T>
void LinkedList<T>::InsertAt(const T& item)
{
	Node<T> *newNode;
	if(!size)
	{
		//在空表中插入
		newNode=GetNode(item,front);
		front=rear=newNode;
		position=0;
	}
	else if(!prevPtr)
	{
		//在表头结点处插入
		newNode=GetNode(item,front);
		front=newNode;
	}
	else
	{
		//在链表的中间位置插入
		newNode=GetNode(item,currPtr);
		prevPtr->InsertAfter(newNode);
	}
	//增加链表的大小
	size++;
	//新插入的结点为当前结点
	currPtr=newNode;
}

//链表类中在当前结点后插入新结点的函数
template<class T>
void LinkedList<T>::InsertAfter(const T& item)
{
	Node<T> *newNode;
	if(!size)
	{
		//在空表中插入
		newNode=GetNode(item);
		front=rear=newNode;
        position=0;
	}
	else if (currPtr==rear|| !currPtr)
	{
		//在表尾结点后插入
		newNode=GetNode(item);
		rear->InsertAfter(newNode);
		prevPtr=rear;
		rear=newNode;
		position=size;
	}
	else
	{
		//在链表的中间位置插入
		newNode=GetNode(item,currPtr->NextNode());
		currPtr->InsertAfter(newNode);
		prevPtr=currPtr;
		position++;
	}
	//增加链表的大小
	size++;
	//新插入的结点为当前结点
	currPtr=newNode;
}

//链表类中删除当前结点的函数
template <class T>
void LinkedList<T>::DeleteAt(void)
{
	Node<T> *oldNode;
	//若表为空或已到表尾之后，则给出错误提示并返回
	if(!currPtr)
	{
		cerr<<"DeleteAt: current position is invalid!"<<endl;
		return ;
	}
	if(!prevPtr)
	{
		//删除的是表头结点
		oldNode=front;
		front=currPtr->NextNode();
	}
	else
	{
		//删除的是表中结点
		oldNode=prevPtr->DeleteAfter();
	}
    if(oldNode==rear)
	{
	//删除的是表尾结点，则修改表尾指针和当前结点位置值
	rear=prevPtr;
	position--;
	}
	//后继结点作为新的当前结点 
	currPtr=oldNode->NextNode();
	//释放原当前结点
	FreeNode(oldNode);
	//链表大小减1
	size--;
}

//链表类中删除当前结点后继的函数
template <class T>
void LinkedList<T>::DeleteAfter(void)
{
	Node<T> *oldNode;
	//若表为空或已到表尾，则给出错误提示并返回
	if(!currPtr|| currPtr==rear)
	{
		cerr<<"DeleteAfter:current position is invalid!"<<endl;
		return;
	}
	//保存被删除结点的指针并从链表中删除该结点
	oldNode=currPtr->DeleteAfter();
	if(oldNode==rear)
	{
		//删除的是表尾结点
		rear=currPtr;
	}
	//释放被删除结点
	FreeNode(oldNode);
	//链表大小减1
	size--;
}

//链表类中获取当前结点数据的函数
template <class T>
T LinkedList<T>::GetData(void) const 
{
	//若表为空或已到达表尾之后，则出错
	if(!size || !currPtr)
	{
		//给出出错信息并退出
		cerr<<"Data:current node not exist!"<<endl;
		exit(1);
	}
	return currPtr->data ;
}

//链表类中修改当前结点数据的函数
template <class T>
void LinkedList<T>::SetData(const T& item)
{
	//若表为空或已经达到表尾之后，则出错
	if(!size || !currPtr)
	{
		cerr<<"Data:current node not exist!"<<endl;
		exit(1);
	}
	//修改当前结点的值
	currPtr->data=item;
}

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