双方向チェーンテーブルにおける基本関数の実装
3199 ワード
#include<iostream>
using namespace std;
typedef int DateType;
struct ListNode
{
DateType _date;
ListNode* _next; //
ListNode* _prev; //
ListNode(DateType x) //
:_date(x)
, _next(NULL)
, _prev(NULL)
{}
};
class List
{
public:
List() //
:_head(NULL), _tail(NULL){}
~List() //
{
Clear();
}
void PushBack(DateType x) //
{
if (_head == NULL)
{
_head = _tail = new ListNode(x);
}
else
{
ListNode* tmp = new ListNode(x);
_tail->_next = tmp;
tmp->_prev = _tail;
_tail = tmp;
}
}
void Clear() //
{
ListNode* cur = _head;
while (cur)
{
ListNode* del = cur;
cur = cur->_next;
delete del;
}
}
void PrintfList() //
{
ListNode* cur = _head;
while (cur)
{
cout << cur->_date << "->";
cur = cur->_next;
}
cout << "NULL " << endl;
}
void PopBack() //
{
if (_head==NULL)
{
return;
}
else if(_head->_next==NULL)
{
delete _head;
_head = _tail = NULL;
}
else
{
ListNode* cur = _tail->_prev;
delete _tail;
_tail = cur;
cur->_next = NULL;
}
}
void PushFront(DateType x) //
{
if (_head == NULL)
{
_head = _tail = new ListNode(x);
}
else
{
ListNode* tmp = new ListNode(x);
tmp->_next = _head;
_head->_prev = tmp;
_head = tmp;
}
}
void PopFront() //
{
if (_head == _tail)
{
if (_head)
{
delete _head;
_head = _tail = NULL;
}
}
else
{
ListNode* cur = _head->_next;
delete _head;
_head = cur;
cur->_prev = NULL;
}
}
void Insert(ListNode* pos, DateType x) //
{
if (_head == _tail)
{
if (_head)
{
ListNode* tmp = new ListNode(x);
pos->_next = tmp;
tmp->_prev = pos;
}
else
{
_head = _tail = new ListNode(x);
}
}
else if (pos->_next == NULL)
{
ListNode* tmp = new ListNode(x);
tmp->_next = NULL;
tmp->_prev = pos;
pos->_next = tmp;
}
else
{
ListNode* tmp = new ListNode(x);
tmp->_next = pos->_next;
pos->_next->_prev = tmp;
tmp->_prev = pos;
pos->_next = tmp;
}
}
ListNode* Find(DateType x) // ,
{
ListNode* cur = _head;
while ( (cur->_date != x) && (cur != NULL) )
{
cur = cur->_next;
}
return cur;
}
void Erase(ListNode* pos ) //
{
if (!pos)
{
return;
}
else if (pos->_prev == NULL)
{
if (pos->_next)
{
ListNode* next = pos->_next;
delete pos;
next->_prev = NULL;
_head = next;
}
else
{
pos->_next = NULL;
pos->_prev = NULL;
delete pos;
}
}
else if (pos->_next == NULL)
{
ListNode* prev = pos->_prev;
delete pos;
prev->_next = NULL;
}
else
{
ListNode* prev = pos->_prev;
ListNode* next = pos->_next;
delete pos;
prev->_next = next;
next->_prev = prev;
}
}
private:
ListNode* _head;
ListNode* _tail;
};