La Programmation en C++ - Les tableaux Les tableaux

tableau.cpp


Bonjour, bonjour. Aujourd'hui, nous abordons le second chapitre avec les tableaux. Qu'est-ce que c'est quoi donc? Rassurez-vous, nous n'allons pas nous mettre à peindre quoi que ce soit. Un tableau en C/C++ est une liste d'un certain nombre de valeurs du même type. Imaginons par exemple que nous voulions enregistrer les 20 derniers relevés de température. Une température peut être représentée par un float, et toutes ces températures forment un ensemble. On va donc les caser dans un tableau, où elles seront toutes rassemblées de manières cohérentes.

Il faudrait voir un tableau comme une famille de variables du même type, d'une taille prédéfinie à l'avance. Ces variables portent toutes le même nom, mais sont différenciées par leur place dans le tableau. Regardez plutôt :

float temp[20];
temp[0] = 17.5;
temp[1] = 20.3;
temp[2] = 13.9;
/* ... */
temp[19] = 15.7;

La première ligne définit un tableau de 20 variables de type float. Le tableau portera le nom temp. Ensuite, chaque élément de ce tableau est repéré par son indice dans le tableau, les indices commençant toujours à 0. Donc dans notre tableau de 20 éléments, on a les variables de type float numérotés de temp[0] à temp[19]. On peut alors considérer temp[?] comme une variable normale, à laquelle on peut affecter une valeur et sur laquelle on peut effectuer des opérations. Ainsi, je peux très bien écrire quelque chose comme :

temp[5] = (temp[4] + 1) / 2;

temp[5] et temp[4] sont deux variables comme les autres, à la différence près que celles-ci, en plus de leur nom, sont caractérisées par un indice.

En mémoire, toutes ces 20 variables sont contigues, c'est-à-dire qu'elles sont placées les unes à la suite des autres. Un tableau de n éléments du type type occupe donc en mémoire n*sizeof(type) octets.

    Lorsque vous précisez le nombre d'éléments d'un tableau en le déclarant, la valeur doit être une constante entière. Vous ne pouvez pas créer un tableau à partir d'une valeur de variable.

Initialisation

Par défaut, les éléments d'un tableau sont initialisés à 0 lors de la création du tableau. Mais parfois, on veut créer un tableau contenant des valeurs prédéfinies. Il existe une syntaxe plus rapide que la méthode utilisée dans notre premier exemple. Voyons un exemple :

int premiers[5] = {2, 3, 5, 7, 11};

Ce tableau contient 5 int représentant des nombres premiers. Comme on connaît les 5 premiers nombres premiers, on peut initialiser directement le tableau avec ces valeurs. En fait, si on utilise cette syntaxe, on n'a pas besoin de spécifier le nombre d'éléments qu'on veut mettre dans le tableau : si on indique 5 valeurs initiales, c'est à priori qu'on veut avoir 5 éléments. Le compilateur crée alors un tableau à 5 éléments, initialisés aux valeurs données entre accolades. La déclaration suivante fait exactement la même chose que la précédente :

int premiers[] = {2, 3, 5, 7, 11};

Mais le nombre de valeurs précisées entre accolades ne doit pas forcément être le même que le nombre d'éléments dans le tableau. Autrement dit, vous n'êtes pas obligé de préciser de valeurs pour tous les éléments du tableau. Si il y a moins de valeurs dans la liste entre accolades que dans le tableau, ces valeurs seront appliquées aux premiers éléments du tableau, les éléments restant étant bien sûr initialisés à 0 :

int premiers[5] = {2, 3, 5};
for(int i = 0; i <= 4; i++) cout << premiers[i] << endl;

Cet exemple produit l'affichage suivant :

2
3
5
0
0

    Par contre, l'inverse n'est pas possible : vous ne pouvez pas préciser plus de valeurs entre accolades qu'il n'y en a dans le tableau.

    int premiers[5] = {2, 3, 5, 7, 11, 13, 17};

    Si vous tentez de compiler cet exemple, le compilateur vous dira quelque chose comme Too many initializers, soit trop de valeurs initiales.

