dbllist.h

清华大学计算机系数据结构课程教材《数据结构 用面向对象方法和C++描述》（殷人昆主编）的类库（书中程序的源代码）

#pragma once
#include<iostream>
using namespace std;
template <class T, class E> 
struct DblNode {		//链表结点类定义
	E data;			//链表结点数据
	DblNode<T,E> *rLink, *lLink;	     //前驱、后继指针
	DblNode ( DblNode<T,E> *l = NULL, 
		DblNode<T,E> *r = NULL ) 
	{ lLink = l;  rLink = r; }           //构造函数
	DblNode ( E value, DblNode<T, E> *l = NULL, DblNode<T,E> *r = NULL)
	{ data = value;  lLink = l;  rLink = r; }  //构造函数
};

template <class T, class E>
class DblList {		//链表类定义
public:
	DblList ( E uniqueVal ) {	        //构造函数
		first = new DblNode<T, E> (uniqueVal);
		first->rLink = first->lLink = first;
	};
	DblNode<T, E> *getFirst () const { return first; }
	void setFirst ( DblNode<T, E> *ptr ) { first = ptr; }
	DblNode<T, E> *Locate ( int i, int d );	
	//在链表中定位序号为i(≥0)的结点, d=0按前驱方
	//向,d≠0按后继方向
	DblNode<T, E> *Search ( T x, int d);	
	//在链表中按d指示方向寻找等于给定值x的结点,
	//d=0按前驱方向,d≠0按后继方向
	bool Insert ( int i, E x, int d );
	//在第i个结点后插入一个包含有值x的新结点,d=0
	//按前驱方向,d≠0按后继方向
	bool Remove ( int i, E& x, int d );   //删除第i个结点
	bool IsEmpty() { return first->rlink == first; }
	//判双链表空否
	friend istream& operator >> (istream& in, DblList<T,E>& dbl){
		int size = 0;
		cout<<"请输入双向链表的大小：";
		in>>size;
		E data;
		for (int i = 0; i<size; ++i){
			cout<<"请输入结点数据："<<endl;
			in>>data;
			dbl.Insert(i, data, 1);
		}
		return in;
	}

	friend ostream & operator <<(ostream& out, DblList <T,E> & dbl){
		DblNode <T,E> *p= dbl.first -> rLink;
		while (p!=dbl.first){
			out<<p->data << "  ";
			p=p->rLink;
		}
		cout<<endl;
		return out;
	}

private:
	DblNode<T, E> *first;                 //表头指针
};

template<class T,class E>
DblNode<T, E> *DblList<T,E>:: Locate ( int i, int d ){
	if (i==0) return first;
	DblNode<T,E> *current = (d == 0)?first->lLink : first->rLink;   //按d确定搜索方向
	while ( current != first  && --i > 0 ) 	current = (d == 0) ? 
		current->lLink : current->rLink;
	if ( current != first ) return current;	   //搜索成功
	else return NULL;			   //搜索失败
};

template <class T, class E>
DblNode<T, E> *DblList<T, E>::Search (T x, int d) {
	//在双向循环链表中寻找其值等于x的结点。
	DblNode<T,E> *current = (d == 0)?
		first->lLink : first->rLink;   //按d确定搜索方向
	while ( current != first && current->data != x )	current = (d == 0) ? 
		current->lLink : current->rLink;
	if ( current != first ) return current;	   //搜索成功
	else return NULL;			   //搜索失败
};
template <class T, class E>
bool DblList<T, E>::Insert ( int i, E x, int d ) {
	//建立一个包含有值x的新结点, 并将其按 d 指定的
	//方向插入到第i个结点之后。
	DblNode<T, E> *current = Locate(i, d);
	//按d指示方向查找第i个结点
	if ( current == NULL ) return false;    //插入失败
	DblNode<T,E> *newNd = new DblNode<T,E>(x);
	if (d == 0) {	  //前驱方向:插在第i个结点左侧
		newNd->lLink = current->lLink; //链入lLink链
		current->lLink = newNd;
		newNd->lLink->rLink = newNd;  //链入rLink链
		newNd->rLink = current;
	} else {		     //后继方向:插在第i个结点后面
		newNd->rLink = current->rLink;  //链入rLink链
		current->rLink = newNd;
		newNd->rLink->lLink = newNd;   //链入lLink链
		newNd->lLink = current;
	}
	return true; 	    //插入成功
}; 
template <class T, class E>
bool DblList<T, E>::Remove( int i, E& x, int d ) {
	//在双向循环链表中按d所指方向删除第i个结点。
	DblNode<T, E> *current = Locate (i, d);
	if (current == NULL) return false; 	      //删除失败
	current->rLink->lLink = current->lLink;
	current->lLink->rLink = current->rLink;	
	//从lLink链和rLink链中摘下
	x = current->data;  delete current; 	     //删除
	return true; 			               //删除成功
};