Corrigé 10. Enoncé

1. Méthodes d'index

Structures des tables : Index primaire à un niveau

    TYPE T1 = STRUCTURE
        Clé : Typeclé
        Adr : Typeadresse
    FIN
    VAR T : TABLEAU (1..N) DE T1

Structures des tables : Index primaire à deux niveaux

    TYPE T1 = STRUCTURE
        Clé : Typeclé
        Adr1 : ENTIER
    FIN

    TYPE T2 = STRUCTURE
        Clé : Typeclé
        Adr2 : Typeadresse
    FIN
    VAR Tniv1 : TABLEAU (1..N1) DE T1 { Index de niveau 1 }
    VAR Tniv2 : TABLEAU (1..N2) DE T2 { Index de niveau 2 }


Structures des tables : Index secondaire sous forme de listes inversées

    TYPE T1 = STRUCTURE
        Clésec : Typeclé
        Adr1 : ENTIER
    FIN
    TYPE T2 = STRUCTURE
        Cléprim : Typeclé
        Adr2 : ENTIER
    FIN
    TYPE T3 = STRUCTURE
        Cléprim : Typeclé
        Adr : Typeadresse
    FIN
    { Tab1 et Tab2 constitue l' index secondaire }
    VAR Tab1 : TABLEAU (1..N1) DE T1
    VAR Tab2 : TABLEAU (1..N2) DE T2
    VAR Tab3 : TABLEAU (1..N3) DE T3 { Index primaire }

Typeadresse est formé d'un numéro de bloc et d'un déplacement dans le bloc.

Modules nécessaires pour réaliser une insertion d'articles pour les méthodes (a), (b) et (c).

Dans l'index primaire à un niveau :

(a) Recherche(Clé, T, Trouv, I) : recherche la clé Clé dans T. Si elle est trouvée, I est son indice sinon c'est la position après laquelle on insère.

(b) Insérer(Clé, T, I) : insérer la clé Clé dans T à la position I.

Dans l'index primaire à deux niveaux :

Modules (a) et (b) +
(c) Recherche(Clé, T, I, J) : recherche la clé Clé dans T (index primaire du premier niveau). Le résultat est l'intervalle [I, J].

Dans l'index secondaire sous forme de listes inversées :

Modules (a) et (b) +
(d) Rechlist(Clé, T, I, Trouv) : recherche la clé Clé dans la liste I contenue dans T. Trouv est donc positionnée à VRAI si elle existe, FAUX sinon.
(e) Inserlist(I, T, Clé) : insérer la clé Clé dans la liste I contenue dans T.

2. Hachage externe.

(a) Taux de chargement bas.
(b) Les débordements de tous les blocs primaires sont dans une même liste linéaire chaînée (llc) de blocs. Ainsi, on aura plusieurs llcs statiques d'articles dans une llc dynamique de blocs.
(c) Description

    { Fichier des blocs primaires }
    TYPE Typeblocprimaire = STRUCTURE
        Nb : ENTIER
        T : TABLEAU(1..B) DE Typearticle
        Lien : Typeadresse
    FIN
    TYPE Typeadresse = STRUCTURE
        Numbloc : POINTEUR(Typeblocsecondaire)
        Tête : ENTIER
    FIN
   
    { Fichier des blocs secondaires }
    TYPE Typeblocsecondaire = STRUCTURE
        Tab : TABLEAU(1..N) DE Typemaillon
        Suiv : POINTEUR(Typeblocsecondaire)
    FIN
    TYPE Typedumaillon = STRUCTURE
        Article : Typearticle
        Adr : Typeadrese
    FIN

On a ainsi plusieurs listes linéaires chaînées dans un même fichier.
Typearticle contient au moins la clé.

Nombre maximal de buffers utilisés

    (a) : 2
    (b) : 2
    (c) : 1


3. Une méthode d'accès à un fichier de caractères(UNIX)

Le fichier est une liste linéaire chaînée bidirectionnelle de blocs. Le premier bloc étant spécial, il n'est pas chaîné avec les autres blocs.

Structure de données

    TYPE Typebloc = STRUCTURE
        Lieng, Liend : POINTEUR(Typebloc)
        T : TABLEAU(1..1024) DE CAR
    FIN
    VAR Buffer : Typebloc
    Table : TABLEAU(1..Limit) DE POINTEUR(Typebloc)

Chargement de la table

Dans l'algorithme qui suit, l'opération Cat désigne la concaténation.

    { Lecture du bloc 0 contenant les caractéristiques du fichier et la table }
    Lirebloc(F, 0, Buffer)
    { Récuperer la position libre dans le dernier bloc }
    C := ''
    POUR I=1, 4 : C := C Cat Buffer.T(I) FINPOUR
    Convert(C, Poslibre)
    { Récupérer le nombre de blocs }
    C := Buffer.T(5) Cat Buffer.T(6)
    Convert(C, Nbrbloc)
    {Charger la table}
    K := 7
    Ind := 0
    POUR I=1, Nbrbloc
            C := ''
            POUR J=K, K+3 : C := C Cat Buffer.T(J) FINPOUR
            Ind := Ind + 1
            Convert(C, Table(Ind))
             K := K + 4
    FINPOUR

Pour les modules qui suivent, on considère que la table Table, les variables Poslibre et Nbrbloc sont en mémoire.

Récupération du N-ième caractère (N donnée)

    { Déterminer le bloc concerné s'il existe }
    Numbloc := N DIV 1024
    P := N Mod 1024
    SI P#0 : Numbloc := Numbloc + 1 FSI
    SI Numbloc > Nbrbloc :
        "Position Inexistante"
    SINON
        Lirebloc(F, Table(Numbloc), Buffer)
        Ecrire( Buffer.T(P))
    FSI

Ajout de caractères

    SI Nbrbloc = 0
        Buffer.T(1) := C
        Buffer.Lieng, Buffer.Liend := NIL
        Poslibre:= 2
        I := Demandebloc(Typebloc)
        Ecrirebloc(F, I, Buffer)
        Nbrbloc := Nbrbloc + 1
        SI Nbrbloc <= Limit :
            Table(Nbrbloc) := I
        SINON
            "Table saturée"
        FSI
    SINON
        SI Poslibre = 1025
            Buffer.Liend := NIL
            Buffer.Lieng := Table(Nbrbloc)
            Buffer.T(1) := C
            Poslibre := 2
            I := Demandebloc (Typebloc)
            Ecrirebloc(F, I, Buffer)
            Nbrbloc := Nbrbloc + 1
            SI Nbrbloc <= Limit :
                Table(Nbrbloc) := I
            SINON " Table saturée" FSI
            { Ramener L'ancien dernier bloc }
            Lirebloc(F, Table(Nbrbloc-1), Buffer)
            Buffer.Liend := I
            Ecrirebloc(F, Table(Nbrbloc-1), Buffer)
        SINON
            { Ramener le dernier bloc}
            Lirebloc(F, Table(Nbrbloc), Buffer)
            Buffer.T(Poslibre) := C
            Poslibre := Poslibre + 1
            Ecrirebloc(F, Table(Nbrbloc), Buffer)
        FSI
    FSI

Récupération des N caractères ( N donnée) qui précèdent un caractère de position Pos donnée

    { Déterminer le bloc concerné s'il existe }
    Numbloc := Pos DIV 1024
    P := Pos Mod 1024
    SI P#0 : Numbloc := Numbloc + 1 FSI
    SI Numbloc > Nbrbloc :
        "Position inexistante
    SINON
        Lirebloc(F, Table(Numbloc), Buffer)
        K := N ; Possible := VRAI
        TANTQUE K > 0 ET Possible :
            Ecrire( Buffer.T(P) )
            K := K - 1;
            P := P - 1;
            SI P = 0 ET K > 0 :
                SI Buffer.Lieng # NIL :
                    Lirebloc(F, Buffer.Lieng,Buffer)
                    P := 1024
                SINON
                    "Fin de fichier rencontré"
                    Possible := FAUX
                FSI
            FSI
        FINTANTQUE
    FSI