Practical File

Data Structures & Analysis of Algorithms Lab

KCA253

Master of Computer Application (2nd Sem)

Session- 2022-23

Submitted To Submitted By
Dr. Rajesh Verma Vineet Kumar
Professor Roll No- 2200160140035

RBMI Group of Institutions, Bareilly

(Affiliated to A.P.J. Abdul Kalam University, Lucknow)

Vineet Kumar 2200160140035 Page 1

INDEX
S. No. Program Description Page No.

1. A function to create array 4

2. A function to traverse array 5

3. Program to input a new element at the beginning 6

4. Input a new element at the end of an array 7

5. Input a new element at the given location 8

6. Input a new element at the sorted array 9

7. Program to delete element from the beginning 10

8. Program to delete elements from the end 11

9. Program to delete element at the given location 12

10. Program to sort the array by Selection sort method 13

11. Program to sort the array by Bubble sort method 14

12. Program to sort the array by Insertion sort method 15

13. Program to sort the array by Quick sort method 16

14. Program to sort the array by Merge sort method 17

15. Program to search the element from the array by using the Linear 18
search method..

16. Program to search the element from array by using Binary search 19
method

17. Program to concatenate two arrays 20

18. Program to merge two sorted arrays 21

19. Program to create & traverse the Linked List 23

20. Write a program to insert a new node 24

1. At the beginning
2. At the end
3. After given node information
4. In the sorted Linked List.

21. Program to delete a new node 27

1. From the begiqnning

Vineet Kumar 2200160140035 Page 2

2. From the end
3. After given node information.

22. Program to concatenate two linked lists 30

23. Program to sort the information of node 32

24. Program to merge two sorted information linked list 34

25. Program to create & traverse polynomials 36

26. Program to add two polynomials 38

27. Program to create & traverse doubly linked list 41

28. Program to insert a new node into a doubly linked list 42

29. Program to delete a node from a doubly linked list 44

30. Program to find exponent of a given number 46

Signature ……………………….

Vineet Kumar 2200160140035 Page 3

> Write a function to create an array

#include <stdio.h>

void create_array(int count, int *arr) {

for (int i = 0; i < count; i++) {
printf("Enter element %d: ", i);
scanf("%d", &arr[i]);
}
}

int main(int argc, char const *argv[]) {

int count;
printf(">>> Input\n");
printf("Enter number of elements: ");
scanf("%d", &count);

int arr[count];
create_array(count, arr);
printf(">>> Output\n");

for (int i = 0; i < count; i++)

printf("Element %d: %d\n", i, arr[i]);

return 0;
}

Vineet Kumar 2200160140035 Page 4

> Write a function to traverse the array

#include <stdio.h>

void traverse_array(int *arr, int length) {

for (int i = 0; i < length; i++) {
printf("Element %d: %d\n", i, arr[i]);
}
}

int main(int argc, char const *argv[]) {

int arr[] = {5, 73, 95, 24, 21};
traverse_array(arr, sizeof(arr) / sizeof(int));

return 0;
}

Vineet Kumar 2200160140035 Page 5

> Write a program to input a new element at the beginning

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

int main(int argc, char const *argv[]) {

int input, length = 3, *arr = calloc(length, sizeof(int));

printf(">>> Before\n");
for (int i = 0; i < length; i++)
printf("Element %d: %d\n", i, arr[i] = rand());

printf("Enter element to insert at start: ");

scanf("%d", &input);

arr = realloc(arr, (length + 1) * sizeof(int));

for (int i = length; i != -1; i--)

arr[i] = arr[i - 1];
arr[0] = input;

length++;

printf(">>> After\n");
for (int i = 0; i < length; i++)
printf("Element %d: %d\n", i, arr[i]);

return EXIT_SUCCESS;
}

Vineet Kumar 2200160140035 Page 6

> Input a new element at the end of an array.

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

int main(int argc, char const *argv[]) {

int input, length = 3, *arr = calloc(length, sizeof(int));

printf(">>> Before\n");
for (int i = 0; i < length; i++)
printf("Element %d: %d\n", i, arr[i] = rand());

printf("Enter element to insert at end: ");

scanf("%d", &input);

arr = realloc(arr, (length + 1) * sizeof(int));

arr[length] = input;
length++;

printf(">>> After\n");
for (int i = 0; i < length; i++)
printf("Element %d: %d\n", i, arr[i]);

return EXIT_SUCCESS;
}

Vineet Kumar 2200160140035 Page 7

> Input a new element at the given location.

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

