Formation structures de données dynamiques langage C, tutoriel & guide de travaux pratiques en pdf.

Structure de Donnée Abstraite

C’est quoi une SDA ?
C’est un ensemble de données reliées logiquement, et dont l’organisation permet la manipulation individuelle ou collective de ces données. Cette notion de SDA est indépendante de tout langage de programmation. Un exemple élémentaire est le type entier (int). Les actions possibles sont l’affectation, la lecture au clavier, les opérations +,*,-, /, … Un exemple plus complexe, défini comme type construit dans les langages de programmation est le tableau (type []). Il contient divers éléments d’un même type de base. Les actions sont : définir/demander la taille, lire/écrire un élément par son numéro, …
Le concepteur du logiciel va regrouper tous les éléments informatiques (types, constantes, procédures et fonctions) qui concourent à la définition d’une SDA dans un module informatique. Cet élément deviendra à son tour une brique de base pour de nouvelles conceptions au même titre que les types existant dans les langages classiques.

Spécification et implémentation d’une SDA
Dans le même esprit de l’indépendance par rapport à un langage de programmation, une SDA se spéficifie par la description logique du contenu et des actions possibles sur les données sans connaître sa programmation effective. Une SDA définit une abstraction des données et de leurs manipulations et cache l’implémentation. Reprenons l’exemple des entiers. Aucun besoin de connaître la manière de coder chaque entier en mémoire pour comprendre les actions et opérations associées. La spécification logique est simplement celle de l’entier mathématique.
On décrit en général l’ensemble des actions possibles en 4 classes :
• Les constructeurs (fabriquer une donnée à partir de valeurs de base)
• Les sélecteurs (interroger la SDA sur ces valeurs de base)
• Les modificateurs
• Les itérateurs (parcourir toutes les données de la SDA)
Exemples d’actions pour le tableau :
• Modificateur : t[i]=a ;
• Sélecteur : if (t[i]==a) …
• Itérateur : index de l’élément [i]
Le tableau est un exemple significatif de la description d’un ensemble (toujours au sens mathématique) avec éventuellement répétition de la même valeur (alors appelé « sac »). Bien évidemment, un constructeur comme « ajouter » n’aura pas la même signification pour un ensemble (E ∪ {x}=E si x ∈ E) et pour un sac (S ∪ {x} ≠ S ∀ S). Les structures de données que nous allons étudier sont vues essentiellement comme des représentations informatiques d’ensembles de valeurs. Les différences résident dans leur structure : linéaire (liste, file, pile, …) ou hiérarchique (arbre binaire, arbre de recherche, …). Celles-ci influent sur la performance – appelée « complexité » – des actions, que ce soit en occupation mémoire (en espace), ou un temps d’exécution (en temps).
Une manière élégante (et souvent optimale) de spécifier et d’implémenter des SDA fait appel à la récursivité. La définition récursive d’un objet fait référence à l’objet lui même..