Page 60 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Unit 4: Arrays

4.2.2 Representation of Two-Dimensional Arrays Notes

Let A be a two-dimensional m × n array. Although A is pictured as a rectangular array of
elements with m rows and n columns, the array will be represented in memory by a block of
m.n sequential memory locations. If they are being stored in sequence, then how are they
sequenced? Is it that the elements are stored row wise or column wise? Again, it depends on the
operating system. Specifically, the programming languages will store the array A in either,
Column by column, called column-major order, or

Row by row, called row-major order.
Row Major Representation

The first method of representing a two-dimensional array in memory is the row major
representation. Under this representation, the first row of the array occupies the first set of the
memory location reserved for the array, the second row occupies the next set, and so forth.
The schematic of row major representation of an Array is shown in Figure 4.7.

Let us consider the following two-dimensional array:
a b c d
e f g h
i j k l

To make its equivalent row major representation, we perform the following process:
Move the elements of the second row starting from the first element to the memory location
adjacent to the last element of the first row. When this step is applied to all the rows except for
the first row, you have a single row of elements. This is the Row major representation.
By application of above mentioned process, we get {a, b, c, d, e, f, g, h, i, j, k, l }

Figure 4.7: Schematic of a Row major representation of an Array

Row 0 Row 1 Row 2 ….. Row i

Column Major Representation

The second method of representing a two-dimensional array in memory is the column major
representation. Under this representation, the first column of the array occupies the first set of
the memory locations reserved for the array. The second column occupies the next set and so
forth. The schematic of a column major representation is shown in Figure 4.8.

Consider the following two-dimensional array:
a b c d
e f g h
i j k l
To make its equivalent column major representation, we perform the following process:

Transpose the elements of the array. Then, the representation will be same as that of the row
major representation.

LOVELY PROFESSIONAL UNIVERSITY 53