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

# 9.2 Implementing Multi-Dimensional Arrays

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 + j`
The 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.

• ***2D Arrays, Pointers ***
• array (row) pointer a = 65474, *a = 65474
• a + 0 = 65474
• *a + COL * 0 + 0 = 65474; intptr = 65474
• &a[0][0] = 65474
• a[0][0] = 12; *(*(a + 0) + 0) = 12
• *a + COL * 0 + 1 = 65476; intptr = 65476
• &a[0][1] = 65476
• a[0][1] = 24; *(*(a + 0) + 1) = 24
• *a + COL * 0 + 2 = 65478; intptr = 65478
• &a[0][2] = 65478
• a[0][2] = 29; *(*(a + 0) + 2) = 29
• a + 1 = 65480
• *a + COL * 1 + 0 = 65480; intptr = 65480
• &a[1][0] = 65480
• a[1][0] = 23; *(*(a + 1) + 0) = 23
• *a + COL * 1 + 1 = 65482; intptr = 65482
• &a[1][1] = 65482
• a[1][1] = 57; *(*(a + 1) + 1) = 57
• *a + COL * 1 + 2 = 65484; intptr = 65484
• &a[1][2] = 65484
• a[1][2] = 19; *(*(a + 1) + 2) = 19
• The two dimensional array is:

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```

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

tep@wiliki.eng.hawaii.edu
Wed Aug 17 09:20:12 HST 1994