刪除雙向鏈表中的節點（C++）

我在理解爲什麼當我創建兩個或多個節點時（如下所示），函數void del_end()將只刪除char name[20]而不是整個節點。我如何解決這個問題沒有內存泄漏？刪除雙向鏈表中的節點（C++）

#include <iostream> 
using namespace std; 

struct node 
{ 
    char name[20]; 
    char profession[20]; 
    int age; 
    node *nxt; 
    node *prv; 
}; 

node *start_ptr = NULL; 

void del_end() 
{ 
    node *temp, *temp2; 
    temp = start_ptr; 
    if (start_ptr == NULL) 
     cout << "Can't delete: there are no nodes" << endl; 
    else if (start_ptr != NULL && start_ptr->nxt == NULL) 
    {start_ptr=NULL;} 
    else 
    { 
    while (temp->nxt != NULL) 
    { 
     temp = temp->nxt; 
    } 
    temp2=temp->prv; 
    delete temp; 
    temp->nxt= NULL; 
    } 
}

來源

2010-07-06 danutenshu

這功課嗎？ – Karmastan 2010-07-06 18:46:28

我認爲這是作業嗎？如果是這種情況，請添加作業標籤。 – pmr 2010-07-06 18:47:24

您的代碼有問題，最嚴重的在這兒：

temp2=temp->prv; 
delete temp2; 
temp->nxt= NULL;

你刪除下一個到最後一個節點，留任何指向它晃來晃去，而且失去了最後一個節點。

但是，如果你發佈了更多的真實代碼，我們可以告訴你更多。

編輯：
這裏是del_end稍微清理後的版本（還是有很多改進的餘地）。

void del_end() 
{ 
    if (start_ptr == NULL) 
    { 
    cout << "Can't delete: there are no nodes" << endl; 
    return; 
    } 

    if (start_ptr->nxt == NULL) 
    { 
    delete start_ptr; 
    start_ptr = NULL; 
    return; 
    } 

    node *nextToLast = start_ptr; 
    node *last = start_ptr->nxt; 

    while(last->nxt != NULL) 
    { 
    nextToLast = last; 
    last = last->nxt; 
    } 

    delete last; 
    nextToLast->nxt = NULL; 

    return; 
}

注意這並沒有假設prev鏈接都是正確的，這看起來穩重這裏。

來源

2010-07-06 18:50:25 Beta

我的代碼真的很長，每行添加4個空格是很多手動工作。有沒有辦法只是把文件放在帖子上？ – danutenshu 2010-07-06 18:55:47

@danutenshu：如果有的話，這還不是一個好主意 - 帖子應該簡短。試着輸入足夠的代碼來重現問題（例如，放入一個'main'構造一個小列表，然後調用'del_end'）。與此同時，我將發佈'del_end'的修改版本。 – Beta 2010-07-06 19:08:16

所以我意識到我需要一個析構函數，但是'temp = NULL'會導致任何內存泄漏？ – danutenshu 2010-07-06 19:31:07

delete temp2;

會刪除整個節點。

來源

2010-07-06 18:45:53

節點被刪除，但是如果在堆中聲明瞭節點指向的任何內存，我認爲它不會被刪除。你能否提供解釋我的錯誤的原始資料？ OOPS！我不知何故傳遞了兩個char數組在堆棧中聲明的事實！ – 2010-07-06 18:49:49

如果你關心記憶，我強烈建議學習與Valgrind http://valgrind.org/一起工作。這是一個偉大的工具。 Valgrind的劃分內存泄漏分爲3類：

「肯定失去了」 - 指向動態分配的內存丟失，沒有辦法恢復了
「可能失去」 - 指向動態分配的內存指向到塊的內部，並且可以是不相關的
「仍可達」 - 指向動態分配的內存仍然存在，但是所述存儲器從未在程序的執行

運行Valgrind的的端部釋放也很簡單。這裏有一個鏈接到用戶手冊http://valgrind.org/docs/manual/manual.html。 Valgrind的運行時，一些有用的標誌：

--leak-check=<no|summary|yes|full>
--show-reachable=<no|yes>

現在，我會刪除一個節點的雙向鏈表的方法是：

// if the node to be removed is the head node 
if (nodeToRemove->prev == NULL) { 
    // reassign the head node pointer 
    start_ptr = nodeToRemove->next; 
} else { 
    // correct previous node pointer 
    nodeToRemove->prev->next = nodeToRemove->next; 
} 

// if the node to be removed node is the tail node 
if (nodeToRemove->next == NULL) { 
    // reassign the tail node pointer 
    end_ptr = nodeToRemove->prev; 
} else { 
    // correct next node pointer 
    nodeToRemove->next->prev = nodeToRemove->prev; 
} 

// deallocate memory 
delete(nodeToRemove); 
nodeToRemove = NULL;

只是聲明node *end_ptr = NULL;在聲明start_ptr並將一個節點追加到列表中時，請確保end_ptr始終指向列表的結尾......如果你添加到列表的末尾，它很容易......只需將end_ptr指向要添加的節點即可。

如果你總是需要刪除最後一個節點，你還可以保留一個尾指針。所以一旦你有要刪除的節點，我就檢查它的頭/尾節點，重新分配下一個/ prev指針，並釋放內存。

Btw ...我從我的C實現中取得了這個，所以如果語法關閉，我道歉......但是邏輯在那裏。

希望有所幫助。

來源

2010-07-06 19:00:01 Hristo

嘿，非常感謝，我一定會用這個。 – danutenshu 2010-07-06 19:12:23

沒問題。如果這是與學校有關的任務，我很驚訝他們不會讓你使用Valgrind。 – Hristo 2010-07-06 19:14:32

nope，自學，哈哈 – danutenshu 2010-07-06 19:57:23

問題是，您似乎試圖刪除最後一個節點，但實際上是在刪除它之前。

while (temp->nxt != NULL) 
{ 
    temp = temp->nxt; 
} 
temp2=temp->prv; 
delete temp2; 
temp->nxt= NULL;

這是你的問題。將其更改爲：

while (temp->nxt != NULL) 
{ 
    temp = temp->nxt; 
} 
temp2=temp->prv; 
delete temp; 
temp2->nxt= NULL;

而且我相信它會按預期工作。這節省了倒數第二個節點，刪除了結尾，然後將倒數第二個節點的nxt指針設置爲空，使其成爲最後一個節點。

來源

2010-07-06 19:09:16

刪除雙向鏈表中的節點（C++）

回答

相關問題