RB Institute of Management Studies

LAB MANUAL
Data Structures (629401)

MASTER OF COMPUTER APPLICATIONS(MCA)

II SEMESTER

2023-2025

PREPARED BY

PATEL SONALI MAHESHBHAI

(235490694084)
Q1. Create a Structure with following Data Members:
1. Integer Array
2. Size of the Array Sort the Array using various Sorting algorithms such as
(i) Selection Sort (ii) Bubble Sort (iii) Two-way Merge Sort (iv) Quick Sort
(v) Heap Sort. And store the sorted Array in a text file.

Code :
#include <stdio.h>
#include <stdlib.h>
// Structure definition
struct Array {
int *arr;
int size;
};
// Function prototypes
void selectionSort(int arr[], int n);
void bubbleSort(int arr[], int n);
void mergeSort(int arr[], int l, int r);
void merge(int arr[], int l, int m, int r);
void quickSort(int arr[], int low, int high);
int partition(int arr[], int low, int high);
void heapSort(int arr[], int n);
void heapify(int arr[], int n, int i);
void swap(int *a, int *b);
void printArray(int arr[], int n);
void storeSortedArrayToFile(int arr[], int n);

int main() {
struct Array arrStruct;
int n;

printf("Enter the size of the array: ");

scanf("%d", &n);

arrStruct.size = n;
arrStruct.arr = (int *)malloc(n * sizeof(int));
 printf("Enter the elements of the array:\n");
for (int i = 0; i < n; i++) {
scanf("%d", &arrStruct.arr[i]);
}

// Sort the array using different sorting algorithms

selectionSort(arrStruct.arr, n); // Selection Sort
// bubbleSort(arrStruct.arr, n); // Bubble Sort
// mergeSort(arrStruct.arr, 0, n - 1); // Merge Sort
// quickSort(arrStruct.arr, 0, n - 1); // Quick Sort
// heapSort(arrStruct.arr, n); // Heap Sort

printf("Sorted array: ");

printArray(arrStruct.arr, n);

// Store sorted array to a text file

storeSortedArrayToFile(arrStruct.arr, n);

free(arrStruct.arr);
return 0;
}

// Selection Sort
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int min_index = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[min_index]) {
min_index = j;
}
}
swap(&arr[i], &arr[min_index]);
}
}

// Bubble Sort
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
swap(&arr[j], &arr[j + 1]);
}
}
}
}
// Merge Sort
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}

void merge(int arr[], int l, int m, int r) {

int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;

int L[n1], R[n2];

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

L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];

i = 0;
j = 0;
k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}

while (i < n1) {

arr[k] = L[i];
i++;
k++;
}

while (j < n2) {

arr[k] = R[j];
j++;
k++;
}
}

// Quick Sort
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);

quickSort(arr, low, pi - 1);

quickSort(arr, pi + 1, high);
}
}

int partition(int arr[], int low, int high) {

int pivot = arr[high];
int i = (low - 1);

for (int j = low; j <= high - 1; j++) {

if (arr[j] < pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}

// Heap Sort
void heapSort(int arr[], int n) {
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
for (int i = n - 1; i > 0; i--) {
swap(&arr[0], &arr[i]);
heapify(arr, i, 0);
}
}

void heapify(int arr[], int n, int i) {

int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;

if (l < n && arr[l] > arr[largest])

largest = l;
if (r < n && arr[r] > arr[largest])
largest = r;
 if (largest != i) {
swap(&arr[i], &arr[largest]);
heapify(arr, n, largest);
}
}

// Function to store sorted array in a text file

void storeSortedArrayToFile(int arr[], int n) {
FILE *fp;
fp = fopen("sorted_array.txt", "w");
if (fp == NULL) {
printf("Error opening file!\n");
exit(1);
}
for (int i = 0; i < n; i++) {
fprintf(fp, "%d ", arr[i]);
}
fclose(fp);
printf("Sorted array is stored in 'sorted_array.txt' file.\n");
}
Output:- ( store the sorted Array in a text file.)

Q2 Create a Structure with following Data Members:

1. Integer Array
2. Size of the Array Search an element in Array using Linear (Sequential) Search and
Binary Search, and Display result in file. For Sequential Search, assume that input array is
Unordered and for Binary Search assume that input array is Ordered and develop
programs accordingly.
Code:
#include <stdio.h>
#include <stdlib.h>
// Structure definition
struct Array {
int *arr;
int size;
};

// Function prototypes
int linearSearch(struct Array arrStruct, int key);
int binarySearch(struct Array arrStruct, int key);
void displayResultsToFile(int result, char *searchType);

int main() {
struct Array arrStruct;
int n, key, linearResult, binaryResult;

printf("Enter the size of the array: ");

scanf("%d", &n);

arrStruct.size = n;
arrStruct.arr = (int *)malloc(n * sizeof(int));

printf("Enter the elements of the array:\n");

for (int i = 0; i < n; i++) {
scanf("%d", &arrStruct.arr[i]);
}

printf("Enter the element to search: ");

scanf("%d", &key);

// Perform linear search

linearResult = linearSearch(arrStruct, key);
displayResultsToFile(linearResult, "Linear");
 // Perform binary search (assuming the array is sorted)
// First, let's sort the array
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arrStruct.arr[j] > arrStruct.arr[j + 1]) {
int temp = arrStruct.arr[j];
arrStruct.arr[j] = arrStruct.arr[j + 1];
arrStruct.arr[j + 1] = temp;
}
}
}

binaryResult = binarySearch(arrStruct, key);

displayResultsToFile(binaryResult, "Binary");

free(arrStruct.arr);
return 0;
}

// Linear search function

int linearSearch(struct Array arrStruct, int key) {
for (int i = 0; i < arrStruct.size; i++) {
if (arrStruct.arr[i] == key) {
return i; // Return index if found
}
}
return -1; // Return -1 if not found
}

// Binary search function

int binarySearch(struct Array arrStruct, int key) {
 int low = 0;
int high = arrStruct.size - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arrStruct.arr[mid] == key) {
return mid; // Return index if found
}
if (arrStruct.arr[mid] < key) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1; // Return -1 if not found
}

// Function to display search results in a text file

void displayResultsToFile(int result, char *searchType) {
FILE *fp;
fp = fopen("search_results.txt", "a");
if (fp == NULL) {
printf("Error opening file!\n");
exit(1);
}
if (result != -1) {
fprintf(fp, "%s search: Element found at index %d.\n", searchType, result);
} else {
fprintf(fp, "%s search: Element not found.\n", searchType);
}
fclose(fp);
}
Output:-
Q 3. Create a “Stack” data structure with following Data members:
1. Integer Array
2. Stack Pointer (Top of Stack: Is it same as the Size of the Array) Perform the following
operations on stack using user-defined functions: 1. Push 2. Pop 3. Isempty 4. Isfull 5.
Peep Create a file which stores all values of Array through Stack. Has it reversed the order
of the elements of the Array? Why?
Code:
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<malloc.h>
struct ArrayStack
{
int top;
int capacity;
int *array;
};
struct ArrayStack* createstack(int cap)
{
struct ArrayStack *stack;
stack=malloc(sizeof(struct ArrayStack));
stack->capacity=cap;
stack->top=-1;
stack->array=malloc(sizeof(int)*stack->capacity);
return(stack);
}
int isFull(struct ArrayStack *stack)
{
if(stack->top==stack->capacity)
{
return(1);
}
else
{
return(0);
}
}
int isEmpty(struct ArrayStack *stack)
{
if(stack->top==-1)
{
return(1);
}
else
{
return(0);
}
}
void push(struct ArrayStack *stack,int item)
{
if(!isFull(stack))
{
stack->top++;
stack->array[stack->top]=item;
}
}
int peep(struct ArrayStack *stack)
{
int item;
if(!isFull(stack))
{
item=stack->array[stack->top];
return(item);
}
else
{
return(-1);
}
}
int pop(struct ArrayStack *stack)
{
int item;
if(!isEmpty(stack))
{
item=stack->array[stack->top];
stack->top--;
return(item);
}
return(-1);
}
void main()
{
struct ArrayStack *stack;
int choice,item,cap;
int peepitem;
/* printf("Enter the Capicity of the Stack");
scanf("%d",&cap);*/
stack=createstack(4);
do
{
printf("\n1. Push");
printf("\n2. Pop");
printf("\n3. Peep");
printf("\n4. Exit");
printf("\nEnter Your Choice");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("\nEnter n number");
scanf("%d",&item);
push(stack,item);
break;
case 2:
item=pop(stack);
if(item==-1)
{
printf("Stack is Empty");
}
else
{
printf("\n Poped value is %d",item);
}
break;
case 3:
peepitem=peep(stack);
if(peepitem==-1)
{
printf("Stack is Empty");
}
else
{
printf("\nYour Peep Element is : %d",peepitem);
}
break;
case 4:
exit(0);
break;
}
getch();
} while(choice!=4);
}
Output :

