Linking two structures in C

Question

I am trying to link 2 structures, one is a matrix and one is a single node. The connection should be a matrix that holds size and an array of rows with nodes connected between each other: so a 3X3 matrix should look like this:

|Node|->|Node|->|Node|-> NULL

|Node|->|Node|->|Node|-> NULL

|Node|->|Node|->|Node|-> NULL

The question is how do I connect it properly? Do I need to allocate the memory for the rows only or should I allocate the memory for all elemets and then connect them?

typedef struct cellNode {
        int cell;
        struct cellNode* next;
}   Node;

typedef struct  {
        int numRows;
        int numColumns;
        Node** rows;
}   Matrix;



Matrix* MatrixAdder(int row, int col, char mat)
{
    Matrix temp=NULL;
    int i,j;
    if(!(temp=(Matrix*)malloc(sizeof(Matrix)));
        exit(1);
    temp->numRows=row;
    temp->numColumns=col;
    if (!(temp.rows[i]=(Node*)malloc((row)*sizeof(Node))));
        exit (1);
    printf("Please insert values for matrix %c:\n",mat);
    for (i=0;i<row;i++)
    {
        if(!(temp->rows[i]=(Node*)malloc(sizeof(Node))))
            exit (1);
        printf("Enter row %d data\n",i);
        for(j=0;j<col;j++)
        {
            scanf("%d",&temp->rows->cell);
            temp->rows=temp->rows->next;
            if(!(temp->rows=(Node*)malloc(sizeof(Node))))
              exit (1);
        }
        temp->rows=NULL;
    }


}

Answer 1

If you know how many nodes you need to allocate, then you can of course allocate them all in a single call to malloc (as a normal plain "dynamic array" of nodes) and then link them all together. All you need is to keep track of the pointer returned by malloc.

But you still need to allocate the array of pointers used for rows. So no matter what you need at least two allocations.

It could be dome something like this (using normal variables and not your structures):

int numRows = 3;
int numColumns = 3;

// Allocate all the nodes
Node *allNodes = malloc(sizeof *allNodes * numRows * numColumns);

// Allocate the array of pointers needed
Node **rows = malloc(sizeof *rows * numRows);

// Initialize the rows
for (int row = 0; row < numRows; ++row)
{
    // if numColums == 3 then for
    //   row == 0 get a pointer to allNodes[0]
    //   row == 1 get a pointer to allNodes[3]
    //   row == 2 get a pointer to allNodes[6]
    rows[row] = &allNodes[row * numColumns];
}

// Now create the linked lists
for (int row = 0; i < numRows; ++row)
{
    // For numRows == 3, this will make node point to, in turn:
    //   allNodes[0]
    //   allNodes[3]
    //   allNodes[6]
    Node **node = &rows[row];

    // node will be pointing to a pointer to the *previous* node
    // So start with 1 because that's then the *next* node in the list
    for (int col = 1; col < numColumns; ++col)
    {
        // When row == 0 then:
        //   When col == 1 then link allNodes[0]->next to allNodes[1]
        //   When col == 2 then link allNodes[1]->next to allNodes[2]
        // When row == 1 then:
        //   When col == 1 then link allNodes[3]->next to allNodes[4]
        //   When col == 2 then link allNodes[4]->next to allNodes[5]
        // Etc...
        (*node)->next = &allNodes[row * numColumns + col];
        (*node) = &(*node)->next;
    }

    // Now head will be pointing to the lasts nodes next member
    (*node) = NULL;
}

_{[Note: Code not tested!]}

When finished you only have two pointers to free:

free(rows);
free(allNodes);

---

To understand exactly what's going on, if you're having trouble following along, I recommend you use a debugger together with a pen and some paper.

First of all draw a long rectangle for allNodes and divide it into numRows * numColumns number of sub-rectangles. Label them with their index (so the first becomes 0, the second 1 etc.). Then draw a second rectangle for rows and divide it into numRows sub-rectangles. Label these too with the indexes.

Now as you step along in the debugger, draw arrows between the sub-rectangles for form "pointers". For example with the first iteration of the first loop you draw an arrow from rows[0] to allNodes[0].

For the second loop, where the linked lists are created, draw another little rectangle and label it head. For each iteration of the outer linking loop you (erase) and draw an arrow from head to first rows[0], and so on.

Inside the inner linking loop (over columns) with the statement

(*head)->next = &allNodes[row * numColumns + col];

start at head and follow its arrow to rows. Then again follow the arrow to allNodes, and continue to follow any arrows until there are no more. Then draw an arrow from that element in allNodes to the next element in allNodes as indicated by row * numColumns + col. So for the first iteration you follow the arrow from head to rows[0], you follow that along to allNodes[0] where you draw an arrow to allNodes[1].

To understand why we use a pointer to a pointer for node and what (*node) = NULL is doing, then we need to draw how it looks like after the inner loop finishes. Again we use row == 0 as example.

+------+     +------------------+
| node | --> | allNodes[2].next | --> ???
+------+     +------------------+

By dereferencing node (as in (*node)) then we get to allNodes[2].next which we then can assign to be a NULL pointer.