Неожиданная ошибка в тестировании и изучении графов в C

Question

Я недавно начал изучать эту конкретную книгу для алгоритмов и структуры данных SkienaTheAlgorithmDesignManual.pdf , от которой я услышал много похвал не только в Интернете, но и от моего учителя по разработке алгоритмов, какхорошо в колледже, и у меня возникли некоторые ошибки с кодом из книги на стр. 153 (в самой книге) или 165 (в формате PDF).

Вот код:

#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#define MAXV 1000
typedef struct  {
    int y;
    int weight;
    struct edgenode *next;
}edgenode;
typedef struct {
    edgenode *edges[MAXV + 1];
    int degree[MAXV + 1];
    int nvertices;
    int nedges;
    bool directed;
}graph;

void initialize_graph(graph *g, bool directed);
void read_graph(graph *g, bool directed);
void insert_edge(graph *g, int x, int y, bool directed);
void print_graph(graph *g);
void initialize_graph(graph *g, bool directed) {
    int i;

    g->nvertices = 0;
    g->nedges = 0;
    g->directed = directed;
    for (i = 1; i <= MAXV; i++) {
        g->degree[i] = 0;
        g->edges[i] = NULL;
    }

}

void read_graph(graph *g, bool directed) {
    int i;
    int m;
    int x, y;
    initialize_graph(g, directed);
    scanf("%d %d", &(g->nvertices), &m);
    for (i = 1; i <= m; i++) {
        scanf("%d %d", &x, &y);
        insert_edge(g, x, y, directed);
    }
}

void insert_edge(graph *g, int x, int y, bool directed) {
    edgenode *p;
    p = malloc(sizeof(edgenode));
    p->weight = NULL;
    p->y = y;
    p->next = g->edges[x];
    g->edges[x] = p;
    g->degree[x]++;
    if (directed == false)
        insert_edge(g, y, x, true);
    else
        g->nedges++;
}

void print_graph(graph *g) {
    int i;
    edgenode *p;
    for (i = 1; i <= g->nvertices; i++) {
        printf("%d ", i);
        p = g->edges[i];
        while (p != NULL) {
            printf(" %d", p->y);
            p = p->next;
        }
        printf("\n");
    }
}
main() {
    bool directed = true;
    graph *g;
    read_graph(g, directed);
    print_graph(g);
    system("pause");
}

Вот ошибки:

1> c: \ users \ dragos \ source \ repos \ learninggraph \ learninggraph \ main.c (47): предупреждение C4047:'=': 'int' отличается по уровням косвенности от 'void *' 1> c: \ users \ dragos \ source \ repos \ learninggraph \ learninggraph \ main.c (49): предупреждение C4133: '=': несовместимые типы- из 'edgenode *' в 'edgenode *' 1> c: \ users \ dragos \ source \ repos \ learninggraph \ learninggraph \ main.c (65): предупреждение C4133: '=': несовместимые типы - из 'edgenode *'to 'edgenode *' 1> c: \ users \ dragos \ source \ repos \ learninggraph \ learninggraph \ main.c (73): ошибка C4700: используется неинициализированная локальная переменная 'g' 1> Закончен сборочный проект "LearningGraph.vcxproj" - СБОЙ.========== Построение: 0 выполнено, 1 не выполнено, 0 обновлено, 0 пропущено ==========

Я думаю, что главная проблема - это «несовместимые типы», но я могу быть совершенно не прав.

Answer 1

In insert_edge

 p->weight = NULL;

недопустимо, потому что weight является int , но NULL aуказатель (обычно (void*)0)

In insert_edge

 p->next = g->edges[x];

недопустим, поскольку next является неопределенным типом struct edgenode *, ноedges[x] - это edgenode *.Чтобы решить, что вы должны заменить

typedef struct {
    int y;
    int weight;
    struct edgenode *next;
}edgenode;

на

typedef struct edgenode {
    int y;
    int weight;
    struct edgenode *next;
}edgenode;

Причина та же в print_graph line

 p = p->next;

Явно установите тип возврата main как int

В main вы звоните read_graph с g никогдаустановить / инициализировать так, чтобы при разыменовании в read_graph поведение не было определено, и это также имеет место в print_graph.Просто замените

 graph *g;
 read_graph(g, directed);
 print_graph(g);

на

graph g;
read_graph(&g, directed);
print_graph(&g);

---

Полная модифицированная версия:

#include <stdlib.h>
#include<stdio.h>
#include<stdbool.h>

#define MAXV 1000

typedef struct edgenode {
    int y;
    int weight;
    struct edgenode *next;
}edgenode;

typedef struct {
    edgenode *edges[MAXV + 1];
    int degree[MAXV + 1];
    int nvertices;
    int nedges;
    bool directed;
}graph;

void initialize_graph(graph *g, bool directed);
void read_graph(graph *g, bool directed);
void insert_edge(graph *g, int x, int y, bool directed);
void print_graph(graph *g);
void initialize_graph(graph *g, bool directed) {
    int i;

    g->nvertices = 0;
    g->nedges = 0;
    g->directed = directed;
    for (i = 1; i <= MAXV; i++) {
        g->degree[i] = 0;
        g->edges[i] = NULL;
    }

}

void read_graph(graph *g, bool directed) {
    int i;
    int m;
    int x, y;
    initialize_graph(g, directed);
    scanf("%d %d", &(g->nvertices), &m);
    for (i = 1; i <= m; i++) {
        scanf("%d %d", &x, &y);
        insert_edge(g, x, y, directed);
    }
}

void insert_edge(graph *g, int x, int y, bool directed) {
    edgenode *p;
    p = malloc(sizeof(edgenode));
    p->weight = 0;
    p->y = y;
    p->next = g->edges[x];
    g->edges[x] = p;
    g->degree[x]++;
    if (directed == false)
        insert_edge(g, y, x, true);
    else
        g->nedges++;
}

void print_graph(graph *g) {
    int i;
    edgenode *p;
    for (i = 1; i <= g->nvertices; i++) {
        printf("%d ", i);
        p = g->edges[i];
        while (p != NULL) {
            printf(" %d", p->y);
            p = p->next;
        }
        printf("\n");
    }
}

int main() {
    bool directed = true;
    graph g;
    read_graph(&g, directed);
    print_graph(&g);
    system("pause");
}

Компиляция:

pi@raspberrypi:/tmp $ gcc -pedantic -Wall -Wextra g.c
pi@raspberrypi:/tmp $ 

Answer 2

Вы никогда не выделяли память для graph *g.

Нет необходимости указывать это, делать его нормальной переменной и передавать его адрес функциям.

int main() {
    bool directed = true;
    graph g;
    read_graph(&g, directed);
    print_graph(&g);
    system("pause");
}