What is ADDRESS CALCULATION in Data Structure

Address calculation in 2-D array: suppose A is a 2D array with dimensions M1 X M2. So that here total number of elements is equal to M1 X M2. Address should be calculated using one of the two methods as the following,

a.      Row-by-Row

Location (A [j, k]) = Base (A) + w [N (j-1) + (k -1)]

Here, j and k indicates index value of the element whose address you want to search. Base (A) is the starting address of the given array. W is the memory word required to store given array’s element. Here, array is the of size M(rows) X N(columns).

b.     Column-by-Column

Location (A [j, k]) = Base (A) + w [M (k-1) + (j -1)]

Here, j and k indicates index value of the element whose address you want to search. Base (A) is the starting address of the given array. W is the memory word required to store given array’s element. Here, array is the of size M(rows) X N(columns).

Examples:

1.      Consider 30 X 4 2D arrays and base address is 200 and 1 word per memory locations. Find out the address of A (15, 3).

Base (A),                      M =30,  N=4,      j=15,     k=3,      w=1

a.      Row-by-row

Location (A [j, k]) = Base (A) + w [N (j-1) + (k -1)]

Location (A [15, 3])           = 200 + 1 [4 (15 - 1) + (3 - 1)]

                              = 200 + 1 [56 + 2]

                              = 200 + 58

                              =258

b.      Column-by-column

Location (A [j, k]) = Base (A) + w [M (k-1) + (j -1)]

Location (A [15, 3])           = 200 + 1 [30 (3 – 1) + (15 – 1)]

                              = 200 + 1 [30 (2) + 14]

                              = 200 + 74

                              =274

ii.                Address calculation in multidimensional array: Suppose A is a 3D array of size M1 X M2 X M3. So total number if elements are M1 X M2 X M3. In 3D array lower bound (LB) is not always zero (0). It can be any number. Base address of any row of matrix is called effective address.

For example, A [2:11] indicates that A is a 1D array with lower bound 2 and upper bound (UB) 11.

A [2:11, 3:15] indicates that A is a 2D array with lower bound (LB) of row is 2 and Upper Bound (UB) of row is 11. In the same way lower bound (LB) of column is 3 and upper bound (UB) of column is 15.

        Length of each dimension is equal to L_i = UB – LB +1

Lower bound (LB) is not always started with zero (0). So, we have to calculate effective address of each value.

      Effective Address (E_i) = K_i - LB

        Real address of any element is calculated as follows,

        Row-by-Row: Base (A) + W [(E₁L₂ +E₂) L₃ + E₃]

      Column-by-column: Base (A) + W [(E₃L₂ + E₂) L₁ + E₁)

Example: Suppose multidimensional array A and B are declared using A [-2:2, 2:22] and

B [1:8, -5:5, -10:5].

1.      Find out the length of each dimension and number of elements in array A and B.

2.     Consider B [3, 3, 3] elements in array B find effective address E1, E2 and E3. Also find out the real address of these elements. (In this case the base address of array B is 400 and W is 4)

Answer:       For array A

L₁    = UB –LB +1                       L₂            = UB –LB +1

        =2 – (-2) +1                                        =22 – 2 + 1

        = 4 + 1 = 5                                          = 21

For array B

L₁ = UB –LB +1                          L₂= UB –LB +1                    L₃= UB –LB +1

      = 8 – 1 + 1                                 = 5 – (-5) +1                        =5 – (-10) +1

      = 8                                              = 11                                     = 16

Total number of elements in array B is: L₁ X L₂ X L₃ = 8 X 11 X 16 = 1408.

Here in given question K_i = 3, 3, 3 therefore K₁=3, k₂ = 3 and K₃ = 3

        LB₁= 1, LB₂ = -5 LB₃ = -10

        E₁ = K₁ – LB₁ = 3 – 1 = 2

        E₂ = K₂ – LB₂ = 3- (-5) = 8

        E₃ = K₃ – LB₃ = 3 – (-10) = 13

The real address Row – by- Row:

= Base (A) + W [ (E₁L₂ + E₂) L₃ + E₃]

        = 400 + 4 [(2 (11) + 8) 16 + 13]

        = 400 + 4 [(22+8) 16 + 13]

        = 400 + 4 [(30) 16 + 13]

        = 400 + 4 [480 + 13]

        = 400 + 4 [493]

        = 400 + 1972

        = 2372

The real address Column – by – column:

        = Base (A) + W [(E₃L₂ +E₂) L₁ + E₁]

        = 400 + 4 [(13(11) + 8) 8 + 2]

        = 400 +4 [(143 + 8) 8 + 2]

        = 400 + 4[(151) 8 + 2)]

        = 400 + 4[1208 + 2]

        = 400 + 4840

        = 5240

Sparse Matrix: It is a matrix with relatively high proportion of zero (0) values called sparse matrix. But these zero values occupy lots of memory. So, sparse matrix must be converted to some form which contains only non-zero values.