Buona sera a tutti, oggi nella risoluzione di un esercizio che prevedeva di creare una lista per ogni corrispettivo tipo (In questo caso sono 3 forme: Rettangolo, Cerchio e Triangolo) e poi inserire gli elementi di ogni lista all'interno di un albero sempre del corrispettivo tipo. Dopo di che l'esercizio prevede che, dato un numero in input, venivano eliminate tutti gli oggetti all'interno dell'albero che avessero una area minore a quella data in input. Il mio problema sta appunto in quest'ultimo punto, sono riuscito a implementare l'eliminazione dei nodi dell'albero ma appena provo a fare l'output il programma si blocca.
Questo qui sotto è l'intero codice
#include <iostream>
#include <typeinfo>
using namespace std;
#define PI 3.14
class Shape //Forma, classe astratta
{
public:
Shape() { }
~Shape() { }
virtual std::ostream &input(std::ostream &out) = 0;
virtual double getArea() = 0;
//virtual bool operator < (Shape&) = 0;
};
std::ostream& operator<<(std::ostream& out, Shape &s)
{
return s.input(out);
}
class Rectangle : public Shape
{
private:
int b;
int h;
double area = (double)b*h;
public:
Rectangle(int base,int altezza) : b(base), h(altezza) { }
~Rectangle() { }
//Funzioni get
double getArea() {return area;}
void setArea(double AREA) {this->area = AREA;}
int getBase() {return b;}
int getAltezza() {return h;}
bool operator <(Rectangle& r) {return area < r.area;}
std::ostream &input(std::ostream& out)
{
out << "B: " << b << " H: " << h << " A: " << getArea();
return out;
}
};
class Circle : public Shape
{
private:
int r; //Raggio
double area = (double) r*r *PI;
public:
Circle(int raggio) : r(raggio) { }
~Circle() { }
//Funzioni get
double getArea() {return area;}
int getRaggio() {return r;}
void setArea(double AREA) {this->area = AREA;}
bool operator <(Circle& c) {return getArea() < c.getArea();}
std::ostream &input(std::ostream& out)
{
out << "R: " << r << " A: " << getArea();
return out;
}
};
class Triangle : public Shape //Facciamo riferimento a un Triangolo Isoscele
{
private:
int l; //I due lati uguali del triangolo isoscele
int b; //Base
double area = (double) (l*b)/2;
public:
Triangle(int lato, int base) : l(lato), b(base) { }
~Triangle() {}
//Funzioni get
double getArea() {return area;}
int getLato() {return l;}
void setArea(double AREA) {this->area = AREA;}
bool operator <(Triangle &t) {return getArea() < t.getArea();}
std::ostream &input(std::ostream& out)
{
out << "L: " << l << " B: " << b << " A:" << getArea();
return out;
}
};
template <typename T>
class Nodo
{
public:
T valore;
Nodo* succ;
Nodo(T _valore) : valore(_valore) { }
};
template <typename T>
class Lista
{
private:
Nodo<T>* testa;
public:
Lista() {testa = NULL;}
~Lista();
void inserisci(T val); //!!E' UN INSERIMENTO A CODA
Nodo<T>* getTesta() {return testa;}
template <typename U>
friend
std::ostream& operator<<(std::ostream& out, Lista& l);
};
template <typename U>
std::ostream& operator<<(std::ostream& out, Lista<U>& l)
{
if(l.getTesta() == NULL)
{
out << "Lista vuota.\n";
}
else
{
if(typeid(l) == typeid(Lista<Rectangle>))
out << "-RETTANGOLI-\n";
else if(typeid(l) == typeid(Lista<Circle>))
out << "-CERCHI-\n";
else if(typeid(l) == typeid(Lista<Triangle>))
out << "-TRIANGOLI-\n";
int i = 1;
for(Nodo<U>* aux = l.getTesta(); aux != NULL; aux = aux->succ)
{
out << i << ") "<<aux->valore << std::endl;
i++;
}
}
out << std::endl;
return out;
}
template <typename T>
Lista<T>::~Lista()
{
Nodo<T>* aux1 = testa;
while(aux1 != NULL)
{
Nodo<T>* aux2 = aux1->succ;
delete aux1;
aux1 = aux2;
}
}
template <typename T>
void Lista<T>::inserisci(T val) //!!E' UN INSERIMENTO A CODA
{
Nodo<T>* nuovo = new Nodo<T>(val);
//nuovo->valore = val;
if(testa == NULL)
{
nuovo->succ = testa;
testa = nuovo;
}
else
{
Nodo<T>* aux = testa;
while(aux->succ != NULL)
aux = aux->succ;
aux->succ = nuovo;
nuovo->succ = NULL;
}
}
template <typename T>
class NodoA //Creiamo un Nodo per l'albero
{
public:
T valore;
NodoA* left, *right, *padre;
NodoA(T _val) : valore(_val), left(NULL), right(NULL), padre(NULL) { }
};
template <typename T>
class Albero
{
private:
NodoA<T>* radice;
void trapianta(NodoA<T>* u, NodoA<T>* v); //Trapiantiamo quello puntato da "v" nella posizione di "u"
NodoA<T>* minimo(NodoA<T> *x);
int num_elementi;
//Funzioni overloadate
void cancella(NodoA<T>* z);
void preOrder(NodoA<T>* p) const;
void inOrder (NodoA<T>* p) const;
void postOrder(NodoA<T>* p) const;
NodoA<T>* ricercaRicorsiva(NodoA<T>* x, int valore);
public:
Albero() : radice(NULL), num_elementi(0) { }
void inserisci(T valore);
NodoA<T>* ricercaIterativa(int valore); //Questa funzioen serve per il compito. Ricerca iterativa.
int altezza(NodoA<T>* p) const;
//Funzioni overloadate
bool cancella(int valore);
NodoA<T>* ricercaRicorsiva(int valore) {return ricercaRicorsiva(radice,valore);}
void preOrder() const {preOrder(radice); std::cout << std::endl;}
void inOrder() const {inOrder(radice); std::cout << std::endl;}
void postOrder() const{postOrder(radice); std::cout << std::endl;}
template <typename U>
friend
std::ostream& operator<< (std::ostream& out, const Albero<U>& a);
};
template <typename U>
std::ostream& operator<< (std::ostream& out, const Albero<U>& a)
{
int h = a.altezza(a.radice);
if(typeid(a) == typeid(Albero<Rectangle>))
out << "-RETTANGOLI-\n";
if(typeid(a) == typeid(Albero<Circle>))
out << "-CERCHI-\n";
if(typeid(a) == typeid(Albero<Triangle>))
out << "-TRIANGOLI-\n";
for(int i = 0; i < h; i++)
{
stampaLivello(a.radice, i);
out << std::endl;
}
return out;
}
template <typename T>
void stampaLivello(NodoA<T>* p, int livello)
{
if(p == NULL)
{
std::cout << "_\t";
return;
}
if(livello == 0)
std::cout << p->valore << "\t";
else if(livello > 0)
{
stampaLivello(p->left, livello-1);
stampaLivello(p->right, livello-1);
}
}
template <typename T>
NodoA<T>* Albero<T>::ricercaIterativa(int valore)//Questa funzione serve per il compito. Ricerca iterativa.
{
NodoA<T> *aux = radice;
std::cout << aux << std::endl;
std::cout << "Area attuale: " << aux->valore.getArea() << std::endl;
while((aux != NULL) && (valore != (aux->valore.getArea())))
{
std::cout << " --> " << aux->valore;
if((aux->valore.getArea()) < valore)
return aux;
else
aux = aux->right;
}
return NULL;
}
template <typename T>
int Albero<T>::altezza(NodoA<T>* p) const
{
if(p == NULL)
return 0;
else
{
int leftHeight = altezza(p->left);
int rightHeight = altezza(p->right);
if(leftHeight > rightHeight)
return leftHeight + 1;
else
return rightHeight + 1;
}
}
template <typename T>
void Albero<T>::inserisci(T val)
{
NodoA<T>* nuovo = new NodoA<T>(val);
NodoA<T>* x = radice, *y = NULL; //x variabile ausiliare che va avanti fino a quando non
//trova un posto dove mettere il valore || Mentre y tiene conto del padre di x
nuovo->valore = val;
nuovo->left = NULL;
nuovo->right = NULL;
while(x != NULL)
{
y = x; //Ricordiamo che y tiene traccia del padre di x
if(val < x->valore) //Se il valore inseritovi è < del valore attuale di x->val, viene messo nel sotto albero sinistro
x = x->left;
else //Altrimenti va nel sotto albero destro
x = x->right;
}
nuovo->padre = y;
if(y == NULL) //Nel caso in cui x sia la radice, ovviamente non avrà un padre, quindi y = NULL
radice = nuovo;
else if(val < y->valore)
y->left = nuovo;
else
y->right = nuovo;
num_elementi++;
}
template <typename T>
void Albero<T>::trapianta(NodoA<T>* u, NodoA<T>* v)//Trapiantiamo quello puntato da "v" nella posizione di "u"
{
if(u->padre = NULL) //Ovvero se u è la radice
radice = v;
else if(u == u->padre->left) //Se u è il figlo sinistro del padre
u->padre->left = v;
else //Se u è il figlo destro del padre
u->padre->right = v;
if(v != NULL) //Se v != NULL, aggiorniamo il padre
v->padre = u->padre;
}
template <typename T>
NodoA<T>* Albero<T>::minimo(NodoA<T> *x)
{
NodoA<T>* nMin = x;
while(nMin->left != NULL)
nMin = nMin->left;
return nMin;
}
/*
template <typename T>
NodoA<T>* Albero<T>::ricercaRicorsiva(NodoA<T>* x, int valore)
{
if(x == NULL || x->valore == valore) //Caso base
return x;
if(valore < this->x->valore)
return ricercaRicorsiva(x->left, valore);
else
return ricercaRicorsiva(x->right, valore);
}
*/
template <typename T>
bool Albero<T>::cancella(int valore)
{
NodoA<T>* n = ricercaIterativa(valore);
if(n == NULL)
return false;
cancella(n);
return true;
}
template <typename T>
void Albero<T>::cancella(NodoA<T>* z)
{
//Caso 2: z ha un solo figlio
NodoA<T> *y; //Fungerà da ausiliare per tenere conto del padre di z
if(z->left == NULL)
trapianta(z,z->right);
else if(z->right == NULL)
trapianta(z,z->left);
//Caso 3: z ha entrambi i figli (Destro e Sinitro)
else
{
y = minimo(z->right); //y sarà il successo (destro) di z, può essere o figlio diretto di z, oppure non esserlo
if(y->padre != z) //Ecco il caso in cui il PADRE DI Y != Z (Quindi y non è figlio di z)
{
trapianta(y, y->right);
y->right = z->right;
y->right->padre = y;
}
trapianta(z,y);
y->left = z->left;
y->left->padre = y;
}
delete z;
}
template <typename T>
void Albero<T>::preOrder(NodoA<T>* p) const
{
if(p != NULL)
{
std::cout << p->valore << "\t";
preOrder(p->left);
preOrder(p->right);
}
}
template <typename T>
void Albero<T>::inOrder(NodoA<T>* p) const
{
if(p != NULL)
{
inOrder(p->left);
std::cout << p->valore << "\t";
inOrder(p->right);
}
}
template <typename T>
void Albero<T>::postOrder(NodoA<T>* p) const
{
if(p != NULL)
{
postOrder(p->left);
postOrder(p->right);
std::cout << p->valore << "\t";
}
}
using namespace std;
void creaListe(Lista<Rectangle>& r, Lista<Circle>& c, Lista<Triangle>& t, int n)
{
char scelta;
int b, l, rag; //b e l sono o basi e lati per Rettangolo, oppure base e i due lati cateti per il triangolo isoscele. r è il raggio della circ
for(int i = 0; i < n; i++)
{
cout << "Scrivi una lettera per scegliere la forma \nR - Rettangolo\nC - Cerchio\n T - Triangolo\n"; cin >> scelta;
while(toupper(scelta) != 'C' && toupper(scelta) != 'R' && toupper(scelta) != 'T')
{
cout << "Hai inserito una lettera non valida!" << endl;
cout << "Scrivi una lettera per scegliere la forma \nR - Rettangolo\nC - Cerchio\nT - Triangolo\n"; cin >> scelta;
}
switch(toupper(scelta))
{
case 'R':
cout << "Inserisci la base e il lato separati da uno spazio: "; cin >> b >> l;
r.inserisci({b,l});
break;
case 'C':
cout << "Inserisci il raggio: "; cin >> rag;
c.inserisci({rag});
break;
case 'T':
cout << "Inserisci la base e i lati del triangolo isoscele da uno spazio: "; cin >> b >> l;
t.inserisci({b,l});
break;
default:
cout << "ERRORE!\n";
break;
}
}
}
void creaAlberi(Lista<Rectangle>& r, Lista<Circle>& c, Lista<Triangle>& t, Albero<Rectangle>& R, Albero<Circle>& C, Albero<Triangle>& T)
{
Nodo<Rectangle>* auxR = r.getTesta();
Nodo<Circle>* auxC = c.getTesta();
Nodo<Triangle>* auxT = t.getTesta();
while(auxR != NULL)
{
R.inserisci(auxR->valore);
auxR = auxR->succ;
}
while(auxC != NULL)
{
C.inserisci(auxC->valore);
auxC = auxC->succ;
}
while(auxT != NULL)
{
T.inserisci(auxT->valore);
auxT = auxT->succ;
}
}
void cancellaArea(int valore, Albero<Rectangle>& R, Albero<Circle>& C, Albero<Triangle>& T)
{
//NodoA<Rectangle>* retRicerca = R.search(valore);
R.cancella(valore);
C.cancella(valore);
T.cancella(valore);
}
int main()
{
int n;
int area;
Lista<Rectangle> r;
Lista<Circle> c;
Lista<Triangle> t;
Albero<Rectangle> R;
Albero<Circle> C;
Albero<Triangle> T;
cout << "Quanti elementi vuoi inserire? "; cin >> n;
creaListe(r, c, t, n);
creaAlberi(r, c, t, R, C, T);
cout << r << endl;
cout << c << endl;
cout << t << endl;
cout << R << endl;
cout << C << endl;
cout << T << endl;
cout << "Pre-Order Triangoli: "; T.preOrder();
cout << "Pre-Order Rettangoli: "; R.preOrder();
cout << "Pre-Order Cerchi: "; C.preOrder();
cout << "Inserisci l'area da voler eliminare: "; cin >> area;
cancellaArea(area,R,C,T);
cout << "\n\nALBERI POST ELIMINAZIONE\n\n";
cout << "Pre-Order Triangoli: "; T.preOrder();
cout << "Pre-Order Rettangoli: "; R.preOrder();
cout << "Pre-Order Cerchi: "; C.preOrder();
}
Qui sotto invece ci sono le due funzioni cancella (nodo) e quella di ricerca degli oggetti che abbiano un'area minore a quella data in input
template <typename T>
void Albero<T>::cancella(NodoA<T>* z)
{
//Caso 2: z ha un solo figlio
NodoA<T> *y; //Fungerà da ausiliare per tenere conto del padre di z
if(z->left == NULL)
trapianta(z,z->right);
else if(z->right == NULL)
trapianta(z,z->left);
//Caso 3: z ha entrambi i figli (Destro e Sinitro)
else
{
y = minimo(z->right); //y sarà il successo (destro) di z, può essere o figlio diretto di z, oppure non esserlo
if(y->padre != z) //Ecco il caso in cui il PADRE DI Y != Z (Quindi y non è figlio di z)
{
trapianta(y, y->right);
y->right = z->right;
y->right->padre = y;
}
trapianta(z,y);
y->left = z->left;
y->left->padre = y;
}
delete z;
}
template <typename T>
NodoA<T>* Albero<T>::ricercaIterativa(int valore)//Questa funzione serve per il compito. Ricerca iterativa.
{
NodoA<T> *aux = radice;
std::cout << aux << std::endl;
std::cout << "Area attuale: " << aux->valore.getArea() << std::endl;
while((aux != NULL) && (valore != (aux->valore.getArea())))
{
std::cout << " --> " << aux->valore;
if((aux->valore.getArea()) < valore)
return aux;
else
aux = aux->right;
}
return NULL;
}
Spero di essermi spiegato bene, il programma funziona in tutto per tutto ma non riesco proprio a sistemare l'elimnazione di un nodo. Grazie in anticipo a tutti