有序双向链表

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

- xor

---

@downvoters：请解释一下。我可以看到，楼主已经清晰地陈述了问题，并尽力去解决，但仍然无法找到解决方案，需要帮助。他可能不太擅长 Python，但我们应该帮助他，而不是投票贬低他。 - Abhijit

请您详细解释一下“有序双向链表”的精确含义？说明它应该如何运作，需要实现哪些方法等等…… - Inbar Rose

@eumiro 谢谢...但还是没有改善... - xor

我并没有看到你的解决方案有什么特别不正确的地方。根据我的经验，像这样递归遍历列表的插入函数有些奇怪，但是这样做并没有什么问题。你能告诉我们你遇到的问题吗？比如一系列插入操作后列表出现错误的例子？ - ken.ganong

@ken说的是实话...我一直在提交给评分者，但每次都得到错误的答案...但我无法找到原因... 它在测试条件下运行良好... 对于那些认为我想让你们帮我做作业的人...我是在没有时间提交之后才问的...[我也不喜欢作弊] - xor

Answer 1

问题出现在这行代码（当你向另一个方向移动时会有类似的代码）：

newFrob.setBefore(atMe.getBefore)

你在atMe.getBefore之后缺少一组括号，所以你最终会把该绑定方法本身传递给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，这让我找到了代码中的错误。

- Blckknght