從鏈接列表中刪除節點

Question

我正在從迭代刪除功能，從鏈表中刪除節點，我認爲代碼應該工作正常，它遍歷列表，找到所需的節點，指向頭到下一個節點，並刪除當前，但是當我試運行它，我得到無限循環，可以請你幫我查明錯誤，這裏是功能：

typedef struct E_Type * List; 
struct E_Type 
{ 
    int data; 
    struct E_Type* next; 
}; 

功能：

bool erase(List & l, int data){ 
List head = l; 
if (l != 0){ 
    for(List current = head; current; current = current->next){ 
    if (current->data == data) 
     head = current->next; 
     delete current; 
     return true; 
    } 
    } 
return false; 
} 

測試程序：

int main() 
{ 
    List l = 0; 
    cout << boolalpha << l->data << "went well? "<< (insert(l,73)) << endl; 
    cout << boolalpha << l->data << "went well? "<< (insert(l,24)) << endl; 
    print(cout,l); 
    cout << boolalpha << "Is deleted 24? "<<(erase(l,24)) << endl;  
    cout << boolalpha << "Is deleted 35? "<<(erase(l,35)) << endl; 
    print(cout,l); 
    cout << endl; 
    return 0; 
} 

插入：

bool insert(List & l, int data) 
{ 

    List current = l; 
    while(current != 0) { 
     if (current->data == data) 
     return false; 
     current = current->next; 
    } 

    if (l == 0 || l->data > data){ 
     List new_list = new E_Type; 
     new_list->data = data; 
     new_list->next = l; 
     l = new_list; 
    return true; 
    } 

    else if(l->data < data){ 
    insert(l->next, data); 
    return true; 
    } 

} 

Answer 1

正如Andreas Brinck已經指出的那樣，您還需要更新'上一個'鏈接。不過，你不需要爲這個專門的變量，只要用一個指針的指針：

bool erase(List & l, int data){ 
    List *it = &l; 
    while (*it) { 
    if ((*it)->data == data) { 
     List next = (*it)->next; 
     delete *it; 
     *it = next; 
     return true; 
    } 
    it = &(*it)->next; 
    } 
    return false; 
} 

這也需要謹慎的處理所有的「特殊情況」，比如從空的列表中刪除，刪除列表中的第一個元素或刪除列表中的最後一個元素。

Answer 2

我們可能需要看到您的插入方法爲好。

難道

current == current->next 

如果是的話，可能會導致無限循環。

Answer 3

您需要在跟蹤前一個節點，以及用於循環，這樣做：

prev->next = current->next; 
delete current; 

您還需要處理的就是刪除元素是第一要素的情況下列表，在這種情況下，你需要設置l到l->next

bool erase(List & l, int data){ 
if (l != 0){ 
    for(List current = head, prev = 0; current; prev = current, current = current->next){ 
    if (current->data == data) 
    { 
     if (prev) 
     { 
      prev->next = current->next; 
     } 
     else 
     { 
      l = current->next; 
     } 
     delete current; 
     return true; 

    } 
    } 
return false; 
} 

你的第一擦除可能創建一個循環鏈表現在。