RUNGTA COLLEGE OF ENGINEERING & TECHNOLOGY

DEPARTMENT OF Computer Science and Engineering

LAB MANUAL

Data Structures LAB

SEMESTER 3rd

RUNGTA COLLEGE
Rungta Educational Campus,
Kohka-Kurud Road, Bhilai,
Chhattisgarh, India
Phone No. 0788-6666666
MANAGED BY : SANTOSH RUNGTA GROUP OF INSTITUTIONS

Prepared By: Prof. Anmol Agrawal

 RUNGTA COLLEGE OF ENGINEERING & TECHNOLOGY

DEPARTMENT OF Computer Science and Engineering

LAB MANUAL

Data Structure LAB

SEMESTER 3rd

PREPARED AS PER THE SYLLABUS PRESCRIBED BY

CHHATTISGARH SWAMI VIVEKANAND TECHNICAL UNIVERSITY, BHILAI

 List of DOs & DON’Ts.

(Give instructions as per < Name Of The Department > Laboratories)

DOs:

▪ Remove your shoes outside the laboratory.

▪ Come prepared in the lab regarding the experiment to be performed in the

lab.

▪ Take help from the Manual / Work Book for preparation of the experiment.

▪ For any abnormal working of the machine consult the Faculty In-charge/

Lab Assistant.

▪ Shut down the machine and switch off the power supply after performing

the experiment.

▪ Maintain silence and proper discipline in the lab.

▪ Enter your machine number in the Login register.

DON’Ts:

▪ Do not bring any magnetic material into the lab.

▪ Do not eat or drink anything in the lab.

▪ Do not tamper with the instruments in the Lab and do not disturb their

settings.
 LIST OF EXPERIMENTS
AS PER THE SYLLABUS PRESCRIBED BY THE UNIVERSITY
Chhattisgarh Swami Vivekananda Technical University, Bhilai
Branch: Computer Science and Engineering Semester: III
Subject: Data Structures Laboratory Subject Code: B022321(022)
Total Lab Periods: 36 Batch Size: 30
Maximum Marks: 40 Minimum Marks: 20

COURSE OBJECTIVES
1. To implement linear and non-linear data structures
2. To Introduce basic operations on linear and non-Linear data structures
3. To understand the different operations of search trees
4. To implement graph traversal algorithms
5. To get familiarized with sorting and searching algorithms

COURSE OUTCOMES
After successful completion of this course, the students will be able to-
1. Identify the appropriate data structure for a given problem.
2. Design various data structure algorithms and estimate their time and space complexity.
3. Apply appropriate algorithms for better utilization of memory.
4. Apply practical knowledge on the applications of data structures.
5. Solve real-world problems using sorting and searching techniques.

List of Experiments
1. Write a program to perform the following operations in the one-dimensional array:
insertion, deletion, and searching (Linear and Binary).

2. Write a program to implement stack and perform push and pop operations.

3. Write a program to convert infix to postfix or prefix expression using stack.

4. Write a program to perform the following operations on linear queue- addition, deletion,
traversing.

5. Write a program to perform the following operations in the circular queue- addition,
deletion, and traversing.

6. Write a program to perform the following operations on a double-ended queue - addition,

deletion, and traversing.

7. Write a program to perform the following operations on a single link list-creation,

inversion, and deletion.

8. Write a program to perform the following operations on a double link list – creation,
insertion, and deletion.

9. Write a program to implement polynomials in the link list and perform. a) Polynomial
arithmetic b) Evaluation of polynomial
10. Write a program to implement a linked stack and linked queue.

11. Write programs to perform Insertion, selection, and bubble sort.

12. Write a program to perform quick sorting.

13. Write a program to perform merge sorting.

14. Write a program to perform heap sort.

15. Write a program to create a Binary search tree and perform –insertion, deletion &
traversal.

16. Write a program to traverse the graph (B.F.S, D.F.S)

TEXTBOOKS

1. Fundamentals of Data Structures – Horowitz and Sahani, Galgotia Publication

REFERENCE BOOKS

1. “Data structure using C” by Samir Kumar Bandyopadhyay, KashiNathDey

2. “C and Data Structures” by Ashok K Kamthane Pearson Education.
3. “An Introduction to Data Structures with Application” by Tremblay & Sorenson ( TMH)
4. “Fundamentals of Data Structure” by Horowitz &Sahni (Golgotia)
5. “Data Structures using C/C++” by Rajesh Shukla, Wiley India
6. “Data Structures using C” by ISRD Group (TMH)
7. “Data Structures using C/C++” by Langsam, Augenstein&Tananbaum (PHI)
8. “Data Structures & Program Design” by Robert L Kruse (PHI)
 LIST OF EXPERIMENTS
AS PER RUNGTA COLLEGE OF ENGINEERING & TECHNOLOGY

LIST OF EXPERIMENTS

Exp Program page no.

No.
Write a program to perform the following 1-6
operations in the one-dimensional array:
1 a. Insertion
b. Deletion
Write a program to perform the following 7-13
operations in the one-dimensional array:
2
a. Linear Search
b. Binary Search
Write a program to perform the following 14-19
operations in the stack:
3 a. Push
b. Pop
Write a program to convert infix to postfix or 20-23
4
prefix expression using stack.
Write a program to perform the following 24-27
5 operations on linear queue- addition, deletion,
traversing.
Write a program to perform the following 28-34
6 operations in the circular queue- addition,
deletion, and traversing.
Write a program to perform the following 35-41
7 operations on a double-ended queue -
addition, deletion, and traversing
Write a program to perform the following 42-57
8 operations on a single link list-creation,
inversion, and deletion.
Write a program to perform the following 58-65
9 operations on a double link list – creation,
insertion, and deletion.
10 Write a program to implement polynomials in 66-71
the link list and perform. a) Polynomial
arithmetic b) Evaluation of polynomial
11 Write a program to implement a linked stack 72-81
and linked queue.
12 Write programs to perform Insertion, 82-90
selection, and bubble sort.
13 Write a program to perform quick sorting. 91-94
14 Write a program to perform merge sort. 95-98
15 Write a program to perform heap sort. 99-103
16 Write a program to create a Binary search tree 100-113
and perform –insertion, deletion & traversal.
17 Write a program to traverse the graph (B.F.S, 114-122
D.F.S)
 Experiment No. 1

Aim: Write a program to perform the following operations in the

one-dimensional array:
a. Insertion
b. Deletion

1.1 Insertion of an Array:

Theory:

1) Locate the position where the element in to be inserted (position may be

user-specified in case of an unsorted
2) list or may be decided by search for a sorted list).
3) Reorganize the list and create an ‘empty’ slot.
4) Insert the element.

Example

Data: 345 358 490 501 513 555 561 701 724 797

Location: 0 1 2 3 4 5 6 7 8 9

Insert 505 onto the above list:

1. Locate the appropriate position by performing a binary search. 505

should be stored in location 4.
2. Create an ‘empty’ slot
Data: 345 358 490 501 513 555 561 701 724 797

Location: 0 1 2 3 4 5 6 7 8 9 10

3. Insert 505

Data: 345 358 490 501 505 513 555 561 701 724 797

Location: 0 1 2 3 4 5 6 7 8 9

1
Algorithm

Suppose, the array to be arr[max], pos to be the position at which the element
num has to be inserted. For insertion, all the elements starting from the
position pos are shifted towards their right to make a vacant space where the
element num is inserted.

1. FOR I = (max-1) TO pos

2. arr[I] = arr[I-1]
3. arr[I] = num
4. Exit

Sample Source Code:

#include<stdio.h>

