NUMERIQUE ET SCIENCES INFORMATIQUES

Niveau : Terminale générale, enseignement de spécialité NSI

D
É
C
O
N
N
E
C
T
É

Structures de données, partie 3 - Les dictionnaires

1. Type abstrait dictionnaire

Remarque.

Le type abstrait dictionnaire ressemble au type abstrait liste. Mais au lieu d'attribuer à chaque valeur un indice, on attribue ici à chaque valeur ce que l'on appelle une clé, qui peut être de différents types (entier, chaîne de caractères etc...).

Définition

Un dictionnaire est une collection non ordonnée de couples clé-valeur appelés entrées accompagnée de différentes opérations parmi lesquelles :

  • creer_vide() : crée et retourne un dictionnaire vide
  • inserer(dico, cle, valeur) : insère l'entrée clé-valeur dans le dictionnaire
  • supprimer(dico, cle): supprime du dictionnaire l'entrée associée à la clé passée en paramètre
  • lire(dico, cle) : retourne la valeur associée au paramètre cle dans le dictionnaire
  • rechercher(dico, cle) : retourne vrai si il existe dans le dictionnaire une entrée donc la clé est le paramètre cle et faux sinon.

Remarque.

La liste d'opérations donnée ci-dessus est une liste minimale. on ajoute en général différentes opérations à cette liste, comme par exemple une opération permettant de modiffier une entrée.

2. Dictionnaires en Python : rappels

2.1 Type dict

Remarque.

En pratique, les dictionnaires de Python sont réalisés grâce à des fonctions de hachage, qui à toute clé associent un entier, et ce en temps constant. Si on note i cet entier, le couple (clé, valeur) sera stocké à l'indice i d'un tableau appelé table de hachage. Grâce à cela, chercher si une clé ou une entrée appartient à un dictionnaire se fait en temps constant, ce qui fait des dictionnaires une structure de données très efficace.

En Python

  • Le type dictionnaire en Python s'appelle dic.
  • Une clé dans un dictionnaire se note key et est nécessairement de type non mutable (par exemple int, float, str (chaîne de caractère) ou tuple)
  • Une valeur dans un dictionnaire se note value et peut être de n'importe quel type.
  • Une entrée est représentée par une clé et sa valeur, séparées par le symbole deux points. Il se note item en Python.
  • Pour créer un dictionnaire, on met les entrées séparées par des virgules, le tout entre accolades.

Exemple :

		
		


	

2.2 Manipulation des éléments

En Python

Pour accéder à la valeur associée à une clé dans un dictionnaire on utilise la syntaxe : dictionnaire[clé]

Exemple

		
		
		

En Python

Le nombre d'éléments d'un dictionnaire s'obtient avec la fonction len.

Exemple

		


		

En Python

On peut tester si une clé est dans un dictionnaire avec l'opération in.

Remarque.

L'opération in est également valable pour différents types de Python (list, str, ...).

Exemple

		

		

En Python

  • Si une clé est déjà dans un dictionnaire, on peut modifier la valeur associée à cette clé avec la syntaxe :
    dictionnaire[clé] = nouvelle valeur
  • Si un clé n'est pas dans un dictionnaire, on peut l'ajouter au dictionnaire avec la syntaxe :
    dictionnaire[nouvelle clé] = nouvelle valeur

Exemple

		



		

En Python

On peut supprimer une entrée d'un dictionnaire avec la fonction del.

Exemple

		

	

2.3 Parcours séquentiel d'un dictionnaire

On peut parcourir un dictionnaire de trois façons différentes. Évidemment, ces trois façons impliquent l'usage d'une boucle.

  • Parcours des clés :
  • Pour parcourir les clés, on utilise la syntaxe :

    for cle in dictionnaire:

    ou : for cle in dictionnaire.keys():

    Exemple

    		
    
    		
  • Parcours des valeurs :
  • Pour parcourir les valeurs, on utilise la syntaxe :

    for valeur in dictionnaire.values():

    Exemple

    		
    
    		
  • Parcours des entrées :
  • Pour parcourir les entrées (sous forme de couples (clé,valeur)), on utilise la syntaxe :

    for item in dictionnaire.items():

    Exemple

    		
    
    		

3. Exercices

Exercice 1.

