>> ROB BOWDEN Cześć.
Jestem Rob i hash niech to rozwiązanie się.
Więc idziemy do wdrożenia Ogólnie tabeli mieszania.
Widzimy, że struktura naszego węzła mieszania tabela będzie wyglądać tak.
Więc to będzie mieć słowo char Tablica długości size plus 1.
Nie zapomnij o 1 Ponieważ maksimum słowo w słowniku jest 45
znaków, a następnie jedziemy do Potrzebujemy jeden dodatkowy znak dla
odwrotny ukośnik 0.
>> A potem nasz tabeli mieszania w każdym wiadro będzie przechowywać
powiązana lista węzłów.
Nie robimy tu liniową próbkowania.
I tak, w celu podłączenia się do następnego elementem w wiadrze, musimy
węzeł struct * następny.
Więc to, co węzeł wygląda.
Teraz tutaj jest deklaracja naszej tabeli mieszania.
To będzie mieć 16.384 wiadra, ale liczba ta nie ma znaczenia.
I wreszcie będziemy mieć zmienna globalna hashtable_size, które
zaczynać się jako 0, i to będzie śledzić, jak wiele słów
były w naszym słowniku.
Dobrze.
>> Warto więc spojrzeć na obciążenia.
Więc zauważyć, że obciążenia, zwraca bool.
Powrót prawda, czy to z powodzeniem załadowany i false w przeciwnym wypadku.
I zajmuje const char * gwiazdkę słownik, który słownik
że chcemy otworzyć.
Więc to jest pierwsza rzecz, mamy zamiar zrobić.
Jedziemy do fopen słownika dla czytania, a my będziemy mieć
aby upewnić się, że udało się, więc jeśli powrócił NULL, to my nie
powodzeniem otworzyć słownik i musimy return false.
>> Ale zakładając, że tak skutecznie otwarte, to chcemy, aby przeczytać
słowniku.
Dlatego należy zachować pętli, dopóki nie znajdziemy niektórych powód, aby wyrwać się z tego
pętli, które zobaczymy.
Dlatego należy zachować pętli, a teraz idziemy malloc pojedynczego węzła.
I oczywiście, musimy kontrolę błędów ponownie więc jeśli mallocing nie udało
i chcemy rozładować dowolny węzeł, że się do malloc przed zamknij
słownik i return false.
>> Ale pomijając, że przy założeniu, że udało, to chcemy wykorzystać fscanf
przeczytać ani jednego słowa od naszych słownika do naszego węzła.
Więc pamiętać, że wejścia-> słowo jest char Bufor słowo długości plus size
jeden, że będziemy przechowywać słowo w.
Więc fscanf zamierza powrócić 1 tak długo, jak to było w stanie z powodzeniem czytać
słowo z pliku.
>> Jeśli błąd się dzieje, albo czy możemy osiągnąć koniec pliku, nie będzie
zwraca 1, w którym to przypadku, jeśli tak nie jest zwraca 1, jesteśmy w końcu złamie
z tej pętli while.
Tak więc widzimy, że raz mamy powodzeniem czytać słowo w
entry-> słowo, następnie idziemy do mieszania słowo za pomocą naszej funkcji skrótu.
Rzućmy okiem na funkcja skrótu.
>> Tak naprawdę nie potrzebujesz aby to zrozumieć.
I rzeczywiście, po prostu wyciągnął to funkcji skrótu z internetu.
Jedyne, co trzeba uznać to że trwa const char * wyraz,
tak, to biorąc ciąg na wejściu i zwrócenie int jako wyjście.
Więc to wszystko funkcja skrótu jest, jest to odbywa się w wejściu, to daje
indeks w tabeli mieszania.
Zauważ, że jesteśmy modding przez NUM_BUCKETS więc wartość skrótu wrócił
faktycznie jest indeks w tabeli mieszania a nie indeks poza
granice tablicy.
>> Tak więc biorąc pod uwagę, że funkcja skrótu, jedziemy hash słowo, które czytamy
ze słownika, a następnie jedziemy w użyciu, że musi wstawić
Wejście w tabeli mieszania.
Teraz hashtable hash jest obecny powiązana lista w tabeli mieszania i
to jest bardzo możliwe, że jest po prostu NULL.
Chcemy wstawić nasz wpis w począwszy od tej związanej liście i dlatego
będziemy mieć naszą aktualną pozycję wskazują na to, co obecnie w tabeli mieszania
punkty, a potem jedziemy do przechowywania w tabeli mieszania w hash
aktualny wpis.
>> Tak więc te dwie linie z powodzeniem wstawić Wpis na początku
powiązana lista w tym indeksie w tabeli mieszania.
Kiedy skończysz z tym, wiemy, że znaleźliśmy inny wyraz w
słownik i zwiększamy ponownie.
Więc robić, że do fscanf wreszcie zwraca na coś non 1
który punkt należy pamiętać, że musimy wstęp wolny, więc tutaj, że malloced
Wpis i staraliśmy się przeczytać coś ze słownika.
A nie z powodzeniem czytać coś ze słownika, w którym
przypadku musimy uwolnić wpis, że nigdy nie umieścić w tabeli mieszania
i wreszcie przełamać.
>> Kiedy wybuchnie, musimy zobaczyć, dobrze, nie wyjdziemy, bo tam
został błąd odczytu z pliku, lub nie łamiemy, bo dotarliśmy
koniec pliku?
Jeśli był błąd, to chcemy return false, ponieważ obciążenie nie
sukces, w procesie, chcemy rozładować wszystkie słowa, które czytamy
i zamknąć plik słownika.
Zakładając, że nie uda, to po prostu jeszcze trzeba zamknąć słownika
złożyć, i wreszcie powrót prawda od my pomyślnie załadowany
słowniku.
I to jest to dla ładunku.
>> Więc teraz sprawdzić, ponieważ załadowany tabeli mieszania, będzie wyglądać tak.
Więc sprawdź, zwraca bool, który będzie wskazywać, czy
przeszedł w char * tekst, czy przekazywane w ciąg jest w naszym słowniku.
Jeśli więc w słowniku, jeśli jest to w naszej tabeli mieszania, wrócimy
prawda, a jeśli tak nie jest, wrócimy fałszywe.
Biorąc pod uwagę ten przeszedł w słowo, jesteśmy będzie hash słowo.
>> Teraz ważne jest, aby rozpoznać że obciążenia, wiedzieliśmy, że wszystkie
słowa miały być małe litery, ale tutaj, nie jesteśmy tak pewni.
Jeśli przyjrzeć się naszej funkcji skrótu, faktycznie nasza funkcja skrótu
każdy znak jest lowercasing słowa.
Tak więc bez względu na kapitalizację Słowo, nasza funkcja skrótu będzie
powrót ten sam wskaźnik dla co kapitalizacja jest jak miałoby to
wrócił do zupełnie małe wersja słowa.
Dobrze.
>> Tak, że nasz indeks.
To tabeli mieszania do tego słowa.
Teraz, to będzie na pętli się nad połączonej listy
, że był w tym indeksie.
Więc zauważyć, że wpis jest inicjowanie aby wskazać tym indeksie.
Jedziemy dalej, podczas gdy wejście nie nie równe NULL, i pamiętać, że
aktualizowania wskaźnika w naszej listy Wpis równa entry-> następny, więc mają
Nasz obecny punkt wejścia do Kolejnym punktem w połączonej listy.
Dobrze.
>> Więc dla każdego wpisu w połączonej listy, będziemy używać strcasecmp.
To nie strcmp ponieważ po raz kolejny, że chcą robić rzeczy, wielkość liter.
Więc używamy strcasecmp porównać słowo , który został przekazany do tej funkcji
do słowa, które w tej pozycji.
Jeśli zwróci 0, co oznacza, że ​​nie było Mecz, w którym to przypadku chcemy
return true.
Udało nam się znaleźć Słowo w naszej tabeli mieszania.
>> Jeśli nie było meczu, to jesteśmy będzie pętli ponownie i spojrzeć na
obok wejścia.
A my nadal zapętlenie podczas gdy są wpisy w tej połączonej listy.
Co się stanie, jeśli łamiemy z tego do pętli?
Oznacza to, że nie znaleźliśmy wpis, który pasuje to słowo, w którym to przypadku
my return false, aby wskazać, że nasz hash tabeli nie zawierają to słowo.
I to jest to do odprawy.
Dobrze.
>> Warto więc przyjrzeć się wielkości.
Teraz rozmiar będzie bardzo proste odkąd pamiętam w obciążeniu, dla każdego słowa
okazało się, że zwiększa się globalny Zmienna hashtable_size.
Więc rozmiar jest tylko funkcja powróci, że globalne
zmienne, i to jest to.
>> Teraz wreszcie, musimy rozładować Słownik raz wszystko się robi.
Więc jak mamy to zrobić?
Tu, jesteśmy w pętli na wszystko wiadra z naszej tabeli mieszania.
Tak więc istnieje NUM_BUCKETS wiadra.
I dla każdej połączonej listy w naszym hash Stół, jedziemy do pętli na
Całość połączonej listy uwalniając każdy element.
Teraz, musimy być ostrożni, więc tutaj mają tymczasową zmienną, która jest
przechowywania wskaźnika do następnego element połączony listy.
A następnie jedziemy do darmo bieżący element.
>> Musimy być pewni, że od kiedy to zrobić Nie można po prostu zwolnić bieżący element
a następnie spróbuj przejść do następnego wskaźnika od razu go uwolnił nas
Pamięć staje się nieważne.
Więc musimy zachować wokół wskaźnik do Kolejnym elementem, możemy uwolnić
bieżący element, a następnie możemy aktualizować nasz obecny element wskazać
Kolejnym elementem.
>> Będziemy pętli, podczas gdy istnieją elementy w tej połączonej listy.
Zrobimy to na wszystkich listach w powiązanych Tabela mieszania, a gdy już skończysz
się, że mamy całkowicie rozładowane Tabela mieszania, a skończymy.
Więc jest to niemożliwe dla odciążenia coraz return false, a kiedy skończymy, możemy
po prostu wrócić prawdziwe.