尝试为双向链表编写交换位置的函数

Question

我一直在尝试用Python实现一个简单的链表作为代码练习，虽然我大部分功能都已经实现了（比如插入、删除、漂亮打印、交换两个节点的内容），但我在交换两个节点的部分卡了好几天。

我在网上查了一下，大多数人似乎建议要么删除再插入节点，要么交换节点的数据。这两种方法都很好用，但我想挑战自己，看看能不能用“正确”的方式来交换节点。

理想情况下，我希望能有一个通用的函数，能够处理所有边界情况（比如移动到开头、结尾和随机交换节点）。这比我想象的要难得多。

我用纸和笔做了一些实验，也在网上找了一些资料，发现了以下讨论和示例实现：

我遇到的问题是我的 node1.next 和 node2.prev 被交换了，而且我的 node2.next 指向了自己，而不是链表中的下一个节点。

示例实现页面上的评论专门提到了这个问题，并说在他的实现中不应该发生这种情况。

我似乎搞不清楚自己哪里出错了。我想我可以“作弊”，强制它们在最后取正确的值，但这样在节点是第一个或最后一个时会出现很多问题。

__author__ = 'laurens'
from django.core.exceptions import ObjectDoesNotExist
import logging
import copy

logging.basicConfig(level=logging.DEBUG)
logger = logging.getLogger(__name__)

class DoublyLinkedList(object):
    """This class implements a basic doubly linked list in Django, it depends
    on a Django model with the following field:

    id : PK
    prev: integer previous node
    data_field: Foreign key
    next: integer next node

    the prev and next fields don't need to be self-referencing

    When instantiating the class you have to link this class to a Django model
     and specify a data field. The data field can link to a foreign key
     or contain data
    """

    def __init__(self, doubly_linked_list_model, data_field):
        self.doubly_linked_list_model = doubly_linked_list_model
        self.data_field = data_field

    def get_node_from_node_id(self, node_id=None):
        """This function returns the node associated with a certain node_id"""
        if node_id is None:
            node = None
        else:
            try:
                node = self.doubly_linked_list_model.get(id=node_id)
            except ObjectDoesNotExist:
                node = None

        return node

    @staticmethod
    def _update_node(node, prev=None, next=None):

        node.prev = prev
        node.next = next

        logger.debug('updating node: %s', node.id)
        logger.debug('node.prev = %s', node.prev)
        logger.debug('node.next = %s', node.next)

        try:
            node.save()
        except Exception as e: #Todo: specify this
            logger.debug('Error saving node: %s', node.id)

    def move_node(self, node1=None, node2=None):
        """
        This function swaps the position of node1 with the position of node2
        """

        #swapping two nodes!
        logger.debug('Swapping two random nodes!: %s, %s', node1.id, node2.id)

        # Swapping next nodes
        logger.debug('Swapping next node')
        tmp = copy.deepcopy(node1.next)

        self._update_node(node=node1,
                          prev=node1.prev,
                          next=node2.next)

        #Todo: Check if tmp changes or is stored as a copy
        self._update_node(node=node2,
                          prev=node2.prev,
                          next=tmp)

        if node1.next is not None:
            logger.debug('Connect the next node to node 1')
            node_next = self.get_node_from_node_id(node1.next)
            self._update_node(node=node_next,
                              prev=node1.id,
                              next=node_next.next)

        if node2.next is not None:
            logger.debug('Connect the next node to node 2')
            node_next = self.get_node_from_node_id(node2.next)
            self._update_node(node=node_next,
                              prev=node2.id,
                              next=node_next.next)

        logger.debug('Swap prev nodes')
        tmp = copy.deepcopy(node1.prev)

        self._update_node(node=node1,
                          prev=node2.prev,
                          next=node1.next)

        self._update_node(node=node2,
                          prev=tmp,
                          next=node2.next)

        # Connect the node before node1 to node 1
        if node1.prev is not None:
            logger.debug('Connect the prev to node 1')
            node_prev = self.get_node_from_node_id(node1.prev)
            self._update_node(node=node_prev,
                              prev=node_prev.prev,
                              next=node1.id)

        # Connect the node before node2 to node 2
        if node2.prev is not None:
            logger.debug('Connect the prev to node 2')
            node_prev = self.get_node_from_node_id(node2.prev)
            self._update_node(node=node_prev,
                              prev=node_prev.prev,
                              next=node2.id)

这个 _update_node function 只是把我的输入保存到数据库中，它可以处理 None 值。

get_node_from_node_id 接受一个整数作为输入，并返回与之关联的节点对象。我这样做是为了避免在数据库中使用自引用的外键（这个说法对吗？），目前我想继续这样工作。一旦这个部分正常工作了，我会再去修正数据库中的相关内容。

数据结构链表操作 C语言实现边界情况双向链表自引用外键节点交换链表算法

尝试为双向链表编写交换位置的函数

1 个回答

撰写回答