Intro Ds

Introduction
to
Data Structures
Definition
 Data structure is representation of the logical
relationship existing between individual
elements of data.
 In other words, a data structure is a way of
organizing all data items that considers not
only the elements stored but also their
relationship to each other.
Introduction
 Data structure affects the design of both
structural & functional aspects of a program.
Program=algorithm + Data Structure
 You know that a algorithm is a step by step
procedure to solve a particular function.

Introduction
 That means, algorithm is a set of instruction
written to carry out certain tasks & the data
structure is the way of organizing the data
with their logical relationship retained.
 To develop a program of an algorithm, we
should select an appropriate data structure
for that algorithm.
 Therefore algorithm and its associated data
structures from a program.
Classification of Data Structure
 Data structure are normally divided into
two broad categories:
 Primitive Data Structure
 Non-Primitive Data Structure

Data structure
Primitive DS Non-Primitive DS
Integer Float Character Pointer

Non-Primitive DS
Linear List Non-Linear List
Array Queue Graph Trees
Link List Stack

Primitive Data Structure
 There are basic structures and directly
operated upon by the machine instructions.
 In general, there are different representation
on different computers.
 Integer, Floating-point number, Character
constants, string constants, pointers etc, fall
in this category.
Non-Primitive Data Structure
 There are more sophisticated data structures.
 These are derived from the primitive data
structures.
 The non-primitive data structures emphasize
on structuring of a group of homogeneous
(same type) or heterogeneous (different type)
data items.
 Lists, Stack, Queue, Tree, Graph are
example of non-primitive data structures.
 The design of an efficient data structure
must take operations to be performed on the
data structure.
 The most commonly used operation on data
structure are broadly categorized into
following types:
 Create
 Selection
 Updating
 Searching
 Sorting
 Merging
 Destroy or Delete
Different between them
 A primitive data structure is generally a
basic structure that is usually built into the
language, such as an integer, a float.
 A non-primitive data structure is built out of
primitive data structures linked together in
meaningful ways, such as a or a linked-list,
binary search tree, AVL Tree, graph etc.
Description of various
Data Structures : Arrays
 An array is defined as a set of finite number
of homogeneous elements or same data
items.
 It means an array can contain one type of
data only, either all integer, all float-point
number or all character.
Arrays
 Simply, declaration of array is as follows:
int arr[10]
 Where int specifies the data type or type of
elements arrays stores.
 “arr” is the name of array & the number
specified inside the square brackets is the
number of elements an array can store, this is
also called sized or length of array.
Arrays
 Following are some of the concepts to be
remembered about arrays:
 The individual element of an array can be
accessed by specifying name of the array,

following by index or subscript inside
square brackets.
 The first element of the array has index
zero[0]. It means the first element and last

element will be specified as:arr[0] & arr[9]
Respectively.
Arrays
 The elements of array will always be
stored in the consecutive (continues)
memory location.
 The number of elements that can be stored
in an array, that is the size of array or its

length is given by the following equation:
(Upperbound-lowerbound)+1
Arrays
 For the above array it would be
(9-0)+1=10,where 0 is the lower bound
of array and 9 is the upper bound of
array.
 Array can always be read or written
through loop. If we read a one-

dimensional array it require one loop for
reading and other for writing the array.
Arrays
 For example: Reading an array
For(i=0;i<=9;i++)
scanf(“%d”,&arr[i]);
 For example: Writing an array
For(i=0;i<=9;i++)
printf(“%d”,arr[i]);
Arrays
 If we are reading or writing two-
dimensional array it would require two
loops. And similarly the array of a N
dimension would required N loops.
 Some common operation performed on
array are:
 Creation of an array
 Traversing an array
Arrays
 Insertion of new element
 Deletion of required element
 Modification of an element
 Merging of arrays
Lists
 A lists (Linear linked list) can be defined as a
collection of variable number of data items.
 Lists are the most commonly used non-primitive
data structures.
 An element of list must contain at least two
