首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
社区首页 >问答首页 >当我将图中的节点数从4增加到大于5的任何值时,malloc得到内存损坏

当我将图中的节点数从4增加到大于5的任何值时,malloc得到内存损坏
EN

Stack Overflow用户
提问于 2019-08-22 16:36:21
回答 1查看 147关注 0票数 1

我已经写了一个简单的代码来打印给定的边的图形,我使用结构来存储图形中的数据,当节点的数量小于5但任何大于5的节点都会带来malloc错误时,它工作得很好,我不知道为什么会发生这种情况,有人能指出我做错了什么吗?

代码语言:javascript
代码运行次数:0
运行
复制
#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的节点时遇到的错误:

代码语言:javascript
代码运行次数:0
运行
复制
struct Node *newNode = (struct Node *)malloc(sizeof(struct Node));

如下所示:

代码语言:javascript
代码运行次数:0
运行
复制
malloc(): memory corruption aborted (core dumped)
EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2019-08-22 17:09:52

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

代码语言:javascript
代码运行次数:0
运行
复制
// Data structure to store graph
struct Graph {
    // An array of pointers to Node to represent adjacency list
    struct Node* head[N];
};

稍后,你会因为初始化越界而接触到不属于你的内存:

代码语言:javascript
代码运行次数:0
运行
复制
   // initialize head pointer for all vertices
for (i = 0; i < n; i++)
    graph->head[i] = NULL;

使用valgrind:

代码语言:javascript
代码运行次数:0
运行
复制
=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)
票数 5
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/57605262

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档