У меня проблемы с удалением узла из списка пропусков. У меня есть следующие структуры:
struct Node
{
int info;
Node **link_;
Node(int v, int levels)
{
info = v;
link_ = new Node*[levels];
for ( int i = 0; i < levels; ++i )
link_[i] = NULL;
}
};
struct List
{
int H; // list height
Node *Header;
List()
{
Header = new Node(0, maxH);
H = 1;
}
};
Проблема, я думаю, заключается в функции, которая ищет узел с заданным значением, а затем удаляет его. Функция реализована так:
void Remove(int v, List *L)
{
Node *current = L->Header;
for ( int i = L->H - 1; i >= 0; --i )
{
for ( ; current->link_[i] != NULL; current = current->link_[i] )
if ( current->link_[i]->info > v )
break;
else if ( current->link_[i]->info == v )
{
// Node *del = current->link_[i];
current->link_[i] = current->link_[i]->link_[i];
// delete del;
break;
}
}
}
Функция работает нормально, как есть, однако список, кажется, ломается, если я раскомментирую две закомментированные строки. Под прерыванием я подразумеваю, что следующий тестовый код никогда не завершается:
int main()
{
srand((unsigned)time(0));
List *SKL = new List();
for ( int i = 0; i < 1000000; ++i )
Insert(rand() * rand(), SKL);
for ( int i = 0; i < 1000000; ++i )
Search(rand() * rand(), SKL);
for ( int i = 0; i < 1000000; ++i )
Remove(rand() * rand(), SKL);
for ( int i = 0; i < 1000000; ++i )
Insert(rand() * rand(), SKL);
return 0;
}
Проблема заключается в последнем цикле for
, который вставляет больше значений в список. Если эти две строки закомментированы, программа завершается примерно через 10 секунд. Если я раскомментирую их, кажется, что они входят в бесконечный цикл, так как он даже не заканчивается за несколько минут. Я не уверен, является ли это правильным способом удаления узла из списка пропусков или нет, поэтому я также публикую свою функцию вставки:
void Insert(int v, List *L)
{
// this section just determines the levels the new node will be part of
int newH = 0;
int tmp;
unsigned int rnd = rand() * rand();
do
{
tmp = lookup[rnd & 255];
rnd >>= 8;
newH += tmp;
} while ( tmp == 8 );
if ( newH >= L->H )
++L->H;
// this does the actual insertion
Node *newNode = new Node(v, L->H);
Node *current = L->Header;
for ( int i = L->H - 1; i >= 0; --i )
{
for ( ; current->link_[i] != NULL; current = current->link_[i] )
if ( current->link_[i]->info >= v )
break;
if ( i <= newH )
{
newNode->link_[i] = current->link_[i];
current->link_[i] = newNode;
}
}
}
Итак, мои вопросы:
- Почему программа ломается и как я могу заставить ее работать, фактически удаляя узлы, которые я хочу удалить из памяти?
- Это правильный способ реализации списков пропуска, или я использую неправильный подход?