[MUSIC SPIEL] 

ROB BOWDEN: Hallo. Ich bin Rob. Und lassen Sie uns diese Lösung aus. Also hier werden wir umsetzen eine allgemeine Tabelle. Wir sehen, dass die Struktur der Knoten Tabelle wird wie folgt aussehen. Also es geht um einen char Wort haben Array der Größe LÄNGE + 1. Vergessen Sie nicht die + 1, da die maximale Wort in dem Wörterbuch 45 Zeichen. Und dann werden wir brauchen, eine zusätzliche Zeichen für den umgekehrten Schrägstrich Null. 

Und dann unsere Hash-Tabelle in jeder Eimer wird zu speichern, eine verkettete Liste von Knoten. Wir sind nicht hier, lineare Sondieren tun. Und so, um auf die nächste verlinken Element in den Eimer, brauchen wir eine struct node * next. OK. Also das ist, was ein Knoten aussieht. 

Nun, hier ist die Erklärung der Hash-Tabelle. Es geht um 16.834 Schaufeln haben. Aber diese Zahl ist nicht wirklich wichtig. Und schließlich werden wir haben die globale Variable Hash-Tabelle Größe, die wird zu starten als Null. Und es wird zu verfolgen, wie halten viele Wörter sind im Wörterbuch. 

Werfen wir also einen Blick auf Last. Beachten Sie, dass Last, gibt sie eine bool. Sie kehren dann, wenn es erfolgreich war geladen ist, und ansonsten false. Und es ein char * nimmt Wörterbuch, welches das Wörterbuch dass wir wollen, sich zu öffnen. Also das ist das erste, was wir tun werden. 

Wir werden die fopen Wörterbuch zum Lesen. Und wir gehen zu müssen, um sicher, dass es gelungen. Also, wenn es NULL zurückgegeben, dann haben wir nicht erfolgreich das Wörterbuch zu öffnen. Und wir müssen return false. Aber unter der Annahme, dass es erfolgreich war offen ist, dann lesen wollen wir die Wörterbuch. So halten Looping, bis wir einige Grund, um aus dieser Schleife zu brechen, was wir sehen. So halten Looping. 

Und jetzt sind wir zu gehen malloc eines einzelnen Knotens. Und natürlich brauchen wir an der Luft noch einmal überprüfen. Also, wenn mallocing nicht gelingt, dann wir einen beliebigen Knoten, die wir entladen möchten passiert malloc vor, schließen Sie die Wörterbuch-und Rück falsch. Aber ignorieren, dass, vorausgesetzt, wir gelang es, dann wollen wir nutzen fscanf ein einziges Wort aus lesen Sie unsere Lexikon in unsere Knoten. Also denken Sie daran, dass der Eintritt> Wort ist der char Wort Puffer der Größe LAENGE + 1 dass wir gehen, um das Wort zu speichern in. 

So fscanf wird zu 1 zurück, so lange, da es in der Lage, erfolgreich lesen Sie ein Wort aus der Datei. Wenn entweder ein Fehler passiert, oder wir erreichen das Ende der Datei, es 1 wird nicht zurückkehren. In diesem Fall ist es nicht wieder ein, wir endlich zu durchbrechen Diese while-Schleife. So sehen wir, dass, wenn wir erfolgreich haben lesen Sie ein Wort in entry> Wort, dann sind wir zu, dass geht Wort über unser Hash-Funktion. 

Werfen wir einen Blick auf die Hash-Funktion. So können Sie nicht wirklich brauchen um das zu verstehen. Und eigentlich haben wir nur diesen Hash gezogen Funktion aus dem Internet. Das einzige, was Sie brauchen, um zu erkennen, ist dass das dauert ein char * Wort. So ist es sie einen String als Eingabe und Rückgabe eines unsigned int als Ausgabe. Also das ist alles eine Hash-Funktion, ist es nimmt in einem Eingang und gibt Ihnen ein Index in die Hash-Tabelle. 

Beachten Sie, dass wir durch num_buckets Moding, so dass Wert zurückgegeben tatsächlich ist ein Index in die Hash-Tabelle und nicht über die Index Grenzen des Arrays. Also da Funktion, wir gehen das Wort, das wir lesen die Hash Wörterbuch. Und dann werden wir nutzen dass die Hash einfügen Eintritt in die Hash-Tabelle. 

Jetzt Hash Hash-Tabelle ist der aktuelle in der Tabelle verketteten Liste. Und es ist sehr gut möglich, dass es nur NULL. Wir wollen unseren Eintrag bei der einfügen Anfang dieses verketteten Liste. Und so werden wir unsere aktuellen haben Einstiegspunkt, was der Hash-Tabelle derzeit zeigt. Und dann werden wir zu speichern, in der Hash-Tabelle an die Hash, der aktuelle Eintrag. Also diese beiden Linien erfolgreich einfügen der Eintrag am Anfang der verketteten Liste an diesem Index in der Hash-Tabelle. 

Sobald wir damit fertig sind, wissen wir, dass wir fanden ein anderes Wort in der Wörterbuch, und wir wieder zu erhöhen. So halten wir tun, bis fscanf endlich wieder etwas Nicht-1 bei die Stelle daran erinnern, dass wir brauchen, um Eintrag zu befreien. Also hier haben wir malloced einen Eintrag. Und wir haben versucht, etwas zu lesen aus dem Wörterbuch. Und haben wir nicht erfolgreich gelesen etwas aus dem Wörterbuch, in welcher Fall müssen wir den freien Eintritt dass wir nie wirklich in die setzen Hash-Tabelle, und schließlich brechen. 

Sobald wir ausbrechen müssen wir sehen, na ja, haben wir ausbrechen, weil es wurde ein Fehler beim Lesen aus der Datei? Oder haben wir brechen, weil wir erreicht das Ende der Datei? Wenn es ein Fehler ist, dann wir wollen return false. Weil Last nicht gelungen. Und in dem Prozess, den wir entladen möchten alle Worte, die wir lesen in und schließen Sie die Wörterbuchdatei. 

Angenommen, wir haben, gelingt es uns nur noch brauchen, um das Wörterbuch zu schließen Datei, und endlich wieder wahr, da wir erfolgreich geladen das Wörterbuch. Und das ist es für die Last. So, jetzt zu prüfen, da eine geladene Hash-Tabelle, wird wie folgt aussehen. So überprüfen Sie, es gibt einen bool, das ist, gehen, um anzuzeigen, ob das übergebene char * in Wort, ob das übergebene in String im Wörterbuch. So dass, wenn es in dem Wörterbuch ist, wenn es in unserer Hash-Tabelle, wir true zurück. Und wenn es nicht, werden wir false zurück. 

Angesichts dieser in Wort übergeben, wir sind gehen, um das Wort Hash. Jetzt eine wichtige Sache zu erkennen ist dass in Last wir wussten, dass alle der Worten, wir werden klein geschrieben werden. Aber hier sind wir nicht so sicher. Wenn wir einen Blick auf unsere Hash-Funktion, unsere Hash-Funktion tatsächlich untere Gehäuse ist jedes Zeichen des Wortes. Also unabhängig von der Aktivierung von Wort, ist unser Hash-Funktion der Rück der gleiche Index für was auch immer der Kapitalisierung ist, wie es sein würde, für eine komplett in Kleinbuchstaben zurück Version des Wortes. In Ordnung. Das ist unser Index ist in der Hash-Tabelle für dieses Wort. 

Nun ist diese for-Schleife wird zu laufen der verketteten Liste das war an diesem Index. So bemerken wir Initialisierung Eintrag zu diesem Index zu verweisen. Wir werden weiterhin während Eintrag! = NULL. Und denken Sie daran, dass die Aktualisierung der Zeiger in unserem verketteten Liste entry = Eintrag> weiter. So haben unsere aktuellen Einstiegspunkt das nächste Element in der verketteten Liste. 

So dass für jeden Eintrag in der verketteten Liste, wir werden strcasecmp verwenden. Es ist nicht StrComp. Weil wieder einmal, wir wollen Dinge tun, ohne Berücksichtigung der Groß-/Kleinschreibung. So verwenden wir zum Vergleich die strcasecmp Wort, das durch diese übergeben wurde Funktion gegen das Wort das ist in diesem Eintrag. Wenn er Null zurückkehrt, bedeutet, dass es ein Spiel, in welchem ​​Fall wir wollen return true. Wir fanden die erfolgreich Wort in unserer Hash-Tabelle. 

Wenn es nicht ein Spiel, dann sind wir werde Schleife wieder und sehen Sie sich die nächsten Eintrag. Und wir werden Looping, während es weiterhin Einträge in dieser verketteten Liste. Was passiert, wenn wir brechen aus dieser for-Schleife? Das heißt, wir haben einen Eintrag nicht zu finden, die abgestimmt dieses Wort, in welchem ​​Fall wir false zurück, um anzuzeigen, dass unsere Hash-Tabelle nicht dieses Wort enthalten. Und das ist ein Scheck. 

Werfen wir also einen Blick auf Größe. Jetzt Größe sein wird, ziemlich einfach. Da erinnere mich, in Last, für jedes Wort wir fanden, wir erhöht, eine globale variable Größe Hash-Tabelle. Also die Größe Funktion wird nur gehen zu globalen Variablen zurück. Und das ist es. 

Nun endlich, wir müssen entladen, die Wörterbuch einmal alles fertig ist. Also, wie sollen wir das tun? Genau hier sind wir Schleifen über Alle Eimer unserem Tisch. So gibt es num_buckets Eimer. Und für jede verknüpfte Liste in unserem Hash-Tabelle, sind wir eine Schleife über gehen die Gesamtheit der verbundenen Liste, jedes Element zu befreien. 

Jetzt müssen wir vorsichtig sein. So, hier haben wir eine temporäre Variable das ist das Speichern der Zeiger auf den nächsten Element in der verketteten Liste. Und dann sind wir frei gehen das aktuelle Element. Wir müssen sicher sein, wir tun dies, weil wir können nicht nur kostenlos das aktuelle Element und dann versuchen, die nächste Zeiger zuzugreifen, da, sobald wir davon befreit, der Speicher wird ungültig. 

Also müssen wir einen Zeiger auf herum zu halten das nächste Element, dann werden wir frei kann der aktuelle Element, und dann werden wir aktualisieren können unsere aktuelle Element zu Punkt das nächste Element. Wir werden während Schleife gibt es Elemente in dieser verketteten Liste. Wir werden das für alle verknüpft tun Listen in der Hash-Tabelle. Und wenn wir damit fertig sind, haben wir die Hash-Tabelle vollständig entladen und wir fertig sind. So ist es unmöglich, Entladen immer false zurück. Und wenn wir fertig sind, werden wir nur true zurück. 

Geben wir diese Lösung versuchen. Werfen wir also einen Blick auf das, was unsere struct Knoten aussehen wird. Hier sehen wir, wir werden einen bool haben Wort und eine struct node * Kinder Halterung Alphabet. Das erste, was Sie sein könnten frage mich, warum ist ALPHABET ed als 27 definiert? Nun, denken Sie daran, dass wir gehen zu müssen, werden, um die Handhabung des Apostroph. Also, das wird so etwas wie ein sein Sonderfall dieses Programms. 

Jetzt erinnere, wie ein Trie tatsächlich funktioniert. Lassen Sie uns sagen, dass wir das Wort der Indizierung "Katzen." Dann von der Wurzel des Trie werden wir an die Kinder kümmern Array und wir werden bei der Suche Index, die dem Buchstaben entspricht, C. So, die indiziert 2 wird. Also da, das wird geben uns einen neuen Knoten. Und dann werden wir von diesem Knoten zu arbeiten. 

Also gegeben, dass der Knoten wieder einmal sind wir später in der Kinder-Array zu suchen. Und wir werden bei Index Null aussehen auf die A in Katzen entsprechen. So dann werden wir zu diesem Knoten zu gehen, und da Knoten werden wir am Ende sehen, es ist eine, entspricht T. und Bewegen auf diesem Knoten, schließlich haben wir komplett ausgesehen haben durch unser Wort "Katze". Und jetzt bool Wort soll zeigen, ob Dieser gegebene Wort tatsächlich ein Wort. 

Warum also brauchen wir das Spezialfall? Nun, was das Wort "Katastrophe" ist im Wörterbuch, aber die Wort "Katze" ist es nicht? So und zu schauen, ob das Wort "Katze" wird im Wörterbuch, wir sind gehen, um erfolgreich durch zu schauen die Indizes C-A-T in der Region Knoten. Aber das ist nur, weil Katastrophe passiert, um Knoten auf dem Weg zu schaffen von C-A-T, bis hin zu das Ende des Wortes. So bool Wort wird verwendet, um anzugeben, ob diese besondere Lage tatsächlich zeigt ein Wort. 

Gut. So, jetzt wissen wir, was es ist Trie aussehen würde, schauen wir uns die Laden-Funktion. Also Last wird einen bool zurück für, ob wir erfolgreich oder erfolglos geladen das Wörterbuch. Und das wird das Wörterbuch sein dass wir wollen, laden. 

Also erste, was wir zu tun, ist offen bis diesem Wörterbuch zum Lesen. Und wir müssen dafür sorgen, wir nicht scheitern. Also, wenn das Wörterbuch nicht erfolgreich geöffnet wurde, wird es zurück null, wobei in diesem Fall sind wir werde return false. Aber unter der Annahme, dass es erfolgreich geöffnet, dann können wir tatsächlich lesen durch das Wörterbuch. 

Also erste, was wir zu gehen tun möchte, ist, dass wir dies globale Variable Wurzel. Jetzt Wurzel wird ein Knoten sein *. Es ist die Spitze unserer Trie, dass wir sein werden, durch Iteration. So ist die erste Sache, die wir gehen zu wollen, ist vergeben Speicher für Root. Beachten Sie, dass wir mit der calloc Funktion, die im Wesentlichen die gleiche ist wie die malloc-Funktion, außer es ist garantiert etwas, das ist zurück komplett auf Null gesetzt. Also, wenn wir malloc verwendet, würden wir brauchen, gehen durch alle Zeiger in unserem Knoten, und stellen Sie sicher, dass sie sind alle null. So calloc wird das für uns tun. 

Jetzt nur wie malloc, müssen wir sicherstellen, sicher, dass die Zuteilung war eigentlich erfolgreich. Wenn diese wieder null, dann werden wir müssen schließen oder Wörterbuch Datei-und Rück falsch. So wurde unter der Annahme, dass die Zuweisung erfolgreich ist, werden wir einen Knoten verwenden * Cursor durch unsere Trie laufen. Also unsere Wurzeln nie ändern, aber wir werden, um den Cursor zu bedienen tatsächlich gehen von Knoten zu Knoten. 

So in dieser for-Schleife wir lesen durch die Wörterbuchdatei. Und wir sind mit fgetc. Fgetc wird zu schnappen Sie sich einen einzigen Zeichen aus der Datei. Wir werden weiter greifen Zeichen, während wir nicht erreichen, die Ende der Datei. 

Es gibt zwei Fälle müssen wir umgehen. Der erste, wenn die Zeichen war nicht eine neue Zeile. So wissen wir, ob es eine neue Linie, dann wir sind dabei auf dem Weg zu einem neuen Wort. Aber angenommen, es war nicht eine neue Zeile, dann hier, um herauszufinden, wollen wir die Index wir gehen in den Index in der Kinder-Array, schauten wir uns vor. 

Also, wie ich schon sagte, müssen wir Sonderfall der Apostroph. Beachten Sie, wir sind mit den ternären Betreiber hier. So werden wir dies als, wenn lesen der Charakter, den wir in las, war ein Apostroph, dann werden wir gesetzt index = "Alphabet" -1, was wird sein, der Index 26. 

Else, wenn es nicht ein Apostroph, gibt wir gehen, um den Index gesetzt = c - a. Also denken Sie daran aus zuvor p-Sätzen zurück, c - a wird uns das zu geben alphabetische Position von C. Also, wenn C ist der Buchstabe A, das wird geben uns Index Null. Denn der Buchstabe B, wird es geben uns der Index ein, und so weiter. 

So gibt uns den Index in die Kinder Array, das wir wollen. Nun, wenn dieser Index ist derzeit null in Kinder, bedeutet das, dass ein Knoten noch nicht vorhanden ist aus diesem Pfad. Also müssen wir vergeben ein Knoten für diesen Pfad. Das ist, was wir hier tun. 

So werden wir wieder das calloc Funktion, so dass wir nicht haben, um Null aus, alle Zeiger. Und wir müssen wieder zu überprüfen, dass calloc nicht scheitern. Wenn calloc hat scheitern, dann müssen wir um alles zu entladen, schließen unsere Wörterbuch und false zurück. Also unter der Annahme, dass es nicht scheitern, dann dies wird ein neues Kind für uns zu schaffen. Und dann werden wir diesem Kind zu gehen. Unsere Cursor laufen auf das Kind. 

Nun, wenn dies nicht mit null zu beginnen, dann wird der Cursor gerade durchlaufen kann auf das Kind, ohne tatsächlich dass Sie etwas zuzuweisen. Dies ist der Fall, wenn wir zuerst passiert zuteilen, das Wort "Katze". Und das bedeutet, dass, wenn wir zu vergeben "Katastrophe", die wir nicht brauchen, um zu erstellen Knoten für C-A-T wieder. Sie existieren bereits. 

Was ist das sonst? Dies ist der Zustand, in der c Backslash-n, wobei c war eine neue Zeile. Das heißt, wir haben erfolgreich abgeschlossen Wort. Nun, was wir tun wollen, wenn wir erfolgreich ein Wort abgeschlossen? Wir werden dieses Wort Feld verwenden Innere unserer Struktur-Knoten. Wir wollen, dass auf true setzen. Damit anzeigt, daß dieser Knoten deutet auf eine erfolgreiche Wort, eine tatsächliche Wort. 

Nun setzen, dass auf true. Wir wollen unsere Cursor auf Punkt zurückgesetzt zu Beginn des Trie wieder. Und schließlich erhöhen Wörterbuch Größe, da wir fanden eine andere Arbeit. So werden wir weiterhin tun, dass, Lesen im Zeichen für Zeichen, Bau neuer Knoten in unserem Trie und für jedes Wort in dem Wörterbuch, bis erreichen wir schließlich C! = EOF, in der Fall brechen wir aus der Datei. 

Jetzt gibt es zwei Fälle unter die wir vielleicht EOF getroffen haben. Die erste ist, wenn es einen Fehler Lesen aus der Datei. Also, wenn es einen Fehler, wir müssen die typische tun. Entladen Sie alles, in der Nähe die Datei, return false. Angenommen, es war kein Fehler, dass bedeutet nur, dass wir tatsächlich das Ende der die Datei, in diesem Fall schließen wir die Datei-und Rück wahr, da wir erfolgreich geladen Wörterbuch in unsere Trie. 

So, jetzt bitte zuerst Prüfung lassen. Mit Blick auf die Check-Funktion, sehen wir , dass der Check wird eine bool zurück. Es liefert true, wenn dieses Wort, dass es übergeben ist in unserem Trie. Es gibt ansonsten false. Also, wie Sie ermitteln, ob Dieses Wort ist in unserer Trie? 

Wir sehen hier, dass, genau wie zuvor, wir gehen, um den Cursor zu verwenden, um laufen durch unsere Trie. Nun, hier werden wir durchlaufen über unsere gesamte Wort. So Iteration über dem Wort sind wir Vergangenheit, wir werden zur Bestimmung der Index in der Kinder-Array, entspricht Wort Klammer I. Also das wird genau so aussehen Last, wo, wenn Wort [i] ist ein Apostroph, dann möchten wir Index "ALPHABET" verwenden - 1. Da wir festgestellt, dass die ist, wohin wir gehen, um zu speichern Apostrophe. 

Else, wir werden zwei untere Wort verwenden Halterung I. Also denken Sie daran, dieses Wort kann willkürliche Kapitalisierung. Und so stellen Sie sicher, dass wir wollen, wir mit einem Kleinbuchstaben Version der Dinge. Und dann aus, dass 'a', einmal subtrahieren geben uns wieder die alphabetische Position dieses Charakters. Also, das wird zu unserem Index sein in der Kinder-Arrays. 

Und jetzt, wenn dieser Index in die Kinder Array null ist, bedeutet, dass wir kann nicht mehr weiter Laufen hinunter unsere Trie. Wenn das der Fall ist, kann nicht dieses Wort möglicherweise in unserem Trie sein. Da wäre es, würde das meine, es wäre ein Weg sein bis zu diesem Wort. Und Sie würden nie begegnen null. So stoßen null kehren wir falsch. Das Wort ist nicht im Wörterbuch. Wenn es nicht null waren, dann sind wir werde Laufen fortsetzen. 

Also werden wir dort Cursor bis zu diesem bestimmten Punkt Knoten an diesem Index. Wir halten, dass in das gesamte Wort, vorausgesetzt, wir nie getroffen null. Das heißt, wir waren in der Lage, um durchzukommen das gesamte Wort und finden ein Knoten in unserem Versuch. Aber wir sind noch nicht ganz fertig. 

Wir wollen nicht nur true zurück. Wir wollen Cursor> Wort zurück. Da wieder erinnern, ist "cat" nicht im Wörterbuch, und "Katastrophe" wird, dann werden wir erfolgreich wir durch das Wort "Katze". Aber Cursor Wort falsch und nicht wahr sein. Also haben wir Cursor Wort zurück, um anzuzeigen, ob dieser Knoten tatsächlich ein Wort. Und das ist es für den Check. 

Also lassen Sie uns prüfen, Größe. So Größe sein wird, recht einfach da, daran erinnern, in der Last, wir sind Erhöhen Wörterbuch Größe für jedes Wort, denen wir begegnen. Also Größe ist gerade dabei, Rückkehr Wörterbuch Größe. Und das ist es. 

So haben wir schließlich entladen. So entladen, werden wir für eine rekursive Funktion, um tatsächlich alle tun der Arbeit für uns. Also unsere Funktion wird sich auf Entlader bezeichnet werden. Was Entlader tun? Wir sehen hier, dass Entlader wird sich laufen alle Kinder bei Diese bestimmten Knoten. Und wenn der Kindknoten nicht null ist, dann werden wir Entladen der untergeordneten Knoten. 

Das ist also rekursiv Sie entladen alle unsere Kinder. Sobald wir sicher sind, dass alle unsere Kinder entladen haben, dann werden wir kann uns befreien, so entladen uns. Dies wird rekursiv arbeiten Entladen des gesamten Trie. Und dann, wenn das erledigt ist, wir können einfach true zurück. Entladen kann nicht scheitern. Wir stehen noch Dinge zu befreien. Also, wenn wir fertig sind befreit alles, true zurückgeben. Und das ist es. Mein Name ist Rob. Und das war Speller. 

[MUSIC SPIEL]