12 PRINCIPLES OF DATA STRUCTURES USING C AND C++
1.13.3. SPARSE ARRAYS
Sparse array is an important application of arrays. A sparse array is an array where
nearly all of the elements have the same value (usually zero) and this value is a constant.
One-dimensional sparse array is called sparse vectors and two-dimensional sparse arrays
are called sparse matrix.
The main objective of using arrays is to minimize the memory space requirement
and to improve the execution speed of a program. This can be achieved by allocating
memory space for only non-zero elements.
For example a sparse array can be viewed as
0 0 8 0 0 0 0
0 1 0 0 0 9 0
0 0 0 3 0 0 0
0 31 0 0 0 4 0
0 0 0 0 7 0 0
Fig. 1.5. Sparse array
We will store only non-zero elements in the above sparse matrix because storing all
the elements of the sparse array will be consisting of memory sparse. The non-zero ele-
ments are stored in an array of the form.
A[0......n][1......3]
Where ‘n’ is the number of non-zero elements in the array. In the above Fig. 1.4 ‘n = 7’.
The space array given in Fig. 1.4 may be represented in the array A[0......7][1.....3].
A[0][1] A[0][2]
1 2 3
0 5 7 7
1 1 3 8
2 2 2 1
3 2 6 9
4 3 4 3
5 4 2 31
6 4 6 4
7 5 5 7
Fig. 1.6. Sparse array representation
The element A[0][1] and A[0][2] contain the number of rows and columns of the
sparse array. A[0][3] contains the total number of nonzero elements in the sparse array.
PROGRAMMING METHODOLOGIES 13
A[1][1] contains the number of the row where the first nonzero element is present in the
sparse array. A[1][2] contains the number of the column of the corresponding nonzero
element. A[1][3] contains the value of the nonzero element. In the Fig. 1.4, the first nonzero
element can be found at 1st row in 3rd column.
1.14. VECTORS
A vector is a one-dimensional ordered collection of numbers. Normally, a number of
contiguous memory locations are sequentially allocated to the vector. A vector size is fixed
and, therefore, requires a fixed number of memory locations. A vector can be a column
vector which represents a ‘n’ by 1 ordered collections, or a row vector which represents a
1 by ‘n’ ordered collections.
The column vector appears symbolically as follows :
A1
A
2
A = A3
M
A
n
A row vector appears symbolically as follows :
A = (A1, A2, A3, ...... An)
Vectors can contain either real or complex numbers. When they contain real num-
bers, they are sometime called real vectors. When they contain complex numbers, they are
called complex vectors.
1.15. LISTS
As we have discussed, an array is an ordered set, which consist of a fixed number of
elements. No deletion or insertion operations are performed on arrays. Another main dis-
advantage is its fixed length; we cannot add elements to the array. Lists overcome all the
above limitations. A list is an ordered set consisting of a varying number of elements to
which insertion and deletion can be made. A list represented by displaying the relation-
ship between the adjacent elements is said to be a linear list. Any other list is said to be
non linear. List can be implemented by using pointers. Each element is referred to as
nodes; therefore a list can be defined as a collection of nodes as shown below :
Head
x
Fig. 1.7
