Précédent Remonter Suivant

Chapitre 4  Tableaux

La possibilité de manipuler des tableaux se retrouve dans tous les langages de programmation; toutefois Java, qui est un langage avec des objets, manipule les tableaux d'une façon particulière que l'on va décrire ici.

4.1  Déclaration, construction, initialisation

L'utilisation d'un tableau permet d'avoir à sa disposition un très grand nombre de variables en utilisant un seul nom et donc en effectuant une seule déclaration. En effet, si on déclare un tableau de nom tab et de taille n contenant des valeurs de type typ, on a à sa disposition les variables tab[0],tab[1], ..., tab[n-1] qui se comportent comme des variables ordinaires de type typ.

En Java on sépare la déclaration d'une variable de type tableau, la construction effective d'un tableau et l'initialisation du tableau.

La déclaration d'une variable de type tableau de nom tab dont les éléments sont de type typ, s'effectue par1:
  typ[] tab;
Lorsque l'on a déclaré un tableau en Java on ne peut pas encore l'utiliser complètement. Il est en effet interdit par exemple d'affecter une valeur aux variables tab[i], car il faut commencer par construire le tableau, ce qui signifie qu'il faut réserver de la place en mémoire avant de s'en servir.

L'opération de construction s'effectue en utilisant un new, ce qui donne:
  tab = new typ[taille];
Dans cette instruction, taille est une constante entière ou une variable de type entier dont l'évaluation doit pouvoir être effectuée à l'exécution. Une fois qu'un tableau est créé avec une certaine taille, celle-ci ne peut plus être modifiée.

On peut aussi regrouper la déclaration et la construction en une seule ligne par:
  typ[] tab = new typ[taille];
L'exemple de programme le plus typique est le suivant:
  int[] tab = new int[10];

  for(int i = 0; i < 10; i++)
      tab[i] = i;    
Pour des tableaux de petite taille on peut en même temps construire et initialiser un tableau et initialiser les valeurs contenues dans le tableau. L'exemple suivant regroupe les 3 opérations de déclaration, construction et initialisation de valeurs en utilisant une affectation suivie de {, }:
  int[] tab = {1,2,4,8,16,32,64,128,256,512,1024};
La taille d'un tableau tab peut s'obtenir grâce à l'expression tab.length. Complétons l'exemple précédent:
  int[] tab = {1,2,4,8,16,32,64,128,256,512,1024};

  for(int i = 0; i < tab.length; i++)
      System.out.println(tab[i]);
Insistons encore une fois lourdement sur le fait qu'un tableau en Java commence nécessairement à l'indice 0.

Si tab est un tableau dont les éléments sont de type typ, on peut alors considérer tab[i] comme une variable et effectuer sur celle-ci toutes les opérations admissibles concernant le type typ, bien entendu l'indice i doit être inférieur à la taille du tableau donnée lors de sa construction. L'interpréteur Java vérifie cette condition et une exception est levée si elle n'est pas satisfaite.

Donnons un exemple simple d'utilisation d'un tableau. Recherchons le plus petit élément dans un tableau donné:
    static int plusPetit(int[] x){
        int k = 0, n = x.length;

        for(int i = 1; i < n; i++)
            // invariant : k est l'indice du plus petit
            //             élément de x[0..i-1]
            if(x[i] < x[k])
                k = i;
        return x[k];
    }

4.2  Représentation en mémoire et conséquences

La mémoire accessible au programme peut être vue comme un ensemble de cases qui vont contenir des valeurs associées aux variables qu'on utilise. C'est le compilateur qui se charge d'associer aux noms symboliques les cases correspondantes, qui sont repérées par des numéros (des indices dans un grand tableau, appelés encore adresses). Le programmeur moderne n'a pas à se soucier des adresses réelles, il laisse ce soin au compilateur (et au programme). Aux temps historiques, la programmation se faisait en manipulant directement les adresses mémoire des objets, ce qui était pour le moins peu confortable2.

