Caricare documenti e articoli online 
INFtub.com è un sito progettato per cercare i documenti in vari tipi di file e il caricamento di articoli online.


 
Non ricordi la password?  ››  Iscriviti gratis
 

Introduzione alla ricorsione, ai puntatori e alle liste - Programmi e ricorsione (tramite un caso di studio: il sort)

informatica



PROGRAMMAZIONE 2


Appunti del Corso




PARTE PRIMA

Introduzione alla ricorsione, ai puntatori e alle liste



INDICE




Indice dei Capitoli


Programmi e ricorsione (tramite un caso di studio: il sort) 3

Un metodo di soluzione: il Selection Sort

1.1.bis Il Selection Sort (continua) ...............

Un altro modo per ordinare una sequenza: 'merge-sort' 13

Implementazione di merge-sort 15

Implementazione di merge-sort con una classe MioVett

Le Liste 21

Vettori e liste: alcuni vantaggi e svantaggi 26

Altre operazioni sulle liste 28

La classe LinkedList di Java 31

Ancora sulla memoria 31

Le eccezioni in Java

Input e output con files

Merge-Sort sulle liste 41



Indice dei Richiami di Java


1: Generalità .......... ..... ...... 4

2: Vettori .......... ..... ...... 5

3: Spazio di memoria    .................... 6

4: Passaggio dei parametri ai metodi ................... 9

5: Metodi statici ............................ 11


Indice delle Procedure e dei Programmi


Proc. 1 - Selection Sort - Versione 0 .....................    8

Proc. 2 - Il main della classe MioProg, che usa Selection Sort 0 ..........    12

Proc. 3 - Merge di vettori - Versione 1 ................... 16

Proc. 4 - Merge Sort - Versione 1 ...................... 17

Proc. 5 - Merge Sort - Versione 2 ...................... 18

Proc. 6 - La Classe MioVett ......................... 20

Proc. 7 - Un programma che usa la Classe MioVett ................ 21

Proc. 8 - printList: visualizza gli elementi di una lista ................ 23

Proc. 9 - I metodi getFirstDato e advance .................... 24

Proc. 10 - I metodi insertFirst e deleteFirst .................... 25

Proc. 11 - in_lista: C'e' un elemento in una lista? ....................    28

Proc. 12 - modifElem: Modifica un elemento di una lista ..............    28

Proc. 13 - insertAfter: Inserisci un elemento in una lista 'dopo' un elemento specificato 29

Proc. 14 - deleteElem: Cancella un elemento da una lista ..............    30

Proc. 15 - getFirstDato e printList con trattamento delle eccezioni .......... 36

Proc. 16 - readListFromFile: Leggi una lista da un file .............. 38

Proc. 17 - Operazioni di base sulle liste .................... 40

Proc. 18 - splitList: dividi una lista in due metà (versione 1) ............ 43

Proc. 19 - splitList: dividi una lista in due metà (versione 2) ............ 45

Proc. 20 - mergeList: merge di due liste ordinate ................ 48

Proc. 21 - sortList: ordinamento di una lista .................. 49




Indice delle figure


Figura 1: Classi e oggetti nell'ambiente Java ................. 5

Figura 2: Allocazione dello spazio: lo stack e lo heap ........... 7

Figura 3: Rappresentazione semplificata del riferimento ad un vettore .... 8

Figura 4: Passaggio ad un metodo di un valore intero (non ok) .... .... 10

Figura 5: Passaggio ad un metodo di un valore intero (ok) ...... .... 11

Figura 6: Variabili di istanza della classe MioVett .... ...... .... 19

Figura 7: Struttura di una lista generica .... .... ...... ....    21

Figura 8: Struttura di una istanza della classe MiaLista ... ...... .... 23

Figura 9: Implementazione di una lista con le classi MiaLista e ListElem .... 23

Figura 10: Realizzazione di un cursore su una lista: loopElem .... .... 24

Figura 11: Avanzamento di un cursore su una lista: loopElem .... .... 24

Figura 12: Un cursore realizzato in modo errato ...... .... ....    25

Figura 13: Eliminazione di un elemento da una lista .... .... ....    26

Figura 14: Inserimento di un elemento in una lista ..... .... ....    27

Figura 15: Realizzazione di un cursore su una lista: loopElem (ripetizione) ... 30

Figura 16: Allocazione di un nuovo blocco sullo stack ........... ... 32

Figura 17: Allocazione di blocchi sullo stack in caso di chiamate ricorsive ... 33

Figura 18: Contenuto di un blocco sullo stack ............... ... 33

Figura 19: Rientri da metodi in presenza di una situazione di errore ...... ... 35

Figura 20: Split di una lista ................... ...... ... 42

Figura 21: Un altro modo per fare lo split di una lista ........ ...... ... 44

Figura 22: Split: situazione iniziale ................. ...... ... 45

Figura 23: Prima di un passo di split ................ ...... ...    45

Figura 24: Dopo il passo di split .................. ...... ...    45


Programmi e Ricorsione


La programmazione è un'attivita' creativa. Non si tratta, infatti di imparare a memoria delle formule o delle leggi, bensì di inventare delle soluzioni per dei problemi. Deve essere chiaro che il punto chiave non è la scrittura del programma (cosa che voi comunque dovrete fare in Java, ma avreste potuto fare con altri linguaggi, come C, Prolog, o Lisp), bensì la scoperta del modo per ottenere il risultato.


Supponiamo che a un impiegato il capufficio dia un pacco di 200 fogli dicendogli:

"Queste sono delle nuove fatture. Le vorrei in ordine alfabetico tra mezz'ora!"

Indipendentemente da qualunque calcolatore, o linguaggio di programmazione, l'impiegato dovrà trovare un modo (o un metodo, o un algoritmo) per fare il lavoro, e cioè per effettuare un 'sort' dei fogli. E' possibile che, con un metodo efficiente, l'impiegato termini il lavoro nel tempo richiesto, mentre con un metodo meno efficiente può non rispettare i tempi.


Allo stesso modo, se debbo trovare una parola in un vocabolario, non comincio dalla prima pagina e poi procedo pagina per pagina fino ad arrivare alla parola desiderata, ma applico un metodo (cioè un algoritmo) che rende la ricerca più rapida.


Non si devono quindi confondere due aspetti della programmazione:

Trovare il metodo di soluzione

Tradurre tale metodo nel linguaggio di programmazione che si vuole (o si deve) usare.



1.1 Un metodo di soluzione: il Selection Sort


L'impiegato che deve ordinare i 200 fogli può inizialmente pensare di farlo nel modo seguente:


Beh, mi scorro tutta la pila di fogli, e trovo quello col nominativo che in ordine alfabetico viene prima; lo tolgo dalla pila e lo metto sul tavolo. Poi nella pila rimanente cerco quello, di nuovo, col primo nome in ordine alfabetico e lo metto sopra il primo, e così via. Però poi la pila mi viene all'incontrario e devo invertirla. Forse posso cominciare dall'ultimo; o magari dal primo, ma mettendo i fogli sul tavolo rovesciati. Già, però quanto ci metto a fare 'sto lavoro?


Il povero impiegato non sa che ha a che fare con un (per nulla banale) problema di 'sort'. E la soluzione che ha adottato è simile a quella nota col nome di 'Selection Sort' (e che, purtroppo per lui, non è per nulla efficiente). Proviamo a vedere quanto tempo gli ci vorrà per finire il lavoro.


Supponiamo innanzitutto che per verificare il nominativo su un foglio (e per confrontarlo con quello che è attualmente il primo in ordine alfabetico tra tutti quelli già esaminati) ci voglia un secondo. La prima volta , per trovare il primo in ordine alfabetico, dovrà guardare tutti i 200 fogli (200 secondi); estratto il primo, per trovare il secondo dovrà guardare solo i 199 fogli rimanenti (199 secondi); per il terzo 198 fogli (198 secondi), e così via. Il tempo totale è, ovviamente:

(200 + 199 + 198 + 197 + 196 + ... + 5 + 4 +3 + 2 + 1) secondi

E' chiaro che, se il nostro impiegato si mette a fare la somma, esaurisce già il suo tempo. Ma noi sappiamo che, con il seguente semplice ragionamento (che voi dovreste già conoscere) si fa prima:


200 + 199 + 198 + 197 + 196 + ... + 102 + 101 +

1 + 2 + 3 + 4 + 5 + ... + 99 + 100 =

= = = == = == = == = == = == = =

201 + 201 + 201 + 201 + 201 + ... + 201 + 201


E cioe' la somma dei primi 200 numeri equivale a sommare 100 volte il valore 201; la formula generale e':

(n/2)*(n+1) (nel nostro caso n=200)

Per cui, il tempo totale sara' di 20100 secondi . Ahiahiahi: sarebbero 5 ore e 35 minuti.


Prima di vedere se si sarebbe potuto fare meglio, cerchiamo di capire le differenze tra l'esempio dell'impiegato e un ordinamento (ad es. di un vettore) su un calcolatore. L'unica differenza rilevante è che in un calcolatore non c'è il tavolo (quello su cui posare i fogli estratti). Ma non si può fare finta di averlo? Beh, se i 200 fogli sono 'rappresentati' da un vettore, il modo più semplice per 'fare finta' di avere un tavolo è quello di simulare un posto dove mettere i fogli (valori) estratti. Questo può essere fatto introducendo un secondo vettore (che conterrà il risultato). Però, a livello di strutture dati, questo non basta. Debbo anche 'simulare' di togliere il foglio dalla pila. E questo, lavorando su un vettore non è per nulla comodo (uso 'non comodo' per dire che è facile scrivere il programma, ma che l'operazione è molto lenta). Infatti, per simulare di aver tolto il 50-esimo foglio devo spostare tutti gli elementi successivi del vettore (cioè devo mettere vett[51] in vett[50], poi vett[52] in vett[51], e così via fino all'assegnazione di vett[200] a vett[199]). Dopodichè devo aggiornare la dimensione della pila (che passa da 200 a 199 fogli). Naturalmente vett[200] esiste ancora, ma è come se fosse vuoto. Questa versione del selection sort è proprio 'scarsa', ma, per curiosità, la riporto sotto, dopo alcuni richiami di Java.



Richiami di Java 1: Generalità


I concetti fondamentali del linguaggio Java sono stati introdotti nel corso di Programmazione I. Penso però sia bene ricordare alcune idee fondamentali, prima di scrivere il programma per il Selection Sort in Java.


Contrariamente a quello che avviene in altri linguaggi di programmazione, il concetto di 'programma' in Java è secondario. Il concetto primario è infatti quello di Oggetto (infatti, Object-Oriented Programming: Programmazione Orientata agli Oggetti). Voi dovete immaginare il vostro programma come situato all'interno di un enorme scatolone che contiene oggetti. Il vostro compito, per scrivere il programma, è quindi quello di inserire nello scatolone un nuovo insieme di oggetti, che si comportino in modo tale da realizzare ciò che voi volete faccia il programma.


Nello scatolone vi sono due tipi di oggetti: Classi e Istanze. Una classe è la definizione di un certo tipo di oggetti. Un'utile analogia può essere quella delle specie naturali: Gatto è una classe (una specie, o tipo), mentre i vari gatti che ci sono al mondo sono istanze della classe Gatto. Mentre è evidente che le istanze hanno delle proprietà caratteristiche (per un gatto il colore, l'età, il peso, etc.), meno ovvio è che anche le classi hanno delle caratteristiche. Ad esempio, per la classe Gatto l''età massima' per un gatto, e magari l'indirizzo di un veterinario esperto in gatti.


Poiché esistono solo oggetti[1], che sono delle cose statiche, ma noi vogliamo 'fare delle cose' con gli oggetti, ci si deve chiedere come questo può essere realizzato. La risposta è semplice: mandando dei messaggi agli oggetti. Se, ad esempio, invio il messaggio "Pappa" al mio gatto (che è una istanza), provoco una reazione: il mio gatto viene verso di me. Perché questo avviene? Perché il mio gatto, dentro la testa, ha un metodo che gli permette di riconoscere alcuni (semplici) messaggi vocali e di reagire opportunamente ad essi. Esattamente la stessa cosa avviene per gli oggetti di Java: un oggetto è in grado di rispondere a un messaggio solo se ha al proprio interno un metodo, che gli dice come comportarsi in risposta al messaggio. All'interno di questo metodo, l'oggetto in questione potrà inviare messaggi ad altri metodi e operare in base alla risposta a questi messaggi, fino a completare l'attività richiesta dal messaggio iniziale (il mio gatto è venuto da me).


Ora però sorge un problema: come fare a mandare il messaggio all'oggetto giusto? (se io grido 'Pappa' nello scatolone, arriveranno alcune decine di gatti, non solo il mio). Ebbene, lo scatolone di oggetti è organizzato in scatole più piccole al suo interno. Una di queste scatole è il file che contiene gli oggetti che compongono il mio programma. Ma anche all'interno di questa scatola vi sono tanti oggetti; coma si fa a sapere qual è quello giusto? semplicemente quello che ha come 'nome' lo stesso nome della scatola (cioè del file).






















Figura 1: Classi e oggetti nell'ambiente Java



Nella figura 1, compaiono un po' di classi (nel vero ambiente Java ve ne sono centinaia) e ho inserito anche 4 istanze di gatti. Ho anche evidenziato la connessione tra i gatti e la classe Gatto (in Java, ogni istanza è membro di una classe). MioPro è la scatola che contiene le classi che ho definito nel mio file-programma (ce ne sono due, e una di esse deve, appunto, chiamarsi MioPro).


Però, la classe MioPro può essere in grado di rispondere a messaggi diversi. Come faccio a richiedere proprio l'esecuzione (in generale) del programma? Sono obbligato a inserire tra i vari metodi il metodo main: questo è il metodo che verrà applicato quando viene richiesta l'esecuzione del programma.


Vista l'organizzazione delineata sopra, in Java, a differenza che in altri linguaggi di programmazione, la prima cosa da fare non è tanto decidere quali "procedure" (che sarebbero i nostri metodi) servono, bensì decidere quali sono gli oggetti coinvolti (innanzitutto, quali classi). Se ci riferiamo di nuovo all'esempio dell'impiegato, i tipi di oggetti coinvolti sono le 'fatture'; sarà quindi necessario definire una classe Fattura. Ciascuna istanza di Fattura, dovrà includere, al proprio interno un Nominativo, che specificherà chi ha emesso la fattura, e che servirà all'impiegato per effettuare l'ordinamento. Per ora, non preoccupiamoci di questo (le Classi possono essere strutturate al loro interno); poiché a noi interessa l'algoritmo di ordinamento, e non i dettagli dell'esempio dell'impiegato, supponiamo di dover semplicemente ordinare dei numeri interi. In questo caso, non mi serve una nuova classe, perché il tipo di dato 'numero intero' è già predefinito.


