Sprecher 1: Okay, das ist so CS50 Dies ist das Ende der fünften Woche. Und erinnern daran, dass wir das letzte Mal begann man die Züchter Daten Strukturen, die zu lösen begonnen Probleme, die die Einführung begonnen neue Probleme, doch der Schlüssel dazu war die Art von Einfädeln, dass wir begonnen, von Knoten zu Knoten zu tun. Also das ist natürlich, eine einfach verkettete Liste. Und einfach verkettete, Ich meine, es gibt nur eine Faden zwischen jedem dieser Knoten. Stellt sich heraus, die Sie tun können, Züchter Dinge wie doppelt verkettete Listen wobei Sie einen Pfeil haben in beide Richtungen, die kann mit bestimmten Wirkungsgrade zu helfen. Aber dies das Problem gelöst? Welches Problem hat dieses Problem zu lösen? Warum haben wir am Montag, kümmern? Warum, in der Theorie, wir kümmern wir am Montag? Was tut es? 

Publikum: Wir können dynamisch ändern Sie die Größe. 

Sprecher 1: OK, also wir können dynamisch ändern Sie die Größe. Gut gemacht, alle beide. So können Sie dynamisch die Größe dieses Datenstruktur, wobei eine Anordnung, Recall, müssen Sie eine kennen priori, wie viel Platz Sie wollen und wenn Sie ein wenig mehr Art von Raum, sind Sie kein Glück. Sie müssen sich eine ganz neue Palette erstellen. Sie müssen alle bewegen Sie Daten von einem zum anderen, schließlich befreien das alte Array wenn du kannst, und dann fortzufahren. Was fühlt sich einfach sehr teuer und sehr ineffizient, und in der Tat kann es sein. Aber das ist nicht alles gut. Wir zahlen einen Preis, was einem der offensichtlicheren Preise, die wir bezahlen, indem Sie eine verkettete Liste? 

ZIELGRUPPE: Wir haben zu bedienen Doppelraum für jeden einzelnen. Sprecher 1: Ja, so müssen wir uns mindestens doppelt so viel Platz. In der Tat, erkannte ich, das Bild der sogar ein wenig irreführend, denn am CS50 IDE in eine Menge von modernen Computer, ein Zeiger oder eine Adresse ist in der Tat nicht vier Byte. Es ist sehr oft diese Tage acht Bytes, die bedeutet die unterste Rechtecke gibt es in der Realität sind so eine Art doppelt so groß wie das, was ich gezeichnet habe, was bedeutet, dass Sie drei Mal so sind viel Platz, da wir sonst haben könnte. Jetzt zur gleichen Zeit, wir sind noch im Gespräch Bytes, nicht wahr? Wir sind nicht unbedingt sprechen Megabyte oder Gigabyte, es sei denn, diesen Datenstrukturen zu groß. 

Und so beginnen wir heute zu prüfen, wie wir Daten untersuchen könnten effizienter, wenn in Tatsächlich werden die Daten immer größer. Aber lassen Sie uns versuchen, kanonisieren die Operationen ersten dass Sie sich auf diese tun können Arten von Datenstrukturen. So etwas wie eine verknüpfte Liste in der Regel unterstützt Operationen wie Löschen, einzufügen, und zu suchen. Und was mache ich damit? Das bedeutet nur, dass in der Regel, wenn Menschen nutzen verknüpften Liste, sie oder jemand anderes eingeführt hat Funktionen wie Löschen, Einfügen, und suchen, so können Sie tatsächlich etwas zu tun nützlich bei der Datenstruktur. Werfen wir also einen Blick an, wie wir implementieren ein Code für eine verkettete Liste wie folgt. 

Das ist also nur einige C-Code, nicht einmal ein komplettes Programm dass ich wirklich schnell aufgepeitscht. Es ist nicht online in der Distribution Code, weil es nicht tatsächlich ausgeführt. Aber ich habe gerade bemerkt mit einem Kommentar sagte: Punkt Punkt Punkt, es gibt etwas, dort, Punkt Punkt Punkt, dort etwas. Und lassen Sie uns einfach betrachten was die saftige Teile sind. Also auf Linie drei, daran erinnern, dass dies jetzt Wir haben vorgeschlagen, die Vereinbarkeit eines Knotens letzten Zeit, eine jener rechteckige Objekte. Es verfügt über einen int, die wir N nennen, aber wir nennen es könnte alles, und dann ein struct node Stern neben bezeichnet. Und genauso klar zu sein, dass die zweite Linie, auf der Linie sechs, was ist das? Wie ist es für uns tut? Denn es sieht mehr kryptisch als unsere üblichen Variablen. 

Publikum: Es macht es mehr als eine zu bewegen. 

Sprecher 1: Es macht es mehr als eine zu bewegen. Und um genauer zu sein, es wird die Adresse zu speichern des Knotens, der gemeint hat, um sein semantisch daneben, nicht wahr? So dass es nicht zu gehen unbedingt etwas zu bewegen. Es ist gerade dabei, speichern Wert, das ist, gehen, um die Adresse sein, von einem anderen Knoten, und das ist, warum wir die Struktur Knoten Stern, der Stern bezeichnet ein Zeiger oder eine Adresse. OK, so jetzt, wenn Sie annehmen, dass wir Diese N zur Verfügung zu uns, und lassen Sie uns davon ausgehen, dass jemand anderes hat eingefügt eine ganze Reihe von ganzen Zahlen in einer verketteten Liste. Und das verknüpfte Liste ist die von einem gewissen Punkt hingewiesen eine Variable namens Liste, die ist hier als Parameter übergeben, wie gehe ich über Linie gehen 14 Umsetzung Suche? Mit anderen Worten, wenn ich die Umsetzung Funktion, deren Zweck im Leben ist es, eine int und dann das zu nehmen beginnend von einer verknüpften Liste, das ist ein Zeiger auf die verbundene Liste. Wie erste, die ich denke, David war unsere Freiwilligen am Montag, er wurde bei weis die gesamte verknüpfte Liste, es ist, als ob wir vorbei David in unser Argument hier. Wie sprechen wir über das Durchlaufen dieser Liste gehen? Nun stellt sich heraus, dass, obwohl Zeiger sind relativ neu jetzt an uns, wir können dies relativ zu tun unkompliziert. 

Ich werde weitermachen und deklarieren Sie eine temporäre Variable, per Konvention wird nur gehen Zeiger aufgerufen werden, oder PTR, aber Sie es nennen könnte, was Sie wollen. Und ich werde nicht initialisiert werden der auf den Anfang der Liste. So können Sie Art denken Sie an dieses wie ich dem Lehrer den anderen Tag, Art auf jemand zeigt unter unseren Menschen als Freiwillige. Ich bin also eine temporäre Variable, die ist nur zeigt auf die gleiche Sache dass unsere zufällig benannt Freiwilliger David wurde auch darauf hingewiesen. Jetzt, während Zeiger nicht null ist, weil Rückruf dass null ist einige spezielle Sentinelwert das grenzt das Ende der Liste, so, während ich nicht das Zeige Boden wie unsere letzte Freiwilligen war, lassen Sie uns weitermachen und gehen Sie folgendermaßen vor. Wenn pointer-- und jetzt bin Art von wollen zu tun, was wir mit dem Schüler haben structure-- wenn Zeiger Punkt neben equals-- eher, wenn Zeiger dot N gleich entspricht die Variable N, die Argument, die übergeben worden ist, dann will ich voran gehen und sagen, return true. Ich habe die Anzahl N Innenseite gefunden einem der Knoten meiner verketteten Liste. Aber der Punkt nicht mehr arbeitet in diesem Zusammenhang, weil Zeiger PTR ist tatsächlich ein Zeiger, um eine Adresse, Wir können tatsächlich wunderbar benutzen endlich ein Stück Syntax diese Art von Marken intuitiven Sinn und tatsächlich verwenden einen Pfeil hier, was bedeutet, gehen von diese Adresse auf den ganzzahligen dort. So ist es in sehr ähnlich Grundprinzip her der Punkt-Operator, sondern weil Zeiger kein Zeiger und nicht eine tatsächliche Struktur selbst, wir benutzen Sie einfach auf den Pfeil. 

Also, wenn der aktuelle Knoten daß ich, der temporäre Variable, bin am Zeige nicht N, was will ich machen? Na ja, mit meinem menschlichen Freiwilligen dass wir hier den anderen Tag, wenn meine erste Mensch ist nicht der, den ich wollen, und vielleicht der zweite Mensch ist nicht die, die ich will, und der dritte, I müssen körperlich in Bewegung bleiben. Wie, wie kann ich Schritt durch eine Liste? Als wir ein Array Sie, gerade getan hast, wie ich plus plus. Aber in diesem Fall ist es ausreichend, tun Zeiger, bekommt, Zeiger, neben. Mit anderen Worten, das nächste Feld, ist wie alle der linken Hände dass unsere menschlichen Freiwilligen am Montag, wurden mit den an einem anderen Knotenpunkt. Das waren ihre nächsten Nachbarn. 

Also, wenn ich durch diese Liste zu treten, Ich kann nicht einfach zu tun I plus plus mehr, Ich muss sagen, statt I, Zeiger, wird um gleiche, was auch immer das nächste Feld ist, Das nächste Feld ist, ist das nächste Feld, nach all diesen linke Hand dass wir auf der Bühne hatten Zeige zu einigen Folgewerte. Und wenn ich durchkommen dass ganze Iteration und schließlich, schlug ich null nicht mit fand N noch, ich habe gerade return false. Also noch einmal, alles, was wir hier tun, nach dem Bild vor einem Augenblick, beginnt mit dem Hinweis auf die Anfang der Liste vermutlich. Und dann habe ich zu prüfen, ist der Wert Ich suche nach gleich neun? Wenn dem so ist, kehre ich wahr und ich fertig bin. Wenn nicht, ich meine Hand zu aktualisieren, Alias-Zeiger, darauf hinzuweisen am Standort des nächsten Pfeils, und dann Standort der nächsten Pfeils, und dem nächsten. Ich bin einfach zu Fuß durch dieses Array. 

