Unit-2 Linear Data Structure-Array

 Outline:
• Definition of Array
• Types of Array
• Representation of Array
• Application of Array
• Sparse Matrix
Unit-2 Linear Data Structure-Array
 What is an Array?
• An array is a data structure that contains a group of elements.
• Typically these elements are all of the same data type, such as an integer or string.
• Arrays are commonly used in computer programs to organize data so that a related set
of values can be easily sorted or searched.
• An array is a collection of data items, all of the same type, accessed using a common
name.
 Types of Array:
1. One Dimensional
2. Two Dimensional
3. Multi Dimensional
Unit-2 Linear Data Structure-Array
 Types of Array:
1. One Dimensional Array:
• An array which store its elements into a single row is called one dimensional array.
• Syntax for Declare an Array
datatype ArrayName[Arraysize];
For Example: Float Mark[5];
• Here, we declared an array, mark, of floating-point type. And its size is 5. Meaning, it can
hold 5 floating-point values.
Unit-2 Linear Data Structure-Array
1. One Dimensional Array:
 How to Access Array Elements?
• You can access elements of an array by indices.
• Suppose you declared an array mark as above. The first element is mark[0], the second
element is mark[1] and so on.
• Arrays have 0 as the first index, not 1. In our example, mark[0] is the first element.
• If the size of an array is n, to access the last element, the n-1 index is used. In this
example, mark[4].
• Suppose the starting address of mark[0] is 2120. Then, the address of the mark[1] will be
2124. Similarly, the address of mark[2] will be 2128 and so on. This is because the size of
a float is 4 bytes.
Unit-2 Linear Data Structure-Array
1. One Dimensional Array:
 How to Initialize an Array?
• It is possible to initialize an array during declaration. For example,
int mark[5] = {19, 10, 8, 17, 9};

• Input and Output Array Element

• Here's how you can take input from the user and store it in an array element.
scanf("%d", &mark[2]); // take input and store it in the 3rd element
scanf("%d", &mark[i-1]); // take input and store it in the ith element
Unit-2 Linear Data Structure-Array
1. One Dimensional Array:
• Here's how you can print an individual element of an array.
printf("%d", mark[0]); // print the first element of the array
printf("%d", mark[2]); // print the third element of the array
printf("%d", mark[i-1]); // print ith element of the array
Unit-2 Linear Data Structure-Array
1. One Dimensional Array:
 Example: Array Input/output
