Blog ENI : Toute la veille numérique !
-25€ dès 75€ sur les livres en ligne, vidéos... avec le code FUSEE25. J'en profite !
Accès illimité 24h/24 à tous nos livres & vidéos ! 
Découvrez la Bibliothèque Numérique ENI. Cliquez ici
  1. Livres et vidéos
  2. Algorithmique
  3. Les tableaux et structures
Extrait - Algorithmique Techniques fondamentales de programmation - Exemples en Python (nombreux exercices corrigés) - BTS, DUT informatique (Nouvelle édition)
Extraits du livre
Algorithmique Techniques fondamentales de programmation - Exemples en Python (nombreux exercices corrigés) - BTS, DUT informatique (Nouvelle édition) Revenir à la page d'achat du livre

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...