>> ROB BOWDEN: Hallo.
Ich bin Rob, und seien wir Hash diese Lösung aus.
Also hier werden wir umsetzen eine allgemeine Hash-Tabelle.
Wir sehen, dass die Struktur-Knoten der Hash Tabelle wird wie folgt aussehen.
Also es geht um einen char Wort haben Array der Größe Länge plus 1.
Vergessen Sie nicht die 1, da die maximale Wort in dem Wörterbuch 45
Zeichen, und dann werden wir brauchen ein zusätzliches Zeichen für die
0 Backslash.
>> Und dann unsere Hash-Tabelle in jeder Eimer wird zu speichern, eine
verkettete Liste von Knoten.
Wir sind hier nicht linear Sondieren tun.
Und so, um auf die nächste verlinken Element in den Eimer, brauchen wir eine
struct node * next.
Also das ist, was ein Knoten aussieht.
Nun, hier ist die Erklärung der Hash-Tabelle.
Es geht um 16.384 Eimer haben, aber diese Zahl ist nicht wirklich wichtig.
Und schließlich werden wir haben die globale Variable hashtable_size, die
wird zu starten als 0, und es ist gehen, um zu verfolgen, wie viele Wörter
waren im Wörterbuch.
Gut.
>> Werfen wir also einen Blick auf Last.
So bemerken, dass die Last, es gibt einen bool.
Sie kehren dann, wenn es erfolgreich war geladen und ansonsten false.
Und es dauert eine char * Sterne Wörterbuch, das das Wörterbuch
dass wir wollen, sich zu öffnen.
Also das ist das erste, was wir tun werden.
Wir werden das Wörterbuch für fopen Lesen, und wir gehen zu müssen
um sicherzustellen, dass es gelang so, wenn es NULL zurück, dann haben wir nicht
das Wörterbuch erfolgreich ö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, aus dieser zu brechen
Schleife, die wir sehen.
So halten Looping, und jetzt werden wir um einen einzelnen Knoten malloc.
Und natürlich, um Check-Fehler müssen wir wieder so, wenn mallocing war nicht erfolgreich
und wir, die wir jeden Knoten 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 Länge plus
eine, die wir gehen, um speichern Sie das Wort in.
So fscanf wird zu 1 zurück, so lange da es in der Lage, erfolgreich gelesen ein
Wort aus der Datei.
>> Wenn entweder ein Fehler passiert, oder wir erreichen das Ende der Datei, wird es nicht
1 zurückzukehren, in dem Fall, wenn es nicht 1 zurück, sind wir endlich zu brechen
aus dieser while-Schleife.
So sehen wir, dass, wenn wir erfolgreich haben lesen Sie ein Wort in
entry-> Wort, dann werden wir auf Such Wort, dass mit unserem Hash-Funktion.
Werfen wir einen Blick auf die Hash-Funktion.
>> So können Sie nicht wirklich brauchen um das zu verstehen.
Und tatsächlich, wir haben nur diese gezogen Hash-Funktion aus dem Internet.
Das einzige, was Sie brauchen, um zu erkennen, ist dass das dauert ein char * Wort,
so dass es sie einen String als Eingabe und Rückgabe eines unsigned int als Ausgabe.
Also das ist alles eine Hash-Funktion, ist es erfolgt in einem Eingabe, gibt es Ihnen eine
Index in die Hash-Tabelle.
Beachten Sie, dass wir durch num_buckets Modding so der Hash-Wert zurück
tatsächlich ist ein Index in die Hash-Tabelle, und nicht über die Index
Grenzen des Arrays.
>> Also da Hash-Funktion, werden wir das Wort, das wir lesen hash
aus dem Wörterbuch und dann werden wir zu bedienen, dass zu legen Sie die
Eintrag in der Hash-Tabelle.
Nun ist die aktuelle Hash-Hash-Tabelle Linked-List in der Hash-Tabelle, und
es ist sehr möglich, dass nur NULL ist.
Wir wollen unseren Eintrag bei der einfügen Anfang dieses verknüpfte Liste, und so
werden wir unsere aktuellen Eintrag haben zeigen auf, was der Hash-Tabelle derzeit
Punkte auf und dann werden wir speichern in der Hash-Tabelle in der 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 kehrt schließlich etwas nicht eins zu
die Stelle erinnern, dass wir Eintritt frei, so dass hier auf, malloced wir ein
Eintritt und wir haben versucht, etwas zu lesen aus dem Wörterbuch.
Und haben wir nicht erfolgreich gelesen etwas aus dem Wörterbuch in dem
Fall müssen wir den Eintrag, den wir frei nie wirklich in die Hash-Tabelle setzen
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 ausbrechen, weil wir erreicht
das Ende der Datei?
Wenn es ein Fehler ist, dann wollen wir return false, weil Last nicht
folgen, und in dem Prozess, wir wollen entladen all die 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 haben das erfolgreich geladen
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, die wird, um anzuzeigen, ob der
gebenen char * Wort, ob die gebenen String ist im Wörterbuch.
So dass, wenn es in dem Wörterbuch ist, wenn es in unserer Hash-Tabelle, werden wir zurückkehren
wahr, und wenn es nicht ist, wir false zurück.
Angesichts dieser übergebenen Wort, wir sind gehen, um das Wort Hash.
>> Nun, das ist eine wichtige Sache zu erkennen, dass in der Last, wussten wir, dass alle
die Worte wollten unteren Fall sein, aber hier sind wir nicht so sicher.
Wenn wir einen Blick auf unsere Hash-Funktion, unsere Hash-Funktion tatsächlich
wird auf die Schreibweise jedes Zeichen des Wortes.
Also unabhängig von der Aktivierung von Wort, ist unser Hash-Funktion zu gehen
geben den gleichen Index für was auch immer die Kapitalisierung ist, wie es hätte
für eine komplett in Kleinbuchstaben zurück Version des Wortes.
Gut.
>> Also das ist unsere Index.
Es ist die Hash-Tabelle für dieses Wort.
Nun, diese for-Schleife wird um die verknüpfte Liste über
das war an diesem Index.
So bemerken wir Initialisierung Eintrag zu diesem Index zu verweisen.
Wir werden weiterhin während Eintrag tut nicht gleich NULL, und denken Sie daran, dass
Aktualisierung der Zeiger in unserem verketteten Liste Eintrag gleich entry-> nächsten, so haben
unsere aktuellen Einstieg in die nächste Element in verketteten Liste.
Gut.
>> So dass für jeden Eintrag in der verketteten Liste, wir werden strcasecmp verwenden.
Es ist nicht strcmp weil wieder einmal, wir wollen die Dinge tun, ohne Berücksichtigung der Groß-/Kleinschreibung.
So verwenden wir strcasecmp, um das Wort zu vergleichen dass wir diese Funktion übergeben
gegen das Wort, dass ist in diesem Eintrag.
Wenn es 0 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 es für den Check.
Gut.
>> Werfen wir also einen Blick auf Größe.
Nun wird Größe wird ziemlich einfach da in Last erinnern, für jedes Wort
wir fanden wir eine globale erhöht Variable hashtable_size.
Also die Größe Funktion ist nur gehen, dass die globale zurückkehren
variabel, 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 über alle Looping Eimer unseren Hash-Tabelle.
So gibt es num_buckets Eimer.
Und für jede verknüpfte Liste in unserem Hash Tisch, wir eine Schleife über das Gehen
Gesamtheit der verketteten Liste jedes Element zu befreien.
Jetzt müssen wir vorsichtig sein, so dass wir hier eine temporäre Variable, ist
Speichern der Zeiger auf die nächste 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 zugreifen da, wenn wir es befreit die
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üpften Listen tun die Hash-Tabelle, und wenn wir fertig sind
mit, dass wir vollständig entladen haben die Hash-Tabelle, und wir sind fertig.
So ist es unmöglich, jemals entlädt false zurück, und wenn wir fertig sind, werden wir
nur true zurück.