Arbre Lexicographique [Résolu]

Signaler
Messages postés
2865
Date d'inscription
samedi 2 novembre 2002
Statut
Membre
Dernière intervention
11 mai 2009
-
cs_LordBob
Messages postés
2865
Date d'inscription
samedi 2 novembre 2002
Statut
Membre
Dernière intervention
11 mai 2009
-
Bonjour a tous,
voila en fait j'ai un exercice d'algorithmique ou je dois créé un arbre l'exicographique, voici la structure de ma classe:

class ArbreLexico
{
    private:
        class Noeud
        {
            private:
                char info;
                bool fin;
                ArbreLexico *fils[26];

            public:
                Noeud( void )
                {
                    int i;

                    fin = true;

                    for(i=0; i < 26; i++)
                        fils[i] = NULL;
                }
               
                Noeud( char val )
                {
                    int i;

                    fin = true;

                    for(i=0; i < 26; i++)
                        fils[i] = NULL;

                    info = val;
                }

                Noeud( char val, bool f )
                {
                    int i;

                    fin = f;

                    for(i=0; i < 26; i++)
                        fils[i] = NULL;

                    info = val;
                }

                char getVal()
                { return( info ); }
               
                void setVal( char val )
                { info = val; }

                void setFils( int i, ArbreLexico *a )
                { fils[i] = a; }

                void setFin( bool val )
                { fin = val; }

                ArbreLexico *getFils( int i )
                { return( fils[i] ); }

                bool getFin()
                { return(fin); }
        };
        Noeud *arb;

    public:
        ArbreLexico( void );
        ArbreLexico( char *v );
        void add( char *v );
        void aff( void );
        bool rechercher( char *u );
};

alors pour ajouter un mot dans l'arbre, aucun problème, pour rechercher si un mot existe aucun problème non plus.
la ou ca coince, c'est pour afficher les mots qu'il y a dans l'arbre. je ne vois pas comment pouvoir afficher tous les mots contenu dans l'arbre.
j'aimerais que vous me donniez quelques piste pour pouvoir faire l'affichage des mots contenue dans l'abre parce que la je séche total.
Merci par avance.
Bob...
"Vaut mieux se taire et passer pour un con, que de l'ouvrir et ne laisser aucun doute sur le sujet..."

7 réponses

Messages postés
6535
Date d'inscription
lundi 16 décembre 2002
Statut
Modérateur
Dernière intervention
22 août 2010
7
Je pense pas qu'il y ait besoin de ca. Voila ce que je ferais, a quelques erreurs près:

int p = 0;
char buffer[MAX_LONGUEUR_MOT];

void aff( void )
{
  if(getFin())
  {
    buffer[p] = 0;
    puts(buffer);
  }

  else for(int i = 0; i < 26; i++)
  {
    if(fils[i])
    {
      buffer[p++] = i + 'a';
      fils[i]->aff();
      p--;
    }
  }
}

_____________________________________
Un éditeur de ressources gratuit pour Windows
Messages postés
2865
Date d'inscription
samedi 2 novembre 2002
Statut
Membre
Dernière intervention
11 mai 2009
9
bon je viens de trouver, il faut que je commence a par initialiser mes variables de classe.
mais maintenant j'ai un autre petit probleme.

sinon voici la méthode d'affichage terminer:
void ArbreLexico::aff()
{
    if( arb -> getVal() == '#' )
    {
        for(int i = 0; i < 26; i++)
        {
            p = 0;

            if( arb -> getFils( i ) != NULL )
                arb -> getFils( i ) -> aff();
        }

        return;
    }

    if( arb -> getFin() )
    {
        buffer[p] = arb -> getVal();
        p++;

        buffer[p] = '\0';
        puts( buffer );
        p--;
    }
   
    for(int i = 0; i < 26; i++)
    {
        if( arb -> getFils( i ) != NULL )
        {
            buffer[p++] = arb -> getVal();

            arb -> getFils( i ) -> aff();
            p--;
        }
    }
}

merci beaucoup pour ton aide et de m'avoir mis sur la piste.
bonne continuation a toi.
Bob...
"Vaut mieux se taire et passer pour un con, que de l'ouvrir et ne laisser aucun doute sur le sujet..."
Messages postés
6535
Date d'inscription
lundi 16 décembre 2002
Statut
Modérateur
Dernière intervention
22 août 2010
7
"un arbre l'exicographique" no comment

Tu peux décrire plus précisément la structure de ton arbre? Par exemple comment est représenté un arbre contenant un seul mot?

_____________________________________
Un éditeur de ressources gratuit pour Windows
Messages postés
2865
Date d'inscription
samedi 2 novembre 2002
Statut
Membre
Dernière intervention
11 mai 2009
9
Bah en fait l'arbre est composé de noeud.
un noeud c'est un caractere, un booleen qui indique la fin d'un mot (bien que l'arbre peut se "prolonger" encore) et ensuite le possibilité d'avoir 26 fils.

en fait mon probleme dans l'affichage des mots contenu dans l'arbres, c'est le fait de revenir sur ces pas, tout en gardant en mémoire ce que l'on a deja parcourus dans l'arbre, je pensais peut etre faire ca au moyen d'une pile, mais voila quoi...
Bob...
"Vaut mieux se taire et passer pour un con, que de l'ouvrir et ne laisser aucun doute sur le sujet..."
Messages postés
2865
Date d'inscription
samedi 2 novembre 2002
Statut
Membre
Dernière intervention
11 mai 2009
9
c'est vrai que ton code n'a pas l'air bete, c'est meme plutot intelligent, par contre je ne comprend pas pourquoi tu fait buffer[p++] = i + 'a'; la on devrait plutot récupéré la valeur du noeud.
Bob...
"Vaut mieux se taire et passer pour un con, que de l'ouvrir et ne laisser aucun doute sur le sujet..."
Messages postés
6535
Date d'inscription
lundi 16 décembre 2002
Statut
Modérateur
Dernière intervention
22 août 2010
7
Vu qu'il y en a 26, je pensais qu'implicitement le 1er était 'a', le 2ème 'b', etc...
Pourquoi ne pas faire comme ca?

_____________________________________
Un éditeur de ressources gratuit pour Windows
Messages postés
2865
Date d'inscription
samedi 2 novembre 2002
Statut
Membre
Dernière intervention
11 mai 2009
9
non ca ne se passe pas comme ca, et je ne sais vraiment pas comment t'expliquer...
mais je te remercie quand meme pour ton code car il m'a aidé a comprendre comment faire, bien sur je l'adapte à mon code.

j'essairé d'expliquer le principe tout a l'heure, pour l'heure j'ai un petit probleme, que je ne comprend pas d'ou vient mon erreur, je te montre voici la déclaration de ma classe (simplifié):

class ArbreLexico
{
    private:
        ...
        static int p;
        ...

    public:
        ArbreLexico( void );
        ...
};

et mon constructeur:

ArbreLexico::ArbreLexico()
{
...
    p = 0; <= erreur ici!!!!
...
}

pourquoi dès que j'essai d'affecté le p, j'ai une erreur de link, alors que la compilation marche très bien?
Bob...
"Vaut mieux se taire et passer pour un con, que de l'ouvrir et ne laisser aucun doute sur le sujet..."