Però noi non dobbiamo lavorare su singoli numeri interi, ma su un gruppo di numeri (200, nell'esempio). Ovviamente, sarebbe possibile introdurre 200 variabili diverse di tipo int, e cioè num1,

num2, num3, . num200, ma poiché le operazioni che dobbiamo fare si ripetono uguali per tutti i numeri, è molto più conveniente usare una struttura dati composta, ad esempio un vettore (potete provare, come utile esercizio, a scrivere il metodo per l'ordinamento di 10 numeri che utilizza il Selection Sort, usando 10 variabili intere invece di un vettore di 10 elementi; ve lo sconsiglio con 200).



Richiami di Java 2: Vettori


Come tutte le altre cose, i vettori in Java sono degli oggetti. Sono, in particolare degli oggetti compositi, formati da altri oggetti più semplici, tutti dello stesso tipo (e cioè, tutti gli elementi di un vettore sono istanze della stessa classe). Per ora, mi limiterò a considerare vettori di numeri. Sebbene i vettori siano oggetti, essi sono di uso molto comune, per cui Java permette delle espressioni più semplici di quelle standard per trattare i vettori. In particolare, come vedremo, non è sempre necessario utilizzare la new per creare un nuovo vettore.


Una caratteristica fondamentale dei vettori in Java (come in molti altri linguaggi) è che essi hanno una dimensione fissa. Vi sono due modi per specificare la dimensione di un vettore. Il primo è quello di far coincidere la dichiarazione di esistenza del vettore con la sua inizializzazione:


int [] mioVettore = ;


Le due parentesi quadre (aperta e chiusa) informano il compilatore Java che mioVettore non è una variabile intera (Int), ma è, appunto, un vettore di variabili intere. Il contenuto della parentesi graffa specifica i valori iniziali degli elementi del vettore; poiché nella parentesi ci sono 5 valori, allora il vettore sarà formato da 5 elementi. Nel seguito del programma sarà possibile riferirsi ai singoli elementi del vettore tramite l'espressione


mioVettore [ind]


Dove ind è una variabile (o una costante) intera che può assumere un valore da 0 a 4: purtroppo, in Java, il primo elemento è sempre individuato dall'indice 0, e non 1, come sarebbe più naturale. In questo caso, se io scrivessi:


mioVettore [5] oppure

mioVettore [7] oppure

mioVettore [var] in cui var abbia attualmente un valore maggiore di 4,


otterrei una segnalazione di errore e il programma si interromperebbe!


In alcuni casi non è però possibile fornire subito i valori degli elementi che compongono il vettore. Supponiamo, ad esempio, di voler costruire un nuovo vettore che abbia gli elementi in ordine inverso rispetto a mioVettore. In questo caso il risultato (supponiamo si chiami nuovoVettore) dovrà essere lungo 5, ma non so quali sono i valori (ovviamente so quali sono i valori, in questo semplice esempio, ma non voglio fare l'inversione a mano, voglio che la faccia il programma). In un caso come questo, debbo definire un vettore nuovo di 5 elementi interi 'vuoti'. Questo posso farlo con due istruzioni:


int [] nuovoVettore;

nuovoVettore = new int[5];


Si sono qui separate le due fasi: prima si dichiara l'esistenza dell'oggetto nuovoVettore, specificandone la classe (vettore di interi); in altre parole dico che nuovoVettore è una istanza della classe vettore di interi; poi, separatamente, chiedo a Java di creare tale istanza, riservando lo spazio necessario e mettendo dentro la variabile nuovoVettore un riferimento allo spazio (locazione di memoria) che è stato riservato per esso. Notate che se io usassi l'espressione nuovoVettore[2] prima di aver effettuato la new, avrei una segnalazione di errore, perché il vettore non esiste ancora!



Richiami di Java 3: Spazio di memoria


Poiché sopra ho parlato di 'riservare lo spazio' per il vettore, è opportuno ricordare come viene gestita la memoria in Java.


L'area di memoria disponibile ad un programma Java è ripartita in due sezioni: lo stack e lo heap. Come dicono i nomi, lo stack (pila) è strutturato, mentre lo heap (mucchio) non ha una struttura predefinita. Scopo dello stack è mantenere le informazioni necessarie per l'esecuzione dei singoli metodi, mentre tutti gli oggetti Java sono memorizzati nello heap. Parliamo, per ora, dello heap.


3.1 Lo heap


Lo heap può essere visto come una lunga sequenza di celle di memoria. Quando un metodo richiede la creazione di un nuovo oggetto (new), Java deve trovare dentro questa sequenza lo spazio libero necessario per l'oggetto. Nel caso dei vettori, lo spazio necessario deve essere costituito da una sequenza di celle adiacenti. Cioè, se si vuole creare un vettore di 5 interi, Java dovrà trovare una quantità di spazio libero sufficiente per memorizzare 5 interi, cioè 20 bytes[2]. Una volta fatto ciò, dovrà fornire al metodo che ha richiesto la creazione qualcosa che gli permetta di accedere allo spazio riservato; ciò che Java fornisce al metodo è un riferimento al vettore. Il termine riferimento è piuttosto astratto: questo è fatto di proposito per evitare di legarsi ad una particolare implementazione. Se può aiutare, si può pensare al riferimento ad un vettore come all'indirizzo della prima cella di memoria riservata per il vettore, ma Java, di per sé, non dice come deve essere realizzato un riferimento, dice solo come funziona!


Il riferimento viene inserito in una locazione di memoria, di cui il metodo conosce la posizione. In questo modo, quando il metodo usa un'espressione come mioVettore[2], è possibile determinare la posizione della cella che contiene il terzo elemento del vettore. Ma dove viene in realtà messo il riferimento? Esso viene posto all'interno dello stack. Vediamo allora brevemente come viene gestito lo stack.


3.2 Lo stack


Ogni volta che inizia l'esecuzione di un metodo, sullo stack viene riservata una quantità di spazio (record di attivazione, o blocco) pari a quella (determinata dal compilatore) necessaria per i parametri e le variabili locali del metodo. Quando il metodo inizia l'esecuzione, è nota la posizione iniziale del blocco sullo stack ad esso associato (ad esempio, il blocco inizierà dalla cella 124.001) e, per ogni parametro o variabile del metodo, è nota la sua posizione all'interno del blocco (ad esempio, il riferimento a mioVettore si troverà nella quarantesima cella del blocco). A questo punto, dovrebbe essere ovvio come si fa ad accedere ad un elemento del vettore. Se, ad esempio, bisogna leggere il valore di mioVettore[3], si prende la posizione del blocco sullo stack associato al metodo che si sta eseguendo (124.001), ad essa si somma la posizione del riferimento all'interno del blocco meno 1 (124.001+40-1); in questa cella (124.040) ci sarà il riferimento al vettore (ad es. 302.024, se il riferimento è costituito da un indirizzo); a questo punto, se ogni intero occupa una cella, e poiché le celle del vettore sono adiacenti, è immediato determinare la posizione della cella voluta: 302.024+3 = 302.027. Si noti che qui non è necessario togliere 1, proprio perché la numerazione degli elementi del vettore parte da 0. La situazione è dunque quella mostrata nella figura 2:























Figura 2: Allocazione dello spazio: lo stack e lo heap




Suggerisco di studiare bene il disegno di figura 2: questo è l'unico modo per comprendere bene come funzionano i riferimenti in Java. Notate che tutti i numeri che ho usato sono casuali: lo stack potrebbe iniziare da qualsiasi indirizzo di memoria, così pure come lo heap (basta che non si sovrappongano, ovviamente). Naturalmente, sia leggere che disegnare una figura come quella sopra richiede parecchio tempo, per cui, più frequentemente, si usano rappresentazioni come quelle in figura 3. Anch'io farò altrettanto, ma deve essere chiaro che solo la figura 2 chiarisce davvero come viene utilizzato lo spazio di memoria in Java.














Figura 3: Rappresentazione semplificata del riferimento ad un vettore



1.1.bis Un metodo di soluzione: il Selection Sort (continua)


Possiamo finalmente tornare al Selection Sort. Il metodo che realizza tale algoritmo è riportato nel riquadro Proc.1. Esso è costituito da un unico ciclo for, che viene ripetuto tante volte quanti sono gli elementi del vettore. Notate che il controllo di fine ciclo è i < size, strettamente minore, non minore o uguale, proprio perché la numerazione parte da 0 e termina a size-1. All'interno del ciclo si fanno 4 operazioni (notate l'utilità di un buon allineamento delle righe del metodo!). Queste 4 operazioni hanno lo scopo di trovare l'elemento più piccolo tra quelli non ancora esaminati e di metterlo nella posizione corretta nel vettore. Per far ciò, si suppone che l'elemento più piccolo sia il primo tra quelli non esaminati, si mette il suo valore nella variabile minval, e la sua posizione nella variabile minind (inizializzazione della ricerca: prime due operazioni del ciclo). Poi, si esaminano tutti quelli rimanenti (ciclo 'for' interno: terza operazione del ciclo). Se si trova un elemento più piccolo di quello trovato finora, lo si mette in minval, e si mette la sua posizione in minind. Alla fine del 'for' interno, in minval avremo il valore più piccolo e in minind la sua posizione nel vettore. Se l'elemento più piccolo non è nella posizione corretta ('if': quarta operazione del ciclo), si effettua uno scambio (body dell'if).




static void selectionSort0 (int [] argVett, int size)

; // Fine del 'for' interno

if (minind != i)


} // Fine del 'for' esterno

} // Fine del Selection Sort !


Proc.1 - Selection Sort - Versione 0



Per quanto riguarda il 'for' esterno, esso inizia dal primo elemento del vettore ed esamina tutti gli elementi. Al termine del loop interno avrà trovato l'elemento più piccolo di tutti. Se esso è già in prima posizione, non fa nulla, altrimenti lo scambia con quello in prima posizione. A questo punto in argVett[0] c'è sicuramente l'elemento più piccolo, la variabile di ciclo i viene incrementata, e inizia la ricerca dell'elemento più piccolo da argVett[1] (secondo elemento del vettore) in avanti.


Per cui nel selection sort che vedete nel riquadro, invece di togliere il foglio, lo si scambia col primo non ancora ordinato. Così non c'è bisogno di un secondo vettore (risparmio di spazio) e non c'è bisogno di modificare la dimensione della pila, nè di spostare i fogli successivi (risparmio di tempo). Come potete osservare, lo 'spazio' reale non è del tutto analogo a quello del calcolatore (ma immaginate che l'impiegato non avesse un tavolo su cui appoggiarsi e dovesse fare tutto il lavoro con i fogli sulle ginocchia). E anche il 'tempo' reale non è lo stesso di quello del calcolatore: scambiare a mano due fogli in una pila richiede magari 10 volte più tempo che controllare un nome su un foglio, mentre scambiare due elementi di un vettore può richiedere 2 o 3 volte più tempo che controllare il valore di un elemento.


In ogni caso, il metodo realizzato rimane molto inefficiente. Prima di vedere se si può trovare un metodo migliore, però, riprendiamo un altro argomento fondamentale in Java (così come in ogni altro linguaggio di programmazione): il passaggio dei parametri.


Richiami di Java 4: Passaggio dei parametri ai metodi


Supponiamo di voler ordinare il vettore mioVettore, che, come abbiamo visto, è memorizzato nello heap. Per far ciò, visto che per ora l'unico metodo che conosciamo è SelectionSort0, non possiamo fare altro che applicare a mioVettore tale metodo. Questo si ottiene con l'espressione


selectionSort0 (mioVettore, 5);


In questo modo, io ho mandato un messaggio (vedremo nel prossimo paragrafo chi è il ricevente di questo messaggio), in cui si chiede di applicare il metodo SelectionSort0, a mioVettore, informando anche il metodo che mioVettore è composto da 5 elementi. Quando SelectionSort0 inizia l'esecuzione, però, si trova ad eseguire delle operazioni su argVett, e non su mioVettore! Per comprendere come questo può funzionare, è necessario guardare di nuovo la figura 2. Quando SelectionSort0 inizia l'esecuzione, viene riservato dello spazio sullo stack (supponiamo sia proprio quello disegnato in grigio, che inizia dalla posizione 124.001). Chi ha inviato il messaggio, ovviamente, sa dove si trova mioVettore (e cioè a partire dalla cella 302.024). Inoltre, sia chi ha inviato il messaggio, sia il metodo SelectionSort0 sanno anche che la posizione in cui sono memorizzate le informazioni sul primo argomento (mioVettore per il mittente, argVett per il ricevente) sono nella quarantesima posizione del blocco sullo stack: è sufficiente che il mittente copi in tale cella il riferimento a mioVettore. Quindi, durante l'esecuzione, SelectionSort0, andrà a prendere dalla cella 124.040 il riferimento a argVett, e andrà quindi ad agire sulle celle di memoria in cui mioVettore è stato memorizzato. In questo modo, qualunque operazione, sia per leggere che per scrivere il vettore, viene in realtà effettuata su mioVettore. Di conseguenza, quando le operazioni di SelectionSort0 sono terminate, chi ha inviato il messaggio si troverà mioVettore ordinato.


E' necessario però ricordarsi che quasi tutti gli elementi di Java sono oggetti, non proprio tutti! Come si è visto nel §1.3, i tipi di base (interi, reali, caratteri, booleani), NON sono oggetti. Di conseguenza, per questi elementi, nonostante il modo per il passaggio dei parametri sia esattamente lo stesso, il risultato dell'esecuzione di un metodo è differente.


Cosa intendo, quando dico che il modo di passaggio dei parametri è esattamente lo stesso? Semplicemente, che ciò che deve fare il metodo che invia il messaggio è la stessa cosa in entrambi i casi: copiare un valore nella cella opportuna dello stack. La differenza sta nel fatto che nel caso degli oggetti (tra cui i vettori) ciò che viene copiato è il riferimento all'oggetto, mentre nel caso dei tipi di base ciò che viene copiato è il valore stesso (non c'è nessun oggetto cui riferirsi). Ma, come dicevo, l'effetto dell'esecuzione del metodo è molto differente. Supponiamo di usare un metodo per raddoppiare il valore di un intero:


static void raddoppia (int mioNumero)

;


Sebbene il metodo sia corretto, un messaggio come il seguente (che, ad esempio, compaia nel main) non ottiene il risultato voluto:


int numeroInput = 147;

raddoppia (numeroInput);


Per comprendere perché, supponiamo che anche i numeri siano oggetti veri e propri. Allora la situazione, all'atto dell'esecuzione del metodo, sarebbe quella di figura 4. Non preoccupiamoci, per ora di dove si trova la cella associata a numeroInput (sarà anch'essa sullo stack); ciò che importa è che è stata copiata la freccia (e cioè il riferimento ad un oggetto nello heap, che contiene il valore 147. E' importante che facciate attenzione! Copiare la freccia, vuol dire semplicemente copiare il numero (presumibilmente un indirizzo) che è contenuto nella cella da cui la freccia parte! Confrontate ancora le figure 2 e 3. La freccia si usa solo per comodità di chi guarda la figura: non ci sono frecce in Java! Ora, se io facessi in questa situazione mioNumero = mioNumero*2, tutto sarebbe OK: Java utilizza il riferimento per recuperare il valore (147) , e poi lo stesso riferimento per scrivere il valore raddoppiato; per cui, nella cella dello heap andrebbe a finire il valore 294. Quando il metodo termina, il riferimento numeroInput individuerebbe il valore 294, come desiderato. Questo è proprio quello che succede in SelectionSort0, in cui il primo argomento è un vettore, e cioè un oggetto.






























Figura 4: Passaggio ad un metodo di un valore intero SE i numeri interi fossero oggetti (ma non è così!)




Ma la situazione non è quella di figura 4, bensì quella di figura 5! Notate che il passaggio del parametro è avvenuto esattamente come prima: il contenuto di numeroInput è stato copiato in mioNumero. Solo che questa volta, il contenuto è di tipo diverso: non è un riferimento, ma un valore. Per cui, quando il metodo preleva il valore iniziale di mioNumero, lo preleva dallo stack, e quando va a modificare tale valore, lo modifica sullo stack. E' chiaro, quindi, che in questo caso il valore di numroInput rimane invariato (quando il metodo termina l'esecuzione, la sua porzione di spazio sullo stack viene rilasciata, per cui anche della modifica di mioNumero non rimane più traccia). Come si può fare, allora? In questo caso, bisogna scrivere un metodo che non sia void. Il metodo, cioè, anziché modificare esso stesso il valore, dovrà 'restituire' al mittente del messaggio il valore desiderato:


static int raddoppia (int mioNumero)

;


e il metodo che vuole raddoppiare il numero dovrà fare:


numeroInput = raddoppia (numeroInput);


Sarà cioè compito del mittente prendere il valore restituito dal metodo e memorizzarlo nella variabile.

























Figura 5: Passaggio effettivo ad un metodo di un valore intero. La modifica interna al metodo non ha l'effetto desiderato!





Richiami di Java 5: Metodi statici


Se guardate il riquadro Proc.1, vedete che il primo termine che compare è static. Questa parola chiave indica che il metodo SelectionSort0 è un metodo statico. Ciò significa che il metodo è associato alla classe, e non alle istanze della classe. Per capire meglio, torniamo alla figura 1. Abbiamo detto che, quando definisco un programma (ad esempio mioPro), questo consiste nella definizione di una o più classi (che sono oggetti Java). Abbiamo anche visto che una delle classi deve avere lo stesso nome del file che contiene il programma, e che tale classe deve includere il metodo main. Infine, abbiamo ricordato che vi sono sia classi (es. Gatto) che istanze. Nell'esempio dei gatti, inoltre, abbiamo supposto che il messaggio 'Pappa' sia inviato ad una istanza della classe. Cosa succede, però se io voglio ottenere l'informazione relativa al veterinario per gatti? Non debbo certo mandare il messaggio di richiesta di informazioni al mio gatto (né ad alcun gatto in particolare), ma debbo inviarlo alla classe stessa. Non solo, ma questa informazione può essere reperibile (anche se, magari, non molto utile) anche se non esiste nel mio ambiente Java nessuna istanza di Gatto.


I metodi che vengono attivati inviando un messaggio alla classe vengono appunto detti metodi statici. Il motivo per cui viene utilizzato questo termine è che, di norma, le classi costituiscono la parte più stabile di un ambiente Java: un gatto può nascere o morire, ma il concetto di gatto rimane. Tutto ciò che è associato alle classi viene dunque detto statico nella terminologia Java.


E perché, nel nostro caso, viene utilizzato un metodo statico, se ciò che vogliamo ordinare è un singolo vettore (e cioè un'istanza della classe dei vettori)? La risposta è che, per introdurre questi primi concetti di programmazione in Java, abbiamo adottato un approccio solo in parte coerente con i principi della programmazione a oggetti! Quello che noi abbiamo fatto è stato infatti di definire la classe mioPro (in realtà non l'abbiamo ancora fatto; vedi sotto il riquadro Proc.2) e di associare ad essa la procedura di sort. Al contrario, se avessimo voluto essere più fedeli ai principi della programmazione ad oggetti, avremmo dovuto definire, all'interno del file mioPro, una classe 'iniziale' (con il metodo main) e poi una classe distinta MioVett. A questo punto sarebbe stato possibile:

