Un tableau (Array) est la structure de données la plus fondamentale, la plus simple et la plus utilisée. C'est un moyen de stocker une collection d'éléments accessibles directement avec un index. Pour être plus précis: c'est une collection de taille fixe d'éléments de même type stockés dans un emplacement de mémoire contiguë.

La chose importante à retenir est qu'un index de tableau commence toujours à 0 et se termine à "taille - 1" :
array[0]                  // Premier item
array[lenght - 1]     // Dernier item.

Stocker des éléments de même type (même taille en mémoire) de manière contiguë permet à l'ordinateur de calculer la position d'un élément en mémoire en ajoutant simplement un décalage à l'adresse de base. C’est le principal avantage d’un tableau : il permet la récupération rapide, en O(1), d'un élément.

En revanche, l'ajout et la suppression d'un élément est lent car nous ne pouvons pas modifier la taille d'un tableau une fois celui-ci créé. Il est vrai que la plupart des langages de programmation nous permettent de définir des tableaux dynamiques (dynamique arrays) : ceux-ci sont flexibles car la mémoire est allouée pendant l'exécution du programme (std :: vector pour le C++ par exemple). Le mieux est de les utiliser, mais gardons à l'esprit que pour changer la taille d'un tableau, l'ordinateur doit créer un nouveau tableau et copier tous les éléments dans celui-ci en O(n).

Réduire le nombre de variables en utilisant des tableaux
Utiliser des index pour accéder rapidement à un élément (accesseur aléatoire - random accessor)
Itérer séquentiellement à travers un tableau (Boucle - Loop)
Calculer des statistiques avec nos données (Algorithmes).

Nous avons un aperçu rapide de l’utilisation de tableaux avec des exemples de code. Nous allons effectuer des opérations de parcours, de récupération et de mise à jour. Nous verrons aussi comment trouver la valeur maximale et calculer le total des bénéfices d’une série de pertes et de gains.

Et ensuite ?

Si nous ne connaissons pas les listes chaînées, faisons un tour pour comprendre les principales différences avec l'autre structure de données la plus élémentaire. Les tableaux sont également l’un des sujets les plus chers aux programmeurs et il y a toujours beaucoup de questions telles que chercher un élément ou trier un tableau en entretien.

Voyons du code utilisant à la fois les tableaux de bases et ceux dynamiques (recommandé). Nous avons opté pour le C++ comme langage de programmation pour l’illustration du code, les autres langues utilisent la même logique et le plus souvent la même syntaxe.

Initialisation

// type array_name[size];    (size must be known at compile time)
string names[5];                // names["?","?","?","?","?"]
int ages[] = {2, 3, 1, 0, 6};   //  ages[2, 3, 1, 0, 6]

// using namespace std;
// vector < type > array_name(size);  (size is optional and may be changed at running time)
vector< int > empty;                    // empty[]
vector< string > names(5);              // names["?","?","?","?","?"]
vector< int > ages = {2, 3, 1, 0, 6};   //  ages[2, 3, 1, 0, 6]
 

Accès / Mise à jour

// For both
int thirdAge = ages[2];   // Retrieve thirdAge = 1 (index starts at 0)
names[2] = "thirdName";   // Update third name : names["?","?","thirdName","?","?"]

// Using vector allows you to add values whenever you want
empty.push_back(66);  // empty[66]
empty.push_back(99);  // empty[66, 99]

Traversée / Mise à jour (Boucle - Loop)

// Display ages line by line (for both)
for (int i = 0; i < 5; ++i)
  cout << ages[i] << endl;

// Update ages - Add one year to everyone (for both)
for (int i = 0; i < 5; ++i)
  ages[i]  += 1;

// Using vector allows you use its size instead of having to know it
for (int i = 0; i < ages.size(); ++i)
  cout << ages[i] << endl;

// Vector also provides you iterators for more convenient traversal
// Here we write the ages in reverse order (from the last to the first)
for (auto it = ages.cbegin(); it != ages.cend(); ++it)
  cout << *it << endl;

C’est tout : nous avons tout pour commencer à jouer avec les tableaux et construire un processus ou programme. Nous allons juste terminer par trois cas réels simples et souvent utilisés. Disons que nous sommes un joueur de poker qui note les résultats de ses bénéfices ou de ses pertes jour après jour pendant un an.

Algorithms

Gain Maximal

// vector< T > gains = { ... }
auto it = gains.begin();
auto maxValue = *it;
++it;

for (; it != gains.end(); ++it)
  if (*it > maxValue)
    maxValue = *it;

Dernière fois que nous avons perdu

int lastLoosingTime = 0; // Number of days since last lost (0 means never lost).

for (auto it = gains.cbegin(); it != gains.cend(); ++it, ++lastLoosingTime)
  if (*it < 0)
    break;

Gain total

auto it = gains.begin();
auto totalGain = *it;
++it;

for (; it != gains.end(); ++it)
  totalGain += *it;

• The Algorithm Design Manual Book by Steven S Skiena
• Wikipedia