Quand on écrit:
    int i = 3, j;
une case mémoire3 est réservée pour chaque variable, et celle pour i remplie avec la valeur 3, celle de j recevant la valeur 0 (en Java). Quand on exécute:
    j = i;
le programme va chercher la valeur présente dans la case affectée à i et la recopie dans la case correspondant à j.

Que se passe-t-il maintenant quand on déclare un tableau?
    int[] tab;
Le compilateur réserve de la place pour la variable tab correspondante, mais pour le moment, aucune place n'est réservée pour les éléments qui constitueront tab. C'est ce qui explique que quand on écrit:
class Bug1{
    public static void main(String[] args){
        int[] tab;

        tab[0] = 1;
    }
}
on obtient à l'exécution:
java.lang.NullPointerException at Bug1.main(Bug1.java:5)
C'est une erreur tellement fréquente que les compilateurs récents détectent ce genre de problème à la compilation.

Quand on manipule un tableau, on travaille en fait de façon indirecte avec lui, comme si on utilisait une armoire pour ranger ses affaires. Il faut toujours imaginer qu'écrire
    tab[2] = 3;
veut dire au compilateur "retrouve l'endroit où tu as stocké tab en mémoire et met à jour la case d'indice 2 avec 3". En fait, le compilateur se rappelle d'abord où il a rangé son armoire, puis en déduit quel tiroir utiliser.

La valeur d'une variable tableau est une référence, c'est-à-dire l'adresse où elle est rangée en mémoire. Si on écrit:
    int[] tabnouv = tab;
les variables tabnouv et tab désignent le même tableau, en programmation on dit qu'elles font référence au même tableau. Il n'y a pas recopie de toutes les valeurs contenues dans le tableau tab pour former un nouveau tableau mais simplement une indication de référence. Ainsi si l'on modifie la valeur de tab[i], celle de tabnouv[i] le sera aussi.

Si on souhaite recopier un tableau dans un autre il faut écrire une fonction:
  static int[] copier(int[] x){
      int n = x.length;
      int[] y = new int[n];

      for(int i = 0; i < n; i++)
          y[i] = x[i];
      return y;
  }

Noter aussi que l'opération de comparaison de deux tableaux x == y est évaluée à true dans le cas où x et y référencent le même tableau (par exemple si on a effectué l'affectation y = x). Si on souhaite vérifier l'égalité des contenus, il faut écrire une fonction particulière:
  static boolean estEgal(int[] x, int[] y){
      if(x.length != y.length) return false;
      for(int i = 0; i < x.length; i++)
          if(x[i] != y[i])
              return false;
      return true;
  }

Dans cette fonction, on compare les éléments terme à terme et on s'arrête dès que deux éléments sont distincts, en sortant de la boucle et de la fonction dans le même mouvement.

4.3  Tableaux à plusieurs dimensions, matrices

Un tableau à plusieurs dimensions est considéré en Java comme un tableau de tableaux. Par exemple, les matrices sont des tableaux à deux dimensions, plus précisément des tableaux de lignes. Leur déclaration peut se faire par:
  typ[][] tab;
On doit aussi le construire à l'aide de new. L'instruction
  tab = new typ[N][M];
construit un tableau à deux dimensions, qui est un tableau de N lignes à M colonnes. L'instruction tab.length retourne le nombre de lignes, alors que tab[i].length retourne la longueur du tableau tab[i], c'est-à-dire le nombre de colonnes.

On peut aussi, comme pour les tableaux à une dimension, faire une affectation de valeurs en une seule fois:
  int[2][3] tab = {{1,2,3},{4,5,6}};
qui déclare et initialise un tableau à 2 lignes et 3 colonnes. On peut écrire de façon équivalente:
  int[][] tab = {{1,2,3},{4,5,6}};
Comme une matrice est un tableau de lignes, on peut fabriquer des matrices bizarres. Par exemple, pour déclarer une matrice dont la première ligne a 5 colonnes, la deuxième ligne 1 colonne et la troisième 2, on écrit
    public static void main(String[] args){
 int[][] M = new int[3][];

 M[0] = new int[5];
 M[1] = new int[1];
 M[2] = new int[2];
    }
