C语言添加节点函数调用时索引异常：无向加权图邻接表问题

嘿，我太懂你这种困扰了——刚用C写邻接表的时候，这种“加第二条边就覆盖第一条”的问题简直是新手标配！本质上大多是没搞懂邻接表的链式存储逻辑，或者指针用错了导致旧边被直接覆盖。我给你拆解下常见原因和解决办法：

最常见的坑：直接覆盖头指针，没做链式链接 #

很多人一开始会写这种错误代码：

typedef struct Edge {
    int dest;
    int weight;
    struct Edge* next;
} Edge;

#define MAX_NODES 100
Edge* adj[MAX_NODES]; // 邻接表头数组

// 错误的添加边方式
void addEdge(int u, int v, int weight) {
    Edge* newEdge = (Edge*)malloc(sizeof(Edge));
    newEdge->dest = v;
    newEdge->weight = weight;
    adj[u] = newEdge; // 这里直接把新节点赋值给表头，旧边直接丢了！
    
    // 无向图的反向边也犯了同样的错
    Edge* revEdge = (Edge*)malloc(sizeof(Edge));
    revEdge->dest = u;
    revEdge->weight = weight;
    adj[v] = revEdge;
}

为啥会覆盖？因为你把新节点直接赋值给了adj[u]，原来的头指针（指向第一条边）就被覆盖了，那条边的内存还在，但你再也找不到它了。

正确的链式添加方式 #

要把新节点挂在链表的头部，让它的next指向原来的表头，再更新表头为新节点：

// 正确的addEdge实现
void addEdge(int u, int v, int weight) {
    // 添加u→v的边
    Edge* newEdge = (Edge*)malloc(sizeof(Edge));
    newEdge->dest = v;
    newEdge->weight = weight;
    newEdge->next = adj[u]; // 新节点链接到原表头
    adj[u] = newEdge;       // 更新表头为新节点
    
    // 添加v→u的反向边（无向图必须加）
    Edge* revEdge = (Edge*)malloc(sizeof(Edge));
    revEdge->dest = u;
    revEdge->weight = weight;
    revEdge->next = adj[v];
    adj[v] = revEdge;
}

第二个坑：忘记初始化邻接表表头 #

如果你的adj数组没有初始化为NULL，第一次添加边时，newEdge->next会指向随机的垃圾内存，后续操作可能出现奇怪的覆盖、崩溃或者乱码。一定要先初始化：

void initAdjList() {
    for (int i = 0; i < MAX_NODES; i++) {
        adj[i] = NULL; // 所有表头初始为空链表
    }
}

第三个坑：用栈内存创建边节点 #

如果你图省事，直接在栈上定义边节点（比如Edge newEdge;），而不用malloc动态分配内存，那么addEdge函数执行完后，栈上的节点内存会被系统回收，后续访问邻接表时会出现野指针，看起来像是边被覆盖了。一定要用动态内存分配创建边节点。

适配Dijkstra和Kruskal的小提示 #

• 对于Dijkstra算法，这个邻接表结构完全够用，遍历每个节点的邻接边即可；
• 对于Kruskal算法，你还需要单独维护一个所有边的列表（因为Kruskal要对边排序），可以在添加边的时候同步把边存入一个数组（注意无向图要避免重复存储同一条边，比如只存u < v的情况）。

最后可以写个打印函数验证邻接表是否正确：

void printAdjList() {
    for (int i = 0; i < MAX_NODES; i++) {
        printf("节点 %d 的邻接边：", i);
        Edge* temp = adj[i];
        while (temp != NULL) {
            printf("(目标节点：%d，权重：%d) ", temp->dest, temp->weight);
            temp = temp->next;
        }
        printf("\n");
    }
}

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