JASON HIRSCHHORN: Willkommen jeder auf das Kapitel Sieben. Wir sind in der Woche sieben des Kurses. Und am kommenden Donnerstag Halloween ist also bin ich wie ein Kürbis gekleidet. Ich konnte nicht bücken und legte auf meine Schuhe, damit ist, warum ich bin nur das Tragen von Socken. Ich bin auch nicht alles unter das Tragen dies, so kann ich es nicht aus, wenn es ablenken zu Ihnen. Ich entschuldige mich im Voraus dafür. Sie brauchen nicht, sich vorzustellen, , was los ist. Ich trage Boxershorts. Es ist also alles gut. 

Ich habe eine längere Geschichte darüber, warum ich bin gekleidet wie ein Kürbis, aber ich werde sparen, dass für die später in diesem Abschnitt weil ich will, um loszulegen. Wir haben eine Menge spannende Dinge , über diese Woche. Die meisten von ihnen beziehen sich direkt auf diese Woche Problem Satz, Rechtschreibfehler. Wir werden über verknüpft werden gehen Listen und Hash-Tabellen für den gesamten Abschnitt. Ich habe diese Liste jede Woche eine Liste der Ressourcen für Sie, um Ihnen zu helfen das Material auf diesem Kurs. Wenn bei einem Verlust oder der Suche nach einigen Weitere Informationen lesen Sie in einem diese Ressourcen. 

Auch hier ist pset6 Rechtschreibfehler, dieser Woche pset. Und es fordert Sie auch, und ich Sie ermutigen, auf eine andere verwenden Ressourcen, die speziell für dieses pset. Insbesondere die drei habe ich auf dem Bildschirm aufgelistet - gdb, die wir waren mit vertrauten und mit für eine Weile jetzt, werde diese Woche sehr hilfreich sein. Also habe ich, dass hier oben. Aber wenn Sie mit C arbeiten, Sie sollten immer mit gdb werden, um Debuggen von Programmen. Diese Woche auch valgrind. Weiß jemand, was valgrind tut? 

ZIELGRUPPE: Es prüft, ob Speicherlecks? 

JASON HIRSCHHORN: Valgrind Prüfungen für Speicherlecks. Also, wenn Sie etwas in Ihrem malloc Programm können Sie für Speicher fragen. Am Ende des Programms, haben Sie auf alles, was Sie haben frei zu schreiben malloced, um den Speicher zurück zu geben. Wenn Sie nicht schreiben, kostenlos am Ende nicht und Ihr Programm kommt zu dem Schluss, alles wird automatisch befreit werden. Und für kleine Programme, ist es nicht so große Sache. Aber wenn Sie schreiben eine längere Lauf sind Programm, das nicht beendet hat, notwendig, in ein paar Minuten oder paar Sekunden, dann Speicherlecks kann eine große Sache werden. 

Also für pset6 ist die Erwartung, dass Sie Null Speicherlecks haben mit Ihr Programm. Um Speicherlecks zu überprüfen, führen valgrind und es wird Ihnen ein paar schöne geben Ausgangs dass Sie wissen, ob oder nicht, alles war frei. Wir werden mit später üben heute, hoffentlich. 

Schließlich wird der Befehl diff. Sie verwendet es so etwas wie in pset5 mit dem Blick-Tool. Sie erlaubt nach innen zu schauen. Sie auch diff auch pro das Problem eingestellt spec. Aber konnten Sie zwei Dateien vergleichen. Sie konnten die Bitmap-Datei und vergleichen info Header einer Personal-Lösung und Ihre Lösung in pset5 wenn Sie entschied sich, es zu benutzen. Diff werden Sie damit tun, als gut. Sie können die richtige Antwort für vergleichen dieser Woche Problem zu Ihrer Antwort gesetzt und sehen, ob es nach oben oder Linien zu sehen Sind die Fehler. 

Das sind also drei gute Tools, die sollten Sie für diese Woche zu verwenden, und auf jeden Fall Ihr Programm überprüfen Mit diesen drei Werkzeuge bevor es in. Auch hier, wie ich jede Woche erwähnt, beides - wenn ihr Feedback für mich positiv und konstruktiv - fühlen Sie sich frei, um auf die Website leiten an der Unterseite des Schiebe und Eingabe es dort. Ich schätze jede und alle Rückmeldungen. Und wenn du mich bestimmte Dinge zu geben, dass Ich tun kann, zu verbessern oder zu, dass ich geht es gut, dass Sie mich zu mögen weiter, nehme ich das zu Herzen und versuchen wirklich schwer zu hören auf Ihr Feedback. Ich kann nicht versprechen, ich werde tun, alles, obwohl, wie das Tragen ein Kürbis-Kostüm jede Woche. 

So werden wir den Großteil verbringen Abschnitt, wie ich bereits erwähnt, sprechen über verkettete Listen und Hash-Tabellen, die wird direkt auf die sein Problem in dieser Woche eingestellt. Verknüpfte Listen wir über relativ gehen schnell, denn wir haben ein gutes Stück verbracht der Zeit gehen über sie im Schnitt. Und so werden wir direkt in das zu bekommen Codierung Probleme für verkettete Listen. Und dann am Ende werden wir darüber zu sprechen Hash-Tabellen und wie sie diese anwenden Woche Problem eingestellt. 

Sie haben diesen Code zuvor gesehen. Dies ist eine Struktur, und es wird definiert, Neues ein Knoten genannt. Und in einem Knoten gibt es eine ganze hier und da ein Zeiger auf ein anderer Knoten. Wir haben das gesehen. Dies wurde kommt für ein paar Wochen. Es kombiniert Zeiger, die wir waren Arbeit mit, und Strukturen, die es erlauben uns auf zwei unterschiedliche verbinden Dinge in einem Datentyp. 

Es ist viel los auf dem Bildschirm. Aber all das sollte relativ sein Sie vertraut mit. In der ersten Zeile, die wir erklären einen neuen Knoten. Und dann in diesem neuen Knoten, habe ich die ganze Zahl in diesem Knoten zu eins. Wir sehen in der nächsten Zeile ich mache ein printf Befehl, aber ich habe ausgegraut der Befehl printf, weil das wirklich wichtiger Teil ist diese Linie hier - new_node.n. Was ist der Punkt das? 

ZIELGRUPPE: an den Knoten gehen und Beurteilung der n-Wert für sie. 

JASON HIRSCHHORN: Das ist genau richtig. Punkt bedeutet den Zugang des n Teil dieser neuen Knoten. Das nächste Zeile macht was? Michael. 

ZIELGRUPPE: Es wird einen weiteren Knoten dass an den neuen Knotenpunkt. 

JASON HIRSCHHORN: Also es funktioniert nicht erstellen Sie einen neuen Knoten. Es schafft ein was? 

ZIELGRUPPE: Ein Zeiger. 

JASON HIRSCHHORN: Ein Zeiger auf einen Knoten, wie von diesem Knoten * gekennzeichneten hier. So schafft einen Zeiger auf einen Knoten. Und die Knoten wird es zeigen zu, Michael? 

ZIELGRUPPE: Neuer Knoten? 

JASON HIRSCHHORN: Neuer Knoten. Und es ist dort zeigen, weil wir haben gegeben es die Adresse des neuen Knotens. Und jetzt in dieser Linie sehen wir zwei Arten von elbe ausdrückt. Und ich wollte darauf hinweisen, wie diese Zwei Dinge sind gleich. In der ersten Zeile, die wir dereferenzieren der Zeiger. So gehen wir in den Knoten. Das ist, was dieser Stern bedeutet. Wir haben gesehen, dass, bevor mit Zeigern. Gehen Sie zu diesem Knoten. Das ist in Klammern. Und dann über den Punkt-Operator zugreifen die n Element dieses Knotens. 

Also das ist, nehmen Sie die Syntax wir hier und jetzt sah Sie es mit einem Zeiger. Natürlich wird es etwas beschäftigt, wenn Sie schreiben diese Klammern - dass Sterne und Punkt. Es wird ein wenig beschäftigt. So haben wir einige syntaktischer Zucker. Und diese Linie hier - ptr_node-> n. Das tut exakt das gleiche Ding. Also diese beiden Codezeilen sind Äquivalent und wird tun genau die gleiche Sache. 

Aber ich wollte darauf hinweisen, zu denen vor wir weiter gehen, so dass Sie verstehen, dass wirklich dieses Ding hier ist nur syntaktischer Zucker für Dereferenzierung der Zeiger, und dann werde die n Teil dieser Struktur. Haben Sie Fragen zu dieser Folie? OK. 

So werden wir durch ein paar gehen von Operationen, die Sie tun können, auf verkettete Listen. Eine verkettete Liste, Rückruf, ist eine Reihe von Knoten, die zueinander weisen. Und wir in der Regel mit einem Zeiger starten Kopf genannt, in der Regel, Punkte, die das erste, was in der Liste. Also in der ersten Zeile hier, wir haben zuerst unsere ursprüngliche L. Also das, was Sie sich vorstellen können - das Text hier als Sie denken nur der Zeiger die wir gespeichert haben Punkte, die irgendwo auf das erste Element. Und in dieser verketteten Liste wir haben vier Knoten. Jeder Knoten ist ein großes Feld. Im größeren Feld innerhalb der großen Feld der ganzzahlige Teil. Und dann haben wir eine Zeigerteil. 

Diese Boxen sind nicht gezeichnet Maßstab, weil, wie groß ist eine ganze Zahl in Bytes? Wie groß ist jetzt? Four. Und wie groß ist ein Zeiger? Four. Also wirklich, wenn wir zu zeichnen waren dies, um beide Boxen zu skalieren würde die gleiche Größe haben. In diesem Fall einfügen möchten wir etwas in den verketteten Liste. So kann man hier unten sehen wir Einsetzen Wir durchqueren fünf durch die verknüpften Liste finden, wo fünf geht, und setzen Sie sie. 

Lassen Sie uns brechen, dass die nach unten und gehen ein wenig langsamer. Ich werde in den Vorstand verweisen. So haben wir unsere fünf Knoten, die wir in mallocs erstellt haben. Warum ist jeder lachen? Nur ein Scherz. OK. Also haben wir fünf malloced. Wir haben diesen Knoten erstellt woanders. Wir haben es bereit zu gehen. Wir starten an der Vorderseite des unsere Liste mit zwei. Und wir einfügen wollen in einer sortierten Mode. 

