Utilisation d'un arbre binaire et des classes en c++ (algorithme)

Soyez le premier à donner votre avis sur cette source.

Vue 9 880 fois - Téléchargée 1 265 fois

Description

Un fichier est demandé pour une analyse lexicale. Les mots sont mémorisés dans les feuilles de l'arbre. A la fin l'arbre est lu et affiché sous forme de nombre
d'occurences ( répétitions ) des mots enregistrés.

Source / Exemple :


/*******************************************************************

  • Fichier string_nikko_defs.cpp
*
  • Contient les définitions de la classe String
*
                                                                                                                                      • /
#include "string_nikko.h" //--------- OPERATOR = pour la classe Strg ------ Strg & Strg::operator=( const Strg & op2 ) { delete [] string; //Libérer la mém. allouée par l'opérande gauche. //La taille initiale n'est pas bonne. if ( string = new char[ op2.len + 1 ] ) { strcpy( string, op2.string ); //Copie de la chaîne len = op2.len; //On "devient" comme l'autre. Même longueur. } else exit(1); return (*this); //Retourne réf. de l'opérande gauche. } //---------- OPERATOR + pour la classe Strg ----- Strg Strg::operator +( const Strg & op2) { Strg resultat; if ( resultat.string = new char[ strlen(string) + strlen(op2.string)+ 1 ] ) { strcpy( resultat.string, string ); //On prend le premier bout... strcat( resultat.string, op2.string ); //...et le deuxième. resultat.len = strlen(string) + strlen(op2.string); } else exit(1); return resultat; //Retourne la classe contenant le résultat. //Si c'était *this, cela signifirait que l'opérande //gauche est modifié ! } //---------- OPERATOR == pour test d'égalité --------- int Strg::operator ==( const Strg & op2 ) { int res = 0; //Contiendra le résultat du test. (tjrs en INT ) if ( strcmp( string, op2.string ) == 0 ) res = 1; return res; } //-------- OPERATOR <= pour test ------------ int Strg::operator <=( const Strg & op2 ) { static int res; //Contiendra le résultat du test. (tjrs en INT ) if ( strcmp( string, op2.string ) == 0 ) res = 1; if ( strcmp( string, op2.string ) < 0 ) res = 1; return res; } //-------- OPERATOR >= pour test ------------ int Strg::operator >=( const Strg & op2 ) { static int res; //Contiendra le résultat du test. (tjrs en INT ) if ( strcmp( string, op2.string ) == 0 ) res = 1; if ( strcmp( string, op2.string ) > 0 ) res = 1; return res; } //---------- OPERATOR > pour test d'égalité --------- int Strg::operator >( const Strg & op2 ) { static int res = 0; //Contiendra le résultat du test. (tjrs en INT ) if ( strcmp( string, op2.string ) > 0 ) res = 1; return res; } //---------- OPERATOR < pour test d'égalité --------- int Strg::operator <( const Strg & op2 ) { static int res = 0; //Contiendra le résultat du test. (tjrs en INT ) if ( strcmp( string, op2.string ) < 0 ) res = 1; return res; } //-------- OPERATOR [] POUR INDEXATION ------------- char & Strg::operator []( const int & index ) { char * p = 0; if (( index > len ) || ( index < 0 )) { cerr << "ERREUR [] :" << endl << "Indice en dehors de la plage admise."; return *p; } return string[index]; } //Surcharge de << pour cout: ostream & operator <<( ostream & out, const Strg & op ) { out << op.string; return out; } //Surcharge de >> pour cin: istream & operator >>( istream & in, Strg & op ) { char ph[256]; in >> ph; delete [] op.string; if ((op.string = new char[ strlen( ph ) + 1 ]) != 0) { strcpy( op.string, ph ); op.len = strlen( op.string ); } else exit (1); return in; } //------------------------------------------- // += //------------------------------------------- void Strg::operator += ( const Strg op ) { Strg resultat; if ( resultat.string = new char[ strlen(string) + strlen(op.string)+ 1 ] ) { strcpy( resultat.string, string ); //On prend le premier bout... strcat( resultat.string, op.string ); //...et le deuxième. resultat.len = strlen(string) + strlen(op.string); } else exit(1);
  • this = resultat;
} /*************************************************************************
  • Fichier string_nikko.h
                                                                                                                                              • /
#ifndef STRING_NIKKO_H_ #define STRING_NIKKO_H_ #include <iostream.h> #include <string.h> #include <process.h> // ======================================================================= class Strg { private: //------------------------------------------------------------ //Données accessibles seulement par les fonctions ci-dessous //------------------------------------------------------------- char * string; int len; public: //Ajout pour l'exo de l'arbre: int occurences; //--------------------------- // Constructeur avec un char //--------------------------- Strg( const char car ) { if ( string = new char[ 2 ] ) { string[ 0 ] = car; string[ 1 ] = '\0'; occurences = 1; } else exit (1); } //----------------------- //Fonction Constructeur: //----------------------- Strg( const char * s = "" ) { len = strlen( s ); if ( string = new char[ len + 1 ] ) //Allocation mémoire pour un espace.. { strcpy( string, s ); occurences = 1; } else exit (1); } //--------------------- //Fonction Destructeur //--------------------- ~Strg() //Destructeur: la mémoire doit être { //libérée car prise avec NEW if ( string == 0 ) cout << "WARNING: Tentative de destruction d'1 pointeur nul !" << endl; else { delete [] string; string = 0; //Pour ne pas le réutiliser. } } //-------------------------- //Accès à la chaîne de car. //-------------------------- char * show() { return string; } //--------------------------------------- //Accès en écriture de la chaîne de car. //--------------------------------------- void set( const char * ch ) { delete [] string; //La chaîne sera sûrement de taille != len = strlen( ch ); if ( string = new char[ len + 1 ] ) //Ré-allocation. strcpy( string, ch ); else exit(1); } //----------------------------------- //Surcharge d'opérateur pour copie //----------------------------------- Strg & operator =( const Strg & op2 ); //---------------------------------------- //Surchrage d'opérateur pour concaténation //---------------------------------------- Strg operator +( const Strg & op2 ); //-------------------------------------------- //Surcharge d'opérateur pour test d'égalité == //--------------------------------------------- int operator ==( const Strg & op2 ); //------------------------------ //Surcharge d'opérateur pour <= //------------------------------- int operator <=( const Strg & op2 ); //-------------------------------- //Surcharge d'opérateur pour >=* //-------------------------------- int operator >=( const Strg & op2 ); //----------------------------- //Surchrage d'opérateur pour > //----------------------------- int operator >( const Strg & op2 ); //----------------------------- //Surchrage d'opérateur pour < //----------------------------- int operator <( const Strg & op2 ); //---------------------------------------------- //Surcharge des crochets [] pour accès à un car. //---------------------------------------------- char & operator []( const int & index ); //--------------------------------- // += //--------------------------------- void operator += ( const Strg op ); //-------------------------------------------------------------- friend ostream & operator <<( ostream & out, const Strg & op ); friend istream & operator >>( istream & in, Strg & op ); //-------------------------------------------------------------- //---------------------- //Constructeur de copie //---------------------- Strg( const Strg & src ) //Appelé lorsque : - passage par valeur; { // - Strg s4(s1). if ((string = new char[ strlen( src.string) + 1 ]) != 0 ) { strcpy( string, src.string ); len = strlen( src.string); occurences = 1; } else exit (1); } //--------------------------------------------- //Constructeur de conversion de STRG en CHAR * //--------------------------------------------- operator char * () const //Ne modifie rien ! { return string; //Pas de type de retour, comme constructeur, } //Mais renvoi quan même (!) de qqchose. }; #endif /************************************************************************\
  • FICHIER: arbre_nikko_main.cpp
  • N.P. 18/04/02 (12:46:42)
  • OBJET:
  • Exemple d'utilisation d'un arbre binaire
  • NOTES:
  • Un fichier est demandé pour une analyse lexicale.
  • A la fin l'arbre est lu et affiché sous forme de nombre
  • d'occurences ( répétitions ).
*
  • L'arbre binaire est un moyen efficace et rapide pour traiter
  • un grand nombre de données. Son point le plus fort réside dans
  • le fait que les données sont pré-triées étant donné la façon
  • de ranger les données dedans !
* *
  • Point intérressant: les données contenues dans les feuilles de
  • l'arbre binaire sont des objets de la classe Strg ( String ).
  • A méditer ! ;-)
* \************************************************************************/ #include <ctype.h> #include <stdlib.h> #include <fstream.h> //Pour accès E/S aux fichiers #include <iostream.h> #include "string_nikko.h" #include "arbre_nikko.h" void main() { Strg filename; cout << "Utilisation d'un arbre binaire pour analyse lexicale." << "\n\n"; system( "dir/w" ); cout << endl << "Choisissez un fichier à analyser: "; cin >> filename; //Lecture du fichier afin de trouver les mots: Arbre sapin; Strg mot; char car = 0; //ouverture du fichier: fstream f1; f1.open( filename.show(), ios::in ); while ( !f1.eof() ) { f1.read( &car, sizeof( char ) ); if ((( car == ' ' ) || ( car == '\n' )) && ( mot[ 0 ] != '\0' )) { //Insertion du mot trouvé dans un arbre cout << mot << "|| "; sapin.AddNode( mot ); mot.set( "" ); //On repart pour un nouveau mot. } else if ( isalpha( car ) ) mot += Strg( car ); } //Fermeture du fichier: f1.close(); //Affichage de l'arbre: cout << "Fichier parcouru.Apercu de l'arbre:\n\n"; sapin.Afficher( sapin.ptr_r ); } /********************************************************************** *
  • Fichier arbre_nikko_defs.cpp
