Lezione 12
Strutture dati dinamiche
Programmazione per la Musica | Prof. Luca A. Ludovico
Strutture dati dinamiche
• Le strutture dati dinamiche hanno dimensioni che
possono variare «dinamicamente» a seconda delle
esigenze.
• Nella scorsa lezione abbiamo affrontato due tipi di
lista molto simili come comportamento: ArrayList e
Vector. Si tratta di rivisitazioni del concetto di array
(collezione lineare di elementi), con dimensioni
variabili a run time e con tipi di elementi non
prefissati e potenzialmente vari (si tratta di generiche
istanze di Object).
Programmazione per la Musica - Prof. Luca A. Ludovico
12. Strutture dati dinamiche
Dizionari
• Un altro esempio di strutture dati dinamiche è la
categoria dei dizionari, ossia collezioni (di dimensioni
variabili a run time) di coppie <chiave,valore>. L’accesso
ai valori avviene non per indice ma per chiave.
• Concettualmente questo tipo di strutture dati ricorda
proprio i dizionari di una data lingua, collezioni di
definizioni che vengono ricercate procedendo per chiave.
• In Java, i dizionari si possono implementare tramite la
classe public class HashMap<K,V>. Altre classi verranno
presentate al termine delle slide.
Programmazione per la Musica - Prof. Luca A. Ludovico
12. Strutture dati dinamiche
Metodi principali
• boolean containsKey(Object key)
restituisce true se la mappatura corrente contiene la
chiave specificata
• boolean containsValue(Object value)
restituisce true se la mappatura corrente contiene
(almeno una volta) il valore specificato.
Da notare che la chiave deve essere univoca nella
struttura dati, mentre il valore può essere ripetuto.
• boolean isEmpty ()
vero se non ci sono coppie <K,V>
• int size()
numero di chiavi contenute
Programmazione per la Musica - Prof. Luca A. Ludovico
12. Strutture dati dinamiche
Strutture dati per chiavi e valori
• Set<K> keySet()
Restituisce l’insieme delle chiavi.
• Collection<V> values()
Restituisce la collezione dei valori.
• Set<Map.Entry<K,V>> entrySet()
Restituisce una visione di insieme delle mappature.
• Per ciclare mantenendo sincronizzazione chiave-valore:
for (Entry<tipo_chiave, tipo_valore> entry :
nome_dizionario.entrySet())
All’interno del ciclo, su entry si possono invocare i metodi tipo_chiave getKey() e
tipo_valore getValue(); vedi esempio PitchDictionary.java
Programmazione per la Musica - Prof. Luca A. Ludovico
12. Strutture dati dinamiche
Aggiunta e rimozione di elementi
• V put(K key, V value)
associa il valore specificato alla chiave specificata
• void putAll(Map<? extends K,? extends V> m)
copia tutti I valori delle mappature dalla mappa specificata a quella
corrente
• V remove(Object key)
se presente, rimuove la mappatura <chiave,valore> specificata per
questa chiave
• void clear()
rimuove tutte le mappature
Programmazione per la Musica - Prof. Luca A. Ludovico
12. Strutture dati dinamiche
Varianti
• HashMap è concepita per creare coppie
<chiave,valore> in casi in cui l’ordine di inserimento
non è rilevante.
– In altre parole, non si può confidare sull’ordinamento delle
chiavi (né in ordine di inserimento, né in ordine naturale)
• LinkedHashMap è una variante in cui le chiavi
rispettano l’ordine di inserimento.
• TreeMap utilizza l’ordine naturale delle chiavi
– …ma permette anche di definire un criterio custom
Programmazione per la Musica - Prof. Luca A. Ludovico
12. Strutture dati dinamiche
Strutture dati annidate
• E’ possibile complicare a piacimento le strutture dati.
Ad esempio, è possibile creare un’istanza di HashMap i
cui valori, dovendo contenere dei generici Object,
possono essere:
–
–
–
–
variabili di tipo primitivo
enumerazioni o array
istanze di classi definite dall’utente
istanze di classi quali ArrayList o HashMap
• Un caso di moderata complessità verrà esemplificato
alla prossima slide.
Programmazione per la Musica - Prof. Luca A. Ludovico
12. Strutture dati dinamiche
ESEMPI
ScaleDictionary.java
L’esempio implementa un dizionario «tradizionale», in cui si fa corrispondere al
nome di una scala il suo modello, espresso in termini di sequenza di toni T e
semitoni s. Questo codice permette di valutare le differenze di comportamento tra
vari tipi di dizionario in merito all’ordinamento delle chiavi.
PitchDictionary.java
Nell’esempio si crea una struttura dati complessa, in particolare un HashMap di
ArrayList di stringhe, la cui finalità è permettere di supportare tutte le differenti
scritture dell’altezza delle note nelle varie lingue e formati.
Le versioni (ad esempio Do, Ut, C, 0, ecc.) verranno elencate nell’ArrayList, e lo
scopo è farle tutte collassare sul valore di una enumerazione, utilizzato come
chiave della HashMap.
Programmazione per la Musica - Prof. Luca A. Ludovico
12. Strutture dati dinamiche
ESERCIZIO
Si progetti ed implementi un questionario da sottoporre all’utente, le cui risposte
consistano nel nome di uno strumento musicale (liberamente scelto dall’utente
stesso, non estratto da un elenco predeterminato).
Una struttura dati interna di tipo dizionario, indicizzata per nome dello strumento
e costruita incrementalmente, presenterà per ciascuna chiave un contatore che
verrà incrementato ogni volta che l’intervistato risponde indicando quello
strumento.
Al termine dell’esecuzione, il programma riassumerà i risultati complessivi, ossia
mostrerà l’elenco delle chiavi (strumenti musicali) e dei valori (contatori).
Esempio di output:
Chitarra > 3
Pianoforte > 1
Flauto > 1
Programmazione per la Musica - Prof. Luca A. Ludovico
12. Strutture dati dinamiche