머리와 꼬리 노드를 가진 양방향 순환 체인 테이블

테스트 용례의 선택에 주의하세요!!
#include<iostream>
using namespace std;
#include<string>
template<class T>
struct LinkNode
{
	LinkNode(const T& x)
	:_data(x)
	, _prev(NULL)
	, _next(NULL)
	{

	}
	T _data;
	LinkNode<T>* _prev;
	LinkNode<T>* _next;
};
template<class T>
class List
{
public:
	List()
	:_head(NULL)
	, _tail(NULL)
	{}
	List(const List<T>& l)
	:_head(NULL)
	, _tail(NULL)
	{
		LinkNode<T>* cur = l._head;
		if (cur == NULL)
		{
			return;
		}
		(*this).PushBack(cur->_data);
		while (cur&&cur->_next!=l._head)
		{
			cur = cur->_next;
			(*this).PushBack(cur->_data);
		}
	}
	List<T>& operator=(List<T> l)
	{
		swap(_head, l._head);
		swap(_tail, l._tail);
	}
	void PushBack(const T& x)
	{
		if (_head == NULL)
		{
			_head = new LinkNode<T>(x);
			_tail= _head;
		}
		else
		{
			LinkNode<T>* tmp = new LinkNode<T>(x);
			_tail->_next = tmp;
			tmp->_prev = _tail;
			_tail = _tail->_next;
			_tail->_next = _head;
			_head->_prev = _tail;
		}
	}
	void PopBack()
	{
		Destory();
	}
	void Print()
	{
		LinkNode<T>* cur = _head;
		if (cur == NULL)
		{
			return;
		}
		cout << (cur->_data) << "->";
		while (cur&&cur->_next!= _head)
		{
			cur = cur->_next;
			cout << (cur->_data) << "->";
		}
		cout<<"NULL" << endl;
	}
	~List()
	{
		while (_head!=NULL)
		{
           Destory();
		}
	}
	LinkNode<T>* Find(const T& x)
	{
		LinkNode<T>* cur = _head;
		if (cur == NULL)
		{
			return NULL;
		}
		if (cur->_data == x)
		{
			return cur;
		}
		while (cur->_next != _head)
		{
			cur = cur->_next;
			if (cur->_data == x)
				return cur;
		}
		return NULL;
	}
	void Insert(LinkNode<T>* pos, const T& x)
	{
		if(pos==NULL)
			return;
		LinkNode<T>* tmp = new LinkNode<T>(x);
		tmp->_prev = pos;
		tmp->_next = pos->_next;
		pos->_next = tmp;
	}
	void Erase(LinkNode<T>* pos)
	{
		if (pos == NULL)
			return;
		else if (pos == _tail)
		{
			_tail = _tail->_prev;
		}
		else if (pos == _head)
		{
			_head = _head->_next;
		}
		LinkNode<T>* del = pos;
		LinkNode <T>* next = pos->_next;
		LinkNode<T>* prev = pos->_prev;
		if(prev)
			prev->_next = next;
		if(next)
			next->_prev =prev;
		delete del;
	}
protected:
	void Destory()
	{
		if (_head == NULL)
		{
			return;
		}
		else if(_head == _tail)
		{
			delete _head;
			_head = _tail = NULL;
		}
		else
		{
			LinkNode<T>* del = _head;
			_head = _head->_next;
			_head->_prev = del->_prev;
			del->_prev->_next = _head;
			delete del;
		}
	}
protected:
	LinkNode<T>* _head;
	LinkNode<T>* _tail;
};
void Test1()
{
	List<int> l;
	l.PushBack(1);
	l.PushBack(2);
	l.PushBack(3);
	l.PushBack(4);
	l.PushBack(5);
	l.Print();
	List<int> l1(l);
	l1.Print();
}
void Test2()
{
	List<int> l;
	l.PushBack(1);
	l.PushBack(2);
	l.PushBack(3);
	l.PushBack(4);
	l.PushBack(5);
	l.Print();
	List<int> l1(l);
	l1.Print();
	List<int> l2;
	l2.PushBack(6);
	l2.PushBack(7);
	l2.PushBack(8);
	l2.PushBack(9);
	l2.PushBack(10);
	l2.Print();
}
void Test3()
{
	List<string> l1;
	l1.PushBack("abc");
	l1.PushBack("edf");
	l1.PushBack("th");
	l1.PushBack("ik");
	l1.Print();
	List<string> l2(l1);
	l2.Print();
	l2.PopBack();
	l2.PopBack();
	l2.Print();
	l2.PopBack();
	l2.PopBack();
	l2.PopBack();
	l2.PopBack();
	l2.PopBack();
	l2.Print();
}
void Test4()
{
	List<int> l;
	l.PushBack(1);
	l.PushBack(2);
	l.PushBack(3);
	l.PushBack(4);
	l.PushBack(5);
	l.Insert(l.Find(2), 8);
	l.Print();
	l.Erase(l.Find(1));
	l.Print();
}
void Test5()
{
	List<string> l;
	l.PushBack("abc");
	l.PushBack("def");
	l.Erase(l.Find("abc"));
	l.Print();
}
int main()
{
	Test5();
	system("pause");
	return 0;
}

좋은 웹페이지 즐겨찾기