Q 4. Create a “Linked List” structure with the following data members:

1. A Data
2. A link to the next node Perform the following operations on stack using user-defined
functions: 1. Insert a value X at the first place 2. Insert a value X at the end of the list
3. Insert a value X at the place so that it preserves the ordering of the terms in the
increasing order. i. Delete an element whose address is given by X ii. Copy a linked linear
list Create a file which stores all values of list.
Code:
#include<stdio.h>
#include<conio.h>
struct Node
{
int data;
struct Node *next;
}*top = NULL;
void push(int);
void pop();
void display();
void isFull();
void isEmpty();
void main()
{
int choice,value;
printf("\n:: Stack using Linked List ::\n");
while(1){
printf("\n****** MENU ******\n");
printf("1. Push\n2. Pop\n3. Display\n4. isFull\n5. isEmpty\n6. Exit\n");
printf("Enter your choice: ");
scanf("%d",&choice);
switch(choice){
case 1: printf("Enter the value to be insert: ");
scanf("%d", &value);
push(value);
break;
case 2: pop(); break;
case 3: display(); break;
case 4: isFull(); break;
case 5: isEmpty(); break;
case 6: exit(0);
default: printf("\nWrong selection!!! Please try again!!!\n");
}
}
}
void push(int value)
{
struct Node *newNode;
newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
if(top == NULL)
newNode->next = NULL;
else
newNode->next = top;
top = newNode;
printf("\nInsertion is Success!!!\n");
}
void pop()
{
if(top == NULL)
printf("\nStack is Empty!!!\n");
else{
struct Node *temp = top;
printf("\nDeleted element: %d", temp->data);
top = temp->next;
free(temp);
}
}
void display()
{
if(top == NULL)
printf("\nStack is Empty!!!\n");
else{
struct Node *temp = top;
while(temp->next != NULL){
printf("%d--->",temp->data);
temp = temp -> next;
}
printf("%d--->NULL",temp->data);
}
}
void isFull()
{
if(top<=5)
{
printf("\nStack is Full\n");
}
else
{
printf("\nStack is Not Full\n");
}
}
void isEmpty()
{
if(top==NULL)
{
printf("\nStack is Empty\n");
}
else
{
printf("\nStack is Not Empty\n");
}
}
Output :

Q 5. Write a program to convert an infix arithmetic expression (parenthesize /

unparenthesized) into postfix notation.
Code:
#include<stdio.h>
char stack[20];
int top = -1;
void push(char x)
{
stack[++top] = x;
}
char pop()
{
if(top == -1)
return -1;
else
return stack[top--];
}
int priority(char x)
{
if(x == '(')
return 0;
if(x == '+' || x == '-')
return 1;
if(x == '*' || x == '/')
return 2;
}
void main()
{
char exp[20];
char *e, x;
printf("Enter the expression :: ");
scanf("%s",exp);
e = exp;
while(*e != '\0')
{
if(isalnum(*e))
printf("%c",*e);
else if(*e == '(')
push(*e);
else if(*e == ')')
{
while((x = pop()) != '(')
printf("%c", x);
}
else
{
while(priority(stack[top]) >= priority(*e))
printf("%c",pop());
push(*e);
}
e++;
}
while(top != -1)
{
printf("%c",pop());
}
}
Output :

Q 6. Write a program to evaluate a postfix expression.

Code:
#include<stdio.h>
int stack[20];
int top = -1;
void push(int x)
{
stack[++top] = x;
}
int pop()
{
return stack[top--];
}
int main()
{
char exp[20];
char *e;
int n1,n2,n3,num;
printf("Enter the expression :: ");
scanf("%s",exp);
e = exp;
while(*e != '\0')
{
if(isdigit(*e))
{
num = *e - 48;
push(num);
}
else
{
n1 = pop();
n2 = pop();
switch(*e)
{
case '+':
{
n3 = n1 + n2;
break;
}
case '-':
{
n3 = n2 - n1;
break;
}
case '*':
{
n3 = n1 * n2;
break;
}
case '/':
{
n3 = n2 / n1;
break;
}
 }
push(n3);
}
e++;
}
printf("\nThe result of expression %s = %d\n\n",exp,pop());
return 0;
}
Output:

Q 7 . Create a structure with the following Data members: 1. Integer Array 2. Size of the
Array Search an element in a given list using Binary Search by recursion. And Display
result in a file.
Code:
#include<stdio.h>
struct array{
int arr[100],n;
}array1;
int binary(int,int);
void save(int);
int i,num;
void sort(){
int temp,j;
for(i=0;i<array1.n;i++){
for(j=i+1;j<array1.n;j++){
if(array1.arr[i]>array1.arr[j]){
temp=array1.arr[i];
array1.arr[i]=array1.arr[j];
array1.arr[j]=temp;
}
}
}
}
void main()
{
int loc;
//clrscr();
printf("\n Enter the size of Array[MAX=100]:");
scanf("%d",&array1.n);
printf("\n Enter the Elements:\n");
for(i=0;i<array1.n;i++){
scanf("%d",&array1.arr[i]);
}
printf("\n\t ARRAY SEARCHING");
printf("\n\t--------------------------------");
printf("\n Enter the Number to be searched:");
scanf("%d",&num);
sort();
printf("After Sorting Array... \n");
for(i=0;i<array1.n;i++){
printf("%d \n",array1.arr[i]);
}
loc=binary(0,array1.n);
if(loc!=0){
printf("\nElement Found At :- %d\n",loc);
save(loc);
}
else{
printf("\nElement not found...\n");
save(0);
}
}
int binary(f,l){
 int m;
m = (f+l)/2;
if (l >= f)
{
if (array1.arr[m] == num) {
return m+1;
}
else if (array1.arr[m] < num){
f = m + 1;
binary(f,l);
}
else if (array1.arr[m] > num){
l = m - 1;
binary(f,l);
}
}
else{
return 0;
}
}
void save(num){
FILE *fptr;
fptr = fopen("binary_search_rec.txt","w");
if(fptr == NULL)
{
printf("Error in file!");
exit(0);
}
if(num==0){
fprintf(fptr,"\n Element found not Found");
}
else{
fprintf(fptr,"\n Element found at position: %d",num);
}
fclose(fptr);
}
Output:

