时间戳

首页 > 解决方案 > 对链表进行排序（交换节点）

python - 对链表进行排序（交换节点）

问题描述

我正在尝试对包含此类节点的 LinkedList 进行排序：

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

这个想法是获取一个序列（列表/元组/字符串），从中创建一个 LinkedList：

def __init__(self, seq):
    self.front = self.Node(None)
    node = self.front
    for item in seq:
        node.next = self.Node(item)
        node = node.next

排序的逻辑是，在每次迭代中遍历链表，将每个项目与第一个项目进行比较，如果它更小/更大，则执行交换，继续遍历链表并执行相同的比较和操作。此处显示：

    def min_sort(self, reverse):
        self.count = 0
        first = self.front
        while first.next is not None:
            print(self.get_list())
            self.progress(first, reverse)
            self.count += 1
            first = first.next

    def progress(self, first, reverse):
        node = first
        if (node is None): return
        while True:
            node = node.next
            if node is None or node.next is None: break

            if (reverse):
                if (first.next.data < node.next.data):
                    self.vymen(first, node, node.next)
            else:
                if (first.next.data > node.next.data):
                    self.vymen(first, node, node.next)

问题在于交换本身（函数self.vymen（...）），它通常使用基本的数字链接列表，但是当加载一个字符串时，例如“我在Python中编码”，空格不会被交换到正确的位置使整个结果一团糟。交换本身是：

    def vymen(self, first, prev, swap):
        prevX, currX, prevY, currY = first, first.next, prev, swap

        if (self.front.next.data == swap.data): return
        if (currX is None or currY is None): return

        if (currX != prevY):
            if (prevX is not None): prevX.next = currY
            else: self.front = currY

            if (prevY is not None): prevY.next = currX
            else: self.front = currX

            temp = currX.next
            currX.next = currY.next
            currY.next = temp

        else:
            temp = currY.next
            currX.next = temp
            currY.next = currX
            prevX.next = currY

正如我所看到的，它实际上只是空间的一个问题，我不明白问题是什么，因为它在开始时交换了第一个空间，而不是其余的。如果有人能够指出错误或告诉我发生了什么，我将不胜感激:)

标签： pythonsortinglinked-list

解决方案

您的代码中有两个问题：

  • 下面的语句vymen是麻烦的原因：

    if (self.front.next.data == swap.data): return

    其目的是在交换节点的数据相等时避免不必要的交换。但是它不应该引用self.front.next，而是curX- 因为那是要交换的节点：

    if currX.data == currY.data:
    return

  • if紧随其后的条件此时没有用：

    if (currX is None or currY is None): return

    ...正如我们在这一点上已经提到的swap.data（即）。currY.data因此，如果这确实可行，则应在引用currY.dataor之前对其进行检查currX.data。所以把它和前面的结合起来if：

    if currX is None or currY is None or currX.data == currY.data:
    return

  • 当交换两个连续的（！）节点时，主循环progress将跳过一个节点。在这种情况下，在调用 之前，将变为将跳过。所以在调用之后，仍然会引用同一个节点，但它在列表中的位置更远。结果，有一个节点不会有循环的迭代。这是导致错误输出的原因，即使是纯数字也是如此。为了解决这个问题，您可以进行调整，使其返回与调用开始时处于相同位置的节点。然后调用者应该将该引用重新分配给它的变量。vymennodecurrXnode.nextnodevymennodenode

其他一些评论：

  • 在 Python 中，不需要在if条件周围加上括号

  • 在vymen中，以下条件应始终为真：

    if (prevX is not None): prevX.next = currY
else: self.front = currY

    这绝不应该是真的，因为您已经将链表设计为在其前面有一个哨兵节点（具有 value None）。所以你甚至不想self.front = currY执行！prevX永远不应该None。它也绝不会None以您调用此函数的方式出现。因此，只需删除此构造并分配：

    prevX.next = currY

    紧随其后的也应该发生同样的情况if..else。

  • 不应该需要它的vymen最后一个参数 ( swap)，因为它应该始终是 的值prev.next。所以函数可以像这样开始：

    def vymen(self, first, prev):
    prevX, currX, prevY, currY = first, first.next, prev, prev.next

    调用将是（还要注意返回值的分配）：

    node = self.vymen(first, node)

  • 遗憾的是，在 的函数头之后，您定义了与andvymen完全相同的新变量：和。为什么不立即这样命名参数变量呢？firstprevprevXprevY

  • 遗憾的是，在progress您的正文中，第一个语句是ifwith a 。您可以更好地重写它，以便在语句中具有条件breakwhile Truewhile

综上所述，这是有问题的两种方法的结果代码：

    def progress(self, first, reverse):
        if first is None or first.next is None:
            return
        node = first.next
        while node.next:  # Use a condition to exit instead of break
            if reverse:
                if first.next.data < node.next.data:
                    # Take the return value, and pass one argument less
                    node = self.vymen(first, node)  
            else:
                if first.next.data > node.next.data:
                    # Take the return value, and pass one argument less
                    node = self.vymen(first, node)
            node = node.next

    def vymen(self, prevX, prevY):  # Use the desired variable names
        # No need for the swap argument
        currX, currY = prevX.next, prevY.next

        # Corrected comparison of the two nodes' data, and put the 
        #   conditions in the right order:
        if currX is None or currY is None or currX.data == currY.data:
            return prev # return the node at the position of prev 

        if currX != prevY:
            # Make the following assignments unconditionally
            prevX.next = currY
            prevY.next = currX

            temp = currX.next
            currX.next = currY.next
            currY.next = temp
            # Return the reference of the node that is in the position
            #    of prev: it is still in the same position:
            return prev
        else:
            temp = currY.next
            currX.next = temp
            currY.next = currX
            prevX.next = currY
            # Return the reference of the node that is in the position
            #    of prev: it has moved, so now it is...:
            return currY

推荐阅读