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
Jien Rob, u hash ejja
din is-soluzzjoni out.

4
00:00:16,210 --> 00:00:20,070
Allura hawnhekk aħna qed tmur biex jimplimentaw
tabella hash ġenerali.

5
00:00:20,070 --> 00:00:24,090
Naraw li l-node Struct ta 'hash tagħna
tabella hija ser teżamina bħal dan.

6
00:00:24,090 --> 00:00:28,710
Allura li għaddej biex ikollhom kelma char
firxa ta 'tul daqs plus 1.

7
00:00:28,710 --> 00:00:32,259
Tinsiex l-1 sa l-massimu
kelma fid-dizzjunarju huwa 45

8
00:00:32,259 --> 00:00:35,110
karattri, u allura aħna qed tmur biex
bżonn karattru wieħed żejda għall-

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

10
00:00:37,070 --> 00:00:40,870
>> U mbagħad tabella hash tagħna f'kull
barmil se taħżen

11
00:00:40,870 --> 00:00:42,320
lista marbuta ta 'nodes.

12
00:00:42,320 --> 00:00:44,420
Aħna mhux qed tagħmel lineari probing hawn.

13
00:00:44,420 --> 00:00:48,430
U dan sabiex link għall-ieħor
element fil-barmil, għandna bżonn

14
00:00:48,430 --> 00:00:51,110
node Struct * jmiss.

15
00:00:51,110 --> 00:00:53,090
Allura dan huwa dak node Dehra.

16
00:00:53,090 --> 00:00:56,180
Issa, hawnhekk huwa d-dikjarazzjoni
ta 'tabella hash tagħna.

17
00:00:56,180 --> 00:01:01,910
Huwa ser ikollhom 16384 bramel, iżda
dak in-numru ma verament kwistjoni.

18
00:01:01,910 --> 00:01:05,450
U fl-aħħarnett, aħna qed tmur biex ikollhom l-
hashtable_size varjabbli globali, li

19
00:01:05,450 --> 00:01:08,640
se jibda off bħala 0, u huwa
se jżommu rekord ta 'kemm kliem

20
00:01:08,640 --> 00:01:10,080
kienu dizzjunarju tagħna.

21
00:01:10,080 --> 00:01:10,760
Kull dritt.

22
00:01:10,760 --> 00:01:13,190
>> Mela ejja tagħti ħarsa lejn tagħbija.

23
00:01:13,190 --> 00:01:16,390
Allura avviż li tagħbija,
dan jirritorna a bool.

24
00:01:16,390 --> 00:01:20,530
Inti tirritorna veru jekk kien b'suċċess
mgħobbija u falza mod ieħor.

25
00:01:20,530 --> 00:01:23,990
U li tieħu const char * star
dizzjunarju, li hija l-dizzjunarju

26
00:01:23,990 --> 00:01:25,280
li aħna rridu li tiftaħ.

27
00:01:25,280 --> 00:01:27,170
Allura dak hu l-ewwel ħaġa
aħna qed tmur biex tagħmel.

28
00:01:27,170 --> 00:01:30,420
Aħna ser fopen-dizzjunarju għal
qari, u aħna qed tmur biex ikollhom

29
00:01:30,420 --> 00:01:34,700
biex tiżgura li hija rnexxielha hekk jekk
huwa lura NULL, allura aħna ma

30
00:01:34,700 --> 00:01:37,440
miftuħa b'suċċess-dizzjunarju
u għandna bżonn li jirritornaw falza.

31
00:01:37,440 --> 00:01:41,580
>> Iżda jekk wieħed jassumi li għamlet b'suċċess
miftuħa, allura aħna trid taqra l-

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

33
00:01:42,400 --> 00:01:46,210
Sabiex iżommu looping sakemm insibu xi
raġuni għal break out ta 'dan

34
00:01:46,210 --> 00:01:47,570
loop li aħna ser tara.

35
00:01:47,570 --> 00:01:51,780
Sabiex iżommu looping, u issa aħna qed tmur
għall malloc node wieħed.

36
00:01:51,780 --> 00:01:56,800
U naturalment, għandna bżonn ta 'żball verifika
darb'oħra hekk jekk mallocing ma rnexxilhomx

37
00:01:56,800 --> 00:02:00,660
u rridu li jħottu kwalunkwe node li aħna
ġara malloc qabel, tagħlaq il-

38
00:02:00,660 --> 00:02:02,590
dizzjunarju u r-ritorn foloz.

39
00:02:02,590 --> 00:02:07,440
>> Iżda jinjora li, jekk wieħed jassumi aħna
irnexxielu, allura irridu li jużaw fscanf

40
00:02:07,440 --> 00:02:12,400
biex jaqraw kelma waħda minn tagħna
dizzjunarju fis node tagħna.

41
00:02:12,400 --> 00:02:17,310
Mela ftakar li word-dħul> hija l-char
buffer kelma ta 'tul daqs plus

42
00:02:17,310 --> 00:02:20,300
wieħed li aħna qed tmur biex
jaħżnu l-kelma pulzieri

43
00:02:20,300 --> 00:02:25,280
Allura fscanf se jirritorna 1 sakemm
kif kien kapaċi b'suċċess jaqra

44
00:02:25,280 --> 00:02:26,750
kelma mill-fajl.

45
00:02:26,750 --> 00:02:31,030
>> Jekk la l-iżball iseħħ jew nilħqu
l-aħħar tal-fajl, mhux se

46
00:02:31,030 --> 00:02:34,950
ritorn 1 f'liema każ jekk ma
ritorn 1, aħna qed finalment se break

47
00:02:34,950 --> 00:02:37,280
minn dan loop waqt.

48
00:02:37,280 --> 00:02:42,770
Allura naraw li ladarba aħna rnexxielna
aqra kelma in

49
00:02:42,770 --> 00:02:48,270
dħul-> kelma, allura aħna qed tmur biex issir hash
din il-kelma li jużaw funzjoni hash tagħna.

50
00:02:48,270 --> 00:02:49,580
Ejja tagħti ħarsa lejn
il-funzjoni hash.

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

52
00:02:52,430 --> 00:02:55,610
>> Allura inti ma verament bżonn
biex jifhmu dan.

53
00:02:55,610 --> 00:02:59,460
U fil-fatt, aħna biss jinġibed dan
hash funzjoni mill-internet.

54
00:02:59,460 --> 00:03:04,010
L-unika ħaġa li għandek bżonn biex jirrikonoxxu hija
li dan jieħu const char * kelma,

55
00:03:04,010 --> 00:03:08,960
Allura huwa tieħu string bħala input u
jirritorna int mhux iffirmat bħala output.

56
00:03:08,960 --> 00:03:12,360
Hekk li kollox funzjoni hash, huwa
jieħu fl input, li tagħtik

57
00:03:12,360 --> 00:03:14,490
indiċi fit-tabella hash.

58
00:03:14,490 --> 00:03:18,530
Avviż li aħna qed modding mill NUM_BUCKETS
hekk il-valur hash lura

59
00:03:18,530 --> 00:03:21,730
attwalment huwa indiċi fit-tabella hash
u ma indiċi lil hinn mill-

60
00:03:21,730 --> 00:03:24,320
limiti ta 'l-array.

61
00:03:24,320 --> 00:03:27,855
>> Allura peress li funzjoni hash, aħna qed tmur
biex hash-kelma li naqraw

62
00:03:27,855 --> 00:03:31,700
mill-dizzjunarju u allura aħna qed tmur
għall-użu li għandha tiddaħħal l-

63
00:03:31,700 --> 00:03:33,750
dħul fis-tabella hash.

64
00:03:33,750 --> 00:03:38,830
Issa, hash hashtable hija l-kurrent
lista marbuta fit-tabella hash, u

65
00:03:38,830 --> 00:03:41,410
huwa ferm possibbli li huwa biss NULL.

