Java

Arbres

Recherche :

Mot : Pseudo : Filtrer
Bas de page
Auteur	Sujet : Arbres

jmfr

Salut à tous,

Je suis en train de créer une classe qui permet de construire un arbre à lettres.
L’idée est de regrouper tous les mots en un arbre dont chaque arc représente une lettre. Donc un mot sera représenté par un chemin de la racine à un nœud contenant la valeur “fin de mot”.
En fait, il s'agit d'une manière compacte de représenter un ensemble de mot, comme par exemple un dictionnaire. Je veux ajouter deux méthodes, l'une pour tester si un mot introduit par l'utilisateur appartient déjà à l'arbre et une autre méthode pour permettre d'y ajouter un mot. J'utilise pas la JTree, tout est fait avec l'array.
Je vous envoie ci-dessous mon code avec quelques commentaires.

Quelqu'un pourrait m'aider?

Merci.

Code :

import java.io.*;
import java.util.*;
public class ArbreLettre
{
char lettre;
boolean finDeMot;
ArrayList lettresSuivantes;
/* constructeur */
ArbreLettre(char c)
{
lettre = c;
finDeMot = false;
lettresSuivantes = new ArrayList();
}
/* permet de modifier la variable finDeMot
pour indiquer si un sous-arbre correspond ou non à la fin d'un mot */
void setFinDeMot(boolean b)
{
finDeMot = b;
}
/* teste si l'arbre correspond à la fin d'un mot (dernière lettre) */
boolean isFinDeMot()
{
return finDeMot;
}
/* teste si le caractère c est l'une des lettres suivant la lettre courante */
boolean contientLettre(char c)
{
for (int i=0; i<lettresSuivantes.size();i++)
{
ALettre a = (ALettre)lettresSuivantes.get(i);
if (a.lettre == c) return true;
}
return false;
}
/* retourne le sous-arbre (lettre suivante) correspondant au caractère c */
ALettre getSousArbre(char c)
{
for (int i=0; i<lettresSuivantes.size();i++)
{
ALettre a = (ALettre)lettresSuivantes.get(i);
if (a.lettre == c) return a;
}
return null;
}
/* ajoute mot dans l'arbre à lettres */
void ajouterMot(String mot){
}
/* teste si mot existe dans l'arbre à lettre */
boolean contientMot(String mot){
}
}

Publicité

funlys

Précise un peur plus ce que tu veux...

vhAnton

Ca fait un moment que j'ai pas fais de java, donc pour la gestion des chaines je vais faire avec substr(debut,fin) (idem pour in_array, fait la correspondance)

Code :

boolean motExiste(string mot)
{
if(count(mot) == 0)
return true;
elseif(in_array(substr(0,1),lettreSuivantes))
return motExiste(substr(1,count(mot));
else
return false;
}

Ca devrait marcher, la recurence est la, desolé pour le code

EDIT : Wai, je dis n'importe quoi moi, je vais plutot aller me coucher

Message édité par vhAnton le 05-06-2009 à 00:26:03

jmfr

Salut,

Merci pour vos réponses.

Ce que je veux faire c'est:
Créer les méthodes contientMot et ajouterMot.
Ensuite d'utiliser cette classe pour construire un arbre à lettre à partir d'un fichier texte. Finalement lire le fichier et afficher tous les mots qui ne se trouvent pas dans l'arbre à lettres construit à partir du premier fichier.

C'est la création de ces 2 méthodes qui me posent problème. Pour le reste c'est bon.

Je pense que la solution la plus facile est de faire avec récursivité,il faudrait utiliser les deux methodes contientlettres et getsousarbre
dans un appel récursif pour les deux methodes contientMot et ajouterMot.

Le principe est le même, donc si je peux trouver l'algorithme correct pour la méthode ajouterMot alors c'est exactement
le même principe pour l'autre méthode c'est juste au lieu d'ajouter il faut renvoyer un booléen.

Voilà...mais pour l'instant je n'ai pas réussi.

Quelqu'un pourrait-m'aider?

Voici une version plus récente de mon code:

Code :

import java.io.*;
import java.util.*;
public class ALettre
{
char lettre;
boolean finDeMot;
ArrayList lettresSuivantes;
/* constructeur */
ALettre(char c)
{
lettre = c;
finDeMot = false;
lettresSuivantes = new ArrayList();
}
/* permet de modifier la variable finDeMot
pour indiquer si un sous-arbre correspond ou non à la fin d'un mot */
void setFinDeMot(boolean b)
{
finDeMot = b;
}
/* teste si l'arbre correspond à la fin d'un mot (dernière lettre) */
boolean isFinDeMot()
{
return finDeMot;
}
/* teste si le caractère c est l'une des lettres suivant la lettre courante */
boolean contientLettre(char c)
{
for (int i=0; i<lettresSuivantes.size();i++)
{
ALettre a = (ALettre)lettresSuivantes.get(i);
if (a.lettre == c)
return true;
}
return false;
}
/* retourne le sous-arbre (lettre suivante) correspondant au caractère c */
ALettre getSousArbre(char c)
{
for (int i=0; i<lettresSuivantes.size();i++)
{
ALettre a = (ALettre)lettresSuivantes.get(i);
if (a.lettre == c)
return a;
}
return null;
}
/* ajoute mot dans l'arbre à lettres */
void ajouterMot(String mot)
{
}
/* teste si mot existe dans l'arbre à lettre */
boolean contientMot(String mot)
{
}
/* lecture du fichier dico, construction de l'arbre et vérification */
public static void main(String[] args)
{
String fichier ="test.txt";
String fichier1 = "test1.txt";
String mot, lin;
StringTokenizer ligneToken;
ALettre p;
p = new ALettre('A');
System.out.println("ça marche!!" );
//lecture du fichier texte
try
{
InputStream input = new FileInputStream(fichier);
InputStreamReader streamReader = new InputStreamReader(input);
BufferedReader br = new BufferedReader(streamReader);
while ((lin = br.readLine())!=null)
{
System.out.println("ça marche!!" );
ligneToken = new StringTokenizer(lin);
while (ligneToken.hasMoreTokens())
{
System.out.println("ça marche!!" );
mot = (ligneToken.nextToken());
System.out.println(mot);
p.ajouterMot(mot.toLowerCase());
}
}
br.close();
}
catch (Exception e)
{
}
//recherche du fichier texte
try
{
InputStream input = new FileInputStream(fichier1);
InputStreamReader streamReader = new InputStreamReader(input);
BufferedReader br = new BufferedReader(streamReader);
while ((lin = br.readLine())!=null)
{
System.out.println("ça marche!!" );
ligneToken = new StringTokenizer(lin);
while (ligneToken.hasMoreTokens())
{
System.out.println("ça marche!!" );
mot = (ligneToken.nextToken());
System.out.println(mot);
if(p.contientMot(mot.toLowerCase()))
System.out.println("ça marche!! Mot trouvé : "+mot);
else
System.out.println("ça marche pas!! Mot non trouvé : "+mot);
}
}
br.close();
}
catch (Exception e)
{
}
}
}

Encore merci.

FORUM HardWare.fr

Programmation

Java

Arbres

Sujets relatifs
Les Arbres	[C]Arbres et seg fault
Les arbres programmatique	Arbres 2-3
[Arbres] Logiciel de dessin	Aides sur les arbres n-aires
[XML] XML encryption : cryptage d'arbres XML	[ALGO/SQL] Gérer les arbres en SQL
[SQL] Algèbre relationnelle, arbres algèbriques et SQL [resolu]	[structure] Comment représenter des arbres ?
Plus de sujets relatifs à : Arbres

Page générée en 0.100 secondes