1
Il nostro esempio guida:
La costruzione di uno stack
2
Costruiamo uno stack
stackapplet.html
3
#include <iostream.h>
#include <cassert>
#define DEBUG
contenuto
struct Pila {
size
int size;
int defaultGrowthSize;
int marker;
marker
int * contenuto;
} ;
16
5
12
2
4
Pila * crea(int initialSize) {
//crea una Pila
cout<<"entro in crea"<<endl;
Pila * s= new Pila ;
s->size=initialSize;
s->defaultGrowthSize=initialSize;
s->marker=0;
s-> contenuto=new int[initialSize];
return s;
}
5
void distruggi(Pila * s) {
//distruggi lo Pila
cout<<"entro in destroy"<<endl;
delete [](s->contenuto);
delete s;
}
6
void cresci(Pila *s, int increment){
//aumenta la dimensione dello Pila
cout<<"entro in cresci"<<endl;
s->size+=increment;
int * temp=new int[s->size];
for (int k=0; k<s->marker;k++) {
temp[k]=s->contenuto[k];
}
delete [](s->contenuto);
s->contenuto=temp;
}
7
void inserisci(Pila *s, int k) {
//inserisci un nuovo valore
cout<<"entro in inserisci"<<endl;
if (s->size==s->marker)
cresci(s,s->defaultGrowthSize);
s->contenuto[s->marker]=k;
s->marker++;
}
8
int estrai(Pila *s) {
//estrai l’ultimo valore
cout<<"entro in estrai"<<endl;
assert(s->marker>0);
return s->contenuto[--(s->marker)];
}
9
void stampaStato(Pila *s) {
//stampa lo stato dello Pila
cout <<"=================="<< endl;
cout << "size = "<<s->size<<endl;
cout << "defaultGrowthSize = “
<<s->defaultGrowthSize<<endl;
cout << "marker = "<<s->marker <<endl;
for (int k=0;k<s->marker;k++)
cout << "["<<(s->contenuto[k])<<"]";
cout << endl;
cout <<"=================="<< endl;
}
10
Pila * copia(Pila * from) {
cout<<"entro in copia"<<endl;
Pila * to=crea(from->size);
to->defaultGrowthSize=from->defaultGrowthSize;
for (int k=0; k<from->marker;k++) {
to->contenuto[k]=from->contenuto[k];
}
to->marker=from->marker;
return to;
}
11
int main() {
Pila * s=crea(5);
cout<<"s";stampaStato(s);
for (int k=1; k<10;k++) inserisci(s,k);
cout<<"s"; stampaStato(s);
Pila * w = copia(s);
cout<<"w"; stampaStato(w);
for (int k=1; k<8;k++)
cout<<estrai(s)<<endl;
cout<<"s"; stampaStato(s);
distruggi(s);
cout<<"s"; stampaStato(s);
for (int k=1; k<15;k++)
cout<<estrai(w)<<endl;
cout<<"w";stampaStato(w);
}
12
bash-2.02$ gcc Pila.cc -lstdc++ -o Pila.exe
bash-2.02$ Pila.exe
entro in crea
s==================
size = 5
defaultGrowthSize = 5
marker = 0
==================
entro in inserisci
entro in inserisci
entro in inserisci
entro in inserisci
entro in inserisci
entro in inserisci
entro in cresci
entro in inserisci
entro in inserisci
entro in inserisci
s==================
size = 10
defaultGrowthSize = 5
marker = 9
[1][2][3][4][5][6][7][8][9]
==================
entro in copia
w==================
size = 10
defaultGrowthSize = 10
marker = 9
[1][2][3][4][5][6][7][8][9]
==================
13
entro in estrai
9
entro in estrai
8
…
entro in estrai
4
entro in estrai
3
s==================
size = 10
defaultGrowthSize = 5
marker = 2
[1][2]
==================
entro in distruggi
s==================
size = 1627775824
defaultGrowthSize = 1627775824
marker = 2
[1627775848][1627775848]
==================
entro in estrai
9
entro in estrai
8
…
entro in estrai
2
entro in estrai
1
entro in estrai
assertion "s->marker>0" failed: file "Pila.cc", line 72
bash-2.02$
14
#include <Pila.h>
Perchè abbiamo scritto
int main() {
il metodo copia?
Pila * s=crea(5);
cout<<"s"; stampaStato(s);
for (int k=1; k<10;k++) inserisci(s,k);
cout<<"s"; stampaStato(s);
Pila * w=s;
cout<<"w"; stampaStato(w);
for (int k=1; k<8;k++)
cout<< estrai(s)<<endl;
cout<<"s"; stampaStato(s);
cout<<“w"; stampaStato(w);
}
Una copia
(troppo)
sbrigativa…
15
s==================
size = 10
defaultGrowthSize = 5
marker = 9
[1][2] [3][4] [5] [6] [7] [8] [9]
==================
w==================
size = 10
defaultGrowthSize = 5
marker = 9
[1][2] [3][4] [5] [6] [7] [8] [9]
==================
entro in estrai
9
entro in estrai
8
…
…
entro in estrai
4
entro in estrai
3
s==================
size = 10
defaultGrowthSize = 5
marker = 2
[1][2]
==================
w==================
size = 10
defaultGrowthSize = 5
marker = 2
[1][2]
==================
16
Pila.h
struct Pila {
int size;
int defaultGrowthSize;
int marker;
int * contenuto;
} ;
Pila * crea(int initialSize) ;
void distruggi(Pila * s) ;
Pila * copia(Pila * from) ;
void cresci(Pila *s, int increment);
void inserisci(Pila *s, int k) ;
int estrai(Pila *s) ;
void stampaStato(Pila *s) ;
17
Pila.h
versione 2
struct Pila {
int size;
int defaultGrowthSize;
int marker;
int * contenuto;
int estrai() ;
} ;
Pila * crea(int initialSize) ;
void distruggi(Pila * s) ;
Pila * copia(Pila * from) ;
void cresci(Pila *s, int increment);
void inserisci(Pila *s, int k) ;
// int estrai(Pila *s) ; vecchia versione
void stampaStato(Pila *s) ;
18
int estrai(Pila *s) {
//estrai l’ultimo valore
cout<<"entro in estrai"<<endl;
assert(s->marker>0);
return s->contenuto[--(s->marker)];
}
Re-implementazione
di estrai
int estrai() {
//estrai l’ultimo valore
cout<<"entro in estrai"<<endl;
assert(this->marker>0);
return this-> contenuto[--(this-> marker)];
}
19
Re-implementazione
del main
int main() {
Pila * s=crea(5);
cout<<"s";stampaStato(s);
for (int k=1; k<10;k++) inserisci(s,k);
cout<<"s"; stampaStato(s);
Pila * w = copia(s);
cout<<"w"; stampaStato(w);
for (int k=1; k<8;k++)
//cout<<estrai(s)<<endl;
cout<<s->estrai()<<endl;
…
}
20
Re-implementazione
di estrai: dove scrivo il codice?
struct Pila {
int size;
int defaultGrowthSize;
int marker;
int * contenuto;
int estrai() {
//estrai l’ultimo valore
cout<<"entro in estrai"<<endl;
assert(this->marker>0);
return this->contenuto[--(this->marker)];
}
};
21
Re-implementazione
di estrai: dove scrivo il codice?
struct Pila {
int size;
int defaultGrowthSize;
int marker;
int * contenuto;
int estrai();
};
int Pila::estrai() {
//estrai l’ultimo valore
cout<<"entro in estrai"<<endl;
assert(this->marker>0);
return this->contenuto[--(this->marker)];
}
22
int estrai(Pila *s) {
//estrai l’ultimo valore
cout<<"entro in estrai"<<endl;
assert(s->marker>0);
return s->contenuto[--(s->marker)];
}
Re-implementazione
di estrai con this
implicito
int estrai() {
//estrai l’ultimo valore
cout<<"entro in estrai"<<endl;
assert(marker>0);
return contenuto[--(marker)];
}
23
Pila * crea(int initialSize) {
Pila * s= new Pila ;
s->size=initialSize;
Re-implementazione
s->defaultGrowthSize=initialSize;
s->marker=0;
di crea
s-> contenuto=new int[initialSize];
return s;
}
Pila::Pila(int initialSize) {
size=initialSize;
defaultGrowthSize=initialSize;
marker=0;
contenuto=new int[initialSize];
}
“Il costruttore”
24
void Pila:: distruggi () {
//distruggi lo Pila
cout<<"entro in distruggi"<<endl;
Re-implementazione
delete []contenuto;
delete this;
di distruggi
}
Pila::~Pila() {
//distruggi lo Pila
cout<<"entro nel distruttore"<<endl;
delete []contenuto;
// NO! delete this;
}
“Il distruttore”
25
Re-implementazione
del main
int main() {
Pila * s=new Pila(5); // OLD: =crea(5)
cout<<"s";s->stampaStato();
for (int k=1; k<10;k++) s->inserisci(k);
cout<<"s"; s->stampaStato();
Pila * w = s->copia();
cout<<"w"; w->stampaStato();
for (int k=1; k<8;k++)
cout<< s->estrai()<<endl;
cout<<"s"; s->stampaStato();
delete s; // OLD: s->distruggi();
cout<<"s"; s->stampaStato();
for (int k=1; k<15;k++)
cout<< w->estrai()<<endl;
cout<<"w"; w->stampaStato();
}
26
Pila.h
versione 3
struct Pila {
int size;
int defaultGrowthSize;
int marker;
int * contenuto;
Pila(int initialSize) ;
~Pila() ;
Pila * copia() ;
void cresci(int increment);
void inserisci(int k) ;
int estrai() ;
void stampaStato() ;
} ;
Variabili di istanza,
Dati membro
Metodi,
Funzioni membro
27
struct Pila {
Pila(int initialSize) ;
Pila();
~Pila() ;
void copia(Pila * to) ;
void inserisci(int k) ;
int estrai() ;
void stampaStato() ;
private:
int size;
int defaultGrowthSize;
int marker;
int * contenuto;
void cresci(int increment);
};
Pila.h
versione 4
28
Pila.h
versione 5
class Pila {
int size;
int defaultGrowthSize;
int marker;
int * contenuto;
void cresci(int increment);
public:
Pila(int initialSize) ;
Pila();
~Pila() ;
void copy(Pila * to) ;
void inserisci(int k) ;
int estrai() ;
void stampaStato() ;
};
29
Pila.h versione 6
struct Pila {
class Pila {
private:
private:
int size;
int size;
int defaultGrowthSize;
int defaultGrowthSize;
int marker;
int marker;
int * contenuto;
int * contenuto;
void cresci(int increment);
void cresci(int increment);
public:
public:
Pila(int initialSize) ;
Pila(int initialSize) ;
Pila();
Pila();
~Pila() ;
~Pila() ;
void copy(Pila * to) ;
void copy(Pila * to) ;
void inserisci(int k) ;
void inserisci(int k) ;
int estrai() ;
int estrai() ;
void stampaStato() ;
void stampaStato() ;
};
};
La Pila in Java - 1
package strutture;
public class Pila {
int size;
int defaultGrowthSize;
int marker;
int contenuto[];
final int initialSize=3;
Pila() {
size=initialSize;
defaultGrowthSize=initialSize;
marker=0;
contenuto=new int[size];
}
La Pila in Java - 1
package strutture;
public class Pila {
int size;
int defaultGrowthSize;
costante
int marker;
int contenuto[];
final int initialSize=3;
Pila() {
size=initialSize;
defaultGrowthSize=initialSize;
marker=0;
contenuto=new int[size];
}
La Pila in Java - 2
private void cresci(int dim){
size+=defaultGrowthSize;
int temp[ ]=new int[size];
for (int k=0;k<marker;k++)
temp[k]=contenuto[k];
contenuto=temp;
}
La Pila in Java - 3
void inserisci(int k) {
if (marker==size){
cresci(defaultGrowthSize;)}
contenuto[marker]=k;
marker++;
}
int estrai() {
if (marker==0) {
System.out.println(
"Non posso estrarre da una pila vuota");
System.exit(1);
}
return contenuto[--marker];
}
La Pila in Java - 4
public static void main(String args[]) {
int dim=10;
Pila s=new Pila();
for (int k=0;k<2*dim;k++)
s.inserisci(k);
for (int k=0;k<3*dim;k++)
System.out.println(s.estrai());
}
}
Using assertions (da Java 1.4)
int estrai() {
assert(marker>0):"Invalid marker";
return contenuto[--marker];
}
Compilare con:
java –ea Pila.java
java.lang.AssertionError: Invalid marker
at pila.Pila.estrai(Pila.java:22)
at pila.Pila.main(Pila.java:39)
Using System.arrayCopy()
System.arraycopy(
Object src, int src_position,
Object dst, int dst_position, int length
);
Copies the specified source array, beginning at the
specified position, to the specified position of the
destination array.
La Pila in Java - 2
private void cresci(int dim){
size+=defaultGrowthSize;
int temp[ ]=new int[size];
System.arraycopy(
contenuto, 0,
temp, 0, marker-1);
contenuto=temp;
}
Tipi di dato derivati (reference data)
Java,
come tutti i linguaggi OO, permette di definire
NUOVI TIPI DI DATO (classi).
Alcuni
tipo
tipi di dato (classi) sono predefinite:
ad esempio le stringhe. (String)
Operatore
identificatore
costruttore
di creazione
Point
punto = new Point(10,10);
No
Structures or Unions
Java does not support C struct or union types. Note, however, that a class
is essentially the same thing as a struct, but with more features. And you
can simulate the important features of a union by subclassing.
“Java non ha i puntatori”
Ma è vero?
Point punto = new Point(10,10);
l’identificatore di un oggetto (“punto”)
sembra proprio un puntatore!
Quel che Java non ha è
l’aritmetica dei puntatori
.
Confronto dell’operatore new
in C++:
in Java:
Point * punto = new Point(10,10);
Point
punto.x di Java
punto = new Point(10,10);
equivale a
punto->x del C++
In Java gli oggetti sono accessibili
SOLO per referenza
.
memory management
La gestione (dinamica) della memoria e’ automatica, tramite
la creazione (operatore new ) e
la distruzione (garbage collection) di oggetti.
GC interviene quando serve memoria.
GC elimina gli oggetti per i quali non vi sono piu’ riferimenti attivi.
GC puo’ essere attivato su richiesta esplicita:
System.gc()
memory management - costruttori
Operazioni da eseguirsi alla nascita di un oggetto vanno definite nel
metodo “costruttore”.
Ogni classe deve avere uno (o più) costruttori.
I costruttori possono differire per numero e tipo di parametri.
Es.:
Pila() {
size=100; …
}
Pila(int size) {
this.size=size
}
memory management - distruttori
Operazioni da associarsi con l’eliminazione di un oggetto possono
essere definite nel metodo “distruttore” finalize() (opzionale)
NOTA: il metodo finalize POTREBBE NON ESSERE CHIAMATO DAL
SISTEMA (es. se il programma finisce prima…)
Per essere certi che vengano chiamati i metodi finalize, occorre
chiamare la
System.runFinalization() subito DOPO la System.gc()
System agisce come libreria
System.out.println(…);
System.gc();
System.runFinalization();
System.exit(int status);
System.arraycopy(Object src, int srcPos, Object dest, int destPos, int
length);
long System. currentTimeMillis();
Class String
Class String
Class String
Class String
Class String
String
Per trasformare il contenuto di una stringa in un intero:
int Integer.parseInt(String s)
Per trasformare il contenuto di una stringa in un float:
float Float.parseFloat(String s)
51
Esercizio:
Costruite una Coda analoga alla Pila