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:
- King, Section 8.2, pp. 169-174
The previous lab introduced
a struct to combine several different pieces of data
within one logical unit.
- Each piece of data has its own name.
- Different pieces of data may have the same or different data types.
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], ....
-
One name, the array identifier (e.g.,
item) is used to designate the entire collection of data. - An index, 0, 1, 2, ..., allows access to individual pieces of data.
-
All pieces of data within an array must have the same type
(e.g.,
int, doubleor astruct).
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:
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 te forthcoming 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:
- Each row has a label (on the left)
- Each column has a label (at the top)
- Each cell (except the labels) has the same data type (e.g., doubles) and is stored in a in the two-dimensional array.
- Strings for row or column labels may be stored in separate one-dimensional arrays.
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
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:
data_t table [row][col];
where row and col have been previously
specified as integer values and data_t is whatever type
of data is stored in the array. 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:
-
Start at the base address given by the
tablevariable. -
Skip over
irows; this involvesi * colelements. -
Skip over
jelements in the given row.
Altogether, the element table[i][j] may be found at
address
table + (i*col + j)*sizeof(data_t).
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:
-
If
NUM_COLSis an integer with global scope (e.g., created by a#definestatement), then a procedure may have the header:void proc (int table [][NUM_COLS]); /* NUM_COLS declared globally */ -
Alternatively,
colcan be passed to the procedure as part of the parameters:void proc (int num_cols, int table [][num_cols]); /* num_cols passed as parameter */
