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
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, item, ....
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
int, doubleor a
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 ;
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
table were passed to a
procedure, the header of
printArray might be given as
void printArray (int arr)
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|
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.
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:
col have been previously
specified as integer values. A schematic of the array is shown to
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
table[i][j], one proceeds as follows:
Start at the base address given by the
irows; this involves
i * colelements.
jelements in the given row.
Altogether, the element
table[i][j] may be found at
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
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:
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 */
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 */