#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// Constants
#define TABLE_SIZE 10
#define DELETED -999 // Marker for deleted slots in linear probing
// Structure for a node in the linked list (for chaining)
struct ChainNode {
int key;
int value;
struct ChainNode* next;
};
// Structure for chaining hash table
struct ChainHashTable {
struct ChainNode** table; // Array of linked list pointers
};
// Structure for open addressing hash table
struct OpenHashTable {
int* keys; // Array to store keys
int* values; // Array to store values
int size; // Current number of elements
};
// --- Chaining Hash Table Functions ---
// Create a new chain node
struct ChainNode* createChainNode(int key, int value) {
struct ChainNode* node = (struct ChainNode*)malloc(sizeof(struct ChainNode));
if (!node) {
printf("Memory allocation failed!\n");
exit(1);
}
node->key = key;
node->value = value;
node->next = NULL;
return node;
}
// Initialize chaining hash table
struct ChainHashTable* createChainHashTable() {
struct ChainHashTable* ht = (struct ChainHashTable*)malloc(sizeof(struct ChainHashTable));
if (!ht) {
printf("Memory allocation failed!\n");
exit(1);
}
ht->table = (struct ChainNode**)calloc(TABLE_SIZE, sizeof(struct ChainNode*));
if (!ht->table) {
printf("Memory allocation failed!\n");
exit(1);
}
return ht;
}
// Hash function
unsigned int hashFunction(int key) {
return key % TABLE_SIZE; // Simple modulo
}
// Insert into chaining hash table
void insertChain(struct ChainHashTable* ht, int key, int value) {
unsigned int index = hashFunction(key);
struct ChainNode* current = ht->table[index];
// Check if key exists
while (current) {
if (current->key == key) {
current->value = value;
printf("Updated key %d with value %d\n", key, value);
return;
}
current = current->next;
}
// Insert new node at the front of the list
struct ChainNode* newNode = createChainNode(key, value);
newNode->next = ht->table[index];
ht->table[index] = newNode;
printf("Inserted key %d with value %d\n", key, value);
}
// Search in chaining hash table
int searchChain(struct ChainHashTable* ht, int key) {
unsigned int index = hashFunction(key);
struct ChainNode* current = ht->table[index];
while (current) {
if (current->key == key) {
printf("Found key %d with value %d\n", key, current->value);
return current->value;
}
current = current->next;
}
printf("Key %d not found\n", key);
return -1;
}
// Delete from chaining hash table
void deleteChain(struct ChainHashTable* ht, int key) {
unsigned int index = hashFunction(key);
struct ChainNode* current = ht->table[index];
struct ChainNode* prev = NULL;
while (current) {
if (current->key == key) {
if (prev) {
prev->next = current->next;
} else {
ht->table[index] = current->next;
}
free(current);
printf("Deleted key %d\n", key);
return;
}
prev = current;
current = current->next;
}
printf("Key %d not found\n", key);
}
// Display chaining hash table
void displayChain(struct ChainHashTable* ht) {
printf("Chaining Hash Table:\n");
for (int i = 0; i < TABLE_SIZE; i++) {
printf("Index %d: ", i);
struct ChainNode* current = ht->table[i];
while (current) {
printf("(%d, %d) ", current->key, current->value);
current = current->next;
}
printf("\n");
}
}
// --- Open Addressing (Linear Probing) Hash Table Functions ---
// Initialize open addressing hash table
struct OpenHashTable* createOpenHashTable() {
struct OpenHashTable* ht = (struct OpenHashTable*)malloc(sizeof(struct OpenHashTable));
if (!ht) {
printf("Memory allocation failed!\n");
exit(1);
}
ht->keys = (int*)calloc(TABLE_SIZE, sizeof(int));
ht->values = (int*)calloc(TABLE_SIZE, sizeof(int));
if (!ht->keys || !ht->values) {
printf("Memory allocation failed!\n");
exit(1);
}
ht->size = 0;
// Initialize with -1 to indicate empty slots
for (int i = 0; i < TABLE_SIZE; i++) {
ht->keys[i] = -1;
}
return ht;
}
// Linear probing function
int probe(struct OpenHashTable* ht, int key, int i) {
return (hashFunction(key) + i) % TABLE_SIZE;
}
// Insert into open addressing hash table
void insertOpen(struct OpenHashTable* ht, int key, int value) {
if (ht->size >= TABLE_SIZE) {
printf("Hash table is full\n");
return;
}
int i = 0;
int index = probe(ht, key, i);
// Search for key or empty/deleted slot
while (ht->keys[index] != -1 && ht->keys[index] != key && i < TABLE_SIZE) {
i++;
index = probe(ht, key, i);
}
if (ht->keys[index] == key) {
ht->values[index] = value;
printf("Updated key %d with value %d\n", key, value);
} else {
ht->keys[index] = key;
ht->values[index] = value;
ht->size++;
printf("Inserted key %d with value %d\n", key, value);
}
}
// Search in open addressing hash table
int searchOpen(struct OpenHashTable* ht, int key) {
int i = 0;
int index = probe(ht, key, i);
while (ht->keys[index] != -1 && i < TABLE_SIZE) {
if (ht->keys[index] == key) {
printf("Found key %d with value %d\n", key, ht->values[index]);
return ht->values[index];
}
i++;
index = probe(ht, key, i);
}
printf("Key %d not found\n", key);
return -1;
}
// Delete from open addressing hash table
void deleteOpen(struct OpenHashTable* ht, int key) {
int i = 0;
int index = probe(ht, key, i);
while (ht->keys[index] != -1 && i < TABLE_SIZE) {
if (ht->keys[index] == key) {
ht->keys[index] = DELETED; // Mark as deleted
ht->size--;
printf("Deleted key %d\n", key);
return;
}
i++;
index = probe(ht, key, i);
}
printf("Key %d not found\n", key);
}
// Display open addressing hash table
void displayOpen(struct OpenHashTable* ht) {
printf("Open Addressing Hash Table:\n");
for (int i = 0; i < TABLE_SIZE; i++) {
if (ht->keys[i] != -1 && ht->keys[i] != DELETED) {
printf("Index %d: (%d, %d)\n", i, ht->keys[i], ht->values[i]);
} else {
printf("Index %d: Empty\n", i);
}
}
}
// Main function to test both hash tables
int main() {
// Test Chaining Hash Table
printf("--- Testing Chaining Hash Table ---\n");
struct ChainHashTable* chainHT = createChainHashTable();
insertChain(chainHT, 1, 100);
insertChain(chainHT, 11, 110); // Collides with key 1
insertChain(chainHT, 2, 200);
insertChain(chainHT, 1, 150); // Update key 1
displayChain(chainHT);
searchChain(chainHT, 11);
deleteChain(chainHT, 11);
displayChain(chainHT);
// Test Open Addressing Hash Table
printf("\n--- Testing Open Addressing Hash Table (Linear Probing) ---\n");
struct OpenHashTable* openHT = createOpenHashTable();
insertOpen(openHT, 1, 100);
insertOpen(openHT, 11, 110); // Collides with key 1, probes to next slot
insertOpen(openHT, 2, 200);
insertOpen(openHT, 1, 150); // Update key 1
displayOpen(openHT);
searchOpen(openHT, 11);
deleteOpen(openHT, 11);
displayOpen(openHT);
return 0;
}
Output:
Comments
Post a Comment