Fr. C.

RODRIGUES INSTITUTE OF TECHNOLOGY

(FCRIT, VASHI)

COURSE FILE
DATA STRUCTURES LAB (CSL301)
Part-B (Lab Manual)

S.E. - SEMESTER III

DEPARTMENT OF COMPUTER ENGINEERING

Data Structures Lab (CSL303) Lab Manual-Part B

LIST OF EXPERIMENTS

Prac . Language/tools
Name of Practical CO mapped
No used
1. Array Implementation of Stack. CO1 Online C-compiler

2. Well-formedness of parenthesis CO3 Online C-compiler

3. Conversion of Infix to Postfix. CO3 Online C-compiler

4. Evaluation of Postfix Expression. CO3 Online C-compiler

5. Array Implementation of Queue CO1 Online C-compiler

6. Implementation of Circular Queue CO1 Online C-compiler

7. Implementation of Singly Linked List CO1 Online C-compiler

8. Implementation of Circular Linked List. CO3 Online C-compiler

9. Linked Implementation of Stack and queue. CO1 Online C-compiler

10. Implement Binary Search Tree. CO2 Online C-compiler

11. Implement Graph Traversal Techniques CO2 Online C-compiler

12. Implement Binary search application CO4 Online C-compiler

Course Outcome

CO-ID CO-Statement Cognitive Level

Students will be able to implement Linear data
CSL303.1 structures to demonstrate various operations like Apply
create, insert, delete, search and traversal.
Students will be able to implement Non-linear data
CSL303.2 structures to demonstrate various operations like Apply
create, insert, delete, search and traversal.
Students will be able to choose and apply a suitable
CSL303.3 Apply
data structure to implement diverse problems.
Students will be able to analyze and implement several
CSL303.4 Apply, Analyze
searching techniques.

Department of Computer Engineering – FCRIT SH-2021

Data Structures Lab (CSL303) Lab Manual-Part B

Practical-01

Statement of To implement Stack using Array data structure

Problem
Course Students will be able to implement Linear data structures to demonstrate various operations
Outcome like create, insert, delete, search and traversal.
Theory A stack is a list in which all insertions and deletions are made at one end, called the top. It is
a collection of contiguous cells, stacked on top of each other. The last element to be inserted
into the stack will be the first to be removed. Thus stacks are sometimes referred to as Last In
First Out (LIFO) lists

The operations that can be performed on a stack are push, pop and top. Push is to insert an
element at the top of the stack. Pop is deleting an element that is at the top most position in
the stack. Top simple examines and returns the top most value in the stack without deleting
it. Push on an already filled stack and pop on an empty stack results in serious errors. Before
any insertion, the value of the variable top is initialized to -1.

Department of Computer Engineering – FCRIT SH-2021

Data Structures Lab (CSL303) Lab Manual-Part B

Algorithm Step 1: IF TOP = MAX-1

for PUSH PRINT OVERFLOW
Operation Goto Step 4
[END OF IF]
Step 2: SET TOP = TOP + 1
Step 3: SET STACK[TOP] = VALUE
Step 4: END
Algorithm Step 1: IF TOP = NULL
for POP PRINT UNDERFLOW
operation Goto Step 4
[END OF IF]
Step 2: SET VAL = STACK[TOP]
Step 3: SET TOP = TOP - 1
Step 4: END

Algorithm Step 1: IF TOP = NULL

PEEK PRINT STACK IS EMPTY
operation Goto Step 3
END IF
Step 2: RETURN STACK[TOP]
Step 3: END

Input *****MAIN MENU*****

and 1. PUSH
2. POP
Output
3. PEEK
4. DISPLAY
5. EXIT
Enter your option : 1
Enter the number to be pushed on stack : 500

Department of Computer Engineering – FCRIT SH-2021

Data Structures Lab (CSL303) Lab Manual-Part B

Practical-02

Statement of
Problem Check well-formedness of parenthesis using stack
Course Students will be able to choose and apply a suitable data structure to implement diverse
Outcome problems.
Theory Stacks can be used to check the validity of parentheses in any algebraic expression. For
example, an algebraic expression is valid if for every open bracket there is a corresponding
closing bracket. For example, the expression (A+B} is invalid but an expression {A + (B –
C)} is valid. Look at the program below which traverses an algebraic expression to check
for its validity.

Algorithm 1. Read one character at a time from left to right

for 2. Repeat step 3 to 5 till end of string
parenthesis 3. If it is operand and operator discard it
checking 4. If it is closing parenthesis then push onto the stack
5. If current character is closed parenthesis then check the stack[top]
a. if stack[top] is opening parenthesis of same type of current character then
pop stack[top]
b. else print “Invalid Expression” and go to exit
6. If stack[top] is empty then print “valid Expression” and go to exit
7. If stack[top] is not empty then print “Invalid Expression”
8. Exit
Algorithm Step 1: IF TOP = MAX-1
for PUSH PRINT OVERFLOW
Operation Goto Step 4
[END OF IF]
Step 2: SET TOP = TOP + 1
Step 3: SET STACK[TOP] = VALUE
Step 4: END
Algorithm Step 1: IF TOP = NULL
for POP PRINT UNDERFLOW
operation Goto Step 4
[END OF IF]
Step 2: SET VAL = STACK[TOP]
Step 3: SET TOP = TOP - 1
Step 4: END

