[Musikwiedergabe] 

ANDI PENG: Willkommen in Woche 6 des Abschnitts. Wir abweichend von unseren Standard Abschnitt Zeit vom Dienstag Nachmittag zu diesem schönen Sonntagmorgen. Vielen Dank für alle, begleitete mich heute, aber im Ernst, eine Runde Applaus. 

Das ist ein ziemlich großer Aufwand. Ich habe fast gar nicht machen es up in der Zeit, aber es war ok. Also ich weiß, dass ihr alle habe gerade es zum Quiz gemacht. Zunächst einmal, herzlich willkommen auf die Kehrseite, dass. 

Zweitens werden wir darüber reden. Wir werden über das Quiz zu sprechen. Wir werden darüber sprechen, wie Sie in der Klasse tust. Alles wird gut. Ich habe deinen Quizfragen für man am Ende des hier also, wenn Sie Jungs wollen nehmen einen Blick auf sie, völlig in Ordnung. 

So schnell, bevor wir beginnen, die Tagesordnung für heute ist wie folgt. Wie Sie sehen können, sind wir im Grunde Schnellbrand durch eine ganze Reihe von Datenstrukturen wirklich, wirklich, wirklich schnell. So als solches wird es nicht Super interaktive heute. Es wird nur sein, mich Art von Schreien Dinge, die Sie, und wenn ich verwirren, wenn ich zu schnell, lass es mich wissen. Sie sind nur verschiedene Daten Strukturen und als Teil Ihrer pset dafür kommenden Woche, werden Sie gebeten, eine von ihnen zu implementieren, vielleicht zwei them-- zwei davon in Ihrer pset. OK, ich werde einfach beginnen mit einigen Ankündigungen. Wir werden über Stacks und Warteschlangen mehr gehen Tiefe als das, was wir vor dem Quiz taten. Wir gehen über verlinkt Liste erneut noch einmal, mehr in die Tiefe, als Wir hatten vor dem Quiz. Und dann werden wir über Hash sprechen Tabellen, Bäume und versucht, die sind alle für Ihre pset ziemlich nötig. Und dann werden wir über einige gehen hilfreiche Tipps für pset5. 

OK, so Quiz 0. Die durchschnittliche war ein 58%. Es war sehr niedrig, und schauen Sie sich die Jungs alle hat sehr, sehr gut im Einklang damit. 

Ziemlich viel, ist Faustregel gilt, wenn Sie innerhalb einer Standardabweichung des Mittelwertes zumal wir in einer weniger sind Bequeme Abschnitt, du bist völlig in Ordnung. Du bist auf dem richtigen Weg. Das leben ist gut. 

Ich weiß, es ist erschreckend zu denken, dass Ich stand wie eine 40% in diesem Quiz. Ich werde diese Klasse scheitern. Ich verspreche Ihnen, Sie sind nicht gehen, um die Klasse scheitern. Sie sind völlig in Ordnung. 

Für diejenigen unter Ihnen, die überstanden die mittlere, eindrucksvoll, beeindruckend, wie ernst gut gemacht. Ich habe sie mit mir. Fühlen Sie sich frei zu kommen, bekommen sie am Ende der Seite. Lassen Sie mich wissen, wenn Sie welche haben Fragen, Fragen mit ihnen. Wenn wir hinzufügen, Ihre Punktzahl falsch, lass es uns wissen. 

OK, so pset5, ist dies ein wirklich seltsame Woche für Yale in dem Sinne, dass unsere pset fällig ist Mittwochmittag einschließlich der späte Tag, so dass es tatsächlich theoretisch aufgrund Dienstag um die Mittagszeit. Wohl niemand fertig am Dienstag um die Mittagszeit. Das ist völlig in Ordnung. Wir werden Bürozeiten haben heute Abend als auch am Montagabend. Und alle Abschnitte in dieser Woche tatsächlich in Workshops eingeschaltet werden, so zögern Sie nicht in Pop- Jeder Abschnitt die Sie wollen, und sie werden Art Mini-pset sein Workshops für die Hilfe auf, dass. So solches ist dies der einzige Abschnitt wo wir Lehrmaterial. Alle anderen Abschnitte werden mit Schwerpunkt ausschließlich auf die Hilfe für die pset. Ja? 

ZIELGRUPPE: Wo sind Bürozeiten? 

ANDI PENG: Bürozeiten tonight-- oh, gute Frage. Ich denke, dass der Bürozeiten heute Abend sind in Teal oder Commons. Wenn Sie Online-CS50 überprüfen und gehen Sie zu Bürozeiten, es sollte ein Zeitplan sein, dass sagt Ihnen, wo sie alle sind. 

Ich weiß, entweder heute Abend oder morgen ist blaugrün, und ich denke, wir haben kann commons für die andere Nacht. Ich bin mir nicht sicher. Gute Frage. Prüfen Sie am CS50. 

Cool, Fragen hinsichtlich der Zeitplan für die nächste wie drei Tage? Ich verspreche Ihnen, Leute wie David sagte, das ist die Spitze des Hügels. Sie Kerle sind fast da. Nur noch drei Tage. Holen Sie sich dort, und dann werden wir alle unten kommen. Wir haben eine schöne CS-freie Pause. Willkommen zurück. Wir werden in Web tauchen Programmierung und Entwicklung, Dinge, die sehr lustig sind im Vergleich um einige der anderen psets. Und es wird Chill sein und wir haben viel Spaß. Wir werden mehr Süßigkeiten zu haben. Sorry für Süßigkeiten. Ich habe vergessen, Süßigkeiten. Es war eine grobe Morgen. So euch fast dort sind, und ich bin wirklich stolz auf euch. 

OK, so stapelt. Wer liebte die Frage zu Jack und seine Kleidung auf das Quiz? Niemand? OK Das passt. 

So im Wesentlichen, wie Sie können Bild Jack, dieser Kerl hier, liebt es, die Kleidung zu nehmen aus der Oberseite des Stapels, und er es wieder auf der Stapel, nachdem er getan hat. Also auf diese Weise, hat er nie scheint sich immer an der Unterseite des Stapel in seiner Kleidung. Also diese Art der beschreibt, die grundlegende Datenstruktur wie ein Stapel implementiert wird. 

Im Wesentlichen, denken Sie an ein stapeln wie jedes Stapels von Gegenständen wo Sie die Dinge auf die Spitze, und dann können sie Pop aus der Oberseite. Also LIFO ist die Abkürzung uns gefällt um use-- Last In, First Out. Und so halten, um die Oberseite des Stack ist die erste, die herauskommt. Und so sind die beiden Begriffe möchten wir assoziieren Mit dieser werden Push- und Pop bezeichnet. Wenn Sie etwas zu drücken auf die stapeln, und Sie es Pop wieder auf. 

Und so Ich denke, das ist ein bisschen ein abstraktes Konzept für die von Ihnen die wollen, um wie ein zu sehen tatsächliche Umsetzung dieser in der realen Welt. Wie viele von euch haben einen Aufsatz geschrieben vielleicht wie eine Stunde, bevor es auf Grund, und Sie versehentlich eine riesige gelöscht Stück davon, wie aus Versehen? Und was dann Steuer tun wir verwenden, um ihn wieder? Strg-Z, yeah? Strg-Z, so dass die Höhe der Zeit dass Ctrl-Z hat mir das Leben gerettet, hat meinen Arsch jedes Mal gespeichert, das ist durch einen Stapel implementiert. 

Im Wesentlichen alle Informationen das ist auf Ihrem Word-Dokument, Es wird aufgeschoben und am Willen tauchte. Und so im Wesentlichen, wenn Sie alles löschen, knallen Sie ihn wieder auf. Und dann, wenn Sie es auf der Rückseite benötigen, schieben Sie es, das, was Sie Strg-C tut. Und so realen Welt Funktion wie einfache Datenstruktur kann mit Ihrem täglichen Leben zu helfen. 

So eine Struktur ist der Weg, wir tatsächlich ein Stapel. Wir geben zu definieren Struktur, und dann wir nennen es am Boden zu stapeln. Und innerhalb des Stapels, wir haben zwei Parameter dass wir im Wesentlichen manipulieren kann, so haben wir char Sterne Saiten Kapazität. 

Alles, was sie tut, wird ein Array dass wir speichern können, was Sie wollen die wir die Kapazität bestimmen. Kapazität ist nur die maximale Anzahl von Artikel können wir in diesem Array setzen. int size ist der Zähler, der hält verfolgen, wie viele Artikel sind derzeit in dem Stapel. So können wir verfolgen, A zu halten, sowohl, wie groß die aktuelle Stapel, und B, wie viel von diesem Stapel wir gefüllt, weil wir nicht wollen, zum Überlaufen über das, was unsere Kapazität ist. 

So zum Beispiel, dieses schöne Frage war, auf Ihrem Quiz. Im wesentlichen wie können wir schieben auf die Oberseite eines Stapels. Ziemlich einfach. Wenn man es betrachtet, wir werden über diese zu gehen. Wenn [unverständlich] size-- denken Sie daran, wenn Sie möchte jeder Zugriff Parameter innerhalb einer Struktur, Sie den Namen des struct.parameter zu tun. 

In diesem Fall wird S der Name unseres Stack. Wir wollen die Größe zugreifen davon, so wir tun s.size. So lange, wie die Größe nicht gleich Kapazität oder, sofern da es weniger als Kapazität, entweder würde hier zu arbeiten. 

Sie wollen, um das Innere zugreifen Ihr Stack, so s.strings, und du wirst diese neue Nummer einsetzen werden , die Sie in es eingefügt werden soll. Sagen wir einfach, wir werden zu wollen, einfügen int n auf den Stapel, wir s.strings tun konnte, Klammern, gleich s.size n. Da Größe ist, wo wir Zur Zeit sind in der Stapel wenn wir zu schieben sie auf, wir haben nur Zugriff wo die Größe ist, die Strom Fülle des Stapels, und wir drücken Sie den int n auf sie. Und dann dafür sorgen, dass wir wollen Wir sind auch Inkrementieren Größe der n, also können wir verfolgen, wir haben hinzugefügt eine zusätzliche Sache, um den Stapel. Jetzt haben wir eine größere Größe. Bedeutet dies hier sinnvoll, jeder, wie logisch funktioniert es? Es war irgendwie schnell. ZIELGRUPPE: Können Sie übergehen die s.stringss.strings [s.size] noch einmal? ANDI PENG: Sicher, so was macht s.size uns noch geben? Publikum: Es ist die aktuelle Größe. ANDI PENG: Genau, so dass die aktuellen Index, der unserer Größe ist, und so, um die neue Ganzzahl setzen wollen wir dass wir wollen in s.size einfügen. Ist das sinnvoll? Weil s.strings, alles, was ist der Name des Arrays. Alles, was es ist, den Zugriff auf die Array innerhalb unserer Struktur, und so, wenn wir wollen platzieren n in diesem Index, wir können einfach darauf zugreifen mit Klammern s.size. Cool. 

In Ordnung, pop, Pseudo ich es aus für euch, aber ähnliches Konzept. Ist das sinnvoll? Wenn die Größe größer ist als Null ist, dann wissen, dass Sie etwas machen wollen aus, weil, wenn die Größe nicht größer als Null ist, dann haben nichts in dem Stapel. 

Also nur ausführen wollen Sie nur dieser Code, kann es pop, wenn es etwas zu Pop. Also, wenn die Größe größer ist als 0 ist, wir abzüglich der Größe. Wir verringern die Größe und dann wieder was auch immer in der es aufgrund nach knallen, wir wollen Zugang, was gespeichert wird, in dem Index der Oberseite des Stapels. Alles, was sinnvoll? Wenn ich euch dies schreiben, würde euch in der Lage, es zu schreiben, sein? OK, Jungs können spielen, um mit ihm. Keine Sorge, wenn Sie nicht bekommen. Wir haben keine Zeit, um zu kodieren es aus heute, weil wir bekam viele dieser Strukturen zu durchlaufen, aber im Wesentlichen Pseudocode, sehr, sehr ähnlich zu schieben. Folgen Sie einfach entlang der Logik. Stellen Sie sicher, Sie zugreifen, alle Funktionen Ihres struct richtig. Ja? 

ZIELGRUPPE: werden diese Folien und diese ganze Sache bis heute-ish sein? ANDI PENG: Immer, yep. Ich werde versuchen, setzen Diese oben wie nach einer Stunde. Ich werde David mailen, David zu versuchen stellen Sie sie wie eine Stunde danach. 

OK, so dass dann in diesem anderen bewegen wir uns lovely Datenstruktur namens eine Warteschlange. Wie euch kann hier sehen, ein Warteschlange, für die Briten unter uns, allem ist es eine Linie ist. So anders als Sie denken, ein Stapel ist, eine Warteschlange Genau logisch denken Sie es ist. Es ist nach den Vorschriften des FIFO gehalten, Das ist First In, First Out. Wenn Sie der erste sind eine in der Linie, du bist Der erste, kommt aus der Leitung. 

Also, was wir zu dieser Aufforderung wird dequeueing und Einreihen. Wenn wir etwas hinzufügen wollen, unsere Warteschlange einzureihen wir. Wenn wir aus der Warteschlange entfernt, oder nehmen etwas weg, aus der Warteschlange entfernt wir. 

So gleichen Sinne, dass wir Art sind Schaffung fester Größe Elemente, die wir können sicher speichern Dinge, aber wir können auch zu ändern, wo wir platzieren Parameter innerhalb von ihnen basierend auf welche Art von Funktionalität wollen wir. So Stacks, die zuletzt wollten wir einem, N, um die erste, aus zu sein. Warteschlange wollen wir das erste, was um das erste, was Sie können. 

So der Strukturtyp zu definieren, wie Sie sehen können, es ist ein bisschen anders von dem, was der Stapel war weil nicht nur müssen wir halten verfolgen, wo die Größe derzeit ist, wir wollen auch den Überblick über den Kopf zu halten wie auch, wo wir derzeit stehen. Also ich denke, es ist einfacher, wenn ich diese aufzustellen. So stellen wir uns vor, wir haben eine Warteschlange stand, also lassen Sie uns sagen, der Kopf ist hier richtig. Der Kopf der Zeile, lassen Sie uns nur sagen, dass es derzeit gibt, und wir einfügen wollen etwas in die Warteschlange. Ich werde Größe Wesentlichen nennen ist das gleiche wie Schwanz, das Ende, wo immer Sie Ihre Warteschlange. Sagen wir einfach, Größe ist hier richtig. 

Also wie kann man durchführbar Einsatz etwas in eine Warteschlange? Welche Index wollen wir platzieren möchten wo wir wollen, in einfügen. Wenn dies der Anfang Ihrer Warteschlange, und dies ist das Ende davon oder die Größe der es, wo wollen wir wollen das nächste Objekt hinzufügen? 

ZIELGRUPPE: [unverständlich] ANDI PENG: Genau, Sie hinzufügen möchten es je nach haben Sie es geschrieben. Entweder ist dieser leer ist oder dass leer ist. So müssen Sie es wahrscheinlich hinzufügen wollen hier, weil, wenn die Größe ist-- wenn es sich um alle voll, Sie wollen die an dieser Stelle hinzufügen, oder? 

Und das ist also, während sehr, sehr einfach, nicht ganz immer korrekt denn der Hauptunterschied zwischen einer Schlange und einem Stapel ist, dass die Warteschlange tatsächlich manipuliert werden so dass der Kopf Änderungen je nachdem, wo Sie wollen der Anfang Ihrer Cue zu starten. Und als ein Ergebnis, deinen Schwanz wird sich auch ändern. Und so einen Blick auf dieser Code jetzt. Wie Sie Jungs waren auch gefragt, schreiben Sie auf dem Quiz, Enqueue. Vielleicht werden wir durch, warum sprechen die Antwort war, was es war. 

Ich nicht ganz passen könnte diese Linie auf der einen, aber im Wesentlichen dieses Stück Code sollte auf einer Linie sein. Verbringen Sie wie 30 Sekunden. Werfen Sie einen Blick und sehen, warum Dies ist die Art, sie ist. 

Sehr, sehr ähnliche Struktur, sehr, sehr ähnliche Struktur wie die vorherige Stapel mit Ausnahme vielleicht eine Zeile Code. Und dass eine Zeile Code bestimmt die Funktionalität. Und es ist wirklich unterscheidet eine Warteschlange von einem Stapel. 

Jeder möchte einen Stich nehmen zu erklären, warum Sie haben, erhielt diese komplizierte Sache hier? Wir sehen die Rückkehr unserer wunderbarer Freund Modul. Wie euch bald kommen um in der Programmierung zu erkennen, fast immer wenn Sie etwas brauchen, um nichts zu wickeln, Modul wird sich die Art und Weise, es zu tun. So wissen, dass dann, wenn jemand will um zu versuchen, zu erklären, dass die Codezeile? Ja, sind alle Antworten akzeptiert und willkommen. ZIELGRUPPE: Sprechen Sie mit mir? ANDI PENG: Ja. ZIELGRUPPE: Oh, keine Entschuldigung. ANDI PENG: OK, also lassen Sie uns Spaziergang durch dieses Codes. Also, wenn Sie versuchen, fügen etwas auf eine Warteschlange, in dem schönen Fall, dass der Kopf passiert, nach rechts hier zu sein, ist es für uns sehr einfach nur bis zum Ende gehen Einsatz etwas, nicht wahr? Aber der springende Punkt bei einer Warteschlange dass der Kopf tatsächlich dynamisch sich ändern, je nachdem, wo wir soll der Beginn unserer q zu sein, und als solche, die Schwanzvene wird sich auch ändern. 

Und so vorstellen, dass dies nicht die Warteschlange, sondern dies der Warteschlange war. Nehmen wir an, der Kopf ist hier richtig. Nehmen wir an, unsere Warteschlange sah wie folgt aus. Wenn wir zu verschieben, wo gesucht der Anfang der Zeile ist, sagen wir, wir verschoben Kopf auf diese Weise und Größen hier. 

Nun, etwas hinzufügen wollen wir diese Warteschlange, aber wie Sie sehen können, Jungs, es ist nicht so einfach wie nur Addieren Sie, was nach der Größe weil dann aus laufen wir Rahmen unserer aktuellen Array. Wo wir wirklich hinzuzufügen ist hier. Das ist die Schönheit einer Warteschlange geht das uns an, es visuell sieht aus wie die Zeile geht so, aber wenn es in einer Datenstruktur gespeichert sind, Sie geben ihm so wie ein Zyklus. Es Art von umschlingt nach vorne genauso dass eine Linie kann auch wickeln rund, je nach wohin Sie will Anfang der Zeile sind. Und so, wenn wir ein schauen Sie hier, lassen Sie uns sagen wir ein schaffen wollte Funktion namens Enqueue. Wir wollten int n in diese q hinzuzufügen. Wenn q.size Q-- wir, dass Sie unsere Daten structure-- wenn unsere queue.size nicht gleich Kapazität oder wenn es ist weniger als Kapazität, q.strings ist das Array innerhalb unserer q. Wir werden festgelegt dass gleich q.heads, Das ist genau hier, zzgl q.size Modul durch die Kapazität, die wickeln wir wieder hier. 

Also in diesem Beispiel, index der Kopf ist 1, oder? Der Index der Größe 0, 1, 2, 3, 4. So können wir 1 plus 4 Modul zu tun unsere Fähigkeit, die 5 ist. Was bedeutet das für uns? Was ist der Index, kommt aus dem? 

ZIELGRUPPE: 0. 

ANDI PENG: 0, die passiert mit Recht hier zu sein, und so zu können wollen wir in hier einfügen. Und so diese Gleichung hier Art der nur arbeitet mit beliebigen Rufnummern je nachdem, wo Sie Ihre Kopf und Ihre Größe sind. Wenn Sie wissen, was diejenigen, Dinge, die Sie wissen, genau dort, wo Sie einfügen möchten was auch immer, nachdem Ihre Warteschlange. Ist das sinnvoll, um alle? 

Ich weiß, dass eine Art Gehirn teaser zumal diese kam in der Zeit nach Ihrer Quiz. Aber hoffentlich alle Jetzt verstehen Deshalb ist diese Lösung oder diese Funktion ist die Möglichkeit, die sie ist. Wer ein wenig unklar dazu? OK. 

Und jetzt, wenn Sie wollte, dies aus der Warteschlange entfernt ist, wo unsere Kopf wäre Verschiebung denn wenn wir aus der Warteschlange entfernt wurden, wir nehmen nicht das Ende der q. Wir wollen weg vom Kopf zu nehmen, nicht wahr? So als Ergebnis wird der Kopf wird sich ändern, Deshalb, wenn Sie einzureihen, Sie haben, um zu verfolgen wo Sie Ihren Kopf und Ihre Größe sind in der Lage, einzufügen in die korrekte Position. 

