Nur über Listen, Wörterbücher und Mengen oder TOP 5 Datenstrukturen



    Hallo. Für sie! Sag nicht „Verdammt! Ich weiß, wie sich die Liste vom Vektor unterscheidet, ich brauche diesen Artikel nicht. “ Bitte werfen Sie einen Blick unter die Katze und aktualisieren Sie Ihr Wissen. Ich hoffe jedoch, dass Sie aus diesem Artikel viel mehr lernen können, und einige werden möglicherweise endlich herausfinden, warum es so viele Datentypen für Objektsammlungen gibt.

    Einleitung


    Es kam vor, dass es beim Programmieren einer Sammlung sehr viele verschiedene Entitäten gibt - Listen, Arrays, Vektoren, Mengen, Stapel, Warteschlangen, assoziative Arrays und die meisten dieser Datenstrukturen weisen mehrere weitere Unterarten auf.

    Es muss Gründe für so viele verschiedene Variationen für eine einfache Darstellung einer Sammlung von Objekten geben.

    Sollte es Unterschiede zwischen einer Liste und einem Array geben? Zwischen assoziativem Array und Hash-Tabelle?

    Sammlung


    Zunächst - das Langweiligste (ja, ich liebe das). Was ist eine Sammlung im Allgemeinen?

    Eine Sammlung ist eine Datenstruktur (Typ, Klasse, besser gesagt Schnittstelle), die so erstellt wurde, dass sie eine bestimmte Anzahl von Objekten enthält (je nach Sprache und Terminologie müssen sie vom selben Typ sein oder können von unterschiedlichem Typ sein).

    Verschiedene Arten von Sammlungen können statisch oder dynamisch sein, d. H. ihre Größe ändern oder konstant bleiben, können geordnet (genauer unter Berücksichtigung der Reihenfolge der Elemente) und ungeordnet (bzw. nicht berücksichtigt) werden.

    Für Sammlungen werden verschiedene Standardoperationen bereitgestellt (jetzt werden wir uns mit veränderlichen, d. H. Veränderlichen Sammlungen befassen), wie z.

    Okay, ich habe meine geheime Pflicht erfüllt, jetzt lass uns gehen!

    1 Vektor (Vektor, Array)



    Worauf hast du gewartet?

    Ein Vektor (auch bekannt als eindimensionales Array) ist eine geordnete Menge von Elementen mit wahlfreiem Zugriff über einen numerischen Index. Was ist uns bei dieser Definition wichtig? Nichts. Tatsächlich ist uns nur ein Scherz wichtig, fast jedes Wort: Auf

    Elemente wird über einen numerischen Index zugegriffen (normalerweise ab dem 0. Index, obwohl es Ausnahmen gibt), der Zugriff auf ein Auflistungselement über einen Index wird normalerweise als myFavoriteCats [i] oder blackKitties [5 geschrieben ]. Um genau diese Zahl - den Index - anzuzeigen, wird außerdem der Buchstabe i verwendet.

    Und wenn ein Buchstabe fehlt, werden hier j und k gezogen.

    Des Weiteren verstehen wir, dass der Zugriff willkürlich ist - das heißt, wir können auf Elemente unter den Indizes 0, 42, 2014 zugreifen und im Allgemeinen erwarten, dass die Operation die Komplexität O (1) aufweist, d. H. konstant und unabhängig von dem von uns gewünschten Element wird er sofort mit Lichtgeschwindigkeit zu uns zurückkehren.

    Als nächstes - ein Vektor - eine geordnete Sammlung, die verständlich ist - haben wir Konzepte wie das erste, letzte Element, für jedes bestimmte Element können wir auch das vorherige und das nächste benennen.

    Freigabe


    Typischerweise ist ein Vektor (als Struktur auf niedriger Ebene) ein Deskriptor, der verschiedene Informationen enthält, die nicht von der Struktur selbst zu trennen sind (es ist am sinnvollsten, nur die Größe des Vektors dort beizubehalten) und einen Zeiger auf das erste Element.

    Eine solche Implementierung ermöglicht den Zugriff auf ein beliebiges Element eines Vektors durch seinen Index in konstanter Zeit und ermöglicht auch das Kopieren, Verketten und andere einfache Operationen auf einer niedrigen Ebene.

    In der Tat ist der Zugriff auf ein bestimmtes Element sehr einfach - fügen Sie dem Zeiger einen Index zum ersten Element hinzu (mit einigen Anpassungen für die Größe des Datentyps) und rufen Sie einen Zeiger zum gewünschten Element ab! Es bleibt dereferenziert und wir haben das richtige Kätzchen in der Variablen!

    Nun, der Vektor ist eine coole Struktur, aber er hat auch Fehler (und wer hat sie nicht?!). Sie können beispielsweise nicht einfach ein neues Element nehmen und dem Vektor hinzufügen! Besonders in der Mitte drücken. Es ist auch unmöglich zu sagen, dass wir Katzen mit den Nummern 0, 1 und 4 haben, aber nicht mit den Nummern 2 und 3 (das war früher so, aber es stellte sich heraus, dass es Hunde waren).

    Sie können sich den Vektor als ein Bücherregal mit Fächern vorstellen, von denen jedes genau ein Buch enthält. Um Dontsovas neuen Roman zwischen dem 10. und 11. Band der Großen Sowjetskaja-Enzyklopädie zu verschieben, müssen Sie sich bemühen, alle Bände vom 11. auf den 65. Band zu verschieben (Sie können schummeln und den 11. Band am Ende einfügen, aber ich weiß nicht sagte, und in diesem Fall werden wir die Ordnung verlieren).


    In meiner Erinnerung ist alles genau das

    Bewerbung


    In unserem Fall wäre der Vektor perfekt für die 10 süßesten Kätzchen, weil Sie müssen keine Elemente hinzufügen oder entfernen (nur ändern), es sollten keine Lücken zwischen dem ersten und fünften Platz bestehen, und es ist bequem, eine Kontaktaufnahme über die Nummer vorzunehmen.

    Ok In jedem Fall ist der Vektor cool, wir werden nur sehen, welche anderen Sammlungen es gibt.

    2 Liste



    Band Eins

    Wow! Die Liste der Aufgaben für heute, die Liste der Einkäufe im Laden. Die Liste der Gäste für die Hochzeit ... Komm auf den Punkt.

    Wir wissen bereits, dass die Elemente des Vektors sauber, schön und gleichmäßig hintereinander liegen. Dies gibt uns sowohl Vor- als auch Nachteile.

    Die Liste in dieser Hinsicht ist genau das Gegenteil - ihre Elemente können nach Belieben aus dem Gedächtnis gestreut werden! Aus diesem Grund verlieren wir die Fähigkeit, schnell einen Eintrag nach Index zu erhalten, und wir können auch nicht schnell die gesamte Liste kopieren, aber wir bekommen eine nette Sache - wir können Elemente an jedem Ort in einer konstanten Zeit einfügen! Gerüchten zufolge werden Elemente aus der Liste auch für O (1) gelöscht.

    Implementierung


    Hm. Was ist mit der formalen Definition?

    Eine Liste ist eine geordnete Menge von Elementen, für die jeweils ein Zeiger auf das nächste (oder auf eine doppelt verknüpfte Liste sowie auf das nächste und vorherige) Listenelement gespeichert ist.

    Für das letzte Element der Liste speichern wir einen Nullzeiger (in den Diagrammen verwende ich einen Zeiger auf eine Nullkatze (Nullkatze), werde nicht alarmiert).

    Achtung! Bei der kanonischen Implementierung der Liste ist es erforderlich, die gesamte Liste zu durchlaufen, um die Größe der Liste zu ermitteln. Dabei muss der Nullzeiger erreicht werden (lineare Zeit ist O (n) -Komplexität), und obwohl bei einigen Implementierungen die Größe im Listendeskriptor (oder im ersten Element) zwischengespeichert wird. es lohnt sich, sich darauf zu verlassen.


    Wenn ich könnte, würde ich ein Element der Liste am Nordpol platzieren und das andere irgendwo in der Nähe von Betelgeuse

    Bewerbung


    Die Liste wäre geeignet für (Achtung!) Eine Liste obdachloser Kätzchen, sortiert nach Alter (aufsteigend). Wir müssen nur häufig Elemente zur Liste hinzufügen und daraus entfernen (Sie denken nicht an etwas Ähnliches - Kätzchen werden weggenommen), und häufiger benötigen Sie die ersten Elemente der Liste. Ich nehme mir ein kleines flauschiges Kätzchen und kein 8-jähriges Manul.

    Ok Listen sind eine einfache Struktur. Was gibt es sonst noch?

    3 Setzen



    This Seth.

    In der Mathematik gibt es ein ähnliches Konzept, genauer gesagt in der Mengenlehre. Vieles unterscheidet sich sowohl vom Vektor als auch von der Liste, obwohl ihre Implementierung möglicherweise ähnlich ist.

    Viel ist eine ungeordnete Menge von Elementen, ohne Wiederholungen. Wow Und alle? Kein wahlfreier Zugriff für Sie, nichts! Warum ist das nötig?

    Wie wir in einem Vektor wissen, können Sie ein Element schnell über einen Index abrufen. In der Liste können Sie ein Element schnell hinzufügen oder entfernen, aber wie steht es mit einer Menge?

    Im Set können Sie schnell prüfen, ob sich darin ein Element befindet oder nicht. Wenn ich herausfinden wollte, ob eine bestimmte Katze auf meiner Favoritenliste steht, müsste ich für die Liste und den Vektor (im schlimmsten Fall) alle Elemente durchgehen!

    Implementierung


    Im Set, weil Ist dies ungeordnet, können Sie die Elemente beim Hinzufügen sortieren und in diesem Fall eine binäre Suche durchführen. Hm. Dies ist ein Paradox, die Sammlung ist ungeordnet, aber im Inneren wird alles in Ordnung sein. Es ist wichtig zu verstehen, dass, wenn Sie dem Set ein neues Element hinzufügen, dieses nicht enden wird.

    Tatsächlich können Sie sich bei der Arbeit mit einer Menge überhaupt nicht auf eine Reihenfolge von Elementen verlassen, sondern auf eine beliebige - daher eine Menge und eine ungeordnete Sammlung.

    Es ist erwähnenswert, dass viele auf viele verschiedene Arten implementiert werden können, zum Beispiel kann Hashing verwendet werden, um noch schneller nach Elementen zu suchen, sodass ich die Implementierung nicht im Detail betrachten werde. Ich kann nur sagen, dass Sie betrügen und unser Wissen auf Listen anwenden können.

    Im Allgemeinen gibt es immer noch geordnete Mengen, Mengen mit Wiederholungen (Multiset), und wahrscheinlich sollte es eine geordnete Multiset geben.


    Die Mengenlehre ist einfacher, wenn Sie viele Kätzchen nehmen

    Bewerbung


    Viele sind ideal für eine Liste von Lieblingskätzchen, weil es viele gibt. Ha! Nur ein Scherz.

    Aber es funktioniert wirklich, da eine solche Sammlung nicht sortiert werden muss (Reihenfolge ist nicht wichtig) und wir leicht überprüfen können, ob eine bestimmte Katze in diesem Set ist (sagen wir, ich habe 100 Kätzchen und meine Lieblingskätzchen füttere ich mit Garnelen).

    Okay. Viele sind auch gut, aber gibt es wirklich etwas anderes?

    4 Wörterbuch (Assoziatives Array, Karte, Wörterbuch)



    Zugegeben, dies ist besser als nur ein Wörterbuch: Ein

    Wörterbuch (auch als assoziatives Array bezeichnet) ist derselbe Vektor, jedoch mit geringfügigen Unterschieden. Der Index (der im Wörterbuch als Schlüssel bezeichnet wird) kann nicht nur Zahlen, sondern auch beliebige andere Datentypen (auch andere Sammlungen!) Enthalten. Lücken sind auch akzeptabel, wenn wir immer noch eine Ganzzahl als Schlüssel verwenden, z. B. ein Element mit dem Schlüssel 5 verknüpft haben, aber gleichzeitig möglicherweise kein Element mit dem Schlüssel 4 verknüpft ist.

    Was bedeutet dies alles in der Praxis? Es ist nur so, dass wir in eckigen Klammern, um ein Element durch "Index" anzuzeigen, einen beliebigen Typ angeben können, z. B. allMyCats ["Murka"].

    Implementierung


    Unbewaffnet ist zu erkennen, dass Sie einfach ein Array (oder eine Liste) von Paaren (Schlüssel, Wert) erstellen und eine spezielle Funktion hinzufügen können, die diese Liste durchläuft und einen bestimmten Wert mit dem dazugehörigen Schlüssel zurückgibt.

    Wir können auch nicht sagen, welches Paar das erste, welches das letzte ist und was früher „Murka“ oder „Borka“ war, daher wird das Wörterbuch als ungeordnete Struktur angesehen.

    Auch hier kann jedem Schlüssel nur ein Wert zugeordnet werden, daher ist für das angegebene Beispiel mit den Namen der Katzen das Wörterbuch in seiner reinen Form schlecht geeignet.

    Die Implementierung kann, wie im Fall der Menge, völlig unterschiedlich sein. Sie können die Paare nach Schlüssel sortieren und die Binärsuche verwenden, um das Element zu erhalten (in diesem Fall müssen die Elemente sortierbar sein). Auch hier können Sie ein Wörterbuch mithilfe von Key-Hashing implementieren, das häufig mit Zeichenfolgen verwendet wird.

    Bewerbung


    Am plausibelsten und kompetentesten ist es, das Wörterbuch zusammen mit der Liste zu verwenden, wobei der Wörterbuchschlüssel die Zeichenfolge ist - der Name der Katze und der Wert die Liste der Katzen mit diesem Namen. So finden Sie schnell alle Katzen mit dem Namen Murka und können aus ihnen die auswählen, die gerade benötigt wird.


    So sieht std :: map im Speicher aus>

    Und ich habe Neuigkeiten für Sie - die Arten von Sammlungen sind vorbei. Nun, das ist es. Im Allgemeinen nicht mehr. Absolut.

    5 Stapel



    Eine andere Katze und wird Stack Overflow

    Ha sein! Ich habe dich angelogen (im Scherz gedacht)! Es gibt einige weitere Datenstrukturen, die Sammlungen darstellen.

    Der Stapel ist also eine Sammlung mit ungewöhnlichem Zugriff bzw. ungewöhnlichen Regeln für das Hinzufügen und Entfernen von Elementen.

    Alles ist einfach - das hinzugefügte Element mit dem Namen "last", das erste wird vom Stapel gelöscht.

    Der Stack ist sehr notwendig und nützlich beim Programmieren. Mit dem Stack wird beispielsweise ein verschachtelter Prozeduraufruf ausgeführt - die Rücksprungadresse und die Argumente der aufgerufenen Funktion werden auf dem Stack gespeichert.

    Implementierung


    Bei einer Implementierung auf hoher Ebene ist nichts besonders interessant - ein Zeiger auf eine Liste und Elemente werden am Anfang dieser Liste hinzugefügt und daraus entfernt.

    In der Low-Level-Implementierung (genauer gesagt, wie sie in modernen Architekturen implementiert ist) gibt es interessante Punkte.

    Der Stapel dort ist ein kleiner reservierter Teil des Speichers, und zwei Zeiger werden damit gespeichert - zum Anfang des Stapels (wo sich das erste hinzugefügte Element befindet) und zum Ende des Stapels - wo sich das zuletzt hinzugefügte befindet.

    Wenn Sie zu viele Daten auf den Stapel legen, wird das Programm mit dem bekannten Fehler "Stapelüberlauf" beendet. Dies bedeutet, dass der Zeiger auf das Ende des Stapels die zulässige Obergrenze überschritten hat.

    Die umgekehrte Situation kann auch eintreten (Stapelüberlauf), wenn Sie versuchen, mehr vom Stapel aufzunehmen, als er enthält, dies jedoch nicht in höheren Sprachen geschieht (es ist verständlich, warum wir nicht direkt mit dem Stapel arbeiten dürfen).

    Wenn jemand daran interessiert ist, wie das alles funktioniert, kann es hilfreich sein, die Assemblersprache für eine gängige Architektur wie i386 zu lernen.

    Bewerbung


    Es wäre möglich, an dieser Stelle einen Stapel armer Kätzchen in der Höhe eines Berges zu beschreiben, aber in höheren Sprachen wird ein Stapel selten benötigt. Oft gibt es genug Rekursionen, die den Stapel implizit verwenden. Ich habe kein weit hergeholtes Beispiel angewendet (und konnte leider kein normales finden), also fahren wir mit dem nächsten Punkt fort.

    Verschiedenes


    Tatsächlich gibt es immer noch eine Reihe von Sammlungen, z. B. eine Warteschlange, eine Zweiwege-Warteschlange (Dec), eine doppelt verknüpfte Liste, einen Ringsatz und Prioritätswarteschlangen.

    Es gibt Bäume (ja ihren ganzen Wald!) Und Grafiken.

    Es gibt probabilistische Datenstrukturen, z. B. eine Wahrscheinlichkeitsmenge und eine Überspringliste.

    Ich möchte wirklich darüber schreiben, aber Zeit und Platz auf dem Hub sind nicht immer klein.

    Es gibt jedoch viele (oder vektorielle) Dinge in Bezug auf das Thema, die ich zumindest nebenbei erwähnen möchte, aber ein neugieriger Leser bittet mich, ein intelligentes Buch zu lesen.

    Linien


    Zuallererst mag es seltsam erscheinen, wie Zeichenfolgen in einigen Sprachen implementiert werden. Die einfachste und effektivste Lösung ist wahrscheinlich die C-Lösung - eine Zeichenfolge ist eine Zeichenfolge mit einem Null-Zeichen am Ende, sodass Sie auf einen Deskriptor verzichten können.

    In C ++ ähnelt std :: string eher einem Vektor.

    Nun, im alten Pascal ist der Deskriptor (genauer gesagt, nur die Länge) im Null-Element des Arrays gespeichert.

    In Haskell ist ein String eine Liste von Zeichen ([Char]), was bedeutet, dass das Abrufen der Länge eines Strings eine O (n) -Komplexität hat. Aber sie sind sehr praktisch, um rekursiv herumzulaufen.

    Im Allgemeinen ist eine Zeichenfolge eine geordnete Menge von Zeichen und nicht mehr. Welche Art von Sammlung verwendet wird, ist nicht wichtig (naja, ich würde nicht empfehlen, viel zu verwenden, ha!).

    Warteschlange


    Eine Warteschlange ist einem Stapel sehr ähnlich und ist gleichzeitig das Gegenteil davon - das erste, was wir zurückerhalten, ist nicht das Element, das wir zuletzt hinzugefügt haben, sondern dasjenige, das am längsten in der Warteschlange steht. Die Warteschlange ist eine sehr praktische Struktur, aber trotz der Tatsache, dass ihr Funktionsprinzip dem Stapel ähnelt, gibt es einen kleinen Unterschied in der effektiven Implementierung.

    Für den Stapel konnten wir ein Stück Speicher, dessen Größe akzeptabel war, schummeln und zuweisen. In diesem Fall konnte er erweitert werden, da der Stapel abnimmt und zunimmt, weil Elemente werden „an einem Ende“ hinzugefügt und entfernt. Wenn wir uns die Arbeit der Warteschlange vorstellen, schleicht sie sich in den Speicher ein - der Anfang verschiebt sich ständig nach oben, sodass der für den Stapel geltende Trick schlechter funktioniert und es viel besser ist, eine doppelt verknüpfte Liste zu verwenden (und die Zeiger auf die erste Liste nicht zu vergessen) und die letzten Elemente).

    Sie können auch versuchen, eine Warteschlange auf zwei Stapeln zu implementieren, dies ist jedoch auch weniger effizient.

    Es gibt auch ein Deck (doppelseitig - deque). Darin können Sie sowohl am Ende als auch am Anfang Elemente hinzufügen. Und nimm sie auch vom Ende und vom Anfang an.

    Fazit



    Wow Ich beginne mich zu wiederholen und

    erwähne die Kombination verschiedener Sammlungen, dank derer Matrizen und Tabellen gebildet werden, überhaupt nicht. Außerdem habe ich die Bäume nicht berührt, den Ring gesetzt, fast nichts über die Warteschlangen geschrieben, sehr wenig Informationen über Hashing (ich habe noch ein paar Worte zu diesem Thema) und andere Optimierungsmethoden.

    Ich denke jedoch, dass der Artikel seine Rolle erfüllen wird - er wird einfach und klar die Grundlagen von Datenstrukturen für Leser mit unterschiedlichem Vorbereitungsgrad angeben. Und ich werde gerne weitermachen und viele (oder alle, ha!) Andere Themen in die gleiche Richtung lenken.

    Vielen Dank an diejenigen, die diese Zeilen lesen konnten (wie haben sie das überstanden?).

    Viel Glück bisher!

    Jetzt auch beliebt: