Université Bordeaux 1

Dictionnaire

---

• Définition
• Opérations d'ajout et suppression

Définition

Un dictionnaire est une structure de donnée permettant de stocker des mots. Dans ce cours, on considère que le mot est stocké dans une variable de type "mot" dont on peut connaitre la longueur par la fonction "longueur".

fonction longueur(ref m:mot):entier;

Si M est un mot, M[i] est le ième caractère de M.
Un dictionnaire est donc un containeur dont les primitives sont les suivantes.
• accès

  fonction appartient((ref d:dictionnaire,val M::mot):booléen;
  

• modification

  fonction creerDictionnaire(ref d: dictionnaire):vide
  fonction ajouter(ref d:dictionnaire,val M::mot):vide;
  fonction supprimer(ref d:dictionnaire,val M:mot):vide;
  fonction detruireDictionnaire(ref d:dictionnaire):vide;
  

Opérations d'ajout et suppression

On considère que l'implémentation se fait dans le type arbreBinaire. On munit le dictionnaire d'un curseur de façon à ne pas passer ou déclarer un pointeur à chaque appel.

type dico=structure
            a:sommet; /* l'arbre*/
            p:sommet; :* le curseur */
          finstructure

L'implémentation peut également être faite dans le type arbrePlanaire mais dans ce cas les factorisations qui permettent une optimisation de l'arbre sont moins efficaces. Le principe est le suivant :
• Descendre sur le fils gauche correspond à passer à la lettre suivante dans un mot,
• Descendre sur le fils droit correspond à passer à une autre lettre en même position.
Tous les mots se terminent par un même caractère que nous noteron "\0" et qui est stocké dans l'arbre. Pour ajouter un mot M dans un dictionnaire :
• on recherche le plus long préfixe du mot M contenu dans l'arbre à partir de la racine, on détermine ainsi un sommet S de l'arbre correspondant au I premières lettres du mot.
• On parcours à partir de S la branche droite de l'arbre de manière à trouver deux sommets tels que
  • S2==filsDroit(S1),
  • valeur(S1)<valeur(S2)
• On crée un arbre "baguette" (tous les fils droits sont vide) B étiquetté par toutes lettres de M à partir du (i+1)ème caractère.
• on insère B entre les sommets S1 et S2 dans l'arbre
Un exemple est ici
Pour supprimer un mot M dans un dictionnaire :
• on recherche la feuille correspondante au mot, elle se trouve au bout d'un arbre "baguette" B,
• on détruit l'arbre B.
Un exemple est ici