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

2
00:00:00,530 --> 00:00:03,070
>> SPEAKER 1: Diamo
questa soluzione una prova.

3
00:00:03,070 --> 00:00:07,130
Quindi diamo un'occhiata a ciò che il nostro
Struct node sarà simile.

4
00:00:07,130 --> 00:00:11,040
Qui, vediamo che stiamo andando ad avere un
Bool Word e un nodo stella Struct

5
00:00:11,040 --> 00:00:12,990
Bambini staffa alfabeto.

6
00:00:12,990 --> 00:00:18,720
Quindi, prima cosa che si potrebbe chiedere,
perché è l'alfabeto hash definito come 27?

7
00:00:18,720 --> 00:00:22,540
Beh, ricordiamo che stiamo andando ad avere bisogno
essere la manipolazione l'apostrofo, così

8
00:00:22,540 --> 00:00:25,610
che sta per essere un po 'speciale
caso nel corso di questo programma.

9
00:00:25,610 --> 00:00:28,780
>> OK, ora, ricordare come una
Trie funziona realmente.

10
00:00:28,780 --> 00:00:33,420
Diciamo che stiamo indicizzando la parola gatti,
poi dalla radice della nostra Trie,

11
00:00:33,420 --> 00:00:36,670
stiamo andando a guardare i bambini
array, e stiamo andando a guardare il

12
00:00:36,670 --> 00:00:42,250
indice che corrisponde alla lettera
C. So che sarebbe indice due.

13
00:00:42,250 --> 00:00:46,400
Quindi dato che, che ci darà
un nuovo nodo, e poi faremo

14
00:00:46,400 --> 00:00:47,880
lavorare da quel nodo.

15
00:00:47,880 --> 00:00:51,830
>> Quindi, dato che il nodo, siamo ancora una volta
andando a guardare la matrice dei bambini,

16
00:00:51,830 --> 00:00:56,170
e stiamo andando a guardare indice zero
corrispondere alla A in cat.

17
00:00:56,170 --> 00:01:01,240
Allora stiamo per andare a quel nodo,
e dato che il nodo, stiamo andando

18
00:01:01,240 --> 00:01:05,170
a guardare l'indice che corrisponde
a T. E passare a quel nodo,

19
00:01:05,170 --> 00:01:09,590
Infine, abbiamo completamente guardato
attraverso la nostra parola Gatto, e ora Bool

20
00:01:09,590 --> 00:01:15,020
Word dovrebbe indicare se
Questa parola data è in realtà una parola.

21
00:01:15,020 --> 00:01:17,530
>> Allora, perché abbiamo bisogno che il caso speciale?

22
00:01:17,530 --> 00:01:21,680
Ebbene, che cosa se la parola catastrofe
è nel nostro dizionario, ma

23
00:01:21,680 --> 00:01:24,120
la parola gatto non è?

24
00:01:24,120 --> 00:01:29,030
Quindi, in cercando di vedere se la parola gatto è
nel nostro dizionario, stiamo andando a

25
00:01:29,030 --> 00:01:34,880
guardare con successo attraverso gli indici
C-A-T e raggiungere un nodo, ma questo è

26
00:01:34,880 --> 00:01:39,760
solo perché la catastrofe è successo a
creare nodi sulla strada da C-A-T tutti

27
00:01:39,760 --> 00:01:41,250
fino alla fine della parola.

28
00:01:41,250 --> 00:01:46,520
Così Bool Word viene usato indicare se
questa posizione particolare realtà

29
00:01:46,520 --> 00:01:48,370
indica una parola.

30
00:01:48,370 --> 00:01:52,920
>> Va bene, ora che sappiamo cosa sia una
Trie è andare a guardare come, diamo un'occhiata

31
00:01:52,920 --> 00:01:54,800
alla funzione Load.

32
00:01:54,800 --> 00:01:58,670
Così Load sta per restituire un Bool
per se abbiamo successo o

33
00:01:58,670 --> 00:02:03,020
dizionario e senza successo caricati
questo sta andando essere il dizionario

34
00:02:03,020 --> 00:02:04,520
che vogliamo caricare.

35
00:02:04,520 --> 00:02:08,310
Quindi prima cosa che andremo a fare è aprire
a quel dizionario per la lettura.

36
00:02:08,310 --> 00:02:12,060
Dobbiamo fare in modo noi non falliamo,
quindi se il dizionario non era

37
00:02:12,060 --> 00:02:15,280
aperto con successo, verrà restituito
No, in questo caso andremo a

38
00:02:15,280 --> 00:02:16,340
ritorno False.

39
00:02:16,340 --> 00:02:21,290
Ma supponendo che successo
aperto, allora possiamo davvero leggere

40
00:02:21,290 --> 00:02:22,310
attraverso il dizionario.

41
00:02:22,310 --> 00:02:24,940
>> Quindi prima cosa che andremo a
vogliamo fare è che abbiamo questa

42
00:02:24,940 --> 00:02:26,560
radice variabile globale.

43
00:02:26,560 --> 00:02:30,250
Ora, radice sta per essere una stella nodo.

44
00:02:30,250 --> 00:02:33,830
E 'la parte superiore della nostra Trie che siamo
sta per essere scorrendo.

45
00:02:33,830 --> 00:02:38,200
Quindi prima cosa che andremo a voler
fare è allocare memoria per la nostra radice.

46
00:02:38,200 --> 00:02:42,040
>> Si noti che stiamo usando il calloc
funzione, che è sostanzialmente la stessa

47
00:02:42,040 --> 00:02:45,560
come funzione Malloc, tranne che è
garantito per restituire qualcosa che è

48
00:02:45,560 --> 00:02:47,240
completamente azzerato.

49
00:02:47,240 --> 00:02:51,350
Quindi, se abbiamo usato Malloc, avremmo bisogno di
passare attraverso tutti i puntatori nella nostra

50
00:02:51,350 --> 00:02:54,220
nodo e fare in modo che
sono tutti nulli.

51
00:02:54,220 --> 00:02:56,780
Così calloc lo farà per noi.

52
00:02:56,780 --> 00:03:00,390
>> Ora, proprio come Malloc, abbiamo bisogno di fare
Assicurarsi che la ripartizione realtà

53
00:03:00,390 --> 00:03:01,580
successo.

54
00:03:01,580 --> 00:03:04,060
Se questo restituito un valore nullo, allora
necessario chiudere nostro dizionario

55
00:03:04,060 --> 00:03:06,170
file e restituire False.

56
00:03:06,170 --> 00:03:11,040
Quindi, supponendo che l'assegnazione è stata
successo, stiamo andando a utilizzare un nodo

57
00:03:11,040 --> 00:03:14,340
stella cursore per scorrere
attraverso il nostro Trie.

58
00:03:14,340 --> 00:03:17,950
Così la nostra radice è mai cambierà,
ma abbiamo intenzione di utilizzare il cursore per

59
00:03:17,950 --> 00:03:20,770
effettivamente andare da nodo a nodo.

60
00:03:20,770 --> 00:03:25,000
>> Va bene, quindi in questo ciclo For, siamo
lettura attraverso il file dizionario,

61
00:03:25,000 --> 00:03:26,965
e stiamo usando a fgetc.

62
00:03:26,965 --> 00:03:30,360
Così fgetc sta per afferrare un unico
carattere dal file.

63
00:03:30,360 --> 00:03:33,430
Abbiamo intenzione di continuare a catturare
personaggi mentre noi non raggiungiamo l'

64
00:03:33,430 --> 00:03:37,540
fine del file, quindi non ci sono
due casi dobbiamo gestire.

65
00:03:37,540 --> 00:03:41,640
La prima, se il carattere non era
nuova linea, in modo da sapere se si trattava di un nuovo

66
00:03:41,640 --> 00:03:44,480
linea, allora stiamo per
passare ad una nuova parola.

67
00:03:44,480 --> 00:03:49,300
Ma ammesso che non era una nuova linea, quindi
qui, vogliamo capire il

68
00:03:49,300 --> 00:03:52,440
Indice stiamo per indicizzare
nella matrice bambini che

69
00:03:52,440 --> 00:03:53,890
abbiamo guardato prima.

70
00:03:53,890 --> 00:03:57,950
>> Così come ho detto prima, abbiamo bisogno di
caso particolare l'apostrofo.

71
00:03:57,950 --> 00:04:01,040
Notate che stiamo usando l'operatore ternario
qui, così stiamo andando a leggere

72
00:04:01,040 --> 00:04:05,500
questo come se il personaggio si legge in è stato
un apostrofo, allora stiamo andando a

73
00:04:05,500 --> 00:04:11,740
impostare indice pari alfabeto meno
1, che sarà l'indice 26.

74
00:04:11,740 --> 00:04:15,190
Altrimenti, se non fosse un apostrofo,
allora stiamo andando a impostare l'indice

75
00:04:15,190 --> 00:04:17,820
pari a C meno.

76
00:04:17,820 --> 00:04:23,090
Quindi ricordatevi di ritorno da set p precedenti,
c meno una sta per darci l'

77
00:04:23,090 --> 00:04:27,470
posizione alfabetica di c, quindi se
c è la lettera A, questa volontà

78
00:04:27,470 --> 00:04:28,770
darci indice zero.

79
00:04:28,770 --> 00:04:32,180
Per la lettera B, darebbe
noi l'indice 1, e così via.

80
00:04:32,180 --> 00:04:37,070
>> Quindi questo ci dà l'indice nella
I bambini matrice che vogliamo.

81
00:04:37,070 --> 00:04:42,540
Ora, se questo indice è attualmente nullo in
la matrice bambini, che significa che

82
00:04:42,540 --> 00:04:47,470
un nodo attualmente non esiste da
tale percorso, quindi abbiamo bisogno di destinare una

83
00:04:47,470 --> 00:04:49,220
nodo per quel percorso.

84
00:04:49,220 --> 00:04:50,610
Questo è quello che facciamo qui.

85
00:04:50,610 --> 00:04:54,650
Quindi stiamo andando, ancora una volta, utilizzare il calloc
funzione in modo che non abbiamo

86
00:04:54,650 --> 00:05:00,130
per azzerare tutti i puntatori, e noi,
ancora una volta, è necessario verificare che calloc

87
00:05:00,130 --> 00:05:01,300
non ha mancato.

88
00:05:01,300 --> 00:05:04,760
Se calloc ha mancato, allora abbiamo bisogno
per scaricare tutto, chiudere il nostro

89
00:05:04,760 --> 00:05:06,880
dizionario, e restituire False.

90
00:05:06,880 --> 00:05:14,110
>> Quindi, supponendo che non ha mancato, poi
questo creerà un nuovo figlio per noi,

91
00:05:14,110 --> 00:05:16,000
e poi andremo a quel bambino.

92
00:05:16,000 --> 00:05:19,030
Il nostro cursore scorrere
fino a quel bambino.

93
00:05:19,030 --> 00:05:23,390
Ora, se questo non fosse nullo per cominciare,
poi il cursore può solo scorrere

94
00:05:23,390 --> 00:05:26,650
fino a quel bambino senza realmente
dover allocare nulla.

95
00:05:26,650 --> 00:05:30,790
Questo è il caso in cui abbiamo prima accademmo
di destinare la parola gatto, e

96
00:05:30,790 --> 00:05:34,390
questo significa che quando andiamo a destinare
catastrofe, non abbiamo bisogno di creare

97
00:05:34,390 --> 00:05:35,720
nodi per C-A-T di nuovo.

98
00:05:35,720 --> 00:05:37,620
Essi esistono già.

99
00:05:37,620 --> 00:05:40,140
>> OK, allora che cosa è questo altro?

100
00:05:40,140 --> 00:05:44,600
Questa è la condizione in cui c era
backslash n, dove c era una nuova linea.

101
00:05:44,600 --> 00:05:47,780
Questo significa che abbiamo successo
completato una parola.

102
00:05:47,780 --> 00:05:51,020
Ora, che cosa vogliamo fare quando si
completato con successo una parola?

103
00:05:51,020 --> 00:05:55,250
Stiamo andando a utilizzare questo campo parola
interno del nostro nodo Struct.

104
00:05:55,250 --> 00:06:00,570
>> Vogliamo impostare che a True, in modo che
indica che questo nodo indica un

105
00:06:00,570 --> 00:06:03,320
parola successo una parola vera.

106
00:06:03,320 --> 00:06:05,050
Ora, impostare tale true.

107
00:06:05,050 --> 00:06:09,210
Vogliamo ripristinare il nostro cursore sul punto
all'inizio del trie nuovamente.

108
00:06:09,210 --> 00:06:13,510
E, infine, incrementare nostro dizionario
dimensioni dato che abbiamo trovato un'altra parola.

109
00:06:13,510 --> 00:06:16,450
>> Va bene, quindi abbiamo intenzione di continuare a fare
che, leggendo nel carattere da

110
00:06:16,450 --> 00:06:21,960
carattere, la costruzione di nuovi nodi in
la nostra Trie e per ogni parola nel

111
00:06:21,960 --> 00:06:26,810
dizionario, fino a quando raggiungiamo finalmente c
uguale EOF, in questo caso, noi spezziamo

112
00:06:26,810 --> 00:06:28,100
dal file.

113
00:06:28,100 --> 00:06:31,110
Ora, ci sono due casi sotto
che avremmo potuto colpire EOF.

114
00:06:31,110 --> 00:06:35,680
La prima è se c'è stato un errore
leggendo il file, quindi se ci fosse

115
00:06:35,680 --> 00:06:39,280
un errore, dobbiamo fare il tipico
scarico tutto, chiudere il file,

116
00:06:39,280 --> 00:06:40,520
ritorno False.

117
00:06:40,520 --> 00:06:43,870
Supponendo che non c'è stato un errore, che
semplicemente significa che in realtà ha colpito la fine del

118
00:06:43,870 --> 00:06:47,820
il file, nel qual caso, si chiude l'
file e restituire True dato che

119
00:06:47,820 --> 00:06:51,010
caricato correttamente il dizionario
nel nostro Trie.

120
00:06:51,010 --> 00:06:54,240
>> Va bene, così ora cerchiamo di
Estrai.

121
00:06:54,240 --> 00:06:58,780
Guardando la funzione di controllo, vediamo
Controlla che sta per restituire un Bool.

122
00:06:58,780 --> 00:07:03,740
Restituisce True se questa parola che è
essere passato è nella nostra Trie.

123
00:07:03,740 --> 00:07:06,170
Esso restituisce False altrimenti.

124
00:07:06,170 --> 00:07:10,110
>> Quindi, come facciamo a stabilire se
questa parola è nel nostro Trie?

125
00:07:10,110 --> 00:07:14,270
Vediamo qui che, proprio come prima,
stiamo andando a utilizzare il cursore per scorrere

126
00:07:14,270 --> 00:07:16,010
attraverso il nostro Trie.

127
00:07:16,010 --> 00:07:20,650
Ora, qui, stiamo andando a scorrere
su tutta la nostra parola.

128
00:07:20,650 --> 00:07:24,680
Così l'iterazione sulla parola siamo
passato, stiamo andando a determinare il

129
00:07:24,680 --> 00:07:29,280
indice nella matrice bambini che
corrisponde alla staffa parola i.

130
00:07:29,280 --> 00:07:34,150
Quindi questo sta a guardare esattamente come
Load, dove se la staffa parola i è un

131
00:07:34,150 --> 00:07:38,110
apostrofo, poi vogliamo usare l'indice
alfabeto meno 1 perchè abbiamo determinato

132
00:07:38,110 --> 00:07:41,160
che è dove stiamo andando
memorizzare apostrofi.

133
00:07:41,160 --> 00:07:44,440
>> Altrimenti andremo a utilizzare tolower
Staffa parola i.

134
00:07:44,440 --> 00:07:48,270
Quindi ricorda che la parola può avere arbitrario
capitalizzazione, e quindi abbiamo

135
00:07:48,270 --> 00:07:51,590
vuole fare in modo che stiamo usando
una versione minuscola delle cose.

136
00:07:51,590 --> 00:07:55,300
E quindi sottrarre da questo minuscolo
una, ancora una volta, ci dia la

137
00:07:55,300 --> 00:07:57,940
posizione alfabetica
di quel personaggio.

138
00:07:57,940 --> 00:08:01,740
Quindi, che sta per essere il nostro indice
nella matrice dei bambini.

139
00:08:01,740 --> 00:08:06,480
>> E ora, se tale indice nei bambini
array è null, questo significa che

140
00:08:06,480 --> 00:08:09,050
non può più continuare l'iterazione
giù la nostra Trie.

141
00:08:09,050 --> 00:08:13,320
Se questo è il caso, questa parola non può
forse nella nostra Trie, perché se

142
00:08:13,320 --> 00:08:18,000
stati, ciò significherebbe ci sarebbe un
discesa a quella parola, e si sarebbe

143
00:08:18,000 --> 00:08:19,350
mai incontrare null.

144
00:08:19,350 --> 00:08:21,910
Così incontrando nullo, torniamo False.

145
00:08:21,910 --> 00:08:23,810
La parola non è nel dizionario.

146
00:08:23,810 --> 00:08:28,200
Se non fosse nullo, allora stiamo andando a
continua iterazione, quindi stiamo andando

147
00:08:28,200 --> 00:08:33,150
per aggiornare il nostro cursore per puntare a quella
particolare nodo a tale indice.

148
00:08:33,150 --> 00:08:36,659
>> Quindi noi continuiamo a fare che per tutto
l'intera parola.

149
00:08:36,659 --> 00:08:40,630
Supponendo che non abbiamo mai colpito nulla, il che significa
siamo stati in grado di ottenere attraverso l'intera

150
00:08:40,630 --> 00:08:44,840
mondo e trovare un nodo nella nostra Trie,
ma non siamo ancora del tutto finito.

151
00:08:44,840 --> 00:08:46,350
Noi non vogliamo tornare solo true.

152
00:08:46,350 --> 00:08:51,400
Vogliamo tornare il cursore parola errore
dal momento che, ricordiamo ancora una volta, se il gatto non è

153
00:08:51,400 --> 00:08:55,140
nel nostro dizionario e la catastrofe è,
allora avremo successo ottenere attraverso

154
00:08:55,140 --> 00:08:59,810
la parola del gatto, ma la parola del cursore
sarà falso e non vero.

155
00:08:59,810 --> 00:09:04,990
Quindi torniamo cursore parola per indicare
se questo nodo è in realtà una parola,

156
00:09:04,990 --> 00:09:06,530
e questo è tutto per il check.

157
00:09:06,530 --> 00:09:08,310
>> Quindi diamo un'occhiata Size.

158
00:09:08,310 --> 00:09:11,410
Così Dimensioni sta per essere abbastanza facile
poiché, ricordate in carico, siamo

159
00:09:11,410 --> 00:09:15,480
incrementando le dimensioni del dizionario per
ogni parola che incontriamo.

160
00:09:15,480 --> 00:09:20,820
Così Size è solo andare a ritorno
dimensione del dizionario, e questo è tutto.

161
00:09:20,820 --> 00:09:24,650
>> Va bene, quindi, infine, abbiamo Unload.

162
00:09:24,650 --> 00:09:29,050
Così Unload, stiamo andando a utilizzare un
funzione ricorsiva per fare realtà tutti

163
00:09:29,050 --> 00:09:33,390
del lavoro per noi, così la nostra funzione
sta per essere chiamato Scaricatore.

164
00:09:33,390 --> 00:09:35,830
Che cosa sta Scaricatore intenzione di fare?

165
00:09:35,830 --> 00:09:40,640
Vediamo qui che Scaricatore sta per
iterare su tutti i bambini al

166
00:09:40,640 --> 00:09:45,810
questo particolare nodo, e se il bambino
nodo non è nullo, allora stiamo andando a

167
00:09:45,810 --> 00:09:47,760
scaricare il nodo figlio.

168
00:09:47,760 --> 00:09:52,070
>> Quindi questo sta andando in modo ricorsivo
scaricare tutti i nostri figli.

169
00:09:52,070 --> 00:09:55,140
Una volta che siamo sicuri che tutti i nostri figli
sono stati scaricati, poi abbiamo

170
00:09:55,140 --> 00:09:58,830
può liberare noi stessi, in modo da scaricare noi stessi.

171
00:09:58,830 --> 00:10:04,550
Quindi questo ricorsivamente scaricare la
intero Trie, e poi una volta che è

172
00:10:04,550 --> 00:10:06,910
fatto, possiamo solo tornare Vero.

173
00:10:06,910 --> 00:10:09,770
Unload non può fallire, siamo
solo liberando le cose.

174
00:10:09,770 --> 00:10:12,985
Quindi, una volta che abbiamo finito liberando
tutto, di ritorno Vero.

175
00:10:12,985 --> 00:10:14,380
E questo è tutto.

176
00:10:14,380 --> 00:10:16,792
Il mio nome è Rob, e questo
era [incomprensibile].

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