C语言随机图生成与直径计算程序多次运行内存溢出，邻接表释放逻辑是否有误

核心内存布局错误 #

• 顶点数组的声明语句存在不匹配的类型转换：
  原代码写法：List** vertices = (List*)calloc(v, sizeof(List));
  • 二级指针List**本质是指向“存储List指针的数组”的指针，但代码里却把一级指针类型的返回值强转后赋值给它，同时按List结构体的大小给数组分配空间，而不是按指针大小分配。
  • 后续执行vertices[i] = malloc(...)时，会持续越界写入堆内存，破坏堆的元数据结构。这也是程序运行中内存不断上涨、最后堆损坏触发空指针崩溃的核心原因。
  • 正确写法应当是按指针宽度分配数组空间，匹配指针类型：

    List** vertices = (List**)calloc(v, sizeof(List*));
    

释放逻辑的空指针解引用 #

• 邻接表释放函数没有判断空链表的情况：
  原代码直接对vertices[i]->head取值后进入循环：Node* t = vertices[i]->head; while (t->next != NULL) {...}
  • 只要碰到没有任何邻接边的孤立顶点，head指针就是NULL，直接读取NULL地址上的next字段，必然触发段错误。
  • 不管是不是空链表，都应该按节点遍历直到NULL再停止，正确写法：

    for (int i = 0; i < v; i++) {
        Node* current = vertices[i]->head;
        while (current != NULL) {
            Node* temp = current;
            current = current->next;
            free(temp);
        }
    }
    

内存分配缺少结果校验 #

• 所有malloc调用都没有检查返回值是否为NULL。
  • 当系统物理内存耗尽时，malloc会返回空指针，后续直接给空指针的字段赋值（比如dest->e = j），就会触发内存访问异常。
  • 每次动态分配内存后必须做非空判断，内存不足时做可控退出，避免直接踩野指针。

随机种子初始化位置错误 #

• 原代码把srand(time(0))放在build_random_graph函数内部。
  • 每次调用建图函数都会按秒级时间戳重置随机序列，如果连续两次建图的间隔小于1秒，生成的图会完全一样，不符合实验要求。
  • 应当把srand(time(0))移到主函数开头，仅初始化一次随机数序列。

冗余的链表遍历开销 #

• 原加边逻辑是遍历整个邻接链表到尾部再插入新节点。
  • 当图的顶点数较多时，这种插入方式会把建图的时间复杂度从O(E)拉到O(E*V)，运行过程中如果碰到堆损坏的野指针，还会提前触发崩溃。可以直接把新节点插到链表头部，不需要遍历，插入操作的时间复杂度能降到O(1)。
• 另外，build_random_graph和add_edge函数声明为int返回类型，但函数内部没有写任何return语句，属于未定义行为，建议要么给函数补充正确的返回值，要么把返回类型改成void，避免出现不可预期的运行结果。

内容的提问来源于stack exchange，提问作者Mark Bromberg