当我将图中的节点数从4增加到大于5时，malloc受到内存破坏

Question

我编写了一个简单的代码来打印给定边的图形，并且我正在使用结构将数据存储在图形中，当节点数少于5个但大于5个会带来malloc错误时，它可以很好地工作。不知道为什么会这样，有人可以指出我做错了什么。

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

// Define maximum number of vertices in the graph

#define N 5
//#define N 4 //use this when the nodes are less than 5 

// Data structure to store graph
struct Graph {
    // An array of pointers to Node to represent adjacency list
    struct Node *head[N];
};

// A data structure to store adjacency list nodes of the graph
struct Node {
    int dest;
    struct Node *next;
};

// data structure to store graph edges
struct Edge {
    int src, dest;
};

// Function to create an adjacency list from specified edges
struct Graph *createGraph(struct Edge edges[], int n) {
    unsigned i;

    // allocate memory for graph data structure
    struct Graph *graph = (struct Graph *)malloc(sizeof(struct Graph));

    // initialize head pointer for all vertices
    for (i = 0; i < n; i++)
        graph->head[i] = NULL;

    // add edges to the directed graph one by one
    for (i = 0; i < n; i++) {
        // get source and destination vertex
        int src = edges[i].src;
        int dest = edges[i].dest;

        // allocate new node of Adjacency List from src to dest
        // error occurs over here and does not move forward when the number of nodes are greater than 5
        struct Node *newNode = (struct Node *)malloc(sizeof(struct Node));
        newNode->dest = src;

        // point new node to current head
        newNode->next = graph->head[dest];

        // point head pointer to new node
        graph->head[dest] = newNode;
    }
    return graph;
}

// Function to print adjacency list representation of graph
void printGraph(struct Graph *graph) {
    int i;
    for (i = 0; i < N; i++) {
        // print current vertex and all ts neighbors
        printf("for node %d\n", i);
        struct Node *ptr = graph->head[i];
        while (ptr != NULL) {
            printf("(%d -> %d)\t", i, ptr->dest);
            ptr = ptr->next;
        }
        printf("\n");
    }
}

// Directed Graph Implementation in C
int main(void) {
    // input array containing edges of the graph (as per above diagram)
    // (x, y) pair in the array represents an edge from x to y
    // when the nodes are 5 or more use this 
    struct Edge edges[] = {
        { 3, 0 }, { 3, 1 }, { 3, 2 }, { 1, 0 },
        { 1, 2 }, { 4, 1 }, { 4, 3 }
    };

    //when the nodes are 4 use this below
    // struct Edge edges[] = {
    //     { 3, 0 }, { 3, 1 }, { 3, 2 }, { 1, 0 },
    //     { 1, 2 }
    // };

    // calculate number of edges
    int n = sizeof(edges) / sizeof(edges[0]);
    printf("%d\n",n );
    // construct graph from given edges
    struct Graph *graph = createGraph(edges, n);

    // print adjacency list representation of graph
    printGraph(graph);

    return 0;
} 

在以下位置使用大于4的节点时出现的错误：

struct Node *newNode = (struct Node *)malloc(sizeof(struct Node));

如下：

malloc(): memory corruption aborted (core dumped)

Answer 1

在代码中，您在Graph中分配了一个由4个Node指针组成的数组，称为head。

// Data structure to store graph
struct Graph {
    // An array of pointers to Node to represent adjacency list
    struct Node* head[N];
};

稍后，您将通过初始化内存来触摸不是您的内存：

   // initialize head pointer for all vertices
for (i = 0; i < n; i++)
    graph->head[i] = NULL;

使用valgrind：

=16498== Invalid write of size 8
==16498==    at 0x400653: createGraph (a.c:37)
==16498==    by 0x400815: main (a.c:103)
==16498==  Address 0x52044a0 is 0 bytes after a block of size 32 alloc'd
==16498==    at 0x4C2DB8F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==16498==    by 0x40063E: createGraph (a.c:33)
==16498==    by 0x400815: main (a.c:103)