YENEPOYA INSTITUTE OF TECHNOLOGY

(Affiliated to Visvesvaraya Technological University, Belagavi) N.H. 13, Thodar,

Moodbidri, Mangaluru 574225 (D.K), Karnataka

DEPARTMENT OF
ARTIFICIAL INTELLIGENCE & MACHINE
LEARNING

LAB MANUAL
(ACADEMIC YEAR 2023-2024)

DATA STRUCTURES LABORATORY

(BCSL305)

[As per Choice Based Credit System (CBCS) scheme]

 Yenepoya Institute of Technology, Moodbidri
Department of Artificial Intelligence & Machine Learning

Vision
To be a centre of excellence to produce engineers in the field of artificial intelligence &
Machine Learning who are committed, innovation driven, self - determined, and capable of
developing applications for the improvement of society

Mission
 To expedite the students to various knowledge platforms through expertized academic
guidance and supervision.
 To inspire the students to be innovative, skilled engineers by imparting the leadership
qualities, team-spirit, and ethical responsibilities.
 To encourage faculty and students to get involved in lifelong learning, research oriented
and significantly contributing to the advancement of the civilization.

Program Educational Objectives

Artificial intelligence & Machine learning graduates will be able to

 Demonstrate technical Competence in Artificial intelligence & Machine learning and their
applications
 Design solution for problems in different domains like medical, data science by applying
Artificial intelligence & Machine learning Concepts.
 Take up Masters and Research Programs in the area of Artificial intelligence & Machine
learning.

Program Specific Outcomes

Artificial intelligence & Machine learning graduates will be able to

 Apply knowledge of Artificial intelligence & Machine learning and formulate solutions for
interdisciplinary problems
 Develop models in Data Science,Machine Learning and Big Data technologies and
integrate into real time applications
Q No Description
1 Develop a Program in C for the following:
a) Declare a calendar as an array of 7 elements (A dynamically Created array) to represent
7 days of a week. Each Element of the array is a structure having three fields. The first field
is the name of the Day (A dynamically allocated String), The second field is the date of the
Day (A integer), the third field is the description of the activity for a particular day (A
dynamically allocated String).
b) Write functions create(), read() and display(); to create the calendar, to read the data
from the keyboard and to print weeks activity details report on screen.
2 Develop a Program in C for the following operations on Strings.
a. Read a main String (STR), a Pattern String (PAT) and a Replace String (REP)
b. Perform Pattern Matching Operation: Find and Replace all occurrences of PAT in STR
with REP if PAT exists in STR. Report suitable messages in case PAT does not exist in STR
Support the program with functions for each of the above operations. Don't use Built-in
functions.
3 Develop a menu driven Program in C for the following operations on STACK of Integers
(Array Implementation of Stack with maximum size MAX)
a. Push an Element on to Stack
b. Pop an Element from Stack
c. Demonstrate how Stack can be used to check Palindrome
d. Demonstrate Overflow and Underflow situations on Stack
e. Display the status of Stack
f. Exit
Support the program with appropriate functions for each of the above operations
4 Develop a Program in C for converting an Infix Expression to Postfix Expression. Program
should support for both parenthesized and free parenthesized expressions with the
operators: +, -, *, /, % (Remainder), ^ (Power) and alphanumeric operands.
5 Develop a Program in C for the following Stack Applications
a. Evaluation of Suffix expression with single digit operands and operators: +, -, *, /, %, ^
b. Solving Tower of Hanoi problem with n disks
6 Develop a menu driven Program in C for the following operations on Circular QUEUE of
Characters (Array Implementation of Queue with maximum size MAX)
a. Insert an Element on to Circular QUEUE
b. Delete an Element from Circular QUEUE
c. Demonstrate Overflow and Underflow situations on Circular QUEUE
d. Display the status of Circular QUEUE
e. Exit
Support the program with appropriate functions for each of the above operations
7 Develop a menu driven Program in C for the following operations on Singly Linked List (SLL)
of Student Data with the fields: USN, Name, Programme, Sem, PhNo
a. Create a SLL of N Students Data by using front insertion.
b. Display the status of SLL and count the number of nodes in it
c. Perform Insertion / Deletion at End of SLL
d. Perform Insertion / Deletion at Front of SLL(Demonstration of stack)
e. Exit
8 Develop a menu driven Program in C for the following operations on Doubly Linked List
(DLL) of Employee Data with the fields: SSN, Name, Dept, Designation, Sal, PhNo
a. Create a DLL of N Employees Data by using end insertion.
b. Display the status of DLL and count the number of nodes in it
c. Perform Insertion and Deletion at End of DLL
d. Perform Insertion and Deletion at Front of DLL
e. Demonstrate how this DLL can be used as Double Ended Queue.
f. Exit
9 Develop a Program in C for the following operationson Singly Circular Linked List (SCLL)
with header nodes
a. Represent and Evaluate a Polynomial P(x,y,z) = 6x2y2z-4yz5+3x3yz+2xy5z-2xyz3
b. Find the sum of two polynomials POLY1(x,y,z) and POLY2(x,y,z) and store the result in
POLYSUM(x,y,z)
Support the program with appropriate functions for each of the above operations
10 Develop a menu driven Program in C for the following operations on Binary Search Tree
(BST) of Integers .
a. Create a BST of N Integers: 6, 9, 5, 2, 8, 15, 24, 14, 7, 8, 5, 2
b. Traverse the BST in Inorder, Preorder and Post Order
c. Search the BST for a given element (KEY) and report the appropriate message
d. Exit
11 Develop a Program in C for the following operations on Graph(G) of Cities
a. Create a Graph of N cities using Adjacency Matrix.
b. Print all the nodes reachable from a given starting node in a digraph using DFS/BFS
method
12 Given a File of N employee records with a set K of Keys (4-digit) which uniquely determine
the records in file F. Assume that file F is maintained in memory by a Hash Table (HT) of m
memory locations with L as the set of memory addresses (2-digit) of locations in HT. Let
the keys in K and addresses in L are Integers. Develop a Program in C that uses Hash
function H:K →L as H(K)=K mod m (remainder method), and implement hashing technique
to map a given key K to the address space L. Resolve the collision (if any) using linear
probing.

Laboratory Outcomes(CO): The student should be able to:

BCSL305.1 Analyze various linear and non-linear data structures
BCSL305.2 Demonstrate the working nature of different types of data structures and
their applications
BCSL305.2 Use appropriate searching and sorting algorithms for the give scenario.
BCSL305.2 Apply the appropriate data structure for solving real world problems
:
Data Structure Lab (BCSL305)

1. Develop a Program in C for the following:

a) Declare a calendar as an array of 7 elements (A dynamically Created array) to representv7 days
of a week. Each Element of the array is a structure having three fields. The first field is the name
of the Day (A dynamically allocated String), The second field is the date of the Day (A integer),
the third field is the description of the activity for a particular day (A dynamically allocated String).
b) Write functions create(), read() and display(); to create the calendar, to read the data from the
keyboard and to print weeks activity details report on screen.
#include <stdio.h>
#include <stdlib.h>

// Structure definition for a day

struct Day {
char *dayName;
int date;
char *activity;
};

// Function prototypes
void create(struct Day *calendar, int size);
void read(struct Day *calendar, int size);
void display(struct Day *calendar, int size);

int main() {
int size = 7; // Number of days in a week
struct Day *calendar = (struct Day *)malloc(size * sizeof(struct Day));

if (calendar == NULL) {
printf("Memory allocation failed.\n");
return 1;
}

create(calendar, size);
read(calendar, size);
display(calendar, size);

Department of AI&ML, YIT Moodbidri 1

Data Structure Lab (BCSL305)

// Free dynamically allocated memory

for (int i = 0; i < size; ++i) {
free(calendar[i].dayName);
free(calendar[i].activity);
}
free(calendar);

return 0;
}

// Function to create the calendar

void create(struct Day *calendar, int size) {
for (int i = 0; i < size; ++i) {
calendar[i].dayName = (char *)malloc(20 * sizeof(char)); // Assuming maximum length of
day name is 20
calendar[i].activity = (char *)malloc(50 * sizeof(char)); // Assuming maximum length of
activity description is 50
}
}

// Function to read data from the keyboard

void read(struct Day *calendar, int size) {
for (int i = 0; i < size; ++i) {
printf("Enter details for Day %d:\n", i + 1);
printf("Day Name: ");
scanf("%s", calendar[i].dayName);

printf("Date: ");
scanf("%d", &calendar[i].date);

printf("Activity: ");
scanf(" %[^\n]s", calendar[i].activity);
}
}
// Function to display the calendar
void display(struct Day *calendar, int size) {
printf("\nWeek's Activity Details:\n");
for (int i = 0; i < size; ++i) {
printf("Day %d - %s, Date %d: %s\n", i + 1, calendar[i].dayName, calendar[i].date,
calendar[i].activity);
}
}

Department of AI&ML, YIT Moodbidri 2

Data Structure Lab (BCSL305)

OUTPUT:

Enter details for Day 1:

