下面程序的功能是;将两个有序链表(降序捧序)合并为一个有序链表,函数merge(node *h1,node *h2)将由h1和h2分别指向的己排序的两个链表,合并为一个依然有序的链表。注意;对于数据大小相同的结点,都要保留在合并后的链表上。主函数产生两条已降序排序的链表,并输出合并后链表上的数据值.
例如,原链表上各结点的数据依次为;
h1:15,9,8,7,3
h2:15,12,10,7,3,2
合并后得到的新链表为;15,15,12, 10,9,8,7,7,3,3,2
【程序]
#include
struct node{
int data;
node*next;
};
node *merge(node *h1,node *h2)
{
if(h1==NULL) return h2;
if(h2==NULL) return h1;
node *h=NULL;
if(___(1)___){
h=h1;
h1=h1->next;
}
else{
h=h2;
h2=h2->next;
}
node *p=h;
while(___(2)___){
if(h1->data >=h2->data){
p->next=h1;
p=h1;
h1=h1->next;
}
else{
p->next=h2;
p=h2;
h2=h2->next;
}
}
if(h1 !=NULL) ___(3)___;
else
if(h2!=NULL) p->next=h2;
return h;
}
void main(void)
{
node a[5]={{15},{9},{8},{7},{3}};
node b[6]={{15},{12},{10),{7},{3},{2}};
node *h,*h1,*h2,*p;
int i;
h1=a;
h2=b;
for(i=0;i<4;i++) a[i].next=&a[i+1]; //形成a链表
a[4].next=NULL;
for(i=0;i<5;i++) b[i].next=&b[i+1]; //形成b链表
b[5].next=NULL;
___(4)___ ;
p=h;
while(p){
cout<data<<’\t’;
p=p->next;
}
cout<
}
