我试图写一个链表有哨兵根据CLRS的书。出于某种原因,我的remove函数会将LL块移到要删除的节点上。附件是我的密码。任何建议都将不胜感激。你知道吗
class Node():
def __init__(self,v):
self.value = v
self.next = None
self.prev = None
def getValue(self):
return self.value
def changeValue(self,v):
self.value = v
def getNext(self):
return self.next
def getPrev(self):
return self.prev
def setNext(self,newNext):
self.next = newNext
def setPrev(self,newPrev):
self.prev = newPrev
class List(Node):
def __init__(self):
self.nil = Node(None)
def addNode(self,v):
a = Node(v)
a.setNext(self.nil.next)
a.setPrev(self.nil)
self.nil.next = a
def length(self):
count = 0
a = self.nil
while(a.next != None):
count += 1
a = a.getNext()
return count
def search(self,v):
a = self.nil
while(a.next != None):
if (a.value == v):
return True
a = a.getNext()
return False
def remove(self,v):
a = self.nil.next
breakloop = 0
while((a.next != None) and (breakloop == 0)):
if (a.value == v):
a.prev.next = a.next
a.next.prev = a.prev
breakloop = 1
a = a.getNext()
def printList(self):
a = self.nil.next
while(a.next != None):
print(a.value)
a =a.getNext()
print(a.value)
a = List()
a.addNode(4)
a.addNode(7)
a.addNode(2)
a.addNode(6)
a.addNode(5)
a.addNode(8)
a.addNode(1)
a.addNode(14)
a.addNode(13)
a.addNode(17)
a.addNode(18)
a.printList()
a.remove(13)
a.printList()
输出将
18 17 13 14 1 8 5 6 2 7 4
14 1 8 5 6 2 7 4
bug在
addNode
函数中,所有节点的.prev
节点是self.nil
使用以下方法:
会解决你的问题。您可能希望将此逻辑放在
setPrev
和setNext
函数中(以确保所有a == a.next.prev
和a == a.prev.next
在任何时候都适用于除端点以外的所有a
)。你知道吗@tcaswell正确地诊断了代码的问题:您没有正确地设置节点上的
prev
链接,这些链接以前是self.nil.next
。然而,我认为他的解决方案并不理想。以下是我的建议:以下是问题的即时解决方法:
但是,当列表为空时,这将无法正常工作,因为
self.nil.next
在开始时是None
。但是我们可以通过在List
构造函数中创建self.nil
链接到自身来修复它:现在,
self.nil
将始终有一个有效的节点,因为它是next
和prev
值。你知道吗您需要更改
removeNode
和printList
循环来检查self.nil
,而不是None
。你知道吗相关问题 更多 >
编程相关推荐