在C++中刪除鏈接列表中的節點

Question

我想在列表的第n個位置刪除單個鏈接列表中的節點，但在運行項目時我一直收到一個分段錯誤：11。下面是我的功能remove我認爲問題是，但我似乎無法弄清楚爲什麼它不工作，因爲邏輯是有道理的。另外，其中headM點在列表中的第一個項目中是第0個位置。 我打這個電話之前刪除我的名單順序770 440 330 220 110 我兩次調用刪除

remove(0) 
remove(2) 

名單應該是440 330 110後，但現在我得到770 330 110 ....

void SimpleList::remove(int n) 
{ 
if(n < 0 || n > sizeM) { 
    return; 
} 
Node* p = headM; 
for(int c = 0; c < n - 1; c++) 
{ 
    p = p->next; 
    //assert(p != nullptr); 
} 
Node* const p_doomed = p->next; 
//assert(p_doomed != nullptr); 
p->next = p_doomed->next; 
delete p_doomed; 
--sizeM; 
} 

下面是節點的結構。這部分是正確的，因爲我的push_front和push_back工作。

class Node { 
public: 
    ListItem item; 
    Node *next; 
}; 

Node *headM; 
int sizeM; 

void destroy(); 
// Deallocate all nodes, and sets headM to zero. 

void copy(const SimpleList& source); 
// List becomes copy of source. 

Answer 1

你不檢查一個節點是否等於nullptr和sizeM沒有的情況下，降低節點被刪除

該函數可以寫成下面的方式

size_t sizeM; 

//... 

void SimpleList::remove(size_t n) 
{ 
    Node *current = headM; 
    Node *prev = nullptr; 

    while (current && n--) 
    { 
     prev = current; 
     current = current->next; 
    } 

    if (current) 
    { 
     if (prev) prev->next = current->next; 
     else headM = headM->next; 

     delete current; 
     --sizeM; 
    } 
} 

我猜想該列表的索引從零開始。

考慮到應將sizeM定義爲size_t而不是int。聲明它爲int沒有意義，在這種情況下，您應該始終檢查sizeM是否小於零。你也可以定義一個更通用的類型sizeM。例如

typedef size_t size_type; 

如果headM和sizeM是全局變量那麼這將是更好的封裝headM和sizeM在例如一個單獨的類名爲List。

此外，你可以檢查函數是否大於或等於sizeM。如果確實大於或等於sizeM那麼您可以簡單地退出該函數或拋出exceprion。

例如

void SimpleList::remove(size_t n) 
{ 
    if (!(b < sizeM)) return; 

或

void SimpleList::remove(size_t n) 
{ 
    if (!(b < sizeM)) throw std::out_of_range("Incorrect value of the index"); 

Answer 2

考慮的最後一個節點，例如，如果該列表具有（i）節點：{0 .. I - 1}，則在節點位置（i - 1）。你應該能夠滿足自己，在循環後：

for(int c = 0; c < n; c++) p = p->next; // where: n = i - 1 

p->next是NULL（或nullptr），因此：

p->next = p->next->next;取消引用一個空指針。

Answer 3

您刪除的方式有點不對。您必須將先前指針的next節點獲取到後續節點p，然後將其刪除。

無論如何，你也可以寫這樣的：

void SimpleList::remove(int value) 
{ 
    Node** ptr = &headM, *next; 

    while (*ptr && (*ptr)->data != value) 
     ptr = &(*ptr)->next; 

    if (*ptr) 
    {  
     next = (*ptr)->next; 
     delete *ptr; 
     *ptr = next; 
    } 
} 

而像弗拉德說，你應該遞減尺寸爲好。

Answer 4

^{這個答案現在被OP的問題中的新信息所無效。事實證明，他沒有虛擬頭節點（正如命名和邏輯所暗示的那樣），並且第n箇中的n不是基於1的，而是基於0的索引。我現在離開了答案，寧願不追逐一個不斷變化的問題。}

該原始代碼

void SimpleList::remove(int n) 
{ 
    Node *p = headM; 
    for(int c=0;c<n;c++) 
    { 
     p = p->next; 
    } 
    Node *todel = p->next; 
    p->next = p->next->next; 
    delete todel; 
} 

意味着headM指向一個虛設頭節點。

考慮到n = 1時發生的情況，todel錯誤地設置爲p->next，即您想要刪除的節點之後的節點。對於這個問題，你不能用p直接指向你想要刪除的節點，除非你保證至少有一個後續節點，並且沒有其他指針進入列表。此外，即使列表包含n節點（正好），p->next->next表達式也可以具有UB。

而是這樣做：

void SimpleList::remove(int const n) 
{ 
    if(n <= 0 || n > sizeM) { throw std::runtime_error("Ouch!"); } 
    Node* p = headM; 
    for(int c = 1; c <= n - 1; ++c) 
    { 
     p = p->next; 
     assert(p != nullptr); 
    } 
    Node* const p_doomed = p->next; 
    assert(p_doomed != nullptr); 
    p->next = p_doomed->next; 
    delete p_doomed; 
    --sizeM; 
}