implementa una libreria generica che realizza la struttura dati tavola hash (con concatenamento) in grado di ospitare un insieme di coppie {<chiave_1,valore_1>,...,<chiave_n,valore_n>}. La tavola hash deve accettare chiavi e valori di tipi generici, tutte le chiavi hanno uno stesso tipo, tutti i valori hanno uno stesso tipo, ma chiavi e valori possono avere tipi fra loro differenti. La struttura dati deve offrire almeno le seguenti funzionalità: HashTable* hash_table_create(int (*f1)(const void*,const void*), unsigned long (*f2)(const void*)); void hash_table_put(HashTable*, const void*, const void*); void* hash_table_get(const HashTable*, const void*); int hash_table_contains_key(const HashTable*, const void*); void hash_table_remove(HashTable*, const void*); int hash_table_size(const HashTable*); void** hash_table_keyset(const HashTable*); void hash_table_free(HashTable*);
Ecco un'implementazione della libreria generica per la struttura dati tavola hash con concatenamento in C: ```c #include <stdio.h> #include <stdlib.h> #include <string.h> // Struttura per la cella della tavola hash typedef struct Cell { void* key; void* value; struct Cell* next; } Cell; // Struttura per la tavola hash typedef struct HashTable { int (*hash_function)(const void*, const void*); unsigned long (*equals_function)(const void*, const void*); int size; int capacity; Cell** buckets; } HashTable; // Funzione per creare una nuova tavola hash HashTable* hash_table_create(int (*hash_function)(const void*, const void*), unsigned long (*equals_function)(const void*)) { HashTable* table = malloc(sizeof(HashTable)); table->hash_function = hash_function; table->equals_function = equals_function; table->size = 0; table->capacity = 1000; // dimensione iniziale della tavola hash table->buckets = malloc(sizeof(Cell*) * table->capacity); for (int i = 0; i < table->capacity; i++) { table->buckets[i] = NULL; } return table; } // Funzione per calcolare l'indice della cella della tavola hash int hash_table_hash(const HashTable* table, const void* key) { return table->hash_function(key, NULL) % table->capacity; } // Funzione per inserire una nuova coppia chiave-valore nella tavola hash void hash_table_put(HashTable* table, const void* key, const void* value) { int index = hash_table_hash(table, key); Cell* cell = table->buckets[index]; while (cell != NULL) { if (table->equals_function(key, cell->key) == 1) { // se la chiave esiste, sostituisci il valore cell->value = value; return; } cell = cell->next; } // se la chiave non esiste, crea una nuova cella cell = malloc(sizeof(Cell)); cell->key = key; cell->value = value; cell->next = table->buckets[index]; table->buckets[index] = cell; table->size++; } // Funzione per recuperare il valore associato a una chiave void* hash_table_get(const HashTable* table, const void* key) { int index = hash_table_hash(table, key); Cell* cell = table->buckets[index]; while (cell != NULL) { if (table->equals_function(key, cell->key) == 1) { return cell->value; } cell = cell->next; } return NULL; } // Funzione per verificare se una chiave esiste nella tavola hash int hash_table_contains_key(const HashTable* table, const void* key) { int index = hash_table_hash(table, key); Cell* cell = table->buckets[index]; while (cell != NULL) { if (table->equals_function(key, cell->key) == 1) { return 1; } cell = cell->next; } return 0; } // Funzione per rimuovere una coppia chiave-valore dalla tavola hash void hash_table_remove(HashTable* table, const void* key) { int index = hash_table_hash(table, key); Cell* cell = table->buckets[index]; Cell* prev = NULL; while (cell != NULL) { if (table->equals_function(key, cell->key) == 1) { if (prev != NULL) { prev->next = cell->next; } else { table->buckets[index] = cell->next; } free(cell); table->size--; return; } prev = cell; cell = cell->next; } } // Funzione per ottenere il numero di elementi nella tavola hash int hash_table_size(const HashTable* table) { return table->size; } // Funzione per ottenere l'insieme delle chiavi della tavola hash void** hash_table_keyset(const HashTable* table) { int size = hash_table_size(table); void** keys = malloc(sizeof(void*) * size); int index = 0; for (int i = 0; i < table->capacity; i++) { Cell* cell = table->buckets[i]; while (cell != NULL) { keys[index] = cell->key; index++; cell = cell->next; } } return keys; } // Funzione per liberare la memoria allocata dalla tavola hash void hash_table_free(HashTable* table) { for (int i = 0; i < table->capacity; i++) { Cell* cell = table->buckets[i]; while (cell != NULL) { Cell* next = cell->next; free(cell); cell = next; } } free(table->buckets); free(table); } ``` Ecco un esempio di utilizzo della libreria: ```c int main() { // creare una tavola hash con funzione di hash e funzione di uguaglianza HashTable* table = hash_table_create(hash_function, equals_function); // inserire elementi nella tavola hash hash_table_put(table, "chiave1", "valore1"); hash_table_put(table, "chiave2", "valore2"); // recuperare il valore associato a una chiave void* valore = hash_table_get(table, "chiave1"); printf("%s\n", (char*)valore); // stampa "valore1" // verificare se una chiave esiste nella tavola hash int esiste = hash_table_contains_key(table, "chiave1"); printf("%d\n", esiste); // stampa 1 // rimuovere un elemento dalla tavola hash hash_table_remove(table, "chiave1"); // ottenere il numero di elementi nella tavola hash int size = hash_table_size(table); printf("%d\n", size); // stampa 1 // ottenere l'insieme delle chiavi della tavola hash void** keys = hash_table_keyset(table); for (int i = 0; i < size; i++) { printf("%s\n", (char*)keys[i]); // stampa "chiave2" } // liberare la memoria allocata dalla tavola hash hash_table_free(table); return 0; } ``` Nota che le funzioni di hash e uguaglianza devono essere implementate in base alle esigenze specifiche dell'applicazione. In questo esempio, le funzioni di hash e uguaglianza sono semplici e non sono ottimizzate per prestazioni.