c - 无法在我的图的 C 实现中为新节点分配内存

Question

我正在用 C 实现一个图，这是我的程序:

#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
typedef  struct EdgeNode{
     int adjvex;
     struct EdgeNode *nextarc;
 }ENode, *PENode;
typedef struct VertexNode{
     char *data; 
     ENode *firstarc; 
 }VNode;

typedef  struct MyGraph{
     VNode vertices[INT_MAX];

}Graph;

static int get_pos(Graph g, char* name, int num_ver){
    int i;
    for (i = 0; i < num_ver; i++){
        if(strcmp(g.vertices[i].data,name) == 0)
            return i;
    }
    return -1;
}


void add_node(ENode *mylist, ENode *newEdge){
    ENode *p = mylist;
    while(p->nextarc)
        p = p->nextarc;
    p->nextarc = newEdge;
}

void DFS(Graph G, int first_node, int* visited){
    ENode *new_edge;
    visited[first_node] = 1;
    new_edge = G.vertices[first_node].firstarc;
    while (new_edge != NULL){
        if (!visited[new_edge->adjvex])
            DFS(G, new_edge->adjvex, visited);
        new_edge = new_edge -> nextarc;
    }
}

static int dfs_traverse(Graph G, int first_node, int second_node, int number_of_nodes){
    int visited[INT_MAX];
    int i;
    for (i = 0; i < number_of_nodes; i++){
        visited[i] = 0;
    }
    DFS(G, first_node, visited);
    if (visited[second_node] == 1){
        return 1;
    }else{
        return 0;
    }

}


void print_graph(Graph G, int num_vertex)
{
    int i;
    ENode *node;

    printf("List Graph:\n");
    for (i = 0; i < num_vertex; i++)
    {
        printf("%d(%s): ", i, G.vertices[i].data);
        node = G.vertices[i].firstarc;
        while (node != NULL)
        {
            printf("%d(%s) ", node->adjvex, G.vertices[node->adjvex].data);
            node = node->nextarc;
        }
        printf("\n");
    }
}




int main (){                                                                                        
    size_t sz1;
    char *line = NULL;
    //char line[1024];
    char make_nodes[] = "@n";
    char make_edges[] = "@e";
    char check_edges[] = "@q";
    static int  i = 0;
    int  index_1, index_2;
    int  dfs_1, dfs_2;
    int  pathExists;
    ENode* Edge1;

    Graph* pGraph = malloc(sizeof(Graph));
    if (pGraph == NULL){
        fprintf(stderr, "Unable to allocate memory for new node\n");
        exit(1);
    }


    while(getline(&line, &sz1, stdin) > 0){
    char cmd[3],n1[65],n2[65],dummy[2];
    int num_args;
    num_args = sscanf(line,"%3s%64s%64s%2s",cmd,n1,n2,dummy);
        if (strcmp(cmd,make_nodes) == 0){
      if(num_args != 2){
        printf("error\n");
      }else{
        pGraph->vertices[i].data = strdup(n1);
        pGraph->vertices[i].firstarc = NULL;
        i++;
        printf("the node is %s\n",pGraph->vertices[i].data);
      }
    }if (strcmp(cmd,make_edges) == 0){
      if (num_args != 3){
        printf("error\n");
      }else{
        index_1 = get_pos(*pGraph, n1, i);
        index_2 = get_pos(*pGraph, n2, i);
        Edge1 = (ENode*)malloc(sizeof(ENode));
        Edge1 -> adjvex = index_2;
        if (pGraph -> vertices[index_1].firstarc == NULL)
          pGraph -> vertices[index_1].firstarc = Edge1;
        else{
          add_node(pGraph->vertices[index_1].firstarc, Edge1);
        }


      }
    }



  }
    print_graph(*pGraph,i);

     return 0;
}

虽然程序应该按如下方式工作:

@n [somenode]  for adding a new node
@e [somenode] [somenode] for adding a new edge
@q [somenode] [somenode] for testing the connection between two nodes

应该是这样的:

@n first
@n second
@e first second
@q first second
1 //which means first and second is connected

但是，鉴于所有这些信息，我的程序崩溃了，当我使用 valgrind 时，它只返回消息:

==7758== Memcheck, a memory error detector
==7758== Copyright (C) 2002-2013, and GNU GPL'd, by Julian Seward et al.
==7758== Using Valgrind-3.10.1 and LibVEX; rerun with -h for copyright info
==7758== Command: ./reach
==7758== 
Unable to allocate memory for new node
==7758== 
==7758== HEAP SUMMARY:
==7758==     in use at exit: 0 bytes in 0 blocks
==7758==   total heap usage: 0 allocs, 0 frees, 0 bytes allocated
==7758== 
==7758== All heap blocks were freed -- no leaks are possible
==7758== 
==7758== For counts of detected and suppressed errors, rerun with: -v
==7758== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

如果我只是通过读取标准输入进行测试，它会像这样工作:

@n first
the node is (null)
@n second
the node is (null)
@e first second 
Segmentation fault (core dumped)
@q first second
Segmentation fault (core dumped)

我不知道是否有足够的信息，但有人知道可能发生了什么吗？

Answer 1

您正在尝试为 Graph 分配内存:

typedef  struct MyGraph{
     VNode vertices[INT_MAX];
} Graph;

INT_MAX 可能是一个很大的数字，比如 2,147,483,647，每个 VNode 包含两个指针。如果您希望分配该结构，那是因为您系统上的指针是八个字节，所以您正在尝试分配 32 GB。

如果您没有 32 GB，这可能很好地解释了为什么您不能分配内存。有些系统会让你分配比你拥有的更多的内存——只要你实际上并不打算使用它——但我认为 valgrind 的 malloc 不是那么慷慨。

也许您应该尝试分配一个更易于管理的大小的图形。

此外，这种堆栈分配巨大 vector 的尝试:

int visited[INT_MAX];

肯定会溢出您的堆栈，这可能不会超过 8 兆字节，远小于您尝试分配的 8 GB。

用自动对象溢出堆栈是未定义的行为；可能会出现段错误，因为运行时不会验证您没有溢出堆栈。