DAVID J. MALAN: In Ordnung. Also willkommen in der ersten CS50 Obduktion für ein Quiz. Wir dachten, wir würden einweihen diese Tradition in diesem Jahr. Und das wird eine Chance sein durch die gehen Lösungen zum Quiz. Und wir beschleunigen oder verlangsamen Basis auf Interesse derer hier. 

So sind Sie wahrscheinlich hier, weil Sie interessiert, wie könnten Sie haben oder sollten einige beantwortet haben dieser Probleme. Also, warum nicht wir einen Blick in diesem Abschnitt zuerst? So bekommen Saiten. Dies gab drei verschiedene Versionen eines Programms, war schließlich soll eine Zeichenfolge von einem Benutzer zu bekommen. Ob es tat, war links an Ihnen zu bestimmen. 

Und wir fragten in Frage 0, nehme an, dass die Version 1 ist kompiliert und ausgeführt. Warum könnte das Programm abstürzt? Auf den ersten Blick, irgendwelche Vorschläge , warum? Ja. 

ZIELGRUPPE: Also ich erinnere mich, diese in eine vorherige Beispiel der Blick auf die char * s und zu sehen, den Scan der s-und sehen, denn es ist ein Zeiger, wie hat es sich auf, was Sie in gescannt? Ist es s oder die Adresse von s? 

DAVID J. MALAN: OK. Gut. So sind letztlich die Quelle eines Problems vermutlich werde reduzieren auf diese Variable s. Und es ist in der Tat eine Variable. Der Datentyp dieser Variablen ist char *, was bedeutet, es wird enthalten die Adresse eines Zeichens. Und darin liegt die Einsicht. Es wird die Adresse enthalten ein Zeichen oder, allgemeiner, die Adresse des ersten Zeichens in ein ganzer Block von Zeichen. 

Aber der Haken ist, dass Scan-s, Zweck in Leben, eine Adresse gegeben und gegeben ein Format-Code, wie% s lesen eine Zeichenfolge in das Stück Speicher an dieser Adresse. Aber weil es keine Gleichheitszeichen vor Semikolon, dass auf der ersten Code-Zeile, weil wir nicht wirklich zuteilen beliebigen Speicher mit malloc, denn es kam nicht wirklich zuteilen ein Array mit einer gewissen Größe, die alle Sie tun, ist das Lesen der Benutzer- Tastatureingaben in eine komplette Müll-Wert, der ist in s standardmäßig. Also Chancen sind Sie gehen zu abstürzt, sind, wenn dass Adresse nicht einfach so passieren ein Wert, der du sein kannst, in der Tat, zu schreiben. So schlecht, nicht zu vergeben Ihr Gedächtnis gibt. 

So in Frage 1, fragten wir, nehme an, dass die Version 2 ist kompiliert und ausgeführt. Warum könnte das Programm abstürzt? Also dieses ist weniger fehlerbehaftet. Und es gibt wirklich nur eine offensichtliche Weise, wo man auslösen segfault hier. Und das ist thematisch. Jedes Mal, wenn wir mit c in Erinnerung, was könnten Sie tun, um einen Speicherzugriffsfehler herbei Version 2? 

ZIELGRUPPE: Wenn Sie diese Eingabe in verwenden ein String, der länger als 49 ist Zeichen. 

DAVID J. MALAN: Genau. Jedes Mal, wenn Sie etwas fester Länge sehen wenn es um eine Anordnung kommt, Ihre Radar sollte gehen, dass dies sein problematisch, wenn Sie nicht die Überprüfung sind die Grenzen eines Arrays. Und das ist das Problem hier. Wir sind immer noch mit scanf. Wir sind immer noch mit% s, was bedeutet, versuchen um eine Zeichenfolge vom Benutzer gelesen. Das wird in s gelesen werden, die, An diesem Punkt ist effektiv die Adresse eines Teil des Speichers oder dessen Äquivalent. Es ist der Name eines Arrays der Zeichen-Speicher. 

Aber genau das, wenn Sie einen String lesen das ist länger als 49 Zeichen, 49 weil man Platz für den umgekehrten Schrägstrich müssen 0, wirst du zum Überlaufen dass Puffer. Und Sie vielleicht Glück haben und in der Lage, einen 51. Charakter, 52., 53.. Aber irgendwann, das Betriebssystem wird sagen, nein. Dies ist definitiv nicht Speicher dürfen Sie zu berühren. Und das Programm wird sich abstürzt. 

Also gibt, sollten die Heuristik beliebig sein Zeit, die Sie feste Länge haben, müssen Sie um sicherzustellen, dass Sie die Überprüfung der Länge von was auch immer es ist, Sie versuchen, in sie zu lesen. 

ZIELGRUPPE: Also zu lösen, könnten Sie eine Erklärung Überprüfung tatsächlich gehabt haben ist die Länge größer oder kleiner als? 

DAVID J. MALAN: Unbedingt. Sie müssen nur eine Bedingung , die sagt, wenn die - oder vielmehr muss man nicht unbedingt wissen im Voraus, wie viele Zeichen der Benutzer wird sich geben, weil Sie haben Huhn und das Ei. Nicht, bis Sie es mit scanf gelesen habe können Sie herausfinden, wie lang es ist. Aber an diesem Punkt, ist es zu spät, weil Sie bereits in lesen einige Speicherblock. So nebenbei, die CS50-Bibliothek vermeidet diese Frage überhaupt, Rückruf durch die Verwendung fgetc. Und es liest ein Zeichen in einer Zeit, Zehenspitzen zusammen, wohl wissend, dass Sie können ein Zeichen, wenn nicht überlaufen Sie lesen ein zu einer Zeit. 

Der Haken ist mit getstring Rückruf dass wir uns immer wieder neu Größe dass Teil des Speichers, die ist nur ein Schmerz. Es ist eine Menge von Zeilen Code, um das zu tun. So wäre ein weiterer Ansatz sein tatsächlich eine Cousine, so zu sprechen, von scanf. Es gibt Varianten einer Menge von diesen Funktionen, die tatsächlich überprüfen Länge, wie viele Zeichen Sie können maximal lesen. Und man konnte angeben, nicht lesen mehr als 50 Zeichen. Damit wäre ein weiterer Ansatz sein, aber weniger entgegen von größeren Eingängen. 

Also Frage 2 fragt, nehme diese Version 3 kompiliert und ausgeführt. Woran kann das Programm abstürzt? Also das ist eigentlich das gleiche beantworten, obwohl es sieht ein wenig schicker. Wir verwenden malloc, die wie fühlt sich wir geben uns mehr Möglichkeiten. Und dann sind wir zu befreien, dass Speicher am Ende. Es ist immer noch nur 50 Byte Speicherplatz. So könnten wir immer noch versuchen zu lesen in 51, 52, 1000 Bytes. Es wird für abstürzt genau dem gleichen Grund. 

Aber es ist ein weiterer Grund. Was sonst könnte Rück neben malloc die Adresse eines Speicherstück? Es könnte null zurück. Und weil wir nicht für die Überprüfung dass wir vielleicht etwas tun dumm aus einem anderen Grund, der ist, dass wir könnten sagen, scanf, lesen die Benutzereingabe von der Tastatur 0 in Lage, AKA null. Und das auch, wird auf jeden Fall Auslöser einer Schutzverletzung. Also für den Zweck des Quiz ist, würden wir entweder von denen als angenommen triftigen Grund. Einer ist identisch. Man ist ein wenig differenzierter. 

Schließlich, in Bezug auf die Programm Speichernutzung, wie die Version 2 zu tun und Version 3 unterscheiden? Also für das, was es wert ist, sahen wir einen scheinbar endlosen Vorrat an möglichen Antworten. Und unter den Antworten der Menschen, was wir waren hoffen, aber wir anderen akzeptiert Dinge, war eine Erwähnung der Tatsache, dass die Version 2 wird mit die sogenannten Stack. Version 3 wird mit dem Heap. Und funktionell, tut dies nicht wirklich machen, dass alle viel von einem Unterschied. Am Ende des Tages sind wir immer noch nur immer 50 Byte Speicherplatz. 

Aber das war eine der möglichen Antworten dass wir auf der Suche. Aber Sie werden sehen, wie Sie Ihre Quiz bekommen zurück von der TF, dass wir das gemacht haben anderen Diskussionen akzeptieren ihre unterschiedlichen Verwendungen von Speicher auch. Aber Stack und Heap gewesen wäre eine einfache Antwort mit zu gehen. Haben Sie Fragen? Ich gebe dir Rob. 

ROB BOWDEN: Also Problem 4. Dies ist die eine, wo Sie hatte zu füllen in der Anzahl der Bytes von allen Diese verschiedenen Arten verwendet. Also erste, was wir sehen. Angenommen, ein 32-Bit-Architektur, wie dieses Gerät CS50. Also eine der grundlegenden Dinge über 32-Bit-Architekturen, die uns sagt, dass genau, wie groß ein Zeiger geht in der Architektur. 

Also sofort, wir wissen, dass jede Zeiger Typ 32 Bits oder 4 Bytes. So suchen Sie in dieser Tabelle ein Knoten * ist ein Zeiger-Typ. Das wird 4 Bytes. Struct Knoten *, das ist buchstäblich identisch mit Knoten Stern. Und damit geht um 4 Bytes. String, so dass es nicht wie ein noch Zeiger, aber die typedef ein String ist nur ein char *, die ist ein Zeiger-Typ. Also das wird 4 Bytes. 

Also diese drei sind alle 4 Bytes. Jetzt, Knoten und Schüler sind ein wenig komplizierter. So suchen Sie in Knoten und Schüler, sehen wir Knoten nach einer ganzen Zahl und einem Zeiger. Und Schüler zwei Zeiger darin. So dass zumindest für unseren Fall hier der Weg dass wir am Ende der Berechnung der Größe der Diese Struktur ist nur hinzufügen, bis alles das ist in der Struktur. 

Also für Knoten, haben wir eine ganze Zahl, das ist 4 Bytes. Wir haben einen Zeiger, der 4 Bytes ist. Und so ein Knoten wird zu nehmen 8 Byte. Und ebenso für Studenten, haben wir ein Zeiger, der 4 Byte und ein anderer ist Zeiger, der 4 Bytes ist. Also das geht zu Ende Sein bis 8 Byte. So Knoten und Schüler sind 8 Byte. Und diese drei sind alle 4 Bytes. Fragen dazu? Ja. 

ZIELGRUPPE: Ist es ein 64-Bit- Architektur, würde das verdoppeln alle? 

ROB BOWDEN: Es würde nicht verdoppeln alle. Also 64-Bit-Architektur, sie, wieder, Veränderungen, die grundlegende Sache, dass ein Zeiger ist jetzt 64 Bit. Ja. So ist ein Zeiger 8 Byte. Also diese, die 4 Bytes waren gehen, um 8 Bytes sein. Ein Student, der zwei Zeiger war, Nun, jetzt es geht um werden 8 Byte, 8 Byte. Es wird zu 16 Byte zu machen. 

Aber ein Knoten noch 4 Bytes. So wird dieser Zeiger 8 Byte. Das ist 4 Bytes. So ein Knoten ist nur noch 12 Bytes. Alle anderen Fragen auf, dass man? Also das nächste, das sind die HTTP-Statuscodes. Und Sie nach Umständen zu beschreiben, hatte unter denen diese Macht an Sie zurückgegeben werden. ein Problem, das ich hörte einige Studenten ist, dass sie versuchte, die Fehler auf Ende des Auftraggebers. Also, wenn wir versuchen, den Antrag zu stellen an den Server, geht etwas falsch an unserem Ende. Aber im allgemeinen sind diese Codes , die vom Server zurückgegeben. Also, um herauszufinden, was los ist wollen wir falsch oder richtig auf dem Server, bewirkt, dass diese Dinge zurückgegeben werden. Warum könnte ein Server zurück Statuscode 200? Irgendwelche Gedanken? 

Ja. So etwas erfolgreich der Antrag ging durch. Und sie sind in der Lage, zurück was auch immer Sie fragte nach. So war alles in Ordnung. Was etwa 302 gefunden? Ja. 

