Data Structure Using C & C++ (BCA-302)

UNIT-I

Data Structures

Data Structure is a way to store and organize data so that it can be used efficiently.

A data structure is a storage that is used to store and organize data. It is a way of arranging data on a
computer so that it can be accessed and updated efficiently.

A data structure is not only used for organizing the data. It is also used for processing, retrieving,
and storing data.

Characteristics of data structures

Following are the characteristics of the data structures as follows:

1. Linear: A linear describes data characteristics whether the data items are arranged in
sequential form like an array.
2. Non-Linear: A Non-Linear data structure describes the characteristics of data items that
are not in sequential form like a tree, graph.
3. Static: It is a static data structure that describes the size and structures of a collection of
data items associated with a memory location at compile time that are fixed. Example -
Array.
4. Homogenous: It is a characteristic of data structures representing whether the data type
of all elements is the same. Example- Array.
5. Non-Homogenous: It is a characteristic of data structures representing whether the data
type elements may or may not be the same.
 6. Dynamic: It is a dynamic data structure that defines the shrinking and expanding of data
items at the run time or the program's execution. It is also related to the utilization of
memory location that can be changed at the program's run time. Example: Linked list.
7. It has some rules that define how the data items are related to each other.
8. It defines some rules to display the relationship between data items and how they interact
with each other.
9. It has some operations used to perform on data items like insertion, searching, deletion,
etc.
10. It helps in reducing the usage of memory resources.
11. Time Complexity: The execution time of a program in a data structure should be
minimum as possible.
12. Space Complexity: The memory usage through all data items in a data structure should
be less possible.

Classification of Data Structure:

  Linear data structure: Data structure in which data elements are arranged sequentially
or linearly, where each element is attached to its previous and next adjacent elements, is
called a linear data structure.
Examples of linear data structures are array, stack, queue, linked list, etc.
 Static data structure: Static data structure has a fixed memory size. It is easier to
access the elements in a static data structure.
An example of this data structure is an array.
 Dynamic data structure: In dynamic data structure, the size is not fixed. It can
be randomly updated during the runtime which may be considered efficient
concerning the memory (space) complexity of the code.
Examples of this data structure are queue, stack, etc.
 Non-linear data structure: Data structures where data elements are not placed
sequentially or linearly are called non-linear data structures. In a non-linear data structure,
we can’t traverse all the elements in a single run only.
Examples of non-linear data structures are trees and graphs.

Basic Operations of Data Structures

Some basic functions are chosen based on all types of data that occur in a data structure.

1. Traversing: It is used to visit each variable once. It is also referred to as visiting

elements in the data structure.
2. Searching: It is used to find the location of a given element in the whole data structure.
Example, an array.
3. Insertion: It is used to insert an element at the specified position in data elements.
4. Deletion: A deletion operation is used to delete an element from the specified location.
5. Sorting: It is used to arrange or sort the data elements in ascending or descending order.
However, the data items are arranged in some logical order, such as Name key, account
number, etc.
 6. Merging: The Merge operation is used to join two or more sorted data elements to a data
structure.

Array

An array is defined as the collection of similar type of data items stored at contiguous memory
locations. Arrays are the derived data type in C programming language which can store the
primitive type of data such as int, char, double, float, etc. It also has the capability to store the
collection of derived data types, such as pointers, structure, etc. The array is the simplest data
structure where each data element can be randomly accessed by using its index number.

C array is beneficial if you have to store similar elements. For example, if we want to store the
marks of a student in 6 subjects, then we don't need to define different variables for the marks in
the different subject. Instead of that, we can define an array which can store the marks in each
subject at the contiguous memory locations.

Types of Arrays
In c programming language, arrays are classified into two types. They are as follows...

1. Single Dimensional Array / One Dimensional Array

2. Multi Dimensional Array

Single Dimensional Array

In c programming language, single dimensional arrays are used to store list of values of same
datatype. In other words, single dimensional arrays are used to store a row of values. In single
dimensional array, data is stored in linear form. Single dimensional arrays are also called as one-
dimensional arrays, Linear Arrays or simply 1-D Arrays.

