[MUZYKA GRA] 

ROB BOWDEN Cześć. Jestem Rob. I niech to rozwiązanie się. Więc idziemy do wdrożenia ogólnego zestawienia. Widzimy, że węzeł struktura naszych stron tabela będzie wyglądać tak. Więc to będzie mieć słowo char Tablica o rozmiarze size + 1. Nie zapomnij o + 1, gdyż maksymalna słowo w słowniku jest 45 znaków. I wtedy będziemy potrzebować jeden dodatkowy znaków dla zera backslash. 

, A następnie w każdym naszym hashtable 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. OK. Więc to, co węzeł wygląda. 

Teraz tutaj jest deklaracja naszego hashtable. To będzie mieć 16.834 wiader. Ale ta liczba nie ma znaczenia. I wreszcie będziemy mieć zmienna globalna wielkość hashtable, które zaczynać się jako zero. I to będzie śledzić, jak wiele słów są w naszym słowniku. 

Warto więc spojrzeć na obciążenia. Zauważ, że obciążenie, zwraca bool. Powrót prawda, czy to z powodzeniem załadowany, a false w przeciwnym wypadku. I zajmuje const char * słownika który słownik że chcemy otworzyć. Więc to jest pierwsza rzecz, mamy zamiar zrobić. 

Jedziemy do fopen słownik do czytania. I będziemy musieli dokonać pewien, że to się udało. Więc jeśli zwrócony NULL, to 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 tej pętli, które zobaczymy. Dlatego należy zachować pętli. 

A teraz mamy zamiar malloc pojedynczego węzła. I oczywiście musimy wietrzyć sprawdzić ponownie. Więc jeśli mallocing nie uda, to 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 o rozmiarze lenghth słowo + 1 że mamy zamiar przechowywać słowo w. 

Więc fscanf zamierza powrócić 1, tak długo, jak to było w stanie skutecznie czytaj słowo z pliku. Jeśli błąd się dzieje, albo, albo dotrzeć do końca pliku, to nie zwróci 1. W takim przypadku nie zwraca 1, mamy wreszcie będzie wyrwać się z to pętla while. Tak więc widzimy, że raz mamy powodzeniem czytać słowo w Wpis> słowo, następnie idziemy do tego 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ął ten hash funkcjonować z internetu. Jedyne, co trzeba uznać to że trwa const char * wyraz. Tak to trwa 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 i daje Indeks do hashtable. 

Zauważ, że my moding przez NUM_BUCKETS, tak, że wartość zwracana faktycznie jest indeks do hashtable a nie indeks poza granice tablicy. Tak więc biorąc pod uwagę, że funkcja, jedziemy hash słowo, które czytamy słowniku. A potem będziemy używać że hash wstawić Wejście w hashtable. 

Teraz hashtable hash jest obecny połączonej listy w tabeli. I to jest bardzo możliwe , że to jest po prostu NULL. Chcemy wstawić nasz wpis w począwszy od tego połączonej listy. I tak będziemy mieć nasz prąd punkt wyjścia do tego, co hashtable obecnie wskazuje. A następnie jedziemy do przechowywania, w hashtable w hash, aktualny wpis. Tak więc te dwie linie z powodzeniem wstawić Wpis na początku powiązana lista w tym indeksie w hashtable. 

Kiedy skończysz z tym, wiemy, że znaleźliśmy inny wyraz w słownik, a my ponownie zwiększyć. Więc robić, że do fscanf wrócił coś nie 1 na który punkt należy pamiętać, że musimy uwolnić wpis. Więc tutaj mamy malloced wpisu. I staraliśmy się przeczytać coś ze słownika. A nie z powodzeniem czytać coś ze słownika, w takim przypadku musimy uwolnić wpis że nigdy nie wprowadzony do hashtable i wreszcie przełamać. 