fields, one for storing data or information and
other for storing address of next element.
 As you know for storing address we have a
special data structure of list the address must be
pointer type.
Lists
 Technically each such element is referred to
as a node, therefore a list can be defined as
a collection of nodes as show bellow:
[Linear Liked List]
Head
AAA BBB CCC
Information field Pointer field

Lists
 Types of linked lists:
 Single linked list
 Doubly linked list
 Single circular linked list
 Doubly circular linked list
Stack
 A stack is also an ordered collection of
elements like arrays, but it has a special
feature that deletion and insertion of
elements can be done only from one end
called the top of the stack (TOP)
 Due to this property it is also called as last
in first out type of data structure (LIFO).
Stack
 It could be through of just like a stack of plates
placed on table in a party, a guest always takes
off a fresh plate from the top and the new plates
are placed on to the stack at the top.
 It is a non-primitive data structure.
 When an element is inserted into a stack or
removed from the stack, its base remains fixed
where the top of stack changes.
Stack
 Insertion of element into stack is called
PUSH and deletion of element from stack is
called POP.
 The bellow show figure how the operations
take place on a stack:
PUSH POP
[STACK]
Stack
 The stack can be implemented into two
ways:
 Using arrays (Static implementation)
 Using pointer (Dynamic implementation)

Queue
 Queue are first in first out type of data
structure (i.e. FIFO)
 In a queue new elements are added to the
queue from one end called REAR end and the
element are always removed from other end
called the FRONT end.
 The people standing in a railway reservation
row are an example of queue.
Queue
 Each new person comes and stands at the
end of the row and person getting their
reservation confirmed get out of the row
from the front end.
 The bellow show figure how the
operations take place on a stack:
10 20 30 40 50
front rear
Queue
 The queue can be implemented into two
ways:
 Using arrays (Static implementation)
 Using pointer (Dynamic implementation)

Trees
 A tree can be defined as finite set of data
items (nodes).
 Tree is non-linear type of data structure in
which data items are arranged or stored in a
sorted sequence.
 Tree represent the hierarchical relationship
between various elements.
Trees
 In trees:
 There is a special data item at the top of
hierarchy called the Root of the tree.
 The remaining data items are partitioned into
number of mutually exclusive subset, each
of which is itself, a tree which is called the
sub tree.
 The tree always grows in length towards
bottom in data structures, unlike natural trees
which grows upwards.
Trees
 The tree structure organizes the data into
branches, which related the information.
A root
B C
D E F G
Graph
 Graph is a mathematical non-linear data
structure capable of representing many kind
of physical structures.
 It has found application in Geography,
Chemistry and Engineering sciences.
 Definition: A graph G(V,E) is a set of
vertices V and a set of edges E.
Graph
 An edge connects a pair of vertices and
many have weight such as length, cost and
another measuring instrument for according
the graph.
 Vertices on the graph are shown as point or
circles and edges are drawn as arcs or line
segment.
Graph
 Example of graph:
6
v2 v5
v1 v3
10
v1 8 11
15
9 v2
v3 v4 v4
[a] Directed & [b] Undirected Graph

Weighted Graph
Graph
 Types of Graphs:
 Directed graph
 Undirected graph
 Simple graph
 Weighted graph
 Connected graph
 Non-connected graph

Intro Ds

Uploaded by

Copyright:

Available Formats

Intro Ds

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Intro Ds

Uploaded by

Copyright:

Available Formats

Introduction

procedure to solve a particular function.

 Non-Primitive Data Structure

Integer Float Character Pointer

Linear List Non-Linear List

Array Queue Graph Trees

Link List Stack

accessed by specifying name of the array,

zero[0]. It means the first element and last

in an array, that is the size of array or its

through loop. If we read a one-

AAA BBB CCC

Information field Pointer field

 Using pointer (Dynamic implementation)

 Using pointer (Dynamic implementation)

[a] Directed & [b] Undirected Graph

You might also like