双向链表python

Question

我使用的是Python 3.0，并且我必须创建以下内容：

1)将名为Setplus的ADT实现为有序的双向链表，其中项在列表中从最小项到最大项排序

因此，首先我创建了一个名为Double_Node的模块

class Double_Node:
    """
    Fields: value stores any value
            next points to the next node in the list
            prev points to the previous node in the list
    """

    ## Double_Node() produces a newly constructed empty node.
    ## __init__: Any -> Node
    def __init__(self, value, prev = None, next = None):
        self.value = value 
        self.prev_node = prev
        self.next_node = next

    def get_next (self):
        return self.next_node
    def set_next (self, n):
        self.next_node = n
    def get_prev (self):
        return self.prev_node
    def set_prev (self, p):
        self.next_prev_node = p
    def get_value (self):
        return self.value
    def set_value (self, d):
        self.value = d


    ## print(self) prints the value stored in self.
    ## Effect: Prints value.
    ## __str__: Node -> Str
    def __str__(self):
        return str(self.value)

然后我创建了一个名为Setplus的类：

class Setplus:
    """
    Field: _head points to the first node in the linked list
           _tail points to the last node in a linked list
    """


    ## Setplus() produces a newly constructed empty setplus.
    ## __init__: -> Setplus
    def __init__(self):
        self._head = None
        self._tail = None

    ## self.empty() produces True if self is empty.
    ## empty: Setplus -> Bool
    def empty(self):
        return self._head == None

    ## value in self produces True if value is an item in self.
    ## __contains__: Setplus Any -> Bool
    def __contains__(self, value):
        current = self._head
        while current:
            if current.get_value == value:
                return True
            else:
                current = current.get_next
        return False

    ## self.distinct() produces True if all items are distinct.
    ## distinct: Setplus -> Bool
    #def distinct(self):

    ## count(value) produces the number of occurrences of value.
    ## count: Setplus Any -> Int
        def count(self, value):
            counter = 0
            current = self._head
            while current != None:
                if current.value == value:
                    counter += 1
                    print (counter)
                else:
                    current = current.next
            return counter

    ## self.add(value) adds value as an item in order.
    ## Effects: Mutates self.
    ## add: Setplus Any -> None 
    def add(self, value):
        new_node = Double_Node(value)
        if self.head == None:
            self.head = new_node
        if self.tail != None:
            slef.tail.next = new_node

        self.tail = new_node

我在创建一个包含方法count和add时遇到了问题，count方法计算值的数量，add方法以正确的非递减顺序添加节点。

提前感谢

Answer 1

代码中的第一个主要问题是打字错误和错误的名称。

在你的一个函数中有一个明显的拼写错误，slef而不是self。

还有很多地方，您使用了两个不同的名称来表示应该是相同的属性(例如，_head和head或next和next_node )。

您还在Double_Node类中定义了getter和setter函数，但是当您尝试在Setplus中使用它们时，只能引用该方法，而不调用它。几乎可以肯定的是，行current = current.get_next应该是current = current.get_next()。

简单介绍一下getter和setter函数: Python类通常不需要它们。直接使用属性即可。如果您后来发现需要更多花哨的行为(例如，验证新设置的值或动态生成请求的值)，您可以使用property更改类，将属性访问语法转换为方法调用。在其他编程语言中，您通常不能以这种方式改变属性访问，因此鼓励使用getter和setter方法，以便从一开始就拥有可扩展的API。

(请注意，如果您是学生，您的讲师可能不熟悉Python，因此他们可能希望您编写getter和setter，即使它们在Python代码中通常不是很好的风格。考虑学习如何使用property，您可能会在以后让他们大吃一惊！)

我会去掉Double_Node中的getter和setter函数，这只是一个风格问题。但是，如果你打算保留它们(可能是因为你的任务需要它们)，那么你应该在你的代码中实际使用它们！

最后，为了得到您需要帮助的实际问题，以排序的顺序插入到链表中，您可能想要这样做：

def add(self, value):
    new_node = Double_Node(value)
    if self._head == None: # inserting into empty list
        self._head = self._tail = new_node

    else: # inserting into a list that contains at least one node already
        current = self._head
        while current and current.value < value: # find a node to insert before
            current = current.get_next()

        if current: # not inserting at end of list
            prev = current.get_prev()
            if prev: # not inserting at start
                new_node.set_prev(prev)
                prev.set_next(new_node)

            else: # inserting at start
                self._head = new_node

            new_node.set_next(current)
            current.set_prev(new_node)

        else: # inserting at end
            new_node.set_prev(self._tail)
            self._tail.set_next(new_node)
            self._tail = new_node

在按排序顺序插入add之后，其他方法可以利用这一点。例如，如果__contains__发现的值大于它要查找的值，它可以停止搜索，并且count将在一个连续的组中找到所有匹配值。

Answer 2

如果您想使用现有的Python类来完成此任务，您可能会发现这些类很有用。

双向链表：

来自collections模块的deque：

https://docs.python.org/3/library/collections.html#collections.deque

数据结构从小到大排序如下：

heapq模块，它实现了一个最小堆。

https://docs.python.org/3/library/heapq.html