1
00:00:00,000 --> 00:00:12,350
>> [Redare a muzicii]

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

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

4
00:00:13,640 --> 00:00:16,210
Și să această soluție afară.

5
00:00:16,210 --> 00:00:20,070
Deci, aici am de gând să pună în aplicare
o masă generală.

6
00:00:20,070 --> 00:00:24,090
Vedem că nodul struct de nostru
masă este de gând să arate ca aceasta.

7
00:00:24,090 --> 00:00:28,710
Deci, o să aibă un cuvânt char
matrice de dimensiune lungime + 1.

8
00:00:28,710 --> 00:00:32,259
Nu uita de + 1, de la maxim
cuvânt în dicționar este de 45

9
00:00:32,259 --> 00:00:33,130
caractere.

10
00:00:33,130 --> 00:00:37,070
Și apoi vom avea nevoie de un plus
caracter de zero backslash.

11
00:00:37,070 --> 00:00:40,870
>> Și apoi hashtable noastră în fiecare
găleată se va stoca un

12
00:00:40,870 --> 00:00:42,320
Lista legate de noduri.

13
00:00:42,320 --> 00:00:44,420
Noi nu facem liniar sondare aici.

14
00:00:44,420 --> 00:00:48,430
Și astfel, în scopul de a lega la alta
Element în găleată, avem nevoie de un

15
00:00:48,430 --> 00:00:50,390
struct nod * viitor.

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

17
00:00:51,110 --> 00:00:53,090
Deci, asta e ceea ce un nod arata ca.

18
00:00:53,090 --> 00:00:56,180
>> Acum, aici este declarația
de hashtable noastre.

19
00:00:56,180 --> 00:00:59,640
Se va avea 16,834 găleți.

20
00:00:59,640 --> 00:01:01,910
Dar acest număr nu contează cu adevărat.

21
00:01:01,910 --> 00:01:05,450
Și, în sfârșit, vom avea
Dimensiunea globală hashtable variabilă, care

22
00:01:05,450 --> 00:01:07,000
va incepe la zero.

23
00:01:07,000 --> 00:01:10,760
Și se va urmări modul în care
multe cuvinte sunt în dicționarul nostru.

24
00:01:10,760 --> 00:01:13,710
>> Deci, haideți să aruncăm o privire la sarcină.

25
00:01:13,710 --> 00:01:16,390
Observați că sarcina, returnează un bool.

26
00:01:16,390 --> 00:01:20,530
Te vei întoarce true dacă a fost cu succes
încărcate, și false în caz contrar.

27
00:01:20,530 --> 00:01:23,990
Și este nevoie de un const char * dicționar,
care este dicționarul

28
00:01:23,990 --> 00:01:25,280
pe care ne-o dorim pentru a deschide.

29
00:01:25,280 --> 00:01:27,170
Deci, asta e primul lucru
am de gând să faci.

30
00:01:27,170 --> 00:01:29,500
>> Vom fopen
dicționar pentru lectură.

31
00:01:29,500 --> 00:01:31,680
Și vom avea de a face
sigur că a reușit.

32
00:01:31,680 --> 00:01:35,920
Deci, în cazul în care sa întors NULL, atunci nu am
deschide cu succes în dicționar.

33
00:01:35,920 --> 00:01:37,440
Și avem nevoie pentru a reveni false.

34
00:01:37,440 --> 00:01:41,580
Dar presupunând că a făcut-o cu succes
deschis, apoi ne-o dorim pentru a citi

35
00:01:41,580 --> 00:01:42,400
dicționar.

36
00:01:42,400 --> 00:01:46,450
Deci, ține looping până când vom găsi unele
motiv de a ieși din această buclă,

37
00:01:46,450 --> 00:01:47,570
pe care vom vedea.

38
00:01:47,570 --> 00:01:48,920
Deci, ține looping.

39
00:01:48,920 --> 00:01:51,780
>> Și acum vom
malloc un singur nod.

40
00:01:51,780 --> 00:01:54,020
Și, desigur, avem nevoie
la aer a verifica din nou.

41
00:01:54,020 --> 00:01:58,680
Deci, dacă mallocing nu a avut succes, atunci
ne-o dorim pentru a descărca orice nod pe care le

42
00:01:58,680 --> 00:02:02,590
sa întâmplat cu malloc înainte, închideți
dicționar și a reveni false.

43
00:02:02,590 --> 00:02:06,830
Dar ignorând că, ne-am presupunând
a reușit, atunci vrem sa folosim fscanf

44
00:02:06,830 --> 00:02:12,400
pentru a citi un singur cuvânt de la noastră
dictionar în nodul nostru.

45
00:02:12,400 --> 00:02:17,940
Deci, amintiți-vă că intrarea> cuvânt este char
tampon cuvânt de dimensiuni Lungime de + 1

46
00:02:17,940 --> 00:02:20,300
că vom stoca cuvântul inch

47
00:02:20,300 --> 00:02:25,070
>> Astfel fscanf este de gând să se întoarcă 1, atâta timp
așa cum a fost în măsură să succes

48
00:02:25,070 --> 00:02:26,750
citit un cuvânt de la dosar.

