从跳过列表中删除节点

Question

从跳过列表中删除节点时出现了一些问题。我有以下结构：

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; 
     } 
    } 
} 

所以，我的问题是：

1. 为什么程序中断，以及如何在实际删除要从内存中删除的节点时使其工作？
2. 这是一个实现跳过列表的正确方法，还是我使用了错误的方法？

Answer 1

有一个与Remove方法的问题，因为你猜：

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]; 

       // if (0 == i) delete del; 
       break; 
      } 
     } 
    } 
} 

例如起见，我们假设节点，我们希望在2级删除出现：0和1

for级别L->H到2的循环不会执行任何操作。

在级别1上，它会找到请求的节点并删除它。

在级别0上，它将尝试跟随指向已经删除的节点的指针，导致未定义的行为。

解决方案：

只删除节点时为0级，只要你在上层的节点仍然被引用，你需要保持它活着。

Answer 2

在您的删除功能中，您的外循环遍历列表中的当前条目数。然后在循环中删除其中一个ntries，但继续迭代旧计数。