DAVID MALAN: All right, willkommen zurück. Dies ist CS50. Dies ist der Beginn der Woche sieben. Also es ist schon eine Weile her, so dass ich dachte, wir würden nehmen eine rasante Tour, wo wir Aus-und links, wo wir gehen jetzt. 

Also diese Sache hier haben könnte verursachte etwas angst auf den ersten. Aber hoffentlich sind Sie zum Anfang akklimatisieren, was dies bedeutet hier - Sterne, die einen Zeiger, der ist genau das, was in mehr juristischer Hinsicht? Also ist es eine Adresse. 

So ist es die Adresse des etwas in Erinnerung. Und wir begannen zu schälen die Schichten ein paar Wochen, wie die Dinge GetString und andere solche Funktionen all dieser Zeit wurden wieder Adressen der Dinge in Erinnerung, wie die Adresse des ersten Zeichens in einige Sequenz. 

So führten wir auch valgrind, die Sie beginnen, für dieses Problem verwenden festzulegen, insbesondere für die nächste Problem eingestellt als gut. Und valgrind tut, was für uns? Es prüft, ob Speicherlecks, und es Außerdem prüft wegen Missbrauch der Erinnerung. 

Es kann mit einiger Wahrscheinlichkeit erkennen, ob Ihr Code wird Speicher berühren dass es einfach nicht tun sollten. Also nicht unbedingt ein Leck, aber wenn Sie geht über die Grenzen der einige Array und Sie tatsächlich ausführen valgrind und induzieren dieses Verhalten während valgrind wird in Ihrem Programm ausgeführt wird Laufen in der es, erhalten Sie Meldungen wie diese - "invalid schreiben von Größe 4 ", die erinnern ein paar Wochen gemeint, dass ich aus Versehen hatte mag auf der einen int zu weit über die Grenzen eines Arrays. Und so Größe 4 bedeutet hier die Größe des jeweiligen Int. 

So nehmen Beruhigung in der Tatsache, dass valgrind die Ausgabe, das Format ist, ist nur grauenhaft. Es ist wirklich schwer, durch das Durcheinander zu sehen für die interessanten Informationen. Also, was wir hier gemacht haben ist nur Auszug einige von den paar mehr interessante Linien. Aber klar, dass 80% der valgrind die Ausgang wird ein bisschen wie ein sein Ablenkung. 

Just for Muster wie diese aussehen - ungültig Recht, ungültig zu lesen, 40 Byte und eine Anzahl von Blöcken sind definitiv verloren, dass Schlüsselwörter wie. Und das, was Sie sehen, ist hoffentlich einige Art der Spur, welche Funktion die Fehler ist eigentlich in. In diesem Fall hier, in welcher Zeile mein Code war der Fehler offenbar? 

26 in einer Datei namens memory.c, das war das Beispiel haben wir mit dem Spielen wurden an der Zeit. So ist es wahrscheinlich nicht in malloc. Es war wohl in meinem Code statt. Also werden wir dies wieder zu sehen und schon bald wieder. 

So scanf, kam diese in ein paar Formen so weit. Wir sahen sscanf kurz. Es war etwas, eine Reihe von Sie tauchte in in Ihrem Vorbereitungen für das Quiz. Und scanf ist eigentlich das, was die CS50 Bibliothek unter die wurden mit Kapuze seit geraumer Zeit, um einer Eingabe durch den Benutzer zu erhalten. 

Zum Beispiel, wenn ich mich bewege über den CS50 Gerät hier, lass mich eröffnen ein Beispiel heute, die aufgerufen scanf-0.C ist Und es ist super einfach. Es ist nur ein paar Zeilen Code. Aber es zeigt wirklich, wie getInt gearbeitet hat, all dieser Zeit. 

In diesem Programm finden Sie hier, in Zeile 16 Beachten Sie, dass ich ein int deklarieren. Also keine Zeiger, nichts Magisches da, nur ein int. Dann in Zeile 17, die ich prompt Benutzer für eine Reihe, bitte. Dann Ende 18, ich benutze scanf hier. Und ich angegeben, der Art wie printf, Ich erwarte, dass Zitat unquote Prozent i. 

So Prozent i natürlich bezeichnet einen int. Aber bemerken, was die zweite Argument scanf ist. Wie würden Sie die zweite Argument nach dem Komma? Was ist das? 

Es ist die Adresse von x. So ist dies, weil durch die Bereitstellung nützlicher scanf mit der Adresse x, was bedeutet , die Lage versetzen, diese Funktion zu tun? Nicht nur dorthin zu gehen, sondern auch was zu tun? 

Nehmen Sie eine Änderung um sie. Weil du es gehen kann, ist es eine Art wie eine Karte zu einer Stelle in dem Speicher. Und so lange, wie Sie bieten scanf oder jede Funktion mit einer solchen Karte, dass Funktion kann es gehen, und nicht nur Blick auf den Wert, aber es kann auch Ändern Sie diesen Wert, das ist nützlich, wenn das Ziel im Leben ist es, von scanf Scannen Eingabe vom Benutzer, und zwar von der Tastatur. Und das f zeigt formatierte, genau wie printf bezeichnet das f eine formatierte Zeichenfolge, die Sie drucken möchten. 

Also kurz gesagt, diese Linie 18 sagt einfach, versuchen, eine int vom Benutzer gelesen Tastatur und speichern Sie es innerhalb von x, bei was passiert mit x-Adresse an leben. Und dann schließlich, Zeile 19 sagt nur, danke für den int, in diesem Fall. 

Also lassen Sie mich gehen Sie vor und machen diese. So machen scanf 0. Lassen Sie mich gehen Sie vor und Vergrößern klicken Ich werde gehen und laufen diese mit dots Schrägstrich scanf 0. Nummer, bitte? 50. Vielen Dank für die 50. So ist es ganz einfach. 

Nun, was ist es nicht zu tun? Es ist nicht zu tun eine ganze Reihe der Fehlerprüfung. Zum Beispiel, wenn ich nicht mit, und ich glaube nicht eine Zahl eingeben, aber stattdessen schreibe ich etwas wie "hallo" das ist nur irgendwie seltsam. Und so eines der Dinge, die CS50 Bibliothek wurde für uns zu tun für einige Zeit ist, dass reprompting und reprompting. 

Die Wiederholung Begriff Rückruf war in cs50.c, und das ist der Grund, dass in getInt der CS50-Bibliothek ist eigentlich eine ganze Bündel von Zeilen lang, weil wir Überprüfung für dumme Sachen wie diese. Hat der Benutzer nicht geben uns in der Tat, ein int? Hat er oder sie uns etwas geben wie ein alphabetischer Brief? Wenn ja, wollen wir erkennen dass und schreien sie an. 

Aber die Sache schon interessanter Im nächsten Beispiel. Wenn ich scanf-1.c gehen, ist was der eine Sache, die grundsätzlich in geändert wird Das nächste Beispiel? Ich bin mit char *, natürlich, anstelle von int. 

Also das ist interessant, weil char *, erinnern, ist wirklich nur die dasselbe wie String. So fühlt es sich wie vielleicht ein super ist einfache Implementierung GetString. Aber ich habe wieder die Schicht geschält des CS50-Bibliothek, also bin ich Aufruf dieser char * jetzt. Also mal sehen, wo, wenn irgendwo, wir schief gehen. 

Zeile 17 - Ich noch einmal sagen, bitte geben Sie mir etwas, in diesem Fall wird eine Zeichenfolge. Und dann in der nächsten Zeile, ich nenne scanf, wieder, die ihm einen Format-Code, aber diesmal Prozent s. Und dann ist diese Zeit, ich bin ihm Puffer. 

Jetzt bemerken, ich bin nicht mit das kaufmännische. Aber warum ist das wohl OK hier? Denn was ist schon Puffer? Es ist schon ein Zeiger. Es ist bereits eine Adresse. 

