Enoncé 33. Listes linéaires chaînées Corrigé 33

Problème : Vecteur de listes linéaires chaînées

On dispose d ’un vecteur de listes linéaires chaînées (LLC).

Chaque LLC contient un mot de longueur quelconque à raison d’un caractère par maillon.

1- Définir les structures de données.

2 Ecrire le module PREMIER (L, x, Prem, Prec) qui retourne

- dans Prem l’adresse du premier maillon de la LLC L contenant un caractère donné x s’il existe,

- dans Prec l’adresse de son précédent.

3. Ecrire le module CREER(C, I, L, T, Q) qui crée une LLC de tête T et de queue Q à partir d’une sous-chaîne de C de longueur L commençant à la position I.

4- Utiliser le module PREMIER pour écrire le module de recherche RECH(C, L, Tete,Trouv, P, Q) d’une chaîne donnée C de longueur L dans une LLC Tete. Le module rend comme résultats une valeur booléenne Trouv indiquant l’existence de la chaîne C et les pointeurs P et Q définis comme suit :

- P pointe le précédent du premier élément de la chaîne C

- Q le dernier élément de la chaîne C.

5- Utiliser le module RECH et CREER pour écrire l’algorithme qui remplace une chaîne donnée C1 de longueur L1, si elle existe, par une autre chaîne C2 de longueur L2 dans tous les mots du vecteur. Le remplacement s’effectue sur les maillons déjà existants. En

d’autres termes, il y a allocation de nouveaux maillons que si L2 > L1.

NB:

1. Un mot est une suite de caractères non blancs

2. Une chaîne est assimilée à un vecteur de caractères.