TD62 MIC

guillerm@laas.fr

Romaric GUILLERM

Algo-Progen Ada

TD6 – Arbres n-aires Représentation d’un dictionnaire

Les mots d’un dictionnaire D peuvent être mémorisés sur les branches d’un arbre n-aire de la façon suivante :

chaque nœud comporte un tableau de 26 pointeurs et un booléen

le tableau contenu dans un nœud est indicé par une lettre (entre ‘a’ et ‘z’) et chaque case du tableau contient un pointeur sur un nœud fils dans l’arbre.

le booléen d’un nœud indique si le mot construit par concaténation des indices des pointeurs sur la branche issue de la racine jusqu’à ce nœud forme un mot qui fait partie de D.

le booléen associé à la racine est toujours faux (il n’y a pas de mot vide «»).

initialement la racine est un nœud dont tous les pointeurs sont nuls.

TD6

Question 1 : Quelle serait la figure correspondant à un dictionnaire qui ne comporte que le mot «au» ?

false

Réponse à la question 1

TD6 Question 2 : Définir les structures de données concrètes qui permettent de

modéliser un dictionnaire.

TD6 Question 3 : Ecrire une procédure qui initialise un dictionnaire vide.

Le booléen associé à la racine est toujours faux (il n’y a pas de mot vide «»).

Initialement la racine est un nœud dont tous les pointeurs sont nuls. 

TD6 Question Bonus 1 :

Procédure pour vider un dictionnaire en libérant la mémoire :

TD6 Question Bonus 2 :

Procédure pour afficher tous les mots d’un dictionnaire :

TD6 Question 4 : Ecrire une fonction qui détermine l’appartenance d’un mot à un

dictionnaire.

TD6 Question 5 : Ecrire un sous-programme permettant d’insérer un nouveau mot dans

un dictionnaire.