ZIELGRUPPE: Der Server war auf der Suche für das, was Sie angefordert haben. Aber es konnte ihn nicht finden. Es gibt also ein Fehler. 

ROB BOWDEN: So war der Server suchen, was Sie wollten. Also einfach hier suchen, 302 gefunden, es war in der Lage, es zu finden. 

ZIELGRUPPE: Tut mir leid. Gefunden bedeutet, dass sie tat es. Entschuldigung. 

ROB BOWDEN: Also 302 gefunden. Der Server ist in der Lage zu finden was Sie wollten. 

ZIELGRUPPE: Aber es ist nicht angezeigt oder? 

ROB BOWDEN: Die Differenz zwischen Diese 302 und 200 ist, dass es weiß, was Sie wollen. Aber es ist nicht genau, wo Sie wollte fragen. Also 302 ist ein typisches Umleitung. So haben Sie eine Seite angefordert. Es weiß, oh, ich will um Ihnen diese zurück. Dies ist jedoch in einer anderen URL. Also hey, die Sie tatsächlich wollen, dass diese. 

DAVID J. MALAN: Es ist ein Stück, das die gab, dass wir euch eine Umleitung Funktion, die die Kopffunktion verwendet daß wiederum ausgedruckt Lage, Doppelpunkt und dann die URL, auf die Sie den Benutzer zurückweisen möchten. Auch wenn Sie nicht sehen, 302 es ausdrücklich, dass das, was PHP würde magisch als Header einfügen sagen, genau das, was Rob sagte, dass es - gefunden. Aber hier gehen statt. 

ROB BOWDEN: OK. So was über 403 verboten? 

ZIELGRUPPE: Ich denke, es ist, dass der Server ist im Grunde sagen, dass der Client kann nicht auf die Startseite. 

ROB BOWDEN: Also ja. Nun, wir waren die typische Antwort erwarten ist so etwas wie die Dateien nicht angemessen chmodded. Das ist wahrscheinlich, unter welchen Umständen Sie sah. Aber es gibt einen Grund dafür, dass der Client Schuld könnte hier sein. Es gibt tatsächlich ein weiteres Status-Code - 401. Das sind also sehr ähnlich. 

401 ein. Und 403 ist untersagt. Und so unberechtigten Sie ausschließlich bekommen, wenn Sie nicht eingeloggt Aber der Anmeldung könnte bedeuten, dass Sie berechtigt sind. Aber wenn Sie bereits eingeloggt, und Sie noch nicht über die Berechtigung, dann können Sie auch verboten. Also, wenn Sie eingeloggt sind und müssen nicht Genehmigung ist auch verboten etwas, das man bekommen kann. 

DAVID J. MALAN: Und der Mechanismus, durch welche diese Probleme sind in der Regel gelöst, auf dem Server über welchen Befehl? Chmod, wenn es in der Tat ein Berechtigungen Ausgabe auf die Datei oder das Verzeichnis. 

ROB BOWDEN: Dann 404 nicht gefunden. Ja. Also im Gegensatz zu 302, wo es nicht genau wo Sie fragen, aber es weiß, was Sie wollen, nur hat es diese keine Ahnung, was Sie wollen. Und Sie anfordern, etwas gültig. 418 Ich bin eine Teekanne und dann 500 internen Server. Also, warum sollten Sie das her? 

So abstürzt - Ich eigentlich nicht wissen, die Einstufung Standard für diese. Aber wenn Ihre PHP-Code hatte etwas falsch daran, in der Theorie, könnte es tatsächlich abstürzt, in welchem ​​Fall diese 500 Internal Server Error, etwas, ist falsch mit Ihrem Server des Konfiguration. Oder gibt es eine Syntax-Fehler in der PHP-Code. Oder etwas Schlimmes vor sich geht. 

DAVID J. MALAN: Wir haben sehen segfault unter die Antworten ein paar Leute. Und technisch könnte es passieren. Aber das wäre ein PHP, das Programm sein geschrieben von anderen Menschen, eigentlich segfaulted, die nur, wenn diese Personen oben geschraubt und schrieb fehlerhaften Code in ihre Dolmetscher würde PHP selbst abstürzt. Also auch wenn 500 ist wie eine Schutzverletzung im Geiste, ist es fast immer der Ergebnis einer Konfigurationsdatei Ausgabe mit Ihrem Web-Server oder, wie Rob sagte, Syntaxfehler, wie Sie hat ein Angebot nicht zu schließen. Oder Sie ein Semikolon irgendwo verloren. 

ZIELGRUPPE: Also für den Shuttle pset, ich denken, wenn ich es tat, wenn ich das angeklickt Browser, aber nichts kam, was sie weiße Seite aufgerufen. Aber es war wegen der Codes. Ich glaube, das war kein JavaScript, oder? 

ROB BOWDEN: Ja. 

ZIELGRUPPE: Würde das Fehler noch kommen? 

ROB BOWDEN: Also würden Sie nicht bekommen haben dieser Fehler, weil alles aus Sicht der Web-Server war völlig in Ordnung. Aber Sie angefordert index.html. Sie beantragt shuttle.js und service.js. Und es war in der Lage, erfolgreich zurück an euch alle diese Dinge - 200. OK. Es ist nur, wenn Ihr Browser versucht, interpretieren den JavaScript-Code, es ist wie, warten, ist dies nicht gültigen JavaScript-Fehler. Noch Fragen? Gut. 

DAVID J. MALAN: Also das nächste Sie war die Nummer 11. Und 11 war der schrecklichste für eine Menge Leute. So ist die wichtigste Sache, hier zu beachten war, dass dies in der Tat zu ein doppelt verketteten Liste. Aber das war nicht das gleiche wie im letzten Jahr doppelt verknüpfte Liste Problem, die nicht geben, haben Sie den Vorbehalt, dass die Liste könnte in der Tat sein, unsortiert. 

Also die Tatsache, dass die Liste war unsortiert und die Tatsache, dass das Wort war unterstrichen es bedeutet wurde, um zu vermitteln dass dies tatsächlich eine Vereinfachung von dem, was sonst gewesen wäre, eine größere Herausforderung Problem und eine längere. So war ein häufiger Fehler, hier zu setzen haben im vergangenen Jahr die Lösung auf ein Pager und dann einfach blind zu kopieren, dass sich wie die Antwort, die die richtige ist Antwort auf eine andere Frage im Geiste. Aber die Feinheiten hier waren wie folgt. 

So eine haben wir ein Knoten deklariert und in üblicher Weise definiert. Dann definiert man eine Liste der global sein Zeiger mit null initialisiert. Dann anscheinend gibt es zwei Funktionen wir haben Prototypen für hier, einfügen und zu entfernen. Und dann haben wir hier einige Beispiel-Code zu tun, ein paar von Insertionen. Und dann bitten wir Sie, vervollständigen die Umsetzung des Einsatzes unten dergestalt eine Möglichkeit, dass es in die Liste eingefügt n in konstanter Zeit, unterstrich auch, auch wenn bereits vorhanden ist. 

So ist die Schönheit des Seins in der Lage, einfügen in konstanten Zeit ist, dass es bedeutet, dass Sie einfügen müssen der neue Knoten, wo? In der Front. So ist es eliminiert, Gott sei Dank, wenigstens einer der Fälle, die erfordern noch mehr Zeilen Code, wie damals, im letzten Jahr und auch in der Klasse, wenn wir durch diese Art der Sache gesprochen mit Menschen und mit einigen verbale Pseudo-Code. Also in der Lösung hier, mal überspringen zu, dass, nur um eine visuelle auf haben der Bildschirm. 

Beachten Sie, dass wir tun, die folgenden. Und auch feststellen, das andere Vereinfachung war, dass auch wenn es bereits vorhanden ist, so bedeutet dies, auch wenn die Zahl ist schon da, du kannst einfach blind ein anderes einfügen Kopie. Und das auch, sollte ein sein Vereinfachung, so dass Sie könnte konzentrieren, wirklich, einige der mehr intellektuell interessante Teil und nicht nur einige zusätzliche Fehlerprüfung Angesichts der begrenzten Zeit. 

Also in diesem Probenlösung, weisen wir einen Zeiger auf die linke Seite hier zu einem Knoten. Jetzt merke, dass die Zeiger, so Rob sagte, ist nur 32 Bit. Und es muss nicht tatsächlich enthalten eine Adresse, bis Sie weisen Sie die Adresse. Und das tun wir auf der rechten Seite über malloc. Wie ein guter Bürger, überprüfen wir, dass malloc nicht tatsächlich null, so dass wir nicht versehentlich zu erstellen ein segfault hier. Und jedes Mal, wenn Sie malloc im Leben verwenden, sollte die Überprüfung werden für null, damit Sie haben einen subtilen Bug. 

Dann initialisieren wir, dass von null Zuweisen von n und vorherigen und nächsten. Und in diesem Fall hier, I initialisiert vorherige Null ist, weil diese neue Knoten wird der neue sein Anfang meiner Liste. Also es geht um sein nichts vor ihr. Und ich möchte die wesentlichen anhängen vorhandene Liste auf den neuen Knoten durch Einstellung neben sich selbst gleich auflisten. Aber ich bin nicht nur noch nicht fertig. Also, wenn die Liste selbst bereits existierte, und es mindestens einen Knoten bereits vorhanden, wenn dies die Liste hier und ich setzen Sie einen neuen Knoten hier, ich müssen sicherstellen, dass meine ehemaligen Knoten weist nach hinten, um meine neuen Knoten, denn dies ist wiederum ein doppelt verketteten Liste. 

Also machen wir eine Plausibilitätsprüfung. Wenn Liste ist nicht null, wenn es bereits einen oder mehrere Knoten gibt, dann hinzufügen, dass Rückbezug sozusagen. Und dann das letzte, was wir brauchen zu tun, ist eigentlich die globale aktualisieren Variablenliste selbst zu Punkt zu diesem neuen Knoten. Ja. 

ZUSCHAUER: In der Mauspfeil [Unverständlich] gleich null ist, geht das befassen sich mit der Liste, weil die Liste ist null? 

DAVID J. MALAN: Nö. Das ist einfach, mich als pro-aktiv Vorsicht, dass, wenn das ist mein ursprünglichen Liste mit vielleicht einigen mehr Knoten hier und ich meine Einsetzen neuen Knoten hier, es geht nichts mehr hier zu sein. Und ich möchte, dass die Idee zu erfassen indem Sie den vorherigen null auf dem neuen Knoten. Und vermutlich, wenn mein Code korrekt ist und es gibt keinen anderen Weg zu legen außer dieser Funktionsknoten, vermutlich bereits, auch wenn Liste einen oder mehrere Knoten in der es vermutlich die Liste der erste Knoten haben würde vorherige Zeiger von null sich. 

ZIELGRUPPE: Und nur ein Follow-up. Der Grund, warum Sie setzen Zeiger neben Gleichen Liste wird Sie machen den Zeiger sind Liste vor, dass es zeigen auf die nächste, ich denke - Ich tun nicht - nur nennt? 

DAVID J. MALAN: Genau. Und so wollen wir zwei Fällen tatsächlich der Ansicht hier wirklich, auch wenn die Bestellung werden wir sie prüfen, ist nicht ziemlich der gleiche wie der Code. Sondern auf einem hohen Niveau, wenn diese für Liste, und dies ist ein 32-Bit- Zeiger, ist die einfachste Szenario dass dies standardmäßig Null. Und angenommen, ich möchte die einfügen Nummer 50 war die erste Nummer. Also werde ich weitermachen und zuweisen ein Knoten, die gehen zu enthalten drei Felder - n, vorherigen und nächsten. 

Ich werde die Nummer 50 gesetzt hier, da dies n sein. Das wird der nächste sein. Und dies wird sein vorheriges. Und so was kann ich in diesem Fall tun? Nun, ich habe gerade Linie 1 hier. Pointer n n bekommt. Ich bin dann zu sagen, frühere bekommen sollte null. Es wird also null sein. Dann werde ich als nächstes sagen wird, um die Liste zu bekommen. 

Und das funktioniert nur gut aus. Dies ist null. Und so sage ich, der neue Knoten der nächsten Feld sollte bekommen, was das ist. Damit setzt ein weiteres null da. Und dann das letzte, was Ich habe hier überprüfen. Wenn Liste ist nicht gleich null, aber es ist gleich null, so dass wir überspringen insgesamt. Und so alles, was ich als nächstes tun ist Liste bekommt Zeiger, der bildhaft führt ein Bild so. Also das ist ein Szenario. 

Und die eine, die Sie wurden zu fragen Insbesondere ist eine Situation wie dieser, wo wir bereits eine Ein-Knoten-Liste. Und wenn ich wieder in der ursprünglichen Problemstellung, der nächste wir werden legen sagen wir 34 ist, nur für die um der Diskussion willen. Also werde ich einfach nur bequem hinweisen, dass hier. Ich habe gerade malloced. Nehmen wir an, ich bin Überprüfung auf null. 

Nun, ich werde zu initialisieren n 34 ist. Und dies wird n sein. Das wird der nächste sein. Und dies wird sein vorheriges. Lassen Sie uns sicherstellen, dass ich nicht erhalten diese nach hinten. Zurück kommt zuerst in der Definition. Lassen Sie mich dies zu beheben. Dies ist vorherige. Dies ist der nächste. Auch wenn diese identisch sind, wir halten es konsistent. 

Vorherige. Dies ist der nächste. Also ich habe gerade malloced meine Anmerkung, geprüft für null zugeordnet, 34 in den Knoten. Zurück bekommt null. Also das gibt mir, dass. Weiter erhält Liste. So ist diese Liste. Also das ist jetzt die gleiche wie diese Zeichnung Pfeil, so daß sie auf einen Punkt in der gleichen. Und dann werde ich prüfen, ob Liste nicht gleich null. Und es ist diesmal nicht. Dann werde ich um Liste zu tun vorherige bekommt Zeiger. 

So Liste previous bekommt PTR. So hat dies die Wirkung der Umsetzung eine grafische Pfeil hier. Und das ist immer ein wenig gewellt, die Linien. Und dann, endlich, ich aktualisieren Liste zu Punkt auf Zeiger. So, jetzt deutet dies auf diesem Kerl. Und jetzt machen wir einen schnellen Plausibilitätsprüfung. 

Hier ist die Liste, das ist, die globale Variable. Der erste Knoten ist in der Tat 34, weil Ich bin nach dieser Pfeil. Und das ist richtig, weil ich Einsatz am Anfang der Liste Alle neuen Knoten. Seine nächste Feld führt mich zu diesem Kerl. Wenn ich weitermachen, schlug ich nächste ist null. Also gibt es keine Liste mehr. Wenn ich auf früheren, bekomme ich zurück, wo ich erwarte. 

So gibt es immer noch ein paar Hinweise, offensichtlich zu manipulieren. Aber die Tatsache, dass man Ihnen sagte, zu tun dies in konstanter Zeit bedeutet, dass Sie nur eine endliche Anzahl von Dingen dürfen Sie zu tun. Und was ist diese Zahl? Es könnte ein Schritt sein. Es könnte zwei sein. Es könnte 1000 Stufen. Aber es ist endlich, das heißt, Sie können nicht haben jede Art von looping los hier, keine Rekursion, keine Schleifen. Es ist gerade zu hart codierte Linien Code, wie wir in diesem Beispiel. 

Also das nächste Problem 12 hat uns gebeten, runden die Implementierung von remove unten in der Weise, dass es entfernt n aus der Liste in linearer Zeit. So haben Sie ein wenig mehr haben Spielraum jetzt. Sie können davon ausgehen, dass n, falls vorhanden in der Liste, wird anwesend sein nicht mehr als einmal. Und das auch sein soll ein Quiz-basierten vereinfachenden Annahme, so dass, wenn Sie die Zahl 50 irgendwo zu finden in der Liste, können Sie nicht auch tun haben, um über weiter Sorgen laufen, auf der Suche nach allen möglichen Kopie von 50, die gerade übertragen würde in eine Einzelheit in begrenzter Zeit. 

Also mit entfernen, auf jeden Fall war dies eine anspruchsvoller und mehr Code zu schreiben. Aber auf den ersten Blick, ehrlich gesagt, könnte es Blick überwältigend und wie etwas es gibt keine Möglichkeit, Sie haben könnten kommen mit einem Quiz auf. Aber wenn wir uns auf die einzelnen Schritte, Hoffentlich wird es plötzlich schlagen Sie, dass jede dieser einzelnen Schritte macht offensichtlich Sinn im Rückblick. Werfen wir also einen Blick. 

Also zuerst initialisieren wir Zeiger Liste zu sein sich. Weil ich will, die lineare Zeit, dass Mittel Ich werde einige Schleife haben. Und ein üblicher Weg, um über die laufen Knoten in einer Listenstruktur oder jede Art der Struktur iterativ zu nehmen ein Zeiger auf der Vorderseite des Daten Struktur und dann starten Sie einfach die Aktualisierung es und gehen Sie Ihren Weg durch die Datenstruktur. Also werde ich genau das tun. 

Während Zeiger, meine temporäre Variable, nicht gleich null, lassen gehen Sie vor und überprüfen. Habe ich Glück? Ist das Feld in der n Knoten Ich bin derzeit suchen gleich der Zahl ich suche? Und wenn ja, wollen wir etwas tun. Nun merkt das, wenn die Bedingung umgibt die gesamte folgende Zeilen Code. Das ist das einzige, was mich interessiert - Finden einer Zahl in Frage. Also gibt es keine andere, die vereinfacht Dinge konzeptionell ein wenig. 

Aber jetzt wurde mir klar, und haben Sie vielleicht nur erkannte dies nach dem Denken es durch ein Bit, gibt es eigentlich zwei Fälle hier. Einer ist, wo der Knoten bei der Anfang der Liste, die eine ist wenig ärgerlich, denn das ist eine Sonderfall, weil Sie zu tun haben mit diesem Ding, was Nur Anomalie. Überall sonst in der Liste, es ist die gleiche Sache. Es gibt einen vorherigen Knoten und eine nächste Knoten vorherigen Knoten, nächsten Knoten. Aber dieser Kerl ist ein kleines Special wenn er am Anfang. 

Also, wenn der Zeiger entspricht der Liste selbst, so dass, wenn ich am Anfang des die Liste und ich habe n gefunden, ich brauche , um ein paar Dinge zu tun. Man, ich brauche, um die Liste zu ändern weisen auf das nächste Feld, 50. So nehme an, dass ich versuche 34 zu entfernen. Also dieser Kerl muss gehen weg in nur einem Augenblick. 

, Liste, so werde ich sagen, wird nächste Zeiger. Nun, das ist Zeiger. Weiter zeigt sich hier. Also das ändert sich dieses Pfeil rechts jetzt um auf diesem Kerl hier zeigen. Nun, denkt daran, wir haben eine temporäre Variable ist. So haben wir nicht alle verwaisten Knoten, weil ich auch diesen Kerl in meinem Implementierung von remove. So jetzt, wenn Liste selbst nicht null ist, Ich muss ein wenig etwas zu beheben. 

Ich muss jetzt dafür sorgen, dass dieser Pfeil, die zuvor zeigen wird 50 bis 34, hat das alles weg, weil, wenn ich versuche, loszuwerden von 34, 50 besser nicht halten jede Art von Rückverweis, um es als das Pfeil vorgeschlagen. Also habe ich nur diese Zeile. Also dann bin ich fertig. Dieser Fall ist eigentlich recht einfach. Hacken Sie den Kopf der Liste ist relativ einfach. 

Leider gibt es diese ärgerlich else-Block. So, jetzt habe ich den Fall zu prüfen, wo gibt es etwas in der Mitte. Aber es ist nicht zu schrecklich, außer Syntax wie diese. Also, wenn ich nicht am Anfang der Liste, ich bin irgendwo in der Mitte. Und diese Linie hier ist zu sagen, Start Zu welcher Knoten, den Sie gerade sind. Zum nächsten Feld des vorherigen Knotens und zeigen, dass am Zeiger. 

Wir tun dies bildhaft. Das wurde immer komplizierter. Also, wenn ich eine frühere Felder hier - wir tun dies - neben Felder hier. Ich werde meine Zeiger eher vereinfachen als ziehe eine ganze Reihe von Dinge hin und her, kreuz und quer einander. Und nun lassen Sie uns einfach sagen, das ist 1, 2, 3 zum Zwecke der Diskussion, auch obwohl das nicht eine Linie mit das Problem in Frage. 

Also hier ist meine verketteten Liste. Ich versuche, zwei in diese zu entfernen bestimmte Version der Geschichte. Also ich habe Zeiger aktualisiert werden, um diesen Kerl zeigt. Das ist also PTR. Er hat hier zeigt. Dies ist die Liste, die vorhanden weltweit als zuvor. Und er zeigt hier, egal was. Und jetzt versuche ich, zwei zu entfernen. 

Also, wenn Zeiger wird hier zeigen, ich bin gehen, um zu folgen, offenbar, die vorherige Zeiger, die mich bei 1 setzt. Ich bin dann zu sagen, dass der nächste Feld, das bringt mich auf, dies zu Box hier, wird sich gleich Zeiger neben. Also, wenn dieser Zeiger ist diese nächste. Das bedeutet, dass diese Bedürfnisse Pfeil zu diesem Kerl zeigen. 

Also, was das Codezeile muss nur getan ist ein bisschen dafür. Und nun, das ist wie ein Blick Schritt in die richtige Richtung. Wir wollen im Wesentlichen bis 2 snip von der Mitte der 1 und 3. So macht es Sinn, dass wir wollen, Route diesen Zeiger um ihn herum. Also das nächste Zeile prüft, ob Zeiger nächste nicht null ist, gibt es jemand tatsächlich rechts von 2, das bedeutet, dass wir auch zu tun haben, ein wenig schnippeln hier. 

Also ich muss jetzt diesen Zeiger folgen und aktualisieren Sie die vorherigen Zeiger auf dieser Kerl, ein wenig von einer do Umgehung hier den Punkt hier. Und nun, das ist optisch schön. Es ist ein wenig chaotisch, dass es in Niemand zeigt auf die zwei nicht mehr. 2 nach links zeigt. Und 2 nach rechts zeigt. Aber er kann machen, was er will, weil er ist dabei, befreit zu werden. Und es spielt keine Rolle, was diese Werte nicht mehr. 

Was wichtig ist, dass die verbleibende Jungs sind über Routing und unter ihm jetzt. Und in der Tat ist das, was wir als nächstes tun. Wir geben Zeiger, der bedeutet, dass wir sagen, die Betriebssystem, sind Sie herzlich willkommen dies zurückfordern. Und dann endlich, wir zurückkehren. Else implizit, wenn wir noch nicht zurückgegeben, wir müssen weiter suchen. So entspricht Zeiger Zeiger neben nur bedeutet bewegen diesen Kerl hier. Bewegen Sie diesen Kerl hier. Bewegen Sie diesen Kerl hier, wenn in der Tat, wir haben die Nummer nicht finden wir suchen noch auf der Suche. 

Also ehrlich gesagt, sieht es ganz überwältigend, denke ich, auf den ersten Blick, vor allem, wenn Sie kämpfte mit diesem während des Quiz dann sehen, so etwas. Und Sie selbst auf die Schulter klopfen. Nun, es gibt keinen Weg, ich hätte kommen mit, dass auf dem Quiz. Aber ich würde behaupten, Sie können, wenn Sie brechen es nach unten in diese einzelnen Fällen und nur zu Fuß durch sorgfältig, wenn auch, zugegeben, unter stressigen Umständen. 

Gott sei Dank, das Bild gemacht alles, was glücklicher. Sie könnten dies in zeichnen eine beliebige Anzahl von Möglichkeiten. Sie müssen nicht um die kreuz und quer zu tun Sache hier. Man könnte es mit gerade tun Zeilen wie diese. Aber der Kern des Problems, in Generell war zu erkennen, dass die Bild am Ende sollte ein wenig aussehen so etwas wie dies, weil konstante Zeit angedeutet, dass Sie zu halten Störungen und Störungen und Verklemmen der neue Knoten zu Beginn auf der Liste. Haben Sie Fragen? Die wohl größte Herausforderung sicherlich die Codierung Fragen. 

