>> [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]