Algorithm Step 1: IF TOP = NULL

PEEK PRINT STACK IS EMPTY
operation Goto Step 3
END IF
Step 2: RETURN STACK[TOP]
Step 3: END

Input and Enter the arithmetic expression : (())

Output Output: Valid

Department of Computer Engineering – FCRIT SH-2021

Data Structures Lab (CSL303) Lab Manual-Part B

Practical-03

Statement To implement program for Converting Infix Expression into a Postfix Expression using
of Problem Stack data structure
Course Students will be able to choose and apply a suitable data structure to implement diverse
Outcome problems.
Theory Postfix notation was developed by Jan Łukasiewicz who was a Polish logician, mathematician,
and philosopher. His aim was to develop a parenthesis-free prefix notation (also known as
Polish notation) and a postfix notation, which is better known as Reverse Polish Notation or
RPN.
In postfix notation, as the name suggests, the operator is placed after the operands. For
example, if an expression is written as A+B in infix notation, the same expression can be
written as AB+ in postfix notation. The order of evaluation of a postfix expression is always
from left to right. Even brackets cannot alter the order of evaluation.
The expression (A + B) * C can be written as:
[AB+]*C
AB+C* in the postfix notation
Algorithm Step1: Examine the next element in the input.
Step2: If it is operand, output it.
Step3: If it is opening parenthesis, push it on stack.
Step4: If it is an operator, then
i) If stack is empty, push operator on stack.
ii) If the top of stack is opening parenthesis, push operator on stack
iii) If it has higher priority than the top of stack, push operator on stack.
iv) Else pop the operator from the stack and output it, repeat step 4
Step5: If it is a closing parenthesis, pop operators from stack and
output them until an opening parenthesis is encountered. Pop
and discard the opening parenthesis.
Step6: If there is more input go to step 1
Step7: If there is no more input, pop the remaining operators to output.

Input Enter any infix expression: A+B–C*D

Output The corresponding postfix expression is : AB+CD*–

Department of Computer Engineering – FCRIT SH-2021

Data Structures Lab (CSL303) Lab Manual-Part B

Practical-04

Statement of To implement program for evaluating Postfix Expression using Stack data structure
Problem
Course Students will be able to choose and apply a suitable data structure to implement diverse
Outcome problems.
Theory The ease of evaluation acts as the driving force for computers to translate an infix notation
intoa postfix notation. Using stacks, any postfix expression can be evaluated very easily.
Every character of the postfixexpression is scanned from left to right. If the character
encountered is an operand, it is pushedon to the stack. However, if an operator is encountered,
then the top two values are popped fromthe stack and the operator is applied on these values.
The result is then pushed on to the stack.
Let us now take an example that makes use of this algorithm. Consider the infix
expressiongiven as 9 – ((3 * 4) + 8) / 4. Evaluate the expression.The infix expression 9 – ((3
* 4) + 8) / 4 can be written as 9 3 4 * 8 + 4 / – using postfixnotation. Table which shows the
procedure.

Algorithm WHILE more input items exist

{
If symb is an operand
then push (opndstk,symb)
else //symbol is an operator
{
Opnd2=pop(opndstk);
Opnd1=pop(opndnstk);
Value = result of applying symb to opnd1 & opnd2
Push(opndstk,value);
} //End of else
} // end while
Result = pop (opndstk);
Input Enter any postfix expression: 9 – ((3 * 4) + 8) / 4

Output The answer of postfix expression is 4

Department of Computer Engineering – FCRIT SH-2021

Data Structures Lab (CSL303) Lab Manual-Part B

Practical-05

Statement of Implement a program for Queue using array data structures

Problem
Course Students will be able to implement Linear data structures to demonstrate various operations
Outcome like create, insert, delete, search and traversal.
Theory Queue is an ordered collection of items from which items may be deleted at one end (called
the front of the queue) and into which items may be inserted at the other end (the rear of the
queue). Queues remember things in first-in-first-out (FIFO) order. The basic operations in a
queue are: Enqueue - Adds an item to the end of queue. Dequeue - Removes an item from the
front

Array implementation of Queue ADT:

A queue is implemented using a one dimensional array. FRONT is an integer value, which
contains the array index of the front element of the array. REAR is an integer value, which
contains the array index of the rear element of the array. When an element is deleted from
the queue, the value of HEAD is increased by one. i.e. HEAD = HEAD + 1 When an element
is inserted into the queue, the value of TAIL is increased by one. i.e. TAIL = TAIL + 1

Algorithm Step 1: IF REAR = MAX-1

for inserting Write OVERFLOW
an element in Goto step 4
queue [END OF IF]
Step 2: IF FRONT = -1 and REAR = -1
SET FRONT = REAR =0
ELSE
SET REAR = REAR + 1
[END OF IF]
Step 3: SET QUEUE[REAR] = NUM
Step 4: EXIT