Par contre, l'instruction:
        int[][] N = new int[][3];
est incorrecte. On ne peut définir un tableau de colonnes.

On peut continuer à écrire un petit programme qui se sert de cela:
class Tab3{
    static void ecrire(int[] M){
        for(int j = 0; j < M.length; j++)
            System.out.println(M[j]);
    }
    public static void main(String[] args){
        int[][] M = new int[3][];

        M[0] = new int[5];
        M[1] = new int[1];
        M[2] = new int[2];
        for(int i = 0; i < M.length; i++)
            ecrire(M[i]);
    }
}

4.4  Les tableaux comme arguments de fonction

Les valeurs des variables tableaux (les références) peuvent être passées en argument, on peut aussi les retourner:
class Tab2{
    static int[] construire(int n){
        int[] t = new int[n];

        for(int i = 0; i < n; i++)
            t[i] = i;
        return t;
    }

    public static void main(String[] args){
        int[] t = construire(3);

        for(int i = 0; i < 3; i++)
            System.out.println(t[i]);
    }
}

Considérons maintenant le programme suivant:
class Test{

    static void f(int[] t){
        t[0] = -10;
        return;
    }

    public static void main(String[] args){
        int[] t = {1, 2, 3};

        f(t);
        System.out.println("t[0]="+t[0]);
        return;
    }
}

Que s'affiche-t-il? Pas 1 comme on pourrait le croire, mais -10. En effet, nous voyons là un exemple de passage par référence: le tableau t n'est pas recopié à l'entrée de la fonction f, mais on a donné à la fonction f la référence de t, c'est-à-dire le moyen de savoir où t est gardé en mémoire par le programme. On travaille donc sur le tableau t lui-même. Cela permet d'éviter des recopies fastidieuses de tableaux, qui sont souvent très gros. La lisibilité des programmes peut s'en ressentir, mais c'est la façon courante de programmer.

4.5  Exemples d'utilisation des tableaux

4.5.1  Algorithmique des tableaux

Nous allons écrire des fonctions de traitement de problèmes simples sur des tableaux contenant des entiers.

