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.

Les tableaux: list

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.

Par Original uploader was Sanao at fr.wikipedia — Transferred from fr.wikipedia; transferred to Commons by User:Bloody-libu using CommonsHelper., Domaine public, Lien

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.

# création
ma_liste = [1, "deux", 3.0]
# accés aux élements par index
ma_liste[1] # renvoie "deux"!

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

# suppression avec la méthode `pop()`
ma_liste.pop(2)
ma_liste # renvoie ['zéro', 1, 3.0]

• Il est également fréquent de souhaiter connaitre la longueur de la liste :

# longueur avec la fonction `len()`
len(ma_liste) # renvoie 3 puisque ['zéro', 1, 3.0]

Différence entre interface et implémentation

Les quatre méthodes qui ont été définies dans la classe list en Python sont ce que l'on appelle une implémentation de la structure de donnée tableau.

Il existe de nombreux langages de programmation qui implémentent le type abstrait $tableau$, nous avions vu l'année dernière les différences d'implémentation entre les list de Python et les Array de javascript.

Implémentation

L'implémentation d'une structure de données ou d'un algorithme est leur mise en œuvre pratique dans un langage de programmation.

Cependant, on retrouve des méthodes similaires qui sont ce que l'on appelle l'interface de la structure de données $tableau$:

1. « Insérer » : ajoute un élément dans le tableau à l'index souhaité. ajout(index, élément) ;
2. « Retirer » : retire un élément de le tableau à l'index souhaité. suppr(index) ;
3. « Le tableau est-il vide ? » : renvoie « vrai » si le tableau est vide, « faux » sinon. est_vide()
4. « 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.

Les dictionnaires: dict

Un dictionnaire, est un type de données associant à un ensemble de clés, un ensemble de valeurs correspondantes.

Il s'agit d'une structure de données abstraite appelée tableau associatif qui a une implémentation native en Python par 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

Méthodes

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.

Article Wikipedia sur le Tableau associatif

Implémentation en Python

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.

Recherche d'une valeur

Les méthodes d'itération diffèrent légèrement entre les listes et le dictionnaire en Python.

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

>>> 8 in paires
True
>>> 7 in paires
False

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

>>> 'André Franquin' in personne
False
>>> 'dessinateur' in personne
True

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.

Cas des listes

Time complexity sur le wiki Python

Cas des dictionnaires

Note: les complexités données sont moyennes car dans le pire des cas, toutes ses opérations sont en $O(n)$.

Time complexity sur le wiki Python