1

我正在尝试在 C++ 中实现有向图。但是,我的 RemoveEdge 函数有问题,在我调用该函数并在指针上使用 delete 运算符并将指针设置为nullptr之后,它不会在函数范围之外为空。

我不确定我是否已经足够清楚地说明了我的问题,但也许一些代码会有所帮助。

图.h

template<class TVertex, class TEdge, class TWeight>
class Graph
{
protected:
    std::list<Vertex<TVertex, TEdge, TWeight>*>* _Vertices;
    std::list<Edge<TVertex, TEdge, TWeight>*>* _Edges;
public:
    Graph();
    int TotalVertices();
    int TotalEdges();
    std::list<Vertex<TVertex, TEdge, TWeight>*>* Vertices();
    std::list<Edge<TVertex, TEdge, TWeight>*>* Edges();

    Vertex<TVertex, TEdge, TWeight>* FindVertex(const TVertex&);
    Vertex<TVertex, TEdge, TWeight>* InsertVertex(const TVertex&);
    void RemoveVertex(const TVertex&);

    Edge<TVertex, TEdge, TWeight>* FindEdge(const TEdge&);
    Edge<TVertex, TEdge, TWeight>* InsertEdge(const TVertex&, const TVertex&, const TEdge&, const TWeight&);
    void RemoveEdge(const TEdge&);
};

Graph.FindEdge()

template<class TVertex, class TEdge, class TWeight>
Edge<TVertex, TEdge, TWeight>* Graph<TVertex, TEdge, TWeight>::FindEdge(const TEdge& label)
{
    Edge<TVertex, TEdge, TWeight>* edge = nullptr;
    std::list<Edge<TVertex, TEdge, TWeight>*>::iterator it;

    for(it = this->_Edges->begin(); it != this->_Edges->end(); ++it)
    {
        if(label == (*it)->Label())
        {
            edge = *it;
            break;
        }
    }

    return edge;
}

Graph.RemoveEdge()

template<class TVertex, class TEdge, class TWeight>
void Graph<TVertex, TEdge, TWeight>::RemoveEdge(const TEdge& label)
{
    Edge<TVertex, TEdge, TWeight>* edge = this->FindEdge(label);
    if(edge == nullptr)
        return;

    this->_Edges->remove(edge);
    edge->Source()->RemoveEdge(edge);
    edge->Destination()->RemoveEdge(edge);

            // Problem is here, why isn't this working like I think it should?
    delete edge;
    edge = nullptr;
}

主文件

// created graph
// added vertices
// added edges
Edge<string, string, int>* e5 = graph->InsertEdge("Oshawa", "Toronto", "E5", 5);
graph->RemoveEdge("E5");
cout << ((e5 == nullptr) ? "null" : "not null") << endl; // this outputs not null

所以你可以看到我从图中删除边后我的程序崩溃了,由于某种原因,它not null在执行 RemoveEdge 函数后输出。我不确定为什么会发生这种情况,我使用了 delete 运算符,并且之后我还明确地使指针为空。我在这里做错了什么?

是的,我确定找到了边缘,FindEdge 函数找到了正确的边缘对象并将其从适当的列表中删除,但删除运算符没有做我想要它做的事情。

感谢任何帮助。提前致谢。

4

5 回答 5

5

e5是一个与类不同的局部变量edge

两者都可能指向内存中的同一个对象,但这并不意味着如果您将一个设为空,另一个也会指向空。

考虑这个简单的例子,

int i = 10;
int *p1 = &i;
int *p2 = p1;

//here p1 and p2 points to the same object in memory which is i
p1 = nullptr; //it makes only p1 point to null

//here only p2 points to i
cout << *p2 << endl; //ok
cout << *p1 << endl; //dangerous - undefined behaviour!

我希望这可以帮助您理解程序的行为!


然而,你可以做一个技巧。而不是使用T*,如果你使用T*&,那么你会得到预期的结果:

Edge<string, string, int>* & e5 = graph->InsertEdge("Oshawa", "Toronto", "E5", 5);
//                         ^ see this