Creare nuove istanze di MioVett (ad esempio l'istanza Vett33)

Definire un metodo SelectionSort0 non statico, che fa esattamente le stesse cose che abbiamo visto, e che è associato alla classe MioVett

Inviare alle istanze il messaggio SelectionSort0, la cui esecuzione comporta l'ordinamento dell'istanza che riceve il messaggio.

Poiché tutto ciò è un po' più complicato, abbiamo seguito la strada di definire una classe che include solo metodi, non istanze, e quindi l'unico modo per eseguire i metodi è quello di inviare dei messaggi alla classe stessa, richiedendo quindi l'esecuzione di metodi, appunto, statici. Il metodo main che può essere utilizzato per provare il metodo SelectionSort0 è riportato nel riquadro Proc.2.



public class MioProg

;

/* visualizzazione del vettore iniziale */

System.out.print (" Input: ");

for (int i = 0; i < mioVettore.length; i++)

System.out.print (mioVettore[i] + ", ");

System.out.println ("");

/* esecuzione del metodo di ordinamento */

selectionSort0 (myVett, 10);

/* visualizzazione del vettore ordinato */

System.out.print (" Risultato: ");

for (int i = 0; i <mioVettore.length; i++)

System.out.print (mioVettore[i] + ", ");

System.out.println ("");

} // Fine del metodo 'main'


static void selectionSort0 (int [] argVett, int size)

// Fine del Selection Sort !


} // fine della definizione della classe Mio Prog


Proc.2 - Il main della classe MioProg, che usa Selection Sort 0



Nel programma, ho introdotto due cicli for per stampare il vettore (prima nell'ordine originale e poi dopo l'ordinamento). La condizione di terminazione del ciclo è stata espressa con

i < mioVettore.length

length è un messaggio che si può inviare agli oggetti di tipo vettore per ottenerne la lunghezza. L'operatore di confronto, come abbiamo già visto, deve essere < e non <=, perché la numerazione degli elementi parte da 0.

Un ultimo commento. Abbiamo detto che tutto il meccanismo di esecuzione programmi in Java consiste nell'invio di messaggi. Quindi, anche la riga SelectionSort0 (mioVettore, 10) è l'invio di un messaggio! Ma mandare di un messaggio implica la presenza di un ricevente. Chi è il ricevente di SelectionSort0 (mioVettore, 10)? Il ricevente è la classe stessa (poichè, come abbiamo visto, si tratta di un metodo statico) che ha inviato il messaggio. In altre parole, il ricevente coincide col mittente!



Un altro modo per ordinare una sequenza: merge-sort


Torniamo ora al modo di ordinamento. L'impiegato può, in un modo o nell'altro, essersi reso conto che l'impresa è irrealizzabile, e quindi può aver escogitato un altro metodo. Supponiamo di dividere la pila iniziale in 4 pile di 50 fogli ciascuna (diciamo che questa divisione richiede 1 minuto). Poi ordina ciascuna pila, e poi mette insieme le pile ordinate (merge). Oramai sappiamo quanto ci vuole a ordinare una pila di 50 fogli:

((50/2)*51) secondi = 1275 secondi (cioè 21 minuti e 15 secondi)

Che, moltiplicato per 4, fa 1 ora e 25 minuti. Se per fare il merge da 4 pile, ci mette 2 secondi a foglio, sono altri 400 secondi (6 minuti e 40 secondi). Per cui il tempo totale è:



1 minuto + (suddivisione in 4 pile)

1 ora 25 minuti + (sort delle 4 pile)

6 minuti 40 secondi = (merge)

= = = = = = = = = =

1 ora 32 minuti 40 secondi (totale)

Ora va un pò meglio: abbiamo risparmiato più di 4 ore!


A questo punto, vorrei ribadire quanto già detto sopra: il problema del sort è un problema per nulla banale. Gli algoritmi di sort vengono studiati sostanzialmente per due motivi:

Sono utili dal punto di vista applicativo (capita spesso di dover ordinare degli elenchi)

Sono stati ben studiati, e quindi ne sono note le caratteristiche di efficienza

Quello che NON si richiede è che uno studente 'inventi' un buon algoritmo di sort. Nè voi nè io sapremmo far meglio di quanto già si sa. Ma se uno studente comprende bene la differenza, in termini di efficienza, che c'è tra due diversi algoritmi di sort, allora è sulla buona strada per capire cos'è l'efficienza degli algoritmi (o, come si dice, di analizzarne la 'complessità computazionale'). Il che, come abbiamo visto nell'esempio dell'impiegato, non è solo una questione di diletto scientifico.


Torniamo ora al metodo. A parte che la scadenza imposta dal capufficio non è ancora rispettata, si deve osservare che l'impiegato sta ora usando due metodi diversi. Un metodo (chiamiamolo merge-sort) per la pila completa (dividerla in pile più piccole, ecc.) e un altro metodo (il solito selection-sort) per ordinare ciascuna delle pile piccole. Ci si può quindi chiedere se non si può fare tutto col merge-sort (che, come abbiamo visto, porta notevoli vantaggi di tempo). In altre parole, non si può applicare lo stesso merge-sort anche alle pile di 50 fogli? Non si vede perchè no! Se la pila iniziale fosse stata di 50 fogli, tutti i ragionamenti visti sopra si sarebbero potuti fare esattamente nello stesso modo. Per cui possiamo prendere la prima pila di 50 fogli, la dividiamo in 4 pile (due di 13 fogli e due di 12), ordiniamo le 4 sotto-sottopile e poi facciamo il merge. Per ordinare ciascuna delle sotto-sottopile (di 13, 13, 12, 12 fogli) facciamo lo stesso. Prendiamo la prima (di 13) e la suddividiamo in 4 (di 4, 3, 3, 3 fogli). Poi prendiamo la prima di esse (4 fogli) e facciamo quattro pile di un foglio. Ora sul tavolo (in verità un po' grande) l'impiegato ha pile delle seguenti dimensioni:


1 1 1 1 3 3 3 13 12 12 50 50 50


Le prime 4 pile sono già ordinate (contengono solo un foglio) e quindi si può fare il merge, ottenendo


4* 3 3 3 13 12 12 50 50 50


In cui l'asterisco indica che la pila è ordinata. Allora possiamo suddividere la prima non ordinata:


4* 1 1 1 3 3 13 12 12 50 50 50


e farne il merge:


4* 3* 3 3 13 12 12 50 50 50


così pure come per le due successive (in due passi - suddivisione e merge - ciascuna):


4* 3* 3* 3* 13 12 12 50 50 50


e finalmente possiamo fare il merge delle prime 4 sotto-sotto pile:


13* 13 12 12 50 50 50


e cosi' via, fino ad avere la pila completa ordinata. Poichè il merge-sort della pila originale di 200 fogli è stato ottenuto tramite il merge-sort di ciascuna delle sottopile di 50, e così via per pile sempre più piccole, abbiamo inventato il nostro primo metodo 'ricorsivo'. Vediamo ora se è efficiente (nei calcoli sotto suppongo che un'operazione di merge da 4 pile richieda 2 secondi a foglio, mentre la suddivisione di una pila richiede 0.3 secondi a foglio).


Per ordinare la pila di 200 fogli:

Tempo di suddivisione (1 minuto)

4 * Tempo di ordinamento delle pile da 50 (?1) ! non si sa ancora !

Tempo di merge (400 secondi)


Per ordinare una pila di 50 fogli:

Tempo di suddivisione (15 secondi)

4 * Tempo di ordinamento delle pile da 13 (?2)   (sarebbe 2 da 13 e 2 da 12, ma cambia poco)

Tempo di merge (100 secondi)


Per ordinare una pila di 13 fogli:

Tempo di suddivisione (4 secondi) (sarebbe 3.9 secondi)

4 * Tempo di ordinamento delle pile da 3 (?3) (sarebbe una da 4 e 3 da 3)

Tempo di merge (26 secondi)


Per ordinare una pila di 3 fogli:

Tempo di suddivisione (1 secondo) + (sarebbe 0.9 secondi)

3 * Tempo di ordinamento delle pile da 1 (0 secondi) (sono gia' ordinate)

Tempo di merge (6 secondi)


Quindi, 7 secondi è il tempo totale per una pila da 3 fogli (il valore da sostituire a ?3, sopra).

Quindi, 58 secondi è il tempo totale per una pila da 13 fogli (il valore da sostituire a ?2, sopra).

Quindi, 347 secondi è il tempo totale per una pila da 50 fogli (il valore da sostituire a ?1, sopra).

Quindi, 1848 secondi è il tempo totale per una pila da 200 fogli (quello che ci serviva).


Poichè 1848 secondi sono 30 minuti e 48 secondi, ora possiamo quasi rispettare la scadenza (avremo meno di un minuto di ritardo)!


Torniamo ora al nostro algoritmo ricorsivo, che possiamo sintetizzare nel modo seguente:


Per fare il merge-sort di una pila di N fogli:

Suddividi la pila in 4 pile da N/4 (circa) fogli ciascuna;

Fai il merge-sort di ciascuna sottopila

Fai il merge delle 4 pile da N/4 fogli che sono state appena ordinate

N.B. Se N vale 1, non fare nulla, perchè la pila è già ordinata


Questa versione sintetica permette di evidenziare gli aspetti principali di qualunque algoritmo ricorsivo:

Il problema da risolvere viene suddiviso in problemi più semplici dello stesso tipo, più altre operazioni (nel nostro caso, ordinare un pila di N/4 fogli è più semplice che ordinare una pila di N fogli; le altre operazioni necessarie sono la suddivisione iniziale e il merge finale)

Esiste un caso (o più d'uno) in cui il problema è così semplice che può essere considerato risolto (nel nostro esempio, un solo caso, e cioè quello di pile di un unico foglio).

Ora che abbiamo una buona soluzione 'intuitiva' del problema del sort, possiamo passare alla seconda fase, e cioè quella della scrittura del programma. Come ho detto sopra, vi sono due aspetti da considerare: la scelta delle strutture dati e la scelta delle strategie di controllo. Si noti, comunque, che l'adozione di un algoritmo ricorsivo costituisce già, almeno in parte, una scelta sulle strategie di controllo. Prima di procedere, però, osserviamo che ho scelto di dividere N per 4, perchè rendeva più breve l'esempio. Avrei, allo stesso modo, potuto decidere di dividere per 2, 3, o 10. Su un calcolatore, la scelta più naturale è quella di dividere per due (questo rende anche più semplice il merge). Questo farò nell'implementazione che stiamo per vedere.


Implementazione di merge-sort


Per quanto riguarda le strutture dati, è chiaro che, dovendo trattare dei pacchi di fogli, dovremo utilizzare delle strutture dati composte; quelle a disposizione in Java sono i vettori (più in generale le array a n dimensioni) o le liste. Consideriamo per ora i vettori.

Nella valutazione del 'lavoro da fare', ciò che entra in gioco sono solo quelle che ho chiamato 'altre operazioni', poichè la risoluzione del problema base (quello risolto) ha costo 0 (si veda, in particolare, la valutazione del costo che abbiamo fatto sopra per il merge-sort dei 200 fogli; notate che questo è vero per il sort, ma non tutti i problemi sono così). Dobbiamo quindi, nel nostro caso, vedere cosa succede per le due operazioni di 'suddivisione' e di 'merge'.

Per quanto riguarda la 'suddivisione', il problema e' banale. Soprattutto se si sa già, come nel nostro caso, la lunghezza (L) del vettore (inpVett, diciamo). Basta avere due vettori che possano contenere le due meta' (firstHalf e secondHalf). Allora si copieranno i primi L/2 elementi in firstHalf con un semplice ciclo di firstHalf[i] = inpVett[i] e i rimanenti elementi in SecondHalf, con un ciclo del tipo secondHalf[i] = inpVett[L/2 + i] (si veda sotto la realizzazione effettiva, in cui si vede che un vettore di input di lunghezza dispari non crea difficoltà).

Per 'merge' si intende un'operazione che ha come argomenti due liste ordinate e come risultato la lista ordinata che include gli elementi che compaiono negli argomenti.

Es: merge ([1, 7 ,8, 32, 32, 50], [2, 3, 5, 7, 32, 40, 60, 61, 62]

[1, 2, 3, 5, 7, 7, 8, 32, 32, 32, 50, 60, 61, 62]

Si noti che i due argomenti 'devono' essere già ordinati, altrimenti non si può parlare di merge. Inoltre, possono esservi elementi ripetuti, come si vede nell'esempio (sono liste, non insiemi).

Vediamo dunque cosa si può fare utilizzando, come strutture dati, i vettori. Presumibilmente, avremo bisogno di tre vettori, due per gli argomenti e uno per il risultato. Dopodichè possiamo confrontare i primi due elementi dei vettori di input e mettere nel vettore in output il più piccolo, avanzando sul vettore da cui abbiamo preso l'elemento. Bisogna però sempre ricordarsi i casi 'limite'. Nel merge, essi corrispondono alla situazione in cui uno dei due argomenti è vuoto. Quando le due liste sono ambedue vuote, abbiamo terminato le operazioni. Proviamo ora a scrivere un programma iterativo che realizzi questo algoritmo. La procedura (Merge1) avrà tre argomenti (due vettori di input e uno di output) e le lunghezze dei due vettori di input.

static void merge1 (int [] vett1, int [] vett2, int [] outVett, int size1, int size2)

dove size1 e size2 sono le dimensioni effettive dei due vettori di input. Ora viene il difficile. Debbo spostarmi su tre vettori, per cui verrebbe naturale pensare di utilizzare tre cicli 'for'; purtroppo questa soluzione non è praticabile, perchè l'incremento degli indici di ciclo dipende da cosa succede dentro il ciclo. Ad esempio, devo avanzare sul primo vettore (incrementare l'indice) solo se il suo primo elemento è più piccolo del primo elemento del secondo vettore, altrimenti l'indice deve rimanere invariato. Però, l'indice sul vettore di output viene incrementato regolarmente. Quindi possiamo avere un unico ciclo for (sull'output) con incrementi 'manuali' degli indici dei due vettori di input[3].

int i1 = 0;

int i2 = 0;

[ ciclo sul vettore di output; il valore massimo dell'indice è pari alla dimensione finale

del vettore di output, cioè alla somma delle dimensioni dei due vettori di input ]

for (iOut = 0; iOut < size1+size2; iOut++)



else if (i2 == size2)



else if (inplist1[i1] > inplist2[i2])



else } }.

Il metodo completo è riportato nel riquadro Proc.3:


static void merge (int[] vett1, int[] vett2, int[] outVett, int size1, int size2)


else


else


else

;} // End of 'if vett1'

} // End of 'if i2'

} // End of 'if i1'

} // End of merge !


Proc. 3 - Merge di vettori - Versione 1


Ora possiamo pensare al metodo merge-sort. Poichè dobbiamo lavorare con i vettori, avremo bisogno, concettualmente, di 2 vettori distinti:

Il vettore che contiene i dati iniziali da ordinare

Un vettore che contenga il risultato

Inoltre, ci vorranno altri 4 vettori 'locali' alla procedura:

2 vettori che contengono i dati suddivisi da ordinare

2 vettori che contengono i dati suddivisi dopo che sono stati ordinati

Nella prima versione introdurrò tutti i 6 vettori; poi, vedremo se si può risparmiare qualcosa. L'intestazione della procedura può essere:

static void mergeSort (int [] inpVett, int [] outVett, int size)

in cui size è la dimensione del vettore da ordinare; ora debbo introdurre i due vettori per i dati suddivisi (non ancora ordinati) e quelli per i dati suddivisi ordinati:

int [] firstHalf;

int [] secondHalf;

int [] sortedFirstHalf;

int [] sortedSecondHalf;

Per ora ho solo dichiarato l'esistenza dei vettori! Non ho ancora riservato spazio per essi. Questo lo farò con delle new. Ma prima debbo sapere quanto spazio riservare, e per far ciò divido size per 2.

int size1 = size / 2;

int size2 = size - size1;

Se size è dispari, size1 sarà troncata (se size è 13, size1 sarà 6). Non posso quindi usare size1 anche per la seconda metà del vettore, per cui viene introdotta anche size2. Ora posso chiedere di riservare lo spazio sullo heap.

firstHalf = new int [size1];

sortedFirstHalf = new int [size1];

secondHalf = new int [size2];

sortedSecondHalf = new int [size2];

Ora il primo passo, la suddivisione del vettore.

for (int i = 0; i < size1; i++)

firstHalf[i] = inpVett[i];

for (int i =0; i < size2; 1++)

secondHalf[i] = inpVett[size1+i];

Ora dobbiamo ordinare i due mezzi vettori e poi fare il merge:

mergeSort0 (firstHalf, sortedFirstHalf, size1);

mergeSort0 (secondHalf, sortedSecondHalf, size2);

merge (sortedFirstHalf, sortedSecondHalf, outVett, size1, size2)

Sì, ma quando mi fermo? Ho dimenticato la condizione per la fine della ricorsione! Questa va messa all'inizio della procedura: se il vettore è lungo 1, allora è già ordinato.

if (size == 1 )


static void mergeSort0 (int[] inpVett, int[] outVett, int size)


else

// End of 'if'

} // End of mergeSort0 !


