Javascript a-t-il des structures de données ?

Il existe des structures de données en JavaScript. Les structures de données font référence à un ensemble d'éléments de données qui ont une ou plusieurs relations spécifiques les uns avec les autres. Les structures de données peuvent gérer efficacement les objets de données et améliorer les performances informatiques. , files d'attente, listes chaînées, dictionnaires, hachages, graphiques et arbres de recherche binaires.

L'environnement d'exploitation de ce tutoriel : système Windows 10, JavaScript version 1.8.5, ordinateur Dell G3.

Javascript a-t-il des structures de données ?

Javascript a des structures de données

Structures de données : liste, pile, file d'attente, liste chaînée, dictionnaire, hachage, graphique et arbre de recherche binaire

liste

quotidiennement la vie Dans la vie, les gens utilisent souvent des listes : listes de choses à faire, listes de courses, listes des dix meilleurs, etc. Les programmes informatiques utilisent également des listes. Les listes de sélection sont particulièrement utiles en tant que structures de données dans les conditions suivantes :

La structure des données est relativement simple

Il n'est pas nécessaire de rechercher des éléments dans une longue séquence, ou de les trier

Et vice versa, si la structure des données est très complexe, le rôle de la liste n'est pas si important.

Stack

Une pile est un type spécial de liste. Les éléments de la pile ne sont accessibles que par une extrémité de la liste, appelée le haut de la pile. Imaginez que la pile d'assiettes que nous voyons habituellement dans les restaurants est un exemple d'une pile courante dans le monde réel. Les assiettes ne peuvent être prises que par le haut. Une fois lavées, elles ne peuvent être placées que sur le dessus. La pile est connue sous le nom de structure de données dernier entré, premier sorti. Il s'agit d'une structure de données efficace car les données ne peuvent être ajoutées ou supprimées qu'en haut de la pile, ces opérations sont donc rapides.

Conditions d'utilisation :

Tant que le stockage des données répond au principe du dernier entré, premier sorti ou premier entré-dernier sorti, la priorité est donnée à l'utilisation de la stack

Queue

La file d'attente est C'est aussi une sorte de liste, la différence est que la file d'attente ne peut contenir que des éléments d'insertion à la fin de la file d'attente et des éléments de suppression au début. Imaginez que nous faisons la queue à la banque et que les gens en première ligne sont les premiers à faire des affaires, tandis que ceux qui viennent derrière doivent attendre au fond de la file jusqu'à ce que ce soit leur tour.

Conditions d'utilisation :

Tant que le stockage des données respecte le principe du premier entré, premier sorti, dernier entré, dernier sorti, la priorité est donnée à l'utilisation des files d'attente

Scénarios d'application courants :

La file d'attente est principalement utilisée dans les endroits liés au temps, en particulier dans les systèmes d'exploitation , la file d'attente est un mécanisme important pour réaliser plusieurs tâches

Le mécanisme de message peut être implémenté via la file d'attente, et la planification du processus est également implémentée à l'aide de la file d'attente

Liste chaînée

La liste chaînée est aussi une sorte de liste, pourquoi y a-t-il besoin d'une liste chaînée et d'un tableau en JavaScript Le principal problème est qu'ils sont implémentés en tant qu'objets, ce qui est très inefficace par rapport aux tableaux dans d'autres langages ​​(comme C++ et Java). Si vous constatez que les tableaux sont lents dans l'utilisation réelle, envisagez plutôt d'utiliser une liste chaînée.

Conditions d'utilisation :

Les listes chaînées peuvent être utilisées dans presque toutes les situations où un tableau unidimensionnel peut être utilisé. Si un accès aléatoire est requis, les tableaux restent un meilleur choix.

Dictionary

Un dictionnaire est une structure de données qui stocke les données dans des paires clé-valeur. La classe Object en JavaScript est conçue sous la forme d'un dictionnaire. JavaScript peut rendre cet objet de type dictionnaire plus facile à utiliser en implémentant la classe dictionnaire. Le dictionnaire peut réaliser les fonctions communes de l'objet et étendre les fonctions souhaitées en conséquence. Les objets peuvent être vus partout dans l'écriture JavaScript, donc le rôle du dictionnaire est. aussi extrêmement évident.

Hash

Le hachage (également appelé table de hachage) est une technologie de stockage de tableau couramment utilisée. Le tableau haché peut être rapidement inséré ou récupéré. La structure de données utilisée pour le hachage est appelée table de hachage. L'insertion, la suppression et la récupération de données sur une table de hachage sont très rapides, mais elles sont inefficaces pour les opérations de recherche, telles que la recherche des valeurs maximales et minimales dans un tableau. Ces opérations nécessitent de recourir à d'autres structures de données, comme l'arbre de recherche binaire décrit ci-dessous.

