How do I correctly set up, access, and free a multidimensional array in C?

Statically speaking, this is easy to understand:

int mtx[3][2] = {{1, 2},
                 {2, 3},
                 {3, 4}};

Nothing complicated here. 3 rows, 2 columns; data in column one: 1, 2, 3; data in column two: 2, 3, 4. We can access the elements via the same construct:

for(i = 0; i<3; i++){
    for(j = 0; j<2; j++)
        printf("%d ", mtx[i][j]);
    printf("\n");
}
//output
//1 2
//2 3
//3 4

Now let’s look at this in terms of Pointers:

The brackets are a very nice construct to help simplify things, but it doesn’t help when we need to work in a dynamic environment, so we need to think of this in terms of pointers. If we want to store a “row” of integers, we need an array:

int row[2] = {1,2};

And you know what? We can access this just like a pointer.

printf("%d, %d\n",*row,*(row+1));   //prints 1, 2
printf("%d, %d\n",row[0],row[1]);   //prints 1, 2

Now if we don’t know the number of values in a row we can make this array a dynamic length if we have a pointer to int, and we give it some memory:

int *row = malloc(X * sizeof(int));  //allow for X number of ints
*row = 1;        //row[0] = 1
*(row+1) = 2; //row[1] = 2
…
*(row+(X-1)) = Y; // row[x-1] = Some value y

So now we have a dynamic 1 dimensional array; a single row. But we want lots of rows, not just one, and we don’t know how many. That means we need another dynamic 1 dimensional array, each element of that array will be a pointer which points to a row.

//we want enough memory to point to X number of rows
//each value stored there is a pointer to an integer
int ** matrix = malloc(X * sizeof(int *));

//conceptually:
(ptr to ptr to int)     (pointer to int)
   **matrix ------------> *row1 --------> [1][2]
                          *row2 --------> [2][3]
                          *row3 --------> [3][4]

Now all that’s left to do is to write the code which will perform these dynamic allocations:

int i, j, value = 0;

//allocate memory for the pointers to rows
int ** matrix = malloc(Rows * sizeof(int*));

//each row needs a dynamic number of elements
for(i=0; i<Rows; i++){
    // so we need memory for the number of items in each row… 
    // we could call this number of columns as well
    *(matrix + i) = malloc(X * sizeof(int));

     //While we’re in here, if we have the items we can populate the matrix
    for(j=0; j<X; j++)
        *(*(matrix+i)+j) = value; // if you deference (matrix + i) you get the row
                                  // if you add the column and deference again, you
                                  // get the actual item to store (not a pointer!)
}

One of the most important things to do now is to make sure we free the memory when we’re done. Each level of malloc() should have the same number of free() calls, and the calls should be in a FILO order (reverse of the malloc calls):

for(i=0; i<Rows; i++) 
    free(*(matrix + i));
free(matrix);

//set to NULL to clean up, matrix points to allocated memory now so let’s not use it!
matrix = NULL; 

In C since C99, even dynamic multidimensional arrays can be easily allocated in one go with malloc and freed with free:

double (*A)[n] = malloc(sizeof(double[n][n]));

for (size_t i = 0; i < n; ++i)
  for (size_t j = 0; j < n; ++j)
      A[i][j] = someinvolvedfunction(i, j);

free(A);

There are at least four different ways to create or simulate a multi-dimensional array in C89.

One is "allocate each row separately", described by Mike in his answer. It is not a multidimensional array, it merely imitates one (in particular it mimics the syntax for accessing an element). It can be useful in the case where each row has different size, so you aren't representing a matrix but rather something with a "ragged edge".

One is "allocate a multidimensional array". It looks likes this:

int (*rows)[NUM_ROWS][NUM_COLS] = malloc(sizeof *rows);
...
free(rows);

Then the syntax to access element [i,j] is (*rows)[i][j]. In C89, both NUM_COLS and NUM_ROWS must be known at compile-time. This is a true 2-D array, and rows is a pointer to it.

One is, "allocate an array of rows". It looks like this:

int (*rows)[NUM_COLS] = malloc(sizeof(*rows) * NUM_ROWS);
...
free(rows);

Then the syntax to access element [i,j] is rows[i][j]. In C89, NUM_COLS must be known at compile-time. This is a true 2-D array.

One is, "allocate a 1-d array and pretend". It looks like this:

int *matrix = malloc(sizeof(int) * NUM_COLS * NUM_ROWS);
...
free(matrix);

Then the syntax to access element [i,j] is matrix[NUM_COLS * i + j]. This (of course) is not a true 2-D array. In practice it has the same layout as one.

If you want to use a typedef'd array, it is even simpler.

Say you have in your code typedef int LabeledAdjMatrix[SIZE][SIZE];

You can then use:

LabeledAdjMatrix *pMatrix = malloc(sizeof(LabeledAdjMatrix));

Then you can write:

for (i=0; i<SIZE; i++) {
    for (j=0; j<SIZE; j++) (*parr)[i][j] = k++; /* or parr[0][i][j]... */
}

Because pArr is a pointer to you matrix and * has lower priority than [];

That is why a mode common idiom is to typedef the row:

typedef int LabeledAdjRow[SIZE];

Then you can write:

LabeledAdjRow *pMatrix = malloc(sizeof(LabeledAdjRow) * SIZE);
for (i=0; i<SIZE; i++) {
    for (j=0; j<SIZE; j++) parr[i][j] = k++;
}

And you can memcpy all that directly:

LabeledAdjRow *pOther = malloc(sizeof(LabeledAdjRow) * SIZE);
memcpy(pOther, pMatrix, sizeof(LabeledAdjRow) * SIZE);