Und lassen Sie uns dieses Wort "verwirren", lassen Sie mich nennen es einfach s, z. B. für Einfachheit. Aber ich habe es nannte puffern, weil in Generell in der Programmierung, wenn Sie einen Teil des Speichers, die einen String wirklich gerade ist, könnten Sie nennen es einen Puffer. Es ist ein Ort, um Informationen zu speichern. 

Ähnliche Dinge wie YouTube, wenn sie Pufferung, so zu sprechen, dass bedeutet nur, es ist das Herunterladen von Bits das Internet und Speichern derselben in einem lokales Array, einem lokalen Teil des Speichers so dass man es später zu sehen, ohne Überspringen oder es hängen Sie während der Wiedergabe. 

So gibt es hier ein Problem, obwohl, weil ich sage scanf bin, erwarten eine String von dem Benutzer. Hier ist die Adresse von ein Teil des Speichers. Setzen Sie diese Zeichenfolge gibt. Warum ist das so gebundene geben uns Mühe, obwohl? 

Was ist das? Darf ich zugreifen dass ein Teil des Speichers? Weißt du, ich weiß nicht. Da hat Puffer initialisiert um nichts? Nicht wirklich. Und so ist es, was wir gefordert eine Garbage-Wert, der ist nicht eine formale Wort. Es bedeutet nur, wir haben keine Ahnung, was Bits sind innerhalb der vier Bytes, Ich habe als Puffer zugeordnet. 

Ich habe nicht angerufen malloc. Ich habe definitiv nicht genannt GetString. Also, wer weiß, was ist eigentlich Innenseite der Puffer? Und doch erzählen scanf blind, dorthin zu gehen und setzen, was der Benutzer eingegeben. 

Also, was ist zu veranlassen geeignet in unserem Code, wenn wir es laufen? Wahrscheinlich ein segfault. Vielleicht nicht, aber wahrscheinlich ein segfault. Und ich sage, vielleicht auch nicht, denn manchmal Sie tun, manchmal Sie erhalten keine segfault. Manchmal muss man einfach Glück haben, aber es dennoch sein wird ein Fehler in unserem Programm. 

Also lass mich gehen und diese kompilieren. Ich werde es tun, desto alten Schule. So clang dash 0, scanf-1, scanf-1.c, Enter. Hoppla, zu alten Schule. Mal sehen. Wo habe ich? Oh, char * buffer. Oh, danke - Speichern, OK - sehr alte Schule. Na gut, es ist schon eine Weile her. 

Also habe ich einfach die Datei nach gespeichert machen, dass temporäre vor einem Augenblick ändern. Und jetzt habe ich es kompiliert manuell mit Schall. Und jetzt gehe ich voran gehen und führen scanf-1, Enter. String bitte. Ich werde in Typ "hallo." 

Und jetzt ist hier, wo, ehrlich gesagt, printf kann, ist ein wenig ärgerlich. Es ist nicht eigentlich los Segfault in diesem Fall. Printf ist ein wenig speziell, weil es ist so super, dass häufig verwendete Wesentlichen printf tut uns einen Gefallen und Realisierung, das ist nicht ein gültiger Zeiger. Lassen Sie mich es auf mich nur zum Drucken in Klammern null, auch obwohl es nicht unbedingt das, was wir uns erwartet. 

So können wir nicht wirklich leicht zu induzieren ein segfault mit diesem, aber eindeutig das ist nicht das Verhalten, das ich wollte. Also, was ist die einfache Lösung? Nun, in scanf-2, lassen Sie mich schlagen vor, dass anstatt wirklich nur eine Zuteilung char *, lassen Sie mich ein wenig schlauer über dies, und lassen Sie mich zuteilen Puffer als eine Folge von 16 Zeichen. 

So kann ich diese in ein paar Möglichkeiten. Ich konnte absolut malloc verwenden. Aber ich kann zurück zu Woche zwei, wenn Ich brauchte nur eine ganze Reihe von Zeichen. Das ist nur ein Array. Also lassen Sie mich stattdessen neu Puffer ein Array von 16 Zeichen lang sein. 

Und jetzt, wo ich pass in Puffer - und dies ist etwas, was wir nicht sprechen in Woche zwei - aber Sie können ein Array als behandeln obwohl es eine Adresse. Technisch, wie wir gesehen haben, sind sie ein bisschen anders. Aber scanf nichts dagegen, wenn Sie es weitergeben der Name eines Arrays, weil das, was Schall wird für uns tun im Wesentlichen behandeln den Namen dieses Array als die Adresse des Brocken von 16 Bytes. 

Also das ist besser. Dies bedeutet nun, dass ich kann hoffentlich Gehen Sie wie folgt. Lassen Sie mich zu verkleinern und für einen Moment tun machen scanf-2, zusammengestellt OK. Lassen Sie mich nun zu tun Schrägstrich scanf-2. String bitte. "Hallo." Und es schien diese Zeit zu arbeiten. 

Aber kann jemand vorschlagen ein Szenario , in dem es nicht immer noch funktionieren? Ja? Etwas mehr als 16 Zeichen. Und tatsächlich, wir können etwas genauer. Etwas länger als 15 Zeichen, weil wir wirklich brauchen, um im Auge zu behalten die wir brauchen, dass Backslash Null implizit am Ende der Zeichenkette, Das ist nebenbei scanf wird in der Regel kümmern sich für uns. 

Also lassen Sie mich etwas tun - Manchmal können wir nur lassen Sie es so. OK, also haben wir jetzt induziert unsere Segmentation Fault. Warum? Da ich mehr als 15 eingegeben Zeichen, und so haben wir eigentlich Speicher berührt, dass ich eigentlich sollte nicht. 

Also, was ist wirklich die Lösung hier? Nun, was ist, wenn wir eine längere Schnur? Nun, wir machen es vielleicht 32 Byte. Nun, was ist, wenn das nicht lang genug? Wie wäre es mit 64 Bytes? Was ist, wenn das nicht lang genug? Wie wäre es mit 128 oder 200 Bytes? Was ist eigentlich die Lösung hier in der allgemeinen Fall, wenn wir nicht wissen, in voranzubringen, was der Benutzer geht zu schreiben? 

Es ist nur eine Art große Schmerzen in den Arsch, um ehrlich zu sein, weshalb die CS50-Bibliothek hat ein paar Dutzend Zeilen Code, der gemeinsam umsetzen GetString String in einer Weise, dass wir nicht müssen im Voraus wissen, was die Benutzer wird geben. Insbesondere, wenn man sich wieder an cs50.c von vor zwei Wochen, werden Sie sehen, dass GetString tatsächlich nicht verwenden scanf in dieser Weise. Vielmehr liest sie ein Zeichen zu einer Zeit. 

Da das eine nette Sache über Lesen eines Zeichens ist, können wir garantieren uns immer mindestens einen char. Ich kann nur erklären, ein char, und dann nehmen diese wirklich kleine Schritte nur lesen ein Zeichen auf eine Zeit von der Tastatur. Und dann, was Sie sehen GetString macht, ist jedes Mal läuft es aus, sagen, 16 Byte Speicher, verwendet es malloc oder ein Cousin davon, um mehr Speicher, das Kopieren der alten Speicher in den neuen und dann kriechen entlang, immer ein Zeichen in einer Zeit, und wenn es läuft aus, dass Teil des Speichers, wirft es weg, Greifer ein größerer Teil des Speichers, kopiert alt in neue und wiederholt. Und es ist wirklich ein Schmerz tatsächlich Umsetzung etwas so einfaches wie Erhalten einer Eingabe von einem Benutzer. 

So können Sie scanf. Sie können auch andere ähnliche Funktionen. Und eine Menge von Lehrbüchern und Online- Beispiele zu tun, aber sie sind alle anfällig für Probleme wie diese. Und letztlich immer ein segfault ist irgendwie nervig. Es ist nicht gut für den Anwender. 

