1
00:00:00,000 --> 00:00:12,350
>> [GIOCO MUSICA]

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

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

4
00:00:13,640 --> 00:00:16,210
E cerchiamo di questa soluzione fuori.

5
00:00:16,210 --> 00:00:20,070
Così qui stiamo andando a implementare
una tabella generale.

6
00:00:20,070 --> 00:00:24,090
Si vede che il nodo struct del nostro
tabella è andare a guardare come questo.

7
00:00:24,090 --> 00:00:28,710
Così sta andando ad avere un carattere normale
array di dimensioni LUNGHEZZA + 1.

8
00:00:28,710 --> 00:00:32,259
Non dimenticare il + 1, dato che il massimo
parola nel dizionario è di 45

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

10
00:00:33,130 --> 00:00:37,070
E poi stiamo andando ad avere bisogno uno in più
caratteri per lo zero backslash.

11
00:00:37,070 --> 00:00:40,870
>> E allora la nostra hashtable in ogni
benna sta per memorizzare un

12
00:00:40,870 --> 00:00:42,320
lista concatenata di nodi.

13
00:00:42,320 --> 00:00:44,420
Non stiamo facendo scansione lineare qui.

14
00:00:44,420 --> 00:00:48,430
E così, al fine di collegare al successivo
elemento nel secchio, abbiamo bisogno di una

15
00:00:48,430 --> 00:00:50,390
struct node * prossimo.

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

17
00:00:51,110 --> 00:00:53,090
Quindi questo è quello che un nodo assomiglia.

18
00:00:53,090 --> 00:00:56,180
>> Ora qui è la dichiarazione
della nostra tabella hash.

19
00:00:56,180 --> 00:00:59,640
E 'intenzione di avere 16.834 secchi.

20
00:00:59,640 --> 00:01:01,910
Ma questo numero non importa.

21
00:01:01,910 --> 00:01:05,450
E, infine, stiamo andando ad avere la
Dimensioni tabella hash variabile globale, che

22
00:01:05,450 --> 00:01:07,000
sta per iniziare a zero.

23
00:01:07,000 --> 00:01:10,760
E sta andando a tenere traccia di come
molte parole sono nel nostro dizionario.

24
00:01:10,760 --> 00:01:13,710
>> Quindi diamo un'occhiata a carico.

25
00:01:13,710 --> 00:01:16,390
Si noti che il carico, esso restituisce un bool.

26
00:01:16,390 --> 00:01:20,530
Si ritorna true se fosse successo
caricato, false in caso contrario.

27
00:01:20,530 --> 00:01:23,990
E ci vuole un dizionario * const char,
che è il dizionario

28
00:01:23,990 --> 00:01:25,280
che vogliamo aprire.

29
00:01:25,280 --> 00:01:27,170
Ecco, questo è la prima cosa
stiamo andando a fare.

30
00:01:27,170 --> 00:01:29,500
>> Stiamo andando a fopen l'
Dizionario per la lettura.

31
00:01:29,500 --> 00:01:31,680
E stiamo andando ad avere per fare
Assicurarsi che è riuscito.

32
00:01:31,680 --> 00:01:35,920
Quindi, se restituito NULL, allora non abbiamo
aprire correttamente il dizionario.

33
00:01:35,920 --> 00:01:37,440
E dobbiamo restituire false.

34
00:01:37,440 --> 00:01:41,580
Ma supponendo che lo ha fatto con successo
aperto, quindi vogliamo leggere l'

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

36
00:01:42,400 --> 00:01:46,450
In modo da mantenere il ciclo finché non troviamo un po '
motivo per uscire da questo ciclo,

37
00:01:46,450 --> 00:01:47,570
che vedremo.

38
00:01:47,570 --> 00:01:48,920
Così mantenere looping.

39
00:01:48,920 --> 00:01:51,780
>> E ora stiamo andando a
malloc un singolo nodo.

40
00:01:51,780 --> 00:01:54,020
E naturalmente abbiamo bisogno
all'aria prova di nuovo.

41
00:01:54,020 --> 00:01:58,680
Quindi, se mallocing non è riuscito, quindi
vogliamo scaricare qualsiasi nodo che

42
00:01:58,680 --> 00:02:02,590
è successo a malloc prima, chiudere il
Dizionario e restituire false.

43
00:02:02,590 --> 00:02:06,830
Ma ignorare che, assumendo che
riuscito, allora vogliamo usare fscanf

44
00:02:06,830 --> 00:02:12,400
leggere una sola parola dei
Dizionario nel nostro nodo.

45
00:02:12,400 --> 00:02:17,940
Quindi ricorda che l'ingresso> parola è il carattere
tampone parola di dimensioni lenghth + 1

46
00:02:17,940 --> 00:02:20,300
che stiamo andando a memorizzare la parola dentro

47
00:02:20,300 --> 00:02:25,070
>> Così fscanf sta per restituire 1, purché
come è stato in grado di successo

48
00:02:25,070 --> 00:02:26,750
leggere una parola dal file.

49
00:02:26,750 --> 00:02:30,460
Se succede sia un errore, o noi
raggiungere la fine del file,

50
00:02:30,460 --> 00:02:31,950
non tornerà 1.

51
00:02:31,950 --> 00:02:35,180
Nel qual caso non ritorna 1,
stiamo finalmente per uscire

52
00:02:35,180 --> 00:02:37,280
questo ciclo while.

53
00:02:37,280 --> 00:02:42,770
Così vediamo che quando abbiamo successo
leggere una parola in

54
00:02:42,770 --> 00:02:48,270
iscrizione> parola, poi andremo a che
parola utilizzando la nostra funzione di hash.

55
00:02:48,270 --> 00:02:49,580
>> Diamo uno sguardo a
la funzione hash.

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

57
00:02:52,430 --> 00:02:55,610
Quindi non si ha realmente bisogno
per capire questo.

58
00:02:55,610 --> 00:02:59,460
E in realtà abbiamo appena tirato questo hash
funzionare da internet.

59
00:02:59,460 --> 00:03:04,010
L'unica cosa che dovete riconoscere è
che questo richiede un const char * word.

60
00:03:04,010 --> 00:03:08,960
Così sta prendendo una stringa come input, e
restituire un int unsigned come output.

61
00:03:08,960 --> 00:03:12,360
Ecco, questo è tutto una funzione di hash è, è
prende in input e ti dà una

62
00:03:12,360 --> 00:03:14,490
indice nella tabella hash.

63
00:03:14,490 --> 00:03:18,530
>> Notate che stiamo moding da NUM_BUCKETS,
in modo che il valore restituito

64
00:03:18,530 --> 00:03:21,730
in realtà è un indice nella tabella hash
e non indicizza oltre il

65
00:03:21,730 --> 00:03:24,320
limiti della matrice.

66
00:03:24,320 --> 00:03:28,060
Quindi, dato che la funzione, stiamo andando
hash la parola che leggiamo l'

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

68
00:03:29,390 --> 00:03:31,700
E poi andremo a utilizzare
che hash per inserire la

69
00:03:31,700 --> 00:03:33,750
entrata nella tabella hash.

70
00:03:33,750 --> 00:03:38,520
>> Hash Ora hashtable è la corrente
elenco collegato nella tabella.

71
00:03:38,520 --> 00:03:41,410
Ed è molto probabile
che è solo NULL.

72
00:03:41,410 --> 00:03:44,960
Vogliamo inserire il nostro ingresso alla
all'inizio di questa lista collegata.

73
00:03:44,960 --> 00:03:48,600
E così stiamo per avere la nostra attuale
punto di ingresso a quello che il hashtable

74
00:03:48,600 --> 00:03:50,380
Attualmente punti a.

75
00:03:50,380 --> 00:03:53,310
E poi andremo a memorizzare,
nella tabella hash alla

76
00:03:53,310 --> 00:03:55,350
hash, la voce corrente.

77
00:03:55,350 --> 00:03:59,320
Così queste due righe inserire con successo
la voce all'inizio del

78
00:03:59,320 --> 00:04:02,260
lista collegata a tale indice
nella tabella hash.

79
00:04:02,260 --> 00:04:04,900
>> Una volta che abbiamo finito con quello, sappiamo
che abbiamo trovato un'altra parola nella

80
00:04:04,900 --> 00:04:07,790
dizionario, e incrementiamo di nuovo.

81
00:04:07,790 --> 00:04:13,960
Così continuiamo a farlo fino fscanf
finalmente tornato qualcosa di non-1 a

82
00:04:13,960 --> 00:04:16,950
questo punto ricordare che
abbiamo bisogno di liberare voce.

83
00:04:16,950 --> 00:04:19,459
Quindi qui abbiamo malloced una voce.

84
00:04:19,459 --> 00:04:21,329
E abbiamo cercato di leggere qualcosa
dal dizionario.

85
00:04:21,329 --> 00:04:23,910
E non abbiamo letto con successo
qualcosa dal dizionario, in

86
00:04:23,910 --> 00:04:26,650
qual caso occorre liberare la voce
che non abbiamo mai messo in

87
00:04:26,650 --> 00:04:29,140
Hashtable, e infine rompere.

88
00:04:29,140 --> 00:04:32,750
>> Una volta che usciamo abbiamo bisogno di vedere, bene,
fatto usciamo perché non

89
00:04:32,750 --> 00:04:34,360
stava leggendo un errore dal file?

90
00:04:34,360 --> 00:04:37,120
Oppure abbiamo rompere fuori perché abbiamo
raggiunto la fine del file?

91
00:04:37,120 --> 00:04:39,480
Se c'è stato un errore, quindi
vogliamo tornare false.

92
00:04:39,480 --> 00:04:40,930
Dato che il carico non è riuscito.

93
00:04:40,930 --> 00:04:43,890
E nel processo vogliamo scaricare
tutte le parole che leggiamo in, e

94
00:04:43,890 --> 00:04:45,670
chiudere il file dizionario.

95
00:04:45,670 --> 00:04:48,740
>> Supponendo che ci siamo riusciti, poi abbiamo appena
ancora bisogno di chiudere il dizionario

96
00:04:48,740 --> 00:04:53,040
File e infine ritorno vero dal momento che
caricata correttamente il dizionario.

97
00:04:53,040 --> 00:04:54,420
E questo è tutto per il carico.

98
00:04:54,420 --> 00:04:59,020
Così ora controllare, dato un hashtable caricata,
sta andando a guardare come questo.

99
00:04:59,020 --> 00:05:03,140
Quindi controllare, restituisce un bool, che è
andando per indicare se il passato

100
00:05:03,140 --> 00:05:07,530
in char * parola, se il passato
nella stringa è nel nostro dizionario.

101
00:05:07,530 --> 00:05:09,890
Quindi, se è nel dizionario,
se è nella nostra tabella hash,

102
00:05:09,890 --> 00:05:11,170
ci torneremo vero.

103
00:05:11,170 --> 00:05:13,380
E se non lo è, ci torneremo false.

104
00:05:13,380 --> 00:05:17,740
>> Dato questo passò in parola, siamo
andando hash parola.

105
00:05:17,740 --> 00:05:22,110
Ora, una cosa importante da riconoscere è
che in carico sapevamo che tutte le

106
00:05:22,110 --> 00:05:23,820
parole che andremo ad essere minuscolo.

107
00:05:23,820 --> 00:05:25,820
Ma qui non siamo così sicuri.

108
00:05:25,820 --> 00:05:29,510
Se diamo uno sguardo alla nostra funzione di hash,
la nostra funzione di hash realtà

109
00:05:29,510 --> 00:05:32,700
è inferiore dell'involucro ogni carattere
della parola.

110
00:05:32,700 --> 00:05:37,940
Quindi, indipendentemente dalla capitalizzazione di
parola, la nostra funzione hash è il ritorno

111
00:05:37,940 --> 00:05:42,270
lo stesso indice per qualunque
capitalizzazione è, come avrebbe

112
00:05:42,270 --> 00:05:45,280
restituito per completamente minuscolo
versione della parola.

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

114
00:05:46,600 --> 00:05:49,790
Questo è il nostro indice è verso la
Hashtable per questa parola.

115
00:05:49,790 --> 00:05:52,940
>> Ora questo ciclo for sta per
scorrere l'elenco collegato

116
00:05:52,940 --> 00:05:55,000
che era a tale indice.

117
00:05:55,000 --> 00:05:59,610
Così notiamo che stiamo inizializzazione di iscrizione
per puntare a tale indice.

118
00:05:59,610 --> 00:06:02,750
Abbiamo intenzione di continuare
mentre la voce! = NULL.

119
00:06:02,750 --> 00:06:07,770
E ricorda che l'aggiornamento del puntatore
nella nostra lista iscrizione collegata = entry> prossimo.

120
00:06:07,770 --> 00:06:14,400
Così abbiamo il nostro punto di ingresso attuale
l'elemento successivo nella lista collegata.

121
00:06:14,400 --> 00:06:19,250
>> Quindi, per ogni voce nella lista collegata,
stiamo andando a utilizzare strcasecmp.

122
00:06:19,250 --> 00:06:20,330
Non è StrComp.

123
00:06:20,330 --> 00:06:23,780
Perché, ancora una volta, vogliamo
fare caso le cose insensitively.

124
00:06:23,780 --> 00:06:27,870
Quindi usiamo strcasecmp confrontare la
parola che è stato passato attraverso questo

125
00:06:27,870 --> 00:06:31,860
funzione contro la parola
cioè in questa voce.

126
00:06:31,860 --> 00:06:35,570
Se si restituisce zero, significa che non vi era
una partita, in questo caso vogliamo

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

128
00:06:36,630 --> 00:06:39,590
Abbiamo trovato con successo la
parola nella nostra tabella hash.

129
00:06:39,590 --> 00:06:43,040
>> Se non ci fosse una partita, quindi siamo
andando in loop di nuovo e guardare il

130
00:06:43,040 --> 00:06:43,990
voce successiva.

131
00:06:43,990 --> 00:06:47,640
E noi continueremo looping mentre ci
sono voci in questa lista collegata.

132
00:06:47,640 --> 00:06:50,160
Cosa succede se rompiamo
fuori di questo ciclo for?

133
00:06:50,160 --> 00:06:55,110
Questo significa che non abbiamo trovato una voce che
abbinato questa parola, nel qual caso

134
00:06:55,110 --> 00:07:00,220
torniamo false per indicare che il nostro
hashtable non conteneva questa parola.

135
00:07:00,220 --> 00:07:02,540
E questo è un assegno.

136
00:07:02,540 --> 00:07:04,790
>> Quindi diamo un'occhiata a dimensioni.

137
00:07:04,790 --> 00:07:06,970
Ora dimensioni sta per essere piuttosto semplice.

138
00:07:06,970 --> 00:07:11,080
Da ricordare in carico, per ogni parola
abbiamo trovato, abbiamo incrementato globale

139
00:07:11,080 --> 00:07:12,880
Dimensioni tabella hash variabile.

140
00:07:12,880 --> 00:07:16,480
Quindi la funzione di dimensione è solo andare
per tornare variabile globale.

141
00:07:16,480 --> 00:07:18,150
E questo è tutto.

142
00:07:18,150 --> 00:07:22,300
>> Ora finalmente, abbiamo bisogno di scaricare la
dizionario una volta che tutto è fatto.

143
00:07:22,300 --> 00:07:25,340
Quindi, come facciamo a fare questo?

144
00:07:25,340 --> 00:07:30,440
Proprio qui stiamo eseguendo un ciclo su
tutti i secchi della nostra tavola.

145
00:07:30,440 --> 00:07:33,240
Quindi ci sono NUM_BUCKETS secchi.

146
00:07:33,240 --> 00:07:37,410
E per ogni lista collegata nel nostro
hashtable, stiamo andando a ciclo su

147
00:07:37,410 --> 00:07:41,070
l'interezza della lista collegata,
liberando ogni elemento.

148
00:07:41,070 --> 00:07:42,900
>> Ora dobbiamo stare attenti.

149
00:07:42,900 --> 00:07:47,910
Quindi qui abbiamo una variabile temporanea
che è memorizzare il puntatore al successivo

150
00:07:47,910 --> 00:07:49,730
elemento della lista concatenata.

151
00:07:49,730 --> 00:07:52,140
E poi stiamo andando alla libera
l'elemento corrente.

152
00:07:52,140 --> 00:07:55,990
Dobbiamo essere sicuri che facciamo da quando abbiamo
non si può semplicemente liberare l'elemento corrente

153
00:07:55,990 --> 00:07:59,180
e quindi provare ad accedere il puntatore prossimo,
dal momento che una volta che abbiamo liberato esso,

154
00:07:59,180 --> 00:08:00,870
la memoria non è più valido.

155
00:08:00,870 --> 00:08:04,990
>> Quindi abbiamo bisogno di mantenere attorno a un puntatore a
l'elemento successivo, allora possiamo liberare il

156
00:08:04,990 --> 00:08:08,360
elemento corrente, e quindi possiamo aggiornare
il nostro elemento corrente per puntare a

157
00:08:08,360 --> 00:08:09,550
l'elemento successivo.

158
00:08:09,550 --> 00:08:12,800
Ti ciclo while ci sono elementi
in questa lista collegata.

159
00:08:12,800 --> 00:08:15,620
Lo faremo per tutte legate
liste nella tabella hash.

160
00:08:15,620 --> 00:08:19,460
E una volta che avremo finito con quello, abbiamo
completamente scaricato la tabella hash, e

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

162
00:08:20,190 --> 00:08:23,200
Quindi è impossibile per lo scaricamento
per ritornare sempre false.

163
00:08:23,200 --> 00:08:26,470
E quando abbiamo finito, abbiamo
solo return true.

164
00:08:26,470 --> 00:08:29,000
>> Diamo questa soluzione una prova.

165
00:08:29,000 --> 00:08:33,070
Quindi diamo un'occhiata a ciò che il nostro
struct nodo sarà simile.

166
00:08:33,070 --> 00:08:36,220
Qui vediamo che stiamo andando ad avere un bool
parola e un nodo struct * bambini

167
00:08:36,220 --> 00:08:37,470
Staffa ALFABETO.

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

169
00:08:38,929 --> 00:08:42,020
Quindi la prima cosa che si potrebbe essere
chiedendo, perché è ALFABETO

170
00:08:42,020 --> 00:08:44,660
Ed definito come 27?

171
00:08:44,660 --> 00:08:47,900
Beh, ricordiamo che stiamo andando ad avere bisogno
da gestire l'apostrofo.

172
00:08:47,900 --> 00:08:51,910
In modo che sara 'un po' un
caso speciale nel corso di questo programma.

173
00:08:51,910 --> 00:08:54,710
>> Ora, ricordare come un trie
effettivamente funziona.

174
00:08:54,710 --> 00:08:59,380
Diciamo che stiamo indicizzando la parola
"gatti". Poi dalla radice del trie,

175
00:08:59,380 --> 00:09:02,610
stiamo andando a guardare i bambini
array, e stiamo andando a guardare il

176
00:09:02,610 --> 00:09:08,090
indice che corrisponde alla lettera
C. So che sarà indicizzato 2.

177
00:09:08,090 --> 00:09:11,530
Quindi, dato che, quella volontà
ci danno un nuovo nodo.

178
00:09:11,530 --> 00:09:13,820
E poi ci lavoriamo da quel nodo.

179
00:09:13,820 --> 00:09:17,770
>> Quindi, dato che il nodo, siamo ancora una volta
andando a guardare la matrice bambini.

180
00:09:17,770 --> 00:09:22,110
E stiamo andando a guardare indice zero
corrispondere alla A in cat.

181
00:09:22,110 --> 00:09:27,170
Allora stiamo per andare a quel nodo,
e dato che il nodo stiamo andando

182
00:09:27,170 --> 00:09:31,090
di guardare alla fine si tratta di un corrisponde
a T. E passare a quel nodo,

183
00:09:31,090 --> 00:09:35,530
Infine, abbiamo completamente guardato
attraverso la nostra parola "cat". E ora bool

184
00:09:35,530 --> 00:09:40,960
parola dovrebbe indicare se
Questa parola data è in realtà una parola.

185
00:09:40,960 --> 00:09:43,470
>> Allora, perché abbiamo bisogno che il caso speciale?

186
00:09:43,470 --> 00:09:47,700
Beh, cosa della parola "catastrofe"
è nel nostro dizionario, ma l'

187
00:09:47,700 --> 00:09:50,150
la parola "cat" non è?

188
00:09:50,150 --> 00:09:54,580
Quindi, e cercando di vedere se la parola "cat"
è nel nostro dizionario, siamo

189
00:09:54,580 --> 00:09:59,970
andando a guardare con successo attraverso
gli indici C-A-T nel nodo regione.

190
00:09:59,970 --> 00:10:04,290
Ma è solo perché la catastrofe
successo per creare nodi sulla strada

191
00:10:04,290 --> 00:10:07,190
da C-A-T, fino a
la fine della parola.

192
00:10:07,190 --> 00:10:12,020
Così bool parola è usata per indicare se
questa particolare posizione

193
00:10:12,020 --> 00:10:14,310
in realtà indica una parola.

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

195
00:10:15,140 --> 00:10:19,310
Quindi, ora che sappiamo che cosa è trie
andando a guardare come, diamo un'occhiata al

196
00:10:19,310 --> 00:10:20,730
funzione di caricare.

197
00:10:20,730 --> 00:10:24,610
Quindi il carico sta per restituire un bool
per se abbiamo successo o

198
00:10:24,610 --> 00:10:26,720
invano caricato il dizionario.

199
00:10:26,720 --> 00:10:30,460
E questo sta andando essere il dizionario
che vogliamo caricare.

200
00:10:30,460 --> 00:10:33,930
>> Quindi prima cosa siamo a fare è aprire
a quel dizionario per la lettura.

201
00:10:33,930 --> 00:10:36,160
E dobbiamo fare in modo
noi non falliremo.

202
00:10:36,160 --> 00:10:39,580
Quindi, se il dizionario non era
aperto con successo, verrà restituito

203
00:10:39,580 --> 00:10:42,400
null, nel qual caso siamo
andando a restituire false.

204
00:10:42,400 --> 00:10:47,230
Ma supponendo che successo
aperto, allora possiamo davvero leggere

205
00:10:47,230 --> 00:10:48,220
attraverso il dizionario.

206
00:10:48,220 --> 00:10:50,880
>> Quindi prima cosa che andremo a
vogliamo fare è che abbiamo questa

207
00:10:50,880 --> 00:10:52,500
radice variabile globale.

208
00:10:52,500 --> 00:10:56,190
Ora radice sta per essere un nodo *.

209
00:10:56,190 --> 00:10:59,760
E 'la parte superiore della nostra trie che siamo
sta per essere scorrendo.

210
00:10:59,760 --> 00:11:02,660
Quindi la prima cosa che stiamo andando
a voler fare è allocare

211
00:11:02,660 --> 00:11:04,140
memoria per la nostra radice.

212
00:11:04,140 --> 00:11:07,980
Si noti che stiamo usando il calloc
funzione, che è sostanzialmente la stessa

213
00:11:07,980 --> 00:11:11,500
come funzione malloc, tranne che è
garantito per restituire qualcosa che è

214
00:11:11,500 --> 00:11:13,180
completamente azzerato.

215
00:11:13,180 --> 00:11:17,290
Quindi, se abbiamo usato malloc, avremmo bisogno di
passare attraverso tutti i puntatori nella nostra

216
00:11:17,290 --> 00:11:20,160
nodo, e assicurarsi che
sono tutti nulli.

217
00:11:20,160 --> 00:11:22,710
Così calloc lo farà per noi.

218
00:11:22,710 --> 00:11:26,330
>> Ora, proprio come malloc, abbiamo bisogno di fare
Assicurarsi che la ripartizione era in realtà

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

220
00:11:27,520 --> 00:11:29,990
Se questo restituito un valore nullo, allora
necessità di chiudere o dizionario

221
00:11:29,990 --> 00:11:32,100
file e restituire false.

222
00:11:32,100 --> 00:11:36,835
Quindi, supponendo che l'assegnazione è stata
successo, stiamo andando a utilizzare un nodo *

223
00:11:36,835 --> 00:11:40,270
cursore per scorrere il nostro trie.

224
00:11:40,270 --> 00:11:43,890
Quindi, le nostre radici non cambierà mai,
ma abbiamo intenzione di usare cursore

225
00:11:43,890 --> 00:11:47,875
effettivamente andare da nodo a nodo.

226
00:11:47,875 --> 00:11:50,940
>> Quindi, in questo ciclo for stiamo leggendo
attraverso il file dizionario.

227
00:11:50,940 --> 00:11:53,670
E stiamo usando fgetc.

228
00:11:53,670 --> 00:11:56,290
Fgetc sta per afferrare un unico
carattere dal file.

229
00:11:56,290 --> 00:11:59,370
Abbiamo intenzione di continuare a catturare
personaggi mentre noi non raggiungiamo l'

230
00:11:59,370 --> 00:12:01,570
fine del file.

231
00:12:01,570 --> 00:12:03,480
>> Ci sono due casi che dobbiamo gestire.

232
00:12:03,480 --> 00:12:06,610
La prima, se il carattere
non era una nuova linea.

233
00:12:06,610 --> 00:12:10,450
Così sappiamo se si trattasse di una nuova linea, quindi
stiamo per passare ad una nuova parola.

234
00:12:10,450 --> 00:12:15,240
Ma ammesso che non era una nuova linea, quindi
qui vogliamo capire il

235
00:12:15,240 --> 00:12:18,380
Indice stiamo per indicizzare
nella matrice bambini che

236
00:12:18,380 --> 00:12:19,810
abbiamo guardato prima.

237
00:12:19,810 --> 00:12:23,880
>> Quindi, come ho detto prima, abbiamo bisogno di
caso particolare l'apostrofo.

238
00:12:23,880 --> 00:12:26,220
Notate che stiamo usando il ternario
operatore qui.

239
00:12:26,220 --> 00:12:29,580
Quindi stiamo andando a leggere questo come, se
il personaggio si legge in è stato un

240
00:12:29,580 --> 00:12:35,330
apostrofo, poi andremo a impostare
index = "ALFABETO" -1, che sarà

241
00:12:35,330 --> 00:12:37,680
essere l'indice 26.

242
00:12:37,680 --> 00:12:41,130
>> Altrimenti, se non fosse un apostrofo, ci
stiamo andando a impostare l'indice

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

244
00:12:43,760 --> 00:12:49,030
Quindi ricordatevi di ritorno da precedentemente p-set,
c - una sta per darci l'

245
00:12:49,030 --> 00:12:53,410
posizione alfabetica di C. Quindi, se
C è la lettera A, questo sarà

246
00:12:53,410 --> 00:12:54,700
darci indice zero.

247
00:12:54,700 --> 00:12:58,120
Per la lettera B, darà
noi l'indice 1, e così via.

248
00:12:58,120 --> 00:13:03,010
>> Quindi questo ci dà l'indice nella
bambini matrice che vogliamo.

249
00:13:03,010 --> 00:13:08,890
Ora, se questo indice è attualmente nullo in
i bambini, che significa che un nodo

250
00:13:08,890 --> 00:13:11,830
attualmente non esiste
da tale percorso.

251
00:13:11,830 --> 00:13:15,160
Quindi abbiamo bisogno di allocare
un nodo per quel percorso.

252
00:13:15,160 --> 00:13:16,550
Questo è quello che faremo qui.

253
00:13:16,550 --> 00:13:20,690
>> Così stiamo andando usare di nuovo la calloc
funzione, in modo che non c'è bisogno di

254
00:13:20,690 --> 00:13:22,880
azzerare tutti i puntatori.

255
00:13:22,880 --> 00:13:27,240
E abbiamo ancora bisogno di controllare
che calloc non ha fallito.

256
00:13:27,240 --> 00:13:30,700
Se calloc ha mancato, allora abbiamo bisogno
per scaricare tutto, chiudere il nostro

257
00:13:30,700 --> 00:13:32,820
dizionario, e restituire false.

258
00:13:32,820 --> 00:13:40,050
Quindi, supponendo che non ha mancato, poi
questo creerà un nuovo figlio per noi.

259
00:13:40,050 --> 00:13:41,930
E poi andremo a quel bambino.

260
00:13:41,930 --> 00:13:44,960
Il nostro cursore scorrere
fino a quel bambino.

261
00:13:44,960 --> 00:13:49,330
>> Ora, se questo non era nulla per cominciare,
poi il cursore può solo scorrere

262
00:13:49,330 --> 00:13:52,590
fino a quel bambino senza realmente
dover allocare nulla.

263
00:13:52,590 --> 00:13:56,730
Questo è il caso in cui abbiamo prima accademmo
allocare la parola "cat". E

264
00:13:56,730 --> 00:14:00,330
questo significa che quando andiamo a destinare
"Catastrofe" non abbiamo bisogno di creare

265
00:14:00,330 --> 00:14:01,680
nodi per C-A-T di nuovo.

266
00:14:01,680 --> 00:14:04,830
Essi esistono già.

267
00:14:04,830 --> 00:14:06,080
>> Che cosa è questa cosa?

268
00:14:06,080 --> 00:14:10,480
Questa è la condizione in cui c era
backslash n, dove c era una nuova linea.

269
00:14:10,480 --> 00:14:13,710
Questo significa che abbiamo successo
completato una parola.

270
00:14:13,710 --> 00:14:16,860
Ora, che cosa vogliamo fare quando ci
completato con successo una parola?

271
00:14:16,860 --> 00:14:21,100
Stiamo andando a utilizzare questo campo parola
interno del nostro nodo struct.

272
00:14:21,100 --> 00:14:23,390
Vogliamo impostare tale true.

273
00:14:23,390 --> 00:14:27,150
In modo che indica che questo nodo
indica un successo

274
00:14:27,150 --> 00:14:29,250
parola, una parola vera.

275
00:14:29,250 --> 00:14:30,940
>> Ora impostare tale true.

276
00:14:30,940 --> 00:14:35,150
Vogliamo ripristinare il nostro cursore sul punto
all'inizio del trie nuovamente.

277
00:14:35,150 --> 00:14:40,160
E, infine, incrementare nostro dizionario
dimensioni, dal momento che abbiamo trovato un altro lavoro.

278
00:14:40,160 --> 00:14:43,230
Quindi stiamo andando a continuare a farlo,
lettura carattere per carattere,

279
00:14:43,230 --> 00:14:49,150
la costruzione di nuovi nodi nel nostro trie e
Per ogni parola del dizionario, fino

280
00:14:49,150 --> 00:14:54,020
finalmente raggiungiamo C! = EOF, in cui
caso usciamo del file.

281
00:14:54,020 --> 00:14:57,050
>> Ora ci sono due casi in
che avremmo potuto colpire EOF.

282
00:14:57,050 --> 00:15:00,980
La prima è se c'è stato un errore
la lettura dal file.

283
00:15:00,980 --> 00:15:03,470
Quindi se ci fosse un errore,
bisogno di fare tipico.

284
00:15:03,470 --> 00:15:06,460
Scaricare tutto, close
il file, return false.

285
00:15:06,460 --> 00:15:09,810
Supponendo che non c'è stato un errore, che
semplicemente significa che in realtà ha colpito la fine del

286
00:15:09,810 --> 00:15:13,750
il file, nel qual caso, si chiude l'
file e restituire true quando abbiamo

287
00:15:13,750 --> 00:15:17,330
Dizionario caricato correttamente
nel nostro trie.

288
00:15:17,330 --> 00:15:20,170
>> Così ora diamo un'occhiata assegno.

289
00:15:20,170 --> 00:15:25,156
Guardando la funzione di controllo, vediamo
tale verifica sta per restituire un bool.

290
00:15:25,156 --> 00:15:29,680
Restituisce true se questa parola che è
essere passato è nella nostra trie.

291
00:15:29,680 --> 00:15:32,110
Esso restituisce false in caso contrario.

292
00:15:32,110 --> 00:15:36,050
Allora, come è possibile determinare se
questa parola è nel nostro trie?

293
00:15:36,050 --> 00:15:40,190
>> Vediamo qui che, proprio come prima,
stiamo andando a utilizzare il cursore per scorrere

294
00:15:40,190 --> 00:15:41,970
attraverso il nostro trie.

295
00:15:41,970 --> 00:15:46,600
Ora qui stiamo andando a scorrere
su tutta la nostra parola.

296
00:15:46,600 --> 00:15:50,620
Così l'iterazione sulla parola siamo passati,
stiamo andando a determinare il

297
00:15:50,620 --> 00:15:56,400
indice nella matrice bambini che
corrisponde alla staffa parola I. Quindi questo

298
00:15:56,400 --> 00:15:59,670
sta andando a guardare esattamente come
carico, dove se la parola [i]

299
00:15:59,670 --> 00:16:03,310
è un apostrofo, allora vogliamo
utilizzare l'indice "alfabeto" - 1.

300
00:16:03,310 --> 00:16:05,350
Poiché abbiamo determinato che tale
è dove stiamo andando a memorizzare

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

302
00:16:07,100 --> 00:16:11,780
>> Altrimenti andremo ad usare due parole più basso
Staffa I. Quindi ricorda che la parola può

303
00:16:11,780 --> 00:16:13,920
hanno capitalizzazione arbitraria.

304
00:16:13,920 --> 00:16:17,540
E quindi vogliamo essere sicuri che siamo
utilizzando una versione minuscola delle cose.

305
00:16:17,540 --> 00:16:21,920
E poi sottrarre da quella 'a' per volta
ancora una volta ci danno la alfabetico

306
00:16:21,920 --> 00:16:23,880
posizione di quel personaggio.

307
00:16:23,880 --> 00:16:27,680
Quindi, che sta per essere il nostro indice
nell'array bambini.

308
00:16:27,680 --> 00:16:32,420
>> E ora se questo indice nei bambini
array è null, questo significa che

309
00:16:32,420 --> 00:16:34,990
non può più continuare l'iterazione
giù la nostra trie.

310
00:16:34,990 --> 00:16:38,870
Se questo è il caso, questa parola non può
forse nella nostra trie.

311
00:16:38,870 --> 00:16:42,340
Poiché se così fosse, che sarebbe
significa che ci sarebbe un percorso

312
00:16:42,340 --> 00:16:43,510
fino a quella parola.

313
00:16:43,510 --> 00:16:45,290
E si sarebbe mai incontrare null.

314
00:16:45,290 --> 00:16:47,850
Così incontrando null, torniamo false.

315
00:16:47,850 --> 00:16:49,840
La parola non è nel dizionario.

316
00:16:49,840 --> 00:16:53,660
Se non fosse nullo, quindi siamo
intenzione di continuare l'iterazione.

317
00:16:53,660 --> 00:16:57,220
>> Così stiamo andando là fuori cursore
per puntare a quel particolare

318
00:16:57,220 --> 00:16:59,760
nodo a tale indice.

319
00:16:59,760 --> 00:17:03,150
Noi continuiamo a fare che per tutto
l'intera parola, assumendo

320
00:17:03,150 --> 00:17:03,950
non abbiamo mai colpito nulla.

321
00:17:03,950 --> 00:17:07,220
Questo significa che siamo stati in grado di ottenere attraverso
l'intera parola e trovare

322
00:17:07,220 --> 00:17:08,920
un nodo nel nostro tentativo.

323
00:17:08,920 --> 00:17:10,770
Ma non siamo ancora del tutto finito.

324
00:17:10,770 --> 00:17:12,290
>> Noi non vogliamo tornare solo true.

325
00:17:12,290 --> 00:17:14,770
Vogliamo tornare il cursore> parola.

326
00:17:14,770 --> 00:17:18,980
Da ricordare ancora una volta, è "cat" non è
nel nostro dizionario, e "catastrofe"

327
00:17:18,980 --> 00:17:22,935
è, allora avremo successo otteniamo
attraverso la parola "cat". Ma cursore

328
00:17:22,935 --> 00:17:25,760
parola sarà falso e non vero.

329
00:17:25,760 --> 00:17:30,930
Quindi torniamo cursore parola per indicare
se questo nodo è in realtà una parola.

330
00:17:30,930 --> 00:17:32,470
E questo è tutto per il controllo.

331
00:17:32,470 --> 00:17:34,250
>> Quindi diamo un'occhiata dimensioni.

332
00:17:34,250 --> 00:17:37,350
Così dimensioni sta per essere abbastanza facile
poiché, ricordate in carico, siamo

333
00:17:37,350 --> 00:17:41,430
incrementando le dimensioni del dizionario per
ogni parola che incontriamo.

334
00:17:41,430 --> 00:17:45,350
Così dimensione è solo andare a
ritorno dimensione del dizionario.

335
00:17:45,350 --> 00:17:47,390
E questo è tutto.

336
00:17:47,390 --> 00:17:50,590
>> Così, infine, abbiamo scaricato.

337
00:17:50,590 --> 00:17:55,100
Così scarico, stiamo andando a utilizzare un
funzione ricorsiva per fare realtà tutti

338
00:17:55,100 --> 00:17:56,530
del lavoro per noi.

339
00:17:56,530 --> 00:17:59,340
Quindi la nostra funzione sta per
essere invitato scaricatore.

340
00:17:59,340 --> 00:18:01,650
Che cosa sta scaricatore intenzione di fare?

341
00:18:01,650 --> 00:18:06,580
Vediamo qui che scaricatore sta per
iterare su tutti i bambini al

342
00:18:06,580 --> 00:18:08,410
questo particolare nodo.

343
00:18:08,410 --> 00:18:11,750
E se il nodo figlio non è
null, allora stiamo andando a

344
00:18:11,750 --> 00:18:13,730
scaricare il nodo figlio.

345
00:18:13,730 --> 00:18:18,010
>> Quindi questo è il modo ricorsivo scaricatela
tutti i nostri figli.

346
00:18:18,010 --> 00:18:21,080
Una volta che siamo sicuri che tutti i nostri figli
sono stati scaricati, poi abbiamo

347
00:18:21,080 --> 00:18:25,210
può liberare noi stessi, in modo
scarico noi stessi.

348
00:18:25,210 --> 00:18:29,460
Questo funzionerà in modo ricorsivo
scaricare l'intero trie.

349
00:18:29,460 --> 00:18:32,850
E poi, una volta fatto,
possiamo semplicemente restituire true.

350
00:18:32,850 --> 00:18:34,210
Unload non può fallire.

351
00:18:34,210 --> 00:18:35,710
Stiamo solo liberando le cose.

352
00:18:35,710 --> 00:18:38,870
Quindi, una volta che abbiamo finito liberando
tutto, di ritorno vero.

353
00:18:38,870 --> 00:18:40,320
E questo è tutto.

354
00:18:40,320 --> 00:18:41,080
Il mio nome è Rob.

355
00:18:41,080 --> 00:18:42,426
E questo era correttore ortografico.

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