AccueilđŸ‡«đŸ‡·Chercher

Collection (type de données)

En programmation informatique, une collection est un regroupement d'un nombre variable d'Ă©lĂ©ments de donnĂ©es (Ă©ventuellement zĂ©ro) qui ont une signification commune pour le problĂšme Ă  rĂ©soudre et qui doivent ĂȘtre traitĂ©s ensemble d'une maniĂšre contrĂŽlĂ©e. En gĂ©nĂ©ral, les Ă©lĂ©ments de donnĂ©es sont du mĂȘme type ou, dans les langages supportant l'hĂ©ritage, dĂ©rivĂ©s d'un type ancĂȘtre commun. Une collection est un concept applicable aux types de donnĂ©es abstraits, et ne prescrit pas une implĂ©mentation spĂ©cifique en tant que structure de donnĂ©es concrĂšte, bien qu'il y ait souvent un choix conventionnel (voir Conteneur pour une discussion sur la thĂ©orie des types).

Les listes, les ensembles, les multiensembles, les arbres et les graphes sont des exemples de collections.

Les matrices (ou tables) de taille fixe ne sont gĂ©nĂ©ralement pas considĂ©rĂ©es comme des collections car elles contiennent un nombre fixe d'Ă©lĂ©ments de donnĂ©es, bien qu'elles jouent souvent un rĂŽle dans la mise en Ɠuvre des collections. Les matrices de taille variable sont gĂ©nĂ©ralement considĂ©rĂ©es comme des collections.

Collections linéaires

De nombreuses collections dĂ©finissent un ordre linĂ©aire particulier, avec un accĂšs Ă  l'une ou aux deux extrĂ©mitĂ©s. La structure de donnĂ©es rĂ©elle qui met en Ɠuvre une telle collection ne doit pas nĂ©cessairement ĂȘtre linĂ©aire - par exemple, une file de prioritĂ© est souvent mise en Ɠuvre comme un tas, qui est une sorte d'arbre. Parmi les collections linĂ©aires importantes, citons

Les listes

