DSA LAB Programs

1. Develop a Program in C for the following: a) Declare a

calendar as an array of 7 elements (A dynamically Created
array) to represent7 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>
#include <string.h>

typedef struct {
char* dayName;
int date;
char* activity;
} DayInfo;

DayInfo* create() {
DayInfo* day = (DayInfo*)malloc(sizeof(DayInfo));
if (day == NULL) {
fprintf(stderr, "Memory allocation failed.\n");
exit(EXIT_FAILURE);
}
 day->dayName = NULL;
day->activity = NULL;
return day;
}

void read(DayInfo* day) {

char temp[100];
printf("Enter day name: ");
fgets(temp, sizeof(temp), stdin);
temp[strcspn(temp, "\n")] = '\0'; // Remove the newline character
day->dayName = strdup(temp);

printf("Enter date: ");

scanf("%d", &day->date);
getchar(); // Consume the newline character left by scanf

printf("Enter activity: ");

fgets(temp, sizeof(temp), stdin);
temp[strcspn(temp, "\n")] = '\0';
day->activity = strdup(temp);
}

void display(DayInfo* week, int numDays) {

printf("Week's Activity Details:\n");
for (int i = 0; i < numDays; i++) {
printf("Day %d - %s (Date: %d): %s\n", i + 1, week[i].dayName,
week[i].date, week[i].activity);
}
}

int main() {
 int numDays = 7;
DayInfo* week = (DayInfo*)malloc(numDays * sizeof(DayInfo));
if (week == NULL) {
fprintf(stderr, "Memory allocation failed.\n");
return EXIT_FAILURE;
}
for (int i = 0; i < numDays; i++) {
week[i] = *create();
read(&week[i]);
}
display(week, numDays);

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

free(week[i].dayName);
free(week[i].activity);
}
free(week);
return 0;
}

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 <string.h>

// Function to calculate the length of a string

int stringLen(char str[]);

// Function to concatenate two strings

void stringCat(char dest[], char src[]);

int main() {
int i = 0, j, k = 0, flag = 0;
char STR[50], PAT[15], REP[15], RESULT[50];

// Input the main string

printf("Enter String\n");
fgets(STR, sizeof(STR), stdin);
STR[strcspn(STR, "\n")] = '\0'; // Remove newline character

// Input the pattern to be replaced

printf("Enter Pattern\n");
fgets(PAT, sizeof(PAT), stdin);
PAT[strcspn(PAT, "\n")] = '\0'; // Remove newline character

// Input the substitution key

printf("Enter Substitution Key\n");
fgets(REP, sizeof(REP), stdin);
REP[strcspn(REP, "\n")] = '\0'; // Remove newline character

// Loop through the main string

while (STR[i] != '\0') {
 j = 0;
// Check if substring matches the pattern
while ((STR[i + j] == PAT[j]) && (PAT[j] != '\0')) {
j++;
}

if (PAT[j] == '\0') {
// If the loop reached the end of the pattern, it means a match
is found
flag = 1;
RESULT[k] = '\0';
// Concatenate the substitution key to the result
stringCat(RESULT, REP);
k = k + stringLen(REP);
// Move the main string index to skip the matched pattern
i = i + (j - 1);
} else {
// If no match, copy the character to the result
RESULT[k++] = STR[i];
}

i++; // Move to the next character in the main string

}

RESULT[k] = '\0';

// Output the result

printf("The result is\n");
if (flag)
puts(RESULT);
else
 printf("Pattern not found\n");

return 0;
}

// Function to calculate the length of a string

int stringLen(char str[]) {
int len = 0;
while (str[len] != '\0') {
len++;
}
return len;
}

// Function to concatenate two strings

void stringCat(char dest[], char src[]) {
int i = 0, j = 0;
while (dest[i] != '\0') {
i++;
}

while (src[j] != '\0') {

dest[i + j] = src[j];
j++;
}
}

3. Design, Develop and Implement 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 onto Stack
b. Pop an Element from Stack
c. Demonstrate Overflow and Underflow situations on
Stack
d. Display the status of Stack
e. Exit

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

int stack_full(int top);

int stack_empty(int top);
void push(int stack[], int *top, int ele);
int pop(int stack[], int *top);
int is_palindrome(int stack[], int top);
void display(int stack[], int top);

