双方向チェーンテーブルの逆置き(2種類)
2865 ワード
#include<iostream>
#include<string>
using namespace std;
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)
{
}
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;
}
}
void PopBack()
{
if (_head == NULL)
{
return;
}
else if (_head == _tail)
{
delete _head;
_head = _tail = NULL;
}
else
{
LinkNode<T> *del = _tail;
_tail->_prev->_next = NULL;
_tail = _tail->_prev;
delete del;
}
}
void PushFront(const T& x)
{
if (_head == NULL)
{
_head = new LinkNode<T>(x);
_tail = _head;
}
else
{
LinkNode<T>* tmp = new LinkNode<T>(x);
tmp->_next = _head;
_head->_prev = tmp;
_head = tmp;
}
}
void PopFront()
{
if (_head == NULL)
{
return;
}
else if (_head == _tail)
{
delete _head;
_head = _tail = NULL;
}
else
{
LinkNode<T> *del = _head;
_head->_next->_prev = NULL;
_head = _head->_next;
delete del;
}
}
~List()
{
while (_head)
{
Destory();
}
_head = _tail = NULL;
}
void Print()
{
LinkNode<T>* cur = _head;
while (cur)
{
cout << (cur->_data) << "->";
cur = cur->_next;
}
cout << "NULL" << endl;
}
void Reverse_()
{
if (_head == NULL || _head == _tail)
return;
LinkNode<T>* left = _head;
LinkNode<T>* right = _tail;
while (left != right&&left->_prev != right)//
{
swap(left->_data, right->_data);
left = left->_next;
right = right->_prev;
}
}
void Reverse()
{
if (_head == NULL || _head == _tail)
return;
LinkNode<T>* cur = _head;
while (cur)
{
swap(cur->_prev, cur->_next);
cur = cur->_prev;//
}
swap(_head, _tail);
}
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 = NULL;
delete del;
}
}
protected:
LinkNode<T>* _head;
LinkNode<T>* _tail;
};
void Test1()
{
List<int> k;
k.PushBack(1);
k.PushBack(2);
k.PushBack(3);
k.PushBack(4);
k.PushBack(5);
k.PushBack(6);
k.Print();
k.Reverse_();
k.Print();
k.Reverse();
k.Print();
}
int main()
{
Test1();
system("pause");
return 0;
}
注意試験例の選択