Le fichier ltdm80j.txt ci-dessous contient le texte du roman "Le tour du monde en 80 jours" de Jules Verne sans aucun symbole de ponctuation et en minuscules.

Le fichier suivant permet d'importer ce texte en Python, sous la forme d'un tableau de mots noté tab.

    1. Écrire en Python une fonction compte_mots qui :
      • prend en paramètre un tableau de mots,
      • retourne un dictionnaire dans lequel les clés sont les mots du tableau et les valeurs sont le nombre d'occurrences de ces mots dans le tableau.

      
      											
      							
      
      
      			
    2. Tester cette fonction sur le texte de Jules Verne.
    3. Résultat :

      {'le': 1895, 'tour': 42, 'du': 770, 'monde': 63, 'en': 918, 'quatre': 90, 'vingts': 26, 'jours': 97, ...
    4. Écrire un programme faisant appel à la fonction précédente et qui affiche le mot le plus fréquent du texte.
    5. Le mot le plus fréquent est : 'de' (2897 occurrences)
    6. Écrire un programme faisant appel à la fonction précédente qui affiche le mot de longueur 5 le plus fréquent du texte.
    7. Le mot de longueur 5 le plus fréquent du texte est : 'était' (582 occurrences)
    8. Écrire en Python une fonction compte_lettres qui :
      • prend en paramètre un tableau de mots,
      • retourne un dictionnaire dans lequel les clés sont les caractères composant les mots du tableau et les valeurs sont le nombre d'occurrences de ces caractères dans le tableau.
      {'l': 17215, 'e': 45225, 't': 25069, 'o': 17471, 'u': 19622, 'r': 22501, 'd': 12110, 'm': 9439, ...
    9. Quelle est la lettre la plus fréquente du texte de Jules Verne et son nombre d'occurrences ?

Exercice 2

titanic

Le Titanic appareille de Southampton (Angleterre) le mercredi 10 avril à 12 h 15 .

Six heures plus tard, à 18 h 15, il fait escale dans la rade de Cherbourg. Il y débarque 24 passagers et en embarque 274, amenés par les transbordeurs Nomadic et Traffic. Il appareille à 20 h 10.

Le Titanic fait route vers l'Irlande. Il arrive à Queenstown (aujourd'hui Cobh) le 11 avril à 11 h 30. Il débarque 7 passagers et en embarque 120. À 13 h 30, le paquebot appareille et entame sa traversée de l'Atlantique vers New York .

Le 14 avril, à 23 h 40 (heure locale, GMT-3), il percute un iceberg au large de Terre-Neuve. Il sombre le 15 avril à 2 h 20, causant la mort de 1 524 personnes.

(source wikimanche)

Le fichier ci-dessous est une table de données contenant des informations sur certains passagers du Titanic au format csv. La source initiale provient de github.com



											
							
			
  1. Les dictionnaires éléments du tableau titanic contiennent une clé "Name" qui contient le nom des passagers du Titanic et une clé PassengerId, son identifiant sous la forme d'une chaine de caractères.
    Ecrire une fonction nom prenant en paramètre un entier id correspondant à l'identifiant et qui retourne le nom du passager si l'identifiant existe sinon None
  2. >>>nom(44)
    Laroche, Miss. Simonne Marie Anne Andree
    >>>nom(892)
    None
  3. Les dictionnaires éléments du tableau titanic contiennent une clé "Survived" dont la valeur associée est "1" pour les survivants et "0" sinon.
    Écrire un programme affichant le nombre de survivants du Titanic.
  4. Résultat :

    Le nombre de survivants est : 341
  5. Les dictionnaires éléments du tableau titanic contiennent une clé "Age" dont la valeur associée est l'âge du passager sous la forme d'une chaîne de caractères. Attention l'age de plusieurs passagers ne sont pas indiqué ('').
    Écrire un programme affichant l'âge moyen des passagers du Titanic.
  6. l'age moyen des passagers est : 29.69911764705882
  7. Lors d'un naufrage, la devise est de sauver les femmes et les enfants d'abord.
    Écrire un programme affichant le pourcentage de mineurs survivants, puis le nombre de femmes survivantes de tout age
  8. Le pourcentage de mineurs survivants est : 53.98230088495575
    Le pourcentage de femmes survivantes est : 74.20382165605095

Fond :  Texte :  Tables :  Thème du langage: