读书人

链表归并,该怎么处理

发布时间: 2012-02-19 19:43:39 作者: rapoo

链表归并
谁能告诉我下面这代码怎么实现归并的
void MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc) {

// 已知单链线性表La和Lb的元素按值非递减排列。
// 归并La和Lb得到新的单链线性表Lc,Lc的元素也按值非递减排列。
LinkList pa, pb, pc;
pa = La->next; pb = Lb->next;
Lc = pc = La; // 用La的头结点作为Lc的头结点
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(Lb); // 释放Lb的头结点
}

[解决办法]
就是最常规的两个升序列的归并啊
依次比较两个队列的当前节点,插入较小的一个,然后指针往后移一位,下面继续
最后跳出循环以后,至少有一个链表已经是空的了,把另外一个接在后面就行了
[解决办法]
循环逐个比较大小,将小的放进去, 循环结束,剩下的就是大的, 再将大的加到链表中
[解决办法]

探讨
pc->next = pa ? pa : pb; // 插入剩余段不应用个循环码?假如LB表剩余元素个数大于一不就插入不完了吗

读书人网 >软件架构设计

热点推荐