Declaration of Single Dimensional Array

We use the following general syntax for declaring a single dimensional array...

datatype arrayName [ size ] ;

Example Code

int rollNumbers [60] ;

The above declaration of single dimensional array reserves 60 continuous memory locations of 2
bytes each with the name rollNumbers and tells the compiler to allow only integer values into
those memory locations.

Initialization of Single Dimensional Array

We use the following general syntax for declaring and initializing a single dimensional array
with size and initial values.

datatype arrayName [ size ] = {value1, value2, ...} ;

Example Code

int marks [6] = { 89, 90, 76, 78, 98, 86 } ;

The above declaration of single dimensional array reserves 6 contiguous memory locations of 2
bytes each with the name marks and initializes with value 89 in first memory location, 90 in
second memory location, 76 in third memory location, 78 in fourth memory location, 98 in fifth
memory location and 86 in sixth memory location.

We can also use the following general syntax to intialize a single dimensional array without
specifying size and with initial values...

datatype arrayName [ ] = {value1, value2, ...} ;

The array must be initialized if it is created without specifying any size. In this case, the size of
the array is decided based on the number of values initialized.

Example Code

int marks [] = { 89, 90, 76, 78, 98, 86 } ;

char studentName [] = "btechsmartclass" ;

In the above example declaration, size of the array 'marks' is 6 and the size of the
array 'studentName' is 16. This is because in case of character array, compiler stores one exttra
character called \0 (NULL) at the end.

Accessing Elements of Single Dimensional Array

In c programming language, to access the elements of single dimensional array we use array
name followed by index value of the element that to be accessed. Here the index value must be
enclosed in square braces. Index value of an element in an array is the reference number given to
each element at the time of memory allocation. The index value of single dimensional array
starts with zero (0) for first element and incremented by one for each element. The index value in
an array is also called as subscript or indices.

We use the following general syntax to access individual elements of single dimensional array...

arrayName [ indexValue ]

Example Code

marks [2] = 99 ;

In the above statement, the third element of 'marks' array is assinged with value '99'.

Multi Dimensional Array

An array of arrays is called as multi dimensional array. In simple words, an array created with
more than one dimension (size) is called as multi dimensional array. Multi dimensional array can
be of two dimensional array or three dimensional array or four dimensional array or more...

Most popular and commonly used multi dimensional array is two dimensional array. The 2-D
arrays are used to store data in the form of table. We also use 2-D arrays to create
mathematical matrices.
Declaration of Two Dimensional Array

We use the following general syntax for declaring a two dimensional array...

datatype arrayName [ rowSize ] [ columnSize ] ;

Example Code

int matrix_A [2][3] ;

The above declaration of two dimensional array reserves 6 continuous memory locations of 2
bytes each in the form of 2 rows and 3 columns.

Initialization of Two Dimensional Array

We use the following general syntax for declaring and initializing a two dimensional array with
specific number of rows and coloumns with initial values.

datatype arrayName [rows][colmns] = {{r1c1value, r1c2value, ...},{r2c1, r2c2,...}...} ;

Example Code

int matrix_A [2][3] = { {1, 2, 3},{4, 5, 6} } ;

he above declaration of two-dimensional array reserves 6 contiguous memory locations of 2

bytes each in the form of 2 rows and 3 columns. And the first row is initialized with values 1, 2
& 3 and second row is initialized with values 4, 5 & 6.

We can also initialize as follows...

Example Code

int matrix_A [2][3] = {

{1, 2, 3},

{4, 5, 6}

};

Accessing Individual Elements of Two Dimensional Array

In a c programming language, to access elements of a two-dimensional array we use array name
followed by row index value and column index value of the element that to be accessed. Here the
row and column index values must be enclosed in separate square braces. In case of the two-
dimensional array the compiler assigns separate index values for rows and columns.

We use the following general syntax to access the individual elements of a two-dimensional
array...

arrayName [ rowIndex ] [ columnIndex ]

