Corrigé 33.  Enoncé

1. Vecteurs de listes linéaires chaînées

Structures de données

    VAR Tab : TABLEAU[1..N] DE POINTEUR(Tmaillon)
    TYPE Tmaillon = STRUCTURE
        Val : CAR
        Adr : POINTEUR(Tmaillon)
    FIN
   
Module Premier(L, X) ---> Prem, Prec

    Prem := L
    Prec := NIL
    Trouv := FAUX
    TANTQUE Prem # NIL ET NON Trouv :
        SI Valeur(Prem) = X : Trouv := VRAI
        SINON Prec := Prem; Prem := Suivant(Prem) FSI
    FINTANTQUE


Module Creer (C, I, L) ---> Tete, Queue

    Tete := NIL
    POUR K:= I, I+L-1
        Allouer(M, Tmaillon)
        Aff_Val(M, C[K])
        SI Tete=NIL : Tete := M
        SINON Aff_Adr(P, M) FSI
        P := M
    FINPOUR
    Aff_Adr(M, NIL)
    Queue := M


Module RECH( C, L, Tete) ---> Trouv, P, Q

    Premier(Tete, C[1], Prem, Prec)
    { Si C[1] n'existe pas Prem est NIL }
    P := Prec
    Trouv := FAUX
    TANTQUE NON Trouv ET Prem # NIL :
        Compare (C,L, Prem, Exist, Q)
        SI Exist
            Trouv := VRAI
        SINON
            Premier(Suivant(Prem), C[1], Prem, Prec)
            P := Prec
        FINSI
    FINTANTQUE

Le module Compare(C, L, Prem, Exist, Q) recherche une chaîne de caractères C de longueur L dans la liste de tête Prem. Si cette chaîne existe, Exist prend la valeur VRAI et Q est l'adresse du dernier caractère de la chaîne dans cette liste.

Il est défini comme suit :
    I := 1
    Arret := FAUX
    TANTQUE Prem # NIL ET I <= L ET NON Arret :
        SI Valeur(Prem) # C[I] :
            Arret := VRAI
        SINON
            I := I + 1
            Q := Prem
            Prem := Suivant(Prem)
        FSI
    FINTANTQUE
    Exist := ( I > L)


Algorithme de substitution

Soit Nc le nombre courant d'élements dans la table Tab.

    POUR K=1, Nc :
        Rech(C1, L1, Tab[K]) ---> Trouv, P, Q
        SI Trouv :
            Prem := Suivant(P)
            I := 1
            TANTQUE Prem # Suivant(Q)ET I <= L2 :
                Aff_Val(Prem, C2[I])
                Prec := Prem
                Prem := Suivant(Prem) ; I := I + 1
            FINTANTQUE
   
            SI Prem # Suivant(Q) { L2 < L1}
                Aff_Adr( Prec, Suivant(Q) )
                { Libérer les maillons restants à partir de Prem }
                TANTQUE Prem # Suivant(Q) :
                    Sauv := Prem
                    Prem := Suivant(Sauv)
                    Libérer( Sauv)           
                FINTANTQUE
            SINON
                SI L2 > L1 :
                    Creer( C2, L1+1, L2-L1, T1, Q1)
                    Aff_Adr(Q1, Suivant(Q); Aff_Adr(Q, T1)
                FSI
            FSI
        SINON " Substitution impossible " FSI
    FINPOUR