DAVID MALAN: Alles klar. Willkommen zurück auf CS50. Dies ist der Beginn der 8. Woche. Und daran erinnern, dass Problem Satz 5 beendet mit ein bisschen eine Herausforderung. Also vorausgesetzt, Sie wieder alle Ihre Lehre Fellows und CA Fotografien in der Datei card.raw, sind Sie berechtigt, Bisher finden all jene Menschen, und ein glücklicher Gewinner mit nach Hause ein Fuß diese Dinge, der Sprung Bewegung Gerät, das Sie für einen endgültigen Verwendungszweck Projekte, zum Beispiel. 

Dieser wird jedes Jahr, führt zu ein bisschen Grusel. Und so, was ich dachte, ich würde tun Aktie mit Ihnen einige der Noten, die haben hin und her gegangen die Liste der Mitarbeiter der spät. Zum Beispiel, nur letzte Nacht, Zitat unquote, von einem der Mitarbeiter Mitglieder: "Ich hatte gerade ein Student Klopfen an meine Tür, um ein Foto mit mir. Stalkers, sage ich Ihnen. "Started off ziemlich beschreibend und dann zogen wir auf, eine Stunde oder so später, "Ich hatte eine Student wartet auf mich nach dem Abschnitt und er hatte alle unsere Namen und Fotos auf einigen Blatt Papier. "alles in Ordnung. So organisiert, aber nicht alles, was gruselig noch. 

Dann: "Ich war nicht in der Stadt an diesem Wochenende, und als ich zurückkam, gab es eine in meine Schlafzimmer. "[Gelächter] DAVID MALAN: Nächstes Zitat aus einem Personal Mitglied, "ein Schüler kam zu meinem Haus an Somerville um 4 Uhr heute Morgen. "Next Mitarbeiter: "Ich habe zu meinem Hotel in San Francisco und ein Student wartete mich in der Lobby mit drei DSLRs. " Art der Kamera. "Ich bin nicht einmal auf die Mitarbeiter in diesem Semester, aber ein Student brach in mein Haus in diesem Morgen und nahm die ganze Sache mit Google Glass. "Und dann schließlich, "Mindestens 12 Leute waren eifrig wartet für mich, wenn ich aus meinem limo, und dann habe ich aufgewacht. "In Ordnung. Also unter den Fotos, wie Sie vielleicht erinnern, sind dieser Kerl hier, die Sie könnte als Milo Banane, lebt wissen mit Lauren Carvalho, unser Kopf Lehr-Fellow. Milo, Milo, komm her Junge. Milo. Milo. Wohlgemerkt, er trägt Google Glass, so Wir zeigen Ihnen, all dies nach. Also das ist Milo, wenn Sie möchten, nehmen Sie ein Foto mit ihm hinterher. Wenn Sie möchten, schauen auf das Publikum dort. OK. Das ist eine gute Aufnahmen. Nun, Milo Banana. Oh, tun Sie das nicht. 

[Gelächter] 

OK. So ein Wort dann auf das, was vor uns liegt, weil, wie wir den Übergang beginnen, diese Woche speziell von C in eine Kommandozeilen-Umgebung, um PHP und JavaScript und SQL und HTML und CSS in eine web-basierte Umgebung, werden wir stattet Sie mit allen mehr Wissen für Potenzial letzten Projekte. Mit diesem Ziel hat das natürlich eine Tradition der Abhaltung von Seminaren, welche sind auf tangential Themen zum Kurs. Sehr zur Programmierung und zum Zusammenhang App-Entwicklung und so weiter, aber nicht unbedingt erforscht den Kurs der eigenen Lehrplan. 

Also, wenn Sie Interesse an einem oder mehr der diesjährigen Seminare, registrieren Sie sich bei cs50.net/seminar. Es gibt ältere Seminare bei cs50.net/seminars. Und auf dem Dienstplan bisher für dieses Jahr Erstaunlich sind Web Apps mit Ruby on Schienen, die eine Alternative ist Sprache PHP. Computerlinguistik. Einführung in iOS, die das ist Plattform, die für das iPhone verwendet hat und iPad Entwicklung. JavaScript für Web-Apps, wir decken , aber in diesem Seminar erfahren Sie, gehen in mehr Detail. 

Leap Bewegung, so dass wir tatsächlich haben einige von unseren Freunden von Leap Motion das Unternehmen selbst, besuchen Sie uns. Morgen, in der Tat, um ein Hands-on Seminar, wenn für Sie von Interesse. Meteor.js, eine alternative Technik zum Verwendung von JavaScript im Browser nicht, sondern auf einem Server. Node.js, was sehr viel ist in dieser Art auch. Sleek Android-Entwurf. Android ist eine sehr beliebte Alternative iOS und Windows Phone und andere mobile Plattformen. Und Web Security Active Defense. 

Also in der Tat, wenn Sie möchten, in diese eingreifen, lassen Sie mich notieren Sie sich diese. Wir sind sehr glücklich zu sagen, dass unseren Freunden bei Leap Bewegung, die ein Startup ist - dieses Gerät wirklich nur kam vor ein paar Monaten - hat freundlicherweise 30 solcher Geräte gespendet der Klasse für so viele Schüler, wenn Sie möchten, dass die Hardware ausleihen Richtung Semester Ende und verwenden Sie es für eine tatsächliche endgültige Projekt. Sie unterstützen eine Reihe von Sprachen. Keiner von ihnen C, keine von ihnen PHP, so erkennen, eine oder mehrere dieser Seminare von Interesse zu beweisen. Und alle von ihnen werden in gefilmt werden das Ereignis, dass Sie nicht in der Lage persönlich teilnehmen. Der Zeitplan über bekanntgegeben E-Mail, da wir Zimmer zu verfestigen. 

Und schließlich, wenn Sie gehen, um projects.cs.50.net, ist dies eine Website pflegen wir jedes Jahr, dass wir laden Leute aus der Gemeinde, Fakultät, Abteilungen, Personal, und beide in einer Außenseite des CS50 bis schlagen Projektideen. Aktivitäten von Interesse Schülergruppen. Aktivitäten von Interesse Abteilungen. Also es drehen, wenn Sie zu kämpfen haben mit Unsicherheit darüber, was Sie Sie möchten zu bewältigen. 

So letzte Mal haben wir ein wohl eingeführt komplexere Datenstruktur als würden wir gesehen in Wochen Vergangenheit. Wir hatten bisher mit Arrays ziemlich glücklich als nützlich, wenn vereinfachende Datenstruktur. Dann stellten wir diese, die natürlich sind Listen verbunden. Und was war einer der Beweggründe für Einführung dieser Datenstruktur? Ja? Was ist das? 

ZUSCHAUER: Dynamische Größe. 

DAVID MALAN: Dynamische Größe. Während also in der Reihe, müssen Sie wissen seine Größe im Voraus, wann Sie ordnen es. In verketteten Liste, die Sie nicht müssen wissen, dass. Sie können nur malloc, oder allgemeiner, zuteilen eine zusätzliche Knoten, so zu sprechen, wann immer Sie wollen mehr Daten einzufügen. Und Knoten hat keine Bedeutung vorgegeben. Es ist nur ein Oberbegriff für eine Art Container, wir sind mit in unsere Datenstruktur zu speichern einige Artikel von Interesse, die in diesem Fall passieren, um ganze Zahlen sein. 

Aber es gibt immer ein Kompromiss. So bekommen wir dynamische Größen der Daten Struktur, aber welchen Preis wir zahlen? Was ist die Kehrseite der verknüpften Listen? Ja? 

ZUSCHAUER: Benötigt mehr Speicher. 

DAVID MALAN: Es erfordert mehr Speicher, wie genau? 

ZUSCHAUER: [unverständlich]. 

DAVID MALAN: Genau. So, jetzt haben wir Zeiger Aufnahme zusätzlichen Speicher, die wir vorher nicht brauchen, weil der Vorteil einer Anordnung, selbstverständlich ist, dass alles ist zusammenhängend zurück auf Rücken an Rücken, die gibt Ihnen wahlfreien Zugriff. Denn nur durch eckige Klammer Notation oder mehr technisch Zeiger Arithmetik, sehr einfache Addition, können Sie auf einem Elemente in konstanter Zeit. Und in der Tat ist diese Art von anspielend auf ein weiterer Preis, den wir mit einem zahlen sind verketteten Liste. 