Day Name: Monday
Date: 11
Activity: Sports
Enter details for Day 2:
Day Name: Tuesday
Date: 12
Activity: Sports
Enter details for Day 3:
Day Name: Wednesday
Date: 13
Activity: Annual Day
Enter details for Day 4:
Day Name: Thursday
Date: 14
Activity: Food Fest
Enter details for Day 5:
Day Name: Friday
Date: 15
Activity: Parents Meet
Enter details for Day 6:
Day Name: Saturday
Date: 16
Activity: Workshop
Enter details for Day 7:
Day Name: Sunday
Date: 17
Activity: IV

Week's Activity Details:

Day 1 - Monday, Date 11: Sports
Day 2 - Tuesday, Date 12: Sports
Day 3 - Wednesday, Date 13: Annual Day
Day 4 - Thursday, Date 14: Food Fest
Day 5 - Friday, Date 15: Parents Meet
Day 6 - Saturday, Date 16: Workshop
Day 7 - Sunday, Date 17: IV

Department of AI&ML, YIT Moodbidri 3

Data Structure Lab (BCSL305)

2. Develop a Program in C for the following operations on Strings.

a. Read a main String (STR), a Pattern String (PAT) and a Replace String (REP)
b. Perform Pattern Matching Operation: Find and Replace all occurrences of PAT in STR with
REP if PAT exists in STR. Report suitable messages in case PAT does not exist in STR Support
the program with functions for each of the above operations. Don't use Built-in functions.

#include<stdio.h>
#include<stdlib.h>
char STR[100],PAT[100],REP[100];
void ReadStrings(char STR[100], char PAT[100], char REP[100])
{
printf("Enter the main string STR : ");
gets(STR);
printf("Enter the pattern string PAT : ");
gets(PAT);
printf("Enter the replace string REP : ");
gets(REP);
}
void PatternMatching(char STR[100], char PAT[100], char REP[100])
{
int i,j,k,m,c,flag,count;
i=m=c=j=count=flag=0;
char RESULT[100];
while(STR[c] != '\0')
{
if(STR[m] == PAT[i])
{
i++;
m++;

if(PAT[i] =='\0')
{
for(k=0;REP[k] !='\0';k++,j++)
RESULT[j]=REP[k];
i=0;
c=m;
count++;
flag =1;
}
}

Department of AI&ML, YIT Moodbidri 4

Data Structure Lab (BCSL305)

else
{

RESULT[j]=STR[c];
j++;
c++;
m=c;
i=0;
}
}
if(flag == 0)
printf("Pattern does not found\n");
else
{
RESULT[j]='\0';
printf("Pattern found %d times\n",count);
printf("The resultant string is\n%s\n",RESULT);
}
}
int main()
{
ReadStrings(STR,PAT,REP);
PatternMatching(STR, PAT, REP);
}

OUTPUT 1:

Enter the main string STR : YIT Moodbidri is the best college in Moodbidri
Enter the pattern string PAT : Moodbidri
Enter the replace string REP : Mangalore
Pattern found 2 times
The resultant string is
YIT Mangalore is the best college in Mangalore

OUTPUT 2:
Enter the main string STR : YIT Moodbidri
Enter the pattern string PAT : Yenepoya
Enter the replace string REP : YIT
Pattern does not found

Department of AI&ML, YIT Moodbidri 5

Data Structure Lab (BCSL305)

3. Develop a menu driven Program in C for the following operations on STACK of Integers
(Array Implementation of Stack with maximum size MAX)
a. Push an Element on to Stack
b. Pop an Element from Stack
c. Demonstrate how Stack can be used to check Palindrome
d. Demonstrate Overflow and Underflow situations on Stack
e. Display the status of Stack
f. Exit
Support the program with appropriate functions for each of the above operations

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 10

int stack[MAX];
int top = -1;
char a[10];

int isFull()
{
return (top == MAX - 1);
}

int isEmpty()
{
return (top == -1);
}

void push(int element)

{
if (isFull())
{
printf("Stack Overflow. Cannot push element.\n");
}
else
{
stack[++top] = element;
printf("Element %d pushed successfully.\n", element);
}
}

int pop()
{
if (isEmpty())

Department of AI&ML, YIT Moodbidri 6

Data Structure Lab (BCSL305)

{
printf("Stack Underflow. Cannot pop element.\n");
return -1;
}
else
{
int element = stack[top--];
return element;
}
}

int isPalindrome()
{
int i;
for(i=0;i<=top;i++)
{
if (a[i] != pop())
return 0;

}
return 1;
}

void displayStack() {
if (isEmpty()) {
printf("Stack is empty.\n");
} else {
printf("Stack elements: ");
for (int i = 0; i <= top; i++)
{
printf("%d ", stack[i]);
}
printf("\n");
}
}

