Top 50 Data Structure Programs

array-operations.c

                    // array-operations.c - Insert, delete, search, and traverse operations in an array
#include <stdio.h>
#define MAX_SIZE 100

void insert(int arr[], int *n, int pos, int val) {
    if (*n >= MAX_SIZE || pos < 0 || pos > *n) {
        printf("Insertion failed. Invalid position or array full.\n");
        return;
    }
    for (int i = *n; i > pos; i--)
        arr[i] = arr[i - 1];
    arr[pos] = val;
    (*n)++;
    printf("Inserted %d at position %d\n", val, pos);
}

void delete(int arr[], int *n, int pos) {
    if (*n <= 0 || pos < 0 || pos >= *n) {
        printf("Deletion failed. Invalid position or array empty.\n");
        return;
    }
    for (int i = pos; i < *n - 1; i++)
        arr[i] = arr[i + 1];
    (*n)--;
    printf("Deleted element at position %d\n", pos);
}

void search(int arr[], int n, int val) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == val) {
            printf("Element %d found at position %d\n", val, i);
            return;
        }
    }
    printf("Element %d not found\n", val);
}

void traverse(int arr[], int n) {
    printf("Array elements: ");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[MAX_SIZE], n = 0;
    int choice, pos, val;

    while (1) {
        printf("\nArray Operations:\n");
        printf("1. Insert\n2. Delete\n3. Search\n4. Traverse\n5. Exit\nEnter your choice: ");
        scanf("%d", &choice);

        switch (choice) {
            case 1:
                printf("Enter position and value to insert: ");
                scanf("%d %d", &pos, &val);
                insert(arr, &n, pos, val);
                break;
            case 2:
                printf("Enter position to delete: ");
                scanf("%d", &pos);
                delete(arr, &n, pos);
                break;
            case 3:
                printf("Enter value to search: ");
                scanf("%d", &val);
                search(arr, n, val);
                break;
            case 4:
                traverse(arr, n);
                break;
            case 5:
                return 0;
            default:
                printf("Invalid choice. Try again.\n");
        }
    }
}

Last Modified: January 13, 2025 06:36:21

merge-two-arrays.c

                    // merge-two-arrays.c - Merge two sorted arrays
#include <stdio.h>
#define MAX_SIZE 100

void mergeArrays(int arr1[], int n1, int arr2[], int n2, int merged[]) {
    int i = 0, j = 0, k = 0;
    while (i < n1 && j < n2) {
        if (arr1[i] < arr2[j])
            merged[k++] = arr1[i++];
        else
            merged[k++] = arr2[j++];
    }
    while (i < n1)
        merged[k++] = arr1[i++];
    while (j < n2)
        merged[k++] = arr2[j++];
}

int main() {
    int arr1[MAX_SIZE], arr2[MAX_SIZE], merged[2 * MAX_SIZE];
    int n1, n2;

    printf("Enter size of first array: ");
    scanf("%d", &n1);
    printf("Enter elements of first sorted array: ");
    for (int i = 0; i < n1; i++)
        scanf("%d", &arr1[i]);

    printf("Enter size of second array: ");
    scanf("%d", &n2);
    printf("Enter elements of second sorted array: ");
    for (int i = 0; i < n2; i++)
        scanf("%d", &arr2[i]);

    mergeArrays(arr1, n1, arr2, n2, merged);

    printf("Merged array: ");
    for (int i = 0; i < n1 + n2; i++)
        printf("%d ", merged[i]);
    printf("\n");

    return 0;
}

Last Modified: January 13, 2025 06:36:48

find-second-largest.c

                    // find-second-largest.c - Find the second largest element in an array
#include <stdio.h>
#define MAX_SIZE 100

int findSecondLargest(int arr[], int n) {
    if (n < 2) {
        printf("Array must have at least two elements.\n");
        return -1;
    }

    int largest = -1, secondLargest = -1;
    for (int i = 0; i < n; i++) {
        if (arr[i] > largest) {
            secondLargest = largest;
            largest = arr[i];
        } else if (arr[i] > secondLargest && arr[i] != largest) {
            secondLargest = arr[i];
        }
    }

    return secondLargest;
}

int main() {
    int arr[MAX_SIZE], n;

    printf("Enter size of array: ");
    scanf("%d", &n);
    printf("Enter elements of array: ");
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    int secondLargest = findSecondLargest(arr, n);
    if (secondLargest != -1)
        printf("Second largest element is: %d\n", secondLargest);

    return 0;
}

Last Modified: January 13, 2025 06:37:06

rotate-array.c

                    // rotate-array.c - Rotate an array to the left or right
#include <stdio.h>
#define MAX_SIZE 100

void rotateLeft(int arr[], int n, int d) {
    int temp[MAX_SIZE];
    d = d % n;
    for (int i = 0; i < n; i++)
        temp[i] = arr[(i + d) % n];
    for (int i = 0; i < n; i++)
        arr[i] = temp[i];
}

void rotateRight(int arr[], int n, int d) {
    rotateLeft(arr, n, n - d % n);
}

int main() {
    int arr[MAX_SIZE], n, d, choice;

    printf("Enter size of array: ");
    scanf("%d", &n);
    printf("Enter elements of array: ");
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    printf("Enter number of rotations: ");
    scanf("%d", &d);

    printf("Rotate: 1. Left  2. Right\nEnter your choice: ");
    scanf("%d", &choice);

    if (choice == 1) {
        rotateLeft(arr, n, d);
        printf("Array after left rotation: ");
    } else {
        rotateRight(arr, n, d);
        printf("Array after right rotation: ");
    }

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

    return 0;
}

Last Modified: January 13, 2025 06:37:25

find-missing-number.c

                    // find-missing-number.c - Find the missing number in a sequence
#include <stdio.h>

int findMissingNumber(int arr[], int n) {
    int total = (n + 1) * (n + 2) / 2;
    for (int i = 0; i < n; i++)
        total -= arr[i];
    return total;
}

int main() {
    int arr[MAX_SIZE], n;

    printf("Enter size of array (excluding missing number): ");
    scanf("%d", &n);
    printf("Enter elements of array: ");
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    printf("Missing number is: %d\n", findMissingNumber(arr, n));

    return 0;
}

Last Modified: January 13, 2025 06:37:52

string-reversal.c

                    // string-reversal.c - Reverse a string
#include <stdio.h>
#include <string.h>
#define MAX_SIZE 100

void reverseString(char str[]) {
    int n = strlen(str);
    for (int i = 0; i < n / 2; i++) {
        char temp = str[i];
        str[i] = str[n - i - 1];
        str[n - i - 1] = temp;
    }
}

int main() {
    char str[MAX_SIZE];

    printf("Enter a string: ");
    fgets(str, MAX_SIZE, stdin);
    str[strcspn(str, "\n")] = '\0'; // Remove newline character

    reverseString(str);
    printf("Reversed string: %s\n", str);

    return 0;
}

Last Modified: January 13, 2025 06:40:04

string-palindrome.c

                    // string-palindrome.c - Check if a string is a palindrome
#include <stdio.h>
#include <string.h>
#define MAX_SIZE 100

int isPalindrome(char str[]) {
    int n = strlen(str);
    for (int i = 0; i < n / 2; i++) {
        if (str[i] != str[n - i - 1])
            return 0;
    }
    return 1;
}

int main() {
    char str[MAX_SIZE];

    printf("Enter a string: ");
    fgets(str, MAX_SIZE, stdin);
    str[strcspn(str, "\n")] = '\0'; // Remove newline character

    if (isPalindrome(str))
        printf("The string is a palindrome.\n");
    else
        printf("The string is not a palindrome.\n");

    return 0;
}

Last Modified: January 13, 2025 06:40:20

substring-search.c

                    // substring-search.c - Find a substring in a string
#include <stdio.h>
#include <string.h>
#define MAX_SIZE 100

int substringSearch(char str[], char substr[]) {
    char *pos = strstr(str, substr);
    if (pos != NULL)
        return pos - str;
    return -1;
}

int main() {
    char str[MAX_SIZE], substr[MAX_SIZE];

    printf("Enter the main string: ");
    fgets(str, MAX_SIZE, stdin);
    str[strcspn(str, "\n")] = '\0'; // Remove newline character

    printf("Enter the substring: ");
    fgets(substr, MAX_SIZE, stdin);
    substr[strcspn(substr, "\n")] = '\0'; // Remove newline character

    int pos = substringSearch(str, substr);
    if (pos != -1)
        printf("Substring found at position %d\n", pos);
    else
        printf("Substring not found.\n");

    return 0;
}

Last Modified: January 13, 2025 06:40:39

string-permutations.c

                    // string-permutations.c - Generate all permutations of a string
#include <stdio.h>
#include <string.h>

void swap(char *x, char *y) {
    char temp = *x;
    *x = *y;
    *y = temp;
}

void generatePermutations(char str[], int start, int end) {
    if (start == end) {
        printf("%s\n", str);
        return;
    }

    for (int i = start; i <= end; i++) {
        swap(&str[start], &str[i]);
        generatePermutations(str, start + 1, end);
        swap(&str[start], &str[i]); // Backtrack
    }
}

int main() {
    char str[MAX_SIZE];

    printf("Enter a string: ");
    fgets(str, MAX_SIZE, stdin);
    str[strcspn(str, "\n")] = '\0'; // Remove newline character

    printf("Permutations of the string:\n");
    generatePermutations(str, 0, strlen(str) - 1);

    return 0;
}

