TD-1, recherche en table




Ce document est disponible à l'URL http://www.enseignement.polytechnique.fr/profs/informatique/Luc.Maranget/TC/TD-1/

Envoyez vos programmes à Luc.Maranget@inria.fr. Les solutions sont ici.
Important : le .emacs nouveau est arrivé. De la couleur pour tous, à condition de le recopier dans votre répertoire personnel.
1 Échauffement
Ce travail pratique va faire un usage abondant des chaînes. Les chaînes Java sont plus subtiles qu'il n'y paraît, principalement parce que Java utilise un jeu de caractère extrêmement étendu (sur 16 bits). Heureusement, il est possible de faire comme si les chaînes contenaient des bêtes caractères, 'a', 'b', etc. identifiés à la demande à leur code interne (qui est un entier...). Le programme Echo.java fait l'écho de ses arguments sur la console:
class Echo {
  public static void main (String arg[]) {
    for (int i = 0 ; i < arg.length ; i++) {
      System.out.println(arg[i]);
    }
  }
}
Transformez-le pour qu'il affiche les arguments minusculés. Vous pouvez soit, utiliser une fonction de librairie, soit travailler directement sur les caractères (plus long, mais intéressant, il faut remarquer que les codes des caractères alphabétiques (de 'a' à 'z' et de de 'A' à 'Z'), sont consécutifs).

