Corrigé 35 Enoncé

1. Liste de vecteurs/listes

1. Structure de données

TYPE Tmaillon = STRUCTURE
    Val : Typevaleur
    Suiv : Pointeur (Tmaillon)
FIN
Typevaleur = STRUCTURE
    Nb : entier
    Tab : Tableau[1..max] de car
FIN

Var
Liste : Pointeur (Tmaillon)

2. Création de la liste

Lire(N)
P := Nil
POUR i :=1, N
    Lire(Mot)
    V.tab := Mot
    V.Nb := Long(Mot)
    Allouer (Q, Tmaillon)
    Aff_val(Q, V)
    SI P <> Nil
        Aff_adr( P, Q)
    SINON
        Tete := Q
    FSI
    P := Q
FINPOUR
Aff_adr(P, Nil)


3. Module Rech(C, L, V, Nb, Trouv, Ind )

I := 1
Trouv := FAUX
Continue1 := VRAI
TANTQUE I <= Nb et Continue1
    {Rechercher le premier caractère de C dans V }
    Trouver := FAUX
    TANTQUE I <= Nb et NON Trouver
        SI V(i) = C(1)
            Trouver := VRAI
        SINON
            I := I + 1
        FSI
    FINTANTQUE
    SI Trouver
        {Sauvegarde de l'indice du premier caractère de C dans V}
        Ind := I
        {Vérifie SI C est incluse dans V }
        I := I + 1
        J := 2
        Continue2 := VRAI
        TANTQUE i <= Nb et J <= L et Continue2
            SI V(i) <> C(J)
                Continue2 := FAUX
            SINON
                I := I + 1
                J := J + 1
            FSI
        FINTANTQUE
        SI Continue2 et J > L
            Trouv := VRAI
        FSI
    FSI
FINTANTQUE

4. Remplacement de la chaîne C1 de longueur L1 par la chaîne C2 de longueur L2 dans tous les mots de la liste.

P := Tete
TANTQUE P <> Nil
    V := Valeur(p)
    Rech(C1, L1, V.tab , V.nb, Trouv, Ind)
    SI trouv
        SI L2 <= L1
            K := 0
            POUR I := Ind, Ind+L2-1
                K := K + 1     V(I) := C2(K)
            FINPOUR
            SI L2 - L1 > 0
                POUR I := Ind + L1, V.Nb
                    V(I- (L2-L1) := V(I)
                FINPOUR
                V.Nb := V.Nb - (L2-L1)
            SINON {L2 > L1 }
                SI (Max - V.Nb) > (L2-L1)
                    POUR I :=V.nb, Ind +L1, -1
                        V(I+L2-L1) := V(I)
                    FINPOUR
            K := 0
                    POUR I := Ind, Ind+L2-1
                        K := K +1
                        V(I) := C2(K)
                    FINPOUR
                    V.Nb := V.Nb + (L2-L1)
                SINON
                    'Remplacement impossible'
                FSI
            FSI
            Aff_val(P, V)
        FSI
        P := Suivant(P)
    FINTANTQUE

5. Structures de données

TYPE Tmaillon1 := STRUCTURE
    Val : Pointeur(Tmaillon2)
    Suiv : Pointeur(Tmaillon1)
FIN
TYPE Tmaillon2 := STRUCTURE
    Val : Car
    Suiv : Pointeur(Tmaillon2)
FIN
Var
    Liste : Pointeur(Tmaillon1)

6. Seuil

Première représentation :
    N ( Max + 2 {Pointeur} + 1 {Longueur du mot } ) --> N.Max + 3N = N(Max + 3)

Deuxième représentation :
Liste principale : N (2+2) --> 4N
Listes secondaires : N(Max/2 ( 2{pointeur} + 1 {Caractère}) --> N. Max/2 .3


La première représentation occupe plus de place si :
N(Max + 3) >= N. (Max/2).3
c'est à dire 2N.Max + 6N >= 3N.Max
ou encore 6N >= N.Max
et donc Max <= 6

Pour une taille de vecteur supérieure à 6, il est avantageux de considérer la deuxième représentation.