Q 8 . Create a “Queue” structure with following Data members: 1. Integer Array 2. Size of
the Array Perform the following operations on Simple queue using user-defined
functions: 1. Insert an element 2. Remove an element 3. Display 4. Isfull 5. Isempty Create
a file which stores all values of Array.
Code:
#include<stdio.h>
struct queue{
int q[100],n;
}struct1;
int choice,start=-1,rear=-1,x,i;
void insert();
void rem();
void display();
void save();
int main()
{
//clrscr();
start=-1;
printf("\n Enter the size of Queue[MAX=100]:");
scanf("%d",&struct1.n);
do
{
printf("\n\t Queue OPERATIONS USING ARRAY");
printf("\n\t--------------------------------");
printf("\n\t 1.Insert\n\t 2.Remove\n\t 3.Display\n\t 4.Save in file\n\t 5.EXIT");
printf("\n Enter the Choice:");
scanf("%d",&choice);
switch(choice)
{
case 1:
{
insert();
break;
}
case 2:
{
rem();
break;
}
case 3:
{
display();
break;
}
case 4:
{
save();
break;
}
case 5:
{
printf("\n\t EXIT POINT ");
break;
}
default:
{
printf ("\n\t Please Enter a Valid Choice(1/2/3/4/5)");
}
}
}
while(choice!=5);
return 0;
}
void insert()
{
if(rear==struct1.n-1)
{
printf("\n\tQueue is full");
}
else
{
printf(" Enter a value to be inserted:");
scanf("%d",&x);
rear++;
struct1.q[rear]=x;
if(start==-1){
start=0;
}
}
}
void rem()
{
if(start==-1)
{
printf("\n\t Queue is empty");
}
else
{
printf("\n\t The remd element is %d",struct1.q[start]);
if(start==rear){
start=-1;
rear=-1;
}
else{
start++;
}
}
}
void display()
{
if(start>=0)
{
printf("\n The elements in queue \n");
for(i=start;i<=rear;i++){
printf("\n%d",struct1.q[i]);
}
printf("\n Press Next Choice");
}
else
{
printf("\n The queue is empty");
}
}
void save()
{
if(start>=0)
{
FILE *fptr;
fptr = fopen("queue.txt","w");
if(fptr == NULL)
{
printf("Error in file!");
exit(0);
}
for(i=start;i<=rear;i++)
{
fprintf(fptr,"\n%d",struct1.q[i]);
}
printf("\n File is saved");
fclose(fptr);
}
else
{
printf("\n The queue is empty");
}
}
Output
 :
Q 9 . Create a “Queue” user-defined structure with the following data members:
1. A Data , 2. A link to the next node Perform the following operations on Simple queue
using user-defined functions:
1. Insert an element
2. Remove an element
3. Display
4. Isfull
5. Isempty
Create a file which stores all values of list.
Code:
#include <stdio.h>
#include <stdlib.h>

// Node structure
typedef struct Node {
int data;
struct Node* next;
} Node;

// Queue structure
typedef struct Queue {
Node* front;
 Node* rear;
} Queue;

// Function to create a new node

Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
printf("Memory allocation failed.\n");
exit(1);
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}

// Function to initialize the queue

Queue* initializeQueue() {
Queue* queue = (Queue*)malloc(sizeof(Queue));
if (queue == NULL) {
printf("Memory allocation failed.\n");
exit(1);
}
queue->front = NULL;
queue->rear = NULL;
return queue;
}

// Function to check if the queue is empty

int isEmpty(Queue* queue) {
return (queue->front == NULL);
}
// Function to insert an element into the queue
void enqueue(Queue* queue, int data) {
Node* newNode = createNode(data);
if (isEmpty(queue)) {
queue->front = newNode;
queue->rear = newNode;
} else {
queue->rear->next = newNode;
queue->rear = newNode;
}
}

// Function to remove an element from the queue

int dequeue(Queue* queue) {
if (isEmpty(queue)) {
printf("Queue is empty.\n");
exit(1);
}
Node* temp = queue->front;
int data = temp->data;
queue->front = queue->front->next;
free(temp);
return data;
}

// Function to display the queue

void display(Queue* queue) {
if (isEmpty(queue)) {
printf("Queue is empty.\n");
return;
}
Node* temp = queue->front;
 while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}

// Function to store queue values in a file

void storeToFile(Queue* queue, const char* filename) {
FILE* file = fopen(filename, "w");
if (file == NULL) {
printf("Error opening file.\n");
exit(1);
}
Node* temp = queue->front;
while (temp != NULL) {
fprintf(file, "%d\n", temp->data);
temp = temp->next;
}
fclose(file);
}

int main() {
Queue* queue = initializeQueue();
int choice, element;

do {
printf("\n1. Insert an element\n");
printf("2. Remove an element\n");
printf("3. Display\n");
printf("4. Store values in a file\n");
printf("5. Exit\n");
 printf("Enter your choice: ");
scanf("%d", &choice);

switch(choice) {
case 1:
printf("Enter element to insert: ");
scanf("%d", &element);
enqueue(queue, element);
break;
case 2:
if (!isEmpty(queue))
printf("Removed element: %d\n", dequeue(queue));
break;
case 3:
printf("Queue: ");
display(queue);
break;
case 4:
storeToFile(queue, "queue_values.txt");
printf("Queue values stored in 'queue_values.txt'\n");
break;
case 5:
printf("Exiting program.\n");
break;
default:
printf("Invalid choice. Please enter a valid option.\n");
}
} while (choice != 5);

return 0;
}
Output :
Q 10. Create a “Circular Queue” structure with following Data members:
1. Integer Array
2. Size of the Array Perform the following operations on Circular queue using user-
defined functions:
1. Insert an element
2. Remove an element
3. Display
4. Isfull
5. Isempty
Create a file which stores all values of Array.
Code:
#include <stdio.h>
#include <stdlib.h>

// Circular Queue structure

typedef struct CircularQueue {
int* array;
int front, rear, size;
} CircularQueue;

// Function to initialize the circular queue

CircularQueue* initializeCircularQueue(int size) {
CircularQueue* cq = (CircularQueue*)malloc(sizeof(CircularQueue));
if (cq == NULL) {
printf("Memory allocation failed.\n");
exit(1);
}
cq->array = (int*)malloc(size * sizeof(int));
if (cq->array == NULL) {
printf("Memory allocation failed.\n");
exit(1);
}
cq->front = cq->rear = -1;
cq->size = size;
return cq;
}

// Function to check if the circular queue is full

int isFull(CircularQueue* cq) {
return (cq->front == (cq->rear + 1) % cq->size);
}

// Function to check if the circular queue is empty

int isEmpty(CircularQueue* cq) {
return (cq->front == -1);
}

// Function to insert an element into the circular queue

void enqueue(CircularQueue* cq, int element) {
if (isFull(cq)) {
printf("Queue is full. Cannot enqueue.\n");
return;
}
 if (isEmpty(cq))
cq->front = 0;
cq->rear = (cq->rear + 1) % cq->size;
cq->array[cq->rear] = element;
}

// Function to remove an element from the circular queue

int dequeue(CircularQueue* cq) {
if (isEmpty(cq)) {
printf("Queue is empty. Cannot dequeue.\n");
exit(1);
}
int element = cq->array[cq->front];
if (cq->front == cq->rear)
cq->front = cq->rear = -1;
else
cq->front = (cq->front + 1) % cq->size;
return element;
}

// Function to display the circular queue

void display(CircularQueue* cq) {
if (isEmpty(cq)) {
printf("Queue is empty.\n");
return;
}
int i = cq->front;
do {
printf("%d ", cq->array[i]);
i = (i + 1) % cq->size;
} while (i != (cq->rear + 1) % cq->size);
printf("\n");
}

// Function to store circular queue values in a file

void storeToFile(CircularQueue* cq, const char* filename) {
FILE* file = fopen(filename, "w");
if (file == NULL) {
printf("Error opening file.\n");
exit(1);
}
int i = cq->front;
do {
fprintf(file, "%d\n", cq->array[i]);
i = (i + 1) % cq->size;
} while (i != (cq->rear + 1) % cq->size);
fclose(file);
}

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

printf("Enter size of circular queue: ");

scanf("%d", &size);
CircularQueue* cq = initializeCircularQueue(size);

do {
printf("\n1. Insert an element\n");
printf("2. Remove an element\n");
printf("3. Display\n");
printf("4. Store values in a file\n");
printf("5. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
 switch(choice) {
case 1:
printf("Enter element to insert: ");
scanf("%d", &element);
enqueue(cq, element);
break;
case 2:
if (!isEmpty(cq))
printf("Removed element: %d\n", dequeue(cq));
break;
case 3:
printf("Queue: ");
display(cq);
break;
case 4:
storeToFile(cq, "circular_queue_values.txt");
printf("Queue values stored in 'circular_queue_values.txt'\n");
break;
case 5:
printf("Exiting program.\n");
break;
default:
printf("Invalid choice. Please enter a valid option.\n");
}
} while (choice != 5);

free(cq->array);
free(cq);

return 0;
}
Output :