int main()
{
int choice, element,i;

while(1)
{
printf("\n------ Menu ------");

Department of AI&ML, YIT Moodbidri 7

Data Structure Lab (BCSL305)

printf("Enter 1. Push, 2 for pop, 3 for Palindrome, 4 Display stack, 5 Exit\n ");
scanf("%d", &choice);

switch (choice)
{
case 1:
printf("Enter the element to push: ");
scanf("%d", &element);
push(element);
break;
case 2:
element = pop();
if (element != -1)
printf("Popped element: %d", element);
break;
case 3:
top=-1;
printf("Enter the string:");
scanf("%s",a);
for (i=0;i<strlen(a);i++)
push(a[i]);
if (isPalindrome())
printf("The string is a palindrome.\n");
else
printf("The string not palindrome.\n");
break;
case 4:

displayStack();
break;
case 5:
exit(0);
default:
printf("Invalid choice. Please enter a valid choice.\n");
}
}

Department of AI&ML, YIT Moodbidri 8

Data Structure Lab (BCSL305)

OUTPUT:
------ Menu ------Enter 1. Push, 2 for pop, 3 for Palindrome, 4 Display stack, 5 Exit
3
Enter the string:MALAYALAM
Element 77 pushed successfully.
Element 65 pushed successfully.
Element 76 pushed successfully.
Element 65 pushed successfully.
Element 89 pushed successfully.
Element 65 pushed successfully.
Element 76 pushed successfully.
Element 65 pushed successfully.
Element 77 pushed successfully.
The string is a palindrome.

------ Menu ------Enter 1. Push, 2 for pop, 3 for Palindrome, 4 Display stack, 5 Exit
4
Stack elements: 77 65 76 65

------ Menu ------Enter 1. Push, 2 for pop, 3 for Palindrome, 4 Display stack, 5 Exit
1
Enter the element to push: 10
Element 10 pushed successfully.

------ Menu ------Enter 1. Push, 2 for pop, 3 for Palindrome, 4 Display stack, 5 Exit
2
Popped element: 10
------ Menu ------Enter 1. Push, 2 for pop, 3 for Palindrome, 4 Display stack, 5 Exit
4
Stack elements: 77 65 76 65

------ Menu ------Enter 1. Push, 2 for pop, 3 for Palindrome, 4 Display stack, 5 Exit
2
Popped element: 65
------ Menu ------Enter 1. Push, 2 for pop, 3 for Palindrome, 4 Display stack, 5 Exit
2
Popped element: 76
------ Menu ------Enter 1. Push, 2 for pop, 3 for Palindrome, 4 Display stack, 5 Exit
22
Invalid choice. Please enter a valid choice.

------ Menu ------Enter 1. Push, 2 for pop, 3 for Palindrome, 4 Display stack, 5 Exit
2
Popped element: 65
------ Menu ------Enter 1. Push, 2 for pop, 3 for Palindrome, 4 Display stack, 5 Exit
2

Department of AI&ML, YIT Moodbidri 9

Data Structure Lab (BCSL305)

Popped element: 77
------ Menu ------Enter 1. Push, 2 for pop, 3 for Palindrome, 4 Display stack, 5 Exit
2
Stack Underflow. Cannot pop element.

------ Menu ------Enter 1. Push, 2 for pop, 3 for Palindrome, 4 Display stack, 5 Exit
5

Department of AI&ML, YIT Moodbidri 10

Data Structure Lab (BCSL305)

4. Develop a Program in C for converting an Infix Expression to Postfix Expression. Program

should support for both parenthesized and free parenthesized expressions with the operators: +, -,
*, /, % (Remainder), ^ (Power) and alphanumeric operands.

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

int stack[20];
int top = -1;
void push(char);
char pop();
int incmprc(char);
int instprc(char);
void IntoPost(char[], char[]);

int main()
{
char infix[20], postfix[20];
printf("Enter the valid infix expression : ");
scanf("%s",infix);
push('#');
IntoPost(infix,postfix);
printf("The corresponding postfix expression is :
\n%s\n",postfix);
}

void push(char ch)

{
stack[++top]=ch;
}

char pop()
{
return stack[top--];
}

int incmprc(char ch)

{
switch(ch)
{
case '+' :
case '-' : return 1;
case '*' :
case '/' :
case '%' : return 2;
case '^' : return 3;
}
}

Department of AI&ML, YIT Moodbidri 11

Data Structure Lab (BCSL305)

int instprc(char ch)

{
switch(ch)
{
case '#' :
case '(' : return 0;
case '+' :
case '-' : return 1;
case '*' :
case '/' :
case '%' : return 2;
case '^' : return 3;
}
}
void IntoPost(char infix[20], char postfix[20])
{
int i=0,j=0;
char ch;
ch = infix[i++];
while(ch !='\0')
{
switch(ch)
{
case '(': push(ch);
break;
case ')': while(stack[top]!='(')
postfix[j++] = pop();
pop();
break;
case '^':
case '+':
case '-':
case '*':
case '/':
case '%': while(incmprc(ch) <= instprc(stack[top]))
postfix[j++] = pop();
push(ch);
break;
default : postfix[j++] = ch;
}
ch = infix[i++];
}
while(stack[top] != '#')
postfix[j++] = pop();
postfix[j]= '\0';
}

OUTPUT:
Enter the valid infix expression : (3+5)*(3-5)
The corresponding postfix expression is :
35+35-*

Department of AI&ML, YIT Moodbidri 12

Data Structure Lab (BCSL305)

5. Develop a Program in C for the following Stack Applications

a. Evaluation of Suffix expression with single digit operands and operators: +, -, *, /, %,^
b. Solving Tower of Hanoi problem with n disks

a. Evaluation of Suffix expression with single digit operands and operators: +, -, *, /, %,^

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int stack[50];
int top = -1;
void push(int);
int pop();

void push(int num)

{
stack[++top] = num;
}

int pop()
{

return stack[top--];

int main()
{
char suffix[50],ch;
int p1,p2,p3,i;
printf("Enter the valid suffix expression : ");
gets(suffix);
for(i=0;suffix[i]!='\0';i++)
{
ch = suffix[i];
//puts(ch);

if(isdigit(ch))
push(ch-'0');
else
{
p2 = pop();
p1 = pop();
switch(ch)
{
case '+': push(p1+p2);
//printf("%d",pop());
break;
case '-': push(p1-p2);
break;

Department of AI&ML, YIT Moodbidri 13

Data Structure Lab (BCSL305)

case '*': push(p1*p2);

break;
case '/': if(p2 == 0)
{
printf("Divide by Zero error\n");
exit(0);
}
push(p1/p2);
break;
case '%': if(p2 == 0)
{
printf("Divide by Zero error\n");
exit(0);
}
push(p1%p2);
break;
case '^': push(pow(p1,p2));
break;
default : printf("Invalid Expression\n");
}
}
}
printf("The value of given suffix expression is : %d\n",pop());
}

OUTPUT 1:

Enter the valid suffix expression : 79+

The value of given suffix expression is : 16

OUTPUT 2:

Enter the valid suffix expression : 93/1-24^+91*2%-

The value of given suffix expression is : 17

Department of AI&ML, YIT Moodbidri 14

Data Structure Lab (BCSL305)

b. b. Solving Tower of Hanoi problem with n disks

#include <stdio.h>

void towerOfHanoi(int n, char source, char auxiliary, char destination)

{
if (n == 1) {
printf("Move disk 1 from %c to %c\n", source, destination);
return;
}

// Move n-1 disks from source to auxiliary using destination

towerOfHanoi(n - 1, source, destination, auxiliary);

// Move the nth disk from source to destination

printf("Move disk %d from %c to %c\n", n, source, destination);

// Move the n-1 disks from auxiliary to destination using source

towerOfHanoi(n - 1, auxiliary, source, destination);
}

int main() {
int n;

// Input the number of disks

printf("Enter the number of disks: ");
scanf("%d", &n);

// Solve Tower of Hanoi problem

towerOfHanoi(n, 'A', 'B', 'C');

return 0;
}

OUTPUT:
Enter the number of disks: 3
Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

Department of AI&ML, YIT Moodbidri 15

Data Structure Lab (BCSL305)

6. Develop a menu driven Program in C for the following operations on Circular QUEUE of
Characters (Array Implementation of Queue with maximum size MAX)
a. Insert an Element on to Circular QUEUE
b. Delete an Element from Circular QUEUE
c. Demonstrate Overflow and Underflow situations on Circular QUEUE
d. Display the status of Circular QUEUE
e. Exit
Support the program with appropriate functions for each of the above operations

#include<stdio.h>
#include<stdlib.h>
#define MAX 5

int insert(char[], int, int);

int delete(char[], int, int);
void display(char[], int, int);

int main()
{
int choice,rear = 0,front = 0;
char cirqueue[MAX], ele;
while(1)
{
printf("\n\n**********************MENU*****************");
printf("\n1. Insert an Element on to Circular Queue\n2. Delete an
Element from Circular Queue\n3. Display the status of Circular Queue\n4. Exit\n");
printf("Enter your choice : ");
scanf("%d", &choice);
switch(choice)
{
case 1: rear = insert(cirqueue,rear,front);
break;
case 2: front = delete(cirqueue,rear,front);
break;
case 3: display(cirqueue,rear,front);
break;
case 4: exit(0);
}
}
}

Department of AI&ML, YIT Moodbidri 16

Data Structure Lab (BCSL305)

int insert(char cirqueue[MAX], int rear, int front)

{
int ele;
if(front == (rear + 1) % MAX)
{
printf("Circular Queue Overflow\n");
}
else
{
rear = (rear + 1) % MAX;
printf("Enter the element to be inserted: ");
getc(stdin);
scanf("%c",&ele);
cirqueue[rear] = ele;
}
return rear;
}
int delete(char cirqueue[MAX], int rear, int front)
{
if(front == rear)
{
printf("Circular Queue Underflow\n");
}
else
{
front = (front + 1) % MAX;
printf("The element deleted is : %c\n", cirqueue[front]);
}
return front;
}
void display(char cirqueue[MAX], int rear, int front)
{
int i;
if(front == rear)
printf("Circular Queue Underflow\n");
else
{
printf("The elements of circular queue are\n\n");

Department of AI&ML, YIT Moodbidri 17

Data Structure Lab (BCSL305)

i=front;
do
{
i=((i+1)%MAX);
printf("%c ",cirqueue[i]);
}
while(i!=rear);
}
}

OUTPUT:
**********************MENU*****************
1. Insert an Element on to Circular Queue
2. Delete an Element from Circular Queue
3. Display the status of Circular Queue
4. Exit
Enter your choice : 1
Enter the element to be inserted: c
**********************MENU*****************
1. Insert an Element on to Circular Queue
2. Delete an Element from Circular Queue
3. Display the status of Circular Queue
4. Exit
Enter your choice : 1
Enter the element to be inserted: h
**********************MENU*****************
1. Insert an Element on to Circular Queue
2. Delete an Element from Circular Queue
3. Display the status of Circular Queue
4. Exit
Enter your choice : 1
Enter the element to be inserted: o
**********************MENU*****************
1. Insert an Element on to Circular Queue
2. Delete an Element from Circular Queue
3. Display the status of Circular Queue
4. Exit
Enter your choice : 3

Department of AI&ML, YIT Moodbidri 18

Data Structure Lab (BCSL305)

The elements of circular queue are

cho
**********************MENU*****************
1. Insert an Element on to Circular Queue
2. Delete an Element from Circular Queue
3. Display the status of Circular Queue
4. Exit
Enter your choice : 2
The element deleted is : c
**********************MENU*****************
1. Insert an Element on to Circular Queue
2. Delete an Element from Circular Queue
3. Display the status of Circular Queue
4. Exit
Enter your choice : 3
The elements of circular queue are
ho
**********************MENU*****************
1. Insert an Element on to Circular Queue
2. Delete an Element from Circular Queue
3. Display the status of Circular Queue
4. Exit
Enter your choice : 1
Enter the element to be inserted: l
**********************MENU*****************
1. Insert an Element on to Circular Queue
2. Delete an Element from Circular Queue
3. Display the status of Circular Queue
4. Exit
Enter your choice : 1
Enter the element to be inserted: i
**********************MENU*****************
1. Insert an Element on to Circular Queue
2. Delete an Element from Circular Queue
3. Display the status of Circular Queue
4. Exit
Enter your choice : 1
Circular Queue Overflow

Department of AI&ML, YIT Moodbidri 19

Data Structure Lab (BCSL305)

**********************MENU*****************
1. Insert an Element on to Circular Queue
2. Delete an Element from Circular Queue
3. Display the status of Circular Queue
4. Exit
Enter your choice : 1
Circular Queue Overflow
**********************MENU*****************
1. Insert an Element on to Circular Queue
2. Delete an Element from Circular Queue
3. Display the status of Circular Queue
4. Exit
Enter your choice : 3
The elements of circular queue are
holi
**********************MENU*****************
1. Insert an Element on to Circular Queue
2. Delete an Element from Circular Queue
3. Display the status of Circular Queue
4. Exit
Enter your choice : 2
The element deleted is : h
**********************MENU*****************
1. Insert an Element on to Circular Queue
2. Delete an Element from Circular Queue
3. Display the status of Circular Queue
4. Exit
Enter your choice : 2
The element deleted is : o
**********************MENU*****************
1. Insert an Element on to Circular Queue
2. Delete an Element from Circular Queue
3. Display the status of Circular Queue
4. Exit
Enter your choice : 2
The element deleted is : l
**********************MENU*****************
1. Insert an Element on to Circular Queue

Department of AI&ML, YIT Moodbidri 20

Data Structure Lab (BCSL305)

2. Delete an Element from Circular Queue

3. Display the status of Circular Queue
4. Exit
Enter your choice : 2
The element deleted is : i
**********************MENU*****************
1. Insert an Element on to Circular Queue
2. Delete an Element from Circular Queue
3. Display the status of Circular Queue
4. Exit
Enter your choice : 3
Circular Queue Underflow
**********************MENU*****************
1. Insert an Element on to Circular Queue
2. Delete an Element from Circular Queue
3. Display the status of Circular Queue
4. Exit
Enter your choice : 4

Department of AI&ML, YIT Moodbidri 21

Data Structure Lab (BCSL305)

7. Develop a menu driven Program in C for the following operations on Singly Linked List
(SLL) of Student Data with the fields: USN, Name, Programme, Sem, PhNo
a. Create a SLL of N Students Data by using front insertion.
b. Display the status of SLL and count the number of nodes in it
c. Perform Insertion / Deletion at End of SLL
d. Perform Insertion / Deletion at Front of SLL(Demonstration of stack)
e. Exit

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

int count = 0;

struct node
{
int sem, phno;
char usn[50], name[50],branch[50];
struct node *link;
};
struct node *first = NULL, *last = NULL, *temp = NULL, *temp1 = NULL;

void CreateNode()
{
int sem,phno;
char usn[50],name[50],branch[50];
temp=(struct node*)malloc(sizeof(struct node));
printf("\nEnter usn,name, branch, sem, phno of student \n");
scanf("%s %s %s %d %d", usn, name,branch, &sem,&phno);
strcpy(temp->usn,usn);
strcpy(temp->name,name);
strcpy(temp->branch,branch);
temp->sem = sem;
temp->phno = phno;
temp->link=NULL;
count++;
}

void InsertAtFront()
{
if (first == NULL)
{
CreateNode();
first = temp;
last = first;
}
else
{
CreateNode();
temp->link = first;
first = temp;

Department of AI&ML, YIT Moodbidri 22

Data Structure Lab (BCSL305)

}
}

void InsertAtEnd()
{
if(first==NULL)
{
CreateNode();
first = temp;
last = first;
}
else
{
CreateNode();
last->link = temp;
last = temp;
}
}

void Display()
{
temp1=first;
if(temp1 == NULL)
{
printf("\nList is empty \n");

}
else
{
printf("\nThe elements of SLL are :\n");
while (temp1!= NULL)
{
printf("%s %s %s %d %d\n", temp1->usn, temp1-
>name,temp1->branch,temp1->sem,temp1->phno );
temp1 = temp1->link;
}
}
printf("Number of students = %d\n", count);
}

void DeleteAtEnd()
{
struct node *temp;
temp=first;
if(first == NULL)
printf("\nList is empty\n");
else if(temp->link==NULL)
{
printf("The student record deleted is\n%s %s %s %d %d\n",
temp->usn, temp->name, temp->branch, temp->sem, temp->phno );
free(temp);
first=NULL;

Department of AI&ML, YIT Moodbidri 23

Data Structure Lab (BCSL305)

count--;
}
else
{
while(temp->link!=last)
temp=temp->link;
printf("The student record deleted is\n%s %s %s %d %d\n",
last->usn, last->name,last->branch,last->sem, last->phno );
free(last);
temp->link=NULL;
last=temp;
count--;
}
}

void DeleteAtFront()
{
struct node *temp;
temp=first;
if(first == NULL)
printf("\nList is empty\n");
else if(temp->link==NULL)
{
printf("The student record deleted is\n%s %s %s %d %d",
temp->usn, temp->name,temp->branch,temp->sem, temp->phno );
free(temp);
first=NULL;
count--;

}
else
{
first=temp->link;
printf("The student record deleted is\n%s %s %s %d %d",
temp->usn, temp->name,temp->branch,temp->sem, temp->phno );
free(temp);
count--;
}
}

int main()
{
while(1)
{
int choice, n, i, choice2, flag1, flag2;
printf("\n\n**********************MENU*****************");
printf("\n1. Create a SLL of N students Data by using front
insertion\n2. Display the status of SLL and count the number of nodes
in it\n3. Perform Insertion/Deletion at End of SLL\n4. Perform
Insertion/Deletion at Front of SLL (Demonstaration of SLL as
STACK)\n5. Exit\n");

Department of AI&ML, YIT Moodbidri 24

Data Structure Lab (BCSL305)

printf("\nEnter your choice : ");

scanf("%d",&choice);
switch(choice)
{
case 1 : printf("Enter the number of students : ");
scanf("%d",&n);
for(i=0;i<n;i++)
InsertAtFront();
break;
case 2 : Display();
break;
case 3 : flag1 = 0;
while(flag1 == 0)
{
printf("\n\n1. Insertion\n2. Deletion\n3.
Exit");
printf("\n\nEnter your option\n");
scanf("%d",&choice2);
switch(choice2)
{
case 1 : InsertAtEnd();
Display();
break;
case 2 : DeleteAtEnd();
Display();
break;
case 3 : flag1 = 1;
break;
}
}
break;
case 4 : flag2 = 0;
printf("\n\nDemonstration of STACK\n");
while(flag2 == 0)
{
printf("\n\n1. Insertion\n2. Deletion\n3.
Exit\n");
printf("\n\nEnter your option\n");
scanf("%d",&choice2);
switch(choice2)
{
case 1 : InsertAtFront();
Display();
break;
case 2 : DeleteAtFront();
Display();
break;
case 3 : flag2 = 1;
break;
}
}
break;

Department of AI&ML, YIT Moodbidri 25

Data Structure Lab (BCSL305)

case 5 : exit(0);
break;
}
}
}

OUTPUT

**********************MENU*****************
1. Create a SLL of N students Data by using front insertion
2. Display the status of SLL and count the number of nodes in it
3. Perform Insertion/Deletion at End of SLL
4. Perform Insertion/Deletion at Front of SLL (Demonstaration of SLL as STACK)
5. Exit
Enter your choice : 1
Enter the number of students : 2
Enter usn,name, branch, sem, phno of student
4PA15CS001 JOHN CS 1 1111
Enter usn,name, branch, sem, phno of student
4PA15CS002 JACK CS 3 3333

**********************MENU*****************
1. Create a SLL of N students Data by using front insertion
2. Display the status of SLL and count the number of nodes in it
3. Perform Insertion/Deletion at End of SLL
4. Perform Insertion/Deletion at Front of SLL (Demonstaration of SLL as STACK)
5. Exit
Enter your choice : 2
The elements of SLL are :
4PA15CS002 JACK CS 3 3333
4PA15CS001 JOHN CS 1 1111
Number of students = 2

**********************MENU*****************
1. Create a SLL of N students Data by using front insertion
2. Display the status of SLL and count the number of nodes in it
3. Perform Insertion/Deletion at End of SLL
4. Perform Insertion/Deletion at Front of SLL (Demonstaration of SLL as STACK)
5. Exit
Enter your choice : 3
1. Insertion
2. Deletion
3. Exit
Enter your option
1

Department of AI&ML, YIT Moodbidri 26

Data Structure Lab (BCSL305)

Enter usn,name, branch, sem, phno of student

4PA15CS003 RAJ CS 5 5555

The elements of SLL are :

4PA15CS002 JACK CS 3 3333
4PA15CS001 JOHN CS 1 1111
4PA15CS003 RAJ CS 5 5555
Number of students = 3

1. Insertion
2. Deletion
3. Exit
Enter your option
2
The student record deleted is
4PA15CS003 RAJ CS 5 5555

The elements of SLL are :

4PA15CS002 JACK CS 3 3333
4PA15CS001 JOHN CS 1 1111
Number of students = 2

1. Insertion
2. Deletion
3. Exit
Enter your option
3

**********************MENU*****************
1. Create a SLL of N students Data by using front insertion
2. Display the status of SLL and count the number of nodes in it
3. Perform Insertion/Deletion at End of SLL
4. Perform Insertion/Deletion at Front of SLL (Demonstaration of SLL as STACK)
5. Exit
Enter your choice : 4

Demonstration of STACK

1. Insertion
2. Deletion
3. Exit
Enter your option
1
Enter usn,name, branch, sem, phno of student
4PA15CS004 RAHUL CS 7 7777

Department of AI&ML, YIT Moodbidri 27

Data Structure Lab (BCSL305)

The elements of SLL are :

4PA15CS004 RAHUL CS 7 7777
4PA15CS002 JACK CS 3 3333
4PA15CS001 JOHN CS 1 1111
Number of students = 3

1. Insertion
2. Deletion
3. Exit

Enter your option

2
The student record deleted is
4PA15CS004 RAHUL CS 7 7777
The elements of SLL are :
4PA15CS002 JACK CS 3 3333
4PA15CS001 JOHN CS 1 1111
Number of students = 2

1. Insertion
2. Deletion
3. Exit

Enter your option

2
The student record deleted is
4PA15CS002 JACK CS 3 3333
The elements of SLL are :
4PA15CS001 JOHN CS 1 1111
Number of students = 1
1. Insertion
2. Deletion
3. Exit

Enter your option

2
The student record deleted is
4PA15CS001 JOHN CS 1 1111
List is empty
Number of students = 0

1. Insertion
2. Deletion
3. Exit

Department of AI&ML, YIT Moodbidri 28

Data Structure Lab (BCSL305)

Enter your option

3
**********************MENU*****************
1. Create a SLL of N students Data by using front insertion
2. Display the status of SLL and count the number of nodes in it
3. Perform Insertion/Deletion at End of SLL
4. Perform Insertion/Deletion at Front of SLL (Demonstaration of SLL as STACK)
5. Exit
Enter your choice : 5

Department of AI&ML, YIT Moodbidri 29

Data Structure Lab (BCSL305)

8. Develop a menu driven Program in C for the following operations on Doubly Linked List
(DLL) of Employee Data with the fields: SSN, Name, Dept, Designation, Sal, PhNo
a. Create a DLL of N Employees Data by using end insertion.
b. Display the status of DLL and count the number of nodes in it
c. Perform Insertion and Deletion at End of DLL
d. Perform Insertion and Deletion at Front of DLL
e. Demonstrate how this DLL can be used as Double Ended Queue.
f. Exit

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

int count=0;

struct node
{
int ssn, phno;
float sal;
char name[50],dept[50],desig[50];
struct node *llink;
struct node *rlink;
};
struct node *first = NULL,*temp = NULL,*temp1=NULL,*temp2=NULL;

void CreateNode()
{
int ssn,phno;
float sal;
char name[50],dept[50],desig[50];
temp =(struct node *)malloc(sizeof(struct node));
temp->llink = NULL;
temp->rlink = NULL;
printf("\nEnter ssn,name,department, designation, salary and phno
of employee\n");
scanf("%d %s %s %s %f %d", &ssn, name,dept,desig,&sal, &phno);
temp->ssn = ssn;
strcpy(temp->name,name);
strcpy(temp->dept,dept);
strcpy(temp->desig,desig);
temp->sal = sal;
temp->phno = phno;
count++;
}

void InsertAtFront()
{
if (first == NULL)
{
CreateNode();
first = temp;

Department of AI&ML, YIT Moodbidri 30

Data Structure Lab (BCSL305)

temp1 = first;
}
else
{
CreateNode();
temp->rlink = first;
first->llink = temp;
first = temp;
}
}

void InsertAtEnd()
{
if(first==NULL)
{
CreateNode();
first = temp;
temp1 = first;
}
else
{
CreateNode();
temp1->rlink = temp;
temp->llink = temp1;
temp1 = temp;
}
}

void Display()
{
temp2 =first;
if(temp2 == NULL)
{
printf("\nList is empty \n");
}
else
{
printf("\n\nThe elements of DLL are :\n");
while (temp2!= NULL)
{
printf("%d %s %s %s %f %d\n", temp2-
>ssn, temp2->name,temp2->dept,temp2->desig,temp2->sal, temp2->phno );
temp2 = temp2->rlink;
}
}
printf("Number of employees = %d ", count);
}

void DeleteAtEnd()
{
struct node *temp;
temp=first;

Department of AI&ML, YIT Moodbidri 31

Data Structure Lab (BCSL305)

if(first == NULL)
printf("\nList is empty\n");
else if(temp->rlink==NULL)
{
printf("The employee record deleted is\n%d %s %s %s %f
%d\n", temp->ssn, temp->name,temp->dept,
temp->desig,temp->sal, temp->phno );
free(temp);
first=NULL;
count--;
}
else
{
temp2=temp1->llink;
temp2->rlink=NULL;
printf("The employee record deleted is\n%d %s %s %s %f
%d\n", temp1->ssn, temp1->name,temp1->dept,
temp1->desig,temp1->sal, temp1->phno );
free(temp1);
temp1 = temp2;
count--;

}
}

void DeleteAtFront()
{
struct node *temp;
temp=first;
if(first == NULL)
printf("\nList is empty\n");
else if(temp->rlink==NULL)
{
printf("The employee record deleted is\n%d %s %s %s %f %d",
temp->ssn, temp->name,temp->dept, temp->desig,temp->sal, temp->phno );
free(temp);
first=NULL;
count--;
}
else
{
first=first->rlink;
printf("The employee record deleted is\n%d %s %s %s %f %d",
temp->ssn, temp->name,temp->dept, temp->desig,temp->sal, temp->phno );
free(temp); \
count--;
}
}

int main()
{

Department of AI&ML, YIT Moodbidri 32

Data Structure Lab (BCSL305)

int choice,choice2,n,i, flag, flag1, flag2;

first=NULL;
temp = temp1 = NULL;
while(1)
{
printf("\n\n**********************MENU*****************");
printf("\n1. Create a DLL of N employees Data by using end
insertion\n2. Display the status of DLL and count the number of nodes
in it\n3. Perform Insertion and Deletion at End of DLL\n4. Perform
Insertion and Deletion at Front of DLL\n5. Demonstaration of DLL as
DOUBLE ENDED QUEUE\n6. Exit");
printf("\nEnter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1 : printf("Enter the number of employees : ");
scanf("%d",&n);
for(i=0;i<n;i++)
InsertAtEnd();
break;
case 2 : Display();
break;
case 3 : flag1 = 0;
while(flag1 == 0)
{
printf("\n\n1. Insertion\n2. Deletion\n3.
Exit");
printf("\n\nEnter your option\n");
scanf("%d",&choice2);
switch(choice2)
{
case 1 : InsertAtEnd();
Display();
break;
case 2 : DeleteAtEnd();
Display();
break;
case 3 : flag1 = 1;
break;
}
}
break;
case 4 : flag2 = 0;
while(flag2 == 0)
{
printf("\n\n1. Insertion\n2. Deletion\n3.
Exit\n");
printf("\n\nEnter your option\n");
scanf("%d",&choice2);
switch(choice2)
{
case 1 : InsertAtFront();

Department of AI&ML, YIT Moodbidri 33

Data Structure Lab (BCSL305)

Display();
break;
case 2 : DeleteAtFront();
Display();
break;
case 3 : flag2 = 1;
break;
}
}
break;

case 5 : printf("Demonstration of DLL as DOUBLE ENDED

QUEUE\n");
flag = 0;
while(flag == 0)
{
printf("\n\n1. Insert at end\n2. Delete at
end\n3. Insert at front\n4. Delete at front\n5. Exit\n\n");
printf("\nEnter your option : ");
scanf("%d",&choice2);
switch(choice2)
{
case 1 : InsertAtEnd();
Display();
break;
case 2 : DeleteAtEnd();
Display();
break;
case 3 : InsertAtFront();
Display();
break;
case 4 : DeleteAtFront();
Display();
break;
case 5 : flag = 1;
break;
}
}
break;
case 6 : exit(0);
break;
}
}
}

OUTPUT:
**********************MENU*****************
1. Create a DLL of N employees Data by using end insertion
2. Display the status of DLL and count the number of nodes in it
3. Perform Insertion and Deletion at End of DLL
4. Perform Insertion and Deletion at Front of DLL
Department of AI&ML, YIT Moodbidri 34
Data Structure Lab (BCSL305)

5. Demonstaration of DLL as DOUBLE ENDED QUEUE

6. Exit
Enter your choice : 1
Enter the number of employees : 2

Enter ssn,name,department, designation, salary and phno of employee

100 JOHN ADMINISTRATION HR 50000 1111

Enter ssn,name,department, designation, salary and phno of employee

200 AHMED FINANCE HEAD 40000 2222

**********************MENU*****************
1. Create a DLL of N employees Data by using end insertion
2. Display the status of DLL and count the number of nodes in it
3. Perform Insertion and Deletion at End of DLL
4. Perform Insertion and Deletion at Front of DLL
5. Demonstaration of DLL as DOUBLE ENDED QUEUE
6. Exit
Enter your choice : 2

The elements of DLL are :

100 JOHN ADMINISTRATION HR 50000.000000 1111
200 AHMED FINANCE HEAD 40000.000000 2222
Number of employees = 2

**********************MENU*****************
1. Create a DLL of N employees Data by using end insertion
2. Display the status of DLL and count the number of nodes in it
3. Perform Insertion and Deletion at End of DLL
4. Perform Insertion and Deletion at Front of DLL
5. Demonstaration of DLL as DOUBLE ENDED QUEUE
6. Exit
Enter your choice : 3

1. Insertion
2. Deletion
3. Exit

Enter your option

1

Enter ssn,name,department, designation, salary and phno of employee

300 RAJ ADMINISTRATION DIRECTOR 80000 3333

Department of AI&ML, YIT Moodbidri 35

Data Structure Lab (BCSL305)

The elements of DLL are :

100 JOHN ADMINISTRATION HR 50000.000000 1111
200 AHMED FINANCE HEAD 40000.000000 2222
300 RAJ ADMINISTRATION DIRECTOR 80000.000000 3333
Number of employees = 3

1. Insertion
2. Deletion
3. Exit

Enter your option

2
The employee record deleted is
300 RAJ ADMINISTRATION DIRECTOR 80000.000000 3333

The elements of DLL are :

100 JOHN ADMINISTRATION HR 50000.000000 1111
200 AHMED FINANCE HEAD 40000.000000 2222
Number of employees = 2

1. Insertion
2. Deletion
3. Exit

Enter your option

3

**********************MENU*****************
1. Create a DLL of N employees Data by using end insertion
2. Display the status of DLL and count the number of nodes in it
3. Perform Insertion and Deletion at End of DLL
4. Perform Insertion and Deletion at Front of DLL
5. Demonstaration of DLL as DOUBLE ENDED QUEUE
6. Exit
Enter your choice : 4

1. Insertion
2. Deletion
3. Exit

Department of AI&ML, YIT Moodbidri 36

Data Structure Lab (BCSL305)

Enter your option

1

Enter ssn,name,department, designation, salary and phno of employee

400 SHAM FINANCE EXECUTIVE-DIRECTOR 35000 4444

The elements of DLL are :

400 SHAM FINANCE EXECUTIVE-DIRECTOR 35000.000000 4444
100 JOHN ADMINISTRATION HR 50000.000000 1111
200 AHMED FINANCE HEAD 40000.000000 2222
Number of employees = 3

1. Insertion
2. Deletion
3. Exit

Enter your option

2
The employee record deleted is
400 SHAM FINANCE EXECUTIVE-DIRECTOR 35000.000000 4444

The elements of DLL are :

100 JOHN ADMINISTRATION HR 50000.000000 1111
200 AHMED FINANCE HEAD 40000.000000 2222
Number of employees = 2

1. Insertion
2. Deletion
3. Exit

Enter your option

3

**********************MENU*****************
1. Create a DLL of N employees Data by using end insertion
2. Display the status of DLL and count the number of nodes in it
3. Perform Insertion and Deletion at End of DLL
4. Perform Insertion and Deletion at Front of DLL
5. Demonstaration of DLL as DOUBLE ENDED QUEUE
6. Exit
Enter your choice : 5
Demonstration of DLL as DOUBLE ENDED QUEUE

Department of AI&ML, YIT Moodbidri 37

Data Structure Lab (BCSL305)

1. Insert at end
2. Delete at end
3. Insert at front
4. Delete at front
5. Exit

Enter your option : 1

Enter ssn,name,department, designation, salary and phno of employee

300 RAJ ADMINISTRATION DIRECTOR 80000 3333

The elements of DLL are :

100 JOHN ADMINISTRATION HR 50000.000000 1111
200 AHMED FINANCE HEAD 40000.000000 2222
300 RAJ ADMINISTRATION DIRECTOR 80000.000000 3333
Number of employees = 3

1. Insert at end
2. Delete at end
3. Insert at front
4. Delete at front
5. Exit

Enter your option : 3

Enter ssn,name,department, designation, salary and phno of employee

400 SHAM FINANCE EXECUTIVE-DIRECTOR 35000 4444

The elements of DLL are :

400 SHAM FINANCE EXECUTIVE-DIRECTOR 35000.000000 4444
100 JOHN ADMINISTRATION HR 50000.000000 1111
200 AHMED FINANCE HEAD 40000.000000 2222
300 RAJ ADMINISTRATION DIRECTOR 80000.000000 3333
Number of employees = 4

1. Insert at end
2. Delete at end
3. Insert at front
4. Delete at front
5. Exit

Department of AI&ML, YIT Moodbidri 38

Data Structure Lab (BCSL305)

Enter your option : 2

The employee record deleted is
300 RAJ ADMINISTRATION DIRECTOR 80000.000000 3333

The elements of DLL are :

400 SHAM FINANCE EXECUTIVE-DIRECTOR 35000.000000 4444
100 JOHN ADMINISTRATION HR 50000.000000 1111
200 AHMED FINANCE HEAD 40000.000000 2222
Number of employees = 3

1. Insert at end
2. Delete at end
3. Insert at front
4. Delete at front
5. Exit

Enter your option : 4

The employee record deleted is
400 SHAM FINANCE EXECUTIVE-DIRECTOR 35000.000000 4444

The elements of DLL are :

100 JOHN ADMINISTRATION HR 50000.000000 1111
200 AHMED FINANCE HEAD 40000.000000 2222
Number of employees = 2

1. Insert at end
2. Delete at end
3. Insert at front
4. Delete at front
5. Exit

Enter your option : 2

The employee record deleted is
200 AHMED FINANCE HEAD 40000.000000 2222

The elements of DLL are :

100 JOHN ADMINISTRATION HR 50000.000000 1111
Number of employees = 1

1. Insert at end

Department of AI&ML, YIT Moodbidri 39

Data Structure Lab (BCSL305)

2. Delete at end
3. Insert at front
4. Delete at front
5. Exit

Enter your option : 2

The employee record deleted is
100 JOHN ADMINISTRATION HR 50000.000000 1111

List is empty
Number of employees = 0

1. Insert at end
2. Delete at end
3. Insert at front
4. Delete at front
5. Exit

Enter your option : 5

**********************MENU*****************
1. Create a DLL of N employees Data by using end insertion
2. Display the status of DLL and count the number of nodes in it
3. Perform Insertion and Deletion at End of DLL
4. Perform Insertion and Deletion at Front of DLL
5. Demonstaration of DLL as DOUBLE ENDED QUEUE
6. Exit
Enter your choice : 6

Department of AI&ML, YIT Moodbidri 40

Data Structure Lab (BCSL305)

9. Design, Develop and Implement a Program in C for the following operations on Singly
Circular Linked List (SCLL) with header nodes
a. Represent and Evaluate a Polynomial P(x,y,z) = 6x2y2z-4yz5+3x3yz+2xy5z-2xyz3
b. Find the sum of two polynomials POLY1(x,y,z) and POLY2(x,y,z) and store the
result in POLYSUM(x,y,z)
Support the program with appropriate functions for each of the above operations

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

struct node
{
int coef;
int xexp;
int yexp;
int zexp;
struct node *link;
};
typedef struct node *NODE;
NODE first = NULL, last = NULL, temp = NULL, poly1 = NULL, poly2 =
NULL;

void CreateTerm()
{
int coef, xexp, yexp, zexp;
temp=(struct node*)malloc(sizeof(struct node));
printf("Enter the coefficient, x power, y power and z power : ");
scanf("%d %d %d %d",&coef, &xexp, &yexp, &zexp);
temp->coef = coef;
temp->xexp = xexp;
temp->yexp = yexp;
temp->zexp = zexp;
temp->link=NULL;
}

void DisplayPoly(NODE poly)

{
NODE temp1;
temp1=poly->link;
printf("\nThe Polynomial is :\n");
while (temp1!= poly)
{
printf("%dx^(%d)y^(%d)z^(%d)", temp1->coef, temp1->xexp,
temp1->yexp, temp1->zexp);
if(temp1->link != poly && temp1->link->coef > 0)
printf(" + ");
//else if(temp1->link != poly && temp1->link->coef < 0)
//printf(" - ");

Department of AI&ML, YIT Moodbidri 41

Data Structure Lab (BCSL305)

temp1 = temp1->link;
}
}

void CreatePoly()
{
int n, i;
NODE header = NULL;
header = (struct node *)malloc(sizeof(struct node));
header->coef = header->xexp = header->yexp = header->zexp = -1;
header->link = header;
printf("\nEnter the number of terms in the polynomial : ");
scanf("%d",&n);
for(i = 1;i <= n; i++)
{
if(header->link == header)
{
CreateTerm();
header->link = temp;
temp->link = header;
first = header;
last = temp;
}
else
{
CreateTerm();
last->link = temp;
temp->link = header;
last = temp;
}
}
DisplayPoly(first);
}

void EvaluatePoly()
{
int x, y, z, sum = 0;
NODE temp2;
printf("\n\nEnter the value for x, y and z : ");
scanf("%d %d %d", &x, &y, &z);
temp2 = first->link;
while(temp2 != first)
{
sum = sum + temp2->coef * pow(x,temp2->xexp) * pow(y,
temp2->yexp) * pow(z,temp2->zexp);
temp2 = temp2->link;
}
printf("The value of polynomial is : %d\n", sum);
}

void attach(int coef, int xexp, int yexp, int zexp, NODE *rear)

Department of AI&ML, YIT Moodbidri 42

Data Structure Lab (BCSL305)

{
NODE temp3;
temp3=(struct node*)malloc(sizeof(struct node));
temp3->coef = coef;
temp3->xexp = xexp;
temp3->yexp = yexp;
temp3->zexp = zexp;
temp3->link = NULL;
(*rear)->link = temp3;
*rear = temp3;
}

void Add(NODE poly1,NODE poly2)

{
NODE poly3, poly4, temp2, ptr1, ptr2, header1 = NULL, header2 =
NULL;
int result,flag1=0,flag2=0;
header1 = (struct node *)malloc(sizeof(struct node));
header1->coef = header1->xexp = header1->yexp = header1->zexp = -
1;
header1->link = header1;
header2 = (struct node *)malloc(sizeof(struct node));
header2->coef = header2->xexp = header2->yexp = header2->zexp = -
1;
header2->link = header2;
poly3=header1;
poly4=header2;
ptr1=poly1->link;
while(ptr1 != poly1)
{
ptr2 = poly2->link;
while(ptr2 != poly2)
{
if(ptr1->xexp == ptr2->xexp && ptr1->yexp == ptr2-
>yexp && ptr1->zexp == ptr2->zexp)
{
result = 0;
result = ptr1->coef + ptr2->coef;
attach(result, ptr1->xexp, ptr1->yexp, ptr1-
>zexp, &header1);
header1->link = poly3;
flag1 = 1;
attach(ptr2->coef, ptr2->xexp, ptr2->yexp, ptr2-
>zexp, &header2);
header2->link = poly4;
break;
}
else
ptr2 = ptr2->link;
}
if(flag1 == 0)
{

Department of AI&ML, YIT Moodbidri 43

Data Structure Lab (BCSL305)

attach(ptr1->coef, ptr1->xexp, ptr1->yexp, ptr1->zexp,

&header1);
header1->link = poly3;

flag1 = 0;
ptr1 = ptr1->link;
}
ptr2 = poly2->link;
while(ptr2 != poly2)
{
temp2 = poly4->link;
while(temp2 != poly4)
{
if(ptr2->xexp == temp2->xexp && ptr2->yexp == temp2-
>yexp && ptr2->zexp == temp2->zexp)
{
flag2 = 1;
break;
}
else
temp2 = temp2->link;
}
if(flag2 == 0)
{
attach(ptr2->coef, ptr2->xexp, ptr2->yexp, ptr2->zexp,
&header1);
header1->link = poly3;
}
flag2 = 0;
ptr2 = ptr2->link;
}
printf("\n\nResultant Polynomial:");
DisplayPoly(poly3);
}

int main()
{
while(1)
{
int choice;
printf("\n\n**********************MENU*****************");
printf("\n1. Represent and Evaluate the Polynomial\n2. Add
two Polynomials\n3. Exit\n");
printf("Enter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1: first = last = NULL;
CreatePoly();
EvaluatePoly();

Department of AI&ML, YIT Moodbidri 44

Data Structure Lab (BCSL305)

break;
case 2: printf("\nPolynomial 1 :\n");
first = last = NULL;
CreatePoly();
poly1=first;
printf("\n\nPolynomial 2 :\n");
first = last = NULL;
CreatePoly();
poly2=first;
Add(poly1,poly2);
break;
case 3: exit(0);
break;
}
}
}

OUTPUT

**********************MENU*****************
1. Represent and Evaluate the Polynomial
2. Add two Polynomials
3. Exit
Enter your choice : 1

Enter the number of terms in the polynomial : 5

Enter the coefficient, x power, y power and z power : 6 2 2 1
Enter the coefficient, x power, y power and z power : -4 0 1 5
Enter the coefficient, x power, y power and z power : 3 3 1 1
Enter the coefficient, x power, y power and z power : 2 1 5 1
Enter the coefficient, x power, y power and z power : -2 1 1 3

The Polynomial is :
6x^(2)y^(2)z^(1)-4x^(0)y^(1)z^(5) + 3x^(3)y^(1)z^(1) + 2x^(1)y^(5)z^(1)-2x^(1)y^(1)z^(3)

Enter the value for x, y and z : 3 2 1

The value of polynomial is : 550

**********************MENU*****************
1. Represent and Evaluate the Polynomial
2. Add two Polynomials
3. Exit
Enter your choice : 2

Department of AI&ML, YIT Moodbidri 45

Data Structure Lab (BCSL305)

Polynomial 1 :

Enter the number of terms in the polynomial : 3

Enter the coefficient, x power, y power and z power : 2 2 2 2
Enter the coefficient, x power, y power and z power : 3 3 1 1
Enter the coefficient, x power, y power and z power : 4 1 2 3

The Polynomial is :
2x^(2)y^(2)z^(2) + 3x^(3)y^(1)z^(1) + 4x^(1)y^(2)z^(3)

Polynomial 2 :

Enter the number of terms in the polynomial : 4

Enter the coefficient, x power, y power and z power : 5 3 3 3
Enter the coefficient, x power, y power and z power : 2 1 2 3
Enter the coefficient, x power, y power and z power : 7 1 1 1
Enter the coefficient, x power, y power and z power : 6 2 2 2

The Polynomial is :
5x^(3)y^(3)z^(3) + 2x^(1)y^(2)z^(3) + 7x^(1)y^(1)z^(1) + 6x^(2)y^(2)z^(2)

Resultant Polynomial:
The Polynomial is :
8x^(2)y^(2)z^(2) + 3x^(3)y^(1)z^(1) + 6x^(1)y^(2)z^(3) + 5x^(3)y^(3)z^(3) + 7x^(1)y^(1)z^(1)

**********************MENU*****************
1. Represent and Evaluate the Polynomial
2. Add two Polynomials
3. Exit
Enter your choice : 3

Department of AI&ML, YIT Moodbidri 46

Data Structure Lab (BCSL305)

10. Design, Develop and Implement a menu driven Program in C for the following operations
on Binary Search Tree (BST) of Integers
a. Create a BST of N Integers: 6, 9, 5, 2, 8, 15, 24, 14, 7, 8, 5, 2
b. Traverse the BST in Inorder, Preorder and Post Order
c. Search the BST for a given element (KEY) and report the appropriate message
e. Exit

#include<stdio.h>
#include <stdlib.h>
#define MAX 20

struct node
{
int data;
struct node *lchild, *rchild;
};
typedef struct node *NODE;
NODE tree = NULL;
void CreateBST (int a[MAX], int n)
{
NODE temp, p, q;
int i;
for(i=0;i<n;i++)
{
temp =(struct node *)malloc(sizeof(struct node*));
temp->data = a[i];
temp->lchild = temp->rchild = NULL;
if(tree == NULL)
tree = temp;
else
{
p = q = tree;
while(q != NULL)
{
p=q;
if(a[i] < p->data)
q = p->lchild;
else if(a[i] > p->data)
q = p->rchild;
else
{
free(temp);
break;
}
}
if( q == NULL)
{
if(a[i] < p->data)
p->lchild = temp;
else
p->rchild = temp;

Department of AI&ML, YIT Moodbidri 47

Data Structure Lab (BCSL305)

}
}
}
printf("Binary Seacrh Tree created\n\n");
}

void Inorder(NODE tree)

{
if(tree != NULL)
{
Inorder(tree->lchild);
printf("%d ",tree->data);
Inorder(tree->rchild);
}
}

void Preorder(NODE tree)

{
if(tree != NULL)
{
printf("%d ",tree->data);
Preorder(tree->lchild);
Preorder(tree->rchild);
}
}

void Postorder(NODE tree)

{
if(tree != NULL)
{
Postorder(tree->lchild);
Postorder(tree->rchild);
printf("%d ",tree->data);
}
}

void SearchBST()
{
NODE temp1;
int key;
printf("Enter the key to be searched : ");
scanf("%d", &key);
temp1= tree;
while(temp1 != NULL)
{
if(key == temp1->data)
{
printf("The key %d found in the BST", key);
return;
}
else if(key < temp1->data)
temp1 = temp1->lchild;

Department of AI&ML, YIT Moodbidri 48

Data Structure Lab (BCSL305)

else
temp1 = temp1->rchild;
}
printf("Key %d not found in the BST", key);
}

int main()
{
int a[MAX], n, i, choice;
while(1)
{
printf("\n\n**********************MENU*****************");
printf("\n1. Create a BST of n integers\n2. Traverse the
BST in Inorder\n3. Traverse the BST in Preorder\n4. Traverse the BST
in Postorder\n5. Search the BST for a given element (KEY)\n6.
Exit\n");
printf("Enter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1 : printf("Enter the number of integers : ");
scanf("%d",&n);
printf("Enter the elements\n");
for(i=0; i<n; i++)
scanf("%d",&a[i]);
CreateBST(a, n);
break;
case 2 : printf("Inorder Traversal :\n");
Inorder(tree);
break;
case 3 : printf("Preorder Traversal :\n");
Preorder(tree);
break;
case 4 : printf("Postoder Traversal :\n");
Postorder(tree);
break;
case 5 : SearchBST(tree);
break;
case 6 : exit(0);
break;
}
}
}

Department of AI&ML, YIT Moodbidri 49

Data Structure Lab (BCSL305)

OUTPUT

5 9

2 8 15

7 14 24

**********************MENU*****************
1. Create a BST of n integers
2. Traverse the BST in Inorder
3. Traverse the BST in Preorder
4. Traverse the BST in Postorder
5. Search the BST for a given element (KEY)
6. Exit
Enter your choice : 1
Enter the number of integers : 12
Enter the elements
6 9 5 2 8 15 24 14 7 8 5 2
Binary Seacrh Tree created

**********************MENU*****************
1. Create a BST of n integers
2. Traverse the BST in Inorder
3. Traverse the BST in Preorder
4. Traverse the BST in Postorder
5. Search the BST for a given element (KEY)
6. Exit
Enter your choice : 2
Inorder Traversal :
2 5 6 7 8 9 14 15 24

Department of AI&ML, YIT Moodbidri 50

Data Structure Lab (BCSL305)

**********************MENU*****************
1. Create a BST of n integers
2. Traverse the BST in Inorder
3. Traverse the BST in Preorder
4. Traverse the BST in Postorder
5. Search the BST for a given element (KEY)
6. Exit
Enter your choice : 3
Preorder Traversal :
6 5 2 9 8 7 15 14 24

**********************MENU*****************
1. Create a BST of n integers
2. Traverse the BST in Inorder
3. Traverse the BST in Preorder
4. Traverse the BST in Postorder
5. Search the BST for a given element (KEY)
6. Exit
Enter your choice : 4
Postoder Traversal :
2 5 7 8 14 24 15 9 6

**********************MENU*****************
1. Create a BST of n integers
2. Traverse the BST in Inorder
3. Traverse the BST in Preorder
4. Traverse the BST in Postorder
5. Search the BST for a given element (KEY)
6. Exit
Enter your choice : 5
Enter the key to be searched : 8
The key 8 found in the BST

**********************MENU*****************
1. Create a BST of n integers
2. Traverse the BST in Inorder
3. Traverse the BST in Preorder
4. Traverse the BST in Postorder
5. Search the BST for a given element (KEY)
6. Exit
Enter your choice : 5
Enter the key to be searched : 10

Department of AI&ML, YIT Moodbidri 51

Data Structure Lab (BCSL305)

Key 10 not found in the BST

**********************MENU*****************
1. Create a BST of n integers
2. Traverse the BST in Inorder
3. Traverse the BST in Preorder
4. Traverse the BST in Postorder
5. Search the BST for a given element (KEY)
6. Exit
Enter your choice : 6

Department of AI&ML, YIT Moodbidri 52

Data Structure Lab (BCSL305)

11. Design, Develop and Implement a Program in C for the following operations on Graph(G)
of Cities
a. Create a Graph of N cities using Adjacency Matrix.
b. Print all the nodes reachable from a given starting node in a digraph using
DFS/BFS method

#include<stdio.h>
#include<stdlib.h>
#define MAX 10

int source;

void DFS(int a[MAX][MAX], int visited[MAX], int s, int n)

{
int u, v;
u = s;
visited[u] = 1;
if(u != source)
printf(" %d ", u);
for(v=1; v<=n; v++)
{
if(a[u][v] == 1 && visited[v] == 0)
DFS(a,visited, v, n);
}
}

void BFS(int a[MAX][MAX], int visited[MAX], int source, int n)

{
int queue[MAX], f=0, r=0, u, v;
queue[r] = source;
visited[source] =1;
while(f<=r)
{
u = queue[f++];
for(v=1; v<=n; v++)
{
if(a[u][v] == 1 && visited [v] == 0)
{
printf("%d ", v);
visited[v] = 1;
queue[++r] = v;
}
}
}
}

int main()
{
int a[MAX][MAX], visited[MAX], n, choice, i, j, x, y;
printf("Enter the number of vertices in the graph : ");

Department of AI&ML, YIT Moodbidri 53

Data Structure Lab (BCSL305)

scanf("%d", &n);
printf("Enter the adjacency matrix for the graph\n");
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
scanf("%d",&a[i][j]);
printf("Enter the starting node of the graph : ");
scanf("%d",&source);

while(1)
{
printf("\n\n**********************MENU*****************");
printf("\n1. DFS\n2. BFS\n3. Exit\n");
printf("Enter your choice : ");
scanf("%d", &choice);
switch(choice)
{
case 1 : printf("Nodes reachable from %d using DFS
method\n", source);
for(x=1; x<=n; x++)
visited[x] = 0;
DFS(a, visited, source, n);
break;
case 2 : printf("Nodes reachable from %d using BFS
method\n", source);
for(y=1; y<=n; y++)
visited[y] = 0;
BFS(a, visited, source, n);
break;
case 3: exit(0);
break;
}
}
}

OUTPUT

Consider the following graph

2 3

4 5 6 7

Department of AI&ML, YIT Moodbidri 54

Data Structure Lab (BCSL305)

Enter the number of vertices in the graph : 7

Enter the adjacency matrix for the graph
0110000
0001100
0000011
0000000
0000000
0000000
0000000
Enter the starting node of the graph : 1

**********************MENU*****************
1. DFS
2. BFS
3. Exit
Enter your choice : 1
Nodes reachable from 1 using DFS method
2 4 5 3 6 7

**********************MENU*****************
1. DFS
2. BFS
3. Exit
Enter your choice : 2
Nodes reachable from 1 using BFS method
2 3 4 5 6 7

**********************MENU*****************
1. DFS
2. BFS
3. Exit
Enter your choice : 3

Department of AI&ML, YIT Moodbidri 55

Data Structure Lab (BCSL305)

12. Given a File of N employee records with a set K of Keys(4-digit) which uniquely determine
the records in file F. Assume that file F is maintained in memory by a Hash Table(HT) of m
memory locations with L as the set of memory addresses (2-digit) of locations in HT. Let the
keys in K and addresses in L are Integers. Design and develop a Program in C that uses Hash
function H: K L as H(K)=K mod m (remainder method), and implement hashing technique
to map a given key K to the address space L. Resolve the collision (if any) using linear
probing.

#include<stdio.h>
#include<stdlib.h>
#define MAX 100

int main()
{
int n,m,ht[MAX],i, j, k, rec, address, homebucket, currentbucket,
count = 0, choice;
printf("Enter the number of employee records : ");
scanf("%d", &n);
for(i = 0; i < MAX; i++)
ht[i] = -1;
for(k = 0; k <n; k++)
{
printf("\nEnter the record %d\n", k+1);
scanf("%d", &rec);
address = rec % MAX;
homebucket = address;
currentbucket = homebucket;
while(ht[currentbucket] != -1)
{
currentbucket = (currentbucket + 1) % MAX;
if(currentbucket == homebucket)
{
printf("Hash Table Overflow");
exit(0);
}
count++;
}
if(count != 0)
printf("Collision occured %d times and solved using
Linear Probing\n", count);
count = 0;
ht[currentbucket] = rec;
printf("Record : %d\nHome Address : %d\nCurrent Adrress :
%d\n",rec,homebucket,currentbucket);
}
printf("\nHASH TABLE DISPLAY\n");
while(1)
{
printf("\n\n**********************MENU*****************");

Department of AI&ML, YIT Moodbidri 56

Data Structure Lab (BCSL305)

printf("\n1. Complete Hash table contents\n2. Hash Table

showing only record entries\n3. Exit\n\n");
printf("Enter your choice : ");
scanf("%d", &choice);
switch(choice)
{
case 1 : printf("Complete Hash Table Contents :\n");
for(j = 0; j < MAX; j++)
printf("%d %d\n",j,ht[j]);
break;
case 2 : printf("Hash Table showing Records : \n");
for(j = 0; j < MAX; j++)
if(ht[j] != -1)
printf("%d %d\n",j,ht[j]);
break;
case 3 : exit(0);
break;
}
}
}

OUTPUT

Enter the number of employee records : 5

Enter the record 1

1231
Record : 1231
Home Address : 31
Current Adrress : 31

Enter the record 2

1299
Record : 1299
Home Address : 99
Current Adrress : 99

Enter the record 3

1265
Record : 1265
Home Address : 65
Current Adrress : 65

Enter the record 4

2231
Collision occured 1 times and solved using Linear Probing
Record : 2231

Department of AI&ML, YIT Moodbidri 57

Data Structure Lab (BCSL305)

Home Address : 31
Current Adrress : 32

Enter the record 5

2299
Collision occured 1 times and solved using Linear Probing
Record : 2299
Home Address : 99
Current Adrress : 0

HASH TABLE DISPLAY

**********************MENU*****************
1. Complete Hash table contents
2. Hash Table showing only record entries
3. Exit

Enter your choice : 1

Complete Hash Table Contents :
0 2299
1 -1
2 -1
3 -1
4 -1
5 -1
6 -1
7 -1
8 -1
9 -1
10 -1
11 -1
12 -1
13 -1
14 -1
15 -1
16 -1
17 -1
18 -1
19 -1
20 -1
21 -1
22 -1
23 -1
24 -1
25 -1
26 -1

Department of AI&ML, YIT Moodbidri 58

Data Structure Lab (BCSL305)

27 -1
28 -1
29 -1
30 -1
31 1231
32 2231
33 -1
34 -1
35 -1
36 -1
37 -1
38 -1
39 -1
40 -1
41 -1
42 -1
43 -1
44 -1
45 -1
46 -1
47 -1
48 -1
49 -1
50 -1
51 -1
52 -1
53 -1
54 -1
55 -1
56 -1
57 -1
58 -1
59 -1
60 -1
61 -1
62 -1
63 -1
64 -1
65 1265
66 -1
67 -1
68 -1
69 -1
70 -1
71 -1
72 -1

Department of AI&ML, YIT Moodbidri 59

Data Structure Lab (BCSL305)

73 -1
74 -1
75 -1
76 -1
77 -1
78 -1
79 -1
80 -1
81 -1
82 -1
83 -1
84 -1
85 -1
86 -1
87 -1
88 -1
89 -1
90 -1
91 -1
92 -1
93 -1
94 -1
95 -1
96 -1
97 -1
98 -1
99 1299

**********************MENU*****************
1. Complete Hash table contents
2. Hash Table showing only record entries
3. Exit

Enter your choice : 2

Hash Table showing Records :
0 2299
31 1231
32 2231
65 1265
99 1299

**********************MENU*****************
1. Complete Hash table contents
2. Hash Table showing only record entries
3. Exit

Department of AI&ML, YIT Moodbidri 60

Data Structure Lab (BCSL305)

Enter your choice : 3

Department of AI&ML, YIT Moodbidri 61