Strutture dati dinamiche
Paolo Bison
Fondamenti di Informatica 1 A.A. 2004/05 Universit`a di Padova
Strutture dati dinamiche, Paolo Bison, A.A. 2004-05, 2004-12-04 – p.1/24
Strutture dinamiche
strutture dati il cui numero di componenti può variare durante l’esecuzione del programma
ciascuna componente contiene espliciti riferimenti ad altre componenti
le relazioni tra componenti sono date dai valori di tali riferimenti
possibilità di strutturare i dati secondo diverse modalità liste, alberi, grafi
operare su una struttura dinamica significa modificare i riferimenti contenuti nelle singole componenti
vs. strutture statiche (array)
Strutture dati dinamiche, Paolo Bison, A.A. 2004-05, 2004-12-04 – p.2/24
Linked list
la struttura dinamica più semplice per rappresentare una lista a cui componenti possono essere aggiunti o tolti
ogni elemento della lista (nodo) contiene un riferimento all’elemento seguente
esiste una variabile che contiene il riferimento al primo elemento
riferimento nullo
indica che non ci si riferisce a nessun elemento
head
Lista vuota
lista che non ha nessun elemento
la variabile che indica il primo elemento contiene il riferimento nullo
head
Definizione ricorsiva
una lista è:
vuota
un nodo che contiene un riferimento ad una lista
Strutture dati dinamiche, Paolo Bison, A.A. 2004-05, 2004-12-04 – p.5/24
Liste in Java
nodi sono istanze di una oppurtuna classe
ClassNameche descrive l’informazione memorizzata nel nodo
variabile d’istanza di tipo
ClassNameper mantenere un riferimento al nodo successivo
riferimento nullo
indicato dal valore null
variabile di tipo
ClassNameper mantenere un riferimento al primo nodo
Strutture dati dinamiche, Paolo Bison, A.A. 2004-05, 2004-12-04 – p.6/24
Classi per i nodi
due possibilità
estendere la classe che rappresenta l’informazione del nodo aggiungendo la variabile per il riferimento public class LinkedDatum
extends Datum{
LinkedDatum next;
}
definire una classe con cui creare istanze di nodi che contengono un riferimento all’elemento successivo ed uno ai dati
public class Node{
Node next;
Datum data;
}
Strutture dati dinamiche, Paolo Bison, A.A. 2004-05, 2004-12-04 – p.7/24Operazioni su liste
inserimento
in testa
in coda
in qualunque posizione
accesso ai nodi
in testa
in coda
ricerca
iterazione
cancellazione
in testa
in coda
in qualunque posizione
confronto
copia
ordinamento
Strutture dati dinamiche, Paolo Bison, A.A. 2004-05, 2004-12-04 – p.8/24
Inserimento in testa
lista vuota
1.
head dato
2.
head dato
lista non vuota
1.
head dato
2.
head dato
3.
head dato
Strutture dati dinamiche, Paolo Bison, A.A. 2004-05, 2004-12-04 – p.9/24
Inserimento in coda
lista vuota
vedi inserimento in testa
lista non vuota
1.
head
dato
2.
head
dato tmp
3.
head tmp
dato
4.
head tmp
dato
5.
head tmp
dato
Strutture dati dinamiche, Paolo Bison, A.A. 2004-05, 2004-12-04 – p.10/24
Inserimento in una posizione qualunque
ricerca
inserimento
1.
head
dato
2.
head
dato tmp
3.
head tmp
dato
4.
head tmp
dato
head tmp
Accesso agli elementi
testa
coda
con una ricerca
si itera finchè non si trova l’elemento cercato o termina la lista
metodo equals per il confronto
con un iteratore
Iterare su una lista
interfaccia Iterator del package java.util
metodi
boolean hasNext()
Object next()
void remove()
metodo per ritornare una istanza di tipo Iterator
Strutture dati dinamiche, Paolo Bison, A.A. 2004-05, 2004-12-04 – p.13/24
Cancellazione in testa
1.
head
2.
head tmp
3.
head tmp
4.
head tmp
Strutture dati dinamiche, Paolo Bison, A.A. 2004-05, 2004-12-04 – p.14/24
Cancellazione in coda 1.
head
2.
tmp head
3.
tmp head
4.
tmp
head tmp0
5.
tmp
head tmp0
Strutture dati dinamiche, Paolo Bison, A.A. 2004-05, 2004-12-04 – p.15/24
Cancellazione in una posizione qualunque
ricerca
rimozione
1.
head
2.
tmp head
3.
tmp head
tmp0
4.
tmp head
tmp0
5.
tmp head
tmp0
Strutture dati dinamiche, Paolo Bison, A.A. 2004-05, 2004-12-04 – p.16/24
Confronto tra liste
uguaglianza metodo equals
stessi oggetti independentemente dall’ordine
stessi oggetti nel medesimo ordine
relazione d’ordine
relazione d’ordine tra gli oggetti memorizzati nelle due liste
Strutture dati dinamiche, Paolo Bison, A.A. 2004-05, 2004-12-04 – p.17/24
Copia di una lista
data una lista creare una copia di tale lista
due modi
copia dei nodi
copia dei nodi e degli oggetti
copiare un oggetto metodo clone
Strutture dati dinamiche, Paolo Bison, A.A. 2004-05, 2004-12-04 – p.18/24
metodo clone in Object
protected Object clone()
throws CloneNotSupportedException
crea e ritorna una copia dell’oggetto this
la copia è ottenuta creando una nuova istanza
inizializzata ai medesimi valori contenuti nelle variabili dell’oggetto
genera CloneNotSupportedException se la classe dell’oggetto non implementa l’interfaccia Cloneable
classe che implementa l’interfaccia deve ridefinire il metodo clone
shallow copy vs. deep copy
copia dei valori dei tipi base e “reference type”
non si fa la copia degli oggetti a cui si ha un riferimento
shallow copy
1.
0.67null234
2.
0.67null234
3.
0.67null234 234
deep copy
1.
0.67null234
2.
0.67null234
3.
0.67null234 234
4.
0.67null 0.67null234 234
5.
0.67null 0.67null234 234
Ordinare una lista
modifica algoritmi di sort
selezione
inserimento
merge-sort
inserimento ordinato
Strutture dati dinamiche, Paolo Bison, A.A. 2004-05, 2004-12-04 – p.21/24
Estensioni
variabile per riferirsi all’ultimo elemento
rende metodi di inserimento ed accesso alla coda O(1)
head tail
variabile per memorizzare il numero di elementi rende metodo che ritorna la lunghezza O(1)
Strutture dati dinamiche, Paolo Bison, A.A. 2004-05, 2004-12-04 – p.22/24
Doppio link
ogni nodo contiene due riferimenti
al nodo che lo segue
al nodo che lo precede
O (1) per metodi di inserimento e rimozione sia in testa che in coda
head tail
Strutture dati dinamiche, Paolo Bison, A.A. 2004-05, 2004-12-04 – p.23/24
Lista circolare
non vi è alcun riferimento nullo
head
Strutture dati dinamiche, Paolo Bison, A.A. 2004-05, 2004-12-04 – p.24/24