Proc. 4 - Merge Sort - Versione 1


Salta però subito all'occhio un notevole spreco di spazio: per ogni livello di annidamento nelle chiamate, è necessario riservare spazio, oltre che per le variabili, anche per 4 vettori. Si può però osservare che quando si effettua il merge finale, il contenuto di inpVett è ormai inutile (i dati sono già stati spostati in firstHalf e secondHalf), cosicchè si può utilizzare come vettore di output lo stesso vettore di input (ovviamente, visto che i vettori sono passati per riferimento, in questo modo il mittente perderà la versione originale 'disordinata' del vettore; se serve, bisognerà farne una copia prima). Otteniamo così:


static void mergeSort1 (int[] inpVett, int size)

// End of 'if'

} // End of MergeSort1 !


Proc. 5 - Merge Sort - Versione 2


Implementazione di merge-sort con una classe MioVett


Ora che abbiamo un'idea chiara dell'algoritmo di merge sort e della sua implementazione, possiamo fare un passo indietro. Ho osservato in precedenza (v. Richiami di Java 5: Metodi Statici) che l'approccio che abbiamo seguito nell'implementazione non è del tutto coerente con i principi della programmazione ad oggetti. Infatti, l'implementazione dovrebbe essere centrata su 'oggetti', anziché sui 'metodi'. In questo paragrafo cercherò di ovviare a questo problema, introducendo una nuova classe di oggetti, che chiamerò MioVett, e che sia in grado di rispondere a vari messaggi, tra cui uno che richiede di effettuare l'ordinamento.

Innanzitutto, dove va definita questa classe? Se noi vogliamo che essa sia disponibile a vari metodi (e cioè che anche metodi definiti per altre classi possano definire nuove istanze di MioVett, ed inviare messaggi ad esse), è necessario che MioVett sia public. Poiché in ciascun file può esserci solo una classe public, dovremo avere due file: uno per il main (il nostro vecchio MioProg) e uno per la nuova classe (MioVett).

A questo punto dobbiamo decidere come è strutturata la classe MioVett. Poiché essa è, in realtà, l'implementazione di alcune particolari funzioni sui vettori, dovrà includere dei dati di tipo vettore (supponiamo, come abbiamo fatto fino ad ora, che siano vettori di interi). Dovremo dunque includere nella classe una variabile di istanza (poiché ogni istanza ha i suoi propri dati) di tipo vettore. Poiché questa è una variabile interna della classe (non accessibile dall'esterno, se non attraverso i metodi della classe), dovrà essere privata. La sua definizione (se la chiamiamo datiVett) sarà quindi la seguente:

private int [] datiVett;

Però, come abbiamo visto, questa dichiarazione dice solo che datiVett esiste, ma non serve a riservare dello spazio. Questo è particolarmente utile qui, in quanto ciò che si vuole fare è definire una classe che vada bene per vettori di dimensione qualsiasi. Rimane però il problema di riservare lo spazio, quando si vuole creare una nuova istanza della classe. Come sappiamo, questo si fa con una new (per tutte le classi, non solo per i vettori). Per cui, presumibilmente, dovrebbe essere possibile scrivere un'espressione del tipo:

MioVett varVettore = new MioVett (100);

mediante la quale si specifica che viene definita una nuova istanza di MioVett (di nome varVettore) e che per essa deve essere allocato spazio per 100 elementi. Affinchè tale espressione sia 'capita' dalla classe MioVett, MioVett deve includere un metodo 'costruttore' (cioè un metodo in grado di rispondere ad una new). Tale metodo, che sarà ovviamente public, non si chiamerà (come potrebbe essere naturale) new, ma sarà identificato dallo stesso nome della classe (e quindi dovrà chiamarsi, nel nostro caso, MioVett). Tutto ciò che dovrà fare questo metodo, nel nostro esempio, sarà di creare una nuovo vettore, che verrà associato alla variabile (di istanza) datiVett. La quantità di spazio da riservare, e cioè la lunghezza del vettore, è specificata dall'argomento del metodo.

Ora, a me sembra si crei qui un po' di confusione tra la istanza di MioVett, che stiamo creando, e l'istanza di datiVett, che è una variabile di istanza della classe. I due oggetti, anche se in questo esempio sembrano coincidere, sono concettualmente diversi: l'istanza di datiVett fa parte (anche se ne è l'unica parte) dell'istanza di MioVett, e quindi, essendone parte non è la stessa cosa. Solo per chiarire questa ambiguità, introdurrò una seconda variabile di istanza (non sarebbe necessario), che è un intero che contiene la lunghezza del vettore. La situazione che viene a crearsi quando si fa una new di MioVett, è quindi la seguente:





Figura 6: Variabili di istanza della classe MioVett


Per ottenere questo, le variabili di istanza saranno dichiarate con:

private int [] datiVett;

private int lung;

E a questo punto possiamo scrivere il metodo costruttore:

public MioVett (int dimens)


E ora le due operazioni di base su MioVett; poiché si tratta della realizzazione di un vettore, dovremo leggere e scrivere elementi del vettore. Naturalmente, non si potrà usare la notazione

varVettore [5]

Poiché varVettore NON è un vettore (tipo int []), ma un mio vettore (tipo MioVett). E quindi, dovremo definire due metodi appositi per eseguire le due operazioni. Posso chiamarli elem e store:

public int elem (int pos)


elem ha come argomento un indice sul vettore (pos), ed è public (usabile anche da metodi esterni, ad esempio quelli che compaiono in MioProg), e int (perché restituisce il valore dell'elemento). Notate che qui, datiVett [pos] si può scrivere, perché datiVett è, effettivamente, un vettore di tipo standard.

public void store (int pos, int val)


Nel metodo store abbiamo due parametri: la posizione (indice sul vettore: pos) e il valore da memorizzare (val). L'unica cosa da osservare è che store è void, perché il suo effetto è di modificare il contenuto dell'istanza, senza restituire nulla. Infine, possiamo riscrivere mergeSort. Non lo faccio passo per passo: il risultato finale sta nel riquadro proc.5, insieme alla nuova versione di merge. Si noti:

mergeSort è public, mentre merge è private. Questo significa che dall'esterno (in particolare da MioProg) potrò inviare un messaggio di 'auto-ordinarsi' ad un'istanza di MioVett, ma non potrò inviarle un messaggio di effettuare un merge.

Il merge è stato realizzato nel modo seguente: si invia il messaggio al MioVett che dovrà contenere il risultato del merge, passando, come argomenti, i due MioVett, di cui fare il merge. Parafrasando il messaggio, esso potrebbe essere interpretato come "prendi come tuoi elementi il merge dei due vettori che ti passo".

Secondo quanto avevamo deciso nell'ultima versione di mergeSort, il risultato dell'ordinamento va nello stesso vettore di input (si ordina il vettore stesso, non si crea un nuovo vettore ordinato). Per ottenere qui lo stesso effetto, il messaggio di merge finale va inviato all'istanza che conteneva i


public class MioVett



public int elem (int pos)



public void store (int pos, int val)



public void mergeSort1 ()

// End of 'if'

} // End of MergeSort1 !


private void merge1 (MioVett vett1, MioVett vett2)


else

else

else

;} // End of 'if vett1'

} // End of 'if i2'

} // End of 'if i1'

} // End of Merge !



Proc. 6 - La Classe MioVett


dati iniziali da ordinare (e cioè a quella che ha inizialmente ricevuto il messaggio mergeSort). In pratica, il messaggio di merge deve essere inviato dall'istanza xxx alla stessa istanza xxx: il mittente e il ricevente devono coincidere. Questo si realizza usando la parola chiave this, che sta ad indicare l'istanza da cui il messaggio parte (il mittente, appunto): this.merge1 (firstHalf, secondHalf); In realtà, in casi come questo, this si può anche omettere, in quanto Java, se non trova il ricevente, assume sia l'istanza stessa, ma così il metodo è più leggibile.

Infine, possiamo riportare la nuova versione del main, che si trova in MioProg:. Ho lasciato il più possibile invariata la definizione, ma a questo punto sarebbe molto più sensato inserire un nuovo metodo public nella classe MioVett, che si occupi della stampa di un vettore, anche in modo di evitare la ripetizione delle istruzioni per la visualizzazione del vettore originale e di quello ordinato; lascio a voi l'estensione. Notate solo che ho introdotto inpVett al solo scopo di evitare di fare 12 assegnazioni separate di valori a varVettore (in questo modo ho potuto usare un ciclo).


public class Vettori

;

MioVett varVettore = new MioVett (12);

for (int i = 0; i < 12; i++)

varVettore.store (i, inpVett [i]);

System.out.print (" Input: ");

for (int i = 0; i < 12; i++)

System.out.print (varVettore.elem (i) + ", ");

System.out.println ("");

varVettore.mergeSort1 ();

System.out.print (" Risultato: ");

for (int i = 0; i < 12; i++)

System.out.print (varVettore.elem (i) + ", ");

System.out.println ("");

} // End of main!

} // End of Vettori Class definition


Proc. 7 - Un programma che usa la Classe MioVett


1.5 Le Liste


La cosa importante dell'algoritmo che abbiamo visto è che il metodo è indipendente dalla scelta delle particolari strutture dati: è, appunto, un algoritmo, non un programma. E quindi, se vogliamo utilizzare le liste al posto dei vettori non si tratta di inventare un nuovo algoritmo, ma solo di realizzare il nostro merge-sort in modo diverso. Poiché quello delle liste è un argomento importante, in particolare quando verranno analizzate strutture dati più complesse, cerchiamo di vedere le caratteristiche principali delle liste e del modo in cui operare su di esse.

In Java, esiste già una classe predefinita che permette di creare delle liste e compiere operazioni su di esse: il nome della classe è LinkedList. In questo capitolo, però, il mio obiettivo è quello di chiarire come le liste possono essere strutturate al loro interno, per cui ci complicheremo la vita e costruiremo una nostra classe MiaLista, con caratteristiche simili (non proprio uguali a LinkedList) e definiremo alcuni metodi per operare sulle istanze di tale classe, tra cui MergeSortList.

Vediamo innanzitutto come è fatta, intuitivamente, una lista:





Figura 7: Struttura di una lista generica


Bisogna precisare, però, che il termine lista è ambiguo; esso infatti può essere usato sia per indicare una struttura dati astratta, composta da una sequenza ordinata di elementi omogenei, sia una particolare classe di oggetti (LinkedList di Java, o MiaLista). Alcuni testi inglesi usano i termini list e linked list per riferirsi ai due concetti. Poiché le possibili traduzioni non mi soddisfano, io userò invece sequenza e lista. Quindi una sequenza è un elenco ordinato di elementi di qualunque tipo (addirittura, gli elementi possono essi stessi essere delle sequenze), ma tutti dello stesso tipo. Invece una lista è una classe, opportunamente implementata.

Sebbene l'analogia tra sequenze e liste sia evidente, non è per nulla detto che io debba realizzare una sequenza con una lista. Anzi, è proprio questo il problema che stiamo affrontando ora nel nostro esempio dell'impiegato: prima avevamo deciso di realizzare la sequenza di fogli con un vettore, ora stiamo provando a vedere cosa succede con le liste.

Nella figura precedente, è chiaro che gli elementi della lista sono formati da due parti distinte: valori (Dato1, ., DatoN) e riferimenti (rappresentati dalle frecce). Di conseguenza, è ragionevole definire una classe di oggetti (possiamo chiamarla ListElem), costituita in modo analogo. Se supponiamo che i valori siano numeri interi, la prima variabile di istanza sarà dunque di tipo int. E di che tipo sarà la seconda variabile? Non esiste, in Java, la classe Riferimento. Ma d'altronde, sempre, quando si definisce una variabile di tipo ClasseX, ciò che viene memorizzato nella variabile (o meglio, che verrà memorizzato in essa all'atto di una new) è un riferimento all'istanza; in altre parole, se io dichiaro una variabile ClasseX, ciò che faccio è richiedere di riservare lo spazio per contenere un riferimento a istanze di ClasseX. Ma questo è proprio quello che mi serve adesso: la seconda parte di ListElem deve essere un riferimento ad un'altra istanza di ListElem, e quindi avrò:

private class ListElem


Il motivo per cui la classe è privata e le variabili di istanza sono pubbliche lo vedremo tra un attimo. Ora che abbiamo definito gli elementi della lista, passiamo alla definizione della lista vera e propria. A differenza dei vettori, però, un riferimento alla lista non è all'intera lista, ma al suo primo elemento, in quanto tutti gli altri saranno poi raggiungibili procedendo sulla lista. Per cui MiaLista avrà bisogno di un'unica variabile di istanza, e cioè una variabile che contenga il riferimento al primo elemento della lista:

public class MiaLista


E' a questo punto chiaro il motivo per cui la precedente classe ListElem è privata: dall'esterno, si accederà agli elementi di una lista sempre tramite MiaLista, che a sua volta metterà a disposizione il primo elemento, e mai direttamente ai ListElem. Inoltre, le variabili di ListElem possono essere pubbliche, poiché esse sono usabili solo all'interno della classe MiaLista (che è l'unica, come abbiamo detto, a vedere i ListElem), e quindi non utilizzabili direttamente da procedure esterne.

Ci si potrebbe chiedere perché tutte queste complicazioni. Perché, ad esempio, non lasciamo che una lista sia semplicemente identificata da un ListElem (cioè il primo elemento della lista)? Sarebbe tutto molto più semplice, ma questo porta a delle difficoltà di gestione della lista vuota. Infatti, se si volesse creare una lista vuota, l'unico modo sarebbe:

ListElem nuovaLista = null;

Se si applicasse una new ListElem, infatti, si creerebbe un nuovo elemento, e questo non è quello che si desidera (la lista vuota non ha elementi). Purtroppo, a un riferimento null non si possono inviare messaggi. Non posso quindi creare un metodo per la stampa della lista (es. printList) che funzioni anche per la lista vuota. Se io scrivessi:

nuovaLista.printList ();

otterrei infatti un messaggio di errore (NullPointerException). Questi problemi vengono risolti introducendo MiaLista. La lista vuota viene infatti creata nel modo seguente:

MiaLista nuovaLista = new MiaLista ();

che, in presenza di un costruttore del tipo:

public MiaLista ()


Produce la creazione di una nuova istanza, come si vede nella figura che segue:






Figura 8: Struttura di una istanza della classe MiaLista



Dovrebbe essere evidente che in questa situazione il messaggio

nuovaLista.printList ();

Non provoca problemi, se il metodo PrintList verifica innanzitutto che first != null. Proviamo a scrivere questo metodo, che è abbastanza semplice. Non semplicissimo, però! Concettualmente, esso opera nel modo seguente: stampa il dato del primo elemento e poi procedi sull'elemento successivo, e così via, fino a che si trova il riferimento null (fine della lista). Sfortunatamente, però, il messaggio printList va inviato ad un oggetto di tipo MiaLista, mentre gli elementi successivi sono di tipo ListElem. Vi sono due possibili soluzioni: o si definisce una printElem per gli elementi successivi della lista, o si introduce un nuovo elemento di tipo MiaLista, che abbia la funzione di cursore, e cioè che permetta di spostarsi in avanti. Io adotterò questa seconda soluzione, per evitare di duplicare il metodo.



public void printList ()

;

System.out.println ("");}

Proc. 8 - printList: visualizza gli elementi di una lista




Vediamo ora come funziona la printList. Supponiamo che la lista da stampare sia provaLista:






Figura 9: Implementazione di una lista mediante le classi MiaLista e ListElem




La creazione di loopElem, e l'assegnazione del first produce la situazione di fig.10:










Figura 10: Realizzazione di un cursore su una lista: loopElem



Ora, visto che loopElem.first non è null, si effettua la stampa del valore 7 (tramite il metodo getFirstDato, che vedremo tra un attimo). A questo punto possiamo avanzare sulla lista (anche il metodo advance lo vediamo subito sotto), arrivando nella situazione seguente:










Figura 11: Avanzamento di un cursore su una lista: loopElem



Prima di vedere come termina il ciclo, introduciamo i metodi getFirstDato e advance.



public int getFirstDato ()


else

;

}


public void advance ()





Proc. 9 - I metodi getFirstDato e advance


Sono ambedue molto semplici, limitandosi a prelevare i valori delle variabili di istanza. Il primo è però di tipo int (e infatti effettua una return, per restituire il dato della istanza di ListElem cui si riferisce il first). Il secondo invece è void, in quanto il suo effetto è ottenuto modificando il first del ricevente (nel nostro caso loopElem). Per quanto riguarda il ramo else della getFirstDato, siamo obbligati ad inserirlo, perché il metodo è int, e il compilatore si preoccupa di cosa potrebbe succedere se il first fosse null (è necessario che anche in tal caso, un intero venga restituito).

Si noti che con questa implementazione della advance sarebbe stato errato inizializzare il ciclo di stampa con

MiaLista loopElem = this;

anziché

MiaLista loopElem = new MiaLista ();

loopElem.first = first

La situazione che si sarebbe realizzata sarebbe stata la seguente:










Figura 12: Un cursore realizzato in modo errato


In questa situazione, lo spostamento del first realizzato dalla advance avrebbe provocato uno spostamento del first (condiviso) di provaLista: la lista originale sarebbe stata modificata dallo spostamento in avanti! Possiamo ora ritornare alla chiusura del ciclo di stampa. Quando loopElem si riferisce all'elemento 15, l'assegnazione first = first.next in advance fa sì che il riferimento null venga copiato nel first di loopElem, così che al passo successivo il ciclo termina.

Prima di tornare al problema dell'ordinamento, vediamo ancora due semplici metodi, quello che inserisce un elemento all'inizio di una lista, e quello che consente di cancellare il primo elemento di una lista.


public void insertFirst (int val)



public void deleteFirst ()



Proc. 10 - I metodi insertFirst e deleteFirst



Non credo siano necessari particolari commenti, eccetto il fatto che la deleteFirst è identica alla advance. Questo non deve stupire: avanzare su una lista vuol dire far sì che il suo nuovo 'primo elemento' sia quello che prima era il secondo elemento, esattamente la stessa cosa che una cancellazione!



Vettori e liste: alcuni vantaggi e svantaggi


Possiamo ora vedere rapidamente i vantaggi e gli svantaggi rispettivi dei vettori e delle liste. Sinteticamente si può dire che per quanto riguarda l'accesso ai dati, i vettori sono più efficienti, mentre per alcune operazioni di modifica le liste sono migliori. Supponiamo, ad esempio di voler modificare il 50-esimo elemento di un vettore (ad esempio, se si tratta di un vettore di interi, di voler incrementare il valore). Come sappiamo, è sufficiente una semplice operazione:

vettore[50]++;

Questa semplicità è dovuta al fatto che gli elementi dei vettori sono memorizzati uno dopo l'altro, per cui Java è in grado, sapendo dove si trova il primo elemento del vettore e sapendo quanto spazio occupa ogni elemento, di determinare con semplici calcoli dove si trova il 50-esimo elemento. (la formula è start + pos*elemSize, dove start è la posizione del primo elemento, pos è l'indice dell'elemento che interessa, e elemSize è lo spazio occupato da ogni elemento, supponendo che il primo elemento abbia pos=0; nel nostro caso, pos sarebbe 49; si veda la figura 2). Se si usano le liste, invece, non è possibile 'calcolare' la posizione del 50-esimo elemento, bisogna invece seguire uno per uno gli elementi della lista e i relativi riferimenti, contando fino a che punto si è arrivati. Questo tipo di modifica (cambiamento di un valore) è quindi più rapido se si usano i vettori. La stessa cosa si può dire per qualunque operazione di accesso: prendere vett[725] è quasi immediato, mentre prendere il settecentoventicinquesimo elemento della lista richiede molto più tempo.

Consideriamo ora due operazioni di tipo diverso: la cancellazione di un elemento dalla sequenza e l'inserimento di un nuovo elemento nella sequenza. Supponiamo, ad esempio, di avere la sequenza che segue e che l'elemento 137 debba essere eliminato dalla sequenza (magari si tratta di un fornitore che non opera più, o di un cliente di una banca che ha chiuso il conto corrente).


Nel caso dei vettori bisogna fare due cose: specificare che la dimensione effettiva (size, o dim, o max, o qualunque altra variabile usata per questo) se prima era n, è ora di n-1, e spostare tutti gli elementi che seguono quello cancellato. Esattamente il contrario si farà nel caso di inserimento: se dopo l'elemento 137 bisogna inserire un nuovo elemento con valore 77, si dovranno spostare tutti gli elementi, in modo che vi sia una cella libera che possa ricevere il valore 77. Può sembrare che questi spostamenti siano banali, ma provate a farli voi su un vettore di 100 elementi con gomma e matita e vi renderete conto del problema.

Nel caso delle liste, tutto è più semplice. Se vogliamo cancellare il valore 137, non dobbiamo fare altro che prendere il valore del riferimento associato ad esso (il suo next) e metterlo al posto del riferimento associato al 55 (cosicchè il next di 55 diventa 0). Finito! L'unico problema potrebbe essere quello di trovare l'elemento precedente della lista (il 55) in modo da poter modificare il suo riferimento. Ma per come avviene lo spostamento sulle liste, per arrivare all'elemento con valore 137, siamo appena passati dal 55, e quindi è sufficiente ricordarsi il riferimento all'elemento precedente[4].








Figura 13: Eliminazione di un elemento da una lista


La figura 13 illustra graficamente l'operazione. Si noti che il riferimento associato a 137 non è stato modificato! Ma tanto, da 137 non ci si passerà più nello scorrimento della lista e quindi il contenuto delle due celle (il 137 e il suo riferimento) non è più di interesse.

Del tutto analogo è l'inserimento del 77 tra il 137 e lo 0. E' sufficiente:

Trovare dello spazio libero nello heap per due celle contigue (il valore e il riferimento associato).

Mettere il nuovo valore nella prima di queste celle (la variabile di istanza dato)

Mettere il riferimento associato a 137 nel nuovo riferimento. In questo modo il nuovo elemento 'punta' a quello che prima era successivo a 137, e cioè 0.

Mettere al posto del riferimento di 137, il riferimento alla nuova istanza (77). In questo modo l'elemento successivo a 137 diventa il nuovo elemento inserito, e cioè 77.

Anche qui: sembra complicato, ma provate a farlo a mano su un foglio con gomma e matita e vedete quanto tempo risparmiate rispetto a spostare 100 elementi.









Figura 14: Inserimento di un elemento in una lista



C'è infine un ultimo argomento a favore delle liste. Supponiamo di avere a disposizione 1000 celle di memoria e di dover memorizzare cinque sequenze, ma senza sapere all'inizio quanto sono lunghe (magari sono lette da un file o inserite da tastiera). Nel caso dei vettori, la soluzione più ragionevole è quella di riservare 200 celle per vettore. Se la lunghezza effettiva delle cinque sequenze è 150, 180, 30, 100, 60, tutto va bene. Ma se invece la lunghezza è 80, 20, 210, 60, 10, allora il programma deve inviare una segnalazione di errore, perchè la terza sequenza non ha spazio a sufficienza (nonostante che la quantità totale di spazio necessaria sia di 380 celle). Al contrario, nel caso delle liste, non è necessario dichiarare a priori la lunghezza di ogni lista, per cui in ambo i casi le cose funzionano. Si potrebbe obiettare che, comunque, lo spazio effettivo occupato da una lista è maggiore di quello occupato da un vettore (per ogni dato ci vuole anche il riferimento associato) e che quindi in molti casi i vettori hanno spazio a sufficienza, mentre le liste no. Ciò significa, in pratica, che parte dello spazio è occupato da oggetti interni, relativi alla struttura dati (i riferimenti) che non sono di nessun interesse per l'applicazione (e cioè il programma, a cui interessa solo memorizzare i suoi dati). Ci sono due risposte a questa (ragionevole) obiezione:

In molti casi i 'dati' occupano più di una cella. Supponendo, infatti, che i dati non siano dei numeri interi, ma degli oggetti veri e propri (ad es. di un conto bancario), può essere che ciascuno di essi occupi, ad esempio 100 celle. In questo caso, una cella (riferimento) è usata per ogni 100 celle di dati 'utili', e quindi lo spreco è di solo 1/101 (cioè meno dell'uno per cento).

Vi sono sempre, nei calcolatori, dei trade-off. Si deve cioè pagare qualcosa da una parte per ottenere qualcosa da un'altra parte. Nel nostro caso si tratta di pagare in termini di occupazione complessiva di spazio, in cambio di una maggiore flessibilità (lunghezza variabile delle sequenze). Dipende ovviamente dal caso particolare se ha maggior valore lo spazio risparmiato o se ha maggiore importanza la flessibilità. Infatti, esistono e sono usati sia le liste che i vettori: in alcuni casi è meglio usare i vettori, in altri le liste (se così non fosse, non ci sarebbero due strutture dati alternative).


1.7 Altre operazioni sulle liste


Ora che abbiamo visto le caratteristiche più importanti delle liste, possiamo vedere una realizzazione in Java delle operazioni fondamentali:

a)   Verifica se nella lista c'è l'elemento X.

b)   Modifica il valore dell'elemento X (se c'è) in Y.

c)   Cancella l'elemento X (se c'è)

d)   Inserisci l'elemento Y dopo l'elemento X (se c'è)

Poichè Programmazione 2 deve servire da introduzione alla ricorsione, diamo la versione ricorsiva delle procedure che realizzano le operazioni viste sopra. Prendiamo la prima operazione (ricerca). Alla domanda "c'è l'elemento X nella lista?" si può rispondere molto semplicemente: "O il primo elemento della lista è X, o X, se c'è, X è nella parte restante della lista". Detto in modo un poco più preciso: l'elemento X è nella lista se il primo elemento è X o se l'elemento X è nella parte restante della lista. Ho messo in corsivo la parte rilevante della definizione ri-corsiva: abbiamo, come visto sopra, definito "X è nella lista" tramite la stessa richiesta, applicata ad un 'oggetto più semplice'. Questo oggetto è 'la parte restante della lista', che è più semplice da trattare, perché più corta. Non abbiamo però ancora finito: dobbiamo specificare quando la ricerca termina. Questo è facile: si finisce o quando abbiamo trovato l'elemento o quando la lista è finita! E in questo secondo caso, la risposta è negativa.

Ora, però, dobbiamo affrontare un problema che sorgerà ancora in seguito. Per effettuare la ricerca è necessario avanzare sulla lista. Abbiamo visto come questo si può realizzare con un cursore nel caso del metodo printList. Con un metodo ricorsivo, le cose sono un po' più complicate. Non è opportuno infatti creare il cursore all'interno del metodo ricorsivo, altrimenti se ne creerebbe uno nuovo ad ogni passo di ricorsione. Per risolvere il problema, il metodo inLista ha lo scopo principale di inizializzare il cursore, mentre la ricerca vera e propria viene lasciata ad un metodo ricorsivo privato (che chiamerò inListaIntern). Notate che, come già osservato, non è possibile utilizzare l'istanza ricevente di inLista come cursore, perché ciò comporterebbe la modifica della lista ricevente.


public boolean inLista (int val)



private boolean inListaIntern (int val)


else


else



}


Proc. 11 - inLista: C'è un elemento in una lista?


Ora il cambiamento del valore, che è praticamente uguale. Anche qui viene introdotto il cursore e viene restituito un valore booleano. Il valore indica il successo dell'operazione: true se l'elemento è stato trovato e modificato, false se l'elemento da modificare (identificato dal vecchio valore) non è stato trovato. In alternativa, si sarebbe potuta inviare un'eccezione in caso di elemento non presente (v. §1.10).


public boolean modifElem (int oldVal, int newVal)



private boolean modifElemIntern (int oldVal, int newVal)


else


else



}


Proc. 12 - modifElem: Modifica un elemento di una lista



Passiamo ora all'inserimento di un elemento 'dopo' un altro elemento. Qui, precElem è il valore (dato) dell'elemento che precede quello nuovo che deve essere inserito. Ad esempio, il risultato di fig.14 si otterrebbe inviando alla lista il messaggio insertAfter (137, 77);


public boolean insertAfter (int precElem, int newVal)



private boolean insertAfterIntern (int precElem, int newVal)


else


else



}


Proc. 13 - insertAfter: Inserisci un elemento in una lista 'dopo' un elemento specificato



E ora, la cancellazione di un elemento. Purtroppo, sebbene l'operazione di cancellazione sia più semplice di quella di inserimento, qui c'è un problema. La cancellazione deve modificare il next dell'elemento precedente a quello da cancellare, non il next dell'elemento stesso. E questo, per come abbiamo costruito il cursore, non si può fare. Riconsideriamo, per capire perché, la precedente figura 10, che ripeto sotto come figura 15.











Figura 15: Realizzazione di un cursore su una lista: loopElem (ripetizione)


Supponiamo ora, per semplicità, di dover cancellare il primo elemento della lista (7). Quello che devo fare non è altro che

first = first.next

Ma questa operazione, se effettuata sul cursore (loopElem, nella figura) non ottiene il risultato voluto. Infatti, il first di loopElem risulta modificato, ma quello di provaLista, che è quello che a noi interessa, rimane invariato: la cancellazione non è stata effettuata. Non c'è d'altronde da stupirsi: abbiamo introdotto il cursore proprio per spostarci in avanti senza modificare la lista originale! La soluzione di questo problema è un po' seccante, perché richiede la duplicazione di alcune istruzioni, ma non mi sembra si possa fare meglio. Innanzitutto, si fanno i controlli (first == null e first.dato == val) sulla lista ricevente e poi, solo se questi falliscono, si introduce il cursore nel modo standard. Naturalmente, se first.dato è uguale al valore di input, si modifica il first, ma sulla lista originale, non sul cursore. A questo punto, però, il cursore è indietro di un elemento nel controllo: nell'esempio, il suo first è 7, ma 7 è già stato controllato. Ma questo è proprio quello che ci serve (mantenere il riferimento all'elemento precedente). Se, infatti, l'elemento da cancellare è il 33, è il next dell'elemento 7 che va modificato. I metodi risultanti sono nel riquadro successivo. Notate che un problema analogo (con una soluzione analoga) si presenta per l'inserimento di un elemento 'prima' di un elemento specificato. Lascio a voi, come esercizio, la stesura dei metodi relativi.


public boolean deleteElem (int val)


else


else

} }


private boolean deleteElemIntern (int val)


else


else

} }


Proc. 14 - deleteElem: Cancella un elemento da una lista



1.8 La classe LinkedList di Java


Come sappiamo, molte classi sono già predefinite in Java. Questo ha lo scopo di mettere a disposizione del programmatore degli strumenti che gli evitino del lavoro supplementare. In effetti, tutto ciò che noi abbiamo fatto fin qui sulle liste è inutile, in quanto tutte le operazioni che noi abbiamo definito tramite nostri metodi sulle liste si possono effettuare usando, anziché MiaLista, la classe Java LinkedList. Ovviamente, lo scopo della definizione di una nostra classe è quello di imparare a programmare, e la stesura e lo studio dei vari metodi che abbiamo visto fin qui dovrebbe aver aiutato a chiarire le idee sull'uso dei riferimenti e della ricorsione. E questo, dopotutto, è lo scopo del corso di Programmazione: imparare a programmare.

Visto però che la classe LinkedList si comporta in modo un po' diverso dalla classe MiaLista, è bene chiarire le differenze. Sebbene l'organizzazione interna delle liste sia del tutto analoga, vi è una differenza molto importante. In un metodo esterno a quelli da noi definiti (per intenderci, un qualunque metodo che non faccia parte della classe MiaLista) non vi è alcun modo per posizionarsi su un elemento intermedio di una lista. Tutti i messaggi che si possono inviare (inLista, insertAfter, deleteElem, .) si riferiscono alla lista come un tutt'uno. Solo internamente alla classe abbiamo introdotto un cursore, che permette di spostarsi, e che mantiene una posizione diversa dall'inizio della lista; questo cursore, però, non è visibile dall'esterno in quanto è una variabile interna ai metodi.

L'approccio seguito nell'implementazione della classe LinkedList permette, al contrario, di utilizzare un cursore direttamente in un metodo esterno. Il termine che usa Java per indicare un cursore è iterator. Il procedimento che consente ad un metodo di acquisire un'istanza di iterator è il seguente:

LinkedList listaEsempio = new LinkedList ();


ListIterator cursore = listaEsempio.listIterator ();

A questo punto cursore è un'istanza di ListIterator, e quindi un normale oggetto Java, che può ricevere dei messaggi. Ad esempio:

cursore.next ();

per spostarsi in avanti sulla lista, o

cursore.remove ();

per cancellare l'elemento attuale della lista. Ci si può chiedere come si fa a realizzare la remove, visto il problema, che noi abbiamo affrontato nel paragrafo precedente, di modificare il puntatore dell'elemento che precede quello da cancellare. La soluzione, per LinkedList, sta nella seconda differenza fondamentale rispetto alla nostra implementazione: le liste di Java hanno un 'doppio collegamento', e cioè ciascun elemento include sia il riferimento al successivo che il riferimento al precedente (così come si può accedere direttamente non solo al first della lista, ma anche al last).

Ma c'è anche una differenza sostanziale di approccio: nella nostra implementazione, noi abbiamo 'isolato' (incapsulato) le liste in modo molto più rigido. A rigore, questo è più vicino all'idea di base della programmazione ad oggetti: limita l'interfaccia verso l'esterno alle operazioni utili, mantenendo all'interno della classe tutti i dettagli implementativi; tra questi, ad esempio, vi sono le modalità di uso del cursore e le primitive di spostamento sulle liste. Naturalmente, il nostro è stato solo un esercizio, ed è chiaro che la classe LinkedList offre al programmatore una flessibilità molto maggiore: essa è cioè uno strumento per un programmatore e non per l'utente finale delle liste.


Ancora sulla memoria


Vorrei qui dare qualche informazione supplementare sulla gestione della memoria. In particolare, sul ruolo dello stack e sul garbage collector.