*
  • Contient les définitions de la classe Arbre
*
                                                                                                                                            • /
//---------------------------------------------------- // Définitions des fonctions membres des deux classes: //---------------------------------------------------- #include "arbre_nikko.h" #include "string_nikko.h" #include <iostream.h> #include <string.h> //------------------- // Ajouter un noeud //------------------- bool Arbre::AddNode( Strg & donnee ) { if ( ptr_r == 0 ) { //Si arbre sans branches... ptr_r = new Noeud; //...en voici une ! ptr_r->data_in = donnee; } else { Noeud * tmp = ptr_r; Noeud * n_parent; do //Recherche d'une feuille. { n_parent = tmp; if ( donnee == tmp->data_in ) { //On a trouvé la donnée dans l'arbre: tmp->data_in.occurences++; return true; } else if ( donnee < tmp->data_in ) tmp = tmp->n_g; //On chope l'adr du noeud futur papa else tmp = tmp->n_d; //On chope l'adr du noeud futur papa } while ( tmp ); //Maintenant, il faut créer ce nouveau noeud: if ( donnee < n_parent->data_in ) { n_parent->n_g = new Noeud; n_parent->n_g->data_in = donnee; } else { n_parent->n_d = new Noeud; n_parent->n_d->data_in = donnee; } } return true; } //------------------ // Gicler un noeud //------------------ bool Arbre::RemoveNode( Strg & donnee ) { if ( ptr_r == 0) return false; //On ne coupe pas l'arbre ! Noeud * tmp = ptr_r; Noeud * n_parent = ptr_r; //Parcours de l'arbre à la recherche de la valeur à trouver: while ( tmp && ( donnee != tmp->data_in ) ) { n_parent = tmp; if ( donnee <= tmp->data_in ) tmp = tmp->n_g; else tmp = tmp->n_d; if ( tmp == 0 ) return false; //La valeur n'y était pas ! } //Cas facile: il était célibataire: if (!tmp->n_g && !tmp->n_d ) { //IL est d*le noeud g ou d de son père ? if ( n_parent->n_g == tmp ) { //..le noeud gauche va mourrir. delete n_parent->n_g; n_parent->n_g = 0; } else { //...le noeud droit va mourrir. delete n_parent->n_d; n_parent->n_d = 0; } } //Cas difficile: deux gosses à charge: else if ( tmp->n_g && tmp->n_d ) { Noeud * tampon = tmp; //On regarde du côté du fils droit du 'zombie'. tmp = tmp->n_d; //Recherche jusqu'au bout de ce côté: while ( tmp->n_g ) { n_parent = tmp; tmp = tmp->n_g; } //Le fils droit n'a pas de noeaud à sa gauche? if ( tampon->n_d == tmp ) { tampon->data_in = tmp->data_in; tampon->n_d = tmp->n_d; delete tmp; } else { //Le fils gauche n'a pas de descendance? tampon->data_in = tmp->data_in; n_parent->n_g = tmp->n_d; delete tmp; } } //Cas medium: un noeud fils: d ou g ? else if ( tmp->n_g ) n_parent = tmp->n_g; else n_parent = tmp->n_d; tmp->data_in = n_parent->data_in; tmp->n_d = n_parent->n_d; tmp->n_g = n_parent->n_g; //TODO return true; } //--------------------------------------- // Parcours de l'arbre à la recherche de // la donnée à trouver: //--------------------------------------- Noeud * Arbre::Wanted( Strg donnee ) { Noeud * tmp; //Parcours de l'arbre: while ( tmp && ( donnee != tmp->data_in ) ) { if ( donnee < tmp->data_in ) tmp = tmp->n_g; else tmp = tmp->n_d; if ( tmp == 0 ) return 0; //La valeur n'y était pas ! } return tmp; } //--------------------------------------------------- // Affichage de l'arbre: départ au fond à gauche, // puis on remonte à la recine et on fait pareil à d. //--------------------------------------------------- void Arbre::Afficher( Noeud * org ) { if ( org == 0 ) return; Afficher( org->n_g ); cout << "Mot: " << org->data_in << "\tOccurences : " << org->data_in.occurences << endl; Afficher( org->n_d ); } /********************************************************************* *
  • Fichier arbre_nikko.h
