c++ - 此递归函数如何工作?合并排序两个单链表

c++ - 此递归函数如何工作?合并排序两个单链表,第1张

我在geeksforgeeks.org上的C 中找到了此递归函数,用于合并和排序两个单链列表,我使用netbeans调试了此代码,但仍然无法在该代码的功能背后找到清晰的主意。我也见过类似的代码stackoverflow,但没有解释它的工作方式。我的问题是关于它背后的想法及其工作方式的问题,这里的充分解释也将帮助其他有相同问题的人。

在netbeans上调试代码以了解代码的工作流程

//Merges two given lists in-place. This function 
// mainly compares head nodes and calls mergeUtil() 

Node *merge(Node *h1, Node *h2) 
 { 
if (!h1) 
    return h2; 
if (!h2) 
    return h1; 

// start with the linked list 
// whose head data is the least 
if (h1->data < h2->data) 
{ 
    h1->next = merge(h1->next, h2); 
    return h1; 
} 
else
{ 
    h2->next = merge(h1, h2->next); 
    return h2; 
 } 
} 

此函数应返回一个排序的链表

最佳答案:

2 个答案:

答案 0 :(得分:1)

我在代码中添加了注释。如果将其用于合并排序,我还将if从<更改为<=,如果h1-> data == h2-> data,则您希望首先使用h1以获得稳定性。请记住,两个列表已经排序,此功能只是合并它们。

该函数递归地跟随两个列表,跳过较小的节点,直到到达列表之一的末尾,这时它将该列表的末尾设置为另一个列表的其余部分,然后返回递归调用链,沿着列表向后移动,将较小的节点设置为下一个指针,以从后到前合并列表。这是合并列表的一种低效方式,因为由于每个节点上的递归都会消耗O(n)堆栈空间,但这可能是一种学习活动,效率不高。

// initial input parameters, h1 and h2 each point to already sorted lists
Node *merge(Node *h1, Node *h2) 
{
    if (!h1)                                // if h1 empty
        return h2;                          //  return h2
    if (!h2)                                // if h2 empty
        return h1;                          //  return h1

    if (h1->data <= h2->data)               // if h1->data <= h2->data
    {
        h1->next = merge(h1->next, h2);     //  h1->next = smaller of {h1->next, h2}
        return h1;                          //  return h1
    }
    else                                    // else h1->data > h2->data
    {
        h2->next = merge(h1, h2->next);     //  h2->next = smaller of {h1, h2->next}
        return h2;                          //  return h2
    }
}

答案 1 :(得分:0)

我相信举一个例子是理解递归算法如何工作的最好方法。让我们以这两个示例链接列表为例:

  • {13, 24, 74}
  • {34, 72, 95}

请注意,由于algorithm的要求,它们都已排序:

  

给出两个排序列表,将它们合并以产生组合的排序列表

我已对结果进行了跟踪:

  • 箭头是执行顺序
  • 每行是一个堆栈框架。特别是,左侧的行在递归调用merge之前,而右侧的行则在之后。

c&#43;&#43; - 此递归函数如何工作?合并排序两个单链表,Execution order,第2张

也请注意以下几点:

  • 在左侧的每个箭头上,从节点开始的较小元素消失了
  • 在回溯的路上,较小的元素在另一侧获得了元素的排序顺序。最后,我们以排序形式返回刚刚获得另一个列表的列表,即:{13,24,34,72,74,95}
本文经用户投稿或网站收集转载,如有侵权请联系本站。

发表评论

0条回复