1
00:00:00,000 --> 00:00:11,856

2
00:00:11,856 --> 00:00:13,050
>> ROB Bowden: Hi.

3
00:00:13,050 --> 00:00:16,210
Estic Rob, i el hash de let
aquesta solució fora.

4
00:00:16,210 --> 00:00:20,070
Així que aquí anem a posar en pràctica
una taula hash general.

5
00:00:20,070 --> 00:00:24,090
Veiem que el node d'estructura de la nostra haixix
taula tindrà aquest aspecte.

6
00:00:24,090 --> 00:00:28,710
Així que va a tenir una paraula caràcters
matriu de longitud més de la mida 1.

7
00:00:28,710 --> 00:00:32,259
No us oblideu el 1, ja que la màxima
paraula al diccionari és 45

8
00:00:32,259 --> 00:00:35,110
caràcters, i després ens anem a
necessitarà un personatge extra per al

9
00:00:35,110 --> 00:00:37,070
barra invertida 0.

10
00:00:37,070 --> 00:00:40,870
>> I llavors la nostra taula hash en cada
cub es va a emmagatzemar un

11
00:00:40,870 --> 00:00:42,320
llista enllaçada de nodes.

12
00:00:42,320 --> 00:00:44,420
No estem fent el sondeig lineal aquí.

13
00:00:44,420 --> 00:00:48,430
I així, per tal de vincular la següent
element en el cub, necessitem un

14
00:00:48,430 --> 00:00:51,110
struct node * següent.

15
00:00:51,110 --> 00:00:53,090
Així que això és el que un node es sembla.

16
00:00:53,090 --> 00:00:56,180
Ara, aquí és la declaració
de la nostra taula hash.

17
00:00:56,180 --> 00:01:01,910
Va a tenir 16.384 cubs, però
aquest nombre en realitat no importa.

18
00:01:01,910 --> 00:01:05,450
I, finalment, tindrem la
hashtable_size variable global, que

19
00:01:05,450 --> 00:01:08,640
va a començar com 0, i és
realitzarà un seguiment de la quantitat de paraules

20
00:01:08,640 --> 00:01:10,080
estaven en el nostre diccionari.

21
00:01:10,080 --> 00:01:10,760
Està bé.

22
00:01:10,760 --> 00:01:13,190
>> Així que donem una ullada a la càrrega.

23
00:01:13,190 --> 00:01:16,390
Així notar que la càrrega,
retorna un bool.

24
00:01:16,390 --> 00:01:20,530
Es torna veritat si va ser amb èxit
carregat i false en cas contrari.

25
00:01:20,530 --> 00:01:23,990
I es necessita un const char * estrelles
diccionari, que és el diccionari

26
00:01:23,990 --> 00:01:25,280
que volem obrir.

27
00:01:25,280 --> 00:01:27,170
Així que això és el primer
que farem.

28
00:01:27,170 --> 00:01:30,420
Anem a fopen el diccionari per
lectura, i tindrem

29
00:01:30,420 --> 00:01:34,700
per assegurar-se que va tenir èxit pel que si
es retorna NULL, llavors no ho vam fer

30
00:01:34,700 --> 00:01:37,440
obrir correctament el diccionari
i hem de tornar false.

31
00:01:37,440 --> 00:01:41,580
>> Però suposant que ho va fer amb èxit
obert, llavors volem llegir la

32
00:01:41,580 --> 00:01:42,400
diccionari.

33
00:01:42,400 --> 00:01:46,210
Així seguirà sonant fins que trobem alguna
raó per sortir d'aquest

34
00:01:46,210 --> 00:01:47,570
bucle que ja veurem.

35
00:01:47,570 --> 00:01:51,780
Així mantenim bucle, i ara anem
a malloc un sol node.

36
00:01:51,780 --> 00:01:56,800
I, per descomptat, hem de error de comprovació
de nou per la qual cosa si mallocing no va tenir èxit

37
00:01:56,800 --> 00:02:00,660
i volem descarregar qualsevol node que
va passar a malloc abans, tanqui la

38
00:02:00,660 --> 00:02:02,590
diccionari i tornar false.

39
00:02:02,590 --> 00:02:07,440
>> Però fent cas omís d'això, suposant
tingut èxit, llavors volem utilitzar fscanf

40
00:02:07,440 --> 00:02:12,400
per llegir una sola paraula del nostre
diccionari de al nostre node.

