双向链表

//头文件
#ifndef _DOUBLE_LINKED_LIST_H
#define _DOUBLE_LINKED_LIST_H
#include
using namespace std;
template
class dblist
{//头结点可用但删不去，删除操作中会被忽略
struct dbnode
{
dbnode*left,*right;
T value;
dbnode(){}
dbnode(const T&x):value(x){}
};
dbnode*head;
bool _insert(dbnode*it,const T&x);
void _delete(dbnode*&it);
public:
class iterator
{//内嵌迭代器，可实现操作：（前后）自增，（前后）自减，解除引用并且赋值,==,!=
dbnode*iter;
public:
iterator(){}
iterator(dbnode*it):iter(it){}
iterator(iterator&it):iter(it.iter){}
void operator++(){iter=iter->right;}
void operator++(int){iter=iter->right;}
void operator--(){iter=iter->left;}
void operator--(int){iter=iter->left;}
T&operator*(){return iter->value;}
dbnode*&operator=(dbnode*it){iter=it;return iter;}
dbnode*&operator=(iterator&it){iter=it.iter;return iter;}
bool operator==(dbnode*it){return it==iter;}
bool operator==(iterator&it){return iter==it.iter;}
bool operator!=(dbnode*it){return it!=iter;}
bool operator!=(iterator&it){return iter!=it.iter;}
friend class dblist;
};
dblist(){head=new dbnode;if(!head){cerr<<"内存分配失败"<left=head->right=head;}
dblist(dblist&L);
~dblist(){clear();delete head;}
int length();//元素个数
dbnode*begin(){return head->right;}
dbnode*end(){return head;}
dbnode*locate(int i);//定位于第i个元素
dbnode*search(const T&x);//定位于第1个值为x的元素
bool empty(){return head->left==head;}
bool push_front(const T&x){return _insert(head,x);}//把元素插入头部
bool push_back(const T&x){return _insert(head->left,x);}//把元素插入尾部
bool insert(iterator it,const T&x);//迭代器it之后插入x
bool insert(int i,const T&x);//第i个元素之后插入x
void remove(int i);
void remove(iterator it);
void erase(const T&x);//删除值为x的全部元素
void erase(iterator first,iterator last);//删除[first,last)的元素
void clear();
void sort();//递增排序
};
template
bool dblist::_insert(dbnode*it,const T&x)
{
dbnode*p=new dbnode(x);
if(!p)return false;
p->left=it;
p->right=it->right;
it->right->left=p;
it->right=p;
return true;
}
template
void dblist::_delete(dbnode*&it)
{
if(it==head)return;
it->left->right=it->right;
it->right->left=it->left;
delete it;
}
template
dblist::dblist(dblist&L)
{
head=new dbnode;
head->right=head->left=head;
dbnode*p=L.head->right,*newnode;
for(;p!=L.head;p=p->right)
{
newnode=new dbnode(p->value);
if(!newnode){cerr<<"内存分配失败"< newnode->left=head->left;
newnode->right=head;
head->left->right=newnode;
head->left=newnode;
}
}
template
int dblist::length()
{
dbnode*p=head->right;
int count=0;
for(;p!=head;p=p->right,count++);
return count;
}
template
dblist::dbnode*dblist::locate(int i)
{
dbnode*p=head;
for(;i>0;i--)
p=p->right;
return p;
}
template
dblist::dbnode*dblist::search(const T&x)
{
dbnode*p=head->right;
for(;p->value!=x&&p!=head;p=p->right);
return p;
}
template
bool dblist::insert(iterator it,const T&x)
{return _insert(it.iter,x);}
template
bool dblist::insert(int i,const T&x)
{
dbnode*p=head;
for(;i>0;i--)
p=p->right;
return _insert(p,x);
}
template
void dblist::remove(iterator it)
{
_delete(it.iter);
}
template
void dblist::remove(int i)
{
dbnode*p=head;
for(;i>0;i--)
p=p->right;
_delete(p);
}
template
void dblist::erase(const T&x)
{
dbnode*p=head->right,*q;
while(p!=head)
{
q=p;
p=p->right;
if(q->value==x)
_delete(q);
}
}
template
void dblist::erase(iterator first,iterator last)
{
iterator p;
while(first!=last)
{
p=first;
first++;
_delete(p.iter);
}
}
template
void dblist::clear()
{
dbnode*p=head->right;
for(p=p->right;p!=head->right;p=p->right)
delete p->left;
head->right=head->left=head;
}
template
void dblist::sort()
{
dbnode*p;
T temp;
bool t=head->right->right==head ? false:true;
while(t)
{
t=false;
p=head->right;
while(p->right!=head)
{
if(p->value>p->right->value)
{
t=true;
temp=p->value;
p->value=p->right->value;
p->right->value=temp;
}
p=p->right;
}
}
}
#endif

//测试程序
#include"双向循环链表类的常用实现.h"
#include
using namespace std;
int main()
{
dblistdb;
cout< dblist::iterator it1(db.begin());
int i;
for(i=0;i<10;i++)
db.push_back(i);
for(;i<20;i++)
db.push_front(i);
for(it1=db.begin();it1!=db.end();it1++)
cout<<*it1<<" ";
cout< dblistaaa(db);
aaa.sort();
for(dblist::iterator it2(aaa.end());it2!=aaa.begin();it2--)
cout<<*it2<<" ";
cout< it2=aaa.locate(10);
*it2=3;it2++;aaa.erase(3);
aaa.insert(it2,58);aaa.remove(it2);
aaa.remove(3);
for(it1=aaa.begin();it1!=aaa.end();it1++)
cout<<*it1<<" ";
cout< cout< it1=aaa.begin();it2=aaa.end();
aaa.clear();
cout< return 0;
}

已经发过去了。。。。