Si la recherche et l'insertion sont faciles pour leur compréhension, la  suppression mérite reflexion.

Nous proposons ci-après une solution possible à l'opération de suppression :

Implémentation

- une table TDON [1..Max] de sous tableaux

Chaque sous tableau [1..B] peut contenir B données

- une table TLIEN [1..Max] de lien contenant les données en débordements des sous tableaux

- une table TNBR[1..Max] contient le nombre d'éléments de chaque sous tableau

Algorithme de suppression :

1. Rechercher la donnée

Si elle existe soit I l'entrée dans la table TDON et J la position dans le sous tableauc correspondant à l'entrée I

 2. supprimer la donnée en procédant par simple déplacement du dernier vers la position J.

3. Si l'entrée I n'a pas de suivant, l'algorithme s'arrête.

4. sinon, chercher s’il existe plus loin dans la liste des sous tables une donnée d telle que la liste qui commence en h(d) contient (passe ou traverse) le maillon I. h étant la fonction de hachage utilisée.

5. Si une telle donnée existe, K est son indice dans TDON et Ind l'indice dans sa sous table.

déplacer cette donnée au maillon I position J, poser I:= K et J := Ind et recommencer la suppression de cette donnée à partir de 2.

6. Sinon faire une coupe : couper la liste en deux en mettant tout simplement Nil dans TLIEN(I).

  {

            Chaînage interne

            Capacité de la case > 1

            Recherche - Insertion - Suppression

            Réalisation D.E  ZEGOUR

 }

   SOIT

       F UN FICHIER DE ENTIERS BUFFER Donnee ;

       Tdon UN VECTEUR ( 100 ) DE VECTEUR ( 5 ) ;

       Tlien UN VECTEUR ( 100 ) DE ENTIER ;

       Tnb UN VECTEUR ( 100 ) DE ENTIER ;

       M UN ENTIER ;

       B UN ENTIER ;

       Nile UN ENTIER ;

       R UN ENTIER ;

       N UN ENTIER ;

       H UNE FONCTION ( ENTIER ) ;

       Init , Inserer , Rechercher , Suprimer DES ACTIONS ;

       Generer_donnees UNE ACTION ;

       Chercher UNE ACTION ;

       Exist UNE FONCTION ( BOOLEEN ) ;

       Imprimer UNE ACTION ;

      {

 Génère un fichier de n données aléatoires

 Initialise la table, Insère les n données du fichier , puis  les Supprime.

 Montre les tables après toutes les insertions et après toutes les

 suppressions

       }

   DEBUT

       M := 100 ;

       B := 5 ;

       Nile := - 1 ;

       R := M ;

       APPEL Init ;

       APPEL Generer_donnees ;

       OUVRIR ( F , 'don.pas' , 'A' ) ;

       TQ NON FINFICH ( F )

           LIRESEQ ( F , Donnee ) ;

           APPEL Inserer ( Donnee )

       FTQ ;

       FERMER ( F ) ;

       ECRIRE ( 'table avant' ) ;

       APPEL Imprimer ;

       ECRIRE ( 'Suppression ...' ) ;

       OUVRIR ( F , 'don.pas' , 'A' ) ;

       TQ NON FINFICH ( F )

           LIRESEQ ( F , Donnee ) ;

           APPEL Suprimer ( Donnee )

       FTQ ;

       FERMER ( F ) ;

       ECRIRE ( 'table après' ) ;

       APPEL Imprimer ;

   FIN

  { Génère un fichier avec n  données aléatoires }

   ACTION Generer_donnees ;

   SOIT

       K UN ENTIER ;

   DEBUT

       OUVRIR ( F , 'don.pas' , 'N' ) ;

       POUR K := 1 , 490

           Donnee := ALEANOMBRE ( 5000 ) ;

           ECRIRESEQ ( F , Donnee )

       FPOUR ;

       FERMER ( F ) ;

   FIN

  {Initialise les tables}

   ACTION Init ;

   SOIT

       I , J DES ENTIERS ;

       V UN VECTEUR ( 5 ) ;

   DEBUT

       INIT_VECT ( V , [ 0 , 0 , 0 , 0 , 0 ] ) ;

       POUR I := 1 , M

           AFF_ELEMENT ( Tlien [ I ] , - 1 ) ;

           AFF_ELEMENT ( Tnb [ I ] , 0 ) ;

           AFF_ELEMENT ( Tdon [ I ] , V ) ;

       FINPOUR

   FIN

  {Fonction de hachage}

   FONCTION H ( Nombre ) : ENTIER ;

   SOIT

       Nombre UN ENTIER ;

   DEBUT

       H := MOD ( Nombre , M ) + 1

   FIN

  {Imprime les tables}

   ACTION Imprimer ;

   SOIT

       I UN ENTIER ;

   DEBUT

       POUR I := 1 , M

           ECRIRE ( I , ':' , ELEMENT ( Tnb [ I ] ) , ELEMENT ( Tdon [ I ] ) , ELEMENT ( Tlien [ I ] ) )

       FPOUR ;

   FIN ;

  {

 Recherche d'une donnée D

 Si D existe, Trouv est vrai. I est sa coordonnée dans Tdon et  J sa coordonnée dans la sous table

 Si D n'existe pas, Trouv est faux. I est l'indice du dernier maillon visité

 }

   ACTION Rechercher ( D , Trouv , I , J )

   SOIT

       I , J DES ENTIERS ;

       Trouv , Arret DES BOOLEENS ;

       D UN ENTIER ;

   DEBUT

       I := H ( D ) ;

       Trouv := FAUX ;

       Arret := FAUX ;

       TQ NON Trouv ET ( I <> Nile ) ET ( NON Arret )

           J := 1 ;

           TQ ( J <= ELEMENT ( Tnb [ I ] ) ) ET NON Trouv

               SI ELEMENT ( ELEMENT ( Tdon [ I ] ) [ J ] ) = D

                   Trouv := VRAI

               SINON

                   J := J + 1

               FSI

           FTQ ;

           SI NON Trouv

               SI ELEMENT ( Tlien [ I ] ) <> Nile

                   I := ELEMENT ( Tlien [ I ] ) ;

               SINON

                   Arret := VRAI

               FSI

           FSI

       FTQ

   FIN

  { Insérer une donnée d }

   ACTION Inserer ( D ) ;

   SOIT

       D UN ENTIER ;

       I , J DES ENTIERS ;

       Trouv UN BOOLEEN ;

   DEBUT

       APPEL Rechercher ( D , Trouv , I , J ) ;

       SI NON Trouv

           SI ELEMENT ( Tnb [ I ] ) < B

               AFF_ELEMENT ( ELEMENT ( Tdon [ I ] ) [ ELEMENT ( Tnb [ I ] ) + 1 ] , D ) ;

               AFF_ELEMENT ( Tnb [ I ] , ELEMENT ( Tnb [ I ] ) + 1 )

           SINON

          /* Collision */

               Trouv := FAUX ;

               TQ NON Trouv ET ( R >= 1 )

                   SI ELEMENT ( Tnb [ R ] ) < B

                       Trouv := VRAI

                   SINON

                       R := R - 1

                   FSI

               FTQ ;

               SI NON Trouv

                   ECRIRE ( 'saturation de la table' )

               SINON

              /* inserer la donnee */

                   AFF_ELEMENT ( ELEMENT ( Tdon [ R ] ) [ ELEMENT ( Tnb [ R ] ) + 1 ] , D ) ;

                   AFF_ELEMENT ( Tnb [ R ] , ELEMENT ( Tnb [ R ] ) + 1 ) ;

                  /* chainage */

                   AFF_ELEMENT ( Tlien [ I ] , R )

               FSI

           FSI

       SINON

           ECRIRE ( 'Donnée ' , D , ' existe' ) ;

       FSI

   FIN

  {

 Cherche s'il existe dans une sous table T de taille Taille,

 une donnée d telle que la liste qui commence en h(d) contient le maillon I

 Si une telle donnée existe, Ind est son indice dans T

 }

   ACTION Chercher ( T , Taille , I , Trouv , Ind )

   SOIT

       I UN ENTIER ;

       T UN VECTEUR ( 5 ) ;

       Trouv UN BOOLEEN ;

       Ind UN ENTIER ;

       Taille UN ENTIER ;

       V UN ENTIER ;

   DEBUT

       Ind := 1 ;

       Trouv := FAUX ;

       TQ ( Ind <= Taille ) ET NON Trouv

           V := ELEMENT ( T [ Ind ] ) ;

           SI Exist ( I , H ( V ) )

               Trouv := VRAI

           SINON

               Ind := Ind + 1

           FSI

       FTQ

   FIN

  { Détermine si  la liste de tete N contient le maillon I }

   FONCTION Exist ( I , N ) : BOOLEEN ;

   SOIT

       N , I UN ENTIER ;

       Trouv UN BOOLEEN ;

       P UN ENTIER ;

   DEBUT

       P := N ;

       Trouv := FAUX ;

       TQ NON Trouv ET ( P <> Nile )

           SI ( P = I )

               Trouv := VRAI

           SINON

               P := ELEMENT ( Tlien [ P ] ) ;

           FSI

       FTQ ;

       Exist := Trouv ;

   FIN

  {Surprime une donnée d }

   ACTION Suprimer ( D ) ;

   SOIT

       D UN ENTIER ;

       I , J , K , Ind DES ENTIERS ;

       Trouv UN BOOLEEN ;

       L UNE LISTE ;

       Continue UN BOOLEEN ;

   DEBUT

       APPEL Rechercher ( D , Trouv ,  I , J ) ;

       SI Trouv

           Continue := VRAI ;

           TQ Continue

               AFF_ELEMENT ( ELEMENT ( Tdon [ I ] ) [ J ] , ELEMENT ( ELEMENT ( Tdon [ I ] ) [ ELEMENT ( Tnb [ I ] ) ]

               ) ) ;

               SI ELEMENT ( Tlien [ I ] ) = Nile

                   Continue := FAUX ;

                   AFF_ELEMENT ( Tnb [ I ] , ELEMENT ( Tnb [ I ] ) - 1 ) ;

               SINON

                   Trouv := FAUX ;

                   K := ELEMENT ( Tlien [ I ] ) ;

                   TQ ( K <> Nile ) ET NON Trouv

                       APPEL Chercher ( ELEMENT ( Tdon [ K ] ) , ELEMENT ( Tnb [ K ] ) , I , Trouv , Ind ) ;

                       SI NON Trouv

                           K := ELEMENT ( Tlien [ K ] )

                       FSI

                   FTQ ;

                   SI Trouv

                       AFF_ELEMENT ( ELEMENT ( Tdon [ I ] ) [ B ] , ELEMENT ( ELEMENT ( Tdon [ K ] ) [ Ind ] ) ) ;

                       I := K ;

                       J := Ind ;

                   SINON

                       ECRIRE ( 'Une coupe' ) ;

                      /* Couper la liste en 2 */

                       AFF_ELEMENT ( Tlien [ I ] , Nile ) ;

                       AFF_ELEMENT ( Tnb [ I ] , ELEMENT ( Tnb [ I ] ) - 1 ) ;

                       Continue := FAUX

                   FSI

               FSI

           FTQ ;

       SINON

           ECRIRE ( 'Donnée ' , D , 'inexistante' ) ;

       FSI

   FIN