python - 有序双向链表

Question

好的，作业中的一个问题说要创建一个有序的双向链表......这样每个对象在字典序上较小的名称都出现在另一个“之前”......就像字典中的名称......也有相同名称的对象可以按任意顺序排列...

要链接两个对象，我有 setBefore() 和 setAfter() 方法...我已经做了这么多......但仍然不知道我哪里做错了......可能你们的一些指导可以帮助我......

atMe 是双向链表中已经存在的对象，newFrob 是要插入的对象...

def insert(atMe, newFrob):
    if newFrob.myName() < atMe.myName():
        if atMe.getBefore() == None:
            atMe.setBefore(newFrob)
            newFrob.setAfter(atMe)
        elif atMe.getBefore().myName()<newFrob.myName():
            atMe.getBefore().setAfter(newFrob)
            newFrob.setBefore(atMe.getBefore)
            atMe.setBefore(newFrob)
            newFrob.setAfter(atMe)
        else:
            insert(atMe.getBefore(),newFrob)

    elif newFrob.myName() > atMe.myName():
        if atMe.getAfter() == None:
            atMe.setAfter(newFrob)
            newFrob.setBefore(atMe)
        elif atMe.getAfter().myName()>newFrob.myName():
            atMe.getAfter().setBefore(newFrob)
            newFrob.setAfter(atMe.getAfter)
            atMe.setAfter(newFrob)
            newFrob.setBefore(atMe)
        else:
            insert(atMe.getAfter(),newFrob)

    elif newFrob.myName()==atMe.myName():
        if atMe.getAfter() != None:
            newFrob.setAfter(atMe.getAfter())
        newFrob.setBefore(atMe)
        if atMe.getAfter() != None:
            atMe.getAfter().setBefore(newFrob)
        atMe.setAfter(newFrob)

这是要使用的 Frob 类...

class Frob(object):
    def __init__(self, name):
        self.name = name
        self.before = None
        self.after = None
    def setBefore(self, before):
        self.before = before
    def setAfter(self, after):
        self.after = after
    def getBefore(self):
        return self.before
    def getAfter(self):
        return self.after
    def myName(self):
        return self.name

其中 Before 和 After 是指向双链表中左右对象的链接...来自此类的对象将被插入到双链表中...

例子:

a=Frob('foo')
b=Frob('bar')
c=Frob('frob')
d=Frob('code')

code                             output
insert(a,b)                   bar->foo
insert(a,c)                   bar->foo->frob
insert(b,d)                   bar->code->foo->frob

现在假设

code                             output
insert(b,Frob('code'))        bar->code->code->foo->frob

Answer 1

问题出在这一行(当您向另一个方向移动时，问题出在这一行中):

newFrob.setBefore(atMe.getBefore)

您在 atMe.getBefore 之后缺少一组括号，因此您最终将绑定(bind)方法本身传递给 newFrob.setBefore 而不是将要传递的值由该方法返回。这是一个很容易犯的错字，所以我不会因为在你的作业中遗漏它而感到难过。

我通过尝试以下插入序列并检查值发现了错误(我已经总结了那些工作正常的评论):

>>> a = Frob("a")
>>> b = Frob("b")
>>> c = Frob("c")
>>> d = Frob("d")
>>> insert(a, b) # list is a<->b
>>> insert(a, d) # list is a<->b<->d
>>> insert(a, c) # list is a<->b<->c->?
>>> c.getAfter()
<bound method Frob.getAfter of <__main__.Frob object at 0x000000000318EBA8>>

最后提到的那个对象是b，这让我找到了代码中的错误。