Q 11. Create a “Circular Queue” user-defined structure with the following data members:
1. A Data 2. A link to the next node Perform the following operations on Circular queue
using user-defined functions:
1. Insert an element
2. Remove an element
3. Display
4. Isfull
5. Isempty
Create a file which stores all values of list.
Code:
#include <stdio.h>
#include <stdlib.h>

// Node structure
typedef struct Node {
int data;
struct Node* next;
} Node;

// Circular Queue structure

typedef struct CircularQueue {
 cq->rear->next = temp->next;
free(temp);
}
cq->size--;
return data;
}

// Function to display the circular queue

void display(CircularQueue* cq) {
if (isEmpty(cq)) {
printf("Queue is empty.\n");
return;
}
Node* current = cq->rear->next;
do {
printf("%d ", current->data);
current = current->next;
} while (current != cq->rear->next);
printf("\n");
}

// Function to store circular queue values in a file

void storeToFile(CircularQueue* cq, const char* filename) {
FILE* file = fopen(filename, "w");
if (file == NULL) {
printf("Error opening file.\n");
exit(1);
}
if (!isEmpty(cq)) {
Node* current = cq->rear->next;
do {
fprintf(file, "%d\n", current->data);
 current = current->next;
} while (current != cq->rear->next);
}
fclose(file);
}

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

printf("Enter capacity of circular queue: ");

scanf("%d", &capacity);
CircularQueue* cq = initializeCircularQueue(capacity);

do {
printf("\n1. Insert an element\n");
printf("2. Remove an element\n");
printf("3. Display\n");
printf("4. Store values in a file\n");
printf("5. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);

switch(choice) {
case 1:
if (!isFull(cq)) {
printf("Enter element to insert: ");
scanf("%d", &element);
enqueue(cq, element);
} else {
printf("Queue is full. Cannot enqueue.\n");
}
break;
 case 2:
if (!isEmpty(cq))
printf("Removed element: %d\n", dequeue(cq));
else
printf("Queue is empty. Cannot dequeue.\n");
break;
case 3:
printf("Queue: ");
display(cq);
break;
case 4:
storeToFile(cq, "circular_queue_values.txt");
printf("Queue values stored in 'circular_queue_values.txt'\n");
break;
case 5:
printf("Exiting program.\n");
break;
default:
printf("Invalid choice. Please enter a valid option.\n");
}
} while (choice != 5);

// Free memory
Node* current = cq->rear;
if (current != NULL) {
Node* temp = current->next;
while (temp != current) {
Node* toDelete = temp;
temp = temp->next;
free(toDelete);
}
free(current);
 }
free(cq);

return 0;
}
Output :

Q 12. Create a user-defined “Linked List” structure with the following data members:
1. A Co-efficient
2. An Exponent
3. A link to the next node Perform the following operations on Singly list using user-
defined functions: 1. Create 2. Display 3. Addition 4. Multiplication Create a file which
stores all values of list.
Code:
#include <stdio.h>
#include <stdlib.h>

// Node structure
typedef struct Node {
int coefficient;
int exponent;
struct Node* next;
} Node;

// Function to create a new node

Node* createNode(int coefficient, int exponent) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
 printf("Memory allocation failed.\n");
exit(1);
}
newNode->coefficient = coefficient;
newNode->exponent = exponent;
newNode->next = NULL;
return newNode;
}

// Function to insert a term into the polynomial (linked list)

void insertTerm(Node** head, int coefficient, int exponent) {
Node* newNode = createNode(coefficient, exponent);
if (*head == NULL) {
*head = newNode;
} else {
Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}
}

// Function to display the polynomial (linked list)

void display(Node* head) {
if (head == NULL) {
printf("Polynomial is empty.\n");
return;
}
while (head != NULL) {
printf("(%dx^%d) ", head->coefficient, head->exponent);
if (head->next != NULL) {
 printf("+ ");
}
head = head->next;
}
printf("\n");
}

// Function to add two polynomials

Node* addPolynomials(Node* poly1, Node* poly2) {
Node* result = NULL;
Node* current1 = poly1;
Node* current2 = poly2;

while (current1 != NULL && current2 != NULL) {

if (current1->exponent > current2->exponent) {
insertTerm(&result, current1->coefficient, current1->exponent);
current1 = current1->next;
} else if (current1->exponent < current2->exponent) {
insertTerm(&result, current2->coefficient, current2->exponent);
current2 = current2->next;
} else {
int sum_coefficient = current1->coefficient + current2->coefficient;
insertTerm(&result, sum_coefficient, current1->exponent);
current1 = current1->next;
current2 = current2->next;
}
}

// If one polynomial has more terms, add remaining terms

while (current1 != NULL) {
insertTerm(&result, current1->coefficient, current1->exponent);
current1 = current1->next;
 }
while (current2 != NULL) {
insertTerm(&result, current2->coefficient, current2->exponent);
current2 = current2->next;
}

return result;
}

// Function to multiply two polynomials

Node* multiplyPolynomials(Node* poly1, Node* poly2) {
Node* result = NULL;
Node* current1 = poly1;

while (current1 != NULL) {

Node* current2 = poly2;
while (current2 != NULL) {
int coeff = current1->coefficient * current2->coefficient;
int exp = current1->exponent + current2->exponent;
insertTerm(&result, coeff, exp);
current2 = current2->next;
}
current1 = current1->next;
}

return result;
}

// Function to store polynomial values in a file

void storeToFile(Node* head, const char* filename) {
FILE* file = fopen(filename, "w");
if (file == NULL) {
 printf("Error opening file.\n");
exit(1);
}
while (head != NULL) {
fprintf(file, "%dx^%d\n", head->coefficient, head->exponent);
head = head->next;
}
fclose(file);
}

// Function to free memory allocated for the linked list

void freeList(Node* head) {
Node* temp;
while (head != NULL) {
temp = head;
head = head->next;
free(temp);
}
}

int main() {
Node* poly1 = NULL;
Node* poly2 = NULL;
Node* result = NULL;
int coefficient, exponent;
int num_terms1, num_terms2;

// Input for the first polynomial

printf("Enter the number of terms for the first polynomial: ");
scanf("%d", &num_terms1);
printf("Enter the terms for the first polynomial (coefficient exponent):\n");
for (int i = 0; i < num_terms1; i++) {
 scanf("%d %d", &coefficient, &exponent);
insertTerm(&poly1, coefficient, exponent);
}

// Input for the second polynomial

printf("Enter the number of terms for the second polynomial: ");
scanf("%d", &num_terms2);
printf("Enter the terms for the second polynomial (coefficient exponent):\n");
for (int i = 0; i < num_terms2; i++) {
scanf("%d %d", &coefficient, &exponent);
insertTerm(&poly2, coefficient, exponent);
}

printf("First polynomial: ");

display(poly1);
printf("Second polynomial: ");
display(poly2);

// Addition
result = addPolynomials(poly1, poly2);
printf("Addition result: ");
display(result);

// Multiplication
result = multiplyPolynomials(poly1, poly2);
printf("Multiplication result: ");
display(result);

// Storing polynomials in file

storeToFile(poly1, "polynomial1.txt");
storeToFile(poly2, "polynomial2.txt");
 // Free memory
freeList(poly1);
freeList(poly2);
freeList(result);

return 0;
}
Output :

Q13. Create a user-defined structure with the following data members: 1. A Data 2. A link
to the next node Perform the following operations on list using user-defined functions:
1. Create a list
2. Traverse the whole list
3. Delete first node
4. Delete last node
5. Delete a node before specified data
6. Insert at first position
7. Insert at last position
8. Insert a node before specified data
9. Insert a node at specified position
10. Count
11. Copy
12. Merge two list
13. Reverse
14. Search
15. Sort Create a file which stores all values of list.
Code:
#include <stdio.h>
#include <stdlib.h>
// Node structure
typedef struct Node {
int data;
struct Node* next;
} Node;

