Structure de données
Un article de Wikipédia, l'encyclopédie libre.
Vous avez de 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 |
[modifier] 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 certaines 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.
[modifier] Types de collections
[modifier] 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 :
[modifier] Files à priorités
Le type abstrait file à priorités est une collection d'éléments indexés par des clés sur lesquels ont 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é:
[modifier] 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).
- Table de hachage
- Arbre binaire de recherche ou ABR
- Arbre balancé ou arbre à critère d'équilibre.
- Arbre AVL
- Arbre 2-3-4
- Arbre rouge-noir ou arbre SBB (Symetric Binary Tree)
- Arbre B ou B-Tree
[modifier] Autres collections
[modifier] 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<str::string> définit une liste doublement chaînée pouvant contenir des chaines de caractères.
[modifier] Données en sécurité de l'information
La conception des structures de données, du point de vue de leur cohérence (intégrité principalement) est un élément clé de la robustesse et de la sécurité des logiciels en général.
Il serait illusoire de croire que la conception des structures de données n'implique pas le matériel informatique, car les différents systèmes d'exploitation gèrent en permanence des données en fonction des structures de données employées par tous les logiciels.
Par ailleurs, le traitement des données passe toujours par des infrastrucures de réseaux informatiques.
Les progiciels de gestion intégrés sont appelés en anglais data processing
Les données essentielles en sécurité de l'information sont les critères communs et les profils de protection.
La mise en œuvre d'une politique de sécurité du système d'information peut amener à revoir les structures de données en fonction des critères de sécurité.
[modifier] Liens internes
- Donnée
- Métadonnée
- Sécurité de l'information
- Critères communs
- Entity Relationship Diagram
- Business process modeling language