Kiedy wybuchnie musimy zobaczyć, dobrze, nie wyjdziemy, bo tam został błąd odczytu z pliku? Lub nie wyjdziemy, bo osiągnął koniec pliku? Jeżeli istnieje błąd, to chcemy return false. Ponieważ obciążenie nie udało. Oraz w procesie chcemy rozładować wszystkie słowa, które czytamy, i zamknij 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 kiedy pomyślnie załadowany słownik. I to jest to dla ładunku. Więc teraz sprawdzić, ponieważ załadowany hashtable, będzie wyglądać tak. Więc sprawdź, zwraca bool, który jest będzie wskazywać, czy przekazywane w char * tekst, czy przekazywane w ciągu jest w naszym słowniku. Jeśli więc w słowniku czy jest w naszym hashtable, wrócimy prawda. A jeśli nie, będziemy return false. 

Biorąc pod uwagę ten przeszedł w słowa, że ​​jesteśmy będzie hash słowo. Teraz ważne jest, aby rozpoznać że obciążenia wiedzieliśmy, że wszystkie Słowa Zamierzamy być małe. Ale tutaj nie jesteśmy tak pewni. Jeśli przyjrzeć się naszej funkcji skrótu, faktycznie nasza funkcja skrótu jest mniejsza obudowa każdy znak słowa. Tak więc bez względu na kapitalizację Słowo, nasza funkcja skrótu jest powrót sam wskaźnik dla co kapitalizacja jest, jak to ma wrócił do zupełnie małe wersja słowa. W porządku. To nasz indeks jest w hashtable dla tego słowa. 

Teraz to dla pętli będzie iteracyjne nad połączonej listy , że był w tym indeksie. Więc zauważyć, że wpis jest inicjowanie aby wskazać tym indeksie. Zamierzamy kontynuować natomiast wejście! = NULL. I pamiętaj, że aktualizację wskaźnika w naszej listy entry = Wpis> obok. Więc nasz aktualny punkt wejścia do Kolejnym punktem w połączonej listy. 

Więc dla każdego wpisu w połączonej listy, będziemy używać strcasecmp. To nie jest StrComp. Ponieważ po raz kolejny, że chcemy robić rzeczy, wielkość liter. Więc używamy strcasecmp porównać słowem, które przepuszczono przez to Funkcja do słowa to jest w tej pozycji. Jeśli powraca do zera, co oznacza, że ​​nie było Mecz, w którym to przypadku chcemy return true. Udało nam się znaleźć Słowo w naszym hashtable. 

Jeśli nie było meczu, to jesteśmy będzie pętli ponownie i spojrzeć na następny wpis. 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 hashtable nie zawierają to słowo. I to jest kontrola. 

Warto więc przyjrzeć się wielkości. Teraz rozmiar będzie bardzo proste. Ponieważ pamiętam w obciążeniu, dla każdego słowa okazało się, że zwiększa się globalny zmienny rozmiar hashtable. Więc funkcja rozmiar jest po prostu będzie powrót zmiennej globalnej. I to jest to. 

Teraz wreszcie, musimy rozładować Słownik raz wszystko się robi. Więc jak mamy to zrobić? Tutaj mamy pętli na wszystkie wiadra z naszego stołu. Tak więc istnieje NUM_BUCKETS wiadra. I dla każdej połączonej listy w naszym hashtable, jedziemy do pętli na Całość połączonej listy, uwalniając każdy element. 

Teraz musimy być ostrożni. Więc tutaj mamy zmiennej tymczasowej , który jest przechowywanie 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 kiedy już uwolnił go, 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 zawsze związane Wykazy w hashtable. A gdy już skończysz z tym, mamy Hashtable całkowicie rozładowane, a skończymy. Więc jest to niemożliwe do rozładunku kiedykolwiek zwróci false. A kiedy skończymy, możemy po prostu wrócić prawdziwe. 

Dajmy rozwiązanie to spróbować. Warto więc spojrzeć na to, co nasze węzeł struktura będzie wyglądać. Tutaj widzimy, będziemy mieć bool Słowo i węzeł struct * dzieci Uchwyt alfabetu. Tak więc pierwszą rzeczą, może być zastanawiasz się, dlaczego jest ALFABET wydanie zdefiniowane jako 27? Cóż, pamiętaj, że będziemy potrzebować do obsługi apostrof. Tak, że będzie nieco od Szczególnym przypadkiem w całym programie. 

