>> 1 głośnik: 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 Word i węzeł Struct gwiazdki
Dzieci wspornik alfabetu.
Tak więc pierwszą rzeczą, którą może się zastanawiać, dlaczego jest zdefiniowany jako hash alfabet 27?
Cóż, pamiętaj, że będziemy potrzebować do obsługi apostrof, więc
że będzie nieco od specjalnego Sprawa w niniejszym programie.
>> OK, teraz, pamiętam jak Trie faktycznie działa.
Powiedzmy, że mamy do indeksowania koty haseł, następnie z korzenia naszej Trie,
będziemy patrzeć na dzieci macierz, i mamy zamiar spojrzeć na
Indeks, który odpowiada na list C. Tak że byłoby Indeks dwa.
Tak więc biorąc pod uwagę, że da nam nowy węzeł, a potem
pracować w tym węźle.
>> 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
spojrzeć na wskaźnik, który 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?
A co, jeśli słowo katastrofa jest w naszym słowniku, ale
Słowo nie jest kot?
Więc patrząc, czy słowo jest kot w naszym słowniku, będziemy
powodzeniem przejrzeć indeksy C-T i dotrzeć węzeł, ale to
tylko dlatego, że katastrofa się do tworzenie węzłów na drodze z C-A-T wszystko
aż do końca słowa.
Więc Bool Słowo wskazać, czy jest używany faktycznie ta konkretna lokalizacja
wskazuje na słowo.
>> Dobrze, więc teraz, że wiemy, co Trie będzie wyglądać, spójrzmy
w funkcji obciążenia.
Tak obciążenia będzie zwrócić Bool do tego, czy uda nam się lub
Słownik i bezskutecznie załadowany ta będzie słownika
które chcemy załadować.
Tak więc pierwszą rzeczą, którą mamy zamiar zrobić, to otworzyć do tego słownika do czytania.
Musimy upewnić się, że nie uda, więc jeśli nie słownika
pomyślnie otwarty, zwróci Nie, w tym przypadku będziemy
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, korzeń będzie gwiazdą węzeł.
To jest szczyt naszej Trie, że jesteśmy będzie iteracja.
Tak więc pierwszą rzeczą, którą będziemy chcieli wystarczy przydzielić pamięci 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ł rzeczywiście
sukces.
Jeśli ten wrócił null, wówczas trzeba zamknąć nasz 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
gwiazdkowy Cursor iteracyjne za pośrednictwem naszego Trie.
Więc nasz główny nigdy się nie zmieni, ale mamy zamiar użyć kursora do
faktycznie przejść od węzła do węzła.
>> W porządku, więc w tym przypadku pętli, jesteśmy przeczytaniu pliku słownika,
i używamy na fgetc.
Więc fgetc będzie chwycić wolny znaków z pliku.
Zamierzamy kontynuować pobieranie znaków, a my nie docierają
koniec pliku, więc nie dwie sprawy, które musimy obsłużyć.
Po pierwsze, jeśli nie było znaków Nowa linia, więc wiemy, czy to nowy
Linia, 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 mówiłem wcześniej, musimy Szczególnym przypadkiem apostrof.
Zauważ, używamy operatora trójskładnikowych tu, więc mamy zamiar przeczytać
to tak, jakby postać była czytamy w apostrof, to będziemy
ustawić wskaźnik równy minus alfabetu 1, który będzie wskaźnik 26.
Inny, gdyby nie apostrof, Następnie idziemy do ustawienia wskaźnika
równa c minus.
Więc pamiętaj, powrót z poprzednich zbiorów P, c minus ma dać nam
Stanowisko alfabetyczny c, więc jeśli c jest literą, to wola
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 Tablica dzieci, co oznacza, że
Węzeł obecnie nie istnieje od że ścieżka, więc musimy przeznaczyć
Węzeł na tej drodze.
To, co tu robimy.
Więc będziemy znowu użyć calloc Funkcja tak, że nie mamy
do zera wszystkie wskaźniki, a my, ponownie, należy sprawdzić, czy calloc
nie powiedzie się.
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 ma potrzeby tworzenia
węzły dla C-A-T ponownie.
One już istnieją.
>> OK, więc co to jest reszta?
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, 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 się prawda, tak, że wskazuje, że węzeł oznacza
sukces słowo rzeczywiste słowo.
Teraz ustaw, które na True.
Chcemy przywrócić nasz kursor do punktu na początku Trie ponownie.
I w końcu, zwiększamy naszą słownika Rozmiar od znaleźliśmy ani słowa.
>> Dobrze, więc mamy zamiar dalej robić że charakter poprzez czytanie
charakter, w budowę nowych węzłów nasza Trie i dla każdego słowa w
słownik, aż w końcu dotrzeć c równa EOF, w tym przypadku, możemy złamać
z pliku.
Obecnie istnieją dwa przypadki pod 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, musimy zrobić typowy wyładować wszystko, zamknij 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 plik i powrócić prawda od kiedy
pomyślnie załadowany słownik do naszego Trie.
>> Dobra, więc Teraz sprawdź Check.
Patrząc na kontrolę działania, widzimy Sprawdź, które będzie zwracać Bool.
To zwraca True, jeśli to słowo, które jest były przekazywane jest w naszym Trie.
Zwraca False inaczej.
>> Więc jak idziemy do ustalenia, 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, tutaj, jedziemy do iteracji w ciągu całego naszego słowa.
Więc iterowanie słowem jesteśmy minęło, idziemy do określenia
Wskaźnik do tablicy, że dzieci odpowiada słowo uchwytem i.
Tak to będzie wyglądać dokładnie tak, jak Obciążenia, w którym, jeśli uchwyt jest słowo i
apostrof, to chcemy użyć indeksu alfabet minus 1, ponieważ określona
to gdzie idziemy przechowywać apostrofy.
>> Jeszcze będziemy używać tolower Uchwyt i słowo.
Więc pamiętaj, że słowo może mieć dowolna kapitalizacja, a więc
Aby upewnić się, że używamy Wersja małe rzeczy.
I odejmujemy od tego małymi literami aby po raz kolejny daje nam
Stanowisko alfabetycznie z tego znaku.
Tak, że to będzie nasz indeks do tablicy dzieci.
>> A teraz, jeśli 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ż jeśli
były, to by znaczyło, że będzie Droga w dół do tego słowa, i byś
nigdy nie spotkać null.
Więc napotkania NULL, wracamy Fałsz.
Słowa nie ma w słowniku.
Gdyby nie to, null, a następnie jedziemy do nadal Iterowanie, więc jedziemy
aktualizować naszą kursor wskazywać, że szczególności węzła w tym indeksie.
>> Więc robić, że w całym całe słowo.
Zakładając, że nie uderzył NULL, że środki byliśmy w stanie dostać się przez cały
świat i znaleźć węzeł w naszej Trie, ale my nie dość jeszcze zrobione.
Nie chcemy, aby tylko wrócić prawda.
Chcemy wrócić kursora błędzie słowo gdyż należy pamiętać, ponownie, jeśli kot nie jest
w naszym słowniku a katastrofa jest, wtedy uda nam się przejść przez
kot słowo, ale słowo kursor będzie Fałsz i nie prawda.
Więc wracamy do wskazania kursora słowo czy węzeł jest rzeczywiście słowem,
i to jest to do odprawy.
>> Warto więc sprawdzić rozmiar.
Tak Rozmiar będzie dość łatwe gdyż należy pamiętać, w obciążeniu, jesteśmy
zwiększając rozmiar słownika dla każde słowo, które napotykamy.
Wielkość jest tylko tak zamierza wrócić rozmiar słownika, i to jest to.
>> W porządku, więc wreszcie mamy Unload.
Więc Rozładunek, będziemy korzystać rekurencyjna funkcja faktycznie zrobić wszystko
pracy dla nas, więc naszej funkcji będzie nazywany Unloader.
Co jest Unloader zrobić?
Widzimy tutaj, że Unloader będzie iteracyjne nad wszystkie dzieci w
ten konkretny węzeł, i jeśli dziecko węzeł nie jest null, a następnie jedziemy do
rozładować węzeł podrzędny.
>> Więc to będzie rekurencyjnie rozładować wszystkie nasze dzieci.
Kiedy jesteś pewien, że wszystkie nasze dzieci zostały wyładowane, to
może się uwolnić, więc zwolnić Nas.
Więc będzie to rekurencyjnie rozładować Cały Trie, a następnie od razu, że jest
zrobione, możemy po prostu wrócić prawda.
Rozładunek nie może nie jesteśmy tylko uwolnienie rzeczy.
Więc kiedy już skończysz uwalniając wszystko, wrócić prawda.
I to jest to.
Nazywam się Rob, i to był [niesłyszalne].