int main(int argc, char const *argv[]) {

int input, pos, length = 3, *arr = calloc(length, sizeof(int));

printf(">>> Before\n");
for (int i = 0; i < length; i++)
printf("Element %d: %d\n", i, arr[i] = rand());

printf("Enter element to insert followed by its position: ");

scanf("%d%d", &input, &pos);

arr = realloc(arr, (length + 1) * sizeof(int));

pos = pos > length ? length : pos;

for (int i = length; i > pos; i--)

arr[i] = arr[i - 1];
arr[pos] = input;
length++;

printf(">>> After\n");
for (int i = 0; i < length; i++)
printf("Element %d: %d\n", i, arr[i]);

return EXIT_SUCCESS;
}

Vineet Kumar 2200160140035 Page 8

> Input a new element at the sorted array

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

int main(int argc, char const *argv[]) {

int input, length = 3, *arr = calloc(length, sizeof(int));

printf(">>> Before\n");
for (int i = 0; i < length; i++)
printf("Element %d: %d\n", i, arr[i] = 13 * (i + 1));

printf("Enter element to insert: ");

scanf("%d", &input);

arr = realloc(arr, length + 1 * sizeof(int));

int i = length;
for (; input < arr[i - 1]; i--)
arr[i] = arr[i - 1];
arr[i] = input;
length++;

printf(">>> After\n");
for (int i = 0; i < length; i++)
printf("Element %d: %d\n", i, arr[i]);

return EXIT_SUCCESS;
}

Vineet Kumar 2200160140035 Page 9

> Write a program to delete element from the beginning

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

int main(int argc, char const *argv[]) {

int count;

printf("Enter number of elements: ");

scanf("%d", &count);
if (count == 0) {
printf("Invalid input!");
return 1;
}

int *arr = calloc(count, sizeof(int));

for (int i = 0; i < count; i++) {
printf("Enter element %d: ", i);
scanf("%d", &arr[i]);
}

printf("Deleting element at index 0\n");

count--;

for (int i = 0; i < count; i++)

arr[i] = arr[i + 1];
arr = realloc(arr, count);
for (int i = 0; i < count; i++)
printf("Element at %d: %d\n", i, arr[i]);

return EXIT_SUCCESS;
}

Vineet Kumar 2200160140035 Page 10

> Write a program to delete elements from the end.

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

int main(int argc, char const *argv[]) {

int count;

printf("Enter number of elements: ");

scanf("%d", &count);

if (count == 0) {
printf("Invalid input!");
return 1;
}

int *arr = calloc(count, sizeof(int));

for (int i = 0; i < count; i++) {
printf("Enter element %d: ", i);
scanf("%d", &arr[i]);
}

printf("Deleting element at index %d\n", count - 1);

count--;
arr = realloc(arr, count);
for (int i = 0; i < count; i++)
printf("Element at %d: %d\n", i, arr[i]);

return EXIT_SUCCESS;
}

Vineet Kumar 2200160140035 Page 11

> Write a program to delete an element at the given location.

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

int main(int argc, char const *argv[]) {

int count, pos;

printf("Enter number of elements: ");

scanf("%d", &count);
if (count == 0) {
printf("Invalid input!");
return 1;
}

int *arr = calloc(count, sizeof(int));

for (int i = 0; i < count; i++) {
printf("Enter element %d: ", i);
scanf("%d", &arr[i]);
}

printf("Enter index to delete element from: ", &pos);

scanf("%d", &pos);
for (int i = pos; i <= count; i++)
arr[i] = arr[i + 1];
count--;
arr = realloc(arr, count);
for (int i = 0; i < count; i++)
printf("Element at %d: %d\n", i, arr[i]);

return EXIT_SUCCESS;
}

Vineet Kumar 2200160140035 Page 12

> Write a program to sort the array by Selection sort method.

#include <stdio.h>

void swap(int *a, int *b) {

*a = *a + *b; *b = *a - *b; *a = *a - *b;
}

void selection_sort(int *arr, int count) {

for (int i = 0; i < count; i++)
for (int j = i; j < count; j++)
if (arr[i] > arr[j])
swap(&arr[i], &arr[j]);
}

int main(int argc, char const *argv[]) {

int count;
printf("How many numbers do you have?: ");
scanf("%d", &count);
int arr[count];
for (int i = 0; i < count; i++) {
printf("Enter number %d: ", i);
scanf("%d", &arr[i]);
}
selection_sort(arr, count);
printf("Numbers after sorting:");
for (int i = 0; i < count; i++)
printf(" %d", arr[i]);
printf("\n");
return 0;
}

Vineet Kumar 2200160140035 Page 13

> Write a program to sort the array by Bubble sort method

#include <stdio.h>

void swap(int *a, int *b) {

*a = *a + *b; *b = *a - *b; *a = *a - *b;
}