void main()
{
int stack[MAX], top = -1, ele, ch;
for(;;)
//while(1)
{
printf("\nMenu\n");
printf("1. Push\n2. Pop\n3. Check Palindrome\n4. Stack
Status\n5. Display\n6. Exit\n");
scanf("%d", &ch);
switch(ch)
{
case 1:
if(stack_full(top))
printf("Stack Full\n");
else
{
printf("Enter an Element\n");
scanf("%d", &ele);
push(stack, &top, ele);
}
break;

case 2:
if(stack_empty(top))
printf("Stack Empty\n");
else
{
ele = pop(stack, &top);
printf("Deleted Element is %d", ele);
}
break;

case 3:
if(stack_empty(top))
printf("Stack Empty\n");
else if(is_palindrome(stack, top))
{
printf("Stack is Palindrome\n");
display(stack, top);
}
 else
printf("Stack is not Palindrome\n");
break;

case 4:
if(stack_empty(top))
printf("Stack Empty\n");
else if(stack_full(top))
printf("Stack Full\n");
else
printf("Stack contains %d elements\n", top+1);
break;

case 5:
if(stack_empty(top))
printf("Stack Empty\n");
else
display(stack, top);
break;

case 6:
exit(0);

default:
printf("Entered Menu is not available");
break;
}
}
}
int stack_full(int top)
{
 if(top == MAX-1)
return 1;
return 0;
}

int stack_empty(int top)

{
if(top == -1)
return 1;
return 0;
}

void push(int stack[], int *top, int ele)

{

stack[++(*top)] = ele;
}

int pop(int stack[], int *top)

{
return stack[(*top)--];
}

int is_palindrome(int stack[], int top)

{
int i, not_palindrome=0;
for(i=0; i<=top/2; i++)
{
if(stack[i] != stack[top-i])
{
 not_palindrome = 1;
break;
}
}

if(not_palindrome)
return 0;
else
return 1;
}

void display(int stack[], int top)

{
int i;
for(i=0; i <= top; i++)
{
printf("%d ", stack[i]);
}
printf("\n");
}

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>
// Enumeration to represent different token types
typedef enum {lparen, rparen, plus, minus, mul, divi, mod, pwr, eos,
operand} precedence;

// Function to get the next token from the infix expression

precedence getToken(char infix[], char *symbol, int *n);

// Function to convert infix expression to postfix expression

void convert(char infix[]);

// Function to push a token onto the stack

void push(int stack[], int *top, precedence token);

// Function to pop a token from the stack

precedence pop(int stack[], int *top);

// Function to print a token

void printToken(precedence token);

// Main function
void main() {
char infix[30];
printf("Enter Infix Expression\n");
gets(infix);
convert(infix);
}

// Function to get the next token from the infix expression

precedence getToken(char infix[], char *symbol, int *n) {
*symbol = infix[(*n)++];
switch(*symbol) {
 case '(': return lparen;
case ')': return rparen;
case '+': return plus;
case '-': return minus;
case '*': return mul;
case '/': return divi;
case '%': return mod;
case '^': return pwr;
case '\0': return eos;
default: return operand;
}
}

// Function to convert infix expression to postfix expression

void convert(char infix[]) {
int stack[20], top = 0, n = 0;
int icp[] = {5, 4, 1, 1, 2, 2, 2, 3, 0}; // In-coming precedence
int isp[] = {0, 4, 1, 1, 2, 2, 2, 3, 0}; // In-stack precedence
precedence token;
char symbol;
stack[0] = eos;

// Loop through the infix expression to convert to postfix

for(token = getToken(infix, &symbol, &n); token != eos; token =
getToken(infix, &symbol, &n)) {
if(token == operand)
printf("%c", symbol);
else if(token == rparen) {
// Pop and print tokens until an lparen is encountered
while(stack[top] != lparen) {
printToken(pop(stack, &top));
 }
pop(stack, &top); // Pop the lparen
} else {
// Pop and print tokens while in-stack precedence is higher
while(isp[stack[top]] >= icp[token]) {
printToken(pop(stack, &top));
}
push(stack, &top, token);
}
}

// Pop and print any remaining tokens on the stack

while(stack[top] != eos) {
printToken(pop(stack, &top));
}
}

// Function to push a token onto the stack

void push(int stack[], int *top, precedence token) {
stack[++(*top)] = token;
}

// Function to pop a token from the stack

precedence pop(int stack[], int *top) {
return stack[(*top)--];
}

// Function to print a token

void printToken(precedence token) {
switch(token) {
case plus:
 printf("+");
break;
case minus:
printf("-");
break;
case mul:
printf("*");
break;
case divi:
printf("/");
break;
case mod:
printf("%c", '%');
break;
case pwr:
printf("^");
break;
}
}

5. Design, Develop and Implement 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

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

// Global variables and stack array

int i, top = -1;
int op1, op2, res, s[20];
char postfix[90], symb, result=1;

// Function to push an item onto the stack

void push(int item)
{
top = top + 1;
s[top] = item;
}

// Function to pop an item from the stack

int pop()
{
int item;
item = s[top];
top = top - 1;
return item;
}

// Main function
void main()
{
// Accepting postfix expression from the user
printf("\nEnter a valid postfix expression:\n");
scanf("%s", postfix);
 // Processing each symbol in the postfix expression
for (i = 0; postfix[i] != '\0'; i++)
{
symb = postfix[i];
if (isdigit(symb))
{
// If the symbol is a digit, push its integer value onto the stack
push(symb -'0' );
}
else
{
// If the symbol is an operator, pop two operands, perform the
operation, and push the result back onto the stack
op2 = pop();
op1 = pop();
switch (symb)
{
case '+':
push(op1 + op2);
break;
case '-':
push(op1 - op2);
break;
case '*':
push(op1 * op2);
break;
case '/':
push(op1 / op2);
break;
case '%':
push(op1 % op2);
 break;
case '^':

for(int i= 0;i<op2;i++)
{
result*=op1;
}
push(result);
break;
default:
push(0);
}
}
}

// The final result is at the top of the stack

res = pop();
printf("\n Result = %d", res);
}

TOH

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

// Function to solve Tower of Hanoi problem

void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod)
{
// Base case: If there is only one disk, move it from source to
destination
 if (n == 1)
{
printf("\n Move disk 1 from rod %c to rod %c", from_rod,
to_rod);
return;
}

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

as the auxiliary rod
towerOfHanoi(n - 1, from_rod, aux_rod, to_rod);

// Move the nth disk from source to destination

printf("\n Move disk %d from rod %c to rod %c", n, from_rod,
to_rod);

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

as the auxiliary rod
towerOfHanoi(n - 1, aux_rod, to_rod, from_rod);
}

