cstructmallocdynamic-memory-allocationadjacency-list

Does malloc assign memory in the same location if you use the same variable name again on every iteration of a loop?

I am writing code to take in a weighted adjacency list in C. Each edge is stored in the form of a struct. I created an array of pointers where each pointer leads to the list for a node. Here's what I did:

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

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

// taking a weighted adjacency list 
int main() {
    int n; // number of nodes
    scanf("%d ", &n);
    struct edge **list[n];
    int p = n;
    while (p) {
        struct edge *n_list = (struct edge *)malloc(n * sizeof(struct edge));
        int num = 1;
        for (int i = 0; i < n; i++) {
            n_list[i].u = n - p;
            scanf("%d ", &n_list[i].v);
            if (n_list[i].v == -1) {
                n_list[i].w = -1;
                break;
            } else {
                num++;
                scanf("%d ", &n_list[i].w);
            }
        }
        
        n_list = (struct edge *)realloc(n_list, num * sizeof(struct edge));
        list[n - p] = &n_list;
        struct edge *ptr = *list[n - p];
        for (int j = 0; j < num - 1; j++) {
            printf("%d %d %d\n", ptr[j].u, ptr[j].v, ptr[j].w);
        }
        p--;
    }
}

The problem is that the edges get printed correctly but after the whole iteration over p (number of nodes), every element in the array of pointers (list) has the same address stored. I'm guessing that everytime I use malloc for n_list, it is allocating memory in the same location, thereby erasing the list for the previous node when I start taking input. How can I ensure this does not happen? Also any easier methods to go about this task are welcome.

Solution

  • Here's your problem

        list[n-p]=&n_list;
    //        ^ address of

    That puts the address of n_list into list[n-p]. This will be an address on the stack - the location of n_list and it won't change while n_list is in scope during the loop iteration. It will almost certainly have the same address on the stack on each iteration.

    The elements of list are of type struct edge** but you should be putting items in them of type struct edge*. You have too much indirection. Fortunately, you also dereference the pointer to do the printing out before the end of the iteration and n_list is malloc'd for the next time around.

        struct edge* ptr=*list[n-p];
    //               ^ dereference

    To fix this, declare list as follows

    struct edge* list[n];

    And remove the "address of"/dereferencing

        list[n-p] = n_list;
    struct edge* ptr = list[n-p];

    Edit

    Just realised that the suggestion above isn't completely correct because you realloc each element of list to be only as large as needed. This is problematic because you can't tell how many edges are in each list[i]. You need to either