66
00:03:41,410 --> 00:03:45,640
Aħna rridu li daħħal id-dħul tagħna fl-
bidu ta 'din il-lista marbuta, u għalhekk

67
00:03:45,640 --> 00:03:48,910
aħna qed tmur biex ikollhom dħul attwali tagħna
punt li dak l-tabella hash bħalissa

68
00:03:48,910 --> 00:03:54,030
punti li u allura aħna qed tmur biex jaħżnu
fit-tabella hash fil-hash

69
00:03:54,030 --> 00:03:55,350
id-dħul attwali.

70
00:03:55,350 --> 00:03:59,320
>> Allura dawn iż-żewġ linji b'suċċess daħħal
id-dħul fil-bidu tal-

71
00:03:59,320 --> 00:04:02,270
lista marbuta f'dak l-indiċi
fit-tabella hash.

72
00:04:02,270 --> 00:04:04,900
Ladarba aħna qed isir ma 'dan, nafu
li sibna kelma oħra fil-

73
00:04:04,900 --> 00:04:07,800
dizzjunarju u aħna inkrement darb'oħra.

74
00:04:07,800 --> 00:04:13,960
Allura aħna iżommu tagħmel li sakemm fscanf
finalment jirritorna xi ħaġa non 1 fi

75
00:04:13,960 --> 00:04:18,560
li punt ftakar li għandna bżonn li
dħul mingħajr, so up here, aħna malloced l

76
00:04:18,560 --> 00:04:21,329
dħul u aħna ppruvaw biex taqra xi ħaġa
mill-dizzjunarju.

77
00:04:21,329 --> 00:04:24,110
U aħna ma taqra b'suċċess
xi ħaġa mill-dizzjunarju li fih

78
00:04:24,110 --> 00:04:27,440
każ għandna bżonn li ħielsa l-entrata li aħna
qatt effettivament imqiegħda fiċ-tabella hash

79
00:04:27,440 --> 00:04:29,110
u finalment break.

80
00:04:29,110 --> 00:04:32,750
>> Ladarba aħna break out, jeħtieġ li naraw, ukoll,
aħna ma break out għaliex hemm

81
00:04:32,750 --> 00:04:35,840
kien żball qari mill-fajl, jew
aħna ma break out għaliex aħna laħaq

82
00:04:35,840 --> 00:04:37,120
l-aħħar tal-fajl?

83
00:04:37,120 --> 00:04:40,150
Jekk kien hemm żball, allura irridu
ritorn foloz minħabba tagħbija ma

84
00:04:40,150 --> 00:04:43,260
tirnexxi, u fil-proċess, irridu
jħottu l-kliem kollha li naqraw

85
00:04:43,260 --> 00:04:45,670
fi u tagħlaq il-fajl dizzjunarju.

86
00:04:45,670 --> 00:04:48,740
Jekk wieħed jassumi aħna ma tirnexxi, allura aħna biss
xorta jeħtieġ li tagħlaq il-dizzjunarju

87
00:04:48,740 --> 00:04:51,970
fajl, u finalment ritorn vera peress
konna mgħobbija b'suċċess il-

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

89
00:04:53,040 --> 00:04:54,420
U li hu għal tagħbija.

90
00:04:54,420 --> 00:04:59,020
>> Allura issa jiċċekkjaw, minħabba tabella hash mgħobbija,
se teżamina bħal dan.

91
00:04:59,020 --> 00:05:02,690
Sabiex jiċċekkjaw, huwa jirritorna bool, li
se jindikaw jekk l-

92
00:05:02,690 --> 00:05:07,530
'għadda fil char * kelma, jekk il-
għaddew fil-sekwenza huwa dizzjunarju tagħna.

93
00:05:07,530 --> 00:05:10,530
Hekk jekk huwa fl-dizzjunarju, jekk huwa
fit-tabella hash tagħna, aħna se terġa 'lura