int main()
{
int n = 4; // Number of disks

// A, B, and C are names of rods

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

return 0;
}
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

// Function prototypes
void cqInsert(char queue[], int *rear, int *count);
void cqDelete(char queue[], int *front, int *count);
void display(char queue[], int front, int count);

int main() {
char queue[MAX];
int front = 0, rear = -1, ch, count = 0;

for (;;) {
// Display menu options
printf("\nMenu\n");
printf("1. Insert\n2. Delete\n3. Demonstrate Overflow and
Underflow\n4. Display\n5. Exit\n");
scanf("%d", &ch);
 switch (ch) {
case 1:
// Insert operation
cqInsert(queue, &rear, &count);
break;
case 2:
// Delete operation
cqDelete(queue,&front, &count);
break;
case 3:
// Demonstrate Overflow and Underflow
if (count == MAX) {
printf("Queue is Full (Overflow)\n");
} else if (count == 0) {
printf("Queue is Empty (Underflow)\n");
} else {
printf("Queue is neither Full nor Empty\n");
}
break;
case 4:
// Display operation
display(queue, front, count);
break;
case 5:
// Exit the program
exit(0);
}
}
}

// Function to insert a character into the circular queue

void cqInsert(char queue[], int *rear, int *count) {
char ele;
printf("Enter a Character to Insert\n");
scanf(" %c", &ele);

// Check for overflow

if (*count == MAX) {
printf("Queue is Full (Overflow)\n");
return;
}

// Increment rear circularly and insert the character

*rear = (*rear + 1) % MAX;
queue[*rear] = ele;

// Increment the count of elements in the queue

(*count)++;
}

// Function to delete a character from the circular queue

void cqDelete(char queue[],int *front, int *count) {
// Check for underflow
if (*count == 0) {
printf("Queue is Empty (Underflow)\n");
return;
}

// Print the character to be deleted from the front of the queue

printf("Deleted Character is %c\n", queue[*front]);

// Increment front circularly to delete the character

 *front = (*front + 1) % MAX;

// Decrement the count of elements in the queue

(*count)--;
}

// Function to display all characters in the circular queue

void display(char queue[], int front, int count) {
int i;
if (count == 0) {
printf("Queue is Empty\n");
return;
}

printf("The Characters are\n");

// Iterate through the circular queue and print characters

for (i = 0; i < count; i++) {
printf("%c\t", queue[i]);
front = (front + 1) % MAX;
}
printf("\n");
}

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<math.h>

// Node structure to represent a term in a polynomial

typedef struct poly_node {
float coef; // Coefficient of the term
int expx, expy, expz; // Exponents for variables X, Y, and Z
struct poly_node *link; // Pointer to the next term
} POLY;

// Function to create a new node and return its address

POLY *getNode();

// Function to read a polynomial from the user

void read_poly(POLY *head, int n);

// Function to print a polynomial

void print_poly(POLY *head);

// Function to add two polynomials

POLY *add_poly(POLY *h1, POLY *h2);

// Function to compare two terms based on exponents

int compare(POLY *temp1, POLY *temp2);
// Function to attach a new term to the resultant polynomial
void attach(float cf, POLY *exptemp, POLY **tempres);

// Function to delete a term from a polynomial

POLY *delete(POLY *head, POLY *temp);

// Function to evaluate the polynomial for given exponents

void evaluate(POLY *head);

// Main function
void main() {
int n1, n2;
POLY *POLY1 = getNode();
POLY *POLY2 = getNode();
POLY *POLYSUM = getNode();

// Initialize head nodes

POLY1->expx = -1;
POLY1->link = POLY1;
POLY2->link = POLY2;
POLYSUM->link = POLYSUM;

printf("\nEnter the number of terms for both polynomials\n");

scanf("%d%d",&n1, &n2);

printf("\nEnter 1st Polynomial\n");

read_poly(POLY1, n1);
printf("\n1st Polynomial is\n");
print_poly(POLY1);

printf("\nEnter 2nd Polynomial\n");

 read_poly(POLY2, n2);
printf("\n2nd Polynomial is\n");
print_poly(POLY2);

POLYSUM = add_poly(POLY1, POLY2);

printf("\nThe Resultant polynomial is\n");
print_poly(POLYSUM);

evaluate(POLYSUM);
}

// Function to create a new node and return its address

POLY *getNode() {
POLY *temp = (POLY *) malloc(sizeof(POLY));
if(temp == NULL) {
printf("No Memory\n");
exit(0);
}
return temp;
}

// Function to read a polynomial from the user

void read_poly(POLY *head, int n) {
int i;
POLY *new = NULL;
POLY *temp = head;

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

new = getNode();
printf("Enter Coef and Exps\n");
scanf("%f%d%d%d", &(new->coef), &(new->expx),
&(new->expy), &(new->expz));
(temp->link) = new;
temp = temp->link;
}

temp->link = head;
return;
}

