2

Array

Chapter 2
DATA STRUCTURES
Way of organizing data in computer memory so that the memory can be
efficiently used in terms of both time and space.

Operations on data structures:

1) Traversal: Visiting each element in the list

2) Search: Finding the location of an element with a given value of the
record with a given key.
3) Insertion: Adding a new element to the list.
4) Deletion: Removing an element from the list.
5) Sorting: Arranging the elements.
6) Merging: Combining two lists into one.

Types of data structures:

Array

95
Chapter 2

Linear data structure:

A Linear relationship between the elements is represented by means of
contiguous memory locations. Another way of representing this linear
relationship is by using pointers or linked list.
E.g. Array, stack, queue, linked list

Non–linear data structures:

Non–linear data structures are not arranged sequentially in the memory.
The elements in non–linear data structures cannot be traversed in a single
run. Although they are more memory efficient than linear data structures.
E.g. graphs, trees.

Abstract data type (ADT):

y It is a class or datatype whose objects are defined by a set of values
and a set of operations
y Combining data structure with its operation

Previous Years’ Question\

Array

96
 Chapter 2
2.1 BASICS OF ARRAY
Introduction:
y An array is a collection of similar types of data items.
y Each data item is called an element of an array
y Often referred to as homogeneous collection of data elements.
y The datatype of elements may be any valid data type like char, int or
float.
y The elements of the an array share same variable name, but each
variable has a different index number. This index number is called the
subscript.
Syntax: datatype array_name [Size];
E.g. int arr[10]; //represents an array of 10 elements each of integer datatype.
y The array index starts from 0 in C language; hence arr[0] represents the
first element of the array.

Array

97
Chapter 2

y One disadvantage of arrays is that they have fixed sizes. Once an array
is
declared, its size cannot be changed. This is due to static memory allocation.

Rack Your Brain

Properties of array:
1) A one-dimensional array is a linear data structure which is used to store
similar types of elements.
2) The two basic operations that access an array are:
  i) Extraction operation: It is a function that accepts an array ‘a’ and an
index ‘i’ and returns an element of the array.
  ii) Storing operation: It accepts an array ‘a’, an index ‘i’ and an element
‘x’.
Array

98
 Chapter 2
3) The smallest element of an array’s index is called the lower bound. In C
lower bound is always 0.
4) The highest element is called the upper bound and is usually one less
than the number of elements.
5) The number of elements in the array is called range.

E.g. An array ‘a’ whose lower bound is ‘0’ and the upper bound is 99, then
the range would be
⇒ 99–0+1
⇒ 100
6) Array elements are stored at subsequent memory locations
7) 2-D arrays are by default stored in row- major order.
8) In C Programming, the lowest index of a 1-D array is always zero, while
the upper index is the size of the array minus one.
9) Array name represents the base address of the array.
10) Only constants and literal values can be assigned as a value of a number
of elements.

E.g.

Different types of array:

1–D arrays
y One–dimensional array is used when it is necessary to keep a large
number of items in memory and reference all the items in a uniform
manner.
Syntax: int b[100];
y This declaration reserves 100 successive memory locations, each
containing a single integer value.
y The address of the first location is called the base address and denoted
by base(b).
y The size of each element be w then address of an element i in an array
b is given as:
Array

99
Chapter 2

Rack Your Brain

E.g. Program to print the average of 100 integers and how much each
deviates from the average.
#include <stdio.h>
#define Num 100
average( )
{ int n[Num];
int i ; int total = 0;
float avg, diff;
for (i = 0; i < Num ; i++)
{ scanf(“ %d”, & n[i]);
total + = n[i];
}
avg = total/Num ;
printf(“Number difference”);
for (i = 0; i < Num ; i++)
{
diff = n[i] – avg;
printf (“\n %d %f”, n[i], diff);
}
Array

100
 Chapter 2
printf (“\n average is: %f”, avg)};
main()
{ average();
}

2–D arrays
y A 2–dimensional array is a logical data structure helpful in solving
problems.
Syntax: int a[3][5];
here [3] is the number of rows, and [5] is the number of columns.
y This represents a new array containing 3 elements. Each of these
elements in itself is an array containing five integers.
y The 2–D array has 2–indices called row and column.
y The number of rows or columns is called the range of the dimension.
Array

101
Chapter 2

y The arrays are, by default stored in row- major order. i.e. the first row
of the array occupies the first set of memory locations, the second row
occupies the next set so on and so forth.

Accessing element a[i][j] from a 2–D array a[m][n] then,

(Here, starting index of array is 0)
Row–major order:
a[i][j] = base(a) + (i*n + j) *w
Column–major order:
a[i][j] = base(a) + (i + j * m) *w
Where:
m : no. of rows
n : no. of columns
w : element size
base (a): base address of array a[m][n]
Array

102
 Chapter 2
