DOUG LLOYD: Also in CS50, die wir behandelt haben viele verschiedene Datenstrukturen, Recht? Wir haben gesehen, Arrays und verknüpfte Listen und Hash-Tabellen, und versucht, Stacks und Warteschlangen. Wir werden auch ein wenig zu lernen über Bäume und Haufen, aber wirklich diese alle nur am Ende herauf Sein Variationen über ein Thema. Es gibt wirklich diese Art von vier Grundideen dass alles andere können bis zu kochen. Arrays, verkettete Listen, Hash-Tabellen und versucht. Und wie ich schon sagte, gibt sind Variationen davon, aber das ist ziemlich viel los zusammenzufassen alles, was werden wir reden etwa in dieser Klasse in Bezug auf C. Aber wie diese alle Maßnahmen, oder? Wir haben über die Vor- und Nachteile gesprochen der jeweils in separaten Videos auf sie, aber es gibt eine Menge von Zahlen Kinder Umgebung geschleudert. Es gibt eine Menge von allgemeinem Gedanken immer um sich geworfen. Lassen Sie uns versuchen und zu konsolidieren, sie in nur einem Ort. Lassen Sie wägen die Vor-gegen die Nachteile, und betrachten die Datenstruktur könnte die richtige Daten sein Struktur für Ihre spezielle Situation, welcher Art von Daten Sie speichern. Sie müssen nicht unbedingt immer brauchen, um verwenden Sie die super schnelle Einfügen, Löschen, und Lookup eines Trie, wenn Sie wirklich nicht über Einfügen und Löschen von Pflege zu viel. Wenn Sie nur schnell Zufalls brauchen Zugang, vielleicht ein Array ist besser. Lassen Sie uns also, dass zu destillieren. Lassen Sie uns über jede der vier sprechen Hauptarten von Datenstrukturen dass wir gesprochen haben, und nur sehen, wenn sie könnte gut sein, und wenn sie nicht so gut sein könnte. Lassen Sie uns also mit Arrays zu starten. So Insertion, ist diese Art von schlecht. 

Ansatz am Ende eines Arrays in Ordnung ist, wenn wir bauen ein Array als wir gehen. Aber wenn wir brauchen, um einfügen Elemente in der Mitte, denken Sie zurück, um das Einführen Sortieren, es gibt eine Menge der Verschiebung, um ein Element in es passen. Und so, wenn wir gehen, um einfügen überall aber das Ende eines Arrays, das ist wahrscheinlich nicht so groß. 

Ebenso Löschen, es sei denn wir sind Löschen aus dem Ende des Arrays, ist wohl auch nicht so groß, wenn wir wollen nicht, um leere Zwischenräume zu verlassen, die in der Regel tun wir nicht. Wir wollen, um ein Element zu entfernen, und dann Art machen es wieder gemütlich. Und so Löschen von Elementen aus ein Array, auch nicht so toll. 

Lookup, obwohl, ist groß. Wir haben mit wahlfreiem Zugriff, konstante Zeit Lookup. Wir sagen nur sieben, und wir gehen Array Verlagerung sieben. Wir sagen, 20, mit Gehe zu Array Umzug 20. Wir müssen nicht über laufen. Das ist ziemlich gut. 

Arrays sind auch relativ leicht zu sortieren. Jedes Mal, wenn wir über eine Sortier sprachen Algorithmus, wie Auswahl Sortieren, Insertion Sort, Bubble-Sort, fusionieren sort wir immer Arrays verwendet, es zu tun, weil Arrays sind ziemlich einfach, Sortieren, relativ zu den Datenstrukturen wir bisher gesehen haben. 

Sie sind auch relativ klein. Es gibt nicht viel mehr Platz. Sie haben genau so viel beiseite gesetzt wie Sie benötigen, um Ihre Daten zu halten, und das ist so ziemlich alles. So sind sie ziemlich klein und effizient auf diese Weise. Aber ein anderer Nachteil, obwohl, ist, dass sie in der Größe festgelegt sind. Wir müssen uns genau erklären, wie big wollen wir unser Angebot zu sein, und wir nur einen Schuss auf sie. Wir können nicht wachsen und schrumpfen sie. 

Wenn wir brauchen, um zu wachsen oder schrumpfen, wir brauchen, um ein völlig neues Array deklarieren, kopieren Sie alle Elemente der erste Array in das zweite Array. Und wenn wir uns verkalkuliert, dass Zeit, müssen wir es wieder tun. Nicht so gut. So Arrays nicht geben uns die Flexibilität, variable Anzahl von Elementen haben. 

