Structures de données/Introduction

Introduction

L'étude des structures de données fait suite à celle de l'algorithmique impérative. Une bonne connaissance stable de l'algorithmique impérative est une base essentielle à l'étude menée ici. L'étude de l'algorithmique fonctionnelle est d'une aide non-négligeable.

Nous n'avons donc utilisé jusqu'ici qu'une structure de données, le tableau. Cette structure de données pose un problème : elle occupe la mémoire en fonction de sa déclaration. Ce qui signifie que si on ignore combien l'utilisateur va nécessiter d'indice, il va falloir réserver le tableau le plus grand possible afin d'être sûr qu'il puisse contenir autant d'élément que l'utilisateur souhaitera. Il serait plus judicieux de réserver l'espace au fur et à mesure de la demande. C'est ce que l'on appelle la gestion dynamique de la mémoire (par opposition à statique).

Nous avons également vu que les tableaux sont génériques : c'est à dire qu'au moment de sa déclaration, nous pouvons dire que tous ses éléments sont d'un type donné et choisir ce type.

Nous avons vu que les tableaux sont homogènes : c'est à dire qu'un tableau donné ne peut contenir qu'un seul type d'élément (celui précisé dans la déclaration du tableau). Nous pourrions avoir besoin d'un tableau dont certain élément serait des entiers, d'autres des chaînes, d'autres encore des booléens. Il s'agit là de la problématique de l'hétérogénéité.

Note : attention à ne pas confondre la notion de généricité avec celle d'hétérogénéité. La première désigne la capacité à contenir des éléments d'un même type que l'on peut choisir en le fixant au moment de la déclaration. La seconde désigne la capacité à contenir des éléments de types différents.

Supposons maintenant que nous devions utiliser des formes d'information qui ne font pas partie de type de bases : les listes chaînées, les matrices, rationnels, les arbres, de l'génome, les couleurs, etc. Comment créer les éléments nécessaires au stockage de tel information quand un simple tableau ou un simple enregistrement ne suffisent plus ?

Dynamicité, généricité, hétérogénéité et la création de nouveau types non-élémentaires sont autant de problèmes traités dans ce wikilivre.

Problématique

• Comment stocker des données en mémoire en prenant de la mémoire de façon dynamique, en fonction du besoin. Ceci afin d'éviter les dépassements de mémoire et de ne pas mobiliser des ressources machines (parfois précieuses) inutilement.
• Comment stocker en mémoire une donnée si aucun type n'est intégré dans le langage ? Les langages ne peuvent intégrer toutes les structures de données possibles. Il faut parfois les implémenter soi-même.
• Comment, au sein d'une structure, gérer sa généricité, son hétérogénéité.

Pré-requis

• Algorithmique impérative : indispensable
• Algorithmique fonctionnelle : facultatif mais fortement conseillé (notamment pour l'implémentation de structures dynamiques)
• Architecture des ordinateurs : au moins les notions élémentaires sur la mémoire : mémoire statique/dynamique, représentation de valeurs en mémoire, codage sur un (entiers, caractères) ou plusieurs octets (chaînes de caractères), adressage (sur n bits)...