Corrigé 3.  Enoncé

1. Hachage ou rangement dispersé dans une table

Structures de données utilisées

Chaque entrée de la table est composée de deux champs :
    - Nb     : nombre courant d'éléments
    - Tab     : les articles

    TYPE Typebloc = STRUCTURE
        Nb     : ENTIER
        Tab     : TABLEAU[1..B] DE Typecle
    FIN

Donc, la table est définie comme suit :

    VAR Table    :     TABLEAU[0..M-1] DE Typebloc

Typecle peut être tout ensemble muni d'une relation d'ordre.


Module de recherche

    H := Hash(Cle) { Hash désigne la fonction de hachage }
    Continue := VRAI
    TANTQUE Continue :
        { Rechercher dans l'entrée H de Table }
        Trouv := FAUX ; I := 1
        TANTQUE NON Trouv ET I <= Table(H).Nb
            SI Table(H).Tab(I) = Cle :
                Trouv := VRAI
            SINON
                I := I + 1
            FSI
        FINTANTQUE
        SI Trouv :
            Continue := FAUX
        SINON
            SI Table(H).Nb < B :
                Continue := FAUX
            SINON
                H := H - 1; SI H < 0 : H:=H+M FSI
            FSI
        FSI
    FINTANTQUE

Module d'insertion

Soient Trouv et H les paramètres donnés par le module de Recherche.

N étant une variable globale contenant à tout moment le nombre d'éléments rangés dans Table.

    SI Trouv :
        "Insertion impossible"
    SINON
        N := N + 1
        SI N = M*B - 1 :
            "Débordement"
        SINON
            Table(H).Nb := Table(H).Nb + 1
            Table(H).Tab(Table(H).Nb) := Cle
        FSI
    FSI

Remarquer que la table est considérée comme pleine quand il reste une seule clé à ranger.

Module de suppression

Soit Trouv, H et I les paramètres donnés par le module Recherche. I est donc l'indice de l'élément à supprimer dans la case H de la table.

    SI Trouv :
        N := N - 1 { Nombre d'éléments dans la table }
        Continue := VRAI
        TANTQUE Continue :
       
            {Supprimer le i-ième élément de l'entrée H de Table}
            SI I # Table(H).Nb : { Déplacer l'article }
                Table(H).Tab(I) := Table(H).Tab(Table(H).Nb)
            FSI
            Table(H).Nb := Table(H).Nb - 1

            Place := ( Table(H).Nb # B-1)
            Cond := FAUX
            J := H
            TANTQUE NON Place ET NON Cond:
                {L'entrée H était pleine}
                H:=H-1;SI H<0 : H:=H+M FSI
           
                K := 1
                TANTQUE K <= Table(H).Nb ET NON Cond :
                    R := Hash( Table(H).Tab(K) )
                    SI J > H :
                        Test := R<H OU R >= J
                    SINON Test := R < H ET R >= J FSI
                    SI Test : Cond := VRAI
                    SINON K := K + 1 FSI
               
                FINTANTQUE
                SI NON Cond ET Table(H).Nb < B :
                    Place := VRAI
                FSI
            FINTANTQUE
            SI Place : Continue := FAUX
            SINON
                Table(J).Tab(B) := Table(H).Tab(K)
                I := K
            FSI
        FINTANTQUE
    SINON " Clé inexistante " FSI


2. Fichiers structurés en tableaux

Description de F :

    TYPE Typebloc = STRUCTURE
        T     : Tableau[1..B] DE Typecle
        Nb     : ENTIER { Nombre d'articles}
    FIN

Typecle peut être tout ensemble muni d'une relation d'ordre.

Module de recherche dichotomique :

Soit Buffer une zone mémoire de type Typebloc.

    { Recherche dichotomique externe }
    Trouv := FAUX
    Bi := 1
    Bs := M { Dernier bloc }
    TANTQUE Bi <= Bs ET NON Trouv :
        Milieu := (Bi+Bs) DIV 2 { Division entière }
        Lirebloc(F, Milieu, Buffer)
        SI Buffer.T(1) <= Cle ET
        Buffer.T(Buffer.Nb) >= Cle :
            Trouv := VRAI
        SINON
            SI Cle < Buffer.T(1):
                Bs := Milieu - 1
            SINON
                Bi := Milieu + 1
            FSI
        FSI
    FINTANTQUE

    { Recherche dichotomique interne }
    SI Trouv :
        Trouv := FAUX
        Binf := 1
        Bsup := Buffer.Nb { Nombre d'éléments }
        TANTQUE Binf <= Bsup ET NON Trouv :
            Mil := (Binf+Bsup) DIV 2
            SI Buffer.T(Mil) = Cle
                Trouv := VRAI
            SINON
                SI Cle < Buffer.T(Mil)
                    Bsup := Mil - 1
                SINON
                    Binf := Mil + 1
                FSI
            FSI
        FINTANTQUE
    SINON
        SI Bs = M
            Binf := Buffer.Nb + 1
        SINON
            Binf := 1
        FSI
    FSI

Remarque : si Trouv est FAUX, Milieu pointe le bloc qui devait contenir la clé recherchée et Binf la position o� elle devrait se trouver dans ce bloc.

Module d'insertion :

Soit Trouv, Milieu et Binf les paramètres donnés par le module de Recherche dans le cas o� la clé à inserer n'existe pas.

    SI NON Trouv :
        SI Buffer.Nb = B:
            {Rechercher un bloc libre dans les blocs I+1,
            I-1,I+2, I-2, . . . }
       
            Inf, Sup := Milieu
            Creerpile(Linf);Empiler(Linf, Buffer.T(1))
            Creerpile(Lsup);Empiler(Lsup, Buffer.T(B) )
       
            Aig, Trouv := FAUX
            S := 0
            TANTQUE NON Trouv ET S < 2 :
                SI Aig :
                    Inf := Inf - 1
                    K := Inf
                SINON
                    Sup := Sup + 1
                    K := Sup
                FSI
                SI 1 <= K <= M
                    Lirebloc(F, K, Buffer)
                    SI Buffer.Nb < B :
                        Trouv := VRAI
                    SINON
                        SI Aig :
                            Empiler(Linf,Buffer.T(1))
                        SINON
                            Empiler(Lsup,Buffer.T(B))
                        FSI
                        Aig := NON Aig
                    FSI
                SINON
                    S := S + 1
                FSI
            FINTANTQUE

            { Décalage }
            SI NON Trouv :
                M := M + 1 { Extension du fichier }
                K := M
                Buffer.Nb := 0
            FSI
            SI K > Milieu :
                {Décalage dans le bloc K }
                POUR J=Buffer.Nb,1, -1 :
                    Buffer.T(J+1) :=Buffer.T(J)
                FINPOUR
                Depiler(Lsup,Elmt)
                Buffer.T(1) := Elmt
                Buffer.NB := Buffer.Nb + 1
                Ecrirebloc(F, K, Buffer)

                POUR I=K-1, Milieu, -1 :
                    Lirebloc(F,I,Buffer)
                    SI I = Milieu :
                        Limit := Binf
                    SINON
                        Limit := 1
                    FSI
                    POUR J=Buffer.Nb - 1 , Limit, -1 :
                        Buffer.T(J+1) :=Buffer.T(J)
                    FINPOUR
                    SI I = Milieu :
                        Buffer.T(Binf) := Cle
                    SINON
                        Depiler(Lsup, Elmt)
                        Buffer.T(1) := Elmt
                    FSI        
                    Ecrirebloc(F, I, Buffer)
                FINPOUR
            SINON
                Depiler(Linf, Elmt)
                Buffer.NB := Buffer.Nb + 1
                Buffer.T(Buffer.Nb) := Elmt
                Ecrirebloc(F, K, Buffer)

                POUR I=K+1, Milieu :
                    Lirebloc(F,I,Buffer)
                    SI I = Milieu :
                        Limit := Binf - 2
                    SINON
                        Limit := Buffer.Nb - 1
                    FSI
                    POUR J=1, Limit:
                        Buffer.T(J):=Buffer.T(J+1)
                    FINPOUR
                    SI I = Milieu :
                        Buffer.T(Binf) := Cle
                    SINON
                        Depiler(Linf, Elmt)
                        Buffer.T(B) := Elmt
                    FSI                    
                    Ecrirebloc(F, I, Buffer)
                FINPOUR
            FSI            

        SINON { Buffer.Nb < B }
            {Insertion de Cle dans le bloc Milieu à la position Binf}
            POUR J=Buffer.Nb,Binf, 1, -1
                Buffer.T(J+1) := Buffer.T(J)
            FINPOUR
            Buffer.T(Binf) := Cle
            Buffer.Nb := Buffer.Nb + 1
            Ecrirebloc(F, Milieu, Buffer)
        FSI
    SINON
        " Clé existe "
    FSI
   
Description de F

    TYPE Typebloc = STRUCTURE
        T     : TABLEAU[1..B] DE Typecle
        Nb     : ENTIER { Nombre d'articles}
        Lien     : Typeadresse
    FIN
    TYPE Typeadresse = STRUCTURE
        Numbloc     : ENTIER
        Tetelist     : ENTIER
    FIN

Description de F'

    TYPE Typebloc' = STRUCTURE
        T'     : TABLEAU[1..M] DE Typemaillon
        Lien' : ENTIER
    FIN
    TYPE Typemaillon= STRUCTURE
        Cle     : Typecle
        Suiv     : Typeadresse
    FIN

Pour pouvoir pratiquer toujours la recherche dichotomique sur le fichier F, nous convenons de faire les suppositions suivantes :

- Buffer.T(B) est toujours supérieur à tous les éléments de la liste se trouvant sur le fichier F'.
- les listes sont ordonnées.
- la liste de débordements n'existe que si le bloc primaire est rempli. Donc, quand on effectue une suppression d'un article d'un bloc rempli du fichier F, on doit ramener un élément de la liste de débordements si celle-ci existe.

Nous utilisons les modules suivants :

Rechdicho(F, Cle, Trouv, I) : recherche dichotomique d'une clé Cle sur le fichier F. Si la clé est trouvée, Trouv est VRAI et I pointe le bloc contenant cette clé.

Rechlist (Buffer.Lien, Cle, Trouv, K) : recherche d'une clé Cle dans une liste linéaire chaînée de tête Buffer.Lien contenue dans F'. Si la clé est trouvée, Trouv est VRAI et K pointe l'entrée dans le bloc contenant cette clé.

Module de recherche/insertion

    Rechdicho(F, Cle, Trouv, I)
    SI NON Trouv : { Le bloc I est dans Buffer }
        SI Buffer.Nb < B :
            . Inserer la clé Cle dans ce buffer
        SINON
            SI Buffer.Lien.Numbloc = NIL :
                . Créer une liste avec la clé Cle
            SINON
                Rechlist(Buffer.Lien, Cle, Trouv",K)
                SI NON Trouv" :
                    . Inserer la cle Cle dans la liste
                FSI
            FSI
        FSI
    FSI
   
Recherche dans le fichier de débordements

On a, en entrée :

Num     : le numéro du bloc o� commence la liste.
L     : la tête de liste dans ce bloc.
Clé    : clé à rechercher.

et en sortie :

Trouv : vrai si la clé est trouvée, faux sinon.
K    : position de la clé dans le cas o� la clé est trouvée.

    Trouv := FAUX
    Lirebloc(F', Num, Buffer)
    TANTQUE L # -1 ET NON Trouv :
        SI Buffer.T'(L).Article.Cle= Cle :
            Trouv := VRAI
        SINON
            L := Buffer.T(L).Suiv.Tetelist
            SI Buffer.T(L).Suiv.Numbloc # Num :
                Num := Buffer.T(L).Suiv.Numbloc
                Lirebloc(F, Num, Buffer)
            FSI
        FSI
    FINTANTQUE