7
Les tableaux
Les variables que nous avons utilisées jusqu’ici étaient ce que l’on nomme des variables simples (ou scalaires) : à un instant donné, une variable de ce type contenait une seule valeur.
Comme nous l’avons dit dans le premier chapitre, la notion de structure de données permet à
un langage évolué de donner un nom, non plus à une seule valeur, mais à un ensemble de
valeurs. La structure de données la plus répandue, et présente dans tous les langages, est le
tableau. Nous distinguerons :
• le tableau à une dimension (on dit aussi « à un indice ») : il s’agit alors d’une liste ordonnée
de valeurs de même type, désignée par un nom unique, chaque valeur de la liste étant repérée
par un numéro d’ordre qu’on nomme indice ; le tableau à une dimension s’apparente, en fait,
à la notion mathématique de vecteur ;
• le tableau à deux dimensions (à « deux indices ») : il est plus proche que le précédent de
l’idée usuelle que l’on se fait du mot « tableau », à savoir un ensemble de lignes et de
colonnes ; cette fois, chaque valeur du tableau est repérée par deux indices.
Nous allons tout naturellement commencer par présenter comment définir et utiliser un
tableau à une dimension et nous introduirons la notion de variable indicée en montrant comment elle peut s’utiliser de la même manière qu’une variable simple. Nous montrerons
ensuite comment les techniques classiques de somme et de recherche de maximum s’appliquent à un tel tableau. Nous introduirons également quelques techniques spécifiques aux
tableaux : recherche en table et tri. Puis nous verrons comment définir et utiliser un tableau à
deux dimensions. Enfin, nous ferons le point sur la façon dont peut être géré l’emplacement
mémoire destiné à un tableau, ce qui nous amènera à distinguer l’allocation statique de l’allocation dynamique et à parler de tableau associatif.
Les tableaux
Les variables que nous avons utilisées jusqu’ici étaient ce que l’on nomme des variables simples (ou scalaires) : à un instant donné, une variable de ce type contenait une seule valeur.
Comme nous l’avons dit dans le premier chapitre, la notion de structure de données permet à
un langage évolué de donner un nom, non plus à une seule valeur, mais à un ensemble de
valeurs. La structure de données la plus répandue, et présente dans tous les langages, est le
tableau. Nous distinguerons :
• le tableau à une dimension (on dit aussi « à un indice ») : il s’agit alors d’une liste ordonnée
de valeurs de même type, désignée par un nom unique, chaque valeur de la liste étant repérée
par un numéro d’ordre qu’on nomme indice ; le tableau à une dimension s’apparente, en fait,
à la notion mathématique de vecteur ;
• le tableau à deux dimensions (à « deux indices ») : il est plus proche que le précédent de
l’idée usuelle que l’on se fait du mot « tableau », à savoir un ensemble de lignes et de
colonnes ; cette fois, chaque valeur du tableau est repérée par deux indices.
Nous allons tout naturellement commencer par présenter comment définir et utiliser un
tableau à une dimension et nous introduirons la notion de variable indicée en montrant comment elle peut s’utiliser de la même manière qu’une variable simple. Nous montrerons
ensuite comment les techniques classiques de somme et de recherche de maximum s’appliquent à un tel tableau. Nous introduirons également quelques techniques spécifiques aux
tableaux : recherche en table et tri. Puis nous verrons comment définir et utiliser un tableau à
deux dimensions. Enfin, nous ferons le point sur la façon dont peut être géré l’emplacement
mémoire destiné à un tableau, ce qui nous amènera à distinguer l’allocation statique de l’allocation dynamique et à parler de tableau associatif.