Technologie

8 structures de données communes que chaque programmeur doit connaître

8 structures de données communes que chaque programmeur doit connaître


Une introduction rapide à 8 structures de données couramment utilisées

0*DKoctRl5mJ xoQIK - 8 structures de données communes que chaque programmeur doit connaître

Structures de données sont un moyen spécialisé d'organiser et de stocker des données dans des ordinateurs de manière à pouvoir effectuer des opérations sur les données stockées plus efficacement. Les structures de données ont un champ d'utilisation large et diversifié dans les domaines de l'informatique et du génie logiciel.

Les structures de données sont utilisées dans presque tous les programmes ou systèmes logiciels qui ont été développés. De plus, les structures de données relèvent des principes fondamentaux de l'informatique et du génie logiciel. Il s'agit d'un sujet clé pour les questions d'entrevue en génie logiciel. Par conséquent, en tant que développeurs, nous devons avoir une bonne connaissance des structures de données.

Dans cet article, je vais expliquer brièvement 8 structures de données couramment utilisées que chaque programmeur doit connaître.

Un tableau est une structure de taille fixe, qui peut contenir des éléments du même type de données. Il peut s'agir d'un tableau d'entiers, d'un tableau de nombres à virgule flottante, d'un tableau de chaînes ou même d'un tableau de tableaux (appelé tableaux multidimensionnels).

UNE liste liée est une structure séquentielle qui consiste en une séquence d'éléments en ordre linéaire qui sont liés les uns aux autres. Les listes liées fournissent une représentation simple et flexible des ensembles dynamiques.

Examinons les termes suivants concernant les listes chaînées. Vous pouvez vous faire une idée claire en vous référant à la figure 2.

  • Les éléments d'une liste chaînée sont appelés noeuds.
  • Chaque nœud contient un clé et un pointeur sur son nœud successeur, appelé suivant.
  • L'attribut nommé tête pointe vers le premier élément de la liste chaînée.
  • Le dernier élément de la liste chaînée est appelé queue.

