邻接表的实现在c++中使用链表



我见过很多邻接表的实现。在这里,我尝试使用c++来实现它。从我的c++结构可以看出,我在c++方面完全是个新手。在这里,我正在努力让我的代码运行。我现在的问题是,它不能遍历整个图。就会出现分割错误。结果:

顶点:01 ->

顶点:1

2 -> 3 ->

顶点:2

顶点:3

顶点:4

段错误

我需要一些帮助让这个运行起来。我想实现DFS算法。任何建议都会很棒!!

标题:

#ifndef DFS_H
#define DFS_H
class DFS{
private:
    struct vertex{
        int data;
        bool visited;
        struct vertex* next;
    };  
    int V;
    struct vertex* G[20];
public:
    DFS(int vertices);
    vertex* addVertex(int data);
    void addEdge(int index, int data);
    void dfs(int vertex);
    void printGraph();
};
#endif

cpp文件:

#include "DFS.h"
#include <iostream>
#include <cstdlib>
using namespace std;
DFS:: DFS(int vertices){
    this->V=vertices;
    for(int i=0; i<V; i++){
        G[i]= NULL; 
    }
}
DFS::vertex* DFS::addVertex(int data){
    struct vertex* newNode= new vertex;
    newNode->data= data;
    newNode->next= NULL;
    newNode->visited=false;
    return newNode;
}
void DFS:: addEdge(int index, int data){
    struct vertex* cursor;
    struct vertex* newVertex= addVertex(data);
    if(G[index]==NULL)
        G[index]=newVertex;
    else{
        cursor=G[index];
        while(cursor->next!=NULL)
            cursor=cursor->next;
        cursor->next= newVertex; 
    }
}
void DFS::printGraph(){
    for(int i=0; i<V; i++){
        struct vertex* cursor= G[i];
        cout<<"vertex: "<<i<<endl;
        while(cursor->next!=NULL){
            cout<<cursor->data<<"->";
            cursor=cursor->next;    
        }
        cout<<endl;
    }
}
void DFS:: dfs(int vertex){
}
int main(){
    DFS dfs(5);
    dfs.addEdge(0,1);
    dfs.addEdge(0,4);
    dfs.addEdge(1,2);
    dfs.addEdge(1,3);
    dfs.addEdge(1,4);
    dfs.addEdge(2,3);
    dfs.addEdge(3,4);
    dfs.printGraph();
    return 0;   
}
*

感谢Stackoverflow社区的帮助!

区段故障来自printGraph,它假设所有V顶点都存在,这在您的情况下是不正确的。注意没有dfs.addEdge(4, ...)初始化第5个顶点

一般来说,长度必须匹配稍后设置的元素数量的方法是自找麻烦,我将使用vector来重构此代码用于存储。

另一个问题是addEdge总是实例化一个新的vertex,这意味着dfs.addEdge(1,3)dfs.addEdge(2,3)之后,顶点1和2将指向顶点3的不同实例。

另一件事:addEdge(1,2)addEdge(1,3)将留给您边缘1->22->3。我假设结果应该是边1->21->3

更不用说从addVertex返回一个裸new ed指针是在请求内存泄漏;我建议使用auto_ptr (unique_ptr如果你是在c++ 11)。

另一件事是,当std::forward_list可用时,你正在重新实现前向链表。

这些只是我通过查看您的代码发现的一些问题。我相信还有更多,因为老实说,它看起来很糟糕(无意冒犯,我们都曾经是初学者)。我建议@Beta说:一次学习和练习一件事(建立一个顶点列表,当你对如何表示边感到舒服时,然后尝试遍历它,建立一个简单的算法,等等)。

相关内容

  • 没有找到相关文章