DATA STRUCTURE
CHAPTER - 2
INTRODUCTION TO DATA STRUCTURES
1. Field
2. Record
3. File
4. Data
a) Elementary Items
b) Group Items
c) Entity
INTRODUCTION TO DATA STRUCTURES
1. Field
2. Record
3. File
4. Data
a) Elementary Items – ROLL NO , MOBILE NO.
b) Group Items – DOB
c) Entity –
NAME AGE GENDER EDUCATION
ATUL 22 M B.E. (CS)
PORTION
• Basic Definitions
• Algorithms
• Array & Pointer Array
• Records
• Linked List
• Stack
• Queue
• Tree
SIX DATA STRUCTURE OPERATIONS
DATA STRUCTURE
ALGORITHMS
USUAL FORMAT FOR WRITING ALGORITHMS
1. START
2.
3.
4.
N. STOP
FORMAT FOR WRITING DATA STRUCTURE ALGORITHMS
STEP 1:
STEP 2:
STEP 3:
STEP 4:
STEP N: EXIT
How to assign a value to a variable :-
In C++ / VB, we assign a value like :
int x = 15
x 15
In Data Structure algorithm :
set x : = 15
How to write comments :-
In Data Structure algorithm comments are
written in a pair of square brackets “[ ]” :
Eg: [Decrement the count]
How to use “ if statement ” :-
If condition, then :
[module A]
[End of if structure]
Eg. How to use “ if statement ” :-
If a > b, then :
set s := 0
[End of if structure]
How to use “ if else statement ” :-
If condition, then :
[module A]
else :
[module B]
[End of if structure]
Eg. How to use “ if else statement” :-
If a > b, then :
set s : = 0
else :
set s : = 1
[End of if structure]
How to use “else if statement ” :-
If condition 1, then :
[module A1]
else if condition 2, then :
[module A2]
.
.
else if condition n, then :
[module An]
else :
[module B]
[End of if structure]
Eg. How to use “else if statement ” :-
If a = 1, then :
set s : = 1
else if a = 2, then :
set s : = 2
.
.
else if s = n, then :
set s : = n
else :
set s : = 0
[End of if structure]
How to use “ while loop ” :-
Repeat while condition :
[module]
[End of loop]
Eg. How to use “ while loop ” :-
set a : = 1
Repeat while a < = 5 :
set s : = a
set a : = a + 1
[End of loop]
How to use “ for loop ” :-
Repeat for K = R To S by T :
[module]
[End of loop]
NOTE :- Here, K is the variable , R is the initial value ,
S is the final value and T is the increment or decrement value
(if T is not mentioned then it is by default considered as
increment by 1)
Eg. How to use “ for loop ” :-
Repeat for K = 1 To 10 by 2 :
set s : = K
[End of loop]
NOTE :- Here, K is the variable , 1 is the initial value ,
10 is the final value and 2 is the increment (or decrement)
value
Eg. How to use “ for loop ” :-
Repeat for K = 1 To 10 :
set s : = K
[End of loop]
NOTE :- Here, K is the variable , 1 is the initial value , 10 is
the final value and 1 is the increment or decrement value (if T
is not mentioned then it is by default considered as increment
by 1)
Algorithm has two parts :-
First part is a paragraph which tells the
purpose of the algorithm. In this part,
variables used in the algorithm are defined
and the inputs going to be used in the
algorithm are listed. (1 Mark)
Second part is the algorithm (2 or 3 Marks)
ARRAYS
ARRAYS
10
a=
LA [0] LA [1] LA [2] LA [3]
LA = 32
34 16
18 80
82 55
57
PROCESS = LA [K] + 2
TRAVERSING AN ARRAY :-
TRAVERSE (LA, LB, UB)
Here LA is a linear array with lower bound LB and upper bound
UB. The following algorithm applies an operation PROCESS to
each element of the array LA.
Step 1 : Repeat For K = LB To UB : Repeat For K = 0 To 3
Apply PROCESS to LA [K] Apply PROCESS to LA [K]
[ End of loop ] K=42
3
1
Step 2 : Exit
ORIGINAL ARRAY
LA [0] LA [1] LA [2] LA [3]
32 16 80 55
ARRAY WITH A NEW ELEMENT 10 INSERTED AT
POSITION LA [2]
LA [0] LA [1] LA [2] LA [3] LA [4]
32 16 80 55
LA [0] LA [1] LA [2] LA [3] LA [4]
32 16 10 80 55
INSERTING AN ELEMENT INTO AN ARRAY :-
INSERT (LA, N, K, ITEM)
Here LA is a linear array with N elements. This algorithm
inserts an element ITEM at the K th position in the array LA.
Step 1 : [initialize counter]
Set J := N
Step 2 : Repeat steps 3 and 4 while J> K :
Step 3 : [Move J th element forward]
Set LA [J +1] := LA [J]
Step 4 : [Decrement counter]
Set J := J – 1
[End of Step 2 loop]
Step 5 : [Insert the element]
Set LA [K] := ITEM
Step 6 : [Reset N]
Set N := N + 1
Step 7 : Exit
DELETING AN ELEMENT FROM AN ARRAY :-
DELETE (LA, N, K, ITEM)
Here LA is a linear array with N elements. This algorithm deleted
an element at the K th position in the array LA and assigns it to
variable ITEM.
Step 1 : [Assign the element at K th position to variable ITEM]
Set ITEM := LA [K]
Step 2 : Repeat for J = K To N - 1 :
[Move J th element backward]
Set LA [J] := LA [J + 1]
[End of loop]
Step 3 : [Reset N]
Set N := N - 1
Step 4 : Exit
Bubble
Sort
3 5 4 6 8
3 5 4 6 8
3 4 5 6 8
3 4 5 6 8
3 4 5 6 8
3 4 5 6 8
3 4 5 6 8
3 4 5 6 8
3 4 5 6 8
3 4 5 6 8
3 4 5 6 8
3 4 5 6 8
BUBBLE SORT ALGORITHM :-
DATA [1] DATA [2] DATA [3] DATA [4] DATA [5]
5
3 3
5 8
4 4
6
8 6
8
BUBBLE SORT(DATA, N)
Here DATA is a linear array with N elements. This algorithm sorts
the elements of the array DATA in ascending order.
Step 1 : Repeat steps 2 and 3 for K := 1 To N – 1 :
Step 2 : Set Ptr := 1
Step 3 : Repeat while Ptr < N - K :
(a) If DATA [Ptr] > DATA [Ptr + 1], then interchange
DATA [Ptr] and DATA [Ptr + 1]
[End of If structure]
(b)[increment pointer]
Set Ptr := Ptr + 1
[End of inner while loop]
[End of outer for loop]
Step 4 : Exit
Linear
Search
2
1 2 3 4 5 6
2
1 2 3 4 5 6
2
1 2 3 4 5 6
2 4
1 2 3 4 5 6
22
1 2 3 4 5 6 7
22
1 2 3 4 5 6 7
22
1 2 3 4 5 6 7
22 4
1 2 3 4 5 6 7
LINEAR SEARCH ALGORITHM :-
LINEAR SEARCH (DATA, N, ITEM, LOC)
Here DATA is a linear array with N elements and ITEM is the
element to be searched. This algorithm finds the location LOC of
ITEM in the array DATA or sets LOC = 0 if search is unsuccessful.
Step 1 : [Insert ITEM at the end of DATA]
Set DATA [N + 1] := ITEM
Step 2 : [Initialize counter]
Set LOC := 1
Step 3 : [Search for ITEM]
Repeat while DATA [LOC] ≠ ITEM :
Set LOC := LOC + 1
[End of loop]
Step 4 : If LOC = N + 1, then :
Set LOC := 0
Step 5 : Exit
Binary
Search
Item to be searched is 23 in the given array ‘a’
1 2 3 4 5 6 7 8 9
6
9
7
1 2 3 4 5 6 7 8 9
8
9
8
1 2 3 4 5 6 7 8 9
Item to be searched is “7” in the given array ‘a’
1 2 3 4 5 6 7 8 9
a[mid] = a[5] = 13
13 > 7 6
end = 9mid – 1 = 4
beg = 1 7
mid = (beg + end)/2 = 2
1 2 3 4 5 6 7 8 9
a[mid] = a[2] = 5
5<7
beg = mid + 1 = 83
end = 49
8
mid = (beg + end)/2 = 3
1 2 3 4 5 6 7 8 9
a[mid] = a[3] = 7
7=7
loc = mid = 3
BINARY SEARCH ALGORITHM :-
BINARY SEARCH (DATA, LB, UB, ITEM, LOC)
Here DATA is a sorted array with lower bound LB and upper bound
UB and ITEM is the element to be searched. BEG denotes beginning,
MID denotes middle and END denotes end location of DATA. This
algorithm finds the location LOC of ITEM in the array DATA or sets
LOC = NULL if search is unsuccessful.
Step 1 : [Initialize variables]
Set BEG := LB, END := UB and MID := INT((BEG + END)/2)
Step 2 : Repeat steps 3 and 4
while BEG ≠ END and DATA [MID] ≠ ITEM :
Step 3 : If ITEM < DATA [MID], then :
Set END := MID - 1
Else :
Set BEG := MID + 1
[End of If structure]
Step 4 : Set MID := INT ((BEG + END)/2)
[End of step 2 loop]
Step 5 : If DATA [MID] = ITEM, then :
Set LOC := MID
Else :
Set LOC := NULL
[End of If structure]
Step 6 : Exit
PORTION
• Basic Definitions
• Algorithms
• Array & Pointer Array
• Records
• Linked List
• Stack
• Queue
• Tree
ADDRESS OF NAME OF EMPLOYEE ARRAYS & POINTER ARRAYS
ARRAY A
Now, dividing the employees
A[1] PRIYA
in groups of 2, 5, 4 & 4
A[2] NITIN
A[3] SAKSHI
A[4] AMIT EMPLOYEE ADDRESS OF
GROUP ARRAY B
A[5] VIVEK
(ARRAY B)
A[6] RAVI
1 B[1]
A[7] POOJA
3 B[2]
A[8] RAJVEER
8 B[3]
A[9] VIHAAN
12 B[4]
A[10] AMOL
A[11] YOGESH
A[12] PREETI
A[13] ROHIT
A[14] BEENA
A[15] RAHUL
WHAT IS A RECORD ?
(START)
START /
INFO LINK INFO LINK INFO LINK INFO LINK
HEAD
5 A 7 B 4 C 1 D X
5 7 4 1
REPRESENTATION OF LINKED LIST IN MEMORY
START INFO LINK
5 1 D 0
2
3
4 C 1
5 A 7
6
7 B 4
Queue follows FIFO system. The insertion of data takes place at
the “Rear or Back” of the Queue which is called ‘Enqueue’. The
deletion of data takes place from the “Front” of the Queue which
is called ‘Dequeue’.
STACK
Stack follows LIFO system
The data is “Pushed” (or put) into the stack on top of the
previous data. The data which is on top is always
“Poped” (or taken out) of the stack first.
TREE STRUCTURE
1. Root
2. Parent
3. Child
4. Sibling
5. Leaf
6. Subtree
LEVEL OF A TREE
Each node in a tree is assigned a level number.
The level number for Root is always “0”.
Following child nodes will have a level number one more than
its parent.
It is the distance from the Root.
HEIGHT / DEPTH OF A TREE
DEGREE OF A TREE
The number of subtree / children of a
node is called the Degree of the node.
The maximum degree of any node in the
tree is called the degree of the tree.
The degree of the tree given is 5.
BINARY TREE
The binary tree is a tree in which no node has degree
more than 2.
COMPLETE BINARY TREE
A complete binary tree is a tree in which all leaf nodes
have the same level.
EXTENDED BINARY TREE / 2 - TREE
An extended binary tree or 2 – Tree is a tree in which all
nodes have either 0 or 2 children (i.e. the degree of each
node is 0 or 2).
DRAWING TREE DIAGRAMS FROM EXPRESSIONS /
EQUATIONS
(a + b)(c + d)
(a + b)*(c + d)
*
+ +
a b c d
DRAWING TREE DIAGRAMS FROM EXPRESSIONS /
EQUATIONS
y = (a + b)(c + d)
=
y
*
+ +
a b c d
DRAWING TREE DIAGRAMS FROM EXPRESSIONS /
EQUATIONS
y = (a + b)2(c + d)
=
y
*
↑ +
+ 2 c d
a b
DRAWING TREE DIAGRAMS FROM EXPRESSIONS /
EQUATIONS
y = (a + b) (c + d) 3
=
y
*
+ ↑
+ 3
a b
c d
DRAWING TREE DIAGRAMS FROM EXPRESSIONS /
EQUATIONS
y = [(a + b) (c + d)]5
y =
↑
* 5
+ +
a b c d
WRITE THE EXPRESSIONS / EQUATIONS FROM TREE
DIAGRAMS
EXPRESSION :-
(a + b * c) + ((d * e + f) * g)
WRITE THE EXPRESSIONS / EQUATIONS FROM TREE
DIAGRAMS
EXPRESSION :-
(a / (b + d)) + ((a2 – b2) / 2)
IMPORTANT QUESTIONS FOR BOARD EXAM
1) Define : Data, Group Item, Elementary Item, Entity,
Field, Record & File.
2) What is Data Structure ?
3) Explain six Data Structure operations in brief.
4) Data Structure Algorithms :-
a) Traversing an array
b) Inserting an element in an array
c) Deleting an element from an array
d) Bubble Sort
e) Linear Search
f) Binary Search
IMPORTANT QUESTIONS FOR BOARD EXAM
5) What are Pointer Arrays ?
6) What is a Record and how is it represented in
memory ?
7) What are Linked Lists and how is it represented in
memory ?
8) Explain Stack and Queue ?
9) What is a Tree ? Define the terms : Root, Leaf, Siblings
and Child.
IMPORTANT QUESTIONS FOR BOARD EXAM
10)Explain the terms :-
a) Level of a Tree
b) Depth / Height of a Tree
c) Degree of a Tree
11) What is a Binary Tree ? What is Complete Binary
Tree & Extended Binary Tree (2 – Tree)?
12) Draw the Tree Structure for the given Expression.
(any expression can be given)
13) Write the Expression for the Tree Structure shown.
(any tree structure can be given)