41
00:02:12,400 --> 00:02:17,310
Així que recordi que la paraula d'entrada-> és el carbó de llenya
memòria intermèdia paraula de longitud més grandària

42
00:02:17,310 --> 00:02:20,300
un que anem a
guardar la paraula polz

43
00:02:20,300 --> 00:02:25,280
Així fscanf va a tornar 1, sempre i
ja que era capaç de llegir correctament un

44
00:02:25,280 --> 00:02:26,750
Paraules de l'arxiu.

45
00:02:26,750 --> 00:02:31,030
>> Si passa, ja sigui un error o s'arriba
al final del fitxer, no ho farà

46
00:02:31,030 --> 00:02:34,950
retorna 1, en aquest cas si no ho fa
retorna 1, finalment anem a trencar

47
00:02:34,950 --> 00:02:37,280
fora d'aquest bucle while.

48
00:02:37,280 --> 00:02:42,770
Així que veiem que una vegada que tinguem èxit
llegir una paraula en

49
00:02:42,770 --> 00:02:48,270
entrada-> paraula, llavors anem per discutir
aquesta paraula utilitzant la nostra funció hash.

50
00:02:48,270 --> 00:02:49,580
Fem una ullada a
la funció hash.

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

52
00:02:52,430 --> 00:02:55,610
>> Així que vostè realment no necessita
per entendre això.

53
00:02:55,610 --> 00:02:59,460
I, de fet, ens vam aturar aquest
funció hash de la Internet.

54
00:02:59,460 --> 00:03:04,010
L'única cosa que cal reconèixer és
que això pren un char * const paraula,

55
00:03:04,010 --> 00:03:08,960
així que està tenint una cadena com a entrada i
tornar un int sense signe com a sortida.

56
00:03:08,960 --> 00:03:12,360
Així que això és tot, una funció hash és, és
pren en una entrada, se li dóna un

57
00:03:12,360 --> 00:03:14,490
índex a la taula hash.

58
00:03:14,490 --> 00:03:18,530
Noteu que estem modding per NUM_BUCKETS
de manera que el valor hash retornat

59
00:03:18,530 --> 00:03:21,730
en realitat és un índex a la taula hash
i no indexa més enllà de la

60
00:03:21,730 --> 00:03:24,320
límits de la matriu.

61
00:03:24,320 --> 00:03:27,855
>> Així que tenint en compte que la funció hash, anem
per discutir la paraula que llegim

62
00:03:27,855 --> 00:03:31,700
del diccionari i després anem
per utilitzar que ha de inserir el

63
00:03:31,700 --> 00:03:33,750
entrada a la taula hash.

64
00:03:33,750 --> 00:03:38,830
Ara, el hash taula hash és el corrent
llista vinculada a la taula hash, i

65
00:03:38,830 --> 00:03:41,410
és molt possible que sigui simplement NULL.

66
00:03:41,410 --> 00:03:45,640
Volem inserir la nostra entrada al
a partir d'aquesta llista enllaçada, i així

67
00:03:45,640 --> 00:03:48,910
tindrem la nostra entrada actual
apuntar al que la taula hash actualment

68
00:03:48,910 --> 00:03:54,030
punts i després anem a emmagatzemar
a la taula hash al hash

69
00:03:54,030 --> 00:03:55,350
l'entrada actual.

70
00:03:55,350 --> 00:03:59,320
>> Així doncs, aquestes dues línies s'insereixen amb èxit
l'entrada al principi de la

71
00:03:59,320 --> 00:04:02,270
llista enllaçada en aquest índex
a la taula hash.

72
00:04:02,270 --> 00:04:04,900
Un cop hem acabat amb això, sabem
que trobem una altra paraula al

73
00:04:04,900 --> 00:04:07,800
diccionari i que s'incrementen de nou.

74
00:04:07,800 --> 00:04:13,960
Així que seguim fent això fins fscanf
finalment torna alguna cosa no 1

75
00:04:13,960 --> 00:04:18,560
el punt recordar que hem de
entrada gratuïta, pel que fins aquí, ens malloced 1

76
00:04:18,560 --> 00:04:21,329
entrada i tractem de llegir alguna cosa
del diccionari.

77
00:04:21,329 --> 00:04:24,110
I no ens llegim amb èxit
alguna cosa del diccionari en el qual