Les tables de hachage peuvent être conçues sur la base de tableaux en JavaScript. La longueur du tableau est prédéfinie, et tous les éléments sont stockés à des emplacements spécifiques du tableau en fonction des clés correspondant aux éléments. Les clés ici et les clés de l'objet sont des concepts de type. Lorsque vous utilisez une table de hachage pour stocker un tableau, une fonction de hachage mappe la clé à un nombre compris entre 0 et la longueur de la table de hachage.

Même si une fonction de hachage efficace est utilisée, il est toujours possible que deux clés soient mappées à la même valeur. Ce phénomène est appelé collision. Les méthodes courantes de traitement des collisions comprennent : la méthode de chaîne ouverte et la méthode de détection linéaire (si vous êtes intéressé par des concepts spécifiques, vous pouvez les découvrir en toute confiance en ligne)

Conditions d'utilisation :

Peut être utilisé pour insérer, supprimer et récupérer des données, ne convient pas pour trouver des données

Image

Un graphe est composé d'un ensemble d'arêtes et d'un ensemble de sommets. Les cartes sont des scènes réelles très courantes autour de nous. Par exemple, toutes les deux villes sont reliées par une sorte de route. Chaque ville située au-dessus peut être considérée comme un sommet, et les routes reliant les villes sont des limites. Une arête est définie par une paire de sommets (v1, v2), où v1 et v2 sont les deux sommets du graphe. Les sommets ont également des poids et deviennent des coûts. Si les paires de sommets d'un graphe sont ordonnées, on parle de graphe orienté (comme un organigramme commun), sinon on parle de graphe non ordonné.

Scénario d'utilisation (utiliser des graphiques pour modéliser des systèmes réels) :

Système de circulation, les sommets peuvent être utilisés pour représenter les intersections de rues et les arêtes peuvent être utilisées pour représenter les rues. Les bords pondérés peuvent représenter les limites de vitesse ou le nombre de voies. Le système peut être utilisé pour déterminer les meilleurs itinéraires et quelles rues sont les plus susceptibles d'être embouteillées.

Tout système de transport peut être modélisé à l'aide de graphiques. Par exemple, les compagnies aériennes peuvent utiliser des diagrammes pour modéliser leurs systèmes de vol. Considérons chaque aéroport comme un sommet et chaque route passant par deux sommets comme une arête. Les bords pondérés peuvent représenter le coût d’un vol d’un aéroport à un autre, ou la distance entre deux aéroports, selon ce qui est modélisé.

Il existe deux algorithmes principaux pour rechercher des graphiques : la recherche en profondeur d'abord et la recherche en largeur d'abord.

Arbre binaire et arbre de recherche binaire

L'arbre est une structure de données souvent utilisée en informatique. Un arbre est une structure de données non linéaire qui stocke les données de manière hiérarchique.

Chaque nœud d'un arbre binaire ne peut pas avoir plus de deux nœuds enfants. Les deux nœuds enfants d'un nœud parent sont appelés respectivement nœud gauche et nœud droit. En limitant le nombre de nœuds enfants à 2, des programmes efficaces peuvent être écrits pour insérer, rechercher et supprimer des données dans l'arborescence.

L'arbre de recherche binaire (BST) est un arbre binaire spécial dans lequel des valeurs relativement petites sont stockées dans le nœud de gauche et des valeurs plus grandes sont stockées dans le nœud de droite. Cette fonctionnalité rend les recherches très efficaces, tant pour les données numériques que non numériques, telles que les mots et les chaînes.

Méthode d'implémentation de l'arbre de recherche binaire

function Node(data, left, right) { // 创建节点
  this.data = data;
  this.left = left;
  this.right = right;
  this.show = show
}
function show () { // 显示树的数据
  return this.data
}
function BST () { // 二叉查找树类
  this.root = null;
  this.insert = insert;
  this.inOrder = inOrder; // inOrder是遍历BST的方式
}
function insert (data) { // 向树中插入数据
  var n = new Node(data, null, null)
  if (this.root == null) {
    this.root = n;
  } else {
    var current = this.root;
    var parent;
    while (true) {
  parent = current
  if (data < current.data) {
current = current.left;
if (current == null) {
  parent.left = n;
  break;
}
  } else {
current = current.right;
if (current == null) {
  parent.right = n;
  break;
}
  }
    }
  }
}

Il existe trois façons de parcourir BST : traversée dans l'ordre (visitez tous les nœuds de l'arborescence par ordre croissant, visitez d'abord le nœud de gauche, puis visitez le nœud racine et enfin visitez le nœud de droite nœud), parcours de pré-commande (visitez d'abord le nœud racine, puis accédez au nœud gauche et au nœud droit de la même manière), parcours de post-commande (visitez d'abord les nœuds feuilles, du sous-arbre gauche au sous-arbre droit, puis au nœud racine)

[Recommandations associées : Tutoriel vidéo javascript, front-end web】

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!