Und so, wenn Sie aus der Warteschlange entfernt, I Pseudo noch darauf. Zögern Sie nicht, wenn Sie möchten, um zu versuchen, Kodierung this out. Sie wollen den Kopf zu bewegen, oder? Wenn ich wollte, aus der Warteschlange entfernt, I würde den Kopf zu bewegen vorbei. Dies würde der Kopf sein. 

Und unsere aktuellen Größe würde subtrahieren, weil wir nicht mehr vier Elemente in der Anordnung. Wir haben nur drei, und dann wollen wir um zurückzukehren, was wurde gespeichert innen der Kopf, weil wir das machen wollen Wert aus, so sehr ähnlich zu dem Stapel. Nur du nimmst von einem anderen Ort, und Sie Ihre Zeiger neu zuordnen müssen zum anderen Ort als Ergebnis. Logisch, jeder folgen? Groß. 

OK, so dass wir gehen, um ein wenig zu sprechen mehr in die Tiefe zu verknüpften Listen denn sie werden sehr, sehr wertvoll sein, für Sie im Laufe dieser Woche psets. Verkettete Listen, wie Sie Kerle kann mich daran erinnern, was sie sind sind Knoten, die Knoten sicher sind, Werte sowohl einen Wert und einen Zeiger die miteinander verbunden sind von diesen Zeigern. Und so ist die Struktur auf, wie Wir erstellen ein Knoten ist hier wir haben int n, das ist, was auch immer der Wert in einem Geschäft oder String n oder was auch immer Sie wollen, nennen, die char-Sterne-n. Struct node Stern, der sich der Zeiger dass Sie in jedem Knoten haben wollen, Sie gehen zu müssen, dass du Zeiger weisen auf Weiter. Sie werden den Kopf haben einer verketteten Liste, die ist gehen, um für den Rest der Punkt die Werte so weiter und so fort bis Sie irgendwann an das Ende. Und das letzte Knoten ist nur werde nicht über einen Zeiger. Es wird darauf null ist und dass, wenn Sie wissen, dass Sie das getroffen haben Ende der verknüpften Liste ist, wenn Ihre letzten Zeiger nicht auf nichts. 

So werden wir ein bisschen mehr gehen Tiefe darüber, wie würde man vielleicht Suche eine verknüpfte Liste. Denken Sie daran, was sind einige der Nachteile der verketteten Listen Verse ein Array in Bezug auf Suchanfragen. Ein Array können Sie binäre Suche, aber warum kannst du nicht, dass in einer verknüpften Liste zu tun? 

ZIELGRUPPE: Weil sie alle miteinander verbunden, aber man weiß nicht recht, wo [UNVERSTÄNDLICH]. 

ANDI PENG: Ja, genau, so erinnern dass die Brillanz eines Arrays war die Tatsache, dass wir Direktzugriffsspeicher, in dem wenn ich den Wert von index sechs, konnte ich nur sagen Index sechs, geben Sie mir diesen Wert. Und das ist, weil Arrays sind geordnet in einem zusammenhängenden Speicherplatz des Speichers an einem Ort, während Art von verknüpften Listen statistisch, setzt rundum und der einzige Weg, die man finden kann ist durch einen Zeiger, der Ihnen sagt, die Adresse, wo die nächsten Knoten ist. 

Und so als Ergebnis der einzige Weg, um durch eine verkettete Liste zu suchen ist lineare Suche. Weil ich nicht genau wissen, wo der 12. Wert in der verknüpften Liste ist, Ich habe, um die Gesamtheit zu durchqueren dieser verknüpften Liste ein durch eine von dem Kopf zu dem ersten Knoten, mit dem zweiten Knoten zu dem dritten Knoten, den ganzen Weg hinunter, bis ich endlich , wo dieser Knoten ich suche ist. Und so in diesem Sinne, Suche auf einer verknüpften Liste ist immer n. Es ist immer n. Es ist immer in linearer Zeit. 

Und so dass der Code, in dem implementieren wir das, und das ist ein bisschen neu für euch da Sie Jungs haben nicht wirklich über oder jemals gesprochen zu sehen, wie man Zeiger in Suche über Zeiger, so dass wir zu Fuß durch diese sehr, sehr langsam. So bool Suche, rechts, Lassen Sie uns vorstellen, wir wollen, um eine Funktion namens erstellen Suche, die true zurückgibt, wenn Sie einen Wert innerhalb der gelinkten gefunden Liste, und es kehrt andernfalls false. Node-Sterne-Liste derzeit nur der Zeiger auf das erste Element in der verketteten Liste. int n den Wert, den Sie Suche nach in dieser Liste. 

So Knoten Sterne-Zeiger entspricht Liste. Das bedeutet, dass wir die Einstellung und die Schaffung eines Zeigers in diesem ersten Knoten innerhalb der Liste. Jeder mit mir? Also, wenn wir waren zu gehen wieder hier, würde ich initialisiert einen Zeiger, der auf die Punkte der Kopf von was auch immer, dass die Liste ist. 

Und dann, sobald Sie unten hier, während die Zeiger nicht gleich null, damit ist die Schleife in dem wir gehen, um anschließend sein Laufen der Rest unserer Liste, weil das, was passiert, wenn die Maus gleich null? Wir wissen, dass wir have-- 

ZIELGRUPPE: [unverständlich] 

ANDI PENG: Genau, so wissen wir, dass wir haben das Ende der Liste erreicht, oder? Wenn Sie hierher zurück, wobei jeder Knoten sollte zu einem anderen Knoten gerichtet sein und so weiter und so fort bis Sie schließlich getroffen der Schwanz der verknüpften Liste, die einen Zeiger hat, der gerade zeigt nicht irgendwo anders als keine. Und so im Grunde wissen Sie, dass Ihre Liste ist immer noch da oben bis der Zeiger nicht gleich null, denn wenn es null ist gleich, Sie wissen, dass es keine Sachen mehr. 

Das ist also die Schleife, in der wir sind gehen, um die tatsächliche Kategorie. Und wenn die pointer-- sehen Sie, diese Art von Pfeil gibt Funktion? Also, wenn Zeiger auf n, wenn der Zeiger bei n gleich gleich n, so daß bedeutet, wenn der Zeiger, die Sie Suche nach auf dem Ende von jedem Knoten tatsächlich gleich dem Wert ist, Sie suchen, dann Sie wollen, um wahr zu zurückzukehren. Also im Grunde, wenn Sie an einem Knoten sind, dass den Wert, die Sie suchen, Sie wissen, dass Sie gewesen sind Lage, erfolgreich zu suchen. 

Andernfalls setzen wollen Sie Sie den Mauszeiger an den nächsten Knoten. Das ist, was diese Linie hier tut. Pointer gleich Zeiger neben. Jeder sehen, wie das funktioniert? 

Und im wesentlichen wirst du gerade durchqueren die Gesamtheit der Liste, Zurücksetzen Ihres Zeiger jedes Mal, bis Sie schließlich traf das Ende der Liste. Und Sie wissen, dass es keine mehr Knoten zu durchsuchen, und dann können Sie false zurück weil Sie wissen, dass, oh, na ja, wenn ich in der Lage, um zu suchen durch die Gesamtheit der Liste. Wenn in diesem Beispiel, wenn ich wollte, um den Wert von 10 zu suchen, und ich fange an der Spitze, und Ich suche den ganzen Weg hinunter, und ich bekam schließlich dazu, die ein Zeiger, der auf null Punkte, Ich weiß, dass, Mist, ich denke, 10 ist nicht in diese Liste, weil ich konnte ihn nicht finden. Und ich bin am Ende der Liste. Und in dem Fall, dass Sie wissen, Ich werde return false. 

Lassen Sie das Bad in für ein wenig. Das wird schön sein wichtig für Ihre pset. Die Logik ist es sehr einfach, vielleicht syntaktisch einfach umzusetzen. Ihr Jungs wollen Sie sicher, dass Sie verstehen. Cool. 

OK, so wie wir wäre Einfügen von Knoten, rechts, in eine Liste, da erinnern was sind das, was von den Vorteilen der mit einer verknüpften Liste Vergleich ein Array in Bezug auf die Lagerung? 

ZIELGRUPPE: Es ist dynamisch, so ist es einfacher zu-- 

ANDI PENG: Genau, es ist also dynamisch, was bedeutet, dass es zu erweitern und schrumpfen kann je nach den Bedürfnissen des Benutzers. Usw., in diesem Sinne, brauchen wir nicht um unnötige Speicher verschwenden, weil ich wenn ich nicht weiß, wie viele Werte Ich möchte zu speichern, ist es nicht sinnvoll für mich um ein Array zu erstellen, weil wenn ich 10 Werte speichern und ich erstellen ein Array von 1000, das ist, viel Speicher verschwendet, zugeteilt. Deshalb haben wir, um zu verwenden ein verknüpftes möchten Liste, um in der Lage zu sein, dynamisch zu ändern oder zu verkleinern unserer Größe. 

Und so, dass das Einführen ein bisschen komplizierter. Da wir nicht nach dem Zufallsprinzip auf Elemente die Art und Weise, dass wir ein Array aus. Wenn ich ein Element einfügen in die siebte Index, Ich kann es einfach einfügen in die siebte Index. Auf einer verknüpften Liste, ist es nicht ganz so einfach zu arbeiten, und so, wenn wir stecken wollte das hier in der verketteten Liste, visuell, es ist sehr leicht zu sehen. Wir wollen einfach nur, um es genau dort einfügen, direkt am Anfang der Liste, direkt nach dem Kopf. 

Aber die Art und Weise, in der wir neu zuweisen die Zeiger ist ein bisschen gewunden oder logisch, ist es sinnvoll, aber Sie sicherstellen, dass Sie es haben wollen ganz nach unten, weil das letzte, was Sie wollen ist es, einen Zeiger zuweisen die Weise, die wir hier tun. Wenn Sie die Dereferenzierung Zeiger vom Kopf bis zu 1, dann plötzlich die Rest der verknüpften Liste ist verloren, weil man eigentlich nicht haben erstellt eine temporäre nichts. Das ist auf die 2 hingewiesen. Wenn Sie den Mauszeiger, dann die neu zuweisen Rest der Liste ist völlig verloren. Also Sie wollen sehr, sehr vorsichtig hier In den ersten zuweisen Zeiger von was auch immer Sie wollen in überall einfügen Sie wollen, und dann kann dereferenzieren den Rest Ihrer Liste. 

So gilt für überall Sie versuchen, in die einzufügen. Falls Sie an der eingefügt werden soll Kopf, wenn Sie hier zu beantworten möchten, ob Sie zu einfügen möchten das Ende, nun ja, das Ende I denke, man würde nur keine Zeiger, aber Sie wollen Sie sicherstellen, dass Sie dies nicht tun verlieren Sie den Rest Ihrer Liste. Sie wollen immer, um sicherzustellen, Ihre neue Knoten zeigen Richtung, was auch immer Sie wollen in einfügen, und dann können Sie die Verkettung auf hinzufügen. Jeder klar? 

Dies wird sein, einer der wirklichen Probleme. Eine der wichtigsten Fragen Wirst du auf pset haben werden ist, dass Sie gehen, um zu versuchen, um zu erstellen sind eine verkettete Liste und Einsatz Dinge aber dann nur verlieren die Rest der verknüpften Liste. Und du wirst sein wie du, ich weiß nicht, warum dies geschieht? Und es ist ein Schmerz zu durchlaufen und suchen Sie alle Ihre Zeiger. 

Und ich garantiere Ihnen auf dieser pset, Schreiben und Zeichnen diese Knoten aus wird sehr, sehr hilfsbereit. So können Sie ganz verfolgen von wo alle Ihre Zeiger sind, was falsch läuft, wo alle Ihre Knoten sind, was Sie tun müssen, um Zugang benötigen oder einfügen oder löschen oder einer von ihnen. Jeder gut mit, dass? Cool. 

Also, wenn wir wollten, um sich den Code aus? Ach, ich weiß nicht, ob wir kann the-- OK zu sehen, so an der Spitze allem ist es eine Funktion Namen einfügen, wo wir wollen zu int n sich der Liste einzufügen. Wir werden über diese zu gehen. Es ist eine Menge Code, viel neue Syntax. Wir werden in Ordnung sein. 

So an der Spitze, wenn wir etwas erstellen möchten was wir tun müssen, vor allem wenn Sie wollen, dass es nicht auf den Stapel abgelegt werden aber in der Halde? Wir gehen zu einem malloc, nicht wahr? Wir werden also, um einen Zeiger zu erstellen. Knoten, zeiger, neue equals malloc die Größe eines Knotens denn wir wollen, dass der Knoten erstellt werden. Wir wollen, dass die Menge an Speicher, der ein Knoten nimmt für die zugeteilt werden Erstellung des neuen Knotens. 

Und dann werden wir zu überprüfen, ob neue equals ist gleich null. Denken Sie daran, was wir gesagt haben? Was auch immer Sie malloc, Was müssen Sie immer tun? Sie müssen immer überprüfen, um zu sehen, ob oder ob nicht das ist null. 

Zum Beispiel, wenn Sie Ihr Betriebs System komplett ausgebucht war, wenn man sich hatte keine Speicher alles, und Sie müssen malloc versuchen, es wäre für Sie null zurück. Und so, wenn Sie versuchen, es zu verwenden, als es war, die auf null, du bist nicht in der Lage sein werde für den Zugriff auf diese Informationen. Und so als solche zu machen wollten wir Sie sicher, dass, wann immer Sie mallocing bist, Sie immer überprüfen, ob zu sehen dass der Speicher ein, die Sie ist null. Und wenn es nicht ist, dann können wir bewegen kann mit dem Rest unseres Codes. 

So dass wir zu gehen initialisieren Sie den neuen Knoten. Wir werden tun, neue n gleich n. Und dann werden wir tun, setzen neue den Mauszeiger auf neue auf null, weil jetzt wir nicht möchte alles für sie zu zeigen. Wir haben keine Ahnung, wo es wird euch geben, und dann, wenn wir wollen legen Sie sie an der Spitze, dann werden wir neu zuweisen können der Zeiger auf den Kopf. Hat jeder folgen der Logik von wo das passiert? 

Alles, was wir tun, ist die Schaffung einer neuen Knoten, die Einstellung der Zeiger auf Null, und dann die Neuzuweisung es auf den Kopf, wenn wir wissen wir, es an der Spitze eingefügt werden soll. Und dann der Kopf zu gehen deuten darauf hin, dass neue Knoten. Jeder OK mit, dass? 

Es ist also ein zweistufiges Verfahren. Sie haben den ersten assign bekam was auch immer Sie erstellen. Stellen Sie den Zeiger, um die Referenz, und dann kann Art von Dereferenzierung der erste Zeiger und verweisen Sie auf die neuen Knoten. Überall dort, wo Sie es einfügen möchten, daß die Logik geht, um wahr zu halten. 

Es ist eine Art, wie die Zuordnung temporäre Variablen. Denken Sie daran, Sie haben um sicherzustellen, dass Sie keine Spur, wenn Sie tauschen bist zu verlieren. Sie wollen sicherstellen, dass Sie eine temporäre Variable, die Art hält verfolgen, wo das Ding wird gespeichert, so dass Sie keinen Wert im Laufe verlieren der wie Herumspielen mit ihr. 

OK, so dass Code wird hier sein. Ihr Jungs werfen Sie einen Blick nach der Seite. Es wird da sein. 

Also ich denke, wie funktioniert Diese unterscheiden sich, wenn wir wollten in der Mitte oder am Ende einfügen? Hat jemand eine Idee von dem, was die haben Pseudocode als logische Referenz dass wir uns nehmen, wenn wir wollten, um es in der Mitte einfügen? Also, wenn wir es am Einsatz wollte Kopf, ist alles was wir tun, erstellen Sie einen neuen Knoten. Wir setzen den Zeiger, dass neuen Knoten zu, was den Kopf, und dann setzen wir den Kopf auf den neuen Knoten, nicht wahr? Wenn wir es in der Mitte stecken wollte, der Liste, was würden wir tun? 

Publikum: es wäre immer noch ist ein ähnlicher Prozess der wie das Zuweisen von Zeiger und dann Zuweisen diesen Zeiger, aber wir müssten es zu lokalisieren. 

ANDI PENG: Genau, so genau, der gleiche Prozess, außer Sie müssen, wo genau lokalisieren Sie wollen, dass die neuen Zeiger, um in zu gehen, so, wenn ich in einfügen Mitte verbunden list-- OK, sagen wir mal, das ist unser verknüpften Liste. Wenn wir es gleich hier einfügen möchten, wir werden einen neuen Knoten erstellen. Wir fahren nach malloc gehen. Wir werden einen neuen Knoten erstellen. Wir werden das weisen Sie Zeiger dieses Knotens hier. 

Aber das Problem, das unterscheidet von wo der Kopf ist, dass wir genau wussten, wo der Kopf ist. Es war richtig, in der ersten, nicht wahr? Aber hier müssen wir Kurs zu halten von wo wir Einsetzen in. Wenn wir unsere Einfügen Knoten hier, wir haben um sicherzustellen, dass die einem vor dieser Knoten ist derjenige, der den Zeiger neu zuweist. Also dann muss man Art zu verfolgen, zwei Dinge. Wenn Sie verfolgen, wo diese zu halten Knoten derzeit ist das Einfügen in. Sie haben auch zu verfolgen, wo halten der vorherige Knoten, den Sie suchen, War auch da. Jeder gut mit, dass? OK. 

Wie wäre es mit Einfügen in das Ende? Wenn ich wollte, um es hinzuzufügen hier-- wenn ich wollte um einen neuen Knoten zu dem Ende einer Liste, wie könnte ich fahren bei tuend jene? Publikum: So aktuell, die wies zuletzt auf NULL. ANDI PENG: Ja. Genau, so ist dies ein derzeit wird darauf zu wissen, und so denke ich, in diesem Sinne, ist es sehr einfach, an das Ende der Liste hinzuzufügen. Alles, was Sie tun müssen, ist festgelegt gleich null und dann Boom. Genau dort, sehr einfach. Sehr einfach. 

Sehr ähnlich dem Kopf, aber logischer Sie wollen sicherstellen, dass die Schritte Sie zu tun, irgendetwas davon zu nehmen, Sie folgenden sind zusammen. Es ist sehr einfach, um, in der Mitte des Codes, steh auf gefangen, Oh, ich habe so viele Hinweise bekam. Ich weiß nicht, wo nichts ist, die auf. Ich weiß nicht einmal, welcher Knoten Ich bin auf. Was ist los? 

Entspannen Sie sich, beruhigen Sie sich, atmen Sie tief ein. Ziehen Sie Ihren verknüpften Liste. Wenn Sie sagen, ich weiß, wo genau Ich muss dies in einfügen und ich weiß genau, wie ich meine neu zuweisen Zeiger, viel, viel einfacher zu Bild out-- viel, viel einfacher, nicht in den Fehler des Codes verloren gehen. Jeder OK mit, dass? OK. 

Also ich denke, ein Konzept, das haben wir nicht wirklich darüber gesprochen, bevor jetzt, und ich denke, Sie wahrscheinlich wird viel yet-- nicht begegnen es ist eine Art von einem fortgeschrittenen concept-- ist, dass wir tatsächlich eine Daten Struktur namens eine doppelt verknüpfte Liste. So wie Sie Jungs sehen können, alles, was wir tun, ist die Schaffung ein Ist-Wert, ein extra Zeiger auf jedem unserer Teilnehmer dass auch Punkte zum vorherigen Knoten. Also nicht nur haben wir unsere Knoten weisen auf die nächste. Sie verweisen auch auf die vorherige. Ich werde diese beiden jetzt zu ignorieren. 

Also dann haben Sie eine Kette dass in beide Richtungen zu bewegen, und dann ist es ein bisschen leichter logisch folgen. Wie hier, anstelle von Verfolgung, oh, ich müssen wissen, dass dieser Knoten die eine, die ich neu zuzuweisen, Ich kann einfach gehen Sie hier und Ziehen Sie einfach die vorherige. Dann weiß ich genau, wo das ist, und dann nicht haben, um das zu durchqueren Gesamtheit der verknüpften Liste. Es ist ein bisschen einfacher. 

Aber als solche müssen Sie doppelt die Menge von Zeigern, das ist doppelt so viel Speicher. Es ist eine Menge von Zeigern, um zu verfolgen. Es ist ein wenig komplexer, aber es ist ein bisschen mehr benutzerfreundlich je auf, was Sie versuchen zu erreichen. 

So dass diese Art von Daten Struktur völlig vorhanden ist, und die Struktur für die sehr, sehr einfache, außer alle die Sie haben ist, anstelle von nur einem Zeiger zur nächsten, Sie haben auch einen Zeiger auf vorhergehende. Das ist alles, der Unterschied war. Jeder gut mit, dass? Cool. 

In Ordnung, so jetzt bin ich um wirklich wahrscheinlich verbringen wie 15 bis 20 Minuten oder die Masse der Rest der Zeit, in der Rubrik reden über Hash-Tabellen. Wie viele von euch haben pset5 spec lesen? Also gut, gut. Das ist höher als die 50% der in der Regel. Es ist in Ordnung. 

So wie Sie Kerle werden sehen, Sie Herausforderung pset5 sind werden, um ein Wörterbuch zu implementieren wo Sie mehr als 140.000 Wörter zu laden dass wir Ihnen und Rechtschreibprüfung gegen den gesamten Text. Registrieren Sie sich zufällig ergeben Stücke der Literatur. Wir geben Ihnen die Odyssee. Wir geben Ihnen die Ilias. Wir geben Ihnen Austin Powers. 

Und Ihre Herausforderung wird es sein, Rechtschreibüberprüfung jedes einzelne Wort in all dieser Wörterbücher im wesentlichen mit unseren Rechtschreibprüfung. Und so gibt es ein paar Teile der Schaffung dieses pset, erste Sie sein wollen Lage, tatsächlich zu laden Alle Wörter in Ihr Wörterbuch, und dann wollen in der Lage zu sein, Rechtschreibprüfung alle von ihnen. Und so wie, Sie gehen zu verlangen sind eine Datenstruktur, die diese schnell tun können und effizient und dynamisch. 

Also nehme ich an der einfachste Weg, dies zu tun, werden Sie wäre wahrscheinlich ein Array, oder? Die einfachste Art der Lagerung ist, dass Sie kann ein Array von 140.000 Wörtern zu erstellen und legen Sie sie alle einfach nur da und Dann durchlaufen sie durch binäre Suche oder durch Auswahl oder nicht-- Es tut uns leid, dass ist das Sortieren. Sie können sortieren sie und dann durchlaufen sie durch binäre Suche oder lineare Suche und nur Abschluss die Worte, aber das nimmt einen riesigen Menge an Speicher, und es ist nicht sehr effizient. 

Und so werden wir beginnen Gespräch über Möglichkeiten, unsere Laufzeit effizienter. Und unser Ziel ist es, konstante Zeit, wo es ist fast wie Arrays, in denen Sie haben sofortigen Zugang. Wenn ich wollte, um etwas zu suchen, Ich möchte in der Lage sein, nur, boom, finden es genau, und ziehen Sie sie heraus. Und so eine Struktur, in der werden wir immer ganz in der Nähe um Zugriff konstant sein Zeit, diese heilige Gral Programmier konstanter Zeit wird als eine Hash-Tabelle. Und so David bereits erwähnt die [Unverständlich] ein wenig in der Vorlesung, aber wir sind wirklich zu Tauchen im tiefen Gespräch auf einem Stück, das in Bezug auf ist wie eine Hash-Tabelle funktioniert. 

Also die Art und Weise, dass eine Hash- Tabelle Werke beispielsweise wenn ich einen Haufen von Wörtern zu speichern wollte, ein Haufen von Wörtern in der englischen Sprache, Ich könnte theoretisch setzen Banane, Apfel, Kiwi, Mango, Paar, und Melone alle auf nur einem Array. Sie könnten alle passen und werden zu finden. Es wäre eine Art Schmerz zu sein durchsuchen und den Zugang, aber der einfachere Weg dies zu tun ist dass wir tatsächlich eine Struktur erstellen können rief eine Hash-Tabelle, wo wir Hash. Wir führen alle unsere Schlüssel durch eine Hash-Funktion, eine Gleichung, dass macht sie alle in eine Art von einem Wert dass dann können wir auf speichern im wesentlichen eine Reihe von verknüpften Liste. 

Und hier, wenn wir wollten , englische Wörter zu speichern, wir könnten einfach, weiß ich nicht kennen, schalten Sie die ersten Buchstaben in eine Art von einer Zahl. Und so, beispielsweise, wenn ich A bis Synonym apple-- sein oder mit dem Index 0 ist und B gleichbedeutend mit 1 zu sein, Wir können 26 Einträge haben dass nur speichern kann alle Buchstaben des Alphabet, das wir mit zu beginnen. Und dann haben wir können Apfel bei Index 0. Wir können Bananen bei Index haben 1, Melone am Index von 2, und so weiter und so fort. Und so, wenn ich wollte, um zu suchen meine Hash-Tabelle und den Zugang Apfel, Ich weiß, Apfel beginnt mit ein A, und ich weiß genau, , dass es sein muss, und der Hash- Tisch im Index 0, weil der Funktion zuvor zugewiesen. 

Also ich weiß nicht, wir sind ein Benutzer-Programm, wo Sie werden mit in Rechnung gestellt arbitrarily-- nicht willkürlich, mit dem Versuch, nachdenklich denken Sie an gute Gleichungen in der Lage sein zu verbreiten Sie alle Ihre Werte in einer Art, wie sie leicht zugänglich machen können sie später mit, wie eine Gleichung , dass Sie selbst wissen. Also in dem Sinne, wenn ich wollte, um zu gehen Mango, weiß ich, oh, mit m beginnt es. Es muss bei Index 12 zu sein. Ich habe keine, durch nichts zu suchen. Ich weiß, ich könnte nur exactly-- zu gehen der Index von 12 und ziehen, dass aus. 

Jeder klar, wie ein Funktion Hash-Tabelle funktioniert? Es ist eine Art nur eine komplexere Arrays. Das ist alles, es ist. OK. 

Also ich denke, wir laufen in Diese Frage, was passiert, wenn Sie mehrere Dinge haben daß Ihnen die gleiche Index? So sagen unsere Funktion, alles was man tat, war, dass die erste Buchstabe und drehen Sie die in einen jeweils 0 bis 25-Index. Das ist völlig in Ordnung, wenn Sie haben nur einen von jedem. Aber die zweite Sie beginnen mit mehr, du bist gehen zu müssen, was heißt eine Kollision. 

Also, wenn ich versuche, legen Sie in eine Hash begraben Tabelle, die bereits Bananen auf sie, was passieren wird, wenn Sie versuchen, dass ein? Bad Dinge, weil Bananen die bereits im Index vorhanden dass Sie es speichern wollen. Berry Art ist wie, ach, was soll ich tun? Ich weiß nicht, wohin sie gehen. Wie kann ich dieses Problem lösen? 

Und damit Sie Jungs Art sehen wir diese heikle Sache wo wir können Art von tatsächlich erstellen verknüpften Liste in unserem Arrays. Und so am einfachsten darüber nachdenken, alle Hash-Tabelle ist eine Array von verknüpften Listen. Und so, in diesem Sinne, müssen Sie dieses schöne Array von Zeigern, und dann jeder Zeiger in dieser Wert, in diesem Index, kann tatsächlich auf andere Dinge zu zeigen. Und damit Sie all diese separaten haben Ketten kommen aus einem großen Array. 

Und hier, wenn ich wollte berry einzufügen, Ich weiß, OK, ich bin zur Eingabe gehen es mir durch den Hash-Funktion. Ich werde mit dem Index am Ende 1, und dann werde ich in der Lage, zu haben nur ein kleiner Teilsatz von diesem Riesen 140.000-Wort Wörterbuch. Und dann kann ich nur schauen durch 1/26 davon. 

Und so ist, dann kann ich einfach einfügen Beeren entweder vor oder nach Banane in diesem Fall? Nach, oder? Und so wirst du zu wollen, sind fügen Sie diesen Knoten nach Banane, und so wirst du einzufügen sind am Heck dieser verbundenen Liste. Ich werde zurückgehen zu dieser vorherigen Folie, so euch kann sehen, wie Hash-Funktion arbeitet. 

So Hash-Funktion ist diese Gleichung dass Sie mit Art Ihrer Eingabe sind durch was auch immer Index zu bekommen Sie es in Richtung zuordnen wollen. Usw., in diesem Beispiel wollten wir zu tun war, nehmen Sie den ersten Buchstaben, drehen, dass in einen Index, dann sind wir kann, dass in unserer Hash-Funktion zu speichern. Alles, was wir hier tun, ist, wir sind Umwandeln des ersten Buchstaben. So KeyKey [0] ist nur der erste Buchstabe gleich welcher String wir haben, wir im Vorbeigehen. Wir konvertieren, dass zu den oberen und wir subtrahiert von Großbuchstaben A, so alles, was zu tun ist ist eine Zahl, die uns in dem wir unsere Werte auf Hash. 

Und dann werden wir zu gehen Rück Hash-Modul SIZE. Seien Sie sehr, sehr vorsichtig weil theoretisch hier Ihre Hash-Wert könnte unendlich sein. Es könnte einfach weiter und weiter und weiter. Es könnte ein paar wirklich sein, wirklich großen Wert, sondern weil Ihre Hash-Tabelle, Sie erstellt haben, hat nur 26 Indizes, Sie sicherstellen möchten, dass Ihre modulusing, so dass Sie nicht run-- es ist das gleiche Sache, als Ihre queue-- so dass Sie nicht ausführen off der Unterseite Ihres Hash-Funktion. 

Sie wollen es herum wickeln zurück auf die gleiche Weise in [unverständlich], wenn Sie hatte wie ein sehr, sehr großen Buchstaben, die Sie wollte nicht, dass, um führen Sie einfach das Ende. Das Gleiche gilt hier, um sicherzustellen, dass Sie wollen es läuft nicht das Ende durch das Einwickeln herum zur Oberseite der Tabelle. So ist dies nur ein sehr einfache Hash-Funktion. All das tat, war die erste Brief von was auch immer unsere Eingangs war und drehen Sie, dass in einen Index, konnten wir in unser Hash-Tabelle zu setzen. 

Ja, und so, wie ich schon sagte, die Art und Weise, die wir Kollisionen zu beheben in unserer Hash-Tabellen werden mit, wie wir es nennen, Verkettung. Also, wenn Sie versuchen, legen Sie mehrere Wörter, die mit der gleichen Sache zu starten, Sie gehen zu einem Hash-Wert haben. Avocados und Apfel, wenn Sie schon führen Sie es durch unsere Hash-Funktion, werden euch das zu geben gleiche Anzahl, der Anzahl von 0. Und so ist die Art, wie wir beschließen, dass es dass wir eigentlich ganz verknüpfen miteinander über verkettete Listen. 