Ho già osservato, in un precedente richiamo di Java, che lo stack è, a differenza dello heap, organizzato in blocchi (record di attivazione). Compito principale dello stack è di consentire l'esecuzione dei metodi, mettendo a disposizione spazio per le variabili locali e per gli argomenti. Lo stack (pila) è appunto organizzato come una pila: subito prima che un metodo inizi l'esecuzione, viene riservato per esso in cima allo stack (e quindi, come in una pila, sopra i blocchi già esistenti) un gruppo di celle, la cui dimensione dipende dal metodo (quante variabili usa, quanti argomenti ha). Quando il metodo avrà terminato l'esecuzione, il suo blocco si troverà in cima allo stack e verrà 'eliminato'. Quindi, quando un metodo inizia si 'mette' un blocco in cima alla pila, quando termina si 'toglie' un blocco dalla cima della pila. Ho usato i termini 'mettere' e 'togliere' tra virgolette, per ricordare che stiamo parlando di memoria, che è già lì: non si può metter o togliere nulla, fisicamente. Quello che in realtà succede è che parte della memoria centrale della macchina è riservata allo stack (ad esempio, dalla cella 124.001 alla cella 280.000). Ad un certo istante, parte di queso spazio sarà 'occupato' dai blocchi dei metodi in esecuzione (ad esempio dalla cella 124.001 alla cella 176.820). In questa situazione, 'mettere' un blocco sullo stack quando inizia l'esecuzione del metodo X vuol dire semplicemente che (se le informazioni necessarie per l'esecuzione di X occupano 120 celle) le celle dalla 176.821 alla 176.940 verranno riservate per le informazioni di X: a questo punto, la parte di stack occupata (lo stack) va dalla cella 124.001 alla cella 176.940, mentre la parte di memoria libera per eventuali 'crescite' dello stack va dalla cella 176.940 alla cella 280.000 (v. fig. 16).














Figura 16: Allocazione di un nuovo blocco sullo stack



Ci si può chiedere, a questo punto, come mai ci sono tanti blocchi sullo stack, se la macchina ha un unico processore, e quindi (per un certo programma) ci può essere un solo metodo davvero in esecuzione. Il fatto è che se un certo metodo (diciamo il main), durante la sua esecuzione, ha inviato un messaggio, questo ha prodotto l'esecuzione del metodo associato a quel messaggio (chiamiamolo X). A questo punto ci sono due metodi contemporaneamente in esecuzione: il main (che è in realtà sospeso in attesa che termini X), e X stesso. E se X invia un messaggio che richiede l'esecuzione del metodo Y, a quel punto ci saranno tre metodi in esecuzione: main, X e Y (e quindi tre blocchi sullo stack). Nel momento in cui Y termina l'esecuzione, lo spazio riservato per il suo blocco viene reso nuovamente disponibile: lo stack si è rimpicciolito! Notate che quando Y termina, saranno già terminati tutti i metodi che Y può aver chiamato. Ciò vuol dire che a quel punto il suo blocco è quello in cima allo stack; come si diceva, sullo stack si mette sempre in cima (sul 'top') e si toglie dalla cima. Uno dei motivi per cui lo stack deve essere piuttosto grande è che lo stesso meccanismo si applica anche nel caso di chiamate ricorsive. Se voi osservate, ad esempio, l'ultimo metodo che abbiamo scritto (deleteElemIntern, nel riquadro Proc.14), vedete che esso invia, se non si è ancora trovato l'elemento da cancellare, un messaggio di deleteElemIntern, dopo aver posizionato il cursore sul successivo elemento della lista. Questo comporta l'aggiunta di un blocco sullo stack. Questo blocco avrà la stessa struttura del precedente, ma viene inviato ad un oggetto che si riferisce ad una lista 'più corta'. Se l'elemento da cancellare è il 100-esimo della lista, questo procedimento verrà ripetuto 99 volte, e quindi in cima allo stack ci sarà una sequenza di 99 blocchi, tutti relativi ad una esecuzione di deleteElemIntern (ma su una lista sempre più corta).

















Figura 17: Allocazione di blocchi sullo stack in caso di chiamate ricorsive



Prima di passare allo heap, vediamo ancora, a grandi linee, cosa c'è in ogni blocco sullo stack. Le informazioni necessarie per l'esecuzione di un metodo sono sostanzialmente 4:

Il riferimento all'oggetto ricevente (per poter, ad esempio, accedere alle sue variabili di istanza)

Gli argomenti del metodo (e cioè i valori assunti dai parametri)

Le variabili locali del metodo

Un indirizzo 'di ritorno', e cioè qualcosa che dica da che punto bisogna continuare l'esecuzione del metodo chiamante dopo che l'esecuzione di questo metodo è terminata.

Se consideriamo quindi deleteElem supponendo che esso sia stato richiamato dal main inviando un messaggio all'oggetto listaEsempio, come nell'esempio che segue

public static void main (string [] args)



allora il blocco di deleteElem dovrà contenere (nella figura i dati compaiono all'incontrario solo perché, come al solito, ho supposto che lo stack sia caricato dal basso verso l'alto):


















Figura 18: Contenuto di un blocco sullo stack


Dovrebbe essere chiaro, a questo punto che, anche se la struttura dei blocchi di deleteElemIntern che compaiono nella fig.17 è sempre la stessa, il loro contenuto cambia, in relazione all'informazione 3 (variabili locali), in quanto il contenuto di cursore sarà diverso (avanzamento sulla lista) in ciascun blocco.

Torniamo ora allo heap. Come si è detto, lo heap non ha una struttura interna: esso è costituito semplicemente da un insieme di celle (una sequenza di celle, ovviamente, come in tutta la memoria), che può essere usato per memorizzare gli oggetti. Quando viene richiesta una new, compito di Java è:

Determinare quanto spazio occupa l'oggetto (e questo è noto in base alla definizione della classe; notate che, per i vettori, questo passo 1 non può essere effettuato fin quando non si dice a Java quanto è lungo il vettore, ed in effetti, quando si fa la new 'bisogna' dirlo).

Andare a cercare nello heap delle celle 'libere' in quantità sufficiente per memorizzare i dati della nuova istanza (le celle sono consecutive, cioè una dopo l'altra).

Restituire al metodo che ha richiesto la new l'indirizzo della prima di queste celle (il riferimento alla nuova istanza).

D'ora in poi, il metodo che ha richiesto la new avrà in una sua variabile il riferimento all'istanza e potrà 'lavorarci' sopra come meglio gli aggrada.

Ci si può chiedere a questo punto se non esiste una operazione 'inversa' della new, cioè un'operazione che, così come la new richiede di occupare nuove celle dello heap, richiede di lasciare libere delle celle dello heap che prima erano occupate. Questo sembra ragionevole: dopotutto, quando ho terminato la cancellazione dell'elemento (ad esempio) che cosa me ne faccio del cursore sulla lista? Non mi serve più, ed è quindi solo spazio occupato inutilmente sullo heap. Ebbene, in Java, non esiste nessuna operazione di questo tipo (analoga alla delete in C++, o alla dispose in Pascal). Non c'è alcun modo per il programmatore, di dichiarare che lo spazio occupato da un oggetto deve essere reso libero. Ma allora come è possibile che, con tutta questa inutile spazzatura, lo heap prima o poi non si riempia? Mentre i programmi girano, è anche in esecuzione un programma di Java che si occupa di garbage collection (raccolta di spazzatura, appunto), che fa le cose seguenti:

Determina quali oggetti non sono più in uso

Fa sì che lo spazio occupato da questi oggetti sia considerato spazio libero (disponibile per nuovi oggetti)

E' evidente che i garbage collectors sono programmi molto complicati: come si fa a sapere se non esiste, da nessuna parte, un riferimento ad un oggetto? Come viene identificato lo spazio libero? Ciononostante, essi evitano al programmatore gran parte del lavoro (ed anche possibili errori).



1.10 Le eccezioni in Java


Era mia intenzione far vedere ora come è possibile leggere i dati (di un vettore, di una lista, o di qualunque altro tipo) da un file. La lettura da file, però presuppone la possibilità di effettuare un controllo da programma di eventuali errori che si verifichino nel corso della lettura. Di conseguenza, prima di parlare dell'Input-Output da files, è necessario dire due parole sulla gestione degli errori in Java, e cioè sulle eccezioni.

Nel corso dell'esecuzione di un metodo X possono verificarsi degli errori (ad esempio, ho cercato di prelevare l'elemento vettore[15], ma vettore è formato da solo 10 elementi). In questi casi, il metodo deve interrompere l'esecuzione e inviare un messaggio di errore, che permetta di stabilire quale errore si è verificato. A chi dovrà essere inviato questo messaggio? In linea di principio, sarà il metodo che ha richiesto l'esecuzione di X (diciamo Y) che riceverà l'informazione che si è verificato un errore. Ciò significa che, dopo il messaggio che richiede l'esecuzione di X, Y dovrà inserire una istruzione che verifichi che non ci siano stati errori (presumibilmente una if). Purtroppo, in situazioni reali, l'esecuzione di un metodo è prodotta da una serie di 'richiami' in cascata: il metodo W ha richiesto l'esecuzione del metodo Z, che ha richiesto l'esecuzione del metodo Y, che ha richiesto l'esecuzione del metodo X. Di conseguenza, non solo Y, ma anche Z e W dovranno preoccuparsi di verificare eventuali situazioni di errore. In molti casi, però, i metodi intermedi (Z e Y, nell'esempio) non possono fare nulla per gestire l'errore, eccetto che passare a loro volta il messaggio di errore al metodo chiamante. Y riceve la segnalazione di errore da X e la passa a Z, il quale la passa a W, che, forse, può fare qualcosa di utile. La situazione è mostrata nella figura 19, in cui le linee continue rappresentano l'invio di messaggi che attivano i metodi e le linee sottili tratteggiate rappresentano il completamento del metodo con invio del messaggio di errore. Come si vede, sia il Metodo Y che il Metodo Z debbono necessariamente effettuare un controllo, per verificare la presenza di un errore. Tutto ciò sarebbe inutile se fosse possibile al Metodo X inviare direttamente a W (che, abbiamo supposto, è in grado di trattare l'errore) la segnalazione di errore. E' proprio questo che è consentito dal meccanismo delle eccezioni in Java.























Figura 19: Rientri da metodi in presenza di una situazione di errore



E' chiaro, d'altronde, che il rientro dal metodo X non può avvenire tramite una normale return. E' anche evidente che il metodo X non può essere obbligato a sapere chi tratterà l'errore: l'unica cosa che deve sapere è il tipo di errore che è stato prodotto. Ed in effetti, ciò che deve fare X è semplicemente di 'lanciare' verso l'alto la segnalazione di errore, mentre sarà compito del metodo W 'catturare' la segnalazione lanciata. Ed è proprio questo che prevede Java: per 'sollevare' un'eccezione, X farà una throw dell'errore, mentre W avrà (se il programma è scritto correttamente) predisposto una catch per intercettare quel tipo di errore. In realtà, W dovrà aver fatto qualcosa di più: anziché includere semplicemente delle istruzioni (e cioè dire implicitamente: esegui le istruzioni che seguono), dovrà essere stato più prudente, dicendo: prova a eseguire il seguente blocco di istruzioni, e se per caso viene sollevata un'eccezione, trattala nel modo opportuno. In definitiva, le operazioni richieste sono le seguenti:

Nel metodo W

try

catch (ClasseEccezione variabile)

;

Nel metodo X

ClasseEccezione varErrore = new ClasseEccezione ();

throw varErrore;

o, più semplicemente:

throw new ClasseEccezione ();

In cui ClasseEccezione deve essere una di quelle previste da Java. Esempi di tali classi sono IOException (errore di input/output), EOFException (tentativo di lettura da un file in cui non ci sono più record da leggere, un tipo particolare di IOException), IllegalArgumentException (argomento non consentito per un metodo), NullPointerException (tentativo di inviare un messaggio tramite un riferimento che ha valore null), ecc.

Ovviamente, questo meccanismo per trattare gli errori non è, di norma, obbligatorio: il programmatore può decidere se preferisce una sequenza di return, o preferisce sfruttare il trattamento delle eccezioni. Vi sono però alcuni casi in cui il compilatore Java obbliga il programmatore a inserire la gestione delle eccezioni.

Uno di questi casi è proprio l'input-output da file, in cui, ovviamente, il file deve esistere. Quando si dice (vedremo come nel prossimo paragrafo) che si vuole utilizzare un certo file, il compilatore Java si preoccupa di ciò che può succedere se tale file non esiste. In tal caso, infatti, il metodo Java che si occupa di 'aprire' il file solleva un'eccezione (throw) e sarà compito del nostro metodo fare la catch, in modo da specificare cosa si deve fare se il file non esiste. Se tale catch manca, il compilatore segnala un errore e non si può procedere con l'esecuzione.

Un altro caso in cui potrebbe essere utile la gestione delle eccezioni è il metodo getFirstDato (riquadro Proc.9): se un metodo ha un tipo diverso da void, il compilatore richiede che per ogni possibilità di uscita dal metodo stesso, il tipo sia quello specificato. Per cui, se il metodo è int, ed è costituito da una if, deve essere prevista la restituzione di un intero sia quando la condizione della if è verificata, sia quando non lo è. Nel caso della getFirstDato, abbiamo supposto che i valori della lista fossero tutti interi positivi (e quindi -1 non può essere il valore di un elemento e può essere interpretato come 'fine lista'). Ma se anche gli interi negativi possono comparire nella lista, questa soluzione non funziona. Quello che si può fare è di sollevare un'eccezione quando si cerca di prelevare un valore da una lista vuota. Questa nuova versione della getFirstDato è riportata nella prima parte del riquadro Proc.15. Nella seconda parte del riquadro, è riportata la nuova versione della printList, che gestisce l'eccezione.


public int getFirstDato () throws noSuchElementException


else


}


public void printList ()


catch (noSuchElementException nSEE) ;

loopElem.advance ();};

System.out.println ("");}

Proc. 15 - getFirstDato e printList con trattamento delle eccezioni


Nella getFirstDato, compare la throw nella forma che abbiamo specificato. Da osservare solo la necessità di indicare nell'intestazione del metodo (dopo la lista dei parametri), che questo è un metodo che può sollevare un'eccezione (throws noSuchElementException). Più sostanziali sono le modifiche di printList. Innanzitutto, il body della while è stato inserito all'interno della clausola try: come abbiamo detto, ciò è da interpretarsi come: esegui il body, a meno che durante l'esecuzione non siano sollevate eccezioni. Nel caso, invece, in cui ci sia un'eccezione, vedi se non riesci a intercettarla tramite la catch. L'unica eccezione che questo metodo è in grado di trattare è noSuchElementException, e in tal caso l'unica cosa da fare è uscire dalla while (break). La label nSEE può essere usata, in altri casi, per avere maggiori dettagli sui motivi dell'eccezione, ma noi non ne parleremo qui (una label - qualsiasi - è comunque obbligatoria).

E' tutto, come si vede, abbastanza semplice, ma c'è un'ultima complicazione. noSuchElementException non è un'eccezione nota a Java: tale classe non è definita. Come in tutti i casi in cui serve una classe che non c'è, è compito del programmatore definirla. Non è qui il caso di approfondire i metodi per la definizione di proprie classi di eccezioni. La cosa più semplice è dire solo che noSuchElementException è un tipo di eccezione: per far ciò, è sufficiente introdurre, in un nuovo file, la definizione:

class noSuchElementException extends Exception

che dice che noSuchElementException è una nuova sotto-classe (extends) della classe Java Exception. Solo a questo punto, la new noSuchElementException (); è riconosciuta e accettata dal compilatore.


1.11 Input e output con files


Se ora vogliamo fare degli esperimenti, per verificare che la classe MiaLista funzioni come previsto e che i metodi ad essa associati eseguano le operazioni volute, dobbiamo costruire delle liste che servano come test. Naturalmente, questo si può fare mediante un metodo main che chieda uno per uno gli elementi della lista dalla tastiera e che esegua una successione (ciclo) di insertFirst (v. riquadro Proc.10). In questo modo, possiamo costruire, ad esempio, una lista di 10 elementi su cui provare a fare delle cancellazioni o degli inserimenti tramite insertAfter. Supponiamo però che vi sia stato un banale errore di battitura nel ricopiare la deleteElem, o che voi stiate facendo questo lavoro per verificare una vostra versione della insertBefore; se c'è un errore non rilevato dal compilatore verrà sollevata un'eccezione e il programma terminerà. A questo punto voi potete cercare e, si spera, correggere l'errore e riprovare. Però, riprovare vuol dire inserire di nuovo, da tastiera, i 10 dati già introdotti durante la prima prova. E se c'è un altro errore? Di nuovo, dopo la correzione, si dovranno re-inserire i 10 elementi della lista.

Un primo modo per evitare questo inconveniente è utilizzare un vettore. Come abbiamo visto, si può inizializzare un vettore con una singola istruzione; poi, con un semplice ciclo, si può creare la lista corrispondente:

int [] inpVett = ;

int size = 7;

MiaLista inpList = new MiaLista ();