Also, wenn wir sehen, zwei und wir setzen wollen in fünf, was tun wir, wenn wir sehen, etwas weniger als bei uns? Was? Wir wollen in diese einfügen fünf verketteten Liste, halten sie sortiert. Wir sehen die Nummer zwei. Also, was tun wir? Marcus? 

ZIELGRUPPE: Rufen Sie den Zeiger zu dem nächsten Knoten. 

JASON HIRSCHHORN: Und warum tun gehen wir in die nächste? 

ZIELGRUPPE: Weil es die nächste Knoten in der Liste. Und wir wissen nur, dass andere Lage. 

JASON HIRSCHHORN: Und fünf ist größer als zwei, insbesondere. Weil wir es sortierten halten wollen. So fünf größer als zwei ist. So bewegen wir uns auf das nächste. Und jetzt kommen wir vier. Und was passiert, wenn wir vier zu erreichen? 

Fünf größer als vier ist. So können wir weitermachen. Und jetzt sind wir um sechs. Und was machen wir an sechs sehen? Ja, Carlos? 

ZIELGRUPPE: Sechs größer als fünf ist. 

JASON HIRSCHHORN: Sechs ist größer als fünf ist. Also das ist, wo wir wollen einfügen fünf. Doch bedenken Sie, dass, wenn wir nur einen Zeiger hier - das ist unser extra Zeiger, ist Fahren Sie durch die Liste. Und wir sind zu sechs zeigt. Wir haben den Überblick über das, was verloren kommt vor sechs. Also, wenn wir etwas einfügen möchten Diese Liste halten es sortiert, wir wahrscheinlich brauchen, wie viele Zeiger? 

ZIELGRUPPE: Zwei. 

JASON Hirschhorn: Zwei. Einer, den Überblick über die aktuell zu halten eins und eins, um zu verfolgen die vorherige. Dies ist nur eine einfach verkettete Liste. Es geht nur eine Richtung. Wenn wir eine doppelt verknüpfte Liste, wo alles war auf die Sache zeigen nach ihm und der Sache, bevor es dann würden wir nicht brauchen, um das zu tun. Aber in diesem Fall wollen wir nicht verlieren verfolgen, was vor uns im Falle kam wir brauchen, um fünf irgendwo einfügen in der Mitte. Sagen wir, wir waren neun Einfügen. Was würde passieren, wenn bekamen wir zu acht? 

ZIELGRUPPE: Sie würden zu haben, bekommen, dass Nullpunkt. Anstatt Nullpunkt müss um ein Element hinzufügen und dann haben es neun verweisen. 

JASON Hirschorn: Genau. So bekommen wir acht. Wir erreichen das Ende der Liste, weil dies zeigt auf null. Und jetzt, anstatt es zu zeigen null haben wir es zu unserem neuen Knoten zeigen. Und wir setzen Sie den Mauszeiger in In unserem neuen Knoten auf null. Hat jemand irgendwelche Fragen haben, zum Einfügen? Was, wenn ich kümmere mich nicht um , die Liste sortiert? 

ZIELGRUPPE: Halten Sie es an die Anfang oder das Ende. 

JASON Hirschorn: Halten Sie es an der Beginn oder das Ende. Welche sollen wir tun? Bobby? Warum das Ende? 

ZIELGRUPPE: Weil der Anfang ist bereits gefüllt. 

JASON Hirschorn: OK. Der Anfang ist bereits gefüllt. Wer will gegen Bobby streiten. Marcus. 

ZIELGRUPPE: Nun möchten Sie wahrscheinlich kleben Sie es am Anfang, weil ansonsten, wenn du es am das Ende Sie müssten durchqueren die gesamte Liste. 

JASON Hirschorn: Genau. Also, wenn wir über Laufzeit denken, die Laufzeit des Einsetzens am Ende n würde sein, die Größe davon. Was ist die große O-Laufzeit des Einsetzens am Anfang? Constant Zeit. Also, wenn Sie nicht über das Halten kümmern etwas sortiert, viel besser, nur legen am Anfang dieser Liste. Und daß in konstanter Zeit durchgeführt werden. 

OK. Weiter Betrieb zu finden, die andere - wir dies als Such formuliert habe. Aber wir werden schauen durch die verketteten Liste für ein Objekt. Ihr habt Code für gesehen suchen, bevor in der Vorlesung. Aber wir haben irgendwie nur tat es mit einzufügen, oder zumindest das Einfügen etwas sortiert. Sie schauen durch, gehen Knoten für Knoten, bis Sie die Nummer, die Sie finden suche. Was passiert, wenn Sie zu erreichen das Ende der Liste? Sagen wir, ich bin für neun und ich erreichen das Ende der Liste. Was machen wir? 

ZIELGRUPPE: Zurück falsch? 

JASON Hirschorn: Zurück falsch. Wir fanden es nicht. Wenn Sie das Ende der Liste zu erreichen und Sie hat die Nummer, du bist nicht zu finden sucht, es ist nicht dort. Haben Sie Fragen zu finden? Wenn dies eine sortierte Liste, was wäre anders für unsere Suche? Ja. 

ZIELGRUPPE: Es wäre der erste Wert finden das ist größer als der Sie suchen und dann wieder falsch. 

JASON Hirschorn: Genau. Also, wenn es eine sortierte Liste, wenn wir bekommen etwas, das größer ist als das, was wir suchen, haben wir nicht brauchen fahren Sie bis zum Ende der Liste. Wir können an diesem Punkt return false weil wir nicht gehen, um es zu finden. Die Frage ist nun, über die wir gesprochen haben halten verkettete Listen sortiert, halten sie unsortiert. Das wird etwas sein, du bist wahrscheinlich zu denken zu müssen Problem bei der Codierung eingestellt, wenn Sie fünf wählen Sie eine Hash-Tabelle mit separater Verkettung Ansatz, der wir werden darüber später reden. 

Aber ist es das wert, um die Liste zu halten sortiert und dann in der Lage, vielleicht haben schneller Suchanfragen? Oder ist es besser, schnell einfügen etwas in konstanter Laufzeit, aber dann haben mehr zu suchen? Das ist ein Kompromiss Recht gibt, die Sie erhalten, zu entscheiden, was ist besser geeignet für Ihr spezielles Problem. Und es ist nicht unbedingt ein absolut richtige Antwort. Aber es ist sicherlich eine Entscheidung, die Sie bekommen zu machen, und wahrscheinlich gut zu verteidigen dass in, sagen wir, ein oder zwei Kommentar, warum Sie einen über den anderen gewählt haben. 

Schließlich löschen. Wir haben gesehen, zu löschen. Es ist ähnlich wie die Suche. Wir schauen für das Element. Sagen wir, wir versuchen zu löschen, sechs. So finden wir hier sechs. Die Sache, die wir haben, um sicherzustellen, dass wir machen zu tun ist, dass alles, was auf den Hinweis sechs - wie wir sehen, in Schritt zwei hier unten - was auch immer zu sechs Bedürfnisse auf den Hinweis ist überspringen sechs und jetzt geändert werden was auch immer sechs zeigen wird. Wir wollen nicht immer den Rest der Waisen unserer Liste durch das Vergessen zu setzen, dass vorherige Zeiger. Und dann manchmal, je auf dem Programm, werden sie einfach diesen Knoten vollständig zu löschen. Manchmal werde zurückkehren möchten, dass Sie der Wert, der in diesem Knoten ist. Also das ist, wie das Löschen funktioniert. Sie haben Fragen zu löschen? 

ZIELGRUPPE: Also, wenn Sie gehen, um zu löschen es würde Sie einfach frei, weil vermutlich wurde es malloced? 

JASON Hirschorn: Wenn Sie sich befreien wollen etwas, das genau richtig, und Sie ist malloced es. Sagen wir, wir, diesen Wert zurückkehren wollte. Wir könnten zurück sechs und dann frei dieser Knoten und Anruf ist kostenlos auf sie. Oder würden wir wahrscheinlich frei zuerst anrufen und dann wieder sechs. 

OK. Also machen wir weiter zu praktizieren Codierung. Wir werden drei Funktionen zu codieren. Die erste heißt insert_node. Sie haben also Code, den ich per E-Mail Sie und Wenn Sie beobachten diese später Sie den Code in linked.c zugreifen können CS50 auf der Website. Aber in linked.c, es gibt einige Skeleton-Code, der bereits ist wurde für Sie geschrieben. Und dann gibt es ein paar Funktionen Sie brauchen, um zu schreiben. 

Zuerst sind wir zu gehen insert_node schreiben. Und was tut insert_node heißt fügt eine ganze Zahl. Und Sie geben dem ganzen Zahl sind in einer verketteten Liste. Und vor allem, Sie müssen , um die Liste sortiert halten vom kleinsten zum größten. Auch können Sie nicht wollen, Duplikate einfügen. Schließlich, wie Sie sehen insert_node gibt einen bool. Also man eigentlich damit der Benutzer weiß ob der Einsatz war oder nicht, durch Rücksendung wahr oder falsch ist erfolgreich. Am Ende des Programms - und für diese Phase brauchen Sie nicht sich um nichts kümmern zu befreien. Also alles, was Sie tun, ist, die einen Integer und Einfügen in eine Liste. 

Das ist, was ich frage Sie jetzt noch tun. Auch in der linked.c, die Sie alle haben, ist das Skelett-Code. Und Sie sollten auf den Grund sehen die Probe Funktionsdeklaration. Doch bevor er in Codierung es in C, ich sehr empfehlen Ihnen, gehen durch die Schritte, die wir schon seit Üben pro Woche. Wir haben schon durchgemacht ein Bild davon. So sollten Sie ein gewisses Verständnis haben wie das funktioniert. Aber ich möchte Sie ermutigen zu schreiben einige Pseudocode vor dem Tauchen in. Und wir gehen über Pseudocode als Gruppe. Und dann, wenn Sie geschrieben haben, Ihre Pseudocode, und wenn wir geschrieben haben, unsere Pseudocode als Gruppe, können Sie gehen in Codierung in C 

Wie ein Heads-up, das insert_node Funktion ist wahrscheinlich der schwierigste von die drei werden wir schreiben, weil ich hinzugefügt einige zusätzliche Einschränkungen Ihre Programmierung, insbesondere die du gehst nicht zu einem einfügen Duplikate und dass die Liste sollte sortierten bleiben. Das ist also eine nicht-triviale Programm dass Sie zu codieren. Und warum nimmst du nicht fünf vor sieben Minuten, nur um auf die Arbeit zu bekommen Pseudocode und der Code. Und dann werden wir beginnen gehen als Gruppe. Auch, wenn Sie irgendwelche Fragen haben, nur heben Sie Ihre Hand, und ich werde kommen um. . 

Wir tun dies in der Regel auch - oder ich weiß nicht explizit sagen mit Menschen zu arbeiten. Aber offensichtlich habe ich sehr empfehlen Ihnen, Wenn Sie Fragen haben, die fragen, Nachbar neben Ihnen sitzt oder sogar mit jemandem arbeiten sonst, wenn Sie wollen. Dies muss nicht ein Individuum zu sein Stumm Aktivität. 

Lassen Sie uns mit dem Schreiben beginnen einige Pseudocode auf dem Board. Wer kann mir die erste Zeile geben Pseudocode für dieses Programm? Für diese Funktion nicht - insert_node. Alden? 

ZIELGRUPPE: Also das erste, was ich tat, war erstellen Sie einen neuen Zeiger auf die Knoten und ich initialisiert wird der gleiche Zeige Sache, die Liste verweist. 

JASON Hirschorn: OK. So erstellen Sie einen neuen Zeiger sind die Liste nicht in den Knoten. 

ZIELGRUPPE: Richtig. Ja. 

JASON Hirschorn: OK. Und dann, was wollen wir tun? Was ist danach? Was ist mit dem Knoten? Wir haben nicht einen Knoten. Wir müssen nur einen Wert. Wenn wir einen Knoten einfügen wollen, was wir tun müssen, bevor wir können sogar tun denke über Einlegen? 

ZIELGRUPPE: Oh, sorry. Wir müssen, um Platz für einen Knoten malloc. 

JASON Hirschorn: Excellent. Lassen Sie uns - OK. Nicht erreichen können, dass hoch. OK. Wir werden nach unten gehen und dann wir sind mit zwei Spalten. Ich kann nicht gehen, dass - OK. Erstellen Sie einen neuen Knoten. Sie können einen anderen Zeiger zu erstellen zur Liste oder können Sie einfach Liste, wie sie ist. Sie nicht wirklich brauchen, um das zu tun. 

So schaffen wir einen neuen Knoten. Große. Das ist, was wir zuerst tun. Was kommt als nächstes? 

ZIELGRUPPE: Warten. Sollten wir einen neuen Knoten jetzt oder sollten wir warten, um sicherzustellen, dass es gibt keine Duplikate des Knotens auf der Liste, bevor wir es schaffen? 

JASON Hirschorn: Gute Frage. Halten wir das für später, weil die Mehrheit der Zeit werden wir die Schaffung ein neuer Knoten. Also werden wir das hier zu halten. Aber das ist eine gute Frage. Wenn wir es schaffen und wir finden ein Duplikat, was sollte wir vor der Rückkehr tun? 

ZIELGRUPPE: Befreien sie. 

JASON Hirschorn: Ja. Wahrscheinlich befreien sie. OK. Was machen wir, nachdem wir tun erstellen Sie einen neuen Knoten? Annie? 

Gemeinde: Wir haben das Anzahl in den Knoten? 

JASON Hirschorn: Genau. Wir setzen die Zahl - wir malloc Raum. Ich werde dabei belassen alle als eine Zeile. Aber Sie haben Recht. Wir malloc Leerzeichen und dann wir setzen die Zahl in. Wir können sogar den Zeiger gesetzt Teil davon auf null. Das ist genau richtig. Und was ist dann danach? Wir zeichnete dieses Bild auf dem Brett. Also, was tun wir? 

ZIELGRUPPE: Wir gehen durch die Liste. 

JASON Hirschorn: Gehen Sie durch die Liste. OK. Und was machen wir prüfen in jedem Knoten. Kurt, was machen wir überprüfen für jeden Knoten? 

ZIELGRUPPE: Schauen Sie, ob der n-Wert von dass der Knoten größer ist als der Wert n ist der Knoten. 

JASON Hirschorn: OK. Ich werde tun, - ja, OK. So ist es n - Ich werde sagen, wenn Wert größer ist als dieser Knoten, dann was machen wir? 

ZIELGRUPPE: Nun, dann fügen wir die Sache richtig davor. 

JASON Hirschorn: OK. So dass, wenn er größer als dieser ist, dann wollen wir einfügen. Aber wir wollen es richtig eingeben möchten weil wir auch sein müsste Verfolgung, dann, von dem, was vorher war. So legen Sie vor. Also haben wir wohl etwas verpasst früher. Wir müssen wahrscheinlich werden halten verfolgen, was los ist. Aber wir werden es wieder zu bekommen. Also, was Wert ist kleiner als? Kurt, was tun wir, wenn Wert kleiner als? 

ZIELGRUPPE: Dann einfach weiter es sei denn, es ist die letzte. 

JASON Hirschhorn: Ich mag diese. So gehen Sie zum nächsten Knoten. Es sei denn, es ist die letzte - Wir sind wahrscheinlich, dass für die Überprüfung im Sinne einer Bedingung. Aber ja, nächsten Knoten. Und das ist immer zu niedrig, so dass wir hier über zu bewegen. Aber wenn - kann jeder sehen das? Wenn wir gleich sind, was sollen wir tun? Wenn der Wert versuchen wir einfügen ist gleich Wert dieses Knotens? Ja? 

ZIELGRUPPE: [unverständlich]. 

JASON Hirschorn: Ja. Angesichts dieser - Marcus ist richtig. Wir könnten vielleicht getan haben etwas anderes. Aber da wir sie geschaffen haben, ist hier wir sollten zu befreien und dann zurückkehren. Oh Junge. Ist das besser? Wie ist das? OK. Kostenlose und dann, was zu tun wir zurückzukehren, [unverständlich]? OK. Sind wir etwas fehlt? Also, wo sind wir den Überblick des Standes der Knoten? 

ZIELGRUPPE: Ich denke, es gehen würde nach einen neuen Knoten. 

JASON Hirschorn: OK. Also am Anfang werden wir wahrscheinlich - ja, können wir einen Zeiger auf eine neue erstellen Knoten, wie eine vorherige Knotenzeiger und eine aktuelle Knoten-Zeiger. Lassen Sie uns also, dass hier einfügen. Neues aktuellen und früheren Zeiger auf die Knoten. Aber wenn wir diese Zeiger einstellen? Wo tun wir das in dem Code? Jeff? 

ZIELGRUPPE: - Wert Bedingungen? 

JASON Hirschorn: Welche ein im Besonderen? 

ZIELGRUPPE: Ich bin nur verwirrt. Wenn der Wert größer ist als dieser Knoten, heißt das nicht, dass Sie gehen wollen zu dem nächsten Knoten? 

JASON HIRSCHHORN: Also wenn unsere Wert größer als der Wert dieses Knotens. 

ZIELGRUPPE: Ja, dann würden Sie wollen weiter auf der ganzen Linie, oder? 

JASON HIRSCHHORN: Richtig. Also haben wir es hier nicht einfügen. Wenn weniger als diese Knoten, dann gehen wir zum nächsten Knoten - oder dann werden wir vor einfügen. 

ZIELGRUPPE: Warten Sie, was das ist Knoten und die ist Wert? 

JASON HIRSCHHORN: Gute Frage. Wert je dieser Funktionsdefinition ist das, was uns gegeben. So Wert ist die Anzahl uns gegeben. So dass, wenn der Wert kleiner als dieser ist Knoten, brauchen wir Zeit, um einzufügen. Wenn der Wert größer ist als dieser Knoten, gehen wir in den nächsten Knoten. Und zurück auf die ursprüngliche Frage, obwohl, wo - 

ZIELGRUPPE: Wenn Wert größer ist als dieser Knoten. 

JASON HIRSCHHORN: Und so was tun wir hier? Süße. Das ist richtig. Ich werde einfach schreiben Update Zeiger. Aber ja, mit der aktuellen Sie würde zu aktualisieren Punkt zum nächsten. Alles andere uns fehlt? Also werde ich das hier schreibe Code in gedit. Und während ich dies tun, können Sie eine haben kann, paar Minuten auf den Code arbeiten dies in C. 

So habe ich den Pseudocode-Eingang. Ein kurzer Hinweis, bevor wir loslegen. Wir können möglicherweise nicht vollständig sein beenden diese in allen drei dieser Funktionen. Es ist richtig, Lösungen zu dass ich an euch eine E-Mail aus nach Abschnitt, und es wird auf CS50.net veröffentlicht. Also ich weiß nicht Sie ermutigen schau auf den Abschnitten. Ich ermutige Sie, diese auf versuchen Sie Ihr zu besitzen, und dann mit dem die Praxis Probleme, Ihre Antworten zu überprüfen. Diese wurden alle entwickelt, um eng betreffen und sich an das, was Sie haben sich auf das Problem Satz zu tun. Also habe ich Sie ermutigen, dies zu üben auf eigene Faust und dann mit dem Code überprüfen Sie Ihre Antworten. Weil ich will auf dem Weg zu hacken Tabellen zu einem bestimmten Zeitpunkt in der Sektion. So könnten wir nicht über allem. Aber wir werden jetzt so viel wir können. 

OK. Lassen Sie uns beginnen. Asam, wie schaffen wir einen neuen Knoten? 

ZIELGRUPPE: Sie konstruieren *. 

JASON HIRSCHHORN: Also wir haben, dass hier oben. Oh, sorry. Sie sagten struct *. 

ZIELGRUPPE: Und dann [? Art?] Knoten-oder c-Knoten. 

JASON HIRSCHHORN: OK. Ich werde es nennen new_node so können wir im Einklang bleiben. 

ZIELGRUPPE: Und Sie setzen wollen, dass den Kopf, den ersten Knoten. 

JASON HIRSCHHORN: OK. So, jetzt diese zeigt auf - so dass diese noch nicht einen neuen Knoten erstellt. Dies ist nur die Zeige ersten Knoten in der Liste. Wie erstelle ich einen neuen Knoten? Wenn ich Platz für einen neuen Knoten erstellen. Malloc. Und wie groß? 

ZIELGRUPPE: Die Größe der Struktur. 

JASON HIRSCHHORN: Die Größe der Struktur. Und was die Struktur genannt? 

ZIELGRUPPE: Knoten? 

JASON HIRSCHHORN: Knoten. So malloc (sizeof (Knoten)); gibt uns Raum. Und ist diese Linie - eine Sache falsch ist auf dieser Linie. New_node ist ein Zeiger auf eine Struktur? Das ist ein generischer Name. Was ist das - Knoten, genau. Es ist ein Knoten *. Und was machen wir nach rechts zu tun malloc wir etwas, Asan? Was ist das erste, was wir tun? Was, wenn es nicht funktioniert? 

ZIELGRUPPE: Oh, prüfen, ob es zeigt auf den Knoten? 

JASON HIRSCHHORN: Genau. Also, wenn Sie new_node gleich equals null, was tun wir? Dies gibt einen bool, diese Funktion. Genau. Sieht gut aus. Alles, was es hinzufügen? Wir werden die Dinge am Ende hinzufügen. Aber so weit, dass sieht gut aus. Neues aktuellen und früheren Zeiger. Michael, wie kann ich dies tun? 

ZIELGRUPPE: Sie müssten um einen Knoten zu machen *. Man müsste man nicht machen für new_node aber für die Knoten haben wir bereits. 

JASON HIRSCHHORN: OK. So der aktuelle Knoten sind wir auf. Ich werde diese curr anrufen. Gut. Wir haben beschlossen, die wir behalten wollen zwei, weil wir wissen müssen was vor ihm. Was bekommen sie initialisiert? 

ZIELGRUPPE: Ihr Wert in unserer Liste. 

JASON HIRSCHHORN: Also, was ist der erste, was auf unserer Liste? Oder wie können wir wissen, wo die Anfang unserer Liste ist? 

ZIELGRUPPE: Ist es nicht übergeben in die Funktion? 

JASON HIRSCHHORN: Richtig. Es wurde hier weitergeleitet. Also, wenn es in die Funktion übergeben, die Anfang der Liste, was sollen wir Strom gleich gesetzt? 

ZIELGRUPPE: Liste. 

JASON HIRSCHHORN: Liste. Das ist genau richtig. Jetzt die Adresse hat der Anfang unserer Liste. Und was ist mit vorherigen? 

ZIELGRUPPE: Liste minus eins? 

JASON HIRSCHHORN: Es gibt nichts vor ihr. Also, was können wir tun, um nichts zu bedeuten? 

ZIELGRUPPE: Null. 

JASON HIRSCHHORN: Ja. Das klingt wie eine gute Idee. Perfect. Danke. Gehen Sie durch die Liste. Konstantin, wie lange werden wir um durch die Liste zu gehen? 

ZIELGRUPPE: bis wir null. 

JASON HIRSCHHORN: OK. Also, wenn, während, for-Schleife. Was machen wir? 

ZIELGRUPPE: Vielleicht eine for-Schleife? 

JASON HIRSCHHORN: Wir tun eine for-Schleife. OK. 

ZIELGRUPPE: Und wir sagen, für - bis der aktuelle Zeiger nicht gleich null. 

JASON HIRSCHHORN: Also, wenn wir wissen, dass die Zustand, wie können wir schreiben eine Schleife Basis weg von diesem Zustand. Welche Art von einer Schleife sollten wir verwenden? 

ZIELGRUPPE: Während. 

JASON HIRSCHHORN: Ja. Das macht mehr Sinn, auf der Basis ab von dem, was Sie gesagt haben. Wenn wir wollen, nur um in die wir gehen, es würde weiß nur, dass die Sache, wäre es Sinn, eine while-Schleife zu tun. Während aktuelle ist nicht gleich null, wenn der Wert weniger als dieses Knotens. Akshar, gib mir diese Zeile. 

ZIELGRUPPE: Wenn Strom> n n kleiner als der Wert. Oder umgekehrt, dass. Schalter, der Halterung. 

JASON HIRSCHHORN: Es tut uns leid. 

ZIELGRUPPE: Ändern Sie die Halterung. 

JASON HIRSCHHORN: Also, wenn es größer als der Wert. Denn das ist verwirrend mit der Kommentar oben, werde ich das tun. Aber ja. Wenn unser Wert kleiner als das ist Knoten, was tun wir? Oh. Ich habe es hier richtig. Legen Sie vor. OK. Wie tun wir das? 

ZIELGRUPPE: Ist es immer noch zu mir? 

JASON HIRSCHHORN: Ja. 

ZIELGRUPPE: Sie - new_node-> next. 

JASON HIRSCHHORN: Also, was ist dass würde gleich? 

ZIELGRUPPE: Es ist die Gleichstrom gehen. 

JASON HIRSCHHORN: Genau. Und so ist die andere - was wir sonst noch brauchen, um zu aktualisieren? 

ZIELGRUPPE: Prüfen Sie, ob Vergangenheit gleich null. 

JASON HIRSCHHORN: Wenn prev - Wenn prev gleich null. 

PUBLIKUM: Das bedeutet, es wird bis der Kopf zu werden. 

JASON HIRSCHHORN: Das Mittel es ist der Kopf geworden. Also, was tun wir? 

ZIELGRUPPE: Wir tun new_node Kopf entspricht. 

JASON HIRSCHHORN: Kopf new_node entspricht. Und warum hier aus fahren, nicht aufgelistet? 

ZIELGRUPPE: Weil Kopf ist ein weltweit Variable, die der Ausgangspunkt ist. 

JASON HIRSCHHORN: Süße. OK. Und - 

ZIELGRUPPE: Dann können Sie sonst noch prev-> gleich neben new_node. Und dann true zurück. 

JASON HIRSCHHORN: Wo setzen wir new_node Ende? 

ZIELGRUPPE: Ich würde - Ich, dass an den Start. 

JASON HIRSCHHORN: Also welche Linie? 

ZIELGRUPPE: Nach der if-Anweisung prüft, ob es bekannt. 

JASON HIRSCHHORN: Gleich hier? 

ZIELGRUPPE: Ich würde tun new_node-> n Wert entspricht. 

JASON HIRSCHHORN: Klingt gut. Wahrscheinlich macht es Sinn - wir nicht müssen wissen, welche Liste sind wir auf weil wir nur den Umgang mit einer Liste. Also eine bessere Funktion Erklärung für das ist einfach nur loszuwerden, diese und ganz einfach einfügen ein Wert in den Kopf. Wir brauchen nicht einmal zu wissen, Liste, welche wir in. Aber ich werde es jetzt zu halten und dann ändern Sie es auf die Aktualisierung Die Folien und Code. Also das sieht gut aus für heute. Wenn der Wert -, die diese Linie tun kann? Wenn - was tun wir hier, Noah. 

ZIELGRUPPE: Wenn Wert größer ist als curr-> n - 

JASON HIRSCHHORN: Wie gehen wir zum nächsten Knoten? 

ZIELGRUPPE: Curr-> n gleich new_node. 

JASON HIRSCHHORN: Also n welcher Teil der Struktur? Die ganze Zahl ist. Und new_node ist ein Zeiger zu einem Knoten. Also, welche Teil der curr sollten wir aktualisieren? N Wenn nicht, was ist dann der andere Teil? Noah, was ist der andere Teil. 

ZIELGRUPPE: Oh, das nächste. 

JASON HIRSCHHORN: Next, genau. Genau. Als nächstes ist der richtige. Und was wir sonst noch brauchen zu aktualisieren, Noah? 

ZIELGRUPPE: Die Zeiger. 

JASON HIRSCHHORN: Also wir aktualisiert Strom. 

ZIELGRUPPE: Vorschau-> next. 

JASON HIRSCHHORN: Ja. OK, wir unterbrechen. Wer kann uns hier helfen? Manu, was sollen wir tun? 

ZIELGRUPPE: Du musst gesetzt sie gleich curr-> next. Aber wissen, dass vor der vorherigen Zeile. 

JASON HIRSCHHORN: OK. Sonst noch was? Akshar. 

ZIELGRUPPE: Ich glaube nicht, dass Sie soll curr-> next ändern. Ich denke, man soll curr Gleichen erleben curr-> neben an den nächsten Knoten zu gehen. 

JASON HIRSCHHORN: Also sorry, wo? Auf welcher Linie? Diese Linie? 

ZIELGRUPPE: Ja. Machen curr gleich curr-> next. 

JASON HIRSCHHORN: Also das ist richtig denn Strom ist ein Zeiger auf einen Knoten. Und wir wollen, dass es mit dem nächsten Punkt Knoten, was immer noch wies auf. Curr selbst hat eine nächste. Aber wenn wir curr.next aktualisieren wir würde die Aktualisierung des eigentlichen Noten selbst nicht, wo diese Zeiger deutete. Was ist mit dieser Linie, aber. Avi? 

ZIELGRUPPE: Vorschau-> next gleich akt. 

JASON HIRSCHHORN: Also wieder zurück, wenn ein Zeiger auf einen Knoten, der nächste ist prev-> das Ist Zeiger im Knoten. Also das wäre eine Aktualisierung Zeiger in einem Knoten zu akt. Wir wollen nicht zu aktualisieren ein Zeiger in einem Knoten. Wir wollen die Aktualisierung von früheren. Also, wie machen wir das? 

ZIELGRUPPE: Es wäre nur prev werden. 

JASON HIRSCHHORN: Richtig. Prev ist ein Zeiger zu einem Knoten. Jetzt werden wir ändern, dass es ein neue Zeiger auf einen Knoten. OK wir uns nach unten. Schließlich kann diese letzte Bedingung. Jeff, was tun wir hier? 

ZIELGRUPPE: Wenn Wert gleich curr-> n. 

JASON HIRSCHHORN: Es tut uns leid. Ach du meine Güte. Was? Value == curr-> n. Was machen wir? 

ZIELGRUPPE: Sie würden unsere new_node befreien, und dann würden Sie false zurück. 

JASON HIRSCHHORN: Das ist, was wir bisher geschrieben. Hat jemand etwas haben hinzuzufügen, bevor wir? OK. Versuchen wir es. Die Kontrolle kann das Ende erreichen eines nicht-Leerfunktion. Avi, was ist los? 

