c++ - 特定值的段错误

Question

我写了一段代码，它首先将矩阵的维度 (n X m) 作为输入，然后是它的元素 0 和 1s。现在我正在尝试使用此矩阵构建一个图(邻接列表表示)，以便所有 1 都连接到它们相邻的所有其他 1(即，垂直，水平或对角)。矩阵的元素以行主要方式编号，以便将它们表示为图的顶点。

代码如下:

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <stdlib.h>
#include <list>
#include <deque>

using namespace std;

class Graph
{
 public:

    list<int> *adjlist;
    int v;

    Graph(int v)
    {
        this->v=v;
        adjlist=new list<int> [v];      
    }

    void add_edge(int src, int dest)
    {
        cout<<src<<" "<<dest<<"\n";
        adjlist[src].push_back(dest);
    }

    void dfs_util(int src, bool *visited)
    {
        if(!visited[src])
        {
            cout<<src<<" ";
            visited[src]=true;
            list<int>::iterator i;
            for(i=adjlist[src].begin(); i!=adjlist[src].end(); i++)
            {
                if(!visited[*i])
                {
                    dfs_util(*i, visited);
                }
            }
        }
    }

    void dfs(int src)
    {
        bool visited[v];
        int i;
        for(i=0; i<v; i++)
            visited[i]=false;
        dfs_util(src, visited);
    }

    void bfs(int src)
    {
        int j;
        bool visited[v];
        for(j=0; j<v; j++)
        {
            visited[j]=false;
        }

        int front;
        deque<int> q;
        q.push_back(src);
        list<int>::iterator i;
        visited[src]=true;


        while(!q.empty())
        {
            front=q.front();
            q.pop_front();
            cout<<front<<" ";

            for(i=adjlist[front].begin(); i!=adjlist[front].end(); i++)
            {
                cout<<*i<<"\n";
                if(!visited[*i])
                {
                    visited[*i]=true;
                    q.push_back((*i));
                }
            }
        }
    }

    void display()
    {
        list<int>::iterator it;
        int i;
        //list<int>::iterator it;

        for(i=0; i<v; i++)
        {           
            cout<<"Adj list for "<<i<<"\n";
            for(it=adjlist[i].begin(); it != adjlist[i].end(); ++it)
            {
                cout<<*it<<"->";
            }
            cout<<"\n";
        }
    }
};


int main() {
    int arr[11][11], n, m, i, j, node;
    cin>>n;
    cin>>m;

    for(i=0; i<n; i++)
    {
        for(j=0; j<m; j++)
        {
            cin>>arr[i][j];
        }
    }

    Graph g(n*m-1);

    for(i=0; i<n; i++)
    {
        for(j=0; j<m; j++)
        {
            node=m*i+j;
            if(arr[i][j]==1)
            {
                if((i-1)>=0 && arr[i-1][j]==1)
                    g.add_edge(node, m*(i-1)+j);

                if((i-1)>=0 && (j+1)<m && arr[i-1][j+1]==1)
                    g.add_edge(node, m*(i-1)+(j+1));

                if((j+1)<m && arr[i][j+1]==1)
                    g.add_edge(node, m*(i)+(j+1));

                if((i+1)<n && (j+1)<m && arr[i+1][j+1]==1)
                    g.add_edge(node, m*(i+1)+(j+1));

                if((i+1)<n && arr[i+1][j]==1)
                    g.add_edge(node, m*(i+1)+(j));

                if((i+1)<n && (j-1)>=0 && arr[i+1][j-1]==1)
                    g.add_edge(node, m*(i+1)+(j-1));

                if((j-1)>=0 && arr[i][j-1]==1)
                    g.add_edge(node, m*(i)+(j-1));

                if((i-1)>=0 && (j-1)>=0 && arr[i-1][j-1]==1)
                    g.add_edge(node, m*(i-1)+(j-1));
            }
        }       
    }

    //g.bfs(0);
    //g.dfs(0);
    g.display();
    return 0;
}

现在这段代码在调用 g.bfs(0) 或 g.dfs(0) 时给了我段错误。所以我写了一个简单的显示函数来缩小错误范围，但即使调用 g.display() 也会给我 segmentation fault。

然而，当我将 display() 函数中的外循环更改为:

for(i=1; i<n; i++)

它工作得很好，不会出现段错误。

我不明白为什么我会收到这些段错误，以及如何将外循环的初始化更改为1 来阻止它。谁能解释一下原因？

这是我使用的示例输入:

5
5
1 1 0 0 0
0 1 1 0 0
0 0 1 0 1
1 0 0 0 1
0 1 0 1 1

Answer 1

问题

您的邻接表是一个数组，而不是列表或 vector :

list<int> *adjlist;

您在构造函数中根据参数 v 对其进行初始化:

adjlist=new list<int> [v];      

因此，在构建图形时，您需要提前提供有多少个邻接表？所以最好不要弄错!

不幸的是，在 main() 中，您使用缺少的项目对其进行了初始化

Graph g(n*m - 1);   //  <----- why -1 ?  Don't you have n*m nodes ?

解决方案

只需调用具有正确大小的构造函数

Graph g(n*m);   //  n*m nodes ! 

如果遇到这样的问题，您可以通过添加一些绑定(bind)检查来帮助自己:

void add_edge(int src, int dest)   // src should be smaller than v 
{
    if (src>=v) {         // nice diagnostic message in case of problem
       cout <<"FAILURE: "<<src<<" out of bound ("<<v<<")"<<endl; 
    }
    else {
        cout<<src<<" "<<dest<<"\n";
        adjlist[src].push_back(dest);
    }
}

如果不总是像那样实现漂亮的错误消息，它至少应该成为对 assert 的反射。满足先决条件:

assert (src<v && dest<v);   

更好的办法是让你的邻接列表 adjlist 成为一个 vector 或 map ，并让它动态增长。