Corrigé 14.  Enoncé

1. Système de gestion d'affectations de chaînes de caractères

Description

    TYPE Type_élément = STRUCTURE
        Nom : CAR
        Adresse : Type_adresse
        Longueur : ENTIER
    FIN
    TYPE Type_adresse = STRUCTURE
        Adr : POINTEUR (Type_maillon)
        Depl : ENTIER
    FIN
    TYPE Type_maillon = STRUCTURE
        Tab : TABLEAU(1..M] DE CAR
        Suiv : POINTEUR(Type_maillon)
    FIN
    VAR Tchaîne : Tableau[1..N] DE Type_élément

Initialisation

Soit N_variable le nombre d'éléments dans Tchaîne, W l'adresse du dernier maillon créé et D la première position libre dans ce maillon.

    N_variable := 0
    Allouer (W, Type_maillon)
    Aff_Adr(W, NIL)
    Têtelist := W
    D := 1

Recherche d'une variable de nom X donné : recherche (X, Trouv, I)

    I := 1 ; Trouv := FAUX
    TANTQUE I <= N_variable ET NON Trouv :
        SI Tchaîne(I).Nom >= X :
            Trouv := VRAI
        SINON
            I := I + 1
        FSI
    FINTANTQUE
    Trouv := ( Tchaîne(I).Nom = X )

Récupération du contenu d'une variable de nom X donné: Recupere(X, Y)

    Recherche(X, Trouv, I)
    SI Trouv :
        {Récupérer l'adresse du maillon contenant la chaîne dans P , l'indice du  début dans J et la longueur dans L }
        V := Tchaine(I).Adresse
        P := V.Adr
        J := V.Depl
        L := Tchaine(I).Longueur
        Tab := Valeur(P)
        Ind := 0:
        TANTQUE L > ( M - J + 1 ) :
            POUR K = J, M :
                Ind := Ind + 1
                Y(Ind) := Tab(K)
            FINPOUR
            P := Suivant(P)
            Tab := Valeur(P)
            L := L - ( M - J + 1)
            J := 1
        FINTANTQUE
        POUR K := J, J + L - 1 :
            Ind := Ind + 1
            Y(Ind) := Tab(K)
        FINPOUR
    SINON " X n'existe pas " FSI

Insertion d'une chaîne Y de caractères de longueur L dans le maillon d'adresse W à partir de la position D: Insère (Y, L, W, D, W', D')

    Tab := Valeur(W)
    I := 1
    TANTQUE L > ( M - D + 1 ) :
        POUR K = D, M :
            Tab(D) := Y(I)
            I := I + 1
        FINPOUR
        Aff_Val(W, Tab)
        Allouer( Q, Typemaillon)
        Aff_Adr(W, Q)
        Aff_Adr(Q, NIL)
        L := L - ( M - D + 1 )
        W := Q
        D := 1
    FINTANTQUE
    POUR K := D, D + L - 1 :
        Tab(K) := Y(I)
        I := I + 1
    FINPOUR
    Aff_Val(W, Tab)
    D := D + L
    W' := W ; D' := D

Réalisation d'une affectation

Soit W le dernier maillon alloué et D le premier emplacement libre dans ce maillon. La variable Cumul comptabilise l'espace devenu inaccessible.

    Recherche(X, Trouv, I) :
    SI NON Trouv :
        { Cas o� X n'existe pas }
        Insère (Y, Long(Y), W, D, W', D')
        W := W' ; D := D'
        SI N_variable < N { N étant le nombre maximal de variables }
            POUR J = N_variable, I, -1 :
                Tchaîne(J+1) := Tchaîne(J)
            FINPOUR
            Tchaîne(I).Nom := X
            Tchaîne(I).Adresse := (W, D)
            Tchaîne(I).Longueur := Long(Y)
            N_variable := N_variable + 1
        SINON " Saturation " FSI
    SINON
        { Cas o� X existe }
       
        V := Tchaîne(I).Adresse
        P := V.Adr
        J := V.Depl
        L := Tchaîne(I).Longueur

        SI Long(Y) > L :
            Tchaîne(I).Adresse := (W, D)
            Tchaîne(I).Longueur := Long(Y)
            { Insertion à la fin }
            Insère (Y, Long(Y), W, D, W', D')
            W := W' ; D := D'
            Cumul := Cumul + L
        SINON
            Tchaîne(I).Longueur := Long(Y)
            { Recopier à la même place}
            Insère (Y, Long(Y), P, J, W', D')
            Cumul := Cumul + ( L - Long(Y) )
        FSI
    FSI

Réorganisation

Le module de réorganisation consiste à créer une autre liste linéaire chaînée.
    Sauv := Têtelist
    Allouer(W, Type_maillon)
    Têtelist := W
    Aff_Adr(W, NIL)
    D := 1
    POUR I = 1, N_variable :
        Recupère ( Tchaîne(I).Nom, Y)
        Insère(Y, Long(Y), W, D, W', D')
        Tchaîne(I).Adresse := (W, D)
        W := W' ; D := D'
    FINPOUR
    { Libération de l'espace occupé par l'ancienne liste }
    TANTQUE Sauv # NIL :
        S := Sauv
        Libérer(Sauv)
        S auv := Suivant (S)
    FINTANTQUE

Il faut rajouter dans le module d'affectation le calcul de � et l'appel au module de réorganisation si ce taux devient inférieur au seuil donné.