[Powered by Google Translate] [Woche 6, Fortsetzung]
[David J. Malan] [Harvard University]
[Dies ist CS50.] [CS50.TV]
Dies ist CS50 und das ist das Ende der Woche 6.
So CS50x, einer der ersten Kurse in Harvard in den EDX-Initiative beteiligt
Tat debütierte am vergangenen Montag.
Wenn Sie möchten, um einen Blick auf, was andere über das Internet erhalten
folgen nun zusammen mit, können Sie x.cs50.net Kopf.
Das wird Sie an die entsprechende Stelle auf edx.org umzuleiten,
das war, wo diese und andere Kurse vom MIT und Berkeley jetzt leben.
Sie müssen sich für ein Konto, Sie werden feststellen, dass das Material weitgehend die gleichen
Sie habe in diesem Semester, wenn auch ein paar Wochen verzögert, da wir alles fertig zu bekommen.
Aber was die Schüler in CS50x werden jetzt sehen, ist eine Schnittstelle ganz wie diese ein.
Dies ist zum Beispiel Zamyla führt die Komplettlösung für den problemlosen Satz 0.
Nach der Anmeldung in edx.org sieht ein CS50x Schüler die Art von Dingen
Sie erwarten würden, in einem Kurs zu sehen: die Vorlesung für Montag,
Vortrag für Mittwoch, diverse Kurzfilme, die Problemstellungen, die Komplettlösungen, PDFs.
Darüber hinaus, wie Sie hier sehen, maschinelle Übersetzungen
Englisch Transkripte in Chinesisch, Japanisch, Spanisch, Italienisch,
und eine ganze Reihe von anderen Sprachen, die sicherlich wird unvollkommenen
wie wir ausrollen programmatisch mit etwas namens ein API,
oder Application Programming Interface, von Google
das ermöglicht es uns, zu konvertieren Deutsch zu diesen anderen Sprachen.
Aber dank der wunderbaren Geist von einigen hundert-plus Freiwilligen,
zufälligen Menschen über das Internet, die uns freundlicherweise angeboten haben, sich zu engagieren
In diesem Projekt werden wir schrittweise Verbesserung der Qualität dieser Übersetzungen
indem er den Menschen die Fehler korrigieren, dass unsere Computer gemacht haben.
>> So stellt sich heraus, dass wir ein paar mehr Studenten auftauchen hatte am Montag, als wir ursprünglich erwartet.
In der Tat, jetzt CS50x hat 100.000 Menschen nach zusammen zu Hause.
So realisieren Sie alle sind Teil dieser konstituierenden Klasse machen diesen Kurs in der Informatik
Bildung allgemein, weiter gefasst, zugänglich.
Und die Realität ist nun mit einigen dieser massiven Online-Kurse,
sie alle mit diesen sehr hohen Zahlen beginnen, wie wir hier zu tun zu haben scheinen.
Aber das Ziel letztlich für CS50x ist wirklich so viele Menschen über die Ziellinie wie möglich zu erhalten.
Vom Design her ist CS50x werde aus dieser vergangenen Montag angeboten werden
den ganzen Weg bis zum 15. April 2013, so dass Leute, die haben Schule Verpflichtungen anderswo,
Arbeit, Familie, andere Konflikte und dergleichen, haben ein bisschen mehr Flexibilität
mit denen in diesem Kurs tauchen, das, es genügt zu sagen,
ist ziemlich ambitioniert tun, wenn erst im Laufe von nur drei Monaten während eines üblichen Semester.
Aber diese Schüler werden die Bewältigung der gleiche Problem Sets, sich den gleichen Inhalt,
mit Zugriff auf dieselben Shorts und dergleichen.
So erkennen, dass wir alle wirklich sind in diesem zusammen.
Und einer der Endziele der CS50x ist nicht nur so viele Leute sich
bis zur Ziellinie und ihnen diese neu gewonnene Verständnis der Informatik
und Programmierung, sondern auch, haben sie über diese gemeinsame Erfahrung.
Eines der bestimmenden Merkmale der 50 auf dem Campus, so hoffen wir,
hat diese Art von Gemeinschaftserlebnis, zum Besseren oder zum Schlechteren, manchmal,
aber mit diesen Menschen um nach links und nach rechts zu drehen,
und Sprechzeiten und die Hackathon und fair.
Es ist ein wenig schwerer zu, dass in der Person mit Leuten online tun,
aber CS50x wird im April mit dem ersten CS50 Expo abzuschließen,
was wird ein Online-Adaption unserer Idee der Messe sein
wo diese Tausende von Studenten alle eingeladen, eine 1 einzureichen - bis 2-Minuten-Video,
entweder ein Screencast über ihre endgültige Projekt oder Video von ihnen winken hallo
und reden über ihr Projekt und Demonstrieren es,
ähnlich wie Ihre Vorgänger haben hier auf dem Campus in der Messe getan,
so dass durch Semester Ende ist die Hoffnung auf eine globale Ausstellung haben
der CS50x Studenten Abschlussarbeiten, ähnlich wie das, was erwartet Sie im Dezember dieses Jahres hier auf dem Campus.
Also mehr auf, dass in den kommenden Monaten.
>> Mit 100.000 Studenten, obwohl, kommt eine Notwendigkeit für ein paar CAs.
Vorausgesetzt, dass Sie Jungs sind sich der Weg hier und unter CS50
mehrere Wochen im Voraus aus diesem Material die Freilassung der Leute auf EDX,
erkennen wir würden uns freuen, möglichst viele unserer eigenen Studenten wie möglich an dieser Initiative beteiligt,
sowohl während des Semesters als auch in diesem Winter und im kommenden Frühjahr.
Also, wenn Sie möchten, sich in CS50x,
Besonders Beitritt in auf CS50x diskutieren, die EDX Version CS50 diskutieren,
was viele von Ihnen haben auf dem Campus wurden mit der Online-Bulletin Board,
bitte den Kopf auf diese URL, lassen Sie uns wissen, wer Sie sind,
weil wir würden gerne bauen ein Team von Studenten und Mitarbeitern und Dozenten gleichermaßen
auf dem Campus, die sind einfach Mitspielen und aushelfen.
Und wenn sie sehen, eine Frage, die ihnen vertraut ist,
Sie hören einen Studenten berichten einige Fehler irgendwo da draußen in einem Land auf dem Internet,
und dass klingelt, weil Sie hatte auch das gleiche Problem
in Ihrer d-Halle vor einiger Zeit, hoffentlich dann können Sie in Glockenspiel und teilen Sie Ihre eigenen Erfahrungen.
Also bitte teilzunehmen, wenn Sie möchten.
>> Informatik Kurse an der Harvard haben ein bisschen von einer Tradition,
CS50 unter ihnen, der mit etwas Kleidung, ein paar Kleider, die Sie mit Stolz tragen kann
am Semester Ende sagen ganz stolz, dass Sie CS50 fertig
und nahm CS50 und dergleichen, und wir versuchen immer die Studenten einbeziehen
bei diesem Verfahren so weit wie möglich, wodurch wir laden,
um diese Zeit des Semesters den Studenten einreichen Designs
mit Photoshop, oder was auch immer Werkzeug der Wahl Sie möchten, verwenden
wenn Sie ein Designer, Entwürfe für T-Shirts und Sweatshirts einreichen
und Sonnenschirme und kleine Bandanas für Hunde, die wir jetzt haben, und dergleichen.
Und alles ist dann - die Gewinner jedes Jahr werden dann ausgestellt
auf den Verlauf der Internetseite store.cs50.net.
Alles wird zum Selbstkostenpreis dort verkauft, aber die Website läuft einfach selbst.
und ermöglicht es den Menschen, um die Farben und Designs, die sie gerne wählen.
Also dachte ich, wir würden nur Aktien einige der letztjährigen Designs
Das waren auf der Website neben diesem einen hier, was ist eine jährliche Tradition.
"Every Day I Seg Faultn bin" war einer der Einreichungen im vergangenen Jahr,
die immer noch dort für Alumni.
Wir hatten diese ein, "CS50, Established 1989."
Einer unserer Bowdens, Rob, war sehr beliebt im letzten Jahr.
"Team Bowden" geboren wurde, wurde dieser Entwurf vorgelegt, unter den Top-Anbietern.
Wie diese hier. Viele Menschen hatten "Bowden Fever" nach den Umsatz-Protokolle.
Erkenne, dass das könnte jetzt Ihr Design dabei sein, auf dem Internet.
Weitere Details hierzu finden Sie im nächsten Problem setzt zu kommen.
>> Ein weiteres Werkzeug: Sie habe einige Belichtung und jetzt hoffentlich
einige Hands-on Erfahrung mit GDB,
das ist natürlich ein Debugger und ermöglicht es Ihnen zu manipulieren
Ihr Programm auf einem relativ niedrigen Niveau, zu tun, was Arten von Dingen?
Was bedeutet GDB können Sie tun?
Yeah? Gib mir etwas. [Schüler Antwort unverständlich]
Gut. Treten Sie ein in Funktion, so dass Sie nicht einfach zu laufen geben
und haben das Programm durchblasen seiner Gesamtheit, Druck, Dinge auf die Standardausgabe.
Vielmehr kann man durch sie Zeile für Zeile fort, entweder eingeben nächsten
Zeile für Zeile für Zeile oder Schritt in eine Funktion zu tauchen, in der Regel ein, dass du geschrieben hast zu gehen.
Was bedeutet GDB können Sie tun? Yeah? [Schüler Antwort unverständlich]
Drucken Variablen. Also, wenn Sie wollen ein wenig Introspektion innerhalb des Programms zu tun
ohne zu schreiben printf Aussagen ganz über dem Platz greifen,
Sie können nur drucken variable oder zeigen eine Variable.
Was kann man mit einem Debugger wie GDB tun?
[Schüler Antwort unverständlich]
Genau. Sie können Haltepunkte setzen, können Sie Pause Ausführung sagen,
an der Hauptfunktion oder foo Funktion.
Sie können Pause Ausführung in Zeile 123 sagen.
Und Haltepunkte sind eine wirklich leistungsfähige Technik
denn wenn Sie ein allgemeines Gefühl von wo Ihr Problem
Wahrscheinlich ist, müssen Sie nicht Zeit damit verschwenden Durchlaufen des Programms insgesamt.
Sie lassen sich im Wesentlichen genau dort springen und dann beginnt zu schreiben -
Schreiten durch sie mit der nächsten Stufe oder od.dgl.
Aber der Haken mit so etwas wie GDB ist, dass es Ihnen hilft, die menschliche,
finden Sie Ihre Probleme und finden Sie Ihre Fehler.
Es muss nicht unbedingt finden sie so viel für dich.
>> So haben wir die anderen Tage style50, was eine kurze Kommandozeilen-Tool
das versucht, Ihren Code ein wenig sauberer als Sie stilisieren, der Mensch könnte getan haben.
Aber auch das ist wirklich nur eine ästhetische Sache.
Aber es stellt sich heraus, es ist das andere Tool namens Valgrind, die ein wenig mehr geheimnisvoll zu bedienen ist.
Sein Ausgang ist grausam kryptisch auf den ersten Blick.
Aber es ist wunderbar nützlich, vor allem jetzt, da wir in dem Teil des Begriffs sind
wo Sie fangen an, malloc und dynamische Speicherzuweisung verwenden.
Dinge gehen wirklich, wirklich falsch schnell.
Denn wenn Sie vergessen, Ihr Gedächtnis zu befreien, oder Sie dereferenzieren einige NULL-Zeiger,
oder Sie einige Müll Zeigerdereferenzierung, was ist in der Regel das Symptom, dass die Ergebnisse?
Seg Schuld. Und Sie erhalten diese Core-Datei einer gewissen Anzahl von Kilobyte oder Megabyte
das stellt den Zustand Ihres Programms im Speicher, wenn es abgestürzt ist,
aber Ihr Programm letztendlich seg Fehler, Segmentation Fault,
was bedeutet, etwas Schlimmes passiert fast immer im Zusammenhang
zu einem Speicher-bezogene Fehler, dass Sie irgendwo gemacht.
So Valgrind hilft Ihnen, Dinge wie diese.
Es ist ein Werkzeug, das Sie laufen, wie GDB, nachdem Sie das Programm zusammengestellt haben,
aber anstatt Führen Sie das Programm direkt, laufen Sie Valgrind
und Sie übergeben es Ihrem Programm, so wie du mit GDB tun.
Nun, die Nutzung, um die beste Art der Ausgabe,
ist ein wenig lang, so richtig es atop des Bildschirms sehen Sie Valgrind-v.
"-V" fast universell bedeutet, verbose, wenn Sie Programme sind auf einem Linux-Computer.
So bedeutet es ausspucken mehr Daten, als Sie vielleicht standardmäßig.
"- Leck-check = voll." Dies ist nur zu sagen Check für alle möglichen Speicherlecks,
Fehler, die ich gemacht haben könnte. Auch dies ist ein gemeinsames Paradigma mit Linux-Programmen.
Im Allgemeinen, wenn Sie eine Befehlszeile Argument haben, das ist ein "Schalter",
Das soll das Verhalten des Programms zu ändern, und es ist ein einzelner Buchstabe,
es-v, aber wenn es das ist eingeschaltet, nur durch Design des Programmierers,
ist ein ganzes Wort oder eine Reihe von Wörtern, beginnt das Befehlszeilenargument mit -.
Dies sind nur menschliche Konventionen, aber du wirst sie immer sehen.
Und dann, endlich, "a.out" ist die willkürliche Namen für das Programm in diesem speziellen Beispiel.
Und hier einige repräsentative Ausgabe.
>> Bevor wir uns, was das bedeuten könnte schauen, lass mich gehen über zu einer Code-Snippet hier.
Und lassen Sie mich verschieben Sie diese aus dem Weg, in Kürze,
und lassen Sie uns einen Blick auf memory.c, die in diesem kurzen Beispiel ist hier.
So in diesem Programm, lassen Sie mich heran zu den Funktionen und Fragen.
Wir haben eine Funktion main, die eine Funktion aufruft, f,
und was dann bedeutet f gehen zu tun, in etwas technisches Englisch?
Was bedeutet f gehen zu tun?
Wie wäre ich mit der Linie 20 zu starten, und der Stern Standort spielt keine Rolle,
aber ich werde einfach konsequent sein hier mit dem letzten Vortrag.
Was ist in Zeile 20 für uns? Auf der linken Seite. Wir brechen sie weiter.
Int * x: Was bedeutet das?
Okay. Es Deklaration eines Zeigers, und jetzt lasst uns noch technisch.
Was bedeutet es ganz konkret, um einen Zeiger zu deklarieren? Jemand anderes?
Yeah? [Schüler Antwort unverständlich] Too far.
Sie sind also auf der rechten Seite des Gleichheitszeichens lesen.
Konzentrieren wir uns nur auf der linken Seite, nur auf int * x.
Dies bedeutet "deklarieren", einen Zeiger, aber jetzt lass uns in tieferen dieser Definition tauchen.
Was heißt das konkret, technisch bedeuten? Yeah?
[Schüler Antwort unverständlich]
Okay. Es bereitet sich auf eine Adresse im Speicher zu speichern.
Gut. Und lassen Sie uns noch einen Schritt weiter, es ist eine Variable deklarieren, x, die 32 Bit ist.
Und ich weiß, es ist 32 Bit, weil -?
Es ist nicht, weil es ein int ist, weil es ein Zeiger in diesem Fall ist.
Zufall, dass es ein und dieselbe mit einem int ist,
aber die Tatsache, dass es der Stern dort bedeutet dies ist ein Zeiger
und in dem Gerät, wie bei vielen Computern, aber nicht alle, sind Zeiger 32 Bits.
Auf mehr moderne Hardware wie die neuesten Macs, die neuesten PCs, Sie haben 64-Bit-Zeiger,
aber in dem Gerät, diese Dinge sind 32 Bit.
So werden wir auf, dass zu standardisieren. Genauer gesagt, geht die Geschichte wie folgt:
Wir "erklären" einen Zeiger, was bedeutet das?
Wir bereiten eine Speicheradresse zu speichern.
Was bedeutet das?
Wir schaffen eine Variable namens x, das in Anspruch nimmt 32 Bit
das wird sich bald speichern Sie die Adresse einer Ganzzahl.
Und das ist wahrscheinlich ungefähr so ​​präzise wie wir bekommen können.
Es ist gut voran, um die Welt zu vereinfachen und nur sagen, erklären, einen Zeiger namens x.
Deklariert einen Zeiger, sondern erkennen und verstehen, was eigentlich vor sich geht
sogar in nur jenen wenigen Zeichen.
>> Nun, ist das ein fast ein wenig zu erleichtern, obwohl es eine längere Ausdruck ist.
Also, was ist dieses Tun, das ist nun hervorgehoben: "malloc (10 * sizeof (int));" Yeah?
[Schüler Antwort unverständlich]
Gut. Und ich werde es dort. Es Zuteilung ein Stück Speicher für zehn Zahlen.
Und nun in etwas tiefer tauchen, es ist Zuweisung ein Stück Speicher für zehn Zahlen.
Was ist malloc dann wieder?
Die Adresse dieser Brocken, oder, genauer gesagt, die Adresse des ersten Bytes des Chunk.
Wie dann bin ich, der Programmierer, um zu wissen, wo das Stück Speicher Enden?
Ich weiß, dass es zusammenhängende ist. Malloc, per Definition, wird Ihnen einen zusammenhängenden Block arbeiten.
Keine Lücken. Sie haben Zugriff auf jedes Byte in diesem Stück,
Rücken an Rücken an Rücken, aber wie kann ich wissen, wo das Ende dieses Stück Erinnerung ist?
Wenn Sie malloc? [Schüler Antwort unverständlich] Gut.
Sie tun es nicht. Sie haben sich daran zu erinnern.
Ich muss daran erinnern, dass ich den Wert 10 verwendet wird, und ich weiß nicht einmal zu, dass hier getan haben.
Aber die Verantwortung liegt ausschließlich bei mir. Strlen, was wir geworden sind leicht abhängig für Streicher,
funktioniert nur, weil dieser Konvention mit \ 0
oder diese spezielle nul Charakter, NUL am Ende eines Strings.
Das bedeutet nicht nur für beliebige Stücke der Erinnerung zu halten.
Es ist bis zu Ihnen. So Zeile 20, dann ordnet ein Stück der Erinnerung
das kann zehn Ganzzahlen speichern und speichert die Adresse des ersten Bytes
dieses Stück Speicher in der Variablen x.
Ergo, die ein Zeiger ist. So Linie 21 war leider ein Fehler.
Aber zuerst, was ist das denn? Es sagt store bei Position 10, 0 indiziert,
der Brocken Speicher abgerufen x den Wert 0.
>> So bemerkt ein paar Dinge sind passiert.
Auch wenn x ist ein Zeiger, von ein paar Wochen wieder zu
Sie können immer noch die Array-style eckigen Klammern.
Denn das ist eigentlich kurz-Hand-Notation für die mehr kryptischen aussehende Zeigerarithmetik.
wo wir etwas tun: Nehmen Sie die Adresse x, verschieben 10 Punkte über,
dann gehen Sie zu, was Adresse wird an dieser Stelle gespeichert.
Aber ehrlich gesagt, das ist nur grauenhaft zu lesen und sich bequem mit.
So die Welt verwendet in der Regel die eckigen Klammern, nur weil es so viel mehr Menschen freundlich zu lesen ist.
Aber das ist, was wirklich vor sich geht unter der Haube;
x ist eine Adresse, nicht ein Array an sich.
Das ist also die Speicherung 0 bei Position 10 in x.
Warum ist das schlecht? Yeah?
[Schüler Antwort unverständlich] Genau.
Wir haben nur zugeteilt zehn ints, aber wir von 0 zu zählen, wenn die Programmierung in C,
so haben Sie Zugang zu 0 1 2 3 4 5 6 7 8 9, aber nicht 10.
Also entweder das Programm auf seg Fehler gehen oder es ist nicht.
Aber wir wissen nicht wirklich, das ist eine Art von nichtdeterministischen Verhalten.
Es hängt wirklich davon ab, ob wir Glück haben.
Wenn es sich herausstellt, dass das Betriebssystem nicht dagegen, wenn ich diesen zusätzlichen Byte verwenden,
obwohl es nicht hat sie mir gegeben, könnte mein Programm nicht abstürzen.
Es ist roh, sie ist fehlerhaft, aber Sie könnten nicht sehen, dass Symptom,
oder Sie können es nur einmal in eine Weile zu sehen.
Aber die Realität ist, dass der Fehler ist in der Tat gibt.
Und es ist wirklich problematisch, wenn Sie ein Programm, das Sie richtig geschrieben haben,
dass Sie das Programm verkauft, dass die Menschen mit, dass jeder einmal in eine Weile stürzt
weil natürlich das ist nicht gut. In der Tat, wenn Sie ein Android-Handy oder ein iPhone
und laden Sie Apps in diesen Tagen, wenn Sie jemals eine App zu beenden,
plötzlich verschwindet, das ist fast immer das Ergebnis einer Speicher-bezogene Frage,
wobei der Programmierer und schraubte einen Zeiger dereferenziert
dass er oder sie sollte nicht haben, und das Ergebnis der iOS oder Android ist einfach töten das Programm insgesamt
anstatt das Risiko einzugehen undefinierten Verhalten oder irgendeine Art von Sicherheit zu gefährden.
>> Es gibt einen weiteren Fehler in diesem Programm neben diesem ein.
Was habe ich in diesem Programm geschraubt?
Ich habe nicht geübt, was ich gepredigt. Yeah?
[Schüler Antwort unverständlich] Gut.
Ich habe nicht den Speicher freigegeben. So die Faustregel jetzt
muss, wenn Sie malloc aufrufen, müssen Sie rufen Sie kostenlos, wenn Sie fertig sind mit diesem Speicher.
Jetzt würde, wenn ich will, diesen Speicher zu befreien?
Wahrscheinlich, vorausgesetzt, diese erste Zeile korrekt war, möchte ich es hier tun.
Da konnte ich zum Beispiel nicht, tun Sie es hier unten. Warum?
Just out of scope. Also auch wenn wir über Zeiger reden,
dies ist in der Woche 2 oder 3 Ausgabe, wobei x ist nur im Umfang Innenseite der geschweiften Klammern dort erklärt wurde.
So dass Sie definitiv nicht befreien können es dort. Meine einzige Chance, es zu befreien ist etwa nach Zeile 21.
Dies ist ein ziemlich einfaches Programm, es war ziemlich einfach, sobald Sie wickelte Art von Geist
um das, was das Programm tut, wo die Fehler waren.
Und selbst wenn Sie nicht sehen, es auf den ersten, hoffentlich ist es ein wenig offensichtlich jetzt
dass diese Fehler sind ziemlich leicht zu lösen und leicht gemacht.
Aber wenn ein Programm mehr als 12 Zeilen lang ist, ist es 50 Zeilen lang, 100 Zeilen lang,
Spaziergang durch den Code Zeile für Zeile, durchdenken es logisch,
ist möglich, aber nicht besonders viel Spaß, ständig auf der Suche nach Bugs,
und es ist auch schwer zu tun, und deshalb ein Tool wie Valgrind existiert.
Lassen Sie mich gehen Sie vor und tun dies: Lassen Sie mich öffne meine Terminal-Fenster,
und lass mich nicht nur laufen Speicher, weil der Speicher scheint in Ordnung zu sein.
Ich bin immer glücklich. Flugziel daß zusätzliches Byte am Ende des Arrays
scheint nicht allzu problematisch.
Aber lassen Sie mich dennoch tun, eine Plausibilitätsprüfung, die bedeutet nur, um zu überprüfen,
ob dies tatsächlich stimmt.
>> So lasst uns valgrind-v - Leck-Check = full,
und dann den Namen des Programms in diesem Fall ist der Speicher nicht a.out.
Also lass mich gehen Sie vor und tun dies. Drücken Sie die Eingabetaste.
Lieber Gott. Dies ist seine Leistung, und dies ist, was ich zuvor angespielt.
Aber, wenn Sie lernen, durch all der Unsinn hier gelesen,
die meisten ist dies nur eine diagnostische Ausgabe, ist nicht so interessant.
Was das Auge wirklich will gesucht werden ist jede Erwähnung von Fehlern oder ungültig.
Worte, die Probleme vorzuschlagen.
Und in der Tat, mal sehen, was falsch läuft hier unten.
Ich habe eine Zusammenfassung von einer Art "im Einsatz bei Ausfahrt. 40 Byte in 1 blocks"
Ich bin nicht wirklich sicher, was ein Block ist noch nicht, aber 40 Bytes
fühlt sich tatsächlich wie ich herausfinden konnte, wo das herkommt ist.
40 Byte. Warum sind 40 Byte im Einsatz an der Ausfahrt?
Und genauer gesagt, wenn wir nach unten scrollen hier
warum habe ich endgültig verloren 40 Byte? Yeah?
[Schüler Antwort unverständlich] Perfect. Ja, genau.
Es waren zehn ganze Zahlen, und jede von ihnen ist eine Größe von 4 oder 32 Bits,
so habe ich genau 40 Byte verloren, weil, wie Sie vorgeschlagen, ich nicht angerufen haben frei.
Das ist ein Fehler, und jetzt schauen wir uns ein wenig nach unten weiter und sehen daneben,
"Invalid der Größe 4 zu schreiben." Nun, was ist das?
Diese Adresse wird, was Ausgangspunkt Schreibweise ausgedrückt, offenbar?
Dies ist hexadezimal, und zu jeder Zeit sehen Sie eine Nummer, beginnend mit 0x,
es bedeutet hexadezimal, was wir Weg zurück in, glaube ich, pset 0-Sektion von Fragen haben,
das war nur ein Aufwärmprogramm Übung, die Umwandlung Dezimal in Hex zu binär und so weiter.
Hexadezimal, nur durch menschliche Konvention ist in der Regel verwendet, um Zeiger stellen
oder, allgemeiner, adressiert. Es ist nur eine Konvention,
weil es ein wenig leichter zu lesen ist, ist es ein wenig kompakter als so etwas wie dezimal,
und Binär ist nutzlos für die meisten Menschen zu verwenden.
So, jetzt, was bedeutet das? Nun, es sieht aus wie es ist ein ungültiger Schreibvorgang
der Größe 4 on line 21 von memory.c.
So gehen wir zurück in die Linie 21, und in der Tat, hier ist, dass ungültige schreiben.
So Valgrind wird nicht komplett meine Hand halten und sagen Sie mir, was die Lösung ist,
aber es ist Erkennen, dass ich tue, einen ungültigen Schreibvorgang.
Ich berühre 4 Byte, dass ich nicht sein sollte, und anscheinend das ist, weil,
Sie haben darauf hingewiesen, ich tue [10] anstelle von [9] maximal
oder [0] oder etwas dazwischen.
Mit Valgrind realisieren jederzeit du jetzt schreibst ein Programm
die Zeiger verwendet und Speicher verwendet, und malloc genauer gesagt,
definitiv in der Gewohnheit läuft so lange erhalten
aber sehr leicht kopiert und das Kommando über Valgrind eingefügt
zu sehen, ob es gibt einige Fehler drin.
Und es wird überwältigend sein jedes Mal, wenn Sie sehen die Ausgabe,
sondern nur durch ein visuell alle der Ausgabe analysieren und sehen, wenn Sie sehen, erwähnt von Fehlern
oder Warnungen oder ungültig werden oder verloren gehen.
Jedes Wort, die klingen wie Sie vermasselt irgendwo.
So erkennen, dass es ein neues Tool in Ihrem Toolkit.
>> Jetzt am Montag hatten wir eine ganze Reihe von Leute kommen hier
und stellen die Vorstellung einer verketteten Liste.
Und wir stellten die verknüpfte Liste als eine Lösung für welches Problem?
Yeah? [Schüler Antwort unverständlich] Gut.
Arrays können nicht haben Memory hinzugefügt werden.
Wenn Sie reservieren ein Array der Größe 10, das ist alles, was Sie bekommen.
Sie können eine Funktion wie realloc, wenn Sie angerufen zunächst malloc,
und dass können versuchen, das Array wachsen, wenn es Raum in Richtung des Ende davon
dass niemand sonst benutzt, und wenn es nicht ist, wird es nur finden Sie einen größeren Teil woanders.
Aber dann wird es all diese Bytes in das neue Array kopiert.
Das klingt wie eine sehr richtige Lösung.
Warum ist das unattraktiv?
Ich meine, es funktioniert, haben die Menschen dieses Problem gelöst.
Warum haben wir müssen es am Montag zu lösen mit verknüpften Listen? Yeah?
[Schüler Antwort unverständlich] Es könnte lange dauern.
In der Tat, jedes Mal, wenn malloc oder realloc oder calloc, die noch nicht ein anderes sind,
jedes Mal, wenn das Programm, an das Betriebssystem sprechen,
Sie neigen dazu, das Programm zu verlangsamen.
Und wenn du diese Art von Dingen in Schleifen, du bist wirklich zu verlangsamen.
Du wirst doch nicht um diese für die einfachsten "Hallo Welt"-Typ Programmen bemerken,
aber in viel größeren Programmen fragen Sie das Betriebssystem wieder und wieder für das Gedächtnis
oder geben sie wieder und wieder neigt nicht eine gute Sache sein.
Plus, es ist nur eine Art intellektuell - es ist eine komplette Zeitverschwendung.
Warum dafür mehr und mehr Speicher, Risiko kopiert alles, was in das neue Array,
Wenn Sie eine Alternative, die Sie zuordnen nur so viel Speicher, wie Sie tatsächlich benötigen lets have?
Also gibt es Vor-und Nachteile hier.
Einer der Pluspunkte ist jetzt, dass wir die Dynamik haben.
Egal, wo die Stücke der Erinnerung sind, dass sind kostenlos,
Ich kann nur von erstellen sortieren diese Semmelbrösel über Zeiger
mein ganzes verketteten Liste aneinanderreihen.
Aber ich zahlen mindestens ein Preis.
>> Was muss ich aufgeben müssen, zu gewinnen verkettete Listen?
Yeah? [Schüler Antwort unverständlich] Gut.
Sie benötigen mehr Speicher. Jetzt brauche ich Platz für diese Zeiger,
und im Falle dieser super einfach verkettete Liste
das ist nur versuchen, Zahlen, die 4 Bytes zu speichern, halten wir sagen
gut, ist ein Zeiger 4 Bytes, so jetzt habe ich buchstäblich verdoppelt
die Menge an Speicher brauche ich nur, um diese Liste zu speichern.
Aber auch dies ist eine Konstante Kompromiss in der Informatik
zwischen Zeit und Raum und Entwicklung, Aufwand und andere Ressourcen.
Was ist ein weiterer Nachteil der Verwendung einer verketteten Liste? Yeah?
[Schüler Antwort unverständlich]
Gut. Nicht so einfach zu erreichen. Wir können nicht mehr nutzen
Woche 0 Prinzipien wie teile und herrsche.
Und genauer gesagt, binäre Suche. Denn obwohl wir Menschen
kann grob sehen, wo in der Mitte dieser Liste ist,
der Computer nur weiß, dass diese verketteten Liste unter der Adresse genannt das erste Mal startet.
Und das ist 0x123 oder so ähnlich.
Und der einzige Weg das Programm finden Sie das mittlere Element
ist, um tatsächlich die gesamte Liste.
Und selbst dann ist es buchstäblich um die ganze Liste zu suchen, weil
sogar einmal erreichen Sie das mittlere Element, indem Sie die Zeiger,
Sie, das Programm, haben keine Ahnung, wie lange diese Liste ist möglicherweise auch
bis Sie traf das Ende, und wie Sie wissen, programmatisch
dass Sie am Ende einer verketteten Liste sind?
Es gibt eine spezielle NULL-Zeiger, so wieder, eine Konvention.
Anstatt diesen Zeiger verwenden wir definitiv nicht wollen, dass es einige Müll Wert
Hinweis Bühne irgendwo, wir wollen, dass es Hand nach unten, NULL,
so dass wir diesen Terminus in dieser Datenstruktur, so dass wir, wo es endet kennen.
>> Was ist, wenn wir dies manipulieren wollen?
Wir haben die meisten dieser visuell und mit Menschen,
aber was, wenn wir eine Insertion tun?
So die ursprüngliche Liste war 9, 17, 20, 22, 29, 34.
Was, wenn wir wollten dann malloc Platz für Nummer 55, ein Knoten für sie,
und dann wollen wir 55 in die Liste einzufügen, so wie wir am Montag getan hat?
Wie machen wir das? Nun kam Anita und sie im Wesentlichen ging die Liste.
Sie begann am ersten Element, dann die nächste, die nächste, der nächsten, am nächsten, am nächsten.
Schließlich traf die linke den ganzen Weg hinunter
und erkannte, oh, das ist NULL. Also, was Zeigermanipulation getan werden musste?
Die Person, die am Ende war, Nummer 34, musste seine linke Hand erhoben
zu Punkt 55, brauchte 55 ihren linken Arm nach unten, um die neue Nullabschlusszeichen sein. Fertig.
Ganz einfach bis 55 in eine sortierte Liste einzufügen.
Und wie könnte dies aussehen?
>> Lassen Sie mich gehen Sie vor und eröffnen einen Code Beispiel hier.
Ich werde eröffnen gedit, und lassen Sie mich eröffnen zwei Dateien zuerst.
Eines ist list1.h, und lassen Sie mich nur daran erinnern, dass dies der Teil des Codes war
die wir verwendet, um einen Knoten zu repräsentieren.
Ein Knoten verfügt sowohl über einen int namens n und einen Zeiger namens Next dass nur auf die nächste Sache in der Liste.
Das ist jetzt in einer. H-Datei. Warum?
Es gibt diese Konvention, und wir haben nicht zunutze gemacht eine riesige Menge selbst,
aber die Person, printf und andere Funktionen schrieb
gab als Geschenk an die Welt all diese Funktionen, indem er eine Datei namens stdio.h.
Und dann gibt es string.h, und dann gibt es map.h, und es gibt all diese h-Dateien
dass Sie vielleicht gesehen oder benutzt haben während der Laufzeit von anderen Leuten geschrieben.
Typischerweise in diesen. H Dateien sind nur Dinge wie typedefs
oder Erklärungen von benutzerdefinierten Typen oder Deklarationen von Konstanten.
Sie müssen nicht gestellt Funktionen 'Implementierungen in Header-Dateien.
Sie setzen stattdessen nur ihre Prototypen.
Sie stellen Dinge, die Sie freigeben möchten, mit der Welt, was sie brauchen
Um zu kompilieren ihren Code. So, nur um in dieser Gewohnheit zu bekommen,
haben wir beschlossen, das Gleiche zu tun. Es gibt nicht viel in list1.h,
aber wir haben etwas, das von Interesse sein könnten, um Menschen setzen in der Welt
die wollen uns verlinkten Liste Implementierung verwenden.
Jetzt, in list1.c, werde ich nicht durch diese ganze Sache
weil es ein bisschen lang ist, dieses Programm, aber wir führen Sie es real schnell an der Eingabeaufforderung.
Lassen Sie mich zu kompilieren list1, lassen Sie mich dann führen list1, und was Sie sehen, ist
wir haben simuliert ein einfaches kleines Programm hier
das wird mir zu erlauben, hinzuzufügen und zu entfernen Nummern in einer Liste.
Also lass mich gehen Sie vor und geben Sie 3 für das Menü Option 3.
Ich möchte die Nummer einfügen - lasst uns die erste Zahl, die 9 war,
und jetzt bin ich erzählte der Liste ist nun 9.
Lassen Sie mich gehen Sie vor und das andere tun Insertion, so schlug ich Menüpunkt 3.
Welche Nummer muss ich einfügen wollen? 17.
Enter. Und ich werde tun, nur eine mehr.
Lassen Sie mich die Nummer 22.
So haben wir die Anfänge der verketteten Liste, die wir in slide hatte vor einem Augenblick.
Wie ist das Einsetzen tatsächlich passiert?
Tatsächlich ist 22 nun am Ende der Liste.
So die Geschichte uns erzählt auf der Bühne am Montag und wieder verschlossen gerade jetzt
muss tatsächlich im Code geschehen.
Lassen Sie uns einen Blick. Lassen Sie mich nach unten scrollen in dieser Datei.
Wir beschönigen einige der Funktionen,
aber wir gehen, um, sagen wir, die Funktion EINFÜGEN.
>> Lasst uns sehen, wie wir über das Einfügen eines neuen Knotens in dieser verketteten Liste zu gehen.
Wo ist die Liste erklärt? Nun, lassen Sie blättern ganzen Weg bis an der Spitze,
und merke, dass meine verkettete Liste im Wesentlichen als einzigen Zeiger, die zunächst NULL ist erklärt.
Also ich bin mit einer globalen Variablen hier, was in der Regel haben wir gegen gepredigt
denn es macht Ihren Code ein wenig chaotisch zu pflegen,
Es ist eine Art faul, in der Regel, aber es ist nicht faul und es ist nicht falsch, und es ist nicht schlecht
wenn Ihr Programm die einzige Aufgabe im Leben ist es, eine verknüpfte Liste zu simulieren.
Das ist genau das, was wir tun.
Also anstatt zu erklären dies in Haupt-und dann müssen sie auf jeden Funktion übergeben
Wir haben in diesem Programm geschrieben, wir stattdessen erkennen, oh, lass uns einfach machen es global
weil der ganze Zweck dieses Programms ist es eine und nur eine verkettete Liste zu demonstrieren.
So, das fühlt sich okay. Hier sind meine Prototypen, und wir werden nicht durch alle diese gehen,
aber ich schrieb eine Löschfunktion, eine Suchfunktion, ein Insert-Funktion und eine Traverse-Funktion.
Aber lasst uns jetzt wieder nach unten gehen, um die Insert-Funktion
und sehen, wie diese hier funktioniert.
Insert ist online - here we go.
Einfügen. Es spielt also keine Argumente, weil wir zu fragen, sind
der Benutzer innerhalb dieser Funktion für die Nummer, die sie einfügen möchten.
Aber zuerst, bereiten wir ihnen etwas Platz.
Dies ist eine Art copy and paste aus dem anderen Beispiel.
In diesem Fall waren wir Zuordnung eines int, diesmal sind wir Zuweisung eines Knotens.
Ich weiß nicht wirklich erinnern, wie viele Bytes ein Knoten ist, aber das ist in Ordnung.
Sizeof herausfinden können, dass für mich.
Und warum bin ich Überprüfung auf NULL in Zeile 120?
Was könnte schief gehen in Linie 119? Yeah?
[Schüler Antwort unverständlich]
Gut. Nur könnte der Fall, dass ich zu viel Speicher gestellt werden
oder etwas nicht stimmt und das Betriebssystem nicht genügend bytes mir zu geben,
so signalisiert er so viel durch Rücksendung NULL, und wenn ich nicht für, dass der Check
und ich einfach blind fahren verwenden Sie die Adresse zurückgegeben, könnte es sein, NULL.
Es könnte einige unbekannte Wert sein, nicht eine gute Sache, wenn ich -
tatsächlich kein unbekannter Wert. Es könnte NULL sein, so will ich nicht
zu missbrauchen und riskieren Dereferenzierung es.
Wenn das passiert, ich habe gerade zurück und wir werden tun, wie ich es nicht wieder eine Erinnerung überhaupt.
>> Ansonsten sage ich der Benutzer geben Sie mir eine Nummer einzufügen, rufe ich unseren alten Freund GetInt,
und dann war die neue Syntax wir am Montag vorgestellt.
'Newptr-> n' bedeutet, nehmen Sie die Adresse, die Sie von malloc gegeben wurden
Erforderlich ist eine das erste Byte eines neuen Knotens Objekt,
und dann dem Feld namens n gehen.
Ein wenig Trivia-Frage: Dies ist äquivalent zu dem, was kryptischer Code-Zeile?
Wie sonst hätte ich das geschrieben? Möchten Sie einen Stich nehmen?
[Schüler Antwort unverständlich]
Gut. Mit der. N, aber es ist nicht ganz so einfach, wie dieses.
Was brauche ich zuerst tun? [Schüler Antwort unverständlich]
Gut. Ich muss * newptr.n tun.
Das ist also sagen neuen Zeiger ist offensichtlich eine Adresse. Warum?
Da wurde es von malloc zurückgegeben. Der * newptr sagen "go there"
und dann, wenn Sie dort sind, dann können Sie das besser vertraut. n,
aber das sieht einfach nur ein wenig hässlich, vor allem, wenn wir Menschen zu gehen
Zeichnen Zeiger mit Pfeilen die ganze Zeit, die Welt standardisiert auf diesen Pfeil-Notation,
was macht genau das Gleiche.
So verwenden Sie nur die ->-Notation, wenn das Ding auf der linken Seite ist ein Zeiger.
Andernfalls, wenn es eine tatsächliche Struktur ist, verwenden Sie die. N.
Und dann das: Warum muss ich newptr-> next initialisiert auf NULL?
Wir wollen keine baumelnden linke Hand nach dem Ende der Bühne.
Wir wollen, dass es senkrecht nach unten, was bedeutet, das Ende dieser Liste
könnte an diesem Knoten zu sein, so dass wir besser darauf achten, es ist NULL.
Und überhaupt, die Initialisierung Ihrer Variablen oder Ihre Daten Mitglieder und Strukturen
etwas ist nur gute Praxis.
Nur lassen Müll bestehen und weiterhin in der Regel gibt es bekommt man in Schwierigkeiten
Wenn Sie vergessen, etwas später tun.
>> Hier sind ein paar Fälle. Dies wiederum ist die Insert-Funktion,
und das erste, was ich prüfen ist, wenn die Variable namens ersten,
dass die globale Variable ist NULL, dh es gibt keine verketteten Liste.
Wir haben keine Zahlen eingefügt, so ist es trivial, um diesen Strom Nummer einfügen
in die Liste, weil es nur gehört am Anfang der Liste.
Das war also, wenn Anita gerade stand hier allein vorgibt
niemand war hier auf der Bühne, bis wir einen Knoten zugeordnet,
dann konnte sie ihre Hand zum ersten Mal zu erhöhen,
wenn alle anderen hatten auf der Bühne nach ihr kommen am Montag.
Jetzt ist hier, das ist ein wenig Kontrolle, wo ich muss sagen, wenn der neue Knoten den Wert von n
beträgt <den Wert von n in der aktuellen ersten Knoten,
Das heißt, es ist eine verknüpfte Liste, die angefangen hat.
Es gibt mindestens ein Knoten in der Liste, aber diese neue Mann
gehört, bevor es so, wir müssen die Dinge bewegen.
In anderen Worten, wenn die Liste mit gerade erst begonnen hat, sagen wir,
nur die Zahl 17, das ist das ist - eigentlich können wir dies noch deutlicher machen.
Wenn wir beginnen unsere Geschichte mit einem Zeiger hier als erste,
und anfangs ist es NULL, und wir die Nummer 9,
die Zahl 9 gehört eindeutig zu Beginn der Liste.
Also lasst uns so tun wir gerade malloced die Adresse oder die Nummer 9 und steckte es hier.
Wenn die ersten 9 ist standardmäßig das erste Szenario diskutierten wir nur bedeutet, let Standpunkt dieser Kerl hier,
lassen dies als NULL; jetzt haben wir die Zahl 9.
Die nächste Zahl, die wir einfügen wollen ist 17.
17 gehört hierher, so dass wir gehen zu müssen, einige logische Abstufung durch dies zu tun.
Also lasst uns statt, bevor das machen wir, wir behaupten, dass wir die Zahl 8 legen wollte.
>> Also nur der Einfachheit halber, werde ich hier ziehen.
Aber denken Sie daran, kann malloc es fast überall setzen.
Aber für Zeichnung willen, werde ich es hier setzen.
So behaupten, ich habe gerade einen Knoten für die Zahl 8 zugeordnet, dies ist standardmäßig NULL.
Was muss nun geschehen? Ein paar Dinge.
Wir haben diesen Fehler auf der Bühne am Montag, wo wir einen Zeiger wie folgt aktualisiert,
Dann tat dies, und dann haben wir behauptet - wir verwaiste alle anderen auf der Bühne.
Weil Sie kann nicht - die Reihenfolge der Operationen ist hier wichtig,
denn jetzt haben wir diese Knoten 9, die gerade ist eine Art im Raum schwebend verloren.
Das war also nicht der richtige Ansatz am Montag.
Wir müssen zuerst noch etwas anderes zu tun.
Der Zustand der Welt sieht wie folgt aus. Anfänglich hat 8 zugeordnet.
Was wäre ein besserer Weg, Einfügen 8 sein?
Statt der Aktualisierung dieses Zeigers erste, aktualisieren Sie einfach diese hier statt.
Also brauchen wir eine Codezeile, werde diese NULL-Zeichen wiederum ist
in eine tatsächliche Zeiger, der am Knoten 9 zeigt ist,
und dann können wir sicher zuerst ändern an dieser Kerl hier zeigen.
Jetzt haben wir eine Liste, eine verkettete Liste, aus zwei Elementen.
Und was bedeutet das eigentlich, wie hier zu sehen?
Wenn wir auf den Code schauen, bemerken, dass ich genau das getan.
Ich habe gesagt, newptr, und in dieser Geschichte, newptr wurde bei dieser Kerl zeigt.
>> Also lass mich ziehen eine weitere Sache, und ich sollte ein wenig mehr Raum für diese verlassen haben.
So vergeben die winzig kleine Zeichnung.
Dieser Kerl wird als newptr.
Das ist die Variable, die wir erklärt, ein paar Zeilen zuvor in line - knapp über 25.
Und es ist bis 8 zeigt. Also, wenn ich newptr-> next sagen, dass bedeutet, gehen Sie zu der Struktur
das ist, die bei von newptr hingewiesen, so sind wir hier, dorthin zu gehen.
Dann wird der Pfeil sagen Sie das nächste Feld, und dann die = sagt gestellt, welchen Wert es?
Der Wert, der in der ersten war, welchen Wert war zuerst da?
Zunächst wurde an diesem Knoten zeigt, so dass bedeutet dies sollte nun an diesem Knoten zeigen.
In anderen Worten, sieht, was allerdings eine lächerliche Verwirrung mit meiner Handschrift,
was ist eine einfache Idee, nur bewegen diese Pfeile um
übersetzt den Code genau mit diesem Einzeiler.
Bewahren, was in erster in das nächste Feld und aktualisieren Sie dann, was zuerst tatsächlich ist.
Lassen Sie uns weiter und schneller vorwärts gehen einige davon,
und nur schauen Sie sich diese tail Einsetzen für jetzt.
Angenommen, ich bis zu dem Punkt, wo ich finde, dass das nächste Feld eines Knotens NULL bekommen.
Und an diesem Punkt in der Geschichte, ein Detail, dass ich beschönigen
ist, dass ich einen weiteren Zeiger eingeführt hier in Zeile 142, Vorgänger Zeiger.
Im wesentlichen an diesem Punkt in der Geschichte, wenn die Liste erhält lang,
Ich Art brauchen, um es mit zwei Fingern zu gehen, denn wenn ich zu weit gehen,
Speichern in einer Single-length-Liste können Sie nicht rückwärts gehen.
So diese Idee predptr ist meine linken Finger und newptr - nicht newptr.
Ein weiterer Zeiger, hier ist meine andere Finger, und ich bin einfach Art des Gehens auf der Liste.
Deshalb ist, was existiert. Aber lassen Sie berücksichtigen nur eine der einfacheren Fälle hier.
Wenn dieses Zeigers nächste Feld ist NULL, was ist der logische Implikation?
Wenn Sie durchqueren diese Liste sind und Sie treffen einen NULL-Zeiger?
Du bist am Ende der Liste, und so wird der Code dann hängen diese ein zusätzliches Element
ist eine Art der intuitiven nehmen, dass Knoten, dessen nächste Zeiger NULL ist,
so ist dies derzeit NULL, und zu verändern, obwohl, um die Adresse des neuen Knotens ist.
So sind wir nur Zeichnen im Code auf den Pfeil, dass wir auf der Bühne machte, indem jemand mit der linken Hand.
>> Und der Fall, dass ich meine Hände jetzt winken,
nur weil ich denke, es ist leicht verirren, wenn wir es in dieser Art von Umgebung zu tun,
zum Einsetzen in der Liste der mittleren überprüfen.
Aber gerade intuitiv, muss was passieren, wenn Sie herausfinden möchten,
wo einige Zahl in der Mitte gehört, Sie zu tun haben, ihn zu gehen
mit mehr als einem Finger, mehrere Zeiger,
herauszufinden, wo es durch Überprüfung gehört, ist das Element <die aktuelle,
> Die aktuelle ein, und sobald Sie diesen Ort,
dann müssen Sie diese Art von Hütchenspiel tun, wo man die Zeiger bewegen sehr sorgfältig.
Und die Antwort, wenn Sie möchten die Vernunft durch diese wie zu Hause auf eigene Faust,
läuft darauf hinaus, nur um diese beiden Zeilen Code, aber die Reihenfolge dieser Zeilen ist super wichtig.
Denn wenn man jemandem die Hand sinken und heben jemand anderes in der falschen Reihenfolge,
wieder, könnten Sie am Ende Verwaisung der Liste.
Um mehr konzeptionell fassen, ist das Einfügen am Heck relativ einfach.
Das Einsetzen an der Spitze ist auch relativ einfach,
aber Sie müssen zu aktualisieren Ein zusätzliches Indiz diesmal
die Nummer 5 in der Liste hier zu quetschen,
und dann Einfügen in der Mitte geht noch mehr Aufwand,
sehr sorgfältig die Nummer 20 in der richtigen Position,
welches zwischen 17 und 22.
Sie müssen also so etwas wie die neuen Knoten 20 auf 22 zu tun,
und dann muss die Knoten Zeiger auf aktualisierte letzten werden?
Es ist 17, um tatsächlich einfügen.
Also noch einmal, ich werde aufschieben den eigentlichen Code für die jeweilige Umsetzung.
>> Auf den ersten Blick ist es ein wenig überwältigend, aber es ist wirklich nur eine Endlosschleife
Das ist Looping, Looping, Looping, Looping und brechen, sobald Sie die NULL-Zeiger getroffen,
an welcher Stelle Sie tun können, die erforderliche Insertion.
Dies also ist repräsentativ verketteten Liste Platzhalter-Code.
Das war eine Art viel, und es fühlt sich an, wie wir ein Problem gelöst haben,
aber wir haben eine ganze andere eingeführt. Ehrlich gesagt, haben wir die ganze Zeit verbracht
auf großen O und Ω und Laufzeit, versuchen, Probleme schneller zu lösen,
und hier sind wir einen großen Schritt nach hinten, spürt es.
Und noch, wenn das Ziel ist, Daten zu speichern,
es fühlt sich an wie der Heilige Gral, wie wir am Montag sagte, wäre wirklich
die Dinge sofort zu speichern.
>> In der Tat annehmen, dass wir beiseite verketteten Liste für einen Moment tat
und wir stattdessen führte den Begriff einer Tabelle.
Und lasst uns einfach eine Tabelle denken Sie einen Moment als ein Array.
Dieses Array und dieser Fall hier hat rund 26 Elementen, 0 bis 25,
und annehmen, dass Sie einige Brocken Speicher benötigt für Namen:
Alice und Bob und Charlie und dergleichen.
Und Sie brauchen etwas Datenstruktur um diese Namen zu speichern.
Nun, man könnte so etwas wie eine verkettete Liste
und man konnte die Liste einfügen Alice, bevor Bob und Charlie nach Bob gehen und so weiter.
Und in der Tat, wenn Sie wollen, um Code so wie Nebenbei sehen
wissen, dass in list2.h wir genau das tun.
Wir werden nicht durch diesen Code zu gehen, aber dies ist eine Variante des ersten Beispiels
das stellt einen weiteren struct wir vor genannten Studenten gesehen habe,
und dann, was es eigentlich speichert in der verketteten Liste ist ein Zeiger auf einen Studenten-Struktur
anstelle eines einfachen kleinen Integer, n ist.
So klar es gibt Codes gibt, beinhaltet eigentlichen Strings,
aber wenn das Ziel bei der Hand nun wirklich ist, die Effizienz Problem anzugehen,
Wäre es nicht schön, wenn wir ein Objekt namens Alice sind gegeben,
Wir wollen sie in der richtigen Stelle in einer Datenstruktur setzen,
es fühlt sich an, wie es sein würde wirklich schön, nur legte Alice,
deren Name mit A, in der ersten Lage.
Und Bob, deren Name mit B, in der zweiten Lage.
Mit einem Array oder fangen wir nennen es eine Tabelle, eine Hash-Tabelle an, dass
können wir genau das tun. Wenn wir einen Namen wie Alice gegeben,
eine Zeichenkette, wie Alice, weiß, wo du A-l-i-c-e?
Wir brauchen eine hueristic. Wir brauchen eine Funktion, um eine Eingabe wie Alice nehmen
und gibt eine Antwort, "Put Alice an dieser Stelle."
Und diese Funktion, diese black box, wird als eine Hash-Funktion sein.
>> Eine Hash-Funktion ist etwas, das einen Eingang hat, wie "Alice",
und kehrt, dann typischerweise die numerische Position in irgendeiner Datenstruktur wo Alice gehört.
In diesem Fall sollten Sie unsere Hash-Funktion relativ einfach sein.
Unsere Hash-Funktion sollte sagen, wenn Sie "Alice", die Figur, die ich zu kümmern sollte gegeben werden?
Die erste. So sehe ich [0], und dann sage ich, wenn [0] Zeichen A, wieder die Nummer 0.
Wenn es B ist, kehren ein. Wenn es C, zurückzukehren 2, und so weiter.
Alle 0 Index, und das würde mir erlauben, Alice und dann Bob und dann Charlie einfügen und so weiter
in diese Datenstruktur. Aber es gibt ein Problem.
Was passiert, wenn Anita kommt wieder?
Wohin mit Anita? Ihr Name auch mit dem Buchstaben A,
und es fühlt sich wie wir ein noch größeres Durcheinander von diesem Problem gemacht haben.
Wir haben jetzt unmittelbaren Insertion, konstante Zeit Insertion, in eine Datenstruktur
anstatt Worst-Case-linear,
aber was können wir mit Anita zu tun in diesem Fall?
Was sind die zwei Optionen, wirklich? Yeah?
[Schüler Antwort unverständlich] Okay, so konnten wir eine weitere Dimension haben.
Das ist gut. So können wir bauen Dinge in 3D, wie wir darüber gesprochen, mündlich am Montag.
Wir könnten einen anderen Zugangspunkt hier hinzufügen, aber angenommen, dass keine, ich versuche zu halten so einfach.
Das ganze Ziel ist hier die sofortige konstanter Zeit Zugriff haben,
Also das ist zu viel Komplexität hinzuzufügen.
Was sind andere Optionen beim Versuch, Anita in diese Datenstruktur einfügen? Yeah?
[Schüler Antwort unverständlich] Gut. So konnten wir alle anderen nach unten zu bewegen,
wie Charlie stößt sich Bob und Alice, und dann haben wir Anita, wo sie wirklich will zu sein.
>> Natürlich, jetzt gibt es ein Nebeneffekt.
Diese Datenstruktur ist wahrscheinlich sinnvoll, nicht weil wir die Menschen legen einmal wollen
sondern weil wir wollen prüfen, ob sie später dort sind
wenn wir drucken alle Namen in der Datenstruktur wollen.
Wir werden etwas mit diesen Daten schließlich tun.
So jetzt haben wir Art über Alice, die nicht mehr ist, wo sie sein soll geschraubt.
Auch ist Bob, noch ist Charlie.
Also vielleicht ist dies nicht so eine gute Idee.
Aber in der Tat ist dies eine Option. Wir konnten zu verlagern jeden nieder,
oder Heck, Anita spät gekommen, um das Spiel, warum nicht wir haben gerade Anita
nicht hier, nicht hier, nicht hier, lass uns einfach legte ein wenig tiefer in der Liste.
Aber dann dieses Problem beginnt wieder zu übergehen.
Sie könnten in der Lage sein Alice finden sofort, basierend auf ihren Vornamen.
Und Bob sofort, und Charlie. Aber dann schauen Sie für Anita,
und du, hmm sehen, ist Alice im Weg.
Nun, lassen Sie mich unter Alice überprüfen. Bob ist nicht Anita.
Charlie ist nicht Anita. Oh, da ist Anita.
Und wenn Sie weiterhin den Zug der Logik den ganzen Weg,
was ist das Worst-Case-Laufzeit finden oder Einfügen von Anita in diese neue Datenstruktur?
Es ist O (n), nicht wahr?
Denn im schlimmsten Fall gibt es Alice, Bob, Charlie. . .
den ganzen Weg hinunter jemandem namens "Y", so gibt es nur einen Ort verlassen.
Zum Glück haben wir keine sogenannte "Z", so stellen wir Anita ganz unten.
>> Wir haben nicht wirklich das Problem gelöst.
Also vielleicht brauchen wir diese dritte Dimension vorzustellen.
Und es stellt sich heraus, wenn wir diese dritte Dimension eingeführt haben,
Wir können dies nicht perfekt, aber der Heilige Gral wird bekommen
konstanter Zeit Einsetzen und dynamische Einfügungen, so dass
haben wir nicht zu hart-Code ein Array der Größe 26.
Wir können so viele Namen einzufügen, wie wir wollen, aber wir nehmen unsere 5-minütige Pause hier
und dann tun, richtig.
Gut. Ich habe die Geschichte bis ziemlich künstlich gibt
indem Alice und dann Bob und dann Charlie und dann Anita,
dessen Name offenbar werde, um mit Alice kollidieren.
Aber die Frage, die wir am Montag endete mit ist nur, wie wahrscheinlich ist es,
Sie würde diese Art von Kollisionen? Mit anderen Worten,
wenn wir diese tabellarische Struktur zu verwenden beginnen, ist das wirklich nur ein Array,
in diesem Fall von 26 Zielen,
was ist, wenn unsere Eingänge statt gleichmäßig verteilt sind?
Es ist nicht künstlich Alice und Bob und Charlie und David usw. alphabetisch
es ist gleichmäßig über A bis Z. verteilt
>> Vielleicht werden wir einfach Glück, und wir gehen nicht zwei A-oder zwei B haben
mit sehr hoher Wahrscheinlichkeit, sondern als jemand darauf hingewiesen,
wenn wir verallgemeinerte dieses Problem und nicht von 0 bis 25
sondern etwa 0 bis 364 bzw. 65, oft die Anzahl der Tage in einem typischen Jahr
und stellte die Frage: "Was ist die Wahrscheinlichkeit, dass zwei von uns in diesem Raum am gleichen Tag Geburtstag haben?"
Anders ausgedrückt, was ist die Wahrscheinlichkeit, dass zwei von uns einen Namen beginnend mit A haben?
Die Art der Anfrage ist dieselbe, aber das Adressraum,
Dieses Suchraums, größer ist im Falle von Geburtstagen
weil wir so viele Tage im Jahr als Buchstaben im Alphabet.
Was ist die Wahrscheinlichkeit einer Kollision?
Nun, wir können dies durch die herauszufinden, die Mathematik in die entgegengesetzte Richtung zu denken.
Was ist die Wahrscheinlichkeit, dass keine Kollisionen?
Nun, sagt dieser Ausdruck hier, dass, was die Wahrscheinlichkeit ist
wenn es nur eine Person in diesem Raum, dass sie eine einzigartige Geburtstag haben?
Es ist 100%. Denn wenn es nur eine Person im Raum,
seinen Geburtstag kann jeder der 365 Tage aus dem Jahr.
So 365/365 Optionen gibt mir einen Wert von 1.
So ist die Wahrscheinlichkeit, in Frage im Moment ist nur 1.
Aber wenn es eine zweite Person im Zimmer,
was ist die Wahrscheinlichkeit, dass ihr Geburtstag anders ist?
Es gibt nur 364 möglichen Tag, ignorieren Schaltjahre,
für ihren Geburtstag nicht mit den anderen Personen kollidieren.
So 364/365. Wenn eine dritte Person kommt, ist es 363/365, und so weiter.
So halten wir miteinander multipliziert diese Fraktionen, die werden immer kleiner und kleiner,
um herauszufinden, was ist die Wahrscheinlichkeit, dass alle von uns einzigartig Geburtstage haben?
Aber dann können wir natürlich, nehmen Sie nur diese Antwort und drehen es um
und tun 1 minus alle, dass ein Ausdruck wir schließlich bekommen werde
Wenn Sie die Rückseite Ihrer math Pfund erinnern, es sieht ein wenig so etwas wie dieses,
das ist viel leichter interpretiert grafisch dargestellt.
Und diese Grafik hat hier auf der x-Achse die Anzahl der Geburtstage,
oder die Anzahl der Personen mit Geburtstage und auf der y-Achse ist die Wahrscheinlichkeit einer Übereinstimmung.
Und was das sagt, ist, dass wenn man, sagen wir, auch,
wählen wir so etwas wie 22, 23.
Wenn es 22 oder 23 Leute im Raum,
die Wahrscheinlichkeit, dass zwei von diesen nur sehr wenige Menschen gehen, um am gleichen Tag Geburtstag haben
ist eigentlich super high, kombinatorisch.
50% Wahrscheinlichkeit, dass in einer Klasse mit nur 22 Personen, ein Seminar, praktisch,
2 von diesen Leuten gehen, um am gleichen Tag Geburtstag haben.
Denn es gibt so viele Möglichkeiten, wie Sie am gleichen Tag Geburtstag haben.
Noch schlimmer ist, wenn man sich an der rechten Seite des Diagramms,
durch die Zeit, Sie haben eine Klasse mit 58 Schülern in ihr,
die Wahrscheinlichkeit von 2 Personen einen Geburtstag ist super, super hoch, fast 100%.
Nun, das ist eine Art von Spaß Tatsache über das wahre Leben.
>> Aber die Auswirkungen, jetzt, für Datenstrukturen und Speicherung von Informationen
bedeutet, dass nur vorausgesetzt, Sie haben eine schöne, saubere, gleichmäßige Verteilung von Daten
und Sie haben einen groß genug Array ein paar Dinge passen
bedeutet nicht, dass du gehst, um Menschen in einzigartigen Orten zu bekommen.
Du wirst Kollisionen haben. So diese Vorstellung von Hashing, wie es heißt,
unter einen Eingang wie "Alice" und massiert es in irgendeiner Weise
und dann immer wieder eine Antwort wie 0 oder 1 oder 2.
Kommen wir zurück eine Ausgabe Aus dieser Funktion wird durch diese Kollisionswahrscheinlichkeit geplagt.
Also, wie können wir damit umgehen, diese Kollisionen?
Nun, auf dem einen Fall, können wir die Idee, dass vorgeschlagen wurde.
Wir können nur zu verlagern jeden nieder, oder vielleicht ein wenig einfacher,
anstatt sich alle anderen, lasst uns einfach bewegen Anita auf den Grund des zur Verfügung stehenden Platz.
Also, wenn Alice ist in 0, Bob in 1 ist, ist Charlie in 2,
wir gerade auf Anita an Position 3.
Und dies ist eine Technik, bei Datenstrukturen als lineares Sondieren.
Linear weil man nur zu Fuß diese Zeile, und du bist Art von Probing
verfügbaren Stellen in der Datenstruktur.
Natürlich zufällt dies in O (n).
Wenn die Datenstruktur ist wirklich voll ist, gibt es 25 Leute in es schon,
und dann Anita entlang kommt, endet sie an, was würde location Z sein, und das ist in Ordnung.
Sie passt immer noch, und wir können sie später zu finden.
>> Aber das war im Gegensatz zu dem Ziel der Beschleunigung Dinge.
So was, wenn wir stattdessen führte diese dritte Dimension?
Diese Technik wird allgemein als getrennte Verkettung oder mit Ketten.
Und was für eine Hash-Tabelle ist jetzt, diese tabellarische Struktur,
Ihr Tisch ist nur ein Array von Zeigern.
Aber was diese Zeiger auf ist guess what?
Eine verkettete Liste. So was passiert, wenn wir das Beste aus beiden Welten?
Wir verwenden Arrays für die ersten Indizes
in die Datenstruktur so können wir sofort auf [0] [1], [30] oder so weiter gehen,
aber so, dass wir eine gewisse Flexibilität, und wir können Anita und Alice und Adam passen
und andere Ein Name,
wir stattdessen ließ die andere Achse beliebig wachsen.
Und wir schließlich ab Montag, haben diese Möglichkeiten des Ausdrucks mit verknüpften Liste.
Wir können eine Datenstruktur beliebig wachsen.
Alternativ könnten wir nur einen großen 2-dimensionalen Array,
aber das geht zu einer schrecklichen Situation, wenn eine der Zeilen in einem 2-dimensionalen Array
ist nicht groß genug für die zusätzliche Person, deren Name zufällig mit A beginnen
Gott bewahre, müssen wir eine riesige 2-dimensional umverteilen
nur weil es so viele Menschen mit dem Namen A,
vor allem, wenn es so wenige Menschen namens Z etwas.
Es ist gerade dabei, eine sehr spärliche Daten-Struktur sein.
So ist es nicht perfekt mit allen Mitteln, aber jetzt haben wir wenigstens die Möglichkeit haben
um sofort herauszufinden, wo Alice oder Anita gehört,
zumindest hinsichtlich der vertikalen Achse,
und dann müssen wir nur noch zu entscheiden, wo Anita oder Alice in dieser verketteten Liste setzen.
Wenn wir nicht über das Sortieren von Dingen kümmern, konnte, wie schnell wir legen Alice in eine Struktur wie diese?
Es ist konstante Zeit. Wir Index in [0], und wenn niemand da ist,
Alice geht am Anfang dieser verketteten Liste.
Aber das ist keine große Sache. Denn wenn Anita dann kommt
eine Zahl von Schritten später, woher Anita gehören?
Nun, [0]. OOP. Alice ist bereits in dieser verketteten Liste.
>> Aber wenn wir nicht über das Sortieren diese Namen egal,
können wir nur bewegen Alice vorbei, Einsatz Anita, aber selbst das ist konstante Zeit.
Auch wenn es Alice und Adam und all diese anderen A-Namen,
es ist nicht wirklich verschieben sie physisch. Warum?
Weil wir gerade hier mit verketteten Liste, wer weiß wurden diese Knoten sind sowieso?
Alles, was Sie tun müssen, ist bewegen Sie die Semmelbrösel.
Verschieben Sie die Pfeile um, Sie müssen nicht körperlich bewegen alle Daten um.
So können wir legen Anita, in diesem Fall sofort. Konstante Zeit.
So haben wir in konstanter Zeit Lookup und konstanter Zeit Einsetzen von jemandem wie Anita.
Aber irgendwie vereinfache die Welt.
Was ist, wenn wir später wollen Alice zu finden?
Wie viele Schritte ist, dass gehen zu nehmen?
[Schüler Antwort unverständlich]
Genau. Die Zahl der Menschen, bevor Alice in der verknüpften Liste.
So ist es nicht ganz perfekt, weil unsere Datenstruktur hat wieder diese vertikale Zugang
und dann hat es diese verkettete Listen hängen - eigentlich, lasst uns nicht ziehen es ein Array.
Es hat diese verkettete Listen hängen von ihm weg, das sieht ein wenig so etwas wie dieses.
Aber das Problem ist, wenn Alice und Adam und all diese anderen A-Namen
Ende mehr und mehr dort drüben,
jemanden zu finden, könnte am Ende unter eine Reihe von Schritten,
bcause müssen Sie die verknüpfte Liste durchlaufen,
die eine lineare Operation.
So wirklich also die Einfügezeitpunkt letztlich O (n), wobei n die Anzahl der Elemente in der Liste.
Geteilt durch, lasst uns willkürlich nennen es m, wobei m die Anzahl der verbundenen Listen
dass wir in dieser vertikalen Achse.
Mit anderen Worten, wenn wir wirklich setzen eine gleichmäßige Verteilung von Namen,
völlig unrealistisch. Es gibt offensichtlich einige Briefe als andere.
>> Aber wenn man annimmt, für den Augenblick eine gleichmäßige Verteilung,
und wir haben n insgesamt Volk und m Gesamtlänge Ketten
Verfügung zu stellen, dann wird die Länge eines jeden dieser Ketten
ziemlich einfach wird der gesamte, n geteilt durch die Anzahl von Ketten ist.
So n / m. Aber hier, wo wir sicher sein können alle mathematisch clever.
m eine Konstante ist, weil es eine feste Anzahl von diesen.
Du wirst das Array zu Beginn erklären,
und wir sind nicht die Größe des vertikalen Achse. Per Definition bleibt die behoben.
Es ist nur die horizontale Achse, so zu sprechen, dass sich verändert.
So technisch ist dies eine Konstante. So, jetzt das Einsetzen der Zeit
ist so ziemlich O (n).
Also das hat nicht das Gefühl, dass alle viel besser.
Aber was ist die Wahrheit hier? Nun, die ganze Zeit, seit Wochen,
Wir haben gesagt, O (n ²). O (n), 2 x n ², - n, dividiert durch zwei. . . ech.
Es ist nur n ². Aber jetzt, in diesem Teil des Semesters
können wir anfangen, über die reale Welt wieder.
Und n / m ist absolut schneller als nur n allein.
Wenn Sie mehr als tausend Namen, und Sie brechen in mehrere Eimer
so dass Sie nur zehn Namen in jeder dieser Ketten,
absolut Suchen zehn Dinge geht, schneller zu sein als tausend Dinge.
Und so einer der kommenden Problemstellungen wird Sie herausfordern
über genau das denken, obwohl, yeah,
asymptotisch und mathematisch, ist dies immer noch nur linear,
die saugt in der Regel, wenn Sie versuchen, die Dinge zu finden.
In Wirklichkeit, es wird schneller sein als die
wegen dieser Divisor.
Und so gibt es wieder los, dies zu trade-off zu sein
und dieser Konflikt zwischen Theorie und Wirklichkeit,
und einen der Knöpfe beginnt sich zu diesem Zeitpunkt in den Semesterferien
ist mehr von der Realität ein, wie wir für Semesters das Ende Art vorzubereiten,
wie wir die Einführung in die Welt der Web-Programmierung,
wo wirklich, wird die Leistung gehen zu zählen, weil die Benutzer gehen, um
beginnen zu fühlen und schätzen schlechte Design-Entscheidungen.
>> So wie Sie über die Durchführung einer verlinkten gehen - eine Hash-Tabelle mit 31 Elementen?
Und das vorherige Beispiel wurde willkürlich über Geburtstage.
Wenn jemand Geburtstag 1. Januar oder 1. Februar werden wir sie in diesem Eimer gestellt.
Wenn es 2. Januar, 2. Februar, 2. März ist, werden wir sie in diesem Eimer gestellt.
Deshalb ist es 31 war. Wie kann man erklären, eine Hash-Tabelle?
Es kann ziemlich einfach, ist der Knoten * tabelle meiner beliebigen Namen für sie, [31].
Das gibt mir 31 Zeigern auf Knoten,
und das ermöglicht es mir, 31 Zeiger auf verkettete Listen haben
auch wenn diese Ketten sind zunächst NULL.
Was will ich zu setzen, wenn ich speichern möchten "Alice", "Bob", "Charlie"?
Nun müssen wir diese Dinge in einer Struktur wickeln
denn wir brauchen Alice zu Bob zeigen, um Charlie zeigen, und so weiter.
Wir können nicht einfach die Namen allein, so konnte ich eine neue Struktur namens Knoten hier.
>> Was ist eine tatsächliche Knoten? Was ist ein Knoten in diesem neuen verketteten Liste?
Die erste Sache, als Wort, ist für den Namen der Person.
LÄNGE vermutlich betrifft die maximale Länge eines menschlichen Namen,
was auch immer das ist, 20, 30, 40 Zeichen in verrückten Ecke Fällen,
und +1 ist für was? Es ist nur die zusätzlichen NULL-Zeichen, \ 0.
So wird dieser Knoten Einwickeln "etwas" in sich selbst,
aber es erklärt auch einen Zeiger namens nächsten
so dass wir Chain Alice an Bob, Charlie und so weiter.
Kann NULL sein, aber nicht unbedingt so sein.
Haben Sie Fragen zu dieser Hash-Tabellen? Yeah?
[Schüler fragen Frage, unverständlich] Ein Array - gute Frage.
Warum ist das char Wort in einem Array nicht nur char *?
In diesem etwas willkürliches Beispiel, wollte ich nicht zu haben, um Zuflucht
malloc für jeden der ursprünglichen Namen.
Ich wollte eine maximale Menge an Speicher für den String zu erklären
so dass ich in die Struktur kopieren Alice \ 0 und nicht mit malloc und free und dergleichen zu tun haben.
Aber ich könnte das tun, wenn ich ein größeres Bewusstsein für Raumnutzung wollte. Gute Frage.
So wollen wir versuchen, zu verallgemeinern weg von diesem
und konzentrieren den Rest von heute auf Datenstrukturen allgemein
und andere Probleme, die wir lösen mit den gleichen Grundlagen können
obwohl die Datenstrukturen selbst könnten in ihren Angaben abweichen.
>> So es sich herausstellt, in der Informatik, sind Bäume sehr häufig.
Und Sie können von einem Baum wie eine Art Stammbaum denken,
wo es einige Wurzeln, einige Matriarchin oder Patriarch,
Oma oder Opa oder früher zurück,
unter denen Mama und Papa oder verschiedene Geschwister oder dergleichen.
So eine Baumstruktur hat Knoten und hat Kinder,
meistens 0 oder mehr Kinder für jeden Knoten.
Und einige der Jargon, dass Sie in diesem Bild sehen Sie hier
irgendeine der kleine Kinder oder Enkel an den Rändern
, die haben keine Pfeile von ihnen ausgehenden,
das sind die sogenannten Blätter, und einem auf der Innenseite
ist ein innerer Knoten, man kann es nennen etwas in diese Richtung.
Aber diese Struktur ist sehr verbreitet. Dieser ist ein wenig willkürlich.
Wir haben ein Kind auf der linken Seite, wir haben drei Kinder auf der rechten Seite,
zwei Kinder auf dem Boden hinterlassen.
So können wir haben unterschiedlich große Bäume, aber wenn wir Dinge zu standardisieren starten,
und Sie könnten diese von Patrick Video erinnern, auf binäre Suche von einer früheren kurzen
online, Binärsuche muss nicht mit einer Anordnung durchgeführt werden
oder Stücke von Papier auf einer Tafel.
Angenommen, Sie möchten Ihre Zahlen in einem komplexeren Datenstruktur speichern wollte.
Sie könnten einen Baum wie diese.
Sie hätte eine Knoten in C deklariert, und dieser Knoten kann wenigstens zwei Elemente im Inneren davon haben.
Eine davon ist die Nummer, die Sie speichern wollen, und das andere ist - na ja, wir brauchen noch einen.
Die andere ist seine Kinder.
Also hier ist eine andere Datenstruktur. Dieser Zeitpunkt wird als ein Knoten Speichern einer Zahl n definiert
und dann zwei Zeigern, links Kindes und das Recht Kind.
Und sie sind nicht willkürlich. Was ist interessant an dieser Baum?
>> Was ist das Muster, wie wir diese angelegt oder wie Patrick es legte in seinem Video?
Es ist ziemlich offensichtlich, dass es einige Sortierung geht hier vor,
aber was ist die einfache Regel? Yeah?
[Schüler Antwort unverständlich]
Perfect. Wenn Sie einen Blick auf diese, sehen Sie die kleinen Zahlen auf der linken Seite,
großen Zahlen auf der linken Seite, aber das ist für jeden Knoten wahr.
Für jeden Knoten, seine linke Kind weniger als sie und ihre rechte Kind größer als dieser.
Was bedeutet dies jetzt, wenn ich diese Datenstruktur für, sagen wir, der Nummer 44 suchen möchten,
Ich habe an der Wurzel beginnen, denn wie bei allen diesen komplexere Datenstrukturen jetzt
wir haben nur einen Zeiger auf eine Sache, der Anfang.
Und in diesem Fall, ist der Beginn der Wurzel. Es ist nicht das linke Ende,
es ist die Wurzel dieser Struktur. Also ich sehe hier ist 55, und ich bin für 44 suchen.
Welche Richtung will ich gehen?
Nun, ich will nach links gehen, weil offensichtlich auf der rechten Seite wird zu groß sein.
Also hier merkt, du bist Art konzeptionell hacken den Baum in der Mitte
weil du nie auf der rechten Seite.
So jetzt habe ich von der 55 auf die 33 gehen. Es ist zu klein für eine Nummer.
Ich bin für 44 suchen, aber jetzt weiß ich, wenn 44 ist in diesem Baum, kann ich natürlich nach rechts gehen.
Also noch einmal, ich bin Beschneiden der Baum in der Mitte.
Es ist ziemlich identisch konzeptionell mit dem Telefonbuch.
Es ist identisch zu dem, was wir mit den Arbeiten an der Tafel hat,
aber es ist eine kompliziertere Struktur, die wir wirklich tun können
Diese teilen und zu erobern, indem Entwurf des Algorithmus,
und in der Tat, durchqueren eine Struktur wie diese - hoppla.
Durchlaufen einer Struktur wie diese, wo es nur "diesen Weg gehen oder gehen Sie auf diese Weise"
bedeutet, dass alle, dass Code, die Ihren Verstand auf den ersten gebogen bei ihrer Umsetzung in Abschnitt
oder zu Fuß durch sie zu Hause, für binäre Suche mit Rekursion oder Iteration
es ist ein Schmerz im Nacken. Finden Sie das mittlere Element, dann tun Sie Ihre Auf-oder Abrundung.
>> Es gibt eine Schönheit, weil wir nun Rekursion wieder
sondern viel mehr sauber. In der Tat, wenn Sie unter der Nummer 55, und Sie möchten 44 zu finden,
Sie gehen links in diesem Fall, so was tun Sie? Sie führen den exakt gleichen Algorithmus.
Sie überprüfen den Wert des Knotens, dann gehen Sie nach links oder rechts.
Dann überprüfen Sie den Wert des Knotens, gehen Sie nach links oder rechts.
Dieses ist perfekt auf Rekursion geeignet.
Also auch wenn in der Vergangenheit haben wir einige ziemlich willkürlich Beispiele mit Rekursion
das brauchte nicht rekursiv sein, mit Daten stuctures,
vor allem Bäume, es ist eine perfekte Anwendung dieser Idee, ein Problem
Schrumpfen, und dann die Lösung der gleichen Art von, jedoch kleiner Programm.
>> So gibt es eine andere Datenstruktur, die wir einführen können.
Dieser ist auf den ersten Blick aussehen kryptischen entwickelt, aber dieses ist erstaunlich.
Dies ist also eine Datenstruktur genannt Trie Trie, die aus der Wort-Wiederauffindungseinrichtung geerbt wird,
was nicht re-try-val ausgeprägt, aber das ist, was die Welt diese Dinge nennt. Versucht. T-R-I-e.
Es ist eine Baumstruktur von einer Art, aber jeder der Knoten in einem Trie
scheint was? Und das ist ein wenig irreführend, weil es irgendwie abgekürzt ist.
Aber es sieht aus wie jeder Knoten in diesem Trie ist eigentlich ein Array.
Und obwohl der Autor dieser Darstellung nicht gezeigt,
in diesem Fall ist dies ein Trie-Datenstruktur, deren Zweck im Leben ist, um Wörter zu speichern
wie A-l-i-c-e-oder B-O-B.
Und die Art und Weise, in der diese Daten speichert Alice und Bob und Charlie und Anita usw.
wird es verwendet ein Array, wodurch Alice in einer Trie speichern,
Wir beginnen bei den Root-Knoten, die wie ein Array aussieht,
und es ist in Kurzschrift geschrieben worden.
Der Autor verzichtet abcdefg, denn es gab keine Namen damit.
Sie zeigten nur M und P und T, aber in diesem Fall,
Lassen Sie uns weg von Alice und Bob und Charlie zu bewegen, um ein paar Namen, die hier sind.
Maxwell ist eigentlich in diesem Diagramm.
Wie hat der Autor store M-A-x-w-e-l-l?
Er oder sie begann an der Root-Knoten, und ging zu [M], so etwa 13, die 13. Position im Array.
Dann von dort aus gibt es einen Zeiger.
Ein Zeiger, die zu einem anderen Array.
Von dort führt der Autor in diesem Array am Standort A indiziert, da links oben dargestellt,
und dann hat er oder sie folgten den Zeiger zu einem anderen Array,
und ging auf den Zeiger an der Stelle X.
Dann im nächsten Matrixort W, E, L, L, und so weiter,
und schließlich, lasst uns tatsächlich versuchen, ein Bild zu bereiten.
Was bedeutet ein Knoten aussehen im Code?
Ein Knoten in einem Trie enthält ein Array von Zeigern auf weitere Knoten.
Aber es ist auch bekam eine Art von booleschen Wert zu sein, zumindest in dieser Implementierung.
Ich bin zufällig nennen es is_word. Warum?
Denn wenn Sie das Einfügen Maxwell, du bist nicht Einsetzen
alles in dieser Datenstruktur.
Sie sind nicht schriftlich M. Sie sind nicht schriftlich X.
Alles, was Sie tun, ist nach Zeigern.
Der Zeiger, M, dann wird der Zeiger, der A darstellt,
dann die Zeiger, X, W, E, L, L,
aber was Sie brauchen, um am Ende zu tun ist eine Art zu gehen, zu überprüfen, erreichte ich diesen Ort.
Es gab ein Wort, das hier endet in der Datenstruktur.
>> Also, was ein Trie ist wirklich mit gefüllt und der Autor wählte zu vertreten
diese Endhaltestellen mit kleinen Dreiecke.
Dies bedeutet nur, dass die Tatsache, dieses Dreieck ist hier, diese boolesche Wert true
bedeutet, wenn Sie rückwärts in den Baum gehen,
das heißt, ein Wort benannt Maxwell ist in diesem.
Aber das Wort foo beispielsweise
nicht in den Baum, denn wenn ich starten am Wurzelknoten hier oben,
Es gibt keine f Zeiger, kein o Zeiger, kein o Zeiger. Foo ist nicht ein Name in diesem Wörterbuch.
Aber im Gegensatz dazu entwickelt, durch t-u-r-i-n-g. Auch habe ich nicht speichern t oder u oder r oder i oder n oder g.
Aber ich habe store in dieser Datenstruktur ein Wert von wahren Weg hier unten in diesem Knoten - im Baum
indem Sie diesen booleschen Wert is_word auf true.
So ein Trie ist eine Art dieser sehr interessanten Meta-Struktur,
wo du nicht wirklich die Speicherung der Worte selbst für diese Art von Wörterbuch.
Um es klar, du bist nur die Speicherung ja oder nein, es ist ein Wort, das hier endet.
>> Nun, was ist die Implikation?
Wenn Sie 150.000 Wörter in einem Wörterbuch, dass Sie versuchen, zu speichern
mit so etwas wie einer verketteten Liste,
Sie gehen zu 150.000 Knoten in Ihrer verketteten Liste haben.
Und die Suche nach einem dieser Wörter alphabetisch könnte O (n) Zeit.
Lineare Zeit. Aber in dem Fall des hier einem Trie
Was ist die Laufzeit der Suche nach einem Wort?
Es stellt sich heraus, die Schönheit hier ist, dass selbst wenn Sie 149.999 Wörter in diesem Wörterbuch,
wie mit dieser Datenstruktur implementiert,
Wie viel Zeit braucht es, um zu finden oder legen Sie eine weitere Person in das, wie Alice, Alice?
Nun, es ist nur 5, vielleicht 6 Schritte für den nachlaufenden Charakter.
Da die presense von anderen Namen in der Struktur
nicht in der Weise des Einsetzens Alice erhalten.
Darüber hinaus finden Alice einmal gibt es 150.000 Wörter in diesem Wörterbuch
nicht in den Weg zu finden, Alice überhaupt zu bekommen,
weil Alice ist. . . . . hier, weil ich fand einen boolean Wert.
Und wenn es keine boolesche wahr ist, dann Alice nicht in dieser Datenstruktur von Wörtern.
Mit anderen Worten, die Laufzeit des Findens Dinge und Einsetzen in diese neue Dinge
Datenstruktur Trie ist O - es ist nicht n.
Da die presense 150.000 Menschen hat keinen Einfluss auf Alice, wie es scheint.
So nennen wir es k, wo k ist die maximale Länge eines Wortes in Englisch
der typischerweise nicht mehr als 20-etwas Zeichen.
So k eine Konstante ist. So der Heilige Gral scheinen wir jetzt gefunden haben,
ist, dass von einem Trie konstante Zeit für Einsätze, für Lookups, für Deletionen.
Da die Anzahl der Dinge bereits in der Struktur,
das sind nicht einmal physisch anwesend. Auch sie einfach irgendwie abgehakt, ja oder nein,
hat keine Auswirkungen auf die künftige Laufzeit.
>> Aber es muss doch einen Haken, sonst wären wir nicht so viel Zeit verschwendet haben
auf all diesen anderen Datenstrukturen, nur um endlich das Geheimnis ein, die erstaunlich bekommen.
Also, was Preis zahlen wir diese Größe hier erreichen? Space.
Das Ding ist riesig. Und der Grund, dass der Autor
nicht präsentieren hier bemerken, dass all diese Dinge, die wie Arrays aussehen,
Er zog nicht den Rest des Baumes, der Rest der Trie
weil sie einfach nicht relevant für die Geschichte.
Aber alle diese Knoten sind super breit, und jeder Knoten im Baum nimmt
26 oder tatsächlich, könnte 27 Zeichen lang sein, da in diesem Fall war ich auch Platz für den Apostroph
so konnten wir haben apostrophierten Worte.
In diesem Fall sind dies breite Arrays. Also auch wenn sie nicht picutured,
Diese nimmt eine enorme Menge an RAM.
Welche könnte in Ordnung sein, especilly in moderner Hardware
aber das ist der Kompromiss. Wir bekommen weniger Zeit verbringen mehr Platz.
Also, wo ist das alles hin?
Nun, lass es uns tun - lasst uns hier zu sehen.
Lassen Sie uns einen Sprung zu diesem Kerl hier.
>> Ob Sie es glauben oder nicht, so viel Spaß wie C seit einiger Zeit jetzt gewesen,
wir den Punkt erreicht, in dem Semester, in denen es an der Zeit für den Übergang zu Dinge mehr modern.
Dinge, auf einer höheren Ebene. Und obwohl für die nächsten paar Wochen
wir noch weiter, um uns in der Welt der Zeiger und Speicher-Management eintauchen
, dass Trost, mit dem wir dann auf zu bauen bekommen,
das Endspiel ist letztlich einzuführen, ironischerweise nicht diese Sprache.
Wir verbringen, wie 10 Minuten reden HTML.
Alle HTML ist eine Markup-Sprache, und was für eine Markup-Sprache ist
ist diese Reihe von offenen Klammern und geschlossenen Klammern, 'machen diese bold' sagen
"Nehmen Sie diese kursiv 'machen diese zentriert."
Es ist gar nicht so intellektuell interessant, aber es ist super nützlich.
Und es ist sicherlich allgegenwärtig in diesen Tagen.
Aber was ist mächtig über die Welt der HTML und Web-Programmierung allgemein
baut dynamische Dinge; Schreiben von Code in Sprachen wie PHP oder Python oder Ruby oder Java oder C #.
Wirklich, was der Sprache Ihrer Wahl, und die Erzeugung von HTML dynamisch.
Generieren etwas namens CSS dynamisch.
Cascading Style Sheets, die auch um Ästhetik.
Und obwohl heute, wenn ich gehe zu einem gewissen Website wie die vertraute Google.com,
und ich gehe zu sehen, Entwickler, Quelltext, die Sie vielleicht zuvor getan,
sondern gehen für Quellenangaben, dieses Zeug wohl sieht ziemlich kryptisch.
Aber dies ist die zugrunde liegende Code, Google.com implementiert.
Auf dem vorderen Ende. Und tatsächlich all dies ist flauschig Ästhetik Zeug.
Dies ist CSS hier oben. Wenn ich nach unten scrollen zu halten bekommen wir einige farbige Sachen.
Dies ist HTML. Google-Code sieht aus wie ein Chaos, aber wenn ich tatsächlich eröffnen ein anderes Fenster,
können wir eine gewisse Struktur, das zu sehen.
Wenn ich diesen eröffnen, hier zu bemerken, ist es ein wenig besser lesbar.
Wir werden bald sehen diesen Tag, [word] ist ein Tag,
HTML, Kopf, Körper, div, Drehbuch, Textbereich, span, zentriert, div.
Und dies wird auch von kryptischen aussehende sortieren auf den ersten Blick
aber alle aus diesem Schlamassel folgt bestimmten Mustern und wiederholbare Muster,
so dass, wenn wir die Grundlagen runter, wirst du in der Lage sein, Code wie diesen schreiben
und dann manipulieren Code wie dies mit noch einer anderen Sprache, genannt JavaScript.
Und JavaScript ist eine Sprache, die in Auflagen von einem Browser
heute bekannt, dass wir auf Harvard Kursen, verwenden Sie für den Kurs Shopping-Tool, dass Google Maps verwendet
um Ihnen eine ganze Reihe von Dynamik, gibt Facebook Sie Instant Status-Updates zeigen,
Twitter nutzt es Ihnen zu zeigen, Tweets sofort.
All dies werden wir beginnen, uns eintauchen in.
Aber um dorthin zu gelangen, müssen wir ein bisschen etwas über das Internet zu verstehen.
Dieser Clip ist hier nur eine Minute lang, und nehmen wir an, jetzt dies ist in der Tat,
wie das Internet als Teaser für das, was zu kommen funktioniert. Gebe ich euch "Warriors of the Net".
>> [♫ Langsam Chormusik ♫]
[Männlich Erzähler] Er kam mit einer Botschaft.
Mit einem Protokoll alle seine eigenen.
[♫ Schnellere elektronische Musik ♫]
Er kam, um eine Welt der kühlen Firewalls, gefühllos Router,
und Gefahren weit schlimmer als der Tod.
Er ist schnell. Er ist stark. Er ist TCP / IP, und er hat Ihre Adresse.
Warriors of the Net.
[Malan] Nächste Woche dann. Das Internet ist. Web-Programmierung. Dies ist CS50.
[CS50.TV]