Aber im schlimmsten Fall, was bedeutet es grundsätzlich setzen Sie Ihre Code in Gefahr? Irgendeine Art von Angriff, möglicherweise. Wir sprachen über einen solchen Angriff - Überlaufen des Stapels. Aber im Allgemeinen, wenn Sie zu erlaubt einen Pufferüberlauf, wie wir eine Vor einigen Wochen, mit nur schriftlich mehr als "Hallo" auf dem Stack, Sie kann in der Tat zu übernehmen, möglicherweise ein Computer, oder zumindest Daten zu erhalten, die nicht Ihnen gehören. 

Also kurz gesagt, das ist, warum wir diese Stützräder. Aber jetzt fangen wir an, sie abzunehmen, wie unsere Programme nicht mehr benötigen, notwendigerweise Eingabe von dem Benutzer. Aber im Fall von Problem stellte sechs, Ihre Eingaben werden aus einer riesigen kommen Wörterbuch-Datei mit 150 einige ungerade tausend Worte. 

Sie werden also nicht zu befürchten des Benutzers beliebigen Eingang. Wir geben Ihnen einige Annahmen über diese Datei. Irgendwelche Fragen zu Zeigern oder scanf oder Benutzereingaben im Allgemeinen? 

Alles klar, so ein kurzer Blick dann auf einen Hinterkante Thema aus vor zwei Wochen. Und das war diese Vorstellung von einer Struktur. Nicht, dass - diese Vorstellung von einem struct, das war was? Was hat struct für uns tun? 

Definieren - Entschuldigung? Definieren Sie eine Variable Typ. Also irgendwie. Wir sind tatsächlich die Kombination von zwei Themen. Also mit typedef, daran erinnern, dass wir können erklären, eine Art von unseren eigenen, wie ein Synonym für wie String char *. Aber mit typedef struct und können wir erstellen Sie wirklich unsere eigenen Datenstrukturen. 

Zum Beispiel, wenn ich zurück in gedit hier nur für einen Augenblick, und ich gehe voraus und etwas tun, lassen Sie mich zu retten dies als, sagen wir, structs.c vorübergehend, ich werde einfach gehen Sie vor und schließen standardio.h, int main nichtig. Und dann hier, nehme, was ich will um ein Programm, dass speichert schreiben mehrere Schüler aus verschiedenen Häuser, zum Beispiel. So ist es wie ein registrarial Datenbank einiger sortieren. 

Also, wenn ich den Namen ein Student braucht, ich könnte so etwas wie char * Namen zu tun, und ich werde etwas tun - tatsächlich, verwenden wir die CS50-Bibliothek nur für einen Augenblick, um diesen ein wenig einfacher, so können wir leihen jene Dutzende von Zeilen Code. Und lasst uns einfach keep it simple. Wir halten es string, und jetzt GetString. 

So behaupte ich jetzt, dass ich den Namen gespeichert von einigen Studenten, und das Haus einige Schüler, einfach mit Variablen wie wir und in der ersten Woche. Aber ich nehme jetzt unterstützen wollen mehrere Schüler. Alles klar, also meinen Instinkten zu tun String Name2, bekommt GetString, string house2 bekommt GetString. Und dann unsere dritte Student, lass es uns tun name3 GetString. 

Alles klar, so ist dies hoffentlich markante Sie als eine Art dumm, da dieser Prozess ist nie wirklich zu Ende gehen, und es ist gerade dabei, machen meinen Code schlechter aussehen und schlimmer und schlimmer. Aber wir lösen diese auch in Woche zwei. Was war unser relativ saubere Lösung wenn wir hatten mehrere Variablen des gleichen Datentyp, die alle miteinander verbunden sind, sondern wir nicht wollen, dass diese grausamen Chaos von ähnlich benannten Variablen? Was haben wir stattdessen? 

Also ich glaube, ich hörte ein paar Plätze. Wir hatten ein Array. Wenn Sie mehrere Instanzen von etwas, warum wir nicht alle diese reinigen und einfach sagen, gib mir Array namens Namen? 

Und jetzt, lasst uns hart Code 3. Und dann geben Sie mir ein weiteres Array Häuser genannt, und lassen Sie mich für jetzt schwer Code 3. Und ich habe massiv bis das gereinigte durcheinander, dass ich gerade erstellt haben. Nun, ich habe immer noch schwer 3 codiert, sondern sogar die 3 könnte dynamisch aus der kommen Benutzer oder argv oder dergleichen. Also das ist schon sauberer. 

Aber was ist ärgerlich daran ist, dass jetzt ist, obwohl ein Name irgendwie grundsätzlich verknüpft eines Schülers Haus - es ist ein Student, dass ich wirklich darstellen wollen - Ich habe jetzt zwei Arrays, die parallel sind in dem Sinne, dass sie das sind gleiche Größe und Namen Klammer 0 Karten vermutlich um Häuser Halterung 0, und Namen Halterung 1 Karten um Häuser Halterung 1. In anderen Worten, lebt, dass Schüler in das Haus, und dass andere Schüler Leben im anderen Haus. Aber sicherlich könnte dies getan noch sauber. 

Nun, es kann, in der Tat. Und lassen Sie mich gehen Sie vor und öffnen bis structs.h, und du wirst sehen diese Idee hier. Beachten Sie, dass ich verwendet habe, typedef, wie Sie angespielt einen Moment vor, zu erklären, unsere eigenen Datentyp. Aber ich bin auch mit diesen anderen Stichwort genannt struct was gibt mir eine neue Datenstruktur. 

Und diese Datenstruktur Ich behaupte, wird auf zwei Dinge in haben es - ein String namens name, und eine Zeichenfolge namens Haus. Und der Name Ich werde zu geben Diese Datenstruktur wird genannt Schüler werden. Ich könnte es, was ich will, aber diese semantisch machen Sinn für mich in meinem Kopf. 

So, jetzt, wenn ich eröffnen eine bessere Version des Programms begann ich gibt, lassen Sie mich nach oben scrollen. Und es gibt einige weitere Zeilen Code hier, aber lassen Sie mich zu konzentrieren für der Moment, auf einem. Ich habe ein konstanter genannte Schüler erklärt und hart 3 jetzt codiert. Aber jetzt, bemerken, wie sauber mein Code beginnt zu bekommen. 

In Zeile 22, erkläre ich Array von Studenten. Und feststellen, dass Schüler offenbar Jetzt ein Datentyp. Denn am Anfang der Datei, bemerken Ich habe diesen Header-Datei enthalten dass ich zog nur einen Augenblick vor. Und dass die Header-Datei ganz einfach hatte diese Definition eines Schülers. 

So jetzt habe ich meine eigene benutzerdefinierte Daten erstellt Art, dass die Autoren von C Jahren Vor nicht von im Voraus zu denken. Aber kein Problem. Ich kann es mir. Das ist also ein Array namens Studenten, jeweils aus Mitgliedern ist ein Student Struktur. Und ich möchte drei davon in dem Array. 

Und nun, was macht der Rest dieses Programm? Ich brauchte etwas, ein wenig willkürlich. Also von Online 24 vorwärts, I von 0 bis 3 zu durchlaufen. Dann frage ich den Benutzer zur den Namen des Studenten. Und dann benutze ich nach wie vor GetString. Dann frage ich für die Schüler das Haus, und ich verwende GetString wie zuvor. 

Aber beachten Sie - etwas neues Stück Syntax - Ich kann mich noch an den Index i-ten Studenten, aber wie kann ich die Daten bekommen Feld innerhalb der Struktur? Nun, was ist offenbar die neues Stück Syntax? Es ist nur der Punkt-Operator. 

Wir haben nicht wirklich schon einmal gesehen. Sie haben es in fünf pset gesehen haben, wenn Sie tauchte bereits mit Bitmap-Dateien. Aber der Punkt bedeutet nur innerhalb dieses struct oder mehrere Felder, geben dot Namen, oder geben Sie mir dot Haus. Das bedeutet, gehen innerhalb der Struktur und bekommen diese speziellen Bereichen. 

Was macht der Rest dieses Programm? Es ist gar nicht so sexy. Beachten Sie, dass ich 0-3 wieder durchlaufen, und ich erstellen Sie einfach eine englische Phrase wie so und so ist in solchen und wie ein Haus, vorbei an dot Namen die i-te und die Schüler Haus auch. 

Und dann endlich, jetzt werden wir beginnen, um anal darüber, jetzt, wo wir sind vertraut mit dem, was malloc-und andere Funktionen haben die ganze Zeit getan. Warum muss ich sowohl Name befreien und Haus, obwohl ich nicht nennen malloc? 

GetString tat. Und das war das schmutzige kleine Geheimnis für mehrere Wochen, aber GetString hat wurde undicht Speicher der ganzen Legen Sie alle Semester so weit. Und Valgrand endlich zeigen uns dies. 

Aber es ist keine große Sache, weil ich weiß, dass ich einfach befreien den Namen und das Haus, obwohl technisch auf sein super, super sicher, sollte ich dabei einige Fehlerprüfung hier. Was sind Ihre Instinkte sagen Sie? Was soll ich werden überprüft bevor ich zu befreien, was ist ein String, aka die ein char *? 

Ich sollte wirklich prüfen, ob Studenten Halterung i dot Name nicht gleich null. Dann wird es bald auf OK, um voran zu gehen und kostenlos daß Zeiger und gleichen oder andere man als gut. Wenn die Schüler Halterung i dot Haus ist nicht gleich null, wird dies jetzt schützen gegen die Ecke Fall, in dem GetString kehrt so etwas wie null. Und wir sahen einen Moment vor, printf wird schützen uns bis hier nur sagen, null ist, wird die gut aussehen seltsam. Aber zumindest wird es nicht segfault, wie wir gesehen haben. 

Nun, lassen Sie mich noch eine andere Sache hier. Strukturen-0 ist eine Art dumm Programm geben, weil ich all diese Daten, und dann es ist verloren, sobald das Programm beendet. Aber lassen Sie mich gehen Sie vor und tun dies. Lassen Sie mich das Terminal Fenster ein bisschen größer. Lassen Sie mich Strukturen-1, die ist eine neue Version davon. 

Ich werde in ein wenig vergrößern. Und jetzt lassen Sie mich laufen dot Schrägstrich Strukturen-1. Student-Namen - David Mather, lass es uns tun Rob Kirkland, lass es uns tun Lauren Leverett. Was interessant ist jetzt Aufträge - und ich weiß nur, weil dieses Ich schrieb das Programm - gibt es eine Datei jetzt auf meinem aktuellen Verzeichnis namens students.csv. Einige von euch haben vielleicht gesehen haben diese in der realen Welt. 

Was ist eine CSV-Datei? Werte durch Komma getrennt. Es ist wie eine Art des armen Mannes Version einer Excel-Datei. Es folgt eine Tabelle mit Zeilen und Spalten, Sie können in einem Programm wie Excel zu öffnen, oder Zahlen auf einem Mac. 

Und wenn ich diese Datei öffnen hier auf gedit, Bekanntmachung - und die Zahlen sind nicht da. Das ist nur gedit erzählen mich Zeilennummern. Hinweis auf der ersten Zeile des Datei ist David und Mather. Die nächste Zeile ist Rob Komma Kirkland. Und die dritte Zeile ist Lauren Komma Leverett. 

So was habe ich geschaffen? Ich habe jetzt ein C-Programm geschrieben, dass effektiv erzeugen kann Kalkulationstabellen das kann in eine geöffnet werden Programm wie Excel. Nicht alles, was zwingend ein Datensatz, aber wenn Sie haben viel größere Brocken Daten, die Sie wirklich wollen, manipulieren und machen Graphen und die möchten, ist dies vielleicht eine Möglichkeit, diese Daten zu erstellen. Darüber hinaus sind CSVs eigentlich Super gemeinsamen nur für die Speicherung von einfachen Daten - Yahoo Finance, zum Beispiel, wenn man Börsenkurse über ihre sogenannten API, der kostenlose Service, mit dem Sie bekommen aktuellen up-to-the-date Lager Angebote für Unternehmen, sie geben die Daten wieder in der super einfach CSV-Format. 

Und wie haben wir das tun? Nun bemerken, die meisten von diesem Programm fast die gleichen. Aber beachten Sie hier unten, anstatt Druck die Schüler heraus, on line 35 weiter, behaupte ich, dass ich die Sparquote der Studenten auf der Festplatte, so das Speichern einer Datei. 

So stelle ich mir die Vereinbarkeit eines FILE * - Jetzt ist diese Art einer Anomalie in C. Aus welchem ​​Grund, ist FILE alle Kappen, Das ist nicht wie die meisten anderen Datentypen in C. Aber dies ist eine integrierte Datentyp FILE *. Und ich erklärte einen Zeiger auf eine Datei, So können Sie von zu denken. 

fopen bedeutet geöffnete Datei. Welche Datei müssen Sie öffnen möchten? Ich möchte eine Datei zu öffnen, dass ich will willkürlich nennen students.csv. Ich nennen könnte, dass alles, was ich will. 

Und dann nehmen Sie eine Vermutung. Was das zweite Argument zu fopen wahrscheinlich bedeuten? Richtig, w für Schreiben, konnte r sein für gelesen. Es gibt eine für append, wenn Sie Zeilen und wollen nicht hinzufügen überschreiben die ganze Sache. 

Aber ich will einfach nur diese Datei zu erstellen einmal, also werde ich verwenden Zitat unquote w. Und ich weiß, dass nur aus gelesen zu haben die Dokumentation oder die man-Seite. Wenn die Datei nicht null ist - in anderen Worten, wenn nichts schief gelaufen ist da - lassen Sie mich über die durchlaufen Schüler 0-3. 

Und nun feststellen, es ist etwas, immer so leicht unterschiedliche um die Linie 41 hier. Es ist nicht printf. Es ist für fprintf Datei printf. Also es geht um die Datei schreiben. Welche Datei? Derjenige, dessen Zeiger Sie angeben als erstes Argument. 

Dann geben wir einen Format-String. Dann werden wir festlegen, was wir wollen String Plug-in für das erste Prozent s, und dann eine andere Variable oder das zweite s Prozent. Dann schließen wir die Datei mit fclose. Als ich den Speicher frei wie zuvor, obwohl Ich sollte gehen wieder an und fügen einige Prüfungen für null. 

Und das ist es. fopen, fprintf, gibt mir das fclose Fähigkeit, Text-Dateien zu erstellen. Nun, werden Sie in Problem-Set fünf sehen Bilder, die beinhaltet, werden Sie mit Binär-Dateien statt. Aber im Grunde ist die Idee, die gleiche, obwohl die Funktionen, die Sie werde sehen, sind ein bisschen anders. 

So rasante Tour, aber Sie erhalten nur allzu vertraut mit Datei I/O-- Eingang und Ausgang - mit pset fünf. Und Fragen zu den ersten Grundlagen hier? Ja? 

Was, wenn Sie einen Nullwert kostenlos ausprobieren? Ich glaube, es sei denn, ein frei bekommen hat wenig mehr benutzerfreundlich, können Sie potenziell segfault. Vorbei ist es null ist schlecht, weil ich nicht glauben frei stört, für Sie zu überprüfen, denn es wäre möglicherweise eine Verschwendung Zeit für ihn, sich für tun jeder in der Welt. Gute Frage, though. 

