1
00:00:00,000 --> 00:00:02,740
[Powered by Google Translate] [Paso a paso - conxunto de problemas 5]

2
00:00:02,740 --> 00:00:04,870
[Zamyla Chan - Harvard University]

3
00:00:04,870 --> 00:00:07,190
[Esta é CS50. - CS50.TV]

4
00:00:07,190 --> 00:00:10,400
>> Todo ben. Ola, todos, e ben benvida ao Paso a paso 5.

5
00:00:10,400 --> 00:00:17,400
>> Pset5 e erros de ortografía, en que imos estar facendo un corrector ortográfico.

6
00:00:17,400 --> 00:00:21,030
Corretores ortográficos son moi importantes.

7
00:00:21,030 --> 00:00:23,390
Iso xa aconteceu contigo?

8
00:00:23,390 --> 00:00:27,170
Vostede traballa moito acumulan nun papel para un enfrontamento

9
00:00:27,170 --> 00:00:33,120
e despois aínda acabar recibindo un rade brillo moi parecido cun D ou = D

10
00:00:33,120 --> 00:00:39,390
e todo porque é o spoiler en liverwurst a palabra balea de ancho.

11
00:00:39,390 --> 00:00:44,710
Si, revisión súas pemento é unha cuestión de, a impotencia máxima.

12
00:00:44,710 --> 00:00:49,140
Este é un problema que afecta viris, os alumnos viris.

13
00:00:49,140 --> 00:00:56,260
Me dixeron unha vez polo meu torturador grao Sith que eu nunca ía entrar nun bo compañeiro.

14
00:00:56,260 --> 00:01:00,250
E iso é todo o que eu sempre quixo, iso é todo o que calquera neno quere na miña idade,

15
00:01:00,250 --> 00:01:04,569
só para entrar nun bo compañeiro.

16
00:01:04,569 --> 00:01:12,720
E non só calquera compañeiro. Non Eu quería ir a un compañeiro do Marfil Legal.

17
00:01:12,720 --> 00:01:18,360
Entón, se eu non mellorar, aínda que serían os meus soños de ir a Harvard,

18
00:01:18,360 --> 00:01:22,730
Jale, a prisión ou - vostede sabe, en prisión, Nova Jersey.

19
00:01:22,730 --> 00:01:25,170
Entón, eu mesmo teño un corrector ortográfico.

20
00:01:25,170 --> 00:01:29,380
Este é un fragmento pequeno de un dos meus artistas favoritos palabra falada, Taylor Mali.

21
00:01:29,380 --> 00:01:34,630
En calquera caso, como el di, a importancia de ter un corrector ortográfico é moi importante.

22
00:01:34,630 --> 00:01:39,440
>> Entón, benvido ao Paso a paso 5, en que imos estar fala de pset5: Erros de ortografía,

23
00:01:39,440 --> 00:01:44,300
en que nós estamos facendo o noso propio corrector ortográfico.

24
00:01:44,300 --> 00:01:50,880
A caixa de ferramentas para esta semana, o código de distribución, será importante ollar para

25
00:01:50,880 --> 00:01:54,950
só para entender as diferentes funcións que o seu dicionario vai ter.

26
00:01:54,950 --> 00:02:01,500
En realidade, estamos indo a ter varios ficheiros. C que, xuntos, forman a nosa pset.

27
00:02:01,500 --> 00:02:05,420
E así mirando a través de diferentes aspectos, aínda que non estamos realmente edición

28
00:02:05,420 --> 00:02:10,770
un dos arquivos, speller.c, sabendo como funciona con relación a dictionary.c,

29
00:02:10,770 --> 00:02:14,100
que iremos escribir, vai ser moi importante.

30
00:02:14,100 --> 00:02:16,970
A especificación pset tamén contén unha serie de información útil

31
00:02:16,970 --> 00:02:21,360
en termos de cousas que pode asumir, regras e cousas así,

32
00:02:21,360 --> 00:02:24,710
que non deixe de ler a especificación pset coidadosamente para suxestións.

33
00:02:24,710 --> 00:02:29,310
E cando está en dúbida dunha regra ou algo así, entón sempre consultar a especificación pset

34
00:02:29,310 --> 00:02:31,550
ou discutir.

35
00:02:31,550 --> 00:02:34,060
Este pset vai dependen fortemente de punteiros,

36
00:02:34,060 --> 00:02:37,890
por iso queremos estar seguro de que entendemos a diferenza entre estrelas engadir

37
00:02:37,890 --> 00:02:41,680
diante do nome do punteiro e ampersands, como para liberalos, etc

38
00:02:41,680 --> 00:02:47,550
Entón, ser un mestre de punteiros vai ser moi útil neste conxunto de problemas.

39
00:02:47,550 --> 00:02:50,460
Nós imos ollar para as listas ligadas un pouco máis,

40
00:02:50,460 --> 00:02:57,790
onde temos elementos que chamamos nós, que posúen tanto un valor, así como un enlace

41
00:02:57,790 --> 00:03:02,520
para o próximo nó, e así, esencialmente, ligando elementos diferentes un despois do outro.

42
00:03:02,520 --> 00:03:07,190
Existen algunhas opcións diferentes de implementar o seu dicionario real.

43
00:03:07,190 --> 00:03:13,150
Nós imos ollar para dous métodos principais, o que é táboas de hash e entón intenta.

44
00:03:13,150 --> 00:03:17,660
En ambos os, implica algún tipo de noción dunha lista ligada

45
00:03:17,660 --> 00:03:20,790
onde teñen elementos conectados un ao outro.

46
00:03:20,790 --> 00:03:25,640
E así imos ollar sobre como pode ser capaz de operar en torno a listas ligadas,

47
00:03:25,640 --> 00:03:29,680
crealas, navegar en termos de como, por exemplo, inserir un nó que

48
00:03:29,680 --> 00:03:32,760
ou libre de todos os nós, ben.

49
00:03:32,760 --> 00:03:34,740
En termos de nós liberadora, que é realmente importante

50
00:03:34,740 --> 00:03:37,700
que sempre que a memoria malloc, despois nos liberar.

51
00:03:37,700 --> 00:03:42,910
Entón, nós queremos estar seguro de que ningún punteiro vai unfreed, que non temos ningunha derrames de memoria.

52
00:03:42,910 --> 00:03:48,330
Nós imos presentar unha ferramenta chamada Valgrind que executa o programa

53
00:03:48,330 --> 00:03:52,260
e comprobar toda a memoria que alocou é entón liberado.

54
00:03:52,260 --> 00:03:59,080
O seu pset só é completa cando funciona e ten a funcionalidade completa,

55
00:03:59,080 --> 00:04:03,990
pero tamén, Valgrind lle di que non atopou ningún escape de memoria.

56
00:04:03,990 --> 00:04:06,690
Finalmente, a este pset, realmente quero salientar -

57
00:04:06,690 --> 00:04:11,360
Quero dicir, como de costume, eu son sempre un defensor do uso de papel e pluma para os seus conxuntos de problemas,

58
00:04:11,360 --> 00:04:14,840
pero a este, eu creo que pluma e papel vai ser especialmente importante

59
00:04:14,840 --> 00:04:19,000
cando quere ser deseño frechas para as cousas e entender como as cousas funcionan.

60
00:04:19,000 --> 00:04:24,440
Entón, en definitiva tentar usar pluma e papel para deseñar as cousas antes de que comece a codificación

61
00:04:24,440 --> 00:04:26,970
porque podería estar un pouco confuso.

62
00:04:26,970 --> 00:04:30,700
>> En primeiro lugar, imos entrar en listas ligadas un pouco.

63
00:04:30,700 --> 00:04:35,510
Listas ligadas consisten de nós, onde cada nodo ten un valor asociado a ela,

64
00:04:35,510 --> 00:04:39,810
, Así como un enlace ao seguinte nodo tras el.

65
00:04:39,810 --> 00:04:43,680
Un par de cousas importantes coas listas ligadas son de que necesitamos nos lembrar

66
00:04:43,680 --> 00:04:48,810
onde o noso primeiro nodo é, a continuación, unha vez que sabemos que o primeiro en se,

67
00:04:48,810 --> 00:04:52,990
Desta forma, podemos acceder ao nodo que os primeiros puntos de nó para

68
00:04:52,990 --> 00:04:55,850
e, a continuación, a outra despois diso e un despois diso.

69
00:04:55,850 --> 00:05:00,340
E entón o último elemento na súa lista conexionada e punteiro que no

70
00:05:00,340 --> 00:05:02,340
sempre vai apuntar a NULL.

71
00:05:02,340 --> 00:05:08,230
Cando un nodo puntos para NULL, entón vostede sabe que chegou ao final da lista,

72
00:05:08,230 --> 00:05:12,320
que ese nodo é o último, que non hai nada despois diso.

73
00:05:12,320 --> 00:05:16,970
Aquí neste esquema, ve que as frechas son os punteiros,

74
00:05:16,970 --> 00:05:20,290
ea sección de azul é onde o valor é almacenado,

75
00:05:20,290 --> 00:05:24,420
e, a continuación, a caixa vermella co punteiro para el é punteiro do nodo

76
00:05:24,420 --> 00:05:27,050
apuntando para o próximo nó tras el.

77
00:05:27,050 --> 00:05:33,730
E así que ve aquí, o nó D ía apuntar para NULL porque é o último elemento da lista.

78
00:05:33,730 --> 00:05:38,240
>> Imos ver como podemos definir unha estrutura para un nó.

79
00:05:38,240 --> 00:05:40,130
E xa que queremos ter varios nós,

80
00:05:40,130 --> 00:05:43,180
iso vai converterse nun typedef struct

81
00:05:43,180 --> 00:05:46,870
en que nós imos ter varias instancias diferentes de nós.

82
00:05:46,870 --> 00:05:50,850
E, así, define-lo como un novo tipo de datos.

83
00:05:50,850 --> 00:05:53,630
Aquí temos un nó typedef struct.

84
00:05:53,630 --> 00:05:56,160
Neste exemplo, estamos a tratar con nós enteiros,

85
00:05:56,160 --> 00:06:00,490
por iso temos un valor enteiro chamado e despois temos outro punteiro,

86
00:06:00,490 --> 00:06:07,390
e, neste caso, é un punteiro para un nó, por iso temos un nó struct * chamada seguinte.

87
00:06:07,390 --> 00:06:09,520
E entón nós estamos chamando este nodo cousa toda.

88
00:06:09,520 --> 00:06:11,110
Asegúrese de que siga esta sintaxe.

89
00:06:11,110 --> 00:06:17,940
Teña en conta que o no está realmente enriba referenciado, así como a continuación das claves.

90
00:06:17,940 --> 00:06:23,400
Entón, para manter o control de onde o meu primeiro nodo está na lista vinculada,

91
00:06:23,400 --> 00:06:29,390
entón ter un punteiro no chamado cabeza, e eu malloc espazo suficiente para o tamaño dun nodo.

92
00:06:29,390 --> 00:06:36,240
Teña en conta, sen embargo, que a cabeza é realmente un punteiro nó en oposición a un nodo propiamente dito.

93
00:06:36,240 --> 00:06:40,130
Así, a cabeza, en realidade, non contén ningún valor,

94
00:06:40,130 --> 00:06:45,590
el só apunta a que o primeiro nó na miña lista conexionada e.

95
00:06:55,080 --> 00:06:58,340
>> Para ter unha noción mellor de listas ligadas, pois é moi importante

96
00:06:58,340 --> 00:07:02,220
para acompañar a certeza de que manter a cadea,

97
00:07:02,220 --> 00:07:09,990
Eu gusto de pensar niso como persoas nunha liña de man,

98
00:07:09,990 --> 00:07:14,330
onde cada persoa está de mans dadas co próximo.

99
00:07:14,330 --> 00:07:18,350
Vostede non pode ver neste deseño, pero, basicamente, están apuntando para a seguinte persoa

