|
|
|
|
|
|
|
Abbiamo visto esempi di attributi che si riferiscono ad altri oggetti (riferimenti interni, vedi sezione 12.8). Una struttura di dati piuttosto comune, la lista linkata, fa uso di questa caratteristica.
Le liste linkate sono costituite da nodi ed ognuno di questi nodi contiene il riferimento al successivo nodo della lista ed un'unità di dati utili chiamata contenuto.
Una lista linkata è considerata una struttura di dati ricorsiva perché la sua definizione è di per sé ricorsiva:
Una lista linkata è:
Le strutture di dati di tipo ricorsivo sono gestite da metodi ricorsivi.
Come abbiamo già visto in occasione della scrittura di nuove classi, cominciamo a scrivere la classe Nodo dalla sua inizializzazione e dal metodo __str__ così da poter testare immediatamente il meccanismo di creazione e visualizzazione del nuovo tipo:
class Nodo:
def __init__(self, Contenuto=None, ProssimoNodo=None):
self.Contenuto = Contenuto
self.ProssimoNodo = ProssimoNodo
def __str__(self):
return str(self.Contenuto)
Abbiamo definito come opzionali i parametri per il metodo di inizializzazione: di default sia Contenuto che il link ProssimoNodo hanno valore None.
La rappresentazione a stringa del nodo è solo la stampa del suo contenuto: dato che alla funzione str può essere passato qualsiasi tipo di valore possiamo memorizzare nella lista ogni tipo di dato.
Per testare l'implementazione possiamo creare un Nodo e stamparne il valore:
>>> Nodo1 = Nodo("test")
>>> print Nodo1
test
Per rendere il tutto più interessante abbiamo bisogno di una lista che contiene più di un nodo:
>>> Nodo1 = Nodo(1)
>>> Nodo2 = Nodo(2)
>>> Nodo3 = Nodo(3)
Questo codice crea tre nodi ma non siamo in presenza di una lista dato che questi nodi non sono linkati (collegati uno all'altro). Il diagramma di stato in questo caso è:
Per linkare i nodi dobbiamo fare in modo che il primo si riferisca al secondo, ed il secondo al terzo:
>>> Nodo1.ProssimoNodo = Nodo2
>>> Nodo2.ProssimoNodo = Nodo3
Il riferimento del terzo nodo è None e questo indica che ci troviamo alla fine della lista. Ecco il nuovo diagramma di stato:
Ora sai come creare nodi e come linkarli in liste. Ciò che probabilmente è meno chiaro è il motivo per cui questo possa rivelarsi utile.
Le liste sono utili perché forniscono un modo per assemblare più oggetti in una entità singola talvolta chiamata collezione. Nell'esempio che abbiamo visto il primo nodo serve come riferimento all'intera lista dato che ne rappresenta il punto di partenza.
Per passare una lista di questo tipo come parametro ad una funzione dobbiamo passare quindi soltanto il riferimento al suo primo nodo. Per fare un esempio, la funzione StampaLista prende un singolo nodo come argomento, considerandolo l'inizio della lista e stampa il contenuto di ogni nodo finché non viene raggiunta la fine della lista:
def StampaLista(Nodo):
while Nodo:
print Nodo,
Nodo = Nodo.ProssimoNodo
print
Per invocare questo metodo passiamo un riferimento al primo nodo:
>>> StampaLista(Nodo1)
1 2 3
All'interno di StampaLista abbiamo un riferimento al primo nodo della lista ma non c'è alcuna variabile che si riferisce agli altri nodi: per passare da un nodo al successivo usiamo il valore Nodo.ProssimoNodo, usando la variabile Nodo per riferirsi ad ognuno dei nodi in successione.
Questo diagramma mostra il valore di Lista ed il valore assunto da Nodo:
Esercizio: per convenzione le liste sono stampate tra parentesi quadrate con virgole che ne separano gli elementi, come in [1, 2, 3]. Modifica StampaLista così da generare una stampa in questo formato.
Data la sua natura ricorsiva è intuitivo esprimere molte operazioni sulle liste con metodi ricorsivi. Questo è un algoritmo per stampare una lista a partire dall'ultimo elemento:
Logicamente il passo 2, la chiamata ricorsiva, parte dal presupposto che ci sia un metodo per stampare la lista al contrario. Se partiamo dal presupposto che la chiamata ricorsiva funziona correttamente questo algoritmo lavora in modo corretto.
Tutto ciò di cui abbiamo bisogno è un caso base ed un modo per verificare che per ogni tipo di lista riusciremo ad arrivare al caso base per interrompere la serie di chiamate ricorsive. Data la definizione ricorsiva della lista un caso base intuitivo è la lista vuota, rappresentata da None:
def StampaInversa(Lista):
if Lista == None: return
Testa = Lista
Coda = Lista.ProssimoNodo
StampaInversa(Coda)
print Testa,
La prima riga gestisce il caso base senza fare niente. Le due righe successive dividono la lista in due parti (Testa e Coda). Le ultime due righe stampano la lista. Ricorda che la virgola alla fine del print evita la stampa del ritorno a capo tra un nodo e l'altro.
Invochiamo questo metodo come abbiamo fatto con StampaLista:
>>> StampaInversa(Nodo1)
3 2 1
Potresti chiederti perché StampaLista e StampaInversa sono funzioni e non metodi nella classe Nodo. La ragione è che vogliamo usare il valore None per rappresentare la lista vuota e non è lecito invocare un metodo su None. Questa limitazione in effetti rende poco pulito il codice, costringendo alla sua implementazione senza poter fare uso di uno stile orientato agli oggetti.
Possiamo provare che StampaInversa giungerà sempre alla fine, raggiungendo il caso base? La risposta è no e infatti la sua chiamata causerà un errore in esecuzione nel caso in cui la lista passata come parametro sia di tipo particolare.
Non c'è nulla che vieti ad un nodo di fare riferimento ad un nodo precedente della lista o addirittura a se stesso. Questa figura mostra una lista di due nodi ognuno dei quali si riferisce a se stesso:
Se invocassimo StampaLista o StampaInversa su questa lista si creerebbe una ricorsione infinita: questo tipo di comportamento rende particolarmente difficile lavorare con le liste...
Ciononostante le liste infinite possono rivelarsi molto utili in (poche) occasioni particolari, come quando vogliamo rappresentare un numero come lista di cifre usando una lista infinita per la descrizione della parte decimale periodica.
Ci rimane comunque il problema che non possiamo dimostrare che StampaLista e StampaInversa raggiungono sempre il caso base. Il meglio che possiamo fare è stabilire una precondizione, assumendo che "se non sono presenti anelli all'interno della lista questi metodi termineranno". La precondizione impone una limitazione ai parametri e descrive il comportamento di un metodo nel caso essa venga soddisfatta. Vediamo subito qualche esempio.
Una parte di StampaInversa aveva qualcosa di sospetto:
Testa = Lista
Coda = Lista.ProssimoNodo
Dopo la prima assegnazione Testa e Lista hanno lo stesso tipo e lo stesso valore. Perché dunque abbiamo creato una nuova variabile?
La ragione è che le due variabili giocano ruoli differenti. Pensiamo a Testa come riferimento ad un singolo nodo e a Lista come riferimento al primo nodo della lista. Questi "ruoli" non sono espressamente necessari al programma, ma sono molto utili per chiarire il concetto al programmatore.
In generale non possiamo dire quale ruolo giochi una variabile semplicemente guardando un programma. Spesso si usano nomi come Nodo e Lista per documentare l'uso della variabile e si introducono variabili addizionali solo per rendere meno ambiguo il codice al momento della lettura.
Avremmo anche potuto scrivere StampaInversa senza Testa e Coda. Il risultato sarebbe stato più conciso, ma decisamente meno chiaro:
def StampaInversa(Lista) :
if Lista == None : return
StampaInversa(Lista.ProssimoNodo)
print Lista,
Con un'attenzione alle due chiamate di funzione è necessario ricordarci che StampaInversa tratta il suo argomento Lista come una collezione e print il proprio come un oggetto singolo.
Il teorema dell'ambiguità fondamentale descrive l'ambiguità inerente al riferimento ad un nodo:
Una variabile che si riferisce ad un nodo può trattare il nodo come oggetto singolo o come primo elemento di una lista di nodi linkati.
Ci sono due modi per modificare una lista linkata: possiamo cambiare il contenuto di uno dei nodi o aggiungere, rimuovere o riordinare i nodi.
Come esempio scriviamo un metodo per rimuovere il secondo nodo di una lista, ritornando un riferimento al nodo rimosso:
def RimuoviSecondo(Lista):
if Lista == None: return
Primo = Lista
Secondo = Lista.ProssimoNodo
# il primo nodo deve riferirsi al terzo
Primo.ProssimoNodo = Secondo.ProssimoNodo
# separa il secondo nodo dal resto della lista
Secondo.ProssimoNodo = None
return Secondo
Ancora una volta abbiamo usato delle variabili temporanee per rendere il codice più leggibile. Ecco come usare questo metodo:
>>> StampaLista(Nodo1)
1 2 3
>>> Rimosso = RimuoviSecondo(Nodo1)
>>> StampaLista(Rimosso)
2
>>> StampaLista(Nodo1)
1 3
Questo diagramma di stato mostra l'effetto dell'operazione:
Cosa succede se invochi questo metodo e passi una lista composta da un solo elemento (elemento singolo)? Cosa succede se passi come argomento una lista vuota? C'è una precondizione per questo metodo? Se esiste riscrivi il metodo per gestire gli eventuali problemi.
Spesso è utile dividere un'operazione su una lista in due metodi. Per esempio per stampare una lista al contrario secondo il formato convenzionale [3, 2, 1] possiamo usare il metodo StampaInversa per stampare 3, 2, ma abbiamo bisogno di un metodo diverso per stampare le parentesi ed il primo nodo. Chiamiamo questo metodo StampaInversaFormato:
def StampaInversaFormato(Lista) :
print "[",
if Lista != None :
Testa = Lista
Coda = Lista.ProssimoNodo
StampaInversa(Coda)
print Testa,
print "]",
Ancora una volta è una buona idea testare questo metodo per vedere se funziona correttamente anche in casi particolari, quando cioè una lista è vuota o composta da un solo elemento.
Quando usiamo questo metodo da qualche parte nel programma invochiamo direttamente StampaInversaFormato e questa invoca a sua volta StampaInversa. In questo senso StampaInversaFormato agisce come un contenitore che usa StampaInversa come aiutante.
Dal modo in cui abbiamo implementato le liste sorgono dei problemi concettuali piuttosto sottili. Procedendo in modo diverso dal consueto proporremo un'implementazione alternativa spiegando solo in seguito quali problemi vengono risolti da questa nuova versione.
Creiamo innanzitutto una nuova classe chiamata ListaLinkata. I suoi attributi sono un intero che contiene la lunghezza della lista e il riferimento al primo nodo. Gli oggetti ListaLinkata ci serviranno per gestire liste di oggetti Nodo:
class ListaLinkata:
def __init__(self) :
self.Lunghezza = 0
self.Testa = None
Una cosa positiva per quanto concerne la classe ListaLinkata è che fornisce un posto naturale dove inserire funzioni contenitore quale StampaInversaFormato e che possiamo far diventare metodi della classe:
class ListaLinkata:
...
def StampaInversa(self):
print "[",
if self.Testa != None:
self.Testa.StampaInversa()
print "]",
class Nodo:
...
def StampaInversa(self):
if self.ProssimoNodo != None:
Coda = self.ProssimoNodo
Coda.StampaInversa()
print self.Contenuto,
Per rendere le cose più interessanti, rinominiamo StampaInversaFormato. Ora abbiamo due metodi chiamati StampaInversa: quello nella classe Nodo che è l'aiutante e quello nella classe ListaLinkata che è il contenitore. Quando il metodo contenitore invoca self.Testa.StampaInversa sta in effetti invocando l'aiutante dato che self.Testa è un oggetto di tipo Nodo.
Un altro beneficio della classe ListaLinkata è che rende semplice aggiungere o rimuovere il primo elemento di una lista. AggiuntaPrimo è il metodo di ListaLinkata per aggiungere un contenuto all'inizio di una lista:
class ListaLinkata:
...
def AggiuntaPrimo(self, Contenuto):
NodoAggiunto = Nodo(Contenuto)
NodoAggiunto.ProssimoNodo = self.Testa
self.Testa = NodoAggiunto
self.Lunghezza = self.Lunghezza + 1
Come sempre occorre verificare che questo codice funzioni correttamente anche nel caso di liste speciali: cosa succede se la lista è inizialmente vuota?
Alcune liste sono "ben formate" mentre altre non lo sono. Se una lista contiene un anello questo può creare problemi a un certo numero dei nostri metodi, tanto che potremmo richiedere solo liste che non contengono anelli al loro interno. Un altro prerequisito è che il valore di Lunghezza nell'oggetto ListaLinkata corrisponda sempre al numero di nodi della lista.
Prerequisiti come questi sono chiamati invarianti perché dovrebbero essere sempre verificati in ogni momento per ogni oggetto della classe. Specificare gli invarianti degli oggetti è una pratica di programmazione molto indicata in quanto consente di rendere molto più facile la verifica del codice, il controllo dell'integrità delle strutture e il riconoscimento degli errori.
Una cosa che può rendere confusi per quanto riguarda gli invarianti è che a volte i prerequisiti che essi rappresentano possono essere violati, anche se solo temporaneamente: nel metodo AggiungiPrimo, dopo aver aggiunto il nodo ma prima di avere aggiornato Lunghezza, il prerequisito invariante non è soddisfatto. Questo tipo di violazione è accettabile, dato che spesso è impossibile modificare un oggetto senza violare un invariante almeno per un breve istante. Normalmente richiediamo che qualsiasi metodo che si trovi a violare un invariante lo ripristini non appena possibile.
Se l'invariante è violato in una parte significativa del codice è molto importante commentare questo comportamento anomalo per evitare che, anche a distanza di tempo, possano essere richieste delle operazioni che dipendono dall'integrità dei dati proprio dove questi dati non sono corretti.
|
|
|
|
|
|
|