void display(int arr[],int n){

//Traversal

for(int i=0;i<n;i++){

printf("%d ",arr[i]);

printf("\n");

int indInsertion(int arr[],int size,int capacity,int element,int

index){

if(size>=capacity){

return -1;

for(int i=size-1;i>=index;i--){

arr[i+1]=arr[i];

2
 arr[index]=element;

return 1;

int main(){

int arr[100]={1,2,6,7,9};

int size=5,element=10,index=2;

display(arr,size);

//let consider we want to insert at index 2

//element to be inserted let 10

indInsertion(arr,size,100,element,index);

size=size+1;

display(arr,size);

return 0;

Outputs :
[Running] cd "d:\DSA LAB\" && gcc tempCodeRunnerFile.c -o
tempCodeRunnerFile && "d:\DSA LAB\"tempCodeRunnerFile

1 2 6 7 9

1 2 10 6 7 9

[Done] exited with code=0 in 1.876 seconds

3
Assignments:

1. Write a program to insert an element at the beginning of the given list:

55, 44, 33, 66, 18.
2. Write a program for insertion of an element after 3rd element in the above given
list.

Viva Questions:

1. What is an array?
2. Give the limitations of array.
3. Differentiate between 1-dimentional and 2-dimensional array.
4. Differentiate between static and dynamic memory allocation.
5. Is array a static or a dynamic memory system?
6. Give procedure to traverse a linear array.
7. What is ADT?
8. What is overflow?
9. What is underflow?
10. Write procedure to insert element at the beginning of the list.

1.2 Deletion of an Array:

Theory:

1. Locate the element in the list (this involves searching).

2. Delete the element.

3. Reorganize the list and index.

Example:

Data: 345 358 490 501 513 555 561 701 724 797

Location: 0 1 2 3 4 5 6 7 8 9

Delete 358 from the above list:

1. Locate 358: If we use ‘linear search’, we’ll compare 358 with each

list element starting from location 0.

4
2. Delete 358: Remove it from the list (space=10).

Data: 345 490 501 513 555 561 701 724 797

Location: 0 1 2 3 4 5 6 7 8 9

3. Reorganize the list: Move the remaining elements. (Space=9)

Data: 345 490 501 513 555 561 701 724 797? (797)

Location: 0 1 2 3 4 5 6 7 8 9

Source code:
#include<stdio.h>

void display(int arr[],int n){

//Traversal

for(int i=0;i<n;i++){

printf("%d ",arr[i]);

printf("\n");

void indDeletion(int arr[],int size,int index){

for(int i=index;i<=size-1;i++){

arr[i]=arr[i+1];

int main(){

5
 int arr[100]={1,2,6,7,9};

int size=5,index=2;

display(arr,size);

//let consider we want to delete element at index 2

indDeletion(arr,size,index);

size=size-1;

display(arr,size);

return 0;}

Outputs :
[Running] cd "d:\DSA LAB\" && gcc deletion.c -o deletion && "d:\DSA
LAB\"deletion

1 2 6 7 9

1 2 7 9

[Done] exited with code=0 in 2.024 seconds

Assignments:

1. Write a program to delete an element from the empty list.

2. Write a program to delete “AND” from “ANAND”.

Viva Questions:

1. What is an array?
2. Give the limitations of array.
3. Differentiate between 1-dimentional and 2-dimensional array.
4. Differentiate between static and dynamic memory allocation.
5. Is array a static or a dynamic memory system?
6. Give procedure to traverse a linear array.
7. What is ADT?
8. What is overflow?
9. What is underflow?
10. Write procedure to delete last element from the list.

6
 Experiment No. 2

AIM: Write a program to perform the following operations in the

one-dimensional array:
a. Linear Search
b. Binary Search

2.1 Linear Search

Theory:

In this algorithm in the set of ‘N’ data item is given—D1, D2 .... Dn having k1,
k2

.... kN, ‘N’ distinct respective keys. If the desired record is located that contains
the

key ‘ki’ then the search is successful otherwise unsuccessful. We assume that N
1.

Step 1 Initialization

Set i 1.

Step 2 Loop, Comparison

while ( i &lt; = N)

if (k = ki) then

message : ‘‘successful search’’

display (k) go to step 4

Else

Set i i + 1

7
}

End of loop.

Step 3 If no match

If (k ki) then

message : &quot;unsuccessful search&quot;.

Step 4 Finish

Exit.

Source Code:
#include<stdio.h>

int linearSearch(int arr[],int size,int element){

for(int i=0;i<size-1;i++){

if(arr[i]==element){

return i;

return -1;

int main(){

int arr[]={1,4,3,7,9,8,10};

int size = sizeof(arr)/sizeof(int);

int element = 8;

8
 int searchIndex=linearSearch(arr,size,element);

printf("the element %d is found at index %d",element,searchIndex);

return 0;

Output:
[Running] cd "d:\DSA LAB\" && gcc tempCodeRunnerFile.c -o
tempCodeRunnerFile && "d:\DSA LAB\"tempCodeRunnerFile

the element 8 is found at index 5

[Done] exited with code=0 in 1.114 seconds

Assignments:

1. Write a program to find “AND” from “ANAND”.

2. Write a program to find the occurrence of a given character from a string.

Viva Questions:

1. What is meant by searching?

2. Differentiate between searching and traversing.
3. What is linear search?
4. What is meant by complexity of an algorithm?
5. What is the complexity of linear search?

9
2.2 Binary Search:
Theory:

Procedure Bsearch (K, N):

The above procedure searches the desired data item having key ‘K’ from the

ordered set of data items. The set consists of ‘N’ data items having ‘N’ distinct
keys

such that,

k1 &lt; k2 &lt; k3 &lt; .... &lt; kN. This procedure searches for a given
argument K,

Step 1 Initialization.

Set l 1, u N.

Step 2 Middle key, loop.

while (u &gt; = l)

Set m=1.

if (K = km) then

Message : &quot;successful search&quot;.

display (K).

else if (K &gt; km)

Set l m + 1.

else

Set u m – 1.

10
}

End of loop.

Step 3 Return at the point of call.

Return.

Source Code:
#include<stdio.h>

int binarySearch(int arr[],int size,int element){

int mid,high=size-1,low=0;

//keep searching until low<=high

while (low <= high)

mid = (high + low) / 2;

if (arr[mid] == element)

return mid;

if (arr[mid] < element)

low = mid + 1;

else

11
 high = mid - 1;

return -1;

//end searching

int main(){

//sorted array for binary search

int arr[]={1,3,5,7,9,13,17,19};

int size = sizeof(arr)/sizeof(int);

int element = 17;

int searchIndex=binarySearch(arr,size,element);

printf("the element %d is found at index %d",element,searchIndex);

return 0;

Output:
[Running] cd "d:\DSA LAB\" && gcc tempCodeRunnerFile.c -o
tempCodeRunnerFile && "d:\DSA LAB\"tempCodeRunnerFile

the element 17 is found at index 6

[Done] exited with code=0 in 1.204 seconds

12
Assignments:

1. Write a program to find “AND” from “ANAND”.

2. Write a program to find the occurrence of a given character from a string.

Viva Questions:

1. What is meant by searching?

2. Differentiate between searching and traversing.
3. What is binary search?
4. What is meant by complexity of an algorithm?
5. Give the complexity of binary search.
6. Why we divide the list in binary search?
7. Why is it necessary to sort the list?

13
 EXPERIMENT No. 3

AIM: Write a program to perform the following operations in the

stack:

a. Push
b. Pop

Theory:
Procedure Create (S) :
The function creates the stack ‘S’. The SIZE variable denotes the maximum limit of an
array it is assumed that its size is such that it can accomodate n number of elements. The
variable ‘top’ holds the topmost index of array. Initially top stores the value –1, which
shows stack is empty.
Step 1 Initialize variable top with value as – 1.
Set top 🡨 –1.
Step 2 Return at the point of call.
Return.
Function IsEmpty (S) :
This Function checks the empty condition in a stack S. The Function returns true if it
is empty otherwise false.
Step 1 Checking, Is Empty ;
if (top = –1) then
return true
else
return false
The above function can also be written by using ternary operator as follows:

Boolean IsEmpty (stack * S)

{
return ( (S 🡪top = = –1 ) ? TRUE: FALSE) ) ;
}

Function IsFull (S) :

The above Function checks whether there exists a stack overflow or not. It returns true
if stack overflow occurs otherwise it returns false.
Step 1 Checking Is Full?
if (top >= SIZE –1 ) then
return true
else

14
 return false.
The above function can also be written by using ternary operator as follows:
Boolean IsFull (stack * S)
{
return ( ( S 🡪 top > = SIZE —1 ) ? TRUE : FALSE ;
}
Procedure push (S, n) :
The above procedure inserts an element stored in variable ‘n’ to the top of the stack
‘S’. Variable ‘top’ holds the index of the topmost element. Stack overflow condition can
be checked by making a call to function IsFull.
Step 1 Is overflow?
if (! IsFull (S) then R Call to IsFull
Set top 🡨 top +1
Set S [top] 🡨 n.
else
message : “STACK OVERFLOW”
Step 2 Return of the point of call .
The above function can also be written in the following way:
void push (stack *S, int n )
{
if (! IsFull (S))
{
S 🡪 item [++ S 🡪 top] = n ;
}
else
printf (‘‘\n STACK OVERFLOW’’ ) ;
}
Function Pop (S) :
This Procedure deletes an element from the stack ‘S’ variable ‘top’ holds the topmost
elements index. Stack underflow (empty) condition can be checked by making a call to
Function IsEmpty.

Step 1 1s Empty?
if (! 1sEmpty (S)) then
Set temp 🡨 S [top]
Set top 🡨 top –1
else
message : ‘STACK UNDERFLOW’
Step 2 Return at the point of call.
return(temp)

15
Source Code:

#include<stdio.h>

#include<stdlib.h>

struct stack{

int size;

int top;

int* arr;

};

//check if stack is empty

int isEmpty(struct stack * s1){

if(s1->top==-1){

return 1;

else{

return 0;

// check if stack is full

int isFull(struct stack* s1){

if(s1->top==s1->size-1){

return 1;

else{

return 0;

// push operation

16
void push(struct stack* s1,int val){

if(isFull(s1)){

printf("Stack Overflow! cannot push %d to the stack \n",val);

else{

s1->top++;

s1->arr[s1->top]=val;

//pop operation

void pop(struct stack* s1){

if(isEmpty(s1)){

printf("Stack Underflow!, No element available in stack to

pop\n");

else{

int val=s1->arr[s1->top];

s1->top--;

printf("Popped stack element is : %d\n",val);

int main(){

//using call by value

// struct stack s;

// s.size=80; //size of stack you want to create

// s.top=-1; //telling stack is empty

// s.arr=(int*)malloc(s.size*sizeof(int)); //dynamically alocated

80xsizeof(int) to arr pointer

//call by reference

17
 struct stack *sp=(struct stack*)malloc(sizeof(struct stack));
//structure point will store address of the structure

printf("Enter the size of stack you want:\n");

scanf("%d",&sp->size); //take 3 as stack size

sp->top=-1;

sp->arr=(int *)malloc(sp->size*sizeof(int));

printf("%d\n",isFull(sp)); //false

printf("%d\n",isEmpty(sp)); //true

push(sp,2); //top=0

push(sp,4); //top=1

push(sp,5); //top=2

push(sp,3); //stack overflow

printf("%d\n",isFull(sp)); //true

printf("%d\n",isEmpty(sp)); //false

pop(sp); //top=1

pop(sp); //top=0

pop(sp); //top=-1

pop(sp); //stack underflow

printf("%d\n",isFull(sp)); //false

printf("%d\n",isEmpty(sp)); //true

return 0;

18
Output:
PS D:\DSA LAB> cd "d:\DSA LAB\" ; if ($?) { gcc stackOperation.c -o stackOperation } ; if
($?) { .\stackOperation }
Enter the size of stack you want:
3
0
1
Stack Overflow! cannot push 3 to the stack
1
0
Popped stack element is : 5
Popped stack element is : 4
Popped stack element is : 2
Stack Underflow!, No element available in stack to pop
0
1
PS D:\DSA LAB>

Assignments:

1. Write a program to implement Towers of Hanoi.

2. Write a program to insert the following list into an empty stack:
A B C D E.

Viva Questions:
1. What is stack?
2. Give real time example of stack?
3. What is meant by push and pop?
4. When overflow will occur in stack?
5. When underflow will occur in stack?
6. What is the significance of top pointer?

19
 EXPERIMENT No.4
Aim:- Write a program to convert infix expression into postfix
expression using stack.

Theory:

Suppose Q is an arithmetic exp written in infix notation. This algorithm finds the equivalent
postfix expression P.
1. Push “(“onto stack and add “)” to the end of Q.
2. Scan Q from left to right and repeat steps 3 to 6 for each element of Q until the stack is
empty.
3. If an operand is encountered add it to p.
4. If a left parenthesis is encountered push it onto stack.
5. If an operator is encountered then:
a. Repeatedly pop from stack.
b. add operator to stack.
6. If right parenthesis is encountered then:
a. Repeatedly pop from stack.
b. Remove the left parenthesis.
7. Exit.

Source code:

#include<stdio.h>
#include<ctype.h>
#include<string.h>
#include<stdlib.h>
#include<conio.h>
#define SIZE 20

typedef struct stack_t

{
int top;
char item[SIZE];
} stack;

/********** Function Declaration begins **********/

void create (stack *S);
void push(stack *, char ch[]);
void pop(stack *);
void infix_to_postfix();
/********** Function Declaration ends **********/
int m,l;
char A[40],c;

void main()

20
{
clrscr();
printf(“\n\ t Program to covert infix expression into postfix expression; “);
printf(“\n\t Enter your expression & to quit enter fullstop(.) :”);
while((c=getc(stdin))!=’\n’)
{
A[m]=c;
m++;
}
l=m;
infix_to_postfix ();
getch();
}

/********** Creating an empty stack **********/

/********** Function Definition begins **********/
void create(stack *S)
{

S->top = 0 ;
}
/********** Function Definition ends **********/
/********** Pushing an element in stack **********/
/********** Function Definition begins **********/
void push(stack *S, char A[])
{
if(S->top >= SIZE)
{
printf(“\nStack is full”);
}
else
{

S->item[S->top] = A[m];
S->top = S->top+1;
}
}
/********** Function Definition ends **********/
/********** Popping an element from stack **********/
/********** Function Definition begins **********/
void pop(stack *S)
{

if (S->top < 0)
{
printf(“\n Stack is empty”);
}
else
{
if(S->top >=0)

21
 {
S->top = S->top-1;
if(S->item[S->top]!=’(‘)
printf(“%c”,S->item[S->top]);
}
}

}
/********** Function Definition ends **********/
/********** Infix to Postfix conversion **********/
/********** Function Definition begins **********/
void infix_to_postfix()
{
stack S;
create(&S);
m=0;
while(m<l)
{
switch(A[m])
{
case ‘+’ :
case ‘-’ :
while(S.item[S.top-1] ==’-’ || S.item[S.top-1] ==’+’ ||S.item[S.top-1]
==’*’ ||S.item[S.top-1] ==’/’ ||S.item[S.top-1] ==’^’ && S.item[S.top-1] !=’(‘)
pop(&S);
push(&S,A);
++m;
break;
case ‘/’ :
case ‘*’ :
while(S.item[S.top-1] ==’*’ ||S.item[S.top-1] ==’/’ ||S.item[S.top-1]
==’^’ && S.item[S.top-1] !=’(‘)
pop(&S);
push(&S,A);
++m;
break;
case ‘^’ :
push(&S,A);
++m;
break;
case ‘(‘ :
push(&S,A);
++m;
break;
case ‘)’ :
while(S.item[S.top-1]!=’(‘)
pop(&S);
pop(&S);
++m;
break;

22
 case ‘.’ :
while (S.top >= 0)
pop(&S);
exit(0);
default : if(isalpha(A[m]))
{
printf(“%c”,A[m]);
++m;
break;
}
else
{
printf(“\n some error”);
exit(0);
}
}
}
}
/********** Function Definition ends **********/

Output:

Program to covert infix expression into postfix expression;

Enter your expression & to quit enter fullstop(.) :A+B/C-D.
ABC/+D-

Assignments:

1. Write a program to convert an infix expression to prefix expression.

2. Write a program to convert postfix expression to infix expression.

Viva Questions:

1. What is stack?
2. What are the operations performed on stack?
3. Explain push and pop operations of stack.
4. What is meant by binary expression?
5. What is meant by prefix expression?
6. What is meant by infix expression?
7. What is meant by postfix expression?
8. Write different applications of stack?
9. Convert the following infix expression into postfix expression
A + (B * C –(D / E ^ F) * G ) * H

23
 EXPERIMENT No. 5
Aim: - Write a program to perform following operations in linear
queue-addition, deletion, and traversing.

Theory:

Procedure createQ(Q):
The above procedure creates an empty queue. Variable front and rear set to value – 1.

Step 1 [setting values to –1]

Set Q (front) 🡨 –1.
Set Q (rear) 🡨 – 1.
Step2 [return at the point of call]
Return.

Procedure Enqueue (Q , item):

This procedure inserts an element ‘item’ at the rear-end of the queue, ‘Q’ only when it
is not full. Variable ‘rear’ points to the element recently inserted. Queue overflow
condition can be checked by making a call to Function ‘IsFull’.
Step 1 [checking overflow condition]
call to IsFull.
if (IsFull (Q)) then
message: ‘Queue overflow’
return .
else goto step 2
Step 2 [setting rear, insert item value]
Set Q (rear) 🡨 Q(rear) + 1.
Set Q (item [a (rear))] 🡨 item.
Step 3 [setting front value]
if (Q (front) = – 1) then
Set Q (front) 🡪 0.
Return.

Function Dequeue (Q):

The above Function deletes an element from the queue ‘Q’. Queue empty condition is
checked by making a call to ‘IsEmpty’.
Step 1 [Is Empty, call to IsEmpty]
if (IsEmpty (Q)) then
message ‘Queue Empty’
return .

24
 else goto step 2.
Step 2 [Deletion of an element]
Set temp 🡨 Q (item [Q (front)]).
Step 3 [setting front and rear, if queue is empty]
if Q (front) = Q(rear)) then
Set Q (front) 🡨 – 1.
Set Q (rear) 🡨 – 1.
else
Set Q(front) 🡪 Q(front) + 1.
Step 4 [return value at the time of call]
return (temp).

Source code:
#include<stdio.h>
#include<stdlib.h>

struct Queue {
int size;
int f;
int r;
int * arr;
};
int isFull(struct Queue* q){
if(q->r==q->size-1){
return 1;
}
else{
return 0;
}
}
int isEmpty(struct Queue* q){
if(q->r==q->f){
return 1;
}
else{
return 0;
}
}
void enqueue(struct Queue * q,int val){
if(isFull(q)){

25
 printf("The queue is full\n");
}
else{
q->r++;
q->arr[q->r]=val;
}
}
int dequeue(struct Queue *q){
int a=-1;
if(isEmpty(q)){
printf("Queue is Empty \n");
}
else{
q->f++;
a=q->arr[q->f];
}
return a;
}
int main(){
struct Queue q;
//q=(struct Queue *)malloc(sizeof(struct Queue));
printf("Enter the size of queue you want to create \n");
scanf("%d",&q.size);
q.f=q.r=-1;
q.arr=(int *)malloc(q.size*sizeof(int));
if(isEmpty(&q)){
printf("Queue is empty\n");
}
// Enqueue few elements
enqueue(&q,5); //&q because we have to give value to pointer and
pointer store address which we get using &
enqueue(&q,7);
enqueue(&q,8);
enqueue(&q,10);
printf("dequeueing element %d \n",dequeue(&q));
printf("dequeueing element %d \n",dequeue(&q));
printf("dequeueing element %d \n",dequeue(&q));
printf("dequeueing element %d \n",dequeue(&q));
return 0;
}

26
Output:

PS D:\DSA LAB> cd "d:\DSA LAB\.vscode\" ; if ($?) { gcc tempCodeRunnerFile.c -o

tempCodeRunnerFile } ; if ($?) { .\tempCodeRunnerFile }
Enter the size of queue you want to create
3
Queue is empty
The queue is full
dequeueing element 5
dequeueing element 7
dequeueing element 8
Queue is Empty
dequeueing element -1
PS D:\DSA LAB\.vscode>

Assignment:

1. Consider the following linear queue of characters, implemented as array of six memory
locations FRONT = 2, REAR = 3, QUEUE: ,A, D, , , . describe the queue as the
following operation takes place: ADD “S”.

Viva Questions:

1) What is a linear queue?

2) What is rear and front pointer?
3) Give real time example of queue?
4) State different applications of stack.
5) Give array representation of queue?

27
 EXPERIMENT No.6
Aim:- Write a program to perform following operations
operation in circular queue- addition, deletion, and traversing.

Theory:
Procedure EnCqueue (Q, data):
This procedure inserts value data in circular queue.
Step 1 [If Empty]
if (CQ (front = – 1) then
{
Set CQ (front) 🡨 0.
Set CQ (rear) 🡨 0 .
}
elseif (CQ (rear) = (SIZE – 1) then
Set CQ (rear) = 0.
else
Set CQ(rear) 🡨 CQ(rear) + 1.
Step 2 [Inserts value at rear end]
Set CQ (item [CQ (rear)]) 🡨 data.
Step 3 return at the point of call
Return.

Function DeCqueue (CQ):

This Function deletes an element from circular queue.
Step 1 [copying front index value to temporary variable]
Set data 🡨 CQ (item [Q(front)]
Step 2 [setting values.]
if (CQ (front) = CQ(rear))
{
Set CQ (front) = – 1.
Set CQ(rear) = – 1.
}
elseif (CQ(front) = SIZE – 1)
Set CQ (front) = 0.
else
Set CQ(front ) 🡨 CQ (front) + 1.
Step 3 [return value at the time of call.]
Return (data).

Procedure Qcreate (Q):

The above Procedure creates Q by setting pointer variables ‘front’ and ‘rear’ value to
NULL.

28
 Step 1 [setting value to NULL]
Set Q(front) 🡨 NULL.
Set Q(rear) 🡨 NULL.
Step 2 [return at the point of call]
Return.

Source code:

#include<stdio.h>
#include<conio.h>
#define SIZE 20

typedef struct circularq_t

{
int front,rear;
int item[SIZE];
}circularQ;
/********** Function Declaration begins **********/
void create(circularQ *);
void display(circularQ *);
void encqueue(circularQ *, int);
void decqueue(circularQ *, int);
/********** Function Declaration ends **********/

void main()
{
int data,ch;
circularQ CQ;
clrscr();
create(&CQ);
printf(“\n\t\t Program shows working of circular queue”);
do
{
printf(“\n\t\t Menu”);
printf(“\n\t\t 1: encequeue”);
printf(“\n\t\t 2: decqueue “);
printf(“\n\t\t 3: exit. “);
printf(“\n\t\t Enter choice : ”);
scanf(“%d”,&ch);
switch(ch)
{
case 1:
printf(“\n Enter data:”);
scanf(“%d”,&data);
encqueue(&CQ,data);
printf(“\n Elements in a circular queue are : ”);

29
 display(&CQ);
continue;
case 2:
decqueue(&CQ,data);
if (CQ.front==0)
continue;
else
{
printf(“\n Elements in a circular queue are : ”);
display(&CQ);
continue;
}
case 3: printf(“\n finish”); return;
}
}while(ch!=3);
getch();
}

/********** Creating an empty circular queue **********/

/********** Function Definition begins **********/
void create(circularQ *CQ)
{
CQ->front=0;
CQ->rear =0;
}
/********** Function Definition ends **********/

/********** Inserting elements in circular queue **********/

/********** Function Definition begins **********/
void encqueue(circularQ *CQ, int data)
{
if (((CQ->rear == (SIZE-1)) && (CQ->front ==1 )) ||
(CQ->front == (CQ->rear + 1)))
{
printf(“\n Circular queue is full”);
return;
}
else
{
if (CQ->front == 0)
{
CQ->front = 1;
CQ->rear = 1;
CQ->item[CQ->rear] = data;
}
else
if(CQ->rear == SIZE-1)
{

30
 CQ->rear = 1;
CQ->item[CQ->rear] = data;
}
else
{
CQ->rear = CQ->rear +1;
CQ->item[CQ->rear] = data;
}
}
}
/********** Function Definition ends **********/

/********** Deleting element from circular queue **********/

/********** Function Definition begins **********/
void decqueue(circularQ *CQ, int data)
{
if (CQ->front == 0)
{
printf(“\n Circular queue underflow”);
return;
}
data = CQ->item[CQ->front];
CQ->item[CQ->front] = 0;
printf(“\n Element %d is deleted :”,data);
if (CQ->front==CQ->rear)
{
CQ->front =0;
CQ->rear = 0;
printf(“\n Circular queue is empty”);
}
else
if (CQ->front == (SIZE-1))
CQ->front =1;
else
CQ->front = CQ->front +1;
}
/********** Function Definition ends **********/

/********** Displaying elements of circular queue **********/

/********** Function Definition begins **********/
void display(circularQ *CQ)
{
int x;
if ((CQ->rear > 1)&&(CQ->front == (CQ->rear+1)))
{
for(x=1;x<SIZE;x++)
{
printf(“%d\t”,CQ->item[x]);

31
 }
printf(“\n”);
}
else
if(CQ->front == (CQ->rear+1))
{
for(x=CQ->rear;x<=SIZE;x++)
{
printf(“%d\t”,CQ->item[x]);
}
printf(“\n”);
}
else
if(CQ->front > (CQ->rear +1))
{
for(x=1;x<=CQ->rear;x++)
{
printf(“%d\t”,CQ->item[x]);
}
for(x=CQ->front;x<SIZE;x++)
{
printf(“%d\t”,CQ->item[x]);
}
printf(“\n”);
}
else
{
for(x=CQ->front;x<=CQ->rear;x++)
{
printf(“%d\t”,CQ->item[x]);
}
printf(“\n”);
}
}
/********** Function Definition ends **********/

Output:
Program shows working of circular queue
Menu
1: encequeue
2: decqueue
3: exit.
Enter choice : 1

32
 Enter data : 11
Elements in a circular queue are : 11
Menu
1: encequeue
2: decqueue
3: exit.
Enter choice :1
Enter data : 22
Elements in a circular queue are : 11 22
Menu
1: encequeue
2: decqueue
3: exit.
Enter choice :1
Enter data: 33
Elements in a circular queue are : 11 22 33
Menu
1: encequeue
2: decqueue
3: exit.
Enter choice : 2
Element 11 is deleted :
Elements in a circular queue are :22 33
Menu
1: encequeue
2: decqueue
3: exit.
Enter choice :2
Element 22 is deleted :
Elements in a circular queue are :33
Menu
1: encequeue
2: decqueue
3: exit.
Enter choice :2
Element 33 is deleted :
Circular queue is empty
Menu
1: encequeue
2: decqueue
3: exit.
Enter choice: 3

Assignment:

33
1. Consider the following circular queue of characters, implemented as array of six memory
locations FRONT = 2, REAR = 3, QUEUE: ,A, D, , , . Describe the queue as the
following operation takes place: ADD “S”.

Viva Questions:

1. What is a circular queue?

2. How can we convert a linear queue to a circular queue?
3. State different applications of circular queue?
4. What happened if Rear=Maxsize?
5. What happened if Rear=Maxsize and Front=1?

34
 EXPERIMENT No.7
Aim: - Write a program to perform following operations in
double ended queue addition , deletion , and traversing.

Theory:
Function Dequeue (Q):
The above function deletes node from the front of the list. A call to FreeNode Function is
made in order to return the memory to the available list.
Step 1 Initialization.
Set temp 🡨 Q(front (item)).
Set p 🡨 Q(front).
Step 2 Checking for single element.
if (Q (front) = Q (rear) then
{
Set Q (front) 🡨 NULL.
Set Q (rear) 🡨 NULL.
}
else
{
Set Q (front) 🡨Q(front (link)).
Step 3 Calling FreeNode, and returning value of temp.
call to FreeNode ( )
return.

Source code:

#include<stdio.h>
#include<conio.h>
#define SIZE 20

typedef struct dq_t

{
int front,rear;
int item[SIZE];
}deque;

/********** Function Declaration begins **********/

void create(deque *);
void display(deque *);
void insert_rear(deque *, int);
void insert_front(deque *, int);
int delete_front(deque *, int);

35
int delete_rear(deque *, int);
/********** Function Declaration ends **********/

void main()
{
int x,data,ch;
deque DQ;
clrscr();
create(&DQ);
printf(“\n\t\t Program shows working of double ended queue”);
do
{
printf(“\n\t\t Menu”);
printf(“\n\t\t 1: insert at rear end”);
printf(“\n\t\t 2: insert at front end”);
printf(“\n\t\t 3: delete from front end”);
printf(“\n\t\t 4: delete from rear end”);
printf(“\n\t\t 5: exit. “);
printf(“\n\t\t Enter choice : ”);
scanf(“%d”,&ch);
switch(ch)
{
case 1:
if (DQ.rear >= SIZE)
{
printf(“\n Deque is full at rear end”);
continue;
}
else
{
printf(“\n Enter element to be added at rear end : ”);
scanf(“%d”,&data);
insert_rear(&DQ,data);
printf(“\n Elements in a deque are : ”);
display(&DQ);
continue;
}
case 2:
if (DQ.front <=0)
{
printf(“\n Deque is full at front end”);
continue;
}
else
{
printf(“\n Enter element to be added at front end : ”);
scanf(“%d”,&data);
insert_front(&DQ,data);

36
 printf(“\n Elements in a deque are : ”);
display(&DQ);
continue;
}
case 3:
x = delete_front(&DQ,data);
if (DQ.front==0)
{
continue;
}
else
{
printf(“\n Elements in a deque are : ”);
display(&DQ);
continue;
}
case 4:
x = delete_rear(&DQ,data);
if (DQ.rear==0)
{
continue;
}
else
{
printf(“\n Elements in a deque are : ”);
display(&DQ);
continue;
}
case 5: printf(“\n finish”); return;
}
}while(ch!=5);
getch();
}

/********** Creating an empty double ended queue **********/

/********** Function Definition begins **********/
void create(deque *DQ)
{
DQ->front=0;
DQ->rear =0;
}
/********** Function Definition ends **********/

/********** Inserting element at rear end **********/

/********** Function Definition begins **********/
void insert_rear(deque *DQ, int data)
{
if ((DQ->front == 0) &&(DQ->rear == 0))

37
 {
DQ->item[DQ->rear] = data;
DQ->rear = DQ->rear +1;
}
else
{
DQ->item[DQ->rear] = data;
DQ->rear = DQ->rear +1;
}
}
/********** Function Definition ends **********/

/********** Deleting element from front end **********/

/********** Function Definition begins **********/
int delete_front(deque *DQ, int data)
{
if ((DQ->front == 0) && (DQ->rear == 0))
{
printf(“\n Underflow”);
return(0);
}
else
{
data = DQ->item[DQ->front];
printf(“\n Element %d is deleted from front :”,data);
DQ->front = DQ->front +1;
}
if (DQ->front==DQ->rear)
{
DQ->front =0;
DQ->rear = 0;
printf(“\n Deque is empty (front end)”);
}
return data;
}
/********** Function Definition ends **********/

/********** Inserting element at front end **********/

/********** Function Definition begins **********/
void insert_front(deque *DQ, int data)
{
if(DQ->front > 0)
{
DQ->front = DQ->front-1;
DQ->item[DQ->front] = data;
}
}
/********** Function Definition ends **********/

38
 /********** Deleting element from rear end **********/
/********** Function Definition begins **********/
int delete_rear(deque *DQ, int data)
{
if (DQ->rear == 0)
{
printf(“\n Underflow”);
return(0);
}
else
{
DQ->rear = DQ->rear -1;
data = DQ->item[DQ->rear];
printf(“\n Element %d is deleted from rear: ”,data);
}
if (DQ->front==DQ->rear)
{
DQ->front =0;
DQ->rear = 0;
printf(“\n Deque is empty(rear end)”);

}
return data;
}
/********** Function Definition ends **********/

/********** Displaying elements of DEQUE **********/

/********** Function Definition begins **********/
void display(deque *DQ)
{
int x;
for(x=DQ->front;x<DQ->rear;x++)
{
printf(“%d\t”,DQ->item[x]);
}
printf(“\n\n”);
}
/********** Function Definition ends **********/

Output:
Program shows working of double ended queue
Menu
1: insert at rear end

39
 2: insert at front end
3: delete from front end
4: delete from rear end
5: exit.
Enter choice : 1
Enter element to be added at rear end : 11
Elements in a deque are : 11
Menu
1: insert at rear end
2: insert at front end
3: delete from front end
4: delete from rear end
5: exit.
Enter choice :1
Enter element to be added at rear end : 22
Elements in a deque are : 11 22
Menu
1: insert at rear end
2: insert at front end
3: delete from front end
4: delete from rear end
5: exit.
Enter choice : 1
Enter element to be added at rear end : 33
Elements in a deque are : 11 22 33
Menu
1: insert at rear end
2: insert at front end
3: delete from front end
4: delete from rear end
5: exit.
Enter choice : 2
Deque is full at front end
Menu
1: insert at rear end
2: insert at front end
3: delete from front end
4: delete from rear end
5: exit.
Enter choice :3
Element 11 is deleted from front :
Elements in a deque are : 22 33
Menu
1: insert at rear end
2: insert at front end

40
 3: delete from front end
4: delete from rear end
5: exit.
Enter choice : 2
Element 11 is deleted from front :
Elements in a deque are : 22 33
Menu
1: insert at rear end
2: insert at front end
3: delete from front end
4: delete from rear end
5: exit.
Enter choice : 5

Assignment:

1. Consider the following deque of characters, implemented as array of six memory locations
FRONT = 2, REAR = 3, QUEUE: ,A, D, , , . Describe the queue as the following
operation takes place: ADD “S”.

Viva Questions:

1) What is a deque?
2) How deque is stored in memory.
3) What is the difference between circular queue and double ended queue?
4) What is the state of rear and front pointer in deque?
5) What will happen if front=null in case of deque?

41
 EXPERIMENT No. 8
Aim: - Write a program to perform following in singly linked list-
creation, insertion, and deletion .

Theory:
Function GetNode ( ):
This procedure provides ‘new’, a pointer to a free node from the available list. If no node
is available, then it displays an error message and return NULL
Step 1 [checking NULL].
if (avail = NULL) then
message : “overflow”.
return (NULL).
Step 2 [Adjusting pointers]
Set new 🡨 avail.
Set new 🡨 Next (avail).
Step 3 [return at the point of call]
return (new).

Procedure FreeNode (F):

This procedure returns node pointed by ’F’ to the available list.
Step 1 [Setting the pointers]
Set Next (F) 🡨 avail.
Set avail 🡨 Next.
Step 2 [return at the point of call]
Return.

Procedure SLCreation (START):

The above Procedure creates an empty linked list pointer variable START is set to NULL.
Step 1 [Initialization]
Set start = NULL.
Step 2 [return at the point of coll]
Return.

Function SLEmpty (START):

The Function checks the empty condition for the linked list. If the list is empty then it
returns ‘true’ otherwise ‘false’.
Step 1 [Checking empty]

42
 if (START = NULL) then
return true.
else
return false.

Procedure SLTraverssing (START):

The above Procedure traverses the whole linked list. Pointer variable ‘START’ stores the
address of the first node and ‘keep’ it to traverse the list.
Step 1 [Is Empty ?]
If (SL Empty (START)) then
message : ‘‘Empty list’’.
Return.
else go to step 2
Step 2 [Traversing the list]
Set keep 🡨 START.
loop
while (Next (keep) 🡨NULL)
display : data (keep).
Set keep 🡨 Next (keep).
End loop.
display : data (keep).

Function SLInsertionpos (START, pos):

The above Function inserts a node at a given position in a single linked list. Pointer
variable ‘START’ stores the address of the first node, and ‘keep’ tracks the NULL. Pointer
variable ‘new’ points to the new node obtained after calling the GetNode function.
Step 1 [Call to GetNode]
Set new 🡨Call to GetNode( ).
Step 2 [Checking empty ?]
if (SLEmpty (START)) then
message : “Empty list”.
first node.
Set START 🡨 new.
return (START).
else goto step 3
Step 3 [Insertion at desired position]
if (pos = 1) then
goto step 4.
else
goto step 5.

43
Step 4 [Insertion at the beginning.]
Set Next (new) 🡨 START.
Set START 🡨 new.
return (START).
Step 5 [Insertion at desired position other than beginning.]
Set count 🡨 1.
Set keep 🡨 START.
loop
while (count 🡨 pos –1)
Set keep🡨 Next (keep).
Set count 🡨 count + 1.
End of loop.
Step 6 [Setting of pointers]
Set Next (new) 🡨 Next (keep).
Set Next (keep) 🡨 new.
Step 7 [Return at the point of call.]
Return(start).

Function SLDeletionpos (START, pos):

The Function deletes node at a given position in a single linked list. Pointer variable
‘START’ stores the address of the first node and ‘keep’ tracks the NULL address. The
‘FreeNode’ operation frees the memory back to the available list. The Function returns the
current ‘START’ after deletion.
Step 1 [Is Empty ?]
if (SLEmpty (START)) then
message : “Empty list”.
return (START).
else go to step 2.
Step 2 [Deletion at the beginning]
if (pos = 1) then
goto step 3.
else
go to step 4.
Step 3 [Deletion at the beginning]
Set keep 🡨 START.
Set START 🡨 Next (START)
FreeNode (keep).
return (START).
Step 4 [Deletion at desired position.]
Set count 🡨 1.

44
 Set keep 🡨 start.
loop
while (count 🡨 pos –1)
Set prev 🡨keep.
Set keep 🡨 Next (keep).
Set count 🡨 count + 1.
End loop.
Step 5 [Setting of pointers]
Set Next (prev) 🡨 Next (keep).
Step 6 [Returning back the memory]

Source code:

8.1 Creation of Linked list:

#include<stdio.h>

#include<stdlib.h>

struct Node{

int data;

//creating pointer of type struct node it will store address of

next Struct Node

struct Node* next;

};

void linkedListTraversal(struct Node *ptr)

while (ptr != NULL)

printf("Element: %d\n", ptr->data);

ptr = ptr->next;

45
int main(){

struct Node * head;

struct Node * second;

struct Node * third;

//allocate memory for the nodes in the linked list in Heap

head=(struct Node *)malloc(sizeof(struct Node));

second=(struct Node *)malloc(sizeof(struct Node));

third=(struct Node *)malloc(sizeof(struct Node));

//link first and second node

head->data=7;

head->next=second;

//link second and third node

second->data=11;

second->next=third;

//terminate the list at the third node

third->data=8;

third->next=NULL;

//calling function LinkedListTraversal(struct Node* ptr)

linkedListTraversal(head);

printf("print after second node \n");

linkedListTraversal(second);

return 0;

46
Output:
PS D:\DSA LAB> cd "d:\DSA LAB\.vscode\" ; if ($?) { gcc linkedListCreation.c -o
linkedListCreation } ; if ($?) { .\linkedListCreation }
Element: 7
Element: 11
Element: 8
print after second node
Element: 11
Element: 8

PS D:\DSA LAB\.vscode>

8.2 Insertion in Linked List:

#include<stdio.h>

#include<stdlib.h>

struct Node{

int data;

//creating pointer of type struct node it will store address of

next Struct Node

struct Node* next;

};

void linkedListTraversal(struct Node *ptr)

while (ptr != NULL)

printf("Element: %d\n", ptr->data);

ptr = ptr->next;

//it will return element of type struct Node *

47
struct Node * insertAtFirst(struct Node * head,int data){

struct Node * ptr=(struct Node *)malloc(sizeof(struct Node));

ptr->next=head;

ptr->data=data;

head=ptr;

//head is changed

return head;

struct Node * insertAtIndex(struct Node * head,int data,int index){

struct Node * ptr=(struct Node *)malloc(sizeof(struct Node));

struct Node * p=head;

int i=0;

while(i!=index-1){

p=p->next;

i++;

ptr->next=p->next;

ptr->data=data;

p->next=ptr;

//no changes in head

return head;

struct Node * insertAtEnd(struct Node * head,int data){

struct Node * ptr=(struct Node *)malloc(sizeof(struct Node));

struct Node * p=head;

while(p->next!=NULL){

p=p->next;

48
 }

ptr->next=NULL;

ptr->data=data;

p->next=ptr;

//no changes in head

return head;

struct Node * insertAfterNode(struct Node * head,struct Node *

previousNode,int data){

struct Node * ptr=(struct Node *)malloc(sizeof(struct Node));

ptr->next=previousNode->next;

ptr->data=data;

previousNode->next=ptr;

//no changes in head

return head;

int main(){

struct Node * head;

struct Node * second;

struct Node * third;

struct Node * fourth;

//allocate memory for the nodes in the linked list in Heap

head=(struct Node *)malloc(sizeof(struct Node));

second=(struct Node *)malloc(sizeof(struct Node));

third=(struct Node *)malloc(sizeof(struct Node));

fourth=(struct Node *)malloc(sizeof(struct Node));

49
 //link first and second node

head->data=7;

head->next=second;

//link second and third node

second->data=11;

second->next=third;

//link second and third node

third->data=16;

third->next=fourth;

//terminate the list at the third node

fourth->data=8;

fourth->next=NULL;

//calling function LinkedListTraversal(struct Node* ptr)

linkedListTraversal(head);

head=insertAfterNode(head,second,13);

printf("after insertion of node after second node\n");

linkedListTraversal(head);

head=insertAtFirst(head,5);

printf("after insertion at beginning\n");

linkedListTraversal(head);

head=insertAtIndex(head,9,2);

printf("after insertion at between index 2 \n");

linkedListTraversal(head);

head=insertAtEnd(head,15);

printf("after insertion at End\n");

linkedListTraversal(head);

return 0;

50
Output:
PS D:\DSA LAB> cd "d:\DSA LAB\.vscode\" ; if ($?) { gcc linkedListInsertion.c -o
linkedListInsertion } ; if ($?) { .\linkedListInsertion }
Element: 7
Element: 11
Element: 16
Element: 8
after insertion of node after second node
Element: 7
Element: 11
Element: 13
Element: 16
Element: 8
after insertion at beginning
Element: 5
Element: 7
Element: 11
Element: 13
Element: 16
Element: 8
after insertion at between index 2
Element: 5
Element: 7
Element: 9
Element: 11
Element: 13
Element: 16
Element: 8
after insertion at End
Element: 5
Element: 7

51
Element: 9
Element: 11
Element: 13
Element: 16
Element: 8
Element: 15
PS D:\DSA LAB\.vscode>

8.3 Deletion in the linked list:

#include<stdio.h>

#include<stdlib.h>

struct Node{

int data;

//creating pointer of type struct node it will store address of

next Struct Node

struct Node* next;

};

void linkedListTraversal(struct Node * ptr)

while (ptr != NULL)

printf("Element: %d\n", ptr->data);

ptr = ptr->next;

//case 1: Delete first node from linked list

struct Node * deleteFirst(struct Node * head){ //it will return

element of type struct Node *

struct Node * ptr=head;

52
 head=head->next;

free(ptr);

//head is changed

return head;

//case 2: Delete a node from in between linked list

struct Node * deleteIndex(struct Node * head,int index){ //it will

return element of type struct Node *

struct Node * p=head;

int i=0;

while(i!=index-1){

p=p->next;

i++;

struct Node * q=p->next;

p->next=q->next;

free(q);

//head is changed

return head;

//case 3: Delete a node from the end linked list

struct Node * deleteEnd(struct Node * head){ //it will return element

of type struct Node *

struct Node * p=head;

struct Node * q=p->next;

while (q->next!=NULL)

p=p->next;

q=q->next;

53
 p->next=NULL;

free(q);

//head is changed

return head;

//case 2: Delete a node with a given value

struct Node * deleteValue(struct Node * head,int value){ //it will

return element of type struct Node *

struct Node * p=head;

struct Node * q=p->next;

while(q->data!=value && q->next!=NULL){

p=p->next;

q=q->next;

if(q->data==value){

p->next=q->next;

free(q);

return head;

int main(){

struct Node * head;

struct Node * second;

struct Node * third;

struct Node * fourth;

struct Node * fifth;

//allocate memory for the nodes in the linked list in Heap

54
head=(struct Node *)malloc(sizeof(struct Node));

second=(struct Node *)malloc(sizeof(struct Node));

third=(struct Node *)malloc(sizeof(struct Node));

fourth=(struct Node *)malloc(sizeof(struct Node));

fifth=(struct Node *)malloc(sizeof(struct Node));

//link first and second node

head->data=7;

head->next=second;

//link second and third node

second->data=11;

second->next=third;

//link third and fourth node

third->data=16;

third->next=fourth;

//link fourth and fifth node

fourth->data=8;

fourth->next=fifth;

//terminate the list at the fifth node

fifth->data=1;

fifth->next=NULL;

//calling function LinkedListTraversal(struct Node* ptr)

linkedListTraversal(head);

head=deleteFirst(head);

printf("After deleting first node:\n");

linkedListTraversal(head);

head=deleteIndex(head,2);

printf("After deleting node at index: 2\n");

linkedListTraversal(head);

head=deleteEnd(head);

55
 printf("After deleting node at End:\n");

linkedListTraversal(head);

head=deleteValue(head,16);

printf("After deleting given value from linked list:\n");

linkedListTraversal(head);

head=deleteValue(head,3);

printf("After deleting given value not present in linked list:\n");

linkedListTraversal(head);

return 0;

Output:
PS D:\DSA LAB> cd "d:\DSA LAB\.vscode\" ; if ($?) { gcc LinkedListDeletion.c -o
LinkedListDeletion } ; if ($?) { .\LinkedListDeletion }
Element: 7
Element: 11
Element: 16
Element: 8
Element: 1
After deleting first node:
Element: 11
Element: 16
Element: 8
Element: 1
After deleting node at index: 2
Element: 11
Element: 16
Element: 1
After deleting node at End:
Element: 11

56
Element: 16
After deleting given value from linked list:
Element: 11
PS D:\DSA LAB\.vscode>

Assignments:

1. Implement experiment no. 2 using linked list.

2. Implement experiment no. 4 using linked list.

Viva Questions:
1. What is a linked list?
2. Give the importance of linked list?
3. Can we implement stack and queue using linked list?
4. State applications of singly linked list?
5. What is the significance of pointers in linked list?

57
 EXPERIMENT No.9
Aim:- Write a program to perform creation , insertion , deletion
of doubly linked list.
Theory:
Procedure Dcreate (START, END)
This procedure creates an empty list. The pointer variable START and END are
assigned a sentinel value to indicate the list is empty in the beginning.
Step1 Initialization.
Set START ← NULL

Set END ← NULL

Step 2 R return at the point of call.
return

Source code:

#include <stdio.h>
#include <malloc.h>
#include<process.h>

typedef struct DList_tag

{
int data;
struct DList_tag *rlink, *llink;
}node;

/**************Function Declaration Begin**********/

node *DLcreation(node **);
void DLinsertion(node **, node **, int, int);
void DLdeletion(node **, node**);
void DLdisplay(node *, node *);
/**************Function Declaration End**********/

void main()
{
node *left=NULL,*right;
int item,pos,ch;
printf(“\n\t\tProgram for doubly linked list\n”);

do
{

58
 printf(“\n\t\tMenu”);
printf(“\n\t\t1.Create”);
printf(“\n\t\t2.Insert”);
printf(“\n\t\t3.Delete”);
printf(“\n\t\t4.Display”);
printf(“\n\t\t5.Exit”);
printf(“\n\t\tEnter choice : “);
scanf(“%d”,&ch);

switch(ch)
{
case 1:
left = DLcreation(&right);
break;
case 2:
printf(“\nEnter data :”);
scanf(“%d”,&item);
do
{
printf(“\nEnter position of insertion :”);
scanf(“%d”,&pos);
}while(pos < 1);
DLinsertion(&left,&right,item,pos);
break;
case 3:
DLdeletion(&left,&right);
break;
case 4:
printf(“\n\t**** Doubly linked list *****\n”);
DLdisplay(left,right);
break;
case 5:
exit(0);
default:
printf(“\n Wrong Choice”);
}
}while(ch!=5);
printf(“\n”);
}

/********** Creating of double linked list MENU **********/

/********** Function Definition begins **********/
node *DLcreation( node **right )
{
node *left, *new_node;
int item,ch;
*right = left = NULL;
do

59
 {
printf(“\n\t\tMenu”);
printf(“\n\t\t1.Add node”);
printf(“\n\t\t2.Quit”);
printf(“\n\t\tEnter choice : “);
scanf(“%d”,&ch);

switch(ch)
{
case 1:
printf(“\n Enter data:”);
scanf(“%d”,&item);
new_node = (node *)malloc(sizeof(node));
new_node->data = item;
new_node->rlink = NULL;
if(left == NULL)
{
new_node->llink = NULL;
left = new_node;
}
else
{
new_node->llink = (*right);
(*right)->rlink = new_node;
}
(*right) = new_node;
if(left != NULL)
(*right) = new_node;
break;
case 2:
break;
default:
printf(“\n Wrong Choice”);
}
}while(ch!=2);
return left;
}
/********** Function Definition ends **********/

/********** Insertion of node in double linked list **********/

/********** Function Definition begins **********/
void DLinsertion(node **start, node **right,int item, int pos)
{
node *new_node, *temp;
int i;
if((pos == 1) ||((*start) == NULL))
{
new_node = (node *)malloc(sizeof(node));

60
 new_node->data = item;
new_node->rlink = *start;
new_node->llink = NULL;
if((*start) != NULL)
(*start)->llink = new_node;
else
(*right) = new_node;
*start = new_node;
}
else
{
temp = *start;
i = 2;
while((i < pos) && (temp->rlink != NULL))
{
temp = temp->rlink;
++i;
}
new_node = (node *)malloc(sizeof( node));
new_node->data = item;
new_node->rlink = temp->rlink;
if(temp->rlink != NULL)
temp->rlink->llink = new_node;
new_node->llink = temp;
temp->rlink = new_node;
}
if(new_node->rlink == NULL)
*right = new_node;
}
/********** Function Definition ends **********/

/********** Deletion of node in linked list **********/

/********** Function Definition begins **********/
void DLdeletion( node **start, node **right)
{
node *temp, *prec;
int item;
printf(“\nElement to be deleted :”);
scanf(“%d”,&item);
if(*start != NULL)
{
if((*start)->data == item)
{
if((*start)->rlink == NULL)
*start = *right = NULL;
else
{
*start = (*start)->rlink;

61
 (*start)->llink = NULL;
}
}
else
{
temp = *start;
prec = NULL;
while((temp->rlink != NULL) && (temp->data != item))
{
prec = temp;
temp = temp->rlink;
}
if(temp->data != item)
printf(“\n Data in the list not found\n”);
else
{
if(temp == *right)
*right = prec;
else
temp->rlink->llink = temp->llink;
prec->rlink = temp->rlink;
}
}
}
else
printf(“\n!!! Empty list !!!\n”);
return;
}
/********** Function Definition ends **********/

/********** Displaying nodes of double linked list **********/

/********** Function Definition begins **********/
void DLdisplay(node *start, node *right)
{
printf(“\n***** Traverse in Forward direction *****\n left->”);
while(start != NULL)
{
printf(“%d-> “,start->data);
start = start->rlink;
}
printf(“right”);
printf(“\n***** Traverse in Backward direction *****\n right->”);
while(right != NULL)
{
printf(“%d-> “,right->data);
right = right->llink;
}
printf(“left”);

62
}
/********** Function Definition ends **********/

Output:
Program for doubly linked list
Menu
1.Create
2.Insert
3.Delete
4.Display
5.Exit
Enter choice : 1
Menu
1.Add node
2.Quit
Enter choice : 1
Enter data:11
Menu
1.Add node
2.Quit
Enter choice : 1
Enter data:22
Menu
1.Add node
2.Quit
Enter choice : 1
Enter data:33
Menu
1.Add node
2.Quit
Enter choice : 1
Enter data:44
Menu
1.Add node
2.Quit
Enter choice : 1
Enter data:55
Menu
1.Add node
2.Quit
Enter choice : 2

63
 Menu
1.Create
2.Insert
3.Delete
4.Display
5.Exit
Enter choice : 2
Menu
1.Create
2.Insert
3.Delete
4.Display
5.Exit
Enter choice : 2
Enter data :99
Enter position of insertion :3
Menu
1.Create
2.Insert
3.Delete
4.Display
5.Exit
Enter choice :4
**** Doubly linked list *****
***** Traverse in Forward direction *****
left->11-> 22-> 99-> 33-> 44-> 55-> right
***** Traverse in Backward direction *****
right->55-> 44-> 33-> 99-> 22-> 11-> left
Menu
1.Create
2.Insert
3.Delete
4.Display
5.Exit
Enter choice : 3
Element to be deleted :33
Menu
1.Create
2.Insert
3.Delete
4.Display
5.Exit
Enter choice : 4
**** Doubly linked list *****

64
***** Traverse in Forward direction *****
left->11-> 22-> 99-> 44-> 55-> right
***** Traverse in Backward direction *****
right->55-> 44-> 99-> 22-> 11-> left
Menu
1.Create
2.Insert
3.Delete
4.Display
5.Exit
Enter choice :5

Assignments:

1. Implement experiment no.2 using linked list.

2.Implement experiment no. 4 using linked list.

Viva Questions:
1. What is a linked list?
2. Give the importance of linked list?
3. Can we implement stack and queue using linked list?
4. State applications of doubly linked list?
5. What is the significance of pointers in linked list?

65
 EXPERIMENT No. 10

Aim:-Write a program to implement polynomial in link list and

perform
(a) Arithmetic.
(b) Evaluation.

Theory:-
Linked lists are widely used to represent and manipulate polynomials. Polynomials are the
expressions containing number of terms with non zero coefficients and exponents. Consider
the following polynomial.
p(X)=anxen+an-1xen-1+…+a1x1e+a
where ai a are nonzero coefficients.
ei a are exponents such that
In the linked representation of polynomials, each term is considered as a node. And such a
node contains three fields.
1.Coefficent field 2.Exponent field 3.Link field.
The coefficient field holds the value of the coefficient of a term and the exponent field
contains the exponent value of that term and the exponent field contains the exponent value
of that term. And the link field contains the addresses of the next term in the polynomial.
The logical representation of the above node is given below:

struct polynode
{
int coeff;
int expo;
struct polynode *ptr;
};
typedef struct polynode PNODE;

Two polynomials can be added. And the steps involved in adding two polynomials are given
below:
1.Read the number of terms in the first polynomial P.
2.Read the coefficients and exponents of the first polynomial.
3.Read the number of terms in the second polynomial Q.
4.Read the coefficients and exponents in the second polynomial.
5.Set the temporary pointers p and q to traverse the two polynomials respectively.
6.Compare the exponents of two polynomials starting from the first nodes.
(a) If both exponents are equal then add the coefficients and store it in the resultant linked
list.
(b) If the exponent of the current term in the first polynomial P is less than the exponent of
the current term of the second polynomial is added to the resultant linked list. And move the
pointer q to point to the next node in the second polynomial Q.

(c) If the exponent of the current term in the first polynomial P is greater than the exponent of
the current term in the second polynomial Q then the current term of the first polynomial is
added to the resultant linked list. And move the pointer p to the next node.

66
(d) Append the remaining nodes of either of the polynomials to the resultant linked list.

Source Code:-

#include<stdio.h>
#include<conio.h>
#include<limits.h>
int select();
struct rec
{
float coef;
int exp;
struct rec *next;
};
struct rec *rear;
struct rec *create(struct rec *list);
void *add(struct rec *first,struct rec *second);
struct rec *insert(double coef,int exp,struct rec *rear);
void *display(struct rec *list);
int nodes;
void main()
{
struct rec *first=NULL,*second=NULL;
int choice;
do
{
choice=select();
switch(choice)
{
case 1: first=create(first);continue;
case 2: second=create(second);continue;
case 3: add(first,second);continue;
case 4: puts("END");exit(0);
}
}while(choice!=4);
}
int select()
{
int selection;
do
{
puts("Enter 1: create the first list");
puts("Enter 2: create the second list");
puts("Enter 3: add the two list");
puts("Enter 4: END");
puts("Entr your choice");
scanf("%d",&selection);

67
}while((selection<1)||(selection>4));
return (selection);
}

struct rec *create(struct rec *x)

{
float coef;
int exp;
int endexp=INT_MAX;
struct rec *element;
puts("Enter coefs &exp:exp in descending order:""to quit enter 0 for exp");
x=(struct rec *)malloc(sizeof(struct rec));
x->next=NULL;
rear=x;
for(;;)
{
puts("Enter coefficient");
element=(struct rec*)malloc(sizeof(struct rec));
scanf("%f",&coef);
element->coef=coef;
if(element->coef==0.0)break;
puts("Enter exponent");
scanf("%d",&exp);
element->exp=exp;
if((element->exp<=0)||(element->exp>=endexp))
{
puts("Invalid exponent");
break;
}
element->next=NULL;
rear->next=element;
rear=element;
}
x=x->next;
return(x);
}
void *add(struct rec *first,struct rec *second)
{
float total;
struct rec *end,*rear,*result;
result=(struct rec *)malloc(sizeof(struct rec));
rear=end;
while((first!=NULL)&&(second!=NULL))
{
if(first->exp==second->exp)
{
if((total=first->exp+second->exp)!=0.0)
rear=insert(total,first->exp,rear);
first=first->next;

68
second=second->next;
}
Else

if(first->exp>second->exp)
{
rear=insert(first->coef,first->exp,rear);
first=first->next;
}else
{
rear=insert(second->coef,second->exp,rear);
second=second->next;
}
}
for(;first;first=first->next)
rear=insert(first->coef,first->exp,rear);
for(;second;second=second->next)
rear=insert(second->coef,second->exp,rear);
rear->next=NULL;
display(end->next);
free(end);
}
void *display(struct rec *head)
{
while(head!=NULL)
{
printf("%2lf",head->coef);
printf("%2d",head->exp);
head=head->next;
}
printf("\n");
}
struct rec *insert(double coef,int exp,struct rec *rear)
{
rear->next=(struct rec *)malloc(sizeof(struct rec));
rear=rear->next;
rear->coef=coef;
rear->exp=exp;
return(rear);
}

Output:

Enter 1 : Create the first list

Enter 2 : Create the second list
Enter 3 : Add the two list

69
Enter 4 : END
Enter your choice

1
Enter coefs & exp : exp in descending order : to quit enter 0 for exp
Enter coefficient
5
Enter exponent
4
Enter coefficient
7
Enter exponent
9
Enter coefficient
1
Enter exponent
3
Enter coefficient
0
Enter 1 : Create the first list
Enter 2 : Create the second list
Enter 3 : Add the two list
Enter 4 : END
Enter your choice

2
Enter coefs & exp : exp in descending order : to quit enter 0 for exp
Enter coefficient
9
Enter exponent
3
Enter coefficient
2
Enter exponent
2
Enter coefficient
11
Enter exponent
1
Enter coefficient
5
Enter exponent
0
Invalid exponent
Enter 1 : Create the first list
Enter 2 : Create the second list
Enter 3 : Add the two list
Enter 4 : END
Enter your choice
3

70
 5.000000 47.000000 96.000000 32.000000 211.000000 1
Enter 1 : Create the first list
Enter 2 : Create the second list
Enter 3 : Add the two list
Enter 4 : END
Enter your choice
4

Assignments:-

1. Write a program to multiply two polynomials.

2. Write a program for addition of two-variable polynomials.

Viva Questions:-

1. What is a polynomial?
2. What is a two variable polynomial?
3. Give pictorial representation of addition of two polynomials.
4. Can overflow occur in link list?
5. What is dynamic memory allocation?

71
 EXPERIMENT No. 11

Aim:- Write programs to implement linked stack and linked

queue.

11.1 Linked Stack:

Theory:-

Pushing:-

1. Input the data element to be pushed.

2. Create a NewNode.
3. NewNode 🡪 DATA=DATA.
4. NewNode 🡪 Next=TOP.
5. TOP=NewNode.
6. Exit.

Popping:-

1. If(TOP is equal to NULL)

(a) Display “The Stack is empty”.
2. Else
(a) TEMP=TOP.
(b) Display “The popped element is TOP🡪DATA”.
(c) TOP=TOP🡪Next.
(d) TEMP🡪Next=NULL.
(e) Free the TEMP node.
3. EXIT.

Source Code:-
#include <stdio.h>
#include <malloc.h>
#include<process.h>
typedef struct link_tag
{
int data;
struct link_tag *link;
}node;

/********** Function Declaration begins **********/

node *push(node *);
node *pop(node *);
void display(node *);

72
/********** Function Declaration ends **********/

void main()
{
node *start=NULL;
int ch;

printf(“\n\t\t Program of stack using linked list”);

do
{
printf(“\n\t\tMenu”);
printf(“\n\t\t1.Push”);
printf(“\n\t\t2.Pop”);
printf(“\n\t\t3.Display”);
printf(“\n\t\t4.Exit”);
printf(“\n\t\tEnter choice : “);
scanf(“%d”,&ch);
switch(ch)
{
case 1:
start = push(start);
break;
case 2:
start = pop(start);
break;
case 3:
printf(“\n\t**** Stack *****\n”);
display(start);
break;
case 4:
exit(0);
default:
printf(“\nwrong choice : ”);
}
}
while (ch!=4);
printf(“\n”);
}

/********** Pushing an element in stack **********/

/********** Function Definition begins **********/
node *push(node *temp)
{
node *new_node;
int item;

73
 printf(“Enter an data to be pushed : “);
scanf(“%d”,&item);

new_node = ( node *)malloc(sizeof( node));

new_node->data = item;
new_node->link = temp;
temp = new_node;
return(temp);
}
/********** Function Definition ends **********/

/********** Popping an element from stack **********/

/********** Function Definition begins **********/
node *pop(node *p)
{
node *temp;

if(p == NULL)
printf(“\n***** Empty *****\n”);
else
{
printf(“Popped data = %d\n”,p->data);
temp = p->link;
free(p);
p = temp;
if (p == NULL)
printf(“\n***** Empty *****\n”);
}
return(p);
}
/********** Function Definition ends **********/

/********** Displaying elements of Multistack1 **********/

/********** Function Definition begins **********/
void display(node *seek)
{
printf(“\nTop”);
while (seek != NULL)
{
printf(“-> %d”,seek->data);
seek = seek->link;
}
printf(“->NULL\n”);
return;
}

74
/********** Function Definition ends **********/

Output:
Program of stack using linked list
Menu
1.Push
2.Pop
3.Display
4.Exit
Enter choice : 1
Enter an data to be pushed : 11
Menu
1.Push
2.Pop
3.Display
4.Exit
Enter choice : 1
Enter an data to be pushed : 22
Menu
1.Push
2.Pop
3.Display
4.Exit
Enter choice : 1
Enter an data to be pushed : 33
Menu
1.Push
2.Pop
3.Display
4.Exit
Enter choice : 3
**** Stack *****

Top-> 33-> 22-> 11->NULL

Menu
1.Push
2.Pop
3.Display
4.Exit
Enter choice : 2
Popped data = 33
Menu

75
 1.Push
2.Pop
3.Display
4.Exit
Enter choice : 2
Popped data = 22
Menu
1.Push
2.Pop
3.Display
4.Exit
Enter choice : 3
**** Stack *****
Top-> 11->NULL
Menu
1.Push
2.Pop
3.Display
4.Exit
Enter choice :2
Popped data = 11
***** Empty *****
Menu
1.Push
2.Pop
3.Display
4.Exit
Enter choice : 4

Assignments:-

1. Write a program to implement stack using array.

2. Write a program for implementing Tower of Hanoi using link list.

Viva Questions:-

1. What is a stack?
2. What are push and pop operations?
3. Give practical implementation of stack.
4. Can overflow occur in link list?
5. What is dynamic memory allocation?

76
11.2 Linked Queue:
Theory:-

Pushing:-
1. Input the data element to be pushed.
2. Create a NewNode.
3. NewNode 🡪 DATA=DATA.
4. NewNode 🡪 Next=NULL.
5. If (REAR not equal to NULL)
(a) REAR 🡪 Next=NewNode.
6. REAR=NewNode.
7. Exit.

Popping:-
1. If (FRONT is equal to NULL)
(a) Display “The Queue is empty”.
2. Else
(a) Display “The popped element is FRONT🡪DATA”.
(b) If (FRONT is not equal to REAR)
(i) FRONT=FRONT🡪Next.
(c) Else
FRONT=NULL.
3. EXIT.

Source Code:-
#include <stdio.h>
#include <malloc.h>
#include<process.h>

typedef struct queue_link

{
int data;
struct queue_link *link;
}node;

/********** Function Declaration begins **********/

void enqueue(node **, node **, int);
void dequeue(node **);
void display(node *);
/********** Function Declaration ends **********/

void main()
{
node *front = NULL, *rear = NULL;
int ch,item;

printf(“\n\t\t Program of queue using linked list”);

77
 do
{
printf(“\n\t\tMenu”);
printf(“\n\t\t1.enqueue”);
printf(“\n\t\t2.dequeue”);
printf(“\n\t\t3.display”);
printf(“\n\t\t4.exit”);
printf(“\n\t\tEnter choice : “);
scanf(“%d”,&ch);

switch(ch)
{
case 1:
printf(“Enter an data to be enqueued : “);
scanf(“%d”,&item);
enqueue(&front,&rear,item);
break;
case 2:
dequeue(&front);
break;
case 3:
printf(“\n\t**** Queue *****\n”);
display(front);
break;
case 4:
exit(0);
default:
printf(“\n wrong choice:”);
}
}
while (ch!=4);
printf(“\n”);
}

/********** Inserting elements in queue **********/

/********** Function Definition begins **********/
void enqueue( node **front,node **rear,int item)
{
node *new_node;

new_node = (node *)malloc(sizeof( node));

new_node->data = item;
new_node->link = NULL;

if ((*front) == NULL)
{
(*front) = new_node;
(*rear) = new_node;
}

78
 else
{
(*rear)->link = new_node;
(*rear) = new_node;
}
return;
}
/********** Function Definition ends **********/

/********** Deleting element from queue **********/

/********** Function Definition begins **********/
void dequeue(node **front)
{
node *temp;

if((*front) != NULL)
{
temp = *front;
(*front) = (*front)->link;
free(temp);
}
return;
}
/********** Function Definition ends **********/

/********** Displaying elements of queue **********/

/********** Function Definition begins **********/
void display(node *record)
{
printf(“\nRoot”);
while (record != NULL)
{
printf(“-> %d”,record->data);
record = (record->link);
}
printf(“->NULL\n”);
return;
}
/********** Function Definition ends **********/

Output:
Program of queue using linked list
Menu
1.enqueue
2.dequeue
3.display
4.exit
Enter choice : 1
Enter an data to be enqueued : 11

79
 Menu
1.enqueue
2.dequeue
3.display
4.exit
Enter choice : 1
Enter an data to be enqueued : 22
Menu
1.enqueue
2.dequeue
3.display
4.exit
Enter choice : 1
Enter an data to be enqueued : 33
Menu
1.enqueue
2.dequeue
3.display
4.exit
Enter choice : 3
**** Queue *****
Root-> 11-> 22-> 33->NULL
Menu
1.enqueue
2.dequeue
3.display
4.exit
Enter choice : 2
Menu
1.enqueue
2.dequeue
3.display
4.exit
Enter choice : 2
Menu
1.enqueue
2.dequeue
3.display
4.exit
Enter choice : 3
**** Queue *****
Root-> 33->NULL
Menu
1.enqueue
2.dequeue
3.display
4.exit
Enter choice : 2
Menu

80
 1.enqueue
2.dequeue
3.display
4.exit
Enter choice :3
**** Queue *****
Root->NULL
Menu
1.enqueue
2.dequeue
3.display
4.exit
Enter choice : 4

Assignments:-

1. Write a program to implement circular queue using link list.

2. Write a program for implementing priority queue using link list.

Viva Questions:-

1. What is a circular queue?

2. What are front and rear pointers?
3. Give practical implementation of priority queue.
4. Can overflow occur in link list?
5. What is a priority queue?

81
 EXPERIMENT No. 12
Aim:- Write programs to perform Insertion sort, Selection sort
and Bubble sort.

12.1 Selection Sort:

Theory:-
Procedure Selectionsort (A, n):
The above Procedure Subalgorithm sorts the given element of an array ‘A’ of ‘n’
number of elements in an ascending order. The smallest element that is located in
particular pass is denoted by variable ‘S’. The variable ‘p’ denotes the index of a pass and
position of the first element which is to be examined during a particular pass.
Step 1 Loop, repeated (n – 1) times.
Repeat through step 3 for p 🡨 1, 2, 3 ...... n – 1.
Set S🡨 p.
Step 2 Element with smallest value is obtained in every pass.
Repeat step 2 for i 🡨 p + 1, p + 2 ..... n.
if (A[S] > A[i]) then
Set S 🡨 i.
End of step 2 loop.
Step 3 Exchanging the values
if ( S🡨p) then
Set A[p] 🡨 A[S]
End of step 1 loop.
Step 4 Finish.
Return.

Source Code:-

#include<stdio.h>

void printArray(int* A,int n){

for(int i=0;i<n;i++){

printf("%d ",A[i]);

printf("\n");

void selectionSort(int * A,int n){

82
 int indexOfMin,temp;

//n is the no. of elements in the array

for(int i=0;i<n-1;i++){ //pass will star for index=0 and loop

should run n-1 times

printf("Working in pass no. :%d\n",i+1);

indexOfMin=i; //for fist pass i=0,second i=1,......(n-1)th pass

i=(n-2)

for(int j=i+1;j<=n-1;j++){

if(A[j]<A[indexOfMin]){

indexOfMin=j;

temp=A[indexOfMin];

A[indexOfMin]=A[i];

A[i]=temp;

printArray(A,n);

int main()

//passing

// 0 1 2 3 4 5 index

//|12 54 65 7 23 9 consider element at index=0 min

// 7 | 54 65 12 23 9 consider element at index=1 min

// 7 9 |65 12 23 54 consider element at index=2 min

// 7 9 12 |65 23 54 consider element at index=3 min

// 7 9 12 23| 65 54 consider element at index=4 min

// 7 9 12 23 54| 65 sorting ends

int A[]={12,54,65,7,23,9};

int n=6;

83
 printf("Before sorting: \n");

printArray(A,n); //before sorting

selectionSort(A,n);

printf("After sorting: \n");

printArray(A,n);

return 0;

Output:
PS D:\DSA LAB> cd "d:\DSA LAB\" ; if ($?) { gcc selection_sort.c -o selection_sort } ; if
($?) { .\selection_sort }
Before sorting:
12 54 65 7 23 9
Working in pass no. :1
7 54 65 12 23 9
Working in pass no. :2
7 9 65 12 23 54
Working in pass no. :3
7 9 12 65 23 54
Working in pass no. :4
7 9 12 23 65 54
Working in pass no. :5
7 9 12 23 54 65
After sorting:
7 9 12 23 54 65
PS D:\DSA LAB>

Assignments:-

1. Write a program to sort list of names in medical dictionary.

2. Write a program to implement this technique in address book.

84
Viva Questions:-

1. What is sorting?
2. Differentiate between sorting and searching.
3. Give complexity of this technique.
4. What is a pass?
5. What is worst case and average case of complexity?

12.2 Bubble Sort:

Theory:-
This algorithm sorts the element of an array ‘A’ (having n elements) in the ascending
(increasing) order. The pass counter is denoted by variable ‘P’ and the variable ‘E’ is used
to count the number of exchanges performed on any pass. The last unsorted element is
referred by variable ‘l’.

Step 1 Initialization.
Set l 🡨 n, P 🡨 1.
Step 2 loop
Repeat step 3, 4 while (P🡨n – 1).
Set E 🡨 0 R Initializing exchange variable.
Step 3 Comparison, loop.
Repeat for i 🡨 1, l, ..... l – 1.
if (A [i] > A[i + 1]) then
Set A [i] <--> A [i + 1] R Exchanging values.
Set E 🡨 E + 1.
Step 4 Finish, or reduce the size.
if (E = 0) then
Exit.
else
Set l 🡨 l – 1.

Source code:-

#include<stdio.h>

void printArray(int* A,int n){

for(int i=0;i<n;i++){

printf("%d ",A[i]);

85
 printf("\n");

void bubblesort(int * A,int n){

int temp;

for (int i = 0; i < n-1; i++)// for no. of passes

printf("Working on pass no. %d \n",i+1);

for (int j = 0; j < n-1-i; j++) //no. of swaps/comparision in

each pass

if(A[j]>A[j+1]){ //swaping

temp=A[j];

A[j]=A[j+1];

A[j+1]=temp;

printArray(A,n);

int main(){

int A[]={12,54,65,7,23,9};

int n=6;

printf("Before sorting: \n");

printArray(A,n); //before sorting

bubblesort(A,n);

printf("After sorting: \n");

printArray(A,n); //After sorting

return 0;

86
Output:
PS D:\DSA LAB> cd "d:\DSA LAB\" ; if ($?) { gcc bubbleSort.c -o bubbleSort } ; if ($?) {
.\bubbleSort }
Before sorting:
12 54 65 7 23 9
Working on pass no. 1
12 54 7 23 9 65
Working on pass no. 2
12 7 23 9 54 65
Working on pass no. 3
7 12 9 23 54 65
Working on pass no. 4
7 9 12 23 54 65
Working on pass no. 5
7 9 12 23 54 65
After sorting:
7 9 12 23 54 65
PS D:\DSA LAB>

Assignments:-

1. Write a program to sort list of names in medical dictionary.

2. Write a program to implement this technique in address book.

Viva Questions:-

1. What is sorting?
2. Differentiate between sorting and searching.
3. Give complexity of this technique.
4. What is a pass?
5. What is worst case and average case of complexity?

87
12.3 Insertion Sort:

Theory:-
Procedure Insertionsort (A, n):
The Procedure Subalgorithm sorts the elements of an array ‘A’ in an ascending order.
The array consists of ‘n’ number of elements. The variable ‘i’ is used for index and ‘t’ is a
temporary variable.
Step 1 Loop, uptil length [A].
Repeat step 1, 2 for i 🡨 2, 3, 4, 5, --- n
Set t 🡨A[i], p 🡨 i – 1
Temporary variable is set to new value, pointer is adjusted.
Step 2 Loop, comparison
Repeat while (p > 0 and t < A[p])
Set A [p +1] 🡨A[p], p🡨p – 1.
End of step 2 loop.
Step 3 Inserting element in appropriate place
Set A [p + 1] 🡨 t.
End of step 1 loop.
Step 4 Finished.
Return.

Source Code:-

#include<stdio.h>

void printArray(int* A,int n){

for(int i=0;i<n;i++){

printf("%d ",A[i]);

printf("\n");

void insertionsort(int * A,int n){

//comparision will be done for element in index 1 to n-1

int key,j;

for(int i=1;i<=n-1;i++){

88
 printf("working in pass no. %d \n",i);

key=A[i];

j=i-1;

//Loop for each pass

while(j>=0 && A[j]>key)

A[j+1]=A[j];

j--; //when A[j]<key or j=-1 then loop will end

A[j+1]=key;

printArray(A,n); //printing array after each pass

int main()

//passing

//-1 0 1 2 3 4 5

// 12| 54 65 7 23 9 i=1,key=A[1]=54,j=0

// 12 54| 65 7 23 9 i=2,key=A[2]=65,j=1

// 12 54 65| 7 23 9 i=3,key=A[3]=7,j=2

// 7 12 54 65| 23 9 i=4,key=A[4]=23,j=3

// 7 12 23 54 65| 9 i=5,key=A[5]=9,j=4

// 7 9 12 23 54 65|

int A[]={12,54,65,7,23,9};

int n=6;

printf("Before sorting: \n");

printArray(A,n); //before sorting

89
 insertionsort(A,n);

printf("After sorting: \n");

printArray(A,n);

return 0;

Output:
PS D:\DSA LAB> cd "d:\DSA LAB\" ; if ($?) { gcc insertionSort.c -o insertionSort } ; if ($?)
{ .\insertionSort }
Before sorting:
12 54 65 7 23 9
working in pass no. 1
12 54 65 7 23 9
working in pass no. 2
12 54 65 7 23 9
working in pass no. 3
7 12 54 65 23 9
working in pass no. 4
7 12 23 54 65 9
working in pass no. 5
7 9 12 23 54 65
After sorting:
7 9 12 23 54 65
PS D:\DSA LAB>

90
 EXPERIMENT No. 13
Aim:- Write a program to perform Quick sort.

Theory:-

Quick_Sort(a,l,h):
a 🡪 represents the list of elements.
l 🡪 represents the position of the first element in the list(only at the starting point, it’s value
change during the execution of the function).
h 🡪 represents the position of the last element in the list(only at starting point the value of it’s
changes during the execution of the function).

Step 1: [Initially]
low=l.
high=h.
key=a[(l+h)/2][middle element of the element of the list].

Step 2: Repeat through step 7 while (low<=high).

Step 3: Repeat step 4 while (a([low]<key)).
Step 4: low=low+1.
Step 5: Repeat step 6 while (a([high]<key)).
Step 6: high=high-1.
Step 7: if(low<=high)
(i) temp=a[low].
(ii) a[low]=a[high].
(iii) a[high]=temp.
(iv) low=low+1.
(v) high=high-1.
Step 8: if (i<high) Quick_Sort(a,l,high).
Step 9: if (low<h) Quick_Sort(a,low,h).
Step 10: Exit.

Source Code:-

#include<stdio.h>

void printArray(int* A,int n){

for(int i=0;i<n;i++){

printf("%d ",A[i]);

printf("\n");

91
int partition(int A[], int low, int high)

printf("partition performed \n");

int pivot = A[low];

int i = low + 1;

int j = high;

int temp;

do

{ while (A[i] <= pivot)

i++;

while (A[j] > pivot)

j--;

if (i < j)

temp = A[i];

A[i] = A[j];

A[j] = temp;

} while (i < j);

//swap pivot with A[j]

temp = A[low];

A[low] = A[j];

A[j] = temp;

return j;

92
void quickSort(int A[],int low, int high){

int partitionIndex;

if(low<high){

partitionIndex=partition(A,low,high); //pivot element index after

partition

printArray(A,6);

quickSort(A,low,partitionIndex-1); //sort left subarray

quickSort(A,partitionIndex+1,high); //sort right subarray

int main()

{ //passing

// 0 1 2 3 4 5 index

//(12) 54i 65 7 23 9j j>i

//(12) 9i 65 7 23 54j swapped A[i] with A[j]

//(12) 9 65i 7j 23 54 j>i

//(12) 9 7i 65j 23 54 swapped A[i] with A[j]

//(12) 9 7j 65i 23 54 i>j

//{7 9} (12) {65 23 54} swapped pivot with A[j]

partitionIndex=2

//{(7) 9} 12 {(65) 23 54} partioned into two

int A[]={12,54,65,7,23,9};

int n=6;

printf("Before sorting: \n");

printArray(A,n); //before sorting

quickSort(A,0,n-1);

printf("After sorting: \n");

printArray(A,n);

return 0;

93
Output:
PS D:\DSA LAB> cd "d:\DSA LAB\" ; if ($?) { gcc tempCodeRunnerFile.c -o
tempCodeRunnerFile } ; if ($?) { .\tempCodeRunnerFile }
Before sorting:
12 54 65 7 23 9
partition performed
7 9 12 65 23 54
partition performed
7 9 12 65 23 54
partition performed
7 9 12 54 23 65
partition performed
7 9 12 23 54 65
After sorting:
7 9 12 23 54 65
PS D:\DSA LAB>

Assignments:-

1. Write a program to sort list of names in medical dictionary.

2. Write a program to implement this technique in address book.

Viva Questions:-

1. What is sorting?
2. Differentiate between sorting and searching.
3. State complexity of this technique.
4. What is a pass?
5. What is worst case and average case of complexity?

94
 EXPERIMENT No. 14

Aim:- Write a program to perform Heap sort.

Theory:-

Procedure Heap-sort (H):

The above procedure sorts the element of a given array using heap sort technique. The
procedure makes a call to Build-Heap, and Heapify.
Step 1 Building.
Call to Build-heap (H).
Step 2 Loop, exchanging root, and fixing the heap.
for i🡨 length [H] down to 2
Set H [1] 🡨 H [i].
Set heap-size [H] 🡨heap-size [H] – 1.
Call to Heapify (H, 1).
Step 3 Return at the point of call.

Procedure Heapify (H, i):

The above Procedure fixes the heap for index ‘i’ where ‘i’ refers to the index such that
the tree rooted at H[i] is a heap. This Procedure recursively calls itself until the given heap
is fixed.
Step 1 Left child, and right child, initialization.
Set l 🡨 Lchild (i).
Set r 🡨 Rchild (i).
Step 2 Place the maximum value, left child.
if (l 🡨 heap-size [H] and H [l] > H[i]) then
Set max 🡨 l.
else
Set max 🡨 i.
Step 3 Place the maximum value, right child.
if (r <= heap-size [H] and H [r] > H [max]) then
Set max 🡨 r.
Step 4 Checking with parent
if (max ≠ i) then
Set H [i] 🡨 H [max].
Step 5 Fixing of heap.
Call to Heapify (H, max).

95
Source Code:-
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>

/* A binary tree node has data, pointer to left child

and a pointer to right child */
struct node {
int data;
struct node* left;
struct node* right;
};

int isBSTUtil(struct node* node, int min, int max);

/* Returns true if the given tree is a binary search tree

(efficient version). */
int isBST(struct node* node)
{
return (isBSTUtil(node, INT_MIN, INT_MAX));
}

/* Returns true if the given tree is a BST and its

values are >= min and <= max. */
int isBSTUtil(struct node* node, int min, int max)
{
/* an empty tree is BST */
if (node == NULL)
return 1;

/* false if this node violates the min/max constraint */

if (node->data < min || node->data > max)
return 0;

/* otherwise check the subtrees recursively,

tightening the min or max constraint */
return isBSTUtil(node->left, min, node->data - 1)
&& // Allow only distinct values
isBSTUtil(node->right, node->data + 1,
max); // Allow only distinct values

96
 }

/* Helper function that allocates a new node with the

given data and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node
= (struct node*)malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return (node);
}

/* Driver code*/
int main()
{
struct node* root = newNode(4);
root->left = newNode(2);
root->right = newNode(5);
root->left->left = newNode(1);
root->left->right = newNode(3);

// Function call
if (isBST(root))
printf("Is BST");
else
printf("Not a BST");
return 0;
}

Output:
PS D:\DSA LAB> cd "d:\DSA LAB\" ; if ($?) { gcc heap_sort.c -o heap_sort } ; if ($?) {
.\heap_sort }
Sorted array is
5 6 7 11 12 13
PS D:\DSA LAB>

97
Assignments:-

1. Write a program to sort list of names in medical dictionary.

2. Write a program to implement this technique in address book.

Viva Questions:-

1. What is sorting?
2. Differentiate between sorting and searching.
3. State complexity of this technique.
4. What is a pass?
5. What is worst case and average case of complexity?

98
 EXPERIMENT No. 15

Aim:- Write a program to perform Merge sort.

Theory:-

Procedure Mergesort (A, start, finish):

The above Procedure Subalgorithm recursively sorts given list of elements between
position “start’ and “finish” (inclusive) . Array ‘A’ contains ‘n’ number of elements.
Variables ‘length’ and ‘mid’ refer to the number of elements in the current sublist and
position of the middle element of the sublist, respectively.
Step 1 Computation, size of current sublist.
Set length 🡨 finish – start + 1.
Step 2 Condition checking, if length is one
if (length 🡨 1) then
Return.
Step 3 Calculating, middle point
Set mid 🡨 sort + [length/2]– 1.
Step 4 Solving I sublist, recursively.
Call Mergesort (A, start, mid).
Step 5 Solving II sublist, recursively.
Call Mergesort (A, mid + 1, finish).
Step 6 Merging two sublists, sorted.
Call Merge (A, start, mid + 1, finish).
Step 7 Finish.
Return.

Procedure Merge (A, first, second, third):

The above procedure subalgorithm merges the two lists and produces a new sorted list.
Temporary array 'temp' is used for holding sorted values.
Step 1 Initialisation.
Set n 🡨 0, f🡨first, S🡨second.
Step 2 Comparison, giving smallest element.
if (A[f] 🡨 A[S]) then
Set n 🡨 n + 1.
Set temp [n] 🡨 A[f].
Set f 🡨 f + 1.
else
Set n 🡨 n + 1.
Set temp [n] 🡨A[S].
Set S🡨S + 1.

99
 Step 3 Copying remaining elements
if (f 🡨 second) then
Loop
Repeat while (S🡨third)
Set n 🡨n + 1.
Set temp [n] 🡨A[S].
Set S🡨S + 1.
End loop.
else
Loop
Repeat while (f < second)
Set n🡨n + 1.
Set temp [n] 🡨 A[S].
Set f 🡨 f + 1.
End of loop.
Step 4 Copying, element to original array
Loop
Repeat for f🡨1, 2, ---- n.
A [first – 1 + f] 🡨 temp [f].
End of loop.
Step 5 Finish.
Return.

Source Code:-

#include<stdio.h>

void printArray(int* A,int n){

for(int i=0;i<n;i++){

printf("%d ",A[i]);

printf("\n");

void merge(int A[],int mid,int low,int high){

int i,j,k,B[high+1];

i=low;

j=mid+1;

k=low;

100
 while(i<=mid && j<=high){

if(A[i]<A[j]){

B[k]=A[i];

k++;

i++;

else{

B[k]=A[j];

k++;

j++;

while (i<=mid)

B[k]=A[i];

k++;

i++;

while(j<=high){

B[k]=A[j];

k++;

j++;

for(i=low;i<=high;i++){

A[i]=B[i];

printArray(A,high+1);

101
void mergeSort(int A[],int low, int high)

int mid;

if(low<high){

mid=(low+high)/2;

mergeSort(A,low,mid);

mergeSort(A,mid+1,high);

merge(A,mid,low,high);

int main()

//passing

//-1 0 1 2 3 4 5

// 12| 54 65 7 23 9

int A[]={9,14,4,8,7,5,6};

int n=7;

printf("Before sorting: \n");

printArray(A,n); //before sorting

mergeSort(A,0,n-1);

printf("After sorting: \n");

printArray(A,n); //after sorting

return 0;

102
Output:
PS D:\DSA LAB> cd "d:\DSA LAB\" ; if ($?) { gcc merge_sort.c -o merge_sort } ; if ($?) {
.\merge_sort }
Before sorting:
9 14 4 8 7 5 6
9 14
9 14 4 8
4 8 9 14
4 8 9 14 5 7
4 8 9 14 5 6 7
4 5 6 7 8 9 14
After sorting:
4 5 6 7 8 9 14
PS D:\DSA LAB>

Assignment:-

1. Write a program to sort an array in descending order obtained after merging two
separate arrays each sorted in ascending order.

Viva Questions:-

1. What is sorting?
2. Differentiate between sorting and searching.
3. State complexity of this technique.
4. What is a pass?
5. What is worst case and average case of complexity?

103
 EXPERIMENT No. 16
Aim:- Write a program to create a binary search tree and
perform insertion, deletion, and traversal.
Theory:
A particular form of binary tree suitable for searching.
A binary search tree is a binary tree that is either empty or in which each node
contains a key that satisfies the following conditions:
▪ All keys (if any) in the left subtree of the root precede the key in the
root.
▪ The key in the root precedes all keys (if any) in its right subtree.

▪ The left and right subtrees of the root are again binary search trees.

Source Code:-

16.1 Insertion
// C program to demonstrate insert
// operation in binary
// search tree.

#include <stdio.h>
#include <stdlib.h>

struct node {
int key;
struct node *left, *right;
};

// A utility function to create a new BST node

struct node* newNode(int item)
{
struct node* temp
= (struct node*)malloc(sizeof(struct node));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}

// A utility function to do inorder traversal of BST

104
void inorder(struct node* root)
{
if (root != NULL) {
inorder(root->left);
printf("%d ", root->key);
inorder(root->right);
}
}

// A utility function to insert

// a new node with given key in BST
struct node* insert(struct node* node, int key)
{
// If the tree is empty, return a new node
if (node == NULL)
return newNode(key);

// Otherwise, recur down the tree

if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);

// Return the (unchanged) node pointer

return node;
}

// Driver Code
int main()
{
/* Let us create following BST
50
/ \
30 70
/ \ / \
20 40 60 80 */
struct node* root = NULL;
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);

105
 insert(root, 80);

// Print inorder traversal of the BST

inorder(root);

return 0;
}

Output:

PS D:\DSA LAB> cd "d:\DSA LAB\" ; if ($?) { gcc BST_Insertion.c -o BST_Insertion } ; if

($?) { .\BST_Insertion }
20 30 40 50 60 70 80
PS D:\DSA LAB>

16.2 Deletion:

Source Code:
// C program to implement optimized delete in BST.
#include <stdio.h>
#include <stdlib.h>

struct Node {
int key;
struct Node *left, *right;
};

// A utility function to create a new BST node

struct Node* newNode(int item)
{
struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}

// A utility function to do inorder traversal of BST

void inorder(struct Node* root)
{

106
 if (root != NULL) {
inorder(root->left);
printf("%d ", root->key);
inorder(root->right);
}
}

/* A utility function to insert a new node with given key in

* BST */
struct Node* insert(struct Node* node, int key)
{
/* If the tree is empty, return a new node */
if (node == NULL)
return newNode(key);

/* Otherwise, recur down the tree */

if (key < node->key)
node->left = insert(node->left, key);
else
node->right = insert(node->right, key);

/* return the (unchanged) node pointer */

return node;
}

/* Given a binary search tree and a key, this function

deletes the key and returns the new root */
struct Node* deleteNode(struct Node* root, int k)
{
// Base case
if (root == NULL)
return root;

// Recursive calls for ancestors of

// node to be deleted
if (root->key > k) {
root->left = deleteNode(root->left, k);
return root;
}
else if (root->key < k) {
root->right = deleteNode(root->right, k);
return root;
}

107
// We reach here when root is the node
// to be deleted.

// If one of the children is empty

if (root->left == NULL) {
struct Node* temp = root->right;
free(root);
return temp;
}
else if (root->right == NULL) {
struct Node* temp = root->left;
free(root);
return temp;
}

// If both children exist

else {

struct Node* succParent = root;

// Find successor
struct Node* succ = root->right;
while (succ->left != NULL) {
succParent = succ;
succ = succ->left;
}

// Delete successor. Since successor

// is always left child of its parent
// we can safely make successor's right
// right child as left of its parent.
// If there is no succ, then assign
// succ->right to succParent->right
if (succParent != root)
succParent->left = succ->right;
else
succParent->right = succ->right;

// Copy Successor Data to root

root->key = succ->key;

// Delete Successor and return root

108
 free(succ);
return root;
}
}

// Driver Code
int main()
{
/* Let us create following BST
50
/ \
30 70
/ \ / \
20 40 60 80 */
struct Node* root = NULL;
root = insert(root, 50);
root = insert(root, 30);
root = insert(root, 20);
root = insert(root, 40);
root = insert(root, 70);
root = insert(root, 60);

printf("Original BST: ");

inorder(root);

printf("\n\nDelete a Leaf Node: 20\n");

root = deleteNode(root, 20);
printf("Modified BST tree after deleting Leaf Node:\n");
inorder(root);

printf("\n\nDelete Node with single child: 70\n");

root = deleteNode(root, 70);
printf("Modified BST tree after deleting single child Node:\n");
inorder(root);

printf("\n\nDelete Node with both child: 50\n");

root = deleteNode(root, 50);
printf("Modified BST tree after deleting both child Node:\n");
inorder(root);

return 0;
}

109
Output:

PS D:\DSA LAB> cd "d:\DSA LAB\.vscode\" ; if ($?) { gcc BST_Deletion.c -o

BST_Deletion } ; if ($?) { .\BST_Deletion }
Original BST: 20 30 40 50 60 70

Delete a Leaf Node: 20

Modified BST tree after deleting Leaf Node:
30 40 50 60 70

Delete Node with single child: 70

Modified BST tree after deleting single child Node:
30 40 50 60

Delete Node with both child: 50

Modified BST tree after deleting both child Node:
30 40 60
PS D:\DSA LAB\.vscode>

16.3 BST Traversal:

#include<stdio.h>
#include<stdlib.h>

struct Node {
int data;
struct Node * left;
struct Node * right;
};
struct Node * createNode(int data){
struct Node * n; //crrating a node pointer
n=(struct Node *)malloc(sizeof(struct Node));//allocatio=ng the
memory in the heap
n->data=data;//setting the data
n->left=NULL;//setting the left and right child to null
n->right=NULL;
return n;//returning the creact node of type struct node
}
void preorder(struct Node * root){
if(root!=NULL){
printf("%d ",root->data);
preorder(root->left);
preorder(root->right);
}
}

110
void postorder(struct Node * root){
if(root!=NULL){
postorder(root->left);
postorder(root->right);
printf("%d ",root->data);
}
}
void inorder(struct Node * root){
if(root!=NULL){
inorder(root->left);
printf("%d ",root->data);
inorder(root->right);

}
}
int main(){
/* constructing the root node
struct Node * p;
p=(struct Node *)malloc(sizeof(struct Node));
p->data=2;
p->left=NULL;
p->right=NULL;
//constructing the 2nd node
struct Node * p1;
p1=(struct Node *)malloc(sizeof(struct Node));
p1->data=1;
p1->left=NULL;
p1->right=NULL;
//constructing the 3rd node
struct Node * p2;
p2=(struct Node *)malloc(sizeof(struct Node));
p2->data=4;
p2->left=NULL;
p2->right=NULL;
*/

//constructing nodes using createNode function

struct Node * p=createNode(5);
struct Node * p1=createNode(3);
struct Node * p2=createNode(6);
struct Node * p3=createNode(1);
struct Node * p4=createNode(4);
//TREE

111
 // 5
// / \
// 3 6
// / \
// 1 4
//linking root with left and right child
p->left=p1;
p->right=p2;
//linking left child with its left and right child
p1->left=p3;
p1->right=p4;
//linking right child with its left and right child
p2->left=NULL;
p2->right=NULL;
//
p3->left=NULL;
p3->right=NULL;
//
p4->left=NULL;
p4->right=NULL;

//calling preorder function

printf("Preorder Traversal: \n");
preorder(p);
printf("\nPostorder Traversal: \n");
postorder(p);
printf("\nInorder Traversal: \n");
inorder(p);
return 0;
}

Output:

PS D:\DSA LAB> cd "d:\DSA LAB\" ; if ($?) { gcc tempCodeRunnerFile.c -o

tempCodeRunnerFile } ; if ($?) { .\tempCodeRunnerFile }
Preorder Traversal:
53146
Postorder Traversal:
14365
Inorder Traversal:
13456
PS D:\DSA LAB>

112
Assignments:-

1. Write a program to create a binary tree.

2. Write a program to add following nodes in the binary tree in assignment 1.
A, F, G, H

Viva Questions:-

1. What is a tree?
2. What is a binary tree?
3. Define path, degree of a tree and forest?
4. What is a forest tree?
5. What is a binary search tree?

113
 EXPERIMENT No. 17
Aim:- Write a program for traversal of graph (B.F.S., D.F.S.).

17.1 BFS:

Theory:-

Procedure BFS (G, S):

The above Procedure computes the breadth-first-search for a given graph ‘G’. Variable
‘S’ refers to the start of graph ‘G’. Three arrays color [u] holds the color of u, pre [u]
points to the predecessor of u, and dist [u] calculates the distance from S to u. The
subalgorithms Enqueue and Dequeue are also used for inserting and deleting element from
the queue.
Step 1 Initialization, loop.
for u 🡨V1, V2, ..... R For each u in V
{
Set color [u] 🡨 white.
Set dist [u] 🡨 ∞.
Set pre [u] 🡨NULL.
}
Step 2 Intializing source S, placing ‘S’ in the queue.
Set color [S] 🡨 gray.
Set dist [S] 🡨 0.
Set Q 🡨 {S} R putting S in the queue.
Step 3 Loop, while no more adjacent vertices
while (Q 🡨NULL)
{
Set u 🡨 Dequeue (Q) R u is the next to visit.
for V 🡨 Vk .... Vn R for each V in adj [u]
{
if (color [V] = white) then { R if neighbour unreached
Set color [V] 🡨gray R mark it reached.
Set dist [V] 🡨 dist [u] + 1 R set its distance.
Set pre [V] 🡨 u R set its predecessor.
call to Enqueue (Q, V) R put in the queue.
}
Set color [u] 🡨 black R u is visited.
}
Step 4 Return at the point of call.
Return.

114
Source Code:-

#include<stdio.h>
#include<conio.h>
#define SIZE 10
#define FALSE 0
#define TRUE 1

typedef int adj_mat[SIZE][SIZE];

int front=1,rear=1;
int q[SIZE];

typedef struct graph_t{

int nodes;
int *visited;
adj_mat mat;
}graph;

/**************Function Declaration Begin**********/

void BFS(graph *);
void add_queue(int[],int);
int delete_queue();
/**************Function Declaration End**********/
void main()
{
graph G;
clrscr();
printf(“\n\t\t Program shows Breath First Search in a graph ”);
printf(“\n\t\t Enter number of nodes in the graph : ”);
scanf(“%d”,&G.nodes);
BFS(&G);
getch();
}

/********** breadth first searching **********/

/********** Function Definition begins **********/
void BFS( graph *G )
{
int k,i,j;
for(k=1;k<=G->nodes;k++)
G->visited[k] = FALSE;
for(i=1;i<=G->nodes;i++)
{
for(j=1;j<=G->nodes;j++)
{
printf(“\n Enter data of vertex %d for(%d,%d) : ”,i,i,j);
printf(“\n Enter 1 for adjacent vertex and 0 otehrwise ”);
scanf(“%d”,&G->mat[i][j]);

115
 }
}
for(k=1;k<=G->nodes;k++)
{
if ( !G->visited[k] )
{
add_queue(q,k);
do
{
k= delete_queue(q);
G->visited[k] = TRUE;
for(j=1;j<=G->nodes;j++)
{
if(G->mat[k][j] == 0)
continue;
if (!G->visited[j])
{
G->visited[j] = TRUE;
add_queue(q, j);
}
}
}while(front!=rear);
}
}
printf(“\n Adjacency matrix of a graph is :\n”);
for(i=1;i<=G->nodes;i++)
{
for(k=1;k<=G->nodes;k++)
{
printf(“%d\t”,G->mat[i][k]);
}
printf(“\n”);
}
i=0;
printf(“\n Traversal of a given graph is \n”);
while(i<G->nodes)
{
printf(“%d\t”,q[++i]);
}
}
/********** Function Definition ends **********/

/********** inserting element in queue **********/

/********** Function Definition begins **********/
void enqueue(int q[], int k)
{
q[rear] = k;
rear++;

116
 }
/********** Function Definition ends **********/

/********** deleting element from queue **********/

/********** Function Definition begins **********/
int dequeue(int q[])
{
int data;
data = q[front];
front++;
if(front==SIZE)
{
front=1;
rear=1;
}
return(data);
}
/********** Function Definition ends **********/

Output:

Program shows the traversal of graph using breadth first search

Enter number of nodes in the graph : 3

Enter data of vertex 1 for (1,1) :

Enter 1 for adjacent vertex and 0 for otherwise : 0

Enter data of vertex 1 for (1,2) :

Enter 1 for adjacent vertex and 0 for otherwise : 1

Enter data of vertex 1 for (1,3) :

Enter 1 for adjacent vertex and 0 for otherwise : 1

Enter data of vertex 1 for (2,1) :

Enter 1 for adjacent vertex and 0 for otherwise : 0

Enter data of vertex 1 for (2,2) :

Enter 1 for adjacent vertex and 0 for otherwise : 0

Enter data of vertex 1 for (2,3) :

Enter 1 for adjacent vertex and 0 for otherwise : 0

Enter data of vertex 1 for (3,1) :

Enter 1 for adjacent vertex and 0 for otherwise : 0

Enter data of vertex 1 for (3,2) :

Enter 1 for adjacent vertex and 0 for otherwise : 0

117
Enter data of vertex 1 for (3,4) :
Enter 1 for adjacent vertex and 0 for otherwise : 0

Adjacency matrix of the graph is

011
000
000
Traversal of a given graph is
123

Assignments:-

1. Write a C code for creating an empty graph.

2. Write a C code for inputting graph information.
3. Write a C code for printing a graph.

Viva Questions:-

1. State different methods of graph traversal.

2. Differentiate between BFS and DFS.
3. State adjacency representation of any graph.
4. State multilist representation of any graph.
5. What is a spanning graph?

118
17.2 DFS:

Theory:-

Procedure DFSvisit (u):

The above Procedure subalgorithm processes the given vertex. It makes a recursive
call to itself. The arrays used in this procedure have been previously described.
Step 1 Start search at u, mark u visited.
Set color [u] 🡨 gray.
Set time 🡨 time + 1.
Set dis [u] 🡨 time.
Loop,
for V 🡨 Vk .... Vn R for each V in Adj [u]
{
if (color [V] = White) then R if neighbour marked unreached
Set pre [V] 🡨 u R set predecessor pointer.
Call to DFS visit (V) R processed V.
}
End Loop
Step 2 U, is visited
Set color [u] 🡨 black.
Set time 🡨 time + 1.
Set pre [u] 🡨 time.
Step 3 Return at the point of call
Return.

Procedur DFS (G):

The above Procedure computes the depth-first-search of the given ‘G’ graph ‘G’. It
takes the advantage of Procedure DFS visit ( ). All the auxillary arrays used in this
procedure have been previously described.
Step 1 Loop, initialization.
for u 🡨 V1, V2 .... Vn R for each u in V
{
Set color [u] 🡨 white.
Set pre [u] 🡨 NULL.
}
Step 2 Setting time
Set time 🡨 0.
Step 3 Loop, finding unreached vertex and start new search
for u 🡨 V1, V2 .... V R for each u in V
{
if (color = white) R found unreached vertex
Call to DFS visit (u) R start a new search.
}
Step 4 Return at point of call
Return.

119
Source Code:-

#include<stdio.h>
#include<conio.h>
#define SIZE 10
#define FALSE 0
#define TRUE 1
typedef int adj_mat[SIZE][SIZE];
typedef struct graph_t{
int nodes[SIZE];
int n;
int *visited;
adj_mat mat;
}graph;

/**************Function Declaration Begin**********/

void DFS(graph *);
void visit(graph *,int);
/**************Function Declaration End**********/

static int find=0;

void main()
{
graph G;
//clrscr();
printf(“\n\t\t Program shows the traversal of graph using Depth First Search ”);
printf(“\n\t\t Enter number of nodes in the graph : ”);
scanf(“%d”,&G.n);
DFS(&G);
getch();
}
/********** depth first searching **********/
/********** Function Definition begins **********/
void DFS( graph *G )
{
int k,i,j;
for(k=1;k<=G->n;k++)
G->visited[k] = FALSE;
for(i=1;i<=G->n;i++)
{
for(j=1;j<=G->n;j++)
{
printf(“\n Enter data of vertex %d for(%d,%d) :\n”,i,i,j);
printf(“\n Enter 1 for adjacent vertex and 0 for otherwise : ”);
scanf(“%d”,&G->mat[i][j]);
}
}
for(k=1;k<=G->n;k++)

120
 {
if ( !G->visited[k] )
visit(G, k);
}
printf(“\n Adjacency matrix of the grpah is \n”);
for(i=1;i<=G->n;i++)
{
for(k=1;k<=G->n;k++)
{
printf(“%d\t”,G->mat[i][k]);
}
printf(“\n”);
}
i=0;
printf(“\n Traversal of a given graph is \n”);
while(i<G->n)
{
printf(“%d\t”,G->nodes[++i]);
}
}
/********** Function Definition ends **********/
/********** visiting graph **********/
/********** Function Definition begins **********/
void visit( graph *G, int k )
{
int j;
G->visited[k] = TRUE;
G->nodes[++find] = k;
for(j=1;j<=G->n;j++)
{
if(G->mat[k][j] == 1)
{
if (!G->visited[j])
visit( G, j );
}
}
}
/********** Function Definition ends **********/

Output:

Program shows the traversal of graph using depth first search

Enter number of nodes in the graph : 3

Enter data of vertex 1 for (1,1) :

Enter 1 for adjacent vertex and 0 for otherwise : 0

121
Enter data of vertex 1 for (1,2) :
Enter 1 for adjacent vertex and 0 for otherwise : 1

Enter data of vertex 1 for (1,3) :

Enter 1 for adjacent vertex and 0 for otherwise : 1

Enter data of vertex 1 for (2,1) :

Enter 1 for adjacent vertex and 0 for otherwise : 0

Enter data of vertex 1 for (2,2) :

Enter 1 for adjacent vertex and 0 for otherwise:0

Enter data of vertex 1 for (2,3):

Enter 1 for adjacent vertex and 0 for otherwise : 0

Enter data of vertex 1 for (3,1) :

Enter 1 for adjacent vertex and 0 for otherwise : 0

Enter data of vertex 1 for (3,2) :

Enter 1 for adjacent vertex and 0 for otherwise : 0

Enter data of vertex 1 for (3,4) :

Enter 1 for adjacent vertex and 0 for otherwise : 0

Adjacency matrix of the graph is

011
000
000
Traversal of a given graph is
123

Assignments:-

1. Write a C code for creating an empty graph.

2. Write a C code for inputting graph information.
3. Write a C code for printing a graph.

Viva Questions:-

1. State different methods of graph traversal.

2. Differentiate between BFS and DFS.
3. State adjacency representation of any graph.
4. State multilist representation of any graph.
5. What is a spanning graph?

122