Was passiert mit der Laufzeit etwas wie Suche, wenn ich will finden einen gewissen Wert und innen einer verknüpften Liste? Was macht meine Laufzeit werden? Big O n. Wenn es zu sortieren? Was passiert, wenn die Datenstruktur ist sortiert? Kann ich besser als große O von n zu suchen? Nein, denn im schlimmsten Fall kann es sehr gut sortiert, aber die Anzahl Sie könnten große suchen. Es könnte die Zahl 100, die sein passieren könnte, um all sein der Weg am Ende. Und da kann man nur auf eine verknüpfte Liste in dieser Ausführung durch Weg von den ersten Knoten, du bist trotzdem irgendwie kein Glück. Du musst die ganze Sache durchziehen vom ersten bis zum letzten, um zu finden so groß wie 100 Wert. Oder um festzustellen, ob es nicht einmal dort. 

So können wir nicht tun, was Algorithmus in einem Daten- Struktur, das aussieht wie das? Wir können nicht binäre Suche, weil binäre Suche erforderlich, die wir hatten Direktzugriffsspeicher. Wir könnten einfach von Ort zu springen Lage ohne folgen diese Brotkrumen in Form all dieser Zeiger. 

Nun, wie wir diese umsetzen? Nun, wenn wir auf den Bildschirm gehen Sie hier, wenn können wir schnell reimplementieren diese Daten Struktur - meine Handschrift ist nicht alles, toll hier, aber wir werden versuchen. So typedef struct, und was habe ich will dieses Ding nennen hier? Node. Also werde ich uns begonnen. Und nun, was braucht, um in der sein die Datenstruktur für die einzeln verketteten Liste? Wie viele Felder? 

Also zwei. Eines ist recht einfach. So int n. Und wir nennen könnte n, was wir wollen, aber es sollte ein int sein, wenn wir Implementierung einer verketteten Liste für ints. Und nun, was macht die zweite Feld sein? Struct node *. Also, wenn ich struct node *, und dann habe ich kann dies auch, was ich will rufen, aber nur klar zu sein Ich rufe daneben, als wir getan haben. Und dann werde ich schließe meine geschweiften Klammern. 

Und nun, wie beim letzten Mal, Ich legte Knoten hier unten. Aber wenn ich erklärte dies als Knoten, warum ich mir die Mühe wird so ausführliche Erklärung hier in struct node * next, im Gegensatz nur node * next? Ja? 

ZUSCHAUER: [unverständlich]. 

DAVID MALAN: Genau. Genau. Weil C wirklich braucht man buchstäblich und sieht nur die Definition der Knoten Weg hier unten, kann man nicht finden Sie es hier. So haben wir diese Art von Präventivschlag Erklärung hier, die zugegebenermaßen ausführlicher. Struct Knoten, das heißt wir können jetzt zugreifen innerhalb der Datenstruktur. 

Und so nebenbei, denn dies ist immer ein wenig mehr subjektive jetzt der Stern kann technisch hier gehen, kann es hier gehen, kann es auch in der Mitte gehen. Wir haben angenommen, in der Styleguide für Der Kurs, der Konvention, der Stern rechts neben den Daten Typ, der in diesem Fall würde struct Knoten sein. Aber in vielen Lehrbüchern zu realisieren und Online-Referenzen, könnte man in der Tat sehen es auf der anderen Seite. Aber nur erkennen, dass beide tatsächlich arbeiten, und Sie sollten einfach sein konsistent. 

In Ordnung. Das war also unsere Erklärung von struct Knoten. Aber dann haben wir angefangen, mehr anspruchsvolle Dinge. Zum Beispiel haben wir beschlossen, die Einführung so etwas wie eine Hash-Tabelle. So, hier ist eine Hash-Tabelle der Größe n, indiziert von 0 auf links oben nach n minus 1 auf der unten links. Dies könnte ein Hash sein Tabelle für alles. Aber welche Arten von Dingen haben wir reden über die Verwendung einer Hash-Tabelle für? Speichern, was? 

Namen. Wir konnten Namen wie zu tun wir haben letzten Zeit. Und wirklich, können Sie speichern alles. Und wir werden diese wieder zu sehen in PHP und in JavaScript. Eine Hash-Tabelle ist eine schöne Art von Swiss Taschenmesser, die Sie speichern können ziemlich viel, was Sie im Inneren des Mangels es durch Zuordnung Schlüssel mit Werten. Keys mit Werten. 

Jetzt in diesem einfachen Fall unsere Tasten sind nur Zahlen. Wir Implementierung eines Hash Tabelle als ein Array. Und so sind die Tasten 0, 1, 2, und so weiter. Und so haben wir, als Menschen, entschied letzten Woche, dass Sie wissen, was, wenn wir werde store Namen, lass uns einfach willkürlich, aber ziemlich vernünftig, annehmen, dass Alice eine mit Namen, wird nur in 0 indiziert werden. Und Bob, ein B Name, indiziert werden in 1, und so weiter. Also mussten wir eine Zuordnung zwischen den Eingängen, die Strings sind, und der Hash- Standorte, die Zahlen sind. 

Damit wird im allgemeinen bekannt als eine Hash-Funktion, und man kann wirklich Umsetzung es im Code. Wenn ich wollte, um einen Hash-Funktion zu implementieren das tut genau das, was wir nur vom letzten Mal beschrieben, könnte ich deklarieren eine Funktion, die, nimmt als Eingang zum Beispiel - und lasst uns dies tun auf diese Bildschirm hier. Wenn ich wollte, um einen Hash zu implementieren Funktion, könnte ich sagen, etwas wie dieses. 

Es geht um einen int zurück. Es wird als Hash werden, und es ist werde als Argument einer akzeptieren String, oder wir können mehr richtigen jetzt, und sagen, char *, wir nennen es s. Und dann all diese Funktion zu tun hat, letztlich wird zurückgeben int. Nun, wie es das könnte nicht so klar. Ich werde diese ohne Umsetzung Form der Fehlerprüfung zeigen. Ich werde einfach blind zu sagen, zurück was auch immer ist s Bracket 0, Minus, sagen wir mal, die Hauptstadt ein Semikolon. 

Völlig gebrochen. Es ist nicht perfekt, weil ein, was ist, wenn s ist null? Schlimme Dinge passieren werden. Zwei, was ist, wenn der erste Buchstabe in dieser Name ist nicht ein Großbuchstabe? Das wird nicht zu drehen aus gut entweder. Es könnte ein Kleinbuchstabe sein oder nicht ein Brief überhaupt. So völlig Raum für Verbesserungen hier aber dies ist die Grundidee. 

Was wir beschrieben, wie letzte Woche mündlich nur ein Prozess des Abbildens Alice 0 und Bob Anspruch 1 ausgedrückt werden kann, sicherlich mehr formelhaft als C funktionieren hier. Genannt wieder Hash, braucht eine Zeichenkette als Eingang, und dann irgendwie etwas tut mit dem Eingang, um ein Ausgangssignal zu erzeugen. Nicht anders als unsere black box Beschreibung dass wir schon lange getan. Ich weiß nicht, wie dies könnte arbeitet unter der Haube. 

Zum problemlosen Satz 6, eine der Herausforderungen ist für euch zu entscheiden, was Ihre Hash-Funktion sein? Was wird in dieser schwarz sein Feld, und vermutlich wird es eine sein wenig interessanter als diese, und definitiv mehr fehleranfällig Überprüfung als diese besondere Umsetzung. 

Aber Probleme auftreten können, nicht wahr? Wenn wir eine Datenstruktur wie diese ein, was ist eines der Probleme, Sie können in der Zeit laufen, wie Sie einfügen mehr und mehr Namen in der Hash-Tabelle? Sie erhalten Kollisionen, nicht wahr? Was, wenn Sie haben Alice und Aaron, zwei Personen, deren Namen passiert mit A anfangen? Das wirft die Frage auf, wo man legte den zweiten einen solchen Namen? 

Nun, könnte man naiv nur ihn wo Bob gehört, aber dann ist Bob Art verschraubt, wenn Sie versuchen, einfügen seinen Namen neben und es gibt keinen Platz für ihn. So könnten Sie legte Bob, wo Charlie ist, und Sie können diese sehr schnell vorstellen zufallenden in ein bisschen ein Durcheinander. Etwas linear am Ende, wo man müssen nur die ganze Sache zu suchen Suche nach Alice oder Bob oder Aaron oder Charlie. 

Anstatt also haben wir vorgeschlagen, statt nur linear Sondieren für Freiflächen und Plopp die Namen da, wir schlug ein schicker Ansatz. Eine Hash-Tabelle noch mit einem umgesetzt Array von Indizes, aber der Datentyp diese Indizes jetzt waren Zeigern. Zeiger auf was? Zeiger auf verkettete Listen. 

Denn daran erinnern, dass eine verlinkte Liste ist wirklich nur ein Zeiger auf einen Knoten, und der Knoten eine nächste Feld, und dieser Knoten eine nächste Feld, und so weiter. So können Sie jetzt von diesem Array denken auf die linke Seite einer Hash-Tabelle als was zu einer verketteten Liste. Der Vorteil davon ist, wenn Sie eine bekommen Kollision zwischen Alice und Aaron, was meinst du mit dem zu tun zweite solche Person? Sie müssen nur befestigen ihn oder sie zu der Ende, oder auch der Beginn dieser verknüpften Liste. 

Und tatsächlich, lass uns einfach Nudel durch dass nur für eine Sekunde. Wo würde am meisten Sinn? Wenn ich einfügen Alice und sie endet am die erste Stelle, dann versuche ich, legen den Namen Aarons, und es gibt offensichtlich eine Kollision, sollte ich ihn am Anfang der verketteten Liste? Das ist bei dieser ersten Stelle oder am Ende? 

ZUSCHAUER: [unverständlich]. 

DAVID MALAN: OK. Ich habe gehört, am Anfang. Warum am Anfang? 

ZUSCHAUER: [unverständlich]. 

DAVID MALAN: OK. Es ist alphabetisch, so das ist schön. Das ist eine gute Eigenschaft. Es erspart mir etwas Zeit möglicherweise. Es lässt mich nicht tun binäre Suche, aber ich könnte zumindest in der Lage sein, um aus einer Schleife, wenn ich merke, gut, ich bin so Vergangenheit waren Aaron würde dies sortiert verketteten Liste. Ich habe nicht meine Zeit damit verschwenden suchen den ganzen Weg bis zum Ende. Also das ist vernünftig. Warum sonst könnten Sie einfügen möchten der Name an den kollidierenden Anfang der Liste? Was ist das? 

ZUSCHAUER: [unverständlich]. 

DAVID MALAN: Es könnte eine lange Zeit in Anspruch nehmen bis zum Ende der Liste zu erhalten. Und in der Tat, länger und länger. Je mehr Namen, die Sie einsetzen, dass beginnen mit A, die länger als Kette wird zu bekommen. Je länger verbunden Liste wird zu bekommen. Sie sind also wirklich nur Ihre Zeit verschwenden. Vielleicht bist du besser dran Aufrechterhaltung konstant Einsetzen Zeit, groß O von 1, durch ständig die Kollision Namen an der Beginn der verketteten Liste, und nicht so viel Sorgen über das Sortieren. 

Was ist die beste Lösung? Es ist unklar. Es Art von abhängt, was der Verteilung ist, was das Muster ist der Namen Sie einfügen. Es ist nicht unbedingt eine offensichtliche Antwort. Aber hier ist wiederum ein Design-Chance. 

Also schauten wir uns dieser Sache, die ist wirklich die andere große Chance für p-Set 6. Und klar, wenn Sie nicht über bereits, Zamyla taucht in diese beiden, Hash Tabellen und versucht, im Detail. Und die Video-Anleitung ist eingebettet in p-Set spec. Dies war ein Trie - T-R-I-E. Und was war interessant zu war, dass die Laufzeit der Suche nach einem Namen, wie Maxwell letzten Mal, war groß O von was? Was ist das? 

ZUSCHAUER: Die Anzahl der Buchstaben. 

DAVID MALAN: Anzahl der Buchstaben. Ich hörte zwei Dinge. Anzahl der Buchstaben und konstante Zeit. Lassen Sie uns also mit dem ersten zu gehen. Die Anzahl der Buchstaben. Nun, das ist diese Datenstruktur, Rückruf, Wie ein Baum, ein Stammbaum, der sich dessen Knoten aus Arrays hergestellt. Und diese Anordnungen sind Zeiger auf anderen derartigen Knoten oder andere derartige Arrays in den Baum. 

Also, wenn wir wollten dann bestimmen ob Maxwell in hier ist, ich könnte gehen auf das erste Array, an der Spitze der der Baum, der sogenannten Wurzel, Spitze die Trie, und folgen Sie dann den Zeiger m, dann ein Zeiger, dann x, w, e, l, l. Und dann, wenn ich sehe einige Sonderzeichen, hier als Dreieck bezeichnet. In Code, den Sie sehen, wir schlagen vor, dass Sie implementiert als bool, nur ja zu sagen oder nein, stoppt ein Wort hier. 

Nun, wenn wir zu M-A-X-W-E-L-L gegangen, fühlt sich an wie sieben, vielleicht acht, wenn wir gehen noch einen an ihm vorbei, acht Schritte, um Maxwell finden. Oder nennen wir es K. Aber erinnern letzten Zeit habe ich argumentiert, dass, wenn es realistisch eine maximale Länge für ein Wort, wie 40-some-ungerade Zeichen ein Maximale Länge impliziert ein konstanter Wert. Also wirklich, ja, es ist technisch big O von 8 oder 7, oder wirklich große O von K. Aber wenn es eine endliche Kappe auf, was K könnte sein, es ist eine Konstante. Und so ist es groß O von 1 bei das Ende des Tages. 

Nicht in der realen Welt. Nicht, wenn Sie tatsächlich beginnen beobachten Ihre Uhr als Ihr Programm läuft. Es ist absolut werde ein bisschen langsamer als wirklich konstant Zeit mit einem Schritt. Es geht um sieben oder acht Schritte sein, aber das ist viel, viel besser als einem Algorithmus wie große O von n, dass hängt von der Größe von dem, was in der Datenstruktur. 

Beachten Sie die auf den Kopf hier ist, können wir einfügen eine Million mehr Namen in dieser Datenstruktur, aber wie viele weitere Schritte wird es um uns zu finden Maxwell in diesem Fall? Keine. Er ist unberührt. Und bis heute weiß ich nicht denke, dass wir gesehen haben, ein Beispiel einer Datenstruktur oder eines Algorithmus, der vollständig war unbeeinflusst von externen Verhaltensweisen wie die. Aber das kann nicht sein erstaunlich. Dies kann nicht die einzige Lösung sein für die p-Set 

Und es ist nicht. Dies ist nicht unbedingt die Daten Struktur sollten Sie tendieren, denn wie Hash-Tabellen, Kompromiss. Was ist der Preis, den Sie zahlen hier? Speicher. Ich meine, das ist eine grauenhafte Speichergröße. Und man kann nicht ganz sehen es hier, weil der Autor dieses Bild offensichtlich abgeschnitten alle Arrays und wir sehen nicht viel von A und die B und C ist und Q und Y des und Z die in diesen Arrays. Aber sie sind da. 

Jeder dieser Knoten ist eine ganze Reihe von ca. 26 oder mehr Bytes, die jeweils was einen Brief. 27 in unserem Fall, so dass wir Sie unterstützen Apostrophe in der Problem-Set. Also diese Datenstruktur ist wirklich, wirklich dicht und breit. Und das allein könnte am Ende verlangsamt Dinge nach unten, oder zumindest kostet Sie ein viel mehr Platz. Aber auch hier können wir ziehen Vergleiche hier. 

Rufen Sie eine Weile zurück, erreichten wir viel spannender Laufzeit in Sortieranlagen wenn wir merge sort, aber den Preis wir zahlten zu erreichen n log n für Merge Art erforderlich, dass wir verbringen mehr, was Ressource? Mehr Platz. Wir brauchten eine sekundäre Array kopieren Menschen in, genau wie wir haben hier auf der Bühne. Also noch einmal, keine klaren Gewinner, sondern nur subjektive Design Entscheidungen getroffen werden. 

