從雙向鏈表中刪除一個節點

Question

我已經看過這個話題的其他線程，但沒有能夠使用它們來解決我的問題。

---

這是在鏈接列表中的節點的主類定義：

class node { 

public: 

    // default constructor 
    node() {name = ""; prev = NULL; next = NULL;}; 

    // default overloaded 
    node(string s) {name = s; prev = NULL; next = NULL;}; 

    // item in the list 
    string name; 

    // links to prev and next node in the list 
    node * next, * prev; 

}; 

---

以上是節點類的定義，這是在其產生鏈表另一類使用。鏈表代碼給了我們，我們必須修改，所以我知道它的工作原理。我已經完成並測試了雙向鏈表中新增節點的工作，現在我正在從這個雙向鏈表中刪除節點。

功能刪除一個節點：http://pastebin.com/HAbNRM5W

^這是我需要幫助的代碼中，有太多的重複鍵入

---

我被我的老師告訴記者，該代碼，問題是行56，它讀取：

tmp->prev = prev; 

我想設置鏈接到前一個節點是正確的。我嘗試使用類似的if/else循環的情況是當前節點是否是列表中的最後一項。如果它是最後一項（又名curr->next = NULL），則不要使用curr->next設置鏈接並停止循環迭代。

任何幫助/想法/建議/反饋將不勝感激！

void linkedList::remove(string s) 
{ 
     bool found = false; 
     node * curr = getTop(), * prev = NULL; 
     node * tmp = new node(); 
     while(curr != NULL) 
     { 
       // match found, delete 
       if(curr->name == s) 
       { 
         found = true; 
         // found at top 
         if(prev == NULL) 
         { 
          node * temp = getTop(); 
          setTop(curr->next); 
          getTop()->prev = NULL; 
          delete(temp); 
         } // end if 
         else 
         { 
          // determine if last item in the list 
          if (curr->next = NULL) 
          { 
           // prev node points to next node 
           prev->next = curr->next; 
           // delete the current node 
           delete(curr); 
          } // end if 
          // if not last item in list, proceed as normal 
          else 
          { 
           // prev node points to next node 
           prev->next = curr->next; 
           // set the next node to its own name 
           tmp = prev->next; 
           // set prev-link of next node to the previous node (aka node before deleted) 
           tmp->prev = prev; 
           // delete the current node 
           delete(curr); 
          } // end else 
         } // end else 
        } // end if 

       // not found, advance pointers 
       if(!found) 
       { 
        prev = curr; 
        curr = curr->next; 
       } // end if 

       // found, exit loop 
       else curr = NULL; 
     } // end while 

     if(found) 
      cout << "Deleted " << s << endl; 
     else 
      cout << s << " Not Found "<< endl; 
} // end remove 

Answer 1

對於你的代碼，我建議幾件事。隔離代碼以查找具有您正在查找的名稱的節點。刪除方法應該只刪除一個雙向鏈接的節點，只要它給出一個。

我知道你的remove方法需要一個字符串參數，但將它傳遞給另一個函數，並讓該函數返回你正在尋找的節點。

它應該是這個樣子：

Node *cur = find("abcd"); 
Node *prev = cur->prev; 
prev->next = cur->next; 

Node *n = cur->next; 
n->next = cur->prev; 

cur->next = NULL; //or nullptr 
cur->prev = NULL; //or nullptr 

delete cur; 

Answer 2

NULL應nullptr

if (curr->next = NULL) { ... 

這是一個任務所取代，你想：

if (curr->next == nullptr) { ... 

在線47我想你說：如果prev == nullptr和next是不nullptr，但你使用

prev->next = curr->next; 

哪一個不行，因爲prev是nullptr。

Answer 3

應該像這樣：

prev->next = curr->next; 
prev->next->prev = prev; 
delete (curr); 

Answer 4

我在所有不同的條件語句迷路了。所有你需要做的是：

void linkedList::remove(const std::string& s) 
{ 
    node* current = getTop(); // get head node 
    while (current != nullptr) // find the item you are trying to remove 
    { 
     if (current->name == s) 
     { 
      break; // when you find it, break out of the loop 
     } 
    } 

    if (current != nullptr) // if found, this will be non-null 
    { 
     if (current->prev) // if this is not the head node 
     { 
      current->prev->next = current->next; 
     } 
     else 
     { 
      // update head node 
     } 

     if (current->next) // if this is not the tail node 
     { 
      current->next->prev = current->prev; 
     } 
     else 
     { 
      // update tail node 
     } 

     // at this point, current is completely disconnected from the list 
     delete current; 
    } 
}