Also noch einmal, wer sich interessiert? Wie, was ist dies ein Bestandteil für? Nun, daran erinnern, dass wir uns vorgestellt die Vorstellung von einem Stapel, der ist ein abstrakter Datentyp, soweit es kein C Sache, es ist nicht eine Sache, CS50, es ist eine abstrakte Idee, diese Idee der Stapel Dinge aufeinander Das kann umgesetzt werden Bündeln von verschiedenen Möglichkeiten. Und eine Möglichkeit, die wir vorgeschlagen war mit ein Array oder eine verknüpfte Liste. Und es stellt sich heraus, dass kanonisch ein Stack unterstützt mindestens zwei Operationen. Und die Schlagworte sind Push, um drücken Sie etwas auf dem Stapel, wie ein neues Fach in der Speisesaal, oder Pop, was bedeutet, den obersten entfernen Tablett aus dem Stapel im Speisesaal Flur, und dann vielleicht noch einige andere Operationen als auch. Also, wie können wir definieren die Struktur dass wir fordern nun einen Stapel? 

Nun, wir haben alle die erforderliche Syntax zur Verfügung in C, sage ich, geben Sie mir eine Typdefinition eine Struktur innerhalb eines Stapels, Ich werde sagen, ein Array ist, der eine ganze Reihe von Zahlen und dann deine Größe. Also mit anderen Worten, wenn ich will, dies im Code zu implementieren, lassen Sie mich gehen und nur irgendwie zu ziehen, was dieser sagt. Also das ist zu sagen, gib mir ein Struktur, die ein Array bekam ist, und ich weiß nicht, was Kapazität ist, es ist offensichtlich eine Konstante, die ich an anderer Stelle definiert ist, und das ist in Ordnung. Aber angenommen, es ist nur eine, zwei, drei, vier, fünf. So Kapazität ist 5. Dieses Element Innenseite meiner Struktur Zahlen genannt werden. Und dann, eines muss ich andere nicht fest offenbar genannte Größe, die zunächst werde ich zu bestimmen, wird auf Null initialisiert. Wenn es nichts in der Stapel, Größe Null ist, und es ist Müll Werte in Zahlen. Ich habe keine Ahnung, was da drin nur noch. 

Also, wenn ich drücken etwas in den Stapel, nehme ich die Funktion Push anrufen, und Ich sage zu schieben 50, wie die Zahl 50, wo würden Sie vorschlagen Ich ziehe es in diesem Array? Es gibt fünf verschiedene mögliche Antworten. Wo wollen Sie, um die Zahl 50 zu schieben? Wenn das Ziel ist hier, wieder, rufen Sie die Funktionsdruck, übergeben in einem Argument von 50, wo soll ich sagen? Fünf possible-- Chance von 20% richtig zu raten. Ja? 

ZIELGRUPPE: Ganz rechts. 

Sprecher 1: Ganz rechts. Es gibt nun eine Chance von 25% richtig zu raten. Also das wäre eigentlich in Ordnung sein. Gemäß der Konvention, werde ich mit einer Reihe sagen, wir würden in der Regel auf der linken Seite zu beginnen, aber wir konnten auf jeden Fall beginnen an der rechten Seite. So der Spoiler hier wäre ich wahrscheinlich, um es auf der linken Seite zu ziehen, genau wie in einem normalen Array, in dem Ich beginnen werde links nach rechts. Aber wenn Sie drehen können der arithmetische, fein. Es ist einfach nicht üblich. OK, ich brauche eine zu machen weitere Änderung though. Nun, da ich etwas geschoben auf den Stapel, was kommt als nächstes? 

Also gut, ich habe, um die Größe zu erhöhen. Also lassen Sie mich voran und gehen Sie einfach aktualisieren diese, die Null war. Und statt jetzt, ich werde in den Wert eins gesetzt. Und jetzt nehme ich eine andere schieben auf den Stapel, wie 51. Nun, ich habe noch einen machen Änderung, die bis zu einer Größe zwei ist. Und dann nehme ich noch einen Push Nummer auf den Stapel, wie 61, jetzt brauche ich, um die Größe zu aktualisieren, noch eine Zeit, und erhalten Sie den Wert 3 als Größe. Und jetzt nehme ich als Pop. Jetzt öffnet, durch Konvention, nicht ein Argument. Mit einem Stapel, der ganze Punkt des Fachs Metapher ist, dass Sie keinen Ermessensspielraum zu holen, dass Tablett, alles, was Sie tun können, Pop ist das oberste eine aus der Stapel, nur weil. Das ist, was diese Datenstruktur tut. 

So nach dieser Logik, wenn ich sagen, pop, was kommt aus? So 61. Also, was ist wirklich der Computer gehen, um in Erinnerung zu tun? Was bedeutet mein Code zu tun haben? Was würden Sie vorschlagen, wir auf dem Bildschirm zu ändern? Was sollte sich ändern? Es tut uns leid? So bekommen wir von 61 zu befreien. So kann ich auf jeden Fall tun. Und ich kann von 61 loszuwerden. Und dann, was andere Veränderung muss geschehen? Größe hat wohl wieder auf zwei zu gehen. Und so ist das in Ordnung. Aber warten Sie eine Minute, Größe vor einem Augenblick war drei. Lassen Sie uns einfach eine schnelle Plausibilitätsprüfung zu tun. Wie haben wir uns, dass wir wollte von 61 loswerden? Weil wir knallen. Und so habe ich diese zweite Eigenschaft Größe. 

Warten Sie eine Minute, ich bin Denken zurück zu Woche zwei wenn wir kamen ins Gespräch über Arrays, wo dies Lage Null, dies war ein Ort, war dies Lage Zwei, ist dies Lage drei, vier, es sieht aus wie die Beziehung zwischen Größe und das Element, das möchte ich entfernen aus dem Feld erscheint nur, was? Größe minus eins. Und so das ist, wie als Menschen wir wissen, 61 an erster Stelle. Wie geht der Computer geht zu wissen? Wenn Sie Ihren Code, wo Sie wahrscheinlich wollen Größe minus eins zu tun, so drei minus eins ist zwei, und das bedeutet, wollen wir von 61 loszuwerden. Und dann werden wir in der Tat zu aktualisieren können die Größe, so dass die Größe jetzt geht von drei auf zwei. Und nur um pedantisch zu sein, werde ich vorzuschlagen, dass ich fertig bin, nicht wahr? Sie schlug intuitiv korrekt sollte ich von 61 loszuwerden. Aber haben nicht die Art von I Art bekommen von 61 zu befreien? Ich habe effektiv vergessen dass es tatsächlich gibt. Und denken Sie zurück an PSET4, wenn Sie gelesen haben, Der Artikel über Forensik, die PDF- dass wir euch zu lesen, oder Sie wird diese Woche für PSET4 lesen. Erinnern, dass dies tatsächlich relevant für die ganze Idee der Computer-Forensik. Was ein Computer in der Regel tut, ist, es einfach vergisst, wo etwas ist, aber es funktioniert nicht in zu gehen und wie versuchen, es auskratzen oder Override- jene Bits mit Nullen und Einsen oder eine andere Zufallsmuster es sei denn, Sie selbst tun, so bewusst. So Ihre Intuition war Okay, lassen Sie von 61 zu befreien. Aber in Wirklichkeit haben wir nicht zu stören. Wir müssen nur vergessen, dass es ist da durch Veränderung unserer Größe. 

Jetzt gibt es ein Problem mit diesem Stack. Wenn ich weiter pushen Dinge auf den Stapel, was ist offensichtlich passieren in nur ein paar Augenblicke Zeit? Wir werden aus dem Raum laufen. Und was machen wir jetzt? Wir Art verschraubt. Diese Implementierung nicht lassen uns die Größe des Array, denn mit diese Syntax, wenn Sie denken Sie zurück an der Woche zwei, wenn Sie erklärt haben die Größe eines Arrays, haben wir nicht einen Mechanismus noch nicht, wo zu sehen Sie können die Größe des Arrays ändern. Und in der Tat C nicht über diese Funktion. Wenn Sie sagen, gib mir fünf Nths, nennen sie Zahlen, das ist alles, du gehst, es zu bekommen sind. So tun wir jetzt ab Montag, haben die Fähigkeit, eine Lösung zu äußern aber, müssen wir nur noch zwicken die Definition unserer Stapel einige hartcodierte Array nicht sein, aber nur, um eine Adresse zu speichern. 

Nun, warum ist das? Jetzt müssen wir nur komfortabel mit zu sein die Tatsache, dass, wenn mein Programm läuft, Ich bin vermutlich werde haben, um die menschliche stellen, wie viele Zahlen Sie speichern möchten? So der Eingang von irgendwoher kommen. Aber sobald ich weiß, dass Zahl ist, dann kann ich nur verwenden, welche Funktion zu geben, mich ein Teil des Speichers? Ich kann malloc verwenden. Und ich kann sagen, dass eine beliebige Anzahl von bytes Ich möchte wieder für diese Nths. Und alles, was ich in den Nummern speichern variable hier innerhalb dieser Struktur sollten, was sein? Was tatsächlich in der geht Zahlen in diesem Szenario? Ja, ein Zeiger auf das erste Byte dieser Teil des Speichers, oder genauer gesagt, die Adresse, der erste dieser Bytes. Egal, ob es eines Byte oder eine Milliarde Bytes, Ich muss nur um die erste zu kümmern. Denn was malloc Garantien und mein Betriebssystem garantiert, ist, dass der Teil des Speichers I zu erhalten, wird es zusammenhängend sein. Es wird nicht zu Lücken aufweisen kann. Also, wenn ich für 50 gebeten Bytes oder 1000 Bytes, sie alle sein wird zurück zu zurück zu zurück. Und so lange ich mich erinnern, wie groß, wie viel fragte ich nach, alles, was ich wissen muss ist die erste Adresse. 

So, jetzt haben wir die Möglichkeit im Code. Wenn auch nur, es geht um uns zu nehmen mehr Zeit, dies zu schreiben up, wir könnten jetzt umzuschichten, dass der Speicher durch nur eine andere Adresse speichert es wenn wir wollen, eine größere oder sogar ein kleinerer Teil des Speichers. So, hier zu einem Kompromiss. Jetzt bekommen wir Dynamik. Wir haben noch contiguousness ich behaupten. Weil malloc wird uns ein zusammenhängender Teil des Speichers. Aber das wird ein Schmerz in sein der Hals für uns, der Programmierer, um tatsächlich Code oben. Es ist nur mehr Arbeit. Wir benötigen Code verwandt, was ich eben noch hämmern. Sehr machbar, aber es erhöht die Komplexität. Und so Entwicklungszeit, Programmierer Es ist noch eine weitere Ressource dass wir brauchen, um zu verbringen einige Zeit, um neue Funktionen zu erhalten. Und dann natürlich gibt es eine Warteschlange. Wir werden nicht in diese zu gelangen eine in vielen Details. Aber es ist im Geiste sehr ähnlich. Ich konnte eine Warteschlange zu implementieren, und ihre entsprechenden Operationen, Enqueue oder dequeue, wie hinzuzufügen oder zu entfernen, es ist nur ein schicker Art zu sagen, ist es, enqueue oder dequeue, wie folgt. Ich kann mir selbst eine struct hat, dass wieder ein Zahlen-Array, hat, dass wieder eine Größe, aber warum muss ich jetzt brauchen zu verfolgen, der vor einer Warteschlange zu halten? Ich brauchte nicht zu wissen, die vor meinem Stack. Nun, wenn ich wieder für ein queue-- lassen Sie uns nur schwer Code als mit wie fünf Zahlen hier möglicherweise. So dass dieser null, eins, zwei, drei, vier. Dies wird sein, rufenen Nummern erneut. Und dies wird genannt Größe sein. 

Warum ist es nicht ausreichend, nur Größe haben? Nun, lassen Sie schieben die gleichen Zahlen auf. So pushed-- ich eingereiht, oder geschoben. Jetzt werde ich Enqueue 50, und dann 51, und 61 und Punkt Punkt Punkt. Also das ist, Enqueue. Ich reiht 50, dann 51, dann 61. Und das sieht identisch zu einem Stapel so weit, außer ich tun müssen, um eine Änderung vorzunehmen. Ich brauche, um diese Größe zu aktualisieren, so dass ich gehen von null auf eins, zwei bis drei bekommen. Wie kann ich aus der Warteschlange entfernt? Was passiert mit dequeue? Wer sollte zuerst kommen aus dieser Liste ob es die Zeile im Apple Store? So 50. So ist es Art von komplizierter diesmal. Während im letzten Mal war es Super- leicht, einfach zu tun Größe minus eins, Ich zum Ende meiner Array effektiv erhalten wobei die Zahlen sind, entfernt es 61. Aber ich will nicht zu entfernen 61. Ich möchte 50 zu nehmen, der war es um 5:00 Uhr um sich für die neue iPhone oder Dingsbums. Und so, um von 50 loszuwerden, I können nicht einfach tun, nicht wahr? Ich kann streiche 50. Aber wir gesagt, dass wir nur haben nicht so anal zu sein wie zu kratzen oder die Daten zu verstecken. Wir können einfach vergessen, wo es ist. 

Aber wenn ich meine Größe jetzt zu ändern Zwei, ist dies ausreichend Informationen zu wissen, was los ist in meiner Warteschlange? Nicht wirklich. Wie meine Größe zwei, sondern Woher kommt die Warteschlange zu beginnen, vor allem, wenn ich noch die gleichen Nummern im Speicher. 50, 51, 61. Also muss ich daran erinnern, Jetzt, wo die Front ist. Und so wie ich vorgeschlagen up da wir gerade genannt haben werde Nth Front, deren Anfangs Wert gewesen sein sollte, was? Zero, nur der Anfang der Liste. Aber jetzt zusätzlich zum Dekrementieren die Größe, wir erhöhen die Front. Nun, hier ist ein anderes Problem. Also, wenn ich weiterzumachen. Angenommen, dies ist die Anzahl von wie 121, 124, und dann, verdammt noch mal, Ich bin aus dem Raum. Aber warten Sie eine Minute, ich bin mir nicht. So an diesem Punkt in der Geschichte, Angenommen, dass die Größe ein, zwei, drei, vier, so angenommen, daß die Größe ist vier, die Front ist eine, so 51 ist an der Vorderseite. Ich möchte eine andere Zahl hier zu setzen, aber, verdammt, ich bin aus dem Raum. Aber ich bin nicht wirklich, oder? Wo könnte ich einige setzen Mehrwert wie 171? Ja, könnte ich nur irgendwie gehen Sie zurück dort, nicht wahr? Und dann über die 50 oder einfach überschreiben ihn mit 171. Und wenn Sie sich fragen, warum unsere Zahlen wurden so zufällig, diese sind häufig Computer übernommen Wissenschaftskurse in Harvard, nachdem CS50. Aber das war eine gute Optimierung, denn jetzt bin ich nicht Platzverschwendung. Ich habe immer noch daran zu erinnern, wie groß das Ding ist total. Es ist fünf insgesamt. Weil ich nicht möchte Start überschreiben 51. So, jetzt bin ich immer noch der Platz, so dass das gleiche Problem wie zuvor. Aber Sie sehen, wie jetzt in Ihrem Code, werden Sie wahrscheinlich noch ein wenig mehr zu schreiben Komplexität, um dies zuzulassen. Und in der Tat, was für Betreiber in C wahrscheinlich lässt Sie magisch tun dies die Rund? Ja der Modulo-Operator, das Prozentzeichen. Also, was ist irgendwie cool zu einer Warteschlange, obwohl wir zeichnen Arrays zu halten da diese wie gerade Linien, wenn Sie Art darüber nachzudenken, wie geschwungene rund wie ein Kreis, dann nur intuitiv es irgendwie funktioniert mental Ich denke, ein wenig sauberer. Sie würden immer noch zu implementieren dass mentales Modell in Code. Also nicht so schwer, letztlich zu implementieren, aber wir verlieren die size-- vielmehr die Fähigkeit, Größe ändern, wenn wir dies tun. 

Wir müssen uns des Arrays zu entfernen, die wir ersetzen Sie es mit einem einzigen Zeiger, und dann irgendwo in meinem Code ich habe a nennen, was funktioniert, um tatsächlich zu erstellen das Array angerufenen Nummern? Malloc, oder eine ähnliche Funktion, genau. Irgendwelche Fragen zu Stapeln oder Warteschlangen. Ja? Gute Frage. Was für Modulo würden Sie hier verwenden. So im Allgemeinen, bei der Verwendung von mod, können Sie es tun würde mit der Größe des gesamte Datenstruktur. So etwas wie fünf oder Kapazität, wenn konstant ist, ist wahrscheinlich beteiligt. Aber nur tun, Modulo fünf wahrscheinlich nicht ausreichend ist, weil wir wissen müssen, tun wir Wrap-around hier oder hier oder hier. So sind Sie sicher auch gehen zu beteiligen zu wollen, die Größe der Sache oder die vordere variable als auch. So ist es nur diese relativ einfachen arithmetischen Ausdruck, aber Modulo würde der Hauptbestandteil ist. 

So kurzen Film, wenn man so will. Eine Animation, die einige Leute an einer anderen Hochschule zusammen, dass wir für diese Diskussion angepasst. Es geht um das Lernen der Jack Fakten über Warteschlangen und Statistiken. 

FILM: Es war einmal, gab es einen Mann namens Jack. Wenn es um Freunde kamen, Jack hatte nicht ein Talent. Also ging Jack zu sprechen, die beliebteste Kerl wusste er. Er ging zu Lou und fragte: Was soll ich tun? Lou sah, dass sein Freund war wirklich verzweifelt. Nun begann er, nur schauen, wie Sie angezogen sind. Glauben Sie nicht keine Kleidung haben mit einem anderen Blick? Ja, sagte Jack. Ich mache es auf jeden Fall. Komm in mein Haus und Ich werde sie Ihnen zeigen. So gingen sie aus, um Jacks. Und Jack zeigte Lou die Box wo er behielt alle seine Hemden, und seine Hose, und seine Socken. Lou sagte: Ich sehe, Sie haben Ihre Kleidung in einem Haufen. Warum gehst du nicht einige tragen andere einmal in eine Weile? 

Jack sagte: Nun, als ich Kleidung und Socken zu entfernen, Ich wasche sie und legte sie weg in die Box. Dann kommt die nächste Morgen, und bis ich hüpfen. Ich gehe in die Box und erhalten meine Kleider aus der Spitze. Lou erkannte schnell, das Problem mit Jack. Er hielt Kleidung, CDs, und Bücher in den Stapel. Als er zum Erreichen etwas zu lesen oder zu tragen, er würde die obere Buch oder Unterwäsche zu wählen. Dann, als er fertig war, er würde es gleich wieder setzen. Zurück es gehen würde, oben auf dem Stapel. Ich weiß, dass die Lösung, sagte eine triumphale Laute. Sie brauchen, um zu lernen, starten Sie mit einer Warteschlange. Lou nahm Jacks Kleidung und hängte sie in den Schrank. Und wenn er geleert hatte die Box, er hat nur warf sie. 

