Voir la source de Structure de données

En [[informatique]], une '''structure de données''' est une manière d'organiser les [[donnée]]s pour les [[traitement de l'information|traiter]] plus facilement. Une structure de données est une mise en œuvre concrète d'un [[type abstrait]].
== Objectifs ==
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ée]]s, on permet un [[traitement de l'information|traitement automatique]] de ces dernières plus efficace et rapide.

Le fait d'utiliser une structure de données appropriée à un [[Traitement de l'information|traitement informatique]] peut également faire baisser de manière significative la [[Théorie de la complexité (informatique théorique)|complexité]] d'une [[Application (informatique)|application informatique]] et ainsi contribuer à diminuer le taux d'[[Bug (informatique)|erreurs]].

== Exemples ==
Différentes structures de données existent pour des données différentes ou répondant à des contraintes algorithmiques différentes :
* structures finies :
** [[Constante (programmation informatique)|constantes]],
** [[Variable (informatique)|variables]],
** [[Enregistrement (base de données)|enregistrements]],
** structures composées finies ;
* structures indexées :
** [[Tableau (structure de données)|tableaux]] (sur [1..n]),
** [[Tableau (structure de données)|tableaux]] multidimensionnels (e.g. tableaux bidimensionnels: sur [1..n, 1..m]; sinon, tableaux de tableaux: sur [1..n][1..m]),
** [[Tableau associatif|tableaux associatifs]],
** [[Vecteur (structure de données)|vecteurs]] ;
* structures récursives :
** [[Liste (informatique)|listes]],
** [[Arbre enraciné|arbres]],
** [[Théorie des graphes|graphes]].

== Types de collections ==
=== Séquentielles ===
Une collection séquentielle permet de ranger des [[objet (informatique)|objets]] dans un ordre arbitraire.

On parle de collection [[Indexation automatique de documents|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 [[Mise en œuvre|implémentation]] particulière dépend d'un certain nombre de compromis, comme l'occupation [[Mémoire (informatique)|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 automatique de documents|indexation]], suppression d'un élément, décompte du nombre d'éléments, etc.

Il existe deux grands types de collections séquentielles :
* les [[Liste (informatique)|listes]] ;
* les [[Tableau (structure de données)|tableaux]] ou [[vecteur]]s.

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 :
* [[Pile (informatique)|pile]] ;
* [[File (structure de données)|file]].

=== Files à priorités ===
Le [[type abstrait]] [[File de priorité|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 (informatique)|Tas]] ou tas binaire
On peut implémenter une ''union'' sur les files à priorité :
* [[tas binomial]] ;
* [[tas de Fibonacci]].

=== Tables de symboles ===
Ce type de collection nommé [[tableau associatif]], dictionnaire ou ''map'' permet de ranger des objets en fonction d'une clef dans une [[Tableau associatif|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 équilibré]]
** [[Arbre AVL]]
** [[Arbre 2-3-4]]
** [[Arbre bicolore|Arbre rouge-noir]] ou arbre SBB (''symetric binary tree'')
** [[Arbre B]] ou B-tree

=== Autres collections ===
* [[Buffer circulaire|Buffer tournant]]
* [[Graphe (théorie des graphes)|Graphes]]
* [[Ensemble (informatique)|Ensemble]] 
* [[Multiensemble|Bag]] aussi appelé ''multisensemble'' ou ''sac''
* [[skip list]]
* [[Union-find]]

== Collections et typage ==
Les collections posent des problèmes de [[Type (informatique)|typage]] des [[donnée]]s stockées. Comment garantir le [[Type (informatique)|type]] d'un [[objet (informatique)|objet]] qui est stocké dans une liste par exemple ?

Ce problème n'est pas rédhibitoire dans les [[Langage informatique|langages informatiques]] à [[typage dynamique]], où le type exact de l'objet peut être vérifié à l'exécution par [[Réflexion (informatique)|introspection]]. Il est plus gênant dans les [[Langage informatique|langages informatiques]] à [[typage statique]] puisqu'il oblige le [[Développeur|programmeur]], soit à devoir [[Programmation informatique|programmer]] une [[Conteneur (informatique)|classe conteneur]] spécialisée pour chaque type de donnée à traiter, soit à violer la [[sûreté]] de typage en utilisant des [[Conversion de type|conversions de type]] (en anglais : ''coercions'').

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

== Annexes ==

=== Articles connexes ===

* [[Donnée]]
* [[Métadonnée]]
* [[Sécurité de l'information]]
* [[Arbre enraciné]]
* [[Critères communs]]
* [[Modèle entité-association|Modèle entité-relation]]
* [[Structure de contrôle]]
* [[ASN.1]]
* [[Structure de données multidimensionnelles]]
* [[Passive data structure]]

=== Liens externes ===

*[[b:Programmation C-C++/Structures et types|Structures et types]] sur [[Wikibooks|Wikilivres]].

{{Palette|Structure de données|Types de données|Informatique théorique}}
{{Portail|informatique|programmation informatique|bases de données}}

[[Catégorie:Structure de données]]