Python中的单链表搜索

Question

我想在一个链表中查找某个值或字符，并返回这个值或字符在链表中出现的次数。另外，如果我使用递归会不会比用尾递归更简单呢？

class MyList():
    __slots__=('head','size')

class Empty():
    __slots__=()

class NonEmpty():
    __slots__=('data','next')

def mkMyList():
    lst = MyList()
    lst.head = mkEmpty()
    lst.size = 0
    return lst

def mkEmpty():
    return Empty()

def mkNonEmpty(data,lst):
    node = NonEmpty()
    node.data  = data
    node.next = lst
    return node

def count(l, value, c = 0):
    l = mkMyList()
    if l.head != value:
        l.head = l.head.next
    if l.head == value:
        return count(l.head.next, value, c + 1)
    if l.size == 0:
        return c

当我尝试测试的时候，我得到了这个：

count(s,'s',c= 0)
Traceback (most recent call last):
  File "<pyshell#2>", line 1, in <module>
    count(s,'s',c= 0)
  File "C:\Users\Qasim\Desktop\Linked Lists.py", line 30, in count
    l.head = l.head.next
AttributeError: 'Empty' object has no attribute 'next'

\

Answer 1

跟踪你的代码：

 l = mkMyList() # => head = Empty()
 if l.head != value: # True since head is Empty()
     l.head = l.head.next # Empty does not have a ".next" attribute

这就是追踪信息（Traceback）告诉你的内容。

补充说明：还有两点： (1) 我不太明白为什么 count 会调用 mkMyList，感觉你本来是想在函数参数中传递列表 l。 (2) 我猜你想把检查大小的 if 语句放在这个函数的最前面：

if l.size == 0:
    return c

Answer 2

我看到的问题是，count里的列表从来没有正确初始化。在mkMyList()函数中，head元素被设置为Empty，而Empty没有next这个属性。在count()函数中，你只用了mkMyList()。这就意味着l.head是Empty，所以它不可能有next这个属性。要解决这个问题，我建议根据给定的输入来实例化列表l。

关于递归的问题：不，写一个尾递归函数和普通递归函数之间几乎没有区别。

Answer 3

与其使用递归，我更倾向于使用迭代器模式。在你的问题背景下，这里有一种实现方法：

class LinkedList(object):

    class Node(object):
        __slots__ = ('prev', 'next', 'value')

        def __init__(self, prev=None, next=None, value=None):
            self.prev = prev
            self.next = next
            self.value = value

    def __init__(self, iterable=[]):
        self.head = LinkedList.Node() # dummy node
        self.tail = self.head
        self.size = 0
        for item in iterable:
            self.append(item)

    def __iter__(self):
        current = self.head
        while True:
            if current.next is not None:
                current = current.next
                yield current.value
            else:
                raise StopIteration

    def append(self, value):
        self.tail.next = LinkedList.Node(prev=self.tail, value=value)
        self.tail = self.tail.next
        self.size += 1

    def pop(self):
        if self.size > 0:
            value = self.tail.value
            self.tail = self.tail.prev
            self.tail.next = None
            self.size -= 1
            return value
        else:
            raise IndexError('pop from empty list')

    def count(self, value):
        cumsum = 0
        for item in self:
            if item == value:
                cumsum += 1
        return cumsum

通过定义一个叫做 Python特殊方法 的 __iter__，我们可以按顺序访问一个 LinkedList 的元素，方法如下：

l = LinkedList([1, 2, 3, 3, 3, 4, 5])
for value in l:
    print(value)

这样一来，想要实现的 count 方法就变得简单明了。

需要注意的是，我使用了Python的生成器语法来实现 __iter__，你可以在 这里了解更多关于生成器和 yield 语句的内容。