你可以选择用STL....下面是我写的一个双链表，功能不多....
[size=1.5]/*****************************************************************
** HighlightCodeV3.0 software by yzfy(雨中飞燕) http:// **
*****************************************************************/
#ifndef DATASTRUCT_H_
#define DATASTRUCT_H_
#include<cassert>
#include<iostream>
template<typename _Ty>
struct node
{
public:
_Ty value_;
node* next_,*pre_;
node(const _Ty& value): value_(value)
{
pre_ = next_ =0;
}
~node(){ std::cout<<"destory..."<<std::endl;}
} ;
template<typename _Ty,class _Node=node<_Ty> >
class DList
{
typedef _Node* pointer;
typedef _Node const* const_pointer;
typedef _Node& reference;
typedef _Node& const_reference;
public:
DList();
DList(const DList<_Ty,_Node>& source);
DList<_Ty,_Node>& operator=(const DList<_Ty,_Node>& source);
~DList();
bool empty() const { return (head_==0); }
int size() const { return size_; }
pointer begin() const { return head_; }
pointer end() const { return 0; }
void push_front(const _Ty& value);
void push_back(const _Ty& value);
_Ty front() const;
_Ty back() const;
void pop_front();
void pop_back();
void Insert(const _Ty& value,pointer where_);
void Delete(pointer where_);
pointer Find(int pos) const;
void reverse() ;
void print() const
{
for(pointer it=head_;it!=0;it=it->next_ )
std::cout<<it->value_<<" ";
std::cout<<std::endl;
}
private:
pointer allocated() const
{
return static_cast<pointer>(::operator new(sizeof(_Node)));
}
void append(pointer where_,const _Ty& value) const
{
new (where_)_Node(value);
}
void destroy(pointer where_) const
{
where_->~_Node();
::operator delete(where_);
}
pointer link(pointer where_pre,pointer where_,pointer where_suc)
{
where_->pre_ = where_pre;
where_->next_ = where_suc;
if( where_pre ) where_pre->next_ = where_;
if( where_suc ) where_suc->pre_ = where_;
return where_;
}
void Swap(DList<_Ty,_Node>& source)
{
std::swap(head_,source.head_);
std::swap(size_,source.size_);
}
private:
pointer head_;
int size_;
};
// 具体实现
template<typename _Ty,class _Node >
DList<_Ty,_Node>::DList():head_(0),size_(0)
{}
template<typename _Ty,class _Node >
DList<_Ty,_Node>::~DList()
{
for(pointer begin_=head_,current;begin_!=end();)
{
current=begin_;
begin_=begin_->next_;
destroy(current);
}
std::cout<<"this is ....."<<std::endl;
}
template<typename _Ty,class _Node >
DList<_Ty,_Node>::DList(const DList<_Ty,_Node>& source):head_(0),size_(0)
{
typename DList<_Ty,_Node>::pointer begin_=source.begin();
DList<_Ty,_Node> temp;
for(;begin_!=source.end();begin_=begin_->next_)
{
temp.push_back(begin_->value_);
}
Swap(temp);
}
template<typename _Ty,class _Node>
DList<_Ty,_Node>& DList<_Ty,_Node>::operator= (const DList<_Ty,_Node>& source)
{
DList<_Ty,_Node> temp(source);
Swap(temp);
return *this;
}
template<typename _Ty,class _Node >
void DList<_Ty,_Node>::push_front(const _Ty& value)
{
typename DList<_Ty,_Node>::pointer node_=allocated();
append(node_,value);
head_=link(0,node_,head_);
++size_;
}
template<typename _Ty,class _Node >
void DList<_Ty,_Node>::push_back(const _Ty& value)
{
typename DList<_Ty,_Node>::pointer node_=allocated();
append(node_,value);
typename DList<_Ty,_Node>::pointer end_=Find(size_);
if( head_==0 ) head_=node_;
else link(end_->pre_,end_,node_);
++size_;
}
template<typename _Ty,class _Node>
inline _Ty DList<_Ty,_Node>::front() const
{
return head_->value_;
}
template<typename _Ty,class _Node>
inline _Ty DList<_Ty,_Node>::back() const
{
typename DList<_Ty,_Node>::pointer node_=Find(size_);
return node_->value_;
}
template<typename _Ty,class _Node>
void DList<_Ty,_Node>::pop_back()
{
typename DList<_Ty,_Node>::pointer node_p=Find(size_-1);
typename DList<_Ty,_Node>::pointer node_s=Find(size_);
link(node_p->pre_,node_p,0);
destroy(node_s);
head_=--size_?head_:0;
}
template<typename _Ty,class _Node>
void DList<_Ty,_Node>::pop_front()
{
typename DList<_Ty,_Node>::pointer node_=head_;
head_=link(0,head_->next_,head_->next_->next_);
destroy(node_);
head_=--size_?head_:0;
}
template<typename _Ty,class _Node>
void DList<_Ty,_Node>::Insert(const _Ty& value,typename DList<_Ty,_Node>::pointer where_)
{
typename DList<_Ty,_Node>::pointer node_=allocated();
append(node_,value);
if( where_==head_ ) head_=link(where_->pre_,node_,where_);
else link(where_->pre_,node_,where_);
++size_;
}
template<typename _Ty,class _Node>
void DList<_Ty,_Node>::Delete(typename DList<_Ty,_Node>::pointer where_)
{
if( where_==head_ ) head_=link(0,head_->next_,head_->next_->next_);
else link(where_->pre_->pre_,where_->pre_,where_->next_);
destroy(where_);
--size_;
}
template<typename _Ty,class _Node>
typename DList<_Ty,_Node>::pointer DList<_Ty,_Node>::Find(int pos) const
{
assert(pos>=0&&pos<=size_);
typename DList<_Ty,_Node>::pointer node_=head_;
for(;pos>1;--pos) node_=node_->next_;
return node_;
}
template<typename _Ty,class _Node>
void DList<_Ty,_Node>::reverse()
{
typename DList<_Ty,_Node>::pointer end_=Find(size_);
for(typename DList<_Ty,_Node>::pointer x_pre=0,x=end_;end_!=0;)
{
end_=end_->pre_;
x_pre=link(x_pre,x,0);
x=end_;
if(x_pre->pre_==0) head_=x_pre;
}
}
#endif[/size]
