What do you mean by two dimensional array and multi dimensional array in data structure and an algorithm?

Question

In this article, you will get to know about:

1. 2-D array and how to represent it in memory
2. Multi-dimensional array

Answer 1

1. Two-dimensional arrays

                                 

• A 2-D array is a list of a finite number m×n of homogenous data elements.
• The elements of the array are referred by two index sets consisting of m and n consecutive integer numbers. 
• The elements of the array are stored in consecutive memory location.
• 2-D arrays are called matrices in mathematics and tables in business applications

2. Representing 2D array in memory

                                       

                 

• The elements are stored column by column i. e. m elements of first column and stored in first m locations, elements of the second column are stored in next m locations and so on.

                                                  

• The elements are sorted row by row for n elements.

For 2-D array a of size m×n , using the base address of a[i][j] element by:

In column major order

loc(a[i][j]) =base(a) +w(m*j+i)

 In row major order

loc (a[i][j])=base(a) +w(n*i+j)

where, w=width i. e. number of bytes taken by each element

 m=total number of rows

n=total number of columns

Note:The product A×B of two matrices A and B is defined only when the number of columns in A equals to the number of rows in B.

Square Matrix

• A square matrix has the same number of rows and columns.
• Some special form of square matrix are:
• Diagonal matrix
• Tridiagonal matrix
• Lower triangular matrix
• Upper triangular matrix

Diagonal matrix

• A matrix B is diagonal iff B(i,j) =0 for i≠j

• The  diagonal matrix can be stored as 1-D array to reduce memory space.

 Tridiagonal matrix

• A matrix B is trdiagonal iff B(i,j) =0 for |i-j|>1

• In a n×n tridiagonal matrix B, the non-zero elements lie on one of the three diagonals.
• Main diagonal , for which i=j.It has n elements.
• Diagonal below main diagonal, for which i=j+1.It has n-1 elements.
• Diagonal above main diagonal, for which i=j-1.It has n-1 elements.
• It has 3n-2 non-zero elements.
• The elements of tridiagonal matrix can be mapped up by following ways
• Row wise
• Column wise
• Diagonal wise beginning with the lowest.

Triangular matrix 

Lower triangular matrix 

• A matrix B is lower triangular iff B(i,j) =0 for i<j

Upper triangular matrix

• A matrix B is upper triangular iff B(i,j) =0 for i>j

• Total number of non-zero elements in triangular matrix is n(n+1) /2

Sparse Matrix

• A m×n matrix A is said to be sparse if many of its elements are zero. 
• Matrix that is not sparse is known as dense matrix.
• It is not possible to define an exact boundary between dense and sparse matrices.
• The diagonal and tridiagonal matrices fit into the category of sparse matrices.

Array representation of sparse matrices

• In array representation, an array of triplets of type
• <row,col,element>
• is used to store non-zero elements, where first field of the triplet is used to record row position, second to record column position and third one to record non-zero element of the sparse matrix. 

• In addition, we need to record the size of the matrix(i.e. number of rows and columns) and non-zero elements. For this purpose, the first element of array triplet is used, where first field stores number of rows, second field stores number of non-zero elements . The remanining elements of the array store non-zero elements of the sparse matrix on row major order.

3. Multi-Dimensional Array

• A linear array can be called 1-D array, since each element in the array is referred by a single subscript.
• A 2-D ‘m×n’ array is a collection of m. n data elements such that each element is specified called subscriptsA[i],[j]
• A 3-D array ‘m×n×s’ . Then it contains m. n. elements.
• For example, Suppose B is a three dimensional 2×4×3 array, then B contains 2.4.3=24 elements.

---