Transcript INTRODUCTION TO DATA STRUCTURE

APPLICATION OF DATA STRUCTURE
www.fakengineer.com
INTRODUCTION TO DATA STRUCTURE
• A data structure is a way of storing data in a computer & the
associated method for retrieving the data.
• A carefully chosen data structure will allow a more efficient
algorithm to be used.
• A well design data structure allows a variety of critical operation to
be performed using a few resources, both execution time & memory
space.
• Data structures are implemented using the data types, reference &
operation on them provided by a programming language.
www.fakengineer.com
• Different data structure are suited to different kinds of application &
are highly specialized to certain task. Ex- B-trees are particularly
well suited for implementation of databases.
• Since data structures are so crucial to professional programs, many
of them enjoy extensive support in standard libraries of modern
programming languages & environment such as C++, java API etc.
• Some of the common data structure used are stacks, linked list, trees
& graph.
www.fakengineer.com
SOME COMMON DATASTRUCTURE
STACKS• A stack is a temporary
abstract data type & data
structures based on the
principle of LIFO (last in
first out).
• The modern PCs uses stacks
at the architecture levels;
which are in a basic design
of an operating system for
the interrupt handling &
operating system function
calls.
www.fakengineer.com
QUEUES-
• It is a abstract data structure
where various entities such
as data, object, persons or
events are stored & held to
be processed later.
• The most well known
operation of a queue is the
FIFO (first in first out).
www.fakengineer.com
LINKED LIST-
•
•
•
•
1.
2.
3.
A linked list is one of the fundamental data structures used in
computer programming.
It consist of sequence of nodes, each containing arbitrary data
fields & one or two references pointing to the next or previous
nodes.
It permits insertion & removal of node at any point in the list in
constant time, but don’t allow random access.
There are three types of linked list;
Single linked list
Double linked list
Circular linked list.
www.fakengineer.com
www.fakengineer.com
www.fakengineer.com
TREES• A tree is a widely used data structure that emulates a tree structure
with a set of linked nodes.
• Node may contain a value or condition or represent a separate data
structure or tree of its own. Each node in a tree has zero or more
child nodes, which are below it in a tree, a node that has a child is
called as a child’s parent node.
• The top most node in a tree is called the root n0des.
• Nodes at the bottom most level of the trees are called leaf nodes.
• An internal node is any node of the tree that has child nodes & is not
thus a leaf node.
• The portion of the tree data structure that can be viewed as a
complete tree itself is called as sub tree.
www.fakengineer.com
www.fakengineer.com
GRAPHS• A graph is a kind of data structure, specifically an abstract data type
(ADT) that consist of a set of nodes and a set of edges that establish
relationships between the node.
• The graph ADT follows directly from the graph,
a graph G defined as follows G=(V,E),
where V is a finite, non-empty set of vertices &
E is a set of edge (link between pair of vertices).
when the edge in the graph has no direction, the graphic is called
uni-directed.
www.fakengineer.com
GRAPH THEORY-
• Graph theory is a study of
graphs, mathematical
structures use to model pair
wise relations between
object from a certain
collection.
• Graph in this context refers
to an collection of vertices &
collection of edges that
connects pair of vertices.
• A graph can be uni-directed,
meaning that there is no
distinction between the two
vertices associated with each
www.fakengineer.com
edge.
APPLICATION OF DATA STRUCTURES
1.
APPLICATION OF STACKS-
•
Expression, evaluation & syntax parsingcalculators employing reverse polish notation use a stack structure
to hold values. Expression can be represented in prefix & infix
notation. Conversion from one form of the expression to another
form needs a stack. Many compilers use a stack for parsing the
syntax of expression program, blocks etc before translating into
low level code. Most of the programming language is context free
language allowing them to be parsed with stack based machine.
www.fakengineer.com
•
Runtime memory managementA number of programming languages are stack oriented.
Many virtual machines are also stack oriented, including the
p-code machine & java virtual machines. Almost all
computer runtime memory environment uses a special stack
to hold information about procedure or function calling &
nesting in order to switch to the context of the called
function & restore to the callers function when the calling
finishes. They follow a runtime protocol between a caller &
the callee to save argument & return value on the stacks.
Stacks are an important way of supporting nested or
recursive function calls.
www.fakengineer.com
• Solving search problemsSolving a search program, regardless of whether the approach is
exhaustive or optimal, needs stack space.
Example of exhaustive search methods is brute force &
backtracking.
Example of optimal search exploring method is branch & bound &
heuristic solution.
All of this algorithm use stacks to remember the search nodes that
had been noticed but not explored now.
www.fakengineer.com
2.
•
•
1.
2.
3.
APPLICATION OF THE QUEUES
Simulation of traffic control system.
CPU scheduling in multiprogramming & time sharing
environment.
Multilevel queue scheduling.
Multilevel feedback queue scheduling.
Round robin scheduling algorithm.
www.fakengineer.com
3.
APPICATION OF LINKED LIST
• Linked list are used as building block for many other data structure
such as stacks, queues and their variations, the data field of the node
can be another linked list.
• By this device, one can construct many linked data structure with
lists, this practice originated in the lisp programming language.
• Linked list are used to implement associative arrays, and are in this
context called association list.
• Linked list are usually outperformed by the other data structures
such as self balancing binary search trees even in a small data set.
However sometimes a linked list is dynamically created out of a
subset of nodes in such a tree & used to more efficiently traverse that
set.
www.fakengineer.com
4.
APPLICATION OF TREES
• To manipulate hierarchical data.
• Make information easy to search.
• Manipulate sorted list of data.
www.fakengineer.com
5.
APPICATION OF GRAPHS
• Graph data structure are not hierarchical & therefore suitable for
data sets where the individual elements are interconnected in
complex ways.
for ex. computer network can be stimulated by a graph.
• Graph algorithm are significant field of interest for computer
scientists. Typical operations associated with graphs are:
_finding a path between two nodes like depth first
search & breadth first search.
_& finding the shortest path from one node to another
like Dijkstra’s algorithm.
www.fakengineer.com
• Structures can be represented as graphs, many problem of practical
interest can be represented by a graph. The linked structure of the
website can be represented by a directed graph; a similar approach
can be taken to the problems in travel, biology, computer chip
design & in many other field.
• It helps in determination of the structural properties of a network,
such as the distribution in the vertex degrees & the diameter of the
graph.
• It helps in the analysis to find a measurable quantity within a
network. ex. fora transportation network.
• The three dimensional structure of the complicated simulated
atomic structure can be studied quantitatively by gathering statistics
on graph theoretic properties related to the topology of the atom.
www.fakengineer.com