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

2
00:00:00,530 --> 00:00:03,070
>> SPEAKER 1: Dosim
Šis risinājums mēģināt.

3
00:00:03,070 --> 00:00:07,130
Tātad, pieņemsim apskatīt to, kas mūsu
Struktūrai mezgls izskatīsies.

4
00:00:07,130 --> 00:00:11,040
Šeit mēs redzam, mēs esam nāksies
Bool Word un Struct mezglu zvaigzne

5
00:00:11,040 --> 00:00:12,990
Bērni Bracket alfabētu.

6
00:00:12,990 --> 00:00:18,720
Tātad, pirmā lieta, jūs varētu būt jautājums,
kāpēc alfabēts hash definēta kā 27?

7
00:00:18,720 --> 00:00:22,540
Nu, atcerieties, ka mēs ejam uz nepieciešamību
kas apstrādes apostrofu, lai

8
00:00:22,540 --> 00:00:25,610
, kas būs nedaudz īpašs
lieta visā šajā programmā.

9
00:00:25,610 --> 00:00:28,780
>> Labi, tagad atceros, kā
Trie faktiski darbojas.

10
00:00:28,780 --> 00:00:33,420
Pieņemsim, ka mēs esam indeksēšanas vārdu kaķi,
tad no saknes mūsu Trie,

11
00:00:33,420 --> 00:00:36,670
mēs ejam apskatīt Bērnu
masīvs, un mēs ejam apskatīt

12
00:00:36,670 --> 00:00:42,250
indekss, kas atbilst vēstules
C. Lai būtu indekss divi.

13
00:00:42,250 --> 00:00:46,400
Tātad, ņemot vērā, ka tas dos mums
jaunu mezglu, un tad mēs

14
00:00:46,400 --> 00:00:47,880
strādā no šī mezgla.

15
00:00:47,880 --> 00:00:51,830
>> Tāpēc, ka mezglā, mēs atkal esam
skatīsies uz Bērnu masīvs,

16
00:00:51,830 --> 00:00:56,170
un mēs ejam apskatīt indeksu nulles
lai tā atbilstu A kaķu.

17
00:00:56,170 --> 00:01:01,240
Tātad, tad mēs ejam, lai dotos uz šo mezglu,
un ņemot vērā, ka mezglā, mēs ejam

18
00:01:01,240 --> 00:01:05,170
aplūkot indekss, kas atbilst
ar T. un pārvietojas uz šo mezglu,

19
00:01:05,170 --> 00:01:09,590
Visbeidzot, mēs esam pilnīgi izskatījās
caur mūsu vārdu Cat, un tagad Bool

20
00:01:09,590 --> 00:01:15,020
Vārds ir paredzēts, lai norādītu, vai
tas dots vārds ir faktiski vārdu.

21
00:01:15,020 --> 00:01:17,530
>> Tātad, kāpēc mums ir nepieciešams, ka īpaša gadījumā?

22
00:01:17,530 --> 00:01:21,680
Nu, ko tad, ja vārds katastrofa
ir mūsu vārdnīcā, bet

23
00:01:21,680 --> 00:01:24,120
vārds kaķis ir ne?

24
00:01:24,120 --> 00:01:29,030
Tāpēc vēlas redzēt, ja vārds kaķis
mūsu vārdnīcā, mēs ejam

25
00:01:29,030 --> 00:01:34,880
veiksmīgi meklēt, izmantojot indeksu
C-T un sasniegt mezglu, bet tas ir

26
00:01:34,880 --> 00:01:39,760
tikai tāpēc, ka katastrofa notika
izveidot mezglu ceļā no C-A-T all

27
00:01:39,760 --> 00:01:41,250
veids, beigās vārdu.

28
00:01:41,250 --> 00:01:46,520
Tāpēc Bool Word lieto norādīt, vai
šī konkrētā vietā faktiski

29
00:01:46,520 --> 00:01:48,370
norāda vārdu.

30
00:01:48,370 --> 00:01:52,920
>> Labi, tāpēc tagad, ka mēs zinām, kas
Trie gatavojas izskatās, aplūkosim

31
00:01:52,920 --> 00:01:54,800
pie slodzes funkciju.

32
00:01:54,800 --> 00:01:58,670
Tāpēc Slodze gatavojas atgriezties bool
par to, vai mēs veiksmīgi vai

33
00:01:58,670 --> 00:02:03,020
neveiksmīgi piekrauts vārdnīcu un
tas būs vārdnīca

34
00:02:03,020 --> 00:02:04,520
ka mēs gribam, lai slodze.

35
00:02:04,520 --> 00:02:08,310
Tātad pirmā lieta, ko mēs gatavojamies darīt, ir atvērts
līdz šim vārdnīcā lasījumā.

36
00:02:08,310 --> 00:02:12,060
Mums ir jāpārliecinās, mums nav neizdoties,
tāpēc, ja vārdnīcā nav

37
00:02:12,060 --> 00:02:15,280
veiksmīgi atvērts, tas atgriezīsies
Nē, tādā gadījumā mēs spēsim

38
00:02:15,280 --> 00:02:16,340
atgriešanās False.

39
00:02:16,340 --> 00:02:21,290
Bet, pieņemot, ka tā veiksmīgi
atvērts, tad mēs faktiski var izlasīt

40
00:02:21,290 --> 00:02:22,310
izmantojot vārdnīcu.

41
00:02:22,310 --> 00:02:24,940
>> Tātad pirmā lieta, ko mēs gatavojamies
vēlaties darīt, ir, mums ir šis

42
00:02:24,940 --> 00:02:26,560
globālo mainīgo saknes.

43
00:02:26,560 --> 00:02:30,250
Tagad, saknes būs mezglā zvaigzne.

44
00:02:30,250 --> 00:02:33,830
Tā ir top mūsu Trie, ka mēs esam
būs atkārtojot cauri.

45
00:02:33,830 --> 00:02:38,200
Tātad pirmā lieta, ko mēs esam gatavojas vēlaties
darīt, ir piešķirt atmiņu mūsu saknes.

46
00:02:38,200 --> 00:02:42,040
>> Ievērojiet, ka mēs esam, izmantojot Calloc
funkcija, kas būtībā ir tas pats

47
00:02:42,040 --> 00:02:45,560
jo malloc funkciju, izņemot tā
garantēta, lai atgrieztos kaut ko, kas ir

48
00:02:45,560 --> 00:02:47,240
pilnīgi nulli out.

49
00:02:47,240 --> 00:02:51,350
Tātad, ja mēs izmantojām malloc, mums būtu nepieciešams, lai
iet cauri visiem norādes mūsu

50
00:02:51,350 --> 00:02:54,220
mezglu un pārliecinieties, ka
viņi visi null.

51
00:02:54,220 --> 00:02:56,780
Tāpēc Calloc būs darīt, ka mums.

52
00:02:56,780 --> 00:03:00,390
>> Tagad, tāpat kā malloc, mums ir nepieciešams veikt
pārliecināts, ka sadalījums ir faktiski

53
00:03:00,390 --> 00:03:01,580
veiksmīga.

54
00:03:01,580 --> 00:03:04,060
Ja tas atgriezās null, tad mēs
nepieciešams slēgt mūsu vārdnīca

55
00:03:04,060 --> 00:03:06,170
failu un atgriešanās False.

56
00:03:06,170 --> 00:03:11,040
Tātad, pieņemot, ka piešķiršanu tika
veiksmīga, mēs ejam, lai izmantotu mezglu

57
00:03:11,040 --> 00:03:14,340
star kursoru atkārtot
caur mūsu Trie.

58
00:03:14,340 --> 00:03:17,950
Tātad mūsu saknes nekad mainīsies,
bet mēs esam gatavojas izmantot kursoru

59
00:03:17,950 --> 00:03:20,770
tiešām iet no mezgla uz mezglu.

60
00:03:20,770 --> 00:03:25,000
>> Labi, tāpēc šis cilpas, mēs esam
iepazīšanās ar vārdnīcas failu,

