III. Les dictionnaires¶

Cours¶

A. Définition¶

Définition

Les dictionnaires ou tableaux associatifs sont des structures de données non-linéaires, où des valeurs sont associées à des clés.

B. Type abstrait¶

Les opérations primitives pouvant être faites sur les dictionnaires sont les suivantes :
- ajout d'une nouvelle valeur à une nouvelle clé,
- modification de la valeur associée à une clé existante,
- suppression d'une clé et de la valeur associée,
- recherche de la valeur associée à une clé.

Ils sont implémentés directement en Python avec le type dict.

Rappels

Comment vous pouvez effectuer les opérations primitives sur un dictionnaire Python, noté d ? Commencer par créer un dictionnaire vide.

Solution

d = {}
d[cle] = v1   #ajout d'une nouvelle valeur à une nouvelle clé
d[cle] = v2   #modification de la valeur associée à cle
d.pop(cle)  #supprime cle et sa valeur associée
print(d[cle])  #recherche de la valeur associée à cle

Avec quelle méthode accède-t-on à la liste des clés de d ? A la liste de ses valeurs ?

Solution

d.keys() et d.values() donnent respectivement la liste des clés et des valeurs.
Comment peut-on afficher l'ensemble des clés et des valeurs associées, en parcourant d ?
Solution
```
for cle in d:
    print(cle, d[cle])

d.items()  #donne la liste des couples
```

C. Accès à un élément¶

L'accès à un élément dans un tableau associatif s'effectue, comme dans un tableau, en temps constant. Il est indépendant de la taille de la structure.

L'implémentation d'un dictionnaire est en effet faite grâce à une table de hachage (hors programme) qui associe à chaque couple clé-valeur un indice du tableau.

Rappel des algorithmes à connaître

Ecrire une fonction occurrence_dico(d, k) recherchant la clé k dans le dictionnaire d. Si elle trouve cette clé, elle renvoie le tuple k, valeur associée à k, sinon elle renvoie None, 0.

###
Ecrire une fonction maxi_dico(d) renvoyant la valeur maximale du dictionnaire d non-vide, constitué d'entiers positifs, et la clé associée.

###
Ecrire une fonction moyenne_dico(d) renvoyant la moyenne des valeurs du dictionnaire d non-vide sur l'ensemble de ses clés. On suppose que toutes les valeurs sont des entiers ou des flottants.

###

Exercice

Correction

Écrire en Python une fonction tabToDict qui prend en paramètre d’entrée une liste Python de la forme [clé1, valeur1, clé2, valeur2,…] et retourne un dictionnaire correspondant de la forme { clé1 : valeur1, clé2 : valeur2,…}.
Réciproquement, écrire une fonction en Python dictToTab qui permet de passer d'un dictionnaire à une liste.