双向循环链表模板类(C++)

//header.h
#include<iostream>
using namespace std;
/*
* 双向循环链表头文件，
* 其声明中封装有指向链表附加头节点的头x指针first
*/template<class T>
struct DbNode
{
T data;
DbNode<T> *pred, *next;
DbNode(T value, DbNode<T> *a = NULL, DbNode<T> *b = NULL):\
data(value), pred(a), next(b){}
DbNode(DbNode<T> *a = NULL, DbNode<T> *b = NULL):pred(a), next(b){}
};template<class T>
class Dblist
{
private: DbNode<T> *first;
public:
Dblist(T value);
~Dblist(){makeEmpty();}
void makeEmpty();
int Length()const;
bool IsEmpty(){return (this->first->pred == this->pred);}
DbNode<T> *getHead()const{return this->first;}
DbNode<T> *Locate(int i, int d);
DbNode<T> *Search(const T& x);
bool Insert(int i, const T& x, int d);
bool Remove(int i, T& x, int d);
void Print(int d);
};
template<class T>
int Dblist<T>::Length()const
{
DbNode<T> *tmp = this->first;
int i = 1;
while(tmp->next!=this->first)
{
++i;
tmp = tmp->next;
}
return i;
}
template<class T>
bool Dblist<T>::Remove(int i, T& x, int d)
{
DbNode<T> *p = this->Locate(i, d);
if(!p)
return false;
x = p->data;
if(p==this->first && this->Length()>1)
this->first = p->next;
else
cout<<"仅有头节点的双向循环链表已被删除！请勿在没添加新元素前对其调用。"<<endl;
p->pred->next = p->next;
p->next->pred = p->pred;
delete p;
return true;
}
template<class T>
DbNode<T>* Dblist<T>::Search(const T& x)
{
DbNode<T> *tmp = this->first;
do
{
if(tmp->data==x)
{
cout<<"address of x is "<<tmp<<" x = "<<tmp->data<<endl;
return tmp;
}
tmp = tmp->pred;
}while(tmp!=this->first);
return NULL;
}
template<class T>//定位元素，d=0时从头节点向前(pred)查第i个元素，d!=0时，从头节点向后(next)找第i个元素
DbNode<T>* Dblist<T>::Locate(int i, int d)
{
if(this->first->next==this->first || i==0)
return this->first;
int t = 1;
DbNode<T>* tmp = this->first;
if(d)//向后找
{
while(tmp->next!=this->first && t!=i)//查找到的条件为，在没把双向循环链表遍历一遍前，t=i
{
tmp = tmp->next;
++t;
}
if(tmp->next==this->first&&t!=i)
return NULL;
else
return tmp;}
else//向前找
{
while(tmp->pred!=this->first && t!=i)
{
tmp = tmp->pred;
++t;
}
if(tmp->pred==this->first&&t!=i)
return NULL;
else
return tmp;
}
}
template<class T>
bool Dblist<T>::Insert(int i, const T& x, int d)
{
DbNode<T> *p = this->Locate(i, d);
if(!p)
return false;
DbNode<T> *newnode = new DbNode<T>;
if(newnode==NULL)
{
cout<<"申请内存错误！"<<endl;
exit(1);
}
newnode->data = x;
if(d)//p节点后插入
{
p->next->pred = newnode;
newnode->pred = p;
newnode->next = p->next;
p->next = newnode;
}
else//p节点前插入
{
p->pred->next = newnode;
newnode->next = p;
newnode->pred = p->pred;
p->pred = newnode;
}
return true;
}
template<class T>
void Dblist<T>::makeEmpty()
{
DbNode<T> *p, *q = this->first->pred;
while(q != this->first)
{
p = q;
q = q->pred;
delete p;
}
}
template<class T>
void Dblist<T>::Print(int d)
{
if(d)//正序打印
{
cout<<"Positive order: ";
DbNode<T> *tmp = this->first;
while(tmp->next != this->first)
{
cout<<tmp->data<<"->";
tmp = tmp->next;
}
cout<<tmp->data<<"->over."<<endl;}
else//逆序打印
{
DbNode<T> *tmp = this->first;
cout<<"Reverse sequence: ";
while(tmp->pred != this->first)
{
cout<<tmp->data<<"->";
tmp = tmp->pred;
}
cout<<tmp->data<<"->over."<<endl;
}
}template<class T>
Dblist<T>::Dblist(T value)
{
this->first = new DbNode<T>(value);
if(this->first == NULL)
{
cerr<<"内存分配错误！"<<endl;
exit(1);
}
this->first->next = this->first->pred = this->first;
}

//main.cpp
#include"header.h"int main()
{
Dblist<int> dl(888);
dl.Print(0);
for(int i=1; i<=4; ++i)
{
dl.Insert(1, i, 0);
}
dl.Print(1);
int l = 999, k = 0;
dl.Insert(0, l, 0);
//int k = 0;
dl.Print(1);
dl.Remove(0, k, 0);
dl.Print(1);
k = 5;
dl.Search(k);
dl.Print(0);
return 0;
}