0/5 (2 avis)
Vue 8 554 fois - Téléchargée 410 fois
template <class T> class sub_pile { public: sub_pile<T>* suivant; T* valeur; long int numeros; }; template <class T> class pile { private: sub_pile<T>* tete; int copy; public: pile(); pile(const pile<T>&); ~pile(); int ajouter(T* ); T* enlever(int ); T* depiler(); void vider(); T* get(int ); T* getlast(); int getlastnumber(); int getmaxnumber(); int nbelt(); void recompt(); bool estvide(); pile<T> operator=(pile<T>); pile<T> operator+(pile<T>); T* operator[](int); friend ostream& operator<<(ostream& ,pile<T>& ); friend istream& operator>>(istream& ,pile<T>& ); }; ////////////////////////////////////////////////////////////////////////////////////// ///////////////////////////////class : pile //////////////////////////////////////////// ////////////////////////////////////////////////////////////////////////////////////// // cette class permet de stocker sous forme de pile un certain type d'information #include <iostream.h> #include "pile.h" #include <limits.h> ////////////////////////////////////////////////////////////////////////////////////// // constructeur template <class T> pile<T>::pile() { copy=0; tete=NULL; } ////////////////////////////////////////////////////////////////////////////////////// // destructeur template <class T> pile<T>::~pile() { vider(); } ////////////////////////////////////////////////////////////////////////////////////// // vide la pile, copy=1 pour delete chaque element, 0 sinon template <class T> void pile<T>:: vider() { if(copy==0) { while(estvide()==0) { depiler(); }; } tete=NULL; } ////////////////////////////////////////////////////////////////////////////////////// // ajoute un element a la pile, // retour le numeros de l'element (-1 en cas d'echec) template <class T> int pile<T>:: ajouter(T* elt) { int i; // creation d'une nouvelle cellule sub_pile<T> *temp; temp=new sub_pile<T>; if( temp == NULL) { return -1; } temp->valeur=elt; temp->suivant = NULL; temp->numeros=0; // adition dans la pile if(tete==NULL) { tete = temp; tete->numeros = 0; return 0; } sub_pile<T> *der; der = tete; while(der->suivant != NULL) { der = der->suivant; }; if(der->numeros<INT_MAX) temp->numeros = der->numeros+1; else for(i=0;i<INT_MAX;i++) { if(get(i)==NULL) { temp->numeros=i; break; } } der->suivant = temp; return temp->numeros; } ////////////////////////////////////////////////////////////////////////////////////// // enleve l'element avec le numeros donne, retourne 0 si probleme, 1 sinon // attention 1: la classe ne peu pas liberer la memoire pointé par *T // cet methode n'utilise pas la variable copy // attention 2 : cette methode ne libere pas la memoire pointé par T* // si vous ne l'avez pas libéré vous meme ou si il n'existe pas une // copie de ce pointeur (dans une autre pile par exemple), la zone // memoire est perdu! template <class T> T* pile<T>::enlever(int nbcherche) { sub_pile<T>* temp; sub_pile<T>* adetruire; T* retour=NULL; if(tete == NULL) { return retour; } if(tete->numeros == nbcherche) { adetruire=tete; tete=tete->suivant; retour=adetruire->valeur; delete (adetruire); return retour; } if(tete->suivant == NULL) { return retour; } temp = tete; while(temp->suivant->suivant!=NULL) { if(temp->suivant->numeros==nbcherche) break; temp=temp->suivant; } if(temp->suivant->numeros!=nbcherche) { return retour; } adetruire=temp->suivant; temp->suivant=temp->suivant->suivant; retour=adetruire->valeur; delete (adetruire); return retour; } ////////////////////////////////////////////////////////////////////////////////////// // depile , retourne 0 si probleme, 1 sinon // attention 1: la classe ne peu pas liberer la memoire pointé par *T // cet methode n'utilise pas la variable copy // attention 2 : cette methode ne libere pas la memoire pointé par T* // si vous ne l'avez pas libéré vous meme ou si il n'existe pas une // copie de ce pointeur (dans une autre pile par exemple), la zone // memoire est perdu! template <class T> T* pile<T> :: depiler() { sub_pile<T>* temp; T* retour=NULL; if(tete==NULL) return retour; if(tete->suivant==NULL) { retour=tete->valeur; delete tete; tete=NULL; return retour; } temp=tete; while(temp->suivant->suivant!=NULL) { temp=temp->suivant; if(temp==NULL) { return retour; } if(temp->suivant==NULL) { return retour; } }; retour=temp->suivant->valeur; delete temp->suivant; temp->suivant=NULL; return retour; } ////////////////////////////////////////////////////////////////////////////////////// // retourne l'element avec ce numeros, NULL si il n'existe pas template <class T> T* pile<T> :: get(int nbcherche) { sub_pile<T>* temp; if(tete==NULL) { return NULL; } if(tete->suivant==NULL) { if(tete->numeros==nbcherche) { return (tete->valeur); } else { return NULL; } } temp=tete; while( temp->suivant!=NULL ) { if(temp->numeros==nbcherche) { return (temp->valeur); } temp=temp->suivant; }; if(temp->numeros!=nbcherche) { return NULL;} return (temp->valeur); } ////////////////////////////////////////////////////////////////////////////////////// // retourne le dernier element, NULL si vide template <class T> T* pile<T> :: getlast() { sub_pile<T>* temp; if(tete==NULL) { return NULL;} if(tete->suivant==NULL) { return (tete->valeur); } temp=tete; while(temp->suivant!=NULL) { temp=temp->suivant; } return (temp->valeur); } ////////////////////////////////////////////////////////////////////////////////////// //retourne le numeros du dernier template <class T> int pile<T> :: getlastnumber() { sub_pile<T>* temp; if(tete==NULL) { return -1; } if(tete->suivant==NULL) { return (tete->numeros); } temp=tete; while(temp->suivant!=NULL) { temp=temp->suivant; } return temp->numeros; } ////////////////////////////////////////////////////////////////////////////////////// //retourne le numeros le plus grande template <class T> int pile<T> :: getmaxnumber() { sub_pile<T>* temp; int max=-1; if(tete==NULL) { return -1; } if(tete->suivant==NULL) { return (tete->numeros); } temp=tete; max=tete->numeros; do { temp=temp->suivant; if(temp->numeros > max) max=temp->numeros; } while(temp->suivant!=NULL); return max; } ////////////////////////////////////////////////////////////////////////////////////// // 1 vide , 0 sinon template <class T> bool pile<T> :: estvide() { if(tete==NULL) return true; return false; } ////////////////////////////////////////////////////////////////////////////////////// // retourne le nombre d'element dans la pile template <class T> int pile<T> :: nbelt() { sub_pile<T>* temp; int nb=1; if(tete==NULL) { return 0;} if(tete->suivant==NULL) { return 1;} temp=tete; while(temp->suivant!=NULL) { temp=temp->suivant; nb++; } return nb; } ////////////////////////////////////////////////////////////////////////////////////// // retourne le nombre d'element dans la pile template <class T> void pile<T> :: recompt() { sub_pile<T>* temp; if(tete==NULL) { return ; } tete->numeros=0; if(tete->suivant==NULL) { return ; } temp=tete; while(temp->suivant!=NULL) { temp->suivant->numeros=temp->numeros+1; temp=temp->suivant; } return ; } ////////////////////////////////////////////////////////////////////////////////////// // retourne l'element avec ce numeros, NULL si il n'existe pas template <class T> T* pile<T> :: operator[](int nbcherche) { return get(nbcherche); } //////////////////////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////////////////////// //ici, on duplique entierement la pile, // il n'y a donc pas besoin de la proteger contre la destruction. //////////////////////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////////////////////// template <class T> pile<T>::pile(const pile<T>& lapile) { copy=0; tete=NULL; sub_pile<T> *temp,*temp2; temp=lapile.tete; if(temp!=NULL) { do { ajouter(temp->valeur); temp2=tete; while(temp2->suivant!=NULL) { temp2=temp2->suivant; } temp2->numeros=temp->numeros; temp=temp->suivant; } while(temp!=NULL); } } template<class T> pile<T> pile<T>::operator=(pile<T> lapile) { vider(); copy=0; tete=NULL; sub_pile<T> *temp; temp=lapile.tete; if(temp!=NULL) { do { ajouter(temp->valeur); temp=temp->suivant; } while(temp!=NULL); } return *this; } template <class T> pile<T> pile<T>:: operator+(pile<T> lapile) { pile<T> retour; retour.copy=0; sub_pile<T> *temp; if(tete==NULL) { retour=lapile; } else { retour=*this; temp=lapile.tete; while(temp!=NULL) { retour.ajouter(temp->valeur); temp=temp->suivant; } } retour.recompt(); return retour; } //////////////////////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////////////////////// // ici, c'est la meme pile qui sera utilisée, // il faut donc éviter que la 1ere pile se detruise en meme temps que // celle-ci! (utilisé ces methode pour les objet couteux en memoire) // attention, il est possible qu'il y est des problemes de recurences // ou de gestion de memoire. Dans le doute utiliser celles du dessus. //////////////////////////////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////////////////////////////// /* template <class T> pile<T>::pile(const pile<T>& lapile) { copy=1; tete=lapile.tete; } template <class T> pile<T> pile<T>:: operator=(pile<T> lapile) { vide(); copy=1; tete=lapile.tete; return *this; } // attention il peut y avoir des probleme de recurence si on ajoute 2 fois la meme pile! template <class T> pile<T> pile<T>:: operator+(pile<T> lapile) { pile<T> retour; retour.copy=1; sub_pile<T> *temp; if(tete==NULL) { retour=lapile; } else { retour=*this; temp=retour.tete; while(temp->suivant!=NULL) { temp=temp->suivant; } temp->suivant=lapile.tete; } retour.recompt(); return retour; }
4 mars 2004 à 12:48
Il existe déjà stack en C++ (donc ce ne doit être ici qu'un exercice)
Regarde la manière dont stack est implémenté dans le standard
pour t'inspirer et voir les choix qu'ils ont fait.
Mélanger du français/anglais dans les méthodes c'est pas
commode sinon (à mon goût en tout cas).
4 mars 2004 à 12:48
Il existe déjà stack en C++ (donc ce ne doit être ici qu'un exercice)
Regarde la manière dont stack est implémenté dans le standard
pour t'inspirer et voir les choix qu'ils ont fait.
Mélanger du français/anglais dans les méthodes c'est pas
commode sinon (à mon goût en tout cas).
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.