Tableaux multidimensionnels 
Il est parfois intéressant d'utiliser des tableaux à plusieurs dimensions, c'est-à-dire avec plusieurs indices.
Par exemple, une image est une grille de pixels, chaque pixel ayant une abscisse et une ordonnée. On voudrait donc accéder aux pixels en utilisant son abscisse et son ordonnée.
Dans ce cours, on se limite à des tableaux 2D. On pourrait généraliser à des tableaux multidimensionnels quelconques de façon similaire.
Tableaux statiques (définis sur la pile)¶
Voici un exemple de tableau à deux dimensions (2D) :
int tab[2][3];
tab est alors un tableau d'entiers, où il faut donner deux indices pour accéder à un élément :
tab[0][1] = 42; // modifie l'élément d'indices 0, 1
42
tab[0][1] // récupération de la valeur en position 0, 1
42
int tab[2][3] signifie que la taille suivant la 1ère dimension est 2 et que la taille suivant la 2ème dimension est 3. Pour utiliser tab[i][j] il faut donc que i soit strictement inférieur à 2 et que j soit strictement inférieur à 3.
Pour parcourir les éléments d'un tableau 2D, on a besoin de deux boucles for imbriquées (pour les 2 indices) :
for(int i = 0; i < 2; i++)
for(int j = 0; j < 3; j++)
tab[i][j] = i*3 + j;
On parcourt toutes les valeurs i possibles pour le 1er indice, et toutes les valeurs j possibles pour le 2ème indice.
On peut ensuite afficher le tableau :
for(int i = 0; i < 2; i++) {
for(int j = 0; j < 3; j++)
printf("%d ", tab[i][j]);
printf("\n"); // saute une ligne pour que ce soit plus clair
}
0 1 2 3 4 5
Exercice
Calculer la somme des éléments de tab.
Matrices¶
Un tableau 2D correspond à une matrice en mathématiques. Ainsi, tab correspond à la matrice $2\times 3$ suivante :
$$\begin{pmatrix}
0 & 1 & 2\\
3 & 4 & 5\\
\end{pmatrix}$$
De manière générale, on peut stocker une matrice $M$ de taille $n\times p$ (avec $n$ lignes et $p$ colonnes) dans un tableau 2D défini par int t[n][p] (ou double t[n][p] pour stocker des flottants au lieu d'entiers, par exemple).
t[i][j] correspond alors à l'élément de $M$ sur la ligne i, colonne j. La ligne 0 est celle tout en haut ($0 ~1 ~2$ sur l'exemple ci-dessus) et la colonne 0 celle tout à gauche.
Initialisation¶
On pourrait aussi initialiser le tableau 2D tab ci-dessus de la façon suivante :
int tab[2][3] = {
{0, 1, 2},
{3, 4, 5}
}
Tableau 2D = tableau de tableaux¶
Un tableau 2D est un tableau dont les éléments sont des tableaux. Par exemple, int tab[2][3] signifie que tab est un tableau à 2 éléments, qui sont 2 tableaux de taille 3.
tab[0] // tab[0] est un tableau
{ 0, 1, 2 }
Quand on écrit tab[i][j], on obtient l'élément d'indice j du tableau tab[i] :
int* t = tab[1]; // 2ème tableau de tab
t[2] // donne la même chose que tab[1][2]
5
Représentation en mémoire des tableaux statiques¶
Les tableaux définis sur la pile ont leurs éléments stockés consécutivements : d'abord les éléments du 1er tableau, puis du 2ème...
Par exemple, voici comme est stocké le tableau 2D tab dans la mémoire RAM :
Linéarisation de tableau 2D¶
Reprenons le tableau sur le dessin ci-dessus :
int t2[2][3] = {
{0, 1, 2},
{3, 4, 5}
}
À la place d'un tableau 2D, on pourrait utiliser un tableau 1D :
int t1[6] = {0, 1, 2, 3, 4, 5}
En mémoire, t1 et t2 sont stockés de la même façon. Le seul avantage apporté par la première définition est de pouvoir écrire t2[i][j].
Comme t2 est un tableau $2\times 3$, t2[i][j] est la même chose que t1[3*i + j] :
t1[3 + 2] // pareil que t2[1][2]
5
De manière générale, au lieu d'un tableau t2[n][p] 2D de dimensions $n$ et $p$, on peut utiliser un tableau 1D t1[n*p] de taille $np$, en disant que t2[i][j] correspond à t1[i*p + j].
void print_matrix1(int* m, int n, int p) {
// affiche une matrice m de taille n*p (linéarisée)
for(int i = 0; i < n; i++) { // i parcourt les lignes
for(int j = 0; j < p; j++) // j parcourt les colonnes
printf("%d ", m[i*p + j]);
printf("\n");
}
}
print_matrix1(t1, 2, 3);
0 1 2 3 4 5
Remarque : Puisqu'un tableau 2D est stocké comme un tableau 1D et que c'est l'adresse vers le premier élément qui est passé lorsqu'on donne un tableau en argument, on peut aussi utiliser print_matrix sur un tableau 2D :
print_matrix1(&t2[0][0], 2, 3); // marche
print_matrix1(t2[0], 2, 3); // marche aussi
0 1 2 3 4 5 0 1 2 3 4 5
Exercice
Écrire une fonction pour calculer la trace d'une matrice carrée, c'est-à-dire la somme des termes sur la diagonale.
Avec un "vrai" tableau 2D¶
Pour garder un tableau 2D en argument, il faut que la taille suivant la deuxième dimension soit constante et donnée, pour que C sache de combien à quelle cases mémoires il faut regarder lorsqu'on écrit m[i][j] (c'est-à-dire à la i + p*j ème case) :
void print_matrix2(int n, int m[][3]) {
// affiche une matrice m de taille n*3
for(int i = 0; i < n; i++) { // i parcourt les lignes
for(int j = 0; j < 3; j++) // j parcourt les colonnes
printf("%d ", m[i][j]);
printf("\n");
}
}
print_matrix2(2, t2);
0 1 2 3 4 5
Exercice
Écrire une fonction pour déterminer si une matrice est symétrique ($M_{i, j} = M_{j, i}, ~\forall i, j$).
Remarque : Il serait possible d'utiliser les VLA (Variable Length Array) du C pour éviter de fixer comme constante la 2ème dimension. C'est de toute façon déconseillé, et incompatible en C++.
Tableau 2D dynamiques (sur le tas, avec malloc)¶
On peut définir dynamiquement un tableau 2D, ce qui permet, comme pour les tableaux classiques, d'avoir une taille connue à l'exécution et de pouvoir être créé puis renvoyé par une fonction sans être supprimé.
Tableau dynamique linéarisé¶
// renvoie la matrice identité de taile n sous forme de tableau 1D
int* id_matrix1(int n) {
int *t = (int*)malloc(n*n*sizeof(int));
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++) {
if(i == j)
t[i*n + j] = 1;
else
t[i*n + j] = 0;
}
return t;
}
int* id = id_matrix1(5);
print_matrix1(id, 5, 5);
1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1
On peut ensuite libérer toute la mémoire avec free :
free(id)
Exercice
Comment se passer du if ... else ... dans id_matrix1 ?
Exercice
Écrire une fonction pour calculer le produit de deux matrices (de tailles compatibles). Complexité?
Exercice
Écrire une fonction pour calculer une puissance de matrice. Complexité?
Tableau de pointeurs¶
On peut aussi utiliser un malloc pour chaque sous-tableau (c'est-à-dire chaque ligne de la matrice correspondante). Chaque malloc nous donne un pointeur vers la zone où est stocké le tableau. On peut stocker tous ces pointeurs dans un tableau, qui est donc un tableau de tableaux (par exemple de type int**, c'est-à-dire un pointeur vers la première case d'un tableau dont les éléments sont des int*).
// renvoie la matrice identité de taile n sous forme de tableau de pointeurs
int** id_matrix2(int n) {
int **t = (int**)malloc(n*sizeof(int*)); // tableau de pointeurs
for(int i = 0; i < n; i++) {
t[i] = (int*)malloc(n*sizeof(int)); // tableau pour la ligne i
for(int j = 0; j < n; j++) {
if(i == j)
t[i][j] = 1;
else
t[i][j] = 0;
}
}
return t;
}
void print_matrix3(int** m, int n, int p) {
// affiche une matrice m de taille n*3
for(int i = 0; i < n; i++) { // i parcourt les lignes
for(int j = 0; j < 3; j++) // j parcourt les colonnes
printf("%d ", m[i][j]);
printf("\n");
}
}
int** id = id_matrix2(3);
print_matrix3(id, 3, 3)
1 0 0 0 1 0 0 0 1
Pour libérer la mémoire, c'est un peu plus compliqué. Il faut d'abord un free sur chaque sous-tableau, puis sur le tableau global :
void free_matrix(int** m, int n) {
for(int i = 0; i < n; i++)
free(m[i]);
free(m);
}
free_matrix(id, 3);
Un avantage de cette représentation est qu'elle permet de créer des tableaux 2D dont les sous-tableaux sont de tailles différentes, même si c'est rarement utile.
Exercice
Écrire une fonction permettant de renvoyer la transposée d'une matrice.
Exercice
(1ère question d'un oral math-info du concours Centrale) Écrire une fonction int* serpent(int n) renvoyant une matrice $n\times n$ ressemblant à :
$$\begin{pmatrix}
1 & 2 & 3 & 4\\
8 & 7 & 6 & 5\\
9 & 10 & 11 & 12\\
16 & 15 & 14 & 13
\end{pmatrix}$$