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.