Commençons par remplir un tableau avec des entiers aléatoires de [0, M[, on écrit:
class Tableaux{

    static int M = 128;

    // initialisation
    static int[] aleatoire(int N){
        int[] t = new int[N];

        for(int i = 0; i < N; i++)
            t[i] = (int)(M * Math.random());
        return t;
    }
}

Ici, il faut convertir de force le résultat de Math.random()*M en entier de manière explicite, car Math.random() retourne un double.

Pour tester facilement les programmes, on écrit aussi une fonction qui affiche les éléments d'un tableau t, un entier par ligne:
  // affichage à l'écran
  static void afficher(int[] t){
      for(int i = 0; i < t.length; i++)
          System.out.println(t[i]);
      return;
  }

Le tableau t étant donné, un nombre m est-il élément de t ? On écrit pour cela une fonction qui retourne le plus petit indice i pour lequel t[i]=m s'il existe et -1 si aucun indice ne vérifie cette condition:
  // retourne le plus petit i tq t[i] = m s'il existe
  // et -1 sinon.
  static int recherche(int[] t, int m){
      for(int i = 0; i < t.length; i++)
          if(t[i] == m)
              return i;
      return -1;
  }

Passons maintenant à un exercice plus complexe. Le tableau t contient des entiers de l'intervalle [0, M-1] qui ne sont éventuellement pas tous distincts. On veut savoir quels entiers sont présents dans le tableau et à combien d'exemplaire. Pour cela, on introduit un tableau auxiliaire compteur, de taille M, puis on parcourt t et pour chaque valeur t[i] on incrémente la valeur compteur[t[i]]. À la fin du parcourt de t, il ne reste plus qu'à afficher les valeurs non nulles contenues dans compteur:
  static void compter(int[] t){
      int[] compteur = new int[M];

      for(int i = 0; i < M; i++)
          compteur[i] = 0;
      for(int i = 0; i < t.length; i++)
          compteur[t[i]] += 1;
      for(int i = 0; i < M; i++)
          if(compteur[i] > 0){
               System.out.print(i+" est utilisé ");
               System.out.println(compteur[i]+" fois");
          }
  }

4.5.2  Un peu d'algèbre linéaire

Un tableau est la structure de donnée la plus simple qui puisse représenter un vecteur. Un tableau de tableaux représente une matrice de manière similaire. Écrivons un programme qui calcule l'opération de multiplication d'un vecteur par une matrice à gauche. Si v est un vecteur colonne à m lignes et A une matrice n× m, alors w = A v est un vecteur colonne à n lignes. On a:
wi =
m-1
k = 0
Ai, k vk
pour 0 ≤ i < n. On écrit d'abord la multiplication:
    static double[] multMatriceVecteur(double[][] A,
                                       double[] v){
        int n = A.length;
        int m = A[0].length;
        double[] w = new double[n];

        // calcul de w = A * v
        for(int i = 0; i < n; i++){
            w[i] = 0;
            for(int k = 0; k < m; k++)
                w[i] += A[i][k] * v[k];
        }
        return w;
    }

puis le programme principal:
    public static void main(String[] args){
        int n = 3, m = 4;
        double[][] A = new double[n][m]; // A est n x m
        double[] v = new double[m]; // v est m x 1
        double[] w;

        // initialisation de A
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++)
                A[i][j] = Math.random();
        // initialisation de v
        for(int i = 0; i < m; i++)
            v[i] = Math.random();

        w = multMatriceVecteur(A, v); // (*)

        // affichage
        for(int i = 0; i < n; i++)
            System.out.println("w["+i+"]="+w[i]);
        return;
    }

On peut récrire la fonction de multiplication en passant les arguments par effets de bord sans avoir à créer le résultat dans la fonction, ce qui peut être couteux quand on doit effectuer de nombreux calculs avec des vecteurs. On écrit alors plutôt:
    static void multMatriceVecteur(double[] w,
                                   double[][] A,
                                   double[] v){
        int n = A.length;
        int m = A[0].length;

        // calcul de w = A * v
        for(int i = 0; i < n; i++){
            w[i] = 0;
            for(int k = 0; k < m; k++)
                w[i] += A[i][k] * v[k];
        }
    }

Dans le programme principal, on remplacerait la ligne (*) par:
        w = new double[n];
 multMatriceVecteur(w, A, v);

4.5.3  Le crible d'Eratosthene

On cherche ici à trouver tous les nombres premiers de l'intervalle [1, N]. La solution déjà connue des grecs consiste à écrire tous les nombres de l'intervalle les uns à la suite des autres. Le plus petit nombre premier est 2. On raye alors tous les multiples de 2 plus grands que 2 de l'intervalle, ils ne risquent pas d'être premiers. Le premier nombre qui n'a pas été rayé au-delà du nombre premier courant est lui-même premier, c'est le suivant à traiter. On raye ainsi les multiples de 3 sauf 3, etc. On s'arrête quand on s'apprête à éliminer les multiples de p > √  (rappelons que tout nombre non premier plus petit que N a un diviseur premier ≤ √ ).

// Retourne le tableau des nombres premiers
// de l'intervalle [2..N]
static int[] Eratosthene(int N){
    boolean[] estpremier = new boolean[N+1];
    int p, kp, nbp;

    // initialisation
    for(int n = 2; n < N+1; n++)
        estpremier[n] = true;
    // boucle d'élimination
    p = 2;
    while(p*p <= N){
        // élimination des multiples de p
        // on a déjà éliminé les multiples de q < p
        kp = 2*p; // (cf. remarque)
        while(kp <= N){
            estpremier[kp] = false;
            kp += p;
        }
        // recherche du nombre premier suivant
        do{
            p++;
        } while(!estpremier[p]);
    }
    // comptons tous les nombres premiers <= N
    nbp = 0;
    for(int n = 2; n <= N; n++)
        if(estpremier[n])
            nbp++;

    // mettons les nombres premiers dans un tableau
    int[] tp = new int[nbp];
    for(int n = 2, i = 0; n <= N; n++)
        if(estpremier[n])
              tp[i++] = n;
    return tp;
}

Figure 4.1 : Crible d'Eratosthene.


Comment modéliser le crible? On utilise un tableau de booléens estpremier, de taille N+1, qui représentera l'intervalle [1, N]. Il est initialisé à true au départ, car aucun nombre n'est rayé. À la fin du calcul, p ≥ 2 est premier si et seulement si estpremier[p] == true. On trouve le programme complet dans la figure 4.1.

Remarquons que la ligne
    kp = 2*p;
peut être avantageusement remplacée par
    kp = p*p;
car tous les multiples de p de la forme u p avec u < p ont déjà été rayés du tableau à une étape précédente.

Il existe de nombreuses astuces permettant d'accélérer le crible. Notons également que l'on peut se servir du tableau des nombres premiers pour trouver les petits facteurs de petits entiers. Ce n'est pas la meilleure méthode connue pour trouver des nombres premiers ou factoriser les nombres qui ne le sont pas. Revenez donc me voir en Majeure 2 si ça vous intéresse.

4.5.4  Jouons à la bataille rangée

On peut également se servir de tableaux pour représenter des objets a priori plus compliqués. Nous allons décrire ici une variante simplifiée du célèbre jeu de bataille, que nous appelerons bataille rangée. La règle est simple: le donneur distribue 32 cartes (numérotées de 1 à 32) à deux joueurs, sous la forme de deux piles de cartes, face sur le dessous. À chaque tour, les deux joueurs, appelés Alice et Bob, retournent la carte du dessus de leur pile. Si la carte d'Alice est plus forte que celle de Bob, elle marque un point; si sa carte est plus faible, c'est Bob qui marque un point. Gagne celui des deux joueurs qui a marqué le plus de points à la fin des piles.

Le programme de jeu doit contenir deux phases: dans la première, le programme bat et distribue les cartes entre les deux joueurs. Dans un second temps, le jeu se déroule.

Nous allons stocker les cartes dans un tableau donne[0..32[ avec la convention que la carte du dessus se trouve en position 31.

Pour la première phase, battre le jeu revient à fabriquer une permutation au hasard des éléments du tableau donne. L'algorithme le plus efficace pour cela utilise un générateur aléatoire (la fonction Math.random() de Java, qui renvoie un réel aléatoire entre 0 et 1), et fonctionne suivant le principe suivant. On commence par tirer un indice j au hasard entre 0 et 31 et on permute donne[j] et donne[31]. On continue alors avec le reste du tableau, en tirant un indice entre 0 et 30, etc. La fonction Java est alors (nous allons ici systématiquement utiliser le passage par référence des tableaux):



    static void battre(int[] donne){
        int n = donne.length, i, j, tmp;

        for(i = n-1; i > 0; i--){
            // on choisit un entier j de [0..i]
            j = (int)(Math.random() * (i+1));
            // on permute donne[i] et donne[j]
            tmp = donne[i];
            donne[i] = donne[j];
            donne[j] = tmp;
        }
    }

La fonction qui crée une donne à partir d'un paquet de n cartes est alors:
    static int[] creerJeu(int n){
        int[] jeu = new int[n];

        for(int i = 0; i < n; i++)
            jeu[i] = i+1;
        battre(jeu);
        return jeu;
    }

et nous donnons maintenant le programme principal:
    public static void main(String[] args){
        int[] donne;

        donne = creerJeu(32);
        afficher(donne);
        jouer(donne);
    }

Nous allons maintenant jouer. Cela se passe en deux temps: dans le premier, le donneur distribue les cartes entre les deux joueurs, Alice et Bob. Dans le second, les deux joueurs jouent, et on affiche le nom du vainqueur, celui-ci étant déterminé à partir du signe du gain d'Alice (voir plus bas):
    static void jouer(int[] donne){
        int[] jeuA = new int[donne.length/2];
        int[] jeuB = new int[donne.length/2];
        int gainA;

        distribuer(jeuA, jeuB, donne);
        gainA = jouerAB(jeuA, jeuB);
        if(gainA > 0) System.out.println("A gagne");
        else if(gainA < 0) System.out.println("B gagne");
        else System.out.println("A et B sont ex aequo");
    }

Le tableau donne[0..31] est distribué en deux tas, en commençant par Alice, qui va recevoir les cartes de rang pair, et Bob celles de rang impair. Les cartes sont données à partir de l'indice 31:
    // donne[] contient les cartes qu'on distribue à partir
    // de la fin. On remplit jeuA et jeuB à partir de 0
    static void distribuer(int[] jeuA,int[] jeuB,int[] donne){
        int iA = 0, iB = 0;

        for(int i = donne.length-1; i >= 0; i--)
            if((i % 2) == 0)
                jeuA[iA++] = donne[i];
            else
                jeuB[iB++] = donne[i];
    }

On s'intéresse au gain d'Alice, obtenu par la différence entre le nombre de cartes gagnées par Alice et celles gagnées par Bob. Il suffit de mettre à jour cette variable au cours du calcul:
    static int jouerAB(int[] jeuA, int[] jeuB){
        int gainA = 0;

        for(int i = jeuA.length-1; i >= 0; i--)
            if(jeuA[i] > jeuB[i])
                gainA++;
            else if(jeuA[i] < jeuB[i])
                gainA--;
        return gainA;
    }

Exercice. (Programmation du jeu de bataille) Dans le jeu de bataille (toujours avec les cartes 1..32), le joueur qui remporte un pli le stocke dans une deuxième pile à côté de sa pile courante, les cartes étant stockées dans l'ordre d'arrivée, formant une nouvelle pile. Quand il a fini sa première pile, il la remplace par la seconde et continue à jouer. Le jeu s'arrête quand un des deux joueurs n'a plus de cartes. Programmer ce jeu.

4.5.5  Pile

On a utilisé ci-dessus un tableau pour stocker une pile de cartes, la dernière arrivée étant utilisée aussitôt. Ce concept de pile est fondamental en informatique.

Par exemple, considérons le programme Java:
    static int g(int n){
        return 2*n;
    }
    static int f(int n){
        return g(n)+1;
    }
    public static void main(String[] args){
        int m = f(3); // (1)

        return;
    }
Quand la fonction main s'exécute, l'ordinateur doit exécuter l'instruction (1). Pour ce faire, il garde sous le coude cette instruction, appelle la fonction f, qui appelle elle-même la fonction g, puis revient à ses moutons en remplissant la variable m. Garder sous le coude se traduit en fait par le stockage dans une pile des appels de cette information.


Figure 4.2 : Pile des appels.


Le programme main appelle la fonction f avec l'argument 3, et f elle-même appelle g avec l'argument 3, et celle-ci retourne la valeur 6, qui est ensuite retournée à f, et ainsi de suite:


Figure 4.3 : Pile des appels (suite).


Cette notion sera complétée au chapitre 6.


1
ou de manière équivalente par typ tab[];. Nous préférerons la première façon de faire car elle respecte la convention suivant laquelle dans une déclaration, le type d'une variable figure complètement avant le nom de celle-ci. La seconde correspond à ce qui se fait en langage C.
2
Tempérons un peu: dans des applications critiques (cartes à puce par exemple), on sait encore descendre à ce niveau là, quand on sait mieux que le compilateur comment gérer la mémoire. Ce sujet dépasse le cadre du cours.
3
Une case mémoire pour un int de Java est formée de 4 octets consécutifs.

Précédent Remonter Suivant