INTRODUCTION TO DATA STRUCTURES
By
Dr.A.Ashok Kumar
Department Of Computer Science,
Alagappa Govt. Arts College, Karaikudi
THE NEED OF DATA STRUCTURES
Computer system based on three
activities:
1. Storing
2. Accessing
3. Manipulation
CONTINUED....
The field of computer science divided into major
categories:
Operating systems
Databases
Compilers
Artificial Intelligence
Application programs
Etc..
Each of this field requires above said activities
CONTINUED ...
Each field addresses the data of their interest
All applications of computer science uses the
study of data structures
Every programmer need to understand the
principles and techniques to solve the problems.
TYPES
A type refers to a domain of values
The following table shows the examples:
Types Domain of Values
Characters Set of characters
Integers ...., -3, -2, -1, 0, 1, 2, 3, ....
Real Set of real numbers
Complex numbers Real number x Real number
Small fractions { x | x is between 0.0 and 1.0}
Boolean {true | false}
Days {Sunday, Monday,..., Saturday}
Months {Jan, Feb, ..., Dec}
Primary colors {red, green, blue}
DATA TYPE
Data type refers to the domain of values
(types) and the operations performed on these
values
Table shows the examples of data types:
Data Types Set of operations
Integer Addition, Subtraction, Multiplication, Division, Modules
Character Convert a character to lowercase/uppercase, to find whether
the character is alphabetic/digit, etc.
Real Number Arithmetic (+, -, *,/), finding absolute, floor, ceil values
Complex number Create complex number, find conjugate of the number,
arithmetic operations(+, -, *, /)
Boolean AND, OR, NOT
ABSTRACT DATA TYPES (ADT)
An ADT is a data type in which the members of
the data type are unknown to users of the type
Abstraction refers to defining new types, hiding
the details of implementation
The user and the implementor agree on the type
of the interface
Example: interface for operating a television
using remote control
Television circuit details are hidden
ADVANTAGES OF ADT
Isolate application from the implementation
Supports modular programming
1. Program split into modules
2. Modules compiled separately
3. Modules can use same ADT
Supports encapsulation
1. Modules are kept independent
2. Different classes that implements same interface
3. No need to change the modules use the ADT, when change
the implementation
PRE- AND POST- CONDITIONS
Pre- condition refers to the properties of the
inputs assumed by the operation
This defines the state of the program before calling a
function
Post- conditions specifies the effect of an
operation
This defines the state of the program when it returns
DATA STRUCTURES
A data structure is a physical representation of an
ADT
It indicates the data type and how its stored in a
computer
An integer as a data structure, defined as integer
data type stored on consecutive memory locations
CONTINUED...
String is a data structure, consists of sequence of
characters – stored in consecutive locations
Two types of implementations:
Fixed length and
Variable length
The following table shows the various types of
data types:
Type Topology Description Examples
Set Collection of Students in a class
unrelated items
Linear One-to-One Queue at a ticket
relationship counter
Hierarchical One-to-Many A family tree,
(Tree) relationship organization chart
Network (Graph) Many-to-Many Communication
relationship network, road map
TYPES OF DATA STRUCTURES
Classification according to the type of elements:
Primitive data structure:- basic structures like integer,
character
Compound data structure:- one which consists of
other structures
Classification according to the ordering between
them:
Linear data structure:- elements have a linear order
with first, second and so on
Non-linear data structure:- ordering is not present
File structures
The data structure defined in secondary storage
devices as files
Recursive data structure
A data structure partially composed of smaller
instances of the same data structure, e.g. Tree
