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);
}
/*************************************************************************
#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 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 :-)
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.