Teraz pamiętam, jak trie faktycznie działa. Powiedzmy, że mamy do indeksowania słowo "koty". Następnie z korzenia trie, będziemy patrzeć na dzieci macierz, i mamy zamiar spojrzeć na Indeks, który odpowiada na list C. Tak więc, która jest indeksowana 2. Tak więc biorąc pod uwagę, że wola dać nam nowy węzeł. A potem będziemy pracować z tego węzła. 

Tak więc biorąc pod uwagę, że węzeł, po raz kolejny jesteśmy będzie wyglądać na tablicy dzieci. I będziemy patrzeć na indeksie zerowym odpowiadać A u kota. Tak więc mamy zamiar udać się do tego węzła, i biorąc pod uwagę, że węzeł jedziemy patrzeć na koniec, że to odpowiada do T. i przeniesienie się do tego węzła, w końcu mamy zupełnie wyglądał przez nasze słowo "kot". A teraz bool Słowo ma wskazać, czy to dane słowo jest w rzeczywistości słowo. 

Więc po co nam ten szczególny przypadek? No i co z tego słowa "katastrofa" jest w naszym słowniku, ale słowo "kot" nie jest? Tak i patrzy, czy słowo "kot" jest w naszym słowniku, jesteśmy będzie skutecznie przeglądać Wskaźniki C-węzeł-T w regionie. Ale to tylko dlatego, że katastrofa się do tworzenia węzłów na drodze z C-A-T, aż do koniec słowa. Więc bool słowo to jest używane do wskazania, czy ta konkretna lokalizacja faktycznie oznacza słowo. 

Dobrze. Więc teraz, że wiemy, co to jest Trie będzie wyglądać, przyjrzyjmy funkcję ładowania. Więc obciążenie będzie powrócić bool do tego, czy uda nam się lub bezskutecznie załadowany słownik. I to ma być słownik które chcemy załadować. 

Tak więc pierwszą rzeczą, że jesteśmy zrobić, to otworzyć do tego słownika do czytania. I musimy się upewnić, nie powiedzie się. Tak więc, jeśli nie słownika pomyślnie otwarty, zwróci null, w tym przypadku mamy będzie return false. Ale zakładając, że z powodzeniem otwarte, to rzeczywiście możemy przeczytać przez słownika. 

Tak więc pierwszą rzeczą, którą mamy zamiar chcę zrobić, to musimy to zmienna globalna korzeń. Teraz głównym będzie węzeł *. To jest szczyt naszej trie, że jesteśmy będzie iteracja. Tak więc pierwszą rzeczą, że idziemy chce zrobić to przeznaczyć Pamięć dla naszego korzenia. Zauważmy, że używamy calloc Funkcja, która jest zasadniczo taka sama jako funkcji malloc, oprócz tego, że jest gwarancją zwrotu, że coś jest całkowicie wyzerowany. Więc jeśli kiedyś malloc, musielibyśmy przejść przez wszystkie wskaźniki w naszym węzeł, i upewnij się, że wszystkie są puste. Więc calloc zrobi to za nas. 

Teraz, podobnie jak malloc, musimy dokonać upewnić się, że podział był rzeczywiście sukces. Jeśli ten wrócił null, wówczas należy zamknąć lub słownik złożyć i return false. Tak więc przy założeniu, że podział został sukces, będziemy korzystać z węzła * kursor do iteracji naszej trie. Więc nasze korzenie nigdy nie zmieni, ale mamy zamiar użyć kursora do faktycznie przejść od węzła do węzła. 

Więc to dla pętli przegląda za pomocą pliku słownika. I używamy fgetc. Fgetc będzie chwycić wolny znaków z pliku. Zamierzamy kontynuować pobieranie znaków, a my nie docierają koniec pliku. 