Und so in diesem Sinne euch kann Art zu sehen wie Datenstrukturen, wir haben bisher Einstellung wie eine Rosine verknüpften Liste Art der können zusammen in einem kommen. Und dann hast du weit erstellen effizientere Datenstrukturen dass größere Mengen verarbeiten kann Daten, die dynamisch in Abhängigkeit skalieren nach Ihren Bedürfnissen. Jeder klar? Jeder Art von klaren auf das, was hier passiert? 

Wenn ich wollte insert-- was ist ein Frucht, die mit, ich weiß nicht, beginnt, B, ausgenommen Beeren, Bananen. 

ZIELGRUPPE: Blackberry. 

ANDI PENG: Brombeere, Brombeere. Wo kommt Brombeere geht es weiter? Nun, wir haben eigentlich nicht sortiert dies noch nicht, aber theoretisch Wenn wir dies gesucht in alphabetischer Reihenfolge, wo soll Brombeere gehen? 

ZIELGRUPPE: [unverständlich] 

ANDI PENG: Genau, nach hier, nicht wahr? Aber da es sehr schwierig ist, reorder-- Ich denke, es liegt an euch. Euch kann total umzusetzen, was Sie wollen. Das effizientere dies zu tun, vielleicht wäre zu sortieren Sie Ihre verlinkt Liste in alphabetischer Reihenfolge, und so, wenn Sie Einfügen von Dingen, Sie wollen um sicher zu sein, um sie einzufügen in alphabetischer Reihenfolge so dass dann, wenn Sie versuchen, sie zu suchen, Sie müssen nicht, um alles zu durchqueren. Sie wissen genau, wo es ist, und es ist einfacher. 

Aber wenn Sie Art haben Dinge durchsetzt nach dem Zufallsprinzip, du bist immer noch zu haben um es trotzdem zu durchqueren. Und so, wenn ich wollte gerade einfügen blackberry hier und ich wollte, nach dem gesucht sie, das weiß ich, oh, Blackberry müssen mit dem Index 1 beginnen, so dass ich weiß augenblicklich nur bei 1 zu suchen. Und dann kann ich Art von durchqueren die verkettete Liste bis ich den Blackberry, und then-- ja? 

Publikum: Wenn Sie versuchen, create-- sind Ich denke, so ist eine sehr einfache Hash- Funktion. Und wenn wir wollten, mehrere Schichten, die wie, OK, um in zu trennen wollen wir wie alle Buchstaben des Alphabets und dann noch einmal um einen weiteren Satz gefallen der alphabetischen Buchstaben innerhalb, dass, setzen wir wie ein Hash- Tabelle innerhalb einer Hash-Tabelle, oder wie eine Funktion innerhalb einer Funktion? Oder dass-- ist 

ANDI PENG: Also Ihre Hash- function-- Ihre Hash-Tabelle kann so groß sein, wie Sie es wollen. Also in diesem Sinne, ich dachte, es war sehr einfach, sehr einfach für mich, einfach so auf der Basis Buchstaben des ersten Wortes. Und so gibt es nur 26 Optionen. Ich kann nur 26 Optionen zu erhalten 0 bis 25, weil sie nur Start von A bis Z. Aber Wenn Sie wollten zu ergänzen, vielleicht, mehr Komplexität oder schneller laufen Zeit, um Ihre Hash-Tabelle, die Sie unbedingt können alle möglichen Dinge zu tun. Sie können Ihre eigenen zu machen Gleichung, die Ihnen weitere Verteilung in Ihrem Worte, dann, wenn Sie suchen, es wird schneller zu sein. 

Es ist völlig bis zu Ihnen Kerle wie Sie zu implementieren, dass wollen. Betrachten Sie es als nur Eimer. Wenn ich haben wollte 26 Eimer, ich werde die Dinge in diese Eimer sortieren. Aber ich werde zu einem Haufen haben Sachen in jedem Eimer, so, wenn Sie es machen wollen schneller und effizienter, lassen Sie mich haben hundert Eimer. 

Aber dann haben Sie, um herauszufinden, ein Weg, Dinge zu sortieren, so dass sie in der richtigen Eimer sollten sie sein. Aber dann, wenn Sie tatsächlich möchte in diesem Eimer aussehen, es ist viel schneller, weil es weniger Sachen in jedem Eimer. Und ja, ja, das ist wirklich der Trick für euch in pset5 ist, dass Sie sein herausgefordert, erstellen Sie einfach was die effizienteste Funktion können Sie denken zu sein in der Lage zu speichern und zu überprüfen, diese Werte. 

Völlig bis zu Ihnen Kerle aber Sie es wollen, aber das ist ein sehr guter Punkt. Dass die Art der Logik, die Sie wollen, darüber nachzudenken, ist, nun ja, warum nicht ich mehr Eimer zu machen. Und dann muss ich suchen weniger Dinge, und dann vielleicht ich haben eine andere Hash-Funktion. 

Ja, es gibt eine Menge von Möglichkeiten, dies zu tun PSET, einige sind schneller als andere. Ich bin total gehen, um nur zu sehen, wie schnell war der schnellste euch wird in der Lage sein, um Ihre Aufgaben zu arbeiten. OK, jeder gut auf Verkettung und Hash-Tabellen? Es ist eigentlich wie eine sehr einfache Konzept, wenn man darüber nachdenkt. Alles, was es ist, was auch immer trenn Ihre Eingaben werden in Eimern, sortiert sie und dann die Suche im nennt, dass es im Zusammenhang mit. 

Cool. Also gut, jetzt haben wir eine andere Art der Datenstruktur, die aufgerufen Baum. Lassen Sie uns gehen und sprechen über Versuche sich deutlich voneinander unterscheiden, aber in der gleichen Kategorie. Im Wesentlichen ist, anstatt alle ein Baum der Organisation von Daten in der linearen Weg dass eine Hash-Tabelle does-- Sie weiß, es hat eine Oberseite und eine Unterseite und dann können Sie Art von Link aus der es-- ein Baum hat eine Oberseite, die Sie das root aufrufen, und dann hat es Blätter alle um ihn herum. 

Und so alles, was Sie hier haben, ist nur der oberste Knoten dass die Punkte zu anderen Knoten, dass die Punkte mehr Knoten und so weiter und so fort. Und so müssen Sie nur noch Aufspaltung Filialen. Es ist nur eine andere Art und Weise zu organisieren Daten, und weil wir es einen Baum nennen, Sie Kerle just-- es ist einfach Vorbild aus, um wie ein Baum aussehen. Deshalb nennen wir es Bäumen. 

Hash-Tabelle sieht wie ein Tisch. Ein Baum sieht aus wie ein Baum. Alle es gibt einen separaten Art der Organisation Knoten je nachdem, was Ihre Bedürfnisse sind. 

So dass Sie einen root haben und dann haben Sie Blätter. Die Möglichkeit, dass wir vor allem darüber nachzudenken ist ein binärer Baum, ein binärer Baum ist nur ein spezifische Art eines Baumes wobei jeder Knoten nur Punkte auf, bei max zwei anderen Knoten. Und so hier haben Sie verschiedene Symmetrie in Ihrem Stammbaum dass macht es einfacher, Art suchen an, welche Werte Sie sind, weil dann immer eine linke oder eine rechte. Es gibt nie wie ein dritter von links die linke oder ein vierter von links. Es ist nur Sie eine linke und eine rechte haben und Sie können eine dieser beiden zu suchen. Und warum ist das nützlich? Die Art und Weise, dass dies nützlich ist, wenn Sie schauen, um in den Werten zu suchen, oder? Anstatt Umsetzung binären Suche in einem Fehler-Array, wenn Sie in der Lage sein, um Knoten einzufügen sein wollte und nehmen Knoten an Willen und auch Erhaltung der Suche Kapazitäten der binären Suche. Also auf diese Weise, Art der wir tricking-- erinnere mich, als wir die verknüpften Listen kann nicht binäre Suche? Wir Art der Erstellung einer Datenstruktur dass Tricks, die in die Arbeits. 

Und so, weil verknüpfte Listen sind linear, sie nur eine Verknüpfung einer nach dem anderen. Wir können Art haben andere Art von Zeigern dieser Punkt auf verschiedenen Knoten dass können Sie uns Suche zu helfen. Und hier, wenn ich wollte, einen binären Suchbaum, Ich weiß, dass mein zweiter, wenn 55. Ich werde einfach zu erstellen wie meine Mitte, als meine Wurzel, und dann werde ich haben Werte Spin-off von ihm. 

Also hier, wenn ich gehe, um zu suchen der Wert 66, kann ich bei 55 zu beginnen. Es ist 66 größer als 55? Ja, es ist, damit ich weiß, ich mus suchen i n der rechte Zeiger dieses Baumes. Ich gehe in die 77. OK, das ist weniger als 66 oder größer als 77? Es ist weniger als, so dass Sie wissen, oh, dass nach links Knoten sein. 

Und hier sind wir Art von Konservierung alle großen Dinge über Arrays, so wie dynamische Größenanpassung von Objekten, wobei Lage einzusetzen und nach Belieben zu löschen, ohne sich um die feste Sorgen Platzbedarf. Wir alle noch zu bewahren diese wunderbaren Dinge, aber auch in der Lage, das zu bewahren log und die Suche Zeit der binären Suche dass wir nur vorher Lage, einen Begriff zu bekommen. 

Coole Datenstruktur, Art der komplex zu implementieren, wird der Knoten. Wie Sie, alle es sehen können ist die Struktur des Knotens ist, dass Sie eine linke haben und ein Pfeil nach rechts. Das ist alles, es ist. So und nicht nur mit einem x oder eine frühere. Sie haben eine links oder rechts, und dann Sie können Art miteinander verbinden aber Sie dies wünschen. 

OK, wir sind eigentlich los nur ein paar Minuten dauern. So werden wir hier wieder. Wie ich bereits sagte, Ich Art erklärt die Logik, wie wir würde durch diese zu suchen. Wir werden versuchen, pseudocoding diese aus, um zu sehen wenn wir die Art der Anwendung gleichen Logik der binären Suche auf eine andere Art von Datenstruktur. Wenn euch an wie ein paar machen wollen Minuten, nur darüber nachzudenken. OK. Also gut, ich bin zu gehen eigentlich nur geben Ihnen kein the--, Wir werden über die Pseudo reden. So hat jemand will um einen Stich zu geben, was das erste, was Sie tun, wenn möchten Sie beginnen heraus Suche ist? Wenn wir suchen der Wert von 66, was ist das erste, was wir, wenn tun möchten wir wollen, suchen diesen Baum zu Binär? 

ZIELGRUPPE: Sie wollen gut aussehen, und links schauen und sehen, [unverständlich] größere Anzahl. 

ANDI PENG: Ja, genau. So wirst du in Ihr Root aussehen. Es gibt viele Möglichkeiten, die Sie anrufen können es, sagen, dass Ihre übergeordneten Knoten Personen. Ich mag zu sagen, weil root das ist, wie die Wurzel des Baumes. Sie gehen, zu betrachten Ihre Stammknoten, und du bist gehen zu sehen, ist 66 mehr oder weniger als 55. Und wenn es größer als, nun ja, ist es größer als, wollen, wo wir zu schauen? Wo wollen wir jetzt suchen, oder wollen? Wir wollen die Suche rechte Hälfte dieses Baumes. 

So haben wir, günstig, ein Zeiger, der nach rechts zeigt. Und so ist, dann setzen wir können unsere neue Wurzel bis 77 sein. Wir können nur, wohin gehen der Zeiger zeigt. Nun, oh, hier wir beginnen bei 77, und wir können nur tun dies rekursiv wieder und wieder. Auf diese Weise, Sie Art der eine Funktion haben. Sie haben einen Weg suchen, dass Sie kann nur wiederholen, immer und immer und immer wieder, je nachdem, wo Sie aussehen wollen bis Sie schließlich zu dem Wert zu erhalten dass Sie suchen. Sinn ergeben? 

Ich bin, Ihnen zu zeigen, die tatsächliche Code, und es gibt eine Menge von Code. Keine Notwendigkeit, ausflippen. Wir werden durch sie zu sprechen. 

Nicht wirklich. Das war nur Pseudocode. OK, das war nur der Pseudocode, Das ist ein wenig komplex, aber es ist völlig in Ordnung. Jeder folgende entlang hier? Wenn die Wurzel ist null, Rück falsch, weil, dass Mittel Sie haben nicht einmal etwas gibt. 

Wenn root n ist der Wert, also wenn es geschieht, die man Sie gerade sehen können, dann wirst du treu bist zurück weil Sie wissen, dass Sie es gefunden. Aber wenn der Wert kleiner ist als Wurzel n, du bist gehen, um die linke suchen Kind oder das linke Blatt, was auch immer Sie es nennen wollen. Und wenn der Wert größer als Wurzel ist, Du wirst den richtigen Baum zu suchen, dann führen Sie einfach die Funktion über die Suche erneut. 

Und wenn root null ist, dass diese bedeutet, dass Sie das Ende erreicht haben? Das heißt, Sie müssen nicht mehr mehr Blätter zu suchen, dann wissen Sie, oh, ich denke, es ist nicht hier, denn nachdem ich durchgesehen die ganze Sache und es ist nicht hier, es könnte nur nicht hier. 

Ist das sinnvoll, um alle? So ist es wie binäre Suche zu bewahren die Fähigkeiten der verknüpften Listen. Kühlen, und so der zweite Typ der Datenstruktur euch können versuchen, die Umsetzung auf pset, Sie müssen nur eine Methode zu wählen. Aber vielleicht eine alternative Methode zur die Hash-Tabelle ist, was wir einen Trie nennen. 

Alle ein Trie ist bestimmte Art von Baum, hat Werte, die auf andere Werte zu gehen. Anstatt also mit einem binären Struktur in dem Sinne, dass nur eine Sache kann auf zwei hinweisen, können Sie eine Sache, zeigen Sie auf viele, viele Dinge. Sie haben im Wesentlichen Arrays Innere, die Sie speichern Hinweise, die auf andere Arrays verweisen. 

So wird der Knoten, wie wir würde eine Trie definieren ist, dass wir wollen, um eine haben Boolean, c Wort, nicht wahr? So der Knoten Boolean wie wahr oder falsch, vor allem an der Spitze dieses Array, ist dies ein Wort? Zweitens, um Zeiger haben wollen auf das, was der Rest von ihnen sind. Ein wenig komplex, etwas abstrakt, aber Ich werde erklären, was das alles bedeutet. 

So, hier, an der Spitze, wenn Sie haben ein Array deklariert bereits, ein Knoten in dem Sie eine Boolean haben Wert auf der Vorderseite gespeichert , dass erfahren Sie, dies ist ein Wort? Ist das nicht ein Wort? Und dann haben Sie die Rest des Array, tatsächlich speichert alle Möglichkeiten, was sie sein könnte. So, zum Beispiel, wie an der Spitze haben Sie die erste Sache, die besagt, dass wahr ist oder falsch, ja oder nein, das ist ein Wort. 

Und dann haben Sie über 26 haben 0 die Buchstaben, die Sie speichern können. Wenn ich wollte hier für Fledermaus, gehe ich an die Spitze und ich freue mich für B. Ich finde B in meiner Array und so weiß ich, OK, ist B ein Wort? B ist nicht ein Wort, also damit Ich muss weitersuchen. Ich gehe von B, und ich freue mich auf die Zeiger, B deutet auf und ich sehe ein anderes Array mit Informationen, die gleiche Struktur, die wir vorher hatten. 

Und hier-- oh, das nächste Brief in [unverständlich] ist A. So suchen wir in diesem Array. Wir finden die achten Wert, und dann schauen wir, um zu sehen, oh, hey, das ist mit einem Wort, ist B-A ein Wort? Es ist nicht ein Wort. Wir müssen die Augen offen halten. 

Und so freuen wir dorthin, wo der Zeiger eines Punkte, und es an eine andere Art und Weise weist was wir haben mehr Wert gespeichert. Und schließlich, um uns B-A-T, die ein Wort ist. Und so das nächste Mal, Sie sehen, Sie gehen , dass die Überprüfung der ja haben, Diese Boolesche Funktion ist wahr. Und so in dem Sinne, wir sind Art der mit einem Baum mit Arrays. 

So, dann können Sie Art der Suche nach unten. Anstatt Hashing-Funktion und Zuweisen von Werten durch verknüpfte Liste, Sie können einfach zu implementieren ein trie, die downwords sucht. Wirklich, wirklich kompliziert Sachen. Nicht leicht, über, weil ich denke, wie Spucken so viele Datenstrukturen aus dich an, macht aber jeder Art von zu verstehen, wie die Logik funktioniert das? 

OK COOL. So B-A-T und dann du gehst zu suchen. Das nächste Mal, du gehst um zu sehen, oh, hey, es ist wahr, damit ich weiß, das muss ein Wort sein. 

Das Gleiche gilt für den Zoo. Also hier ist die Sache gerade jetzt, wenn wir wollte für Zoo jetzt suchen, derzeit Zoo ist kein Wort im Wörterbuch weil, wie euch kann sehen, die erster Linie, dass wir ein Boolean return true ist am Ende der Zoom. Wir haben Z-O-O-M. 

Und hier, eigentlich nicht haben wir das Wort, Zoo, im Wörterbuch weil dieses Kontrollkästchen nicht aktiviert ist. So dass der Computer nicht wissen, dass Zoo ist ein Wort weil die Art und Weise, dass wir gespeichert ist, nur eine Zoom hier hat tatsächlich einen Boolean-Wert Das ist wahr geworden. Wenn wir also die eingefügt werden soll Wort, Zoo, in unser Wörterbuch, wie würden wir zu tun, dass zu gehen? Was müssen wir tun, um sicherzustellen, haben unsere Computer weiß, dass Z-O-O ist ein Wort, und nicht das erste Wort ist, Z-O-O-M? 

ZIELGRUPPE: [unverständlich] 

ANDI PENG: Genau, wir wollen sicherstellen, dass diese hier, ist, dass Boolean-Wert abgehakt, dass es wahr ist. Z-O-O, dann werden wir das prüfen, so dass wir genau wissen, hey, ist Zoo ein Wort. Ich werde das sagen, Computer, es ist ein Wort, so dass, wenn der Computer überprüft, sie weiß, dass Zoo ist ein Wort. 

Da erinnere mich an all diese Daten Strukturen, ist es für uns sehr einfach zu sagen, oh, bat ein Wort. Zoo ist ein Wort. Zoom ist ein Wort. Aber wenn man es bauen, der Computer hat keine Ahnung. 

Also muss man es genau sagen, an welchem ​​Punkt ist das ein Wort? An welchem ​​Punkt ist es nicht ein Wort? Und an welchem ​​Punkt ich müssen die Dinge zu suchen, und an welchem ​​Punkt muss ich gehen als nächstes? Jeder klar, dass? Cool. 

Und so dann kommt die Problem, wie würden wir gehen Sie zum Einfügen von etwas Das ist eigentlich nicht? Also lasst uns einfach sagen, dass wir einfügen wollen das Wort, Bad, in unsere trie. Wie euch kann wie noch zu sehen alles, was wir jetzt haben, ist B-A-T, und diese neue Datenstruktur dort hatte ein Pint, dass wies auf null, weil wir davon ausgehen, dass, oh, es gibt keine Worte, nachdem B-A-T, warum brauchen wir, um zu halten mit Dingen nach, dass T. 

Aber das Problem entsteht, wenn wir das tun Sie möchten ein Wort, das danach kommt haben die T-Shirts. Wenn Sie baden, du bist werde ein H rechts. Und so ist die Art, wie wir gehen, um das zu tun ist wir werden einen separaten Knoten erstellen. Wir sind nicht zuzuteilen, was Menge der Speicher für diese neuen Arrays, und wir werden Zeiger zuweisen. 

Wir werden das weisen Sie H, Zuallererst diese null ist, wir gehen, um loszuwerden. Wir gehen zu müssen der H-Punkt nach unten. Wenn wir sehen, ein H, sie wollen wir um woanders hin. 

In hier, dann können wir abhaken ja. Wenn wir eine H Hit nach dem T, oh, dann wissen wir, dass es sich um ein Wort. Der Boolean wird true zurückgibt. Jeder klar, wie das passiert ist? OK. 

So im Wesentlichen, alle Diese Datenstrukturen dass wir über heute gegangen, ich habe über sie wirklich, wirklich schnell gegangen und nicht in wesentlich Detail, und das ist OK. Sobald Sie verwirren beginnen mit ihm, werden Sie die Verfolgung der in dem alle Zeiger sind, was los ist in Ihrem Datenstrukturen, und so weiter. Sie werden sehr nützlich sein, und es liegt an Ihnen, Jungs völlig herausfinden, wie Ihnen, die Dinge umsetzen wollen. 

