1
ESEMPIO DI UNA CLASSE PILA
Ricordiamo che:
La pila o stack è una struttura astratta composta da più elementi
omogenei.
Una pila è uno stack di dati con accessi del tipo LIFO (Last In First
Out) per cui l’ultimo elemento inserito nello pila è anche il primo
elemento che si può estrarre da esso.
L’aggiunta di un elemento alla pila viene detta operazione di push,
mentre la rimozione dallo pila viene detta operazione di pop.
Vogliamo implementare una classe astratta chiamata pila i cui
elementi sono numeri interi e la cui struttura è quella di un vettore.
2
Aggiungiamo alla struttura descritta un intero che indichi la
posizione attuale dell’elemento da rimuovere.
Indichiamo con items il vettore che contiene i componenti della pila
(supposta omogenea), con top l’indice dell’elemento attuale, con
push l’operazione di aggiungere oggetti e con pop quella di
eliminarli.
Prima di analizzare l’oggetto pila, osserviamo che dobbiamo
necessariamente determinare il numero massimo di elementi che
possiamo gestire: indichiamo con Max tale valore che rappresenterà
una costante globale (ad esempio Max=100).
I data-member della pila sono
int top;
int items[Max];
rigorosamente privati, mentre il costruttore dovrà inizialmente
indicare che la pila è vuota ponendo
3
top = -1;
In questo caso non è necessario un distruttore.
Per usufruire della classe pila abbiamo la necessità di implementare i
seguenti metodi:
push che inserisce un oggetto della pila in cima;
pop che elimina l’elemento dalla cima;
cima che ne stampi semplicemente il valore senza eliminarlo;
vuota, funzione booleana che restituisca true se la pila è vuota, false
altrimenti;
piena, funzione booleana che restituisca true se la pila è piena, false
altrimenti;
stampa, mostra a video tutti gli elementi nello stesso ordine in cui sono
4
stati immessi.
#include<iostream>
using namespace std;
const int Max=10;
//
CLASSE
class pila {
public:
pila() { top=-1; }
void push(int e);
void pop(int &e);
void cima();
bool vuota();
bool piena();
friend ostream& operator<< (ostream&, pila);
private:
int top;
int items[Max];
};
5
push : se la pila non è piena allora, per inserire l’elemento e in cima,
s’incrementa di una unità la variabile top e si pone items[top]e; se
la pila è piena si scrive “Pila piena”;
pop : se la pila non è vuota allora, per eliminare l’elemento dalla
cima, si restituisce prima l’elemento e posto in cima e poi si
decrementa la variabile top di una unità;
cima : se la pila non è vuota, stampa il valore items[top] senza
eliminarlo;
vuota : restituisce il valore booleano del confronto top==-1;
piena: restituisce il valore booleano del confronto top==Max-1;
overload di <<: stampa tutti gli elementi della pila a partire da top
6
decrescendo fino all’indice 0.
void pila::push(int e) {// ----- DEFINIZIONI METODI
// COSTRUZIONE E GESTIONE DI UNA PILAif (!piena()) {
CON UN VETTORE
top++;
items[top]=e; }
#include<iostream>
else
cout<<"Pila piena"<<endl;
}
using namespace std;
void pila::pop(int& e) {
if(!vuota()) {
const int Max=5;
e=items[top];
//
CLASSE
top--; }
class pila {
else
public:
cout<<"Errore la pila è vuota"<<endl; }
pila() { top=-1; }
void pila::cima() {
void push(int e);
if(!vuota())
void pop(int &e);
cout<<"elemento in cima = "<<items[top]<<endl;
void cima();
else
bool vuota();
cout<<"Non ci sono elementi nella pila "<<endl; }
bool piena();
bool pila::vuota() {
friend ostream& operator<< (ostream&, pila); return (top==-1);
}
private:
bool pila::piena() {
int top;
return (top==Max-1);
}
int items[Max];
ostream& operator<< (ostream& os, pila p) {
};
os<<"(";
for(int i=p.top; i>=0; i--)
os<<p.items[i]<<" ";
os<<")"<<endl;
7
return os; }
#include<iostream>
#include"pileMat.h"
// #include"pileS.h"
using namespace std;
{
case 1:
cout<<endl<<"Dammi il valore dell'elemento da
inserire nella pila: (0 per finire) ";
cin>>e;
//
MAIN
while (e!=0){
int main() {
if (A.piena()) {
pila A;
cout<<"\n\a La pila e' piena !!\n";
int e, scelta=-1;
e=0;}
do {
else {
cout<<"\n
MENU PILA "<<endl;
cout<<"1) Inserisci elemento nella pila"<<endl;A.push(e);
cout<<"2) Preleva elemento dalla pila"<<endl; cout<<endl<<"Dammi il valore dell'elemento
da inserire nella pila: (0 per finire) ";
cout<<"3) Verifica pila vuota"<<endl;
cin>>e; }
cout<<"4) Verifica pila piena"<<endl;
}
cout<<"5) Visualizza elemento della pila"<<endl;
break;
cout<<"6) Visualizza elenco della pila"<<endl;
case 2:
cout<<"0) ESCI"<<endl;
if(!A.vuota()) {
cout<<"\n Inserisci scelta : ";
A.pop(e);
cin>>scelta;
cout<<"\n L'elemento prelevato dalla testa
switch(scelta){
alla pila e' : "<<e<<endl;
}
else cout<<"\n\n LA PILA e' VUOTA \a\n\n";
break;
8
#include<iostream>
//#include"pileMat.h"
#include"pileS.h"
using namespace std;
case 3:
if (A.vuota()) cout<<"\n\a La pila e' vuota !!\n";
else cout<<"\n La pila non e' vuota !\n";
break;
//
MAIN
case 4:
int main() {
if(A.piena()) cout<<"\n la pila e' piena !!";
pila A;
else cout<<"\n La pila non e' piena !";
int e, scelta=-1;
break;
do {
cout<<"\n
MENU PILA "<<endl;
case 5:
cout<<"1) Inserisci elemento nella pila"<<endl;
A.cima();
cout<<"2) Preleva elemento dalla pila"<<endl;
break;
cout<<"3) Verifica pila vuota"<<endl;
cout<<"4) Verifica pila piena"<<endl;
case 6:
cout<<"5) Visualizza elemento della pila"<<endl;
cout<<A;
cout<<"6) Visualizza elenco della pila"<<endl;
break;
cout<<"0) ESCI"<<endl;
cout<<"\n Inserisci scelta : ";
case 0:
cin>>scelta;
scelta =0;
switch(scelta)
break;
{
default:
cout<<"\n\a Inserisci un numero tra 0 e 6 \n";
}
9
} while(scelta);
return 0;
ESERCIZIO
Assegnata la classe Pila avente la seguente descrizione
class pila {
public:
pila() { top=-1; }
void push(int e);
void pop(int &e);
void cima();
bool vuota();
bool piena();
friend ostream& operator<< (ostream&, pila);
private:
int top;
int items[Max];
};
Scrivere un algoritmo che gestisca i dati introdotti nella pila
con la strategia FIFO invece che LIFO
10
Le Code
• Una coda è una successione lineare di elementi,
eventualmente anche vuota
• Se gli elementi che compongono una coda sono tutti dello
stesso tipo la coda è detta omogenea.
• Le operazioni elementari che possono esser effettuate su di
esse sono: aggiungere un elemento, cancellare e/o estrarre
un elemento.
111
LE CODE (coda)
testa
testa
coda
12
LE CODE
Le operazioni fondamentali che si fanno sulle code sono:
riempimento e svuotamento.
Questo implica che durante lo svolgimento del programma il
numero di oggetti in coda può cambiare.
Dynamic data type: il numero di componenti nel Data Type
cambia nel corso del programma.
Dobbiamo descrivere una coda in funzione della sua testa , della
sua coda , degli oggetti in coda e del loro numero in ogni istante
della computazione.
13
OPERAZIONI SULLE CODE
In una coda l’elemento inserito per primo viene anche estratto per
primo (FIFO).
In una coda, se si adopera una struttura ad array, occorrerà distinguere
tra un inizio o TESTA della coda (punto di estrazione e/o
cancellazione di un elemento) ed una fine o CODA della coda (punto
di inserimento di un nuovo elemento).
Aggiungere ed eliminare oggetti.
Se Items[ ] è un array in cui si collocano gli oggetti. Testa l’indice
dell’array corrispondente alla testa, Coda l’indice corrispondente
alla coda e Item l’oggetto da aggiungere potremmo usare i
seguenti algoritmi:
14
OPERAZIONI SULLE CODE
AGGIUNGERE
coda  coda+1
Items[coda]  Item
InUse  InUse + 1
ELIMINARE
testa  testa+1
InUse  InUse - 1
SOLUZIONE IMPROPONIBILE !!!!!!!!!!!!
Ogni volta che esce un oggetto bisogna spostare in avanti di un
posto tutti quelli in coda altrimenti lo spazio disponibile si esaurisce
rapidamente pur essendoci posti vuoti.
15
Testa
1
N°=6
2
3
Coda
4
5
6
7
8
9
Escono due oggetti e ne entrano due
N°=6
Testa
1
1
Coda
2
3
4
5
6
Escono due oggetti e ne entrano tre
Coda
Testa
2
3
4
5
6
7
8
9
8
9
N°=7
7
16
Possiamo descrivere una coda in funzione della sua testa, della sua
coda, degli oggetti in coda e del loro numero in ogni istante della
computazione utilizzando l’espressione
coda:=coda % Maxcoda + 1 (elimina elemento)
testa:=testa % Maxcoda + 1
(preleva elemento)
Ovviamente nel caso in cui InUse< Maxcoda possiamo adoperare
entrambe le espressioni per aggiungere e levare, in caso contrario
possiamo solo levare.
17
METODI
coda costruttore - inizializza la coda vuota
push(int &e) se la coda non è piena aggiungi oggetti altrimenti segnala
errore
pop(int &e) se la coda non è vuota elimina il primo oggetto altrimenti
segnala errore
cima() fornisce il valore del primo oggetto in coda, in mancanza segnala
stampa() stampa gli oggetti in coda
vuota() restituisce vero se non ci sono oggetti in coda
piena() restituisce vero se la coda è piena
18
int main() {
coda A;
int e, scelta=-1;
do {
cout<<"\n
MENU coda "<<endl;
cout<<"1) Inserisci elemento nella coda"<<endl;
cout<<"2) Preleva elemento dalla coda"<<endl;
cout<<"3) Verifica coda vuota"<<endl;
cout<<"4) Verifica coda piena"<<endl;
cout<<"5) Visualizza elemento della coda"<<endl;
cout<<"6) Visualizza elenco della coda"<<endl;
cout<<"0) ESCI"<<endl;
cout<<"\n Inserisci scelta : ";
cin>>scelta;
switch(scelta)
19
{
case 1:
cout<<endl<<"Dammi il valore dell'elemento da inserire nella coda: (0 per finire) "; cin>>e;
while (e!=0){
if (A.piena()) {
cout<<"\n\a La coda e' piena !!\n";
e=0;}
else {
A.push(e);
cout<<endl<<"Dammi il valore dell'elemento da inserire nella coda: (0 per finire) “
cin>>e; }
}
break;
case 2:
if(!A.vuota()) {
A.pop(e);
cout<<"\n L'elemento prelevato dalla testa della coda e' : "<<e<<endl;
}
else cout<<"\n\n LA coda e' VUOTA \a\n\n";
break;
20
case 3:
if(A.vuota()) cout<<"\n\a La coda e' vuota !!\n";
else cout<<"\n La coda non e' vuota !\n";
break;
case 4:
if(A.piena()) cout<<"\n la coda e' piena !!";
else cout<<"\n La coda non e' piena !";
break;
case 5:
A.cima();
break;
case 6:
//cout<<A;
A.stampa();
break;
case 0:
scelta =0;
break;
default:
cout<<"\n\a Inserisci un numero tra 0 e 6 \n";
}
} while(scelta);
return 0;
}
21
// COSTRUZIONE E GESTIONE DI UNA CODA
CON UN VETTORE
void coda::pop(int &e) {
#include<iostream>
if (!vuota()) {
using namespace std;
const int Max=4;
//
CLASSE
class coda {
public:
coda() { top=0;queue=0; num=0;}
void push(int &e);
void pop(int &e);
void cima();
bool vuota();
bool piena();
void stampa();
private:
int top;
int queue;
int num;
int items[Max];
};
e=items[top];
num--;
top=top%Max+1;//system("pause");
}
else
cout<<"coda vuota"<<endl;
}
void coda::push(int& e) {
if(!piena()) {
num++;
items[queue]=e;
queue=(queue+1)%Max;
}
else
cout<<"Errore la coda è piena"<<endl;
}
22
void coda::cima() {
if(!vuota())
cout<<"elemento in cima = "<<items[top]<<endl;
else
cout<<"Non ci sono elementi nella coda "<<endl;
}
bool coda::vuota() {
return (num==0);
}
bool coda::piena() {
return (num==Max);
}
void coda::stampa()
{ if(!vuota())
for (int i=top;i<=top+num-1;i++)
{ cout<<items[i%Max]<<" "; }
else
cout<<"Non ci sono elementi nella coda "<<endl;
}
23
Anche una coda può essere realizzata mediante delle liste legate.
In questo caso si ha:
Pnodo Coda;
Pnodo AddCoda(Pnodo &Coda,Pnodo FCoda, int item);
// aggiunge un nodo alla fine della lista Coda;
Pnodo DeleteCoda(Pnodo &Coda, int item);
// elimina un nodo alla testa della lista Coda;
24
ESERCIZIO
Scrivere i prototipi e le definizioni degli operatori:
MakeCoda
AddCoda
DeleteCoda
FirstOnCoda
QCount
QEmpty
QFull
25
ESEMPIO
Dati due oggetti della classe lista (di interi) L1 ed L2,aventi la stessa lunghezza, costruire
una lista L3 in cui nelle posizioni dispari siano presenti i corrispondenti presenti nelle
posizioni dispari di L1, nelle posizioni pari siano presenti i corrispondenti presenti nelle
posizioni pari di L2, a meno che nelle corrispondenti posizioni di L1 e L2 i due numeri
non siano uguali, in tal caso porre 0 in L3 e cancellare da L1 e L2 i due numeri.
(NB In L1 e L2 non appare mai lo zero).
Es.
L1=(3, 1, 7, 15, 21)
L2=(8, 6, 7, 15, 55)
L3=(3, 6, 0, 0, 55)
L1=(3, 1, 21) L2=(8, 6, 55)
Si hanno a disposizione le seguenti funzioni membro:
class lista {
int lung()
// fornisce la lunghezza della lista.
lista()
// costruttore, inizializza a lista vuota.
int estrai(int n)// ritorna il valore dell’elemento di posto n, se esiste, MAX_INT altrimenti
void cancella(int n) //cancella l’elemento di posizione n se esiste.
void inserisci(int n, int k) // Inserisce l’intero k nel posto ennesimo.
}
26
class lista {
int lung()
// fornisce la lunghezza della lista.
lista()
// costruttore, inizializza a lista vuota.
int estrai(int n)// ritorna il valore dell’elemento di posto n, se esiste, MAX_INT altrimenti
void cancella(int n) //cancella l’elemento di posizione n se esiste.
void inserisci(int n, int k) // Inserisce l’intero k nel posto ennesimo.
}
void ListaClass(lista L1,L2,L3);
{int i=1,j=1;
while (i<=L1.lung())
{ if ((L1.estrai(i)!=L2.estrai(i)))
{
if (i%2=1))
{L3.inserisci(j,L1.estrai(i));
i=i+1; j=j+1; }
else
{L3.inserisci(j,L2.estrai(i));
i=i+1; j=j+1; }
}
}
else
{L1.cancella(i);
L2.cancella(i);
L3.inserisci(j,0);
j=j+1
}
}
}
Costruire una lista L3 in
cui nelle posizioni
dispari siano presenti i
corrispondenti presenti
nelle posizioni dispari di
L1, nelle posizioni pari
siano presenti i
corrispondenti presenti
nelle posizioni pari di
L2, a meno che nelle
corrispondenti posizioni
di L1 e L2 i due numeri
non siano uguali, in tal
caso porre 0 in L3 e
cancellare da L1 e L2 i
due numeri.
27
ESERCIZI
Siano assegnate due liste astratte di interi L1 ed L2, non ordinate, per cui sono disponibili
solo le seguenti funzioni-membro:
class Lista {
Lista() //costruttore, inizializza a lista vuota
int estrai(int n) //ritorna il valore dell’elemento di posto n se esiste, MAX_INT altrimenti
int lung() // fornisce la lunghezza della lista
void inserisciOrdinato(int n) //inserisce in ordine crescente l’intero n nella lista
void cancella(int n) // cancella l’elemento posto nella posizione n, se esiste
bool primo(int n) // ritorna vero se n è primo
}
Costruire la lista L3, ordinata in modo crescente, che contenga tutti i numeri pari
appartenenti ad L1 e non appartenenti ad L2 e tutti i numeri primi>2 appartenenti sia ad
L1 che a L2.
Es.
L1= {12,13, 25, 44, 1, 20, 7,6,11}  L3={6,7, 12,13,20 }
L2= {5,6, 15, 17, 2,13, 44, 7}
28
Dati due oggetti della classe lista (di interi) L1 ed L2,aventi la stessa lunghezza, per ogni
coppia di elementi aventi lo stesso indice eliminare il più grande dalla corrispondente lista ed
inserirlo in una lista ordinata L3.
Si hanno a disposizione le seguenti funzioni membro:
class lista {
lista()
// costruttore, inizializza a lista vuota.
int estrai(int n)
// ritorna il valore dell’elemento di posto n, se esiste, MAX_INT altriment
void cancella(int n) //cancella l’elemento di posizione n se esiste.
int lung()
// fornisce la lunghezza della lista.
void inserisci(int n, int k) // Inserisce l’intero k nel posto ennesimo se n è minore o uguale
alla lunghezza della lista più uno.
…………..}
ESEMPIO: L1= (5,14,3,12)  L1=(5,3)
L2=(7,11,5, 1) L2=(11,1) ed L3= (5,7,12,14)
29
Sia data una lista circolare L (v. fig.) i cui elementi, a partire da quello in posizione k
noto sono ordinati in maniera crescente e con ripetizioni, e l’elemento in posizione k
non presenta ripetizioni. A partire da k scrivere una funzione ricorsiva che elimini le
ripetizioni dalla lista e conti quanti sono gli elementi rimasti.
k
Le function disponibili sono:
class lista {
lista()
int estrai(int n)
// costruttore, inizializza a lista vuota.
// ritorna il valore dell’elemento di posto n,
se esiste, MAX_INT altrimenti
void cancella(int n) //cancella l’elemento di posizione n se esiste.
…………..}
9
8
9
3
8
5
7
5
k
9
8
3
5
Es. numero elementi=5
7
30