// Function to create a new node

Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
printf("Memory allocation failed.\n");
exit(1);
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}

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

void insertAtFirst(Node** head, int data) {
Node* newNode = createNode(data);
newNode->next = *head;
*head = newNode;
}

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

void insertAtLast(Node** head, int data) {
Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
return;
// Function to delete the entire list
void deleteList(Node** head) {
Node* current = *head;
Node* next;
while (current != NULL) {
next = current->next;
free(current);
current = next;
}
*head = NULL;
}

// Function to store list values in a file

void storeListToFile(Node* head, const char* filename) {
FILE* file = fopen(filename, "w");
if (file == NULL) {
printf("Error opening file.\n");
exit(1);
}
while (head != NULL) {
fprintf(file, "%d\n", head->data);
head = head->next;
}
fclose(file);
}

int main() {
Node* head = NULL;

// Test operations
insertAtLast(&head, 1);
insertAtLast(&head, 2);
insertAtLast(&head, 3);

printf("Original list: ");

traverse(head);

// Perform operations
printf("\nAfter operations:\n");

// Delete first node

deleteFirst(&head);
printf("After deleting first node: ");
traverse(head);

// Delete last node

deleteLast(&head);
printf("After deleting last node: ");
traverse(head);

// Insert before specified data

insertBeforeData(&head, 4, 2);
printf("After inserting 4 before 2: ");
traverse(head);

// Insert at first position

insertAtFirst(&head, 5);
printf("After inserting 5 at first position: ");
traverse(head);

// Insert at last position

insertAtLast(&head, 6);
printf("After inserting 6 at last position: ");
traverse(head);
// Insert a node at specified position
insertAtPosition(&head, 7, 3);
printf("After inserting 7 at position 3: ");
traverse(head);

// Count nodes
printf("Number of nodes: %d\n", countNodes(head));

// Copy list
Node* copiedList = copyList(head);
printf("Copied list: ");
traverse(copiedList);

// Merge lists
Node* list1 = NULL;
insertAtLast(&list1, 2);
insertAtLast(&list1, 4);
insertAtLast(&list1, 6);
Node* list2 = NULL;
insertAtLast(&list2, 1);
insertAtLast(&list2, 3);
insertAtLast(&list2, 5);
Node* mergedList = mergeLists(list1, list2);
printf("Merged list: ");
traverse(mergedList);

// Reverse list
head = reverseList(head);
printf("Reversed list: ");
traverse(head);
 // Search value
int target = 4;
int position = search(head, target);
if (position != -1) {
printf("%d found at position %d.\n", target, position);
} else {
printf("%d not found in the list.\n", target);
}

// Sort list
head = sortList(head);
printf("Sorted list: ");
traverse(head);

// Store list values in a file

storeListToFile(head, "list_values.txt");
// Delete entire list
deleteList(&head);
return 0;
}
Output :

Q14 . Create a user-defined structure with the following data members: 1. A Data 2. A link
to the next node Perform the following operations on Circular list using user-defined
functions:
1. Create a list
2. Traverse the whole list\
3. Delete first node
4. Delete last node
5. Delete a node before specified data
6. Insert at first position
7. Insert at last position
8. Insert a node before specified data
9. Insert a node at specified position
10. Count
11. Copy
12. Merge two list
13. Reverse
14. Search
15. Sort Create a file which stores all values of list.
Code:
#include <stdio.h>
#include <stdlib.h>

// Node structure
typedef struct Node {
int data;
struct Node* next;
} Node;

// Function to create a new node

Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
printf("Memory allocation failed.\n");
exit(1);
}
newNode->data = data;
newNode->next = NULL;
 return newNode;
}

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

void insertAtFirst(Node** head, int data) {
Node* newNode = createNode(data);
if (*head == NULL) {
newNode->next = newNode; // For circular list, point to self if empty
*head = newNode;
} else {
Node* temp = *head;
while (temp->next != *head) {
temp = temp->next;
}
newNode->next = *head;
temp->next = newNode;
*head = newNode;
}
}

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

void insertAtLast(Node** head, int data) {
Node* newNode = createNode(data);
if (*head == NULL) {
newNode->next = newNode; // For circular list, point to self if empty
*head = newNode;
} else {
Node* temp = *head;
while (temp->next != *head) {
temp = temp->next;
}
temp->next = newNode;
 newNode->next = *head;
}
}

// Function to insert a node before a specified data value

void insertBeforeData(Node** head, int data, int target) {
if (*head == NULL) {
printf("List is empty. Cannot insert before data.\n");
return;
}
if ((*head)->data == target) {
insertAtFirst(head, data);
return;
}
Node* current = *head;
while (current->next != *head && current->next->data != target) {
current = current->next;
}
if (current->next == *head) {
printf("Data not found in the list.\n");
return;
}
Node* newNode = createNode(data);
newNode->next = current->next;
current->next = newNode;
}

// Function to delete the first node

void deleteFirst(Node** head) {
if (*head == NULL) {
printf("List is empty. Cannot delete first node.\n");
return;
 }
Node* temp = *head;
if ((*head)->next == *head) {
free(temp);
*head = NULL;
} else {
Node* current = *head;
while (current->next != *head) {
current = current->next;
}
*head = (*head)->next;
current->next = *head;
free(temp);
}
}

// Function to delete the last node

void deleteLast(Node** head) {
if (*head == NULL) {
printf("List is empty. Cannot delete last node.\n");
return;
}
if ((*head)->next == *head) {
free(*head);
*head = NULL;
return;
}
Node* temp = *head;
Node* prev = NULL;
while (temp->next != *head) {
prev = temp;
temp = temp->next;
 }
prev->next = *head;
free(temp);
}

// Function to delete a node before specified data

void deleteBeforeData(Node** head, int target) {
if (*head == NULL || (*head)->next == *head) {
printf("List has less than two nodes. Cannot delete node before data.\n");
return;
}
if ((*head)->data == target) {
printf("Cannot delete node before first node.\n");
return;
}
if ((*head)->next->data == target) {
deleteFirst(head);
return;
}
Node* current = *head;
while (current->next->next != *head && current->next->next->data != target) {
current = current->next;
}
if (current->next->next == *head) {
printf("Data not found in the list.\n");
return;
}
Node* temp = current->next;
current->next = temp->next;
free(temp);
}
// Function to insert a node at a specified position
void insertAtPosition(Node** head, int data, int position) {
if (position < 1) {
printf("Invalid position.\n");
return;
}
if (position == 1) {
insertAtFirst(head, data);
return;
}
Node* newNode = createNode(data);
Node* current = *head;
for (int i = 1; i < position - 1 && current->next != *head; i++) {
current = current->next;
}
if (current->next == *head) {
printf("Invalid position.\n");
return;
}
newNode->next = current->next;
current->next = newNode;
}

// Function to traverse and display the list

void traverse(Node* head) {
if (head == NULL) {
printf("List is empty.\n");
return;
}
Node* temp = head;
do {
printf("%d ", temp->data);
 temp = temp->next;
} while (temp != head);
printf("\n");
}

// Function to count the number of nodes in the list

int countNodes(Node* head) {
if (head == NULL) {
return 0;
}
int count = 0;
Node* temp = head;
do {
count++;
temp = temp->next;
} while (temp != head);
return count;
}

// Function to copy a list

Node* copyList(Node* head) {
Node* newHead = NULL;
if (head == NULL) {
return NULL;
}
Node* temp = head;
do {
insertAtLast(&newHead, temp->data);
temp = temp->next;
} while (temp != head);
return newHead;
}
// Function to merge two lists
Node* mergeLists(Node* head1, Node* head2) {
if (head1 == NULL) {
return head2;
}
if (head2 == NULL) {
return head1;
}
Node* temp1 = head1;
while (temp1->next != head1) {
temp1 = temp1->next;
}
Node* temp2 = head2;
while (temp2->next != head2) {
temp2 = temp2->next;
}
temp1->next = head2;
temp2->next = head1;
return head1;
}

// Function to reverse the list