Initialization of 2D arrays
y One can initialize a 2–D array in the form of a matrix.
E.g. int a[2][3] = { {0, 0, 0},
{1, 1, 1} };

y When the array is completely initialized with all the values, then we do
not need to specify the size of the first dimension.
E.g. int a[ ][3] = { {0, 0, 3},
{1, 1, 1} };

Array

103
Chapter 2

Multi–dimensional arrays
y Arrays with more than two dimensions
Syntax: int a[3][2][4] ;// 3–D array

y The first subscript specifies the plane number, the second specifies the
row number, and the third specifies the column number.
int a[p][m][n] ;
p : Plane number
m : row number
n : column number
E.g. a[3][2][4] ;
no. of plane = 3
no. of rows = 2
no. of columns = 4
Array

104
 Chapter 2
2.2 ACCESS ELEMENT
1–D array:

y Let the base address of an array a be b and the lower bound be

represented as L.B, and this size of each element be w.
y Then the address of Kth element of an array a is given as:

y If array indexing starts from 0 then:

SOLVED EXAMPLES

Sol: Given,
base address (b) = 200
size of each element (w) = 4 bytes

since L.B not given, it is by default 0. Here the fifth element refers to the element
at array index 4
fifth element = a[4]
∴ K=4
a[K] = b+ K *w
a[4] = 200 + 4 * 4
a[4] = 216
Array

105
Chapter 2

Sol:
Given,
array : A[–7....7]
W = 4 bytes
b = 3000
no. of elements = U.B – L.B + 1
= 7 – (–7) + 1
= 14 + 1
= 15
∴ A[K] = b+[(K–L.B)] *w
A[0] = 3000 + [(0–(–7))] *4
= 3000 + 28
A[0] = 3028
OR
Since: A[–7....7] = A[0.....14]
∴ A[0] = A[0–(–7)]
A[0] = A[7]
∴ A[7] = b + K*w
= 3000 + 7*4
A[7] = 3028

Previous Years’ Question (GATE 2005: 2-Mark)

Rack Your Brain

Array

106
 Chapter 2
2–D array:
Two ways of array implementation

Row major order

Let an array A[m][n], then address of element A[i][j] in row major order is
given by:

when: A[0.....m–1] [0........n–1]

when: A[1.....m] [1......n]

Similarly:
A[L1......U1] [L2.....U2]
then:
A[i][j] = b+[(U2–L2+1) (i–L1) + (j–L2)] *w
Where:
L1 : lower bound of rows
U1 : upper bound of rows
L2 : lower bound of columns
U2 : upper bound of columns

SOLVED EXAMPLES

Sol: given,
A[11][17] which is A[5.....15, –8.....8]
m = 11 //no. of rows
n = 17 //no. of columns
b = 500, w = 3 bytes
or
L1 = 5, L2 = –8
U1 = 15, U2 = 8
Array

107
Chapter 2

i.e. A[8][5] = A[8–(5)] [5–(–8)]

≈ A[3][13]
A[i][j] = b + (i*n + j) *w
A[3][13] = 500 + (3 * 17 + 13) * 3
= 500 + 192
A[3][13] = 692
or
A[8][5] = b + [(U2–L2 + 1) (i–L1) + (j–L2)] *w
= 500 + [(8–(–8)+1) (8–5) + (5–(–8))] *3
= 500 + [17 × 3 + 13] *3
= 500 + 192
A[8][5] = 692

Sol: Given,

1st Approach:

A[i][j] = b + [(U2–L2+1) (i–L1) + (j–L2)] *w

A[5][6] = 2000 + [(13–3+1) (5–1(–5)) + (6–3)] *4
= 2000 + [(10×11)+3] *4
= 2000 + 452
A[5][6] = 2452
2nd Approach:
Arr[0.....10, 0......10]
Array

108
 Chapter 2
A[5][6] ≈ [5–1(–5)] [6–3]
≈ A[10] [3]
A[10][3] = b + (i*n + j) *w
= 2000 + ((10×11)+3) *4
= 2000 + 452
A[10][3] = 2452

Previous Years’ Question (GATE 2000: 1-Mark)

Previous Years’ Question (GATE 2014 : 1-Mark)

Array

109
Chapter 2

Previous Years’ Question (GATE 2015 Set-2 : 2-Marks)

Previous Years’ Question (GATE 1998 : 2-Marks)

Column–major order
Let any array A[m][n] then address of element A[i][j] in column major order
is given by:

when: A[0......m–1] [0......n–1]

when: A[1....m] [1......n]

Array

110
 Chapter 2
Similarly: A[L1.....U1] [L2.......U2]
then:

where:
L1 : Lower bound of rows
U1 : Upper bound of rows
L2 : Lower bound of columns
U2 : Upper bond of columns

Rack Your Brain

SOLVED EXAMPLES

