Как исправить ошибку «ошибка чтения памяти из 0x4000000000000000 (чтение 0 байт)» в C

Question

У меня есть простое упражнение на C. Но когда я инициализирую свой граф переменных с помощью malloc, он не выполняет действие правильно.Вот мой код:

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

typedef int Weight;

typedef struct aux {
    int vDest;
    Weight weight;
    struct aux * next;
} TypeEdge;

typedef TypeEdge* TypePointer;

typedef struct {
    TypePointer * listAdj;
    int numVertices;
    int numEdges;
} TypeGraph;

typedef int* TipoInt;

bool initializeGraph(TypeGraph *graph, int nv) {
    if (nv < 0) {
        return false;
    }

    graph->numVertices = nv;
    graph->numEdges = 0;
    int i;
    for (i = 0; i < nv; i++) {
        graph->listAdj = (TypePointer*) malloc(sizeof(TypePointer));
    }
    for (i = 0; i < nv; i++) {
        graph->listAdj[i] = NULL;
    }
    return true;
}

void insertEdge(int v1, int v2, Weight weight, TypeGraph *graph) {
    if (v1 < 0 || v1 > graph->numVertices || v2 < 0 || v2 > graph->numVertices) {
        return;
    }
    TypePointer actual = graph->listAdj[v1];
    while (actual->next) {
        actual = actual->next;
    }
    TypePointer pNew = (TypePointer) malloc(sizeof(TypeEdge));
    pNew->vDest = v2;
    pNew->weight = weight;
    pNew->next = NULL;
    actual->next = pNew;
}

int main() {
    TypeGraph graph;
    bool result = initializeGraph(&graph, 100);
    if (result) {
        insertEdge(2, 3, 1, &graph);
    }
    return 0;
}

Проблема в том, что вместо инициализации графа размером в сотню TypePointer он инициализирует только размер два и не выполняет никаких действий.Когда я пытаюсь отладить его на Clion, появляется сообщение об ошибке: read memory from 0x4000000000000000 failed (0 of 4 bytes read).Если я просто запускаю код, он возвращает код одиннадцать.

Пожалуйста, кто-нибудь может мне помочь?

Answer 1

В ваших initializeGraph и insertEdge есть что-то не так.Это изменение должно работать для вас

bool initializeGraph(TypeGraph *graph, int nv)
{
    if (nv < 0) {
        return false;
    }

    graph->numVertices = nv;
    graph->numEdges = 0;

    /* call `calloc` to avoid using for-loop to zero memory */
    graph->listAdj = calloc(nv, sizeof(TypePointer));

    return true;
}

void insertEdge(int v1, int v2, Weight weight, TypeGraph *graph)
{
    if (v1 < 0 || v1 > graph->numVertices || v2 < 0 || v2 > graph->numVertices) {
        return;
    }

    /* just insert the node at the head of the adjList */
    TypePointer pNew = malloc(sizeof(TypeEdge));

    pNew->vDest = v2;
    pNew->weight = weight;
    pNew->next = graph->listAdj[v1];
    graph->listAdj[v1] = pNew;
    graph->numEdges++;
}

Что касается typedef , пожалуйста, прочитайте Почему мы должны так часто печатать структуру в C? и .Ядро Linux CodingStyle документ , чтобы принять собственное решение, использовать его или нет.Лично я сам избегаю использования typedef без необходимости.

Answer 2

У вас действительно большой беспорядок в ваших руках. Вы внесли свой вклад в typedef указателей, но в основном потому, что вам не удалось выделить nv указателей, а вместо этого выделить тот же указатель listAdj, а затем сразу же перезаписать указатель с помощью NULL, создав 100 утечек памяти.

Подумайте об этом:

    for (i = 0; i < nv; i++) {
        graph->listAdj = (TypePointer*) malloc(sizeof(TypePointer));
    }

(Нет необходимости приводить к возврату malloc, это не нужно. См .: Приводит ли я результат malloc? и ... ВСЕГДА проверяет КАЖДОЕ распределение)

graph->listAdj - это одиночный указатель, который содержит адрес для вновь выделенного блока памяти на каждой итерации, который затем перезаписывается при каждом последующем выделении.

Далее вы пытаетесь разыменовать перезаписанный указатель и устанавливаете несуществующие указатели на NULL, например ::

    for (i = 0; i < nv; i++) {
        graph->listAdj[i] = NULL;
    }

