In this tutorial, we are going to learn about how to store elements in a two-dimensional array. For those who love to learn through videos, jump over to the bottom of the page, there’s a video tutorial for you.
Before starting storing elements of a multi-dimensional array, let’s say I’ve an one dimensional array having elements like this:
A1, A2, A3….An
These elements are stored in my linear memory space as follows:
A1 A2 A3 A4 ... An
One thing you need to remember is, no matter what type of array it is (1D or multi-dimensional), they will be always stored linearly in the memory space as above.
Let’s jump to the case of multi-dimensional arrays now. Imagine I’ve a 3×3 matrix like this:
A11 A12 A13 A21 A22 A23 A31 A32 A33
The real problem of storing elements arises here, since elements have to be stored linearly in the memory space, we have many possible ways to store them. Here are some of the possibilities I could’ve had for the matrix above.
1. A11 A13 A12 A21 A23 A22 A31 A33 A32 A33 2. A11 A22 A33 A12 A32 A13 A23 A31 A32 A21
… and I could go on filling randomly depending on the no. of elements I’ve in my 2-D array.
Out of all these possible ways, there are two main ways of storing them, they are:
- Row Major Ordering
- Column Major Ordering
1. Row Major method
In this method, the elements of an array are filled up row-by-row such that the first row elements are stored first, then the second row and so on.
Most of the high level programming languages like C/C++, Java, Pascal, etc use this method for storing multidimensional arrays.
Offset for row major ordering
As you can see in the 3×3 Matrix array we have above, I want to know at what position is my element A12 located in the linear memory space. This position is called the OFFSET.
One way to do it is to make up a linear diagram like the one below, count manually using 0 as the starting index and go on till the element I need. But imagine you are given an array like A, definitely you can’t go over all these elements if you wanted to know, say where A is located.
For this, we resort to a fairly easy mathematical method of calculating the offset.
Here is the formula to calculate the offset for row major ordering
2. Column Major method
In Column Major ordering, all the elements of the first column are stored first, then the next column elements and so on till we are left with no columns in our 2-D array.
Offset for column major method
Calculating address of a particular element
Depending on the ordering method the elements are stored in the memory, we will get different positions of an element in the linear memory and consequently a different address for each method. To calculate the address we use the following procedure:
Step 1: Get the offset value of the element under consideration, make sure you use the correct forumula.
Step 2: Multiply the offset with the size of the element’s datatype (Like int is of 4 bytes for 32-bit, Earlier compilers like TurboC worked on 16-bit platform and for them size of int is 2 bytes).
Step 3: Add this to the base address to get the final address