Istnieją dwa przypadki, które musimy obsłużyć. Po pierwsze, jeśli charakter nie nowa linia. Więc wiemy, czy to nowa linia, a następnie mamy zamiar przenieść się do nowego słowa. Ale zakładając, że nie był to nowa linia, a następnie tutaj, chcemy dowiedzieć się, Indeks jedziemy do indeksu w W tablicy dzieci, które przyjrzeliśmy się wcześniej. 

Tak, jak powiedziałem wcześniej, musimy Szczególnym przypadkiem apostrof. Zauważ, że używamy trójskładnikowej Operator tutaj. Więc mamy zamiar przeczytać jak, jeśli Czytamy w charakter był apostrof, następnie idziemy do ustawienia index = "alfabet" -1, która będzie być indeks 26. 

Inny, gdyby nie apostrof, nie mamy zamiar ustawić wskaźnik równa c -. Więc pamiętaj, powrót z poprzednio P-set, c - ma dać nam Stanowisko alfabetyczny C. Więc jeśli C jest literą, to będzie daje nam indeks zerowy. Do litery B, to daje us indeks 1, i tak dalej. 

Więc to daje nam wskaźnik do dzieci tablica, że ​​chcemy. Teraz, jeśli wskaźnik ten jest obecnie wartość null w dzieci, co oznacza, że ​​węzeł obecnie nie istnieje z tej ścieżki. Dlatego musimy przeznaczyć Węzeł na tej drodze. To co zrobimy tutaj. 

Więc mamy zamiar ponownie użyć calloc Funkcja, dzięki czemu nie mamy do wyzerować wszystkie wskaźniki. I znów trzeba sprawdzić że calloc nie zawiódł. Jeśli calloc zawiódł, to musimy wyładować wszystko, zamykać słownik i zwraca fałsz. Tak więc przy założeniu, że nie uda, to stworzy nowe dziecko dla nas. , A następnie udamy się do tego dziecka. Nasz kursor iteracji w dół do tego dziecka. 

Teraz, jeśli nie jest to wartość null, aby rozpocząć, Następnie można po prostu iteracyjne kursor w dół do tego dziecka bez konieczności konieczności przeznaczyć nic. Jest to przypadek, w którym po raz pierwszy się przeznaczyć słowo "kot". I co oznacza, że ​​kiedy idziemy do przeznaczenia "Katastrofa", nie musimy stworzyć węzły dla C-A-T ponownie. One już istnieją. 

Co to jest inny? Jest to stan, w którym c było odwrotny ukośnik n, gdzie c to nowa linia. Oznacza to, że udało nam się zakończone słowo. Teraz to, co chcemy zrobić, gdy zakończone powodzeniem słowo? Zamierzamy wykorzystywać to pole słowo wewnątrz naszego węzła struct. Chcemy ustawić, że na true. Tak, że wskazuje, że węzeł wskazuje na sukces Słowo, rzeczywisty wyraz. 

Ustawiony, że na true. Chcemy przywrócić nasz kursor do punktu na początku trie ponownie. I w końcu, zwiększamy naszą słownika rozmiar, ponieważ okazało się, innej pracy. Więc będziemy dalej robić, że Czytaj w znak po znaku, budowy nowych węzłów oraz w naszym trie dla każdego słowa w słowniku, do momentu w końcu dotrzeć C! = EOF, w którym przypadku możemy wyrwać się z pliku. 

Teraz są dwie sprawy w toku które moglibyśmy trafić EOF. Pierwszym z nich jest, czy istnieje błąd czytanie z pliku. Więc jeśli nie było błędów, my Wystarczy typowy. Wyładować wszystko, blisko plik, return false. Przy założeniu, że nie był błąd, to po prostu oznacza, że ​​faktycznie hit koniec plik, w którym to przypadku, zamykamy pliku i zwraca true, ponieważ my pomyślnie załadowany słownik do naszego trie. 