#include<stdio.h>
void main()
{
int a[4];
int i, j;
printf("Enter array element:");
OUTPUT:
for(i = 0; i < 4; i++)
Enter array element:1
{ 5
scanf("%d", &a[i]); //Run time array initialization 2
} 3
printf(“Array elements are:");
for(j = 0; j < 4; j++) Array Elements are:1
5
{
2
printf("%d\n", a[j]); 3
}
}
Unit-2 Linear Data Structure-Array
 Types of Array:
2. Two Dimensional Array:
• C language supports multidimensional arrays also.
• The simplest form of a multidimensional array is the two-dimensional array.
• An array of arrays is known as 2D array.
• The two dimensional (2D) array in C programming is also known as matrix.
• A matrix can be represented as a table of rows and columns.
• Two-dimensional arrays are declared as follows,
data-type array-name[row-size][column-size] ;
For Example, float x[3][4];
• Here, x is a two-dimensional (2d) array. The array can hold 12 elements. You can think the
array as a table with 3 rows and each row has 4 columns.
Unit-2 Linear Data Structure-Array
 Types of Array:
2. Two Dimensional Array:

• Similarly, you can declare a three-dimensional (3d) array. For example,

float y[2][4][3];
• Here, the array y can hold 24 elements.
Unit-2 Linear Data Structure-Array
2. Two Dimensional Array:
 How to initialize 2D Array?
• Different ways to initialize two-dimensional array
i=0 j=0 : a[0][0]
int c[2][3] = {{1, 3, 0}, {-1, 5, 9}}; j=1 : a[0][1]
int c[][3] = {{1, 3, 0}, {-1, 5, 9}}; j=2 : a[[0][2]
j=3 : a[0][3]
int c[2][3] = {1, 3, 0, -1, 5, 9};
• Runtime initialization of a two dimensional Array i=1 j=0 :a[1][0]
Suppose array size is a[3][4] j=1 :a[1][1]
j=2 :a[1][2]
for(i = 0; i < 3;i++) j=3 :a[1][3]
{
i=2 j=0 :a[2][0]
for(j = 0; j < 4; j++) j=1 :a[2][1]
{ j=2 :a[2][2]
j=3 :a[2][3]
scanf("%d", &a[i][j]); i=3 condition false
}
}
Unit-2 Linear Data Structure-Array
2. Two Dimensional Array:
 Example: 2D Array Input/output
#include<stdio.h>
0 1 2 3
void main()
{
int arr[3][4];
int i, j, k; 0 5 10 15 20
printf("Enter array element");
for(i = 0; i < 3;i++)
{
for(j = 0; j < 4; j++) 1 25 30 35 40
{
scanf("%d", &arr[i][j]);
}
} 2 45 50 55 60
for(i = 0; i < 3; i++)
{
for(j = 0; j < 4; j++)
{ printf("%d", arr[i][j]);
}
}
}
Unit-2 Linear Data Structure-Array
Array Representation:
• The elements of a Two dimensional array can be arranged in two ways.
1. Row major Representation
2. Column major Representation
1.Row major Representation:
• If the elements are stored in row wise manner then it is called row major representation.
• If we want to store element 10,20,30,40,50,60,70,80 and if size of array is a[3][4] then,
0 1 2 3

0
10 20 30 40

1 50 60 70 80
2
Unit-2 Linear Data Structure-Array
Array Representation:
2.Column major Representation:
• If the elements are stored in column wise manner then it is called Column major
representation.
• If we want to store element 10,20,30,40,50,60,70,80 and if size of array is a[3][4] then,

0 1 2 3

0
10 40 70

1
20 50 80

2
30 60
Unit-2 Linear Data Structure-Array
Address calculation of Array Elements :
• You can calculate the address of any element which is stored in an array.
• To calculate the address of any element you must know,
1.Base Address(Address of first element(which is at index 0).
2.Data Types of Array(int(2bytes),Float(4 bytes)).
3.Size of Array.
4.Representation of array(Row major or Column Major)
5.index of element for which you want to find address.
6.Formula.
Unit-2 Linear Data Structure-Array
Address calculation of Array Elements :
Formula for Calculating Address:
Row Major System:
The address of a location in Row Major System is calculated using the following formula:
Address of A [ I ][ J ] = B + W * [ N * ( I – Lr ) + ( J – Lc ) ]
Column Major System:
The address of a location in Column Major System is calculated using the following formula:
Address of A [ I ][ J ] Column Major Wise = B + W * [( I – Lr ) + M * ( J – Lc )]
Where,
B = Base address(Address of First Element)
I = Row subscript of element whose address is to be found
J = Column subscript of element whose address is to be found
W = Storage Size of one element stored in the array (in byte)(Int=2 byte,Float=4 byte)
Lr = Lower limit of row/start row index of matrix, if not given assume 0 (zero)
Lc = Lower limit of column/start column index of matrix, if not given assume 0 (zero)
M = Number of row of the given matrix
N = Number of column of the given matrix
Unit-2 Linear Data Structure-Array
Address calculation of Array Elements :
Example 1:Consider an integer array int a[3][4].if the base address is 1050,find the
address of the element a[2][2] with row major and column major representation of
array.
Row Major System:
The address of a location in Row Major System is calculated using the following formula:
Address of A [ I ][ J ] = B + W * [ N * ( I – Lr ) + ( J – Lc ) ]
B = Base address(Address of First Element)=1050
I = Row subscript of element whose address is to be found=2
J = Column subscript of element whose address is to be found=2
W = Storage Size of one element stored in the array =2 bytes(because datatype is int).
Lr = Lower limit of row/start row index of matrix, if not given assume 0 (zero)=0
Lc = Lower limit of column/start column index of matrix, if not given assume 0 (zero)=0
M = Number of row of the given matrix=3
N = Number of column of the given matrix=4
Unit-2 Linear Data Structure-Array
Address calculation of Array Elements :
Example 1:Consider an integer array int a[3][4].if the base address is 1050,find the
address of the element a[2][2] with row major and column major representation of
array.
Row Major System:
The address of a location in Row Major System is calculated using the following formula:
Address of A [ I ][ J ] = B + W * [ N * ( I – Lr ) + ( J – Lc ) ]
A [ 2 ][ 2 ] = 1050 + 2 * [ 4 * ( 2 – 0 ) + ( 2 – 0) ]
= 1070 0 1 2 3

0 1050 1052 1054 1056

1 1058 1060 1062 1064

2 1066 1068 ?(1070)

Unit-2 Linear Data Structure-Array
Address calculation of Array Elements :
Example 1:Consider an integer array int a[3][4].if the base address is 1050,find the
address of the element a[2][2] with row major and column major representation of
array.
Column Major System:
The address of a location in Column Major System is calculated using the following formula:
Address of A [ I ][ J ] Column Major Wise = B + W * [( I – Lr ) + M * ( J – Lc )]
A [ 2 ][ 2 ] = 1050 + 2 * [ ( 2 – 0 ) + 3*( 2 – 0) ]
= 1050+16 0 1 2 3
= 1066 0 1050 1056 1062

1 1052 1058 1064

2 1054 1060 ?(1066)

Unit-2 Linear Data Structure-Array
Address calculation of Array Elements :
Example 2:A 2-D array defined as A[r, c] where 1 ≤ r ≤ 4, 5≤ c ≤ 8, requires 2 bytes of memory for
each element. If the array is stored in Row-major order form, calculate the address of A[3,7]
given the Base address as 2000
Size of Array A[1:4][5:8}
Row Major System:
The address of a location in Row Major System is calculated using the following formula:
Address of A [ I ][ J ] = B + W * [ N * ( I – Lr ) + ( J – Lc ) ]
B=2000 =2000 + 2[ 4*(3-1) +( 7-5)
5 6 7 8
W=2 byte =2000 + 2*10
I=3 =2000+20 1 2000 20002 2004 2006
J=7 =2020
2 2008 2010 2012 2014
Lr=1
Lc=5 3 2016 2018 ?(2020)
M=4
N= 4 4
Unit-2 Linear Data Structure-Array
Address calculation of Array Elements :
Example 2:A 2-D array defined as A[r, c] where 1 ≤ r ≤ 4, 5≤ c ≤ 8, requires 2 bytes of memory for
each element. If the array is stored in Row-major order form, calculate the address of A[3,7]
given the Base address as 2000
Size of Array A[1:4][5:8}
Column Major System:
The address of a location in Column Major System is calculated using the following formula:
Address of A [ I ][ J ] Column Major Wise = B + W * [( I – Lr ) + M * ( J – Lc )]
B=2000 =2000 + 2[ (3-1) +4*( 7-5)
5 6 7 8
W=2 byte =2000 + 2*10
I=3 =2000+20 1 2000 2008 2016
J=7 =2020
2 2002 2010 2018
Lr=1
Lc=5 3 2004 2012 ?(2020)
M=4
N= 4 4 2006 2014
Unit-2 Linear Data Structure-Array
Address calculation of Array Elements :
Example 3:Given a two dimensional array Z1(2:9, 9:18) stored in column-major order with base
address 100 and size of each element is 4 bytes, find address of the element Z1(4, 12).
Size of Array A[2:9][9:18]
Column Major System:
The address of a location in Column Major System is calculated using the following formula:
Address of A [ I ][ J ] Column Major Wise = B + W * [( I – Lr ) + M * ( J – Lc )]
B=100 =100 + 4[ (4-2) +8*( 12-9) 9 10 11 12 13 14 15 16 17 18
W=4 byte =100 + 4[2+8*3] 100 132 164 196
2
I=4 =100+4*26 104 136 168 200
3
J=12 =100+104 108 140 172 ?204
4
Lr=2 =204 112 144 176
5
Lc=9
116 148 180
M=8(9-2+1) 6
120 152 184
N= 10(18-9+1) 7
124 156 188
8
128 160 192
9
Unit-2 Linear Data Structure-Array
Address calculation of Array Elements :
Example 3:Given a two dimensional array Z1(2:9, 9:18) stored in column-major order with base
address 100 and size of each element is 4 bytes, find address of the element Z1(4, 12).
Size of Array A[2:9][9:18]
Row Major System:
The address of a location in Row Major System is calculated using the following formula:
Address of A [ I ][ J ] = B + W * [ N * ( I – Lr ) + ( J – Lc ) ]
B=100 =100 + 4[ 10(4-2) +( 12-9) 9 10 11 12 13 14 15 16 17 18
W=4 byte =100 + 4[20+3] 100 104 108 112 116 120 124 128 132 136
2
I=4 =100+4*23 140 144 148 152 156 160 164 168 172 176
3
J=12 =100+92 180 184 188 ?192
4
Lr=2 =192
5
Lc=9
M=8(9-2+1) 6

N= 10(18-9+1) 7
8
9
Unit-2 Linear Data Structure-Array
 Applications of Array:
• Array are used for representing some sequential data structures such as stack and
queues.
• Array are used to represent sparse matrices.
• Array are widely used to implement mathematical vector, matrices and other kind of
tables.
• Array can be used for sorting elements in ascending or descending order.
• It is used in every possible situation where you need to gather similar objects at one
place.
• Arrays are used to implement Search Algorithms.
• Arrays are also used to implement CPU Scheduling Algorithms.
Unit-2 Linear Data Structure-Array
 Sparse Matrix:
• Sparse matrix is a matrix which contains very few non-zero elements.
• A matrix that is not sparse is called dense matrix.
• Normally matrices are represent in a two dimensional array.
• In a matrix if there are m rows and n columns then the space required to store the
numbers will be m*n*s where s is the number of bytes required to store the value.
• Suppose, there are 10 rows and 10 columns and we have to store the integer values then
space complexity will be 10*10*2 =200 bytes.
• For example, if the matrix is of size 10*10 and only 10 elements are non zero. Then for
accessing 10 elements one has to make 100 times scan.
• Also only 10 spaces will be with non-zero elements, remaining spaces of matrix will be
filled with zeros only.
• The concept of sparse matrix has therefore came forward to investigate that
representation will store only non-zero elements of the matrix and still carry out the
operations quite efficiently.
Unit-2 Linear Data Structure-Array
 Sparse Matrix Representation:
• Representation of sparse matrix will be a triplet only.
• Sparse matrix means very few non-zero elements having in it.
• Rest of the spaces are having the values zero which are basically useless values.
• So in this efficient representation we will consider all the non-zero values along with
their positions.
• For example –Suppose a matrix is 6 * 7 and the number of non-zero values are say 8.
0 1 2 3 4 5 6
0 0 0 0 0 0 0 -10
1 55 0 0 0 0 0 0
2 0 0 0 0 0 -23 0
3 0 67 0 0 0 0 88
4 0 0 0 14 -28 0 0
5 99 0 0 0 0 0 0
Unit-2 Linear Data Structure-Array
 Sparse Matrix Representation:
• In normal representation of the matrix this will take 6 * 7 *2 =84 bytes.
• In row wise representation of sparse matrix the 0th rows will store total rows of the matrix, total column of
the matrix, and the total non-zero values.
index Row No Column No Value

0 6 7 8

1 0 6 -10

2 1 0 55

3 2 5 -23

4 3 1 67

5 3 6 88

6 4 3 14

7 4 4 -28

8 5 0 99
Unit-2 Linear Data Structure-Array
 Sparse Matrix Representation:
• In normal representation of the matrix this will take 6 * 7 *2 =84 bytes.
• In sparse matrix representation (total no of non-zero values +1) * 3 * 2 bytes .
• So it will be ( 8 + 1) * 3 * 2 = 54 Bytes.
• Clearly in normal representation 30 bytes is unused space, which are saving in the sparse matrix
representation.