Last Modified: January 13, 2025 06:40:56

character-frequency.c

                    // character-frequency.c - Count the frequency of each character in a string
#include <stdio.h>
#include <string.h>
#define MAX_SIZE 100
#define ASCII_SIZE 256

void countCharacterFrequency(char str[]) {
    int freq[ASCII_SIZE] = {0};

    for (int i = 0; str[i] != '\0'; i++)
        freq[(int)str[i]]++;

    printf("Character frequencies:\n");
    for (int i = 0; i < ASCII_SIZE; i++) {
        if (freq[i] > 0)
            printf("%c: %d\n", i, freq[i]);
    }
}

int main() {
    char str[MAX_SIZE];

    printf("Enter a string: ");
    fgets(str, MAX_SIZE, stdin);
    str[strcspn(str, "\n")] = '\0'; // Remove newline character

    countCharacterFrequency(str);

    return 0;
}

Last Modified: January 13, 2025 06:41:13

singly-linked-list.c

                    // Program to implement a singly linked list with basic operations (insert, delete, traverse)
#include <stdio.h>
#include <stdlib.h>

// Node structure for singly linked list
struct Node {
    int data;
    struct Node* next;
};

// Function to insert a new node at the end
void insert(struct Node** head, int data) {
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    struct Node* last = *head;
    new_node->data = data;
    new_node->next = NULL;

    // If the list is empty, make new node the head
    if (*head == NULL) {
        *head = new_node;
        return;
    }

    // Traverse to the last node and insert the new node
    while (last->next != NULL) {
        last = last->next;
    }
    last->next = new_node;
}

// Function to delete a node with specific data
void delete(struct Node** head, int data) {
    struct Node* temp = *head;
    struct Node* prev = NULL;

    // If the node to be deleted is the head node
    if (temp != NULL && temp->data == data) {
        *head = temp->next;
        free(temp);
        return;
    }

    // Search for the node to be deleted
    while (temp != NULL && temp->data != data) {
        prev = temp;
        temp = temp->next;
    }

    // If the data was not found
    if (temp == NULL) return;

    // Unlink the node from the list
    prev->next = temp->next;
    free(temp);
}

