[Musik zu spielen] David J. MALAN: In Ordnung. Dies ist CS50. Dies ist Woche fünf fort, und wir habe eine gute Nachricht und eine schlechte Nachricht. So gute Nachricht ist, dass CS50 startet an diesem Freitag. Wenn Sie möchten, sich uns anzuschließen, Kopf der üblichen URL hier. Noch bessere Nachricht, keine Vorlesung am kommenden Montag, der 13.. Etwas weniger gute Nachrichten, Quiz Null ist nächsten Mittwoch. Mehr Details kann unter dieser URL finden Sie hier. Und in den nächsten paar Tagen wir werden die Lücken füllt werden im Hinblick auf die Zimmer dass wir reserviert haben. Bessere Nachricht ist, dass es dann sein ein Kurs weiten Überprüfung Sitzung am kommenden Montag in den Abend. Bleiben Sie auf den Kurs Tuned Website für Standort und Details. Abschnitte, obwohl es ein Urlaub, wird auch mit als auch. Beste Nachricht, Vortrag am kommenden Freitag. So ist dies eine Tradition, die wir haben, nach dem Lehrplan. Just-- es wird erstaunlich sein. Sie werden Dinge wie sehen konstanten Zeitdatenstrukturen und Hash-Tabellen und Bäume und Versuche. Und wir werden über Probleme zu sprechen Geburtstag. Eine ganze Reihe von Sachen erwartet am kommenden Freitag. Ok. Sowieso. So erinnern, dass wir schon seit Fokussierung auf dieses Bild von dem, was innerhalb des Speichers unsere Computer. So oder RAM ist, wo Programme existieren, während Sie ihnen bist. Wenn Sie einen Doppelklick auf ein Symbol, um irgendein Programm laufen oder doppelklicken Sie auf eine Symbol, um etwas Datei zu öffnen, es ist von Ihrer Fest geladen fahren oder Solid-State-Laufwerk in den RAM, Random Access Memory, wobei sie lebt, bis sich das Gerät ausschaltet, der Laptop-Deckel schließt, oder Sie das Programm beenden. 

Jetzt, Speicher, der was haben Sie wahrscheinlich 1 Gigabyte in diesen Tagen, 2 Gigabyte oder sogar noch viel mehr, wird im allgemeinen fest für ein gegebenes Programm in dieser Art von rechteckigen Konzeptmodell wobei wir haben den Stapel an der Unterseite und ein paar andere Sachen an der Spitze. Die Sache an der Spitze wir auf diesem Bild gesehen habe vor, aber nie darüber gesprochen ist die sogenannte Textsegment. Textsegment ist nur eine andere Art zu sagen, die Nullen und Einsen, dass komponieren Sie Ihre tatsächlichen kompilierte Programm. 

Also, wenn Sie einen Doppelklick auf Microsoft Word auf Ihrem Mac oder PC, oder wenn Sie Punkt laufen Schrägstrich Mario auf ein Linux-Computer in Ihrem Terminal-Fenster, die Nullen und Einsen, die komponieren Wort oder Mario vorübergehend gespeichert werden im Arbeitsspeicher des Computers in der so genannten Textsegment für ein bestimmtes Programm. Darunter geht initialisiert und nicht initialisierten Daten. Dies ist Sachen wie globale Variablen, dass wir nicht genutzt haben viele, aber gelegentlich wir haben hatte globale Variablen oder statisch definierten Zeichenfolgen, die ist hart codiert Worte wie "Hallo" , die sind nicht vom Benutzer übernommen Das sind in Ihrem Programm hart codiert. 

Jetzt, auf dem Grund wir die sogenannten Stack. Und der Stapel, so weit, wir waren Verwendung für welche Arten von Zwecken? Was ist der Stack für verwendet? Ja? 

ZIELGRUPPE: Funktionen. 

David J. MALAN: Für Funktionen? In welchem ​​Sinn für Funktionen? 

ZIELGRUPPE: Wenn Sie eine Funktion aufrufen, die Argumente auf dem Stapel kopiert. 

David J. MALAN: Genau. Wenn Sie eine Funktion aufrufen, ihre Argumente auf dem Stapel kopiert. So dass alle X oder Y oder A oder B dass Sie in eine Funktion vorbei sind werden vorübergehend anziehen die sogenannten Stack, nur wie eine von der Annenberg Speisesaal Tabletts, und auch Dinge, wie lokale Variablen. Wenn Ihr foo Funktion oder Swap- Funktion haben lokale Variablen, wie Temperatur, die beiden Ende auf dem Stapel. Jetzt werden wir nicht zu viel reden sie, aber diese Variablen an der Unterseite haben wir vor einer Weile, wenn sah Ich wurde an der Tastatur 1 Tag futzing und ich begann den Zugriff auf die Dinge wie argv 100 oder argv 1000, nur elements-- ich vergessen die numbers-- aber, dass sollten auch nicht von mir zugegriffen werden. Wir begannen zu sehen, einige Funky Symbole auf dem Bildschirm. Das waren so genannte Umgebungsvariablen wie globale Einstellungen für meine Programm oder für den Computer, nicht die nicht mit der bisherigen Fehler, die wir diskutiert, Shellshock, das ist schon plagen ganz wenigen Computern. 

Jetzt endlich in der heutigen Fokus wir letztlich auf dem Heap sein. Dies ist ein weiterer Teil des Speichers. Und im Grunde alles Speicher ist das gleiche Zeug. Es ist die gleiche Hardware. Wir sind nur eine Art Behandlung von verschiedenen Clustern Bytes für verschiedene Zwecke. Der Haufen wird sich auch dort sein, wo Variablen und Speicher, die Sie anfordern vom Betriebssystem zwischengelagert wird. 

Aber es ist irgendwie ein Problem hier, wie das Bild bedeutet. Wir haben zwei Art von Schiffe zu kollidieren. Weil, wie Sie mehr und mehr nutzen des Stapels, und wie wir heute sehen, vorwärts, wie Sie mehr und mehr über die Verwendung Haufen, sicherlich schlechte Dinge passieren könnte. Und in der Tat können wir, dass induzieren absichtlich oder unabsichtlich. So der Cliffhanger letzte Zeit war dieses Programm, die keine funktionellen dienen hat anderen Zweck als zu zeigen, wie Sie als ein schlechter Kerl tatsächlich statt Vorteil von Bugs in jemandes Programm und über ein Programm oder auch eine nehmen ganze Computersystem oder Server. Also, nur um einen kurzen Blick, Sie feststellen, dass die Haupt am Boden nimmt in der Kommandozeile Argumente, wie pro argv. Und es hat einen Aufruf einer Funktion f, Wesentlichen eine namenlose Funktion aufgerufen f, und es ist in argv vorbei [1]. 

Also was auch immer Wort der Benutzer zumin die Eingabeaufforderung nach der diesProgrammNamen, und dann diese willkürliche Funktion bis oben, f, nimmt in einem String, AKA char *, wie wir begonnen haben zu diskutieren, und nennt es nur "bar". Aber wir nennen es könnte alles. Und dann erklärt sie, innen F, ein Array von Zeichen c-- 12 solche Zeichen bezeichnet. 

Jetzt, durch die Geschichte, die ich erzählte vor einem Augenblick, wo im Speicher c ist, oder sind diese 12 Zeichen am Ende sich? Nur klar zu sein. Ja? 

ZIELGRUPPE: auf den Stapel. 

David J. MALAN: auf den Stapel. Also c ist eine lokale Variable. Wir suchen 12 Zeichen oder 12 Bytes zu fragen. Diese werden am Ende sich auf der so genannten Stack. Nun endlich ist diese andere Funktion Das ist eigentlich ziemlich nützlich, aber wir haben nicht wirklich genutzt es uns, strncopy. Es bedeutet, String Kopie, sondern nur N Buchstaben, n Zeichen. So n Zeichen werden von bar in c kopiert. Und wie viele? Die Länge der Stange. In anderen Worten, daß eine Zeile, strncopy, wird zu kopieren effektiv Bar in c. 

Jetzt, nur um Art rechnen Die Moral von dieser Geschichte, was ist potentiell problematisch hier? Auch wenn wir die Überprüfung der Länge der Bar und Einleiten in strncopy, Was ist Ihr Gefühl sage, ist noch zu diesem Programm gebrochen? Ja? 

ZIELGRUPPE: Beinhaltet keine Raum für die Null-Zeichen. David J. MALAN: Beinhaltet keine Raum für die Null-Zeichen. Potenziell, in Gegensatz zu bisherigen Praxis wissen wir nicht einmal haben, so viel wie ein plus 1 zu zubringen, dass die Null-Zeichen. Aber es ist noch schlimmer. Was sonst gelingt es uns nicht zu tun? Ja? 

