1
00:00:00,000 --> 00:00:12,350
>> [Muzikavimo]

2
00:00:12,350 --> 00:00:13,050
>> ROB BOWDEN: Sveiki.

3
00:00:13,050 --> 00:00:13,640
Aš Rob.

4
00:00:13,640 --> 00:00:16,210
Ir tegul šį sprendimą iš.

5
00:00:16,210 --> 00:00:20,070
Taigi čia mes ketiname įgyvendinti
bendras stalas.

6
00:00:20,070 --> 00:00:24,090
Mes matome, kad struct mazgas mūsų
lentelė atrodys tai.

7
00:00:24,090 --> 00:00:28,710
Taigi jis ketina turėti char žodį
masyvo dydis ilgis + 1.

8
00:00:28,710 --> 00:00:32,259
Nepamirškite + 1, nes maksimalus
žodis žodyne yra 45

9
00:00:32,259 --> 00:00:33,130
simbolių.

10
00:00:33,130 --> 00:00:37,070
Ir tada mes ketiname reikia vieną papildomą
personažas pasvirąjį nulio.

11
00:00:37,070 --> 00:00:40,870
>> Ir tada mūsų Hashtable kiekvienoje
kibiras ketina saugoti

12
00:00:40,870 --> 00:00:42,320
susijęs sąrašas mazgų.

13
00:00:42,320 --> 00:00:44,420
Mes nedarome linijinė zondavimo čia.

14
00:00:44,420 --> 00:00:48,430
Ir todėl, kad rodo į kitą
elementas kibirą, mes turime

15
00:00:48,430 --> 00:00:50,390
struct mazgas * šalia.

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

17
00:00:51,110 --> 00:00:53,090
Štai ką mazgas atrodo.

18
00:00:53,090 --> 00:00:56,180
>> Dabar čia yra deklaracija
mūsų Hashtable.

19
00:00:56,180 --> 00:00:59,640
Ji ketina turėti 16.834 kibirus.

20
00:00:59,640 --> 00:01:01,910
Tačiau šis skaičius nėra iš tikrųjų klausimas.

21
00:01:01,910 --> 00:01:05,450
Ir pagaliau, mes ketiname turėti
pasaulinį kintamąjį Hashtable dydis, kuris

22
00:01:05,450 --> 00:01:07,000
ketina pradėti nuo nulio.

23
00:01:07,000 --> 00:01:10,760
Ir jis ketina stebėti, kaip
daug žodžių yra mūsų žodyną.

24
00:01:10,760 --> 00:01:13,710
>> Taigi galime pažvelgti apkrovos išvaizdą.

25
00:01:13,710 --> 00:01:16,390
Atkreipkite dėmesį, kad apkrovos, jis grįžta bool.

26
00:01:16,390 --> 00:01:20,530
Jūs grąžina true, jei ji buvo sėkmingai
pakrautas, ir false kitaip.

27
00:01:20,530 --> 00:01:23,990
Ir tai trunka const char * žodyną,
kuris yra žodynas

28
00:01:23,990 --> 00:01:25,280
kad mes norime atidaryti.

29
00:01:25,280 --> 00:01:27,170
Štai pirmas dalykas,
mes ketiname daryti.

30
00:01:27,170 --> 00:01:29,500
>> Mes ketiname fopen
žodynas skaityti.

31
00:01:29,500 --> 00:01:31,680
Ir mes turėsime padaryti
įsitikinkite, kad ji pavyko.

32
00:01:31,680 --> 00:01:35,920
Taigi, jei jis grįžo NULL, tada mes ne
sėkmingai atidaryti žodyną.

33
00:01:35,920 --> 00:01:37,440
Ir mes turime grįžti klaidinga.

34
00:01:37,440 --> 00:01:41,580
Tačiau darant prielaidą, kad jis sėkmingai padarė
atidaryti, tada mes norime skaityti

35
00:01:41,580 --> 00:01:42,400
žodynas.

36
00:01:42,400 --> 00:01:46,450
Taigi neišmeskite apsisukimo kol mes radote
priežastis išeiti iš šio ciklo,

37
00:01:46,450 --> 00:01:47,570
kurį matysime.

38
00:01:47,570 --> 00:01:48,920
Taigi neišmeskite apsisukimo.

39
00:01:48,920 --> 00:01:51,780
>> Ir dabar mes ketiname
malloc vieną mazgą.

40
00:01:51,780 --> 00:01:54,020
Ir, žinoma, mes turime
į orą vėl patikrinkite.

41
00:01:54,020 --> 00:01:58,680
Taigi, jei mallocing nepavyko, tada
norime iškrauti bet kokį mazgą, kad mes

42
00:01:58,680 --> 00:02:02,590
atsitiko malloc prieš, uždarykite
žodynas ir return false.

43
00:02:02,590 --> 00:02:06,830
Tačiau ignoruojant, kad, darant prielaidą, mes
pavyko, tada mes norite naudoti fscanf

44
00:02:06,830 --> 00:02:12,400
skaityti vieną žodį iš mūsų
žodyną į mūsų mazgas.

45
00:02:12,400 --> 00:02:17,940
Taigi nepamirškite, kad įrašas> žodis yra char
Žodis buferio dydis LENGHTH + 1

46
00:02:17,940 --> 00:02:20,300
kad mes ketiname saugoti žodį in

47
00:02:20,300 --> 00:02:25,070
>> Taigi fscanf ketina grįžti 1, kol
kaip ji galėjo sėkmingai

