双向循环链表模板类(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;
}