在递归调用时,python构造函数不返回None

Question

以下代码不返回None,而是一些神秘的" main _.link_list对象":

class link_list(object):
    """a link list class"""
    def __init__(self, list):
        super(link_list, self).__init__()
        pdb.set_trace()
        if list==[]:
            return None
        else:
            self.value = list[0]
            self.next = link_list(list[1:len(list)])

测试代码打印'False':

l=link_list([1,2,3])
print l.next.next.next==None

为什么？

Answer 1

.__init__() 不是一个真正的构造函数.

__init__作为构造函数？

无论您是否None从中返回,都将创建该对象.__init__().正如@Ignacio Vazquez-Abrams在评论中指出的那样,Python 期望 None作为返回值来自.__init__(); 无论如何你不能回报任何其他东西.如果您需要发出某种灾难性错误信号,则应提出异常.

在您的示例中,您可能应该有一个表示完整链表的类,带有"head"引用和"tail"引用,另一个类表示链表中的数据条目.然后可以通过检查是否可以测试链表类本身的空列表head is None.

编辑:经过一番深思,你的单班实施将会奏效; 只是我们需要设置.next到None内部.__init__().这是我对你的代码的编辑:

class link_list(object):
    """a link list class"""
    def __init__(self, lst):
        super(link_list, self).__init__()
        pdb.set_trace()
        if len(lst) > 1:
            self.value = lst[0]
            self.next = link_list(lst[1:])
            print "id == %d, linked in %d" % (id(self), id(self.next))
        elif len(lst) == 1:
            self.value = lst[0]
            self.next = None
            print "length-one case: id == %d" % id(self)
        else:
            self.value = None
            self.next = None
            print "length-zero case: id == %d" % id(self)

l=link_list([1,2,3])
print l.next.next.next is None

笔记:

• 我修复了缩进.

• 我使用lst而不是list变量名,以免影响内置类型list.

• 我添加了一些打印语句来帮助您观察正在发生的事情.

编辑:并且,为了完整性,这里是一个使用两个类的实现:一个表示列表并且可能是零长度的类,以及一个表示列表中一个条目的类.甲for环建立条目的链,并且可以建立从任何序列(包括一个迭代)的列表; 不使用切片,因此序列不必是列表.

class link_list_val(object):
    """one value for a linked list"""
    def __init__(self, value):
        self.value = value
        self.next = None

class link_list(object):
    """a link list class"""
    def __init__(self, seq):
        self.head = None

        for value in seq:
            x = link_list_val(value)
            if self.head is None:
                self.head = x;
                cur = x
            else:
                cur.next = x
                cur = x

l=link_list([1,2,3])
print l.head.next.next.next is None

编辑:这是另一个版本.这使用迭代来构建链表,而不是尾递归,而是使用单个类.诀窍是.__init__()函数需要知道它是构建一个完整的链表,还是仅仅创建一个用于构建链表的实例; 因此检查seq is None.如果用户传入一个序列,则.__init__()构建一个完整的链表,否则它只会使一个实例用作列表中的链接.

class link_list(object):
    """a link list class"""
    def __init__(self, seq=None):
        super(link_list, self).__init__()
        if seq is None:
            return
        pdb.set_trace()
        itr = iter(seq)
        try:
            self.value = next(itr)
        except StopIteration:
            self.value = None
            self.next = None
            return
        cur = self
        for value in itr:
            cur.next = link_list()
            cur = cur.next
            cur.value = value
        cur.next = None

l=link_list([])
print l.next is None
l=link_list([1,2,3])
print l.next.next.next is None

首先,我们从序列中获得一个新的迭代器.然后我们尝试从序列中提取一个值next().如果失败,我们有一个零长度的链表并返回它; 如果成功,我们将该值用于链表的头部,然后循环遍历序列中的其余值.

直接使用迭代器可能看起来很棘手,但我认为这是处理这种情况的最干净的方法,我们想从序列中拉出第一个项目然后遍历其余的项目,我们不想使用切片(因此只适用于实际列表).