In Ordnung. So wie etwa das? Wer erkennen, welche D-Hall? OK. Also drei von uns tun. Mather House. Also das ist für Mather Speisesaal. Ich wette, alle Säle haben Plattenstapel wie diese. Und dies ist tatsächlich repräsentativ von etwas, das wir offensichtlich schon gesehen. Wir nannten es buchstäblich einen Stapel. Und der Stapel, in Bezug auf Ihre Arbeitsspeicher des Computers ist, wo Daten geht während Funktionen werden aufgerufen. 

Zum Beispiel, gehen Sie, welche Arten von Dingen auf dem Stapel mit Bezug auf die Speicher-Layout wir besprochen haben in Wochen Vergangenheit? Was ist das? 

ZUSCHAUER: Anrufe zu den Funktionen. 

DAVID MALAN: Tut mir leid. 

ZUSCHAUER: Anrufe zu den Funktionen. 

DAVID MALAN: Anrufe auf Funktionen, aber speziell, was drin ist jeder diese Rahmen? Welche Dinge? Ja. So lokalen Variablen. Jederzeit wir brauchten einige lokale Speicherung, wie ein Argument oder int I oder int temp, oder was auch immer die lokale Variable wird, waren wir in der setzen, dass auf den Stapel. Und wir nennen es ein Stapel, weil dieser Schichtung Idee. Nur irgendwie Begegnungen mit der Realität, das Konzept davon. 

Aber es stellt sich heraus, dass ein Stapel kann auch als Datenstruktur zu sehen ist, ein Alternativ zu einer Anordnung, eine alternative eine verknüpfte Liste. Etwas konzeptionell interessanter das kann noch unter Verwendung entweder von denen Dinge, aber es ist eine andere Art von Datenstruktur unterstützen, wirklich, nur zwei Operationen. Aber man kann auf fancier hinzufügen Eigenschaften als diese. Aber das sind die Grundlagen - Push-und Pop. 

Und die Idee, mit einem Stapel ist, dass, wenn ich hier haben, mit oder ohne Annenberg wissen, ein Tablett von nebenan mit der Nummer 9 auf sie. Also einfach ein int. Und ich möchte diese auf die Daten-Push Struktur, die derzeit leer. Betrachten dieses den Boden des Stapels. Ich würde diese Nummer 9 auf die Push- stapeln, und jetzt ist es genau dort. 

Aber das Interessante an einem Stapel ist, dass wenn ich jetzt möchte schieben einen anderen Wert, wie 17, und ich schiebe diese auf den Stapel, werde ich tun das einzige intuitive Sache, ich werde einfach um es in Ordnung zu bringen, wo wir Menschen wäre geneigt, es ausdrückte, an der Spitze werden. Aber was ist nun interessant ist, wie kann ich bei 9 zu bekommen? Du weißt, ich nicht ohne eine gewisse Anstrengung. 

Also, was ist interessant ein Stapel ist, dass durch Design, es ist eine LIFO-Datenstruktur. Dummer Weise der Beschreibung last in, first out. Also die letzte Zahl in war zu dieser Zeit 17. Also, wenn ich etwas Pop-off des Stapels kann es nur 17 sein. So gibt es eine verbindliche Bestellung für Operationen hier, wo das letzte Element in hat das erste aus sein. Daher die Abkürzung, LIFO. 

Warum könnte dies nützlich sein? Sind ihre Kontexte, in denen Sie würden wollen eine Datenstruktur wie diese? Nun, es ist sicherlich nützlich gewesen innerhalb eines Computers. So Betriebssysteme verwenden diese deutlich Art der Datenstruktur für Stapel. Wir werden auch sehen, die gleiche Idee wenn es um Web-Seiten. So diese Woche und nächste Woche und darüber hinaus und wie Sie starten Implementierung von Web Seiten in einer Sprache namens HTML, können Sie tatsächlich eine Datenstruktur wie Diese zu ermitteln, ob die Seite ist richtig formatiert. Denn wir sehen werden alle Web-Seiten folgen eine Art von Hierarchie, eine Vertiefung das wird am Ende des Tages, ein sein Baumstruktur unter der Haube. Also mehr auf, dass in nur ein bisschen. 

Aber jetzt lassen Sie uns für eine vorschlagen Moment, wie könnten wir gehen darstellen, was ein Stack ist? Lassen Sie mich vorschlagen, dass wir implementieren ein Stapel mit Code wie diesen. So ein Stapel wird in der es haben zwei Dinge, ein Array genannt Tabletts, nur im Einklang mit der Demo. Und jedes der Elemente in diesem Array wird ein Typ int sein. Und Kapazität ist vermutlich, was? Weil ich nicht die schriftliche vollständige Definition hier. 

Es ist wohl das Maximum Größe des Arrays. Und es ist wohl als eine scharfe erklärt definieren am Anfang der Datei, einige Art konstant an der impliziten die bloße Aktivierung. Also irgendwo Kapazität definiert ist als die maximal mögliche Größe. In der Zwischenzeit innerhalb der Datenstruktur bekannt als Stapel wird es eine ganze Zahl nur bekannt, einfach als Größe. 

Also wenn ich jetzt, um dies darzustellen bildhaft, nehmen wir an, dass diese gesamte Black Box stellt mein Stack. Innerhalb von zwei Variablen ist es. So werde ich das Zeichnen erste als Größe. Und das zweite, ich werde als ein Array zu ziehen. 

Aber nur, um die Dinge ordentlich, normalerweise würde ich ein Array wie zeichnen , aber es ist irgendwie schön wenn wir der Realität entsprechen, oder entsprechen den mentalen Modells. Also lassen Sie mich stattdessen ziehen das Array vertikal, ist die gerade wieder künstlerische Darstellung. Spielt keine Rolle, was es ist unter der Haube. Und wir sagen, dass in der Standardeinstellung Kapazität wird drei sein. So wird dies Lage 0, dies wird Standort 1, dies wird Standort 2 sein. 

Wenn ich bestechen mit einem Stress-Ball, würde jemand wie zu kommen und führen die Board hier nur für einen Moment? OK, habe Ihre Hand zuerst. Komm up. In Ordnung. Also ich glaube, es ist Steven. Komm up. In Ordnung. 

Aber nehmen wir jetzt zurückspulen, um die anfängliche Zustand der Welt, wo ich haben gerade erklärt, einen Stapel, und es ist werde der Kapazität drei sein. Aber Größe ist noch nicht bestimmt worden. Trays ist noch nicht bestimmt worden. So ein paar Fragen zuerst. Und lassen Sie mich Ihnen mic so können Sie teilhaben mehr aktiv in diese. 

Also, was ist in der Größe in diesem Moment in der Zeit, wenn alles, was ich getan habe, ist deklariert einen Stapel mit eine Zeile Code? 

STEVEN: Nicht viel. 

DAVID MALAN: OK, nicht viel. Wissen wir, was drin ist von ihrer Größe, wir wissen, was drin ist dieses Arrays hier? 

STEVEN: Just Random-Code, nicht wahr? Just - 

DAVID MALAN: Yeah, ich bin zu gehen nennen es Code, aber zufällig - 

STEVEN: Things. 

DAVID MALAN: Dinge wie zufällig 

STEVEN: Bits. 

DAVID MALAN: Bits, nicht wahr? So Müll Werte, nicht wahr? So Permutationen von 0 und 1 ist. Reste der früheren Nutzungen dieses Speichers. Und wir wissen nicht wirklich, was die Werte werden, so dass wir in der Regel ziehen sie als Fragezeichen. 

Das erste, was wir sind vermutlich gehen zu wollen, zu tun - und lassen Sie mich dieses Feld im Inneren von dort einen Namen - Tabletts. Was sollten wir vermutlich initialisieren Größe, wenn wir wollen starten Sie mit diesem Stack? 

STEVEN: Tray ist sub 3. 

DAVID MALAN: So, OK. Um klar zu sein, wird die Kapazität erklärt an anderer Stelle als drei. Und das ist, was ich benutzt habe das Array bereitzustellen. Größe wird zu entnehmen, wie viele Tabletts sind derzeit auf dem Stapel. 

STEVEN: Null. 

DAVID MALAN: So sollte es Null sein. So gehen Sie vor, und mit jedem Finger, ziehen Sie eine Null in der Größe. In Ordnung. So, jetzt, was drin ist dies hier, wissen wir nicht. Diese sind wirklich nur Müll Werte. So konnten wir ziehen Fragezeichen, aber wir halten das Board sauber für jetzt weil es keine Rolle, was da ist. Wir brauchen nicht, um das Array zu initialisieren nichts, denn wenn wir wissen, dass die Größe des Stapels Null ist, na ja, wir sollte nicht auf etwas zu suchen in Dieses Array sowieso an Dieser Zeitpunkt. 

So, jetzt annehmen, dass ich schiebe die Nummer 9 auf den Stapel. Wie sollen wir aktualisieren die Datenstruktur Innere dieser Black Box? Welche Werte ändern müssen? 

STEVEN: Innerhalb - die Größe? 

DAVID MALAN: OK. Größe was soll werden? 

STEVEN: Größe würde man. 

DAVID MALAN: OK. Also Größe sollte eins werden. So können Sie diese in ein paar Möglichkeiten. Lassen Sie mich Ihnen nun Ihre Finger ist ein Radiergummi. In Ordnung. Dann jetzt Ihren Finger ist ein Pinsel. In Ordnung. Und jetzt was muss sich ändern, offensichtlich, in der Datenstruktur? 

STEVEN: Wir gehen von Boden bis zu 9. 

DAVID MALAN: 9. OK, gut. So still ist egal, was auf dem Standort ein oder zwei weil sie Müll-Werte, aber wir sollten nicht die Mühe suchen dort, weil Größe ist sagt uns, dass nur das erste Element ist eigentlich legitim. So, jetzt schiebe ich 17 auf der Liste. Was passiert mit diesem Bild? 

STEVEN: Also Größe wird zu beiden gehen. 

DAVID MALAN: OK. Du bist Radiergummi - oops. Du bist ein Radiergummi. 

STEVEN: Eraser. 

DAVID MALAN: Du bist ein Pinsel. 

STEVEN: Pinsel. 

DAVID MALAN: OK. Und was noch? 

STEVEN: Und dann haben wir - 

DAVID MALAN: Wir schoben 17. 

STEVEN: Wir halten 17 an der Spitze, so - 

DAVID MALAN: OK, gut. 

STEVEN: - Drop it down. 

DAVID MALAN: Alles klar. Es ist immer einfach. Ich werde nicht zu helfen, Sie diese Zeit. Drücken Sie 22. 

STEVEN: Fertig. Werden Sie ein Radiergummi. Ich bin immer ein Pinsel. Und dann habe ich setze 22. 

DAVID MALAN: 22. Sep. Excellent. Also noch einmal. Ich gehe jetzt zu schieben auf den Stapel 26. 

STEVEN: Ooh. Oh Gott. Du bist wirklich erwischte mich unvorbereitet. 

DAVID MALAN: Sie haben nicht kommen sehen? 

STEVEN: Ich habe nicht kommen sehen. Könnten wir wieder anfänglichen Kapazität? 

DAVID MALAN: Das ist eine gute Frage. Deshalb haben wir uns von uns selbst gemalt Art in einer Ecke hier. Es ist wirklich keine gute für Steven weil wir dieses Array zugewiesen statisch, so zu sprechen, innen der Datenstruktur. Und wir haben im Wesentlichen hart codiert es von der Größe drei. So können wir nicht wirklich umzuschichten es. 

Wir könnten, wenn wir wieder in, wir umdefiniert Tabletts ein Zeiger, dass sein wir dann malloc zur Hand Speicher. Denn wenn wir den Speicher von der Haufen über malloc, wir könnte dann befreien sie. Doch bevor es zu befreien, könnten wir umzuschichten einen größeren Teil des Gedächtnisses, Aktualisieren des Zeigers, und so weiter. Aber für jetzt, das ist wirklich das Beste was wir tun können. Push-und Pop sind vermutlich gehen zu haben, um einige Fehler zu signalisieren. 

So zum Beispiel, Umsetzung unserer von Push zurückkehren konnte eine bool die zuvor zurückgekehrt wahr, true, true. Aber das vierte Mal, es gehen zu müssen false zurück, zum Beispiel. In Ordnung. Sehr gut gemacht. Herzlichen Glückwunsch. Sie haben Ihre Stress-Ball verdient heute. 

[Applaus] 

STEVEN: Danke. 

DAVID MALAN: Danke. OK, so scheint dies nicht viel sein von einem Schritt nach vorn, nicht wahr? Wir beschrieben diese Datenstruktur. Es ist schon überzeugend, oder? Betriebssysteme mag. Offenbar kann die Bahn nutzen diese, und andere Anwendungen noch. Aber was für eine dumme Einschränkung, dass wir Rücken an Art Woche zwei Grenzen wo wir Größe Arrays fixiert. 

So gibt es in der Tat ein paar Möglichkeiten, wie wir dieses Problem lösen könnte. Wir konnten die dynamische Zuordnung des Array, nicht durch harte Codierung, wie ich es haben hier getan, sondern neu erklärt dies, um nur klar sein, wie etwas wie dieses. Int * Tabletts, nicht entscheiden auf eine Kapazität noch. Aber wenn ich erkläre den Stapel anderswo in meinem Code, ich konnte dann rufen malloc, erhalten die Adresse eines Batzen Speicher, und ich konnte zuweisen diese Adresse Tabletts. 

Und dann, weil es nur ein Stück Speicher, konnte ich weiter verwenden Quadrat Klammer-Notation in der üblichen Weise. Denn hier gibt es diese Art von funktionelles Äquivalent von Arrays und Brocken von Speicher, die kommen zurück von malloc. Wir können eine wie die andere behandeln mit Pointer-Arithmetik oder eckige Klammer Notation. Also das ist ein Ansatz. 

Aber wie sonst könnten wir diese umsetzen dieselbe Datenstruktur, möglicherweise? Right? Ich fühle mich wie wir lösen gerade diese Problem wie vor einer Woche. Was war die Lösung für dieses Problem dass Steven lief in? So verkettete Listen, richtig. 

Wenn das Problem ist, dass wir malen uns in eine Ecke durch die Zuweisung im Voraus zu wenig Speicher, dass wir dann haben irgendwie behandeln, gut, warum nicht nur verhindern, dass Ausgabe insgesamt? Warum nicht einfach erklären, Tabletts, ein sein Zeiger auf einen Knoten, ergo eine verlinkte Liste, und dann einfach neue Knoten zuweisen jedes Mal, Steven musste ein passen Anzahl in die Datenstruktur. 

Also das Bild würde sich ändern müssen. Es wird nicht zu sein, wie sauber und wie einfach wie nur ein Array von drei ints. Nun, es wird ein Zeiger auf ein sein struct, und dass struct ist los einen int und eine nächste Zeiger. Es wird dazu führen, über diesen Zeiger zu anderen solchen Struktur zu weitere solche Struktur. So würde das Bild tatsächlich bekommen ein bisschen unordentlicher. Und wir würden haben Pfeile binden alles zusammen. 

Aber das ist in Ordnung, rechts, weil wir haben gesehen, wie dies zu tun. Und wenn Sie es sich bequem Umsetzung etwas wie einer verknüpften Liste, die Sie zu tun haben werde, wenn Sie wählen, um eine Hash-Tabelle mit implementieren getrennte Verkettung für p-Set 6 können Sie verwenden Sie es als Baustein oder eine Zutat oder in Scratch sprechen, ein Verfahren, etwas, dass Sie gesagt, Sie erstellt eigene Puzzleteil die Sie dann wiederverwenden. So Kompromisse, aber mögliche Lösungen dass wir tatsächlich gesehen. 

So oft, sehen Sie dies jeden Jahr oder zwei, wenn Apple veröffentlicht etwas Neues, und all die verrückten Leute line up außerhalb des Apple speichern, um ihre marginal kaufen Upgrade auf Hardware. Ich sage dies, es ist OK, weil Ich bin einer jener Menschen. Also, welche Art von Datenstruktur könnte diese Realität dar? 

Nun, nennen wir es eine Warteschlange, eine Linie. So British würde es in der Regel ein Warteschlange sowieso, also ist es ein schöner Name. Und die beiden Operationen, die eine Warteschlange Die Vertragsparteien unterstützen wir eine enqueue nennen Betrieb und eine dequeue Betrieb die ein analoges Geist zu schieben und Pop. Es ist einfach irgendwie anders Konvention, was wir fordern diese. Aber um etwas bedeutet einreihen hinzufügen oder legen Sie sie auf die Datenstruktur. Um dequeue bedeutet, es zu entfernen. Aber während ein Stapel war ein LIFO-Daten Struktur ist eine Warteschlange ein first in, first out Datenstruktur. 

Wenn Sie sind die erste Person in der Linie, Sie ist die erste Person, um sein aus der Reihe und kaufen Sie Ihr neues Gerät. Stellen Sie sich vor, wie aufgeregt diese Menschen wäre wenn Apple stattdessen verwendet einen Stapel, für Beispiel für die Umsetzung der Kommissionierung up von Ihrem neuen Spielzeug. So Warteschlangen sinnvoll, natürlich, und können wir von allerlei denken Anwendungen vermutlich für Warteschlangen, vor allem, wenn Sie wollen Fairness. Also, wie können wir diese umsetzen als Datenstruktur? 

Nun, schlage ich vor, wir könnten tun müssen, es auf diese Weise. Also werde ich jetzt Zahlen. Also werden wir es einfach halten und nicht unbedingt in Bezug auf Böden sprechen. Nur Zahlen, dass die Menschen bekommen. Die Kapazität wird zu gehen, wieder zu beheben die Gesamtzahl der Menschen, die in sein können diese Linie, wie drei oder unabhängig von anderen Wert. 

Aber ich vorschlagen, dass ich den Überblick zu behalten müssen nicht nur von der Größe des Warteschlange, wie viele Dinge sind in ihm. Also Größe ist die aktuelle Größe, Kapazität ist die maximale Größe. Gerade wieder Nomenklatur durch Konvention. Warum brauche ich eine zusätzliche int innen einer Warteschlange, um zu verfolgen, wer in halten vor der Linie? Warum muss ich, dass in diesem Fall tun? 

Nun, wie ist das Bild wird sich ändern? Ich kann wohl wiederverwenden von diesem Bild. Lassen Sie mich gehen und löschen, was hier ist. Wir geben diese eine leicht anderen Namen hier. Lasst uns loszuwerden, die 17, lasst uns loswerden der 9, lasst uns loszuwerden, die 3. Und fügen wir eine andere Sache. Ich schlage vor, dass ich den Überblick zu behalten müssen die Vorderseite der Liste ist, die gerade werde ein int als gut. Und wir werden es einfach zu halten. Kein verketteten Liste für jetzt. 

Wir gestehen, dass wir zu gehen bump up gegen diesen Grenzwert. Aber was will ich sehen dieses Mal passieren? So nehme ich voran gehen und die erste Person kommt in der Linie, und Es ist die Nummer 9. Wir haben Stress-Bälle. Kann ich stehlen, sagen wir, zwei oder drei Personen? Eins, zwei, drei? Komm up. Rechts von vorne, weil wir machen dieses schnell. 

Jeder von euch wird jetzt sein Fan boy in Linie bei Apple. Sie werden nicht erhalten Apple-Hardware am Ende dieses aber. In Ordnung. So Nummer 9, bist du Nummer 17, Nummer 22. Dies sind willkürliche Zahlen, wie Studentenausweise oder Dingsbums. Und in einem Moment, lassen Sie uns beginnen zu beginnen, die Dinge. Und ich werde das Board hier laufen diese Zeit. 

Also in diesem Fall habe ich initialisiert die Front zu sein - Ich eigentlich nicht wirklich, was die liegt, da die Größe Null ist. So könnte genauso gut sein ein Fragezeichen. Diese sind alle Fragezeichen. So, jetzt fangen wir tatsächlich sehen einige Leute in der Schlange vor dem Laden. 

Also, wenn die Zahl 9, du bist der erste es um 5 Uhr, gehen Sie vor und Line-Up, oder in der Nacht zuvor. OK. So, jetzt 9 ist hier. So 9 ist in der Vorderseite der Liste. Also werde ich weitermachen und aktualisieren die Größe dieser aktuellen Daten Struktur nicht mehr 0 sein, aber auf 1 gesetzt. Ich werde bis 9 auf der Put- vor der Liste. Lassen Sie mich gehen Sie vor und schalten Sie den Bildschirm so können wir an uns vorbei zu sehen. 

Und nun, was will ich um vorne zu setzen? Ich werde den Überblick zu behalten, dass die Vorderseite der Warteschlange jetzt ist an der Stelle 0. Denn was wird als nächstes passieren? Nun, ich nehme jetzt einreihen 17 sowie. So hüpfen in Linie gibt. Und wieder, um die Art von Tür die Speicher wird hier zu sein. So jetzt habe ich am 17. Und obwohl diese Jungs blockieren der Bildschirm, ist das in Ordnung, denn wir sehen es hier. Entschuldigung. 

ZUSCHAUER: Wir bewegen kann - 

DAVID MALAN: Nein, das ist OK. Es ist riesig dort oben. Also 17 ist jetzt in der Warteschlange. Ich brauche, um welches Update Felder jetzt aber? OK, auf jeden Fall groß. Und wie vor? OK, nein. Vorne sollte nicht geändert werden, weil Im Gegensatz zu einem Stapel, wir wollen Fairness halten. Also, wenn 9 in ersten kamen, wollen wir 9 der erste aus der Reihe sein und in den Laden. 

In der Tat, wir sehen, dass. Bevor wir 22 einzufügen, lassen Sie uns gehen Sie vor und dequeue 9. Was ist Ihr Name? 

ZUSCHAUER: Jake. 

DAVID MALAN: Jake wird jetzt dequeued werden. So erhalten Sie in den Laden gehen. Und so tun, dass das Geschäft ist dort drüben. Und was jetzt benötigt - dit-dit-dit! Was muss jetzt passieren? Design-Entscheidung. Also kein schlechter Instinkt, aber - was ist Ihr Name? 

ZUSCHAUER: David. 

DAVID MALAN: David. So was hat David zu tun? Er versuchte, der fix die Daten zu sortieren Struktur und Bewegung von seinem Standort in Jakes ehemaligen Standort. Und das ist in Ordnung, wenn wir bereit sind auf, die als akzeptieren Umsetzung Detail. Aber zunächst wollen wir die Daten aktualisieren Struktur, bevor wir das tun. Weil ich nicht zu mögen die Idee, alle die Leute Verschiebung in dieser Linie. 

Es ist keine große Sache, wenn David tut es mit einen Schritt, aber wieder, denken Sie zurück an wenn wir hatten acht Freiwilligen auf die Bühne und wir haben wie Insertion getan Art, wo wir anfangen Bewegen jeder um. Das brachte teuer, nicht wahr? Das macht mich erschaudern über große O von n, straffte big O von n wieder. Es fühlt sich nicht wie ein ideales Ergebnis. 

Also lasst uns einfach aktualisieren diese. So dass die Größe der Warteschlange nicht mehr 2. Es ist jetzt einfach ein. Aber ich kann jetzt etwas aktualisieren Ich habe nicht vor zu aktualisieren, die vor der Liste. Ich konnte nur sagen, dass Platz 1? Jetzt haben wir also Müll Wert hier Müll Wert hier, und David in die Mitte dieser Müll. Aber die Datenstruktur noch intakt ist. 

Und in der Tat, ich habe nicht einmal zu ändern Jakes ehemalige Nummer 9, denn wer sich interessiert. Ich habe genug Informationen jetzt in der Größe, dass ich es eine Person in weiß diese Warteschlange. Und ich weiß, dass diese Person ist am Standort 1, nicht 0 ist. Ich zähle nicht. Also 1 sowie. Also die Datenstruktur ist noch OK. 