49
00:02:26,750 --> 00:02:30,460
În cazul în care fie o eroare se întâmplă, sau noi
ajunge la sfârșitul fișierului, se

50
00:02:30,460 --> 00:02:31,950
nu va reveni 1.

51
00:02:31,950 --> 00:02:35,180
În cazul în care aceasta nu se întoarce 1,
suntem în cele din urmă o să iasă din

52
00:02:35,180 --> 00:02:37,280
această buclă în timp.

53
00:02:37,280 --> 00:02:42,770
Deci, vom vedea că, odată ce avem succes
citit un cuvânt în

54
00:02:42,770 --> 00:02:48,270
intrare> cuvânt, apoi mergem la care
cuvânt utilizând funcția noastră hash.

55
00:02:48,270 --> 00:02:49,580
>> Să aruncăm o privire la
funcția de distribuire.

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

57
00:02:52,430 --> 00:02:55,610
Deci, nu aveți cu adevărat nevoie
să înțeleagă acest lucru.

58
00:02:55,610 --> 00:02:59,460
Și de fapt, doar ne-am scos acest hash
funcționeze de pe internet.

59
00:02:59,460 --> 00:03:04,010
Singurul lucru pe care trebuie să recunoască este
că acest lucru are un const char * cuvânt.

60
00:03:04,010 --> 00:03:08,960
Deci, se ia un șir ca intrare, și
revenind un int nesemnate ca ieșire.

61
00:03:08,960 --> 00:03:12,360
Deci, asta e tot o funcție hash este, este
ia într-o intrare și vă oferă o

62
00:03:12,360 --> 00:03:14,490
index în Hashtable.

63
00:03:14,490 --> 00:03:18,530
>> Observați că suntem moding de NUM_BUCKETS,
astfel ca valoarea returnată

64
00:03:18,530 --> 00:03:21,730
de fapt este un index în Hashtable
și nu indicele de dincolo de

65
00:03:21,730 --> 00:03:24,320
limitele de matrice.

66
00:03:24,320 --> 00:03:28,060
Deci, având în vedere că funcția, vom
hash cuvântul pe care am citit

67
00:03:28,060 --> 00:03:29,390
dicționar.

68
00:03:29,390 --> 00:03:31,700
Și apoi vom folosi
care hash pentru a insera

69
00:03:31,700 --> 00:03:33,750
intrarea în Hashtable.

70
00:03:33,750 --> 00:03:38,520
>> Hash acum hashtable este curentul
Lista legată în tabel.

71
00:03:38,520 --> 00:03:41,410
Și e foarte posibil
că e doar NULL.

72
00:03:41,410 --> 00:03:44,960
Vrem să inserați intrarea nostru de la
începând din această listă legat.

73
00:03:44,960 --> 00:03:48,600
Și astfel vom avea curent noastră
punct de intrare în ceea ce Hashtable

74
00:03:48,600 --> 00:03:50,380
subliniază în prezent la.

75
00:03:50,380 --> 00:03:53,310
Și apoi vom stoca,
în Hashtable la

76
00:03:53,310 --> 00:03:55,350
hash, intrarea curentă.

77
00:03:55,350 --> 00:03:59,320
Deci, aceste două linii se introduce cu succes
intrarea de la începutul

78
00:03:59,320 --> 00:04:02,260
Lista legat la acel index
în Hashtable.

79
00:04:02,260 --> 00:04:04,900
>> După ce am terminat cu asta, știm
că am găsit un alt cuvânt în

80
00:04:04,900 --> 00:04:07,790
dicționar, și ne-am incrementa din nou.

81
00:04:07,790 --> 00:04:13,960
Așa că am continuăm să facem asta până fscanf
a revenit în cele din urmă ceva non-1 la

82
00:04:13,960 --> 00:04:16,950
care punct amintiți-vă că
avem nevoie pentru intrare gratuită.

83
00:04:16,950 --> 00:04:19,459
Deci, aici am malloced o intrare.

84
00:04:19,459 --> 00:04:21,329
Și am încercat să citesc ceva
din dicționar.

85
00:04:21,329 --> 00:04:23,910
Și nu ne-am citit cu succes
ceva din dicționar, în

86
00:04:23,910 --> 00:04:26,650
caz în care avem nevoie pentru a elibera intrarea
că nu ne-am pus de fapt în

87
00:04:26,650 --> 00:04:29,140
hashtable, și în cele din urmă rupe.

88
00:04:29,140 --> 00:04:32,750
>> Odată ce am izbucni avem nevoie pentru a vedea, de asemenea,
ne-am izbucni deoarece acolo

89
00:04:32,750 --> 00:04:34,360
a fost citit o eroare de la dosar?

90
00:04:34,360 --> 00:04:37,120
Sau ne-am izbucni pentru ca noi
a ajuns la sfârșitul fișierului?

91
00:04:37,120 --> 00:04:39,480
Dacă a existat o eroare, atunci
vrem să se întoarcă false.

92
00:04:39,480 --> 00:04:40,930
Deoarece sarcina nu a reușit.

93
00:04:40,930 --> 00:04:43,890
Și în procesul de ne-o dorim pentru a descărca
toate cuvintele pe care le-am citit în, și

94
00:04:43,890 --> 00:04:45,670
închideți fișierul dicționar.

95
00:04:45,670 --> 00:04:48,740
>> Presupunând că am reușit, atunci ne-am
încă mai trebuie să închidă în dicționar

96
00:04:48,740 --> 00:04:53,040
dosar, și în cele din urmă a reveni adevărat din moment ce
încărcate cu succes în dicționar.

97
00:04:53,040 --> 00:04:54,420
Și asta este pentru sarcină.

98
00:04:54,420 --> 00:04:59,020
Deci, acum, verifica, având în vedere un Hashtable încărcat,
este de gând să arate ca aceasta.

99
00:04:59,020 --> 00:05:03,140
Deci, a verifica, se returnează un bool, care este
va indica dacă a trecut

100
00:05:03,140 --> 00:05:07,530
în char * cuvânt, dacă a trecut
în șir este în dicționar nostru.

101
00:05:07,530 --> 00:05:09,890
Deci, în cazul în care acesta este în dicționar,
în cazul în care acesta este în Hashtable nostru,

102
00:05:09,890 --> 00:05:11,170
ne vom întoarce adevărat.

103
00:05:11,170 --> 00:05:13,380
Și dacă nu e, ne vom întoarce false.

104
00:05:13,380 --> 00:05:17,740
>> Având în vedere acest lucru a trecut în cuvânt, suntem
merge la hash cuvântul.

105
00:05:17,740 --> 00:05:22,110
Acum, un lucru important să recunoaștem este
că în sarcină am știut că toate

106
00:05:22,110 --> 00:05:23,820
Cuvintele noi de gând să fie litere mici.

107
00:05:23,820 --> 00:05:25,820
Dar aici nu suntem așa de sigur.

108
00:05:25,820 --> 00:05:29,510
Dacă ne uităm la funcția noastră hash,
Funcția noastră hash de fapt

109
00:05:29,510 --> 00:05:32,700
este carcasa inferioară fiecare personaj
al cuvântului.

110
00:05:32,700 --> 00:05:37,940
Deci, indiferent de capitalizarea de
cuvânt, funcția noastră hash este revenirea

111
00:05:37,940 --> 00:05:42,270
același indice pentru orice
capitalizare este, așa cum ar trebui

112
00:05:42,270 --> 00:05:45,280
a revenit pentru o complet cu litere mici
versiune a cuvântului.

113
00:05:45,280 --> 00:05:46,600
În regulă.

114
00:05:46,600 --> 00:05:49,790
Acesta este indexul nostru este în
Hashtable pentru acest cuvânt.

115
00:05:49,790 --> 00:05:52,940
>> Acum, acest lucru pentru bucla se va
itera lista de legătura

116
00:05:52,940 --> 00:05:55,000
care a fost la acel index.

117
00:05:55,000 --> 00:05:59,610
Deci observa suntem inițializarea intrare
pentru a indica faptul că index.

118
00:05:59,610 --> 00:06:02,750
Vom continua
în timp ce intrare! = NULL.

119
00:06:02,750 --> 00:06:07,770
Și amintiți-vă că actualizarea indicatorul
în lista de intrare noastră legată = intrare> următor.

120
00:06:07,770 --> 00:06:14,400
Deci, au punctul nostru de intrare curent la
următorul element din lista de legat.

121
00:06:14,400 --> 00:06:19,250
>> Deci, pentru fiecare intrare în lista de legat,
vom folosi strcasecmp.

122
00:06:19,250 --> 00:06:20,330
Nu e strcomp.

123
00:06:20,330 --> 00:06:23,780
Pentru că, încă o dată, vrem să
face lucruri caz fără sensibilitate.

124
00:06:23,780 --> 00:06:27,870
Deci, vom folosi strcasecmp pentru a compara
cuvânt care a fost trecut prin acest

125
00:06:27,870 --> 00:06:31,860
Funcția împotriva cuvântului
care este în această intrare.

126
00:06:31,860 --> 00:06:35,570
În cazul în care se întoarce la zero, înseamnă că nu a fost
un meci, în cazul în care dorim să

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

128
00:06:36,630 --> 00:06:39,590
Am găsit cu succes
cuvânt în Hashtable nostru.

129
00:06:39,590 --> 00:06:43,040
>> Dacă nu a fost un meci, atunci suntem
merge la bucla din nou si uita-te la

130
00:06:43,040 --> 00:06:43,990
intrare următor.

131
00:06:43,990 --> 00:06:47,640
Și vom continua looping în timp ce acolo
sunt intrări în această listă legat.

132
00:06:47,640 --> 00:06:50,160
Ce se întâmplă dacă am rupe
din aceasta pentru buclă?

133
00:06:50,160 --> 00:06:55,110
Asta înseamnă că nu am găsit o intrare care
potrivit acest cuvânt, în care caz

134
00:06:55,110 --> 00:07:00,220
ne întoarcem false pentru a indica faptul că noastră
hashtable nu conțin acest cuvânt.

135
00:07:00,220 --> 00:07:02,540
Si asta e un cec.

