Retour aux articles
  • 23.06.2021

Quels sont les types de structures de données ?

Quels sont les types de structures de données ?

Les structures de données sont un concept de programmation très important. Elles nous fournissent un moyen de stocker, d'organiser et de récupérer des données de manière efficace. Les structures de données sont utilisées pour faciliter le travail avec nos données. Il existe de nombreuses structures de données qui nous aident dans ce domaine.

 

 

Tableau

La première structure de données à apprendre en programmation et la structure de données la plus courante et la plus utilisée dans de nombreuses applications.

Le parcours de tout débutant en programmation commence par la résolution des questions relatives aux tableaux. Cette structure de données est utilisée dans toutes les situations possibles où on doit rassembler les objets en un seul endroit. Qu'il s'agisse d'un logiciel simple ou complexe ou d'une application Web, le tableau est principalement utilisé pour stocker et afficher les données de manière dynamique sur les pages Web.

Pile (Stack)

La pile suit une technique "LIFO" pour stocker et récupérer les éléments. L'élément qui est stocké à la fin sera le premier à être récupéré de la pile. La pile a les fonctions primaires suivantes :

  • Push() : Pour insérer un élément dans la pile.
  • Pop() : Pour retirer un élément de la pile.

Un éditeur de texte tel que Notepad ou Microsoft Word utilise une structure de données en pile pour accomplir des tâches d'annulation dans son éditeur. Un autre bon exemple de pile est le navigateur de votre ordinateur portable ou de votre système.

Liste liée

Une autre structure de données populaire et commune parmi les programmeurs est la liste chaînée. Les listes liées stockent des collections d'éléments dans un ordre linéaire. Chaque élément d'une liste liée contient un élément de données et un lien, ou une référence, vers l'élément suivant de la même liste.

Par exemple, lorsqu’on crée une liste de lecture sur un smartphone, elle fonctionne sur le concept de la liste liée. Ces chansons sont jouées une par une, elles sont connectées et on peut passer de la chanson trois à la chanson quatre mais pas revenir en arrière. C’est le comportement d'une liste singulièrement liée.

Lorsqu’on met en œuvre la fonctionnalité permettant de lire la chanson dans les deux sens, elle suit le comportement d'une liste doublement liée. Dans une liste doublement liée, les nœuds sont connectés dans les deux sens. La navigation bidirectionnelle est donc possible.

Lorsqu’on lit les chansons en mode répétition, elles suivent le comportement d'une liste circulaire liée. Dans une liste circulaire, le dernier nœud est connecté au premier nœud. Ainsi, une fois la dernière chanson terminée, la première chanson sera rejouée et la lecture se fera en mode cyclique, sans jamais s'arrêter.

Graphique

La structure de données graphique est une structure de données très puissante. Le graphique peut représenter non seulement la terre, mais aussi l'univers entier.

Lorsqu’on utilise Google Map, toutes les villes sont reliées comme un graphique avec des informations sur la distance. Il existe de nombreuses façons de se rendre d'une ville à l'autre, mais pour trouver le chemin le plus court entre deux villes, on doit utiliser certains algorithmes.

Pour décider du chemin le plus court vers votre destination, l'algorithme de Dijkstra active notre système de navigation/GPS dans notre téléphone. Uber utilise l'algorithme de Hungarian pour affecter chaque voiture aux personnes qui recherchent un trajet.

Algorithme de recherche binaire

L'algorithme de recherche binaire est également connu sous le nom de recherche par demi-intervalle, recherche logarithmique ou hachage binaire. Dans cet algorithme, nous recherchons la valeur cible dans un tableau trié.

Cet algorithme facilite le processus de recherche car on n’a pas besoin de comparer chaque élément de la liste de nombres. La recherche binaire est un moyen rapide de rechercher la valeur cible dans une liste ordonnée de données. Elle donne la possibilité d'effectuer ce processus de manière efficace.

L'un des scénarios réels de cet algorithme est la validation des informations d'identification des utilisateurs dans une application. En utilisant la recherche binaire, on peut valider les informations d'identification de millions d'utilisateurs en une fraction de seconde.

Cet algorithme est également utilisé dans les bibliothèques de nombreux langages de programmation tels que Java, .NET, C++ STL, etc. La méthode list.sort() de Python utilise Timsort qui (AFAIK) utilise la recherche binaire pour localiser les positions des éléments.

Structure de données Trie