ZIELGRUPPE: Also ist die Liste ähnlich Kopf in den vorherigen Beispielen. 

DAVID J. MALAN: Genau, genau. Nur ein anderer Name für eine globale Variable. World wide was? 

ROB BOWDEN: OK. Das ist also die eine, wo man hatte, den Absatz zu schreiben. Einige Leute schrieb Essays für diese Frage. Aber Sie müssen nur diese sechs Begriffe verwenden um zu beschreiben, was passiert, wenn Sie versuchen, facebook.com kontaktieren. Also werde ich nur durch den Prozess sprechen mit all diesen Bedingungen. Also in unserem Browser, geben wir facebook.com und drücken Sie Enter. Also unsere Browser geht um ein Konstrukt HTTP verlangen, dass es sich auf senden durch einen Prozess zu Facebook für Auf Facebook, um uns mit der Antwort HTML seiner Seite. 

Also, was ist der Prozess, durch die der HTTP-Anforderung tatsächlich bekommt zu Facebook? Also zuerst müssen wir übersetzen Facebook.com. Also nur der Name Facebook.com gegeben, wo tatsächlich die HTTP-Anfrage gehen müssen? Also müssen wir übersetzen Facebook.com zu einer IP-Adresse, die eindeutig identifiziert, was wir eigentlich Maschine wollen, um diese Anforderung zu senden. Ihr Laptop verfügt über eine IP-Adresse. Alles, was mit dem Internet verbunden hat eine IP-Adresse. 

So DNS, Domain Name System, ist, dass was los ist, um die Übersetzung zu behandeln facebook.com aus einer IP-Adresse, die Sie wirklich wollen, zu kontaktieren. Also haben wir die DNS-Server zu kontaktieren und sagen wir, was ist facebook.com? Er sagt, oh, es ist die IP-Adresse 190,212 etwas, etwas, etwas. Gut. Jetzt weiß ich, welche Maschine Ich möchte zu kontaktieren. 

Also dann können Sie Ihre HTTP-Anfrage senden über dieser Maschine. Also, wie kommt es zu dieser Maschine? Nun, der Antrag geht von Router zu Router Prellen. Denken Sie daran, die beispielsweise in der Klasse, wo sahen wir tatsächlich die Route, die der Pakete nahm, als wir versuchten, zu kommunizieren. Wir sahen es über den Atlantik springen Ozean an einem Punkt oder was auch immer. 

Also der letzte Term-Port. Also das ist jetzt auf Ihrem Computer. Sie können mehrere Dinge haben derzeit die Kommunikation mit dem Internet. So kann ich laufen, sagen wir, Skype. Ich hätte einen Web-Browser geöffnet. Ich könnte so etwas haben, dass torren-Dateien. Also alle diese Dinge sind Kommunizieren mit dem Internet in irgendeiner Weise. 

Also, wenn Ihr Computer einige Daten erhält aus dem Internet, wie funktioniert es wissen, welche Anwendung tatsächlich will, dass die Daten? Woher weiß er, ob diese besondere Daten für die bedeutete, torren Anwendung im Gegensatz auf dem Web-Browser? Also das ist der Zweck der Häfen in das Alle diese Anwendungen haben behauptete einen Port auf Ihrem Computer. Also Ihr Web-Browser sagt, hey, Ich bin auf Port 1000 hört. Und Ihre torren Programm sagt, Ich bin auf Port 3000 hört. Und Skype sagt, ich bin mit Port 4000. 

Also, wenn Sie einige Daten zu bekommen, die gehört eine dieser Anwendungen, die Daten mit welchem ​​Port markiert es tatsächlich sollte zusammen gesendet werden. Also das sagt, oh, ich gehöre auf Port 1000. Ich weiß, dann muss ich diese weiterleiten entlang auf meiner Web-Browser. Also der Grund, es ist hier von Bedeutung ist, dass Web-Server sind in der Regel hören auf Port 80. Also, wenn ich Facebook.com kontaktieren, ich bin Kommunikation mit einigen Maschine. Aber ich muss sagen, welcher Anschluss, dass Maschine möchte ich mit zu kommunizieren. Und Web-Server sind in der Regel Port 80. 

Wenn sie wollten, könnten sie es eingestellt bis so listet es als auf Port 7000. Und dann in einem Web-Browser, konnte ich manuell eingeben Facebook.com: 7000 bis senden die Anfrage an Port 7000 der Facebook-Web-Server. 

DAVID J. MALAN: Und in diesem Fall, auch wenn wir nicht verlangen, dass die Menschen erwähne das, in diesem Fall, welchen Port würde der Antrag tatsächlich gehen? Versuchen Sie es erneut. Genau. Suchen Sie nicht nach, aber eine Subtilität das ist es keiner der Letzte. 

ROB BOWDEN: Also die HTTPS, da es hören, die speziell für die verschlüsselt, es ist auf Port 4430. 

ZIELGRUPPE: Und E-Mails sind 25, oder? 

DAVID J. MALAN: Outbound E-Mails, 25, yep. 

ROB BOWDEN: Ich weiß nicht einmal die meisten wissen die - all die unteren sind in der Regel für Dinge vorbehalten. Ich denke, alles unter 1024 ist reserviert. 

ZIELGRUPPE: Warum haben Sie sagen, 3 war die falsche Nummer? 

ROB BOWDEN: Weil in einer IP-Adresse, es gibt vier Gruppen von Ziffern. Und sie sind von 0 bis 255. So 192.168.2.1 ist eine gemeinsame lokalen Netz IP-Adresse. Beachten Sie, alle, die weniger als 255 sind. Also, wenn ich mit 300 gestartet wird, dass konnte nicht möglicherweise eine der Zahlen. 

DAVID J. MALAN: Aber das dumme Clip aus - war es CSI, wo sie ein Zahl, die zu groß war für die IP-Adresse. 

ROB BOWDEN: Sie haben Fragen dazu? Der nächste, so dass komplette Veränderung in Thema, aber wir haben diese PHP-Array für die Häuser in der Quad. Und wir haben eine ungeordnete Liste. Und wir jedes Listenelement ausdrucken möchten nur das Haus Namen enthält. So haben wir eine foreach-Schleife. Also denken Sie daran, die Syntax ist foreach Array als Element im Array. So durch jede Iteration der Schleife, Haus wird auf einem der nehmen Werte innerhalb des Arrays. 

Bei der ersten Iteration, Haus Cabot Haus sein wird. Auf einer zweiten Iteration Haus wird Courier sein Haus und so weiter. Also für jeden Quad als Haus, wir sind nur gehen, um zu drucken - Sie könnte auch hallte haben - das Listenelement und dann der Name des Hauses und schließen Sie dann das Listenelement. Die geschweiften Klammern sind hier optional. 

Und dann sagte, dass wir auch in der Frage selbst, denken Sie daran, schließen Sie die ungeordnete Liste-Tag. Also müssen wir PHP-Modus zu verlassen um dies zu tun. Oder wir haben hallte könnte die schließen ungeordnete Liste-Tag. 

DAVID J. MALAN: Auch gut hier würde gewesen, eine alte Schule für eine Nutzung Schleife mit einem $ i = 0 0 und zählt mit zu herauszufinden, die Länge des Strahlen. Völlig auch in Ordnung, nur etwas wortreicher. 

ZIELGRUPPE: Also, wenn Sie im Begriff waren, [Unverständlich], würden Sie tun - Ich vergesse, was die Schleife [unverständlich] ist. Würden Sie $ Quad Halterung i? 

DAVID J. MALAN: Genau. Ja, genau. 

ROB BOWDEN: Sonst noch was? 

DAVID J. MALAN: In Ordnung. Trade-offs. Es gab also Bündel von Antworten kann jeder von diesen. Wir waren eigentlich nur auf der Suche nach etwas Zwingendes für ein auf dem Kopf und eine Kehrseite. Und Nummer 16 fragte, Validierung Nutzer Eingangs Client-Seite, wie mit JavaScript anstelle der Server-Seite, wie mit PHP. Also, was ist ein auf dem Kopf von Dabei Client-Seite? 

Nun, das ist eines der Dinge, die wir vorgeschlagen dass Sie Wartezeit zu reduzieren, da Sie nicht zu stören, die in Kontakt Server, die einige Minuten dauern kann Millisekunden oder sogar ein paar Sekunden dass durch die Vermeidung und nur Validierung Nutzer zur Client-Seite durch Auslösung eines auf-submit Handler und nur die Kontrolle, haben sie geben etwas für Name? Haben sie etwas zu geben in für E-Mail-Adresse? Haben sie wählen Sie ein Studentenwohnheim aus das Dropdown-Menü? 

Sie können sie sofortiges Feedback geben mit der Gigahertz-Computer oder was auch immer sie haben, das ist tatsächlich auf ihrem Schreibtisch. So ist es nur eine bessere Benutzer erleben in der Regel. Aber eine Kehrseite des Tuns Client-Seite Validierung, wenn Sie es tun, auch ohne Dabei serverseitige Validierung ist, dass Äusserste, was man weiß, CS50 kommen dass man einfach alle Daten, die Sie wollen senden einem Server eine beliebige Anzahl von Möglichkeiten. Ehrlich gesagt, in fast jedem Browser, können Sie Klicken Sie um in die Einstellungen und nur JavaScript auszuschalten, das würde daher, deaktivieren Sie jede Form von Validierung. 

Aber Sie könnten auch daran erinnern, dass auch ich haben einige obskure Dinge in der Klasse mit telnet und eigentlich vorgibt, ein Browser durch Senden get Anforderungen an einen Server. Und das ist sicherlich nicht mit einem beliebigen JavaScript. Das ist nur mir der Eingabe von Befehlen an einer Tastatur. Also wirklich, jeder Programmierer innerhalb genug Komfort mit der Web-und HTTP könnten Daten senden, was er oder sie will zu einem Server ohne Validierung. Und wenn der Server nicht auch die Überprüfung, haben sie mir einen Namen zu geben, ist dies tatsächlich eine gültige E-Mail-Adresse, tat sie wählen, ein Wohnheim, könnten Sie am Ende bis Einfügen gefälschte oder einfach nur leere Daten in Ihre Datenbank, die wahrscheinlich wird nicht eine gute Sache sein, wenn Sie wurden unter der Annahme, es war da. 

Also das ist eine lästige Realität. Aber im allgemeinen clientseitige Validierung ist groß. Es bedeutet aber zweimal so viel Arbeit. Obwohl es existieren verschiedene Bibliotheken, JavaScript-Bibliotheken für Beispiel, die so viel zu machen, weniger Kopfschmerzen. Und Sie können einige der Code wiederverwenden Server-Side-, Client-Seite. Aber schon klar, dass es in der Regel zusätzliche Arbeit. Ja. 

ZIELGRUPPE: Also, wenn wir nur die weniger sicher - 

DAVID J. MALAN: [lacht] Ugh. Diese sind immer schwieriger diejenigen zu entscheiden. 

ROB BOWDEN: Das wäre angenommen. 

DAVID J. MALAN: Was? 

ROB BOWDEN: ich dieses Problem geschaffen. Das wäre akzeptiert worden. 

DAVID J. MALAN: Ja. 

ZIELGRUPPE: Kühle. 

ROB BOWDEN: Aber haben wir nicht akzeptieren für die erste - gut, das, was wir suchen, ist etwas, wie Sie nicht zu haben, Kommunikation mit dem Server. Wir haben nicht einfach akzeptieren schneller. 

PUBLIKUM: Was ist mit Sie Seite nicht neu laden? 

ROB BOWDEN: Ja. Das war eine akzeptierte Antwort. 

DAVID J. MALAN: Alles, wo wir fühlten uns es war eher als nicht wahrscheinlich dass Sie wussten, was Sie waren sagen, das ist eine schwierige Linie manchmal ziehen. Mit einer verketteten Liste statt einer Anordnung zur Aufrechterhaltung eines sortierte Liste von ganzen Zahlen. Also ein auf dem Kopf zitieren wir oft mit verknüpften Listen, die motiviert ihre ganze Einführung war man Dynamik bekommen. Sie können wachsen. Sie können schrumpfen. So müssen Sie nicht haben, um durch den Reifen springen mehr Speicher tatsächlich schaffen mit einem Array. Oder Sie müssen nicht nur sagen, sorry, Benutzer. Das Array gefüllt ist. So dynamische Wachstum der Liste. Ein Nachteil ist aber der verbundenen Listen? 