Node* reverseList(Node* head) {
if (head == NULL) {
return NULL;
}
Node *prev = NULL, *current = head, *next;
do {
next = current->next;
current->next = prev;
prev = current;
 current = next;
} while (current != head);
head->next = prev;
return prev;
}

// Function to search for a value in the list

int search(Node* head, int target) {
if (head == NULL) {
return -1;
}
int position = 1;
Node* temp = head;
do {
if (temp->data == target) {
return position;
}
temp = temp->next;
position++;
} while (temp != head);
return -1;
}

// Function to sort the list

Node* sortList(Node* head) {
if (head == NULL || head->next == head) {
return head;
}
Node *current, *index;
int temp;
current = head;
do {
 index = current->next;
while (index != head) {
if (current->data > index->data) {
temp = current->data;
current->data = index->data;
index->data = temp;
}
index = index->next;
}
current = current->next;
} while (current->next != head);
return head;
}

// Function to delete the entire list

void deleteList(Node** head) {
if (*head == NULL) {
printf("List is already empty.\n");
return;
}
Node* current = *head;
Node* temp;
do {
temp = current;
current = current->next;
free(temp);
} while (current != *head);
*head = NULL;
}

// Function to store list values in a file

void storeListToFile(Node* head, const char* filename) {
 FILE* file = fopen(filename, "w");
if (file == NULL) {
printf("Error opening file.\n");
exit(1);
}
Node* temp = head;
do {
fprintf(file, "%d\n", temp->data);
temp = temp->next;
} while (temp != head);
fclose(file);
}

int main() {
Node* head = NULL;

// Test operations
insertAtLast(&head, 1);
insertAtLast(&head, 2);
insertAtLast(&head, 3);

printf("Original circular list: ");

traverse(head);

// Perform operations
printf("\nAfter operations:\n");

// Delete first node

deleteFirst(&head);
printf("After deleting first node: ");
traverse(head);
// Delete last node
deleteLast(&head);
printf("After deleting last node: ");
traverse(head);

// Insert before specified data

insertBeforeData(&head, 4, 2);
printf("After inserting 4 before 2: ");
traverse(head);

// Insert at first position

insertAtFirst(&head, 5);
printf("After inserting 5 at first position: ");
traverse(head);

// Insert at last position

insertAtLast(&head, 6);
printf("After inserting 6 at last position: ");
traverse(head);

// Insert a node at specified position

insertAtPosition(&head, 7, 3);
printf("After inserting 7 at position 3: ");
traverse(head);

// Count nodes
printf("Number of nodes: %d\n", countNodes(head));

// Copy list
Node* copiedList = copyList(head);
printf("Copied circular list: ");
traverse(copiedList);
// Merge lists
Node* list1 = NULL;
insertAtLast(&list1, 2);
insertAtLast(&list1, 4);
insertAtLast(&list1, 6);
Node* list2 = NULL;
insertAtLast(&list2, 1);
insertAtLast(&list2, 3);
insertAtLast(&list2, 5);
Node* mergedList = mergeLists(list1, list2);
printf("Merged circular list: ");
traverse(mergedList);

// Reverse list
head = reverseList(head);
printf("Reversed circular list: ");
traverse(head);

// Search value
int target = 4;
int position = search(head, target);
if (position != -1) {
printf("%d found at position %d.\n", target, position);
} else {
printf("%d not found in the list.\n", target);
}
// Sort list
head = sortList(head);
printf("Sorted circular list: ");
traverse(head);
// Store list values in a file
 storeListToFile(head, "circular_list_values.txt");
// Delete entire list
deleteList(&head);
return 0;
}
Output:

Q15. Create a user-defined structure with the following data members: 1. A Data 2. A link
to the next node 3. A link to the previous node Perform the following operations on the
doubly-linked list using user-defined functions: 1. Create a list 2. Traverse the whole list\
3. Delete first node 4. Delete last node 5. Delete a node before specified data 6. Insert at
first position 7. Insert at last position 8. Insert a node before specified data 9. Insert a
node at specified position 10. Count 11. Copy 12. Merge two list 13. Reverse 14. Search
15. Sort Create a file which stores all values of list.
Code:
#include <stdio.h>
#include <stdlib.h>

// Node structure
typedef struct Node {
int data;
struct Node* next;
struct Node* prev;
} Node;

// Function to create a new node

Node* createNode(int data) {
 Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
printf("Memory allocation failed.\n");
exit(1);
}
newNode->data = data;
newNode->next = NULL;
newNode->prev = NULL;
return newNode;
}

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

void insertAtFirst(Node** head, int data) {
Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
} else {
newNode->next = *head;
(*head)->prev = newNode;
*head = newNode;
}
}

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

void insertAtLast(Node** head, int data) {
Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
} else {
Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
printf("Original doubly linked list: ");
traverse(head);

// Perform operations
printf("\nAfter operations:\n");

// Delete first node

deleteFirst(&head);
printf("After deleting first node: ");
traverse(head);

// Delete last node

deleteLast(&head);
printf("After deleting last node: ");
traverse(head);

// Insert before specified data

insertBeforeData(&head, 4, 2);
printf("After inserting 4 before 2: ");
traverse(head);

// Insert at first position

insertAtFirst(&head, 5);
printf("After inserting 5 at first position: ");
traverse(head);
// Insert at last position
insertAtLast(&head, 6);
printf("After inserting 6 at last position: ");
traverse(head);
// Insert a node at specified position
insertAtPosition(&head, 7, 3);
printf("After inserting 7 at position 3: ");
traverse(head);
// Count nodes
printf("Number of nodes: %d\n", countNodes(head));
// Copy list
Node* copiedList = copyList(head);
printf("Copied doubly linked list: ");
traverse(copiedList);
// Merge lists
Node* list1 = NULL;
insertAtLast(&list1, 2);
insertAtLast(&list1, 4);
insertAtLast(&list1, 6);
Node* list2 = NULL;
insertAtLast(&list2, 1);
insertAtLast(&list2, 3);
insertAtLast(&list2, 5);
Node* mergedList = mergeLists(list1, list2);
printf("Merged doubly linked list: ");
traverse(mergedList);
// Reverse list
head = reverseList(head);
printf("Reversed doubly linked list: ");
traverse(head);
int target = 4;
int position = search(head, target);
if (position != -1) {
printf("%d found at position %d.\n", target, position);
} else {
printf("%d not found in the list.\n", target);
}
head = sortList(head);
 printf("Sorted doubly linked list: ");
traverse(head);
storeListToFile(head, "doubly_linked_list_values.txt");
deleteList(&head);
return 0;
}
Output:

Q16. Create a user-defined structure with the following data members: 1. A Data 2. A link
to the next node 3. A link to the previous node Perform the following operations on
doubly-linked Circular list using user defined functions: 1. Create a list 2. Traverse the
whole list\ 3. Delete first node 4. Delete last node 5. Delete a node before specified data 6.
Insert at first position 7. Insert at last position 8. Insert a node before specified data 9.
Insert a node at specified position 10. Count 11. Copy 12. Merge two list 13. Reverse 14.
Search 15. Sort Create a file which stores all values of list.
Code:
#include <stdio.h>
#include <stdlib.h>

// Node structure
typedef struct Node {
int data;
struct Node* next;
struct Node* prev;
} Node;

// Function to create a new node

Node* createNode(int data) {
 Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
printf("Memory allocation failed.\n");
exit(1);
}
newNode->data = data;
newNode->next = NULL;
newNode->prev = NULL;
return newNode;
}

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

void insertAtFirst(Node** head, int data) {
Node* newNode = createNode(data);
if (*head == NULL) {
newNode->next = newNode;
newNode->prev = newNode;
*head = newNode;
} else {
newNode->next = *head;
newNode->prev = (*head)->prev;
(*head)->prev->next = newNode;
(*head)->prev = newNode;
*head = newNode;
}
}

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

void insertAtLast(Node** head, int data) {
Node* newNode = createNode(data);
if (*head == NULL) {
newNode->next = newNode;
 newNode->prev = newNode;
*head = newNode;
} else {
newNode->next = *head;
newNode->prev = (*head)->prev;
(*head)->prev->next = newNode;
(*head)->prev = newNode;
}
}