On retiendra que si un nombre d'éléments est précisé dans la déclaration d'un tableau et que des valeurs initiales sont données entre accolades, le nombre de valeurs initiales doit être inférieur ou égal au nombre d'éléments du tableau.

Les avantages des tableaux

Les avantages des tableaux ne sont pas immédiats à voir mais ils sont réels. Un tableau est la plupart du temps utilisé pour contenir un ensemble de valeurs qui vont subir plus ou moins les mêmes traitement. Il est complètement intutile de créer un tableau pour contenir des valeurs qui n'ont rien à voir les unes avec les autres, comme par exemple le nombre de voitures vendues dans le monde l'an dernier, l'âge du capitaine et le vitesse en MHz de votre processeur : ces valeurs n'ont rien en commun et vous n'en utiliserez pas 2 de la même façon. Il est donc inutile de faire un tableau pour cela. Par contre, un tableau peut servir à regrouper les notes d'un élève, ou des températures enregistrées tous les mois, ou encore les différents prix d'un produit au cours du temps. Le traitement appliqué à l'un des éléments du tableau peut alors être appliqué à tous les autres éléments, et le résultat obtenu aura la même signification.

Aujourd'hui, nous sommes obligés de dire que les tableaux doivent être déclarés avec un nombre fixé de valeurs, car il nous manque quelques connaissances. Plus tard (dans pas trop longtemps, lorsque nous parlerons de la gestion dynamique de la mémoire), nous verrons qu'il est possible de créer des tableaux de tailles non définies à l'avance, c'est-à-dire avec des valeurs variables, ce qui nous donnera encore plus de flexibilité. On constatera alors qu'il est aussi aisé de manipuler un tableau de 5 éléments qu'un tableau de 5000 éléments.

Comme les valeurs d'un tableau sont indexées par un entier, tout traitement collectif de ces valeurs peut se faire grâce à une boucle, comme le montre l'un des exemples précédents où nous affichions les valeurs d'un tableau une à une. Ainsi, quelque soit la taille du tableau, on peut utiliser une simple boucle pour travailler dessus. Imaginez la galère que ce serait si on avait 500 variables différentes et qu'on devait en faire la somme puis le produit!!! Avec un tableau de 500 éléments, ces calculs sont immediats :

const int NB_VALEURS = 500;
int valeurs[NB_VALEURS];
/* Initialisation des valeurs
(par saisie ou par calcul direct) */

int somme = 0;
int produit = 1;

for(int i = 0; i < NB_VALEURS; i++)
{

    somme += valeurs[i];
    produit *= valeurs[i];

}

Avouez que c'est facile, non?

Parfois, on se sert de tableaux pour stocker des valeurs précalculées, afin d'accélere un peu la vitesse d'exécution d'un programme. Par exemple, les calculs mettant en jeu les fonctions sin() et cos() (définies dans math.h) sont très longs, mais on en a souvent besoin d'en faire beaucoup lorsqu'on fait de la 3D par exemple. On peut alors créer deux tableaux tblSin[] et tblCos[] dans lesquels ont place toutes les valeurs de sin et de cos dont on aura besoin, et ainsi on peut les récuperer infiniment plus vite qu'en refaisant le calcul à chaque fois. On dit alors que ce sont des lookup tables. C'est une des nombreuses techniques qu'on utilise pour optimiser la vitesse d'exécution d'un programme, et je ne vous en parle qu'à titre indicatif : nous ne nous préocuperons pas de la vitesse de nos programme dans ce cours, car ce n'est ni nécessaire, ni simple. C'était juste pour vous donner encore un exemple d'avantages que peut représenter le tableau.