void bubble_sort(int *arr, int count) {

for (int i = 0; i < count - 1; i++)
for (int j = 0; j < count - i - 1; j++)
if (arr[j] > arr[j + 1])
swap(&arr[j], &arr[j + 1]);
}

int main(int argc, char const *argv[]) {

int count;
printf("How many numbers do you have?: ");
scanf("%d", &count);
int arr[count];
for (int i = 0; i < count; i++) {
printf("Enter number %d: ", i);
scanf("%d", &arr[i]);
}
bubble_sort(arr, count);
printf("Numbers after sorting:");
for (int i = 0; i < count; i++)
printf(" %d", arr[i]);
printf("\n");
return 0;
}

Vineet Kumar 2200160140035 Page 14

> Write a program to sort the array by Insertion sort method

#include <stdio.h>

void insertion_sort(int *arr, int count) {

for (int i = 1; i < count; i++) {
int j = i - 1, key = arr[i];
while (key < arr[j] && j >= 0) {
arr[j + 1] = arr[j]; j--;
}
arr[j + 1] = key;
}
}

int main(int argc, char const *argv[]) {

int count;
printf("How many numbers do you have?: ");
scanf("%d", &count);
int arr[count];
for (int i = 0; i < count; i++) {
printf("Enter number %d: ", i);
scanf("%d", &arr[i]);
}
insertion_sort(arr, count);
printf("Numbers after sorting:");
for (int i = 0; i < count; i++)
printf(" %d", arr[i]);
printf("\n");
return 0;
}

Vineet Kumar 2200160140035 Page 15

> Write a program to sort the array by Quick sort method

#include <stdio.h>

void swap(int *a, int *b) {

*a = *a + *b; *b = *a - *b; *a = *a - *b;
}
void quick_sort(int *number, int first, int last) {
if (first < last) {
int i = first, pivot = first, j = last;
while (i < j) {
while (number[i] <= number[pivot] && i < last) i++;
while (number[j] > number[pivot]) j--;
if (i < j) swap(&number[i], &number[j]);
}
swap(&number[pivot], &number[j]);
quick_sort(number, first, j - 1);
quick_sort(number, j + 1, last);
}
}
int main(int argc, char const *argv[]) {
int count;
printf("How many numbers do you have?: ");
scanf("%d", &count);
int arr[count];
for (int i = 0; i < count; i++) {
printf("Enter number %d: ", i);
scanf("%d", &arr[i]);
}
quick_sort(arr, 0, count - 1);
printf("Numbers after sorting:");
for (int i = 0; i < count; i++) printf(" %d", arr[i]);
printf("\n");
return 0;
}

Vineet Kumar 2200160140035 Page 16

> Write a program to sort the array by Merge sort method

#include <stdio.h>

void merge_sort(int *arr, int i, int j) {

int aux[0xff];

if (j <= i)
return;

int mid = (i + j) / 2;

merge_sort(arr, i, mid);
merge_sort(arr, mid + 1, j);

int pointer_left = i;
int pointer_right = mid + 1;

for (int k = i; k <= j; k++) {

if (pointer_left == mid + 1) {
aux[k] = arr[pointer_right];
pointer_right++;
} else if (pointer_right == j + 1) {
aux[k] = arr[pointer_left];
pointer_left++;
} else if (arr[pointer_left] < arr[pointer_right]) {
aux[k] = arr[pointer_left];
pointer_left++;
} else {
aux[k] = arr[pointer_right];
pointer_right++;
}
}

for (int k = i; k <= j; k++) {

arr[k] = aux[k];
}
}

int main(int argc, char const *argv[]) {

int count;
printf("How many numbers do you have?: ");
scanf("%d", &count);
int arr[count];

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

printf("Enter number %d: ", i);

Vineet Kumar 2200160140035 Page 17

scanf("%d", &arr[i]);
}

merge_sort(arr, 0, count - 1);

printf("Numbers after sorting:");

for (int i = 0; i < count; i++)
printf(" %d", arr[i]);
printf("\n");

return 0;
}

Vineet Kumar 2200160140035 Page 18

> Write a program to search the element from array by using Linear search method

#include <stdio.h>

int main(int argc, char const *argv[]) {

int count, key;
printf("How many numbers do you have?: ");
scanf("%d", &count);
int arr[count];

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

printf("Enter number %d: ", i);
scanf("%d", &arr[i]);
}

printf("Enter number you want to search: ");

scanf("%d", &key);

for (int i = 0; i < count; i++)

if (arr[i] == key) {
printf("Number found at position %d\n", i);
return 0;
}

printf("Number not found in array!!!\n");

return 0;
}

Vineet Kumar 2200160140035 Page 19

> Write a program to search the element from array by using Binary search method

#include <stdio.h>

int main(int argc, char const *argv[]) {

int count;
printf("How many numbers do you have?: ");
scanf("%d", &count);

int arr[count], key, low = 0, high = count, mid = (low + high) / 2;

for (int i = 0; i < count; i++) {
printf("Enter number %d: ", i);
scanf("%d", &arr[i]);
}

printf("Enter number you want to search: ");

scanf("%d", &key);
while (low <= high) {
if (arr[mid] == key) {
printf("Number found at index %d\n", mid);
return 0;
}
if (arr[mid] < key) {
low = mid + 1;
} else {
high = mid - 1;
}
mid = (low + high) / 2;
}

printf("Number not found in array!!!\n");

return 0;
}

Vineet Kumar 2200160140035 Page 20

> Write a program to concatenate two arrays

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

int main(int argc, char const *argv[]) {

int count1, *arr1, count2, *arr2;
printf("How many numbers do you have for first array?: ");
scanf("%d", &count1);
arr1 = calloc(count1, sizeof(int));
for (int i = 0; i < count1; i++) {
printf("Enter number %d for array1: ", i);
scanf("%d", &arr1[i]);
}
printf("How many numbers do you have for second array?: ");
scanf("%d", &count2);
arr2 = calloc(count2, sizeof(int));
for (int i = 0; i < count2; i++) {
printf("Enter number %d for array2: ", i);
scanf("%d", &arr2[i]);
}
int count = count1 + count2, *arr = calloc(count, sizeof(int));
for (int i = 0; i < count; i++)
arr[i] = i < count1 ? arr1[i] : arr2[i - count1];
free(arr1);
free(arr2);
printf("Merged Array:");
for (int i = 0; i < count; i++)
printf(" %d", arr[i]);
printf("\n");

return EXIT_SUCCESS;
}

Vineet Kumar 2200160140035 Page 21

> Write a program to merge two sorted arrays

#include <stdio.h>

void merge_sorted_array(int *a, int *b, int *c, int n, int m) {

int i = 0, j = 0, k = 0;
while (i < n && j < m) {
if (a[i] < b[j]) {
c[k] = a[i];
i++;
} else {
c[k] = b[j];
j++;
}
k++;
}
while (i < n) {
c[k] = a[i];
i++;
k++;
}
while (j < m) {
c[k] = b[j];
j++;
k++;
}
}

int main(int argc, char const *argv[]) {

int count1, count2;

printf("Enter the number of elements in the first array: ");

scanf("%d", &count1);
int arr1[count1];
for (int i = 0; i < count1; i++) {
printf("Enter element %d of first array: ", i);
scanf("%d", &arr1[i]);
}

printf("Enter the number of elements in the second array: ");

scanf("%d", &count2);
int arr2[count2];
for (int i = 0; i < count2; i++) {
printf("Enter element %d of second array: ", i);
scanf("%d", &arr2[i]);
}

Vineet Kumar 2200160140035 Page 22

int count = count1 + count2, arr[count];
merge_sorted_array(arr1, arr2, arr, count1, count2);
printf("The merged array is:");
for (int i = 0; i < count; i++)
printf(" %d", arr[i]);
printf("\n");

return 0;
}

Vineet Kumar 2200160140035 Page 23

> Write a program to create & traverse the Linked List

#include <stdio.h>
#include <stdlib.h>
struct node { int data; struct node *next; };

void create_ll(struct node **head, int count) {

struct node *temp, *prev;
temp = (struct node *)malloc(sizeof(struct node));
temp->data = count;
temp->next = NULL;
*head = temp; prev = temp;
for (int i = 1; i < count; i++) {
temp = (struct node *)malloc(sizeof(struct node));
temp->data = rand() % 100;
temp->next = NULL; prev->next = temp; prev = temp;
}
}
void print_ll(struct node *head) {
struct node *temp = head;
printf("Elements in list currently:");
while (temp != NULL) {
printf(" %d", temp->data);
temp = temp->next;
}
printf("\n");
}
int main(int argc, char const *argv[]) {
int count; struct node *head;
printf("Enter the number of elements: ");
scanf("%d", &count);
create_ll(&head, count);
print_ll(head);
return EXIT_SUCCESS;
}

Vineet Kumar 2200160140035 Page 24

> Write a program to insert a new node

1. At the beginning
2. At the end
3. After given node information
4. In the sorted info Linked List.

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

struct node {
int data;
struct node *next;
};

void create_sorted_ll(struct node **head, int count) {

struct node *temp, *prev;
temp = (struct node *)malloc(sizeof(struct node));
temp->data = 0;
temp->next = NULL;
*head = temp;
prev = temp;
for (int i = 1; i < count; i++) {
temp = (struct node *)malloc(sizeof(struct node));
temp->data = i;
temp->next = NULL;
prev->next = temp;
prev = temp;
}
}

