Node:Multidimensional arrays, Next:Arrays and nested loops, Previous:Arrays and for loops, Up:Arrays
Suppose that you are writing a chess-playing program like GNU Chess. A chessboard is an 8-by-8 grid. What data structure would you use to represent it?
You could use an array that has a chessboard-like structure, that is, a two-dimensional array, to store the positions of the chess pieces. Two-dimensional arrays use two indices to pinpoint an individual element of the array. This is very similar to what is called "algebraic notation", already commonly used in chess circles to record games and chess problems.
In principle, there is no limit to the number of subscripts (or dimensions) an array can have. Arrays with more than one dimension are called multidimensional arrays. Although humans cannot easily visualize objects with more than three dimensions, representing multidimensional arrays presents no problem to computers.
In practice, however, the amount of memory in a computer tends to place limits on how large an array can be. For example, a simple four-dimensional array of double-precision numbers, merely twenty elements wide in each dimension, already takes up 20^4 * 8, or 1,280,000 bytes of memory -- about a megabyte. (Each element of the array takes up 8 bytes, because doubles are 64 bits wide. See Floating point variables, for more information.)
You can declare an array of two dimensions as follows:
variable_type array_name[size1][size2]
In the above example, variable_type is the name of some type of
variable, such as int. Also, size1 and size2 are the
sizes of the array's first and second dimensions, respectively. Here is
an example of defining an 8-by-8 array of integers, similar to a
chessboard. Remember, because C arrays are zero-based, the indices on
each side of the chessboard array run 0 through 7, rather than 1 through
8. The effect is the same, however: a two-dimensional array of 64
elements.
int chessboard[8][8];
To pinpoint an element in this grid, simply supply the indices in both dimensions.
Every element in this grid needs two indices to pin-point it. Normally,
C programmers think of element 0,0 of a two-dimensional array as being
the upper-left corner. The computer, however, knows nothing of left and
right, and for our purposes (attempting to conform to international
chess notation), it makes more sense to mentally "flop" the array
vertically so that element 0,0 is the lower-left corner of the board,
and 7,7 the upper-right. Thus, the first index gives the row number for
the grid and the second index gives the column number. For example, 1,0
is the square directly above the lower-left corner. Suppose that a
value of 1 for an array location means a the chess king is on the space
in question. To indicate the White king's usual position (that is,
square a5 in algebraic chess notation or 0,4 in our zero-based integer
notation), you would write this:
chessboard[0][4] = 1;
Since computer memory is essentially one-dimensional, with memory
locations running straight from 0 up through the highest location in
memory, a multidimensional array cannot be stored in memory as a grid.
Instead, the array is dissected and stored in rows. Consider the
following two-dimensional array.
-----------
row 0 | 1 | 2 | 3 |
-----------
row 1 | 4 | 5 | 6 |
-----------
row 2 | 7 | 8 | 9 |
-----------
Note that the numbers inside the boxes are not the actual indices of the array, which is two-dimensional and has two indices for each element, but only arbitrary placeholders to enable you to see which elements correspond in the following example. The row numbers do correspond to the first index of the array, so they are numbered from 0 to 2 rather than 1 to 3.
To the computer, the array above actually "looks" like this:
------------------------------------ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | ------------------------------------ | row 0 | row 1 | row 2 |
Another way of saying that arrays are stored by row is that the second
index varies fastest. A two-dimensional array is always thought of
as follows:
array_name[row][column]
Every row stored will contain elements of many columns. The column index runs from 0 to size - 1 inside every row in the one-dimensional representation (where size is the number of columns in the array), so the column index is changing faster than the row index, as the one-dimensional representation of the array inside the computer is traversed.
You can represent a three-dimensional array, such as a cube, in a similar way:
variable_type array_name[size1][size2][size3]
Arrays do not have to be shaped like squares and cubes; you can give
each dimension of the array a different size, as follows:
int non_cube[2][6][8];
Three-dimensional arrays (and higher) are stored in the same basic way as two-dimensional ones. They are kept in computer memory as a linear sequence of variables, and the last index is always the one that varies fastest (then the next-to-last, and so on).