61
00:03:25,000 --> 00:03:26,965
un mēs esam izmantojot pie fgetc.

62
00:03:26,965 --> 00:03:30,360
Tāpēc fgetc gatavojas sagrābt vienotu
rakstzīmi no lietas materiāliem.

63
00:03:30,360 --> 00:03:33,430
Mēs turpināsim satveršanas
rakstzīmes, kamēr mēs nenonāk

64
00:03:33,430 --> 00:03:37,540
beigām failu, tāpēc ir
abas lietas mums ir nepieciešams rīkoties.

65
00:03:37,540 --> 00:03:41,640
Pirmais, ja raksturs nebija
Jaunā līnija, tāpēc mēs zinām, ja tas bija jauns

66
00:03:41,640 --> 00:03:44,480
līniju, tad mēs esam par to, lai
pāriet uz jaunu vārdu.

67
00:03:44,480 --> 00:03:49,300
Bet pieņemot, ka tas nebija jaunu līniju, tad
šeit, mēs gribam, lai noskaidrotu

68
00:03:49,300 --> 00:03:52,440
indekss mēs ejam indeksēt
ar bērniem masīvā, ka

69
00:03:52,440 --> 00:03:53,890
mēs paskatījās agrāk.

70
00:03:53,890 --> 00:03:57,950
>> Tā kā es teicu iepriekš, mums ir nepieciešams
Īpašs gadījums Apostrofs.

71
00:03:57,950 --> 00:04:01,040
Ievērojiet, mēs izmantot trīskāršo operators
šeit, tāpēc mēs ejam, lai lasītu

72
00:04:01,040 --> 00:04:05,500
Tas it kā varonis lasām bija
Apostrofs, tad mēs ejam uz

73
00:04:05,500 --> 00:04:11,740
iestatīts indekss ir vienāds alfabēts mīnusu
1, kas būs rādītājs 26.

74
00:04:11,740 --> 00:04:15,190
Cits, ja tas nav Apostrofs,
tad mēs ejam, lai uzstādītu indeksu

75
00:04:15,190 --> 00:04:17,820
vienāds ar c mīnus.

76
00:04:17,820 --> 00:04:23,090
Līdz ar to atcerēties atpakaļ no iepriekšējiem p komplekti,
c mīnus gatavojas sniegt mums

77
00:04:23,090 --> 00:04:27,470
alfabēta stāvokli c, tāpēc, ja
c ir burts, tas

78
00:04:27,470 --> 00:04:28,770
dod mums indekss nulle.

79
00:04:28,770 --> 00:04:32,180
Par vēstules B, tas dotu
mums indekss 1, un tā tālāk.

80
00:04:32,180 --> 00:04:37,070
>> Tāpēc tas dod mums indekss spēkā
Bērni masīvs, ko mēs gribam.

81
00:04:37,070 --> 00:04:42,540
Tagad, ja šis rādītājs pašlaik Null
Bērni masīvs, tas nozīmē, ka

82
00:04:42,540 --> 00:04:47,470
mezglu pašreiz nav no
ka ceļš, tāpēc mums ir nepieciešams piešķirt

83
00:04:47,470 --> 00:04:49,220
mezglu, lai šajā ceļā.

84
00:04:49,220 --> 00:04:50,610
Tas ir tas, ko mēs darām šeit.

85
00:04:50,610 --> 00:04:54,650
Tāpēc mēs ejam atkal izmantojiet Calloc
funkciju, tā, ka mums nav

86
00:04:54,650 --> 00:05:00,130
līdz nulle visas norādes, un mēs,
atkal, ir nepieciešams, lai pārbaudītu, vai Calloc

87
00:05:00,130 --> 00:05:01,300
nav neizdoties.

88
00:05:01,300 --> 00:05:04,760
Ja Calloc tomēr neizdodas, tad mums
izkraut viss, aizvērt

89
00:05:04,760 --> 00:05:06,880
vārdnīcu, un atgriešanās False.

