PROBLEME : Essai linéaire avec tableaux dynamiques

Soient les modules suivants définis sur l’essai linéaire

- Rech(AdrT, M, Val, Trouv): recherche d'une valeur Val dans le tableau d'adresse AdrT de M éléments. Trouv est VRAI si Val existe, FAUX sinon.

- Insert(AdrT, M, Val): insertion d'une valeur Val dans le tableau d'adresse AdrT de M éléments.

- Sup(AdrT, M, Val): suppression d'une valeur Val dans le tableau d'adresse AdrT de M éléments.

et soit le modèle suivant défini sur les tableaux dynamiques

Allouer(AdrT, M ) : allocation d'un tableau de M éléments. Chaque élément est le couple ( Valeur, Occupé) appartenant à l’ensemble Entier X Booléen. L'adresse de ce tableau est rendue dans la variable AdrT.

Libérer(AdrT) : libération du tableau d'adresse AdrT.

Elément( AdrT, i ) : donne le i-ème élément du tableau d'adresse AdrT.

Aff_element( AdrT, i, Element) : affecte l’élément Element à la i-ème position du tableau d'adresse Adrt.

Considérons la méthode de hachage suivante :

. Toute donnée est hachée par une fonction f en un entier i dans un tableau statique à N éléments ( 0 <= i < N ). L'entrée i de ce tableau renferme l'adresse d'un tableau dynamique, sa taille ainsi que le nombre d’éléments rangés dans ce tableau. Ce dernier contient toutes les données dj telles que f(dj) = i, c'est à dire tous les synonymes.

. Initialement, les synonymes sont rangés dans ce tableau dynamique de taille M par la technique de l'essai linéaire avec la fonction de hachage h₀(d) = d Mod M. Ceci constitue le niveau 0.

. Lors d’une insertion, au niveau K, si le facteur de chargement du tableau des synonymes devient supérieur à �%, on remplace celui-ci de taille 2^K M par un autre tableau de taille double(2^K+1M) en y réinsérant toute les données avec la fonction h_K+1(d) = d Mod 2^K+1 M

. Lors d'une suppression, au niveau K, si le facteur de chargement du tableau des synonymes devient inférieur à �' % ( �'=25) , on lance l'opération inverse de l'insertion qui consiste à remplacer le tableau des synonymes de taille 2^K M par un autre tableau de taille moitié (2^K-1M) en y réinsérant toute les données avec la fonction h_K-1(d) = d Mod (2^K-1)M

Questions

. Donner les structures de la table principale et des tableaux dynamiques. Comment initialiser la table principale ?

. Ecrire les module de recherche, d’insertion et de suppression d'une valeur V donnée.

. Dans le but de sauvegarder toute la structure (toutes les données insérées) dans un fichier afin de pouvoir les récupérer ultérieurement, on décide de mettre uniquement les données dans ce fichier. Définir une structure de fichier possible ( organisation et méthode d’accès)

. En déduire le module de sauvegarde.