Вы пытались выделить только один graph->listAdj (хотя и 100 раз), а не nv указатели, как вы и предполагали. Вы должны выделить память для nv указателей одновременно.

Теперь давайте начнем с самого начала и очистим все, удалив ВСЕ typedef с, и просто используя int для bool, например,

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

typedef struct aux {
    int vDest;
    int weight;
    struct aux *next;
} TypeEdge;

typedef struct {
    TypeEdge **listAdj;
    int numVertices;
    int numEdges;
} TypeGraph;

Теперь всем, кто смотрит на ваш код, совершенно очевидно, что listAdj является указателем на указатель на TypeEdge. Нет смысла гадать или охотиться позже, задаваясь вопросом, что TypePointer 300 строк позже, TypeEdge - это TypeEdge, ничего более.

Когда вы initializeGraph, вам нужно выделить все nv указатели - это один вызов malloc, а не в цикле. Затем вы можете зацикливать указатели, устанавливая их все NULL, например,

int initializeGraph (TypeGraph *graph, int nv)
{
    if (nv < 0)
        return 0;

    graph->numVertices = nv;
    graph->numEdges = 0;
    int i;

    if ((graph->listAdj = malloc(sizeof *graph->listAdj * nv)) == NULL) {
        perror ("malloc-graph->listAdj");
        return 0;
    }

    for (i = 0; i < nv; i++)
        (graph->listAdj)[i] = NULL;

    return 1;
}

Далее, когда вы insertEdge(), вы должны обработать случай, когда вы вставляете первое ребро для этой вершины, или вам нужно выполнить итерацию до конца списка и вставить туда. Вам также необходимо настроить способ итерации до конца, чтобы не пытаться получить доступ к actual->next, если actual равно NULL. Собрав это вместе, вы можете сделать:

TypeEdge *insertEdge (int v1, int v2, int weight, TypeGraph *graph) 
{
    if (v1 < 0 || v1 > graph->numVertices || 
        v2 < 0 || v2 > graph->numVertices) {
        return NULL;
    }

    TypeEdge *actual = graph->listAdj[v1];
    while (actual && actual->next)
        actual = actual->next;

    TypeEdge *pNew = malloc(sizeof *pNew);
    if (!pNew) {
        perror ("malloc-pNew");
        return NULL;
    }

    pNew->vDest = v2;
    pNew->weight = weight;
    pNew->next = NULL;

    if (!actual)
        graph->listAdj[v1] = pNew;
    else
        actual->next = pNew;

    return (pNew);
}

( примечание: , как тип возвращаемого значения функции был изменен на TypeEdge * с void, так что у вас есть значимое возвращение, которое может указывать на успех / неудачу вашей попытки вставить ребро. Никогда не выделяйте внутри функции void, не имея возможности указать вызывающей функции, было ли выделение (и остаток критических шагов) успешным или неудачным)

Пока ваш main() пытается insertEdge(), он не дает никаких сведений о том, что произошло. Если у вас нет какого-либо способа проверки правильности вставленного края, это заставляет задуматься. Просто напишите короткий набор print функций для обработки вывода списка ребер для каждой вершины, в которой они есть, например,

void prnedge (const TypeEdge *e)
{
    do
        printf (" %3d %3d\n", e->vDest, e->weight);
    while ((e = e->next));
}

void print_edge (const TypeEdge *e, int edge)
{
    printf ("\nedge %d\n", edge);
    prnedge (e);
}

void print_graph (const TypeGraph *g)
{
    for (int i = 0; i < g->numVertices; i++)
        if (g->listAdj[i])
            print_edge (g->listAdj[i], i);
}

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

void freelist (TypeEdge *l)
{
    while (l) {
        TypeEdge *victim = l;
        l = l->next;
        free (victim);
    }
}

void free_graphlists (TypeGraph *g)
{
    for (int i = 0; i < g->numVertices; i++)
        if (g->listAdj[i])
            freelist (g->listAdj[i]);

    free (g->listAdj);
}

На который вы можете позвонить main() как:

int main (void) {

    TypeGraph graph;
    int result = initializeGraph (&graph, 100);

    if (result) {
        insertEdge (2, 3, 1, &graph);
        insertEdge (2, 4, 1, &graph);
    }

    print_graph (&graph);
    free_graphlists (&graph);

    return 0;
}