90
00:05:06,880 --> 00:05:14,110
>> Tātad, pieņemot, ka tas nav neizdoties, tad
Tas radīs jaunu bērnu mums,

91
00:05:14,110 --> 00:05:16,000
un tad mēs dosimies uz šo bērnu.

92
00:05:16,000 --> 00:05:19,030
Mūsu kursors atkārtot
uz leju, lai šo bērnu.

93
00:05:19,030 --> 00:05:23,390
Tagad, ja tas nav null, lai sāktu ar,
tad kursors var tikai atkārtot

94
00:05:23,390 --> 00:05:26,650
uz leju, lai šo bērnu, bet faktiski
kam piešķirt neko.

95
00:05:26,650 --> 00:05:30,790
Šis ir gadījums, kad mēs pirmo reizi notika
piešķirt vārdu kaķis, un

96
00:05:30,790 --> 00:05:34,390
tas nozīmē, ka tad, kad mēs ejam, lai sadalītu
katastrofa, mums nav nepieciešams, lai izveidotu

97
00:05:34,390 --> 00:05:35,720
mezglu C-A-T vēlreiz.

98
00:05:35,720 --> 00:05:37,620
Viņi jau pastāv.

99
00:05:37,620 --> 00:05:40,140
>> Labi, lai to, kas ir šis cits?

100
00:05:40,140 --> 00:05:44,600
Tas ir stāvoklis, kurā c ir
slīpsvītru n, kur c ir jauna līnija.

101
00:05:44,600 --> 00:05:47,780
Tas nozīmē, ka ir veiksmīgi
pabeidzis vārdu.

102
00:05:47,780 --> 00:05:51,020
Tagad, ko mēs vēlamies darīt, kad mēs
sekmīgi pabeigta vārdu?

103
00:05:51,020 --> 00:05:55,250
Mēs ejam, lai izmantotu šo vārdu lauku
iekšpusē mūsu struktūrai mezglā.

104
00:05:55,250 --> 00:06:00,570
>> Mēs gribam, lai noteiktu, ka uz True, lai
norāda, ka šis mezgls norāda

105
00:06:00,570 --> 00:06:03,320
veiksmīga vārdu faktisko vārdu.

106
00:06:03,320 --> 00:06:05,050
Tagad, noteikti, ka, lai True.

107
00:06:05,050 --> 00:06:09,210
Mēs vēlamies, lai atjaunotu savu kursoru uz punktu
līdz sākumā Trie atkal.

108
00:06:09,210 --> 00:06:13,510
Un visbeidzot, solis mūsu vārdnīca
izmērs, jo mēs atradām citu vārdu.

109
00:06:13,510 --> 00:06:16,450
>> Labi, tāpēc mēs ejam, lai saglabātu darot
ka, lasot raksturs, ko

110
00:06:16,450 --> 00:06:21,960
raksturs, būvējot jaunas mezglu
mūsu Trie un katram vārdu

111
00:06:21,960 --> 00:06:26,810
vārdnīcu, kamēr mēs beidzot sasniedz c
vienāds EOF, tādā gadījumā mēs laužam

112
00:06:26,810 --> 00:06:28,100
no lietas materiāliem.

113
00:06:28,100 --> 00:06:31,110
Tagad ar divi gadījumi
kas mēs varētu būt hit EOF.

114
00:06:31,110 --> 00:06:35,680
Pirmais ir, ja tur bija kļūda
lasot no lietas materiāliem, tāpēc, ja tur bija

115
00:06:35,680 --> 00:06:39,280
kļūda, kas mums jādara, tipisks
izkraut viss, slēgt datni,

116
00:06:39,280 --> 00:06:40,520
atgriešanās False.

117
00:06:40,520 --> 00:06:43,870
Pieņemot, ka tur nebija kļūda, ka
tikai nozīmē, ka mēs faktiski hit beigām

118
00:06:43,870 --> 00:06:47,820
failu, un tādā gadījumā, mēs cieši
failu un atgriezties taisnība, jo mēs

