python - python递归中的链表

Question

我在 python 中有一个 LinkedList 的简单实现。如何在方法中使用递归？我知道递归是如何工作的，但我如何将 self 与递归一起使用。如果有人可以修复我的代码，那就太好了，但我对解释更感兴趣，因此我可以用不同的方法使用它。

链表代码:

class Node:
    def __init__(self, item, next):
        self.item = item
        self.next = next

class LinkedList:
    def __init__(self):
        self.head = None

    def add(self, item):
        self.head = Node(item, self.head)

    def remove(self):
        if self.is_empty():
            return None
        else:
            item = self.head.item
            self.head = self.head.next
            return item

    def is_empty(self):
        return self.head == None 

我的代码是:

def count(self, ptr=self.head):
    if ptr == None:
        return '0'
    else:
        return 1 + self.count(ptr.next)

它给我一个错误:

def count(self, ptr=self.head):
NameError: name 'self' is not defined

非常感谢任何帮助。

Answer 1

在 Python 中，默认参数是不是在运行时计算的表达式。这些是在评估 def 本身时评估的表达式。所以对于一个 class 通常是在第一次读取文件的时候。

结果，在那一刻，没有self。 self 是一个参数。所以这仅在您调用函数时可用。

您可以通过使用例如 None 作为默认值并执行检查来解决该问题。但是这里我们不能使用None，因为你已经给它赋予了特殊的含义。然而，我们可以构建一个dummy 对象，并使用它:

<b>dummy = object()</b>

def count(self, ptr=<b>dummy</b>):
    <b>if ptr is dummy:
        ptr = self.head</b>
    if ptr == None:
        return '0'
    else:
        return 1 + self.count(ptr.next)

您的代码的另一个问题是您返回一个表示零的字符串。因为你不能简单地添加一个整数和一个字符串，这会出错。所以你应该返回一个整数:

dummy = object()

def count(self, ptr=dummy):
    if ptr is dummy:
        ptr = self.head
    if ptr == None:
        return <b>0</b>  # use an integer
    else:
        return 1 + self.count(ptr.next)