我正在尝试使用Python实现Skiplist.你能帮我吗?非常简单

Question

这只是一个非常简单的代码，我的参考如下：http://www.mathcs.emory.edu/~张/课程/323/教学大纲/地图/跳过列表impl.html#why-q

我认为insert函数是可以的，但当我尝试使用get()函数时，它不会返回任何内容，而是在searchEntry()部分中无休止地循环。我不知道怎么了。在insert()功能中，searchEntry()运行良好。它返回对floorEntry(k)条目的引用，该条目包含一个小于需要插入skiplist中的密钥的密钥。请帮我找出searchEntry()函数中错误的来源。对不起，我不太擅长这个。非常感谢。

from QuadLinkedList import QLLNode
import random
class Skippy:

    def __init__(self):
        self._p1 = QLLNode("MINUS_INF")
        self._p2 = QLLNode("PLUS_INF")
        self._head = self._p1
        self._tail = self._p2
        self._p1.setNext(self._p2)
        self._p2.setPrev(self._p1)
        self._height = 0
        self._n = 0
    def insert(self, key, value):
        p = self.searchEntry(key)
        print "p = " + str(p.getKey())
        q = QLLNode(key, value)
        q.setPrev(p)
        q.setNext(p.getNext())
        p.getNext().setPrev(q)
        p.setNext(q)
        i = 0
        while random.randint(0,1) != 0:
            if i >= self._height:
                self._height += 1
                newHead = QLLNode("MINUS_INF")
                newTail = QLLNode("PLUS_INF")
                newHead.setNext(newTail)
                newHead.setDown(self._head)
                newTail.setPrev(newHead)
                newTail.setDown(self._tail)
                self._head.setUp(newHead)
                self._tail.setUp(newTail)
                self._head = newHead
                self._tail = newTail
            while p.getUp() == None:
                p = p.getPrev()
            p = p.getUp()
            e = QLLNode(key,None)
            e.setPrev(p)
            e.setNext(p.getNext())
            e.setDown(q)
            p.getNext().setPrev(e)
            p.setNext(e)
            q.setUp(e)
            q = e
            i += 1
        self._n += 1
        return None
    def get(self, key):
        p = self.searchEntry(key)
        if key == p.getKey():
            return p.getElement()
        else:
            return "There's None!"
    def searchEntry(self, key):
        p = self._head
        while True:
            while p.getNext().getKey() != "PLUS_INF" and p.getNext().getKey() <= key:
                p = p.getNext()
            if p.getDown() != None:
                p = p.getDown()
            else:
                break
        return p

Answer 1

问题不在searchEntry的代码中，它似乎具有正确的逻辑。问题是列表结构变得一团糟。我认为问题在于您在insert中为列表添加新级别的代码。特别是这个比特：

       if i >= self._height:    #make an empty level
            self._height += 1
            self._minus.setNext(self._plus)
            self._minus.setDown(self._head)
            self._plus.setPrev(self._minus)
            self._plus.setDown(self._tail)
            self._head.setUp(self._minus)
            self._tail.setUp(self._plus)
            self._head = self._minus
            self._tail = self._plus

关于这段代码，我最清楚的一点是，你没有创建任何新的节点，只是修改现有的节点，这就是破坏列表结构的原因。我认为，您需要创建新的head和tail节点，并将它们链接到结构的顶部。(minus和plus不是你链接中描述的算法的一部分，所以我不确定你在用它们做什么。(也许你想要这样的东西：

       if i >= self._height:    #make an empty level
            self._height += 1
            newHead = QLLNode("MINUS_INF")
            newTail = QLLNode("PLUS_INF")
            newHead.setNext(newTail)
            newHead.setDown(self._head)
            newTail.setPrev(newHead)
            newTail.setDown(self._tail)
            self._head.setUp(newHead)
            self._head = newHead
            self._tail.setUp(newTail)
            self._tail = newTail