Nun, was passiert als nächstes? Lassen Sie uns enqueue - was ist Ihr Name? 

ZUSCHAUER: Callen. 

DAVID MALAN: Callen. Lassen Sie uns ein Einreihen Callen und 22 ist nun in der Warteschlange. So jetzt, was hat hier ändern? Vorne ist nicht zu ändern, offensichtlich. Größe wird sich ändern, um 2 wieder. Und 22 endet hier, 9 noch vorhanden ist, aber es ist effektiv ein Müll Wert jetzt. Es ist nur ein Überbleibsel von Jake Vergangenheit. 

So jetzt, was passiert, wenn Ich dequeue David? Eine letzte Operation dequeue David. Wir konnten zu verschieben, aber ich schlage lasst tun so wenig Arbeit wie möglich. Nun meine Datenstruktur geht Sichern in der Größe 2-1. Aber die Spitze der Schlange Jetzt wird 2. Ich brauche nicht diese Zahlen ändern nur noch, weil sie Werte nur Müll. 

Aber nun, was passiert? Angenommen, ich mich einreihen, 26? Ich fühle mich wie ich hierher gehöre. Also bin ich in die Warteschlange gestellt. Also habe ich hierher. Und auch wenn Sie nicht ganz schätzen visuell auf der Bühne, weil wir genug Platz haben, sollte ich nicht hier stehen, warum? 

ZUSCHAUER: Sie sind außerhalb der Grenzen. 

DAVID MALAN: Richtig. Ich bin außerhalb der Grenzen. Ich habe über die indizierte Grenzen dieses Feldes. Ich sollte wirklich in einer der sein drei mögliche Standorte. Nun, wo ist die natürlichste zu gehen? Ich schlage vor, wir Leveraged eine Woche ein Trick. Der Mod-Operator, Prozentsatz. Weil ich technisch Stehen bei Standort 3, aber ich 3 mod Kapazität, so 3, ein Prozent-Zeichen, 3 - Kapazität ist 3. Was ist das? Was ist, wenn der Rest teilen Sie 3 mal 3? 0. 

Also das bringt mich waren Jake war, Das ist wirklich gut. So, jetzt die Umsetzung dieser Sache geht um sein ein wenig Kopfschmerzen. Es ist wirklich nur eine Zeile Kopfschmerzen, Code. Aber zumindest gibt es jetzt Müll Wert hier, aber es gibt zwei legitimen ints hier. Und ich behaupte, dass wir jetzt getan haben genau das, was wir brauchen, um so lange wie zu tun wir ändern, was Jakes -Wert wurde auf 26 sein. 

Wir haben jetzt genug Informationen noch die Integrität aufrechtzuerhalten dieser Datenstruktur. Wir sind immer noch Art von Glück, wenn wir wollen vier oder mehr insgesamt einfügen Elemente, aber ich kann zumindest machen ziemlich effizienten Nutzung dieser Konstante Zeit, in der Tat. Ich weiß nicht um die Schaltarbeit Sorgen jeder, wie David die Neigung war. 

Irgendwelche Fragen zu Stapeln, oder diese Warteschlange? 

ZUSCHAUER: Ist der Grund, warum Sie brauchen Größe, damit Sie wissen wo eine Person? 

DAVID MALAN: Genau. Ich brauche, um die Größe des Arrays kennen da muss ich genau wissen, wie Viele dieser Werte sind legitim, und so, dass ich finden kann, wo zu setzen die nächste Person. Genau. Die Größe ist - eigentlich hatten wir nicht aktualisieren diese noch. Ich habe mich bei 26. Die Größe ist jetzt, nicht 1, sondern 2. So, jetzt dies tatsächlich hilft mir finden die Kopf der Liste, was nicht 0, nicht 1, jedoch für 2 steht. Die Vorderseite der Liste ist in der Tat der Nummer 22. Da kam er in der ersten, so sollte er in den Laden vor mir erlaubt sein, obwohl visuell ich stehe näher an das Geschäft. 

Alles klar? Ein Applaus für diese Jungs und wir lassen sie da raus. 

[Applaus] 

DAVID MALAN: Ich konnte lassen Sie halten das Fach. Wir konnten sehen, was passiert, wenn Sie wollen, aber vielleicht auch nicht. In Ordnung. Also, was bedeutet das nun für uns? Nun, lassen Sie mich schlagen, dass es eine einige andere Datenstrukturen konnten wir fangen Sie an unserem Tool-Kit, das wird eigentlich ganz, ganz relevant sein wir in Sachen Web tauchen. Welche wiederum hat eine Art von Verbindung Bäume in Form von etwas namens DOM Dokument Objektmodell. Aber wir werden sehen, mehr von dass vor lang. 

Lassen Sie mich definitorisch vorschlagen, dass wir rufen Baum nun, was Sie vielleicht wissen, wie eher ein Stammbaum, in dem Sie habe einige Vorfahren bei der Wurzeln des Baumes. Eine patriarchale oder eine Matriarchin an Ganz oben auf dem Baum. Ohne ihre Ehepartner, in diesem Fall. Aber wir haben jetzt das, was wir nennen Kinder, die Knoten, die hängen sind von der linken oder der rechten Kind Kind, Pfeile, wie hier dargestellt. 

Mit anderen Worten, in einer Baum-Datenstruktur in Computer hat ein Baum Null oder mehr Knoten. Wenn es mindestens einen Knoten, Das nennt man die Wurzel. Es sind die Dinge, die visuell wir ziehen an der Spitze. Und dass der Knoten, wie jeder andere Knoten können kein, ein oder zwei, oder drei, oder wie viele Kinder die Datenstruktur unterstützt. In diesem Fall wird die Wurzel, Speichern der Wert eins, hat zwei Kinder, 2 und 3, so nennen wir in der Regel 2 die linke Kind und 3 die richtige Kind. 

Und dann, wenn wir uns an die 5, 6, und 7, 6 könnte man das mittlere Kind werden. Wenn Sie haben vier Kinder, wird es verwirrend. So stoppen wir mit dieser Art von Shortcut-verbal. Aber es ist wirklich nur ein Stammbaum. Und die Blätter hier sind die Knoten, die selbst haben keine Kinder. Sie hängen von der Unterseite des Baumes. 

Also, wie könnten wir implementieren einen Baum, hat nur zwei Kinder maximal? Wir nennen es ein binärer Baum. Bi wieder einen Sinn zwei, in dieser Fall wie mit binären. Und so kann es kein, ein, oder maximal zwei Kinder. 

Ich werde vorschlagen, dass wir den Knoten implementieren für diese Struktur mit einem int n, und dann zwei Zeiger, nannte man verließ, nannte man rechts. Aber das sind nur schön willkürlichen Konventionen. Und was ist schön, jetzt, vor allem, wenn Sie Art kämpfte konzeptionell mit Rekursion, oder dachte, dass es nicht wirklich eine Lösung für alles, vor allem, wenn Sie könnten Arbeitsspeicher ausgeführt. Jetzt, da wir über Daten sprechen Strukturen und Algorithmen, mit denen uns zu durchqueren und zu manipulieren, stellt sich heraus, dass Rekursion kommt zurück in eine viel überzeugendere wenn nicht schöne Weise. 

Also das ich vorschlage, ist die Umsetzung einer Suchfunktion. Da zwei Eingänge - so daran zu denken, wie eine Black Box. Da zwei Eingänge, n, ein int und ein Zeiger auf einem Baum, einen Zeiger auf eine Knoten, oder wirklich die Wurzel eines Baumes, I Anspruch, dass diese Funktion zurückkehren können wahr oder falsch, dass Wert n ist innerhalb von diesem Baum. 

Was ist in der Innenseite dieser Black Box? Nun, vier Niederlassungen. Der erste gerade überprüft. Wenn Baum ist null, nur false zurück. Wenn es keinen Knoten gibt es keine n, es gibt keine Zahl, nur false zurück. Wenn aber, n, der Wert Sie suchen für ist weniger als Baum Pfeil n, und nur klar zu sein, was bedeutet es, wenn Ich schreibe Baum und dann der Pfeil Notation, n? Genau. Es bedeutet, dass dereference Pointer aufgerufen Baum. Gehen Sie dort hin, und dann innerhalb der, dass Knoten und erhalten ihre Feld namens n. Und dann vergleichen Sie die tatsächlichen n das war ging in Search dagegen. 

