我已经解决了这个问题!!!我发现如果我必须使用 vector<Node*> children;
.但是我不太确定原因,有人可以告诉我为什么吗?谢谢:)
问题:
我使用 test.cpp
生成如下树结构:
(ROOT->children).size()
的结果是2
, 自 root
有两个 child 。
((ROOT->children)[0].children).size()
的结果应该是 2
, 自 root
的第一个 child 有两个 child 。但答案是0
, 为什么?这让我很困惑。
test.cpp (This code is runnable in visual studio 2010)
#include <iostream>
#include <vector>
using namespace std;
struct Node {
int len;
vector<Node> children;
Node *prev;
Node(): len(0), children(0), prev(0) {};
};
class gSpan {
public:
Node *ROOT;
Node *PREV;
void read();
void insert(int);
};
int main() {
gSpan g;
g.read();
system("pause");
}
void gSpan::read() {
int value[4] = {1, 2, 2, 1};
ROOT = new Node();
PREV = ROOT;
for(int i=0; i<4; i++) {
insert(value[i]);
}
cout << "size1: " << (ROOT->children).size() << endl; // it should output 2
cout << "size2: " << ((ROOT->children)[0].children).size() << endl; // it should output 2
system("pause");
}
void gSpan::insert(int v) {
while(v <= PREV->len)
PREV = PREV->prev;
Node *cur = new Node();
cur->len = v;
cur->prev = PREV;
PREV->children.push_back(*cur);
PREV = cur;
}
最佳答案
问题是你children
vector 包含Node
值而不是 Node*
指针。虽然您的访问正确使用了根,但它只会找到您尝试维护的子项的拷贝。您的所有节点也都已泄露。
您可能想使用 std::vector<Node*>
为了您的 child 和delete
他们在某个时候。最简单的方法可能是使用智能指针 vector ,例如一个引用计数指针,并让智能指针负责释放。
关于c++ - 我的 DFS 树 (C++) 的意外结果,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9780955/