Construire et manipuler un tableau
Construire un tableau
Fondamental :
Si un tableau peut contenir plusieurs éléments, il reste toutefois une variable de notre programme. Comme toute variable, nous allons devoir le déclarer avant de pouvoir l’utiliser. Un tableau doit avoir un nom, un type et une taille. Le type d’un tableau indique la présence d’un tableau ainsi que le type des éléments qu’il va contenir.
Variables :
Age : entier[30]
Taille : réel[30]
Début
…
Fin
La notation [ ] indique que nous sommes en présence d’un tableau. Le nombre entre [ ] permet d’indiquer la taille du tableau. « Age » est un tableau d’entiers comportant 30 éléments. « Taille » est un tableau de réels comportant 30 éléments. Dans ce cas-là, les tableaux sont considérés comme non initialisés : nous connaissons leur taille mais le contenu n’est pas encore défini.
Spécifier la taille dès le départ est important car le programme va chercher un emplacement mémoire susceptible de pouvoir stocker le tableau. Si je déclare un tableau de 30 éléments, il faut que je trouve en mémoire un emplacement de 30 zones mémoires contigües :
Même si les éléments du tableau ne sont pas encore renseignés, la zone mémoire dédiée au stockage est réservée. La question du dimensionnement du tableau est donc très importante. Elle doit pouvoir contenir tous les éléments manipulés sans pour autant saturer la mémoire.
Il est possible de définir un tableau à partir des éléments qui le composent :
Variables :
Age : entier[ ] = [22, 18, 25, 33]
Taille : réel[ ] = [1.76, 1.84, 1.81, 1.79]
Début
…
Fin
Remarque :
Cette fois-ci, la taille n’est plus spécifiée, mais la définition du tableau nous indique les éléments constituant le tableau. « Age » est un tableau d’entiers contenant 4 éléments : 22, 18, 25 et 33. Une fois de plus, nous retrouvons tous les éléments nécessaires pour pouvoir déclarer un tableau.
Avec les listes Python, nous avons la possibilité de rajouter un élément à une liste existante. Il est intéressant de comprendre ce qui se passe en mémoire lorsque nous faisons un liste.append(element). En effet, il est possible de gagner énormément de temps de traitement sur cette instruction.
Exemple :
Imaginons un tableau de 4 éléments :
Si je veux ajouter un 5ième élément à ce tableau, je m’aperçois que la zone mémoire après la valeur 24 n’est pas disponible. Je vais donc devoir trouver un nouvel emplacement mémoire qui contient 5 emplacements libres contigus et je vais recopier mon tableau à cet endroit. Ici, nous sommes sur 4 éléments mais si j’ajoute un élément à un tableau de plusieurs milliers d’éléments, il y a de fortes chances que ce tableau soit copié dans un autre emplacement mémoire.
Remarque :
Copier des milliers d’éléments prend du temps. Si vous savez à l’avance combien d’éléments va contenir votre tableau, le mieux est de le déclarer directement à la bonne taille pour éviter les recopies inutiles. Il y a toujours des cas où on ne peut pas prévoir le nombre d’éléments à traiter et dans ces cas-là, nous n’avons pas d’autres choix que de sacrifier un peu de temps de traitement.
Accéder aux éléments d’un tableau
Fondamental :
Un tableau est un élément de structure incontournable pour traiter un grand nombre de valeurs qui représentent la même notion. Cela ne veut pas dire pour autant qu’il devient impossible d’accéder aux éléments d’un tableau de manière individuelle. D’après la représentation mémoire que nous avons présentée, nous savons que la variable tableau pointe sur le premier élément du tableau en mémoire. Nous allons utiliser le fait que les éléments du tableau sont stockés dans des zones mémoire contigües pour pouvoir y accéder facilement.
Lors de la déclaration du tableau, nous avons parlé des crochets [ ]. Les crochets vont nous permettre d’accéder facilement à un élément particulier d’un tableau en fonction de sa position. À chaque élément du tableau correspond un indice de rang qui va nous permettre d’y accéder.
Remarque :
Nous pouvons dire que « 22 » est l’élément du tableau au rang « 0 », « 18 » est l’élément du tableau au rang « 1 » et ainsi de suite. L’opérateur crochet va nous permettre d’accéder directement à un élément en connaissance son rang :
Age[0] va nous renvoyer la valeur 22 (22 est la valeur dans le tableau « age » de l’élément au rang 0).
Age[1] va nous renvoyer la valeur 18 (18 est la valeur dans le tableau « age » de l’élément au rang 1).
Etc.
Remarque :
Nous savons maintenant comment déclarer un tableau et comment accéder à ses éléments. Voici un petit exemple d’algorithme qui reprend ces notions.
Variables :
Age : entier[ ] = [22, 18, 25, 33]
Taille : réel[ ] = [1.76, 1.84, 1.81, 1.79]
Début
Afficher ‘La personne 1 est âgée de ‘ + age[0] + ‘ ans’
Afficher ‘La personne 2 est âgée de ‘ + age[1] + ‘ ans’
Afficher ‘La personne 3 est âgée de ‘ + age[2] + ‘ ans’
Afficher ‘La personne 4 est âgée de ‘ + age[3] + ‘ ans’
Fin
Attention :
Pour quelqu’un qui débute en programmation, il peut être perturbant que les indices de tableau commencent à 0 et non à 1. Pour que ce soit plus clair, le rang dans le tableau correspond au nombre de décalages à faire à partir du début du tableau :
Age[0] : la variable « age » de type tableau d’entiers pointe déjà sur le premier élément de tableau il y a donc 0 décalage à faire et on retourne juste la valeur pointée : 22.
Age[1] : la variable « age » de type tableau d’entiers pointe sur le second élément de tableau il y a donc 1 décalage à faire pour se retrouver sur la zone mémoire suivante : 18.
Et ainsi de suite.
Attention :
S’il y a 4 éléments dans le tableau, ces 4 éléments seront désignés par des indices allant de 0 à 3. Si on veut généraliser cette règle à n’importe quel tableau, un tableau de n éléments verra ses éléments désignés par des indices allant de 0 à n-1.
Modifier un tableau
Fondamental :
Un tableau permet donc de stocker des valeurs en mémoire en les regroupant sous le nom d’une seule et même variable tout en nous permettant d’accéder à chaque élément de manière individuelle. Cependant, les valeurs peuvent être amenées à changer et il est nécessaire de pouvoir modifier les valeurs d’un tableau sans avoir à en recréer un.
Les éléments d’un tableau étant accessibles directement à travers leur indice, il est tout à fait possible de modifier également un élément en y accédant directement :
Variables :
Age : entier[ ] = [22, 18, 25, 33]
Début
Age[1] ← 24
Afficher ‘La personne 2 est âgée de ‘ + age[1] + ‘ ans’
Fin
Remarque :
Age[1] représente l’élément qui se trouve à l’indice 1 du tableau, à savoir la valeur 18 lors de l’initialisation. Le fait que age[1] se retrouve à gauche de l’opération d’affectation indique que sa valeur va être modifiée. Après modification, age[1] vaudra donc 24 et le tableau age sera composé de 4 éléments : [22, 24, 25, 33]. Pour que la modification puisse être faite, il faut bien entendu que la valeur de modification coïncide avec le type du tableau. Il n’est pas possible d’affecter une valeur réelle à un élément d’un tableau d’entiers.
Attention :
La plupart des langages de programmation permettent les opérations d’ajout suivantes :
Ajout d’un élément à gauche (append left). Dans ce cas, un élément est ajouté avant le premier élément et la variable du tableau pointe désormais sur ce nouvel élément.
Ajout d’un élément à droite (append ou append right). Dans ce cas, un élément est ajouté en fin de tableau.
Dans la plupart des cas, ces opérations entrainent une recopie du tableau vers une zone mémoire assez grande pour pouvoir le contenir. Si vous connaissez à l’avance la taille maximale de votre tableau, déclarez cette taille dès le début et effectuez des modifications en accédant à chaque élément par son indice. Votre programme sera plus rapide car il évitera de nombreuse recopies en mémoire.
La plupart des langages permettent également de supprimer un élément bien particulier du tableau. Dans ce cas tous les éléments qui suivent cet élément subiront une copie :
Sur cet exemple, deux copies ont été réalisées :
17 vers le rang 1
24 vers le rang 2
Suivant la taille du tableau, une suppression peut également prendre beaucoup de temps à cause des recopies successives.
La majorité des langages de programmation vont vous permettre de trier un tableau. Les algorithmes de tri pourraient représenter une partie de cours entier tant il y a dire sur le sujet. L’importance des tris en programmation vient du fait qu’il est plus facile de chercher dans un tableau trié. Pour s’en convaincre, il suffit d’imaginer un dictionnaire. Personne ne se servirait d’un dictionnaire si les mots à l’intérieur n’étaient pas triés. En programmation, c’est exactement la même chose.
Exemple :
Nous voulons savoir si la valeur 24 se trouve dans le tableau âge. Si le tableau n’est pas trié, il faudra comparer chaque élément du tableau. Si le tableau est trié, nous savons que si nous atteignons une valeur > 24, ce n’est plus la peine de continuer, toutes les autres seront > 24 également. Cela permet d’éviter des recherches inutiles et donc de gagner du temps.
Parcours de tableau avec une boucle
Une fois toutes nos valeurs rassemblées au sein d’une même variable tableau, nous aimerions construire des algorithmes qui traitent des tableaux entiers et non plus élément par élément. Nous aimerions obtenir par exemple la moyenne des valeurs du tableau sans pour autant avoir à accéder à chaque élément par son indice. Pour cela, nous allons utiliser une structure algorithmique qui permet d’itérer sur une ou plusieurs instructions : la boucle.
Définition :
Une boucle est une structure de contrôle qui permet de répéter plusieurs fois les mêmes instructions. Cela permet au développeur de ne pas avoir à se répéter. Plusieurs styles de boucles existent selon que l’on veut répéter les instructions un nombre de fois déterminé (par exemple 10 fois) ou alors jusqu’à ce qu’une condition soit vraie (avance jusqu’à tomber sur un obstacle). Le sujet des boucles sera détaillé dans une autre partie du cours, nous allons juste nous intéresser ici au parcours des tableaux.
Remarque :
Voici un petit exemple de boucle qui affiche les nombres de 1 à 10.
Début
Pour i de 1 à 10 Faire
Afficher i
Fait
Fin
Remarque :
La variable i est déclarée directement dans l’entête de la boucle. Lors du premier tour de la boucle, elle vaut 1, puis elle est incrémentée de 1 pour valoir 2 dans le second tour. La boucle s’arrête une fois la borne maximum atteinte, ici 10.
Si on reprend ce que l’on vient d’expliquer sur les tableaux, il est donc possible accéder à chaque élément par son indice :
Tab[0] : premier élément du tableau tab
Tab[1] : second élément du tableau tab
Etc.
Pour accéder à l’élément suivant, on ajoute donc juste 1 à l’indice en vérifiant que nous sommes toujours dans le tableau à l’aide de la taille. L’indice étant un nombre entier, nous pouvons le remplacer par une variable de type entier.
Variables :
Indice : entier
Tab :[] = [22, 24, 19, 18]
Début
Indice ← 0
Afficher ‘L’element ‘ + Indice + ‘ est ‘ + tab[indice]
Indice ← indice +1
Afficher ‘L’element ‘ + Indice + ‘ est ‘ + tab[indice]
Indice ← indice +1
Afficher ‘L’element ‘ + Indice + ‘ est ‘ + tab[indice]
Indice ← indice +1
Afficher ‘L’element ‘ + Indice + ‘ est ‘ + tab[indice]
Fin
Ce petit algorithme va simplement écrire :
L’element 0 est 22
L’element 1 est 24
L’element 2 est 19
L’element 3 est 18
Remarque :
Nous avons juste accédé aux différents éléments grâce à notre variable « indice ». L’algorithme est encore long et redondant. Entre chaque affichage, il faut ajouter 1 à l’indice. L’idéal serait d’avoir une structure à laquelle on pourrait dire « tu me fais varier indice de 0 à 3 et pour chaque valeur de cet indice, tu me fais un affichage. » Nous avons de la chance, c’est exactement ce que fait une boucle. Une boucle va répéter une opération un certain nombre de fois et va contrôler le nombre de boucles grâce à un compteur. Notre algorithme précédent peut donc s’écrire avec une boucle :
Variable :
Indice : entier
Tab : entier[] = [22, 24, 19, 18]
Début
Pour indice de 0 à 3 Faire
Afficher ‘L’element ‘ + Indice + ‘ est ‘ + tab[indice]
Fait
Fin
Remarque :
Dans le premier tour de la boucle, l’indice va valoir 0. Dans le second, il va valoir 1 et la boucle va s’arrêter lorsque l’indice vaut 3. Cette structure est intéressante car si nous devons traiter un tableau de 10 000 éléments, il suffit de modifier la valeur finale du compteur (pour indice de 0 à 9 999). En tant que développeur, cela nous fait moins de code à écrire et du coup moins de code à maintenir.