线性表之单链表

#include<iostream>
using namespace std;
template<typename T>struct node{
	T data;
	node<T> *next;
};
template<typename T>class Link{
private:
	node <T> *head;
public: 
	Link()
	{
		head=new node<T>;
		head->next =NULL;
	}
	~Link()
	{
		clearLink();
		delete head;
	}
	void clearLink()
	{
		node<T> *q,*p=head->next;
		head->next=NULL;
		while (p)
		{
			q=p->next;
			delete p;
			p=q;
		}
	}
	bool Empty()
	{
		return head->next==NULL;
	}
	int LinkLength()
	{
		node<T> *p=head->next;
		int i=0;
		while(p)
		{
			i++;
			p=p->next;
		}
		return i;
	}
	bool getElem(int i,T &e)
	{
		node <T> *p=head->next;
		int j=0;
		while(j<i-1 && p)
		{
			j++;
			p=p->next;
		}
		if(j>i-1 || p==NULL)
		{
			return false;
		}
		e=p->data;
		return true;
	}
	bool InsertLink(int i,T e)
	{
		node<T> *s,*p=head;
		int j=0;
		while(p && j<i-1)
		{
			j++;
			p=p->next;
		}
		if(j>i-1 || p==NULL)
		{
			return false;
		}
		s=new node<T>;
		s->data=e;
		s->next=p->next;
		p->next=s;
		return true;
	}
	bool deleteLink(int i,T &e)
	{
		node<T> *q,*p=head;
		int j=0;
		while(p && j<i-1)
		{
			j++;
			p=p->next;
		}
		if(j>i-1 || p==NULL)
		{
			return false;
		}
		q=p->next;
		e=q->data ;
		p->next=q->next;
		return true;
	}
	void print()
	{
		node <T> *p=head->next;
		while(p)
		{
			cout<<p->data<<" ";
			p=p->next;
		}
		cout<<endl;
	}
	template<class T>
	friend ostream & operator <<(ostream &,Link<T>&);
	template <class T>
	friend void MergeLink(Link<T> &,Link<T> &,Link<T> &);
	template <class T>
	friend void MergeLink(Link<T>&,Link<T>&);
};
template<class T>
ostream & operator << (ostream & out,Link<T>& a)
{
	node<T> *p=a.head->next;
	while(p)
	{
		out<<p->data<<" ";
		p=p->next;
	}
	out<<endl;
	return out;
}
template <class T>
void MergeLink(Link<T> &a,Link<T> &b,Link<T> &c)
{
	node<T> *pa=a.head ->next,*pb=b.head ->next,*pc=c.head ;
	T ai,bj;
	int i=1,j=1,k=0;
	while (pa && pb)
	{
		if(pa->data <=pb->data)
		{
			a.getElem (i++,ai);
			c.InsertLink (++k,ai);
			pa=pa->next;
		}
		else{
			b.getElem (j++,bj);
			c.InsertLink (++k,bj);
			pb=pb->next;
		}
	}
		while(pa)
		{
			a.getElem (i++,ai);
			c.InsertLink (++k,ai);
			pa=pa->next;
		}
		while(pb)
		{
			b.getElem (j++,bj);
			c.InsertLink (++k,bj);
			pb=pb->next;
		}
}
template <class T>
void MergeLink(Link<T>&a,Link<T>&b)
{
	node<T> *pa=a.head ->next,*pb=b.head ->next ,*p=a.head ;
	while(pa && pb)
	{
		if(pa->data<=pb->data)
		{
			p->next =pa;
			p=pa;
			pa=pa->next;
		}
		else {
			p->next=pb;
			p=pb;
			pb=pb->next;
		}
	}
	p->next=pa?pa:pb;
              /*
		while(pa)
		{
			p->next =pa;
			p=pa;
			pa=pa->next;
		}
		while(pb)
		{
			p->next=pb;
			p=pb;
			pb=pb->next;
		}
             */
		b.head->next=NULL;
}
int main()
{
	Link<int> La,Lb,Lc;
	cout<<"La是否为空?"<<boolalpha<<La.Empty ();
	cout<<La.LinkLength ();
	for(int i=0;i<5;i++)
		La.InsertLink (i+1,i*2);
	for(int i=0;i<6;i++)
		Lb.InsertLink(i+1,i*3);
	cout<<"La的各个元素是:"<<La;
	cout<<La.LinkLength ();
	cout<<"Lb的各个元素是:"<<Lb;
	cout<<Lb.LinkLength ();
	MergeLink(La,Lb,Lc);
	cout<<"Lc的各个元素是:"<<Lc;
	cout<<Lc.LinkLength ()<<endl;
	MergeLink(La,Lb);
	cout<<"La的各个元素是:"<<La;
	cout<<La.LinkLength ()<<endl;
	return 0;
}