我的双向链表交换功能有什么问题吗？

我有一个用于交换2个节点的功能：我的双向链表交换功能有什么问题吗？

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; 
}

但是我的递归选择排序时：

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

    swap(head,minimum); 

    selectionSort(minimum->m_next); 
}

关于通过某种半路上，它集我的一个节点'下一个指向NULL的指针，然后当我打印我的列表时，它将正确地排序为该值，但其余部分因为指针被错误地设置为NULL而丢失。

我检查和：

我最初的名单是正确的，并没有正确连接的节点。

我的交换功能只能用非空的有效节点调用。

所以我怪责交换功能。它有什么问题吗？

来源

2014-03-13 jmasterx

我认为，当a毗邻列表b出现问题。例如，如果b->prev点a（意为a只是在列表b前），然后行至

a->next = a;

b->prev->next = a;

相当于这显然不是你想要的。

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

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在情况2中连接到A和B应该对交换实现没有影响）。如果B先于A，则可以通过交换函数参数来处理最后两种情况，以便变量a始终指向第一个节点，并且变量b始终指向第二个节点。因此，四个病例减少为两个的情况下，建模为

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

在案件1 & 2有4个指针需要被更新的内部节点上，并且4个指针需要是外部节点上更新。在3 & 4的情况下，需要更新的内部节点上有4个指针，但需要更新的外部节点上只有2个指针。

我建议坐下来用铅笔和纸，先确定需要进行更新，然后确定您希望每个指针的终值是什么指针。知道这一点，编码部分应该很容易。

来源

2014-03-13 03:13:34 user3386109

10我能做些什么来解决这个问题？我不知道如何。 – jmasterx

@Milo我在回答中增加了一些附注。 – user3386109

你可以交换节点的值，以避免指针灾难

来源

2014-03-13 03:34:35 michaeltang

重要的是，我不会使节点包含的内容或节点本身无效。 – jmasterx

这应该工作。

void swap(Node<T>* a, Node<T>* b) { 

    if (a == b) 
    { 
     return; 
    } 

    Node<T*> oldANext = a->m_next; 
    Node<T*> oldAPrev = a->m_prev; 
    Node<T*> oldBNext = b->m_next; 
    Node<T*> oldBPrev = b->m_prev; 

    // Special case when b is the next of a. 
    if (a->m_next == b) 
    { 
     a->m_next = oldBNext; 
     a->m_prev = b; 
     b->m_next = a; 
     b->m_prev = oldAPrev; 

     if (oldAPrev) 
      oldAPrev->m_next = b; 
     if (oldBNext) 
      oldBNext->m_prev = a; 
    } 
    // Special case when b is the prev of a. 
    else if (a->m_prev == b) 
    { 
     a->m_prev = oldBPrev; 
     a->m_next = b; 
     b->m_prev = a; 
     b->m_next = oldANext; 

     if (oldANext) 
      oldANext->m_prev = b; 
     if (oldBPrev) 
      oldBPrev->m_next = a; 
    } 
    // When a and b are not related. 
    else 
    { 
     a->m_next = oldBNext; 
     a->m_prev = oldBPrev; 
     b->m_next = oldANext; 
     b->m_prev = oldAPrev; 

     if (oldANext) 
      oldANext->m_prev = b; 
     if (oldAPrev) 
      oldAPrev->m_next = b; 
     if (oldBNext) 
      oldBNext->m_prev = a; 
     if (oldBPrev) 
      oldBPrev->m_next = a; 
    } 
}

来源

2014-03-13 04:50:43

我的双向链表交换功能有什么问题吗？

回答

相关问题