Dann sagte er, jetzt Jack, am Ende des der Tag, setzen Sie Ihre Kleidung auf der linken Seite wenn man sie entfernt. Dann morgen früh, wenn Sie finden Sie in der Sonne, erhalten Sie Ihre Kleidung auf der rechten Seite, aus dem Ende der Leitung. Siehst du denn nicht? , sagte Lou. Es wird so schön sein. Hier finden Sie alles einmal zu tragen bevor Sie etwas zweimal zu tragen. Und mit allem, was in Warteschlangen in seinem Schrank und Regal, Jack begann zu fühlen, sehr von sich überzeugt. Alle durch Lou und seine wunderbare Warteschlange. Sprecher 1: In Ordnung, es ist entzückend. Also, was hat sich wirklich auf unter der Haube jetzt? Dass wir Hinweise, dass wir malloc, dass wir die Fähigkeit haben, zu erstellen Stücke von Speicher für uns selbst dynamisch. Das ist also ein Bild, das wir erblickte nur den anderen Tag. Wir haben nicht wirklich zu wohnen darauf aber dieses Bild hat schon unter die Haube seit Wochen. Und so stellt dies nur ein Rechteck, die wir gezogen haben, Arbeitsspeicher Ihres Computers. Und vielleicht Ihren Computer oder CS50 ID, verfügt über ein Gigabyte Arbeitsspeicher oder RAM oder zwei oder vier Gigabyte. Es spielt eigentlich keine Rolle. Ihr Betriebssystem Windows oder Mac OS oder Linux, Wesentlichen ermöglicht Ihrem Programm zu denken, dass sie Zugang hat auf die Gesamtheit Arbeitsspeicher Ihres Computers, auch wenn Sie vielleicht laufen mehrere Programme auf einmal. So in der Realität bedeutet das nicht wirklich funktionieren. Aber es ist eine Art einer Illusion um alle Ihre Programme gegeben. Also, wenn Sie hatte zwei GB RAM, dies ist, wie der Computer könnte daran denken. 

Jetzt zufällig einer von ihnen Dinge, wobei eine dieser Speichersegmente, heißt eines Stapels. Und in der Tat jedes Mal, bisher in das Schreiben von Code dass Sie angerufen haben ein Funktion, zum Beispiel Haupt. Daran erinnern, dass jedes Mal, wenn ich Speicher gezogen Computers, Ich habe immer irgendwie zu ziehen die Hälfte eines Rechtecks ​​hier und nicht die Mühe sprechen über das, was oben. Denn als Haupt heißt, behaupten I dass Sie diese Splitter der Erinnerung erhalten das geht hier unten. Und wenn Haupt genannt Funktion wie Swaps, gut Swap goes here. Und es stellt sich heraus, das ist, wo sie landen. Auf einem so genannten Stack Innere des Arbeitsspeichers Ihres Computers. Nun am Ende des Tages, dies ist nur Adressen. Es ist wie das Byte Null ist, Byte eine, Byte 2 Milliarden. Aber wenn man darüber nachdenkt, wie diese rechteckiges Objekt, alles, was wir tun jeden Zeit rufen wir eine Funktion Schichtung eine neue Scheibe des Speichers. Wir geben diese Funktion eine Scheibe von seinen eigenen Speicher, mit zu arbeiten. 

Und jetzt daran erinnern, dass dies wichtig ist. Denn wenn wir nicht haben so etwas wie Swap- und zwei lokale Variablen wie A und B und wir die Werte von einem und zwei ändern um zwei und eins, Rückruf dass, wenn Swap zurückkehrt, es ist, als ob dieser Scheibe der Speicher ist einfach weg. In Wirklichkeit ist es immer noch es forensisch. Und noch etwas ist immer noch wirklich da. Aber konzeptionell, es ist so obwohl es komplett verschwunden. Und so Haupt weiß nicht, irgendwelche der Arbeit das war in diesem Swap-Funktion durchgeführt, es sei denn, es ist eigentlich in denen übergeben Argumente Zeiger oder durch Bezugnahme. Nun, die grundlegende Lösung zu diesem Problem mit Swap- ist vorbei Dinge nach Adresse. Aber es zeigt sich auch, was ist nun schon über diesem Teil des Rechtecks ​​während dieser ganzen Zeit ist doch gibt es mehr Speicher oben. Und wenn Sie dynamisch Speicher zuweisen, ob es innerhalb der GetString, die haben wir für Sie tun in der CS50 wurde Bibliothek, oder wenn Sie Kerle anrufen malloc und fragen das Betriebssystem für ein Stück aus Speicher, ist es nicht von dem Stapel zu kommen. Es kommt aus einem anderen Ort im Arbeitsspeicher Ihres Computers dass heißt die Heap. Und das ist nicht anders. Es ist das gleiche RAM. Es ist das gleiche Speicher. Es ist nur der RAM, die ist es anstelle von hier unten. 

Und was bedeutet das? Nun, wenn Ihr Computer über eine endliche Menge an Arbeitsspeicher und der Stapel wächst, so zu sprechen, und der Haufen nach dieser Pfeil, wächst nach unten. Mit anderen Worten, jedes Zeit anruft malloc, melden wir Sie ein Stück gegeben Arbeitsspeicher von oben, dann vielleicht ein wenig niedriger, dann ein wenig niedriger, jedes Mal wenn Sie malloc nennen, der Haufen ist es Nutzung, ist Art von wachsenden, wachsen näher und näher an was? Der Stapel. So scheint dies wie eine gute Idee? Ich meine, wo es ist nicht wirklich klar, was Sie sonst noch, wenn nur Sie tun können haben eine begrenzte Menge an Speicher. Aber das ist sicherlich schlecht. Diese beiden Pfeile sind auf einer Crashkurs für einander. 

Und es stellt sich heraus, dass die schlechte Kerl, Leute, sind besonders gut mit der Programmierung, und zu versuchen, in Computer zu hacken, kann diese Realität zu nutzen. In der Tat, betrachten ein kleiner Ausschnitt. Das ist also ein Beispiel können Sie lesen, etwa im Detail auf Wikipedia. Registrieren Sie an der Stelle, Artikel, wenn neugierig. Aber es gibt ein Angriff in der Regel wie Pufferüberlauf bekannt, dass hat, solange Menschen bestanden haben die Fähigkeit zur Manipulation hatten Speicher Computers, insbesondere in C. Das ist also ein sehr willkürlich Programm, aber lassen Sie las es von unten nach oben. Haupt in argC char Sterne argv. So ist es ein Programm, das dauert Befehlszeilenargumente. Und alle Haupt hat offenbar Anruf eine Funktion, nennen es F der Einfachheit halber. Und es geht in was? Argv von einem. So ist es in F verläuft unabhängig das Wort ist, dass der Benutzer eingetippt an der Eingabeaufforderung, nachdem die Programmnamen überhaupt. So viel wie Cäsar oder Vigenere, die Sie erinnern sich vielleicht tun mit argv. 

Also, was ist F? F erfolgt in einem String als einziges Argument, Alias ​​ein char Sterne, gleiche Sache, als String zurück. Und es ist willkürlich genannt bar in diesem Beispiel. Und dann char c 12, nur in juristischer Hinsicht, was ist char c Konsole 12 für uns tun? Was ist es? Zuweisen von Speicher, und zwar 12 Bytes für 12 Zeichen. Genau. Und dann die letzte Zeile, umrühren und Kopie, haben Sie wahrscheinlich nicht gesehen. Dies ist ein String Kopie Funktion, deren Zweck im Leben ist vor dem zweiten Argument kopieren in seine erste Argument, aber nur bis zu einem bestimmte Anzahl von Bytes. Also das dritte Argument, sagt, wie viele Bytes sollten Sie kopieren? Die Länge der Bar, was auch immer der Benutzer eingetippt. Und der Inhalt der Bar, diesen String sind in den Speicher kopiert zeigte auf bei C. 

So scheint Art von dumm, und es ist. Es ist ein konstruiertes Beispiel, aber es Vertreters einer Klasse von Angriffsvektoren, ein Weg, der Angriff auf ein Programm. Alles ist schön und gut, wenn der Benutzer Typen in einem Wort, das 11 Zeichen ist oder weniger, plus der Rückstrich Null. Was ist, wenn der Benutzer in mehr als 11 oder 12 oder 20 oder 50 Zeichen? Was ist das Programm vor? Potenziell seg Fehler. Es geht blindlings alles in bar up kopieren zu seiner Länge, das ist buchstäblich alles in bar, in die Adress zeigte auf C. Aber C nur präventiv als 12 Byte angegeben. Aber es gibt keine zusätzliche Überprüfung. Es gibt keinen, wenn die Bedingungen. Es gibt keine Fehlerüberprüfung hier. 

Und was ist dieses Programm zu tun ist einfach blind Kopieren einer Sache zur anderen. Und so, wenn wir ziehen diese als Bild, hier ist nur ein Splitter des Speicherplatzes. So bemerken an der Unterseite, die wir haben die lokalen Variablen bar. So dass Zeiger, die gehen, um store-- vielmehr, dass lokale Argument, das ist gehen, um die Zeichenfolge bar zu speichern. Und dann einfach feststellen, darüber in einem Stapel, denn jedes Mal, wenn Sie fragen, für Speicher auf dem Stapel, es geht ein wenig darüber bildhaft, Beachten Sie, dass wir 12 Bytes dort ankamen. Die obere linke ist C Halterung Null und die untere rechte ist C Halterung 11. Das ist nur, wie die Computer werde es auslegen. Also einfach intuitiv, wenn bar mehr als 12 Zeichen insgesamt, einschließlich der Backslash Null, wo ist der 12 oder der C Konsole 12 hingehen? Oder besser gesagt, wo ist der 12. Zeichen oder der 13. Charakter, der hundertste Charakter gehen auf dem Bild am Ende? Über oder unter? 

