Arbres

Arbres - Java - Programmation

Marsh Posté le 04-06-2009 à 23:08:23    

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 :
  1. import java.io.*;
  2. import java.util.*;
  3. public class ArbreLettre
  4. {
  5.     char lettre;
  6.     boolean finDeMot;
  7.     ArrayList lettresSuivantes;
  8.     /* constructeur */
  9.     ArbreLettre(char c)
  10.     {
  11.         lettre = c;
  12.         finDeMot = false;
  13.         lettresSuivantes = new ArrayList();
  14.     }
  15.    
  16.    
  17.     /* permet de modifier la variable finDeMot  
  18.        pour indiquer si un sous-arbre correspond ou non à la fin d'un mot */
  19.     void setFinDeMot(boolean b)
  20.     {
  21.         finDeMot = b;
  22.     }
  23.    
  24.    
  25.     /* teste si l'arbre correspond à la fin d'un mot (dernière lettre) */
  26.     boolean isFinDeMot()
  27.     {
  28.         return finDeMot;
  29.     }
  30.    
  31.    
  32.     /* teste si le caractère c est l'une des lettres suivant la lettre courante */
  33.     boolean contientLettre(char c)
  34.     {
  35.         for (int i=0; i<lettresSuivantes.size();i++)
  36. {
  37.             ALettre a = (ALettre)lettresSuivantes.get(i);
  38.             if (a.lettre == c) return true;
  39.         }
  40.         return false;
  41.     }
  42.    
  43.    
  44.     /* retourne le sous-arbre (lettre suivante) correspondant au caractère c */
  45.     ALettre getSousArbre(char c)
  46.     {
  47.         for (int i=0; i<lettresSuivantes.size();i++)
  48. {
  49.             ALettre a = (ALettre)lettresSuivantes.get(i);
  50.             if (a.lettre == c) return a;
  51.         }
  52.         return null;
  53.     }
  54.  
  55.    
  56.     /* ajoute mot dans l'arbre à lettres */
  57.     void ajouterMot(String mot){
  58.    
  59.     }
  60.     /* teste si mot existe dans l'arbre à lettre */
  61.     boolean contientMot(String mot){
  62.        
  63.     }
  64.    
  65. }


Reply

Marsh Posté le 04-06-2009 à 23:08:23   

Reply

Marsh Posté le 05-06-2009 à 00:01:35    

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

Reply

Marsh Posté le 05-06-2009 à 00:23:05    

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 :
  1. boolean motExiste(string mot)
  2. {
  3.    if(count(mot) == 0)
  4.        return true;
  5.    elseif(in_array(substr(0,1),lettreSuivantes))
  6.        return motExiste(substr(1,count(mot));
  7.    else
  8.        return false;
  9. }


 
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
Reply

Marsh Posté le 05-06-2009 à 12:48:18    

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 :
  1. import java.io.*;
  2. import java.util.*;
  3. public class ALettre
  4. {
  5. char lettre;
  6. boolean finDeMot;
  7. ArrayList lettresSuivantes;
  8.    
  9. /* constructeur */
  10. ALettre(char c)
  11. {
  12.  lettre = c;
  13.  finDeMot = false;
  14.  lettresSuivantes = new ArrayList();
  15. }
  16. /* permet de modifier la variable finDeMot  
  17. pour indiquer si un sous-arbre correspond ou non à la fin d'un mot */
  18. void setFinDeMot(boolean b)
  19. {
  20.  finDeMot = b;
  21. }
  22. /* teste si l'arbre correspond à la fin d'un mot (dernière lettre) */
  23. boolean isFinDeMot()
  24. {
  25.  return finDeMot;
  26. }
  27. /* teste si le caractère c est l'une des lettres suivant la lettre courante */
  28. boolean contientLettre(char c)
  29. {
  30.  for (int i=0; i<lettresSuivantes.size();i++)
  31.  {
  32.   ALettre a = (ALettre)lettresSuivantes.get(i);
  33.   if (a.lettre == c)
  34.    return true;
  35.  }
  36.  return false;
  37. }
  38. /* retourne le sous-arbre (lettre suivante) correspondant au caractère c */
  39. ALettre getSousArbre(char c)
  40. {
  41.  for (int i=0; i<lettresSuivantes.size();i++)
  42.  {
  43.   ALettre a = (ALettre)lettresSuivantes.get(i);
  44.   if (a.lettre == c)
  45.    return a;
  46.  }
  47.  return null;
  48. }
  49. /* ajoute mot dans l'arbre à lettres */
  50. void ajouterMot(String mot)
  51. {
  52. }
  53. /* teste si mot existe dans l'arbre à lettre */
  54. boolean contientMot(String mot)
  55. {
  56.         }
  57. /* lecture du fichier dico, construction de l'arbre et vérification */
  58. public static void main(String[] args)
  59. {
  60.  String fichier ="test.txt";
  61.  String fichier1 = "test1.txt";
  62.  String mot, lin;
  63.  StringTokenizer ligneToken;
  64.      
  65.  ALettre p;
  66.  p = new ALettre('A');
  67.  System.out.println("ça marche!!" );
  68.  //lecture du fichier texte           
  69.  try
  70.  {
  71.   InputStream input = new FileInputStream(fichier);
  72.   InputStreamReader streamReader = new InputStreamReader(input);
  73.   BufferedReader br = new BufferedReader(streamReader);
  74.          
  75.   while ((lin = br.readLine())!=null)
  76.   {
  77.    System.out.println("ça marche!!" );
  78.    ligneToken = new StringTokenizer(lin);
  79.    while (ligneToken.hasMoreTokens())
  80.    {
  81.     System.out.println("ça marche!!" );
  82.     mot = (ligneToken.nextToken());
  83.     System.out.println(mot);
  84.     p.ajouterMot(mot.toLowerCase());         
  85.    }         
  86.   }
  87.  br.close();
  88.  }
  89.  catch (Exception e)
  90.  {
  91.  }
  92.  //recherche du fichier texte           
  93.  try
  94.  {
  95.   InputStream input = new FileInputStream(fichier1);
  96.   InputStreamReader streamReader = new InputStreamReader(input);
  97.   BufferedReader br = new BufferedReader(streamReader);
  98.   while ((lin = br.readLine())!=null)
  99.   {
  100.    System.out.println("ça marche!!" );
  101.    ligneToken = new StringTokenizer(lin);
  102.              
  103.    while (ligneToken.hasMoreTokens())
  104.    {
  105.     System.out.println("ça marche!!" );
  106.     mot = (ligneToken.nextToken());
  107.     System.out.println(mot);
  108.                  
  109.     if(p.contientMot(mot.toLowerCase()))
  110.      System.out.println("ça marche!! Mot trouvé : "+mot);
  111.     else
  112.      System.out.println("ça marche pas!! Mot non trouvé : "+mot);
  113.    }             
  114.   }
  115.  br.close();
  116.  }
  117.  catch (Exception e)
  118.  {
  119.  }
  120. }
  121. }


 
Encore merci.

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed