循环复用变量名时malloc是否分配同地址？C邻接表问题求助

你的代码出现所有指针地址相同的问题，核心有两个错误：

1. 数组类型定义错误：你声明的struct edge **list[n];是一个「指向指针的指针数组」，但实际上我们需要的是「指向边结构体数组的指针数组」，应该定义为struct edge *list[n];。
2. 错误存储局部变量地址：你执行list[n - p] = &n_list;时，存入的是循环内局部变量n_list的栈地址。而n_list是每次循环都会复用栈上同一个位置的变量，所以所有list元素最终都指向同一个栈地址，这个地址最后指向的是最后一次循环中malloc/realloc分配的内存块，之前的内存块地址都丢失了，还会导致内存泄漏。

下面是修正了上述问题的代码，同时调整了输入格式的小问题（去掉scanf里多余的空格，避免输入阻塞）：

#include <stdio.h>
#include <stdlib.h>

struct edge {
    int u;
    int v;
    int w;
};

int main() {
    int n; // 节点数量
    scanf("%d", &n);
    // 修正数组类型：每个元素是指向边数组的指针
    struct edge *list[n];
    int p = n;
    
    while (p) {
        int current_node = n - p;
        // 初始可以先分配小一点的空间，比如2个，避免浪费
        struct edge *n_list = malloc(2 * sizeof(struct edge));
        if (!n_list) {
            perror("malloc failed");
            exit(EXIT_FAILURE);
        }
        
        int num = 0;
        while (1) {
            scanf("%d", &n_list[num].v);
            if (n_list[num].v == -1) {
                break;
            }
            n_list[num].u = current_node;
            scanf("%d", &n_list[num].w);
            num++;
            // 空间不足时扩容
            struct edge *temp = realloc(n_list, (num + 1) * sizeof(struct edge));
            if (!temp) {
                perror("realloc failed");
                free(n_list);
                exit(EXIT_FAILURE);
            }
            n_list = temp;
        }
        
        // 重新分配到实际需要的大小
        struct edge *final_list = realloc(n_list, num * sizeof(struct edge));
        if (final_list) {
            n_list = final_list;
        }
        // 将边数组的指针存入list
        list[current_node] = n_list;
        
        // 打印验证
        printf("Node %d's edges:\n", current_node);
        for (int j = 0; j < num; j++) {
            printf("%d %d %d\n", n_list[j].u, n_list[j].v, n_list[j].w);
        }
        
        p--;
    }

    // 记得最后释放所有分配的内存，避免泄漏
    for (int i = 0; i < n; i++) {
        free(list[i]);
    }
    return 0;
}

上面的数组式邻接表需要频繁扩容，对于边数不确定的场景，用链表实现邻接表更灵活，也更符合邻接表的常规设计：

#include <stdio.h>
#include <stdlib.h>

// 链表节点：代表一条边
struct EdgeNode {
    int v;          // 邻接节点
    int weight;     // 边权
    struct EdgeNode *next;
};

// 邻接表的表头：每个节点对应一个链表表头
struct AdjListNode {
    int u;          // 当前节点
    struct EdgeNode *head;
};

// 邻接表结构体
struct AdjList {
    int num_nodes;
    struct AdjListNode *array;
};

// 创建新的边节点
struct EdgeNode* createEdge(int v, int weight) {
    struct EdgeNode *new_edge = malloc(sizeof(struct EdgeNode));
    new_edge->v = v;
    new_edge->weight = weight;
    new_edge->next = NULL;
    return new_edge;
}

// 创建邻接表
struct AdjList* createAdjList(int n) {
    struct AdjList *adj_list = malloc(sizeof(struct AdjList));
    adj_list->num_nodes = n;
    adj_list->array = malloc(n * sizeof(struct AdjListNode));
    
    for (int i = 0; i < n; i++) {
        adj_list->array[i].u = i;
        adj_list->array[i].head = NULL;
    }
    return adj_list;
}

// 添加边到邻接表
void addEdge(struct AdjList *adj_list, int u, int v, int weight) {
    struct EdgeNode *new_edge = createEdge(v, weight);
    // 头插法，效率更高
    new_edge->next = adj_list->array[u].head;
    adj_list->array[u].head = new_edge;
}

// 打印邻接表
void printAdjList(struct AdjList *adj_list) {
    for (int i = 0; i < adj_list->num_nodes; i++) {
        struct EdgeNode *temp = adj_list->array[i].head;
        printf("Node %d's edges: ", i);
        while (temp) {
            printf("(%d, %d) ", temp->v, temp->weight);
            temp = temp->next;
        }
        printf("\n");
    }
}

// 释放邻接表内存
void freeAdjList(struct AdjList *adj_list) {
    for (int i = 0; i < adj_list->num_nodes; i++) {
        struct EdgeNode *temp = adj_list->array[i].head;
        while (temp) {
            struct EdgeNode *next = temp->next;
            free(temp);
            temp = next;
        }
    }
    free(adj_list->array);
    free(adj_list);
}

int main() {
    int n;
    scanf("%d", &n);
    struct AdjList *adj_list = createAdjList(n);
    
    for (int u = 0; u < n; u++) {
        while (1) {
            int v, w;
            scanf("%d", &v);
            if (v == -1) break;
            scanf("%d", &w);
            addEdge(adj_list, u, v, w);
        }
    }
    
    printAdjList(adj_list);
    freeAdjList(adj_list);
    return 0;
}

链表形式的优势在于不需要提前预估边数，也不需要频繁的内存扩容操作，添加和遍历边的逻辑更简洁，是邻接表的标准实现方式。

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