c++ - 有多个 child 的树使用 vector

Question

我正在尝试制作一棵有多个 child 的树，这棵树应该如下所示:

      n 
/     |     \
n2    n3     n4
|
n5  

每个节点都有自己的因子，我的任务是统计所有节点的数量，比如n5的数量是n.factor * n2.factor * n5.factor。

我认为问题出在指针上，但我不知道如何处理它。

下面的代码中有一些关于可能出错的想法。

对象.h

#include <string>
using namespace std;
class Obiekt
{
private:
string name;


public:
    Obiekt();
    Obiekt(string name);

    void wyswietlObiekt();
    string getName();

    ~Obiekt();
};

节点.h:

#include "Obiekt.h"
#include <vector>
#include <string>


using namespace std;

class Node {

public:

    Node();
    Node(Obiekt ob, double factor);

    void add(Node node);
    void show();
    vector<Node> getChildrenList();
    double getFactor();
    Obiekt getObiekt();


private:
    vector<Node> children;
    double factor;
    Obiekt obiekt;

};

节点.cpp:

#include "Node.h"
#include <string>
#include <vector>
#include <iostream>
#include <sstream>
#include <cstdlib>

using namespace std;


Node::Node()
{
    obiekt = Obiekt();
    factor = 0.0;
}

Node::Node(Obiekt ob, double mn)
{
    obiekt = ob;
    factor = mn;
}

void Node::show()
{
    for (int i = 0; i < children.size(); i++) {

        cout << children[i].getFactor() << endl;
    }
}


void Node::add(Node node)
{
    children.push_back(node);
}



vector<Node> Node::getChildrenList()
{
    return children;
}

double Node::getFactor()
{
    return factor;
}

Obiekt Node::getObiekt()
{
    return obiekt;
}

树.h:

#include <string>
#include <vector>
#include "Node.h"

using namespace std;


class Tree
{

public:
    Tree();

    void addNode(Node *parent, Obiekt o, double mnoznik);
    void addNode(Node *parent, Node wezel);
    void deleteTree();
    double countNodes(Node node, string key);
    vector<Node*> getList();
    double search(string key);

private:
    vector<Node*> nodeTree;
    Node root;
};

和 Tree.cpp:

#include "Tree.h"
#include <string>
#include <vector>
#include <iostream>
#include <sstream>
#include <cstdlib>

using namespace std;

Tree::Tree()
{
    root = Node();
}

void Tree::addNode(Node *parent, Obiekt o, double mnoznik)
{
    Node n(o, mnoznik);

    nodeTree.push_back(&n);

    if (parent == NULL)
    {
        root = Node(o, mnoznik);
        cout << "mnoznik korzenia: " << root.getFactor() << endl;
    }
    else
    {
        parent->add(n);
    }
}

void Tree::addNode(Node *parent, Node wezel)
{
    nodeTree.push_back(&wezel);

    if (parent == NULL)
    {
        root = wezel;
        cout << "mnoznik korzenia: " << root.getFactor() << endl;
    }
    else
    {
        parent->add(wezel);
        cout << "added: " << wezel.getFactor() << endl;
    }
}

double Tree::countNodes(Node node, string key)
{
    int rozmiar = nodeTree.size();

    double factor = node.getFactor();
    double iloczynTemp = 1.0;
    double quantity = 0.0;

    for (Node node : node.getChildrenList())
    {
        iloczynTemp = factor * node.getFactor();

        if (node.getObiekt().getNazwa() == key)
        {
            quantity = quantity + iloczynTemp;
        }

        quantity = quantity + countNodes(node, key);
    }

    return quantity;
}

double Tree::search(string key)
{
    double wynik = 0.0;
    for (Node *n : nodeTree)
    {
        if (n->getObiekt().getNazwa() == key)
        {
            wynik = wynik + n->getFactor();
        }
    }
    return wynik;
}


void Tree::deleteTree()
{
    nodeTree.clear();
}


vector<Node*> Tree::getList()
{
    return nodeTree;
}

int main()
{

    Tree tree;

    Node n(Obiekt("n"), 1.0);

    tree.addNode(NULL, n);

    Node n2(Obiekt("n2"), 2.0);
    tree.addNode(&n, n2);
    Node n3(Obiekt("n3"), 3.0);
    tree.addNode(&n, n3);
    Node n4(Obiekt("n4"), 4.0);
    tree.addNode(&n, n4);

    Node n5(Obiekt("n5"), 5.0);
    tree.addNode(&n2, n5);

    n.show();

    cout << n.getChildrenList().size() << endl;
    cout << n2.getChildrenList().size() << endl;
    cout << n.getChildrenList()[0].getChildrenList().size() << endl;


    system("pause");
    return 0;
}

问题出现在 main() 中

cout << n.getChildrenList().size() << endl;      // right result = 3
cout << n2.getChildrenList().size() << endl;     // right result = 1
cout << n.getChildrenList()[0].getChildrenList().size() << endl;  // wrong result, should be 1 like above, but it is 0, why?

另一个问题是在 Tree.cpp 中的 countNodes 方法中:

    quantity = quantity + countNodes(node, key); // why countNodes(node, key) is 0, it should be 0 when node don't have children, but some of them has.

提前谢谢你，bakii!

Answer 1

我在这段代码中看到的最大问题是您混合使用了指针和按值传递的项目。一个不好的例子:

void Tree::addNode(Node *parent, Obiekt o, double mnoznik)
{
    Node n(o, mnoznik);

    nodeTree.push_back(&n);
    ...

在这一行中，您在 addNode() 函数的上下文中在堆栈上创建了一个本地对象，然后将其地址 压入您的 vector 中。在此函数结束时，n 将超出范围，地址将不再有效。很可能在后续调用中会重复使用该地址，但您已进入未定义行为领域，而且不会产生任何好处。

对于这种结构，您可能希望自始至终都使用指针。与其像这样在堆栈上分配节点，不如这样:

Node* n = new Node(o, mnoznik);
nodeTree.push_back(&n);

在您的析构函数中，您可能希望删除 vector 中的所有节点。

通过更多的工作，您可能会想出一个基于全值的树，或者能够使用智能指针来处理您的内存管理，但我认为这超出了这个问题的范围。