Und so pset4, der 5-- Oh, das ist falsch. Pset5 ist Rechtschreibfehler. Wie ich schon sagte, sind Sie gehen zu, einmal wieder, laden Sie Quellcode von uns. Es geht um drei Haupt sein Dinge, die Sie werden heruntergeladen. Du wirst Wörterbücher herunterzuladen, KERS und Texte. 

All diese Dinge sind entweder Wörterbüchern der Wörter dass wir Sie prüfen möchten oder Prüfung von Informationen dass wir wollen, dass Sie Prüfung buchstabieren. Und so sind die Wörterbücher wir geben Sie gehen Sie tatsächlichen Worte, die wir geben wollen Sie irgendwie in einer Weise, die es speichern effizienter als ein Array. Und dann die Texte das sein, was wir sind fordert Sie auf, die Rechtschreibprüfung, um sicherzustellen, allen Wörtern es reale Wörter. 

Und so sind die drei Blöcke von Programme, die wir geben Ihnen sind dictionary.c genannt, dictionary.h und speller.c. Und so alle dictionary.c tut, ist was werden Sie gefragt, zu implementieren. Er lädt Wörtern. Es Rechtschreibprüfungen in ihnen, und es wird sichergestellt, dass alles richtig eingesetzt ist. 

diction.h ist nur eine Bibliotheksdatei dass erklärt, alle diese Funktionen. Und speller.c, werden wir Sie geben. Sie brauchen nicht zu einem ihn zu ändern. Alle speller.c tut, ist, dass, lädt sie prüft die Geschwindigkeit davon, testet die Benchmark wie, wie schnell Sie in der Lage, Dinge zu tun. 

Es ist eine Rechtschreibprüfung. Just do not mess with es, aber stellen sicher, Sie verstehen, was es tut. Wir verwenden eine Funktion namens getrusage dass prüft die Leistung den Zauber Checker. Denn es macht im Grunde das testen Zeit der alles in Ihrem Wörterbuch, so stellen Sie sicher, es zu verstehen. Achten Sie darauf, dass die Messe mit nicht oder sonst die Dinge nicht richtig laufen. 

Und der Großteil dieser Aufgabe ist für Sie Kerle wirklich dictionary.c ändern. Wir werden Ihnen 140.000 Wörter in einem Wörterbuch. Wir werden Sie einen Text zu geben, Datei, die diese Worte hat, und wir möchten, dass Sie in der Lage, zu organisieren sie in eine Hash-Tabelle oder eine Trie denn wenn wir Sie bitten, die Zauber check-- vorstellen, wenn Sie Rechtschreib sind Prüfen, wie Homers Odyssee. Es ist wie dieser großen, großen Test. 

Stellen Sie sich vor jedem einzelnen Wort musste man suchen durch eine Anordnung von 140.000 Werten. Das würde ewig dauern, für Ihre Maschine zu laufen. Deshalb haben wir unsere organisieren Daten in effizienter Datenstrukturen wie beispielsweise eine Hash-Tabelle oder eine Trie. Und dann kann man Jungs Art der bei der Suche Zugang Dinge einfacher und schneller. 

Und so vorsichtig sein, um Kollisionen zu lösen. Du wirst eine Menge zu bekommen von Wörtern dieser Anfang mit A. Du wirst einen Haufen Worte erhalten dass mit B. starten Bis zu Ihnen Jungs, wie Sie wollen, es zu lösen. Vielleicht gibt es mehr effizienten Hash-Funktion als nur die ersten Buchstaben etwas, und so, dass es an Ihnen Jungs Art zu tun, was Sie wollen. 

Vielleicht die Sie hinzufügen möchten alle Buchstaben zusammen. Vielleicht möchten Sie gerne tun seltsame Dinge wollen um die Anzahl von Buchstaben zu berücksichtigen, was auch immer. Bis zu euch, wie Sie tun möchten. Wenn Sie eine Hash-Tabelle zu tun, wenn Sie wollen wollen eine Trie versuchen, völlig bis zu Ihnen. Ich werde dich vor der Zeit, dass die zu warnen Trie ist typischerweise ein etwas schwieriger nur weil es gibt eine Menge Weitere Hinweise, um zu verfolgen. Aber völlig bis zu euch. Es ist wesentlich effizienter in den meisten Fällen. Sie wollen wirklich in der Lage zu halten Überblick über alle Ihre Zeiger. Wie das Gleiche tun dass ich hier tun. Wenn Sie versuchen, einzufügen sind Werte in einer Hash-Tabelle oder zu löschen, stellen Sie sicher, dass Sie wirklich die Verfolgung von wo alles ist, weil es ist für die, wenn ich mich einfach versuchen, wie das Wort, andy einfügen. Sagen wir einfach, das ist ein Echt Wort, das Wort, andy, in eine riesige Liste von Wörtern. 

Wenn ich nur zufällig neu zuweisen ein Zeiger falsch, oops, da geht die Gesamtheit der der Rest meiner verknüpften Liste. Nun ist die einzige Wort, das ich haben, ist Andy, und jetzt alle anderen Wörter Wörterbuch sind verloren gegangen. Und so können Sie sicherstellen, dass Sie wollen, den Überblick über alle Ihre Hinweise oder Sie bekommen werden große Probleme in Ihrem Code. Zeichnen Sie die Dinge sorgfältig Schritt für Schritt. Es macht es viel einfacher, um zu denken. 

Und schließlich, um in der Lage sein wollen, dass Sie Testen Sie Ihre Leistungsfähigkeit Ihres Programms auf dem großen Brett. Wenn euch nehmen ein Blick auf CS50 gerade jetzt, Wir haben, was heißt das große Platine. Es ist das Notenblatt der am schnellsten Rechtschreibprüfung Zeiten über alle CS50 gerade jetzt, ich glaube, die obere wie 10 Ich denke mal acht von ihnen sind Mitarbeiter. Wir wünschen Sie wirklich Jungs, uns zu schlagen. 

Alle von uns versuchten, zu implementieren der schnellste Code wie möglich. Wir wollen euch zu versuchen, herausfordern uns und Umsetzung schneller als alle von uns kann. Und so ist das wirklich das erste Mal, dass wir bitten euch um eine pset zu tun, dass kann man wirklich in irgendeiner Methode zu tun du willst. 

Ich sage immer, das ist eher zu einer realen Lösung, nicht wahr? Ich sage, hey, ich brauche dich, dies zu tun. Erstellen Sie ein Programm, das für mich tut. Machen Sie es, wie Sie wollen. Ich weiß nur, dass ich zu schnell. Das ist Ihre Herausforderung für diese Woche. Ihr Jungs, wir gehen Sie eine Aufgabe zu geben. Wir werden Ihnen eine Herausforderung bieten. Und dann liegt es an euch vollständig gerade herauszufinden, was ist der schnellste und effizienter Weg, um dies zu implementieren. Ja? 

ZIELGRUPPE: Dürfen wir, wenn wollten schnellere Wege zu erforschen In den Hash-Tabellen online tun, können wir tun, dass und zu zitieren Code jemand anders? ANDI PENG: Ja, völlig in Ordnung. Also, wenn Sie die Jungs lesen spec, es gibt eine Linie in der Spezifikation, die euch sagt, sind völlig frei, Hash-Forschung Funktionen auf, was einige sind der schneller Hash-Funktionen die Dinge durch, wie laufen Solange Sie diesen Code zu zitieren. So manche Menschen haben bereits herausgefunden, schnelle Wege zu tun, Rechtschreibprüfung, der schnellen Möglichkeiten der Speicherung von Informationen. Völlig bis zu Ihnen Kerle, wenn Sie will nur nehmen, oder? Achten Sie darauf, unter Berufung sind. Die Herausforderung wirklich dass wir versuchen zu testen, sorgt dafür, dass Sie wissen, Ihren Weg durch Zeiger. So weit wie möglich die Umsetzung die tatsächliche Hash-Funktion und kommen mit, wie die Mathematik zu tun, euch erforschen können, was Methoden Online will euch. Ja? 

ZIELGRUPPE: Können wir zitieren mit Hilfe der [unverständlich]? 

ANDI PENG: Ja. Sie können einfach, in Ihrem Kommentar, Sie zitieren, wie, oh, von yada genommen, yada, yada, Hash-Funktion. Jedermann haben alle mögliche Fragen? Wir haben eigentlich breezed Durchschnitt heute. Ich werde hier sein, beantworten Fragen auch. 

Auch, wie gesagt, im Büro Stunden heute Abend und morgen. Die Spezifikation dieser Woche ist eigentlich super einfach und sehr kurz, um zu lesen. Ich würde vorschlagen, einen Blick, nur Lesen durch die Gesamtheit davon. 

Und Zamyla tatsächlich führt Sie durch jede der Funktionen Sie brauchen, um zu implementieren, und so ist es sehr, sehr klar, wie alles zu tun. Nur um sicherzustellen, dass Sie Verfolgen von Zeigern. Dies ist eine sehr herausfordernde psoll. 

Es ist nicht schwierig, weil, wie, oh, sind die Konzepte so viel mehr schwierig, oder Sie lernen müssen so viel neue Syntax der Weg dass Sie für die letzte pset taten. Diese pset ist schwierig, weil es gibt so viele Zeiger, und dann ist es sehr, sehr einfach, einmal Sie einen Fehler in Ihrem Code haben, nicht in der Lage sein, um herauszufinden, wo die Fehler ist. 

Und so vollständige und vollkommene Vertrauen in Sie Jungs, dass wir unsere [unverständlich] zu schlagen Schreibweisen. Ich habe eigentlich keine schriftliche Mine noch nicht, aber ich bin zu mir zu schreiben. So, während Sie schreiben Ihnen, ich werde das Schreiben meiner. Ich werde versuchen, Bergwerk schneller als deine. Wir werden sehen, wer am schnellsten man hat. 

Und ja, ich werde alle zu sehen ihr hier am Dienstag. Ich werde eine Art wie ein pset Werkstatt ausgeführt werden. Alle Abschnitte dieser Woche sind pset Workshops, so euch viele Möglichkeiten haben, um Hilfe, der Bürozeiten wie immer, und ich freue mich darauf, liest alle Codes Ihren Jungs. Ich habe Tests hier, wenn Sie Jungs wollen kommen zu denen. Das ist alles.