119
00:06:47,820 --> 00:06:51,010
veiksmīgi ielādēta vārdnīcu
mūsu Trie.

120
00:06:51,010 --> 00:06:54,240
>> Labi, tāpēc tagad pieņemsim
izbraukšana pārbaude.

121
00:06:54,240 --> 00:06:58,780
Raugoties uz pārbaudes funkciju, mēs redzam,
ka pārbaude ir gatavojas atgriezties bool.

122
00:06:58,780 --> 00:07:03,740
Tā atgriež True, ja šis vārds, ka tas ir
tiek pieņemts, tur ir mūsu Trie.

123
00:07:03,740 --> 00:07:06,170
Tā atgriež False citādi.

124
00:07:06,170 --> 00:07:10,110
>> Tātad, kā mēs gatavojamies, lai noteiktu, vai
šis vārds ir mūsu Trie?

125
00:07:10,110 --> 00:07:14,270
Mēs redzam šeit, ka, tāpat kā iepriekš,
mēs gatavojamies izmantot kursoru atkārtot

126
00:07:14,270 --> 00:07:16,010
caur mūsu Trie.

127
00:07:16,010 --> 00:07:20,650
Tagad, šeit mēs esam gatavojas atkārtot
pār mūsu visu vārdu.

128
00:07:20,650 --> 00:07:24,680
Tātad, atkārtojot visā vārdu mēs esam
pagājis, mēs ejam, lai noteiktu

129
00:07:24,680 --> 00:07:29,280
indeksu uz Bērnu masīvu, kas
atbilst vārdu stiprinājuma i.

130
00:07:29,280 --> 00:07:34,150
Tāpēc tas ir gatavojas izskatās tieši tāpat kā
Slodze, kur, ja vārds kronšteins i ir

131
00:07:34,150 --> 00:07:38,110
Apostrofs, tad mēs vēlamies izmantot indeksu
alfabēts mīnus 1, jo mēs noteicām

132
00:07:38,110 --> 00:07:41,160
tas ir, ja mēs ejam
uzglabāt apostrofiem.

133
00:07:41,160 --> 00:07:44,440
>> Vēl mēs spēsim izmantot tolower
Vārds kronšteins i.

134
00:07:44,440 --> 00:07:48,270
Līdz ar to atcerēties, ka vārds var būt patvaļīgs
kapitalizācija, un tāpēc mēs

135
00:07:48,270 --> 00:07:51,590
vēlaties pārliecināties, ka mēs izmantojam
mazie versija lietām.

136
00:07:51,590 --> 00:07:55,300
Un tad atņemt no šī mazajiem
lai, atkal, dod mums

137
00:07:55,300 --> 00:07:57,940
alfabēta amats
par šo personāžu.

138
00:07:57,940 --> 00:08:01,740
Tā, ka būs mūsu indeksu
uz bērnu masīvs.

139
00:08:01,740 --> 00:08:06,480
>> Un tagad, ja šis rādītājs uz Bērnu
masīvs ir nulle, tas nozīmē, ka mēs

140
00:08:06,480 --> 00:08:09,050
vairs nevar turpināt, atkārtojot
leju mūsu Trie.

141
00:08:09,050 --> 00:08:13,320
Ja tas ir gadījumā, šis vārds nevar
iespējams, varētu būt mūsu Trie, jo, ja tā

142
00:08:13,320 --> 00:08:18,000
bija, tas nozīmētu, ka varētu būt
ceļš uz leju, lai šo vārdu, un jūs,

143
00:08:18,000 --> 00:08:19,350
nekad sastapties null.

144
00:08:19,350 --> 00:08:21,910
Tātad sastopas Null, mēs atgriežamies False.

145
00:08:21,910 --> 00:08:23,810
Vārda nav vārdnīcā.

146
00:08:23,810 --> 00:08:28,200
Ja tas nav null, tad mēs ejam
turpinās atkārtojot, tāpēc mēs ejam

147
00:08:28,200 --> 00:08:33,150
lai atjauninātu savu kursoru, lai norādītu, ka
īpaši mezglā šajā indeksā.

