时间戳

首页 > 解决方案 > 指向结构的指针向量的元素具有相同的地址

c++ - 指向结构的指针向量的元素具有相同的地址

问题描述

我正在尝试实现一个不相交的森林数据结构。简而言之，它是一种没有共同元素的集合的数据结构，可以很容易地执行诸如组合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 指向节点所属的 Tree。每棵树都有一个指向节点的指针向量，确定它包含的所有节点和一个 id，该 id 与向量中第一个节点的值/创建它的节点的值相同。

我计划做许多联合操作，其中一个节点的父节点将指向其他节点，而 parentTree 将指向其他树。类似地，find-set(x) 操作应该返回节点 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

如你看到的：

  1. 每个 Nodes 值都是一个垃圾值
  2. 每个节点都有相同的地址
  3. 父 ID 为 0，但它应该与节点值相同

我不明白为什么会发生上述三个。我期待每个节点的值是 0-7 和不同的地址。我对 c++ 比较陌生，因此，我发现很难调试这个程序。

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

标签： c++data-structuresrecursive-datastructuresdisjoint-sets

解决方案

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是 this for 功能块的本地，并具有自动存储功能。在函数结束时，生命周期node结束并自动销毁。

返回的tree指向这个被破坏的node。一旦函数返回，这些指针就会变得无效。

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

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

推荐阅读