for (int i = size-1; i >= 0; i--)

inpList.insertFirst (inpVett[i]);

Nell'esempio, il ciclo for opera partendo dall'ultimo elemento del vettore, in modo che alla fine la lista abbia gli elementi nello stesso ordine.

Questo metodo, però, va bene per fare delle prove, ma tutte le volte che si vogliono cambiare i dati su cui effettuare la prova bisogna modificare e ricompilare il programma. Inoltre, è necessario allocare dello spazio per il vettore, che in realtà ha come unica funzione quella di fornire l'input per i test, e non verrà più utilizzato in seguito.

C'è un'altra alternativa, sicuramente più generale, ed è quella di scrivere i dati su cui effettuare le prove in un file separato da quello che contiene la classe. Una volta fatto ciò, avremo bisogno di un meccanismo che mi permetta di 'collegare' il metodo che deve leggere i dati al file che contiene i dati stessi. Questo meccanismo è costituito dai 'flussi' (inglese stream) che sono degli oggetti speciali messi a disposizione da Java. Scopo di questo capitolo è di dare un'idea del funzionamento di un tipo speciale di flusso, quello associato alla classe FileReader (esiste, ovviamente anche la classe FileWriter, e varie altre classi per l'input/output da file, ma qui, per ragioni di tempo e spazio, vedremo solo FileReader; i concetti principali che qui introdurrò sono comuni alle varie classi).

Innanzitutto, come si è detto, è necessario stabilire un collegamento tra il nostro metodo e il file esterno che contiene i dati. Questo verrà fatto (e se ne occupa Java, per cui a noi non interessano i dettagli), attraverso una particolare istanza di FileReader. Come sempre, per creare una nuova istanza, si fa una new. Ovviamente, poiché il collegamento è ad un particolare file, sarà necessario dire a FileReader qual è il file, e questo si fa con l'argomento della new, che deve essere una stringa che contiene il nome del file:

FileReader portIn = new FileReader ("dati.txt");



(ho usato il nome portIn, perché spesso i collegamenti di cui stiamo parlando vengono detti "porti", inglese port; porti da cui arrivano dati, anziché merci). La classe FileReader mette a disposizione dei metodi per leggere dei caratteri (uno alla volta) dal flusso (porto). Questo, però, è piuttosto scomodo! Debbo poi 'mettere insieme' i vari caratteri di una riga per formare il numero (supponiamo che nel nostro caso abbiamo messo un numero intero in ciascuna riga del file 'dati.txt'). Per evitare questo lavoro, Java permette di leggere tutta una riga in un colpo solo, ma il metodo che fa questo (readLine) non è associato alla classe FileReader, bensì ad una classe diversa (BufferedReader). Dovremo quindi creare un'istanza di questa classe; il lavoro che abbiamo fatto prima è però importante, perché la new di BufferedReader richiede come argomento un flusso, nel nostro caso il portIn che abbiamo appena creato:

BufferedReader lineIn = new BufferedReader (portIn);

A questo punto, abbiamo tutto ciò che ci serve per fare la lettura; dobbiamo solo decidere dove verranno messi i dati letti; poiché il metodo readLine restituisce una stringa, avremo bisogno di una variabile di tipo stringa:

string nxtLine;

e l'operazione di lettura vera e propria sarà:

nxtLine = lineIn.readLine ();

Ovviamente, la classe BufferedReader avrà al proprio interno una variabile che contiene la posizione sul file, così che ogni volta che si esegue l'operazione precedente si 'avanza' leggendo la linea successiva del file. Ora, però, a che punto siamo arrivati? Abbiamo in nxtLine una stringa che contiene il numero intero della prossima riga (ad es. "137"). Ma una string è diversa da un int. Non possiamo quindi usare direttamente ciò che è stato letto per inserire i dati nella lista; se io faccio:

insertFirst (nxtLine);

avrò una segnalazione di errore, perché la insertFirst ha come argomento int val. Ciò che si deve fare è effettuare una 'conversione' da stringa a intero. Questa non è un'operazione banale, ma per fortuna un metodo che fa questo esiste già: è un metodo della classe Integer e si chiama parseInt. E quindi, prima di procedere alla memorizzazione nella lista, faremo ancora:

newVal = Integer.parseInt (nxtLine);

Dove newVal sarà stato definito di tipo int.

Come si diceva in precedenza, tutto ciò richiede anche un trattamento delle eccezioni. In particolare, vi sono due problemi che potrebbero verificarsi:

Per qualche motivo il file di input non esiste (ed es. ho sbagliato a scrivere il nome, o il file è stato cancellato). In questo caso, new FileReader solleva un'eccezione di tipo FileNot Found Exception.

La linea da convertire tramite parseInt, non contiene, come dovrebbe, una stringa che rappresenta un intero. Questo, in particolare, si verifica alla fine della lettura del file, in cui la stringa è la stringa vuota (""). In questo caso, l'eccezione prodotta da parseInt è della classe numberFormatException.

Ma noi sappiamo ora come comportarci (v. sezione precedente): ogni volta che potrebbe verificarsi un'eccezione, le operazioni corrispondenti vengono inserite in una try e dopo il blocco incluso tra parentesi viene posta una catch. Questo dobbiamo farlo qui due volte (separatamente): la prima per l'intero corpo del programma (che potrebbe fallire per mancanza del file:

public void readListFromFile ()


catch (java.io.FileNotFoundException fileNotFound)


}

La seconda try va invece inserita nel loop:

while (contin)


catch (NumberFormatException nFE)

;

}; // fine while

In questo modo, la variabile booleana contin, inizializzata a true, viene messa a false quando si rileva l'eccezione, e il ciclo termina. Nel riquadro Proc.16 trovate il metodo completo. Notate solo che la lista viene letta all'incontrario: il numero nella prima linea del file sarà l'ultimo elemento della lista. Per evitare ciò, è sufficiente definire insertLast (un metodo che inserisce un nuovo elemento in fondo, anziché all'inizio) e usare questo metodo al posto di insertFirst.


public void readListFromFile ()


catch (NumberFormatException nFE)

;

}; // fine while

} // fine try open file

catch (java.io.FileNotFoundException fileNotFound)


}


Proc. 16 - readListFromFile: Leggi una lista da un file


A questo punto, possiamo scrivere un programma che sia in grado di effettuare diverse operazioni su una lista.

Il main è costituito da due parti:

Lettura dei dati dal file (con creazione della lista iniziale) e loro visualizzazione sul monitor

Ciclo while in cui si chiede all'utente quale operazione vuole effettuare. Il ciclo è 'infinito', nel senso che la while continua fino a quando l'utente non dice che vuole finire (operazione=9).


import java.io.*;

public class Liste


else


break;

case 5:

newval = Console.readInt (" Elemento da cancellare? ");

inpList.deleteElem (newval);

System.out.print (" Risultato: ");

inpList.printList ();

break;

case 6:

oldval = Console.readInt (" Elemento da modificare? ");

newval = Console.readInt (" Nuovo valore? ");

inpList.modifElem (oldval,newval);

System.out.print (" Risultato: ");

inpList.printList ();

break;

case 9:

break;

default:

System.out.println("Operazione non prevista");

break;

} // End of Switch!

} // End of While!

} // End of main!


} // End of Liste Class definition

Proc.17 - Operazioni di base sulle liste


Il body della while è formato dalla presentazione dell'insieme di operazione possibili, seguita dalla lettura dell'operazione desiderata dall'utente e da un'istruzione switch.

L'istruzione switch è molto semplice dal punto di vista concettuale. Essa ha il compito di evitare la scrittura di inutili sequenze di

if (condiz1)

// (caso 1)

else

// (caso 2)

else

// (caso 3)

...

L'istruzione sopra dice che se è vera condiz1, allora bisogna eseguire op1, altrimenti, se è vera condiz2, allora bisogna eseguire op2, ecc. Lo scopo della switch è quello di consentire di non scrivere tutti gli 'allora' e 'altrimenti'. In altre parole, si dice solo: a seconda del caso in cui ti trovi, devi fare: se il caso è condiz1, op1; se il caso è condiz2, op2; ecc. Dal punto di vista sintattico (e cioè di come va scritta) la switch è fatta nel seguente modo:

switch ('espressione')