ZIELGRUPPE: Sind Sie eigentlich Rückkehr setzen wahr außerhalb der while-Schleife? 

JASON HIRSCHHORN: Ich weiß es nicht. Willst du mich auf? 

ZIELGRUPPE: Macht nichts. Nein. 

JASON HIRSCHHORN: Akshar? 

ZIELGRUPPE: Ich denke, Sie bedeutete return false setzen am Ende der while-Schleife. 

JASON HIRSCHHORN: Also, wo Sie wollen, dass es gehen? 

ZIELGRUPPE: Wie außerhalb der while-Schleife. Also, wenn Sie die while-Schleife verlassen, dass Mittel dass Sie das Ende erreicht haben, und nichts passiert ist. 

JASON HIRSCHHORN: OK. Also, was tun wir hier? 

ZIELGRUPPE: Sie return false auch dort. 

JASON HIRSCHHORN: Oh, wir tun es in beiden Orten? 

ZIELGRUPPE: Ja. 

JASON HIRSCHHORN: OK. Sollen wir gehen? Ach du meine Güte. Es tut mir leid. Ich entschuldige mich für den Bildschirm. Es ist eine Art ausgeflippt auf uns. So wählen Sie eine Option. Zero, per Code, beendet das Programm. Man legt etwas. Lassen Sie uns legen Sie drei. Das Insert war nicht erfolgreich. Ich werde zum ausdrucken. Ich habe nichts. OK. Vielleicht war das nur ein Zufall. Legen Sie ein. Nicht erfolgreich. OK. Lassen Sie uns wirklich schnell durch GDB laufen zu prüfen, was los ist. 

Angemeldet gdb. / Der Name des Programm bringt uns in GDB. Ist das viel zu handhaben? Die blinkende? Wahrscheinlich. Schließen Sie die Augen und nehmen Sie sich etwas tief atmet, wenn Sie müde es zu betrachten. Ich bin in der GDB. Was ist das erste, was ich tun in GDB? Wir müssen herausfinden, was ist denn hier los. Mal sehen. Wir haben sechs Minuten, um Figur heraus, was los ist. Brechen Haupt. Und was kann ich tun? Carlos? Führen. OK. Wählen wir eine Option. Und was bedeutet N tun? Weiter. Ja. 

ZIELGRUPPE: Hast du nicht erwähnen - hast du nicht gesagt, dass der Kopf, es war zu Beginn auf null initialisiert. Aber ich dachte, Sie sagten, das war OK. 

JASON HIRSCHHORN: Lass uns gehen - lassen Sie uns in GDB, und dann werden wir wieder zurück. Aber es klingt wie Sie bereits einige Ideen, was los ist. Deshalb wollen wir etwas einfügen. OK. Wir haben einfügen. Bitte geben Sie eine int. Wir werden drei einfügen. Und dann bin ich auf dieser Linie. Wie gehe ich mit dem Debuggen beginnen der Einsatz bekannte Funktion? Ach du meine Güte. Das ist eine Menge. Ist das ausgeflippt viel? 

ZIELGRUPPE: Oh, es starb. 

JASON HIRSCHHORN: Ich habe zog es heraus. OK. 

ZIELGRUPPE: Vielleicht ist es die andere Ende des Drahtes ist. 

JASON HIRSCHHORN: Wow. Also unter dem Strich - was hast du gesagt? 

ZIELGRUPPE: Ich sagte, die Ironie der technischen Schwierigkeiten in dieser Klasse. 

JASON HIRSCHHORN: Ich weiß. Wenn ich nur die Kontrolle über diesen Teil. [Unverständlich] Das klingt großartig. Warum gehst du nicht anfangen, über Jungs das, was wir falsch gemacht haben könnte, und wir werden wieder in 90 Sekunden sein. 

Avica, werde ich Sie fragen, wie es weiter gehen innerhalb insert_node es zu debuggen. Also das ist, wo wir uns das letzte aufgehört hat. Wie kann ich in insert_node gehen, Avica, zu prüfen, was ist los? Welche GDB-Befehl? Pause würde mich nicht im Inneren. Hat Marquise wissen? 

PUBLIKUM: Was? 

JASON HIRSCHHORN: Was GDB Befehl Ich nutzen, um innerhalb dieser Funktion gehen? 

ZIELGRUPPE: Step? 

JASON HIRSCHHORN: über Schritt S. Das nimmt mich hinein. OK. New_node mallocing etwas Platz. Das alles sieht aus wie sein Gehen. Betrachten wir new_node. Es habe einige Speicheradresse. Lassen Sie uns - das ist alles richtig. Also alles scheint hier werden ordnungsgemäß. 

PUBLIKUM: Was ist der Unterschied zwischen P und Display? 

JASON HIRSCHHORN: P steht für den Druck. Und so Sie fragen, was ist der Unterschied zwischen das und das? In diesem Fall nichts. Aber im Allgemeinen gibt es einige Unterschiede. Und Sie sollten in der GDB-Handbuch nachschlagen. Aber in diesem Fall nichts. Wir neigen dazu, drucken zu können, obwohl, weil wir nicht viel mehr tun müssen, als drucken Sie einen einzelnen Wert. 

OK. So sind wir auf der Linie 80 von unseren Code, Einstellung Knoten * curr gleich Liste. Lassen Sie uns ausdrucken akt. Sie ist gleich-Liste. Süße. Warten. Es ist gleich etwas. Das scheint nicht richtig. Dort gehen wir. Es ist, weil in GDB, rechts, wenn es ist die Linie, die Sie an ihm sind noch nicht ausgeführt. Sie wollen also tatsächlich eingeben müssen neben die Linie ausführen bevor man seine Ergebnisse. So, hier sind wir. Wir haben gerade diese Zeile ausgeführt, vorherige gleich null. Also noch einmal, wenn wir drucken früheren wir werden nichts sehen seltsam. Aber wenn wir tatsächlich auszuführen, dass Linie, dann werden wir sehen, dass diese Linie gearbeitet. 

So haben wir akt. Die sind beide gut. Right? Jetzt werden wir auf dieser Linie sind hier richtig. Während curr nicht gleich null. Nun, was macht curr gleich? Wir haben gerade sah es null erreicht. Wir druckte es aus. Ich werde es wieder heraus zu drucken. So ist die while-Schleife werde ausführen? 

ZIELGRUPPE: Nein 

JASON HIRSCHHORN: Also, wenn ich getippt Zeile sehen Sie, sprangen wir den ganzen Weg bis auf den Boden, return false. Und dann werden wir return false und gehen Sie zurück zu unserem Programm und schließlich ausdrucken, wie wir sahen, das Insert war nicht erfolgreich. Also, jemand irgendwelche Ideen, was haben wir tun müssen, um dieses Problem beheben? Ich werde warten, bis ich sehe, ein paar Hände nach oben. Wir haben nicht diese auszuführen. Denken Sie daran, dies war der erste was wir taten. Ich werde nicht um ein paar zu tun. Ich werde ein paar zu tun. Weil ein Paar bedeutet zwei. Ich werde für mehr als zwei warten. 

Die erste Insertion, curr, Standardmäßig ist gleich null. Und nur diese Schleife führt wenn curr ist nicht null. Also, wie kann ich um dieses? Ich sehe drei Händen. Ich werde für mehr als drei warten. Marcus, was denken Sie? 

ZIELGRUPPE: Nun, wenn Sie es brauchen mehr als einmal auszuführen, müssen Sie nur ändern Sie es in einer do-while-Schleife. 

JASON HIRSCHHORN: OK. Will, dass unser Problem zu lösen, wenn? 

ZIELGRUPPE: In diesem Fall nicht, weil der die Tatsache, dass die Liste leer ist. Also dann haben Sie wahrscheinlich nur brauchen, um hinzuzufügen eine Erklärung, dass, wenn die Schleife beendet dann müssen Sie am Ende der sein die Liste, an welcher Stelle Sie kann nur einzuschieben. 

JASON HIRSCHHORN: Ich mag diese. Das macht Sinn. Wenn die Schleife beendet - denn es wird hier false zurück. Also, wenn die Schleife beendet, dann sind wir bei das Ende der Liste, oder vielleicht die Beginn einer Liste, wenn es nichts in es, was das gleiche wie das Ende. So, jetzt einfügen möchten wir hier etwas. Und wie funktioniert der Code aussehen, Marcus? 

ZIELGRUPPE: Wenn Sie bereits den Knoten bekam malloced, die Sie gerade sagen konnte new_node-> ist gleich null, weil neben sie muss am Ende sein. Oder new_node-> next gleich null. 

JASON HIRSCHHORN: OK. Entschuldigung. New_node-> next gleich null denn wir sind am Ende. Das bedeutet nicht, es in. Wie setzen wir es in der Liste? Richtig. Das ist nur er gleich. Nein, wie tun wir eigentlich legen Sie sie in der Liste? Was ist mit dem Zeige Ende der Liste? 

ZIELGRUPPE: Head. 

JASON HIRSCHHORN: Es tut uns leid? 

ZIELGRUPPE: Kopf wird zeigen an das Ende der Liste. 

JASON HIRSCHHORN: Wenn es nichts in die Liste wird der Kopf auf die Zeige Ende der Liste. Damit werde für die Arbeit ersten Anzeige. Was ist, wenn es ein paar Dinge in der Liste? Als wir wollen nicht gesetzt Kopf gleich new_node. Was wollen wir dort? Ja? Wahrscheinlich vorherigen. Wird das funktionieren? Daran erinnern, dass die bisherigen ist nur einen Zeiger zu einem Knoten. Und vorherige ist eine lokale Variable. So wird diese Linie eine lokale Variable, vorherige gleich oder , die auf diesem neuen Knoten. Das wird nicht tatsächlich legte es in unserer Liste, wenn. Wie setzen wir es in unserer Liste? Akchar? 

ZIELGRUPPE: Ich glaube, Sie tun Strom-> next. 

JASON HIRSCHHORN: OK. curr-> next. Also noch einmal, der einzige Grund, warum wir unten sind hier ist, was macht Strom gleich? 

ZIELGRUPPE: Gleich null. 

JASON HIRSCHHORN: Und so was passiert, wenn wir tun, null-> next? Was wir jetzt bekommen? Wir werden einen Segmentation Fault zu bekommen. 

ZIELGRUPPE: Do curr gleich null. 

JASON HIRSCHHORN: Das ist die gleiche Sache wie zurück, obwohl, weil es eine lokale Variable wir die Einstellung gleich diesem neuen Knoten. Gehen wir zurück zu unserem Bild Einsetzen etwas. Sagen wir, wir sind am Ende einfügen der Liste, so finden Sie hier. Wir haben eine aktuelle Zeiger, ist zeigt auf null und einem vorherigen Punkt das ist bis 8 zeigt. So was brauchen wir, um zu aktualisieren, Avi? 

ZIELGRUPPE: Zurück-> next? 

JASON HIRSCHHORN: Zurück-> next ist das, was wir aktualisieren möchten, weil das tatsächlich legen Sie sie an das Ende der Liste. Wir haben immer noch ein Fehler, obwohl, dass wir gehen den Weg laufen. Was ist das für Fehler? Ja? 

ZIELGRUPPE: Es wird zurückkehren falsch in diesem Fall? 

JASON HIRSCHHORN: Oh, das ist werde return false. Aber es gibt einen anderen Bug. Also werden wir brauchen, um in return true setzen. 

ZIELGRUPPE: Hat vorherigen noch gleich null an der Spitze der Liste? 

JASON HIRSCHHORN: Also vorherigen Stand gleich null am Anfang. Wie können wir also über das zu bekommen? Ja? 

ZIELGRUPPE: Ich glaube, Sie tun können, einen Scheck bevor die while-Schleife, um zu sehen, ob es eine leere Liste. 

JASON HIRSCHHORN: OK. Also lassen Sie uns hier. Eine Überprüfung durch. Wenn - 

ZIELGRUPPE: Also, wenn Kopf gleich ist gleich null. 

JASON HIRSCHHORN: Wenn Kopf gleich ist gleich null - das wird uns sagen, ob es eine leere Liste. 

ZIELGRUPPE: Und dann haben Sie tun Kopf gleich neu. 

JASON HIRSCHHORN: Kopf gleich new_node? Und was müssen wir tun? 

ZIELGRUPPE: Und dann true zurück. 

JASON HIRSCHHORN: Nicht ganz. Wir sind einen Schritt fehlt. 

ZIELGRUPPE: New_node nächsten hat zu Punkt null. 

JASON HIRSCHHORN: Genau, Alden. Und dann können wir true zurück. OK. Aber es ist immer noch eine gute Idee, Dinge zu tun am Ende der Liste, oder? Gut. Wir könnten eigentlich noch zu bekommen an das Ende der Liste. So ist dieser Code in Ordnung, wenn wir die bist Ende der Liste und es gibt einige Dinge in der Liste? Right? Denn wir haben immer noch Marcus Idee. Wir könnten diese Schleife zu verlassen, weil wir sind am Ende der Liste. So wissen wir immer noch wollen, dass diese Code hier unten? 

ZIELGRUPPE: Ja. 

JASON HIRSCHHORN: Ja. Und was brauchen wir, um dies zu ändern? Wahr. Klingt das gut an alle, so weit? Jedes haben alle - Avi, hast du etwas hinzufügen? 

ZIELGRUPPE: Nein 

JASON HIRSCHHORN: OK. Also haben wir ein paar Änderungen vorgenommen. Wir haben diese Prüfung, bevor wir ging für eine leere Liste. Also haben wir uns um eine leere Liste genommen. Und hier haben wir darauf geachtet Einfügen was am Ende der Liste. So wie es scheint, dieser while-Schleife Nahme um Dinge dazwischen, irgendwo in der Liste, wenn es sind die Dinge in der Liste. 

OK. Lassen Sie uns dieses Programm laufen wieder. Nicht erfolgreich. 

ZIELGRUPPE: Sie hat es nicht geschafft. 

JASON HIRSCHHORN: Oh, Ich habe es nicht geschafft. Guter Punkt, Michael. Fügen wir ein Make verknüpft. Linie 87 gibt es einen Fehler. Linie 87. Alden, war dies die Linie, die Sie mir gegeben haben. Was ist los? 

ZIELGRUPPE: Es muss auf null gesetzt. 

JASON HIRSCHHORN: Excellent. Genau richtig. Es sollte null sein. Lassen Sie uns wieder. Übersetzen. OK. Lassen Sie uns legen Sie drei. Der Einsatz war erfolgreich. Lassen Sie ausdrucken. Oh, wenn wir überprüfen konnten. Aber wir nicht getan haben, die drucken noch Funktion. Lassen Sie uns noch etwas anderes geben. Was sollen wir geben? 

ZIELGRUPPE: Sieben. 

JASON HIRSCHHORN: Sieben? 

ZIELGRUPPE: Ja. 

JASON HIRSCHHORN: Wir haben ein Segment Schuld. Also haben wir, aber wir deutlich kann nicht zwei. Es ist 05.07 Uhr. So konnten wir dieses debuggen für drei Minuten. Aber ich werde uns hier verlassen und fahren Sie mit Hash-Tabellen. Aber nochmals, die Antworten zu diesem Code Ich werde es dir ein bisschen E-Mail. Wir sind sehr nahe daran. Ich sehr empfehlen Ihnen, herauszufinden, was ist denn hier los und zu beheben. Also werde ich Sie diesen Code als E-Mail gut plus die Lösung - wahrscheinlich die Lösung später. Zuerst dieser Code. 

Das andere, was ich will, bevor wir tun Ziel ist, wir haben nichts befreit. So möchte ich Ihnen zeigen, was valgrind aussieht. Wenn wir laufen valgrind Grenzen auf dem Programm. / verknüpft. Auch nach dieser Folie wir valgrind sollte mit irgendeiner Art von laufen Möglichkeit, in diesem Fall - Dichtheitsprüfung = voll. Also schreiben wir valgrind - Dichtheitsprüfung = voll. So wird dies valgrind laufen auf dem Programm. Und jetzt das Programm tatsächlich ausgeführt wird. So werden wir es wie laufen vor, legte etwas in. Ich werde in drei setzen. Das funktioniert. Ich werde nicht versuchen, an etwas zu setzen sonst, weil wir zu gehen einen Segmentation in diesem Fall falsch. Also ich werde einfach zu beenden. 

Und jetzt bist du hier unten zu sehen Leck-und Heap-Zusammenfassung. Das sind die guten Dinge, die Sie überprüfen möchten. So die Zusammenfassung Haufen - sie sagt, im Einsatz an der Ausfahrt - acht Bytes in einem Block. Daß ein Block ist Knoten wir malloced. Michael, Sie haben gesagt, bevor ein Knoten acht Bisse, weil es die ganze Zahl hat und der Zeiger. Also das ist unser Knoten. Und dann heißt es wir verwendet malloc sieben Mal und wir befreit etwas sechsmal. Aber wir haben nie als frei bezeichnet, so habe ich keine Ahnung, was das spricht. 

Aber es genügt zu sagen, dass, wenn Sie Ihre Programm läuft, malloc aufgerufen wird in einigen anderen Orten, die wir brauchen Sie nicht zu befürchten. So wurde malloc wahrscheinlich genannt an einigen Stellen. Wir brauchen keine Sorgen zu machen, wo. Aber das ist uns wirklich. Diese erste Linie sind wir. Wir verließen diesen Block. Und Sie sehen, dass hier kann im Leck Zusammenfassung. Noch erreichbar - acht Bytes in einem Block. Das bedeutet, dass der Speicher - wir, dass der Speicher durchgesickert. Definitiv verloren - etwas für immer verloren. Im Allgemeinen werden Sie nicht sehen, nichts da. Noch ist in der Regel erreichbar, wo Sie werden Dinge sehen, wo Sie wollen zu schauen, um zu sehen, welche Code sollten Sie befreit haben, aber Sie vergessen haben, zu befreien. 

Und dann, wenn dies nicht der Fall ist, wenn wir das alles kostenlos, wir können das überprüfen. Lassen Sie das Programm laufen nur nicht setzen in nichts. Sie werden hier unten im Einsatz an der Ausfahrt sehen - Null-Bytes in Null-Blöcke. Das heißt, wir hatten nichts mehr Wenn dieses Programm verlassen. Also, bevor Sie in pset6, führen valgrind und stellen Sie sicher, dass Sie nicht haben, keine Speicherlecks in Ihrem Programm. Wenn Sie alle Fragen mit valgrind haben, fühlen Sie sich frei zu erreichen. Aber das ist, wie Sie es verwenden. Sehr einfach - sehen, wenn Sie haben im Einsatz bei der Ausfahrt - alle Bytes in allen Blöcken. 

So waren wir auf Einsatz Knoten arbeiten. Ich hatte zwei andere Funktionen hier - drucken Knoten und Knoten frei. Auch diese Funktionen sind gut sein, damit Sie üben denn sie werden Ihnen nicht nur helfen, diese Probe Übungen, aber auch auf das Problem eingestellt. Sie bilden auf ziemlich genau die Dinge Sie gehen in die zu tun zu haben sind Problem eingestellt. Aber ich möchte sicherstellen, dass berühren wir auf alles. Und Hash-Tabellen sind auch entscheidend für was wir in diesem Abschnitt tun Woche - oder in dem Problem-Set. 

So werden wir, um den Abschnitt zu beenden Gespräch über Hash-Tabellen. Wenn Sie bemerken, ich machte ein wenig Hash-Tabelle. Das ist nicht das, was wir reden über, jedoch. Wir freuen uns über einen anderen sprechen Art von Hash-Tabellen. Und im Kern in einer Hashtabelle ist nichts weiter als ein Array plus eine Hash-Funktion. Wir werden für ein bisschen einfach nur reden sicherzustellen, dass jeder versteht, was für ein Hash-Funktion ist. Und ich sage Ihnen jetzt, dass es nicht mehr als zwei Dinge - ein Array und eine Hash-Funktion. Und hier sind die Schritte durch die diese betreibt. 

Da ist unser Angebot. Es ist unsere Aufgabe. Insbesondere Hash-Funktionen müssen tun, ein paar Dinge mit diesem. Ich werde speziell sprechen über dieses Problem eingestellt. Es ist wahrscheinlich zu nehmen in einer Zeichenkette. Und was es geht zurück? Welche Datentyp? Alden? Ihre Hash-Funktion zurück? Eine ganze Zahl. Also das ist, was der Hash Tabelle besteht aus - eine Tabelle, in der Form von Array und eine Hash-Funktion. Wie funktioniert es? Es arbeitet in drei Schritten. Wir geben ihm einen Schlüssel. In diesem Fall werden wir ihm einen String. Wir nennen die Hash-Funktion pro Schritt ein auf den Schlüssel und wir bekommen einen Wert. 

Genauer gesagt, werden wir sagen, wir bekommen eine ganze Zahl. Die ganze Zahl ist, gibt es sehr spezielle Grenzen, was die ganze Zahl sein kann. In diesem Beispiel unsere Anordnung eine Größe von drei. Also, welche Nummern können, dass ganze Zahl sein. Was ist der Bereich der gültigen Werte für dass ganze Zahl, die Rückkehr Typ dieser Hash-Funktion? Zero, eins und zwei. Der Punkt, der die Hash-Funktion ist, herauszufinden, den Platz in der Reihe wo unser Schlüssel geht. Es gibt nur drei mögliche Orte hier - null, eins oder zwei. Also diese Funktion bessere Rendite null, eins oder zwei. Einige gültig indice in diesem Array. 

Und dann je nachdem, wo es zurückkehrt, Sie können es sehen, offenen Array umklammern den Wert. Das ist, wo wir den Schlüssel. So werfen wir in den Kürbis, wir raus Null. Bei Array Bügel 0, setzen wir Kürbis. Wir werfen in Katzen, bekommen wir aus einem. Wir haben eine Katze an. Wir stellen in Spinne. Wir steigen aus beiden. Wir stellen Spinne in der Halterung zwei Array. Es wäre so schön, wenn es funktionierte so. Aber leider, wie wir sehen werden, es ist ein bisschen komplizierter. 

Bevor wir dort ankommen, Fragen über diese Grund Set-up von einer Hash-Tabelle? Dies ist ein Bild von genau was wir zog auf dem Brett. Da wir aber zog es auf dem Brett, ich werde mich nicht in sie weiter zu gehen. Im Wesentlichen Tasten, der magische Black Box - oder in diesem Fall, blaugrün-Box - einer Hash-Funktion stellt sie in Eimern. Und in diesem Beispiel sind wir nicht setzen den Namen. Wir setzen die zugehörige Telefon Anzahl von Namen in den Eimer. Aber man konnte sehr gut nur setzen Sie den Namen in den Eimer. 

Dies ist nur ein Bild von dem, was wir zeichneten auf dem Brett. Wir haben potenzielle Fallstricke, wenn. Und es gibt vor allem zwei gleitet, dass ich gehen will über. Der erste ist zu eine Hash-Funktion. Also stellte ich die Frage, was macht eine gute Hash-Funktion? Ich gebe zwei Antworten. Die erste ist, dass es deterministisch. Im Rahmen von Hash-Funktionen, was bedeutet das? Ja? 

Zielgruppe: IT kann die finden Index in konstanter Zeit? 

JASON HIRSCHHORN: Das ist nicht, was es bedeutet. Aber das ist ein guter Tipp. Jeder andere haben eine Vermutung zu dem, was das bedeutet? Dass eine gute Hash-Funktion deterministisch ist? Annie? 

PUBLIKUM: Das kann nur ein Schlüssel abgebildet werden an einen Ort in der Hash-Tabelle. 

JASON HIRSCHHORN: Das ist genau richtig. Jedes Mal, wenn Sie in Kürbis setzen, es immer Null zurück. Wenn Sie in Ihrem Kürbis und Hash setzen Rückgabewert ist Null, hat aber eine Wahrscheinlichkeit der Rücksendung etwas sonst größer als Null - so vielleicht kann man manchmal zurück oder zwei anderen Zeiten - das ist keine gute Hash-Funktion. Du bist genau richtig. Ihre Hash-Funktion zurückgeben sollte die elbe exakte ganze Zahl, in diesem Fall für exakt das gleiche Zeichenfolge. 

Vielleicht ist es genau die gleiche Ganzzahl zurück für exakt das gleiche Zeichenfolge unabhängig von der Kapitalisierung. Aber in diesem Fall ist es immer noch deterministische, da mehrere Dinge werden auf den gleichen Wert zugeordnet. Das ist in Ordnung. Solange es nur eine Ausgabe für einen gegebenen Eingang. 

OK. Die zweite Sache ist, dass es kehrt gültigen Indizes. Wir erzogen, dass früher. Dieser Hash-Funktion - oh boy - eine Hash-Funktion sollte zurück gültigen Indizes. So sagen - wir zurück zu diesem Beispiel gehen. Meine Hash-Funktion zählt die Buchstaben im Wort. Das ist der Hash-Funktion. Und wieder, dass ganze Zahl ist. Also wenn ich das Wort A, ist es gehen zu einem zurück. Und es geht um ein Recht hier zu setzen. Was ist, wenn ich in dem Wort Fledermaus? Es geht um drei zurück. Wo Fledermaus gehen? 

Es passt nicht. Aber es braucht, um irgendwohin zu gehen. Das ist mein Hash-Tabelle nachdem alle, und alles muss irgendwo hin. Also, wo soll Fledermaus gehen? Irgendwelche Gedanken? Errät? Gute Vermutungen? 

ZIELGRUPPE: Null. 

JASON HIRSCHHORN: Warum Null? 

ZIELGRUPPE: Weil drei Modulo drei Null ist? 

JASON HIRSCHHORN: Drei Modulo drei Null ist. Das ist eine große Vermutung, und das ist richtig. Also in diesem Fall sollte es wahrscheinlich auf Null. Also ein guter Weg, um sicherzustellen, dass dieser Hash Funktion nur gültig Indizes die ihr von der Größe der Tabelle modulo. Wenn Sie Modulo was immer das Rendite drei, du bist immer zu bekommen etwas zwischen null, eins und zwei. Und wenn das immer wieder sieben, und Sie immer von drei Modulo, sind Sie immer gehen, um die gleiche Sache zu bekommen. 

Also es ist immer noch determinis wenn Sie Modulo. Aber das wird sicherstellen, dass Sie nie etwas zu bekommen - eine ungültige Industrie. Im Allgemeinen, dass Modulo passieren sollte in Ihrem Hash-Funktion. So brauchen Sie nicht zu kümmern. Sie können nur dafür sorgen, dass Dies ist eine gültige indice. Haben Sie Fragen zu diesem Thema potenzielle Fallstrick? 

OK. Und wir gehen. Nächste potenzielle Fallstrick, und das ist die große. Was passiert, wenn zwei Tasten Karte auf den gleichen Wert? So gibt es zwei Möglichkeiten, dies zu umgehen. Die erste ist linear genannt Sondieren, was ich bin nicht zu übergehen. Aber Sie kennen sollten, wie das funktioniert und was das ist. 

Die zweite werde ich gehen über denn das ist die eine, die viele Menschen werden wahrscheinlich am Ende entscheiden in ihr Problem Satz zu verwenden. Natürlich müssen Sie nicht auf. Aber für das Problem gesetzt, viele Menschen neigen zu wählen, um eine Hash-Tabelle erstellen mit separater Verkettung zu implementieren ihr Wörterbuch. So werden wir über das, was es bedeutet, zu gehen um eine Hash-Tabelle mit erstellen getrennte Verkettung. 

Also habe ich in Kürbis. Es gibt Null zurück. Und ich habe hier Kürbis. Dann habe ich in - was ist eine andere Halloween-Themen-Sache? 

ZIELGRUPPE: Süßigkeit. 

JASON HIRSCHHORN: Süßigkeit! Das ist ein großer. Ich in Süßigkeiten und Bonbons setzen gibt mir auch Null. Was kann ich tun? Irgendwelche Ideen? Weil Sie alle Art von wissen welche getrennte Verkettung ist. Also irgendwelche Ideen, was zu tun? Ja. 

ZIELGRUPPE: Setzen Sie die Zeichenfolge tatsächlich in der Hash-Tabelle. 

JASON HIRSCHHORN: Also wir gehen auf zeichnen die gute Idee hier. OK. 

ZIELGRUPPE: Haben Sie die Hash-Tabelle [Unverständlich] der Zeiger, die auf die Punkte der Beginn einer Liste. Und dann haben Kürbis der erste Wert sein in dieser verknüpften Liste und Süßigkeiten sein der zweite Wert in dieser verketteten Liste. 

JASON HIRSCHHORN: OK. Marcus, das war hervorragend. Ich werde das brechen. Marcus sagt nicht schreiben Kürbis. Das wäre schlecht. Nicht setzen Süßigkeiten woanders. Wir werden sie beide auf Null setzen. Aber wir werden, zu beschäftigen setzen sie auf Null Erstellen einer Liste auf Null. Und wir werden um eine Liste zu erstellen alles, was auf null abgebildet. Und der beste Weg lernten wir erstellen eine Liste, die wachsen und schrumpfen kann dynamisch nicht im ein anderes Array. So dass nicht ein mehrdimensionales Array. Aber nur eine verkettete Liste. 

Also, was er vorgeschlagen - Ich werde einen neuen zu bekommen - ist ein Array mit Zeigern, ein Array von Zeigern. OK. Jede Idee oder Tipp, was die Art dieser Zeiger sein sollte? Marcus? 

ZIELGRUPPE: Zeiger auf - 

JASON HIRSCHHORN: Weil Sie sagte eine verkettete Liste, so - 

ZIELGRUPPE: Knoten Zeiger? 

JASON HIRSCHHORN: Knoten Zeiger. Wenn die Dinge in unserem verknüpft Liste sind Knoten, dann sind sie sollte Knoten Zeiger sein. Und was tun sie anfangs gleich? 

ZIELGRUPPE: Null. 

JASON HIRSCHHORN: Null. Es gibt also unsere leeren Sache. Kürbis Null zurück. Was machen wir? Gehe ich durch sie? Eigentlich hat mir schon Marcus. Jemand anders gehen mir durch sie. Was wir tun, wenn wir - das sieht sehr ähnlich das, was wir gerade tun. Avi. 

ZIELGRUPPE: Ich werde eine Vermutung zu nehmen. Also, wenn Sie Süßigkeiten zu bekommen. 