// Function to print a polynomial

void print_poly(POLY *head) {
POLY *temp = head->link;

while(temp != head) {
printf("%f*X^%d*Y^%d*Z^%d\t", temp->coef, temp->expx,
temp->expy, temp->expz);
temp = temp->link;
}

printf("\n");
return;
}

// Function to add two polynomials

POLY *add_poly(POLY *h1, POLY *h2) {
float cf;
POLY *temp1 = h1->link, *temp2 = NULL;
POLY *result = getNode();
POLY *tempres = result;

while(temp1 != h1) {
 temp2 = h2->link;

while(temp2 != h2) {
switch(compare(temp1, temp2)) {
case 1:
cf = temp1->coef + temp2->coef;
if(cf) {
attach(cf, temp1, &tempres);
}
temp1 = temp1->link;
h2 = delete(h2, temp2);
temp2 = h2->link;
break;
case 2:
temp2 = temp2->link;
break;
}
}

if(temp1 != h1) {
attach(temp1->coef, temp1, &tempres);
temp1 = temp1->link;
}
}

temp2 = h2->link;

while(temp2 != h2) {
attach(temp2->coef, temp2, &tempres);
temp2 = temp2->link;
}
 tempres->link = result;
return result;
}

// Function to compare two terms based on exponents

int compare(POLY *temp1, POLY *temp2) {
if((temp1->expx == temp2->expx) && (temp1->expy ==
temp2->expy) && (temp1->expz == temp2->expz)) {
return 1;
}
return 2;
}

// Function to attach a new term to the resultant polynomial

void attach(float cf, POLY *exptemp, POLY **tempres) {
POLY *new = getNode();
new->coef = cf;
new->expx = exptemp->expx;
new->expy = exptemp->expy;
new->expz = exptemp->expz;
(*tempres)->link = new;
*tempres = new;
return;
}

// Function to delete a term from a polynomial

POLY* delete(POLY *head, POLY *temp) {
POLY *previous = head, *present = head->link;

while(present != temp) {
 previous = present;
present = present->link;
}

previous->link = present->link;
free(present);
return head;
}

// Function to evaluate the polynomial for given exponents

void evaluate(POLY *head) {
float result = 0.0;
int x, y, z;
POLY *temp = head->link;

printf("\nEnter exponents\n");
scanf("%d%d%d", &x, &y, &z);

while(temp != head) {
result += (temp->coef) * pow(x, temp->expx) * pow(y,
temp->expy) * pow(z, temp->expz);
temp = temp->link;
}

printf("\nResult after evaluation is %f\n", result);

return;
}

8. Design, Develop and Implement 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>

// Node structure to store employee details

typedef struct node {
char ssn[20], name[20], department[20], designation[20];
float sal;
long int phno;
struct node *llink, *rlink; // Pointers for doubly linked list
} NODE;

// Head node structure to keep track of the list

