C Data Structures: Code Examples & Algorithms

Posted on Feb 27, 2025 in Computer Engineering

Binary Tree Traversal in C

This code demonstrates binary tree traversal using C.

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

struct node { int data; struct node left; struct node right; };

struct node *root = NULL;

struct node create() { struct node ptr, *ptr1; int x, a;

ptr = (struct node*)malloc(sizeof(struct node));
if (ptr == NULL) {
    printf("Memory Full");
    return NULL; // Important: Return NULL on memory allocation failure
}
printf("\nEnter the data for the current node: ");
scanf("%d", &x);
ptr->data = x;

printf("\nDo you want to create a left child of the current node %d? (0 for no, 1 for yes): ", x);
scanf("%d", &a);

if (a == 0 || a == 1) {
    ptr->left = create();
} else {
    ptr->left = NULL;
}

printf("\nDo you want to create a right child of the current node %d? (0 for no, 1 for yes): ", x);
scanf("%d", &a);
if (a == 0 || a == 1) {
    ptr->right = create(); // No need to create ptr1, reuse create()
} else {
    ptr->right = NULL;
}
return ptr;

}

void Pre_Order(struct node *nd) { // LNR if (nd == NULL) { return; } printf("%d ", nd->data); Pre_Order(nd->left); Pre_Order(nd->right); }

void In_Order(struct node *nd) { //LNR if (nd == NULL) { return; } In_Order(nd->left); //L printf("%d ", nd->data); //N In_Order(nd->right); //R }

void Post_Order(struct node *nd) { //LRN if (nd == NULL) { return; } Post_Order(nd->left); //L Post_Order(nd->right); //R printf("%d ", nd->data); //N }

int main() { struct node* ptr; //char x, a = 'A'; // Unnecessary variables

ptr = create(); // Binary Tree Creation

printf("\nThe Pre Order is: ");
Pre_Order(ptr);

printf("\nThe In Order is: ");
In_Order(ptr);

printf("\nThe Post Order is: ");
Post_Order(ptr);

return 0;

}

Check if a Linked List is a Palindrome

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

struct Node { char data; struct Node* next; };

void reverse(struct Node* head); bool isPalindrome(struct Node head);

void reverse(struct Node* head) { struct Node prev = NULL; struct Node current = head; struct Node* next = NULL; // Initialize next to NULL

while (current != NULL) {
    next = current->next;
    current->next = prev;
    prev = current;
    current = next;
}
*head = prev;

}

bool isPalindrome(struct Node head) { struct Node slow = head, fast = head, mid = NULL, prevSlow = head, secondHalf;

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

if (fast != NULL) {
    mid = slow;
    slow = slow->next;
}

secondHalf = slow;
prevSlow->next = NULL; // Separate the first half
reverse(&secondHalf); // Reverse the second half

struct Node* temp1 = head;
struct Node* temp2 = secondHalf;
 bool result = true; // Initialize result

while (temp1 != NULL && temp2 != NULL) {
    if (temp1->data != temp2->data) {
        result = false; // Set result to false if mismatch found
        break;
    }
    temp1 = temp1->next;
    temp2 = temp2->next;
}


reverse(&secondHalf); // Restore the second half

if (mid != NULL) {
    prevSlow->next = mid;
    mid->next = secondHalf;
} else {
    prevSlow->next = secondHalf; // Reconnect the list
}

return result;

}

void printList(struct Node* ptr) { while (ptr != NULL) { printf("%c->", ptr->data); ptr = ptr->next; } printf("NULL\n"); }

int main() { // Creating a linked list for the palindrome "level" struct Node head = NULL; char palindrome[] = "level"; for (int i = 0; palindrome[i] != '\0'; i++) { struct Node newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = palindrome[i]; newNode->next = head; head = newNode; } printf("Linked List: "); printList(head); isPalindrome(head) ? printf("Is Palindrome\n\n") : printf("Not Palindrome\n\n"); return 0; }

Delete N Nodes After M Nodes in Doubly Linked List

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

struct Node { int data; struct Node next; struct Node prev; };

void deleteNAfterM(struct Node* head_ref, int m, int n) { if (head_ref == NULL) return; // Handle empty list

struct Node *current = *head_ref, *temp;
int i;

// Traverse to the mth node
for (i = 1; i < m && current != NULL; ++i) {
    current = current->next;
}

if (current == NULL) return; // Not enough nodes


// Delete n nodes after m nodes
 temp = current->next; // Start deleting from the next node
for (i = 0; i < n && temp != NULL; i++) {
    struct Node *next_node = temp->next;
    free(temp);
    temp = next_node;
}

 current->next = temp; //connect

if (temp != NULL) {
    temp->prev = current; // Connect previous if not the end
}

}

Replace Element with Next Greatest Element

#include <stdio.h>

void replaceWithNextGreatest(int arr[], int n) { if (n <= 0) return; // Handle empty or single-element array

// Initialize max_element with the last element
int max_element = arr[n - 1];
arr[n-1] = -1; // Replace last element

// Iterate in reverse order
for (int i = n - 2; i >= 0; --i) {
    // Store current element
    int temp = arr[i];
    // Replace the current element with max_element
    arr[i] = max_element;
    // If the current element is greater than max_element, update max_element
    if (temp > max_element) {
        max_element = temp;
    }
}

}

int main() { int arr[] = {4, 5, 2, 10, 8}; int n = sizeof(arr) / sizeof(arr[0]); replaceWithNextGreatest(arr, n); printf("Modified array: "); for (int i = 0; i < n; ++i) { printf("%d ", arr[i]); } return 0; }

Sort Elements by Frequency (Decreasing Order)

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

// Structure to represent an element and its frequency struct Element { int value; int frequency; };

// Custom comparator function for sorting elements int compare(const void a, const void b) { int freqDiff = ((struct Element)b)->frequency - ((struct Element)a)->frequency; if (freqDiff == 0) { return ((struct Element)a)->value - ((struct Element)b)->value; // If frequencies are equal, sort by value } return freqDiff; }

// Function to sort elements by their frequency in decreasing order void sortByFrequency(int arr[], int n) { // Create a frequency map struct Element freqMap[n]; int freqMapIndex = 0; int i,j;

// Populate the frequency map
for (i = 0; i < n; ++i) {
    for (j = 0; j < freqMapIndex; ++j) {
        if (freqMap[j].value == arr[i]) {
            freqMap[j].frequency++;
            break;
        }
    }
    if (j == freqMapIndex) {
        freqMap[freqMapIndex].value = arr[i];
        freqMap[freqMapIndex].frequency = 1;
        freqMapIndex++;
    }
}

// Sort the array using the custom comparator
qsort(freqMap, freqMapIndex, sizeof(struct Element), compare);

// Modify the original array based on the sorted frequencies
int index = 0;
for (i = 0; i < freqMapIndex; ++i) {
    for (j = 0; j < freqMap[i].frequency; ++j) {
        arr[index++] = freqMap[i].value;
    }
}

}

int main() { int arr[] = {4, 4, 2, 8, 3, 3, 1, 1, 1, 8, 8, 8}; int n = sizeof(arr) / sizeof(arr[0]);

sortByFrequency(arr, n);

printf("Sorted array by frequency: ");
for (int i = 0; i < n; ++i) {
    printf("%d ", arr[i]);
}
return 0;

}

Interchange Kth and K+1st Elements

#include <stdio.h>

void interchangeElements(int arr[], int n, int k) { // Check if Kth and K+1st elements are within bounds if (k < 0 || k + 1 >= n) { printf("Invalid indices\n"); return; }

// Interchange without swapping values
int temp = arr[k];
arr[k] = arr[k+1];
arr[k+1] = temp;

}

int main() { // Example usage int arr[] = {1, 2, 3, 4, 5}; int n = sizeof(arr) / sizeof(arr[0]); int k = 2; // Replace with your desired K value

interchangeElements(arr, n, k);

// Display the modified array
printf("Modified Array: ");
for (int i = 0; i < n; i++) {
    printf("%d ", arr[i]);
}

return 0;

}

Reverse String using Queue (Recursive)

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

// Structure for a queue node struct QueueNode { char data; struct QueueNode* next; };

// Structure for a queue struct Queue { struct QueueNode front; struct QueueNode rear; };

// Function to create a new queue node struct QueueNode createQueueNode(char data) { struct QueueNode newNode = (struct QueueNode*)malloc(sizeof(struct QueueNode)); if (newNode == NULL) { // Handle memory allocation failure printf("Memory allocation failed\n"); exit(1); } newNode->data = data; newNode->next = NULL; return newNode; }

// Function to initialize a queue struct Queue createQueue() { struct Queue queue = (struct Queue*)malloc(sizeof(struct Queue)); if (queue == NULL) { // Handle memory allocation failure printf("Memory allocation failed\n"); exit(1); } queue->front = NULL; queue->rear = NULL; return queue; }

// Function to enqueue a character into the queue void enqueue(struct Queue queue, char data) { struct QueueNode newNode = createQueueNode(data); if (queue->rear == NULL) { queue->front = newNode; queue->rear = newNode; } else { queue->rear->next = newNode; queue->rear = newNode; } }

// Function to dequeue a character from the queue char dequeue(struct Queue queue) { if (queue->front == NULL) { printf("Queue is empty\n"); exit(1); } char data = queue->front->data; struct QueueNode temp = queue->front; queue->front = queue->front->next; if (queue->front == NULL) { queue->rear = NULL; } free(temp); return data; }

// Recursive function to display the string in reverse order void displayStringReverse(struct Queue* queue) { if (queue->front != NULL) { char character = dequeue(queue); displayStringReverse(queue); // Recursive call printf("%c", character); } }

int main() { // Example usage struct Queue* queue = createQueue(); char inputString[] = "Hello, World!";

// Enqueue each character of the string into the queue
for (int i = 0; inputString[i] != '\0'; i++) {
    enqueue(queue, inputString[i]);
}

// Display the string in reverse order
printf("Reversed String: ");
displayStringReverse(queue);
printf("\n");
return 0;

}

Check Balanced Parentheses in Postfix

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

define bool int

// Structure of a stack node struct sNode { char data; struct sNode* next; };

// Function to push an item to stack void push(struct sNode** top_ref, char new_data);

// Function to pop an item from stack char pop(struct sNode** top_ref);

// Returns 1 if character1 and character2 are matching left and right Brackets bool isMatchingPair(char character1, char character2) { return (character1 == '(' && character2 == ')') || (character1 == '{' && character2 == '}') || (character1 == '[' && character2 == ']'); }

// Return 1 if expression has balanced Brackets bool areBracketsBalanced(char exp[]) { int i = 0; struct sNode* stack = NULL;

while (exp[i]) {
    if (exp[i] == '{' || exp[i] == '(' || exp[i] == '[')
        push(&stack, exp[i]);
    else if (exp[i] == '}' || exp[i] == ')' || exp[i] == ']') {
        if (stack == NULL || !isMatchingPair(pop(&stack), exp[i]))
            return 0;
    }
    i++;
}
return stack == NULL;

}

// Driver code int main() { char exp[100] = "{()}[]";

if (areBracketsBalanced(exp))
    printf("Balanced \n");
else
    printf("Not Balanced \n");
return 0;

}

// Function to push an item to stack void push(struct sNode* top_ref, char new_data) { struct sNode new_node = (struct sNode*)malloc(sizeof(struct sNode));

if (new_node == NULL) {
    printf("Stack overflow\n");
    exit(0);
}

new_node->data = new_data;
new_node->next = *top_ref;
*top_ref = new_node;

}