À ne pas confondre avec un arbre, les arbres sont des structures de données qui stockent des chaînes de caractères comme des éléments de données et sont placés dans un graphique visuel. Les tries sont également appelées arbres de mots-clés ou arbres de préfixes. Chaque fois qu’on utilise un moteur de recherche et que vous recevez des suggestions automatiques, on est témoin de la structure de données trie en action.

Algorithme de tri par fusion

Le tri par fusion fonctionne sur le concept de la technique "diviser pour mieux régner". Nous divisons la liste en plusieurs sous-liste jusqu'à ce que la sous-liste ne contienne plus un seul élément. Ensuite, nous fusionnons ces sous-listes pour obtenir la liste triée des éléments.

La plupart des sites de e-commerce ont une section "Vous pourriez aimer". Cette section maintient le tableau de tous les comptes d'utilisateurs et ensuite celui qui a le moins d'inversion avec notre tableau de choix, commence à recommander ce qu'ils ont acheté, ou ce qu'ils aiment.

Algorithmes de palindrome

Le nombre ou la chaîne de caractères palindrome se lit dans l'ordre inverse.

Les palindromes sont utilisés dans le traitement des séquences d'ADN. Mais comment sont-ils utilisés dans ce traitement ?

Un grand nombre de séquences d'ADN deviennent disponibles. Pour stocker les informations sur ces séquences d'ADN, nous utilisons des bases de données de biologie moléculaire. La capacité de ces bases de données sera plus importante à l'avenir, il est donc important de communiquer et de stocker les données efficacement dans la base de données.

Il est important de compresser ces séquences d'ADN pour une meilleure performance. Pour comprimer ces séquences, on peut utiliser la méthode CTW (Context Tree Weighting Method). Cette méthode permet de compresser les séquences d'ADN en moins de deux bits par symbole.

On connaît principalement deux structures caractéristiques des séquences d'ADN. L'une est le palindrome ou les compliments inversés et l'autre les répétitions approximatives. En utilisant le hachage et la programmation dynamique, l'algorithme recherche les répétitions approximatives et les palindromes avant de coder le symbole suivant. S'il trouve un palindrome ou une répétition approximative avec une longueur suffisante, l'algorithme le représente avec la longueur et la distance.

Les nombres Armstrong

Dans les nombres Armstrong, la somme des cubes des chiffres d'un nombre est égale au nombre lui-même. Par exemple, 153 et 371 sont des nombres Armstrong. Les nombres d'Armstrong sont principalement utilisés dans les applications de sécurité des données pour le cryptage et le décryptage des données.

Les nombres Armstrong sont mentionnés pour les réseaux de capteurs sans fil. Ils ont utilisé des algorithmes de sécurité basés sur Armstrong où une clé de 128 bits est générée en utilisant le nombre Armstrong. Elle est utilisée dans l'algorithme AES pour le cryptage et le décryptage des données.

Codage de Huffman

Le codage de Huffman est utilisé en conjonction avec la cryptographie et la compression de données. Il est utilisé pour la compression de données sans perte. Basé sur la probabilité, il est mis en œuvre de manière à ce que vous n'ayez pas besoin de conserver plusieurs copies de la même chose.

Le codage de Huffman est utilisé dans des formats de compression tels que GZIP, PKZIP (winzip, etc.) et BZIP2. Toutes les communications avec et depuis l'internet utilisent le codage Huffman. La plupart des fichiers d'image tels que JPEG et PNG sont codés en Huffman. De même, les fichiers musicaux tels que les MP3 sont codés en Huffman.

Le code Huffman convertit les codes de longueur fixe en codes de longueur variable. Ces derniers sont ensuite compressés à l'aide des techniques JPEG et MPEG qui génèrent le taux de compression souhaité.

Programmation dynamique

Le problème du Knapsack 0-1, les problèmes de rupture de mots, la plus longue suite commune, tous ces problèmes sont les plus populaires et les plus courants de la programmation dynamique.

La programmation dynamique est largement utilisée en bioinformatique, en mathématiques et en économie. En bioinformatique, des tâches telles que l'alignement des séquences, le repliement des protéines, la prédiction de la structure de l'ARN et la liaison protéine-ADN utilisent la programmation dynamique.

En mathématiques, la programmation dynamique est utilisée dans la multiplication des matrices, qui est largement utilisée dans la technologie des fusées. La trajectoire des fusées est décidée en résolvant de nombreux paramètres. Tous les problèmes de prise de décision peuvent être résolus de manière optimale à l'aide de la programmation dynamique.