DSA PRACTICAL FILE

SAKSHAM SHARMA
2023UIC3518
 Question-1
Aim: Write a program to implement a linked list
1. #include <stdio.h>
2. #include <stdlib.h>
3.
4. typedef struct Node {
5.
6. int data;
7.
8. struct Node *next;
9. } Node;
10.
11. int main() {
12.
13. Node *first = (Node *)malloc(sizeof(Node));
14. first->data = 10;
15.
16. Node *second = (Node *)malloc(sizeof(Node));
17. second->data = 20;
18.
19. Node *third = (Node *)malloc(sizeof(Node));
20. third->data = 30;
21.
22.
23. first->next = second;
24. second->next = third;
25. third->next = NULL;
26. }
27.
 Question-2
Aim: Write a program to insert and delete a node from a
linked list
1. #include <stdio.h>
2. #include <stdlib.h>
3.
4. struct Node {
5. int data;
6. struct Node* next;
7. };
8.
9. void insertAtPosition(struct Node** head, int value, int position) {
10.
11. struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
12. struct Node* temp = *head;
13.
14.
15. newNode->data = value;
16.
17.
18. for (int i = 1; i < position - 1; i++) {
19. if (temp->next != NULL) {
20. temp = temp->next;
21. } else {
22. printf("Invalid position\n");
23. return;
24. }
25. }
26.
27. newNode->next = temp->next;
28.
29. void deleteAtPosition(struct Node** head, int position) {
30. if (*head == NULL) {
31. printf("Linked list is already empty.\n");
32. return;
33. }
34.
35. struct Node* temp = *head;
36. struct Node* prev = NULL;
37.
38. if (position == 1) {
39. *head = temp->next;
40. free(temp);
41. return;
42. }
43.
44. for (int i = 1; temp != NULL && i < position; i++) {
45. prev = temp;
46. temp = temp->next;
47. }
48.
49. if (temp == NULL) {
50. printf("Invalid position.\n");
51. return;
52. }
53.
54. prev->next = temp->next;
55. free(temp);
56. }
57.
 Question-3
Aim: Write a program to implement doubly linked list
1. #include <stdio.h>
2. #include <stdlib.h>
3.
4. typedef struct Node {
5. int data;
6. struct Node *next;
7. struct Node *prev;
8. } Node;
9.
10. Node *createNode(int data) {
11. Node *newNode = (Node *)malloc(sizeof(Node));
12. newNode->data = data;
13.
14. newNode->next = NULL;
15. newNode->prev = NULL;
16.
17. return newNode;
18. }
19.
20. int main() {
21.
22. Node *head = createNode(10);
23. Node *second = createNode(20);
24. Node *third = createNode(30);
25.
26. head->next = second;
27. second->prev = head;
28. second->next = third;
29. third->prev = second;
30. }
31.
 Question-4
Aim: Write a program to construct a binary search tree
1. #include <stdio.h>
2. #include <stdlib.h>
3.
4. struct BinaryTreeNode {
5. int key;
6. struct BinaryTreeNode *left, *right;
7. };
8.
9. struct BinaryTreeNode* newNode(int value)
10. {
11. struct BinaryTreeNode* temp
12. = (struct BinaryTreeNode*)malloc(
13. sizeof(struct BinaryTreeNode));
14. temp->key = value;
15. temp->left = temp->right = NULL;
16. return temp;
17. }
18.
19. struct BinaryTreeNode*
20. insertNode(struct BinaryTreeNode* node, int value)
21. {
22. if (node == NULL) {
23. return newNode(value);
24. }
25. if (value < node->key) {
26. node->left = insertNode(node->left, value);
27. }
28. else if (value > node->key) {
29. node->right = insertNode(node->right, value);
30. }
31. return node;
32. }
33.
34. int main()
35. {
36. struct BinaryTreeNode* root = NULL;
37.
38. root = insertNode(root, 50);
39. insertNode(root, 30);
40. insertNode(root, 20);
41. insertNode(root, 40);
42. insertNode(root, 70);
43. insertNode(root, 60);
44. insertNode(root, 80);
45. }
 Question-5
Aim: Write a program to implement Binary Search
1. #include <stdio.h>
2.
3. int binarySearch(int arr[], int low, int high, int x)
4. {
5. while (low <= high) {
6. int mid = low + (high - low) / 2;
7.
8. if (arr[mid] == x)
9. return mid;
10.
11. if (arr[mid] < x)
12. low = mid + 1;
13.
14. else
15. high = mid - 1;
16. }
17.
18. return -1;
19. }
 Question-6
Aim: Write a program to implement linear search
1. #include <stdio.h>
2.
3. int linearSearch(int* arr, int n, int key) {
4.
5. for (int i = 0; i < n; i++) {
6. if (arr[i] == key) {
7. return i;
8. }
9. }
10.
11. return -1;
12. }
13.
14. int main() {
15. int arr[] = { 10, 50, 30, 70, 80, 60, 20, 90, 40 };
16. int n = sizeof(arr) / sizeof(arr[0]);
17. int key = 30;
18.
19. int i = linearSearch(arr, n, key);
20.
21. if (i == -1)
22. printf("Key Not Found");
23. else
24. printf("Key Found at Index: %d", i);
25.
26. return 0;
27. }
 Question-7
Aim: Write a program to implement Merge Sort.
1. #include <stdio.h>
2. #include <stdlib.h>
3.
4. // Merges two subarrays of arr[].
5. // First subarray is arr[left..mid]
6. // Second subarray is arr[mid+1..right]
7. void merge(int arr[], int left, int mid, int right) {
8. int i, j, k;
9. int n1 = mid - left + 1;
10. int n2 = right - mid;
11.
12. // Create temporary arrays
13. int leftArr[n1], rightArr[n2];
14.
15. // Copy data to temporary arrays
16. for (i = 0; i < n1; i++)
17. leftArr[i] = arr[left + i];
18. for (j = 0; j < n2; j++)
19. rightArr[j] = arr[mid + 1 + j];
20.
21. // Merge the temporary arrays back into arr[left..right]
22. i = 0;
23. j = 0;
24. k = left;
25. while (i < n1 && j < n2) {
26. if (leftArr[i] <= rightArr[j]) {
27. arr[k] = leftArr[i];
28. i++;
29. }
30. else {
31. arr[k] = rightArr[j];
32. j++;
33. }
34. k++;
35. }
36.
37. // Copy the remaining elements of leftArr[], if any
38. while (i < n1) {
39. arr[k] = leftArr[i];
40. i++;
41. k++;
42. }
43.
44. // Copy the remaining elements of rightArr[], if any
45. while (j < n2) {
46. arr[k] = rightArr[j];
47. j++;
48. k++;
49. }
50. }
51.
52. void mergeSort(int arr[], int left, int right) {
53. if (left < right) {
54.
55. int mid = left + (right - left) / 2;
56.
57. mergeSort(arr, left, mid);
58. mergeSort(arr, mid + 1, right);
59.
60. merge(arr, left, mid, right);
61. }
62. }
63.
64. int main() {
65. int arr[] = { 12, 11, 13, 5, 6, 7 };
66. int n = sizeof(arr) / sizeof(arr[0]);
67.
68. mergeSort(arr, 0, n - 1);
69.
70. for (int i = 0; i < n; i++)
71. printf("%d ", arr[i]);
72. return 0;
73. }
74.
 Question-8
Aim: Write a program to implement Selection Sort
1. #include <stdio.h>
2.
3. void selectionSort(int arr[], int N) {
4.
5. for (int i = 0; i < N - 1; i++) {
6. int min_idx = i;
7. for (int j = i + 1; j < N; j++) {
8. if (arr[j] < arr[min_idx]) {
9. min_idx = j;
10. }
11. }
12.
13. int temp = arr[min_idx];
14. arr[min_idx] = arr[i];
15. arr[i] = temp;
16. }
17. }
18.
19. int main() {
20. int arr[] = {64, 25, 12, 22, 11};
21. int N = sizeof(arr) / sizeof(arr[0]);
22. printf("Unsorted array: \n");
23. for (int i = 0; i < N; i++) {
24. printf("%d ", arr[i]);
25. }
26. printf("\n");
27.
28. selectionSort(arr, N);
29.
30. printf("Sorted array: \n");
31. for (int i = 0; i < N; i++) {
32. printf("%d ", arr[i]);
33. }
34. printf("\n");
35. return 0;
36. }
37.
 Question-9
Aim: Write a program to implement Quick Sort.
1. #include <stdio.h>
2.
3. void swap(int* a, int* b) {
4. int temp = *a;
5. *a = *b;
6. *b = temp;
7. }
8.
9. int partition(int arr[], int low, int high) {
10.
11. int p = arr[low];
12. int i = low;
13. int j = high;
14.
15. while (i < j) {
16.
17. while (arr[i] <= p && i <= high - 1) {
18. i++;
19. }
20.
21. while (arr[j] > p && j >= low + 1) {
22. j--;
23. }
24. if (i < j) {
25. swap(&arr[i], &arr[j]);
26. }
27. }
28. swap(&arr[low], &arr[j]);
29. return j;
30. }
31.
32. void quickSort(int arr[], int low, int high) {
33. if (low < high) {
34.
35. int pi = partition(arr, low, high);
36.
37. quickSort(arr, low, pi - 1);
38. quickSort(arr, pi + 1, high);
39. }
40. }
41.
42. int main() {
43.
44. int arr[] = { 4, 2, 5, 3, 1 };
45. int n = sizeof(arr) / sizeof(arr[0]);
46. quickSort(arr, 0, n - 1);
47.
48. for (int i = 0; i < n; i++)
49. printf("%d ", arr[i]);
50.
51. return 0;
52. }
 Question-10
Aim: Write a program to display pre-order, post-order and in-
order traversal.
1. #include <stdio.h>
2. #include <stdlib.h>
3.
4. struct Node {
5. int data;
6. struct Node* left;
7. struct Node* right;
8. };
9.
10. void inorderTraversal(struct Node* root) {
11.
12. if (root == NULL)
13. return;
14.
15. inorderTraversal(root->left);
16. printf("%d ", root->data);
17. inorderTraversal(root->right);
18. }
19.
20. void preorderTraversal(struct Node* root) {
21.
22. if (root == NULL)
23. return;
24.
25. printf("%d ", root->data);
26. preorderTraversal(root->left);
27. preorderTraversal(root->right);
28. }
29.
30. void postorderTraversal(struct Node* node) {
31.
32. if (node == NULL)
33. return;
34.
35. postorderTraversal(node->left);
36. postorderTraversal(node->right);
37. printf("%d ", node->data);
38. }
39.
40.
41. struct Node* newNode(int data) {
42. struct Node* node = (struct Node*)malloc(sizeof(struct Node));
43.
44. node->data = data;
45. node->left = NULL;
46. node->right = NULL;
47. return node;
48. }
49.
50. int main() {
51. struct Node* root = newNode(1);
52. root->left = newNode(2);
53. root->right = newNode(3);
54. root->left->left = newNode(4);
55. root->left->right = newNode(5);
56. printf("Inorder traversal: ");
57. inorderTraversal(root);
58. printf("\n");
59.
60. printf("Preorder traversal: ");
61. preorderTraversal(root);
62. printf("\n");
63.
64. printf("Postorder traversal: ");
65. postorderTraversal(root);
66. printf("\n");
67.
68. return 0;
69. }
70.