Richtig, denn obwohl der Stapel selbst wächst nach oben, wenn Sie Sachen in gesteckt haben es, ist es aus konstruktiven Gründen, setzt den Speicher von oben nach unten. Also, wenn Sie mehr als 12 Byte haben, Sie gehen zu beginnen, bar zu überschreiben. Nun, das ist ein Problem, aber es ist nicht wirklich eine große Sache. Aber es ist eine große Sache, weil es mehr Sachen passiert im Speicher. Also hier ist, wie wir legte hallo, klar zu sein. Wenn ich tippte hallo an der Eingabeaufforderung. H-E-L-L-O umgekehrten Schrägstrich Null, endet in diese 12 Bytes, und wir sind super sicher. Alles ist gut. Aber wenn ich etwas mehr potentiell es werde in bar Raum kriechen. Aber schlimmer noch, es stellt sich out all dieser Zeit, obwohl wir nie darüber gesprochen es wird der Stapel für die anderen Sachen verwendet wird. Es ist nicht nur lokale Variablen. 

C ist eine sehr geringe Sprachniveau. Und es Art von heimlich verwendet den Stack auch sich daran zu erinnern, wenn ein Funktion aufgerufen wird, welche die Adresse des vorherigen Funktion, so dass es zurück zu dieser Funktion springen. Als Haupt Anrufen zu wechseln, unter die Dinge, die auf dem Stapel abgelegt sind nicht nur vertauscht lokalen Variablen, oder ihre Argumente, auch heimlich geschoben auf dem Stapel als vertreten durch die rot scheibe hier, ist die Adresse des Hauptkörper im Arbeitsspeicher Ihres Computers, so dass beim Austausch wird durchgeführt, wobei das Computer weiß, ich muss zurück zur Haupt gehen und schliessen Sie die Hauptfunktion ausführt. Also das ist jetzt gefährlich, denn wenn der Benutzer in gut mehr als hallo, derart, dass die Eingabe des Benutzers clobbers oder überschreibt, dass roten Bereich, logisch, wenn der Computer gerade dabei, blind übernehmen dass die Bytes in dieser rot scheibe sind die Adresse, auf die sie zurückkehren sollen, was ist, wenn der Gegner ist intelligent genug, oder Glück, eine Folge von Bytes gesetzt gibt, die wie eine Adresse aussieht, aber es ist die Adresse des Codes dass er oder sie den Computer will anstelle von Haupt ausführen? 

Mit anderen Worten, wenn, was die Benutzer an der Eingabeaufforderung eingeben, ist nicht nur etwas harmlos wie hallo, aber es ist eigentlich Code, der äquivalent ist Um alle Dateien des Nutzers löschen? Oder mailen Sie ihr Passwort zu mir? Oder starten Sie die Protokollierung ihrer Tastatureingaben, oder? Es gibt einen Weg, lasst uns vor, heute, dass sie nicht nur geben könnte hallo Welt oder ihren Namen, sie konnten im wesentlichen Pass in Code, Nullen und Lieben, dass der Computer Fehler sowohl für Code und einer Adresse. So wenngleich etwas abstrakt, wenn der Benutzertypen in genug kontradiktorischen Code dass wir hier verallgemeinern A. Ein Angriff ist oder Gegner. Also nur schlechte Sachen. Wir wissen nicht über die Pflege Zahlen oder die Nullen oder Einsen heute, so dass Sie am Ende überschreibt diese roten Bereich, feststellen, dass die Folge von Bytes. O 835 C null acht Null. Und jetzt als Wikipedia-Artikel hier hat vorgeschlagen, wenn Sie jetzt tatsächlich beginnen Markierung der Bytes in Ihren Computer Gedächtnis, was der Wikipedia-Artikel ist vorschlagen, ist, dass, was ist, wenn die Adresse dieser oberen linken Byte ist 80 C 0 3508. 

In anderen Worten, wenn der Bösewicht ist intelligent genug, mit seinen oder ihren Code um tatsächlich legte eine Reihe hier, dass entspricht der Adresse des Code er oder sie injiziert in den Computer, die Sie können Sie den Computer Trick in etwas zu tun. Entfernen von Dateien, E-Mails Dinge, schnüffeln Ihren Traffic, buchstäblich alles sein könnte in den Computer eingespritzt. Und so ein Pufferüberlauf Angriff in seinem Kern ist nur ein dumm, dumm wiegendes eines Arrays, nicht über seine Grenzen überprüft. Und das ist, was ist super gefährlich und gleichzeitig super leistungsfähiges in C ist, dass wir haben in der Tat Zugang zu jedem Ort in der Erinnerung. Es liegt an uns, die Programmierer, die das Original-Code schreiben um die verflixte Länge jeder überprüfen Arrays, die wir manipulieren. So klar zu sein, was ist die Lösung? Wenn wir zurückrollen, um diese Code, sollte ich nicht einfach ändern Sie die Länge der Stange, was sollte ich sonst werden überprüft? Was muss ich tun, um diesen Angriff zu verhindern vollständig? Ich will nicht einfach blind sagen dass Sie so viele Bytes kopieren so ist die Länge der Stange. Ich möchte sagen, zu kopieren, wie viele Bytes, wie es in bar bis der zugewiesene Speicher oder 12 maximal. Also brauche ich eine Art, wenn die Bedingung das tut überprüfen Sie die Länge der Stange, aber wenn es 12, wir haben nur schwer Code überschreitet 12 als der größtmöglichen Abstand. Ansonsten die sogenannte Puffer Überlauf-Angriff kann passieren. An der Unterseite des auf den Folien, wenn Sie neugierig, mehr zu lesen sind ist das eigentliche Original-Artikel wenn Sie möchten, um einen Blick zu nehmen. 

Aber jetzt, unter den Preisen Hier bezahlt war Ineffizienzen. Das war also eine schnelle niedrigen Niveau Blick auf, was Probleme können nun ergeben, dass wir Zugriff auf Speicher Computers. Aber ein anderes Problem, das wir bereits am Montag, stolperte war nur die Ineffizienz einer verketteten Liste. Wir sind wieder in linearer Zeit. Wir müssen nicht mehr einen zusammenhängenden Array. Wir haben nicht mit wahlfreiem Zugriff. Wir können nicht mit eckigen Klammern. Wir haben buchstäblich in einer while-Schleife verwenden wie die, die ich vorhin geschrieben habe. Aber am Montag, behauptete wir, dass wir kriechen zurück in das Reich der Effizienz etwas, das es zu erreichen logarithmische vielleicht, oder am besten noch, vielleicht sogar etwas, das ist sogenannte konstante Zeit. Also, wie können wir das tun, indem Sie diese neue Werkzeuge, diese Adressen, diese Zeiger, und Gewinde Dinge unserer eigenen? Nun, nehme an, dass Hier handelt es sich um ein Bündel von Zahlen, die wir in einem Geschäft wollen Datenstruktur und Such effizient. Wir können absolut zu Woche zurückspulen zwei, werfen diese in einem Array, und suchen Sie sie mit binäre Suche. Teile und herrsche. Und in der Tat Sie geschrieben binäre Suche in PSET3, wo Sie die Fund-Programm implementiert. Aber wissen Sie was. Es ist eine Art mehr cleverer Weg, dies zu tun. Es ist ein wenig mehr anspruchsvoll und es vielleicht ermöglicht es uns, zu sehen, warum binären Suche so viel schneller ist. Lassen Sie uns zunächst vorstellen der Begriff eines Baumes. Welche, obwohl in Realität Bäumen Art wachsen wie dieser, in der Welt der Computer- Wissenschaft sie Art von unten wachsen wie ein Stammbaum, wo Sie Ihre Großeltern oder Urgroßeltern oder was auch an der Spitze, dem Patriarchen und die Matriarchin der Familie, nur ein so genannte Wurzel, Knoten, unten die ihre Kinder sind, unterhalb dessen sind ihre Kinder oder ihre Nachkommen im Allgemeinen. Und wer hängen aus der Boden der Familie Baum, abgesehen davon, das Jüngste in der Familie, können auch einfach generisch sein rief die Blätter des Baumes. 

Also das ist nur ein Haufen von Wörtern und Definitionen für so etwas wie einen Baum im Computer Wissenschaft, ähnlich wie ein Stammbaum. Aber es gibt noch schicker Inkarnationen von Bäumen, von denen eine heißt ein binärer Suchbaum. Und Sie können Art von tease auseinander, was dieses Ding funktioniert. Nun, es ist binär in welchem ​​Sinne? Woher kommt das binäre aus hierher gekommen? Es tut uns leid? Es ist nicht so sehr ein entweder oder. Es ist mehr, dass jeder der Knoten hat keine mehr als zwei Kinder, wie wir hier sehen. Im Allgemeinen ist eine tree-- und Ihre Eltern und Großeltern können so viele Kinder zu haben oder grandkids, als sie eigentlich wollen, und so zum Beispiel gibt uns drei haben Kinder ab diesem rechten Knoten, aber in einer Binärbaum besitzt eine Knoten null, eine oder zwei Kinder maximal. Und das ist ein schönes Anwesen, denn wenn es von beiden mit einer bedeckt, werden wir in der Lage zu sein, noch ein wenig Protokollbasis zwei Aktion geht hier schließlich. Also müssen wir etwas logarithmisch. Aber mehr dazu in einem Moment. Suchbaum bedeutet, dass die Zahlen angeordnet, dass die linken Kindes Wert größer als die Wurzel. Und seine rechte Kind größer als die Wurzel. Mit anderen Worten, wenn Sie eines der nehmen Knoten, die Kreise in diesem Bild, und schaut auf seiner linken Kind und seine rechte Kind, die erste sollte kleiner sein, der zweite sollte größer sein. So Plausibilitätsprüfung 55. Es verließ Kind ist 33. Es ist weniger als. 55, sein Recht Kind ist 77. Es ist größer als. Und das ist eine rekursive Definition. Wir konnten jeden einer von denen zu prüfen Knoten und das gleiche Muster halten würde. 