// Function to traverse the list
void traverse(struct Node* head) {
    struct Node* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

int main() {
    struct Node* head = NULL;
    
    insert(&head, 10);
    insert(&head, 20);
    insert(&head, 30);

    printf("List: ");
    traverse(head);

    delete(&head, 20);

    printf("After deletion: ");
    traverse(head);

    return 0;
}

Last Modified: January 13, 2025 06:45:51

doubly-linked-list.c

                    // Program to implement a doubly linked list with basic operations (insert, delete, traverse)
#include <stdio.h>
#include <stdlib.h>

// Node structure for doubly linked list
struct Node {
    int data;
    struct Node* prev;
    struct Node* next;
};

// Function to insert a new node at the end
void insert(struct Node** head, int data) {
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    struct Node* last = *head;
    new_node->data = data;
    new_node->next = NULL;

    if (*head == NULL) {
        new_node->prev = NULL;
        *head = new_node;
        return;
    }

    while (last->next != NULL) {
        last = last->next;
    }
    last->next = new_node;
    new_node->prev = last;
}

// Function to delete a node with specific data
void delete(struct Node** head, int data) {
    struct Node* temp = *head;

    // If the list is empty
    if (temp == NULL) return;

    // If the node to be deleted is the head node
    if (temp != NULL && temp->data == data) {
        *head = temp->next;
        if (*head != NULL) {
            (*head)->prev = NULL;
        }
        free(temp);
        return;
    }

    // Search for the node to be deleted
    while (temp != NULL && temp->data != data) {
        temp = temp->next;
    }

    if (temp == NULL) return;

    if (temp->next != NULL) {
        temp->next->prev = temp->prev;
    }

    if (temp->prev != NULL) {
        temp->prev->next = temp->next;
    }

    free(temp);
}

// Function to traverse the list
void traverse(struct Node* head) {
    struct Node* temp = head;
    while (temp != NULL) {
        printf("%d <-> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

int main() {
    struct Node* head = NULL;

    insert(&head, 10);
    insert(&head, 20);
    insert(&head, 30);

    printf("List: ");
    traverse(head);

    delete(&head, 20);

    printf("After deletion: ");
    traverse(head);

    return 0;
}

Last Modified: January 13, 2025 06:46:05

circular-linked-list.c

                    // Program to implement a circular linked list with basic operations (insert, delete, traverse)
#include <stdio.h>
#include <stdlib.h>

// Node structure for circular linked list
struct Node {
    int data;
    struct Node* next;
};

// Function to insert a new node at the end
void insert(struct Node** head, int data) {
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    struct Node* last = *head;
    new_node->data = data;

    if (*head == NULL) {
        new_node->next = new_node;
        *head = new_node;
        return;
    }

    while (last->next != *head) {
        last = last->next;
    }
    last->next = new_node;
    new_node->next = *head;
}

// Function to delete a node with specific data
void delete(struct Node** head, int data) {
    struct Node* temp = *head;
    struct Node* prev = NULL;

    // If the list is empty
    if (*head == NULL) return;

    // If the node to be deleted is the head node
    if (temp->data == data) {
        if (temp->next == *head) {
            free(temp);
            *head = NULL;
        } else {
            prev = *head;
            while (prev->next != *head) {
                prev = prev->next;
            }
            *head = temp->next;
            prev->next = *head;
            free(temp);
        }
        return;
    }

    // Search for the node to be deleted
    while (temp->next != *head && temp->data != data) {
        prev = temp;
        temp = temp->next;
    }

    if (temp == *head) return;

    prev->next = temp->next;
    free(temp);
}

// Function to traverse the list
void traverse(struct Node* head) {
    struct Node* temp = head;
    if (head == NULL) return;

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

int main() {
    struct Node* head = NULL;

    insert(&head, 10);
    insert(&head, 20);
    insert(&head, 30);

    printf("List: ");
    traverse(head);

    delete(&head, 20);

    printf("After deletion: ");
    traverse(head);

    return 0;
}

Last Modified: January 13, 2025 06:46:19

merge-two-linked-lists.c

                    // Program to merge two sorted linked lists
#include <stdio.h>
#include <stdlib.h>

// Node structure for linked list
struct Node {
    int data;
    struct Node* next;
};

// Function to insert a new node at the end
void insert(struct Node** head, int data) {
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    struct Node* last = *head;
    new_node->data = data;
    new_node->next = NULL;

    if (*head == NULL) {
        *head = new_node;
        return;
    }

    while (last->next != NULL) {
        last = last->next;
    }
    last->next = new_node;
}

// Function to merge two sorted linked lists
struct Node* merge(struct Node* list1, struct Node* list2) {
    struct Node* merged = NULL;
    struct Node** last_ptr = &merged;

    while (list1 != NULL && list2 != NULL) {
        if (list1->data < list2->data) {
            *last_ptr = list1;
            list1 = list1->next;
        } else {
            *last_ptr = list2;
            list2 = list2->next;
        }
        last_ptr = &((*last_ptr)->next);
    }

    if (list1 != NULL) {
        *last_ptr = list1;
    } else {
        *last_ptr = list2;
    }

    return merged;
}

// Function to traverse the list
void traverse(struct Node* head) {
    struct Node* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

int main() {
    struct Node* list1 = NULL;
    struct Node* list2 = NULL;
    struct Node* merged_list = NULL;

    insert(&list1, 1);
    insert(&list1, 3);
    insert(&list1, 5);

    insert(&list2, 2);
    insert(&list2, 4);
    insert(&list2, 6);

    printf("List 1: ");
    traverse(list1);
    printf("List 2: ");
    traverse(list2);

    merged_list = merge(list1, list2);
    printf("Merged List: ");
    traverse(merged_list);

    return 0;
}

Last Modified: January 13, 2025 06:46:38

detect-cycle-linked-list.c

                    // Program to detect a cycle in a linked list
#include <stdio.h>
#include <stdlib.h>

// Node structure for linked list
struct Node {
    int data;
    struct Node* next;
};

// Function to detect cycle in the linked list
int detectCycle(struct Node* head) {
    struct Node* slow = head;
    struct Node* fast = head;

    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;

        if (slow == fast) {
            return 1; // Cycle detected
        }
    }

    return 0; // No cycle
}

// Function to insert a new node at the end
void insert(struct Node** head, int data) {
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    struct Node* last = *head;
    new_node->data = data;
    new_node->next = NULL;

    if (*head == NULL) {
        *head = new_node;
        return;
    }

    while (last->next != NULL) {
        last = last->next;
    }
    last->next = new_node;
}

int main() {
    struct Node* head = NULL;

    insert(&head, 10);
    insert(&head, 20);
    insert(&head, 30);
    insert(&head, 40);
    
    // Creating a cycle for testing
    head->next->next->next->next = head->next;

    if (detectCycle(head)) {
        printf("Cycle detected in the list\n");
    } else {
        printf("No cycle in the list\n");
    }

    return 0;
}

Last Modified: January 13, 2025 06:46:54

stack-using-array.c

                    // Program to implement a stack using arrays
#include <stdio.h>
#include <stdlib.h>

#define MAX 10

struct Stack {
    int arr[MAX];
    int top;
};

// Function to initialize stack
void initStack(struct Stack* stack) {
    stack->top = -1;
}

// Function to check if the stack is full
int isFull(struct Stack* stack) {
    return stack->top == MAX - 1;
}

// Function to check if the stack is empty
int isEmpty(struct Stack* stack) {
    return stack->top == -1;
}

// Function to push an element onto the stack
void push(struct Stack* stack, int data) {
    if (isFull(stack)) {
        printf("Stack is full\n");
    } else {
        stack->arr[++stack->top] = data;
    }
}

// Function to pop an element from the stack
int pop(struct Stack* stack) {
    if (isEmpty(stack)) {
        printf("Stack is empty\n");
        return -1;
    } else {
        return stack->arr[stack->top--];
    }
}

// Function to peek the top element of the stack
int peek(struct Stack* stack) {
    if (isEmpty(stack)) {
        printf("Stack is empty\n");
        return -1;
    } else {
        return stack->arr[stack->top];
    }
}

int main() {
    struct Stack stack;
    initStack(&stack);

    push(&stack, 10);
    push(&stack, 20);
    push(&stack, 30);

    printf("Top element: %d\n", peek(&stack));
    printf("Popped element: %d\n", pop(&stack));
    printf("Top element after pop: %d\n", peek(&stack));

    return 0;
}

Last Modified: January 13, 2025 06:47:08

stack-using-linked-list.c

                    // Program to implement a stack using linked list
#include <stdio.h>
#include <stdlib.h>

// Node structure for stack
struct Node {
    int data;
    struct Node* next;
};

struct Stack {
    struct Node* top;
};

// Function to initialize stack
void initStack(struct Stack* stack) {
    stack->top = NULL;
}

// Function to check if the stack is empty
int isEmpty(struct Stack* stack) {
    return stack->top == NULL;
}

// Function to push an element onto the stack
void push(struct Stack* stack, int data) {
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node->data = data;
    new_node->next = stack->top;
    stack->top = new_node;
}

// Function to pop an element from the stack
int pop(struct Stack* stack) {
    if (isEmpty(stack)) {
        printf("Stack is empty\n");
        return -1;
    } else {
        struct Node* temp = stack->top;
        int popped_data = temp->data;
        stack->top = stack->top->next;
        free(temp);
        return popped_data;
    }
}

// Function to peek the top element of the stack
int peek(struct Stack* stack) {
    if (isEmpty(stack)) {
        printf("Stack is empty\n");
        return -1;
    } else {
        return stack->top->data;
    }
}

int main() {
    struct Stack stack;
    initStack(&stack);

    push(&stack, 10);
    push(&stack, 20);
    push(&stack, 30);

    printf("Top element: %d\n", peek(&stack));
    printf("Popped element: %d\n", pop(&stack));
    printf("Top element after pop: %d\n", peek(&stack));

    return 0;
}

Last Modified: January 13, 2025 06:47:24

stack-balanced-parentheses.c

                    // Program to check if parentheses are balanced in an expression
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Stack structure
struct Stack {
    char arr[100];
    int top;
};

// Function to initialize stack
void initStack(struct Stack* stack) {
    stack->top = -1;
}

// Function to push an element onto the stack
void push(struct Stack* stack, char ch) {
    stack->arr[++stack->top] = ch;
}

// Function to pop an element from the stack
char pop(struct Stack* stack) {
    return stack->arr[stack->top--];
}

// Function to check if the parentheses are balanced
int isBalanced(char* expr) {
    struct Stack stack;
    initStack(&stack);

    for (int i = 0; i < strlen(expr); i++) {
        char ch = expr[i];

        if (ch == '(') {
            push(&stack, ch);
        } else if (ch == ')') {
            if (stack.top == -1 || pop(&stack) != '(') {
                return 0; // Not balanced
            }
        }
    }

    return stack.top == -1; // If stack is empty, it's balanced
}

int main() {
    char expr[] = "(a + b) * (c + d)";

    if (isBalanced(expr)) {
        printf("The expression has balanced parentheses\n");
    } else {
        printf("The expression does not have balanced parentheses\n");
    }

    return 0;
}

Last Modified: January 13, 2025 06:47:53

infix-to-postfix.c

                    // Program to convert infix expression to postfix
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

// Stack structure
struct Stack {
    char arr[100];
    int top;
};

// Function to initialize stack
void initStack(struct Stack* stack) {
    stack->top = -1;
}

// Function to push an element onto the stack
void push(struct Stack* stack, char ch) {
    stack->arr[++stack->top] = ch;
}

// Function to pop an element from the stack
char pop(struct Stack* stack) {
    return stack->arr[stack->top--];
}

// Function to get precedence of operators
int precedence(char ch) {
    if (ch == '+' || ch == '-') return 1;
    if (ch == '*' || ch == '/') return 2;
    return 0;
}

// Function to convert infix to postfix
void infixToPostfix(char* infix, char* postfix) {
    struct Stack stack;
    initStack(&stack);
    int j = 0;

    for (int i = 0; i < strlen(infix); i++) {
        char ch = infix[i];

        if (isalnum(ch)) {
            postfix[j++] = ch;
        } else if (ch == '(') {
            push(&stack, ch);
        } else if (ch == ')') {
            while (stack.top != -1 && stack.arr[stack.top] != '(') {
                postfix[j++] = pop(&stack);
            }
            pop(&stack); // Pop '('
        } else {
            while (stack.top != -1 && precedence(stack.arr[stack.top]) >= precedence(ch)) {
                postfix[j++] = pop(&stack);
            }
            push(&stack, ch);
        }
    }

    while (stack.top != -1) {
        postfix[j++] = pop(&stack);
    }

    postfix[j] = '\0'; // Null terminate the postfix expression
}

int main() {
    char infix[] = "(a+b)*(c+d)";
    char postfix[100];

    infixToPostfix(infix, postfix);
    printf("Postfix expression: %s\n", postfix);

    return 0;
}

Last Modified: January 13, 2025 06:48:05

evaluate-postfix-expression.c

                    // Program to evaluate a postfix expression
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

// Stack structure
struct Stack {
    int arr[100];
    int top;
};

// Function to initialize stack
void initStack(struct Stack* stack) {
    stack->top = -1;
}

// Function to push an element onto the stack
void push(struct Stack* stack, int value) {
    stack->arr[++stack->top] = value;
}

// Function to pop an element from the stack
int pop(struct Stack* stack) {
    return stack->arr[stack->top--];
}

// Function to evaluate postfix expression
int evaluatePostfix(char* postfix) {
    struct Stack stack;
    initStack(&stack);

    for (int i = 0; i < strlen(postfix); i++) {
        char ch = postfix[i];

        if (isdigit(ch)) {
            push(&stack, ch - '0'); // Convert char to int and push onto stack
        } else {
            int operand2 = pop(&stack);
            int operand1 = pop(&stack);

            switch (ch) {
                case '+': push(&stack, operand1 + operand2); break;
                case '-': push(&stack, operand1 - operand2); break;
                case '*': push(&stack, operand1 * operand2); break;
                case '/': push(&stack, operand1 / operand2); break;
            }
        }
    }

    return pop(&stack);
}

int main() {
    char postfix[] = "23*5+";
    printf("Result of postfix evaluation: %d\n", evaluatePostfix(postfix));

    return 0;
}

Last Modified: January 13, 2025 06:48:18

queue-using-array.c

                    // Program to implement a queue using arrays
#include <stdio.h>
#include <stdlib.h>

#define MAX 10

struct Queue {
    int arr[MAX];
    int front, rear;
};

// Function to initialize the queue
void initQueue(struct Queue* queue) {
    queue->front = -1;
    queue->rear = -1;
}

// Function to check if the queue is full
int isFull(struct Queue* queue) {
    return queue->rear == MAX - 1;
}

// Function to check if the queue is empty
int isEmpty(struct Queue* queue) {
    return queue->front == -1;
}

// Function to enqueue an element
void enqueue(struct Queue* queue, int data) {
    if (isFull(queue)) {
        printf("Queue is full\n");
    } else {
        if (queue->front == -1) {
            queue->front = 0;
        }
        queue->arr[++queue->rear] = data;
    }
}

// Function to dequeue an element
int dequeue(struct Queue* queue) {
    if (isEmpty(queue)) {
        printf("Queue is empty\n");
        return -1;
    } else {
        int data = queue->arr[queue->front];
        if (queue->front == queue->rear) {
            queue->front = queue->rear = -1; // Reset the queue
        } else {
            queue->front++;
        }
        return data;
    }
}

// Function to display the queue
void display(struct Queue* queue) {
    if (isEmpty(queue)) {
        printf("Queue is empty\n");
    } else {
        for (int i = queue->front; i <= queue->rear; i++) {
            printf("%d ", queue->arr[i]);
        }
        printf("\n");
    }
}

int main() {
    struct Queue queue;
    initQueue(&queue);

    enqueue(&queue, 10);
    enqueue(&queue, 20);
    enqueue(&queue, 30);

    printf("Queue: ");
    display(&queue);

    printf("Dequeued: %d\n", dequeue(&queue));
    printf("Queue after dequeue: ");
    display(&queue);

    return 0;
}

Last Modified: January 13, 2025 06:49:14

queue-using-linked-list.c

                    // Program to implement a queue using linked list
#include <stdio.h>
#include <stdlib.h>

// Node structure for queue
struct Node {
    int data;
    struct Node* next;
};

struct Queue {
    struct Node* front;
    struct Node* rear;
};

// Function to initialize the queue
void initQueue(struct Queue* queue) {
    queue->front = queue->rear = NULL;
}

// Function to check if the queue is empty
int isEmpty(struct Queue* queue) {
    return queue->front == NULL;
}

// Function to enqueue an element
void enqueue(struct Queue* queue, int data) {
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node->data = data;
    new_node->next = NULL;

    if (isEmpty(queue)) {
        queue->front = queue->rear = new_node;
    } else {
        queue->rear->next = new_node;
        queue->rear = new_node;
    }
}

// Function to dequeue an element
int dequeue(struct Queue* queue) {
    if (isEmpty(queue)) {
        printf("Queue is empty\n");
        return -1;
    } else {
        int data = queue->front->data;
        struct Node* temp = queue->front;
        queue->front = queue->front->next;
        free(temp);
        return data;
    }
}

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

int main() {
    struct Queue queue;
    initQueue(&queue);

    enqueue(&queue, 10);
    enqueue(&queue, 20);
    enqueue(&queue, 30);

    printf("Queue: ");
    display(&queue);

    printf("Dequeued: %d\n", dequeue(&queue));
    printf("Queue after dequeue: ");
    display(&queue);

    return 0;
}

Last Modified: January 13, 2025 06:49:27

circular-queue.c

                    // Program to implement a circular queue
#include <stdio.h>
#include <stdlib.h>

#define MAX 10

struct Queue {
    int arr[MAX];
    int front, rear;
};

// Function to initialize the queue
void initQueue(struct Queue* queue) {
    queue->front = queue->rear = -1;
}

// Function to check if the queue is full
int isFull(struct Queue* queue) {
    return (queue->rear + 1) % MAX == queue->front;
}

// Function to check if the queue is empty
int isEmpty(struct Queue* queue) {
    return queue->front == -1;
}

// Function to enqueue an element
void enqueue(struct Queue* queue, int data) {
    if (isFull(queue)) {
        printf("Queue is full\n");
    } else {
        if (queue->front == -1) {
            queue->front = 0;
        }
        queue->rear = (queue->rear + 1) % MAX;
        queue->arr[queue->rear] = data;
    }
}

// Function to dequeue an element
int dequeue(struct Queue* queue) {
    if (isEmpty(queue)) {
        printf("Queue is empty\n");
        return -1;
    } else {
        int data = queue->arr[queue->front];
        if (queue->front == queue->rear) {
            queue->front = queue->rear = -1; // Reset the queue
        } else {
            queue->front = (queue->front + 1) % MAX;
        }
        return data;
    }
}

// Function to display the queue
void display(struct Queue* queue) {
    if (isEmpty(queue)) {
        printf("Queue is empty\n");
    } else {
        int i = queue->front;
        while (i != queue->rear) {
            printf("%d ", queue->arr[i]);
            i = (i + 1) % MAX;
        }
        printf("%d\n", queue->arr[queue->rear]);
    }
}

int main() {
    struct Queue queue;
    initQueue(&queue);

    enqueue(&queue, 10);
    enqueue(&queue, 20);
    enqueue(&queue, 30);

    printf("Queue: ");
    display(&queue);

    printf("Dequeued: %d\n", dequeue(&queue));
    printf("Queue after dequeue: ");
    display(&queue);

    return 0;
}

Last Modified: January 13, 2025 06:49:46

priority-queue.c

                    // Program to implement a priority queue
#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    int priority;
    struct Node* next;
};

struct PriorityQueue {
    struct Node* front;
};

// Function to initialize the priority queue
void initQueue(struct PriorityQueue* pq) {
    pq->front = NULL;
}

// Function to check if the priority queue is empty
int isEmpty(struct PriorityQueue* pq) {
    return pq->front == NULL;
}

// Function to enqueue an element with priority
void enqueue(struct PriorityQueue* pq, int data, int priority) {
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node->data = data;
    new_node->priority = priority;
    new_node->next = NULL;

    if (isEmpty(pq) || pq->front->priority < priority) {
        new_node->next = pq->front;
        pq->front = new_node;
    } else {
        struct Node* temp = pq->front;
        while (temp->next != NULL && temp->next->priority >= priority) {
            temp = temp->next;
        }
        new_node->next = temp->next;
        temp->next = new_node;
    }
}

// Function to dequeue an element
int dequeue(struct PriorityQueue* pq) {
    if (isEmpty(pq)) {
        printf("Priority queue is empty\n");
        return -1;
    } else {
        struct Node* temp = pq->front;
        int data = temp->data;
        pq->front = pq->front->next;
        free(temp);
        return data;
    }
}

// Function to display the priority queue
void display(struct PriorityQueue* pq) {
    if (isEmpty(pq)) {
        printf("Priority queue is empty\n");
    } else {
        struct Node* temp = pq->front;
        while (temp != NULL) {
            printf("%d(%d) ", temp->data, temp->priority);
            temp = temp->next;
        }
        printf("\n");
    }
}

int main() {
    struct PriorityQueue pq;
    initQueue(&pq);

    enqueue(&pq, 10, 2);
    enqueue(&pq, 20, 1);
    enqueue(&pq, 30, 3);

    printf("Priority Queue: ");
    display(&pq);

    printf("Dequeued: %d\n", dequeue(&pq));
    printf("Priority Queue after dequeue: ");
    display(&pq);

    return 0;
}

Last Modified: January 13, 2025 06:50:11

deque-implementation.c

                    // Program to implement a double-ended queue (Deque)
#include <stdio.h>
#include <stdlib.h>

#define MAX 10

struct Deque {
    int arr[MAX];
    int front, rear;
};

// Function to initialize the deque
void initDeque(struct Deque* deque) {
    deque->front = deque->rear = -1;
}

// Function to check if the deque is full
int isFull(struct Deque* deque) {
    return (deque->front == 0 && deque->rear == MAX - 1) || (deque->rear == deque->front - 1);
}

// Function to check if the deque is empty
int isEmpty(struct Deque* deque) {
    return deque->front == -1;
}

// Function to add an element at the front
void insertFront(struct Deque* deque, int data) {
    if (isFull(deque)) {
        printf("Deque is full\n");
    } else {
        if (deque->front == -1) {
            deque->front = deque->rear = 0;
        } else if (deque->front == 0) {
            deque->front = MAX - 1;
        } else {
            deque->front--;
        }
        deque->arr[deque->front] = data;
    }
}

// Function to add an element at the rear
void insertRear(struct Deque* deque, int data) {
    if (isFull(deque)) {
        printf("Deque is full\n");
    } else {
        if (deque->front == -1) {
            deque->front = deque->rear = 0;
        } else if (deque->rear == MAX - 1) {
            deque->rear = 0;
        } else {
            deque->rear++;
        }
        deque->arr[deque->rear] = data;
    }
}

// Function to delete an element from the front
int deleteFront(struct Deque* deque) {
    if (isEmpty(deque)) {
        printf("Deque is empty\n");
        return -1;
    } else {
        int data = deque->arr[deque->front];
        if (deque->front == deque->rear) {
            deque->front = deque->rear = -1; // Reset the deque
        } else if (deque->front == MAX - 1) {
            deque->front = 0;
        } else {
            deque->front++;
        }
        return data;
    }
}

// Function to delete an element from the rear
int deleteRear(struct Deque* deque) {
    if (isEmpty(deque)) {
        printf("Deque is empty\n");
        return -1;
    } else {
        int data = deque->arr[deque->rear];
        if (deque->front == deque->rear) {
            deque->front = deque->rear = -1; // Reset the deque
        } else if (deque->rear == 0) {
            deque->rear = MAX - 1;
        } else {
            deque->rear--;
        }
        return data;
    }
}

// Function to display the deque
void display(struct Deque* deque) {
    if (isEmpty(deque)) {
        printf("Deque is empty\n");
    } else {
        int i = deque->front;
        while (i != deque->rear) {
            printf("%d ", deque->arr[i]);
            i = (i + 1) % MAX;
        }
        printf("%d\n", deque->arr[deque->rear]);
    }
}

int main() {
    struct Deque deque;
    initDeque(&deque);

    insertRear(&deque, 10);
    insertRear(&deque, 20);
    insertFront(&deque, 30);

    printf("Deque: ");
    display(&deque);

    printf("Deleted from front: %d\n", deleteFront(&deque));
    printf("Deque after deletion from front: ");
    display(&deque);

    printf("Deleted from rear: %d\n", deleteRear(&deque));
    printf("Deque after deletion from rear: ");
    display(&deque);

    return 0;
}

Last Modified: January 13, 2025 06:50:27

binary-tree-traversal.c

                    // Program for preorder, inorder, and postorder traversal of a binary tree
#include <stdio.h>
#include <stdlib.h>

// Binary tree node
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// Function to create a new node
struct Node* newNode(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->left = node->right = NULL;
    return node;
}

// Preorder traversal (Root, Left, Right)
void preorder(struct Node* root) {
    if (root != NULL) {
        printf("%d ", root->data);
        preorder(root->left);
        preorder(root->right);
    }
}

// Inorder traversal (Left, Root, Right)
void inorder(struct Node* root) {
    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->data);
        inorder(root->right);
    }
}

// Postorder traversal (Left, Right, Root)
void postorder(struct Node* root) {
    if (root != NULL) {
        postorder(root->left);
        postorder(root->right);
        printf("%d ", root->data);
    }
}

int main() {
    // Example tree
    struct Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);

    printf("Preorder traversal: ");
    preorder(root);
    printf("\n");

    printf("Inorder traversal: ");
    inorder(root);
    printf("\n");

    printf("Postorder traversal: ");
    postorder(root);
    printf("\n");

    return 0;
}

Last Modified: January 13, 2025 06:50:42

binary-search-tree.c

                    // Program to implement a binary search tree (BST)
#include <stdio.h>
#include <stdlib.h>

// Binary tree node
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// Function to create a new node
struct Node* newNode(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->left = node->right = NULL;
    return node;
}

// Function to insert a node in the BST
struct Node* insert(struct Node* root, int data) {
    if (root == NULL) {
        return newNode(data);
    }

    if (data < root->data) {
        root->left = insert(root->left, data);
    } else if (data > root->data) {
        root->right = insert(root->right, data);
    }

    return root;
}

// Function to search for a value in the BST
struct Node* search(struct Node* root, int data) {
    if (root == NULL || root->data == data) {
        return root;
    }

    if (data < root->data) {
        return search(root->left, data);
    }

    return search(root->right, data);
}

int main() {
    struct Node* root = NULL;
    root = insert(root, 10);
    insert(root, 20);
    insert(root, 5);

    struct Node* found = search(root, 10);
    if (found) {
        printf("Node found with data: %d\n", found->data);
    } else {
        printf("Node not found\n");
    }

    return 0;
}

Last Modified: January 13, 2025 06:50:56

lowest-common-ancestor.c

                    // Program to find the lowest common ancestor (LCA) in a binary search tree
#include <stdio.h>
#include <stdlib.h>

// Binary tree node
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// Function to create a new node
struct Node* newNode(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->left = node->right = NULL;
    return node;
}

// Function to find the LCA of two nodes in a BST
struct Node* findLCA(struct Node* root, int n1, int n2) {
    if (root == NULL) return NULL;

    // If both nodes are smaller than root, LCA lies in the left subtree
    if (root->data > n1 && root->data > n2) {
        return findLCA(root->left, n1, n2);
    }

    // If both nodes are greater than root, LCA lies in the right subtree
    if (root->data < n1 && root->data < n2) {
        return findLCA(root->right, n1, n2);
    }

    return root;
}

int main() {
    struct Node* root = newNode(20);
    root->left = newNode(10);
    root->right = newNode(30);
    root->left->left = newNode(5);
    root->left->right = newNode(15);

    struct Node* lca = findLCA(root, 5, 15);
    if (lca) {
        printf("Lowest Common Ancestor: %d\n", lca->data);
    } else {
        printf("LCA not found\n");
    }

    return 0;
}

Last Modified: January 13, 2025 06:51:09

height-of-tree.c

                    // Program to calculate the height of a binary tree
#include <stdio.h>
#include <stdlib.h>

// Binary tree node
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// Function to create a new node
struct Node* newNode(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->left = node->right = NULL;
    return node;
}

// Function to calculate the height of a binary tree
int height(struct Node* root) {
    if (root == NULL) {
        return 0;
    }

    int leftHeight = height(root->left);
    int rightHeight = height(root->right);

    return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}

int main() {
    struct Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);

    printf("Height of tree: %d\n", height(root));

    return 0;
}

