Découvrez le fonctionnement des algorithmes

Agencez les informations entre elles

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.

Dans ces structures de données, vous pouvez créer, lire, modifier ou même supprimer des éléments. On parle alors de type d’opération que vous pouvez effectuer sur votre structure, il en existe bien d'autres.

Le type d’opération 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

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 liste des objets éparpillés dans le labyrinthe :

Dans un tableau, chaque élément est associé à sa position dans la liste à l’aide d’un indice commençant à 0. Exactement comme dans une liste numérotée !

Cette position est appelée indice ou index. Attention, petite feinte : le premier élément de la liste est à l’index 0 et non 1 !  ;-)

Selon le tableau ci-dessus, voici les points importants à considérer.

• L'index commence par 0.

• La taille du tableau est de 3, ce qui signifie qu'il peut stocker 3 éléments.

• Chaque élément est accessible via son indice. Par exemple, nous pouvons récupérer un élément à l'index 1 en tant que  Pied de biche  .

Dans le pseudo-code, vous pouvez déclarer le tableau  objets  avec 5 cases par exemple, comme ceci : 

Algorithme Tableau
Variable
    objets[5] : TABLEAU CHAÎNE DE CARACTÈRES
Début
Fin

Pour expliciter :

• Vous devez tout d’abord donner le nom du tableau et ensuite mettre entre crochets la taille du tableau. 

• Puis vous donnez le type du tableau précédé par les deux points. 

• Il est aussi intéressant de donner le type de valeur contenu dans chaque case. Dans notre cas, j’ai spécifié que c’est un tableau de chaînes de caractères.

Avantages et inconvénients

D’une part, 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é.

D’autre part, 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.

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.

Ainsi, une liste chaînée est une structure de données linéaire qui comprend une série de nœuds connectés. Ici, chaque nœud stocke les données et l'adresse du nœud suivant ; le dernier élément de la liste aura une adresse vide.

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 faciles, mais l’accès à un élément plus long.

Avantages et inconvénients

Dans une liste chaînée, vous pouvez facilement ajouter un élément en début de liste et ensuite ajouter de nouveaux éléments en queue de liste. Mais c’est un peu plus compliqué, car il vous faut parcourir toute la liste avant de trouver un nœud dont l’adresse est vide. Concernant la recherche d’un élément, vous allez devoir parcourir la liste du début à la fin jusqu’à le trouver.

Parfois, vous êtes amené à associer deux éléments ensemble, mais actuellement, vous ne pouvez pas simplement associer un index et un élément avec les listes chaînées. Les tables de hachage vont vous permettre d’associer deux éléments de type quelconque. On parlera alors ici de l’association d’une clé et d’une valeur.

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 :

Un tableau qui stocke la correspondance entre le type du véhicule et le nombre de roues :

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 !

Opérations courantes

Pour retrouver une valeur, vous indiquez sa clé, contrairement à l’index dans un tableau.

Considérons que la table de hachage précédente est nommée  roues  ; pour récupérer le nombre de roues pour une voiture, nous devons écrire roues[“voiture”]  .

Les tables de hachage sont très flexibles : vous pouvez ajouter ou supprimer des données rapidement.

Structures de données particulières

Mais que se passe-t-il si vous voulez accéder à vos données selon leur ordre d’arrivée ? Par exemple, si vous voulez trouver en premier la toute première information ajoutée ?

Laissez-moi vous présenter les piles et les files !

Qu’est-ce qu’une pile ?

Il s’agit d’une structure de données qui donne accès en priorité aux dernières données ajoutées. Ainsi, la dernière information ajoutée sera la première à en sortir.

Les piles sont ce que l’on appelle un traitement des données LIFO (Last In First Out, ou dans la langue de Molière : dernier ajouté, premier parti), très pratique lorsque nous aurons à utiliser en premier les dernières données ajoutées.

Les piles sont très utilisées sur les plateformes de streaming musical comme Spotify ou Deezer par exemple. Lorsque vous demandez à la plateforme de lire une chanson à la suite, elle va ajouter cette dernière tout en haut de la liste "en attente de lecture".

Les piles (de type LIFO) s’utilisent lorsque vous devez traiter en priorité les dernières données arrivées. Nous retrouvons ce système dans les placards de notre cuisine ou dans notre frigo : ce qui est mis en avant est ce que l’on va consommer le plus vite ! C’est également le cas dans le flux d’actualités de Facebook ou d’Instagram (la dernière information arrivée est la première que vous voyez), bien que ces plateformes utilisent également des algorithmes de curation pour montrer à l'utilisateur le contenu le plus adapté à ses besoins.

Mais que se passe-t-il si nous avons besoin d’accéder non pas aux dernières données ajoutées, mais aux premières ? C’est exactement ce qui se passe lorsque vous constituez une liste de musique. Vous ajoutez peu à peu les chansons qui seront lues dans le même ordre : les premières chansons ajoutées sont les premières lues. Impossible de réaliser cela avec une pile. C’est pourquoi les files existent !

Qu’est-ce qu’une file ?

Une file (queue, en anglais) est une structure de données dans laquelle on accède aux éléments suivant la règle du premier arrivé premier sorti, ou encore FIFO (First In First Out).

Elle suit la même logique que les files d’attente (au McDrive, à Pôle Emploi...) : plus vous arrivez tôt et plus vous partez tôt !  ;-)

Prenons un exemple de notre vie courante. Vous vous rendez à la poste, car vous avez reçu un colis. Vous prenez un ticket qui vous indique votre place dans la file d’attente. Vous comparez alors ce numéro avec celui qui s’affiche, et vous avez une idée du nombre de personnes avant vous. Vous râlez : si seulement vous étiez arrivé plus tôt, vous auriez moins attendu ! Premier arrivé, premier servi (et premier parti !)...

