LAB MANUAL

Subject: Data Structure LAB (CSL301)

Semester: III

Prepared By: Mr. Mahendra Patil

1
 Lab Outcomes
LO1 Students will be able to implement linear data structures & be able to
handle operations like insertion, deletion, searching and traversing on
them.
LO2 Students will be able to implement nonlinear data structures & be
able to handle operations like insertion, deletion, searching and
traversing on them
LO3 Students will be able to choose appropriate data structure and apply
it in various problems
LO4 Students will be able to select appropriate searching techniques for
given problems.

2
 List of Experiments
Subject:- Data Structures Laboratory (CSL301) Class: SE 1 & 2 SEM: III

Sr. No. Title of Experiments LO addressed

1 Implement Stack ADT using an array. LO1

2 Convert an Infix expression to Postfix expression using stack ADT. LO1, LO3

3 Evaluate Postfix Expression using Stack ADT. LO1, LO3

4 Implement Linear Queue ADT using an array. LO1

5 Implement Circular Queue ADT using an array. LO1

6 Implement Singly Linked List ADT. LO1

7 Implement Circular Linked List ADT. LO1

8 Implement Stack ADT using Linked List. LO1, LO3

9 Implement Binary Search Tree ADT using Linked List. LO2, LO3, LO4

10 Implement Graph Traversal techniques: a) Depth First Search b) LO2, LO3, LO4
Breadth First Search

Subject Incharge: H.O.D.

Prof. Mahendra Patil Dr. Suvarna Pansambal

3
 Experiment No: 1
Aim:
Implement Stack ADT using an array.

Theory:
Stack is a linear data structure which follows a particular order in which the operations are
performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out). Stack is an
abstract data type with a bounded(predefined) capacity. It is a simple data structure that
allows adding and removing elements in a particular order. Every time an element is added,
it goes on the top of the stack and the only element that can be removed is the element that
is at the top of the stack, just like a pile of objects.

Basic features of Stack:

1. Stack is an ordered list of similar data types.
2. Stack is a LIFO(Last in First out) structure or we can say FILO(First in Last out).
3. push() function is used to insert new elements into the Stack and pop() function is used to
remove an element from the stack. Both insertion and removal are allowed at only one end of
Stack called Top.
4. Stack is said to be in Overflow state when it is completely full and is said to be in Underflow
state if it is completely empty.

Algorithm:
Algorithm for PUSH operation
1. Check if the stack is full or not. If the stack is full, then print an error of overflow and exit
the program by going to step 4.
2. If the stack is not full, then
Do Top = Top + 1
3. Set Stack [Top] = VALUE.
4. End
Algorithm for POP operation
1. Check if the stack is empty or not. If the stack is empty, then print the error of underflow
and exit the program by going to step 4.
2. If the stack is not empty, then Print VALUE = STACK [Top]
3. Do Top = Top - 1
4. End

