1
00:00:00,000 --> 00:00:12,350
>> [MUZYKA GRA]

2
00:00:12,350 --> 00:00:13,050
>> ROB BOWDEN Cześć.

3
00:00:13,050 --> 00:00:13,640
Jestem Rob.

4
00:00:13,640 --> 00:00:16,210
I niech to rozwiązanie się.

5
00:00:16,210 --> 00:00:20,070
Więc idziemy do wdrożenia
ogólnego zestawienia.

6
00:00:20,070 --> 00:00:24,090
Widzimy, że węzeł struktura naszych stron
tabela będzie wyglądać tak.

7
00:00:24,090 --> 00:00:28,710
Więc to będzie mieć słowo char
Tablica o rozmiarze size + 1.

8
00:00:28,710 --> 00:00:32,259
Nie zapomnij o + 1, gdyż maksymalna
słowo w słowniku jest 45

9
00:00:32,259 --> 00:00:33,130
znaków.

10
00:00:33,130 --> 00:00:37,070
I wtedy będziemy potrzebować jeden dodatkowy
znaków dla zera backslash.

11
00:00:37,070 --> 00:00:40,870
>> , A następnie w każdym naszym hashtable
wiadro będzie przechowywać

12
00:00:40,870 --> 00:00:42,320
powiązana lista węzłów.

13
00:00:42,320 --> 00:00:44,420
Nie robimy tu liniową próbkowania.

14
00:00:44,420 --> 00:00:48,430
I tak, w celu podłączenia się do następnego
elementem w wiadrze, musimy

15
00:00:48,430 --> 00:00:50,390
węzeł struct * następny.

16
00:00:50,390 --> 00:00:51,110
OK.

17
00:00:51,110 --> 00:00:53,090
Więc to, co węzeł wygląda.

18
00:00:53,090 --> 00:00:56,180
>> Teraz tutaj jest deklaracja
naszego hashtable.

19
00:00:56,180 --> 00:00:59,640
To będzie mieć 16.834 wiader.

20
00:00:59,640 --> 00:01:01,910
Ale ta liczba nie ma znaczenia.

21
00:01:01,910 --> 00:01:05,450
I wreszcie będziemy mieć
zmienna globalna wielkość hashtable, które

22
00:01:05,450 --> 00:01:07,000
zaczynać się jako zero.

23
00:01:07,000 --> 00:01:10,760
I to będzie śledzić, jak
wiele słów są w naszym słowniku.

24
00:01:10,760 --> 00:01:13,710
>> Warto więc spojrzeć na obciążenia.

25
00:01:13,710 --> 00:01:16,390
Zauważ, że obciążenie, zwraca bool.

26
00:01:16,390 --> 00:01:20,530
Powrót prawda, czy to z powodzeniem
załadowany, a false w przeciwnym wypadku.

27
00:01:20,530 --> 00:01:23,990
I zajmuje const char * słownika
który słownik

28
00:01:23,990 --> 00:01:25,280
że chcemy otworzyć.

29
00:01:25,280 --> 00:01:27,170
Więc to jest pierwsza rzecz,
mamy zamiar zrobić.

30
00:01:27,170 --> 00:01:29,500
>> Jedziemy do fopen
słownik do czytania.

31
00:01:29,500 --> 00:01:31,680
I będziemy musieli dokonać
pewien, że to się udało.

32
00:01:31,680 --> 00:01:35,920
Więc jeśli zwrócony NULL, to nie
powodzeniem otworzyć słownik.

33
00:01:35,920 --> 00:01:37,440
I musimy return false.

34
00:01:37,440 --> 00:01:41,580
Ale zakładając, że tak skutecznie
otwarte, to chcemy, aby przeczytać

35
00:01:41,580 --> 00:01:42,400
słowniku.

36
00:01:42,400 --> 00:01:46,450
Dlatego należy zachować pętli, dopóki nie znajdziemy niektórych
powód, aby wyrwać się z tej pętli,

37
00:01:46,450 --> 00:01:47,570
które zobaczymy.

38
00:01:47,570 --> 00:01:48,920
Dlatego należy zachować pętli.

39
00:01:48,920 --> 00:01:51,780
>> A teraz mamy zamiar
malloc pojedynczego węzła.

40
00:01:51,780 --> 00:01:54,020
I oczywiście musimy
wietrzyć sprawdzić ponownie.

41
00:01:54,020 --> 00:01:58,680
Więc jeśli mallocing nie uda, to
chcemy rozładować dowolny węzeł, że

42
00:01:58,680 --> 00:02:02,590
się do malloc przed zamknij
słownik i return false.

43
00:02:02,590 --> 00:02:06,830
Ale pomijając, że przy założeniu, że
udało, to chcemy wykorzystać fscanf

44
00:02:06,830 --> 00:02:12,400
przeczytać ani jednego słowa od naszych
słownika do naszego węzła.

45
00:02:12,400 --> 00:02:17,940
Więc pamiętać, że wejścia> słowo jest char
bufor o rozmiarze lenghth słowo + 1

46
00:02:17,940 --> 00:02:20,300
że mamy zamiar przechowywać słowo w.

47
00:02:20,300 --> 00:02:25,070
>> Więc fscanf zamierza powrócić 1, tak długo,
jak to było w stanie skutecznie

