如何为 Trie 树编写析构函数
How to write destructor for Trie tree
我一直在做一项作业,它让我们使用特里树将字典中的单词添加到树中,然后在其中进行搜索。我坚持的部分是 class 析构函数。这是我第一次不得不处理 destructor/memory 管理,下面是我搜索目前拥有的资源后的最佳猜测。
我走在正确的轨道上吗?每个节点有 27 个子节点(字母表和一个分隔符),所以我希望它将它们从叶节点到根节点全部删除。
class Trie
{
private:
TrieNode *_root = nullptr;
TrieNode *_current = nullptr;
TrieNode *_child = nullptr;
string current_word;
bool setRoot = false;
protected:
public:
Trie()
{
_root = new TrieNode{};
}
virtual ~Trie()
{
//TODO: clean up memory
DestroyRecursive(_root);
}
void Trie::DestroyRecursive(TrieNode* node)
{
if (node != nullptr)
{
for (TrieNode* child : node->getChildren())
{
delete(child);
}
}
}
如何检查析构函数是否正常工作?我正在使用 Visual Studio.
你的DestroyRecursive
实际上不是递归的
您需要在叶节点上调用 delete
并在有子节点的节点上递归。
void Trie::DestroyRecursive(TrieNode* node)
{
if (node != nullptr)
{
if (node->getChildren().size() == 0)
{
// delete the leaf node
delete(node);
return;
}
for (TrieNode* child : node->getChildren())
{
DestroyRecursive(child);
}
}
}
这 可能 出错,这取决于对 TrieNode
结构的依赖性。例如,它是否具有 non-trivial 析构函数?
可以通过将原始指针替换为 std::shared_ptr
来避免很多这种情况
std::shared_ptr<TrieNode> _root = nullptr;
vector<shared_ptr<TrieNode>> _child = nullptr;
Trie()
{
_root = std::make_shared<TrieNode>();
}
然后在大多数情况下你不需要析构函数。 std::vector
和 shared_ptr
将负责在超出范围时在适当的内存上调用 delete
。
请注意,所有权没有循环依赖性。如果以后添加父指针,它必须是原始指针或 std::weak_ptr
How can I check if a destructor is working properly? I'm using Visual
Studio.
你可以放一个breakpoint来检查代码是否被命中。
我一直在做一项作业,它让我们使用特里树将字典中的单词添加到树中,然后在其中进行搜索。我坚持的部分是 class 析构函数。这是我第一次不得不处理 destructor/memory 管理,下面是我搜索目前拥有的资源后的最佳猜测。
我走在正确的轨道上吗?每个节点有 27 个子节点(字母表和一个分隔符),所以我希望它将它们从叶节点到根节点全部删除。
class Trie
{
private:
TrieNode *_root = nullptr;
TrieNode *_current = nullptr;
TrieNode *_child = nullptr;
string current_word;
bool setRoot = false;
protected:
public:
Trie()
{
_root = new TrieNode{};
}
virtual ~Trie()
{
//TODO: clean up memory
DestroyRecursive(_root);
}
void Trie::DestroyRecursive(TrieNode* node)
{
if (node != nullptr)
{
for (TrieNode* child : node->getChildren())
{
delete(child);
}
}
}
如何检查析构函数是否正常工作?我正在使用 Visual Studio.
你的DestroyRecursive
实际上不是递归的
您需要在叶节点上调用 delete
并在有子节点的节点上递归。
void Trie::DestroyRecursive(TrieNode* node)
{
if (node != nullptr)
{
if (node->getChildren().size() == 0)
{
// delete the leaf node
delete(node);
return;
}
for (TrieNode* child : node->getChildren())
{
DestroyRecursive(child);
}
}
}
这 可能 出错,这取决于对 TrieNode
结构的依赖性。例如,它是否具有 non-trivial 析构函数?
可以通过将原始指针替换为 std::shared_ptr
来避免很多这种情况std::shared_ptr<TrieNode> _root = nullptr;
vector<shared_ptr<TrieNode>> _child = nullptr;
Trie()
{
_root = std::make_shared<TrieNode>();
}
然后在大多数情况下你不需要析构函数。 std::vector
和 shared_ptr
将负责在超出范围时在适当的内存上调用 delete
。
请注意,所有权没有循环依赖性。如果以后添加父指针,它必须是原始指针或 std::weak_ptr
How can I check if a destructor is working properly? I'm using Visual Studio.
你可以放一个breakpoint来检查代码是否被命中。