[Powered by Google Translate] [Woche 6] [David J. Malan] [Harvard University] [Dies ist CS50.] [CS50.TV] 

Dies ist CS50, und dies ist der Beginn der Woche 6, so ein paar neue Tools sind jetzt für Sie die Vorteile zu nehmen, von denen die erste ist CS50 Kriterien genannt. Quoten sind, wenn Sie wie ich oder einer der Lehre Stipendiaten sind, Sie haben wahrscheinlich ein Programm, dessen Stil sieht ein wenig so etwas wie dieses gesehen. Vielleicht fang an zu schneiden einige Ecken spät in der Nacht, oder du wirst mit ihm später beschäftigen, und dann ein TF oder CA überkommt während der Bürozeiten. Dann ist es für uns schwer zu lesen. Nun ist dieser Code syntaktisch korrekt ist, und es wird kompiliert, und es wird tatsächlich ausgeführt. Aber es ist definitiv kein 5 für Stil. 

Aber jetzt, wenn wir in dieses Verzeichnis gehen hier- und bemerken, dass ich conditions2.c-have und ich laufe dieses neuen Befehl style50, auf diese Datei conditions2.c, Enter, feststellen, dass ich es bin darüber informiert, dass es war stilisiert. Gedit bemerkt, dass die Datei auf der Festplatte geändert wurde, und wenn ich laden klicken, werden alle Ihre Probleme jetzt automatisiert. [Applaus] Das ist eines der Dinge, die wir an diesem Wochenende. Erkenne, dass sie unvollkommen ist, weil es einige Codes sind dass es einfach nicht in der Lage, perfekt zu stilisieren, aber weiß, das ist jetzt ein Werkzeug, das Sie nutzen können wenn auch nur, um aufzuräumen einige der errantly platziert geschweiften Klammern und dergleichen. 

Aber überzeugender ist jetzt CS50 Check. Mit CS50 prüfen, können Sie tatsächlich die gleichen Korrektheit Tests auf Ihrem eigenen Code, dass die Lehre Stipendiaten der Lage sind. Dies ist ein Befehlszeilenprogramm, das kommt jetzt in das Gerät sobald Sie eine update50 nach tun pset 4 Spezifikationen, und verwenden Sie es im Wesentlichen wie folgt aus. Sie führen den Befehl check50. Dann passieren Sie in einer Befehlszeile Argument, oder allgemeiner als Schalter oder eine Fahne bekannt. Im Allgemeinen sind die Dinge, die Bindestriche müssen als ein Schalter zu einem Kommandozeilen-Programm, gibt so-c die Kontrollen, die Sie ausführen möchten. 

Die Tests, die Sie ausführen möchten sind eindeutig durch diese Zeichenfolge identifiziert, 2012/pset4/resize. Mit anderen Worten, das ist nur eine beliebige aber eindeutige Zeichenfolge , die wir verwenden, um eindeutig zu identifizieren pset 4 die Richtigkeit Tests. Und dann geben Sie eine durch Leerzeichen getrennte Liste der Dateien, die Sie hochladen möchten um CS50 prüfen für die Analyse. Zum Beispiel, wenn ich gehe in meine Lösung hier für resize.c- Lassen Sie mich eröffnen eine größere Terminal-Fenster- und ich voran gehen und laufen, sagen wir check50-c 2012/pset4/resize, und dann habe ich voran gehen und geben Sie die Namen der Dateien, resize.c, und drücken Sie dann die Eingabetaste, es komprimiert, lädt es, prüft es, und ich konnte eine ganze Reihe von Tests. Die in rot oben links sagt, dass resize.c und bmp existieren. Das war der Test. Das war die Frage, die wir gestellt. Und es ist unglücklich, weil die Antwort falsch war. Der weiße Text heißt es erwartet bmp.h zu existieren, und das ist einfach meine Schuld. Ich habe vergessen, es hochzuladen, damit ich beide Dateien hochladen, resize.c und bmp.h. Aber jetzt feststellen, alle anderen Tests sind in gelb, weil sie noch nicht ausgeführt haben, und so das Smiley-Gesicht ist vertikal, weil er weder glücklich noch traurig ist, aber wir müssen diese Frage in rot Wiedergutmachung, bevor diese andere Kontrollen ausgeführt wird. 

Lassen Sie mich dieses Problem beheben. Lassen Sie mich verkleinern und erneut diese, dieses Mal mit bmp.h auch auf der Kommandozeile, Enter, und jetzt, wenn alles gut geht, es geht um zu überprüfen, und dann wieder ein Ergebnis-halten Sie den Atem- alles grün, was bedeutet, ich bin wirklich gut auf pset 4 so weit. Sie können sehen und folgern aus dem beschreibenden Text hier genau das, was es ist, wir getestet. Wir testeten zuerst gar die Dateien vorhanden sind? Wir haben dann geprüft hat resize.c compile? Dann testeten wir es nicht die Größe eines 1x1-Pixel BMP, wenn n, die Größenänderung Faktor 1 ist. Nun, wenn Sie keine Ahnung, was n haben, werden Sie, sobald Sie in pset 4 tauchen, aber das ist einfach eine Plausibilitätsprüfung, um sicherzustellen, dass Sie nicht Größenänderung ein Bild überhaupt, wenn die Größenänderung Faktor 1 ist. Wenn dagegen die Größe es eine 1x1-Pixel zu einem 1x1 Pixel BMP zu 2x2 richtig wenn n 2 ist, dann ähnlich bildet Mine entsprechend. 

Kurz gesagt, dies zu, ein gemeint ist, nehmen Sie die Kreuzung der Finger aus der Gleichung rechts, bevor Sie Ihren pset. Sie wissen genau, was Ihre TF wird bald wissen, wenn Sie über die Einreichung einige der genannten Problembereiche Sätze gehen, und auch die pädagogische Motivation ist wirklich zu setzen die Möglichkeit vor sich, so dass, wenn Sie a priori wissen dass es Fehler in Ihrem Code und Tests, die nicht weitergegeben werden, Sie können in effizienter Zeit bis vor genommen, um diese Probleme zu lösen anstatt Punkte verlieren, bekommen Feedback von Ihren TF, und dann gehen, "Ahh," wie sollte ich dachte, dass sich zu haben. Nun zumindest gibt es ein Werkzeug, um Ihnen helfen, dass. Es wird nicht darauf hingewiesen, wo der Fehler ist, aber es wird Ihnen sagen, was ist symptomatisch für sie. 

Jetzt erkennen die Tests sind nicht unbedingt erschöpfend. Nur weil Sie einen Bildschirm voller grüner Smiley-Gesichter bedeutet nicht, dass Ihr Code ist perfekt, aber es bedeutet, dass sie bestimmte Tests durch das spec verschrieben übergeben. Manchmal werden wir nicht loslassen Schecks. Beispielsweise whodunit, einer der Aspekte der pset 4, ist etwas enttäuschend, wenn wir Ihnen Die Antwort auf die Frage, was es ist, und es gibt eine Reihe von Möglichkeiten zu offenbaren wer die Person ist in dem roten Rauschen. Die Spezifikation wird immer in der Zukunft angeben, für pset 5 an Was prüft für Sie vorhanden sind. Sie werden feststellen, es ist das weiße URL an der Unterseite. Denn jetzt ist dies nur Diagnoseausgang. Wenn Sie diese URL besuchen, erhalten Sie eine ganze Reihe von verrückten, kryptische Nachrichten Sie sind herzlich eingeladen, durch zu schauen, aber es ist vor allem für die Mitarbeiter so dass wir zu diagnostizieren und zu debuggen Bugs in check50 sich. 

Ohne Umschweife, lasst uns an, wo wir aufgehört zu bewegen. CS50-Bibliothek haben wir für einige Wochen gewährt, aber dann letzten Wochen begannen wir Abziehen einer der Schichten davon. Wir begannen beiseite String zugunsten dessen, was statt? [Studenten] Char. Char *, die ein char * hat die ganze Zeit, aber jetzt haben wir nicht zu behaupten, dass es eine tatsächliche Datentyp string ist. Vielmehr ist es ein Synonym von Sorten für char *, und eine Zeichenkette eine Folge von Zeichen, Warum also macht es Sinn, Strings als char * s darstellen? Was macht ein char * im Rahmen dieses Konzepts einer Zeichenfolge darzustellen? Yeah. >> [Student] Das erste Zeichen. Gut, das erste Zeichen, aber nicht ganz das erste Zeichen. Es ist die-[Studenten] Adresse. Gut, die Adresse des ersten Zeichens. Alles, was notwendig ist, um einen String in einem Arbeitsspeicher des Computers stellen ist nur die einzigartige Adresse der ersten Byte. Sie müssen nicht einmal wissen, wie lange es denn wie können Sie herausfinden, dass Sie dynamisch? [Student] String Länge. Sie können String-Länge, ausgezeichnet, aber wie funktioniert Stringlänge Arbeit? Was bedeutet es? Yeah. [Student] Keep going, bis Sie das Null-Zeichen erhalten. Ja, genau, es ist nur eine Iteration mit einer for-Schleife, while-Schleife, was sonst vom * bis zum Ende, und das Ende wird vertreten durch \ 0, die sogenannte nul Charakter, nul, nicht mit null, die ein Zeiger verwechselt werden, die kommen im Gespräch heute wieder. 

