c++ 我如何修复基于BST的图形，似乎是覆盖相同的顶点？

t2a7ltrp 于 2023-04-01 发布在其他

关注(0)|答案(1)|浏览(105)

我希望这不是一个重复，但我找不到任何类似的职位。
在此基础上的构建可能看起来过于复杂，但我正在尝试学习二叉排序树并将其应用到我的图形知识中。
目前，构建使用两个结构和一个类，一个结构用于Edges，一个用于Vectors，“Graph”类用作二叉搜索树。

// Vertex node stores name and neighbors
    struct Vertex {
        string name;
        vector<Edge *> *neighbors;
    };

    class Graph {
        // Functions like BST and stores a Vertex object with each node
        int value;
        Graph *left, *right;
        struct Vertex *node;

与程序的这一部分交互的函数是我的默认构造函数和参数化构造函数：

Graph::Graph() : value(0), left(NULL), right(NULL), node(){};

    Graph::Graph(int data, Vertex* node) {
        value = data;
        left = right = NULL;
        Vertex* newNode = new Vertex;
        newNode = node;
    };

addVertex函数：

Graph* Graph::addVertex(Graph* root, string name, int data){
        if (!root) {
            Vertex* newVertex = new Vertex;
            newVertex->name = name;
            newVertex->neighbors = new vector<Edge *>();
            node = newVertex;
            return new Graph(data, node);
        }
        if (value > root->value){
            root->right = addVertex(root->right, name, data);
        }
        else if (value < root->value){
            root->left = addVertex(root->left, name, data);
        }
        return root;
    };

我试着分别删除每个构造函数，尝试在构造函数中创建一个新的顶点。改变类和结构中的变量顺序。看起来程序只是在顶点上创建，并重复覆盖顶点。
我希望发生的是程序会创建一个新的Vertex并存储其名称以供以后比较，但我的输出是这样的：

Vertex name: g Graph Node Value: 3
    vertex name: g Neighbors:
    Vertex name: g Graph Node Value: 2
    vertex name: g Neighbors:
    Vertex name: g Graph Node Value: 1
    vertex name: g Neighbors:

所以我得到的值是在BST中分配给节点的，但我没有得到存储在顶点中的名称。

c++

来源：https://stackoverflow.com/questions/75838943/how-do-i-fix-bst-based-graph-that-seems-to-be-overwriting-the-same-vertex

1条答案

按热度按时间

bjp0bcyl1#

在你的图构造器中，你有：

Vertex* newNode = new Vertex;
    newNode = node;

在局部变量newNode中构造一个新顶点和指向它的指针。
然后将局部变量赋值为指向不同的顶点，即作为参数传入的顶点
然后退出。新构造的顶点保留，但没有任何东西可以引用它。这是内存泄漏。
你的代码还有很多其他的问题（左指针和右指针应该在Vertex类中，而不是Graph类中...），我在这里就不赘述了。
下面是一个完整的应用程序的代码，它可以满足您的需求：

#include <string>
#include <sstream>
#include <iostream>
#include <vector>

struct Edge
{
};

// Vertex node stores name, value and neighbors
struct Vertex
{
    std::string name;
    int value;
    std::vector<Edge *> *neighbors;
    Vertex *left, *right;

    Vertex(const std::string &n,
           int v)
        : name(n), value(v),
          left(0), right(0)
    {
    }
    std::string text() const
    {
        std::stringstream ss;
        ss << name << " " << value << "\n";
        return ss.str();
    }
};

// Functions like BST and stores a Vertex object with each node
class Graph
{
    struct Vertex *root;

public:
    /// @brief Construct empty graph
    Graph()
        : root(0)
    {
    }
    /// @brief Construct graph with root vertex
    /// @param name root vertex name
    /// @param value root vertex value

    cGraph(
        const std::string &name,
        int value)
    {
        root = new Vertex(name, value);
    }

    /// @brief Add root vertex to empty graph
    /// @param name
    /// @param value

    void setRoot(
        const std::string &name,
        int value)
    {
        if (root)
            throw std::runtime_error(
                "root already set");
        root = new Vertex(name, value);
    }

    /// @brief add vertex to graph
    /// @param name
    /// @param value
    /// @param cur  // application code must omit this parameter
    
    void addVertex(
        const std::string &name,
        int value,
        Vertex *cur = 0)
    {
        if (!cur) {
            if (!root)
                setRoot("defaultRoot", 0);
            cur = root;
        }

        if (value < cur->value)
        {
            if (!cur->left)
            {
                cur->left = new Vertex(name, value);
                return;
            }
            else
                addVertex(name, value, cur->left);
        }
        else
        {
            if (!cur->right)
            {
                cur->right = new Vertex(name, value);
                return;
            }
            else
                addVertex(name, value, cur->right);
        }
    }

    // display graph contents
    void text()
    {
        text(root);
    }

private:
    void text(Vertex *v)
    {
        if (!v)
            return;
        text(v->left);
        std::cout << v->text();
        text(v->right);
    }
};

main()
{
    Graph g;

    g.setRoot("A", 10);

    g.addVertex("B", 20);
    g.addVertex("C", 5);

    g.text();

    return 0;
}

其输出

C 5
A 10
B 20

赞(0）回复(0）举报 2023-04-01

我来回答

c++ 我如何修复基于BST的图形，似乎是覆盖相同的顶点？

1条答案

相关问题

热门标签

最新问答