- #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;
- }
- //该片段来自于http://www.codesnippet.cn/detail/190620134145.html
来源: http://www.codesnippet.cn/detail/190620134145.html