Department of Computer Engineering – FCRIT SH-2021

Data Structures Lab (CSL303) Lab Manual-Part B

Algorithm Step 1: IF FRONT = -1 OR FRONT > REAR

for deleting Write UNDERFLOW
an element ELSE
from queue SET VAL = QUEUE[FRONT]
SET FRONT = FRONT + 1
[END OF IF]
Step 2: EXIT

Input and ***** MAIN MENU *****"

Output 1. Insert an element
2. Delete an element
3. Peek
4. Display the queue
5. EXIT
Enter your option : 1
Enter the number to be inserted in the queue : 50

Department of Computer Engineering – FCRIT SH-2021

Data Structures Lab (CSL303) Lab Manual-Part B

Practical-06

Statement of Implement a program for Circular Queue using array data structures
Problem
Course Students will be able to implement Linear data structures to demonstrate various operations
Outcome like create, insert, delete, search and traversal.
Theory In linear queues, we have discussed so far that insertions can be done only at one end called
the REAR and deletions are always done from the other end called the FRONT. Look at the
queue shown in
Fig

Here, FRONT = 0 and REAR = 9.

Now, if you want to insert another value, it will not be possible because the queue is
completely full. There is no empty space where the value can be inserted. Consider a scenario
in which two
successive deletions are made. The queue will then be given as shown in Fig

Suppose we want to insert a new element in the queue shown in Fig. 8.14. Even though there
is space available, the overflow condition still exists because the condition rear = MAX – 1
still holds true. This is a major drawback of a linear queue. To resolve this problem, we have
two solutions. First, shift the elements to
the left so that the vacant space can be occupied and utilized efficiently. But this can be very
time-consuming, especially when the queue is quite large. The second option is to use a
circular queue. In the circular queue, the first index comes right after the last index.
Conceptually, you can think of a circular queue as shown in Fig

Algorithm Step 1: IF FRONT = and Rear = MAX - 1

for inserting Write OVERFLOW
an element in Goto step 4
queue Step 2: IF FRONT = -1 and REAR = -1
SET FRONT = REAR =0
ELSE IF REAR = MAX - 1 and FRONT !=1
SET REAR =0
ELSE
SET REAR = REAR + 1
[END OF IF]
Step 3: SET QUEUE[REAR] = VAL
Step 4: EXIT

Department of Computer Engineering – FCRIT SH-2021

Data Structures Lab (CSL303) Lab Manual-Part B

Algorithm Step 1: IF FRONT = and Rear = MAX - 1

for deleting Write OVERFLOW
an element Goto step 4
from queue Step 2: IF FRONT = -1 and REAR = -1
SET FRONT = REAR =0
ELSE IF REAR = MAX - 1 and FRONT !=0
SET REAR =0
ELSE
SET REAR = REAR + 1
[END OF IF]
Step 3: SET QUEUE[REAR] = VAL
Step 4: EXIT
Input and ***** MAIN MENU *****"
Output 1. Insert an element
2. Delete an element
3. Peek
4. Display the queue
5. EXIT
Enter your option : 1
Enter the number to be inserted in the queue : 50

Department of Computer Engineering – FCRIT SH-2021

Data Structures Lab (CSL303) Lab Manual-Part B

Practical-07

Statement To perform all the singly linked list operations

of Problem
Course Students will be able to implement Linear data structures to demonstrate various operations
Outcome like create, insert, delete, search and traversal.
Theory Singly linked list is the simplest type of linked list in which every node contains some data and
a pointer to the next node of the same data type. By saying that the node contains a pointer to
the next node, we mean that the node stores the address of the next node in sequence. A singly
linked list allows traversal of data only in one way. Figure shows a singly linked list.

In C, we can implement a linked list using the following code:

struct node
{
int data;
struct node *next;
};

Algorithm struct node *create_ll(struct node *start)

for create {
Linked List struct node *new_node, *ptr;
int num;
printf(“\n Enter -1 to end”);
printf(“\n Enter the data : “);
scanf(“%d”, &num);
while(num!=-1)
{
new_node = (struct node*)malloc(sizeof(struct node));
new_node -> data=num;
if(start==NULL)
{
new_node -> next = NULL;
start = new_node;
}
else
{
ptr=start;
while(ptr->next!=NULL)
ptr=ptr->next;
ptr->next = new_node;
new_node->next=NULL;
}
printf(“\n Enter the data : “);
scanf(“%d”, &num);
}
return start;
}
Algorithm struct node *display(struct node *start)
for {
Displaying a struct node *ptr;
Linked List ptr = start;
while(ptr != NULL)
{

Department of Computer Engineering – FCRIT SH-2021

Data Structures Lab (CSL303) Lab Manual-Part B

printf(“\t %d”, ptr -> data);

ptr = ptr -> next;
}
return start;
}

Algorithm Step 1: IF AVAIL = NULL

for Write OVERFLOW
Inserting a Go to Step 7
Node at the [END OF IF]
Beginning Step 2: SET NEW_NODE = AVAIL
of a Linked Step 3: SET AVAIL = AVAIL→ NEXT
List Step 4: SET NEW_NODE→DATA = VAL
Step 5: SET NEW_NODE→ NEXT = START
Step 6: SET START = NEW_NODE
Step 7: EXIT

