CST 201 DATA STRUCTURES
Module 1
1
Data
Data : a value or a set of values
Examples :
1. 20
2. 10/2/90
3. 40,45,50,35
2
Entity
An entity is one that has certain attributes and which may be
assigned values.
Example :
Employee in an organization is an entity.
Attributes : Name DOB Designation
Values : Ravi 10/2/85 Manager
Entity set : all the employees in an organization constitute an
entity set.
Domain : set of all possible values that could be assigned to a
particular attributes.
3
Information
Information : meaningful data or processed data
Example :
Data Meaning
20 Age of the person
10/2/90 Date of birth of the person
40,45,50,35 Marks of the 4 subjects
4
Relation between data and information
To get information from the given set of data, we need to define certain
processes and then apply the corresponding process on the data.
5
Data type
Data type : refers to the type of data that may appear in a
computation OR
A data type is a collection of objects and a set of operations that
act on those objects.
Example :
Data Data type
20 Numeric(integer)
10/2/90 Date
40,45,50,35 Array of integers
6
Built-in data type
In every programming language, there is a set of data types
called built-in data types.
Example :
C : int, float, char, double etc.
FORTRAN : INTEGER, REAL, COMPLEX, DOUBLE
PRECISION, CHARACTER etc.
Pascal : Integer, Real, Character, Boolean etc.
7
Abstract data type(user-defined data type)
When an application requires a special kind of data which is not
available as built-in data type then it is the programmer's burden
to implement his own kind of data.
Here, the programmer has to give more effort regarding how to
store value for that data, what are the operations that
meaningfully manipulate variables of that kind of data, amount
of memory require to store for a variable.
The programmer has to decide all these things and accordingly
implement it.
Programmers' own data type is termed as abstract data type.
For example, we want to process dates of the form dd/mm/yy
8
Abstract data type(user-defined data type)
If a programmer wants to process dates, then an abstract data type,
say Date, can be devised and various operations like: to add few
days to a date to obtain another date, to find the days between two
dates, to obtain a day for a given date, etc., have to be defined
accordingly.
An abstract data type, in fact, can be built with the help of built-in
data types and other abstract data type(s) already built by the
programmer.
Some programming languages allow facility to build abstract data
type easily.
For example, using struct/class in C/C++ and using record in
Pascal, programmers can define their own data types. 9
Abstract data type(user-defined data type)
Definition :
An abstract data type(ADT) is a data type that is organized in
such a way that the specification of the objects and the
specifications of the operations on the objects is separated from
the representation of the objects and the implementations of the
operations.
10
Data Structure - Definitions
The Logical or mathematical representation of a
particular organization of data is called a Data Structure.
A data structure is the systematic way to organize data so
that it can be used efficiently.
Example : Array, Stack, Queue, Linked List, Tree, Graph.
11
Data Structure - Definitions
For a given kind of user data, its structure implies the following:
1. Domain (D): This is the range of values that the data may have.
This domain is also termed as data object.
2. Function : This is the set of operations which may legally
be applied to elements of data object. This implies that for a
data structure we must specify the set of operations.
3. Axioms This is the set of rules with which the different
operation belongs to can actually be implemented.
Now we can define the term data structure.
12
Data Structure - Definitions
13
Data Structure
Different kinds of data structures are suited to different kinds
of applications, and some are highly specialized to specific
tasks.
Example: B-trees are particularly well-suited for
implementation of databases, while compiler
implementations usually use hash tables to look up
identifiers.
14
Types of Data Structure
1. Primitive and Non-Primitive Data Structure :
Primitive :
Examples : int, char, float, double etc.
The integers, reals, logical data, character data and pointers are
primitive data structures.
These data types are available in most programming languages as
built in type.
Data objects of primitive data types can be operated upon by
machine level instructions.
15
Types of Data Structure
Non-Primitive :
These data structure are derived from primitive data structures and
also known as user defined data structure.
Examples of non-primitives data structures: Array, structure,
union, linked-list, stack, queue, tree, graph.
Non-primitive data structures can be two types :
1. Static Data Structure Example : Array
2. Dynamic Data Structure Example : Linked List
16
Types of Data Structure
1. Static Data Structure
In Static data structure the size of the structure is fixed.
The content of the data structure can be modified but without changing
the memory space allocated to it.
17
Types of Data Structure
2. Dynamic Data Structure
There are many situation where the number of items to be stored is not
known before hand. In this case we use dynamic data structure.
In Dynamic data structure the size of the structure in not fixed and can be
modified during the operations performed on it.
18
Types of Data Structure
2. Linear and Non-Linear Data Structure :
Linear :
Elements are arranged in a linear fashion.
Arrays, Lists, stacks and queues are examples of linear data
structure.
19
Types of Data Structure
Figure shows the representation of linear data structure.
20
Types of Data Structure
2. Linear and Non-Linear Data Structure :
Non-Linear :
Data structures where data elements are not arranged sequentially
or linearly are called non-linear data structures.
Examples : Tree, graphs
21
Types of Data Structure
Figure : Non-Linear data structure
22
Types of Data Structure
23
Thank You…
24
