Strutture dati dinamiche

Strutture dati dinamiche

Paolo Bison

Fondamenti di Informatica 1 A.A. 2004/05

Universit`a di Padova

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

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

Liste in Java



nodi sono istanze di una oppurtuna classe ^ClassName che descrive l’informazione memorizzata nel nodo



variabile d’istanza di tipo ^ClassName per mantenere un riferimento al nodo successivo



riferimento nullo

indicato dal valore null



variabile di tipo ^ClassName per mantenere un

riferimento al primo nodo

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;

Operazioni 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

Inserimento in testa



lista vuota

1.

head

dato

2.

head

dato



lista non vuota

1.

head dato

2.

head dato

3.

head dato

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

head tmp

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

Cancellazione in testa

1.

head

2.

head tmp

3.

head tmp head

Cancellazione in coda 1.

head

2.

tmp head

3.

tmp head

4.

tmp

head tmp0

5.

tmp

head tmp0

Cancellazione in una posizione qualunque



ricerca



rimozione

1.

head

2.

tmp head

3.

tmp head

tmp0

4.

tmp head

tmp0

tmp head

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

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

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.

234

2.

234

3.

234 234



deep copy

1.

234

2.

234

3.

234 234

Ordinare una lista



modifica algoritmi di sort



selezione



inserimento



merge-sort



inserimento ordinato

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)

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

Lista circolare



non vi è alcun riferimento nullo

head