Algorithm Step 1: IF AVAIL = NULL

for Write OVERFLOW
Inserting a Go to Step 1
Node at the [END OF IF]
End of a Step 2: SET NEW_NODE = AVAIL
Linked List Step 3: SET AVAIL = AVAIL→ NEXT
Step 4: SET NEW_NODE→DATA = VAL
Step 5: SET NEW_NODE→NEXT = NULL
Step 6: SET PTR = START
Step 7: Repeat Step 8 while PTR→NEXT != NULL
Step 8: SET PTR = PTR→NEXT
[END OF LOOP]
Step 9: SET PTR→NEXT =NEW_NODE
Step 10: EXIT
Algorithm Step 1: IF AVAIL = NULL
for Write OVERFLOW
Inserting a Go to Step 12
Node After a [END OF IF]
Given Node Step 2: SET NEW_NODE = AVAIL
in a Linked Step 3: SET AVAIL = AVAIL→NEXT
List Step 4: SET NEW_NODE→DATA = VAL
Step 5: SET PTR = START
Step 6: SET PREPTR = PTR
Step 7: Repeat Steps 8 and 9 while!
PREPTR→DATA=NUM
Step 8: SET PREPTR = PTR
Step 9: SET PTR = PTR→NEXT
[END OF LOOP]
Step 1 : PREPTR→NEXT =NEW_NODE
Step 11: SET NEW_NODE→NEXT = PTR
Step 12: EXIT

Department of Computer Engineering – FCRIT SH-2021

Data Structures Lab (CSL303) Lab Manual-Part B

Algorithm Step 1: IF AVAIL = NULL

for Write OVERFLOW
Inserting a Go to Step 12
Node Before [END OF IF]
a Given Step 2: SET NEW_NODE= AVAIL
Node in a Step 3: SET AVAIL = AVAIL→ NEXT
Linked List Step 4: SET NEW_NODE→DATA = VAL
Step 5: SET PTR = START
Step 6: SET PREPTR = PTR
Step 7: Repeat Steps 8 and 9 while PTR→DATA != NUM
Step 8: SET PREPTR = PTR
Step 9: SET PTR = PTR→NEXT
[END OF LOOP]
Step 1 : PREPTR→NEXT =NEW_NODE
Step 11: SET NEW_NODE→NEXT = PTR
Step 12: EXIT
Algorithm Step 1: IF START = NULL
for Deleting Write UNDERFLOW
a First Node Go to Step 5
from a [END OF IF]
Linked List Step 2: SET PTR = START
Step 3: SET START = START→NEXT
Step 4: FREE PTR
Step 5: EXIT
Algorithm Step 1: IF START = NULL
for Deleting Write UNDERFLOW
the Last Go to Step 8
Node from a [END OF IF]
Linked List Step 2: SET PTR = START
Step 3: Repeat Steps 4 and 5
while PTR→NEXT != NULL
Step 4: SET PREPTR = PTR
Step 5: SET PTR = PTR→NEXT
[END OF LOOP]
Step 6: SET PREPTR→NEXT = NULL
Step 7: FREE PTR
Step 8: EXIT
Algorithm Step 1: IF START = NULL
for Deleting Write UNDERFLOW
the Node Go to Step 1
After a [END OF IF]
Given Node Step 2: SET PTR = START
in a Linked Step 3: SET PREPTR = PTR
List Step 4: Repeat Steps 5 and 6 while PREPTR→DATA != NUM
Step 5: SET PREPTR = PTR
Step 6: SET PTR = PTR→NEXT
[END OF LOOP]
Step 7: SET TEMP = PTR
Step 8: SET PREPTR→NEXT = PTR→NEXT
Step 9: FREE TEMP
Step 1 : EXIT
Students Implement menu driven C program for Singly Link List and tests for result
should do

Department of Computer Engineering – FCRIT SH-2021

Data Structures Lab (CSL303) Lab Manual-Part B

Input *****MAIN MENU *****

and 1: Create a list
2: Display the list
Output
3: Add a node at the beginning
4: Add the node at the end
5: Add the node before a given node
6: Add the node after a given node
7: Delete a node from the beginning
8: Delete a node from the end
9: Delete a given node
10: Delete a node after a given node
11: Delete the entire list
12: Sort the list
13: Exit
Enter your option : 3
Enter your option : 73

Department of Computer Engineering – FCRIT SH-2021

Data Structures Lab (CSL303) Lab Manual-Part B

Practical-08

Statement of To perform all the Circular linked list operations

Problem
Course Students will be able to implement Linear data structures to demonstrate various
Outcome operations like create, insert, delete, search and traversal.
Theory In a circular linked list, the last node contains a pointer to the first node of the list. We can
have a circular singly linked list as well as a circular doubly linked list. While traversing a
circular linked list, we can begin at any node and traverse the list in any direction, forward
or backward, until we reach the same node where we started. Thus, a circular linked list
has no beginning and no ending. Figure shows a circular linked list.