// Function to insert a node before a specified data value

void insertBeforeData(Node** head, int data, int target) {
if (*head == NULL) {
printf("List is empty. Cannot insert before data.\n");
return;
}
if ((*head)->data == target) {
insertAtFirst(head, data);
return;
}
Node* current = *head;
while (current->data != target && current->next != *head) {
current = current->next;
}
if (current->data != target) {
printf("Data not found in the list.\n");
return;
}
Node* newNode = createNode(data);
newNode->next = current;
newNode->prev = current->prev;
current->prev->next = newNode;
 current->prev = newNode;
}

// Function to delete the first node

void deleteFirst(Node** head) {
if (*head == NULL) {
printf("List is empty. Cannot delete first node.\n");
return;
}
if ((*head)->next == *head) {
free(*head);
*head = NULL;
} else {
Node* temp = *head;
(*head)->prev->next = (*head)->next;
(*head)->next->prev = (*head)->prev;
*head = (*head)->next;
free(temp);
}
}

// Function to delete the last node

void deleteLast(Node** head) {
if (*head == NULL) {
printf("List is empty. Cannot delete last node.\n");
return;
}
if ((*head)->next == *head) {
free(*head);
*head = NULL;
} else {
Node* temp = (*head)->prev;
 temp->prev->next = *head;
(*head)->prev = temp->prev;
free(temp);
}
}

// Function to delete a node before specified data

void deleteBeforeData(Node** head, int target) {
if (*head == NULL || (*head)->next == *head) {
printf("List has less than two nodes. Cannot delete node before data.\n");
return;
}
if ((*head)->data == target) {
printf("Cannot delete node before first node.\n");
return;
}
if ((*head)->next->data == target) {
deleteLast(head);
return;
}
Node* current = *head;
while (current->next->data != target && current->next != *head) {
current = current->next;
}
if (current->next == *head) {
printf("Data not found in the list.\n");
return;
}
Node* temp = current->prev;
temp->prev->next = current;
current->prev = temp->prev;
free(temp);
}

// Function to insert a node at a specified position

void insertAtPosition(Node** head, int data, int position) {
if (position < 1) {
printf("Invalid position.\n");
return;
}
if (position == 1) {
insertAtFirst(head, data);
return;
}
Node* newNode = createNode(data);
Node* current = *head;
for (int i = 1; i < position - 1 && current->next != *head; i++) {
current = current->next;
}
if (current->next == *head) {
printf("Invalid position.\n");
return;
}
newNode->next = current->next;
newNode->prev = current;
current->next->prev = newNode;
current->next = newNode;
}

// Function to traverse and display the list

void traverse(Node* head) {
if (head == NULL) {
printf("List is empty.\n");
return;
 }
Node* temp = head;
do {
printf("%d ", temp->data);
temp = temp->next;
} while (temp != head);
printf("\n");
}

// Function to count the number of nodes in the list

int countNodes(Node* head) {
if (head == NULL) {
return 0;
}
int count = 0;
Node* temp = head;
do {
count++;
temp = temp->next;
} while (temp != head);
return count;
}

// Function to copy a list

Node* copyList(Node* head) {
if (head == NULL) {
return NULL;
}
Node* newHead = NULL;
Node* temp = head;
do {
insertAtLast(&newHead, temp->data);
 temp = temp->next;
} while (temp != head);
return newHead;
}

// Function to merge two lists

Node* mergeLists(Node* head1, Node* head2) {
if (head1 == NULL) {
return head2;
}
if (head2 == NULL) {
return head1;
}
Node* temp1 = head1->prev;
Node* temp2 = head2->prev;
head1->prev = temp2;
temp1->next = head2;
head2->prev = temp1;
temp2->next = head1;
return head1;
}

// Function to reverse the list

Node* reverseList(Node* head) {
if (head == NULL) {
return NULL;
}
Node *current = head, *temp = NULL;
do {
temp = current->prev;
current->prev = current->next;
current->next = temp;
 current = current->prev;
} while (current != head);
return temp->prev;
}

// Function to search for a value in the list

int search(Node* head, int target) {
if (head == NULL) {
return -1;
}
int position = 1;
Node* temp = head;
do {
if (temp->data == target) {
return position;
}
temp = temp->next;
position++;
} while (temp != head);
return -1;
}

// Function to sort the list

Node* sortList(Node* head) {
if (head == NULL || head->next == head) {
return head;
}
Node *current, *index;
int temp;
current = head;
do {
index = current->next;
 while (index != head) {
if (current->data > index->data) {
temp = current->data;
current->data = index->data;
index->data = temp;
}
index = index->next;
}
current = current->next;
} while (current != head);
return head;
}

// Function to delete the entire list

void deleteList(Node** head) {
if (*head == NULL) {
printf("List is already empty.\n");
return;
}
Node* temp = (*head)->next;
while (temp != *head) {
temp = temp->next;
free(temp->prev);
}
free(*head);
*head = NULL;
}

// Function to store list values in a file

void storeListToFile(Node* head, const char* filename) {
FILE* file = fopen(filename, "w");
if (file == NULL) {
 printf("Error opening file.\n");
exit(1);
}
Node* temp = head;
do {
fprintf(file, "%d\n", temp->data);
temp = temp->next;
} while (temp != head);
fclose(file);
}

int main() {
Node* head = NULL;

// Test operations
insertAtLast(&head, 1);
insertAtLast(&head, 2);
insertAtLast(&head, 3);

printf("Original doubly linked circular list: ");

traverse(head);

// Perform operations
printf("\nAfter operations:\n");

// Delete first node

deleteFirst(&head);
printf("After deleting first node: ");
traverse(head);

// Delete last node

deleteLast(&head);
printf("After deleting last node: ");
traverse(head);

// Insert before specified data

insertBeforeData(&head, 4, 2);
printf("After inserting 4 before 2: ");
traverse(head);

// Insert at first position

insertAtFirst(&head, 5);
printf("After inserting 5 at first position: ");
traverse(head);

// Insert at last position

insertAtLast(&head, 6);
printf("After inserting 6 at last position: ");
traverse(head);

// Insert a node at specified position

insertAtPosition(&head, 7, 3);
printf("After inserting 7 at position 3: ");
traverse(head);

// Count nodes
printf("Number of nodes: %d\n", countNodes(head));

// Copy list
Node* copiedList = copyList(head);
printf("Copied doubly linked circular list: ");
traverse(copiedList);

// Merge lists
Node* list1 = NULL;
insertAtLast(&list1, 2);
insertAtLast(&list1, 4);
insertAtLast(&list1, 6);
Node* list2 = NULL;
insertAtLast(&list2, 1);
insertAtLast(&list2, 3);
insertAtLast(&list2, 5);
Node* mergedList = mergeLists(list1, list2);
printf("Merged doubly linked circular list: ");
traverse(mergedList);

// Reverse list
head = reverseList(head);
printf("Reversed doubly linked circular list: ");
traverse(head);
// Search value
int target = 4;
int position = search(head, target);
if (position != -1) {
printf("%d found at position %d.\n", target, position);
} else {
printf("%d not found in the list.\n", target);
}
// Sort list
head = sortList(head);
printf("Sorted doubly linked circular list: ");
traverse(head);
// Store list values in a file
storeListToFile(head, "doubly_linked_circular_list_values.txt");
// Delete entire list
deleteList(&head);
 return 0;
}
Output:

Q17. Write a program to represent an undirected graph using the adjacency matrix to
implement the graph and perform following operations, with menu driven options for
following tasks: 1. Create graph 2. Insert an edge 3. Print Adjacency Matrix 4. List all
vertices that are adjacent to a specified vertex. 5. Print out vertices using depth first
search 6. Print out vertices using breadth first search 7. Exit program
Code:

#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100
int adjacencyMatrix[MAX_VERTICES][MAX_VERTICES];
int numVertices = 0;
// Function to create a graph
void createGraph() {
printf("Enter the number of vertices in the graph: ");
scanf("%d", &numVertices);
if (numVertices <= 0 || numVertices > MAX_VERTICES) {
printf("Invalid number of vertices.\n");
return;
}
printf("Graph with %d vertices has been created.\n", numVertices);
// Initialize adjacency matrix with zeros
for (int i = 0; i < numVertices; i++) {
for (int j = 0; j < numVertices; j++) {
 adjacencyMatrix[i][j] = 0;
}
}
}
// Function to insert an edge between two vertices
void insertEdge() {
int vertex1, vertex2;
printf("Enter the vertices to connect (separated by space): ");
scanf("%d %d", &vertex1, &vertex2);
if (vertex1 < 0 || vertex1 >= numVertices || vertex2 < 0 || vertex2 >= numVertices) {
printf("Invalid vertices.\n");
return;
}
adjacencyMatrix[vertex1][vertex2] = 1;
adjacencyMatrix[vertex2][vertex1] = 1;
printf("Edge between vertices %d and %d has been inserted.\n", vertex1, vertex2);
}
// Function to print the adjacency matrix
void printAdjacencyMatrix() {
printf("Adjacency Matrix:\n");
for (int i = 0; i < numVertices; i++) {
for (int j = 0; j < numVertices; j++) {
printf("%d ", adjacencyMatrix[i][j]);
}
printf("\n");
}
}
// Function to list all vertices adjacent to a specified vertex
void listAdjacentVertices() {
int vertex;
printf("Enter the vertex to list adjacent vertices: ");
scanf("%d", &vertex);
 if (vertex < 0 || vertex >= numVertices) {
printf("Invalid vertex.\n");
return;
}
printf("Vertices adjacent to vertex %d: ", vertex);
for (int i = 0; i < numVertices; i++) {
if (adjacencyMatrix[vertex][i] == 1) {
printf("%d ", i);
}
}
printf("\n");
}
// Depth First Search
void DFSUtil(int v, int visited[]) {
visited[v] = 1;
printf("%d ", v);
for (int i = 0; i < numVertices; i++) {
if (adjacencyMatrix[v][i] == 1 && !visited[i]) {
DFSUtil(i, visited);
}
}
}
void DFS() {
int visited[MAX_VERTICES] = {0};
printf("Depth First Search: ");
for (int i = 0; i < numVertices; i++) {
if (!visited[i]) {
DFSUtil(i, visited);
}
}
printf("\n");
}
// Breadth First Search
void BFS(int start) {
int visited[MAX_VERTICES] = {0};
int queue[MAX_VERTICES], front = -1, rear = -1;
printf("Breadth First Search: ");
visited[start] = 1;
queue[++rear] = start;
while (front != rear) {
int current = queue[++front];
printf("%d ", current);
for (int i = 0; i < numVertices; i++) {
if (adjacencyMatrix[current][i] == 1 && !visited[i]) {
visited[i] = 1;
queue[++rear] = i;
}
}
}
printf("\n");
}
// Function to display menu
void displayMenu() {
printf("\nMenu:\n");
printf("1. Create graph\n");
printf("2. Insert an edge\n");
printf("3. Print Adjacency Matrix\n");
printf("4. List all vertices that are adjacent to a specified vertex\n");
printf("5. Print out vertices using depth first search\n");
printf("6. Print out vertices using breadth first search\n");
printf("7. Exit program\n");
}
int main() {
int choice;
do {
displayMenu();
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
createGraph();
break;
case 2:
insertEdge();
break;
case 3:
printAdjacencyMatrix();
break;
case 4:
listAdjacentVertices();
break;
case 5:
DFS();
break;
case 6:
printf("Enter the starting vertex for Breadth First Search: ");
int start;
scanf("%d", &start);
BFS(start);
break;
case 7:
printf("Exiting program.\n");
break;
default:
printf("Invalid choice. Please enter a number from 1 to 7.\n");
}
 } while (choice != 7);

return 0;
}
Output:

Q18. Create a user-defined structure with the following data members: 1. A Data 2. A link
to the Left child 3. A link to the Right child Perform the following operations on Binary
Search Tree using recursion: 1. Create 2. Traverse (Inorder, Preorder, Postorder) 3. Insert
4. Delete 5. Search 6. Create a file which stores all values of traversal.
Code:
#include <stdio.h>
#include <stdlib.h>

// Node structure for Binary Search Tree

typedef struct Node {
int data;
struct Node* left;
struct Node* right;
} Node;

// Function to create a new node

Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
 printf("Memory allocation failed.\n");
exit(1);
}
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}

// Function to insert a new node into the BST

Node* insert(Node* root, int data) {
if (root == NULL) {
root = createNode(data);
} else if (data <= root->data) {
root->left = insert(root->left, data);
} else {
root->right = insert(root->right, data);
}
return root;
}

// Function to perform inorder traversal of the BST

void inorderTraversal(Node* root, FILE* file) {
if (root == NULL) {
return;
}
inorderTraversal(root->left, file);
fprintf(file, "%d ", root->data);
inorderTraversal(root->right, file);
}

// Function to perform preorder traversal of the BST

void preorderTraversal(Node* root, FILE* file) {
if (root == NULL) {
return;
}
fprintf(file, "%d ", root->data);
preorderTraversal(root->left, file);
preorderTraversal(root->right, file);
}

// Function to perform postorder traversal of the BST

void postorderTraversal(Node* root, FILE* file) {
if (root == NULL) {
return;
}
postorderTraversal(root->left, file);
postorderTraversal(root->right, file);
fprintf(file, "%d ", root->data);
}

// Function to search for a value in the BST

Node* search(Node* root, int data) {
if (root == NULL || root->data == data) {
return root;
}
if (data < root->data) {
return search(root->left, data);
} else {
return search(root->right, data);
}
}

// Function to find the minimum value node in a BST

Node* findMin(Node* root) {
while (root->left != NULL) {
root = root->left;
}
return root;
}

// Function to delete a node from the BST

Node* deleteNode(Node* root, int data) {
if (root == NULL) {
return root;
} else if (data < root->data) {
root->left = deleteNode(root->left, data);
} else if (data > root->data) {
root->right = deleteNode(root->right, data);
} else {
// Case 1: No child or 1 child
if (root->left == NULL) {
Node* temp = root->right;
free(root);
return temp;
} else if (root->right == NULL) {
Node* temp = root->left;
free(root);
return temp;
}
// Case 2: 2 children
Node* temp = findMin(root->right);
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);
}
return root;
}

// Function to delete entire BST

void deleteBST(Node* root) {
if (root == NULL) {
return;
}
deleteBST(root->left);
deleteBST(root->right);
free(root);
}

int main() {
Node* root = NULL;

// Insert elements into the BST

root = insert(root, 10);
root = insert(root, 5);
root = insert(root, 15);
root = insert(root, 3);
root = insert(root, 7);
root = insert(root, 12);
root = insert(root, 20);

// Open file to store traversal values

FILE* file = fopen("bst_traversal.txt", "w");
if (file == NULL) {
printf("Error opening file.\n");
exit(1);
}

// Perform traversals and store traversal values in the file

printf("Inorder Traversal: ");
inorderTraversal(root, file);
printf("\n");

printf("Preorder Traversal: ");

preorderTraversal(root, file);
printf("\n");

printf("Postorder Traversal: ");

postorderTraversal(root, file);
printf("\n");

// Close file
fclose(file);

// Search for a value

int searchValue = 12;
Node* foundNode = search(root, searchValue);
if (foundNode != NULL) {
printf("%d found in the BST.\n", searchValue);
} else {
printf("%d not found in the BST.\n", searchValue);
}
// Delete a node
int deleteValue = 7;
root = deleteNode(root, deleteValue);
printf("Deleted node with value %d.\n", deleteValue);
// Open file to append deleted node value
file = fopen("bst_traversal.txt", "a");
if (file == NULL) {
printf("Error opening file.\n");
exit(1);
 }
fprintf(file, "Deleted node with value %d.\n", deleteValue);
fclose(file);
// Delete entire BST
deleteBST(root);

return 0;
}
Output: