删除双向链表中的节点（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++）

回答

相关问题