指向结构的指针的 Vector 的元素具有相同的地址

Question

我正在尝试实现一个不相交的森林数据结构。简而言之，它是一种没有共同元素的集合的数据结构，可以很容易地进行诸如合并2个集合和找到一个元素的集合等操作。每个集合都有一定数量的元素。

我将一个集合实现为一棵树，集合中的每个元素都是一个节点类型。这是我的 DisjointForesh.h 文件：

#ifndef STD_VECTOR
#define STD_VECTOR
#include <vector>
#endif

#ifndef DISJOINTFOREST_DISJOINTFOREST_H
#define DISJOINTFOREST_DISJOINTFOREST_H

struct TreeRoot;

struct Node{
    int rank = 0;
    int id;
    TreeRoot* parentTree;
    Node* parent;
    int value;
};

struct TreeRoot{
    std::vector<Node *> nodes;
    int id;
};

TreeRoot makeSet(int x);
.......

#endif //DISJOINTFOREST_DISJOINTFOREST_H

DisjointForest.cpp:

#ifndef STD_VECTOR
#define STD_VECTOR
#include <vector>
#endif
#include "DisjointForest.h"

TreeRoot makeSet(int x){
    TreeRoot tree;
    Node node;
    node.value = x;
    node.parent = &node;
    tree.nodes.push_back(&node);
    tree.id = node.value;
    node.parentTree = &tree;
    return tree;
}
........

最初，我制作了一棵包含一个节点的树。节点 parent 指向自身（最初），而 parentTree 指向该节点所属的树。每个树都有一个指向节点的指针向量，确定它包含的所有节点和一个 id，它与创建它的节点的 vector/the 值中的第一个节点的值相同。

我计划进行许多联合操作，其中一个节点的父节点将指向其他节点，而 parentTree 将指向其他树。类似地，find-set(x) 操作应该 return 一棵树，其中节点 x 属于。

这是我的 main.cpp:

#include <iostream>
#include "DisjointForest.h"

void printParentAddress(TreeRoot &tree){
    for(Node* nodes: tree.nodes){
        std::cout << nodes->value << "-->" << nodes->parentTree->id << '\n';
    }
}

void printNodesInTree(TreeRoot &tree){
    for(Node* nodes: tree.nodes){
        std::cout << nodes->value << ' ';
    }
}


int main() {
    std::vector<TreeRoot> trees;
    std::vector<Node *> nodes;
    for(int index = 0; index < 8; ++index){
        TreeRoot tree = makeSet(index);
        Node *node = tree.nodes[0];
        trees.push_back(tree);
        nodes.push_back(node);
    }


    std::cout << "Total trees: " << trees.size() << '\n';
    std::cout << "Total nodes: " << nodes.size() << '\n';
//
    std::cout << "Printing all nodes with parent trees:\n";
    for(Node *node: nodes){
        std::cout << node->value << "-->" << node->parentTree->id << '\n';
        std::cout << node << '\n';
}

    return 0;
}

我得到以下输出：

Total trees: 8
Total nodes: 8
Printing all nodes with parent trees:
-749254164-->0
0x7ffe0cd60cf0
-749254164-->0
0x7ffe0cd60cf0
-749254164-->0
0x7ffe0cd60cf0
-749254164-->0
0x7ffe0cd60cf0
-749254164-->0
0x7ffe0cd60cf0
-749254164-->0
0x7ffe0cd60cf0
-749254164-->0
0x7ffe0cd60cf0
-749254164-->0
0x7ffe0cd60cf0

如您所见：

每个节点值都是垃圾值
每个节点都有相同的地址
父 ID 为 0，但应与节点值相同

我不明白为什么会出现以上三种情况。我期待 0-7 的值和每个值的不同地址 node.I 对 c++ 来说相对较新，因此，我发现很难调试这个程序。

你能帮我找出我哪里出错了吗？任何优化我的代码的建议也会有所帮助。如果需要任何其他信息，请告诉我。

Answer 1

TreeRoot makeSet(int x){
    TreeRoot tree;
    Node node;
    node.value = x;
    node.parent = &node;
    tree.nodes.push_back(&node);
    tree.id = node.value;
    node.parentTree = &tree;
    return tree;
}

node 是这个函数块的局部并且有自动存储。函数结束时，node的生命周期结束，自动销毁

返回的tree指向这个销毁的node。一旦函数returns.

，这些指针就会失效

for(Node *node: nodes){
    std::cout << node->value << "-->" << node->parentTree->id << '\n';

在这里，您通过无效指针间接尝试访问不存在的对象。程序的行为未定义。

指向结构的指针的 Vector 的元素具有相同的地址

Elements of a Vector of pointers to structs have same address

c++

data-structures

recursive-datastructures

disjoint-sets