例2_7.cpp

《数据结构（C++描述）》-李根强-源代码

//两个升序链表合并
#include<iostream.h> 
struct link
{   int data; //元素类型
 link     *next;   //指针类型,存放下一个元素地址
};

  link *rcreat( )//尾插法建立链表
 { 
 link *s,*r,*p;
   int i;
   p=r=new link;
   p->next=NULL;
   cin>>i;
   while(i)
   {s=new link;
s->data=i;
r->next=s;
r=s;
cin>>i;
}
r->next=NULL;
return p;
}

link  *sum(link *la, link *lb)
//将两个升序排列的单链表la和lb合并成一个升序排列的单链表lc
{
  link *pa,*pb,*r,*lc;
  pa=la->next;
  pb=lb->next;
  lc=la;
  lc->next=NULL;
  r=lc;
  while((pa!=NULL)&&(pb!=NULL))
   if(pa->data<pb->data)
{ r->next=pa;
 r=pa; 
pa=pa->next;
}
   else 
{ r->next=pb;
 r=pb;
pb=pb->next;
}

 if(pa==NULL)  r->next=pb;
else r->next=pa;
return lc;
}
 void print(link *head)
 {  
 link *p;
    p=head->next;
    while(p->next!=NULL)
  { 
 cout<<p->data<<"->"; //输出表中非最后一个元素
p=p->next;
  }
  cout<<p->data;   //输出表中最后一个元素
 cout<<endl;
}
void main()
{ link *a,*b,*c;
cout<<"建立第一个升序排列的链表"<<endl;
 a=rcreat();
 cout<<"建立第二个升序排列的链表"<<endl;
 b=rcreat();
 cout<<"第一个链表的结果"<<endl;
 print(a);
 cout<<"第二个链表的结果"<<endl;
 print(b);
 c=sum(a,b);
 cout<<"合并后的结果"<<endl;
print(c);
}