Esercizio 1 Si vuole gestire un insieme dinamico contenente numeri interi attraverso una tabella hash. Si definiscono le seguenti strutture dati: typedef struct int_list{ int info; struct int_list *next; } int_list; typedef struct hash_table{ //vettore di puntatori a lista di interi int_list **h_table; //dimensione del vettore di puntatori h_table int t_size; //numero di elementi contenuti nella tabella int n_elem; } hash_table; Una tabella hash e' una struttura hash_table che contiene: - Un vettore di puntatori a lista di interi - Un valore t_size rappresentante la dimensione del vettore di puntatori - Un valore n_elem rappresentante il numero di elementi attualmente presenti nella tabella Tale tabella sara' gestita con liste di trabocco, quindi ogni bucket della tabella e' un puntatore alla testa della lista contenente gli elementi che, secondo la funzione hash utilizzata, sono stati inseriti in quel bucket. Gli elementi inseriti, quindi, saranno memorizzati come elementi di una lista di interi int_list. Lo scopo dell'homework e' quello di definire un'interfaccia, costituita da un insieme di funzioni, che permettano di effettuare diverse operazioni, come inserimento e cancellazione, nella tabella hash. La dimensione della tabella, cioe' del vettore di puntatori, e' data da una costante SIZE e non dovra' cambiare nell'esecuzione del programma. Viene fornita la seguente funzione hash che restituisce l'indice, compreso tra 0 e SIZE-1, del bucket in inserire o cercare un certo valore. Tale funzione e' data e non deve essere modificata. int hash(int x, hash_table *ht){ return x % ht->t_size; } L'homework prevede che il main, la funzione hash e la funzione di stampa siano gia' implementate e NON DEVONO ESSERE MODIFICATE. Possono essere aggiunte ulteriori funzioni ausiliarie oltre a quelle da implementare. Si dovranno implementare le seguenti funzioni: *Funzione di creazione ed inizializzazione di una tabella hash* hash_table * create_hash_table(int size) La funzione prende in input la dimensione del vettore di puntatori della tabella da creare e restituisce il puntatore alla struttura hash_table allocata. La funzione deve: - Allocare la zona di memoria per la struttura hash_table - Allocare il vettore di puntatori a int_list della hash_table - Inizializzare i puntatori del vettore a NULL - Inizializzare t_size a size e n_elem a 0. *Funzione di inserimento nella tabella hash* void insert(hash_table *ht, int x) La funzione prende ininput la hash_table ed il valore intero da inserire. La funzione deve: - Allocare una zona di memoria per il nuovo elemento della lista - Porre il valore info dell'elemento allocato ad x - Inserire l'elemento IN TESTA alla lista con indice hash(x,ht) - Aggiornare n_elem *Funzione di eliminazione delle occorrenze di un valore* void delete(hash_table *ht, int x) La funzione prende in input la tabella hash ed il valore da eliminare La funzione deve: - Rimuovere tutti gli elementi con valore x dalla tabella. Tali elementi, se esistono, si troveranno nel bucket con indice h(x,ht) - Aggiornare n_elem Ricordarsi di deallocare la memoria degli elementi rimossi. *Funzione di individuazione del bucket piu' pieno* int index_max_bucket(hash_table *ht) La funzione prende in input la tabella hash e ritorna l'indice del bucket che contiene il maggior numero di elementi. Nel caso in cui vi siano piu'bucket con lo stesso numero di elementi, si deve ritornare l'indice del bucket con indice minore tra quelli aventi il numero massimo di elementi. *Funzione di ricerca di un valore* int_list * search(hash_table *ht, int x) La funzione prende in input la tabella hash ed il valore da cercare, restituisce un puntatore all'elemento con il valore cercato, se presente, NULL altrimenti. Nel caso in cui siano presenti piu' elementi con lo stesso valore e' indifferente quale sia il puntatore ritornato tra questi. Esempio: Si vogliono inserire i valori: 83 86 77 15 93 35 86 92 49 21 62 27 90 59 63 26 40 26 72 36 11 68 67 29 82 L'inserimento termina con l'inserimento del valore -1, si inseriranno quindi da tastiera i valori precedenti seguiti da -1, premendo invio dopo OGNI numero inserito. La tabella ha dimensione 53, il numero di elementi inseriti e' 25. La stampa della tabella dopo l'inserimento sarĂ  quindi: 53 25 0: 1: 2: 3: 4: 5: 6: 59 7: 8: 9: 62 10: 63 11: 11 12: 13: 14: 67 15: 68 15 16: 17: 18: 19: 72 20: 21: 21 22: 23: 24: 77 25: 26: 26 26 27: 27 28: 29: 82 29 30: 83 31: 32: 33: 86 86 34: 35: 35 36: 36 37: 90 38: 39: 92 40: 40 93 41: 42: 43: 44: 45: 46: 47: 48: 49: 49 50: 51: 52: Si rimuovono poi tutti i numeri pari tra 0 e 99, la tabella quindi diventa: 53 13 0: 1: 2: 3: 4: 5: 6: 59 7: 8: 9: 10: 63 11: 11 12: 13: 14: 67 15: 15 16: 17: 18: 19: 20: 21: 21 22: 23: 24: 77 25: 26: 27: 27 28: 29: 29 30: 83 31: 32: 33: 34: 35: 35 36: 37: 38: 39: 40: 93 41: 42: 43: 44: 45: 46: 47: 48: 49: 49 50: 51: 52: Gli unici bucket pieni hanno un solo elemento, per stampare l'indice del bucket che contiene il maggior numero di elementi si deve quindi stampare l'indice del bucket con indice minore tra quelli che ne hanno uno, in questo caso il bucket con indice sei. 6 Si ricerca infine il 29 ed il 105, il primo e' presente nella tabella hash mentre il secondo no. Il programma quindi deve stampare: 29 FOUND 105 NOT FOUND Ricapitolando, l'esecuzione corretta e': 83 86 77 15 93 35 86 92 49 21 62 27 90 59 63 26 40 26 72 36 11 68 67 29 82 -1 53 25 0: 1: 2: 3: 4: 5: 6: 59 7: 8: 9: 62 10: 63 11: 11 12: 13: 14: 67 15: 68 15 16: 17: 18: 19: 72 20: 21: 21 22: 23: 24: 77 25: 26: 26 26 27: 27 28: 29: 82 29 30: 83 31: 32: 33: 86 86 34: 35: 35 36: 36 37: 90 38: 39: 92 40: 40 93 41: 42: 43: 44: 45: 46: 47: 48: 49: 49 50: 51: 52: 53 13 0: 1: 2: 3: 4: 5: 6: 59 7: 8: 9: 10: 63 11: 11 12: 13: 14: 67 15: 15 16: 17: 18: 19: 20: 21: 21 22: 23: 24: 77 25: 26: 27: 27 28: 29: 29 30: 83 31: 32: 33: 34: 35: 35 36: 37: 38: 39: 40: 93 41: 42: 43: 44: 45: 46: 47: 48: 49: 49 50: 51: 52: 6 29 FOUND 105 NOT FUOND