'espressione' è qualcosa che in Java ha un valore (ad esempio una variabile, un elemento di un vettore, un campo di un record, un metodo non void, un'espressione aritmetica, ecc.). val1, val2, ., valn sono i possibili valori dell'espressione. Quindi, quando si esegue una switch, se il valore di 'espressione' è uguale a val1, allora verranno eseguite le operazioni op11, op12, ., se il valore è uguale a val2, allora verranno eseguite le operazioni op21, op22, . e così via. Nel nostro caso 'espressione' è data semplicemente dalla variabile optype. Per cui, se l'utente ha scritto 1, verrà eseguita la parte di programma che segue l'indicazione case 1 (e cioè quella che si occupa delle operazioni di modifica della lista). Analogamente, negli altri casi. Tutto è molto semplice. Solo quattro osservazioni sono necessarie:

Le istruzioni op possono anche essere 'vuote'. E cioè è possibile che, per alcuni valori di 'espressione', non si debba fare niente (questo è il caso di 9 nell'esempio).

Se l'espressione assume un valore non previsto, l'effetto della switch è quello specificato nello operazioni che seguono default.

Solo i 'tipi' di valori cosiddetti 'scalari' sono permessi per 'espressione' (e, ovviamente, per le corrispondenti etichette). Essi includono interi e caratteri, ma escludono numeri reali, riferimenti, stringhe.

Ogni blocco di operazioni è terminato da un break. Il break non è obbligatorio: se esso manca, l'esecuzione continua con le istruzioni del caso successivo.

A questo punto, l'effetto della switch nel nostro programma dovrebbe essere ovvio (ricordando che essa si trova all'interno del ciclo while):

Se l'utente scrive 1, 2, 3, 4, 5, o 6 viene eseguita la parte di programma associata a tale valore. Una volta fatto ciò, l'esecuzione della switch termina e si controlla la condizione di uscita dalla while. Poiché essa è falsa (il valore non è 9), si ripete il ciclo, chiedendo una nuova istruzione all'utente, ed eseguendo nuovamente la switch.

Se l'utente scrive 9, la switch non fa nulla (istruzione vuota) e termina. La while esterna verifica che la condizione di fine ciclo è verificata e l'esecuzione del programma è completata.


Merge-Sort sulle liste


Possiamo ora tornare al nostro problema originale, cioè quello del Sort. Come ho già detto più volte, l'algoritmo non cambia. Lo riporto quindi qui come l'avevamo descritto in modo informale in precedenza:


Per fare il merge-sort di una pila di N fogli:

Suddividi la pila in 2 pile da N/2 (circa) fogli ciascuna;

Fai il merge-sort di ciascuna sottopila

Fai il merge delle 2 pile da N/2 fogli che sono state appena ordinate

N.B. Se N vale 1, non fare nulla, perché la pila è già ordinata


Il metodo è esattamente come all'inizio, con l'unica differenza che ho diviso in 2 pile, anziché in 4, come avevamo già fatto per l'implementazione con i vettori.

Cominciamo quindi ad affrontare la prima delle due 'operazioni extra' (suddivisione e merge), e cioè la suddivisione della pila (che ora è rappresentata come lista) in due sottoliste.

Come input alla procedura di suddivisione avremo una lista (o meglio, come abbiamo visto, il riferimento all'inizio della lista). Come risultato, dobbiamo ovviamente avere due liste (o meglio, due riferimenti alle due metà). Graficamente, la situazione è riportata sotto. Nella figura, inpList è il riferimento alla lista in input, mentre outList1 e outList2 sono i riferimenti alle due liste di output. Quindi, una possibile intestazione del metodo è la seguente:

public void split (MiaLista outList1, MiaLista outList2);

Ovviamente, inpList sarà il ricevente del messaggio splitList.

Ora possiamo passare al body del metodo. Sappiamo che qualunque operazione su una lista impone una 'scansione' (e cioè l'attraversamento) della lista. Sappiamo anche cosa vogliamo fare: mettere null nell'elemento 44 e mettere il riferimento che era prima associato a 44 (quello a 29), come first del secondo argomento del metodo. Però c'è un problema! Come stabilisco che l'elemento su cui fare queste operazioni è proprio il 44? Beh, perché è quello a metà della lista (lasciamo perdere il problema delle liste di lunghezza dispari, che, come abbiamo visto nel caso dei vettori, è facilmente risolvibile)! Già, ma come faccio a sapere dove sta la metà della lista? Nel caso dei vettori era facile, perchè lì sono obbligato a specificare la dimensione totale del vettore. E quindi, visto che la sequenza è lunga 10, il quinto elemento (e cioè 44) è quello subito prima della metà. Ma nelle liste non è così! E quindi ho solo due alternative: o assumo che mi venga data in input la lunghezza totale della lista, o sono obbligato a trovarmela. L'unico modo per trovarla è percorrere tutta la lista contando gli elementi. Perciò, in questo caso, devo prima percorrere tutta la lista per stabilirne la lunghezza (10), poi dividere per due e ricominciare dall'inizio della lista per contare fino a 5 e trovare l'elemento intermedio (il 44). Ciò è molto seccante (pensate sempre alla lista di lunghezza 1000)! Vedremo però fra breve che c'è un metodo molto più 'astuto'.

Prima di continuare vorrei ribadire ancora che, come si vede anche dalla figura, il riferimento all'inizio della lista è una cosa ben diversa dalla lista in sè. E questo avrebbe dovuto essere chiaro dalle operazioni di base sulle liste che abbiamo visto: Cambiare una lista non vuol dire cambiare il riferimento al suo inizio! Ad esempio, per aggiungere un elemento a metà di una lista, il riferimento all'inizio non è modificato. Quindi, lo stesso riferimento identifica dopo l'operazione una lista diversa da quella che si aveva prima dell'operazione: il riferimento è lo stesso, perché l'indirizzo del primo elemento è lo stesso, ma la lista è diversa, perché rappresenta una sequenza con un elemento in più.



Figura 20: Split di una lista


Torniamo ora al metodo in sè, supponendo, ad esempio, che la lunghezza della lista sia già data in input. Facciamo inizialmente l'ipotesi che la lista in input non mi serve più dopo l'esecuzione del metodo

Se questa ipotesi non è corretta, non devo solo dividere in due la lista, ma devo creare 'una copia' della prima metà e 'una copia' della seconda metà. Ciò significa che, se la lista è lunga 100, dovrò eseguire 100 istruzioni new durante l'esecuzione del metodo (e riservare dunque 200 nuove celle). Ma se l'ipotesi è corretta, non devo copiare nulla! E' sufficiente che metta nel riferimento associato a 44 il valore null e che metta nel first di outList2 il riferimento alla seconda metà (cioè a 29). Ma ora cos'è successo a inpList, e qual è il valore da associare a outList1? Il first di inpList non è stato modificato e quindi continua a puntare a 55. Però non si riferisce alla stessa lista di prima, ma a una lista che finisce dopo il 44! E outList1 deve riferirsi esattamente alla stessa lista. E allora, a cosa serve avere due riferimenti uguali? Possiamo lavorare con solo 2 riferimenti, anziché 3: il primo punta, all'inizio, alla lista intera e, dopo l'esecuzione del metodo, alla prima metà della lista suddivisa. Il secondo punterà, come prima (outList2), alla seconda metà della lista. Possiamo ora provare a scrivere il metodo che esegue queste operazioni (assumendo di non avere in input la lunghezza, e quindi di doverla calcolare).

Public void splitList (MiaLista outList2)

Non so ancora quali variabili locali mi serviranno. Però, certo, avrò bisogno della lunghezza della lista, e di un cursore per avanzare sulla lista (potrei anche usare outList2, ma non facciamo confusione). Introduciamo, per ora, length e cursore.

int inpLength;

MiaLista cursore;

Per prima cosa, troviamo la lunghezza totale della lista originale. Se lo facciamo in modo iterativo, avremo bisogno di un ciclo, per avanzare sulla lista, che incrementi length ad ogni passo e che termini quando la lista è finita. length, all'inizio, deve essere 0. Poiché non sappiamo quante volte il body del ciclo verrà ripetuto (è proprio quello che vogliamo trovare), non possiamo usare una for. Poiché la procedura può terminare subito (cioè senza che il body sia eseguito neppure una volta, nel caso in cui la lista sia vuota, e cioè non abbia nessun elemento) forse una while è la scelta più corretta. Proviamo:

inpLength = 0;

cursore.first = first;

while (cursore != null)


Questo è un altro esempio di ciclo 'scomodo', e cioè facile da scrivere, ma lungo da eseguire (devo percorrere comunque tutta la lista fino in fondo). All'uscita, avremo in length la lunghezza cercata. Ora possiamo dividere per due:

int halfLenght = inpLength / 2;

(potevamo riusare length, ma non siamo così spilorci!)

E ora, finalmente, la suddivisione vera e propria:

cursore.first = first;

for (int i = 1; i <=halfLength; i++)

cursore.first := cursore.first.next;

Il ciclo sopra per posizionarsi sull'elemento a metà della lista (il nostro 44). Questo è l'unico punto un po' delicato. A cosa punta adesso cursore, al 44, o al 29 che lo segue? Sebbene la risposta corretta sia 'considerate l'invariante di ciclo', il suggerimento che posso darvi è quello di 'simulare' l'esecuzione su un caso semplice. Supponiamo che la lista iniziale sia lunga 2. Allora halfLength vale 1 e, all'inizio del ciclo for, il first di cursore punta al primo dei due elementi. Poiché il valore iniziale della variabile di ciclo e quello finale coincidono (ambedue valgono 1), il ciclo viene eseguito una volta. Al termine, il first di cursore si riferirà al secondo elemento. Quindi, generalizzando, alla fine cursore punta al primo elemento della seconda metà, e non all'ultimo della prima metà! Ma allora il ciclo sopra è sbagliato!!! Perchè adesso devo modificare i riferimenti. Posso facilmente assegnare al first di outList2 il first di cursore, così ho trovato la seconda metà della lista, ma come faccio a mettere nel puntatore associato a 44 il valore null? Dove sta il 44? Sono già andato troppo avanti (e sulle liste, come le abbiamo viste noi, non si può tornare indietro). Allora, continuare il ciclo solo fino a che i< halfLength è la soluzione giusta:

for (int i = 1; i < halfLength; i++}

cursore.first = cursore.first.next;

outList2 = cursore.first;

cursore.first.next = null;

Il metodo finale è dunque:


public void splitList (MiaLista outList2)

;

halfLenght = inpLength / 2;

cursore.first = first;

for (int i = 1; i < halfLength; i++)

cursore.first = cursore.first.next;

outList2.first = cursore.first.next;

cursore.first.next = null;



Proc. 18 - splitList: dividi una lista in due metà (versione 1)


Come si diceva prima, c'è però un modo per evitare di scorrere la lista due volte (una volta e mezzo, in realtà). Si deve considerare che stiamo qui lavorando sulla lista in input, e cioè 'disordinata', per cui non ci interessa quali elementi saranno alla fine nelle due mezze liste: l'ordinamento si farà dopo. Tutto ciò che ci interessa è che le due liste siano della stessa lunghezza (con una differenza al massimo di 1, se la lista iniziale ha lunghezza dispari). Allora, anziché mettere la prima metà degli elementi nella prima mezza lista e la seconda metà nella seconda mezza lista, possiamo scorrere la lista mettendo alternativamente prima un elemento nella prima sottolista e poi un elemento nella seconda, e poi di nuovo nella prima, e così via, ottenendo, alla fine, la situazione della prossima figura.





Figura 21: Un altro modo per fare lo split di una lista


Per ottenere questo risultato, è sufficiente avanzare sulla lista di due elementi per volta, mettendo (o lasciando) il primo elemento nella prima lista e mettendo il secondo nella seconda. Proviamo a farlo in modo ricorsivo

La condizione di terminazione? Qui, per la prima volta, ne abbiamo due! Infatti, poiché si avanza di due elementi per volta, bisogna fermarsi o quando non ci sono più elementi (siamo in fondo alla lista, che era di lunghezza pari) o quando ne è rimasto solo 1 (la lista era di lunghezza dispari).

Le operazioni supplementari? Metti il secondo elemento nella seconda lista (e lascia il primo nella prima). Tutto si fa con due operazioni di assegnazione, più la chiamata ricorsiva. Ma poiché come questo funziona mi sembra piuttosto complicato, cerchiamo di capire cosa deve succedere.


Proviamo a ragionare sullo split iniziale di una lista. Supponiamo che ci siano almeno due elementi. Il ragionamento, a livello di ricorsione è il seguente: se io effettuo una chiamata ricorsiva della mia procedura con inpList che si riferisce al terzo elemento della lista, e le passo outList2 come argomento, allora il metodo modificherà inpList in modo che essa sia formata da metà degli elementi della lista che comincia dal terzo elemento e in outList2 restituirà il riferimento ad una lista che contiene i rimanenti elementi. Questa è l'ipotesi ricorsiva, che abbiamo già visto in precedenza: suppongo che il metodo sia corretto (giusto) per un oggetto 'piu' piccolo' di quello iniziale (nel nostro caso una lista con due elementi di meno). Ma come devono essere sistemati i due elementi che abbiamo tolto? Possiamo vederlo nelle figure 19-21.


Figura 22: Split: situazione iniziale


Prima di effettuare la chiamata ricorsiva, dobbiamo sistemare outList2. outList2 deve puntare al secondo elemento della lista (e quindi dobbiamo copiare in esso il riferimento associato a 55 (che è contenuto in inpList.first.next; in realtà, in first.next, visto che inpList è il ricevente del messaggio)


Figura 23: Prima di un passo di split



E ora, il riferimento del 55 deve 'saltare' il 137, perché il 137 è stato messo nella seconda sottolista. Questo lo facciamo copiando nel puntatore associato a 55 (first.next) il riferimento associato a 137 (che, come si vede dalla figura, è attualmente first.next.next).


Figura 24: Dopo il passo di split


Ora possiamo effettuare la chiamata ricorsiva, ma sulla lista 'accorciata'. Quali sono i due nuovi riferimenti su cui lavorare? Il primo è inpList.first.next (e cioè l'inizio della lista ancora da suddividere) e il secondo è outList2.first.next (e cioè il riferimento associato all'elemento 137, in cui andrà messo il puntatore al secondo elemento della lista da suddividere (e cioè al 12). A questo punto, il metodo sarebbe fatto, ma c'è il solito problema di non spostare il riferimento all'inizio della lista, mentre si avanza sulla lista. In precedenza, avevamo affrontato questo problema tramite l'introduzione di un cursore. Però, ora ce ne vorrebbero 2 (uno per inpList e uno per outList). Proviamo un'altra soluzione. Uno dei problemi nello spostarsi sulle nostre liste è che c'è una differenza di tipo (ragionevole) tra le liste (MiaLista) e gli elementi della lista (listElem). Per spostarsi mediante un cursore (di tipo MiaLista), è necessario sempre operare sul first per arrivare al primo elemento della lista (di tipo listElem). Nulla però impedisce che i metodi privati (non quelli pubblici, che nulla sanno dell'esistenza di listElem) operino direttamente sugli elementi della lista. Possiamo quindi pensare che splitList 'inizializzi' l'accesso alle due liste, posizionandosi opportunamente sugli elementi, e poi usare una splitListInternal, che invece avanza ricorsivamente sugli elementi, senza più preoccuparsi dei first, che rimarranno invariati (e quindi continueranno a identificare inpList e outList) dopo l'inizializzazione.

Otteniamo così:

public void splitList (MiaLista outList2)




private void splitListInternal (listElem inpFirst, listElem outFirst)


}


Proc. 19 - splitList: dividi una lista in due metà (versione 2)



Il metodo public splitList, se la lista è vuota (first=null) o se contiene un solo elemento (first.next = null) non fa nulla, altrimenti sposta il primo elemento di inpList in outList2 ed effettua il richiamo al metodo privato, passando come parametri il primo elemento non ancora esaminato di inpList (first.next) e il primo elemento della nuova lista (outList2.first). Il metodo interno effettua gli spostamenti di riferimenti descritti sopra e richiama se stesso ricorsivamente, dopo aver avanzato sugli elementi delle due liste.


Ora possiano ritornare al problema del Merge. Il metodo è del tutto analogo a quello che abbiamo già visto per i vettori: se nessuna delle due liste è finita, si inserisce nel risultato il più piccolo tra i primi elementi delle due liste e si avanza sulla lista che conteneva quel primo elemento, e così via fino alla fine delle due liste (si veda la Proc. 5). Supponiamo che alla procedura di Merge siano passati in input due riferimenti (firstList e secondList) e che il risultato sia poi in firstList.

Ci sono quattro casi da considerare:

La seconda lista è finita. In questo caso non si fa nulla, poiché firstList si riferisce già ad una parte terminale di lista ordinata (stiamo facendo un merge e quindi le due liste in input sono ordinate). Se anche la prima lista è finita, non cambia nulla.







La prima lista è finita, ma la seconda no. In questo caso, la parte finale (ordinata) sta nella seconda lista, ma visto che noi il risultato lo vogliamo nella prima, basta copiare il first di SecondList nel first di FirstList. Il fatto che SecondList continui a puntare al suo primo elemento è irrilevante: a noi basta che sia a posto FirstList.















Nessuna delle due liste è finita e il primo elemento della prima lista è più piccolo del primo elemento della seconda lista. In questo caso, bisogna 'avanzare' sulla prima lista. Questo vuol dire semplicemente che si effettuerà il richiamo ricorsivo lasciando invariato il riferimento alla seconda lista e passando invece come primo argomento il riferimento al secondo elemento. In questo modo, al livello di annidamento attuale della procedura, firstList rimane invariata (infatti il primo elemento è già quello più piccolo delle due liste). Ma al livello successivo di annidamento (dopo la chiamata ricorsiva), firstList si riferirà all'elemento successivo (400 nell'esempio), e cioè all'inizio della lista di cui rimane da fare il merge (più 'piccola' di quella originale).


Nella figura ho lasciato non sottolineati i valori dei due riferimenti a livello di metodo chiamante, mentre ho sottolineato i valori dei due riferimenti a livello di metodo chiamato (livello successivo di ricorsione). Naturalmente secondList rimane invariato (e cioè si passerà come secondo argomento della chiamata secondList stessa), mentre FirstList deve 'avanzare' (e quindi si passerà come primo argomento firstList.next).


Nessuna delle due liste è finita e il primo elemento della prima lista è più grande del primo elemento della seconda lista. In questo caso, bisogna 'avanzare' sulla seconda lista. Ma non basta! si deve anche 'spostare' il primo elemento della seconda lista nella prima (che contiene il risultato del merge). Ora bisogna fare un po' di attenzione, perché le prossime quattro righe di Java sono piuttosto complicate; secondo me, sono il 'clou' di questa prima parte del corso, quindi non spaventatevi se vi sembrano difficili: lo sono! Per prima cosa, osserviamo bene la figura che segue.



Quello che è stato fatto è simile a quanto abbiamo già visto per le operazioni elementari sulle liste: una cancellazione (abbiamo cancellato il 164 dalla seconda lista) e un inserimento (abbiamo inserito il 164 nella prima lista). Questo è proprio quello che ci serve: il 164 è l'elemento più piccolo, e quindi va inserito nel risultato (firstList). Questa doppia operazione possiamo farla in due modi: o si utilizzano i metodi che abbiamo scritto in precedenza (richiamando prima la insertBefore e poi la deleteElem), o si eseguono le operazioni sui rifermenti direttamente. Sebbene la strada giusta in un sistema software complesso sia la prima (isolare 'sottoproblemi' di cui si conosce già la soluzione, e cioè usare precedure già disponibili), io seguirò la seconda strada per due motivi: per mantenere questo metodo 'autonomo' e per fare ulteriore pratica sulle operazioni con i riferimenti. Se a livello concettuale si tratta di due operazioni (cancellazione e inserimento), a livello di implementazione si tratta di modificare tre riferimenti. Questi riferimenti sono: firstList (in realtà, il first della lista che riceve il messaggio), secondList (in realtà il suo first) e secondList.first.next (v. figura). Con essi, bisogna fare una specie di 'scambio a 3'. Per capire cosa intendo, pensate allo scambio del valore di due variabili. Come sapete, questo si fa usando una variabile 'di supporto'. Se si deve scambiare il valore di A col valore di B, si mette il valore di A in X (la variabile di supporto), poi il valore di B in A, e infine il valore di X (che ci è servita per 'salvare' il valore originale di A) in B. Questo metodo (della variabile di supporto) si deve usare anche quando le variabili coinvolte sono più di 2. Ad esempio, se le variabili sono A, B, e C, e noi vogliamo mettere il valore di A in B, quello di B in C e quello di C in A (potete immaginare che i valori vengano fatti 'ruotare' tra le variabili), non possiamo farlo direttamente senza una variabile di supporto: in caso contrario, qualunque assegnazione facessimo per prima (ad es. C = B) ci farebbe 'perdere' uno dei valori che ci servono (nell'esempio, quello di C). E quindi la sequenza di operazioni corretta è:

X = C;

C = B;

B = A;

A = X

Potete facilmente verificare che lo stesso vale anche quando le variabili sono più di 3. Se ora osserviamo di nuovo la figura, possiamo notare che ci troviamo proprio nello stesso caso. Solo che, al posto di A, B, e C, abbiamo tre riferimenti, e cioè first, secondList.first e secondList.first.next. Ma la soluzione è la stessa: chiamiamo savElem la nostra 'variabile di supporto' e poi facciamo le 4 assegnazioni:

listElem savElem = secondList.first.next; (X = C)

secondList.first.next = first; (C = B)

first = secondList.first; (B = A)

secondList.first = savElem; (A = X)


Ora l'implementazione. Il primo problema è, come al solito, l'avanzamento sulle liste. Come nel caso della split, ci vorrebbero due cursori, ma adottiamo la stessa soluzione già vista, ed avanziamo usando i riferimenti a listElem. Per quanto riguarda l'inizializzazione, come abbiamo visto nella discussione precedente, è necessario in alcuni casi assegnare un valore al riferimento finale della prima lista (ad esempio quando la prima lista è vuota). Per far ciò, non possiamo usare come primo argomento del metodo la parte di lista ancora da esaminare: se questa fosse vuota, non potremmo tornare indietro e fare l'assegnamento di cui abbiamo appena parlato. Dobbiamo quindi fare in modo che il primo argomento si riferisca ad un elemento di lista che sia già a posto. Per ottenere ciò, il valore del primo argomento sarà inizialmente uguale al first della prima lista, ma si dovrà fare in modo che il primo elemento sia già il più piccolo di tutti, facendo quindi uno scambio iniziale, prima del richiamo alla solita mergeListInternal.

Infine, per quanto riguarda mergeListInternal, tutto procede come descritto aopra, con l'unica avvertenza che i controlli (per eventuali scambi o per la terminazione) vanno effettuati sul secondo elemento della prima lista e non sul primo, che si suppone sia già stato messo a posto nel passo precedente (per i motivi appena detti).


public void mergeList (MiaLista secondList)

;

mergeListInternal (first, secondList.first);}



private void mergeListInternal (listElem firstElem, listElem secondElem)

// Il dato di firstElem è sicuramente più piccolo del dato di secondElem


else


mergeListInternal (firstElem.next, secondElem);}

} // end of 'if (firstElem.next.dato > secondElem.dato)'

} // end of 'if (firstElem.next == null)'

} // end of 'if (secondElem!= null) '


Proc. 20 - mergeList: merge di due liste ordinate


Ora abbiamo splitList e mergeList; dobbiamo solo più scrivere la procedura di sort vera e propria. Ma questo è banale: se la lista è vuota o lunga 1, allora non si fa nulla (è già ordinata; caso di terminazione), altrimenti la si divide in 2, si ordinano le due parti, e poi si fa il merge. Finalmente, dopo un così lungo lavoro, siamo arrivati ad un programma quasi identico alla versione 'intuitiva' del metodo che avevamo descritto all'inizio!


public void sortList ()


}


Proc. 21 - sortList: ordinamento di una lista



Come avete visto in precedenza, questo non è del tutto vero! In particolare, i tipi primitivi non sono oggetti. Quelli principali sono boolean, char, int, float (oltre a questi, esistono anche byte, short, long, double). Anche void è un tipo primitivo, anche se un po' particolare

Sebbene ogni dato elementare (come int) abbia una dimensione predefinita, che è diversa a seconda del tipo (ad esempio, un int occupa 4 bytes, un char 2 bytes, un intero long 8 bytes, ecc.), io nel seguito eviterò di considerare questo problema, parlando, in generale di 'celle' di memoria. Questo è impreciso, ma semplifica notevolmente la presentazione.

Nelle procedure e nei programmi che compaiono nei riquadri non inserirò dei commenti. Questo perchè ampi commenti sono riportati nel testo. Ciò non toglie che invece voi dovete inserire commenti, visto che i vostri programmi non sono accompagnati da un testo esplicativo.

In realtà, per la macchina, le operazioni sono un pò più complicate. Infatti, il calcolatore dovrebbe scoprire che le due celle (dato e puntatore) 'cancellate' non servono più. In questo modo può utilizzarle in seguito per successive operazioni di new. Purtroppo, le cose sono ancora più difficili di quanto sembri, perché è possibile che ad una cella facciano riferimento diversi 'riferimenti utili': cancellarne uno non vuol dire che la cella non serve più. Esistono dei programmi piuttosto complessi, che, ogni tanto, verificano se ci sono celle a cui nessuno punta e che quindi possono essere 'riciclate' (questi programmi si chiamano garbage collectors, letteralmente 'raccoglitori di immondizia', v. §1.9).






Privacy




});

Articolo informazione


Hits: 2776
Apprezzato: scheda appunto

Commentare questo articolo:

Non sei registrato
Devi essere registrato per commentare

ISCRIVITI



Copiare il codice

nella pagina web del tuo sito.


Copyright InfTub.com 2024