1
00:00:00,000 --> 00:00:02,740
[Powered by Google Translate] [Walkthrough - Problemo Serio 5]

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

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

4
00:00:07,190 --> 00:00:10,400
>> Bone. Saluton, ĉiuj, kaj bonvenon al Walkthrough 5.

5
00:00:10,400 --> 00:00:17,400
>> Pset5 estas fuŝo, en kiu ni estos preni literumilo.

6
00:00:17,400 --> 00:00:21,030
Literumi-kontroliloj estas ege grava.

7
00:00:21,030 --> 00:00:23,390
Ĉu ĉi tiu iam okazis al vi?

8
00:00:23,390 --> 00:00:27,170
Vi laboras tre, tre hoard sur papero por kolizio

9
00:00:27,170 --> 00:00:33,120
kaj tiam ankoraŭ fini atingi tre ardo Rade kiel D aŭ D =

10
00:00:33,120 --> 00:00:39,390
kaj ĉiuj ĉar vi estas la liverwurst spoiler en la baleno larĝa vorto.

11
00:00:39,390 --> 00:00:44,710
Jes, provlegado vian kapsikoj estas afero de la, la plej granda senpoveco.

12
00:00:44,710 --> 00:00:49,140
Tio estas problemo kiu tuŝas vireca, vireca studentoj.

13
00:00:49,140 --> 00:00:56,260
Mi iam diris per mia sith lernojaro torturador ke mi neniam en bonan kolego.

14
00:00:56,260 --> 00:01:00,250
Kaj tio estas ĉio, kion mi iam volis, ke ĉio ajn knabo volas en mia aĝo,

15
00:01:00,250 --> 00:01:04,569
nur por eniri bonan kolego.

16
00:01:04,569 --> 00:01:12,720
Kaj ne nur iu kolego. Ne, mi volis iri al Ebur Juraj kolego.

17
00:01:12,720 --> 00:01:18,360
Do, se mi ne plibonigo, foriris estus miaj sonĝoj de iri al Harvard,

18
00:01:18,360 --> 00:01:22,730
Jale, aŭ Malliberejo - vi scias, en malliberejo, New Jersey.

19
00:01:22,730 --> 00:01:25,170
Do mi atingis min literumilo.

20
00:01:25,170 --> 00:01:29,380
Tio estas iom ekstrakto de unu el miaj preferataj parolata vorto artistoj, Taylor Malio.

21
00:01:29,380 --> 00:01:34,630
Ĉiuokaze, kiel li diras, la graveco de havi literumilo estas tre grava.

22
00:01:34,630 --> 00:01:39,440
>> Do bonvena Walkthrough 5, en kiu ni parolos pri pset5: fuŝo,

23
00:01:39,440 --> 00:01:44,300
en kiu ni faros nian plej propra literumilo.

24
00:01:44,300 --> 00:01:50,880
La iloj por ĉi tiu semajno, la dissendo kodo, tuj estos grava por rigardi

25
00:01:50,880 --> 00:01:54,950
nur kompreni la malsamajn funkciojn, ke via vortaro tuj havos.

26
00:01:54,950 --> 00:02:01,500
Ni efektive tuj estos havi multnombraj. C dosierojn kiuj kune fari nian pset.

27
00:02:01,500 --> 00:02:05,420
Kaj tiel rigardante tra la diversaj aspektoj, kvankam ni fakte ne redaktado

28
00:02:05,420 --> 00:02:10,770
unu el la dosieroj, speller.c, sciante kiel ĝi funkcias kun rilato al dictionary.c,

29
00:02:10,770 --> 00:02:14,100
kiuj ni skribos, tuj estos bela grava.

30
00:02:14,100 --> 00:02:16,970
La pset spec ankaŭ enhavas multajn utilajn informojn

31
00:02:16,970 --> 00:02:21,360
en terminoj de aĵoj kiujn vi povas supozi, reguloj kaj aĵoj kiel tiu,

32
00:02:21,360 --> 00:02:24,710
tiel certe legis la pset spec zorgeme por konsiloj.

33
00:02:24,710 --> 00:02:29,310
Kaj kiam en dubo de regulo aŭ io simila, tiam ĉiam rilatas al la pset spec

34
00:02:29,310 --> 00:02:31,550
aŭ Discuss.

35
00:02:31,550 --> 00:02:34,060
Ĉi pset tuj fidas peze sur punteros,

36
00:02:34,060 --> 00:02:37,890
do ni volas certigi, ke ni komprenas la diferencon inter aldonante steloj

37
00:02:37,890 --> 00:02:41,680
antaŭ la puntero la nomon kaj ampersands, kiom por liberigi ilin, ktp

38
00:02:41,680 --> 00:02:47,550
Do estante mastro punteros tuj estos tre utila en ĉi tiu problemo aro.

39
00:02:47,550 --> 00:02:50,460
Ni tuj rigardi en ligitaj listoj iom pli,

40
00:02:50,460 --> 00:02:57,790
kie ni havas elementojn kiuj ni nomas nodoj kiuj havas ambaŭ valoro tiel kiel puntero

41
00:02:57,790 --> 00:03:02,520
al la sekvanta nodo, kaj tiel esence ligas malsamaj elementoj unu post la alia.

42
00:03:02,520 --> 00:03:07,190
Estas kelkaj malsamaj ebloj de apliko vian realan vortaro.

43
00:03:07,190 --> 00:03:13,150
Ni tuj serĉos en du ĉefaj manieroj, kiu estas hash tabloj kaj poste provas.

44
00:03:13,150 --> 00:03:17,660
En ambaŭ el tiuj, ili implicas ian nocion de ligitaj listo

45
00:03:17,660 --> 00:03:20,790
kie vi elementoj ligitaj unu al la alia.

46
00:03:20,790 --> 00:03:25,640
Kaj tial ni tuj serĉos pri kiel vi eble povus funkcii ĉirkaŭ ligitaj lertaj,

47
00:03:25,640 --> 00:03:29,680
krei ilin, navigi en terminoj de kiel, ekzemple, enŝovu nodo en ĝin

48
00:03:29,680 --> 00:03:32,760
aŭ libera ĉiuj nodoj tiel.

49
00:03:32,760 --> 00:03:34,740
En terminoj de liberigante nodoj, kiuj estas vere gravaj

50
00:03:34,740 --> 00:03:37,700
ke ĉiufoje kiam ni malloc memoro, poste ni liberigi ĝin.

51
00:03:37,700 --> 00:03:42,910
Do ni volas certigi, ke neniu puntero iras unfreed, ke ni ne havas ajnan memoro likas.

52
00:03:42,910 --> 00:03:48,330
Ni tuj enkonduki ilon nomata Valgrind kiu kuras via programo

53
00:03:48,330 --> 00:03:52,260
kaj ĉekojn ĉu ĉiuj memoro kiun vi destinis estas tiam liberigita.

54
00:03:52,260 --> 00:03:59,080
Via pset nur kompletigi kiam ĝi funkcias kaj ĝi havas tutajn funkciojn,

55
00:03:59,080 --> 00:04:03,990
sed ankaŭ, Valgrind informas vin, ke vi ne trovis ajnan memoro likas.

56
00:04:03,990 --> 00:04:06,690
Fine, por ĉi pset, mi vere volas substreki -

57
00:04:06,690 --> 00:04:11,360
Mi volas diri, kiel kutime, mi estas definitive subtenanto de uzi plumon kaj paperon por via problemo aroj,

58
00:04:11,360 --> 00:04:14,840
sed por ĉi tiu, mi kredas ke plumo kaj papero tuj estos speciale grava

59
00:04:14,840 --> 00:04:19,000
kiam vi volas esti desegnante sagojn por aĵoj kaj kompreni kiel aferoj funkcias.

60
00:04:19,000 --> 00:04:24,440
Do certe klopodos uzi plumon kaj paperon por desegni aferojn de antaŭ vi get kodigo

61
00:04:24,440 --> 00:04:26,970
ĉar ĝi povus akiri iom senorda.

62
00:04:26,970 --> 00:04:30,700
>> Unue, ni iru en ligitaj listoj iom.

63
00:04:30,700 --> 00:04:35,510
Ligitaj listoj konsistas nodoj, kie ĉiu vertico havas valoro asociita kun ĝi,

64
00:04:35,510 --> 00:04:39,810
tiel kiel sagon al la sekva nodo post tio.

65
00:04:39,810 --> 00:04:43,680
Paro de aferoj gravaj kun la ligitaj listoj estas ke ni devas memori

66
00:04:43,680 --> 00:04:48,810
kie nia unua nodo estas, kaj tiam iam ni scios kie la unua nodo estas,

67
00:04:48,810 --> 00:04:52,990
tiel ni povas konsenti la nodo kiu la unua nodo punktoj al

68
00:04:52,990 --> 00:04:55,850
kaj poste unu post tio kaj la post tio.

69
00:04:55,850 --> 00:05:00,340
Kaj tiam la lasta elemento en via ligitaj listo estas ke nodo puntero

70
00:05:00,340 --> 00:05:02,340
ĉiam tuj indikas nula.

71
00:05:02,340 --> 00:05:08,230
Kiam nodo punktoj al nula, tiam vi scias, ke vi atingis la finon de la listo,

72
00:05:08,230 --> 00:05:12,320
ke tiu nodo estas la lasta, kiu tie estas nenio post tio.

73
00:05:12,320 --> 00:05:16,970
Ĉi tie en ĉi esquemática, vi vidas ke la sagoj estas la punteros,

74
00:05:16,970 --> 00:05:20,290
kaj la blua sekcio kie la valoro estas stokita,

75
00:05:20,290 --> 00:05:24,420
kaj tiam la ruĝan skatolon kun la puntero al ĝi estas la nodo puntero

76
00:05:24,420 --> 00:05:27,050
montrante la sekva nodo post tio.

77
00:05:27,050 --> 00:05:33,730
Kaj tial vi vidas tie, la D nodo notus al nula ĉar ĝi estas la lasta elemento en la listo.

78
00:05:33,730 --> 00:05:38,240
>> Ni rigardu kiel ni povus difini struct por nodo.

79
00:05:38,240 --> 00:05:40,130
Kaj ĉar ni volas havi plurajn nodoj,

80
00:05:40,130 --> 00:05:43,180
ĉi tuj fariĝi typedef struct

81
00:05:43,180 --> 00:05:46,870
en kiu ni iras al havi kelkaj malsamaj kazoj de nodoj.

82
00:05:46,870 --> 00:05:50,850
Kaj tial ni difini ĝin kiel nova datumtipo.

83
00:05:50,850 --> 00:05:53,630
Tie, ni havas typedef struct nodo.

84
00:05:53,630 --> 00:05:56,160
En ĉi tiu ekzemplo, ni pritraktas entjero nodoj,

85
00:05:56,160 --> 00:06:00,490
do ni havos entjero nomata valoro kaj tiam ni havas alian pointer,

86
00:06:00,490 --> 00:06:07,390
kaj en ĉi tiu kazo, ĝi estas puntero al nodo, tial ni havas struct nodo * nomas proksima.

87
00:06:07,390 --> 00:06:09,520
Kaj tiam ni nomas ĉi tiu tuta afero nodo.

88
00:06:09,520 --> 00:06:11,110
Certiĝu, ke vi sekvu tiun sintakson.

89
00:06:11,110 --> 00:06:17,940
Rimarku ke nodo estas reale referenciado super tiel kiel sub la frizita krampoj.

90
00:06:17,940 --> 00:06:23,400
Tiam teni spuro de kie mia unua nodo estas en ĉi ligillisto,

91
00:06:23,400 --> 00:06:29,390
tiam mi havas nodo puntero nomita kapo, kaj mi malloc spaco sufiĉa por la grandeco de nodo.

92
00:06:29,390 --> 00:06:36,240
Rimarki, tamen, ke kapo estas fakte nodo puntero kontraste al efektiva nodo mem.

93
00:06:36,240 --> 00:06:40,130
Do la kapo fakte ne enhavas ajnan valoron,

94
00:06:40,130 --> 00:06:45,590
nur notas al kiom la unua nodo en mia ligitaj listo estas.

95
00:06:55,080 --> 00:06:58,340
>> Por havi pli bonan senson de ligitaj listoj, ĉar ĝi estas tre grava

96
00:06:58,340 --> 00:07:02,220
teni spuro de certigante ke vi subtenas la ĉeno,

97
00:07:02,220 --> 00:07:09,990
Mi ŝatas pensi pri tio kiel homoj en linio tenante manojn,

98
00:07:09,990 --> 00:07:14,330
kie ĉiu persono estas tenante manojn kun la proksima.

99
00:07:14,330 --> 00:07:18,350
Vi ne povas vidi en ĉi desegno, sed esence ili estas montrante al la sekvanta persono

100
00:07:18,350 --> 00:07:23,760
kio estas sur ilia ĉeno.

101
00:07:23,760 --> 00:07:29,270
Kaj do se vi volas trairi ligillisto kie tiuj homoj -

102
00:07:29,270 --> 00:07:32,830
imagi ĉiuj el tiuj homoj havas valorojn asociita kun ili

