CENG 205

Data structures
Lecture 3:
Representation of Multidimensional Arrays
What is an Array?

• An array is a fixed size sequential collection of elements of identical types.

• A multidimensional array is treated as an array of arrays.
• Let a be a k-dimensional array; the elements of A can be accessed using the
following syntax:
A [ i1 ] [ i2 ]…[ ik ]

The following loop stores 0 into each location in two dimensional array A :

int row, column;

int A[3][4];
for (row = 0; row < 3; row++)
{
for (column = 0; column < 4; column++)
{
A[row][column] = 0;
}
}
 Definition of a Multidimensional Array

• One-dimensional arrays are linear containers.

[0] [1] [2]
int A[3];
2
A[1]=2;

7
Multi-dimensional Arrays
[2]
[1]
[0]
[0] [1] [2] [3] 10
[0] [0]
5
[1] [1]
[2]
[2] -1
[3]
int A[3][4];
A[0][1]=5;
[0] [1] [2] [3] [4] int A[3][4][5];
A[2][3]=-1; A[1][1][4]=10;
A[2][0][1]=7;
Array size

• In a d-dimensional array, which is declared as

<type> a[N1][N2]…[Nd];

the number of items is:

𝑑

ෑ 𝑁𝑖
𝑖=1

Example: What is the number of items in a[20][20][1]?

 StorageAllocation
• The storage arrangement shown in this example uses the
array subscript, i.e. array indices.

Array declaration: int a[3][5];

Array elements:
a[0][0] a[0][1] a[0][2] a[0][3] a[0][4]
a[1][0] a[1][1] a[1][2] a[1][3] a[1][4]
a[2][0] a[2][1] a[2][2] a[2][3] a[2][4]
Two-Dimensional Storage Allocation
A 2d array declared in C as: int A[3][5]; A: 0xb0 1
could be considered as a matrix with 3 0
rows and 5 columns A : 0xb0 12
A[0] : 0xb0
0xb0 : 1 -1
0xb4 : 0 4
0xb8 : 12
A: 1 0 12 -1 4 0xbc : -1 0xc4 7
7 -3 2 5 6 0xc0 : 4
-3
-5 -2 2 9 7 A[1] : 0xc4
0xc4 : 7 2
0xc8 : -3 5
But in reality, it has a linear structure. 0xcc : 2
0xd0 : 5 6
0xd4 : 6
0xd8 -5
A[2] : 0xd8 -2
0xd8 : -5
0xdc : -2 2
0xe0 : 2
0xe4 : 9 9
0xe8 : 7 7
Row major ordering of elements
 Memory Storage
• There are two types of placement for multidimensional
arrays in memory:
• Row major ordering
• Column major ordering
Row Major Ordering

offset = irow * NCOLS + icol

[Link]
Column Major Ordering

offset = icol * NROWS + irow

[Link]
 Three-Dimensional Storage Allocation
• Like 2D arrays, the elements of a 3D array should also be
stored contiguously in memory:
• We use the same two techniques, the Row Major Order and Column
Major Order but with added dimension.
• The elements are first stored layer by layer (or 2D array by 2D array)
• Within each 2D array, the elements follow the corresponding row or
column major order.
Memory Storage

Example: For a 2D array which is defined as A[N1][N2], if the memory

address of A[0][0] is α, then what is the memory address of A[i][0]
(according to row major ordering)?

N2

α + i * N2
N1
Memory Storage

• For a three-dimensional array defined as A[N1][N2][N3]

what is the memory storage like?

• Example: char y[2][2][4]

which slice? which row? which column?

• What is the memory address of y[1][1][3] if the memory address of

y[0][0][0] α?

α + 1 * N2 * N3 + 1 * N3 + 3
Memory Storage
Suppose the memory address of a[0][0][0] is α; the
memory address of a[i][0][0] is:

α + i * N2 * N3

Therefore, the memory address of a[i][j][k] becomes:

α + i * N2 * N3 + j * N3 + k

The memory address of a[m1][m2][m3]…[mn] is:

𝑛 𝑛
α + ෍ 𝑚𝑥 𝑎𝑥 where, 𝑎𝑥 = ෑ 𝑁𝑦 1≤ x ≤n
𝑥=1 𝑦=𝑥+1

ax = 1
 DynamicAllocation of 2d Arrays
A dynamically allocated 2d array of But in reality, A holds a reference to an array
dims: [3][5] could be considered of 3 items, where each item is a reference to
as a matrix with 3 rows and 5 columns an array of 5 integers

int** A; 1
A = (int**)malloc(3 * sizeof(int*)); 0
for(int i=0;i<3;i++)
A[i] = (int*)malloc(5 * sizeof(int)); 12
-1
4
7
A: 1 0 12 -1 4 A:
-3
7 -3 2 5 6
-5
2
-5 -2 2 9 7
-2 5
2 6
9
7
DynamicAllocation behind the scenes…
0x2092a0 1
int** A; 0
0x2092a4
A = (int**)malloc(3 * sizeof(int*));
for(int i=0;i<3;i++) 0x2092a8 12
A[i] = (int*)malloc(5 * sizeof(int));
0x2092ac -1
0x2092b0 4
A: 1 0 12 -1 4
7 -3 2 5 6
0x2092c0 7
-5 -2 2 9 7
0x2092c4 -3
0x2092c8 2
64 bit addressing 0x2092cc 5
0x209280 0x2092a0 0x2092d0 6

A: 0x209280 0x209288 0x2092c0

0x2092e0 -5
0x209290 0x2092e0
0x2092e4 -2
0x2092e8 2
0x2092ec 9
0x2092f0 7