Two-Dimensional (and Multidimensional) Arrays
23.1: Multidimensional Arrays and Functions
23.2: Dynamically Allocating Multidimensional Arrays
C does not have true multidimensional arrays. However, because of the generality of C's type system, you can have arrays of arrays, which are almost as good. (This should not surprise you; you can have arrays of anything, so why not arrays of arrays?)
We'll use two-dimensional arrays as examples in this section, although the techniques can be extended to three or more dimensions. Here is a two-dimensional array:
int a2[5][7];
Formally, a2 is an array of 5 elements, each of which is an array of 7 ints. (We usually think of it as having 5 rows and 7 columns, although this interpretation is not mandatory.)
Just as we declared a two-dimensional array using two pairs of brackets, we access its individual elements using two pairs of brackets:
int i, j;
for(i = 0; i < 5; i++)
{
for(j = 0; j < 7; j++)
a2[i][j] = 0;
}
Make sure that you remember to put each subscript in its own, correct pair of brackets. Neither
int a2[5, 7]; /* XXX WRONG */
nor
a2[i, j] = 0; /* XXX WRONG */
nor
a2[j][i] = 0; /* XXX WRONG */
would do anything remotely like what you wanted.
23.1: Multidimensional Arrays and Functions
The most straightforward way of passing a multidimensional array to a function is to declare it in exactly the same way in the function as it was declared in the caller. If we were to call
func(a2);
then we might declare
func(int a[5][7])
{
...
}
and it's clear that the array type which the caller passes is the same as the type which the function func accepts.
If we remember what we learned about simple arrays and functions, however, two questions arise. First, in our earlier function definitions, we were able to leave out the (single) array dimension, with the understanding that since the array was really defined in the caller, we didn't have to say (or know) how big it is. The situation is the same for multidimensional arrays, although it may not seem so at first. The hypothetical function func above accepts a parameter a, where a is an array of 5 things, where each of the 5 things is itself an array. By the same argument that applies in the single-dimension case, the function does not have to know how big the array a is, overall. However, it certainly does need to know what a is an array of. It is not enough to know that a is an array of "other arrays"; the function must know that a is an array of arrays of 5 ints. The upshot is that although it does not need to know how many "rows" the array has, it does need to know the number of columns. That is, if we want to leave out any dimensions, we can only leave out the first one:
func(int a[][7])
{
...
}
The second dimension is still required. (For a three- or more dimensional array, all but the first dimension are required; again, only the first dimension may be omitted.)
The second question we might ask concerns the equivalence between pointers and arrays. We know that when we pass an array to a function, what really gets passed is a pointer to the array's first element. We know that when we declare a function that seems to accept an array as a parameter, the compiler quietly compiles the function as if that parameter were a pointer, since a pointer is what it will actually receive. What about multidimensional arrays? What kind of pointer is passed down to the function?
The answer is, a pointer to the array's first element. And, since the first element of a multidimensional array is another array, what gets passed to the function is a pointer to an array. If you want to declare the function func in a way that explicitly shows the type which it receives, the declaration would be
func(int (*a)[7])
{
...
}
The declaration int (*a)[7] says that a is a pointer to an array of 7 ints. Since declarations like this are hard to write and hard to understand, and since pointers to arrays are generally confusing, I recommend that when you write functions which accept multidimensional arrays, you declare the parameters using array notation, not pointer notation.
What if you don't know what the dimensions of the array will be? What if you want to be able to call a function with arrays of different sizes and shapes? Can you say something like
func(int x, int y, int a[x][y])
{
...
}
where the array dimensions are specified by other parameters to the function? Unfortunately, in C, you cannot. (You can do so in FORTRAN, and you can do so in the extended language implemented by gcc, and you will be able to do so in the new version of the C Standard ("C9X") to be completed in 1999, but you cannot do so in standard, portable C, today.)
Finally, we might explicitly note that if we pass a multidimensional array to a function:
int a2[5][7];
func(a2);
we can not declare that function as accepting a pointer-to-pointer:
func(int **a) /* WRONG */
{
...
}
As we said above, the function ends up receiving a pointer to an array, not a pointer to a pointer.
23.2: Dynamically Allocating Multidimensional Arrays
We've seen that it's straightforward to call malloc to allocate a block of memory which can simulate an array, but with a size which we get to pick at run-time. Can we do the same sort of thing to simulate multidimensional arrays? We can, but we'll end up using pointers to pointers.
If we don't know how many columns the array will have, we'll clearly allocate memory for each row (as many columns wide as we like) by calling malloc, and each row will therefore be represented by a pointer. How will we keep track of those pointers? There are, after all, many of them, one for each row. So we want to simulate an array of pointers, but we don't know how many rows there will be, either, so we'll have to simulate that array (of pointers) with another pointer, and this will be a pointer to a pointer.
This is best illustrated with an example:
#include
int **array;
array = malloc(nrows * sizeof(int *));
if(array == NULL)
{
fprintf(stderr, "out of memory\n");
exit or return
}
for(i = 0; i < nrows; i++)
{
array[i] = malloc(ncolumns * sizeof(int));
if(array[i] == NULL)
{
fprintf(stderr, "out of memory\n");
exit or return
}
}
array is a pointer-to-pointer-to-int: at the first level, it points to a block of pointers, one for each row. That first-level pointer is the first one we allocate; it has nrows elements, with each element big enough to hold a pointer-to-int, or int *. If we successfully allocate it, we then fill in the pointers (all nrows of them) with a pointer (also obtained from malloc) to ncolumns number of ints, the storage for that row of the array. If this isn't quite making sense, a picture should make everything clear:
Once we've done this, we can (just as for the one-dimensional case) use array-like syntax to access our simulated multidimensional array. If we write
array[i][j]
we're asking for the i'th pointer pointed to by array, and then for the j'th int pointed to by that inner pointer. (This is a pretty nice result: although some completely different machinery, involving two levels of pointer dereferencing, is going on behind the scenes, the simulated, dynamically-allocated two-dimensional "array" can still be accessed just as if it were an array of arrays, i.e. with the same pair of bracketed subscripts.)
If a program uses simulated, dynamically allocated multidimensional arrays, it becomes possible to write "heterogeneous" functions which don't have to know (at compile time) how big the "arrays" are. In other words, one function can operate on "arrays" of various sizes and shapes. The function will look something like
func2(int **array, int nrows, int ncolumns)
{
}
This function does accept a pointer-to-pointer-to-int, on the assumption that we'll only be calling it with simulated, dynamically allocated multidimensional arrays. (We must not call this function on arrays like the "true" multidimensional array a2 of the previous sections). The function also accepts the dimensions of the arrays as parameters, so that it will know how many "rows" and "columns" there are, so that it can iterate over them correctly. Here is a function which zeros out a pointer-to-pointer, two-dimensional "array":
void zeroit(int **array, int nrows, int ncolumns)
{
int i, j;
for(i = 0; i < nrows; i++)
{
for(j = 0; j < ncolumns; j++)
array[i][j] = 0;
}
}
Finally, when it comes time to free one of these dynamically allocated multidimensional "arrays," we must remember to free each of the chunks of memory that we've allocated. (Just freeing the top-level pointer, array, wouldn't cut it; if we did, all the second-level pointers would be lost but not freed, and would waste memory.) Here's what the code might look like:
for(i = 0; i < nrows; i++)
free(array[i]);
free(array);
Read sequentially: prev next top
No comments:
Post a Comment