Неожиданный результат моего дерева DFS (C ++) - PullRequest
Новая
       41

Неожиданный результат моего дерева DFS (C ++)

1 голос
/ 20 марта 2012

Я решил эту проблему !!! Я обнаружил, что если я должен использовать vector<Node*> children;. Но я не совсем уверен, причина, кто-то может сказать мне, почему? Спасибо:)

Вопрос:

Я использую test.cpp для создания древовидной структуры, такой как:

enter image description here

Результат (ROOT->children).size() равен 2, поскольку root имеет двоих детей.

Результат ((ROOT->children)[0].children).size() должен быть 2, так как у первого ребенка root есть два ребенка. Но ответ 0, почему? Это действительно смущает меня.

test.cpp (Этот код можно запустить в 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;

}

1 Ответ

3 голосов
/ 20 марта 2012

Проблема в том, что ваш children вектор содержит Node значения, а не Node* указатели. В то время как ваш доступ правильно использует root, он находит только копии дочерних элементов, которые вы пытаетесь сохранить. Все ваши узлы также протекают.

Возможно, вы захотите использовать std::vector<Node*> для своих детей и delete их в какой-то момент. Самый простой способ - использовать вектор умных указателей, например, указатель с подсчетом голосов и умный указатель позаботится о выпуске.

...