Corrigé 37  Enoncé

1. Essai linéaire avec tableaux dynamiques

Structure de la table principale
    TYPE typeelement1 = STRUCTURE
        Adresse : Pointeur ( Typeelement2)
        Taille : Entier
        Nombre : Entier
    FIN
    Var T : Tableau [1..N] de Typeelement

Structure des tables dynamiques secondaires

    TYPE typeelement2 = Pointeur ( Tableaudynamique)
    TYPE tableaudynamique = Tableau [1..M] de S
    TYPE S = STRUCTURE
        Valeur : Entier
        Occupé : Booleen
    FIN
   
Initialisation

POUR i : =1, N : T(i).Adresse : = NIL FINPOUR

Recherche

    I := f(d)
    SI T(i).adresse = Nil :    
        Ecrire(FAUX)
    SINON    
        Rech( T(i).adresse, T(i).taille, d, trouv) Ecrire( Trouv )
    FSI

Insertion

    I := F(d)
    SI T(i).adresse = Nil
        Allouer ( Adr, M)
        T(i).adresse : = Adr ;   T(i) .Taille : = M     ;   T(i).Nombre := 1
        Insert( Adr, M, d)
    SINON
        SI T(i).Nombre / T(i).Taille < Mu

            Insert( T(i).adresse, T(i).Taille, d)
        SINON
            Allouer ( Adr', T(i).Taille * 2 )
            POUR j :=1, T(i).Taille
                Couple := Element(T(i).adresse, j )
                SI Couple.Occupé
                    Inser( Adr', T(i).taille*2, d)
                FSI   
            FINPOUR
            Insert( Adr', T(i).Taille*2, d)
            Liberer ( T(i).adresse)
            T(i).adresse : = Adr'   ;   T(i).taille := T(i).taille * 2
            T(i).Nombre : = T(i).Nombre + 1
        FSI
    FSI       

Suppression

    I : = f(d)
    SI T(i).adresse = nil
        ecrire( 'élément inexistant')
    SINON
        Sup(T(i).adresse, T(i).taille, d)
        SI T(i).Nombre / T(i).Taille < Mu'  et (T(i).taille <> M)
            Allouer ( Adr', T(i).Taille / 2 )
            POUR j :=1, T(i).Taille
                Couple := Element(T(i).adresse, j )
                SI Couple.occupé
                    Inser( Adr', T(i).taille/2, d)
                FSI
            FINPOUR
            Liberer ( T(i).adresse)
            T(i).adresse : = Adr'     ;   T(i).taille := T(i).taille / 2
            T(i).Nombre : = T(i).Nombre - 1
            SI T(i).Nombre = 0
                Liberer ( T(i).adresse)
                T(i).adresse := Nil
            FSI
        FSI
    FSI

Structure du fichier

Méthode d'accès : tableau non ordonné
Organisation : Format fixe des articles. 1 article = donnée entière
TYPE Typebloc = STRUCTURE
        Nb : entier
        Tab : tableau [1..B] de ENTIER
FIN
F : Fichier de Typebloc

Sauvegarde

    Ind := 0 Buffer.Nb := 0
    POUR i : = 1, N
        POUR j :=1, T(i).Taille
            Couple := Element(T(i).adresse, j )
            SI.Couple.Occupé
                Ind : = ind + 1
                SI ind <= B :
                    Buffer.Tab(ind) := Couple.Valeur
                    Buffer.nb := Buffer.nb + 1
                SINON
                    Ecrire(F, Buffer)
                    Buffer.Tab(1) := Couple.Valeur
                    Buffer.Nb := 1
                    ind := 1
                FSI
            FSI
        FINPOUR
    FINPOUR
    { Ecriture dernier bloc }
    SI ind <> B + 1 : Ecrire( F, Buffer) FSI