Previous: 9.1 Two Dimensional Arrays
Up: 9.1 Two Dimensional Arrays
Next: 9.3 Arrays of Strings
Previous Page: 9.1 Two Dimensional Arrays
Next Page: 9.3 Arrays of Strings
Previous: 9.1 Two Dimensional Arrays
Up: 9.1 Two Dimensional Arrays
Next: 9.3 Arrays of Strings
Previous Page: 9.1 Two Dimensional Arrays
Next Page: 9.3 Arrays of Strings
In the last section we saw how we can use two dimensional arrays - how to declare them, pass them to functions, and access the date elements they contain using array indexing notation. As with one dimensional arrays, we can access elements in a 2D array using pointers as well. In order to understand how this is done, in this section we look at how multi dimensional arrays are implemented in C.
As we saw in Chapter ,
a one dimensional array is stored in a set of contiguous memory cells
and the name of the array is associated with a pointer cell
to this block of memory.
In C, a two
dimensional array is considered to be a one dimensional array of
rows, which are, themselves, one dimensional arrays.
Therefore, a two
dimensional array of integers, AA[][],
is stored as a contiguous sequence of elements, each of which is a
one dimensional array.
The rows are stored in sequence, starting with row 0 and continuing
until the last row is stored, i.e.
AA[0] is stored first, then AA[1], then AA[2], and so on
to AA[MAX-1].
Each of these ``elements'' is an array, so is stored as a contiguous
block of integer cells as seen in Figure 9.10.
This storage organization for two
dimensional arrays is called row major order.
The same is true for higher dimensional arrays.
An
dimensional array is considered to be a one dimensional array
whose elements are, themselves, arrays of dimension
.
As such, in C, an array of any dimension is stored in row major order
in memory.
With this storage organization in mind, let us look at what implications this has to referencing the array with pointers. Recall that an array name (without an index) represents a pointer to the first object of the array. So the name, AA, is a pointer to the element AA[0]. iBut, AA[0] is a one dimensional array; so, AA[0] points to the first object in row 0, i.e. AA[0] points to AA[0][0]. Similarly, for any k points to the beginning of the kth row, i.e. AA[k] is the address of AA[k][0]. Since AA[k] points to AA[k][0], *AA[k] accesses AA[k][0], an object of type integer. If we add 1 to the pointer AA[k], the resulting pointer will point to the next integer type element, i.e. the value of AA[k][1]. In general, AA[k] + j points to AA[k][j], and *(AA[k] + j) accesses the value of AA[k][j]. This is shown in Tables 9.1 and 9.2. Each AA[k] points to an integer type object. When an integer is added to the pointer AA[k], the resulting pointer points to the next object of the integer type.
The name, AA, is the name of the entire array, whose elements are themselves arrays of integers. Therefore, AA points to the first object in this array of arrays, i.e. AA points to the array AA[0]. The addresses represented by AA and AA[0] are the same; however, they point to objects of different types. AA[0] points to AA[0][0], so it is an integer pointer. AA points to AA[0], so it is a pointer to an integer pointer. If we add 1 to AA, the resulting pointer, AA + 1, points to the array AA[1], and AA + k points to the array AA[k]. When we add to a pointer to some type, we point to the next object of that type. Therefore, adding to AA and AA[0] result in pointers to different objects. Adding 1 to AA results in a pointer that points to the next array or row, i.e. AA[1]; whereas adding 1 to AA[0] results in a pointer that points to AA[0][1]. Dereferencing such a pointer, *(AA + k), accesses AA[k], which as we saw, was &AA[k][0]. It follows that *(*(AA + k) + j) accesses the integer, AA[k][j]. This pointer equivalence for two dimensional arrays is shown in Table 9.3.
The C compiler converts array indexing to indirect access by dereferenced pointers as shown in the table; thus, all array access is indirect access When we pass a 2D array to a function, we pass its name ( AA). The function can access elements of the array argument either by indexing or by pointers. We generally think of a two dimensional array as a table consisting of rows and columns as seen in Figure 9.11. As such, it is usually easiest to access the elements by indexing; however, the pointer references are equally valid as seen in the figure.
The relationships between different pointers for a two dimensional
array is further illustrated with the program shown in Figure 9.12.
The two-dimensional array, a,
is not an integer pointer, it points to the array of integers, a[0].
However, *a is an integer pointer;
it points to an integer object, a[0][0]. To
emphasize this point, we initialize an integer pointer, intptr
to *a, i.e. a[0].
The initial value of intptr is the address of a[0][0].
We next print the
values of a and *a,
which are the same address even though they point to
different types of objects.
In the for loop, we print the value of a + i,
which is the same as that of a[i]
even though they point to different types of objects. In the inner for loop, we
print the address of the row and the
column element
of the row major array using pointers:
*a + COL * i + jThe same value is printed using the address of operator, . Finally, the value of a[i][j] is printed using array indices as well as by dereferencing pointers, i.e. *(*(a + i) + j).
The value of intptr, initialized to *a, is incremented after each element value is printed; making it point to the next element. The value of intptr is printed as it is incremented. Observe that it prints the address of each element of the array in one row, and proceeds to the next row in sequence. This shows that arrays are stored in row major form.
Finally, the function, print2aray() is used to print the two dimensional array in rows and columns. The output of a sample run is shown below.
As we mentioned in the last section, when a two dimensional array is passed to a function, the parameter declaration in the function must include the number of columns. We can now see why this is so. The number of columns in a row specifies the size of each row in the array of rows. Since the passed parameter is a pointer to a row object, it can be incremented and dereferenced, as shown in Table 9.3, to access the elements of the two dimensional array. The compiler must know the size of the row in order to be able to increment the pointer to the next row.
As we stated earlier,
multi-dimensional arrays are arrays of arrays just like two dimensional arrays.
An dimensional array is an array of
dimensional arrays. The same
general approach applies as for two dimensional arrays. When passing an
dimensional array, the declaration of the formal parameter must specify all
index ranges except for the first index.
As was seen in the program in Figure 9.12, multi-dimensional arrays may also be initialized in declarations by specifying constant initializers within braces. Each initializer must be appropriate for the corresponding lower dimensional array. For example, a two dimensional array may be initialized as follows:
int x[2][3] = { {10, 23}, {0, 12, 17} };
The array has two elements, each of which is an array of three elements. The first initializer initializes the first row of x. Since only the first two elements of the row are specified, the third element is zero. The second element initializes the second row. Thus, x is initialized to the array:
10 23 0
0 12 17