Also, wenn n kleiner, der n-Wert im Baum Knoten selbst, na ja, was bedeutet das? Das bedeutet, dass nichts auf den ersten Blick. Right? Genau wie wenn Sie eine Reihe von haben Werte, die Ihnen gefallen könnten, um binäre gelten Suche als eine Form der Spaltung und zu erobern. Aber was haben wir davon brauchen, um für binäre Suche, um überhaupt arbeiten im Telefonbuch und früheren Beispielen? 

Wie sortiert werden. Also lasst verfeinern die Definition von Baum hier nicht nur ein Baum, das kann eine beliebige Anzahl von Kindern. Nicht nur ein binärer Baum, der kann 0, 1, 2 oder maximal. Aber als binärer Suchbaum oder BST, Das ist nur eine andere Art zu sagen, ein Binärbaum, so dass jeder Knoten linken Kind, falls vorhanden, unter dem Knoten. Und jedes Knotens rechte Kind, wenn vorhanden, größer ist als der Knoten selbst. 

Also mit anderen Worten, wenn Sie wurden zu ziehen der Baum aus, sind alle Zahlen sorgfältig so ausgewogen, so dass, wenn Sie haben 55 als die Wurzel, kann 33 gehen auf der linken Seite, weil es weniger als 55 Jahre. 77 kann auf sein Recht, da gehen es ist mehr als 55 Jahre. Aber jetzt bemerken, die die gleiche Definition, es ist eine rekursive Definition mündlich, muss für 33 gelten. 33 das linke Kind muss kleiner sein als sie, und 33 das Recht Kind, 44, muss größer als sie. 

Das ist also ein binärer Suchbaum, und Ich schlage vor, mit ein wenig Rekursion, können wir jetzt finden n. Also, wenn n kleiner als der Wert N ist, die aktuellen Knoten, werde ich gehen voran und Punt, sozusagen, und nur zurück, was die Antwort ist Suche nach n auf die Baum linken Kind. Beachten Sie wieder, diese Funktion nur erwartet einen Knoten Sterne, eine Zeiger zu einem Knoten. So sicher kann ich nur tun, Baum Pfeil nach links, das führt mich zu einem anderen Knoten. Aber was ist, dass der Knoten? 

Nun, nach dieser Erklärung, linken Seite ist nur ein Zeiger, so dass nur bedeutet, dass ich auf die Suchfunktion vorbei eine andere Zeiger, nämlich derjenige, stellt meine linke Kindes Baum. Also in diesem Fall, bis der Zeiger 33, wenn dies ist unsere Probe Eingang der Zwischenzeit, wenn n ist größer als der Wert n in der aktuellen Knoten im Baum, dann bin ich werde weitermachen und Kahn gehen in die andere Richtung und nur sagen, ich weiß nicht wissen, ob dieser Wert n ist in dem Baum, aber ich weiß, wenn es ist, ist es nach meiner rechten Arm, so zu sprechen. Also lassen Sie mich rufen rekursiv suchen, Übergabe eines n wieder, sondern die Weitergabe in ein Zeiger auf meiner rechten Kind. 

Mit anderen Worten, wenn ich gerade bei 55 und ich bin auf der Suche für 99, ich weiß, dass 99 ist größer als 55, so wie ich riss die Telefonbuch Wochen und wir ging nach rechts, ähnlich wie wir sind gehen, um hier zu gehen. Und ich weiß nicht, ob es an meiner rechten ist Kind, und es ist nicht, ist es 77, aber Ich weiß, dass es in diese Richtung. So nenne ich suche für meine rechte Kind, 77, und ließ Suche Figur aus wenn es 99 in dieser willkürlichen Beispiel ist tatsächlich da. 

Else, was ist der letzte Fall? Wenn Baum ist null ist ein Fall. Wenn n kleiner als die aktuellen Knotens Wert ist ein weiterer Fall. Ist n größer als die aktuelle Knoten Wert ist ein dritter Fall. Was ist die vierte und letzte Fall? Ich denke, wir sind aus der Fälle, nicht wahr? Es muss sein, dass in der n ist aktuellen Knoten, dass ich auf bin. 

Also, wenn ich für 55 Benutzer an dieser Stelle in der Geschichte, dass Zweig der Baum würde true zurückgeben. Also, was ist hier interessant ist, dass wir eigentlich, im Gegensatz zu Wochen vorbei, wir Art von zwei Basis-Fällen. Und sie müssen nicht alles sein an der Spitze. Die Oberseite ist ein Base-Case, denn wenn die Baum ist null, es gibt nichts zu tun. Nur zurückgeben hart codiert Wert false. 

Der untere Zweig ist eine Art der Standard, wobei, wenn wir für aufgegebenes null, haben wir geprüft, ob es sein sollte verlassen, aber es sollte nicht sein, haben wir geprüft, ob es sein sollte Recht, aber es sollte nicht sein, klar muss es sein genau dort, wo wir sind. Das ist ein Base-Case. Also gibt es zwei rekursive Fälle dort in der Mitte angeordnet ist. Aber ich hätte schreiben können diese in beliebiger Reihenfolge. Ich dachte nur, es fühlte sich irgendwie natürlicher zum ersten für einen möglichen Fehler zu überprüfen, dann schauen Sie nach links, dann nach rechts zu überprüfen, dann davon ausgehen, dass Sie an dem Knoten sind Sie eigentlich suchen. 

Warum könnte dies nützlich sein? So stellt sich heraus - und lassen Sie mich zu einem Teaser springen das ist hier im Web. Wir fangen an mit nicht Programmiersprache auf den ersten, sondern ein Markup-Sprache. Eine Markup-Sprache ist eine, die ist im Geiste in die Programmierung Sprache, aber es gibt Ihnen nicht das Fähigkeit, sich logisch auszudrücken. Es gibt Ihnen nur die Möglichkeit, auszudrücken strukturell. 

Wo wollen Sie etwas setzen auf der Seite, die Web-Seite? Welche Farbe wollen Sie es machen? Was Schriftgröße wollen Sie es machen? Welche Worte haben Sie eigentlich wollen auf der Web-Seite? Also das ist eine Markup-Sprache. Aber dann werden wir sehr schnell einführen JavaScript, das eine vollwertige ist Programmiersprache. Sehr ähnlich syntaktisch in Erscheinung zu C, aber es müssen einige schön, noch leistungsfähiger, noch benutzerfreundlichen Funktionen. 

Und einer von den Frustrationen an diesem Punkt im Semester ist, dass wir werden bald umzusetzen Speller in weit weniger Zeilen Code mit anderen Sprachen als C selbst erlaubt, aber für Vernunft wir werden bald verstehen. Dies wird die erste derartige Webseite sein. Es wird völlig berauschend, das erste, das wir machen. Es wird einfach sagen, hallo Welt. Aber wenn Sie es noch nie gesehen vor, ist dies HTML, HyperText Markup Language. 

Wenn Sie zu einem bestimmten Menüpunkt in fast jedem Browser auf einem beliebigen Web-Seite auf das Internet, können Sie sich den HTML dass einige Leute schrieb schaffen, dass Web-Seite. Und ist es wahrscheinlich nicht so aussehen kurze oder so sauber wie dieses. Aber es wird nach dem Muster von diesen offenen Klammern und Schrägstriche und Buchstaben und Zahlen potentiell. 

Ich dachte, ich würde Ihnen ein Teaser von dem, was Sie tun können, nach der Einnahme von CS50. Lassen Sie mich zu cs.harvard.edu / rob gehen, unsere eigenen Rob Bowden-Homepage. Er machte das für uns. So werden Sie bald in der Lage sein, das zu tun. Und auch, was Sie gehört haben an diesem Morgen - was Sie heute Morgen gehört - 

[HAMSTER DANCE MUSIC] 

- Du wirst in der Lage sein, dies zu machen. Das erwartet uns am Mittwoch. Wir werden sehen uns dann. 

[HAMSTER DANCE MUSIC] DAVID MALAN: An der nächsten CS50 -