主题:一个简单的归并
将两个递增有序表A,B归并成一个新的链表C,但不开辟新的存储空间,使C递减有序。
void revers_merge(LinkList &A,LinkList &B,LinkList &C)
{
pa=A->next;pb=B->next;pre=Null; //pa和pb分别指向A、B的当前元素
while(pa&&pb)
{
if(pa->data <pb->data) //将A的元素插入新表
{
pc=pa;q=pa->next;pa->next=pre;pa=q; //这里是怎么实现具体插入的?
}
else
{
pc=pb;q=pb->next;pb->next=pre;pb=q; //这里是怎么实现具体插入的?
}
pre=pc;
}
while(pa) //插入A中剩下的元素
{
q=pa->next;pa->next=pc;pc=pa;pa=q; //这里是怎么实现具体插入的?
}
while(pb)//插入B中剩下的元素
{
q=pb->next;pb->next=pc;pc=pb;pb=q;//这里是怎么实现具体插入的?
}
C=A;A->next=pc;
}
这里的归并思想俺也懂(就是从小到大顺序依次把A和B的元素插入新表的头部pc处,最后处理A或B的剩下元素),但是我加注释的那些细节就是不太明白,他们是怎么实现具体插入的咯,作图示好像感觉不对。呵呵,麻烦哪们详细讲解下哦,对我很重要,你辛苦了,我谢谢了!
void revers_merge(LinkList &A,LinkList &B,LinkList &C)
{
pa=A->next;pb=B->next;pre=Null; //pa和pb分别指向A、B的当前元素
while(pa&&pb)
{
if(pa->data <pb->data) //将A的元素插入新表
{
pc=pa;q=pa->next;pa->next=pre;pa=q; //这里是怎么实现具体插入的?
}
else
{
pc=pb;q=pb->next;pb->next=pre;pb=q; //这里是怎么实现具体插入的?
}
pre=pc;
}
while(pa) //插入A中剩下的元素
{
q=pa->next;pa->next=pc;pc=pa;pa=q; //这里是怎么实现具体插入的?
}
while(pb)//插入B中剩下的元素
{
q=pb->next;pb->next=pc;pc=pb;pb=q;//这里是怎么实现具体插入的?
}
C=A;A->next=pc;
}
这里的归并思想俺也懂(就是从小到大顺序依次把A和B的元素插入新表的头部pc处,最后处理A或B的剩下元素),但是我加注释的那些细节就是不太明白,他们是怎么实现具体插入的咯,作图示好像感觉不对。呵呵,麻烦哪们详细讲解下哦,对我很重要,你辛苦了,我谢谢了!