Ce document a été produit par HEVEA.
Votre browser peut avoir a être configuré pour afficher correctement certains symboles.
Reportez-vous à la documentation d'HEVEA.

Licence d'informatique
Module de C/Unix

TD de programmation en C : le dictionnaire

Nouvelle révision, janvier 2001

Ce document est disponible sous forme d'un fichier PostScript compressé.

On se propose de gérer un dictionnaire de mots (un mot est une liste de lettres) avec la structure de données suivante : un noeud du dictionnaire est composé d'une lettre et de deux pointeurs ; un pointeur vers un fils détenant la lettre suivante du mot et un pointeur vers un frère codant un mot qui a la même racine (les mêmes premières lettres que le mot). La liste des frères est ordonnée suivant l'ordre alphabétique (en particulier, on utilise le caractère # comme marqueur de fin de mot ; ce marqueur est inférieur à la lettre A). 
typedef struct ELEM {
  char        lettre ;              
  struct ELEM *frere, *fils ; 
} elem_t, *dico_t ;
Par exemple, le dictionnaire constitué des mots ARBRE, BAC, BAL, BOL, BON et BONNE est représenté par la structure

Écrire les fonctions suivantes :
  1. int nbnoeuds (dico_t d) ; retourne le nombre de noeuds présents dans un dictionnaire.

  2. int nbmots (dico_t d) ; retourne le nombre de mots présents dans un dictionnaire.

  3. int present (dico_t d, char *mot) ; retourne VRAI si le mot passé en paramètre est présent dans le dictionnaire.

  4. dico_t insert (dico_t d, char *mot) ; insère un mot dans le dictionaire.

  5. void print (dico_t d) ; affiche sur la sortie standard tous les mots du dictionnaire (dans l'ordre alphabétique).

  6. dico_t delete (dico_t d, char *mot) ; supprime un mot du dictionnaire.

  7. On se propose maintenant de jouer au mot le plus long à l'aide d'une telle structure. Écrire la fonction char *lepluslong (dico_t d, char *tirage) ; qui retourne le mot le plus long du dictionnaire pour un tirage de lettres donné.

  8. int maxlong (dico_t d) ; retourne la longueur du plus long mot du dictionnaire.

  9. void ecrireWildCard (dico_t d, char *format) ; produit sur stdout tous les mots du dictionnaire qui verifient le format passé en paramètre. Ce format est un mot qui peut comporter un (ou plus) caractère '?'. Ce caractère remplace une et une seule lettre.
Ce document a été traduit de LATEX par HEVEA.