Salve,ho necessità di un consiglio x migliorare il programma sotto riporato.
Mi è stato già suggerito di allocare i molti oggetti allocati dinamicamente in maniera statica; volrrei chiedervi se avete altri suggerimenti x renderlo più efficente e leggibile..
Ci tengo a precisare che il prog nn deve rispettare specifiche particolari, deve implamentare un albero binario utilizzando template e grosso modo deve effettuare le operazioni di inserimento, cancellazione, trovare max, il min ecc insomma + o- tutte quelle che ho gia definito.. Qualsiasi suggerimento è ben accetto. Grazie
------------------------------------------------------------------------------------
--------------------------------------------------------------------------------------codice://main.cpp //programma di verifica della classe Albero #include "proj.h" int main(){ Albero<int> P; int v[]={47,25,11,7,17,43,31,44,77,65,68,93}; for (int i=0;i<12;i++){ P.inserisci(v[i]); } cout<<P; P.MostraRadice(); P.Massimo(); P.Minimo(); P.Ricerca(7); P.Cancella(7); cout<<P; P.MostraRadice(); P.Massimo(); P.Minimo(); return 0; }
codice://proj.h //Implementazione di un albero binario tramite programmazione generica[template] #ifndef ALBEROBIN_H #define ALBEROBIN_H #include <iostream> using namespace std; template<class T>class Albero{ friend ostream& operator<<(ostream &,Albero<T>); public: Albero(){Radice=0; } ~Albero(){} class Nodo{ public: Nodo(){ sinistro=0; destro=0; chiave=0; padre=0; } ~Nodo(){} Nodo * sinistro; Nodo * destro; Nodo * padre; T chiave; }; void inserisci(T);//inserisce un nodo nell'albero void Massimo();//stampa il massimo void Cancella(T);//interfaccia per la funzione cancella void Ricerca(T);//interfaccia per la funzione ricerca void Minimo();//stampa il minimo void MostraRadice();//stampa la radice void Stampa(ostream &);//utilizzata nella funzione che ridefinisce //l'operatore << per accedere alle funzioni //membro private private: //funzioni membro private void cancella(T,Nodo **);//cancella un nodo che ha una certa chiave bool ricerca(T,Nodo **);//ricerca un nodo che ha una certa chiave void successore(Nodo **);//trova il successore di un nodo void minimo(Nodo **);//scorre l'albero fino a trovare il nodo che ha chiave minore void massimo(Nodo **);//scorre l'albero fino a trovare il nodo con chiave minore void InOrdine(Nodo *,ostream &);//visualizza in ordine simmetrico void PreOrdine(Nodo *,ostream &);//visualizza in ordine anticipato void PostOrdine(Nodo *,ostream &);//visualizza in ordine posticipato Nodo * Radice; //radice dell'albero }; //definizione delle funzioni membro pubbliche; la classe Nodo è resa trasparente all'utente template<class T>void Albero<T>::Massimo(){ Nodo *x=new Nodo(); x=Radice; massimo(&x); cout<<"La chiave di valore maggiore contenuta nell'albero e':"<<x->chiave<<endl; } template<class T>void Albero<T>::Cancella(T chiave){ Nodo *x=new Nodo(); x=Radice; cout<<"Cancellazione del nodo con chiave "<<chiave<<endl; cancella(chiave,&x); cout<<"Nodo cancellato"<<endl; } template<class T>void Albero<T>::Ricerca(T chiave){ Nodo *x=new Nodo(); cout<<"Ricerca della chiave "<<chiave<<".. "; if(ricerca(chiave,&x)) cout<<"trovata"<<endl; else cout<<"chiave non trovata"<<endl; } template <class T>void Albero<T>::Minimo(){ Nodo *x=new Nodo(); x=Radice; minimo(&x); cout<<"La chiave minore contenuta nell'albero e': "<<x->chiave<<endl; } template <class T>void Albero<T>::MostraRadice(){ Nodo *x=new Nodo(); x=Radice; cout<<"La radice dell'albero e': "<<x->chiave<<endl; } template <class T>void Albero<T>::Stampa(ostream &out){ out<<"Visualizzazione in Ordine Simmetrico: "; InOrdine(Radice,out); out<<"\nVisualizzazione in Ordine Anticipato: "; PreOrdine(Radice,out); out<<"\nVisualizzazione in Ordine Posticipato: "; PostOrdine(Radice,out); out<<endl; } //definizione delle funzioni membro private template<class T>void Albero<T>::inserisci(T ChiaveDaInserire){ Nodo * y=new Nodo(); Nodo * x=new Nodo(); Nodo * z=new Nodo(); y=0; x=0; x=Radice; (z->chiave)=ChiaveDaInserire;//preparazione del nodo da inserire while (x!=0){//ricerca della corretta posizione per l'inserimento y=x; if((z->chiave)<(x->chiave)) x=x->sinistro; else x=x->destro; } z->padre=y; //inserzione del nodo if (y==0) Radice=z; else if((z->chiave)<(y->chiave)) y->sinistro=z; else y->destro=z; } template<class T>void Albero<T>::cancella(T ChiaveDaCancellare,Nodo **z){ Nodo *y=new Nodo(); Nodo *x=new Nodo(); ricerca(ChiaveDaCancellare,z);//ricerca del nodo da cancellare if(((*z)->sinistro==0)||((*z)->destro==0)) y=*z;//si determina se il nodo da //cancellare ha figli else { successore(z);//se ce li ha entrambi se ne trova il successore y=(*z); } //che necessariamente ha un solo figlio if(y->sinistro!=0) x=y->sinistro; else x=y->destro;//in x si memorizza il figlio del nodo da cancellare if(x!=0) x->padre=y->padre;//se x esiste si attacca al padre del nodo da //cancellare if((y->padre)==0) x=Radice;//se il nodo cancellato era la radice //la nuova radice è x if(y=(y->padre->sinistro)) y->padre->sinistro=x; else y->padre->destro=x;//se il nodo cancellato era il figlio sinistro/destro //si aggiorna il puntatore sinistro/destro if(y!=(*z)) (*z)->chiave=y->chiave;//se il nodo da cancellare ha richiesto //la determinazione del successore copia la chiave //del successore (*z)=y;//restituisce il nodo cancellato } template<class T>bool Albero<T>::ricerca(T ChiaveDaRicercare,Nodo **x){//ricerca iterativa *x=Radice;//partiamo dalla radice si scorre l'albero fino a trovare la chiave while(((*x)!=0)&&((*x)->chiave!=ChiaveDaRicercare)){ if(ChiaveDaRicercare<((*x)->chiave)) *x=(*x)->sinistro; else (*x)=(*x)->destro; } if((*x)!=0)return true; else return false; } template<class T>void Albero<T>::successore(Nodo **x){ Nodo *y=new Nodo(); if((*x)->destro!=0){ minimo(&((*x)->destro));//se il nodo ha figlio destro il successore return; //coincide con il nodo minimo del sottoalbero } //destro y=(*x)->padre;//se non ha un figlio destro while((y!=0)&&((*x)=y->destro)){ (*x)=y; //si risale gli antenati di x fino a trovare il nodo y=(*x)->padre;//antenato meno lontano e più piccolo } (*x)=y; } //dato un nodo ne discende tutti i figli alla sinistra fino a trovare il minimo template<class T>void Albero<T>::minimo(Nodo **x){ while(((*x)->sinistro)!=0) {(*x)=(*x)->sinistro;} } //dato un nodo ne discende tutti i figli alla destra fino a trovare il massimo template<class T>void Albero<T>::massimo(Nodo **x){ while(((*x)->destro)!=0) {(*x)=(*x)->destro;} } //visualizzazzione dei nodi template<class T>void Albero<T>::InOrdine(Nodo *x,ostream &out){ if (x!=0) { InOrdine(x->sinistro,out); out<<(x->chiave)<<" "; InOrdine(x->destro,out); } } template<class T>void Albero<T>::PreOrdine(Nodo *x,ostream &out){ if (x!=0) { out<<(x->chiave)<<" "; PreOrdine(x->sinistro,out); PreOrdine(x->destro,out); } } template<class T>void Albero<T>::PostOrdine(Nodo *x,ostream &out){ if (x!=0) { PostOrdine(x->sinistro,out); PostOrdine(x->destro,out); out<<(x->chiave)<<" "; } } //definizione della classe friend che effettua una ridefinizione dell'operatore << e permette //dato un albero la stampa dei suoi elementi in ordine anticipato simmetrico e posticipato template <class T> ostream& operator<<(ostream &out,Albero<T> A){ out<<"##########Visualizzazione dei nodi##########\n"; A.Stampa(out); return out; } #endif
Rispondi quotando