L'un des inconvénients du tableau est qu'il n'y a pas de moyen immédiat de connaître son nombre d'éléments. Ici, on a définit une constante pour fixer le nombre d'éléments du tableau, mais ce n'est pas toujours le cas. Par contre, il existe un moyen détourné. Prenons le tableau ci-dessus : il y a 500 ints, donc le tableau prend 500*4 octets (voir Les types de variables si ce n'est pas clair). L'opérateur sizeof permet de connaître la taille du tableau en octets, ainsi que la taille d'un int. On obtient alors le nombre d'éléments du tableau en faisant la division de l'un par l'autre :

int tableau[14];
cout << "Nombre d'éléments : " << (sizeof(tableau) / sizeof(int)) << endl;

Tableaux à plusieurs dimensions

Dans une certaine mesure, tableau peut-être considéré comme un type en lui-même. Pourquoi alors ne pas faire un tableau de tableaux? Imaginons que nous sommes en train d'écrire un petit programme qui affiche une image. Une image est un quadrillage dont chaque point est défini par deux coordonnées et une couleur. Nous dirons que les couleurs sont codées sur des int. Notre image aura pour dimensions 50*25, c'est-à-dire 50 colonnes et 25 rangées, ou encore un tableau de 50 tableaux de 25 éléments chacuns. Ce n'est pas clair ?

Dans un tableau d'entiers, chaque élément est un entier. On identifie chaque élément de la sorte : tabl[i]. Ici, tabl[i] est un entier. Si maintenant on crée un tableau de tableaux d'entiers, chaque élément est un tableau. On identifie alors chaque élément de la même façon, c'est-à-dire avec tabl[i], à part que cette fois-ci, tabl[i] est un tableau, contenant lui-même des entiers. Prenons le premier tableau d'entiers. Il s'appelle tabl[0]. Le premier élément de ce tableau s'appelle alors, tout naturellement, tabl[0][0]. Le troisième entier du sixième tableau s'appelle, de la même façon, tabl[5][2].

Imaginer des tableaux de tableaux n'est pas facile, surtout lorsqu'on arrive aux tableaux de tableaux de tableaux... et on peut continuer. Pour des tableaux de dimensions 2 ou 3, on peut imaginer qu'ils représentent un plan ou un espace, et que chaque élément de ces tableaux sont repérés par leurs coordonnées (2 dans un plan, 3 dans un espace). Si on revient à notre image à dessiner, on peut très bien utiliser deux coordonnées pour placer un point. On fera alors :

int image[50][25];
image[13][10] = COULEUR_ROUGE;

On crée un plan de dimensions 50*25, chaque case contenant un int, et après on décide que la case (13, 10) contient du rouge (en supposant qu'il y ait une constante COULEUR_ROUGE définie quelque part avant).

Un autre exemple : on veut maintenant créer un jeu de dames. Il y a un damier de 8 cases sur 8, avec des cases noires et des cases blanches. Supposons que 0 signifie noir, 1 signifie blanc, voici comment déclarer et initialiser notre damier :

int damier[8][8];
for(int x = 0; x < 8; x++)

    for(int y = 0; y < 8; y++)

      damier[x][y] = (x + y) % 2;

On aura alors un cadrillage comme il faut. Il existe, pour initialiser un tableau à deux dimensions, une syntaxe similaire à celle de l'initialisation d'un simple tableau. Prenons comme exemple un tableau d'entiers de 3*3 :

int tabl[3][3] = {{4, 3, 6},{10, 0, 0},{-1, 5, 3}};

Voici le tableau créé par cette ligne :

4 10 -1
3 0 5
6 0 3

tabl[2][1] == 5.

Affichage

Vous savez maintenant qu'une variable de type fondamental peut être affichée avec cout. Mais pour afficher un tableau, il n'y a pas de moyen prédéfini, il faut donc le faire soi-même. Pour l'exemple on utilisera le tableau définit ci-dessus.

Nous avons vu qu'il y avait des caractères spéciaux qui, lors de l'affichage, permettaient de contrôler un peu celui-ci. Ainsi, le caractère '\n' permet de revenir à la ligne. Aujourd'hui, je vais introduire le caractère '\t' qui permet de faire une tabulation, et donc de faire des colonnes. Voici un moyen d'afficher joliment le tableau ci-dessus :

int tabl[3][3] = {{4, 3, 6},{10, 0, 0},{-1, 5, 3}};

for(int y = 0; y < 3; y++)
{

    for(int x = 0; x < 3; x++)

      cout << tabl[x][y] << '\t';

    cout << endl;

}

Voici l'affichage produit par ce programme :

4
10 -1
3 0 5
6 0 3

Le caractère tabulation permet donc d'aligner verticalement tous les nombres. Bien sûr, rien ne vous empêche d'afficher votre tableau autrement, ceci n'est qu'une proposition.

Un tableau comme argument d'une fonction

Bien sûr, au même titre que les autres types de variables, vous pouvez passer un tableau comme argument d'une fonction :

void AfficheTableau(int tableau[], int n)
{

    for(int i = 0; i < n; i++)
    {

      cout << tableau[i] << '\t';
      if(i%5 == 4) cout << endl;

    }

}

int main(void)
{

    int table[100];
    for(int i = 0; i < 100; i++)

      table[i] = i*i;

    AfficheTableau(table, 100);

}

Ce petit programme affiche sur 5 colonnes les valeurs du tableau table grâce à la fonction AfficheTableau(), qui prend comme paramètre un tableau d'entiers et la taille du tableau (le nombre d'éléments qu'il contient). Dans la fonction AfficheTableau(), vous ne pouvez pas savoir la taille du tableau grâce à l'opérateur sizeof, vous devez donc passer comme argument sa taille. 

Lecture/écriture en dehors des limites d'un tableau

Que se passe-t-il si on fait référence à une case d'un tableau lorsque celle-ci n'est plus dans les limites du tableau ?

Le C, créé à la base pour faire des programmes rapides (et ainsi remplacer dans une certaine mesure l'assembleur), ainsi que le C++, ne font absolument aucune vérification concernant les tableaux lors de l'exécution et de la compilation d'un programme. Ainsi, vous pouvez impunément écrire quelque chose du genre :

int tabl[3] = {2, 3, 4};
cout << tabl[3] << endl;
tabl[4] = 7;

Manifestement, tabl[3] et tabl[4] n'ont pas été définis, puisque tabl est un tableau à 3 éléments (0 ... 2). Et pourtant, ce programme va compiler. Et si vous avez de la chance, il va même s'exécuter correctement, et plus loin dans le programme, vous pourrez utiliser tabl[4] comme n'importe quelle autre variable.

Par contre, si vous avez moins de chance, et c'est ce qui arrive le plus souvent, la tentative d'écriture se passera assez mal et votre programme plantera. Qui fait le malin tombe dans le ravin, comme dirait un ami à moi :-) La lecture, elle, devrait dans tous les cas vous produire un résultat pour le moins inatendu : la valeur de l'élément fantome n'ayant pas été initialisée, elle est celle que contient cet endroit de la mémoire à ce moment-là. Souvent, c'est n'importe quoi, en particulier avec les tableaux de char.

Vous l'aurez compris, mieux vaut ne rien faire en dehors des limites d'un tableau, sous peine de se voir renvoyé comme un malpropre par le système. Pas toi, je t'ai déjà dit pas de baskets!

Un type de tableaux particulier

Nous avons déjà vu les chaînes de caractères : "ceci est une chaîne". Et bien en réalité, ce ne sont ni plus ni moins que des tableaux de chars. Voici un exemple :

char chaine[] = {'c', 'o', 'u', 'c', 'o', 'u', '!'};
cout << chaine << endl;

Nous reconnaissons bien sûr la déclaration d'un tableau, son initialisation, et une instructions d'affichage.

La première remarque que vous pourriez me faire, c'est que l'initialisation semble très laborieuse : faut-il vraiment écrire toutes ces apostrophes et ces accolades pour représenter une chaîne ? Alors que nous les avons écrites avec des guillemets jusqu'ici ? Vous avez parfaitement raison. L'exemple que je vous ai donné là est la manière standard pour initialiser un tableau, quelque soit le type utilisé. Un tableau de char est donc initialisé avec une liste de char. Mais voilà : ce n'est pas pratique, et les chaînes de caractères sont tellement courantes que le C++ (comme le C) nous permet de l'écrire avec des guillemets, plus simples :

char chaine[] = "coucou!";
cout << chaine << endl;

La notation avec les guillemets est donc réservée aux chaînes de caractères. Bien sûr, vous pouvez accéder (lecture/écriture) à chaque caractère de cette chaine de la même manière que vous accedez aux éléments d'un tableau d'entiers. Pour écrire une lettre sur 2 à l'écran, faites :

char chaine[] = "coucou, c'est nous!";
for(int i = 0; i < sizeof(chaine) - 1; i += 2)

    cout << chaine[i];

cout << endl;

Deux petits mots sur cet exemple : tout d'abord, les char ne font qu'un octet, il n'y a donc pas besoin de faire de division avec l'opérateur sizeof pour obtenir la longueur de la chaîne.

Si vous avez bien regardé, vous vous êtes sans doute rendu compte que la boucle s'arrête à l'avant-dernier élément de la chaîne. Parquoi diable ?

Ce qu'il faut savoir (et que vous ne savez pas encore), c'est qu'une chaîne de caractères au sens C/C++ se termine toujours par un caractère nul : encore un caractère spécial, noté '\0'. Dans le premier exemple que je vous ai donné, le tableau de char contenait exactement la liste de char donnée entre accolades. Mais avec les guillemets, le caractère nul est rajouté à la fin de la chaîne. Donc une chaine de 5 lettres occupera 6 octets en mémoire. Comme écrire un caractère nul n'est pas plus passionant que cela, on s'arrête avant celui-ci.

Je ne m'avancerais pas plus loin dans les chaînes de caractères pour le moment, mais sachez que leur manipulation pourrait faire l'objet de tout un livre (bon, d'accord, pas un livre trop gros, mais au moins un petit bouquin de poche! :-). Plus tard, j'y consacrerais un cours, mais d'ici là, nous verrons plusieurs outils qui nous permettront de mieux comprendre les tableaux et les chaînes de caractères.

Application

Pour le programme du jour, je vous propose de remplir un tableau avec des entiers et ensuite de le trier par ordre croissant. L'algorithme n'est pas difficile :

A la fin, le tableau sera classé dans l'ordre. La permutation se fait grâce à une variable intermédiaire. Voici le programme :

1

2
3

4
5
6

7

8

9
10

11
12
13

14

15

16

17

#include <iostream.h>

int main(void)
{

    int tabl[] = {10, 4, 5, 2, 1, 7, 10, 3};
    int longueur = sizeof(tabl) / sizeof(int);
    int temp = 0;

    for(int i = 1; i <= longueur; i++)

      for(int j = 0; j < longueur - 1; j++)

        if(tabl[j] > tabl[j+1])
        {

          temp = tabl[j];
          tabl[j] = tabl[j+1];
          tabl[j+1] = temp;

        }

    while(longueur--)

      cout << tabl[longueur] << endl;

}

Je ne pense pas que ce programme ne nécessite plus d'explications que cela. A la ligne 15, je ne m'encombre pas d'une boucle for : je sais que longueur contient exactement le nombre d'éléments du tableau tabl, et je ne m'en servirais plus par la suite, ce qui fait que je peux l'utiliser comme compteur. Notez que dans cette boucle, d'abord la valeur de longueur est utilisée pour le test, ensuite celle-ci est décrémentée et enfin, l'affichage se produit (la décrémentation se fait juste avant le contenu de la boucle dans ce cas-ci).

Voici les quelques points importants :

  • Un tableau à n éléments est un ensemble de n variables contigües en mémoire et différenciées par un index. Toutes ces variables sont de même type au sein d'un même tableau.
  • Les membres d'un tableau à n éléments sont compris entre 0 et n-1.
  • L'opérateur sizeof permet de connaître la taille d'un tableau (moyennant une petite division).
  • Le nombre d'éléments d'un tableau est précisé avec une variable entière et constante.
  • Lorsqu'on initialise un tableau avec une liste ({a, b, ...}), le nombre d'éléments retenu est celui précisé entre crochets (si il est précisé), sinon c'est le nombre d'éléments compris dans la liste.
  • Une tentative d'écriture en dehors des limites d'un tableau peut se solder par un plantage du programme.

Et pour vous faire la main avec les tableaux, très importants :

  • Faites un petit programme qui crée 2 tableaux de même taille et qui copie le contenu de l'un dans l'autre.
  • Implémentez ceci dans le programme du jour afin qu'une copie du tableau d'origine seulement soit classée (l'original restant intact).
  • Il existe de nombreuses manières de classer un tableau, et j'ai exposé ici la plus économique en code. C'est sans doute l'une des moins efficaces, et je vous encourage à en chercher d'autres par vous-même. Même celle-ci peut être un peu optimisée. Cependant, vu le nombre d'éléments à classer, vous ne verriez pas la différence entre les méthodes. Mais aussi pourriez vous utiliser un tableau plus grand (10000 éléments!!!) et le remplir grâce à une boucle (en impliquant un sinus, par exemple, afin de ne pas avoir les nombres déjà classés).
  • Faites un petit programme qui fait la moyenne des valeurs contenues dans un tableau (somme des valeurs divisée par le nombre de valeurs).
  • Rajoutez au programme du jour une belle petite fonction pour afficher le résultat sur des colonnes.
  • En créant deux chaînes de caractères de même longueur, recopiez le contenu de l'une dans l'autre. Ensuite, la même chose, mais en sens inverse (pensez au dernier caractère nul, qui lui doit être à la fin!).
  • Attention, voici un petit défi pour les plus hardis d'entre vous :

    Il s'agid du problème des huit reines. Il s'agit de placer huit reines sur un échiquier de 64 cases (8x8) sans qu'aucune d'entre-elles ne puisse en prendre une autre (je vous rappelle qu'une reine peut aller vers le haut, le bas, gauche, droite et diagonales, d'autant de cases qu'elle veut). Je vous propose donc de faire un petit programme qui tente de placer (de manière bête et disciplinée) ces 8 reines.

    Pour l'échiquier, on pourra utiliser un tableau à 2 dimensions (8x8 également), dont les cases marquées d'un 1 sont occupées, les autres étant à 0. Pour chaque tentative de placer une reine dans une case vide, il faut au préalable vérifier toute la rangée, la colonne et les 4 diagonales, afin de s'assurer qu'aucune reine ne fait obstacle. Ce programme se fait de manière récursive le plus élégamment du monde, chaque étage de la récursivité s'occupant de placer une reine et se rappellant pour placer la suivante. Il ne faut pas trop de temps pour trouver la solution (quelques secondes), et dès que la solution est trouvée, les coordonnées des huit reines s'affichent à l'écran, afin que vous puissiez vérifier la solution. C'est un poil compliqué, mais abordable pour ceux qui ont déjà fait de la programmation.

    Je vous conseille de revoir le cours sur la récursivité pour bien vous en imprégnier. Cet exercice vous fera travailler à la fois les tableaux, mais aussi la récursivité, les fonctions et tout plein de petites choses qui croustillent sous la dent.

    Comme l'exercice est un peu difficile, les trois meilleures solutions que vous m'enverrez seront publiées ici! Alors, à vos claviers.

Si vous réussissez le dernier exo, vous savez que vous êtes bien parti!!! Enfin bon. La semaine prochaine, nous verrons comment créer nos propres types de variables, qui seront des assemblages de données, afin de créer des groupes cohérents. Nous verrons également un type un peu particulier de constantes.


Voir aussi: Les types de variables - la récursivité