Alles klar, so bekommt diese Art von uns zu einem interessanten Thema. Das Thema Problem Set fünf ist Forensik. Mindestens das ist ein Teil des Problems Satz. Forensics Regel bezieht sich auf die Verwertung von Informationen, die kann oder kann nicht gelöscht wurden bewusst. Und so dachte ich, ich geben Ihnen einen schnellen Vorgeschmack darauf, was wirklich vor sich geht alle diesmal unter der Motorhaube Ihres Computers. 

Zum Beispiel, wenn Sie in Ihrer Laptop oder Ihren Desktop-Computer ein Festplatte, ist es entweder ein mechanisches Gerät, das tatsächlich dreht - es gibt Dinge genannt kreisförmigen Platten Dieser Blick ganz gerne, was ich hatte gerade auf dem Bildschirm hier, obwohl Dies ist zunehmend der alten Schule. Dies ist ein Drei-and-a-half-inch Festplatte. Und dreieinhalb Zoll bezieht sich der mit der Sache, wenn Sie es installieren in einem Computer. 

Viele von euch in Ihrer Laptops jetzt haben Solid-State-Laufwerke oder SSDs die haben keine beweglichen Teile. Sie sind eher wie RAM und weniger wie Diese mechanischen Vorrichtungen. Aber die Ideen sind immer noch die gleichen, sicherlich als sie sich beziehen, zum Problem stellte fünf. 

Und wenn Sie darüber nachdenken, jetzt eine Festplatte wesen stellt einen Kreis, der Ich werde wie diese hier zu ziehen. Wenn Sie eine Datei auf Ihrem Computer, ob es sich um eine SSD, oder in In diesem Fall eine ältere Schule Festplatte, diese Datei enthält mehrere Bits. Lassen Sie uns sagen, dass es diese 0 und 1 ist, eine ganze Reihe von 0 und 1. Also das ist meine ganze Festplatte. Dies ist offenbar eine ziemlich große Datei. Und es ist mit den 0 und 1 an, dass Teil der physischen Platte. 

Nun, was ist, dass körperliche Teil? Nun stellt sich heraus, dass auf einer Festplatte, mindestens dieser Art gibt es diese winzige magnetische Partikel. Und sie haben im Wesentlichen nördlich und Südpol zu ihnen, so dass, wenn Sie wiederum eine jener magnetischen Teilchen auf diese Weise könnte man sagen, dass es 1, die eine. Und wenn es den Kopf nach Süden bis Norden, könnte man sagen, dass es ist repräsentiert eine 0 ein. 

So in der realen physischen Welt, das ist wie man etwas in repräsentieren binären Zustand der 0 und a 1. Also das ist alles eine Datei ist. Es gibt eine ganze Reihe von magnetischen Partikel, die ihre so oder sind Auf diese Weise Schaffung von Mustern von 0 und 1. 

Aber es stellt sich heraus, wenn Sie eine Datei speichern, einige Informationen wird separat gespeichert. Also das ist ein kleiner Tisch, ein Verzeichnis, so zu sprechen. Und ich rufe diese Spalte Name, und Ich rufe diese Spalte Lage. 

Und ich werde sagen, nehme dies ist mein Lebenslauf. Meine resume.doc an gespeicherten Lage, sagen wir 123. Ich habe immer für diese Zahl zu gehen. Aber es genügt zu sagen, dass genau wie im RAM, können Sie eine Festplatte Das ist ein Gigabyte oder 200 Gigabyte oder ein Terabyte, und Sie können Anzahl alle Bytes. Sie können Nummer alle Stücke von 8 Bit. 

Also werden wir sagen, dass diese ist die Lage 123. Also das Verzeichnis innerhalb von meinem Betriebssystem System merkt, dass mein Lebenslauf ist an der Stelle 123. Aber es wird interessant, wenn Sie eine Datei löschen. 

So zum Beispiel - und Gott sei Dank, hat die meisten der Welt gefangen auf diese - was passiert, wenn Sie ziehen eine Datei auf Ihren Mac OS Trash oder Ihr Windows-Papierkorb? Was ist der Zweck, das zu tun? Es ist offensichtlich, um loszuwerden, der Datei, aber was bedeutet der Akt der Drag-and- Drop in den Papierkorb oder Ihr Papierkorbs auf einem Computer zu tun? 

Absolut nichts, wirklich. Es ist wie ein Ordner. Es ist ein spezieller Ordner, um sicher zu sein. Aber ist es tatsächlich die Datei löschen? 

Nun, nein, weil einige von Ihnen wahrscheinlich wie gewesen, oh verdammt, hast du nicht bedeutet, das zu tun. So können Sie einen Doppelklick auf das Trash oder Papierkorb. Sie haben rund um stocherte und Sie haben gewonnen die Datei einfach per Drag es raus. So klar, es ist nicht unbedingt löschen. 

OK, du bist schlauer. Sie wissen, dass gerade bewegen indem sie sie in die Trash oder Papierkorb bedeutet nicht, Sie Leeren des Papierkorbs. So können Sie bis zum Menü, und Sie sagen, Empty Trash oder Papierkorb leeren. Und was passiert dann? 

Ja, so ist es um so mehr gelöscht. Aber alles, was geschieht, ist dies. Der Computer vergisst, wo resume.doc war. 

Aber was sich nicht geändert hat offenbar auf dem Bild? Die Bits sind die 0 und 1, dass ich behaupten vor Ort von einigen physischen Aspekt des die Hardware. Sie sind immer noch da. Es ist nur der Computer vergessen, was sie sind. 

So ist es im wesentlichen befreit die Datei Bits, so dass sie wiederverwendet werden können. Aber erst, wenn man mehrere Dateien zu erstellen, und mehr Dateien und mehr Dateien werden probabilistisch, die 0 und 1, diese magnetischen Teilchen, wiederverwendet zu werden, Kopf oder rechten Seite nach oben, für andere Dateien, 0s und 1s. 

So haben Sie dieses Zeitfenster. Und es ist nicht vorhersehbarer Länge, wirklich. Es hängt von der Größe Ihrer Festplatte Antrieb und wie viele Dateien Sie haben und wie schnell Sie neue Kontakte zu knüpfen. Aber es ist das Zeitfenster, in welche die Datei ist immer noch perfekt erstattungsfähig. 

Also, wenn Sie jemals verwenden Programme wie McAfee Norton oder zu versuchen sich zu erholen Daten, wird alles, was sie tun versuchen, erholen dieses sogenannten Verzeichnis herauszufinden, wo Sie Ihre Datei war. Und manchmal Norton und wird sagen: Datei beträgt 93% erstattungsfähig. Nun, was bedeutet das? Das bedeutet nur, dass eine andere Datei zufällig unter Verwendung endete, sagen wir, diese Bits aus Ihrer ursprünglichen Datei. 

Also, was ist eigentlich beteiligt in die Wiederherstellung von Daten? Nun, wenn Sie nicht so etwas wie Norton auf Ihrem Computer vorinstalliert, das Beste was Sie tun können, ist manchmal aussehen auf die gesamte Festplatte auf der Suche nach Muster von Bits. Und eines der Themen von Problem-Set fünf ist, dass Sie die Suche Äquivalent einer Festplatte, einem forensischen Bild von einer Compact-Flash-Karte von einem Digitalkamera, die Suche nach dem 0s 1s und dass in der Regel mit hohen Wahrscheinlichkeit, stellen die Starten eines JPEG-Bildes. 

Und euch kann diese Bilder durch erholen vorausgesetzt, wenn ich dieses Muster der zu sehen Bits auf der forensischen mit hohe Wahrscheinlichkeit, die markiert der Beginn einer JPEG. Und wenn ich sehe, das gleiche Muster wieder, das wahrscheinlich markiert den Beginn der JPEG andere und ein anderes JPEG, JPEG und andere. Und dies ist in der Regel, wie Datenrettung funktioniert. Was ist schön zu JPEGs ist, obwohl das Dateiformat selbst ist etwas Komplex, der zu Beginn eines jeden solchen Datei ist eigentlich ziemlich identifizierbaren und einfach, wie Sie sehen werden, wenn Sie nicht bereits haben. 

Werfen wir also einen genaueren Blick unter die Haube, um genau das, was gewesen ist los ist, und was diese 0 und 1 sind, um Ihnen ein bisschen mehr von einem Rahmen für dieses besondere Herausforderung. 

[VIDEO PLAYBACK] 

-Wo ist Ihr PC speichert die meisten seiner permanenten Daten. Um dies zu erreichen, bewegt sich die Daten aus dem RAM zusammen mit Software-Signale, die sagen, die Festplatte, wie diese Daten zu speichern. Die Festplatte Schaltungen übersetzen diese Signale in Spannungssignale Schwankungen. Diese wiederum kontrollieren die Festplatte bewegliche Teile, einige der wenigen beweglichen Teile in der linken modernen Computer. 

Einige der Steuersignale einen Motor die spinnt Metall beschichteten Platten. Ihre Daten tatsächlich gespeichert auf diesen Platten. Andere Signale bewegen die Lese / Schreib- Köpfen zu lesen oder Schreiben von Daten auf den Platten. Diese Maschinen so präzise, ​​dass ein Mensch Haar konnte nicht einmal zwischen den Pass Köpfe und Spinnen Platten. Doch es funktioniert alles mit ungeheurer Geschwindigkeit. 

[END VIDEO PLAYBACK] 

DAVID MALAN: Zoom in einem kleinen tiefer jetzt an, was tatsächlich auf diesen Platten. 

[VIDEO PLAYBACK] 

-Lassen Sie uns, was wir gerade sah in Zeitlupe. Wenn eine kurze Stromimpuls ist an den Schreib / Lese-Kopf, wenn Flips auf einem winzigen elektromagnetischen für ein Bruchteil einer Sekunde. Der Magnet erzeugt ein Feld, das ändert sich die Polarität eines winzig kleinen Teil der Metall-Teilchen, Mantel jeden Plattenteller Oberfläche. 

Ein Muster dieser Serie winzige, aufgeladenen Bereichen auf dem Speicherplatten ein einzelnes Bit Daten in der Binärzahl System von Computern verwendet. Nun, wenn der Strom einen Weg geschickt durch den Lese / Schreib-Kopf, den Bereich ist in einer Richtung polarisiert. Wenn der Strom in die gesendete entgegengesetzte Richtung, die Polarisation umgekehrt wird. 

Wie Sie Daten von der Festplatte zu bekommen? Nur den Prozess umzukehren. So ist es die Partikel auf der Platte das bekommen den Strom in der Lese / Schreib-Kopf zu bewegen. Stellen Sie sich diese Millionen von magnetisierten Segmenten und Sie haben eine Datei. 

Nun kann die Stücke aus einer einzigen Datei alle über einen Laufwerks gestreut werden Platten, ein bisschen wie das Chaos Papiere auf Ihrem Schreibtisch. So ein besonderes Extra Datei verfolgt von wo alles ist. Weißt du nicht wünschte, Sie hätten so etwas? 

[END VIDEO PLAYBACK] 

DAVID MALAN: OK, wahrscheinlich nicht. So wie viele von euch wuchs mit diesen? OK, es ist also immer weniger Hände jedes Jahr. Aber ich bin froh, dass du wenigstens vertraut mit ihnen, weil diese und unsere eigenen Buch Demo leider sterben einen sehr langsamen Tod hier der Vertrautheit. 

Aber das ist, was ich zumindest wieder in High School, verwendet Verwendung für Backups. Und es war erstaunlich, weil man konnte 1,4 Megabyte auf speichern Diese Festplatte. Und dies war die hohe Dichte Version wie durch die HD, die hat angegeben dh vor der heutigen HD-Videos. 

Standard-Dichte betrug 800 Kilobyte. Und davor gab es 400-Kilobyte-Festplatten. Und davor gab es 5 und 1/4 Zoll-Disketten, die wirklich Floppy waren, , und ein wenig breiter und höher als diese Dinge hier. Aber kann man tatsächlich sehen die sogenannte Floppy Aspekt dieser Scheiben. 

Und funktionell, sind sie tatsächlich ziemlich ähnlich wie bei Festplatten mindestens dieses Typs. Wieder SSDs in neueren Computern Arbeit ein wenig anders. Aber wenn Sie sich bewegen, dass kleine Metall-Registerkarte kann man tatsächlich sehen ein wenig Cookie oder Platte. 

Es ist nicht aus Metall wie dieser. Dieser ist eigentlich etwas billiger Kunststoff. Und Sie können es Art wackeln. Und du hast trully gerade weg wischte einige Anzahl von Bits oder magnetischen Teilchen von dieser Festplatte. 

Also zum Glück, es gibt nichts auf sie. Wenn das Ding ist in der Art und Weise - und decken Ihre Augen und die Ihrer Nachbarn - Sie können nur eine Art ziehen diese ganzen Mantel aus so. Aber es gibt eine kleine Quelle, so sein bewusst, dass mit den Augen. So, jetzt haben Sie wirklich eine Diskette. 

Und was ist bemerkenswert, über diese ist, dass, soweit es sich um eine kleine Darstellung eines größeren Festplatten, diese Dinge sind super, super einfach. Wenn Sie kneifen die Unterseite von ihr, jetzt, dass Metall Sache ab und schälen sie zu öffnen, ist alles dort ist zwei Stücke Filz und dem sogenannten Diskette mit einem Stück aus Metall an der Innenseite. 

Und da geht die Hälfte der meine Festplatte den Inhalt. Es geht noch eine halbe von ihnen. Aber das ist alles, was im Inneren Spinnerei wurde von Ihrem Computer in vergangener Zeiten. 

Und wieder, dieses in Perspektive zu setzen, Wie groß ist die meisten Ihrer Festplatten in diesen Tagen? 500 Gigabyte, ein Terabyte, vielleicht in ein Desktop-Computer, 2 Terabyte, 3 Terabyte, 4 Terabyte, nicht wahr? Dies ist ein Megabyte, geben oder nehmen, das kann nicht einmal fit ein typisches MP3 mehr in diesen Tagen, oder einige ähnliche Musikdatei. 

So ein kleines Souvenir für Sie heute, und auch zu helfen, zu kontextualisieren, was wir für selbstverständlich nehmen jetzt in Problem stellte fünf. Das sind also Ihnen zu halten. Lassen Sie mich also Übergang, wo sein verbringen die nächsten pset als gut. So haben wir jetzt diese Seite gesetzt für - oh, ein paar Ansagen schnell. 

An diesem Freitag, wenn Sie möchten, kommen CS50 zum Mittagessen, zu den üblichen Ort zu gehen, cs50.net/rsvp. Und letztes Projekt - so pro Lehrplan, haben wir geschrieben das Abschlussprojekt Spezifikation bereits. Erkenne, dass das bedeutet nicht, es ist wegen besonders schnell. Es ist geschrieben, wirklich, nur um euch daran zu denken. Und in der Tat, ein super signifikante Prozentsatz werden Sie Bewältigung Abschlussarbeiten auf Material, das wir noch nicht einmal in der Klasse bekommen, wird aber so früh wie nächste Woche. 

Beachten Sie jedoch, dass die Spezifikation fordert einige unterschiedliche Komponenten der Abschlussprojekt. Die erste, in wenigen Wochen ein Erstvorschlag, ein ziemlich lässig E-Mail an Ihre TF, ihm zu sagen, oder was du bist darüber nachzudenken, für Ihr Projekt, mit keine Verpflichtung. Der Vorschlag macht Ihre besondere sein Engagement und sagte, hier ist das, was Ich möchte für mein Projekt zu tun. Was denken Sie? Zu groß? Zu klein? Ist es überschaubar? Und sehen Sie die Spezifikation für weitere Details. 

Paar Wochen danach ist der Status Bericht, der ein ähnlich ist Casual-Mail an Ihre TF zu sagen, wie weit hinter Sie in Ihrem letzten Projektdurchführung, gefolgt von die CS50 Hackathon zu dem jeder ist eingeladen wird, die ein Ereignis aus 20.00 an einem Abend bis 07.00 Uhr Uhr am nächsten Morgen. Pizza, wie ich kann in Woche erwähnt haben Null, wil um 9:00 Uhr serviert werden, Chinesisches Essen um 1:00 Uhr. Und wenn Sie noch um 5:00 Uhr wach, nehmen wir Sie zum Frühstück IHOP. 

Also die Hackathon ist eine der mehr Erlebnisse in der Klasse. Dann wird die Umsetzung fällig ist, und dann die klimatischen CS50 Fair. Mehr Details über all diese in den kommenden Wochen. 

Aber gehen wir zurück zu etwas old school - wieder ein Array. So ein Array war schön, denn es löst Probleme wie wir sahen nur eine vorhin mit studentischen Strukturen immer ein wenig außer Kontrolle, wenn wir Studenten wollen eine, Student zwei, Schüler drei, student dot dot dot, einige beliebige Anzahl von Studenten. 

So Arrays, vor ein paar Wochen, stürzte in und lösen alle unsere Probleme nicht im Voraus zu wissen, wie viele Dinge irgendeiner Art könnten wir wollen. Und wir haben gesehen, dass Strukturen können Sie uns helfen weiter zu organisieren unseren Code und halten konzeptionell ähnliche Variablen, wie ein Namen und ein Haus, zusammen, so dass wir können sie als eine Einheit, innen behandeln von denen es kleinere Stücke. 

Aber Arrays haben einige Nachteile. Was sind einige der Nachteile haben wir angetroffen mit Arrays so weit? Was ist das? Feste Größe - so, obwohl Sie vielleicht in der Lage sein, um Speicher für eine Zuweisung Array, wenn Sie wissen, wie viele Schüler Sie haben, wie viele Zeichen Sie haben vom Benutzer, wenn man einmal zugeordnet das Array, haben Sie Art gemalt sich in eine Ecke. 

Da kann man keinen neuen Elemente in der Mitte eines Arrays. Sie können keine Elemente mehr am Ende eines Arrays. Wirklich, müssen Sie in der Schaffung einer zurückgreifen ganz neue Reihe, wie wir besprochen haben, Kopieren der alten in die neue. Und wieder, das ist das, dass Kopfschmerzen GetString beschäftigt sich mit für Sie. 

Aber noch einmal, kann man noch nicht einfügen etwas in der Mitte des Arrays wenn die Rate nicht vollständig gefüllt. Zum Beispiel, wenn diese Anordnung hier Größe sechs nur fünf Dinge in ihm, Nun, man könnte nur tack etwas auf das Ende. Aber was, wenn Sie etwas einfügen in der Mitte des Array, obwohl es wahrscheinlich fünf von sechs Dinge in ihm? 

Nun, was wir tun, wenn wir alle hatten unserer menschlichen Freiwilligen auf der Bühne in Wochen Vergangenheit? Wenn wir jemanden hier setzen wollte, entweder diese Menschen, wie dies zu bewegen Weg, oder diese Menschen, wie dies zu bewegen Weise, und das wurde teuer. Die Verschiebung von Menschen innerhalb eines Array landete Addition und Kalkulation uns Zeit, damit viele unserer n squared Laufzeiten wie Insertion Sort, für Beispiel im schlimmsten Fall. So Arrays sind groß, aber man muss im Voraus wissen, wie groß Sie wollen. 

So OK, hier ist eine Lösung. Wenn ich nicht im Voraus wissen, wie viele Studenten, die ich haben könnte, und ich weiß, einmal Ich entscheide mich, obwohl, ich bin mit dem stecken viele Schüler, warum ich nicht einfach immer zuteilen doppelt so viel Platz wie ich denke, vielleicht brauche ich? Ist das nicht eine vernünftige Lösung? 

Realistisch gesehen, glaube ich nicht, dass wir gehen, um mehr als 50 Slots benötigen in einem Array für eine mittlere Klasse, also lasst uns einfach aufrunden. Ich werde 100 Slots in meinem Array zu machen, so so dass wir auf jeden Fall erhalten die Zahl der Studenten, die ich erwarten, in einigen mittel-Größenklasse. Also warum nicht einfach aufrunden und zuweisen mehr Speicher, typischerweise für eine Reihe als Sie denken Sie vielleicht sogar müssen? Was ist das einfache pushback zu dieser Idee? 

Du bist nur verschwenden Speicher. Buchstäblich jedes Programm schreiben Sie dann ist vielleicht mit doppelt so viel Speicher wie Sie tatsächlich benötigen. Und das funktioniert einfach nicht wie ein Gefühl besonders elegante Lösung. Darüber hinaus ist es gerade nimmt die Wahrscheinlichkeit eines Problems. Wenn Sie geschehen, ein beliebtes natürlich einem Semester und Sie haben 101 Studenten, ist das Programm noch grundsätzlich vor dem gleichen Problem. 

Also zum Glück gibt es eine Lösung für Diese Anzeige all unsere Probleme in Form von Datenstrukturen, die sind komplexer als die Wir haben bisher gesehen. Dies, behaupte ich, ist eine verkettete Liste. Dies ist eine Liste von Zahlen - 9, 17, 22, 26 und 34 - das sind zusammen durch verlinkt von dem, was ich als Pfeile gezeichnet. 

In anderen Worten, wenn ich darstellen wollte ein Array ist, konnte ich tun etwas wie dieses. Und ich werde diese auf dem Overhead setzen in nur einem Augenblick. Was ich tun konnte - hallo, alles in Ordnung. Stand by. Neue Computer hier, klar - alles in Ordnung. 

Also, wenn ich diese Zahlen in Array - 9, 17, 22, 26, 24 - nicht notwendigerweise maßstabsgetreu. Alles klar, also hier ist mein array - oh mein Gott. Alles klar, also hier ist mein Array. Oh mein Gott. 

[Gelächter] 

DAVID MALAN: Pretend. Es ist zu viel Aufwand um zurück zu gehen und beheben, so dass es - 26. So haben wir diese Reihe von 9, 17, 22, 26 und 34. Für diejenigen unter Ihnen können die peinliche Fehler, den ich gerade gemacht, da ist es. 

Also ich behaupten, dass dies ein sehr effiziente Lösung. Ich habe so viele ints als zugeteilt Ich - ein, zwei, drei, vier, fünf oder sechs - und ich habe dann die Nummern gespeichert innerhalb dieses Arrays. Aber nehmen wir an, dann möchte ich einfügen einen Wert wie die Zahl 8? Nun, wo es gehen? Angenommen, ich möchte einfügen eine Zahl wie 20. Nun, wo es gehen? Irgendwo in der Mitte, oder die Nummer 35 muss gehen irgendwo am Ende. Aber ich bin ganz aus dem Raum. 

Und dies ist eine grundlegende Herausforderung von Arrays, sind die Lösung nicht. Ich behauptete vor einem Augenblick, GetString löst dieses Problem. Wenn Sie möchten, um eine sechste Nummer einfügen in diesem Array, was ist mindestens eine Lösung können Sie zurückgreifen sicher, genau wie wir mit GetString? Was ist das? 

Nun, um es größer wird leichter gesagt als getan. Wir können nicht unbedingt das Array größer, aber was können wir tun? Machen Sie ein neues Array, das größer ist, der Größe 6, oder vielleicht Größe 10, wenn wir wollen, die Nase vorne zu bekommen, und dann kopieren das alte Array in das neue, und dann gratis das alte Array. 

Aber was ist die Laufzeit jetzt dieses Prozesses? Es ist groß O von n, weil der Kopiervorgang kosten wird Ihnen einige Einheiten Zeit, also nicht so ideal, wenn wir zuteilen ein neues Array, das wird doppelt so viel verbrauchen Speicher vorübergehend. Kopieren alt mach neu - Ich meine, es ist nur ein Kopfschmerz, der wird wieder, warum wir schrieben GetString für Sie. 

Also, was können wir stattdessen tun? Nun, was ist, wenn unsere Datenstruktur tatsächlich hat Lücken in ihm? Angenommen, dass ich mein Ziel mit entspannen zusammenhängende Abschnitte des Speichers, wobei 9 befindet sich direkt neben 17, das ist direkt neben 22, und so weiter. 

Und angenommen, dass 9 kann hier in RAM und 17 können hier im RAM überschrieben werden, und 22 können hier im RAM überschrieben werden. Mit anderen Worten, ich brauche sie nicht sogar zurück, um nicht mehr zurueck. Ich muss nur irgendwie eine Nadel einfädeln durch jede dieser Zahlen oder jedem dieser Knoten, so nennen wir die Rechtecke wie ich sie gezeichnet, um erinnern, wie man auf den letzten bekommen Knoten, wie die erste. 

Also, was ist die Programmierung zu konstruieren Wir haben vor kurzem gesehen, mit denen ich kann den Thread zu implementieren, oder hier, gezeichnet mit dem ich Umsetzung dieser Pfeile? So Zeiger, nicht wahr? Wenn ich vergeben nicht nur ein int, sondern ein Knoten - und durch Knoten, ich habe gerade meine Container. Und visuell, ich meine ein Rechteck. So ein Knoten anscheinend braucht zwei Werte enthalten - die int selbst, und dann, wie angedeutet die untere Hälfte des Rechtecks, ausreichend Platz für ein int. 

Also einfach Vorausdenken hier wie groß ist dieser Knoten, diese Container in Frage? Wie viele Bytes für den int? Vermutlich 4, wenn es wie üblich. Und dann, wie viele Bytes für den Zeiger? 4. Also dieser Behälter oder dieser Knoten ist gehen, um eine 8-Byte-Struktur sein. Oh, und das ist ein glücklicher Zufall, dass wir gerade eingeführt diesen Begriff der eine Struktur oder eine C-Struktur. 

Also ich behaupten, dass ich einen Schritt machen wollen auf dieses kompliziertere Umsetzung einer Liste von Nummern, einem verketteten Liste von Zahlen, muss ich eine do wenig mehr nach vorne und Denken erklären nicht nur ein int, aber eine Struktur dass ich rufe, konventionell hier Knoten. Wir könnten es, was wir wollen, aber Knoten sein wird, in einer Menge thematischen Dinge, die wir beginnen, jetzt. 

Innerhalb dieses Knotens ist ein int n. Und dann diese Syntax, ein wenig seltsam auf den ersten Blick - struct node * next. Nun bildhaft, was ist das? Das ist die untere Hälfte der Das Rechteck, das wir gesehen haben nur einen Augenblick vor. 

Aber warum sage ich struct node * als nur Knoten * dagegen? Denn wenn die Zeiger zeigt an einem anderen Knoten, es ist nur die Adresse eines Knotens. Das ist im Einklang mit, was wir diskutiert über Zeiger so weit. Aber warum, wenn ich behaupte, ist diese Struktur genannt Knoten, muss ich sagen, struct Knoten hier drinnen? 

Genau. Es ist irgendwie eine dumme Wirklichkeit C. Der typedef, so zu sprechen, hat nicht passiert. C ist super wörtlich. Es liest den Code oben nach unten, von links nach rechts. Und bis es trifft, dass das Semikolon Unterm Strich denke was nicht existieren als Datentyp? Node, Zitat unquote Knotens. 

Aber wegen der ausführlichere Erklärung habe ich in der ersten Zeile - typedef struct node - denn das war zuerst da, bevor die geschweiften Klammern, die Art ist wie Pre-Erziehung Clang, dass Sie Wissen Sie was, geben Sie mir eine Struktur genannt struct Knoten. Ehrlich gesagt, mag ich nicht, die Dinge struct Knoten struct Knoten alle in meinem Code. Aber ich werde es nur einmal, nur innen, so dass ich effektiv schaffen eine Art kreisförmige Referenz, nicht ein Zeiger auf mich per se, sondern ein Zeiger auf eine andere von einen identischen Typ. 

So stellt sich heraus, dass auf einer Datenstruktur wie diese, es gibt ein paar Operationen, die möglicherweise für uns von Interesse. Wir könnten einfügen möchten in eine Liste wie diese. Wir könnten zu löschenden aus einer Liste wie diese. Vielleicht wollen wir die Liste für eine Suche Wert, oder allgemeiner, Verfahrwege. Und Traverse ist nur eine andere Art von sagt Start auf der linken und stellen Sie der Weg nach rechts. 

Und beachten Sie, auch mit diesem etwas mehr anspruchsvolle Datenstruktur, lassen mich vorzuschlagen, dass wir einige leihen die Ideen der letzten zwei Wochen und implementieren eine Funktion namens Suche wie diese. Es wird true oder falsch, was darauf hinweist, ja oder nein, n in der Liste. Sein zweites Argument ist ein Zeiger an die Liste selbst, so dass ein Zeiger zu einem Knoten. 

Alles, was ich dann tun werde, ist zu erklären einen temporären Variablen. Wir nennen sie ptr durch Konvention, für Zeiger. Und ich zuweisen gleich die Anfang der Liste. 

Und jetzt bemerken die While-Schleife. Solange Zeiger nicht gleich auf null, ich werde zu prüfen. Ist Zeigerpfeil n gleich die n, die übergeben wurde? Und warten Sie eine Minute - neue Stück Syntax. Was ist Pfeil ganz plötzlich? Ja? 

Genau. Während also vor ein paar Minuten haben wir die Punkt-Notation etwas zugreifen Innere eines der Struktur, wenn die Variable Sie ist nicht die Struktur selbst, sondern ein Zeiger auf eine Struktur, Gott sei Dank, ein Stück Syntax, schließlich macht intuitiv Sinn. Der Pfeil bedeutet, um den Zeiger zu folgen, wie unsere Pfeile in der Regel bedeuten, bildhaft, und gehen Datenfeld innen. So Pfeil ist das gleiche wie Punkt, aber Sie verwenden, wenn Sie einen Zeiger haben. 

So, nur um dann rekapitulieren, wenn das n Feld innerhalb der Struktur als Zeiger gleich gleich n, true zurückgeben. Ansonsten ist diese Linie hier - Zeiger gleich Zeiger nächsten. Also, was ist zu tun, bemerken, ist, wenn ich bin derzeit zeigt auf die Struktur mit 9 und 9 ist nicht die Anzahl Ich suche - nehme ich suche für n gleich 50 - Ich werde meine temporäre Zeiger aktualisieren bis zu diesem Knotenpunkt mehr, aber den Mauspfeil nächsten, die wird mich hier aufgestellt. 

Jetzt erkannte ich, ist ein Wirbelwind Einführung. Am Mittwoch, den wir tatsächlich tun dies mit einigen Menschen und mit etwas mehr Code in einem langsameren Tempo. Aber klar, wir machen jetzt unsere Daten Strukturen komplexer, so dass unsere Algorithmen können effizienter, die sein wird, Voraussetzung für pset sechs, wenn wir in laden, wieder diejenigen 150.000 Worte, sondern müssen so tun, effizient und im Idealfall erstellen Programm, das für unsere Nutzer nicht läuft lineare, nicht in n Quadrat, aber in konstante Zeit, in der ideal. 

Wir informieren Sie am Mittwoch sehen. 

SPRECHER: Bei der nächsten CS50, David vergisst seine base case. 

DAVID MALAN: Und das ist, wie Sie senden Textnachrichten mit C. Was die - 

[VARIOUS TEXTNACHRICHT Hinweis-Sounds]