Two-dimensional Arrays

Introduction

Many problems have an intrinsic two-dimensional structure. For example, images are naturally thought of as consisting of pixels arranged into rows and columns. While it is certainly possible for us to store an image in a linear array, we would lose the correspondence between spatial location and array index.

Beyond the simple linear array, languages like C offer additional way to group data using higher-dimensional structures. A two-dimensional array is one such commonly used structure, as introduced in your textbook readings:

The previous lab introduced a struct to combine several different pieces of data within one logical unit.

In contrast, one-dimensional arrays provide a mechanism to access a sequence of data using a single index, such as item[0], item[1], item[2], ....

Basics of two-dimensional arrays

Expanding upon the concept of an array, C supports the organization of data in a table by specifying a row and a column:

2 dimensional array

As with one-dimensional arrays, two-dimensional arrays can contain data of any type, although each entry in a table must have the same type. Also, the size of a two-dimensional array must be declared when it is first defined:

int table [5][10];

When using a two-dimensional array as a function parameter, the function header and prototype declaration must know the number of columns in the table (so the computer knows when one row stops and the next starts). As with 1-dimensional arrays, a procedure header does not need to specify the number of rows in the table. Thus, if the above table were passed to a printArray procedure, the header of printArray might be given as follows:

void printArray (int arr[][10])

The examples and exercises in the lab illustrate working with 2D dimenstional arrays that conceptually store data of the same type within a table.


Example: Daily Precipitation for Six Cities

Consider a table that presents the amount of precipitation for six cities over an eight day period: December 18-25, 2014.

Chicago Denver Des Moines Phoenix San Jose Seattle
Date Illinois Colorado Iowa Arizona California Washington
 
Dec. 18 0.00 0.00 0.00 0.00 0.00 0.51
Dec. 19 0.00 0.00 0.00 0.00 0.19 0.12
Dec. 20 0.00 0.00 0.00 0.00 0.06 0.77
Dec. 21 0.00 0.00 0.00 0.00 0.00 0.00
Dec. 22 0.28 0.14 0.34 0.00 0.00 0.00
Dec. 23 0.13 0.00 0.34 0.00 0.02 0.81
Dec. 24 0.12 0.00 0.09 0.00 0.04 0.21
Dec. 25 0.00 0.21 0.00 0.00 0.00 0.00
 
Totals 0.53 0.35 0.77 0.00 0.31 2.42

This type of table arises frequently:

Program city-precipitation.c stores the precipitation data for this table in a two-dimensional array and prints the table.

Altogether, two dimensional arrays are a wonderful way to store lots of data which would otherwise require many arrays!

2D Array Storage

array storage

Once we have some basic experience with two-dimensional arrays, we need to examine more closely how these arrays are stored in main memory. Suppose an array is declared:

table [row][col];

where row and col have been previously specified as integer values. A schematic of the array is shown to the right.

In main memory, the two-dimensional array table is stored row-by-row. First, row 0 is stored, then row 1, then row 2, etc. Such a storage configuration is called row-major order. Note that no extra memory is used to separate one row from another; the elements of one row immediately follow the elements of the previous row.

The location of any array element can therefore be computed very quickly. To locate element table[i][j], one proceeds as follows:

Altogether, the element table[i][j] may be found at address table + i*col + j. That is, the element itself may be referenced with the computation

element = *(table + i*col + j);

One consequence of this computation is that the compiler must know how many columns are in a two-dimensional array into order to determine where an array element might be. In particular, the signature of a procedure involving a two-dimensional array must include the number of columns. As with one-dimensional arrays, the number of rows need not be specified, as the computation of an element is valid for any i and j, as long as the number col is known.

In practice, column information may be included in a procedure header in either of two ways: