[Powered by Google Translate] [Walkthrough - Problem Set 5] [Zamyla Chan - Harvard University] [Dies ist CS50. - CS50.TV] 

Gut. Hallo, alle, und Walkthrough 5 begrüßen zu dürfen. 

Pset5 ist Rechtschreibfehler, in denen werden wir machen eine Rechtschreibprüfung. Spell-Checker sind extrem wichtig. Hat das schon einmal passiert? Sie arbeiten sehr, sehr horten auf ein Papier für einen Zusammenstoß und dann noch am Ende immer eine sehr glow rade wie ein D oder D = und alles, weil Sie sind die Leberwurst Spoiler in den Wal breites Wort. Ja, Korrekturlesen Ihrer Paprika ist eine Frage der, höchste Impotenz. Dies ist ein Problem, das männlich, männliche Schüler auswirkt. Ich wurde einmal von meiner sith Grade Folterer gesagt, dass ich nie in eine gute Kollegen bekommen. Und das ist alles, was ich jemals wollte, das ist alles jedes Kind will in meinem Alter ist, nur um in eine gute Kollegin bekommen. Und nicht nur irgendein Kollege. Nein, ich wollte zu einem Ivory Legal Kollegen gehen. Also, wenn ich es nicht tat Verbesserung gegangen wäre meine Träume zu gehen, Harvard sein, Jale oder Prison - Sie wissen, in Prison, New Jersey. Also habe ich mir eine Rechtschreibprüfung. Das ist ein kleiner Auszug aus einer meiner Lieblings gesprochene Wort Künstler, Taylor Mali. Wie auch immer, wie er sagt, ist die Bedeutung einer Rechtschreibprüfung sehr wichtig. 

So zum Walkthrough 5 begrüßen, in denen wir über pset5 sprechen: Rechtschreibfehler, in denen werden wir machen unsere eigene Rechtschreibprüfung. Die Toolbox für diese Woche, die Verteilung Code wird wichtig sein, zu betrachten nur zu verstehen, die verschiedenen Funktionen, die Ihr Wörterbuch ist zu haben. Wir eigentlich los zu sein mit mehreren. C Dateien, die zusammen unsere pset. Und so einen Blick in die verschiedenen Aspekte, obwohl wir eigentlich nicht bearbeiten eine der Dateien, speller.c, zu wissen, wie es mit Bezug auf dictionary.c funktioniert, was werden wir schreiben, wird es ziemlich wichtig. Die pset spec enthält auch eine Menge nützlicher Informationen in Bezug auf Dinge, die kann man davon ausgehen, Regeln und ähnliche Dinge, so sicher sein, die pset spec sorgfältig für Tipps. Und im Zweifelsfall einer Regel oder so etwas, dann immer auf die pset spec beziehen oder Diskutieren. Diese pset wird stark auf Zeiger, so wollen wir sicherstellen, dass wir den Unterschied zwischen dem Hinzufügen stars verstehen vor dem Mauszeiger den Namen und die kaufmännische, wie um sie zu befreien, etc. So ist ein Meister der Zeiger wird sehr hilfreich sein, dieses Problem set. Wir gehen in verkettete Listen ein bisschen mehr zu sehen, wo wir Elemente, die wir Knoten, die sowohl einen Wert sowie einen Zeiger haben, rufen an den nächsten Knoten, und so im wesentlichen Verknüpfung verschiedener Elemente eines nach dem anderen. Es gibt ein paar verschiedene Möglichkeiten der Umsetzung Ihrer aktuellen Wörterbuch. Wir werden in zwei wichtigsten Methoden, die Hash-Tabellen ist und dann versucht zu suchen. In diese beiden, beinhalten sie eine Art von Vorstellung einer verketteten Liste wo Sie Elemente miteinander verknüpft. Und so werden wir schauen über, wie Sie vielleicht in der Lage sein um verkettete Listen zu betreiben, schaffen sie, navigieren in Hinblick darauf, wie, zum Beispiel, legen Sie einen Knoten hinein oder freie alle Knoten als auch. In Bezug auf die Befreiung Knoten, das ist wirklich wichtig dass, wenn wir malloc Speicher, danach haben wir es zu befreien. So wollen wir sicherstellen, dass kein Zeiger unfreed geht, dass wir keine Speicherlecks. Wir werden ein Tool namens Valgrind, die Ihr Programm läuft einzuführen und prüft, ob alle Speicher, die Sie zugeordnet wird dann befreit. Ihre pset ist erst dann abgeschlossen, wenn es funktioniert, und es hat die volle Funktionalität, sondern auch, erzählt Valgrind Sie, dass Sie keine Speicherlecks vorhanden. Schließlich, für diese pset, ich möchte wirklich betonen - Ich meine, wie gewohnt, ich bin definitiv ein Befürworter der mit Stift und Papier für Ihr Problem Sets, aber für diesen einen, ich denke, dass Stift und Papier wird besonders wichtig sein, wenn Sie zu zeichnen Pfeile, um Dinge und verstehen, wie die Dinge funktionieren wollen. Also auf jeden Fall versuchen, Stift und Papier verwenden, um Dinge zu ziehen, bevor Sie mit der Codierung erhalten denn es könnte ein bisschen chaotisch. 

Lassen Sie uns zuerst in verkettete Listen gehen ein wenig. Verketteten Listen bestehen aus Knoten, wobei jeder Knoten einen Wert zugeordnet ist, sowie einen Zeiger auf den nächsten Knoten, nachdem sie. Ein paar Dinge wichtig mit den verknüpften Listen sind, dass wir uns daran erinnern müssen wobei das erste Knoten ist, und dann, sobald wir wissen, wo der erste Knoten ist, So können wir den Knoten zuzugreifen, dass die ersten Knoten Punkte auf und dann das übernächste und das übernächste. Und dann das letzte Element in Ihrer verketteten Liste ist, dass Knoten Zeiger wird immer auf NULL. Wenn ein Knoten auf NULL, dann wissen Sie, dass Sie das Ende der Liste erreicht, dass dieser Knoten ist das letzte, dass es nichts danach. Hier in dieser schematischen, sehen Sie, dass die Pfeile die Zeiger sind, und der blaue Abschnitt ist, wo der Wert gespeichert wird, und dann das rote Feld mit dem Zeiger auf es ist der Knoten Zeiger zeigt auf den nächsten Knoten, nachdem sie. Und so sehen Sie hier, würde die D-Knoten auf NULL, weil es das letzte Element in der Liste ist. 

Lassen Sie uns, wie wir eine Struktur für einen Knoten zu definieren suchen. Und da wollen wir mehrere Knoten, dies wird ein typedef struct geworden in denen wir gehen, um verschiedene Instanzen von Knoten haben. Und so definieren wir es als einen neuen Datentyp. Hier haben wir eine typedef struct Knoten. In diesem Beispiel sind wir mit ganzzahligen Knoten handelt, so haben wir eine ganze Zahl benannten Wert und dann haben wir einen weiteren Zeiger, und in diesem Fall ist es ein Zeiger auf einen Knoten, so haben wir eine struct node * namens Next. Und dann nennen wir diese ganze Sache Knoten. Stellen Sie sicher, dass Sie diese Syntax folgen. Beachten Sie, dass der Knoten tatsächlich bis oben erwähnten als auch unter den geschweiften Klammern. Dann den Überblick zu behalten, wo meine erste Knoten ist in diesem verketteten Liste, dann habe ich einen Knoten Zeiger namens Kopf, und ich malloc Platz genug für die Größe eines Knotens. Hinweise, ist jedoch, dass Kopf tatsächlich ein Knoten Zeiger als zu einer tatsächlichen Knoten selbst entgegengesetzt. So der Kopf tatsächlich enthält keine Wert, es nur die Punkte auf den niedrigeren der erste Knoten in meinem verkettete Liste ist. 

Um ein besseres Gefühl für verkettete Listen zu bekommen, weil es sehr wichtig ist zu verfolgen, um sicherzustellen, dass Sie die Kette zu halten zu halten, Ich mag daran zu denken, wie Menschen in einer Linie den Händen halten, wo jede Person wird Hand in Hand mit dem nächsten ein. Sie können in dieser Zeichnung nicht zu sehen, aber im Grunde sind sie an die nächste Person zeigen das ist in ihrer Kette. Und wenn Sie so wollen, um eine verkettete Liste, wo diese Leute durchqueren - vorstellen, all jener Menschen haben Werte mit ihnen verbundenen und auch an die nächste Person in der Linie zeigen - wenn Sie die verknüpfte Liste durchlaufen wollen, zum Beispiel, um entweder die Werte bearbeiten oder suchen Sie nach einem Wert oder so etwas, dann werden Sie wollen, um einen Zeiger auf die jeweilige Person zu haben. So werden wir einen Datentyp Knoten Zeiger haben. Für diesen Fall nennen wir es Cursor. Ein weiterer gemeinsamer Weg, dies zu nennen wäre Iterator oder so ähnlich weil es Iteration über und tatsächlich bewegt, welcher Knoten es zeigt auf. Das hier wird unser Cursor sein. Unsere Cursor wird zunächst auf das erste Element in unserer Liste zeigen. Und was wir tun wollen, ist, dass wir würde grundsätzlich fortsetzen Sie den Cursor, Verschieben von Seite zu Seite. In diesem Fall wollen wir es auf das nächste Element in der Liste zu verschieben. Bei Arrays, was wir tun müssen, ist würden wir nur sagen, dass wir erhöhen den Index um 1 erhöht. In diesem Fall ist das, was wir tun müssen, tatsächlich finden, welche Person dieser Strom Person verweist, und dass geht zum nächsten Wert. Also, wenn der Cursor nur ein Knoten Zeiger, dann das, was wir tun wollen ist, dass wir wollen, um den Wert zu erhalten, dass der Cursor verweist. Wir wollen zu diesem Knoten zu bekommen und dann, wenn wir an diesem Knoten sind, zu finden, wo es geht zeigt. Um zu der Ist-Knoten, dass der Cursor zeigt, um zu erhalten, wir in der Regel zeigen, dass er mit einem (* Cursor). Das würde Ihnen den aktuellen Knoten, der Cursor verweist. Und danach, was wir tun wollen, ist, dass wir zugreifen wollen unabhängig, dass der Knoten der nächsten Wert ist. Um dies zu tun, um die Werte in der Struktur zu gelangen, müssen wir den Punkt-Operator. So wäre es (* Cursor). Nächsten. Aber das ist ein bisschen chaotisch im Sinne der mit den Klammern um das * Cursor und so ersetzen wir diese ganze Erklärung mit den Cursor->. Dies ist ein Bindestrich und dann ein Größer-Zeichen, so dass ein Pfeil. Cursor-> next. Das wird tatsächlich bekommen Sie die Knoten, der Cursor zeigt. Dieser Wert ist der nächste. Anstatt also mit dem Stern und den Punkt, du ersetzen, dass mit einem Pfeil. Seien Sie sehr vorsichtig, um sicherzustellen, dass Sie diese Syntax verwenden versuchen. 

Nun, da haben wir unsere Cursor, wenn wir den Wert zugreifen möchten, hatten wir vorher Cursor-> next, sondern um den Wert an dem Knoten, mit dem Cursor auf den Hinweis zugreifen, einfach nur sagen, node-> Wert. Von dort ist es vom Datentyp, was wir haben, die Werte und die Knoten werden definiert. Wenn es ein int-Knoten ist, dann Cursor-> value ist gerade dabei, eine ganze Zahl sein. So können wir Operationen auf das zu tun, überprüfen Gleichheiten, weisen unterschiedliche Werte, etc. Also, was Sie tun möchten, wenn Sie Ihren Cursor an die nächste Person verschieben möchten, Sie tatsächlich ändern Sie den Wert des Cursors. Da Cursor ist ein Knoten Zeiger, ändern Sie die tatsächlichen Pointer-Adresse an die Adresse des nächsten Knotens in Ihrer Liste. Dies ist nur ein Code wo man durchlaufen. Wo habe ich den Kommentar etwas tun, das ist, wo Sie wahrscheinlich gehst auf den Wert zuzugreifen oder etwas tun, um mit diesem bestimmten Knoten zu tun. Um es zu beginnen, ich sage, dass mein Cursor zunächst wird auf das erste Element in der verknüpften Liste verweist. Und so weiter vorne, definiert ich es als Leiter des Knotens. 

Wie ich schon erwähnt, ist befreit wirklich wichtig. Sie wollen sicherstellen, dass Sie jedes Element zu befreien in der Liste, wenn Sie mit ihm fertig sind. Wenn Sie nicht brauchen, um jede dieser Zeiger mehr verweisen, Sie wollen sicherstellen, dass Sie alle diese Hinweise zu befreien. Aber Sie wollen hier sehr vorsichtig sein, dass Sie keine Speicherlecks vermeiden wollen. Wenn Sie sich kostenlos eine Person vorzeitig, dann alle Zeiger, dass diese Knotenpunkte zu gehen verloren. Gehen wir zurück zu der Person beispielsweise, um es ein bisschen mehr High Stakes, lasst uns diese Leute, außer in diesem Fall werden sie über einem See mit einem Monster schwebt. Wir wollen sicherstellen, dass, wenn wir zu befreien, verlieren wir nicht und lassen Sie keinen Knoten, bevor wir sie tatsächlich haben befreit. Zum Beispiel, wenn Sie wurden zu rufen Sie einfach kostenlos auf dieser Kerl hier, dann würde er befreit werden, aber dann alle diese Jungs würden dann verloren und sie würden abdriften und herunterfallen. So wollen wir sicherstellen, dass stattdessen haben wir einen Link zu dem Rest aufrechterhalten wollen. Unsere Kopfzeiger, die auf das erste Element in der Liste zeigt. Es ist eine Art wie ein Seil Verankerung der ersten Person. Was möchten Sie vielleicht tun, wenn Sie eine kostenlose Liste haben - Wenn Sie das erste Element zuerst befreien wollen, dann können Sie eine temporäre Zeiger dass Punkte auf, was auch immer das erste Element ist. So haben Sie Ihre temporären Zeiger hier. Auf diese Weise haben wir ein Halten des ersten Knotens. Und dann, da wir wissen, dass der erste Knoten wird befreit werden, dann können wir dieses Seil, dieser Anker, unser Haupt, tatsächlich an, was der erste ist, der auf weisen. So dieser Kopf tatsächlich auf dem zweiten Element jetzt. Jetzt dürfen wir befreien, was wird in temp gespeichert, und so können wir, dass ohne sie zu gefährden alle anderen Knoten in unserer Liste zu löschen. Ein anderer Weg, dass man dies tun könnte jedes Mal, wenn Sie gerade befreien das letzte Element in der Liste weil sie gewährleistet sind nicht auf etwas hingewiesen werden. So könnten Sie einfach befreien diese ein, dann frei diese, dann frei diese. Das funktioniert auf jeden Fall aber ist ein bisschen langsamer, weil durch die Art der verkettete Listen, können wir nicht einfach sofort an die letzte springen. Wir müssen jedes Element in der Liste zu durchqueren und prüfen, ob dass man zeigt auf NULL, überprüfen Sie jedes Mal, und dann noch einmal erreichen wir das Ende, dann frei, dass. Wenn Sie diesen Prozess zu tun, würden Sie tatsächlich hier werden überprüft, Prüfen Sie hier, dann überprüfen Sie hier, befreien ihn, dann zurück, Prüfen Sie hier, Prüfen Sie hier, befreien ihn, Prüfen Sie hier, und dann befreien sie. Das dauert ein bisschen mehr Zeit. Yeah. 

[Schüler] Wäre es möglich, eine verkettete Liste, die eine Ausfahrt Zeiger speichert bis zum Ende zu machen? Das wäre auf jeden Fall möglich sein. Um die Frage zu wiederholen, ist es möglich, eine verknüpfte Liste Struktur haben so dass Sie einen Zeiger an das Ende der Liste zu haben? Ich würde sagen, dass das möglich ist, und jedes Mal, dass Sie etwas einfügen in Ihre verknüpfte Liste Sie müssten den Zeiger und solche Sachen zu aktualisieren. Sie müssten einen Knoten * tail, zum Beispiel. Aber wenn du Implementierung dieser Funktion müssen Sie die Trade-offs denken, wie, wie oft soll ich über diese werden Iteration, Wie schwierig ist es sein wird, den Überblick über den Schwanz sowie die Kopf bewahren sowie meine Iterator und solche Dinge. Heißt das -? >> [Schüler] Yeah. Es ist möglich, aber in Bezug auf Design-Entscheidungen, müssen Sie die Optionen abwägen. 

Hier ist ein Grundgerüst des Codes, mit denen Sie jedes Element in einer verketteten Liste befreien würde. Wieder, da ich über eine verknüpfte Liste durchlaufen, ich gehen zu wollen, um irgendeine Art von Cursor haben oder Iterator. Wir durchlaufen, bis der Cursor NULL. Sie wollen nicht zu durchlaufen, wenn der Cursor ist NULL , weil das bedeutet, dass es nichts in der Liste. Also hier mache ich eine temporäre Knoten * zeigt auf, was ich überlege ist das erste auf meiner Liste, und dann bewege ich meinen Mauszeiger vor 1 und dann frei, was ich in dem temporären Speicher hatte. 

Nun kommen wir zum Einsetzen in verkettete Listen kommen. Ich habe drei Knoten in meiner verketteten Liste, und lassen Sie uns mit dem einfachen Fall gehen wo wir einen anderen Knoten am Ende unserer verketteten Liste einfügen möchten. Um dies zu tun, ist alles, was wir tun würden wir durchqueren um herauszufinden, wo die aktuelle Ende der verketteten Liste ist, so je nachdem Knoten zeigt auf NULL - das ist das ein - und dann sagen, eigentlich, dieser wird nicht der letzte Knoten sein; wir eigentlich los, um eine andere zu haben. So würden wir diesen Strom ein Punkt, was wir Einlegen haben. So, jetzt diese rote Person hier wird der letzte Knoten in der verketteten Liste. Und so die Charakteristik der letzten Knoten in der verketteten Liste ist, dass es auf NULL zeigt. Also, was wir tun müssen, ist gesetzt Dieser rote Kerl Zeiger auf NULL. There. 

Aber was, wenn wir wollten, um einen Knoten zwischen dem zweiten und dritten einfügen? Dass man nicht ganz so einfach, weil wir sicherstellen wollen, dass wir nicht loslassen beliebigen Knoten in unserem verketteten Liste. Was wir tun müssen, ist sicherzustellen, dass wir uns zu verankern, um jeden einzelnen. Zum Beispiel, nennen wir diese die zweite. Wenn Sie sagen, die zweite zeigt nun auf diesem neuen und Sie gerade einen Zeiger gibt, dann wäre das in dieser Kerl verloren führen denn es gibt keine Verbindung zu ihm. Stattdessen - ich werde dies wieder zu zeichnen. Entschuldigen Sie meine künstlerischen Fähigkeiten. Wir wissen, dass wir nicht nur einen direkten Link 2 auf den neuen. Wir müssen sicherstellen, dass wir auf dem letzten zu halten. Was könnten wir tun möchten, ist eine temporäre Zeiger auf das Element, gehen auf angehängt ist. Also haben wir eine temporäre Zeiger gibt. Da wir wissen, dass diese dritte wird Spur gehalten, 2 kann nun zu unserem neuen zu verbinden. Und wenn dieser neue rote Kerl sein wird zwischen 2 und 3, was dann ist der Kerl den Zeiger gehen, um zu zeigen? >> [Schüler] Temp. Temp. Yeah. Also dieser rote Kerlchen nächste Wert wird Temp sein. Wenn Sie in verkettete Listen einfügen, sahen wir, dass wir konnten einfach noch etwas bis zum Ende durch die Schaffung eines temporären Array zu, oder wenn wir wollten etwas in der Mitte unserer Array hinzuzufügen, dann würde ein bisschen mehr herumschlurfenden. Wenn Sie wollen, zum Beispiel, haben einen sortierten verketteten Liste, dann müssen Sie Art wiegen die Kosten und Nutzen der, dass denn wenn man ein sortiertes Array haben wollen, bedeutet das, dass jedes Mal, wenn man in sie einzufügen, es geht um ein bisschen mehr Zeit in Anspruch nehmen. Allerdings, wenn Sie zu einem späteren Zeitpunkt wollen, wie wir finden, werden wir möchten, Suche in einer verketteten Liste, dann könnte es einfacher sein, wenn Sie wissen, dass alles in Ordnung ist. So möchten Sie vielleicht, um die Kosten und Nutzen der, dass wiegen. 

Ein weiterer Weg, um in einer verketteten Liste einzufügen, ist in das ganz am Anfang einer Liste einzufügen. Wenn wir unser Anker ziehen hier - das ist unser Kopf - und dann haben diese Leute mit ihm verbundenen und dann haben wir einen neuen Knoten in den Anfang eingefügt werden, was könnte dann wollen wir tun? Was wäre mit nur sagen, ich will den roten zum blauen Link falsch, denn das ist der erste? Was wäre hier geschehen? Alle diese drei verloren gehen würde. So wollen wir nicht, das zu tun. Auch haben wir gelernt, dass wir eine Art von temporären Zeiger haben müssen. Lasst uns wählen, um eine temporäre Punkt zu diesem Kerl haben. Dann können wir den blauen Punkt in den temporären haben und dann der rote Punkt auf den blauen. Der Grund, warum ich mit Menschen bin hier, weil wir wirklich wollen, zu visualisieren Festhalten an Menschen und dafür sorgen, dass wir einen Link zu ihnen haben bevor wir uns von einer anderen Hand oder so etwas. 

Jetzt, da wir haben einen Sinn für verkettete Listen - wie wir eine verkettete Liste erstellen und schaffen die Strukturen für diese aus der Typdefinition für einen Knoten und dann dafür sorgen, dass wir einen Zeiger auf den Kopf dieser verketteten Liste haben - einmal haben wir, und wir wissen, wie man durch eine Reihe durchqueren, Zugriff auf die verschiedenen Elemente, wissen wir, wie das Einsetzen und wir wissen, wie um sie zu befreien, dann können wir in Rechtschreibfehler zu bekommen. Wie üblich, haben wir einen Teil der Fragen, die Sie Betriebssystem erhalten mit verknüpften Listen verwendet und verschiedene Strukturen wie Warteschlangen und stapelt. Dann können wir in Rechtschreibfehler zu bewegen. 

Rechtschreibfehler hat bei der Verteilung Code ein paar Dateien von Bedeutung. Zunächst bemerken wir, dass wir dieses Makefile hier haben, welche wir noch nicht wirklich vor anzutreffen. Wenn Sie innerhalb der pset5 Ordner anschaust, wirst du feststellen, dass Sie eine. H-Datei haben, dann haben Sie zwei. c Dateien. Was dieses Makefile tut, ist vor, würden wir nur make eingeben und dann der Name des Programms und dann würden wir sehen, all diese Argumente und Flags in den Compiler. Was das Makefile tut, ist erlaubt uns, mehrere Dateien auf einmal zu kompilieren und in den Flaggen, die wir wollen passieren. Hier sehen wir nur gibt es eine Header-Datei hier. Dann haben wir eigentlich zwei Quelldateien. Wir haben speller.c und dictionary.c. Sie sind herzlich eingeladen, die Makefile bearbeiten, wenn Sie es wünschen. Beachten Sie, dass hier, wenn Sie saubere geben, dann, was es tut, ist tatsächlich entfernt nichts das ist der Kern. Wenn Sie einen Segmentation Fault hat, im Grunde erhalten Sie einen Core Dump. Also das hässliche kleine Datei wird in Ihrem Verzeichnis mit dem Namen Core erscheinen. Sie entfernen möchten, dass, um es zu reinigen. Es entfernt alle exe-Dateien und. O-Dateien. 

Werfen wir einen Blick in dictionary.h. Dieser sagt, dass es ein Wörterbuch der Funktionalität erklärt. Wir haben eine maximale Länge für jedes Wort im Wörterbuch. Wir sagen, dass dies wird die längste mögliche Wort sein. Es ist der Länge 45. Also werden wir nicht irgendwelche Worte, die diese Länge überschreiten müssen. Hier müssen wir nur noch die Funktionsprototypen. Wir haben nicht die tatsächliche Umsetzung, weil das ist, was wir für diese pset tun. Aber was dies bedeutet ist, da wir mit größeren Dateien zu tun haben hier und Funktionalität in einem größeren Maßstab, ist es sinnvoll, eine. h-Datei haben so, dass jemand anderes lesen oder mit Ihrem Code kann verstehen, was vor sich geht. Und vielleicht wollen sie umzusetzen versucht, wenn Sie Hash-Tabellen oder umgekehrt tat. Dann würden sie sagen, dass meine Ladefunktion, die tatsächliche Umsetzung wird unterschiedlich sein, aber dieser Prototyp wird sich nicht ändern. Hier haben wir überprüfen, welche true zurückgibt, wenn ein bestimmtes Wort im Wörterbuch. Dann haben wir Last, die im Grunde nimmt in einem Wörterbuch-Datei und lädt sie in eine Datenstruktur. Wir haben Größe, die, wenn sie aufgerufen wird, gibt die Größe des Wörterbuchs wieviele Wörter darin gespeichert sind, und dann entladen, das entlastet den gesamten Speicher, die Sie aufgenommen haben während Sie Ihr Wörterbuch. 

Werfen wir einen Blick auf dictionary.c. Wir sehen, dass es sehr ähnlich zu dictionary.h aussieht, außer jetzt muss es einfach all diese TODOs in ihm. Und damit ist Ihre Aufgabe. Irgendwann werden Sie werden Ausfüllen speller.c mit all diesen Code. Dictionary.c, wenn ausgeführt wird, wird nicht wirklich etwas zu tun, so blicken wir in Richtung speller.c, um die tatsächliche Umsetzung der Rechtschreibprüfung zu sehen. Auch wenn Sie nicht vorhaben zu der Bearbeitung der diesem Code es ist wichtig, zu lesen, zu verstehen, wenn die Last aufgerufen wird, wenn ich rufe Scheck, nur zu verstehen, ordnen Sie es aus, zu sehen, wie die Funktion arbeitet. Wir sehen, dass es für die korrekte Verwendung überprüfen. Im Wesentlichen, wenn jemand Speller läuft, bedeutet dies, dass es optional ist für sie in einem Wörterbuch-Datei übergeben, weil es geht um ein Standard-Wörterbuch-Datei sein. Und dann haben sie die im Text vorbei zu sein Rechtschreibprüfung überprüft. rusage befasst sich mit der Zeit, da ein Teil dieser pset die wir später beschäftigen ist nicht nur immer eine funktionierende Rechtschreibprüfung arbeitet aber tatsächlich bekommen es schnell zu sein. Und so dann ist das, wo rusage wird kommen in. Hier sehen wir den ersten Anruf zu einem unserer dictionary.c Dateien, die Last ist. Last gibt true oder false - true bei Erfolg, false bei einem Fehler. Also, wenn das Wörterbuch nicht geladen ist richtig, dann ist die speller.c gibt 1 zurück und beenden. Aber wenn es Last tut richtig, dann es geht weiter. Wir werden weiterhin, und wir sehen eine Datei I / O hier wohin es geht mit dem Öffnen der Textdatei zu tun haben. Hier, was dieser tut, ist die Rechtschreibprüfung prüft jedes einzelne Wort im Text. Also, was speller.c befindet sich direkt hier tun, ist die Iteration über jedes der Worte in der Textdatei und dann prüft sie im Wörterbuch. Hier haben wir einen Boolean falsch das wird sehen, ob Check true zurückgibt oder nicht. Wenn das Wort ist eigentlich im Wörterbuch, dann überprüfen Sie gibt true zurück. Das bedeutet, dass das Wort nicht falsch geschrieben. So falsch wäre falsch, und das ist, warum wir den Knall dort haben, die Anzeige. Wir machen weiter, und dann verfolgt, wie viele falsch geschriebene Wörter gibt es in der Datei. Es geht weiter auf und schließt die Datei. Dann ist hier, meldet er, wie viele falsch geschriebene Wörter, die Sie hatten. Es berechnet, wie viel Zeit es um das Wörterbuch zu laden stattfand, wie viel Zeit es brauchte, um zu überprüfen, wie viel Zeit es brauchte, um die Größe zu berechnen, die, wie wir weitermachen, sollte sehr klein sein, und dann, wie viel Zeit es brauchte, um das Wörterbuch zu entladen. Hier oben über uns den Aufruf hier entladen zu sehen. Wenn wir für die grösse hier zu überprüfen, dann sehen wir, dass hier ist der Ruf nach Größe, wo es bestimmt die Größe des Wörterbuchs. Awesome. 

Unsere Aufgabe für dieses pset ist die Last, die das Wörterbuch geladen werden umsetzen Datenstruktur - je nachdem, was Sie sich entscheiden, es ist ein Hash-Tabelle oder ein Versuch - mit Wörtern aus dem Wörterbuch-Datei. Dann haben Sie Größe, die die Anzahl der Wörter im Wörterbuch zurückkehren wird. Und wenn du Last auf intelligente Weise zu implementieren, dann die Größe sollte recht einfach. Dann haben Sie überprüfen, welche prüft, ob ein gegebenes Wort im Wörterbuch. So speller.c übergibt einen String, und dann haben Sie, ob diese Zeichenfolge zu überprüfen wird in Ihrem Wörterbuch enthalten. Beachten Sie, dass wir in der Regel Standard-Wörterbücher, aber in diesem pset, ging im Grunde jede Wörterbuch in in jeder Sprache. So können wir nicht einfach davon ausgehen, dass das Wort die drin ist. Das Wort FOOBAR könnte in einem bestimmten Wörterbuch definiert werden, dass wir in. vorbei Und dann haben wir entladen, welche befreit das Wörterbuch aus dem Speicher. 

Erstens würde Ich mag zu gehen über die Hash-Tabelle Verfahren wie könnten wir alle diese vier Funktionen zu implementieren, und dann werde ich gehen über das versucht, Methode, wie wir diese vier Funktionen zu implementieren, und am Ende reden einige allgemeine Tipps, wenn du machst das pset und auch, wie Sie vielleicht in der Lage sein zu verwenden Valgrind für Speicherlecks zu überprüfen. 

Lassen Sie uns in die Hash-Tabelle Methode zu erhalten. Eine Hash-Tabelle besteht aus einer Liste von Eimern. Jeder Wert, jedes Wort, wird in eine dieser Eimer gehen. Eine Hash-Tabelle im Idealfall gleichmäßig verteilt alle diese Werte, dass Sie im Vorbeigehen und füllt sie in den Eimer, so dass jeder Eimer hat etwa eine gleiche Anzahl von Werten verändern. Die Struktur für eine Hash-Tabelle, haben wir eine Reihe von verknüpften Listen. Was wir tun ist, wenn wir in einem Wert zu übergeben, prüfen wir, wo dieser Wert gehören sollte, die Eimer er gehört, und dann legen Sie sie in der verketteten Liste mit dem Eimer verbunden. Hier, was ich habe, ist eine Hash-Funktion. Es ist ein int Hash-Tabelle. Also für den ersten Eimer, irgendwelche Zahlen unter 10 in den ersten Eimer gehen. Beliebige ganze Zahlen über 10, aber unter 20 gehen in die zweite, und dann so weiter und so fort. Für mich ist jede Schaufel repräsentieren diese Zahlen. Allerdings sage ich waren in 50 passieren, zum Beispiel. Es scheint, als ob die ersten drei eine Reihe von zehn Zahlen enthalten. Aber ich möchte, dass meine Hash-Tabelle in irgendeiner Art von Zahlen zu nehmen, so dann hätte ich herausfiltern alle Nummern über 30 in den letzten Eimer. Und so dann wäre das in einer Art von unsymmetrischen Hash-Tabelle führen. Um es zu wiederholen, ist eine Hash-Tabelle nur ein Array von Eimern wo jeder Eimer ist eine verkettete Liste. Und so zu bestimmen, wo jeder Wert geht, welche bucket es in geht, Sie gehen zu wollen, was heißt eine Hash-Funktion das nimmt einen Wert und sagt dann entspricht dieser Wert einer bestimmten Eimer. So in diesem Beispiel oben, nahm meine Hash-Funktion jeden Wert. Überprüft wird, ob sie geringer als 10 war. Wenn ja, würde es in die erste Wanne gelegt. Es prüft, ob es weniger als 20 ist, bringt es in die zweite, wenn wahr, prüft, ob es weniger als 30, und dann ist es ausdrückt in den dritten Eimer, und dann alles andere fällt einfach auf die vierte Eimer. Also, wenn Sie einen Wert haben, Ihre Hash-Funktion diesen Wert in den entsprechenden Eimer platzieren. Die Hash-Funktion grundsätzlich muss wissen, wie viele Eimer haben. Ihre Hash-Tabelle Größe, die Anzahl der Buckets Sie haben, das wird sich eine feste Zahl, die bis zu Ihnen, für euch zu entscheiden sein, aber es wird um eine feste Zahl sein. Also Ihr Hash-Funktion auf, dass, um festzustellen, angewiesen sein, welche Eimer jede Taste geht in so dass es gleichmäßig ist verteilt. Ähnlich wie bei unserer Implementierung von verketteten Listen nun jeder Knoten in der Hash-Tabelle ist eigentlich los, um einen Typ char haben. Also haben wir ein char-Array als Wort und dann noch einen Zeiger auf den nächsten Knoten Das macht Sinn, weil es sich um eine verkettete Liste sein. Erinnern, wenn wir Listen hatten verbunden, machte ich einen Knoten * als Kopf das wurde an den ersten Knoten in der verketteten Liste zeigt. Aber für unsere Hash-Tabelle, weil wir mehrere verkettete Listen, was wir wollen, ist, dass wir wollen, dass unsere Hash-Tabelle zu sein wie: "Was ist ein Eimer?" Ein Eimer ist nur eine Liste von Knoten-Zeiger, und so jedes Element im Eimer ist eigentlich Hinweis auf seine entsprechenden verlinkten Liste. Um zurück zu dieser schematischen sehen Sie, dass die Eimer selbst die Pfeile sind, nicht die tatsächlichen Knoten. Eine wesentliche Eigenschaft von Hash-Funktionen ist, dass sie deterministisch sind. Das bedeutet, dass, wenn Sie Hash die Zahl 2, es sollte immer wieder den gleichen Eimer. Jeder einzelne Wert, der in der Hash-Funktion geht, wenn wiederholt, muss den gleichen Index. Also Ihr Hash-Funktion gibt den Index des Arrays wenn dieser Wert gehört. Wie ich schon erwähnt, ist die Anzahl der Buckets fest, und so Ihren Index, den Sie zurückkehren muss kleiner sein als die Anzahl der Buckets aber größer als 0 ist. Der Grund, warum wir Hash-Funktionen anstelle von nur einem einzigen verketteten Liste oder ein einzelnes Array ist, dass wir in der Lage sein, um einen bestimmten Abschnitt springen am leichtesten möchten wenn wir kennen die Charakteristik eines Wertes - anstatt durch das ganze gesamte Wörterbuch suchen, in der Lage, bis zu einem gewissen Teil von ihr zu springen. Ihre Hash-Funktion zu berücksichtigen, dass im Idealfall nehmen, jede Schaufel hat ungefähr die gleiche Anzahl von Tasten. Da die Hash-Tabelle eine Reihe von verknüpften Listen, dann die verkettete Listen selbst gehen, um mehr als einen Knoten haben. Im vorherigen Beispiel zwei verschiedene Zahlen, obwohl sie nicht gleich sind, wenn gehasht, zurückkehren würde den gleichen Index. Also, wenn Sie mit Worten zu tun haben, ein Wort, wenn gehasht würde die gleiche Hash-Wert als ein anderes Wort sein. Das ist das, was wir eine Kollision nennen, wenn wir einen Knoten, dass, wenn Hash haben, die verkettete Liste zu jener Eimer nicht leer ist. Die Technik, die wir nennen es lineares Sondieren, wo Sie in der Liste zu gehen und dann, wo Sie diesen Knoten einfügen möchten weil Sie eine Kollision. Sie können sehen, dass es einen Trade-off hier, nicht wahr? Wenn Sie einen sehr kleinen Hash-Tabelle, eine sehr kleine Anzahl von Eimern, dann wirst du eine Menge von Kollisionen haben. Aber dann, wenn Sie eine sehr große Hash-Tabelle, du bist wahrscheinlich die Kollisionen zu minimieren, aber es wird eine sehr große Datenstruktur sein. Es geht um Kompromisse sein damit. Also, wenn Sie, Ihre pset, versuchen, um zu spielen zwischen vielleicht machen eine kleinere Hash-Tabelle aber dann wissen, dass es geht um ein bisschen länger dauern, bis die verschiedenen Elemente durchlaufen dieser verknüpften Listen. 

Welche Belastung ist zu tun ist iterieren jedes Wort im Wörterbuch. Es geht in einen Zeiger auf die Wörterbuch-Datei. So wirst du die Vorteile der Datei übernehmen I / O-Funktionen, die Sie in pset4 gemeistert und durchlaufen jedes Wort im Wörterbuch. Sie wollen jedes Wort im Wörterbuch, um einen neuen Knoten geworden, und du wirst jeden dieser Knoten innerhalb Ihres Wörterbuchs Datenstruktur platzieren. Wenn Sie ein neues Wort zu bekommen, wissen Sie, dass es geht um ein Knoten geworden. So können Sie sofort gehen und malloc einen Knoten Zeiger für jedes neue Wort, das Sie haben. Hier rufe ich meinen Knoten Zeiger new_node und ich bin mallocing was? Die Größe eines Knotens. Dann lesen Sie die aktuelle Zeichenkette aus einer Datei, weil das Wörterbuch tatsächlich gespeichert wird durch ein Wort und dann eine neue Linie, was wir nutzen können ist die Funktion fscanf, wobei Datei ist die Wörterbuch-Datei, die wir in sind vergangen, so ist es durchsucht die Datei nach einer Zeichenkette und Orte, die Zeichenfolge in das letzte Argument. Wenn Sie sich erinnern zurück zu einem der Vorträge, wenn wir über ging und Art der Schichten wieder auf dem CS50-Bibliothek geschält, sahen wir eine Implementierung von fscanf dort. Um zurück zu fscanf, haben wir die Datei, die wir aus der Lektüre, wir nach einer Zeichenkette in der Datei suchen, und dann sind wir Einlegen in hier habe ich new_node-> Wort, weil new_node ist ein Knoten Zeiger, nicht eine tatsächliche Knoten. Also ich sage new_node bin, möchte ich auf den Knoten zu gehen, dass es zu zeigen und weisen Sie dann diesen Wert zu Wort. Wir wollen dann das Wort und legen Sie sie in der Hash-Tabelle. Erkennen, dass wir new_node einen Knoten Zeiger aus Weil wir wissen wollen, was die Adresse des Knotens wenn wir stecken Sie es in, weil die Struktur der Knoten selbst, der Struktur, ist, dass sie einen Zeiger zu einem neuen Knoten haben. So was ist dann die Adresse dieses Knotens gehen zu zeigen? Diese Adresse wird new_node sein. Macht das Sinn, warum wir machen new_node einen Knoten * als einem Knoten dagegen? Okay. Wir haben ein Wort. Dieser Wert ist new_node-> Wort. Das enthält das Wort aus dem Wörterbuch, das wir wollen auf den Eingang. Also, was wir tun wollen, ist, dass wir wollen unsere Hash-Funktion auf dieser Saite nennen weil unsere Hash-Funktion in einem String und dann bringt uns eine ganze Zahl, wo diese Zahl ist der Index, wo hashtable an diesem Index stellt den Eimer. Wir wollen diesen Index zu nehmen und gehen Sie dann zu diesem Index der Hash-Tabelle und dann diese verketteten Liste, um den Knoten zu new_node einzufügen. Beachten Sie, dass auch immer Sie zu Ihrem Knoten einfügen möchten, ob es in der Mitte, wenn Sie es sortieren möchten oder am Anfang oder am Ende, so stellen Sie sicher, dass Ihre letzte Knoten zeigt immer auf NULL weil das der einzige Weg, dass wir wissen, wo das letzte Element der von uns verlinkten Liste ist. 

Wenn Größe eine ganze Zahl, die die Anzahl von Wörtern in einem Wörterbuch darstellt, dann ein Weg, dies zu tun, ist, dass, wenn eine Größe aufgerufen wir gehen durch jedes Element in unserem Hash-Tabelle und dann durch alle verknüpften Liste innerhalb der Hash-Tabelle iterieren und berechnen dann die Länge, dass Erhöhung unserer Zähler 1 um 1 erhöht. Aber jedes Mal, dass die Größe genannt wird, das geht eine lange Zeit in Anspruch nehmen Weil wir linear sein Sondieren jeden einzelnen verketteten Liste. Stattdessen, wird es um einiges leichter, wenn man im Auge behalten, wie viele Wörter übergeben werden in. Also, wenn Sie einen Zähler in Ihrem Ladefunktion dass Updates nach Bedarf, dann Zähler, wenn Sie es auf eine globale Variable in der Lage, nach Größe genutzt werden. Also, was Größe könnte einfach tun, ist in einer Zeile, nur wieder den Zählerstand, die Größe des Wörterbuchs, die Sie bereits mit der Last behandelt. Das ist, was ich meine, wenn ich sagte gemeint, wenn Sie laden zu implementieren auf eine hilfreiche Weise, dann die Größe sein wird recht einfach. 

So nun kommen wir zu überprüfen. Jetzt sind wir mit Worten zu tun aus dem eingegebenen Text-Datei, und so werden wir zu prüfen, ob alle diese Eingangsworte sind eigentlich im Wörterbuch oder nicht. Ähnlich Scramble, wollen wir für die Groß-/Kleinschreibung ermöglichen. Sie wollen sicherstellen, dass alle Wörter übergeben, obwohl sie gemischte sind, wenn sie mit String vergleichen genannt, gleichwertig sind. Die Wörter im Wörterbuch Textdateien sind eigentlich alle Kleinbuchstaben. Eine andere Sache ist, dass man davon ausgehen, dass jedes Wort in, jeder String übergeben, wird entweder alphabetisch oder Apostrophe. Apostrophes gehen, um gültige Worte im Wörterbuch. Also, wenn Sie ein Wort mit Apostroph S haben, ist, dass eine tatsächliche legitimen Wort in Ihrem Wörterbuch das wird zu einem der Knoten in Ihrer Hashtabelle sein. Überprüfen Sie arbeitet mit, wenn das Wort existiert, dann es hat in unserem Hashtabelle sein. Wenn das Wort in dem Wörterbuch, dann allen Wörtern in dem Wörterbuch in der Hash-Tabelle, also lasst uns für dieses Wort in der Hash-Tabelle. Wir wissen, dass wir seit unserer Hash-Funktion implementiert so dass jede eindeutige Wort immer auf den gleichen Wert gehasht, dann wissen wir, dass anstelle des Suchens durch unser ganzes gesamte Hash-Tabelle, Wir können tatsächlich finden die verknüpfte Liste, dass dieses Wort gehören soll. Wenn es im Wörterbuch wäre, dann wäre es in diesem Eimer sein. Was wir tun können, wenn Wort ist der Name unserer String übergeben in, Wir können nur Hash, dass Wort und Blick auf die verknüpfte Liste im Wert von hashtable [hash (Wort)]. Von dort aus, was wir tun können, ist, dass wir eine kleinere Teilmenge von Knoten für dieses Wort zu suchen, und so können wir durchqueren die verketteten Liste, anhand eines Beispiels aus zuvor in der exemplarischen Vorgehensweise und rufen Sie dann String auf das Wort zu vergleichen, wo der Cursor verweist, das Wort, und sehen, ob diejenigen zu vergleichen. Abhängig von der Art und Weise, dass Sie Ihre Hash-Funktion zu organisieren, wenn es sortiert, können Sie möglicherweise auf false ein bisschen früher zurückkehren, aber wenn es unsortierten ist, dann wollen Sie weiterhin durchquert Ihren verketteten Liste bis Sie das letzte Element der Liste. Und wenn Sie immer noch nicht das Wort von der Zeit, die Sie am Ende der verketteten Liste erreicht haben gefunden, das bedeutet, dass Sie Ihr Wort nicht im Wörterbuch vorhanden ist, und so das Wort ist ungültig, und Kontrolle sollte false zurück. 

Nun kommen wir zu entladen, wo wir alle Knoten, die wir malloc'd befreien wollen, so frei alle Knoten innerhalb unseres Hashtabelle. Wir gehen zu wollen, durchlaufen alle verknüpften Listen und kostenlos allen Knoten darin. Wenn Sie oben in der exemplarischen Vorgehensweise aussehen auf das Beispiel, wo wir eine verkettete Liste zu befreien, dann werden Sie wollen, um diesen Prozess für jedes Element in der Hash-Tabelle zu wiederholen. Und ich werde über diese gegen Ende der Komplettlösung zu gehen, aber Valgrind ist ein Tool, wo Sie sehen, wenn Sie richtig befreit haben können jeder Knoten, dass Sie malloc'd oder irgendetwas anderes, dass Sie malloc'd jede andere Zeiger. Also das ist, Hash-Tabellen, in denen wir eine endliche Anzahl von Schaufeln haben und eine Hash-Funktion, die einen Wert nehmen wird und weisen Sie dann diesen Wert zu einem bestimmten Eimer. 

Nun kommen wir zu Versuchen kommen. Versucht Art aussehen, und ich werde auch ziehen ein Beispiel. Grundsätzlich haben Sie eine ganze Reihe von möglichen Buchstaben, und dann, wenn Sie bauen ein Wort, Dieses Schreiben kann für ein Wörterbuch, um eine breite Palette von Möglichkeiten verknüpft werden. Einige Wörter beginnen mit C, dann aber mit A fortsetzen, aber andere weiter mit O, zum Beispiel. Ein Trie ist eine Art der Visualisierung alle möglichen Kombinationen von diesen Worten. Ein Trie wird den Überblick über die Reihenfolge der Buchstaben, die Wörter enthalten zu halten, abzweigenden wenn notwendig, wenn ein Buchstabe durch ein Vielfaches von Buchstaben folgen kann, und am Ende geben an jedem Punkt, ob das Wort gültig ist oder nicht denn wenn Sie die Rechtschreibprüfung das Wort MAT sind, MA Ich glaube nicht, ein gültiges Wort, aber MAT ist. Und so in Ihrem Trie, würde es zeigen, dass nach MAT das eigentlich ein gültiges Wort. Jeder Knoten im Trie wird eigentlich um eine Anordnung von Knoten Zeiger enthalten, und wir gehen zu müssen, insbesondere, 27 dieser Knoten Zeiger, ein für jeden Buchstaben im Alphabet sowie der Apostroph. Jedes Element in dem Array sich gehen, um zu einem anderen Knoten zeigt. Also, wenn dieser Knoten ist NULL, wenn es nichts nach, dass dann wissen wir, dass es keine weiteren Briefe in dieser Wortfolge. Aber wenn der Knoten nicht NULL ist, bedeutet dies, dass es mehr Briefe in diesem Brief Sequenz. Und dann ferner zeigt jeder Knoten, ob es das letzte Zeichen eines Wortes oder nicht. 

Gehen wir in Beispiel eines Trie gehen. Zuerst muss ich Platz für 27 Knoten in diesem Array. Wenn ich das Wort BAR - Wenn ich das Wort BAR und ich möchte, dass einzufügen, der erste Buchstabe B, so, wenn mein Trie leer ist, B ist der zweite Buchstabe des Alphabets, so werde ich wählen, um diese hier zu setzen an diesem Index. Ich werde B hier. B wird ein Knoten, der zu einem anderen Array aller möglichen Zeichen weist sein das kann nach dem Buchstaben B. folgen In diesem Fall bin ich mit dem Wort BAR Umgang, so A wird hier. Nach A, habe ich die Buchstaben R, so ist, dann A weist jetzt auf seine eigene Kombination, und dann R wird hier sein. BAR ist ein ganzes Wort, ja, dann werde ich R-Punkt zu einem anderen Knoten haben das sagt, dass dieses Wort gültig ist. Das Knoten wird sich auch um eine Anordnung von Knoten haben, aber diejenigen, könnte NULL sein. Aber im Grunde kann es so weitergehen. Das wird ein wenig klarer, wenn wir ein anderes Beispiel zu gehen, so einfach mit mir da zu tragen. Jetzt haben wir BAR Innenseite Wörterbuch. Jetzt sagen, wir haben das Wort BAZ. Wir beginnen mit B, und wir haben bereits B als einer der Briefe, die im Wörterbuch ist. Das ist mit A. gefolgt Wir haben A bereits. Aber dann statt, haben wir Z folgende. Also ein Element in unser Angebot wird Z, und so, dass man dann wird eine andere gültige Ende des Wortes zu verweisen. So sehen wir, dass A, wenn wir durch B weiter und dann, es gibt zwei verschiedene Optionen derzeit im Wörterbuch für Wörter, die mit B und A beginnen Sagen wir, wir wollten das Wort FOOBAR einzufügen. Dann würden wir einen Eintrag bei F. F ist ein Knoten, der zu einer ganzen Reihe zeigt. Wir würden O zu finden, gehen Sie auf O, O verknüpft dann eine ganze Liste. Wir würden B haben und dann weiter, hätten wir A und dann R. Also FOOBAR durchquert den ganzen Weg hinunter bis FOOBAR ist eine richtige Wort. Und so wäre dies ein gültiges Wort ist. Jetzt sagen unsere nächste Wort im Wörterbuch ist eigentlich das Wort FOO. Wir würden sagen, F. Was folgt, F? Ich eigentlich schon einen Platz für O, so werde ich auch weiterhin. Ich brauche nicht, um eine neue zu machen. Weiter. FOO ist ein gültiges Wort in diesem Wörterbuch, so dann werde ich, um anzuzeigen, dass dies gültig ist. Wenn ich meine Reihenfolge aufhören, das wäre richtig. Aber wenn wir weiter Sequenz von FOO auf B und hatte gerade foob ist foob nicht ein Wort, und das ist nicht als eine gültige angezeigt. In einem Trie haben Sie jeden Knoten angibt, ob es sich um ein gültiges Wort ist oder nicht, und dann jeder Knoten auch über eine Reihe von 27 Knotenzeiger , dass dann auf Knoten selbst. 

Hier ist eine Möglichkeit, wie Sie wollen, dies zu definieren. Allerdings nur in der Hash-Tabelle beispielsweise gerne, wo wir einen Knoten * Kopf hatte um den Beginn der von uns verlinkten Liste geben, sind wir auch gehen zu wollen, einen Weg zu wissen, wo der Anfang unserer Trie ist. Manche Leute nennen versucht Bäumen, und das ist, wo root kommt. So wollen wir die Wurzel unseres Baumes, um sicherzustellen, dass wir geerdet bleiben dorthin, wo unsere Trie ist. Wir haben bereits solche ging so, wie Sie über das Laden jedes Wort in das Wörterbuch denken konnte. Im Grunde für jeden Wort, das Sie gehen zu wollen, um durch Ihre Trie iterieren und zu wissen, dass jedes Element in der Kinder - wir Kinder in diesem Fall genannt - entspricht einem anderen Brief, sind Sie gehen zu wollen, um diese Werte zu überprüfen an diesem bestimmten Index, der dem Buchstaben entspricht. So denken den ganzen Weg zurück zu Caesar und Vigenere, wohl wissend, dass jeder Brief können Sie Art von Karte zurück an einen alphabetischen Index, auf jeden Fall von A bis Z wird ziemlich leicht zu einer alphabetischen Buchstaben zuzuordnen, aber leider sind Apostrophe auch ein anerkanntes Zeichen in Worte. Ich bin nicht einmal sicher, was die ASCII-Wert ist, also, dass, wenn Sie wollen, um einen Index zu entscheiden, ob Sie es entweder der erste sein wollen, finden oder die letzte, müssen Sie einen hart codierten Scheck, dass zu machen und dann setzte sich in Index 26, zum Beispiel. So, dann sind Sie die Überprüfung der Wert bei Kindern [i] wobei [i] entspricht, was Brief, den Sie gerade sind. Wenn das so ist NULL, dh, dass es momentan keine möglichen Buchstaben die sich aus diesem vorherigen Sequenz, so dass Sie gehen zu wollen, malloc und machen einen neuen Knoten und haben, dass Kinder [i] Punkt, um ihn so dass Sie zu schaffen - wenn wir einen Brief eingefügt in das Rechteck - so dass Kinder nicht NULL und Punkt in diesem neuen Knoten. Aber wenn das nicht NULL ist, in unserem Fall der FOO gerne wenn wir schon FOOBAR wir weiterhin, und wir sind nicht immer so einen neuen Knoten sondern nur die Einstellung is_word auf true am Ende dieses Wortes. 

Also nach wie vor, denn hier sind mit jedem Brief Umgang zu einer Zeit, es wird einfacher für Sie, für die Größe, anstatt zu berechnen und durch den ganzen Baum zu gehen und berechnen, wie viele Kinder habe ich und dann abzweigt, Erinnern, wieviele sind auf der linken Seite und auf der rechten Seite und solche Sachen, es geht um sehr viel einfacher für Sie wenn man nur im Auge behalten, wie viele Wörter Sie beim Hinzufügen wenn Sie mit Last zu tun haben. Und so ist, dann so groß kann nur wieder eine globale Variable der Größe. 

Nun kommen wir zu überprüfen. Gleichen Standards wie früher, wo wir für Groß-/Kleinschreibung zulassen möchten. Wie gut, gehen wir davon aus, dass die Saiten nur alphabetische Zeichen oder die Apostrophe weil die Kinder ist ein Array von 27 langen, so alle Buchstaben des Alphabets zuzüglich der Apostroph. Für den Check ist, was Sie tun möchten, Sie wollen an der Wurzel beginnen weil die Wurzel wird auf ein Array, enthält hinweisen alle möglichen Anfangsbuchstaben eines Wortes. Du wirst dort zu starten, und dann wirst du zu überprüfen, ist dieser Wert NULL ist oder nicht, denn wenn der Wert NULL ist, bedeutet dies, dass das Wörterbuch nicht alle Werte das enthalten, diesen Brief in dieser bestimmten Reihenfolge. Wenn es NULL, dann heißt das, dass das Wort sofort ist falsch geschrieben. Aber wenn es nicht NULL, dann können Sie auch weiterhin, sagen, dass erste Brief eine mögliche erste Buchstaben in einem Wort ist, so jetzt will ich überprüfen, ob der zweite Brief, dass Sequenz, ist in meinem Wörterbuch. So wirst du zum Index der Kinder des ersten Knotens gehen und prüfen, ob diese zweite Brief existiert. Dann wiederholen Sie diesen Prozess, um zu überprüfen, ob diese Sequenz gültig ist oder nicht innerhalb Ihrer Trie. Wenn der Knoten Kindern an diesem Index auf NULL, Sie wissen, dass diese Sequenz nicht existiert, aber dann, wenn Sie das Ende des Wortes, dass du eingegeben, dann wollen Sie nun überprüfen, dass ich diese Sequenz abgeschlossen und fand es in meinem Trie ist das Wort gültig ist oder nicht? Und so dann wollen Sie, dass der Check, und das ist, wenn, wenn du diese Sequenz gefunden, dann wollen Sie prüfen, ob das Wort gültig ist oder nicht da erinnere mich zurück in dem vorherigen Fall, dass ich, wo wir foob hatten zog, das war eine gültige Sequenz, die wir gefunden, war aber nicht eine tatsächliche gültiges Wort selber. 

