链式有序表的合并中,为什么要把第二个表的头结点释放掉?
jmyz_0455在链式有序表的合并中,假设头指针为 LA 和 LB 的单链表分别为线性表 LA 和 LB 的存储结构,归并 LA 和 LB 得到单链表 LC。
网上很多教材的算法描述里,最后都要把 LB 的头结点释放掉,就这一点我想不明白。请问:
1、为什么要释放 LB 的头结点?
2、那么释放掉头结点的线性表 LB 是不是就不存在了(被删掉)?
3、如果2的答案是「是」,那么为什么合并线性表 LA 和 LB 之后要只剩下 LA 和 LC ?不应该是三个表都保留吗?
就是想不明白释放 LB 头结点是为了什么,可能我有些基础的概念遗漏了?请各位指点一下。
请上代码截图^_^
我挺好奇是个什么情况^_^
void MergeList_L(LinkList &LA, LinkList &LB, LinkList &LC)
{
pa = LA->next; pb = LB->next;
LC = LA;
pc = 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;
delete LB;
}
}
这文字编辑器搞得我都疯了...Markdown 格式嚒,我还是去学一下再来回复
1 void MergeList_L(LinkList &LA, LinkList &LB, LinkList &LC) {
2 pa = LA->next; pb = LB->next;
3 LC = LA;
4 pc = LC;
5 while(pa && pb) {
6 if(pa->data <= pb->data) {
7 pc->next = pa;
8 pc = pa;
9 pa = pa->next;
10 } else {
11 pc->next = pb;
12 pc = pb;
13 pb = pb->next;
14 }
15 pc->next = pa ? pa : pb;
16 delete LB;
17 }
18 }
首先, LA/ LB / LC 都是指针
那么,第3行已经让LC 指向LA,所以删除LA就是删除LC所指的空间。
代码一行一行的看,不要求快。
LA和LB的头指针都是用了所谓的「哨兵节点」,它们本身是空的节点,所以合并时并不参与。用哨兵节点做头指针是为了简化边界条件。
两个链表合并完之后,LA(LC)是新链表的头指针,仍是一个哨兵节点。这时原本用作LB头指针的这个哨兵节点就没有用了,所以要释放掉。
如果你创建一个链表的时候不使用哨兵节点做头指针,那合并完之后就不可以释放掉LB的头指针。