*
                                                                                                                                          • /
//------------------------------------------ // Fichier d'en-tête contenant les classes //------------------------------------------ #include "string_nikko.h" #ifndef ARBRE_NIKKO_H #define ARBRE_H const short LG_MOT_MAX = 50; //Pour les mots //---------------------- // Classe de base Noeud //---------------------- class Noeud { //Pour lire tout les noeuds avec la classe Arbre. friend class Arbre; public: Noeud( Noeud * ng = 0, Noeud * nd = 0, Strg done = "" ) { //Constructeur: n_g = ng; n_d = nd; data_in = done; //Le constructeur Strg met une chaîne vide par défaut. } protected: Noeud * n_g; Noeud * n_d; Strg data_in; }; //---------------------- // Classe dérivée Arbre //---------------------- // Elle hérite de deux pointeurs de noeud: n_g et n_d class Arbre : private Noeud { public: Arbre( Noeud * r = 0, Noeud * g = 0, Noeud * d = 0 ) { ptr_r = r; n_g = g; n_d = d; } void Arbre::Afficher( Noeud * org ); bool AddNode( Strg & ); bool RemoveNode( Strg & ); Noeud * Wanted( Strg donnee ); Noeud * ptr_r; }; #endif

Conclusion :


N'hésitez pas à donner vos idées ou vos reproches, qui sont aussi des idées d'ailleurs, mais négatives :-)

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