136
00:07:02,540 --> 00:07:04,790
>> Deci, haideți să aruncăm o privire la dimensiune.

137
00:07:04,790 --> 00:07:06,970
Acum, dimensiunea va fi destul de simplu.

138
00:07:06,970 --> 00:07:11,080
Amintiți-vă, deoarece în sarcină, pentru fiecare cuvânt
am găsit, am incrementat un global

139
00:07:11,080 --> 00:07:12,880
Dimensiunea Hashtable variabilă.

140
00:07:12,880 --> 00:07:16,480
Deci, funcția de dimensiunea este doar de gând
pentru a reveni variabilă globală.

141
00:07:16,480 --> 00:07:18,150
Și asta e tot.

142
00:07:18,150 --> 00:07:22,300
>> Acum, în cele din urmă, avem nevoie pentru a descărca
dicționar dată totul sa terminat.

143
00:07:22,300 --> 00:07:25,340
Deci, cum vom face asta?

144
00:07:25,340 --> 00:07:30,440
Chiar aici suntem looping peste
toate găleți de masa noastră.

145
00:07:30,440 --> 00:07:33,240
Deci, există NUM_BUCKETS galeti.

146
00:07:33,240 --> 00:07:37,410
Și pentru fiecare listă legată în nostru
hashtable, vom buclă peste

147
00:07:37,410 --> 00:07:41,070
totalitatea lista legate,
eliberând fiecare element.

148
00:07:41,070 --> 00:07:42,900
>> Acum, avem nevoie să fim atenți.

149
00:07:42,900 --> 00:07:47,910
Deci, aici avem o variabilă temporar
care este stocarea indicatorul la alta

150
00:07:47,910 --> 00:07:49,730
element din lista de legătura.

151
00:07:49,730 --> 00:07:52,140
Și apoi vom liber
elementul curent.

152
00:07:52,140 --> 00:07:55,990
Avem nevoie pentru a fi sigur că vom face acest lucru, deoarece ne-am
nu se poate elibera doar elementul curent

153
00:07:55,990 --> 00:07:59,180
și apoi încercați să accesați cursorul următoare,
deoarece odată ce l-am eliberat,

154
00:07:59,180 --> 00:08:00,870
memoria devine invalid.

155
00:08:00,870 --> 00:08:04,990
>> Deci, avem nevoie pentru a menține în jurul valorii de un pointer la
elementul următor, atunci ne putem elibera

156
00:08:04,990 --> 00:08:08,360
element de curent, și apoi putem actualiza
elementul nostru curent de a indica

157
00:08:08,360 --> 00:08:09,550
elementul următor.

158
00:08:09,550 --> 00:08:12,800
Vom buclă în timp ce există elemente
în această listă legat.

159
00:08:12,800 --> 00:08:15,620
Vom face acest lucru pentru toate legate
liste în Hashtable.

160
00:08:15,620 --> 00:08:19,460
Și odată ce am terminat cu asta, ne-am
descărcată complet Hashtable, și

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

162
00:08:20,190 --> 00:08:23,200
Deci, este imposibil pentru descărcare
pentru a reveni vreodată false.

163
00:08:23,200 --> 00:08:26,470
Și când am terminat, ne-am
doar return true.

164
00:08:26,470 --> 00:08:29,000
>> Să-i dăm această soluție o încercare.

165
00:08:29,000 --> 00:08:33,070
Deci, haideți să aruncăm o privire la ceea ce noi
struct nod va arata.

166
00:08:33,070 --> 00:08:36,220
Aici vom vedea vom avea o bool
cuvânt și un nod struct * copii

167
00:08:36,220 --> 00:08:37,470
suport alfabet.

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

169
00:08:38,929 --> 00:08:42,020
Deci, primul lucru pe care ar putea fi
întrebam, de ce este ALPHABET

170
00:08:42,020 --> 00:08:44,660
ed definit ca 27?

171
00:08:44,660 --> 00:08:47,900
Ei bine, amintiți-vă că vom avea nevoie de
să fie de manipulare apostrof.

172
00:08:47,900 --> 00:08:51,910
Astfel că va fi un fel de
caz special de-a lungul acestui program.

173
00:08:51,910 --> 00:08:54,710
>> Acum imi amintesc cum o trie
de fapt, funcționează.

174
00:08:54,710 --> 00:08:59,380
Să presupunem că suntem indexarea cuvântul
"pisici". Apoi, de la rădăcina de trie,

175
00:08:59,380 --> 00:09:02,610
ne vom uita la copii
matrice, și ne vom uita la

176
00:09:02,610 --> 00:09:08,090
indice care corespunde literei
C. Deci, care vor fi indexate 2.

177
00:09:08,090 --> 00:09:11,530
Deci, având în vedere că, ceea ce va
ne da un nou nod.

178
00:09:11,530 --> 00:09:13,820
Și apoi vom lucra de la acel nod.

179
00:09:13,820 --> 00:09:17,770
>> Deci, având în vedere că nod, suntem încă o dată
gând să se uite la matrice copii.

180
00:09:17,770 --> 00:09:22,110
Și ne vom uita la index zero,
să corespundă A de pisică.