Last Modified: January 13, 2025 06:51:22

level-order-traversal.c

                    // Program for level-order traversal of a binary tree
#include <stdio.h>
#include <stdlib.h>

// Binary tree node
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// Function to create a new node
struct Node* newNode(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->left = node->right = NULL;
    return node;
}

// Queue structure for level-order traversal
struct Queue {
    struct Node* arr[100];
    int front, rear;
};

// Function to initialize the queue
void initQueue(struct Queue* queue) {
    queue->front = queue->rear = -1;
}

// Function to check if the queue is empty
int isEmpty(struct Queue* queue) {
    return queue->front == -1;
}

// Function to enqueue an element
void enqueue(struct Queue* queue, struct Node* node) {
    if (queue->rear == 99) {
        printf("Queue is full\n");
    } else {
        if (queue->front == -1) {
            queue->front = 0;
        }
        queue->arr[++queue->rear] = node;
    }
}

// Function to dequeue an element
struct Node* dequeue(struct Queue* queue) {
    if (isEmpty(queue)) {
        printf("Queue is empty\n");
        return NULL;
    } else {
        struct Node* node = queue->arr[queue->front];
        if (queue->front == queue->rear) {
            queue->front = queue->rear = -1;
        } else {
            queue->front++;
        }
        return node;
    }
}

// Function for level-order traversal
void levelOrder(struct Node* root) {
    if (root == NULL) return;

    struct Queue queue;
    initQueue(&queue);

    enqueue(&queue, root);

    while (!isEmpty(&queue)) {
        struct Node* node = dequeue(&queue);
        printf("%d ", node->data);

        if (node->left) enqueue(&queue, node->left);
        if (node->right) enqueue(&queue, node->right);
    }
}

int main() {
    struct Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);

    printf("Level-order traversal: ");
    levelOrder(root);
    printf("\n");

    return 0;
}

Last Modified: January 13, 2025 06:51:34

min-heap.c

                    // Program to implement a Min-Heap
#include <stdio.h>
#include <stdlib.h>

#define MAX 100

// Min-Heap structure
struct MinHeap {
    int arr[MAX];
    int size;
};

// Function to initialize the Min-Heap
void initMinHeap(struct MinHeap* heap) {
    heap->size = 0;
}

// Function to get the parent index of a node
int parent(int i) {
    return (i - 1) / 2;
}

// Function to get the left child index of a node
int leftChild(int i) {
    return 2 * i + 1;
}

// Function to get the right child index of a node
int rightChild(int i) {
    return 2 * i + 2;
}

// Function to heapify the Min-Heap
void heapify(struct MinHeap* heap, int i) {
    int left = leftChild(i);
    int right = rightChild(i);
    int smallest = i;

    if (left < heap->size && heap->arr[left] < heap->arr[smallest]) {
        smallest = left;
    }
    if (right < heap->size && heap->arr[right] < heap->arr[smallest]) {
        smallest = right;
    }
    if (smallest != i) {
        int temp = heap->arr[i];
        heap->arr[i] = heap->arr[smallest];
        heap->arr[smallest] = temp;
        heapify(heap, smallest);
    }
}

// Function to insert a new element in the Min-Heap
void insert(struct MinHeap* heap, int key) {
    if (heap->size == MAX) {
        printf("Heap is full\n");
        return;
    }
    heap->size++;
    heap->arr[heap->size - 1] = key;

    // Fix the min-heap property
    int i = heap->size - 1;
    while (i != 0 && heap->arr[parent(i)] > heap->arr[i]) {
        int temp = heap->arr[i];
        heap->arr[i] = heap->arr[parent(i)];
        heap->arr[parent(i)] = temp;
        i = parent(i);
    }
}

// Function to extract the minimum element
int extractMin(struct MinHeap* heap) {
    if (heap->size <= 0) {
        return -1;
    }
    if (heap->size == 1) {
        heap->size--;
        return heap->arr[0];
    }

    // Store the minimum value and replace the root with the last element
    int root = heap->arr[0];
    heap->arr[0] = heap->arr[heap->size - 1];
    heap->size--;
    heapify(heap, 0);

    return root;
}

// Function to print the Min-Heap
void printMinHeap(struct MinHeap* heap) {
    for (int i = 0; i < heap->size; i++) {
        printf("%d ", heap->arr[i]);
    }
    printf("\n");
}

int main() {
    struct MinHeap heap;
    initMinHeap(&heap);

    insert(&heap, 3);
    insert(&heap, 2);
    insert(&heap, 15);

    printf("Min-Heap: ");
    printMinHeap(&heap);

    printf("Extracted Min: %d\n", extractMin(&heap));
    printf("Min-Heap after extraction: ");
    printMinHeap(&heap);

    return 0;
}

Last Modified: January 13, 2025 07:03:39

max-heap.c

                    // Program to implement a Max-Heap
#include <stdio.h>
#include <stdlib.h>

#define MAX 100

// Max-Heap structure
struct MaxHeap {
    int arr[MAX];
    int size;
};

// Function to initialize the Max-Heap
void initMaxHeap(struct MaxHeap* heap) {
    heap->size = 0;
}

// Function to get the parent index of a node
int parent(int i) {
    return (i - 1) / 2;
}

// Function to get the left child index of a node
int leftChild(int i) {
    return 2 * i + 1;
}

// Function to get the right child index of a node
int rightChild(int i) {
    return 2 * i + 2;
}

// Function to heapify the Max-Heap
void heapify(struct MaxHeap* heap, int i) {
    int left = leftChild(i);
    int right = rightChild(i);
    int largest = i;

    if (left < heap->size && heap->arr[left] > heap->arr[largest]) {
        largest = left;
    }
    if (right < heap->size && heap->arr[right] > heap->arr[largest]) {
        largest = right;
    }
    if (largest != i) {
        int temp = heap->arr[i];
        heap->arr[i] = heap->arr[largest];
        heap->arr[largest] = temp;
        heapify(heap, largest);
    }
}