JASON HIRSCHHORN: Ja. Nun, wir haben Kürbis. Lassen Sie uns unsere erste. Wir bekamen Kürbis. 

ZIELGRUPPE: OK. Kürbis Null zurück. So setzen Sie es in diesem. Oder tatsächlich, sie setzen Sie in der verketteten Liste. 

JASON HIRSCHHORN: Wie wollen wir es in der verketteten Liste? 

ZIELGRUPPE: Oh, das eigentliche Syntax? 

JASON HIRSCHHORN: Nur zu Fuß - mehr sagen. Was machen wir? 

ZIELGRUPPE: Sie legen Sie einfach als den ersten Knoten. 

JASON HIRSCHHORN: OK. So haben wir unsere Knoten, Kürbis. Und jetzt, wie kann ich es einfügen? 

ZIELGRUPPE: Sie weisen es dem Zeiger. 

JASON HIRSCHHORN: Welche Zeiger? 

ZIELGRUPPE: Der Zeiger auf Null. 

JASON HIRSCHHORN: Also, wo macht dieser Punkt? 

ZIELGRUPPE: Um jetzt null. 

JASON HIRSCHHORN: Nun, es zeigt auf null. Aber ich setze in Kürbis. Also, wo soll es zeigen? 

ZIELGRUPPE: Um Kürbis. 

JASON HIRSCHHORN: Um Kürbis. Genau. So deutet dies auf Kürbis. Und wo ist dieser Zeiger Kürbis in Punkt? Zu 

ZIELGRUPPE: Null. 

JASON HIRSCHHORN: Um null. Genau. Also haben wir nur etwas einge sich der Liste. Wir haben gerade schrieb diesen Code, um dies zu tun. Fast wir haben es fast vollständig geknackt. Jetzt fügen wir Süßigkeiten. Unsere Süßigkeiten geht ebenfalls auf Null. Also, was machen wir mit Süßigkeiten? 

PUBLIKUM: Das hängt davon ab, ob nicht wir versuchen, es zu sortieren. 

JASON HIRSCHHORN: Das ist genau richtig. Es hängt davon ab, ob wir versuchen, es zu sortieren. Nehmen wir an, wir sind nicht gehen, um es zu sortieren. 

ZIELGRUPPE: Na dann, wie wir diskutiert zuvor, ist es am einfachsten, nur um es setzen gleich zu Beginn so der Zeiger Null Punkte, um Süßigkeiten. 

JASON HIRSCHHORN: OK. Halten Sie an. Lassen Sie mich Süßigkeiten schaffen hier richtig. Also dieser Zeiger - 

ZIELGRUPPE: Ja, sollte jetzt werden, um Süßigkeiten zu zeigen. Dann haben Sie den Mauszeiger aus Süßigkeiten Punkt Kürbis. 

JASON HIRSCHHORN: Wie das? Und sagen, wir haben eine andere Ding auf Null Karte? 

ZIELGRUPPE: Nun, man muss nur das gleiche tun? 

JASON HIRSCHHORN: Tun Sie das Gleiche. Also in diesem Fall, wenn wir nicht wollen, halten Sie es sortiert klingt ziemlich einfach. Wir nehmen den Zeiger in der indice von unseren Hash-Funktion gegeben. Wir haben diesen Punkt auf unserer neuen Knoten. Und dann, was es zeigt zuvor - in diesem Fall null, in der zweiten Fall Kürbis - , dass, was immer es ist zu zeigen zuvor, in den nächsten fügen wir unsere neuen Knoten. Wir sind etwas Einsetzen am Anfang. In der Tat ist dies viel einfacher als versuchen, die Liste sortiert zu halten. Aber noch einmal, wird sein Suchen mehr hier kompliziert. Wir haben immer bis zum Ende zu gehen. 

OK. Haben Sie Fragen zu getrennten Verkettung? Wie das funktioniert? Bitte fragen sie jetzt. Ich sicherstellen, dass Sie alle wollen wirklich verstehen, bevor wir den Kopf aus. 

ZIELGRUPPE: Warum haben Sie Kürbis setzen und Süßigkeiten in die gleiche Teil des Hash-Tabelle? 

JASON HIRSCHHORN: Gute Frage. Warum wir setzen Sie sie in der gleichen Teil des Hash-Tabelle? Nun, in diesem Fall ist unsere Hash-Funktion Null zurück für beide. So müssen sie bei indice Null gehen weil das ist, wo wir zu gehen nach ihnen zu suchen, wenn wir jemals wollen sie schauen. Wieder mit einem linearen Ansatz Sondieren wir nicht setzen würde sie beide bei Null. Aber in der separaten Kettenansatz, wir werden sie beide auf Null setzen und dann eine Liste aus der Null. 

Und wir wollen nicht überschreiben Kürbis einfach für das, weil dann werden wir davon ausgehen, dass Kürbis war nie eingesetzt. Wenn wir nur immer eine Sache, in der Ort, der schlecht sein würde. Dann gäbe es keine Chance von uns je - wenn wir jemals eine Kopie hatte, dann haben wir würde nur zu löschen unseren Ausgangswert. Also das ist, warum wir diesen Ansatz zu tun. Oder, das ist, warum wir uns - aber wieder, wir entschied sich für die getrennte Verkettung Ansatz, denen es viele andere Ansätze man konnte wählen. Heißt das, Ihre Frage zu beantworten? 

OK. Carlos. Linear Probing würde bedeuten - wenn wir fanden eine Kollision bei Null, wir würde im nächsten Ort, um zu sehen, ob es war offen und hat es dort. Und dann schauen wir uns in der nächsten Sport-und sehen, ob das offen war und legte es dort. So finden wir den nächsten verfügbaren offene Stelle und legen Sie sie dort. Noch Fragen? Ja, Avi. 

ZIELGRUPPE: Als Follow-up zu, dass was halten Sie von der nächsten Stelle das? In der Hash-Tabelle oder in einer verknüpften Liste. 

JASON HIRSCHHORN: Für lineare Programmierung, keine verkettete Listen. Der nächste Punkt auf der Hash-Tabelle. 

ZIELGRUPPE: OK. Also die Hash-Tabelle wäre Initialisierung der Größe - wie die Anzahl der Strings Sie wurden Einfügen? 

JASON HIRSCHHORN: Sie würde wollen, dass es wirklich groß. Ja. Hier ist ein Bild von dem, was wir zog nur auf dem Brett. Auch hier haben wir eine Kollision hier richtig. bei 152. Und Sie werden sehen, die wir erstellt eine verkettete Liste aus der IT. Auch die Hash-Tabelle separaten Verkettung Ansatz ist nicht die, die Sie haben für Probleme eingestellt zu nehmen sechs, sondern ist eine, die eine Menge von Studenten neigen dazu, zu übernehmen. Also in diesem Sinne, lassen Sie uns kurz sprechen bevor wir den Kopf aus etwa sechs Problem, und dann werde ich eine Geschichte mit Ihnen teilen. Wir haben drei Minuten. 

Problem stellte sechs. Sie haben vier Funktionen - Last, überprüfen Sie, Größe und Entladen. Last - Nun, wir haben es schon gerade jetzt über Last. Wir zogen Last auf dem Brett. Und wir begannen sogar Codierung eine Menge Einfügen in einer verknüpften Liste. Also Last nicht viel mehr als was wir gerade tun. 

Check ist, sobald Sie etwas geladen. Es ist das gleiche Verfahren wie diese. Die gleichen ersten beiden Teile, wo Sie werfen etwas in der Hash-Funktion und erhalten seinen Wert. Aber jetzt sind wir nicht einlegen. Jetzt sind wir für sie suchen. Ich habe Beispielcode für die Suche geschrieben etwas in einer verketteten Liste. Ich ermutige Sie, dass zu üben. Aber intuitiv etwas zu finden ist ziemlich ähnlich wie das Einfügen etwas. In der Tat, ein Bild zu finden, zeichneten wir etwas in einer verketteten Liste, bewegen durch, bis Sie am Ende bekam. Und wenn du zu Ende und konnte nicht finden, dann ist es nicht da. Also das ist, zu überprüfen, im Wesentlichen. 

Weiter ist die Größe. Lassen wir Größe. Schließlich haben Sie entladen. Unload ist, die wir nicht gezeichnet haben auf der Platine oder noch codiert. Aber ich ermutige Sie, versuchen Sie es Codierung in unserer Stichprobe verbundenen Liste Beispiel. Aber entladen intuitiv ähnlich ist kostenlos - oder ich meine, ist ähnlich zu überprüfen. Außer jetzt jedes Mal, du gehst durch, bist du nicht einfach zu überprüfen, sehen, wenn Sie Ihren Wert dort zu haben. Aber du nimmst diesen Knoten und befreit wird, im Wesentlichen. Das ist, was Entladen fragt, was Sie tun. Kostenlose alles, was Sie malloced habe. Durch die ganze Liste, so wirst du wieder, die durch den ganzen Hash Tabelle wieder. Dieses Mal nicht überprüfen um zu sehen, was da ist. Nur befreien, was da ist. 

Und schließlich groß. Größe sollten umgesetzt werden. Wenn Sie nicht implementieren Größe - Ich werde es so zu sagen. Wenn Sie nicht genau implementieren Größe eine Zeile Code, einschließlich der return-Anweisung, sind Sie Dabei Größe falsch. So stellen Sie sicher, Größe, für die vollständige Design Punkte, Sie tun es in genau einem Codezeile, einschließlich die return-Anweisung. 

Und noch nicht packen, Akchar. Eager Beaver. Ich danke sagen wollte Jungs für das Kommen zu Abschnitt. Haben Sie ein glückliches Halloween. Das ist mein Kostüm. Ich werde das Tragen dieser am Donnerstag, wenn ich dich sehe an Bürozeiten. Und wenn Sie neugierig sind etwas mehr Hintergrund als zu diesem Kostüm, fühlen frei, um 2011 Abschnitt für eine Geschichte auf, warum bin ich Tragen Sie den Kürbis-Kostüm. Und es ist eine traurige Geschichte. So stellen Sie sicher, dass Sie einige Gewebe in der Nähe. Aber auf das, wenn Sie welche haben Fragen werde ich bleiben, um außerhalb nach Abschnitt. Viel Glück auf sechs Problem eingestellt. Und wie immer, wenn Sie welche haben Fragen, lassen Sie es mich wissen.