TP7

Principe

On se propose d'implémenter un modèle simple de table de hachage pour stocker des chaînes de caractères dans un tableau. Ensuite, on utilisera un modèle de liste chaînée pour optimiser les tables de hachages et éviter les collisions. :

Une table de hachage est une structure de données permettant de stocker des objet avec un temps d'accès extrêmement rapide. En effet, si on souhaite savoir où se trouve un élément dans un tableau inconnu, il faut normalement faire une recherche qui parcours au maximum tous les tableaux. Ici, on va définir une fonction (qu'on appelle fonction de hachage) qui permettra de calculer directer l'indice auquel on doit ranger (ou trouver) un élément dans ce tableau.

Partie 1 - Tables simples

1. Notre structure de données sera un tableau de taille N (avec N=13 ici) permettant de stocker des chaînes de caractères de taille MAX_SIZE (fixée à 20). Définir une telle structure dans le main. Dans la suite du problème, on ne considère que des mots en lettres minuscules.
2. Implémentez une fonction permettant d'afficher une telle structure.
3. Implémenter une fonction init_table qui initialise une table de hachage en mettant toutes ses cases à NULL.
4. On définit la fonction de hachage suivante pour connaître l'index auquel on doit stocker un mot :
   • - à chaque lettre du mot, on associe son rang dans l'alphabet. On calcule la somme des rangs des lettres du mot
   • - On ajoute à cette somme le nombre de lettres du mot
   • - Le résultat final est le résultat précédent modulo N
   Définir une fonction h qui pour un mot calcule la valeur de sa fonction de hachage. Vous pouvez définir pour vous aider les fonctions rang et taille qui donnent le rang d'une lettre dans l'alphabet et la taille d'une chaîne de caractères.
5. Implémenter la fonction insere qui insère un mot dans une table donnée. La fonction renvoie l'index si tout s'est bien passé, ou -1 en cas de collision.
6. Donnez le code de la fonction presence qui prend en paramètre un mot et une table, et renvoie True si le mot est présent dans la table, False sinon.
7. Testez votre table sur les prénoms suivants : serge, odile, luc, anne, annie, jean, julie, basile, paula, marcel, elise.

Partie 2 - Tables avec listes chaînées.

Cette partie est un problème ouvert pour lequel il vous est vivement conseillé de réfléchir à la modélisation avant de vous lancer dans le code. On propose que la table de hachage ne stocke pas des chaînes de caractères, mais des listes de chaînes de caractères. Ainsi, en cas de collision, il suffit d'ajouter la valeur à la liste contenue dans l'index calculé par h, plutôt que de ne pas pouvoir ajouter la valeur à la table.

Implémentez toutes les fonctions précédentes en modifiant le programme de façon à ce qu'il réponde à la consigne ci-dessus. Implémentez également les fonctions nécessaire pour libérer la mémoire (c'est à dire vider un index).

Vous avez la possibilité si vous le souhaitez de rendre cette deuxième partie comme exercie bonus avant le 14/06/2022 à 23h59. La note comptera pour votre moyenne de contrôle continu, seulement si elle la fait augmenter.