0

スキップ リストのコピー関数を作成しようとしているときに問題が発生しました。クラスのほとんどはすでに完了しているので、デザインを変更したくない.

各ノードには 2 つのポインタがあり、1 つは同じレベルの次のノードへのポインタで、もう 1 つは 1 レベル下の同等のノードへのポインタです。私のクラスには、各レベルのヘッド ノードへのポインタを格納するベクトルがあります。

struct Node
{
    int key;
    Node* next;
    Node* below;
}
vector<Node*> levels;

私のプライベートコピー機能：

void copyAll(const SkipList& s)
{
    for(unsigned int i = 0; i < s.level.size(); ++i)
    {
        Node* curr = s.level[i];
        Node* copy = new Node(curr->key, nullptr, curr->below);
        level.push_back(copy);
        curr = curr->next;
        while(curr != nullptr)
        {
            copy->next = new Node(curr->key, nullptr, curr->below);
            copy = copy->next;
            curr = curr->next;
        }
    }
}

この関数は、すべての単一ノードがコピーされて相互にリンクされている状態で水平方向に正常に機能しますが、垂直方向のリンクは設定しません。
curr->below誰でもこれを機能させる方法についていくつかの提案を得ることができますか?

4

1 に答える 1

0

トップレベルから下に向かって作業する代わりに、ボトムアップから行うことができます. そうすれば、ノードのコピーを作成するときはいつでも、対応する「下」のコピーがすでに存在します。

void copyAll(const SkipList& s)
{
    level.resize(s.level.size());
    for(unsigned int i = s.level.size(); i > 0; --i)
    {
        Node* curr = s.level[i-1]; // Note the intended change in the range of i
        Node* curBelowCopy = // If not the bottom, ptr to start of the row below
            curr->below ? level[i] : nullptr;

        Node* copy = new Node(curr->key, nullptr, curBelowCopy);
        level[i-1] = copy;
        curr = curr->next;
        while(curr != nullptr)
        {
            if (curBelowCopy) {
                // Not the last level: advance curBelowCopy to the
                // corresponding copy of cur->below
                while (curBelowCopy->key != curr->below->key)
                    curBelowCopy = curBelowCopy->next;
            }

            copy->next = new Node(curr->key, nullptr, curBelowCopy);
            copy = copy->next;
            curr = curr->next;
        }
    }
}
于 2016-05-18T19:36:44.767 に答える