181
00:09:22,110 --> 00:09:27,170
Deci, atunci vom merge la acel nod,
și având în vedere că nod vom

182
00:09:27,170 --> 00:09:31,090
să se uite la final este o corespunde
la T. Și de a trece la acel nod,

183
00:09:31,090 --> 00:09:35,530
în cele din urmă, ne-am uitat complet
prin cuvântul nostru "pisică". Și acum bool

184
00:09:35,530 --> 00:09:40,960
cuvânt ar trebui să indice dacă
acest cuvânt dat este de fapt un cuvânt.

185
00:09:40,960 --> 00:09:43,470
>> Deci, de ce avem nevoie de acest caz special?

186
00:09:43,470 --> 00:09:47,700
Ei bine, ceea ce a cuvântului "catastrofă"
este în dicționarul nostru, dar

187
00:09:47,700 --> 00:09:50,150
Cuvântul "pisica" nu este?

188
00:09:50,150 --> 00:09:54,580
Deci, și căutați pentru a vedea dacă cuvântul "pisică"
este în dicționarul nostru, suntem

189
00:09:54,580 --> 00:09:59,970
de gând să se uite cu succes prin
indicii C-A-T în nod regiune.

190
00:09:59,970 --> 00:10:04,290
Dar asta e doar pentru că catastrofă
sa întâmplat pentru a crea noduri pe drum

191
00:10:04,290 --> 00:10:07,190
de la C-A-T, tot drumul de a
sfârșitul cuvântului.

192
00:10:07,190 --> 00:10:12,020
Deci, bool cuvânt este folosit pentru a indica dacă
această locație special

193
00:10:12,020 --> 00:10:14,310
indică de fapt un cuvânt.

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

195
00:10:15,140 --> 00:10:19,310
Deci, acum că știm ce trie este
va arăta, să ne uităm la

196
00:10:19,310 --> 00:10:20,730
Funcția se încarce.

197
00:10:20,730 --> 00:10:24,610
Astfel de sarcină este de gând să se întoarcă un bool
pentru dacă noi cu succes sau

198
00:10:24,610 --> 00:10:26,720
încărcate fără succes dicționar.

199
00:10:26,720 --> 00:10:30,460
Și acest lucru va fi în dicționar
pe care vrem să se încarce.

200
00:10:30,460 --> 00:10:33,930
>> Deci, primul lucru pe care vrem să faceți este să deschideți
up care dicționar pentru lectură.

201
00:10:33,930 --> 00:10:36,160
Și noi trebuie să ne asigurăm
nu am eșua.

202
00:10:36,160 --> 00:10:39,580
Deci, în cazul în dicționarul nu a fost
deschis cu succes, se va reveni

203
00:10:39,580 --> 00:10:42,400
nul, caz în care suntem
O să se întoarcă false.

204
00:10:42,400 --> 00:10:47,230
Dar presupunând că aceasta cu succes
a deschis, atunci se poate citi de fapt

205
00:10:47,230 --> 00:10:48,220
prin dicționar.

206
00:10:48,220 --> 00:10:50,880
>> Deci, primul lucru pe care am de gând să
Vreau să faceți este să avem această

207
00:10:50,880 --> 00:10:52,500
rădăcină variabilă globală.

208
00:10:52,500 --> 00:10:56,190
Acum rădăcină va fi un nod *.

209
00:10:56,190 --> 00:10:59,760
Este partea de sus a trie nostru că suntem
va fi iterarea prin intermediul.

210
00:10:59,760 --> 00:11:02,660
Deci, primul lucru pe care vom
să vrea să faceți este să aloce

211
00:11:02,660 --> 00:11:04,140
memorie de radacina noastra.

212
00:11:04,140 --> 00:11:07,980
Observați că suntem folosind calloc
funcție, care este în esență același

213
00:11:07,980 --> 00:11:11,500
ca funcția malloc, cu excepția e
garantat pentru a reveni ceva care este

214
00:11:11,500 --> 00:11:13,180
complet adus la zero.

215
00:11:13,180 --> 00:11:17,290
Deci, dacă am folosit malloc, ne-ar trebui să
du-te prin toate indicii în nostru

216
00:11:17,290 --> 00:11:20,160
nod, și asigurați-vă că
toate acestea sunt nule.

217
00:11:20,160 --> 00:11:22,710
Astfel calloc va face asta pentru noi.

218
00:11:22,710 --> 00:11:26,330
>> Acum, la fel ca malloc, avem nevoie pentru a face
vă că alocarea a fost de fapt

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

220
00:11:27,520 --> 00:11:29,990
În cazul în care acest lucru sa întors null, atunci ne-am
nevoie pentru a închide sau dicționar

221
00:11:29,990 --> 00:11:32,100
fișier și a reveni false.

222
00:11:32,100 --> 00:11:36,835
Deci, presupunând că alocarea a fost
de succes, vom folosi un nod *

223
00:11:36,835 --> 00:11:40,270
cursorul pentru a itera prin trie nostru.

224
00:11:40,270 --> 00:11:43,890
Deci, rădăcinile noastre nu se va schimba,
dar am de gând să folosească cursorul pentru a