Ebenso zum Entladen in den Versuchen Sie alle Knoten in Ihrem Trie entladen. Entschuldigung. Ähnlich den Hash-Tabellen, wo in entladen wir befreit alle Knoten, in den Versuchen wollen wir auch befreien alle Knoten. Entladen tatsächlich funktionieren einfachste von unten nach oben denn diese sind im Wesentlichen verkettete Listen. So wollen wir sicherstellen, dass wir halten, um alle Werte und frei alle von ihnen ausdrücklich. Was wirst du tun wollen, wenn Sie mit einem Trie arbeiten ist auf der Unterseite und freie möglichst niedrigen Knoten zuerst reisen und gehen Sie dann bis zu all diesen Kindern und dann frei all diejenigen, hinaufgehen und dann frei, etc. Art wie die sich mit der unteren Schicht des ersten Trie und dann gehen bis oben, wenn Sie alles befreit habe. Dies ist ein gutes Beispiel dafür, wo rekursive Funktion könnte sich als nützlich erweisen. Sobald Sie die untere Schicht des Trie befreit, dann rufen Sie Entladen auf dem Rest, darauf achten, dass Sie jeden Mini befreien - Sie können Art visualisieren als Mini-Versuche. So haben Sie Ihre Wurzeln hier. Ich bin nur zu vereinfachen, damit ich nicht haben, um 26 von ihnen ziehen. So Sie diese haben, und diese dann stellen Sequenzen von Wörtern wo all diese kleinen Kreise sind die Buchstaben, die gültige Sequenzen von Buchstaben sind. Lassen Sie uns einfach ein bisschen mehr fortsetzen. Was wirst du tun möchten, ist kostenlos unten hier und dann frei dies ein und dann freie dies ein am Boden, bevor Sie kostenlos die besten eins hier denn wenn du frei etwas in der zweiten Ebene hier dann wäre eigentlich diesen Wert hier zu verlieren. Deshalb ist es in Entladen für einen Trie, um sicherzustellen, dass Sie die unten befreien erste ist wichtig. Was möchten Sie vielleicht wird sagen, für jeden Knoten zu tun Ich möchte alle Kinder zu entladen. 

Jetzt, da wir über Entladen für die Hashtabelle Methode sowie der Trie Verfahren gegangen, wir gehen zu wollen, um Valgrind aussehen. Valgrind Sie mit den folgenden Kommandos auszuführen. Sie haben valgrind-v. Sie sind für alle Lecks überprüfen, wenn Sie Speller angesichts dieser bestimmten Text laufen weil Speller muss in einer Textdatei zu nehmen. So Valgrind läuft das Programm, sagen, wie viele Bytes Sie zugeteilt, wie viele Bytes Sie befreit, und es wird Ihnen sagen, ob Sie gerade genug befreit oder ob Sie nicht frei genug, oder manchmal kann man sogar über-frei, wie frei ein Knoten, ist bereits freigegeben und so wird es Sie zurück Fehler. Wenn Sie Valgrind benutzen, es wird Ihnen einige Nachrichten der angibt, ob du entweder weniger als genug befreit, gerade genug, oder mehr als genug Zeit. 

Ein Teil dieser pset, ist es freigestellt, um die Big Board herauszufordern. Aber wenn wir mit diesen Datenstrukturen Umgang es ist irgendwie lustig zu sehen, wie schnell und wie effizient Ihre Datenstrukturen sein könnte. Hat Ihr Hash-Funktion zu einer Menge von Kollisionen? Oder sind Ihre Daten Größe wirklich groß? Braucht es eine Menge Zeit zu durchqueren? Im Protokoll der Speller, gibt es, wie viel Zeit Sie laden zu verwenden, zu überprüfen, um Größe zu führen und zu entladen, und so sind diejenigen in The Big Board gepostet, wo Sie gegen Ihre Klassenkameraden zu konkurrieren und einige Mitarbeiter zu sehen, wer hat das schnellste Rechtschreibprüfung. Eine Sache, die Ich mag über den Hash-Tabellen beachten Sie würde ist, dass es einige ziemlich einfache Hash-Funktionen, die wir denken konnte. Zum Beispiel haben Sie 26 Eimer, und so jeden Eimer entspricht dem ersten Buchstaben in einem Wort, aber das geht in einer ziemlich unausgeglichenen Hash-Tabelle führen denn es gibt viel weniger Wörter, die mit X beginnen, als Start mit M, zum Beispiel. Ein Weg, um über Speller gehen, wenn Sie alle anderen Funktionen runter wollen, dann benutzen Sie einfach eine einfache Hash-Funktion in der Lage sein, um Ihre Code ausgeführt und dann gehen Sie zurück und ändern Sie die Größe Ihrer Hash-Tabelle und der Definition. Es gibt eine Menge von Ressourcen im Internet für Hash-Funktionen, und so für diese pset dürfen Sie Hash-Funktionen im Internet recherchieren für einige Tipps und Anregungen, solange Sie sicher zu zitieren, wo Sie es haben aus zu machen. Du bist willkommen, zu schauen und zu interpretieren einige Hash-Funktion, die Sie im Internet finden. Zurück zu, dass Sie vielleicht in der Lage sein zu sehen, ob jemand verwendet eine Trie ob ihre Umsetzung ist schneller als dein Hash-Tabelle oder nicht. Sie können zu den Big Board vorlegen mehrfach. Es zeichnen Ihre jüngsten Eintrag. Also vielleicht ändern Sie Ihre Hash-Funktion und dann feststellen, dass es eigentlich viel schneller oder viel langsamer als zuvor. Das ist ein bisschen wie ein unterhaltsame Art und Weise. Es gibt immer 1 oder 2 Mitarbeiter, die die langsamste mögliche Wörterbuch zu machen versuchen, so dass es immer Spaß zu sehen. 

Die Nutzung für die pset ist, dass Sie laufen Speller mit einem optionalen Wörterbuch und dann eine verbindliche Textdatei. Standardmäßig, wenn Sie laufen Speller mit nur einer Textdatei und geben Sie nicht ein Wörterbuch, es geht um das Wörterbuch Textdatei, die große eins verwenden im cs50/pset5/dictionaries Ordner. Dass man hat mehr als 100.000 Wörter. Sie haben auch ein kleines Wörterbuch, das wesentlich weniger Worte hat das CS50 hat für Sie gemacht. Sie können jedoch sehr leicht so stellen Ihr eigenes Wörterbuch wenn Sie wollen einfach nur in kleinen Beispielen zu arbeiten - zum Beispiel, wenn Sie gdb verwenden, und Sie kennen die spezifischen Werte dass Sie Ihre Hash-Tabelle zu kartieren wollen. So können Sie einfach Ihre eigenen Text-Datei nur mit BAR, BAZ, FOO und FOOBAR, machen, dass in einer Textdatei, trennen diejenigen mit jeweils 1 Zeile, und dann machen Sie Ihren eigenen Text-Datei, die buchstäblich enthält nur vielleicht 1 oder 2 Worte so dass Sie genau wissen, was die Ausgabe sollte. Einige der Probe Textdateien, die Big Board, wenn Sie Herausforderung läuft überprüfen sind Krieg und Frieden und eine Jane Austen Roman oder so ähnlich. Also, wenn Sie anfangen, ist es viel einfacher, eine eigene Text-Dateien zu machen das enthalten nur ein paar Worte oder vielleicht 10 so dass Sie kann vorhersagen, was das Ergebnis sein sollte und dann überprüfen Sie es dagegen, so dass mehr von einem kontrollierten Beispiel. Und so da wir mit der Vorhersage und Zeichnen Dinge um sich, einmal möchte ich Sie ermutigen, Stift und Papier weil es wirklich zu Ihnen mit diesem zu helfen - Zeichnen Sie die Pfeile, wie die Hash-Tabelle oder wie Ihr Trie aussieht, wenn Sie befreien etwas, wo die Pfeile gehen, Sie hielt sich an genug, siehst du alle Links verschwinden und fallen in den Abgrund des durchgesickert Speicher. Also bitte, bitte versuchen Sie, die Dinge ziehen, noch bevor Sie den Code schreiben runter. Zeichnen Sie die Dinge so, dass Sie verstehen, wie die Dinge laufen zu arbeiten weil ich dann garantieren, dass Sie in weniger Zeiger Durcheinander dort laufen. 

Gut. Ich wünsche Ihnen das Allerbeste und viel Glück mit diesem pset. Es ist wahrscheinlich das härteste. So versuchen, früh zu beginnen, ziehen Sie die Dinge, zeichnen Dinge aus, und viel Glück. Dies war Walkthrough 5. 

[CS50.TV]