78
00:04:24,110 --> 00:04:27,440
cas que necessitem per alliberar l'entrada que ens
En realitat mai lloc en la taula hash

79
00:04:27,440 --> 00:04:29,110
i finalment trencar-se.

80
00:04:29,110 --> 00:04:32,750
>> Un cop comencem, hem de veure, bé,
què ens separem perquè hi ha

81
00:04:32,750 --> 00:04:35,840
estava llegint un error de l'arxiu o
què ens separem perquè arribem a

82
00:04:35,840 --> 00:04:37,120
el final de l'arxiu?

83
00:04:37,120 --> 00:04:40,150
Si hi va haver un error, llavors volem
return false perquè la càrrega no ho va fer

84
00:04:40,150 --> 00:04:43,260
èxit, i en el procés, volem
descarregar totes les paraules que llegim

85
00:04:43,260 --> 00:04:45,670
en i tanqueu el fitxer de diccionari.

86
00:04:45,670 --> 00:04:48,740
Assumint que vam tenir èxit, llavors només
encara han de tancar el diccionari

87
00:04:48,740 --> 00:04:51,970
presentar, i finalment tornar cert ja
ens hem carregat amb èxit el

88
00:04:51,970 --> 00:04:53,040
diccionari.

89
00:04:53,040 --> 00:04:54,420
I això és tot per la càrrega.

90
00:04:54,420 --> 00:04:59,020
>> Així que ara comprovar, donada una taula hash carregat,
que tindrà aquest aspecte.

91
00:04:59,020 --> 00:05:02,690
Per tal de comprovar, torna un bool, que
va a indicar si el

92
00:05:02,690 --> 00:05:07,530
passat com char * paraula, si la
cadena passada-in és al diccionari.

93
00:05:07,530 --> 00:05:10,530
Així que si està al diccionari, si és
en la nostra taula hash, tornarem

94
00:05:10,530 --> 00:05:13,380
veritat, i si no ho és,
anem a tornar false.

95
00:05:13,380 --> 00:05:17,770
Donada aquesta paraula-passatger en, som
anar per discutir la paraula.

96
00:05:17,770 --> 00:05:22,020
>> Ara, una cosa important a reconèixer és
que en la càrrega, sabíem que tots

97
00:05:22,020 --> 00:05:25,820
les paraules serien minúscules,
però aquí, no estem tan segurs.

98
00:05:25,820 --> 00:05:29,510
Si fem una ullada a la nostra funció hash,
nostra funció hash realitat

99
00:05:29,510 --> 00:05:32,700
està en minúscula cada personatge
de la paraula.

100
00:05:32,700 --> 00:05:37,580
Així que, independentment de la capitalització de
paraula, la nostra funció hash es va a

101
00:05:37,580 --> 00:05:42,270
tornar el mateix índex per a qualsevol que sigui el
capitalització és, ja que tindria

102
00:05:42,270 --> 00:05:45,280
tornat per a una completament en minúscules
versió de la paraula.

103
00:05:45,280 --> 00:05:45,950
Està bé.

104
00:05:45,950 --> 00:05:47,410
>> Així que aquest és el nostre índex.

105
00:05:47,410 --> 00:05:49,790
És la taula hash d'aquesta paraula.

106
00:05:49,790 --> 00:05:52,940
Ara, aquest bucle es va
a més de la llista enllaçada

107
00:05:52,940 --> 00:05:55,000
que era en aquest índex.

108
00:05:55,000 --> 00:05:59,630
Així notem que estem inicialitzant entrada
per assenyalar a aquest índex.

109
00:05:59,630 --> 00:06:03,480
Seguirem mentre que l'entrada no
no NULL d'igualtat, i recordar que

110
00:06:03,480 --> 00:06:08,350
actualitzar el punter a la nostra llista enllaçada
entrada és igual a l'entrada-> següent, pel que tenen

111
00:06:08,350 --> 00:06:13,840
nostre punt d'entrada actual a la
següent element de llista enllaçada.

112
00:06:13,840 --> 00:06:14,400
Està bé.

113
00:06:14,400 --> 00:06:19,150
>> Així que per a cada entrada de la llista enllaçada,
utilitzarem strcasecmp.

114
00:06:19,150 --> 00:06:23,780
No és strcmp perquè una vegada més, hem
voler fer si les coses minúscules.