// Function to insert a new element in the Max-Heap
void insert(struct MaxHeap* heap, int key) {
    if (heap->size == MAX) {
        printf("Heap is full\n");
        return;
    }
    heap->size++;
    heap->arr[heap->size - 1] = key;

    // Fix the max-heap property
    int i = heap->size - 1;
    while (i != 0 && heap->arr[parent(i)] < heap->arr[i]) {
        int temp = heap->arr[i];
        heap->arr[i] = heap->arr[parent(i)];
        heap->arr[parent(i)] = temp;
        i = parent(i);
    }
}

// Function to extract the maximum element
int extractMax(struct MaxHeap* heap) {
    if (heap->size <= 0) {
        return -1;
    }
    if (heap->size == 1) {
        heap->size--;
        return heap->arr[0];
    }

    // Store the maximum value and replace the root with the last element
    int root = heap->arr[0];
    heap->arr[0] = heap->arr[heap->size - 1];
    heap->size--;
    heapify(heap, 0);

    return root;
}

// Function to print the Max-Heap
void printMaxHeap(struct MaxHeap* heap) {
    for (int i = 0; i < heap->size; i++) {
        printf("%d ", heap->arr[i]);
    }
    printf("\n");
}

int main() {
    struct MaxHeap heap;
    initMaxHeap(&heap);

    insert(&heap, 3);
    insert(&heap, 2);
    insert(&heap, 15);

    printf("Max-Heap: ");
    printMaxHeap(&heap);

    printf("Extracted Max: %d\n", extractMax(&heap));
    printf("Max-Heap after extraction: ");
    printMaxHeap(&heap);

    return 0;
}

Last Modified: January 13, 2025 07:03:55

heap-sort.c

                    // Program to perform Heap Sort
#include <stdio.h>
#include <stdlib.h>

#define MAX 100

// Function to swap two elements
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Function to heapify a subtree rooted at index i
void heapify(int arr[], int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }

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

// Function to perform heap sort
void heapSort(int arr[], int n) {
    // Build a max-heap
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }

    // Extract elements one by one from the heap
    for (int i = n - 1; i >= 0; i--) {
        swap(&arr[0], &arr[i]);
        heapify(arr, i, 0);
    }
}

// Function to print an array
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    heapSort(arr, n);

    printf("Sorted array: ");
    printArray(arr, n);

    return 0;
}

Last Modified: January 13, 2025 07:04:09

kth-largest-element.c

                    // Program to find the kth largest element using a heap
#include <stdio.h>
#include <stdlib.h>

#define MAX 100

// Function to heapify a subtree rooted at index i
void heapify(int arr[], int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }

    if (largest != i) {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        heapify(arr, n, largest);
    }
}

// Function to find the kth largest element
int kthLargest(int arr[], int n, int k) {
    // Build a max-heap
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }

    // Extract max k times
    for (int i = n - 1; i >= n - k; i--) {
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        heapify(arr, i, 0);
    }

    return arr[n - k];
}

int main() {
    int arr[] = {12, 3, 5, 7, 19};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 2;

    printf("The %dth largest element is %d\n", k, kthLargest(arr, n, k));

    return 0;
}

Last Modified: January 13, 2025 07:04:24

merge-k-sorted-arrays.c

                    // Program to merge k sorted arrays using a heap
#include <stdio.h>
#include <stdlib.h>

#define MAX 100

// A structure to store a heap node
struct HeapNode {
    int val;
    int row;
    int col;
};

// Min-Heap to store the heap nodes
struct MinHeap {
    struct HeapNode arr[MAX];
    int size;
};

// Function to initialize the Min-Heap
void initMinHeap(struct MinHeap* heap) {
    heap->size = 0;
}

// Function to swap two elements
void swap(struct HeapNode* a, struct HeapNode* b) {
    struct HeapNode temp = *a;
    *a = *b;
    *b = temp;
}

// Function to heapify the Min-Heap
void heapify(struct MinHeap* heap, int i) {
    int smallest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < heap->size && heap->arr[left].val < heap->arr[smallest].val) {
        smallest = left;
    }
    if (right < heap->size && heap->arr[right].val < heap->arr[smallest].val) {
        smallest = right;
    }
    if (smallest != i) {
        swap(&heap->arr[i], &heap->arr[smallest]);
        heapify(heap, smallest);
    }
}

// Function to insert a new element into the heap
void insert(struct MinHeap* heap, struct HeapNode node) {
    if (heap->size == MAX) {
        return;
    }
    heap->arr[heap->size] = node;
    int i = heap->size;
    heap->size++;

    while (i != 0 && heap->arr[(i - 1) / 2].val > heap->arr[i].val) {
        swap(&heap->arr[i], &heap->arr[(i - 1) / 2]);
        i = (i - 1) / 2;
    }
}

// Function to extract the minimum element
struct HeapNode extractMin(struct MinHeap* heap) {
    struct HeapNode root = heap->arr[0];
    heap->arr[0] = heap->arr[heap->size - 1];
    heap->size--;
    heapify(heap, 0);
    return root;
}

// Function to merge k sorted arrays using a Min-Heap
void mergeKSortedArrays(int arr[][MAX], int n, int k) {
    struct MinHeap heap;
    initMinHeap(&heap);

    // Insert the first element of each array into the heap
    for (int i = 0; i < k; i++) {
        struct HeapNode node = {arr[i][0], i, 0};
        insert(&heap, node);
    }

    // Extract the minimum element and insert the next element from the same array
    while (heap.size > 0) {
        struct HeapNode node = extractMin(&heap);
        printf("%d ", node.val);

        if (node.col + 1 < n) {
            struct HeapNode newNode = {arr[node.row][node.col + 1], node.row, node.col + 1};
            insert(&heap, newNode);
        }
    }
}

int main() {
    int arr[3][5] = {{1, 4, 7, 8, 10},
                     {2, 5, 8, 9, 11},
                     {3, 6, 9, 10, 12}};
    int k = 3;
    int n = 5;

    printf("Merged array: ");
    mergeKSortedArrays(arr, n, k);
    printf("\n");

    return 0;
}

Last Modified: January 13, 2025 07:04:46

graph-representation.c

                    // Program to represent a graph using adjacency matrix and adjacency list
#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 5

// Graph using adjacency matrix
struct GraphMatrix {
    int adjMatrix[MAX_VERTICES][MAX_VERTICES];
};

// Graph using adjacency list
struct GraphList {
    struct Node* adjList[MAX_VERTICES];
};

// Node for adjacency list
struct Node {
    int data;
    struct Node* next;
};

// Function to create a new adjacency list node
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// Function to add an edge to adjacency matrix
void addEdgeMatrix(struct GraphMatrix* graph, int u, int v) {
    graph->adjMatrix[u][v] = 1;
    graph->adjMatrix[v][u] = 1;
}

// Function to add an edge to adjacency list
void addEdgeList(struct GraphList* graph, int u, int v) {
    struct Node* newNode = createNode(v);
    newNode->next = graph->adjList[u];
    graph->adjList[u] = newNode;

    newNode = createNode(u);
    newNode->next = graph->adjList[v];
    graph->adjList[v] = newNode;
}

// Function to print the adjacency matrix
void printGraphMatrix(struct GraphMatrix* graph) {
    for (int i = 0; i < MAX_VERTICES; i++) {
        for (int j = 0; j < MAX_VERTICES; j++) {
            printf("%d ", graph->adjMatrix[i][j]);
        }
        printf("\n");
    }
}

// Function to print the adjacency list
void printGraphList(struct GraphList* graph) {
    for (int i = 0; i < MAX_VERTICES; i++) {
        struct Node* temp = graph->adjList[i];
        printf("Vertex %d: ", i);
        while (temp != NULL) {
            printf("%d ", temp->data);
            temp = temp->next;
        }
        printf("\n");
    }
}

int main() {
    struct GraphMatrix graphMatrix;
    struct GraphList graphList;

    // Initialize graph
    for (int i = 0; i < MAX_VERTICES; i++) {
        for (int j = 0; j < MAX_VERTICES; j++) {
            graphMatrix.adjMatrix[i][j] = 0;
        }
        graphList.adjList[i] = NULL;
    }

    // Add edges
    addEdgeMatrix(&graphMatrix, 0, 1);
    addEdgeMatrix(&graphMatrix, 0, 2);
    addEdgeList(&graphList, 0, 1);
    addEdgeList(&graphList, 0, 2);

    // Print graph
    printf("Adjacency Matrix:\n");
    printGraphMatrix(&graphMatrix);

    printf("Adjacency List:\n");
    printGraphList(&graphList);

    return 0;
}

Last Modified: January 13, 2025 07:05:16

dfs-traversal.c

                    // Program to perform Depth First Search (DFS) traversal of a graph
#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 5

// Graph representation using adjacency list
struct Graph {
    struct Node* adjList[MAX_VERTICES];
};

// Node for adjacency list
struct Node {
    int data;
    struct Node* next;
};

// Function to create a new adjacency list node
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// Function to add an edge to the graph
void addEdge(struct Graph* graph, int u, int v) {
    struct Node* newNode = createNode(v);
    newNode->next = graph->adjList[u];
    graph->adjList[u] = newNode;

    newNode = createNode(u);
    newNode->next = graph->adjList[v];
    graph->adjList[v] = newNode;
}