100
00:07:18,350 --> 00:07:23,760
que está na súa cadea.

101
00:07:23,760 --> 00:07:29,270
E por iso, se quere percorrer unha lista ligada onde esas persoas -

102
00:07:29,270 --> 00:07:32,830
Imaxina todas esas persoas teñen valores asociados a eles

103
00:07:32,830 --> 00:07:36,590
e tamén apuntar á seguinte persoa na liña -

104
00:07:36,590 --> 00:07:40,810
se quere percorrer a lista ligada, por exemplo, para editar os valores

105
00:07:40,810 --> 00:07:42,830
ou buscar por un valor ou algo así,

106
00:07:42,830 --> 00:07:48,270
entón vai querer ter un punteiro para a persoa específica.

107
00:07:48,270 --> 00:07:52,670
Entón, nós imos ter un punteiro de datos no tipo.

108
00:07:52,670 --> 00:07:55,580
Para este exemplo, imos chamalo cursor.

109
00:07:55,580 --> 00:07:59,630
Outra forma común de nomear este sería iterador ou algo parecido

110
00:07:59,630 --> 00:08:05,130
porque está interactuando sobre e realmente mover o nodo que está apuntando.

111
00:08:05,130 --> 00:08:14,410
Iso aquí vai ser o noso cursor.

112
00:08:14,410 --> 00:08:20,180
O noso primeiro cursor apuntar para o primeiro elemento na nosa lista.

113
00:08:20,180 --> 00:08:26,910
E entón o que queremos facer é que sería basicamente ser continuar o cursor,

114
00:08:26,910 --> 00:08:29,130
movéndose de lado a lado.

115
00:08:29,130 --> 00:08:33,409
Neste caso, queremos mover para o próximo elemento da lista.

116
00:08:33,409 --> 00:08:38,480
Con matrices, o que nós facemos é só diría que aumentar o índice de 1.

117
00:08:38,480 --> 00:08:46,020
Neste caso, o que necesitamos facer é realmente atopar o que esta persoa persoa actual está a apuntar,

118
00:08:46,020 --> 00:08:48,930
e que vai ser o seguinte valor.

119
00:08:48,930 --> 00:08:53,230
Entón, se o cursor é só un punteiro no, entón o que queremos facer

120
00:08:53,230 --> 00:08:56,320
é que queremos chegar ao valor que o cursor está a apuntar.

121
00:08:56,320 --> 00:09:01,350
Queremos chegar a ese nó e, a continuación, unha vez que estamos nese nó, atopar onde está a apuntar.

122
00:09:01,350 --> 00:09:05,820
Para chegar ao nodo real que o cursor está a apuntar,

123
00:09:05,820 --> 00:09:13,160
Normalmente indican-lo (cursor *).

124
00:09:13,160 --> 00:09:19,160
Que lle daría o no real que o cursor está a apuntar.

125
00:09:19,160 --> 00:09:21,730
E despois diso, o que queremos facer é que queremos para acceder

126
00:09:21,730 --> 00:09:25,680
calquera que sexa o valor próximo ao nó é.

127
00:09:25,680 --> 00:09:32,820
Para iso, para acceder os valores dentro da estructura, temos operador punto.

128
00:09:32,820 --> 00:09:39,530
Entón sería (cursor *). Seguinte.

129
00:09:39,530 --> 00:09:44,840
Pero iso é un pouco confuso en canto ao que os soportes arredor do cursor *,

130
00:09:44,840 --> 00:09:56,800
e así imos substituír esa declaración enteira con cursor->.

131
00:09:56,800 --> 00:10:02,700
Este é un guión e un sinal máis do que, polo que facendo unha frecha.

132
00:10:02,700 --> 00:10:05,840
cursor-> seguinte.

133
00:10:05,840 --> 00:10:12,390
Que realmente vai che dar o no que os puntos cursor. Este valor é do seguinte.

134
00:10:12,390 --> 00:10:16,790
Entón, en vez de ter a estrela eo punto, está substituíndo iso cunha frecha.

135
00:10:16,790 --> 00:10:24,820
Teña moito coidado para asegurarse de que Vostede tente utilizar esa sintaxe.

136
00:10:33,550 --> 00:10:37,620
>> Agora que temos o noso cursor, se quere acceder ao valor,

137
00:10:37,620 --> 00:10:40,450
antes, tivemos cursor-> seguinte,

138
00:10:40,450 --> 00:10:46,260
pero para acceder ao valor no no que o cursor está a apuntar, nós simplemente dicir

139
00:10:46,260 --> 00:10:48,070
node>-valor.

140
00:10:48,070 --> 00:10:53,600
De alí, é o tipo de datos que definimos os valores e os nós a seren.

141
00:10:53,600 --> 00:10:59,620
Se é un nodo int e cursor-> valor é só vai ser un enteiro.

142
00:10:59,620 --> 00:11:04,870
Entón, podemos facer operacións en que comprobar igualdades, asignar valores diferentes, etc

143
00:11:04,870 --> 00:11:11,090
Entón o que quere facer, se quere mover o cursor á seguinte persoa,

144
00:11:11,090 --> 00:11:15,270
realmente cambiar o valor do cursor.

145
00:11:15,270 --> 00:11:19,340
Dende cursor é un punteiro no, vostede cambiar o enderezo do punteiro real

146
00:11:19,340 --> 00:11:23,890
ao enderezo do próximo nó na súa lista.

147
00:11:23,890 --> 00:11:28,930
Este é só un código, onde podes interactuar.

148
00:11:28,930 --> 00:11:31,230
Onde eu teño o comentario facer algo,

149
00:11:31,230 --> 00:11:33,850
que é onde está indo probablemente para acceder o valor

150
00:11:33,850 --> 00:11:37,850
ou facer algo que ver con ese nó específico.

151
00:11:37,850 --> 00:11:43,050
Para inicia-lo fóra, eu digo que o meu cursor inicialmente

152
00:11:43,050 --> 00:11:48,430
vai para apuntar para o primeiro elemento na lista encadeada.

153
00:11:48,430 --> 00:11:52,910
E así alí na fronte, eu define-lo como o xefe do nodo.

154
00:11:52,910 --> 00:11:57,610
>> Como mencionei antes, liberando é realmente importante.

155
00:11:57,610 --> 00:12:02,440
Quere estar seguro de que liberar todos os elementos da lista unha vez que rematou con el.

156
00:12:02,440 --> 00:12:04,940
Cando non ten que facer referencia a calquera destes punteiros máis,

157
00:12:04,940 --> 00:12:10,620
quere ter seguro de que liberar todos os punteiros.

158
00:12:10,620 --> 00:12:14,460
Pero quere ter moito coidado aquí que quere evitar calquera fuga de memoria.

159
00:12:14,460 --> 00:12:25,080
Se unha persoa libre prematuramente, despois de todos os punteiros que os puntos de nó para

160
00:12:25,080 --> 00:12:26,900
van ser perdidos.

161
00:12:26,900 --> 00:12:32,070
Volvendo ao exemplo persoa para facelo un pouco máis altas apostas,

162
00:12:32,070 --> 00:12:49,600
imos ter estas persoas, só que neste caso están paira sobre un lago con un monstro.

163
00:12:49,600 --> 00:12:53,200
Queremos estar seguro de que cada vez que liberar, non perdemos

164
00:12:53,200 --> 00:12:58,920
e deixar de ir todos os nós antes de que realmente os liberou.

165
00:12:58,920 --> 00:13:05,730
Por exemplo, se fose simplemente conectar de balde sobre este cara aquí,

166
00:13:05,730 --> 00:13:15,350
entón, sería liberado, pero despois todos eses caras, entón, ser perdido

167
00:13:15,350 --> 00:13:18,450
e que iría durmir e caer.

168
00:13:18,450 --> 00:13:24,900
Entón, nós queremos estar seguro de que en vez diso, queremos manter un vínculo co resto.

169
00:13:37,630 --> 00:13:42,480
A nosa cabeza punteiro, que apunta para o primeiro elemento da lista.

170
00:13:42,480 --> 00:13:49,990
É como unha especie de corda de ancoraxe primeira persoa.

171
00:13:52,870 --> 00:13:57,470
O que pode querer facer cando liberar unha lista ter -

172
00:13:57,470 --> 00:14:04,520
Se queres liberar o primeiro elemento primeiro, entón vostede pode ter un punteiro temporal

173
00:14:04,520 --> 00:14:07,370
que apunta a que o primeiro elemento é.

174
00:14:07,370 --> 00:14:11,420
Entón tes o punteiro temporal apuntando aquí.

175
00:14:11,420 --> 00:14:15,840
Desta forma, temos un soto do primeiro nodo.

176
00:14:15,840 --> 00:14:18,930
E entón, xa que sabemos que o primeiro en vai ser liberada,

177
00:14:18,930 --> 00:14:24,890
entón podemos pasar esta corda, esa referencia, a nosa cabeza,

178
00:14:24,890 --> 00:14:31,930
para realmente apuntar para o que quere que o primeiro está a apuntar.

179
00:14:31,930 --> 00:14:38,760
Polo tanto, esta cabeza realmente apunta para o segundo elemento agora.

180
00:14:38,760 --> 00:14:43,980
Agora estamos autorizados a liberar o que está almacenado na temperatura,

181
00:14:43,980 --> 00:14:53,360
e así podemos borrar que sen el poñer en perigo os outros nós na nosa lista.

182
00:14:54,140 --> 00:15:05,020
Outra forma que podería facer isto podería ser

183
00:15:05,020 --> 00:15:08,650
cada vez que acaba de liberar o último elemento da lista

184
00:15:08,650 --> 00:15:11,010
porque son a garantía de non ser apuntado para calquera cousa.

185
00:15:11,010 --> 00:15:15,570
Entón, vostede podería simplemente liberar este, entón libre este, a continuación, un agasallo gratuíto.

186
00:15:15,570 --> 00:15:21,900
Isto definitivamente funciona, pero é un pouco máis lento, porque pola natureza das listas ligadas,

187
00:15:21,900 --> 00:15:24,670
non podemos simplemente ir inmediatamente para a última.

188
00:15:24,670 --> 00:15:28,030
Debemos percorrer cada elemento da lista encadeada

189
00:15:28,030 --> 00:15:31,020
e comproba que se está a apuntar cara NULL, comprobar cada vez,

190
00:15:31,020 --> 00:15:33,780
e, a continuación, unha vez que chegar ao final, entón libre diso.

191
00:15:33,780 --> 00:15:40,270
Se fose facer ese proceso, sería realmente comprobando aquí,

192
00:15:40,270 --> 00:15:44,190
comprobando aquí, a continuación, comprobando aquí, liberando-o,

193
00:15:44,190 --> 00:15:47,470
a continuación, volver, comprobando aquí, alomenos aquí, liberando-o,

194
00:15:47,470 --> 00:15:49,660
comprobando aquí, e logo liberalo la.

195
00:15:49,660 --> 00:15:52,880
Isto leva un pouco máis tempo. Si

196
00:15:52,880 --> 00:15:59,060
>> [Alumno] Sería posíbel facer unha lista ligada que almacena un punteiro de saída para o fin?

197
00:15:59,060 --> 00:16:01,320
Que ía ser posible.

198
00:16:01,320 --> 00:16:08,340
Para repetir a pregunta, é posible ter unha estrutura de lista ligada

199
00:16:08,340 --> 00:16:12,490
de tal forma que ten un punteiro que apunta para o fin da lista ligada?

200
00:16:12,490 --> 00:16:18,090
Eu diría que é posible, e cada vez que introduza algo na súa lista ligada

201
00:16:18,090 --> 00:16:21,470
que tería que actualizar este punteiro e cousas así.

202
00:16:21,470 --> 00:16:26,640
Vostede tería unha cola * no, por exemplo.

203
00:16:26,640 --> 00:16:29,840
Pero cando se está aplicando este recurso, ten que pensar no trade-offs,

