链式有序表的合并中,为什么要把第二个表的头结点释放掉?

jmyz_0455 发布于 11月前
无人欣赏。

在链式有序表的合并中,假设头指针为 LA 和 LB 的单链表分别为线性表 LA 和 LB 的存储结构,归并 LA 和 LB 得到单链表 LC。

网上很多教材的算法描述里,最后都要把 LB 的头结点释放掉,就这一点我想不明白。请问:

1、为什么要释放 LB 的头结点?

2、那么释放掉头结点的线性表 LB 是不是就不存在了(被删掉)?

3、如果2的答案是「是」,那么为什么合并线性表 LA 和 LB 之后要只剩下 LA 和 LC ?不应该是三个表都保留吗?

就是想不明白释放 LB 头结点是为了什么,可能我有些基础的概念遗漏了?请各位指点一下。

猜你喜欢:

共5条回复
wangxl 回复于 11月前

请上代码截图^_^

我挺好奇是个什么情况^_^

jmyz_0455 回复于 11月前

1楼 @wangxl 书本里的代码是这样的,注释没打:

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 格式嚒,我还是去学一下再来回复

wangxl 回复于 11月前
  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所指的空间。

wangxl 回复于 11月前

代码一行一行的看,不要求快。

amosji 回复于 11月前

LA和LB的头指针都是用了所谓的「哨兵节点」,它们本身是空的节点,所以合并时并不参与。用哨兵节点做头指针是为了简化边界条件。
两个链表合并完之后,LA(LC)是新链表的头指针,仍是一个哨兵节点。这时原本用作LB头指针的这个哨兵节点就没有用了,所以要释放掉。

如果你创建一个链表的时候不使用哨兵节点做头指针,那合并完之后就不可以释放掉LB的头指针。

登录 或者 注册
相关帖子
格式建议
  • 本站使用 Markdown 格式,想了解这一格式请阅读:《用Markdown语法写文章》
  • 内容框下有实时预览框,请预览后发帖。
  • 文字前面请不要空4个英文空格
  • 每段文字之间请回两次车
  • 贴代码前点击左侧工具栏的“贴代码”按钮(
    ),然后在出现的“enter code here”处贴入你的代码。
  • 回复特定回复的时候,请点击该回复右侧的回复链接,系统将自动创建楼号和@通知。
  • @他人的时候注意,id后面请加一个空格。
  • 使用左侧工具栏“贴链接”按钮(
    )创建的优酷、土豆、youtube视频链接,将自动生成播放区域,不需要使用其他包含方式。
  • 如果要创作长篇格式复杂的帖子,本站建议Mac用户使用Mou软件,离线写好,贴入即可。