第一个插入的值总是被推到排序的跳过列表的后面 C++

Question

#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 个值，它们都会插入正确的位置，除了第一个插入的元素总是最后一个，无论我是否放置更大的值。

我不能完全确定它，但显然它在放置插入时忽略了列表的最后一个元素。欣赏是否有人可以阐明这一点。谢谢！

Answer 1

        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];。为此，我颠倒了你的 && 的两侧，这样我就可以安全地从其中一个中删除一个间接级别。我希望解释足够清楚。

Answer 2

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

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()，因为设计依赖于 level>0，但推广没有提供。您的原始代码使用 <=level 因此它通常在 next[] 中使用比分配的位置多一个位置。我更正后的代码更合理地使用了级别。相反，如果您希望级别 0 有效，请修复节点构造函数，以便您可以安全地切换到我的 i < level

中的 <=

第一个插入的值总是被推到排序的跳过列表的后面 C++

First inserted value always pushed to rear of sorted skip list c++

c++

list

skip-lists