In C, we can implement a linked list using the following code:

struct node
{
int data;
struct node *next;
};

Algorithm for struct node *create_ll(struct node *start)

create Linked {
List struct node *new_node, *ptr;
int num;
printf(“\n Enter -1 to end”);
printf(“\n Enter the data : “);
scanf(“%d”, &num);
while(num!=-1)
{
new_node = (struct node*)malloc(sizeof(struct node));
new_node -> data=num;
if(start==NULL)
{
new_node -> next = NULL;
start = new_node;
}
else
{
ptr=start;
while(ptr->next!=start)
ptr=ptr->next;
ptr->next = new_node;
new_node->next=NULL;
}
printf(“\n Enter the data : “);
scanf(“%d”, &num);
}
return start;
}

Department of Computer Engineering – FCRIT SH-2021

Data Structures Lab (CSL303) Lab Manual-Part B

Algorithm for struct node *display (struct node *start)

Displaying a {
Linked List struct node *ptr;
ptr = start;
while(ptr -> next != start)
{
printf(“\t %d”, ptr -> data);
ptr = ptr -> next;
}
return start;
}

Algorithm for Step 1: IF AVAIL = NULL, then

Inserting a Write OVERFLOW
Node at the Go to Step 7
Beginning of a [END OF IF]
Linked List Step 2: SET New_Node = AVAIL
Step 3: SET AVAIL = AVAIL→NEXT
Step 4: SET New_Node→DATA = VAL
Step 5: SET PTR = START
Step 6: Repeat Step 7 while PTR→NEXT != START
Step 7: PTR = PTR→NEXT
Step 8: SET New_Node→Next = START
Step 8: SET PTR→NEXT = New_Node
Step 6: SET START = New_Node
Step 7: EXIT
Algorithm for Step 1: IF AVAIL = NULL
Inserting a Write OVERFLOW
Node at the End Go to Step 1
of a Linked List [END OF IF]
Step 2: SET NEW_NODE = AVAIL
Step 3: SET AVAIL = AVAIL→NEXT
Step 4: SET NEW_NODE→DATA = VAL
Step 5: SET PTR = START
Step 6: Repeat Step 8 while PTR→NEXT! = START
Step 7: SET PTR = PTR→ NEXT
[END OF LOOP]
Step 8: SET PTR→NEXT = NEW_NODE
Step 9: SET NEW_NODE→NEXT = START
Step10: EXIT
Algorithm for Step 1: IF AVAIL = NULL
Inserting a Write OVERFLOW
Node After a Go to Step 12
Given Node in a [END OF IF]
Linked List Step 2: SET NEW_NODE = AVAIL
Step 3: SET AVAIL = AVAIL→NEXT
Step 4: SET NEW_NODE→DATA = VAL
Step 5: SET PTR = START
Step 6: SET PREPTR = PTR
Step 7: Repeat Steps 8 and 9 while!
PREPTR→DATA=NUM
Step 8: SET PREPTR = PTR
Step 9: SET PTR = PTR→NEXT
[END OF LOOP]
Step 1 : PREPTR→NEXT =NEW_NODE
Step 11: SET NEW_NODE→NEXT = PTR
Step 12: EXIT

Department of Computer Engineering – FCRIT SH-2021

Data Structures Lab (CSL303) Lab Manual-Part B

Algorithm for Step 1: IF AVAIL = NULL

Inserting a Write OVERFLOW
Node Before a Go to Step 12
Given Node in a [END OF IF]
Linked List Step 2: SET NEW_NODE= AVAIL
Step 3: SET AVAIL = AVAIL→ NEXT
Step 4: SET NEW_NODE→DATA = VAL
Step 5: SET PTR = START
Step 6: SET PREPTR = PTR
Step 7: Repeat Steps 8 and 9 while PTR→DATA!= NUM
Step 8: SET PREPTR = PTR
Step 9: SET PTR = PTR→NEXT
[END OF LOOP]
Step 10 : PREPTR→NEXT =NEW_NODE
Step 11: SET NEW_NODE→NEXT = PTR
Step 12: EXIT
Algorithm for Step 1: IF START = NULL
Deleting a First Write UNDERFLOW
Node from a Go to Step 8
Linked List [END OF IF]
Step 2: SET PTR = START
Step 3: Repeat Step 4 while PTR→NEXT != START
Step 4: SET PTR = PTR→NEXT
[END OF LOOP]
Step 5: SET PTR→NEXT = START→NEXT
Step 6: FREE START
Step 7: SET START = PTR→NEXT
Step 8: EXIT
Algorithm for Step 1: IF START = NULL
Deleting the Write UNDERFLOW
Last Node from Go to Step 8
a Linked List [END OF IF]
Step 2: SET PTR = START
Step 3: Repeat Steps 4 and 5 while PTR→ NEXT != START
Step 4: SET PREPTR = PTR
Step 5: SET PTR = PTR→NEXT
[END OF LOOP]
Step 6: SET PREPTR→ NEXT = START
Step 7: FREE PTR
Step 8: EXIT
Algorithm for Step 1: IF START = NULL
Deleting the Write UNDERFLOW
Node After a Go to Step 1
Given Node in a [END OF IF]
Linked List Step 2: SET PTR = START
Step 3: SET PREPTR = PTR
Step 4: Repeat Steps 5 and 6 while PREPTR→DATA != NUM
Step 5: SET PREPTR = PTR
Step 6: SET PTR = PTR→NEXT
[END OF LOOP]
Step 7: SET TEMP = PTR
Step 8: SET PREPTR→NEXT = PTR→NEXT
Step 9: FREE TEMP
Step 1 : EXIT