Więc teraz niech sprawdzić czek. Patrząc na funkcję wyboru, widzimy że kontrola będzie powrócić bool. Zwraca true, jeśli to słowo, które jest były przekazywane jest w naszym trie. Zwraca false w przeciwnym wypadku. Więc jak można określić, czy to słowo jest w naszym trie? 

Widzimy tutaj, że, podobnie jak poprzednio, mamy zamiar użyć kursora do iteracji za pośrednictwem naszego trie. Teraz tu idziemy do iteracji w ciągu całego naszego słowa. Więc iterowanie słowem jesteśmy w przeszłości, zamierzamy ustalić Wskaźnik do tablicy, że dzieci odpowiada wspornika I. Tak więc słowo to będzie wyglądać dokładnie tak, jak obciążenia, w którym, jeśli słowo [i] jest apostrof, to chcemy używać indeksu "alfabet" - 1. Ponieważ stwierdziliśmy, że to gdzie jedziemy do przechowywania apostrofy. 

Jeszcze będziemy używać dwóch dolnych słowo Uchwyt I. Więc pamiętaj, że słowo może mieć dowolny kapitalizacji. A więc chcemy się upewnić, że jesteśmy stosując małą wersję rzeczy. I odejmujemy od tego "a" na raz ponownie daje nam alfabetyczne Stanowisko tego znaku. Tak, że to będzie nasz indeks do tablicy dzieci. 

I teraz, jeżeli indeks do dzieci tablicy jest null, co oznacza, że nie może już kontynuować Iterowanie w dół naszego trie. Jeśli tak jest, to słowo nie może może być w naszym trie. Ponieważ gdyby tak było, że byłoby znaczy nie będzie droga w dół do tego słowa. I nigdy nie spotkać null. Więc napotkania NULL, my return false. Słowa nie ma w słowniku. Gdyby nie to, null, to jesteśmy zamierza kontynuować Iterowanie. 

Więc będziemy się tam kursor aby wskazać, że szczególnie węzeł w tym indeksie. Mamy dalej robić, że w całym Całe słowo, zakładając nigdy nie trafić zerowy. Oznacza to, że udało nam się przejść przez całe słowo i znaleźć węzeł w naszej próbie. Ale nie całkiem jeszcze zrobić. 

Nie chcemy, aby tylko wrócić prawda. Chcemy wrócić kursora> słowo. Ponieważ pamiętam raz, jest "kot" nie jest w naszym słowniku, a "katastrofa" jest, to z powodzeniem możemy uzyskać przez słowo "kot". Ale kursor Słowo będzie fałszywe i nie prawdziwe. Więc wracamy do wskazania kursora słowo czy węzeł jest faktycznie słowo. I to jest to do odprawy. 

Warto więc sprawdzić rozmiar. Więc rozmiar będzie bardzo łatwe gdyż należy pamiętać, obciążenia, jesteśmy zwiększając rozmiar słownika dla każde słowo, które napotykamy. Więc rozmiar jest po prostu będzie powrót rozmiar słownika. I to jest to. 

Więc wreszcie mamy rozładować. Tak rozładować, będziemy korzystać rekurencyjna funkcja faktycznie zrobić wszystko pracy dla nas. Więc nasza funkcja będzie miano na rozładunku. Co jest kiszonki zrobić? Widzimy tutaj, że będzie odciążający iteracyjne nad wszystkie dzieci w ten konkretny węzeł. I jeśli węzeł potomny nie jest null, a następnie jedziemy do rozładować węzeł podrzędny. 

Więc to ty rekurencyjnie rozładować wszystkie nasze dzieci. Kiedy jesteś pewien, że wszystkie nasze dzieci zostały wyładowane, to może się uwolnić, więc wyładować się. To będzie działać rekurencyjnie wyładować całą TRIE. A następnie po dokonaniu rejestracji, możemy po prostu wrócić prawdziwe. Rozładunek nie może się nie powieść. My tylko uwolnienie rzeczy. Więc kiedy już skończysz uwalniając wszystko, zwraca true. I to jest to. Nazywam się Rob. I to był ortografii. 

[MUZYKA GRA]