#include <stdio.h>
#include <stdlib.h>
#define TABLE_SIZE 101 // prime number for better distribution
/*
Better distribution means the hash function spreads your values evenly across all
buckets in the hash table instead of clustering them in just a few places.
*/
/* -----------------------------------------
Node structure for each hash bucket
----------------------------------------- */
typedef struct Node {
int value;
struct Node *next;
} Node;
/* -----------------------------------------
Hash table (array of linked lists)
----------------------------------------- */
Node* table[TABLE_SIZE];
/* -----------------------------------------
Hash function
----------------------------------------- */
unsigned hash(int x) {
return (unsigned)x % TABLE_SIZE;
}
/* -----------------------------------------
Initialize the set
----------------------------------------- */
void set_init() {
for (int i = 0; i < TABLE_SIZE; i++)
table[i] = NULL;
}
/* -----------------------------------------
Check if a value exists in the set
----------------------------------------- */
int set_contains(int x) {
unsigned h = hash(x);
Node *cur = table[h];
while (cur != NULL) {
if (cur->value == x)
return 1;
cur = cur->next;
}
return 0;
}
/* -----------------------------------------
Add a value to the set (no duplicates)
----------------------------------------- */
void set_add(int x) {
if (set_contains(x))
return; // already exists
unsigned h = hash(x);
Node *n = malloc(sizeof(Node));
n->value = x;
n->next = table[h]; // insert at head
table[h] = n;
}
/* -----------------------------------------
Remove a single value from the set
Returns 1 if removed, 0 if not found
----------------------------------------- */
int set_remove(int x) {
unsigned h = hash(x);
Node *cur = table[h];
Node *prev = NULL;
while (cur != NULL) {
if (cur->value == x) {
if (prev == NULL)
table[h] = cur->next; // removing head
else
prev->next = cur->next;
free(cur);
return 1; // removed
}
prev = cur;
cur = cur->next;
}
return 0; // not found
}
/* -----------------------------------------
Print all values in the set
----------------------------------------- */
void set_print() {
printf("Set contents: { ");
for (int i = 0; i < TABLE_SIZE; i++) {
Node *cur = table[i];
while (cur != NULL) {
printf("%d ", cur->value);
cur = cur->next;
}
}
printf("}\n");
}
/* -----------------------------------------
Free all memory used by the set
----------------------------------------- */
void set_free() {
for (int i = 0; i < TABLE_SIZE; i++) {
Node *cur = table[i];
while (cur != NULL) {
Node *tmp = cur;
cur = cur->next;
free(tmp);
}
table[i] = NULL;
}
}
/* -----------------------------------------
Delete the entire set (wrapper)
----------------------------------------- */
void set_delete() {
set_free();
}
/* -----------------------------------------
Demonstration of usage
----------------------------------------- */
int main() {
set_init();
set_add(40);
set_add(30);
set_add(20);
set_add(60);
set_add(20); // duplicate, ignored
set_add(20); // duplicate, ignored
set_add(10);
set_print();
printf("Removing 20...\n");
set_remove(20);
set_print();
printf("Deleting entire set...\n");
set_delete();
set_print(); // should print empty set
return 0;
}
/*
run:
Set contents: { 10 20 30 40 60 }
Removing 20...
Set contents: { 10 30 40 60 }
Deleting entire set...
Set contents: { }
*/
