我在互联网上阅读了有关跳过列表的信息,但对它如何与不同的数据结构以及所有其他数据一起使用的想法一目了然。但是我真的想实现带有双重链接列表的跳过列表,因为我想在插入时对双重链接列表进行排序。表示当时元素插入时,应仅以排序方式插入。

在这里,我实现了以排序方式在双向链表中插入数据的方法,但是当元素数量很大时,这需要很长时间才能以排序方式插入数据和建立列表。

请告诉我如何在现有函数中添加跳过列表算法,或者我必须重新编写整个内容?实现方面的任何帮助将不胜感激

这是代码:

void DoubleList::addSorted(int value)
{
    IDoubleNode * tempNode = new DoubleNode();
    tempNode->setValue(value);
    // if double link list is empty
    if(getHead() == NULL)
    {
        // temp node already has NULL value in next and prev.
        setHead(tempNode);
        setTail(tempNode);
    }
    else if(value <= getHead()->getValue())
    {
        tempNode->setNext(getHead());// set tempnode next as current head.
        tempNode->setPrev(getHead()->getPrev()); // set previous
        getHead()->setPrev(tempNode); // set previous pointer of head to tempnode which we just inserted
        setHead(tempNode); // set head
        getHead()->setPrev(NULL);// for safer side. we already done this.
    }
    else
    {
        int found = 0;
        IDoubleNode *currNode = getHead();
        while(currNode->getNext() != NULL && found == 0)
        {
            if(currNode->getNext()->getValue() > tempNode->getValue())
            {
                found = 1;
            }
            else
            {
                currNode = currNode->getNext();
            }
        }
        if(found)
        {
            tempNode->setNext(currNode->getNext());
            currNode->getNext()->setPrev(tempNode);
            currNode->setNext(tempNode);
            tempNode->setPrev(currNode);
        }
        else
        {
            currNode->setNext(tempNode);
            tempNode->setPrev(currNode);
            tempNode->setNext(NULL);
            setTail(tempNode);
        }
    }
}

最佳答案

跳过列表的优点在于它可以对数据项进行排序,还可以提供o(log n)插入和删除时间的复杂性。为了使它更容易理解,请想象您的链表有捷径或 anchor ,这样您就不必遍历整个列表来查找插入项目的位置。您只需遵循 anchor ,因此它是具有快速访问 anchor 的双向链接列表。

至于实现,如果您不打算将跳过列表用于多线程访问,那么实现起来就变得微不足道了。没有理由将跳过列表与双向链接列表组合在一起,但是您可以将跳过列表实现为双向链接列表

看着
http://www.sanfoundry.com/cpp-program-implement-skip-list/

关于c++ - 带有跳过列表的双重链接列表以排序方式插入,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/28511881/

10-11 23:05
查看更多