尝试给定节点

Question

之前删除我有以下两个功能，我可以得到时，试图实现removeBefore功能链表完全不改变removeAfter功能才能正常工作，但随后。我错过了什么吗？我做了必要的更改，但仍得到相同的结果：removeBefore不会输出对列表的任何更改。

// remove the node after the node p 
void DoublyLinkedList::removeAfter(DListNode &p){ 
    if (isEmpty()){ 
     throw EmptyDLinkedListException("Empty Doubly Linked List"); 
    } 

    DListNode *to_delete = &p; 
    to_delete = to_delete->next; 

    if (to_delete != NULL){ 
     if(to_delete->next != NULL){ 
      to_delete->prev->next = to_delete->next; 
     } 

     if(to_delete->prev != NULL){ 
      to_delete->next->prev = &p; 
     } 
     if (to_delete == &trailer) { 
      trailer = *to_delete->prev; 
     } 


    } 
    if (to_delete == NULL){ 
     throw EmptyDLinkedListException("Cannot delete a null pointer"); 
    } 
    delete to_delete; 
} 

// remove the node before the node p 
void DoublyLinkedList::removeBefore(DListNode &p){ 
     /* Complete this function */ 
    if (isEmpty()){ 
     throw EmptyDLinkedListException("Empty Doubly Linked List"); 
    } 

    DListNode *to_delete = &p; 
    to_delete = to_delete->prev; 

    if (to_delete != NULL){ 
     if (to_delete->next != NULL) { 
      to_delete->next->prev = to_delete->prev; 
     } 
     if (to_delete->prev != NULL) { 
      to_delete->prev->next = to_delete->next; 
     } 

     if (to_delete == &header) { 
      header = *to_delete->next; 
     } 

    } 

    if (to_delete == NULL){ 
     throw EmptyDLinkedListException("Cannot delete a null pointer"); 
    } 

    delete to_delete; 
} 

Answer 1

代码中存在错误。

首先，一个链表指针列表，所以它不是常规的通过参考节点绕过。你真的应该通过指针来传递它们。

removeAfter()没有考虑到p.next在输入时可能为NULL的可能性（当p是列表中的最后一个节点时）。而且这还不是那么删除to_delete本身之前正确更新to_delete的兄弟姐妹。它应该是这样的，而不是：

void DoublyLinkedList::removeAfter(DListNode *p) 
{ 
    DListNode *to_delete = p->next; //Get to the node after p that is to be deleted 
    if (to_delete != NULL) 
    { 
     if (to_delete->next != NULL) { 
      to_delete->next->prev = to_delete->prev; 
     } 

     if (to_delete->prev != NULL) { 
      to_delete->prev->next = to_delete->next; 
     } 


     // update the tail pointer if to_delete is the tail node... 
     if (trailer == to_delete) { 
      trailer = to_delete->prev; 
     } 

     delete to_delete; 
    } 
} 

removeBefore()是类似的错误。它不占可能性p.prev可能是在输入NULL（当p是列表中的第一个节点），甚至可以说，它可能是列表的头节点。它应该是这样的，而不是：

void DoublyLinkedList::removeBefore(DListNode *p) 
{ 
    DListNode *to_delete = p->prev; //Get to the node before p that is to be deleted 

    if (to_delete != NULL) 
    { 
     if (to_delete->next != NULL) { 
      to_delete->next->prev = to_delete->prev; 
     } 

     if (to_delete->prev != NULL) { 
      to_delete->prev->next = to_delete->next; 

     // update the head pointer if to_delete is the head node... 

     if (header == to_delete) { 
      header = to_delete->next; 
     } 

     delete to_delete; 
    } 
} 

话虽这么说，逻辑将更好地进行集中实现，例如：

void DoublyLinkedList::remove(DListNode *p) 
{ 
    if (p = NULL) return; 

    if (p->next != NULL) { 
     p->next->prev = p->prev; 
    } 

    if (p->prev != NULL) { 
     p->prev->next = p->next; 
    } 

    if (header == p) { 
     header = p->next; 
    } 


    if (trailer == p) { 
     trailer = p->prev; 
    } 

    delete p; 
} 

void DoublyLinkedList::removeAfter(DListNode *p) 
{ 
    remove(p->next); 
} 

void DoublyLinkedList::removeBefore(DListNode *p) 
{ 
    remove(p->prev); 
} 

话虽这么说，一旦你了解双链表工作，你应该扔掉所有这些代码，只是使用STL std::list类代替，这是一个标准的双链表实现。