148
00:08:33,150 --> 00:08:36,659
>> Tāpēc mēs turpinām darām visu
visu vārdu.

149
00:08:36,659 --> 00:08:40,630
Pieņemot, ka mēs nekad hit nulle, tas nozīmē
mēs varējām dabūt cauri visam

150
00:08:40,630 --> 00:08:44,840
pasaulē un atrast mezglu mūsu Trie,
bet mēs neesam gluži izdarīts vēl.

151
00:08:44,840 --> 00:08:46,350
Mēs nevēlamies, lai tikai atgrieztos True.

152
00:08:46,350 --> 00:08:51,400
Mēs vēlamies, lai atgrieztos kursoru kļūdas vārdu
jo, atcerieties, atkal, ja kaķis nav

153
00:08:51,400 --> 00:08:55,140
mūsu vārdnīcu un katastrofa ir,
tad mēs veiksmīgi tikt cauri

154
00:08:55,140 --> 00:08:59,810
vārdu kaķis, bet kursors vārds
būs False un nav taisnība.

155
00:08:59,810 --> 00:09:04,990
Tāpēc mēs atgriežamies kursora vārdu, lai norādītu
vai šis mezgls ir patiesībā vārds,

156
00:09:04,990 --> 00:09:06,530
un tas arī viss par pārbaudi.

157
00:09:06,530 --> 00:09:08,310
>> Tāpēc pieņemsim izbraukšana izmērs.

158
00:09:08,310 --> 00:09:11,410
Tā lielums būs diezgan viegli
jo atceros, Load, mēs esam

159
00:09:11,410 --> 00:09:15,480
palielināšanai vārdnīca izmēru
katrs vārds, ko mēs saskaramies.

160
00:09:15,480 --> 00:09:20,820
Tā lielums ir tikai gatavojas atgriezties
vārdnīca izmēru, un tas arī viss.

161
00:09:20,820 --> 00:09:24,650
>> Labi, tāpēc visbeidzot, mēs esam izkraut.

162
00:09:24,650 --> 00:09:29,050
Tātad Izkraut, mēs ejam, lai izmantotu
rekursīvas funkcijas, lai faktiski darīt visu

163
00:09:29,050 --> 00:09:33,390
no darba mums, lai mūsu funkcija
būs saukt Atslodzes.

164
00:09:33,390 --> 00:09:35,830
Kas ir Atslodzes gatavojas darīt?

165
00:09:35,830 --> 00:09:40,640
Mēs redzam šeit, ka Atslodzes gatavojas
atkārtot pār visiem bērniem

166
00:09:40,640 --> 00:09:45,810
Tas īpaši mezglā, un, ja bērns
mezgls nav nulle, tad mēs ejam

167
00:09:45,810 --> 00:09:47,760
izkraut bērnu mezglu.

168
00:09:47,760 --> 00:09:52,070
>> Tātad šis būs rekursīvi
izkraut visas mūsu bērniem.

169
00:09:52,070 --> 00:09:55,140
Pēc tam, kad mēs esam pārliecināti, ka visi mūsu bērni
ir izkrautas, tad mēs

170
00:09:55,140 --> 00:09:58,830
var atbrīvot sevi, lai izkrautu ourself.

171
00:09:58,830 --> 00:10:04,550
Tāpēc tas rekursīvi izkraut
Visa Trie, un tad, kad tas ir

172
00:10:04,550 --> 00:10:06,910
izdarīts, mēs varam vienkārši atgriezties True.

173
00:10:06,910 --> 00:10:09,770
Izkraut nevar neizdoties, mēs esam
tikai atbrīvojot lietas.

174
00:10:09,770 --> 00:10:12,985
Tātad, kad mēs esam darījuši atbrīvojot
viss, atgriešanās True.

175
00:10:12,985 --> 00:10:14,380
Un tas arī viss.

176
00:10:14,380 --> 00:10:16,792
Mans vārds ir Rob, un šī
bija [dzirdams].

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