>> [Musikwiedergabe]
>> [VIDEO PLAYBACK]
>> -Er lügt.
>> -Worüber?
>> -Ich weiß es nicht.
>> -SO Was wissen wir?
>> -Das Um 9:15, Ray Santoya war bei der ATM.
-Ja.
Die Frage ist also, was tat er, um 9:16?
>> -Shooting Die 9 Millimeter auf etwas.
Vielleicht sah er den Scharfschützen.
>> -oder Mit ihm arbeiten.
>> -wait.
Gehen Sie zurück ein.
>> -Was siehst du?
>> -Bringen Sein Gesicht Vollbild.
>> -His Brille.
>> -Es Ist eine Reflexion.
>> -Es Ist das Nuevitas Baseball-Team.
Das ist ihr Logo.
>> -Und Er zu sprechen wer trägt diese Jacke.
>> [END PLAYBACK]
>> DAVID MALAN: Alles klar.
Dies CS50 und dies ist ein wenig von [unverständlich], mit dem Sie
Dilettantismus mit Problem stellte vier ein.
Heute starten wir ein wenig mehr suchen tief auf diese Dinge genannt Zeigern,
welches, obwohl es eine ziemlich obskure Thema,
es stellt sich heraus, dass es geht das Mittel sein, mit dem wir
kann mit dem Bau und Montage viel mehr anspruchsvolle Programme.
Aber wir haben es am vergangenen Mittwoch anhand einiger claymation zuerst.
Also das, Rückruf ist Binky und wir haben ihn benutzt
um einen Blick auf ein Programm zu nehmen, dass nicht wirklich etwas Interessantes zu tun,
aber es hat ein paar Probleme zu offenbaren.
Also heute, um zu beginnen, warum nicht wir zu Fuß schnell durch einige dieser Schritte,
versuchen, in Bezug auf die Menschen destillieren genau das, was hier vor sich geht
und warum dies schlecht ist, und fahren Sie dann und tatsächlich beginnen etwas zu bauen,
mit dieser Technik?
So waren die ersten zwei Zeilen in diesem Programm
und in juristischer Hinsicht, was werden diese beiden Linien zu tun?
Jemand, der recht komfortabel ist mit dem, was auf dem Bildschirm erklärt?
Was sind diese beiden Linien zu tun?
Es ist nicht alles, unterscheidet sich von Woche eins,
aber es gibt einige neue Sonderzeichen.
Ja?
Zurück gibt.
>> ZIELGRUPPE: Deklarieren von Zeigern?
DAVID MALAN: Sagen Sie wieder?
ZIELGRUPPE: Deklarieren von Zeigern?
DAVID MALAN: Deklarieren von Zeigern und Lassen Sie uns zu verfeinern es ein bisschen mehr.
ZIELGRUPPE: [unverständlich] Adresse x und y.
DAVID MALAN: Und dann anzugehen.
So gesagt, was wir tun wird uns erklärt, zwei Variablen.
Diese Variablen allerdings gehen um vom Typ int Sterne, werden,
Genauer gesagt bedeutet sie gehen, um zu speichern
die Adresse eines int, jeweils x und y.
Jetzt gibt es irgendwelche Werte?
Gibt es irgendwelche tatsächlichen Adressen in diesen zwei Variablen an diesem Punkt in der Zeit?
Nein.
Es ist nur so genannte Garbage-Werte.
Wenn Sie nicht wirklich zuweisen ein variable, was auch immer in RAM war
zuvor wird sich mit Nullen zu füllen und diejenigen, beide dieser Variablen.
Aber wir wissen noch nicht, was sie sind, und das ist,
gehen Schlüssel, warum Binky zu sein den Kopf verloren letzte Woche.
>> So war dies die claymation Inkarnation dieses
wobei Sie nur zwei Variablen, kleine kreisförmige Stücke aus Ton,
dass Variablen speichern, sondern als die eingewickelt Pfeile deuten darauf hin,
sie sind nicht wirklich zeigen überall bekannt.
Also mussten wir diese Linie, und das neu war in der vergangenen Woche, malloc für Speicher
Allokation, die nur eine andere Art ist zu sagen, das Betriebssystem, Linux
oder Mac OS oder Windows, hey, geben Sie mir einige Speicher,
und alles, was Sie zu sagen, das Betriebssystem
ist das, was bei der Beantragung es für Speicher.
Es wird nicht zu kümmern, was Sie gehen damit zu tun,
aber Sie brauchen, um die Betriebs sagen Systems, was durch malloc.
Ja?
>> Publikum: Wie viel?
DAVID MALAN: Wie viel?
Wieviel in Bytes, und so diese wieder eine erfundene Beispiel ist nur zu sagen,
geben Sie mir die Größe eines int.
Nun wird die Größe eines int vier Bytes oder 32 Bits.
Also das ist nur eine Möglichkeit, sagen, hey, Betriebssystem,
gib mir vier Byte, dass ich zu meiner Verfügung zu verwenden,
und gesagt, was bedeutet malloc Rendite gegen
in diesem Stück von vier Bytes?
ZIELGRUPPE: Adresse?
DAVID MALAN: Die Adresse.
Die Adresse dieser Brocken von vier Bytes.
Genau.
Und so das ist, was letztendlich gespeichert in x und das ist, warum wir nicht wirklich
egal, was die Anzahl der, dass Adresse ist, ob es sich um ox1 oder OX2
oder eine kryptische hexadezimale Adresse.
Wir kümmern uns nur bildhaft daß die Variable x ist jetzt
zeigt auf diesem Teil des Speichers.
So der Pfeil repräsentiert einen Zeiger oder Genauer gesagt wird eine Speicheradresse.
Aber noch einmal, wir in der Regel nicht kümmern was die eigentlichen Adressen sind.
Nun, sagt dieser Linie was in juristischer Hinsicht?
Sterne x erhält 42 Semikolon.
Was bedeutet das?
Du willst gehen?
Nicht zerkratzen den Hals.
>> ZIELGRUPPE: Die Adresse von x ist am 42.
>> DAVID MALAN: Die Adresse von x ist 42.
Nicht ganz.
So nah, aber nicht ganz, denn es gibt der Stern, ist diese Voran x.
Also müssen wir ein wenig zwicken.
Ja?
>> Publikum: Der Wert, den der Zeiger x ist, die auf 42.
DAVID MALAN: OK.
Der Wert, den der Zeiger x zeigt auf, sagen wir, sind 42,
oder anders gesagt, die Sterne x sagt, gehen Sie zu was auch immer-Adresse
ist in x, ob es sich um 1 Oxford Straße oder 33 Oxford Street
oder ox1 oder OX33, was auch immer dass numerische Adresse ist,
Sterne x die dereferenzierenden von x.
So gehen Sie an diese Adresse und dann legte die Zahl 42 gibt.
Also das wäre ein gleichwertige Art zu sagen, dass.
Also das ist alles schön und dann wir würden das Bild darstellen
wie folgt, wo wir hinzugefügt haben der 42 in diesem Stück von vier
Byte auf der rechten Seite, aber Diese Linie wurde, wo die Dinge schiefgegangen
und Binky den Kopf geknallt an diesem Punkt,
weil schlechte Dinge passieren, wenn Sie dereferenzieren Müllwerte
oder Sie dereferenzieren ungültig Zeiger, und ich sage ungültig
da zu diesem Zeitpunkt in der Geschichte, was innerhalb von y?
Was ist der Wert von y auf der Basis auf den letzten paar Schritte?
Ja?
Was ist das?
>> Publikum: Eine Adresse.
DAVID MALAN: Eine Adresse.
Es sollte eine Adresse sein aber ich habe es initialisiert?
So habe ich noch nicht.
Also, was ist bekannt, dass in es geben?
Es ist nur einige Müll Wert.
Es könnte eine beliebige Adresse von Null zu sein 2000000000, wenn Sie zwei GB RAM haben,
oder null bis 4 Milliarden Wenn Sie auch bekam vier Gigabyte RAM.
Es ist einige Müllwert, aber das Problem ist
dass das Betriebssystem, wenn es Ihnen nicht gegeben
dass Teil des Speichers spezifisch dass Sie versuchen, zu gehen,
es ist in der Regel werde, was dazu führen, wir als Segmentierungsfehler gesehen habe.
Also in der Tat, jeder von Ihnen, haben bei Problemen bei der Bürozeiten kämpfte
oder Probleme, die mehr ist in der Regel mit versuchen, herauszufinden,
einen Segmentation Fault, dass in der Regel bedeutet,
Du bist ein Segment zu berühren Speicher, die Sie sollte nicht sein.
Sie berühren Speicher, das Betriebssystem nicht
erlaubt Ihnen, zu berühren, egal ob es durch zu weit zu gehen in Ihrem Array
oder ab jetzt, ob es ist, weil Sie zu berühren
Speicher, der nur einige Müll Wert.
>> Dabei Sterne x hier Art von undefinierten Verhalten.
Sie sollten niemals tun, weil die Quoten werden, ist das Programm nur gehen zum Absturz zu bringen,
weil du sagst, gehen Sie zu dieser Adresse
und Sie haben keine Ahnung, wo diese Adresse tatsächlich ist.
Also das Betriebssystem ist wahrscheinlich, gehen, um Ihr Programm zum Absturz bringen
als Ergebnis ja ist, dass was da passiert ist, um Binky.
Also letztendlich, Binky Fest Dieses Problem mit diesem.
So dass Programm selbst war fehlerhaft.
Aber wenn Sie eine Art vorantreiben und diese Zeile ausführen, anstatt,
y gleich x bedeutet nur, was auch immer Adresse ist eine x, legte es auch in y.
>> Und so bildhaft, wir haben vertreten diese mit zwei Pfeilen
von x und von y Zeige an der gleichen Stelle.
So semantisch, gleich x y, da beide von denen
werden zum Speichern derselben Adresse, ergo zeigt auf 42,
und jetzt, wenn Sie sagen, Sterne y, an die Adresse gehen in y,
dies hat einen interessanten Nebeneffekt.
So ist die Adresse in y ist die dasselbe wie die Adresse in x.
Also, wenn Sie sagen, gehen Sie an die Adresse in y und ändern Sie den Wert bis 13,
Wer ist betroffen?
X ist, Punkt D, so zu sprechen, sollten ebenso betroffen sein.
>> Und in der Tat, wie Nick zeichnete dieses Bild in claymation war genau das.
Auch wenn wir folgen dem Zeiger y, landeten wir an der gleichen Stelle,
und so, wenn wir zu drucken waren aus X oder Y ist pointee,
dann würden wir den Wert von 13 zu sehen.
Nun, ich sage pointee zu sein konsistent mit dem Video.
Programmierer, meiner Wissen, nie wirklich
sagen, das Wort pointee, das, was gezeigt wird
an, sondern auch für die Konsistenz mit dem Video, erkennen
das ist alles, war in dieser Situation bestimmt.
Also irgendwelche Fragen über claymation oder Zeiger oder malloc jetzt noch?
Nein?
Gut.
>> So ohne weiteres Umschweife, lassen Sie uns einen Blick
bei denen dies eigentlich seit einiger Zeit verwendet.
Also haben wir diesen CS50-Bibliothek hatte das ist all diese Funktionen hat.
Wir haben getint verwendet eine Menge, GetString, wahrscheinlich früher GetLongLong
in meinem PSet ein oder so, aber was eigentlich los ist auf?
Nun, lassen Sie uns einen kurzen Blick unter der Haube auf einem Programm, das
inspiriert, warum geben wir Ihnen die CS50 Bibliothek, und in der Tat, wie in der vergangenen Woche,
wir begonnen, diejenigen, Stützräder ab.
Also das ist nun sortiert einer Obduktion, was
gibt es schon innerhalb der CS50-Bibliothek,
auch wenn wir jetzt beginnt sich zu bewegen weg von den meisten Programmen.
>> Das ist also ein Programm scanf 0 bezeichnet.
Es ist super kurz.
Es hat nur diese Zeilen, aber es stellt eine Funktion namens scanf
dass wir eigentlich vor sich geht um zu sehen ein Moment innerhalb der CS50-Bibliothek,
wenn auch in etwas anderer Form.
So ist dieses Programm auf der Leitung 16 ist eine Variable deklarieren x.
Also gib mir vier Bytes für ein int.
Es wird erzählt, Benutzer, Nummer bitte, und dann
das ist eine interessante Linie, letzte Woche tatsächlich miteinander verbindet
Und dies.
Scanf, und dann feststellen, es dauert ein Format-String, wie printf,
% i bedeutet einen int, und dann dauert es ein zweite Argument, die ein wenig aussieht
flippig.
Es ist Et-Zeichen x, und daran zu erinnern, sahen wir dies einmal in der vergangenen Woche nur.
Was bedeutet Et-Zeichen x dar?
Was bedeutet Et-Zeichen in C tun?
Ja?
>> ZIELGRUPPE: Die Adresse.
DAVID MALAN: Die Adresse.
So ist es das Gegenteil der Sternoperator,
während die Sterne Betreiber sagt, zu gehen Adresse, das kaufmännische Betreiber
sagt, herauszufinden, die Adresse dieses variable,
und so ist dies Taste, denn Zweck scanf im Leben
ist zum Scannen des Benutzers Eingabe von der Tastatur,
je nachdem, was auch immer er oder sie Typen, und lesen Sie dann Eingabe des Benutzers
in eine variable, aber wir sah in den vergangenen zwei Wochen
dass diese Swap-Funktion, die wir mühelos versucht, umzusetzen
war nur gebrochen.
Daran erinnern, dass die Swap-Funktion, wenn wir so wie ints deklariert A und B,
wir haben erfolgreich tauschen die zwei Variablen innerhalb der Swap-
Genau wie bei der Milch und Orangensaft, aber sobald Swap zurück
was war das Ergebnis in Bezug x und y sind die ursprünglichen Werte?
Gar nichts.
Ja.
Nichts ist passiert, dass die Zeit, denn Swaps nur die lokalen Kopien ändern,
was zu sagen, alles ist dieses Mal, wenn wir haben
wurde in Argumenten vorbei auf Funktionen, wir sind
nur auf der Durch Kopien dieser Argumente.
Sie können mit dem zu tun was Sie wollen mit ihnen,
aber sie gehen nicht zu haben, Wirkung auf die ursprünglichen Werte zurück.
Also das ist problematisch, wenn Sie möchte eine Funktion wie scanf haben
im Leben, ist deren Zweck zu scannen die Eingabe des Anwenders von der Tastatur
und dann die Lücken zu füllen, so zu zu sprechen, das heißt, geben Sie eine Variable wie x
ein Wert, denn wenn ich nur passieren x zu scanf,
wenn Sie die Logik des vergangenen betrachten Woche können scanf tun, was es will,
mit einer Kopie von x, aber es konnte nicht x dauerhaft zu ändern, es sei denn wir geben
scanf eine Schatzkarte, so zu sprechen, wobei x markiert die Stelle, wobei
wir in der Adresse von x, so dass übergeben scanf kann es und tatsächlich Veränderung gehen
der Wert von x.
Und so in der Tat, alle dass dieses Programm funktioniert
wenn ich scanf 0, in meinem Source- 5m Verzeichnis, stellen scanf 0,
dot Slash scanf, Nummer bitte 50, danke für den 50.
>> Also ist es nicht so interessant, Aber was ist wirklich passiert
ist, dass, sobald ich nennen scanf Hier wird der Wert von x
wird nachhaltig verändert.
Jetzt scheint diese schöne und gut, und in der Tat ist es
scheint, wie wir nicht wirklich brauchen der CS50-Bibliothek überhaupt nicht mehr.
Zum Beispiel lassen Sie uns laufen dies noch einmal hier.
Lassen Sie mich für eine Sekunde wieder zu öffnen.
Lassen Sie uns versuchen eine Reihe bitte und anstatt zu sagen, 50 wie zuvor,
lassen Sie uns einfach nein sagen.
OK, das ist ein wenig seltsam.
OK.
Und nur einige Unsinn hier.
So dass es nicht zu scheinen, handfehlerhaften Situationen.
Also müssen wir Beginn minimal Hinzufügen einiger Fehlerprüfung
um sicherzustellen, dass der Benutzer in einer tatsächlichen Zahl eingegeben haben, wie 50,
denn anscheinend einzutippen wird nicht als problematisch erkannt,
aber es wird wahrscheinlich sein sollte.
>> Lassen Sie uns an dieser Version Nun, das ist mein Versuch, GetString neu implementieren.
Wenn scanf hat all dies Funktionalität eingebaut,
Deshalb haben wir uns mit diesen wurden Dilettantismus Stützräder wie GetString?
Nun, hier ist vielleicht meine eigene einfache Version GetString
wobei vor einer Woche hätte ich gesagt haben, geben Sie mir eine Zeichenfolge und nennen es puffern.
Heute werde ich einfach starten sagen char Sterne, die, Rückruf,
es ist nur ein Synonym.
Es sieht aus, gruseliger, aber es ist genau dasselbe.
So geben Sie mir eine Variable namens Puffer das wird eine Zeichenfolge zu speichern,
sagen Sie dem Benutzer String bitte, und dann, wie zuvor,
wollen wir versuchen, diese Lektion zu leihen scanf % s diesmal und dann in Puffer übergeben.
Jetzt eine schnelle Plausibilitätsprüfung.
Warum bin ich nicht sagen, Und-Zeichen-Puffer dieses Mal?
Folgern aus dem vorherigen Beispiel.
ZIELGRUPPE: Char Sterne ist ein Zeiger.
DAVID MALAN: Genau, denn dieses Mal, char
Stern ist bereits ein Zeiger, eine Adresse, durch Definition dieser Stern dort zu sein.
Und wenn scanf erwartet eine Adresse, es genügt, einfach nur, um in Puffer übergeben.
Ich brauche nicht zu sagen, Und-Zeichen-Puffer.
Für die Neugierigen, könnten Sie tun so etwas wie dieses.
Es wäre unterschiedliche Bedeutung haben.
Dies würde Ihnen einen Zeiger einem Zeiger, der eigentlich
eine gültige Sache in C, aber für Jetzt, lassen Sie es einfach halten
und halten Sie die Geschichte konsequent.
Ich werde einfach weitergeben müssen in Puffer und das ist richtig.
Das Problem ist aber, diese.
Lassen Sie mich gehen Sie vor und führen Sie diese Programm nach dem Kompilieren.
Machen scanf 1.
Verdammt, mein Compiler fangen meine Fehler.
Gib mir eine Sekunde.
Clang.
Nehmen wir an, scanf-1.c.
OK.
Da gehen wir.
Ich brauche es.
CS50-ID verfügt über verschiedene Konfigurationseinstellungen
dass Sie zum Schutz vor sich selbst.
Ich brauchte, um diejenigen, die durch deaktivieren Laufklang manuell diesmal.
So String bitte.
Ich werde weitermachen und geben Sie meine Lieblings Hallo Welt.
OK, null.
Das ist nicht das, was ich getippt.
So ist es bezeichnend für etwas, falsch.
Lassen Sie mich gehen Sie vor und geben Sie in eine wirklich lange Zeichenfolge.
Vielen Dank für die null und ich weiß nicht, wenn ich in der Lage sein, um es zum Absturz bringen können.
Lassen Sie uns versuchen, ein wenig Kopie und fügen Sie ihn und sehen, ob das hilft.
Fügen Sie einfach eine Menge von dieser.
Es ist definitiv eine größere String als üblich.
Lassen Sie uns gerade richtig schreiben.
Nein.
Verdammt.
Befehl nicht gefunden.
Also das ist, in keinem Zusammenhang.
Das ist, weil ich eingefügt einige schlechte Charaktere,
aber dies stellt sich heraus, ist nicht zur Arbeit gehen.
>> Versuchen wir diesen Punkt nochmals, denn es macht mehr Spaß, wenn wir tatsächlich abstürzen es.
Lassen Sie uns geben Sie dies und jetzt bin ich gehen, um eine wirklich lange Zeichenfolge kopieren
und jetzt ist, wenn wir uns sehen lassen kann diese Sache zum Absturz bringen.
Beachten Sie, ich weggelassen Räume und neue Linien und Strichpunkte
und alle flippig Zeichen.
Enter.
Und jetzt ist einfach nur das Netzwerk langsam.
Ich gedrückter Befehlstaste-V zu lang ist, deutlich.
Verdammt!
Befehl nicht gefunden.
>> OK.
Nun, das ist der Punkt, dennoch die folgende.
Also, was ist eigentlich los Auf dieser Erklärung
Saiblings Sterne-Puffer in Zeile 16?
So Was bekomme ich wenn ich erklären, einen Zeiger?
Alles, was ich bin immer ist ein Vier-Byte-Wert genannte Puffer, aber was ist innerhalb der IT
Im Moment?
Es ist nur einige Müll Wert.
Da jederzeit Sie eine Variable deklarieren in C, es ist nur einige Müll Wert,
und wir sind in die Ausgangs Fahrt über diese Realität.
Nun, wenn ich sagen, scanf, gehen Sie zu dieser Adresse
und setzen, was die Benutzertypen in.
Wenn der Benutzer in hallo Welt, na ja, wo finde ich es?
Buffer ist ein Müllwert.
>> Also das ist ein bisschen wie ein Pfeil das ist zeigt wer weiß, wo.
Vielleicht ist es zeigen hier in meinem Speicher.
Und so, wenn der Benutzer Typen in Hallo Welt,
das Programm versucht, die setzen String Hallo Welt Backslash 0
in diesem Teil des Speichers.
Aber mit einer hohen Wahrscheinlichkeit, aber eindeutig nicht 100% Wahrscheinlichkeit,
der Computer wird sich dann zum Absturz das Programm, da dies nicht
Speicher I erlaubt sein sollte, berührt werden.
Also kurz gesagt, ist dieses Programm genau aus diesem Grund fehlerhaft.
Ich bin grundsätzlich nicht zu tun, was?
Welche Schritte muss ich weggelassen, ebenso wie wir mit Binky erste Beispiel weggelassen?
Ja?
>> ZIELGRUPPE: Speicherzuweisung?
>> DAVID MALAN: Speicherzuweisung.
Ich habe nicht wirklich zugeordnet Jeder Speicher für diesen String.
So können wir dies in ein paar Möglichkeiten zu beheben.
Eines können wir es einfach zu halten und in der Tat, jetzt bist du
gehen zu beginnen, um eine Verwischung sehen der Leitungen zwischen dem, was
ein Array ist, was ein String ist, was für ein char Stern ist, was ein Array von Zeichen
ist.
Hier ist ein zweites Beispiel mit Streichern und Bekanntmachung
alles, was ich auf der Leitung durchgeführt 16 ist, anstatt zu sagen,
dass Puffer wird ein char Stern, ein Zeiger auf einen Teil des Speichers,
Ich werde sehr proaktiv geben mir einen Puffer für 16 Zeichen,
und in der Tat, wenn Sie nicht vertraut sind mit dem Begriff Pufferung
wahrscheinlich aus der Welt der Videos, wo ein Video ist Puffern, Puffern,
Pufferung.
Nun, was ist die Verbindung hier?
Nun, Innerhalb von YouTube und im Inneren des Video-Player
Regel ist ein Array das ist größer als 16.
Es könnte eine Reihe von Größe sein Megabyte, vielleicht 10 Megabyte,
und in diesem Array unterstützt Ihr Browser laden Sie eine ganze Reihe von Bytes,
eine ganze Reihe von Megabytes Video- und der Video-Player,
YouTube oder wer auch immer ist, beginnt Lesen der Bytes aus dem Array,
und jedes Mal, wenn die sehen, Wort Pufferung Pufferung
das bedeutet, dass der Spieler bis zum Ende des Arrays geworden.
Das Netzwerk ist so langsam, dass es nicht nachgefüllt das Array mit mehr Bytes
und so du aus Bits sind um dem Benutzer anzuzeigen.
>> So Puffer ist eine treffende Begriff hier, dass es ist nur ein Array, ein Teil des Speichers.
Und das wird es zu beheben denn es stellt sich heraus,
dass Sie Arrays behandeln, als ob sie sind Adressen, obwohl Puffer
ist nur ein Symbol, es ist ein Folge von Zeichen, Puffer,
das ist nützlich für mich, der Programmierer, können Sie den Namen der Umgebung übergeben
als wäre es ein Zeiger, als ob es
waren die Adresse eines Chunk Speicher für 16 Zeichen.
Also das ist, zu sagen, ich passieren kann die scanf genau das Wort
und so jetzt, wenn ich dieses Programm, machen scanf 2, Punkt Schrägstrich scanf 2,
und geben Sie in Hallo Welt, Geben Sie, dass Zeit--
>> Hmm, was ist passiert?
String bitte.
Was habe ich falsch gemacht?
Hallo Welt, Puffer.
Hallo Welt.
Ah, ich weiß, was es tut.
OK.
So ist es zu lesen up bis zum ersten Platz.
Lassen Sie uns also betrügen nur für einen Augenblick und sagen, ich wollte nur etwas geben
wirklich lange, wie dies ein langer Satz das ist einer, zwei, drei, vier, fünf,
sechs, sieben, acht, neun, 10, 11, 12, 13, 14, 15, 16.
OK.
Es ist in der Tat ein langer Satz.
So ist dieser Satz länger als 16 Zeichen
und so, wenn ich drücken Sie die Eingabetaste, was wird passieren?
Nun, in diesem Fall von der Geschichte, ich erklärt hatte Puffer
um tatsächlich als ein Array mit 16 Zeichen bereit zu gehen.
So ein, zwei, drei, vier, fünf, sechs, sieben, acht, neun, 10, 11, 12, 13, 14,
15, 16.
So 16 Zeichen, und jetzt, wenn ich in etwas zu lesen, wie das ist ein langer
Satz, was passieren wird dass ich gehe, um in diese zu lesen ist ein lang
S-E-N-T-E-N-C-E, Satz.
>> Das ist also absichtlich eine schlechte Sache ist, dass ich
halten das Schreiben über die Grenzen meines Array,
über die Grenzen meiner Puffer.
Ich konnte das Glück und das Programm zu erhalten wird am Laufen zu halten und nicht zu kümmern,
aber allgemein gesprochen, diese wird in der Tat stürzt mein Programm,
und es ist ein Fehler in mein Kodex der Moment, als ich Schritt
über die Grenzen dieses Arrays, weil ich
weiß nicht, ob es notwendigerweise zum Absturz
oder wenn ich werde einfach glücklich zu erhalten.
So ist dies problematisch, da in diesem Fall ist es nicht zu funktionieren scheint,
und lassen Sie uns das Schicksal herausfordern hier, auch wenn die IDE scheint einiges vertragen
von--
>> Da gehen wir.
Endlich.
Also ich bin der einzige, der diese sehen können.
Also musste ich einfach nur eine Menge Spaß Typisierung out eine wirklich lange eigentlichen Begriff
dass es mit Sicherheit überschritten 16 Bytes, weil ich
in dieser verrückten lange multi-Zeile eingegeben Phrase, und dann feststellen, was passiert ist.
Das Programm versucht, ihn zu drucken und dann bekam einen Segmentation Fault
und Segmentierung Fehler ist, wenn so etwas passiert
und das Betriebssystem, sagt nein, nicht berühren können, dass der Speicher.
Wir werden töten das Programm überhaupt.
>> So scheint dies problematisch.
Ich habe das Programm, wobei verbesserte zumindest haben einige Speicher,
dies würde jedoch zu beschränken scheinen die Funktion GetString zu bekommen
Saiten der endlichen Länge 16.
Also, wenn Sie mehr unterstützen wollen, Sätze als 16 Zeichen,
Wie geht's?
Nun, man kann die Zunahme Größe dieses Puffers zu 32
oder das scheint Art Kurz.
Warum wir nicht einfach machen es 1000 aber zurückschieben.
Was ist die Antwort intuitiv von einfach vermeiden dieses Problem, indem sie
meinem Puffer größer, wie 1.000 Zeichen?
Durch die Implementierung von GetString diese Weise.
Was ist gut oder schlecht hier?
Ja?
Publikum: Wenn Sie binden eine Menge von Raum und Sie sie nicht benutzen,
dann können Sie diesen Raum nicht umzuschichten.
DAVID MALAN: Absolut.
Es ist eine Verschwendung, sofern wenn Sie nicht tun wirklich brauchen 900 dieser Bytes
und du fragst 1000 insgesamt wie auch immer,
Sie gerade verbrauchen mehr Speicher auf Computer des Benutzers als Sie benötigen,
und immerhin einige Sie bereits erlebt habe
im Leben, dass, wenn Sie laufen viele Programme
und sie essen bis viel Speicher, Dies kann tatsächlich die Leistung auswirken
und die Erfahrung des Benutzers auf dem Computer.
Also das ist ein bisschen eine faule Lösung, sicher, und umgekehrt,
es ist nicht nur verschwenderisch, welches Problem bleibt, auch wenn ich meinen Puffer
1000?
Ja?
>> Publikum: Der String ist Länge 1.001.
DAVID MALAN: Genau.
Wenn Ihr String Länge 1001, Sie haben genau das gleiche Problem,
und durch meine Argumentation, würde ich nur dann machen es 2000
aber Sie wissen nicht, in voranzubringen, wie groß es sein sollte,
und doch, ich muss mein Programm zu kompilieren bevor er Menschen nutzen und Download
es.
Also das ist genau die Art von Zeug, dass die CS50-Bibliothek versucht
um uns mit zu helfen und wir nur einen Blick auf einige der zugrunde liegenden Implementierung
Hier, aber dies ist CS50 Punkt C. Diese ist die Datei, die auf CS50 IDE gewesen ist
alle diese Wochen, die Sie verwendet haben.
Es ist vorkompilierte und Sie haben benutze es automatisch
von Natur aus mit der dash L CS50 Flagge mit Klang,
aber wenn ich scrollen Sie durch alle Diese Funktionen, hier ist GetString,
und nur, um Ihnen eine geben Geschmack von, was los ist,
lassen Sie uns einen kurzen Blick auf die relative Komplexität.
Es ist nicht eine super lange Funktion, aber wir haben nicht die
müssen alle hart zu denken wie man über das Erhalten Saiten zu gehen.
>> Also hier meine Puffer und ich offenbar initialisieren Sie sie auf null.
Dabei ist natürlich die Gleiche wie char Sterne,
aber ich beschloss, in Umsetzung der CS50-Bibliothek
dass, wenn wir gehen, um vollständig dynamisch,
Ich weiß nicht im Voraus wie groß von einem wissen, String-Benutzer gehen zu wollen, zu bekommen.
Also werde ich anfangen mit nur einem leeren String
und ich werde den Aufbau so viel Speicher als ich brauche, um den Benutzer String passen
und wenn ich nicht haben genug, ich werde fragen
das Betriebssystem für mehr Speicher.
Ich werde ihren String bewegen in einen größeren Teil des Speichers
und ich werde zu lösen oder zu befreien die ausreichend großen Teil des Speichers
und wir sind gerade dabei dies iterativ zu tun.
>> So ein kurzer Blick, Hier ist nur eine Variable
, mit dem werde ich den Überblick zu behalten der Fähigkeit meiner Puffer.
Wie viele Bytes kann ich ein?
Hier ist eine Variable n mit das werde ich halten
verfolgt, wie viele Bytes tatsächlich der Puffer oder die der Benutzer eingegeben hat.
Wenn Sie das nicht vorher gesehen haben, können Sie können angeben, dass eine Variable, wie ein int
nicht signiert ist, die wie der Name andeutet, bedeutet, es ist nicht negativ ist, und warum sollte
I zur Angabe stören wollen immer dass ein int ist nicht nur ein int,
aber es ist ein unsigned int?
Es ist eine nicht-negative Int.
Was bedeutet die [unverständlich] das?
>> ZIELGRUPPE: Es beschreibt einen Betrag des Speichers, der sein kann, [unverständlich].
>> DAVID MALAN: Ja.
Also, wenn ich sage, ohne Vorzeichen, das ist eigentlich so dass Sie ein Bit der zusätzlichen Speicher
und es scheint irgendwie albern, aber wenn Sie haben eine Zusatzspeicher, dass
bedeutet, dass Sie so viele haben doppelt Werte, die Sie stellen können,
denn es kann eine 0 oder eine 1 sein.
So standardmäßig, kann ein int grob sein negativen 2 Milliarden den ganzen Weg
bis zu positiven 2 Milliarden.
Das sind große Reichweiten, aber es ist immer noch Art von Verschwendung
wenn Sie kümmern sich nur um Größen, die nur intuitiv
sollte nicht negativ sein oder positiv oder 0, auch dann,
warum sind Sie verschwenden 2 Mrd. mögliche Werte für negative Zahlen
wenn Sie nie, sie zu benutzen?
So sagen, unsigned, jetzt meine int kann zwischen 0 und etwa 4 Milliarden.
>> Also hier ist nur ein int C aus Gründen werden wir nicht gerade jetzt, wie in zu erhalten
warum es ein int statt eines char, aber hier ist
das Wesentliche, was los ist auf, und einige von euch
verwenden könnte, zum Beispiel, die fgetc Funktion auch PSet vier
oder danach, werden wir es sehen, wieder in Problem stellte fünf,
fgetc ist nett, weil, wie der Name Art, Art arcanely schon sagt,
es ist eine Funktion, bekommt einen Charakter und so,
was ist grundlegend anders über das, was wir tun, in GetString
ist, dass wir sie nicht verwenden Scanf in der gleichen Weise.
Wir sind nur kriechend entlang Schritt-für-Schritt über alles, was der Benutzer eingetippt,
denn wir können immer zuzuweisen einem char, und so können wir immer sicher
Blick auf einen char zu einem Zeitpunkt, und der Zauber beginnt hier geschehen.
Ich werde nach unten zu scrollen Mitte dieser Funktion
nur um kurz vorstellen diese Funktion.
Ähnlich wie es gibt eine malloc-Funktion, gibt es
a realloc-Funktion, wo realloc lässt Sie einen Teil des Speichers umzuschichten
und machen es größer oder kleiner.
So lange Geschichte kurz und mit eine Welle von Hand für heute,
wissen, dass das, was GetString tut, ist es sort
der magisch wachsen oder Schrumpfen der Puffer als Benutzer
Typen in seiner Zeichenfolge.
>> Also, wenn der Benutzer ein kurze Zeichenfolge, dieser Code
nur ordnet genug Speicher, um die Zeichenfolge zu passen.
Wenn der Benutzer hält Typisierung wie ich es wieder und wieder
wieder gut, wenn die Puffers anfänglich dieses große
und das Programm erkennt, um warten Sie eine Minute, ich bin aus dem Raum,
es geht um das Doppelte die Größe des Puffer
und dann die doppelte Größe des Puffers und der Code, die Verdoppelung der Fall ist,
Wenn wir uns hier, es ist nur diese clevere Einzeiler.
Sie können diese Syntax nicht gesehen haben vor, aber wenn Sie sagen, Sterne gleich,
dies ist dasselbe wie sagen Kapazität mal 2.
So ist es einfach immer verdoppelt die Kapazität des Puffer
und dann erzählte realloc zu geben selbst, dass viel mehr Speicher.
>> Nun Nebenbei gibt weitere Funktionen hier
dass wir nicht ins Detail aussehen außer in getint zeigen,
verwenden wir in GetString getint.
Wir überprüfen, dass es nicht null, die, Rückruf,
ist der besondere Wert, bedeutet etwas schief gelaufen ist.
Wir sind aus der Erinnerung.
Besser überprüfen dafür.
Und wir haben eine Wächter Wert zurück.
Aber ich werde auf die Bemerkungen wie zu verschieben warum und dann verwenden wir diese Cousin von scanf
genannt Sscanf und es stellt sich heraus, dass sscanf oder String scanf,
lässt Sie einen Blick auf die Linie zu nehmen, dass der Benutzer eingetippt und lassen Sie sich
analysieren sie im Wesentlichen und was ich bin denn hier ist Ich sage sscanf,
zu analysieren, was der Benutzer eingegeben und stellen Sie sicher,% i,
gibt es eine ganze Zahl in ihr, und wir werden nicht gelangen in heute genau, warum gibt es auch
a% c hier, aber das auf den Punkt erlaubt uns zu erkennen, ob der Benutzer eingegeben hat
in etwas Schein nach der Nummer.
Also der Grund, dass getint und GetString Ihnen sagen, es nochmal zu versuchen, versuchen, versuchen Sie es erneut
Wegen all der dass Code, den wir geschrieben haben,
es ist Art von Blick auf die Eingabe des Benutzers dafür zu sorgen, ist es durchaus Ziffern
oder es ist eine tatsächliche Floating- Punktwert oder dergleichen,
je nachdem, welchen Wert funktionieren Sie verwenden.
>> Puh.
OK.
Das war ein Schluck aber der Punkt ist hier,
dass der Grund, wir hatten diese Stützräder auf
Denn auf der untersten Ebene, es gibt einfach so viele Dinge, die
schief gehen kann, dass wir wollten, präventiv zu behandeln
diese Dinge sicherlich in der frühesten Wochen der Klasse,
aber jetzt mit PSet vier und fünf und PSet darüber hinaus werden Sie sehen, dass es mehr zu
Sie aber auch Sie besser in der Lage sind zur Lösung dieser Art von Problemen
selbst.
Irgendwelche Fragen zu GetString oder getint?
Ja?
>> Publikum: Warum würden Sie verdoppeln die Kapazität des Puffer
anstatt nur steigende es wird von dem genauen Betrag?
>> DAVID MALAN: Gute Frage.
Warum sollten wir verdoppeln die Kapazität des Puffers im Gegensatz
nur zunehmende es von einigen konstanten Wert?
Es war eine Design-Entscheidung.
Wir haben gerade beschlossen, dass, da es dazu neigt, ein wenig teuer zeitlich zu fragen,
das Betriebssystem für Speicher, haben wir nicht
wollen am Ende immer in eine Situation, für große Zeichenfolgen
dass wir uns fragen, das Betriebssystem wieder
und wieder und wieder in schneller Folge für Speicher.
So haben wir gerade beschlossen, etwas beliebig, aber wir hoffen angemessen,
dass, weißt du was, lassen Sie uns versuchen, vorgreifen
und einfach weiter zu verdoppeln, so dass Wir minimieren die Höhe der Zeit
wir müssen malloc anrufen oder realloc, aber insgesamt Urteil
rufen Sie in der Abwesenheit von zu wissen, was die Nutzer möchten Sie vielleicht geben.
Beide Wege könnte fraglich sein.
Die wohl gut.
>> Werfen wir also einen Blick auf ein paar andere Nebenwirkungen des Gedächtnisses,
Dinge, die schief gehen können und Tools, die Sie
verwenden, um diese Art von Fehler zu fangen.
Es stellt sich heraus alle von euch, auch wenn check50 hat dir nicht gesagt, so viel,
wurden schriftlich buggy Code da Woche ein,
selbst wenn alle check50 Tests übergeben, und selbst wenn Sie und Ihre TF
sind super zuversichtlich, dass Ihr Code funktioniert wie vorgesehen.
Ihr Code ist Buggy oder dass alle von Ihnen fehlerhaft,
bei der Verwendung der CS50-Bibliothek, wurden undicht Speicher.
Sie haben uns gefragt, das Betriebssystem für Speicher in den meisten Programmen
Sie geschrieben haben, aber Sie haben, nie es tatsächlich zurück gegeben.
Sie haben GetString genannt und getint und GetFloat,
jedoch mit GetString, haben Sie nie unGetString oder Give genannt
String zurück oder dergleichen, aber wir gesehen haben, dass GetString tut Speicher zuweisen
durch malloc oder dieser Funktion realloc, das nur
im Geiste sehr ähnlich, und doch, wir waren
fragt das Betriebssystem für Speicher und Speicher wieder und wieder
aber nie geben es zurück.
>> Nun, so nebenbei, stellt sich heraus, dass wenn ein Programm beendet wird, wird der gesamte Speicher
wird automatisch freigegeben.
So ist es nicht eine große Sache.
Es wird nicht zum Bruch IDE oder Dinge verlangsamen,
aber wenn Programme zu tun Regel undicht Speicher
und sie für eine lange Zeit laufen.
Wenn Sie jemals die dummen kleinen gesehen haben Beach-Ball in Mac OS oder die Sanduhr
unter Windows, wo es eine Art ist Verlangsamung oder denken oder denken
oder einfach nur richtig los um auf ein Schneckentempo verlangsamen,
es sehr wahrscheinlich sein könnte das Ergebnis eines Speicherverlusts.
Die Programmierer, die schrieb, die Software, die Sie verwenden
fragen Sie das Betriebssystem für das Gedächtnis alle paar Minuten, jede Stunde.
Aber wenn Sie laufen die Software, auch wenn es
in Ihrem Computer minimiert für Stunden oder Tage auf Ende,
Sie könnte für immer mehr fragen Speicher und eigentlich nie benutzen
und so Ihren Code sein könnte, oder Programme könnten undicht sein Gedächtnis,
und wenn Sie ein Speicherleck zu starten, gibt es weniger Speicher für andere Programme,
und die Wirkung ist, langsam alles auf.
>> Nun, dies ist mit Abstand einer der die grausamsten Programme
Sie Möglichkeiten haben in CS50 laufen, sofern
als seine Ausgabe ist noch esoterischer als Klang oder machen oder jeder der Befehls
Zeilenprogramme, bevor wir laufen haben, aber Gott sei Dank, in seine Ausgabe eingebettet
es einige Tipps, die sehr hilfsbereit wird nützlich entweder für PSet vier sein
oder sicher PDie fünf.
So valgrind ist ein Werkzeug die verwendet werden können, um zu suchen
für Speicherlecks in Ihrem Programm.
Es ist relativ einfach zu laufen.
Sie führen valgrind und dann, auch aber es ist ein wenig ausführlicher,
dash dash Leckprüfung ist gleich voll, und dann dot
Schrägstrich und den Namen Ihres Programms.
So valgrind dann führen Sie Ihr Programm und ganz am Ende des Programms
ausgeführt wird, bevor es beendet wird und gibt Ihnen eine weitere Eingabeaufforderung
es geht zu analysieren Ihre Programm, während es bereits läuft
und Ihnen sagen, hast du lecken Jeder Speicher und noch besser,
haben Sie Speicher Note, nicht Ihnen gehören?
Es kann nicht alles zu fangen, aber es ist ziemlich gut fangen die meisten Dinge.
>> Also hier ist ein Beispiel für meine mit Lauf Dieses Programm, mit Lauf valgrind,
ein Programm namens Gedächtnis, und ich werde
um die Linien, die sich hervorheben letztlich für uns von Interesse.
Es gibt also noch mehr Ablenkungen dass ich von der Folie gelöscht.
Aber lasst uns einfach sehen, was diese Programm ist in der Lage, uns zu sagen.
Es ist in der Lage, uns mitzuteilen, was wie ungültige Schreib der Größe 4.
Mit anderen Worten, wenn Sie Speicher berühren, speziell 4 Bytes des Speichers
dass Sie nicht haben sollte, valgrind kann Ihnen sagen, dass.
Ungültige Schreib der Größe 4.
Sie berührte vier Bytes dass Sie nicht haben sollte.
Wo hast du das gemacht?
Das ist die Schönheit.
Speicher dot c Linie 21 ist, wo Sie vermasselt, und das ist, warum es ist hilfreich.
Ähnlich wie GDB, kann es helfen, Punkt, den Sie bei der aktuellen Fehler.
>> Jetzt ist dieses ein wenig mehr verbose, wenn nicht verwirrend.
40 Bytes in 1 Blöcke sind auf jeden Fall Verlust Posten 1 von 1 verloren.
Was bedeutet das?
Nun, es bedeutet nur, Sie gefragt 40 Byte und Sie nie gab es zurück.
Sie nannte malloc oder Sie aufgerufen GetString und das Betriebssystem
gab Ihnen 40 Bytes, aber man kann nie freigegeben oder freigegeben, dass der Speicher,
und fair zu sein, haben wir nie zeigen Ihnen, wie Sie zurück Speicher geben.
Stellt sich heraus, es ist ein Super- einfache Funktion frei bezeichnet.
Nimmt ein Argument, das Ding Sie befreien oder zurückgeben möchten,
aber 40 Bytes, offenbar, in diesem Programm
haben in Zeile verloren 20 von Speicher Punkt c.
>> Also mal sehen, dieses Programm.
Es ist super nutzlos.
Es zeigt nur Dieser spezielle Fehler.
Werfen wir also einen Blick.
Hier ist Haupt-und Haupt, bemerken, Anrufe eine Funktion namens f und dann zurückkehrt.
Also nicht so interessant.
Was bedeutet f zu tun?
Beachten Sie, ich habe nicht mit einem Prototyp zu stören.
Ich wollte, um den Code zu halten so gering wie möglich.
Also setzte ich f oben Haupt- und das ist in Ordnung, natürlich,
für kurze Programme wie dieses.
So f nichts zurückgibt und tut nichts nehmen, aber es tun.
Es erklärt, ähnlich wie in der Binky Beispiel
ein Zeiger namens x, das wird um die Adresse eines int speichern.
Das ist also der linken Seite.
In Englisch, was ist das rechten Seite gerade?
Anyone?
Was ist dies für uns tun?
Ja?
>> ZIELGRUPPE: [unverständlich] mal so groß wie ein Int
das ist 10-mal, dass [unverständlich]
DAVID MALAN: Gut und lassen Sie mich zusammenfassen.
Also genug Platz zuzuweisen für 10 ganze Zahlen oder 10, was ist die Größe eines int,
es ist vier Bytes, also 10 mal 4 40, so dass die rechte Seite, die ich
markiert ist mir 40 Byte und Speichern der Adresse des ersten Bytes
in x.
Und jetzt endlich, und hier ist, wo dieses Programm ist fehlerhaft, was ist
falsch mit Linie 21 auf der Grundlage dieser Logik?
Was ist los mit der Leitung 21?
Ja?
ZIELGRUPPE: Sie können nicht Index in x [unverständlich].
DAVID MALAN: Ja.
Ich sollte nicht Index in x so.
So syntaktisch, das ist OK.
Was ist schön ist, genauso wie Sie kann der Name eines Arrays zu behandeln
als ob es ein Zeiger ähnlich können Sie einen Zeiger zu behandeln, als ob es
ein Array, und so kann ich syntaktisch sagen x Halterung etwas, x Halterung i,
aber die 10 ist problematisch.
Warum?
>> ZIELGRUPPE: Weil es nicht im Inneren.
>> DAVID MALAN: Es ist nicht innerhalb dieser Teil des Speichers.
Was ist der größte Wert, ich sollte Putting in den eckigen Klammern?
9, 0 bis 9.
Da Null Indizierung.
So 0 bis 9 wäre in Ordnung.
Bracket 10 ist nicht gut, und aber jedes Mal, wenn erinnern
Ich glaube mich zu versuchen, CS50 IDE machen Absturz, indem Sie in falsche Werte,
es muss nicht immer zusammenwirken, und in der Tat, Sie oft
Glück nur, weil die Betriebssystem nicht
feststellen, dass Sie immer so leicht passieren einige Teil des Speichers,
weil Sie in technisch blieb Ihr Segment, aber mehr dazu
in einem Betriebssystem-Klasse, und so etwas wie dieses
könnte sehr leicht unentdeckt bleiben.
Ihr Programm wird nie zum Absturz konsequent, aber vielleicht einmal in eine Weile.
>> Und so wollen wir versuchen valgrind auf dieser, und hier ist,
wo wir überwältigt erhalten durch das Ausgangssignal vorübergehend.
So stellen Speicher valgrind Leckprüfung gleich Vollpunktstrich Speicher.
Und hier ist, warum ich verspreche, dies würde zu überwältigen.
Hier ist, was valgrind, hier ist was ein Programmierer, ein paar Jahre AGO
beschlossen, es wäre eine gute Idee, Für die Ausgabe aussehen.
Lassen Sie uns also einen Sinn dafür.
Also den ganzen Weg auf der linken Seite für keinen guten Grund
die Prozess-ID des Programms wir gerade laufen, die eindeutige Kennung
für das Programm, das wir gerade lief.
Wir gelöscht, dass aus der Schieber, aber es
einige nützliche Informationen hier.
>> Lassen Sie uns nach oben an die Spitze.
Hier ist, wo wir begannen.
Es ist also gar nicht so viel ausgegeben.
Hier ist, dass ungültige Schreib der Größe 4 in Zeile 21.
Nun, was war die Leitung 21?
Zeile 21 war genau das, Diese und es ist sinn
dass ich in rechtsgültig Schreiben 4 Bytes, weil ich
versuchen, diese ganze Zahl ausgedrückt, was alles sein könnte,
es passiert einfach zu sein, Null, aber ich versuche,
um es an einer Stelle setzen das nicht zu mir gehören.
Darüber hinaus hier unten, 40 Bytes in einem Blöcke werden auf jeden Fall in Rekord 1 verloren.
Das ist, weil, wenn ich rufe malloc hier, ich nie wirklich den Speicher frei.
>> Wie können wir dieses Problem beheben?
Lassen Sie mich voran gehen und ein wenig sicherer und tun es 9 und lassen Sie mich hier kostenlos x.
Dies ist die neue Funktion für heute.
Wenn ich nun erneut stellen Speicherpunktstrich, lassen Sie uns laufen valgrind darauf wieder,
maximieren meinem Fenster und drücken Sie Enter.
Nun, es ist gut.
Sie begraben die gute Nachricht in all diesen Ausgang.
Alle Haufen blockiert waren frei.
Wir kommen wieder zu dem, was dem Heap kommen ist, aber keine Lecks sind möglich.
So ist das nur eine Werkzeug für Ihren Werkzeugkasten
mit denen Sie zu starten Finde jetzt Fehler so.
>> Aber mal sehen, was mehr kann schief gehen.
Lassen Sie uns nun auf Übergangs tatsächlich ein Problem zu lösen.
Nebenbei bemerkt, wenn dadurch eine Linderung wenig Verwirrung oder Spannung,
das ist jetzt lustig.
Ja.
Das ist ziemlich gut.
Da Zeiger sind Adressen und Adressen
sind in der Regel durch Konvention mit hexadezimal geschrieben.
Ha, ha, das ist jetzt lustig.
Wie auch immer, also lassen Sie uns jetzt tatsächlich ein Problem zu lösen.
Dies war super, Super-Low-Level so weit,
und wir können wirklich nützlich machen Dinge mit diesen Low-Level-Details.
>> So haben wir ein paar Wochen Vor der Begriff eines Arrays.
Ein Array war schön, weil es ist schwer zu bereinigen, unseren Code
denn wenn wir auf ein Schreiben wollte Programm mit mehreren Studenten
oder mehrere Namen und Häuser und Schlafsäle und Fachhochschulen und all das,
wir alles mehr speichern könnte sauber innerhalb eines Arrays.
Aber schlagen ein Nachteil eines Arrays bisher.
Selbst wenn Sie noch nicht gelitten it yourself in einem Programm, nur instinktiv,
Was ist eine schlechte Sache zu einem Array, vielleicht?
Ich habe gehört, einige Murmeln.
Publikum: Es ist schwierig, um die Größe zu ändern.
DAVID MALAN: Es ist schwierig, um die Größe zu ändern.
Sie können die Größe nicht ändern einer Anordnung, in der Tat an sich
in C. Sie können ein anderes Array zuzuordnen, bewegen alles, was von der alten
in die neue, jetzt haben etwas mehr Platz,
aber es ist nicht wie ein Sprache wie Java oder Python
oder eine beliebige Anzahl anderer Sprachen, mit denen einige von euch
vielleicht kennen, wo Sie kann nur halten das Hinzufügen Dinge
Überdruss an das Ende eines Arrays.
Wenn Sie ein Array von haben Größe 6, die seine Größe ist,
und so sehr wie die Idee früher mit einem Puffer einer bestimmten Größe,
Sie aus dem Tor erraten welche Größe Sie wollen, dass es sein?
Wenn Sie zu groß denke, Sie verschwenden Speicherplatz sind.
Wenn Sie zu klein raten, du kann, dass die Daten nicht zu speichern, zumindest
ohne viel mehr Arbeit.
>> So heute, dank Zeiger, können wir beginnen Zusammennähen eigene benutzerdefinierte
Datenstrukturen und der Tat, hier ist etwas,
, dass ein wenig mehr sieht kryptische auf den ersten Blick
aber das ist, was wir nennen eine verknüpfte Liste, und sein Name Art fasst zusammen
es.
Es ist eine Liste von Zahlen, oder in diesem Fall wird eine Liste von Zahlen,
aber es könnte eine Liste der alles sein, aber es miteinander über einen Pfeil verbunden,
und nehmen Sie nur eine Vermutung, mit welcher Technik
wir werden zu können zusammen zu nähen,
Art wie Popcorn mit einem Gewinde, eine verkettete Listen Recht hier?
Seine Zahlen?
Was ist die zugrunde liegende Sprache-Funktion?
>> Publikum: Ein Zeiger.
>> DAVID MALAN: Ein Zeiger.
So jede dieser Pfeile stellt hier ein Zeiger oder einfach nur eine Adresse.
Also mit anderen Worten, wenn ich will, um eine Liste von Nummern zu speichern,
Ich kann nicht einfach speichern Sie es, wenn ich will die Fähigkeit zu wachsen und schrumpfen
Mein-Datenstruktur in einem Array.
Also muss ich ein wenig haben mehr Raffinesse,
aber feststellen, dass dieses Bild Art schlägt
dass, wenn Sie gerade wenig Threads habe alles miteinander verbindet,
ist wahrscheinlich nicht so schwer, Platz zu schaffen zwischen zwei von diesen Recht
oder zwei dieser Knoten, wie wir starten indem er sie in einen neuen Knoten setzen,
und dann mit einigen neuen Thread, nur Graben die drei Knoten zusammen,
die erste, die letzte und die eine dass Sie gerade in die Mitte eingesetzt.
>> Und in der Tat eine verkettete Liste, Im Gegensatz zu einer Anordnung, ist dynamisch.
Es kann wachsen und es kann schrumpfen und Sie dies nicht tun
müssen wissen oder Pflege im Voraus, wie viele Daten Sie gehst zu speichern,
aber es stellt sich heraus, wir müssen ein wenig vorsichtig sein, wie dies zu implementieren.
Also lassen Sie uns zuerst überlegen, wie wir implementieren eine dieser kleinen Rechtecken.
Es ist einfach, einen int zu implementieren.
Sie sagen, nur int n und dann erhalten Sie 4 Byte für ein int,
aber wie kann ich einen int zu erhalten, rufen Sie n, und dann ein Zeiger, nennen wir es nächsten.
Wir könnten diese nennen Dinge, was wir wollen
aber ich brauche eine benutzerdefinierte Datenstruktur.
Ja?
>> ZIELGRUPPE: Ampersand [unverständlich].
>> DAVID MALAN: So kaufmännisches Und wir werden zu bedienen Holen Sie sich die Adresse eines Knotens möglicherweise.
Aber wir brauchen eine andere Merkmal C, um
mir die Möglichkeit zu schaffen, um zu geben dieser Brauch Rechteck, dieser Brauch
variable wenn man so will, in Erinnerung.
Publikum: Ein struct.
DAVID MALAN: Eine Struktur.
Daran erinnern, aus der vergangenen Woche führten wir struct, diese relativ einfache Schlüsselwort
dass lässt uns die Dinge wie diese.
C nicht mit einer Daten kommen Struktur namens Student.
Es kommt mit int und float und Saibling und solche, jedoch nicht mit Studenten kommen,
aber wir können einen Studenten-Datentyp zu erstellen, Student-Struktur, mit dieser Syntax
Hier.
Und Sie werden das immer wieder zu sehen.
Seien Sie also nicht zu befürchten Speichern der Keywords,
aber das Schlüsselwort, das wichtige ist nur die Tatsache, dass wir die Struktur
und dann riefen wir Studenten und innen des Studenten war ein Name und ein Haus
oder ein Wohnheim oder dergleichen.
>> Und nun heute, lassen Sie schlagen diese.
Ich habe ein paar Worte hinzugefügt, aber wenn ich will, dieses Rechtecks, das ist zu implementieren
erhielt sowohl einen int und eine Zeiger, weißt du was, ich bin
gehen, um eine Struktur namens Knoten erklären.
Ich bin auch, in der es, sagen dass ein Knoten, dieses Rechteck, eine int
und wir nennen es n und es hat eine nächste Zeiger.
Und das ist ein wenig ausführlicher, aber wenn man darüber nachdenkt,
Die Pfeile, die im Bild waren vor einem Augenblick sind von dem, was Datentyp?
Wo jeder dieser Pfeile wird zeigen um welche Art von Datenstruktur?
Es ist nicht nur in ein int an sich zeigt.
Es ist, um die Zeige ganze rechteckige Ding
und das rechteckige Ding, wir gesagt, wird als ein Knoten.
Und so haben wir Art müssen rekursiv definieren diese wie
dass ein Knoten, sagen wir mal, wird einen int namens n enthalten
und einen Zeiger namens nächsten und der Art der Datenstruktur, an welche
dass Zeiger ist offenbar werde struct Knoten sein.
>> Also das ist ärgerlich verbose und nur pedantisch zu sein,
der Grund, warum wir es nicht können nur sagen, das, was ehrlich gesagt
sieht viel besser lesbar, Denn daran erinnern, dass zu lesen C
Dinge, von oben nach unten, von links nach rechts.
Es ist nicht, bis wir das Semikolon zu bekommen dass das Schlüsselwort Knoten tatsächlich existiert.
Also, wenn wir wollen, dass diese Art von haben zyklischen Verweis innerhalb des Daten
Struktur, um dies zu tun müssen wir gegebenen wir sagen struct Knoten an der Spitze, die
gibt uns einen längeren Weg zur Beschreibung dieses Sache, dann im Inneren wir sagen struct node,
und dann an der letzten Zeile wir sagen, alles in Ordnung, C, übrigens,
dieses ganze verdammte rufen Sie einfach was ein Knoten und zu stoppen
mit dem Schlüsselwort struct insgesamt.
Also das ist einfach irgendwie eine syntaktische Trick, schließlich lässt uns erstellen
etwas, das genau so aussieht.
>> Wenn wir nun an, wir können implementieren diese Sache in C,
wie können wir tatsächlich Start durchqueren das?
Nun, in der Tat ist alles, was wir tun müssen, Iteration von links nach rechts und einfach
Art von Knoten einfügen oder Knoten zu löschen oder suchen Sie nach Dingen, wo immer wir wollen,
aber um dies zu tun, gehen Sie voran und machen die Dinge ein wenig mehr real, weil diese
hat Super-Low-Level war so weit.
Würde jemand buchstäblich wie Erste sein?
OK.
Komm auf.
Wie heißen Sie?
>> DAVID: David.
DAVID MALAN: David.
Nett, dich zu treffen.
Ich auch.
Gut.
Und wir brauchen eine Nummer 9.
Nicht so gut wie erste, vielleicht.
OK, Nummer 9.
Eine Reihe 17, bitte.
Lassen Sie mich gehen zurück ein wenig weiter.
Number 22, bitte, und wie wäre es weiter zurück
wenn ich keine Hände zu sehen mit all dem Licht oder nicht.
Jemand wird genau dort freiwillig.
Wollen Sie kommen?
Unterarm zwangsweise nach oben entwickelt.
OK, 17.
22.
26 herab.
Würde jemand gerne forcefully-- Komm up.
Eine tatsächliche Freiwilligen.
>> So sehr schnell, wenn euch könnte arrangieren
euch genau wie die Knoten auf dem Bildschirm.
Danke.
Und Sie werden 26 sein.
Alle rechte und schnelle Einführungen.
Also ich bin David und Sie auch?
DAVID: David.
DAVID MALAN: Und Sie sind?
JAKE: Jake.
SUE: Sue.
Alex: Alex.
RAPHAEL: Raphael.
TAYLOR: Taylor.
DAVID MALAN: Taylor.
Ausgezeichnet.
Das sind unsere Freiwilligen für heute und gehen Sie voran
und Schicht ein wenig so, und gehen Sie einfach weiter und halten Sie
Halten Sie Ihre Zahlen, wie Sie sind oder Ihr erste Zeichen und mit der linken Hand,
gehen Sie voran und einfach zu implementieren diese Pfeile, nur
so dass Ihre linke Hand ist buchstäblich zeigt auf, was Sie möchte darauf hinweisen,
an, und etwas Raum, damit geben Sie sich können wir visuell sehen Sie die Arme tatsächlich
zeigen, und Sie müssen nur darauf hinweisen können Art auf den Boden ist in Ordnung.
>> Hier haben wir also eine verknüpfte Liste von ein, zwei, drei, vier, fünf Knoten anfänglich
und bemerken wir diesen speziellen Zeiger auf den Anfang, wer
Schlüssel, denn wir haben den Überblick zu behalten der Gesamtlänge Liste irgendwie.
Diese Jungs, auch wenn sie sind links nach rechts, zurück auf im Speicher sichern,
sie können tatsächlich überall sein in den Speicher des Computers.
Also diese Jungs könnten stehen überall auf der Bühne
und das ist in Ordnung, so lange, wie sie sind tatsächlich einander zeigen,
sondern um die Dinge sauber und einfach, wir
nur ziehen sie von links nach rechts, wie dies, aber es könnte massiven Lücken
zwischen diesen Knoten.
>> Nun, wenn ich tatsächlich einzufügen einige neuen Wert, gehen Sie vor und tun dies.
Wir haben die Chance jetzt einen anderen Knoten zu wählen.
Sagen lassen Sie uns beginnen mit mallocing 55.
Würde jemand dagegen, malloc?
OK, komm herauf.
Wie heißen Sie?
RAINBOW: Regenbogen.
DAVID MALAN: Regenbogen?
Gut.
Malloc Regenbogen.
Komm auf.
So, jetzt haben wir uns fragen, algorithmisch, wo wir 55 gesetzt.
So wissen wir alle, offensichtlich, wo sie wahrscheinlich
gehört, wenn wir versuchen, halten diese sortiert
und wenn euch könnte man nehmen Schritt zurück, so dass wir fallen nicht ab
die Bühne, das wäre toll.
Also eigentlich, Regenbogen, vorne beginnen hier bei mir,
weil wir wie der Computer können nun nur eine Variable sehen, zu einer Zeit.
So dass, wenn dies der erste Knoten.
Beachten Sie, dass er nicht ein Knoten, er ist nur ein Zeiger,
und das ist, warum er gezogen zu sein nur die Größe eines Zeigers nicht
einer jener vollen Rechtecke.
So werden wir bei jedem Check Iteration 55 weniger als 9?
Nein.
55 weniger als 17?
Nein.
Weniger als 22?
Weniger als 26?
Weniger als 34?
Und nun, offensichtlich Regenbogen gehört am Ende.
So klar zu sein, und was war Ihr Name, Taylor?
>> TAYLOR: Taylor.
DAVID MALAN: So unter Taylors linke Hand und Regenbogen-Hände hier,
dessen Hand braucht, um über das, was in Punkt um Beiträge in dieser Liste einfügen 55?
Was müssen wir tun?
Ja?
>> ZIELGRUPPE: Taylor Hand muss links zeigen.
>> DAVID MALAN: Genau.
So Einfügen eines Knotens in das Ende der Liste
ist ziemlich einfach, weil Taylor gerade muss an den Massepunkt anstelle
oder wir nennen es null, null ist eine Art der Abwesenheit
eines Zeigers oder eines speziellen Null-Zeiger, du bist
gehen, um mit dem linken Punkt Hand an der Regenbogen und Regenbogen,
wo soll der linken Hand wahrscheinlich zeigen?
Down.
Es ist nicht gut, wenn ihre Hand ist eine Art des Zeigens weg hier, oder jede Art von
welche Richtung.
Das wäre in Betracht gezogen werden ein Müllwert,
aber wenn sie verweist auf einige bekannte Wert, werden wir
nennen es null oder null, das ist OK, denn wir haben eine Laufzeit in diesem
und wir wissen, die Liste ist nun abgeschlossen.
>> Also, was ist ein weiterer relativ einfachen Fall?
Könnten wir malloc 5?
Komm auf.
Wie heißen Sie?
TIFFANY: Tiffany.
DAVID MALAN: Es tut mir leid?
TIFFANY: Tiffany.
DAVID MALAN: Tiffany.
Gut.
Tiffany wurde malloced mit dem Wert 5.
Komm auf.
Das hier ist relativ einfach, auch, aber laßt uns überlegen Reihenfolge der Operationen jetzt.
Es war recht einfach mit Taylor am Ende.
Nummer 5 ist natürlich weniger als 9, und so haben wir David, wir haben Tiffany,
und was war Ihr Name?
>> JAKE: Jake.
>> DAVID MALAN: Jake.
Tiffany, Jake und David.
Dessen Hand sollte zuerst aktualisiert werden?
Was wollen Sie hier?
Es gibt ein paar Möglichkeiten, aber es gibt auch eine oder mehrere falsche Wege.
>> ZIELGRUPPE: Beginnen Sie mit ganz links.
>> DAVID MALAN: Beginnen Sie mit der am weitesten links.
Wer ist der am weitesten links dann hier?
ZIELGRUPPE: Erstens.
>> DAVID MALAN: OK.
Also mit zum ersten Mal starten und wo sehen Sie aktualisieren möchten Davids Händen zu sein?
Publikum: Auf dem Weg zur 5.
DAVID MALAN: OK.
Und David, zeigen an fünf oder Tiffany hier, und jetzt?
>> ZIELGRUPPE: Tiffany weist auf die 9?
DAVID MALAN: Perfect, außer Binkys Kopf nur irgendwie fiel, nicht wahr?
Denn was ist los mit Dieses Bild wörtlich?
ZIELGRUPPE: Nichts zeigt.
DAVID MALAN: Nichts ist zeigt auf Jake jetzt.
Wir haben buchstäblich verwaiste 9 und 17, und wir haben buchstäblich
durchgesickert all dieses Speichers, denn durch Aktualisieren ersten Davids Hand, das ist,
Fein soweit sie korrekt ist zeigt auf Tiffany jetzt,
aber wenn niemand hatte die Weitsicht, um Jake hinweisen,
dann haben wir verloren haben, die Gesamtheit dieser Liste.
Lassen Sie uns also rückgängig zu machen.
Das war also eine gute Sache, stolpern, aber lassen Sie uns jetzt zu korrigieren.
Was sollen wir tun ersten statt?
Ja?
>> ZIELGRUPPE: Tiffany sollte an der 9-Punkt?
DAVID MALAN: Ich kann nicht bekommen, dass in Ihrer Nähe.
Wer sollte an der 9-Punkt?
>> ZIELGRUPPE: Tiffany.
>> DAVID MALAN: Alles klar.
So sollte Tiffany ersten Punkt an der 9.
So Tiffany nehmen sollte auf einem identischen Wert
David, die scheint, redundanten für einen Moment,
aber das ist in Ordnung, denn jetzt, die zweite Schritt können wir Davids Hand aktualisieren
bei Tiffany Punkt, und dann, wenn wir nur irgendwie saubere Dinge
als ob dies Art von federartigen, nun, das ist eine korrekte Insertion.
So ausgezeichnet.
So, jetzt wir sind fast da.
Lassen Sie uns stecken Sie ein Abschluss Wert wie der Wert 20.
Wenn wir eine letzte Freiwilligen malloc?
Komm auf.
Also das hier ist ein wenig komplizierter.
Aber wirklich, der Code sind wir Schreiben, wenn auch mündlich,
ist genau wie mit einem Bündel der, wenn die Bedingungen jetzt, nicht wahr?
Wir hatten eine Bedingung Überprüfung, ob sie gehört
am Ende, vielleicht Anfang.
Wir brauchen eine Art Schleife finden Sie den Punkt in der Mitte.
Lassen Sie uns so tun, mit dem, was ist Ihr Name?
>> ERIC: Eric.
>> DAVID MALAN: Eric?
Eric.
Nett, dich zu treffen.
Wir haben also 20.
Weniger als fünf?
Nein.
Weniger als neun?
Nein.
Weniger als 17?
Nein.
OK.
Er gehört hier und Ihre Namen sind wieder?
SUE: Sue.
DAVID MALAN: Sue.
Alex: Alex.
DAVID MALAN: Sue, Alex, und?
ERIC: Eric.
DAVID MALAN: Eric.
Deren Hände müssen zuerst aktualisiert?
>> ZIELGRUPPE: Eric.
OK.
So Erics sollte in dem Punkt?
22.
Gut.
Und jetzt, was kommt als nächstes?
Sue kann dann an der Eric-Punkt und jetzt, wenn Sie Kerle gerade
machen einige Zimmer, was in Ordnung ist visuell, jetzt haben wir das Einsetzen durchgeführt.
Also lassen Sie uns betrachten nun eine Frage, aber danke Ihnen so sehr für unsere Freiwilligen.
Sehr gut gemacht.
Sie können diejenigen zu halten, wenn Sie möchten.
Und wir haben ein schönes Abschiedsgeschenk, wenn Sie würden jeder gerne eine Stress-Ball statt.
Lassen Sie mich nur leiten Sie diese nach unten.
Also, was ist das Mitnehmen von diesem?
Das scheint unglaublich zu sein insofern, als wir jetzt haben,
um ein eingeführtes eine alternative Array, das nicht so eingeschlossen ist
einem Array von einigen feste Größe.
Sie können dynamisch wachsen.
>> Aber so wie wir in Wochen gesehen Vergangenheit haben wir nie etwas bekommen kostenlos,
wie sicher es ist ein Trade-off hier.
So mit einem Kopf einer Linked Liste, das ist Dynamik?
Diese Fähigkeit zu wachsen und ehrlich gesagt, könnten wir löschen getan haben
und wir konnten zu schrumpfen, wie gebraucht.
Welchen Preis zahlen wir?
Doppelt so viel Platz, in erster Linie.
Wenn Sie das Bild betrachten, nicht mehr Ich bin Speichern einer Liste von Zahlen.
Ich Speichern einer Liste von Zahlen und Zeiger.
Also ich bin eine Verdoppelung der Menge an Speicherplatz.
Nun, vielleicht ist das nicht so eine große Sache, 4 Bytes, 8 Bytes,
aber es könnte sicherlich hinzufügen up für große Datenmengen.
Was ist ein weiterer Nachteil?
Ja?
>> Publikum: Wir müssen queren sie einen nach dem anderen.
DAVID MALAN: Ja.
Wir müssen sie durchlaufen einen nach dem anderen.
Weißt du was, gaben wir auf diese super praktische Funktion der eckigen Klammer
Notation, mehr korrekt wie Random Access bekannt,
wo wir gerade springen zu einem einzelnen Element
aber jetzt, wenn ich hatte immer noch meine Freiwillige hier,
wenn ich wollte, das zu finden Nummer 22, kann ich nicht einfach
springe zur Halterung etwas etwas.
Ich muss über die Liste aussehen, viel wie unsere Suchbeispiele linear,
um die Zahl 22 zu finden.
So scheinen wir einen Preis gibt bezahlt haben.
Aber wir können trotzdem lösen andere Probleme.
>> In der Tat, lassen Sie mich vorstellen nur ein paar Visuals.
Also, wenn Sie haben bis zu gewesen Mathers Dining Hall vor kurzem,
Sie, denn erinnern an ihre Stapel von Schalen wie diese,
wir geliehen diese aus Annenberg vor der Klasse.
Also dieser Stapel von Ablagen, obwohl, ist repräsentativ tatsächlich
eines Informatik-Datenstruktur.
Es ist eine Datenstruktur in der Informatik
als Stapel bekannt, die sehr schön eignet sich für genau diese Sicht.
Also, wenn jeder dieser Schalen ist kein Tablett, sondern wie eine Nummer, und ich wollte
das Speichern von Rufnummern, I Hier könnte man niedergeschlagen,
und ich konnte ein weiterer hier unten setzen, und weiter Stapelnummern
übereinander, und was möglicherweise hilfreich zu diesem
ist, dass, was die Implikation dieser Datenstruktur?
Welche Zahl kann ich herausziehen zunächst am einfachsten?
Die zuletzt einen Put auf es.
>> Also das ist, was wir nennen würde in Informatik eine LIFO-Datenstruktur.
Last in, first out.
Und wir werden bald sehen, warum das könnte nützlich sein, aber für jetzt,
man denke nur an die Immobilie.
Und es ist ziemlich blöd, wenn Sie denken darüber, wie der Speisesaal tut es.
Jedes Mal, wenn sie sauber und Schalen legte die frischesten diejenigen an der Spitze,
Sie eine zuvor sauber haben könnte aber schließlich sehr schmutzig und staubig
Tablett ganz unten wenn Sie nie
auf den Grund dessen, Stapel, weil Sie gerade
halten Inbetriebnahme der neuen und die saubere diejenigen oben drauf.
Das gleiche kann passieren, in einem Supermarkt zu.
Wenn Sie eine Vitrine haben Milch und jedes Mal, wenn CVS
oder wer bekommt mehr Milch, einfach schieben Sie die Milch
Sie haben bereits auf den Rücken und Sie setzen die neuen vorne,
Sie gehen ein paar ziemlich gemein zu haben sind Milch am Ende der Datenstruktur,
weil es immer am Boden oder äquivalent ist es immer an der Rückseite.
>> Aber es gibt noch einen anderen Weg, um darüber nachzudenken Schlange Daten und zum Beispiel dafür.
Wenn Sie einer jener Menschen sind, die gerne außerhalb der Apple Stores line up
wenn ein neues Produkt kommt Sie, sind Sie wahrscheinlich
nicht mit einem Stapel Daten Struktur, weil Sie
würde entfremden alle anderen, ist Futter bis etwas neues Spielzeug zu kaufen.
Eher wahrscheinlich mit du bist welche Art von Datenstruktur
oder welche Art von System in der realen Welt?
Hoffentlich ist es eine Linie, oder mehr richtig oder mehrere britische artig, eine Warteschlange.
Und es zeigt sich eine Warteschlange ist auch eine Datenstruktur in der Informatik,
aber eine Warteschlange hat eine sehr andere Eigenschaft.
Es ist nicht LIFO.
Last in, first out.
Gott bewahre.
Es ist stattdessen FIFO.
Als Erster rein, als erster raus.
Und das ist eine gute Sache, Fairness willen
sicherlich, wenn Sie Futter sind up Super früh am Morgen.
Wenn Sie es zuerst zu erhalten, können Sie wollen ersten als auch raus.
>> Und so all diese Daten Strukturen, Warteschlangen und Stacks
und Trauben von anderen, stellt sich heraus, die Sie kann dieser nur als ein Array zu denken.
Dies ist ein Array, vielleicht eine feste Größe 4, aber es würde
sein ganz nett, wenn wir nur anhäufen könnten Schalen fast unendlich groß, wenn wir
haben, dass viele Schalen oder Zahlen.
Vielleicht wollen wir verwenden eine verkettete Liste hier,
aber der Kompromiss sein wird möglicherweise, dass wir mehr Speicher,
dauert ein wenig mehr Zeit, aber wir nicht die Höhe des Stapels zu begrenzen,
ähnlich wie Mathers Vitrine könnte die Größe des Stapels zu begrenzen,
und so sind diese Design-Entscheidungen oder Möglichkeiten, die uns letztendlich.
Also mit diesen Daten Strukturen, die wir begonnen haben,
Sehen Sie neue obere Schranken potenziell auf welcher zuvor war super schnell
und wo wir verlassen off heute und wo
wir hoffen, zu bekommen, ist am Mittwoch, werden wir
beginnen mit einer Daten suchen Struktur, die uns suchen können
durch die Daten in Protokollende immer wieder.
Und wir sahen, dass, erinnern, in Woche null und eines mit binäre Suche oder dividieren
und zu erobern.
Es ist noch zurück und besser kommen, der heilige Gral für diesen Mittwoch
wird es sein, sich mit der Datenstruktur, die wirklich läuft
oder theoretisch in konstante Zeit, wobei
es spielt keine Rolle, wie viele Millionen oder Milliarden von Dingen
die in der Datenstruktur haben, wird es nehmen Sie uns konstante Zeit, vielleicht einen Schritt
oder in zwei Schritten oder Stufen 10, aber konstante Anzahl von Schritten
um durch diese Datenstruktur zu suchen.
Dass in der Tat wird der Heilige Gral sein aber mehr dazu am Mittwoch.
Wir sehen uns dann.
>> [Musikwiedergabe]