Первое вставленное значение всегда помещается сзади отсортированного списка пропусков Переполнение стека
#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];
}
}
Я думаю, что есть гораздо больше ошибок. Но конкретная ошибка, о которой вы спрашивали, очевидна в приведенном выше примере. Всегда останавливается перед последним пунктом. Я думаю, что вы должны бросить if и измените время на:
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