Sprecher 1: Alles klar, also sind wir wieder zurück. Willkommen auf CS50. Dies ist das Ende der Woche sieben. So erinnern daran, dass beim letzten Mal, haben wir begonnen, Blick auf etwas anspruchsvollere Datenstrukturen. Da bis jetzt hatten wir wirklich zur Verfügung war, um ein Array. Aber bevor wir verwerfen das Array als nicht alles, was interessant, was es tatsächlich eigentlich ist, was sind einige der Pluspunkte dieser einfachen Daten Struktur so weit? Was ist es gut? So weit wie wir gesehen haben? Was hast du? Nichts. STUDENT: [unverständlich]. Sprecher 1: Was ist das? STUDENT: [unverständlich]. Sprecher 1: Feste Größe. OK, also warum ist feste Größe aber gut? STUDENT: [unverständlich]. Sprecher 1: OK, es ist effizient in das Gefühl, dass man eine Zuweisung feste Menge an Speicherplatz, die hoffentlich ist genau so viel Raum, wie Sie wollen. Also das könnte durchaus ein Plus. Was ist ein anderes up side eines Arrays? Ja? STUDENT: [unverständlich]. Sprecher 1: All das - sorry? STUDENT: [unverständlich]. Sprecher 1: Alle Boxen im Speicher oder nebeneinander. Und das ist hilfreich - warum? Das ist ganz richtig. Aber wie können wir ausnutzen, dass die Wahrheit? STUDENT: [unverständlich]. Sprecher 1: Genau, wir können von Kurs zu halten wo alles ist nur durch das Wissen eine Adresse, nämlich die Adresse des erste Byte dieser Teil des Speichers. Oder im Fall der Zeichenfolge die Adresse des ersten char in dieser Zeichenfolge. Und von dort, können wir das Ende der Schnur. Wir finden das zweite Element, das dritte Element und so weiter. Und so ist die andere Art zu beschreiben, dass Merkmal ist, dass Arrays uns geben Direktzugriffsspeicher. Nur mit Hilfe der eckigen Klammer Notation und eine Zahl ist, können Sie zu springen ein bestimmtes Element in der Matrix in konstanter Zeit, big O von einem, sozusagen. Aber es ist schon einige Nachteile. Was ein Array nicht sehr leicht zu tun? Was ist es nicht gut? STUDENT: [unverständlich]. Sprecher 1: Was ist das? STUDENT [unverständlich]. Sprecher 1: Ausbau in der Größe. So sind die Schattenseiten des Arrays sind genau das Gegenteil von dem, was die upsides sind. Damit wird eines der Nachteile ist dass es eine feste Größe. So kann man nicht wirklich wachsen sie. Sie können umzuschichten einen größeren Teil der Speicher, und verschieben Sie dann die alten Elemente in das neue Array. Und dann kostenlos das alte Array, für beispielsweise durch malloc oder eine ähnliche Funktion aufgerufen realloc, die Neuzuweisen Speicher. Realloc als beiseite, versucht, Sie geben Speicher, der neben dem Array ist dass Sie bereits haben. Aber es könnte etwas bewegen um insgesamt. Aber kurz gesagt, das ist teuer, nicht wahr? Weil, wenn Sie einen Teil des Speichers von dieser Größe, aber Sie wirklich wollen, eine dieser Größe, und Sie wollen zu bewahren die ursprünglichen Elemente, müssen Sie etwa eine lineare Zeit Kopiervorgang das muss aus geschehen alte Array neu. Und die Realität fragt das Betriebssystem System wieder und wieder und wieder für große Brocken Speicher kann beginnen kostet Sie einige Zeit als gut. Also es ist ein Segen und ein Fluch in verschleiern, die Tatsache, dass diese Arrays sind eine feste Größe. Aber wenn wir stattdessen etwas vorstellen wie diese, die wir als eine verknüpfte Liste, bekommen wir ein paar Vor-und ein paar Nachteile auch hier. So eine verlinkte Liste ist einfach eine Daten Struktur, bestehend aus C Strukturen in dieser Fall, in dem eine Struktur, Rückruf, ist nur ein Behälter für eine oder mehrere bestimmte Typen von Variablen. In diesem Fall wird das tun, was die Datentypen scheinen innerhalb der Struktur, dass letzten Mal riefen wir einen Knoten? Jedes dieser Rechtecke ist ein Knoten. Und jedes der kleineren Rechtecke in der es ist ein Datentyp. Welche Arten haben wir gesagt sie waren am Montag? Ja? STUDENT: [unverständlich]. Sprecher 1: Eine Variable und einen Zeiger, oder Genauer gesagt, ein int für n, und ein Zeiger an der Unterseite. Beide diejenigen passieren auf 32 Bit sein, bei zumindest auf einem Computer wie dieser CS50 Appliance, und so sind sie gleichermaßen in Größe gezeichnet. Also, was mit dem Mauszeiger obwohl für scheinbar? Warum fügen Sie diesen Pfeil, jetzt, wenn Arrays waren so schön und sauber und einfach? Was tun, wird der Zeiger für uns in jedem dieser Knoten? STUDENT: [unverständlich]. Sprecher 1: Genau. Es sagt dir, wo der nächste ist. So ich irgendwie die Analogie von mit einem Gewinde zu sortieren von fädeln diese Knoten zusammen. Und das ist genau, was wir tun, mit Zeiger Da jedes dieser Stücke von Speicher kann oder nicht zusammenhängenden, Rücken an Rücken an Rücken innerhalb von RAM, weil jedes Mal, wenn rufen malloc sagen, gib mir genug Bytes für einen neuen Knoten, könnte es hier sein oder es könnte hier zu sein. Es könnte hier sein. Es könnte hier sein. Sie wissen einfach nicht. Aber mit Zeigern in den Adressen diese Knoten können Sie nähen sie in einer Weise zusammen, die visuell sieht wie eine Liste, selbst wenn diese Dinge sind alle aus einem oder in Ihrem verbreiten Ihre zwei oder Ihre vier Gigabyte RAM innerhalb des eigenen Rechners. So ist die Kehrseite, dann, eine verlinkte Liste ist was? Was ist ein Preis, den wir sind anscheinend zahlen? STUDENT: [unverständlich]. Sprecher 1: Mehr Platz, nicht wahr? Wir haben in diesem Fall verdoppelt den Betrag der Raum, weil wir gegangen von 32 Bit für jeden Knoten für jede int, so dass nun 64 Bits, da müssen wir halten um einen Zeiger als gut. Sie erhalten mehr Effizienz, wenn Ihr struct ist größer als diese einfache Sache. Wenn Sie tatsächlich einen Schüler in von denen ein paar Saiten für Namen und Haus, vielleicht eine ID-Nummer, vielleicht ein paar anderen Bereichen zusammen. Wenn Sie also eine ausreichend große Struktur, dann vielleicht die Kosten der Zeiger nicht so eine große Sache. Das ist ein bisschen von einer Ecke in Fall, dass speichern wir eine so einfache primitive innerhalb der verknüpften Liste. Der Punkt ist der gleiche. Sie sind auf jeden Fall mehr Geld Speicher, aber Sie bekommen Flexibilität. Denn jetzt, wenn ich will, um ein Element hinzufügen am Anfang der Liste, Ich habe einen neuen Knoten zuweisen. Und ich muss nur diejenigen aktualisieren Pfeile irgendwie durch Verschieben nur einige Hinweise um. Wenn ich etwas in den Einsatz Mitte der Liste, ich habe nicht zu schieben alle beiseite, wie wir in tat Wochen Vergangenheit mit unseren Freiwilligen, die vertreten ein Array. Ich kann nur vergeben einen neuen Knoten und dann nur darauf hinweisen, die Pfeile in verschiedenen Richtungen, weil es nicht müssen in tatsächliche bleiben Speicher eine echte Linie, wie ich gezeichnet haben hier auf dem Bildschirm. Und dann schließlich, wenn Sie einfügen möchten auch am Ende der Liste, ist es noch einfacher. Dies ist eine Art von beliebigen Schreibweise aber die Zeiger 34, zu erraten. Was ist der Wert der Zeiger am wahrscheinlich gezogen Art wie ein alter Schule Antenne da? STUDENT: [unverständlich]. Sprecher 1: Es ist wahrscheinlich null. Und in der Tat, das ist eines Autors Darstellung von null. Und es ist null, weil man absolut müssen wissen, wo das Ende einer verknüpften Liste ist, damit ihr folgenden zu halten und nach und nach diese Pfeile bis zu einem gewissen Wert Müll. Also null wird bedeuten, dass es keine mehrere Knoten auf der rechten Reihe 34, in diesem Fall. So schlagen wir vor, die wir umsetzen können dieser Knoten im Code. Und wir haben diese Art gesehen der Syntax vor. Typedef nur definiert einen neuen Typ für uns, gibt uns ein Synonym wie String war für char *. In diesem Fall, es geht um uns Kurzschrift, so dass struct node kann statt nur geschrieben werden als Knoten, die viel sauberer ist. Es ist viel weniger ausführlich. Innerhalb eines Knotens ist offenbar ein int n genannt, und dann ein struct node * was bedeutet genau das, was wir wollten die Pfeile bedeuten, einen Zeiger auf ein anderes Knoten der exakt gleichen Datentyp. Und ich vorschlagen, dass wir eine Umsetzung Suchfunktion wie diese, die bei den ersten Blick scheinen mag ein wenig komplex. Aber mal sehen, es im Kontext. Laß mich hinübergehen zu dem Gerät hier. Lassen Sie mich öffnen, eine Datei mit dem Namen Liste Null dot h. Und das nur die Definition, die wir sah nur vor einem Augenblick für diese Daten Art Knoten genannt. Deshalb haben wir uns, dass in einem Punkt h-Datei setzen. Und so nebenbei, obwohl dies Programm, das Sie über zu sehen sind ist nicht alles, was komplex, es ist in der Tat Konvention beim Schreiben eines Programms zur Dinge wie die Datentypen zu ziehen Konstanten manchmal innerhalb Ihres Header-Datei und nicht unbedingt in Ihre C-Datei, natürlich, wenn Ihr Programme zu größer, so dass Sie wissen, wo sie beide suchen Dokumentation in einigen Fällen, oder für Grundlagen wie diese, die Definition eines Typs. Wenn ich jetzt eröffnen Liste Null dot c, ein paar Dinge beachten. Es enthält ein paar Header-Dateien, die meisten von denen wir bisher gesehen haben. Es verfügt über einen eigenen Header-Datei. Und so nebenbei, warum das doppelt Zitate hier, wie auf den Winkel entgegengesetzt Klammern auf der Linie, dass Ich habe dort hervorgehoben? STUDENT: [unverständlich]. Sprecher 1: Ja, so ist es eine lokale Datei. Also, wenn es eine lokale Datei des eigenen hier on line 15, zum Beispiel, verwenden Sie die doppelten Anführungszeichen statt der eckigen Klammern. Nun ist dies irgendwie interessant. Beachten Sie, dass ich erklärte eine globale Variable in diesem Programm on line 18 zuerst aufgerufen, ist die Idee, dass diese wird ein Zeiger auf das erste sein Knoten in meiner verketteten Liste, und ich habe initialisiert sie auf null, weil ich nicht zugeordnet jede tatsächliche Knoten nur noch. So bedeutet dies, bildhaft, was wir sah vor einem Augenblick in dem Bild als dass Zeiger auf dem weit linken Seite. So jetzt, dass Zeiger nicht über einen Pfeil. Es ist stattdessen nur null. Aber es stellt dar, was wird das sein Adresse des ersten tatsächlichen Knoten in dieser Liste. Also habe ich es umgesetzt ist ein globales weil, wie Sie sehen, all dies Programm läuft im Leben ist zu implementieren eine verlinkte Liste für mich. Jetzt habe ich ein paar Prototypen hier. Ich beschloss, Funktionen wie umsetzen Deletion, Insertion, Suchen und Traversal - die letzte einfach nur zu Fuß über die Liste Ausdrucken seiner Elemente. Und hier ist mein Hauptprogramm. Und wir werden nicht zu viel Zeit auf diese da diese Art von, hoffentlich alter Hut mittlerweile. Ich werde Folgendes tun, während der Benutzer arbeitet. So eins, ich werde ausdrucken aus diesem Menü. Und ich habe es als formatiert sauber, wie ich konnte. Wenn der Benutzer in einem, das heißt sie wollen etwas zu löschen. Wenn die Benutzer in zwei, das heißt sie wollen etwas einzufügen. Und so weiter. Ich werde dann aufgefordert, dann auf einen Befehl. Und dann werde ich GetInt verwenden. Also das ist eine wirklich einfache Menüführung Schnittstelle, wo Sie nur noch auf den Typ eine Reihe Zuordnung zu einer dieser Befehle. Und jetzt habe ich ein schönes, sauberes Schalter Anweisung, die gehen auf Schalters was der Benutzer eingegeben in. Und wenn sie eingegeben eins, ich werde rufen zu löschen und zu brechen. Wenn sie zwei getippt, ich werde rufen einzusetzen und zu brechen. Und jetzt habe ich feststellen das jede setzen davon auf der gleichen Linie. Dies ist nur eine stilistische Entscheidung. Normalerweise haben wir etwas gesehen wie diese. Aber ich beschloss, ehrlich gesagt, mein Programm sah besser lesbar, weil es war nur vier Fälle nur aufzulisten es wie folgt. Völlig legitime Nutzung des Stils. Und ich werde, dies zu tun, solange der Benutzer hat nicht Null eingegeben, die ich entschieden wird, dass sie aufhören wollen. So, jetzt merken, was ich bin hier tun. Ich werde die Liste offenbar zu befreien. Aber mehr dazu in einem Moment. Lassen Sie uns zuerst dieses Programm ausführen. Also lassen Sie mich ein größeres Terminal Fenster dot Streichliste 0. Ich werde weitermachen und durch einfügen Typisierung zwei, eine Zahl wie 50, und jetzt Sie werden sehen, die Liste ist jetzt 50. Und mein Text gescrollt nur ein wenig. So, jetzt feststellen, enthält die Liste die Zahl 50. Lassen Sie uns ein anderes einfügen, indem man zwei. Lassen Sie uns in der Anzahl wie eine geben. Liste ist nun ein, gefolgt von 50. Also das ist nur eine textuelle Repräsentation von der Liste. Und lassen Sie uns legen Sie eine weitere Zahl wie die Zahl 42, die hoffentlich gehen, um am Ende in der Mitte, weil dieses Programm insbesondere sortiert sie Elemente, wie es fügt sie. Also da haben wir es. Super-einfaches Programm, das könnte absolut haben ein Array verwendet, aber ich passieren zu sein mit einer verketteten Liste nur so kann ich dynamisch wachsen und schrumpfen sie. Werfen wir also einen Blick für die Suche, wenn ich Befehl laufen drei, ich möchte suchen für, sagen wir, die Zahl 43. Und nichts wurde offenbar gefunden, weil ich wieder keine Antwort. Also lasst uns wieder tun. Suchen. Lasst Suche nach 50 oder vielmehr suchen für 42, hat die einen schönen wenig subtile Bedeutung. Und ich fand den Sinn des Lebens gibt. Nummer 42, wenn Sie nicht wissen, der Verweis, google es. In Ordnung. Also, was hat dieses Programm für mich getan? Es ist nur mir erlaubt, so legen weit und die Suche nach Elementen. Lassen Sie uns schnell vorwärts, dann, um Diese Funktion haben wir einen Blick auf am Montag, als Teaser. Also dieser Funktion, behaupte ich, sucht nach ein Element in der Liste, indem Sie zuerst ein, die den Nutzer und rufen dann Getint um eine tatsächliche int bekommen , die Sie suchen möchten. Dann bemerken dies. Ich werde eine temporäre Variable erstellen in Zeile 188 aufgerufen pointer - PTR - könnte man sie haben nichts. Und es ist ein Zeiger auf einen Knoten weil ich den Knoten * gibt. Und ich bin es zu initialisieren, um gleich zuerst, so dass ich effektiv meine Finger, sozusagen, auf dem sehr erste Element der Liste. Also, wenn meine rechte Hand ist hier PTR Ich bin zeigt auf die gleiche Sache, die erste gerade befindet. So, jetzt wieder im Code was als nächstes passiert - dies ist ein gemeinsames Paradigma bei der Iteration über eine Struktur wie ein verketteten Liste. Ich werde die folgenden Weile zu tun Zeiger nicht gleich null So während meine Finger nicht null zeigt an einigen Wert, wenn Mauspfeil n gleich n. Wir werden zunächst bemerken, dass n ist, was die Benutzer pro GetInts eingegeben rufen hier. Und Zeigerpfeil n bedeutet was? Nun, wenn wir wieder zu dem Bild hier, wenn ich einen Finger zeigt auf dass der erste Knoten mit neun, die Pfeil bedeutet im Wesentlichen, gehen Sie zu, dass Knoten und greifen den Wert an der Stelle n, in diesem Fall muß das Datenfeld n. Nebenbei - und wir sahen diese ein paar von Wochen, wenn jemand gefragt - Diese Syntax ist neu, aber es funktioniert nicht geben uns Kräfte, die wir nicht bereits haben. Was war dieser Satz entspricht der Verwendung Punkt-Notation und ein paar Sterne von Wochen, wenn wir geschält zurück diese Schicht etwas zu früh? STUDENT: [unverständlich]. Sprecher 1: Genau, es war Stern und dann war es Sterne dot n mit Klammern Sie hier, was aussieht, ehrlich gesagt, ich glaube, eine Menge mehr kryptisch zu lesen. Aber Sterne Zeiger, wie immer, Mittel dorthin zu gehen. Und wenn du da bist, welche Daten Feld wollen Sie zugreifen? Nun verwenden Sie die Punkt-Notation für den Zugriff auf ein Datenfeld Strukturen, und ich Insbesondere wollen n. Ehrlich gesagt, würde ich behaupten, diese ist nur schwerer zu lesen. Es ist schwieriger, sich zu erinnern, wo Sie gehen die Klammern, die Stern und das alles. So verabschiedete die Welt einige syntaktische Zucker, so zu sprechen. Nur eine sexy Art und Weise zu sagen, dies entspricht und vielleicht mehr intuitiv. Wenn Zeiger ist in der Tat ein Zeiger, der arrow Notation Mittel gehen dorthin und findet das Feld in diesem Fall n genannt. Also, wenn ich es finde, bemerken, was ich mache. Ich habe einfach ausdrucken, fand ich i Prozent, Einstecken der Wert für die Int. Ich nenne schlafen für eine Sekunde nur um Art der Pause Dinge auf dem Bildschirm dem Benutzer eine zweite zu absorbieren was gerade passiert ist. Und dann habe ich zu brechen. Ansonsten, was soll ich tun? Ich aktualisiere Zeiger auf gleich Mauspfeil nächsten. Also nur klar zu sein, bedeutet dies, gehen es, mit meiner alten Schule Notation. So bedeutet dies einfach, um was auch immer gehen Sie sehen, die zeigen in der sehr erste Fall ist, dass ich bei weisenden die Struktur mit neun drin. Also habe ich es weg. Und dann der Punkt-Notation bedeutet, erhalten den Wert am nächsten. Aber der Wert, obwohl es gezeichnet als schmale, ist nur eine Nummer. Es ist eine numerische Adresse. So ist dieses eine Zeile Code, ob geschrieben wie diese, die mehr kryptischen So oder so, die etwas mehr intuitive Art und Weise, bedeutet nur, meine Hand zu bewegen von dem ersten Knoten zu dem nächsten, und dann wird die nächste, und dann das nächste, und so weiter. So werden wir nicht auf der anderen Seite wohnen Implementierungen einfügen und löschen und Durchlaufen der ersten beiden von die sind ziemlich beteiligt. Und ich denke, es ist ganz einfach zu bekommen verloren, wenn es zu tun verbal. Aber was wir hier tun können, ist versuchen zu bestimmen, wie am besten, dies visuell zu tun. Da würde ich vorschlagen, dass, wenn wir wollen Elemente in diese einfügen bestehende Liste, die hat fünf Elemente - 9, 17, 22, 26 und 33 - wenn ich im Begriff waren, diese in Umsetzung Code, muss ich überlegen, wie gehen zu tun. Und ich würde vorschlagen, die Baby-Schritte wobei in diesem Fall, den ich meine, was sind die möglichen Szenarien, die wir vielleicht im Allgemeinen zu begegnen? Bei der Umsetzung Einsatz für eine verknüpfte Liste, dies nur geschieht, ein sein konkretes Beispiel für Größe fünf. Nun, wenn Sie eine Nummer einfügen, gerne sagen, dass die Nummer eins, und Aufrechterhaltung sortierter Reihenfolge, wo offensichtlich hat die Nummer eins müssen gehen in diesem speziellen Beispiel? Wie am Anfang. Aber was interessant ist, dass es wenn Sie wollen, einen in diese einfügen Liste, was braucht besondere Zeiger scheinbar aktualisiert werden? Erste. Also ich würde behaupten, dies ist der erste Fall dass wir vielleicht zu prüfen, eine Szenario mit Einsetzen von der Anfang der Liste. Lasst abzupfen vielleicht eine so einfach oder gar einfacher Fall, relativ gesehen. Angenommen, ich möchte die einfügen Nummer 35 in sortierter Reihenfolge. Es gehört offenbar drüben. Also, was Zeiger offensichtlich ist los müssen in diesem Szenario aktualisiert werden? 34 der Zeiger immer nicht null aber die Adresse der Struktur mit der Nummer 35. Also das ist bei zwei. Also schon, ich bin Art der Quantisierung wie viel Arbeit ich habe zu tun. Und schließlich ist die offensichtliche Mitte Fall in der Tat, in der Mitte, wenn ich will legen etwas sagen wie 23, das geht zwischen der 23 und der 26, aber jetzt sind die Dinge ein wenig mehr beteiligt, weil das, was Zeiger geändert werden müssen? So 22 offensichtlich geändert werden muss weil er nicht mehr bis 26 zu verweisen. Er muss auf den neuen Knoten zeigen, dass Ich werde zu vergeben, indem Sie malloc oder einige gleichwertig. Aber dann brauche ich auch, dass die neuen Knoten, 23 in diesem Fall, daß sein Zeiger zeigt auf wen? 26. Und es geht um ein sein Reihenfolge der Operationen hier. Denn wenn ich das dumm, und ich zum Beispiel Start zu Beginn die Liste, und mein Ziel ist es, 23 einzufügen. Und ich überprüfen, gehört es hier, in der Nähe von neun? Nr. Ist es hier gehören neben 17? Nr. Hat es gehört hier neben 22? Ja. Nun, wenn ich dumm bin hier, und nicht Denken diese durch, könnte ich zuteilen meiner neuen Knoten für 23. Ich könnte aktualisieren Sie den Mauszeiger aus der Knoten genannt 22, zeigt es bei dem neuen Knoten. Und dann, was muss ich aktualisieren der neue Knoten Zeiger sein? STUDENT: [unverständlich]. Sprecher 1: Genau. Zeigen auf 26. Aber verdammt noch mal, wenn ich nicht bereits aktualisiert wurde, 22 der Zeiger, um auf diesem Kerl zeigen und jetzt habe ich den Waisen, den Rest der Liste, so zu sprechen. So Reihenfolge der Operationen hier wird wichtig sein. Um dies zu tun, könnte ich stehlen, sagen wir, sechs Freiwilligen. Und lassen Sie uns sehen, wenn wir dies nicht tun können visuell statt Code-weise. Und wir haben einige schöne Stress Kugeln für Sie heute. OK, wie wäre es mit ein, zwei, in der zurück - am Ende gibt. drei, vier, beide von Ihnen Jungs am Ende. Und fünf, sechs. Sicher. Fünf und sechs. Alles klar und wir kommen an euch nächste Zeit. Alles klar, nach oben zu kommen. Alles klar, da bist du hier zuerst, möchten Sie das eine ungeschickt sein in Google Glass hier? Alles klar, so, OK, Glass, Videos aufzeichnen. OK, du bist gut zu gehen. Alles klar, also wenn euch kann kommen hier habe ich im Voraus vorbereitet einige Zahlen. Alles klar, komm hier rüber. Und warum gehen Sie nicht ein wenig weiter so. Und lassen Sie uns sehen, was ist Ihr Name, mit dem Google Glass? STUDENT: Ben. Sprecher 1: Ben? OK, Ben, werden Sie in der ersten, buchstäblich. So werden wir zu euch senden bis zum Ende der Bühne. Alles klar, und dein Name? STUDENT: Jason. Sprecher 1: Jason, du wirst OK die Nummer neun. Also, wenn Sie zu Ben so folgen wollen. STUDENT: Jill. Sprecher 1: Jill, du gehst zu sein 17, die, wenn ich dieses mehr getan hatte intelligent, hätte ich begann am anderen Ende. Sie gehen diesen Weg. 22. Und Sie sind? STUDENT: Mary. Sprecher 1: Mary, wirst du 22 sein. Und Ihr Name ist? STUDENT: Chris. Sprecher 1: Chris, wirst du 26 sein. Und dann schließlich. STUDENT: Diana. Sprecher 1: Diana, wirst du 34 sein. So kommen Sie auf hier. Alles klar, so perfekt sortiert bestellen bereits. Und lassen Sie uns gehen Sie vor und tun dies so dass wir wirklich - Ben, du bist nur irgendwie suchen heraus ins Nirgendwo gibt. OK, also lasst uns weitermachen und zeigen diese mit Armen, so wie ich war, genau, was los ist. So gehen Sie vor und geben euch ein oder zwei Fuß zwischen euch. Und gehen Sie vor und mit einer Hand zu weisen wer auch immer Sie sollten gerichtet sein auf dieser Basis. Und wenn du null bist nur darauf gerade nach unten auf den Boden. OK, so gut. So, jetzt haben wir eine verkettete Liste, und lassen Sie mich vorschlagen, dass ich die Rolle des spielen PTR, also werde ich nicht die Mühe Tragen Sie diese um. Und dann - jemand dumm Konvention - Sie nennen das, was Sie wollen - Vorgänger Zeiger, Zeiger pred - es ist nur der Spitzname wir gaben unsere Beispielcode meiner linken Hand. Die andere Hand, dass zu halten gehen verfolgen, wer ist wer in der Folgende Szenarien. So nehme erstens, ich abzupfen wollen dass erste Beispiel für das Einfügen, sagen 20, in der Liste. Also werde ich, jemanden zu brauchen verkörpern die Zahl 20 für uns. Also muss ich malloc jemand aus dem Publikum. Komm up. Wie ist dein Name? STUDENT: Brian. Sprecher 1: Brian, alles in Ordnung, so dass Sie ist der Knoten mit 20 sein. Alles klar, komm hier rüber. Und natürlich, wo hat Brian gehören? Also, in der Mitte - eigentlich warten Sie eine Minute. Wir tun dies nicht in Ordnung. Wir machen dies viel schwieriger als es braucht, um auf den ersten sein. OK, wir gehen zum kostenlosen Brian und realloc Brian als fünf. OK, so jetzt wollen wir einfügen Brian als fünf. So komm hier neben Ben nur für einen Augenblick. Und man kann sagen, vermutlich wo diese Geschichte geht. Aber lassen Sie sorgfältig darüber nachdenken, die Reihenfolge der Operationen. Und es ist genau diese visuelle das wird antreten mit dem Beispielcode. So hier habe ich PTR zeigt zunächst nicht bei Ben, per se, sondern um jeden Preis Wert, den er enthält, die in diesem Fall ist - was ist Ihr Name? STUDENT: Jason. Sprecher 1: Jason, so dass sowohl Ben und ich sind zeigt auf Jason in diesem Moment. So jetzt habe ich, um zu bestimmen, woher kommt Brian gehören? So ist die einzige Sache, die ich haben Zugang zu jetzt ist seine n Datenelement. Also werde ich, um zu überprüfen, wird Brian weniger als Jason? Die Antwort ist richtig. Also, was jetzt geschehen muss, in der richtigen Reihenfolge? Ich muss, wie viele Zeiger aktualisieren insgesamt in dieser Geschichte? Wo meine Hand ist immer noch zeigt auf Jason und die Hand - wenn Sie möchten, setzen Sie Ihre Hand wie, irgendwie, ich nicht wissen, ein Fragezeichen. OK, gut. Alles klar, so haben Sie ein paar Kandidaten. Entweder Ben oder ich oder Brian oder Jason oder alle anderen, die Zeiger ändern müssen? Wie viele insgesamt? OK, also zwei. Mein Zeiger nicht wirklich Rolle mehr weil ich bin nur vorübergehend. So ist es diese beiden Jungs, vermutlich, sowohl Ben und Brian. Lassen Sie mich also vor, dass wir aktualisieren Ben, da er zuerst. Das erste Element der Liste Nun soll Brian sein. So Ben Punkt, an Brian. OK, was nun? Wer bekommt bei denen darauf hingewiesen? STUDENT: [unverständlich]. Sprecher 1: OK, so Brian hat bei Jason verweisen. Aber ich habe den Überblick über diesen Zeiger verloren? Muss ich wissen, wo Jason ist? STUDENT: [unverständlich]. Sprecher 1: ich tue, da ich die temporäre Zeiger. Und vermutlich habe ich nicht geändert Am neuen Knotenpunkt. So können wir einfach haben Brian Punkt bei wem ich bin bei zeigt. Und wir sind fertig. So ein Fall, Einfügung in die Anfang der Liste. Es gab zwei wichtige Schritte. Eines müssen wir Ben aktualisieren und anschließend wir müssen auch Brian aktualisieren. Und dann habe ich nicht zu stören latschen durch den Rest der Liste, weil wir bereits gefunden sein Lage, denn er gehörte zu den links von dem ersten Element. Alles klar, also ziemlich einfach. In der Tat fühlt sich an wie wir sind fast so dass dies zu kompliziert. So lasst uns nun abzupfen das Ende der Liste, und sehen, wo die Komplexität beginnt. Also, wenn jetzt, alloc ich aus dem Publikum. Wer will bis 55 spielen? Alles klar, ich sah deine Hand zuerst. Komm up. Ja. Wie ist dein Name? STUDENT: [unverständlich]. Sprecher 1: Habata. OK, come on up. Du wirst die Nummer 55 sein. Also, natürlich, gehören am Ende der Liste. Also lasst uns wiederholen Sie die Simulation mit mir wobei die PTR nur für einen Augenblick. Also ich bin zuerst zu zeigen bei was ist bei Ben zeigt. Wir beide zeigen jetzt an Brian. So 55 nicht kleiner ist als fünf. Also ich werde mich durch aktualisieren Hinweis auf nächste Zeiger Brians, die Es ist jetzt natürlich Jason. 55 nicht weniger als neun, so Ich werde PTR aktualisieren. Ich werde PTR aktualisieren. Ich werde PTR aktualisieren Ich werde PTR aktualisieren. Und ich werde - hmm, was ist Ihr Name? STUDENT: Diana. Sprecher 1: Diana wird zeigen, natürlich, bei null mit der linken Hand. Woher kommt eigentlich Habata gehören eindeutig? Auf der linken Seite, hier. Also wie kann ich wissen, sie hier zu setzen Ich glaube, ich habe Mist gebaut. Denn was ist Kunst PTR dieser Moment in der Zeit? NULL. So, obwohl, visuell, können wir offensichtlich sehen alle diese Jungs hier auf der Bühne. Ich habe nicht Spur der früheren gehalten Person in der Liste. Ich habe nicht einen Finger wies darauf hin, in diesem Fall wird die Knotennummer 34. Lassen Sie uns also tatsächlich beginnen diesen über. So jetzt habe ich wirklich benötigen eine zweite lokale Variable. Und das ist, was Sie sehen in der eigentliche Probe C-Code, wo, wie ich gehe, wenn ich meine rechte Hand darauf Jason, wodurch verlassen hinter Brian, ich besser beginnen mit meiner linken Hand zu aktualisieren, wo ich war, so dass, wie ich gehen durch diese Liste - mehr verlegen, als ich beabsichtigt Hier visuell - Ich werde um die zu bekommen Ende der Liste. Diese Hand ist immer noch null, das ist ziemlich nutzlos, außer, um anzuzeigen, Ich bin deutlich am Ende der Liste, aber jetzt habe ich wenigstens diese Vorgänger Zeiger hier, so jetzt, was die Hände und was Zeiger müssen aktualisiert werden? Dessen Hand wollen Sie zu rekonfigurieren zuerst? STUDENT: [unverständlich]. Sprecher 1: OK, so Diana. Wo möchten Sie darauf hinweisen Dianas linken Zeiger an? Bei 55 vermutlich so dass wir haben dort eingefügt. Und wo sollte 55 Zeiger gehen? Unten, was null. Und meine Hände, an dieser Stelle, nicht egal, denn sie waren einfach temporäre Variablen. So, jetzt sind wir fertig. Also die zusätzliche Komplexität gibt - und es ist nicht so schwer zu implementieren, aber wir brauchen einen sekundären Variablen zu machen sicher, dass vor dem ich meine rechte Hand, aktualisieren ich den Wert meines linken Hand pred Zeiger in diesem Fall so dass ich ein Schleppzeiger zu verfolgen, wo ich war, zu halten. Jetzt als zur Seite, wenn du denkst, diese durch, fühlt sich, wie es eine wenig ärgerlich zu haben, um zu halten verfolgen dieses linken Hand. Wie würde eine andere Lösung dieses Problems wurden? Wenn du um die Daten neu zu gestalten Struktur wir reden durch gerade jetzt? Wenn dies nur irgendwie fühlt sich ein wenig ärgerlich zu haben, wie, zwei Zeiger Gehen Sie durch die Liste, wer könnte sonst haben, in einer idealen Welt, aufrechterhalten Informationen, die wir brauchen? Ja? STUDENT: [unverständlich]. Sprecher 1: Genau. Rechts, so gibt es tatsächlich eine interessante Keim einer Idee. Und diese Idee von einer früheren Zeiger, deutete auf das vorherige Element. Was ist, wenn ich gerade ausgeführt, dass Innenseite der Liste selbst? Und es wird schwer sein, zu visualisieren dies ohne all das Papier auf den Boden fallen. Aber nehmen wir an, dass diese Jungs beide verwendet ihrer Hände, um eine frühere Zeiger und eine nächste Zeiger, wodurch Umsetzung dessen, was wir nennen eine doppelt verketteten Liste. Das würde mir erlauben, der Rücklauf zu sortieren, viel leichter, ohne dass ich die Programmierer, mit zu halten verfolgen manuell - wirklich manuell - von denen ich vorher in der Liste. So werden wir nicht tun. Wir werden es einfach halten, denn das ist gehen, um zu einem Preis zu kommen, zweimal so viel Platz für die Zeiger, wenn Sie eine zweite. Aber das ist in der Tat eine gemeinsame Datenstruktur als eine bekannte doppelt verketteten Liste. Lassen Sie uns die letztes Beispiel hier und setzen diese Jungs aus ihrem Elend. So malloc 20. Komm aus dem Gang gibt. Na gut, was ist Ihr Name? STUDENT: [unverständlich]. Sprecher 1: Wie bitte? STUDENT: [unverständlich]. Sprecher 1: Demeron? OK nach oben zu kommen. Du sollst 20 sein. Sie sind offensichtlich zu gehen gehören zwischen 17 und 22. Also lassen Sie mich meine Lektion lernen. Ich werde Zeiger beginnen zeigt auf Brian. Und ich werde meine linke Hand haben nur Brian aktualisieren, wie ich mich bewegen Jason, Kontrolle macht 20 weniger als neun? Nr. Ist 20 kleiner als 17? Nr. Ist 20 kleiner als 22? Ja. Also, was Zeiger oder Nadeln ändern müssen wo sie jetzt zeigen? So können wir tun 17 zeigt auf 20. Also das ist in Ordnung. Wo wollen wir darauf hinweisen Sie den Mauszeiger nun? Am 22. Und wir wissen, wo 22 ist, wieder dank Zu meiner temporären Zeiger. So sind wir es OK. Also wegen dieser vorübergehenden Lagerung Ich habe den Überblick, wo jeder ist gehalten. Und jetzt können Sie optisch in denen gehen Sie gehören, und jetzt müssen wir 1, 2, 3, 4, 5, 6., 7, 8, 9 Stress-Bälle, und einen Applaus für diese Jungs, wenn wir könnten. Schön gemacht. [Applaus] Sprecher 1: In Ordnung. Und Sie können halten die Stücke Papier als Andenken. Alles klar, also, vertrauen Sie mir, es ist viel leichter durch, dass mit Fuß Menschen, als es mit den tatsächlichen Code ist. Aber das, was Sie in nur einem Augenblick finden jetzt ist das gleiche - oh, danke. Danke - ist, dass Sie, dass die gleichen Daten zu finden Struktur, eine verknüpfte Liste, kann eigentlich als Baustein noch mehr verwendet werden anspruchsvolle Datenstrukturen. Und zu erkennen, das Thema hier ist, dass wir haben absolut mehr eingeführt Komplexität in der Umsetzung dieses Algorithmus. Insertion, und wenn wir gingen durch sie, Löschen und Suchen, ist ein wenig komplizierter, als es wurde mit einem Array. Aber wir gewinnen einige Dynamik. Wir bekommen eine adaptive Datenstruktur. Aber noch einmal, zahlen wir einen Preis der mit einigen zusätzliche Komplexität, sowohl in Umsetzung. Und wir sind bis random access gegeben. Und um ehrlich zu sein, gibt es nicht ein paar schöne reinigen Rutsche kann ich Ihnen, dass sagt hier, warum eine verlinkte Liste ist besser als ein Array. Und es dabei belassen. Weil das Thema wiederkehrende jetzt, auch um so mehr, in den kommenden Wochen ist dass es nicht unbedingt eine richtige Antwort. Aus diesem Grund haben wir die separate Achse haben von Design für Problem-Sets. Es wird sehr kontextsensitive ob Sie diese Daten verwenden Struktur oder dass man, und es wird davon abhängen, was für Sie wichtig ist im Hinblick auf von Ressourcen und Komplexität. Aber lassen Sie mich schlagen vor, die ideal Daten Struktur, der heilige Gral, wäre etwas, das konstante Zeit ist, unabhängig davon, wie viel Zeug ist drin, wäre es nicht erstaunlich, wenn ein Datenstruktur zurückgegeben Antworten konstante Zeit. Ja. Dieses Wort ist in Ihrem riesigen Wörterbuch. Oder nein, das ist nicht Wort. Oder irgendein solches Problem gibt. Nun lassen Sie uns sehen, wenn wir nicht mindestens einen Schritt in Richtung, dass. Lassen Sie mich schlagen eine neue Datenstruktur, kann für verschiedene Dinge verwendet werden, in diesem Fall als eine Hash-Tabelle. Und so sind wir tatsächlich wieder auf einem Blick bei einer Anordnung, in diesem Fall, und etwas willkürlich, habe ich daraus gezogen Hash-Tabelle als ein Array mit einer Art ein zweidimensionales Array - oder vielmehr es ist hier als zwei dargestellt dimensional array - aber das ist nur ein Array der Größe 26, so dass, wenn wir rufen Sie das Array, Tisch Halterung Null ist das Rechteck an der Spitze. Tabelle Klammer 25 ist das Rechteck an der Unterseite. Und dies ist, wie könnte ich einen Datensatz ziehen Struktur, in dem ich speichern möchten Die Namen. So zum Beispiel, und ich werde nicht zeichnen die Ganze hier auf dem Kopf, wenn ich hatte diese Anordnung, die ich nun gehe zu rufen eine Hash-Tabelle, und dies ist wieder Lage Null. Das hier ist die Lage ein, und so weiter. Ich behaupte, dass ich diese Daten verwenden wollen Struktur zum Zwecke der Diskussion die Namen von Personen zu speichern, Alice und Bob und Charlie und andere solche Namen. So dies jetzt denken, wie die Anfänge von, sagen wir, einem Wörterbuch mit vielen Worten. Sie geschehen, um Namen sein in unserem Beispiel hier. Und das ist nur allzu Germane, vielleicht, um Durchführung einer Rechtschreibprüfung, wie wir könnte für Problem stellte sechs. Wenn wir also eine Reihe von insgesamt Größe 26 so dass dies ist der 25. Standort an der Unterseite, und ich behaupte, dass Alice ist das erste Wort im Wörterbuch Namen, die ich möchte in den RAM einfügen in dieser Datenstruktur, wo sind Instinkte Ihnen mitteilt, dass Alices Name sollte in diesem Array gehen? Wir haben 26 Optionen. Wo wir zu ihr setzen wollen? Wir wollen, dass sie in der Halterung Null, nicht wahr? A für Alice, nennen wir, dass die Null. Und B wird man, und C werden zwei sein. So werden wir zu schreiben Alices Namen hier. Wenn wir dann einfügen Bob, seine Name wird hier zu gehen. Charlie wird hier zu gehen. Und so weiter nach unten durch Diese Datenstruktur. Dies ist eine wunderbare Datenstruktur. Warum? Nun, was ist die Laufzeit der Einsetzen eines Menschen Namen in dieser Datenstruktur gerade jetzt? Da diese Tabelle implementiert ist, wirklich, als ein Array. Nun, es ist Zeit konstant. Es ist, um von einem. Warum? Nun, wie Sie feststellen wo Alice gehört? Sie schauen auf die Buchstaben ihres Namens? Die erste. Und Sie können es zu bekommen, wenn es ein String ist, bei einem Blick auf String Klammer Null. So der nullten Zeichen des Strings. Das ist einfach. Wir haben das in der Krypto- Zuordnung Wochen. Und dann, wenn Sie wissen, dass Alices Schreiben ist das Kapital A, können wir subtrahieren Aus 65 oder Kapital A selbst, Das gibt uns Null. So wissen wir jetzt, dass Alice gehört an der Stelle Null. Und da einen Zeiger auf diese Daten Struktur, von einer Art, wie lange dauert es mich zu Standort zu finden Null in einem Array? Nur ein Schritt, rechts Es ist konstanter Zeit Aufgrund der zufälligen Zugriff wir vorgeschlagenen war ein Merkmal eines Arrays. Also kurz gesagt, herauszufinden, was der Index von Alice ist der Name, was ist, in In diesem Fall ist A, oder lasst uns einfach beheben dass auf Null, wobei B und C ist ein zwei, herauszufinden, dass aus konstant ist Zeit. Ich muss nur noch bei ihrem ersten Brief aussehen, herauszufinden, wo Null ist ein Anordnung ist auch konstante Zeit. Also das ist technisch wie zwei Schritte jetzt. Aber das ist immer noch konstant. So nennen wir diesen großen O von einem, so haben wir eingefügt Alice in dieser Tabelle in konstante Zeit. Aber natürlich bin ich als naiv hier, nicht wahr? Was, wenn es ein Aaron in der Klasse? Oder Alicia? Oder irgendwelche anderen Namen beginnend mit A. Wohin gehen wir zu setzen die Person, nicht wahr? Ich meine, jetzt gibt es nur noch drei Menschen auf dem Tisch, so wir vielleicht Aaron sollte an der Stelle setzen null eins zwei drei. Richtig, ich könnte A hier setzen. Aber dann, wenn wir versuchen, David eingefügt werden diese Liste, wo kommt David gehen? Jetzt ist unser System beginnt zu brechen unten, rechts? Da nun David endet hier wenn Aaron ist eigentlich hier. Und nun diese ganze Idee, dass eine saubere Datenstruktur, die uns konstante Zeit Insertionen nicht mehr konstante Zeit, denn ich muss überprüfen, oh, verdammt, ist jemand schon bei Alice Standort. Lassen Sie mich sondieren den Rest dieser Daten Struktur, auf der Suche nach einer Stelle zu setzen jemanden wie den Namen Aarons. Und so beginnt die zu zu linearen Zeit in Anspruch nehmen. Außerdem, wenn Sie wollen nun das finden Aaron in dieser Datenstruktur, und Sie überprüfen, und den Namen Aarons ist nicht hier. Idealerweise würde man nur sagen Aarons nicht in der Datenstruktur. Aber wenn Sie anfangen, Raum für Aaron, wo es hätte ein D haben oder E, Sie, schlimmsten Fall müssen prüfen die gesamte Datenstruktur, in wobei es obliegt in etwas linear in der Größe der Tabelle. Also alles in Ordnung, ich werde dieses Problem beheben. Das Problem hier ist, dass ich hatte 26 Elemente in diesem Array. Lassen Sie mich zu verändern. Whoops. Lassen Sie mich zu ändern, so dass eher als von Größe 26, insgesamt feststellen, die untere Index wird zu n minus 1 ändern. Wenn 26 ist eindeutig zu klein für den Menschen " Namen, denn es gibt Tausende von Namen der Welt, lasst uns einfach machen in 100 oder 1.000 oder 10.000. Lasst uns einfach zuteilen viel mehr Platz. Nun, das ist nicht unbedingt verringern die Wahrscheinlichkeit, dass wir nicht zwei Personen, deren Namen mit A, und so wurden Sie werde versuchen, A setzen Namen an der Stelle Null still. Sie sind immer noch zu kollidieren, die heißt, wir müssen noch eine Lösung zu setzen Alice und Aaron und Alicia und andere Namen, die mit A anderswo. Aber wie viel von einem Problem ist das? Was ist die Wahrscheinlichkeit, dass Sie haben Kollisionen in einem Daten Struktur wie diese? Nun, lassen Sie mich - wir kommen wieder auf diese Frage hier. Und, wie wir aussehen könnte lösen Sie es zuerst. Lassen Sie mich hochziehen diesen Vorschlag hier. Was wir gerade beschrieben ist ein Algorithmus, eine Heuristik genannt lineare Sondieren wobei, wenn Sie einfügen versucht hier etwas in dieser Daten Struktur, die als eine Hash-Tabelle, und es gibt keinen Raum gibt, Sie wirklich sondieren die Datenstruktur Überprüfung ist diese erhältlich? Ist dieser verfügbar ist vorhanden? Ist das vorhanden? Und wenn es endlich ist, legen Sie die nennen, die Sie ursprünglich gedacht anderswo an dieser Stelle. Aber im schlimmsten Fall die einzige Stelle könnte die ganz unten der Daten sein Struktur, die ganz am Ende des Arrays. So linearen Sondieren, im schlimmsten Fall, obliegt in einen linearen Algorithmus, bei dem Aaron, wenn er eingesetzt als letztes passiert in dieser Datenstruktur, könnte er kollidieren mit dieser ersten Stelle, aber dann durch Pech am Ende ganz am Ende. Das ist also nicht konstant Zeit heilige Gral für uns. Dieser Ansatz der Einfügen von Elementen in eine Datenstruktur genannt Hash Tabelle scheint nicht konstant Zeit zumindest nicht in den allgemeinen Fall. Es kann in etwas linear über. So was, wenn wir lösen Kollisionen etwas anders? Also hier ist eine differenziertere Ansatz zu dem, was noch rief eine Hash-Tabelle. Und durch Hash, so nebenbei, was Ich meine, ist, dass der Index Ich bezog mich auf früher. Um Hash etwas kann gedacht als ein Verb. Also, wenn Sie Hash Alice ist ein Name, eine Hash-Funktion, so zu sprechen, sollte eine Zahl zurückgibt. In diesem Fall ist Null, wenn sie an gehört Lage null, eins, wenn sie an gehört eine Lage, und so weiter. Also meine Hash-Funktion war bisher super einfach, nur Blick auf die ersten Buchstaben in den Namen einer Person. Aber eine Hash-Funktion als Eingang einige Stück von Daten, ein String, ein int, was auch immer. Und es spuckt der Regel eine Nummer. Und diese Zahl ist, wo diese Daten Element gehört in einer Datenstruktur hier als Hash-Tabelle bekannt. Also einfach intuitiv, ist dies ein etwas anderen Zusammenhang. Dies ist eigentlich auf ein Beispiel bezogen mit Geburtstagen, wo Es können so viele wie sein 31 Tage im Monat. Aber was hat diese Person zu entscheiden, tun im Falle einer Kollision? Context ist jetzt, nicht eine Kollision Namen, aber eine Kollision Geburtstage, wenn zwei Menschen haben am gleichen Tag Geburtstag auf 2. Oktober, zum Beispiel. STUDENT: [unverständlich]. Sprecher 1: Ja, so haben wir hier die Nutzung von verknüpften Listen. So sieht es ein wenig anders als wir es früher machte. Aber wir scheinen auf ein Array haben Auf der linken Seite. Das ist ein Index, für keine besonderen Grund. Aber es ist immer noch ein Array. Es ist ein Array von Zeigern. Und jedes dieser Elemente, die jeweils diese Kreise oder Schrägstriche - der Schrägstrich repräsentiert null - jede dieser Zeiger ist offenbar, die auf was Datenstruktur? Eine verkettete Liste. Deshalb haben wir jetzt die Möglichkeit, hart-Code in unserem Programm Die Größe der Tabelle. In diesem Fall wissen wir, es ist nie mehr als 31 Tage in einem Monat. So hart zu kodieren einen Wert wie 31 vernünftig in diesem Zusammenhang. Im Zusammenhang mit Namen, harte Kodierung 26 ist nicht unvernünftig es Menschen Nur Namen beginnen mit, zum Beispiel, denen das Alphabet A bis Z. Wir können sie alle in dieser Daten stopfen Struktur so lange, wenn wir eine bekommen Kollision, wissen wir nicht setzen die Namen hier wir denken, anstatt diesen Zellen nicht als Strings selbst, sondern als Zeiger auf, zum Beispiel, Alice. Und dann kann Alice einen weiteren Zeiger auf einen anderen Namen, beginnend mit A. Und Bob geht eigentlich hier. Und wenn es ein anderer Name ab mit B, endet er hier. Und so jedes der Elemente dieser Tabelle zwei, wenn wir diese ein konzipiert wenig klüger - Come on - wenn haben wir diese ein wenig mehr geschickt, jetzt wird eine adaptive Daten Struktur, wo es keine harte Grenze auf wie viele Elemente, die Sie einfügen können hinein, denn wenn Sie zu tun haben eine Kollision, ist das in Ordnung. Dann nichts wie los und hängen Sie ihn an was wir sahen, war ein bisschen vor bekannt als verknüpfte Liste. Nun lasst uns Pause nur für einen Augenblick. Was ist die Wahrscheinlichkeit einer Kollision in erster Linie? Richtig, vielleicht bin ich über das Denken, vielleicht Ich bin über Projektierung dieses Problems weil Sie wissen, was? Ja, ich kann kommen mit beliebigen Beispiele aus der Spitze von meinem Kopf wie Allison und Aaron, aber in Wirklichkeit, bei einer gleichmäßigen Verteilung von Eingänge, die einige zufällige Insertionen ist in eine Datenstruktur, was wirklich ist die Wahrscheinlichkeit einer Kollision? Nun stellt sich heraus, es ist eigentlich Super-High. Lassen Sie mich dies verallgemeinern Problem ist, als dieses. Also in einem Raum von n CS50 Studenten, was ist die Wahrscheinlichkeit, dass mindestens zwei Schüler in den Raum haben am gleichen Tag Geburtstag? Also gibt es was. ein paar hund - 200, 300 Menschen hier und mehrere hundert Menschen heute zu Hause. Also, wenn Sie wollten uns fragen, was ist die Wahrscheinlichkeit, dass zwei Menschen in diesem Raum mit dem gleichen Geburtstag, können wir dieses heraus. Und ich behaupte, tatsächlich gibt es zwei Personen mit dem gleichen Tag Geburtstag. Zum Beispiel hat jemand haben heute Geburtstag? Yesterday? Morgen? Alles klar, so fühlt es sich wie ich bin zu haben, um diese 363 oder so mehr zu tun mal um tatsächlich herauszufinden, wenn wir haben eine Kollision. Oder wir könnten einfach tun dies mathematisch anstatt mühsam dies zu tun. Und schlagen vor, folgenden. So schlage ich vor, dass wir das Modell Wahrscheinlichkeit, dass zwei Menschen, die die gleichen Tag Geburtstag wie die Wahrscheinlichkeit von 1 minus die Wahrscheinlichkeit nicht einer, am gleichen Tag Geburtstag. Also, um das, und das ist nur der andere Art des Schreibens dieses, für die ersten Person im Raum, er oder sie kann irgendeine der möglichen haben Geburtstage davon 365 Tage im Jahr, Entschuldigung an Personen mit im Februar 29. Geburtstag. So ist die erste Person in diesem Zimmer ist kostenlos um eine beliebige Anzahl von Geburtstagen haben aus der 365 Möglichkeiten, so dass das machen wir 365 geteilt durch 365, das ist eins. Die nächste Person im Raum, wenn das Ziel ist, um eine Kollision zu vermeiden, können nur haben seinen Geburtstag auf, wie viele verschiedene mögliche Tage? 364. So der zweite Term in diesem Ausdruck ist Wesentlichen tun, dass Mathematik für uns durch Subtraktion aus einer möglichen Tag. Und dann am nächsten Tag, am nächsten Tag, die am nächsten Tag auf der Gesamtzahl der Menschen in den Raum. Und wenn wir dann überlegen, was ist dann die Wahrscheinlichkeit nicht von jedermann mit einzigartige Geburtstage, aber wieder minus 1 das, was wir bekommen, ist ein Ausdruck Das kann sehr phantasievoll sehen wie folgt aus. Aber es ist mehr interessant auf visuell aussehen. Dies ist ein Diagramm, in dem auf der x-Achse die Zahl der Personen im Raum, die Anzahl der Geburtstage. Auf der y-Achse ist die Wahrscheinlichkeit, einer Kollision zwei Personen mit dem gleichen Geburtstag. Und das Essen zum Mitnehmen aus dieser Kurve ist dass, sobald man auf 40 gefallen Studenten, sind Sie mit einer Wahrscheinlichkeit von 90% combinatorically von zwei oder mehr Personen mit das gleiche GEBURTSTAG. Und wenn Sie erst einmal 58 Personen, es ist wie nahezu 100% Chance die beiden Menschen in den Raum gehen, um die haben gleichen Tag Geburtstag, obwohl es 365 oder 366 möglich Eimer und nur 58 Personen im Raum. Nur statistisch Sie wahrscheinlich bekommen Kollisionen, die in kurzen motiviert diese Diskussion. Dass selbst wenn wir Lust bekommen hier und beginnen mit diesen Ketten, wir sind immer noch gehen, um Kollisionen zu haben. Damit stellt sich die Frage, was ist der Kosten der Insertionen und Deletionen in eine Datenstruktur wie diese? Nun lassen Sie mich schlagen - und ließ mich zurück auf den Bildschirm über hier - wenn wir n Elemente in der Liste, also, wenn wir versuchen, einfügen n Elemente, und wir haben wie viele insgesamt Eimer? Sagen wir 31 gesamt Eimer bei Geburtstag. Was ist die maximale Länge eines dieser Ketten potenziell? Wenn wieder gibt es 31 möglich Geburtstage in einem bestimmten Monat. Und wir sind nur Verklumpung alle - Eigentlich ist das eine dumme Beispiel. Lassen Sie uns 26 statt. Also, wenn tatsächlich Leute, deren Namen beginnen mit A bis Z, wodurch us 26 Möglichkeiten. Und wir verwenden eine Datenstruktur wie das, was wir gerade gesehen haben, wobei wir ein Array von Zeigern, die jeweils Punkte auf einer verketteten Liste, wo der erste Liste ist jeder mit dem Namen Alice. Die zweite Liste ist jedes mit der Name beginnend mit A beginnend mit B, und so fort. Was ist der wahrscheinlich Länge jedes diese Listen, wenn wir davon ausgehen, ein schönes, sauberes Verteilung von Namen von A bis Z über die gesamte Datenstruktur? Es gibt n Menschen in der Datenstruktur geteilt durch 26, wenn sie schön sind verteilt über den gesamten Datenstruktur. So die Länge eines jeden von ihnen Ketten n geteilt durch 26. Aber in O-Notation, was ist das? Was ist das eigentlich? Also es ist wirklich nur n, nicht wahr? Weil wir in der Vergangenheit gesagt, ugh, dass Sie dividieren durch 26. Ja, in Wirklichkeit ist es schneller. Aber in der Theorie ist es nicht grundsätzlich alles, was schneller. Also haben wir scheinen nicht allzu viel sein näher an diesem heiligen Gral. In der Tat ist dies nur lineare Zeit. Heck, an dieser Stelle, warum tun wir das nicht benutzen Sie einfach eine riesige verketteten Liste? Warum gehen wir nicht einfach eine riesige Anordnung, um die Namen zu speichern jeder im Raum? Nun, das ist es noch etwas zwingenden über eine Hash-Tabelle? Gibt es noch etwas Zwingendes über eine Datenstruktur Das sieht dann so? This. STUDENT: [unverständlich]. Sprecher 1: Richtig, und wieder, wenn es nur eine lineare Algorithmus und eine linearer Zeit Datenstruktur, warum nicht ich speichern nur alle Namen in einer großen Array oder in einer großen verketteten Liste? Und aufhören, so viel schwieriger CS als es sein muss? Was ist zwingend über diese, auch obwohl ich kratzte es aus? STUDENT: [unverständlich]. Sprecher 1: Insertionen sind nicht? Teure mehr. So Insertionen potentiell noch Zeit konstant sein, auch wenn Ihre Daten Struktur sieht wie folgt aus, eine Reihe von Zeiger, von denen jede jeweils weist möglicherweise eine verknüpfte Liste. Wie konnten Sie erreichen konstant Zeit Einfügen von Namen? Halten Sie es in der Front, nicht wahr? Wenn wir opfern einen Design-Ziel von früher, wo wir hin wollten halten alle Namen, zum Beispiel sortiert, oder alle Nummern auf der Bühne übersetzt, nehme an, dass wir eine haben unsortierte verkettete Liste. Es kostet nur uns einen oder zwei Schritte, wie im Fall von Ben und Brian früher, um ein Element zu legen der Anfang der Liste. Also, wenn wir nicht über das Sortieren völlig egal der Namen beginnend mit A oder alle die Namen mit dem Anfangsbuchstaben B, können wir noch erreichen konstanter Zeit Insertion. Jetzt blickte Alice oder Bob oder einen beliebigen Namen allgemein ist noch what? Es ist groß O von n durch 26 geteilt, in die Idealfall, wo jeder ist gleichmäßig verteilt, wo es so viele A die da sind z, das ist wahrscheinlich unrealistisch. Aber das ist immer noch linear. Aber hier kommen wir zurück zu dem Punkt der asymptotischen Notation ist theoretisch wahr. Aber in der realen Welt, wenn ich behaupte, dass mein Programm kann etwas tun 26 mal schneller als Ihr, deren Programm willst du lieber mit? Mit freundlichen oder Mine, die ist 26 mal schneller? Realistisch betrachtet, ist die Person, deren 26 mal schneller, auch wenn theoretisch unsere Algorithmen in der gleichen laufen asymptotische Laufzeit. Lassen Sie mich schlagen eine andere Lösung überhaupt. Und wenn dies nicht blow your mind, wir sind aus Datenstrukturen. Das ist es also ein Trie - Art von einem dummen Namen. Es kommt von Abfragen und das Wort geschrieben Trie, t-r-i-e, weil Natürlich Retrieval klingt Trie. Aber das ist die Geschichte des Wortes Trie. So ein Trie ist in der Tat eine Art von Baum, und es ist auch eine Anspielung auf das Wort. Und auch wenn man es nicht ganz sehen mit dieser Visualisierung ist ein Trie ein Baum strukturiert, wie ein Stammbaum mit ein Vorfahr an der Spitze und viele der Enkel und Urenkel wie Blätter auf dem Boden. Aber jeder Knoten in einem Trie ist ein Array. Und es ist in einer Reihe - und lassen Sie uns vereinfachen für einen Moment - es ist ein Anordnung, in diesem Fall der Größe 26, wobei jeder Knoten ist wiederum ein Array der Größe 26, wobei das nullte Element daß Array repräsentiert A, und die letzte Element in jedem solchen Array stellt Z. So schlage ich vor, dann, dass diese Daten Struktur, wie ein Trie bekannt, kann auch, um Wörter zu speichern verwendet. Wir sahen einen Moment vor, wie wir speichern Wörter oder benennt in diesem Fall, und wir früher sahen, wie wir Nummern zu speichern, aber wenn wir auf Namen oder Zeichenfolgen konzentrieren hier bemerken, was ist interessant. Ich behaupte, dass der Name Maxwell ist innerhalb dieser Datenstruktur. Wo sehen Sie Maxwell? STUDENT: [unverständlich]. Sprecher 1: Auf der linken Seite. Also, was ist interessant, mit diesen Daten Struktur ist eher als Geschäft der String M-A-X-W-E-L-L Backslash Null, alle zusammenhängend, was Sie stattdessen tun folgt. Wenn dies ein Trie wie Datenstruktur, enthält, deren jeweilige Knoten ist wiederum ein Array, und Sie wollen Maxwell speichern, müssen Sie zuerst Index und so den Root-Knoten, so zu sprechen, den obersten Knoten, an der Stelle M, rechts, so ungefähr in der Mitte. Und dann von dort aus folgen Sie Zeiger auf einen untergeordneten Knoten, so zu sprechen. So im Stammbaum Sinne Sie folgen ihm nach unten. Und das führen Sie zu einem anderen Knoten auf der linken Seite, das ist nur ein weiteres Array. Und dann, wenn Sie wollen, um Maxwell zu speichern, finden Sie den Zeiger, stellt A, ist das diese hier. Dann sind Sie auf den nächsten Knoten gehen. Und beachten Sie - das ist, warum das Bild des ein wenig irreführend - dieser Knoten sehen super winzig. Aber in dem Rechts davon ist, Y und Z. Es ist nur der Autor hat das abgeschnitten Bild, so dass Sie tatsächlich Dinge sehen. Ansonsten ist dieses Bild wäre enorm breit. So, jetzt Index in Ort X, dann W, dann e und L, dann L. Dann was ist diese Neugier? Nun, wenn wir über diese Art von neuen nehmen, wie man einen String in einem Geschäft Datenstruktur, müssen Sie noch Wesentlichen abhaken in den Daten Struktur, dass ein Wort, das hier endet. Mit anderen Worten: Jeder dieser Knoten irgendwie hat sich daran zu erinnern, dass wir tatsächlich gefolgt all dieser Zeiger und verlassen ein wenig Brotkrümel unten hier davon Struktur M-A-X-W-E-L-L geben ist in der Tat in dieser Datenstruktur. So könnten wir dies wie folgt tun. Jeder der Knoten in dem Bild Wir Säge hat einen, ein Array der Größe 27. Und es ist jetzt 27, da in p gesetzt sechs, wir tatsächlich geben Ihnen einen Apostroph, so können wir haben Namen wie O'Reilly und andere mit Apostroph. Aber gleiche Idee. Jedes dieser Elemente in die Array zeigt auf eine Struktur Knoten, so dass nur ein Knoten. Also das ist sehr an unserer verketteten Liste. Und dann habe ich eine Boolean, denen ich Ihnen rufen Wort, das nur noch zu dann, wenn ein Wort endet an diesem Knoten im Baum. Es stellt gewissermaßen die kleine Dreieck sahen wir vor einem Moment. Also, wenn ein Wort endet an diesem Knoten in der Baum, wird das Wort Feld wahr zu sein, was ist konzeptionell Abhaken oder wir zeichnen dieses Dreieck, ja, es ist ein Wort, das hier. Das ist also ein Trie. Und jetzt ist die Frage, was ist seine Laufzeit? Ist er groß O von n? Ist es etwas anderes? Nun, wenn Sie n Namen in dieser Daten Struktur, wobei nur einer von Maxwell sie, was ist die Laufzeit Einfügen oder der Suche nach Maxwell? Was ist die Laufzeit Einsetzen von Maxwell? Wenn es n anderen Namen bereits in der Tabelle? Ja? STUDENT: [unverständlich]. Sprecher 1: Ja, es ist die Länge der Name, nicht wahr? So M-a-x-w-e-l-l so fühlt es sich wie folgt Algorithmus ist groß O von sieben Jahren. Jetzt natürlich der Name wird in der Länge variieren. Vielleicht ist es ein kurzer Name. Vielleicht ist es ein längerer Name. Aber was ist der Schlüssel hier ist, dass es ist eine konstante Anzahl. Und vielleicht ist es nicht wirklich konstant, aber Gott, wenn realistisch, in ein Wörterbuch, gibt es wahrscheinlich eine Grenze von der Anzahl von Buchstaben in einem den Namen der Person in einem bestimmten Land. Und so können wir davon ausgehen, dass Wert eine Konstante ist. Ich weiß nicht, was es ist. Es ist wahrscheinlich größer als Wir denken es ist. Da gibt es immer irgendeine Ecke Fall mit einem verrückten langen Namen. So nennen wir es k, aber es ist immer noch ein konstant vermutlich, denn jeder Name in der Welt, zumindest in eine bestimmten Land, ist, dass Länge oder kürzer, es ist also konstant. Aber wenn wir etwas gesagt ist groß O von einem konstanten Wert, was ist das wirklich gleichwertig? Das ist wirklich das Gleiche mit den Worten konstante Zeit. Jetzt sind wir Art von Betrug, nicht wahr? Wir sind irgendwie nutzt einige Theorie hier zu sagen, dass gut ist, um von k eigentlich nur eines zu bestellen, und es ist Zeit konstant. Aber es ist wirklich. Da die wichtigste Erkenntnis dabei ist, dass wenn wir n Namen bereits in diesem Datenstruktur, und wir Einsatzes Maxwell, ist die Menge an Zeit, die uns einfügen Maxwell überhaupt betroffenen durch, wie viele andere Menschen sind in der Datenstruktur? Scheint nicht zu sein. Wenn ich eine Milliarde mehr Elemente dazu trie, und fügen Sie anschließend Maxwell, wird er überhaupt betroffen? Nr. Und das ist anders als irgendeine der Tag-Daten Strukturen, die wir haben bisher gesehen, wo die Laufzeit Ihres Algorithmus ist völlig unabhängig davon, wie viel Zeug ist oder nicht bereits in dieser Datenstruktur. Und so bietet Ihnen mit diesem ist jetzt eine Chance für p set sechs, das wird wieder einzubeziehen Umsetzung Ihrer eigenen Rechtschreibprüfung, das Lesen in 150.000 Worte, wie sie am besten zu lagern, dass ist nicht offensichtlich. Und obwohl ich strebte zu finden der heilige Gral, das tue ich nicht dadurch gekennzeichnet, dass ein Trie ist. In der Tat kann eine Hash-Tabelle sehr gut erweisen sich als wesentlich effizienter. Aber das sind nur - das ist nur eine der Design-Entscheidungen Sie machen müssen. Aber bei der Schließung nehmen wir 50 oder so Sekunden, um einen Blick auf, was sich vor nächste Woche und darüber hinaus haben wir Übergang aus dieser Befehlszeile Welt, wenn C-Programme, die Dinge web Basis und Sprachen wie PHP und JavaScript und das Internet selbst, Protokolle wie HTTP, die Sie haben gemacht für seit Jahren gewährt jetzt, und tippte fast jeden Tag, vielleicht, oder gesehen. Und wir werden zu schälen beginnen wieder die Schichten, was ist das Internet. Und was ist der Code, zugrunde heutigen Werkzeugen. Also 50 Sekunden dieser Teaser hier. Ich gebe Ihnen Warriors of the Net. [VIDEO PLAYBACK] -Er kam mit einer Botschaft. Mit einem Protokoll alle seine eigenen. Er kam in eine Welt von grausamer Firewalls gefühllos Router und Gefahren weit schlimmer als der Tod. Er ist schnell. Er ist stark. Er ist TCPIP. Und er hat Ihre Adresse. Warriors of the Net. [END VIDEO PLAYBACK] Sprecher 1: Das ist, wie das Internet wird wie in der nächsten Woche zu arbeiten.