48
00:02:25,070 --> 00:02:26,750
czytaj słowo z pliku.

49
00:02:26,750 --> 00:02:30,460
Jeśli błąd się dzieje, albo, albo
dotrzeć do końca pliku, to

50
00:02:30,460 --> 00:02:31,950
nie zwróci 1.

51
00:02:31,950 --> 00:02:35,180
W takim przypadku nie zwraca 1,
mamy wreszcie będzie wyrwać się z

52
00:02:35,180 --> 00:02:37,280
to pętla while.

53
00:02:37,280 --> 00:02:42,770
Tak więc widzimy, że raz mamy powodzeniem
czytać słowo w

54
00:02:42,770 --> 00:02:48,270
Wpis> słowo, następnie idziemy do tego
słowo za pomocą naszej funkcji skrótu.

55
00:02:48,270 --> 00:02:49,580
>> Rzućmy okiem na
funkcja skrótu.

56
00:02:49,580 --> 00:02:52,430

57
00:02:52,430 --> 00:02:55,610
Tak naprawdę nie potrzebujesz
aby to zrozumieć.

58
00:02:55,610 --> 00:02:59,460
I rzeczywiście po prostu wyciągnął ten hash
funkcjonować z internetu.

59
00:02:59,460 --> 00:03:04,010
Jedyne, co trzeba uznać to
że trwa const char * wyraz.

60
00:03:04,010 --> 00:03:08,960
Tak to trwa ciąg na wejściu i
zwrócenie int jako wyjście.

61
00:03:08,960 --> 00:03:12,360
Więc to wszystko funkcja skrótu jest, jest to
odbywa się w wejściu i daje

62
00:03:12,360 --> 00:03:14,490
Indeks do hashtable.

63
00:03:14,490 --> 00:03:18,530
>> Zauważ, że my moding przez NUM_BUCKETS,
tak, że wartość zwracana

64
00:03:18,530 --> 00:03:21,730
faktycznie jest indeks do hashtable
a nie indeks poza

65
00:03:21,730 --> 00:03:24,320
granice tablicy.

66
00:03:24,320 --> 00:03:28,060
Tak więc biorąc pod uwagę, że funkcja, jedziemy
hash słowo, które czytamy

67
00:03:28,060 --> 00:03:29,390
słowniku.

68
00:03:29,390 --> 00:03:31,700
A potem będziemy używać
że hash wstawić

69
00:03:31,700 --> 00:03:33,750
Wejście w hashtable.

70
00:03:33,750 --> 00:03:38,520
>> Teraz hashtable hash jest obecny
połączonej listy w tabeli.

71
00:03:38,520 --> 00:03:41,410
I to jest bardzo możliwe
, że to jest po prostu NULL.

72
00:03:41,410 --> 00:03:44,960
Chcemy wstawić nasz wpis w
począwszy od tego połączonej listy.

73
00:03:44,960 --> 00:03:48,600
I tak będziemy mieć nasz prąd
punkt wyjścia do tego, co hashtable

74
00:03:48,600 --> 00:03:50,380
obecnie wskazuje.

75
00:03:50,380 --> 00:03:53,310
A następnie jedziemy do przechowywania,
w hashtable w

76
00:03:53,310 --> 00:03:55,350
hash, aktualny wpis.

77
00:03:55,350 --> 00:03:59,320
Tak więc te dwie linie z powodzeniem wstawić
Wpis na początku

78
00:03:59,320 --> 00:04:02,260
powiązana lista w tym indeksie
w hashtable.

79
00:04:02,260 --> 00:04:04,900
>> Kiedy skończysz z tym, wiemy,
że znaleźliśmy inny wyraz w

80
00:04:04,900 --> 00:04:07,790
słownik, a my ponownie zwiększyć.

81
00:04:07,790 --> 00:04:13,960
Więc robić, że do fscanf
wrócił coś nie 1 na

82
00:04:13,960 --> 00:04:16,950
który punkt należy pamiętać, że
musimy uwolnić wpis.

83
00:04:16,950 --> 00:04:19,459
Więc tutaj mamy malloced wpisu.

84
00:04:19,459 --> 00:04:21,329
I staraliśmy się przeczytać coś
ze słownika.

85
00:04:21,329 --> 00:04:23,910
A nie z powodzeniem czytać
coś ze słownika, w

86
00:04:23,910 --> 00:04:26,650
takim przypadku musimy uwolnić wpis
że nigdy nie wprowadzony do

87
00:04:26,650 --> 00:04:29,140
hashtable i wreszcie przełamać.

88
00:04:29,140 --> 00:04:32,750
>> Kiedy wybuchnie musimy zobaczyć, dobrze,
nie wyjdziemy, bo tam

89
00:04:32,750 --> 00:04:34,360
został błąd odczytu z pliku?

90
00:04:34,360 --> 00:04:37,120
Lub nie wyjdziemy, bo
osiągnął koniec pliku?

91
00:04:37,120 --> 00:04:39,480
Jeżeli istnieje błąd, to
chcemy return false.

92
00:04:39,480 --> 00:04:40,930
Ponieważ obciążenie nie udało.

93
00:04:40,930 --> 00:04:43,890
Oraz w procesie chcemy rozładować
wszystkie słowa, które czytamy, i