Department of Computer Engineering – FCRIT SH-2021

Data Structures Lab (CSL303) Lab Manual-Part B

Input *****MAIN MENU *****

and 1: Create a list
2: Display the list
Output
3: Add a node at the beginning
4: Add the node at the end
5: Add the node before a given node
6: Add the node after a given node
7: Delete a node from the beginning
8: Delete a node from the end
9: Delete a given node
10: Delete a node after a given node
11: Delete the entire list
12: Sort the list
13: Exit
Enter your option : 3
Enter your option : 73

Department of Computer Engineering – FCRIT SH-2021

Data Structures Lab (CSL303) Lab Manual-Part B

Practical-09(A)

Statement To implement Stack using Linked List data structure

of Problem
Practical Implement Stack and their uses.
Objective
Course 1. Develop a program to implement Stack data structures and its application Students
Outcome will be able to implement Linear data structures to demonstrate various operations like
create, insert, delete, search and traversal.
2. Students will be able to choose and apply a suitable data structure to implement diverse
problems.
Theory In a linked stack, every node has two parts—one that stores data and another that stores the
address of the next node. The START pointer of the linked list is used as TOP. All insertions
and deletions are done at the node pointed by TOP. If TOP = NULL, then it indicates that the
stack is empty. The linked representation of a stack is shown in Fig

Stack is declared using linked List as follows

struct stack
{
int data;
struct stack *next;
};
Algorithm Step 1: Allocate memory for the new node and name it as New_Node
for PUSH Step 2: SET New_Node->DATA = VAL
Operation Step 3: IF TOP = NULL, then
SET New_Node->NEXT = NULL
SET TOP = New_Node
ELSE
SET New_node->NEXT = TOP
SET TOP = New_Node
[END OF IF]
Step 4: END

Algorithm Step 1: IF TOP = NULL, then

for POP PRINT “UNDERFLOW”
operation Goto Step 5
[END OF IF]
Step 2: SET PTR = TOP
Step 3: SET TOP = TOP ->NEXT
Step 4: FREE PTR
Step 5: END
Algorithm int peek(struct stack *top)
for PEEK {
operation if(top==NULL)
return -1;
else
return top ->data;
}

Department of Computer Engineering – FCRIT SH-2021

Data Structures Lab (CSL303) Lab Manual-Part B

Input *****MAIN MENU*****

and 1. PUSH
2. POP
Output
3. PEEK
4. DISPLAY
5. EXIT
Enter your option : 1
Enter the number to be pushed on stack : 500

Department of Computer Engineering – FCRIT SH-2021

Data Structures Lab (CSL303) Lab Manual-Part B

Practical-09(B)

Statement Implement a program for Queue using Linked List data structures
of Problem
Practical Implement Queue and their uses.
Objective
Course 1. Develop a program to implement Stack data structures and its application Students
Outcome will be able to implement Linear data structures to demonstrate various operations
like create, insert, delete, search and traversal.
2. Students will be able to choose and apply a suitable data structure to implement
diverse problems.
Theory In a linked queue, every element has two parts: one that stores data and the other that stores
the address of the next element. The START pointer of the linked list is used as FRONT. We
will also use another pointer called REAR which will store the address of the last element in
the queue. All insertions will be done at the rear end and all the deletions will be done at the
front end. If FRONT = REAR = NULL, then it indicates that the queue is empty.

1 7 3 4 2 6 5 X

FRONT REAR

Algorithm Step 1: Allocate memory for the new node and name it as NEW-NODE
for Step 2: SET NEW-NODE->DATA = VAL
inserting an Step 3: IF FRONT = NULL, then
element in SET FRONT = REAR = NEW-NODE
queue SET FRONT->NEXT = REAR->NEXT = NULL
ELSE
SET REAR->NEXT = NEW-NODE
SET REAR = NEW-NODE
SET REAR->NEXT = NULL
[END OF IF]
Step 4: END

Algorithm Step 1: IF FRONT = NULL, then

for deleting Write “Underflow”
an element Go to Step 5
from queue [END OF IF]
Step 2: SET PTR = FRONT
Step 3: FRONT = FRONT->NEXT
Step 4: FREE PTR
Step 5: END
Input and ***** MAIN MENU *****"
Output 1. Insert an element
2. Delete an element
3. Peek
4. Display the queue
5. EXIT
Enter your option : 1
Enter the number to be inserted in the queue : 50

Department of Computer Engineering – FCRIT SH-2021

Data Structures Lab (CSL303) Lab Manual-Part B