Example Code

matrix_A [0][1] = 10 ;

Sparse Array

A sparse array or sparse matrix is an array in which most of the elements are zero.
Characteristics of Sparse array:
 The sparse array is an array in which most of the elements have the same value(the
default value is zero or null).
 Sparse matrices are those array that has the majority of their elements equal to zero.
 A sparse array is an array in which elements do not have contiguous indexes starting at
zero.
 Sparse arrays are used over arrays when there are lesser non-zero elements. Sparse
arrays require lesser memory to store the elements and the computation time can be
saved.
Examples of Sparse array:

Why sparse array is required over simple arrays to store the elements:
 Storage: When there is the maximum number of zero elements and the minimum
number of non-zero elements then we use a sparse array over a simple array as it requires
less memory to store the elements. In the sparse array, we only store the non-zero
elements.
 Computation Time: In the sparse array we only store non-zero elements and hence,
traversing only non-zero elements takes less computation time.

Representation of Sparse Array:

Sparse arrays can be represented in two ways:

 Array Representation
 Linked List Representation
1. Array Representation:
To represent a sparse array 2-D array is used with three rows namely: Row, Column, and
Value.

Row: Index of the row where non-zero elements are present.

Column: Index of the column where the non-zero element is present.
Value: The non-zero value which is present in (Row, Column) index.
2. Linked List Representation:
To represent a sparse array using linked lists, each node has four fields namely: Row,
Column, Value, and Next node.

Row: Index of the row where non-zero elements are present.

Column: Index of the column where the non-zero element is present.
Value: The non-zero value which is present in (Row, Column) index.
Next node: It stores the address of the next node.
Triangular Matrix

A triangular matrix is a square matrix in which elements below and/or above the diagonal are
all zeros. We have mainly two types of triangular matrices.

 A square matrix whose all elements above the main diagonal are zero is called a lower
triangular matrix.
 A square matrix whose all elements below the main diagonal are zero is called an upper
triangular matrix.
Properties of Triangular Matrix

Since we have understood the meaning of a triangular matrix, let us go through some of its
important properties. Given below is a list of the properties of a triangular matrix:

 The transpose of a triangular matrix is triangular.

 The transpose of a lower triangular matrix is n upper triangular matrix and vice-versa.
 The product of two triangular matrices is a triangular matrix.
 A triangular matrix is invertible if and only if all entries of the main diagonal are non-
zero.
 The product of two lower(upper) triangular matrices is a lower(upper) triangular matrix.
 The inverse of a triangular matrix is triangular.
 The determinant of a triangular matrix is the product of the elements of the main
diagonal.

Tridiagonal matrix

Tridiagonal matrices are the matrices which are having non-zero elements on the diagonal, super
diagonal and subdiagonal. All the rest of the elements are zeros.
Memory Representation of Sparse Matrix:

There are two types of representations for sparse matrices. These are based on the type of data
structure used to store the sparse matrix. Based on this, the representations are:

1. Array representation (Triplet Representation )

2. Linked list representation

Array Representation:

In an array representation, we make use of arrays to store a sparse matrix. The sparse matrix is
stored in a 2-D array having three rows as follows:

1. Row: It stores the index of the row, where we have a non-zero element in the sparse matrix.
2. Column: It stores the index of the column, where we have the non-zero element in the sparse
matrix.
3. Value: This variable consists of the actual non-zero value being stored.

For example, the following diagram shows how we can represent a sparse matrix with the help of
an array by storing only non-zero elements in the array along with their row number and column
number.
Linked List Representation:

A linked list is a combination of interconnected rows joined in a linear manner. In linked list
representation, each node consists of four components:

1. Row: It stores the index of the row, where we have a non-zero element in the sparse matrix.
2. Column: It stores the index of the column, where we have the non-zero element in the sparse
matrix.
3. Value: This variable consists of the actual non-zero value being stored.
4. Next node: It is a pointer to store the address of the next connected node.

Thus, we can represent the node as follows:

In the following diagram, we can see the linked list representation of a sparse matrix.