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.

Correction

Cliquez ici pour révéler la correction.

tableau_liste.py :

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

from random import randint

from cellule import Cellule


class Liste:
    """
    Une liste chainee simple avec un element fictif en tete
      et un champ stockant le nombre d'elements de la liste
    """

    # pylint: disable=too-few-public-methods

    def __init__(self):
        """
        Constructeur
        """
        self.tete = Cellule("?", None)
        self.nbr_elem = 0

    def afficher(self):
        """
        Affiche les elements d'une liste et va a la ligne
        """
        print(f"({self.nbr_elem} elements) ", end="")
        cour = self.tete.suiv
        while cour is not None:
            print(f"{cour.val} -> ", end="")
            cour = cour.suiv
        print("FIN")


class TableauListe:
    """
    Notre structure est constituee d'un entier representant
      le nombre d'elements dans la table, ainsi qu'un tableau
      des listes chainees
    """

    def __init__(self, taille_tab):
        """
        Cree une table de hachage vide d'une taille donnee
        """
        self.nbr_elem = 0
        self.tab = [Liste() for _ in range(taille_tab)]

    def hachage(self, val):
        """
        Methode de hachage tres naive
        """
        return val % len(self.tab)

    def afficher(self):
        """
        Affiche le contenu de la structure
        """
        print(f"Structure contenant {self.nbr_elem} elements :")
        for idx, lst in enumerate(self.tab):
            print(f"[{idx}] ", end="")
            lst.afficher()

    def inserer(self, val):
        """
        Insere une valeur dans la structure
        """
        self.nbr_elem += 1
        hach = self.hachage(val)
        self.tab[hach].nbr_elem += 1
        self.tab[hach].tete.suiv = Cellule(val, self.tab[hach].tete.suiv)

    def est_presente(self, val):
        """
        Test si val est dans la structure (au moins une fois)
        """
        hach = self.hachage(val)
        cour = self.tab[hach].tete.suiv
        while cour is not None and cour.val != val:
            cour = cour.suiv
        return cour is not None

    def supprimer(self, val):
        """
        Supprime une valeur dans la structure
        Renvoie True ssi la valeur etait dans la liste
        """
        hach = self.hachage(val)
        prec = self.tab[hach].tete
        while prec.suiv is not None and prec.suiv.val != val:
            prec = prec.suiv
        if prec.suiv is not None:
            prec.suiv = prec.suiv.suiv
            self.tab[hach].nbr_elem -= 1
            self.nbr_elem -= 1
            return True
        return False




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()