这只是一个非常简单的代码,我的参考来自这里:http://www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/Map/skip-list-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
问题不在
searchEntry
的代码中,它似乎有正确的逻辑。问题是列表结构越来越混乱。我认为问题在于您在insert
中为列表添加新级别的代码。特别是这一位:关于这段代码,我最清楚的一点是,您没有创建任何新节点,只是修改了现有的节点,这就是破坏列表结构的原因。我认为,您需要创建新的
head
和tail
节点,并将它们链接到结构的顶部。(minus
和plus
不是您链接中描述的算法的一部分,因此我不确定您对它们做了什么。)可能您希望这样:相关问题 更多 >
编程相关推荐