ZIELGRUPPE: [unverständlich] David J. MALAN: Perfect. Wir haben hart codiert 12 ziemlich willkürlich. Das ist nicht so sehr die Problem, aber die Tatsache, dass wir nicht einmal prüfen, ob die Länge der Stange ist kleiner als 12, in diesem Fall, es wird sein sicher ist, es in den Speicher gebracht c genannt, die wir vergeben haben. In der Tat, wenn Bar ist wie 20 Zeichen lang, zu werden Kopien dieser Funktion erscheint 20 Zeichen von bar in c, wodurch Einnahme mindestens 8 Byte dass es nicht sein sollte. Das ist die Implikation. 

Also kurz gesagt, gebrochen Programm. Nicht so eine große Sache. Vielleicht bekommen Sie einen Segmentation Fault. Wir alle haben schon Bugs in Programmen. Wir alle haben möglicherweise Fehler in Programmen jetzt. Aber was ist die Implikation? Nun, hier ist eine gezoomte Version von dass Bild von Speicher meines Computers. Dies ist der Grund meines Stacks. Und in der Tat, ganz unten ist, was aufgerufene Routine Mutter Stapel, andere Art zu sagen, das ist Haupt. So, dass, wer die Funktion aufgerufen f, die wir hier reden. Dies ist also der Unterseite des Stapels. Absenderadresse ist etwas Neues. Es ist immer da gewesen, immer in diesem Bild gewesen. Wir haben einfach nie die Aufmerksamkeit auf sie. Weil es stellt sich heraus, die Art und Weise funktioniert, ist c dass, wenn man eine andere Funktion aufruft, nicht nur die Argumente, das zu tun Funktion auf den Stapel geschoben bekommen, nicht nur lokale Funktion zu tun Variablen gehen auf den Stapel geschoben, einen so genannten Absender-Adresse wird auch auf den Stapel gelegt. Insbesondere dann, wenn Haupt Anrufe Foo, Main eigene Adresse im Speicher, Ochsen etwas, wirksam wird auf den Stapel gelegt so dass, wenn f geschieht Ausführen es weiß, wo man wieder auf die im Text springen Segment, um weiter auszuführen. 

Also, wenn wir hier sind konzeptionell, in Haupt, dann f aufgerufen wird. Wie funktioniert f wissen, wer auf Handsteuerung zurück? Nun, diese kleine Breadcrumb-rot hier rief die Rücksprungadresse, es ist einfach Kontrollen, was ist das Absender-Adresse? Oh, lassen Sie mich zurück zur Haupt hier zu springen. Und das ist ein bisschen einer Vereinfachung, da die Nullen und Einsen für Haupt sind technisch hier in der Tech-Segment. Aber das ist die Idee. f muss nur wissen, was , wo die Steuerung geht letztlich zurück. 

Aber die Art und Weise Computern haben lange auf Dinge gelegt wie lokale Variablen und Argumente wie diese. So in der oberen dieses Bildes in Blau ist die Stapelrahmen für f, so dass alle des Speichers, der f speziell verwendet. So entsprechend, feststellen, dass Bar ist in diesem Bild. Bar war sein Argument. Und wir behauptet, dass Argumente Funktionen bekommen auf dem Stapel abgelegt. Und c, ist natürlich auch in diesem Bild. 

Und nur für Darstellungszwecke Hinweise auf der linken oberen Ecke wird, was c Halterung 0 und dann leicht nach rechts unten c Halterung 11. Also mit anderen Worten, Sie können sich vorstellen dass es ein Gitter von Bytes gibt, die erste ist, oben links, von denen unten ist der letzte der 12 Bytes. 

Aber jetzt versuchen, um vorzuspulen. Was passieren wird, wenn wir weitergeben in einem String-Bar, die länger als c ist? Und wir sind nicht zu überprüfen, ob es ist in der Tat mehr als 12. Welcher Teil des Bildes werde wird von Bytes 0, 1, 2, 3 überschrieben werden, dot dot dot, 11, und dann schlecht, 12, 13 bis 19? Was wird hier passieren, wenn Sie von der Bestellung schließen dass c Klammer 0 ist auf der Oberseite und c Halterung 11 ist eine Art nach unten auf der rechten Seite? Ja? 

ZIELGRUPPE: Nun, es geht die char * bar zu überschreiben. 

David J. MALAN: Ja, es sieht aus wie Sie gehen zu char * bar zu überschreiben. Und schlimmer noch, wenn man in einer wirklich langen senden String, könnten Sie sogar zu überschreiben, was? Die Rücksprungadresse. Die wiederum, ist wie ein Breadcrumb, um das Programm sagen, wo zurück zu gehen, wenn f getan wird aufgerufen. 

Also, was tun bösen Jungs in der Regel ist, wenn sie über ein Programm kommen , dass sie neugierig sind, ob es ausnutzbar, fehlerhaft so dass er oder sie ergreifen kann, Vorteil dieser Bug, Im Allgemeinen sind sie nicht bekommen, dieses Recht das erste Mal. Sie gerade beginnen Sie, zum Beispiel, Zufallszeichenfolgen in Ihrem Programm, ob an der Tastatur, oder offen sie wahrscheinlich schreiben ein kleines Programm, um nur automatisch Saiten, und starten Sie schlugen auf Ihr Programm durch Senden in viele verschiedene Eingänge in unterschiedlichen Längen. 

Sobald Ihr Programm abstürzt, Das ist eine erstaunliche Sache. Weil es bedeutet, dass er oder sie entdeckt hat, was ist wohl in der Tat ein Fehler. Und dann haben sie klüger bekommen können und starten enger Fokussierung auf, wie man diese Fehler auszunutzen. Insbesondere, was er oder sie vielleicht zu tun ist, zu senden, im besten Fall, hallo. Keine große Sache. Es ist eine Zeichenfolge, die ausreichend kurz ist. Aber was, wenn er oder sie sendet, und wir werden es so zu verallgemeinern, Angriff code-- so Nullen und diejenigen, die Dinge tun, rm-rf wie,, die alles entfernen von der Festplatte oder senden Spam oder die Maschine irgendwie anzugreifen? 

So dass, wenn jede von diesen Buchstaben A nur repräsentiert, konzeptionell, Angriff, Angriff, Angriff, Angriff, einige schlechte Code dass jemand anderes geschrieben, aber wenn diese Person ist intelligent genug, zu gehören nicht nur alle dieser rm-RFS, aber auch haben seine letzten paar Bytes sein eine Zahl, entspricht die Adresse seines oder ihre eigenen Angriffscode dass er oder sie in nur weitergegeben indem sie an der Eingabeaufforderung, Sie können effektiv Trick den Computer in bemerken, wenn f ist getan Ausführung, Oh, es ist Zeit für mich, um zu springen zurück zum roten Absenderadresse. Sondern weil er oder sie hat irgendwie überlappen, dass die Rückkehr-Adresse mit ihrer eigenen Nummer, und sie sind intelligent genug, konfiguriert haben, dass Nummer beziehen, wie Sie sehen in der Super-Top- linken Ecke gibt, die tatsächliche Adresse im Computer Erinnerung an einige ihrer Angriffscode, ein schlechter Kerl kann den Computer überlisten in der Ausführung seiner eigenen Code. 

Und dass der Code wieder, kann alles sein. Es ist allgemein als Shell-Code, das nur eine Art zu sagen, dass es nicht in der Regel etwas so einfaches wie rm-rf. Es ist tatsächlich so etwas wie Bash, oder eine aktuelle Programm, das ihm oder ihre programmatische Steuerung ausführen alles andere, was sie wollen. Also kurz gesagt, das alles ergibt sich aus der einfachen Tatsache, , dass dieser Fehler nicht beteiligt Überprüfung die Grenzen des Arrays. Und weil die Art und Weise Computer funktionieren, dass sie den Stapel aus effektiv konzeptionell Boden auf, aber dann die Elemente Sie auf den Stapel schieben wachsen von oben nach unten, Das ist unglaublich problematisch. Nun, es gibt Möglichkeiten, dies zu umgehen. Und ehrlich gesagt, es gibt Sprachen mit denen, dies zu umgehen. Java ist immun, zum Beispiel, zu diesem speziellen Thema. Weil sie nicht geben Ihnen Hinweise. Sie geben nicht Sie Direktspeicheradressen. Also mit dieser Macht, die wir haben , etwas in Erinnerung zu berühren Wir wollen kommt zugegebenermaßen große Gefahr. 

So halten Sie ein Auge. Wenn, ehrlich gesagt, in den Monaten oder Jahre zu kommen, zu jeder Zeit Sie über einige Ausbeutung lesen von einem Programm oder einem Server, wenn Sie jemals einen Hauch von etwas zu sehen wie ein Pufferüberlauf-Angriff, Stack-Überlauf oder eine andere Art des Angriffs, im Geiste, viel wie inspiriert die Website nennen, wenn Sie es wissen, es ist alles nur reden Überlaufen der Größe von einigen Zeichen Array oder Array einige allgemein. Haben Sie Fragen, dann dazu? Versuchen Sie das nicht zu Hause. 

In Ordnung. So malloc bisher hat unsere neu gewesen Freund in dass wir Speicher zuweisen dass wir nicht unbedingt wissen, in Voraus, dass wir wollen, so haben wir nicht hart-Code in unsere Programmnummern wie 12. Sobald der Benutzer sagt uns, wie viel Daten, die er oder sie zur Eingabe will, wir können diese viel Speicher malloc. 

So malloc sich herausstellt, um die Soweit die wir benutzt haben sie, explizit letzten Zeit, und dann Sie Jungs haben es mit für getstring unwissentlich für mehrere Wochen, alle Speicher malloc der stammt aus der sogenannten Heap. Und deshalb getstring zum Beispiel kann der Speicher dynamisch zuzuweisen ohne zu wissen, was du bist gehen, im Voraus zu geben, Hand, die Sie wieder einen Zeiger auf diesen Speicher, und dass Erinnerung ist noch Ihnen zu halten, auch nach getstring Renditen. Da Rückruf, nachdem alle, dass die Stapel wird ständig rauf und runter, auf und ab. Und sobald es geht nach unten, bedeutet, dass jede Speicher diese Funktion verwendet werden, sollten nicht von jemand anderem verwendet werden. Es ist jetzt Müll Werte. 

Aber der Haufen ist hier oben. Und was ist schön zu malloc ist, dass wenn malloc reserviert Speicher hier oben, es ist nicht betroffen, für die überwiegend vom Stapel. Und so jede Funktion zugreifen Speicher, die malloc'd hat, sogar von einer Funktion wie getstring, auch nachdem sie zurückgegeben. 

Nun, das Gegenteil von malloc ist kostenlos. Und in der Tat, die Regel, die Sie brauchen, um die Annahme ist jeder, alle, immer wenn Sie malloc Sie müssen sich frei zu verwenden, schließlich, am selben Zeiger. Die ganze Zeit haben wir geschrieben Buggy, Buggy-Code, aus vielen Gründen. Aber von denen hat mit der CS50-Bibliothek, die selbst ist bewusst Buggy, leckt es Speicher. Jedes Mal, wenn getstring genannt haben in den letzten Wochen fragen wir die Betriebs System, Linux, für das Gedächtnis. Und Sie haben noch nie, wenn es zurück gegeben. Und das ist nicht, in üben, eine gute Sache. 

Und Valgrind, einem der Werkzeuge in Pset 4 eingeführt, dreht sich alles um Ihnen hilft Bugs wie jetzt, dass zu finden. Doch zum Glück für Pset 4 brauchen Sie nicht um den CS50-Bibliothek oder getstring verwenden. So dass alle Fehler in den Speicher zu tun haben letztlich gehen, um Ihre eigenen. 

So malloc ist mehr als nur für diesen Zweck geeignet. Wir können jetzt eigentlich lösen grundlegend andere Probleme, und grundsätzlich mehr Probleme lösen effektiv pro Woche Versprechen Nullen. Bisher ist dies der sexiest Datenstruktur, die wir je hatte. Und Datenstruktur nur, dass ich ein Weg, der Konzeptualisierung Speicher in einer Weise, die über die reine Sprichwort sagt, dies ist ein int, das ist ein Zeichen. Wir können zu Cluster Dinge zusammen zu starten. 

So sah ein Array wie diese. Und was in etwa einer Taste war Array ist, dass es Ihnen Rücken-an-Rücken Brocken Speicher, von denen jeder wird zu der gleichen Art sein, int, int, int, int, char oder char, char, char. Aber es gibt ein paar Nachteile. Dies ist zum Beispiel ein Array der Größe sechs. Angenommen, Sie dieses Array mit sechs füllen Zahlen und dann aus irgendwelchen Gründen, Ihren Benutzer geben will Sie eine siebte Zahl. Wo sehen Sie es? 

Was ist die Lösung, wenn Sie erstellt ein Array auf dem Stapel, beispielsweise nur mit der Woche zwei Notation, die wir eingeführt, von eckigen Klammern mit einer Zahl drin? Nun, Sie haben sechs Zahlen in diesen Feldern. Was würden Sie Ihrem Instinkt sein? Wo wollen Sie damit? 

ZIELGRUPPE: [unverständlich] 

David J. MALAN: Sorry? 

ZIELGRUPPE: Legen Sie es am Ende. 

David J. MALAN: Legen Sie es am Ende. Also einfach auf die rechte, außerhalb dieser Box. Das wäre schön, aber es stellt sich heraus, kann man nicht tun. Denn wenn Sie nicht gefragt haben für diesen Teil des Speichers, es könnte durch Zufall, dass dieser sein wird durch eine andere Variable, haupt. Denken Sie zurück eine Woche oder so, wenn wir fest aus Zamyla und Davin und Gabes Namen im Speicher. Sie waren buchstäblich Zurück, um wieder zurück. So können wir nicht unbedingt Vertrauen, was auch immer die hier ist für mich zu verwenden. 

So was könnte man tun? Nun, einmal bemerkt, dass du brauchen ein Array der Größe sieben, Sie könnten nur Neues Array der Größe sieben dann eine for-Schleife oder einer while-Schleife, kopieren Sie sie in das neue Array, und dann irgendwie nur loswerden Dieses Array oder einfach nicht mehr verwenden. Aber das ist nicht besonders effizient. In kurzen, Arrays lassen Sie sich nicht Sie dynamisch ändern. 

Also auf der einen Seite erhalten Sie Direktzugriff, der unglaublich ist. Denn sie ermöglicht es uns, Dinge zu tun wie Teile und herrsche, binäre Suche, die wir alle haben sprach über auf dem Bildschirm hier. Aber Sie selbst malen in eine Ecke. Sobald Sie schlagen das Ende des Array, Sie eine sehr zu tun haben teure Operation oder schreiben Sie eine ganze Reihe von Code jetzt mit diesem Problem umzugehen. 

So was, wenn wir stattdessen hatte etwas namens eine Liste, oder ein insbesondere verketteten Liste? Was wäre, wenn anstatt Rechtecke Rücken an Rücken an Rücken, wir haben Rechtecke, die ein wenig verlassen wenig Spielraum zwischen ihnen? Und obwohl ich gezogen Bild oder das Bild angepasst von einem der Texte hier, um zurück zu sein Rücken an Rücken sehr ordentlich, in der Realität, eines dieser Rechtecke könnte hier in Erinnerung sein. Einer von ihnen könnte hier sein. Einer von ihnen könnte hier sein, hier, und so weiter. 

Aber was, wenn wir zeichneten, in diesem Fall Pfeile dass irgendwie verknüpfen diese Rechtecke zusammen? In der Tat haben wir eine technische gesehen haben Inkarnation von einem Pfeil. Was haben wir in den letzten verwendet Tage, dass unter der Haube, repräsentiert ein Pfeil? Ein Zeiger, oder? 

So was, wenn statt der nur die Speicherung der Zahlen, wie 9, 17, 22, 26, 34, was ist, wenn wir uns nicht gespeichert nur eine Zahl, sondern ein Zeiger neben jeder solchen Nummer? So dass ähnlich wie Sie einen Thread würde Nadel durch eine ganze Reihe von Stoff, irgendwie binden Dinge zusammen, ähnlich wie möglich wir mit Zeigern, wie durch Pfeile inkarniert hier, Art zusammen zu weben Diese einzelnen Rechtecke durch die effektive Verwendung eines Zeigers neben jeder Zahl, die Punkte bis zu einem gewissen nächste Zahl, dass zeigt auf, der wiederum einige nächste Nummer? In anderen Worten, was wenn wir wollten eigentlich um so etwas zu realisieren? Nun leider diese Rechtecke, mindestens einen mit 9, 17, 22, und so weiter, werden diese nicht mehr schöne Plätze mit einzelnen Zahlen. Der untere, ein Rechteck unter 9, zum Beispiel, stellt dar, was sollte ein Zeiger, 32 Bit. Nun, ich bin noch nicht Kenntnis von einem Datentyp in C, die Ihnen nicht nur einen int aber ein Zeiger ganz. 