ZIELGRUPPE: Es ist linear. Die Suche auf verketteten Liste ist linear statt dessen, was Sie sich einloggen 

DAVID J. MALAN: Genau. Die Suche auf einer verketteten Liste ist linear, auch wenn es sortiert, da kann man nur folgendermaßen Semmelbrösel, diese Zeiger vom Beginn der Liste bis zum Ende. Sie können nicht nutzen, wahlfreien Zugriff und also binäre Suche, auch wenn es sortiert, dass man zu tun mit einem Array. Und es gibt auch eine andere Kosten. Ja. 

ZIELGRUPPE: Speicher ineffizient? 

DAVID J. MALAN: Ja. Nun, das würde ich nicht unbedingt sagen ineffizient. Aber es kostet Sie mehr Speicher, weil du 32 Bit für jeden Bedarf Knoten für den zusätzlichen Zeiger, um dest für eine einfach verkettete Liste. Nun, wenn Sie nur ganze Zahlen und Speicherung Sie hinzufügen den Zeiger sind, ist, dass tatsächlich Art von nicht-trivial. Es ist eine Verdoppelung der Menge an Speicher. Aber in Wirklichkeit, wenn Sie die Speicherung sind ein verkettete Liste von Strukturen, die haben könnte 8 Bytes, 16 Bytes, noch mehr als das, vielleicht ist es weniger eines Grenzkosten. Aber es ist eine Kosten dennoch. Also entweder von denen hätte war fein wie Nachteile. 

18. Mit PHP anstatt C zu schreiben ein Befehlszeilenprogramm. So, hier ist es oft schneller sich für eine Sprache wie PHP oder Ruby oder Python. Sie müssen nur schnell öffnen bis einem Texteditor. Sie haben viel mehr Funktionen zur Verfügung. PHP hat die Küchenspüle von Funktionen, wohingegen in C, Sie haben sehr, sehr wenig. In der Tat, die Jungs wissen, auf die harte Tour dass Sie nicht haben, Hash-Tabellen. Sie müssen nicht Listen verknüpft haben. Wenn Sie diejenigen wollen, müssen Sie setzen sie sich. 

So ein Kurspotenzial von PHP oder wirklich jede interpretierte Sprache ist die Schnelligkeit mit dem Sie Code schreiben. Aber ein Nachteil, sahen wir, als ich schnell eine Misspeller Schlag Umsetzung in der Vorlesung mit PHP, ist dass die Verwendung einer übersetzten Sprache ist in der Regel langsamer. Und wir sahen, dass nachweislich ein Erhöhung in der Zeit von 0,3 Sekunden bis 3 Sekunden wegen der Auslegung dass tatsächlich passiert. 

Ein weiterer Vorteil war, dass Sie nicht zu kompilieren. Also es beschleunigt auch die Entwicklung nebenbei bemerkt, weil Sie nicht haben, zwei Schritte, um ein Programm. Sie haben nur eine. Und so, das ist ziemlich überzeugende als auch. Mit einer SQL-Datenbank statt eine CSV-Datei, um Daten zu speichern. So SQL-Datenbank ist für pset7 verwendet. CSV-Dateien, die Sie nicht viel nutzen. Aber du hast es so verwendet, indirekt in pset7 auch durch Gespräche mit Yahoo Finance. 

Aber CSV ist wie eine Excel-Datei, sondern super einfach, in der die Spalten nur durch Komma abgegrenzt innen eines ansonsten Textdatei. Und mit einer SQL-Datenbank ein wenig mehr überzeugend. Es ist ein auf dem Kopf, weil Sie die Dinge wie auswählen und einfügen und löschen. Und Sie erhalten, vermutlich, Indizes, MySQL und andere Datenbanken, wie Oracle, bauen für Sie in Erinnerung, die bedeutet, dass Ihr wählen ist wahrscheinlich nicht werde linear von oben nach unten sein. Es ist eigentlich los, um etwas zu sein wie binäre Suche oder etwas im Geiste. So sind sie in der Regel schneller. 

Aber ein Nachteil ist, dass es ist nur mehr Arbeit. Es ist mehr Aufwand. Sie haben zu den Datenbanken zu verstehen. Sie haben, um es einzurichten. Sie benötigen einen Server zu laufen die Datenbank auf. Sie müssen verstehen, wie es zu konfigurieren. Das sind also nur diese Arten von Kompromissen. Während eine CSV-Datei, können Sie schaffen sie mit gedit. Und du bist gut zu gehen. Es gibt keine Komplexität darüber hinaus. 

Verwendung eines Trie anstelle einer Hashtabelle mit separater Verkettung zu speichern ein Wörterbuch der Wörter erinnert von pset5. So versucht ein auf den Kopf, in der Theorie zumindest ist was? Constant Zeit, zumindest wenn Sie Hashing von jedem der einzelnen Buchstaben in einem Wort, wie Sie könnte für pset5 haben. Das könnte fünf Hashes, sechs sein Hashes, wenn es fünf oder sechs Buchstaben in dem Wort. Und das ist ziemlich gut. Und wenn es auf eine obere Grenze, wie Ihre Worte lang sein könnte, ist, dass tatsächlich asymptotisch konstante Zeit. 

Während eine Hash-Tabelle mit separater Verkettung, das Problem, dass es mit Art der Datenstruktur ist, dass der Leistung der Algorithmen in der Regel abhängig von der Anzahl von Dingen bereits in der Datenstruktur. Und das ist definitiv der Fall mit Ketten, wobei die mehr Sachen, die man setzen in einer Hash-Tabelle, die mehr denen Ketten gehen, was im schlimmsten bedeutet Fall das, was Sie vielleicht gesucht werden ist ganz am Ende einer dieser Ketten, die effektiv obliegt in etwas linear. 

Jetzt, in der Praxis könnte es absolut der Fall, dass eine Hash-Tabelle ist mit Ketten schneller ist als eine entsprechende Trie Umsetzung. Aber das ist aus verschiedenen Gründen, unter sind die Versuche verwenden eine ganze Reihe von Speicher Das kann in der Tat langsam Dinge unten, weil Sie nicht bekommen, schön Vorteile der so genannte Caching, wo die Dinge, die nahe beieinander liegen im Speicher zugegriffen werden kann häufig schneller. Und manchmal kann man mit zu kommen eine wirklich gute Hash-Funktion. Auch wenn Sie ein bisschen verschwenden Speicher, könnte man in der Tat in der Lage, schnell und nicht die Dinge finden, so schlecht, wie linear. 

Also kurz gesagt, es war nicht unbedingt mit irgendwelchem ​​eine oder sogar zwei bestimmte Dinge, die wir gesucht haben. Wirklich alles, was überzeugend als oben und unten allgemein unser Auge gefangen. 

ROB BOWDEN: Also für den Kopf, wir haben nicht selbst akzeptieren "schneller." Sie musste etwas darüber zu sagen. Selbst wenn man theoretisch schneller, sagte, wir wussten, dass Sie Art verstanden dass es 0 von 1. Und Hash-Tabelle, in der Theorie, nicht 0 von 1. Die Erwähnung nichts über Laufzeit in der Regel haben Sie die Punkte. Aber "schneller", die meisten Lösungen auf die große Tafel, die versucht waren, wurden objektiv langsamer als Lösungen waren, dass Hash-Tabellen. So schneller an und für sich ist nicht wirklich wahr. 

DAVID J. MALAN: Dom de dom dom. Ich bin wahrscheinlich der einzige, der erkennt, das ist, wie das ist zu vermuten, ausgesprochen werden, oder? 

ROB BOWDEN: Ich hatte wirklich keine Ahnung. 

DAVID J. MALAN: Es machte Sinn in meinem Kopf. 

ROB BOWDEN: Ich mache diese. OK. Das ist also die eine, wo man ziehen musste das Diagramm ähnlich wie Sie vielleicht haben auf früheren Prüfungen gesehen. Also lasst uns einfach, dies zu betrachten. So aus dem HTML-Knoten haben wir zwei Kinder, der Kopf und der Körper. Also haben wir verzweigen - Kopf und Körper. Der Kopf hat eine Titel-Tag. So haben wir einen Titel. 

Nun, die eine Sache, eine Menge Leute vergessen ist, dass diese Textknoten sind Elemente innerhalb dieses Baumes. Also hier passieren wir sie als Ovale zeichnen um sie von diesen zu unterscheiden Knotentypen. Aber Mitteilung auch hier haben wir oben, Mitte und unten wird am Ende als Textknoten. So vergessen die war etwas einer gemeinsamen Fehler. 

Der Körper hat drei Kinder - diese drei divs. So div, div, div und dann der Text Knoten Kinder dieser divs. Das ist ziemlich viel es für diese Fragen. 

DAVID J. MALAN: Und es ist bemerkenswert, auch wenn wir uns nicht auf diese wohnen Details in der Zeit verbringen wir auf JavaScript, dass die Bestellung der Fall ist, in Tatsächlich Angelegenheit technisch. Also, wenn Kopf kommt, bevor der Körper in HTML, dann sollte es die erscheinen in der aktuellen DOM links des Körpers. Dass sein ist in der Regel nur FYI, so genannten Dokument um, wo es nicht egal. Und wenn du die Implementierung eines Parsers ein Programm, das HTML in Gebäude liest auf den Baum im Speicher, um ehrlich zu sein, das ist wohl intuitiv, was Sie tun es trotzdem - von oben nach unten, von links nach rechts. 

ROB BOWDEN: Fragen dazu? Sollte ich das nächste? 

DAVID J. MALAN: Sicher. 

ROB BOWDEN: OK. Das ist also der Pufferüberlauf Angriff Frage. Die Hauptsache ist, hier zu erkennen ist, na ja, wie könnte ein Gegner Trick dieses Programm in der Ausführung beliebigen Code? So argv1 die erste Befehlszeile Argument zu diesem Programm, das sein kann beliebig lange. Aber hier sind wir mit memcpy kopieren argv1, die hier ist bar. Wir übergeben Sie als Argument. Und so ist es unter den Namen bar. 

Also sind wir memcpying bar in diesen Puffer c. Wie viele Bytes zu kopieren wir? Nun jedoch viele Bytes Bar passiert, verwenden, die Länge dieses Argument. Aber c ist nur 12 Byte breit. Wenn wir also eine Befehlszeile ein Argument das ist mehr als 12 Bytes, wir sind werde diese überlaufen insbesondere Puffer. Nun, wie könnte ein Gegner auszutricksen die programmieren, beliebigen Code auszuführen? 

Also denken Sie daran, dass hier Haupt ruft foo. Und so ist, dann Haupt Anrufe foo. Ziehen wir dies. So haben wir unsere Stack. Und hat ein Hauptstapelrahmen an der Unterseite. An einem gewissen Punkt, foo Haupt Anrufe. Nun, sofort, foo Haupt Anrufe. Und so foo bekommt seinen eigenen Stack-Frame. 

Jetzt, an einem gewissen Punkt, foo wird, um zurückzukehren. Und ging foo Renditen, müssen wir wissen, an welche Codezeile innerhalb der Haupt wir waren, um zu wissen, wo wir sollten in Haupt wieder aufzunehmen. Wir können foo aus einer ganzen nennen Haufen von verschiedenen Orten. Wie können wir wissen, wo sie zurückkehren? Nun müssen wir, dass irgendwo zu speichern. 

Also irgendwo hier rechts herum, speichern wir wo wir noch einmal zurück foo Renditen. Und das ist die Absenderadresse. So, wie ein Gegner könnte nutzen hierfür ist die Tatsache, dass dieser Puffer c gespeichert ist, lassen Sie uns sagen, hier ist c. Also haben wir 12 Bytes für c bekam. Dies ist c. Und das ist Stapelring foo. Also, wenn der böswillige Benutzer mehr geht Bytes als 12, oder sie einen Befehl eingeben Zeilenargument, die länger als 12 ist Zeichen, dann werden wir diesen Puffer überlaufen. 

Wir können weitermachen. Und irgendwann, weit gehen wir genug, dass wir beginnen Überschreiben Sie diese Absender-Adresse. Also, wenn wir die Rücksprungadresse zu überschreiben, Dies bedeutet, dass, wenn foo Renditen, sind wir dorthin, wo die Rückkehr böswilliger Benutzer sagt es von was es Wert eingegeben wird, gleichgültig mit welchen Zeichen, die der Benutzer eingegeben werden. Und so, wenn der böswillige Benutzer wird besonders klug, er kann dies zurück zu irgendwo in der printDef Funktion oder irgendwo in der malloc Funktion, nur irgendwo willkürlich. 

Aber auch klüger ist, was, wenn er der Benutzer zurückkehrt, genau hier. Und dann Ausführen starten diese als Codezeilen. Also an diesem Punkt, der Benutzer eingeben kann was er will in dieser Region. Und er hat die komplette Kontrolle über das Programm. Fragen dazu? Also komplett die nächste Frage ist die Neuimplementierung von foo in einer Weise dass es nicht mehr anfällig. 

Also gibt es ein paar Möglichkeiten Sie könnte das getan haben. Wir haben immer noch nur c wobei der Länge 12. Man könnte dies geändert haben als Teil der Lösung. Wir haben auch einen Scheck zu machen Bar war sicher nicht null ist. Obwohl Sie nicht brauchen dass für die volle Punktzahl. Also sind wir die erste Prüfung String-Länge-Bar. Wenn es mehr als 12, dann nicht tatsächlich tun die Kopie. Also das ist ein Weg, es zu reparieren. 

Eine weitere Möglichkeit der Fixierung ist es anstelle c mit der Länge nur 12, lassen Sie es werden der Länge strlen (bar). Eine weitere Möglichkeit der Fixierung ist eigentlich nur, um zurückzukehren. Also, wenn Sie hatte gerade losgeworden alle dieses, wenn Sie hatte gerade alle gelöscht Zeilen Code, würden Sie bekommen haben volle Punktzahl, da diese Funktion nicht wirklich etwas zu erreichen. Es ist das Kopieren der Befehlszeile Argument in eine Array in seine lokalen Stack-Frame. Und dann die Sache zurück. Und was auch immer es versierter ist weg. Also Rückkehr war auch eine ausreichende Weg, um die volle Punktzahl. 

DAVID J. MALAN: Nicht ganz der Geist der die Frage, aber die pro akzeptabel spec dennoch. 

ROB BOWDEN: Fragen zu einem der das? Die eine Sache, dass Sie mindestens benötigt, um Code kompiliert haben. Also auch wenn Sie nicht technisch anfällig, wenn der Code nicht kompilieren, können wir nicht akzeptieren wollten, dass. Keine Fragen? OK. 

DAVID J. MALAN: Wollen Sie , diesen Titel zu sagen? 

ROB BOWDEN: Nein 

DAVID J. MALAN: Also in diesem, diese war entweder gute oder schlechte Nachrichten. Dies ist buchstäblich das gleiche Problem als erste Quiz. Und es ist fast die gleiche Problem pset1. Aber es wurde bewusst vereinfacht, um sein eine einfachere Pyramide, eine, die sein können, mit einem leicht gelöst einfacher Iteration. Und wirklich, was wir auf immer hier war nicht so sehr die Logik, weil wahrscheinlich zu diesem Zeitpunkt, sind Sie mehr Komfort als Sie waren, in der ersten Woche mit for-Schleifen oder warum Loops, aber wirklich auseinander zu necken, dass Sie ein wenig bequem mit der sind Vorstellung, dass PHP ist nicht nur über das, was Programmierung. Es kann tatsächlich als eine Sprache verwendet werden, Befehlszeilenprogramme schreiben. 

Und in der Tat ist das, was wir versuchten, Ihre Aufmerksamkeit zu zeichnen. Dies ist ein Kommandozeilen-PHP-Programm. Also C-Code hier, während korrekt in C, nicht für PHP zu korrigieren. Aber der Code ist wirklich das gleiche. Wenn Sie die Lösungen für Quiz vergleichen 0 gegen ein Quiz, werden Sie feststellen, dass es ist fast identisch mit Ausnahme einige Dollar-Zeichen und für die Fehlen eines Datentyps. Insbesondere dann, wenn wir einen Blick hier, Sie werden sehen, dass wir durchlaufen, in diesem Fall von 1 bis 7 durch. 

Wir hätten es getan haben 0 Index. Aber manchmal denke ich, es ist nur mental leichter, über Dinge zu denken von 1 bis 7. Wenn Sie einen Block, dann zwei Blöcke, dann drei, dann Punkt, Punkt, Punkt sieben. Wir haben j auf 1 initialisiert und dann zählen auf bis zu i. Und hier ist alles ansonsten identisch. Aber bemerkenswert sind ein paar Dinge. Wir geben Ihnen diese beiden Zeilen, diese erste ein, goofily als Kram genannt für scharfe Knall. Und dass, nur gibt den Pfad, der Ordner, in dem ein Programm sein kann festgestellt, dass Sie verwenden möchten um diese Datei zu interpretieren. 

Und dann die Linie nach, dass der bedeutet natürlich, geben Sie PHP-Modus. Und die Zeile ganz unten bedeutet Ausfahrt PHP-Modus. Und das funktioniert im Allgemeinen mit interpretierte Sprachen. Es ist irgendwie ärgerlich, wenn Sie schreiben, eine Programm in einer Datei namens foo.php. Und dann die Benutzer müssen nur erinnern, OK, um dieses Programm ausführen, ich auf den Typ "php foo.php Raum." Art von ärgerlich, wenn sonst nichts. Und es zeigt auch, dass das Programm ist in PHP, das ist nicht alles geschrieben das Beleuchten des Benutzers. 

So können Sie die. Php ganz zu entfernen Rückruf von Vortrag. Und Sie können tatsächlich tun. / Foo, wenn Sie es, indem sie es chmodded haben ausführbaren Datei. So chmod a + x foo wäre getan. Und wenn Sie auch den Kram hier hinzufügen. Aber wirklich, war das Problem immer bei Ausdruck von etwas. Kein HTML, kein C-Code-Sicherheit, nur einige PHP. So Milo dann in Problem 25 zurück. Und in 25, wurden Sie die folgenden gegeben Skelett-Code, der eine war ziemlich einfache Web-Seite. Und die saftigen Teil HTML-weise war nach unten Hier, wo wir innerhalb des Körpers haben eine Form, die eindeutige ID der Eingänge hat innerhalb dessen war zwei Eingänge, einen mit einer Idee des Namens, eines mit einer Idee der Taste. 

Die erste war Typ Text, der zweite vom Typ einreichen. Und so haben wir euch eigentlich mehr Zutaten als man benötigt, nur so ihr hattet Optionen, mit denen um dieses Problem zu lösen. Sie müssen nicht unbedingt brauchen alle diese IDs. Aber es ermöglicht Ihnen zu lösen sie auf unterschiedliche Weise. Und an der Spitze, feststellen, dass Das Ziel war es, auslösen ein Fenster wie diese - Hallo, Milo! - Pop-up im Browser mit die Super-einfach, wenn nicht hässlich, Alarm-Funktion. Und so, letztlich läuft es darauf hinaus konzeptionell irgendwie Hören für Einreichungen des Formulars Client-Seite , Nicht die Server-Seite, irgendwie reagiert auf diese Vorlage durch packte den Wert, den der Benutzer eingegeben in dem Namensfeld, und dann Anzeige in den Körper einer Warnung. 

So ein Weg, dies zu tun ist mit jQuery, die ein wenig aussieht syntaktisch verwirrend auf den ersten. Sie können dies mit reinem DOM-Code zu tun - document.getelement nach ID. Aber lassen Sie uns einen Blick auf diese Version. Ich habe ein paar wichtige Linien zuerst. So ein, haben wir diese Linie, das ist, identisch, was man gesehen haben in, glaube ich, form2.html aus der Klasse 9 in der Woche. Und das ist nur zu sagen, führen der folgende Code, wenn das Dokument ist fertig. Da dies nur wichtig, weil HTML-Seiten werden oben zu lesen unten, von links nach rechts. 

Und deshalb, wenn Sie versuchen zu tun, etwas in Code hier oben bis zu einem gewissen DOM Element, einige HTML-Tag, das ist nach unten hier, bist du es tun zu früh, weil dies nicht sogar in den Speicher gelesen wurden. So sagen diese document.ready Linie, wir sagen, hier ist ein Code, Browser. Aber nicht ausführen Sie dies, bis die ganze Dokument fertig ist, ist, dass die DOM Baum im Speicher vorhanden ist. Dieser ist ein wenig mehr einfach, wenn ein syntaktisch bisschen anders, wo ich sage, Halte das HTML-Element, dessen einzigartige Kennung ist Eingänge. Das ist, was die Hash-Tag bezeichnet, die eindeutige ID. Und dann rufe ich. Einreichen. 

So. Einreichen hier ist eine Funktion, sonst als ein Verfahren bekannt, das innerhalb des Objekts auf der linken Seite gibt, dass ich nicht zu markieren. Also, wenn Sie denken, der Eingänge als Objekt in Erinnerung - und in der Tat ist es. Es ist ein Knoten in einem Baum - . Einreichen Einrichtung, wenn diese Form mit Diese ID wird vorgelegt, führen Mit dem folgenden Code. Ich weiß nicht, was der Name der Funktion ist, dass ich die Ausführung. So, hier bin ich mit, wie früher, was ist genannte Lambda-Funktion oder eine anonyme Funktion. Es ist gar nicht intellektuell interessante anders als es keinen Namen hat, das ist gut, wenn Sie nur sind jemals, es einmal anzurufen. Und innen gibt habe ich eigentlich umgehen die Vorlage des Formulars. Ich zuerst eine Variable deklarieren Wert genannt. Und was ist dann die Wirkung dieser hervorgehobene Teil jetzt hier? Was bedeutet, dass bei einem zu tun hohem Niveau für mich? 

Zielgruppe: IT bekommt den Wert, den die Benutzer nicht in der unten stehenden HTML-Code. Es wird diese ID und dann findet den Wert der IT. 

DAVID J. MALAN: Genau. Es packt die Knoten, deren einzigartige Kennung ist der Name. Es wird der Wert darin, die ist vermutlich, was der Benutzer eingegeben selbst zu tragen. Und dann speichert er, dass in der Variable namens Wert. Nebenbei haben Sie auch könnte dies getan, ein wenig anders. Indem er etwas völlig akzeptabel var Wert liegen wird document.getElementById. Und deshalb ist es ein wenig langweilig, nicht mit jQuery. "Name". Wert. So völlig akzeptabel. Verschiedene Möglichkeiten, dies zu tun. jQuery nur neigt dazu, ein wenig mehr sein, prägnant und definitiv mehr beliebt unter Programmierern. 

Nun, ich mache ein bisschen Verstand zu überprüfen, weil in das Problem Aussage, die wir ausdrücklich gesagt, wenn der Benutzer hat noch nicht eingegeben seine Namen, eine Benachrichtigung nicht zeigen. Aber man kann für das überprüfen, indem Sie einfach Kontrolle für die leere Zeichenfolge für eine Zitat-Zitat Ende, wenn es nichts wirklich da. Aber wenn es nicht gleich quote-unquote, Ich möchte Warnungen rufen. Und das Interessante dabei ist, dass wir sind mit den Plus-Operator, der tut, was in JavaScript? Verketten. So ist es wie PHPs Punkt-Operator. Gleiche Idee, etwas andere Syntax. Und ich bin nur der Erstellung der Zeichenfolge, Sie sah auf dem Screenshot - Hallo, so und so. 

Und dann das letzte Detail ist diese. Warum habe ich falsch innen zurück dieser anonymen Funktion? 

ZIELGRUPPE: Es gibt keinen Wert. Sie steckte es in Form. Es sagt nur, wenn der Wert nicht gleich leer, dann tun Sie es. Es war eine leere in dieser Vorlage. 

