代码之家 › 专栏 › 技术社区 › IVlad

从跳过列表中删除节点

skip-lists implementation data-structures algorithm c++

IVlad · 技术社区 · 15 年前

从跳过列表中删除节点时遇到一些问题。我有以下结构:

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

所以,我的问题是:

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

2 回复 | 直到 13 年前

Matthieu M. 15 年前

有一个问题 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;
            }
        }
    }
}

为了举例,我们假设要删除的节点出现在两个级别:0和1。

这个 for 循环层次 L->H 到2不做任何事情。

在级别1上,它将找到请求的节点,并将其删除。

在级别0上,它将尝试跟踪指向已删除节点的指针,从而导致未定义的行为。

解决方案:

仅在级别0时删除节点。只要您在上层,节点仍然被引用,您需要保持它的活动状态。

anon 15 年前

在移除函数中,外部循环在列表中迭代当前条目数的计数。然后在循环中删除其中一个中心点,但继续迭代旧的计数。