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

我不能完全把手指放在它上面，但显然它在放置插入时忽略了列表的最后一个元素。感谢是否有人可以对此有所了解。谢谢！

4

2 回答 2

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

我认为还有很多错误。但是你问的具体错误在上面很明显。它总是在最后一项之前停止。我认为您应该放弃if并将时间更改为：

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

请注意，在您的原始代码中，theif和curr->next[i]->next[i]test 都在防御curr->next[i]->value段错误。您需要curr->next[i]->value在达到最后一项之前停止测试。但是您不想curr = curr->next[i];在到达最后一项之前停止。为此，我颠倒了你 && 的两侧，这样我就可以安全地从其中一个中删除一个间接级别。我希望这个解释足够清楚。

于 2015-07-15T12:43:12.970 回答
0

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

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

于 2015-07-15T13:20:31.370 回答