C语言图邻接表实现问题：无法创建图且节点重复

嘿，我一眼就看到你代码里的核心问题了——在添加边的环节，链表节点的挂载逻辑搞反了，这才导致节点重复或者无法正确添加新边。咱们来一步步解决：

核心错误分析 #

在你的内层循环（添加每条边的部分），最后一行代码是：

new_node = G.edges[i].head;

这行代码完全不符合链表头插法的逻辑！正确的头插法应该是：

1. 让新节点的next指向当前链表的头节点
2. 将链表的头节点更新为新创建的节点

而你现在的操作是把new_node重新赋值成当前的头节点，这就意味着刚malloc出来的新节点直接丢失了（没有被挂载到邻接表的链表上），每次循环都在重复操作同一个旧的头节点，自然会出现节点重复的现象。

修正后的代码片段 #

把内层循环的最后两行修改成这样：

new_node->next = G.edges[i].head;
G.edges[i].head = new_node; // 把新节点设为链表的新头部

完整的修正后主函数关键部分如下：

int numEdges;
int edgeToVertex;
int weight;
EdgeNodePtr new_node;
Graph G;
EdgeNodePtr current;
int *inDeg;

scanf("%d", &G.V);
// 建议添加malloc失败检查
G.edges = malloc(G.V * sizeof(EdgeList));
if (G.edges == NULL) {
    perror("malloc failed for edge list");
    return 1;
}

// 初始化入度数组（如果需要使用的话）
inDeg = calloc(G.V, sizeof(int));
if (inDeg == NULL) {
    perror("calloc failed for in-degree array");
    free(G.edges);
    return 1;
}

for (int i = 0; i < G.V; i++) {
    scanf("%d", &numEdges);
    G.edges[i].head = NULL;
    for (int j = 0; j < numEdges; j++) {
        new_node = malloc(sizeof(*new_node));
        // 检查malloc是否成功
        if (new_node == NULL) {
            perror("malloc failed for edge node");
            // 这里可以添加内存清理逻辑，避免泄漏
            return 1;
        }
        // 注意输入格式要严格匹配，建议添加读取成功检查
        if (scanf("%d,%d", &edgeToVertex, &weight) != 2) {
            fprintf(stderr, "Invalid input format\n");
            free(new_node);
            // 清理已分配内存
            return 1;
        }
        new_node->edge.to_vertex = edgeToVertex;
        new_node->edge.weight = weight;
        // 正确的头插法逻辑
        new_node->next = G.edges[i].head;
        G.edges[i].head = new_node;
        
        // 如果需要统计入度，更新入度数组
        if (edgeToVertex >= 0 && edgeToVertex < G.V) {
            inDeg[edgeToVertex]++;
        }
    }
}

额外的注意事项 #

• 内存安全：每次malloc/calloc后都要检查是否分配成功，避免空指针访问；程序结束前记得释放所有分配的内存（包括邻接表的每个节点和数组本身）。
• 输入健壮性：scanf("%d,%d", ...)要求输入必须是数字,数字的格式，如果输入中没有逗号或者格式不对，会导致读取失败，建议添加返回值检查（比如判断返回值是否为2）。
• 入度数组：你的代码里定义了inDeg但没有初始化和使用，如果需要计算入度，记得在添加边时更新对应的入度值，同时要确保edgeToVertex是合法的顶点索引（在0到G.V-1之间）。

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