线性表之双向循环链表

#include<iostream>
using namespace std;
template<typename T>struct node{
T data;
node<T> *prior,*next;
};
template<typename T> class DLink{
private:
	node<T> *head;
public:
	DLink()
	{
		head=new node<T>;
		head->next=head->prior=head;
	}
	~DLink()
	{
		clearLink();
		delete head;
	}
	void clearLink()
	{
		node<T> *p=head->next;
		while(p!=head)
		{
			p=p->next;
			delete p->prior;
		}
		head->prior=head->next=head;
	}
	bool empty()
	{
		return head->next==head;
	}
	int linkLength()
	{
		node<T> *p=head->next;
		int i=0;
		while(p!=head)
		{
			i++;
			p=p->next;
		}
		return i;
	}
	bool getElem(int i,T &e)
	{
		if(i<1 || i>linkLength())
			return false;
		node <T> *p=head->next;
		int j=1;
		while(j<i)
		{
			j++;
			p=p->next;
		}
		e=p->data;
		return true;
	}
	bool Insert(int i,T e)
	{
		if(i<1 || i> linkLength()+1)
			return false;
		node<T> *s,*p=head;
		int j=0;
		s=new node<T>;
		s->data=e;
		while(j<i-1)
		{
			j++;
			p=p->next;	
		}
		s->next=p->next;
		s->prior=p;
		p->next->prior=s;
		p->next=s;
		return true;
	}
	bool Delete(int i,T &e)
	{
		if(i<1 || i>linkLength())
			return false;
		node<T> *p=head->next;
		int j=0;
		while(j<i-1)
		{
			j++;
			p=p->next;
		}
		p->prior->next=p->next;
		p->next->prior=p->prior;
		delete p;
		return true;
	}
	void print()
	{
		node<T> *p=head->next;
		while(p!=head)
		{
			cout<<p->data<<" ";
			p=p->next;
		}
		cout<<endl;
	}
	template<class T>
	friend ostream & operator <<(ostream &,DLink<T> &);
	template<class T>
	friend void MergeLink(DLink<T>&,DLink<T>&);
	template<class T>
	friend void MergeLink(DLink<T>&,DLink<T>&,DLink<T>&);
};

	template<class T>
    ostream & operator <<(ostream & out ,DLink<T> & a)
	{
		node<T> *p=a.head->next;
		while(p!=a.head)
		{
			out<<p->data<<" ";
			p=p->next;
		}
		out<<endl;
		return out;
	}
	template<class T>
	void MergeLink(DLink<T>&a,DLink<T>&b)
	{
		node<T>*pa,*pb,*p;
		pa=a.head->next;
		pb=b.head->next;
		p=a.head;
		while(pa!=a.head && pb!=b.head)
		{
			if(pa->data<=pb->data)
			{
				p->next=pa;
				pa->prior=p;
				p=pa;
				pa=pa->next;

			}
			else {
				p->next=pb;
				pb->prior=p;
				p=pb;
				pb=pb->next;
			}
		}
		while(pa!=a.head)
		{
			p->next=pa;
			pa->prior=p;
			p=pa;
			pa=pa->next;
		}
		while(pb!=b.head)
		{
			p->next=pb;
			pb->prior=p;
			p=pb;
			pb=pb->next;
		}
		p->next=a.head;
		a.head->prior=p;
		b.head->next=b.head->prior=b.head;
	}
	template<class T>
	void MergeLink(DLink<T>&a,DLink<T>&b,DLink<T>&c)
	{
		node<T> *pa,*pb,*p;
		pa=a.head->next;
		pb=b.head->next;
		int i=1,j=1,k=0;
		T ai,bj;
		while(pa!=a.head && pb!=b.head)
		{
			a.getElem(i,ai);
			b.getElem(j,bj);
			if(ai<=bj)
			{
				c.Insert(++k,ai);
				i++;
				pa=pa->next;
			}
			else {
				c.Insert(++k,bj);
					j++;
					pb=pb->next;
			}
		}
		while(pa!=a.head)
		{
			a.getElem(i++,ai);
			pa=pa->next;
			c.Insert(++k,ai);
		}
		while(pb!=b.head)
		{
			b.getElem(j++,bj);
			pb=pb->next;
			c.Insert(++k,bj);
		}
	}
int main()
{
	DLink<int> La,Lb,Lc;
	cout<<boolalpha<<La.empty()<<endl;
	for(int i=1;i<4;i++)
		La.Insert(i,i);
	for(int i=1;i<4;i++)
		Lb.Insert(i,i+1);
	//cout<<boolalpha<<La.empty()<<endl;
	//La.print();
	//cout<<La<<"链表La的长度是:"<<La.linkLength()<<endl;
	//cout<<Lb<<"链表的Lb长度是:"<<Lb.linkLength()<<endl;
	//cout<<"链表的长度是:"<<La.linkLength()<<endl;
	int e;
	for(int i=1;i<5;i++)
	{
		La.getElem(i,e);
		cout<<e<<" ";
	}
	cout<<endl;
	while(!La.empty())
		{
			La.Delete(La.linkLength(),e);
			La.print();
		}
	//MergeLink(La,Lb);
	MergeLink(La,Lb,Lc);
	cout<<La<<"链表La的长度是:"<<La.linkLength()<<endl;
	cout<<Lb<<"链表的Lb长度是:"<<Lb.linkLength()<<endl;
	cout<<Lc<<"链表的Lc长度是:"<<Lc.linkLength()<<endl;
	return 0;
}