Mit einer verknüpften Liste, Insertion ist recht einfach. Wir haben gerade tack auf die Vorderseite. Das Löschen ist auch recht einfach. Wir haben, um die Elemente zu finden. Das beinhalten einige der Suche. 

Aber sobald Sie das Element gefunden haben Dank für alles, was Sie tun müssen suchen ist zu ändern einen Zeiger, möglicherweise zwei, wenn Sie a list-- einer doppelt verketteten verknüpften Liste, rather-- und dann können Sie nur befreien den Knoten. Sie müssen nicht zu verschieben alles um sich herum. Sie ändern nur zwei Zeigern, das ist also ziemlich schnell. 

Lookup ist schlecht, richtig? Damit wir um eine zu finden Element einer verketteten Liste, ob einfach oder zweifach verlinkt, wir suchen sie linear. Wir müssen am Anfang beginnen und bewegen das Ende, oder starten Sie am Ende bewegen zum Anfang. Wir haben nicht mit wahlfreiem Zugriff mehr haben. Wenn wir also tun ein viel Sucherei, vielleicht eine verkettete Liste ist nicht ganz so gut für uns. 

Sie sind auch wirklich schwer zu sortieren, oder? Die einzige Möglichkeit, eine verknüpfte Liste wirklich sortieren ist, sie zu sortieren, wie Sie es zu konstruieren. Aber wenn Sie es, wie Sie sortieren konstruieren, sind Sie nicht mehr machen schnelle Insertionen mehr. Sie sind nicht nur Heften Dinge, auf die Vorderseite. Sie müssen das zu finden richtige Stelle, um es zu setzen, und dann Sie die Einfügemarke wird fast so schlimm, das Einfügen in ein Array. So verknüpften Listen sind nicht so groß, für das Sortieren von Daten. 

Sie sind auch ziemlich klein, Größe her. Doppelt verknüpften Liste leicht größer als einfach verkettete Listen, die etwas größer sind als Arrays, aber es ist nicht eine riesige Menge an Platz verschwendet. Also, wenn Raum an einer Prämie ist, aber kein wirklich intensiv Premium, könnte dies der richtige Weg zu gehen. 

Hash-Tabellen. Einsetzen in eine Hash-Tabelle ist recht unkompliziert. Es ist ein zweistufiger Prozess. Zunächst müssen wir unsere Daten durchlaufen eine Hash-Funktion, um einen Hash-Code zu erhalten, und dann werden wir das Element in den Einsatz Hash-Tabelle zu dieser Hash-Code Standort. 

Deletion, ähnlich wie verknüpfte Liste, ist einfach, wenn Sie das Element zu finden. Sie müssen es zuerst finden, aber dann, wenn Sie es löschen, Sie brauchen nur zu tauschen ein paar Hinweise, falls Sie getrennte Verkettung sind. Wenn Sie mit Sondieren bist, oder wenn Sie nicht Verwendung Verkettung haupt in Ihrer Hash-Tabelle, Löschen ist eigentlich ganz einfach. Alles, was Sie tun müssen, ist die Hash- Daten, und dann an diesen Ort zu gehen. Und vorausgesetzt, dass Sie das nicht tun keine Kollisionen, Sie in der Lage, sehr schnell zu löschen. 

Nun, das ist, wo die Dinge Lookup ein wenig komplizierter. Es ist im Durchschnitt besser als verkettete Listen. Wenn Sie mit Verkettung bist, Sie haben noch eine verknüpfte Liste, was bedeutet, dass Sie immer noch die Such Schaden führen eine verknüpfte Liste. Aber weil du nimmst deinen verbunden Liste aus und leitet sie im über 100 oder 1000 oder n-Elemente in Ihre Hash-Tabelle, du bist verkettete Listen sind alle eine n-te Größe. Sie sind alle wesentlich kleiner. Sie haben n verkettete Listen statt einer verknüpften Liste der Größe n. 

Und so realen konstanten Faktor, der Allgemeinen wir reden nicht über in Zeitkomplexität ist es, hat tatsächlich einen Unterschied machen hier. So Lookup ist immer noch linear zu suchen, wenn Sie mit Verkettung bist, aber die Länge der Liste Sie durch suchst ist sehr, sehr kurz im Vergleich. Noch einmal, wenn Sortier ist Ihr Ziel ist hier, Hash-Tabelle wahrscheinlich nicht der richtige Weg zu gehen. Verwenden Sie einfach ein Array, wenn Sortier ist wirklich wichtig für Sie. 

