线性表之单循环链表

#include<iostream>
using namespace std;
template<typename T>struct node{
	T data;
	node<T> *next;
};
template <typename T>class TList{
private:
	node<T> *tail;
public:
	TList()
	{
		tail=new node<T>;
		tail->next=tail;
	}
	~TList()
	{
		clearList();
	}
	void clearList()
	{
		node<T> *q,*p,*t;
		q=tail->next;
		p=tail->next->next;
		while(p!=q)
		{
			t=p->next;
			delete p;
			p=t;
		}
	tail->next=tail;
	}
	bool empty()
	{
		return tail->next==tail;
	}
	int ListLength()
	{
		node<T> *p=tail->next;
		int i=0;
		while(p!=tail)
		{
			i++;
			p=p->next;
		}
		return i;
	}
	bool getElem(int i,T &e)
	{
		node<T> *p=tail->next->next;
		int j=0;
		if(i<0 || i>ListLength())
			return false;
		while(j<i-1)
		{
			j++;
			p=p->next;
		}
		e=p->data;
		return true;
	}
	bool Insert(int i,T e)
	{
		node<T> *s,*p=tail->next;
		int j=0;
		if(i<1 || i>ListLength()+1)
			return false;
		while(j<i-1)
		{
			j++;
			p=p->next;
		}
		s=new node<T>;
		s->data=e;
		s->next=p->next;
		p->next=s;
		if(p==tail)
			tail=s;
		return true;
	}
	bool DeleteList(int i,T &e)
	{
		node<T> *q,*p=tail->next;
		int j=0;
		if(i<=0 || i>ListLength())
			return false;
		while(j<i-1)
		{
			j++;
			p=p->next;
		}
		q=p->next;
		p->next=q->next;
		e=q->data;
		if(tail==q)
			tail=p;
		delete q;
		return true;
	}
	void print()
	{
		node<T> *p=tail->next->next;
		while(p!=tail->next)
		{
			cout<<p->data<<" ";
			p=p->next;
		}
		cout<<endl;
	}
	template<class T>
	friend ostream &operator << (ostream &,TList<T> & );
	template<class T>
	friend void MergeList(TList <T>&,TList<T> &);
	template<class T>
	friend void MergeList(TList <T>&,TList<T> &,TList <T> &);
};
template<class T>
ostream & operator << (ostream & out,TList<T> & a )
{
	node<T> *p=a.tail->next->next;
		while(p!=a.tail->next)
		{
			out<<p->data<<" ";
			p=p->next;
		}
		out<<endl;
		return out;
}
template<class T>
	void MergeList(TList <T>&a,TList<T> &b)
	{
		node<T> *pa,*pb,*p;
		pa=a.tail->next->next;
		pb=b.tail ->next->next;
		p=a.tail->next;
		while(pa!=a.tail->next && pb!=b.tail->next)
		{
			if(pa->data <= pb->data)
			{
				p->next=pa;
				p=pa;
				pa=pa->next;
			}
			else{
				p->next=pb;
				p=pb;
				pb=pb->next;
			}
		}
	    while(pa!=a.tail->next)
		{
			p->next=pa;
				p=pa;
				pa=pa->next;
		}
		while(pb!=b.tail->next)
		{
			p->next=pb;
				p=pb;
				pb=pb->next;
		}
		p->next=pa;
		a.tail=p;
		b.tail=pb;
		b.tail->next=b.tail;
	}
	template<class T>
	void MergeList(TList <T>&a,TList<T> &b,TList <T> &c)
	{
		node<T> *pa,*pb,*pc;
		int i=1,j=1,k=0;
		T ai,bj;
		pa=a.tail->next->next;
		pb=b.tail->next->next;
		pc=c.tail->next;
		while(pa!=a.tail->next && pb!=b.tail->next)
		{
			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.tail->next)
		{
			a.getElem(i++,ai);
			c.Insert(++k,ai);
			pa=pa->next;
		}
		while(pb!=b.tail->next)
		{
			b.getElem(j++,bj);
			c.Insert(++k,bj);
			pb=pb->next;
		}
	}
int main()
{
	TList<int > La,Lb,Lc;
	for(int i=1;i<4;i++)
	La.Insert (i,i);
	for(int i=1;i<4;i++)
	Lb.Insert (i,i*2);
	cout<<La;
          cout<<Lb;
          MergeList(La,Lb,Lc);
          MergeList(La,Lb);
          cout<<La;
          cout<<Lb;
          cout<<Lc;
	return 0;
}