Was sind die nützlichsten Datenstrukturen von innen nach außen wissen? [geschlossen]

Question

Ich bin daran interessiert, herauszufinden, was die Menschen der nützlichsten Datenstrukturen in Betracht ziehen würden bei der Programmierung kennen. Welche Datenstruktur finden Sie sich die ganze Zeit mit?

Antworten zu diesem Beitrag sollten neue Programmierer interessiert helfen, eine nützliche Datenstruktur für ihr Problem zu finden. Die Antworten sollen wahrscheinlich die Datenstruktur, Informationen über sie enthalten oder einen entsprechenden Link, um die Situation es verwendet wird und warum ist es eine gute Wahl für dieses Problem (z ideal Berechnung Komplexität, Einfachheit und Verständnis usw.)

Jede Antwort sollte über eine Datenstruktur nur sein.

Vielen Dank für alle Perlen der Weisheit und Erfahrung Menschen teilen kann.

Answer 1

Eine der Datenstrukturen ich die meisten (über Vektoren, natürlich) ist der Hashtable. Es geht um die einzige Wahl, wenn Sie große Datenmengen in O (1) Zeit, dass die Zeit bedeutet, zu suchen, müssen in der Lage wächst nicht zu suchen, wie die Größe der Sammlung wächst.

Der Haken ist, dass die Einfügung und Löschung mal größer sind als in anderen Daten strutures, und Sie müssen eine Art Schlüssel haben, mit denen die Sammlung zu suchen. Jedes Element muss einen Schlüssel hat. Der Algorithmus nimmt den Schlüssel jedes Elements und berechnet einen Hash-Code, der den Schlitz in der Hash-Tabelle anzeigt, in der suchen. Dann je nach Implementierung entweder folgt eine Liste der Elemente, die auf diesem Eimer fielen um Ihren Artikel zu finden oder sucht es in der Nähe Eimer. Die Größe der hastable ist bestimmend für die Effizienz des Hash, der ganz von der ammount von Kollisionen von Hash-Codes zwischen den Tasten beeinflusst wird.

Verwenden Sie es, wenn Sie eine Karte und die erwartete Anzahl der Elemente der Karte benötigen überschreiten etwa 10. Es ist ein bisschen mehr speicherintensiver als andere Strukturen, da es viele ungenutzte Zeitnischen in der Tabelle effizient sein muss.

C # hat eine große Umsetzung mit Dictionary<keytype, valuetype> und hat sogar eine Hybriddictionary, die intern entscheidet, wann eine Hash-Tabelle oder einen Vektor zu verwenden. Jedes gute Buch über Programmierung beschreibt es aber Sie werden auch von wikipedia bedient werden: http://en.wikipedia.org/wiki/Hashtable

Answer 2

Ich muss Ihre Anforderung über eine Datenstruktur per Post außer Acht lassen - das sind diejenigen, die ich die meisten und die meisten Programme verwendet haben, finde ich, erfordern meist eine unter diesen oder eine Kombination.

Arrays - die grundlegendste und bietet den schnellsten Zugriff. Vektoren ist die Improvisation über die einfache alte Arrays und sind de facto Ersatz häufig in diesen Tagen. dequeue ist eine weitere Variation dieses Themas und wieder bietet consant Zeit / random access aber für schnelle Einfügungen und Löschungen am Anfang und Ende optimiert.

Link-Liste - sehr nützlich, um eine Liste von Daten zu erhalten, die fallen gelassen wird und häufig aber sehr langsam iterieren / Suche eingesetzt. zB Frei / Besetzt-Listen innerhalb Speicherseiten

Bäume - eine Grundstruktur, die die Grundlage von komplexeren Strukturen bildet. Es gibt viele Formen dieser Struktur. Bietet logn Suchzeiten, wenn der Baum sorted.Becomes nützlich für große Datenelemente wie Wörterbücher gehalten wird. Binär / AVL und rot-schwarz Bäume sind die häufigsten.

Karten und Hashes - Nicht gerade Datenstrukturen, aber komplexe schnelle Lookup-Algorithmen implementiert unter Verwendung einer Kombination von cleveren Logik und diese obige Datenstruktur

.

Diese Datenstruktur und ihre implementaion sind in der STL-Bibliothek in C ++ avalable. Andere Sprachen auch ihre nativen Implementierungen haben. Sobald Sie wissen, diese grundlegenden Datenstrukturen und ein paar ihrer variatons (Queue, Stapel, Prioritäts-Warteschlangen) und etwas über Suchalgorithmen ich die Grundlagen abgedeckt würden wohl sagen würde.

Answer 3

Ich finde mich mit assoziativen Arrays sehr viel, im Grunde Arrays mit einem String als Index.

Answer 4

  

Die Vorteile der verkettete Listen sind, dass sie sehr billig sind zum Hinzufügen / Entfernen Knoten. Im Gegensatz zu Arrays [...] sie nicht benötigen mehr Speicher Neuzuweisung auf weiter aus.

Wenn Sie ein Array und Sie verdoppeln die Zuweisung Größe jedes Mal, wenn es füllen, werden Sie amortisiert O haben (1) anhängt. Auch Schleifen über alle Elemente eines Arrays ist wahrscheinlich schneller sein (in der Wand Zeit) als über eine verknüpfte Liste Looping, aufgrund Cachen Effekte (es sei denn, Sie über die Links in großen Brocken zuteilen und verwirren nicht um mit ihnen zu viel ).

Auch Arrays sind kleiner: Sie können das pro-Element Wort speichern Overhead sowie der pro-Allocation-Overhead (die wahrscheinlich mindestens zwei Worte ist: eine für die Größe und ein für den nächsten in dem Freilistenzeiger) .

Answer 5

Verknüpfte Listen / doppelt verkettete Listen / andere Varianten

Jeder sollte die Vor- und Nachteile einer verketteten Liste kennen, und durch das völlige Fehlen der Nutzung, so scheint es, etwas, das viele Menschen scheinen zu vergessen zu sein.

Die Vorteile der verkettete Listen sind, dass sie sehr billig sind zum Hinzufügen / Entfernen Knoten. Im Gegensatz zu Arrays oder Datenstrukturen, die einen Array im Kern zu verwenden, müssen sie nicht mehr Speicher Neuzuweisung auf weiter aus.

Die Nachteile sind, dass sie keine gute Leistung auf allen für die Suche. Was in einem Array ein O (1) Lookup wäre O (n) für eine verkettete Liste.

Wie alle Strukturen, verkettete Listen sind ideal nur unter bestimmten Bedingungen. Aber zur richtigen Zeit eingesetzt werden, sind sie sehr mächtig.

Answer 6

Ich finde ich Arrays sehr häufig in Kombination mit der „foreach“ Kontrollstruktur Schleife durch die Elemente verwenden. In der Vergangenheit verwenden I-Arrays mit einem numerischen Index und dem "für (i = 1; i

Answer 7

Graphs sind eine sehr leistungsfähige Datenstruktur übersehen.

Viele Probleme können durch die Konstruktion eines Graphen modelliert Ihr Problem gelöst werden, dann einen bekannten Algorithmus auf der Grafik verwendet wird. Einige Beispiele der Verarbeitung natürliche Sprache (das Kantengewicht Verbindungsknoten darstellen können, wie wahrscheinlich ein Wort ist eine weitere folgen) Videospielen (Verwendung Graphen kürzeste Pfade für AI Zeichen zu bestimmen) und die Netzwerktopologie.

Ich habe gelernt, Graphen von Der Algorithmus Design Manual , die empfohlen wurde von Steve Yegge in einer Blog-Post .

Answer 8

Ich mag Binärbäumen. Besonders Variante der Splay-Baum. Es ist etwas ähnlich wie bei einem selbstausgleich Binärbaum sondern auch auf die Nutzungsmuster der Anwendung anzupassen. Sie fast nie in schlimmsten Fall O (n) Verhalten führen.

Ein schöner Bonus ist, dass sie auch leichter zu schreiben und benötigen weniger Code als andere sich selbst ausgleich Binärbäumen. Es ist eine meiner Lieblings-Daten-Strukturen, weil es so unglaublich gut in der Praxis führt.

http://en.wikipedia.org/wiki/Splay_tree

Answer 9

Das ist ein bisschen wie zu fragen, welche Werkzeuge in einem Werkzeugkasten Tischler sind am besten zu nutzen, um zu lernen. Jeder von ihnen ist gut für eine bestimmte Art von Arbeit, und Sie müssen den grundlegend diejenigen lernen (Karten, Listen, Taschen, Sets, usw.) gleichermaßen.

Answer 10

Ich glaube nicht, dass es eine Datenstruktur ist man wissen muss. Jede Datenstruktur hat seine eigenen Eigenschaften, und somit geeignet für ein bestimmtes Problem.

Answer 11

Ich habe immer eine Vielzahl von Anwendungen für Stacks, wenn auch weniger in der objektorientierten Programmierung. Wirklich, alle Datenstrukturen haben ihren Nutzen, und sie sind nicht komplex. Erfahren Sie alles, was Sie können.

Answer 12

Dieser Beitrag ist viel zu vage. Es gibt unzählige Datenstrukturen. Arrays, Wörterbücher, usw. Jede Datenstruktur verwendet werden, können verschiedene Probleme zu lösen

Es wäre viel produktiver sein für ein bestimmtes Problem für DS zu stellen.

Answer 13

Für eine grundlegende Wertschätzung, sollten Sie ein paar abstrakten Datentypen kennen (set, Wörterbuch, geordnete Liste, Queue, Stack etc.) und verschiedener Möglichkeiten, die jeweils mit ihren relativen Kompromissen umzusetzen.

Dies erfordert, dass Sie wahrscheinlich Felder, verkettete Listen zu verstehen (Einzel- und Doppel verbunden ist), Hash-Tabellen, binäre Suchbäume (mit einem gewissen Verständnis des einfachen Abgleich Heuristiken) und binären Haufen. Kennen Sie diese von innen nach außen, und Sie werden ein langer Weg zum Verständnis komplexe und interessante Datenstrukturen sein. Plus, wenn Sie alle von ihnen implementiert haben, werden Sie haben eine fertige Bibliothek, die Sie für die Programmierung von Projekten verstehen (obwohl offensichtlich mehr kampfgestählten Bibliotheken wie Boost-oder was auch immer besser geeignet für die Produktion Code sind).

Dies ergibt eine sehr nützliche Vokabular von Datenstrukturen, die einen signifikanten Unterschied zu der Art und Weise machen könnten Sie Ihre Programme schreiben. Sie könnten Sie feststellen, habe Probleme mit vielen Teil Implementierungen einer Warteschlange, zum Beispiel zu lösen, dass man jetzt mit einer kanonischen Implementierung ersetzen kann.

Answer 14

Ich glaube nicht, dass es hier eine allgemeine Antwort. Es sollte zu einem gewissen Anwendungsfall begrenzt werden. Zum Beispiel in meiner mehr als 10-jährigen Karriere als Programmierer / Manager habe ich noch nie Binärbäumen verwendet. Ich bezweifle, dass bedeutet, dass binäre Bäume nicht nützlich sind, aber das in Kernel und Embedded-Welt die verkettete Liste wahrscheinlich besser paßt.
Eigentlich, wenn ich denke, über ein paar Ausnahmen fallen benutzte ich nur einfach verkettete Listen.
Und dann auch in eingebetteten es wahrscheinlich nicht die einzige Struktur verwendet, ich bin in der Welt der Low Level-Hardware-Protokolle leben, wahrscheinlich „den Berg hinauf“ mehr Datenstrukturen ...

Answer 15

Quicksort

Mergesort

Bubblesort

Das ist wirklich gut zu lernen und zu verstehen, wie sie funktionieren. Das Sortieren ist Spaß und kann auf viele Bereiche angewendet werden:)