void insert_at_beginning(struct node **head, int el) {

struct node *temp;
temp = (struct node *)malloc(sizeof(struct node));
temp->data = el;
temp->next = *head;
*head = temp;
}

void insert_at_end(struct node **head, int el) {

struct node *temp, *prev;
temp = (struct node *)malloc(sizeof(struct node));
temp->data = el;
temp->next = NULL;
prev = *head;
while (prev->next != NULL)
prev = prev->next;
prev->next = temp;
Vineet Kumar 2200160140035 Page 25
}
void insert_at_position(struct node **head, int el, int pos) {
struct node *temp, *ptr, *prev;
temp = (struct node *)malloc(sizeof(struct node));
temp->data = el;
temp->next = NULL;
ptr = *head;
for (int i = 1; i < pos; i++) {
prev = ptr;
ptr = ptr->next;
}
prev->next = temp;
temp->next = ptr;
}
void insert_node_at_sorted_ll(struct node **head, int el) {
struct node *temp, *ptr, *prev;
temp = (struct node *)malloc(sizeof(struct node));
temp->data = el;
temp->next = NULL;
ptr = *head;
if (ptr->data > el) {
temp->next = ptr; *head = temp;
} else {
while (ptr->next != NULL && ptr->next->data < el)
ptr = ptr->next;
prev = ptr; ptr = ptr->next;
prev->next = temp;
temp->next = ptr;
}
}
void print_ll(struct node *head) {
struct node *temp = head;
printf("Elements in list currently:");
while (temp != NULL) {
printf(" %d", temp->data);
temp = temp->next;
}
printf("\n");
}
int main(int argc, char const *argv[]) {
struct node *head;
int count, pos, el;
printf("Enter the number of nodes: ");
scanf("%d", &count);
create_sorted_ll(&head, count);
print_ll(head);
printf("Enter the node for insertion at beginning: ");

Vineet Kumar 2200160140035 Page 26

scanf("%d", &el);
insert_at_beginning(&head, el);
print_ll(head);
printf("Enter the node for insertion at end: ");
scanf("%d", &el);
insert_at_end(&head, el);
print_ll(head);
printf("Enter the node for insertion at position: ");
scanf("%d", &el);
printf("Enter the position: ");
scanf("%d", &pos);
insert_at_position(&head, el, pos);
print_ll(head);
printf("Enter the node for insertion at sorted linked list: ");
scanf("%d", &el);
insert_node_at_sorted_ll(&head, el);
print_ll(head);
return EXIT_SUCCESS;
}

Vineet Kumar 2200160140035 Page 27

> Write a program to delete a new node

1. From the beginning

2. From the end
3. After given node information.

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

struct node {
int data;
struct node *next;
};

void create_ll(struct node **head, int count) {

struct node *temp, *prev;
temp = (struct node *)malloc(sizeof(struct node));
temp->data = count;
temp->next = NULL;
*head = temp;
prev = temp;
for (int i = 1; i < count; i++) {
temp = (struct node *)malloc(sizeof(struct node));
temp->data = i;
temp->next = NULL;
prev->next = temp;
prev = temp;
}
}

void delete_at_beginning(struct node **head) {

struct node *temp;
temp = *head;
*head = temp->next;
free(temp);
}

void delete_at_end(struct node **head) {

struct node *temp, *prev;
temp = *head;
while (temp->next != NULL) {
prev = temp;
temp = temp->next;
}
prev->next = NULL;
free(temp);
}

Vineet Kumar 2200160140035 Page 28

void delete_at_position(struct node **head, int pos) {
struct node *temp, *prev;
temp = *head;
for (int i = 1; i < pos - 1; i++)
temp = temp->next;
prev = temp->next;
temp->next = prev->next;
free(prev);
}

void print_ll(struct node *head) {

printf("Elements in list currently:");
while (head != NULL) {
printf(" %d", head->data);
head = head->next;
}
printf("\n");
}

int main(int argc, char const *argv[]) {

struct node *head;
int count, pos;
printf("Enter the number of nodes in the linked list: ");
scanf("%d", &count);
create_ll(&head, count);
print_ll(head);
printf("Enter the 1 for Deletion From Beginning: ");
scanf("%d", &pos);
if (pos == 1)
delete_at_beginning(&head);
print_ll(head);
printf("Enter the 2 for Deletion From End: ");
scanf("%d", &pos);
if (pos == 2)
delete_at_end(&head);
print_ll(head);
printf("Enter the 3 for Deletion From Position: ");
scanf("%d", &pos);
if (pos == 3) {
printf("Enter the position from where you want to delete: ");
scanf("%d", &pos);
delete_at_position(&head, pos);
}
print_ll(head);
return EXIT_SUCCESS;
}