Also, was ist die Lösung, wenn wir wollen, unsere eigene Antwort auf diese erfinden? Ja? 

ZIELGRUPPE: [unverständlich] 

David J. MALAN: Was ist das? 

ZIELGRUPPE: Neue Struktur. 

David J. MALAN: Ja, also warum nicht schaffen wir eine neue Struktur, oder in C, eine Struktur? Wir haben Strukturen gesehen, wenn auch nur kurz, wo wir mit einem Schüler-Struktur behandelt wie diese, die einen Namen und ein Haus hatte. In Pset 3 Breakout Sie eine ganze verwendet Haufen von structs-- GRect und GOvals dass Stanford geschaffen Cluster-Informationen zusammen. So was, wenn wir diese gleiche Idee Die Schlüsselwörter "typedef" und "Struktur" und dann einige Schüler-spezifische Dinge, und entwickeln sich diese in die folgenden: typedef struct node-- und Knoten nur eine sehr allgemeine Informatik Begriff für etwas, in einer Datenstruktur, ein Behälter in einer Datenstruktur. Ein Knoten Ich behaupte, ist zu haben, int n, völlig unkompliziert, und dann ein wenig mehr kryptisch, Diese zweite Linie, struct node * Weiter. Aber in weniger technische Begriffe, was ist das zweite Zeile von Code innerhalb der geschweiften Klammern? Ja? 

ZIELGRUPPE: [unverständlich] David J. MALAN: A Zeiger auf einen anderen Knoten. So zwar, Syntax ein wenig kryptisch. Aber wenn man es wörtlich zu lesen, Als nächstes wird der Name der Variablen. Was ist ihr Datentyp? Es ist ein wenig ausführlicher dieses Mal, aber es ist vom Typ struct node *. Jedes Mal, wenn wir etwas Stern gesehen, dass bedeutet, es ist ein Zeiger auf diesen Datentyp. Also das nächste ist offenbar ein Zeiger auf eine Struktur-Knoten. 

Nun, was ist eine Struktur-Knoten? Nun, stellen Sie fest, diejenigen zu sehen gleichen Worte oben rechts. Und in der Tat, Sie sehen auch das Wort "Knoten" hier unten links unten. Und das ist eigentlich nur eine Bequemlichkeit. Beachten Sie, dass in unseren Studenten Definition es ist das Wort "Student" nur einmal. Und das ist, weil ein Student Ziel war nicht selbstreferentiell. Es gibt nichts im Inneren eines Studenten das muss zu einem anderen Schüler darauf hinweisen, persay. Das wäre eine Art sein komisch in der realen Welt. 

Aber mit einem Knoten in einer verknüpften Liste, wollen wir einen Knoten Referenz ein ähnliches Objekt zu sein. Und so bemerken die Veränderung ist hier nicht nur, was innerhalb der geschweiften Klammern. Aber wir haben das Wort "Knoten" hinzufügen Oben sowie Zugabe zu der Boden statt der "Student." Und dies ist nur ein technisches Detail so dass auch hier Ihre Daten Struktur kann selbstbezüglich sein, so dass eine Knoten zu einem anderen Knoten wie zeigen. 

Also, was ist dies letztlich gehen, um für uns? Nun, eines, das Zeug innen ist der Inhalt der Knoten. Dieses Ding hier oben, rechts oben, ist nur so dass auch hier können wir uns beziehen. Und dann die äußerste Sachen, obwohl Knoten ist ein neuer Begriff, vielleicht ist es immer noch die gleiche wie Schüler und was war unter der Haube in SPL. 

Also, wenn wir jetzt beginnen wollte Umsetzung dieser verknüpften Liste, Wie könnten wir übersetzen so etwas wie dies zu codieren? Nun, lassen Sie uns einfach sehen, ein Beispiel eines Programms, tatsächlich nutzt eine verknüpfte Liste. Unter den heutigen Verteilungscode ist ein Programm namens Liste Zero. Und wenn ich dies ich ein super erstellt einfache GUI, Graphical User Interface, Aber es ist wirklich nur printf. Und jetzt habe ich mir ein paar Menü gegeben Optionen- Löschen, Einfügen, Suchen, und Traverse. Und beenden. Dies sind nur gemeinsame Operationen auf ein Datenstruktur als eine Link-Liste bekannt. 

Jetzt, Löschen ist los löschen Sie eine Nummer aus der Liste. Legen Sie los hinzufügen eine Zahl, die der Liste. Suche wird sich freuen für die Nummer in der Liste. Und Quer ist nur eine andere Art zu sagen, zu Fuß durch die Liste, drucken Sie es aus, aber das ist es. Tun Sie es in irgendeiner Weise nicht ändern. 

Also lassen Sie uns versuchen, diese. Fahren wir fort und Typ-2. Und dann bin ich los die Zahl einzufügen, sagen 9. Eingeben. Und jetzt mein Programm ist nur programmiert zu sagen, ist jetzt 9 Liste. Nun, wenn ich weitermachen und Sie wieder einfügen, lassen mich voran gehen und herauszoomen und geben in 17. Jetzt ist meine Liste ist 9, dann 17. Wenn ich wieder einzufügen, lassen Sie uns einen überspringen. Statt 22, wie pro die Bild, das wir haben wurde hier sehen, lassen Sie mich vor springen und fügen Sie 26 weiter. Also werde ich den Typ 26. Die Liste ist als ich erwarte. Aber jetzt, nur um, wenn dieser Code zu sehen wird, flexibel zu sein, lassen Sie mich jetzt Typ 22, die mindestens konzeptionell, wenn wir Vor diesem sortiert, was ja werde ein weiteres Ziel jetzt sein, gehen sollten zwischen 17 und 26. Also schlug ich ein. Tatsächlich funktioniert das. Und so lassen Sie mich jetzt legen Sie die zuletzt, je das Bild, 34. 

In Ordnung. So jetzt lassen Sie mich sehen vor, dass Löschen und Traverse und Suche zu tun, in der Tat, zu arbeiten. In der Tat, wenn ich laufen suchen, lassen Sie uns Suche nach der Hausnummer 22, ein. Es fanden 22. Also das ist, was diese Programmliste Null tut. 

Aber was ist eigentlich los auf, dass diese implementiert? Nun, zuerst muss ich vielleicht, und zwar Ich muss eine Datei namens list0.h. Und irgendwo dort ist dies Linie, typedef, struct Knoten, dann habe ich meine geschweiften Klammern, int n, und dann struct-- was war die Definition? Struct Knoten nächsten. Also müssen wir den Stern. Nun technisch in zu erhalten wir die Gewohnheit, hier zeichnen sie. Sie können sehen und Lehrbücher Online-Referenzen tun es dort. Es ist funktionell gleichwertig. In der Tat ist dies ein wenig mehr typisch. Aber ich werde im Einklang mit dem, was sein wir haben letztes Mal und dies tun. Und dann endlich, ich werde das tun. 

Also in einer Header-Datei irgendwo in list0.h heute ist diese Struktur Definition, und vielleicht noch einige andere Sachen. Inzwischen gibt es in list0c gehen, um ein paar Dinge zu sein. Aber wir werden nur beginnen und diese nicht beenden. List0.h ist eine Datei, ich will in meiner C-Datei enthalten. Und dann irgendwann bin ich werde int haben, haupt ungültig. Und dann bin ich los haben einige to-do ist hier. Ich werde auch eine haben Prototyp, wie nichtig, Suche, int, n, deren Zweck im Leben für ein Element zu suchen. Und dann hier unten Ich behaupte in heutigen Code, nichtig, Suche, int, n, kein Semikolon, sondern offen geschweiften Klammern. Und jetzt will ich irgendwie zu suchen für ein Element in dieser Liste. Aber wir haben nicht genug Informationen auf dem Bildschirm vor. Ich habe nicht wirklich vertreten die Liste selbst. So eine Art, wie wir umsetzen könnten eine verkettete Liste in einem Programm wird ich irgendwie wollen, etwas zu tun wie erkläre hier verlinkten Liste nach oben. Der Einfachheit halber werde ich machen Diese globale, auch wenn wir im Allgemeinen sollte nicht zu viel zu tun. Aber es wird dieses Beispiel zu vereinfachen. Deshalb möchte ich erklären, eine verbundene Liste hier oben. Nun, wie könnte ich das tun? 

Hier ist das Bild einer verketteten Liste. Und ich weiß nicht wirklich weiß im Moment, wie Ich werde über, die gehen so viele Dinge mit nur einem Variable im Speicher. Aber denken Sie sich einen Moment zurück. Die ganze Zeit, die wir hatten Zeichenfolgen, die wir dann offenbarte Arrays sein Zeichen, die wir dann offenbart nur ein Zeiger sein auf das erste Zeichen in einer Reihe von Zeichen, das ist null beendet. So von dieser Logik, und damit Bild Art von Aussaat Ihre Gedanken, was brauchen wir eigentlich in unserem schreiben Code, um eine verkettete Liste vertreten? Wie viele dieser Informationen brauchen wir in C-Code zu erfassen, würden Sie sagen? Ja? 

ZIELGRUPPE: Wir brauchen einen Zeiger auf einen Knoten. DAVID J. MALAN: Ein Zeiger zu einem Knoten. Insbesondere die Knoten würde Ihr Instinkte sein, um einen Zeiger zu halten? 

ZIELGRUPPE: Der erste Knoten. 

David J. MALAN: Ja, wahrscheinlich nur der erste. Und bemerken, die erste Knoten eine unterschiedliche Form. Es ist nur die Hälfte der Größe der Struktur, denn es ist in der Tat nur ein Zeiger. Also, was können Sie tun, ist in der Tat erklären, eine verbundene Liste vom Typ Knoten sein *. Und nennen wir es nur erste und auf Null initialisieren. Also null ist wieder kommen in das Bild hier. Nicht nur ist null als wie ein spezielles verwendet Rückgabewert für Dinge wie getstring und malloc, ist null auch die Null Zeiger, das Fehlen eines Zeigers, wenn man so will. Es bedeutet nur, nichts ist noch hier. Nun zuerst, ich hätte in nannte dies nichts. Ich könnte es "Liste" genannt haben oder beliebig viele andere Dinge. Aber ich nannte es "erste", so dass es reiht sich mit diesem Bild. So wie bei einem String dargestellt werden kann mit der Adresse des ersten Byte, so kann eine verkettete Liste. Und wir werden andere Daten zu sehen Strukturen dargestellt werden mit nur einem Zeiger, eine 32-Bit-Pfeil, auf den ersten Knoten in der Struktur. 

Aber jetzt wollen wir rechnen mit einem Problem. Wenn ich nur die Erinnerung in meinem Programm die Adresse der erste Knoten die erste Rechteck in dieser Datenstruktur, Was hatte den Fall besser über die sein Umsetzung der Rest meiner Liste? Was ist ein Schlüssel Detail, das geht , um sicherzustellen, dies tatsächlich funktioniert? Und mit "tatsächlich funktioniert:" Ich bedeuten, ähnlich wie ein String, lässt uns vom ersten Zeichen gehen in Davin Name auf die zweite, auf die dritte, um das vierte, bis zum Ende, wie wir wissen, wenn wir am Ende sind einer verketteten Liste, die so aussieht? Wenn es null. Und ich habe diese Art von, wie dargestellt wie ein Elektroingenieur Macht, mit der kleinen Masse Symbol der Arten. Aber das bedeutet nur, in diesem Fall null. Sie können eine beliebige Anzahl zeichnen von Möglichkeiten, aber dieser Autor passiert, dieses Symbol hier zu verwenden. 

So lange, wie wir Bespannen Alle diese Knoten miteinander, nur erinnern, wo die erste ist, so lange als wir einen speziellen Symbol der letzte Knoten in der Liste, und wir null zu verwenden, weil das ist, was wir haben, die uns zur Verfügung, diese Liste vollständig ist. Und selbst wenn ich nur geben Ihnen einen Zeiger auf das erste Element, du, der Programmierer, kann sicherlich zugreifen den Rest von ihm. Aber lassen Sie uns lassen Sie Ihre Gedanken wandern ein wenig, wenn sie nicht bereits ganz wandered-- was werde die Laufzeit sein nichts in dieser Liste zu finden? Verdammt, es ist groß O von n, was nicht schlecht ist, in Fairness. Es ist jedoch linear. Wir haben welche Funktion gegeben von Arrays, indem mehr dieses Bild dynamisch zu miteinander verwoben oder verknüpften Knoten? Wir haben uns mit wahlfreiem Zugriff gegeben. Ein Array ist schön, weil mathematisch alles ist wieder nach hinten, um wieder zurück. Auch wenn dieses Bild sieht ziemlich, und selbst wenn es aussieht wie dieser Knoten , sind schön Abstand voneinander in der Realität sie überall sein könnte. Ox1, OX50, Ox123, Ox99, diese Knoten könnte überall sein. Da tut malloc Speicher zuweisen aus dem Haufen, aber überall in den Haufen. Sie müssen nicht unbedingt wissen, dass es gehen, zurück zu sein, um wieder zurück. Und so das Bild in der Realität ist nicht zu recht, dieses hübsche. 

Also, es wird ein bisschen dauern arbeiten, um diese Funktion zu implementieren. Also lassen Sie uns jetzt suchen implementieren. Und wir werden sehen, eine Art von cleverer Weg, dies zu tun. Also, wenn ich bin eine Suchfunktion und Ich bin bei einer Variable, I n zu suchen, ich muss das wissen, neue Syntax für den Blick in einer Struktur, die es zeigte auf, bis n zu finden. Also lassen Sie uns dies tun. 

Also zuerst werde ich gehen vor und erklären, einen Knoten *. Und ich werde es nennen Zeiger, nur durch Konvention. Und ich werde es zuerst initialisieren. Und jetzt kann ich dies tun in einer Reihe von Möglichkeiten. Aber ich werde um einen gemeinsamen Ansatz zu nehmen. Während Zeiger nicht gleich null, und das ist die gültige Syntax. Und es bedeutet nur, gehen Sie wie folgt, so Solange sind Sie nicht an nichts zeigt. Was will ich tun? 

Wenn Zeiger Punkt n, lassen Sie mich zurückkommen auf, dass gleich equals-- was? Welchen Wert soll ich suchen? Die eigentliche n, die übergeben wurde. Also hier ist ein weiteres Merkmal von C und vielen Sprachen. Obwohl die Struktur, die als Knoten hat einen Wert n, völlig legitim , auch eine lokale Argument oder Variable n bezeichnet. Weil auch wir, mit menschliche Auge unterscheiden kann dass diese n ist vermutlich unterscheidet sich von diesem n. Weil die Syntax ist anders. Sie haben einen Punkt und einen Zeiger bekam, wohingegen diese hat so etwas nicht. Also das ist OK. Das ist in Ordnung, sie die gleichen Dinge nennen. 

Wenn ich Sie diese, ich bin etwas tun zu wollen, wie bekannt geben, dass wir fanden, n. Und wir werden, dass als verlassen Kommentare oder Pseudocode. Anderes, und hier ist der interessante Teil, was will ich, wenn der aktuelle Knoten zu tun nicht mit n, die mir wichtig? Wie kann ich die folgende zu erreichen? Wenn meine Finger auf die Moment PTR, und es ist zeigt auf, was auch immer ersten Hinweis auf, wie kann ich meine Finger bewegen an den nächsten Knoten im Code? Nun, was ist der Breadcrumb wir sind gehen in diesem Fall zu folgen? ZIELGRUPPE: [unverständlich]. David J. MALAN: Ja, also das nächste. Also, wenn ich zurück in mein Code hier, ja, ich bin werde weitergehen und sagen, Zeiger, der ist nur eine vorübergehende variable-- es ist ein komischer Name, ptr, aber es ist genau wie temp-- Ich werde Zeiger gesetzt gleich welcher Zeiger ist-- und immer wieder, das wird eine sein wenig buggy für einen Punkt neben moment--. Mit anderen Worten, ich werde mein nehmen Finger, die an diesem Knoten zeigen ist hier, und ich werde sagen, Sie wissen, was, werfen Sie einen Blick auf das nächste Feld und bewegen Sie Ihren Finger, um was auch immer es ist, der auf. Und dies wird zu gehen wiederholen, wiederholen, wiederholen. Aber wann ist mein Finger stoppen haupt etwas zu tun? Sobald was Codezeile Tritte in? ZIELGRUPPE: [unverständlich] David J. MALAN: Wenn Punkt während Zeiger nicht gleich null. An einem gewissen Punkt meine Finger werde bei null gerichtet sein und ich werde zu erkennen, das ist das Ende dieser Liste. Nun, dies ist ein wenig Notlüge für Einfachheit. Es stellt sich heraus, dass, obwohl wir gerade gelernt, diese Punktnotation Strukturen, ist nicht eine Struktur Zeiger. ptr ist was? Nur um mehr pingelig. Es ist ein Zeiger zu einem Knoten. Es ist nicht ein Knoten selbst. Wenn ich hier keinen Stern, Zeiger absolutely-- es ist ein Knoten. Das ist wie eine Woche Deklaration einer Variablen, Obwohl das Wort "Knoten" ist neu. 

Aber sobald wir die Einführung einer Stern, ist es jetzt ein Zeiger zu einem Knoten. Und leider können Sie nicht die Punkt-Notation für einen Zeiger. Sie haben, um den Pfeil zu verwenden Notation, die, auffallend, ist das erste Mal, jedes Stück von Syntax sieht intuitiv. Das sieht buchstäblich wie ein Pfeil. Und so, das ist eine gute Sache. Und hier unten buchstäblich sieht aus wie ein Pfeil. Also ich denke, das ist die la-- ich nicht glaube, ich bin über begehen hier-- ich denke, das ist der letzte neue Stück der Syntax, wir werden sehen. Und Gott sei Dank, es ist in der Tat ein wenig intuitiv. 

Nun, für diejenigen von Ihnen, die vielleicht lieber auf die alte Weise, Sie können immer noch die Punktnotation. Aber nach Montag Gespräche, die wir zuerst müssen, dorthin zu gehen, gehen Sie zu, dass anzugehen, und dann auf das Feld. Also das ist auch richtig. Und ehrlich gesagt, ist dies ein wenig mehr pedantisch. Sie sind buchstäblich sagen, dereferenzieren der Zeiger und dorthin zu gehen. Dann greifen · n, das Feld als n. Aber ehrlich gesagt, niemand will zu schreiben oder zu lesen diese. Und so ist die Welt erfunden der Pfeil-Notation, die entspricht, identisch ist, es ist nur syntaktischer Zucker. So eine Art zu sagen diese sieht besser aus, oder sieht einfacher. 

So, jetzt werde ich noch eine andere Sache zu tun. Ich werde sagen, "Pause" habe ich einmal Ich fand es so nicht zu halten, es zu suchen. Aber das ist der Kern einer Suchfunktion. Aber es ist viel einfacher, in die Ende nicht, um den Code zu gehen. Dies ist in der Tat die formale Umsetzung der Suche in der heutigen Verteilung Code. Ich wage zu sagen, dass Einsatz ist nicht besonders Spaß zu Fuß durch optisch, noch ist zu löschen, auch wenn am Ende des Tages sie laufen auf recht einfache Heuristiken. 

Also lassen Sie uns dies tun. Wenn du mich hier Humor, habe ich bringen eine Reihe von Stress-Bälle. Ich brachte eine Reihe von Zahlen. Und wir konnten nur ein paar Freiwilligen darzustellen 9, 17, 20, 22, 29 und 34? So im Wesentlichen alle wer hier ist heute. Das war eine, zwei, drei, vier, fünf, sechs Personen. Und ich bin gebeten worden, go-- sehen, keine einem in den Rücken wirft ihren Händen. OK, ein, zwei, drei, vier, five-- lassen Sie mich laden balance-- sechs. OK, Sie auf sechs kommen. Wir andere Menschen brauchen. Wir brachten zusätzliche Stress-Bälle. Und wenn Sie könnten, für Nur einen Moment, Linie euch bis nur wie dieses Bild hier. 

In Ordnung. Mal sehen, was ist Ihr Name? 

ZIELGRUPPE: Andrew. 

David J. MALAN: Andrew, Sie sind die Nummer 9. Freut mich, dich kennenzulernen. Bitte schön. ZIELGRUPPE: Jen. David J. MALAN: Jen. David. Number 17. Ja? 

ZIELGRUPPE: Ich bin Julia. 

David J. MALAN: Julia, David. Nummer 20. ZIELGRUPPE: Christian. David J. MALAN: Christian, David. Number 22. Und? 

ZIELGRUPPE: JP. David J. MALAN: JP. Nummer 29. So gehen Sie vor und erhalten in-- Uh oh. Uh oh. Standby-Modus. 20. Hat jemand eine Markierung? ZIELGRUPPE: Ich habe einen Sharpie bekam. David J. MALAN: Sie Sharpie bekam ein? Ok. Und hat jemand ein Stück Papier? Speichern Sie die Vorlesung. Komm schon. ZIELGRUPPE: Wir haben es. David J. MALAN: Wir haben es? Alles klar, danke. Auf geht's. War diese von Ihnen? Sie haben den Tag gerettet. So 29. In Ordnung. Ich falsch geschrieben 29, aber OK. Nur zu. Gut, ich gebe Ihnen Stift wieder kurz auf. Also müssen wir diese Leute hier. Werfen wir einen anderen. Gabe, Sie spielen möchten das erste Element hier? Wir müssen Sie darauf an diesen feinen Leute. So 9, 17, 20, 22, Art von 29 und dann 34. Haben wir jemanden verlieren? Ich habe eine 34. Wo did-- OK, wer will 34 sein? OK, komm hoch, 34. Alles klar, das wird lohnt sich der Höhepunkt. Wie heißen Sie? 

ZIELGRUPPE: Peter. 

David J. MALAN: Peter, komm auf. Alles klar, hier ist so ein ganze Reihe von Knoten. Jeder von euch stellt eines dieser Rechtecke. Und Gabe, die etwas seltsam Mann aus, stellt den ersten. So dass seine Zeiger ist ein wenig kleiner auf dem Bildschirm als alle anderen. Und in diesem Fall, die jeweils von der linken Seite Hände wird sich entweder nach unten zeigen, dabei, die null, so nur die Abwesenheit von einem Zeiger, oder es wird gerichtet sein an einem Knoten in deiner Nähe. 

So jetzt, wenn Sie schmücken sich wie auf dem Bild Hier gehen Sie vor und Punkt bei jedem anderen, mit Gabe insbesondere zeigt auf Zahl 9, um die Liste zu repräsentieren. OK, und die Zahl 34, die linke Hand sollte nur auf den Boden gerichtet sein. 

OK, das ist so die verlinkte Liste. Also das ist das Szenario, in Frage. Und in der Tat, das ist repräsentativ einer Klasse von Problemen Sie könnten versuchen, mit dem Code zu lösen. Sie wollen schließlich einfügen ein neues Element in der Liste. In diesem Fall sind wir zu gehen Versuchen Sie, den Nummer 55. Aber es geht um sein verschiedene Fälle zu betrachten. Und in der Tat, das wird, einer zu sein der big-picture Imbissbuden hier ist, was sind die verschiedenen Fälle. Was sind die verschiedenen, wenn die Bedingungen oder Zweige, die Ihr Programm haben könnte? 

Nun, die Nummer, die Sie versuchen, Einsatz, der wir jetzt wissen, bis 55 zu sein, aber wenn Sie nicht wissen, im Voraus, ich wage zu behaupten, fällt in mindestens drei möglichen Situationen. Wo könnte ein neues Element zu sein? ZIELGRUPPE: Und das Ende oder in der Mitte. DAVID J. MALAN: Am Ende, in der Mitte oder am Anfang. Also ich behaupte, es gibt mindestens drei Probleme, die wir lösen müssen. Wählen wir, was vielleicht wohl einfachsten ein, wo das neue Element gehört zu Beginn. Also ich werde ziemlich Code haben wie zu suchen, was ich gerade geschrieben habe. Und ich werde ptr haben, die Ich werde hier mit meinem Finger repräsentieren, wie gewöhnlich. 

Und denken Sie daran, welchen Wert haben wir initialisieren ptr zu? So initialisiert wir es zunächst null. Aber was haben wir dann, wenn wir tun waren innerhalb unserer Suchfunktion? Wir setzen es gleich erste, was nicht heißt, dies zu tun. Wenn ich ptr gleich zuerst, was sollte meine Hand wirklich sein, zeigt auf? Rechts. Also, wenn Gabe und ich werden auf gleiche Werte hier zu sein, Wir müssen sowohl Punkt an der Nummer 9. 

Das war also der Anfang unserer Geschichte. Und jetzt ist dies nur einfach, obwohl die Syntax ist neu. Konzeptionell ist dies nur lineare Suche. 55 gleich 9? Oder eher, sagen wir, weniger als 9. Weil ich versuche, herauszufinden, wo bis 55 setzen. Weniger als 9 und weniger als 17, weniger als 20, weniger als 22, weniger als 29, weniger als 34, nicht. So, jetzt haben wir den Fall, sind einer von mindestens drei. 

Wenn ich hier einfügen 55, was Codezeilen müssen noch ausgeführt werden? Wie funktioniert dieses Bild von Menschen ändern müssen? Was mache ich mit meiner linken Hand zu tun? Dies sollte zunächst null sein, denn ich bin am Ende der Liste. Und was passieren soll, hier mit Peter, war es? Er ist offensichtlich werde, mich zu zeigen. Also ich behaupte, es gibt mindestens zwei Linien der Code in der Beispielcode von heute das wird sich dies umzusetzen Szenario der Zugabe von 55 am Schwanz. Und könnte ich jemanden Hop und nur 55 darstellen? Alle Rechte, sind Sie der neue 55. 

So, jetzt was, wenn die nächste Szenario kommt, und wir wollen in die eingefügt werden soll Anfang oder am Kopf dieser Liste? Und was ist Ihr Name, Nummer 55? 

ZIELGRUPPE: Jack. 

David J. MALAN: Jack? OK, schön, Sie zu treffen. Willkommen an Bord. So, jetzt sind wir zu gehen legen, sagen wir, die Zahl 5. Hier ist der zweite Fall der drei kamen wir vor. So dass, wenn 5 gehört zu Beginn, mal sehen, wie wir finden, dass aus. Ich meine initialisieren ptr Zeiger auf Platz 9 wieder. Und ich erkannte, oh, 5 weniger als 9. Also dieses Bild für uns zu fixieren. Deren Hände, Gabe oder Davids oder-- was Nummer 9 Name? 

ZIELGRUPPE: Jen. 

David J. MALAN: Jens hands-- welche unsere Hände zu ändern? OK, so Gabe zeigt auf, was nun? Mich an. Ich bin der neue Knoten. Also werde ich nur irgendwie bewegen hier um es visuell sehen. Und in der Zwischenzeit, was ich darauf hinweisen, dass? Noch, wo ich hin. So ist das also. Also wirklich nur eine Zeile Code Fixes Diese besondere Ausgabe, wie es scheint. Alles in Ordnung, und das ist gut. Und kann jemand ein Platzhalter für 5 sein? Komm auf. Wir machen Sie zum nächsten Mal. 

Alles in Ordnung, so now-- und Nebenbei bemerkt, die Namen Ich mache keine explizite Erwähnung von rechts jetzt, pred Zeiger, Zeiger Vorgänger und neue Zeiger, das ist nur die Namen gegeben in der Beispielcode, um den Zeiger oder meine Hände, die Art des Zeigens ist um. Wie heißen Sie? 

ZIELGRUPPE: Christine. 

David J. MALAN: Christine. Willkommen an Bord. Alles klar, also lassen Sie uns nun betrachten eine etwas lästige Szenario wobei ich will einfügen so etwas wie 26 in diese. 20? Was? Diese sind-- gute Sache haben wir diesen Stift. Alle Rechte, 20. Wenn jemand ein Stück bekommen Papier bereit, nur in case-- alles in Ordnung. Oh, interessant. Gut, das ist ein Beispiel einer Vorlesung Fehler. OK, so was ist Ihr Name? ZIELGRUPPE: Julia. David J. MALAN: Julia, können Sie Pop aus und täuschen Sie noch nie dort waren? Ok, das noch nie passiert. Danke. Also nehmen wir wollen einfügen Julia in dieser verketteten Liste. Sie ist die Nummer 20. Und natürlich ist sie in Zukunft an die gehören begin-- nicht auf alles, was darauf ist leer. So können Sie Ihre Hand Art sein unten null oder einige Müll Wert. Lassen Sie uns sagen, die schnelle Geschichte. Ich deutete auf Nummer 5 dieses Mal. Dann überprüfe ich 9. Dann überprüfe ich 17. Dann überprüfe ich 22. Und ich merke, ooh, Julia muss vor 22 gehen. Also, was muss noch passieren? Deren Hände brauchen, um zu ändern? Julia, Bergwerk, oder-- was ist Ihr Name? 

ZIELGRUPPE: Christian. 

David J. MALAN: Christian oder? 

ZIELGRUPPE: Andy. 

David J. MALAN: Andy. Christian oder Andy? Andy muss auf Punkt? Julia. In Ordnung. Also Andy, willst du bei Julia zeigen? Aber warten Sie eine Minute. In der Geschichte so weit, Ich bin die Art von einem zuständig, in dem Sinne, dass Zeiger ist die Sache, die ist Bewegung durch die Liste. Wir könnten einen Namen für Andy, aber es gibt keine Variable namens Andy. Die einzige andere Variable, die wir haben, ist erste, der von Gabe vertreten ist. 

Also das ist eigentlich, warum so Bis jetzt haben wir das nicht nötig haben. Aber jetzt auf dem Bildschirm gibt es erwähnen wieder von pred Zeiger. Also lassen Sie mich noch deutlicher sein. Wenn dies Zeiger, hatte ich besser ein wenig intelligenter über meine Iteration. Wenn Sie nichts dagegen haben, werde hier meine durch wieder und zeigte hier und zeigte hier. Aber lassen Sie mich eine pred Zeiger, Vorgänger-Zeiger, das ist Art zeigt auf die Element Ich war gerade auf. Also, wenn ich hier gehen, jetzt Meine linke Hand Updates. Wenn ich hier meine linke Hand Updates. Und jetzt habe ich nicht nur einen Zeiger auf das Element, das nach Julia geht, Ich habe immer noch einen Zeiger auf Andy, das Element vor. So haben Sie Zugriff Wesentlichen Semmelbrösel, wenn man will, , um alle erforderlichen Zeigern. 

Also, wenn ich an Zeige Andy und ich bin auch zeigen an der Christian, dessen Hände sollte nun an anderer Stelle hingewiesen werden? So Andy kann nun darauf an Julia. Julia kann jetzt bei Christian verweisen. Weil sie kopieren kann meine Die rechte Hand Zeiger. Und das bringt Sie effektiv zurück an diesen Ort hier. So kurz, auch wenn dies nimmt uns Art für immer tatsächlich aktualisieren verknüpfte Liste, erkennen dass die Operationen sind relativ einfach. Es ist von einem, zwei, drei Zeilen Code letztlich. Sondern um diejenigen, eingewickelt Codezeilen vermutlich ist ein bisschen Logik, die effektiv stellt die Frage, wo sind wir? Sind wir am Anfang, die Mitte oder das Ende? 

Nun, es gibt sicher einige andere Operationen, die wir vielleicht zu implementieren. Und diese Bilder hier zeigen nur was wir gerade mit den Menschen getan hat. Was ist die Entfernung? Wenn ich, zum Beispiel, entfernen Sie die Nummer 34 oder 55, Ich könnte die gleiche Art von Code haben, aber ich werde ein oder zwei Schritte brauchen. Denn was gibt es Neues? Wenn ich jemanden am Ende zu entfernen, wie die Nummer 55 und dann 34, Was muss sich ändern, auch, wie ich das tun? Ich muss nicht evict-- was ist Ihr Name? 

ZIELGRUPPE: Jack. 

David J. MALAN: Jack. Ich muss nicht nur evict-- kostenlos Jack, so wörtlich rufen Sie kostenlos Jack, oder zumindest der Zeiger dort auch, aber jetzt was muss mit Peter zu ändern? Seine Hand besseren Start nach unten zeigt. Denn sobald ich rufen Sie kostenlos an Jack, wenn Peter noch auf Jack zeigt und ich deshalb halten Laufen die Liste und den Zugang dieser Zeiger, das ist, wenn unser alter Freund Segmentierung Schuld könnte tatsächlich in Tritt. Weil wir gegeben haben, die Speicher zurück zu Jack. 

Sie können dort zu bleiben ungeschickt für einen Moment. Denn wir haben nur ein paar Abschluss Operationen zu berücksichtigen. Entfernen der Spitze der Liste, oder die beginning-- und das hier ist ein wenig ärgerlich. Weil wir wissen, dass Gabe ist eine Art Sonder in diesem Programm. Weil in der Tat, hat er seine eigene Zeiger. Er ist nicht gerade scharf ein, wie fast alle anderen hier. 

Also, wenn der Kopf der Liste ist entfernt, deren Hände jetzt ändern? Was ist Ihr Name? 

ZIELGRUPPE: Christine. 

David J. MALAN: Ich bin schrecklich bei Namen, anscheinend. So Christine und Gabe, deren Hände ändern müssen wenn wir versuchen, Christine zu entfernen, Nummer 5 aus dem Bild? OK, also lass es uns tun Gabe. Gabe geht, darauf hinzuweisen, vermutlich an der Nummer 9. Aber was soll passieren nächsten? ZIELGRUPPE: Christine sollte null [unverständlich]. David J. MALAN: OK, wir sollten wohl make-- Ich habe gehört, "null" irgendwo. ZIELGRUPPE: Null und kostenlos ihr. David J. MALAN: null, was? ZIELGRUPPE: Null und kostenlos ihr. David J. MALAN: Null und kostenlos ihr. Also das ist sehr einfach. Und es ist perfekt, dass Sie jetzt Art sind Stehen da, nicht dazu zu gehören. Weil Sie waren aus der Liste entkoppelt. Sie haben effektiv gewesen aus der Liste zu Waisen. Und so hatten wir uns besser jetzt kostenlos anrufen auf Christine zu, dass der Speicher zurück zu geben. Sonst immer, wenn wir löschen Sie einen Knoten aus der Liste wir könnten so die Liste kürzer, aber nicht tatsächlich abnimmt die Größe im Speicher. Und so, wenn wir halten das Hinzufügen und Hinzufügen, indem die Dinge in die Liste, Computer könnten langsamer werden und langsamer, weil ich aus renne Speicher, auch wenn ich nicht wirklich mit Christine Bytes Speicher mehr. 

Also am Ende gibt es noch andere Szenarien, von course-- Entfernung in der Mitte, Entfernung am Ende, wie wir sahen. Aber die interessantere Herausforderung ist nun sein wird, genau zu prüfen, Was ist die Laufzeit. So können Sie nicht nur halten Sie Ihre Stücke von Papier, wenn, Gabe, Sie hätte nichts dagegen, was jeder ein Stress-Ball. Vielen, vielen Dank an unsere verbundenen Liste von Freiwilligen hier, wenn Sie. 

[Applaus] 

David J. MALAN: In Ordnung. So ein paar analytische Fragen dann, wenn ich könnte. Wir haben diese Notation gesehen, Big O und das O, obere Schranken und untere Schranken für die Laufzeit von einigen Algorithmus. Also lasst uns einfach überlegen ein paar Fragen. 

, Und wir gesagt vor, was ist die Lauf Zeit der Suche nach einem Liste in Bezug auf Big O? Was ist auf der Lauf eine obere Schranke Zeit zum Suchen einer verketteten Liste wie von unseren Freiwilligen hier umgesetzt? Es ist groß O von n linear. Da im schlimmsten Fall, das Element, wie 55, könnten wir für uns werden könnte sein, wo Jack war, den ganzen Weg am Ende. Und leider, im Gegensatz zu einem Array können wir nicht Lust diese Zeit. Obwohl alle unsere Menschen waren aus kleinen Elementen, 5, sortiert, den ganzen Weg bis zu der größeren Element, 55, das ist in der Regel eine gute Sache. Aber was bedeutet diese Annahme nicht mehr erlauben uns zu tun? ZIELGRUPPE: [unverständlich] David J. MALAN: Sagen Sie noch mal? ZIELGRUPPE: Random-Zugang. David J. MALAN: Random-Zugang. Und im Gegenzug das heißt, wir können nicht mehr verwenden schwachen Nullen, Intuition, und die Offenkundigkeit mit binären suchen und zu teilen und zu erobern. Denn auch wenn wir Menschen konnte offensichtlich sehen, dass Andy oder Christian waren etwa in der Mitte der Liste, wir wissen nur, dass ein Computer durch Abschöpfen der Liste von Anfang an. Deshalb haben wir bis diese wahlfreien Zugriff gegeben. 

So groß O von n jetzt ist die obere auf unserer Suche Zeit gebunden. Was ist mit Omega unserer Suche? Was ist die untere Grenze auf der Suche für eine Zahl in dieser Liste? ZIELGRUPPE: [unverständlich] David J. MALAN: Sagen Sie noch mal? ZIELGRUPPE: One. David J. MALAN: One. So konstante Zeit. Im besten Fall ist Christine tatsächlich am Anfang der Liste. Und wir suchen Zahl 5, so fanden wir sie. Also keine große Sache. Aber sie hat an der sein Anfang der Liste in diesem Fall. Was ist so etwas wie löschen? Was ist, wenn Sie wollen, um ein Element zu löschen? Was ist die Obergrenze und Untergrenze zum Löschen von etwas aus einem verknüpften Liste? ZIELGRUPPE: [unverständlich] David J. MALAN: Sagen Sie noch mal? ZIELGRUPPE: n. David J. MALAN: n tatsächlich die obere Grenze. Weil im schlimmsten Fall werden wir versuchen, Jack löschen, wie wir gerade getan. Er ist den ganzen Weg am Ende. Führt uns immer, oder n Schritte, um ihn zu finden. Also das ist eine obere Schranke. Das ist linear, sicher. Und das Beste bei Laufzeit oder die unteren Grenzen im besten Fall würde konstante Zeit. Weil vielleicht versuchen wir, zu löschen Christine, und wir einfach Glück sie ist am Anfang. Jetzt warten Sie eine Minute. Gabe war auch zu Beginn, und wir hatten auch zu aktualisieren Gabe. Das war also nicht nur ein Schritt. So ist es in der Tat konstant Zeit, im besten Fall, um das kleinste Element zu entfernen? Es ist, auch wenn es vielleicht zwei, drei oder sogar 100 Codezeilen, Wenn es die gleiche Anzahl von Linien, nicht in einem Loop, und unabhängig von der Größe der Liste, absolut. Löschen Sie das Element bei der Anfang der Liste, auch wenn wir es zu tun haben Gabe, ist immer noch konstante Zeit. 

So erscheint dies wie ein massiven Rückschritt. Und was für eine Verschwendung von Zeit wenn in einer Woche und Woche Null hatten wir nicht nur Pseudocode, aber eigentliche Code etwas, das Protokoll umzusetzen Basis n, oder melden Sie sich vielmehr von n, Basis 2, hinsichtlich seiner Laufzeit. Also warum zum Teufel wir starten wollen mit so etwas wie einer verketteten Liste? Ja. 

ZIELGRUPPE: So können Sie hinzufügen Elemente des Arrays. David J. MALAN: So kann man Hinzufügen von Elementen zum Array. Und auch das ist thematisch. Und wir werden auch weiterhin zu sehen dieses, dieses Trade-off, viel wie wir gesehen haben, eine Trade-off mit Merge-Sort. Wir könnten wirklich beschleunigen Suche oder Sortierung vielmehr wenn wir ein bisschen mehr Platz zu verbringen und ein zusätzliches Stück von Speicher oder ein Array für Merge-Sort. Aber wir verbringen mehr Raum, aber wir sparen Zeit. In diesem Fall sind wir Aufgeben Zeit, aber wir sind gewinnt Flexibilität, Dynamik, wenn man so will, das ist wohl ein positives Merkmal. 

Wir sind auch die Ausgaben Raum. In welchem ​​Sinn ist eine verknüpfte Liste teurer in Bezug auf Raum, als ein Array? Wo ist der zusätzliche Platz kommt? Ja? 

ZIELGRUPPE: [unverständlich] Zeiger. 

David J. MALAN: Ja, wir auch die Zeiger. Also das ist ärgerlich minorly daß nicht mehr am Ich Speicherung nur einen int um einen int darstellen. Ich Speichern eines int und eine Zeiger, der ebenfalls 32 Bits. Also ich bin buchstäblich verdoppelt Die Höhe des Raumes beteiligt. Also das ist ein Kompromiss, aber das ist im Fall der Int. Nehmen wir an, dass Sie nicht zu speichern int, aber angenommen, jeder dieser Rechtecke oder jeder dieser Menschen wurde darstellt ein Wort, eine englische Wort, das vielleicht fünf Zeichen, 10 sein Zeichen, vielleicht sogar mehr. Dann Zugabe von nur 32 mehr Bits vielleicht weniger eine große Sache sein. 

Was ist, wenn jeder der Studenten im Demonstrations buchstäblich waren Schüler, dass Strukturen haben Namen und Häuser und vielleicht Telefonnummern und Twitter Griffe und dergleichen. So dass alle Felder, die wir begonnen reden über den anderen Tag, viel weniger eine große Sache wie unsere Knoten bekommen interessanter und groß zu verbringen, eh, eine zusätzliche Zeiger, nur um sie miteinander zu verknüpfen. Aber in der Tat, es ist ein Trade-off. Und in der Tat ist die Code komplexer, wie Sie siehe durch Abschöpfen durch dass besonderes Beispiel. Aber was, wenn es einige heilige Gral hier. Was, wenn wir nicht einen Schritt machen hinten, sondern ein massiver Schritt nach vorn und Umsetzung eines Daten Struktur, über die wir können Elemente wie Jack oder finden Christine oder andere Elemente in diesem Array in konstanter Zeit wahr? Suche ist konstant. Löschen ist konstant. Einsatz ist konstant. Alle diese Operationen sind konstant. Das würde unsere heilige Gral sein. Und das ist, wo wir holt das nächste Mal. Sie sehen dann.