Tableau de listes chaînées

Énoncé

On va travailler sur une structure de données utilisant une fonction de hachage pour stocker des valeur entières. Cette structure de données sera un tableau de listes chaînées. On doit également fournir une fonction de hachage dont le rôle est de déterminer dans quelle liste une valeur entière se trouve ou doit être insérée. Elle prend en argument la valeur entière et renvoie l'indice de la case du tableau contenant la liste appropriée.

Le schéma ci-dessous illustre notre structure de données dans laquelle nous avons inséré les valeurs 4, 0, 8, 9, 1, 2, 6, 7, 3 et 7 (dans un ordre quelconque) et pour laquelle la fonction de hachage est simplement valeur % taille_tableau (% est l'opérateur modulo en Python) :

On pourra tester le code produit grâce au squelette suivant qu'on va compléter au fur et à mesure.

#!/usr/bin/env python3
"""
  Tableau de listes chaînées
"""

from random import randint

from cellule import Cellule




def main():
    """
    Fonction principale
    """
    struct = TableauListe(4)
    struct.afficher()
    for _ in range(10):
        val = randint(0, 9)
        print("\nAjout de la valeur", val)
        struct.inserer(val)
        struct.afficher()
    print()
    for val in range(5):
        if struct.est_presente(val):
            print(f"{val} est presente dans la structure")
        else:
            print(f"{val} est absente de la structure")
    print()
    struct.afficher()
    while struct.nbr_elem > 0:
        val = randint(0, 9)
        if struct.supprimer(val):
            print("\nSuppression de la valeur", val)
            struct.afficher()


main()

Implantation des listes

Commencer par reprendre la classe Cellule basique de la séance 15, composée simplement d'une valeur et un suivant.

Écrivez ensuite une classe Liste : les listes seront simplement chaînées, avec un élément fictif en tête et un compteur d'éléments. Le constructeur __init__ de la classe Liste devra donc initialiser deux champs : un champ tete qui pointe sur la cellule fictive en tête qu'on allouera directement dans le constructeur et un champ nbr_elem qui vaudra zéro initialement (la cellule fictive ne compte pas dans le nombre d'éléments de la liste). On recommande d'écrire aussi une méthode d'affichage d'une liste pour aider à la mise au point du code.

Implantation de la structure

On va ensuite implanter la structure sous la forme d'une classe contenant le nombre total de valeurs dans la structure et le tableau de listes. Commencer par implanter le constructeur __init__ de la classe TableauDeListe pour initialiser ses deux champs : ce constructeur prendra en paramètre la taille du tableau (à ne pas confondre avec le nombre d'éléments dans la structure). Ensuite, il faudra écrire la méthode de hachage d'une valeur (qui renvoie simplement le modulo de cette valeur et de la taille du tableau), ainsi qu'une méthode pour afficher le contenu de la structure.

Implanter une méthode d'insertion d'une valeur dans la structure inserer(self, val) qui ne renvoie rien, une méthode est_presente(self, val) testant si une valeur donnée est présente dans la structure et qui renvoie donc un booléen, ainsi qu'une méthode de suppression supprimer(self, val) qui supprime une occurrence de la valeur dans la structure et renvoie True si une suppression a bien eu lieu et False si la valeur n'était pas présente dans la structure.