115
00:06:23,780 --> 00:06:28,830
Així que fem servir strcasecmp comparar la paraula
que es va fer passar a aquesta funció

116
00:06:28,830 --> 00:06:31,860
en contra de la paraula que
és en aquesta entrada.

117
00:06:31,860 --> 00:06:35,570
Si retorna 0, que significa que hi va haver
un partit, en el qual cas que vulguem

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

119
00:06:36,630 --> 00:06:39,590
Ens trobem amb èxit el
paraula en la nostra taula hash.

120
00:06:39,590 --> 00:06:43,040
>> Si no hi havia un partit, llavors estem
anar a la volta de nou i mirar el

121
00:06:43,040 --> 00:06:43,990
següent entrada.

122
00:06:43,990 --> 00:06:47,640
I continuarem bucle mentre que hi ha
són entrades d'aquesta llista enllaçada.

123
00:06:47,640 --> 00:06:50,160
Què passa si trenquem
fora d'aquest bucle?

124
00:06:50,160 --> 00:06:55,110
Això vol dir que no trobem una entrada que
aparellat aquesta paraula, en aquest cas

125
00:06:55,110 --> 00:07:00,220
tornem false per indicar que la nostra
taula hash no conté aquesta paraula.

126
00:07:00,220 --> 00:07:01,910
I això és tot per xec.

127
00:07:01,910 --> 00:07:02,540
Està bé.

128
00:07:02,540 --> 00:07:04,790
>> Així que donem una ullada a mida.

129
00:07:04,790 --> 00:07:09,280
Ara, la mida serà bastant simple
recordar ja que en la càrrega, per a cada paraula

130
00:07:09,280 --> 00:07:12,880
ens trobem que s'incrementa un mundial
hashtable_size variable.

131
00:07:12,880 --> 00:07:15,830
Així la funció de mida és només
va a tornar aquest mundial

132
00:07:15,830 --> 00:07:18,150
variables, i això és tot.

133
00:07:18,150 --> 00:07:22,300
>> Ara, per fi, hem de descarregar el
diccionari una vegada que tot està fet.

134
00:07:22,300 --> 00:07:25,340
Llavors, com farem això?

135
00:07:25,340 --> 00:07:30,440
Aquí, estem en bucle sobre tots
cubs de la nostra taula hash.

136
00:07:30,440 --> 00:07:33,240
Així que hi ha NUM_BUCKETS cubs.

137
00:07:33,240 --> 00:07:37,490
I per a cada llista enllaçada a la nostra haixix
taula, anem a llaç sobre el

138
00:07:37,490 --> 00:07:41,070
totalitat de la llista enllaçada
l'alliberament de cada element.

139
00:07:41,070 --> 00:07:46,070
Ara, hem de ser curosos, així que aquí estem
tenir una variable temporal que és

140
00:07:46,070 --> 00:07:49,740
emmagatzemar el punter a la següent
element de la llista enllaçada.

141
00:07:49,740 --> 00:07:52,140
I després anem a la lliure
l'element actual.

142
00:07:52,140 --> 00:07:55,990
>> Hem d'estar segurs que fem això des que
no pot simplement alliberar l'element actual

143
00:07:55,990 --> 00:07:59,260
i després tractar d'accedir a la següent punter
ja que una vegada que alliberem a la

144
00:07:59,260 --> 00:08:00,870
la memòria no és vàlida.

145
00:08:00,870 --> 00:08:04,990
Així que hem de mantenir al voltant d'un punter a
el següent element, llavors podem alliberar el

146
00:08:04,990 --> 00:08:08,360
element actual, i llavors podem actualitzar
nostra element actual per apuntar a

147
00:08:08,360 --> 00:08:09,590
el següent element.

148
00:08:09,590 --> 00:08:12,770
>> Anem bucle while hi ha elements
en aquesta llista enllaçada.

149
00:08:12,770 --> 00:08:16,450
Farem això en totes les llistes vinculades a
la taula hash, i un cop haguem acabat

150
00:08:16,450 --> 00:08:20,180
amb això, que hem descarregat completament
la taula hash, i hem acabat.

151
00:08:20,180 --> 00:08:24,050
Així que és impossible que es descarrega alhora
return false, i quan haguem acabat, ens

152
00:08:24,050 --> 00:08:25,320
simplement torni true.

153
00:08:25,320 --> 00:08:27,563