Und sie die ganze Skala der Größe ausgeführt werden können. Es ist schwer zu sagen, ob ein Hash-Tabelle ist klein oder groß, weil es wirklich darauf an, wie groß Ihre Hash-Tabelle ist. Wenn Sie nur gehen, um die Speicherung fünf Elemente in Ihrem Hash-Tabelle, und Sie haben eine Hash-Tabelle haben mit 10.000 Elemente in ihr, sind Sie wahrscheinlich verschwenden viel Platz. Kontrast sein, können Sie auch haben sehr kompakt Hash-Tabellen, aber die kleineren Ihren Hash-Tabelle erhält, je länger jeder dieser verknüpften Listen erhält. Und so gibt es wirklich keine Möglichkeit, zu definieren genau die Größe einer Hash-Tabelle, aber es ist wahrscheinlich sicher zu sagen, es ist in der Regel werde größer als eine verbunden zu sein Liste Speichern der gleichen Daten, aber kleiner als ein Trie. 

Und Versuchen sind die vierte dieser Strukturen dass wir gesprochen haben. Einfügen in einen Trie ist komplex. Es gibt eine Menge von dynamischen Speicherzuweisung, insbesondere zu Beginn, Sie fangen an zu bauen. Aber es ist konstanter Zeit. Es ist nur das menschliche Element hier, die es schwierig macht. Mit den Null-Zeiger begegnen, malloc Raum, gehen dort, möglicherweise malloc Raum von dort wieder. Die Art von Einschüchterung Faktor Zeiger in die dynamische Speicherzuordnung ist die Hürde zu löschen. Aber wenn Sie es gelöscht haben, Einfügung kommt eigentlich ganz einfach, und es ist sicherlich konstante Zeit. 

Löschen ist einfach. Alles, was Sie tun müssen, ist eine nach unten navigieren paar Hinweise und frei den Knoten, das ist also ziemlich gut. Lookup ist auch ziemlich schnell. Es ist nur auf der Grundlage der Länge Ihrer Daten. Also, wenn Sie alle Ihre Daten fünf Zeichenketten, Sie können beispielsweise die Speicherung sind fünf Zeichenfolgen in Ihrem trie, es dauert nur fünf Schritte finden, was Sie suchen. Fünf ist nur eine Konstante, so wieder, Insertion, Deletion und Lookup hier sind alle konstante Zeit, effektiv. 

Eine andere Sache ist, dass Ihr Trie ist eigentlich ganz bereits sortiert, nicht wahr? Aufgrund der, wie wir sind Einfügen von Elementen, indem Sie Buchstaben für Buchstaben des Schlüssel oder Ziffernfolge des Schlüssels, in der Regel, endet Ihre Trie wobei Art sortiert, wie Sie es zu bauen. Es ist nicht wirklich macht Sinn, über Sortier denken in der gleichen Art, wie wir denken sie mit Arrays oder verkettete Listen, oder Hash-Tabellen. Aber in gewisser Weise Ihrer Trie wird sortiert, wie Sie gehen. 

Der Nachteil ist natürlich, dass ein Trie wird schnell riesig. Von jedem Verbindungspunkt, könnten Sie have-- wenn Ihr Schlüssel besteht aus Ziffern, Sie haben 10 weitere Orte, die Sie gehen können, die bedeutet, dass jedem Knoten enthält Informationen über die Daten, die Sie speichern wollen, an diesem Knoten, plus 10 Zeiger. Welche, auf CS50 IDE ist 80 Byte. So ist es mindestens 80 Bytes für jeder Knoten, die Sie erstellen, Und das ist nicht einmal eingerechnet Daten. Und wenn Ihr Knoten Buchstaben anstelle von Ziffern, Jetzt 26 Zeiger müssen Sie von jedem Ort. Und 26 mal 8 ist wahrscheinlich 200 Bytes oder so ähnlich. Und Sie Kapital und lowercase-- können sehen, wo ich mit diesem gehe, nicht wahr? Ihre Knoten kann wirklich groß, so dass der Trie selbst Insgesamt kann bekommen wirklich groß, zu. Also, wenn Raum an einer Hoch Premium auf Ihrem System, ein Trie ist vielleicht nicht der richtige Weg zu sein, zu gehen, obwohl seine anderen Leistungen komm in das Spiel. Ich bin Doug Lloyd. Dies ist CS50.