En informatique, une structure de données est l'organisation et la mise en œuvre de valeurs et d'informations. En termes simples, la structure des données est la façon d'organiser les données de manière efficace. Les structures de données se distinguent des types de données abstraites par la manière dont elles sont utilisées. Les structures de données sont la mise en œuvre de types de données abstraites dans un cadre concret et physique. Elles le font en utilisant des algorithmes. Cela peut être vu dans la relation entre la liste (type de données abstraites) et la liste liée (structure de données). Une liste contient une séquence de valeurs ou de bits d'information. Une liste liée possède également un "pointeur" ou une "référence" entre chaque nœud d'information qui pointe vers l'élément suivant et le précédent. Cela permet d'avancer ou de reculer dans la liste. En outre, les structures de données sont souvent optimisées pour certaines opérations. Trouver la meilleure structure de données lors de la résolution d'un problème est une partie importante de la programmation. La structure des données est un moyen systématique de stocker les données
Structure de données
Structures de données de base
Array
Le type de structure de données le plus simple est un tableau linéaire. Aussi connu sous le nom de tableau unidimensionnel. Un tableau contient plusieurs valeurs du même type (Integer, Floats, String, etc.). L'accès aux éléments du tableau est très rapide. Un tableau est normalement de taille fixe. Une fois la taille du tableau définie au départ, il peut être impossible d'augmenter la taille du tableau sans créer un nouveau tableau plus grand et copier toutes les valeurs dans le nouveau tableau. En informatique, une structure de données de tableau ou simplement un tableau est une structure de données constituée d'une collection d'éléments (valeurs ou variables), chacun étant identifié par au moins un index ou une clé de tableau. Un tableau est stocké de manière à ce que la position de chaque élément puisse être calculée à partir de son tuple d'index par une formule mathématique.
Par exemple, un tableau de 10 variables entières, avec les indices 0 à 9, peut être stocké sous forme de 10 mots aux adresses mémoire 2000, 2004, 2008, 2036, de sorte que l'élément avec l'indice i a l'adresse 2000 + 4 × i.
Comme le concept mathématique d'une matrice peut être représenté par une grille à deux dimensions, les tableaux à deux dimensions sont aussi parfois appelés des matrices. Dans certains cas, le terme "vecteur" est utilisé en informatique pour désigner un tableau, bien que les tuples plutôt que les vecteurs soient l'équivalent mathématique le plus correct. Les tableaux sont souvent utilisés pour implémenter des tableaux, en particulier des tableaux de recherche ; le mot tableau est parfois utilisé comme synonyme de tableau.
Les tableaux sont parmi les structures de données les plus anciennes et les plus importantes, et sont utilisés par presque tous les programmes. Ils peuvent également être utilisés pour mettre en œuvre de nombreuses autres structures de données, telles que des listes et des chaînes de caractères. Ils exploitent efficacement la logique d'adressage des ordinateurs. Dans la plupart des ordinateurs modernes et de nombreux dispositifs de stockage externes, la mémoire est un tableau unidimensionnel de mots, dont les index sont leurs adresses. Les processeurs, en particulier les processeurs vectoriels, sont souvent optimisés pour les opérations de tableau.
Les tableaux sont utiles car les indices des éléments peuvent être calculés au moment de l'exécution. Cette caractéristique permet, entre autres, à un seul énoncé itératif de traiter arbitrairement de nombreux éléments d'un tableau. Pour cette raison, les éléments d'une structure de données de tableau doivent avoir la même taille et doivent utiliser la même représentation des données. L'ensemble des tuples d'index valides et les adresses des éléments (et donc la formule d'adressage des éléments) sont généralement, mais pas toujours, fixés pendant l'utilisation du tableau.
Le terme "array" est souvent utilisé pour désigner le type de données "array", un type de données fourni par la plupart des langages de programmation de haut niveau qui consiste en une collection de valeurs ou de variables pouvant être sélectionnées par un ou plusieurs indices calculés au moment de l'exécution. Les types de tableaux sont souvent mis en œuvre par des structures de tableaux ; cependant, dans certains langages, ils peuvent être mis en œuvre par des tables de hachage, des listes liées, des arbres de recherche ou d'autres structures de données.
Liste des liens
Une structure de données liées est un ensemble d'informations/données reliées entre elles par des références. Les données sont souvent appelées nœuds. Les références sont souvent appelées liens ou pointeurs. À partir de là, les mots nœud et pointeur seront utilisés pour ces concepts.
Dans les structures de données liées, les pointeurs sont seulement déréférencés ou comparés pour l'égalité. Ainsi, les structures de données liées sont différentes des tableaux, qui nécessitent l'ajout et la soustraction de pointeurs.
Les listes liées, les arbres de recherche et les arbres d'expression sont tous des structures de données liées. Ils sont également importants dans les algorithmes tels que le tri topologique et la recherche d'ensembles d'unions.
Stack
Une pile est une structure de données de base qui peut être logiquement pensée comme une structure linéaire représentée par une véritable pile physique, une structure où l'insertion et la suppression d'éléments ont lieu à une extrémité appelée sommet de la pile. Le concept de base peut être illustré en considérant votre ensemble de données comme une pile d'assiettes ou de livres où vous ne pouvez retirer de la pile que l'élément du haut afin d'en retirer des choses. Cette structure est utilisée tout au long de la programmation.
L'implémentation de base d'une pile est également appelée structure "Dernier entré, premier sorti" ; cependant, il existe différentes variantes d'implémentations de piles.
Il y a essentiellement trois opérations qui peuvent être effectuées sur les piles. Elles sont :
- l'insertion ("pousser") d'un objet dans une pile
- supprimer ("popping") un article de la pile
- afficher le contenu de l'élément supérieur de la pile ("peeking")
Queue
Une file d'attente est un type de données abstraites ou une structure de données linéaire, dans laquelle le premier élément est inséré à partir d'une extrémité (la "queue"), et la suppression de l'élément existant a lieu à partir de l'autre extrémité (la "tête"). Une file d'attente est une structure "First In First Out". Le "premier entré, premier sorti" signifie que les éléments placés dans la file d'attente en premier sortiront en premier, et les éléments placés dans la file d'attente en dernier sortiront en dernier. Les files d'attente sont un exemple de file d'attente. La première personne de la file passe en premier, et la dernière personne de la file passe en dernier.
Le processus d'ajout d'un élément à une file d'attente est appelé "mise en file d'attente" et le processus de retrait d'un élément d'une file d'attente est appelé "retrait de la file d'attente".
Graphique
Un graphe est un type de données abstraites qui est destiné à mettre en œuvre les concepts de graphe et d'hypergraphe issus des mathématiques.
Une structure de données de graphe consiste en un ensemble fini (et éventuellement mutable) de paires ordonnées, appelées arêtes ou arcs, de certaines entités appelées nœuds ou sommets. Comme en mathématiques, on dit qu'une arête (x,y) pointe ou va de x à y. Les nœuds peuvent faire partie de la structure du graphe, ou être des entités externes représentées par des indices ou des références entières. Une structure de données de graphe peut également associer à chaque arête une valeur d'arête, telle qu'une étiquette symbolique ou un attribut numérique.
Arbre
L'arbre est l'une des structures de données avancées les plus puissantes. Il apparaît souvent dans des sujets avancés tels que l'intelligence artificielle (IA) et le design. Étonnamment, l'arbre est important dans une application beaucoup plus fondamentale - la tenue d'un index efficace.
Lorsqu'un arbre est utilisé, il y a de fortes chances qu'un indice soit utilisé. Le type d'index le plus simple est une liste triée de champs clés. Un arbre a normalement une structure définie. Dans le cas d'une arborescence binaire, vous pouvez utiliser une recherche binaire pour localiser n'importe quel élément sans avoir à regarder chaque élément.
Le type de données de l'arbre est un type de graphe, ce qui signifie que de nombreux algorithmes conçus pour parcourir un graphe fonctionnent également avec un arbre ; cependant, les algorithmes peuvent être très similaires et doivent avoir un nœud de départ dédié, c'est-à-dire le nœud sans autres nœuds qui lui sont reliés.
Le problème d'une simple liste ordonnée se pose lorsque vous commencez à ajouter de nouveaux articles et que vous devez maintenir la liste ordonnée - cela peut être fait de manière assez efficace mais nécessite quelques modifications. En outre, un index linéaire n'est pas facile à partager car l'ensemble de l'index doit être "verrouillé" lorsqu'un utilisateur le modifie, alors qu'une "branche" d'un arbre peut être verrouillée, laissant les autres branches modifiables par les autres utilisateurs (car ils ne peuvent pas être affectés).
Table de hachage
Une table de hachage est un tableau dans lequel chaque index pointe vers une liste liée basée sur une valeur de hachage. Une valeur de hachage est une valeur déterminée par une fonction de hachage. Une fonction de hachage détermine une valeur unique basée sur les données qu'elle stocke. Cela permet d'accéder aux données en temps constant car l'ordinateur sait toujours où chercher.
Questions et réponses
Q : Qu'est-ce qu'une structure de données ?
R : Une structure de données est l'organisation et la mise en œuvre de valeurs et d'informations dans un ordinateur de manière à ce qu'elles puissent être facilement comprises et utilisées.
Q : En quoi les structures de données diffèrent-elles des types de données abstraits ?
R : Les structures de données sont des implémentations de types de données abstraits dans un cadre concret et physique.
Q : Comment les structures de données utilisent-elles les algorithmes ?
R : Les structures de données utilisent des algorithmes pour mettre en œuvre des types de données abstraits dans un cadre concret.
Q : Pouvez-vous donner un exemple de structure de données ?
R : Une liste chaînée est un exemple de structure de données, qui contient un "pointeur" ou une "référence" entre chaque nœud d'information.
Q : Pourquoi les structures de données sont-elles optimisées pour certaines opérations ?
R : Les structures de données sont souvent optimisées pour certaines opérations afin d'améliorer l'efficacité et la vitesse du code.
Q : Pourquoi est-il important de trouver la meilleure structure de données en programmation ?
R : Il est important de trouver la meilleure structure de données en programmation, car cela peut avoir un impact significatif sur l'efficacité et la rapidité du code lors de la résolution d'un problème.
Q : Quelle est la définition d'une structure de données en termes simples ?
R : La structure de données est une manière systématique de stocker des données dans un ordinateur afin qu'elles soient plus facilement compréhensibles et exploitables.