Retour aux articles
  • 22.06.2021

Qu’est ce que la structure de données ?

Qu’est ce que la structure de données ?

Qu'est-ce qu'une structure de données ?

Avant de définir les structures de données, revenons un peu en arrière et demandons-nous "Qu'est-ce qu'une donnée ?". Voici une réponse rapide : Les données sont des informations optimisées pour le traitement et le déplacement, des faits et des chiffres stockés sur des ordinateurs.

Les structures de données sont une manière spécifique d'organiser les données dans un format spécialisé sur un ordinateur afin que les informations puissent être organisées, traitées, stockées et récupérées rapidement et efficacement. Elles constituent un moyen de traiter l'information, en rendant les données faciles à utiliser.

Toute application, tout logiciel ou toute fondation de programme se compose de deux éléments : les algorithmes et les données. Les données sont des informations, et les algorithmes sont des règles et des instructions qui transforment les données en quelque chose d'utile à la programmation.

Quelle est la relation entre les types de données et les structures de données ?

Il existe trois types de données de base à comprendre :

Les données abstraites

Les données abstraites sont définies par leur comportement. Ce type englobe les graphes, les files d'attente, les stacks et les ensembles.

Composite (ou Composé)

Les données composites comprennent des types de données primitives combinés et incluent les tableaux, les classes, les enregistrements, les chaînes de caractères et les structs (langage de programmation C). Elles peuvent également être constituées d'autres types composites.

Primitives

Les données primitives sont classées comme des données de base et comprennent les booléens, les caractères, les entiers, les pointeurs et les nombres à virgule fixe et flottante.

Ces types de données sont les éléments constitutifs des structures de données. Les types de données indiquent à l'ordinateur comment le programmeur prévoit d'utiliser les données.

Quelles sont les classifications de la structure des données ?

Il existe différents types et classifications de structures de données et de données elles-mêmes.

Il existe trois principales classifications de structures de données, chacune consistant en une paire de caractéristiques.

Linéaires et non linéaires

Les structures linéaires organisent les données selon une séquence linéaire, comme dans un tableau, une liste ou une file d'attente. Dans les structures non linéaires, les données ne forment pas une séquence mais sont reliées à deux ou plusieurs éléments d'information, comme dans un arbre ou un graphique.

Statique et dynamique

Les structures statiques consistent en des structures et des tailles fixes et permanentes au moment de la compilation. Le tableau réserve une quantité déterminée de mémoire de réserve établie à l'avance par le programmeur. Les structures dynamiques présentent des capacités de mémoire non fixes, qui diminuent ou augmentent en fonction du programme et de ses exigences d'exécution. De plus, l'emplacement de la mémoire associée peut changer.

Homogènes et non-homogènes

Les structures de données homogènes sont constituées du même type d'élément de données, comme les collections d'éléments d'un tableau. Dans les structures non homogènes, les données ne doivent pas nécessairement être du même type, comme les structures.

Comment sont utilisées les structures de données ?

En général, les structures de données sont utilisées pour mettre en œuvre les formes physiques de types de données abstraits. Les structures de données sont un élément crucial de la conception de logiciels efficaces. Elles jouent également un rôle essentiel dans la conception d'algorithmes et dans la manière dont ces algorithmes sont utilisés dans les programmes informatiques.

Les premiers langages de programmation, tels que Fortran, C et C++, permettaient aux programmeurs de définir leurs propres structures de données. Aujourd'hui, de nombreux langages de programmation comprennent une vaste collection de structures de données intégrées pour organiser le code et les informations. Par exemple, les listes et dictionnaires de Python, ainsi que les tableaux et objets de JavaScript sont des structures de codage courantes utilisées pour stocker et récupérer des informations.

Les ingénieurs logiciels utilisent des algorithmes qui sont étroitement liés aux structures de données, comme les listes, les files d'attente et les mappings d'un ensemble de valeurs à un autre. Cette approche peut être fusionnée dans diverses applications, notamment pour gérer des collections d'enregistrements dans une base de données relationnelle et créer un index de ces enregistrements à l'aide d'une structure de données appelée arbre binaire.

Quelques exemples d'utilisation des structures de données

Le stockage des données

Les structures de données sont utilisées pour une persistance efficace des données, par exemple en spécifiant la collection d'attributs et les structures correspondantes utilisées pour stocker les enregistrements dans un système de gestion de base de données.

Ordonnancement et tri

Les structures de données telles que les arbres de recherche binaires - également connus sous le nom d'arbres binaires ordonnés ou triés - fournissent des méthodes efficaces de tri des objets, tels que les chaînes de caractères utilisées comme balises. Avec des structures de données telles que les files d'attente prioritaires, les programmeurs peuvent gérer des éléments organisés en fonction d'une priorité spécifique.

Gestion des ressources et des services

Les ressources et les services de base du système d'exploitation (SE) sont activés par l'utilisation de structures de données telles que les listes liées pour l'allocation de mémoire, la gestion des répertoires de fichiers et les arbres de structure de fichiers, ainsi que les files d'attente d'ordonnancement des processus.

Échange de données

Les structures de données définissent l'organisation des informations partagées entre les applications, comme les paquets TCP/IP.

Évolutivité

Les applications Big Data utilisent des structures de données pour allouer et gérer le stockage des données sur des sites de stockage distribués, ce qui garantit l'évolutivité et les performances. Certains environnements de programmation Big Data, comme Apache Spark, fournissent des structures de données qui reflètent la structure sous-jacente des enregistrements des bases de données afin de simplifier les requêtes.

L'indexation

Des structures de données encore plus sophistiquées, comme les arbres B, sont utilisées pour indexer des objets, tels que ceux stockés dans une base de données.

La recherche

Les index créés à l'aide d'arbres de recherche binaires, d'arbres B ou de tables de hachage accélèrent la recherche d'un élément spécifique.

Comment choisir une structure de données ?

Lorsqu'ils choisissent une structure de données pour un programme ou une application, les développeurs doivent tenir compte des réponses aux trois questions suivantes :

Opérations prises en charge

De quelles fonctions et opérations le programme a-t-il besoin ?

La complexité de calcul

Quel niveau de performance de calcul est tolérable ? Pour la vitesse, une structure de données dont les opérations s'exécutent en un temps linéaire par rapport au nombre d'éléments gérés.

L'élégance de la programmation

L'organisation de la structure de données et son interface fonctionnelle sont-elles faciles à utiliser ?