1
00:00:00,000 --> 00:00:00,530

2
00:00:00,530 --> 00:00:03,070
>> 1 głośnik: Dajmy
rozwiązanie to spróbować.

3
00:00:03,070 --> 00:00:07,130
Warto więc spojrzeć na to, co nasze
Węzeł struktura będzie wyglądać.

4
00:00:07,130 --> 00:00:11,040
Tutaj widzimy, będziemy mieć
Bool Word i węzeł Struct gwiazdki

5
00:00:11,040 --> 00:00:12,990
Dzieci wspornik alfabetu.

6
00:00:12,990 --> 00:00:18,720
Tak więc pierwszą rzeczą, którą może się zastanawiać,
dlaczego jest zdefiniowany jako hash alfabet 27?

7
00:00:18,720 --> 00:00:22,540
Cóż, pamiętaj, że będziemy potrzebować
do obsługi apostrof, więc

8
00:00:22,540 --> 00:00:25,610
że będzie nieco od specjalnego
Sprawa w niniejszym programie.

9
00:00:25,610 --> 00:00:28,780
>> OK, teraz, pamiętam jak
Trie faktycznie działa.

10
00:00:28,780 --> 00:00:33,420
Powiedzmy, że mamy do indeksowania koty haseł,
następnie z korzenia naszej Trie,

11
00:00:33,420 --> 00:00:36,670
będziemy patrzeć na dzieci
macierz, i mamy zamiar spojrzeć na

12
00:00:36,670 --> 00:00:42,250
Indeks, który odpowiada na list
C. Tak że byłoby Indeks dwa.

13
00:00:42,250 --> 00:00:46,400
Tak więc biorąc pod uwagę, że da nam
nowy węzeł, a potem

14
00:00:46,400 --> 00:00:47,880
pracować w tym węźle.

15
00:00:47,880 --> 00:00:51,830
>> Tak więc biorąc pod uwagę, że węzeł, po raz kolejny jesteśmy
będzie wyglądać na tablicy dzieci,

16
00:00:51,830 --> 00:00:56,170
i będziemy patrzeć na indeksie zerowym
odpowiadać A u kota.

17
00:00:56,170 --> 00:01:01,240
Tak więc mamy zamiar udać się do tego węzła,
i biorąc pod uwagę, że węzeł, jedziemy

18
00:01:01,240 --> 00:01:05,170
spojrzeć na wskaźnik, który odpowiada
do T. i przeniesienie się do tego węzła,

19
00:01:05,170 --> 00:01:09,590
w końcu mamy zupełnie wyglądał
przez nasze słowo kot, a teraz Bool

20
00:01:09,590 --> 00:01:15,020
Słowo ma wskazać, czy
to dane słowo jest w rzeczywistości słowo.

21
00:01:15,020 --> 00:01:17,530
>> Więc po co nam ten szczególny przypadek?

22
00:01:17,530 --> 00:01:21,680
A co, jeśli słowo katastrofa
jest w naszym słowniku, ale

23
00:01:21,680 --> 00:01:24,120
Słowo nie jest kot?

24
00:01:24,120 --> 00:01:29,030
Więc patrząc, czy słowo jest kot
w naszym słowniku, będziemy

25
00:01:29,030 --> 00:01:34,880
powodzeniem przejrzeć indeksy
C-T i dotrzeć węzeł, ale to

26
00:01:34,880 --> 00:01:39,760
tylko dlatego, że katastrofa się do
tworzenie węzłów na drodze z C-A-T wszystko

27
00:01:39,760 --> 00:01:41,250
aż do końca słowa.

28
00:01:41,250 --> 00:01:46,520
Więc Bool Słowo wskazać, czy jest używany
faktycznie ta konkretna lokalizacja

29
00:01:46,520 --> 00:01:48,370
wskazuje na słowo.

30
00:01:48,370 --> 00:01:52,920
>> Dobrze, więc teraz, że wiemy, co
Trie będzie wyglądać, spójrzmy

31
00:01:52,920 --> 00:01:54,800
w funkcji obciążenia.

32
00:01:54,800 --> 00:01:58,670
Tak obciążenia będzie zwrócić Bool
do tego, czy uda nam się lub

33
00:01:58,670 --> 00:02:03,020
Słownik i bezskutecznie załadowany
ta będzie słownika

34
00:02:03,020 --> 00:02:04,520
które chcemy załadować.

35
00:02:04,520 --> 00:02:08,310
Tak więc pierwszą rzeczą, którą mamy zamiar zrobić, to otworzyć
do tego słownika do czytania.

36
00:02:08,310 --> 00:02:12,060
Musimy upewnić się, że nie uda,
więc jeśli nie słownika

37
00:02:12,060 --> 00:02:15,280
pomyślnie otwarty, zwróci
Nie, w tym przypadku będziemy

38
00:02:15,280 --> 00:02:16,340
return false.

39
00:02:16,340 --> 00:02:21,290
Ale zakładając, że z powodzeniem
otwarte, to rzeczywiście możemy przeczytać

40
00:02:21,290 --> 00:02:22,310
przez słownika.

41
00:02:22,310 --> 00:02:24,940
>> Tak więc pierwszą rzeczą, którą mamy zamiar
chcę zrobić, to musimy to

42
00:02:24,940 --> 00:02:26,560
zmienna globalna korzeń.

43
00:02:26,560 --> 00:02:30,250
Teraz, korzeń będzie gwiazdą węzeł.

44
00:02:30,250 --> 00:02:33,830
To jest szczyt naszej Trie, że jesteśmy
będzie iteracja.

45
00:02:33,830 --> 00:02:38,200
Tak więc pierwszą rzeczą, którą będziemy chcieli
wystarczy przydzielić pamięci dla naszego korzenia.

46
00:02:38,200 --> 00:02:42,040
>> Zauważmy, że używamy calloc
Funkcja, która jest zasadniczo taka sama

47
00:02:42,040 --> 00:02:45,560
jako funkcji malloc, oprócz tego, że jest
gwarancją zwrotu, że coś jest

48
00:02:45,560 --> 00:02:47,240
całkowicie wyzerowany.

49
00:02:47,240 --> 00:02:51,350
Więc jeśli kiedyś malloc, musielibyśmy
przejść przez wszystkie wskaźniki w naszym

50
00:02:51,350 --> 00:02:54,220
węzeł i upewnij się, że
wszystkie są puste.

51
00:02:54,220 --> 00:02:56,780
Więc calloc zrobi to za nas.

52
00:02:56,780 --> 00:03:00,390
>> Teraz, podobnie jak malloc, musimy dokonać
upewnić się, że podział rzeczywiście

53
00:03:00,390 --> 00:03:01,580
sukces.

54
00:03:01,580 --> 00:03:04,060
Jeśli ten wrócił null, wówczas
trzeba zamknąć nasz słownik

55
00:03:04,060 --> 00:03:06,170
złożyć i return false.

56
00:03:06,170 --> 00:03:11,040
Tak więc przy założeniu, że podział został
sukces, będziemy korzystać z węzła

57
00:03:11,040 --> 00:03:14,340
gwiazdkowy Cursor iteracyjne
za pośrednictwem naszego Trie.

58
00:03:14,340 --> 00:03:17,950
Więc nasz główny nigdy się nie zmieni,
ale mamy zamiar użyć kursora do

59
00:03:17,950 --> 00:03:20,770
faktycznie przejść od węzła do węzła.

60
00:03:20,770 --> 00:03:25,000
>> W porządku, więc w tym przypadku pętli, jesteśmy
przeczytaniu pliku słownika,

61
00:03:25,000 --> 00:03:26,965
i używamy na fgetc.

62
00:03:26,965 --> 00:03:30,360
Więc fgetc będzie chwycić wolny
znaków z pliku.

63
00:03:30,360 --> 00:03:33,430
Zamierzamy kontynuować pobieranie
znaków, a my nie docierają

64
00:03:33,430 --> 00:03:37,540
koniec pliku, więc nie
dwie sprawy, które musimy obsłużyć.

65
00:03:37,540 --> 00:03:41,640
Po pierwsze, jeśli nie było znaków
Nowa linia, więc wiemy, czy to nowy

66
00:03:41,640 --> 00:03:44,480
Linia, następnie mamy zamiar
przenieść się do nowego słowa.

67
00:03:44,480 --> 00:03:49,300
Ale zakładając, że nie był to nowa linia, a następnie
tutaj, chcemy dowiedzieć się,

68
00:03:49,300 --> 00:03:52,440
Indeks jedziemy do indeksu w
w tablicy dzieci, które

69
00:03:52,440 --> 00:03:53,890
przyjrzeliśmy się wcześniej.

70
00:03:53,890 --> 00:03:57,950
>> Tak jak mówiłem wcześniej, musimy
Szczególnym przypadkiem apostrof.

71
00:03:57,950 --> 00:04:01,040
Zauważ, używamy operatora trójskładnikowych
tu, więc mamy zamiar przeczytać

72
00:04:01,040 --> 00:04:05,500
to tak, jakby postać była czytamy w
apostrof, to będziemy

73
00:04:05,500 --> 00:04:11,740
ustawić wskaźnik równy minus alfabetu
1, który będzie wskaźnik 26.

74
00:04:11,740 --> 00:04:15,190
Inny, gdyby nie apostrof,
Następnie idziemy do ustawienia wskaźnika

75
00:04:15,190 --> 00:04:17,820
równa c minus.

76
00:04:17,820 --> 00:04:23,090
Więc pamiętaj, powrót z poprzednich zbiorów P,
c minus ma dać nam

77
00:04:23,090 --> 00:04:27,470
Stanowisko alfabetyczny c, więc jeśli
c jest literą, to wola

78
00:04:27,470 --> 00:04:28,770
daje nam indeks zerowy.

79
00:04:28,770 --> 00:04:32,180
Do litery B, to daje
us indeks 1, i tak dalej.

80
00:04:32,180 --> 00:04:37,070
>> Więc to daje nam wskaźnik do
Dzieci tablica, że ​​chcemy.

81
00:04:37,070 --> 00:04:42,540
Teraz, jeśli wskaźnik ten jest obecnie wartość null w
Tablica dzieci, co oznacza, że

82
00:04:42,540 --> 00:04:47,470
Węzeł obecnie nie istnieje od
że ścieżka, więc musimy przeznaczyć

83
00:04:47,470 --> 00:04:49,220
Węzeł na tej drodze.

84
00:04:49,220 --> 00:04:50,610
To, co tu robimy.

85
00:04:50,610 --> 00:04:54,650
Więc będziemy znowu użyć calloc
Funkcja tak, że nie mamy

86
00:04:54,650 --> 00:05:00,130
do zera wszystkie wskaźniki, a my,
ponownie, należy sprawdzić, czy calloc

87
00:05:00,130 --> 00:05:01,300
nie powiedzie się.

88
00:05:01,300 --> 00:05:04,760
Jeśli calloc zawiódł, to musimy
wyładować wszystko, zamykać

89
00:05:04,760 --> 00:05:06,880
słownik i zwraca fałsz.

90
00:05:06,880 --> 00:05:14,110
>> Tak więc przy założeniu, że nie uda, to
stworzy nowe dziecko dla nas,

91
00:05:14,110 --> 00:05:16,000
, a następnie udamy się do tego dziecka.

92
00:05:16,000 --> 00:05:19,030
Nasz kursor iteracji
w dół do tego dziecka.

93
00:05:19,030 --> 00:05:23,390
Teraz, jeśli nie jest to wartość null, aby rozpocząć,
Następnie można po prostu iteracyjne kursor

94
00:05:23,390 --> 00:05:26,650
w dół do tego dziecka bez konieczności
konieczności przeznaczyć nic.

95
00:05:26,650 --> 00:05:30,790
Jest to przypadek, w którym po raz pierwszy się
przeznaczyć słowo kot, i

96
00:05:30,790 --> 00:05:34,390
co oznacza, że ​​kiedy idziemy do przeznaczenia
katastrofa, nie ma potrzeby tworzenia

97
00:05:34,390 --> 00:05:35,720
węzły dla C-A-T ponownie.

98
00:05:35,720 --> 00:05:37,620
One już istnieją.

99
00:05:37,620 --> 00:05:40,140
>> OK, więc co to jest reszta?

100
00:05:40,140 --> 00:05:44,600
Jest to stan, w którym c było
odwrotny ukośnik n, gdzie c to nowa linia.

101
00:05:44,600 --> 00:05:47,780
Oznacza to, że udało nam się
zakończone słowo.

102
00:05:47,780 --> 00:05:51,020
Teraz, co chcemy zrobić, gdy
zakończone powodzeniem słowo?

103
00:05:51,020 --> 00:05:55,250
Zamierzamy wykorzystywać to pole słowo
wewnątrz naszego węzła Struct.

104
00:05:55,250 --> 00:06:00,570
>> Chcemy ustawić, że się prawda, tak, że
wskazuje, że węzeł oznacza

105
00:06:00,570 --> 00:06:03,320
sukces słowo rzeczywiste słowo.

106
00:06:03,320 --> 00:06:05,050
Teraz ustaw, które na True.

107
00:06:05,050 --> 00:06:09,210
Chcemy przywrócić nasz kursor do punktu
na początku Trie ponownie.

108
00:06:09,210 --> 00:06:13,510
I w końcu, zwiększamy naszą słownika
Rozmiar od znaleźliśmy ani słowa.

109
00:06:13,510 --> 00:06:16,450
>> Dobrze, więc mamy zamiar dalej robić
że charakter poprzez czytanie

110
00:06:16,450 --> 00:06:21,960
charakter, w budowę nowych węzłów
nasza Trie i dla każdego słowa w

111
00:06:21,960 --> 00:06:26,810
słownik, aż w końcu dotrzeć c
równa EOF, w tym przypadku, możemy złamać

112
00:06:26,810 --> 00:06:28,100
z pliku.

113
00:06:28,100 --> 00:06:31,110
Obecnie istnieją dwa przypadki pod
które moglibyśmy trafić EOF.

114
00:06:31,110 --> 00:06:35,680
Pierwszym z nich jest, czy istnieje błąd
czytanie z pliku, więc jeśli nie było

115
00:06:35,680 --> 00:06:39,280
błąd, musimy zrobić typowy
wyładować wszystko, zamknij plik,

116
00:06:39,280 --> 00:06:40,520
return false.

117
00:06:40,520 --> 00:06:43,870
Przy założeniu, że nie był błąd, to
po prostu oznacza, że ​​faktycznie hit koniec

118
00:06:43,870 --> 00:06:47,820
plik, w którym to przypadku, zamykamy
plik i powrócić prawda od kiedy

119
00:06:47,820 --> 00:06:51,010
pomyślnie załadowany słownik
do naszego Trie.

120
00:06:51,010 --> 00:06:54,240
>> Dobra, więc Teraz
sprawdź Check.

121
00:06:54,240 --> 00:06:58,780
Patrząc na kontrolę działania, widzimy
Sprawdź, które będzie zwracać Bool.

122
00:06:58,780 --> 00:07:03,740
To zwraca True, jeśli to słowo, które jest
były przekazywane jest w naszym Trie.

123
00:07:03,740 --> 00:07:06,170
Zwraca False inaczej.

124
00:07:06,170 --> 00:07:10,110
>> Więc jak idziemy do ustalenia, czy
to słowo jest w naszym Trie?

125
00:07:10,110 --> 00:07:14,270
Widzimy tutaj, że, podobnie jak poprzednio,
mamy zamiar użyć kursora do iteracji

126
00:07:14,270 --> 00:07:16,010
za pośrednictwem naszego Trie.

127
00:07:16,010 --> 00:07:20,650
Teraz, tutaj, jedziemy do iteracji
w ciągu całego naszego słowa.

128
00:07:20,650 --> 00:07:24,680
Więc iterowanie słowem jesteśmy
minęło, idziemy do określenia

129
00:07:24,680 --> 00:07:29,280
Wskaźnik do tablicy, że dzieci
odpowiada słowo uchwytem i.

130
00:07:29,280 --> 00:07:34,150
Tak to będzie wyglądać dokładnie tak, jak
Obciążenia, w którym, jeśli uchwyt jest słowo i

131
00:07:34,150 --> 00:07:38,110
apostrof, to chcemy użyć indeksu
alfabet minus 1, ponieważ określona

132
00:07:38,110 --> 00:07:41,160
to gdzie idziemy
przechowywać apostrofy.

133
00:07:41,160 --> 00:07:44,440
>> Jeszcze będziemy używać tolower
Uchwyt i słowo.

134
00:07:44,440 --> 00:07:48,270
Więc pamiętaj, że słowo może mieć dowolna
kapitalizacja, a więc

135
00:07:48,270 --> 00:07:51,590
Aby upewnić się, że używamy
Wersja małe rzeczy.

136
00:07:51,590 --> 00:07:55,300
I odejmujemy od tego małymi literami
aby po raz kolejny daje nam

137
00:07:55,300 --> 00:07:57,940
Stanowisko alfabetycznie
z tego znaku.

138
00:07:57,940 --> 00:08:01,740
Tak, że to będzie nasz indeks
do tablicy dzieci.

139
00:08:01,740 --> 00:08:06,480
>> A teraz, jeśli indeks do dzieci
tablicy jest null, co oznacza, że

140
00:08:06,480 --> 00:08:09,050
nie może już kontynuować Iterowanie
w dół naszego Trie.

141
00:08:09,050 --> 00:08:13,320
Jeśli tak jest, to słowo nie może
może być w naszym Trie, ponieważ jeśli