(Solution avec une fonction de libraire, autre solution avec des caractères explicites qui ne marche pas pour les caractères accentués.

2 Une question simple
Combien y a t-il de prénoms différents chez les élèves de la promo et quels sont-ils ?

La classe Eleve, disponible comme le source Eleve.java, contient deux tableaux de chaînes, un tableau nom des noms et un tableau prenom des prénoms des élèves. (Les tableaux des noms et prénoms ont été construits à partir de la liste des élèves obtenue grâce à l'obligeance de Jean-Jacques Lévy) En ce qui vous concerne, il suffit de la mettre dans votre répertoire de travail et elle sera accessible de vos programmes.

2.1 La classe-programme Differents
Pour répondre à la passionnante question de connaître les prénoms des élèves, on va parcourir le tableau Eleve.prenom tout construisant une table table des prénoms différents. Ce travail sera réalisé par une classe Differents:
class Differents {
  .... // déclaration des variables et des méthodes.
}
Une table est en quelque sorte un tableau dont on utilise qu'une partie. Le plus simple est de représenter la table par deux variables: un tableau de chaînes table que l'on remplit de la gauche vers la droite, et un entier next qui représente conventionellement la prochaine place libre dans la table.
class Differents {
    static String [] table = new String [Eleve.prenom.length];
    static int next = 0;  // table vide pour commencer
On remarque au passage:
  1. Une variable se déclare par, éventuellement une suite de mots clefs (ici static), un type, un nom de variable, et en option une valeur initiale.
  2. Les types sont un peu bizarres, c'est plus ou moins la syntaxe de de C, le type des tableaux de chaîne s'écrit String [], celui des entiers est tout simplement int.
  3. Les chaînes semblent assez naturelles. Toutefois ce sont presque des objets (D'où la majuscule de leur type String).
  4. Les tableaux sont très dynamiques, ce sont quasiment des objets Java:
    1. On crée un nouveau tableau (ici de chaînes) par new String [length], c'est la syntaxe usuelle de l'appel de constructeur en Java. Appeler un constructeur c'est créer un objet à partir de sa classe.
    2. La longueur d'un tableau t se trouve dans la variable length de t.
2.2 Méthode d'insertion
La table des prénoms différents sera construite par insertion successive des prénoms. Moralement, la table est construite triée, l'insertion d'un élément se fait en parcourant la table jusqu'à trouver un élément qui lui est égal (auquel cas on laisse tomber) ou strictement plus grand que lui. Dans ce dernier cas on insère l'élément à sa place dans la table, ce qui impose de tout décaler d'un cran vers la droite. Programatiquement, la classe Different contient une méthode qui réalise l'insertion:

    static void insertion(String element) {
      ... // À compléter
    }

La méthode insertion prend en argument la chaîne à insérer dans la table et ne renvoie rien (void). En revanche elle va certainement modifier table et next si c'est utile, et contiendra sans doute une boucle.

2.3 Comparaison des chaînes
Notez que pour insérer une chaîne dans la table par la méthode insertion, il faut pouvoir comparer les chaînes entre elles. Or, les opérateurs traditionnels (<, >, ...) ne fonctionnent que sur les types scalaires (entiers, caractères...) et donc pas sur les chaînes.

Heureusement, on peut comparer deux chaînes s1 et s2, par l'appel s1.compareTo(s2) (tiens les chaînes sont des objets), voir la description de compareTo dans les morceaux de Java.

2.4 Méthode main
Il reste ensuite à transformer votre classe en programme, c'est à dire à le doter d'une méthode main:
  public static void main (String [] arg) { // Déclaration obligatoirement comme ça
    ... // À compléter
  }
Essentiellement, la méthode main va insérer tous les prénoms, puis afficher la table par deux boucles bien senties.

Une fois complet, votre programme devrait vous donner ce résultat :
Il y a 240 prenoms différents  (sur 472 élèves)
Abdelilah
Adrien
Agnès
Aimad
Alain
Alan
Alexandre
Alexei
Alexey
(La commande Unix head donne les dix premières lignes de son entrée, la construction de tuyau (pipe) ``commande1 | commande2'' connecte la sortie de la première commande sur l'entrée de la seconde.)

Vous pouvez comparer votre liste de prénoms avec la nôtre.
maranget@manche ~/TD/TD-1 > java Differents > ma_liste
maranget@manche ~/TD/TD-1 > diff ma_liste differents
(En Unix, la redirection commande > fichier range la sortie de commande dans fichier. La commande Unix diff compare deux fichiers.) (Solution.)

3 Une question plus raffinée
De toute évidence, certains élèves portent le même prénom. On se pose maintenant la question de savoir comment se répartissent les prénoms. Pour ce faire on va écrire un programme en deux classes.

3.1 Une classe des compteurs
Écrivez une classe des compteurs. Cette classe consiste essentiellement en une table d'association, qui à chaque prénom associe un entier. La classe Counter ``exporte'' trois méthodes: Pour réaliser la table d'association, la classe des compteurs utilise une table de hachage de façon interne. Il faut donc déclarer des tableaux, d'autres méthodes etc. dont l'usage est réservé aux méthodes de la classe Counter. De telles variables et méthodes sont dites privées et se déclarent à l'aide du mot-clé private. On peut par exemple écrire :
class Counter {
/*************************************/
/*   Données et méthodes privées     */
/*************************************/

/* Deux tableaux pour la table de hachage */
    private static int [] count = null; // rien au de'part
    private static String [] name = null; // non plus
/* Taille de la table */
    private static int size = 0;

    // Fonction de hachage, qui transforme s en un entier
    private static int hash (String s) {
       ...
    }

/*************************************/
/*   Le reste est accessible         */
/*************************************/

    static void set (String key, int v) {
       ...
    }

    static int get (String key) {
       ...
    }

    static void init (int size) {
        count = new int [size];  // initialisation du tableau des compteurs
        name = new String [size]; // initialisation du tableau des chaînes
        Counter.size = size;     // Jeu subtil sur le nommage des variables
    }
}
Il vous reste donc à écrire les méthodes, hash, set et get, ainsi que toute autre méthode privée que vous pourriez juger pratique. Vous aurez certainement besoins de quelques fonctions de librairie sur les chaînes, voyez la section sur les chaînes des morceaux de Java.

3.2 Compte des prénoms
Il reste à modifier la classe Differents de la section précédente, afin de calculer et d'afficher le nombre d'occurrences de chaque prénom, en plus du prénom lui-même. La nouvelle classe Stat sera en fait très peu différente de la précédente, elle sera juste enrichie de quelques appels aux méthode de la classe Counter. On devrait obtenir :
maranget@manche ~/TD/TD-1 > java StatPasBo | head
Il y a 240 prenoms différents  (sur 472 élèves)
Abdelilah (1)
Adrien (1)
Agnès (1)
Aimad (1)
Alain (1)
Alan (1)
Alexandre (9)
Alexei (1)
Alexey (1)
Voici notre liste complète, pour comparer avec la sortie de votre programme (solution).

4 Encore plus beau
L'affichage du programme de la section précédente n'est pas très satisfaisant. On veut plutôt voir apparaître les prénoms selon leur popularité. Les prénoms qui ont le même succès (ou le même insuccès) étant ensuite ordonnés selon l'ordre alphabétique.
maranget@manche ~/TD/TD-1 > java Stat | head
Il y a 240 prenoms différents dans la promo (sur 472 élèves)
Julien (17)
Nicolas (14)
Guillaume (12)
Laurent (12)
Olivier (12)
Vincent (11)
Pierre (10)
Thomas (10)
Alexandre (9)
Pour réaliser cet affichage, il suffit de trier le tableau table selon un nouveau critère (pour le moment table est trié selon l'ordre du dictionnaire). Il faut donc :
  1. Identifier précisément le nouveau critère de comparaison.

  2. Écrire une méthode qui le réalise. La déclaration de cette méthode sera :
    static boolean compare(String prenom1, String prenom2)
    


  3. Trier table à l'aide d'un tri classique. Quelques tris sont décrits dans le TD-1 d'il y a deux ans.
Voici notre liste complète (solution).

5 Et en Caml ?
5.1 Echauffement
S'attaquer à un classique. Par exemple l'affichage des sous-ensemble de [1..n].

L'entier n sera lu comme le premier argument du programme. Pour démarrer, voici un petit programme qui son premier argument, construit la liste des entiers de 1 à n et l'affiche.
open Printf

let n = int_of_string Sys.argv.(1) (* premier argument de la ligne de commande *)

let rec interval n m =
  if n > m then
    []
  else
    n :: interval (n+1) m

let plist l =
  List.iter (fun x -> printf " %d" x) l ;
  printf "\n"

let main () = plist (interval 1 n)
  
let _ = main () ; exit 0   (* exit 0 est là pour forcer l'affichage *)
Le programme est à utiliser par « ./a.out 10 ». Notez l'usage de List.iter du module List.
Solution.

5.2 Ce TP en Caml
Commencer au Compte des prénoms et utilser uniquement une table de hachage (module Hashtbl). La liste des noms et des prénoms sera lue sur l'entrée standard. Vous le partez pas de zéro mais de cet analyseur lexical stat.mll.

Pour afficher la liste triée, on transformera la table de hachage en liste de couple (avec Hashtbl.iter ou Hashtbl.fold), on triera cette liste (module List ou Sort) avec un critère bien vu, et on l'affichera par exemple avec List.iter.
Solution.


Dernière modification : 2002-11-27

Ce document a été traduit de LATEX par HEVEA.