225
00:11:43,890 --> 00:11:47,875
de fapt, du-te de la nod la nod.

226
00:11:47,875 --> 00:11:50,940
>> Deci, în această buclă pentru citim
prin fișierul dicționar.

227
00:11:50,940 --> 00:11:53,670
Și folosim fgetc.

228
00:11:53,670 --> 00:11:56,290
Fgetc este de gând să apuca un singur
personaj din dosar.

229
00:11:56,290 --> 00:11:59,370
Vom continua hapsân
caractere în timp ce noi nu ajung la

230
00:11:59,370 --> 00:12:01,570
sfârșitul fișierului.

231
00:12:01,570 --> 00:12:03,480
>> Există două cazuri pe care trebuie să se ocupe.

232
00:12:03,480 --> 00:12:06,610
Primul, dacă caracterul
Nu a fost o nouă linie.

233
00:12:06,610 --> 00:12:10,450
Deci, noi știm dacă a fost o noua linie, apoi
suntem pe cale de a trece la un nou cuvânt.

234
00:12:10,450 --> 00:12:15,240
Dar presupunând că nu a fost o linie nouă, apoi
aici ne-am dori să dau seama de

235
00:12:15,240 --> 00:12:18,380
index vom index în
în matrice copii care

236
00:12:18,380 --> 00:12:19,810
ne-am uitat la mai înainte.

237
00:12:19,810 --> 00:12:23,880
>> Deci, cum am spus mai înainte, trebuie să ne
caz special apostrof.

238
00:12:23,880 --> 00:12:26,220
Observați suntem folosind ternar
operator de aici.

239
00:12:26,220 --> 00:12:29,580
Așa că am de gând să citesc acest lucru ca, în cazul în care
caracterul am citit într-o a fost

240
00:12:29,580 --> 00:12:35,330
apostrof, atunci vom stabili
index = "alfabet" -1, care va

241
00:12:35,330 --> 00:12:37,680
fie indexul 26.

242
00:12:37,680 --> 00:12:41,130
>> Altfel, în cazul în care acesta nu a fost un apostrof, acolo
vom stabili indicele

243
00:12:41,130 --> 00:12:43,760
egal cu c - un.

244
00:12:43,760 --> 00:12:49,030
Deci, amintiți-vă înapoi de la anterior p-seturi,
c - o este de gând să ne dea

245
00:12:49,030 --> 00:12:53,410
Poziția alfabetică a C. Deci, dacă
C este litera A, acest lucru va

246
00:12:53,410 --> 00:12:54,700
ne da index zero.

247
00:12:54,700 --> 00:12:58,120
Pentru litera B, se va da
ne indicele 1, și așa mai departe.

248
00:12:58,120 --> 00:13:03,010
>> Deci, acest lucru ne dă indicele în
copii matrice pe care ne-o dorim.

249
00:13:03,010 --> 00:13:08,890
Acum, în cazul în care acest indice este în prezent nul în
copiii, care înseamnă că un nod

250
00:13:08,890 --> 00:13:11,830
nu există în prezent
de la această cale.

251
00:13:11,830 --> 00:13:15,160
Deci, avem nevoie de a aloca
un nod pentru această cale.

252
00:13:15,160 --> 00:13:16,550
Asta e ceea ce vom face aici.

253
00:13:16,550 --> 00:13:20,690
>> Așa că am de gând să folosească din nou calloc
funcție, astfel încât să nu trebuie să

254
00:13:20,690 --> 00:13:22,880
zero, toate indicii.

255
00:13:22,880 --> 00:13:27,240
Și din nou avem nevoie pentru a verifica
că calloc nu a eșuat.

256
00:13:27,240 --> 00:13:30,700
Dacă calloc a eșua, atunci avem nevoie de
pentru a descărca totul, închideți nostru

257
00:13:30,700 --> 00:13:32,820
dicționar, și să se întoarcă false.

258
00:13:32,820 --> 00:13:40,050
Deci, presupunând că nu reușesc, atunci
acest lucru va crea un nou copil pentru noi.

259
00:13:40,050 --> 00:13:41,930
Și apoi vom merge la acel copil.

260
00:13:41,930 --> 00:13:44,960
Cursor nostru va repeta
până la acel copil.

261
00:13:44,960 --> 00:13:49,330
>> Acum, în cazul în care acest lucru nu a fost nul pentru a începe cu,
atunci cursorul se poate repeta doar

262
00:13:49,330 --> 00:13:52,590
până la care copilul fără de fapt,
a trebui să aloce nimic.

263
00:13:52,590 --> 00:13:56,730
Acesta este cazul în care ne-am sa întâmplat în primul rând
aloca cuvântul "pisică". Și

264
00:13:56,730 --> 00:14:00,330
asta înseamnă că, atunci când vom merge să aloce
"Catastrofă," nu avem nevoie pentru a crea

265
00:14:00,330 --> 00:14:01,680
noduri pentru C-A-T din nou.

266
00:14:01,680 --> 00:14:04,830
Acestea există deja.

267
00:14:04,830 --> 00:14:06,080
>> Ce este acest altceva?

268
00:14:06,080 --> 00:14:10,480
Aceasta este condiția în care c este
backslash n, unde c este o noua linie.

269
00:14:10,480 --> 00:14:13,710
Acest lucru înseamnă că avem succes
finalizat un cuvânt.

270
00:14:13,710 --> 00:14:16,860
Acum, ce vrem să facem atunci când ne-am
finalizat cu succes un cuvânt?

271
00:14:16,860 --> 00:14:21,100
Vom folosi acest domeniu cuvânt
interiorul nod noastre struct.

272
00:14:21,100 --> 00:14:23,390
Vrem să stabilească care la true.

273
00:14:23,390 --> 00:14:27,150
Deci, care indică faptul că acest nod
indică un succes

274
00:14:27,150 --> 00:14:29,250
cuvânt, un cuvânt real.

275
00:14:29,250 --> 00:14:30,940
>> Acum stabilit că, pentru a adevărat.

276
00:14:30,940 --> 00:14:35,150
Vrem să resetați cursorul nostru la punct
la începutul trie din nou.

277
00:14:35,150 --> 00:14:40,160
Și, în sfârșit, incrementa dicționarul nostru
dimensiune, deoarece am găsit un alt lucru.

278
00:14:40,160 --> 00:14:43,230
Deci, vom continua să faci asta,
lectură în caracter cu caracter,

279
00:14:43,230 --> 00:14:49,150
construirea de noi noduri în trie noastră și
pentru fiecare cuvânt în dicționar, până

280
00:14:49,150 --> 00:14:54,020
vom ajunge în cele din urmă C! = EOF, în care
caz ne-am iesi din dosar.

281
00:14:54,020 --> 00:14:57,050
>> Acum, există două cazuri în conformitate cu
pe care ne-am fi lovit EOF.

282
00:14:57,050 --> 00:15:00,980
Primul este dacă a existat o eroare
citirea din fișierul.

283
00:15:00,980 --> 00:15:03,470
Deci, dacă a fost o eroare, ne-am
au nevoie pentru a face tipic.

284
00:15:03,470 --> 00:15:06,460
Descărca totul, aproape
fișierul, intoarce false.

285
00:15:06,460 --> 00:15:09,810
Presupunând că nu a fost o eroare, care
înseamnă doar ne-am lovit de fapt la sfârșitul anului

286
00:15:09,810 --> 00:15:13,750
dosar, în care caz, am închide
fișier și a reveni adevărat din moment ce

287
00:15:13,750 --> 00:15:17,330
dicționar încărcat cu succes
în trie nostru.

288
00:15:17,330 --> 00:15:20,170
>> Deci, acum, haideți să verificați de verificare.

289
00:15:20,170 --> 00:15:25,156
Privind la funcția de verificare, vom vedea
care verificare este de gând să se întoarcă un bool.

290
00:15:25,156 --> 00:15:29,680
Acesta returneaza true daca acest cuvânt care este
fiind trecut este în trie nostru.

291
00:15:29,680 --> 00:15:32,110
Returnează false în caz contrar.

292
00:15:32,110 --> 00:15:36,050
Deci, cum te determina dacă
acest cuvânt este în trie nostru?

293
00:15:36,050 --> 00:15:40,190
>> Vedem aici că, la fel ca înainte,
vom folosi cursorul pentru a repeta

294
00:15:40,190 --> 00:15:41,970
prin trie nostru.

295
00:15:41,970 --> 00:15:46,600
Acum, aici vom repeta
peste întreaga noastră cuvânt.

296
00:15:46,600 --> 00:15:50,620
Astfel iterarea peste cuvântul suntem trecut,
vom stabili

297
00:15:50,620 --> 00:15:56,400
index în matrice copii care
corespunde cuvânt suport I. Deci, acest

298
00:15:56,400 --> 00:15:59,670
este de gând să arate exact ca
sarcină, în cazul în care în cazul în care cuvântul [i]

299
00:15:59,670 --> 00:16:03,310
este un apostrof, atunci ne-o dorim
de a utiliza indicele de "alfabet" - 1.

300
00:16:03,310 --> 00:16:05,350
Pentru că am stabilit că
este în cazul în care vom stoca

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

302
00:16:07,100 --> 00:16:11,780
>> Altfel vom folosi două cuvinte mai mici
Suport I. Deci, amintiți-vă că Word poate

303
00:16:11,780 --> 00:16:13,920
au capitalizare arbitrar.

304
00:16:13,920 --> 00:16:17,540
Și așa vrem să ne asigurăm că suntem
folosind o versiune cu litere mici de lucruri.

305
00:16:17,540 --> 00:16:21,920
Și apoi scade de la care "a" la o dată
din nou ne da ordinea alfabetică

306
00:16:21,920 --> 00:16:23,880
poziție de care caracter.

307
00:16:23,880 --> 00:16:27,680
Astfel că va fi indexul nostru
în matrice copii.

308
00:16:27,680 --> 00:16:32,420
>> Și acum, dacă că indicele în copii
matrice este nulă, înseamnă că ne-am

309
00:16:32,420 --> 00:16:34,990
nu mai poate continua iterarea
jos trie nostru.

310
00:16:34,990 --> 00:16:38,870
Dacă acesta este cazul, acest cuvânt nu poate
fi, eventual, în trie nostru.

311
00:16:38,870 --> 00:16:42,340
Deoarece dacă ar fi, care ar
Adică nu ar fi o cale

312
00:16:42,340 --> 00:16:43,510
până la acest cuvânt.

313
00:16:43,510 --> 00:16:45,290
Și nu te-ar întâlni nul.

314
00:16:45,290 --> 00:16:47,850
Așa se confruntă cu null, ne întoarcem false.

315
00:16:47,850 --> 00:16:49,840
În care cuvântul nu este în dicționar.

316
00:16:49,840 --> 00:16:53,660
În cazul în care nu au fost nule, atunci suntem
O să iterarea continua.

317
00:16:53,660 --> 00:16:57,220
>> Deci mergem acolo cursor
pentru a indica faptul că special

318
00:16:57,220 --> 00:16:59,760
nod la acel index.

319
00:16:59,760 --> 00:17:03,150
Noi continua să faci asta de-a lungul
întregul cuvânt, presupunând

320
00:17:03,150 --> 00:17:03,950
nu am lovit nul.

321
00:17:03,950 --> 00:17:07,220
Asta înseamnă că noi am fost capabil de a obține prin intermediul
întregul cuvânt și găsi

322
00:17:07,220 --> 00:17:08,920
un nod în try nostru.

323
00:17:08,920 --> 00:17:10,770
Dar nu suntem destul de terminat încă.

324
00:17:10,770 --> 00:17:12,290
>> Noi nu vrem să se întoarcă doar adevărat.

325
00:17:12,290 --> 00:17:14,770
Vrem să se întoarcă cursorul> cuvânt.

326
00:17:14,770 --> 00:17:18,980
Din moment ce ne amintim din nou, este "pisica" nu este
în dicționarul nostru, și "catastrofă"

327
00:17:18,980 --> 00:17:22,935
este, atunci ne vom lua cu succes
prin cuvântul "pisică". Dar cursor

328
00:17:22,935 --> 00:17:25,760
Cuvântul va fi fals și nu este adevărat.

329
00:17:25,760 --> 00:17:30,930
Deci, ne întoarcem cuvânt cursor pentru a indica
dacă acest nod este de fapt un cuvânt.

330
00:17:30,930 --> 00:17:32,470
Și asta este pentru verificare.

331
00:17:32,470 --> 00:17:34,250
>> Deci, haideți să verificați dimensiunea.

332
00:17:34,250 --> 00:17:37,350
Deci, dimensiunea va fi destul de ușor
din moment ce, amintiți-vă în sarcină, suntem

333
00:17:37,350 --> 00:17:41,430
incrementarea dimensiune dicționar pentru
fiecare cuvânt pe care le întâlnim.

334
00:17:41,430 --> 00:17:45,350
Deci, dimensiunea este doar de gând să
reveni dimensiune dicționar.

335
00:17:45,350 --> 00:17:47,390
Și asta e tot.

336
00:17:47,390 --> 00:17:50,590
>> Deci, în cele din urmă ne-am descărca.

337
00:17:50,590 --> 00:17:55,100
Deci descărca, vom folosi un
Funcția recursive a face de fapt tot

338
00:17:55,100 --> 00:17:56,530
de lucru pentru noi.

339
00:17:56,530 --> 00:17:59,340
Deci, funcția noastră va
fi numit pe descărcător.

340
00:17:59,340 --> 00:18:01,650
Ce este descărcător de gând să faci?

341
00:18:01,650 --> 00:18:06,580
Vedem aici că descărcător se va
itera peste toți copiii la

342
00:18:06,580 --> 00:18:08,410
acest nod special.

343
00:18:08,410 --> 00:18:11,750
Și dacă nodul copil nu este
null, atunci vom

344
00:18:11,750 --> 00:18:13,730
descărca nodul copil.

345
00:18:13,730 --> 00:18:18,010
>> Deci, aceasta este de ai descărca recursiv
toate de copiii noștri.

346
00:18:18,010 --> 00:18:21,080
Odată ce suntem siguri că toți copiii noștri
au fost descărcate, apoi ne-am

347
00:18:21,080 --> 00:18:25,210
ne putem elibera, așa
descărca noi.

348
00:18:25,210 --> 00:18:29,460
Aceasta va funcționa recursiv
descarce întreaga trie.

349
00:18:29,460 --> 00:18:32,850
Și apoi, o dată ce a făcut,
ne putem întoarce pur și simplu adevărată.

350
00:18:32,850 --> 00:18:34,210
În gol nu poate da greș.

351
00:18:34,210 --> 00:18:35,710
Noi doar eliberarea lucruri.

352
00:18:35,710 --> 00:18:38,870
Deci, odată ce am terminat eliberarea
totul, return true.

353
00:18:38,870 --> 00:18:40,320
Și asta e tot.

354
00:18:40,320 --> 00:18:41,080
Numele meu este Rob.

355
00:18:41,080 --> 00:18:42,426
Și acest lucru a fost speller.

356
00:18:42,426 --> 00:18:47,830
>> [Redare a muzicii]