Aller au contenu

TP - Implémenter un tableau associatif

Ce TP est basé sur une idée originale de Messieurs FUCHEY, LAURENT et SALLIOT, enseignants de NSI dans l'académie de Lyon. Qu'ils en soient ici remerciés.

Ce TP, qui sera suivi par un mini-projet, doit conduire à réaliser trois implémentations différentes d'une structure de tableau associatif.

TPA03.31 - Deux tableaux distincts

Dans ce TP, vous devrez construire en POO une structure de tableau associatif munie des méthodes suivantes :

Méthode/Opérations Description
d = Dico() Initialisation d'un tableau associatif vide
d.est_vide() Renvoie True si le tableau associatif est vide, False sinon.
d.est_plein() Renvoie True si le tableau associatif est complet, False sinon
d.hashage(cle) Renvoie l'indice qui correspond à cle,
renvoie -1 si cle est absente du tableau associatif
d.contient(cle) Renvoie True si cle est une clef du tableau associatif, False sinon
d. ajout(cle, valeur) Associe valeur à une nouvelle clef cle.
Si cle est déjà présente, modifie la valeur associée.
print(d) Chaîne de caractère renvoyée pour l'affichage du tableau associatif sous la forme :
    DEBUT
    cle1 : valeur1
    cle2 : valeur2
    (...)
    FIN
Les cellules (clés) vides ne s'affichent pas
d.valeur(cle) Renvoie la valeur associée à la clef clef
d.supprime(cle) Supprime la clef clef (et donc la valeur associée)
len(d) Renvoie le nombre de clés non vides stockées dans le tableau associatif

Fichier à trous

Téléchargez puis complétez le fichier « à trous » TPA03.31.py (clic droit -> [Enregistrer sous]).

Dans ce fichier, la classe se nomme Dico1. Elle comporte quatre attributs :

  • longueur : entier (puissance de 2), nombre total de clefs non vides pouvant être contenues dans le tableau associatif ;
  • cles : tableau (type list en Python) qui contiendra les clés et qui est initialisé avec longueur éléments de valeur None ;
  • valeurs : tableau (type list en Python) qui contiendra les valeurs associées aux clés et qui est initialisé avec longueur éléments de valeur None ;
  • nb_elements : entier, le nombre de clefs non vides stockées dans le tableau associatif.

Énoncé

  1. Complétez le constructeur de la classe Dico1 et vérifiez l'initialisation de chacun des attributs.

    Exemple de tests

    Les entrées du tableau associatif sont stockées dans les tableaux cles et valeurs :

    >>> d = Dico1(3)
    >>> d.longueur
    8
    
    >>> d.cles
    [None, None, None, None, None, None, None, None]
    
    >>> d.valeurs
    [None, None, None, None, None, None, None, None]
    
    >>> d.nb_elements
    0
    
  2. Complétez le code des méthodes est_vide() puis est_plein() qui nécessitent toutes les deux un raisonnement analogue.

  3. Complétez le code de la méthode hachage() qui prend en paramètre une clef cle et qui renvoie -1 si cle n'est pas présent dans le tableau cles ou qui renvoie l'indice auquel on peut trouver cle dans le tableau cles.

    Exemple de tests

    Si d.cles est ['c', 'b', 'a', None, None, None, None, None], alors on obtient les renvois suivants :

    >>> d.hachage('a')
    2
    
    >>> d.hachage('e')
    -1
    

  4. Complétez le code de la méthode contient() qui prend en paramètre une clef cle et qui renvoie True si cle est présente dans le tableau cles, False sinon.

  5. Complétez le code de la méthode ajout() qui prend en paramètres une clef cle et une valeur valeur.

    • Ou bien cle existe déjà dans le tableau cles, alors on remplace par valeur la valeur correspondante à cette cle dans le tableau valeurs ;
    • Ou bien cle n'existe pas et on place cle dans le tableau cles et valeur dans le tableau valeurs à la première position disponible, c'est-à-dire en remplaçant le premier élément valant None.
      Attention, le tableau associatif est peut-être complet...

    Exemple de tests

    >>> d = Dico1(3)
    
    >>> d.cles
    [None, None, None, None, None, None, None, None]
    
    >>> for i in range(5, 9):
    ...     d.ajout(i, 9-i)
    
    >>> d.cles
    [5, 6, 7, 8, None, None, None, None]
    
    >>> d.valeurs
    [4, 3, 2, 1, None, None, None, None]
    
    >>> for i in range(7, 13):
    ...     d.ajout(i, 14-i)
    
    >>> d.cles
    [5, 6, 7, 8, 9, 10, 11, 12]
    
    >>> d.valeurs
    [4, 3, 7, 6, 5, 4, 3, 2]
    
    >>> d.ajout(0, 14)
    AssertionError: Le tableau associatif est complet
    
  6. Complétez le code de la méthode __repr__() qui renvoie la chaîne d'affichage du tableau associatif.

    Exemple de tests

    >>> d = Dico1(3)
    
    >>> for i in range(5, 9):
    ...     d.ajout(i, 9-i)
    
    >>> d
        DEBUT
        5 : 4 
        6 : 3 
        7 : 2 
        8 : 1 
        FIN
    
  7. Terminez en complétant les codes des méthodes valeur(), supprime() puis __len__().
    Ajoutez les tests nécessaires au programme principal.