Les files (de type FIFO) s’utilisent lorsque vous devez traiter un flux de données par ordre d’arrivée. C’est le cas lorsque vous faites une to-do list (votre première action est celle que vous devez réaliser en priorité), ou que vous listez les bugs en attente de traitement.

À vous de jouer

Contexte

Voici notre nouveau labyrinthe :

Vous avez pu remarquer que dans certaines cases il y a des clés.

• Chaque clé a son petit nom, et vous en identifierez trois différentes dans ce labyrinthe. 

• Le joueur possède un sac pour contenir l’ensemble des clés.

• Il va devoir toutes les ramasser avant de rejoindre la case Arrivée.

• S’il ne possède pas toutes les clés, il ne pourra pas ouvrir la porte pour sortir. 

• Le sac sera ainsi assimilé à un tableau dans notre algorithme.

Vous utiliserez les deux fonctions suivantes pour insérer des données et récupérer la taille du tableau :

• insérer()  : cette fonction permet d’insérer une donnée dans le tableau, par exemple :  nom_du_tableau.insérer(“Votre donnée”)

• taille()  : cette fonction retourne le nombre de valeurs dans le tableau, par exemple :  nom_du_tableau.taille()

Par ailleurs, vous allez pouvoir appeler la fonction  déplacement  pour gérer les déplacements du joueur.

Consigne

Vous devez tout d’abord créer une fonction qui permet d’insérer le nom de la clé dans le tableau une fois que le joueur passe dessus.

Ensuite vous allez devoir créer l’algorithme qui permet de gérer les déplacements, et qui vérifie si le joueur est passé sur un objet, et tout cela dans une boucle  Tant que  . Effectivement, la boucle s'arrêtera une fois que le joueur aura ramassé tous les objets et qu’il sera sur la case Arrivée.

Votre objectif :

1. Construire une fonction  ramasser  qui prend en paramètres le tableau et les coordonnées du joueur. Cette fonction va gérer l’insertion des noms des clés dans le tableau une fois que le joueur passe dessus.

   1. Dans un premier temps, créer 6 variables pour assigner les coordonnées  x   et  y   de chaque clé.

   2. Dans un second temps, créer plusieurs structures conditionnelles pour gérer l’insertion des noms dans le tableau, en fonction des coordonnées du joueur et des objets.

2. Construire l’algorithme qui va appeler la fonction  déplacement  et  ramasser  dans une boucle  Tant que  . N’oubliez pas de mettre la condition de boucle, et de créer l’ensemble des variables nécessaires.

Vérifiez votre travail

Voici les deux étapes à suivre pour obtenir  le résultat à l'issue de l'exercice :

Première étape: construction de la fonction  ramasser

Algorithme ramasser(clés, joueur_position_x, joueur_position_y)
Variable
    volante_position_x ← 1 : ENTIER
    volante_position_y ← 3 : ENTIER
    passe-partout_position_x ← 5 : ENTIER
    passe-partout_position_y ← 3 : ENTIER
    celeste_position_x ← 0 : ENTIER
    celeste_position_y ← 4 : ENTIER
Début
    Si volante_position_x == joueur_position_x ET volante_position_y == joueur_position_y :
        clés.insérer(“clé volante”)
    Fin Si
    
    Si passe-partout_position_x == joueur_position_x ET passe-partout_position_y == joueur_position_y :
        clés.insérer(“clé passe-partout”)
    Fin Si
    
    Si celeste_position_x == joueur_position_x ET celeste_position_y == joueur_position_y :
        clés.insérer(“clé celeste”)
    Fin Si
Fin

Seconde étape: construction de l'algorithme qui appelle les fonctions ramasser  et  deplacement

Algorithme Labyrinthe
Variable
    joueur_position_x ← 0 : ENTIER
    joueur_position_y ← 0 : ENTIER
    arrivée_position_x ← 5 : ENTIER
    arrivée_position_y ← 5 : ENTIER
    clés[3] : TABLEAU CHAÎNE DE CARACTÈRES
Début
    Tant Que joueur_position_x != arrivée_position_x ET joueur_position_y != arrivée_position_y ET clés.taille() != 3:
        déplacement(joueur_position_x, joueur_position_y)
        ramasser(clés, joueur_position_x, joueur_position_y)
    Fin Tant Que
Fin

En résumé

• Les structures de données sont utilisées pour stocker et organiser les données. C'est une façon d'organiser les données sur un ordinateur afin qu'elles puissent être consultées et mises à jour efficacement.

• Nous pouvons distinguer trois types de structures de données basiques :

  • Dans un tableau, les éléments stockés sont disposés de manière contiguë. Chaque case d’un tableau est identifiée à l’aide de son index.

  • Une liste chaînée est une séquence de structures de données, qui sont reliées entre elles par des liens.

  • La table de hachage est une structure de données qui stocke les données de manière associative. Dans une table de hachage, chaque valeur de donnée a sa propre clé unique qui constitue l’identifiant de la case.

• Nous avons également deux autres types de structures de données plus complexes :

  • Dans la structure de données en pile, les éléments sont stockés selon le principe LIFO. Autrement dit, le dernier élément stocké dans une pile sera le premier à sortir.

  • La structure de données en file fonctionne selon le principe FIFO où le premier élément stocké dans la file sera le premier à sortir.

Dans le chapitre suivant, nous nous intéresserons à deux structures de données bien utiles pour retrouver des données selon les liens qu’elles entretiennent les unes avec les autres. À tout de suite !