MERGE SORT:
1#include <stdio.h>
2#define max 8
3int arr[max]; // we have defined array globally.
4void mergesort(int low, int high);
5void merge(int low, int mid, int high);
6void main()
7{
8 int i, j;
9 printf("enter the elements\n");
10 for (i = 0; i < 8; i++)
11 {
12 scanf("%d", &arr[i]);
13 }
14 mergesort(0, 7);
15 printf("Sorted list is as follows:\n");
16 for (i = 0; i <= 7; i++)
17 printf("%d\n", arr[i]);
18}
19
20void mergesort(int low, int high)
21{
22 if (low != high)
23 {
24 int mid;
25 mid = (low + high) / 2;
26 mergesort(low, mid);
27 mergesort(mid + 1, high);
28 merge(low, mid, high);
29 }
30}
31
32void merge(int low, int mid, int high)
33{
34 int temp[max];
35 int i = low;
36 int k = low;
37 int j = mid + 1;
38 while ((i <= mid) && (j <= high))
39 {
40 if (arr[i] <= arr[j])
41 temp[k++] = arr[i++];
42 else
43 temp[k++] = arr[j++];
44 }
45 while (i <= mid)
46 temp[k++] = arr[i++];
47 while (j <= high)
48 temp[k++] = arr[j++];
49 for (i = low; i <= high; i++)
50 {
51 arr[i] = temp[i];
52 }
53}
HEAP SORT:
1#include <stdio.h>
2void maxheapify(int a[], int, int);
3void maxheap(int a[], int beg, int end)
4{
5 int i;
6 for (i = end / 2; i >= beg; i--)
7 {
8 maxheapify(a, i, end);
9 }
10}
11
12void maxheapify(int a[], int f, int size)
13{
14 int max = f;
15 int l = f * 2, r = f * 2 + 1, t;
16
17 if (l <= size && a[l] > a[max])
18 max = l;
19 if (r <= size && a[r] > a[max])
20 max = r;
21 if (f != max)
22 {
23 t = a[f];
24 a[f] = a[max];
25 a[max] = t;
26 maxheapify(a, max, size);
27 }
28}
29
30void heapsort(int a[], int size)
31{
32 int i, t;
33 for (i = size; i >= 2; i--)
34 {
35 t = a[1];
36 a[1] = a[i];
37 a[i] = t;
38 maxheapify(a, 1, i - 1);
39 }
40}
41
42int main()
43{
44 int a[10], i;
45 printf("Enter array elements:\n");
46 for (i = 1; i < 10; i++)
47 {
48 scanf("%d", &a[i]);
49 }
50
51 maxheap(a, 1, 9);
52 heapsort(a, 9);
53 printf("Sorted array:\n");
54 for (i = 1; i < 10; i++)
55 {
56 printf("%d", a[i]);
57 printf("\n");
58 }
59}
QUICK SORT:
1#include <stdio.h>
2#define max 8
3int arr[max];
4void quicksort(int low, int high);
5int partition(int low, int high);
6int main()
7{
8 int i;
9 printf("Enter the elements:\n");
10 for (i = 1; i <= max; i++)
11 scanf("%d", &arr[i]);
12 quicksort(1, 8);
13 printf("Sorted list is as follows:\n");
14 for (i = 1; i <= max; i++)
15 printf("%d\n", arr[i]);
16}
17
18void quicksort(int low, int high)
19{
20 if (low < high)
21 {
22 int pi = partition(low, high);
23 quicksort(low, pi - 1);
24 quicksort(pi + 1, high);
25 }
26}
27
28int partition(int low, int high)
29{
30 int pivot = arr[high];
31 int i = low - 1, j, temp;
32 for (j = low; j <= high - 1; j++)
33 {
34 if (arr[j] < pivot)
35 {
36 i++;
37 temp = arr[i];
38 arr[i] = arr[j];
39 arr[j] = temp;
40 }
41 }
42 temp = arr[i + 1];
43 arr[i + 1] = arr[high];
44 arr[high] = temp;
45 return (i + 1);
46}
BST:
1#include <stdio.h>
2#include <stdlib.h>
3
4struct BinaryTreeNode
5{
6 int key;
7 struct BinaryTreeNode *left, *right;
8};
9
10struct BinaryTreeNode *newNodeCreate(int value)
11{
12 struct BinaryTreeNode *temp = (struct BinaryTreeNode *)malloc(
13 sizeof(struct BinaryTreeNode));
14 temp->key = value;
15 temp->left = temp->right = NULL;
16 return temp;
17}
18
19struct BinaryTreeNode *
20insertNode(struct BinaryTreeNode *node, int value)
21{
22 if (node == NULL)
23 {
24 return newNodeCreate(value);
25 }
26 if (value < node->key)
27 {
28 node->left = insertNode(node->left, value);
29 }
30 else if (value > node->key)
31 {
32 node->right = insertNode(node->right, value);
33 }
34 return node;
35}
36
37void postOrder(struct BinaryTreeNode *root)
38{
39 if (root != NULL)
40 {
41 postOrder(root->left);
42 postOrder(root->right);
43 printf(" %d ", root->key);
44 }
45}
46void inOrder(struct BinaryTreeNode *root)
47{
48 if (root != NULL)
49 {
50 inOrder(root->left);
51 printf(" %d ", root->key);
52 inOrder(root->right);
53 }
54}
55
56void preOrder(struct BinaryTreeNode *root)
57{
58 if (root != NULL)
59 {
60 printf(" %d ", root->key);
61 preOrder(root->left);
62 preOrder(root->right);
63 }
64}
65int main()
66{
67 struct BinaryTreeNode *root = NULL;
68
69 root = insertNode(root, 50);
70 insertNode(root, 30);
71 insertNode(root, 20);
72 insertNode(root, 40);
73 insertNode(root, 70);
74 insertNode(root, 60);
75 insertNode(root, 80);
76 postOrder(root);
77 printf("\n");
78
79 preOrder(root);
80 printf("\n");
81
82 inOrder(root);
83 printf("\n");
84 return 0;
85}
QUEUE USING ARRAY:
1#include <stdio.h>//simpleq
2#include <stdlib.h>
3#define n 5
4int a[n];
5int f = -1;
6int r = -1;
7void enqueue(int e)
8{
9 if (r == n - 1)
10 {
11 printf("Q is full\n");
12 }
13 else
14 {
15 if (f == -1 && r == -1)
16 {
17 f = 0;
18 r = 0;
19 }
20 else
21 {
22 r++;
23 }
24 a[r] = e;
25 printf("inserted successfully\n");
26
27 }
28}
29
30void dequeue()
31{
32 if (f == -1 && r == -1)
33 {
34 printf("Q is empty\n");
35 }
36 else
37 {
38 if (f == r)
39 {
40 f = -1;
41 r = -1;
42 }
43 else
44 {
45 f++;
46 }
47 }
48}
49
50void display()
51{
52 if (f == -1 && r == -1)
53 {
54 printf("queue is empty\n");
55 }
56 else
57 {
58 printf("Queue:\n");
59 for (int i = f; i <= r; i++)
60 {
61 printf("%d\t", a[i]);
62 }
63 printf("\n");
64 }
65}
66
67int main()
68{
69 int ch, d;
70 while (1)
71 {
72 printf("1. enqueue operation\n");
73 printf("2. dequeue operation\n");
74 printf("3. Display queue\n");
75 printf("4. exit\n");
76 printf("enter your choice\n");
77 scanf("%d", &ch);
78 switch (ch)
79 {
80 case 1:
81 printf("enter the data\n");
82 scanf("%d", &d);
83 enqueue(d);
84 break;
85 case 2:
86 dequeue();
87 break;
88
89 case 3:
90 display();
91 break;
92
93 case 4:
94 exit(0);
95 break;
96
97 default:
98 printf("invalid operation\n");
99 }
100 }
101}
QUEUE USING LINKED LIST:
1#include <stdio.h>//q using linked list
2#include <stdlib.h>
3
4struct node
5{
6 struct node *next;
7 int data;
8};
9
10struct node *f, *r;
11
12void enqueue()
13{
14 int a;
15 printf("\nEnter the data value\n");
16 scanf("%d", &a);
17
18 struct node *nn = (struct node *)malloc(sizeof(struct node));
19 nn->data = a;
20 nn->next = NULL;
21
22 if (r == NULL)
23 {
24 f = nn;
25 r = nn;
26 }
27
28 else
29 {
30
31 r->next = nn;
32 r = nn;
33 }
34}
35
36void display()
37{
38 struct node *temp;
39 temp = f;
40 printf("\nThe Queue list is as:");
41
42 while (temp->next != NULL)
43 {
44 printf("\n%d", temp->data);
45 temp = temp->next;
46 }
47
48 printf("\n%d", temp->data);
49}
50
51void dequeue()
52{
53 if (f != NULL)
54 f = f->next;
55}
56
57void main()
58{
59
60 while (1)
61 {
62 int ch;
63
64 printf("\nMENU\n");
65 printf("1.enqueue\n");
66 printf("2.display\n");
67 printf("3.dequeue\n");
68 printf("4.exit\n");
69 printf("Enter choice:\n");
70 scanf("%d", &ch);
71
72 switch (ch)
73 {
74
75 case 1:
76 enqueue();
77 break;
78 case 2:
79 display();
80 break;
81 case 3:
82 dequeue();
83 break;
84 case 4:
85 exit(0);
86
87 default:
88 printf("Invalid\n");
89 }
90 }
91}
STACK:
1#include <stdio.h>
2
3#include <stdlib.h>
4
5#define SIZE 4
6
7int top = -1, inp_array[SIZE];
8void push();
9void pop();
10void show();
11
12int main()
13{
14 int choice;
15
16 while (1)
17 {
18 printf("\nPerform operations on the stack:");
19 printf("\n1.Push the element\n2.Pop the element\n3.Show\n4.End");
20 printf("\n\nEnter the choice: ");
21 scanf("%d", &choice);
22
23 switch (choice)
24 {
25 case 1:
26 push();
27 break;
28 case 2:
29 pop();
30 break;
31 case 3:
32 show();
33 break;
34 case 4:
35 exit(0);
36
37 default:
38 printf("\nInvalid choice!!");
39 }
40 }
41}
42
43void push()
44{
45 int x;
46
47 if (top == SIZE - 1)
48 {
49 printf("\nOverflow!!");
50 }
51 else
52 {
53 printf("\nEnter the element to be added onto the stack: ");
54 scanf("%d", &x);
55 top = top + 1;
56 inp_array[top] = x;
57 }
58}
59
60void pop()
61{
62 if (top == -1)
63 {
64 printf("\nUnderflow!!");
65 }
66 else
67 {
68 printf("\nPopped element: %d", inp_array[top]);
69 top = top - 1;
70 }
71}
72
73void show()
74{
75 if (top == -1)
76 {
77 printf("\nUnderflow!!");
78 }
79 else
80 {
81 printf("\nElements present in the stack: \n");
82 for (int i = top; i >= 0; --i)
83 printf("%d\n", inp_array[i]);
84 }
85}
STACK USING LINKED LIST:
1#include <stdio.h>
2#include <stdlib.h>
3
4// Define the structure of a node in the linked list
5struct Node {
6 int data;
7 struct Node* next;
8};
9
10// Function to create a new node
11struct Node* newNode(int data) {
12 struct Node* node = (struct Node*)malloc(sizeof(struct Node));
13 node->data = data;
14 node->next = NULL;
15 return node;
16}
17
18// Function to check if the stack is empty
19int isEmpty(struct Node* top) {
20 return top == NULL;
21}
22
23// Function to push an element onto the stack
24void push(struct Node** top, int data) {
25 struct Node* node = newNode(data);
26 node->next = *top;
27 *top = node;
28 printf("%d pushed to stack\n", data);
29}
30
31// Function to pop an element from the stack
32int pop(struct Node** top) {
33 if (isEmpty(*top)) {
34 printf("Stack underflow\n");
35 return -1;
36 }
37struct Node* temp = *top;
38 int popped = temp->data;
39 *top = (*top)->next;
40 free(temp);
41 return popped;
42}
43
44// Function to peek the top element of the stack
45int peek(struct Node* top) {
46 if (isEmpty(top)) {
47 printf("Stack is empty\n");
48 return -1;
49 }
50 return top->data;
51}
52
53// Function to display the stack
54void display(struct Node* top) {
55 if (isEmpty(top)) {
56 printf("Stack is empty\n");
57 return;
58 }
59 struct Node* temp = top;
60 printf("Stack elements: ");
61 while (temp != NULL) {
62 printf("%d ", temp->data);
63 temp = temp->next;
64 }
65 printf("\n");
66}
67int main() {
68 struct Node* stack = NULL; // Initialize the stack to NULL (empty stack)
69
70 // Testing stack operations
71 push(&stack, 10);
72 push(&stack, 20);
73 push(&stack, 30);
74 display(stack); // Expected output: 30 20 10
75
76 printf("Popped: %d\n", pop(&stack)); // Expected output: 30
77 display(stack); // Expected output: 20 10
78
79 printf("Top element: %d\n", peek(stack)); // Expected output: 20
80
81 pop(&stack); // Popping 20
82 pop(&stack); // Popping 10
83 pop(&stack); // Stack underflow
84
85 return 0;
86}
CIRCULAR QUEUE:
1#include <stdio.h>//circularq
2#include <stdlib.h>
3#define max 6
4int queue[max];
5int front = -1;
6int rear = -1;
7void enqueue(int element)
8{
9 if (front == -1 && rear == -1)
10 {
11 front = 0;
12 rear = 0;
13 queue[rear] = element;
14 }
15 else if ((rear + 1) % max == front)
16 {
17 printf("Queue is full");
18 }
19 else
20 {
21 rear = (rear + 1) % max;
22 queue[rear] = element;
23 }
24}
25int dequeue()
26{
27 if ((front == -1) && (rear == -1))
28 {
29 printf("\nQueue is empty");
30 }
31 else if (front == rear)
32 {
33 printf("\nThe dequeued element is %d", queue[front]);
34 front = -1;
35 rear = -1;
36 }
37 else
38 {
39 printf("\nThe dequeued element is %d", queue[front]);
40 front = (front + 1) % max;
41 }
42}
43void display()
44{
45 if (front == -1 && rear == -1)
46 {
47 printf("Queue is empty\n");
48 }
49 else
50 {
51 printf("Elements in the queue are: ");
52 int i = front;
53 while (1)
54 {
55 printf("%d ", queue[i]);
56 if (i == rear)
57 {
58 break;
59 }
60 i = (i + 1) % max;
61 }
62 printf("\n");
63 }
64}
65
66void main()
67{
68 int ch, x;
69
70 while (1)
71 {
72 printf("\n1.Enqueue");
73 printf("\n2.Dequeue");
74 printf("\n3.Display");
75 printf("\n4.Exit");
76 printf("\nEnter your choice:");
77 scanf("%d", &ch);
78 switch (ch)
79 {
80 case 1:
81 printf("Enter the data:\n");
82 scanf("%d", &x);
83 enqueue(x);
84 break;
85 case 2:
86 dequeue();
87 break;
88 case 3:
89 display();
90 break;
91 case 4:
92 exit(0);
93 break;
94 default:
95 printf("Invalid Operator");
96 }
97 }
98}
SINGLY LINKED LIST:
1#include <stdio.h>//linked list
2#include <stdlib.h>
3struct node
4{
5 int data;
6 struct node *next;
7};
8struct node *head = NULL;
9void insert(int value)
10{
11 struct node *nn = (struct node *)malloc(sizeof(struct node));
12 nn->data = value;
13 nn->next = NULL;
14 if (head == NULL)
15
16 head = nn;
17 else
18 {
19 struct node *current = head;
20 while (current->next != NULL)
21 {
22 current = current->next;
23 }
24 current->next = nn;
25 }
26}
27void delete(int value)
28{
29 if (head == NULL)
30 {
31 printf("empty list");
32 return;
33 }
34 else
35 {
36 struct node *current = head;
37 struct node *previous = NULL;
38 while (current != NULL)
39 {
40 if (current->data == value)
41 {
42 if (previous == NULL)
43 head = current->next;
44 else
45 previous->next = current->next;
46 free(current);
47 return;
48 }
49 previous = current;
50 current = current->next;
51 }
52 printf("element not found");
53 }
54}
55void traverse()
56{
57 struct node *current = head;
58 while (current != NULL)
59 {
60 printf("%d\t", current->data);
61 current = current->next;
62 }
63}
64
65void main()
66{
67
68 while (1)
69 {
70 int ch;
71
72 printf("\nMENU\n");
73 printf("1.insert\n");
74 printf("2.delete\n");
75 printf("3.traverse\n");
76 printf("4.exit\n");
77 printf("Enter choice:\n");
78 scanf("%d", &ch);
79
80 switch (ch)
81 {
82
83 case 1:
84 int d;
85 printf("enter the data value to be inserted");
86 scanf("%d", &d);
87 insert(d);
88 break;
89 case 2:
90 int a;
91 printf("enter the data value to be deleted");
92 scanf("%d", &a);
93 delete (a);
94 break;
95
96 case 3:
97 traverse();
98 break;
99 case 4:
100 exit(0);
101
102 default:
103 printf("Invalid\n");
104 }
105 }
106}
DOUBLY LINKED LIST:
1#include <stdio.h>//doubly linked list
2#include <stdlib.h>
3struct node
4{
5 struct node *prev;
6 struct node *next;
7
8 int data;
9};
10struct node *head;
11void insertion_beginning();
12void insertion_last();
13void deletion_beginning();
14void deletion_last();
15void display();
16void main()
17{
18 int choice = 0;
19 while (choice != 6)
20 {
21 printf("\nChoose one option from the following list ...\n");
22 printf("\n1.Insert in begining\n2.Insert at last\n3.Delete from Beginning\n4.Delete from last\n5.Show\n6.Exit\n");
23 printf("\nEnter your choice?\n");
24 scanf("\n%d", &choice);
25 switch (choice)
26 {
27 case 1:
28 insertion_beginning();
29 break;
30 case 2:
31 insertion_last();
32 break;
33 case 3:
34 deletion_beginning();
35 break;
36 case 4:
37 deletion_last();
38 break;
39 case 5:
40 display();
41 break;
42 case 6:
43 exit(0);
44 break;
45 default:
46 printf("Please enter valid choice..");
47 }
48 }
49}
50void insertion_beginning()
51{
52 struct node *ptr;
53 int item;
54 ptr = (struct node *)malloc(sizeof(struct node));
55 printf("\nEnter Item value");
56 scanf("%d", &item);
57
58 if (head == NULL)
59 {
60 ptr->next = NULL;
61 ptr->prev = NULL;
62 ptr->data = item;
63 head = ptr;
64 }
65 else
66 {
67 ptr->data = item;
68 ptr->prev = NULL;
69 ptr->next = head;
70 head->prev = ptr;
71 head = ptr;
72 }
73 printf("\nNode inserted\n");
74}
75
76void insertion_last()
77{
78 struct node *ptr, *temp;
79 int item;
80 ptr = (struct node *)malloc(sizeof(struct node));
81 printf("\nEnter value");
82 scanf("%d", &item);
83 ptr->data = item;
84 if (head == NULL)
85 {
86 ptr->next = NULL;
87 ptr->prev = NULL;
88 head = ptr;
89 }
90 else
91 {
92 temp = head;
93 while (temp->next != NULL)
94 {
95 temp = temp->next;
96 }
97 temp->next = ptr;
98 ptr->prev = temp;
99 ptr->next = NULL;
100 }
101
102 printf("\nnode inserted\n");
103}
104
105void deletion_beginning()
106{
107 struct node *ptr;
108 if (head == NULL)
109 {
110 printf("\n UNDERFLOW");
111 }
112 else if (head->next == NULL)
113 {
114 head = NULL;
115 free(head);
116 printf("\nnode deleted\n");
117 }
118 else
119 {
120 ptr = head;
121 head = head->next;
122 head->prev = NULL;
123 free(ptr);
124 printf("\nnode deleted\n");
125 }
126}
127void deletion_last()
128{
129 struct node *ptr;
130 if (head == NULL)
131 {
132 printf("\n UNDERFLOW");
133 }
134 else if (head->next == NULL)
135 {
136 head = NULL;
137 free(head);
138 printf("\nnode deleted\n");
139 }
140 else
141 {
142 ptr = head;
143 if (ptr->next != NULL)
144 {
145 ptr = ptr->next;
146 }
147 ptr->prev->next = NULL;
148 free(ptr);
149 printf("\nnode deleted\n");
150 }
151}
152void display()
153{
154 struct node *ptr;
155 printf("\n printing values...\n");
156 ptr = head;
157 while (ptr != NULL)
158 {
159 printf("%d\n", ptr->data);
160 ptr = ptr->next;
161 }
162}
BFS:
1#include <stdio.h>
2
3// creating queue data structure using arrays
4int queue[100];
5
6// defining pointers of the queue to perform pop and push
7int front = 0, back = 0;
8
9// defining push operation on the queue
10void push(int var)
11{
12 queue[back] = var;
13 back++;
14}
15
16// defining pop operation on queue
17void pop()
18{
19 queue[front] = 0;
20 front++;
21}
22
23// creating a visited array to keep the track of visited nodes
24int visited[7] = {0};
25
26int main()
27{
28 // defining the number of total persons
29 int N = 6;
30
31 // adjacenty matrix representing graph
32 int graph[6][6] = {{0, 1, 1, 0, 0, 0},
33 {1, 0, 1, 0, 0, 0},
34 {1, 1, 0, 1, 1, 0},
35 {0, 0, 1, 0, 0, 0},
36 {0, 0, 1, 0, 0, 1},
37 {0, 0, 0, 0, 1, 0}};
38
39 // front == back stands for empty queue
40 // until queue is not empty perfroming bfs
41
42 // adding a starting node in the list
43 push(1);
44 visited[0] = 1; // marking 1st node as visited
45 while (front != back)
46 {
47 int current = queue[front];
48
49 // printing current element
50 printf("%d ", current);
51
52 // popping the front element from the queue
53 pop();
54
55 for (int i = 0; i < 6; i++)
56 {
57 // adding non-visited connected nodes of the current node to the queue
58 if ((graph[current - 1][i] == 1) && (visited[i] == 0))
59 {
60 visited[i] = 1; // marking visisted
61 push(i + 1);
62 }
63 }
64 }
65 return 0;
66}
DFS:
1#include <stdio.h>
2
3#define MAX_VERTICES 100
4
5// Function to perform Depth-First Search (DFS) traversal
6void DFS(int graph[MAX_VERTICES][MAX_VERTICES], int visited[MAX_VERTICES], int vertices, int start) {
7 printf("%d ", start); // Print the current vertex
8 visited[start] = 1; // Mark the current vertex as visited
9
10 // Visit all adjacent vertices
11 for (int i = 0; i < vertices; i++) {
12 if (graph[start][i] == 1 && !visited[i]) {
13 DFS(graph, visited, vertices, i);
14 }
15 }
16}
17
18int main() {
19 int vertices, edges;
20
21 // Input the number of vertices
22 printf("Enter the number of vertices: ");
23 scanf("%d", &vertices);
24
25 if (vertices <= 0 || vertices > MAX_VERTICES) {
26 printf("Invalid number of vertices. Exiting...\n");
27 return 1;
28 }
29
30 int graph[MAX_VERTICES][MAX_VERTICES] = {0}; // Initialize the adjacency matrix with zeros
31 int visited[MAX_VERTICES] = {0}; // Initialize the visited array with zeros
32
33 // Input the number of edges
34 printf("Enter the number of edges: ");
35 scanf("%d", &edges);
36
37 if (edges < 0 || edges > vertices * (vertices - 1)) {
38 printf("Invalid number of edges. Exiting...\n");
39 return 1;
40 }
41
42 // Input edges and construct the adjacency matrix
43 for (int i = 0; i < edges; i++) {
44 int start, end;
45 printf("Enter edge %d (start end): ", i + 1);
46 scanf("%d %d", &start, &end);
47
48 // Validate input vertices
49 if (start < 0 || start >= vertices || end < 0 || end >= vertices) {
50 printf("Invalid vertices. Try again.\n");
51 i--;
52 continue;
53 }
54
55 graph[start][end] = 1;
56 // For undirected graph, uncomment the following line:
57 // graph[end][start] = 1;
58 }
59
60 // Input the starting vertex for DFS traversal
61 int startVertex;
62 printf("Enter the starting vertex for DFS traversal: ");
63 scanf("%d", &startVertex);
64
65 if (startVertex < 0 || startVertex >= vertices) {
66 printf("Invalid starting vertex. Exiting...\n");
67 return 1;
68 }
69
70 printf("DFS Traversal Order: ");
71 DFS(graph, visited, vertices, startVertex);
72
73 return 0;
74}