// DFS function
void dfs(struct Graph* graph, int visited[], int vertex) {
    printf("%d ", vertex);
    visited[vertex] = 1;

    struct Node* temp = graph->adjList[vertex];
    while (temp != NULL) {
        int adjacent = temp->data;
        if (!visited[adjacent]) {
            dfs(graph, visited, adjacent);
        }
        temp = temp->next;
    }
}

int main() {
    struct Graph graph;
    for (int i = 0; i < MAX_VERTICES; i++) {
        graph.adjList[i] = NULL;
    }

    // Add edges
    addEdge(&graph, 0, 1);
    addEdge(&graph, 0, 2);
    addEdge(&graph, 1, 3);
    addEdge(&graph, 2, 3);
    addEdge(&graph, 3, 4);

    int visited[MAX_VERTICES] = {0};
    printf("DFS Traversal: ");
    dfs(&graph, visited, 0);

    return 0;
}

Last Modified: January 13, 2025 07:05:29

bfs-traversal.c

                    // Program to perform Breadth First Search (BFS) traversal of a graph
#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 5

// Graph representation using adjacency list
struct Graph {
    struct Node* adjList[MAX_VERTICES];
};

// Node for adjacency list
struct Node {
    int data;
    struct Node* next;
};

// Function to create a new adjacency list node
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// Function to add an edge to the graph
void addEdge(struct Graph* graph, int u, int v) {
    struct Node* newNode = createNode(v);
    newNode->next = graph->adjList[u];
    graph->adjList[u] = newNode;

    newNode = createNode(u);
    newNode->next = graph->adjList[v];
    graph->adjList[v] = newNode;
}

// BFS function
void bfs(struct Graph* graph, int start) {
    int visited[MAX_VERTICES] = {0};
    int queue[MAX_VERTICES];
    int front = 0, rear = -1;

    visited[start] = 1;
    queue[++rear] = start;

    while (front <= rear) {
        int vertex = queue[front++];
        printf("%d ", vertex);

        struct Node* temp = graph->adjList[vertex];
        while (temp != NULL) {
            int adjacent = temp->data;
            if (!visited[adjacent]) {
                visited[adjacent] = 1;
                queue[++rear] = adjacent;
            }
            temp = temp->next;
        }
    }
}

int main() {
    struct Graph graph;
    for (int i = 0; i < MAX_VERTICES; i++) {
        graph.adjList[i] = NULL;
    }

    // Add edges
    addEdge(&graph, 0, 1);
    addEdge(&graph, 0, 2);
    addEdge(&graph, 1, 3);
    addEdge(&graph, 2, 3);
    addEdge(&graph, 3, 4);

    printf("BFS Traversal starting from vertex 0: ");
    bfs(&graph, 0);

    return 0;
}

Last Modified: January 13, 2025 07:05:41

dijkstra-algorithm.c

                    // Program to find the shortest path using Dijkstra's algorithm
#include <stdio.h>
#include <limits.h>

#define V 5

// Function to find the vertex with the minimum distance value
int minDistance(int dist[], int sptSet[]) {
    int min = INT_MAX, minIndex;
    for (int v = 0; v < V; v++) {
        if (!sptSet[v] && dist[v] <= min) {
            min = dist[v];
            minIndex = v;
        }
    }
    return minIndex;
}