94
00:04:43,890 --> 00:04:45,670
zamknij plik słownika.

95
00:04:45,670 --> 00:04:48,740
>> Zakładając, że nie uda, to po prostu
jeszcze trzeba zamknąć słownika

96
00:04:48,740 --> 00:04:53,040
złożyć, i wreszcie powrót prawda od kiedy
pomyślnie załadowany słownik.

97
00:04:53,040 --> 00:04:54,420
I to jest to dla ładunku.

98
00:04:54,420 --> 00:04:59,020
Więc teraz sprawdzić, ponieważ załadowany hashtable,
będzie wyglądać tak.

99
00:04:59,020 --> 00:05:03,140
Więc sprawdź, zwraca bool, który jest
będzie wskazywać, czy przekazywane

100
00:05:03,140 --> 00:05:07,530
w char * tekst, czy przekazywane
w ciągu jest w naszym słowniku.

101
00:05:07,530 --> 00:05:09,890
Jeśli więc w słowniku
czy jest w naszym hashtable,

102
00:05:09,890 --> 00:05:11,170
wrócimy prawda.

103
00:05:11,170 --> 00:05:13,380
A jeśli nie, będziemy return false.

104
00:05:13,380 --> 00:05:17,740
>> Biorąc pod uwagę ten przeszedł w słowa, że ​​jesteśmy
będzie hash słowo.

105
00:05:17,740 --> 00:05:22,110
Teraz ważne jest, aby rozpoznać
że obciążenia wiedzieliśmy, że wszystkie

106
00:05:22,110 --> 00:05:23,820
Słowa Zamierzamy być małe.

107
00:05:23,820 --> 00:05:25,820
Ale tutaj nie jesteśmy tak pewni.

108
00:05:25,820 --> 00:05:29,510
Jeśli przyjrzeć się naszej funkcji skrótu,
faktycznie nasza funkcja skrótu

109
00:05:29,510 --> 00:05:32,700
jest mniejsza obudowa każdy znak
słowa.

110
00:05:32,700 --> 00:05:37,940
Tak więc bez względu na kapitalizację
Słowo, nasza funkcja skrótu jest powrót

111
00:05:37,940 --> 00:05:42,270
sam wskaźnik dla co
kapitalizacja jest, jak to ma

112
00:05:42,270 --> 00:05:45,280
wrócił do zupełnie małe
wersja słowa.

113
00:05:45,280 --> 00:05:46,600
W porządku.

114
00:05:46,600 --> 00:05:49,790
To nasz indeks jest w
hashtable dla tego słowa.

115
00:05:49,790 --> 00:05:52,940
>> Teraz to dla pętli będzie
iteracyjne nad połączonej listy

116
00:05:52,940 --> 00:05:55,000
, że był w tym indeksie.

117
00:05:55,000 --> 00:05:59,610
Więc zauważyć, że wpis jest inicjowanie
aby wskazać tym indeksie.

118
00:05:59,610 --> 00:06:02,750
Zamierzamy kontynuować
natomiast wejście! = NULL.

119
00:06:02,750 --> 00:06:07,770
I pamiętaj, że aktualizację wskaźnika
w naszej listy entry = Wpis> obok.

120
00:06:07,770 --> 00:06:14,400
Więc nasz aktualny punkt wejścia do
Kolejnym punktem w połączonej listy.

121
00:06:14,400 --> 00:06:19,250
>> Więc dla każdego wpisu w połączonej listy,
będziemy używać strcasecmp.

122
00:06:19,250 --> 00:06:20,330
To nie jest StrComp.

123
00:06:20,330 --> 00:06:23,780
Ponieważ po raz kolejny, że chcemy
robić rzeczy, wielkość liter.

124
00:06:23,780 --> 00:06:27,870
Więc używamy strcasecmp porównać
słowem, które przepuszczono przez to

125
00:06:27,870 --> 00:06:31,860
Funkcja do słowa
to jest w tej pozycji.

126
00:06:31,860 --> 00:06:35,570
Jeśli powraca do zera, co oznacza, że ​​nie było
Mecz, w którym to przypadku chcemy

127
00:06:35,570 --> 00:06:36,630
return true.

128
00:06:36,630 --> 00:06:39,590
Udało nam się znaleźć
Słowo w naszym hashtable.

129
00:06:39,590 --> 00:06:43,040
>> Jeśli nie było meczu, to jesteśmy
będzie pętli ponownie i spojrzeć na

130
00:06:43,040 --> 00:06:43,990
następny wpis.

131
00:06:43,990 --> 00:06:47,640
A my nadal zapętlenie podczas gdy
są wpisy w tej połączonej listy.

132
00:06:47,640 --> 00:06:50,160
Co się stanie, jeśli łamiemy
z tego do pętli?

133
00:06:50,160 --> 00:06:55,110
Oznacza to, że nie znaleźliśmy wpis, który
pasuje to słowo, w którym to przypadku

134
00:06:55,110 --> 00:07:00,220
my return false, aby wskazać, że nasz
hashtable nie zawierają to słowo.

135
00:07:00,220 --> 00:07:02,540
I to jest kontrola.

136
00:07:02,540 --> 00:07:04,790
>> Warto więc przyjrzeć się wielkości.

137
00:07:04,790 --> 00:07:06,970
Teraz rozmiar będzie bardzo proste.

138
00:07:06,970 --> 00:07:11,080
Ponieważ pamiętam w obciążeniu, dla każdego słowa
okazało się, że zwiększa się globalny

139
00:07:11,080 --> 00:07:12,880
zmienny rozmiar hashtable.

140
00:07:12,880 --> 00:07:16,480
Więc funkcja rozmiar jest po prostu będzie
powrót zmiennej globalnej.

141
00:07:16,480 --> 00:07:18,150
I to jest to.

142
00:07:18,150 --> 00:07:22,300
>> Teraz wreszcie, musimy rozładować
Słownik raz wszystko się robi.

143
00:07:22,300 --> 00:07:25,340
Więc jak mamy to zrobić?

144
00:07:25,340 --> 00:07:30,440
Tutaj mamy pętli na
wszystkie wiadra z naszego stołu.

145
00:07:30,440 --> 00:07:33,240
Tak więc istnieje NUM_BUCKETS wiadra.

146
00:07:33,240 --> 00:07:37,410
I dla każdej połączonej listy w naszym
hashtable, jedziemy do pętli na

147
00:07:37,410 --> 00:07:41,070
Całość połączonej listy,
uwalniając każdy element.

148
00:07:41,070 --> 00:07:42,900
>> Teraz musimy być ostrożni.

149
00:07:42,900 --> 00:07:47,910
Więc tutaj mamy zmiennej tymczasowej
, który jest przechowywanie wskaźnika do następnego

150
00:07:47,910 --> 00:07:49,730
element połączony listy.

151
00:07:49,730 --> 00:07:52,140
A następnie jedziemy do darmo
bieżący element.

152
00:07:52,140 --> 00:07:55,990
Musimy być pewni, że od kiedy to zrobić
Nie można po prostu zwolnić bieżący element

153
00:07:55,990 --> 00:07:59,180
a następnie spróbuj przejść do następnego wskaźnika,
od kiedy już uwolnił go,

154
00:07:59,180 --> 00:08:00,870
Pamięć staje się nieważne.

155
00:08:00,870 --> 00:08:04,990
>> Więc musimy zachować wokół wskaźnik do
Kolejnym elementem, możemy uwolnić

156
00:08:04,990 --> 00:08:08,360
bieżący element, a następnie możemy aktualizować
nasz obecny element wskazać

157
00:08:08,360 --> 00:08:09,550
Kolejnym elementem.

158
00:08:09,550 --> 00:08:12,800
Będziemy pętli, podczas gdy istnieją elementy
w tej połączonej listy.

159
00:08:12,800 --> 00:08:15,620
Zrobimy to na zawsze związane
Wykazy w hashtable.

160
00:08:15,620 --> 00:08:19,460
A gdy już skończysz z tym, mamy
Hashtable całkowicie rozładowane, a

161
00:08:19,460 --> 00:08:20,190
skończymy.

162
00:08:20,190 --> 00:08:23,200
Więc jest to niemożliwe do rozładunku
kiedykolwiek zwróci false.

163
00:08:23,200 --> 00:08:26,470
A kiedy skończymy, możemy
po prostu wrócić prawdziwe.

164
00:08:26,470 --> 00:08:29,000
>> Dajmy rozwiązanie to spróbować.

165
00:08:29,000 --> 00:08:33,070
Warto więc spojrzeć na to, co nasze
węzeł struktura będzie wyglądać.

166
00:08:33,070 --> 00:08:36,220
Tutaj widzimy, będziemy mieć bool
Słowo i węzeł struct * dzieci

167
00:08:36,220 --> 00:08:37,470
Uchwyt alfabetu.

168
00:08:37,470 --> 00:08:38,929

169
00:08:38,929 --> 00:08:42,020
Tak więc pierwszą rzeczą, może być
zastanawiasz się, dlaczego jest ALFABET

170
00:08:42,020 --> 00:08:44,660
wydanie zdefiniowane jako 27?

171
00:08:44,660 --> 00:08:47,900
Cóż, pamiętaj, że będziemy potrzebować
do obsługi apostrof.

172
00:08:47,900 --> 00:08:51,910
Tak, że będzie nieco od
Szczególnym przypadkiem w całym programie.

173
00:08:51,910 --> 00:08:54,710
>> Teraz pamiętam, jak trie
faktycznie działa.

174
00:08:54,710 --> 00:08:59,380
Powiedzmy, że mamy do indeksowania słowo
"koty". Następnie z korzenia trie,

175
00:08:59,380 --> 00:09:02,610
będziemy patrzeć na dzieci
macierz, i mamy zamiar spojrzeć na

176
00:09:02,610 --> 00:09:08,090
Indeks, który odpowiada na list
C. Tak więc, która jest indeksowana 2.

177
00:09:08,090 --> 00:09:11,530
Tak więc biorąc pod uwagę, że wola
dać nam nowy węzeł.

178
00:09:11,530 --> 00:09:13,820
A potem będziemy pracować z tego węzła.

179
00:09:13,820 --> 00:09:17,770
>> Tak więc biorąc pod uwagę, że węzeł, po raz kolejny jesteśmy
będzie wyglądać na tablicy dzieci.

180
00:09:17,770 --> 00:09:22,110
I będziemy patrzeć na indeksie zerowym
odpowiadać A u kota.

181
00:09:22,110 --> 00:09:27,170
Tak więc mamy zamiar udać się do tego węzła,
i biorąc pod uwagę, że węzeł jedziemy

182
00:09:27,170 --> 00:09:31,090
patrzeć na koniec, że to odpowiada
do T. i przeniesienie się do tego węzła,

183
00:09:31,090 --> 00:09:35,530
w końcu mamy zupełnie wyglądał
przez nasze słowo "kot". A teraz bool

184
00:09:35,530 --> 00:09:40,960
Słowo ma wskazać, czy
to dane słowo jest w rzeczywistości słowo.

185
00:09:40,960 --> 00:09:43,470
>> Więc po co nam ten szczególny przypadek?

186
00:09:43,470 --> 00:09:47,700
No i co z tego słowa "katastrofa"
jest w naszym słowniku, ale

187
00:09:47,700 --> 00:09:50,150
słowo "kot" nie jest?

188
00:09:50,150 --> 00:09:54,580
Tak i patrzy, czy słowo "kot"
jest w naszym słowniku, jesteśmy

189
00:09:54,580 --> 00:09:59,970
będzie skutecznie przeglądać
Wskaźniki C-węzeł-T w regionie.

190
00:09:59,970 --> 00:10:04,290
Ale to tylko dlatego, że katastrofa
się do tworzenia węzłów na drodze

191
00:10:04,290 --> 00:10:07,190
z C-A-T, aż do
koniec słowa.

192
00:10:07,190 --> 00:10:12,020
Więc bool słowo to jest używane do wskazania, czy
ta konkretna lokalizacja

193
00:10:12,020 --> 00:10:14,310
faktycznie oznacza słowo.

194
00:10:14,310 --> 00:10:15,140
>> Dobrze.

195
00:10:15,140 --> 00:10:19,310
Więc teraz, że wiemy, co to jest Trie
będzie wyglądać, przyjrzyjmy

196
00:10:19,310 --> 00:10:20,730
funkcję ładowania.

197
00:10:20,730 --> 00:10:24,610
Więc obciążenie będzie powrócić bool
do tego, czy uda nam się lub

198
00:10:24,610 --> 00:10:26,720
bezskutecznie załadowany słownik.

199
00:10:26,720 --> 00:10:30,460
I to ma być słownik
które chcemy załadować.

200
00:10:30,460 --> 00:10:33,930
>> Tak więc pierwszą rzeczą, że jesteśmy zrobić, to otworzyć
do tego słownika do czytania.

201
00:10:33,930 --> 00:10:36,160
I musimy się upewnić,
nie powiedzie się.

202
00:10:36,160 --> 00:10:39,580
Tak więc, jeśli nie słownika
pomyślnie otwarty, zwróci

203
00:10:39,580 --> 00:10:42,400
null, w tym przypadku mamy
będzie return false.

204
00:10:42,400 --> 00:10:47,230
Ale zakładając, że z powodzeniem
otwarte, to rzeczywiście możemy przeczytać

205
00:10:47,230 --> 00:10:48,220
przez słownika.

206
00:10:48,220 --> 00:10:50,880
>> Tak więc pierwszą rzeczą, którą mamy zamiar
chcę zrobić, to musimy to

207
00:10:50,880 --> 00:10:52,500
zmienna globalna korzeń.

208
00:10:52,500 --> 00:10:56,190
Teraz głównym będzie węzeł *.

209
00:10:56,190 --> 00:10:59,760
To jest szczyt naszej trie, że jesteśmy
będzie iteracja.

210
00:10:59,760 --> 00:11:02,660
Tak więc pierwszą rzeczą, że idziemy
chce zrobić to przeznaczyć

211
00:11:02,660 --> 00:11:04,140
Pamięć dla naszego korzenia.

212
00:11:04,140 --> 00:11:07,980
Zauważmy, że używamy calloc
Funkcja, która jest zasadniczo taka sama

213
00:11:07,980 --> 00:11:11,500
jako funkcji malloc, oprócz tego, że jest
gwarancją zwrotu, że coś jest

214
00:11:11,500 --> 00:11:13,180
całkowicie wyzerowany.

215
00:11:13,180 --> 00:11:17,290
Więc jeśli kiedyś malloc, musielibyśmy
przejść przez wszystkie wskaźniki w naszym

216
00:11:17,290 --> 00:11:20,160
węzeł, i upewnij się, że
wszystkie są puste.

217
00:11:20,160 --> 00:11:22,710
Więc calloc zrobi to za nas.

218
00:11:22,710 --> 00:11:26,330
>> Teraz, podobnie jak malloc, musimy dokonać
upewnić się, że podział był rzeczywiście

219
00:11:26,330 --> 00:11:27,520
sukces.

220
00:11:27,520 --> 00:11:29,990
Jeśli ten wrócił null, wówczas
należy zamknąć lub słownik

221
00:11:29,990 --> 00:11:32,100
złożyć i return false.

222
00:11:32,100 --> 00:11:36,835
Tak więc przy założeniu, że podział został
sukces, będziemy korzystać z węzła *

223
00:11:36,835 --> 00:11:40,270
kursor do iteracji naszej trie.

224
00:11:40,270 --> 00:11:43,890
Więc nasze korzenie nigdy nie zmieni,
ale mamy zamiar użyć kursora do

225
00:11:43,890 --> 00:11:47,875
faktycznie przejść od węzła do węzła.

226
00:11:47,875 --> 00:11:50,940
>> Więc to dla pętli przegląda
za pomocą pliku słownika.

227
00:11:50,940 --> 00:11:53,670
I używamy fgetc.

228
00:11:53,670 --> 00:11:56,290
Fgetc będzie chwycić wolny
znaków z pliku.

229
00:11:56,290 --> 00:11:59,370
Zamierzamy kontynuować pobieranie
znaków, a my nie docierają

230
00:11:59,370 --> 00:12:01,570
koniec pliku.

231
00:12:01,570 --> 00:12:03,480
>> Istnieją dwa przypadki, które musimy obsłużyć.

232
00:12:03,480 --> 00:12:06,610
Po pierwsze, jeśli charakter
nie nowa linia.

233
00:12:06,610 --> 00:12:10,450
Więc wiemy, czy to nowa linia, a następnie
mamy zamiar przenieść się do nowego słowa.

234
00:12:10,450 --> 00:12:15,240
Ale zakładając, że nie był to nowa linia, a następnie
tutaj, chcemy dowiedzieć się,

235
00:12:15,240 --> 00:12:18,380
Indeks jedziemy do indeksu w
W tablicy dzieci, które

236
00:12:18,380 --> 00:12:19,810
przyjrzeliśmy się wcześniej.

237
00:12:19,810 --> 00:12:23,880
>> Tak, jak powiedziałem wcześniej, musimy
Szczególnym przypadkiem apostrof.

238
00:12:23,880 --> 00:12:26,220
Zauważ, że używamy trójskładnikowej
Operator tutaj.

239
00:12:26,220 --> 00:12:29,580
Więc mamy zamiar przeczytać jak, jeśli
Czytamy w charakter był

240
00:12:29,580 --> 00:12:35,330
apostrof, następnie idziemy do ustawienia
index = "alfabet" -1, która będzie

241
00:12:35,330 --> 00:12:37,680
być indeks 26.

242
00:12:37,680 --> 00:12:41,130
>> Inny, gdyby nie apostrof, nie
mamy zamiar ustawić wskaźnik

243
00:12:41,130 --> 00:12:43,760
równa c -.

244
00:12:43,760 --> 00:12:49,030
Więc pamiętaj, powrót z poprzednio P-set,
c - ma dać nam

245
00:12:49,030 --> 00:12:53,410
Stanowisko alfabetyczny C. Więc jeśli
C jest literą, to będzie

246
00:12:53,410 --> 00:12:54,700
daje nam indeks zerowy.

247
00:12:54,700 --> 00:12:58,120
Do litery B, to daje
us indeks 1, i tak dalej.

248
00:12:58,120 --> 00:13:03,010
>> Więc to daje nam wskaźnik do
dzieci tablica, że ​​chcemy.

249
00:13:03,010 --> 00:13:08,890
Teraz, jeśli wskaźnik ten jest obecnie wartość null w
dzieci, co oznacza, że ​​węzeł

250
00:13:08,890 --> 00:13:11,830
obecnie nie istnieje
z tej ścieżki.

251
00:13:11,830 --> 00:13:15,160
Dlatego musimy przeznaczyć
Węzeł na tej drodze.

252
00:13:15,160 --> 00:13:16,550
To co zrobimy tutaj.

253
00:13:16,550 --> 00:13:20,690
>> Więc mamy zamiar ponownie użyć calloc
Funkcja, dzięki czemu nie mamy do

254
00:13:20,690 --> 00:13:22,880
wyzerować wszystkie wskaźniki.

255
00:13:22,880 --> 00:13:27,240
I znów trzeba sprawdzić
że calloc nie zawiódł.

256
00:13:27,240 --> 00:13:30,700
Jeśli calloc zawiódł, to musimy
wyładować wszystko, zamykać

257
00:13:30,700 --> 00:13:32,820
słownik i zwraca fałsz.

258
00:13:32,820 --> 00:13:40,050
Tak więc przy założeniu, że nie uda, to
stworzy nowe dziecko dla nas.

259
00:13:40,050 --> 00:13:41,930
, A następnie udamy się do tego dziecka.

260
00:13:41,930 --> 00:13:44,960
Nasz kursor iteracji
w dół do tego dziecka.

261
00:13:44,960 --> 00:13:49,330
>> Teraz, jeśli nie jest to wartość null, aby rozpocząć,
Następnie można po prostu iteracyjne kursor

262
00:13:49,330 --> 00:13:52,590
w dół do tego dziecka bez konieczności
konieczności przeznaczyć nic.

263
00:13:52,590 --> 00:13:56,730
Jest to przypadek, w którym po raz pierwszy się
przeznaczyć słowo "kot". I

264
00:13:56,730 --> 00:14:00,330
co oznacza, że ​​kiedy idziemy do przeznaczenia
"Katastrofa", nie musimy stworzyć

265
00:14:00,330 --> 00:14:01,680
węzły dla C-A-T ponownie.

266
00:14:01,680 --> 00:14:04,830
One już istnieją.

267
00:14:04,830 --> 00:14:06,080
>> Co to jest inny?