Vineet Kumar 2200160140035 Page 29

Vineet Kumar 2200160140035 Page 30
> Write a program to concatenate two linked list

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

struct node {
int data;
struct node *next;
};

void create_ll1(struct node **head, int count) {

struct node *temp, *ptr;
temp = (struct node *)malloc(sizeof(struct node));
temp->data = count;
temp->next = NULL;
*head = temp;
ptr = temp;
for (int i = 1; i < count; i++) {
temp = (struct node *)malloc(sizeof(struct node));
temp->data = i;
temp->next = NULL;
ptr->next = temp;
ptr = temp;
}
}

void create_ll2(struct node **head, int n) {

struct node *temp, *ptr;
temp = (struct node *)malloc(sizeof(struct node));
temp->data = n;
temp->next = NULL;
*head = temp;
ptr = temp;
for (int i = 1; i < n; i++) {
temp = (struct node *)malloc(sizeof(struct node));
temp->data = i;
temp->next = NULL;
ptr->next = temp;
ptr = temp;
}
}

void merge_ll(struct node *head1, struct node *head2) {

struct node *ptr1, *ptr2;
ptr1 = head1;
ptr2 = head2;
while (ptr1->next != NULL)

Vineet Kumar 2200160140035 Page 31

ptr1 = ptr1->next;
ptr1->next = ptr2;
}

void print_ll(struct node *head) {

while (head != NULL) {
printf(" %d", head->data);
head = head->next;
}
printf("\n");
}

int main(int argc, char const *argv[]) {

struct node *head1, *head2;
create_ll1(&head1, 5);
printf("Linked list 1:");
print_ll(head1);
create_ll2(&head2, 5);
printf("Linked list 2:");
print_ll(head2);
merge_ll(head1, head2);
printf("Concatenated linked list:");
print_ll(head1);
return EXIT_SUCCESS;
}

Vineet Kumar 2200160140035 Page 32

> Write a program to sort the information of node

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

struct node {
int data;
struct node *next;
};

void create_ll(struct node **head, int count) {

struct node *temp, *ptr;
temp = (struct node *)malloc(sizeof(struct node));
temp->data = count;
temp->next = NULL;
*head = temp;
ptr = temp;
for (int i = 1; i < count; i++) {
temp = (struct node *)malloc(sizeof(struct node));
temp->data = i;
temp->next = NULL;
ptr->next = temp;
ptr = temp;
}
}

void sort_full_ll(struct node **head) {

struct node *ptr, *ptr1, *ptr2;
ptr = *head;
while (ptr->next != NULL) {
ptr1 = ptr;
ptr2 = ptr->next;
while (ptr2 != NULL) {
if (ptr1->data > ptr2->data) {
int temp = ptr1->data;
ptr1->data = ptr2->data;
ptr2->data = temp;
}
ptr2 = ptr2->next;
}
ptr = ptr->next;
}
}

void print_ll(struct node *head) {

while (head != NULL) {
printf(" %d", head->data);
Vineet Kumar 2200160140035 Page 33
head = head->next;
}
printf("\n");
}

int main(int argc, char const *argv[]) {

struct node *head;
int count;
printf("Enter the number of nodes for linked list: ");
scanf("%d", &count);
create_ll(&head, count);
printf("Unsorted linked list:");
print_ll(head);
sort_full_ll(&head);
printf("Sorted linked list:");
print_ll(head);
return EXIT_SUCCESS;
}

Vineet Kumar 2200160140035 Page 34

> Write a program to merge two sorted information linked list

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

struct node {
int data;
struct node *next;
};

void move_node(struct node **destRef, struct node **sourceRef) {

struct node *newNode = *sourceRef;
*sourceRef = newNode->next;
newNode->next = *destRef;
*destRef = newNode;
}

struct node *sorted_merge(struct node *a, struct node *b) {

struct node dummy;
struct node *tail = &dummy;
dummy.next = NULL;
while (1) {
if (a == NULL) {
tail->next = b;
break;
} else if (b == NULL) {
tail->next = a;
break;
}
if (a->data <= b->data)
move_node(&(tail->next), &a);
else
move_node(&(tail->next), &b);
tail = tail->next;
}
return dummy.next;
}

void push(struct node **head_ref, int new_data) {

struct node *new_node = (struct node *)malloc(sizeof(struct node));
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}

void print_ll(struct node *node) {

Vineet Kumar 2200160140035 Page 35

while (node != NULL) {
printf(" %d", node->data);
node = node->next;
}
printf("\n");
}

int main(int argc, char const *argv[]) {

struct node *res = NULL, *a = NULL, *b = NULL;

push(&a, 15);
push(&a, 10);
push(&a, 5);
push(&b, 20);
push(&b, 3);
push(&b, 2);

printf("List A before merge:");

print_ll(a);
printf("List B before merge:");
print_ll(b);

res = sorted_merge(a, b);

printf("Lists after merge:");

print_ll(res);

return EXIT_SUCCESS;
}

Vineet Kumar 2200160140035 Page 36

> Write a program to create & traverse polynomials

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

struct node {
int coeff;
int pow;
struct node *next;
};

void create_node(int x, int y, struct node **temp) {

struct node *r, *z = *temp;
if (z == NULL) {
r = (struct node *)malloc(sizeof(struct node));
r->coeff = x;
r->pow = y;
*temp = r;
r->next = (struct node *)malloc(sizeof(struct node));
r = r->next;
r->next = NULL;
} else {
r->coeff = x;
r->pow = y;
r->next = (struct node *)malloc(sizeof(struct node));
r = r->next;
r->next = NULL;
}
}

void polynomial_print(struct node *node) {

while (node->next != NULL) {
printf("%dx^%d", node->coeff, node->pow);
node = node->next;
if (node->next != NULL)
printf(" + ");
}
printf("\n");
}

int main(int argc, char const *argv[]) {

struct node *p1 = NULL, *p2 = NULL, *result = NULL;
create_node(41, 7, &p1);
create_node(12, 5, &p1);
create_node(65, 0, &p1);
create_node(21, 5, &p2);
create_node(15, 2, &p2);
Vineet Kumar 2200160140035 Page 37
printf("Polynomial: ");
polynomial_print(p1);
return EXIT_SUCCESS;
}

Vineet Kumar 2200160140035 Page 38

> Write a program to add two polynomials

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

struct node {
int coeff;
int pow;
struct node *next;
};

void create_node(int x, int y, struct node **temp) {

struct node *r, *z = *temp;
if (z == NULL) {
r = (struct node *)malloc(sizeof(struct node));
r->coeff = x;
r->pow = y;
*temp = r;
r->next = (struct node *)malloc(sizeof(struct node));
r = r->next;
r->next = NULL;
} else {
r->coeff = x;
r->pow = y;
r->next = (struct node *)malloc(sizeof(struct node));
r = r->next;
r->next = NULL;
}
}

void polynomial_add(struct node *p1, struct node *p2, struct node *result) {
while (p1->next && p2->next) {
if (p1->pow > p2->pow) {
result->pow = p1->pow;
result->coeff = p1->coeff;
p1 = p1->next;
} else if (p1->pow < p2->pow) {
result->pow = p2->pow;
result->coeff = p2->coeff;
p2 = p2->next;
} else {
result->pow = p1->pow;
result->coeff = p1->coeff + p2->coeff;
p1 = p1->next;
p2 = p2->next;
}
result->next = (struct node *)malloc(sizeof(struct node));

Vineet Kumar 2200160140035 Page 39

result = result->next;
result->next = NULL;
}
while (p1->next || p2->next) {
if (p1->next) {
result->pow = p1->pow;
result->coeff = p1->coeff;
p1 = p1->next;
}
if (p2->next) {
result->pow = p2->pow;
result->coeff = p2->coeff;
p2 = p2->next;
}
result->next = (struct node *)malloc(sizeof(struct node));
result = result->next;
result->next = NULL;
}
}

void polynomial_print(struct node *node) {

while (node->next != NULL) {
printf("%dx^%d", node->coeff, node->pow);
node = node->next;
if (node->next != NULL)
printf(" + ");
}
printf("\n");
}

int main(int argc, char const *argv[]) {

struct node *p1 = NULL, *p2 = NULL, *result = NULL;
create_node(41, 7, &p1);
create_node(12, 5, &p1);
create_node(65, 0, &p1);
create_node(21, 5, &p2);
create_node(15, 2, &p2);
printf("Polynomial 1: ");
polynomial_print(p1);
printf("Polynomial 2: ");
polynomial_print(p2);
result = (struct node *)malloc(sizeof(struct node));
polynomial_add(p1, p2, result);
printf("Polynomial after adding p1 and p2: ");
polynomial_print(result);
return EXIT_SUCCESS;
}

Vineet Kumar 2200160140035 Page 40

Vineet Kumar 2200160140035 Page 41
> Write a program to create & traverse doubly linked list

#include <stdio.h>
#include <stdlib.h>
struct node { int data; struct node *next; struct node *prev; };

void create_dll(struct node **head, int count) {

struct node *temp = *head, *temp2;
if (temp == NULL) {
temp = (struct node *)malloc(sizeof(struct node));
temp->data = rand() % 100;
temp->next = NULL; temp->prev = NULL; *head = temp;
}
while (temp->next != NULL) temp = temp->next;
for (int i = 0; i < count; i++) {
temp2 = (struct node *)malloc(sizeof(struct node));
temp2->data = rand() % 100;
temp2->next = NULL;
temp2->prev = temp;
temp->next = temp2;
temp = temp2;
}
}
void print_ll(struct node *head) {
while (head != NULL) {
printf(" %d", head->data);
head = head->next;
}
printf("\n");
}
int main(int argc, char const *argv[]) {
struct node *head = NULL;
create_dll(&head, 10);
printf("Doubly linked list with 10 elements:");
print_ll(head);
return EXIT_SUCCESS;
}

Vineet Kumar 2200160140035 Page 42

> Write a program to insert a new node into doubly linked list

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

struct node {
int data;
struct node *next;
struct node *prev;
};

void create_dll(struct node **head, int n) {

struct node *temp = *head;
if (temp == NULL) {
temp = (struct node *)malloc(sizeof(struct node));
temp->data = rand() % 100;
temp->next = NULL;
temp->prev = NULL;
*head = temp;
}
while (temp->next != NULL)
temp = temp->next;
for (int i = 0; i < n; i++) {
struct node *temp2 = (struct node *)malloc(sizeof(struct node));
temp2->data = rand() % 100;
temp2->next = NULL;
temp2->prev = temp;
temp->next = temp2;
temp = temp2;
}
}

void insert_node(struct node **head, int data, int pos) {

struct node *temp = *head;
struct node *temp2 = (struct node *)malloc(sizeof(struct node));
temp2->data = data;
temp2->next = NULL;
temp2->prev = NULL;
if (pos == 0) {
temp2->next = temp;
temp->prev = temp2;
*head = temp2;
} else {
for (int i = 0; i < pos - 1; i++)
temp = temp->next;
temp2->next = temp->next;
temp->next->prev = temp2;
Vineet Kumar 2200160140035 Page 43
temp->next = temp2;
temp2->prev = temp;
}
}
void print_ll(struct node *head) {
while (head != NULL) {
printf(" %d", head->data);
head = head->next;
}
printf("\n");
}
int main(int argc, char const *argv[]) {
struct node *head = NULL;
create_dll(&head, 10);
printf("Before Insertion:");
print_ll(head);
printf("Enter the data to be inserted: ");
int data, pos;
scanf("%d", &data);
printf("Enter the position: ");
scanf("%d", &pos);
insert_node(&head, data, pos);
printf("After Insertion:");
print_ll(head);
return EXIT_SUCCESS;
}

Vineet Kumar 2200160140035 Page 44

> Write a program to delete a node from doubly linked list

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

struct node {
int data;
struct node *next;
struct node *prev;
};

void delete_node(struct node **head_ref, struct node *del) {

if (*head_ref == NULL || del == NULL)
return;
if (*head_ref == del)
*head_ref = del->next;
if (del->next != NULL)
del->next->prev = del->prev;
if (del->prev != NULL)
del->prev->next = del->next;
free(del);
}

void push(struct node **head_ref, int new_data) {

struct node *new_node = (struct node *)malloc(sizeof(struct node));
new_node->data = new_data;
new_node->prev = NULL;
new_node->next = (*head_ref);
if ((*head_ref) != NULL)
(*head_ref)->prev = new_node;
(*head_ref) = new_node;
}

void print_ll(struct node *node) {

while (node != NULL) {
printf(" %d", node->data);
node = node->next;
}
printf("\n");
}

int main(int argc, char const *argv[]) {

struct node *head = NULL;
push(&head, 2);
push(&head, 4);
push(&head, 8);
push(&head, 10);
Vineet Kumar 2200160140035 Page 45
printf("Original Linked list:");
print_ll(head);
delete_node(&head, head);
delete_node(&head, head->next);
delete_node(&head, head->next);
printf("Modified Linked list:");
print_ll(head);
return EXIT_SUCCESS;
}

Vineet Kumar 2200160140035 Page 46

> Program to find exponent of a given number

#include <stdio.h>

int main(int argc, char const *argv[]) {

int base, exponent;
long long result = 1;

printf("Enter a base number: ");

scanf("%d", &base);

printf("Enter an exponent: ");

scanf("%d", &exponent);

while (exponent != 0) {
result *= base;
--exponent;
}

printf("Answer = %lld", result);

return 0;
}

Vineet Kumar 2200160140035 Page 47