Data Structures Laboratory BCSL305 BE III Sem

S.D.M. Jainmatt Trust®

A.G.M RURAL COLLEGE OF ENGINEERING AND TECHNOLOGY
VARUR – 581207

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING

LABORATORY MANUAL

III SEMESTER

DATA STRUCTURES LABORATORY

(BCSL305)

2023-2024

Approved By Prof. Shanthbushan B.M

Prepared By Dr. Channamma Patil

Instructor Mr. Fakkiresh Asundi

Dept. of CSE, AGMRCET, Varur Page 1

Data Structures Laboratory BCSL305 BE III Sem

Program 01: Calendar Application

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.

Dynamic Memory Allocation

Allocating memory

There are two ways that memory gets allocated for data storage:

1. Compile Time (or static) Allocation

o Memory for named variables is allocated by the compiler

o Exact size and type of storage must be known at compile time

o For standard array declarations, this is why the size has to be constant

2. Dynamic Memory Allocation

o Memory allocated "on the fly" during run time

o dynamically allocated space usually placed in a program segment known as

the heap or the free store
o Exact amount of space or number of items does not have to be known by the
compiler in advance.
o For dynamic memory allocation, pointers are crucial

There are four functions malloc(), calloc(), realloc() and free() present in <stdlib.h> header file that are
used for Dynamic Memory Allocation. Dynamic Memory Allocation is considered as a very important
concept in the field of Data Structures and is used in almost every Data Structures like linked lists, stacks,
queues etc.

Method Description
malloc() Allocates a single block of requested memory.
calloc() Allocates multiple blocks of requested memory.

Dept. of CSE, AGMRCET, Varur Page 2

Data Structures Laboratory BCSL305 BE III Sem

Method Description
realloc() Reallocates the memory occupied by malloc() or calloc() functions.
free() Frees the dynamically allocated memory.

CODE
#include<stdio.h>
#define noofdays 7
#include<stdlib.h>
#include<string.h>
struct day
{
char dayname[20];
int date;
char activity[50];
};

typedef struct day *daylst;

void adddetails(daylst);
daylst createcal();
void display(daylst);

void main()
{
daylst cal;
cal=createcal();
adddetails(cal);
display(cal);
}

daylst createcal()
{
daylst temp;
int i;

temp=(daylst)malloc(noofdays*sizeof(struct day));
if(temp==NULL)
{
printf("Insufficient memory\n");

Dept. of CSE, AGMRCET, Varur Page 3

Data Structures Laboratory BCSL305 BE III Sem

exit(0);
}
else
{
for(i=0;i<noofdays;i++)
{
strcpy(temp[i].dayname,"-------");
temp[i].date=0;
strcpy(temp[i].activity,"No Activity");
}
}
return temp;
}

void adddetails(daylst cal)

{
int i,ch;

printf("Enter Calendar details\n");

for(i=0;i<noofdays;i++)
{
printf("1.Enter Details\n2.Skip Details\n");
printf("Enter your choice\n");
scanf("%d",&ch);
switch(ch)
{
case 1: printf("Details for Day %d\n",i+1);
printf("Day name: ");
scanf("%s",cal[i].dayname);
printf("\nDate: ");
scanf("%d",&cal[i].date);
printf("\nActivity: ");
scanf("%s",cal[i].activity);
break;
case 2:break;
}
}
}

void display(daylst cal)

{

Dept. of CSE, AGMRCET, Varur Page 4

Data Structures Laboratory BCSL305 BE III Sem

int i;
printf("----------CALENDAfR------------------\n");
printf("DAY NO\tDAY NAME\t\tDATE\tACTIVITY\n");
for(i=0;i<noofdays;i++)
printf("%d\t%s\t\t%d\t%s\n",i+1,cal[i].dayname,cal[i].date,cal[i].activity);
}
OUTPUT

Dept. of CSE, AGMRCET, Varur Page 5

Data Structures Laboratory BCSL305 BE III Sem

Program 02: String Operations

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.

Strings
In C, string is implemented as an array of characters. A string constant in C is always terminated
by a NULL character.
For example, the string “AGMRCET” is stored in memory as shown below:
|A|G|M|R|C|E|T| \0|

The normal operations that can be performed on strings are:

 Substring: Substring is a string obtained by extracting a part of a given string given the
position and length of the substring.
 Indexing: The process of finding the position of pattern string in a given text is called
indexing. It is also called pattern matching. If the pattern string is present in text , the
position of the first occurrence of the pattern string is returned otherwise, 0 is returned.
 Concatenation: The process of appending the second string to the end of first string is
called concatenation.
 Length: The number of characters in a string is called length of the string.

String handling functions in C

String Function Description

Dept. of CSE, AGMRCET, Varur Page 6

Data Structures Laboratory BCSL305 BE III Sem

strlen(str) Returns length of the string str

strcpy(dest,src) Copies the source string src to destination string dest

strcat(str1,str2) Append string str2 to string str1

strcmp(str1,str2) Compare two strings str1 and str2

strrev(str) Reverse the contents of string stored in str

Code
//pattern searching and replacing
#include<stdio.h>
#include<string.h>

int main()
{
char mainstr[200],patternstr[50],replacestr[50],resstr[200];
int i,j,k,noofmatches=0,plen,rlen,t=0;

printf("Enter the main string\n");

fgets(mainstr,200,stdin);
printf("Enter the pattern string\n");
fgets(patternstr,100,stdin);
printf("Enter the replace string\n");
fgets(replacestr,100,stdin);
printf("The input string is\n %s\n",mainstr);
plen=strlen(patternstr)-1;
rlen=strlen(replacestr)-1;

for(i=0;i<strlen(mainstr)-plen;i++)
{
for(j=0;j<plen;j++)
{
if(mainstr[i+j]!=patternstr[j])
break;
}

if(j==plen)
{
noofmatches++;
t=0;

Dept. of CSE, AGMRCET, Varur Page 7

Data Structures Laboratory BCSL305 BE III Sem

for(k=0;k<i;k++)
resstr[t++]=mainstr[k];
for(k=0;k<rlen;k++)
resstr[t++]=replacestr[k];
for(k=i+plen;k<strlen(mainstr);k++)
resstr[t++]=mainstr[k];
resstr[t]='\0';
for(k=0;k<strlen(resstr);k++)
mainstr[k]=resstr[k];
mainstr[k]='\0';
}
}
if(noofmatches>0)
{
printf("%d matches occured in the input text\n",noofmatches);
printf("After replacing the matched patterns the string is \n %s\n",resstr);
}
else
printf("Pattern string not found in the input text\n");
return 0;
}

Output

Enter the main string

Raju and Ramu went to shop to buy milk and cakes

Enter the pattern string

and

Enter the replace string

&

The input string is

Raju and Ramu went to shop to buy milk and cakes

2 matches occured in the input text.

After replacing the matched patterns the string is

Raju & Ramu went to shop to buy milk & cakes.

Dept. of CSE, AGMRCET, Varur Page 8

Data Structures Laboratory BCSL305 BE III Sem

Program 03: Stack of Integers

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

STACK

A stack is an Abstract Data Type (ADT), commonly used in most programming languages. It is
named stack as it behaves like a real-world stack, for example – a deck of cards or a pile of
plates, etc. A real-world stack allows operations at one end only. For example, example, we can
place or remove a card or plate from the top of the stack only. Likewise, Stack ADT allows all
data operations at one end only. At any given time, we can only access the top element of a
stack. This feature makes it LIFO data structure. LIFO stands for Last-in-first-out. Here, the
element which is placed (inserted or added) last, is accessed first. In stack terminology, insertion
operation called PUSH operation and removal operation is called POP operation.

Stack Representation

The following diagram depicts a stack and its operation.

Dept. of CSE, AGMRCET, Varur Page 9

Data Structures Laboratory BCSL305 BE III Sem

A stack can be implemented by means of Array, Structure, Pointer, and Linked List. Stack can
either be a fixed size one or it may have a sense of dynamic resizing. Here, we have implemented
stack using arrays, which makes it a fixed size stack implementation.

Basic Operations

Stack operations rations may involve initializing the stack, using it and then de-initializing it.
Apart from these basic stuffs, a stack is used for the following two primary operations –

 push() − Pushing (storing) an element on the stack.

 pop() − Removing (accessing) an element from the stack.

To use a stack efficiently, we need to check the status of stack as well. For the same purpose,
purpose, the following functionality is added to stacks –

 peek() − get the top data element of the stack, without removing it.
 overflow() − check if stack is full.

 underflow() − check if stack is empty.

At all times, we maintain a pointer to the last pushed data on the stack. As this pointer always
represents the top of the stack, hence named top. The top pointer provides top value of the stack
without actually removing it.

Push Operation

The process of putting a new data element onto stack is known as a Push Operation. Push
operation involves a series of steps:

Step 1 − Checks if the stack is full.

Dept. of CSE, AGMRCET, Varur Page 10

Data Structures Laboratory BCSL305 BE III Sem

Step 2 − If the stack is full, produces an error and exit.

Step 3 − If the stack is not full, increments top to point next empty space.

Step 4 − Adds data element to the stack location, where top is pointing.

Step 5 − Returns success.

Pop Operation

Accessing the content while removing it from the stack, is known as a Pop Operation. In an array
implementation of pop() operation, the data element is not actually removed, instead top is
decremented to a lower position in the stack to point to the next value. But in linked-list
implementation, pop() actually removes data element and deallocates memory space. A Pop
operation may involve the following steps –

Step 1 − Checks if the stack is empty.

Step 2 − If the stack is empty, produces an error and exit.

Step 3 − If the stack is not empty, accesses the data element at which top is pointing.

Step 4 − Decreases the value of top by 1.

Step 5 − Returns success.

Peek

Step 1 − Checks if the stack is empty.

Step 2 − If the stack is empty, produces an error and exit.

Step 3 − If the stack is not empty, return the data element at which top is pointing.

Overflow

Step 1: Check if top is pointing to index equal to MAXSIZE -1

Step 2: If yes then return TRUE

Step 3: If no then return FALSE

Underflow

Step 1: Check if top value is equal to -1

Dept. of CSE, AGMRCET, Varur Page 11

Data Structures Laboratory BCSL305 BE III Sem

Step 2: If yes then return TRUE

Step 3: If no then return FALSE

CODE

//Stack operations
#include<stdio.h>
#include<stdlib.h>
#define MAX 5

void push();
void pop();
void display();
void overflow();
void underflow();
void palindrome();

int stack[20],top=-1;

int main()
{
int ch;
for(;;)
{
printf("---------------STACK OPERATIONS---------------------\n");
printf("1.PUSH\n2.POP\n3.DISPLAY\n4.OVERFLOW\n5.UNDERFLOW\n6.PEEK\
n7.PALINDROME\n8.EXIT\n");
printf("Enter your choice:\n");
scanf("%d",&ch);
switch(ch)
{
case 1:push();
break;
case 2:pop();
break;
case 3:display();
break;
case 4:overflow();
break;
case 5:underflow();
break;
case 6:if(top==-1)
printf("Stack is empty\n");
else
printf("Peek of stack: %d\n",stack[top]);

Dept. of CSE, AGMRCET, Varur Page 12

Data Structures Laboratory BCSL305 BE III Sem

break;
case 7:palindrome();
break;
case 8:exit(0);
default:printf("Invalid choice\n");
}
}
}

void push()
{
int e;
if(top==MAX-1)
{
printf("Stack is full\n");
return;
}
else
{
printf("\nEnter the element to be pushed \n");
scanf("%d",&e);
top=top+1;
stack[top]=e;
}
}

void pop()
{
if(top==-1)
{
printf("Stack is empty\n");
return;
}
else
{
printf("Popped element: %d\n",stack[top]);
top=top-1;
}
}

void display()
{
int i;
if(top==-1)
{
printf("Stack is empty\n");

Dept. of CSE, AGMRCET, Varur Page 13

Data Structures Laboratory BCSL305 BE III Sem

return;
}
else
{
printf("Stack Contents are:\n");
for(i=top;i>=0;i--)
printf("%d\n",stack[i]);
}
}

