这是一个创建于 3211 天前的主题，其中的信息可能已经有所发展或是发生改变。
在链式有序表的合并中，假设头指针为 LA 和 LB 的单链表分别为线性表 LA 和 LB 的存储结构，归并 LA 和 LB 得到单链表 LC 。
网上很多教材的算法描述里，最后都要把 LB 的头结点释放掉，就这一点我想不明白。请问：
1 、为什么要释放 LB 的头结点？
2 、那么释放掉头结点的线性表 LB 是不是就不存在了（被删掉）？
3 、如果 2 的答案是「是」，那么为什么合并线性表 LA 和 LB 之后要只剩下 LA 和 LC ？不应该是三个表都保留吗？
就是想不明白释放 LB 头结点是为了什么，可能我有些基础的概念遗漏了？请各位指点一下。
 |
1
Andiry 2016-01-30 15:54:53 +08:00
取决于链表头是一个真实节点还是一个假节点。真实节点不释放。
|
 |
3
Kilerd 2016-01-30 18:58:31 +08:00
取决于你的链表设计吧。
链表分好多种： 单纯链表，带表头的链表（为了统一算法），循环链表 blabla...一大堆 估计你看到的就是 带表头的链表 算法吧。 |
 |
4
mimzy 2016-01-30 19:14:01 +08:00
我从直觉上去理解
1. 释放头结点就是为了该结点所占的空间，保证这个空间以后可以被其他的东西占用。 2. 只是头结点不存在了，头结点后面的结点该怎么连着还怎么连着，空间也占着。 3. LA 和 LC 最后变成了一个东西，就是合并后的链表。只不过 LC 直接利用了 LA 原来的头结点。 真实世界的情况可能未必是这样，但是国内数据结构的课程里应该是我说的这种情况。 |
 |
5
cfans1993 2016-01-30 19:32:46 +08:00 via Android
没头结点的，初始时头和尾指针都指向 null
有头结点的，初始化时头和尾指针都指向头结点。一般头结点内不存储实际数据，作为标记用，如果头尾指针指向同一个结点说明为空；另外删除第一个节点时（头节点的下一个）不容易出错 回到题主的那个问题上，在合并过程中以 A 为基础，然后把 b 给合并到 a 当中，在合并过程中 a 和 b 的数据已经交叉在一起，也就是 a 中的数据节点已经有指向 b 中的， b 中的数据节点也要指向 a 中的， a 和 b 都已经完全脱离原来的形态， b 的那个头节点依然占着一个结点空间，把它删除也就相当于删除了这个已经没什么卵用的头结点 |
|
6
cfans1993 2016-01-30 19:34:36 +08:00 via Android
过一会儿给你上个图
|
|
7
cfans1993 2016-01-30 19:55:53 +08:00
大概是这个样子 |
 |
8
jmyz0455 OP @cfans1993 非常感谢！一看就懂了，我在 CSDN 发两天了都没人回答，刚来 V2EX 就几个人回了，感谢大家，我以后有编程的问题都可以来着问吗，我看这个论坛聊别的也很多，数据结构的去什么论坛问人气多点？
|
|
12
jmyz0455 OP @cfans1993 @mimzy
书本里的代码是这样的，应该跟你们描述的情况一样吧，我怕说错了，注释没打： 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; } } 我自己也画了下图，的确是连起来的，稍微问一下既然 LB 都删了怎么 LA 还留着，好像就留 LC 足够了吧 |
|
13
cfans1993 2016-01-30 21:12:45 +08:00 via Android
我不知道你的链表是怎么实现的，不过成员数据主要是三项：头尾指针，加上一个头结点。删除一个链表时，会连带把他的头尾指针和头节点都删掉，由于 a 中的头节点已经被 c 占用（共享），所以不能直接删除。如果想断开 a 与链表的连接，把 la 指向 null 就好了
|
|
14
cfans1993 2016-01-30 21:15:34 +08:00 via Android
你删了 la 然后打印 lc 的元素试试
|
|
15
mimzy 2016-01-30 22:18:04 +08:00
@jmyz0455 楼上已经给出解释了。因为 LC 和 LA 都是变量名而已，它们指向的是同一个结点（ LC = LA; 这一句传的是地址，并没有创造出新的结点），所以如果你删了 LA 的话， LC 也就一并删除了。
问问题可以在 V2EX ，也可以试试 http://segmentfault.com/ 。 |
Select Language