// Function to pop an item from stack char pop(struct sNode* top_ref) { char res; struct sNode top;

if (*top_ref == NULL) {
    printf("Stack underflow\n"); // Corrected "Stack overflow" to "Stack underflow"
    exit(0);
}

top = *top_ref;
res = top->data;
*top_ref = top->next;
free(top);

return res;

}

Infix to Postfix Conversion

This section provides the algorithm for converting an infix expression to postfix.

infixToPostfix(infixexpr):
  postfixList = []
  tokenList = infixexpr
  Create an empty stack

for token in tokenList: if token is an operand: append(token) to postfixList elif token == '(': push(token) onto the stack elif token == ')': topToken = pop() from the stack while topToken != '(': append(topToken) to postfixList topToken = pop() from the stack else: # Operator while (not isEmpty(stack)) and (prec[top(stack)] >= prec[token]): append(pop(stack)) to postfixList push(token) onto the stack

while not isEmpty(stack): append(pop(stack)) to postfixList

return "".join(postfixList) # Concatenate the postfix list into a string

Infix to Prefix Conversion

This section provides the algorithm for converting an infix expression to prefix.

Input: An infix expression in a string 'infix'.

Reverse the string 'infix'.

Create an empty stack and an empty list for the prefix expression.

while (not end of string(infix)): ch = a character from the 'infix' string

if (ch == ')'): push(ch) onto the stack if (ch == '('): while (top(stack) != ')'): append(top(stack)) to prefixList pop() from the stack pop() // Remove the ')' if (ch is an operand): append(ch) to prefixList if (ch is an operator): while (not empty(stack) && prec(top(stack)) > prec(ch)): append(top(stack)) to prefixList pop() from the stack push(ch) onto the stack

while (not empty(stack)): append(top(stack)) to prefixList pop() from the stack

Reverse the 'prefix' string.