第一个插入的值总是被推到排序跳跃表的后面

#include <iostream>
#include <string>
#include <ctime>
#include <cstdlib>
using namespace std; // TESTING ONLY
class SkipList
{
private:
    struct Node
    {
        Node(int value, int level)
        {
            this->value = value;
            next = new Node*[level];
        }
        Node **next;
        int value;
    };
    Node *head = new Node(0, maxLevel);
    int maxLevel;
    public:
    SkipList()
    {
        maxLevel = 10;
        srand((int)time(nullptr));
        head->next = new Node*[maxLevel];
        for (int i = 0; i < maxLevel; i++)
        {
            head->next[i] = nullptr;
        }
    }
    int promotion()
    {
        int level = 0;
        int _rand = rand() % 2;
        while (_rand)
        {
            level++;
            _rand = rand() % 2;
        }
        return level;
    }
    void Insert(int value)
    {
        int level = promotion();
        Node *newNode = new Node(value, level);
        Node *curr = head;
        for (int i = 9; i >= 0; i--)
        {
            if (curr->next[i] != nullptr)
            {
                while (value > curr->next[i]->value && curr->next[i]->next[i] != nullptr)
                {
                    curr = curr->next[i];
                }
            }
        }
        for (int i = 0; i <= level; i++)
        {
            newNode->next[i] = curr->next[i];
            curr->next[i] = newNode;
        }
    }
    void print() const
    {
        Node *cur = head->next[0];
        cout << "List: NULL --> ";
        while (cur != nullptr)
        {
            cout << cur->value << " --> ";
            cur = cur->next[0];
        }
        cout << "NULL";
        cout << endl;
    }
};

int main()
{
    SkipList skip;
    skip.Insert(3);
    skip.Insert(2);
    skip.Insert(50);
    skip.Insert(39);
    skip.Insert(2000);
    skip.Insert(500);
    skip.print();
    cout << endl << endl;
    system("pause"); // TESTING
    return 0;
}

当我运行上面的代码时，插入的第一个元素(在本例中为3)总是列表中的最后一个元素。所有其他元素都按正确的顺序插入。上面的程序显示2-39-50-500-2000-3。我可以再插入100个值，它们都将插入正确的位置，除了插入的第一个元素总是最后一个，无论我是否放置更大的值。

我不太清楚，但很明显，它在插入时忽略了列表的最后一个元素。如果有人能解释一下，我会很感激的。谢谢!

        if (curr->next[i] != nullptr)
        {
            while (value > curr->next[i]->value && curr->next[i]->next[i] != nullptr)
            {
                curr = curr->next[i];
            }
        }

我认为有更多的错误。但是你所询问的特定bug在上面的while中是很明显的。它总是在最后一项之前停止。我认为你应该放弃if，并将while改为:

        while (curr->next[i] != nullptr && value > curr->next[i]->value )
        {
            curr = curr->next[i];
        }

注意，在您的原始代码中，if和curr->next[i]->next[i]测试都防御curr->next[i]->value隔离故障。您需要在到达最后一个项目之前停止curr->next[i]->value测试。但是，您不希望在到达最后一项之前停止curr = curr->next[i];。为了做到这一点，我把你的两边颠倒了。这样我就可以安全地移除其中一个的间接层级。我希望这个解释足够清楚。

请参阅我对原始问题的评论

for (int i = 9; i >= 0; i--)
{
    // Find the right predecessor at level i.
    while (curr->next[i] != nullptr value > curr->next[i]->value && )
    {
        curr = curr->next[i];
    }
    // link in this node only if its level is high enough
    if ( i < level )
    {
        newNode->next[i] = curr->next[i];
        curr->next[i] = newNode;
    }
}

但是如果我正确理解你的意图，你还需要修复promotion()，因为设计依赖于等级>0，但促销不提供。您的原始代码使用<=level，因此它通常在next[]中使用比分配的位置多一个位置。我修改后的代码使用水平更合理。如果您希望级别0有效，则修复节点构造函数，以便您可以安全地在i < level

中切换到<=。

相关内容

最新更新

热门标签：