1

Introduction to Algorithmsの疑似コードには、次のように記載されています。

for each node w in the root list of H
  link trees of the same degree

しかし、各ルート ノードの部分を効率的に実装するにはどうすればよいでしょうか。元のルートは、統合のプロセスを通じて同程度の他のルートにリンクされます。これにより、ルート ノードの循環リストを通過することが難しくなります。すべてのルート ノードをチェックしたかどうかを判断するにはどうすればよいですか?

4

1 に答える 1

1

これを行う簡単な方法の 1 つは、次の 3 段階のプロセスを使用することです。

  1. リストが通常の二重リンク リストになるように、循環リンクを解除します。
  2. 双方向にリンクされたリストを反復処理し、各ツリーを処理します。前述のように、反復中に各ノードの前方ポインターと次ポインターが変更される可能性があるため、これは注意が必要です。
  3. サイクルを閉じます。

各ステップの実行方法は次のとおりです。

循環リンクを解除します。

rootList->prev->next = NULL;
rootList->prev = NULL;

二重にリンクされたリストを反復処理します。

Node* current = rootList;
while (current != NULL) {
    /* Cache the next node to visit so that even if the list changes, we can still
     * remember where to go next.
     */
    Node* next = current->next;

    /* ... main Fibonacci heap logic ... */

    current = next;
}

二重リンク リストを修復します。

Node* curr = rootList;
if (curr != NULL) { // If list is empty, no processing necessary.
    while (curr->next != NULL) {
        curr = curr->next;
    }
    curr->next = rootList;
    rootList->prev = curr;
}

お役に立てれば！

于 2013-03-16T17:45:20.137 に答える