graph->RemoveEdge("E5");
cout << ((e5 == nullptr) ? "null" : "not null") << endl;

它应该可以工作,因为 nowe5是对类中对象的引用,它不再是一个不同的对象,它更像是您在其中创建并保存在列表中的指针的别名。InsertEdge

i使用,p1的类似代码p2是这样的:

int i = 10;
int *p1 = &i;
int* & p2 = p1; //now it is a reference to p1, i.e an alias  of p1

//here p1 and p2 points to the same object in memory which is i

p1 = nullptr; //it makes only p1 point to null

//here both p1 and p2 points to null

 if ( p1 == nullptr)
       cout << "p1 points to null" << endl;
 if ( p2 == nullptr)
       cout << "p2 points to null" << endl;
 if ( p1 == p2)
       cout << "p1 and p2 are equal" << endl;

输出:

p1 points to null
p2 points to null
p1 and p2 are equal

演示:http: //ideone.com/ARiIl

还要注意这些:

//after p1 = nullptr
cout << *p2 << endl; //dangerous - undefined behaviour!
cout << *p1 << endl; //dangerous - undefined behaviour!
于 2011-12-06T07:44:00.967 回答
1

要解决功能之外的 e5 更新,您可以使用shared_ptrand weak_ptr

template<class TVertex, class TEdge, class TWeight>
class Graph
{
  typedef Vertex<TVertex,TEdge,TWeight> VextexType;
  typedef Edge<TVertex,TEdge,TWeight> EdgeType;

  typedef shared_ptr<VertexType> VertexPtr;
  typedef shared_ptr<EdgeType> EdgePtr;

protected:
    std::list< VertexPtr >* _Vertices;
    std::list< EdgePtr >* _Edges;
public:
    Graph();
    int TotalVertices();
    int TotalEdges();
    std::list<VertexPtr>* Vertices();
    std::list<EdgePtr>* Edges();

    VertexPtr FindVertex(const TVertex&);
    VertexPtr InsertVertex(const TVertex&);
    void RemoveVertex(const TVertex&);

    EdgePtr FindEdge(const TEdge&)
    {
        for( std::list<EdgePtr>::iterator it = this->_Edges->begin(); it != this->_Edges->end(); ++it)
        {
            if( label == (*it)->Label())
            {
                return *it;
            }
        }
        return EdgePtr();
    }

    EdgePtr InsertEdge(const TVertex&, const TVertex&, const TEdge&, const TWeight&);
    void RemoveEdge(const TEdge& label)
    {
        EdgePtr edge = this->FindEdge(label);
        if(!edge)
           return;

       this->_Edges->remove(edge);
       edge->Source()->RemoveEdge( edge.get() );
       edge->Destination()->RemoveEdge( edge.get() );
    }
};

现在您可以像这样在 main 中编写您的部分:

weak_ptr<Edge<string, string, int> > e5( graph->InsertEdge("Oshawa", "Toronto", "E5", 5) );
graph->RemoveEdge("E5");
cout << (e5 ? "null" : "not null") << endl;

请注意,我们使用weak_ptr 来存储返回值,而不是shared_ptr。

于 2011-12-06T07:44:05.803 回答
1

不要将在 main.cpp 中创建的指针设为空。你只是在你的 RemoveEdge 方法中清空一个指针。

如果要将 main.cpp 中的指针设为空,例如可以将其传递给 RemoveEdge 函数,这样就可以消除在列表中搜索的需要。

于 2011-12-06T07:44:13.513 回答
1

edgeMain.cpp中的inRemoveEdgee5in是两个不同的局部变量。为其中一个赋值不会改变另一个的值。

于 2011-12-06T07:44:25.210 回答
1

FindEdge返回列表中存在的指针的副本,您正在将其复制到指针的另一个副本edgein RemoveEdge)中。因此,当您将此设置为NULL仅修改此副本list时,不影响指针。

于 2011-12-06T07:45:12.357 回答