Shashank Yadav (KIET-Ghaziabad)
6. Arrays:
6.1 Linear Array:
The simplest type of data structure is a linear array.
A linear array is a list of a finite number n of homogeneous data elements such that
The elements of the array are referenced respectively by an index set consisting of
n consecutive numbers.
The elements of the array are stored respectively in successive memory locations.
The number n of elements is called the length or size of the array.
The elements of A are denoted by any subscript notation as given below.
a1, a2, a3, …, an
A(1), A(2), A(3),…, A(N)
A[1], A[2], A[3], … , A[N]
The number K in A[K] is called a subscript. A[K] is called subscripted
variable.
In general, the length of the array can be obtained from the index set by the formula
Length= UB- LB +1
UB- Largest index (Upper Bound)
LB- Smallest index (Lower Bound)
The formula for finding out address of Kth element of array in memory.
LOC (LA[K]) = Base(LA) + w(K- LB)
LA Linear Array
LOC(LA[K]) Address of the element LA[K] of the array LA in memory
w the number of words per memory cell for array LA
6.2 Traversing Linear Array:
Let A is an array of data elements. If we want to print all numbers of array A or to count the
numbers of elements of A, we have to traverse all elements.
TRAVERSE(LA, LB, UB)
Where LA is Linear Array with Lower Bound LB and Upper Bound UB.
1. for k= LB to UB do
2. Apply PROCESS to LA
3. Exit.
6.3 Inserting and Deleting:
INSERT(LA, N, K, ITEM)
8|Page
Shashank Yadav (KIET-Ghaziabad)
Where LA is linear array of N elements, K is a positive integer such that K<=N, and
ITEM is an element to be inserted into array.
1. for J=N down to K do
2. LA[J+1]= LA[J]
3. LA[K]=ITEM
4. N=N+1
5. Exit.
Time Complexity:-
Best Case- When the ITEM is inserted at last (Nth) position. In this case 1st statement will be
executed only two times.
T(n)= O(1)
Worst Case- When the ITEM is inserted at first position. In this case 1st statement will be
executed N+1 times.
T(n)= O(n)
DELETE(LA, N, K)
Where LA is linear array of N elements, K is positive number such that K<=N.
1. for J= K to N-1 do
2. A[J]=A[J+1]
3. N=N-1
4. Exit.
Time Complexity:-
Best Case- When we want to delete last (Nth) position. In this case 1st statement will be executed
only one time.
T(n)= O(1)
Worst Case- When we want to delete first element. In this case 1st statement will be executed N
times.
T(n)= O(n)
6.4 Multidimensional Arrays:
In linear array, each element is referenced by a single subscript. Most programming languages
allow two-dimensional and three-dimensional arrays, i.e. where elements are referenced,
respectively, by two and three subscripts.
6.4.1 Two-Dimensional Arrays:
9|Page
Shashank Yadav (KIET-Ghaziabad)
A two-dimensional m x n array A is a collection of m . n data elements such that each
element is specified by a pair of integers (such as J, K), called subscripts, with the
following property that,
1 < = J < = m and 1 <= K <= n
The element of A with first subscripts J and second subscript K will be denoted by
A J,K or A[J, K] or A[J][K]
Two-dimensional arrays are called matrices in mathematics and tables in business
applications; hence two-dimensional arrays are sometimes called matrix arrays.
Columns
1 2 3 4
1 A[1,1] A[1,2] A[1,3] A[1,4]
Rows 2 A[2,1] A[2,2] A[2,3] A[2,4]
3 A[3,1] A[3,2] A[3,3] A[3,4]
Fig: Two-dimensional 3*4 array A
6.4.2 Representation of Two-Dimensional Arrays in Memory:
Let A be a two-dimensional m*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
of m.n sequential memory locations.
Specially, the programming language will store the array A by two orders
1. Column major order
2. Row major order
A Subscript A Subscript
(1,1) (1,1)
(2,1) (1,2)
(3,1) (1,3)
(1,2) (1,4)
(2,2) (2,1)
(3,2) (2,2)
(1,3) (2,3)
(2,3) (2,4)
(3,3) (3,1)
(1,4) (3,2)
(2,4) (3,3)
(3,4) (3,4)
[Link]-major
order [Link]-major order
10 | P a g e
Shashank Yadav (KIET-Ghaziabad)
Formula for finding out address of A[J][K] element (first element of array is stored at
location (1,1)).
(Column-major order) LOC (A[J][K])= Base(A) +w[M(K-1) + (J-1)]
(Row-major order) LOC (A[J][K])= Base(A) +w[N(J-1) + (K-1)]
Where M is the number of rows, and N is the number of columns.
w denotes the numbers of words per memory location for array A.
General formula for finding out address of A[J][K] element
(Column-major order) LOC (A[J][K])= Base(A) +w[M(K-Lc) + (J-Lr)]
(Row-major order) LOC (A[J][K])= Base(A) +w[N(J-Lr) + (K-Lc)]
Where Lr = Lower limit of row/first row index of the matrix,
Lc = Lower limit of column/first column index of the matrix,
Where M is the number of rows, and N is the number of columns.
w denotes the numbers of words per memory location for array A
6.4.3 Multidimensional Array:
A 3-Dimensional array is a collection of 2-Dimensional arrays. It is specified by using three
subscripts:
1. Block size
2. Row size
3. Column size
To find the address of any element in 3-Dimensional arrays there are the following two ways-
Row Major Order
Column Major Order
11 | P a g e
Shashank Yadav (KIET-Ghaziabad)
1. Row Major Order:
To find the address of the element using row-major order, use the following formula:
Address of A[i][j][k] = B + W *(P* N * (i-x) + P*(j-y) + (k-z))
Here:
B = Base Address (start address)
W = Weight (storage size of one element stored in the array)
M = Row (total number of rows)
N = Column (total number of columns)
P = Width (total number of cells depth-wise)
x = Lower Bound of Row
y = Lower Bound of Column
z = Lower Bound of Width
2. Column Major Order:
To find the address of the element using column-major order, use the following formula:1
Address of A[i][j][k]= B + W(M * N(i – x) + M *(k – z) + (j – y))
Here:
B = Base Address (start address)
W = Weight (storage size of one element stored in the array)
M = Row (total number of rows)
N = Column (total number of columns)
P = Width (total number of cells depth-wise)
x = Lower Bound of block (first subscipt)
y = Lower Bound of Row
z = Lower Bound of Column
1. Write an algorithm for searching an element in an array. (Linear Search)
LINEAR-SEARCH(A, N, ITEM)
Where A is an array of N elements, ITEM is to be searched.
1. for I=1 to N do
2. if (A[I]== ITEM) then
3. Write(ITEM is found)
4. goto step (5)
5. if (I== N+1) then
6. Write (ITEM is not found)
Time Complexity:-
Best Case- If the ITEM is at first position. At this case,
T(n)= O(1)
12 | P a g e
Shashank Yadav (KIET-Ghaziabad)
Worst Case- If the ITEM is at last position or ITEM is not present in the array.
T(n)= O(n)
2. Write an algorithm for deleting an element which value is given.
DELETE(A, N, ITEM)
Where A is an array of N elements, ITEM is for deleting from array.
1. for I=1 to N do
2. if (A[I]== ITEM) then
3. for J= I to N-1 do
4. A[J]=A[J+1]
5. N=N-1
6. goto step (7)
7. if (I== N+1) then
8. Write (ITEM is not present in the array)
Time Complexity: In all cases the time complexity of this algorithm is
T(n)= O(n)
3. Write an algorithm for multiplication of two matrices.
MATRIX-MULTIPLY (A, B, M, N, P)
Where A is matrix of order M*N, B is matrix of N*P.
1. Take one output matrix C of order M*P
2. for I=1 to M do
3. for J=1 to P do
4. total=0
5. for K=1 to N do
6. total=total+ A[I][K]*B[K][J]
7. C[I][J]=total
8. Exit
Time complexity:- The complexity of a matrix multiplication algorithm is measured by counting
the numbers of multiplications. The reason that additions are not counted in such algorithms is
that computer multiplications take more time than computer addition. The complexity of the
algorithm is
T(n)= O(M.N.P)
4. Write a C program for searching a number in an array (Linear Search).
#include<stdio.h>
void main()
13 | P a g e
Shashank Yadav (KIET-Ghaziabad)
{
int A[50], i, n, num;
printf(“Enter the number of elements in array : ”);
scanf(“%d”,&n);
printf(“Enter %d numbers: ”,n);
for(i=0;i<n;i++)
{
scanf(“%d”,&A[i]);
}
printf(“\n Enter number do you want to search in array:”);
scanf(“%d”,&num);
for(i=0;i<n;i++)
{
if(A[i]==num)
{
printf(“\n Number is found”);
break;
}
}
if(i==n)
printf(“\n Number is not found.”);
}
Output:
How many numbers do you want in array: 5
Enter 5 numbers: 4 6 7 8 9
Enter number do you want to search in array: 8
Number is found.
5. Write a C program for Insertion Sort.
#include<stdio.h>
void main()
{
int A[30], n, key, i, j;
printf("How many numbers do you want to sort by Insertion Sort:");
scanf("%d",&n);
printf("\n Enter %d numbers: ",n);
for(i=0;i<n;i++)
scanf("%d",&A[i]);
14 | P a g e
Shashank Yadav (KIET-Ghaziabad)
for(j=1;j<n;j++)
{
key=A[j];
i=j-1;
while(i>-1 && A[i]>key)
{
A[i+1]=A[i];
i=i-1;
}
A[i+1]=key;
}
printf("\n Sorted array is \n");
for(i=0;i<n;i++)
printf("%d ",A[i]);
Output:
How many numbers do you want to sort by Insertion Sort: 10
Enter 10 numbers: 2 10 9 8 4 3 1 7 5 6
Sorted array is
1 2 3 4 5 6 7 8 9 10
6. Write a Program in C for multiplication of two matrices A and B.
#include<stdio.h>
#define M 3 //rows of 1st matrix
#define N 2 // columns of 1st matrix and rows of 2nd matrix
#define P 3 //columns of 2nd matrix
void main()
{
int A[M][N], B[N][P], C[M][P];
int i, j, k, total;
printf(“\nEnter %d numbers for 1st matrix ”, M*N);
for(i=0;i<M;i++)
{
for(j=0;j<N;j++)
{
scanf(“%d”, &A[i][j]);
}
}
15 | P a g e
Shashank Yadav (KIET-Ghaziabad)
printf(“\nEnter %d numbers for 2nd matrix”, N*P);
for(i=0;i<N;i++)
{
for(j=0;j<P;j++)
{
scanf(“%d”, &B[i][j]);
}
}
for(i=0;i<M;i++)
{
for(j=0;j<P;j++)
{
total=0;
for(k=0;k<N;k++)
{
total= total + A[i][k] * B[k][j];
}
C[i][j]=total;
}
}
printf(“\n Multiplication of matrix A and B is \n”);
for(i=0;i<M; i++)
{
for(j=0;j<P; j++)
{
printf(“%d\t ”, C[i][j]);
}
printf(“\n”);
}
}
Output:
Enter 6 numbers for 1st Matrix 1 2 3 4 5 6
Enter 6 numbers for 2nd Matrix 2 4 5 6 1 3
Multiplication of Matrix A and B is
14 6 11
30 16 27
46 26 43
6.5 Sparse Matrix:
16 | P a g e
Shashank Yadav (KIET-Ghaziabad)
If a lot of elements from a matrix have a value 0 then matrix is known as a sparse matrix.
There is no precise definition of when a matrix is sparse and when it is not.
If the matrix is sparse we must consider an alternate way of representing it rather than the
normal row major or column major arrangement.
A 1 2 3 4 5
1 2 0 1 0 0
2 0 0 0 6 0
3 0 3 0 0 5
4 9 0 0 3 0
5 0 7 0 0 8
Sparse Matrix of order 5*5
Two general types of n-square sparse matrices, which occur in various applications. The
first matrix, where non-zero entries can only occur on or below the main diagonal, is
called lower triangular matrix. The second matrix, where non-zero entries can only occur
on the diagonal or on elements immediately above or below the diagonal, is called a tri-
diagonal matrix.
1 2 3 4 5
1 4
2 3 -5
3 1 0 6
4 -7 8 -1 3
5 5 -2 0 2 -8
(a) Triangular matrix
1 2 3 4 5 6 7
1 5 -3
2 1 4 3
3 9 -3 6
4 2 4 -7
5 3 -1 0
6 6 -5 8
7 3 -1
(b) Tri-diagonal Matrix
A common way of representing non-zero elements of a sparse matrix is 3-tuple forms. In
this form each non-zero element is stored in a row, with the 1st and 2nd element of this
row containing the row and column in which the element is present in the original matrix.
The 3rd element in this row stores the actual value of the non-zero element. First row
17 | P a g e
Shashank Yadav (KIET-Ghaziabad)
contains total rows, columns, and total elements. Therefore, matrix A can be converted
into following form.
row col Element
1 2 3
1 5 5 9
2 1 1 2
3 1 3 1
4 2 4 6
5 3 2 3
6 3 5 5
7 4 1 9
8 4 4 3
9 5 2 7
10 5 5 8
6.5.1 Algorithm for converting simple matrix into sparse matrix.
CONVERT-SPARSE (ARRAY, SPARSE, M, N)
Where ARRAY is matrix of M*N order, SPARSE is the sparse
representation of M*N matrix.
1. SPARSE [1][1]= M
2. SPARSE [1][2]=N
3. C=2
4. for I=1 to M do
5. for J=1 to N do
6. If ARRAY [I][J] != 0 then
7. SPARSE[C][1]= I
8. SPARSE[C][2]= J
9. SPARSE[C][3]= ARRAY[I][J]
10. C=C+1
11. SPARSE [1][3]=C-1
12. Return.
6.5.2 Addition of two sparse Matrices.
18 | P a g e
Shashank Yadav (KIET-Ghaziabad)
A Matrix A Sparse Matrix
1 2 3 4 5 1 2 3
1 0 0 0 0 1 1 4 5 3
2 0 2 0 0 0 2 1 5 1
3 0 0 0 0 0 3 2 2 2
4 0 0 0 3 0 4 4 4 3
B Matrix B Sparse Matrix
1 2 3 4 5 1 2 3
1 0 0 0 0 0 1 4 5 3
2 0 4 0 0 0 2 2 2 4
3 0 0 5 0 0 3 3 3 5
4 0 0 0 0 3 4 4 5 3
Addition of A and
B Addition of A and B
1 2 3 4 5 1 2 3
1 0 0 0 0 1 1 4 5 5
2 0 6 0 0 0 2 1 5 1
3 0 0 5 0 0 3 2 2 6
4 0 0 0 3 3 4 3 3 5
5 4 4 3
6 4 5 3
19 | P a g e