>> Sprecher 1: Geben wir diese Lösung versuchen.
Werfen wir also einen Blick auf das, was unsere Struct Knoten aussehen wird.
Hier sehen wir, wir gehen zu müssen, ein Bool Word und ein Struct Knoten Sterne
Kinder klammern Alphabet.
Also erste, was werden Sie vielleicht fragen, warum ist Alphabet Hash als 27 definiert?
Nun, denken Sie daran, dass wir gehen zu müssen, werden, um die Handhabung des Apostroph, so
das wird so etwas wie ein besonderes sein Fall dieses Programms.
>> OK, jetzt, daran erinnern, wie ein Trie tatsächlich funktioniert.
Lassen Sie uns sagen, dass wir die Indizierung der Wort Katzen, dann aus der Wurzel unserer Trie,
werden wir an die Kinder kümmern Array und wir werden bei der Suche
Index, die dem Buchstaben entspricht, C. Damit würde Index zwei sein.
Also da, dass wird uns ein neuer Knoten, und dann werden wir
arbeiten von diesem Knoten.
>> Also gegeben, dass der Knoten wieder einmal sind wir später in der Kinder-Array aus,
und wir werden mit dem Index Null aussehen auf die A in Katzen entsprechen.
So dann werden wir zu diesem Knoten zu gehen, und da Knoten, wir gehen
an der Index, entspricht aussehen 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 ist, wenn das Wort Katastrophe ist im Wörterbuch, aber
das Wort Katze nicht?
So in der Suche, um zu sehen, wenn das Wort Katze ist im Wörterbuch, werden wir
erfolgreich durch die Indizes suchen C-A-T und einen Knoten zu erreichen, aber das ist
nur, weil Katastrophe passiert erstellen Knoten auf dem Weg von C-A-T alle
die bis zum Ende des Wortes.
So Bool Wort wird verwendet, ob deuten diese besondere Lage tatsächlich
zeigt, ein Wort.
>> Na gut, so dass wir jetzt wissen, was für ein Trie wird wie, schauen wir uns freuen
auf der Load-Funktion.
So laden wird eine Bool zurück für, ob wir erfolgreich oder
erfolglos geladen und Wörterbuch das wird das Wörterbuch sein
dass wir wollen, laden.
Also erste, was wir tun werden, ist offen bis diesem Wörterbuch zum Lesen.
Wir müssen sicherstellen, dass wir nicht scheitern, Wenn das Wörterbuch nicht
erfolgreich geöffnet wurde, wird es zurück Nein, wobei in diesem Fall werden wir
False zurück.
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.
Nun wird Wurzel wird ein Knoten Stern.
Es ist die Spitze unserer Trie, dass wir sein werden, durch Iteration.
Also erste, was wir werden wollen zu tun ist, reservieren Speicher für unsere Wurzel.
>> Beachten Sie, dass wir mit der calloc Funktion, die im Wesentlichen die gleiche ist
als 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 ist eigentlich
erfolgreich.
Wenn diese wieder null, dann werden wir müssen unser Wörterbuch zu schließen
Datei-und Rück False.
So wurde unter der Annahme der Zuteilung erfolgreich ist, werden wir einen Knoten verwenden
Sterne-Cursor zu durchlaufen durch unsere Trie.
Also Root ist nie zu verändern, aber wir werden Cursor zu bedienen
tatsächlich gehen von Knoten zu Knoten.
>> Na gut, so dass in diesem For-Schleife, wir sind Lesen durch die Wörterbuchdatei,
und wir bei fgetc verwenden.
So fgetc wird zu schnappen Sie sich einen einzigen Zeichen aus der Datei.
Wir werden weiter greifen Zeichen, während wir nicht erreichen, die
am Ende der Datei, so gibt es beiden Fällen müssen wir umgehen.
Die erste, wenn das Zeichen kein neue Linie, so dass wir wissen, ob es eine neue
Linie, dann sind wir über den 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 dem ternären Operator hier, so werden wir lesen
dies, als ob der Charakter, den wir in las, war ein Apostroph, dann werden wir
gesetzt Index gleich Alphabet minus 1, die der Index 26 sein.
Else, wenn es nicht ein Apostroph, dann werden wir, um den Index gesetzt
gleich c minus ein.
Also denken Sie daran aus früheren p Sätze zurück, c abzüglich einer wird uns das zu geben
alphabetisch Position c, so dass, wenn c ist der Buchstabe A, dieser Wille
geben uns Index Null.
Denn der Buchstabe B, es geben würde, 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 die Kinder-Array, das bedeutet, dass
ein Knoten nicht aktuell vom existieren dieser Weg, so müssen wir vergeben ein
Knoten für diesen Pfad.
Das ist, was wir hier tun.
So werden wir, wieder, verwenden Sie die calloc Funktion, so dass wir nicht
auf Null aus alle Zeiger, und wir, wieder, müssen diese calloc überprüfen
nicht scheitern.
Wenn calloc hat scheitern, dann müssen wir um alles zu entladen, schließen unsere
Wörterbuch und False.
>> 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 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 um das Wort Katze zuzuordnen, und
das bedeutet, dass, wenn wir zu vergeben Katastrophe, brauchen wir nicht zu schaffen
Knoten für C-A-T wieder.
Sie existieren bereits.
>> OK, also 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 Struct-Knoten.
>> Wir wollen, dass auf True gesetzt, so dass bedeutet, dass der Knoten zeigt eine
erfolgreich ein Wort eigentliche Wort.
Nun eingestellt, 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 festgestellt, ein anderes Wort.
>> Na gut, also werden wir auch weiterhin tun dass Lesen im Zeichen von
Charakter, den Bau neuer Knoten in unsere Trie und für jedes Wort in der
Wörterbuch, zu erreichen, bis wir endlich c EOF gleich, in welchem ​​Fall, wir brechen
aus der Datei.
Nun gibt es zwei Fälle unter die wir vielleicht EOF getroffen haben.
Die erste ist, wenn es einen Fehler Lesen aus der Datei, so dass, wenn es
ein Fehler, den typischen tun müssen, wir Entladen alles, schließen Sie die Datei,
False zurück.
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 True zurück, da wir
das Wörterbuch erfolgreich geladen in unsere Trie.
>> Alle rechts, so jetzt wollen wir Besuche Check.
Mit Blick auf die Funktion prüfen, sehen wir Überprüfen Sie, dass wird eine Bool zurück.
Es gibt True zurück, wenn dieses Wort, dass es übergeben ist in unserem Trie.
Es gibt ansonsten False.
>> Also, wie sollen wir 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, wir werden durchlaufen über unsere gesamte Wort.
So Iteration über dem Wort sind wir übergeben, werden wir zur Bestimmung der
Index in der Kinder-Array, entspricht Wort Halterung i.
Also, das wird genau so aussehen Laden, wo, wenn Wort Halterung i ist eine
Apostroph, dann auf Index verwenden, wollen wir Alphabet minus 1, weil wir festgestellt,
das ist, wohin wir gehen Apostrophe speichern.
>> Else, wir werden tolower verwenden Wort Halterung i.
Also denken Sie daran, dieses Wort kann beliebige Kapitalisierung, und so haben wir
wollen sicherstellen, dass wir mit einen Kleinbuchstaben Version der Dinge.
Und dann von diesem Klein subtrahieren ein, um noch einmal, geben uns die
alphabetisch Position von diesem Charakter.
Also, das wird zu unserem Index sein in der Kinder-Arrays.
>> Und nun, 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, denn wenn es
wurden, das würde bedeuten, es wäre ein Pfad auf dieses 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 wäre, dann werden wir weiter Iteration, also werden wir
unsere Cursor zu aktualisieren, um zu zeigen, dass bestimmten Knoten an diesem Index.
>> Also wir halten, dass in das gesamte Wort.
Unter der Annahme, die wir nie getroffen null, das heißt Wir waren in der Lage, über den gesamten zu erhalten
Welt und finden Sie einen Knoten in unserem Trie, aber wir sind noch nicht ganz fertig.
Wir wollen nicht nur True zurück.
Wir wollen den Cursor Fehlerwort zurück da, daran erinnern, wieder, wenn Katze nicht
im Wörterbuch und Katastrophe, dann werden wir erfolgreich durchkommen
das Wort Katze, aber Cursor Wort False 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.
Also Größe sein wird, recht einfach da, daran erinnern, in Laden, wir sind
Erhöhen Wörterbuch Größe für jedes Wort, denen wir begegnen.
Also Größe ist gerade dabei, zurückzukehren Wörterbuch Größe, und das ist es.
>> Alle Rechte, so endlich, haben wir Entladen.
So entlasten, werden wir für eine rekursive Funktion, um tatsächlich alle tun
der Arbeit für uns, so dass unsere Funktion wird aufgerufen Unloader werden.
Was Unloader tun?
Wir sehen hier, dass Entlader wird sich laufen alle Kinder bei
Dieses spezielle Knoten, und wenn das Kind Knoten nicht null ist, dann werden wir
Entladen der untergeordneten Knoten.
>> Also das wird rekursiv entladen alle unsere Kinder.
Sobald wir sicher sind, dass alle unsere Kinder entladen haben, dann werden wir
kann uns befreien, uns selbst so zu entladen.
So wird dies rekursiv Entladen der gesamten Trie, und dann noch einmal, das ist
erledigt ist, können wir nur True zurück.
Entladen kann nicht umhin, wir sind nur Dinge zu befreien.
Also, wenn wir fertig sind befreit alles, True zurück.
Und das ist es.
Mein Name ist Rob, und dies war [unverständlich].