Wir geschält zurück eine Schicht von GetInt, und dann nahmen wir einen Blick auf GetString, und dass diese beiden Funktionen, oder wirklich erinnern, GetString war unter Verwendung einer bestimmten Funktion tatsächlich analysiert wird, wird das Lesen oder zu analysieren, die Eingabe des Benutzers. Und was war das neue Funktion? Scanf oder sscanf. Tatsächlich kommt in ein paar verschiedenen Geschmacksrichtungen. Es gibt scanf, es gibt sscanf gibt es fscanf. Für jetzt aber, lasst uns auf die man am leichtesten dargestellt konzentrieren, und lassen Sie mich gehen Sie vor und eröffnen im Gerät eine Datei wie diese, scanf1.c. Dies ist ein super einfaches Programm, aber das tut etwas, dass wir nie getan haben Ohne die Hilfe des CS50 Bibliothek. Diese bekommt einen int von einem Benutzer. Wie funktioniert es? Nun, in Zeile 16 gibt, feststellen, dass wir einen int namens x erklären, und an diesem Punkt in der Geschichte, was ist der Wert x? [Unverständlich Studenten Antwort] [David M.] Richtig, wer weiß, einige Müll-Wert möglicherweise, so in 17, wir sagen, der Benutzer gib mir eine Nummer, bitte, und Schritt 18 ist, wo es interessant wird. Scanf scheint eine Idee von printf, dass es nutzt diese Format-Codes in Anführungszeichen zu leihen. % D ist natürlich eine Dezimalzahl. Aber warum bin ich vorbei in & x anstelle von nur x? Ersteres ist richtig. Yeah. [Unverständlich Studenten Antwort] Genau, wenn das Ziel des Programms, wie die Funktion GetInt selbst, wird, um eine int vom Benutzer bekomme ich passieren können Funktionen alle Variablen ich will, aber wenn ich nicht an ihnen vorbeigehen Referenz oder Adresse oder Zeiger, die alle ein Synonym für die heutigen Zwecke wird diese Funktion hat keine Möglichkeit, den Inhalt dieser Variablen ändern. Dies würde in einer Kopie wie die fehlerhafte Version von Swap vorbei dass wir über ein paar Mal geredet jetzt. 

Aber anstatt, indem Sie & x, bin ich buchstäblich vorbei, was? [Student] Die Adresse. >> Die Adresse von x. Es ist wie Zeichnen einer Karte für die Funktion aufgerufen scanf und sagen hier, Dies sind die Wegbeschreibung zu einem Stück Speicher im Computer dass Sie gehen zu speichern einige Integer in. Damit sscanf jetzt zu tun, dass welchem ​​Betreiber ist das, was Stück Syntax es gehen zu müssen, verwenden obwohl wir es nicht sehen können, weil jemand anderes schrieb diese Funktion? In anderen Worten - was ist das? [Student] X zu lesen. Es geht um etwas zu lesen, aber nur in Bezug auf x hier. Wenn scanf wird die Adresse von x vergangen, syntaktisch ist das, was Betreiber verpflichtet, irgendwo existieren Innere scanf die Umsetzung, so dass scanf kann tatsächlich schreiben Sie eine Zahl 2 an diese Adresse? Yeah, so die *. Daran erinnern, dass die * unsere Dereferenzierungsoperator, was im wesentlichen bedeutet dorthin ist. 

Sobald Sie habe eine Adresse übergeben, wie es hier der Fall ist, scanf ist wahrscheinlich-wenn wir tatsächlich sah sich um seinen Quellcode- tut * x oder den Gegenwert tatsächlich an diese Adresse gehen und einen Wert gibt. Jetzt, da, wie scanf Input bekommt von der Tastatur, wir winken uns die Hände aus für heute. Einfach davon ausgehen, dass das Betriebssystem sscanf zu sprechen erlaubt des Benutzers Tastatur, aber an diesem Punkt jetzt in Zeile 19, wenn wir einfach ausdrucken x, so scheint es der Fall zu sein das scanf hat einen int in x gesetzt. Das ist genau, wie scanf funktioniert, und erinnern an vergangene Woche das ist genau, wie GetString und GetInt und seinen anderen Familie von Funktionen letztendlich funktioniert, wenn auch mit leichten Abweichungen wie sscanf, was bedeutet, scannen eine Zeichenfolge anstelle der Tastatur. Aber lassen Sie uns einen Blick auf eine kleine Abweichung von dieser. In scanf2, habe ich eigentlich vermasselt. Was ist falsch, und ich werde den Kommentar, die als viel erklärt verbergen Was ist falsch an diesem Programm, Version 2? Seien Sie als technischer wie möglich dieser Zeit. Es sieht ziemlich gut. Es ist schön eingerückt, aber- okay, wie wäre es lasst beschneiden es auf kürzere Fragen? Line 16. Was ist in Zeile 16 zu tun in präzise, ​​aber technisches Englisch? Immer ein wenig umständlich. Ja, Michael. [Student] Es ist auf den ersten Buchstaben eines Strings zeigt. 

Okay, schließen. Lassen Sie mich zwicken, dass ein wenig. Unter Hinweis auf die ersten Buchstaben eines Strings, werden Sie eine Variable deklarieren als Puffer das wird auf die erste Adresse eines String zeigen, oder vielmehr, das wird insbesondere ein char zeigen. Beachten Sie es nicht wirklich zeigen überall, weil es keinen Zuweisungsoperator. Es gibt kein Gleichheitszeichen, so alles, was wir tun, ist Zuteilung der variablen genannte Puffer. Es geschieht auf 32 Bit sein, weil es ein Zeiger ist, und der Inhalt des Puffers vermutlich schließlich wird die Adresse eines char enthalten, aber für jetzt, was bedeutet Puffer enthalten? Nur einige gefälschte, wer weiß, einige Müll Wert, weil wir nicht explizit initialisiert haben, so sollten wir nicht davon ausgehen, nichts. Okay, jetzt 17 ist, was bedeutet Zeile 17 zu tun? Vielleicht wärmt diese auf. Er druckt einen String, nicht wahr? Er druckt String bitte. 

Linie 18 ist eine Art vertraut nun, dass wir gerade gesehen eine Abweichung von diesen aber mit einem anderen Format, Code, so dass in der Leitung 18, wir sagen scanf hier ist die Adresse eines Stück Speicher. Ich möchte, dass du in einem String klingeln, wie% s stillschweigend, aber das Problem ist, dass wir nicht ein paar Dinge zu erledigen hier. Was ist eines der Probleme? [Student] Es versucht zu dereferenzieren einen Null-Zeiger ist. Gut, null oder einfach sonst unbekannte Zeigern. Sie reichte scanf eine Adresse, aber Sie sagte nur einen Moment vor dass diese Adresse ist einige Müll Wert, weil wir nicht wirklich zuordnen kam es zu nichts, und so du sagst scanf effektiv zu gehen legte einen String hier aber wir wissen nicht, wo hier noch ist, so haben wir nicht wirklich Speicher für Puffer reserviert. Außerdem, was sind Sie auch gar nicht sagen, scanf? Angenommen, das war ein Stück Erinnerung, und es war kein Müll Wert, aber du bist immer noch nicht sagen, scanf etwas Wichtiges. [Student] Wo es tatsächlich ist, das kaufmännische. Ampersand, so dass in diesem Fall ist es okay. Weil Puffer bereits als Zeiger deklariert mit der * Stück Syntax, brauchen wir nicht, um kaufmännisches verwenden denn es ist bereits eine Adresse, aber ich glaube, ich hörte es hier. [Student] Wie groß ist es? Gut, wir nicht sagen, scanf, wie groß dieser Puffer ist, Das bedeutet, selbst wenn Puffer ein Zeiger waren, wir sagen scanf, legte einen String hier aber hier konnte 2 Bytes sein, es könnte 10 Byte sein, es könnte ein Megabyte sein. Scanf hat keine Ahnung, und weil dies ein Stück Speicher Vermutlich ist es nicht ein String leer. Es ist nur ein String, wenn Sie Zeichen und eine \ 0 zu diesem Stück Speicher zu schreiben. Jetzt ist es nur einige Brocken Speicher. Scanf wird nicht wissen, wann man aufhören muss schriftlich an diese Adresse. 

Wenn Sie sich erinnern einige Beispiele in der Vergangenheit, wo ich zufällig auf der Tastatur getippt versucht, einen Pufferüberlauf, und wir sprachen am Freitag über genau dies. Wenn ein Gegner irgendwie spritzt in Ihr Programm ein viel größeres Wort oder einen Satz oder eine Phrase, dann erwarteten Sie überrannt ein Stück Erinnerung, die schlimme Folgen haben kann, wie wenn man über das ganze Programm selber. Wir müssen das irgendwie beheben. Lassen Sie mich Verkleinern und gehen in die Version 3 des Programms. Das ist ein bisschen besser. In dieser Version den Unterschied bemerken. In Zeile 16, bin ich wieder eine Variable deklarieren als Puffer, aber was ist es jetzt? Es ist ein Array von 16 Zeichen. Das ist gut, weil diese Mittel kann ich jetzt sagen, scanf Hier ist eine tatsächliche Stück Speicher. Man kann fast von Arrays denke als Zeiger jetzt obwohl sie nicht sind eigentlich gleichwertig. Sie werden sich anders verhalten in unterschiedlichen Kontexten. Aber es ist sicherlich der Fall, dass Puffer verweisen 16 zusammenhängenden Zeichen, weil das ist, was ein Array ist und seit einigen Wochen jetzt gewesen. 

