c++ - 删除时出现分段错误
问题描述
我对 C++ 很陌生,我正在尝试实现一个树结构,但是我遇到了一个分段错误,该错误在删除树时出现。这段代码非常简单,我有一个 Node 类,其中包含指向其子级的指针。
#include <vector>
class Node
{
public:
int data1, data2;
std::vector<Node*> children;
Node* add_child(double data1, double data2)
{
Node* n = new Node(data1, data2);
children.push_back(n);
return n;
}
Node(double data1, double data2)
:data1(data1), data2(data2)
{ }
~Node()
{
for(auto child : children)
{
delete child;
}
children.clear();
}
};
int main()
{
Node root = Node(0, 0);
Node* n = &root;
for(int i = 0; i < NB; ++i)
{
n = n->add_child(0, 0);
}
}
主要创建一个非常简单的结构,但有错误就足够了。段故障仅发生在 NB 的值大于 170 000 时。
解决方案
基于非递归程序删除整个二叉树的 例子,我们可以修改你的应用程序如下:
#include <iostream>
using namespace std;
#include <vector>
#include <queue>
class Node
{
public:
Node* add_child(double data1, double data2)
{
Node* n = new Node(data1, data2, false);
children.push_back(n);
return n;
}
Node(double data1, double data2, bool is_root = true )
:data1(data1), data2(data2), is_root(is_root)
{
}
~Node()
{
if( is_root ) deleteTree();
}
size_t get_num_childs()
{
return children.size();
}
Node* get_child( size_t index )
{
return children[index];
}
private:
/* Non-recursive function to delete an entire tree. */
void deleteTree()
{
// Create an empty queue for level order traversal
queue<Node *> deleteQueue;
// Do level order traversal starting from root
for( int index = 0; index < children.size(); index++ )
{
deleteQueue.push( children[index]);
}
while( !deleteQueue.empty())
{
Node *node = deleteQueue.front();
deleteQueue.pop();
for( int index = 0; index < node->get_num_childs(); index++ )
{
// Add all childs to queue for deleting
deleteQueue.push( node->get_child( index ));
}
delete node;
}
}
private:
int data1, data2;
std::vector<Node*> children;
bool is_root;
};
int main()
{
Node root = Node(0, 0);
Node* n = &root;
for(int i = 0; i < 17000; ++i)
{
n = n->add_child(0, 0);
}
return 0;
}
正如评论中提到的,递归调用节点析构函数会导致堆栈溢出,然后是分段错误。
所以为了解决这个问题,我们必须坚持非递归删除节点。这是在方法的支持下完成的deleteTree()
。为此,我们在内部构建了一个包含所有需要删除的节点的队列。
推荐阅读
- c# - 在 C# 中将类序列化为 xml 时处理 null
- node.js - 如何在 JWT 中实现权限
- android - 如何逐行查看类测试覆盖率?
- java - Adempiere webui 380 条码扫描焦点从扫描字段中移除且扫描产品线不集中
- wpf - ListBox 未在按钮单击时更新
- wordpress - 在 WordPress 管理区域中为 user_url 设置默认值
- google-drive-api - 查看 gSuite 驱动器用户文件
- angular - 输入'HttpEvent
不可分配给类型“名称 []” - c# - ASP.net MVC 5 - 如何从 Global.asax.cs 中的 session_end() 事件重定向到操作方法
- reactjs - 为什么函数依赖项的处理方式与其他依赖项不同?