#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 个值,它们都会插入正确的位置,除了插入的第一个元素总是最后一个,无论我是否放置更大的值。
我不能完全把手指放在它上面,但显然它在放置插入时忽略了列表的最后一个元素。感谢是否有人可以对此有所了解。谢谢!