Structures de données¶

Note

Le type Struct proposé dans ce cours n'est pas standard en Python. Il a été programmé pour les besoins du cours, notamment pour approcher de manière progressive la notion de classe, qui sera abordée dans la deuxième partie du cours.

Une structure est un ensemble non ordonné de valeurs ayant potentiellement des types différents. Les valeurs que contient la structure sont appelées ses champs, et sont identifiés par un nom.

Un type de structure (ou type de données structuré) spécifie un ensemble de champs (leur nom et leur type).

Pré-requis

Afin d'utiliser les structures en Python, il est nécessaire :

de télécharger le module algo.py à l'adresse http://champin.net/2012/algo.py
d'inclure la ligne suivante dans tous les programmes utilisant les structures :
```
from algo import Struct
```

Déclaration d'un type de structure¶

Pour déclarer un type de structure, on utilisera une déclaration de la forme suivante :

première ligne :
- le mot-clé class,
- le nom du nouveau type,
- le texte (Struct),
- le caractère deux points (:).
lignes suivantes (indentées par rapport à la première)
- le nom d'un champ
- le caractère =
- le nom du type associé à ce champ

Par exemple :

from algo import Struct

class Date(Struct):
    année=int
    mois=int
    jour=int

class Lieu(Struct):
    nom=str
    long=float
    lat=float

Notons que les champs d'une structure peuvent avoir eux même un type structuré :

class Personne(Struct):
    nom=str
    naissance=Date

Déclaration d'une structure¶

Une fois déclarés un ou plusieurs types structurés, il est possible de créer une donnée correspondant à un de ces types ainsi :

le nom du type

une parenthèse ouvrante (

une liste de valeurs pour les champs, sous la forme nom=valeur, et séparées par des virgules,

une parenthèse fermante ).

NB: l'ordre des champs n'a pas d'influence.

Par exemple :

>>> d = Date(jour=23, mois=6, année=1912)
>>> p = Personne(nom="Alan Turing", naissance=d)

Opérations sur les structures¶

Les seules opérations sur les structures consistent en la lecture et la modification de leurs champs, en utilisant la « notation pointée » : on accède au champ en indiquant le nom de la structure, suivi d'un point, suivi du nom du champ :

>>> p.nom
'Alan Turin'
>>> p.d
Date(jour=22, mois=6, année=1912)
>>> p.nom = "Alan Turing"  # modification d'un champ
>>> p.nom
'Alan Turing'

Dans le cas où un champ contient lui même une structure, on peut enchaîner plusieurs notations pointées :

>>> p.naissance.année
1912
>>> p.naissance.jour = 23

Notons enfin que, comme les tableaux, les structures sont des objets mutables. Lorsque deux variables font référence à la même structure, les modifications sur l'une des variables sont donc répercutées sur l'autre :

>>> alan = p
>>> alan.nom
'Alan Turing'
>>> alan.nom = "Alan M. Turing"
>>> p.nom  # le changement sur alan est également visible sur p
'Alan M. Turing'

Comparaison de structures¶

Les structures peuvent être comparées avec les opérateurs == et !=, mais attention : ces opérateurs ne comparent que l'identité des structures. Deux structures créées indépendamment seront toujours considérées comme différentes, mêmes si leurs champs sont tous égaux :

>>> d1 = Date(jour=1, mois=1, année=1970)
>>> d2 = Date(jour=1, mois=1, année=1970)
>>> d1 == d2
False

La raison en est que l'équivalence de deux structures dépend de la sémantique de ses champs. Ainsi, deux personnes ayant le même nom et la même date de naissance ne sont pas forcément la même personne. Inversement, on peut avoir un type structuré dont deux structures ayant des valeurs de champs différentes représenteraient néanmoins le même objet, par exemple :

class Droite(Struct):
    a=float
    b=float
    c=float
    # représente la droite
    # d'équation ax + by + c = 0

Pour tester l'équivalence entre deux structures du même type, il convient donc d'écrire une fonction spécifique qui tiennent compte de la sémantique particulière des champs.