C Data Structures and Algorithms: Sorting, Lists, Queues, Stacks, Trees and Hashing

C Data Structures and Algorithms: Code Examples

～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～

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

int bubbling(int *arr, int n) {
for (int i = 0; i < n - 1; i++) { // Outer loop controls the number of sorting passes
for (int j = 0; j < n - 1 - i; j++) { // Inner loop controls the comparisons in each pass
if (arr[j] < arr[j + 1]) { // If the previous element is smaller than the next one, swap them
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return 0;
}

int main() {
int arr[6] = {0, 1, 4, 6, 8, 9};
bubbling(arr, 6); // Call the bubble sort
for (int i = 0; i < 6; i++) printf("%d", arr[i]);
return 0;
}

～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～

Greatest Common Divisor (GCD) with Recursion

#include <stdio.h>

int gcd(int a, int b) {
if (b == 0) return a; // Recursive termination condition
return gcd(b, a % b); // Recursive call
}

～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～

Singly Linked List

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

typedef int Elemtype;

typedef struct node {
Elemtype data; // Data field
struct node *next; // Pointer field
} Node;

Node* initlist() {
Node *head = (Node*)malloc(sizeof(Node)); // Create the head node
head->data = 0; // Initialize the data
head->next = NULL; // Initialize the pointer
return head;
}

int insertHead(Node* L, Elemtype e) {
Node *p = (Node*)malloc(sizeof(Node)); // Create a new node
p->data = e; // Assign the value
p->next = NULL; // Initialize the pointer
L->next = p; // Insert at the head of the list
return 1;
}

void listNode(Node *L) {
Node *p = L->next; // Start traversing from the first node after the head
while (p != NULL) { // Traverse the list
printf("%d->", p->data);
p = p->next;
}
}

Node *getTail(Node *L) {
Node *p = L; // Start from the head node
while (p->next != NULL) p = p->next; // Find the tail node
return p;
}

Node *insertTail(Node *tail, Elemtype e) {
Node *p = (Node*)malloc(sizeof(Node)); // Create a new node
p->data = e; // Assign the value
p->next = NULL; // Initialize the pointer
tail->next = p; // Insert at the tail of the list
return p;
}

int insertNode(Node *L, int pos, Elemtype e) {
Node *p = L;
for (int i = 0; i < pos - 1; i++) p = p->next; // Find the predecessor of the insertion position
Node *q = (Node*)malloc(sizeof(Node)); // Create a new node
q->data = e; // Assign the value
q->next = p->next; // Insert into the list
p->next = q;
return 0;
}

int main() {
Node *list = initlist(); // Initialize the list
Node *tail = getTail(list); // Get the tail node
tail = insertTail(tail, 10); // Insert at the tail
tail = insertTail(tail, 20);
tail = insertTail(tail, 30);
insertNode(list, 2, 15); // Insert a node at a specified position
listNode(list); // Print the list
return 0;
}

～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～

Linked Queue

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

typedef int ElemType;

typedef struct QueueNode {
ElemType data; // Data field
struct QueueNode *next; // Pointer field
} QueueNode;

typedef struct {
QueueNode *front; // Front pointer
QueueNode *rear; // Rear pointer
} Queue;

Queue* initQueue() {
Queue *q = (Queue*)malloc(sizeof(Queue)); // Create the queue
QueueNode *node = (QueueNode*)malloc(sizeof(QueueNode)); // Create the head node
node->data = 0; // Initialize the data
node->next = NULL; // Initialize the pointer
q->front = node; // Initialize the front
q->rear = node; // Initialize the rear
return q;
}

int isEmpty(Queue *q) {
return (q->front == q->rear) ? 1 : 0; // Check whether the queue is empty
}

void equeue(Queue *q, ElemType e) {
QueueNode *node = (QueueNode*)malloc(sizeof(QueueNode)); // Create a new node
node->data = e; // Assign the value
node->next = NULL; // Initialize the pointer
q->rear->next = node; // Insert at the rear of the queue
q->rear = node; // Update the rear
}

int dequeue(Queue *q, ElemType *e) {
if (isEmpty(q)) { // Check whether the queue is empty
printf("Empty\n");
return 0;
}
QueueNode *node = q->front->next; // Get the front node
*e = node->data; // Get the data
q->front->next = node->next; // Update the front
if (q->rear == node) q->rear = q->front; // If the queue becomes empty, update the rear
free(node); // Free the memory
return 1;
}

ElemType getFront(Queue *q) {
if (isEmpty(q)) { // Check whether the queue is empty
printf("Empty\n");
return 0;
}
return q->front->next->data; // Return the front data
}

int main() {
Queue *q = initQueue(); // Initialize the queue
equeue(q, 10); // Enqueue
equeue(q, 20);
equeue(q, 30);
equeue(q, 40);
equeue(q, 50);
ElemType e;
dequeue(q, &e); // Dequeue
printf("Dequeued %d\n", e);
dequeue(q, &e);
printf("Dequeued %d\n", e);
printf("%d\n", getFront(q)); // Get the front data
return 0;
}

～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～

Array-Based Stack

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100

typedef int Elemtype;

typedef struct stack {
Elemtype *data; // Data array
int top; // Top pointer
} stack;

stack *initStack() {
stack *s = (stack*)malloc(sizeof(stack)); // Create the stack
s->data = (Elemtype*)malloc(sizeof(Elemtype) * MAXSIZE); // Initialize the data array
s->top = -1; // Initialize the top pointer
return s;
}

int isEmpty(stack *s) {
return (s->top == -1) ? 1 : 0; // Check whether the stack is empty
}

int push(stack *s, Elemtype e) {
if (s->top >= MAXSIZE - 1) return -1; // Check whether the stack is full
s->top++; // Update the top pointer
s->data[s->top] = e; // Push
return 0;
}

int pop(stack *s, Elemtype *e) {
if (s->top == -1) return -1; // Check whether the stack is empty
*e = s->data[s->top]; // Get the top data
s->top--; // Update the top pointer
return 0;
}

int getTop(stack *s, Elemtype *e) {
if (s->top == -1) return -1; // Check whether the stack is empty
*e = s->data[s->top]; // Get the top data
return 0;
}

int main() {
stack *s = initStack(); // Initialize the stack
push(s, 10); // Push
push(s, 20);
push(s, 30);
Elemtype e;
pop(s, &e); // Pop
printf("%d\n", e);
pop(s, &e);
printf("%d\n", e);
pop(s, &e);
printf("%d\n", e);
return 0;
}

～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～

Binary Tree Traversal

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

// Define the binary tree node structure
typedef struct Node {
char data; // Data field
struct Node* left; // Left subtree pointer
struct Node* right; // Right subtree pointer
} Node;

char str[] = "ABDH#K###E##CFI###G#J##"; // Preorder sequence of the binary tree
int idx = 0; // Global index used to build the tree

// Create the binary tree
Node* createTree() {
char ch = str[idx++]; // Get the current character
if (ch == '#') return NULL; // '#' represents an empty node
Node* node = (Node*)malloc(sizeof(Node)); // Create a new node
node->data = ch; // Assign the value
node->left = createTree(); // Recursively create the left subtree
node->right = createTree(); // Recursively create the right subtree
return node;
}

// Preorder traversal
void preOrder(Node* root) {
if (root == NULL) return; // Recursive termination condition
printf("%c ", root->data); // Visit the root node
preOrder(root->left); // Traverse the left subtree
preOrder(root->right); // Traverse the right subtree
}

// Inorder traversal
void inOrder(Node* root) {
if (root == NULL) return; // Recursive termination condition
inOrder(root->left); // Traverse the left subtree
printf("%c ", root->data); // Visit the root node
inOrder(root->right); // Traverse the right subtree
}

// Postorder traversal
void postOrder(Node* root) {
if (root == NULL) return; // Recursive termination condition
postOrder(root->left); // Traverse the left subtree
postOrder(root->right); // Traverse the right subtree
printf("%c ", root->data); // Visit the root node
}

int main() {
Node* root = createTree(); // Create the binary tree
printf("Preorder traversal: ");
preOrder(root); // Preorder traversal
printf("\n");
printf("Inorder traversal: ");
inOrder(root); // Inorder traversal
printf("\n");
printf("Postorder traversal: ");
postOrder(root); // Postorder traversal
printf("\n");
return 0;
}

～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～

AVL Tree: Insertion, Deletion and Search

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

typedef struct Node {
int val; // Data field
int height; // Node height
struct Node* left; // Left subtree pointer
struct Node* right; // Right subtree pointer
} Node;

Node* newNode(int val) {
Node* node = (Node*)malloc(sizeof(Node)); // Create a new node
node->val = val; // Assign the value
node->height = 1; // Initialize the height
node->left = NULL; // Initialize the left subtree
node->right = NULL; // Initialize the right subtree
return node;
}

int getHeight(Node* node) {
return (node == NULL) ? 0 : node->height; // Get the node height
}

int max(int a, int b) {
return (a > b) ? a : b; // Return the larger of two values
}

int getBalance(Node* node) {
return getHeight(node->left) - getHeight(node->right); // Calculate the balance factor
}

Node* leftRotate(Node* root) {
Node* newRoot = root->right; // The new root is the right child of the original root
Node* T2 = newRoot->left; // Save the left subtree of the new root
newRoot->left = root; // The original root becomes the left child of the new root
root->right = T2; // The original left subtree of the new root becomes the right subtree of the original root
root->height = 1 + max(getHeight(root->left), getHeight(root->right)); // Update the height of the original root
newRoot->height = 1 + max(getHeight(newRoot->left), getHeight(newRoot->right)); // Update the height of the new root
return newRoot; // Return the new root
}

Node* rightRotate(Node* root) {
Node* newRoot = root->left; // The new root is the left child of the original root
Node* T2 = newRoot->right; // Save the right subtree of the new root
newRoot->right = root; // The original root becomes the right child of the new root
root->left = T2; // The original right subtree of the new root becomes the left subtree of the original root
root->height = 1 + max(getHeight(root->left), getHeight(root->right)); // Update the height of the original root
newRoot->height = 1 + max(getHeight(newRoot->left), getHeight(newRoot->right)); // Update the height of the new root
return newRoot; // Return the new root
}

Node* insertNode(Node* node, int key) {
if (node == NULL) return newNode(key); // Recursive termination condition
if (key < node->val) node->left = insertNode(node->left, key); // Recursively insert into the left subtree
else if (key > node->val) node->right = insertNode(node->right, key); // Recursively insert into the right subtree
else return node; // If the value already exists, return directly
node->height = 1 + max(getHeight(node->left), getHeight(node->right)); // Update the node height
int balance = getBalance(node); // Calculate the balance factor
// LL imbalance
if (balance > 1 && key < node->left->val) return rightRotate(node); // Right rotation
// LR imbalance
if (balance > 1 && key > node->left->val) {
node->left = leftRotate(node->left); // Left rotate the left subtree first
return rightRotate(node); // Then right rotate the current node
}
// RR imbalance
if (balance < -1 && key > node->right->val) return leftRotate(node); // Left rotation
// RL imbalance
if (balance < -1 && key < node->right->val) {
node->right = rightRotate(node->right); // Right rotate the right subtree first
return leftRotate(node); // Then left rotate the current node
}
return node; // Return the current node
}

// Preorder traversal
void preOrder(Node* root) {
if (root == NULL) return; // Recursive termination condition
printf("%d ", root->val); // Visit the root node
preOrder(root->left); // Traverse the left subtree
preOrder(root->right); // Traverse the right subtree
}

// Inorder traversal
void inOrder(Node* root) {
if (root == NULL) return; // Recursive termination condition
inOrder(root->left); // Traverse the left subtree
printf("%d ", root->val); // Visit the root node
inOrder(root->right); // Traverse the right subtree
}

// Search for a node
Node* findNode(Node* root, int key, int* counter) {
Node* cur = root; // Start searching from the root
while (cur != NULL) {
(*counter)++; // Count the comparisons
if (key < cur->val) cur = cur->left; // Search the left subtree
else if (key > cur->val) cur = cur->right; // Search the right subtree
else return cur; // Target node found
}
return NULL; // Target node not found
}

// Delete a node
Node* deleteNode(Node* root, int key) {
if (root == NULL) return root; // Recursive termination condition
if (key < root->val) root->left = deleteNode(root->left, key); // Recursively delete from the left subtree
else if (key > root->val) root->right = deleteNode(root->right, key); // Recursively delete from the right subtree
else { // Target node found
if (root->left == NULL) { // If the left subtree is empty
Node* temp = root->right; // Replace the current node with the right subtree
free(root); // Free the memory
return temp;
} else if (root->right == NULL) { // If the right subtree is empty
Node* temp = root->left; // Replace the current node with the left subtree
free(root); // Free the memory
return temp;
}
Node* temp = root->right; // Find the minimum node in the right subtree
while (temp->left != NULL) temp = temp->left;
root->val = temp->val; // Replace the current value with the minimum value
root->right = deleteNode(root->right, temp->val); // Recursively delete the minimum node from the right subtree
}
root->height = 1 + max(getHeight(root->left), getHeight(root->right)); // Update the node height
int balance = getBalance(root); // Calculate the balance factor
// LL imbalance
if (balance > 1 && getBalance(root->left) >= 0) return rightRotate(root); // Right rotation
// LR imbalance
if (balance > 1 && getBalance(root->left) < 0) {
root->left = leftRotate(root->left); // Left rotate the left subtree first
return rightRotate(root); // Then right rotate the current node
}
// RR imbalance
if (balance < -1 && getBalance(root->right) <= 0) return leftRotate(root); // Left rotation
// RL imbalance
if (balance < -1 && getBalance(root->right) > 0) {
root->right = rightRotate(root->right); // Right rotate the right subtree first
return leftRotate(root); // Then left rotate the current node
}
return root; // Return the current node
}

int main() {
Node* root = NULL; // Initialize the AVL tree
root = insertNode(root, 10); // Insert nodes
root = insertNode(root, 20);
root = insertNode(root, 30);
printf("Preorder traversal: ");
preOrder(root); // Preorder traversal
printf("\n");
printf("Inorder traversal: ");
inOrder(root); // Inorder traversal
printf("\n");
root = deleteNode(root, 20); // Delete a node
printf("Inorder traversal after deleting 20: ");
inOrder(root);
printf("\n");
int counter = 0;
Node* result = findNode(root, 70, &counter); // Search for a node
if (result != NULL) printf("Node 70 found, comparisons: %d\n", counter);
else printf("Node 70 not found\n");
return 0;
}

～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～

Heap Sort

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

void swap(int *a, int *b) {
int temp = *a; // Swap the values of two variables
*a = *b;
*b = temp;
}

void heapify(int *arr, int n, int i) {
int largest = i; // Initialize the largest as the current node
int left = 2 * i + 1; // Index of the left child
int right = 2 * i + 2; // Index of the right child
if (left < n && arr[left] > arr[largest]) largest = left; // If the left child is larger than the current largest
if (right < n && arr[right] > arr[largest]) largest = right; // If the right child is larger than the current largest
if (largest != i) { // If the largest is not the current node
swap(&arr[i], &arr[largest]); // Swap the current node with the largest node
heapify(arr, n, largest); // Recursively adjust the heap
}
}

void heapSort(int *arr, int n) {
for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); // Build the max heap
for (int i = n - 1; i > 0; i--) {
swap(&arr[0], &arr[i]); // Move the largest value to the end of the array
heapify(arr, i, 0); // Adjust the remaining part into a max heap
}
}

int main() {
int arr[] = {12, 11, 13, 5, 6, 7}; // Initialize the array
int n = sizeof(arr) / sizeof(arr[0]); // Calculate the array length
printf("Before sorting: ");
for (int i = 0; i < n; i++) printf("%d ", arr[i]); // Print the array before sorting
printf("\n");
heapSort(arr, n); // Heap sort
printf("After sorting: ");
for (int i = 0; i < n; i++) printf("%d ", arr[i]); // Print the array after sorting
printf("\n");
return 0;
}

～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～

Hash Table with Separate Chaining

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

typedef struct KeyValuePair {
int key; // Key
char value[20]; // Value
struct KeyValuePair* next; // Pointer to the next key-value pair
} KeyValuePair;

typedef struct HashTable {
KeyValuePair** buckets; // Bucket array
int capacity; // Hash table capacity
} HashTable;

HashTable* createHashTable(int capacity) {
HashTable* hashTable = (HashTable*)malloc(sizeof(HashTable)); // Create the hash table
hashTable->capacity = capacity; // Set the capacity
hashTable->buckets = (KeyValuePair**)malloc(sizeof(KeyValuePair*) * hashTable->capacity); // Initialize the bucket array
for (int i = 0; i < hashTable->capacity; i++) hashTable->buckets[i] = NULL; // Initialize each bucket as empty
return hashTable;
}

int hashFunction(int key, int capacity) {
return key % capacity; // Hash function: modulo operation
}

void insertKeyValuePair(HashTable* hashTable, int key, const char* value) {
int position = hashFunction(key, hashTable->capacity); // Calculate the hash value
KeyValuePair* newPair = (KeyValuePair*)malloc(sizeof(KeyValuePair)); // Create a new key-value pair
newPair->key = key; // Set the key
strcpy(newPair->value, value); // Set the value
newPair->next = NULL; // Initialize the pointer
if (hashTable->buckets[position] == NULL) hashTable->buckets[position] = newPair; // If the bucket is empty, insert directly
else { // Otherwise, insert at the end of the chain
KeyValuePair* current = hashTable->buckets[position];
while (current->next != NULL) current = current->next;
current->next = newPair;
}
}

const char* findValueByKey(HashTable* hashTable, int key) {
int position = hashFunction(key, hashTable->capacity); // Calculate the hash value
KeyValuePair* current = hashTable->buckets[position]; // Get the chain in the bucket
while (current != NULL) { // Traverse the chain
if (current->key == key) return current->value; // Target key found, return the value
current = current->next;
}
return NULL; // Target key not found
}

void deleteKeyValuePair(HashTable* hashTable, int key) {
int position = hashFunction(key, hashTable->capacity); // Calculate the hash value
KeyValuePair* current = hashTable->buckets[position]; // Get the chain in the bucket
KeyValuePair* previous = NULL; // Previous node
while (current != NULL) { // Traverse the chain
if (current->key == key) { // Target key found
if (previous == NULL) hashTable->buckets[position] = current->next; // If it is the head of the chain
else previous->next = current->next; // If it is in the middle or at the end of the chain
free(current); // Free the memory
return;
}
previous = current;
current = current->next;
}
printf("Key-value pair not found, cannot delete.\n"); // Target key not found
}

void printHashTable(HashTable* hashTable) {
printf("Hash table contents:\n");
for (int i = 0; i < hashTable->capacity; i++) { // Traverse the hash table
KeyValuePair* current = hashTable->buckets[i];
if (current != NULL) { // If the bucket is not empty
printf("Bucket %d: ", i);
while (current != NULL) { // Traverse the chain
printf("(key: %d, value: %s) -> ", current->key, current->value);
current = current->next;
}
printf("NULL\n");
}
}
}

int main() {
HashTable* hashTable = createHashTable(10); // Create the hash table
insertKeyValuePair(hashTable, 1, "Alice"); // Insert key-value pairs
insertKeyValuePair(hashTable, 2, "Bob");
insertKeyValuePair(hashTable, 11, "Charlie");
insertKeyValuePair(hashTable, 4, "David");
insertKeyValuePair(hashTable, 15, "Eva");
printHashTable(hashTable); // Print the hash table
const char* value = findValueByKey(hashTable, 11); // Search for a key-value pair
if (value != NULL) printf("Value for key 11: %s\n", value);
else printf("No value found for key 11.\n");
deleteKeyValuePair(hashTable, 2); // Delete a key-value pair
printf("After deleting key 2:\n");
printHashTable(hashTable);
// Free the memory
for (int i = 0; i < hashTable->capacity; i++) {
KeyValuePair* current = hashTable->buckets[i];
while (current != NULL) {
KeyValuePair* temp = current;
current = current->next;
free(temp);
}
}
free(hashTable->buckets);
free(hashTable);
return 0;
}