1

以下代码没有返回 None 而是一些神秘的“主_.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)])

测试代码打印“假”：

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

为什么？

4

2 回答 2

6

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

__init__ 作为构造函数？

无论您是否None从.__init__(). 正如@Ignacio Vazquez-Abrams 在评论中指出的那样，Python期望 None返回值来自.__init__(); 无论如何，你不能返回任何东西。如果您需要发出某种灾难性错误的信号，则应引发异常。

在您的示例中，您可能应该有一个代表完整链表的类，具有“头”引用和“尾”引用，以及另一个代表链表中数据条目的类。然后可以通过检查是否为空列表来测试链表类本身head is None。

编辑：经过进一步思考，您的单类实现将起作用；只是我们需要设置.next为Noneinside .__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()。如果失败，我们有一个长度为零的链表并返回它；如果成功，我们将该值用作链表的头部，然后遍历序列中的其余值。

直接使用迭代器可能看起来很棘手，但我认为这是处理这种情况的最干净的方法，我们想从序列中提取第一个项目，然后循环其余的项目，我们不想使用切片（因此只能使用实际列表）。

于 2012-07-02T23:54:58.347 回答
1 
class Item(object):
    '''Linked list'''

    def __new__(cls, lst):
        '''Construct object (allocate the memory)'''
        if lst:
            return super(Item, cls).__new__(cls)

    def __init__(self, lst):
        '''Initialize object (already created)'''
        self.value = lst[0]
        self.next = self.__class__(lst[1:])

    def __repr__(self):
        '''Representate as string'''
        return "%s(%s) -> %s" % (
            self.__class__.__name__,
            self.value,
            repr(self.next)
        )

>>> items = Item([1,2,3])
>>> print items
Item(1) -> Item(2) -> Item(3) -> None
>>> items.next.next.next is None
True
于 2012-07-03T04:26:48.727 回答