PROBLEME : Liste de vecteurs/listes

On désire ranger des mots de longueur variable dans une liste linéaire chaînée en vue de les exploiter. Un maillon de la liste renferme le couple (Mot, Longueur) o� Mot désigne un vecteur de caractères et Longueur la longueur du mot.

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

2. Ecrire le module de création d’une liste linéaire chaînée à partir de n mots lus. Utiliser l'ordre de lecture Lire(Mot) qui lit un mot dans le vecteur de caractères Mot. On utilisera également la fonction Long (Mot) qui donne la longueur d'un mot donné.

3- Ecrire le module Rech(C, L, V, Nombre, Trouv, Ind) qui recherche une chaîne donnée C de longueur L dans le vecteur V contenant un mot de longueur Nombre. Le module rend comme résultats une valeur booléenne Trouv indiquant l'existence de la chaîne C et l'indice Ind du début de celle-ci (si C existe).

4- Utiliser le module Rech 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 de la liste.

5- Au lieu de représenter un mot de la liste par un vecteur, on peut le représenter par une autre liste linéaire chaînée o� chaque maillon représente un caractère du mot. Donner les structures de données appropriées.

6- Montrer que si les tableaux contenant les mots sont remplis en moyenne à 50% (première représentation ) alors, il existe un seuil pour la taille du vecteur pour lequel il n’est pas avantageux de considérer la deuxième représentation ( un pointeur occupe 2 octets et la longueur d’un mot est représentée sur un octet)

* * * * *