Université Bordeaux 1

Licence Semestre 3  - Algorithmes et structures de données 1

Dernière mise à jour effectuée le 23 Juin 2014


Dictionnaire


  1. Définition
  2. 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.

  3. Opérations d'ajout et suppression
  4. 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 : 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 : Un exemple est ici
    Pour supprimer un mot M dans un dictionnaire : Un exemple est ici