L E C T U R E # 07
INTRODUC TION TO 2D
ARRAY
Instructors:
[Link]-e-Shawar Agha
ROAD M AP
Introduction to 2D Array
Size of 2D Array
2D Array Memory Representation
Row Major Order
Column Major Order
2D A R R A Y
The two-dimensional array can be defined as an array
of arrays. The 2D array is organized as matrices
which can be represented as the collection of rows and
columns.
There is a standard way of drawing a two-
dimensional m x n array X where, the elements of A
form a rectangular array with m rows and n columns
and where, the elements X [J.K] appears in row J and
column K .
EXAMPLE OF 2D A RRA Y
Lab book of multiple readings over several days
Periodic table
Movie ratings by multiple reviewers.
• Each row is a different reviewer
• Each column is a different movie
2D A R R A Y
Suppose, A is a two-dimensional m x n array.
The first dimension of A contains the index set 1,
... m with lower bound 1 and upper bound m, and
the second dimension of A contains the index set
1, 2, ... n with lower bound 1 and upper bound n.
The length of a dimension is the number of
integers in its index set. The pair of lengths m x
n is called size of the array.
SIZE OF ARRAY
The index set for each dimension is still consists of
consecutive integers from the lower bound to the
upper bound of the dimension. The length of a given
dimension can be obtained from the formula,
Length = U B - L B + 1
For two-dimensional array we can find the length of
the array by the following procedure,
• First we will find the length of one-
dimensional row array by the formula,
L 1 =UB 1 - LB 1 + 1
• Do this again one-dimensional column
array, L 2 =UB 2 - LB 2 + 1
• Length of array (number of elements
in two-dimensional array)
L = L1x L2
EXAMPLE
Find total number of elements in N(2:5, 3:1)
Solution
M =5–2+1
M=4
N = 1 – ( -3 ) + 1
N =1+3+1
N=5
Length of total number of elements = M x N
Length of total number of elements = 4 x 5
Length of total number of elements = 20
EXAMPLE
Given array int A(2 : 5, - 3 : 1)
The length of row one-dimensional array (5 - 2 +1
= 4)
The length of column one-dimensional array (1 -
(-3) +1=5)
Length of given array = 4 x 5 = 20
So, there are 20 elements on the given array.
2D ARRAY REPRESENTATION IN MEMORY
Let, A be a two-dimensional array m x n array.
Although A is pictured as a rectangular array of
elements with m rows and n columns, the array
will be represented in memory by a block m.n
sequential memory location. Specifically, the
programming language will store the array A
either,
• Column by Column is called column major
order or
• Row by row, in row major order
C O L U M N M A J O R O R D E R (CMO)
C O L U M N M A J O R O R D E R (CMO)
LOC(A[ J,K])=B(A)+w[M(K-L2)+( J-L1)]
Where,
M = Number of rows
B = Base address of array
W = Size of element (in bytes)
J = The desired row which I have to find
K = The desired column which I have to
find
L1 = Lower bound of row
L2 = Lower Bound of column
C M O EXAMPLE
Consider A [ -20 _ 20 , 10 – 35]
One byte of storage element
B=500
Determine L O C (A[0][30] ?
Solution
M =UB – LB + 1
M = 20 – ( -20) + 1
M = 20 + 20 + 1
M = 41
L1 = -20
L2 = 10
C M O EXAMPLE
L O C (A[J][K]) = B(A) + W[ M(K – L2) + (J – L1)]
= 500 + 1[ 41( 30 – 10) + (0 + 20)]
= 500 + 1[ 41(20) + (20)]
= 500 + 1 [ 820 + 20]
= 500 + 840
LOC(A[0][30]) = 1340
R O W M A J O R O R D E R (RMO)
R O W M A J O R O R D E R (RMO)
L O C ( A [ J , K]) = B(A) + w [ N ( J – L1) + (K – L2)]
Where,
N = Number of columns
B = Base address of array
W = Size of element (in bytes)
J = The desired row which I have to find
K = The desired column which I have to find
L1 = Lower bound of row
L2 = Lower Bound of column
RMO EXAMPLE
Consider Arr [ 4 – 7 , 1 – 3]
2 bytes of storage for each element
Base = 100
Address of Arr [6][2] = ?
Solution
B=100
W=2
J= 6
K=2
L1=5
L2= -1
RMO EXAMPLE
N= U B – L B + 1
N = 3 – (-1) + 1
N =3+1+1
N=5
LOC(Arr[6,2]) = 100 + 2 [ 5 (6 – 4) + ( 2 + 1)]
= 100 + 2 [ 5 (2) + 3 ]
= 100 + 2 [ 10 + 3]
= 100 + 2 [13]
= 100 + 26
LOC(Arr[6][2]) = 126
SUMMARY
Introduction to 2D array
Size of 2D array
Row Major Order
Column Major Order