Chapitre 1: Interface et implémentation
Cette année, nous allons voir de nouvelles façons d’organiser et de traiter les données, ce que l’on appelle des structures de données. On rencontrera, notamment des structures linéaires comme la liste, la pile et la file, mais également des structures relationnelles telles que les arbres ou les graphes. Dans ce chapitre, nous allons commencer par distinguer la structure de données de son implémentation en s’appuyant sur les tableaux et dictionnaires vus en première.
1 Les tableaux: (list
en python)
En première, nous avons déjà rencontré les tableaux(tableaux dynamiques pour être plus précis), qui sont des séquences d’éléments ordonnés auxquels on peut accéder facilement par leur index.
![Un tableau est une suite de données ordonnées auxquelles on accéde par un index(un entier).](../../../../img/d-hVLO-gAH-300.webp)
En python les tableaux sont implémentés par l’objet list
dont les éléments sont séparés par une
virgule et entourés de crochets.
Les listes étant mutables, on peut ajouter ou supprimer des éléments après création.
- Ajout d’un élément à l’index souhaité :
# ajout avec la méthode `insert()`
ma_liste.insert(0, "zéro")
ma_liste # renvoie ['zéro', 1, 'deux', 3.0]
- Suppression d’un élément à l’index souhaité :
- Il est également fréquent de souhaiter connaitre la longueur de la liste :
2 Différence entre interface et implémentation
Les quatre méthodes qui ont été définies dans la classe list
en Python: len
,
pop
, insert
sont ce que l’on appelle une implémentation de la structure de
donnée tableau.
- Implémentation
-
L’implémentation d’une structure de données ou d’un algorithme est une mise en œuvre pratique dans un langage de programmation.
Il existe de nombreux langages de programmation qui implémentent le type abstrait , nous avions vu l’année dernière les
différences d’implémentation entre les list
de Python et les Array
de javascript.
Cependant, on retrouve des méthodes similaires qui sont ce que l’on appelle l’interface de la structure de données :
- « Insérer » : ajoute un élément dans le tableau à l’index souhaité.
ajout(index, élément)
; - « Retirer » : retire un élément de le tableau à l’index souhaité.
suppr(index)
; - « Le tableau est-il vide ? » : renvoie « vrai » si le tableau est vide, « faux » sinon.
est_vide()
; - « Nombre d’éléments dans le tableau » : renvoie le nombre d’éléments dans le tableau.
longueur()
.
Article Wikipedia sur les listes
- Interface
-
L’interface d’une structure de données est la spécification des méthodes pouvant être appliquées sur cette structure de données.
3 Les Tableaux associatifs: (dict
ionnaires en
Python)
Un dictionnaire, est un type de données associant à un ensemble de clés, un ensemble de valeurs correspondantes.
![Dans tableau associatif, on accéde aux données par une clé(chaîne de caractère), ils ne sont généralement pas ordonnés.](../../../../img/DfK9FySFiR-300.webp)
Il s’agit de l’implémentation d’une structure de données abstraite appelée tableau associatif.
3.1 Interface
Les opérations usuellement fournies par un tableau associatif sont :
- ajout : association d’une nouvelle valeur à une nouvelle clef ;
- modification : association d’une nouvelle valeur à une ancienne clef ;
- suppression : suppression d’une clef ;
- recherche : détermination de la valeur associée à une clef, si elle existe.
3.2 Implémentation en python
Les dictionnaires font partie de la bibliothèque standard de Python grâce à la classe dict
vue
en première.
# création du dictionnaire
personne = {"nom": "Lagaffe", "prenom": "Gaston", "age": 27, "rigolo": True}
# accès à une valeur
personne['age'] # renvoie 27
Les dictionnaires étant mutables, on peut ajouter supprimer ou modifier une valeur à un dictionnaire déjà créé:
# ajout d'une clé
personne["dessinateur"] = "André Franquin"
# suppression d'une clé
del personne["rigolo"]
# modification d'une clé
personne["age"] = 28
# accès à une valeur
personne['age'] # renvoie 28
La recherche d’une valeur d’une valeur est traitée ci-après comme le propose le programme officiel.
4 Recherche d’une valeur
Les méthodes d’itération diffèrent légèrement entre les list
es et le dict
ionnaire
en Python.
4.1 Dans une liste
# on crée une liste vide par compréhension
paires = [2*i for i in range(10)]
print(paires) # affiche [0, 2, 4, 6, 8, 10, 12, 14, 16, 18]
def recherche_liste(liste, élément):
# itération sur les valeurs de la liste
for e in liste:
if e == élément:
return True
return False
# Appels de la fonction
recherche_liste(paires, 3) # renvoie False
recherche_liste(paires, 8) # renvoie True
4.2 Dans un dictionnaire
Il existe trois méthodes d’itération sur les dictionnaires vues en première:
- Itération sur les clés:
keys()
- Itération sur les valeurs:
values()
- Itération sur les paires clé, valeurs:
items()
Pour rechercher une valeur, une itération sur les valeurs suffit.
personne = {'nom': 'Lagaffe', 'prenom': 'Gaston', 'age': 28, 'dessinateur': 'André Franquin'}
def recherche_dict(dico, valeur):
for val in dico.values():
if val == valeur:
return True
return False
recherche_dict(personne, 'André Franquin') # renvoie True
recherche_dict(personne, 'Lagafe') # renvoie False
5 Complexité des opérations
Nous avons déjà défini la complexité temporelle d’un algorithme qui consiste à compter le nombre d’opérations élémentaires effectuées par un algorithme pour aboutir au résultat souhaité.
Nous allons préciser ici ce que l’on entend par opération élémentaire, car parfois lorsque l’on tape une opération celle-ci n’est pas élémentaire.
Une opération est élémentaire si elle a une complexité .
5.1 Cas des list
es
|
|
Complexité |
---|---|---|
Ajout à la fin | liste.append(e) |
|
Insertion d’un élément | liste.insert(i, e) |
|
Suppression à la fin | liste.pop() |
|
Suppression au milieu | liste.pop(i) |
|
Accès à un élément | liste[i] |
|
Modification d’un élément | liste[i] = e |
|
Longueur de la liste | len(liste) |
|
Recherche d’un élément | e in liste |
5.2 Cas des dict
ionnaires
|
|
Complexité |
---|---|---|
Ajout d’un élément | dico[clé] = val |
|
Modification d’un élément | dico[clé] = val |
|
Suppression d’un élément | del dico[clé] |
|
Accès à un élément | dico[i] |
|
Recherche d’une clé | e in dico |
|
Recherche d’un valeur | e in dico.values() |
Note: les complexités données sont moyennes car dans le pire des cas, toutes ses opérations sont en .