Also, was ist schön, in ein binären Suchbaum ist dass man, können wir es umsetzen mit einer Struktur, wie diese. Und auch wenn wir werfen viele Strukturen in Ihrem, sie sind etwas intuitive nun hoffentlich. Die Syntax ist immer noch geheimnisvollen sicher, aber der Inhalt eines Knotens in dieser context-- und wir halten Verwendung der Wortknoten, ob es sich um ein Rechteck auf dem Bildschirm oder einem Kreis, es ist nur einige generischen Container, in diesem Fall aus einem Baum, wie einer wir sahen, wir brauchen eine ganze Zahl in jedem der Knoten und dann muss ich zwei Zeiger Zeige auf der linken und der rechten Kind Kind, jeweils. Also das ist, wie wir umzusetzen, dass in einer Struktur. Und wie könnte ich zu implementieren es im Code? Nun, lassen Sie uns einen kurzen Blick auf dieses kleine Beispiel. Es ist nicht funktionsfähig, aber ich habe kopiert und eingefügt werden, dass die Struktur. Und wenn meine Funktion für ein binäres Suchbaum Such genannt, und dies nimmt zwei Argumente, eine ganze Zahl N und einen Zeiger zu einem Knoten, so dass ein Zeiger auf dem Baum oder einen Zeiger zu der Wurzel eines Baums, Wie kann ich über die Suche nach N hin? Nun, zunächst einmal, weil ich Umgang mit Zeigern, Ich werde eine Plausibilitätsprüfung zu tun. Wenn tree ist gleich ist gleich null, ist N In diesem Stammbaum oder nicht in diesem Stammbaum? Es kann nicht sein, oder? Wenn ich mich Vergangenheit null, dort nichts zu finden. Ich könnte auch einfach blind sagen return false. Wenn Sie mir nichts zu geben, ich kann sicher nicht finden eine beliebige Anzahl N. Was anderes könnte ich Jetzt prüfen? Ich werde auch sonst, wenn N sagen weniger als was auch immer an der Baumknoten dass ich N-Wert übergeben worden. Mit anderen Worten, wenn die Anzahl ich sucht, N, kleiner ist als der Knoten dass ich freue mich auf. Und der Knoten Ich suche bei nennt Baum, und daran erinnern, aus dem vorherigen Beispiel zu dem Wert in einem Zeiger zu erhalten, Ich benutze die Pfeilnotation. Also, wenn N kleiner als Baum Pfeil N, ich will konzeptionell links zu gehen. Wie kann ich express Benutzer überlassen? Um es klar, ob dies das Bild in Frage, und ich habe bestanden, dass oberste arrow das ist nach unten zeigt. Das ist mein Baum-Zeiger. Ich zeigte auf die Wurzel des Baumes. Und ich freue mich sagen wir, für die Zahl 44, willkürlich. 44 kleiner oder mehr als 55 offensichtlich? So ist es weniger als. Und so, wenn die Bedingung zutrifft. So konzeptionell, was will ich, um Suche starten, wenn ich mich für 44? Ja? 

Genau, ich will suchen Sie die linke Kind, oder der linke Unterbaum des Bildes. Und in der Tat, lassen Sie mich durch Das Bild hier unten nur für einen Augenblick, da Ich kann nicht kratzen this out. Wenn ich hier beginnen bei 55, und Ich weiß, dass der Wert 44 Ich suche ist es, der linke, es ist eine Art der wie Reißen Sie das Telefonbuch in die Hälfte oder Reißen Sie den Baum in der Mitte. Ich habe nicht mehr zu kümmern diese ganze Hälfte des Baumes. Und doch neugierig im Hinblick auf die Struktur, dieses Ding hier, dass beginnt bei 33, dass sich ist ein binärer Suchbaum. Ich sagte, das Wort rekursive vor, weil tatsächlich ist eine Datenstruktur, per Definition ist rekursiv. Vielleicht haben Sie einen Baum, der dies ist haben groß, aber jeder von seinen Kindern stellt einen Baum nur ein wenig kleiner. Statt wobei Opa oder Großmutter, jetzt ist es nur mom oder-- Ich kann nicht sagen-- nicht mom oder Papa, das wäre seltsam. Statt die beiden Kinder gibt würde wie Bruder und Geschwister zu sein. Eine neue Generation von der Familie Baum. Aber strukturell, es ist die gleiche Idee. Und es stellt sich heraus, Ich habe eine Funktion mit dem ich eine binäre Suche Suche Baum. Es wird Suche aufgerufen. Ich suche für N im Baum Pfeil links sonst wenn N größer ist als der Wert, dass ich mich derzeit auf. 55 in der Geschichte vor einem Augenblick. Ich habe eine Funktion mit dem Namen Such, ich kann nur geben N dieses und rekursiv suchen die Sub-Baum und nur Rück was auch immer die Antwort. Else Ich habe einige abschließende Basisfall hier. 

Was ist der letzte Fall ist? Baum ist entweder Null. Der Wert ich entweder suche, ist geringer als oder größer als derjenige oder gleich ist. Und ich konnte gleich sagen, gleich, aber logisch ist es entspricht einfach nur sagen andere hier. So wahr ist, wie ich etwas zu finden. Hoffentlich ist dies ein noch mehr überzeugendes Beispiel als der dumme Sigma-Funktion wir haben ein paar Vorträge zurück, wo es war so einfach, um eine Schleife zu verwenden zu zählen bis alle Zahlen von eins N. Hier mit einer Datenstruktur daß selbst rekursiv definiert ist und rekursiv gezogen, jetzt sind wir haben die Fähigkeit, uns auszudrücken im Code, die selbst rekursiv. Das ist also die exakt gleichen Code hier. 

Also, was andere Probleme können wir lösen? So ein schneller Schritt davon entfernt Bäume für einen Moment. Hier ist, sagen wir, die deutsche Flagge. Und es gibt eindeutig ein Muster dieser Flagge. Und es gibt viele Flaggen der Welt, sind so einfach wie dies in Bezug auf der Farben und Muster. Aber nehmen wir an, dass dies als eine gespeicherte GIF- oder JPEG-oder Bitmap oder ein Ping, beliebige grafische Dateiformat , mit denen Sie vertraut sind, einige davon sind wir spielt mit in PSET4. Dies scheint nicht sinnvoll zu speichern schwarzes Pixel, schwarzes Pixel, schwarzes Pixel, Punkt, Punkt, Punkt, eine ganze Reihe von schwarzer Pixel für das erste Abtastlinie oder Zeile, dann eine ganze Reihe von gleich sind, dann eine ganze Reihe derselben, und dann ein ganze Reihe von roten Pixel, roten Pixel, roten Pixel, dann eine ganze Bündel gelbe Pixel, gelb, oder? 

Es gibt eine solche Ineffizienz hier. Wie würden Sie intuitiv komprimieren die deutsche Flagge wenn die Umsetzung als Datei? Wie, was Informationen können wir nicht stört die Speicherung auf der Festplatte, um zu unserem Dateigröße aus, wie zu verringern ein Megabyte bis ein Kilobyte, etwas, kleiner? Worin liegt die Redundanz hier klar zu sein? Was könnten Sie tun? Ja? Genau. Warum nicht statt erinnern die Farbe eines jeden Pixels darn genau wie Sie in PSET4 tust mit der Bitmap-Datei-Format, warum du nicht einfach darstellen, die ganz linken Spalte von Pixeln, zum Beispiel ein Haufen von schwarzen Pixeln, ein Haufen roter und ein Bündel von Gelb, und dann einfach irgendwie kodieren die Idee der Wiederholen Sie diese 100-mal oder wiederholen Sie diesen 1.000 Mal? Wo 100 oder 1.000 ist nur eine ganze Zahl, so dass Sie kann mit nur einer einzigen Zahl weg anstelle von hunderten oder tausenden zusätzlicher Pixel. Und in der Tat, das ist, wie wir konnte die deutsche Flagge zu komprimieren. Und Was ist nun mit dem Französisch-Flag? Und ein bisschen eine Art von geistige Übung, die Flagge kann mehr auf der Festplatte komprimiert werden? Die deutsche Flagge oder Französisch Flagge, wenn wir diesen Ansatz? Die deutsche Flagge, weil es Weitere horizontale Redundanz. Und Design, viele grafische Datei Formate tatsächlich arbeiten, wie Scan-Linien horizontal. Sie konnten arbeiten vertikal, nur die Menschlichkeit Vor Jahren beschlossen, dass wir in der Regel der Dinge Reihe denken Zeile statt der Spalte für Spalte. So in der Tat, wenn Sie waren an der Datei zu suchen Größe einer Deutschlandflagge und Französisch Flagge, solange die Auflösung die gleichen sind, die gleiche Breite und Höhe, dieser Hier wird größer sein, weil Sie muss sich dreimal zu wiederholen. Sie müssen blau, wiederholen Sie angeben, sich selbst, weiß, wiederholen Sie sich, rot, wiederholen sich. Man kann nicht einfach alle gehen die Art und Weise nach rechts. Und nebenbei, um deaktivieren Sie die Komprimierung ist überall, wenn es sich um vier Bilder von einer video-- Sie vielleicht, dass ein Film erinnern oder Video ist in der Regel wie 29 oder 30 Bildern pro Sekunde. Es ist wie ein kleines Daumenkino, wo Sie nur Bild, Bild, Bild, Bild sehen Bild einfach super schnell, so dass es aussieht, die Schauspieler auf dem Bildschirm bewegen. Hier ist eine Hummel auf oben auf einem Blumenstrauß. Und wenn es vielleicht Art sein schwer, auf den ersten Blick zu sehen, das einzige, was sich in dieser Film ist die Biene. 

