0

我在尝试为我的跳过列表编写复制功能时遇到了问题。由于大部分课程已经完成，我不想改变我的设计。

每个节点有两个指针，一个指向同一层的下一个节点，另一个指向下一层的等效节点。在我的班级中，有一个向量存储指向每个级别的头节点的指针。

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 回答