Enoncé 15 : Listes linéaires chaînées - Arbres - Piles  Corrigé 15

On désire ranger des chaînes de caractères(cc) dans un arbre de recherche binaire (arb) en vue de réaliser certains traitements. Chaque cc est représentée sous la forme d'une liste linéaire chaînée(llc) o� chaque maillon renferme un caractère de la chaîne. Par conséquent, on a un arb de llc.

Ecrire le modules :

a)- CréerList( C, L) qui consiste à créer la llc L à partir de la cc C.

b)- CréerChaîne(L, C) qui consiste à reconstituer la cc C à partir de la llc L.

Utiliser ces modules pour développer les algorithmes suivants :

c)- Ecrire le module non récursif qui recherche une cc donnée C dans un tel arbre. Puis utilisez-le pour écrire l'algorithme qui insère C si elle n'existe pas.

d)- Ecrire l'algorithme récursif qui imprime toutes les cc contenues dans l'arb en ordre croissant.

e)- Ecrire l'algorithme récursif qui détermine le pourcentage d'octets utilisés par rapport à l'encombrement mémoire total sachant qu'un pointeur occupe 2 octets.

f)- Que contient la pile au moment de la visite d'un nœud en "inordre" ?

g)- Que faut-il rajouter dans le module de recherche pour avoir un tel contenu ?

h)- Utiliser cette pile et le module de recherche pour écrire l'algorithme qui imprime toutes les cc commençant par un caractère C donné.

NB. - Une cc est assimilée à un vecteur.

- L'ensemble des cc est muni d'une relation d'ordre notée <.

- Long(C) donne le nombre de caractères de la cc C.

Les algorithmes doivent être indépendants de la représentation mémoire de l'arb et de la llc.

* * * * *