204
00:16:29,840 --> 00:16:32,700
gusto de cantas veces eu vou ser iteração sobre iso,

205
00:16:32,700 --> 00:16:36,100
quão difícil é que vai ser a de manter o control da cola, así como a cabeza

206
00:16:36,100 --> 00:16:38,400
así como a miña iterador, e cousas así.

207
00:16:40,730 --> 00:16:42,480
Será que -? >> [Estudante] Yeah.

208
00:16:42,480 --> 00:16:48,270
É posible, pero en termos de decisións de proxecto, ten que pesar as opcións.

209
00:16:53,850 --> 00:17:01,090
>> Aquí está un esqueleto de código que lle permitiría liberar cada elemento nunha lista ligada.

210
00:17:01,090 --> 00:17:05,460
Unha vez máis, dende que eu estou iterando unha lista ligada, eu vou querer ter algún tipo de cursor

211
00:17:05,460 --> 00:17:08,670
ou iterador.

212
00:17:08,670 --> 00:17:14,640
Estamos repetindo ata que o cursor está NULL.

213
00:17:14,640 --> 00:17:17,640
Non quere repetir cando o cursor é NULL

214
00:17:17,640 --> 00:17:20,579
porque iso significa que non hai nada na lista.

215
00:17:20,579 --> 00:17:25,069
Entón aquí fago un nó temporal *

216
00:17:25,069 --> 00:17:29,610
apuntando para o que eu estou pensando é o primeiro da miña lista,

217
00:17:29,610 --> 00:17:35,340
e despois eu paso o meu cursor cara adiante e despois un libre que tiña no almacenamento temporal.

218
00:17:38,460 --> 00:17:43,650
>> Agora chegamos ao inserir en listas ligadas.

219
00:18:00,200 --> 00:18:09,660
Eu teño tres nós na miña lista encadeada, e imos co caso sinxelo

220
00:18:09,660 --> 00:18:18,970
onde queremos inserir outro no ao final da lista ligada.

221
00:18:18,970 --> 00:18:25,980
Para iso, todo o que quere facer é que sería atravesar

222
00:18:25,980 --> 00:18:32,100
para atopar onde o fin actual da lista ligada é, entón calquera nodo apunta a NULL -

223
00:18:32,100 --> 00:18:33,850
iso é un agasallo -

224
00:18:33,850 --> 00:18:37,260
e despois din que, en realidade, este non vai ser o último nó;

225
00:18:37,260 --> 00:18:39,830
estamos, en realidade, vai ter outro.

226
00:18:39,830 --> 00:18:46,260
Entón teriamos este punto unha corrente de todo o que está inserindo.

227
00:18:46,260 --> 00:18:50,080
Entón, agora esta persoa vermello aquí se fai o último nó na lista ligada.

228
00:18:50,080 --> 00:18:56,080
E así a característica do último nodo na lista vinculada é que apunta a NULL.

229
00:18:56,080 --> 00:19:09,380
Entón, o que teriamos que facer é definir esa cara punteiro vermello para NULL. Alí.

230
00:19:09,380 --> 00:19:25,370
>> Pero o que se quería introducir un nó entre a segunda e terceira?

231
00:19:25,370 --> 00:19:28,960
Que non é tan sinxelo, porque queremos estar seguro de

232
00:19:28,960 --> 00:19:34,290
que non deixe ir de calquera nodo na lista ligada.

233
00:19:34,290 --> 00:19:43,450
O que temos que facer é estar seguro de que nós ancorar cada un.

234
00:19:43,450 --> 00:19:49,900
Por exemplo, imos chamar iso de un segundo.

235
00:19:49,900 --> 00:19:54,390
Se dixo que o segundo apunta agora a esta nova

236
00:19:54,390 --> 00:20:02,520
e acaba de facer un punteiro alí, entón, que resultaría nun cara sendo perdida

237
00:20:02,520 --> 00:20:07,830
porque non hai ningunha conexión con el.

238
00:20:07,830 --> 00:20:18,970
En vez diso - Vou chamar iso de novo. Sentímolo miñas habilidades artísticas.

239
00:20:18,970 --> 00:20:26,570
Sabemos que non podemos simplemente chamar directamente dous para o novo.

240
00:20:26,570 --> 00:20:30,480
Temos que asegurarse de que soster a última.

241
00:20:30,480 --> 00:20:39,200
O que pode querer facer é ter un punteiro temporal

242
00:20:39,200 --> 00:20:42,650
para o elemento que vai ser anexado en.

243
00:20:42,650 --> 00:20:45,140
Entón temos un punteiro temporal alí.

244
00:20:45,140 --> 00:20:50,780
Desde que sabemos que este terceiro está sometido,

245
00:20:50,780 --> 00:20:53,680
2 pode agora chamar a nosa nova.

246
00:20:53,680 --> 00:20:57,490
E se este cara nova vermello vai ser entre 2 e 3,

247
00:20:57,490 --> 00:21:05,550
Entón o que é punteiro que cara vai apuntar? >> [Alumno] Temp.

248
00:21:05,550 --> 00:21:07,490
Temp. Si

249
00:21:07,490 --> 00:21:15,430
Entón próximo valor este cara vermella que vai ser temporal.

250
00:21:26,090 --> 00:21:33,010
Cando está inserindo en listas ligadas, vimos que podiamos

251
00:21:33,010 --> 00:21:38,260
facilmente engadir algo ao final, creando unha matriz temporal,

252
00:21:38,260 --> 00:21:42,850
ou se quería engadir algo para o medio da nosa matriz,

253
00:21:42,850 --> 00:21:46,810
a continuación, sería preciso un pouco máis de andar por aí.

254
00:21:46,810 --> 00:21:50,240
Se queres, por exemplo, ten unha lista ordenada vinculado,

255
00:21:50,240 --> 00:21:54,880
entón tes que tipo de pesar os custos e os beneficios que

256
00:21:54,880 --> 00:21:59,720
porque se quere ter un array ordenado, o que significa que cada vez que insira-lo,

257
00:21:59,720 --> 00:22:01,630
que vai levar un pouco máis.

258
00:22:01,630 --> 00:22:05,500
Con todo, se quere, máis tarde, como veremos, queremos,

259
00:22:05,500 --> 00:22:10,280
busca a través dunha lista ligada, entón pode ser máis doado se sabe que todo está en orde.

260
00:22:10,280 --> 00:22:15,340
Entón podes querer pesar os custos e beneficios que.

261
00:22:20,150 --> 00:22:27,740
>> Outra forma de introducir nunha lista ligada é introducir no inicio dunha lista.

262
00:22:27,740 --> 00:22:34,700
Se traçarmos a nosa referencia aquí - esta é a nosa cabeza -

263
00:22:34,700 --> 00:22:40,960
e despois que esas persoas ligadas a el,

264
00:22:40,960 --> 00:22:48,460
e, a continuación, temos un novo nodo a ser inserido no inicio,

265
00:22:48,460 --> 00:22:52,590
a continuación, o que podería queremos facer?

266
00:22:55,220 --> 00:23:03,580
O que sería malo con só dicindo que quero obrigar o vermello ao azul,

267
00:23:03,580 --> 00:23:05,790
porque ese é o primeiro?

268
00:23:05,790 --> 00:23:08,570
O que sucedería aquí?

269
00:23:08,570 --> 00:23:12,130
Todos estes tres se perdese.

270
00:23:12,130 --> 00:23:14,140
Entón nós non queremos facelo.

271
00:23:14,140 --> 00:23:21,430
Unha vez máis, nós aprenden que temos que ter algún tipo de punteiro temporal.

272
00:23:21,430 --> 00:23:34,470
Imos optar por ter un punto temporal para este cara.

273
00:23:34,470 --> 00:23:39,640
Entón, podemos ter o punto de un azul para a temporal

274
00:23:39,640 --> 00:23:43,240
e, a continuación, o punto vermello ao azul.

275
00:23:43,240 --> 00:23:47,830
A razón pola que eu estou usando o pobo aquí é porque realmente queremos ver

276
00:23:47,830 --> 00:23:53,180
seguro coas persoas e estar seguro de que temos unha ligazón a eles

277
00:23:53,180 --> 00:23:57,590
antes de deixar de ir a outra man, ou algo así.

278
00:24:05,630 --> 00:24:10,650
>> Agora que temos un sentido de listas ligadas - como podemos crear unha lista encadeada

279
00:24:10,650 --> 00:24:15,090
e crear as estruturas para que consiste na definición de tipo para un nodo

280
00:24:15,090 --> 00:24:19,060
e, a continuación, asegurándose de que temos un punteiro para a cabeza da lista ligada -

281
00:24:19,060 --> 00:24:23,210
Unha vez que temos iso e sabemos como atravesar unha matriz,

282
00:24:23,210 --> 00:24:28,200
acceder varios elementos, sabemos como inserir e sabemos como liberalos,

283
00:24:28,200 --> 00:24:30,260
entón podemos entrar en erros ortográficos.

284
00:24:30,260 --> 00:24:38,150
Como de costume, temos unha sección de preguntas que se usou para operar con listas ligadas

285
00:24:38,150 --> 00:24:41,750
e estruturas diferentes, como colas e pilas.

286
00:24:41,750 --> 00:24:46,000
Entón, podemos mover-se en erros ortográficos.

287
00:24:46,000 --> 00:24:55,170
>> Erros ten no código de distribución un par de arquivos de importancia.

288
00:24:55,170 --> 00:24:58,850
Primeiro notamos que temos ese Makefile aquí,

289
00:24:58,850 --> 00:25:03,040
que non temos realmente visto antes.

290
00:25:03,040 --> 00:25:10,090
Se mirase dentro do cartafol pset5, entender que ten un. Arquivo h,

291
00:25:10,090 --> 00:25:12,530
entón tes dous arquivos. c.

292
00:25:12,530 --> 00:25:18,920
O que isto fai é Makefile antes, teriamos só escriba make e despois o nome do programa

293
00:25:18,920 --> 00:25:25,550
e entón veriamos todos estes argumentos e bandeiras pasado para o compilador.

294
00:25:25,550 --> 00:25:30,580
O que o Makefile fai é nos permite compilar varios arquivos dunha soa vez

295
00:25:30,580 --> 00:25:34,650
e pasar as bandeiras que queremos.

296
00:25:34,650 --> 00:25:41,300
Aquí vemos só hai un ficheiro de cabeceira aquí.

297
00:25:41,300 --> 00:25:43,730
Entón en realidade temos dous arquivos de orixe.

298
00:25:43,730 --> 00:25:47,520
Temos speller.c e dictionary.c.

299
00:25:47,520 --> 00:25:54,560
Estás convidado a editar o Makefile se o desexa.

300
00:25:54,560 --> 00:26:03,310
Teña en conta que aquí se escribe limpo, entón o que fai é realmente eliminar calquera cousa

301
00:26:03,310 --> 00:26:06,340
que é o núcleo.

302
00:26:06,340 --> 00:26:09,190
Se ten un fallo de segmento, basicamente consegue un core dump.

303
00:26:09,190 --> 00:26:13,260
Polo tanto, este ficheiro de pouco feo aparecerá no seu directorio chamado núcleo.

304
00:26:13,260 --> 00:26:16,310
Vai querer eliminar o para facelo limpo.

305
00:26:16,310 --> 00:26:20,940
El elimina todos os ficheiros exe e. Arquivos o.

306
00:26:27,900 --> 00:26:30,220
>> Imos dar un ollo a dictionary.h.

307
00:26:30,220 --> 00:26:34,410
Este di que ela declárase a funcionalidade dun dicionario.

308
00:26:34,410 --> 00:26:39,530
Temos unha lonxitude máxima para calquera palabra no dicionario.

309
00:26:39,530 --> 00:26:45,130
Dicimos que esta vai ser a palabra máis longa posible. É de lonxitude 45.

310
00:26:45,130 --> 00:26:48,900
Entón, nós non imos ter todas as palabras que exceden ese lonxitude.

311
00:26:48,900 --> 00:26:50,980
Aquí só temos os prototipos de función.

312
00:26:50,980 --> 00:26:55,290
Non temos a implementación real porque é iso que imos facer con esta pset.

313
00:26:55,290 --> 00:26:59,940
Pero o que iso fai é xa que estamos lidando con arquivos maiores aquí

314
00:26:59,940 --> 00:27:06,650
e funcionalidade nunha escala maior, é útil ter un. arquivo h

315
00:27:06,650 --> 00:27:11,290
para que outra persoa lendo ou usando o seu código pode entender o que está a suceder.

316
00:27:11,290 --> 00:27:17,910
E quizais eles queren aplicar intenta fixo táboas de hash ou viceversa.

317
00:27:17,910 --> 00:27:21,850
Entón eles din que a miña función de carga,

318
00:27:21,850 --> 00:27:26,950
a implementación real vai ser diferente, pero este prototipo non vai cambiar.

319
00:27:26,950 --> 00:27:33,280
Aquí comprobar que retorna certo se unha determinada palabra está no dicionario.

320
00:27:33,280 --> 00:27:39,800
Entón, temos de carga, que basicamente leva un ficheiro de dicionario

321
00:27:39,800 --> 00:27:44,360
e leva-lo en algunha estrutura de datos.

322
00:27:44,360 --> 00:27:47,500
Temos tamaño, que, cando chamado, devolve o tamaño do seu dicionario,

323
00:27:47,500 --> 00:27:50,310
cantas palabras son almacenados,

324
00:27:50,310 --> 00:27:54,390
e descargar, o que libera toda a memoria que pode tomar

325
00:27:54,390 --> 00:27:57,900
ao mesmo tempo que o seu dicionario.

326
00:28:01,070 --> 00:28:03,590
>> Imos dar un ollo a dictionary.c.

327
00:28:03,590 --> 00:28:10,490
Vemos que é moi parecido dictionary.h, só que agora só ten todas esas todos nel.

328
00:28:10,490 --> 00:28:16,980
E así que é o seu traballo. Finalmente, vai ser o recheo de speller.c con todo este código.

329
00:28:16,980 --> 00:28:21,540
Dictionary.c, cando se executa, non é realmente vai facer algo,

330
00:28:21,540 --> 00:28:29,590
por iso ollar para speller.c para ver a implementación real do corrector ortográfico.

331
00:28:29,590 --> 00:28:32,060
Aínda que non vai ser a edición calquera código,

332
00:28:32,060 --> 00:28:38,050
é importante ler, entender cando é chamado de carga, cando eu estou chamando de verificación,

333
00:28:38,050 --> 00:28:42,350
só para entender, mapea-lo para fóra, ver como a función funciona.

334
00:28:42,350 --> 00:28:49,860
Vemos que está comprobando o uso correcto.

335
00:28:49,860 --> 00:28:55,200
Esencialmente, cando alguén corre Speller, iso indica que é opcional

336
00:28:55,200 --> 00:29:00,950
para eles para pasar nun arquivo de dicionario, porque alí vai ser un ficheiro de dicionario por defecto.

337
00:29:00,950 --> 00:29:05,410
E entón eles teñen que pasar o texto a ser comprobado feitizo.

338
00:29:05,410 --> 00:29:11,410
rusage ofertas co tempo, porque unha parte deste pset que imos tratar máis tarde

339
00:29:11,410 --> 00:29:14,790
é non só obter un funcionamento corrector ortográfico traballando

340
00:29:14,790 --> 00:29:17,190
pero realmente conseguir que sexa rápido.

341
00:29:17,190 --> 00:29:22,040
E así, entón, que é onde rusage vai vir dentro

342
00:29:22,040 --> 00:29:28,740
Aquí vemos a primeira chamada para un dos nosos arquivos dictionary.c, que é carga.

343
00:29:28,740 --> 00:29:34,720
Carga retorna true ou false - true en caso de éxito, falso en caso de fallo.

344
00:29:34,720 --> 00:29:41,400
Entón, se o dicionario non foi posto correctamente, entón o speller.c pode voltar 1 e saia.

345
00:29:41,400 --> 00:29:47,920
Pero se fai a carga correctamente, entón vai continuar.

346
00:29:47,920 --> 00:29:50,740
Continuamos, e vemos algún arquivo I / O aquí,

347
00:29:50,740 --> 00:29:56,210
onde vai ser xestionar a apertura do ficheiro de texto.

348
00:29:56,210 --> 00:30:04,640
Aquí, o que iso fai é feitizo comprobar cada palabra no texto.

349
00:30:04,640 --> 00:30:09,270
Entón, o que está facendo speller.c aquí está interactuando sobre cada unha das palabras no ficheiro de texto

350
00:30:09,270 --> 00:30:12,790
e, a continuación, comprobando los no dicionario.

351
00:30:24,680 --> 00:30:32,350
Aquí temos un Boolean incorrecta que vai ver se a comprobación retorna certo ou non.

352
00:30:32,350 --> 00:30:37,110
Se a palabra é, en realidade, no dicionario, entón cheque volverá true.

353
00:30:37,110 --> 00:30:39,760
Isto significa que a palabra non está incorrecto.

354
00:30:39,760 --> 00:30:45,330
Entón incorrecta sería falsa, e é por iso que temos o estrondo alí, a indicación.

355
00:30:45,330 --> 00:30:56,320
Nós manter en curso, e en seguida, el mantén o control de cantas palabras con erros ortográficos

356
00:30:56,320 --> 00:30:58,910
existen no arquivo.

357
00:30:58,910 --> 00:31:03,870
Continúa e pecha o arquivo.

358
00:31:03,870 --> 00:31:09,250
Entón, aquí, el informa cantas palabras con erros ortográficos que tivo.

359
00:31:09,250 --> 00:31:12,680
El calcula a cantidade de tempo que levou para cargar o dicionario,

360
00:31:12,680 --> 00:31:15,080
canto tempo tardou para comprobar-lo,

361
00:31:15,080 --> 00:31:18,510
canto tempo levou para calcular o tamaño,

362
00:31:18,510 --> 00:31:21,260
que, coma nós imos seguir, debe ser moi pequena,

363
00:31:21,260 --> 00:31:25,390
e despois de canto tempo que levou para descargar o dicionario.

364
00:31:25,390 --> 00:31:27,700
Aquí enriba, vemos a chamada para descargar aquí.

365
00:31:27,700 --> 00:31:52,690
Verificar tamaño aquí,

366
00:31:52,690 --> 00:31:59,050
entón vemos que aquí é a chamada para o tamaño que determina o tamaño do dicionario.

367
00:32:05,730 --> 00:32:07,100
Impresionante.

368
00:32:07,100 --> 00:32:10,920
>> A nosa tarefa para este pset é aplicar carga, o que vai cargar o dicionario

369
00:32:10,920 --> 00:32:15,480
estrutura de datos - o que escoller, sexa unha táboa hash ou un intento -

370
00:32:15,480 --> 00:32:18,810
con palabras do ficheiro de dicionario.

371
00:32:18,810 --> 00:32:25,290
Entón tes tamaño, que pode voltar o número de palabras no dicionario.

372
00:32:25,290 --> 00:32:29,860
E se implantar carga de forma intelixente, entón o tamaño debe ser moi doado.

373
00:32:29,860 --> 00:32:33,860
Entón comprobar que pode comprobar se unha palabra está no dicionario.

374
00:32:33,860 --> 00:32:38,690
Entón speller.c pasa unha corda, e entón ten que comprobar que a cadea que

375
00:32:38,690 --> 00:32:41,610
está contido dentro do seu dicionario.

376
00:32:41,610 --> 00:32:46,750
Teña en conta que xeralmente temos dicionarios estándar,

377
00:32:46,750 --> 00:32:53,020
pero neste pset, basicamente, calquera dicionario transmitido en calquera lingua.

378
00:32:53,020 --> 00:32:57,040
Polo tanto, non podemos só supor que a palabra THE está dentro.

379
00:32:57,040 --> 00:33:03,090
O FOOBAR palabra pode ser definida nun dicionario seguro que pasamos dentro

380
00:33:03,090 --> 00:33:07,920
E entón temos descargar, o que libera o dicionario da memoria.

381
00:33:07,920 --> 00:33:11,930
>> En primeiro lugar, gustaríame ir sobre o método de táboa hash

382
00:33:11,930 --> 00:33:14,630
sobre como podemos implementar todas estas catro funcións,

383
00:33:14,630 --> 00:33:18,650
e entón eu vou pasar por riba do método intenta, como podemos aplicar esas catro funcións,

384
00:33:18,650 --> 00:33:22,720
e na conversa final sobre algunhas suxestións xerais cando está facendo o pset

385
00:33:22,720 --> 00:33:27,870
e tamén como pode ser capaz de usar Valgrind para comprobar se hai vazamentos de memoria.

386
00:33:27,870 --> 00:33:30,550
>> Imos para o método de táboa hash.

387
00:33:30,550 --> 00:33:35,910
Unha táboa consta dunha lista de baldes.

388
00:33:35,910 --> 00:33:43,010
Cada valor, cada palabra, está a ir nun deses baldes.

389
00:33:43,010 --> 00:33:53,200
Unha táboa ideal distribúe todos eses valores que está pasando en

390
00:33:53,200 --> 00:33:57,160
e logo cobre-los no balde de xeito que cada balde

391
00:33:57,160 --> 00:34:02,000
ten preto de un número igual de valores na mesma.

392
00:34:02,000 --> 00:34:09,630
A estrutura dunha táboa hash, temos unha serie de listas ligadas.

393
00:34:09,630 --> 00:34:17,900
O que facemos é cando pasamos nun valor, nós consideramos que ese valor debería pertencer,

394
00:34:17,900 --> 00:34:23,840
balde que pertence, e despois poñelas na lista ligada asociada a ese balde.

395
00:34:23,840 --> 00:34:28,199
Aquí, o que eu teño é unha función hash.

396
00:34:28,199 --> 00:34:31,320
É unha táboa int hash.

397
00:34:31,320 --> 00:34:38,540
Así, para o primeiro balde, os enteiros baixo de 10 ir para o primeiro balde.

398
00:34:38,540 --> 00:34:42,190
Calquera números enteiros riba de 10, pero por baixo de 20 ir para o segundo,

399
00:34:42,190 --> 00:34:44,179
e, a continuación, así por diante e así por diante.

400
00:34:44,179 --> 00:34:52,370
Para min, cada segmento é representar eses números.

401
00:34:52,370 --> 00:34:59,850
Con todo, dicir que eu estaba a pasar en 50, por exemplo.

402
00:34:59,850 --> 00:35:07,490
Afigura-se como se os tres primeiros conteñen unha serie de 10 números.

403
00:35:07,490 --> 00:35:12,570
Pero quero deixar o meu táboa hash para tomar calquera tipo de enteiros,

404
00:35:12,570 --> 00:35:19,860
entón eu tería que filtrar todos os números enriba de 30 no balde pasado.

405
00:35:19,860 --> 00:35:26,660
E así, entón, que resultaría nunha especie de táboa hash desequilibrada.

406
00:35:31,330 --> 00:35:35,640
Para reiterar, unha táboa hash é só unha matriz de caçambas

407
00:35:35,640 --> 00:35:38,590
onde cada balde é unha lista ligada.

408
00:35:38,590 --> 00:35:43,730
E así, para determinar onde cada valor vai, que vai para balde,

409
00:35:43,730 --> 00:35:46,260
vai querer o que se denomina función hash

410
00:35:46,260 --> 00:35:55,010
que asume un valor e, a continuación, di que este valor corresponde a un balde correcto.

411
00:35:55,010 --> 00:36:00,970
Entón, alí encima, neste exemplo, a miña función hash levou cada valor.

412
00:36:00,970 --> 00:36:03,020
É comprobado se foi inferior a 10.

413
00:36:03,020 --> 00:36:05,360
Se fose, sería colocar-lo no primeiro balde.

414
00:36:05,360 --> 00:36:08,910
El verifica se é menor que 20, coloca-o no segundo, se verdadeira,

415
00:36:08,910 --> 00:36:12,880
comproba se é menor que 30, e en seguida, colócase no terceiro balde,

416
00:36:12,880 --> 00:36:16,990
e despois de todo só cae no balde cuarto.

417
00:36:16,990 --> 00:36:20,110
Así, sempre que ten un valor, función teu hash

418
00:36:20,110 --> 00:36:25,420
vai poñer o valor dentro do balde apropiado.

419
00:36:25,420 --> 00:36:32,430
A función hash, basicamente, ten que saber cantos baldes que ten.

420
00:36:32,430 --> 00:36:37,960
O seu tamaño da táboa, o número de depósitos que ten,

421
00:36:37,960 --> 00:36:41,190
que vai ser un número fixo que se con vostede, para decidir,

422
00:36:41,190 --> 00:36:43,590
pero vai ser un número fixo.

423
00:36:43,590 --> 00:36:51,840
Polo tanto, a súa función hash estará contando con iso para determinar balde de cada clave vai

424
00:36:51,840 --> 00:36:54,450
de tal forma que é uniformemente distribuída.

425
00:36:56,150 --> 00:37:03,820
Similar á nosa implantación de listas ligadas, agora cada nó na táboa de hash

426
00:37:03,820 --> 00:37:07,000
é realmente vai ter un char tipo.

427
00:37:07,000 --> 00:37:14,340
Polo tanto, temos unha matriz de char chamado palabra e, a continuación, outro punteiro ao seguinte nodo,

428
00:37:14,340 --> 00:37:19,010
o que ten sentido, porque vai ser unha lista ligada.

429
00:37:19,010 --> 00:37:24,350
Lembre-se de cando tiña conectado listas, fixen un * no chamado cabeza

430
00:37:24,350 --> 00:37:31,060
que estaba apuntando para o primeiro nodo da lista vinculada.

431
00:37:31,060 --> 00:37:34,020
Pero para a nosa táboa hash, porque temos varias listas ligadas,

432
00:37:34,020 --> 00:37:37,520
o que queremos é que queremos que a nosa táboa de hash para ser como, "O que é un balde?"

433
00:37:37,520 --> 00:37:43,340
Un balde é só unha lista de punteiros de nós,

434
00:37:43,340 --> 00:37:50,620
e así cada elemento no balde en realidade apunta a súa lista vinculado correspondente.

435
00:37:56,180 --> 00:38:01,520
Para volver este esquema, ve que os baldes en si son as frechas,

436
00:38:01,520 --> 00:38:06,980
non nos reais.

437
00:38:11,680 --> 00:38:16,420
Unha propiedade esencial de funcións hash é que son determinísticos.

438
00:38:16,420 --> 00:38:19,440
Isto significa que sempre que hash o número 2,

439
00:38:19,440 --> 00:38:22,270
debe volver sempre o mesmo balde.

440
00:38:22,270 --> 00:38:26,440
Cada valor único que vai para a función hash, se repetida,

441
00:38:26,440 --> 00:38:29,690
ten que obter o mesmo índice.

442
00:38:29,690 --> 00:38:34,210
Polo tanto, a súa función hash retorna o índice da matriz

443
00:38:34,210 --> 00:38:38,530
cando ese valor pertence.

444
00:38:38,530 --> 00:38:41,790
Como mencionei antes, o número de depósitos é fixo,

445
00:38:41,790 --> 00:38:49,630
e para que o seu índice que volver ten que ser menor que o número de caçambas

446
00:38:49,630 --> 00:38:52,680
pero maior que 0.

447
00:38:52,680 --> 00:39:00,780
A razón pola que temos funcións de hash en vez de só unha única lista vinculada

448
00:39:00,780 --> 00:39:09,290
ou unha única matriz é que queremos ser capaz de ir a unha determinada sección máis facilmente

449
00:39:09,290 --> 00:39:11,720
se sabemos que a característica de valor -

450
00:39:11,720 --> 00:39:14,760
en vez de ter que buscar no dicionario todo,

451
00:39:14,760 --> 00:39:18,320
ser capaz de ir a unha determinada sección do mesmo.

452
00:39:19,880 --> 00:39:24,440
A súa función hash debe ter en conta que, idealmente,

453
00:39:24,440 --> 00:39:28,980
cada balde ten aproximadamente o mesmo número de teclas.

454
00:39:28,980 --> 00:39:35,040
Como a táboa hash é unha serie de listas ligadas,

455
00:39:35,040 --> 00:39:38,480
a continuación, as listas ligadas propios van ter máis dun nodo.

456
00:39:38,480 --> 00:39:43,210
No exemplo anterior, dous números diferentes, aínda que elas non sexan iguais,

457
00:39:43,210 --> 00:39:46,950
cando desordenado, volvería o mesmo índice.

458
00:39:46,950 --> 00:39:53,620
Entón, cando está lidando coas palabras, unha palabra cando hash

459
00:39:53,620 --> 00:39:57,450
sería o mesmo valor hash como outra palabra.

460
00:39:57,450 --> 00:40:04,140
Iso é o que chamamos unha colisión, cando temos un no que, cando hash,

461
00:40:04,140 --> 00:40:09,610
a lista ligada a ese balde non está baleiro.

462
00:40:09,610 --> 00:40:14,180
A técnica que chamamos hai lineal enquisa,

463
00:40:14,180 --> 00:40:22,550
onde vai a lista de ligazóns e, a continuación, descubrir onde quere inserir o no

464
00:40:22,550 --> 00:40:25,520
porque ten unha colisión.

465
00:40:25,520 --> 00:40:28,070
Podes ver que pode haber un trade-off aquí, non?

466
00:40:28,070 --> 00:40:33,760
Se vostede ten unha táboa moi pequena suma, un número moi pequeno de baldes,

467
00:40:33,760 --> 00:40:36,380
entón vai ter unha morea de colisións.

468
00:40:36,380 --> 00:40:40,460
Pero, entón, se fai unha táboa hash moi grande,

469
00:40:40,460 --> 00:40:44,110
está indo probablemente para minimizar as colisións,

470
00:40:44,110 --> 00:40:47,170
pero vai ser unha gran estrutura de datos.

471
00:40:47,170 --> 00:40:49,310
Non vai ser trade-offs con iso.

472
00:40:49,310 --> 00:40:51,310
Entón, cando está facendo a súa pset, proba xogar

473
00:40:51,310 --> 00:40:54,210
entre quizais facer unha pequena táboa hash

474
00:40:54,210 --> 00:41:02,100
pero entón sabendo que vai levar un pouco máis para atravesar os distintos elementos

475
00:41:02,100 --> 00:41:04,270
desas listas ligadas.

476
00:41:04,270 --> 00:41:09,500
>> O que carga vai facer é iterar sobre cada palabra no dicionario.

477
00:41:09,500 --> 00:41:13,180
El pasa un punteiro para o arquivo de dicionario.

478
00:41:13,180 --> 00:41:18,050
Entón, vai aproveitar o arquivo E / S funcións que dominan en pset4

479
00:41:18,050 --> 00:41:23,010
e iterar sobre cada palabra no dicionario.

480
00:41:23,010 --> 00:41:26,620
Quere que todas as palabras do dicionario para facer un novo nodo,

481
00:41:26,620 --> 00:41:32,730
e vai poñer cada un deses nós dentro da súa estrutura de datos dicionario.

482
00:41:32,730 --> 00:41:36,560
Sempre que comeza unha nova palabra, xa sabe que vai facer un nó.

483
00:41:36,560 --> 00:41:46,590
Entón pode ir inmediatamente e malloc un punteiro no para cada palabra nova que ten.

484
00:41:46,590 --> 00:41:52,610
Aquí estou chamando meu new_node punteiro nó e estou mallocing o que? O tamaño dun nodo.

485
00:41:52,610 --> 00:41:59,190
Entón, para ler a secuencia real dun ficheiro, porque o dicionario está almacenado

486
00:41:59,190 --> 00:42:03,340
por unha palabra e, a continuación, unha nova liña, o que pode aproveitar de

487
00:42:03,340 --> 00:42:06,520
é a función fscanf,

488
00:42:06,520 --> 00:42:10,280
cal é o ficheiro de dicionario que estamos pasada

489
00:42:10,280 --> 00:42:18,900
por iso comproba o arquivo para unha cadea e lugares que cadea o último argumento.

490
00:42:18,900 --> 00:42:26,890
Se se lembrar de volta para unha das conferencias, cando nós fomos

491
00:42:26,890 --> 00:42:29,320
e tipo de peladas as capas de volta na biblioteca CS50,

492
00:42:29,320 --> 00:42:33,430
vimos unha aplicación de fscanf alí.

493
00:42:33,430 --> 00:42:37,700
Para volver ao fscanf, temos o ficheiro que estamos lendo,

494
00:42:37,700 --> 00:42:42,570
Estamos á procura de unha cadea na que o ficheiro, e despois imos poñelas en

495
00:42:42,570 --> 00:42:48,340
aquí eu teño new_node-> palabra porque new_node é un punteiro no,

496
00:42:48,340 --> 00:42:50,380
non un nó real.

497
00:42:50,380 --> 00:42:57,100
Entón eu estou dicindo new_node, quero ir para o nodo que está a apuntar cara

498
00:42:57,100 --> 00:43:01,190
e despois asignar o valor á palabra.

499
00:43:01,190 --> 00:43:08,540
Queremos entón tomar a palabra e inserir-lo na táboa de hash.

500
00:43:08,540 --> 00:43:13,750
Entenda que fixemos new_node un punteiro nodo

501
00:43:13,750 --> 00:43:18,230
porque nós imos querer saber o que o enderezo do nodo é

502
00:43:18,230 --> 00:43:23,940
cando inserir-lo no porque a estrutura dos nós, da estrutura,

503
00:43:23,940 --> 00:43:26,380
é que eles teñen un enlace para un novo nodo.

504
00:43:26,380 --> 00:43:30,820
Entón cal é o enderezo do nodo que vai apuntar?

505
00:43:30,820 --> 00:43:34,550
Este enderezo será new_node.

506
00:43:34,550 --> 00:43:42,140
Isto ten sentido, porque estamos facendo un new_node * ó en oposición a un nodo?

507
00:43:43,700 --> 00:43:45,700
Okay.

508
00:43:45,700 --> 00:43:52,840
Temos unha palabra. Este valor é new_node-> palabra.

509
00:43:52,840 --> 00:43:55,970
Que contén a palabra do dicionario que desexa inserir.

510
00:43:55,970 --> 00:44:00,210
Entón, o que queremos facer é que queremos chamar a nosa función hash sobre esta secuencia

511
00:44:00,210 --> 00:44:03,780
porque a nosa función hash leva nunha secuencia e despois nos devolve un número enteiro,

512
00:44:03,780 --> 00:44:12,090
onde ese enteiro é o índice onde hashtable en que o índice representa que balde.

513
00:44:12,090 --> 00:44:18,260
Queremos levar ese índice e, a continuación, ir ao contido da táboa hash

514
00:44:18,260 --> 00:44:26,960
e despois usar esta lista ligada para introducir o nó no new_node.

515
00:44:26,960 --> 00:44:31,950
Lembre que, con todo, decide introducir o nó,

516
00:44:31,950 --> 00:44:34,370
se é no medio se quere solucionar isto

517
00:44:34,370 --> 00:44:39,650
ou no inicio ou no final, só a certeza de que o seu último nodo sempre apunta para NULL

518
00:44:39,650 --> 00:44:46,730
porque esa é a única forma que sabemos onde o último elemento da lista conexionada e.

519
00:44:50,790 --> 00:44:59,710
>> Se o tamaño é un enteiro que representa o número de palabras nun dicionario,

520
00:44:59,710 --> 00:45:03,060
a continuación, unha forma de facer isto é que, sempre que o tamaño é chamado

521
00:45:03,060 --> 00:45:05,840
pasamos por cada elemento na nosa táboa hash

522
00:45:05,840 --> 00:45:09,410
e logo percorrer cada lista ligada dentro da táboa hash

523
00:45:09,410 --> 00:45:13,770
e, entón, calcular a lonxitude de que, aumentando a nosa 1 contador en 1.

524
00:45:13,770 --> 00:45:16,580
Pero cada vez que o tamaño é chamado, que vai levar un longo tempo

525
00:45:16,580 --> 00:45:22,120
porque imos ser linearmente sondando cada única lista vinculada.

526
00:45:22,120 --> 00:45:30,530
En vez diso, vai ser moito máis doado se manter o control de cantas palabras son pasados ​​dentro

527
00:45:30,530 --> 00:45:36,330
Entón se incluír un contador dentro da súa función de carga

528
00:45:36,330 --> 00:45:42,430
que as actualizacións, como sexa necesario, a continuación, contador, se define-lo como unha variable global,

529
00:45:42,430 --> 00:45:44,930
serán capaces de acceder polo tamaño.

530
00:45:44,930 --> 00:45:51,450
Entón, o que tamaño podería simplemente facer é unha liña, pode voltar o valor do contador,

531
00:45:51,450 --> 00:45:55,500
o tamaño do dicionario, que xa tratadas na carga.

532
00:45:55,500 --> 00:46:05,190
Isto é o que eu quería dicir cando dixo que se aplicar carga de forma útil,

533
00:46:05,190 --> 00:46:08,540
entón o tamaño vai ser moi fácil.

534
00:46:08,540 --> 00:46:11,350
>> Entón, agora temos que comprobar.

535
00:46:11,350 --> 00:46:15,960
Agora estamos lidando con palabras do ficheiro de texto de entrada,

536
00:46:15,960 --> 00:46:19,910
e así imos estar comprobando todas esas palabras de entrada

537
00:46:19,910 --> 00:46:22,520
son, en realidade, no dicionario ou non.

538
00:46:22,520 --> 00:46:26,520
Semellante a Scramble, queremos permitir a insensibilidade caso.

539
00:46:26,520 --> 00:46:32,110
Quere estar seguro de que todas as palabras pasada, a pesar de seren caso mixto,

540
00:46:32,110 --> 00:46:37,840
cando chamado con respecto cadea, son equivalentes.

541
00:46:37,840 --> 00:46:42,450
As palabras nos arquivos de texto dicionario son, en realidade, todas as letras minúsculas.

542
00:46:42,450 --> 00:46:49,280
Outra cousa é que pode asumir que cada palabra pasada, cada corda,

543
00:46:49,280 --> 00:46:53,200
vai ser tanto alfabética ou conter apóstrofos.

544
00:46:53,200 --> 00:46:58,010
Apóstrofos van ser palabras válidas no noso dicionario.

545
00:46:58,010 --> 00:47:06,470
Entón se ten unha palabra con apóstrofo S, que é unha palabra real lexítimo no seu dicionario

546
00:47:06,470 --> 00:47:11,650
que vai ser un dos nós na táboa hash.

547
00:47:13,470 --> 00:47:18,350
Asegúrese de que opera coa palabra existe, entón ten que estar na nosa táboa de hash.

548
00:47:18,350 --> 00:47:22,210
Se a palabra está no dicionario, entón todas as palabras do dicionario están na táboa hash,

549
00:47:22,210 --> 00:47:26,560
entón imos ollar para esta palabra na táboa hash.

550
00:47:26,560 --> 00:47:29,250
Sabemos que dende que Implementar noso función hash

551
00:47:29,250 --> 00:47:38,420
de tal xeito que cada palabra única é sempre hash para o mesmo valor,

552
00:47:38,420 --> 00:47:43,340
entón sabemos que, en vez de buscar a través da nosa mesa enteira toda hash,

553
00:47:43,340 --> 00:47:48,310
podemos realmente atopar unha lista ligada que esa palabra debe pertencer.

554
00:47:48,310 --> 00:47:51,850
Se fose no dicionario, entón sería ese balde.

555
00:47:51,850 --> 00:47:57,140
O que podemos facer, se a palabra é o nome da nosa cadea pasada

556
00:47:57,140 --> 00:48:01,560
Podemos só hash que palabra e ollar para a lista ligada

557
00:48:01,560 --> 00:48:06,410
por valor de hashtable [hash (palabra)].

558
00:48:06,410 --> 00:48:12,410
De alí, o que podemos facer é que temos un subconjunto menor de nós para buscar esta palabra,

559
00:48:12,410 --> 00:48:16,770
e para que poidamos atravesar a lista ligada, usando un exemplo máis cedo no paso a paso,

560
00:48:16,770 --> 00:48:24,110
e despois chamar cadea compare coa palabra onde queira que o cursor está a apuntar,

561
00:48:24,110 --> 00:48:28,430
esa palabra, e ver se os comparar.

562
00:48:30,280 --> 00:48:35,110
Dependendo da forma que organizar a súa función hash,

563
00:48:35,110 --> 00:48:39,260
se é ordenado, pode ser capaz de volver un pouco máis cedo falsa,

564
00:48:39,260 --> 00:48:43,440
pero si é indiferenciados, entón quere seguir percorrendo a través da súa lista ligada

565
00:48:43,440 --> 00:48:46,480
ata atopar o último elemento da lista.

566
00:48:46,480 --> 00:48:53,320
E se aínda non atopou a palabra polo tempo que chegou ao fin da lista ligada,

567
00:48:53,320 --> 00:48:56,890
que significa que a súa palabra non existe no dicionario,

568
00:48:56,890 --> 00:48:59,410
e así que a palabra non é válido,

569
00:48:59,410 --> 00:49:02,730
e comprobación debe retornar falso.

570
00:49:02,730 --> 00:49:09,530
>> Agora imos para descargar, onde queremos liberar todos os nós que temos malloc'd,

571
00:49:09,530 --> 00:49:14,050
tan libre de todos os nós dentro da nosa táboa de hash.

572
00:49:14,050 --> 00:49:20,270
Nós imos querer iterar sobre as listas ligadas e libres de todos os nós que.

573
00:49:20,270 --> 00:49:29,350
Se ollar por riba no paso a paso para o exemplo que liberar unha lista ligada,

574
00:49:29,350 --> 00:49:35,140
entón vai querer repetir este proceso para cada elemento na táboa hash.

575
00:49:35,140 --> 00:49:37,780
E eu vou pasar por riba deste cara ao final da explicación,

576
00:49:37,780 --> 00:49:46,600
pero Valgrind é unha ferramenta onde podes ver se adecuadamente liberado

577
00:49:46,600 --> 00:49:53,600
Cada nodo que malloc'd ou calquera outra cousa que malloc'd, calquera outro punteiro.

578
00:49:55,140 --> 00:50:00,530
Entón, iso é táboas de hash, onde temos un número finito de baldes

579
00:50:00,530 --> 00:50:09,220
e unha función hash, que terá un valor e despois asignar o valor para un balde correcto.

580
00:50:09,220 --> 00:50:13,340
>> Agora chegamos ao tentativas.

581
00:50:13,340 --> 00:50:18,750
Intenta tipo de ollar como este, e eu tamén vou sacar un exemplo.

582
00:50:18,750 --> 00:50:25,630
Basicamente, ten toda unha serie de cartas de potenciais,

583
00:50:25,630 --> 00:50:29,210
e entón, sempre que está construíndo unha palabra,

584
00:50:29,210 --> 00:50:36,490
esa carta pode ser conectado por un dicionario para unha ampla gama de posibilidades.

585
00:50:36,490 --> 00:50:40,840
Algunhas palabras comezan con C, pero a continuación, continuar a,

586
00:50:40,840 --> 00:50:42,960
pero outros continúan co, por exemplo.

587
00:50:42,960 --> 00:50:51,090
Un trie é un xeito de ver todas as combinacións posibles destas palabras.

588
00:50:51,090 --> 00:50:59,070
Unha trie vai seguir a secuencia de letras que compoñen as palabras,

589
00:50:59,070 --> 00:51:08,280
ramificados-se, cando sexa necesario, cando unha letra pode ser seguido por un múltiple de cartas,

590
00:51:08,280 --> 00:51:16,630
e ao final de cada punto indican a palabra é válido ou non

591
00:51:16,630 --> 00:51:30,120
porque se está Soletrando a palabra MAT, MA Eu non creo que é unha palabra válida, pero é MAT.

592
00:51:30,120 --> 00:51:37,820
E así, no seu trie, iso indicaría que despois de MAT que en realidade é unha palabra válida.

593
00:51:41,790 --> 00:51:48,590
Cada nodo na nosa trie está realmente indo para conter unha matriz de punteiros de nós,

594
00:51:48,590 --> 00:51:52,970
e nós imos ter, especialmente, 27 dos punteiros do nodo,

595
00:51:52,970 --> 00:52:00,550
un para cada letra do alfabeto, así como o carácter apóstrofo.

596
00:52:00,550 --> 00:52:10,450
Cada elemento na matriz é en si que pode apuntar a outro nodo.

597
00:52:10,450 --> 00:52:14,020
Entón, se ese nodo é NULL se non hai nada despois diso,

598
00:52:14,020 --> 00:52:20,550
entón sabemos que non hai outras cartas en que a secuencia de palabras.

599
00:52:20,550 --> 00:52:26,950
Pero se ese nodo non é NULL, o que significa que hai máis cartas en que secuencia de letras.

600
00:52:26,950 --> 00:52:32,160
E despois diso, cada nodo indica se é o último carácter dunha palabra ou non.

601
00:52:38,110 --> 00:52:43,170
>> Imos a un exemplo dunha trie.

602
00:52:50,500 --> 00:52:58,340
Primeiro eu teño espazo para 27 nós nesta matriz.

603
00:52:58,340 --> 00:53:03,200
Se eu tivera a palabra BAR -

604
00:53:13,310 --> 00:53:15,370
Se eu tivera a BAR palabra e quero introducir no que,

605
00:53:15,370 --> 00:53:22,700
a primeira letra é B, entón a miña trie é baleiro,

606
00:53:22,700 --> 00:53:29,910
B é a segunda letra do alfabeto, entón eu vou escoller para poñer esta aquí neste índice.

607
00:53:29,910 --> 00:53:33,450
Vou ter B aquí.

608
00:53:33,450 --> 00:53:42,400
B vai ser un nó que apunta a outra matriz de todos os posibles caracteres

609
00:53:42,400 --> 00:53:45,870
que pode seguir tras a letra B.

610
00:53:45,870 --> 00:53:57,610
Neste caso, eu estou lidando con a barra de palabra, de xeito que a ira aquí.

611
00:54:02,000 --> 00:54:08,990
Despois de A, eu teño a letra R, de forma seguida, un puntos agora a súa propia combinación,

612
00:54:08,990 --> 00:54:15,120
e R estarei aquí.

613
00:54:15,120 --> 00:54:22,470
Bar e unha palabra completa, entón eu vou ter punto R para outro no

614
00:54:22,470 --> 00:54:33,990
que di que esa palabra é válido.

615
00:54:36,010 --> 00:54:40,970
Este nó é tamén vai ter un conxunto de nós,

616
00:54:40,970 --> 00:54:45,260
pero os poden ser NULL.

617
00:54:45,260 --> 00:54:49,080
Pero, basicamente, pode seguir así.

618
00:54:49,080 --> 00:54:54,250
Isto vai facer un pouco máis claro cando imos a un exemplo diferente,

619
00:54:54,250 --> 00:54:56,780
por iso teña paciencia comigo alí.

620
00:54:56,780 --> 00:55:02,050
Agora temos BAR dentro do noso dicionario.

621
00:55:02,050 --> 00:55:05,980
Agora dicir que temos o Baz palabra.

622
00:55:05,980 --> 00:55:12,630
Comezamos con B, e xa temos B como unha das cartas que están no noso dicionario.

623
00:55:12,630 --> 00:55:15,170
Isto é seguido con A. Temos un posto.

624
00:55:15,170 --> 00:55:19,250
Pero, entón, en vez diso, temos seguinte Z.

625
00:55:19,250 --> 00:55:25,490
Entón, a continuación, un elemento da nosa matriz será Z,

626
00:55:25,490 --> 00:55:30,810
e así, entón, que un vai apuntar a outro fin válido da palabra.

627
00:55:30,810 --> 00:55:36,930
Así, vemos que cando seguimos a B e despois A,

628
00:55:36,930 --> 00:55:43,480
hai dúas opcións diferentes actualmente no noso dicionario de palabras que comezan con B e A.

629
00:55:49,650 --> 00:55:57,460
Dicir que quería introducir o FOOBAR palabra.

630
00:55:57,460 --> 00:56:05,620
Entón, queremos facer unha entrada en F.

631
00:56:05,620 --> 00:56:11,320
F é un nó que apunta a unha matriz enteira.

632
00:56:11,320 --> 00:56:22,790
O que ía atopar, vai a O, O, a continuación, conecta a unha lista enteira.

633
00:56:22,790 --> 00:56:35,340
Teriamos B e, a continuación, continuar, teriamos A e despois R.

634
00:56:35,340 --> 00:56:43,570
Entón atravesa foobar todo o camiño ata FOOBAR é unha palabra correcta.

635
00:56:43,570 --> 00:56:52,590
E así, entón iso sería unha palabra válida.

636
00:56:52,590 --> 00:57:00,170
Agora dicir que a nosa seguinte palabra no dicionario é realmente a palabra foo.

637
00:57:00,170 --> 00:57:03,530
Diriamos F. O que segue F?

638
00:57:03,530 --> 00:57:06,190
En realidade, eu xa teño un espazo para o, entón eu vou seguir.

639
00:57:06,190 --> 00:57:09,150
Eu non teño de facer un novo. Continuar.

640
00:57:09,150 --> 00:57:15,500
Foo é unha palabra válida neste dicionario, entón eu vou para indicar

641
00:57:15,500 --> 00:57:21,660
que iso é válido.

642
00:57:21,660 --> 00:57:28,370
Se eu deixar o meu secuencia alí, que sería correcto.

643
00:57:28,370 --> 00:57:33,050
Pero se seguimos a nosa secuencia de Foo ata B

644
00:57:33,050 --> 00:57:39,750
e só tiña foob, foob non é unha palabra, e iso non é indicado como un válido.

645
00:57:47,370 --> 00:57:57,600
Nunha trie, ten cada nó indicando se é unha palabra válida ou non,

646
00:57:57,600 --> 00:58:05,840
e, a continuación, cada nó tamén ten unha matriz de 27 punteiros do nodo

647
00:58:05,840 --> 00:58:09,520
que apunte a nós mesmos.

648
00:58:09,520 --> 00:58:12,940
>> Aquí está unha forma de como pode querer axustar iso.

649
00:58:12,940 --> 00:58:17,260
Con todo, como no exemplo da táboa hash, onde tiña a cabeza * ó

650
00:58:17,260 --> 00:58:21,320
para indicar o inicio da nosa lista ligada, nós tamén imos querer

651
00:58:21,320 --> 00:58:29,150
algunha forma de saber onde o inicio da nosa trie é.

652
00:58:29,150 --> 00:58:34,110
Algúns chaman a xente intenta árbores, e é aí que vén da raíz.

653
00:58:34,110 --> 00:58:36,910
Entón, nós queremos a raíz da nosa árbore para estar seguro de que imos estar aterrado

654
00:58:36,910 --> 00:58:39,570
onde o noso trie é.

655
00:58:42,910 --> 00:58:46,300
Nós xa medio que fun máis

656
00:58:46,300 --> 00:58:50,240
a forma como podería pensar a carga de cada palabra no dicionario.

657
00:58:50,240 --> 00:58:54,540
Esencialmente, para cada palabra que vai querer para percorrer o trie

658
00:58:54,540 --> 00:58:59,590
e sabendo que cada elemento en que os nenos - que chamou de nenos neste caso -

659
00:58:59,590 --> 00:59:04,290
corresponde a unha letra diferente, vai querer comprobar eses valores

660
00:59:04,290 --> 00:59:08,320
en que o índice particular, que corresponde á letra.

661
00:59:08,320 --> 00:59:11,260
Entón, pensando todo o camiño de volta a César e Vigenère,

662
00:59:11,260 --> 00:59:16,070
sabendo que cada carta que podes tipo de mapa para un índice alfabético,

663
00:59:16,070 --> 00:59:20,690
definitivamente da a Z vai ser moi fácil de localizar nun mapa a unha letra alfabética,

664
00:59:20,690 --> 00:59:25,200
pero, desgraciadamente, as apóstrofes son tamén un carácter aceptado en palabras.

665
00:59:25,200 --> 00:59:31,650
Eu nin estou seguro que o valor ASCII é,

666
00:59:31,650 --> 00:59:39,250
así para que, se quere atopar un índice de decidir se quere que sexa o primeiro ou

667
00:59:39,250 --> 00:59:44,550
ou o último, vai ter que facer unha proba codificado para

668
00:59:44,550 --> 00:59:48,930
e despois poñer isto no índice 26, por exemplo.

669
00:59:48,930 --> 00:59:55,300
Entón está comprobando o valor en nenos [i]

670
00:59:55,300 --> 00:59:58,400
onde [i] corresponde a calquera carta que está.

671
00:59:58,400 --> 01:00:04,110
Se isto é NULL, o que significa que non hai actualmente ningunha carta posibles

672
01:00:04,110 --> 01:00:08,150
decorrente de que a secuencia anterior, de xeito que vai querer malloc

673
01:00:08,150 --> 01:00:13,150
e facer un novo nodo e teñen que os nenos [i] punto para el

674
01:00:13,150 --> 01:00:17,890
de modo que crear - cando inserido nunha carta para o rectángulo -

675
01:00:17,890 --> 01:00:23,680
facendo os nenos non NULL e punto en que novo nodo.

676
01:00:23,680 --> 01:00:28,340
Pero se iso non é NULL, como no noso exemplo de foo

677
01:00:28,340 --> 01:00:34,570
cando xa FOOBAR, seguimos,

678
01:00:34,570 --> 01:00:44,010
e non estamos sempre facendo un novo nodo, senón só a creación is_word para true

679
01:00:44,010 --> 01:00:47,790
no fin da palabra.

680
01:00:50,060 --> 01:00:55,340
>> Polo tanto, así como antes, porque aquí está lidando con cada letra de cada vez,

681
01:00:55,340 --> 01:01:01,470
que vai ser máis doado para ti para o tamaño, en vez de ter que calcular

682
01:01:01,470 --> 01:01:06,910
e pasar por toda a árbore e calcular cantos fillos eu teño

683
01:01:06,910 --> 01:01:10,850
e, a continuación, ramificados-se, lembrar-se cantos están do lado esquerdo e lado dereito

684
01:01:10,850 --> 01:01:12,850
e cousas así, vai ser moito máis doado para ti

685
01:01:12,850 --> 01:01:16,220
se só manter o control de cantas palabras está engadindo a

686
01:01:16,220 --> 01:01:18,080
cando está lidando con a carga.

687
01:01:18,080 --> 01:01:22,630
E entón que o tamaño do camiño pode devolver só unha variable global do tamaño.

688
01:01:25,320 --> 01:01:28,530
>> Agora chegamos a comprobar.

689
01:01:28,530 --> 01:01:33,920
Mesmos estándares de antes, onde queremos permitir a insensibilidade caso.

690
01:01:33,920 --> 01:01:40,400
Como así, imos supor que as cordas son só caracteres alfabéticos ou os apóstrofos

691
01:01:40,400 --> 01:01:44,000
porque os nenos é unha matriz de 27 de lonxitude,

692
01:01:44,000 --> 01:01:48,480
así todas as letras do alfabeto máis o apóstrofo.

693
01:01:48,480 --> 01:01:53,800
Para comprobar o que vai querer facer é que vai querer comezar na raíz

694
01:01:53,800 --> 01:01:58,440
porque a raíz ha apuntar para unha matriz que contén

695
01:01:58,440 --> 01:02:01,630
todas as letras posibles a partir dunha palabra.

696
01:02:01,630 --> 01:02:03,680
Vai comezar por aí,

697
01:02:03,680 --> 01:02:11,590
e entón vai comprobar e este valor NULL ou non,

698
01:02:11,590 --> 01:02:16,490
porque se o valor é NULL, o que significa que o dicionario non ten ningunha valores

699
01:02:16,490 --> 01:02:21,480
que conteñen a carta en que a orde particular.

700
01:02:21,480 --> 01:02:24,970
Se é nulo, entón iso significa que a palabra é grafada inmediatamente.

701
01:02:24,970 --> 01:02:27,110
Pero se non é NULL, entón podes continuar,

702
01:02:27,110 --> 01:02:34,090
dicir que a primeira letra é unha carta posíbel primeiro nunha palabra,

703
01:02:34,090 --> 01:02:40,630
entón agora eu quero comprobar que a segunda letra, esa secuencia, está dentro do meu dicionario.

704
01:02:40,630 --> 01:02:46,540
Entón está indo para ir ao índice de nenos do primeiro nodo

705
01:02:46,540 --> 01:02:50,720
e comprobar se esa segunda carta existe.

706
01:02:50,720 --> 01:02:57,440
Entón repetir este proceso para verificar que a secuencia é válido ou non

707
01:02:57,440 --> 01:02:59,060
dentro do seu trie.

708
01:02:59,060 --> 01:03:06,430
Sempre que os nenos no no índice apunta a NULL,

709
01:03:06,430 --> 01:03:10,710
vostede sabe que a secuencia non existe,

710
01:03:10,710 --> 01:03:16,230
pero se chegar ao final da palabra que escribiu,

711
01:03:16,230 --> 01:03:20,070
Entón quere comprobar agora que eu completei esa secuencia

712
01:03:20,070 --> 01:03:27,610
e descubriu que dentro do meu trie, que é unha palabra válida ou non?

713
01:03:27,610 --> 01:03:32,480
E entón quere comprobar se, e é aí onde se atopou esa secuencia,

714
01:03:32,480 --> 01:03:35,120
Entón quere comprobar se esa palabra é válido ou non

715
01:03:35,120 --> 01:03:40,290
porque lembro que no caso anterior que eu deseñei, onde tivemos foob,

716
01:03:40,290 --> 01:03:48,410
que era unha secuencia válida que atopamos, pero non era unha palabra real válido en si.

717
01:03:50,570 --> 01:03:59,000
>> Do mesmo xeito, para descargar nos intentos que quere para descargar todos os nós na súa trie.

718
01:03:59,000 --> 01:04:04,790
Sentímolo. Similares ás táboas de hash onde descargar en nós liberados todos os nós,

719
01:04:04,790 --> 01:04:09,740
nos intentos tamén queremos liberar todos os nós.

720
01:04:09,740 --> 01:04:15,000
Descargar realmente máis fácil traballar desde abaixo

721
01:04:15,000 --> 01:04:19,290
porque estes son esencialmente conectados listas.

722
01:04:19,290 --> 01:04:22,540
Entón, nós queremos estar seguro de que temos para todos os valores

723
01:04:22,540 --> 01:04:25,700
e libre de todos los explicitamente.

724
01:04:25,700 --> 01:04:28,840
O que vai querer facer se está a traballar con unha trie

725
01:04:28,840 --> 01:04:35,640
é viaxar para o fondo e no do libre menor posible primeiro

