Révision

Ce qu’il faut savoir

Types abstraits dictionnaire

Dans un dictionnaire (aussi appelé tableau associatif), chaque élément (appelé valeur) est associé à une clé. Un dictionnaire contient donc des couples clé:valeur. Voici les opérations que l'on peut effectuer sur le type abstrait dictionnaire :

• ajout : on associe une nouvelle valeur à une nouvelle clé
• modification : on modifie un couple clef:valeur en remplaçant la valeur courante par une autre valeur (la clé restant identique)
• suppression : on supprime une clé (et donc la valeur qui lui est associée)
• recherche : on recherche une valeur à l'aide de la clé associée à cette valeur.

Implémentation des dictionnaires

Dans beaucoup de langage de programmation les dictionnaires sont implémentés à l’aide de tables de hachage.

Algorithme de recherche dans un dictionnaire

L'algorithme de recherche d'un élément dans un dictionnaire a une complexité O(1). La durée de recherche ne dépend pas du nombre d'éléments présents dans le dictionnaire.

Ce qu’il faut savoir faire

Savoir utiliser les dictionnaires en Python