268
00:14:06,080 --> 00:14:10,480
Jest to stan, w którym c było
odwrotny ukośnik n, gdzie c to nowa linia.

269
00:14:10,480 --> 00:14:13,710
Oznacza to, że udało nam się
zakończone słowo.

270
00:14:13,710 --> 00:14:16,860
Teraz to, co chcemy zrobić, gdy
zakończone powodzeniem słowo?

271
00:14:16,860 --> 00:14:21,100
Zamierzamy wykorzystywać to pole słowo
wewnątrz naszego węzła struct.

272
00:14:21,100 --> 00:14:23,390
Chcemy ustawić, że na true.

273
00:14:23,390 --> 00:14:27,150
Tak, że wskazuje, że węzeł
wskazuje na sukces

274
00:14:27,150 --> 00:14:29,250
Słowo, rzeczywisty wyraz.

275
00:14:29,250 --> 00:14:30,940
>> Ustawiony, że na true.

276
00:14:30,940 --> 00:14:35,150
Chcemy przywrócić nasz kursor do punktu
na początku trie ponownie.

277
00:14:35,150 --> 00:14:40,160
I w końcu, zwiększamy naszą słownika
rozmiar, ponieważ okazało się, innej pracy.

278
00:14:40,160 --> 00:14:43,230
Więc będziemy dalej robić, że
Czytaj w znak po znaku,

279
00:14:43,230 --> 00:14:49,150
budowy nowych węzłów oraz w naszym trie
dla każdego słowa w słowniku, do momentu

280
00:14:49,150 --> 00:14:54,020
w końcu dotrzeć C! = EOF, w którym
przypadku możemy wyrwać się z pliku.

281
00:14:54,020 --> 00:14:57,050
>> Teraz są dwie sprawy w toku
które moglibyśmy trafić EOF.

282
00:14:57,050 --> 00:15:00,980
Pierwszym z nich jest, czy istnieje błąd
czytanie z pliku.

283
00:15:00,980 --> 00:15:03,470
Więc jeśli nie było błędów, my
Wystarczy typowy.

284
00:15:03,470 --> 00:15:06,460
Wyładować wszystko, blisko
plik, return false.

285
00:15:06,460 --> 00:15:09,810
Przy założeniu, że nie był błąd, to
po prostu oznacza, że ​​faktycznie hit koniec

286
00:15:09,810 --> 00:15:13,750
plik, w którym to przypadku, zamykamy
pliku i zwraca true, ponieważ my

287
00:15:13,750 --> 00:15:17,330
pomyślnie załadowany słownik
do naszego trie.

288
00:15:17,330 --> 00:15:20,170
>> Więc teraz niech sprawdzić czek.

289
00:15:20,170 --> 00:15:25,156
Patrząc na funkcję wyboru, widzimy
że kontrola będzie powrócić bool.

290
00:15:25,156 --> 00:15:29,680
Zwraca true, jeśli to słowo, które jest
były przekazywane jest w naszym trie.

291
00:15:29,680 --> 00:15:32,110
Zwraca false w przeciwnym wypadku.

292
00:15:32,110 --> 00:15:36,050
Więc jak można określić, czy
to słowo jest w naszym trie?

293
00:15:36,050 --> 00:15:40,190
>> Widzimy tutaj, że, podobnie jak poprzednio,
mamy zamiar użyć kursora do iteracji

294
00:15:40,190 --> 00:15:41,970
za pośrednictwem naszego trie.

295
00:15:41,970 --> 00:15:46,600
Teraz tu idziemy do iteracji
w ciągu całego naszego słowa.

296
00:15:46,600 --> 00:15:50,620
Więc iterowanie słowem jesteśmy w przeszłości,
zamierzamy ustalić

297
00:15:50,620 --> 00:15:56,400
Wskaźnik do tablicy, że dzieci
odpowiada wspornika I. Tak więc słowo to

298
00:15:56,400 --> 00:15:59,670
będzie wyglądać dokładnie tak, jak
obciążenia, w którym, jeśli słowo [i]

299
00:15:59,670 --> 00:16:03,310
jest apostrof, to chcemy
używać indeksu "alfabet" - 1.

300
00:16:03,310 --> 00:16:05,350
Ponieważ stwierdziliśmy, że
to gdzie jedziemy do przechowywania

301
00:16:05,350 --> 00:16:07,100
apostrofy.

302
00:16:07,100 --> 00:16:11,780
>> Jeszcze będziemy używać dwóch dolnych słowo
Uchwyt I. Więc pamiętaj, że słowo może

303
00:16:11,780 --> 00:16:13,920
mieć dowolny kapitalizacji.

304
00:16:13,920 --> 00:16:17,540
A więc chcemy się upewnić, że jesteśmy
stosując małą wersję rzeczy.

305
00:16:17,540 --> 00:16:21,920
I odejmujemy od tego "a" na raz
ponownie daje nam alfabetyczne

306
00:16:21,920 --> 00:16:23,880
Stanowisko tego znaku.

307
00:16:23,880 --> 00:16:27,680
Tak, że to będzie nasz indeks
do tablicy dzieci.

308
00:16:27,680 --> 00:16:32,420
>> I teraz, jeżeli indeks do dzieci
tablicy jest null, co oznacza, że

309
00:16:32,420 --> 00:16:34,990
nie może już kontynuować Iterowanie
w dół naszego trie.

310
00:16:34,990 --> 00:16:38,870
Jeśli tak jest, to słowo nie może
może być w naszym trie.

311
00:16:38,870 --> 00:16:42,340
Ponieważ gdyby tak było, że byłoby
znaczy nie będzie droga

312
00:16:42,340 --> 00:16:43,510
w dół do tego słowa.

313
00:16:43,510 --> 00:16:45,290
I nigdy nie spotkać null.

314
00:16:45,290 --> 00:16:47,850
Więc napotkania NULL, my return false.

315
00:16:47,850 --> 00:16:49,840
Słowa nie ma w słowniku.

316
00:16:49,840 --> 00:16:53,660
Gdyby nie to, null, to jesteśmy
zamierza kontynuować Iterowanie.

317
00:16:53,660 --> 00:16:57,220
>> Więc będziemy się tam kursor
aby wskazać, że szczególnie

318
00:16:57,220 --> 00:16:59,760
węzeł w tym indeksie.

319
00:16:59,760 --> 00:17:03,150
Mamy dalej robić, że w całym
Całe słowo, zakładając

320
00:17:03,150 --> 00:17:03,950
nigdy nie trafić zerowy.

321
00:17:03,950 --> 00:17:07,220
Oznacza to, że udało nam się przejść przez
całe słowo i znaleźć

322
00:17:07,220 --> 00:17:08,920
węzeł w naszej próbie.

323
00:17:08,920 --> 00:17:10,770
Ale nie całkiem jeszcze zrobić.

324
00:17:10,770 --> 00:17:12,290
>> Nie chcemy, aby tylko wrócić prawda.

325
00:17:12,290 --> 00:17:14,770
Chcemy wrócić kursora> słowo.

326
00:17:14,770 --> 00:17:18,980
Ponieważ pamiętam raz, jest "kot" nie jest
w naszym słowniku, a "katastrofa"

327
00:17:18,980 --> 00:17:22,935
jest, to z powodzeniem możemy uzyskać
przez słowo "kot". Ale kursor

328
00:17:22,935 --> 00:17:25,760
Słowo będzie fałszywe i nie prawdziwe.

329
00:17:25,760 --> 00:17:30,930
Więc wracamy do wskazania kursora słowo
czy węzeł jest faktycznie słowo.

330
00:17:30,930 --> 00:17:32,470
I to jest to do odprawy.

331
00:17:32,470 --> 00:17:34,250
>> Warto więc sprawdzić rozmiar.

332
00:17:34,250 --> 00:17:37,350
Więc rozmiar będzie bardzo łatwe
gdyż należy pamiętać, obciążenia, jesteśmy

333
00:17:37,350 --> 00:17:41,430
zwiększając rozmiar słownika dla
każde słowo, które napotykamy.

334
00:17:41,430 --> 00:17:45,350
Więc rozmiar jest po prostu będzie
powrót rozmiar słownika.

335
00:17:45,350 --> 00:17:47,390
I to jest to.

336
00:17:47,390 --> 00:17:50,590
>> Więc wreszcie mamy rozładować.

337
00:17:50,590 --> 00:17:55,100
Tak rozładować, będziemy korzystać
rekurencyjna funkcja faktycznie zrobić wszystko

338
00:17:55,100 --> 00:17:56,530
pracy dla nas.

339
00:17:56,530 --> 00:17:59,340
Więc nasza funkcja będzie
miano na rozładunku.

340
00:17:59,340 --> 00:18:01,650
Co jest kiszonki zrobić?

341
00:18:01,650 --> 00:18:06,580
Widzimy tutaj, że będzie odciążający
iteracyjne nad wszystkie dzieci w

342
00:18:06,580 --> 00:18:08,410
ten konkretny węzeł.

343
00:18:08,410 --> 00:18:11,750
I jeśli węzeł potomny nie jest
null, a następnie jedziemy do

344
00:18:11,750 --> 00:18:13,730
rozładować węzeł podrzędny.

345
00:18:13,730 --> 00:18:18,010
>> Więc to ty rekurencyjnie rozładować
wszystkie nasze dzieci.

346
00:18:18,010 --> 00:18:21,080
Kiedy jesteś pewien, że wszystkie nasze dzieci
zostały wyładowane, to

347
00:18:21,080 --> 00:18:25,210
może się uwolnić, więc
wyładować się.

348
00:18:25,210 --> 00:18:29,460
To będzie działać rekurencyjnie
wyładować całą TRIE.

349
00:18:29,460 --> 00:18:32,850
A następnie po dokonaniu rejestracji,
możemy po prostu wrócić prawdziwe.

350
00:18:32,850 --> 00:18:34,210
Rozładunek nie może się nie powieść.

351
00:18:34,210 --> 00:18:35,710
My tylko uwolnienie rzeczy.

352
00:18:35,710 --> 00:18:38,870
Więc kiedy już skończysz uwalniając
wszystko, zwraca true.

353
00:18:38,870 --> 00:18:40,320
I to jest to.

354
00:18:40,320 --> 00:18:41,080
Nazywam się Rob.

355
00:18:41,080 --> 00:18:42,426
I to był ortografii.

356
00:18:42,426 --> 00:18:47,830
>> [MUZYKA GRA]