Data Structure (KCS-301)
Unit 1
Prepared By
N. U. Khan
Computer Science And Engineering Department
IMS Engineering College, Ghaziabad
ARRAY
• Array is a finite collection of similar data elements stored in
contiguous/adjacent memory location
• Array basically is a set of pairs index and value, for each index which
is defined, there is a value associated with that index. This is called
one to one mapping
• Data Structure of array is as follows:
• DS = Memory organization + Operations
• Memory organization: Consecutive set of memory location
• Operations:
• 1. CREATE(): It produce a new empty array
• 2. RETRIVE(): It return a appropriate value associate with index
number
• 3. STORE(): It insert a value at defined index number
N U Khan 2
Types of Array
Array
Multi D-
1D-array array
2D-array 3D-array
N U Khan 3
1) One Dimensional Array
• We know that array is a consecutive set of memory locations of same
type.
• we can say that the compiler limits the storage region (From Lower bound
to Upper bound ) to storing set of element, and the first location is
individual element of array , and this called the Base Address.
• Data_Type X[ LB : UB ];
LB UB
•
BA ith
X[0] X[1] X[2] X[3] X[4] X[5] X[6] X[7]
• Size of Array = ( UB – LB + 1 ) x size of cell
• Indexing formula for calculating the address of ith element of array
• let us assume the Base Address of ‘X’ is ‘BA’ and size of cell is ‘w’
• we want to find the address of ith location, where LB<= i <= UB, location
of X[i] will be :
• Loc( X[i] ) = Base Address(X) + (Number of elemts before ith element)*w
• Loc(X[i]) = BA + ( i – LB ) x w
• Where w is the size of data element ( Data_Type may be int, float, char )
N U Khan 4
Example
• let us assume the Base Address of ‘X’ is 500 and we want to find the
address of 4th location, where declaration of array is int X[8]
• In ‘C’ language, location of X[i] will be :
• Location ( X[i] ) = Base Address(X)+ ( i – 0 )*w
BA
X[0] X[1] X[2] X[3] X[4] X[5] X[6] X[7]
For example :
• Given that BA(X) = 500, location is i = 4
• Lower bound (in case of ‘C’ ) is LB=0
• Size of cell w = 2 Bytes (size of integer )
• Loc(X[i]) = BA + ( i – LB ) x size of cell
• Loc(X[4]) = 500 + ( 4 – 0 ) x w
• = 500 +4 x 2
• = 508
• So the address of forth element is 508 because the first element in 500.
N U Khan 5
2) Two - Dimensional Array :
• A two dimensional Array is the collection of one dimensional Array
• A two dimensional Array A is the collection homogeneous ‘m X n’
data elements in contagious memory location .
• Programming language stores the 2-D Array in 1-D memory in
either of two ways –
• 1. Row major order
• 2. Column major order
N U Khan 6
2) Two - Dimensional Array :
Col 0 Col 1 Col 2 Col 3
Row 0 8 6 5 4
Row 1 2 1 9 7
Row 2 3 6 4 2
N U Khan 7
Address calculation of 2-D Array
LB2 jth UB2
• 1) Row Major Order:
• First row of the array occupies the first set of
memory locations reserved for the array;
LB1 3 1 -5 8 0 6
Second row occupies the next set, and so on.
• Let declaration of 2-D Array is -2 11 4 7 9 2
• Data_Type A[ LB1 : UB1 ][ LB2 : UB2 ] 5 16 -9 (i,j) -3 15
ith
• Let us assume: 18 10 -8 17 -1 -7
• Base address of array ‘A’ is ‘BA’ UB1 14 20 19 12 -4 13
• Size of cell is ‘w’
Base Address=BA
Total No of cell before (i,j)
Row-0 Row-1 Row-2
N U Khan Row-3 Row-4 8
• Location of (i,j)th elemnt = Base address of array +
Total number of cells before (i,j) * size of cell
• Loc(A[i,j])=BA + [Total No of complete rows before ith
row * No of cells in each row + Total No of cells in
incomplete ith row] * size of cell
• Loc(A[i,j])=BA + [(i - LB1 ) x (UB2-LB2+1) + (j-LB2)] x w
• In C-Language: Let int A[ROW][COL];
• Lower bound=0, Upper bound=MaxSize-1
• int A[0 : ROW-1 ][0 : COL-1 ]
• Loc(A[i][j])=BA+[(i-0)*(COL-1 – 0 +1) + (j-0)]*w
• Loc(A[i][j]) = BA + ( I x COL + j ) x w
N U Khan 9
Numerical Example on Row major order
• Data_Type A[ LB1 : UB1 ][ LB2 : UB2 ]
• Location (A[i,j]) = BA + [ ( i-LB1 ) x (UB2-LB2+1) + ( j-LB2 ) ] x w
• For example :
Given an array [1…5,1…7] of integers. Calculate address of element A[4,6],
where BA=900 Bytes.
• Solution:-
• i=4,j=6,
• LB1 = 1, UB1 = 5
• LB2 = 1, UB2 = 7
• Size of cell is w = 2 Bytes
• Loc(A[i,j])=BA+[ (i-LB1) * (UB2-LB2+1) + (j-LB2) ]*w
• Location (A [4,6]) = BA + [ (4 – 1 ) x (7 – 1 + 1) + (6 – 1 )] x w
• = 900 + [ 3 x 7 + 5 ] x 2
• = 900 + 25 x 2
• = 950
N U Khan 10
Address calculation of 2-D Array
LB2 jth UB2
• 1) Column Major Order:
• Order elements of first column stored
linearly and then comes elements of next LB1 3 1 -5 8 0 6
column and so on.
-2 11 4 7 9 2
• Data_Type A[ LB1 : UB1 ][ LB2 : UB2 ]
ith 5 16 -9 (i,j) -3 15
• Let us assume: 18 10 -8 17 -1 -7
• Base address of array ‘A’ is ‘BA’ UB1 14 20 19 12 -4 13
• Size of cell is ‘w’
Base Address=BA
Total No of cell before (i,j)
Col-0 Col-1 Col-2 Col-3 Col-4
N U Khan Col-5 11
• Location of (i,j)th elemnt = Base address of array +
Total number of cells before (i,j) * size of cell
• Loc(A[i,j])=BA + [Total No of complete columns
before jth col * No of cells in each col + Total No of
cells in incomplete jth col] * size of cell
• Loc(A[i,j])=BA+[ (j-LB2) * (UB1-LB1+1) + (i-LB1) ]*w
• In C-Language: Let int A[ROW][COL];
• Lower bound=0, Upper bound=MaxSize-1
• int A[0 : ROW-1 ][0 : COL-1 ]
• Loc(A[i][j])=BA+[(j-0)*(ROW – 1 – 0 +1) + (i-0)]*w
• Loc(A[i][j]) = BA + ( j x ROW + I ) x w
N U Khan 12
Numerical Example on Column major order
• Data_Type A[ LB1 : UB1 ][ LB2 : UB2 ]
• Location(A[i,j]) = BA + [ ( j - LB2 ) x ( UB1 - LB1 + 1 ) + ( i - LB1 ) ] x w
• For example :
Given an array [1…6,1…8] of float. Calculate address of an element A[5,7],
where BA=300.
• Solution:-
• i=5, j=7,
• LB1 = 1, UB1 = 6
• LB2 = 1, UB2 = 8
• Size of cell is w = 4 Bytes
• Loc(A[i,j])=BA+[ (j-LB2) * (UB1-LB1+1) + (i-LB1) ]*w
• Location (A [5,7]) = BA + [ (7 – 1 ) x (6 – 1 + 1) + (5 – 1 )] x w
• = 300 + [ 6 x 6 + 4 ] x 4
• = 300 + 40 x 2
• = 380
N U Khan 13
Tutorial Sheet
Q1 Each element of an array Data[20][50] requires 4 Bytes
of storage. Base address of data is 2000. Determine the
location of Data[10][10], when the array is stored as
Row major
Column major
Q2 A 2-D array X[5][4] is stored a row wise in the memory.
The first element of the array is stored at location 80.
Find the memory location of X[3][2] if the each
element of array requires 4 memory locations.
Q3 Give an array float X[6][6] whose base address is 100.
Calculate the location of X[2][5], where array ‘X’ is
stored row-wise.
N U Khan 14
