Chapter-2

Linear Data Structure

(Part-1 Array

&

Matrix)

Prepared By: Dr. Dhruti Sharma, IT, SCET

 OutLine
▪ Array
• Representation of arrays
• One dimensional array
• Two dimensional array
▪ Applications of arrays
• Symbol Manipulation (matrix representation of polynomial
equation)
• Sparse matrix
▪ Sparse matrix and its representation

Prepared By: Dr. Dhruti Sharma, IT, SCET

 One Dimensional Array
 Array is a list of a finite number of homogeneous data items (i.e. data
items of the same type).
 Array is also known as subscripted variable. It can be accessed by
index.
 Number of elements in array is known as length of array.
LENTH = UB – LB + 1
Where UB is upper bound and LB is lower bound.
 The element of an array A may be denoted by subscript notation.
A1, A2, A3, ……. An
By the parentheses notation
A(1),A(2), …….. A(N)
By the bracket notation
A[1],A[2],A[3], ….A[N]

Prepared By: Dr. Dhruti Sharma, IT, SCET

 One Dimensional Array
 Representation of an array in memory
 Formula to find the address of an element in an array
Address of A[Index] = B + W * (Index - LB)
 Where:
o Index = The index of the element whose address is to be found (not the
value of the element).
o B = Base address of the array.
o W = Storage size of one element in bytes.
o LB = Lower bound of the index (if not
specified, assume zero).

Prepared By: Dr. Dhruti Sharma, IT, SCET

 Two Dimensional Array
 Two dimensional arrays are also called table or matrix.
 Two dimensional arrays have two subscripts
o Column major order matrix: Two dimensional array in which
elements are stored column by column is called as column major
matrix.
o Row major order matrix: Two dimensional array in which elements
are stored row by row is called as row major matrix

Prepared By: Dr. Dhruti Sharma, IT, SCET

 Column major order matrix
 Two dimensional array consisting of two rows and four columns
is stored sequentially by columns :
A[1,1], A[2,1], A[1,2], A[2,2], A[1,3], A[2,3], A[1,4], A[2,4]

Col-1 Col-2 Col-3 Col-4

Row 1 [1,1] [1,2] [1,3] [1,4]

Row 2 [2,1] [2,2] [2,3] [2,4]

Prepared By: Dr. Dhruti Sharma, IT, SCET

 Column major order matrix
 Two dimensional array consisting of two rows and four columns
is stored sequentially by columns :

Prepared By: Dr. Dhruti Sharma, IT, SCET

 Column major order matrix
 Ex: Given an array arr[1.........10][1.........15] with a base value
of 100 and the size of each element is 1 Byte in memory find
the address of arr[8][6] with the help of column-major order.

Prepared By: Dr. Dhruti Sharma, IT, SCET

 Row major order matrix
 Row major order matrix: Two dimensional array in which
elements are stored row by row is called as row major matrix.

b2 u2
b1 [1,1] [1,2] [1,3] [1,m]
[2,1] [2,2] [2,3] [2,m]

u1 [n,1] [n,2] [n,3] [n,m]

nXm

Prepared By: Dr. Dhruti Sharma, IT, SCET

 Row major order matrix
 Two dimensional array consisting of two rows and four columns
is stored sequentially by rows:

Prepared By: Dr. Dhruti Sharma, IT, SCET

 Row major order matrix
 Ex: Given an array, arr[1.........10][1.........15] with base
value 100 and the size of each element is 1 Byte in memory.
Find the address of arr[8][6] with the help of row-major order.

Prepared By: Dr. Dhruti Sharma, IT, SCET

 Applications of Array
 Matrix representation of polynomial equation
o 2-dimentional Array can be used to represent Polynomial equation.
o With this different operations such as addition, subtraction, division,
differentiation etc… are possible among polynomial equations.

Prepared By: Dr. Dhruti Sharma, IT, SCET

 Applications of Array
 Matrix representation of polynomial equation
Y Y2 Y3 Y4
X XY XY2 XY3 XY4
X2 X3 Y X2Y2 X2Y3 X2Y4
X3 X3 Y X3Y2 X3Y3 X3Y4
X4 X4 Y X4Y2 X4Y3 X4Y4
2X2 + 5XY + Y2 X2 + 3XY + Y2+Y-X
Y Y2 Y3 Y4 Y Y2 Y3 Y4
0 0 01 0 0 0 01 01 0 0
X 0 05 0 0 0 X 0
-1 3
0 0 0 0
X2 20 0 0 0 0 X2 10 0 0 0 0
X3 0 0 0 0 0 X3 0 0 0 0 0
X4 0 0 0 0 0 X4 0 0 0 0 0
Prepared By: Dr. Dhruti Sharma, IT, SCET
 Sparse matrix
 An m x n matrix is said to be sparse if “many” of its elements
are zero.
 A matrix that is not sparse is called a dense matrix.
 We can device a simple representation scheme whose space
requirement equals the size of the non-zero elements.
Column - 8
Column - 3

Column - 5

Column - 7
Column - 6
Column - 4
Column - 1
Column - 2

Row - 1 0 0 0 2 0 0 1 0 Terms 0 1 2 3 4 5 6 7 8
Row 1 1 2 2 2 3 3 4 4
Row - 2 0 6 0 0 7 0 0 3
Column 4 7 2 5 8 4 6 2 3
Row - 3 0 0 0 9 0 8 0 0 Value 2 1 6 7 3 9 8 4 5
Row - 4 0 4 5 0 0 0 0 0
Linear Representation of given matrix
4x8
Prepared By: Dr. Dhruti Sharma, IT, SCET
 Sparse matrix
 To construct matrix structure from liner representation we need
to record.
o Original row and columns of each non zero entries.
o Number of rows and columns in the matrix.
 So each element of the array into which the sparse matrix is
mapped need to have three fields: row, column and value.

Prepared By: Dr. Dhruti Sharma, IT, SCET

 1 2 3 4
Sparse matrix (Cont..)
5 6 7
Linear representation of Matrix
1 0 0 6 0 9 0 0
Row Column A
2 2 0 0 7 8 0 4
1 3 6
A = 3 10 0 0 0 0 0 0
4 0 0 12 0 0 0 0 1 5 9
5 0 0 0 0 0 0 0 2 1 2
6 0 0 0 3 0 0 5 2 4 7
6x7
2 5 8
Memory Space required to store 4
2 7
6x7 matrix
3 1 10
42 x 2 = 84 bytes
4 3 12
6 4 3
Memory Space required to store
Linear Representation 6 7 5

30 x 2 = 60 bytes Space Saved = 84 – 60 = 24 bytes

Prepared By: Dr. Dhruti Sharma, IT, SCET
 Sparse matrix (Cont..)
Linear Representation of Matrix Efficient Linear Representation of Matrix
Row Column A Column A
1 3 6 1 3 6
1 5 9 2 5 9
Row
2 1 2 3 1 2
1 1
2 4 7 4 4 7
2 3
2 5 8 5 5 8
3 7
2 7 4 6 7 4
4 8
3 1 10 7 1 10
5 0
4 3 12 8 3 12
6 9
6 4 3 9 4 3
6 7 5 10 7 5

Memory Space required to store Liner Representation = 26 x 2 = 52 bytes

 End of Part-1 of Ch-2
 

Prepared By: Dr. Dhruti Sharma, IT, SCET