c - 在c中的函数调用期间添加节点函数更改索引

Question

我正在尝试为一个无向加权图创建一个邻接表，这样我就可以运行 Dijkstra 和 Kruskal 的算法，但我遇到了一个有趣的问题。每当我尝试向列表索引添加第二条边时，它似乎在函数调用期间将列表索引更改为新边，删除了先前指向的边列表索引。 (我认为这个人有类似的问题，但没有答案:How to create an adjacency list of a directed graph in C?)。这是代码:

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

// Edge node
struct edge{
    int v1;                 // vertex it's coming from
    int v2;                 // vertex it's going to
    int weight;             // weight of edge
    struct edge *next;
}

const int MAX = 9;

void createAdjList(struct edge **list);
struct createEdge(int v1, int v2, int weight);
void addEdge(struct edge **list, struct edge newEdge);

int main(){
    struct edge *list = malloc(MAX * sizeof(struct edge));
    createAdjList(&list);
    ...
    return 0;
}
// creates the adjacency list
void createAdjList(struct edge **list){
    for(int i = 0; i < MAX; ++i)
        list[i] = 0;

    // first edge from vertex 0 to 1
    addEdge(list, createEdge(0, 1, 22));
    addEdge(list, createEdge(1, 0, 22));

// this is where the problem happens, when i call addEdge(list, createEdge(0, 2, 9)); 
// as soon as it enters addEdge, list[0] goes from pointing to the 0-1 edge to already
// pointing to this second edge, 0 to 2

    // second edge from vertex 0 to 2
    addEdge(list, createEdge(0, 2, 9));
    addEdge(list, createEdge(2, 0, 9));

    ...
}
// creates and returns an edge node
struct createEdge(int v1, int v2, int weight){
    struct edge newEdge;
    newEdge.v1 = v1;
    newEdge.v2 = v2;
    newEdge.weight = weight;
    newEdge.next = 0;
    return newEdge;
}
// adds the edge to the adjacency list
void addEdge(struct edge **list, struct edge newEdge){
// at this point, after the addEdge(list, createEdge(0, 2, 9)); call, list[0] is now 
// pointing to this new edge and Edge(0, 1, 22) is gone
    for(int i = 0; i < MAX; ++i){
        // if edge vertex equals index i
        if(newEdge.v1 == i){
            // if list index is empty, place it at head and return
            if(list[i] == 0){
                list[i] = &newEdge;
                return;
            // else traverse to the end, place it and return
            }else{
                struct edge* curr = list[i];
                while(curr->next != 0)
                    curr = curr->next;
                curr->next = &newEdge;
                return;
            }
        }
    }
}

谢谢

Answer 1

list[i] = &newEdge;

这里的newEdge是一个函数参数，它和局部变量一样，在addEdge函数返回时销毁。

所以在 addEdge 返回后，列表有一个指针指向 newEdge 曾经所在的位置。边缘的值很可能仍然存在，并且下次调用函数时内存可能会被重用于其他东西。在您的情况下，它恰好被重新用于保持下一个边缘。

解决方案是 malloc 一些空间来保存列表中的边缘。使用 malloc 分配的内存在您 free 之前无法重复使用。