Hier sage ich scanf hier ist ein Stück Erinnerung. Dieses Mal ist es eigentlich ein Stück Erinnerung, aber warum ist das Programm noch verwertbar? Was ist falsch noch? Ich habe gesagt, gebt mir 16 Bytes, aber- [Student] Was, wenn sie geben in mehr als 16? Genau, was, wenn der Benutzer in 17 Zeichen oder 1700 Zeichen? In der Tat, mal sehen, ob wir nicht stolpern diesen Fehler jetzt. Es ist besser, aber nicht perfekt. Lassen Sie mich gehen Sie vor und führen Sie make scanf3 dieses Programm zu kompilieren. Lassen Sie mich laufen scanf3, String bitte: hallo, und wir scheinen in Ordnung zu sein. Lassen Sie mich versuchen, ein wenig länger ein, hallo. Okay, lass es uns tun hallo there how are you today, Enter. Erste Art von Glück hier, sagen wir hallo gibt how are you. Verdammt. Okay, wir hatten Glück. Mal sehen, ob wir nicht dieses Problem beheben. Nein, es ist nicht, um mich zu kopieren. Lassen Sie uns noch einmal versuchen. Alle Rechte, stehen. Wir werden sehen, wie lange ich kann behaupten, zu konzentrieren, während noch dies zu tun. Verdammt. Das ist eher geeignet, eigentlich. Dort gehen wir. Punkt gemacht. 

Dies peinlich obwohl es auch, es ist auch eine der Quellen der großen Verwirrung beim Schreiben von Programmen, die Fehler haben, weil sie sich manifestieren nur einmal in eine Weile manchmal. Die Realität ist, dass selbst wenn Ihr Code vollständig gebrochen ist, es könnte nur vollständig gebrochen einmal in eine Weile denn manchmal, im Wesentlichen, was passiert ist, das Betriebssystem reserviert ein wenig mehr Speicher, als Sie tatsächlich benötigen welchem ​​Grund auch immer, und so niemand sonst mit der Speicher direkt nach dem Stück von 16 Zeichen, Wenn Sie also 17, 18, 19, was auch immer, es ist nicht so eine große Sache zu gehen. Nun, die Computer, auch wenn sie nicht an diesem Punkt abstürzen, könnte schließlich verwenden Byte-Zahl 17 oder 18 oder 19 für etwas anderes, an welchem ​​Punkt Ihrer Daten, die Sie dort stellen, allerdings zu lange, wird überschrieben möglicherweise durch eine andere Funktion. Es ist nicht notwendigerweise erhalten bleiben, aber es wird nicht unbedingt zu einer seg Fehler. Aber in diesem Fall habe ich endlich sofern genügend Zeichen dass ich im wesentlichen übertraf meine Segment des Speichers, und bam, das Betriebssystem sagte: "Sorry, das ist kein guter, Segmentation Fault ist." 

Und lassen Sie uns nun sehen, ob das, was bleibt hier in meinem Verzeichnis- feststellen, dass ich diese Datei hier haben, Kern. Beachten Sie, dass dies wiederum ist ein Core-Dump genannt. Es ist im Wesentlichen eine Datei, die den Inhalt Ihres Programms Speicher enthält an dem Punkt, an dem es abgestürzt und nur ein kleines Beispiel hier versuchen lassen Sie mich hier hinein und führen Sie gdb auf scanf3 und geben Sie dann ein drittes Argument genannt Kern, und hier bemerken, dass, wenn ich Liste den Code, wir können wie gewohnt mit gdb zu starten Fuß durch dieses Programm und ich kann laufen lassen und sobald ich getroffen-wie mit dem Schritt Befehl gdb- sobald ich traf die potenziell buggy Linie nach der Eingabe in einem riesigen string, Ich werde in der Lage sein, um tatsächlich zu identifizieren es hier. Mehr zu diesem Thema, aber im Schnitt in Bezug auf Core-Dumps und dergleichen, so dass Sie tatsächlich herumzustochern Innenseite der Core-Dump und siehe, welche Linie Sie das Programm gescheitert. Fragen Sie dann auf Zeigern und Adressen? Weil heute, werden wir zu Beginn der Einnahme für selbstverständlich, dass diese Dinge existieren und wir wissen genau, was sie sind. Ja. 

[Student] Wieso hast du nicht ein kaufmännisches nächsten, über die Teil- Gute Frage. Wie komme ich musste nicht ein kaufmännisches neben dem Charakter Array setzen wie ich es zuvor getan Mit den meisten unserer Beispiele? Die kurze Antwort lautet Arrays sind ein wenig speziell. Sie können fast denken, einen Puffer als tatsächlich eine Adresse, und es passiert einfach so der Fall zu sein, dass die eckigen Klammern ist ein Komfort, so dass wir in die Halterung 0, Halterung 1 gehen kann, Halterung 2, ohne die * Notation verwenden. Das ist ein bisschen wie ein Notlüge, weil Arrays und Zeiger sind in der Tat ein wenig unterschiedlich, sie können aber oft aber nicht immer synonym verwendet werden. Kurz gesagt, wenn eine Funktion erwartet einen Zeiger auf einen Block arbeiten, Sie können entweder geben sie eine Adresse, die von malloc zurückgegeben wurde, und wir malloc wieder sehen dauerte nicht lange, oder Sie können geben sie den Namen eines Arrays. Sie müssen nicht kaufmännisches mit Arrays zu tun, weil sie ohnehin schon sind im wesentlichen wie Adressen. Das ist die einzige Ausnahme. Die eckigen Klammern machen sie besonders. 

Könnten Sie ein kaufmännisches Und neben dem Puffer? Nicht in diesem Fall. Das wäre nicht da, wieder zu arbeiten, dieser Ecke Fall wo Arrays sind nicht ganz eigentlich Adressen. Aber wir werden vielleicht kommen zurück zu dieser vor langer mit anderen Beispielen. Lasst uns versuchen, hier ein Problem zu lösen. Wir haben eine Datenstruktur, die wir schon seit einiger Zeit als ein Array bekannt verwendet wurde. Case in point, ist das, was wir hatten. Aber Arrays haben einige Vor-und Nachteile. Arrays sind nett warum? Was ist eine Sache, die Sie gerne zu dem Ausmaß Ihnen Arrays-about-Arrays? Was ist bequem über sie? Was ist überzeugend? Warum haben wir führen sie in erster Linie? Yeah. [Student] Sie können eine Menge von Daten zu speichern, und Sie müssen nicht eine ganze Ding benutzen. Sie können einen Abschnitt. Gut, mit einem Array Sie eine Menge Daten speichern kann, und Sie müssen nicht unbedingt alle davon verwenden, so können Sie overallocate, was könnte praktisch sein, wenn Sie nicht im Voraus wissen, wie viele von etwas zu erwarten. 

GetString ist ein perfektes Beispiel. GetString von uns geschrieben, hat keine Ahnung, wie viele Zeichen zu erwarten, so dass die Tatsache, dass wir Stücke von zusammenhängenden Speicher zuzuordnen ist gut. Arrays auch ein Problem zu lösen, sahen wir vor ein paar Wochen jetzt wo Ihr Code in etwas sehr schlecht konzipiert übertragen beginnt. Daran erinnern, dass ich einen Studenten Struktur namens David geschaffen, und dann das war eigentlich eine Alternative, obwohl, um eine Variable mit dem Namen name und eine weitere Variable genannt, ich denke, Haus, und eine andere Variable namens ID, weil in dieser Geschichte wollte ich dann etwas anderes vorstellen wie Rob in das Programm, so dann habe ich beschlossen warten Sie eine Minute, Ich brauche, um diese Variablen umbenennen. Nennen wir meinen name1, ID1, house1. Nennen wir Robs name2, house2, ID2. Aber dann warten Sie eine Minute, was Tommy? Dann hatten wir drei weitere Variablen. Wir stellten jemand anderes, vier Sätze von Variablen. Die Welt begann chaotisch sehr schnell, so führten wir Strukturen, und was ist überzeugend über ein struct? Was bedeutet eine C-Struktur können Sie tun? Es ist wirklich peinlich heute. Welche? >> [Unverständlich Studenten Antwort] Yeah, gesagt ermöglicht typedef Sie einen neuen Datentyp erstellen, und struct, das Schlüsselwort struct, können Sie kapseln konzeptuell Stücke von Daten zusammen und danach nennen sie so etwas wie ein Student. 

Das war gut so, denn jetzt haben wir modellieren können viel mehr eine Art konzeptionell konsequenten die Vorstellung von einem Schüler in einer Variablen statt dessen eines willkürlich für eine Zeichenfolge, eine für eine ID, und so weiter. Arrays sind nett, weil sie uns zu beginnen Reinigung unseren Code zu ermöglichen. Aber was ist ein Nachteil nun ein Array? Was können Sie nicht? Yeah. [Student] Sie müssen wissen, wie groß es ist. Sie müssen wissen, wie groß es ist, es ist also eine Art Schmerz. Diejenigen von euch, mit vorheriger Programmierung Erfahrung wissen, dass in vielen Sprachen, wie Java, können Sie fragen, ein Stück Erinnerung, die speziell ein Array, wie groß bist du, mit einer Länge, des Vermögens, so zu sprechen, und das ist wirklich praktisch. In C kann man nicht einmal nennen strlen auf einem generischen Array weil strlen, wie das Wort schon sagt, ist nur für Streicher, und Sie können herausfinden, die Länge eines Strings, weil dieser menschlichen Konvention der mit einem \ 0, sondern ein Array, mehr allgemein, ist nur ein Stück Erinnerung. Wenn es ein Array von ints ist, ist es nicht zu einigen besonderen Charakter Am Ende wartet auf Sie. Sie müssen die Länge eines Arrays zu erinnern. Ein weiterer Nachteil eines Arrays bäumte seinen Kopf in GetString sich. Was ist ein weiterer Nachteil eines Arrays? Sir, nur du und ich heute. [Unverständlich Student Response] >> Es ist was? Es ist auf dem Stack erklärt. Okay, erklärte auf dem Stapel. Warum gehst du nicht so? [Student] Weil es wird wiederverwendet. Es wird wiederverwendet. Okay, wenn Sie ein Array an Speicher zuweisen, Sie können zum Beispiel nicht, zurückzukehren, weil es auf dem Stapel ist. Okay, das ist ein Nachteil. Und wie wäre es mit einem anderen mit einem Array? Sobald Sie es zuordnen, du bist Art verschraubt, wenn Sie mehr Platz benötigen als Array hat. 

Dann haben wir eingeführt, Rückruf, malloc, was uns die Möglichkeit, dynamisch Speicher zuweisen. Aber was, wenn wir versuchten, eine andere Welt insgesamt? Was, wenn wir wollten ein paar dieser Probleme zu lösen so dass wir statt-my pen eingeschlafen hier- was ist, wenn wir stattdessen wollte Wesentlichen eine Welt schaffen, die nicht mehr so? Dies ist ein Array, und natürlich, verschlechtert diese Art der einmal wir das Ende des Arrays treffen, und ich jetzt nicht mehr Platz für eine weitere ganze Zahl oder ein anderes Zeichen. Was, wenn wir auch eine Art präventiv zu sagen, warum wir nicht entspannen diese Anforderung, dass alle diese Stücke von Speicher zusammenhängenden Rücken an Rücken sein, und warum nicht, wenn ich ein int oder char benötigen, gib mir nur Platz für einen von ihnen? Und wenn ich ein anderes brauchst, gib mir einen anderen Raum, und wenn ich ein anderes brauchst, gib mir einen anderen Raum. Der Vorteil davon ist nun, dass, wenn jemand anderes nimmt den Speicher über hier, keine große Sache. Ich werde dieses zusätzliche Stück Speicher hier und dann ist dies ein zu nehmen. 

Nun ist der einzige Haken dabei, dass diese fühlt sich fast wie ich eine ganze Reihe von verschiedenen Variablen. Das fühlt sich an wie fünf verschiedene Variablen möglicherweise. Aber was, wenn wir stehlen eine Idee von Strings wobei wir irgendwie verknüpfen diese Dinge zusammen konzeptionell und was ist, wenn ich das tat? Dies ist mein sehr schlecht gezeichnet Pfeil. Aber angenommen, daß jede dieser Chunks Speicher wies auf den anderen, und dieser Kerl, der keine Geschwister zu seiner Rechten, hat keine solche Pfeil. Dies ist in der Tat, was heißt eine verkettete Liste. Dies ist eine neue Datenstruktur, die uns ein Stück Speicher zuweisen können, dann noch einen, dann noch einen, dann noch einen, zu jeder Zeit wollen wir während eines Programms, und wir erinnern uns, dass sie alle irgendwie miteinander verwandt buchstäblich chaining sie zusammen, und wir haben das bildlich hier mit einem Pfeil. Aber im Code, was wäre der Mechanismus, über den man irgendwie verbinden könnte, fast wie Scratch, ein Stück zu einem anderen Stück? Wir könnten einen Zeiger, nicht wahr? Denn wirklich der Pfeil, der von der oberen linken Quadrat los ist, dieser Kerl hier, um diesen einen, könnte innerhalb enthalten dieses Platzes nicht nur einige ints, nicht nur einige char, aber was, wenn ich tatsächlich zugeteilten ein wenig mehr Platz, so dass jetzt, jedes meiner Stücke der Erinnerung, obwohl dies wird mich kosten, sieht nun ein wenig mehr rechteckige denen einer der Blöcke von Speicherzellen wird für eine Reihe verwendet, wie die Zahl 1, und dann, wenn dieser Kerl speichert die Nummer 2 diese andere Stück wird für einen Pfeil verwendet, oder konkreter, ein Zeiger. Und wenn ich speichern Sie die Nummer 3 über hier, während ich dies auf diesem Kerl darauf verwenden, und nun dieser Kerl, nehmen wir an, ich will nur drei solcher Stücke der Erinnerung. Ich werde eine Linie durch, dass zu zeichnen, was auf null. Es gibt keine zusätzlichen Charakter. 

Tatsächlich ist dies, wie wir über die Umsetzung gehen etwas, das man eine verkettete Liste ist. Eine verkettete Liste ist eine neue Datenstruktur, und es ist ein Sprungbrett in Richtung viel fancier Datenstrukturen, um Probleme zu lösen beginnen entlang der Linien von Facebook-Typ Probleme und Google-Typ Probleme wo Sie haben riesige Datenmengen, und es nicht mehr schneidet sie alles zusammenhängend speichern und nutzen so etwas wie lineare Suche oder sogar so etwas wie binäre Suche. Sie wollen noch besser Laufzeiten. In der Tat, einer der Heiligen Grails wir später noch diese Woche oder nächstes sprechen ist ein Algorithmus, deren Laufzeit konstant. Mit anderen Worten, es nimmt immer die gleiche Menge an Zeit, egal wie groß der Eingang ist, und dass wäre in der Tat zwingend, umso mehr, als etwas logarithmisch. Was ist das auf dem Bildschirm hier? Jedes der Rechtecke ist genau, was ich gerade machte mit der Hand. Aber die Sache den ganzen Weg auf der linken Seite ist eine spezielle Variable. Es wird ein einziger Zeiger sein, weil das eine gotcha mit einer verketteten Liste, wie diese Dinge genannt werden, ist, dass man auf ein Ende der verketteten Liste zu hängen. 

Nur mit einem String möchten, müssen Sie die Adresse des ersten char kennen. Gleiches Angebot für verkettete Listen. Sie müssen die Adresse des ersten Stück Speicher weiß denn von dort erreicht man alle anderen ein. Downside. Welchen Preis zahlen wir für diese Vielseitigkeit mit einem dynamisch beträchtliche Datenstruktur, wenn wir jemals benötigen mehr Speicher, fein, nur zuordnen eine weitere chunk und ziehen einen Zeiger von den alten zu den neuen Schwanz der Liste? Yeah. [Student] Es dauert etwa doppelt so viel Platz. Es dauert doppelt so viel Platz, so das ist definitiv ein Nachteil, und wir haben gesehen Kompromiss vor zwischen Zeit und Raum und Flexibilität wobei inzwischen brauchen wir nicht 32 Bits für jede dieser Zahlen. Wir brauchen wirklich 64, 32 für die Anzahl und 32 für den Zeiger. Aber hey, ich habe 2 Gigabyte RAM. Hinzufügen eines weiteren 32-Bit hier und hier scheint nicht, dass große Sache. Aber für große Datenmengen, es ist definitiv summiert sich buchstäblich doppelt so viel. Was ist ein weiterer Nachteil jetzt, oder was Funktion geben wir auf, wenn wir stellen Listen von Dingen mit einer verketteten Liste und nicht ein Array? [Student] können Sie nicht überfahren es rückwärts. Sie können nicht fahren sie rückwärts, so dass Sie Art verschraubt, wenn Sie zu Fuß sind von links nach rechts mit einer for-Schleife oder eine while-Schleife und dann merkt man: "Oh, ich muss gehen zurück an den Anfang der Liste wollen." Sie können nicht, weil diese Hinweise nur von links nach rechts gehen, wie die Pfeile zeigen. 

Nun können Sie den Anfang der Liste mit einer anderen Variablen erinnern, aber das ist eine Komplexität im Auge zu behalten. Ein Array, egal, wie weit Sie gehen, können Sie immer tun, Minus, Minus, Minus und gehen Sie zurück, woher du gekommen bist. Was ist ein weiterer Nachteil hier? Yeah. [Unverständlich Studenten stellen] Sie könnten, so haben Sie eigentlich nur eine Datenstruktur namens eine doppelt verknüpfte Liste vorgeschlagen, und zwar, weiss anderen Zeiger zu jedem dieser Rechtecke hinzuzufügen das geht in die andere Richtung, die auf den Kopf, von denen ist nun können Sie hin und her verfahren, Der Nachteil davon ist jetzt bist du mit drei Mal so viel Speicher wie früher und auch die Komplexität im Sinne der Code, den Sie schreiben, um es richtig zu machen. Aber all dies sind vielleicht sehr vernünftige Kompromisse, wenn die Umkehrung ist wichtiger. Yeah. [Student] Sie können auch nicht eine 2D verketteten Liste. Gut, kann man nicht wirklich eine 2D verketteten Liste. Sie konnten. Es ist nicht annähernd so einfach, wie ein Array. Wie ein Array, tun Sie offene Klammer, geschlossene Klammer, Klammer, geschlossen Halterung, und du bekommst einige 2-dimensionale Struktur. Sie könnten Umsetzung eines 2-dimensionalen verketteten Liste wenn Sie Add-wie Sie vorgeschlagen-ein Drittel Zeiger auf jedes dieser Dinge, und wenn Sie über eine andere Liste denke kommen auf Sie 3D-Stil aus dem Bildschirm, um alle von uns ist das nur ein weiteres Kette einiger sortieren. Wir könnten es tun, aber es ist nicht so einfach wie die Eingabe Klammer, eckige Klammer. Yeah. [Unverständlich Studenten stellen] Gut, so ist dies eine echte Kicker. 

Diese Algorithmen, die wir über, wie oh, binäre Suche schmachtete, Sie können eine Reihe von Zahlen auf dem Brett suchen oder ein Telefonbuch so viel schneller, wenn Sie Teile und Herrsche und einen binären Suchalgorithmus, aber Binärsuche erforderte zwei Annahmen. Eines, dass die Daten sortiert wurde. Jetzt können wir vermutlich halten diese sortiert, so vielleicht ist das kein Problem, aber binäre Suche auch angenommen Sie hatten einen wahlfreien Zugriff auf die Liste der Nummern, und ein Array ermöglicht es Ihnen, random access haben, und durch wahlfreien Zugriff, Ich meine, wenn Sie ein Array sind gegeben, wie lange dauert es, nehmen Sie auf Bügel 0 zu bekommen? Eine Operation, die Sie gerade verwenden, [0] und da haben Sie recht. Wie viele Schritte braucht es, um Position 10 zu bekommen? Ein Schritt, die Sie gerade auf [10] zu gehen und du da bist. Im Gegensatz dazu, wie Sie an den 10. Integer in einer verketteten Liste zu bekommen? Sie müssen am Anfang beginnen, weil Sie nur Erinnerung sind der Beginn einer verketteten Liste, wie eine Zeichenkette wird daran erinnert durch die Adresse des ersten char, um und finden, dass der 10. int oder dass der 10. Zeichen in einem String, müssen Sie das ganze verdammte Ding zu suchen. 