Was ist dumm zu speichern Video unkomprimiert? Es ist irgendwie eine Verschwendung, um Video zu speichern vier nahezu identische Bilder, unterscheiden sich nur insofern, als wo die Biene ist. Sie können wegwerfen meisten dieser Informationen und nur daran erinnern, zum Beispiel, der erste Rahmen und der letzte Rahmen, Keyframes Wenn Sie auch überhaupt das Wort hören, und nur in den Laden Mitte, wo die Biene. Und Sie müssen nicht zu haben, speichern alle der rosa, und die blaue und die grüne Werte auch. Das ist also nur sagen, dass Komprimierung ist überall. Es ist eine Technik, die wir verwenden oft oder nehmen Sie für diese Tage gewährt. 

Aber wie wollen Sie Text komprimieren? Was denken Sie über Komprimieren Text gehen? Nun, jedes der Zeichen in ASCII ist einem Byte oder acht Bits. Und das ist irgendwie dumm, nicht wahr? Da Sie wahrscheinlich Typ A und E und E und A und U eine Menge mehr als oft wie W oder Q oder Z, in Abhängigkeit von der Sprache, in der Sie sicherlich schreibst. Und warum sind wir mit acht Bits für jeden Buchstaben, einschließlich des mindestens beliebte Briefe, nicht wahr? Warum nicht mit weniger Bits für die super beliebt Briefe, wie E, das, was Sie sich vorstellen zuerst in Glücksrad, und verwenden Sie mehr Bits für die weniger populären Buchstaben? Warum? Weil wir gerade dabei, benutzen sie weniger häufig. 

Nun stellt sich heraus, dass es haben wurden Versuche unternommen, um dies zu tun. Und wenn Sie von Grad erinnern Schule oder Gymnasium, Morse-Code. Morse-Code hat dots und Striche, die sein können, entlang eines Drahtes übertragen Töne oder Signale von einer Art. Aber Morse-Code ist ein super sauber. Es ist Art von einem binären System in dass Sie Punkte oder Striche. Aber wenn Sie, zum Beispiel, zwei Punkte zu sehen. Oder wenn Sie an den Bediener zurückdenke die geht so piep, piep, piep, Signalton, der Kollision mit einem kleinen Trigger dass ein Signal überträgt, wenn Sie, der Empfänger erhält zwei Punkte, welche Botschaft haben Sie erhalten? Völlig willkürlich. 

ICH? ICH? Oder was about-- oder ich? Vielleicht war es nur zwei richtige E ist? Also gibt es dieses Problem von Decodierbarkeit mit Morse Code, wobei es sei denn, Person Senden Sie die Nachricht eigentlich Pausen, so dass Sie von zu sortieren sehen oder hören, die Lücken zwischen den Buchstaben, ist es nicht ausreichend, nur um schickt einen Strom von Nullen und Einsen, oder Punkten und Strichen, denn es gibt Mehrdeutigkeiten. E ist ein einzelner Punkt, wenn Sie also sehe zwei Punkte oder hören zwei Punkte, vielleicht ist es zwei E oder vielleicht ist es eine I. Also brauchen wir ein System, das eine ist wenig klüger als das. So ein Mann namens Huffman Jahre Vor kam mit genau dies. So dass wir gerade gehen um einen schnellen Blick zu nehmen an, wie Bäume sind relevant für diese. Angenommen, dass dies einige dumm Nachricht, die Sie senden wollen, nur A, B besteht, C D's und E ist, aber es gibt eine Menge von Redundanz hier. Es ist nicht dazu gedacht, Englisch. Es ist nicht verschlüsselt. Es ist nur eine dumme Nachricht mit viel Wiederholung. Also, wenn Sie wirklich zählen alle die A, B, C-Schema, D und E ist, ist hier, die Frequenz ist. 20% der Briefe A, 45% der Briefe sind E ist, und drei weitere Frequenzen. Wir zählten dort manuell und gerade habe die Mathematik. 

So stellt sich heraus, dass Huffman, vor einiger Zeit, erkannte, dass, Sie wissen, Was, wenn ich mit dem Bau ein Baum oder Wald von Bäumen, wenn man so will, wie folgt, was ich tun kann die folgende. Ich gehe, um einen Knoten zu jedem zu geben der Briefe, die mich interessiert, und ich werde speichern innerhalb dieses Knotens die Frequenzen als eine Gleitkommazahl Wert oder Sie es verwenden, könnte ein N, auch, aber wir werden nur mit einem Schwimmer hier. Und der Algorithmus, er vorgeschlagen ist, dass man nehmen diese Wald von einzelnen Knoten Bäume, so super kurzen Bäumen, und Sie können mit sie verbindenden starten neue Gruppen, neue Eltern, wenn man so will. Und Sie dies, indem Sie das tun, zwei kleinsten Frequenzen zu einem Zeitpunkt. Also nahm ich 10% und 10%. Ich erstelle einen neuen Knoten. Und ich fordere den neuen Knoten 20%. 

Welche zwei Knoten kombiniere ich als nächstes? Es ist ein wenig zweideutig. So gibt es einige Sonderfälle zu zu betrachten, sondern die Dinge recht zu halten, Ich werde auf 20% zu wählen - Ich jetzt ignorieren die Kinder. Ich werde auf 20% zu wählen und 15% und zeichnen Sie zwei neue Kanten. Und nun, welche zwei Knoten ich logisch zu kombinieren? Ignorieren alle Kinder, alle Enkel, nur an den Wurzeln zu suchen Jetzt. Welche zwei Knoten kann ich zusammen zu binden? Punkt zwei und 0,35. Also lassen Sie mich zu ziehen zwei neue Kanten. Und dann habe ich nur noch einer übrig. Also hier ist ein Baum. Und es ist ganz bewusst gezogen worden zu Art hübsch aussehen, aber feststellen, dass die Kanten ebenfalls null und eins bezeichnet. So dass alle von den linken Rändern Null beliebig, aber konsequent. Alle rechte Rand sind solche. 

Und was Hoffman vorgeschlagen, wenn Sie ein B darstellen wollen, anstatt für die Zahl 66 als einer ASCII, die acht gesamten Bits ist, Sie wissen, was, nur store das Muster null, null, null, Null, denn das ist der Weg von meinem Baum, Mr. Huffman-Baum, zur Blatt von der Wurzel. Wenn Sie eine speichern möchten E hingegen nicht schickt acht Bits, die eine E. vertreten Stattdessen schickt welche Muster von Bits? Ein. Und was ist schön daran ist, dass E ist die beliebteste Brief, und Sie verwenden die kürzesten Code dafür. Die nächste beliebtesten Brief sieht aus wie es war A. Und so, wie viele Bits er schlage mit dafür? Null, eins. 

Und weil es umgesetzt wie dieses Baumes, für jetzt lassen Sie mich vor, es gibt keine Zweideutigkeit in Morse Code, da alle Briefe, die Sie interessieren sind am Ende dieser Kanten. Also das ist nur ein Anwendung eines Baumes. Dies ist-- und ich werde winken meine Hand auf diese, wie Sie könnte dies als eine C-Struktur zu realisieren. Wir müssen nur zu kombinieren ein Symbol, wie ein char, und die Frequenz in links und rechts. Aber schauen wir uns zwei Abschluss Beispiele, die Sie zu sehr vertraut mit, nachdem Quiz Null Problem stellte fünf. 

So gibt es die Datenstruktur als Hash-Tabelle bekannt. Und eine Hash-Tabelle ist eine Art kühlen, dass sie Eimer hat. Und angenommen, es gibt vier Eimer Hier, nur vier Leerstellen. Hier ist ein Kartenspiel, und wird hier verein, spaten, verein, Diamanten, verein, Diamanten, Club, Diamanten, clubs-- so ist dies die zufällig. Herzen, also bin ich hearts-- bucketizing alle Eingänge hier. Und eine Hash-Tabelle Bedürfnissen auf Ihre Eingabe suchen, und dann legen Sie sie in einem bestimmten legen auf der Grundlage, was Sie sehen. Es ist ein Algorithmus. Und ich wurde mit einem Super- einfache visuelle Algorithmus. Der schwierigste Teil davon war zu erinnern, was die Bilder waren. Und dann gibt es insgesamt vier Dinge. 

Jetzt wurden die Stapel wächst, die ist eine bewusste Gestaltung Sache hier. Aber was könnte ich machen? Also eigentlich hier haben wir eine Haufen alter Schulprüfung Bücher. Nehmen wir an, ein Bündel von Studenten Namen sind hier. Hier ist eine größere Hash-Tabelle. Anstelle von vier Schaufeln, Ich habe, sagen wir, 26. Und wir wollten nicht gehen, leihen 26 Dinge von außen [? Annenberg?], So hier ist fünf, die darstellen A bis Z. Und wenn ich sehen einen Schüler, deren Name mit A, Ich werde seine Quiz dort setzen. Wenn jemand beginnt mit C, dort drüben, A-- eigentlich nicht wollte, das zu tun. B geht hier. Also ich habe A und B und C und Jetzt hier ist ein weiterer Student. Aber wenn das Hash-Tabelle ist mit einer Anordnung implementiert, Ich bin ein bisschen geschraubt an diesem Punkt, nicht wahr? Ich Art müssen diese irgendwo unterbringen. 

