Table des matières

Sujet précédent

7. Structures de contrôle

Sujet suivant

9. Bibliothèque standard (The Python Standard Library)

8. Structures de données

Les types prédéfinis que nous avons vus sont insuffisants pour traiter des données plus complexes. On peut citer deux exemples. On veut représenter un élève qui est caractérisé son nom, son prénom, sa date de naissance, sa moyenne générale, etc. On voudrait qu’une seule variable conserve et donc donne accès à toutes ces informations. En algorithmique, on définirait alors un type enregistrement Eleve regroupant ces informations. Le type Eleve est alors le produit cartésien d’une chaîne de caratère (le nom), d’une deuxième chaîne de caractère (le prénom), d’une date (la date de naissance), d’un nombre (la moyenne générale), etc.

Dans un deuxième exemple, on voudrait pouvoir définir une classe avec tous les élèves qui apparatiennent à la classe. Dans ce cas, on veut représenter des informations de même type, les élèves, dont l’ordre n’a pas d’importance et pourrait être changé (les élèves pourraient être rangés de manière aléatoire, classés par ordre alphabétique de leur nom, classés en fonction de leur moyenne générale, etc.). En algorithmique, on utilise alors un tableau. Un tableau est un type de données qui permet de regrouper un nombre fini d’éléments ayant tous le même type. Les éléments sont repérés par leur position (appelée indice) dans le tableau (souvent l’entier 0 pour le premier élément).

Ces deux types de données, enregistrement et tableau, n’existent pas vraiment en Python. Pour les tableaux, on s’appuiera sur le type List de Python. Pour les enregistrements, plusieurs solutions sont possibles : les tuples, les dictionnaires ou les classes. Nous préviligerons les classes dans un mode très dégradé.

8.1. Tableau en Python (List)

Attention : Nous ne présentons ici qu’un tout petit sous-ensemble des possibilités du tpye List de Python. Le but est en effet de ne présenter que les éléments qui permettent de _simuler_ les tableaux algorithmiques .

Remarque : Pour des tableaux numériques de grande taille, on utilisera le type array de la bibliothèque Numpy qui offre une implémentation efficace.

Définition : Une liste est un agrégat d’éléments qui sont repérés par leur position (ou indice).

Python étant typé dynamiquement, aucun type n’est imposé sur les éléments de la liste qui peuvent donc être hétérogènes.

En algorithmique, quand on déclare un tableau, on précise sa capacité, le nombre maximal d’éléments qu’il pourra stocker, et on est souvent amené à gérer une taille effective, le nombre d’éléments réellement stockés dans le tableau. En Python, le programmeur n’a pas à se préoccuper de la capacité car l’espace de stockage des éléments sera agrandi quand de nouveaux éléments seront ajoutés. Il obtient la taille effective de la liste (le nombre d’éléments qu’elle contient) grâce à la fonction len().

TODO : montrer plutôt les opérateurs du langage : + et += plutôt que append et extend

8.1.1. En Python

>>> l = []   # liste vide
>>> type(l)
<class 'list'>
>>> l
[]
>>> l.append('b')   # ajout d'un élément à la fin
>>> l
['b']
>>> 'a' in l   # teste l'appartenance de 'a' à la liste
False
>>> l.extend(['c','d','d','e'])   # ajout des éléments d'une autre
...                               # liste à la fin (concaténation)
>>> l
['b', 'c', 'd', 'd', 'e']
>>> l.insert(0, 'a')   # ajout d'un élément à une position donnée
>>> l
['a', 'b', 'c', 'd', 'd', 'e']
>>> 'a' in l   # teste l'appartenance de 'a' à la liste
True
>>> len(l)   # nombre d'éléments dans la liste
6
>>> l[2]   # accès à un élément par sa position
'c'
>>> l[2:4]   # accès à une sous-liste
['c', 'd']
>>> del l[3]   # suppression d'un élément (par sa position)
>>> l
['a', 'b', 'c', 'd', 'e']
>>> l[3] = 'D'   # modification d'un élément
>>> l
['a', 'b', 'c', 'D', 'e']
>>> max(l)   # maximum de la liste (ordre lexicographique)
'e'
>>> min(l)   # minimum de la liste (ordre lexicographique)
'D'
>>> l.reverse()   # inverse l'ordre des éléments dans la liste
>>> l
['e', 'D', 'c', 'b', 'a']
>>> l.sort()   # trier la liste (ordre lexicographique)
>>> l
['D', 'a', 'b', 'c', 'e']
>>> [6, 7, 6, 7, 6].count(6)   # compter le nombre d'occurence
...                            # d'un élément
3
>>> list( (1,2,3) )   # contruire une liste (ici à partir d'un tuple)
[1, 2, 3]

8.2. Enregistrement (struct)

8.2.1. Définition algorithmique

Définition algorithmique : Un enregistrement est un type correspondant à un agrégat d’élément de types éventuellement différent auxquels ont accède grâce à un nom.

