我的DFS树(C ++)的意外结果 [英] Unexpected result of my DFS tree (C++)
问题描述
我已经解决了这个问题!我发现,如果我必须使用矢量<节点*>儿童;
。但我不是很肯定的原因,有人可以告诉我为什么?感谢:)
问:
我用 TEST.CPP
来生成一个树状结构,如:
的结果(根 - >儿童).size()
是 2
,因为根
有两个孩子。
的结果((根 - >儿童)[0]。儿童).size()
应 2
,因为根
的第一个孩子有两个孩子。但得到的答复是 0
,为什么呢?这真的迷惑了我。
TEST.CPP(这code是可运行在Visual Studio 2010)
的#include<的iostream>
#包括<载体>
使用名字空间std;
结构节点{
INT LEN;
矢量<节点>儿童;
节点* preV;
节点():LEN(0),儿童(0),preV(0){};
};
一流的gSpan {
上市:
节点*根;
节点* $ P $的pV;
无效的read();
无效插入件(INT);
};
诠释的main(){
gSpan克;
g.read();
系统(暂停);
}
无效gSpan ::阅读(){
int值[4] = {1,2,2,1};
ROOT =新节点();
preV = ROOT;
的for(int i = 0;我4;;我++){
插入(值[I]);
}
COUT<< 尺寸1:&其中;&其中; (根 - >儿童).size()<< ENDL; //它应该输出2
COUT<< size2个:&其中;&其中; ((根 - >儿童)[0]。儿童).size()<< ENDL; //它应该输出2
系统(暂停);
}
无效gSpan ::插入(INT V){
而(V< = preV-> LEN)
preV = preV-> preV;
节点* CUR =新节点();
当前>的len = V;
当前> preV = $ P $的pV;
preV-> children.push_back(* CUR);
preV = CUR;
}
现在的问题是,你孩子
载体包含节点
值,而不是节点*
指针。当你进入正确使用根,找到你尽量保持孩子的唯一副本。您的所有节点也都泄露。
您可能需要使用的std ::矢量<节点*>
为您的孩子和删除
他们在某一点。最简单的方法可能是使用智能指针的载体,如:一个teference计的指针,并具备智能指针照顾释放。
I have solved this problem!!! I found that if i have to use vector<Node*> children;
. But I am not very sure the reason, can someone tell me why? Thanks:)
Question:
I use test.cpp
to generate a tree structure like:
The result of (ROOT->children).size()
is 2
, since root
has two children.
The result of ((ROOT->children)[0].children).size()
should be 2
, since the first child of root
has two children. But the answer is 0
, why? It really confuse for me.
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;
}
The problem is that you children
vector contains Node
values rather than Node*
pointers. While your access uses the root correctly, it finds only copies of the children you try to maintain. All of your nodes are also leaked.
You might want to use a std::vector<Node*>
for your children and delete
them at some point. The easiest way is probably to use a vector of smart pointers, e.g. a teference counted pointer, and have the smart pointer take care of the release.
这篇关于我的DFS树(C ++)的意外结果的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!