Dans une liste, l'ordre des Ă©lĂ©ments de donnĂ©es est important. Les doublons d'Ă©lĂ©ments de donnĂ©es sont autorisĂ©s. Des exemples d'opĂ©rations sur des listes sont la recherche d'un Ă©lĂ©ment de donnĂ©es dans la liste et la dĂ©termination de son emplacement (s'il est prĂ©sent), la suppression d'un Ă©lĂ©ment de donnĂ©es de la liste, l'ajout d'un Ă©lĂ©ment de donnĂ©es Ă  la liste Ă  un emplacement spĂ©cifique, etc. Si les principales opĂ©rations sur la liste sont l'ajout d'Ă©lĂ©ments de donnĂ©es Ă  une extrĂ©mitĂ© et le retrait d'Ă©lĂ©ments de donnĂ©es Ă  l'autre, elle sera gĂ©nĂ©ralement appelĂ©e file ou FIFO. Si les principales opĂ©rations sont l'ajout et le retrait d'Ă©lĂ©ments de donnĂ©es Ă  une seule extrĂ©mitĂ©, on parle de pile ou de LIFO. Dans les deux cas, les Ă©lĂ©ments de donnĂ©es sont maintenus dans la collection dans le mĂȘme ordre (Ă  moins qu'ils ne soient retirĂ©s et rĂ©insĂ©rĂ©s ailleurs) et ce sont donc des cas particuliers de la collection de listes. D'autres opĂ©rations spĂ©cialisĂ©es sur les listes incluent le tri oĂč, encore une fois, l'ordre des Ă©lĂ©ments de donnĂ©es est d'une grande importance.

Les piles

Une pile est une structure de données LIFO comportant deux opérations principales : push, qui ajoute un élément au "sommet" de la collection, et pop, qui retire l'élément supérieur.

Les files de priorité

Dans une file de prioritĂ©, les traces de l'Ă©lĂ©ment de donnĂ©es minimum ou maximum de la collection sont conservĂ©es selon un certain critĂšre d'ordre, et l'ordre des autres Ă©lĂ©ments de donnĂ©es n'a pas d'importance. On peut imaginer une file de prioritĂ© comme une liste qui garde toujours le minimum ou le maximum en tĂȘte, tandis que les autres Ă©lĂ©ments sont conservĂ©s dans un sac.

Les collections associatives

D'autres collections peuvent ĂȘtre interprĂ©tĂ©es comme une sorte de fonction : Ă©tant donnĂ© une entrĂ©e, la collection produit une sortie. Les collections associatives importantes incluent :

Un ensemble peut ĂȘtre interprĂ©tĂ© comme un multiensemble spĂ©cialisĂ©, qui Ă  son tour est une tableau associatif spĂ©cialisĂ©e, dans chaque cas en limitant les valeurs possibles - en considĂ©rant un ensemble comme reprĂ©sentĂ© par sa fonction caractĂ©ristique.

Les ensembles

Dans un ensemble, l'ordre des Ă©lĂ©ments de donnĂ©es n'a pas d'importance (ou est indĂ©fini) mais les Ă©lĂ©ments de donnĂ©es en double ne sont pas autorisĂ©s. Des exemples d'opĂ©rations sur les ensembles sont l'ajout et la suppression d'Ă©lĂ©ments de donnĂ©es et la recherche d'un Ă©lĂ©ment de donnĂ©es dans l'ensemble. Certains langages prennent directement en charge les ensembles. Dans d'autres, les ensembles peuvent ĂȘtre implĂ©mentĂ©s par une table de hachage avec des valeurs fictives ; seules les clĂ©s sont utilisĂ©es pour reprĂ©senter l'ensemble.

Les multiensembles

Dans un multiensemble (ou sac), comme dans un ensemble, l'ordre des Ă©lĂ©ments de donnĂ©es n'a pas d'importance, mais dans ce cas, les Ă©lĂ©ments de donnĂ©es en double sont autorisĂ©s. Des exemples d'opĂ©rations sur les multiensembles sont l'ajout et la suppression d'Ă©lĂ©ments de donnĂ©es et la dĂ©termination du nombre de doublons d'un Ă©lĂ©ment de donnĂ©es particulier prĂ©sents dans le multiensemble. Les multiensembles peuvent ĂȘtre transformĂ©s en listes par une action de tri.

Les tableaux associatifs

Dans une tableau associatif (ou carte, dictionnaire, table de consultation), comme dans un dictionnaire, une consultation sur une clĂ© (comme un mot) fournit une valeur (comme une dĂ©finition). La valeur peut ĂȘtre une rĂ©fĂ©rence Ă  une structure composĂ©e de donnĂ©es. Une table de hachage est gĂ©nĂ©ralement une mise en Ɠuvre efficace, et ce type de donnĂ©es est donc souvent appelĂ© "hachage".

Les graphes

Dans un graphe, les Ă©lĂ©ments de donnĂ©es ont des associations avec un ou plusieurs autres Ă©lĂ©ments de donnĂ©es dans la collection et sont un peu comme des arbres sans le concept de racine ou de relation parent-enfant, de sorte que tous les Ă©lĂ©ments de donnĂ©es sont des pairs. Les exemples d'opĂ©rations sur les graphes sont les traversĂ©es et les recherches qui explorent les associations d'Ă©lĂ©ments de donnĂ©es Ă  la recherche d'une propriĂ©tĂ© spĂ©cifique. Les graphes sont frĂ©quemment utilisĂ©s pour modĂ©liser des situations du monde rĂ©el et pour rĂ©soudre des problĂšmes connexes. Un exemple est le Spanning Tree Protocol, qui crĂ©e une reprĂ©sentation graphe (ou maillĂ©e) d'un rĂ©seau de donnĂ©es et dĂ©termine quelles associations entre les nƓuds de commutation doivent ĂȘtre rompues pour transformer le rĂ©seau en arbre et empĂȘcher ainsi les donnĂ©es de tourner en boucle.

Les arbres

Dans un arbre, qui est un type particulier de graphe, un élément de données racine est associé à un certain nombre d'éléments de données qui, à leur tour, sont associés à un certain nombre d'autres éléments de données dans ce qui est fréquemment considéré comme une relation parent-enfant. Chaque élément de données (autre que la racine) a un seul parent (la racine n'a pas de parent) et un certain nombre d'enfants, éventuellement zéro. Des exemples d'opérations sur les arbres sont l'ajout d'éléments de données de maniÚre à maintenir une propriété spécifique de l'arbre pour effectuer un tri, etc. et des traversées pour visiter des éléments de données dans une séquence spécifique.

Les collections d'arbres peuvent ĂȘtre utilisĂ©es pour stocker naturellement des donnĂ©es hiĂ©rarchiques, qui sont prĂ©sentĂ©es sous forme d'arbre, comme les systĂšmes de menus et les fichiers dans les rĂ©pertoires d'un systĂšme de stockage de donnĂ©es.

Des arbres spécialisés sont utilisés dans divers algorithmes. Par exemple, le tri par tas utilise un type d'arbre appelé tas.

Concept abstrait et implémentation

Comme dĂ©crit ici, une collection et les diffĂ©rents types de collections sont des concepts abstraits. Il existe dans la littĂ©rature une confusion considĂ©rable entre les concepts abstraits de l'informatique et leurs implĂ©mentations spĂ©cifiques dans divers langages ou types de langages. Les affirmations selon lesquelles les collections comme les listes, les ensembles, les arbres, etc. sont des structures de donnĂ©es, des types de donnĂ©es abstraits ou des classes doivent ĂȘtre lues en gardant cela Ă  l'esprit. Les collections sont avant tout des abstractions utiles pour formuler des solutions Ă  des problĂšmes informatiques. Vues sous cet angle, elles conservent des liens importants avec les concepts mathĂ©matiques sous-jacents qui peuvent ĂȘtre perdus lorsque l'accent est mis sur l'implĂ©mentation.

Par exemple, une file de prioritĂ© est souvent mise en Ɠuvre comme un tas, tandis qu'un tableau associatif est souvent mis en Ɠuvre comme une table de hachage, de sorte que ces types abstraits sont souvent dĂ©signĂ©s par cette mise en Ɠuvre prĂ©fĂ©rĂ©e, comme un "tas" ou un "hachage", bien que ce ne soit pas strictement correct.

Implémentations

Certaines collections peuvent ĂȘtre des types de donnĂ©es primitifs dans un langage, comme les listes, tandis que des collections plus complexes sont implĂ©mentĂ©es comme des types de donnĂ©es composites dans des bibliothĂšques, parfois dans la bibliothĂšque standard. En voici quelques exemples :

Références

  1. (en) Steven Feuerstein, Bill Pribyl et Chip Dawes, « Oracle PL/SQL Language Pocket Reference », Pocket Reference, Sebastopol, California, O'Reilly Media, Inc. « Collections in PL/SQL »,‎ (ISBN 978-0-5965-5161-2, lire en ligne, consultĂ© le ) :
    « Les collections sont implémentées en tant que TYPE. Comme pour tout type défini par le programmeur, vous devez d'abord définir le type, puis vous pouvez déclarer des instances de ce type. »

Liens externes

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplĂ©mentaires peuvent s’appliquer aux fichiers multimĂ©dias.