Page 25 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes Memory Allocation to Three-dimensional Array

Suppose we want to Calculate Address of A(i , i , i ). i.e. Address of i th window, i th Row and
1
1
3
2
2
i th Column.
3
… … … …
LB UB
3 3
LB A
2
:
:
:
:
UB 2

:
:
:
… … …
LB i
3 3
LB A
2
:
:
: A(i , i , i ) UB
: 1 2 3 1
i 2

Then, for Row Major Order Form:
Address of A(i , i , i )
1 2 3
= _+((i *(UB – LB + 1) + i )*(UB – LB + 1) + i )*s …(11)
3 2 2 2 1 1 1
Memory Allocation to Multi-dimensional Array

Now if we generalize the formulae (11) for the n dimensions of Array then
For Row Major form
Let, Add. of A(LB , LB , LB ...LB ) = x
1 2 3 n
Add. of A [i , i , i , ...n ]
1 2 3 3
= x [(i – LB ) (UB – LB + 1)
1 1 2 2
.....(UB – LB + 1) + (i – LB )(LB – LB + 1)....(UB – LB + 1)+...
n n 3 3 4 4 n n
.......(i – 1 – LB – 1)(UB – LB + 1) + (i – LB )]*s …(12)
n n n n n n
Now Program for Address Calculation can be made by taking number of dimensions, lower and
upper Bounds of each dimensions, address of A[LB , LB ....LB ] and size as input from user and
2
1
n
give Address of A[i , i ...i ] as output.
1 2 n

20 LOVELY PROFESSIONAL UNIVERSITY