48
00:02:25,070 --> 00:02:26,750
skaityti žodį iš failo.

49
00:02:26,750 --> 00:02:30,460
Jei kuri nors klaida įvyksta, ar mes
pasiekti failo pabaigą, jis

50
00:02:30,460 --> 00:02:31,950
negrįš 1.

51
00:02:31,950 --> 00:02:35,180
Tokiu atveju jis negrįžta 1,
mes pagaliau ketina išeiti iš

52
00:02:35,180 --> 00:02:37,280
tai, o kilpos.

53
00:02:37,280 --> 00:02:42,770
Taigi matome, kad kai mes sėkmingai
skaityti žodis į

54
00:02:42,770 --> 00:02:48,270
įrašas> žodis, tada mes ketiname kad
Žodis naudojant mūsų maišos funkciją.

55
00:02:48,270 --> 00:02:49,580
>> Paimkime pažvelgti
maišos funkcija.

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

57
00:02:52,430 --> 00:02:55,610
Taigi jums nereikia tikrai reikia
tai suprasti.

58
00:02:55,610 --> 00:02:59,460
Ir iš tikrųjų mes tiesiog ištraukė šį maišos
veikti iš interneto.

59
00:02:59,460 --> 00:03:04,010
Vienintelis dalykas, kurį reikia pripažinti,
kad tai mano const char * žodį.

60
00:03:04,010 --> 00:03:08,960
Taigi, tai, atsižvelgiant eilutę kaip įvesties ir
grąžinant unsigned int kaip produkcija.

61
00:03:08,960 --> 00:03:12,360
Taigi, kad viskas maišos funkcija, tai
trunka įvesties ir suteikia jums

62
00:03:12,360 --> 00:03:14,490
rodyklė į Hashtable.

63
00:03:14,490 --> 00:03:18,530
>> Atkreipkite dėmesį, kad mes Moding pagal NUM_BUCKETS,
kad grąžinta reikšmė

64
00:03:18,530 --> 00:03:21,730
iš tikrųjų yra į Hashtable puslapis
ir neindeksuoja už

65
00:03:21,730 --> 00:03:24,320
Ribas masyvo.

66
00:03:24,320 --> 00:03:28,060
Taigi, turint omenyje, kad funkcija, mes ketiname
maišos žodį, kad mes skaityti

67
00:03:28,060 --> 00:03:29,390
žodynas.

68
00:03:29,390 --> 00:03:31,700
Ir tada mes ketiname naudoti
kad maišos įterpti

69
00:03:31,700 --> 00:03:33,750
įrašas į Hashtable.

70
00:03:33,750 --> 00:03:38,520
>> Dabar Hashtable maišos yra dabartinė
susijęs sąrašą lentelėje.

71
00:03:38,520 --> 00:03:41,410
Ir tai labai įmanoma,
kad tai tik NULL.

72
00:03:41,410 --> 00:03:44,960
Mes norime įterpti mūsų bendrovėms patekti į rinką
pradžioje šio susijęs sąrašą.

73
00:03:44,960 --> 00:03:48,600
Ir todėl mes ketiname turėti mūsų srovę
įvažiavimo į ką Hashtable

74
00:03:48,600 --> 00:03:50,380
Šiuo metu nurodo.

75
00:03:50,380 --> 00:03:53,310
Ir tada mes ketiname saugoti,
ir tuo Hashtable

76
00:03:53,310 --> 00:03:55,350
maišos, dabartinis įrašas.

77
00:03:55,350 --> 00:03:59,320
Taigi šios dvi linijos sėkmingai įterpti
prie pradžios įrašas

78
00:03:59,320 --> 00:04:02,260
susijęs sąrašas tuo indeksą
į Hashtable.

79
00:04:02,260 --> 00:04:04,900
>> Kai baigsime su tuo, mes žinome,
kad mes rasti kitą žodį

80
00:04:04,900 --> 00:04:07,790
žodyną, ir mes prieaugio dar kartą.

81
00:04:07,790 --> 00:04:13,960
Taigi, mes nuolat tai daryti, kad iki fscanf
pagaliau grįžo kažką ne 1 metu

82
00:04:13,960 --> 00:04:16,950
kuris taškas prisiminti, kad
turime įėjimas nemokamas.

83
00:04:16,950 --> 00:04:19,459
Taigi čia mes malloced įrašą.

84
00:04:19,459 --> 00:04:21,329
Ir mes bandėme skaityti kažką
iš žodyno.

85
00:04:21,329 --> 00:04:23,910
Ir mes ne sėkmingai skaityti
kažkas iš žodyno, į

86
00:04:23,910 --> 00:04:26,650
tokiu atveju mes turime išlaisvinti įrašą
kad mes niekada iš tikrųjų išleisti į

87
00:04:26,650 --> 00:04:29,140
Hashtable ir galiausiai lūžta.

88
00:04:29,140 --> 00:04:32,750
>> Kai mes išeiti, mes turime pamatyti, gerai,
Ar mes išeiti, nes

89
00:04:32,750 --> 00:04:34,360
buvo klaida skaitant iš failo?

90
00:04:34,360 --> 00:04:37,120
O gal mes išeiti, nes mes
pasiektas failo galas?

91
00:04:37,120 --> 00:04:39,480
Jei ten buvo klaida, tada
mes norime grįžti klaidinga.

92
00:04:39,480 --> 00:04:40,930
Kadangi krovinys nebuvo sėkmingas.

93
00:04:40,930 --> 00:04:43,890
Ir į šį procesą mes norime iškrauti
visus žodžius, kuriuos mes skaitome, ir

94
00:04:43,890 --> 00:04:45,670
uždaryti žodyno failą.

95
00:04:45,670 --> 00:04:48,740
>> Darant prielaidą, kad mes iš tikrųjų pavyko, tada mes tiesiog
vis dar reikia uždaryti žodyną

96
00:04:48,740 --> 00:04:53,040
failą, ir galiausiai grąžina true, nes mes
sėkmingai įkeltas žodynas.

97
00:04:53,040 --> 00:04:54,420
Štai ir viskas kroviniu.

98
00:04:54,420 --> 00:04:59,020
Taigi, dabar patikrinti, nes pakrautas Hashtable,
ketina atrodyti taip.

99
00:04:59,020 --> 00:05:03,140
Taigi patikrinti, jis grįžta bool, kuris yra
ketina nurodyti, ar perduota

100
00:05:03,140 --> 00:05:07,530
į char * žodžiu, ar praėjo
į eilutės yra mūsų žodyną.

101
00:05:07,530 --> 00:05:09,890
Taigi, jei tai yra žodyne,
jei tai yra mūsų Hashtable,

102
00:05:09,890 --> 00:05:11,170
grįšime tiesa.

103
00:05:11,170 --> 00:05:13,380
Ir jei tai nėra, mes return false.

104
00:05:13,380 --> 00:05:17,740
>> Atsižvelgiant į tai praėjo žodžiu, mes
ketina koduoti žodį.

105
00:05:17,740 --> 00:05:22,110
Dabar svarbiausias dalykas pripažinti,
kad apkrovos mes žinojome, kad visi

106
00:05:22,110 --> 00:05:23,820
žodžiai mes ketiname būti mažosiomis raidėmis.

107
00:05:23,820 --> 00:05:25,820
Bet čia mes ne tokie tikri.

108
00:05:25,820 --> 00:05:29,510
Jei mes atsižvelgti į mūsų maišos funkcija atrodo,
mūsų maišos funkcija faktiškai

109
00:05:29,510 --> 00:05:32,700
yra mažesnis korpusas kiekvienas simbolis
žodžio.

110
00:05:32,700 --> 00:05:37,940
Taigi, nepriklausomai nuo kapitalizacijos
žodis, mūsų maišos funkcija grąžinimas

111
00:05:37,940 --> 00:05:42,270
pats indeksas kokia
kapitalizacija, kaip ji turėtų

112
00:05:42,270 --> 00:05:45,280
grąžinama visiškai mažosiomis raidėmis
portalo žodį.

113
00:05:45,280 --> 00:05:46,600
Gerai.

114
00:05:46,600 --> 00:05:49,790
Tai mūsų indeksas yra į
Hashtable šio žodžio.

115
00:05:49,790 --> 00:05:52,940
>> Dabar tai už linijos ketina
pakartoti per susietą sąrašą

116
00:05:52,940 --> 00:05:55,000
kad buvo tuo indeksu.

117
00:05:55,000 --> 00:05:59,610
Taigi pastebėsite mes Inicijuojama įrašą
atkreipti dėmesį į šio indekso.

118
00:05:59,610 --> 00:06:02,750
Mes ketiname tęsti
o įrašas! = NULL.

119
00:06:02,750 --> 00:06:07,770
Ir atminkite, kad atnaujinus žymiklį
Mūsų susijęs sąrašas įrašas = įrašas> šalia.

120
00:06:07,770 --> 00:06:14,400
Taigi turime esamą prieigos tašką prie
Kitas darbotvarkės punktas susijusioje sąrašą.

121
00:06:14,400 --> 00:06:19,250
>> Taigi kiekvieno susieto sąrašo įrašą,
mes ketiname naudoti strcasecmp.

122
00:06:19,250 --> 00:06:20,330
Tai ne strcomp.

123
00:06:20,330 --> 00:06:23,780
Nes dar kartą, mes norime
daryti tai, ko bylą insensitively.

124
00:06:23,780 --> 00:06:27,870
Taigi mes naudojame strcasecmp palyginti
Žodis, kuris buvo priimtas per šį

125
00:06:27,870 --> 00:06:31,860
funkcija prieš žodį
kad yra šio įrašo.

126
00:06:31,860 --> 00:06:35,570
Jei ji grąžina nulį, tai reiškia, kad buvo
rungtynės, tokiu atveju mes norime

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

128
00:06:36,630 --> 00:06:39,590
Mes sėkmingai surado
žodis mūsų Hashtable.

129
00:06:39,590 --> 00:06:43,040
>> Jei ten buvo ne rungtynės, tada mes
ketina kilpos ir vėl pažvelgti

130
00:06:43,040 --> 00:06:43,990
Kitas įrašas.

131
00:06:43,990 --> 00:06:47,640
Ir mes ir toliau Looping nors
yra Įrašų šiame susijęs sąrašą.

132
00:06:47,640 --> 00:06:50,160
Kas atsitiks, jei mes pertrauka
iš čia už linijos?

133
00:06:50,160 --> 00:06:55,110
Tai reiškia, kad mes ne rasti įrašą,
atitiko šį žodį, tokiu atveju

134
00:06:55,110 --> 00:07:00,220
mes return false nurodyti, kad mūsų
Hashtable nebuvo šį žodį.

