Ordering of Main memory
Imagine a matrix or a grid. It has certain number of rows and columns. Elements in a matrix like structure can be accessed by indexing with a combination of row and column. For example, M[i][j] enables access of single element in matrix M where i is the row number and j is the column number.
In the domain of computing, many applications require matrix-like structuring of data. For example, an image is represented as a matrix in memory. A matrix is implemented using two dimensional arrays in C language.
So far we have worked with arrays that have single indexing. This is similar to having a matrix with a single row and multiple columns. Main memory occupies a linear address space. Thus, it can be treated as a very large, single dimensional array. If our program has a two-dimensional array (or higher) then the compiler maps it into single dimension of main memory for storage. Two ways to achieve this are row major order and column major order - the former being the most commonly used.
Two-dimensional arrays
Typically programmers deal with arrays that have single dimension, which translates to array data structure that has a single row and multiple columns. Intuitively, each value of single dimensional array is located at a different column. When an array data structure has multiple rows along with multiple columns, it becomes two-dimensional. The number of rows and columns need not be same. For R rows and C columns, the indexing of the two dimensional array will range from 0 to R-1 and 0 to C-1.
#define ROWS 3
#define COLUMNS 4
int main(){
/*
The general pattern for declaration of 2d array:
data_type var_name[num_rows][num_columns] where
- data_type is a valid data type in C language
- var_name is the name of the variable
*/
int twoD_arr[ROWS][COLUMNS]; /* declaration without initialization*/
/*Initialization*/
/*First row: values 0 through 3*/
/*Second row: values 4 through 7*/
/*Third row: values 8 through 11*/
int twoD_arr2[ROWS][COLUMNS] = {0,1,2,3,4,5,6,7,8,9,10,11};
/*Clearer way to initialize*/
int twoD_arr3[ROWS][COLUMNS] = {{0,1,2,3}, {4,5,6,7}, {8,9,10,11}};
/*Accessing the elements in two dimensional array*/
for (short i = 0; i < ROWS; i++){
for (short j = 0; j < COLUMNS; j++){
printf("twoD_arr3[%d][%d] = %d\n", i, j, twoD_arr3[i][j]);
}
}
return 0;
}
Three-dimensional arrays
A three dimensional array can be visualized a series of two dimensional arrays as shown in the image below.
Image source: Geeks for Geeks
/*Assume the preprocessor directive #define DEPTH 3*/
/*series of 3 two dimensional arrays*/
int threeD_arr3[DEPTH][ROWS][COLUMNS] = {
{{0,1,2,3}, {4,5,6,7}, {8,9,10,11}},
{{0,-1,-2,-3}, {-4,-5,-6,-7}, {-8,-9,-10,-11}},
{{2,4,6,8}, {-2,-4,-6,-8}, {12,13,14,15}}
};
for (short i = 0; i < DEPTH; i++){
for (short j = 0; j < ROWS; j++){
for (short k = 0; k < COLUMNS; k++){
printf("threeD_arr3[%d][%d][%d] = %d\n", i,j,k, threeD_arr3[i][j][k]);
}
}
}
Calculating the index values & addresses for 2D and 3D arrays
Since multidimensional arrays are implemented using contiguous memory locations, a simple arithmetic formula can be devised for calculating the single dimensional index for a given set of depth, rows and columns. Consider the following:
arr2[R][C] is a two dimensional array. arr3[D][R][C] is a three dimensional array. Assuming row-major order:
It must be noted that while performing lookup operation in C language using pointers, the size of data type (Z, above) must not be used. Pointer arithmetic will increment or decrement the addresses based on the type of data that the pointer points. For example, ++ operation on int* will increment the address by 4 bytes. However, ++ operation on char* increments the address by 1 byte.