4
Program:
#include<stdio.h>
#include<conio.h>
#define MAX 50
int stack[MAX], top=-1;
void push();
void pop();
void peek();
void display();
int main()
{
int choice;
clrscr();
printf("\n\t ###MENU###");
printf("\n\t1.PUSH\n\t2.POP\n\t
3.DISPLAY\n\t4.PEEK \n\t5.EXIT\n");
do
{
printf("Enter the Choice:");
scanf("%d", &choice);
switch (choice)
{
case 1:
{
void push()
{
int x;
if (top >= MAX - 1)
{
printf("STACK is overflow\n");
}
else
{
printf("Enter a value to be pushed:");
scanf("%d", &x);
top++;
stack[top] = x;
}
}
void pop()
{
if (top <= -1)
{
printf("Stack is under flow.\n");
}
else
push();
break;
5
 }
case 2:
{
pop();
break;
}
case 3:
{
display();
break;
}
case 4:
{
peek();
break;
}
case 5:
{
printf("Exit Point");
break;
}
default:
{
printf("Invalid Input !");
{
printf("The popped elements is %d.\n",
stack[top]);
top--;
}
}
void peek()
{
if (top == -1)
printf("Nothing to Peek.\n");
else
printf("Top Element is : %d.\n",
stack[top]);
}
void display()
{
int i;
if (top >= 0)
{
printf("The elements in STACK \n");
for (i = top; i >= 0; i--)
printf("%d\n", stack[i]);
}
else
6
 {
printf("The STACK is empty.\n");
}
}
}
} while (choice != 5);
getch();
return 0;
}
}
Outcome:

7
 Experiment No: 2
Aim: Convert an Infix expression to Postfix expression using stack ADT.
Theory:
Expression conversion is the most important application of stack. Given an infix expression, it
can be converted to both prefix and postfix expressions. Postfix notation is said to be harder to
learn.
Infix expression: The expression of the form a op b. When an operator is in-between every pair
of operands.
Postfix expression: The expression of the form a b op. When an operator is followed for every
pair of operands.

Algorithm:
1. Scan the infix expression from left to right.
2. If the scanned character is an operand, output it.
3. Else,
3.1 If the precedence of the scanned operator is greater than the precedence of the
operator in the stack(or the stack is empty or the stack contains a ‘(‘ ), push it.
3.2 Else, Pop all the operators from the stack which are greater than or equal to in
precedence than that of the scanned operator. After doing that Push the scanned operator to
the stack. (If you encounter parenthesis while popping then stop there and push the scanned
operator in the stack.)
4. If the scanned character is an ‘(‘, push it to the stack.
5. If the scanned character is an ‘)’, pop the stack and and output it until a ‘(‘ is encountered,
and discard both the parenthesis.
6. Repeat steps 2-6 until the infix expression is scanned.
7. Print the output
8. Pop and output from the stack until it is not empty.
Program:
#include<stdio.h>
#include<conio.h>
#include<stdlib.h> /* for exit() */
#include<ctype.h> /* for isdigit(char ) */
#include<string.h>
8
#define SIZE 100
char stack[SIZE];
int top = -1;
void push(char item)
{
if(top >= SIZE-1)
{
printf("\nStack Overflow.");
}
else
{
top = top+1;
stack[top] = item;
}
}char pop()
{
char item ;
printf("\nInvalid infix Expression.\n");
}
}
int precedence(char symbol)
{
if(symbol == '^')/* exponent operator,
highest precedence*/
{
return(3);
}
else if(symbol == '*' || symbol == '/')
{
return(2);
}
else if(symbol == '+' || symbol == '-')
/* lowest precedence */
{
return(1);
}
else
{
return(0);
}
if(top <0)
{
printf("stack underflow: invalid
infix expression");
//getchar();
exit(1);
}
else
9
 {
item = stack[top];
top = top-1;
}
return(item);
}int is_operator(char symbol)
{
if(symbol == '^' || symbol == '*' ||
symbol == '/' || symbol == '+' || symbol =='-')
{
return 1;
}
else
{
return 0;
} void InfixToPostfix(char infix_exp[], char
postfix_exp[])
{
int i, j;
char item;
char x;
push('('); /* push '(' onto
stack */
strcat(infix_exp,")"); /* add
')' to infix expression */
i=0;
j=0;
item=infix_exp[i]; /* initialize
before loop*/
while(item != '\0') /* run loop till end of
infix expression */
{
if(item == '(')
{
push(item);
}
else if( isdigit(item) ||
isalpha(item))
else if(is_operator(item) == 1)
/* means symbol is operator */
{
x=pop();
while(is_operator(x) == 1 &&
precedence(x)>= precedence(item))
{
postfix_exp[j] = x; /* so pop all
higher precendence operator and */
10
 j++;
x = pop();
/* add them to postfix expresion */
}
else if(item == ')') /* if current
symbol is ')' then */
{
x = pop(); /* pop and
keep popping until */
while(x != '(') /* '('encountered */
{ postfix_exp[j] = x;
j++;
x = pop(); }
{
postfix_exp[j] =
item; /* add operand symbol to postfix expr */
j++;
}
illegal symbol */
}
if(top>0)
{
printf("\nInvalid infix
Expression.\n"); /* the it is illegal symbol */
}
postfix_exp[j] = '\0';
}
int main()
{
clrscr();
char infix[SIZE], postfix[SIZE]; /* declare infix string and postfix string */
printf("\nEnter Infix expression : ");
gets(infix);
InfixToPostfix(infix,postfix);
/* call to convert */
printf("Postfix Expression: ");
puts(postfix); /* print postfix expression */
getch();
return 0;
}
Outcome:

11
 Experiment No: 3
Aim: Evaluate Postfix Expression using Stack ADT.
Theory:
Introduction to Postfix Expression
● An operator is printed after its operands in a postfix expression.
● In postfix notation, the infix expression 2+3 equals 23+.
● Operations on postfix expressions are conducted in the sequence in which they
are printed (left to right).
● There is no need for brackets. In postfix notation, the infix expression 2+3*4
equals 234*+.
● In postfix notation, the infix expression 3*4+2*5 converts to 34*25*+.

342+*5* is the infix expression for 3*(4+2)*5.

Algorithms:
1. Create an empty stack called operandStack.
2. Scan the string from left to right.
a) If the token is an operand, convert it from a string to an integer and push the
value onto the operand stack.
b) If the token is an operator, *, /, +, or -, it will need two operands. Pop the
operandStack twice. The first pop is the second operand and the second pop is
the first operand. Perform the arithmetic operation. Push the result back on the
operand stack.
3. When the input expression has been completely processed, the result is on the
stack. Pop the operand stack and return the value.
Program:
// C program to evaluate value of a postfix expression
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// Stack type
struct Stack {
int top;
unsigned capacity;
int* array;
12
};
// Stack Operations
struct Stack* createStack(unsigned capacity)
{
struct Stack* stack
= (struct Stack*)malloc(sizeof(struct Stack));
if (!stack)
return NULL;
stack->top = -1;
stack->capacity = capacity;
stack->array
= (int*)malloc(stack->capacity * sizeof(int));
if (!stack->array)
return NULL;
return stack;
}
int isEmpty(struct Stack* stack)
{
return stack->top == -1;
}
char peek(struct Stack* stack)
{
return stack->array[stack->top];
}
char pop(struct Stack* stack)
{
if (!isEmpty(stack))
return stack->array[stack->top--];
return '$';
}
void push(struct Stack* stack, char op)
{
stack->array[++stack->top] = op;
}
// The main function that returns value
// of a given postfix expression
int evaluatePostfix(char* exp)
{
13
 // Create a stack of capacity equal to expression size
struct Stack* stack = createStack(strlen(exp));
int i;
// See if stack was created successfully
if (!stack)
return -1;
// Scan all characters one by one
for (i = 0; exp[i]; ++i) {
// If the scanned character is an operand
// (number here), push it to the stack.
if (isdigit(exp[i]))
push(stack, exp[i] - '0');
// If the scanned character is an operator,
// pop two elements from stack apply the operator
else {
int val1 = pop(stack);
int val2 = pop(stack);
switch (exp[i]) {
case '+':
push(stack, val2 + val1);
break;
case '-':
push(stack, val2 - val1);
break;
case '*':
push(stack, val2 * val1);
break;
case '/':
push(stack, val2 / val1);
break;
}
}
}
return pop(stack);
}

14
// Driver code
int main()
{ char exp[] = "231*+9-";
// Function call
printf("postfix evaluation: %d", evaluatePostfix(exp));
return 0;
}
Output:
postfix evaluation: -4

15
 Experiment No: 4
Aim: Implement Linear Queue ADT using an array.
Theory:
A queue is an abstract data structure that contains a collection of elements. Queue
implements the FIFO mechanism i.e. the element that is inserted first is also deleted
first. In other words, the least recently added element is removed first in a queue.

In this, the function Insert() inserts an element into the queue. If the rear is equal to
n-1, then the queue is full and overflow is displayed. If front is -1, it is incremented by
1. Then the rear is incremented by 1 and the element is inserted in the index of the rear.

In the function Delete(), if there are no elements in the queue then it is underflow
condition. Otherwise the element at front is displayed and the front is incremented by
one.

In the function display(), if the front is -1 then the queue is empty. Otherwise all the
queue elements are displayed using a for loop.

Algorithm:
Algorithm to insert element in Queue:
1. If (REAR == Max - 1) Then [Check for overflow]
Print: Overflow , Go to Step 4. End of If.
2. If (FRONT and REAR == -1)
Set FRONT = REAR = 0
Else Set REAR = REAR + 1 [Increment REAR by 1]
[End of If]
3. Set QUEUE[REAR] = VALUE
4. Exit

Algorithm to delete element from Queue:

16
1. If FRONT == -1 then
Print “Queue Underflow”, Go to step 4.
End of if
2. Value = QUEUE[FRONT]
3. If FRONT=REAR
Then
Set FRONT=REAR=-1
Else
Set FRONT= FRONT+ 1
4. Exit

Program:
# include<stdio.h>
#include<conio.h>
# define MAX 5
int queue[MAX];
int front = -1;
int rear = -1;
void insert(int i)
{
if((front == 0 && rear == MAX-1) || (front
== rear+1))
{
printf("Queue Overflow \n");
return;
}
if (front == -1)
{
front = 0;
rear = 0;
}
else
{
if(rear == MAX-1)
rear = 0;
else
rear = rear+1;
}
queue[rear] = i ;
}
void del()
{
17
if (front == -1)
{
printf("Queue Underflow\n");
return ;
}
printf("Element deleted from queue is :
%d\n",queue[front]);
if(front == rear)
{
front = -1;
rear=-1;
}
else
{
if(front == MAX-1)
front = 0;
else
front = front+1;
}
}
void display()
{
int i;
if(front == -1)
{
printf("Queue is empty\n");
return;
}
printf("Queue elements :\n");
for(i=front;i<=rear;i++)
{
printf("\t %d ",queue[i]);
}
}
int main()
{
int choice,i;
clrscr();
do
{
printf("1.Insert\n");
printf("2.Delete\n");
printf("3.Display\n");
printf("4.Quit\n");
printf("Enter your choice : ");
scanf("%d",&choice);
switch(choice)
18
{
case 1 :
printf("Input the
element for insertion in queue : ");
scanf("%d", &i);
insert(i);
break;
case 2 :
del();
break;
case 3:
display();
break;
case 4:
break;
default:
printf("Wrong
choice\n");
}
}while(choice!=4);
return 0;
}
Outcome:

19
 Experiment No: 5
Aim: Implement Circular Queue ADT using an array.
Theory:
Circular Queue is a linear data structure in which the operations are performed based
on FIFO (First In First Out) principle and the last position is connected back to the first
position to make a circle. It is also called ‘Ring Buffer’.
Operations on Circular Queue:
● Front: Get the front item from the queue.
● Rear: Get the last item from the queue.
● enQueue(value): This function is used to insert an element into the circular queue.
In a circular queue, the new element is always inserted at the Rear position.
1. Steps:Check whether queue is Full – Check ((rear == MAX-1 && front
== 0) || (rear == front-1)).
2. If it is full then the display Queue is full. If queue is not full then, check if
(rear == MAX – 1 && front != 0) if it is true then set rear=0 and insert
element.
● deQueue(): This function is used to delete an element from the circular queue. In a
circular queue, the element is always deleted from front position.
1. Steps:Check whether the queue is Empty means check (front==-1).
2. If it is empty then the display Queue is empty. If queue is not empty then
step 3
3. Check if (front==rear) if it is true then set front=rear= -1 else check if
(front==MAX-1), if it is true then set front=0 and return the element.
Program:
# include<stdio.h>
#include<conio.h>
# define MAX 5
int queue[MAX];
int front = -1;
int rear = -1;
void insert(int i)
{
20
if((front == 0 && rear == MAX-1) ||
(front == rear+1))
{
printf("Queue Overflow \n");
return;
}
if (front == -1)
{
front = 0;
rear = 0;
}
else
{
if(rear == MAX-1 && front!=0)
rear = 0;
else
rear = rear+1;
}
queue[rear] = i ;
}
void del()
{
if (front == -1)
{
printf("Queue Underflow\n");
return ;
}
printf("Element deleted from queue is : %d\n",queue[front]);
if(front == rear)
{
front = -1;
rear=-1;
}
else
{
if(front == MAX-1)
front = 0;
else
front = front+1;
}
}
void display()
{
int x = front,y = rear;
if(front == -1)
{
printf("Queue is empty\n");
return;
21
}
printf("Queue elements :\n");
if( x<= y )
while(x <= y)
{
printf("%d ",queue[x]);
x++;
}
else
{
while(x <= MAX-1)
{
printf("%d ",queue[x]);
x++;
}
x = 0;
while(x <= y)
{
printf("%d ",queue[x]);
x++;
}
}
printf("\n");
}
int main()
{
int choice,i;
clrscr();
do
{
printf("1.Insert\n");
printf("2.Delete\n");
printf("3.Display\n");
printf("4.Quit\n");
printf("Enter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1 :
printf("Input the element for insertion in queue : ");
scanf("%d", &i);
insert(i);
break;
case 2 :
del();
break;
case 3:
display();
22
break;
case 4:
break;
default:
printf("Wrong
choice\n");
}
}while(choice!=4);
return 0;
}

Outcome:

23
 Experiment No: 6
Aim: Implement Singly Linked List ADT.
Theory:
A linked list is a linear collection of data elements. These data elements are called
nodes. Linked list is a data structure which in turn can be used to implement other data
structures. Thus, it acts as a building block to implement data structures such as
stacks, queues, and their variations. A linked list can be perceived as a train or a
sequence of nodes in which each node contains one or more data fields and a pointer to
the next node.

Algorithm:
To insert a new node at the beginning
Step 1: IF AVAIL = NULL
Write OVERFLOW
Go to Step 7
[END OF IF]
Step 2: SET NEW_NODE = AVAIL
Step 3: SET AVAIL = AVAIL NEXT
Step 4: SET DATA = VAL
Step 5: SET NEW_NODE NEXT = START
Step 6: SET START = NEW_NODE
Step 7: EXIT

To insert a new node after a node that has value

NUM
Step 1: IF AVAIL = NULL
Write OVERFLOW
Go to Step 12
[END OF IF]
Step 2: SET = AVAIL
Step 3: SET AVAIL = AVAIL NEXT
24
Step 4: SET DATA = VAL
Step 5: SET PTR = START
Step 6: SET PREPTR = PTR
Step 7: Repeat Steps 8 and 9 while PTR NEXT != NUM
Step 8: SET PREPTR = PTR
Step 9: SET PTR = PTR NEXT
[END OF LOOP]
Step 10: PREPRT->NEXT=NEW_NODE
Step 11: SET NEW_NODE NEXT = PTR
Step 12: EXIT

To insert a new node at the end

Step 1: IF AVAIL = NULL
Write OVERFLOW
Go to Step 1
[END OF IF]
Step 2: SET = AVAIL Step
3: SET AVAIL = AVAIL NEXT
Step 4: SET DATA = VAL
Step 5: SET NEW_NODE = 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 =
Step 10: EXIT

To insert a new node before a node that has

value NUM
Step 1: IF AVAIL = NULL
Write OVERFLOW
Go to Step 12
25
[END OF IF]
Step 2: SET = 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 1 : PREPTR NEXT =NEW_NODE
Step 11: SET NEW_NODE NEXT = PTR
Step 12: EXIT

To delete the firstnode

Step 1: IF START = NULL
Write UNDERFLOW
Go to Step 5
[END OF IF]
Step 2: SET PTR = START
Step 3: SET START = START NEXT
Step 4: FREE PTR
Step 5: EXIT

To delete the last node

Step 1: IF START = NULL
Write UNDERFLOW
Go to Step 8
[END OF IF]
Step 2: SET PTR = START
Step 3: Repeat Steps 4 and 5 while PTR NEXT != NULL
Step 4: SET PREPTR = PTR
26
Step 5: SET PTR = PTR NEXT
[END OF LOOP]
Step 6: SET PREPTR NEXT = NULL
Step 7: FREE PTR
Step 8: EXIT

To delete the node after a given node

Step 1: IF START = NULL
Write UNDERFLOW
Go to Step 10
[END OF IF]
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 10 : EXIT

To delete the node before a given node

Step 1: IF START = NULL
Write UNDERFLOW
Go to Step 10
[END OF IF]
Step 2: SET PTR = START
Step 3: SET PREPTR = PTR
Step 4: Repeat Steps 5 and 6 while PTR->DATA !=
NUM
Step 5: SET PP= PREPTR
27
Step 6: SET PREPTR = PTR
Step 7: SET PTR = PTR NEXT
[END OF LOOP]
Step 8: SET PP->NEXT = PTR
Step 9: FREE PREPTR
Step 10 : EXIT

To sort the list

Step 1: IF START = NULL
Write UNDERFLOW
Go to Step 1
[END OF IF]
STEP 2: SET ptr1=START
STEP 3: SET ptr2= ptr1 -> next
STEP 4: while(ptr1 -> next != NULL)
do
SET ptr2 = ptr1 -> next;
while(ptr2 != NULL)
do
if(ptr1 -> data > ptr2 -> data)
do
SET temp = ptr1 -> data;
SET ptr1 -> data = ptr2 -> data;
SET ptr2 -> data = temp;
End of IF
SET ptr2 = ptr2 -> next;
End of while
ptr1 = ptr1 -> next;
End of while
STEP 5: End

28
Program:
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct Node
{int info;
struct Node *next;
}*start ,*p,*q,*r;
void create();
void Delete();
void display();
void main()
{
int ch;
clrscr();
start=NULL;
printf("\n\n1.create\n2.delete\n3.display\n4.exit
");
while(1)
{
printf("\n enter your choice");
scanf ("%d",&ch);
switch (ch)
{
case 1:create();break;
case 2:Delete();break;
case 3:display();break;
case 4:exit(0); break;
default : printf("wrong choice");
}
}
29
}

void create()
{p=malloc(sizeof(struct Node));
printf("\nenter data");
scanf("%d",&p->info);
p->next=NULL;
if(start==NULL)
start=p;
else
{q=start;
while(q->next!=NULL)
{q=q->next;}
q->next= p;
}
}

void Delete()
{
int n,found=0;
q=start;
if (q==NULL)
printf ("\nlinked list is empty");
else
{printf("\nenter number to be deleted");
scanf("%d",&n);
while((found==0)&&(q!=NULL))
{if (q->info==n)
found=1;
else
q=q->next;
}
30
 if (found ==0)
printf("\nno such element in linked list");
else
{if (q==start)
{start=start->next;
q->next=NULL;
free(q);
}
else
{r=start;
while(q->next!=q)
{r=r->next;
r->next=q->next;
q->next=NULL;
free(q);
}}}}}

void display()
{
if (start==NULL)
printf ("\nlinked list is empty");
else
{
q=start;
while (q!=NULL)
{printf("\t %d",q->info);
q=q->next;
}}}

31
Outcome:

32
 Experiment No: 7
Aim: Implement Circular Linked List ADT.
Theory:
Circular linked lists are typically implemented using a singly linked list data structure.
This means that each node in the list is connected to the next node via a pointer. The
last node in the list is then connected back to the first node, creating the ring-like
structure.
What is a Circular Linked List?
A circular Linked list is a unidirectional linked list. So, you can traverse it in only one
direction. But this type of linked list has its last node pointing to the head node. So
while traversing, you need to be careful and stop traversing when you revisit the head
node.

Program:
// C program for the above operation
#include <stdio.h>
#include <stdlib.h>
// Structure of a linked list node
struct node {
int info;
struct node* next;
};
// Pointer to last node in the list
struct node* last = NULL;
// Function to insert a node in the
33
// starting of the list
void insertAtFront(int data)
{
// Initialize a new node
struct node* temp;
temp = (struct node*)malloc(sizeof(struct node));
// If the new node is the only
// node in the list
if (last == NULL) {
temp->info = data;
temp->next = temp;
last = temp;
}
// Else last node contains the
// reference of the new node and
// new node contains the reference
// of the previous first node
else {
temp->info = data;
temp->next = last->next;
// last node now has reference
// of the new node temp
last->next = temp;
}
}
// Function to print the list
void viewList()
{
// If list is empty
if (last == NULL)
printf("\nList is empty\n");
// Else print the list
else {
struct node* temp;
temp = last->next;
// While first node is not
// reached again, print,
// since the list is circular
do {
printf("\nData = %d", temp->info);
temp = temp->next;
} while (temp != last->next);
34
 }
}
// Driver Code
int main()
{
// Function Call
insertAtFront(10);
insertAtFront(20);
insertAtFront(30);
// Print list
viewList();
return 0;
}
Output:
Data = 30
Data = 20
Data = 10

35
 Experiment No: 8
Aim: Implement Stack ADT using Linked List.
Theory:
If the array size cannot be determined in advance, then the other alternative, i.e., linked
representation, is used. The storage requirement of linked representation of the stack
with n elements is O(n), and the typical time requirement for the operations is O(1). 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.

Algorithm:
To insert an element in a linked stack:
Step 1: Allocate memory for the new node and
name it as NEW_NODE
Step 2: SET NEW_NODE DATA = VAL
Step 3: IF TOP = NULL
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

To delete an element from a linked stack:

Step 1: IF TOP = NULL
PRINT UNDERFLOW
[END OF IF]
Step 2: SET PTR = TOP
Step 3: SET TOP = TOP -> NEXT
36
Step 4: FREE PTR
Step 5: END

Program:
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct Node{
int info;
struct Node*next;
}*top,*p,*q;
void push();
void pop();
void Display();
void main()
{
int ch;
clrscr();
top=NULL;

printf("\n\n1.PUSH\n2.POP\n3.DISPLAY\n4.EXIT");
while(1)
{
printf("\nEnter your
choice");
scanf("%d",&ch);
switch(ch)
{
case 1: push();
break;
case 2:pop();
break;
37
 case 3:Display();
break;
case 4:exit(1);
default:printf("\nWrong
choice");
}
}
getch();
}

void push()
{
p=malloc(sizeof(struct Node));
printf("\nEnter data");
scanf("%d",&p->info);
if(top==NULL)
{
top=p;
}
else{
p->next=top;
top=p;
}
}
void pop()
{
q=top;
if(q==NULL)
printf("\nStack is empty");
else{
printf("Element
popped=%d",top->info);
38
top=top->next;
q->next=NULL;
free(q);
}
}
void Display()
{
q=top;
if(q==NULL)
printf("\nStack is empty");
Else{
printf(“\n Stack elements
are: \t”);
while(q!=NULL)
{
printf("\t%d",q->info);
q=q->next;
}}}

Outcome:

39
 Experiment No: 9
Aim: Implement Binary Search Tree ADT using Linked List.
Theory:
A binary search tree, also known as an ordered binary tree, is a variant of binary
tree in which the nodes are arranged in an order. In a binary search tree, all the nodes
in the left sub-tree have a value less than that of the root node. Correspondingly, all the
nodes in the right subtree have a value either equal to or greater than the root node.

Algorithms:
To insert a given value in a binary search tree:
InsertElement(TREE,VAL)
Step 1: Allocate memory for new variable ptr
SET ptr–>data = val
SET ptr–>left = NULL
SET ptr–>right = NULL
Step 2:
IF TREE=NULL
SET TREE=ptr
else
SET parentptr=NULL
SET nodeptr=TREE
While nodeptr!=NULL
do
SET parentptr=nodeptr
IF val<nodeptr–>data
SET nodeptr=nodeptr–>left
else
SET nodeptr = nodeptr–>right
END OF IF
IF val<parentptr–>data
SET parentptr–>left = ptr;
40
else
SET parentptr–>right = ptr;
END OF IF
END OF WHILE
END OF IF
Step 3: END

to delete a node from a binary search tree

Delete (TREE, VAL)
Step 1: IF TREE = NULL
Write "VAL not found in the tree"
ELSE IF VAL < TREE DATA
Delete(TREE->LEFT, VAL)
ELSE IF VAL > TREE DATA
Delete(TREE RIGHT, VAL)
ELSE IF TREE LEFT AND TREE RIGHT
SET TEMP = findLargestNode(TREE LEFT)
SET TREE DATA = TEMP DATA
Delete(TREE LEFT, TEMP DATA)
ELSE
SET TEMP = TREE
IF TREE LEFT = NULL AND TREE RIGHT = NULL
SET TREE = NULL
ELSE IF TREE LEFT != NULL
SET TREE = TREE LEFT
ELSE
SET TREE = TREE RIGHT
[END OF IF]
FREE TEMP
[END OF IF]
Step 2: END

41
to determine the height of a binary search tree
Height (TREE)
Step 1: IF TREE = NULL
Return 0
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

to search for a given value in a binary search tree

SearchElement (TREE, VAL)
Step 1: IF TREE DATA = VAL OR TREE = NULL
Return TREE
ELSE
IF VAL < TREE DATA
Return searchElement(TREE LEFT, VAL)
ELSE
Return searchElement(TREE RIGHT, VAL)
[END OF IF]
[END OF IF]
Step 2: END

to delete a binary search tree

deleteTree(TREE)
Step 1: IF TREE != NULL
deleteTree (TREE LEFT)
42
deleteTree (TREE RIGHT)
Free (TREE)
[END OF IF]
Step 2: END

pre-order traversal
Step 1: Repeat Steps 2 to 4 while TREE != NULL
Step 2: Write TREE DATA
Step 3: PREORDER(TREE LEFT)
Step 4: PREORDER(TREE RIGHT)
[END OF LOOP]
Step 5: END

in-order traversal
Step 1: Repeat Steps 2 to 4 while TREE != NULL
Step 2: INORDER(TREE LEFT)
Step 3: Write TREE DATA
Step 4: INORDER(TREE RIGHT)
[END OF LOOP]
Step 5: END

Post-order traversal
Step 1: Repeat Steps 2 to 4 while TREE != NULL
Step 2: POSTORDER(TREE LEFT)
Step 3: POSTORDER(TREE RIGHT)
Step 4: Write TREE DATA
[END OF LOOP]
Step 5: END

to calculate the number of nodes in a binary search tree

totalNodes(TREE)
Step 1: IF TREE = NULL
43
Return o
ELSE
Return totalNodes(TREE LEFT)
+ totalNodes(TREE RIGHT) + 1
[END OF IF]
Step 2: END

to calculate the total number of external nodes in a binary search tree

totalExternalNodes(TREE)
Step 1: IF TREE = NULL
Return 0
ELSE IF TREE LEFT = NULL AND TREE RIGHT = NULL
Return 1
ELSE
Return totalExternalNodes(TREE LEFT) +
totalExternalNodes(TREE RIGHT)
[END OF IF]
Step 2: END

to find the largest node in a binary search tree

findLargestElement(TREE)
Step 1: IF TREE = NULL OR TREE RIGHT = NULL
Return TREE
ELSE
Return findLargestElement(TREE RIGHT)
[END OF IF]
Step 2: END

to find the smallest node in a binary search tree

findSmallestElement(TREE)
Step 1: IF TREE = NULL OR TREE LEFT = NULL
Return TREE
44
ELSE
Return findSmallestElement(TREE LEFT)
[END OF IF]
Step 2: END

Program:
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
struct node
{
int data;
struct node *left;
struct node *right;
};
struct node *tree=NULL;
struct node *ins_element(struct node *,int);
struct node *search(struct node *,int);
struct node *smallest_element(struct node *);
struct node *largest_element(struct node *);
struct node *delete_element(struct node *);
int height(struct node *);
int internal_nodes(struct node *);
int external_node(struct node *);
int total_node(struct node *);
int main()
{
int ch,val,h1;
struct node *ptr;
clrscr();
do{
printf("\n1.Insert\n2.Search\n3.Smallest element\n4.Largest element
45
\n5.Delete element\n6.Height\n7.Internal nodes\n8.External nodes
\n9.Total nodes\n10.Exit\n");
printf("Enter your choice \n");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("\nEnter value of new node");
scanf("%d",&val);
tree=ins_element(tree,val);
break;
case 2:
printf("\nEnter element to be searched");
scanf("%d",&val);
tree=search(tree,val);
break;
case 3:
ptr=smallest_element(tree);
printf("\nSmallest element is %d",ptr->data);
break;
case 4:
ptr=largest_element(tree);
printf("\nLargest element is %d",ptr->data);
break;
case 5:
tree=delete_element(tree);
break;
case 6:
h1=height(tree);
printf("\nThe height of the tree is %d",h1);
break;
case 7:
46
printf("\nTotal number of
internal nodes is %d",internal_node(tree));
break;
case 8:
printf("\nTotal number of
external nodes is %d",external_node(tree));
break;
case 9:
printf("\nTotal number of nodes is %d",total_node(tree));
break;
}
}while(ch!=10);
getch();
return 0;
}
struct node *ins_element(struct node *tree,int val)
{
struct node *ptr,*nodeptr,*parentptr;
ptr=(struct node *)malloc(sizeof(struct
node));
ptr->data=val;
ptr->left=NULL;
ptr->right=NULL;
if(tree==NULL)
{ tree=ptr;
tree->left=NULL;
tree->right=NULL;
}
else
{parentptr=NULL;
nodeptr=tree;
while(nodeptr!=NULL)
47
{parentptr=nodeptr;
if(val<nodeptr->data)
nodeptr=nodeptr->left;
else
nodeptr=nodeptr->right;
}
if(val<parentptr->data)
parentptr->left=ptr;
else
parentptr->right=ptr;
}
return tree;
}
struct node *smallest_element(struct node *tree)
{
if((tree==NULL)||(tree->left==NULL))
return tree;
else
return(smallest_element(tree-
>left));
}
struct node *largest_element(struct node *tree)
{
if((tree==NULL)||(tree->right==NULL))
return tree;
else
return(largest_element(tree-
>right));
}
struct node *delete_element(struct node *tree)
{
while(tree!=NULL)
48
delete_element(tree->left);
delete_element(tree->right);
free(tree);
return tree;
}
int height(struct node *tree)
{
int leftheight,rightheight;
if(tree==NULL)
return 0;
leftheight=height(tree->left);
rightheight=height(tree->right);
if(leftheight>rightheight)
return (leftheight+1);
else
return (rightheight+1);
}
int external_node(struct node *tree)
{
if(tree==NULL)
return 0;
else if((tree->left==NULL)&&(tree-
>right==NULL))
return 1;
else
return(external_node(tree-
>left)+external_node(tree->right));
}
int internal_node(struct node *tree)
{
if((tree==NULL)||((tree-
>left==NULL)&&(tree->right==NULL)))
49
return 0;
else
return(internal_node(tree-
>left)+internal_node(tree->right)+1);
}
int total_node(struct node *tree)
{
if(tree==NULL)
return 0;
else
return(total_node(tree-
>left)+total_node(tree->right)+1);
}
struct node *search(struct node *tree,int val)
{
if((tree->data==val)||(tree==NULL))
return tree;
if(val<tree->data)
search(tree->left,val);
else
search(tree->right,val);
return 0;
}

50
Outcome:

51
 Experiment No: 10
Aim: Implement Graph Traversal techniques: a) Depth First Search b) Breadth First
Search.
Theory:
BFS:
Breadth First Traversal (or Search) for a graph is similar to Breadth First Traversal of a
tree. The only catch here is, unlike trees, graphs may contain cycles, so we may come to
the same node again. To avoid processing a node more than once, we use a boolean
visited array. For simplicity, it is assumed that all vertices are reachable from the
starting vertex.

DFS:
Depth First Traversal (or Search) for a graph is similar to Depth First Traversal of a tree.
The only catch here is, unlike trees, graphs may contain cycles, so we may come to the
same node again. To avoid processing a node more than once, we use a boolean visited
array.

Algorithm:
#Algorithm for breadth-first search
Step 1: SET STATUS = 1 (ready state)
for each node in G
Step 2: Enqueue the starting node A
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 neighbours of
N that are in the ready state
(whose STATUS = 1) and set
52
their STATUS = 2
(waiting state)
[END OF LOOP]
Step 6: EXIT

#Algorithm for depth-first search

Step 1: SET STATUS = 1 (ready state) for each
node in G
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 neighbours of N
that
are in the ready state (whose STATUS = 1) and
set their STATUS = 2 (waiting state)
[END OF LOOP]
Step 6: EXIT

Program:

/****** BFS******/
#include <stdio.h>
#define MAX 10
void breadth_first_search(int adj[][MAX],int
visited[],int start, int n)
{
int queue[MAX],rear = -1,front = -1, i;
queue[++rear] = start;
visited[start] = 1;
53
while(rear != front)
{
start = queue[++front];
if(start == 4)
printf("5\t");
else
printf("%c \t",start + 65);
for(i = 0; i < n; i++)
{
if(adj[start][i] == 1 && visited[i] == 0)
{
queue[++rear] = i;
visited[i] = 1;
}
}
}
}
int main()
{
int visited[MAX] = {0};
int adj[MAX][MAX], i, j,n;
clrscr();
printf("\n Enter no of vertices in the graph: \n");
scanf("%d",&n);
printf("\n Enter the adjacency matrix: ");
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
scanf("%d", &adj[i][j]);
breadth_first_search(adj,visited,0,n);
getch();
return 0;
}
54
Outcome:

/******* DFS********/
#include <stdio.h>
#define MAX 5
void depth_first_search(int adj[][MAX],int
visited[],int start,int n)
{
int stack[MAX];
int top = -1, i;
printf("%c\t",start + 65);
visited[start] = 1;
stack[++top] = start;
while(top!=-1)
{
start = stack[top];
for(i = 0; i < n; i++)
{
if(adj[start][i] && visited[i] == 0)
{
stack[++top] = i;
printf("%c\t", i + 65);
visited[i] = 1;
break;
}
55
}
if(i == MAX)
top--;
}
}
int main()
{
int adj[MAX][MAX];
int visited[MAX] = {0}, i, j, n;
clrscr();
printf("\n Enter number of vertices present in
the graph: \n");
scanf("%d",&n);
printf("\n Enter the adjacency matrix: ");
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
scanf("%d", &adj[i][j]);
printf("DFS Traversal: ");
depth_first_search(adj,visited,0,n);
printf("\n");
getch();
return 0;
}

Outcome:

56
 Experiment No: 11
Aim: Implement Binary Search.
Theory:
Binary search works on a principle of searching an element from a sorted array by
repeatedly dividing the search interval in half. Begin with an interval covering the whole
array. If the value of the search key is less than the item in the middle of the interval,
narrow the interval to the lower half. Otherwise narrow it to the upper half. Repeatedly
check until the value is found or the interval is empty.
Algorithm:
BINARY_SEARCH(A, ll, ul, VAL)
Step 1: [INITIALIZE] SET BEG = ll
END = ul, POSITION = - 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 POSITION = MID
PRINT POSITION
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 POSITION = -1
PRINT “VALUE IS NOT PRESENT IN THE ARRAY”
[END OF IF]
Step 6: EXIT
Program:
#include<stdio.h>
#include<conio.h>
int main()
{
int i,beg,end,mid,pos=-1,a[100],n,val;
clrscr();
printf("Enter number of elements ");
scanf("%d",&n);
printf("\nEnter sorted array");
for(i=0;i<n;i++)
57
scanf("%d",&a[i]);
printf("\nEnter number to be searched");
scanf("%d",&val);
beg=0;
end=n-1;
while(beg<=end)
{
mid=(beg+end)/2;
if(a[mid]==val)
{
pos=mid+1;
printf("\nElement found at Position %d", pos);
break;
}
else if(a[mid]>val)
end=mid-1;
else
beg=mid+1;
}
if(pos==-1)
{
printf("\n%d does not exist in
array",val);
}
getch();
return 0;
}

Outcome:

58