103
00:07:32,830 --> 00:07:36,590
kaj ankaŭ indikas la proksiman personon en la linio -

104
00:07:36,590 --> 00:07:40,810
se vi volas trairi la ligillisto, ekzemple, al ĉu redakti la valoroj

105
00:07:40,810 --> 00:07:42,830
aŭ serĉu valoro aŭ io simila,

106
00:07:42,830 --> 00:07:48,270
tiam vi volas havi sagon al la specifa persono.

107
00:07:48,270 --> 00:07:52,670
Do ni tuj havos datumtipo nodo puntero.

108
00:07:52,670 --> 00:07:55,580
Por ĉi tiu kazo, ni nomas ĝin kursoro.

109
00:07:55,580 --> 00:07:59,630
Alia komuna maniero nomi tiun estus iterator aŭ io simila

110
00:07:59,630 --> 00:08:05,130
ĉar ĝi estas ripetanta super kaj efektive movante kiu nodo ĝi estas indikante.

111
00:08:05,130 --> 00:08:14,410
Ĉi tie estos nia kursoro.

112
00:08:14,410 --> 00:08:20,180
Nia kursoro estos unuaj indikas la unua elemento en nia listo.

113
00:08:20,180 --> 00:08:26,910
Kaj tiel kion ni volas fari estas ni esence esti kontinuado de la kursoro,

114
00:08:26,910 --> 00:08:29,130
movi ĝin de flanko al flanko.

115
00:08:29,130 --> 00:08:33,409
En ĉi tiu kazo, ni volas movi ĝin al la sekva elemento en la listo.

116
00:08:33,409 --> 00:08:38,480
Kun tabeloj, kion ni devus fari estas ni nur diras, ke ni pliigos la indekso de 1.

117
00:08:38,480 --> 00:08:46,020
En ĉi tiu kazo, kion ni bezonas por fari estas fakte trovi kiu persono tiu fluo persono indikante,

118
00:08:46,020 --> 00:08:48,930
kaj ke tuj estos la venonta valoro.

119
00:08:48,930 --> 00:08:53,230
Do se kursoro estas nur nodo pointer, tiam kion ni volas fari

120
00:08:53,230 --> 00:08:56,320
estas ni volas atingi la valoron kiu la kursoro montrante.

121
00:08:56,320 --> 00:09:01,350
Ni volas atingi ke nodo kaj tiam, iam ni estas en tiu nodo, trovi kie ĝi estas indikante.

122
00:09:01,350 --> 00:09:05,820
Por atingi la realan nodo ke la kursoro estas indikante,

123
00:09:05,820 --> 00:09:13,160
kutime ni indiki ĝin (* kursoro).

124
00:09:13,160 --> 00:09:19,160
Tio donus al vi la reala nodo ke la kursoro montrante.

125
00:09:19,160 --> 00:09:21,730
Kaj tuj poste, kion ni volas fari estas ni volas atingi

126
00:09:21,730 --> 00:09:25,680
kion ajn kiun nodo La sekva valoro estas.

127
00:09:25,680 --> 00:09:32,820
Por fari tion, por aliri la valoroj ene de la struct, ni havas la skalara operatoro.

128
00:09:32,820 --> 00:09:39,530
Tial do tio estus (* kursoro). Proksima.

129
00:09:39,530 --> 00:09:44,840
Sed ĉi tiu estas iom senorda en terminoj de havi la krampoj ĉirkaŭ la * kursoro,

130
00:09:44,840 --> 00:09:56,800
kaj tiel ni anstataŭigi ĉi tiu tuta frazo kun kursoro->.

131
00:09:56,800 --> 00:10:02,700
Tio ĉi estas streko kaj poste iu pli granda ol signo, tiel farante sago.

132
00:10:02,700 --> 00:10:05,840
kursoro-> proksima.

133
00:10:05,840 --> 00:10:12,390
Kiu reale preni al vi la nodo ke la kursoro punktoj al. Ke valoro estas de alia.

134
00:10:12,390 --> 00:10:16,790
Do anstataŭ havi la stelo kaj la skalara, vi anstataŭante ke kun sago.

135
00:10:16,790 --> 00:10:24,820
Esti tre zorgema por certigi ke vi provas uzi tiun sintakson.

136
00:10:33,550 --> 00:10:37,620
>> Nun ke ni havas niajn kursoro, se ni volas atingi la valoron,

137
00:10:37,620 --> 00:10:40,450
antaŭe, ni havis kursoro-> proksima,

138
00:10:40,450 --> 00:10:46,260
sed por aliri la valoro je la nodo ke la kursoro estas indikante, ni nur simple diras

139
00:10:46,260 --> 00:10:48,070
nodo-> valoro.

140
00:10:48,070 --> 00:10:53,600
De tie, ĝi estas de datumtipo ajn ni difinis la valoroj kaj la nodoj esti.

141
00:10:53,600 --> 00:10:59,620
Se temas pri int nodo, tiam kursoro-> valoro estas nur tuj estos entjero.

142
00:10:59,620 --> 00:11:04,870
Do ni povas fari operaciojn sur tiu, kontrolu egalecoj, atribui ĝin malsamaj valoroj, ktp

143
00:11:04,870 --> 00:11:11,090
Tial, kion vi volas fari se vi volas movi vian kursoron al la sekvanta persono,

144
00:11:11,090 --> 00:11:15,270
vi fakte ŝanĝi la valoron de la kursoro.

145
00:11:15,270 --> 00:11:19,340
Ekde kursoro estas nodo pointer, vi ŝanĝas la efektiva puntero adreso

146
00:11:19,340 --> 00:11:23,890
al la adreso de la venonta vertico en via listo.

147
00:11:23,890 --> 00:11:28,930
Tiu estas nur iom da kodo, kie vi povus persisti.

148
00:11:28,930 --> 00:11:31,230
Kie mi havas la komento fari ion,

149
00:11:31,230 --> 00:11:33,850
tie estas kie vi probable tuj aliri la valoro

150
00:11:33,850 --> 00:11:37,850
aŭ fari ion por fari kun tiu specifa nodo.

151
00:11:37,850 --> 00:11:43,050
Por ekigi ĝin, mi diras, ke mia kursoro komence

152
00:11:43,050 --> 00:11:48,430
tuj indikas la unuan elementon en la ligitaj listo.

153
00:11:48,430 --> 00:11:52,910
Kaj tial ĉe antaŭen, mi difinis kiel la kapo de la nodo.

154
00:11:52,910 --> 00:11:57,610
>> Kiel mi menciis antaŭe, liberigante estas vere grava.

155
00:11:57,610 --> 00:12:02,440
Vi volas certigi ke vi liberigi ĉiun eron en la listo iam vi finis kun ĝi.

156
00:12:02,440 --> 00:12:04,940
Kiam vi ne bezonas referenci iun el tiuj indikoj plu,

157
00:12:04,940 --> 00:12:10,620
vi volas certigi ke vi liberigi ĉiuj el tiuj indikoj.

158
00:12:10,620 --> 00:12:14,460
Sed vi volas esti tre zorgema tie en kiun vi volas eviti ajnan memoro likas.

159
00:12:14,460 --> 00:12:25,080
Se vi libera persono antaŭtempe, tiam ĉiuj el la punteros ke tiu nodo punktoj al

160
00:12:25,080 --> 00:12:26,900
tuj estos perdita.

161
00:12:26,900 --> 00:12:32,070
Irante al la persono ekzemple por fari ĝin iom pli altaj palisoj,

162
00:12:32,070 --> 00:12:49,600
ni havas ĉi tiujn personojn, krom en tiu kazo ili ŝvebis super lago kun monstro.

163
00:12:49,600 --> 00:12:53,200
Ni volas certigi ke ĉiufoje kiam ni liberigos, ni ne perdu

164
00:12:53,200 --> 00:12:58,920
kaj lasi iri ajna nodoj antaux ni efektive liberigis ilin.

165
00:12:58,920 --> 00:13:05,730
Ekzemple, se vi estus al simple nomas libera sur ĉi ulo ĉi tie,

166
00:13:05,730 --> 00:13:15,350
tiam li estus liberigita, sed tiam ĉiuj el ĉi tiuj infanoj devus tiam perdiĝos

167
00:13:15,350 --> 00:13:18,450
kaj ili derivas off kaj falos.

168
00:13:18,450 --> 00:13:24,900
Do ni volas certigi, ke anstataŭ, ni volas subteni ligon al la ceteraj.

169
00:13:37,630 --> 00:13:42,480
Nia kapo pointer, kiu notas al la unua ero en la listo.

170
00:13:42,480 --> 00:13:49,990
Estas ia kiel ŝnuro ankrumante la unua persono.

171
00:13:52,870 --> 00:13:57,470
Kion vi volus fari, kiam vi liberigi listo estas havi -

172
00:13:57,470 --> 00:14:04,520
Se vi volas liberigi la unua elemento unue, tiam vi povas havi portempa puntero

173
00:14:04,520 --> 00:14:07,370
ke antaŭ al kiom la unua elemento estas.

174
00:14:07,370 --> 00:14:11,420
Do vi havas vian temporal puntero montrante tie.

175
00:14:11,420 --> 00:14:15,840
Tiel, ni havas regadon de la unua nodo.

176
00:14:15,840 --> 00:14:18,930
Kaj poste, kiam ni scias ke la unua nodo tuj estos liberigita,

177
00:14:18,930 --> 00:14:24,890
tiam ni povas movi ĉi ŝnuro, ĉi ankro, nia kapo,

178
00:14:24,890 --> 00:14:31,930
por fakte indikas kion ajn la unua estas indikante.

179
00:14:31,930 --> 00:14:38,760
Do tiu kapo vere notas al la dua elemento nun.

180
00:14:38,760 --> 00:14:43,980
Nun ni estas permesita por liberigi ajn stokas en temp,

181
00:14:43,980 --> 00:14:53,360
kaj tiel ni povas viŝi ke sen ĝi endanĝerigi ĉiuj aliaj verticoj en nia listo.

182
00:14:54,140 --> 00:15:05,020
Alia maniero, ke vi povus fari tion eblis

183
00:15:05,020 --> 00:15:08,650
ĉiufoje kiam vi simple liberigi la lasta elemento en la listo

184
00:15:08,650 --> 00:15:11,010
ĉar ili estas garantiitaj ne esti indikis nenion.

185
00:15:11,010 --> 00:15:15,570
Do vi povus simple liberigi ĉi tiu, tiam liberaj ĉi tiu, tiam liberaj ĉi tiu.

186
00:15:15,570 --> 00:15:21,900
Tio definitive funkcias sed estas iom pli malrapida pro la naturo de la ligitaj lertaj,

187
00:15:21,900 --> 00:15:24,670
ni ne povas simple tuj salti al la lasta.

188
00:15:24,670 --> 00:15:28,030
Ni devas trairi ĉiu elemento en la ligitaj listo

189
00:15:28,030 --> 00:15:31,020
kaj kontrolu ĉu tio estas atentigo pri nula, kontrolu ĉiufoje,

190
00:15:31,020 --> 00:15:33,780
kaj tiam iam ni atingos la finon, tiam liberaj tio.

191
00:15:33,780 --> 00:15:40,270
Se vi estus fari ĉi procezo, vi vere estas kontrolanta tie,

192
00:15:40,270 --> 00:15:44,190
kontrolanta tie, tiam kontroli tie, liberigante ĝin,

193
00:15:44,190 --> 00:15:47,470
tiam tuj reen, kontrolanta tie, kontrolanta tie, liberigante ĝin,

194
00:15:47,470 --> 00:15:49,660
kontrolanta tie, kaj tiam liberigas ĝin.

195
00:15:49,660 --> 00:15:52,880
Kiu prenas iom pli da tempo. Yeah.

196
00:15:52,880 --> 00:15:59,060
>> [Studento] Ĉu ĝi estas ebla fari ligitaj listo kiu stokas eliron sagon al la fino?

197
00:15:59,060 --> 00:16:01,320
Tio definitive eblus.

198
00:16:01,320 --> 00:16:08,340
Ripeti la demandon, ĉu eblas havi ligitaj listo strukturo

199
00:16:08,340 --> 00:16:12,490
tia, ke vi havas puntero indikante la finon de la ligitaj listo?

200
00:16:12,490 --> 00:16:18,090
Mi dirus ke estas ebla, kaj ĉiufoje, ke vi enmetas ion en vian ligitaj listo

201
00:16:18,090 --> 00:16:21,470
vi devus aktualigi ke puntero kaj aĵoj tiel.

202
00:16:21,470 --> 00:16:26,640
Vi havus nodo * vosto, ekzemple.

203
00:16:26,640 --> 00:16:29,840
Sed kiam vi apliki ĉi tiun funkcion, oni devas pensi pri la komerca-offs,

204
00:16:29,840 --> 00:16:32,700
kiel kiomfoje mi tuj iros ripetanta super tio,

205
00:16:32,700 --> 00:16:36,100
kiel malfacile estas ĝin tuj estos al konservi trako de la vosto kaj ankaŭ la kapo

206
00:16:36,100 --> 00:16:38,400
tiel kiel mia iterator, kaj aferojn tiel.

207
00:16:40,730 --> 00:16:42,480
Ĉu tio -? >> [Studento] Yeah.

208
00:16:42,480 --> 00:16:48,270
Estas ebla, sed en terminoj de dezajno decidoj, vi devas pesi la ebloj.

209
00:16:53,850 --> 00:17:01,090
>> Jen skeleto de kodo kiu permesus vin liberigi ĉiu ero en ligitaj listo.

210
00:17:01,090 --> 00:17:05,460
Denove, ekde mi ripetanta super ligillisto, mi tuj volas havi ian kursoro

211
00:17:05,460 --> 00:17:08,670
aŭ iterator.

212
00:17:08,670 --> 00:17:14,640
Ni ripetanta ĝis la kursoro estas NULL.

213
00:17:14,640 --> 00:17:17,640
Vi ne volas persisti kiam via kursoro estas NULL

214
00:17:17,640 --> 00:17:20,579
ĉar tio signifas ke ne estas nenio en la listo.

215
00:17:20,579 --> 00:17:25,069
Tial jen mi fari portempan nodo *

216
00:17:25,069 --> 00:17:29,610
indikante kion mi konsideras estas la unua de mia listo,

217
00:17:29,610 --> 00:17:35,340
kaj tiam mi movi mian kursoro antaŭen 1 kaj tiam senpaga, kion ajn mi havis en la provizora stokado.

218
00:17:38,460 --> 00:17:43,650
>> Nun ni venas al la enmeto en ligitaj listoj.

219
00:18:00,200 --> 00:18:09,660
Mi havas tri nodoj en mia ligillisto, kaj ni iru al la simpla kazo

220
00:18:09,660 --> 00:18:18,970
kie ni volas enmeti alian nodon al la fino de nia ligitaj listo.

221
00:18:18,970 --> 00:18:25,980
Por fari tion, ĉiuj ni devus fari estas ni trairi

222
00:18:25,980 --> 00:18:32,100
trovi kie la nuna termino de la ligitaj listo estas, do ajn nodo estas indikante nula -

223
00:18:32,100 --> 00:18:33,850
jen ĉi tiu -

224
00:18:33,850 --> 00:18:37,260
kaj tiam diras, fakte, ĉi tiu estas ne tuj estos la lasta nodo;

225
00:18:37,260 --> 00:18:39,830
ni vere havos alian.

226
00:18:39,830 --> 00:18:46,260
Do ni devus tiu fluo unu punkto al kiom ni enmeto.

227
00:18:46,260 --> 00:18:50,080
Do nun tiu ruĝa persono tie igas la lasta nodo en la ligitaj listo.

228
00:18:50,080 --> 00:18:56,080
Kaj tial la trajton de la lasta nodo en la ligitaj listo estas kiu notas al nula.

229
00:18:56,080 --> 00:19:09,380
Tial, kion ni devus fari estas metita ĉi ruĝa ulo la puntero al nula. Tie.

230
00:19:09,380 --> 00:19:25,370
>> Sed kion se ni volis enmeti nodo inter la dua kaj tria?

231
00:19:25,370 --> 00:19:28,960
Tiu ne estas tiom simpla, ĉar ni volas certigi

232
00:19:28,960 --> 00:19:34,290
ke ni ne lasu iri de iu ajn nodo en nia ligitaj listo.

233
00:19:34,290 --> 00:19:43,450
Kion ni devus fari estas certiĝi ke ni ankrumi nin al ĉiu.

234
00:19:43,450 --> 00:19:49,900
Ekzemple, ni nomas tion la dua.

235
00:19:49,900 --> 00:19:54,390
Se vi diris la dua nun notas al ĉi nova

236
00:19:54,390 --> 00:20:02,520
kaj vi ĵus faris puntero tie, tiam tiu okazigus ĉi ulo perdas

237
00:20:02,520 --> 00:20:07,830
ĉar tie ne estas neniu ligo al li.

238
00:20:07,830 --> 00:20:18,970
Anstataŭe - Mi desegni ĉi denove. Pardonu mian artan kapablojn.

239
00:20:18,970 --> 00:20:26,570
Ni scias ke ni ne povas simple rekte ligi 2 al la nova.

240
00:20:26,570 --> 00:20:30,480
Ni devas certigi ke ni tenadi la lasta.

241
00:20:30,480 --> 00:20:39,200
Kion ni volus fari estas havi temporal puntero

242
00:20:39,200 --> 00:20:42,650
al la elemento kiu tuj estos aldonita plu.

243
00:20:42,650 --> 00:20:45,140
Tial ni havas portempan puntero tie.

244
00:20:45,140 --> 00:20:50,780
Ĉar ni scias, ke ĉi tiu tria estas tenis spuro de,

245
00:20:50,780 --> 00:20:53,680
2 povas nun ligilon al nia nova.

246
00:20:53,680 --> 00:20:57,490
Kaj se tiu nova ruĝa ulo tuj estos en inter 2 kaj 3,

247
00:20:57,490 --> 00:21:05,550
tiam kio estas tiu ulo estas puntero tuj indikas? >> [Studento] Temp.

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

249
00:21:07,490 --> 00:21:15,430
Tial ĉi ruĝa ulo La sekva valoro tuj estos temp.

250
00:21:26,090 --> 00:21:33,010
Kiam vi enmeto en ligitaj listoj, ni vidis, ke ni povus

251
00:21:33,010 --> 00:21:38,260
facile aldoni ion al la fino por krei portempan tabelo,

252
00:21:38,260 --> 00:21:42,850
aŭ se ni volis aldoni ion al la mezo de nia tabelo,

253
00:21:42,850 --> 00:21:46,810
tiam necesus iom pli miksanta ĉirkaŭe.

254
00:21:46,810 --> 00:21:50,240
Se vi volas, ekzemple, havas ordo ligillisto,

255
00:21:50,240 --> 00:21:54,880
tiam vi devas ia pesas la kostoj kaj profitoj de tiu

256
00:21:54,880 --> 00:21:59,720
ĉar se vi volas havi ordo tabelo, tio signifas ke ĉiu tempo kiu vi enmetas en ĝin,

257
00:21:59,720 --> 00:22:01,630
ĝi estas tuj prenos iom pli da tempo.

258
00:22:01,630 --> 00:22:05,500
Tamen, se vi volas poste, kiel ni trovos ni volas,

259
00:22:05,500 --> 00:22:10,280
serĉante tra ligitaj listo, tiam ĝi eble estus pli facile se vi scias, ke ĉio estas en ordo.

260
00:22:10,280 --> 00:22:15,340
Do eble vi volas pesas la kostoj kaj profitoj de tiu.

261
00:22:20,150 --> 00:22:27,740
>> Alia maniero por enmeti en ligitaj listo estas por enmeti en la komenco de listo.

262
00:22:27,740 --> 00:22:34,700
Se ni desegni nian ankron tie - ĉi tiu estas nia kapo -

263
00:22:34,700 --> 00:22:40,960
kaj tiam tiuj homoj ligitaj al ĝi,

264
00:22:40,960 --> 00:22:48,460
kaj poste ni havas novan nodon esti enmetita en la komenco,

265
00:22:48,460 --> 00:22:52,590
tiam kio povus ni volas fari?

266
00:22:55,220 --> 00:23:03,580
Kio estus malbona nur diras mi volas ligi la ruĝa al la blua,

267
00:23:03,580 --> 00:23:05,790
ĉar tio estas la unua?

268
00:23:05,790 --> 00:23:08,570
Kio okazus tie?

269
00:23:08,570 --> 00:23:12,130
Ĉiuj de ĉi tiuj tri estus perdiĝos.

270
00:23:12,130 --> 00:23:14,140
Do ni ne volas fari tion.

271
00:23:14,140 --> 00:23:21,430
Denove, ni lernis ke ni bezonas havi ian temporal puntero.

272
00:23:21,430 --> 00:23:34,470
Ni elektas havi temporal punkto al ĉi tiu viro.

273
00:23:34,470 --> 00:23:39,640
Tiam ni povas havi la blua punkto al la provizora

274
00:23:39,640 --> 00:23:43,240
kaj tiam la ruĝan punkton al la bluo.

275
00:23:43,240 --> 00:23:47,830
La kialo kial Mi uzas homoj ĉi tie estas ĉar ni vere volas bildigi

276
00:23:47,830 --> 00:23:53,180
tenante al la homo kaj certigante ke ni havas ligon al ili

277
00:23:53,180 --> 00:23:57,590
antaŭ ol ni lasis iri de alia mano aŭ io kiel tio.

278
00:24:05,630 --> 00:24:10,650
>> Nun ke ni havas la senton de ligitaj listoj - kiel ni povus krei ligillisto

279
00:24:10,650 --> 00:24:15,090
kaj krei la strukturoj por tiu konsistanta de la tipo difino por nodo

280
00:24:15,090 --> 00:24:19,060
kaj tiam certigi ke ni havas sagon al la kapo de tiu ligitaj listo -

281
00:24:19,060 --> 00:24:23,210
iam ni havas tion kaj ni scias kiel trairi tra tabelo,

282
00:24:23,210 --> 00:24:28,200
aliro diversaj elementoj, ni scias kiel enigi kaj ni scias kiel liberigi ilin,

283
00:24:28,200 --> 00:24:30,260
tiam ni povas eniri en fuŝo.

284
00:24:30,260 --> 00:24:38,150
Kiel kutime, ni havas sekcion de demandoj kiuj get vi uzis por mastruma kun ligitaj listoj

285
00:24:38,150 --> 00:24:41,750
kaj malsamaj strukturoj kiel vostoj kaj piloj.

286
00:24:41,750 --> 00:24:46,000
Tiam ni povas movi en fuŝo.

287
00:24:46,000 --> 00:24:55,170
>> Fuŝo havas en la dissendo kodo kelkaj dosieroj de graveco.

288
00:24:55,170 --> 00:24:58,850
Unue ni rimarkas ke ni havas ĉi Makefile tie,

289
00:24:58,850 --> 00:25:03,040
kiuj ni ne vere renkontis antaŭe.

290
00:25:03,040 --> 00:25:10,090
Se vi rigardis interne de la pset5 dosierujo, vi volas rimarki ke vi havas. H dosiero,

291
00:25:10,090 --> 00:25:12,530
tiam vi havas du. c dosierojn.

292
00:25:12,530 --> 00:25:18,920
Kio ĉi Makefile faras estas antaŭe, ni simple tajpi fari kaj tiam la programo nomo

293
00:25:18,920 --> 00:25:25,550
kaj tiam ni vidus ĉiuj tiuj argumentoj kaj flagoj pasis en la tradukilo.

294
00:25:25,550 --> 00:25:30,580
Kion la Makefile faras estas ni permesas kompili plurajn dosierojn multope

295
00:25:30,580 --> 00:25:34,650
kaj pasi en la flagoj kiujn ni deziras.

296
00:25:34,650 --> 00:25:41,300
Ĉi tie ni nur vidas tie estas kapdosiero tie.

297
00:25:41,300 --> 00:25:43,730
Tiam ni efektive havis du fontaj dosieroj.

298
00:25:43,730 --> 00:25:47,520
Ni havas speller.c kaj dictionary.c.

299
00:25:47,520 --> 00:25:54,560
Vi bonvenigas redaktanton la Makefile se vi deziras.

300
00:25:54,560 --> 00:26:03,310
Rimarku, ke ĉi tie se vi tajpas pura, tiam kio faras estas vere forigas ion

301
00:26:03,310 --> 00:26:06,340
tio estas la kerno.

302
00:26:06,340 --> 00:26:09,190
Se vi havas segmentación kulpo, esence vi ricevas kernan dump.

303
00:26:09,190 --> 00:26:13,260
Do tiu malbela iom dosiero aperos en via dosierujo nomita kerno.

304
00:26:13,260 --> 00:26:16,310
Vi volas forigi tiun por fari ĝin purigi.

305
00:26:16,310 --> 00:26:20,940
Ĝi forigas ajna exe kaj. O dosierojn.

306
00:26:27,900 --> 00:26:30,220
>> Ni rigardu en dictionary.h.

307
00:26:30,220 --> 00:26:34,410
Ĉi tio diras, ke ĝi deklaras vortaro de funkciojn.

308
00:26:34,410 --> 00:26:39,530
Ni havas maksimuman longon por ajna vorto en la vortaro.

309
00:26:39,530 --> 00:26:45,130
Ni diru ke tiu tuj estos la plej longa ebla vorto. Estas de longo 45.

310
00:26:45,130 --> 00:26:48,900
Do ni ne tuj havas vortojn kiuj superas tiu longa.

311
00:26:48,900 --> 00:26:50,980
Ĉi tie ni nur havas la funkcion prototipoj.

312
00:26:50,980 --> 00:26:55,290
Ni ne havas la aktuala efektivigo ĉar tion ni faros por ĉi pset.

313
00:26:55,290 --> 00:26:59,940
Sed kio estas tiu faras estas ekde ni pritraktas pli grandaj dosieroj tie

314
00:26:59,940 --> 00:27:06,650
kaj funcionalidad sur pli granda skalo, ĝi estas utila havi. h dosieron

315
00:27:06,650 --> 00:27:11,290
por ke iu alia legis aŭ uzante vian kodo povas kompreni kio okazas.

316
00:27:11,290 --> 00:27:17,910
Kaj eble ili volas apliki provas se vi faris hash tabloj aŭ inverse.

317
00:27:17,910 --> 00:27:21,850
Tiam ili dirus mia ŝarĝo funkcio,

318
00:27:21,850 --> 00:27:26,950
la reala aplikado tuj diferencas, sed ĉi tiu prototipo ne ŝanĝos.

319
00:27:26,950 --> 00:27:33,280
Jen ni kontrolu, kiu revenas vera se donita vorto estas en la vortaro.

320
00:27:33,280 --> 00:27:39,800
Tiam ni havas ŝarĝon, kiu esence prenas en vortaro dosieron

321
00:27:39,800 --> 00:27:44,360
kaj poste ŝarĝas ĝin en iu datumstrukturo.

322
00:27:44,360 --> 00:27:47,500
Ni havas grandecon, kiu, kiam vokis, revenas la grandeco de via vortaro,

323
00:27:47,500 --> 00:27:50,310
kiom da vortoj estas stokitaj en ĝi,

324
00:27:50,310 --> 00:27:54,390
kaj tiam malŝarĝi, kiu liberigas la tutan memoron, ke vi povus esti formovita

325
00:27:54,390 --> 00:27:57,900
dum farante vian vortaron.

326
00:28:01,070 --> 00:28:03,590
>> Ni rigardu dictionary.c.

327
00:28:03,590 --> 00:28:10,490
Ni vidas, ke ĝi aspektas tre simila al dictionary.h, krom nun nur havas ĉiujn el tiuj todos en ĝi.

328
00:28:10,490 --> 00:28:16,980
Kaj tiel tio estas via laboro. Fine, vi povas plenigi ekster speller.c kun ĉiuj de ĉi tiu kodo.

329
00:28:16,980 --> 00:28:21,540
Dictionary.c, kiam kuri, ne vere volas fari nenion,

330
00:28:21,540 --> 00:28:29,590
do ni rigardu al speller.c vidi la reala realigo de la literumilo.

331
00:28:29,590 --> 00:28:32,060
Kvankam vi ne tuj povas redakti iun el ĉi tiu kodo,

332
00:28:32,060 --> 00:28:38,050
gravas legi, kompreni kiam ŝarĝo vokis, kiam mi vokas ĉeko,

333
00:28:38,050 --> 00:28:42,350
nur por kompreni, mapaj ĝin, vidi kiel la funkcio funkcias.

334
00:28:42,350 --> 00:28:49,860
Ni vidas, ke ĝi estas kontrolanta por la ĝusta uzado.

335
00:28:49,860 --> 00:28:55,200
Esence, kiam iu kuras Speller, ĉi indikas ke ĝi estas nedeviga

336
00:28:55,200 --> 00:29:00,950
por ili pasi en vortaro dosieron ĉar tuj esti defaŭlte vortaro dosiero.

337
00:29:00,950 --> 00:29:05,410
Kaj tiam ili devas pasi en la teksto esti literumilo kontrolis.

338
00:29:05,410 --> 00:29:11,410
rusage traktas tempo ĉar parto de ĉi pset kiuj ni pritrakti poste

339
00:29:11,410 --> 00:29:14,790
ne nur duumaj funkciadon literumilo laborante

340
00:29:14,790 --> 00:29:17,190
sed fakte atingi ĝin esti rapida.

341
00:29:17,190 --> 00:29:22,040
Kaj tiel do estas kie rusage tuj eniri

342
00:29:22,040 --> 00:29:28,740
Tie, ni vidas la unua alvoko al unu el niaj dictionary.c dosieroj, kiuj estas ŝarĝo.

343
00:29:28,740 --> 00:29:34,720
Laŭdu revenas vera aŭ malvera - vera sur sukceso, falsa sur fiasko.

344
00:29:34,720 --> 00:29:41,400
Do, se la vortaro ne estas ŝarĝita pozitive, tiam la speller.c revenos 1 kaj quit.

345
00:29:41,400 --> 00:29:47,920
Sed se ĝi faras ŝarĝo ĝuste, tiam ĝi tuj daŭrigi.

346
00:29:47,920 --> 00:29:50,740
Ni daŭrigu, kaj ni vidas iun dosieron / S tie,

347
00:29:50,740 --> 00:29:56,210
kie tuj povas trakti kun malfermante la teksta dosiero.

348
00:29:56,210 --> 00:30:04,640
Jen, kion tiu faras, estas literumilo kontrolas ĉiun vorton en la teksto.

349
00:30:04,640 --> 00:30:09,270
Do kio speller.c faras ĉi tie estas ripetanta super cxiu el la vortoj en la teksto dosieron

350
00:30:09,270 --> 00:30:12,790
kaj tiam kontroli ilin en la vortaron.

351
00:30:24,680 --> 00:30:32,350
Tie, ni havas Bulea misspelled kiu vidos se ĉeko revenas veraj aŭ ne.

352
00:30:32,350 --> 00:30:37,110
Se la vorto estas vere en la vortaro, tiam ĉeko revenos vera.

353
00:30:37,110 --> 00:30:39,760
Tio signifas ke la vorto ne estas misspelled.

354
00:30:39,760 --> 00:30:45,330
Do misspelled estus falsa, kaj tial ni havas la bang tie, la indiko.

355
00:30:45,330 --> 00:30:56,320
Ni daŭre iras, kaj poste ĝi tenas spuro de kiom da misspelled vortoj

356
00:30:56,320 --> 00:30:58,910
estas en la dosiero.

357
00:30:58,910 --> 00:31:03,870
Ĝi daŭrigas kaj fermas la dosiero.

358
00:31:03,870 --> 00:31:09,250
Tiam ĉi tie, ĝi informas kiom da misspelled vortoj vi havis.

359
00:31:09,250 --> 00:31:12,680
Ĝi kalkulas kiom da tempo ĝi prenis por ŝarĝi la vortaron,

360
00:31:12,680 --> 00:31:15,080
kiom da tempo ĝi prenis por kontroli ĝin,

361
00:31:15,080 --> 00:31:18,510
kiom da tempo ĝi prenis al kalkuli la grandecon,

362
00:31:18,510 --> 00:31:21,260
kiu, kiel ni iros plu, devus esti tre malgranda,

363
00:31:21,260 --> 00:31:25,390
kaj tiam kiom da tempo ĝi prenis por malŝarĝi la vortaro.

364
00:31:25,390 --> 00:31:27,700
Jen super ni vidas la alvoko por malŝarĝi tie.

365
00:31:27,700 --> 00:31:52,690
Se ni kontroli grandecon ĉi tie,

366
00:31:52,690 --> 00:31:59,050
tiam ni vidos, ke tie estas la alvoko al grandeco kie determinas la grandeco de la vortaro.

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

368
00:32:07,100 --> 00:32:10,920
>> Nia tasko por ĉi pset estas apliki ŝarĝo, kiu ŝarĝas la vortaro

369
00:32:10,920 --> 00:32:15,480
datumstrukturo - kiom vi elektas, estu ĝi hash tablo aŭ provu -

370
00:32:15,480 --> 00:32:18,810
kun vortoj de la vortaro dosiero.

371
00:32:18,810 --> 00:32:25,290
Tiam vi havas grandecon, kiu redonos la nombro de vortoj en la vortaro.

372
00:32:25,290 --> 00:32:29,860
Kaj se vi apliki ŝarĝo en inteligenta maniero, tiam grandeco devas esti bela facila.

373
00:32:29,860 --> 00:32:33,860
Tiam vi kontrolu, kiu kontrolu se donita vorto estas en la vortaro.

374
00:32:33,860 --> 00:32:38,690
Do speller.c pasas en kordoj, kaj tiam vi devas kontroli cxu tio kordoj

375
00:32:38,690 --> 00:32:41,610
estas enhavita en via vortaro.

376
00:32:41,610 --> 00:32:46,750
Rimarku ke ni ĝenerale havas norma vortaroj,

377
00:32:46,750 --> 00:32:53,020
sed en ĉi pset, esence ajna vortaro pasis en en ajna lingvo.

378
00:32:53,020 --> 00:32:57,040
Do ni ne povas simple supozi ke la vorto LA estas ene.

379
00:32:57,040 --> 00:33:03,090
La vorto FOOBAR povus esti difinita en iu vortaro kiun ni pasas in

380
00:33:03,090 --> 00:33:07,920
Kaj tiam ni malŝarĝi, kiu liberigas la vortaron de memoro.

381
00:33:07,920 --> 00:33:11,930
>> Unue, mi ŝatus iri super la hash tablo metodo

382
00:33:11,930 --> 00:33:14,630
pri kiel ni povus efektivigi ĉiuj el tiuj kvar funkciojn,

383
00:33:14,630 --> 00:33:18,650
kaj tiam mi iros sur la provas metodon, kiel ni apliki tiujn kvar funkciojn,

384
00:33:18,650 --> 00:33:22,720
kaj fine diskuto pri iuj ĝeneralaj konsiloj kiam vi faras la pset

385
00:33:22,720 --> 00:33:27,870
kaj ankaŭ kiel vi eble povus uzi Valgrind por kontroli por memoro likas.

386
00:33:27,870 --> 00:33:30,550
>> Ni eniras en la hash tablo metodo.

387
00:33:30,550 --> 00:33:35,910
Al hash tablo konsistas el listo de siteloj.

388
00:33:35,910 --> 00:33:43,010
Ĉiu valoro, ĉiu vorto, tuj iros en unu el tiuj siteloj.

389
00:33:43,010 --> 00:33:53,200
Al hash tablo ideale egale disdonas ĉiuj tiuj valoroj, ke vi pasis en

390
00:33:53,200 --> 00:33:57,160
kaj tiam popolas ilin en la rubujon tiaj ke ĉiu rubujo

391
00:33:57,160 --> 00:34:02,000
havas ĉirkaŭ egala nombro de valoroj en ĝi.

392
00:34:02,000 --> 00:34:09,630
La strukturo di hash tablo, ni havas aron da ligitaj listoj.

393
00:34:09,630 --> 00:34:17,900
Kion ni faras estas kiam ni pasas en valoro, ni kontrolu kie tiu valoro devas aparteni,

394
00:34:17,900 --> 00:34:23,840
kiuj balde apartenas al, kaj tiam metu ĝin en la ligillisto asociita kun tiu rubujo.

395
00:34:23,840 --> 00:34:28,199
Jen, kion mi havas estas hash funkcio.

396
00:34:28,199 --> 00:34:31,320
Ĝi estas int hash tablo.

397
00:34:31,320 --> 00:34:38,540
Do por la unua rubujo, ajna entjeroj sub 10 eniru la unuan sitelon.

398
00:34:38,540 --> 00:34:42,190
Ajna entjeroj super 10 sed sub 20 go en la dua,

399
00:34:42,190 --> 00:34:44,179
kaj poste tiel plu kaj tiel plu.

400
00:34:44,179 --> 00:34:52,370
Por mi, ĉiu rubujo estas reprezentanto tiuj nombroj.

401
00:34:52,370 --> 00:34:59,850
Tamen, diru mi estus pasi en 50, ekzemple.

402
00:34:59,850 --> 00:35:07,490
Ĝi aperas kvazaŭ la tri unuaj enhavas serion de dek numeroj.

403
00:35:07,490 --> 00:35:12,570
Sed mi volas permesi mia hash tablo por preni en ajna speco de entjeroj,

404
00:35:12,570 --> 00:35:19,860
do tiam mi devus filtri ĉiuj nombroj super 30 en la lastaj rubujo.

405
00:35:19,860 --> 00:35:26,660
Kaj tiel do, ke rezultos en speco de desequilibrado hash tablo.

406
00:35:31,330 --> 00:35:35,640
Ripeti, hash tablo estas nur tabelo de siteloj

407
00:35:35,640 --> 00:35:38,590
kie ĉiu rubujo estas ligillisto.

408
00:35:38,590 --> 00:35:43,730
Kaj tiel por determini kie ĉiu valoro iras, kiu kondutas iras enen,

409
00:35:43,730 --> 00:35:46,260
vi tuj volas kio nomiĝas hash funkcio

410
00:35:46,260 --> 00:35:55,010
kiu prenas valoron kaj tiam diras ĉi valoro korespondas al iu sitelo.

411
00:35:55,010 --> 00:36:00,970
Do supren supre ĉe ĉi tiu ekzemplo, miaj hash funkcio prenis ĉiu valoro.

412
00:36:00,970 --> 00:36:03,020
Ĝi kontrolis ĉu ĝi estis malpli ol 10.

413
00:36:03,020 --> 00:36:05,360
Se ĝi estis, ĝi metus ĝin en la unua rubujo.

414
00:36:05,360 --> 00:36:08,910
Ĝi kontrolas ĉu ĝi estas malpli ol 20, metas ĝin en la dua, se vera,

415
00:36:08,910 --> 00:36:12,880
ĉekojn se estas malpli ol 30, kaj poste metas ĝin en la tria rubujo,

416
00:36:12,880 --> 00:36:16,990
kaj tiam ĉio simple falas en la kvara rubujo.

417
00:36:16,990 --> 00:36:20,110
Do kiam ajn vi havas valoro, via hash funkcio

418
00:36:20,110 --> 00:36:25,420
metos tiun valoron en la taŭgan rubujo.

419
00:36:25,420 --> 00:36:32,430
La krada funkcio esence bezonas scii kiom da siteloj vi havas.

420
00:36:32,430 --> 00:36:37,960
Via hash tablo grandeco, la nombro de siteloj havas,

421
00:36:37,960 --> 00:36:41,190
ke tuj estos fiksita nombro, kiu estas de ci, al vi decidi,

422
00:36:41,190 --> 00:36:43,590
sed tuj estos fiksita nombro.

423
00:36:43,590 --> 00:36:51,840
Do, via hash funkcio estos dependi sur tiu determini kiuj balde singla ŝlosilo eniras en

424
00:36:51,840 --> 00:36:54,450
tia, ke ĝi estas egale distribuita.

425
00:36:56,150 --> 00:37:03,820
Simila al nia apliko de ligitaj listoj, nun ĉiu nodo en la hash tablo

426
00:37:03,820 --> 00:37:07,000
Efektive oni tuj havas tipo char.

427
00:37:07,000 --> 00:37:14,340
Do ni havas char tabelo nomis vorto kaj tiam alia sagon al la sekva nodo,

428
00:37:14,340 --> 00:37:19,010
kiu havas sencon ĉar tuj esti ligitaj listo.

429
00:37:19,010 --> 00:37:24,350
Memoru kiam ni estis ligitaj listoj, mi faris nodon * nomita kapo

430
00:37:24,350 --> 00:37:31,060
kiu indikante la unuan nodon en la ligitaj listo.

431
00:37:31,060 --> 00:37:34,020
Sed por nia hash tablo, ĉar ni havas plurajn ligitaj lertaj,

432
00:37:34,020 --> 00:37:37,520
kion ni volas estas ni volas nian hash tablo esti kiel, "Kio estas rubujo?"

433
00:37:37,520 --> 00:37:43,340
Al rubujo estas nur listo de nodo punteros,

434
00:37:43,340 --> 00:37:50,620
kaj tiel ĉiu ero en la rubujo estas vere indikante lia responda ligitaj listo.

435
00:37:56,180 --> 00:38:01,520
Reiru al ĉi esquemática, vi vidas ke la siteloj mem estas la sagojn,

436
00:38:01,520 --> 00:38:06,980
Ne realaj nodoj.

437
00:38:11,680 --> 00:38:16,420
Unu esenca propraĵo de kradaj funkcioj estas ke ili estas determina.

438
00:38:16,420 --> 00:38:19,440
Tio signifas ke kiam vi hash la nombro 2,

439
00:38:19,440 --> 00:38:22,270
ĝi devus redoni la sama rubujo.

440
00:38:22,270 --> 00:38:26,440
Ĉiu unuopa valoro kiu iras en la krada funkcio, se ripetis,

441
00:38:26,440 --> 00:38:29,690
devas preni la sama indico.

442
00:38:29,690 --> 00:38:34,210
Do, via hash funkcio redonas la indekso de la tabelo

443
00:38:34,210 --> 00:38:38,530
kie tiu valoro apartenas.

444
00:38:38,530 --> 00:38:41,790
Kiel mi menciis antaŭe, la nombro de siteloj estas fiksa,

445
00:38:41,790 --> 00:38:49,630
kaj tiel viaj indekso ke vi revenos devas esti malpli ol la nombro de siteloj

446
00:38:49,630 --> 00:38:52,680
sed pli granda ol 0.

447
00:38:52,680 --> 00:39:00,780
La kialo kial ni havas kradaj funkcioj anstataŭ nur unu sola ligitaj listo

448
00:39:00,780 --> 00:39:09,290
aŭ unu sola tabelo estas ke ni volas esti kapabla salti al iu sekcio plej facile

449
00:39:09,290 --> 00:39:11,720
se ni konas la karakterizo de valoro -

450
00:39:11,720 --> 00:39:14,760
anstataŭ devi serĉi tra la tuta tuta vortaro,

451
00:39:14,760 --> 00:39:18,320
povi salti al iu sekcio de ĝi.

452
00:39:19,880 --> 00:39:24,440
Via hash funkcio devus konsideri ke ideale,

453
00:39:24,440 --> 00:39:28,980
ĉiu rubujo havas proksimume la sama nombro de klavoj.

454
00:39:28,980 --> 00:39:35,040
Ekde la hash tablo estas serio de ligitaj lertaj,

455
00:39:35,040 --> 00:39:38,480
tiam la ligitaj lertaj sin tuj havas pli ol unu nodo.

456
00:39:38,480 --> 00:39:43,210
En la antaŭa ekzemplo, du malsamaj nombroj, kvankam ili ne estis egalaj,

457
00:39:43,210 --> 00:39:46,950
kiam hashed, denove la sama indico.

458
00:39:46,950 --> 00:39:53,620
Do kiam vi traktas kun vortoj, unu vorton, kiam hashed

459
00:39:53,620 --> 00:39:57,450
estus la sama hash valoro kiel alia vorto.

460
00:39:57,450 --> 00:40:04,140
Tion ni nomas kolizio, kiam ni havas nodo ke, kiam hashed,

461
00:40:04,140 --> 00:40:09,610
la ligitaj listo en tiu sitelo ne estas malplena.

462
00:40:09,610 --> 00:40:14,180
La tekniko kiu ni nomas estas lineara tuŝoprobado,

463
00:40:14,180 --> 00:40:22,550
kie vi eniru la ligitaj listo kaj poste trovi, kie vi volas enmeti ke nodo

464
00:40:22,550 --> 00:40:25,520
ĉar vi havas kolizio.

465
00:40:25,520 --> 00:40:28,070
Vi povas vidi, ke povus esti komerca-off here, right?

466
00:40:28,070 --> 00:40:33,760
Se vi havas tre malgrandan hash tablo, tre malgranda nombro de siteloj,

467
00:40:33,760 --> 00:40:36,380
tiam vi havos multe da kolizioj.

468
00:40:36,380 --> 00:40:40,460
Sed tiam, se vi faras tre grandan hash tablo,

469
00:40:40,460 --> 00:40:44,110
vi probable tuj minimumigi la kolizioj,

470
00:40:44,110 --> 00:40:47,170
sed tuj estos tre granda datumstrukturo.

471
00:40:47,170 --> 00:40:49,310
Tie tuj estos komerco-offs kun tio.

472
00:40:49,310 --> 00:40:51,310
Do kiam vi faras vian pset, provu ludi ĉirkaŭ

473
00:40:51,310 --> 00:40:54,210
inter eble farante pli malgranda hash tablo

474
00:40:54,210 --> 00:41:02,100
sed tiam sciante ke ĝi estas tuj prenos iom pli longa tra la diversaj elementoj

475
00:41:02,100 --> 00:41:04,270
de tiuj ligitaj listoj.

476
00:41:04,270 --> 00:41:09,500
>> Kio ŝarĝo tuj fari estas persisti sur cxiu vorto en la vortaro.

477
00:41:09,500 --> 00:41:13,180
Ĝi pasas en puntero la vortaro dosiero.

478
00:41:13,180 --> 00:41:18,050
Do vi iras por utiligi la dosiero / S funkcioj kiuj vi majstris en pset4

479
00:41:18,050 --> 00:41:23,010
kaj persisti sur cxiu vorto en la vortaro.

480
00:41:23,010 --> 00:41:26,620
Vi volas ĉiu vorto en la vortaro por igi nova nodo,

481
00:41:26,620 --> 00:41:32,730
kaj vi tuj meti ĉiu el tiuj nodoj ene de via vortaro datumstrukturo.

482
00:41:32,730 --> 00:41:36,560
Kiam ajn vi ricevas novan vorton, vi scias ke ĝi tuj fariĝis nodo.

483
00:41:36,560 --> 00:41:46,590
Do vi povas iri straightaway kaj malloc nodo puntero por ĉiu nova vorto, kiun vi havas.

484
00:41:46,590 --> 00:41:52,610
Jen Mi vokas mian nodo puntero new_node kaj mi mallocing kio? La grandeco de vertico.

485
00:41:52,610 --> 00:41:59,190
Tiam legi la reala linio de dosiero, ĉar la vortaro estas vere stokita

486
00:41:59,190 --> 00:42:03,340
per vorto kaj tiam nova linio, kion ni povas utiligi

487
00:42:03,340 --> 00:42:06,520
estas la funkcio fscanf,

488
00:42:06,520 --> 00:42:10,280
per dosiero estas la vortaro dosiero ni pasis en,

489
00:42:10,280 --> 00:42:18,900
tiel skanu la dosieron por kordoj kaj lokoj kiuj kordoj en la lasta argumento.

490
00:42:18,900 --> 00:42:26,890
Se vi rememoras reveni al unu el la prelegoj, kiam ni iris super

491
00:42:26,890 --> 00:42:29,320
kaj tipon de senŝeligita la manteloj denove sur la CS50 biblioteko,

492
00:42:29,320 --> 00:42:33,430
ni vidis efektivigo de fscanf tie.

493
00:42:33,430 --> 00:42:37,700
Reiri al fscanf, ni havas la dosieron kiu ni legas de,

494
00:42:37,700 --> 00:42:42,570
ni serĉas ĉenon en tiu dosiero, kaj tiam ni metante gxin en

495
00:42:42,570 --> 00:42:48,340
tie mi havas new_node-> vorton ĉar new_node estas nodo pointer,

496
00:42:48,340 --> 00:42:50,380
ne estas reala nodo.

497
00:42:50,380 --> 00:42:57,100
Tial Mi diris new_node, mi volas iri al la nodo ke ĝi estas indikante

498
00:42:57,100 --> 00:43:01,190
kaj poste atribui tiun valoron al vorto.

499
00:43:01,190 --> 00:43:08,540
Ni volas tiam preni tiun vorton kaj enmeti ĝin en la hash tablo.

500
00:43:08,540 --> 00:43:13,750
Realigi ke ni faris new_node nodo puntero

501
00:43:13,750 --> 00:43:18,230
ĉar ni tuj volas scii kion la adreso de tiu nodo estas

502
00:43:18,230 --> 00:43:23,940
kiam ni enŝovu ĝin en ĉar la strukturo de la nodoj sin, de la struct,

503
00:43:23,940 --> 00:43:26,380
estas ke ili havas puntero al nova nodo.

504
00:43:26,380 --> 00:43:30,820
Tial kio estas la adreso de tiu nodo tuj indikas?

505
00:43:30,820 --> 00:43:34,550
Tio adreso tuj estos new_node.

506
00:43:34,550 --> 00:43:42,140
Ĉu tio havas sencon, kial ni fari new_node nodo * kontraste al nodo?

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

508
00:43:45,700 --> 00:43:52,840
Ni havas unu vorton. Ke valoro estas new_node-> vorton.

509
00:43:52,840 --> 00:43:55,970
Kiu enhavas la vorton el la vortaro, ke ni volas enigo.

510
00:43:55,970 --> 00:44:00,210
Do kion ni volas fari estas ni volas nomi nian hash funkcio sur tiu linio

511
00:44:00,210 --> 00:44:03,780
cxar nia hash funkcio prenas en ĉenon kaj poste revenas al ni entjero,

512
00:44:03,780 --> 00:44:12,090
kie tiu entjero estas la indekso kie hashtable en tiu indico reprezentas tiun rubujon.

513
00:44:12,090 --> 00:44:18,260
Ni volas preni tiun indekso kaj poste iru al tiu indekso de la hash tablo

514
00:44:18,260 --> 00:44:26,960
kaj poste uzas tiun ligitaj listo por enigi la nodo ĉe new_node.

515
00:44:26,960 --> 00:44:31,950
Memoru ke tamen vi decidas enŝovu vian nodo,

516
00:44:31,950 --> 00:44:34,370
ĉu ĝi estas en la mezo, se vi volas ordigi ĝin

517
00:44:34,370 --> 00:44:39,650
aŭ komence aŭ fine, nur certigi ke via lasta nodo ĉiam notas al nula

518
00:44:39,650 --> 00:44:46,730
ĉar tio estas la sola maniero por ke ni scias, kie la lasta elemento de nia ligitaj listo estas.

519
00:44:50,790 --> 00:44:59,710
>> Se grandeco estas entjero kiu reprezentas la nombro de vortoj en vortaro,

520
00:44:59,710 --> 00:45:03,060
tiam unu maniero fari tion estas ke kiam ajn grandeco estas nomita

521
00:45:03,060 --> 00:45:05,840
ni iru tra ĉiu ero en nia hash tablo

522
00:45:05,840 --> 00:45:09,410
kaj tiam persisti tra ĉiu ligitaj listo ene de la hash tablo

523
00:45:09,410 --> 00:45:13,770
kaj poste kalkuli la longon de tiu, kreskanta nia nombrilo 1 per 1.

524
00:45:13,770 --> 00:45:16,580
Sed ĉiufoje tiu grandeco estas vokitaj, por ke tuj prenas longan tempon

525
00:45:16,580 --> 00:45:22,120
ĉar ni tuj estos lineare tuŝoprobado ĉiu unuopa ligitaj listo.

526
00:45:22,120 --> 00:45:30,530
Anstataŭe, ĝi tuj estos multe pli facile se vi observos spuro de kiom da vortoj estas pasitaj in

527
00:45:30,530 --> 00:45:36,330
Se do vi inkludas nombrilo inter viaj ŝarĝo funkcio

528
00:45:36,330 --> 00:45:42,430
ke ĝisdatigoj kiel necesa, tiam vendotablo, se vi starigis gxin al suma variablo,

529
00:45:42,430 --> 00:45:44,930
povos aliri por grandeco.

530
00:45:44,930 --> 00:45:51,450
Do kio grandeco povus simple fari estas en unu linio, ĝuste redoni la vendotablo valoro,

531
00:45:51,450 --> 00:45:55,500
la grandeco de la vortaro, kiun vi jam traktis en ŝarĝo.

532
00:45:55,500 --> 00:46:05,190
Tion mi volis diri kiam mi diris se vi apliki ŝarĝo en helpema maniero,

533
00:46:05,190 --> 00:46:08,540
tiam grandeco tuj estos bela facila.

534
00:46:08,540 --> 00:46:11,350
>> Do nun ni preni por kontroli.

535
00:46:11,350 --> 00:46:15,960
Nun ni pritraktas vortojn el la eniga teksto-dosiero,

536
00:46:15,960 --> 00:46:19,910
kaj tiel ni tuj estos kontroli ĉu ĉiuj tiuj enigo vortoj

537
00:46:19,910 --> 00:46:22,520
estas vere en la vortaro aŭ ne.

538
00:46:22,520 --> 00:46:26,520
Simila al Scramble, ni volas enkalkuli kazo insensibilidad.

539
00:46:26,520 --> 00:46:32,110
Vi volas certigi, ke ĉiuj de la vortoj pasis en, kvankam ili estas miksitaj kazo,

540
00:46:32,110 --> 00:46:37,840
kiam nomas kun linia kompari, estas ekvivalento.

541
00:46:37,840 --> 00:46:42,450
La vortoj en la vortaro tekstaj dosieroj estas fakte ĉiuj minuskla.

542
00:46:42,450 --> 00:46:49,280
Alia afero estas ke oni povas supozi, ke ĉiu vorto pasis en, ĉiu linio,

543
00:46:49,280 --> 00:46:53,200
tuj estos ĉu alfabeta aŭ enhavi apostrofoj.

544
00:46:53,200 --> 00:46:58,010
Apostrofoj tuj estos valida vortoj en nia vortaro.

545
00:46:58,010 --> 00:47:06,470
Do se vi havas vorton kun apostrofo S, jen reala leĝa vorto en via vortaro

546
00:47:06,470 --> 00:47:11,650
ke tuj estos unu el la nodoj en via hash tablo.

547
00:47:13,470 --> 00:47:18,350
Kontrolu operacias kun se la vorto ekzistas, tiam ĝi estas alvenis al esti en nia hash tablo.

548
00:47:18,350 --> 00:47:22,210
Se la vorto estas en la vortaro, tiam ĉiuj el la vortoj en la vortaro estas en la hash tablo,

549
00:47:22,210 --> 00:47:26,560
do ni serĉas ĉi vorto en la hash tablo.

550
00:47:26,560 --> 00:47:29,250
Ni scias ke ekde ni implementado nia hash funkcio

551
00:47:29,250 --> 00:47:38,420
tia, ke ĉiu sola vorto estas ĉiam hashed al la sama valoro,

552
00:47:38,420 --> 00:47:43,340
tiam ni scias ke en loko de serĉado tra nia tuta tuta hash tablo,

553
00:47:43,340 --> 00:47:48,310
ni povas efektive trovi la ligillisto, ke tiu vorto devus aparteni al.

554
00:47:48,310 --> 00:47:51,850
Se estis en la vortaro, tiam ĝi estus en tiu sitelo.

555
00:47:51,850 --> 00:47:57,140
Kion ni povas fari, se vorto estas la nomo de nia string pasis en,

556
00:47:57,140 --> 00:48:01,560
ni povas nur hash tiun vorton kaj rigardu la ligitaj listo

557
00:48:01,560 --> 00:48:06,410
en la valoro de hashtable [hash (vorto)].

558
00:48:06,410 --> 00:48:12,410
De tie, kion ni povas fari estas ni havas pli malgrandan subaro de nodoj al serĉi ĉi tiun vorton,

559
00:48:12,410 --> 00:48:16,770
kaj tiel ni povas trairi la ligillisto, uzante ekzemplo de pli frue en la walkthrough,

560
00:48:16,770 --> 00:48:24,110
kaj tiam nomita string kompari sur la vorto kien la kursoro estas indikante,

561
00:48:24,110 --> 00:48:28,430
tiun vorton, kaj vidi, cxu tiuj kompari.

562
00:48:30,280 --> 00:48:35,110
Depende de la maniero kiun vi organizos vian hash funkcio,

563
00:48:35,110 --> 00:48:39,260
se ĝi estas ordo, vi eble povos reveni falsa iom pli frue,

564
00:48:39,260 --> 00:48:43,440
sed se estas unsorted, tiam vi volas daŭrigi lauxiris tra viaj ligitaj listo

565
00:48:43,440 --> 00:48:46,480
ĝis vi trovas la lasta elemento de la listo.

566
00:48:46,480 --> 00:48:53,320
Kaj se vi ankoraŭ ne trovis la vorton de la tempo vi atingis la finon de la ligitaj listo,

567
00:48:53,320 --> 00:48:56,890
tio signifas, ke via vorto ne ekzistas en la vortaro,

568
00:48:56,890 --> 00:48:59,410
kaj por ke vorto estas nevalida,

569
00:48:59,410 --> 00:49:02,730
kaj ĉeko devus reveni falsaj.

570
00:49:02,730 --> 00:49:09,530
>> Nun ni venas al malŝarĝi, kie ni volas liberigi ĉiujn nodoj kiuj ni malloc'd,

571
00:49:09,530 --> 00:49:14,050
tiel libera ĉiuj nodoj ene de nia hash tablo.

572
00:49:14,050 --> 00:49:20,270
Ni tuj volas persisti super ĉiuj el la ligitaj lertaj kaj libera ĉiuj nodoj en tio.

573
00:49:20,270 --> 00:49:29,350
Se vi rigardas supre en la walkthrough al la ekzemplo kie ni liberigi lerta kunligita,

574
00:49:29,350 --> 00:49:35,140
tiam vi volas ripeti tiun procezon por ĉiu elemento en la hash tablo.

575
00:49:35,140 --> 00:49:37,780
Kaj mi iros sur oriento al la fino de la walkthrough,

576
00:49:37,780 --> 00:49:46,600
sed Valgrind estas ilo, kie vi povas kontroli ĉu vi bone liberigitaj

577
00:49:46,600 --> 00:49:53,600
ĉiu nodo ke vi malloc'd aŭ io ajn alia ke vi malloc'd, ajna alia puntero.

578
00:49:55,140 --> 00:50:00,530
Do jen hash tabloj, kie ni havas finia nombro de siteloj

579
00:50:00,530 --> 00:50:09,220
kaj hash funkcio kiu prenos valoron kaj poste atribui tiun valoron al iu sitelo.

580
00:50:09,220 --> 00:50:13,340
>> Nun ni venas al provoj.

581
00:50:13,340 --> 00:50:18,750
Provas speco de rigardo kiel ĉi tiu, kaj mi ankaŭ nudigos ekzemplo.

582
00:50:18,750 --> 00:50:25,630
Esence, vi havas tuta tabelo de potenciala literoj,

583
00:50:25,630 --> 00:50:29,210
kaj poste kiam ajn vi konstrui vorton,

584
00:50:29,210 --> 00:50:36,490
tiu litero povas esti ligitaj por vortaro por doni abundan gamon de ebloj.

585
00:50:36,490 --> 00:50:40,840
Iuj vortoj starti kun C sed tiam daŭrigas kun A,

586
00:50:40,840 --> 00:50:42,960
sed aliaj daŭrigi kun O, ekzemple.

587
00:50:42,960 --> 00:50:51,090
Al trie estas vojo de bildiganta ĉiuj eblaj kombinoj de tiuj vortoj.

588
00:50:51,090 --> 00:50:59,070
Al trie tuj konservi trako de la sekvenco de literoj kiuj formas parton vortoj,

589
00:50:59,070 --> 00:51:08,280
debranĉo kiam necesa, kiam unu litero povas esti sekvata de oblo de literoj,

590
00:51:08,280 --> 00:51:16,630
kaj fine indiki je ĉiu punkto ĉu tiu vorto estas valida aŭ ne

591
00:51:16,630 --> 00:51:30,120
ĉar se vi literumas la vorton MAT, MA Mi ne kredas estas valida vorto, sed MAT estas.

592
00:51:30,120 --> 00:51:37,820
Kaj tiel en via trie, ĝi indikus ke post MAT tio fakte validas vorto.

593
00:51:41,790 --> 00:51:48,590
Ĉiu nodo en nia trie vere tuj enhavas aron de nodo punteros,

594
00:51:48,590 --> 00:51:52,970
kaj ni tuj havas, specife, 27 el tiuj nodo punteros,

595
00:51:52,970 --> 00:52:00,550
unu por ĉiu litero en la alfabeto tiel kiel la apostrofo karaktero.

596
00:52:00,550 --> 00:52:10,450
Ĉiu elemento en tiu tabelo estas mem tuj atentigi al alia nodo.

597
00:52:10,450 --> 00:52:14,020
Do se tiu nodo estas NULL, se ne estas nenio post tio,

598
00:52:14,020 --> 00:52:20,550
tiam ni scias ke ne estas pliaj leteroj en tiu vorto sekvenco.

599
00:52:20,550 --> 00:52:26,950
Sed se tiu nodo estas ne NULL, tio signifas ke estas pli literojn en tiu letero sekvenco.

600
00:52:26,950 --> 00:52:32,160
Kaj tiam plue, ĉiu nodo indikas ĉu ĝi estas la lasta karaktero de vorto, aŭ ne.

601
00:52:38,110 --> 00:52:43,170
>> Ni iru en ekzemplo de trie.

602
00:52:50,500 --> 00:52:58,340
Unue mi havas spacon por 27 nodoj en ĉi tabelo.

603
00:52:58,340 --> 00:53:03,200
Se mi havas la vorton TRINKEJO -

604
00:53:13,310 --> 00:53:15,370
Se mi havas la vorton TRINKEJO kaj mi volas enmeti ke en,

605
00:53:15,370 --> 00:53:22,700
la unua litero estas B, do se mia trie estas malplena,

606
00:53:22,700 --> 00:53:29,910
B estas la dua litero de la alfabeto, do mi tuj deziras enmeti ĉi tie en ĉi tiu indekso.

607
00:53:29,910 --> 00:53:33,450
Mi tuj devos B tie.

608
00:53:33,450 --> 00:53:42,400
B estas tuj estos nodo kiu notas al alia tabelo de ĉiuj eblaj signoj

609
00:53:42,400 --> 00:53:45,870
kiu povas sekvi post la litero B.

610
00:53:45,870 --> 00:53:57,610
En ĉi tiu kazo, mi traktas la vorton TRINKEJO, do A iros tien.

611
00:54:02,000 --> 00:54:08,990
Post A, mi havas la literon R, do tiam A nun notas al lia propra kombinaĵo,

612
00:54:08,990 --> 00:54:15,120
kaj tiam R estos ĉi tie.

613
00:54:15,120 --> 00:54:22,470
TRINKEJO estas kompleta vorto, do tiam mi havos R punkto al alia nodo

614
00:54:22,470 --> 00:54:33,990
kiu diras, ke tiu vorto estas valida.

615
00:54:36,010 --> 00:54:40,970
Ke nodo ankaŭ havos aron de nodoj,

616
00:54:40,970 --> 00:54:45,260
sed tiuj povus esti NULL.

617
00:54:45,260 --> 00:54:49,080
Sed esence, povas daŭrigi tiel.

618
00:54:49,080 --> 00:54:54,250
Kiu igos iom pli klara kiam ni iros al malsama ekzemplo,

619
00:54:54,250 --> 00:54:56,780
tiel simple toleras min tie.

620
00:54:56,780 --> 00:55:02,050
Nun ni havas TRINKEJO ene de nia vortaro.

621
00:55:02,050 --> 00:55:05,980
Nun supozu ke ni havas la vorton Baz.

622
00:55:05,980 --> 00:55:12,630
Ni komencu per B, kaj ni jam havas B kiel unu el la literoj kiuj estas en nia vortaro.

623
00:55:12,630 --> 00:55:15,170
Tio sekvis kun A. Ni havas A jam.

624
00:55:15,170 --> 00:55:19,250
Sed tiam anstataŭe, ni havas Z jeno.

625
00:55:19,250 --> 00:55:25,490
Tial ero en nia tabelo tuj estos Z,

626
00:55:25,490 --> 00:55:30,810
kaj tiel do oni tuj indikas alian valida fino de la vorto.

627
00:55:30,810 --> 00:55:36,930
Do ni vidas, ke kiam ni daŭrigas tra B kaj tiam A,

628
00:55:36,930 --> 00:55:43,480
estas du malsamaj ebloj nuntempe en nia vortaro por vortoj kiuj komencas kun B kaj A.

629
00:55:49,650 --> 00:55:57,460
Diras, ke ni volis enmeti la vorton FOOBAR.

630
00:55:57,460 --> 00:56:05,620
Tiam ni farus eniro en F.

631
00:56:05,620 --> 00:56:11,320
F estas nodo kiu notas al tuta tabelo.

632
00:56:11,320 --> 00:56:22,790
Ni trovus ho, iru al O, ho tiam Ligiloj al tuta listo.

633
00:56:22,790 --> 00:56:35,340
Ni havus B kaj tiam daŭrigas, ni havus A kaj tiam R.

634
00:56:35,340 --> 00:56:43,570
Tial FOOBAR trairas la tutan vojon malsupren ĝis FOOBAR estas korekta vorto.

635
00:56:43,570 --> 00:56:52,590
Kaj tiel do ĉi tio estus valida vorto.

636
00:56:52,590 --> 00:57:00,170
Nun diru nian proksiman vorton en la vortaro estas vere la vorto FOO.

637
00:57:00,170 --> 00:57:03,530
Ni dirus F. Kio sekvas F?

638
00:57:03,530 --> 00:57:06,190
Mi vere jam havos spacon por O, do mi tuj daŭrigi.

639
00:57:06,190 --> 00:57:09,150
Mi ne bezonas fari novan. Daŭrigi.

640
00:57:09,150 --> 00:57:15,500
FOO estas valida vorto en ĉi vortaro, do tiam mi iros por indiki

641
00:57:15,500 --> 00:57:21,660
ke tio estas valida.

642
00:57:21,660 --> 00:57:28,370
Se mi haltas mian sekvenco tie, tio estus ĝusta.

643
00:57:28,370 --> 00:57:33,050
Sed se ni daŭrigas nian vico de FOO malsupren al B

644
00:57:33,050 --> 00:57:39,750
kaj nur havis FOOB, FOOB ne estas vorto, kaj tio ne indikis kiel valida.

645
00:57:47,370 --> 00:57:57,600
En trie, vi ĉiun nodon indikante ĉu ĝi estas valida vorto aŭ ne,

646
00:57:57,600 --> 00:58:05,840
kaj tiam ĉiu nodo havas ankaŭ tabelo de 27 nodo punteros

647
00:58:05,840 --> 00:58:09,520
kiu tiam punkto al nodoj sin.

648
00:58:09,520 --> 00:58:12,940
>> Jen estas maniero de kiel vi eble volas difini ĉi.

649
00:58:12,940 --> 00:58:17,260
Tamen, ĝuste kiel en la hash tablo ekzemple, kie ni havis nodon * kapo

650
00:58:17,260 --> 00:58:21,320
por indiki la komenco de nia ligitaj listo, ni ankaŭ tuj volis

651
00:58:21,320 --> 00:58:29,150
iel scii kie la komenco de nia trie estas.

652
00:58:29,150 --> 00:58:34,110
Iuj personoj alvoko provas arboj, kaj tie estas kie radiko devenas.

653
00:58:34,110 --> 00:58:36,910
Do ni volas ke la radiko de nia arbo por certigi ke ni restu bazite

654
00:58:36,910 --> 00:58:39,570
al kie ajn nia trie estas.

655
00:58:42,910 --> 00:58:46,300
Ni jam ia transiris

656
00:58:46,300 --> 00:58:50,240
la vojo vi povus pensi ŝarĝas ĉiu vorto en la vortaro.

657
00:58:50,240 --> 00:58:54,540
Esence, por ĉiu vorto kiun vi tuj volas persisti per via trie

658
00:58:54,540 --> 00:58:59,590
kaj sciante, ke ĉiu elemento en la infanoj - ni nomas ĝin infanoj en ĉi tiu kazo -

659
00:58:59,590 --> 00:59:04,290
korespondas al malsama litero, vi tuj volas kontroli tiujn valorojn

660
00:59:04,290 --> 00:59:08,320
en tiu aparta indekso kiu respondas al la litero.

661
00:59:08,320 --> 00:59:11,260
Do pensante la tutan vojon reen al Cezaro kaj Vigenère,

662
00:59:11,260 --> 00:59:16,070
sciante, ke ĉiu litero oni povas ia mapo reen al alfabeta indekso,

663
00:59:16,070 --> 00:59:20,690
definitive A tra Z tuj estos bela facila por mapi al alfabeta leteron,

664
00:59:20,690 --> 00:59:25,200
sed bedaŭrinde, apostrofoj estas ankaŭ akceptita karaktero en vortoj.

665
00:59:25,200 --> 00:59:31,650
Mi eĉ ne certas kion la ASCII valoro estas,

666
00:59:31,650 --> 00:59:39,250
tiel por ke, se vi volas trovi indekson por decidi ĉu vi volas ĝin al esti ĉu la unua

667
00:59:39,250 --> 00:59:44,550
aŭ la lasta, vi devos fari malfacilan kodita ĉeko por ke

668
00:59:44,550 --> 00:59:48,930
kaj tiam metis tiun en indekso 26, ekzemple.

669
00:59:48,930 --> 00:59:55,300
Tial vi kontroli la valoron al infanoj [i]

670
00:59:55,300 --> 00:59:58,400
kie [i] respondas al kiom letero vi estas en.

671
00:59:58,400 --> 01:00:04,110
Se tio NULL, tio signifas ke ne estas aktuale ajna ebla literoj

672
01:00:04,110 --> 01:00:08,150
devenaj de tiu antaŭa vico, do vi tuj volas malloc

673
01:00:08,150 --> 01:00:13,150
kaj fari novan nodon kaj havas ke infanoj [i] punkto al ĝi

674
01:00:13,150 --> 01:00:17,890
por ke vi kreas - kiam ni insertos leteron en la rektangulo -

675
01:00:17,890 --> 01:00:23,680
farante infanoj ne-NULL kaj punkto en tiu nova nodo.

676
01:00:23,680 --> 01:00:28,340
Sed se tiu ne estas NULL, kiel en nia petskribo de FOO

677
01:00:28,340 --> 01:00:34,570
kiam ni havis jam FOOBAR, ni daŭrigos,

678
01:00:34,570 --> 01:00:44,010
kaj ni ne estas iam farante nova nodo sed prefere nur opcio is_word al vera

679
01:00:44,010 --> 01:00:47,790
fine de tiu vorto.

680
01:00:50,060 --> 01:00:55,340
>> Tial, kiel antaŭe, ĉar ĉi tie vi pritraktas ĉiun literon samtempe,

681
01:00:55,340 --> 01:01:01,470
ĝi tuj estos pli facile por vi por grandeco, anstataŭ devi kalkuli

682
01:01:01,470 --> 01:01:06,910
kaj iru tra la tuta arbo kaj kalkuli kiom da infanoj mi havas

683
01:01:06,910 --> 01:01:10,850
kaj tiam debranĉo, memorante kiom estas sur la maldekstra flanko kaj sur la dekstra flanko

684
01:01:10,850 --> 01:01:12,850
kaj aĵoj kiel tiu, ĝi tuj estos multe pli facile por vi

685
01:01:12,850 --> 01:01:16,220
se vi nur konservi trako de kiom da vortoj vi aldonante en

686
01:01:16,220 --> 01:01:18,080
kiam vi kontraktanta kun ŝarĝo.

687
01:01:18,080 --> 01:01:22,630
Kaj tiel do tiel grandeco povas simple reveni al monda variablo de grandeco.

688
01:01:25,320 --> 01:01:28,530
>> Nun ni venas por kontroli.

689
01:01:28,530 --> 01:01:33,920
Samaj normoj kiel antaŭe, kie ni volas enkalkuli kazo insensibilidad.

690
01:01:33,920 --> 01:01:40,400
Tiel, ni supozas, ke la kordoj estas nur alfabeta karakteroj aŭ la apostrofoj

691
01:01:40,400 --> 01:01:44,000
ĉar infanoj estas tabelo de 27 longaj,

692
01:01:44,000 --> 01:01:48,480
tiel ĉiuj leteroj de la alfabeto plus la apostrofo.

693
01:01:48,480 --> 01:01:53,800
Por kontroli kion vi volas fari estas vi volas komenci ĉe la radiko

694
01:01:53,800 --> 01:01:58,440
ĉar la radiko indikas tabelo kiu enhavas

695
01:01:58,440 --> 01:02:01,630
ĉiuj eblaj startanta literoj de vorto.

696
01:02:01,630 --> 01:02:03,680
Vi tuj komenci tie,

697
01:02:03,680 --> 01:02:11,590
kaj tiam vi tuj kontroli estas tiu valoro NULL aŭ ne,

698
01:02:11,590 --> 01:02:16,490
ĉar se la valoro estas NULL, tio signifas ke la vortaro ne havas neniun valoroj

699
01:02:16,490 --> 01:02:21,480
kie troviĝas la leteron en tiu aparta ordo.

700
01:02:21,480 --> 01:02:24,970
Se ĝi estas NULL, tiam tiu signifas ke la vorto estas malbone skribita tuj.

701
01:02:24,970 --> 01:02:27,110
Sed se ĝi ne estas NULL, tiam vi povas daŭrigi,

702
01:02:27,110 --> 01:02:34,090
diri ke unua litero estas ebla unua litero en vorto,

703
01:02:34,090 --> 01:02:40,630
do nun mi volas kontroli ĉu la dua letero, ke vico, estas en mia vortaro.

704
01:02:40,630 --> 01:02:46,540
Do vi tuj iru al la indekso de la filoj de la unua nodo

705
01:02:46,540 --> 01:02:50,720
kaj kontrolu ĉu tiu dua letero ekzistas.

706
01:02:50,720 --> 01:02:57,440
Tiam vi ripeti tiun procezon por kontroli ĉu tiu vico estas valida aŭ ne

707
01:02:57,440 --> 01:02:59,060
inter viaj trie.

708
01:02:59,060 --> 01:03:06,430
Krom se la nodo infanoj en tiu indekso punktoj al nula,

709
01:03:06,430 --> 01:03:10,710
vi scias, ke tiu vico ne ekzistas,

710
01:03:10,710 --> 01:03:16,230
sed tiam, se vi atingas la fino de la vorto, kiun vi inputted,

711
01:03:16,230 --> 01:03:20,070
tiam vi volas kontroli nun ke mi kompletigis ĉi vico

712
01:03:20,070 --> 01:03:27,610
kaj trovis ĝin en mia trie, estas ke vorto valida aŭ ne?

713
01:03:27,610 --> 01:03:32,480
Kaj tiel do vi volas kontroli tion, kaj tio estas kiam se vi trovis ke vico,

714
01:03:32,480 --> 01:03:35,120
tiam vi volas kontroli, ĉu tiu vorto estas valida aŭ ne

715
01:03:35,120 --> 01:03:40,290
ĉar memori reen en la antaŭa kazo kiun mi tiris kie ni havis FOOB,

716
01:03:40,290 --> 01:03:48,410
kiu estis valida sekvenco kiu ni trovis, sed ne estis reala valida vorto mem.

717
01:03:50,570 --> 01:03:59,000
>> Simile, por malŝarĝi en la klopodoj vi volas malŝarĝi ĉiuj nodoj en via trie.

718
01:03:59,000 --> 01:04:04,790
Pardonu. Simila al la hash tabloj kie en malŝarĝi ni liberigxis ĉiuj nodoj,

719
01:04:04,790 --> 01:04:09,740
en la klopodoj ni volas ankaŭ liberigi ĉiujn nodoj.

720
01:04:09,740 --> 01:04:15,000
Malŝarĝi efektive funkcias plej facila el fundo supren

721
01:04:15,000 --> 01:04:19,290
ĉar ĉi tiuj estas esence ligitaj listoj.

722
01:04:19,290 --> 01:04:22,540
Do ni volas certigi, ke ni tenas al ĉiuj de la valoroj

723
01:04:22,540 --> 01:04:25,700
kaj libera ĉiuj ili eksplicite.

724
01:04:25,700 --> 01:04:28,840
Kion vi tuj volas fari se vi laboras kun trie

725
01:04:28,840 --> 01:04:35,640
estas vojaĝi al la fundo kaj libera la plej malalta ebla nodo unua

726
01:04:35,640 --> 01:04:39,190
kaj poste iru al ĉiuj el tiuj infanoj kaj tiam senpaga ĉiuj el tiuj,

727
01:04:39,190 --> 01:04:43,050
iru kaj tiam senpaga, ktp

728
01:04:43,050 --> 01:04:48,790
Ia kiel trakti kun la fundo tavolo de la trie unua

729
01:04:48,790 --> 01:04:51,940
kaj poste irante supren supro iam vi liberigita ĉion.

730
01:04:51,940 --> 01:04:56,720
Ĉi tiu estas bona ekzemplo de kie rekursia funkcio povus veni en oportuna.

731
01:04:56,720 --> 01:05:03,830
Kiam vi liberigis la fundo tavolo de via trie,

732
01:05:03,830 --> 01:05:08,000
tiam vi nomas malŝarĝi en la resto de ĝi,

733
01:05:08,000 --> 01:05:13,620
certigante ke vi liberigi ĉiun mini -

734
01:05:13,620 --> 01:05:16,410
Vi povas ia bildigi lin kiel mini provoj.

735
01:05:23,300 --> 01:05:28,990
Do vi havas vian radikon tie.

736
01:05:30,840 --> 01:05:35,230
Mi ĵus simplificadora ĝi do mi ne devas desegni 26 el ili.

737
01:05:37,250 --> 01:05:43,770
Do vi havas ĉi tiuj, kaj tiam ĉi tiuj reprezentas sekvencoj de vortoj

738
01:05:43,770 --> 01:05:54,620
kie ĉiuj el ĉi tiuj malgranduloj rondoj estas literoj kiuj estas validaj sekvencoj de literoj.

739
01:06:03,040 --> 01:06:07,160
Ni daŭrigos nur iom pli.

740
01:06:15,110 --> 01:06:25,750
Kion vi tuj volas fari estas libera la fundo tie kaj tiam senpaga ĉi tiu

741
01:06:25,750 --> 01:06:31,640
kaj poste liberaj ĉi tiu malsupre antaŭ vi liberigi la plej supra tien

742
01:06:31,640 --> 01:06:38,180
ĉar se vi liberan ion en la dua nivelo tie,

743
01:06:38,180 --> 01:06:47,230
tiam vi vere perdus tiun valoron tie.

744
01:06:47,230 --> 01:06:54,780
Tial ĝi estas grava en malŝarĝi por trie por certigi ke vi liberigos la fundo unua.

745
01:06:54,780 --> 01:06:59,480
Kion vi volus fari estas diri por ĉiu nodo

746
01:06:59,480 --> 01:07:06,430
Mi volas malŝarĝi ĉiuj de la infanoj.

747
01:07:16,060 --> 01:07:22,140
>> Nun kiam ni iris trans malŝarĝi la hash tablo metodo tiel kiel la trie metodo,

748
01:07:22,140 --> 01:07:27,020
nin tuj volas rigardi Valgrind.

749
01:07:27,020 --> 01:07:29,640
Valgrind vi kuras kun jenaj ordonoj.

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

751
01:07:32,700 --> 01:07:40,960
Vi kontrolanta por ĉiuj filtras kiam vi kuros Speller donita ĉi certaj teksto

752
01:07:40,960 --> 01:07:46,980
ĉar Speller bezonas preni en teksta dosiero.

753
01:07:46,980 --> 01:07:52,330
Do Valgrind kuros via programo, diros al vi, kiom da bitokoj vi destinis,

754
01:07:52,330 --> 01:07:57,150
kiom da bitokoj vi liberigas, kaj diros al vi ĉu vi liberigita nur tiom da

755
01:07:57,150 --> 01:07:58,930
aŭ ĉu vi ne liveris sufiĉe,

756
01:07:58,930 --> 01:08:02,850
aŭ kelkfoje vi povas eĉ tro libera, kiel libera nodo ke tio jam estas liberigitaj

757
01:08:02,850 --> 01:08:05,140
kaj tiel ĝi revenos al vi erarojn.

758
01:08:05,140 --> 01:08:11,600
Se vi uzas Valgrind, ĝi donos al vi mesaĝojn

759
01:08:11,600 --> 01:08:15,970
indikante ĉu vi liberigita ĉu malpli ol sufiĉa, nur sufiĉe,

760
01:08:15,970 --> 01:08:19,609
aŭ pli ol sufiĉa fojoj.

761
01:08:24,370 --> 01:08:30,410
>> Parto de tiu pset, estas laŭvola defii The Big Estraro.

762
01:08:30,410 --> 01:08:35,790
Sed kiam ni pritraktas tiujn datumstrukturoj

763
01:08:35,790 --> 01:08:40,689
ĝi estas speco de amuze vidi kiel rapide kaj kiel efika vian datumstrukturoj eblus.

764
01:08:40,689 --> 01:08:44,490
Ĉu viaj hash funkcio rezulto en tereno de kolizioj?

765
01:08:44,490 --> 01:08:46,300
Aŭ via datumoj grandeco vere granda?

766
01:08:46,300 --> 01:08:49,420
Ĉu ĝi prenas multan tempon por trairi?

767
01:08:49,420 --> 01:08:54,800
En la log'o da Speller, ĝi eligas kiom da tempo vi uzas por ŝarĝi,

768
01:08:54,800 --> 01:08:57,700
por kontroli, por efektivigi grandeco, kaj malŝarĝi,

769
01:08:57,700 --> 01:09:00,720
kaj tiel tiuj estas eldonitaj en The Big Estraro,

770
01:09:00,720 --> 01:09:03,600
kie vi povas konkurenci kontraŭ viaj samklasanoj

771
01:09:03,600 --> 01:09:11,350
kaj iuj stabanojn por vidi kiu havas la plej rapida literumilo.

772
01:09:11,350 --> 01:09:14,760
Unu afero, kiun mi ŝatus noti pri la hash tabloj

773
01:09:14,760 --> 01:09:20,470
estas, ke estas kelkaj belaj simpla kradaj funkcioj, ke ni povus pensi.

774
01:09:20,470 --> 01:09:27,240
Ekzemple, vi havas 26 siteloj, kaj tiel cxiu rubujo

775
01:09:27,240 --> 01:09:30,200
respondas al la unua litero en vorto,

776
01:09:30,200 --> 01:09:35,229
sed tio okazas al rezulti en belan desequilibrado hash tablo

777
01:09:35,229 --> 01:09:40,979
ĉar estas multe malpli da vortoj kiuj komencas kun ikso ol komenci kun M, ekzemple.

778
01:09:40,979 --> 01:09:47,890
Unu vojo por iri sur Speller estas se vi volas ricevi ĉiujn aliajn funkciojn sube,

779
01:09:47,890 --> 01:09:53,240
tiam simple uzi simplan hash funkcion por povi ricevi la kodo kurante

780
01:09:53,240 --> 01:09:58,650
kaj poste reiri kaj ŝanĝi la grandecon de via hash tablo kaj la difino.

781
01:09:58,650 --> 01:10:03,430
Estas multe da rimedoj en la Interreto por kradaj funkcioj,

782
01:10:03,430 --> 01:10:08,250
kaj tiel por tiu ĉi pset vi rajtas enketi kradaj funkcioj en la Interreto

783
01:10:08,250 --> 01:10:15,560
por iuj aludoj kaj inspiro tiel longe kiel vi certigi por citi kie vi ricevis ĝin de.

784
01:10:15,560 --> 01:10:22,060
Vi estas bonvena por rigardi kaj interpreti iuj hash funkcio kiu vi trovas en Interreto.

785
01:10:22,060 --> 01:10:27,460
Reen al tio, vi eble povus vidi se iu uzis trie

786
01:10:27,460 --> 01:10:31,700
ĉu ilia efektivigo estas pli rapida ol via hash tablo aŭ ne.

787
01:10:31,700 --> 01:10:35,290
Vi povas submetiĝi al The Big Estraro plurfoje.

788
01:10:35,290 --> 01:10:37,660
Ĝi gravuros via plej freŝaj eniro.

789
01:10:37,660 --> 01:10:44,300
Do eble vi ŝanĝos vian hash funkcio kaj tiam rimarkas ke fakte multe pli rapida

790
01:10:44,300 --> 01:10:46,780
aŭ multe pli malrapida ol antaŭe.

791
01:10:46,780 --> 01:10:50,960
Tio estas iom da amuza maniero.

792
01:10:50,960 --> 01:10:57,190
Ĉiam 1 aŭ 2 stabanojn, kiuj klopodas fari la plej malrapida ebla vortaro,

793
01:10:57,190 --> 01:11:00,210
por ke ĉiam amuze rigardi.

794
01:11:00,210 --> 01:11:07,630
>> La uzado dum la pset estas vi kuras Speller kun laŭvola vortaro

795
01:11:07,630 --> 01:11:12,840
kaj tiam deviga teksta dosiero.

796
01:11:12,840 --> 01:11:18,380
Implicite, kiam vi kuris Speller kun nur teksta dosiero kaj ne specifi vortaro,

797
01:11:18,380 --> 01:11:24,410
ĝi tuj uzi la vortaron teksta dosiero, la granda unu

798
01:11:24,410 --> 01:11:27,920
en la cs50/pset5/dictionaries dosierujo.

799
01:11:27,920 --> 01:11:32,760
Ke oni havas pli ol 100.000 vortojn.

800
01:11:32,760 --> 01:11:37,950
Ili ankaŭ havas malgrandan vortaron kiu havas konsiderinde malpli da vortoj

801
01:11:37,950 --> 01:11:40,730
ke CS50 faris por vi.

802
01:11:40,730 --> 01:11:44,050
Tamen, vi povas tre facile simple vian propran vortaro

803
01:11:44,050 --> 01:11:47,150
se vi volas nur esti laborante en malgrandaj ekzemploj -

804
01:11:47,150 --> 01:11:51,140
ekzemple, se vi volas uzi gdb kaj vi konas la specifan valoroj

805
01:11:51,140 --> 01:11:53,560
ke vi deziras ke viaj hash tablo por mapi al.

806
01:11:53,560 --> 01:12:00,430
Do vi povas simple fari vian propran teksta dosiero nur kun TRINKEJO, Baz, FOO, kaj FOOBAR,

807
01:12:00,430 --> 01:12:04,860
fari ke en teksto-dosiero, apartigi tiujn ĉiu kun 1 linio,

808
01:12:04,860 --> 01:12:12,670
kaj tiam fari vian propran teksta dosiero kiu laŭvorte nur enhavas eble 1 aŭ 2 vortojn

809
01:12:12,670 --> 01:12:15,950
por ke vi sciu precize kion la eligo devus esti.

810
01:12:15,950 --> 01:12:21,870
Kelkaj el la specimeno tekstaj dosieroj ke La Granda Estraro kiam vi kuros defio kontrolos

811
01:12:21,870 --> 01:12:25,580
estas Milito kaj Paco kaj Jane Austen romano aŭ io kiel tio.

812
01:12:25,580 --> 01:12:30,450
Do kiam vi komencante, estas multe pli facile fari vian propran tekstaj dosieroj

813
01:12:30,450 --> 01:12:34,160
kiuj enhavas nur kelkajn vortojn aŭ eble 10

814
01:12:34,160 --> 01:12:38,280
por ke vi povas aŭguri kio la rezulto devus esti

815
01:12:38,280 --> 01:12:42,880
kaj tiam kontroli ĝin kontraŭ tio, tiom pli kontrolita ekzemplo.

816
01:12:42,880 --> 01:12:45,820
Kaj tiel ekde ni pritraktas antaŭdirante kaj desegno aferojn ĉirkaŭe,

817
01:12:45,820 --> 01:12:48,690
denove mi volas kuraĝigi vin uzi plumon kaj paperon

818
01:12:48,690 --> 01:12:50,700
ĉar ĝi estas vere helpos al vi kun ĉi tiu -

819
01:12:50,700 --> 01:12:55,620
desegnaĵo la sagoj, kiel la hash tablo aŭ kiel via trie aspektas,

820
01:12:55,620 --> 01:12:57,980
kiam vi liberigante io kie la sagoj iras,

821
01:12:57,980 --> 01:13:01,730
vi tenas al sufiĉas, ĉu vi vidas neniun ligiloj malaperi

822
01:13:01,730 --> 01:13:05,750
kaj fali en la abismo de filtrita memoro.

823
01:13:05,750 --> 01:13:11,070
Do bonvolu, bonvolu provi desegni aferojn eĉ antaŭ ol vi atingos skribi kodo sube.

824
01:13:11,070 --> 01:13:14,520
Desegni aferojn por ke vi komprenu kiel la aferoj iras labori

825
01:13:14,520 --> 01:13:22,750
ĉar tiam Mi garantias al vi kuros en malpli puntero muddles tie.

826
01:13:24,270 --> 01:13:25,910
>> Bone.

827
01:13:25,910 --> 01:13:28,780
Mi volas deziri al vi la plej bona el sorton kun tiu pset.

828
01:13:28,780 --> 01:13:31,980
Estas probable la plej malfacila unu.

829
01:13:31,980 --> 01:13:40,360
Do provu komenci frue, desegni aferojn, desegni aferojn, kaj bona sorto.

830
01:13:40,360 --> 01:13:42,980
Tio estis Walkthrough 5.

831
01:13:45,160 --> 01:13:47,000
>> [CS50.TV]