Page 11 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes we must find some way of representing the ADTs in terms of the data types and operators

supported by the programming language itself. To represent the mathematical model underlying
an ADT, we use data structures, which are a collection of variables, possibly of several data types,
connected in various ways.
The cell is the basic building block of data structures. We can picture a cell as a box that is capable
of holding a value drawn from some basic or composite data type. Data structures are created
by giving names to aggregates of cells and (optionally) interpreting the values of some cells as
representing relationships or connections (e.g., pointers) among cells.

Task Value definition is a one part of ADT the second one is

1.2 Definition of Data Structure

A data structure is a set of data values along with the relationship between the data values. Since,
the operations that can be performed on the data values depend on what kind of relationships
exists among them, we can specify the relationship amongst the data values by specifying the
operations permitted on the data values. Therefore, we can say that a data structure is a set
of values along with the set of operations permitted on them. It is also required to specify the
semantics of the operations permitted on the data values, and this is done by using a set of
axioms, which describes how these operations work, and therefore a data structure is made of:

1. A set of data values.
2. A set of functions specifying the operations permitted on the data values.
3. A set of axioms describing how these operations work.
Hence, we conclude that a data structure is a triple (D,F,A), where

1. D is a set of data values
2. F is a set of functions
3. A is a set of axioms
A triple (D, F, A) is referred to as an abstract data structure because it does not tell anything about
its actual implementation. It does not tell anything about how these values will be physically
represented in the computer memory and these functions will be actually implemented.
Therefore every abstract data structure is required to be implemented, and the implementation
of an abstract data structure requires mapping of the abstract data structure to be implemented
into the data structure supported by the computer. For example, if the abstract data structure
to be implemented is integer, then it can be implemented by mapping into bits which is a data
structure supported by hardware. This requires that every integer data value is to be represented
using suitable bit patterns and expressing the operations on integer data values in terms of
operations for manipulating bits.

Data Structure mainly two types:
1. Linear type data structure
2. Non-linear type data structure
Linear data structure: A linear data structure traverses the data elements sequentially, in which
only one data element can directly be reached. Ex: Arrays, Linked Lists.

6 LOVELY PROFESSIONAL UNIVERSITY