Algorithmes de référence sur les tableaux

Un tableau est un type abstrait de donnée qui peut contenir des éléments indexés (repérés par un indice - un numéro).

Exemple

On peut se représenter un tableau comme des « cases » consécutives contenant des valeurs :

tab =

5

3

5

Propriétés

• Le nombre d'éléments du tableau est appelée sa longueur, cette longueur est fixe.
• Les éléments du tableau sont tous du même type (par exemple sont tous des entiers, ou tous des caractères...).
• Chaque élément est repéré par un indice.
  • Dans ce cours, on considèrera que les indices sont compris entre 0 et longueur(tab)-1.
  • La valeur de l'élément d'indice i est obtenu par la notation tab[i].
  • On change la valeur de l'élément d'indice i par affectation : tab[i] ← valeur.

Quelques notations pratiques

Soit tab un tableau contenant n élément et soient i et j deux indices avec 0 ≤ i ≤ j ≤ n-1.

1. La notation tab[i..j] désigne le sous-tableau [tab[i], tab[i+1], ..., tab[j]].

2. La notation tab[i..] désigne le sous-tableau tab[i..n-1].

3. La notation tab[..i] désigne le sous-tableau tab[0..i].

Exercice

On considère le tableau tab = [3, 8, 1, 4, 2].
Que valent :

1. tab[2..3] ?
2. tab[0..0] ?
3. tab[1..] ?

Réponses

1. tab[2..3] = [tab[2], tab[3]] = [1, 4]
2. tab[0..0] = [tab[0]] = [3]
3. tab[1..] = [tab[1], tab[2], tab[3], tab[4]] = [8, 1, 4, 2]