typedef struct headnode {
int count; // Number of records in the list
struct node *llink, *rlink; // Pointers for doubly linked list
} HEAD;

// Function to create a new node and return its address

NODE *getNode();
// Function to insert a node at the front of the list
void insfront(HEAD *head);

// Function to insert a node at the rear of the list

void insrear(HEAD *head);

// Function to delete a node from the front of the list

void delfront(HEAD *head);

// Function to delete a node from the rear of the list

void delrear(HEAD *head);

// Function to display all the records in the list

void display(HEAD *head);

// Main function
void main() {
int ch;
HEAD *head = (HEAD *) malloc(sizeof(HEAD));
head->count = 0;
head->llink = NULL;
head->rlink = NULL;

for(;;) {
printf("\n\nMenu\n");
printf("\n1. Insert Front\n2. Insert Rear\n3. Delete Front\n4.
Delete Rear\n5. Display\n6. Exit\n");
scanf("%d", &ch);

switch(ch) {
 case 1:
insfront(head);
break;
case 2:
insrear(head);
break;
case 3:
if(head->rlink == NULL)
printf("List Empty");
else
delfront(head);
break;
case 4:
if(head->rlink == NULL)
printf("List Empty");
else
delrear(head);
break;
case 5:
if(head->rlink == NULL)
printf("List Empty");
else
display(head);
break;
case 6:
exit(0);
}
}
}

// Function to create a new node and return its address

NODE *getNode() {
NODE *temp = (NODE *) malloc(sizeof(NODE));
if(temp == NULL) {
printf("No Memory\n");
exit(0);
}
return temp;
}

// Function to insert a node at the front of the list

void insfront(HEAD *head) {
NODE *new = getNode();
NODE *next = head->rlink;

printf("Enter Details such as SSN Name Department Designation

Salary PhNo\n");
scanf("%s%s%s%s%f%ld", (new->ssn), (new->name),
(new->department), (new->designation),
&(new->sal), &(new->phno));

if(next != NULL)
next->llink = new;

new->rlink = next;
head->rlink = new;
(head->count)++;
}

// Function to insert a node at the rear of the list

void insrear(HEAD *head) {
NODE *new = getNode();
 NODE *temp = NULL;

printf("Enter Details such as SSN Name Department Designation

Salary PhNo\n");
scanf("%s%s%s%s%f%ld", (new->ssn), (new->name),
(new->department), (new->designation),
&(new->sal), &(new->phno));

(head->count)++;
new->rlink = NULL;

if(head->rlink == NULL) {
head->rlink = new;
return;
}

temp = head->rlink;

while(temp->rlink != NULL)
temp = temp->rlink;

temp->rlink = new;
new->llink = temp;
}

// Function to delete a node from the front of the list

void delfront(HEAD *head) {
NODE *temp = head->rlink;

printf("Deleted Record is\n");

printf("%s\t%s\t%s\t%s\t%f\t%ld\n", (temp->ssn),
(temp->name), (temp->department), (temp->designation),
(temp->sal), (temp->phno));

head->rlink = temp->rlink;
free(temp);
(head->count)--;
}

// Function to delete a node from the rear of the list

void delrear(HEAD *head) {
NODE *previous = NULL, *present = head->rlink;

if(present->rlink == NULL) {
head->rlink = NULL;
} else {
while(present->rlink != NULL) {
previous = present;
present = present->rlink;
}
previous->rlink = NULL;
}

printf("Deleted Record is\n");

printf("%s\t%s\t%s\t%s\t%f\t%ld\n", (present->ssn),
(present->name), (present->department),
(present->designation), (present->sal), (present->phno));

(head->count)--;
free(present);
}
// Function to display all the records in the list
void display(HEAD *head) {
NODE *temp = head->rlink;

printf("Total Number of records are %d\n", head->count);

printf("SSN\tName\tDepartment\tDesignation\tSalary\t\tPhNo\n")
;

while(temp != NULL) {
printf("%s\t%s\t%s\t\t%s\t\t%f\t%ld\n", (temp->ssn),
(temp->name), (temp->department), (temp->designation),
(temp->sal), (temp->phno));
temp = temp->rlink;
}
}

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>
#define COMPARE(x, y) ( (x == y) ? 0 : (x > y) ? 1 : -1)

struct node
{
int coef;
int xexp, yexp, zexp;
struct node *link;
};
typedef struct node *NODE;

NODE getnode()
{
NODE x;
x = (NODE) malloc(sizeof(struct node));
if(x == NULL)
{
printf("Running out of memory \n");
return NULL;
}
return x;
}

NODE attach(int coef, int xexp, int yexp, int zexp, NODE head)
{
NODE temp, cur;
temp = getnode();
temp->coef = coef;
temp->xexp = xexp;
 temp->yexp = yexp;
temp->zexp = zexp;
cur = head->link;
while(cur->link != head)
{
cur = cur->link;
}
cur->link = temp;
temp->link = head;
return head;
}

NODE read_poly(NODE head)

{
int i, j, coef, xexp, yexp, zexp, n;
printf("\nEnter the no of terms in the polynomial: ");
scanf("%d", &n);
for(i=1; i<=n; i++)
{
printf("\n\tEnter the %d term: ",i);
printf("\n\t\tCoef = ");
scanf("%d", &coef);
printf("\n\t\tEnter Pow(x) Pow(y) and Pow(z): ");
scanf("%d", &xexp);
scanf("%d", &yexp);
scanf("%d", &zexp);
head = attach(coef, xexp, yexp, zexp, head);
}
return head;
}
void display(NODE head)
{
NODE temp;
if(head->link == head)
{
printf("\nPolynomial does not exist.");
return;
}
temp = head->link;

while(temp != head)
{
printf("%dx^%dy^%dz^%d", temp->coef, temp->xexp,
temp->yexp, temp->zexp);
temp = temp->link;
if(temp != head)
printf(" + ");
}
}

int poly_evaluate(NODE head)

{
int x, y, z, sum = 0;
NODE poly;

printf("\nEnter the value of x,y and z: ");

scanf("%d %d %d", &x, &y, &z);

poly = head->link;
while(poly != head)
{
 sum += poly->coef * pow(x,poly->xexp)* pow(y,poly->yexp)
* pow(z,poly->zexp);
poly = poly->link;
}
return sum;
}

NODE poly_sum(NODE head1, NODE head2, NODE head3)

{
NODE a, b;
int coef;
a = head1->link;
b = head2->link;

while(a!=head1 && b!=head2)

{
while(1)
{
if(a->xexp == b->xexp && a->yexp == b->yexp &&
a->zexp == b->zexp)
{
coef = a->coef + b->coef;
head3 = attach(coef, a->xexp, a->yexp, a->zexp,
head3);
a = a->link;
b = b->link;
break;
} //if ends here
if(a->xexp!=0 || b->xexp!=0)
{
switch(COMPARE(a->xexp, b->xexp))
 {
case -1 : head3 = attach(b->coef, b->xexp,
b->yexp, b->zexp, head3);
b = b->link;
break;

case 0 : if(a->yexp > b->yexp)

{
head3 = attach(a->coef, a->xexp,
a->yexp, a->zexp, head3);
a = a->link;
break;
}
else if(a->yexp < b->yexp)
{
head3 = attach(b->coef, b->xexp,
b->yexp, b->zexp, head3);
b = b->link;
break;
}
else if(a->zexp > b->zexp)
{
head3 = attach(a->coef, a->xexp,
a->yexp, a->zexp, head3);
a = a->link;
break;
}
else if(a->zexp < b->zexp)
{
head3 = attach(b->coef, b->xexp,
b->yexp, b->zexp, head3);
 b = b->link;
break;
}
case 1 : head3 =
attach(a->coef,a->xexp,a->yexp,a->zexp,head3);
a = a->link;
break;
} //switch ends here
break;
} //if ends here
if(a->yexp!=0 || b->yexp!=0)
{
switch(COMPARE(a->yexp, b->yexp))
{
case -1 : head3 = attach(b->coef, b->xexp,
b->yexp, b->zexp, head3);
b = b->link;
break;
case 0 : if(a->zexp > b->zexp)
{
head3 = attach(a->coef, a->xexp,
a->yexp, a->zexp, head3);
a = a->link;
break;
}
else if(a->zexp < b->zexp)
{
head3 = attach(b->coef, b->xexp,
b->yexp, b->zexp, head3);
b = b->link;
break;
 }
case 1 : head3 = attach(a->coef, a->xexp,
a->yexp, a->zexp, head3);
a = a->link;
break;
}
break;
}
if(a->zexp!=0 || b->zexp!=0)
{
switch(COMPARE(a->zexp,b->zexp))
{
case -1 : head3 =
attach(b->coef,b->xexp,b->yexp,b->zexp,head3);
b = b->link;
break;
case 1 : head3 = attach(a->coef, a->xexp,
a->yexp, a->zexp, head3);
a = a->link;
break;
}
break;
}
}
}
while(a!= head1)
{
head3 = attach(a->coef,a->xexp,a->yexp,a->zexp,head3);
a = a->link;
}
while(b!= head2)
 {
head3 = attach(b->coef,b->xexp,b->yexp,b->zexp,head3);
b = b->link;
}
return head3;
}

void main()
{
NODE head, head1, head2, head3;
int res, ch;
head = getnode(); /* For polynomial evalaution */
head1 = getnode(); /* To hold POLY1 */
head2 = getnode(); /* To hold POLY2 */
head3 = getnode(); /* To hold POLYSUM */

head->link=head;
head1->link=head1;
head2->link=head2;
head3->link= head3;

while(1)
{
printf("\n~~~Menu~~~");
printf("\n1.Represent and Evaluate a Polynomial P(x,y,z)");
printf("\n2.Find the sum of two polynomials POLY1(x,y,z)");
printf("\nEnter your choice:");
scanf("%d",&ch);
switch(ch)
{
case 1: printf("\n~~~~Polynomial evaluation
P(x,y,z)~~~\n");
head = read_poly(head);
printf("\nRepresentation of Polynomial for
evaluation: \n");
display(head);
res = poly_evaluate(head);
printf("\nResult of polynomial evaluation is : %d
\n", res);
break;

case 2: printf("\nEnter the POLY1(x,y,z): \n");

head1 = read_poly(head1);
printf("\nPolynomial 1 is: \n");
display(head1);

printf("\nEnter the POLY2(x,y,z): \n");

head2 = read_poly(head2);
printf("\nPolynomial 2 is: \n");
display(head2);

printf("\nPolynomial addition result: \n");

head3 = poly_sum(head1,head2,head3);
display(head3);
break;
case 3: exit(0);
}
}
}
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
d. Delete an element (ELEM) from BST
e. Exit
#include<stdio.h>
#include<stdlib.h>

// Node structure for a binary search tree

typedef struct t_node {
char data;
struct t_node *llink; // Left link
struct t_node *rlink; // Right link
} TNODE;

// Function to perform inorder traversal on a binary search tree

void inorder(TNODE *root);

// Function to perform preorder traversal on a binary search tree

void preorder(TNODE *root);

// Function to perform postorder traversal on a binary search tree

void postorder(TNODE *root);

// Function to search for an element in the binary search tree

int search(TNODE *root, int key);
// Function to create a new node and return its address
TNODE *getnode();

// Function to insert an element into the binary search tree

TNODE *insert(TNODE *root, int ele);

// Function to delete an element from the binary search tree

TNODE *delete(TNODE *root, int ele);

// Function to find the minimum node in a binary search tree

TNODE *findMin(TNODE *root);

// Main function
void main() {
TNODE *root = NULL;
int ch, flag;
int ele, key;

for (;;) {

printf("\n1.Insert\n2.Inorder\n3.Preorder\n4.Postorder\n5.Search\
n6.Delete\n7.Exit\n");
printf("\nEnter your choice\n");
scanf("%d", &ch);

switch (ch) {
case 1:
printf("Enter the element to be inserted\n");
scanf("%d", &ele);
root = insert(root, ele);
break;
case 2:
if (root == NULL)
printf("Empty tree\n");
else {
printf("The contents are\n");
inorder(root);
}
break;
case 3:
if (root == NULL)
printf("Empty tree\n");
else {
printf("The contents are\n");
preorder(root);
}
break;
case 4:
if (root == NULL)
printf("Empty tree\n");
else {
printf("The contents are\n");
postorder(root);
}
break;
case 5:
printf("Enter the element to be searched\n");
scanf("%d", &key);
flag = search(root, key);
if (flag)
printf("Found\n");
else
 printf("Not Found\n");
break;
case 6:
printf("Enter the element to be deleted\n");
scanf("%d", &ele);
root = delete(root, ele);
break;
case 7:
exit(0);
}
}
}

// Function to create a new node and return its address

TNODE *getnode() {
TNODE *temp = (TNODE *)malloc(sizeof(TNODE));
if (temp == NULL) {
printf("No Memory\n");
exit(0);
}
return temp;
}

// Function to insert an element into the binary search tree

TNODE *insert(TNODE *root, int ele) {
TNODE *new = NULL;

if (root == NULL) {
new = getnode();
new->data = ele;
new->rlink = new->llink = NULL;
 return new;
}

if (ele > root->data)

root->rlink = insert(root->rlink, ele);

if (ele < root->data)

root->llink = insert(root->llink, ele);

return root;
}

// Function to perform inorder traversal on a binary search tree

void inorder(TNODE *root) {
if (root != NULL) {
inorder(root->llink);
printf("%d ", root->data);
inorder(root->rlink);
}
}

// Function to perform preorder traversal on a binary search tree

void preorder(TNODE *root) {
if (root != NULL) {
printf("%d ", root->data);
preorder(root->llink);
preorder(root->rlink);
}
}

// Function to perform postorder traversal on a binary search tree

void postorder(TNODE *root) {
if (root != NULL) {
postorder(root->llink);
postorder(root->rlink);
printf("%d ", root->data);
}
}

// Function to search for an element in the binary search tree

int search(TNODE *root, int key) {
if (root != NULL) {
if (key == root->data)
return 1;

if (key > root->data)

return (search(root->rlink, key));

if (key < root->data)

return (search(root->llink, key));
}

return 0;
}

// Function to delete an element from the binary search tree

TNODE *delete(TNODE *root, int ele) {
TNODE *temp = NULL;

if (root == NULL)
printf("Element not found\n");
else if (ele < root->data)
 root->llink = delete(root->llink, ele);
else if (ele > root->data)
root->rlink = delete(root->rlink, ele);
else {
if (root->llink != NULL && root->rlink != NULL) {
temp = findMin(root->rlink);
root->data = temp->data;
root->rlink = delete(root->rlink, temp->data);
} else {
temp = root;
if (root->llink == NULL)
root = root->rlink;
else if (root->rlink == NULL)
root = root->llink;
free(temp);
}
}

return root;
}

// Function to find the minimum node in a binary search tree

TNODE *findMin(TNODE *root) {
if (root == NULL)
return NULL;

if (root->llink != NULL)
return findMin(root->llink);
else
return root;
}
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 graph using DFS/BFSmethod.

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

int a[50][50], n, visited[50];

int q[20], front = -1,rear = -1;
int s[20], top = -1, count=0;

void bfs(int v)
{
int i, cur;
visited[v] = 1;
q[++rear] = v;
while(front!=rear)
{
cur = q[++front];
for(i=1;i<=n;i++)
{
if((a[cur][i]==1)&&(visited[i]==0))
{
q[++rear] = i;
visited[i] = 1;
printf("%d ", i);
 }
}
}
}

void dfs(int v)
{
int i;
visited[v]=1;
s[++top] = v;
for(i=1;i<=n;i++)
{
if(a[v][i] == 1&& visited[i] == 0 )
{
printf("%d ", i);
dfs(i);
}
}
}

int main()
{

int ch, start, i,j;

printf("\nEnter the number of vertices in graph: ");
scanf("%d",&n);
printf("\nEnter the adjacency matrix:\n");
for(i=1; i<=n; i++)
{
for(j=1;j<=n;j++)
scanf("%d",&a[i][j]);
 }

for(i=1;i<=n;i++)
visited[i]=0;
printf("\nEnter the starting vertex: ");
scanf("%d",&start);

printf("\n==>1. BFS: Print all nodes reachable from a given

starting node");
printf("\n==>2. DFS: Print all nodes reachable from a given
starting node");
printf("\n==>3:Exit");
printf("\nEnter your choice: ");
scanf("%d", &ch);
switch(ch)
{
case 1: printf("\nNodes reachable from starting vertex %d are:
", start);
bfs(start);
for(i=1;i<=n;i++)
{
if(visited[i]==0)
printf("\nThe vertex that is not reachable is %d" ,i);
}
break;

case 2: printf("\nNodes reachable from starting vertex %d

are:\n",start);
dfs(start);
break;
 case 3: exit(0);
default: printf("\nPlease enter valid choice:");
}
}

2. Given a File of N employee records with a set K of Ke

4-digit) which uniquely determine the records in file F. Assum
hat file F is maintained in memory by a Hash Table (HT) of
memory locations with L as the set of memory address
2-digit) of locations in HT. Let the keys in K and addresses in
re Integers. Develop a Program in C that uses Hash function H
K →L as H(K)=K mod m (remainder method), and impleme
ashing technique to map a given key K to the address space
Resolve the collision (if any) using linear probing.

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

int key[10], n, m;
int *ht, index;
int count = 0;

void insert(int key) {

index = key % m;
while (ht[index] != -1) {
index = (index + 1) % m;
}
 ht[index] = key;
count++;
}

void display() {
int i;
if (count == 0) {
printf("\nHash Table is empty");
return;
}

printf("\nHash Table contents are:\n ");

for (i = 0; i < m; i++)
printf("\n T[%d] --> %d ", i, ht[i]);
}

int main() {
int i;
FILE *file = fopen("employee_records.txt", "r");
if (file == NULL) {
printf("Could not open the file.");
return 1;
}

fscanf(file, "%d", &n);

fscanf(file, "%d", &m);

ht = (int *)malloc(m * sizeof(int));

for (i = 0; i < m; i++)

ht[i] = -1;
 for (i = 0; i < n; i++)
{
fscanf(file, "%d", &key[i]);
}
fclose(file);

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

if (count == m) {
printf("\n~~~Hash table is full. Cannot insert the record %d
key~~~", i + 1);
break;
}
insert(key[i]);
}

// Displaying Keys inserted into hash table

display();

free(ht); // Freeing allocated memory

return 0;
}