Problème : Système de gestion d'affectations de chaînes de caractères

Pour réaliser des affectations sur des variables chaînes de caractères, on décide de ranger les contenus de ces dernières dans une liste linéaire chaînée o� chaque élément est un tableau de N caractères. En plus, pour pouvoir accéder directement à une variable, on maintient une table Tchaîne, triée selon le nom, o� chaque entrée est le triplet (Nom, Adresse, Longueur) avec :

- Nom : nom de la variable

- Adresse : coupe(A, J) avec A l'adresse du maillon o� commence la chaîne et J l'indice du début de la chaîne dans le tableau contenu dans ce maillon.

- Longueur : longueur de la chaîne.

NB. * Une chaîne de caractères est assimilée à un tableau de caractères.

* La fonction Long(Y) donne la longueur de la chaîne contenue dans le tableau Y.

Dans l'exemple suivant, on obtient la configuration suivante après les affectations suivantes, faites dans cet ordre :

b <--- 'abcd' ; a <---'ecb' ; d <--- 'efg' ;

c <--- 'ijklmn

B étant égal à 5.

Description : Décrire le schéma ci-dessus.

Initialisation :

Définir les paramètres nécessaires à l'écriture des opérations qui suivent et dire comment les initialiser.

Consultation :

Ecrire le module Recherche (X, Trouv, I) qui recherche la variable X dans Tchaîne. Si X et trouvée, le module rend dans Trouv la valeur VRAI et dans I le rang de cette variable dans Tchaîne.

Ecrire le module Récupère(X , Y) qui récupère dans Y le contenu de la variable de nom X donné.

Mises à jour :

Ecrire le module Insère (Y, L, W, D, W', D') qui insère la chaîne de caractères Y de longueur L dans le maillon W à partir de la position D. Dans le cas o� le maillon W ne suffit pas, ce module rend dans W' le maillon o� finit la chaîne et dans D' la première position libre dans ce maillon.

Utiliser le module Insère pour écrire le module Affect(X, Y) qui réalise l'affectation :

X <--- Y,

pour X une variable donnée et Y une constante chaîne de caractères donnée. On peut avoir les deux cas suivants :

X n'existe pas : dans ce cas, X est rajoutée dans la table Tchaîne à sa bonne position et Y est rajoutée en fin de liste.

X existe : si Y peut être contenu dans l'ancienne valeur de X , elle est recopiée sinon elle est rajoutée en fin de liste. Dans les deux cas, on comptabilise l'espace (en nombre de caractères) devenu inaccessible.

Réorganisation :

Soit � = nombre de caractères utilisés / nombre total de caractères alloués. Après réalisation de chaque affectation, on calcule �. Si ce dernier devient inférieur à un seuil S donné, on lance le module de réorganisation qui consiste à récupérer tous les "trous" créés.

Que faut-il rajouter dans le module Affect ?

Ecrire le module de réorganisation.