2 C Features - Pointers and Arrays

2.3 Multi-dimensional arrays

The arrays we have learned so far are one dimensional array, namely have only one subscript index. In this section, we will introduce n-dimensional arrays, which has n subscript indexes. We first study two-dimensional arrays, and then general multi-dimensional arrays.

2.3.1 Two-dimensional arrays

A two-dimensional arrays (or simply 2D arrays) organizes data elements in row and column manner: each row has the same number of elements, each column has the same number of elements, and each element is in a row and a column. 2D arrays are often used to present matrices, and rectangular tables.

Syntax of 2D arrays

A two-dimensional array is declared using syntax data_type array_name[row][col];

It declares a 2D array of total row * col elements organized in row number of rows and col number of columns. It tells compiler to allocate a memory block of size row * col * sizeof(data_type) for the 2D array.

An element at row i and column j is represented using two subscripts i and j as array_name[i][j], where 0 <= i <= row-1 and 0 <= j <= col-1. i and j are called row index and column index respectively.

2D array elements are stored in the memory block by row major (row by row) order: row 0, row 1, and so on. In this ordering, array_name[0][0] is the first element and of the lowest address, array_name[row-1][col-1] is the last element and of the highest address.

Example:

int a[2][3];      // this declares an int type 2D array of 2 rows and 3 columns. 
a[1][2] = 2;      // this sets value 2 to element at row 1 and column 2
int b = a[1][2];  // this gets the value of element at row 1 and column 2

Table 1 shows the row and column organization of the 2D array a[2][3].

Table 1: 2D array rows and columns.
rows/columns column 0 column 1 column 2
row 0 a[0][0] a[0][1] a[0][2]
row 1 a[1][0] a[1][1] a[1][2]

The output of the above program is like the following.

a[0][0] : 0, address : 6684288
a[0][1] : 1, address : 6684292
a[0][2] : 2, address : 6684296
a[1][0] : 1, address : 6684300
a[1][1] : 2, address : 6684304
a[1][2] : 3, address : 6684308

Listing 1 gives an example 2D array traversal in row major order. Check the addresses of the 2D array elements in the output, we see the addresses are in increasing order.

2D array initialization

A 2D array can be initialized similar to that of 1-dimensional array.

Example:

int a[2][3]={90, 87, 78, 68, 62, 71};  // this initializes 2D elements in row major linear order

If the number of items on the right side is less that of the 2D array, the rest will be set to 0.

A 2D array can also be initialized in row by row manner as the following.

int a[2][3]={{90,87,78},{68, 62, 71}}; // row 0: {90,87,78},  row 1: {68, 62, 71}

2D array operations by pointers

Similar to 1D array operations, 2D array operations can be done by using pointers.

Given data_type array_name[row][col], data_type *ptr = &array_name[0][0];. Then ptr+i*col + j points to element array_name[i][j], and *(ptr+i*col + j) gives the value of array_name[i][j]. This is because element array_name[i][j] is at position i*col + j in the row-major ordering of 2D array elements. We refer to this position number as location index. On the other hand, if a location index k is given, then the row index i and column index j can be calculated as i = k / col, j = k % col.

Example:

int a[2][3]; 
int *ptr = &a[0][0];   // ptr points to a[0][0]
*(ptr + 1*3 + 2) = 1;  // this is equivalent to a[1][2] = 1;

Note that the array name of 2D array does not represent a reference to the first element of an array, instead it represents a reference to the first row.

Example:

int a[2][3]={{1,2,3},{4,5,6}};
int (*ptr)[3];   // this declares an array pointer of type int[3]
ptr=a;           // ptr points to the first row: a[0]
ptr+i            // points to row i: a[i]
*(ptr+i)+j       // points to a[i][j], i.e., represents &a[i][j]
*(*(ptr+i)+j)    // represents a[i][j]

Passing 2D arrays to functions

There are four methods to pass a 2D array to a function.

  1. Passing individual 2D array elements to a function. This is the same as passing individual elements of 1D array to a function.
  2. Passing individual element references to a function. This is the same as passing element address to a function.
  3. Passing a row to a function. This is the same as passing an entire array by array name to a function.
  4. Passing 2D array name to a function. This is the same as passing an array of rows to a function.

The following programs show the examples of methods 3 and 4.