// Dijkstra's algorithm
void dijkstra(int graph[V][V], int src) {
    int dist[V];
    int sptSet[V];  // Shortest Path Tree Set

    for (int i = 0; i < V; i++) {
        dist[i] = INT_MAX;
        sptSet[i] = 0;
    }

    dist[src] = 0;

    for (int count = 0; count < V - 1; count++) {
        int u = minDistance(dist, sptSet);
        sptSet[u] = 1;

        for (int v = 0; v < V; v++) {
            if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }

    printf("Vertex Distance from Source (%d)\n", src);
    for (int i = 0; i < V; i++) {
        printf("%d \t\t %d\n", i, dist[i]);
    }
}

int main() {
    int graph[V][V] = {{0, 10, 0, 0, 20},
                       {10, 0, 50, 0, 0},
                       {0, 50, 0, 10, 0},
                       {0, 0, 10, 0, 5},
                       {20, 0, 0, 5, 0}};

    dijkstra(graph, 0);

    return 0;
}

Last Modified: January 13, 2025 07:05:55

kruskal-algorithm.c

                    // Program to find the Minimum Spanning Tree using Kruskal's algorithm
#include <stdio.h>
#include <stdlib.h>

#define V 4
#define E 5

// Edge structure for Kruskal's algorithm
struct Edge {
    int u, v, weight;
};

// Subset structure for Union-Find
struct Subset {
    int parent;
    int rank;
};

// Function to find the subset of an element
int find(struct Subset subsets[], int i) {
    if (subsets[i].parent != i) {
        subsets[i].parent = find(subsets, subsets[i].parent);
    }
    return subsets[i].parent;
}

// Function to do union of two subsets
void unionSets(struct Subset subsets[], int x, int y) {
    int rootX = find(subsets, x);
    int rootY = find(subsets, y);

    if (subsets[rootX].rank < subsets[rootY].rank) {
        subsets[rootX].parent = rootY;
    } else if (subsets[rootX].rank > subsets[rootY].rank) {
        subsets[rootY].parent = rootX;
    } else {
        subsets[rootY].parent = rootX;
        subsets[rootX].rank++;
    }
}

// Function to compare edges (used for sorting)
int compare(const void* a, const void* b) {
    return ((struct Edge*)a)->weight - ((struct Edge*)b)->weight;
}

// Kruskal's algorithm to find MST
void kruskal(struct Edge edges[], int V) {
    struct Subset* subsets = (struct Subset*)malloc(V * sizeof(struct Subset));

    // Sort edges by weight
    qsort(edges, E, sizeof(edges[0]), compare);

    // Initialize subsets
    for (int i = 0; i < V; i++) {
        subsets[i].parent = i;
        subsets[i].rank = 0;
    }

    // Construct MST
    printf("Edges in MST:\n");
    for (int i = 0; i < E; i++) {
        int x = find(subsets, edges[i].u);
        int y = find(subsets, edges[i].v);

        if (x != y) {
            printf("%d-%d (%d)\n", edges[i].u, edges[i].v, edges[i].weight);
            unionSets(subsets, x, y);
        }
    }

    free(subsets);
}

int main() {
    struct Edge edges[] = {{0, 1, 10}, {0, 3, 20}, {1, 2, 30}, {2, 3, 40}, {1, 3, 50}};
    kruskal(edges, V);
    return 0;
}

Last Modified: January 13, 2025 07:06:10

hash-table.c

                    // Program to implement a hash table with linear probing
#include <stdio.h>
#include <stdlib.h>

#define TABLE_SIZE 10

// Hash table structure
struct HashTable {
    int* table;
};

// Hash function
int hash(int key) {
    return key % TABLE_SIZE;
}

// Function to initialize the hash table
void initTable(struct HashTable* ht) {
    ht->table = (int*)malloc(TABLE_SIZE * sizeof(int));
    for (int i = 0; i < TABLE_SIZE; i++) {
        ht->table[i] = -1;  // -1 represents an empty slot
    }
}

// Function to insert an element using linear probing
void insert(struct HashTable* ht, int key) {
    int index = hash(key);
    while (ht->table[index] != -1) {
        index = (index + 1) % TABLE_SIZE;  // Linear probing
    }
    ht->table[index] = key;
}

// Function to search for an element
int search(struct HashTable* ht, int key) {
    int index = hash(key);
    while (ht->table[index] != -1) {
        if (ht->table[index] == key) {
            return index;  // Found
        }
        index = (index + 1) % TABLE_SIZE;  // Linear probing
    }
    return -1;  // Not found
}

// Function to display the hash table
void display(struct HashTable* ht) {
    for (int i = 0; i < TABLE_SIZE; i++) {
        if (ht->table[i] != -1) {
            printf("Index %d: %d\n", i, ht->table[i]);
        } else {
            printf("Index %d: (empty)\n", i);
        }
    }
}

int main() {
    struct HashTable ht;
    initTable(&ht);

    insert(&ht, 10);
    insert(&ht, 20);
    insert(&ht, 30);
    insert(&ht, 40);
    insert(&ht, 50);

    display(&ht);

    int key = 20;
    int index = search(&ht, key);
    if (index != -1) {
        printf("Element %d found at index %d\n", key, index);
    } else {
        printf("Element %d not found\n", key);
    }

    return 0;
}

Last Modified: January 13, 2025 07:07:32

chaining-hashing.c

                    // Program to implement separate chaining for collision resolution in hashing
#include <stdio.h>
#include <stdlib.h>

// Linked list node for separate chaining
struct Node {
    int data;
    struct Node* next;
};

// Hash table structure
struct HashTable {
    struct Node** table;
    int size;
};

// Hash function
int hash(int key, int size) {
    return key % size;
}

// Function to create a new node
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// Function to initialize the hash table
void initTable(struct HashTable* ht, int size) {
    ht->size = size;
    ht->table = (struct Node**)malloc(size * sizeof(struct Node*));
    for (int i = 0; i < size; i++) {
        ht->table[i] = NULL;
    }
}

// Function to insert an element
void insert(struct HashTable* ht, int key) {
    int index = hash(key, ht->size);
    struct Node* newNode = createNode(key);
    newNode->next = ht->table[index];
    ht->table[index] = newNode;
}

// Function to search for an element
int search(struct HashTable* ht, int key) {
    int index = hash(key, ht->size);
    struct Node* temp = ht->table[index];
    while (temp != NULL) {
        if (temp->data == key) {
            return 1;  // Found
        }
        temp = temp->next;
    }
    return 0;  // Not found
}

// Function to display the hash table
void display(struct HashTable* ht) {
    for (int i = 0; i < ht->size; i++) {
        struct Node* temp = ht->table[i];
        printf("Index %d: ", i);
        while (temp != NULL) {
            printf("%d -> ", temp->data);
            temp = temp->next;
        }
        printf("NULL\n");
    }
}

int main() {
    struct HashTable ht;
    initTable(&ht, 10);

    insert(&ht, 10);
    insert(&ht, 20);
    insert(&ht, 30);
    insert(&ht, 40);
    insert(&ht, 50);

    display(&ht);

    int key = 20;
    if (search(&ht, key)) {
        printf("Element %d found in the hash table.\n", key);
    } else {
        printf("Element %d not found in the hash table.\n", key);
    }

    return 0;
}

Last Modified: January 13, 2025 07:07:43

check-anagram.c

                    // Program to check if two strings are anagrams using hashing
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX_CHAR 256

// Function to check if two strings are anagrams
int areAnagrams(char* str1, char* str2) {
    int count[MAX_CHAR] = {0};

    if (strlen(str1) != strlen(str2)) {
        return 0;
    }

    for (int i = 0; i < strlen(str1); i++) {
        count[str1[i]]++;
        count[str2[i]]--;
    }

    for (int i = 0; i < MAX_CHAR; i++) {
        if (count[i] != 0) {
            return 0; // Not anagrams
        }
    }
    return 1; // Anagrams
}

int main() {
    char str1[] = "listen";
    char str2[] = "silent";

    if (areAnagrams(str1, str2)) {
        printf("The strings are anagrams.\n");
    } else {
        printf("The strings are not anagrams.\n");
    }

    return 0;
}

Last Modified: January 13, 2025 07:08:25

count-distinct-elements.c

                    // Program to count distinct elements in an array using hashing
#include <stdio.h>
#include <stdlib.h>

// Function to count distinct elements
int countDistinct(int arr[], int n) {
    int* hashTable = (int*)calloc(n, sizeof(int));
    int count = 0;

    for (int i = 0; i < n; i++) {
        if (hashTable[arr[i]] == 0) {
            hashTable[arr[i]] = 1;
            count++;
        }
    }

    free(hashTable);
    return count;
}

int main() {
    int arr[] = {10, 20, 20, 10, 30, 40};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Number of distinct elements: %d\n", countDistinct(arr, n));

    return 0;
}

Last Modified: January 13, 2025 07:08:42

subarray-with-sum.c

                    // Program to find a subarray with a given sum using hashing
#include <stdio.h>
#include <stdlib.h>
#include <unordered_map>

int subArrayWithSum(int arr[], int n, int sum) {
    std::unordered_map<int, int> hashMap;
    int currentSum = 0;

    for (int i = 0; i < n; i++) {
        currentSum += arr[i];
        
        if (currentSum == sum) {
            return 1;  // Subarray found
        }

        if (hashMap.find(currentSum - sum) != hashMap.end()) {
            return 1;  // Subarray found
        }

        hashMap[currentSum] = i;
    }

    return 0;  // No subarray found
}

int main() {
    int arr[] = {1, 4, 20, 3, 10, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int sum = 33;

    if (subArrayWithSum(arr, n, sum)) {
        printf("Subarray with given sum found.\n");
    } else {
        printf("Subarray with given sum not found.\n");
    }

    return 0;
}

Last Modified: January 13, 2025 07:08:54

tower-of-hanoi.c

                    // Program to solve the Tower of Hanoi problem
#include <stdio.h>

// Function to solve Tower of Hanoi
void towerOfHanoi(int n, char from, char to, char aux) {
    if (n == 1) {
        printf("Move disk 1 from %c to %c\n", from, to);
        return;
    }
    towerOfHanoi(n - 1, from, aux, to);
    printf("Move disk %d from %c to %c\n", n, from, to);
    towerOfHanoi(n - 1, aux, to, from);
}

int main() {
    int n = 3;  // Number of disks
    towerOfHanoi(n, 'A', 'C', 'B');
    return 0;
}

Last Modified: January 13, 2025 07:09:11

job-scheduling.c

                    // Program to solve the job scheduling problem using greedy techniques
#include <stdio.h>
#include <stdlib.h>

// Job structure
struct Job {
    int id;
    int deadline;
    int profit;
};

// Comparator function for sorting jobs by profit
int compare(const void* a, const void* b) {
    return ((struct Job*)b)->profit - ((struct Job*)a)->profit;
}

// Function to find the maximum profit from job scheduling
void jobScheduling(struct Job jobs[], int n) {
    qsort(jobs, n, sizeof(jobs[0]), compare);

    int result[n];
    bool slot[n];
    for (int i = 0; i < n; i++) {
        slot[i] = false;
    }

    for (int i = 0; i < n; i++) {
        for (int j = jobs[i].deadline - 1; j >= 0; j--) {
            if (!slot[j]) {
                result[j] = i;
                slot[j] = true;
                break;
            }
        }
    }

    int totalProfit = 0;
    for (int i = 0; i < n; i++) {
        if (slot[i]) {
            totalProfit += jobs[result[i]].profit;
        }
    }

    printf("Total profit from job scheduling: %d\n", totalProfit);
}

int main() {
    struct Job jobs[] = {{1, 4, 50}, {2, 1, 60}, {3, 1, 20}, {4, 1, 30}};
    int n = sizeof(jobs) / sizeof(jobs[0]);

    jobScheduling(jobs, n);

    return 0;
}

Last Modified: January 13, 2025 07:09:25

knapsack-problem.c

                    // Program to solve the 0/1 Knapsack problem using dynamic programming
#include <stdio.h>

int knapsack(int W, int wt[], int val[], int n) {
    int dp[n + 1][W + 1];

    for (int i = 0; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            if (i == 0 || w == 0) {
                dp[i][w] = 0;
            } else if (wt[i - 1] <= w) {
                dp[i][w] = (val[i - 1] + dp[i - 1][w - wt[i - 1]] > dp[i - 1][w]) ? 
                            val[i - 1] + dp[i - 1][w - wt[i - 1]] : dp[i - 1][w];
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }

    return dp[n][W];
}

int main() {
    int val[] = {60, 100, 120};
    int wt[] = {10, 20, 30};
    int W = 50;
    int n = sizeof(val) / sizeof(val[0]);

    printf("Maximum value in knapsack: %d\n", knapsack(W, wt, val, n));
    return 0;
}

Last Modified: January 13, 2025 07:09:41

longest-common-subsequence.c

                    // Program to find the longest common subsequence
#include <stdio.h>
#include <string.h>

int lcs(char* X, char* Y, int m, int n) {
    int dp[m + 1][n + 1];

    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0 || j == 0) {
                dp[i][j] = 0;
            } else if (X[i - 1] == Y[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = (dp[i - 1][j] > dp[i][j - 1]) ? dp[i - 1][j] : dp[i][j - 1];
            }
        }
    }

    return dp[m][n];
}

int main() {
    char X[] = "AGGTAB";
    char Y[] = "GXTXAYB";
    int m = strlen(X);
    int n = strlen(Y);

    printf("Length of LCS: %d\n", lcs(X, Y, m, n));
    return 0;
}

Last Modified: January 13, 2025 07:09:54

trie-implementation.c

                    // Program to implement a Trie for storing strings
#include <stdio.h>
#include <stdlib.h>

#define ALPHABET_SIZE 26

// Trie node structure
struct TrieNode {
    struct TrieNode* children[ALPHABET_SIZE];
    int isEndOfWord;
};

// Function to create a new Trie node
struct TrieNode* createNode() {
    struct TrieNode* newNode = (struct TrieNode*)malloc(sizeof(struct TrieNode));
    newNode->isEndOfWord = 0;
    for (int i = 0; i < ALPHABET_SIZE; i++) {
        newNode->children[i] = NULL;
    }
    return newNode;
}

// Function to insert a word into the Trie
void insert(struct TrieNode* root, char* word) {
    struct TrieNode* node = root;
    for (int i = 0; word[i] != '\0'; i++) {
        int index = word[i] - 'a';
        if (node->children[index] == NULL) {
            node->children[index] = createNode();
        }
        node = node->children[index];
    }
    node->isEndOfWord = 1;
}

// Function to search for a word in the Trie
int search(struct TrieNode* root, char* word) {
    struct TrieNode* node = root;
    for (int i = 0; word[i] != '\0'; i++) {
        int index = word[i] - 'a';
        if (node->children[index] == NULL) {
            return 0; // Word not found
        }
        node = node->children[index];
    }
    return node->isEndOfWord;
}

int main() {
    struct TrieNode* root = createNode();

    insert(root, "hello");
    insert(root, "world");

    if (search(root, "hello")) {
        printf("Word 'hello' found in Trie.\n");
    } else {
        printf("Word 'hello' not found in Trie.\n");
    }

    if (search(root, "world")) {
        printf("Word 'world' found in Trie.\n");
    } else {
        printf("Word 'world' not found in Trie.\n");
    }

    return 0;
}

Last Modified: January 13, 2025 07:10:09