双链表.cpp

用C++编写的《算法与程序设计》（王晓东版）的书中的数据结构类（全集）

template<class T>
class DNode{
	friend Double<T>;
	private:
		T data;
		DNode<T> *left,*right;
}
template<class T>
class Double{
	public:
		Double(){LeftEnd=RightEnd=0;};
		~Double();
		bool Empty() const {return n==0;}
		int Length() const {return n;}
		bool Retrieve(int k,T& x) const;
		int Locate(const T& x) const;
		Double<T>& Insert(int k,const T& x);
		Double<T>& Delete(int k,T& x);
		void PrintList(ostream & out) const;
	private:
		int n;
		DNode<T> *LeftEnd, *RightEnd;
}
template<class T>
class Double{
	public:
		Double();
		~Double();
		bool Empty() const {return n==0;}
		int Length() const{return n;}
		bool Retrieve(int k,T& x) const;
		int Locate(const T& x) const;
		Double<T>& Insert(int k,const T& x);
		Double<T>& Delete(int k, T& x);
		void PrintList(ostream & out) const;
	private:
		int n;
		DNode<T> * header;
}
template<class T>
Double<T>::Double()
{
	DNode<T> *y=new DNode<T>;
	y->left=y;
	header=y;
	n=0;
}
template<class T>
Double<T>::~Double()
{
	DNode<T> *current;
	DNode<T> *next;
	current=header->right;
	while(!Empty()){
		next=current->right;
		delete current;
		n--;
		current=next;
	}
	delete header;
}
template<class T>
bool Double<T>::Retrieve(int k,T& x) const
{ 
	if(k<1||k>n) return false;
	DNode<T> *current=header->right;
	int index=1;
	while(index<k){
	  current=current->right;
	  index++;
	}
	x=current->data;
	return true;
}
template<class T>
int Double<T>::Locate(const T& x) const
{
	DNode<T> *current=header->right;
	int index=1;
	header->data=x;
	while(current->data!=x){
		current=current->right;
		index++;
	}
	return((current==header)?0:index);
}
template<class T>
Double<T> & Double<T>::Insert(int k,const T& x)
{
	if(k<0||k>n) throw OutOfBounds();
	//搜索第K个元素
	DNode<T> *p=header->right;
	for(int index=1;index<k;index++)
		p=p->right;
	//插入新元素
	DNode<T> *y=new DNode<T>;
	y->data=x;
	y->left=p;
	y->right=p->right;
	p->right->left=y;
	p->right=y;
	n++;
	return *this;
}
template<class T>
Double<T>& Double<T>::Delete(int k,T& x)
{
	if(k<1||k>n) throw OutOfBounds();
	//搜索第K个元素
	DNode<T> *q=header->right;
	for(int index=1;index<k;index++)
		q=q->right;
	//修改指针，实施删除
	q->left->right=q->right;
	q->right->left=q->left;
	x=q->data;
	delete q;
	n--;
	return *this;
}
template<class T>
void Double<T>::PrintList(ostrean & out) const
{
	DNode<T> *current;
	for(current=header->right;current!=header;current=current->right)
		out<<current->data<<" ";
}