Informatique au lycée Faustin Fleret

Les structures de données

Le principe de base d'une structure de données, c'est de stocker des éléments auxquels le programmeur veut pouvoir accéder plus tard. On appelle les différentes utilisations possibles de la structure de données des opérations.
Par exemple, une opération courante est la lecture : on veut récupérer un élément stocké dans la structure. Il existe de nombreuses autres opérations, comme l'insertion, qui rajoute un nouvel élément dans la structure de données, ou la suppression, qui en enlève.

Toutes les structures de données ne permettent pas les mêmes opérations, et surtout elles n'ont pas toujours le même coût. Par exemple, sur certaines structures, il est très rapide d'ajouter un élément, dans d'autres c'est difficile et cela peut demander une réorganisation complète. Le coût des structures de données peut se mesurer assez finement.
Cette connaissance des coûts a deux intérêts : quand on nous donne un algorithme utilisant une structure de données particulière, on a besoin de connaître le coût (la complexité) des opérations effectuées pour évaluer la complexité globale de l'algorithme. Mais surtout, et c'est sans doute l'aspect le plus intéressant, quand on a une idée des opérations dont on a besoin pour un algorithme, on peut choisir la structure de données la plus adaptée (celle pour laquelle ces opérations sont les moins coûteuses).

Dans la pratique, la plupart des gens utilisent des algorithmes assez simples (qui ne reposent pas sur des manipulations sophistiquées), où le seul choix de la bonne structure de données peut faire la différence au niveau des performances. Bien connaître ses structures de données et savoir faire un choix joue donc un rôle très important pour le programmeur.
Parmi les structures de données linéaires il y a :

• les tableaux,
• les listes chaînées,
• les piles,
• les files.

Les tableaux :

La structure linéaire de type tableau pour lequel les éléments de même type le composant sont placés de façon contigüe en mémoire.

Pour créer un tableau, à 1 ou 2 dimensions, il faut connaître sa taille qui ne pourra être modifiée au cours du programme, et lui associer un indice pour parcourir ses éléments.

mon_tab = [5, 8, 6, 9]
ma_variable = mon_tab[2]