Data
Data Structure
Structure &
&
Algorithms
Algorithms
Mohammad Nawid Rahmani 1
Two dimensional array
• It consist of rows and columns.
• It is called matrix in math and table in business or
database.
• If m is the number of rows and n is the number of
columns then the formula for the size of two Dimension is
as : size = m×n.
• Elements are denoted as A [r , c]
• r=rows of the table
(0,0)
• c=columns of the table (0,1) (0,2)
• As (1,0) (1,1) (1,2)
Mohammad Nawid Rahmani
Two dimensional array
Ex: If there are three students and got marks in five
different subjects then it can be stored in the form of two
dimension array as under:
sub1 sub2 sub3 sub4 sub5
s1 68 83 49 74 55
s2 76 66 37 59 88
s3 44 60 53 21 64
Suppose the array name is “result” and if we want to
access the 2nd student 3rd subject marks then the
statement will be
result(2,3)
While 2 shows row number and 3 shows column number
Mohammad Nawid Rahmani
How to declare
• Each language have different rules to
declare an array.
• In java
– int Array[][]=new int[6][4];
– Here
• The int represents its type ,Array is its name
and
6 and 4 show its rows and columns.
• The total number of elements of two-
dimensional array having m rows and n
columns is m*n.
• For example, an array having 2 rows and 4
columns has 2*4=8 elements.
Mohammad Nawid Rahmani
Row-by-Row mapping
• In this technique the elements of the two
dimension array will store row-wise.
• When the elements of the first row finished then
the 2nd row is started and so on.
• In row by row mapping technique the number of
row is constant while the number of column
changes for each element of a particular row.
e.g 34 21 11
56 83 32
12 43 05
(1,1) (1,2) (1,3) (2,1) (2,2) (2,3) (3,1) (3,2) (3,3)
Result 34 21 11 56 83 32 12 43 05
Mohammad Nawid Rahmani
Con’t
• The following Dope vector formula is used
to access a particular element of three
dimension array.
loc[A(i,j)] = ba+w[n(i-1)+(j-1)]
where
ba = base address or starting address
n = Total number of columns
i = Row number of a particular element
j = Column number of element
w = word per memory cell or word length
Mohammad Nawid Rahmani
EXAMPLE
Consider the 3*3 matrix array before :
Suppose base(score)=200 and there are w=1
word per memory cell.
Suppose the programming language stores two-
dimensional array using row-major order.
Then find the address of [2*3]:
loc[A(i,j)] = ba+w[n(i-1)+(j-1
Loc[A(I,j)]=200+1[3(2-1)+(3-1)]
Loc[A(I,j)]=200+1[3+2]
Loc[A(I,j)]=200+5
Loc[A(I,j)]=205
Mohammad Nawid Rahmani
Column-by-Column mapping
That type of mapping in which all the elements of
an array stores column wise that is first elements
of 1st column stores then 2nd column and so on, is
called column by column mapping
e.g 34 21 11
56 83 32
12 43 05
(1,1) (1,2) (1,3) (2,1) (2,2) (2,3) (3,1) (3,2) (3,3)
34 56 12 21 83 43 11 32 05
Mohammad Nawid Rahmani
Con’t
Formula for accessing a particular element using dope
vector using column-by-column mapping is as under
loc[A(i,j)] = ba+w[m(j-1)+(i-1)]
where
A = array name
ba= base address or starting address
m = total number of rows
i = particular row number
j = particular column number
w = word per memory cell or word length
Mohammad Nawid Rahmani
EXAMPLE
Consider the 3*3 matrix array before :
Suppose base(score)=200 and there are w=1
word per memory cell.
Suppose the programming language stores two-
dimensional array using row-major order.
Then find the address of [3*2]:
loc[A(i,j)] = ba+w[m(j-1)+(i-1)]
Loc[A(I,j)]=200+1[3(3-1)+(2-
1)]
Loc[A(I,j)]=200+1[6+1]
Loc[A(I,j)]=200+7
Loc[A(I,j)]=207
Mohammad Nawid Rahmani
Accessing methods:
• The following methods are used for
accessing of array elements:
1. DOPE vector method
2. LIFFE Access method
3. ACCESS TABLE
Mohammad Nawid Rahmani
LIFFEE ACCESS METHOD
– Fastest method to access array
– But take more memory ,set of pointers
used to access array
– These pointers contain address of each
element in the array as
6 7 8
3 2 1
4 2 1
Row by row
6 7 8 3 2 1 4 2 1
Column by
column
6 3 4 7 2 2 8 1 1
Mohammad Nawid Rahmani
ACCESS TABLE
• Previous method deal with numeric
while this one deal with character
processing
– If we have an array of name as
– This will store in computer memory as
A L I K H A N J A n
Mohammad Nawid Rahmani
Cont.
• As dope vector and liffee method access only
one memory location so
• To deal with string data ,”access table” is
used.
Mohammad Nawid Rahmani
Mohammad Nawid Rahmani
Mohammad Nawid Rahmani
Mohammad Nawid Rahmani
Mohammad Nawid Rahmani