Auch wir sind nicht die Lösung aller unserer Probleme. Wir Einführung neuer, aber es hängt wirklich davon ab, was Sie versuchen, um zu entwerfen. In Bezug auf die Umsetzung, können wir eine Vorstellung von diesem Studenten-Struktur zu leihen. Die Syntax ist sehr ähnlich, nur jetzt ist die Idee ein wenig mehr abstrakte als Haus, Name und ID. Aber ich schlage vor, dass wir eine Datenstruktur in C haben dass heißt Knoten, wie das letzte Wort auf der Folie lässt, innerhalb eines Knotens und ein Knoten ist nur eine generische Container in der Informatik. Es ist in der Regel als ein Kreis oder ein Quadrat oder Rechteck als wir getan haben gezeichnet. Und in dieser Datenstruktur, haben wir einen int, n, so das ist die Zahl, die ich speichern möchten. Aber was ist diese zweite Linie, struct node * next? Warum ist das richtig, oder welche Rolle spielt dieses Ding spielen, obwohl es ein wenig kryptisch auf den ersten Blick? Yeah. [Unverständlich Studenten Antwort] Genau, so die * Art von Beute, dass es ein Zeiger einiger sortieren. Der Name dieses Zeigers ist beliebig nächsten, aber wir konnten es nannte haben, was wir wollen, aber was hat dieser Zeiger Punkt? [Student] Ein anderer Knoten. >> Genau, verweist er auf einem anderen solchen Knoten. 

Nun, dies ist eine Art von Neugier C. Erinnern, dass C durch einen Compiler oben nach unten gelesen wird, von links nach rechts, Das bedeutet, wenn das ist ein wenig anders aus, was wir mit den Studenten. Wenn wir einen Studenten definierten wir eigentlich nicht legte ein Wort gibt. Es sagte nur typedef. Dann hatten wir int id, string name, string Haus, und dann Student an der Unterseite des struct. Diese Erklärung ist ein wenig anders, weil wieder ist der C-Compiler ein wenig dumm. Es ist nur noch zu lesen von oben nach unten, also wenn es erreicht die zweite Linie hier wo neben deklariert wird und es sieht, oh, hier ist eine Variable namens nächsten. Es ist ein Zeiger auf eine struct Knoten. Der Compiler wird zu erkennen, was ist ein struct node? Ich habe noch nie von diesem Ding schon mal gehört, weil das Wort Knoten kann nicht anders angezeigt bis die Unterseite, so dass diese Redundanz. Sie müssen struct node hier sagen, die Sie dann später zu verkürzen Dank typedef hier unten, aber das liegt daran, Wir verweisen auf die Struktur selbst im Inneren der Struktur. Das ist die eine gotcha dort. 

Einige interessante Probleme gehen zu ergeben. Wir haben eine Liste von Zahlen. Wie können wir in sie setzen? Wie suchen wir es? Wie können wir von ihm löschen? Besonders jetzt, dass wir all diese Hinweise zu verwalten haben. Sie dachten, Zeiger waren irgendwie kniffligen wenn Sie hatte einen von ihnen nur versuchen, einen int zu lesen. Jetzt müssen wir eine ganze Liste im Wert manipulieren. Warum nehmen wir nicht unsere 5-minütige Pause hier, und dann bringen wir einige Leute auf die Bühne, um genau das zu tun. 

C ist viel mehr Spaß, wenn es gehandelt hat heraus. Wer würde buchstäblich gern als erster? Okay, komm auf. Sie sind zuerst. Wer möchte 9? Okay, 9. Wie wäre es mit 9? 17? Eine kleine Clique hier. 22 und 26 in dieser ersten Reihe. Und dann, wie etwa jemand über wobei an hingewiesen. Sie sind 34. Okay, 34, auf bis zu kommen. Zunächst ist da drüben. Okay, alle vier von euch. Und wer wollte sagen wir für 9? Wer ist unser 9? Wer wirklich will, um 9? Alles klar, komm, 9 sein. Here we go. 34, wir treffen Sie dort drüben. Der erste Teil ist macht euch so aussehen. 26, 22, 17, gut. Wenn man stehen kann an der Seite, weil wir euch in einem Moment malloc sind. 

Gut, gut. Okay, gut, so fragen wir ein paar Fragen hier. Und tatsächlich, was ist Ihr Name? >> Anita. Anita, okay, komm hier rüber. Anita wird uns helfen, eine Art zu lösen ein ziemlich einfache Frage in der ersten, das ist wie finden Sie, ob ein Wert in der Liste ist? Nun bemerken, dass erste, hier dargestellt durch Lucas, ist ein wenig anders, und so seinen Zettel ist absichtlich seitwärts denn es ist nicht ganz so groß und nimmt nicht so viele Bits, obwohl technisch hat er die gleiche Größe des Papiers gerade gedreht. Aber er ist ein wenig anders, er ist nur 32 Bits für einen Zeiger, und all diese Jungs sind 64 Bits, von denen die Hälfte die Zahl ist, von denen die Hälfte ein Zeiger ist. Aber der Zeiger ist nicht dargestellt, so dass, wenn euch könnte etwas ungeschickt mit der linken Hand an der Person neben Ihnen zeigen. Und du bist die Nummer 34. Wie ist dein Name? Ari. Ari, also eigentlich, halten Sie das Papier in die rechte Hand und die linke Hand geht gerade nach unten. Sie repräsentieren null auf der linken Seite. 

Jetzt ist unsere menschliche Bild ist sehr konsistent. Dies ist tatsächlich, wie Zeiger funktionieren. Und wenn Sie kneten eine wenig auf diese Weise, damit ich nicht im Weg bin. Anita hier finden Sie mir die Nummer 22, aber davon ausgehen, eine Einschränkung des Menschen nicht hält Stücke von Papier, aber dies ist eine Liste, und Sie haben nur Lucas zu beginnen weil er ist buchstäblich der erste Zeiger. Angenommen, Sie selbst sind ein Zeiger, und so haben auch Sie die Möglichkeit, auf etwas hinweisen. Warum kommst du nicht mit dem Hinweis auf genau das, was Lucas gerade befindet anfangen? Gut, und lassen Sie mich verabschieden this out hier. Nur aus Gründen der Diskussion, lassen Sie mich nach oben ziehen eine leere Seite hier. Wie buchstabieren Sie Ihren Namen? >> Anita. Okay, Anita. Lassen Sie uns sagen node * anita = lucas. Nun, wir sollten dich nicht anrufen lucas. Wir sollten rufen Sie zuerst. Warum ist das in der Tat Einklang mit der Realität hier? Ein, erstes bereits vorhanden. Zunächst wurde vermutlich irgendwo hier oben zugeordnet. Node * erste, und es wurde eine Liste zugeordnet irgendwie. Ich weiß nicht, wie das passiert ist. Das geschah vor dem Unterricht begonnen. Diese verknüpften Liste von Menschen geschaffen wurde. Und jetzt an diesem Punkt in der Geschichte, das ist alle gehen auf Facebook offenbar später an diesem Punkt in der Geschichte hat Anita initialisiert worden, dass sie gleich erstens was nicht bedeutet, dass Anita Punkte Lucas. Vielmehr weist sie an, was er zeigt auf weil die gleiche Adresse, die im Inneren ist der Lucas 32 Bit - 1, 2, 3 - ist jetzt auch im Inneren von Anitas 32 Bit - 1, 2, 3. 

Jetzt finden 22. Wie würden Sie tun dies gehen? Was ist das? >> Point to whatever. Zeigen Sie was auch immer, so gehen Sie vor und handeln es so gut du kannst hier. Gut, gut, und jetzt bist du deutete auf-was ist Ihr Name mit 22? Ramon. >> Ramon, so Ramon hält sich 22. Sie haben jetzt einen Scheck erfolgen. Hat Ramon == 22, und wenn ja, zum Beispiel, können wir true zurück. Lassen Sie mich, während diese Jungs hier stehen etwas unbeholfen- lass es mich tun etwas schnell wie bool finden. Ich werde weitermachen und sagen (node ​​* list, int n). Ich bin gleich wieder bei euch. Ich muss nur noch einen Code zu schreiben. Und jetzt werde ich weitermachen und tun dies, node * anita = Liste. Und ich werde weitermachen und sagen, während (anita! = NULL). 

Die Metapher ist hier immer ein wenig gestreckt, aber while (anita! = NULL), was will ich tun? Ich brauche eine Möglichkeit der Referenzierung Die Ganzzahl, Anita gerade befindet. In der Vergangenheit mussten, wenn wir Strukturen, die ein Knoten ist, verwendeten wir die Punkt-Notation, und wir würden so etwas sagen wie anita.n, aber das Problem dabei ist, dass Anita nicht ein struct per se. Was ist sie? Sie ist ein Zeiger, so wirklich, wenn wir diesen Punkt verwenden möchten Notation- und dies aussehen wird absichtlich ein wenig kryptisch- Wir haben so etwas wie gehen Sie links whatever Anita tun, ist auf Hinweis und dann die Feld namens n. Anita ist ein Zeiger, aber was ist * anita? Was finden Sie, wenn Sie zu dem, was Anita gerade befindet? Eine Struktur, ein Knoten und ein Knoten, Zurücksetzen, hat ein Feld namens n weil es hat sich erinnern, diese 2 Felder, nächste und n, , die wir sahen vorhin hier richtig. 

Um tatsächlich imitieren dies in Code, konnten wir dies tun und sagen if ((* anita). n == n), die n, dass ich mich für. Beachten Sie, dass die Funktion der Zahl Ich kümmere mich übergeben wurde. Dann kann ich voran gehen und etwas tun, wie return true. Else, wenn das nicht der Fall ist, was ich tun will? Wie übersetze ich zu kodieren, was Anita so intuitiv getan, indem wir zu Fuß durch die Liste? Was soll ich tun hier oben zu simulieren Anita man den Schritt nach links, diesen Schritt auf der linken Seite? [Unverständlich Student Response] >> Was ist das? [Unverständlich Studenten Antwort] Gut, aber nicht eine schlechte Idee, aber in der Vergangenheit, wenn wir dies getan haben, haben wir getan anita + + denn das würde die Nummer 1 Anita hinzuzufügen, die typischerweise bei der nächsten Person zeigen, wie Ramon, oder die Person neben ihm, oder die neben ihm Menschen auf der ganzen Linie. Aber das ist nicht ganz gut hier, weil was bedeutet das Ding wie im Speicher aussehen? Nicht. Wir müssen das deaktivieren. Es sieht aus wie dies zu meinem Gedächtnis, und obwohl ich 1 und 2 und 3 schließen zueinander hingezogen, wenn wir wirklich simulieren dies-can you guys, während immer noch auf den gleichen Leuten, können einige von euch einen zufälligen Schritt zurück, einige von euch eine zufällige Schritt nach vorne? 

Das Chaos ist immer noch eine verkettete Liste, aber diese Jungs könnten überall in Erinnerung sein, so anita + + ist nicht zur Arbeit zu gehen, warum? Was ist an der Stelle anita + +? Wer weiß. Es ist ein anderer Wert, dass passiert einfach so angeordnet werden Unter allen diesen Knoten durch Zufall, weil wir nicht mit einem Array. Wir zugeordnet jedem dieser Knoten einzeln. Okay, wenn du Jungs können reinigt euch wieder nach oben. Lassen Sie mich schlagen vor, dass anstelle von anita + + wir stattdessen tun anita erhält- gut, warum nicht wir, was Anita gerade befindet gehen und dann tun. als nächstes? In anderen Worten, wir gehen Ramon, der hält die Zahl 22 ist, und dann. nächsten ist, als ob Anita kopieren werden würde seine linke Hand Zeiger. Aber sie wollte nicht weiter gehen als Ramon, weil wir 22 gefunden. Aber das wäre die Idee. Nun, dies ist ein Gott-schreckliches Durcheinander. Ehrlich gesagt, wird niemand daran erinnern, jemals diese Syntax, und so dankbar, Es ist tatsächlich ein wenig bewusste-oh, du hast nicht wirklich sehen, was ich geschrieben habe. Dies wäre überzeugender, wenn man könnte. Voila! 

Hinter den Kulissen, war ich die Lösung des Problems auf diese Weise. Anita, um diesen Schritt nach links zu nehmen, Zuerst müssen wir die Adresse gehen, dass Anita gerade befindet und wo sie finden nicht nur n, die wir nur zum Vergleich willen überprüft, aber Sie werden auch nächstes zu finden - in diesem Fall Ramons linken Hand, die auf den nächsten Knoten in der Liste. Aber das ist der Gott-schreckliches Durcheinander, zu dem ich vorhin sprach, aber es stellt sich heraus, C lässt uns zu vereinfachen dies. Statt zu schreiben (* anita), können wir stattdessen einfach schreiben anita-> n, und es ist genau dasselbe funktional, aber es gibt eine Menge mehr intuitive, und es gibt eine Menge mehr im Einklang mit dem Bild, das wir schon seit der Erstellung die ganze Zeit mit Pfeilen. 

Schließlich, was wir brauchen, um am Ende des Programms zu tun? Es gibt eine Zeile Code verbleiben. Zurück, was? Falsch, weil wenn wir durch die ganze while-Schleife und Anita ist in der Tat, null, das heißt, sie ging den ganzen Weg bis zum Ende der Liste wo sie deutete auf-was ist Ihr Name? Ari. >> Ari mit der linken Hand, die null ist. Anita ist jetzt null, und ich merke, du bist nur hier stehen unbeholfen in der Schwebe weil ich werde off einen Monolog hier aber wir leiten Sie wieder einzubeziehen, nur für einen Augenblick. Anita ist an diesem Punkt in der Geschichte null, so dass die while-Schleife beendet wird, und wir müssen wieder falsch, weil, wenn sie bekam den ganzen Weg bis Nullzeiger Ari dann gab es keine Zahl, dass sie in der Liste gesucht. Wir können dies bereinigen auch, aber das ist eine ziemlich gute Umsetzung dann einer Traversal-Funktion, finden eine Funktion für eine verkettete Liste. Es ist immer noch lineare Suche, aber es ist nicht so einfach wie + + ein Zeiger oder + + eine Variable i denn jetzt können wir nicht erraten wobei jeder dieser Knoten sind im Speicher. Wir haben buchstäblich den Spuren von Paniermehl oder, genauer gesagt, Zeiger, um von einem Knoten zu einem anderen zu gelangen. 

Nun wollen wir versuchen, ein anderes. Anita, wollen Sie wieder hierher kommen? Warum gehen wir nicht voran gehen und Zuweisung einer anderen Person aus dem Publikum? Malloc-was ist Ihr Name? >> Rebecca. Rebecca. Rebecca hat aus dem Publikum wurde malloced, und sie speichert nun die Nummer 55. Und das Ziel bei der Hand ist jetzt für Anita einfügen Rebecca in der verketteten Liste hier in den richtigen Ort. Komm hier rüber für einen Moment. Ich habe etwas getan. Ich habe node * getan. Und was ist Ihr Name? Rebecca. >> Rebecca, okay. Rebecca bekommt malloc (sizeof (Knoten)). Genau wie wir Dinge wie Studenten und so weiter in der Vergangenheit zugeordnet, Wir brauchen die Größe des Knotens, so dass nun Rebecca wird, was zeigt? Rebecca hat zwei Felder in ihr, von denen 55 ist. Lasst uns das tun, was, rebecca-> = 55. Aber dann rebecca-> next sollte gerade jetzt-mögen, ist ihre Hand Art von wer weiß? Es ist bei einigen Müll-Wert zeigt, warum also nicht für eine gute Maßnahme wir wenigstens tun dies, damit linke Hand ist jetzt an ihrer Seite. Jetzt Anita, nehmen Sie es von hier. Sie haben Rebecca worden ist zugewiesen. Gehen Sie weiter und finden, wo wir Rebecca sollten setzen. Gut, sehr gut. Okay, gut, und jetzt müssen wir Sie ein bisschen Richtung geben, du hast also Ari erreicht. Seine linke Hand ist null, aber Rebecca gehört eindeutig auf der rechten Seite, also wie können wir diese verketteten Liste verändern um Rebecca in der entsprechenden Stelle einfügen? Wenn Sie könnte buchstäblich bewegen Menschen die linke Hände um je nach Bedarf, wir das Problem auf diese Weise beheben. Okay, gut, und mittlerweile ist Rebecca die linke Hand jetzt an ihrer Seite. 

Das war zu einfach. Lassen Sie uns versuchen Zuweisung-wir fast fertig, 20. Okay, komm auf. 20 zugeteilt wurde, so lassen Sie es mich voran gehen und sagen, hier wieder wir haben gerade node * saad getan. Wir haben malloc (sizeof (Knoten)). Dann machen wir genau die gleiche Syntax wie wir vor über 20 hat, und ich werde tun next = NULL, und jetzt ist es an Anita zu fügen Sie der Liste zu, wenn Sie diese genau die gleiche Rolle spielen könnte. Ausführen. Okay, gut. Jetzt genau überlegen, bevor Sie sich bewegen linken Hände um zu starten. Sie weitem bekam die heikelsten Rolle heute. Wessen Hand sollte zunächst verschoben werden? Okay, warte, ich höre etwas Neins. Wenn einige Leute würden höflich gerne helfen lösen eine unangenehme Situation. Dessen linke Hand sollte zunächst vielleicht aktualisiert werden? Yeah. [Student] Saad ist. Okay, Saad ist, warum, wenn? [Unverständlich Studenten Antwort] Gut, denn wenn wir uns bewegen, was ist Ihr Name? >> Marshall. Marshall, wenn wir uns bewegen, seine Hand zuerst auf null, Jetzt haben wir buchstäblich vier Personen in dieser Liste verwaiste denn er war das einzige, was zeigt auf Ramon und jeder auf der linken Seite so aktualisiert, dass die Zeiger erste war schlecht. Lasst rückgängig machen. Gut, und jetzt gehen Sie vor und verschieben Sie die entsprechende linke Hand zeigt auf Ramon. Das fühlt sich ein wenig redundant. Jetzt gibt es zwei Personen zeigt auf Ramon, aber das ist in Ordnung denn jetzt, wie wir sonst noch aktualisiert die Liste? Was hingegen hat sich zu bewegen? Ausgezeichnet, jetzt haben wir verloren jede Erinnerung? Nein, so gut, mal sehen, ob wir das nicht noch einmal brechen kann. 

Mallocing ein letztes Mal, Nummer 5. All die Art und Weise zurück, kommen auf Sie. Es ist sehr aufregend. [Applaus] Wie ist dein Name? >> Ron. Ron, okay, Sie sind als Nummer 5 malloced. Wir haben gerade Code ausgeführt, das ist fast identisch mit dieser mit nur einem anderen Namen. Excellent. Nun, das Einfügen Anita, good luck Nummer 5 in der Liste jetzt. Gut, und? Excellent, so ist dies wirklich der dritte von drei gesamten Fälle. Wir mussten erst jemanden am Ende, Rebecca. Wir hatten dann jemand in der Mitte. Jetzt haben wir jemanden am Anfang, und in diesem Beispiel, Wir mussten nun Lucas zum ersten Mal aktualisieren, weil das erste Element in der Liste hat nun zu einer neuen Knotenpunkt, , die wiederum, wird am Knoten Zahl 9 zeigt. 

Dies war eine äusserst unangenehme Demonstration, ich bin mir sicher, so ein großer Applaus für diese Jungs, wenn du könntest. Schön gemacht. Das ist alles. Sie können Ihre Stücke von Papier als kleine Erinnerung behalten. Es stellt sich heraus, dass dies zu tun im Code ist nicht ganz so einfach wie nur bewegte die Hände um und zeigte Zeigern an verschiedene Dinge. Aber klar, dass, wenn es an der Zeit, so etwas wie umsetzen kommt eine verkettete Liste oder eine Variante davon, wenn Sie wirklich konzentrieren diese wesentlichen Grundlagen, die mundgerechte Probleme habe ich, um herauszufinden, ist es diese Hand oder diese Hand, dass das, was nichts anderes ist ein ziemlich komplexes Programm können, in der Tat, recht einfache Bausteine ​​wie diese reduziert werden. 

Lassen Sie uns die Dinge in einem anspruchsvolleren Richtung noch. Wir haben jetzt den Begriff der verketteten Liste. Wir haben auch-dank der Anregung wieder dort-eine doppelt verknüpfte Liste, das sieht fast die gleiche, aber jetzt haben wir zwei Zeiger innerhalb des struct statt einer, und wir konnten wohl nennen diese Pointer vorherigen und nächsten oder nach links oder rechts, aber wir wissen, in der Tat, müssen zwei von ihnen. Der Code wäre ein wenig komplizierter. Anita hätte mehr Arbeit hier zu tun auf der Bühne haben. Aber wir könnten sicherlich umsetzen, diese Art von Struktur. In Bezug auf die Laufzeit, aber was wäre die Laufzeit sein für Anita des Findens einer Zahl n in einer verketteten Liste jetzt? Immer noch groß O von n, so ist es nicht besser als lineare Suche. Wir können nicht binäre Suche, aber wieder. Warum war das so? Sie können nicht springen. Auch wenn wir natürlich sehen alle Menschen auf der Bühne, und Anita hätte eyeballed es und sagte: "Hier ist die Mitte der Liste" sie würden nicht wissen, dass, wenn sie das Computerprogramm waren denn das einzige, was sie mußte Verriegelung an der zu Beginn des Szenarios war Lucas, der als erster Zeiger war. Sie würde unbedingt diesen Links folgen, Zählen ihren Weg, bis sie etwa in der Mitte gefunden, und selbst dann ist sie nicht wissen, wann sie in die Mitte gekommen ist es sei denn, sie geht den ganzen Weg bis zum Ende, um herauszufinden, wie viele es sind, dann backtracks, und das auch schwierig wäre, es sei denn man musste eine doppelt verknüpfte Liste einiger sortieren. 

Lösung einiger Probleme heute, aber die Einführung anderer. Was ist eine andere Datenstruktur insgesamt? Dieses ist eine Fotografie der Tabletts in Mather House, und in diesem Fall haben wir eine Datenstruktur wir auch irgendwie schon gesprochen haben. Wir sprach von einem Stapel in dem Kontext-Speicher, und das ist eine Art absichtlich genannt, weil ein Stapel in den Begriffen der Erinnerung ist tatsächlich eine Datenstruktur, die mehr und mehr Zeug oben drauf geschichtet hat. Aber das Interessante an einem Stapel, wie es der Fall in der Realität ist, dass es eine besondere Art von Datenstruktur ist. Es ist eine Datenstruktur, wobei das erste Element in das letzte Element heraus. Wenn Sie das erste Tablett auf den Stapel gelegt werden, wirst du leider das letzte Fach ausgeschaltet werden die Stapel entnommen, und das ist nicht unbedingt eine gute Sache. Umgekehrt kann man darüber anders herum denken, die letzte in der erste Ort. 

Nun, alle Szenarien in den Sinn kommen, wo mit einem Stapel Datenstruktur, wo Sie diese Eigenschaft der last in, first out, ist tatsächlich überzeugend? Ist das eine gute Sache? Ist das eine schlechte Sache? Es ist definitiv eine schlechte Sache, wenn die Tabletts waren nicht alle gleich und sie waren alle Sonderangebote verschiedenen Farben oder Dingsbums, und die Farbe, die Sie wollen, ist den ganzen Weg nach unten. Natürlich können Sie nicht bekommen, dass ohne großen Aufwand. Du musst von oben beginnen und arbeiten Sie Ihren Weg nach unten. Ebenso, was wenn du einer dieser Fan Jungen Wer wartet die ganze Nacht versucht, eine iPhone und Linien aufstehen an einem Ort wie diesem? Wäre es nicht schön, wenn der Apple Store waren ein Stapel Datenstruktur? Yay? Nay? Es ist nur gut für die Menschen, die zeigen an der letzten möglichen Minute und dann ab zu bekommen die Warteschlange gezupft. Und in der Tat, die Tatsache, dass ich so geneigt war zu sagen Warteschlange ist eigentlich im Einklang mit dem, was wir nennen diese Art von Datenstruktur, ein in der Wirklichkeit, wo die Reihenfolge nicht egal, und Sie wollen, dass die ersten ein, um das erste sein aus wenn auch nur aus Gründen der menschlichen Fairness. Wir verlangen im Allgemeinen, dass eine Warteschlange Datenstruktur. 

Es stellt sich heraus neben verkettete Listen, können wir anfangen, mit diesen gleichen grundlegenden Ideen und beginnen neue und verschiedene Arten von Lösungen für Probleme. Zum Beispiel werden im Fall von einem Stapel, könnten wir stellen eine Stapel mit einer Datenstruktur wie diese, würde ich vorschlagen. In diesem Fall habe ich eine Struktur deklariert, und ich habe innerhalb dieser Struktur der ein Array von Zahlen und dann eine Variable Größe, und ich werde zu nennen dieses Ding einen Stapel. Nun, warum das eigentlich? Im Fall von einem Stapel, diese könnte I effektiv auf dem Bildschirm als ein Array zu ziehen. Hier ist mein Stack. Das sind meine Zahlen. Und wir werden sie als zu ziehen, diese, diese, diese, diese. Und dann habe ich einige andere Daten Mitglied hier, man nennt Größe, so ist dies Größe, und dies ist Zahlen, und kollektiv, stellt das ganze iPad hier ein Stack-Struktur. Nun, standardmäßig hat Größe vermutlich habe auf 0 initialisiert werden, und was innerhalb des Arrays von Zahlen zunächst als ich das erste Zuweisung eines Arrays? Garbage. Wer weiß? Und es spielt eigentlich keine Rolle. Es spielt keine Rolle, wenn diese 1, 2, 3, 4, 5 ist, völlig zufällig vom Pech in meiner Struktur gespeichert, weil so lange ich weiß, dass die Größe des Stapels 0 ist, dann weiß ich, programmatisch, nicht an einem der Elemente im Array. Es spielt keine Rolle, was da ist. Nicht auf sie schauen, wie die Implikation einer Größe von 0 wäre. 

Aber angenommen ich jetzt gehen Sie vor und legen Sie etwas in den Stapel. Ich möchte die Nummer 5 eingefügt, so dass ich Nummer 5 hier und was dann stelle ich hier unten? Jetzt würde ich tatsächlich legte um 1 für die Größe, und nun der Stapel der Größe 1. Was passiert, wenn ich weiter und gehe die Nummer, sagen wir mal, 7 next? Dieser erhält dann auf 2 aktualisiert, und dann werden wir 9 zu tun, und dann diese wird bis 3 aktualisiert. Aber die interessante Feature jetzt dieses Stapels ist, dass Ich soll, welches Element entfernen, wenn ich Pop will etwas abseits des Stapels, so zu sprechen? 9 wäre die erste Sache zu gehen. Wie soll das Bild ändern, wenn ich ein Element aus dem Stapel Pop möchten, Ähnlich wie bei einem Tablett in Mather? Yeah. >> [Student] Set Größe 2. Genau, ist alles, was ich zu tun Größe auf 2 gesetzt, und was mache ich mit dem Array zu tun? Ich glaube nicht, nichts zu tun. Ich konnte, nur um anal, ein 0 gibt oder eine -1 oder etwas zu bedeuten dass dies nicht ein legitimes Wert, aber es spielt keine Rolle, weil Ich kann außerhalb der Array selbst, wie lange es aufzeichnen so dass ich weiß, nur an den ersten beiden Elemente in diesem Array. Nun, wenn ich hingehe und fügen Sie die Nummer 8 auf dieses Array, wie kommt das Bild zu ändern als nächstes? Dies wird 8, und dies wird zu 3. Ich schneide ein paar Ecken hier. Jetzt haben wir 5, 7, 8, und wir sind wieder zu einer Größe von 3. Das ist ziemlich einfach zu implementieren, aber wann werden wir diese Design-Entscheidung bereuen? Wenn die Dinge beginnen, gehen sehr, sehr falsch? Yeah. [Unverständlich Studenten Antwort] Wenn Sie möchten, gehen Sie zurück und bekommen das erste Element Sie setzen in. 

Es stellt sich heraus hier, obwohl ein Stapel ist ein Array unter der Haube, diese Datenstrukturen begannen wir reden haben werden allgemein auch bekannt als abstrakten Datenstrukturen, wobei wie sie implementiert sind ist völlig neben der Punkt. Eine Datenstruktur wie ein Stapel soll Unterstützung hinzufügen Operationen wie Push, die ein Tablett auf den Stapel drückt, und Pop, die ein Element entfernt vom Stapel, und das ist es. Wenn Sie wurden zu fremden Code, die bereits umgesetzt downloaden dieses Ding namens einen Stapel, würde diese Person geschrieben haben nur zwei Funktionen für Sie, Push und Pop, deren einziger Zweck im Leben wäre genau das tun. Sie oder ihn oder sie, die dieses Programm umgesetzt wäre ganz die man sich entscheiden, wie die Umsetzung haben die Semantik von Schieben und knallen unter der Haube oder die Funktionalität von Schieben und knallen. Und ich habe eine etwas kurzsichtige Entscheidung getroffen hier durch die Implementierung meinen Stack mit dieser einfachen Datenstruktur warum? Wann diese Datenstruktur Pause? An welchem ​​Punkt muss ich einen Fehler zurück, wenn der Benutzer ruft Push, zum Beispiel? [Student] Wenn es keinen Platz mehr. Genau, wenn es keinen Platz mehr, wenn ich Kapazität überschritten, was alle Kappen, weil er suggeriert, dass es irgendeine Art von globalen Konstante ist. Na, dann bin ich nur gehen zu müssen, sagen: "Sorry, ich kann nicht schieben einen anderen Wert auf den Stapel, "viel in Mather möchten. 

An einem gewissen Punkt, sie gehen, um den oberen Teil des kleinen Gehäuses getroffen. Es ist kein Platz mehr oder Kapazität im Stapel, an welchem ​​Punkt gibt es irgendeine Art von Fehler. Sie haben, um das Element irgendwo gesagt, das Fach woanders, oder nirgends. Jetzt, mit einer Warteschlange, konnten wir umsetzen es ein wenig anders. Eine Warteschlange ist etwas anders, daß unterhalb der Haube, damit implementiert werden als ein Array, aber warum in diesem Fall schlage ich auch eine Kopf-Element, die die Spitze der Liste, die Front der Liste, die erste Person in der Schlange vor dem Apple Store, zusätzlich zu Größe? Warum brauche ich einen zusätzlichen Teil der Daten hier? Denken Sie zurück zu dem, was Zahlen wenn ich gezogen habe es wie folgt. Angenommen, diese nun ein Warteschlange anstelle von einem Stapel, Der Unterschied besteht darin, wie der Apple-Store-Warteschlange ist fair. Die erste Person in Zeile am Anfang der Liste, Nummer 5 in diesem Fall er oder sie wird in den Laden zuerst zu lassen. Lasst uns das tun. Angenommen, dass dies der Zustand meiner Warteschlange ist in diesem Moment in der Zeit, und jetzt der Apple-Store öffnet und die erste Person, die Zahl 5 wird in den Laden führte. Wie ändere ich das Bild jetzt, dass ich die erste Person, de-Warteschlange an der Vorderseite der Linie? Was ist das? >> [Student] Ändern Sie die Warteschlange. Ändern Sie den Kopf, so 5 verschwindet. In Wirklichkeit ist es, als ob-wie dies am besten tun? In Wirklichkeit ist es, als ob dieser Mann verschwindet. Was wäre Nummer 7 zu tun in einem tatsächlichen Geschäft? Sie würden einen großen Schritt nach vorne machen. 

Aber was haben wir zu schätzen wissen, wenn es um Arrays kommt und bewegliche Sachen herum? Das ist eine Art Verschwendung von Zeit, nicht wahr? Warum muss man so anal als die erste Person muss am Anfang der Zeile an physikalisch Beginn der Block arbeiten? Das ist völlig unnötig. Warum? Was könnte ich nur statt erinnern? >> [Unverständlich Studenten Antwort] Genau, konnte ich nur mit dieser zusätzlichen Daten Mitglied Kopf erinnern dass jetzt der Kopf der Liste ist nicht mehr 0, die sie vor einem Augenblick war. Nun, es ist eigentlich die Nummer 1. Auf diese Weise bekomme ich eine leichte Optimierung. Nur weil ich jemanden aus Zeile am Anfang der Zeile de-Warteschlange im Apple Store bedeutet nicht, jeder hat zu verschieben, was Rückruf ist eine lineare Operation. Ich kann anstatt verbringen konstanter Zeit nur und dann erreichen eine viel schnellere Reaktion. Aber der Preis, den ich zahle, was diese zusätzliche Leistung zu gewinnen und nicht mit jedem zu verlagern? Yeah. >> [Unverständlich Studenten Antwort] Kann mehr Menschen hinzu, gut, ist das Problem orthogonal auf die Tatsache, dass wir nicht verschieben Leute herum. Es ist immer noch ein Array, so, ob wir alle zu verschieben oder nicht- oh, ich sehe, was du meinst, okay. Eigentlich stimme ich mit dem, was du sagst, dass es fast, als ob es wir jetzt nie den Beginn dieses Array nicht mehr nutzen denn wenn ich 5 zu entfernen, dann entferne ich 7. Aber ich habe nur die Leute in der rechten Seite. 

Es fühlt sich an wie ich Platzverschwendung bin, und schließlich meiner Warteschlange zerfällt in gar nichts, so konnten wir nur noch Menschen wraparound, und wir konnten dieses Arrays wirklich als eine Art kreisförmige Struktur, aber wir nutzen, was Operator in C, diese Art von Rundum tun? [Unverständlich Student Response] >> Der Modulo-Operator. Es wäre ein wenig ärgerlich sein, zu durchdenken, wie beurteilen Sie die Rundum tun, aber wir konnten es tun, und wir könnten damit beginnen, die Menschen an, was verwendet werden, um die Vorderseite der Linie sein, aber wir mit diesem Kopf variable, wer der eigentliche Kopf der Linie tatsächlich erinnern. Was passiert, wenn stattdessen unser Ziel letztlich aber war die Suche nach Zahlen, wie wir es hier getan habe auf der Bühne mit Anita, aber wir wollen das Beste von all diesen Welten? Wir wollen mehr Raffinesse als Array erlaubt weil wir die Fähigkeit, dynamisch wachsen die Datenstruktur wollen. Aber wir wollen nicht zu haben, um etwas zu greifen, dass wir darauf hingewiesen in der ersten Vorlesung war nicht ein optimaler Algorithmus, dass der lineare Suche. Es stellt sich heraus, dass man in der Tat, zu erreichen oder zumindest konstante Zeit zu schließen, wodurch jemand wie Anita, wenn sie ihre Datenstruktur konfiguriert nicht eine verkettete Liste zu sein, nicht zu einem Stapel zu sein, nicht eine Schlange sein, könnte in der Tat, kommen mit einer Datenstruktur, die sie zum Nachschlagen Dinge ermöglicht, sogar Worte, nicht nur Zahlen, in dem, was wir nennen konstante Zeit. 

Und tatsächlich nach vorn schaut, ist eine der pset in dieser Klasse fast immer eine Implementierung einer Rechtschreibprüfung, wobei geben wir Ihnen wieder einige 150.000 englische Wörter und das Ziel ist, laden die in den Speicher und schnell in der Lage sein, Fragen der Form zu beantworten wird dieses Wort richtig geschrieben? Und es wäre wirklich saugen, wenn Sie durch alle 150.000 Wörter durchlaufen, um das zu beantworten hatte. Aber in der Tat, wir werden sehen, dass wir es in sehr, sehr schnellen Zeit zu tun. Und es geht um die Umsetzung einer so genannten Hash-Tabelle beinhalten, und obwohl auf den ersten Blick dieses Ding namens eine Hash-Tabelle ist zu gehen lassen Sie uns erreichen diese super schnelle Reaktionszeiten, es stellt sich heraus, dass es in der Tat ein Problem. Wenn es Zeit ist dieses Ding namens-again Umsetzung kommt, werde ich es wieder tun. Ich bin der einzige hier. Wenn es Zeit für die Umsetzung dieses Ding namens eine Hash-Tabelle, wir gehen zu müssen, eine Entscheidung zu treffen. Wie groß sollte das Ding eigentlich? Und wenn wir beginnen Einsetzen Zahlen in dieser Hash-Tabelle, wie werden wir sie in einer solchen Weise zu speichern dass wir sie wieder so schnell, wie wir sie haben in? Aber wir werden bald sehen, dass diese Frage wenn jeder Geburtstag in der Klasse wird ganz Germane. Es stellt sich heraus, dass in diesem Raum, wir haben ein paar hundert Menschen, so dass die Wahrscheinlichkeit, dass zwei von uns haben am gleichen Tag Geburtstag ist wohl ziemlich hoch. Was ist, wenn es nur 40 von uns in diesem Raum? Wie stehen die Chancen von zwei Menschen mit dem gleichen Geburtstag? [Studenten] Mehr als 50%. Ja, über 50%. In der Tat, ich brachte sogar ein Diagramm. Es stellt sich heraus, und das ist wirklich nur eine Vorschau- wenn es nur 58 von uns in diesem Raum, die Wahrscheinlichkeit von 2 of us mit dem gleichen Geburtstag ist enorm hoch, fast 100%, und das ist nun eine ganze Reihe von verletzten für uns am Mittwoch verursachen. 

Mit dieser sagte, lasst uns hier vertagen. Wir werden Sie am Mittwoch sehen. [Applaus] [CS50.TV]