Progetto di Algoritmi e Strutture dati realizzato per il corso "PROVA FINALE (PROGETTO DI ALGORITMI E STRUTTURE DATI)" del Politecnico di Milano nell'anno accademico 2021/2022. Voto: 30 e lode.
| Tempo impiegato [s] | Tempo massimo per passare il task [s] | Memoria occupata [MB] | Limite memoria per passare il task [MB] | |
|---|---|---|---|---|
| UPTO18 | 0,669 | 0,8 | 5,72 | 18 |
| UPTO21 | 10,006 | 25 | 77,2 | 130 |
| UPTO24 | 10,383 | 25 | 77,2 | 130 |
| UPTO27 | 10,431 | 25 | 45,5 | 130 |
| UPTO30 | 9,136 | 25 | 37 | 130 |
| CUMLAUDE | 30,059 | 50 | 93,7 | 170 |
typedef struct _dict
{
int k;
int size_array_max;
int size_array_real;
int size_dictionary_max;
int cand_word;
char * strings; //dizionario
char * strings_v; //coda
} dictionary;L'applicativo necessitava di una struttura dati efficiente nell'inserimento, nella ricerca e nell'ordinamento. Ho deciso allora di memorizzare le stringhe che compongono il "dizionario" in due strutture dati, una tabella di hash "char * strings" gestita in closed hashing e un semplice arraylist "char * strings_v". Se viene richiesto un ordinamento, esso viene effettuato solo sugli elementi utili di "strings_v", mentre le operazioni di ricerca sono sempre eseguite su "strings".