Tableaux

Un tableau est similaire à un array en OCaml : c'est un ensemble de cases mémoires contiguës qui permet d'accéder en O(1) à un élément en position quelconque. Comme en OCaml, la taille d'un tableau ainsi que le type des ses éléments est fixé à sa création :

In [27]:

int t[10];  // créé un tableau de 10 entiers

int t[10]; // créé un tableau de 10 entiers

Cela a pour effet d'allouer $10$ entiers dans la pile, pour un total de $10\times 4$ octets :

In [17]:

sizeof(t)

sizeof(t)

Out[17]:

40

On peut modifier et accéder à un élément par son indice (qui commence à 0) :

In [13]:

t[0] = 42;  // modification du 1er élément

t[0] = 42; // modification du 1er élément

Out[13]:

42

In [14]:

t[0]  // valeur du 1er élément

t[0] // valeur du 1er élément

Out[14]:

42

Si on dépasse de la taille d'un tableau, on obtient une erreur :

In [15]:

t[10]  // le dernier indice d'un tableau de taille n est n - 1

t[10] // le dernier indice d'un tableau de taille n est n - 1

input_line_30:2:2: warning: array index 10 is past the end of the array (which contains 10 elements) [-Warray-bounds]
 t[10]  // le dernier indice d'un tableau de taille n est n - 1
 ^ ~~
input_line_25:2:2: note: array 't' declared here
 int t[10];  // créé un tableau de 10 entiers
 ^

Out[15]:

0

Exercice

Définir un tableau de taille 20 qui contient les entiers de 0 à 19.

Solution

In [1]:

int t[20];
for(int i = 0; i < 20; i++)
    t[i] = i;

int t[20]; for(int i = 0; i < 20; i++) t[i] = i;

Initialisation¶

On peut initialiser un tableau de la façon suivante :

In [11]:

float t[3] = {2.718, 3.14, 1.618};

float t[3] = {2.718, 3.14, 1.618};

Dans ce cas, il n'est pas obligatoire de donner la taille du tableau (qui est automatiquement déduit de l'initialisation) :

In [12]:

float t[] = {2.718, 3.14, 1.618};

float t[] = {2.718, 3.14, 1.618};

float t[] signifie qu'on définit un tableau sans donner sa taille.
Il n'est pas possible d'utiliser la notation {...} pour changer le tableau, après l'avoir défini :

In [14]:

t = {3.14, 2.718} // erreur : l'initialisation n'est possible que lors de la définition

t = {3.14, 2.718} // erreur : l'initialisation n'est possible que lors de la définition

input_line_23:2:4: error: array type 'float [3]' is not assignable
 t = {3.14, 2.718} // erreur : l'initialisation n'est possible que lors de la définition
 ~ ^

Interpreter Error: 

Pointeur et tableau¶

Lorsqu'on utilise un tableau comme une valeur (par exemple quand il apparaît à droite d'une affectation de variable), le tableau est automatiquement converti en pointeur vers le 1er élément du tableau. On parle de pointer decay :

In [3]:

int tab[10];
&tab[0]  // adresse du 1er élément de tab

int tab[10]; &tab[0] // adresse du 1er élément de tab

Out[3]:

@0x7fff1b568238

In [4]:

int* p = tab;  // lorsqu'il est utilisé comme une valeur, tab est converti en pointeur
p              // qui est en fait la même adresse que &tab[0]

int* p = tab; // lorsqu'il est utilisé comme une valeur, tab est converti en pointeur p // qui est en fait la même adresse que &tab[0]

Out[4]:

@0x7fff1b568238

int* p = tab; est donc équivalent à int* p = &tab[0], et mets dans p l'adresse du 1er élément de tab.
Le nom tab ressemble beaucoup à un pointeur vers le premier élément du tableau. Ce n'est cependant pas exactement un pointeur, comme on le voit en utilisant sizeof :

In [7]:

printf("taille de tab (tableau) : %lu\n", sizeof(tab));
printf("taille de p (pointeur) : %lu", sizeof(p));

printf("taille de tab (tableau) : %lu\n", sizeof(tab)); printf("taille de p (pointeur) : %lu", sizeof(p));

taille de tab (tableau) : 40
taille de p (pointeur) : 8

Hormis avec sizeof et &, un tableau se comporte exactement comme un pointeur constant vers le 1er élément.

Passage en argument¶

Lorsque l'on passe un tableau en argument d'une fonction, il y a pointer decay et la fonction récupère un pointeur. Une fonction sur un tableau pourra donc prendre int* en argument :

In [8]:

int somme(int* tab, int n) { 
// renvoie la somme des éléments du tableau tab
// n est la taille du tableau
    int s = 0;
    for(int i = 0; i < n; i++) {
        s += tab[i];
    }
    return s;
}

int t[] = {1, 2, 3, 4};
somme(t, 4)

