我的 DFS 树 (C++) 的意外结果

2022-01-05 00:00:00 depth-first-search algorithm tree c++

我已经解决了这个问题！！！我发现如果我必须使用 vector儿童；.但我不是很确定原因，有人能告诉我为什么吗?谢谢:)

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:)

问题:

我使用 test.cpp 生成一个树结构，如:

I use test.cpp to generate a tree structure like:

(ROOT->children).size() 的结果是 2，因为 root 有两个孩子.

The result of (ROOT->children).size() is 2, since root has two children.

((ROOT->children)[0].children).size() 的结果应该是 2，因为 的第一个孩子root 有两个孩子.但答案是0，为什么呢?这让我很困惑.

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(此代码可在 Visual Studio 2010 中运行)

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 向量包含 Node 值而不是 Node*指针.虽然您的访问正确使用了根，但它只会找到您尝试维护的子项的副本.你的所有节点也都泄露了.

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.

您可能希望为您的孩子使用 std::vector 并在某个时候删除他们.最简单的方法可能是使用智能指针向量，例如一个 tference 计数指针，并让智能指针负责释放.

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.

相关文章