Zunehmend bemerke ich, dass modernen Autodidakten wirklich Material fehlt. Jeder kennt Sprachen, aber kleine Grundlagen wie Datentypen oder Algorithmen. Ein bisschen über Datentypen.
Bereits 1976 schrieb der Schweizer Wissenschaftler
Nicklaus Wirth das Buch
Algorithmen + Datenstrukturen = Programme.Über 40 Jahre später ist diese Gleichung immer noch wahr. Und wenn Sie ein Autodidakt sind und den Artikel lange in der Programmierung durchgehen, können Sie diagonal. Sie können den Kaffee codieren.
Der Artikel enthält auch Fragen, die Sie im Interview hören können.
Was ist eine Datenstruktur?
Eine Datenstruktur ist ein Container, in dem Daten in einem bestimmten Layout gespeichert werden. Dieses „Layout“ ermöglicht es, dass die Datenstruktur in einigen Operationen effektiv und in anderen ineffektiv ist.
Welche gibt es?
Lineare Elemente bilden eine Sequenz oder eine lineare Liste. Das Umgehen von Knoten ist linear. Beispiele: Arrays. Verknüpfte Liste, Stapel und Warteschlangen.
Nicht linear , wenn die Umgehung von Knoten nicht linear ist und die Daten nicht sequentiell sind. Beispiel: Grafik und Bäume.
Grundlegende Datenstrukturen.
- Arrays
- Stapel
- Warteschlangen
- Verwandte Listen
- Zählt
- Bäume
- Präfixbäume
- Tabellen-Hash
Arrays
Ein Array ist die einfachste und am weitesten verbreitete Datenstruktur. Andere Datenstrukturen wie Stapel und Warteschlangen werden von Arrays abgeleitet.
Bild eines einfachen Arrays der Größe 4, das Elemente (1, 2, 3 und 4) enthält.
Jedem Datenelement wird ein positiver numerischer Wert (Index) zugewiesen, der der Position des Elements im Array entspricht. Die meisten Sprachen definieren den Startindex eines Arrays als 0.
Es gibt
Eindimensional , wie oben gezeigt.
Mehrdimensionale Arrays innerhalb von Arrays.
Grundlegende Operationen
- Einfügen - Fügt ein Element an einem bestimmten Index ein
- Get gibt ein Element an einem bestimmten Index zurück
- Löschen - Löschen Sie ein Element an einem bestimmten Index
- Größe - Ermittelt die Gesamtzahl der Elemente im Array
Fragen
- Suchen Sie das zweite minimale Array-Element
- Die ersten sich nicht wiederholenden Ganzzahlen in einem Array
- Führen Sie zwei sortierte Arrays zusammen
- Positive und negative Werte in einem Array neu anordnen
Stapel
Ein Stapel ist ein abstrakter Datentyp, bei dem es sich um eine Liste von Elementen handelt, die nach dem LIFO-Prinzip organisiert sind (last in - first out, last come - first out).
Dies sind keine Arrays. Dies ist die Wende.
Erfunden von Alan Thuring.Ein Beispiel für einen Stapel wäre ein Bündel vertikal angeordneter Bücher. Um das Buch zu erhalten, das sich irgendwo in der Mitte befindet, müssen Sie alle darauf platzierten Bücher löschen. So funktioniert die LIFO-Methode (Last In First Out). Die Funktion "Abbrechen" in Anwendungen funktioniert mit LIFO.
Das Stapelbild in drei Elementen (1, 2 und 3), wobei 3 oben steht und zuerst gelöscht wird.
Grundlegende Operationen
- Push fügt einen Gegenstand oben ein
- Pop-Gibt das oberste Element zurück, nachdem es vom Stapel entfernt wurde
- isEmpty-gibt true zurück, wenn der Stapel leer ist
- Top - Gibt das oberste Element zurück, ohne es vom Stapel zu löschen
Fragen
- Implementieren Sie eine Warteschlange mithilfe des Stapels
- Werte auf dem Stapel sortieren
- Implementieren von zwei Stapeln in einem Array
- Kehren Sie eine Zeichenfolge mit einem Stapel um
Warteschlangen
Wie bei Stapeln speichert eine Warteschlange ein Element nacheinander. Ein wesentlicher Unterschied zum Stapel ist die Verwendung von FIFO (First in First Out) anstelle von LIFO.
Ein Beispiel für eine Linie ist eine Linie von Personen. Letzterer hat den letzten genommen und du wirst, und der erste wird sie zuerst verlassen.
Das Bild der Warteschlange in vier Elementen (1, 2, 3 und 4), wobei 1 oben steht und zuerst gelöscht wird
Grundlegende Operationen
- Enqueue -) - fügt ein Element am Ende der Warteschlange ein
- Dequeue () - Entfernt ein Element vom Anfang der Warteschlange
- isEmpty () - gibt true zurück, wenn die Warteschlange leer ist
- Top () - gibt das erste Element der Warteschlange zurück
Fragen
- Implementieren Sie einen Stapel mithilfe einer Warteschlange
- Kehren Sie die ersten N Elemente einer Warteschlange um
- Generieren von Binärzahlen von 1 bis N mithilfe einer Warteschlange
Verknüpfte Liste
Eine verknüpfte Liste ist ein Array, in dem jedes Element ein separates Objekt ist und aus zwei Elementen besteht - Daten und einer Verknüpfung zum nächsten Knoten.
Der Hauptvorteil gegenüber dem Array ist die strukturelle Flexibilität: Die Reihenfolge der Elemente der verknüpften Liste stimmt möglicherweise nicht mit der Reihenfolge der Position der Datenelemente im Arbeitsspeicher des Computers überein, und die Reihenfolge der Durchquerung der Liste wird immer explizit durch ihre internen Beziehungen bestimmt.
Es gibt
Unidirektional speichert jeder Knoten die Adresse oder den Link zum nächsten Knoten in der Liste, und der letzte Knoten hat die nächste Adresse oder den nächsten Link als NULL.
1-> 2-> 3-> 4-> NULL
Bidirektional , zwei jedem Knoten zugeordnete Links, einer der Stärken zum nächsten Knoten und einer zum vorherigen Knoten.
NULL <-1 <-> 2 <-> 3-> NULL
Kreisförmig sind alle Knoten zu einem Kreis verbunden. Am Ende gibt es kein NULL. Eine zyklisch verknüpfte Liste kann eine einfach oder doppelt zyklisch verknüpfte Liste sein.
1-> 2-> 3-> 1
Die häufigste lineare unidirektionale Liste. Ein Beispiel ist ein Dateisystem.
Grundlegende Operationen
- InsertAtEnd - Fügen Sie das angegebene Element am Ende der Liste ein.
- InsertAtHead - Fügt ein Element an den Anfang der Liste ein
- Löschen - Entfernt das angegebene Element aus der Liste.
- DeleteAtHead - löscht das erste Element der Liste
- Suchen - Gibt das angegebene Element aus der Liste zurück
- isEmpty - gibt True zurück, wenn die verknüpfte Liste leer ist
Fragen
- Verknüpfte Liste umkehren
- Definieren einer Schleife in einer verknüpften Liste
- N Element vom Ende in der verknüpften Liste zurückgeben
- Entfernen Sie Duplikate aus einer verknüpften Liste
Zählt
Ein Graph ist eine Menge von Knoten (Eckpunkten), die in Form eines Netzwerks durch Kanten (Bögen) miteinander verbunden sind.
Es gibt
Orientiert sind die Rippen gerichtet, d.h. Es gibt nur eine verfügbare Richtung zwischen zwei verbundenen Eckpunkten.
Unorientiert können Sie zu jeder der Rippen in beide Richtungen gehen.
Gemischt
Gefunden in Formen wie
- Adjazenzmatrix
- Adjazenzliste
Allgemeine Graph-Traversal-Algorithmen
- Breitensuche - Crawlen auf Ebene
- Tiefensuche - Überqueren der Gipfel
Fragen
- Implementieren Sie die Suche in Breite und Tiefe
- Überprüfen Sie, ob das Diagramm ein Baum ist oder nicht
- Zählen Sie die Anzahl der Kanten in einem Diagramm
- Finden Sie den kürzesten Weg zwischen zwei Gipfeln
Bäume
Ein Baum ist eine hierarchische Datenstruktur, die aus Knoten (Eckpunkten) und Kanten (Bögen) besteht. Bäume sind im Wesentlichen verbundene Graphen ohne Schleifen.
Baumstrukturen überall. Jeder kennt den Fähigkeitsbaum in Spielen.
Einfacher Baum
Baumarten
Der Binärbaum ist der häufigste.
„Ein Binärbaum ist eine hierarchische Datenstruktur, in der jeder Knoten einen Wert hat (in diesem Fall ist er auch der Schlüssel) und auf die linken und rechten Nachkommen verweist. »- ProcsDrei Möglichkeiten, um einen Baum herumzukommen
- In direkter Reihenfolge (von oben nach unten) - das Präfixformular.
- In symmetrischer Reihenfolge (von links nach rechts) - Infixform.
- In umgekehrter Reihenfolge (von unten nach oben) - Postfix-Formular.
Fragen
- Finden Sie die Höhe eines Binärbaums
- Suchen Sie das N kleinste Element in einem binären Suchbaum
- Finden Sie Knoten in einem Abstand N von der Wurzel
- Finden Sie die Vorfahren des N-Knotens im Binärbaum
Trie (Präfixbaum)
Eine Art Baum für Strings, schnelle Suche. Wörterbücher T9
So speichert ein solcher Baum die Wörter "oben", "also" und "ihre".
Wörter werden von oben nach unten gespeichert, die grün gefärbten Knoten "p", "s" und "r" zeigen auf das Ende von "oben", "also" bzw. "ihre".
Fragen
- Zählen Sie die Gesamtzahl der Wörter
- Drucke alle Wörter
- Sortieren Sie Array-Elemente aus dem Präfixbaum
- Erstellen Sie ein T9-Wörterbuch
Tabellen-Hash
Hashing ist ein Prozess, mit dem Objekte eindeutig identifiziert und jedes Objekt in einem vorberechneten eindeutigen Index (Schlüssel) gespeichert wird.
Ein Objekt wird als Schlüssel-Wert-Paar gespeichert, und eine Sammlung solcher Elemente wird als Wörterbuch bezeichnet. Jedes Objekt kann mit diesem Schlüssel gefunden werden.
Im Wesentlichen ist dies ein Array, in dem der Schlüssel als Hash-Funktion dargestellt wird.
Die Hashing-Leistung hängt von ab
- Hash-Funktionen
- Hash-Tabellengröße
- Kollisionsmanagementmethoden
Ein Beispiel für Hash-Matching in einem Array. Der Index dieses Arrays wird über eine Hash-Funktion berechnet.
Fragen
- Finden Sie symmetrische Paare in einem Array
- Suchen Sie, ob ein Array eine Teilmenge eines anderen Arrays ist
- Beschreiben Sie offenes Hashing
Liste der Ressourcen
Anstelle einer Schlussfolgerung
Das Material ist so interessant wie die Sprachen selbst. Vielleicht sieht jemand die ihm vertrauten Grundstrukturen und ist interessiert.
Danke fürs Lesen. Ich hoffe keine Zeitverschwendung =)
PS: Ich entschuldige mich, wie sich herausstellte, war die Übersetzung des Artikels bereits hier und habe sie erst kürzlich übersehen.
Wenn sie interessiert ist,
hier ist sie , danke
Hokum , ich werde vorsichtiger sein.