C++实现数据结构四 单循环链表

ListNode.h

template<typename Type> class CircularList; //不能写成：CircularList<Type>

//重载操作数声明，注意和在类中友元证明方式的区别
//template<typename Type> class ListNode;
//template<typename Type>
//ostream& operator<< (ostream &os, ListNode<Type>  &node);


template<typename Type> class ListNode
{
private:
	friend class CircularList<Type>;
	friend ostream& operator<< <Type>(ostream&, ListNode<Type>&);
	ListNode(): next(NULL) {}
	ListNode(const Type item, ListNode<Type> *p=NULL ): data(item), next(p) {}
	~ListNode()
	{
		next = NULL;
	}

private:
	Type data;
	ListNode *next;
};
template<typename Type>
ostream& operator<< (ostream &os, ListNode<Type>  &node)
{
	os<<node.data;
	return os;
}
           

CircularList.h

#include "ListNode.h"

template<typename Type> class CircularList
{
public:
	CircularList()
	{
		head = new ListNode<Type>();
		head->next = head;
	}
	~CircularList()
	{
		MakeEmpty();
		delete head;
	}

public:
	void MakeEmpty();
	int Length();
	ListNode<Type> *Find(int n);
	bool Insert(Type item, int n=0);
	Type Remove(int n=0);
	bool RemoveAll(Type item);
	Type Get(int n);
	void Print();

private:
	ListNode<Type> *head;
};


template<typename Type>
void CircularList<Type>::MakeEmpty()
{
	ListNode<Type> *pmove = head->next ;
	ListNode<Type> *pdel;
	while(pmove != head)
	{
		pdel=pmove;
		pmove = pmove->next;
		delete pdel;
		pdel = NULL;
	}
}

template<typename Type>
int CircularList<Type>::Length()
{
	ListNode<Type> *pmove = head;
	int count = 0;
	while(pmove->next != head)
	{
		++count;
		pmove = pmove->next;
	}
	return count;
}

template<typename Type>
ListNode<Type>* CircularList<Type>::Find(int n)
{
	if(n<1)
	{
		cout<<"the n is illegal"<<endl;
		return NULL;
	}

	ListNode<Type> *pmove = head;
	for(int i=0; i<n; ++i)
	{
		pmove = pmove->next;
		if(pmove == head)
		{
			cout<<"the n is out of the boundary"<<endl;
			return NULL;
		}
	}


	return pmove;
}

template<typename Type>
bool CircularList<Type>::Insert(Type item, int n=0)
{
	if(n<0)
	{
		cout<<"The n is illegal"<<endl;
	}

	
	ListNode<Type> *pmove = head;
	for(int i=0; i<n; ++i)
	{
		pmove = pmove->next;
		if(pmove == head)
		{
			cout<<"the n is out of the boundary, so cannot insert the data"<<endl;
			return false;
		}
	}
	ListNode<Type> *pnode = new ListNode<Type>();
	pnode->data = item;
	pnode->next = pmove->next;
	pmove->next = pnode;
	return true;

}

template<typename Type>
Type CircularList<Type>::Remove(int n=0)
{
	if(n < 1)
	{
		cout<<"the n is illegal"<<endl;
		return 0;
	}
	ListNode<Type> *pmove = head, *pdel;
	for(int i = 0; i< (n-1) && pmove->next != head ; ++i)
	{
		pmove= pmove->next;

	}
	if(pmove->next == head)
	{
		cout<<"the n is out of boundary"<<endl;
		return 0;
	}

	pdel = pmove->next;
	pmove->next = pdel->next;
	Type item = pdel->data;
	delete pdel;
	return item;

}

template<typename Type>
bool CircularList<Type>::RemoveAll(Type item)
{
	ListNode<Type> *pmove= head->next, *pdel, *p= head;
	int count =0;
	while(pmove != head)
	{
		//p->next = pmove;
		//p = p->next;
		if(pmove->data == item)
		{
			++count;
			pdel =pmove;
			pmove = pmove->next;
			p->next =pmove;
			delete pdel;
			pdel = NULL;
		}
		else
		{
			pmove = pmove->next;
			p= p->next ;
		}
			
	}
	if(count == 0)
		return false;
	else
		return true;
}

template<typename Type>
Type CircularList<Type>::Get(int n)
{
	ListNode<Type> *p = Find(n);
	if(p == NULL)
	{
		cout<<"cannot get the data at "<<n<<endl;
		return 0;
	}
	return p->data;
}

template<typename Type>
void CircularList<Type>::Print()
{
	ListNode<Type> *pmove = head->next;
	
	cout<<"head-->";
	while(pmove != head)
	{
		cout<<pmove->data<<"-->";
		pmove = pmove->next;
	}
	cout<<"voer"<<endl;
}