Sol: Given,
A[20][30] stored in column major order
w = 4 bytes
b = 100
A[5][15] = ?
A[i][j] = b+ (i + j * m) *w
A[5][15] = 100 + (5 + 15×20) *4
A[5][15] = 1320
Array

111
Chapter 2

Sol: Given,
A[–2....8] [–2.....5]
b = 5000
A[i][j] = b+[(i–L1) + (j–L2) (U1–L1+1)] *w
A[3][2] = 5000 + [(3–(–2)) + (2–(–2)) (8–(–2)+1)] *6
= 5000 + [5 + 44] *6
= 5000 + 294
A[3][2] = 5294
or
Convert A[–2....8] [–2.....5] to 0 indexing.
i.e. A[0....10] [0.....7] then A[3][2] also
maps to A[5][4] , m = 11, n = 8
\ A[5][4] = b+ (i + j *m) *w
= 5000 + (5 + 4×11) * 6
= 5000 + 294
A[5][4] = 5294

Multi–dimensional arrays:
y In multi–dimensional structure the terms row and columns cannot be used, since there
are more than 2 dimensions.
\ Let a N–Dimensional array:
A[L1.....U1][L2.....U2][L3.....U3][L4.....U4]........[LN.....UN]
then location of A[i, j, k ......x] is given by:
= b + {(i–L1) [(U2–L2+1) (U3–L3+1) (U4–L4+1)......(UN–LN+1)]
+ (j–L2) [(U3–L3+1) (U2–L4+1)....(UN–LN+1)]
+ (k–L3) [(U4–L4+1) ..... (UN–LN+1)] ...... + (x–LN)} *w
3–D Array
Let a 3–D array A[L1....U1][L2.....U2] [L3.....U3]
then location of A[i][j][k] is given by:
A[i][j][k] = b + {(i–L1) [(U2–L2+1) (U1–L1+1)]
+ (j–L2) [(U1–L1+1)]
+ (k–L3)} *w
Array

112
 Chapter 2
SOLVED EXAMPLES

Sol: Given,

then:
A[i][j][k] = b+ {(i–L1) [(U2–L2+1) (U1–L1+1)]
+ (j–L2) [(U1–L1+1)]
+ (k–L3)} *w
A[6][2][5] = 100 + {(6–(2)) [(1–(–4)+1) (8–2+1)]
+ (2–(–4)) [(8–2+1)]
+ (5–6)} *4
= 100 + {(4*6*7) + (6*7) + (–1)} *4
= 100 + 836
A[6][2][5] = 936

Sparse matrices:
� Matrices with relatively high proportions of entries with zero are called
sparse matrices.
y There are two general n–square sparse matrices.

1) Triangular matrix
y For a square 2-D array, if all the elements beneath(above) principal
diagonal are zero, then the matrix is called as triangular matrix.
y If all elements beneath the principal diagonal are zero, then the
matrix is upper triangular.
y While for a square matrix, if all the elements above the main diagonal
are zero then matrix is upper triangular.

2) Tridiagonal Matrix
y For a square matrix, if all the elements are zero except the elements
on the principal diagonal and all the elements immediately above
and immediately below the principal diagonal, then the matrix is
tridiagonal.
Array

113
Chapter 2

 1 0 0 0  1 5 8 10  1 5 0 0
5 2 0 0  0 2 6 9  8 2 6 0 
     
6 7 3 0  0 0 3 7  0 9 3 7 
     
8 9 10 4  4×4 0 0 0 4  4×4 0 0 10 4  4×4
Lower triangular Upper triangular Tridiagonal
matrix    matrix    matrix

Triangular matrices:

1) Lower Triangular Matrix , a[i][j]

Range n (n + 1 )
2

Row Major Order (RMO)  i (i − 1) 

b + ( j – 1 ) + *w
 2 

Column Major Order (CMO)   ( j − 1) ( j − 2)  

b + (i − j) + ( j − 1) n −  * w
  2  

2) Upper Triangular Matrix , a[i][j]

Range n (n + 1 )
2

Row Major Order (RMO)   (i − 1) (i − 2)  

b + ( j − i) + (i − 1) n −  * w
  2  
Array

114
 Chapter 2
Column Major Order (CMO)  j ( j − 1) 
b + ( i − 1 ) + *w
 2 

3) Strictly Lower Triangular Matrix [ ]nxn, a[i][j]

Range n (n − 1 )
2

Row Major Order (RMO)  (i − 1) (i − 2 ) 

b + ( j − 1 ) + *w
 2 

Column Major Order (CMO)  ( j − 1) ( j − 2 ) 

b + ( i − 1 ) + *w
 2 

Tridiagonal matrix [ ]nxn, a[i][j]

Range 3n–2

Row Major Order (RMO) b+ (2i+j–3) *w

Column Major Order (CMO) b+ (i+2j–3) *w

Rack Your Brain

Array

115
Array Chapter 2

�
�
�
�
�
�
�
�
�
�

116