Hashing Division Method
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// Define a basic hash table structure
typedef struct {
bool *table; // Array representing the hash table (used as a boolean set)
int size; // Size of the hash table
} HashTable;
// Function to create a hash table with a given size
HashTable* createHashTable(int size) {
HashTable *hashTable = (HashTable*)malloc(sizeof(HashTable));
if (hashTable) {
hashTable->table = (bool*)calloc(size, sizeof(bool)); // Initialize all elements to false
hashTable->size = size;
}
return hashTable;
}
// Simple hash function to map a key to an index (based on modulus operation)
int simpleHash(int key, int size) {
return key % size; // Basic division method
}
// Insert a key into the hash table
void insert(HashTable *hashTable, int key) {
int index = simpleHash(key, hashTable->size);
hashTable->table[index] = true; // Set the corresponding index to true
}
// Function to print the entire hash table (showing indices with keys)
void printHashTable(HashTable *hashTable) {
printf("Hash table:\n");
for (int i = 0; i < hashTable->size; i++) {
if (hashTable->table[i]) {
printf("Index %d: Key exists\n", i); // Indicate that a key exists at this index
} else {
printf("Index %d: Empty\n", i); // Indicate that this index is empty
}
}
}
// Main program demonstrating a hash table with insertion and no search
int main() {
int tableSize = 10; // Example size of the hash table
HashTable *hashTable = createHashTable(tableSize);
// Insert some keys into the hash table
insert(hashTable, 1);
insert(hashTable, 3);
insert(hashTable, 5);
insert(hashTable, 7);
insert(hashTable, 9);
// Print the hash table contents
printHashTable(hashTable);
// Free allocated memory
free(hashTable->table);
free(hashTable);
return 0;
}
Binary Search Tree
#include <stdio.h>
#include <stdlib.h>
// Node structure for the Binary Search Tree
typedef struct TreeNode {
int key;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// Function to create a new node
TreeNode* createNode(int key) {
TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
if (newNode) {
newNode->key = key;
newNode->left = NULL;
newNode->right = NULL;
}
return newNode;
}
// Insert a new key into the BST
TreeNode* insert(TreeNode* root, int key) {
if (root == NULL) {
return createNode(key);
}
if (key < root->key) {
root->left = insert(root->left, key);
} else if (key > root->key) {
root->right = insert(root->right, key);
}
return root;
}
// Search for a key in the BST
TreeNode* search(TreeNode* root, int key) {
if (root == NULL || root->key == key) {
return root;
}
if (key < root->key) {
return search(root->left, key);
} else {
return search(root->right, key);
}
}
// In-order traversal (Left, Root, Right)
void inOrderTraversal(TreeNode* root) {
if (root != NULL) {
inOrderTraversal(root->left);
printf("%d ", root->key);
inOrderTraversal(root->right);
}
}
// Pre-order traversal (Root, Left, Right)
void preOrderTraversal(TreeNode* root) {
if (root != NULL) {
printf("%d ", root->key);
preOrderTraversal(root->left);
preOrderTraversal(root->right);
}
}
// Post-order traversal (Left, Right, Root)
void postOrderTraversal(TreeNode* root) {
if (root != NULL) {
postOrderTraversal(root->left);
postOrderTraversal(root->right);
printf("%d ", root->key);
}
}
// Main function to test the BST implementation
int main() {
TreeNode* root = NULL;
// Insert some elements into the BST
root = insert(root, 50);
insert(root, 30);
insert(root, 70);
insert(root, 20);
insert(root, 40);
insert(root, 60);
insert(root, 80);
printf("In-order traversal:\n");
inOrderTraversal(root);
printf("\n");
printf("Pre-order traversal:\n");
preOrderTraversal(root);
printf("\n");
printf("Post-order traversal:\n");
postOrderTraversal(root);
printf("\n");
int searchKey = 40;
TreeNode* foundNode = search(root, searchKey);
if (foundNode) {
printf("Node with key %d found.\n", searchKey);
} else {
printf("Node with key %d not found.\n", searchKey);
}
return 0;
}
Heap Sort
#include <stdio.h>
// Function to swap two integers
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
// Function to heapify a subtree rooted at index 'i' in an array of size 'n'
void heapify(int arr[], int n, int i) {
int largest = i; // Initialize the largest as root
int left = 2 * i + 1; // Left child index
int right = 2 * i + 2; // Right child index
// If the left child is larger than the root, update largest
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
// If the right child is larger than the largest so far, update largest
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
// If largest is not root, swap and continue heapifying
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 by heapifying from the bottom up
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--) {
// Move the current root to the end
swap(&arr[0], &arr[i]);
// Re-heapify the reduced heap
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");
}
// Main function to test heap sort
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Unsorted array:\n");
printArray(arr, n);
// Perform heap sort
heapSort(arr, n);
printf("Sorted array:\n");
printArray(arr, n);
return 0;
}