94
00:05:10,530 --> 00:05:13,380
vera, u jekk mhuwiex,
aħna se terġa 'lura falza.

95
00:05:13,380 --> 00:05:17,770
Minħabba din il-kelma għadda-in, aħna qed
ser hash-kelma.

96
00:05:17,770 --> 00:05:22,020
>> Issa, ħaġa importanti li jirrikonoxxu hija
li fl-tagħbija, aħna kien jaf li kollha ta '

97
00:05:22,020 --> 00:05:25,820
il-kliem kienu ser ikunu minuskuli,
iżda hawnhekk, aħna mhux qed hekk żgur.

98
00:05:25,820 --> 00:05:29,510
Jekk nieħdu ħarsa lejn funzjoni hash tagħna,
funzjoni hash tagħna attwalment

99
00:05:29,510 --> 00:05:32,700
huwa lowercasing kull karattru
tal-kelma.

100
00:05:32,700 --> 00:05:37,580
Allura irrispettivament mill-kapitalizzazzjoni ta '
kelma, funzjoni hash tagħna se

101
00:05:37,580 --> 00:05:42,270
jirritorna l-istess indiċi għal kwalunkwe l-
kapitalizzazzjoni huwa kif kien ikun

102
00:05:42,270 --> 00:05:45,280
lura għal kollox lowercase
verżjoni tal-kelma.

103
00:05:45,280 --> 00:05:45,950
Kull dritt.

104
00:05:45,950 --> 00:05:47,410
>> Allura dak indiċi tagħna.

105
00:05:47,410 --> 00:05:49,790
Hu l-tabella hash għal din il-kelma.

106
00:05:49,790 --> 00:05:52,940
Issa, dan għal loop va
għal aktar minn l-lista marbuta

107
00:05:52,940 --> 00:05:55,000
li kienet f'dak l-indiċi.

108
00:05:55,000 --> 00:05:59,630
Allura avviż aħna initializing dħul
għall-punt li l-indiċi.

109
00:05:59,630 --> 00:06:03,480
Aħna ser ikomplu filwaqt li dħul ma
mhux NULL ugwali, u ftakar li

110
00:06:03,480 --> 00:06:08,350
taġġorna l-pointer fil-lista marbuta tagħna
dħul ugwali dħul-> jmiss, sabiex ikollhom

111
00:06:08,350 --> 00:06:13,840
punt tagħna dħul kurrenti għall-
punt li jmiss fil-lista marbuta.

112
00:06:13,840 --> 00:06:14,400
Kull dritt.

113
00:06:14,400 --> 00:06:19,150
>> Allura għal kull entrata fil-lista marbuta,
aħna qed tmur għall-użu strcasecmp.

114
00:06:19,150 --> 00:06:23,780
Mhuwiex strcmp għaliex għal darb'oħra, aħna
tixtieq li tagħmel affarijiet każ insensitively.

115
00:06:23,780 --> 00:06:28,830
Allura aħna nużaw strcasecmp biex iqabblu l-kelma
li kien mgħoddi lill din il-funzjoni

116
00:06:28,830 --> 00:06:31,860
kontra l-kelma li
huwa f'din l-entrata.

117
00:06:31,860 --> 00:06:35,570
Jekk dan jirritorna 0, dan ifisser li kien hemm
taqbila, f'liema każ rridu

118
00:06:35,570 --> 00:06:36,630
ritorn vera.

119
00:06:36,630 --> 00:06:39,590
Aħna b'suċċess sabet il-
kelma fit-tabella hash tagħna.

120
00:06:39,590 --> 00:06:43,040
>> Jekk ma kienx hemm taqbila, allura aħna qed
ser loop darb'oħra u ħarsa lejn il-

121
00:06:43,040 --> 00:06:43,990
dħul li jmiss.

122
00:06:43,990 --> 00:06:47,640
U aħna ser tkompli looping filwaqt li hemm
iskrizzjonijiet f'din il-lista marbuta.

123
00:06:47,640 --> 00:06:50,160
X'jiġri jekk aħna break
minn dan għal loop?

124
00:06:50,160 --> 00:06:55,110
Dan ifisser li aħna ma sabx ta 'dħul li
mqabbla din il-kelma, f'liema każ

125
00:06:55,110 --> 00:07:00,220
nerġgħu lura falza li tindika li tagħna
tabella hash ma kinitx tinkludi din il-kelma.

126
00:07:00,220 --> 00:07:01,910
U li huwa għal kontroll.

127
00:07:01,910 --> 00:07:02,540
Kull dritt.

128
00:07:02,540 --> 00:07:04,790
>> Mela ejja tagħti ħarsa lejn id-daqs.

129
00:07:04,790 --> 00:07:09,280
Issa, id-daqs se tkun pjuttost sempliċi
peress li tiftakar fit-tagħbija, għal kull kelma

130
00:07:09,280 --> 00:07:12,880
sibna aħna jiżdied globali
hashtable_size varjabbli.

131
00:07:12,880 --> 00:07:15,830
Allura l-funzjoni daqs huwa biss
ser jirritorna dik globali

132
00:07:15,830 --> 00:07:18,150
varjabbli, u thats it.

133
00:07:18,150 --> 00:07:22,300
>> Issa finalment, għandna bżonn li jħottu l-
dizzjunarju ladarba kollox isir.

134
00:07:22,300 --> 00:07:25,340
Allura kif huma aħna se tagħmel dan?

135
00:07:25,340 --> 00:07:30,440
Dritt hawn, aħna qed looping fuq kollha
bramel ta 'tabella hash tagħna.

136
00:07:30,440 --> 00:07:33,240
Allura hemm bramel NUM_BUCKETS.

137
00:07:33,240 --> 00:07:37,490
U għal kull lista marbuta hash tagħna
mejda, aħna qed tmur biex loop madwar id-

138
00:07:37,490 --> 00:07:41,070
intier tal-lista marbuta
ħelsien kull element.

139
00:07:41,070 --> 00:07:46,070
Issa, għandna bżonn li tkun attenta, so here we
jkollhom varjabbli temporanja li l-

140
00:07:46,070 --> 00:07:49,740
ħażna tal-pointer għall-ieħor
element fil-lista marbuta.

141
00:07:49,740 --> 00:07:52,140
U allura aħna qed tmur għall-free
l-element attwali.

142
00:07:52,140 --> 00:07:55,990
>> Għandna bżonn biex tkun ċert nagħmlu dan peress li aħna
tista 'mhux biss ħielsa l-element attwali

143
00:07:55,990 --> 00:07:59,260
u mbagħad jippruvaw jaċċessaw l-pointer li jmiss
peress li ladarba aħna meħlusa dan l-

144
00:07:59,260 --> 00:08:00,870
memorja ssir invalida.

145
00:08:00,870 --> 00:08:04,990
Għalhekk għandna bżonn li jżommu madwar pointer biex
l-element li jmiss, allura nistgħu ħielsa l-

146
00:08:04,990 --> 00:08:08,360
element attwali, u allura nistgħu taġġorna
element attwali tagħna għall-punt li

147
00:08:08,360 --> 00:08:09,590
l-element li jmiss.

148
00:08:09,590 --> 00:08:12,770
>> Aħna ser loop filwaqt li hemm elementi
f'din il-lista marbuta.

149
00:08:12,770 --> 00:08:16,450
Aħna ser tagħmel dan għal-listi kollha marbuta b'mod
-tabella hash, u ladarba aħna qed isir

150
00:08:16,450 --> 00:08:20,180
ma 'dan, konna kompletament maħtuta
-tabella hash, u aħna qed isir.

151
00:08:20,180 --> 00:08:24,050
Allura huwa impossibbli għall tħott li qatt
ritorn foloz, u meta aħna qed isir, aħna

152
00:08:24,050 --> 00:08:25,320
biss ritorn vera.

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