• 4 hours
  • Easy

Free online content available in this course.

Videos available in this course

Certificate of achievement available at the end this course

Got it!

Last updated on 5/20/19

Agencez les informations entre elles

Log in or subscribe for free to enjoy all this course has to offer!

Les différents types définis et utilisés dans un programme s’appellent des structures de données. Elles peuvent être comparées à des constructions en Lego qui ont un but assez particulier : roue, fenêtre, carrosse ou encore lac.

Il en est de même pour les structures de données en programmation. Nous serons vite limités si nous entrons les données une à une dans un algorithme. Nous aimerions parfois entrer plusieurs données déjà organisées d’une certaine manière pour améliorer l’efficacité d’un algorithme. Ou bien nous aimerions générer une certaine structure pour qu’elle puisse être utilisée par ailleurs.

Il existe de multiples structures de données, mais nous allons nous concentrer sur les plus connues :

  • tableaux, listes chaînées et dictionnaires ;

  • piles et files ;

  • arbres binaires et graphs.

Opérations

Une opération est une utilisation possible de la structure de données. De manière générale, nous retrouverons ces quatre opérations basiques :

  • Créer

  • Lire

  • Modifier

  • Supprimer

Les trois dernières dépendent également d’une autre opération : la recherche ! Il faut en effet trouver l’élément demandé dans une structure avant de pouvoir le lire, le modifier ou le supprimer.

Le type d’opérations que nous souhaitons effectuer déterminera notre choix de structure, certaines étant plus efficaces pour la recherche et d’autres pour la création ou la suppression de nouveaux éléments. Commençons tout de suite par les tableaux !

Tableaux

Présentation

Un tableau est une structure qui permet de mémoriser plusieurs données de type semblable ou différent. Autrement dit, cela ressemble en beaucoup de points aux tableaux de notre vie quotidienne.

Un tableau qui stocke la correspondance entre le diamètre d’un arbre et sa taille :

Diamètre

Taille

10

50

20

100

Un autre qui liste des joueurs de l’OM :

Joueurs

Roger Scotti

Steve Mandanda

Brice Samba

Un tableau s’implémentera différemment selon les langages de programmation. Par exemple, voici la liste des joueurs en C :

const char *joueurs[] = {"Roger Scotti", "Steve Mandanda", "Brice Samba"};

Opérations courantes

Dans un tableau, chaque élément est associé à sa position dans la liste. Exactement comme dans une liste numérotée !

Vous retrouvez un élément en indiquant sa position. Exemple en Python :

>>> roger = joueurs[0]
"Roger Scotti"

Avantages et inconvénients

Dans plusieurs langages, la taille d’un tableau est fixe. Autrement dit, vous ne pouvez pas ajouter ou supprimer les données d’un tableau. Il vous faut en faire une copie intégrant vos ajouts ou vos suppressions. Ce n’est pas très pratique si vous devez changer fréquemment la taille de ce tableau. Dans ce cas, vous préférerez d’autres structures de données telles que les listes chaînées.

Néanmoins, il est très facile de lire ou de modifier une donnée d’un tableau grâce à son index. Chaque donnée ayant un numéro, il vous suffit de le connaître et le tour est joué.

Listes chaînées

Une liste chaînée (Singly-linked list en anglais) est un ensemble de valeurs enregistrées dans des endroits différents de la mémoire. À la différence d’un tableau qui contient un nombre fixe d’éléments, la liste chaînée est très souple : vous pouvez ajouter ou supprimer des éléments à votre guise.

On dit que toute valeur d’une liste chaînée est une cellule. Chaque cellule est reliée aux autres par des pointeurs.

Qu’est-ce qu’un pointeur ?

Un pointeur est, de manière très schématisée, l’adresse d’un autre élément. Pour les personnes ayant déjà fait de la programmation, il s’agit d’une variable qui contient une adresse mémoire. Cela vous permet de savoir où est enregistrée une autre donnée.

Une liste chaînée est un peu comme une chasse au trésor informatique. Votre première cellule est comme le premier indice : elle contient l’adresse vous permettant de vous rendre au second indice et ainsi de suite. Le dernier endroit visité n’a pas d’indice. L’informatique n’aimant pas le vide, nous dirons que le dernier élément d’une liste a un pointeur égal à 'valeur nulle' ('NULL' en C, 'None' en Python...).

La première cellule est appelée cellule "de tête", car aucune autre cellule ne pointe sur elle.

La dernière cellule est appelée cellule "de queue", car son pointeur est de valeur nulle.

À quoi ça sert exactement ?

Dans un tableau, toutes les informations sont stockées de manière contiguë dans la mémoire de votre ordinateur. Cela permet d’accéder plus facilement aux données, mais il est, de fait, moins flexible. Une liste chaînée rend l’ajout et la suppression de valeurs plus facile, mais l’accès à un élément plus long.

Opérations courantes

Insertion en tête de liste

Insérer un élément en début de liste est très facile : vous commencez par le premier élément ! Cela demande peu de mémoire et de temps.

Insertion en queue de liste

L’ajout d’une cellule en queue de liste est un peu plus compliqué que l’insertion en tête de liste. Pourquoi ? Car il vous faut parcourir toute la liste avant de trouver la cellule dont le pointeur est nul.

Retrouver une valeur en parcourant la liste

Étant donné que nous ne savons pas où se trouve la valeur recherchée, nous allons commencer par le premier élément de la liste, puis avancer jusqu’à le trouver. Retrouver une valeur demande de parcourir une partie (voire la totalité) de la liste avant de trouver une correspondance.

Tables de hachage

Une table de hachage est une structure de données qui vous permet d’associer une valeur à une clé et non plus à un indice. Cette clé peut être un mot ou un chiffre. Par exemple :

{"name": "Dolorès", "address": "New Hampshire"}

Les tables de hachage ne comportent pas d’ordre. Contrairement aux tableaux, vous ne pouvez pas retrouver un élément via sa position, mais uniquement via sa clé. Il s’agit d’une structure très commune et très pratique !

On les appelle également des dictionnaires. Pourquoi ? Car les tables de hachage fonctionnent de la même manière : elles associent une clé (un mot dans le cas d’un dictionnaire) à une valeur (la définition d’un mot).

Opérations courantes

Pour retrouver une valeur, vous indiquez sa clé. Par exemple en Python :

>>> lolita = {"name": "Dolorès", "address": "New Hampshire"}
>>> lolita["address"]
"New Hampshire"

Les tables de hachage sont très flexibles : vous pouvez ajouter ou supprimer des données rapidement. À noter que plusieurs langages n’ont pas ce type de données en natif : il faut l’implémenter si l’on souhaite l’utiliser.

Découvrez un exemple d’implémentation de table de hachage en C.

Example of certificate of achievement
Example of certificate of achievement