Program. Mod B - Cap. 12 - prof.
Burattini
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.
Program. Mod B - Cap. 12 - prof.
Burattini
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
Program. Mod B - Cap. 12 - prof.
3
top = -1;
Burattini
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
Program. Mod B - Cap. 12 - prof.
4
stati immessi.
Burattini
Le dichiarazioni dei metodi sono riportate di seguito.
#include<iostream>
using namespace std;
const int Max=10;
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];
Program. Mod B - Cap. 12 - prof.
Burattini
};
5
Data la non eccessiva lunghezza della definizione della classe
pila abbiamo ritenuto utile non spezzarla in due file, per cui
utilizzeremo un solo file pilaMat.cpp in cui sono incluse sia
le definizioni che le implementazioni dei vari metodi.
Program. Mod B - Cap. 12 - prof.
Burattini
6
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 Program.
tutti gli
elementi della pila a partire da7 top
Mod B - Cap. 12 - prof.
decrescendo fino all’indice 0. Burattini
// COSTRUZIONE E GESTIONE DI UNA PILA
CON UN VETTORE E LISTE - pileMat.h
#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];
};
// -------------------------- DEFINIZIONI
void pila::push(int e) {
if (!piena()) {
top++;
items[top]=e; }
else
cout<<"Pila piena"<<endl;
}
void pila::pop(int& e) {
if(!vuota()) {
e=items[top];
top--; }
else
cout<<"Errore la pila è vuota"<<endl;
}
void pila::cima() {
if(!vuota())
cout<<"elemento in cima = "<<items[top]<<e
else
cout<<"Non ci sono elementi nella pila "<<en
}
ostream& operator<< (ostream& os, pila p)
bool pila::vuota() {
{ os<<"(";
return (top==-1);
for(int i=p.top; i>=0; i--)
}
os<<p.items[i]<<" ";
bool pila::piena() {
os<<")"<<endl;
return os;
Program. Mod B - Cap. 12return
- prof. (top==Max-1);
8
Burattini
}
}
#include<iostream>
//#include"pileMat.h"
{
case 1:
cout<<endl<<"Dammi il valore dell'elemento da
using namespace std;
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;
A.push(e);
cout<<"1) Inserisci elemento nella pila"<<endl;
cout<<endl<<"Dammi il valore dell'elemento
cout<<"2) Preleva elemento dalla pila"<<endl;
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;
cout<<"6) Visualizza elenco della pila"<<endl; break;
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;
pile
Program. Mod B - Cap. 12 - prof.
Burattini
9
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
Program. Mod B - Cap. 12 - prof.
Burattini
10
// COSTRUZIONE E GESTIONE DI UNA CODA UTILIZZANDO PILE
#include<iostream>
# include"pileMat.h "
using namespace std;
void creaCoda1(pila &,pila &);
//
MAIN
int main() {
pila A,B;
int e, scelta;
do {
cout<<"\n
MENU PILA "<<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 in testa alla coda"<<endl;
cout<<"6) Visualizza elenco della coda"<<endl;
cout<<"0) ESCI"<<endl;
cout<<"\n Inserisci scelta : ";
cin>>scelta;
switch(scelta)
{
Program. Mod B - Cap. 12 - prof.
Burattini
11
case 1:
creaCoda1(A,B);
// DEFINIZIONI
cout<<"\n PILA "<<endl;
cout<<A<<endl;
void creaCoda1(pila &Ax,pila &Bx)
cout<<"\n CODA "<<endl;
{ int elem,ex;pila q;
cout<<B<<endl;
while (!Bx.vuota())
break;
{ Bx.pop(elem);
case 2:
Ax.push(elem);}
if(!B.vuota()) {
cout<<endl<<"Dammi il valore dell'elemento da inserire:
B.pop(e);
(0 per finire) ";
cout<<"\n L'elemento prelevato dalla testacin>>elem;
della coda e' : "<<e<<endl;}
else cout<<"\n\n LA CODA e' VUOTA \a\n\n";
while (elem!=0)
break;
{ Ax.push(elem);
case 3:
cout<<endl<<"Dammi il valore dell'elemento da inserire
if(B.vuota()) cout<<"\n\a La coda e' vuota !!\n";
(0 per finire) ";
else cout<<"\n La coda non e' vuota !\n"; cin>>elem;}
break;
while (!Ax.vuota())
case 4:
{ Ax.pop(elem);
if(B.piena()) cout<<"\n la coda e' piena !!"; Bx.push(elem);
else cout<<"\n La coda non e' piena !";
}
break;
}
case 5:
B.cima();
break;
case 6:
cout<<B;
Program. Mod B - Cap. 12 - prof.
12
break; }
Burattini
} while(scelta); return 0; }
Una versione ricorsiva per creare una pila e una coda contemporaneamente.
void crea_pila_coda(pila &Ax, pila &Bx, int elex)
{
cout<<endl<<"Dammi il valore dell'elemento da inserire: (0 per finire) ";
cin>>elex;
{ if (elex!=0)
{ Ax.push(elex);
leggidati(Ax,Bx, elex);
}
}
{
if (elex!=0)
Bx.push(ela);
}
}
Program. Mod B - Cap. 12 - prof.
Burattini
13
Come costruire un riconoscitore di sequenze palindrome usando
le pile
bool palindroma(pila &A,pila &B)
{int elemA,elemB;
bool flag=true;
while( (!A.vuota())&&(!B.vuota()))
{ A.pop(elemA);
B.pop(elemB);
if (elemA!=elemB)
flag=false;
}
return flag;
pila_coda
}
Program. Mod B - Cap. 12 - prof.
Burattini
14
Program. Mod B - Cap. 12 - prof.
Burattini
15
Una versione ricorsiva per la creazione di pila e coda contemporaneamente
void crea_pila_coda(pila &Ax, pila &Bx, int elex)
{ cout<<endl<<"Dammi il valore dell'elemento da inserire: (0 per finire) ";
cin>>elex;
{ if (elex!=0)
{ Ax.push(elex);
crea_pila_coda (Ax,Bx, elex);
}
}
{if (elex!=0)
Bx.push(elex);
}
}
Program. Mod B - Cap. 12 - prof.
Burattini
16
Assegnate due sequenze di caratteri, utilizzando i metodi della classe
pila sotto indicati, scrivere una funzione booleana che verifichi, se le
due sequenze sono una l’inversa dell’altra.
class Pila {
Pila()
push(char e)
pop(char & e)
int lung()
bool piena()
bool vuota()
}
//costruttore, inizializza a lista vuota
//inserisce il carattere e in testa alla pila
//elimina il carattere e dalla testa della pila
// fornisce la lunghezza della lista
Es.
1a sequenza – ROMA
2a sequienza - AMOR
Program. Mod B - Cap. 12 - prof.
Burattini
17
//MAIN
{
pila P1,P2,P3;
char e;
crea_pila(P1)
crea_pila_coda(P2,P3);
cout<<“ Le due sequenze “;
if (!inversa(P1,P3))
cout<<“ non “;
cout<< sono l’una l’inversa dell’altra”<<endl;
}
void crea_pila(Pila &P)
{cout<<endl<<"Dammi elemento ";
cin>>e;
while (e!=0){
if (A.piena()) {
cout<<"\n\a La pila e' piena;
e=0;}
else {
P.push(e);
cout<<endl<<"Dammi elemento) ";
cin>>e; }
}
bool inversa(Pila Pa, Pila Pb)
{ if (Pa.vuota)
void crea_pila_coda(pila &Ax, pila &Bx, char elex)
return true;
{ cout<<endl<<"Dammi elemento ";
else
cin>>elex;
Pa.pop(Ea);
if (elex!=0)
Pb.pop(Eb);
{ Ax.push(elex);
if (Ea!=Eb) || ((Pa.lung()==Pb.lung)
crea_pila_coda (Ax,Bx, elex); }
return false;
{ if (elex!=0)
else
Bx.push(elex); }
return inversa(Pa, Pb);
Program. Mod B - Cap. 12 - prof.
18
}
Burattini
}
Sia data una lista circolare L 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.
L
k
Le function disponibili sono:
9
8
9
3
8
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.
…………..}
5
7
5
k
9
8
3
5
7
Program. Mod B - Cap. 12 - prof.
Burattini
19
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.
L
// MAIN
La lista L e k sono già noti
{ int i=k+1;
eleK=L.estrai(k);
while (L.estrai(i)!=elek)
{if (L.estrai(i)== L.estrai(i+1)
L.cancella(i);
else
i++;
}
}
Program. Mod B - Cap. 12 - prof.
Burattini
k
9
8
9
3
8
5
7
5
k
9
8
3
5
7
20
/* Dato un albero BST contare quanti nodi ci sono al di sotto di un
nodo preassegnato con chiave multipla di un preassegnato K.*/
Tnodo TrovaDatoT(int d, Tnodo A) {
if (A==NULL)
return NULL;
else if (d==A->key)
return A;
else
if ( A->key > d)
return TrovaDatoT(d,A->left);
else
return TrovaDatoT(d,A->right);
}
alberi eser 1
int conta(Tnodo N, int k)
{ int h=0;
if (N==NULL)
return 0;
else
if (N->key%k==0)
{cout<<N->key<<" ";h=1;}
Program.
Modh+conta(N->left,k)+conta(N->right,k);
B - Cap. 12 - prof.
21
return
Burattini
}
/* Dato un albero BST contare quanti fratelli hanno la somma
delle chiavi dispari.*/
alberi eser 2
int conta(Tnodo N)
{ if (N==NULL)
return 0;
else
if ((N->left!=NULL)&&(N->right!=NULL))
{ if ((N->left->key+N->right->key)%2==1)
{cout<<N->left->key<<" "<<N->right->key<<endl;
return 1+conta(N->left)+conta(N->right);}
else
return conta(N->left)+conta(N->right);
}
else
return conta(N->left)+conta(N->right);
Program. Mod B - Cap. 12 - prof.
}
Burattini
22
Si hanno a disposizione le seguenti funzioni membro:
class lista {
lista()
int lung()
int estrai(int n)
// costruttore, inizializza a lista vuota.
// fornisce la lunghezza della lista.
// 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 m,int i) // se L =(c1,..,ci,.., cn) L diventa (c1,..ci,m,.., cn)
int pos(int m)
// pos = k se ck è il primo elemento di L uguale a m
altrimenti pos = 0.
}
Utilizzando tali funzioni trasformare una lista L disordinata e contenente
ripetizioni nella lista ordinata senza ripetizioni che contiene soltanto gli
elementi di L che si ripetono esattamente k volte.
2A
Program. Mod B - Cap. 12 - prof.
Burattini
23
Date due liste L1 e L2 di interi non ordinate, costruire una lista L3
ordinata senza ripetizioni e senza i nodi con chiave multipla di un
prefissato K.
listeSortNoRip
Trovare l’errore
Program. Mod B - Cap. 12 - prof.
Burattini
24
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}
3A
Program. Mod B - Cap. 12 - prof.
Burattini
25
Data la lista astratta L1 contenente interi relativi, scrivere un algoritmo che
pone i numeri negativi di L1 nella lista Lneg in ordine decrescente e i numeri
positivi o nulli nella lista Lpos in ordine crescente.
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 altrimenti
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.
…………..}
Program. Mod B - Cap. 12 - prof.
Burattini
A4
26
Sia data una lista con nodi del tipo
struct Lnodo {
int info;
Lnodo *prec;
};
Scrivere una procedura che elimini i nodi a partire dalla coda.
Program. Mod B - Cap. 12 - prof.
Burattini
27
Scrivere una procedura che, utilizzando le function per le code
mostrate a lezione trasformi una preassegnata coda in una pila.
Program. Mod B - Cap. 12 - prof.
Burattini
28
Program. Mod B - Cap. 12 - prof.
Burattini
29