2.3.2 High dimensional arrays

C supports multi-dimensional arrays of dimensions bigger than 2.

In general, an n-dimensional array can be declared as: data_type \(a[m_1][m_2]\dots [m_n];\)

It declares an n-dimensional array of \(m_1 \times m_2 \times \dots \times m_n\) elements.

An n-dimensional array element is represented by using n subscripts as \(a[i_1][i_2]\dots [i_n]\), where \(0 \le i_1 < m_1, 0 \le i_2 < m_2, \dots, 0 \le i_n < m_n\).

The elements are organized in memory in order of the increasing lexical order (dictionary order) of their subscript index. That is, if \((i_1, i_2, ..., i_n) < (j_1, j_2, ..., j_n)\), then \(a[i_1][i_2]\dots[i_n]\) is before and of lower address than \(a[j_1][j_2]\dots[j_n]\) in memory.

Where the lexical order of two list \((i_1, i_2, ..., i_n)\) and \((j_1, j_2, ..., j_m)\) is defined by following algorithm:

Algorithm: Lexical comparison, returns -1 if less, 0 if equal, 1 if bigger
Input: n, m, (i<sub>1</sub>, i<sub>2</sub>, ..., i<sub>n</sub>), (j<sub>1</sub>, j<sub>2</sub>, ..., j<sub>m</sub>) 
Step 1: result = 0, k = 0
Step 2: if i<sub>k</sub> < j<sub>k</sub>, result = -1, goto step 8
Step 3: if i<sub>k</sub> > j<sub>k</sub>, result = 1, goto step 8
Step 4: k = k+1
Step 5: if k <= n and k > m, result = 1, goto step 8
Step 6: if k > n and k <= m, result = -1, goto step 8
step 7: goto step 2
Step 8: output result

Examples of 3D arrays

int a[2][3][4]; 
// this declares a 3D int array of 2*3*4 = 24 elements, sizeof(a) equals to 24*4 = 96 bytes

Elements are ordered by lexical-order of index:

a[0][0][0], a[0][0][1], a[0][0][2] a[0][0][3],
a[0][1][0], a[0][1][1], a[0][1][2] a[0][1][3],
a[0][2][0], a[0][2][1], a[0][2][2] a[0][2][3],

a[1][0][0], a[1][0][1], a[1][0][2] a[1][0][3],
a[1][1][0], a[1][1][1], a[1][1][2] a[1][1][3],
a[1][2][0], a[1][2][1], a[1][2][2] a[1][2][3],

Declare and initialization examples

int a[2][3][4]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24};
Int a[2][3][4]={{1,2,3,4,5,6,7,8,9,10,11,12},{13,14,15,16,17,18,19,20,21,22,23,24}};
int a[2][3][4]={{{1,2,3,4},{5,6,7,8},{9, 10, 11, 12}}, {13,14,15,16,17,18,19,20,21,22,23,24}};

3D array operations by pointers

int a[2][3][4]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24};
int (*ptr)[3][4];      // declare ptr to used for pointing 2D array int[3][4] 
ptr = a;               // ptr points to a[0] 
int *p = &a[0][0][0];  // p points to a[0][0][0]

a[0] is a reference to the first [3][4] 2D array, 
a[1] is a reference to the second [3][4] 2D array, 
ptr  points to a[0],  ptr holds &a[0][0][0],  
ptr++; ptr points to a[1], ptr holds &a[1][0][0]

The following expressions do the same thing:
a[i][j][k]  
*(*(a+i)+j)+k)
*(*(*(ptr+i)+j)+k)  
*(p + (i*3+j)*4+k)

In expression *(p + (i*3+j)*4+k), (i*3+j)*4+k represents the location index of element a[i][j][k] in the memory block of the 3D array. The conversion between subscript index notation and location index.

h = (i*2+j)*3+k = i*2*3 + j*3 + k; 
k = h%3;  
d = h/3;  
j = d%2; 
i = d/2;

All the notations and operations of 3D arrays can be generalized to 4D arrays and so on. Theoretically, C supports any dimensional arrays.

2.3.3 Exercises

Self-quiz

Take a moment to review what you have read above. When you feel ready, take this self-quiz which does not count towards your grade but will help you to gauge your learning. Answer the questions posed below.

Go back