135
00:07:00,220 --> 00:07:02,540
Ir tai patikrinti.

136
00:07:02,540 --> 00:07:04,790
>> Taigi galime pažvelgti dydžio išvaizdą.

137
00:07:04,790 --> 00:07:06,970
Dabar dydis bus gana paprasta.

138
00:07:06,970 --> 00:07:11,080
Nuo Prisimenu apkrova, už kiekvieną žodį
mes nustatėme, mes padidinamas pasaulio

139
00:07:11,080 --> 00:07:12,880
kintamasis Hashtable dydis.

140
00:07:12,880 --> 00:07:16,480
Taigi dydis funkcija tiesiog vyksta
grįžti pasaulinį kintamąjį.

141
00:07:16,480 --> 00:07:18,150
Štai ir viskas.

142
00:07:18,150 --> 00:07:22,300
>> Dabar pagaliau turime iškrauti
žodynas kartą viskas daroma.

143
00:07:22,300 --> 00:07:25,340
Taigi, kaip mes ketiname daryti?

144
00:07:25,340 --> 00:07:30,440
Štai čia mes apsisukimo per
visi mūsų stalo kibirai.

145
00:07:30,440 --> 00:07:33,240
Taigi yra NUM_BUCKETS kibirai.

146
00:07:33,240 --> 00:07:37,410
Ir kiekvieną susietą sąrašą mūsų
Hashtable, mes ketiname kilpa per

147
00:07:37,410 --> 00:07:41,070
susieto sąrašo visuma,
išlaisvina kiekvieną elementą.

148
00:07:41,070 --> 00:07:42,900
>> Dabar mes turime būti atsargūs.

149
00:07:42,900 --> 00:07:47,910
Taigi čia mes turime laikiną kintamąjį
tai saugoti žymiklį į kitą

150
00:07:47,910 --> 00:07:49,730
elementas susijęs sąrašą.

151
00:07:49,730 --> 00:07:52,140
Ir tada mes ketiname nemokamai
dabartinis elementas.

152
00:07:52,140 --> 00:07:55,990
Mes turime būti tikri, kad mes darome tai, nes mes
gali ne tik atlaisvinti einamųjų elemento

153
00:07:55,990 --> 00:07:59,180
ir tada bandykite ir atidarykite kitą žymeklį,
nes kai mes išlaisvino jį,

154
00:07:59,180 --> 00:08:00,870
atmintis tampa negaliojančiu.

155
00:08:00,870 --> 00:08:04,990
>> Taigi, mes turime išlaikyti aplink rodyklę į
Kitas elementas, tada mes galime nemokamai

156
00:08:04,990 --> 00:08:08,360
dabartinis elementas, ir tada mes galime atnaujinti
mūsų dabartinis elementas rodo

157
00:08:08,360 --> 00:08:09,550
kitas elementas.

158
00:08:09,550 --> 00:08:12,800
Mes kilpa nors yra elementai
Šiame susijęs sąrašą.

159
00:08:12,800 --> 00:08:15,620
Mes padarysime, kad visi susiję
sąrašus Hashtable.

160
00:08:15,620 --> 00:08:19,460
Ir kai mes baigsite, kad mes
visiškai iškraunamas į Hashtable ir

161
00:08:19,460 --> 00:08:20,190
baigsime.

162
00:08:20,190 --> 00:08:23,200
Todėl neįmanoma iškrauti
kada nors grįžti klaidinga.

163
00:08:23,200 --> 00:08:26,470
Ir kai mes baigsime mes
tiesiog grąžina true.

164
00:08:26,470 --> 00:08:29,000
>> Leiskite duoti šis sprendimas pabandyti.

165
00:08:29,000 --> 00:08:33,070
Taigi galime pažvelgti, kas mūsų išvaizdą
struct mazgas atrodys.

166
00:08:33,070 --> 00:08:36,220
Čia mes matome, mes ketiname turėti bool
žodis ir struct mazgas * vaikai

167
00:08:36,220 --> 00:08:37,470
laikiklis abėcėlė.

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

169
00:08:38,929 --> 00:08:42,020
Taigi pirmas dalykas, kurį gali būti
įdomu, kodėl ALPHABET

170
00:08:42,020 --> 00:08:44,660
ED apibrėžiamas kaip 27?

171
00:08:44,660 --> 00:08:47,900
Na, nepamirškite, kad mes ketiname reikia
reikia tvarkyti kabutes.

172
00:08:47,900 --> 00:08:51,910
Taigi, tai bus šiek tiek
Ypatingas atvejis per šią programą.

173
00:08:51,910 --> 00:08:54,710
>> Dabar prisimenu, kaip trie
iš tiesų veikia.

174
00:08:54,710 --> 00:08:59,380
Tarkime, mes indeksavimo žodį
"katės." Tada iš TRIE šaknis,

175
00:08:59,380 --> 00:09:02,610
mes ketiname pažvelgti į vaikų
masyvas, ir mes ketiname pažvelgti į

176
00:09:02,610 --> 00:09:08,090
indeksas, kuris atitinka raide
C. Taigi, kad bus indeksuojamos 2.

177
00:09:08,090 --> 00:09:11,530
Taigi, atsižvelgiant į tai, kad bus
suteikia mums naują mazgas.

178
00:09:11,530 --> 00:09:13,820
Ir tada mes dirbame nuo to mazgo.

179
00:09:13,820 --> 00:09:17,770
>> Taigi, atsižvelgiant į tai, mazgas, mes dar kartą
ketiname pažvelgti į vaikų masyvo.

180
00:09:17,770 --> 00:09:22,110
Ir mes ketiname pažvelgti į nulinę indekso
atitikti kačių A.

181
00:09:22,110 --> 00:09:27,170
Taigi mes ketiname eiti į tą mazgą,
ir atsižvelgiant į tai, kad mazgas mes ketiname

182
00:09:27,170 --> 00:09:31,090
ieškoti pabaigoje tai atitinka
į T. juda į tą mazgą,

183
00:09:31,090 --> 00:09:35,530
pagaliau, mes turime visiškai atrodė
per mūsų žodis "katė". Ir dabar bool

184
00:09:35,530 --> 00:09:40,960
žodis turėtų nurodyti, ar
turint mintyje tai žodis iš tikrųjų žodis.

185
00:09:40,960 --> 00:09:43,470
>> Tad kodėl mes turime tą ypatingą bylą?

186
00:09:43,470 --> 00:09:47,700
Na, ką žodis "katastrofa"
yra mūsų žodyne, tačiau

187
00:09:47,700 --> 00:09:50,150
žodis "katė" nėra?

188
00:09:50,150 --> 00:09:54,580
Taigi, ir nori pamatyti, jei žodis "katė"
yra mūsų žodyną, mes

189
00:09:54,580 --> 00:09:59,970
vyksta sėkmingai ieškoti per
indeksai C-T regiono mazgas.

190
00:09:59,970 --> 00:10:04,290
Bet tai tik dėl to, katastrofa
atsitiko sukurti mazgų kelyje

191
00:10:04,290 --> 00:10:07,190
iš C-A-T, visi būdas
Žodžio pabaiga.

192
00:10:07,190 --> 00:10:12,020
Taigi bool žodis yra naudojamas nurodyti, ar
tai pirma vieta

193
00:10:12,020 --> 00:10:14,310
iš tikrųjų rodo žodį.

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

195
00:10:15,140 --> 00:10:19,310
Taigi dabar, kad mes žinome, ką jis trie yra
atrodys, pažvelkime

196
00:10:19,310 --> 00:10:20,730
įkelti funkciją.

197
00:10:20,730 --> 00:10:24,610
Taigi apkrova ketina grįžti bool
Dėl klausimo, ar mes sėkmingai arba

198
00:10:24,610 --> 00:10:26,720
nesėkmingai pakrautas žodynas.

199
00:10:26,720 --> 00:10:30,460
Ir tai bus žodynas
kad mes norime įkelti.

200
00:10:30,460 --> 00:10:33,930
>> Taigi pirmas dalykas, mes padaryti, tai atidaryti
iki to žodyne svarstymą.

201
00:10:33,930 --> 00:10:36,160
Ir mes turime įsitikinti,
mes nepamiršo.

202
00:10:36,160 --> 00:10:39,580
Taigi, jei žodynas nebuvo
sėkmingai atidarytas, jis sugrįš

203
00:10:39,580 --> 00:10:42,400
null, tokiu atveju mes
ketina grįžti klaidinga.

204
00:10:42,400 --> 00:10:47,230
Tačiau darant prielaidą, kad jis sėkmingai
atidarytas, tada mes iš tiesų gali skaityti

205
00:10:47,230 --> 00:10:48,220
per žodyną.

206
00:10:48,220 --> 00:10:50,880
>> Taigi pirmas dalykas, kurį mes ketiname
norite padaryti, tai turime tai

207
00:10:50,880 --> 00:10:52,500
pasaulinį kintamąjį šaknis.

208
00:10:52,500 --> 00:10:56,190
Dabar šaknis bus mazgas *.

209
00:10:56,190 --> 00:10:59,760
Tai mūsų TRIE viršų, kad mes
bus iteravimu per.

210
00:10:59,760 --> 00:11:02,660
Taigi pirmas dalykas, kad mes ketiname
nori padaryti, tai skirti

211
00:11:02,660 --> 00:11:04,140
atminties mūsų šaknis.

212
00:11:04,140 --> 00:11:07,980
Atkreipkite dėmesį, kad mes naudojame calloc
funkcija, kuri yra iš esmės tas pats

213
00:11:07,980 --> 00:11:11,500
kaip malloc funkcijos, išskyrus tai
garantuoja, kad grįžti kažką, kad yra

214
00:11:11,500 --> 00:11:13,180
visiškai nulis iš.

215
00:11:13,180 --> 00:11:17,290
Taigi, jei mes naudojome malloc, mums reikia
eiti per visus iš rodyklės mūsų

216
00:11:17,290 --> 00:11:20,160
mazgas, ir įsitikinkite, kad
jie visi null.

217
00:11:20,160 --> 00:11:22,710
Taigi calloc bus tai padaryti už mus.

218
00:11:22,710 --> 00:11:26,330
>> Dabar kaip malloc, mes turime padaryti
įsitikinkite, kad paskirstymas iš tikrųjų buvo

219
00:11:26,330 --> 00:11:27,520
sėkmingas.

220
00:11:27,520 --> 00:11:29,990
Jei tai grąžinami null, tada mes
reikia uždaryti arba žodynas

221
00:11:29,990 --> 00:11:32,100
failą ir return false.

222
00:11:32,100 --> 00:11:36,835
Taigi, darant prielaidą, kad paskirstymas buvo
sėkmingas, mes ketiname naudoti mazgas *

223
00:11:36,835 --> 00:11:40,270
žymeklį pakartoti mūsų TRIE.

224
00:11:40,270 --> 00:11:43,890
Taigi mūsų šaknys niekada pakeisti,
bet mes ketiname naudoti žymeklį į

225
00:11:43,890 --> 00:11:47,875
faktiškai eiti iš mazgo į mazgą.

226
00:11:47,875 --> 00:11:50,940
>> Taigi, tai už linijos mes skaityti
per žodyno failą.

227
00:11:50,940 --> 00:11:53,670
Ir mes naudojame fgetc.

228
00:11:53,670 --> 00:11:56,290
Fgetc ketina patraukti vieną
simbolį iš failo.

229
00:11:56,290 --> 00:11:59,370
Mes ketiname tęsti greiferiniai
ženklai, o mes nepasiekia

230
00:11:59,370 --> 00:12:01,570
failo pabaiga.

231
00:12:01,570 --> 00:12:03,480
>> Yra du atvejai, turime dirbti.

232
00:12:03,480 --> 00:12:06,610
Pirma, jei simbolis
nebuvo nauja linija.

233
00:12:06,610 --> 00:12:10,450
Taigi mes žinome, jeigu tai buvo nauja eilutė, tada
mes ruošiamės pereiti į naują žodį.

234
00:12:10,450 --> 00:12:15,240
Tačiau darant prielaidą, kad tai buvo ne nauja eilutė, tada
čia mes norime išsiaiškinti,

235
00:12:15,240 --> 00:12:18,380
rodiklis mes ketiname indeksą į
į vaikų matrica,

236
00:12:18,380 --> 00:12:19,810
mes pažvelgė anksčiau.

237
00:12:19,810 --> 00:12:23,880
>> Taigi, kaip ir minėjau anksčiau, mes turime
Ypatingas atvejis kabutes.

238
00:12:23,880 --> 00:12:26,220
Atkreipkite dėmesį, mes naudojame trijų komponentų
operatorius čia.

239
00:12:26,220 --> 00:12:29,580
Taigi, mes ketiname skaityti tai kaip, jei
simbolių skaitome buvo

240
00:12:29,580 --> 00:12:35,330
Apostrofa, tada mes ketiname nustatyti
puslapis = "ALPHABET" -1, kuris bus

241
00:12:35,330 --> 00:12:37,680
būti 26 indeksas.

242
00:12:37,680 --> 00:12:41,130
>> Kitur, jei tai buvo ne Apostrofa, yra
mes ketiname sukurti indeksą

243
00:12:41,130 --> 00:12:43,760
lygi c -.

244
00:12:43,760 --> 00:12:49,030
Taigi nepamirškite atgal nuo ankstesnio p rinkinių,
c - ketina duoti mums

245
00:12:49,030 --> 00:12:53,410
Abėcėlinis pozicija C. Taigi, jei
C raidė, tai bus

246
00:12:53,410 --> 00:12:54,700
mums nulinį indeksą.

247
00:12:54,700 --> 00:12:58,120
Dėl raide B, jis duos
mums indeksas 1, ir pan.

248
00:12:58,120 --> 00:13:03,010
>> Taigi, tai suteikia mums rodyklę į
vaikai masyvas, kad mes norime.

249
00:13:03,010 --> 00:13:08,890
Dabar, jei šis rodiklis šiuo metu yra niekinis ir
vaikai, tai reiškia, kad mazgas

250
00:13:08,890 --> 00:13:11,830
šiuo metu nėra
iš to kelio.

251
00:13:11,830 --> 00:13:15,160
Taigi turime skirti
tuo keliu mazgas.

252
00:13:15,160 --> 00:13:16,550
Štai ką mes čia darome.

253
00:13:16,550 --> 00:13:20,690
>> Taigi, mes ketiname vėl naudoti calloc
funkciją, todėl, kad mes neturime

254
00:13:20,690 --> 00:13:22,880
nulis iš visų patarimų.

255
00:13:22,880 --> 00:13:27,240
Ir mes vėl reikia patikrinti
kad calloc nepamiršo.

256
00:13:27,240 --> 00:13:30,700
Jei calloc dar nepavyksta, tada mes turime
iškrauti viską, užmerkti

257
00:13:30,700 --> 00:13:32,820
žodyną, ir return false.

258
00:13:32,820 --> 00:13:40,050
Taigi, darant prielaidą, kad jis nepavyktų, tada
tai sukurs naują vaiką mums.

259
00:13:40,050 --> 00:13:41,930
Ir tada mes galėsime eiti į tą vaiką.

260
00:13:41,930 --> 00:13:44,960
Mūsų žymeklis bus pakartoti
iki to vaiko.

261
00:13:44,960 --> 00:13:49,330
>> Dabar, jei tai buvo ne null prasideda,
tada žymeklį galite tiesiog kartoti

262
00:13:49,330 --> 00:13:52,590
žemyn į tą vaiką faktiškai
turintys skirti nieko.

263
00:13:52,590 --> 00:13:56,730
Tai atvejis, kai mes pirmą kartą atsitiko
skirti žodį "katė". Ir

264
00:13:56,730 --> 00:14:00,330
tai reiškia, kad, kai mes einame skirti
"Katastrofa", mums nereikia kurti

265
00:14:00,330 --> 00:14:01,680
mazgai C-A-T dar kartą.

266
00:14:01,680 --> 00:14:04,830
Jie jau egzistuoja.

267
00:14:04,830 --> 00:14:06,080
>> Kas tai yra dar?

268
00:14:06,080 --> 00:14:10,480
Tai būklė, kai c buvo
Backslash n, kur c buvo nauja linija.

269
00:14:10,480 --> 00:14:13,710
Tai reiškia, kad mes sėkmingai
baigė žodį.

270
00:14:13,710 --> 00:14:16,860
Dabar, ką mes norime daryti, kai mes
sėkmingai baigė žodį?

271
00:14:16,860 --> 00:14:21,100
Mes ketiname naudoti šį žodį lauką
viduje mūsų struct mazgas.

272
00:14:21,100 --> 00:14:23,390
Mes norime nustatyti, kad būtų tiesa.

273
00:14:23,390 --> 00:14:27,150
Taigi, kad rodo, kad šis mazgas
rodo sėkmingas

274
00:14:27,150 --> 00:14:29,250
žodis, tikrasis žodis.

275
00:14:29,250 --> 00:14:30,940
>> Dabar nustatyta, kad "true".

276
00:14:30,940 --> 00:14:35,150
Mes norime, kad naujo mūsų žymeklį į tašką
į TRIE pradžioje dar kartą.

277
00:14:35,150 --> 00:14:40,160
Ir, pagaliau, prieaugio mūsų žodyną
dydis, nes mes radome kitą darbą.

278
00:14:40,160 --> 00:14:43,230
Taigi, mes ketiname toliau daryti, kad
skaityti pobūdį, charakterį,

279
00:14:43,230 --> 00:14:49,150
statant naujus mazgus mūsų TRIE ir
kiekvieno žodžio žodyne, kol

280
00:14:49,150 --> 00:14:54,020
mes pagaliau pasieks C! = EOF, kurioje
atveju mes išeiti iš failo.

281
00:14:54,020 --> 00:14:57,050
>> Dabar yra du atvejai, dėl kurių
kurios mes galime nukentėjo EOF.

282
00:14:57,050 --> 00:15:00,980
Pirma, jei ten buvo klaida
skaitant iš failo.

283
00:15:00,980 --> 00:15:03,470
Taigi, jei ten buvo klaida, mes
reikia padaryti tipiškas.

284
00:15:03,470 --> 00:15:06,460
Iškrauti viską, netoli
failas, return false.

285
00:15:06,460 --> 00:15:09,810
Darant prielaidą, kad nebuvo klaida, kad
tiesiog reiškia, kad mes iš tikrųjų pateko į pabaigą

286
00:15:09,810 --> 00:15:13,750
failas, tokiu atveju, mes uždaryti
failą ir grąžina true, nes mes

287
00:15:13,750 --> 00:15:17,330
sėkmingai įkeltas žodynas
į mūsų TRIE.

288
00:15:17,330 --> 00:15:20,170
>> Taigi dabar galime patikrinti patikrinimą.

289
00:15:20,170 --> 00:15:25,156
Pažvelgus žymės funkcija, matome
kad patikrinimas vyksta grįžti bool.

290
00:15:25,156 --> 00:15:29,680
Ji grąžina true, jei šis žodis, kad tai
bus perduotas yra mūsų TRIE.

291
00:15:29,680 --> 00:15:32,110
Ji grąžina false kitaip.

292
00:15:32,110 --> 00:15:36,050
Taigi, kaip jūs nustatyti, ar
šis žodis yra mūsų TRIE?

293
00:15:36,050 --> 00:15:40,190
>> Čia mes matome, kad, kaip ir anksčiau,
mes ketiname naudoti žymeklį pakartoti

294
00:15:40,190 --> 00:15:41,970
per mūsų TRIE.

295
00:15:41,970 --> 00:15:46,600
Dabar čia mes ketiname pakartoti
per visą mūsų žodį.

296
00:15:46,600 --> 00:15:50,620
Taigi Iteracja virš žodžio mes esame praeities,
mes ketiname nustatyti

297
00:15:50,620 --> 00:15:56,400
rodyklė į vaikų matrica,
atitinka žodžio kronšteino I. Taigi tai

298
00:15:56,400 --> 00:15:59,670
ketina atrodo kaip
apkrova, kur, jei žodis [i]

299
00:15:59,670 --> 00:16:03,310
yra Apostrofa, tada mes norime
naudoti indeksas "Alfabetas" - 1.

300
00:16:03,310 --> 00:16:05,350
Nes mes nustatėme, kad šis
kur mes ketiname saugoti

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

302
00:16:07,100 --> 00:16:11,780
>> Dar mes ketiname naudoti dvi mažesnes žodį
laikiklis I. Taigi nepamirškite, kad žodis gali

303
00:16:11,780 --> 00:16:13,920
turi savavališkai kapitalizaciją.

304
00:16:13,920 --> 00:16:17,540
Ir taip mes norime įsitikinti, kad mes
naudojant mažąją versiją dalykų.

305
00:16:17,540 --> 00:16:21,920
Ir tada atimkite nuo "a" iki vieno karto
vėl suteikti mums abėcėlinis

306
00:16:21,920 --> 00:16:23,880
pozicija šiuo simboliu.

307
00:16:23,880 --> 00:16:27,680
Taigi, tai bus mūsų puslapis
į vaikų masyvo.