726
01:04:35,640 --> 01:04:39,190
e despois irse a todos os fillos e, entón, libre de todos aqueles,

727
01:04:39,190 --> 01:04:43,050
ir cara arriba e, entón, libre, etc

728
01:04:43,050 --> 01:04:48,790
Tipo de como tratar coa capa de fondo do primeiro trie

729
01:04:48,790 --> 01:04:51,940
e despois vai alí enriba despois de liberar todo.

730
01:04:51,940 --> 01:04:56,720
Este é un bo exemplo de que a función recursiva pode vir a cadra.

731
01:04:56,720 --> 01:05:03,830
Unha vez que liberou a capa inferior da trie,

732
01:05:03,830 --> 01:05:08,000
entón chámase descargar sobre o resto,

733
01:05:08,000 --> 01:05:13,620
asegurarse de que liberar todos os mini -

734
01:05:13,620 --> 01:05:16,410
Podes tipo de velo como intentos mini.

735
01:05:23,300 --> 01:05:28,990
Entón, vostede ten a súa raíz aquí.

736
01:05:30,840 --> 01:05:35,230
Estou simplificando, entón eu non teño que tirar 26 deles.

737
01:05:37,250 --> 01:05:43,770
Entón tes que, e en seguida, estes representan secuencias de palabras

738
01:05:43,770 --> 01:05:54,620
onde todos estes pequenos círculos son letras que son secuencias válidas de letras.

739
01:06:03,040 --> 01:06:07,160
Imos continuar un pouco máis.

740
01:06:15,110 --> 01:06:25,750
O que vai querer facer é libre o fondo aquí e entón libre este

741
01:06:25,750 --> 01:06:31,640
e, a continuación, un agasallo libre no fondo antes de liberar o cumio aquí

742
01:06:31,640 --> 01:06:38,180
porque se algo libre no segundo nivel aquí,

743
01:06:38,180 --> 01:06:47,230
entón realmente vai perder este valor aquí.

744
01:06:47,230 --> 01:06:54,780
É por iso que é importante na descarga de un trie para asegurarse de que liberar o fondo primeiro.

745
01:06:54,780 --> 01:06:59,480
O que pode querer facer é dicir para cada nodo

746
01:06:59,480 --> 01:07:06,430
Quero descargar todos os nenos.

747
01:07:16,060 --> 01:07:22,140
>> Agora que xa sabemos descargar para o método de táboa hash, así como o método trie,

748
01:07:22,140 --> 01:07:27,020
imos querer ollar para Valgrind.

749
01:07:27,020 --> 01:07:29,640
Valgrind corre cos seguintes comandos.

750
01:07:29,640 --> 01:07:32,700
Tes valgrind-v.

751
01:07:32,700 --> 01:07:40,960
Vostede está comprobando todos os vazamentos cando realizar Speller dado este determinado texto

752
01:07:40,960 --> 01:07:46,980
Speller porque precisa levar nun arquivo de texto.

753
01:07:46,980 --> 01:07:52,330
Entón Valgrind ha realizar o seu programa, dicir cantos bytes lle asignado,

754
01:07:52,330 --> 01:07:57,150
cantos bytes lle liberou, e el vai lle dicir se liberou só o suficiente

755
01:07:57,150 --> 01:07:58,930
ou se non suficiente,

756
01:07:58,930 --> 01:08:02,850
ou, ás veces pode ata mesmo sobre libre, como un nó libre que xa foi liberado

757
01:08:02,850 --> 01:08:05,140
e así el pode voltar erros.

758
01:08:05,140 --> 01:08:11,600
Se usar Valgrind, que vai che dar algunhas mensaxes

759
01:08:11,600 --> 01:08:15,970
indicando se liberou ou menos que o suficiente, só o suficiente,

760
01:08:15,970 --> 01:08:19,609
ou máis veces o suficiente.

761
01:08:24,370 --> 01:08:30,410
>> Unha parte deste pset, é opcional para desafiar o Big Board.

762
01:08:30,410 --> 01:08:35,790
Pero cando estamos lidando con esas estruturas de datos

763
01:08:35,790 --> 01:08:40,689
É divertido ver como rapidamente e quão eficiente súas estruturas de datos podería ser.

764
01:08:40,689 --> 01:08:44,490
Será que o seu resultado función hash en un monte de colisións?

765
01:08:44,490 --> 01:08:46,300
Ou é o seu tamaño de datos realmente grande?

766
01:08:46,300 --> 01:08:49,420
Leva moito tempo para atravesar?

767
01:08:49,420 --> 01:08:54,800
No rexistro de Speller, el exhibe canto tempo emprega para cargar,

768
01:08:54,800 --> 01:08:57,700
para comprobar, para conducir, tamaño e para descargar,

769
01:08:57,700 --> 01:09:00,720
e así os foron publicados no O Big Board,

770
01:09:00,720 --> 01:09:03,600
onde podes competir contra os seus compañeiros

771
01:09:03,600 --> 01:09:11,350
e algúns membros do equipo para ver quen ten o máis rápido corrector ortográfico.

772
01:09:11,350 --> 01:09:14,760
Unha cousa que me gustaría observar sobre as táboas de hash

773
01:09:14,760 --> 01:09:20,470
é que hai algunhas funcións moi sinxelo de hash que poderiamos pensar.

774
01:09:20,470 --> 01:09:27,240
Por exemplo, ten 26 baldes, e así cada balde

775
01:09:27,240 --> 01:09:30,200
corresponde á primeira letra dunha palabra,

776
01:09:30,200 --> 01:09:35,229
pero iso vai producir unha táboa de hash moi desequilibrada

777
01:09:35,229 --> 01:09:40,979
porque hai palabras moi menos que comezan con X que comezar con M, por exemplo.

778
01:09:40,979 --> 01:09:47,890
Unha forma de facer Speller é se quere obter todas as funcionalidades outra para abaixo,

779
01:09:47,890 --> 01:09:53,240
despois é só usar unha simple función hash para ser capaz de obter o seu código en execución

780
01:09:53,240 --> 01:09:58,650
e despois volver e cambiar o tamaño da súa táboa de hash e definición.

781
01:09:58,650 --> 01:10:03,430
Hai unha serie de recursos na internet para funcións de hash,

782
01:10:03,430 --> 01:10:08,250
e así a este pset que están autorizados a buscar funcións hash en internet

783
01:10:08,250 --> 01:10:15,560
para algúns consellos e inspiración, sempre que asegúrese de citar onde ten que partir.

784
01:10:15,560 --> 01:10:22,060
Estás convidado a mirar e interpretar algunha función hash que atopa en Internet.

785
01:10:22,060 --> 01:10:27,460
Volver a iso, pode ser capaz de ver se alguén usou unha trie

786
01:10:27,460 --> 01:10:31,700
a súa implementación é máis rápido que a súa táboa hash ou non.

787
01:10:31,700 --> 01:10:35,290
Pode enviar o Consello Big varias veces.

788
01:10:35,290 --> 01:10:37,660
Ela ha gravar a súa entrada máis recente.

789
01:10:37,660 --> 01:10:44,300
Entón quizais cambiar de función hash e, a continuación, entender que en realidade é moito máis rápido

790
01:10:44,300 --> 01:10:46,780
ou moito máis lento que antes.

791
01:10:46,780 --> 01:10:50,960
Isto é un pouco de unha forma divertida.

792
01:10:50,960 --> 01:10:57,190
Sempre hai un ou dous membros do equipo que tentan facer o dicionario máis lento posible,

793
01:10:57,190 --> 01:11:00,210
de xeito que sempre divertido de ollar.

794
01:11:00,210 --> 01:11:07,630
>> O uso a pset é executar Speller cun dicionario opcional

795
01:11:07,630 --> 01:11:12,840
e, a continuación, un arquivo de texto obrigatoria.

796
01:11:12,840 --> 01:11:18,380
Por defecto, cando realizar Speller con só un arquivo de texto e non especificar un dicionario,

797
01:11:18,380 --> 01:11:24,410
vai utilizar o arquivo de texto dicionario, a unha gran

798
01:11:24,410 --> 01:11:27,920
na carpeta cs50/pset5/dictionaries.

799
01:11:27,920 --> 01:11:32,760
Que un ten máis de 100.000 palabras.

800
01:11:32,760 --> 01:11:37,950
Eles tamén teñen un pequeno dicionario, que ten palabras considerablemente menos

801
01:11:37,950 --> 01:11:40,730
CS50 que fixo para ti.

802
01:11:40,730 --> 01:11:44,050
Con todo, pode moi facilmente só facer o seu propio dicionario

803
01:11:44,050 --> 01:11:47,150
se só quere estar traballando en pequenos exemplos -

804
01:11:47,150 --> 01:11:51,140
Por exemplo, se quere usar o gdb e vostede sabe os valores específicos

805
01:11:51,140 --> 01:11:53,560
que quere que o seu táboa de hash para mapear a.

806
01:11:53,560 --> 01:12:00,430
Entón só pode facer o seu propio arquivo de texto só con bar, Baz, foo, e FOOBAR,

807
01:12:00,430 --> 01:12:04,860
facelo nun arquivo de texto, separar os cada un cunha liña,

808
01:12:04,860 --> 01:12:12,670
e, a continuación, facer o seu propio arquivo de texto que literalmente só contén quizais unha ou dúas palabras

809
01:12:12,670 --> 01:12:15,950
para que vostede sabe exactamente o que a saída debe ser.

810
01:12:15,950 --> 01:12:21,870
Algúns dos arquivos de texto mostra que a Big Board cando realizar reto pode comprobar

811
01:12:21,870 --> 01:12:25,580
son Guerra e Paz e unha novela de Jane Austen, ou algo así.

812
01:12:25,580 --> 01:12:30,450
Entón, cando está comezando, é moito máis doado de facer os seus propios ficheiros de texto

813
01:12:30,450 --> 01:12:34,160
que conteñen só un par de palabras ou talvez 10

814
01:12:34,160 --> 01:12:38,280
de modo que pode prever o que o resultado debe ser

815
01:12:38,280 --> 01:12:42,880
e despois comprobar se contra iso, entón un exemplo controlado.

816
01:12:42,880 --> 01:12:45,820
E así xa que estamos lidando con a previsión e deseñar as cousas,

817
01:12:45,820 --> 01:12:48,690
outra vez quero che fomentar a usar papel e pluma

818
01:12:48,690 --> 01:12:50,700
porque realmente vai axudar con un regalo -

819
01:12:50,700 --> 01:12:55,620
deseñar as frechas, como a táboa hash ou como o seu trie mira,

820
01:12:55,620 --> 01:12:57,980
cando está liberando algo onde as frechas están indo,

821
01:12:57,980 --> 01:13:01,730
vostede está seguro o suficiente, vostede ve todos os enlaces desaparecendo

822
01:13:01,730 --> 01:13:05,750
e caendo no abismo da memoria baleirada.

823
01:13:05,750 --> 01:13:11,070
Entón, por favor, por favor, ténteo de deseñar as cousas antes de chegar a escribir código para abaixo.

824
01:13:11,070 --> 01:13:14,520
Debuxe as cousas para que entenda como as cousas están indo para o traballo

825
01:13:14,520 --> 01:13:22,750
porque entón eu asegura que vai executar en confusións menos punteiro alí.

826
01:13:24,270 --> 01:13:25,910
>> Todo ben.

827
01:13:25,910 --> 01:13:28,780
Quero desexar-lle o mellor da sorte con este pset.

828
01:13:28,780 --> 01:13:31,980
É probabelmente o máis difícil.

829
01:13:31,980 --> 01:13:40,360
Polo tanto, proba comezar cedo, deseñar as cousas, deseñar as cousas, e boa sorte.

830
01:13:40,360 --> 01:13:42,980
Este foi Walkthrough 5.

831
01:13:45,160 --> 01:13:47,000
>> [CS50.TV]