머리와 꼬리 노드를 가진 양방향 순환 체인 테이블
4008 단어 머리와 꼬리를 가진 양방향 순환 체인 시계
#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;
}