C++實作單向循環連結清單

#include<iostream>
#include<assert.h>
using namespace std;

typedef int DataType;
struct LinkNode
{
	DataType _data;
    LinkNode* _next;
	LinkNode(const DataType& x)
		:_data(x)
		,_next(NULL)
	{}
};
class Slist
{
public:
	Slist()
		:_head(NULL)
		,_tail(NULL)
	{}
	~Slist()
	{
		Destory();
	}
	Slist(const Slist& s)
		:_head(NULL)
		, _tail(NULL)
	{
		if (s._head == NULL)
			return;
		LinkNode* begin = s._head;
		do{
			this->PushBack(begin->_data);
			begin = begin->_next;
		} while (begin != s._head);
	}
	Slist& operator = (const Slist& s)
	{
		if (this != &s)
		{
			this->Destory();
			LinkNode* begin = s._head;
			do{
				this->PushBack(begin->_data);
				begin = begin->_next;
			} while (begin != s._head);
		}
		return *this;
	}
	void Destory()
	{
		LinkNode* begin = _head;
		while (begin!=_tail)
		{
			LinkNode* del = begin;
			begin = begin->_next;
			delete del;
		}
		delete _tail;
		_head = NULL;
		_tail = NULL;
	}
public:
	void Print()
	{
		if (_head == NULL)
		{
			return;
		}	
		LinkNode* begin = _head;
		do{
			cout << begin->_data << "->";
			begin = begin->_next;
		}while (begin != _head);
		cout << endl;
	}
	void PushBack(const DataType& x)//尾插
	{
		//1.空連結清單
		//2.一個或一個以上節點
		if (_head == NULL)
		{
			_head = new LinkNode(x);
			_tail = _head;
			_tail->_next = _head;
		}
		else 
		{
			_tail->_next = new LinkNode(x);
			_tail = _tail->_next;
			_tail->_next = _head;
		}
	}
	void PopBack()
	{
		//1.空連結清單
		//2.隻有一個節點
		//3兩個或兩個以上節點
		if (_head == NULL)
		{
			return;
		}
		else if (_head == _tail)
		{
			delete _head;
			_head = NULL;
			_tail = NULL;
		}
		else
		{
			LinkNode* prev = _head;
			while (prev->_next != _tail)
			{
				prev = prev->_next;
			} 
			prev->_next = _head;
			delete _tail;
			_tail = prev;
		}
	}
	void PushFront(const DataType& x)
	{
		if (_head == NULL)
		{
			_head = new LinkNode(x);
			_tail =_head ;
			_tail->_next = _head;
		}
		else
		{
			LinkNode* begin= new LinkNode(x);
			begin->_next = _head;
			_head = begin;
			_tail->_next = _head;
		}
	}
	void PopFront()//頭删
	{
		if (_head == NULL)
		{
			return;
		}
		else if (_head == _tail)
		{
			delete _head;
			_head = NULL;
			_tail = NULL;
		}
		else
		{
			LinkNode* del = _head;
			_head = _head->_next;
			delete del;
			_tail->_next = _head;
		}
	}
	LinkNode* Find(DataType x)
	{
		LinkNode* begin = _head;
		if (_head == NULL)
		{
			return NULL;
		}
		do{
			if (begin->_data == x)
			{
				return begin;
			}
			begin = begin->_next;
		}while(begin!=_head);
		return NULL;
	}
	bool Remove(LinkNode* n)
	{
		assert(n);
		if (_head == NULL)
		{
			return false;
		}
	    if (_head == _tail)
		{
			if (n == _head)
			{
				delete _head;
			    _head = NULL;
			    _tail = NULL;
	            return true;
			}
			return false;
		}
		LinkNode* prev = _head;
		while (prev->_next!=n)
		{
			prev = prev->_next;
			if (prev = _head)
			{
				return false;
			}
		}
		if (n == _head)
		{
			_head = _head->_next;
			delete n;
			_tail->_next = _head;
			return true;
		}
		else if (n == _tail)
		{
			prev->_next = _head;
			_tail = prev;
			delete n;
			return true;
		}
		else
		{
			prev->_next = n->_next;
		    delete n;
		    return true;
		}
		
	}
	void Reverse()
	{
		LinkNode* newHead=NULL, *newTail=_head;
		LinkNode* begin = _head;
		while (1)
		{
			LinkNode* tmp = begin;
			begin = begin->_next;
			tmp->_next = newHead;
			newHead = tmp;
			if (begin == _head)
			{
				break;
			}
		}
		_head = newHead;
		_tail = newTail;
		_tail->_next = _head;
	}
	bool Insert(LinkNode * n, DataType x)
	{
		if (_tail <= n)
		{
			return false;
		}
		else{
			LinkNode *begin = _head;
			do{
				begin = begin->_next;
				if (begin == _head)
				{
					return false;
				}
			} while (begin->_next != n);
			begin->_next = n->_next;
			delete n;
			return true;
		}
		return false;
	}
	void Erase(DataType x)
	{
		LinkNode* del = _head;
		do{
			del = del->_next;
			if (del->_data == x)
			{
				do{
					del->_data = del->_next->_data;
				} while (del != _tail);
			}
		} while (del != _tail);
	}
private:
	LinkNode* _head;//指向連結清單頭的指針
	LinkNode* _tail;//指向連結清單尾的指針
};
void Test1()
{
	Slist s1;
	s1.PushBack(1);
	s1.PushBack(2);
	s1.PushBack(3); 
	s1.PushBack(4);
	s1.Print();

	/*s1.PopBack();
	s1.PopBack();
	s1.Print();
*/
	Slist s2;
	s2 = s1;
	s2.Destory();
	s2.Print();
}
void Test2()
{
	Slist s2;
	s2.PushFront(1);
	s2.PushFront(2);
	s2.PushFront(3);
	s2.Print();

	s2.Reverse();
	s2.Print();

	s2.PopFront();
	s2.Print();

	LinkNode* ret = s2.Find(2);
	cout << "ret=" << ret->_data << endl;

}
int main()
{
	Test1();
	//Test2();
	system("pause");
	return 0;
}