UNE empiler est un LIFO (Last In First Out - l'élément placé enfin peut être consulté en premier) structure qui peut être trouvée couramment dans de nombreux langages de programmation. Cette structure est appelée «pile» car elle ressemble à une pile du monde réel - une pile d'assiettes.

Ci-dessous sont les 2 opérations de base qui peuvent être effectuées sur une pile. Veuillez vous référer à la figure 3 pour mieux comprendre les opérations de la pile.

  • Pousser: Insérez un élément en haut de la pile.
  • Pop: Supprimer l'élément le plus haut et le renvoyer.

De plus, les fonctions suivantes sont fournies pour une pile afin de vérifier son état.

  • Coup d'oeil: Retourne l'élément supérieur de la pile sans le supprimer.
  • est vide: Vérifiez si la pile est vide.
  • est rempli: Vérifiez si la pile est pleine.

UNE queue est un FIFO (First In First Out - l'élément placé en premier peut être consulté en premier) structure qui peut être trouvée couramment dans de nombreux langages de programmation. Cette structure est nommée «file d'attente» car elle ressemble à une file d'attente du monde réel - des personnes qui attendent dans une file d'attente.

Ci-dessous sont les 2 opérations de base qui peuvent être effectuées sur une file d'attente. Veuillez vous référer à la figure 4 pour mieux comprendre les opérations de la pile.

  • Mettre en file d'attente: Insère un élément à la fin de la file d'attente.
  • Dequeue: Supprime l'élément du début de la file d'attente.

UNE Table de hachage est une structure de données qui stocke des valeurs auxquelles sont associées des clés. De plus, il prend en charge la recherche efficacement si nous connaissons la clé associée à la valeur. Il est donc très efficace pour insérer et rechercher, quelle que soit la taille des données.

Adressage direct utilise le mappage un à un entre les valeurs et les clés lors du stockage dans une table. Cependant, il existe un problème avec cette approche lorsqu'il existe un grand nombre de paires clé-valeur. Le tableau sera énorme avec autant d'enregistrements et peut être impossible, voire impossible à stocker, compte tenu de la mémoire disponible sur un ordinateur typique. Pour éviter ce problème, nous utilisons tables de hachage.

Fonction de hachage

Une fonction spéciale nommée fonction de hachage (h) est utilisé pour surmonter le problème susmentionné dans l'adressage direct.

En accès direct, une valeur avec clé k est stocké dans la fente k. En utilisant la fonction de hachage, nous calculons l'indice de la table (slot) à laquelle chaque valeur va. La valeur calculée à l'aide de la fonction de hachage pour une clé donnée est appelée valeur de hachage qui indique l'index de la table à laquelle la valeur est mappée.

  • h: Fonction de hachage
  • k: Clé dont la valeur de hachage doit être déterminée
  • m: Taille de la table de hachage (nombre d'emplacements disponibles). Une valeur première qui n'est pas proche d'une puissance exacte de 2 est un bon choix pour m.

UNE arbre est une structure hiérarchique où les données sont organisées hiérarchiquement et sont liées entre elles. Cette structure est différente d'une liste chaînée alors que, dans une liste chaînée, les éléments sont liés dans un ordre linéaire.

Arbres de recherche binaires

UNE arbre de recherche binaire (BST), comme son nom l'indique, est un arbre binaire où les données sont organisées dans une structure hiérarchique. Cette structure de données stocke les valeurs dans un ordre trié que nous examinerons en détail au cours de cette leçon.

Chaque nœud dans une arborescence de recherche binaire comprend les attributs suivants.

  1. clé: La valeur stockée dans le nœud.
  2. la gauche: Le pointeur vers l'enfant de gauche.
  3. droite: Le pointeur vers le bon enfant.
  4. p: Le pointeur vers le nœud parent.

Un arbre de recherche binaire présente une propriété unique qui le distingue des autres arbres. Cette propriété est connue sous le nom de propriété d'arbre de recherche binaire.

Laisser X être un nœud dans une arborescence de recherche binaire.

  • Si y est un nœud dans le la gauche sous-arbre de x, puis y.key ≤ x.key
  • Si y est un nœud dans le droite sous-arbre de x, puis touche y ≥ clé x

UNE Tas est un cas particulier d'arbre binaire où les nœuds parents sont comparés à leurs enfants avec leurs valeurs et sont organisés en conséquence.

Voyons comment nous pouvons représenter des tas. Les tas peuvent être représentés à l'aide d'arbres et de tableaux. Les figures 7 et 8 montrent comment nous pouvons représenter un tas binaire à l'aide d'un arbre binaire et d'un tableau.

Les tas peuvent être de 2 types.

  1. Min tas - la clé du parent est inférieure ou égale à celle de ses enfants. C'est ce qu'on appelle le propriété min-heap. La racine contiendra la valeur minimale du tas.
  2. Max Heap - la clé du parent est supérieure ou égale à celle de ses enfants. C'est ce qu'on appelle le propriété max-heap. La racine contiendra la valeur maximale du tas.

UNE graphique consiste en un ensemble fini de sommets ou nœuds et un ensemble de bords reliant ces sommets.

le commande d'un graphique est le nombre de sommets dans le graphique. le Taille d'un graphique est le nombre d'arêtes dans le graphique.

Deux nœuds seraient adjacent s'ils sont reliés les uns aux autres par le même bord.

Graphes dirigés

Un graphique g est dit être un Graphique dirigé si toutes ses arêtes ont une direction indiquant quel est le sommet de départ et quel est le sommet de fin.

Nous disons que (u, v) est incident de ou feuilles sommet u et est incident à ou entre dans sommet v.

Auto-boucles: Bords d'un sommet à lui-même.

Graphes non dirigés

Un graphique g est dit être un graphique non orienté si tous ses bords n'ont pas de direction. Il peut aller dans les deux sens entre les deux sommets.

Si un sommet n'est connecté à aucun autre nœud du graphique, il est dit isolé.

Une feuille de triche pour les complexités temporelles des opérations de structure de données peut être trouvée ici.

J'espère que vous avez trouvé cet article utile comme une simple introduction aux structures de données. Je serais ravi d'entendre vos pensées. 😇

Merci beaucoup d'avoir lu. 😊

À votre santé! 😃

[1] Introduction to Algorithms, Third Edition Par Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein.

[2] Liste des structures de données de Wikipedia (https://en.wikipedia.org/wiki/List_of_data_structures)

Afficher plus

SupportIvy

SupportIvy.com : Un lieu pour partager le savoir et mieux comprendre le monde. Meilleure plate-forme de support gratuit pour vous, Documentation &Tutoriels par les experts.

Articles similaires

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Bouton retour en haut de la page
Fermer