python - 无法合并两个排序的单链表，因为“类型对象'_Node'没有属性'_element'”

Question

我正在制作自己的 merge_list 函数。我已经创建了 SList() 类和 _Node() 类。但是当我在 merge_list 中输入两个排序列表时，merge_list 函数无法比较两个节点的值，显示type object '_Node' has no attribute '_element'，但类 _Node 具有 _element 属性（我也尝试了元素，但它也不起作用）。我的功能有什么问题？？

这是我的部分代码class SList()和class _Node()完整代码merge_list

class SList:
    class _Node:
        def __init__(self, element, next=None):
            self._element = element
            self._next = next

        def element(self):
            return self._element

        def next(self):
            return self._next

        def set_element(self, element):
            self._element = element

        def set_next(self, next):
            self._next = next

    def __init__(self, head=None):
        self._head = head

    def insert_first(self, element):
        self._head = self._Node(element, self._head)

    def insert_after(self, element, p):
        new_node = self._Node(element, p.next())
        p._next = new_node

. . . 和我的 merge_list 函数

def merge_list(s1, s2):
    s3 = SList()
    s3._Node(None, None)
    prev = s3

    while s1 != None and s2 != None:
        if s1._Node._element<= s2._Node._element: # this line is the problem
            prev.next = s1
            s1 = s1.next
        else:
            prev.next = s2
            s2 = s2.next
        prev = prev.next

    if s1 == None:
        prev.next = s2
    elif s2 == None:
        prev.next = s1

    return s3.next

在我做了这个函数之后，我输入了两个这样的排序列表并调用了 merge_list 函数

if __name__ == "__main__":
    s1 = SList()
    s1.insert_first(1)
    s1.insert_first(3)
    s1.insert_first(5)
    s1.insert_first(7)
    s1.insert_first(9)
    s1.insert_first(11)
    s1.insert_first(13)
    print(f"s1 :", s1)


    s2 = SList()
    s2.insert_first(2)
    s2.insert_first(4)
    s2.insert_first(6)
    print(f"s2 : ", s2)
    merge_list(s1, s2)

输出是

Traceback (most recent call last):
s1 : 13 -> 11 -> 9 -> 7 -> 5 -> 3 -> 1 -> None: 7 element(s)
s2 :  6 -> 4 -> 2 -> None: 3 element(s)
  File "", line 334, in <module>
    merge_list(s1, s2)
  File "", line 151, in merge_list
    if s1._Node._element<= s2._Node._element:
AttributeError: type object '_Node' has no attribute '_element'

似乎 s1, s2 列表已成功创建，但无法比较节点的值。merge_list 函数有什么问题？

标签： pythonfunctiondata-structuresmergesingly-linked-list

Answer 1

让我们一步一步来

代码分析：

class SList:
    class _Node:

note为什么要在 SList 类中定义 Node 类？这不是常见的做法，除非您从不希望从 Slist 外部访问节点（即使那样）

        def __init__(self, element, next=None):
            self._element = element
            self._next = next

        def element(self):
            return self._element

        def next(self):
            return self._next

        def set_element(self, element):
            self._element = element

        def set_next(self, next):
            self._next = next

注意初始化/获取器和设置器。到现在为止，一切都说得通。但是，我个人更喜欢@attrs 库。但我们稍后会谈到这一点。

    def __init__(self, head=None):
        self._head = head

    def insert_first(self, element):
        self._head = self._Node(element, self._head)

    def insert_after(self, element, p):
        new_node = self._Node(element, p.next())
        p._next = new_node


def merge_list(s1, s2):
    s3 = SList()
    s3._Node(None, None)
    prev = s3

    while s1 != None and s2 != None:
        if s1._Node._element<= s2._Node._element: # this line is the problem

好吧，由于评论中提到的原因，这根本行不通： _Node 类没有 _element 属性。但实例确实如此。

            prev.next = s1

prev是s3哪一个SList因此不应该具有下一个属性？

            s1 = s1.next
        else:
            prev.next = s2
            s2 = s2.next
        prev = prev.next

    if s1 == None:
        prev.next = s2
    elif s2 == None:
        prev.next = s1

    return s3.next

第一次尝试帮助（注意：这是一个基于 OP 提供的工作解决方案，而不是尝试编写干净的代码。）

class _Node:
    def __init__(self, element, next=None):
        self._element = element
        self._next = next

    @property
    def element(self):
        return self._element
    @property
    def next(self):
        return self._next

    def set_element(self, element):
        self._element = element

    def set_next(self, next):
        self._next = next

class SList:
    def __init__(self, head=None):
        self._head = _Node(head)

    @property
    def head(self):
        return self._head 

    def insert_first(self, element):
        self._head = _Node(element, self._head)

    def insert_after(self, element, p):
        new_node = _Node(element, p.next())
        p._next = new_node

def merge_list(s1, s2):
    s3 = SList()
    prev = s3._head
    head_s1 = s1._head
    head_s2 = s2._head

    while (head_s1._element != None) and (head_s2._element != None):
        if head_s1._element<= head_s2._element: # this line is the problem
            prev.set_next(head_s1)
            head_s1 = head_s1.next
        else:
            prev.set_next(head_s2)
            head_s2 = head_s2.next
        prev = prev.next

    if head_s1 == None:
        prev.set_next(head_s1)
    elif head_s2 == None:
        prev.set_next(head_s2)

    return s3