Structuration des données

Structure de données

En informatique, une structure de données est une structure logique destinée à contenir des données, afin de leur donner une organisation permettant de simplifier leur traitement. Une structure de données implémente concrètement un type abstrait.

Sommaire

Objectifs de l'organisation des données

Pour prendre un exemple de la vie quotidienne, on peut présenter des numéros de téléphone par département, par nom, par profession (comme les Pages jaunes), par numéro téléphonique (comme les annuaires destinés au télémarketing), par rue et/ou une combinaison quelconque de ces classements. À chaque usage correspondra une structure d'annuaire appropriée.

En organisant d'une certaine manière les données, on permet un traitement automatique de ces dernières plus efficace et rapide.

Le fait d'utiliser une structure de données appropriée à un traitement informatique peut également faire baisser de manière significative la complexité d'une application informatique et ainsi participer à faire baisser le taux d'erreurs.

Types de collections

Collections séquentielles

Une collection séquentielle permet de ranger des objets dans un ordre arbitraire.

On parle de collection indexée quand on peut accéder à chaque élément de la collection par un numéro d'ordre (l'index). Le choix d'une implémentation particulière dépend d'un certain nombre de compromis, comme l'occupation mémoire ou les performances requises pour diverses opérations de base : itération, ajout d'un élément (au début, à la fin ou encore dans un emplacement quelconque de la collection), indexation, suppression d'un élément, décompte du nombre d'éléments, etc.

Il existe deux grands types de collections séquentielles :

Un certain nombre de structures de données sont des restrictions de collections séquentielles, qui n'autorisent qu'un sous-ensemble des opérations de base :

Files à priorités

Le type abstrait file à priorités est une collection d'éléments indexés par des clés sur lesquels on peut effectuer deux opérations: l'insertion d'un élément et l'extraction de l'élément de plus grande clé.

  • Tas ou tas binaire

On peut implémenter une union sur les files à priorité:

Tables de symboles ou collections mappées

Ce type de collection nommé dictionnaire ou map permet de ranger des objets en fonction d'une clef dans une table de symboles. La clef doit généralement respecter un certain nombre d'invariants pour être valide (valeur de hachage ou résultats de la comparaison par exemple).

Autres collections

Collections et typage

Les collections posent des problèmes de typage des données stockées. Comment garantir le type d'un objet qui est stocké dans une liste par exemple ?

Ce problème n'est pas rédhibitoire dans les langages informatiques à typage dynamique, où le type exact de l'objet peut être vérifié à l'exécution par introspection. Il est plus gênant dans les langages informatiques à typage statique puisqu'il oblige le programmeur, soit à devoir programmer une classe container spécialisée pour chaque type de donnée à traiter, soit à violer la sûreté de typage en utilisant des coercions.

Cette difficulté a conduit de nombreux langages informatiques à supporter la programmation générique pour définir des types paramétrés. Par exemple en C++, la commande std::list<std::string> définit une liste doublement chaînée pouvant contenir des chaines de caractères.

Voir aussi

Articles connexes

Liens externes

Ce document provient de « Structure de donn%C3%A9es ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Structuration des données de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Gestion des données — La gestion des données est une discipline de gestion qui tend à valoriser les données en tant que ressources numériques. La gestion des données permet d envisager le développement d architectures, de réglementations, de pratiques et de procédures …   Wikipédia en Français

  • Gestion Des Données — La gestion des données aussi appelée gestion en jargon informatique comprend toutes les disciplines relatives à la gestion des données en tant que ressources numériques valorisables. Selon la définition de DAMA, la gestion de la ressource donnée… …   Wikipédia en Français

  • Qualite des donnees — Qualité des données Pour les articles homonymes, voir qualité. La qualité des données, en informatique se référe à la conformité des données aux usages prévus, dans les modes opératoires, les processus, les prises de décision, et la planification …   Wikipédia en Français

  • Qualité des données — Pour les articles homonymes, voir qualité. La qualité des données, en informatique se référe à la conformité des données aux usages prévus, dans les modes opératoires, les processus, les prises de décision, et la planification (J.M. Juran). De… …   Wikipédia en Français

  • Données — Donnée Dans les technologies de l information (TI), une donnée est une description élémentaire, souvent codée, d une chose, d une transaction d affaire, d un événement, etc. Les données peuvent être conservées et classées sous différentes… …   Wikipédia en Français

  • Données informatiques — Donnée Dans les technologies de l information (TI), une donnée est une description élémentaire, souvent codée, d une chose, d une transaction d affaire, d un événement, etc. Les données peuvent être conservées et classées sous différentes… …   Wikipédia en Français

  • Données numériques — Donnée Dans les technologies de l information (TI), une donnée est une description élémentaire, souvent codée, d une chose, d une transaction d affaire, d un événement, etc. Les données peuvent être conservées et classées sous différentes… …   Wikipédia en Français

  • Structuration du contenu disciplinaire de la botanique — Essai de structuration du contenu disciplinaire de la Botanique. Note liminaire : La botanique peut être envisagée dans un sens large qui inclut la biologie végétale (aujourd hui compartiment des « Sciences de la Vie ») ou dans un… …   Wikipédia en Français

  • Donnees archeologiques sur les Philistins — Données archéologiques sur les Philistins Le terme Philistins, tout comme le terme Hébreux, appartient au vocabulaire de la Bible[1]. Dans la Bible, les Philistins, à l époque de Saül et de David, sont géographiquement situés sur les terres de l… …   Wikipédia en Français

  • Structuration du contenu disciplinaire de la Botanique — Essai de structuration du contenu disciplinaire de la Botanique. Note liminaire : La botanique peut être envisagée dans un sens large qui inclut la biologie végétale (aujourd hui compartiment des « Sciences de la Vie ») ou dans un… …   Wikipédia en Français


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.