嘗試給定節點

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類代替，這是一個標準的雙鏈表實現。