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.

Chaque nœud pointe vers un autre nœud.