当前位置: 编程技术>c/c++/嵌入式
C++ 模版双向链表的实现详解
来源: 互联网 发布时间:2014-10-17
本文导语: 代码如下所示: 代码如下:#include template class double_linked{ struct node { T data; node* prev; node* next; node(T t, node* p, node* n) : data(t), prev(p), next(n) {} }; node* head; node* tail;public...
代码如下所示:
#include
template
class double_linked
{
struct node
{
T data;
node* prev;
node* next;
node(T t, node* p, node* n) : data(t), prev(p), next(n) {}
};
node* head;
node* tail;
public:
double_linked() : head( NULL ), tail ( NULL ) {}
template
double_linked( T (&arr) [N]) : head( NULL ), tail ( NULL )
{
for( int i(0); i != N; ++i)
push_back(arr[i]);
}
bool empty() const { return ( !head || !tail ); }
operator bool() const { return !empty(); }
void push_back(T);
void push_front(T);
T pop_back();
T pop_front();
~double_linked()
{
while(head)
{
node* temp(head);
head=head->next;
delete temp;
}
}
};
template
void double_linked::push_back(T data)
{
tail = new node(data, tail, NULL);
if( tail->prev )
tail->prev->next = tail;
if( empty() )
head = tail;
}
template
void double_linked::push_front(T data)
{
head = new node(data, NULL, head);
if( head->next )
head->next->prev = head;
if( empty() )
tail = head;
}
template
T double_linked::pop_back()
{
if( empty() )
throw("double_linked : list empty");
node* temp(tail);
T data( tail->data );
tail = tail->prev ;
if( tail )
tail->next = NULL;
else
head = NULL ;
delete temp;
return data;
}
template
T double_linked::pop_front()
{
if( empty() )
throw("double_linked : list empty");
node* temp(head);
T data( head->data );
head = head->next ;
if( head )
head->prev = NULL;
else
tail = NULL;
delete temp;
return data;
}
int main()
{
int arr[] = { 4, 6, 8, 32, 19 } ;
double_linked dlist ( arr );
dlist.push_back( 11 );
dlist.push_front( 100 );
while( dlist )
std::cout
代码如下:
#include
template
class double_linked
{
struct node
{
T data;
node* prev;
node* next;
node(T t, node* p, node* n) : data(t), prev(p), next(n) {}
};
node* head;
node* tail;
public:
double_linked() : head( NULL ), tail ( NULL ) {}
template
double_linked( T (&arr) [N]) : head( NULL ), tail ( NULL )
{
for( int i(0); i != N; ++i)
push_back(arr[i]);
}
bool empty() const { return ( !head || !tail ); }
operator bool() const { return !empty(); }
void push_back(T);
void push_front(T);
T pop_back();
T pop_front();
~double_linked()
{
while(head)
{
node* temp(head);
head=head->next;
delete temp;
}
}
};
template
void double_linked::push_back(T data)
{
tail = new node(data, tail, NULL);
if( tail->prev )
tail->prev->next = tail;
if( empty() )
head = tail;
}
template
void double_linked::push_front(T data)
{
head = new node(data, NULL, head);
if( head->next )
head->next->prev = head;
if( empty() )
tail = head;
}
template
T double_linked::pop_back()
{
if( empty() )
throw("double_linked : list empty");
node* temp(tail);
T data( tail->data );
tail = tail->prev ;
if( tail )
tail->next = NULL;
else
head = NULL ;
delete temp;
return data;
}
template
T double_linked::pop_front()
{
if( empty() )
throw("double_linked : list empty");
node* temp(head);
T data( head->data );
head = head->next ;
if( head )
head->prev = NULL;
else
tail = NULL;
delete temp;
return data;
}
int main()
{
int arr[] = { 4, 6, 8, 32, 19 } ;
double_linked dlist ( arr );
dlist.push_back( 11 );
dlist.push_front( 100 );
while( dlist )
std::cout