Practical-10

Statement Implement a program for Binary Search Tree

of Problem
Course Students will be able to implement Non-linear data structures to demonstrate various
Outcome operations like create, insert, delete, search and traversal.
Theory A Binary Search Tree is a binary tree with the following properties:
All items in the left subtree are less than the root. All items in the right subtree are greater or
equal to the root. Each subtree is itself a binary search tree. Binary search trees provide an
excellent structure for searching a list and at the same time for inserting and deleting data into
the list.
binary search tree is a binary tree with the following properties:
The left sub-tree of a node N contains values that are less than
N’s value.
The right sub-tree of a node N contains values that are greater
than N’s value.
Both the left and the right binary trees also satisfy these
Properties and, thus, are binary search trees.

Algorithm SearchElement (TREE, VAL)

for Step 1: IF TREE→ DATA = VAL OR TREE = NULL
Searching Return TREE
for a Node ELSE
in a Binary IF VAL < TREE→ DATA
Search Tree Return searchElement(TREE→ LEFT, VAL)
ELSE
Return searchElement(TREE→ RIGHT, VAL)
[END OF IF]
[END OF IF]
Step 2: END
Algorithm Insert (TREE, VAL)
for Step 1: IF TREE = NULL
inserting a Allocate memory for TREE
node in SET TREE→ DATA = VAL
Binary SET TREE→ LEFT = TREE→ RIGHT = NULL
Search Tree ELSE
IF VAL < TREE →DATA
Insert(TREE→ LEFT, VAL)
ELSE
Insert(TREE→ RIGHT, VAL)
[END OF IF]
[END OF IF]
Step 2: END

Department of Computer Engineering – FCRIT SH-2021

Data Structures Lab (CSL303) Lab Manual-Part B

Deleting a Delete (TREE, VAL)

Node from a Step 1: IF TREE = NULL
Binary Write "VAL not found in the tree"
Search Tree ELSE IF VAL < TREE→ DATA
Case 1: Delete(TREE→LEFT, VAL)
Deleting a ELSE IF VAL > TREE→ DATA
Node that Delete(TREE→ RIGHT, VAL)
has No ELSE IF TREE→LEFT AND TREE→RIGHT
Children SET TEMP = findLargestNode(TREE→LEFT)
SET TREE→DATA = TEMP→DATA
Case 2:
Delete(TREE→LEFT, TEMP→DATA)
Deleting a
ELSE
Node with
SET TEMP = TREE
One Child
IF TREE→LEFT = NULL AND TREE→RIGHT = NULL
Case 3: SET TREE = NULL
Deleting a ELSE IF TREE→LEFT != NULL
Node with SET TREE = TREE→LEFT
Two ELSE
Children SET TREE = TREE→RIGHT
[END OF IF]
FREE TEMP
[END OF IF]
Step 2: END
Determinin Height (TREE)
g the Height Step 1: IF TREE = NULL
of a Binary Return
Search Tree ELSE
SET LeftHeight = Height(TREE→LEFT)
SET RightHeight = Height(TREE→RIGHT)
IF LeftHeight > RightHeight
Return LeftHeight + 1
ELSE
Return RightHeight + 1
[END OF IF]
[END OF IF]
Step 2: END
Determinin totalInternalNodes(TREE)
g the Step 1: IF TREE = NULL
number of Return
Internal [END OF IF]
Nodes IF TREE→LEFT = NULL AND TREE→RIGHT = NULL
Return
ELSE
Return totalInternalNodes(TREE→ LEFT) +
totalInternalNodes(TREE→ RIGHT) + 1
[END OF IF]
Step 2: END
Determinin totalNodes(TREE)
g the Step 1: IF TREE = NULL
Number of Return
Nodes ELSE
Return totalNodes(TREE→LEFT)
+ totalNodes(TREE→RIGHT) + 1
[END OF IF]
Step 2: END

Department of Computer Engineering – FCRIT SH-2021

Data Structures Lab (CSL303) Lab Manual-Part B

Determinin totalExternalNodes(TREE)
g the Step 1: IF TREE = NULL
Number of Return
External ELSE IF TREE→ LEFT = NULL AND TREE→ RIGHT = NULL
Nodes Return 1
ELSE
Return totalExternalNodes(TREE→ LEFT) +
totalExternalNodes(TREE→ RIGHT)
[END OF IF]
Step 2: END
Finding the findSmallestElement(TREE)
Smallest Step 1: IF TREE = NULL OR TREE→ LEFT = NULL
Node in a Return TREE
Binary ELSE
Search Tree Return findSmallestElement(TREE→ LEFT)
[END OF IF]
Step 2: END
Finding the findLargestElement(TREE)
Largest Step 1: IF TREE = NULL OR TREE→RIGHT = NULL
Node in a Return TREE
Binary ELSE
Search Tree Return findLargestElement(TREE→RIGHT)
[END OF IF]
Step 2: END
Traversing Step 1: Repeat Steps 2 to 4 while TREE != NULL
BST: Pre- Step 2: Write TREE→DATA
Order Step 3: PREORDER(TREE→LEFT)
Traversal Step 4: PREORDER(TREE→ RIGHT)
[END OF LOOP]
Step 5: END
Traversing Step 1: Repeat Steps 2 to 4 while TREE != NULL
BST: In- Step 2: INORDER(TREE→ LEFT)
order Step 3: Write TREE→DATA
Traversal Step 4: INORDER(TREE→RIGHT)
[END OF LOOP]
Step 5: END
Traversing Step 1: Repeat Steps 2 to 4 while TREE != NULL
BST: Post- Step 2: POSTORDER(TREE→LEFT)
order Step 3: POSTORDER(TREE→RIGHT)
Traversal Step 4: Write TREE→DATA
[END OF LOOP]
Step 5: END
Input and *******MAIN MENU*******
Output 1. Insert Element
2. Preorder Traversal
3. In-order Traversal
4. Post-order Traversal
5. Find the smallest element
6. Find the largest element
7. Delete an element
8. Count the total number of nodes
9. Count the total number of external nodes
10. Count the total number of internal nodes
11. Determine the height of the tree
12. Exit

