Esercizio 06

Si consideri la seguente implementazione di coda con priorità, commentata a lezione. Successivamente si esegua l'esercizio richiesto. Dopo aver testato adeguatamente la struttura, ed aver realizzato tutti i punti richiesti, inviare all'indirizzo paolo.buono@uniba.it l'esercitazione, in una cartella compressa in formato zip. Il file deve essere chiamato: "[ASDBR1314] esercizio06 - cognome.zip" e deve contenere solo file .h, .cpp, e il file di progetto. Scadenza dell'invio dell'esercitazione: 23.59 di domenica 8 dicembre.

Code con priorità

Le code con priorità mantengono minimo (massimo) di un insieme di chiavi su cui è definita una relazione d'ordine totale. Operatori:

• crea
• inserisci
• trovaMinimo
• cancellaMinimo

Altri operatori possono essere presenti:

• aumentaChiave
• decrementoChiave
• fondiCode

Esistono diverse implementazioni: array (ordinato e non), lista (ordinata e non), heap (d-heap, binomiali, di Fibonacci), coda binomiale, ottimo teorico.

Dopo aver scaricato il codice visto in aula eseguire i punti seguenti.
codice mostrato in aula:
- coda priorità con heap;
- coda priorità con lista, vettore, heap + fix[up | down];

- Risolvere i //TODO... presenti nel codice;

- Creare una classe che contiene un intero come chiave e un carattere come valore. Testare le diverse code con priorità con i seguenti dati: <10,'T'>,<11,'I'>,<6,'I'>,<1,'C'>,<2,'O'>,<8,'E'>,<7,'M'>,<3,'M'>,<5,'L'>,<4,'L'>,<9,'N'>,<12,'!'>

Tabelle Hash

Realizzare i seguenti punti:
- proporre una funzione hash perfetta per tutte le chiavi di lunghezza 3 sull'alfabeto {E,C,O}
- supponendo che le chiavi del dizionario siano stringhe e che la funzione hash sia definita su una tavola di dimensione m=5. Sommare i codici ASCII delle lettere della chiave e dividere il risultato per 5, prendere come chiave il resto della divisione e mostrare. il contenuto della tavola dopo aver inserito le stringhe: Bari, BAT, Brindisi, Foggia, Lecce, Taranto.
- Effettuare l'esercizio precedente con hash aperto.
Codice visto in aula:
- dizionario hash aperto
- dizionario hash chiuso