Corrigé 13. Enoncé

1. Essai linéaire avec effacement logique des données

Etat du tableau après insertion et après suppression

Les champs Occ et Eff sont initialisés à FAUX (f).

Recherche/insertion d'un élément E dans le cas oł on ne récupère pas les emplacements des données effacées

Dans les algorithmes qui suivent, N est une variable globale qui désigne le nombre d'éléments dans le vecteur.

    I := H(E) { H désigne la fonction de hachage }
    Trouv, Vide := FAUX
    TANTQUE NON Trouv ET NON Vide :
        SI NON Eff(I) :
            SI Occ(I) :
                SI Val(I) = E
                    Trouv := VRAI
                SINON
                    I:=I-1;SI I<0 : I:=I+M FSI
                FSI
            SINON
                Vide := VRAI
        SINON
            I:=I-1;SI I<0 : I:=I+M FSI
        FSI
    FINTANTQUE
    SI NON Trouv :
        SI N = M-1 :
            " Débordement"
        SINON
            N := N + 1
            Aff_Val(I, E)
            Aff_Occ(I, VRAI)
        FSI
    SINON
        " E existe"
    FSI

Recherche/insertion d'un élément E dans le cas oł on récupère les emplacements des données effacées.

    I := H(E)
    Trouv, Vide, Effacé := FAUX
    TANTQUE NON Trouv ET NON Vide :
        SI NON Eff(I) :
            SI Occ(I) :
                SI Val(I) = E
                    Trouv := VRAI
                SINON
                    I:=I-1;SI I<0 : I:=I+M FSI
                FSI
            SINON
                Vide := VRAI
            FSI
        SINON
            SI NON Effacé :
                K := I
                Effacé := VRAI
            FSI
        FSI
    FINTANTQUE

    SI NON Trouv :
        { Sauvegarde de la première entrée rencontrée effacée }
        SI Effacé :
            Aff_Val(K,E)
            Aff_Eff(K, FAUX)
        SINON
            SI N = M-1 :
                " Débordement"
            SINON
                N := N + 1
                Aff_Val(I, E)
                Aff_Occ(I, VRAI)
            FSI
    SINON
        " E existe"
    FSI


Algorithme de réorganisation (suppression physique des emplacements des données effacées ).

    Continue := VRAI
    TANTQUE Continue :
        Effacé := FAUX
        I := 0
        TANTQUE I <= M-1 ET NON Effacé :
            SI Eff(I) : Effacé := VRAI
            SINON I := I + 1 FSI
        FINTANTQUE
        SI Effacé : Supprimer(I)
        SINON Continue := FAUX FSI
    FINTANTQUE

Le module Supprimer est le suivant :

    Continue := VRAI
    TANTQUE Continue :
        Aff_Eff(I, FAUX)
        Aff_Occ(I, FAUX)
        N := N - 1

        J := I
        I:=I-1;SI I<0 : I:=I+M FSI
        Vide, Cond := FAUX
        TANTQUE NON Cond ET NON Vide :
            SI NON Eff(I) :
                SI NON Occ(I) :
                    Vide := VRAI
                SINON
                    R := H( Val(I) )
                    SI J > I :
                        Test := R < I OU R >= J
                    SINON Test := J <= R < I FSI
                    SI Test : Cond := VRAI
                    SINON
                        I:=I-1;SI I<0 :I:=I+M FSI
                    FSI
                FSI
            SINON
                I:=I-1;SI I<0 : I:=I+M
            FSI
        FINTANTQUE
        SI Vide : Continue := FAUX
        SINON Aff_Val(J, Val(I) ) FSI
    FINTANTQUE


Etat du tableau après cette réorganisation

Les champs Eff et Occ ont la valeur FAUX.