1

我不明白l二项式堆中节点列表的反转：

Node* reverseList(Node* l) {
    //return reverseNode(l);
    if(l->sibling)
    {
        return reverseList(l->sibling);
        l->sibling->sibling = l;
    }
}

这是什么意思？：

l->sibling->sibling = l;

家长？

4

2 回答 2

2

问题中的代码不正确，这是正确的代码

int RevertList(Node *h){
    if (h->sibling != NULL){
        RevertList(h->sibling);
        (h->sibling)->sibling = h;
    }
    else
        root = h;
}

RevertList是从二项式堆中删除节点时使用的辅助函数。

当一个节点被删除时，它的子节点和它们的兄弟节点将从二项堆结构中分离出来。该RevertList函数颠倒了分离的孩子的顺序，因此它们可以以正确的顺序联合到根列表中。

查看此代码以更好地了解其工作原理！

下面是一个示例，来自 CLRS 教科书

在此处输入图像描述

于 2022-02-19T10:07:46.710 回答
2

一条return语句结束了函数的执行，所以你问的是死代码。

我希望该功能实际上是这样的：

Node* reverseList(Node* l) {
    if (l->sibling)
    {
        Node* head = reverseList(l->sibling);
        l->sibling->sibling = l;
        l->sibling = NULL;
        return head;
    }
    return l;
}

为了可视化这一点，让一个示例链表由三个节点组成：

  l
  ↓
┌───────────────┐     ┌───────────────┐     ┌───────────────┐
│ sibling: ─────────► │ sibling: ─────────► │ sibling: NULL │
│               │     │               │     │               │
└───────────────┘     └───────────────┘     └───────────────┘

当函数被调用时，我们进入if并进行递归调用。那个新的（第二个）执行上下文有它自己的局部变量，为了区分它们，我将在它们的名称中添加一个重音符号。所以我们有另一个l'变量：

  l                      l'
  ↓                      ↓
┌───────────────┐     ┌───────────────┐     ┌───────────────┐
│ sibling: ─────────► │ sibling: ─────────► │ sibling: NULL │
│               │     │               │     │               │
└───────────────┘     └───────────────┘     └───────────────┘

该函数的执行还将进行递归调用：

  l                      l'                   l"
  ↓                      ↓                    ↓
┌───────────────┐     ┌───────────────┐     ┌───────────────┐
│ sibling: ─────────► │ sibling: ─────────► │ sibling: NULL │
│               │     │               │     │               │
└───────────────┘     └───────────────┘     └───────────────┘

该函数的最新（第三次）执行将l'->sibling作为参数并将其分配给它自己的局部变量l"。它会找到l"->siblingis NULL，所以它只是返回相同的指针而不做任何更改。此时变量的生命周期l"结束。调用者将返回的值分配给一个局部head'变量——再次强调，这发生在第二个执行上下文中：

  l                      l'                  
  ↓                      ↓                   
┌───────────────┐     ┌───────────────┐     ┌───────────────┐
│ sibling: ─────────► │ sibling: ─────────► │ sibling: NULL │
│               │     │               │     │               │
└───────────────┘     └───────────────┘     └───────────────┘ 
                                              ↑
                                             head'

现在我们得到声明：l'->sibling->sibling = l'. 这意味着对最后一个节点的成员进行了分配sibling，因此我们得到：

  l                      l'                  
  ↓                      ↓                   
┌───────────────┐     ┌───────────────┐     ┌───────────────┐
│ sibling: ─────────► │ sibling: ─────────► │ sibling: ─┐   │
│               │     │               │ ◄───────────────┘   │
└───────────────┘     └───────────────┘     └───────────────┘ 
                                              ↑
                                             head'

然后我们执行l'->sibling = NULL：

  l
  ↓ 
┌───────────────┐     ┌───────────────┐     ┌───────────────┐
│ sibling: ─────────► │ sibling: NULL │     │ sibling: ─┐   │
│               │     │               │ ◄───────────────┘   │
└───────────────┘     └───────────────┘     └───────────────┘ 
                                              ↑
                                             head'

然后我们执行return head'. 第二个执行上下文的变量结束它们的生命（不再有重音符号）。第一个执行上下文会将返回的指针分配给它自己的head变量：

  l
  ↓ 
┌───────────────┐     ┌───────────────┐     ┌───────────────┐
│ sibling: ─────────► │ sibling: NULL │     │ sibling: ─┐   │
│               │     │               │ ◄───────────────┘   │
└───────────────┘     └───────────────┘     └───────────────┘ 
                                              ↑
                                             head

现在我们得到声明：l->sibling->sibling = l. 这意味着对中间节点的成员进行了分配sibling，因此我们得到：

  l
  ↓ 
┌───────────────┐     ┌───────────────┐     ┌───────────────┐
│ sibling: ─────────► │ sibling: ─┐   │     │ sibling: ─┐   │
│               │ ◄───────────────┘   │ ◄───────────────┘   │
└───────────────┘     └───────────────┘     └───────────────┘ 
                                              ↑
                                             head

我们执行l->sibling = NULL：

  l
  ↓ 
┌───────────────┐     ┌───────────────┐     ┌───────────────┐
│ sibling: NULL │     │ sibling: ─┐   │     │ sibling: ─┐   │
│               │ ◄───────────────┘   │ ◄───────────────┘   │
└───────────────┘     └───────────────┘     └───────────────┘ 
                                              ↑
                                             head

最后，我们返回head。局部变量结束它们的生命周期，因此只有返回的指针是相关的：

┌───────────────┐     ┌───────────────┐     ┌───────────────┐
│ sibling: NULL │     │ sibling: ─┐   │     │ sibling: ─┐   │
│               │ ◄───────────────┘   │ ◄───────────────┘   │
└───────────────┘     └───────────────┘     └───────────────┘ 
                                              ↑
                                             (returned)

您可以看到返回的指针确实引用了反向列表。

于 2022-02-19T11:08:29.953 回答