Department of Computer Engineering – FCRIT SH-2021

Data Structures Lab (CSL303) Lab Manual-Part B

Practical-11

Statement of Implementation of Graph Traversal Techniques

Problem
Course Students will be able to implement Non-linear data structures to demonstrate various
Outcome operations like create, insert, delete, search and traversal.
Theory By traversing a graph, we mean the method of examining the nodes and edges of the graph.
There are two standard methods of graph traversal which we will discuss in this section.
These two methods are
✓ Breadth-first search
✓ Depth-first search
While breadth-first search uses a queue as an auxiliary data structure to store nodes for
further processing, the depth-first search scheme uses a stack. But both these algorithms
make use of a variable STATUS. During the execution of the algorithm, every node in the
graph will have the variable STATUS set to 1 or 2, depending on its current state. Table 13.1
shows the value of STATUSand its significance.

Algorithm Step 1: SET STATUS = 1 (ready state)

for BFS for each node in G
Step 2: Enqueue the starting node
and set its STATUS = 2
(waiting state)
Step 3: Repeat Steps 4 and 5 until
QUEUE is empty
Step 4: Dequeue a node N. Process it
and set its STATUS = 3
(processed state).
Step 5: Enqueue all the neighbors of N that are in the ready state (whose STATUS = 1)
and set their STATUS = 2
(waiting state)
[END OF LOOP]
Step 6: EXIT
Algorithm Step 1: SET STATUS = 1 (ready state) for each node in G
for DFS Step 2: Push the starting node A on the stack and set
its STATUS = 2 (waiting state)
Step 3: Repeat Steps 4 and 5 until STACK is empty
Step 4: Pop the top node N. Process it and set its STATUS = 3 (processed state)
Step 5: Push on the stack all the neighbors of N that are in the ready state (whose STATUS
= 1) and
set their STATUS = 2 (waiting state)
[END OF LOOP]
Step 6: EXIT
Input Enter the adjacency matrix:
01010
10110
01001
11001
00110
Output BFS: A B D C E
DFS:

Department of Computer Engineering – FCRIT SH-2021

Data Structures Lab (CSL303) Lab Manual-Part B

Practical-12

Statement of To find a given target number using Binary search from the list of numbers.
Problem
Course Students will be able to analyze and implement several searching techniques.
Outcome
Theory In this algorithm, we see that BEG and END are the beginning and ending positions of the
segment that we are looking to search for the element. MID is calculated as (BEG + END)/2.
Initially, BEG = lower_bound and END = upper_bound. The algorithm will terminate when
A[MID] = VAL. When the algorithm ends, we will set POS = MID. POS is the position at
which the value is present in the array.
However, if VAL is not equal to A[MID], then the values of BEG, END, and MID will be
changed depending on whether VAL is smaller or greater than A[MID].
(a) If VAL < A[MID], then VAL will be present in the left segment of the array. So, the
value of END
will be changed as END = MID – 1.
(b) If VAL > A[MID], then VAL will be present in the right segment of the array. So, the
value of BEG will be changed as BEG = MID + 1.
Finally, if VAL is not present in the array, then eventually, END will be less than BEG.
When this happens, the algorithm will terminate and the search will be unsuccessful.
Algorithm Step 1: [INITIALIZE] SET BEG = lower_bound
END = upper_bound, POS = - 1
Step 2: Repeat Steps 3 and 4 while BEG <= END
Step 3: SET MID = (BEG + END)/2
Step 4: IF A[MID] = VAL
SET POS = MID
PRINT POS
Go to Step 6
ELSE IF A[MID] > VAL
SET END = MID - 1
ELSE
SET BEG = MID + 1
[END OF IF]
[END OF LOOP]
Step 5: IF POS = -1
PRINT “VALUE IS NOT PRESENT IN THE ARRAY”
[END OF IF]
Step 6: EXIT
Input Enter the number of elements in the list: 5
Enter the sorted list: 11 22 33 44 55
Enter the target: 33
Output The target is found in location: 3

Department of Computer Engineering – FCRIT SH-2021