cs_nikko
Messages postés
62
Date d'inscription
jeudi 18 avril 2002
Statut
Membre
Dernière intervention
29 septembre 2004
-
Si t'es débutant en C++ ça va te défriser ;)

Tu as dû télécharger l'archive et dedans tu as uniquement du code (*.cpp) et des fichiers d'en-tête (*.h). Pour t'en servir cela dépend de ton compilateur (gcc sous Linux, visual C++, devCpp, etc). D'une façon générale, crée un nouveau projet et insère les sources téléchargées.

@++
Gandalf The White
Messages postés
1
Date d'inscription
lundi 19 avril 2004
Statut
Membre
Dernière intervention
19 avril 2004
-
hello je suis un nouvel utilisteur du C++ et je suis interessé par ton code le probleme c'est que j'ai beau y mettre du mien je n'arrive pas a faire tourner ton prog.
Si on pouvais en discuter cool.
Merci de me contacter
a+
halkassad
Messages postés
2
Date d'inscription
mercredi 4 juin 2003
Statut
Membre
Dernière intervention
11 juillet 2003
-
Désolé, j ai mal expliqué mon contexte de travail. Je travaille sur un arbre binaire commun. Nous sommes une équipe qui modélisons la forme d un arbre biologique a l aide d un arbre binaire. Chaque noeud va representer un organe (un segment). L intérêt de trouver le chemin entre 2 noeuds est d étudier les flux de sève entre 2 organes sur la base de modèles mathématiques que nous voudrions tester dans un contexte biologique. J ai l impression d apres ce que j ai pu observer sur Internet que pour faire des parcours de chemin il faut passer par des graphes...Nous voudrions rester sur un modèle plus simple a notre niveau (nous ne sommes pas vraiment des matheux) et continuer notre etude avec l arbre binaire.
Merci de l interet que vous porterez a ce commentaire.
cs_nikko
Messages postés
62
Date d'inscription
jeudi 18 avril 2002
Statut
Membre
Dernière intervention
29 septembre 2004
-
??? Je ne comprends pas bien là... Le chemin entre deux noeuds..mais quelle est l'utilité ?
Le but de l'arbre c'est de pouvoir trouver une donnée très rapidement parce que les données sont triées lors de construction de l'arbre (les perfos diminuent si l'arbre est mal construit ou trop modifié).
halkassad
Messages postés
2
Date d'inscription
mercredi 4 juin 2003
Statut
Membre
Dernière intervention
11 juillet 2003
-
peut on trouver le chemin entre 2 noeuds ?

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.