étude de quelques structures outils

La recherche de mises en œuvre efficacies pour les structures de donnees fondamentales conduit a raffiner celles-ci par des structures de donnees secondaires. Comme par un systeme d’echafaudages, la realisation de ce qui releve du niveau abstrait s’appuie sur des structures de donnees concretes. S’il est important de definir avec precision ce que l’on veut realiser (la structure de donnees abstraite), il est tout aussi important de maitriser les outils (les structures de donnees concretes) avant de se lancer dans le travail de mise en oeuvre. C’est notre objectif pour ce chapitre. En nous interessant aux listes, aux arbres et enfin aux sacs, nous nous donnons les moyens, selon les cas, de specifier ou d’implanter des structures de donnees. Alors que les tableaux font partie integrante de la theorie des ensembles, dont les principes elementaires sont rappeles au chapitre 1 (un tableau a une dimension est une fonction totale definie sur un intervalle d’entiers), ce n’est a priori pas le cas des listes, des arbres ni des sacs qui resultent de l’ajout d’une « couche » supplementaire qui enveloppe la theorie des ensembles.