Реализация неориентированного графа с матрицей смежности

Я пытался реализовать неориентированный граф с матрицей смежности.
Тип значения вершины — целое число. И я использую двойной указатель для представления матрицы смежности.

Вопрос в том, что сразу после того, как я ввел все значения вершин, как я
запрограммировал из кода, который я разместил ниже,
произошла ошибка времени выполнения. Затем я добавил комментарий к строке с содержанием ошибки,
из которой возникает ошибка. Я знаю, что причиной должен быть двойной указатель
, который я выделил. Но я действительно понятия не имею, как его отлаживать.
Может ли кто-нибудь мне помочь? Благодарю вас!

#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
    int adj;
}verNode;
typedef struct graph
{
    verNode **matrix;
    int* verList;
    int verNum;
    int edgeNum;
}graph;
graph* createGraph(int v)
{
    graph *g=malloc(sizeof(graph));
    if(!g) exit(-1);
    g->matrix=NULL;
    g->verList=malloc(sizeof(verNode)*v);
    if(!g->verList) exit(-1);
    g->verNum=v;
    printf("Enter the value of vertices:\n");
    for(int i=0;i<g->verNum;i++)
    {
        printf("Enter the value of vertex %d:\n",i);
        scanf("%d",g->verList);
    }
    return g;
}
verNode** createMatrix(graph *g)
{
    if(!g) exit(-1);
    g->matrix=malloc(sizeof(int*)*g->verNum*g->verNum);
    if(!g->matrix) exit(-1);
    for(int i=0;i<g->verNum;i++)
    {
        for(int j=0;j<g->verNum;j++)
        {
            (*g->matrix)->adj=0; //error:EXC_BAD_ACCESS (code=1,           //address=0x0)
        }
    }
    return g->matrix;
}
void addEdge(graph *g,int v)
{
    if(!g||!g->matrix||!g->verList) exit(-1);
    int ver1,ver2;
    g->edgeNum=v;
    printf("Enter the indexes of the vertices:\n");
    for(int i=0;i<g->edgeNum;i++)
    {
        printf("Enter the index of vertex 1:\n");
        scanf("%d",&ver1);
        printf("Enter the index of vertex 2:\n");
        scanf("%d",&ver2);
        if(ver1>g->verNum-1||ver2>g->verNum-1) exit(-1);
        g->matrix[ver1][ver2].adj=1;
        g->matrix[ver2][ver1].adj=1;
    }
}
void printMatrix(graph *g)
{
    if(!g||!g->matrix||!g->verList) exit(-1);
    printf("Print the adjacency matrix:");
    for(int i=0;i<g->verNum;i++)
    {
        for(int j=0;j<g->verNum;j++)
        {
            printf("%d ",g->matrix[i][j].adj);
        }
        printf("\n");
    }
}
int main() {
    graph *g=createGraph(5);
    verNode **matrix =createMatrix(g);
    g->matrix=matrix;
    addEdge(g,7);

    return 0;
}

c undirected-graph double-pointer
person Liu    schedule 24.04.2019    source источник

Ответы (2)


arrow_upward
0
arrow_downward

Здесь:

g->matrix = malloc(sizeof(int*) * g->verNum * g->verNum);

вы выделяете плоский одномерный массив размером VV. Вы обращаетесь к этому массиву, как если бы это был двумерный массив: g->matrix[i][j].adj.

Представление матрицы смежности в виде двумерного массива — хорошая идея, но ваше выделение также должно быть двумерным: выделите массив указателей V на int, затем сделайте каждый из этих указателей дескриптором массив V целых чисел:

g->matrix = malloc(g->verNum * sizeof(*g->matrix));

for (int i = 0; i < g->verNum; i++) {
    g->matrix[i] = calloc(g->verNum, sizeof(*g->matrix[i]));    
}

Что следует отметить:

  • calloc(n, size) похож на malloc(n*size), но сначала обнуляет память, так что вы начинаете с несвязанного графа.
  • p = malloc(n * sizeof(*p)) — полезная идиома, которая выводит тип из p, а не указывает тип явно.
  • Есть и другие способы получить двумерный массив. Например, вы можете выделить плоский массив размерностью VV, как вы сделали, а затем сделать matrix массивом указателей на этот массив, так что matrix[i] представляет строку в плоский массив. Я думаю, что для целей обучения подход, описанный выше, лучше, потому что он более прямолинеен.
  • Конечно, вы должны free выделенную память free позже. Сделайте это в обратном порядке: сначала освободите matrix[i], затем собственно matrix.
person M Oehm    schedule 24.04.2019

arrow_upward
0
arrow_downward

Вы объявили graph.matrix как vernode **. Вы выделили память для конкретного экземпляра g->matrix, судя по всему, успешно. *g->matrix обозначает vernode *, появляющийся в начале этого пробела (и, учитывая, что вы собираетесь использовать пробел в качестве массива, было бы более привычным обозначить этот элемент как g->matrix[0], что эквивалентно). Но вы никогда не присваивали значение этому объекту. Его значение неопределенно, и вы вызываете неопределенное поведение, пытаясь получить к нему доступ.

В целом, похоже, что вы смешали аспекты нескольких разных подходов. Это выделение...

g->matrix=malloc(sizeof(int*)*g->verNum*g->verNum);

... неправильно, во-первых, потому что небезопасно предполагать, что sizeof(int *) совпадает с sizeof(vernode *), а последнее - это то, что вам действительно нужно, учитывая объявленный тип g->matrix. Это кажется неправильным еще и потому, что вы выделяете гораздо больше места, чем я ожидал бы для подхода, основанного на двойном указателе. Обычно для каждой строки выделяется один указатель, а не по одному для каждого элемента, а затем отдельно выделяется память для элементов каждой строки. Тогда это будет поддерживать двойное индексирование, как если бы у вас был добросовестный двумерный массив: g->matrix[i][j].adj = 0;.

Вы можете использовать только одно выделение для всех вершин, но тогда вам понадобится один указатель (vernode *matrix;), и вам нужно будет использовать другие вычисления индекса: g->matrix[i * g->verNum + j].adj = 0;.

person John Bollinger    schedule 24.04.2019
comment
небезопасно предполагать, что sizeof(int *) совпадает с sizeof(vernode *)? размер указателя всегда одинаков и не зависит от типа указателя, к счастью - person bruno; 24.04.2019
comment
Это часто так, @bruno, систематически так во многих реализациях, но на самом деле это не гарантируется. - person John Bollinger; 24.04.2019
comment
Большое спасибо - person Liu; 25.04.2019