c++ - C++ 指针、迭代器、图的邻接表表示的问题

Question

我之前有一个帖子:"Trouble with List or Pointers,..."并收到了一些关于指针的非常有用的信息。在更好地理解实现更改之后，我仍然有一些非常奇怪的行为:

创建了两个顶点，然后在它们之间创建了一条无向边。每个顶点都有一个指向入射到它的边的指针列表。使用此图，边计数不应为 0。但在计算边的过程中，我看到我的边列表得到了不同的位置，这可以解释我的计数问题。

这里是 couts 的简短读数:

顶点1的链表地址:0x1851018顶点2的链表地址:0x1851038

在顶点 1 我们有...边缘列表的地址是... 0x1851068

在 Vertex 2 我们有...边缘列表的地址是... 0x1851098

#include "MinCut.h"
#include <iostream>
#include <list>

struct undirected_edge;
class vertex;

struct undirected_edge
{
    vertex * start;
    vertex * end;
};

class vertex
{
    int vertexLabel;
    std::list<undirected_edge*> edgeList;
public:
    int getVertexNumber(){return vertexLabel;}
    std::list<undirected_edge*> * getPointerOfEdgeList(){
        std::cout << vertexLabel << " has edge List at: " << &edgeList << "\n";
    return &edgeList;}

    vertex(int n){vertexLabel=n;}
};


class undirected_graph
{
private:
    std::list<vertex>  graph;

public:
    void addVertex(vertex * v){graph.push_back(*v);}
    void createEdge(vertex * v1, vertex * v2);
    undirected_edge * getRandomEdge();
    void removeEdge(undirected_edge * e);
    int getNumberOfNodes(){return graph.size();}
    int getNumberOfEdges();
};
void buildGraph(undirected_graph *);

void undirected_graph::createEdge(vertex * v1, vertex * v2)
{
    std::list<undirected_edge*> * e1 = v1->getPointerOfEdgeList();
    std::list<undirected_edge*> * e2 = v2->getPointerOfEdgeList();
    undirected_edge * e = new undirected_edge;
    e->start=v1;
    e->end=v2;
    e1->push_back(e);
    e2->push_back(e);
    std::cout<< "The address of vertex 1's list: " << e1 << "\n";
    std::cout<< "The address of vertex 2's list: " << e2 << "\n";
}

int undirected_graph::getNumberOfEdges()
{    
    int size = getNumberOfNodes();
    std::list<vertex>::iterator it = graph.begin();
    int counter = 0;
    for (int i = 0; i < size; i++)
    {
        std::cout<<"At Vertex " << it->getVertexNumber() << " we have...\n";
        std::cout<<"The address of the edge list is... " << it->getPointerOfEdgeList() << "\n";
        counter = counter + it->getPointerOfEdgeList()->size();
        std::cout<<it->getPointerOfEdgeList()->size()<<"\n";
        it++;
    }
    return counter;
}


int main()
{
    undirected_graph myGraph;
    buildGraph(&myGraph);
    return 0;
}

void buildGraph(undirected_graph * g)
{
    vertex * v1 = new vertex(1);
    vertex * v2 = new vertex(2);

    g->addVertex(v1);           
    g->addVertex(v2);
    g->createEdge(v1,v2);

    std::cout<<"The total number of edges: " << g->getNumberOfEdges();  
}

Answer 1

调用addVertex(vertex * v)时，您将顶点参数的拷贝添加到列表中 graph.push_back(*v) .因此顶点对象有不同的地址。

你可能想存储一个 std::list<vertex*>图和使用 graph.push_back(v) ，那么。