dblist.h

纯粹是学习专用～

#include<iostream.h>
#include<string.h>
class Reader;
template<typename T> class DblList;
template<typename T> class DblNode{

	T Info;//数据域
	DblNode<T> *llink,*rlink;    //前驱（左链）、后继（右链）指针
public:
	DblNode(T data);//一般结点
	DblNode();//头结点
	T GetInfo(){return Info;};
	friend class DblList<T>;
	friend class Library;
};

template<typename T>class DblList{
	DblNode<T> *head,*current;
public:
	DblList();
	~DblList();
	void Insert(const T&  data);
	DblNode<T>* Remove(DblNode<T>* p);
	void Print();
	int Length();//计算链表长度
	DblNode<T> *Find(T  data);//搜索数据与定值相同的结点
	DblNode<T>* Find(int data);//按某个关键字查找
	void MakeEmpty();	//清空链表
	void ShowList();	//显示链表各结点
	//其它操作
};


template<typename T> DblNode<T>::DblNode(){
	llink=rlink=NULL;
}
template<typename T> DblNode<T>::DblNode(T data){
	info=data;
	llink=NULL;
	rlink=NULL;
}


template<typename T> DblList<T>::DblList(){//建立表头结点
	head=new DblNode<T>();
	head->rlink=head->llink=head;
	current=NULL;
}
template<typename T> DblList<T>::~DblList(){
	MakeEmpty();//清空链表
	delete head;
}
template<typename T> void DblList<T>::MakeEmpty(){
	DblNode<T> *tempP;
	while(head->rlink!=head){
		tempP=head->rlink;
		head->rlink=tempP->rlink;//把头结点后的第一个节点从链中脱离
		tempP->rlink->llink=head;//处理左指针
		delete tempP;           //删除(释放)脱离下来的结点
	}
	current=NULL;  //current指针恢复
}
template<typename T> void DblList<T>::Insert(const T & data){//新节点在链尾
	current=new DblNode<T>;
	current->Info=data;
	current->rlink=head;//注意次序
	current->llink=head->llink;
	head->llink->rlink=current;
	head->llink=current;//最后做
}
template<typename T> DblNode<T>* DblList<T>::Remove(DblNode<T>* p){
	current=head->rlink;
	while(current!=head&&current!=p) current=current->rlink;
	if(current==head) current=NULL;
	else{//结点摘下
		p->llink->rlink=p->rlink;
		p->rlink->llink=p->llink;
		p->rlink=p->llink=NULL;
	}
	return current;
}

template<typename T> DblNode<T>* DblList<T>::Find(T data){
	current=head->rlink;
	while(current!=head&&current->Info!=data) current=current->rlink;
	if(current==head) current=NULL;
	return current;
}

template<typename T> DblNode<T>* DblList<T>::Find(int data){
	current=head->rlink;
	int temp =current->Info.GetCode();
	while(current!=head&&temp!=data){
		current=current->rlink;
		temp =  current->Info.GetCode();
	}
	if(current==head) current=NULL;
	return current;
}

template<typename T> void DblList<T>::Print(){
	current=head->rlink;
	while(current!=head){
		cout<<current->Info<<'\t';
		current=current->rlink;
	}
	cout<<endl;
}
template<typename T> int DblList<T>::Length(){
	int count=0;
	current=head->rlink;
	while(current!=head){
		count++;
		current=current->rlink;
	}
	return count;
}

template<typename T> void DblList<T>::ShowList(){
	int count=0;
	current=head->rlink;
	while(current!=head){
		current->GetInfo().Show();
		current=current->rlink;
	}
	return ;
}