作为我所在大学委托我进行的一项练习的一部分，我按照这个标题编写了一个小型Graph实现。
class Node {
private:
std::string name;
std::vector<Node*> children;
public:
Node(const std::string& name="");
virtual ~Node();
}
在为析构函数~Node()编写代码时，我注意到当图包含循环时，我的实现会失败。到目前为止，这是我的实现，如果图中包含一个循环，那么它显然不起作用。
Node::~Node() {
for (Node* n : children) {
delete n;
n = NULL;
}
children.clear();
}
我不确定如何最优雅地编写一个可以处理图中循环的析构函数？
请注意，我的任务是专门编写递归析构函数。谢谢你的回答！
选项1：为节点不属于其他节点的图选择一种表示形式，而是为将成为不同对象的图选择表示形式。这样，节点析构函数就不需要做任何事情这不能满足递归的要求：
struct Graph {
std::vector<std::unique_ptr<Node>> nodes;
};
请注意，如果不涉及继承，那么您可以简单地使用std::vector<Node>。由于Node中使用了虚拟去采购器，我认为存在。
或者，您可以使用图形的另一种表示形式，如邻接列表。
选项2：使用算法生成图的最小生成林。然后递归地删除每个生成树的根。例如，您可以使用Kruskal的算法。(考虑到你的表示，看起来你的图可能是连通的，在这种情况下，只有一棵展开树(。
一个选项可以是首先创建所有Node*的unordered_set，然后创建它们的delete。
void fill(std::unordered_set<Node*>& to_delete, Node* ptr) {
// try to insert ptr and return if it was already in the set
if(not to_delete.emplace(ptr).second) return;
// swap ptr->children with an empty vector
std::vector<Node*> tmp;
std::swap(tmp, ptr->children);
for(Node* c : tmp) // loop over the pointers
fill(to_delete, c); // fill recursively
}
virtual ~Node() noexcept { // std::terminate if anything should throw
if(children.empty()) return; // nothing to do here
std::unordered_set<Node*> to_delete; // to collect all the Node*'s
fill(to_delete, this); // fill the set recursively
to_delete.erase(this); // don't delete "this"
for(auto c : to_delete) // delete all - they have no children by now
delete c;
}
演示
如果你的图是一棵树(我假设它是树，因为你的析构函数实现只对树有效(，并且你可以存储Node的父级，那么你可以编写迭代版本，它不需要任何额外的数据结构来避免递归。
还要学会使用智能指针。
class Node {
private:
std::string name;
std::vector<std::unique_ptr<Node>> children;
Node* parent;
void safeCleanClildren();
public:
Node(std::string name="", Node* parent = nullptr)
: name{std::move(name)}
{}
~Node() {
iterativeCleanClildren();
}
void addChild(std::string name) {
children.emplace_back(std::make_unique<Node>(std::move(node), this);
}
};
void Node::iterativeCleanClildren()
{
auto p = this;
while (!p->children.empty()) {
while (!p->children.empty()) {
p = p->back().get(); // go as deep as possible
}
if (p != this) {
p = p->parent; // go back to parent
p->children.pop_back();
}
}
}
这是怎么回事？
- 首先，它在树(没有子节点的节点(中找到叶子(最右边(
- 然后返回父节点并移除刚刚找到的
p->children.pop_back();的子节点(这会破坏刚刚找到的叶的unique_ptr( - 然后再找到叶子等等
- 此树清除将继续进行，直到到达根(
this(节点
这样根节点结束时根本没有子节点，而且由于它是迭代实现，因此不可能溢出。这棵树有多不平衡并不重要。