Exemple :. On peut définir un note comme étant une valeur (nombre), un coefficient (nombre) et une matière (chaîne de caratères). Les noms « valeur », « coefficient » et « matière » sont alors les champs de l’information et permettent d’accèder à l’une des données d’une note.

8.2.2. En Python

Le type enregistrement n’utilise pas. On peut utiliser les tuples, les dictionnaire (dict) ou les classes.

8.2.2.1. Les tupes

Définition : Un tuple est une valeur composée de plusieurs valeurs.

# note de valeur 15, coefficient 1.5 en programmation
>>> n1 = (15, 1.5, "programmation")
>>> n1
(15, 1.5, 'programmation')
>>> _, c, _ = n1      # récupérer le coefficient
>>> print(c)
1.5
>>> v, _, m = n1      # récupérer la valeur v et la matière m
>>> n1 = (v, 2.5, m)  # pour changer le coefficient en 2.5
>>> n1
(15, 2.5, 'programmation')

Propriété : Un tuple est immuable (il ne peut pas être modifié). Chaque « modification » revient à créer un nouveau tuple (et non à modifier le tuple existant).

Inconvénient : dans un tuple, on ne peut pas nommer les éléments. Ils sont uniquement repérés par leur position (proche de la notion de List).

8.2.2.2. Dictionnaire (dictionary, map)

Définition : Un dictionnaire est une structure de données dite associative, car elle permet de stocker une valeur en lui associant une clé. Cette clé permet ensuite de retrouver la valeur associée.

Pour définir un type Note composé d’une note, d’un coefficient et d’une matière, on pourra alors utiliser un dictionnaire et trois clés (“valeur”, “coefficient” et “matiere”) pour stocker et accéder aux trois valeurs de la note.

# initialiser un(e varialbe de type) enregistrement
>>> n1 = dict(valeur=15, coefficient=1.5, matiere="programmation")
# on peut l'afficher
>>> print(n1)
{'matiere': 'programmation', 'coefficient': 1.5, 'valeur': 15}
# accéder à un champ de l'enregistrement
>>> n1["valeur"]
15
# modifier la valeur d'un champ d'un enregistrement
>>> n1["coefficient"] = 2.5
>>> n1
{'matiere': 'programmation', 'coefficient': 2.5, 'valeur': 15}
>>> "valeur" in n1  # Est-ce qu'un champ "valeur" existe sur un n1 ?
True
>>> "moyenne" in n1
False

8.2.2.3. Les classes

Attention : Ici nous nous appuyons sur la notion de classe pour retrouver un type Enregistrement proche de celui qui existe en algorithmique. Nous n’utilisons donc pas du tout la puissance des classes.

Pour définir un type enregistrement, par exemple Note, on écrira :

class Note:
    pass

On peut ensuite créer une valeur de type Note en faire Note().

n1 = Note()

On peut ajouter les champs nécessaires.

n1.matiere = "programmation"
n1.valeur = 15
n1.coefficient = 1.5

Et y accéder.

>>> c = n1.coefficient
>>> c
1.5

On peut changer la valeur d’un champ.

n1.coefficient = 2.5
>>> print(n1.matiere, ":", n1.valeur, "coefficient", n1.coefficient)
programmation : 15 coefficient 2.5

8.2.2.4. Enregistrement et sous-programmes

Il est vivement conseillé de définir des sous-programmes pour manipuler un type enregistrement. Ceci est tout particulièrement vrai pour l’initialisation.

Nous donnons ci-après un exemple pour le cas d’un enregistrement défini à partir du type class, mais on pourrait faire quelque chose d’équivalent si l’enregistrement était défini par un tuple ou un dictionnaire.

def nouvelle_note(matiere, valeur, coefficient):
    """nouvelle_note(str, number, number) -> Note"""
    resultat = Note()
    resultat.matiere = matiere
    resultat.valeur = valeur
    resultat.coefficient = coefficient
    return resultat

def afficher_note(note):
    """afficher_note(Note)"""
    print(bote.matiere, ":", bote.valeur, "coefficient", bote.coefficient)

On peut alors faire :

n1 = nouvelle_note("programmation", 15, 1.5)
n2 = nouvelle_note("allemand", 16.5, 2)
afficher_note(n1)
afficher_note(n2)

En utilisant un peu plus la notion de classe on pourrait remplacer la fonction de création d’une note par le constructeur de la classe, c’est une fonction appelée __init__ qui prend comme premier paramètre la note à initialiser (son nom est self par convention).

class Note:
    def __init__(self, matiere, valeur, coefficient):
        """nouvelle_note(Note, str, number, number) -> Note"""
        self.matiere = matiere
        self.valeur = valeur
        self.coefficient = coefficient

Quand on crée la note, on fournit dans les parenthèses les paramètres effectifs qui correspondent aux paramètres formels de __init__ à l’exception de self qui est implicite. L’exemple précédent s’écrit alors tout simplement comme suit.

n1 = Note("programmation", 15, 1.5)
n2 = Note("allemand", 16.5, 2)
afficher_note(n1)
afficher_note(n2)