[Musik zu spielen] DAVID MALAN: Dies ist CS50. Und dies ist sowohl der Beginn und das end-- wie literally-- fast zum Ende der Woche sechs. 

Ich dachte, ich würde eine Aktie bisschen ein Spaß Tatsache. Ich habe dies aus einer hochgezogen Daten vergangenen Semester gesetzt. Sie erinnern sich vielleicht, dass wir Sie bitten, auf jeden p soll Formular, wenn Sie online gesehen haben oder wenn Sie persönlich besucht habe. Und hier sind die Daten. So war heute sehr vorhersehbar. Aber wir wollten ein wenig zu verbringen der Zeit mit Ihnen dennoch. Möchte jemand, warum diese Vermutung Graphen ist so Jaggy, up down, up down, so konsequent? Was jeder von den Gipfeln und Mulden stellen? 

PUBLIKUM: [unverständlich] DAVID MALAN: In der Tat. Und mehr amüsant, Gott bewahre, wir halten eine Vorlesung an einem Freitag zu Beginn des Semesters, das ist, was wir sehen passieren. So heute, teilhaben wir in ein wenig mehr über Datenstrukturen. Und um Ihnen mehr von einem Feststoff zu ergeben mentales Modell für Probleme auf fünf, Das ist jetzt aus. Rechtschreibfehler, bei dem wir Hand Sie eine Textdatei einige 100.000 zzgl englische Wörter, und Sie gehen zu müssen sind um herauszufinden, wie man geschickt laden in den Speicher, in den Arbeitsspeicher, mit ein paar Daten Struktur Ihrer Wahl. 

Jetzt eine solche Datenstruktur könnte sein, aber wahrscheinlich nicht sein sollte, die ziemlich simpel verketteten Liste, was wir letztes Mal eingeführt. Und eine verbundene Liste hatte zumindest Ein Vorteil gegenüber einem Array. Was ist ein Vorteil eine verbundene Liste wohl? 

PUBLIKUM: Einfügen. 

DAVID MALAN: Einfügen. Was meinen Sie damit? 

PUBLIKUM: Überall entlang die Liste [unverständlich]. 

DAVID MALAN: Gut. So können Sie ein Element, wo einfügen Sie in der Mitte der Liste möchten ohne etwas zu mischen, welche wir zu dem Schluss, in unserem Sortier Diskussionen, ist nicht unbedingt eine gute Sache, weil es Zeit braucht, um tatsächlich zu bewegen alle diese Menschen links oder rechts. Und so mit einer verketteten Liste, können Sie gerade mit malloc, ein neuer Knoten, und aktualisieren Sie dann ein paar pointers-- zwei, drei Operationen max-- und wir sind in der Lage, jemanden Steckplatz in jedem Ort in eine Liste. 

Was war von Vorteil zu einer verketteten Liste? Ja? 

PUBLIKUM: [unverständlich] DAVID MALAN: Perfect. Perfect. Es ist wirklich dynamisch. Und dass Sie nicht zu begehen, im Voraus, bis zu einem gewissen festen Größe Teil des Speichers, wie Sie müssten mit einer Anordnung, die auf den Kopf davon ist, dass man Knoten nur zuteilen Nachfrage dadurch mit nur so viel Platz wie Sie tatsächlich benötigen. Im Gegensatz zu einem Array, könnte man versehentlich zu wenig zuordnen. Und dann ist es nur geht ein Schmerz im Nacken , um eine neue größere Array umzuschichten, kopieren alles vorbei ist, befreit das alte Array, und verschieben Sie dann über Ihr Unternehmen. Oder noch schlimmer, könnte man so zuteilen mehr Speicher, als Sie tatsächlich benötigen, und so wirst du einen sehr haben sind dünn besiedelten Array, so zu sprechen. 

So eine verbundene Liste gibt Ihnen diese Vorteile der Dynamik und Flexibilität mit Insertionen und Deletionen. Aber sicherlich muss es einen bezahlten Preis. In der Tat, eines der Themen auf Quiz Null erkundet war ein paar der Kompromisse wir bisher gesehen. Also, was ist ein Preis zu zahlen oder eine Nachteil einer verketteten Liste? Ja. 

PUBLIKUM: Kein Direktzugriff. 

DAVID MALAN: Kein Direktzugriff. Aber wen interessiert das? Random access klingt nicht überzeugend. 

PUBLIKUM: [unverständlich] DAVID MALAN: Genau. Wenn Sie haben wollen eine gewisse algorithm-- und lassen Sie mich eigentlich vorschlagen binäre Such insbesondere die ist einer wir ziemlich bit-- verwendet haben wenn Sie nicht mit wahlfreiem Zugriff, Sie können nicht so einfach rechnen kann zu finden wie das mittlere Element und Springen Recht darauf. Sie haben statt dessen beim ersten Start Element und linear von links suchen nach rechts, wenn Sie suchen möchten die mittlere oder ein anderes Element. 

PUBLIKUM: Es dauert wohl mehr Speicher. 

DAVID MALAN: mehr Speicherplatz. Wo ist, dass zusätzliche kosten, die aus in Erinnerung? 

PUBLIKUM: [unverständlich] DAVID MALAN: Genau. In diesem Fall hier, wir hatten eine verkettete Liste für ganze Zahlen, und doch sind wir verdoppeln die Speichermenge, wir brauchen, indem auch die Speicherung dieser Zeiger. Jetzt weniger eine große Sache wie Ihre Strukturen werden größer und Sie die Speicherung nicht eine Zahl, sondern vielleicht ein Student oder ein anderes Objekt. Aber der Punkt sicherlich bleibt. Und so eine Reihe von Operationen auf verkettete Listen genannt wurden waren groß O von N- linear. Dinge wie Insertion oder Suche oder Löschen, falls ein Element passiert ganz am Ende sein, die Liste, ob es sortiert oder nicht. 

Manchmal werden Sie vielleicht Glück haben und in so untere Schranken für diese Operationen Vielleicht haben Sie auch konstante Zeit sein, wenn Sie immer auf der Suche beim ersten Element, beispielsweise. Aber letztlich, wir versprochen um den heiligen Gral zu erreichen Datenstrukturen oder einige Annäherung davon, haft konstante Zeit. Finden wir Elemente oder Elemente hinzufügen oder entfernen Sie Elemente aus einer Liste? Wir werden schon bald sehen. Und es stellt sich heraus, dass einer der Mechanismen sind wir werde heute beginnen zu bedienen, Jahresnutzung in S. fünf, ist eigentlich ziemlich vertraut. Zum Beispiel, wenn dies ein Bündel Prüfungs Bücher, von denen jede hat ein Student das erste Name und Vorname darauf und ich sie abholen von am Ende einer Prüfung, und sie sind alle ziemlich viel in einer zufälligen Reihenfolge, und wir wollen über das Sortieren gehen wollen Diese Prüfungen, so dass einmal benotet es ist nur viel einfacher und schneller, um sie aus zurückgeben um Studenten alphabetisch. Was würden Sie Ihrem Instinkt sein für einen Haufen von Prüfungen wie diese? 

Nun, wenn Sie wie ich sind, Sie vielleicht sehen, dass dies m, so werde ich eine Art setzen Sie dieses in, wenn dies meinem Tisch oder meiner Etage, wo Verbreite ich Dinge out-- oder meine Array really-- Ich könnte die ganze Frau in es gesetzt. Oh. Hier ist ein A. Also ich könnte Nehmen Sie den AS hier. Oh. Hier ist eine andere Antwort: Ich werde , die der über hier setzen. Hier ist eine Z. Hier ist ein weiteres M. Und so Ich könnte anfangen, Pfähle wie diese. Und dann würde ich vielleicht später gehen in und irgendwie sehr pingelig-ly sortieren die einzelnen Pfähle. Aber der Punkt ist, ich würde aussehen am Eingang, dass ich handed und ich würde einige berechnet Entscheidung auf der Grundlage dieser Eingabe. Wenn Sie es mit A beginnt, legte es dort drüben. Wenn Sie es mit Z beginnt, legte es über dort, und alles dazwischen. 

Das ist also eine Technik, die es allgemein als hashing-- H-A-S-H- bekannt die in der Regel bedeutet, die als Eingang und mit diesem Eingang zu berechnen, ein Wert, in der Regel eine Zahl ist, und daß Zahl ist der Index in eine Speicher Behälter, wie ein Array. Also mit anderen Worten, könnte ich eine haben Hash-Funktion, wie ich in meinem Kopf zu tun, dass, wenn ich jemanden sehe, ist Namen, die mit A beginnt, Ich gehe zur Karte, dass in meinem Kopf Null. Und wenn ich mit Z jemanden sehen, ich bin werde, dass zu 25 Karte in meinem Kopf und setzen Sie dann, dass in der letzte meisten Haufen. 

Nun, wenn Sie über keine mein Gehirn denken aber ein C-Programm, welche Zahlen könnten Sie verlassen sich auf, um das gleiche Ergebnis zu erzielen? In anderen Worten, wenn man hatte das ASCII-Zeichen A, wie Sie bestimmen, was Eimer, um es in zu setzen? Sie wollen wahrscheinlich nicht zu steckte es in Eimer 65, die wäre wie drüben ohne guten Grund. Wo sehen Sie nach A setzen wollen im Hinblick auf seine ASCII-Wert? Wo möchten Sie in die entsprechende ASCII tun wollen Wert zu kommen mit einer intelligenteren Eimer um es in zu setzen? 

PUBLIKUM: Minus A. 

DAVID MALAN: Yeah. Also minus A oder minus Insbesondere wenn es 65 eine Kapital A. Oder 98, wenn es ist eine kleine a. Und damit würde uns erlauben, sehr einfach und sehr arithmetisch, geben Sie etwas in einen Eimer so. So stellt sich heraus, dass wir tatsächlich tun dies auch noch mit den Quizfragen. 

So könnten Sie sich erinnern Sie kreisten Ihre Name Lehre Kerl auf dem Cover. Und benennt die TF wurden organisiert in diesen Spalten alphabetisch, Nun, es glauben oder nicht, wenn alle 80 Plus von uns trafen sich die andere Nacht in der Besoldungsgruppe, der letzte Schritt in unserem Sortierprozess ist es, die Quizfragen in ein großes hash Raum der Etage an der [unverständlich] und jedermanns Quiz zu legen, in genau der Reihenfolge ihrer TF Namen auf dem Cover, weil dann ist es viel einfacher für uns durch Verwendung dieser linearen Such Suche oder irgendeine Art von Klugheit für ein TF zu finden sein oder ihrer Schüler Quiz. 

Also diese Idee von Hashing dass Sie sehen, ist, sehr mächtig ist eigentlich ziemlich alltäglich und sehr intuitiv, ähnlich wie vielleicht teilen und Eroberung war in Woche Null. Ich faste mich auf den Hackathon ein paar Jahre her. Dies war Zamyla und ein paar andere Mitarbeiter Gruß Studenten wie sie hereinkam. Und wir hatten eine ganze Reihe von Falten Tischen mit Namensschild. Und wir hatten die Namensschilder organisiert mit wie die Da drüben und die Zs drüben. Und so einer der TFs sehr geschickt schrieb dies als den Anweisungen für den Tag. Und in der 12. Woche des Semesters dieses alle absolut Sinn, und jeder machte wusste, was zu tun ist. Aber, wenn Sie haben in gleicher Weise in der Warteschlange, Sie Implementierung sind die gleiche Vorstellung von einem Hash. Lassen Sie uns also zu formalisieren es ein wenig. Hier ist ein Array. Es ist gezeichnet, ein wenig breit, nur um darzustellen, visuell, dass wir vielleicht Saiten setzen in so etwas wie dieses. Und das Array deutlich von der Größe 26 gesamt. Und das Ding heißt Tabelle willkürlich. Doch dies ist nur Wiedergabe eines Künstlers von dem, was eine Hash-Tabelle könnte. 

So eine Hash-Tabelle nun auf geht sein eine höhere Datenstruktur. Am Ende des Tages wir sind dabei, um zu sehen, dass Sie eine Hash-Tabelle, implementieren die ist ähnlich wie die Check-in-Line bei einem Hackathon ähnlich wie dies Tabelle verwendet zum Sortieren Prüfung Bücher. Aber eine Hash-Tabelle ist Art von diesem hohen Niveau Konzept, das ein Array verwenden unter der Haube, sie umzusetzen, oder es könnte eine Länge Liste verwenden, oder sogar vielleicht einige andere Datenstrukturen. Und jetzt, da ist der theme-- Mitnahmen einige dieser Grundbestandteile wie ein Array und diesem Gebäude blockieren jetzt mit einer Länge Liste und zu sehen, was wir sonst noch bauen können zusätzlich zu jenen, wie Zutaten in ein Rezept, so dass mehr und mehr interessante und nützliche Endergebnisse. 

Also mit der Hash-Tabelle könnten wir sie umsetzen im Speicher bildhaft wie diese, aber wie könnte es tatsächlich kodiert werden? Nun, so einfach ist vielleicht. Wenn die Kapazität in Großbuchstaben, ist nur einige constant-- zum Beispiel 26, für 26 Buchstaben des alphabet-- Ich könnte meine Variablentabelle aufrufen, und ich könnte behaupten, dass ich zu gehen setzen char Sternen drin, oder ein String. Also ist es so einfach, wie dies, wenn Sie wollen eine Hash-Tabelle zu implementieren. Und doch, das ist wirklich nur ein Array. Aber noch einmal, ein Hash Tabelle ist jetzt, was wir rufen Sie einen abstrakten Datentyp, der gerade ist Art eines konzeptionellen Schichtung oben von etwas eher banalen Jetzt wie ein Array. 

Nun, wie gehen wir über die Lösung von Problemen? Nun, früher hatte ich den Luxus , genug Tabellenbereich hier so dass ich die genommen Quiz überall wollte ich. So könnte hier zu gehen. Zs vielleicht hier. Frau könnte hier zu gehen. Und dann hatte ich etwas mehr Platz. Aber das ist ein bisschen wie ein Cheat rechts jetzt, weil dieser Tabelle, wenn ich wirklich dachte an sie als ein Array, ist nur werde von einigen festen Größe sein. 

So technisch, wenn ich meinen up eines anderen Studenten Quiz und sehen, oh, diese Person Name beginnt mit einem A zu, Ich Art wollen sie dort einführen. Aber sobald ich es da, wenn Diese Tabelle Tat stellt ein Array, Ich werde dann überwiegend sein kann oder clobbering Wer auch immer dieser Schüler-Quiz ist. Richtig? Wenn dies ein Array ist, kann nur eins gehen in jeder dieser Zellen oder Elemente. Und so habe ich Art haben zu wählen, und wählen. 

Jetzt früheren Ich Art betrogen und tat dies oder ich nur irgendwie gestapelt sie übereinander liegen. Aber das wird nicht im Code zu fliegen. Also, wo könnte ich das zweite Student, dessen Namen ist ein, wenn alles, was ich hatte, ist dies verfügbar Tabellenbereich? Und ich habe drei Steckplätze, und es verwendet sieht aus wie es ist nur ein paar andere. Was könnten Sie tun? PUBLIKUM: [unverständlich] DAVID MALAN: Yeah. Vielleicht lassen Sie halten es gerade einfach. Richtig? Es passt nicht, wo ich will, es zu setzen. Also werde ich um es technisch, wo ein B gehen würde. Nun, natürlich, ich fange um mich in eine Ecke zu malen. Wenn ich an einen Studenten bekommen dessen Name ist eigentlich B, Jetzt B wird sich ein wenig verschoben werden nach vorn, wie es passieren, yep, ob dies ein B, jetzt muss es hier gehen. 

Und so ist dies sehr schnell könnte problematisch werden, aber es ist eine Technik, die eigentlich wird als lineare Abtastung bezeichnet, wodurch Sie gerade betrachten Sie Ihre Array entlang der Linie sein. Und du nur irgendwie Sonde oder Überprüfen Sie jedes verfügbare Element auf der Suche nach einem freien Fleck. Und sobald Sie feststellen, ein, es bringt Sie dort. 

Nun ist der Preis jetzt bezahlt Für diese Lösung ist was? Wir haben eine feste Größe Anordnung, und wenn ich einfügen Namen hinein, zumindest anfänglich, was die Laufzeit des Einsetzens für die Umsetzung der Schülerinnen und Schüler Quiz in den richtigen Eimer? Big O von was? 

PUBLIKUM: n. DAVID MALAN: Ich habe gehört, Big O n. Das stimmt nicht. Aber wir werden auseinander zu necken warum in nur einem Augenblick. Was sonst könnte es sein? 

PUBLIKUM: [unverständlich] DAVID MALAN: Und lassen Sie mich es tun visuell. Also vermute, dies ist der Buchstabe S. 

PUBLIKUM: Es ist einer. DAVID MALAN: Es ist einer. Richtig? Dies ist ein Array, das bedeutet, dass wir mit wahlfreiem Zugriff. Und wenn wir davon halten als Null und dies als 25, und wir erkennen, dass, oh, hier ist mein Eingang S, Ich kann sicherlich konvertieren S, ein ASCII-Zeichen, mit einer entsprechenden Anzahl zwischen null und 25 und dann sofort setzte es, wo es hingehört. 

Aber natürlich, sobald ich auf das zu bekommen zweite Person, der Name ist A oder B oder C schließlich, wenn ich verwendet habe, die lineare Sondieren als meine Lösung, die Laufzeit Einführen im ungünstigsten Fall ist eigentlich los, um in das, was übergehen? Und ich habe hier hören richtig früh. PUBLIKUM: [unverständlich] DAVID MALAN: So ist es in der Tat einmal ist n Sie haben einen ausreichend großen Datensatz. So, auf der einen Seite, wenn Ihr Array ist groß genug, und Ihre Daten sind spärlich genug, können Sie bekommen diese schöne konstante Zeit. Aber sobald Sie anfangen immer mehr Elemente, und nur statistisch erhalten mehr Menschen mit dem Buchstaben A wie ihr Name oder der Buchstabe B, könnte es möglicherweise übertragen in etwas mehr linear. Also nicht ganz perfekt. So könnten wir besser machen? 

Nun, was war unser Lösung vor, wenn wir wollen mehr Dynamik als haben etwas wie ein Array erlaubt? PUBLIKUM: [unverständlich] DAVID MALAN: Was haben wir vor? Ja. So eine verkettete Liste. Nun, mal sehen, was ein verknüpftes Liste könnte für uns stattdessen tun. Nun, lassen Sie mich vor, dass wir zeichnen das Bild wie folgt. Nun ist dies eine andere Bild von einem Beispiel aus einem anderen Text, tatsächlich, daß tatsächlich unter Verwendung eines Array der Größe 31. Und dieser Autor einfach beschlossen, Strings hash nicht auf Namen der Person basiert, sondern auf der Grundlage ihrer Geburtsdaten. Unabhängig von der Monat, dachte sie wenn Sie am ersten eines Monats geboren sind oder 31. eines Monats, der Autor wird auf der Grundlage dieser Wert hash, um so die Namen ein bisschen zu verbreiten mehr als nur 26 Spots könnte ermöglichen. Und vielleicht ist es ein wenig mehr einheitliche als sich mit alphanumerischen Zeichen denn natürlich gibt es wahrscheinlich mehr Menschen auf der Welt mit Namen dass beginnen mit einem als sicher einige andere Buchstaben des Alphabets. Also vielleicht ist das ein wenig gleichmäßiger, unter der Annahme, eine gleichmäßige Verteilung von Babys in einem Monat. 

Aber natürlich ist dies immer noch unvollkommen. Richtig? Wir mit Kollisionen. Mehrere Menschen in diese Datenstruktur noch mit dem gleichen Geburtsdatum mindestens du bist unabhängig von Monat. Aber was hat der Autor getan? Nun, es sieht aus wie wir haben eine Reihe auf der linken Seite vertikal gezogen, aber das ist nur ein Künstlerwiedergabe. Es ist egal, welche Richtung man zeichnen ein Array, ist es noch ein Array. Was ist das ein Array von scheinbar? 

PUBLIKUM: verketteten Liste. 

DAVID MALAN: Yeah. Es sieht aus wie es ist ein Array von verketteten Liste. Also noch einmal, zu diesem Punkt der Art der Verwendung dieser Datenstrukturen jetzt als Zutaten mehr interessante Lösungen, Sie absolut nehmen ein fundamental, wie ein Array, und dann etwas mehr interessant wie eine verkettete Liste und sogar kombinieren sie zu einem noch interessanter Datenstruktur. Und in der Tat, auch dies würde eine Hash-Tabelle aufgerufen werden, wobei das Array wirklich die Hash-Tabelle, aber das Hash-Tabelle hat Ketten, sozusagen dass wachsen oder schrumpfen auf die anhand Anzahl der Elemente, die Sie einfügen möchten. 

Jetzt dementsprechend, was die Laufzeit ist jetzt? Wenn ich jemandem einfügen deren Geburtstag ist der 31. Oktober, wo kommt er oder sie gehen? In Ordnung. Ganz unten, wo es heißt 31. Und das ist perfekt. Das war konstante Zeit. Aber was, wenn wir jemand anderen finden deren Geburtstag wird, mal sehen, Oktober, November, 31. Dezember? Wo ist er oder sie hingehen? Elbe. Zwei Schritt though. Das ist konstant aber nicht wahr? In Ordnung. Im Moment ist es. Aber im allgemeinen Fall, Je mehr Menschen wir hinzufügen, probabilistisch, wir gehen mehr und mehr Kollisionen zu erhalten. 

Nun ist dies ein wenig besser, weil technisch nun meine Ketten könnte sein im schlimmsten Fall, wie lange? Wenn ich n Personen in diese mehr einfügen komplexe Datenstruktur, n Menschen, im schlimmsten Fall, es wird n sein. Warum? 

PUBLIKUM: Denn wenn alle hat am gleichen Tag Geburtstag, sie gehen, um eine Zeile sein. DAVID MALAN: Perfect. Es könnte ein wenig gekünstelt sein, aber wirklich im schlimmsten Fall, wenn jeder hat den gleichen Geburtstag, angesichts der Eingänge Sie haben, Sie ein Baby haben sind massiv langkettigen. Und so können Sie es einen nennen Hash-Tabelle, aber eigentlich ist es nur eine massive verketteten Liste mit eine ganze Menge Platz verschwendet. Aber in der Regel, wenn wir annehmen, daß mindestens Geburtstage sind uniform-- und es ist wahrscheinlich nicht. Ich mache, dass bis. Wenn wir aber annehmen, beispiels um der Diskussion willen daß sie dann in der Theorie, wenn Dies ist die vertikale Darstellung des Arrays, na dann hoffentlich bist du werde Ketten, die sind, wissen Sie, ungefähr die gleiche Länge haben, wo jeder diese stellt einen Tag des Monats. 

Nun, wenn es 31 Tage im Monat, das bedeutet, dass meine Laufzeit wirklich ist groß O von n über 31, die fühlt sich besser als linear. Aber was war eines unserer Verpflichtungen ein paar Wochen vor, wenn es um auszudrücken kam die Laufzeit eines Algorithmus? Gerade erst am hohen Auftragstigen aussehen. Richtig? 31 ist auf jeden Fall hilfreich. Aber das ist immer noch ein großes O n. Aber eines der Themen von Problem stellte fünf wird zu sein, erkennen an, dass absolut, asymptotisch theoretisch Diese Datenstruktur ist nicht besser als einfach einem massiven verketteten Liste. Und zwar im ungünstigsten Fall Hash-Tabelle könnte in diese übergehen. 

Aber in der realen Welt, mit uns Menschen dass die eigenen Macs oder PCs oder was auch immer und laufen realen Welt Software auf realen Daten, welcher Algorithmus wollen Sie lieber? Die eine, die Ende Schritte oder das dauert eine, n um 31 Schritte unterteilt Takes einige Stück von Daten zu finden oder nachschlagen einige Informationen? Ich meine, absolut die 31 Marken ein Unterschied in der realen Welt. Es ist 31 mal schneller. Und wir Menschen sind sicherlich werde das zu schätzen wissen. 

So realisieren die Dichotomie es zwischen tatsächlich reden über die Dinge theoretisch und asymptotisch die definitiv Wert hat, wie wir gesehen haben, aber in der realen Welt, wenn man darüber nur machen die Pflege Menschen glücklich für allgemeine Eingänge, Sie könnte sehr gut zu akzeptieren möchten die Tatsache, dass ja, ist diese lineare, aber es ist 31 mal schneller als linear sein könnte. Und noch besser, wir haben nicht nur zu tun Sie etwas willkürlich wie ein Geburtsdatum, wir ein wenig verbringen mehr Zeit und Klugheit und darüber nachdenken, was wir tun könnten, gegebenen Namen einer Person und vielleicht ihren Geburtstag mit denen kombinieren Zutaten, um herauszufinden, was das ist wirklich mehr einheitliche und weniger Jaggy, so als dieses Bild sprechen Derzeit schlägt es sein könnte. Wie könnten wir implementieren diese im Code? Nun, lassen Sie mich vor, dass wir nur einige Syntax wir haben zu leihen ein paar Mal verwendet so weit. Und ich werde zu definieren ein Knoten, wieder was ist ein Oberbegriff für nur einige Behälter für einige Datenstruktur. Ich werde mich vorzuschlagen ein String wird in dort. Aber wir werden zu Beginn der Einnahme diejenigen, die Ausbildung Räder vom jetzt. 

No more CS50-Bibliothek wirklich, es sei denn, Sie wollen um es für Ihre endgültige verwenden Projekt, was in Ordnung ist, aber jetzt werden wir nach hinten zu ziehen die Vorhang und sagen, es ist nur ein char Stern. Also das Wort es sein wird den Namen der Person in Frage. Und jetzt habe ich einen Link hier an den nächsten Knoten so daß diese stellen jeder der Knoten in der Kette, möglicherweise, einer verknüpften Liste. 

Und jetzt, wie kann ich erklären, die Hash-Tabelle selbst? Wie kann ich erklären, dass diese ganze Struktur? Also wirklich, so wie ich früher einen Zeiger nur das erste Element der Liste vor, ähnlich wie kann ich nur sagen, Ich brauche nur ein Bündel von Zeigern diese ganze Hash-Tabelle zu implementieren. Ich werde ein Array haben genannt Tisch für Hash-Tabelle. Es wird von der Größe Kapazität. Das ist, wie viele Elemente in ihm passen. Und jedes dieser Elemente in diesem Array wird ein Knoten Star. Warum? Nun, das, was ich bin pro Bild Umsetzung der Hash-Tabelle als effektiv in der Anfang ist nur Dieses Array, das wir haben vertikal gezogen, deren jeweilige Quadrate repräsentiert einen Zeiger. Dass diejenigen, die Schrägstriche haben durch sie sind nur null. Und diejenigen, die haben Pfeilen geht nach rechts sind tatsächliche Hinweise auf tatsächliche Knoten, ergo den Beginn einer verketteten Liste. 

So, hier ist also, wie wir Implementierung einer Hash-Tabelle, implementiert separaten Verkettung. Jetzt können wir besser machen? Alles klar ich letztes Mal versprochen, dass konnten wir konstante Zeit zu erreichen. Und ich Art gab dir konstante Zeit hier, aber dann sagte nicht wirklich konstante Zeit, denn es ist immer noch abhängig von der Gesamt Anzahl der Elemente Sie in der Eingabe sind die Datenstruktur. Aber nehmen wir dies taten. Lassen Sie mich zurück auf den Bildschirm hier. Lassen Sie mich auch projizieren dies hier oben, klar der Bildschirm, und nehme ich dies tat. Angenommen, ich wollte den Namen einfügen Daven in in meine Datenstruktur. 

Deshalb möchte ich einen String einfügen Daven in die Datenstruktur. Was, wenn ich nicht verwenden ein Hash-Tabelle, aber ich benutze etwas, das mehr ist baumartig wie ein Stammbaum, wo Sie einige root an die haben oben und dann Knoten und Blätter dass nach unten und außen zu gehen. Nehmen wir also an, dass ich wollen einfügen Daven in das, was ist derzeit eine leere Liste. Ich werde folgendes tun: Ich bin gehen, um einen Knoten in dieser Familie zu schaffen baumartige Datenstruktur, die aussieht ein wenig wie diese, von denen jede Rechtecke hat, sagen wir, für jetzt 26 Elemente. Und jede der Zellen, in diesem Array wird um den Buchstaben eines Alphabets repräsentieren. 

Insbesondere werde ich behandeln dies ist A, dann B, dann C, dann D, dieser hier. Also das wird wirksam stellen den Buchstaben D. Aber um alle Daven einfügen Namen ich, ein bisschen mehr tun müssen. Also bin ich zuerst zu Hash, so zu sprechen. Ich werde in dem ersten Buchstaben aussehen in Daven was offensichtlich ist ein D, und ich werde zuordnen ein Knoten, der aussieht wie this-- ein großes Rechteck groß genug, um das ganze Alphabet passen. 

Jetzt D durchgeführt wird. Jetzt A. D-A-V-E-N ist das Ziel. So jetzt, was ich tun werde, ist dies. Sobald ich begann D Ankündigung es gibt keine Zeiger gibt. Es ist Müll Werte in dem Moment, oder ich könnte es zu initialisieren auf null. Aber lassen Sie mich weitermachen mit diese Idee zum Bau eines Baumes. Lassen Sie mich zuordnen einem anderen dieser Knoten, die 26 Elemente in sich hat. 

Und wissen Sie was? Ist dies nur ein Knoten im Speicher, Ich mit malloc erstellt, unter Verwendung einer struct wie wir bald sehen werden, Ich werde this-- tun Ich werde einen Pfeil aus ziehen die Sache, die D unten dargestellt zu diesem neuen Knoten. Und nun zunächst der nächste Brief in Daven Namen, V-- D-A-V-- Ich werde weitermachen und zeichnen Sie einen weiteren Knoten wie diese, wobei die V-Elemente hier, die wir werden für instance-- hoppla ziehen. Wir werden dort nicht zeichnen. Es wird hier zu gehen. 

Dann sind wir zu gehen halten dies für V. sein Und dann hier unten sind wir zum Index gehen unten von V in das, was wir E. betrachten Und dann von hier aus sind wir zu gehen gehen einen dieser Knoten hier. Und jetzt haben wir eine Frage zu beantworten. Ich muss irgendwie zeigen, dass Wir sind am Ende der Zeichenfolge Daven. So konnte ich lass es einfach null. 

Aber was, wenn wir Daven auch den vollständigen Namen, die ist, wie wir gesagt haben, Davenport? So was, wenn Daven ist eigentlich ein Teilstring, ein Präfix eines viel längeren Schnur? Wir können nicht nur dauerhaft sagen nichts los ist dorthin zu gehen, weil wir nie ein Wort wie Davenport einfügen in dieser Datenstruktur 

Also, was wir tun könnten, ist stattdessen behandeln jedes dieser Elemente als vielleicht mit zwei Elemente innerhalb von ihnen. Einer ist ein Zeiger tatsächlich wie ich getan habe. So wird jede dieser Boxen ist nicht nur eine Zelle. Aber was, wenn die Besten one-- der Boden irgendjemandes gehen null zu sein, denn es gibt keine Davenport nur noch. Was ist, wenn das oberste ist einige spezielle Wert? Und es geht, ein wenig schwer, es zu dieser Größe zu zeichnen. Aber angenommen, es ist nur ein Häkchen. Überprüfen. D-A-V-E-N ist ein String in dieser Datenstruktur. 

Inzwischen, wenn ich mehr Platz hatte hier, ich P-O-R-T tun konnte, und ich konnte Prüfung im Knoten setzen daß den Buchstaben T am Ende. Das ist also ein massiv komplexe gerichtete Datenstruktur. Und meine Handschrift sicherlich nicht helfen. Aber wenn ich wollte etwas einfügen anderes, überlegen, was wir tun würden. Wenn wir David in stellen wollte, wir würden die gleiche Logik, D-A-V folgen, aber jetzt möchte ich in den nächsten Punkt Element nicht aus E, sondern von I bis D. Also es geht um sein mehrere Knoten in diesem Baum. Wir werden Call malloc mehr. Aber ich möchte nicht eine zu machen komplettes Chaos dieses Bildes. Also lassen Sie uns stattdessen auf einen Blick das ist vorformuliert worden wie diese mit nicht Punkt, Punkt, Punkte, sondern nur abgekürzt Arrays. Aber jeder der Knoten In diesem Stammbaum hier stellt das gleiche thing-- ein Array Ray von Größe 26. 

Oder wenn wir sein wollen wirklich richtige jetzt, was wenn jemand den Namen als ein Apostroph, lassen Sie uns davon ausgehen, dass jeder Knoten tatsächlich wie 27 Indizes in ihm, nicht nur 26. Also das jetzt wird ein Daten sein Struktur genannt trie-- T-R-I-E. Ein Trie, die angeblich historisch ein cleverer Name für einen Baum das ist für eine optimierte Abrufen, welche natürlich mit einem I-E geschrieben, so ist es Trie. Aber das ist die Geschichte des Trie. 

Also ein Trie ist diese baumartige Daten Struktur wie ein Familienstammbaum dass letztlich verhält sich wie das. Und hier ist ein weiteres Beispiel für ein ganze Reihe von Namen anderer Leute. Aber die Frage ist jetzt bei der Hand ist, was haben gewannen wir durch die Einführung wohl eine komplizierte Datenstruktur, und eine, ehrlich gesagt, verwendet, dass eine Menge Speicher. 

Denn auch wenn, im Moment bin ich nur mit D's Zeiger und A und V und E und Ns, Ich vergeude ein Heck viel Speicher. Aber wo ich verbringe eine Ressource, Ich neige dazu, nicht zurück ein anderes zu gewinnen. Also, wenn ich mehr Platz zu verbringen, was ist wohl die Hoffnung? Dass ich weniger ausgeben, was? PUBLIKUM: Weniger Zeit. DAVID MALAN: Zeit. Nun, warum könnte das sein? Nun, was ist das Einfügen Zeit, in nun Bezug auf große O, von einem Namen wie Daven oder Davenport oder David? Nun, das war Daven fünf Schritten. Davenport würde neun Stufen sein, so wäre es ein paar Schritte weiter sein. David würde fünf Schritte als gut. Also diejenigen Beton Zahlen, aber sicherlich gibt es auf dem eine obere Schranke Länge des Namens jemand. Und in der Tat, in der Problem Sätze von fünf Spezifikation wir werden vorschlagen dass es etwas das ist 40-some-ungeraden Zeichen. 

Realistisch gesehen, niemand hat ein unendlich langer Name, das heißt, daß die Länge a benennen oder die Länge eines Strings könnten wir haben bestimmte der Staat Struktur ist wohl was? Es ist konstant. Richtig? Es könnte eine große Konstante wie sein 40 etwas, aber sie ist konstant. Und es keine Abhängigkeit davon, wie viele hat anderen Namen sind in dieser Datenstruktur. In anderen Worten, wenn I wollte jetzt einfügen Colton oder Gabriel oder Rob oder Zamyla oder Alison oder Belinda oder irgendwelche anderen Namen von den Mitarbeitern in diesen Daten Struktur, ist die Laufzeit Einfügen von anderen Namen in Zukunft an allen betroffen sein durch, wie viele andere Elemente in der Datenstruktur schon? Es ist nicht. Richtig? Weil wir effektiv mit Diese Mehrschicht-Hash-Tabelle. Und die Laufzeit jede dieser Operationen hängt nicht von der Anzahl der Elemente, die in der Datenstruktur sind, oder dass irgendwann gehen die in der Datenstruktur, sondern auf die Länge, was speziell? 

Der String wobei eingesetzt, die machen tut diese asymptotisch konstant Zeit-- Big O von einem. Und ehrlich gesagt, nur in die reale Welt, diese bedeutet Einsetzen Daven Namen hat wie fünf Stufen oder Davenport neun Stufen oder David fünf Schritten. Das ist verdammt kleine Laufzeiten. Und in der Tat, das ist eine sehr gute Sache, vor allem, wenn es ist nicht abhängig von der Gesamt Anzahl der Elemente gibt. Also, wie können wir die einschlägigen Vorschriften des Art der Struktur im Code? Es ist ein wenig mehr komplex, aber es ist immer noch nur eine Anwendung des Grundbausteine. Ich werde neu definieren US-Knoten wie folgt: bool genannt word-- und dies könnte alles heißen. Aber die bool repräsentiert was ich zog als Häkchen. Ja. Dies ist das Ende einer Zeichenfolge in dieser Datenstruktur. 

Und natürlich der Knoten star es ist, Kinder zu beziehen. Und zwar genauso wie ein Stammbaum, Sie würden die Knoten betrachten dass hängen off der Boden etwas Mutter Element, Kinder zu sein. Und damit die Kinder an gehen sein eine Reihe von 27, der 27. ein einfach nur für Apostroph. Wir werden sortieren der Sonderfall, dass. So können Sie bestimmte haben können Namen mit Apostroph. Vielleicht sogar Bindestrich sind gehen dort, aber du wirst sehen in p-Set 5 wir nur Pflege etwa Briefe und Apostrophe. 

Und dann, wie vertreten Sie Die Datenstruktur selbst? Wie vertreten Sie die Wurzel dieser Trie sozusagen? Nun, genau wie bei einer verketteten Liste, die Sie benötigen einen Zeiger auf das erste Element. Mit einem Trie Sie brauchen nur eine Zeiger auf die Wurzel dieser Trie. Und von dort aus hash kann Ihren Weg nach unten tiefer und tiefer zu jedem anderen Knoten in der Struktur. Also einfach mit diesem Dosen wir vertreten, dass struct. 

Jetzt Meanwhile-- Oh, Frage. 

PUBLIKUM: Was ist bool Wort? 

DAVID MALAN: Bool Wort ist gerade diese C Inkarnation von dem, was ich beschrieben in diesem Feld hier, wenn Ich begann die Aufteilung jeder der Elemente Arrays in zwei Stücke. Einer ist ein Zeiger zu dem nächsten Knoten. Das andere zu sein so etwas wie ein Kontrollkästchen ja zu sagen, es gibt eine Wort Daven, die hier endet, weil wir nicht wollen, in dem Moment, Dave. 

Obwohl Dave wird eine sein legitime Wort, er ist nicht in der Trie noch. Und D ist nicht ein Wort. Und D-A ist nicht ein Wort oder einen Namen. Also das Häkchen zeigt nur, wenn Sie traf dieser Knoten der früheren Weg der Zeichen eigentlich eine Zeichenfolge, die Sie eingefügt haben. Also das ist alles, die bool es für uns tut. 

Alle anderen Fragen auf versucht? Ja. 

PUBLIKUM: Was ist die Überlappung? Was, wenn Sie ein Dave und Daven haben? DAVID MALAN: Perfect. Was, wenn Sie ein Dave und Daven haben? Also, wenn wir stecken, sagen, ein Spitzname, für David-- Dave-- D-A-V-E? Das ist eigentlich super einfach. Also werden wir nur gehen, um vier Schritte zu unternehmen. D-A-V-E. Und was muss ich tun, wenn ich auf diesen vierten Knoten? Gerade dabei, zu überprüfen. Wir sind schon gut zu gehen. Fertig. Vier Schritte. Konstante Zeit asymptotisch. Und jetzt haben wir, dass sowohl Dave angegeben und Daven sind Strings in der Struktur. So kein Problem. Und merken, wie das Vorhandensein von Daven hat es nicht geschafft keine Zeit mehr oder weniger nehmen Zeit für Dave und umgekehrt. 

Also, was können wir sonst noch tun? Wir haben diese Metapher vor verwendet von Schalen, die etwas darstellt. Aber es stellt sich heraus, dass ein Stapel von Ablagen ist eigentlich demonstrative eines anderen abstrakten Daten Typ-- eine höhere Datenstruktur dass am Ende des Tages ist nur wie ein Array oder eine verkettete Liste oder etwas banal. Aber es ist ein interessanter konzeptionellen Konzept. Ein Stapel, wie diese Rinnen hier in Mather, werden allgemein als nur dass-- einen Stapel. 

Und bei dieser Art von Datenstruktur, Sie zwei operations-- haben Sie nannte man Push für haben Hinzufügen etwas auf den Stapel, wie wenn man ein anderes Fach wieder auf die Spitze des Stapels. Und dann Pop, der Sie bedeutet nehmen Sie die oberste Schale ab. Aber was ist Schlüssel zu einem Stapel ist, dass es hat diese merkwürdige Charakteristik. Als Speisesaal Personal Neuanordnung der Schalen für die nächste Mahlzeit, was los zu sein wahr, wie Studenten interagieren mit dieser Datenstruktur? PUBLIKUM: Sie werden einmalige Pop. DAVID MALAN: Sie sind zu gehen Pop einmalige, hoffentlich die Spitze. Sonst ist es nur irgendwie dumm den ganzen Weg auf den Grund gehen. Richtig? Die Datenstruktur nicht wirklich erlauben Sie die Bodenwanne mindestens greifen leicht. Also gibt es diese merkwürdige Eigenschaft auf einem Stapel dass das letzte Element in ist werde das erste aus sein. Und Informatiker nennen dies LIFO-- in erster dauern, heraus. Und es tatsächlich funktioniert haben interessante Anwendungen. Es ist nicht unbedingt so offensichtlich wie einige anderen, aber es kann in der Tat nützlich sein, und es kann in der Tat umgesetzt werden in einer Reihe von verschiedenen Möglichkeiten. 

So ein, und tatsächlich lassen mich nicht in diesen Tauchgang. Lassen Sie uns dies tun, statt. Schauen wir uns ein, die fast das ist gleiche Idee, aber es ist ein wenig gerechter. Richtig? Wenn Sie eines dieser Fan Jungen sind oder Mädchen, die wirklich mag Apple-Produkte und Sie um 3:00 Uhr aufgewacht irgend store antreten um die neuesten iPhone zu bekommen, können Sie könnte sich wie diese eingereiht haben. 

Jetzt eine Warteschlange ganz bewusst benannt. Es ist eine Linie, weil es einige Fairness zu. Richtig? Es wäre irgendwie angesaugt, wenn Sie noch war zuerst da im Apple Store aber man effektiv die unterste sind Fach, da die Apple-Mitarbeiter dann Pop die letzte Person, die tatsächlich im Einklang stand. So Stacks und Warteschlangen, obwohl funktional sind sie Art des same-- es ist nur diese Sammlung von Ressourcen, das ist werde wachsen und shrink-- es gibt diese Fairness Aspekt, um es, zumindest in der realen Welt, wo die Operationen, die Sie ausüben unterscheiden sich grundlegend. Ein stack-- eine Warteschlange rather-- soll gesagt haben zwei Operationen: n Warteschlange und d Warteschlange. Oder Sie können sie anrufen jede Anzahl von Dingen. Aber Sie wollen einfach nur zu erfassen die Vorstellung, dass man die Zugabe und man schließlich Subtraktion. 

Jetzt unter der Haube, die beide der Stapel und eine Warteschlange könnte umgesetzt werden, wie? Wir werden nicht in die Box zu gehen weil die höhere Idee ist eine Art offensichtlicher. Ich meine, was die Menschen tun? Wenn ich die erste Person auf der Apple Bewahren und das ist die Haustür, Sie wissen, ich werde hier stehen. Und die nächste Person hier stehen. Und die nächste Person hier stehen. Also, was Datenstruktur eignet sich für eine Warteschlange? 

PUBLIKUM: Eine Warteschlange. DAVID MALAN: Nun, eine Warteschlange. Sicher. Was sonst? 

PUBLIKUM: Eine verkettete Liste. 

DAVID MALAN: Ein verknüpftes Liste Sie implementieren könnte. Und eine verkettete Liste ist nett, weil dann es beliebig lang werden kann, im Gegensatz um mit einigen festen Anzahl der Menschen in den Laden. Aber vielleicht eine feste Anzahl der Plätze ist legitim. Denn wenn sie nur wie 20 iPhones am ersten Tag, vielleicht sie müssen nur ein Array der Größe 20, dass die Warteschlange stellen die erst jetzt zu sagen, sobald wir anfangen zu sprechen zu diesen höheren Probleme Ebene Sie können es umsetzen in einer beliebigen Anzahl von Möglichkeiten. Und es ist wahrscheinlich gerade dabei, sein einen Kompromiss in Raum und Zeit oder einfach nur in Ihrem eigenen Code Komplexität. 

Was ist mit einem Stapel? Nun, ein Stapel, auch wir gesehen haben könnte gerade diese Fächer sein. Und man könnte dies ein Array implementieren. Aber irgendwann, wenn Sie ein Array verwenden, was los ist, um zu den Tabletts passieren Sie versuchen, zu legen? In Ordnung. Sie sind nur gehen, um in der Lage, so hoch zu gehen. Und ich denke, in Mather sie tatsächlich in dieser Öffnung ausgespart ist. Also ja, es ist fast wie Mather wird mit ein Array mit fester Größe, Da Sie nur passen so viele Schalen in dieser Öffnung in die Wand unten Knie der Menschen. Und damit auch sein mag sagte ein Array sein, aber wir könnten sicherlich umsetzen, dass allgemein mit einer verknüpften Liste. 

Nun, was ist mit anderen Datenstruktur? Lassen Sie mich nach oben ziehen ein anderer visueller hier. So etwas wie diesen hier? Warum könnte es sinnvoll sein, nicht etwas so schick wie ein Trie, die sahen wir hatten diese sehr breiten Knoten, von denen jede in einem Array? Aber was, wenn wir etwas tun, mehr einfach, wie ein alter Schulstammbaum, jeder, dessen Knoten hier gerade Speichern einer Nummer. Statt einem Namen oder einem Abkömmling gerade Speichern einer Nummer wie diese. 

Nun, der Jargon, die wir in Datenstrukturen ist beide Versuche und Bäumen, wo ein Trie ist wieder nur einer, dessen Knoten-Arrays, ist immer noch, was Sie vielleicht Verwenden von der Grundschule wenn Sie eine Familie haben tree-- Blätter und die Wurzel des Baumes und die Kinder des Eltern und Geschwister davon. Und wir könnten einen Baum zu implementieren, zum Beispiel so einfach wie diese. Ein Baum, wenn er als ein Knoten, eines diese Kreise, die eine Reihe hat, es ist nicht zu haben, einen Zeiger, sondern zwei. Und sobald Sie hinzufügen ein zweiter Zeiger, Sie tatsächlich jetzt machen sort der zweidimensionalen Daten Strukturen im Speicher. Ähnlich wie eine zweidimensionale Array, können Sie haben Art von zweidimensionalen verkettete Listen, sondern diejenigen, dass ein Muster folgen wo es keine Zyklen. Es ist wirklich ein Baum mit einem Großeltern Weg bis hier und dann einige Eltern und Kinder und Enkel und Urenkel. und so weiter. 

Aber was ist wirklich ordentlich darüber zu, nur, um Ihnen mit ein bisschen Code zu necken, Rückruf Rekursion aus eine Weile zurück, wobei Sie eine Funktion, die sich selbst aufruft. Dies ist eine schöne Gelegenheit, um etwas umzusetzen wie Rekursion, denn darüber nachzudenken. 

Dies ist ein Baum. Und ich habe schon ein wenig anal mit, wie Ich habe die ganzen Zahlen auf die Straße. So sehr, dass es eine spezielle hat name-- einen binären Suchbaum. Jetzt haben wir von binären gehört suchen, aber können Sie Arbeit nach hinten vom Namen dieses Ding? Was ist das Muster, wie I eingefügt die ganzen Zahlen in diesem Baum? Es ist nicht willkürlich. Es gibt einige Muster. Ja. 

PUBLIKUM: Kleinere auf der linken Seite. 

DAVID MALAN: Yeah. Kleineren sind auf der linken Seite. Größeren sind auf der rechten Seite. So dass eine wahre Aussage ist eine Mutter größer ist als seine linke Kind, aber weniger als seine rechte Kind. Und das allein ist selbst ein rekursive verbale Definition weil Sie, dass gelten elbe Logik jedem Knoten und es ist nur Sumpf heraus, eine Basis Fall, wenn Sie wird, wenn Sie eine der Hit die Blätter, sozusagen wo ein Abschied hat keine Kinder weiter. 

Nun, wie könnte man die Zahl 44 zu finden? Sie würden an der Wurzel beginnen und sagen, hm. 55 ist nicht 44 Also will ich gehen rechts oder will ich nach links gehen? Nun, offensichtlich möchten Sie links. Und so ist es nur wie das Telefon Buchbeispiel in binäre Suche allgemeiner. Aber wir Umsetzung jetzt ein wenig mehr dynamisch als ein Array könnte ermöglichen. Und in der Tat, wenn Sie wollen aussehen auf den Code, auf den ersten Blick klar. Es sieht aus wie eine ganze Reihe von Linien. Aber es ist schön einfach. Wenn Sie eine Funktion implementieren möchten genannt Suche, deren Zweck im Leben ist es, nach einem Wert suchen wie n eine ganze Zahl ist, und Sie in einer Eins pointer-- vergangen sind ein Zeiger zu dem Knoten der Wurzeln, vielmehr jenes Baumes, aus dem Sie alles andere zugreifen können, merken, wie unkompliziert Sie können die Logik zu implementieren. Wenn Baum ist null, offensichtlich ist es nicht da. Lass uns einfach return false. Richtig? Wenn Sie geben es nichts, dort nichts zu finden. 

Sonst, wenn n kleiner ist Baum Pfeil N- jetzt arrow n, erinnern wir uns vorgestellt Super kurz den anderen Tag, und das bedeutet, nur de-Referenz die Zeiger und Blick auf die Feld namens n. So bedeutet es gehen dort und Blick auf das Feld genannt n. Also, wenn n der Wert euch gegeben sind, ist weniger als der Wert in der Baum integer, Wohin möchten Sie reisen? Nach links. 

So bemerken die Rekursion. Ich returning-- nicht wahr. Nicht falsch. Ich bin zurück was die Antwort ist von einem Aufruf mich, vorbei eine n wieder, die redundante ist, aber was ist jetzt etwas anders? Wie mache ich das Problem kleiner? Ich bin vorbei, die als zweiter Argument, nicht die Wurzel des Baumes, aber das linke Kind in diesem Fall. Also ich bin vorbei im linken Kind. 

Inzwischen, wenn n größer ist als der Knoten Ich bin derzeit auf der Suche bei, Ich suche die rechte Seite. Andernfalls, wenn der Baum nicht null ist, und wenn das Element ist nicht auf die linke und es ist nicht nach rechts, was ist wunderbar der Fall? Wir haben tatsächlich festgestellt, die Knoten in Frage, und so kehren wir wahr. 

Also haben wir nur an der Oberfläche gekratzt jetzt einige dieser Datenstrukturen. In Problem stellte fünf du wirst erkunden diese noch weiter, und Sie werden Ihr Design gegeben werden Wahl, wie um dies zu realisieren. Was möchte ich zu dem Schluss, auf ist nur ein 30 Sekunden Teaser von dem, was erwartet nächste Woche und darüber hinaus. 

Wie wir begin-- Glück Dir evtl. think-- langsam unseren Übergang aus der Welt von C und Unter Implementierungsebene Einzelheiten zu einer Welt, in der wir für selbst selbstverständlich, dass jemand anderes hat endlich diese Daten umgesetzt Strukturen für uns, und wir beginnen, das zu verstehen, realen Welt mittels Durchführungs Web-basierte Programme und Webseiten allgemeiner und auch die sehr sicherheits Auswirkungen, die wir nur haben begonnen, um die Oberfläche zu zerkratzen. Hier ist, was uns erwartet in den kommenden Tagen. 

[VIDEO PLAYBACK] 

-Er Kam mit einer Botschaft, mit einem Protokoll alle seine eigenen. Er kam in eine Welt der grausamen Firewalls, gefühllos Router, und Gefahren weit schlimmer als der Tod. Er ist schnell. Er ist stark. Er ist TCP / IP, und er ist Ihre Adresse bekam. "Warriors of the Net". [END VIDEO PLAYBACK] DAVID MALAN: Nächste Woche. Wir werden Sie dann sehen. [VIDEO PLAYBACK] -Und Jetzt, "Deep Thoughts" durch Daven Farnham. -David Beginnt immer Vorlesungen mit: "In Ordnung." Warum nicht: "Hier ist die Lösung in dieser Woche das Problem set " oder "Wir geben euch alle ein A?" [Lacht] [END VIDEO PLAYBACK]