Editions ENI Livres | Vidéos | e-Formations
Les tableaux et structures
Introduction
Jusqu’à présent, nous nous sommes préoccupés de variables qui n’avaient aucun lien logique entre elles. Dans ce chapitre, nous allons étudier comment stocker et manipuler plusieurs valeurs qui sont liées entre elles afin de pousser encore plus loin notre réflexion et surtout nos algorithmes et programmes.
Les tableaux
Imaginez une liste de courses simple : vous devez acheter douze œufs, du beurre demi-sel, une salade, deux barquettes de fraises et trois tablettes de chocolat. Chaque élément de cette liste est un produit à acheter.
Avec ce que nous avons appris, votre premier instinct serait de créer une variable pour chaque produit :
PROGRAMME Liste_course_var
VAR
produit1 : CHAINE
produit2 : CHAINE
produit3 : CHAINE
produit4 : CHAINE
produit5 : CHAINE
i : ENTIER
DEBUT
ECRIRE("Entrer un produit à acheter)
produit1 <- LIRE()
ECRIRE("Entrer un produit à acheter)
produit2 <- LIRE()
...
FIN Cet algorithme paraît lourd, rébarbatif, peu judicieux… Si vous devez ajouter un produit à acheter, vous allez devoir réécrire cet algorithme en ajoutant une variable produit6 et la valeur finale du compteur de la structure itérative POUR. Vous allez en fait réécrire cet algorithme à chaque fois que vous voulez ajouter ou enlever un produit.
Cette logique va à l’inverse de l’algorithmie : l’algorithme doit prendre en compte le plus de cas possibles pour être le plus générique possible.
Pour pallier ce problème, il existe une structure de données particulière qui permet de stocker plusieurs valeurs de même type : les tableaux. Avec cette nouvelle structure, vous allez également simplifier la saisie et la manipulation de ces valeurs tout en écrivant un algorithme plus compréhensible et donc maintenable.
1. Tableaux à une dimension
Une variable de type tableau peut contenir plusieurs valeurs, la seule obligation est que ces valeurs soient de même type en algorithmie. Les tableaux se déclarent en même temps que les autres variables. Un tableau à une dimension représente une liste de valeurs. Un tableau à deux dimensions peut être vu comme la feuille d’un tableur avec...
Manipulations simples des tableaux
1. Tableaux à une dimension
a. Parcours
Pour parcourir un tableau, nous devons aller de la première case de la ligne à la dernière. Cela indique donc que nous devons déclarer un compteur et, qui dit compteur, dit structures itératives POUR.
PROGRAMME Parcours_tableau_une_dimension
VAR
jours <- {"lundi", "mardi", "mercredi", "jeudi", "vendredi",
"samedi", "dimanche"} : TABLEAU[1...7] : CHAINE
i: ENTIER
DEBUT
POUR i ALLANT DE 1 A 7 AU PAS DE 1
FAIRE
ECRIRE("Le jour ",i," est ", jours[i])
FINPOUR
FIN Un tableau se parcourt toujours avec une boucle POUR où le compteur nous permet de récupérer toutes les valeurs du tableau car il est également égal à l’indice courant de la case.
b. Recherche
La recherche d’une valeur est une opération courante en informatique. Elle se fait avec un parcours de tableau. À chaque case du tableau, nous allons vérifier si la valeur de l’élément courant est égale à la valeur recherchée.
PROGRAMME Recherche_tableau_une_dimension
VAR
jours <- {"lundi", "mardi", "mercredi", "jeudi", "vendredi",
"samedi", "dimanche"} : TABLEAU[1...7] : CHAINE
jour_a_chercher : CHAINE
i: ENTIER
trouve <- FAUX : BOOLEEN
DEBUT
ECRIRE("Entrer le nom du jour à chercher")
jour_a_chercher <- LIRE()
i ALLANT DE 1 A 7 AU PAS DE 1
FAIRE
SI jours[i] = jour_a_chercher
ALORS
trouve <- VRAI
FINSI
FINPOUR
...Structures et enregistrements
1. Structures
Lorsque nous avons modélisé notre liste de courses avec l’algorithme Liste_courses_tableau_deux_dimensions, nous nous sommes aperçus d’un problème de type de données. La quantité est représentée par une chaîne de caractères et non un entier, ce qui n’est pas logique car nous ne pouvons pas faire de calcul sur cette quantité, comme la décrémenter de 1 par exemple.
La STRUCTURE algorithmique permet justement de corriger ce problème : dans un tel type, nous pouvons lier plusieurs variables de types différents ou non. La STRUCTURE permet de lier des variables dans une seule et même variable. Ces variables sont appelées les champs de la structure.
STRUCTURE nom_structure
DEBUT
champ1 : type1
champ2 : type2
...
FINSTRUCTURE La définition de la structure se déclare juste avant le PROGRAMME. La déclaration d’une variable de TYPE structure se fait comme pour les variables d’autres types. Nous appelons ces variables des enregistrements.
VA
mon_enregistrement : nom_structure Nous pouvons donc modéliser notre liste de courses avec la STRUCTURE suivante :
STRUCTURE produit
DEBUT
nom : CHAINE
quantité : ENTIER
FINSTRUCTURE À la différence des autres types de variables...
Mettons en pratique avec Python
1. Tableau = liste
Les tableaux en algorithmie sont appelés listes en Python.
Une liste est une variable qui contient plusieurs expressions (ou valeurs) qui ne sont pas forcément du même type, contrairement à l’algorithmie. Ce principe respecte donc le typage dynamique du langage.
Une liste est un type de donnée dit mutable : elle peut changer de valeur et de taille.
Une liste a également un autre avantage sur le tableau : elle est de taille dynamique, nul besoin d’en déclarer la taille ! La gestion des indices se fait également automatiquement.
Dans tous les langages de programmation, hors les implémentations du langages SQL comme par exemple TransactSQL, nous commençons à compter à partir de 0. Le premier élément d’une liste est donc d’indice 0 (à la position 0 de la liste) en Python.
Les indices en Python peuvent être positifs ou négatifs :
-
Positifs pour aller du premier élément d’une liste aux autres.
-
Négatifs pour commencer par le dernier élément de la liste.
Ainsi, si nous voulons accéder au dernier élément d’une liste, nous demanderons l’élément numéro "taille de la liste -1" en indice positif ou tout simplement l’élément d’indice -1 pour les indices négatifs.
Une liste se déclare avec l’opérateur d’indexation [ ]. Si la liste est vide, nous ne mettons rien entre les crochets, sinon on y ajoute la liste des expressions séparées par des virgules. L’accès aux éléments d’une liste se fait comme en algorithmie grâce à l’opérateur d’indexation.
ma_liste_vide = []
ma_liste_taille_1 = ["je suis le premier élément d'indice 0"]
ma_liste_taille_n = [1, "deux", True, 3.14]
print("Deuxième élément de la liste de taille n :",
ma_liste_taille_n[1])#affiche Deuxième élément de la liste
de taille n : deux Comme en algorithmie, Python donne également la possibilité de créer des tableaux à n dimensions, une paire de crochets par dimension.
board = []
# Initialisation ...Exercices
1. Exercice 1
Écrivez un algorithme qui recherche dans un tableau d’entiers la plus grande et la plus petite valeur du tableau. Codez le script Python correspondant.
2. Exercice 2
Écrivez un algorithme qui recherche dans un tableau d’entiers les indices de la plus grande et de la plus petite valeur du tableau. Codez le script Python correspondant.
3. Exercice 3
Écrivez un algorithme qui calcule la moyenne des valeurs d’un tableau d’entiers. Codez le script Python correspondant.
4. Exercice 4
Écrivez un algorithme qui calcule le nombre d’occurrences d’une valeur entrée par l’utilisateur dans un tableau d’entiers (le nombre de fois que la valeur apparaît dans le tableau). Codez le script Python correspondant.
5. Exercice 5
Écrivez un algorithme qui réalise l’inversion des éléments d’un tableau sans utiliser de tableau intermédiaire. Codez le script Python correspondant.
6. Exercice 6
Écrivez un algorithme qui permet de représenter un niveau d’un jeu. Chaque niveau est composé d’un plateau de jeu (une matrice de dix par dix caractères), d’un nombre d’objets et d’un boss. Un boss possède comme information un nom et des points de vie.
7. Exercice 7
Le drapeau hollandais : le tableau de cet algorithme ne contient que les valeurs entières 1, 2 et 3. Vous...
