增加链表搜索功能

Question

我打算在python链表中添加一个搜索功能。它旨在搜索一个字符串是否在链表中（链表的每个节点都有一个词）。例如，如果链表是：I -> am -> a -> python -> developer。如果我搜索文本“python”，它将返回 True，如果我搜索文本“apython”，它将返回 True，但如果我搜索“java”或“ajava”，它将返回 false。我如下编写代码，但搜索功能无法使用。我不确定我是否应该添加递归函数来解决这个问题。

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


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

    def append(self, new_node):
        curr = self.head
        if curr:
            while curr.next:
                curr = curr.next
            curr.next = new_node
        else:
            self.head = new_node

    def search(self, text, cur):
        if cur.value == text:
            return True
        while cur.next != self.head and cur.next != None:
            if cur.next:
                cur = cur.next
                if cur.value == text:
                    return True
        return False

Answer 1

您的代码仅测试文本与单个节点值完全匹配的情况。

其他备注：

• cur.next != self.head

  永远不会是真的。根据定义，

  head

  节点是列表的第一个节点，因此它永远不会是给定节点之后的 successor。

• if cur.next

  是矫枉过正，因为那个条件总是为真 - 这就是为什么

  while

  循环还没有退出的原因。

• if cur.value == text

  在您的代码中出现两次。这应该没有必要。应用DRY.

但如前所述，主要问题是没有代码尝试将节点与给定文本的part匹配。

解决这个问题的方法之一是编写两个函数：一个检查给定节点是否是一系列节点的start，这些节点一起匹配给定文本。另一个函数可以在列表的每个节点上调用第一个函数。如果其中任何一个导致成功，那么搜索就成功了。

这是代码：

    def startswith(self, text, cur):
        while cur and text.startswith(cur.value):
            text = text[len(cur.value):]
            if not text:
                return True
            cur = cur.next
        return False
    
    def search(self, text, cur):
        if not text:  # Boundary case
            return True  # Or False, whatever you expect to happen
        while cur and not self.startswith(text, cur):
            cur = cur.next
        return cur is not None

运行示例场景的示例代码：

lst = LinkedList()
for word in "I am a python developer".split(" "):
    lst.append(Node(word))

print(lst.search("apython", lst.head))  # True