В целом, вы можете сделать:

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

typedef struct aux {
    int vDest;
    int weight;
    struct aux *next;
} TypeEdge;

typedef struct {
    TypeEdge **listAdj;
    int numVertices;
    int numEdges;
} TypeGraph;

int initializeGraph (TypeGraph *graph, int nv)
{
    if (nv < 0)
        return 0;

    graph->numVertices = nv;
    graph->numEdges = 0;
    int i;

    if ((graph->listAdj = malloc(sizeof *graph->listAdj * nv)) == NULL) {
        perror ("malloc-graph->listAdj");
        return 0;
    }

    for (i = 0; i < nv; i++)
        (graph->listAdj)[i] = NULL;

    return 1;
}

TypeEdge *insertEdge (int v1, int v2, int weight, TypeGraph *graph) 
{
    if (v1 < 0 || v1 > graph->numVertices || 
        v2 < 0 || v2 > graph->numVertices) {
        return NULL;
    }

    TypeEdge *actual = graph->listAdj[v1];
    while (actual && actual->next)
        actual = actual->next;

    TypeEdge *pNew = malloc(sizeof *pNew);
    if (!pNew) {
        perror ("malloc-pNew");
        return NULL;
    }

    pNew->vDest = v2;
    pNew->weight = weight;
    pNew->next = NULL;

    if (!actual)
        graph->listAdj[v1] = pNew;
    else
        actual->next = pNew;

    return (pNew);
}

void prnedge (const TypeEdge *e)
{
    do
        printf (" %3d %3d\n", e->vDest, e->weight);
    while ((e = e->next));
}

void print_edge (const TypeEdge *e, int edge)
{
    printf ("\nedge %d\n", edge);
    prnedge (e);
}

void print_graph (const TypeGraph *g)
{
    for (int i = 0; i < g->numVertices; i++)
        if (g->listAdj[i])
            print_edge (g->listAdj[i], i);
}

void freelist (TypeEdge *l)
{
    while (l) {
        TypeEdge *victim = l;
        l = l->next;
        free (victim);
    }
}

void free_graphlists (TypeGraph *g)
{
    for (int i = 0; i < g->numVertices; i++)
        if (g->listAdj[i])
            freelist (g->listAdj[i]);

    free (g->listAdj);
}

int main (void) {

    TypeGraph graph;
    int result = initializeGraph (&graph, 100);

    if (result) {
        insertEdge (2, 3, 1, &graph);
        insertEdge (2, 4, 1, &graph);
    }

    print_graph (&graph);
    free_graphlists (&graph);

    return 0;
}

Пример использования / Вывод

$ ./bin/edgetype

edge 2
   3   1
   4   1

Использование памяти / проверка ошибок

В любом написанном вами коде, который динамически распределяет память, у вас есть 2 обязанностей относительно любого выделенного блока памяти: (1) всегда сохраняйте указатель на начальный адрес для блока памяти, так что, (2) он может быть освобожден , когда он больше не нужен.

Крайне важно, чтобы вы использовали программу проверки ошибок памяти, чтобы гарантировать, что вы не пытаетесь получить доступ к памяти или писать за пределами / за пределами выделенного блока, пытаться прочитать или основать условный переход на неинициализированном значении и, наконец, , чтобы подтвердить, что вы освобождаете всю выделенную память.

Для Linux valgrind - нормальный выбор. Для каждой платформы есть похожие проверки памяти. Все они просты в использовании, просто запустите вашу программу через него.

$ valgrind ./bin/edgetype
==21679== Memcheck, a memory error detector
==21679== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==21679== Using Valgrind-3.12.0 and LibVEX; rerun with -h for copyright info
==21679== Command: ./bin/edgetype
==21679==

edge 2
   3   1
   4   1
==21679==
==21679== HEAP SUMMARY:
==21679==     in use at exit: 0 bytes in 0 blocks
==21679==   total heap usage: 3 allocs, 3 frees, 832 bytes allocated
==21679==
==21679== All heap blocks were freed -- no leaks are possible
==21679==
==21679== For counts of detected and suppressed errors, rerun with: -v
==21679== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

Всегда подтверждайте, что вы освободили всю выделенную память и что ошибок памяти нет.

Посмотрите вещи и дайте мне знать, если у вас есть дополнительные вопросы.