So eine Art, wie ich dieses Problem zu lösen ist, alle rechts, ist eine geschäftige, B besetzt ist, C ist besetzt. Ich werde ihn in D. Also zumin setzen zuerst, ich habe zufällig den sofortigen Zugriff zu jeder der Schaufeln für die Schüler. Aber jetzt ist es ein bisschen übergegangen in etwas linear, weil, wenn ich für jemanden suchen deren Name mit A, überprüfe ich hier. Sollte dies jedoch nicht der A Student Ich suche nach, Ich Art haben zu Beginn überprüfen die Eimer, weil das, was ich tat, war irgendwie linear Sonde die Datenstruktur. Eine dumme Art zu sagen, nur schauen nach dem ersten verfügbaren Öffnung, und als Plan B gesetzt, so zu sprechen, oder Plan D in diesem Fall wird der Wert an diesem Ort statt. Dies ist nur so, dass, wenn Sie haben, erhielt 26 Standorten und Studenten mit dem Namen Q oder Z, oder so ähnlich , dass zumindest Sie den Raum bist. 

Aber wir haben schon mehr zu sehen clevere Lösungen hier, nicht wahr? Was würden Sie stattdessen tun wenn Sie eine Kollision? Wenn zwei Menschen der Name A, was würden haben eine intelligentere oder mehr gewesen intuitive Lösung als nur Putting A, wobei D sein soll? Warum ich nicht einfach gehen nicht außerhalb [? Annenberg?], wie malloc, einen anderen Knoten, legte es hier, und dann, dass ein Student hier setzen. So daß ich im Grunde haben eine Art eines Arrays, oder vielleicht mehr elegant wie wir sind beginnen, eine verknüpfte Liste zu sehen. 

Und so eine Hash-Tabelle ist eine Struktur, das könnte nur so aussehen, aber klüger, Sie so etwas wie getrennte Verkettung, wobei eine Hash-Tabelle ganz einfach ist eine Anordnung, wobei jede deren Elemente keine Zahl ist, ist selbst eine verknüpfte Liste. So dass Sie super schnell anmelden entscheiden, wo Sie Ihren Wert für Hash. Ähnlich wie mit der Karten Beispiel Ich habe Super schnelle Entscheidungen. Herz geht hier, Diamanten goes here. Same here, geht ein hier D Hier steht, B goes here. So super schnelle Look-ups, und wenn Sie in eine Falle laufen passieren, wo hast du Kollisionen, zwei Personen mit dem gleichen Namen, auch dann Sie gerade beginnen sie miteinander zu verbinden. Und vielleicht haben Sie halten sie sortiert alphabetisch, vielleicht auch nicht. Aber wenigstens haben wir jetzt die Dynamik. Also auf der einen Seite haben wir super schnell konstante Zeit und Art der linearen Zeit Wenn diese verkettete Listen beteiligt beginnen, ein wenig lang zu erhalten. 

Also diese Art von albern, geeky Witz Jahren. Am CS50-Hack-a-thon, wenn die Schüler in zu überprüfen, einige TF oder CA jedes Jahr denkt, es ist lustig zu setzen, ein Zeichen dafür, wie diese, wo es gerade bedeutet, wenn Ihr Name beginnt mit einem A, gehen Sie auf diese Weise. Wenn Ihr Name beginnt mit einem B, gehen this-- OK, es ist lustig, vielleicht später im Semester. Aber es gibt eine andere Möglichkeit dies zu tun, zu. Komm zurück zu, dass. 

Also gibt es diese Struktur. Und dies ist unsere letzte Struktur für heute, Das ist so etwas wie ein Trie. T-R-I-E, die aus irgendeinem Grund kurz zum Abruf, aber es heißt trie. Also ein Trie ist ein weiterer interessanter Amalgam aus einer Menge von diesen Ideen. Es ist ein Baum, der wir zuvor gesehen haben. Es ist nicht ein binärer Suchbaum. Es ist eine Struktur mit einer beliebigen Anzahl von Kindern, aber jedes der Kinder in einem Trie ein Array ist. Ein Array von Größe, sagen, 26 oder vielleicht 27 wenn Sie Namen getrennt unterstützen oder Apostrophe in Namen von Personen. 

Und dies ist eine Datenstruktur. Und wenn Sie von oben sehen nach unten, wie wenn Sie Blick auf die oberen Knoten gibt, M, ist Hinweis auf die am weitesten links, was es gibt, die dann A, X, W, E, L, L. Dies ist nur eine Datenstruktur, die willkürlich speichert die Namen von Personen. Und Maxwell durch nur folgende gespeicherte ein Weg der Array Array Array. Aber was ist erstaunlich, zu einem Trie ist dass, während eine verknüpfte Liste und sogar ein Array ist, ist die beste, die wir je bekommen haben linearen Zeit oder logarithmische Zeit auf der Suche jemanden. In dieser Datenstruktur einer Trie wenn meine Daten-Struktur hat einen Namen in es und ich bin für Maxwell, ich bin würde ihn ziemlich schnell zu finden. Ich habe gerade für M-A-X-B-E-L-L zu suchen. Wenn Diese Datenstruktur hingegen wenn N eine Million, wenn es ein Millionen Namen in dieser Datenstruktur, Maxwell ist noch im Gange zu sein erkennbar nach nur M-A-X-B-E-L-L Schritte. Und David-- D-A-V-I-D Schritte. Mit anderen Worten, indem eine Datenstruktur, ist erhielt, von denen alle diese Anordnungen alle sich selbst zu versorgen mit wahlfreiem Zugriff, Ich kann beginnen, bis Volks Namen über einen Betrag von Zeit, die ist proportional zu der Anzahl nicht der Dinge in der Datenstruktur, wie eine Million vorhandenen Namen. Die Zeit, die es nimmt mich zu finden M-A-X-W-E-L-L in dieser Datenstruktur ist proportional nicht der Größe der Datenstruktur, sondern auf die Länge des Namens. Und realistisch die Namen wir nachschlagen werden nie verrückt lang. Vielleicht hat jemand einen 10 Charakter hat zu nennen, 20 Charakternamen. Es ist sicherlich endlichen, nicht wahr? Es ist ein Menschen auf der Erde, hat die längste mögliche Namen, aber dieser Name ist eine Konstante Wertlänge, nicht wahr? Es ist nicht in irgendeiner Weise zu variieren. Also auf diese Weise, haben wir erreicht eine Datenstruktur dh konstante Zeit Look-up. Es dauert eine Reihe von Schritten abhängig von der Länge der Eingabe, aber nicht die Anzahl der Namen in der Datenstruktur. Wenn wir also das Doppelte der Anzahl der Namen im nächsten Jahr von einer Milliarde auf zwei Milliarden, Befund Maxwell dauern wird genau die gleiche Anzahl von sieben Schritten um ihn zu finden. Und so scheinen wir erreicht haben unsere heilige Gral der Laufzeit. 

So ein paar schnellen Ankündigungen. Quiz Null steht vor der Tür. Mehr dazu auf der Website der Kurs über die nächsten paar Tage. Montag lecture-- es ist ein Ferien hier in Harvard am Montag. Es ist nicht in New Haven, so wir nehmen die Klasse nach New Haven zum Vortrag am Montag. Alles wird gefilmt werden und live über wie üblich, aber wir beenden heute mit einem 30-Sekunden-Clip namens "Deep Thoughts" von Daven Farnham, die wurde im vergangenen Jahr von Samstag inspiriert Night Live zu "Deep Thoughts" von Jack Handlich, die sollte nun sinnvoll. 

FILM: Und jetzt, "Deep Thoughts "von Daven Farnham. Hashtabelle. 

Sprecher 1: Okay, das ist es für jetzt. Wir sehen uns nächste Woche. 

DOUG: Um es in Aktion zu sehen. Werfen wir also einen Blick auf, dass gerade jetzt. Also hier haben wir eine unsortierte Array. 

IAN: Doug, können Sie voran gehen und neu starten dies nur eine Sekunde, bitte. Alle Rechte, sind Kameras rollen, so Aktion, wenn Sie bereit, Doug sind, OK? DOUG: Okay, so was wir haben hier eine unsortierte Array. Und ich habe alle Elemente farbig rot, um anzuzeigen, dass es in der Tat, unsortiert. So erinnern daran, dass das erste, was wir tun, ist sortieren wir die linke Hälfte des Feldes. Dann sortieren wir uns das Recht Hälfte des Feldes. Und ya-da, ya-da, ya-da, wir sie miteinander verschmelzen. Und wir haben eine komplett sortierten Array. Also das ist, wie Mergesort funktioniert. 

IAN: Whoa, whoa, whoa, Schnitt, Schnitt, Schnitt, geschnitten. Doug, können Sie nicht nur ya-da, ya-da, ya-da, Ihren Weg durch merge sort. 

DOUG: ich gerade tat. Es ist in Ordnung. Wir sind gut zu gehen. Lassen Sie uns einfach weiter ins Rollen. Wie auch immer, 

IAN: Sie haben zu erklären, es vollständiger als die. Das ist einfach nicht genug. DOUG: Ian, wir nicht müssen zurück zu einem gehen. Es ist in Ordnung. Wie auch immer, wenn wir mit merge-- weiter Ian, wir sind in der Mitte der Dreharbeiten. 

IAN: Ich weiß. Und wir können nicht einfach ya-da, ya-da, ya-da, durch den gesamten Prozess. Sie müssen erklären, wie die zwei Seiten zusammengefügt zu werden. 

DOUG: Aber wir haben bereits erklärte, wie die beiden sides-- 

IAN: Sie haben gerade gezeigt, ihnen ein Merge-Array. DOUG: Sie kennen den Prozess. Es geht ihnen gut. Wir haben über sie zehn Mal verschwunden. 

IAN: Sie übersprungen genau richtig darüber. Wir gehen zurück auf eine, die Sie kannst du nicht ya-da, ya-da über sie. Also gut, zurück zu einem. 

DOUG: Ich muss zurück durch alle Folien? Mein Gott. Es ist wie das sechste Mal, Ian. Es ist in Ordnung. 

IAN: Alles klar. Bereit? Groß. Aktion.