更新时间:2016-05-15 22:47:43浏览次数:1+次
先看看运行结果:
单链表的求并集问题,就是将两个单链表按升序或是降序的顺序排列成一个链表!那么这样的问题的思路是什么样的呢?这个不急,我们先讲讲单链表一分为二的操作原理。在程序员面试金典一书中,有这样的一个问题:
void pri(LinkList H)
{
LinkList p;
p=H->next;
while(p)
{
cout<<p->data<<" ";
p=p->next;
}
}
void fengecaozuo(LinkList H,LinkList A,LinkList B,int x)
{
LinkList pa,pb,pc;
pc=H->next;
pa=A;
pb=B;
while(pc)
{
if(pc->data<x)
{
pa->next=pc;
pa=pc;//注释掉这行,运行下面那行也行!!!
//pa=pa->next;
pc=pc->next;
}
else
{
pb->next=pc;
pb=pc;//注释掉这行,运行下面那行也行!!!
//pb=pb->next;
pc=pc->next;
}
}
pa->next=NULL;
pb->next=NULL;
cout<<"A链表:"<<endl;
pri(A);
cout<<"B链表:"<<endl;
pri(B);
return ;
}
对于A,B两个单链表,我并没有调用初始化函数,而是直接在main函数中:LinkList A,B;
A=(LinkList)malloc(sizeof(LinkList));
B=(LinkList)malloc(sizeof(LinkList));
就是直接给A,B分配空间。当满足操作的时候,我就给两个链表的对象赋值。从头结点下的第一个结点开始,我们将pc所对应的结点赋值给他们,自然,你就需要递增pc结点。与此同时,递增的还有pa,pb结点,否则的话,我们怎么给整个A,B链表赋值!注意看上面的程序的注释。void MergeList(LinkList A, LinkList B, LinkList *C)
{
ListNode *pa, *pb, *pc;
pa=A->next;
pb=B->next;
*C=A;
(*C)->next=NULL;
pc=*C;
while(pa&& pb)
{
if(pa->data <= pb->data)
{
pc->next=pa;
pc=pa;
pa=pa->next;
}
else
{
pc->next=pb;
pc=pb;
pb=pb->next;
}
}
pc->next=pa ? pa: pb;
free(B);
}
你会发现是一样的。没错,其实原理是一样的,我刚开始研究一分为二的时候,就像从求并集开始着手。于是最后查资料结合自己的理解,其实两者的原理是一样的!相关资讯