Enoncé 13 : Hachage interne   Corrigé 13

Problème : Essai linéaire avec effacement logique des données

Dans la méthode d'essai linéaire, on propose de supprimer les données uniquement par le positionnement d'un bit d'effacement. Chaque entrée dans la table est alors le triplet (Occ, Eff, Val) avec :

- Occ : position occupée ou vide

- Eff : donnée effacée ou pas

- Val : donnée

Donner l'état du vecteur T(0..7) :

- après les insertions des données suivantes avec leurs transformées entre parenthèses : a(3), b(2), c(3), d(7), e(4), f(7)

- après la suppression de b, f, a

Donner l'algorithme qui recherche un élément E donné et qui l'insère s'il n'existe pas dans les deux cas suivants:

- sans récupération des emplacements des données effacées,

- avec récupération éventuelle de ces derniers.

Donner l'algorithme de réorganisation qui consiste à supprimer physiquement tous les emplacements des données effacées. L'algorithme opère ( travaille ) sur le même vecteur.

Donner l'état du tableau après cette réorganisation pour l'exemple précédent.

NB. On utilisera les modules Occ(I), Eff(I) et Val(I) pour l'accès aux différents champs de l'entrée I du tableau et Aff_occ(I, bit), Aff_eff(I, Bit) et Aff_Val(I, Val) pour les mises à jour correspondantes.

* * * * *