int somme(int* tab, int n) { // renvoie la somme des éléments du tableau tab // n est la taille du tableau int s = 0; for(int i = 0; i < n; i++) { s += tab[i]; } return s; } int t[] = {1, 2, 3, 4}; somme(t, 4)

Out[8]:

10

Remarque : Lorsque tab est un pointeur, tab[i] fonctionne quand même et a pour effet de décaler l'adresse de tab de i blocs mémoire. tab[i] donne la même chose que t[i].
Il est nécessaire de donner le n en argument à somme pour connaître la taille du tableau. En effet, sizeof(tab) dans somme donnerait la taille d'une adresse (qui est 8 octets, soit 64 bits) et non pas la taille du tableau.
De plus, il est possible d'utiliser int tab[] (ou int tab[n]) au lieu de int* tab en argument de somme, mais le comportement est exactement le même :

In [109]:

int somme(int tab[], int n) { // fait exactement la même chose que la fonction précédente
    int s = 0;
    for(int i = 0; i < n; i++) {
        s += tab[i];
    }
    return s;
}

int somme(int tab[], int n) { // fait exactement la même chose que la fonction précédente int s = 0; for(int i = 0; i < n; i++) { s += tab[i]; } return s; }

Un tableau est donc toujours passé sous forme de pointeur (il n'existe pas de passage par copie pour les tableaux). On peut s'en servir pour modifier un tableau.

Exercice

1. Écrire une fonction swap pour échanger deux éléments d'un tableau d'entiers.

   void swap(int* tab, int i, int j);
   

2. En déduire une fonction reverse inversant l'ordre des éléments d'un tableau d'entiers.

Solution

In [5]:

// 1.
void swap(int* tab, int i, int j) {
    int tmp = tab[i];
    tab[i] = tab[j];
    tab[j] = tmp;
}

// 1. void swap(int* tab, int i, int j) { int tmp = tab[i]; tab[i] = tab[j]; tab[j] = tmp; }

Solution

In [7]:

// 2. on échange les pairs d'éléments symétriques (l'indice 0 avec l'indice n - 1...)
void reverse(int* tab, int n) {
    for(int i = 0; i < n/2; i++)
        swap(tab, i, n - i - 1); // pour i = 0, n - i - 1 = n - 1 est le dernier
}

int tab[] = {1, 2, 3};
reverse(tab, 3); tab

// 2. on échange les pairs d'éléments symétriques (l'indice 0 avec l'indice n - 1...) void reverse(int* tab, int n) { for(int i = 0; i < n/2; i++) swap(tab, i, n - i - 1); // pour i = 0, n - i - 1 = n - 1 est le dernier } int tab[] = {1, 2, 3}; reverse(tab, 3); tab

Out[7]:

{ 3, 2, 1 }

Allocation dynamique de tableau¶

Il est possible de créer un tableau dans le tas avec malloc :

In [118]:

int* p = (int*)malloc(10*sizeof(int)); // création d'un tableau de 10 entiers dans le tas
p[0] = 42; // modification du 1er élément

int* p = (int*)malloc(10*sizeof(int)); // création d'un tableau de 10 entiers dans le tas p[0] = 42; // modification du 1er élément

Out[118]:

42

In [119]:

p[0] // le 1er élément a bien été modifié

p[0] // le 1er élément a bien été modifié

Out[119]:

42

On obtient, comme précédément, un pointeur vers le 1er élément du tableau ainsi créé. On peut se servir d'une allocation dynamique pour créer un tableau dont la taille dépend d'une variable :

In [120]:

int* range(int n) { // renvoie un tableau contenant 0, ..., n - 1
    int* t = (int*)malloc(n*sizeof(int));
    for(int i = 0; i < n; i++) {
        t[i] = i;
    }
    return t;
}

int* range(int n) { // renvoie un tableau contenant 0, ..., n - 1 int* t = (int*)malloc(n*sizeof(int)); for(int i = 0; i < n; i++) { t[i] = i; } return t; }

In [122]:

int* t = range(5);
for(int i = 0; i < 5; i++) {
    printf("t[%d] = %d\n", i, t[i]);
}

int* t = range(5); for(int i = 0; i < 5; i++) { printf("t[%d] = %d\n", i, t[i]); }

t[0] = 0
t[1] = 1
t[2] = 2
t[3] = 3
t[4] = 4

Sans allocation dynamique, il ne serait pas possible de définir un tableau dont la taille dépend d'une variable (sauf à utiliser des VLA pour Variable Length Array qui sont hors programme et dont l'usage est de toute façon déconseillé) :

In [124]:

int n = 5;
int t[n];

int n = 5; int t[n];

input_line_163:3:5: error: variable length array declaration not allowed at file scope
int t[n]; 
    ^ ~

Interpreter Error: 

Exercice

1. Écrire une fonction copy de prototype double* copy(double* t, unsigned n) renvoyant une copie du tableau en argument de taille n, alloué dynamiquement.
2. Pourquoi est-on obligé de créer un nouveau tableau avec malloc ici?

Solution

In [9]:

// 1.
double* copy(double* t, unsigned n) {
    double* t_copy = (double*)malloc(n*sizeof(double));
    for(int i = 0; i < n; i++)
        t_copy[i] = t[i];
    return t_copy;
}

// 2.
// Deux raisons :
// - Si `t_copy` était créé sur la pile, il serait une variable locale à `copy`, détruit lorsque l'appel de fonction termine et donc inutilisable en dehors.  
// - La taille du tableau `t_copy` dépend d'une variable.

// 1. double* copy(double* t, unsigned n) { double* t_copy = (double*)malloc(n*sizeof(double)); for(int i = 0; i < n; i++) t_copy[i] = t[i]; return t_copy; } // 2. // Deux raisons : // - Si `t_copy` était créé sur la pile, il serait une variable locale à `copy`, détruit lorsque l'appel de fonction termine et donc inutilisable en dehors. // - La taille du tableau `t_copy` dépend d'une variable.