爲鏈表類型數據結構實現「刪除算法」

Question

這裏是我寫的刪除函數，用於在需要時從鏈表中刪除一些節點。

• 鏈表存儲爲按字母順序排序

使用下面的功能，當我嘗試刪除鏈表（稱爲頭）的第一個元素，我得到一個運行時錯誤，當我試圖打印鏈接列表（使用打印功能）和程序崩潰。我知道這可能是由於不創建新的頭節點造成的。但我不知道如何解決這個問題。這可能很簡單，但無法弄清楚。你能幫幫:)

這是刪除功能：

void deleteName(someStruct * &head, string name) 
{ 
    someStruct * ptr = head; 
    someStruct * previous; 

    if(head == NULL) 
    { 
     cout << "empty"; 
    } 
    else if(head->name == name) 
    { 
     ptr = head; 
     head = head->next; 
     delete head; 
    } 
    else 
    { 
     while (ptr -> name != name) 
     { 
      previous = ptr; 
      ptr = ptr->next; 
     } 
     previous->next = ptr->next; 
     delete ptr; 
    } 
} 

這是打印功能：

void Print(someStruct * head) 
{ 
    someStruct * pointer = head; 
    //List is empty 
    if(head == NULL) 
    { 
     cout << "List is empty" << endl; 
    } 
    else 
    { 
     while(pointer != NULL) 
     { 
      cout << pointer->name; 
      cout << pointer->points << endl; 
      pointer = pointer->next; 
     } 
    } 
} 

Answer 1

else if(head->name == name) 
{ 
    ptr = head; 
    head = head->next; 
    delete head; 
} 

此：

1. 保存舊值爲head至ptr，這是正確的
2. 推進INOUT PARAM head，這也是正確的

3. 完全忽略ptr，其中包含要刪除舊的節點，而不是刪除當前的表頭，離開INOUT PARAM head指向刪除節點。

   這一點是不正確的。

只是將delete head更改爲delete ptr。

---

注意事項以供將來參考：構建這個好方法是使用它不需要被刪除本地前哨淋巴結。這將刪除您的特殊情況head（通過添加您的臨時頭永遠不會被刪除的不變量）並簡化代碼。

void deleteName(someStruct * &head, string name) 
{ 
    if(!head) { 
     cout << "empty"; 
     return; 
    } 

    someStruct tmphead; 
    tmphead.next = head; 

    for (someStruct *prev = &tmphead; prev->next; prev = prev->next) { 
     if (prev->next->name == name) { 
      auto todelete = prev->next; 
      prev->next = todelete->next; 
      delete todelete; 
      // if there can be only one match, just bail out 
      break; 
      // otherwise, if there can be many, go round again 
      // but remember to check whether prev->next is null 
      // if (!prev->next) break; 
     } 
    } 

    head = tmphead.next; 
} 

如果您someStruct是太大或太複雜使用臨時頭這樣，你可以做同樣的一個臨時本地頭指針，使prev指針到指針。

Answer 2

delete head in else if block是問題所在。

更改塊這樣的：

else if(head->name == name) { 
    //ptr = head; You don't have to. You already have initialized ptr with head 
    head = head->next; 
    delete ptr; //Delete prt not head, head is now the next node which you assigned in previous line 
} 

Answer 3

else if(head->name == name){ 
    ptr = head; 
    head = head -> next; 
    delete ptr; // change to this statement n you're good to go 
}