DAVID J. MALAN: OK. Aber vorsichtig. Es ist niemand anderes hier. Und das return false außerhalb der if-Bedingungen. Also das hervorgehobene Zeile, return false, führt, egal was, wenn das Formular abgeschickt wird. Was false zurück innerhalb dieses Event-Handler, wie es heißt, die Veranstaltung in Frage als Vorlage? 

ZIELGRUPPE: Weil es nur einmal. 

DAVID J. MALAN: nur einmal passiert. Nicht ganz. Ja? 

ZIELGRUPPE: Es verhindert, dass das Formular von Vorlage auf das Standardverhalten, was die Seite neu zu laden machen würde. 

DAVID J. MALAN: Genau. Also ich bin Überlastung der Begriff hier einreichen, weil ich sage, ist die Form eingereicht werden. Aber, wie Sie vorschlagen, ist es eigentlich nicht wurde im wahrsten HTTP Weg übermittelt. Wenn Sie auf Absenden, weil Sie auf unserer onSubmit Handler, wir Abfangen dass Form Vorlage so zu sprechen. Wir sind dann unser Ding mit JavaScript-Code. Aber ich bin bewusst false zurück, weil das, was ich will nicht geschehen ein Bruchteil einer Sekunde später ist für die ganze Form sich auf die Bahn abgegeben werden Server mit Schlüssel-Wert-Paare durch Veränderung die URL, die so etwas wie q = Katzen oder was auch immer wir getan haben, zum Beispiel in der Klasse. Ich glaube nicht, dass das passiert, weil gibt es keinen Server für diese Abhör bilden Unterwerfung. Es ist rein in JavaScript-Code. Und das ist, warum ich noch nicht einmal eine action-Attribut auf meiner Form, weil ich nicht für dieses beabsichtigen, immer auf den Server zu gehen. 

So ist es, die eingereicht. Aber wir Abfangen diese Form Einreichung und verhindern, dass die Standard- Verhalten, das eigentlich gehen den ganzen Weg auf den Server. 

ZIELGRUPPE: So halten es Client-Seite. 

DAVID J. MALAN: Halten es Client-Seite. Genau richtig. Weiter oben war mein oh MySQL. 

ROB BOWDEN: OK. So war diese erste Frage in der Regel rau für die Menschen. Obwohl die späteren ging besser. Sie hatten also die richtigen Daten wählen Typen für beide Säulen. Und beide von diesen haben einige Dinge über sie, dass machen die Wahl schwer. So int war keine gültige Geben Sie für Nummer. Der Grund dafür ist eine 12-stellige Konto Nummer, ist ein int nicht groß genug, um Gesamt speichern Ziffern. So würde eine gültige Wahl eine große gewesen sein int, wenn Sie wissen, dass passiert. Eine andere Wahl hätte ein char-Feld der Länge 12. Also entweder von denen würde gearbeitet haben. Int nicht. 

Jetzt, Balance, denken Sie zurück an pset7. So haben wir speziell Dezimalstelle auf speichern Sie den Wert von Aktien oder - 

DAVID J. MALAN: Cash. 

ROB BOWDEN: Cash. Wir verwendeten Dezimalzahl, die Menge an zu speichern Geld, das der Benutzer derzeit. Also der Grund, warum wir das tun, ist weil, denken Sie daran, die Schwimmer. Es gibt in Gleitkomma-Präzision. Es kann nicht genau das Geld speichern Werte wie wir wollen hier. So Dezimalzahl ist in der Lage, genau Store etwas, sagen wir, zwei Dezimalstellen. Das ist, warum Balance, sie wollen wir Dezimal-und nicht schwimmen zu können. 

DAVID J. MALAN: Und auch, auch, obwohl das wäre vielleicht klug in anderen Zusammenhängen zu denken, vielleicht ist eine Chance für einen int. Ich werde einfach im Auge behalten Dinge in ein paar Cent. Da haben wir gezeigt, explizit die Standard Wert des Seins 100.00, dass heißt, es könnte nur ein int sein. Und noch eine Zahl mit Subtilität zu war, dass es nicht gemeint um eine Fangfrage sein. Aber daran erinnern, dass ein int in MySQL, wie in C, zumindest in der Gerät ist 32-Bit. Und auch wenn wir nicht erwarten, dass Sie genau wissen, wie viele Stellen, die Mittel, nicht daran erinnern, dass die größte Zahl Sie potentiell darstellen kann mit einem 32-Bit-Zahl ist in etwa, was? 

Welche Nummer haben wir immer sagen? 2 bis 32, die in etwa das, was ist? Sie müssen nicht genau wissen. Aber grob ist hilfreich im Leben. Es ist rund 4 Milliarden Euro. Also haben wir gesagt, dass ein paar mal. Ich weiß, ich habe das ein paar Mal gesagt. Und es ist rund 4 Milliarden Euro. Und das ist eine gute Regel Faust wissen. Wenn Sie 8-Bit-, 256 haben ist die magische Zahl. Wenn Sie 32 Bit, 4 haben Milliarden geben oder nehmen. Also, wenn Sie nur auf 4 Milliarden zu schreiben, Sie werden sehen, dass es weniger Stellen als 12, was bedeutet, dass es nicht klar Ausdrucks genug zu erfassen ein 12-stellige Kontonummer. 

ROB BOWDEN: OK. So gingen die anderen besser. So nehme an, dass die Bank schreibt eine 20 $ monatlich Wartungsgebühr auf alle Konten. Mit SQL-Abfrage, welche die Bank konnte Abzug $ 20 von jedem Zahl, auch wenn es ergeben sich einige negative Salden? Also im Grunde gibt es vier Haupttypen von Abfragen - einzufügen, wählen, aktualisieren und löschen. Also, was tun wir denken, wir sind hier benutzen? Aktualisieren. 

Werfen wir also einen Blick. So, hier sind wir zu aktualisieren. Welche Tabelle aktualisieren wir Konten? So aktualisieren Konten. Und dann die Syntax sagt, was Konten aktualisieren wir? Nun, wir Balance-Einstellung gleich die aktuellen Wert von minus 20 Balance. So wird dies alle Zeilen aktualisieren von Konten, Subtraktion $ 20 aus dem Gleichgewicht. 

DAVID J. MALAN: Ein häufiger Fehler hier auch wenn wir es manchmal verziehen, war es eigentlich PHP-Code hier Aufruf der Query-Funktion oder setzen Anführungszeichen um alles, dass nicht brauchen, um dort zu sein. 

ROB BOWDEN: Denken Sie daran, dass MySQL eine eigene Sprache von PHP. Wir passieren zu MySQL in PHP zu schreiben. Und PHP wird dann Senden über dem MySQL-Server. Aber Sie brauchen nicht in PHP, um kommunizieren mit einem MySQL-Server. 

DAVID J. MALAN: Genau. Also keine Variablen mit Dollar-Zeichen In diesem Zusammenhang sein. Es kann nur die gesamte Mathematik zu tun innerhalb der Datenbank. 

ROB BOWDEN: OK. Also das nächste. Ist das der nächste? Ja. Also mit welcher SQL-Abfrage, die die Bank Abrufen der Kontonummern der reichsten Kunden, die mit Guthaben mehr als 1000? Also, welche der vier Arten werden wir hier? Wählen Sie. So wollen wir auswählen. Was wollen wir wählen? Welche Spalte wollen wir wählen? Wir wollen speziell Nummer zu wählen. Aber wenn Sie die Sterne, die wir auch das akzeptiert. 

Nummer So wählen Sie aus, welche Tabelle? Konten. Und dann die Bedingung, die wir wollen? Wo Gleichgewicht größer als 1000. Wir auch mehr akzeptiert oder gleich. Letzte. Mit SQL-Abfrage, welche die Bank konnte Nähe, das heißt, zu löschen jedes Konto, das hat eine Bilanz von 0 $? Also, welcher der vier sind wir gehen zu verwenden? Löschen. So ist die Syntax für das? Löschen von welchem ​​Tisch? Konten. Und dann, auf dem der Zustand wir löschen wollen - wo Saldo gleich Null. So löschen Sie alle Zeilen aus Konten wobei der Rest Null ist. Fragen zu einem von diesen? Möchten Sie die Warteschlange? 

DAVID J. MALAN: Queue Führer. Also in diesem, haben Sie etwas haben wir vertraut Struktur, die wir erkundet ein Bit in der Klasse neben der Strukturen, welche ein Daten war Struktur im Geiste verwandt. Der Unterschied allerdings mit einer Warteschlange dass wir irgendwie daran erinnern, wer war am Anfang der Warteschlange, in großer Teil, so dass wir mehr machen effizientere Nutzung des Speichers zumindest wenn wir mit einem Array. 

Da erinnern, wenn wir ein Array, wenn zum Beispiel ist dies die Front die Warteschlange, wenn ich in der Warteschlange bekommen hier und dann jemand in der Leitung wird hinter mir, hinter mir, hinter mir, und eine Person aus der Reihe tanzt, können Sie könnte, wie wir sahen einige unserer menschlichen Freiwillige in der Klasse, haben alle verschieben diese Weise. Aber im allgemeinen, nachdem jeder tun etwas ist nicht die beste Nutzung der Zeit in einem Programm, weil es bedeutet, dass Ihre Algorithmus in dem, was läuft asymptotische Laufzeit? Es ist linear. 

Und ich fühle mich wie das ist irgendwie dumm. Wenn der nächste in der Reihe ist der nächste Person, die angeblich in die zu gehen ist speichern, nicht alle haben sie sich zusammen zu bewegen. Lassen Sie die Person aus gepflückt werden wenn die Zeit kommt, zum Beispiel. So können wir ein wenig Zeit, es zu retten. Und so zu tun, aber, dass Mittel dass der Kopf der Schlange oder die Anfang der Warteschlange wird zu immer tiefer und tiefer zu bewegen in die Reihe und schließlich könnte tatsächlich wickeln um, wenn wir mit ein Array, um die Menschen zu speichern in dieser Warteschlange. So kann man fast denken, der Array als eine kreisförmige Daten Struktur in diesem Sinne. 

Also irgendwie muss man den Überblick über die zu halten Größe von ihr oder wirklich das Ende von und dann, wenn der Anfang ist. So schlagen wir vor, dass Sie erklären, eine solche Warteschlange Berufung q es, nur ein Buchstabe. Dann schlagen wir vor, dass die Front auf Null und initialisiert die Größe auf Null initialisiert werden. 

So jetzt gibt es nichts, innerhalb dieser Warteschlange. Und wir bitten Sie, füllen Sie bitte den Umsetzung der Enqueue unten in derart, dass die Funktion fügt n zu das Ende von q und dann true zurück. Aber wenn q voll ist oder negativ, die Funktion sollte anstelle return false. Und wir gaben Sie ein paar von Annahmen. Aber es sind nicht wirklich funktional relevant ist, existiert nur, dass bool, weil technisch nicht tut bool gibt es in C sei denn, Sie sind ein bestimmte Header-Datei. So, dass war nur sicherstellen, dass es wurden nicht ist das ein Trick Frage Art der Sache. 

So Enqueue, in der Probe haben wir vorgeschlagen, Lösungen wie folgt realisieren. Eins, prüfen wir zuerst die Leichtigkeit, die niedrig hängenden Früchte. Wenn die Warteschlange voll ist oder die Zahl, die Sie versuchen zu legen sind weniger als Null ist, die wir in die besagte Spezifikation des Problems sollte nicht erlaubt sein, denn wir wollen nur nicht-negative Werte, dann sollten Sie nur sofort false zurück. So einige relativ einfach Fehlerprüfung. Wenn Sie aber, dass die tatsächlichen hinzufügen möchten Nummer, um ein wenig zu tun hatten Sie Denken Sie hier. Und das ist, wo es ein wenig ärgerlich mental, weil man herauszufinden, wie man Rundum behandeln. 

Aber der Keim der Idee hier ist, dass der Interesse für uns ist, dass Rundum- oft bedeutet, modulare Arithmetik und die Mod-Betreiber, die Seiten Prozent, wo Sie von einem größeren Wert gehen zurück auf Null und dann eins und zwei und drei und dann wieder um auf Null, eins und zwei und drei und so weiter wieder. So schlagen wir vor, die Art und Weise, dies zu tun ist dass wir indizieren sollen in die Array namens Zahlen, bei denen unsere Zahlen liegen. Aber um dorthin zu kommen, wollen wir zuerst zu tun was auch immer die Größe der Warteschlange ist aber dann hinzufügen, dass unabhängig von der vorne auf der Liste steht. Und die Wirkung davon ist, mit uns setzen die richtige Position in der Warteschlange und nicht davon ausgehen, dass die erste Person in der Schlange ist am Anfang, was er oder sie konnte absolut sein, wenn wir wurden ebenfalls verlagert alle. Aber wir sind nur die Schaffung von Arbeit für uns selbst, wenn wir nahmen dass bestimmten Weg. 

So können wir es relativ einfach zu halten. Wir müssen bedenken, dass wir gerade fügte eine int in der Warteschlange. Und dann haben wir nur true zurück. Inzwischen in dequeue, fragten wir Sie folgendes tun. Umsetzung in einer Weise, dass es aus der Warteschlange entfernt, also entfernt und zurückgegeben, INT an der Vorderseite Warteschlange. Um den int zu entfernen, genügt es, zu vergessen. Sie brauchen nicht zu sein Bit überschreiben. Also ist es eigentlich noch gibt. So wie Daten auf einer Festplatte, wir sind nur ignorieren die Tatsache, dass es jetzt dort. Und wenn q leer ist, sollten wir stattdessen zurückgeben negativ ein. Also das fühlt sich willkürlich. Warum zurück minus 1 statt falsch? Ja. 

ZIELGRUPPE: Q ist die Speicherung positive Werte. Da Sie nur positive Werte speichern in der q, negativ ist ein Fehler aufgetreten. 

DAVID J. MALAN: OK, stimmt. Also, weil wir nur positive Speicherung Werte oder Null ist, dann ist es in Ordnung, Rückkehr einen negativen Wert wie ein Wächter Wert, ein spezielles Symbol. Aber du bist Umschreiben der Geschichte gibt, weil der Grund, nur wir sind Rückkehr nicht-negative Werte Denn wir wollen haben eine Sentinelwert. Also genauer gesagt, warum nicht einfach Rückkehr in Fällen von Fehlern falsch? Ja. 

ZIELGRUPPE: Sie haben versagt um eine ganze Zahl zurück. 

DAVID J. MALAN: Genau. Und das ist, wo C bekommt ziemlich Zwangs. Wenn Sie sagen, Sie gehen um einen int zurück, Sie haben um einen int zurück. Sie können nicht schick und beginnen Rückkehr ein bool oder ein Schwimmer oder ein String oder so ähnlich. Nun, mittlerweile, JavaScript und PHP und einige andere Sprachen können in der Tat, Sie haben verschiedene Rück Arten von Werten. Und das kann wirklich nützlich sein, wo Sie könnten positive Ganzzahlen, Nullstellen zurückkehren, ints negativen oder falsch oder null sogar Fehler zu bedeuten. Aber wir haben das nicht Vielseitigkeit in C. 

Also mit dequeue, was wir vorschlagen zu tun ist - 

ROB BOWDEN: Sie können false zurück. Es ist nur so, dass falsch ist Hash definieren falsche Null. Also, wenn Sie false zurück, Sie zurück Null sind. Und Null ist ein gültiger, was in unserem Warteschlange während negative 1 ist nicht, ob falsche passiert negative 1 sein. Man sollte aber auch nicht brauchen, um das zu wissen. 

DAVID J. MALAN: Das ist warum ich es nicht sagen. 

ROB BOWDEN: Aber es war nicht wahr dass man nicht false zurück. 

DAVID J. MALAN: Sicher. So dequeue, bemerken wir akzeptieren Erlöschen als Argument. Und das ist, weil wir nicht Durch nichts in. Wir wollen einfach nur, um das Element zu entfernen an der Vorderseite der Warteschlange. Also, wie können wir dabei vorgehen? Nun, zunächst wollen wir dies tun schnelle Plausibilitätsprüfung. Wenn die Queue-Größe 0 ist, gibt es keine Arbeit zu tun. Zurück negativ ein. Fertig. Also das ist ein paar Zeilen von meinem Programm. So bleiben nur vier Zeilen. 

So, hier habe sich entscheiden, verringern die Größe. Und effektiv Verringern der Größe bedeutet, dass ich vergessen habe etwas drin. Aber ich habe auch zu aktualisieren, wo die vor den Zahlen sind. So, das zu tun, muss ich zwei Dinge tun. Muss ich erst einmal, was die Anzahl erinnern ist an der Vorderseite der Warteschlange, , weil ich das Ding zurück. Also ich möchte nicht versehentlich vergessen über sie und dann überschreiben. Ich werde einfach in einen int erinnern. 

Und jetzt möchte ich aktualisieren q.front zu q.front eins werden. Also, wenn dieser die erste Person in war Linie, nun, ich möchte plus 1 zu tun weisen auf die nächste Person in der Schlange. Aber ich muss diese Rundum behandeln. Und wenn die Kapazität ist eine globale Konstante, das wird mir zu erlauben, stellen Sie sicher, als ich auf die letzte Person in Zeile, wird die Modulo-Operation bringen mich zurück auf Null bei der Anfang der Warteschlange. Und das übernimmt die Rundum hier. Und dann gehe ich auf n zurück. 

Nun, genau genommen, habe ich nicht müssen n erklären. Ich wusste nicht, um es zu packen und speichern vorübergehend, da der Wert immer noch da. So konnte ich genau die richtige Arithmetik um den ehemaligen Chef zurück der Warteschlange. Aber ich fühlte mich nur, dass dies mehr klar tatsächlich greifen die int, legte es n, und dann wieder, dass der Übersichtlichkeit halber aber nicht unbedingt notwendig. Psst. Sie sind alle aussprechbar in meinem Kopf. 

ROB BOWDEN: Also erste Frage der binäre Baum Problem. Also erste Frage ist, sind wir unter diesen Zahlen. Und wir irgendwie in sie einfügen wollen Diese Knoten, so dass es ein gültig binären Suchbaum. So ist die eine Sache, über erinnern binäre Suchbäume ist, dass es nicht nur, dass die Sache auf der linken Seite ist geringer und die Sache die rechte ist größer. Es sein muss, dass die gesamte Struktur auf Links ist weniger und die gesamte Baum nach rechts größer. 

Also, wenn ich hier 34 an der Spitze, und dann Ich habe hier 20, das ist also gültig, weit, weil 34 hier oben. 20 nach links gehen. Also das ist, weniger. Aber ich kann nicht dann setzen hier 59, weil obwohl 59 ist auf der rechten Seite von 20, es ist immer noch auf der linken Seite der 34. Also mit dieser Einschränkung im Hinterkopf, die einfachste Weg, wahrscheinlich die Lösung dieses Problem ist es einfach irgendwie dieser Zahlen - so 20, 34, 36, 52, 59, 106. Und dann legen Sie die von links nach rechts. 

Also 20 geht hier. 34 geht hier. 36 geht hier. 52, 59, 106. Und könnte man auch mit gefunden haben, einige einstecken und zu realisieren, oh, warte, ich habe nicht genug Zahlen haben , dies in hier zu füllen. Also muss ich, was meine reshift Route Note sein wird. Aber beachten Sie, dass in der letzten drei, wenn Sie lesen von links nach rechts, ist es in teigender Reihenfolge. 

So, jetzt wollen wir zu erklären, was die Struktur wird für die sein Knoten in diesem Baum. So was brauchen wir in einem binären Baum? Einen Wert vom Typ So haben wir int, so dass einige int-Wert. Ich weiß nicht, was wir als es in der Lösung - int n. Wir brauchen einen Zeiger auf den linken Tochter und ein Zeiger auf das rechte Kind. Also, es wird so aussehen. Und es wird tatsächlich vor aussehen wann haben die doppelt verknüpfte Liste stuff, so Bekanntmachung - Ich werde scrollen, um alle die Weg zurück zu Problem 11. 

So merkt es gleich aussieht, außer wir nur zufällig diese nennen unterschiedliche Namen. Wir haben noch eine ganze Zahl Wert und zwei Zeigern. Es ist nur so, dass anstelle der Behandlung der Zeiger als Hinweis auf die nächste, was und die vorherige Sache, wir behandeln die Zeiger auf den linken Nachfolger zeigen und rechte Kind. OK. Also das ist unsere Struktur-Knoten. Und nun, die einzige Funktion, die wir brauchen, um Umsetzung dafür ist, Traverse, die wir über den Baum-, Druck gehen wollen aus den Werten der Baum in Ordnung. 

So suchen Sie hier, würden wir drucken möchten aus 20, 34, 36, 52, 59 und 106. Wie erreichen wir das? So ist es ziemlich ähnlich. Wenn Sie in der Vergangenheit Prüfung sah das Problem dass Sie ausdrucken wollte der ganze Baum mit Komma zwischen alles, war es eigentlich auch einfacher. So, hier ist die Lösung. Das war wesentlich einfacher wenn du es getan hast rekursiv. Ich weiß nicht, ob jemand versucht, es iterativ zu tun. 

Aber zuerst müssen wir unsere Basisfall. Was ist, wenn die Wurzel ist null? Dann sind wir nur gehen, um zurückzukehren. Wir wollen nicht, etwas zu drucken. Else, wir werden durchqueren rekursiv nach unten. Drucken Sie die gesamte linke Unterbaum. Also alles weniger zu drucken als meine aktuellen Wert. Und dann werde ich mich selbst zu drucken. Und dann werde ich meine rekursiv gesamten rechten Unterbaum, so dass alles größer als mein Wert. Und das wird gedruckt alles in Ordnung. Fragen wie diese tatsächlich führt das? 

ZIELGRUPPE: Ich habe eine Frage auf die [unverständlich]. 

ROB BOWDEN: So ein Weg der Annäherung keine rekursiven Problem ist, man denke nur an darüber mag man denken, über all die Grenzfälle. So betrachten, dass wir wollen Drucken Sie sich dieses ganze Baum. Also alles, werden wir den Schwerpunkt auf ist dies insbesondere Knoten - 36. Die rekursive Aufrufe, so tun wir die, die gerade arbeiten. So, hier, dieses rekursiven Aufruf Traverse, die wir ohne darüber nachzudenken über sie, nur Durchlaufen des linken drei, sich vorstellen, dass bereits 20 druckt und 34 für uns. Und dann, wenn wir irgendwann rekursiv rufen Traverse auf die rechts, das wird richtig gedruckt 52, 59 und 106 us. 

Also da kann 20, 34 zu drucken, und die anderen können drucken, 52, 59, 108, alles, was wir brauchen, um in der Lage zu tun ist Druck uns selbst in der Mitte davon. So drucken Sie alles, was vor uns liegt. Drucken Sie uns selbst, so der aktuelle Knoten Druck 36, regelmäßige printf und dann drucken alles, was uns nach. 

DAVID J. MALAN: Hier Rekursion wird wirklich schön. Es ist diese erstaunliche Sprung des Glaubens, wo Sie das kleinste bisschen Arbeit zu tun. Und dann lassen Sie jemand sonst den Rest erledigen. Und dass jemand anderes ist ironischer Sie. Also für schwere Pluspunkte, wenn Sie blättern in den Fragen - 

ROB BOWDEN: Auf die Fragen? 

DAVID J. MALAN: Und ein wenig nach unten zu die Zahlen, weiß jemand, wo diese Zahlen her? 

ROB BOWDEN: Ich habe buchstäblich keine Ahnung. 

DAVID J. MALAN: Sie erscheinen während des Quiz. 

ZIELGRUPPE: Sind sie die gleichen Zahlen? 

DAVID J. MALAN: Diese Zahlen. Ein kleines Osterei. Also für diejenigen unter Ihnen, Online-Beobachtung an Hause, wenn Sie uns per E-Mail zu sagen, heads@CS50.net, was die Bedeutung Diese wiederkehrenden von sechs Zahlen sind während ein Quiz, werden wir Sie Dusche mit erstaunlicher Aufmerksamkeit in der letzten Vortrag und ein Stress-Ball. Nice, subtil. 

ROB BOWDEN: Irgendwelche letzten Fragen über alles, was auf dem Quiz?