# 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, 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 (e.g., `int, double` or a `struct`).

## 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 the above `table` were passed to a `printArray` procedure, the header of `printArray` might be given as follows:

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

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

• Start at the base address given by the `table` variable.
• Skip over `i` rows; this involves `i * col` elements.
• Skip over `j` elements in the given row.

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:

• If `NUM_COLS` is an integer with global scope (e.g., created by a `#define` statement), then a procedure may have the header:
``````void
proc (int table [] [NUM_COLS]);  /* NUM_COLS declared globally */``````
• Alternatively, `col` can be passed to the procedure as part of the parameters:
``````void
proc (int num_cols, int table [] [num_cols]);  /* num_cols passed as parameter */``````