Es gibt Datenstrukturen in JavaScript. Datenstrukturen beziehen sich auf eine Sammlung von Datenelementen, die eine oder mehrere spezifische Beziehungen zueinander haben. Datenstrukturen können Datenobjekte effektiv verwalten und die Rechenleistung verbessern. , Warteschlangen, verknüpfte Listen, Wörterbücher, Hashes, Diagramme und binäre Suchbäume.
Die Betriebsumgebung dieses Tutorials: Windows 10-System, JavaScript-Version 1.8.5, Dell G3-Computer.
Javascript verfügt über Datenstrukturen
Datenstrukturen: Liste, Stapel, Warteschlange, verknüpfte Liste, Wörterbuch, Hash, Diagramm und binärer Suchbaum
Liste
täglich Leben Im Leben verwenden Menschen oft Listen: To-Do-Listen, Einkaufslisten, Top-Ten-Listen usw. Computerprogramme verwenden auch Listen als Datenstrukturen unter folgenden Bedingungen:
Die Datenstruktur ist relativ einfach
Es besteht keine Notwendigkeit, Elemente in einer langen Reihenfolge zu finden oder zu sortieren
Und umgekehrt. Wenn die Datenstruktur sehr komplex ist, spielt die Liste keine so große Rolle.
Stapel
Ein Stapel ist eine besondere Art von Liste. Auf die Elemente im Stapel kann nur über ein Ende der Liste zugegriffen werden, das als oberstes Ende des Stapels bezeichnet wird. Stellen Sie sich vor, dass der Tellerstapel, den wir normalerweise in Restaurants sehen, ein Beispiel für einen gewöhnlichen Stapel in der realen Welt ist. Die Teller können nur von oben entnommen werden. Nachdem die Teller gespült wurden, können sie nur noch oben platziert werden. Der Stapel wird als Last-In-First-Out-Datenstruktur bezeichnet. Es handelt sich um eine effiziente Datenstruktur, da Daten nur oben im Stapel hinzugefügt oder gelöscht werden können, sodass solche Vorgänge schnell erfolgen.
Nutzungsbedingungen:
Solange die Datenspeicherung dem Last-In-First-Out- oder First-In-Last-Out-Prinzip entspricht, hat die Nutzung des Stacks Vorrang.
Queue
Queue ist Auch eine Art Liste. Der Unterschied besteht darin, dass die Warteschlange nur Elemente am Ende der Warteschlange einfügen und Elemente am Anfang löschen kann. Stellen Sie sich vor, wir stehen in der Schlange vor der Bank und die Leute vorne in der Schlange sind die ersten, die Geschäfte machen, während diejenigen, die von hinten kommen, hinten in der Schlange warten müssen, bis sie an der Reihe sind.
Nutzungsbedingungen:
Solange die Datenspeicherung dem First-In-First-Out-, Last-In-Last-Out-Prinzip entspricht, hat die Verwendung von Warteschlangen Vorrang.
Häufige Anwendungsszenarien:
Queue wird hauptsächlich verwendet An zeitbezogenen Orten, insbesondere in Betriebssystemen, ist die Warteschlange ein wichtiger Mechanismus zur Erzielung von Multitasking
Der Nachrichtenmechanismus kann über Warteschlangen implementiert werden, und die Prozessplanung wird ebenfalls über Warteschlangen implementiert
Verknüpfte Liste
Eine verknüpfte Liste ist auch eine Art Liste. Warum benötigen wir eine verknüpfte Liste und ein Array in JavaScript? Das Hauptproblem besteht darin, dass sie als Objekte implementiert werden, was im Vergleich zu Arrays in anderen Sprachen (z. B. C++) sehr ineffizient ist und Java). Wenn Sie feststellen, dass Arrays in der tatsächlichen Verwendung langsam sind, sollten Sie stattdessen die Verwendung einer verknüpften Liste in Betracht ziehen.
Nutzungsbedingungen:
Verknüpfte Listen können in fast jeder Situation verwendet werden, in der ein eindimensionales Array verwendet werden kann. Wenn wahlfreier Zugriff erforderlich ist, sind Arrays immer noch die bessere Wahl.
Wörterbuch
Ein Wörterbuch ist eine Datenstruktur, die Daten in Schlüssel-Wert-Paaren speichert. Die Object-Klasse in JavaScript ist in Form eines Wörterbuchs konzipiert. Durch die Implementierung der Wörterbuchklasse kann JavaScript die Verwendung dieses Wörterbuchtyps vereinfachen. Das Wörterbuch kann die allgemeinen Funktionen des Objekts implementieren und die gewünschten Funktionen entsprechend erweitern. Objekte können überall im JavaScript-Schreiben angezeigt werden auch äußerst offensichtlich.
Hash
Hash (auch Hash-Tabelle genannt) ist eine häufig verwendete Array-Speichertechnologie. Das Hash-Array kann schnell eingefügt oder abgerufen werden. Die zum Hashing verwendete Datenstruktur wird als Hash-Tabelle bezeichnet. Das Einfügen, Löschen und Abrufen von Daten in einer Hash-Tabelle geht sehr schnell, ist jedoch für Suchvorgänge, wie zum Beispiel das Finden der Maximal- und Minimalwerte in einem Array, ineffizient. Diese Operationen erfordern den Rückgriff auf andere Datenstrukturen, beispielsweise den unten beschriebenen binären Suchbaum.
Hash-Tabellen können basierend auf Arrays in JavaScript entworfen werden. Die Länge des Arrays ist voreingestellt und alle Elemente werden entsprechend den den Elementen entsprechenden Schlüsseln an bestimmten Stellen im Array gespeichert. Die Schlüssel hier und die Schlüssel des Objekts sind Typkonzepte. Wenn Sie eine Hash-Tabelle zum Speichern eines Arrays verwenden, wird eine Hash-Funktion verwendet, um den Schlüssel einer Zahl zuzuordnen, die von 0 bis zur Länge der Hash-Tabelle reicht.
Auch wenn eine effiziente Hash-Funktion verwendet wird, ist es immer noch möglich, dass zwei Schlüssel demselben Wert zugeordnet werden. Dieses Phänomen wird als Kollision bezeichnet. Zu den gängigen Kollisionsverarbeitungsmethoden gehören: Open-Chain-Methode und lineare Erkennungsmethode (wenn Sie sich für die spezifischen Konzepte interessieren, können Sie sich sicher online darüber informieren)
Nutzungsbedingungen:
Kann zum Einfügen, Löschen und Abrufen von Daten verwendet werden. nicht zum Auffinden von Daten geeignet
Bild
Ein Diagramm besteht aus einer Reihe von Kanten und einer Reihe von Eckpunkten. Karten sind weit verbreitete reale Szenen um uns herum. Beispielsweise sind alle zwei Städte durch eine Art Straße verbunden. Jede der oben genannten Städte kann als Scheitelpunkt betrachtet werden, und die Straßen, die die Städte verbinden, sind Kanten. Eine Kante wird durch ein Paar Scheitelpunkte (v1, v2) definiert, wobei v1 und v2 die beiden Scheitelpunkte im Diagramm sind. Scheitelpunkte haben auch Gewichte und werden zu Kosten. Wenn die Scheitelpunktpaare eines Graphen geordnet sind, spricht man von einem gerichteten Graphen (z. B. einem allgemeinen Flussdiagramm), andernfalls spricht man von einem ungeordneten Graphen.
Verwendungsszenario (Verwenden Sie Diagramme, um reale Systeme zu modellieren):
Verkehrssystem, Scheitelpunkte können zur Darstellung von Straßenkreuzungen und Kanten zur Darstellung von Straßen verwendet werden. Gewichtete Kanten können Geschwindigkeitsbegrenzungen oder die Anzahl der Fahrspuren darstellen. Mit dem System lassen sich die besten Routen ermitteln und ermitteln, auf welchen Straßen es am wahrscheinlichsten zu Staus kommt.
Jedes Transportsystem kann mithilfe von Diagrammen modelliert werden. Beispielsweise können Fluggesellschaften Diagramme zur Modellierung ihrer Flugsysteme verwenden. Betrachten Sie jeden Flughafen als einen Scheitelpunkt und jede Route, die durch zwei Scheitelpunkte verläuft, als eine Kante. Gewichtete Kanten können die Kosten eines Fluges von einem Flughafen zum anderen oder die Entfernung zwischen zwei Flughäfen darstellen, je nachdem, was modelliert wird.
Es gibt zwei Hauptalgorithmen zum Durchsuchen von Diagrammen: Tiefensuche und Breitensuche.
Binärbaum und binärer Suchbaum
Baum ist eine Datenstruktur, die häufig in der Informatik verwendet wird. Ein Baum ist eine nichtlineare Datenstruktur, die Daten hierarchisch speichert.
Jeder Knoten in einem Binärbaum darf nicht mehr als zwei untergeordnete Knoten haben. Die beiden untergeordneten Knoten eines übergeordneten Knotens werden als linker Knoten bzw. rechter Knoten bezeichnet. Durch die Begrenzung der Anzahl der untergeordneten Knoten auf 2 können effiziente Programme geschrieben werden, um Daten in den Baum einzufügen, zu suchen und zu löschen.
Binärer Suchbaum (BST) ist ein spezieller Binärbaum, bei dem relativ kleine Werte im linken Knoten und größere Werte im rechten Knoten gespeichert werden. Diese Funktion macht die Suche sowohl nach numerischen als auch nach nicht numerischen Daten wie Wörtern und Zeichenfolgen sehr effizient.
Implementierungsmethode für den binären Suchbaum
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;
}
}
}
}
}Es gibt drei Möglichkeiten, BST zu durchlaufen: Durchlauf in der richtigen Reihenfolge (Besuchen Sie alle Knoten im Baum in aufsteigender Reihenfolge, besuchen Sie zuerst den linken Knoten, dann den Wurzelknoten und schließlich den rechten Knoten Knoten), Durchquerung vor der Bestellung (Besuchen Sie zuerst den Wurzelknoten und greifen Sie dann auf die gleiche Weise auf den linken und rechten Knoten zu), Durchquerung nach der Bestellung (besuchen Sie zuerst die Blattknoten, vom linken Teilbaum zum rechten Teilbaum und dann zum Wurzelknoten)
[Verwandte Empfehlungen: Javascript-Video-Tutorial, Web-Frontend】
Das obige ist der detaillierte Inhalt vonHat Javascript Datenstrukturen?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
