- #include<iostream>
- using namespace std;
- template<typename T>struct node{
- T data;
- node<T> *prior,*next;
- };
- template <typename T> class nLink
- {
- private:
- node<T> *head;
- public:
- nLink()
- {
- head=NULL;
- }
- ~nLink()
- {
- clearLink();
- }
- void clearLink()
- {
- node<T> *p=head;
- if(p!=NULL)
- {
- p->prior->next=NULL;
- do{
- p=p->next;
- delete head;
- head=p;
- }
- while (p!=NULL);
- }
- }
- bool empty()
- {
- return head==NULL;
- }
- int linkLength()
- {
- node<T> *p=head;
- int i=1;
- while (p->next!=head)
- {
- i++;
- p=p->next;
- }
- return i;
- }
- node<T> *getAddress(int i)
- {
- node <T> *p=head;
- int j=1;
- if(i<1 || head ==NULL)
- return NULL;
- else {
- if(i==1)
- return p;
- do {
- j++;
- p=p->next;
- }while(p!=head && j<i);
- if(p==head)
- {
- return NULL;
- }
- else return p;
- }
- }
- bool getElem(int i,T &e)
- {
- node<T> *p;
- if(!getAddress(i))
- return false;
- else {
- p=getAddress(i);
- e=p->data;
- return true;
- }
- }
- bool Insert(int i,T e)
- {
- node<T> *s,*p=getAddress(i-1);
- s=new node<T>;
- s->data=e;
- if(i==1)
- {
- if(head==NULL)
- {
- s->prior=s->next=s;
- }
- else {
- s->next=head;
- s->prior=head->prior;
- s->next->prior=s;
- s->next->prior=s;
- }
- head=s;
- return true;
- }
- else {
- if(p==NULL)
- return false;
- else {
- s->next=p->next;
- s->prior=p;
- s->next->prior=s;
- p->next=s;
- return true;
- }
- }
- }
- bool deleteElem(int i,T &e)
- {
- node<T> *p=getAddress(i);
- if(p==NULL)
- return false;
- e=p->data;
- if(p->next==p)
- {
- head=NULL;
- }
- else {
- p->prior->next=p->next;
- p->next->prior=p->prior;
- if(p==head)
- head=p->next;
- }
- delete p;
- return true;
- }
- void print()
- {
- node<T> *p=head;
- if(p!=NULL)
- do{
- cout<<p->data<<" ";
- p=p->next;
- }while(p!=head);
- cout<<endl;
- }
- template <class T>
- friend ostream & operator <<(ostream &,nLink<T> &);
- template <class T>
- friend void MergeLink(nLink<T> &,nLink<T> &);
- };
- template <class T>
- ostream & operator <<(ostream &out,nLink<T> &a)
- {
- node<T> *p=a.head;
- if(p!=NULL)
- {
- do{
- out<<p->data<<" ";
- p=p->next;
- }while(p!=a.head);
- }
- out<<endl;
- return out;
- }
- template <class T>
- void MergeLink(nLink<T> &a,nLink<T> &b)
- {
- node<T> *pa,*pb,*p,*t;
- pa=a.head;
- pb=b.head;
- p=new node<T>;
- t=p;
- if(pa)
- pa->prior->next=NULL;
- if(pb)
- pb->prior->next=NULL;
- while(pa && pb)
- {
- 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)
- {
- p->next=pa;
- pa->prior=p;
- p=pa;
- pa=pa->next;
- }
- while (pb)
- {
- p->next=pb;
- pb->prior=p;
- p=pb;
- pb=pb->next;
- }
- p->next=t->next;
- t->next->prior=p;
- a.head=p->next;
- b.head=NULL;
- }
- int main()
- {
- nLink<int > La,Lb;
- cout<<"La是否为空?"<<boolalpha<<La.empty ()<<endl;
- for(int i=1;i<4;i++)
- {
- La.Insert(i,i);
- }
- cout<<La;
- for(int i=1;i<4;i++)
- {
- Lb.Insert(i,i+1);
- }
- cout<<Lb;
- MergeLink(La,Lb);
- cout<<La;
- cout<<Lb;
- return 0;
- }
- //该片段来自于http://www.codesnippet.cn/detail/200620134184.html
来源: http://www.codesnippet.cn/detail/200620134184.html