Pour commencer ce blog, nous allons étudier une structure de données inévitable et certainement la plus simple à utiliser. Il s’agit des tableaux (arrays en anglais).
Un tableau est un ensemble, de taille fixe, regroupant des éléments d’un même type (entier par exemple). Grâce à l’indexation de ces éléments, il est possible d’atteindre immédiatement n’importe quel élément du tableau. La figure 1 illustre ces propos :
Exemple d’implémentation de ce tableau d’entiers en JAVA :
public static void main(String[] args) {
int [] monTableau = {15, 53, 1, 29, 5, 8};
System.out.println(monTableau[0]); // affiche 15
System.out.println(monTableau[3]); // affiche 29 }
Dans ce programme, nous avons crée un tableau nommé monTableau représenté par la figure 1. Il contient six éléments. L’accès à l’un d’eux se fait à l’aider de la syntaxe suivante : monTableau[i] où i représente l’index (ou l’indice) de l’élément recherché.
Vous remarquerez que le premier élément du tableau est indexé par 0 et non par 1. (On parle de “zero-based indexing”). L’index du dernier élément est donc 5.
En mémoire, ce tableau occupe six cases mémoires consécutives. MonTableau est simplement une référence (ou un pointeur) vers la première case mémoire contenant la première valeur du tableau. monTableau[i] signifie simplement un déplacement de i cases mémoires depuis la première case mémoire référencée par monTableau. Ceci permet d’obtenir un temps d’accès constant à n’importe quel élément du tableau. La figure 2 illustre ces propos :
Dans l’exemple précédent le tableau contient des entiers. Il est également possible de créer des tableaux contenant des tableaux. On parle alors de tableaux à N-dimensions.
Les tableaux sont très faciles à utiliser malheureusement ils ne sont pas du tout performants pour les recherches. En effet, pour rechercher un élément dans un tableau il faut le parcourir dans sa totalité dans le pire des cas. On dit alors que la complexité algorithmique est de O(n). Les performances des recherches sur les tableaux peuvent être améliorées en les complétant d’une relation d’ordre. On peut alors soit trier le tableau, soit insérer les éléments au bon endroit lors de la création du tableau.
Le prochain article présentera différents algorithmes de tris des tableaux.
