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é☘

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

Complétez le code des méthodes est_vide() puis est_plein() qui nécessitent toutes les deux un raisonnement analogue.
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
```
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.

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

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

Terminez en complétant les codes des méthodes valeur(), supprime() puis __len__().
Ajoutez les tests nécessaires au programme principal.