Progetto-di-API-2022

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.

Prestazioni

	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

Strutture dati utilizzate

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".

Per ulteriori informazioni si consulti la documentazione all'interno del file sorgente "Bellani - Progetto di Algoritmi e Strutture dati 2021-2022 [07-09-2022].c"