Structures de données

Cours/Algorithmie/Structures de données/Structures de données

Un structure de donnée généralise les tuples et est une version algorithmique des objets de la programmation orientée objet. Une fois définis on pourra utiliser une structure comme un nouveau type de variable.

Attributs

Par défaut une structure de donnée va posséder des attributs qui regroupent les objets de la structure. Pour notre point en 2D on aurait la structure :

structure Point:
    attributs:
        x: entier
        y: entier

Par rapport au tuple, les attributs sont des variables et possèdent ainsi des noms. Si on accède aux éléments d'un tuple avec son indice, on accède aux attributes par la notation pointée :

algorithme affiche_point(p: Point) → vide:
    affiche à l'écran p.x
    affiche à l'écran p.y

En notation pointée a.b signifie que b dépend de a.

Si p est un point, p.x signifie que x est la valeur de l'attribut x pour le point p.

On peut tout à fait modifier les attributs d'un objet. Par exemple la fonction :

algorithme additionne_point(p1: Point, p2: Point) → vide:
    p1.x ← p1.x + p2.x
    p1.y ← p1.y + p2.y

Va modifier les attributs du premier paramètre.

Notation pointée en python

Création

Définition

Créer un objet d'une structure revient à créer ses attributs. La taille en mémoire d'un objet est proportionnelle à la taille de ses attributs.

Ainsi le code :

p ← un nouveau Point

Va créer un nouveau point p pour le quel on pourra accéder à ses attributs via la notation pointée :

p.x ← 0

Comme toute variable nouvellement crée les valeurs des attributs est indéterminée : il faut toujours initialiser avant de les utiliser.

Initialisation par défaut

Pour être sur que les paramètres sont initialisés par défaut, on utilise l'abus suivant :

structure Point:
    attributs:
        x: entier ← 1
        y: entier ← -1

Qui correspond au code :

p ← un nouveau Point
p.x ← 1
p.y ← -1

On peut bien initialiser partiellement les paramètres (en ne donnant qu'un valeur par défaut à x par exemple), mais ce n'est pas recommandé :

À retenir

Dans la mesure du possible donnez toujours une valeur par défaut à tous les attributs.

Initialisation explicite

Si l'on veut avoir des valeurs spécifiques pour nos attributs sans alourdir le code, on utilise l'abus suivant :

p ← Point {x: 3, y: 12}

Qui correspond au code :

p ← un nouveau Point
p.x ← 3
p.y ← 12

Les valeurs non explicitement assignées aurons les valeurs par défaut s'il y en a.

Constructeur

On utilisera tout au long de ce cours le processus de construction d'objets suivant :

Construction

les différents attributs sont crées sous la forme de variables
les initiations explicites des attributs sont effectuées
les initiations par défaut des attributs sans initialisation explicite sont effectuées

Une bonne pratique algorithmique est qu'au terme de ce processus tous les attributs soient initialisés.

Ainsi pour la structure suivante :

structure Point:
    attributs:
        x: entier
        y: entier ← 2 * x

Le code suivant produira des valeurs indéterminées pour p.x et p.y :

p ← Point

Le code suivant sera tel que p.y = 6 :

p ← Point {x: 3}

Le code suivant sera tel que p.y = 42 :

p ← Point {x: 3, y: 42}

Que donnent les exemples précédent avec la structure :

structure Point:
    attributs:
        x: entier ← 0
        y: entier ← 2 * x

corrigé

p ← Point : p.x = 0 et p.y = 0
p ← Point {x: 3} : p.x = 3 et p.y = 6
p ← Point {x: 3, y: 42} : p.x = 3 et p.y = 42

Méthodes

L'intérêt fondamental des structures de données est de leur associer des fonctions spécifiques, appelées méthodes. Le but des méthodes est d'opérer sur les objets de la structure. Transformons la fonction additionne_point précédente en méthode :

structure Point:
    attributs:
        x: entier ← 0
        y: entier ← 0
    méthodes:
        fonction addition(p: Point) → vide:
            x ← x + p.x
            y ← y + p.y

On appelle les méthodes avec la notation pointée :

p1 ← un nouveau Point
p2 ← Point {x: 4, y: 7}

affiche à l'écran p1.x et p1.y  # affiche 0 et 0
p1.addition(p2)
affiche à l'écran p1.x et p1.y  # affiche 4 et 7

Dans le code de l'addition, la notation pointée assure que les variables x et y des lignes 10 et 11 d la définition sont celle de l'objet à gauche de l'appel, ici p1 dans le programme précédent.

Résumé

À retenir

Une structure de données est composée :

d'attributs qui correspondent aux différentes données la constituant (de types de base ou d'autres structures de données). On accède au attributs et aux méthodes d'une structure avec la notation pointée.
de méthodes qui sont des fonctions permettant d’interagir avec une donnée de cette structure.

Une structure de donnée défini un nouveau type qui peut être utilisé ensuite comme un type de base.

Une fois une structure de données définie, on pourra l'utiliser comme un type de base dans tous nos algorithmes. La taille d'une structure est déterminée par rapport à la taille de ses attributs :

Pour qu'une structure de donnée puisse être utilisée, il est crucial de connaître la complexité de la création d'un objet de la structure ($\mathcal{O}(1)$ pour notre Point) et de chaque méthode de celle-ci.

Génériques

Tout come un tableau peut stocker tout type de données, il peut être intéressant de définir une structure générique, c'est à dire pouvant gérer plusieurs types de la même façon, plutôt que de définir une structure par type.

type générique

Pour être explicite, On signifie la généricité entre "<>" dans la définition de la structure, par exemple dans l'exemple suivant :

structure Point<T>:
    attributs:
        valeur: T

        x: entier ← 0
        y: entier ← 0

L'attribut valeur est du type générique T. Ce type est abstrait et doit être défini explicitement à l'utilisation. Par exemples :

utm ← Point<chaîne> {valeur: "Marseille", x: 694669, y: 4796927}
masse ← Point<réel> {valeur: 3.14}

On peut bien sur combiner le tout avec des exemples plus ou moins tordu comme :

[Point<réel>] : un tableau de Points à valeurs réelles
Point<[Point<Point<chaîne>>]> : un Points à valeurs valant un tableau de Point à valeur de Point de chaînes.

Mais la plupart du temps, on reste simple.

Mot clé `self`

L'objet courant, celui qui appelle (à gauche du . en notation pointée), peut être parfois nommé par le mot-clé self.

Certains langages comme python n'autorisent que cette notation ce qui rend le code sans ambiguïté, d'autres comme le java autorise les deux versions (avec ou sans self).

Cela permet d'utiliser la notation pointée partout (et est indispensable si l'on veut connaître l'objet appelant pour le rendre par exemple. Voir l'exemple suivant). En utilisant cette convention, le pseudocode de la structure devient :

structure Point:
    attributs:
        x: entier ← 0
        y: entier ← 0
    méthodes:
        fonction addition(p: Point) → Point:
            self.x ← self.x + p.x
            self.y ← self.y + p.y

            rendre self

Dans l'exemple précédent utiliser x ou self.x est équivalent. Rendre l'objet appelant est une technique très utilisées en programmation objet car elle permet ce genre de code :

p1 ← Point {x: -2, y: 3}
p2 ← Point {x: 4, y: 7}
p3 ← Point {x: 12, y: 21}

affiche à l'écran p1.x et p1.y  # affiche 0 et 0
p1.addition(p2).addition(p3)
affiche à l'écran p1.x et p1.y  # affiche 14 et 31

La ligne p1.addition(p2).addition(p3) sera exécutée de gauche à droite :

p1.addition(p2) rendre l'objet p1
on effectue .addition(p3) sur l'objet rendu (c'est à dire p1)

Enfin, souvent, on n'utilise que partiellement cette convention puisque si une variable à le même nom qu'un attribut, c'est l'attribut. Par exemple :

structure Point:
    attributs:
        x: entier ← 0
        y: entier ← 0
    méthodes:
        fonction addition(p: Point) → Point:
            x ← x + p.x
            y ← y + p.y

            rendre self