下面程序的功能是;将两个有序链表(降序捧序)合并为一个有序链表,函数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<

}