[go: up one dir, main page]
Scribd
Upload
50 views22 pages

1 - Introduction To DS

Uploaded by

swayamgarg117
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPSX, PDF, TXT or read online on Scribd
50 views22 pages

1 - Introduction To DS

Uploaded by

swayamgarg117
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPSX, PDF, TXT or read online on Scribd
You are on page 1/ 22

DATA STRUCTRES &

ALGORITHMS
INTRODUCTION OF DATA STRUCTURE

BY MAYANK BHATT
OUTLINE

 Basic Definitions
 Computer
 Data
 Information
 Data Structure
 Algorithm
 Applications of Data Structure
 Recap of Various Data Structures
 Formal Definitions
 Classification of Data Structures
INTRODUCTION TO DATA STRUCTURE

• What is Computer?
• Computer is an electronic machine which is
used for data processing and manipulation.
• For every kind of processing, there is a need of
data.
INTRODUCTION TO DATA STRUCTURE

• What is Data?
• Data is the basic fact or entity that is
utilized in calculation or manipulation.
• What is Information?
• Processed data
INTRODUCTION TO DATA STRUCTURE

• Data to be processed must be organized in a


particular fashion.
• Data structures is concerned with the
representation and manipulation of data, means
• How the data will be stored ?
• What operations will be performed on it ?
• We can also define
• Data structure as a mathematical or logical
model of a particular organization of data
items.
INTRODUCTION TO DATA STRUCTURE

• Data manipulation requires an algorithm.


• What is Algorithm?
• A high level, language independent
description of a step-by-step process for
solving a problem.
• Algorithm + Data Structure = Program
• Algorithm Analysis
• Determining how long an algorithm will take
to solve a problem.
DATA STRUCTRES &
ALGORITHMS
Lecture - 2

BY MAYANK BHATT
DATA STRUCTURE & ITS APPLICATIONS

Application of
Data Structure

Seat [8] [3]


Booked
This is Real
life
application
of an
Movie Ticket Booking System
ARRAY
DATA STRUCTURE & ITS APPLICATIONS

Application of
Data Structure

___________________
Youtube.com
C K
___________________
A
Mitindore.co.in
S T
___________________
Google.com This is Real
_
life
application of
STACK data
structure i.e.
LIFO.
DATA STRUCTURE & ITS APPLICATIONS

Application of
Data Structure
TOKEN TOKEN
-3 -2
TOKEN
-1

This is Real
life
application
QUEUE of an
QUEUE
DATA STRUCTURE & ITS APPLICATIONS

Application of
Data Structure
ADDITION OF 2
POLYNOMIALS :
• p1(x) = 18x7 + 16x4 + 5x +3
• p2(x) = 4x6 + 10x4 + 12x +
8

p1(x) +p2(x) = 18x7 + 4x6 + 26x4 +


17x + 11
DATA STRUCTURE & ITS APPLICATIONS

Application of This is Real


Data Structure life
application
of a
p1(x) = 18x7 + 16x4 + 5x +3 LINKED LIST

18 7 1 4 5 1 3 0
6
p2(x) = 4x6 + 10x4 + 12x + 8

4 6 1 4 1 1 8 0
0 2
p1(x) + p2(x) = 18x7 + 4x6 + 26x4 + 17x + 11

18 7 4 6 2 4 1 1 1 0
6 7 1
DATA STRUCTURE & ITS APPLICATIONS

This is Real
Application of life
Data Structure application
of a TREE
DATA STRUCTURE & ITS APPLICATIONS

Application of These are


Real life
Data Structure
application
s of GRAPH
Analyzing Social Networks GPS Navigation (Google Map)
RECAP OF VARIOUS APPLICATIONS

• ARRAY - Movie Ticket Booking System,


Storage of student’s marks etc.
• STACK – History in web browser for visited sites,
Recursion etc.
• QUEUE – Restaurant Order booking
Printer job spooling etc.
• LINKED LIST– Polynomial Evaluation
Free space management in OS etc.
• TREE - OS directory hierarchy
Searching and storage of data in databases
• GRAPH – Analyzing social networks
Air traffic control etc
FORMAL DEFINITIONS

ARRAY An array is a collection of same type of


items stored at contiguous memory
locations.
STACK A stack is a container of items that are
inserted and removed according to the
last-in first-out (LIFO) principle.
QUEUE A queue is a container of items that are
inserted and removed according to the
first-in first-out (FIFO) principle.
LINKED A linked list is a collection of nodes
LIST where each node is connected to the next
node through a pointer.
FORMAL DEFINITIONS

TREE Tree can be defined as a collection of


nodes (starting at a root node), where
each node is a data structure consisting
of a value, together with a list of
references to nodes (the children)

GRAPH A graph is a pictorial representation of a


set of objects where some pairs of objects
are connected by links.
CLASSIFICATION OF DATA STRUCTURES

Array

Stack
Linear
Oueue
Data
Structure Linked
s List

Tree
Non
Linear
Graph
Data types

Sr. No. Data Type Size (in bytes)

1 int 2

2 char 1

3 float 4

4 double 8

5 long int 4
Common Operations on Data Structures

 Creating: The first operation used to define


the data structure for the data elements is
called create operation. This operation
reserves the memory for the data elements.
 Traversal: The elements of data structure are
accessed in order to process them for various
operations. The accessing or visiting of each
element of the data structure exactly once is
called traversal operation.
 Searching: The operation used to find the
location of a particular element in the data
structure is called search operation.
 Insertion: The operation used to add some
element into the data structure is called
insertion operation.
Common Operations on Data Structures Continued...

 Deletion: The operation used to delete the


existing value of the data structure is called
deletion operation.
 Sorting: Some application require arranging
the data elements of the data structure in
some specific order(either in assending or
desending). This arrangement is called sorting
operation.
 Merging: The operation used to when
elements of two different sorted lists,
composed of similar elements, are combined
to form a new sorted list is called merging
operation.
 Updating: The operation used to change the
existing value of the data structure is called
Than
k You

You might also like