我的双向链表交换函数有什么问题吗？ [英] Is anything wrong with my doubly linked list swap function?

问题描述

我有一个函数用于交换2个节点：

I have a function which is used to swap 2 nodes:

void swap(Node<T>* a, Node<T>* b) {
    if(a->m_prev)
        a->m_prev->m_next = b;
    if(b->m_prev)
        b->m_prev->m_next = a;
    if(a->m_next)
        a->m_next->m_prev = b;
    if(b->m_next)
        b->m_next->m_prev = a;

    Node<T>* temp;
    temp = a->m_prev;
    a->m_prev = b->m_prev;    
    b->m_prev = temp;
    temp = a->m_next;
    a->m_next = b->m_next;    
    b->m_next = temp;
}

但是当使用我的递归选择排序：

However when used with my recursive selection sort:

void selectionSort(Node<T>* head) {
    if(next(head) == NULL) {
        return;
    }
    Node<T>* minimum = min(head);

    swap(head,minimum);

    selectionSort(minimum->m_next);
}

大约一半的排序，它设置我的节点的下一个指针到NULL，那么当我打印我的列表，它被正确排序到该值，但其余的缺失，因为指针不正确地设置为NULL。

About half way through the sort, it sets one of my nodes' next pointer to NULL, then when I print my list, it is sorted up to that value correctly, but the rest is missing because a pointer was incorrectly set to NULL.

和：

我的初始列表正确，没有不正确连接的节点。

My initial list is correct and has no incorrectly connected nodes.

我的交换函数与非空的有效节点。

My swap function is only called with non-null valid nodes.

所以我责怪交换功能。

So I blame the swap function. Is there anything wrong with it?

推荐答案

我想问题出现在 a 与列表中的 b 相邻。例如，如果 b-> prev 指向 a （表示 a 正好在列表中的 b 之前）

I think the problem occurs when a is adjacent to b in the list. For example, if b->prev points to a (meaning a is just before b in the list) then the line

b->prev->next = a; 

相当于

a->next = a;

这显然不是你想要的。

以下是一些如何处理双向链表中交换节点问题的提示。要交换的节点A和B将被称为内部节点。列表中的其他节点是外部节点。在A和/或B附近的外部节点将被指定为W，X，Y和Z.远离A和B的外部节点将用省略号指定。当交换内部节点时，在交换中将涉及2,3或4个外部节点，如下所示

Here are some tips on how to approach the problem of swapping nodes in a doubly linked list. The nodes to be swapped, A and B, will be referred to as internal nodes. Other nodes in the list are external nodes. The external nodes that are near A and/or B shall be designated W, X, Y, and Z. External nodes far from A and B shall be designated with ellipsis. When swapping the internal nodes, there will be 2, 3, or 4 external nodes involved in the swap, as shown below

case 1: widely separated (four external nodes)      ... W A X ... Y B Z ...
case 2: separated by one (three external nodes)     ... W A X B Z ...
case 3: adjacent (two external nodes, A first)      ... W A B Z ...
case 4: adjacent (two external nodes, B first)      ... W B A Z ...

应该可以用一组代码处理前两种情况（事实上，X连接到A和B，情况2应该有对交换实现没有影响）。最后两种情况可以通过交换函数参数来处理，如果B在A之前，那么变量 a 总是指向第一个节点，变量 b 始终指向第二个节点。因此，将四种情况简化为两种情况，模型为

It should be possible to handle the first two cases with a single set of code (the fact that X is connected to both A and B in case 2 should have no effect on the swap implementation). The last two cases can be handled by swapping the function arguments if B is ahead of A, so that variable a always points to the first node and variable b always points to the second node. Thus, the four cases are reduced to two cases, modeled as

cases 1&2:   ... W A X ... Y B Z ...
cases 3&4:   ... W A B Z ...

1& 2，需要更新的内部节点上有4个指针，外部节点上有4个指针需要更新。在情况3和4中，在需要更新的内部节点上有4个指针，但是在外部节点上只有2个指针需要更新。

In cases 1&2 there are 4 pointers on the internal nodes that need to be updated, and 4 pointers on the external nodes that need to be updated. In cases 3&4, there are 4 pointers on the internal nodes that need to be updated, but only 2 pointers on the external nodes that need to be updated.

I建议坐下来用铅笔和纸，并首先识别需要更新的指针，然后确定你想要的每个指针的最终值。知道，编码部分应该很容易。

I suggest sitting down with a pencil and paper and first identifying the pointers that need to be updated, and then determine what you want the final value of each pointer to be. Knowing that, the coding part should be easy.

这篇关于我的双向链表交换函数有什么问题吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！