GOVERNMENT POLYTECHNIC, GONDIA
Data Structure Using ‘C’
MSBTE course code -22317
UNIT -01
Lecture part-02
Krishn Kumar
(Lecturer in Comp. engg.)
G P Gondia
INDEX
UNIT 1.1 Concept and need of DS
Abstract Data Type
-01 • 1.2 Types of Data Structures:
(i) Linear Data Structures
(ii) Non-Linear Data Structures
• 1.3 Algorithm Complexity:
(i)Time
(ii)Space
• 1.4 Operations on Data Structures:
(i)Traversing,
(ii)Searching,
(iii)Insertion,
(iv)Deletion,
(v) Sorting
Unit Outcomes (Uos)
Concept of Abstract Data Type.
Explain complexity of the given algorithm in
terms of time and space.
Explain the given operations to be performed
on the given type of data structures.
Abstract Data Type
The abstract data type is a triplet of
D –Set of domain
F- set of functions
A-Axioms
in which only what is to be done is mentioned but
how it is to be done is not mentioned.
In ADT all the implementation details are hidden….
ADT=Type +Function names +Behaviour of each
function
ADT
While modelling the problems the necessary details are
separated out from the unnecessary details .
This process of modelling the problem is called abstraction.
• It is represented as
problem
Abstraction
Hidden Abstract model
Abstract model
• The model defines an abstract view to the
problem .
• Thus the model focuses only on problem
related staff and that you try to define
properties of the problem.
• These properties include:
The data which are affected and
The operations which are identified.
Abstract Data Type operations
Create: This operation creates the database.
Display: This operation is for displaying all the
elements of the data structure.
Insertion: By this operation the element can be
inserted at any desired position.
Deletion :By this operation any desired element
can be deleted from the data structure.
Modifications : This operation modifies the
desired elements value by desired new value.
ADT Data Structures
• The ADT operations are carried out with the help of data
structure.
• The part describes the structure of the data used in the
ADT in an informal way.
• Various data structures that can be used for ADT are
Array
Set
Linked list
Stack
Queues
ADT for SET
• If we want to write ADT for a set of integers ,
then we will use following methods.
• AbstractDataType Set
{
Instances: Set is a collection of integer type of
elements.
Preconditions : none
Operations:
• Store():This operation is for storing the integer
element in a set.
• Retrieve():This operation is for retrieving the
desired element from the given set.
• Display():This operation is for displaying the
contents of set.
}
• There is a specific method using which an ADT
can be written.
Let’s analyse the
same example
Once again
ADT for SET
• If we want to write ADT for a set of
integers,then we will use following methods.
AbstractDataType Set
{ Name Of DS
Instances: Set is a collection of integer type of
elements. Basic idea about the corresponding data Structure must be given .
Preconditions:none
Using Precondition / Post Condition mention Specific
Conditions that must be satisfied before or after execution of
corresponding function
Listing of all operation must be given ,.. Must specify the purpose
of the function
Operations:
Store():This operation is for storing the integer
element in a set.
Retrieve():This operation is for retrieving the
desired element from the given set.
Display():This operation is for displaying the
contents of set.
}
ADT for Array
AbstractDataType Array
{
Instance: An array A of size , index i and total number of
elements in the array n.
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]
subscript
Operations:
[Link]()-This operation stores the desired elements at each
successive location.
[Link]()-This operation displays the elements of the array.
}
Recall and Recollect some more fact
• ADT are like user defined data types which
defines operations on values using functions
without specifying what is there inside the
function and how the operations are
performed.
Let’s take some
more examples
• Example :
ADT stack
{
Instance: a stack consist of elements of the same type
arranged in sequential order.
Operations:
Initialize()-initializing is to be empty.
Push()-Insert an element into the stack.
Pop()-Deleting an element from the stack.
IsEmpty()-Check if stack is empty.
Isfull()-Check if stack is full.
}
Abstract Data Type
• ADT is like a black box which hides the inner
structure and design of the data types from
the user .
we can implement an ADT in a multiple ways
Example :Stack can be implemented using arrays
or linked lists.
• Likewise many data structures such as
Queue
Tree
Graphs
And many more can be implemented through
array or linked list.
Why ADT
Answer is here
• The programmes which uses data structure is
client program
• It has access to the ADT i.e interface.
• The program which implements the data
structure is known as the implementation.
Benefit of ADT
• let’s say if any body wants to use
the stack in the program , then
he can simply use push or pop
operations without worrying
about its implementation details.
• If in future implementation of
stack change from array to
linked list , then the client
program will work in the same
way as before without being
Conclusion
ADT Provides
Abstraction
I see the matter of
my concern Only…..