142
00:08:13,320 --> 00:08:18,000
były, to by znaczyło, że będzie
Droga w dół do tego słowa, i byś

143
00:08:18,000 --> 00:08:19,350
nigdy nie spotkać null.

144
00:08:19,350 --> 00:08:21,910
Więc napotkania NULL, wracamy Fałsz.

145
00:08:21,910 --> 00:08:23,810
Słowa nie ma w słowniku.

146
00:08:23,810 --> 00:08:28,200
Gdyby nie to, null, a następnie jedziemy do
nadal Iterowanie, więc jedziemy

147
00:08:28,200 --> 00:08:33,150
aktualizować naszą kursor wskazywać, że
szczególności węzła w tym indeksie.

148
00:08:33,150 --> 00:08:36,659
>> Więc robić, że w całym
całe słowo.

149
00:08:36,659 --> 00:08:40,630
Zakładając, że nie uderzył NULL, że środki
byliśmy w stanie dostać się przez cały

150
00:08:40,630 --> 00:08:44,840
świat i znaleźć węzeł w naszej Trie,
ale my nie dość jeszcze zrobione.

151
00:08:44,840 --> 00:08:46,350
Nie chcemy, aby tylko wrócić prawda.

152
00:08:46,350 --> 00:08:51,400
Chcemy wrócić kursora błędzie słowo
gdyż należy pamiętać, ponownie, jeśli kot nie jest

153
00:08:51,400 --> 00:08:55,140
w naszym słowniku a katastrofa jest,
wtedy uda nam się przejść przez

154
00:08:55,140 --> 00:08:59,810
kot słowo, ale słowo kursor
będzie Fałsz i nie prawda.

155
00:08:59,810 --> 00:09:04,990
Więc wracamy do wskazania kursora słowo
czy węzeł jest rzeczywiście słowem,

156
00:09:04,990 --> 00:09:06,530
i to jest to do odprawy.

157
00:09:06,530 --> 00:09:08,310
>> Warto więc sprawdzić rozmiar.

158
00:09:08,310 --> 00:09:11,410
Tak Rozmiar będzie dość łatwe
gdyż należy pamiętać, w obciążeniu, jesteśmy

159
00:09:11,410 --> 00:09:15,480
zwiększając rozmiar słownika dla
każde słowo, które napotykamy.

160
00:09:15,480 --> 00:09:20,820
Wielkość jest tylko tak zamierza wrócić
rozmiar słownika, i to jest to.

161
00:09:20,820 --> 00:09:24,650
>> W porządku, więc wreszcie mamy Unload.

162
00:09:24,650 --> 00:09:29,050
Więc Rozładunek, będziemy korzystać
rekurencyjna funkcja faktycznie zrobić wszystko

163
00:09:29,050 --> 00:09:33,390
pracy dla nas, więc naszej funkcji
będzie nazywany Unloader.

164
00:09:33,390 --> 00:09:35,830
Co jest Unloader zrobić?

165
00:09:35,830 --> 00:09:40,640
Widzimy tutaj, że Unloader będzie
iteracyjne nad wszystkie dzieci w

166
00:09:40,640 --> 00:09:45,810
ten konkretny węzeł, i jeśli dziecko
węzeł nie jest null, a następnie jedziemy do

167
00:09:45,810 --> 00:09:47,760
rozładować węzeł podrzędny.

168
00:09:47,760 --> 00:09:52,070
>> Więc to będzie rekurencyjnie
rozładować wszystkie nasze dzieci.

169
00:09:52,070 --> 00:09:55,140
Kiedy jesteś pewien, że wszystkie nasze dzieci
zostały wyładowane, to

170
00:09:55,140 --> 00:09:58,830
może się uwolnić, więc zwolnić Nas.

171
00:09:58,830 --> 00:10:04,550
Więc będzie to rekurencyjnie rozładować
Cały Trie, a następnie od razu, że jest

172
00:10:04,550 --> 00:10:06,910
zrobione, możemy po prostu wrócić prawda.

173
00:10:06,910 --> 00:10:09,770
Rozładunek nie może nie jesteśmy
tylko uwolnienie rzeczy.

174
00:10:09,770 --> 00:10:12,985
Więc kiedy już skończysz uwalniając
wszystko, wrócić prawda.

175
00:10:12,985 --> 00:10:14,380
I to jest to.

176
00:10:14,380 --> 00:10:16,792
Nazywam się Rob, i to
był [niesłyszalne].

177
00:10:16,792 --> 00:10:21,888