308
00:16:27,680 --> 00:16:32,420
>> Ir dabar, jei tai puslapis į vaikų
masyvas yra tuščias, tai reiškia, kad mes

309
00:16:32,420 --> 00:16:34,990
nebegali Iteracja
žemyn mūsų TRIE.

310
00:16:34,990 --> 00:16:38,870
Jei tai toks atvejis, šis žodis negali
galbūt bus mūsų TRIE.

311
00:16:38,870 --> 00:16:42,340
Nes jei taip būtų, kad būtų
tai ten bus kelias

312
00:16:42,340 --> 00:16:43,510
žemyn į tą žodį.

313
00:16:43,510 --> 00:16:45,290
Ir jūs niekada susidurti null.

314
00:16:45,290 --> 00:16:47,850
Taigi iškyla null mes return false.

315
00:16:47,850 --> 00:16:49,840
Žodžio nėra žodyne.

316
00:16:49,840 --> 00:16:53,660
Jei tai buvo ne nulis, tada mes
ketina toliau Iteracja.

317
00:16:53,660 --> 00:16:57,220
>> Taigi, mes ketiname ten žymeklį
atkreipti dėmesį į tai ypač

318
00:16:57,220 --> 00:16:59,760
mazgas tuo indeksu.

319
00:16:59,760 --> 00:17:03,150
Mes nuolat tai daryti, kad per
Visas žodis, darant prielaidą,

320
00:17:03,150 --> 00:17:03,950
mes niekada hit null.

321
00:17:03,950 --> 00:17:07,220
Tai reiškia, kad mes galime gauti per
Visas žodis ir rasite

322
00:17:07,220 --> 00:17:08,920
mūsų bandymas mazgas.

323
00:17:08,920 --> 00:17:10,770
Bet mes ne visai padaryta dar.

324
00:17:10,770 --> 00:17:12,290
>> Mes nenorime tiesiog grąžina true.

325
00:17:12,290 --> 00:17:14,770
Mes norime grįžti žymeklį> žodį.

326
00:17:14,770 --> 00:17:18,980
Nuo prisiminti vėl yra "katė" nėra
mūsų žodyną, ir "katastrofa"

327
00:17:18,980 --> 00:17:22,935
yra, tada mes sėkmingai mes
per žodis "katė". Bet žymeklis

328
00:17:22,935 --> 00:17:25,760
Žodis bus klaidingas, o ne tiesa.

329
00:17:25,760 --> 00:17:30,930
Taigi, mes grįžtame žymeklio žodį rodo
ar šis mazgas yra iš tikrųjų žodis.

330
00:17:30,930 --> 00:17:32,470
Štai ir viskas registruotis.

331
00:17:32,470 --> 00:17:34,250
>> Taigi galime patikrinti dydį.

332
00:17:34,250 --> 00:17:37,350
Taigi dydis bus gana lengva
nes prisiminti, kroviniu, mes

333
00:17:37,350 --> 00:17:41,430
incrementing žodyno dydį
kiekvienas žodis, kad mes susiduriame.

334
00:17:41,430 --> 00:17:45,350
Taigi dydis yra tik ketina
grįžti žodyno dydį.

335
00:17:45,350 --> 00:17:47,390
Štai ir viskas.

336
00:17:47,390 --> 00:17:50,590
>> Taigi galiausiai mes iškrauti.

337
00:17:50,590 --> 00:17:55,100
Taigi, iškrauti, mes ketiname naudoti
grįžtamojo funkcija iš tiesų visi

338
00:17:55,100 --> 00:17:56,530
iš mums darbo.

339
00:17:56,530 --> 00:17:59,340
Taigi, mūsų funkcija ketina
būti paprašyta unloader.

340
00:17:59,340 --> 00:18:01,650
Kas yra Kėlimo ketinate daryti?

341
00:18:01,650 --> 00:18:06,580
Čia mes matome, kad Kėlimo ketina
kartoti per visas vaikams

342
00:18:06,580 --> 00:18:08,410
tai ypač mazgas.

343
00:18:08,410 --> 00:18:11,750
Ir jei vaikas mazgas nėra
null, tada mes ketiname

344
00:18:11,750 --> 00:18:13,730
iškrauti vaikų mazgas.

345
00:18:13,730 --> 00:18:18,010
>> Taigi tai jums rekursyviai iškrauti
visus mūsų vaikus.

346
00:18:18,010 --> 00:18:21,080
Kai mes esame tikri, kad visi mūsų vaikai
buvo iškrauti, tada mes

347
00:18:21,080 --> 00:18:25,210
gali išsivaduoti, todėl
iškrauti save.

348
00:18:25,210 --> 00:18:29,460
Ši funkcija veiks rekursyviai
iškrauti visą TRIE.

349
00:18:29,460 --> 00:18:32,850
Ir tada, kai tai daroma,
mes galime tiesiog grąžina true.

350
00:18:32,850 --> 00:18:34,210
Iškelti negali nepavykti.

351
00:18:34,210 --> 00:18:35,710
Mes tiesiog išlaisvina dalykų.

352
00:18:35,710 --> 00:18:38,870
Taigi, kai mes baigsime išlaisvinant
viskas, grąžina true.

353
00:18:38,870 --> 00:18:40,320
Štai ir viskas.

354
00:18:40,320 --> 00:18:41,080
Mano vardas yra Rob.

355
00:18:41,080 --> 00:18:42,426
Ir tai buvo Speller.

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