void overflow()
{
int i;
printf("\nThere are currently %d elements in Stack\nPush %d elements for Stack to
Overflow", top+1, MAX - (top+1));
for(i=top;i<MAX;i++)
push();
printf("Stack overflow\n");
}

void underflow()
{
int i;
printf("\nThere are currently %d elements in Stack\nPop out %d elements for Stack to
Underflow", top+1, MAX - (top+1));

for(i=top;i>=0;i--)
pop();
printf("Stack underflow\n");
}

void palindrome()
{
int i,t[20],j=0;
if(top==-1)
{
printf("Stack is empty\n");
return;
}
else
{
for(i=top;i>=0;i--)
t[j++]=stack[i];

for(i=0;i<=top;i++)
{

Dept. of CSE, AGMRCET, Varur Page 14

Data Structures Laboratory BCSL305 BE III Sem

if(stack[i]!=t[i])
break;
}
if(i==top+1)
printf("Stack elements form palindrome\n");
else
printf("Stack elements doesnot form palindrome\n");
}
}

[write on unruled page]

OUTPUT

-------STACK OPERATIONS---------
1.PUSH
2.POP
3.DISPLAY
4.OVERFLOW
5.UNDERFLOW
6.PEEK
7.PALINDROME
8.EXIT
Enter your choice
1
Enter the element to be pushed
1

-------STACK OPERATIONS---------
1.PUSH
2.POP
3.DISPLAY
4.OVERFLOW
5.UNDERFLOW
6.PEEK
7.PALINDROME
8.EXIT
Enter your choice
1
Enter the element to be pushed
2

-------STACK OPERATIONS---------
1.PUSH
2.POP
3.DISPLAY

Dept. of CSE, AGMRCET, Varur Page 15

Data Structures Laboratory BCSL305 BE III Sem

4.OVERFLOW
5.UNDERFLOW
6.PEEK
7.PALINDROME
8.EXIT
Enter your choice
1
Enter the element to be pushed
1

-------STACK OPERATIONS---------
1.PUSH
2.POP
3.DISPLAY
4.OVERFLOW
5.UNDERFLOW
6.PEEK
7.PALINDROME
8.EXIT
Enter your choice
3
Stack Contents are:
1
2
1
-------STACK OPERATIONS---------
1.PUSH
2.POP
3.DISPLAY
4.OVERFLOW
5.UNDERFLOW
6.PEEK
7.PALINDROME
8.EXIT
Enter your choice
7
Stack elements form palindrome

-------STACK OPERATIONS---------
1.PUSH
2.POP
3.DISPLAY
4.OVERFLOW
5.UNDERFLOW
6.PEEK
7.PALINDROME

Dept. of CSE, AGMRCET, Varur Page 16

Data Structures Laboratory BCSL305 BE III Sem

8.EXIT
Enter your choice
4
There are currently 3 elements in Stack
Push 2 elements for Stack to Overflow
Enter the element to be pushed
3
Enter the element to be pushed
4
Stack is full
Stack Overflow

-------STACK OPERATIONS---------
1.PUSH
2.POP
3.DISPLAY
4.OVERFLOW
5.UNDERFLOW
6.PEEK
7.PALINDROME
8.EXIT
Enter your choice
2

Popped element: 4

-------STACK OPERATIONS---------
1.PUSH
2.POP
3.DISPLAY
4.OVERFLOW
5.UNDERFLOW
6.PEEK
7.PALINDROME
8.EXIT
Enter your choice
6
Peek of stack: 3

-------STACK OPERATIONS---------
1.PUSH
2.POP
3.DISPLAY
4.OVERFLOW
5.UNDERFLOW
6.PEEK

Dept. of CSE, AGMRCET, Varur Page 17

Data Structures Laboratory BCSL305 BE III Sem

7.PALINDROME
8.EXIT
Enter your choice
5
There are currently 4 elements in Stack
Pop out 4 elements for Stack to Underflow

Popped element: 3
Popped element: 1
Popped element: 2
Popped element: 1
Stack Underflow

Program 04: Infix to Postfix Conversion

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.

Algorithm to convert infix to postfix

Step 1: Read the infix expression. Iterate the given expression from left to right, one character at
a time

Step 2: If the scanned character is an operand, put it into postfix expression.

Step 3: If the scanned character is opening round bracket ( '(' ), push it into operator's stack.

Step 4: If the scanned character is closing round bracket ( ')' ), pop out operators from operator's
stack until we find an opening bracket ('(' ).

Step 5: If the scanned character is an operator and operator's stack is empty, push operator into
operators' stack.

Step 6: If the operator's stack is not empty, there may be following possibilities.

 If the precedence of scanned operator is greater than the top most operator of operator's
stack, push this operator into operator’s stack.

Dept. of CSE, AGMRCET, Varur Page 18

Data Structures Laboratory BCSL305 BE III Sem

 If the precedence of scanned operator is less than the top most operator of operator's
stack, pop the operators from operator's stack until we find a low precedence operator
than the scanned character.

Step 7: Repeat Steps 2 to 6 till expression has character.

Step 8: Now pop out all the remaining operators from the operator's stack and push into postfix
expression.

Step 9: Exit

CODE

#include<stdio.h>

int priority(char ch);

char stack[50];
int top= -1;

void main()
{
char infix[50],postfix[50],x,ch;
int i,j=0;
printf("Enter the infix expression\n");
scanf("%s",infix);
for(i=0;infix[i]!='\0';i++)
{
ch=infix[i];
if((ch>='a' && ch<='z')||(ch>='A' && ch<='Z')||(ch>='0' && ch<='9'))
postfix[j++]=ch;
else if(ch=='(')
stack[++top]=ch;
else if(ch==')')
{
while((x=stack[top--])!='(')
postfix[j++]=x;
}

Dept. of CSE, AGMRCET, Varur Page 19

Data Structures Laboratory BCSL305 BE III Sem

else
{
while(priority(stack[top])>=priority(ch))
postfix[j++]=stack[top--];
stack[++top]=ch;
}

}
while(top!= -1)
postfix[j++]=stack[top--];
postfix[j]='\0';
printf("Infix expression = %s\n",infix);
printf("Postfix expression = %s\n",postfix);
}

int priority(char ch)

{
if(ch=='(')
return 0;
if(ch=='+' || ch=='-')
return 1;
if(ch=='*' || ch=='/')
return 2;
if(ch=='^' || ch=='%')
return 3;

return -1;
}

OUTPUT

Dept. of CSE, AGMRCET, Varur Page 20

Data Structures Laboratory BCSL305 BE III Sem

Program 05: Stack Applications

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

Applications of Stack in Data Structure

1. Function Calls-
The state of the program is placed into the Stack when a function is invoked. The preceding
function's execution is continued after the process returns by popping the state off the Stack.
2. Backtracking-
Stacks can be used for backtracking or to verify if an expression's parentheses match. Stacks are
used by the backtracking method to maintain track of the stages of the solution process. The old
state is removed from the Stack when the algorithm goes backwards after pushing the current
state onto it.
3. Undo/Redo Operations-

Dept. of CSE, AGMRCET, Varur Page 21

Data Structures Laboratory BCSL305 BE III Sem

Many apps' undo-redo functionality employs stacks to remember the prior operations. A new
action is added to the Stack each time it is completed. The top member of the Stack is popped to
undo the action, and the original procedure is then carried out.
4. Web browser history-
Stacks are used by web browsers to record the websites you visit. When you click the back
button, the previous URL is removed from the Stack and is added to the Stack each time you
visit a new page.
5. Parenthesis checking-
To determine if brackets are balanced or not, a stack data structure is utilized. An opening
parenthesis is popped off the Stack as a closing parenthesis is added onto it. The brackets are
balanced if the Stack is empty at the conclusion of the expression.
6. Expression Evaluation-
Expressions written in infix, postfix, and prefix notations are evaluated using a stack data
structure. The Stack is used to hold operators and operands, and the top pieces of the Stack are
used to carry out operations.

Algorithm to evaluate postfix expression

Step 1: If a character is an operand push it to Stack

Step 2: If the character is an operator Pop two elements from the Stack.
Operate on these elements according to the operator, and push the result back to the Stack
Step 3: Step 1 and 2 will be repeated until the end has reached.
Step 4: The Result is stored at the top of the Stack, return it
Step 5: End

Tower of Hanoi

The Tower of Hanoi algorithm is a method to solve a mathematical game involving three rods
and a number of disks of different sizes. The algorithm aims to move all of the disks from the
first rod to the last, obeying specific rules. It is a powerful demonstration of recursion in
programming.

The Tower of Hanoi algorithm finds its application in the world of problem-solving, particularly
in puzzles and games.

The objective of the algorithm is to move the entire stack to the last rod, obeying these simple
rules:

1. Only one disk can be moved at a time.

Dept. of CSE, AGMRCET, Varur Page 22

Data Structures Laboratory BCSL305 BE III Sem

2. Each move consists of taking the upper disk from one of the stacks and placing it on top
of another stack or on an empty rod.

3. No disk may be placed on top of a smaller disk.

The number of moves required to solve a Tower of Hanoi puzzle is 2n−1, where n is the number
of disks.

The Tower of Hanoi recursive algorithm involves the following major steps:

1. Recursively move n−1 disks from the source rod to the auxiliary rod.
2. Move the nth disk from the source rod to the target rod.

3. Finally, again recursively, move the n−1 disks from the auxiliary rod to the target rod.

CODE

a. Evaluation of Suffix expression

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

void main()
{
char postfix[50],ch;
int i,top=-1;
float op1,op2,res=0,stack[20];
printf("Enter a valid postfix expression\n");
scanf("%s",postfix);
for(i=0;postfix[i]!='\0';i++)
{
ch=postfix[i];
if(ch>='0' && ch<='9')
stack[++top]=ch-'0';
else
{
op2=stack[top--];
op1=stack[top--];

switch(ch)
{
case '+':res=op1+op2;
break;

Dept. of CSE, AGMRCET, Varur Page 23

Data Structures Laboratory BCSL305 BE III Sem

case '-':res=op1-op2;
break;
case '*':res=op1*op2;
break;
case '/':res=op1/op2;
break;
case '^':res=pow(op1,op2);
break;
case '%':res=(int)op1%(int)op2;
break;
default:printf("Invalid Operator\n");
}
stack[++top]=res;
}
}
printf("Value of %s expression is %f\n",res);
}

Output

Enter a valid postfix expression

45+95-*

Value of 45+95-* expression is 36

Enter a valid postfix expression

632-5*+2^3+

Value of 632-5*+2^3+ expression is 124

b. Tower of Hanoi problem
#include<stdio.h>
void tower(int,char,char,char);
void main()
{
int n;
printf("Enter the no.of discs\n");
scanf("%d",&n);
tower(n,'S','D','T');
}
void tower(int n,char from,char to,char temp)
{
if(n==0)
return;
else

Dept. of CSE, AGMRCET, Varur Page 24

Data Structures Laboratory BCSL305 BE III Sem

{
tower(n-1,from,temp,to);
printf("Move disc %d from %c to %c\n",n,from,to);
tower(n-1,temp,to,from);
}
}

Output

Program 06: Circular Queue

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

Circular Queue
A circular queue is an extended version of a linear queue as it follows the First In First Out
principle with the exception that it connects the last node of a queue to its first by forming a
circular link. Hence, it is also called a Ring Buffer.

Dept. of CSE, AGMRCET, Varur Page 25

Data Structures Laboratory BCSL305 BE III Sem

Implementation of a linear queue brings the drawback of memory wastage. However, memory is
a crucial resource that should be always protected by analyzing all the implications while
designing algorithms or solutions. In the case of a linear queue, when the rear pointer reaches the
MaxSize of a queue, there might be a possibility that after a certain number of dequeue()
operations, it will create an empty space at the start of a queue. Additionally, this newly created
empty space can never be re-utilized as the rear pointer reaches the end of a queue. Hence,
experts introduced the concept of the circular queue to overcome this limitation.

As shown in the figure above, the rear pointer arrives at the beginning of a queue with the help of
a circular link to re-utilize the empty space to insert a new element. This simple addition of a
circular link resolves the problem of memory wastage in the case of queue implementation.
Thus, this particular type of queue is considered the best version of a queue data structure.

Operations on Circular queue

 Enqueue( Insert an element in Circular queue)
 Dequeue (Deleting an element from Circular Queue)

Enqueue(x) Operation

Step 1: Check if the queue is full (Count== Maxsize)

Step 2: If the queue is full, there will be an Overflow error

Step 3: Otherwise, set Rear = (Rear + 1) % Maxsize

Dept. of CSE, AGMRCET, Varur Page 26

Data Structures Laboratory BCSL305 BE III Sem

Step 4: Insert the element into the queue (Queue[Rear] = e)

Step 5: Set count=count+1

Step 6: Exit

Dequeue() Operation

Step 1: Check if the queue is empty (count==0)

Step 2: If the queue is empty, Underflow error

Step 3: Set Element = Queue[Front]

Step 4: set Front = (Front + 1)% Maxsize

Step 5: set count=cout-1

Step 6: Exit

Code
//circular queue operations
#include<stdio.h>
#include<stdlib.h>
#define MAX 5

void insert();
void cdelete();
void display();
void overflow();
void underflow();

char queue[20];
int r=-1,f=0,cnt=0;

int main()
{
int ch;
for(;;)
{
printf("\n-------Queue Operations---------\n");

Dept. of CSE, AGMRCET, Varur Page 27

Data Structures Laboratory BCSL305 BE III Sem

printf("1.INSERT\n2.DELETE\n3.DISPLAY\n4.OVERFLOW\n5.UNDERFLOW\
n6.EXIT\n");
printf("Enter your choice:\n");
scanf("%d",&ch);
switch(ch)
{
case 1:insert();
break;
case 2:cdelete();
break;
case 3:display();
break;
case 4:overflow();
break;
case 5:underflow();
break;
case 6:exit(0);
default:printf("Invalid choice\n");
}
}
}

void insert()
{
int e;
if(cnt==MAX)
{
printf("Queue is full\n");
return;
}
else
{
printf("Enter an element : \n");
scanf("%c",&e);
r=(r+1)%MAX;
queue[r]=e;
cnt=cnt+1;
}
}

void cdelete()
{
if(cnt==0)
{
printf("Queue is empty\n");
return;

Dept. of CSE, AGMRCET, Varur Page 28

Data Structures Laboratory BCSL305 BE III Sem

}
else
{
printf("Deleted element is %c\n",queue[f]);
f=(f+1)%MAX;
cnt=cnt-1;
}
}

void display()
{
int i;
if(cnt==0)
{
printf("Queue is empty\n");
return;
}
else
{
printf(“Contents of the Queue is\n”);
if(f<r)
{
for(i=f;i<=r;i++)
printf("|%4c",queue[i]);
}
else
{
for(i=f;i<MAX;i++)
printf("|%4c",queue[i]);
for(i=0;i<=r;i++)
printf("|%4c",queue[i]);
}
}
}

void overflow()
{
int i;
for(i=cnt;i<=MAX;i++)
insert();
printf("Queue overflow\n");
}

void underflow()
{
int i;

Dept. of CSE, AGMRCET, Varur Page 29

Data Structures Laboratory BCSL305 BE III Sem

for(i=cnt;i>=0;i--)
cdelete();
printf("Queue underflow\n");
}

Output
------Queue Operations------
1.INSERT
2.DELETE
3.DISPLAY
4.OVERFLOW
5.EXIT

Enter your choice

2

Queue is Empty

------Queue Operations------
1.INSERT
2.DELETE
3.DISPLAY
4.OVERFLOW
5.UNDERFLOW
6.EXIT

Enter your choice

1

Enter an element : I

------Queue Operations------
1.INSERT
2.DELETE
3.DISPLAY
4.OVERFLOW
5.UNDERFLOW
6.EXIT

Enter your choice

1

Enter an element : N

------Queue Operations------
1.INSERT
2.DELETE
3.DISPLAY
4.OVERFLOW
5.UNDERFLOW
6.EXIT

Dept. of CSE, AGMRCET, Varur Page 30

Data Structures Laboratory BCSL305 BE III Sem

Enter your choice

4

Enter an element : D
Enter an element : I
Enter an element : A
Queue overflow

------Queue Operations------
1.INSERT
2.DELETE
3.DISPLAY
4.OVERFLOW
5.UNDERFLOW
6.EXIT

Enter your choice

3

Contents of the Queue is

I N D I A

------Queue Operations------
1.INSERT
2.DELETE
3.DISPLAY
4.OVERFLOW
5.UNDERFLOW
6.EXIT

Enter your choice

1

Queue is Full

------Queue Operations------
1.INSERT
2.DELETE
3.DISPLAY
4.OVERFLOW
5.UNDERFLOW
6.EXIT

Enter your choice

2

Deleted element is I

------Queue Operations------
1.INSERT
2.DELETE
3.DISPLAY
4.OVERFLOW
5.UNDERFLOW
6.EXIT

Enter your choice

Dept. of CSE, AGMRCET, Varur Page 31

Data Structures Laboratory BCSL305 BE III Sem

Deleted element is N
Deleted element is D
Deleted element is I
Deleted element is A

Queue is Empty
Queue Underflow

Program 07: Singly Linked List of Student

Data
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

Singly Linked List

Single linked list is a sequence of elements in which every element has link to its next element in
the sequence. In any single linked list, the individual element is called as "Node". Every "Node"
contains two fields, data field, and the next field. The data field is used to store actual value of
the node and next field is used to store the address of next node in the sequence.
The graphical representation of a node in a single linked list is as follows.

Dept. of CSE, AGMRCET, Varur Page 32

Data Structures Laboratory BCSL305 BE III Sem

Operations on Single Linked List

The following operations are performed on a Single Linked List

 Insertion
 Deletion
 Display

Insertion

In a single linked list, the insertion operation can be performed in the following three ways.
1. Inserting At Beginning of the list
2. Inserting At End of the list
3. Inserting At Specific location in the list

Inserting At Beginning of the list

Step 1 - Create a newNode with given value.
Step 2 - Check whether list is Empty (head == NULL)
Step 3 - If it is Empty then, set newNode→next = NULL and head = newNode.
Step 4 - If it is Not Empty then, set newNode→next = head and head = newNode.

Inserting At End of the list

Step 1 - Create a newNode with given value and newNode → next as NULL.
Step 2 - Check whether list is Empty (head == NULL).
Step 3 - If it is Empty then, set head = newNode.
Step 4 - If it is Not Empty then, define a node pointer temp and initialize with head.
Step 5 - Keep moving the temp to its next node until it reaches to the last node in the list
(until temp → next is equal to NULL).
Step 6 - Set temp → next = newNode.

Deletion
In a single linked list, the deletion operation can be performed in the following three ways:
1. Deleting from Beginning of the list
2. Deleting from End of the list
3. Deleting a Specific Node

Deleting from Beginning of the list

Step 1 - Check whether list is Empty (head == NULL)
Step 2 - If it is Empty then, display 'List is Empty!!! Deletion is not possible' and
terminate the function.
Step 3 - If it is Not Empty then, define a Node pointer 'temp' and initialize with head.
Step 4 - Check whether list is having only one node (temp → next == NULL)

Dept. of CSE, AGMRCET, Varur Page 33

Data Structures Laboratory BCSL305 BE III Sem

Step 5 - If it is TRUE then set head = NULL and delete temp (Setting Empty list
conditions)
Step 6 - If it is FALSE then set head = temp → next, and delete temp.

Deleting from End of the list

Step 1 - Check whether list is Empty (head == NULL)
Step 2 - If it is Empty then, display 'List is Empty!!! Deletion is not possible' and
terminate the function.
Step 3 - If it is Not Empty then, defines two Node pointers 'temp1' and 'temp2' and
initialize 'temp1' with head.
Step 4 - Check whether list has only one Node (temp1 → next == NULL)
Step 5 - If it is TRUE. Then, set head = NULL and delete temp1. And terminate the
function. (Setting Empty list condition)
Step 6 - If it is FALSE. Then, set 'temp2 = temp1 ' and move temp1 to its next node.
Repeat the same until it reaches to the last node in the list. (until temp1 → next == NULL)
Step 7 - Finally, Set temp2 → next = NULL and delete temp1.

Displaying a Single Linked List

Step 1 - Check whether list is Empty (head == NULL)
Step 2 - If it is Empty then, display 'List is Empty!!!' and terminate the function.
Step 3 - If it is Not Empty then, define a Node pointer 'temp' and initialize with head.
Step 4 - Keep displaying temp → data with an arrow (--->) until temp reaches to the last
node
Step 5 - Finally display temp → data with arrow pointing to NULL (temp → data -->
NULL).

Code
//Singly linked list operations
#include<stdio.h>
#include<stdlib.h>

struct stud
{
char usn[ 10];
char name[50];
char branch[10];
int sem;
long long int phone;
struct stud *link;
};

typedef struct stud *studlst;

Dept. of CSE, AGMRCET, Varur Page 34

Data Structures Laboratory BCSL305 BE III Sem

studlst create(studlst);
studlst insert_first(studlst);
studlst insert_last(studlst);
studlst delete_first(studlst);
studlst delete_last(studlst);
studlst getnode();
void display(studlst);
void noofnodes(studlst);

int main()
{

int ch;
studlst lst;
lst=NULL;

for(;;)
{
printf("\n=========SINGLY LINKED LIST OPERATIONS==========\n");
printf("\n1.CREATE LIST\n2.DISPLAY\n3.INSERT FIRST\n4.INSERT LAST\
n5.DELETE FIRST\n6.DELETE LAST\n7.NODES COUNT\n8.EXIT\n");
printf("Enter your choice:\n");
scanf("%d",&ch);
switch(ch)
{
case 1:lst=create(lst);
break;
case 2:display(lst);
break;
case 3:lst=insert_first(lst);
break;
case 4:lst=insert_last(lst);
break;
case 5:lst=delete_first(lst);
break;
case 6:lst=delete_last(lst);
break;
case 7:noofnodes(lst);
break;
case 8:exit(0);
default: printf("Invalid choice\n");
}
}

Dept. of CSE, AGMRCET, Varur Page 35

Data Structures Laboratory BCSL305 BE III Sem

studlst create(studlst lst)

{
studlst temp1,cur;
int i,n;
printf("Enter number of students\n");
scanf("%d",&n);

for(i=1;i<=n;i++)
{
temp1=getnode();
temp1->link=lst;
lst=temp1;
}
return lst;
}

studlst getnode()
{
studlst temp;
temp=(studlst)malloc(sizeof(struct stud));
if(temp==NULL)
{
printf("Insufficient memory\n");
exit(0);
}
else
{
printf("Enter the details\n");
printf("USN: ");
scanf("%s",temp->usn);
printf("\nName: ");
scanf("%s",temp->name);
printf("\nBranch: ");
scanf("%s",temp->branch);
printf("\nSem: ");
scanf("%d",&temp->sem);
printf("\nPhone: ");
scanf("%lld",&temp->phone);
temp->link=NULL;
}
return temp;
}

studlst insert_first(studlst lst)

Dept. of CSE, AGMRCET, Varur Page 36

Data Structures Laboratory BCSL305 BE III Sem

{
studlst temp;
temp= getnode();
if(lst==NULL)
lst=temp;
else
{
temp->link=lst;
lst=temp;
}

return lst;
}

studlst insert_last(studlst lst)

{
studls t temp,cur;
temp= getnode();

if(lst==NULL)
lst=temp;
else
{
cur=lst;
while(cur->link!=NULL)
cur=cur->link;
cur->link=temp;
}

return lst;
}

void display(studlst lst)

{
studlst temp;
if(lst==NULL)
{
printf("List is Empty\n");
return;
}
else
{
temp=lst;
printf("The contents of SLL are :\n");
printf("USN\t\tName\tBranch\tSem\tPhone\n")
while(temp!=NULL)

Dept. of CSE, AGMRCET, Varur Page 37

Data Structures Laboratory BCSL305 BE III Sem

{
printf("%s\t\t%s\t%s\t%d\t%lld\n",temp->usn,temp->name,temp->branch,temp-
>sem,temp->phone);
temp=temp->link;
}
}
}

studlst delete_first(studlst lst)

{
studlst temp;
if(lst==NULL)

printf("List is Empty\n");
else
{
temp=lst;
lst=temp->link;
printf("Deleted node with USN %s\n",temp->usn);
free(temp);
}
return lst;
}

studlst delete_last(studlst lst)

{
studlst temp,cur;
if(lst==NULL)

printf("List is Empty\n");
else
{

temp=lst;
while(temp->link!=NULL)
{
cur=temp;
temp=temp->link;
}

cur->link=NULL;
printf("Deleted node with USN %s\n",temp->usn);
free(temp);
}
return lst;

Dept. of CSE, AGMRCET, Varur Page 38

Data Structures Laboratory BCSL305 BE III Sem

void noofnodes(studlst lst)

{
studlst temp;
int count=0;
if(lst==NULL)
{
printf("List is empty\n");
return;
}
else
{
temp=lst;
while(temp!=NULL)
{
count=count+1;
temp=temp->link;
}
}
printf("No. of Nodes = %d\n",count);
}

Output
=========SINGLY LINKED LIST OPERATIONS==========
1.CREATE LIST
2.DISPLAY
3.INSERT FIRST
4.INSERT LAST
5.DELETE FIRST
6.DELETE LAST
7.NODES COUNT
8.EXIT

Enter your choice:

1
Enter number of students
2
Enter the details
USN: 2AV21CS003
Name: Ashwini
Branch: CSE
Sem: 3
Phone: 9188888888

Dept. of CSE, AGMRCET, Varur Page 39

Data Structures Laboratory BCSL305 BE III Sem

Enter the details

USN: 2AV21CS004
Name: Bhuvan
Branch: CSE
Sem: 3
Phone: 8188888888

=========SINGLY LINKED LIST OPERATIONS==========

1.CREATE LIST
2.DISPLAY
3.INSERT FIRST
4.INSERT LAST
5.DELETE FIRST
6.DELETE LAST
7.NODES COUNT
8.EXIT

Enter your choice:

2

The contents of SLL are :

USN Name Branch Sem Phone num

2AV21CS003 Ashwini CSE 3 9188888888
2AV21CS004 Bhuvan CSE 3 8188888888

=========SINGLY LINKED LIST OPERATIONS==========

1.CREATE LIST
2.DISPLAY
3.INSERT FIRST
4.INSERT LAST
5.DELETE FIRST
6.DELETE LAST
7.NODES COUNT
8.EXIT

Enter your choice:

3
Enter the details
USN: 2AV21CS001
Name: Akash
Branch: CSE
Sem: 3
Phone: 8888888888

Dept. of CSE, AGMRCET, Varur Page 40

Data Structures Laboratory BCSL305 BE III Sem

=========SINGLY LINKED LIST OPERATIONS==========

1.CREATE LIST
2.DISPLAY
3.INSERT FIRST
4.INSERT LAST
5.DELETE FIRST
6.DELETE LAST
7.NODES COUNT
8.EXIT

Enter your choice:

4
Enter the details
USN: 2AV21CS008
Name: Kiran
Branch: CSE
Sem: 3
Phone: 8177777777

=========SINGLY LINKED LIST OPERATIONS==========

1.CREATE LIST
2.DISPLAY
3.INSERT FIRST
4.INSERT LAST
5.DELETE FIRST
6.DELETE LAST
7.NODES COUNT
8.EXIT

Enter your choice:

2

The contents of SLL are :

USN Name Branch Sem Phone num
2AV21CS001 Akash CSE 3 8888888888
2AV21CS003 Ashwini CSE 3 9188888888
2AV21CS004 Bhuvan CSE 3 8188888888
2AV21CS008 Kiiran CSE 3 8177777777

=========SINGLY LINKED LIST OPERATIONS==========

1.CREATE LIST
2.DISPLAY
3.INSERT FIRST
4.INSERT LAST
5.DELETE FIRST
6.DELETE LAST

Dept. of CSE, AGMRCET, Varur Page 41

Data Structures Laboratory BCSL305 BE III Sem

7.NODES COUNT
8.EXIT

Enter your choice:

7
No. of Nodes =4

=========SINGLY LINKED LIST OPERATIONS==========

1.CREATE LIST
2.DISPLAY
3.INSERT FIRST
4.INSERT LAST
5.DELETE FIRST
6.DELETE LAST
7.NODES COUNT
8.EXIT

Enter your choice:

5

Deleted node with USN 2AV21CS001

=========SINGLY LINKED LIST OPERATIONS==========

1.CREATE LIST
2.DISPLAY
3.INSERT FIRST
4.INSERT LAST
5.DELETE FIRST
6.DELETE LAST
7.NODES COUNT
8.EXIT

Enter your choice:

6

Deleted node with USN 2AV21CS008

=========SINGLY LINKED LIST OPERATIONS==========

1.CREATE LIST
2.DISPLAY
3.INSERT FIRST
4.INSERT LAST
5.DELETE FIRST
6.DELETE LAST
7.NODES COUNT
8.EXIT

Dept. of CSE, AGMRCET, Varur Page 42

Data Structures Laboratory BCSL305 BE III Sem

Enter your choice:

5

Deleted node with USN 2AV21CS003

=========SINGLY LINKED LIST OPERATIONS==========

1.CREATE LIST
2.DISPLAY
3.INSERT FIRST
4.INSERT LAST
5.DELETE FIRST
6.DELETE LAST
7.NODES COUNT
8.EXIT

Enter your choice:

2

The contents of SLL are :

USN Name Branch Sem Phone num

2AV21CS004 Bhuvan CSE 3 8188888888

Program 08: Doubly Linked List of Employee Data

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

Doubly Linked List

A doubly linked list is an enhancement of a singly linked list in which each node consists of 3
components:
1. a pointer *prev: address of the previous node
2. data: data item
3. a pointer *next: address of next node

Dept. of CSE, AGMRCET, Varur Page 43

Data Structures Laboratory BCSL305 BE III Sem

CODE
//doubly linked list operations
#include<stdio.h>
#include<stdlib.h>

struct emp
{
char ssn[ 10];
char name[50];
char dept[50];
char desig[50];
int sal;
long phone;
struct emp *llink;
struct emp *rlink;
};

typedef struct emp *emplst;

emplst create(emplst);
emplst insert_first(emplst);
emplst insert_last(emplst);
emplst delete_first(emplst);
emplst delete_last(emplst);
emplst getnode();
void display(emplst);

int main()
{

int ch;
emplst lst;
lst=NULL;

for(;;)
{
printf("\n=========DOUBLY LINKED LIST OPERATIONS==========\n");
printf("\n1.CREATE LIST\n2.DISPLAY\n3.INSERT FIRST\n4.INSERT LAST\
n5.DELETE FIRST\n6.DELETE LAST\n7.EXIT\n");

Dept. of CSE, AGMRCET, Varur Page 44

Data Structures Laboratory BCSL305 BE III Sem

printf("Enter your choice:\n");

scanf("%d",&ch);
switch(ch)
{
case 1:lst=create(lst);
break;
case 2:display(lst);
break;
case 3:lst=insert_first(lst);
break;
case 4:lst=insert_last(lst);
break;
case 5:lst=delete_first(lst);
break;

case 6:lst=delete_last(lst);
break;

case 7:exit(0);
default: printf("Invalid choice\n");
}
}

emplst getnode()
{
emplst temp;
temp=(emplst)malloc(sizeof(struct emp));
if(temp==NULL)
{
printf("Insufficient memory\n");
exit(0);
}
else
{
printf("Enter the details\n");
printf("SSN: ");
scanf("%s",temp->ssn);
printf("\nName: ");
scanf("%s",temp->name);
printf("\nDepartment: ");
scanf("%s",temp->dept);
printf("\nDesignation: ");
scanf("%s",temp->desig);
printf("\nSalary: ");

Dept. of CSE, AGMRCET, Varur Page 45

Data Structures Laboratory BCSL305 BE III Sem

scanf("%d",&temp->sal);
printf("\nPhone: ");
scanf("%ld",&temp->phone);
temp->llink=NULL;
temp->rlink=NULL;
}
return temp;
}

emplst create(emplst lst)

{
emplst temp1,cur;
int i,n;
printf("Enter number of employees\n");
scanf("%d",&n);
if(lst==NULL)
{
cur=getnode();
lst=cur;
n=n-1;
}

else
{
cur=lst;
while(cur->rlink!=NULL)
cur=cur->rlink;
}

for(i=1;i<=n;i++)
{
temp1=getnode();
cur->rlink=temp1;
temp1->llink=cur;
cur=temp1;
}
return lst;
}

emplst insert_first(emplst lst)

{
emplst temp;
temp= getnode();
if(lst==NULL)
lst=temp;
else

Dept. of CSE, AGMRCET, Varur Page 46

Data Structures Laboratory BCSL305 BE III Sem

{
temp->rlink=lst;
lst->llink=temp;
lst=temp;
}

return lst;
}

emplst insert_last(emplst lst)

{
emplst temp,cur;
temp= getnode();

if(lst==NULL)
lst=temp;
else
{
cur=lst;
while(cur->rlink!=NULL)
cur=cur->rlink;
cur->rlink=temp;
temp->llink=temp;
}

return lst;
}

void display(emplst lst)

{
emplst temp;
if(lst==NULL)
{
printf("List is Empty\n");
return;
}
else
{
temp=lst;
printf(“The contents of DLL are\n”);
printf(“SSN\tName\tDept\tDesignation\tSalary\tPhone No\n”);

while(temp!=NULL)
{
printf("%s\t%s\t%s\t%s\t%d\t%ld\n",temp->ssn,temp->name,temp->dept,temp-
>desig,temp->sal,temp->phone);

Dept. of CSE, AGMRCET, Varur Page 47

Data Structures Laboratory BCSL305 BE III Sem

temp=temp->rlink;
}
}
}

emplst delete_first(emplst lst)

{
emplst temp;
if(lst==NULL)

printf("List is Empty\n");
else
{
temp=lst;
lst=temp->rlink;
lst->llink=NULL;
printf("Deleted node with ssn %s\n",temp->ssn);
free(temp);
}
return lst;
}

emplst delete_last(emplst lst)

{
emplst temp,cur;
if(lst==NULL)

printf("List is Empty\n");
else
{

temp=lst;
while(temp->rlink!=NULL)
{
cur=temp;
temp=temp->rlink;
}

cur->rlink=NULL;
temp->llink=NULL;
printf("Deleted node with ssn %s\n",temp->ssn);
free(temp);
}
return lst;
}

Dept. of CSE, AGMRCET, Varur Page 48

Data Structures Laboratory BCSL305 BE III Sem

OUTPUT
=========DOUBLY LINKED LIST OPERATIONS==========
1.CREATE LIST
2.DISPLAY
3.INSERT FIRST
4.INSERT LAST
5.DELETE FIRST
6.DELETE LAST
7.EXIT
Enter your choice:
1
Enter number of employees
2
Enter the details
SSN: 1234
Name: Kiran
Department: CSE
Designation: Clerk
Salary: 35000
Phone: 9455665577

SSN: 12355
Name: Ramesh
Department: CSE
Designation: Peon
Salary: 30000
Phone: 9155665577

=========DOUBLY LINKED LIST OPERATIONS==========

1.CREATE LIST
2.DISPLAY
3.INSERT FIRST
4.INSERT LAST
5.DELETE FIRST
6.DELETE LAST
7.EXIT
Enter your choice:
2

SSN Name Dept Designation Salary Phone No

1234 Kiran CSE Clerk 35000 9455665577
1235 Ramesh CSE Peon 30000 9155665577

=========DOUBLY LINKED LIST OPERATIONS==========

Dept. of CSE, AGMRCET, Varur Page 49

Data Structures Laboratory BCSL305 BE III Sem

1.CREATE LIST
2.DISPLAY
3.INSERT FIRST
4.INSERT LAST
5.DELETE FIRST
6.DELETE LAST
7.EXIT
Enter your choice:
3

Enter the details

SSN: 1236
Name: Abhi
Department: CSE
Designation: Driver
Salary: 25000
Phone: 9455665588

=========DOUBLY LINKED LIST OPERATIONS==========

1.CREATE LIST
2.DISPLAY
3.INSERT FIRST
4.INSERT LAST
5.DELETE FIRST
6.DELETE LAST
7.EXIT
Enter your choice:
6
Deleted node with ssn 1235

=========DOUBLY LINKED LIST OPERATIONS==========

1.CREATE LIST
2.DISPLAY
3.INSERT FIRST
4.INSERT LAST
5.DELETE FIRST
6.DELETE LAST
7.EXIT
Enter your choice:
2

SSN Name Dept Designation Salary Phone No

1236 Abhi CSE Driver 25000 9455665588
1234 Kiran CSE Clerk 35000 9455665577

Dept. of CSE, AGMRCET, Varur Page 50

Data Structures Laboratory BCSL305 BE III Sem

Program 09: Polynomial Evaluation and Addition

Develop 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) = 6x 2 y 2 z-4yz 5 +3x 3 yz+2xy 5 z-2xyz 3
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

CODE

//polynomial addition
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

struct term{
int pc;
int px;
int py;
int pz;
struct term *link;
};
typedef struct term *poly1;

poly1 addterm(poly1 p,int pc,int px,int py,int pz)

{
poly1 cur;
poly1 temp;
temp = (poly1)malloc(sizeof(struct term));

temp->pc=pc;
temp->px=px;
temp->py=py;
temp->pz=pz;

cur = p;
while(cur->link != p)

Dept. of CSE, AGMRCET, Varur Page 51

Data Structures Laboratory BCSL305 BE III Sem

{
cur = cur->link;
}
cur->link = temp;
temp->link = p;
return p;
}

void display(poly1 p)
{
poly1 cur;
if (p->link == p)
{
printf("Polynomial is empty.n");
return;
}

cur = p->link;
while(cur!=p)
{
printf("%dx^%dy^%dz^%d ", cur->pc, cur->px, cur->py, cur->pz);
cur = cur->link;
if (cur != p)
{
printf("+ ");
}
}
printf("\n");
}

int fnEvaluatePolynomial(poly1 poly, int x, int y, int z)

{
int result = 0,termValue;
poly1 cur;
if (poly->link == poly)
{
return result;
}

cur = poly->link;

Dept. of CSE, AGMRCET, Varur Page 52

Data Structures Laboratory BCSL305 BE III Sem

do
{
termValue = cur->pc;
termValue *= pow(x, cur->px);
termValue *= pow(y, cur->py);
termValue *= pow(z, cur->pz);

result += termValue;

cur = cur->link;
} while (cur != poly);

return result;
}

int matchterm(poly1 p1, poly1 p2)

{
int match=1;
if(p1->px != p2->px)
match=0;
if(p1->py != p2->py)
match=0;
if(p1->pz != p2->pz)
match=0;
return match;
}

poly1 addpoly(poly1 p1, poly1 p2, poly1 psum)

{
poly1 cur,cur1,cur2;
int match=0;
cur1 = p1->link;
cur2 = p2->link;
do
{
psum = addterm(psum, cur1->pc, cur1->px, cur1->py, cur1->pz);
cur1 = cur1->link;
}while(cur1 != p1);

do
{

Dept. of CSE, AGMRCET, Varur Page 53

Data Structures Laboratory BCSL305 BE III Sem

cur1 = psum->link;
match = 0;
do
{
if(matchterm(cur1, cur2))
{
cur1->pc += cur2->pc;
match = 1;
break;
}
cur1 = cur1->link;

}while(cur1 != psum);
if(!match)
{
psum = addterm(psum, cur2->pc, cur2->px, cur2->py, cur2->pz);
}

cur2 = cur2->link;

}while(cur2 != p2);

return psum;

int main()
{
int n,x=1,y=2,z=3,iRes;
poly1 p1,p2,psum;
p1 = (poly1)malloc(sizeof(struct term));
p1->link = p1;
p2 = (poly1)malloc(sizeof(struct term));
p2->link = p2;
psum = (poly1)malloc(sizeof(struct term));
psum->link = psum;
p1=addterm(p1,6,2,2,1);
p1=addterm(p1,4,0,1,5);
p1=addterm(p1,3,3,1,1);

p1=addterm(p1,2,1,5,1);

Dept. of CSE, AGMRCET, Varur Page 54

Data Structures Laboratory BCSL305 BE III Sem

p1=addterm(p1,2,1,1,3);

printf("\nPOLY1(x, y, z) = ");
display(p1);

p2=addterm(p2,1,1,1,1);
p2=addterm(p2,4,3,1,1);

printf("\nPOLY2(x, y, z) = ");
display(p2);
psum = addpoly(p1, p2, psum);
printf("\nPOLYSUM(x, y, z) = ");
display(psum);
iRes = fnEvaluatePolynomial(psum, x, y, z);
printf("nResult of POLYSUM(%d, %d, %d): %dn", x, y, z, iRes);

return 0;
}

OUTPUT
POLY1(x, y, z) = 6x^2y^2z^1 + 4x^0y^1z^5 + 3x^3y^1z^1 + 2x^1y^5z^1 + 2x^1y^1z^3
POLY2(x, y, z) = 1x^1y^1z^1 + 4x^3y^1z^1

POLYSUM(x, y, z) = 6x^2y^2z^1 + 4x^0y^1z^5 + 7x^3y^1z^1 + 2x^1y^5z^1 + 2x^1y^1z^3 +

1x^1y^1z^1

Result of POLYSUM(1, 2, 3): 2364

Program 10: Binary Search Tree

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

CODE
//binary search tree operations

Dept. of CSE, AGMRCET, Varur Page 55

Data Structures Laboratory BCSL305 BE III Sem

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

struct node
{
int data;
struct node *llink;
struct node *rlink;
};
typedef struct node *tree;

tree getnode();
tree create(tree);
void inorder(tree);
void preorder(tree);
void postorder(tree);
void search(tree,int);

int main()
{
tree t = NULL;
int ch,key,i,n,ele;

printf("Enter number of nodes\n");

scanf("%d", &n);
printf("Enter %d numbers\n", n);
for(i=0;i<n;i++)
t=create(t);

for(;;)
{
printf("\n===========BINARY SEARCH TREE
OPERATIONS==========\n");
printf("\n1.PREORDER\n2.INORDER\n3.POSTORDER\n4.SEARCH\n5.EXIT\
n");
printf("Enter your choice: \n");
scanf("%d",&ch);

switch(ch)
{
case 1: preorder(t);

Dept. of CSE, AGMRCET, Varur Page 56

Data Structures Laboratory BCSL305 BE III Sem

break;
case 2: inorder(t);
break;
case 3: postorder(t);
break;
case 4: printf("Enter the searching element\n");
scanf("%d",&key);
search(t,key);
break;

case 5: exit(0);

default: printf("Invalid choice\n");

tree getnode()
{
tree temp;
temp = (tree ) malloc (sizeof(struct node));
if(temp==NULL)
{
printf("Insufficient memory\n");
exit(0);
}
else
{
printf("Enter the node value\n");
scanf("%d",&temp->data);
temp->llink=NULL;
temp->rlink=NULL;
}
return temp;
}

tree create(tree t)
{

Dept. of CSE, AGMRCET, Varur Page 57

Data Structures Laboratory BCSL305 BE III Sem

tree temp,prev,cur;
temp=getnode();
if(t==NULL)
return temp;
prev = NULL;
cur = t;

while(cur != NULL)
{
prev = cur;

if(temp->data == cur->data)
{
printf("Duplicate items not allowed\n");
free(temp);
return t;
}

if(temp->data < cur->data)

cur=cur->llink;
else
cur=cur->rlink;
}

if(temp->data < prev->data)

prev->llink = temp;
else
prev->rlink = temp;

return t;

void preorder(tree t)
{
if(t != NULL)
{
printf("%d\t",t->data);
preorder(t->llink);
preorder(t->rlink);

Dept. of CSE, AGMRCET, Varur Page 58

Data Structures Laboratory BCSL305 BE III Sem

}
}

void inorder(tree t)
{
if(t != NULL)
{
inorder(t->llink);
printf("%d\t",t->data);
inorder(t->rlink);
}
}

void postorder(tree t)
{
if(t != NULL)
{
postorder(t->llink);
postorder(t->rlink);
printf("%d\t",t->data);
}
}

void search(tree t, int key)

{
if(t != NULL)
{
if(key < t->data)
search(t->llink, key);
else if(key > t->data)
search(t->rlink, key);
else
printf("Successful Search\n");
}
else

printf("Unsuccessful Search\n");
}
OUTPUT
Enter number of nodes
6

Dept. of CSE, AGMRCET, Varur Page 59

Data Structures Laboratory BCSL305 BE III Sem

Enter 6 numbers
Enter the node value
50
Enter the node value
30
Enter the node value
70
Enter the node value
40
Enter the node value
60
Enter the node value
20
===========BINARY SEARCH TREE OPERATIONS==========
1.PREORDER
2.INORDER
3.POSTORDER
4.SEARCH
5.EXIT
Enter your choice:
1

50 30 20 40 70 60
===========BINARY SEARCH TREE OPERATIONS==========
1.PREORDER
2.INORDER
3.POSTORDER
4.SEARCH
5.EXIT
Enter your choice:
2
20 30 40 50 60 70
===========BINARY SEARCH TREE OPERATIONS==========
1.PREORDER
2.INORDER
3.POSTORDER
4.SEARCH
5.EXIT
Enter your choice:
3
20 40 30 60 70 50

Dept. of CSE, AGMRCET, Varur Page 60

Data Structures Laboratory BCSL305 BE III Sem

===========BINARY SEARCH TREE OPERATIONS==========

1.PREORDER
2.INORDER
3.POSTORDER
4.SEARCH
5.EXIT
Enter your choice:
4
Enter the searching element
60
Successful Search

Program 11: Graph Reachability using DFS/BFS

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

CODE
//Graph Reachability using BFS/DFS
#include<stdio.h>
void bfs(int);
void dfs(int);
int graph[10][10],n,visited[20];

int main()
{
int i,j,start;
printf("Enter the number of vertices\n");
scanf("%d",&n);
for(i=0;i<n;i++)
visited[i]=0;

Dept. of CSE, AGMRCET, Varur Page 61

Data Structures Laboratory BCSL305 BE III Sem

printf("Enter the adjacency matrix\n");

for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&graph[i][j]);
printf("Enter starting vertex\n");
scanf("%d",&start);
bfs(start-1);
printf("Vertices which can be reached from vertex %d using BFS are: \n",start);
for(i=0;i<n;i++)
if(visited[i])
printf("%4d",i+1);
printf("\n");
for(i=0;i<n;i++)
visited[i]=0;
dfs(start);
printf("Vertices which can be reached from vertex %d using DFS are: \n",start);
for(i=0;i<n;i++)
if(visited[i])
printf("%4d",i+1);

void bfs(int start)

{
int q[20],r=-1,f=0,fv,i;
visited[start]=1;
q[++r]=start;
while(f<=r)
{
fv=q[f++];
for(i=0;i<n;i++)
{
if(graph[fv][i]&&!visited[i])
{
visited[i]=1;
q[++r]=i;
}
}

Dept. of CSE, AGMRCET, Varur Page 62

Data Structures Laboratory BCSL305 BE III Sem

void dfs(int start)

{
int i;
visited[start]=1;
for(i=0;i<n;i++)
{
if(graph[start][i]&&!visited[i])
dfs(i);
}
}

OUTPUT
Enter the number of vertices
4
Enter the adjacency matrix
0110
1001
1001
0110
Enter starting vertex
1
Vertices which can be reached from vertex 1 using BFS are:
1 2 3 4
Vertices which can be reached from vertex 1 using DFS are:
1 2 3 4

Program 12: Hashing & Linear Probing

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.

CODE

//Hashing
#include <stdio.h>

Dept. of CSE, AGMRCET, Varur Page 63

Data Structures Laboratory BCSL305 BE III Sem

#include <stdlib.h>
#include <string.h>
#define MAX_EMP 100
#define MAX_TAB 50
struct EMPLOYEE
{
int key;
char name[50];
};
typedef struct EMPLOYEE *emp;
emp hashtable[MAX_TAB];
int cmphash(int, int);
void addemp(emp, int);
emp searchemp(int, int);
int main()
{
int m,i,n = 0;
int srchkey,empkey;
char empname[50];
emp temp,found;
FILE *file = fopen("employee.txt", "r");
printf("Enter the size of the hash table (m): ");
scanf("%d", &m);
for (i = 0; i < m; i++)
{
hashtable[i] = NULL;
}

if(file == NULL)
{
printf("Error opening file\n");
return 1;
}
while(fscanf(file, "%d %s", &empkey, empname) != EOF)
{
temp = (emp)malloc(sizeof(struct EMPLOYEE));
temp->key = empkey;

Dept. of CSE, AGMRCET, Varur Page 64

Data Structures Laboratory BCSL305 BE III Sem

strcpy(temp->name, empname);
addemp(temp, m);
n++;
}
fclose(file);
printf("Enter a key to search for an employee record: ");
scanf("%d", &srchkey);
found = searchemp(srchkey, m);
if(found != NULL)
{
printf("Employee found with key %d:\n", found->key);
printf("Name: %sn", found->name);
}
else
{
printf("Employee with key %d not found\n", srchkey);
}
}
void addemp(emp e, int m)
{
int index = cmphash(e->key, m);
while(hashtable[index] != NULL)
{
index = (index + 1) % m;
}
hashtable[index] = e;
}

int cmphash(int key, int m)

{
return key % m;
}

emp searchemp(int key, int m)

{
int index = cmphash(key, m);

while(hashtable[index] != NULL)

Dept. of CSE, AGMRCET, Varur Page 65

Data Structures Laboratory BCSL305 BE III Sem

{
if(hashtable[index]->key == key)
{
return hashtable[index];
}
index = (index + 1) % m;
}
return NULL;
}

OUTPUT
Enter the size of the hash table (m): 50
Enter a key to search for an employee record: 5216
Employee found with key 5216:
Name: sanjay

Enter the size of the hash table (m): 50

Enter a key to search for an employee record: 234
Employee with key 234 not found

Dept. of CSE, AGMRCET, Varur Page 66