1
00:00:00,000 --> 00:00:02,520
[Powered by Google Translate] [Semajno 6, daŭrigis]

2
00:00:02,520 --> 00:00:04,160
[Davido J. Malan] [Universitato Harvard]

3
00:00:04,160 --> 00:00:08,720
[Jen CS50.] [CS50.TV]

4
00:00:08,720 --> 00:00:12,970
Ĉi tiu estas CS50 kaj ĉi tiu estas la fino de semajno 6.

5
00:00:12,970 --> 00:00:17,970
Do CS50x, unu el Harvard unuaj kursoj implikita en la edX iniciato

6
00:00:17,970 --> 00:00:20,590
ja debutis la pasinta lundo.

7
00:00:20,590 --> 00:00:23,460
Se vi ŝatus ricevi bildon de aliaj en la interreto

8
00:00:23,460 --> 00:00:27,180
nun sekvi kune kun vi povas direkti al x.cs50.net.

9
00:00:27,180 --> 00:00:30,350
Tio alidirektilo vin al la taŭga loko sur edx.org,

10
00:00:30,350 --> 00:00:34,160
kiu estis kie ĉi tiu kaj aliaj kursoj de MIT kaj Berkeley nun vivas.

11
00:00:34,160 --> 00:00:38,140
Vi devos registri konton, vi trovos ke la materialo estas plejparte la sama

12
00:00:38,140 --> 00:00:42,170
kiel vi havis ĉi semestro, kvankam kelkaj semajnoj prokrastis, kiam ni atingos ĉiu lerta.

13
00:00:42,170 --> 00:00:46,930
Sed kion studentoj en CS50x nun vidas estas interfaco tute kiel ĉi tiu.

14
00:00:46,930 --> 00:00:50,040
Ĉi tio, ekzemple, estas Zamyla stirante la walkthrough por problemo aro 0.

15
00:00:50,040 --> 00:00:54,230
Sur ensalutante al edx.org, a CS50x studento vidas la varoj de aĵoj

16
00:00:54,230 --> 00:00:57,170
vi atendus vidi en kurso: la prelego por la lundo,

17
00:00:57,170 --> 00:01:01,650
prelego dum Merkredo, diversaj mallongaj, la problemo aroj, la walkthroughs, PDFs.

18
00:01:01,650 --> 00:01:04,459
Krome, kiel vi vidas tie, maŝino tradukoj

19
00:01:04,459 --> 00:01:08,390
de la angla transskriboj en la ĉinan, japanan, Hispana, Itala,

20
00:01:08,390 --> 00:01:12,810
kaj tuta amaso de aliaj lingvoj kiuj certe estos malperfekta

21
00:01:12,810 --> 00:01:15,840
kiel ni ruliĝi ilin el programmatically uzante iun nomita API,

22
00:01:15,840 --> 00:01:18,360
aŭ apliko programado interfaco, de Google

23
00:01:18,360 --> 00:01:21,360
kiu nin permesas konverti angla al tiuj aliaj lingvoj.

24
00:01:21,360 --> 00:01:24,100
Sed danke al la mirinda spirito de iu cent-plus volontuloj,

25
00:01:24,100 --> 00:01:26,940
hazarda homoj en la Interreto kiuj afable proponis al implikiĝi

26
00:01:26,940 --> 00:01:30,180
en ĉi tiu projekto, ni iom post iom plibonigi la kvaliton de tiuj tradukoj

27
00:01:30,180 --> 00:01:35,790
por havi la homoj korekti la erarojn ke nia komputiloj faris.

28
00:01:35,790 --> 00:01:42,330
>> Do rezultas ni kelkajn pli studentoj aperas lunde ol ni komence atendis.

29
00:01:42,330 --> 00:01:48,980
Fakte, nun CS50x havas 100.000 homoj sekvi kune hejme.

30
00:01:48,980 --> 00:01:54,430
Do realigi vi ĉiuj estas parto de tiu inaŭgura klaso de fari ĉi tiu kurso en komputiko

31
00:01:54,430 --> 00:01:57,370
eduko pli ĝenerale, pli vaste, atingebla.

32
00:01:57,370 --> 00:02:00,130
Kaj la realaĵo estas nun, kun kelkaj el tiuj amasaj retaj kursoj,

33
00:02:00,130 --> 00:02:04,070
ili ĉiuj starti kun tiuj tre altaj nombroj, kiel ni ŝajnas esti farita tie.

34
00:02:04,070 --> 00:02:08,759
Sed la celo, finfine, por CS50x estas vere akiri tiom da homoj al la linio fino ebla.

35
00:02:08,759 --> 00:02:12,000
Por dezajno, CS50x tuj proponos el tiu pasinteco lundo

36
00:02:12,000 --> 00:02:17,430
tuta vojo tra Aprilo 15, 2013, por ke homoj, kiuj havas lernejon devontigoj aliloke,

37
00:02:17,430 --> 00:02:20,990
laboro, familio, aliaj konfliktoj kaj similaj, havas iom pli fleksebleco

38
00:02:20,990 --> 00:02:23,640
kun kiu bucear en cxi tiun kurson, kiu, sufiĉas diri,

39
00:02:23,640 --> 00:02:30,540
estas sufiĉe ambicie farita se nur super la kurson de nur tri monatoj dum kutima semestro.

40
00:02:30,540 --> 00:02:34,190
Sed tiuj studentoj estos tuŝas la saman problemon aroj, vidante la sama enhavo,

41
00:02:34,190 --> 00:02:36,350
havi aliron al la sama pantalono kaj similaj.

42
00:02:36,350 --> 00:02:38,990
Do realigi ke ni ĉiuj vere en ĉi kune.

43
00:02:38,990 --> 00:02:42,360
Kaj unu el la fino celoj de CS50x ne estas nur por ricevi tiom da uloj

44
00:02:42,360 --> 00:02:45,720
al la linio kaj donu al ili tiun ĵus malkovrita kompreno de komputiko

45
00:02:45,720 --> 00:02:49,000
kaj programado sed ankaŭ havi ilin havas ĉi dividis sperto.

46
00:02:49,000 --> 00:02:52,010
Unu el la difinaj trajtoj de 50 en la campus, ni esperas,

47
00:02:52,010 --> 00:02:56,260
estis ĉi tia komunuma sperto, por pli bona aŭ por malbona, kelkfoje,

48
00:02:56,260 --> 00:02:59,480
sed havante tiujn homojn turni al la maldekstra kaj la dekstra,

49
00:02:59,480 --> 00:03:01,830
kaj oficejo horoj kaj la hackathon kaj la foiro.

50
00:03:01,830 --> 00:03:04,560
Ĝi estas iom pli malfacile fari tion persone kun uloj en linio,

51
00:03:04,560 --> 00:03:10,580
sed CS50x finos en aprilo kun la unua iam CS50 Expo,

52
00:03:10,580 --> 00:03:13,630
kiu estos interreta adapto de nia ideo de la foiro

53
00:03:13,630 --> 00:03:18,250
kie tiuj miloj da studentoj estos ĉiuj esti invitita al prezenti 1 - 2-minuta video,

54
00:03:18,250 --> 00:03:22,480
ĉu screencast de ilia fina projekto aŭ video el ili flirtis saluton

55
00:03:22,480 --> 00:03:24,490
kaj rakontis pri sia projekto kaj demoing ĝin,

56
00:03:24,490 --> 00:03:27,610
multe ŝatas vian antaŭuloj faris tie sur kampuso en la foiro,

57
00:03:27,610 --> 00:03:31,400
por ke per semestro la fino, la espero estas havi tutmondan ekspozicio

58
00:03:31,400 --> 00:03:37,080
de la CS50x studentoj 'fino projektoj, multe kiel tiu, kiu vin atendas ĉi decembro ĉi tie sur campus.

59
00:03:37,080 --> 00:03:39,680
Do pli en kiuj en la monatoj veni.

60
00:03:39,680 --> 00:03:43,640
>> Kun 100.000 studentoj, tamen, venas bezono por kelkaj pli CAS.

61
00:03:43,640 --> 00:03:47,590
Donita ke vi infanoj estas brilis la pulbazaro tie kaj prenante CS50

62
00:03:47,590 --> 00:03:51,630
pluraj semajnoj anticipe de ĉi tiu materialo ĵeto al la homoj sur edX,

63
00:03:51,630 --> 00:03:55,330
realigi ni amus impliki kiel multaj de niaj propraj studentoj kiel eble en tiu iniciato,

64
00:03:55,330 --> 00:03:58,720
ambaŭ dum la semestro tiel kiel ĉi tiu vintro kaj ĉi venas printempo.

65
00:03:58,720 --> 00:04:01,620
Do se vi ŝatus implikiĝi en CS50x,

66
00:04:01,620 --> 00:04:07,450
aparte aliĝi en sur CS50x diskuti, la edX versio de CS50 diskuti,

67
00:04:07,450 --> 00:04:10,140
kiu multaj de vi estas uzanta la kampuso, la linio bulteno tabulo,

68
00:04:10,140 --> 00:04:13,040
bonvolu fari kapon por ke URL, ni scias, kiu vi estas,

69
00:04:13,040 --> 00:04:16,450
ĉar ni ŝatus konstrui teamo de studentoj kaj personaro kaj fakultato egale

70
00:04:16,450 --> 00:04:19,630
sur kampuso kiuj simple ludas kune kaj helpi eksteren.

71
00:04:19,630 --> 00:04:21,720
Kaj kiam ili vidas demando kiu estas familiara al ili,

72
00:04:21,720 --> 00:04:25,320
vi aŭdas lernanto informis iu cimo ie tie en iu lando en la interreto

73
00:04:25,320 --> 00:04:27,450
kaj ke ringoj sonorilo ĉar vi tro havis tiun saman demandon

74
00:04:27,450 --> 00:04:32,620
en via d-salono iun tempon, mi esperas vi povas chime en kaj dividi viajn propra sperto.

75
00:04:32,620 --> 00:04:37,300
Do bonvolu partopreni, se vi ŝatus.

76
00:04:37,300 --> 00:04:39,360
>> Komputika kursoj en Harvard havas iom de la tradicio,

77
00:04:39,360 --> 00:04:44,730
CS50 inter ili, havi kelkajn vestojn, iuj vestojn, por ke vi povas porti fiere

78
00:04:44,730 --> 00:04:49,090
ĉe semestro la fino, dirante sufiĉe alten, ke vi finis CS50

79
00:04:49,090 --> 00:04:51,830
kaj prenis CS50 kaj similaj, kaj ni ĉiam provas impliki studentoj

80
00:04:51,830 --> 00:04:54,540
en ĉi tiu procezo kiel eble plej multe, per kiu ni invitas,

81
00:04:54,540 --> 00:04:56,900
ĉirkaŭ ĉi tempo de la semestro, studentoj submeti dezajnoj

82
00:04:56,900 --> 00:04:59,330
uzante Photoshop, aŭ kion ajn ilo de elekto vi ŝatus uzi

83
00:04:59,330 --> 00:05:02,330
se vi estas reĝisoro, submeti dezajnoj por T-ĉemizoj kaj sweatshirts

84
00:05:02,330 --> 00:05:06,100
kaj ombreloj kaj iom bandanas por hundoj ni nun havas kaj similaj.

85
00:05:06,100 --> 00:05:09,370
Kaj ĉio estas tiam - la gajnantoj ĉiujare estas poste elmetis

86
00:05:09,370 --> 00:05:12,700
en la paso de afiŝinto ĉe store.cs50.net.

87
00:05:12,700 --> 00:05:15,790
Ĉio estas vendita je kosto tie, sed la retejo ĵus kuras mem

88
00:05:15,790 --> 00:05:18,330
kaj permesas al la homo elektus la koloroj kaj desegnoj, ke ili ŝatas.

89
00:05:18,330 --> 00:05:20,420
Do mi pensis ke ni volas nur konigi kelkajn el la pasinta jaro dezajnoj

90
00:05:20,420 --> 00:05:25,130
kiuj estis sur la retejo krom ĉi tie, kiu estas jara tradicio.

91
00:05:25,130 --> 00:05:29,410
"Ĉiu tago mi seg Faultn" estis unu el la sendoj pasinta jaro,

92
00:05:29,410 --> 00:05:32,290
kio estas ankoraŭ disponebla tie por lernantoj.

93
00:05:32,290 --> 00:05:35,820
Ni havis ĉi tiu, "CS50, Fondita 1989."

94
00:05:35,820 --> 00:05:39,010
Unu el niaj Bowdens, Rob, estis tre populara pasintjare.

95
00:05:39,010 --> 00:05:43,480
"Team Bowden" naskiĝis, tiu dezajno donita, inter la supro vendistoj.

96
00:05:43,480 --> 00:05:49,040
Kiel estis tiun ĉi tie. Multaj homoj havis "Bowden Febro" laŭ la vendoj protokolojn.

97
00:05:49,040 --> 00:05:52,650
Rimarkas ke tiu povis nun estos via dezajno tie, sur la interreto.

98
00:05:52,650 --> 00:05:57,510
Pliaj detaloj sur ĉi en la sekva problemo aroj veni.

99
00:05:57,510 --> 00:06:00,330
>> Unu pli ilo: vi havis iun ekspozicion kaj espereble nun

100
00:06:00,330 --> 00:06:02,350
iuj manoj sur sperto kun GDB,

101
00:06:02,350 --> 00:06:04,570
kiu estas, kompreneble, erarserĉilo kaj permesas manipuli

102
00:06:04,570 --> 00:06:09,500
via programo ĉe sufiĉe malalta nivelo, fari kion specoj de aferoj?

103
00:06:09,500 --> 00:06:13,030
Kion GDB lasu vin fari?

104
00:06:13,030 --> 00:06:15,030
Yeah? Donu al mi ion. [Studenta respondo, nekomprenebla]

105
00:06:15,030 --> 00:06:18,120
Bona. Paŝo en funkcio, do vi ne nur devas tajpi kuri

106
00:06:18,120 --> 00:06:22,310
kaj havas la programon bato per sia tuteco, presi el aferojn cxefeligo.

107
00:06:22,310 --> 00:06:25,190
Pli ĝuste, vi povas treti tra ĝi linio por linio, ĉu tajpi sekva

108
00:06:25,190 --> 00:06:30,300
iri linio por linio por linio aŭ paŝo bucear en funkcio, tipe kiu vi skribis.

109
00:06:30,300 --> 00:06:35,240
Kion alian ne GDB lasu vin fari? Yeah? [Studenta respondo, nekomprenebla]

110
00:06:35,240 --> 00:06:38,100
Presi variabloj. Do se vi volas fari iom introspekto ene de via programo

111
00:06:38,100 --> 00:06:41,500
sen devi recurrir al skribi printf deklaroj tuta loko,

112
00:06:41,500 --> 00:06:44,600
vi povas simple presi variablo aŭ vidigi variablo.

113
00:06:44,600 --> 00:06:46,710
Kion alian vi povas fari kun erarserĉilo kiel GDB?

114
00:06:46,710 --> 00:06:49,170
[Studenta respondo, nekomprenebla]

115
00:06:49,170 --> 00:06:52,080
Ekzakte. Vi povas agordi breakpoints; vi povas diri ripozon ekzekuto

116
00:06:52,080 --> 00:06:54,020
ĉe la ĉefa funkcio aŭ la foo funkcio.

117
00:06:54,020 --> 00:06:56,800
Vi povas diri ripozon ekzekuto ĉe linio 123.

118
00:06:56,800 --> 00:06:58,950
Kaj breakpoints estas vere potenca tekniko

119
00:06:58,950 --> 00:07:01,110
ĉar se vi havas ĝeneralan senton de kie via problemo

120
00:07:01,110 --> 00:07:05,360
probable estas, vi ne devas perdi tempon tretante per la programo totalo.

121
00:07:05,360 --> 00:07:08,250
Vi povas esence salti rajtas tie kaj tiam komenci tajpi -

122
00:07:08,250 --> 00:07:10,970
tretante tra ĝi kun paŝo aŭ apud aŭ similaj.

123
00:07:10,970 --> 00:07:14,340
Sed la kaptita kun iu kiel GDB estas ke ĝi helpas vin, la homo,

124
00:07:14,340 --> 00:07:16,940
trovi vian problemojn kaj trovi vian cimojn.

125
00:07:16,940 --> 00:07:19,470
Ĝi ne nepre trovos ilin tiom por vi.

126
00:07:19,470 --> 00:07:23,070
>> Do ni enkondukis la alia tago style50, kiu estas mallonga komandlinio ilo

127
00:07:23,070 --> 00:07:27,500
kiu provas stylize via kodo iom pli pure ol vi, la homo, povus havi farita.

128
00:07:27,500 --> 00:07:29,530
Sed tio, ankaŭ, estas vere nur estetika afero.

129
00:07:29,530 --> 00:07:34,110
Sed ĝi rezultas tie estas tio alia ilo nomita Valgrind ke estas iom pli arcano uzi.

130
00:07:34,110 --> 00:07:36,860
Lia eligo estas atrociously críptico unuavide.

131
00:07:36,860 --> 00:07:39,420
Sed estas mirinde utila, speciale nun ke ni estas en la parto de la termino

132
00:07:39,420 --> 00:07:43,080
kie vi komencas uzi malloc kaj dinamika memoro atribuo.

133
00:07:43,080 --> 00:07:45,420
Aĵoj povas iri vere, vere malĝusta rapide.

134
00:07:45,420 --> 00:07:49,320
Ĉar se vi forgesos liberigi vian memoron, aŭ vi dereference iuj NULL pointer,

135
00:07:49,320 --> 00:07:55,770
aŭ vi dereference iuj rubo pointer, kio estas tipe la simptomo, ke rezultoj?

136
00:07:55,770 --> 00:07:59,470
Seg kulpo. Kaj vi ricevos tiun kernon dosiero de iu nombro da kilobajtoj aŭ megabajtoj

137
00:07:59,470 --> 00:08:02,990
kiu reprezentas la staton de via programo memoro kiam frakasis,

138
00:08:02,990 --> 00:08:05,730
sed via programo finfine seg kulpoj, segmentación kulpo,

139
00:08:05,730 --> 00:08:08,450
kiu signifas iun malbona okazis preskaŭ ĉiam rilatigita

140
00:08:08,450 --> 00:08:11,750
al la memoro-rilatajn eraro, ke vi faris ie.

141
00:08:11,750 --> 00:08:14,100
Do Valgrind helpas vin trovi aĵojn kiel ĉi tio.

142
00:08:14,100 --> 00:08:17,720
Ĝi estas ilo kiu vi kuros, kiel GDB, post vi kompilis vian programon,

143
00:08:17,720 --> 00:08:20,330
sed anstataŭ kuri via programo rekte, vi kuros Valgrind

144
00:08:20,330 --> 00:08:23,960
kaj pasas al ĝi vian programon, kiel vi faras kun GDB.

145
00:08:23,960 --> 00:08:26,220
Nun, la uzado, por atingi la plej bonaj speco de eligo,

146
00:08:26,220 --> 00:08:30,410
Estas iom longa, do dekstre tie sur la pinto de la ekrano, vi vidos Valgrind-v.

147
00:08:30,410 --> 00:08:35,350
"-V" preskaŭ universale signifas abundajn kiam vi uzas programojn sur Linukso komputilo.

148
00:08:35,350 --> 00:08:38,770
Do tio signifas kraĉi el pli datumoj ol vi povus defaŭlte.

149
00:08:38,770 --> 00:08:45,510
"- Fugon-check = plena." Tiu estas nur diras ĉeko por ĉiuj eblaj memoro fugoj,

150
00:08:45,510 --> 00:08:49,430
erarojn ke mi faris. Ĉi tio, ankaŭ, estas komuna paradigmo kun Linukso programoj.

151
00:08:49,430 --> 00:08:52,710
Ĝenerale, se vi havas komandlinio argumento kiu estas "switch",

152
00:08:52,710 --> 00:08:55,830
ke tio devus ŝanĝi la programon de la konduto, kaj ĝi estas sola litero,

153
00:08:55,830 --> 00:09:00,310
estas-v, sed se ke tio ŝanĝis, kun nur dezajno de la programisto,

154
00:09:00,310 --> 00:09:05,150
estas plena vorto aŭ serio da vortoj, la komanda linio argumento komenciĝas per -.

155
00:09:05,150 --> 00:09:08,190
Ĉi tiuj estas nur homaj konvencioj, sed vi vidas ilin ĉiam pli.

156
00:09:08,190 --> 00:09:12,410
Kaj poste, fine, "a.out" estas la arbitra nomo por la programo en ĉi tiu aparta ekzemplo.

157
00:09:12,410 --> 00:09:14,640
Kaj jen iuj reprezentanto eligo.

158
00:09:14,640 --> 00:09:22,890
>> Antaŭ ol ni rigardu kion tio povus signifi, ke mi transiru al fragmento de kodo super tie.

159
00:09:22,890 --> 00:09:26,390
Kaj lasu min movi tiun de la vojo, baldaŭ,

160
00:09:26,390 --> 00:09:32,120
kaj ni rigardu memory.c, kiu estas tiu mallonga ekzemplo tie.

161
00:09:32,120 --> 00:09:36,290
Do en tiu programo, mi zomi en la funkcioj kaj demandoj.

162
00:09:36,290 --> 00:09:39,430
Ni havas funkcion ĉefa kiu nomas funkcio, f,

163
00:09:39,430 --> 00:09:45,590
kaj tiam kion signifas f procedi por fari, en iomete teknika angla?

164
00:09:45,590 --> 00:09:49,760
Kion f procedi fari?

165
00:09:49,760 --> 00:09:53,680
Kion pri mi komencu per linio 20, kaj la stelo situo ne gravas,

166
00:09:53,680 --> 00:09:56,720
sed mi nur esti konsekvenca tie kun lasta prelego.

167
00:09:56,720 --> 00:09:59,910
Kio estas linio 20 vi por ni? Sur la maldekstra flanko. Ni rompos ĝin plu.

168
00:09:59,910 --> 00:10:02,410
Int * x: kion signifas tiu fari?

169
00:10:02,410 --> 00:10:04,940
Okay. Ĝi estas deklari pointer, kaj nun ni estos eĉ pli teknika.

170
00:10:04,940 --> 00:10:10,230
Kion tio signifas, tre konkrete, por deklari puntero? Iu alia?

171
00:10:10,230 --> 00:10:15,050
Yeah? [Studenta respondo, nekomprenebla] Tro multe.

172
00:10:15,050 --> 00:10:17,060
Do vi legas la dekstra flanko de la egala signo.

173
00:10:17,060 --> 00:10:20,290
Ni enfokusigi nur maldekstre, ĝuste sur int * x.

174
00:10:20,290 --> 00:10:24,700
Tiu signifas "deklari" puntero, sed nun estu la plonĝi en profundan al tiu difino.

175
00:10:24,700 --> 00:10:28,330
Kion tio konkrete, teknike signifas? Yeah?

176
00:10:28,330 --> 00:10:31,940
[Studenta respondo, nekomprenebla]

177
00:10:31,940 --> 00:10:35,090
Okay. Oni preparas por savi adreson en memoro.

178
00:10:35,090 --> 00:10:40,680
Bona. Kaj ni prenos ĉi unu paŝon; ĝi estas deklari variablon, x, jen 32 bitoj.

179
00:10:40,680 --> 00:10:44,440
Kaj mi scias ke estas 32 bitoj ĉar -?

180
00:10:44,440 --> 00:10:47,390
Ne ĉar ĝi estas int, ĉar ĝi estas puntero en ĉi tiu kazo.

181
00:10:47,390 --> 00:10:49,650
Koincido, ke ĝi estas unu kaj la sama kun int,

182
00:10:49,650 --> 00:10:51,970
sed la fakto ke estas la stelo ne signifas ĉi estas puntero

183
00:10:51,970 --> 00:10:57,300
kaj en la aparaton, kiel kun multaj komputiloj, sed ne ĉiuj, punteros estas 32 bitoj.

184
00:10:57,300 --> 00:11:01,850
Sur pli moderna aparataro kiel la lasta Macs, la lasta PC, vi eble havas 64-bitan punteros,

185
00:11:01,850 --> 00:11:04,160
sed en la aparaton, tiuj aferoj estas 32 bitoj.

186
00:11:04,160 --> 00:11:08,380
Do ni normigi sur tio. Pli konkrete, la historio iras tiel:

187
00:11:08,380 --> 00:11:10,820
Ni "deklari" puntero; kion tio signifas?

188
00:11:10,820 --> 00:11:12,810
Ni preparos por stoki memoro adreso.

189
00:11:12,810 --> 00:11:15,530
Kion tio signifas?

190
00:11:15,530 --> 00:11:19,810
Ni krei variablon nomitan x kiu okupas 32 bitoj

191
00:11:19,810 --> 00:11:23,810
kiu baldaŭ stoki la adreson de entjero.

192
00:11:23,810 --> 00:11:26,470
Kaj tio estas probable pri kiel preciza kiel ni povas akiri.

193
00:11:26,470 --> 00:11:31,810
Ĝi estas bone movi antaŭen al simpligi la mondo kaj nur diras deklari puntero nomata x.

194
00:11:31,810 --> 00:11:35,380
Deklari pointer, sed rimarkas kaj komprenas kio vere okazas

195
00:11:35,380 --> 00:11:38,490
eĉ en nur tiuj malmultaj gravuloj.

196
00:11:38,490 --> 00:11:42,040
>> Nun, ĉi tiu estas preskaŭ iom pli facila, kvankam ĝi estas pli longa esprimo.

197
00:11:42,040 --> 00:11:48,160
Do kio estas tiu faras, ke tio emfazita nun: "malloc (10 * sizeof (int))," Jes?

198
00:11:48,160 --> 00:11:52,350
[Studenta respondo, nekomprenebla]

199
00:11:52,350 --> 00:11:58,250
Bona. Kaj mi prenos ĝin tie. Oni atribuas la eron de memoro por dek entjeroj.

200
00:11:58,250 --> 00:12:02,190
Kaj nun ni plonĝi en iomete pli profunde; ĝi estas atribuo eron de memoro por dek entjeroj.

201
00:12:02,190 --> 00:12:05,390
Kio malloc tiam reveni?

202
00:12:05,390 --> 00:12:10,390
La adreso de tiu bloko, aŭ, pli konkrete, la adreso de la unua bitoko de tiu bloko.

203
00:12:10,390 --> 00:12:14,080
Kiel do mi, la programisto, scii kie tio eron de memoro finoj?

204
00:12:14,080 --> 00:12:18,340
Mi scias, ke ĝi estas apuda. Malloc, per difino, donos al vi apudan eron de memoro.

205
00:12:18,340 --> 00:12:21,240
Neniu mankojn en ĝi. Vi havas aliron al ĉiu bajto en tiu bloko,

206
00:12:21,240 --> 00:12:26,760
malantaŭo al malantaŭo al malantaŭo, sed kiel mi scias kie la fino de ĉi tiu bloko de memoro estas?

207
00:12:26,760 --> 00:12:28,850
Kiam vi uzas malloc? [Studenta respondo, nekomprenebla] Bona.

208
00:12:28,850 --> 00:12:30,670
Vi ne. Vi devas memori.

209
00:12:30,670 --> 00:12:35,960
Mi devas memori ke mi uzis la valoron 10, kaj mi eĉ ne ŝajnas esti farita, ke ĉi tie.

210
00:12:35,960 --> 00:12:41,000
Sed la onus estas tute en mi. Strlen, kiu ni fariĝis iomete dependis por kordoj,

211
00:12:41,000 --> 00:12:45,860
laboras nur pro tiu konvencio havi \ 0

212
00:12:45,860 --> 00:12:48,840
aŭ tiu speciala nul karaktero, NUL, fine de linio.

213
00:12:48,840 --> 00:12:51,740
Tio ne veras por nur arbitra pecoj de memoro.

214
00:12:51,740 --> 00:12:58,590
Ĝi dependas de vi. Do linio 20, tiam, allocates eron de memoro

215
00:12:58,590 --> 00:13:02,590
kiu povas stoki dek entjeroj, kaj stokas la adreso de la unua bitoko

216
00:13:02,590 --> 00:13:05,610
de tiu bloko de memoro en la variablo nomata x.

217
00:13:05,610 --> 00:13:11,140
Ergo, kiu estas puntero. Do linio 21, bedaŭrinde, estis eraro.

218
00:13:11,140 --> 00:13:16,110
Sed unue, kio estas tio faras? Oni diras vendejo en loko 10, 0 indeksita,

219
00:13:16,110 --> 00:13:19,480
de la bloko de memoro nomata x la valoron 0.

220
00:13:19,480 --> 00:13:21,510
>> Do rimarki kelkajn aferojn okazas.

221
00:13:21,510 --> 00:13:25,420
Kvankam x estas puntero, memori el paro semajnoj

222
00:13:25,420 --> 00:13:29,440
ke vi povas ankoraŭ uzi la tabelo-stilo kvadrata krampo skribmaniero.

223
00:13:29,440 --> 00:13:36,180
Ĉar tio estas vere mallonga mano skribmaniero por la pli kripta-aspekta puntero aritmetiko.

224
00:13:36,180 --> 00:13:40,320
kie ni devus fari ion kiel jene: Prenu la adreso x, movi 10 makuloj super,

225
00:13:40,320 --> 00:13:44,550
tiam iri tien al kiom adreso estas stokita en tiu loko.

226
00:13:44,550 --> 00:13:48,090
Sed sincere, ĉi tiu estas nur abomena por legi kaj akiri komforta kun.

227
00:13:48,090 --> 00:13:52,900
Do la mondo kutime uzas la rektaj krampoj nur ĉar ĝi estas tiel multe pli homa-amika legi.

228
00:13:52,900 --> 00:13:55,140
Sed tio kio vere okazas sub la kapuĉo;

229
00:13:55,140 --> 00:13:58,190
x estas adreso, ne tabelo, per si mem.

230
00:13:58,190 --> 00:14:02,410
Do tiu estas stokante 0 je situo 10 en x.

231
00:14:02,410 --> 00:14:06,120
Kial ĉi tiu malbona? Yeah?

232
00:14:06,120 --> 00:14:17,370
[Studenta respondo, nekomprenebla] Ekzakte.

233
00:14:17,370 --> 00:14:21,100
Ni nur atribuis dek ints, sed ni kalkulu de 0 kiam programado en C,

234
00:14:21,100 --> 00:14:25,690
do vi havas aliron al 0 1 2 3 4 5 6 7 8 9, sed ne 10.

235
00:14:25,690 --> 00:14:30,270
Do ĉu la programo tuj seg kulpo aŭ ĝi ne estas.

236
00:14:30,270 --> 00:14:32,900
Sed ni ne vere scias, kio estas speco de _nondeterministic_ konduto.

237
00:14:32,900 --> 00:14:35,600
Vere dependas sur ĉu ni preni bonŝanca.

238
00:14:35,600 --> 00:14:40,650
Se ĝi rezultas ke la mastruma sistemo ne gravas se mi uzas tiun ekstran bajto,

239
00:14:40,650 --> 00:14:43,360
kvankam ne donis ĝin al mi, mia programo eble ne frakasi.

240
00:14:43,360 --> 00:14:46,780
Estas kruda, estas kalesxon, sed vi povus ne vidi ke simptomo,

241
00:14:46,780 --> 00:14:48,960
aŭ vi povus vidi ĝin nur tempaltempe.

242
00:14:48,960 --> 00:14:51,230
Sed la realo estas ke la cimo estas, fakte, ne.

243
00:14:51,230 --> 00:14:54,320
Kaj estas vere problema se vi skribis programon kiu volas esti ĝentila,

244
00:14:54,320 --> 00:14:58,840
ke vi vendis la programo, ke homoj uzas ke ĉiu tempaltempe kraŝas

245
00:14:58,840 --> 00:15:02,450
ĉar, kompreneble, ĉi tio ne estas bona. Fakte, se vi havas Android telefonon aŭ iPhone

246
00:15:02,450 --> 00:15:05,550
kaj vi elŝuti apps tiuj tagoj, se vi iam havis programo nur quit,

247
00:15:05,550 --> 00:15:10,040
subite malaperas, ke estas preskaŭ ĉiam la rezulto de iu memoro-rilatajn afero,

248
00:15:10,040 --> 00:15:12,830
per kiu la programisto ŝraŭbita supren kaj dereferenced puntero

249
00:15:12,830 --> 00:15:18,670
ke li aŭ ŝi ne havas, kaj la rezulto de iOS aŭ Android estas nur mortigi la programo tute

250
00:15:18,670 --> 00:15:23,080
anstataŭ risko nedefinita konduto aŭ ia sekureco kompromison.

251
00:15:23,080 --> 00:15:25,950
>> Estas unu alia cimo en la programo krom ĉi tiu.

252
00:15:25,950 --> 00:15:30,180
Kion alian mi ŝraŭbita en tiu programo?

253
00:15:30,180 --> 00:15:32,740
Mi ne praktikis kion mi predikis. Yeah?

254
00:15:32,740 --> 00:15:34,760
[Studenta respondo, nekomprenebla] Bona.

255
00:15:34,760 --> 00:15:36,880
Mi ne liberigis la memoro. Do la regulo de thumb nun

256
00:15:36,880 --> 00:15:43,150
devas esti ajna momento vi nomas malloc, vi devas nomi liberaj kiam vi faris uzante tiu memoro.

257
00:15:43,150 --> 00:15:45,610
Nun, kiam estus mi volas liberigi ĉi memoro?

258
00:15:45,610 --> 00:15:49,780
Probable, supozante tiun unuan linion estis korekta, mi volas fari ĝin ĉi tie.

259
00:15:49,780 --> 00:15:55,710
Ĉar mi ne povis, ekzemple, faru ĝin ĉi tie. Kial?

260
00:15:55,710 --> 00:15:57,860
Ĝuste ekster atingo. Do eĉ se ni parolas pri punteros,

261
00:15:57,860 --> 00:16:04,830
ĉi tiu estas semajno 2 aŭ 3 demando, kie x estas nur en la medio interne de la frizita krampoj kie estis deklarita.

262
00:16:04,830 --> 00:16:11,000
Do vi certe ne povas liberigi ŝin tie. Mia sola ŝanco por liberigi estas proksimume post linio 21.

263
00:16:11,000 --> 00:16:15,170
Tio estas sufiĉe simpla programo; estis sufiĉe facila kiam oni ia envolvis via menso

264
00:16:15,170 --> 00:16:17,870
ĉirkaŭ kio la programo faras, kie la eraroj estis.

265
00:16:17,870 --> 00:16:20,500
Kaj eĉ se vi ne vidis gxin, unue, espereble ĝi estas iom evidenta nun

266
00:16:20,500 --> 00:16:23,870
ke tiuj eraroj bela facile solvitaj kaj facile faras.

267
00:16:23,870 --> 00:16:28,720
Sed kiam programo estas pli ol 12 linioj longaj, estas 50 linioj longaj, 100 linioj longaj,

268
00:16:28,720 --> 00:16:31,150
promenante tra via kodo linio por linio, pensante per ĝi logike,

269
00:16:31,150 --> 00:16:35,110
Eblas, sed ne aparte amuze fari, senĉese serĉas cimojn,

270
00:16:35,110 --> 00:16:38,340
kaj estas ankaŭ malfacila por fari, kaj tial ilo kiel Valgrind ekzistas.

271
00:16:38,340 --> 00:16:40,900
Lasu min kaj fari tion: mi malfermas mian fina fenestro,

272
00:16:40,900 --> 00:16:45,400
kaj lasu min ne nur kuri memoro, ĉar memoro ŝajnas esti bone.

273
00:16:45,400 --> 00:16:49,180
Mi ricevas bonŝanca. Irante al tiu plia bajto je la fino de la tabelo

274
00:16:49,180 --> 00:16:51,060
Ne ŝajnas esti tro problema.

275
00:16:51,060 --> 00:16:56,370
Sed mi, tamen, fari prudento ĉeko, kiu ĵus signifas por kontroli

276
00:16:56,370 --> 00:16:58,320
ĉu ĉi tiu estas vere ĝentilaj.

277
00:16:58,320 --> 00:17:04,690
>> Do ni faru valgrind-v - fugon-check = plena,

278
00:17:04,690 --> 00:17:07,520
kaj tiam la nomo de la programo en ĉi tiu kazo estas memoro, ne a.out.

279
00:17:07,520 --> 00:17:10,760
Do mi faru tion. Hit Eniru.

280
00:17:10,760 --> 00:17:14,109
Kara Dio. Ĉi tiu estas sian produktadon kaj ĉi tiu estas kion mi aludis al pli frua.

281
00:17:14,109 --> 00:17:17,550
Sed, se vi lernas legi tra ĉiuj sensencaĵon tie,

282
00:17:17,550 --> 00:17:20,760
plej de tio estas simple diagnozaj eligo tio ne tiu interesa.

283
00:17:20,760 --> 00:17:24,829
Kio via okulo vere volas esti serĉante estas ajna mencio de eraro aŭ malvalida.

284
00:17:24,829 --> 00:17:26,800
Vortoj kiuj sugestas problemojn.

285
00:17:26,800 --> 00:17:29,340
Kaj efektive, vidu kio okazas erara cxi tie.

286
00:17:29,340 --> 00:17:35,230
Mi havas resumon de iu varo, "en uzo ĉe eliro: 40 bitokoj en 1 blokoj."

287
00:17:35,230 --> 00:17:38,750
Mi ne vere certas kion bloko ankoraux, sed 40 bitokoj

288
00:17:38,750 --> 00:17:41,260
vere sentas mi povus eltrovi kie tiu venas de.

289
00:17:41,260 --> 00:17:45,030
40 bajtoj. Kial 40 bitokoj en uzo ĉe eliro?

290
00:17:45,030 --> 00:17:48,780
Kaj pli konkrete, se ni rulumu malsupren tie,

291
00:17:48,780 --> 00:17:54,520
kial mi definitive perdis 40 bitokoj? Yeah?

292
00:17:54,520 --> 00:17:59,520
[Studenta respondo, nekomprenebla] Perfekta. Yeah, precize.

293
00:17:59,520 --> 00:18:03,540
Tie estis dek entjeroj, kaj ĉiu el tiuj estas grandeco de 4, aŭ 32 bitoj,

294
00:18:03,540 --> 00:18:08,300
tiel mi perdis precize 40 bitokoj ĉar, kiel vi proponis, mi ne nomas libera.

295
00:18:08,300 --> 00:18:13,460
Tio estas unu cimon, kaj nun ni rigardu malsupren iom for kaj vidi apud ĉi tio,

296
00:18:13,460 --> 00:18:16,900
"Nevalida skribi de grandeco 4." Nun kio estas tio?

297
00:18:16,900 --> 00:18:21,150
Tiu adreso estas esprimita kion bazo skribmaniero, ŝajne?

298
00:18:21,150 --> 00:18:23,640
Ĉi tiu estas deksesuma, kaj iam vi vidas numeron ekde 0x,

299
00:18:23,640 --> 00:18:29,410
ĝi signifas deksesuma, kion ni faris vojon reen en, mi kredas, pset 0 La sekcio de demandoj,

300
00:18:29,410 --> 00:18:34,090
kiu estis nur fari warmup ekzerco, konvertanta dekuma al deksesumajn al binaraj ks.

301
00:18:34,090 --> 00:18:39,220
Deksesuma, kun nur homaj konvencio, estas kutime uzata por reprezenti punteros

302
00:18:39,220 --> 00:18:41,570
aŭ, pli ĝenerale, adresoj. Estas nur konvencio,

303
00:18:41,570 --> 00:18:45,340
ĉar ĝi estas iom pli facile legi, estas iom pli kompaktaj ol iu kiel decimala,

304
00:18:45,340 --> 00:18:47,720
kaj binara estas netaŭga por la plimulto homoj por uzi.

305
00:18:47,720 --> 00:18:50,840
Do nun kion tio signifas? Nu, tio aspektas kiel ekzistas nevalidan skribu

306
00:18:50,840 --> 00:18:54,480
de grandeco 4 en linio 21 de memory.c.

307
00:18:54,480 --> 00:18:59,180
Do ni revenu al la linio 21, kaj ja, jen estas tiu nevalida skribu.

308
00:18:59,180 --> 00:19:02,640
Do Valgrind ne tuj tute teni mian manon, kaj diru al mi kion la riparas estas,

309
00:19:02,640 --> 00:19:05,520
sed detekti ke mi faras nevalidan skribu.

310
00:19:05,520 --> 00:19:08,800
Mi tuŝas 4 bajtoj, ke mi ne estos, kaj ŝajne tio estas ĉar,

311
00:19:08,800 --> 00:19:13,960
kiel vi atentigis, mi faras [10] anstataŭ [9] maksimume

312
00:19:13,960 --> 00:19:16,660
aŭ [0] aŭ io inter ili.

313
00:19:16,660 --> 00:19:19,690
Kun Valgrind, realigi ajn vi nun skribas programo

314
00:19:19,690 --> 00:19:24,190
kiu uzas punteros kaj uzas memoron kaj malloc pli specife,

315
00:19:24,190 --> 00:19:27,080
definitive eniri la kutimo de kuri ĉi tiu longa

316
00:19:27,080 --> 00:19:30,890
sed tre facile kopiitaj kaj pasted komando de Valgrind

317
00:19:30,890 --> 00:19:32,650
por vidi, ĉu ekzistas iuj eraroj en tie.

318
00:19:32,650 --> 00:19:34,820
Kaj estos blindiga ĉiufoje kiam vi vidos la eliron,

319
00:19:34,820 --> 00:19:39,430
sed ĝuste analizi tra vide ĉiujn eligo kaj vidu se vi vidas mencioj de eraroj

320
00:19:39,430 --> 00:19:43,190
aŭ avertoj nek nevalida aŭ perditaj.

321
00:19:43,190 --> 00:19:46,200
Ajna vortoj kiuj sonas same kiel vi ŝraŭbita supren ie.

322
00:19:46,200 --> 00:19:48,580
Do rimarkas ke estas nova ilo en via ilaron.

323
00:19:48,580 --> 00:19:51,270
>> Nun lundon, ni havis tutan faskon da uloj venos supren ĉi tien

324
00:19:51,270 --> 00:19:53,150
kaj reprezenti la nocio de ligitaj listo.

325
00:19:53,150 --> 00:20:00,970
Kaj ni enkondukis la ligitaj listo kiel solvo al kio problemo?

326
00:20:00,970 --> 00:20:04,590
Yeah? [Studenta respondo, nekomprenebla] Bona.

327
00:20:04,590 --> 00:20:06,530
Arrays ne povas havi memoron aldonis ilin.

328
00:20:06,530 --> 00:20:09,440
Se vi destini tabelo de amplekso 10, kiu estas ĉio vi ricevas.

329
00:20:09,440 --> 00:20:13,690
Vi povas nomi funkcion kiel realloc se vi komence nomis malloc,

330
00:20:13,690 --> 00:20:17,580
kaj kiu povas provi kreski la tabelo se estas spaco al la fino de tio

331
00:20:17,580 --> 00:20:21,610
ke neniu alia uzas, kaj se ne, gxi simple trovi vin pli grandan parton aliloke.

332
00:20:21,610 --> 00:20:25,040
Sed tiam ĝin kopios ĉiuj el tiuj bajtoj en la nova tabelo.

333
00:20:25,040 --> 00:20:28,310
Ĉi sonas kiel tre ĝentila solvo.

334
00:20:28,310 --> 00:20:34,790
Kial estas ĉi enuaj?

335
00:20:34,790 --> 00:20:36,940
Mi volas diri ĝi funkcias, la homoj solvis tiun problemon.

336
00:20:36,940 --> 00:20:40,710
Kial ni bezonas solvi ĝin lunde kun ligitaj listoj? Yeah?

337
00:20:40,710 --> 00:20:44,060
[Studenta respondo, nekomprenebla] Ĝi povis porti longa tempo.

338
00:20:44,060 --> 00:20:49,260
Fakte, ajna tempo vi vokas malloc aŭ realloc aŭ calloc, kiu estas ankoraŭ alia,

339
00:20:49,260 --> 00:20:52,470
ajn vi, la programo, parolas al la mastruma sistemo,

340
00:20:52,470 --> 00:20:54,310
vi emas prokrasti la programo sube.

341
00:20:54,310 --> 00:20:57,470
Kaj se vi faras tiajn aferojn en cikloj, vi vere malrapidiĝanta aĵoj sube.

342
00:20:57,470 --> 00:21:00,740
Vi ne tuj rimarkas tion por la plej simpla el "saluton mondo" tipo programoj,

343
00:21:00,740 --> 00:21:04,300
sed en multe pli granda programoj, petante la mastruma sistemo denove kaj denove por memoro

344
00:21:04,300 --> 00:21:07,520
aŭ doni ĝin reen kaj denove inklinas ne esti bona afero.

345
00:21:07,520 --> 00:21:11,210
Plus, ĝi estas nur ia intelekte - ĝi estas kompleta perdo de tempo.

346
00:21:11,210 --> 00:21:16,490
Kial atribui pli kaj pli memoro, risko kopii ĉion en la nova tabelo,

347
00:21:16,490 --> 00:21:21,980
se vi havas alternativon kiu ebligas vin atribui nur tiel memoro kiel vi vere bezonas?

348
00:21:21,980 --> 00:21:24,130
Do tie estas pluses kaj malpli en ĉi tie.

349
00:21:24,130 --> 00:21:26,730
Unu el la pluses nun estas ke ni havas dinamismo.

350
00:21:26,730 --> 00:21:29,100
Ne gravas kie la pecoj de memoro estas ke estas libera,

351
00:21:29,100 --> 00:21:32,070
Mi povas nur ordigi de krei tiujn pano panpecetoj tra punteros

352
00:21:32,070 --> 00:21:34,470
al string mia tuta ligitaj listo kune.

353
00:21:34,470 --> 00:21:36,470
Sed mi pagas almenaŭ unu prezo.

354
00:21:36,470 --> 00:21:40,060
>> Kion mi devas rezigni en gajni ligitaj listoj?

355
00:21:40,060 --> 00:21:42,470
Yeah? [Studenta respondo, nekomprenebla] Bona.

356
00:21:42,470 --> 00:21:45,650
Vi bezonas pli memoro. Nun mi bezonas spacon por tiuj indikoj,

357
00:21:45,650 --> 00:21:47,900
kaj en la kazo de ĉi tiu super simpla ligitaj listo

358
00:21:47,900 --> 00:21:51,410
ke nur provas gardi entjeroj, kio estas 4 bitokoj, ni parolas tiele

359
00:21:51,410 --> 00:21:54,240
bone, puntero estas 4 bajtoj, do nun mi laŭvorte duobliĝis

360
00:21:54,240 --> 00:21:57,290
la kvanto de memoro mi bezonas nur por stoki tiu listo.

361
00:21:57,290 --> 00:21:59,680
Sed denove, ĉi tiu estas konstanta tradeoff en komputiko

362
00:21:59,680 --> 00:22:03,440
inter tempo kaj spaco kaj disvolviĝo, penado kaj aliaj rimedoj.

363
00:22:03,440 --> 00:22:06,630
Kio estas alia malavantaĝo de uzante ligitaj listo? Yeah?

364
00:22:06,630 --> 00:22:10,150
[Studenta respondo, nekomprenebla]

365
00:22:10,150 --> 00:22:12,600
Bona. Ne tiel facila por aliri. Ni jam ne povas utiligi

366
00:22:12,600 --> 00:22:15,530
semajno 0 principoj kiel dividi kaj venki.

367
00:22:15,530 --> 00:22:18,220
Kaj pli specife, duuma serĉo. Ĉar eĉ se ni homoj

368
00:22:18,220 --> 00:22:20,400
povas vidi proksimume kie la mezo de ĉi tiu listo estas,

369
00:22:20,400 --> 00:22:25,840
la komputilo nur scias ke ĉi ligitaj listo komenciĝas ĉe adreso nomita unue.

370
00:22:25,840 --> 00:22:28,250
Kaj tio estas 0x123 aŭ io kiel tio.

371
00:22:28,250 --> 00:22:30,990
Kaj la sola maniero la programo povas trovi la mezo elemento

372
00:22:30,990 --> 00:22:33,350
estas vere sercxi la tuta listo.

373
00:22:33,350 --> 00:22:35,500
Kaj eĉ tiam, ĝi laŭvorte devas serĉi en la tuta listo ĉar

374
00:22:35,500 --> 00:22:38,950
eĉ kiam vi atingos la meza ero sekvante la punteros,

375
00:22:38,950 --> 00:22:42,380
vi, la programo, havas neniun ideon kiel longe tiu listo estas, potenciale,

376
00:22:42,380 --> 00:22:45,250
ĝis vi batis la fino de ĝi, kaj kiel vi scias programmatically

377
00:22:45,250 --> 00:22:48,600
ke vi estas ĉe la fino de ligitaj listo?

378
00:22:48,600 --> 00:22:51,120
Ekzistas speciala NULL pointer, do denove, konvencio.

379
00:22:51,120 --> 00:22:53,870
Anstataŭ uzi ĉi pointer, ni definitive ne deziras ke ĝi estu iu rubo valoro

380
00:22:53,870 --> 00:22:57,750
indikante sur scenejo ie; ni volas ke ĝi estu mano malsupren, NULL,

381
00:22:57,750 --> 00:23:01,530
por ke ni havas ĉi termino en ĉi datumstrukturo tiamaniere ni scias kie ĝi finiĝas.

382
00:23:01,530 --> 00:23:03,410
>> Kio se ni volas manipuli tio?

383
00:23:03,410 --> 00:23:05,980
Ni faris la plimulton de ĉi vide, kaj kun homoj,

384
00:23:05,980 --> 00:23:07,630
sed kio se ni volas fari inserción?

385
00:23:07,630 --> 00:23:12,360
Do la originala listo havis 9, 17, 20, 22, 29, 34.

386
00:23:12,360 --> 00:23:16,730
Kio se ni tiam volis malloc spaco por numero 55, nodo por tio,

387
00:23:16,730 --> 00:23:20,730
kaj poste ni volas enmeti 55 en la listo kiel ni faris lunde?

388
00:23:20,730 --> 00:23:23,690
Kiel ni faru tion? Nu, Anita venis kaj ŝi esence piediris la listo.

389
00:23:23,690 --> 00:23:27,500
Ŝi komencis je la unua elemento, tiam la sekva, la sekva, la sekva, la sekva, la sekvanta.

390
00:23:27,500 --> 00:23:29,500
Fine batis la maldekstra mano la tuta vojo malsupren

391
00:23:29,500 --> 00:23:34,480
kaj realigita oh, tio estas NULL. Do kio puntero manipulado bezonas fari?

392
00:23:34,480 --> 00:23:37,980
La persono kiu estis sur la pinto, numero 34, bezonis lian maldekstran manon levis

393
00:23:37,980 --> 00:23:46,220
atentigi je 55, 55 bezonis lian maldekstran brakon montrante malsupren por esti la nova NULL finilo. Faris.

394
00:23:46,220 --> 00:23:49,540
Bela facile enigi 55 en ordo listo.

395
00:23:49,540 --> 00:23:51,800
Kaj kiel povus tiu aspektas?

396
00:23:51,800 --> 00:23:55,690
>> Lasu min kaj malfermu iun kodo ekzemple ĉi tie.

397
00:23:55,690 --> 00:23:58,120
Mi malfermu gedit, kaj lasu min malfermi du dosierojn unua.

398
00:23:58,120 --> 00:24:02,050
Unu estas list1.h, kaj lasu min nur memorigi ke tio estas la bloko de kodo

399
00:24:02,050 --> 00:24:04,920
kiun ni uzas por reprezenti nodo.

400
00:24:04,920 --> 00:24:13,040
Nodo havas ambaŭ kiel int nomis n kaj puntero nomis sekva ke ĵus antaŭ la proksima afero en la listo.

401
00:24:13,040 --> 00:24:15,450
Tio estas nun en al. H dosiero. Kial?

402
00:24:15,450 --> 00:24:19,090
Estas ĉi tiu konvencio, kaj ni ne eluzis ĉi grandega kvanto ni mem,

403
00:24:19,090 --> 00:24:22,220
sed la persono kiu skribis printf kaj aliajn funkciojn

404
00:24:22,220 --> 00:24:27,150
donis kiel donaco al la mondo ĉiuj tiuj funkcioj skribante dosieron nomata stdio.h.

405
00:24:27,150 --> 00:24:30,950
Kaj tiam ekzistas string.h, kaj tiam tie estas map.h, kaj tie estas ĉiuj tiuj h dosieroj

406
00:24:30,950 --> 00:24:34,410
ke vi vidis aŭ uzis dum la termino skribita de aliaj personoj.

407
00:24:34,410 --> 00:24:38,470
Tipe en tiuj. H dosieroj estas nur aĵoj kiel typedefs

408
00:24:38,470 --> 00:24:42,310
aŭ deklaroj de kutimo tipoj aŭ deklaroj de konstantaj.

409
00:24:42,310 --> 00:24:47,890
Vi ne metis funkcioj 'implementaciones en header files.

410
00:24:47,890 --> 00:24:50,570
Vi metis, anstataŭ, ĝuste iliaj prototipoj.

411
00:24:50,570 --> 00:24:53,050
Vi metis tion vi volas dividi kun la mondo, kion ili bezonas

412
00:24:53,050 --> 00:24:55,640
por kompili sian kodon. Do nur por eniri ĉi kutimo,

413
00:24:55,640 --> 00:24:59,110
ni decidis fari la samon. Ne ekzistas multe en list1.h,

414
00:24:59,110 --> 00:25:02,070
sed ni metis iun kiu povus esti de intereso al la homo en la mondo

415
00:25:02,070 --> 00:25:05,030
kiuj volas uzi nian ligillisto efektivigo.

416
00:25:05,030 --> 00:25:08,040
Nun, en list1.c, mi ne iros tra tiu tuta afero

417
00:25:08,040 --> 00:25:11,390
ĉar ĝi estas iom longa, tiu programo, sed ni kuras ĝi realan rapide ĉe la prompto.

418
00:25:11,390 --> 00:25:15,720
Lasu min kompili list1, lasu min tiam kuras list1, kaj kion vi vidos estas

419
00:25:15,720 --> 00:25:18,070
Ni simulita simpla iom programo tie

420
00:25:18,070 --> 00:25:20,990
ke tuj permesos ke mi aldoni kaj forigi nombroj al listo.

421
00:25:20,990 --> 00:25:24,310
Do lasu min antaŭeniri kaj tajpu 3 por la menuo eblo 3.

422
00:25:24,310 --> 00:25:27,880
Mi volas enmeti la numeron - ni faru la unua numero, kiu estis 9,

423
00:25:27,880 --> 00:25:30,550
kaj nun mi diris al la listo estas nun 9.

424
00:25:30,550 --> 00:25:33,760
Lasu min kaj faru alian inserción, do mi batis menuo 3.

425
00:25:33,760 --> 00:25:36,760
Kio nombro mi volas enmeti? 17.

426
00:25:36,760 --> 00:25:39,220
Eniri. Kaj mi faros nur unu pli.

427
00:25:39,220 --> 00:25:41,720
Lasu min enmeti la numeron 22.

428
00:25:41,720 --> 00:25:45,850
Do ni havas la komencoj de la ligitaj listo por ke ni havis en slide formo antaŭ momento.

429
00:25:45,850 --> 00:25:48,740
Kiel tiu inserción vere okazas?

430
00:25:48,740 --> 00:25:52,000
Ja, 22 estas nun ĉe la fino de la listo.

431
00:25:52,000 --> 00:25:55,050
Do la rakonton ni diris en la scenejo lundon kaj recapped gxuste nun

432
00:25:55,050 --> 00:25:57,460
devas vere povus okazi en kodo.

433
00:25:57,460 --> 00:25:59,700
Ni rigardu. Lasu min rulumi malsupren en ĉi tiu dosiero.

434
00:25:59,700 --> 00:26:01,720
Ni glosan super iu el la funkcioj,

435
00:26:01,720 --> 00:26:05,630
sed ni iros malsupren por, ni diru, la insert funkcio.

436
00:26:05,630 --> 00:26:11,720
>> Ni vidos kiel ni iru sur la enmeto de nova nodo en tiun ligitaj listo.

437
00:26:11,720 --> 00:26:14,550
Kie estas la listo deklaris? Nu, ni rulumi la tuta vojo ĝis al la supro

438
00:26:14,550 --> 00:26:19,970
kaj rimarki ke mia ligitaj listo estas esence deklaris kiel sola puntero jen komence NULL.

439
00:26:19,970 --> 00:26:23,180
Do mi uzas malloka variablo tie, kiu ĝenerale ni predikis kontraŭ

440
00:26:23,180 --> 00:26:25,280
ĉar ĝi faras vian kodo iom senorda subteni,

441
00:26:25,280 --> 00:26:29,080
ĝi estas speco de mallaborema, kutime, sed ne estas pigra kaj ne erara kaj ne malbona

442
00:26:29,080 --> 00:26:33,660
se via programo sola celo en la vivo estas por simuli unu ligillisto.

443
00:26:33,660 --> 00:26:35,460
Kio estas ĝuste tio, kion ni faras.

444
00:26:35,460 --> 00:26:39,100
Do anstataŭ deklari tion en ĉefaj kaj tiam devas pasi ĝin al ĉiu funkcio

445
00:26:39,100 --> 00:26:42,640
ni skribis en tiu programo, ni anstataŭ realigi oh, ni nur faras tutmonda

446
00:26:42,640 --> 00:26:47,060
ĉar la tuta celo de tiu programo estas pruvi unu kaj nur unu ligitaj listo.

447
00:26:47,060 --> 00:26:50,700
Por ke sentu bone. Jen mia prototipoj, kaj ni ne iros tra ĉiuj el tiuj,

448
00:26:50,700 --> 00:26:55,800
sed mi skribis delete funkcio, oni trovos funkcio, oni insert funkcio, kaj través funkcio.

449
00:26:55,800 --> 00:26:59,080
Sed ni nun reiru malsupren al la insert funkcio

450
00:26:59,080 --> 00:27:01,490
kaj vidi kiel ĉi tiu laboras tie.

451
00:27:01,490 --> 00:27:09,940
Insert estas ĉe linio - tie ni iru.

452
00:27:09,940 --> 00:27:12,850
Enmetu. Do ĝi ne prenas neniun argumentojn, ĉar nin tuj demandas

453
00:27:12,850 --> 00:27:15,930
la uzanto ene de ĉi tiu funkcio por la nombro ili volas enŝovu.

454
00:27:15,930 --> 00:27:19,410
Sed unue, ni preparas por doni al ili iun spacon.

455
00:27:19,410 --> 00:27:22,050
Tio estas speco de kopio kaj alglui el la alia ekzemplo.

456
00:27:22,050 --> 00:27:25,110
En tiu kazo, ni estis atribui al int; ĉi tempo ni atribui nodo.

457
00:27:25,110 --> 00:27:27,910
Mi ne vere memoras kiom da bitokoj nodo estas, sed tio estas bone.

458
00:27:27,910 --> 00:27:30,460
Sizeof povas kompreni ke por mi.

459
00:27:30,460 --> 00:27:33,340
Kaj kial mi kontrolanta por NULL en linio 120?

460
00:27:33,340 --> 00:27:37,530
Kio povus erari en linio 119? Yeah?

461
00:27:37,530 --> 00:27:40,530
[Studenta respondo, nekomprenebla]

462
00:27:40,530 --> 00:27:43,440
Bona. Nur povus esti la kazo ke mi petis tro da memoro

463
00:27:43,440 --> 00:27:47,020
aŭ io la malbonon kaj la mastruma sistemo ne havas sufiĉe da bitokoj por doni al mi,

464
00:27:47,020 --> 00:27:50,640
tial ĝi markas tiel por reveni NULL, kaj se mi ne kontroli por ke

465
00:27:50,640 --> 00:27:54,710
kaj mi simple blinde procedi por uzi la adreson revenis, ĝi povus esti NULL.

466
00:27:54,710 --> 00:27:58,400
Ĝi povus esti iu nekonata valoro; ne estas bona afero se mi -

467
00:27:58,400 --> 00:28:00,590
efektive ne estos nekonataj valoro. Ĝi povus esti NULL, do mi ne volas

468
00:28:00,590 --> 00:28:02,550
trouzi kaj riski dereferencing ĝin.

469
00:28:02,550 --> 00:28:07,410
Se tio okazas, mi simple reveni kaj ni ŝajnigi kiel mi ne reiros ajna memoro ajn.

470
00:28:07,410 --> 00:28:12,270
>> Alie, mi diras al la uzanto doni al mi kelkajn insertar, mi vokas nia malnova amiko GetInt,

471
00:28:12,270 --> 00:28:15,530
kaj tiam ĉi estis la nova sintakso ni enkondukis lundon.

472
00:28:15,530 --> 00:28:20,320
'Newptr-> n' signifas preni la adreso, kiun vi estis donita per malloc

473
00:28:20,320 --> 00:28:23,490
kiu reprezentas la unua bajto de nova nodo objekto,

474
00:28:23,490 --> 00:28:26,860
kaj poste iru al la kampo nomata n.

475
00:28:26,860 --> 00:28:35,270
Iom vidindaĵoj demando: Ĉi tiu estas ekvivalento al kio pli kripta linio de kodo?

476
00:28:35,270 --> 00:28:38,110
Kiel alie povus mi skribis tion? Volas preni ponardopiko?

477
00:28:38,110 --> 00:28:41,480
[Studenta respondo, nekomprenebla]

478
00:28:41,480 --> 00:28:44,870
Bona. Uzante la. N, sed ĝi ne estas tiom simpla kiel tiu ĉi.

479
00:28:44,870 --> 00:28:47,090
Kion mi unue bezonas fari? [Studenta respondo, nekomprenebla]

480
00:28:47,090 --> 00:28:52,730
Bona. Mi bezonas fari * newptr.n.

481
00:28:52,730 --> 00:28:55,610
Do tiu estas jene nova puntero estas evidente adreson. Kial?

482
00:28:55,610 --> 00:28:59,520
Ĉar ĝi revenis por malloc. La * newptr dirante "iri tien,"

483
00:28:59,520 --> 00:29:02,970
kaj poste kiam vi estas tie, vi povas uzi la pli familiara. n,

484
00:29:02,970 --> 00:29:05,730
sed ĉi nur aspektas iom malbela, speciale se ni homoj tuj

485
00:29:05,730 --> 00:29:10,360
desegni punteros kun sagoj tutan tempon; la mondo havas normigita sur ĉi sago skribmaniero,

486
00:29:10,360 --> 00:29:12,320
kiu faras ĝuste la samon.

487
00:29:12,320 --> 00:29:16,070
Do vi nur uzu la -> notacio kiam la afero sur la maldekstra estas puntero.

488
00:29:16,070 --> 00:29:18,790
Alie, se ĝi estas reala struct, uzu la. N.

489
00:29:18,790 --> 00:29:25,800
Kaj tiam tiu: Kial mi pravalorizi newptr-> apud nula?

490
00:29:25,800 --> 00:29:28,610
Ni ne volas pendantaj maldekstra mano for de la fino de la scenejo.

491
00:29:28,610 --> 00:29:31,630
Ni volas ĝin montrante rekte malsupren, kio signifas la finon de ĉi tiu listo

492
00:29:31,630 --> 00:29:34,980
povus potenciale esti en ĉi tiu nodo, tial ni pli bone certigi estas NULL.

493
00:29:34,980 --> 00:29:38,460
Kaj, ĝenerale, inicializar vian variabloj aŭ viajn datumojn membroj kaj structs

494
00:29:38,460 --> 00:29:40,470
al io estas nur bona praktiko.

495
00:29:40,470 --> 00:29:45,170
Nur lasi rubo ekzisti kaj daŭre ekzistas ĝenerale ricevas vin en mizero

496
00:29:45,170 --> 00:29:48,650
se vi forgesas fari ion poste.

497
00:29:48,650 --> 00:29:51,590
>> Jen kelkaj kazoj. Ĉi tio, denove, estas la insert funkcio,

498
00:29:51,590 --> 00:29:54,930
kaj la unua afero, kiun mi kontroli estas se la variablo nomita unue,

499
00:29:54,930 --> 00:29:58,240
ke tutmonda variablo estas NULL, tio signifas ne estas ligitaj listo.

500
00:29:58,240 --> 00:30:02,460
Ni ne insertos ajna nombroj, do ĝi estas bagatela por enmeti ĉi aktuala nombro

501
00:30:02,460 --> 00:30:05,240
en la listo, ĉar ĝi simple apartenas al la komenco de la listo.

502
00:30:05,240 --> 00:30:08,100
Do ĉi estis kiam Anita ĵus piedo tie sola, ŝajnigante

503
00:30:08,100 --> 00:30:11,390
neniu alia estis ĉi tie sur la scenejo, ĝis ni destinis nodo,

504
00:30:11,390 --> 00:30:13,940
tiam sxi povis levi sian manon por la unua fojo,

505
00:30:13,940 --> 00:30:17,420
se ĉiuj aliaj venis sur la scenejo post ŝi lundon.

506
00:30:17,420 --> 00:30:22,900
Nun ĉi tie, ĉi tiu estas iom ĉeko kie mi devas diri se la nova nodo valoron de n

507
00:30:22,900 --> 00:30:27,370
estas <la valoro de n en la nuna unua nodo,

508
00:30:27,370 --> 00:30:29,930
kiu signifu estas ligillisto ke tio komenciĝis.

509
00:30:29,930 --> 00:30:32,330
Estas almenaŭ unu nodo en la listo, sed ĉi tiu nova tipo

510
00:30:32,330 --> 00:30:37,230
apartenas antaŭ ĝi, do necesas iri paŝon aferojn ĉirkaŭe.

511
00:30:37,230 --> 00:30:43,450
En aliaj vortoj, se la listo komencis kun nur, diru,

512
00:30:43,450 --> 00:30:48,100
nur la numero 17, tio estas la - reale, ni povas fari tion pli klare.

513
00:30:48,100 --> 00:30:56,010
Se ni komencos nian historion kun puntero tie nomita unue,

514
00:30:56,010 --> 00:30:59,870
kaj komence ĝi estas NULL, kaj ni enŝovu la numero 9,

515
00:30:59,870 --> 00:31:02,510
la numero 9 klare apartenas al la komenco de la listo.

516
00:31:02,510 --> 00:31:07,400
Do ni ŝajnigi ni simple malloced la adreso aŭ la nombro 9 kaj metis ĝin ĉi tie.

517
00:31:07,400 --> 00:31:13,170
Se unua estas 9 implicite, la unua scenaro ni diskutis nur signifas let la punkto this guy tie,

518
00:31:13,170 --> 00:31:15,790
forlasi tiun kiel NULL, nun ni havas la nombro 9.

519
00:31:15,790 --> 00:31:18,280
La sekvan numeron ni volas enmeti estas 17.

520
00:31:18,280 --> 00:31:22,420
17 apartenas ĉi tien, do ni tuj devas fari iu logika tretante tra ĉi.

521
00:31:22,420 --> 00:31:26,060
Do ni anstataŭ, antaŭ ol ni faras tion, ni ŝajnigi ke ni volis enmeti la numero 8.

522
00:31:26,060 --> 00:31:28,650
>> Do simple por oportuneco, kalkaj, mi tuj desegni tie.

523
00:31:28,650 --> 00:31:30,760
Sed memoru, malloc povas meti ĝin plej ie ajn.

524
00:31:30,760 --> 00:31:33,460
Sed por desegni la bono, Mi metos ĝin ĉi tie.

525
00:31:33,460 --> 00:31:38,440
Do ŝajnigi Mi ĵus atribuitaj al nodo por la nombro 8; ĉi estas NULL defaŭlte.

526
00:31:38,440 --> 00:31:42,800
Kio nun devas okazi? Paro de aferoj.

527
00:31:42,800 --> 00:31:47,090
Ni faris ĉi eraron en la scenejo lundon kie ni ĝisdatigis puntero kiel ĉi tiu,

528
00:31:47,090 --> 00:31:51,890
tiam faris tion, kaj tiam ni asertis - ni orfoj ĉiuj aliaj en la scenejo.

529
00:31:51,890 --> 00:31:54,350
Ĉar vi can't - la ordo de operacioj tie estas grava,

530
00:31:54,350 --> 00:31:58,760
ĉar nun ni perdis tiun nodon 9 tio estas nur ia flosante en la spaco.

531
00:31:58,760 --> 00:32:01,150
Do tio ne rajtas proksimigo lundon.

532
00:32:01,150 --> 00:32:03,330
Ni unue devas fari ion alian.

533
00:32:03,330 --> 00:32:06,280
La stato de la mondo similas ĉi. Komence, 8 estis asignitaj.

534
00:32:06,280 --> 00:32:10,550
Kio estus pli bona vojo de enmeto 8?

535
00:32:10,550 --> 00:32:14,720
Anstataŭ ĝisdatigi ĉi puntero unue, ĝuste ĝisdatigi ĉi tie anstataŭe.

536
00:32:14,720 --> 00:32:17,720
Do ni bezonas linion de kodo ke tuj turni ĉi NULL karaktero

537
00:32:17,720 --> 00:32:22,020
en reala puntero ke tio montrante nodo 9,

538
00:32:22,020 --> 00:32:27,970
kaj poste ni povas sekure ŝanĝi unua atentigi ĉe ĉi tiu viro tie.

539
00:32:27,970 --> 00:32:31,330
Nun ni havas liston, kunligita listo, de du elementoj.

540
00:32:31,330 --> 00:32:33,580
Kaj kion signifas tiu ĉi vere aspektas kiel ĉi tie?

541
00:32:33,580 --> 00:32:36,900
Se ni rigardas la kodon, rimarki ke mi faris ekzakte tion.

542
00:32:36,900 --> 00:32:41,970
Mi diris newptr, kaj en ĉi tiu rakonto, newptr notis al ĉi tiu viro.

543
00:32:41,970 --> 00:32:45,520
>> Do lasu min desegni pli bona, kaj mi forlasis iom pli ĉambron por ĉi tio.

544
00:32:45,520 --> 00:32:48,540
Do pardonu la etan iom desegno.

545
00:32:48,540 --> 00:32:52,140
Tiu ulo nomata newptr.

546
00:32:52,140 --> 00:32:57,940
Tio estas la variablo ni deklaris kelkajn liniojn pli frue, en linio - ĝuste super 25.

547
00:32:57,940 --> 00:33:03,430
Kaj ĝi estas indikante 8. Do kiam mi diras newptr-> sekva, kiu signifu iri al la struct

548
00:33:03,430 --> 00:33:07,910
ke tio esti notita al by newptr, do jen ni estas, iru tien.

549
00:33:07,910 --> 00:33:13,990
Tiam la sago diras akiri la proksimaj kampo, kaj tiam la = diras metis kio valoro tie?

550
00:33:13,990 --> 00:33:17,280
La valoro kiu estis en unua, kion valoro estis en la unua?

551
00:33:17,280 --> 00:33:21,930
Unue estis montrante tiun nodon, por ke signifas ĉi devus nun notas en tiu nodo.

552
00:33:21,930 --> 00:33:25,660
En aliaj vortoj, kio aspektas kvankam ridinda salaton kun mia manskribo,

553
00:33:25,660 --> 00:33:28,620
kio estas simpla ideo de nur kopii tiujn sagoj ĉirkaŭ

554
00:33:28,620 --> 00:33:31,560
tradukas kodo kun nur ĉi tiu Liner.

555
00:33:31,560 --> 00:33:38,110
Stoki kio estas en la unua en la sekvanta kampo kaj tiam ĝisdatigi kion unua reale estas.

556
00:33:38,110 --> 00:33:40,900
Ni iru antaŭen kaj rapida antaŭen tra kelkaj el ĉi tio,

557
00:33:40,900 --> 00:33:44,220
kaj rigardu nur en ĉi tiu vosto inserción por nun.

558
00:33:44,220 --> 00:33:51,210
Supozu mi alvenas al la punkto, kie mi trovos, ke la venonta kampo de iu nodo estas NULL.

559
00:33:51,210 --> 00:33:53,410
Kaj je tiu punkto en la historio, detalo kiun mi glosando super

560
00:33:53,410 --> 00:33:58,170
estas ke mi enkondukis alian puntero ĝis tie en linio 142, antaŭulo puntero.

561
00:33:58,170 --> 00:34:01,320
Esence, je ĉi tiu punkto en la historio, tuj la listo ricevas longa,

562
00:34:01,320 --> 00:34:04,800
Mi ia bezonas promeni ĝin per du fingroj ĉar se mi iras tro malproksime,

563
00:34:04,800 --> 00:34:08,219
memori en sola longa listo, vi ne povas iri malantaŭen.

564
00:34:08,219 --> 00:34:13,659
Do tiu ideo de predptr estas mia maldekstra fingro, kaj newptr - ne newptr.

565
00:34:13,659 --> 00:34:17,199
Alia puntero jen tie estas miaj aliaj fingroj, kaj mi estas nur speco de marŝante la listo.

566
00:34:17,199 --> 00:34:22,179
Tial ke ekzistas. Sed ni nur konsideras unu el la pli simplaj kazoj tie.

567
00:34:22,179 --> 00:34:26,620
Se tio puntero La sekva kampo estas NULL, kio estas la logika implikacio?

568
00:34:26,620 --> 00:34:30,840
Se vi trairas la listo kaj vi batis NULL puntero?

569
00:34:30,840 --> 00:34:35,780
Vi estas ĉe la fino de la listo, kaj tiel la kodo al la tiam aldonas ĉi tiu plia elemento

570
00:34:35,780 --> 00:34:41,230
estas varo de la intuicia prenos ke nodo kies sekva puntero estas NULL,

571
00:34:41,230 --> 00:34:46,120
tial ĉi estas nuntempe NULL, kaj ŝanĝi ĝin, tamen, esti la adreso de la nova vertico.

572
00:34:46,120 --> 00:34:52,260
Do ni simple desegni en kodo la sago, ke ni tiris la scenejo de levante ies maldekstra mano.

573
00:34:52,260 --> 00:34:54,070
>> Kaj la kazo ke mi skuos mian manon je nuntempe,

574
00:34:54,070 --> 00:34:58,020
nur ĉar mi kredas ke estas facile perdas kiam ni faras en ĉi tiu speco de medio,

575
00:34:58,020 --> 00:35:00,600
estas kontrolanta por inserción en la listo la mezo.

576
00:35:00,600 --> 00:35:03,220
Sed ĝuste intuicie, kion bezonas okazi, se vi volas eltrovi

577
00:35:03,220 --> 00:35:06,600
kie iu nombro apartenas en la mezo estas vi devas promeni ĝin

578
00:35:06,600 --> 00:35:09,510
kun pli ol unu fingro, pli ol unu pointer,

579
00:35:09,510 --> 00:35:12,920
decidi kie ĝi apartenas de kontrolanta estas la elemento <la aktuala,

580
00:35:12,920 --> 00:35:15,450
> La aktuala, kaj iam vi trovas tiun lokon,

581
00:35:15,450 --> 00:35:20,400
tiam vi devas fari ĉi speco de konko ludo kie vi movas la punteros ĉirkaŭ tre atente.

582
00:35:20,400 --> 00:35:23,850
Kaj tiun respondon, se vi ŝatus kialo tra tiu hejme sur via propra,

583
00:35:23,850 --> 00:35:28,340
abscesoj malsupren nur por tiuj du linioj de kodo, sed la ordo de tiuj linioj estas super grava.

584
00:35:28,340 --> 00:35:31,390
Ĉar se vi falas ies mano kaj levi iun alian estas en la malĝusta ordo,

585
00:35:31,390 --> 00:35:34,580
denove, vi povus fini orphaning la listo.

586
00:35:34,580 --> 00:35:39,500
Resumi pli koncepte, la inserción ĉe la vosto estas relative simpla.

587
00:35:39,500 --> 00:35:42,940
La inserción ĉe la kapo estas ankaŭ relative simpla,

588
00:35:42,940 --> 00:35:45,580
sed vi bezonas ĝisdatigi plia puntero ĉi tiu tempo

589
00:35:45,580 --> 00:35:47,930
al elpremi numero 5 en la listo ĉi tie,

590
00:35:47,930 --> 00:35:51,560
kaj tiam inserción meze engaĝas eĉ pli penado,

591
00:35:51,560 --> 00:35:56,130
al tre zorgeme enmeti la numeron 20 en ĝia ĝusta loko,

592
00:35:56,130 --> 00:35:58,350
kio estas inter 17 kaj 22.

593
00:35:58,350 --> 00:36:02,700
Do vi bezonas fari ion kiel havi la nova vertico 20 punkton al 22,

594
00:36:02,700 --> 00:36:08,470
kaj poste, kion nodo puntero bezonas esti ĝisdatigita lasta?

595
00:36:08,470 --> 00:36:10,630
Estas 17, por fakte enŝovu ĝin.

596
00:36:10,630 --> 00:36:14,080
Do denove, mi prokrastas la reala kodo por tiu aparta efektivigo.

597
00:36:14,080 --> 00:36:17,280
>> Je unua rigardo, estas iom blindigaj, sed estas vere nur senfina ciklo

598
00:36:17,280 --> 00:36:21,770
ke tio looping, looping, looping, looping, kaj rompante tiel frue kiel vi batis la NULL pointer,

599
00:36:21,770 --> 00:36:24,590
je kiu punkto oni povas fari la necesan inserción.

600
00:36:24,590 --> 00:36:30,960
Jen, do, estas reprezenta ligitaj listo inserción kodo.

601
00:36:30,960 --> 00:36:34,590
Tio estis ia multe, kaj sentas ni solvas unu problemon,

602
00:36:34,590 --> 00:36:36,940
sed ni enkondukis tuta alia. Sincere, ni pasigis tiun tutan tempon

603
00:36:36,940 --> 00:36:40,540
sur granda a kaj Ω kaj rula tempo, provante solvi problemojn pli rapide,

604
00:36:40,540 --> 00:36:43,270
kaj tie ni prenas grandan paŝon malantaŭen, ĝi sentas.

605
00:36:43,270 --> 00:36:45,380
Kaj tamen, se la celo estas gardi datumojn,

606
00:36:45,380 --> 00:36:48,010
sentas la Holy Grail, kiel ni diris lundon, estus vere esti

607
00:36:48,010 --> 00:36:50,470
stoki aferojn momento.

608
00:36:50,470 --> 00:36:53,930
>> Fakte, supozu ke ni faris al flanko ligitaj listo dum momento

609
00:36:53,930 --> 00:36:56,000
kaj ni anstataŭ enkondukis la nocion de tablo.

610
00:36:56,000 --> 00:36:59,110
Kaj ni nur opinias de tablo por momento tiel tablo.

611
00:36:59,110 --> 00:37:03,790
Tiu tabelo kaj tiu kazo tie havas iujn 26 elementoj, 0 tra 25,

612
00:37:03,790 --> 00:37:07,940
kaj supozu ke vi bezonas iun eron de stokado por nomoj:

613
00:37:07,940 --> 00:37:10,350
Alice kaj Bob kaj Charlie kaj similaj.

614
00:37:10,350 --> 00:37:12,880
Kaj vi bezonas iun datumstrukturo stoki tiuj nomoj.

615
00:37:12,880 --> 00:37:15,000
Nu, vi povus uzi ion kiel ligitaj listo

616
00:37:15,000 --> 00:37:20,260
kaj vi povis marŝi la listo enmeto Alico antaŭ Bob kaj Charlie post Bob ks.

617
00:37:20,260 --> 00:37:23,850
Kaj fakte, se vi volas vidi kodo tiel kiel flanken,

618
00:37:23,850 --> 00:37:27,230
scias ke en list2.h, ni faru ekzakte tion.

619
00:37:27,230 --> 00:37:30,610
Ni ne iros tra tiu kodo, sed ĉi tiu estas varianto de la unua ekzemplo

620
00:37:30,610 --> 00:37:34,640
kiu enkondukas unu alia struct ni vidis antaŭe nomita studento,

621
00:37:34,640 --> 00:37:40,330
kaj tiam kio fakte stokas en la ligillisto estas puntero al studento strukturo

622
00:37:40,330 --> 00:37:44,520
prefere ol simpla iom entjero, n.

623
00:37:44,520 --> 00:37:46,900
Do realigi ekzistas kodo tie kiu implikas reala kordoj,

624
00:37:46,900 --> 00:37:49,940
sed se la celo alproksimiĝis vere nun estas alparoli la efikeco problemo,

625
00:37:49,940 --> 00:37:53,380
ĉu ne estus bela se ni donita objekto nomita Alico,

626
00:37:53,380 --> 00:37:56,020
ni volas meti sxin en la dekstra situo en datumstrukturo,

627
00:37:56,020 --> 00:37:58,860
sentas ĝin estus vere agrable ĵus metis Alico,

628
00:37:58,860 --> 00:38:01,180
kies nomo komenciĝas per A, en la unua loko.

629
00:38:01,180 --> 00:38:05,270
Kaj Bob, kies nomo komenciĝas per B, en la dua loko.

630
00:38:05,270 --> 00:38:09,580
Kun tabelo, aŭ ni komencu nomante ĝin tablo, hash tablo en tiu,

631
00:38:09,580 --> 00:38:13,650
ni povas fari precize tion. Se ni estas donita nomo kiel Alice,

632
00:38:13,650 --> 00:38:16,700
ĉenon kiel Alice, kie vi metis A-l-i-c-e?

633
00:38:16,700 --> 00:38:20,540
Ni bezonas hueristic. Ni bezonas funkcion por preni iujn enigo kiel Alice

634
00:38:20,540 --> 00:38:24,610
kaj revenu respondon, "Metu Alico en ĉi loko."

635
00:38:24,610 --> 00:38:28,720
Kaj ĉi tiu funkcio, ĉi nigra skatolo, tuj estos nomata hash funkcio.

636
00:38:28,720 --> 00:38:32,330
>> Al krada funkcio estas iu kiu prenas enigo, kiel "Alico",

637
00:38:32,330 --> 00:38:38,080
kaj revenas al vi, tipe, la nombra situo en iu datumstrukturo kie Alico apartenas.

638
00:38:38,080 --> 00:38:40,830
En ĉi tiu kazo, nia hash funkcio devus esti relative simpla.

639
00:38:40,830 --> 00:38:47,510
Nia hash funkcio devus diri, se vi donas "Alico", kiu karaktero mi zorgas pri?

640
00:38:47,510 --> 00:38:55,660
La unua. Do mi rigardu [0], kaj tiam mi diros, se [0] karaktero estas A, kaj revenu al la nombro 0.

641
00:38:55,660 --> 00:39:01,130
Se estas B, revenu 1. Se ĝi estas C, revenu 2, kaj tiel plu.

642
00:39:01,130 --> 00:39:05,940
Ĉiuj 0 indekso, kaj kiu permesus min enmeti Alice kaj tiam Bob kaj tiam Charlie kaj tiel plu

643
00:39:05,940 --> 00:39:10,960
en ĉi tiun datumstrukturo. Sed estas problemo.

644
00:39:10,960 --> 00:39:13,060
Kio se Anita venas kune denove?

645
00:39:13,060 --> 00:39:17,510
Kie ni metas Anita? Ŝia nomo, tro, komenciĝas kun la litero A,

646
00:39:17,510 --> 00:39:20,330
kaj sentas ni faris ankoraŭ pli granda katastrofo de tiu problemo.

647
00:39:20,330 --> 00:39:24,380
Ni nun havas tujan inserción, konstanta tempo inserción, en datumstrukturo

648
00:39:24,380 --> 00:39:27,100
anstataŭ malbona-kazo lineara,

649
00:39:27,100 --> 00:39:29,510
sed kion ni faru kun Anita en ĉi tiu kazo?

650
00:39:29,510 --> 00:39:34,110
Kio estas la du ebloj, vere? Yeah?

651
00:39:34,110 --> 00:39:37,410
[Studenta respondo, nekomprenebla] Konsentite, do ni povus havi alian dimension.

652
00:39:37,410 --> 00:39:42,320
Tio estas bona. Do ni povas konstrui el meze en 3D kiel ni parolis pri parole lundon.

653
00:39:42,320 --> 00:39:46,700
Ni povus aldoni alian aliron tie, sed supozas ke ne, mi provas teni ĉi simpla.

654
00:39:46,700 --> 00:39:50,160
La tuta celo tie estas havi tujan konstanta tempo aliron,

655
00:39:50,160 --> 00:39:52,170
tiel ke tio aldonante tro multe komplekseco.

656
00:39:52,170 --> 00:39:55,970
Kio estas aliaj ebloj klopodinte enmeti Anita en tiun datumstrukturo? Yeah?

657
00:39:55,970 --> 00:39:58,610
[Studenta respondo, nekomprenebla] Bona. Do ni povus movi ĉiuj aliaj sube,

658
00:39:58,610 --> 00:40:03,040
kiel Charlie nudges malsupren Bob kaj Alice, kaj poste ni metos Anita kie ŝi vere volas esti.

659
00:40:03,040 --> 00:40:05,660
>> Kompreneble, nun, estas flanka efiko de tio.

660
00:40:05,660 --> 00:40:09,000
Ĉi datumstrukturo estas probable utila ne ĉar ni volas enmeti homoj unufoje

661
00:40:09,000 --> 00:40:11,250
sed ĉar ni volas kontroli se ili estas tie poste

662
00:40:11,250 --> 00:40:13,600
se ni deziras presi ĉiujn nomojn en la datumstrukturo.

663
00:40:13,600 --> 00:40:15,850
Ni tuj fari ion kun tiu datumo eventuale.

664
00:40:15,850 --> 00:40:20,810
Do nun ni ia ŝraŭbita super Alico, kiu ne plu kie ŝi supozis esti.

665
00:40:20,810 --> 00:40:23,880
Nek estas Bob, nek Charlie.

666
00:40:23,880 --> 00:40:26,060
Do eble ĉi tio ne estas tiom bona ideo.

667
00:40:26,060 --> 00:40:28,830
Sed ja, tio estas unu eblo. Ni povus ŝanĝi ĉiujn suben,

668
00:40:28,830 --> 00:40:32,240
aŭ heck, Anita venis malfrue al la ludo, kial ni ne nur metis Anita

669
00:40:32,240 --> 00:40:35,870
ne tie, ne ĉi tie, ne ĉi tie, ni nur metis sian iom pli malalta en la listo.

670
00:40:35,870 --> 00:40:38,680
Sed tiam tiu problemo komencas devolve denove.

671
00:40:38,680 --> 00:40:41,630
Vi eble povos trovi Alico tuj, bazita sur ŝia unua nomo.

672
00:40:41,630 --> 00:40:44,320
Kaj Bob tuj, kaj Charlie. Sed tiam vi serĉas Anita,

673
00:40:44,320 --> 00:40:46,360
kaj vi vidos, hmm, Alice estas en la vojo.

674
00:40:46,360 --> 00:40:48,770
Nu, mi kontrolu sub Alico. Bob ne estas Anita.

675
00:40:48,770 --> 00:40:51,850
Charlie ne Anita. Ho, tie estas Anita.

676
00:40:51,850 --> 00:40:54,720
Kaj se vi daŭrigas tiu trajno de logiko tuta vojo,

677
00:40:54,720 --> 00:41:00,690
kio estas la plej malbona-kazo rula tempo de trovo aŭ enmeto Anita en tiu nova datumstrukturo?

678
00:41:00,690 --> 00:41:03,280
Estas O (n), ĉu ne?

679
00:41:03,280 --> 00:41:06,280
Ĉar en la plej malbona kazo, estas Alico, Bob, Charlie. . .

680
00:41:06,280 --> 00:41:10,150
tuta vojo malsupren al iu nomita "Y", do ne estas nur unu loko restis.

681
00:41:10,150 --> 00:41:13,950
Feliĉe, ni ne havas unu nomita "Z", do ni metis Anita je la tre fundo.

682
00:41:13,950 --> 00:41:16,040
>> Ni ne vere solvis tiun problemon.

683
00:41:16,040 --> 00:41:19,890
Do eble ni bezonas enkonduki tiun trian dimension.

684
00:41:19,890 --> 00:41:22,230
Kaj ĝi rezultas, se ni enkonduki tiun trian dimension,

685
00:41:22,230 --> 00:41:25,240
ni ne povas fari ĉi perfekte, sed la Holy Grail tuj estos atingi

686
00:41:25,240 --> 00:41:28,370
konstanta tempo inserción kaj dinamika inserciones por ke

687
00:41:28,370 --> 00:41:30,960
ni ne devas forte-kodo tabelo de amplekso 26.

688
00:41:30,960 --> 00:41:34,400
Ni povas enmeti tiom da nomoj kiel ni volas, sed ni prenos nian 5-minuta paŭzo tie

689
00:41:34,400 --> 00:41:38,790
kaj poste fari tion ĝuste.

690
00:41:38,790 --> 00:41:46,020
Bone. Mi fiksis la rakonton ĉe bela artefarite tie

691
00:41:46,020 --> 00:41:48,670
elektante Alice kaj tiam Bob kaj tiam Charlie kaj tiam Anita,

692
00:41:48,670 --> 00:41:51,000
kies nomo estis evidente tuj kolizias kun Alice.

693
00:41:51,000 --> 00:41:54,120
Sed la demando ni finiĝis lundon kun estas ĝuste kiel probabla estas

694
00:41:54,120 --> 00:41:56,370
ke vi ricevas tiajn koliziojn? En aliaj vortoj,

695
00:41:56,370 --> 00:42:00,490
se ni ekuzas tiun tabular strukturo, kiu estas vere nur tabelo,

696
00:42:00,490 --> 00:42:02,460
en ĉi tiu kazo de 26 lokoj,

697
00:42:02,460 --> 00:42:05,740
kion se nia enigoj male estas unuforme distribuita?

698
00:42:05,740 --> 00:42:09,620
Ne artefarite Alice kaj Bob kaj Charlie kaj David kaj tiel plu alfabete,

699
00:42:09,620 --> 00:42:12,380
ĝi estas unuforme distribuita sur A tra Z.

700
00:42:12,380 --> 00:42:15,220
>> Eble ni simple akiri bonŝanca kaj ni ne tuj havas du A aŭ du B

701
00:42:15,220 --> 00:42:17,640
kun tre alta probablo, sed kiel iu atentigis,

702
00:42:17,640 --> 00:42:20,730
se ni ĝeneraligita tiun problemon kaj ne faru 0 al 25

703
00:42:20,730 --> 00:42:26,060
sed, diru, 0 tra 364 aŭ 65, ofte la nombro de tagoj en tipa jaro,

704
00:42:26,060 --> 00:42:31,170
kaj demandis la demando, "Kio estas la probablo ke du el ni en tiu ĉambro havas la saman naskiĝtagon?"

705
00:42:31,170 --> 00:42:34,600
Alivorte, kio estas la probablo ke du el ni havas nomon ekde la A?

706
00:42:34,600 --> 00:42:37,190
La speco de demando estas la sama, sed ĉi tiu adreso spaco,

707
00:42:37,190 --> 00:42:39,940
ĉi serĉo spaco, estas pli granda en la kazo de naskiĝtago,

708
00:42:39,940 --> 00:42:42,820
ĉar ni havas tiom da pli tagoj en la jaro ol literoj en la alfabeto.

709
00:42:42,820 --> 00:42:44,910
Kio estas la probablo de kolizio?

710
00:42:44,910 --> 00:42:48,410
Nu, ni povas pensi pri tio per elŝeligi la math la kontraŭa vojo.

711
00:42:48,410 --> 00:42:50,580
Kio estas la probablo de neniu kolizioj?

712
00:42:50,580 --> 00:42:53,970
Nu, ĉi tie esprimo diras ke kio estas la probablo

713
00:42:53,970 --> 00:42:58,770
se estas nur unu persono en ĉi tiu ĉambro, ke ili havas unikan naskiĝtago?

714
00:42:58,770 --> 00:43:01,190
Estas 100%. Ĉar se estas nur unu persono en la ĉambron,

715
00:43:01,190 --> 00:43:03,940
lia aŭ ŝia naskiĝtago povas esti iu ajn el la 365 tagoj el la jaro.

716
00:43:03,940 --> 00:43:08,650
Do 365/365 opcioj donas al mi valoron de 1.

717
00:43:08,650 --> 00:43:11,250
Do la probablo en demando nuntempe estas nur 1.

718
00:43:11,250 --> 00:43:13,270
Sed se estas dua persono en la ĉambron,

719
00:43:13,270 --> 00:43:16,490
kio estas la probablo ke ilia naskiĝtago estas malsamaj?

720
00:43:16,490 --> 00:43:20,680
Estas nur 364 eblaj tagoj, ignorante superjaroj,

721
00:43:20,680 --> 00:43:23,580
por ilia naskiĝtago ne kolizias kun la aliaj homoj.

722
00:43:23,580 --> 00:43:31,920
Do 364/365. Se tria persono venas en, estas 363/365, kaj tiel plu.

723
00:43:31,920 --> 00:43:35,790
Do ni observu multiplikante kune tiujn frakcioj, kiuj estas pli kaj pli malgrandiĝas,

724
00:43:35,790 --> 00:43:40,720
elŝeligi kio estas la probablo ke ni ĉiuj havas unika naskiĝtago?

725
00:43:40,720 --> 00:43:43,570
Sed tiam ni povas, kompreneble, nur prenu ke respondo kaj klaki ĝin ĉirkaŭ

726
00:43:43,570 --> 00:43:47,210
kaj faru 1 minus ĉiuj de tiu, esprimo ni eventuale akiri

727
00:43:47,210 --> 00:43:51,250
se vi memoras la dorso de via math libroj, ĝi aspektas iom io tiamaniere,

728
00:43:51,250 --> 00:43:54,590
kiu estas multe pli facile interpretita grafike.

729
00:43:54,590 --> 00:43:57,820
Kaj ĉi grafikaĵo tie havas sur la x akso la nombro de naskiĝtago,

730
00:43:57,820 --> 00:44:02,030
aŭ nombro de homoj kun naskiĝtago, kaj sur la y akso estas la probablo de turniro.

731
00:44:02,030 --> 00:44:06,060
Kaj kion tio diras, ke se vi havas, diru, inkluzive,

732
00:44:06,060 --> 00:44:10,860
ni elektos iun kiel 22, 23.

733
00:44:10,860 --> 00:44:13,160
Se estas 22 aŭ 23 personoj en la ĉambron,

734
00:44:13,160 --> 00:44:17,100
la probablo ke du el tiuj tre malmultaj personoj tuj havi la sama naskiĝtago

735
00:44:17,100 --> 00:44:19,560
estas fakte super alta, combinatorially.

736
00:44:19,560 --> 00:44:23,450
50% probabloj ke en klaso de nur 22 personoj, seminario, preskaŭ,

737
00:44:23,450 --> 00:44:25,790
2 el tiuj personoj tuj havi la sama naskiĝtago.

738
00:44:25,790 --> 00:44:28,520
Ĉar tie estas tiom da manieroj en kiu vi povas havi la saman naskiĝtagon.

739
00:44:28,520 --> 00:44:31,110
Eĉ pli malbone, se vi rigardas la dekstra flanko de la tabulo,

740
00:44:31,110 --> 00:44:34,040
por kiam vi havas klason kun 58 studentoj en ĝi,

741
00:44:34,040 --> 00:44:39,270
la probablo de 2 homoj havante naskiĝtago estas super, super alta, preskaŭ 100%.

742
00:44:39,270 --> 00:44:41,880
Nun, jen speco de amuza fakto pri la reala vivo.

743
00:44:41,880 --> 00:44:45,850
>> Sed la implikaĵoj, nun, por datumoj strukturoj kaj provizon informoj

744
00:44:45,850 --> 00:44:51,100
signifas ke nur supozante ke vi havas belan, puran, uniforma distribuo de datumoj

745
00:44:51,100 --> 00:44:53,650
kaj vi havas sufiĉe granda tabelo por ĝustigi faskon da aĵoj

746
00:44:53,650 --> 00:44:59,360
ne signifas ke vi ricevos popolo en unika lokoj.

747
00:44:59,360 --> 00:45:03,810
Vi tuj havos kolizioj. Do tiu nocio de Regionoj, kiel ĝi estas nomata,

748
00:45:03,810 --> 00:45:07,450
prenante enigo kiel "Alice" kaj massaging ĝin iel

749
00:45:07,450 --> 00:45:10,190
kaj tiam contrarestar respondon kiel 0 aŭ 1 aŭ 2.

750
00:45:10,190 --> 00:45:17,500
Contrarestar iuj eligo de tiu funkcio estas tuŝita de ĉi probablo de kolizio.

751
00:45:17,500 --> 00:45:19,530
Do kiel ni povas manipuli tiujn koliziojn?

752
00:45:19,530 --> 00:45:21,940
Nu, en unu kazo, ni povas preni la ideo kiu estis sugestita.

753
00:45:21,940 --> 00:45:25,100
Ni povas nur ŝanĝi ĉiuj sube, aŭ eble, iom pli simple,

754
00:45:25,100 --> 00:45:29,870
anstataŭ movi ĉiuj aliaj, ni simple movi Anita al la fundo de la disponebla loko.

755
00:45:29,870 --> 00:45:32,810
Do, se Alice estas en 0, Bob estas en 1, Charlie estas en 2,

756
00:45:32,810 --> 00:45:35,260
ni nur metis Anita je situo 3.

757
00:45:35,260 --> 00:45:38,860
Kaj jen estas tekniko en datumstrukturoj nomita lineara tuŝoprobado.

758
00:45:38,860 --> 00:45:41,310
Lineara ĉar vi ĵus promenis ĉi tiu linio, kaj vi estas ia tuŝoprobado

759
00:45:41,310 --> 00:45:43,640
por disponebla makuloj en la datumstrukturo.

760
00:45:43,640 --> 00:45:46,210
Kompreneble, ĉi devolves en O (n).

761
00:45:46,210 --> 00:45:49,590
Se la datumstrukturo vere plena, estas 25 personoj en ĝi jam,

762
00:45:49,590 --> 00:45:54,120
kaj tiam Anita venas kune, ŝi finiĝos ĉe kio estus loko Z, kaj tio estas fajna.

763
00:45:54,120 --> 00:45:56,540
Ŝi ankoraŭ havas, kaj ni povas trovi ŝin poste.

764
00:45:56,540 --> 00:46:00,100
>> Sed tio estis kontraŭe al la celo de akceli aĵojn.

765
00:46:00,100 --> 00:46:02,530
Do kio se ni anstataŭ enkondukis tiun trian dimension?

766
00:46:02,530 --> 00:46:06,400
Ke tekniko estas ĝenerale nomata apartaj ĉeni, aŭ havanta ĉenoj.

767
00:46:06,400 --> 00:46:10,030
Kaj kia hash tablo nun estas, ĉi tabular strukturo,

768
00:46:10,030 --> 00:46:13,450
via tablo estas nur tabelo de punteros.

769
00:46:13,450 --> 00:46:18,230
Sed kion tiuj punteros indikas estas guess kio?

770
00:46:18,230 --> 00:46:21,970
Al ligitaj listo. Do kio se ni prenas la plej bona el ambaŭ mondoj?

771
00:46:21,970 --> 00:46:26,500
Ni uzas tabeloj por la komenca indeksas

772
00:46:26,500 --> 00:46:32,070
en la datumstrukturo do ni povas tuj iri al [0] [1], [30] aŭ ks,

773
00:46:32,070 --> 00:46:36,480
sed por ke ni havas kelkajn fleksebleco kaj ni povas persvadi Anita kaj Alice kaj Adam

774
00:46:36,480 --> 00:46:38,630
kaj iu ajn alia A nomo,

775
00:46:38,630 --> 00:46:43,470
ni anstataŭ lasi la alia akso kreski arbitre.

776
00:46:43,470 --> 00:46:47,340
Kaj ni fine, ekde lundo, havi tiun esprima kapablo kun ligillisto.

777
00:46:47,340 --> 00:46:49,530
Ni povas kreski datumstrukturo arbitre.

778
00:46:49,530 --> 00:46:52,450
Alternative, ni povus simple grandega 2-dimensia tabelo,

779
00:46:52,450 --> 00:46:57,190
sed tio okazas al esti terura situacio se unu el la vicoj en 2-dimensia tabelo

780
00:46:57,190 --> 00:47:01,280
ne estas sufiĉe granda por la plia persono kies nomon okazas komenci kun A.

781
00:47:01,280 --> 00:47:04,200
Dio gardu ni devas reallocate grandega 2-dimensia strukturo

782
00:47:04,200 --> 00:47:06,600
nur ĉar tie estas tiom da homoj nomis A,

783
00:47:06,600 --> 00:47:09,480
speciale kiam ekzistas tiom malmultaj personoj nomata Z ion.

784
00:47:09,480 --> 00:47:12,170
Ĝi estas nur tuj estos tre maldensa datumstrukturo.

785
00:47:12,170 --> 00:47:15,400
Do ĝi ne estas perfekta por ajna duona, sed nun ni almenaŭ havas la kapablon

786
00:47:15,400 --> 00:47:19,090
al tuj trovi kie Alico aŭ Anita apartenas,

787
00:47:19,090 --> 00:47:21,090
almenaŭ en terminoj de la vertikala akso,

788
00:47:21,090 --> 00:47:25,850
kaj poste ni nur devas decidi kie meti Anita aŭ Alico en ĉi ligitaj listo.

789
00:47:25,850 --> 00:47:32,480
Se ni ne zorgas pri ordigi aferojn, kiel rapide ni povus enmeti Alico en strukturo kiel tiu?

790
00:47:32,480 --> 00:47:35,370
Estas konstanta tempo. Ni indekson en [0], kaj se neniu de tie,

791
00:47:35,370 --> 00:47:37,550
Alico iras al la komenco de tiu ligitaj listo.

792
00:47:37,550 --> 00:47:40,000
Sed tio ne estas grandega traktadon. Ĉar se Anita tiam venas kune

793
00:47:40,000 --> 00:47:42,160
iu nombro de paŝoj poste, kiel tio Anita apartenas?

794
00:47:42,160 --> 00:47:45,140
Nu, [0]. OOP. Alico jam en tiu ligitaj listo.

795
00:47:45,140 --> 00:47:47,760
>> Sed se ni ne zorgas pri ordigi tiujn nomojn,

796
00:47:47,760 --> 00:47:53,580
ni povas nur movi Alico plus insert Anita, sed eĉ tio estas konstanta tempo.

797
00:47:53,580 --> 00:47:57,010
Eĉ se estas Alice kaj Adam kaj ĉiuj tiuj aliaj A nomoj,

798
00:47:57,010 --> 00:47:59,410
ĝi ne vere sxangxigxantaj ilin fizike. Kial?

799
00:47:59,410 --> 00:48:04,090
Ĉar ni ĵus faris tie kun ligitaj listo, kiu scias ili tiuj nodoj estas ĉiuokaze?

800
00:48:04,090 --> 00:48:06,550
Vi nur devas fari estas movi la pano panpecetoj.

801
00:48:06,550 --> 00:48:10,930
Movu la sagojn ĉirkaŭ; vi ne devas fizike movas neniu datumo ĉirkaŭe.

802
00:48:10,930 --> 00:48:14,610
Do ni povas enigi Anita, en tiu kazo, la momento. Konstanta tempo.

803
00:48:14,610 --> 00:48:20,250
Do ni havas konstantan tempo lookup, kaj konstanta tempo inserción de iu kiel Anita.

804
00:48:20,250 --> 00:48:22,740
Sed ia oversimplifying la mondo.

805
00:48:22,740 --> 00:48:28,510
Kio se ni poste volas trovi Alice?

806
00:48:28,510 --> 00:48:31,050
Kio se ni poste volas trovi Alice?

807
00:48:31,050 --> 00:48:35,690
Kiom da paŝoj estas ke tuj prenos?

808
00:48:35,690 --> 00:48:37,850
[Studenta respondo, nekomprenebla]

809
00:48:37,850 --> 00:48:40,950
Ekzakte. La nombro de homoj antaux Alico en ligitaj listo.

810
00:48:40,950 --> 00:48:45,420
Do ĝi ne tute perfekta, ĉar nia datumstrukturo, denove, havas ĉi vertikala aliro

811
00:48:45,420 --> 00:48:50,240
kaj tiam ĝi havas tiuj ligitaj lertaj pendanta - efektive, ni ne desegni ĝin tabelo.

812
00:48:50,240 --> 00:48:56,020
Ĝi tiuj ligitaj lertaj pendantaj ekstere de ĝi ke aspektas iom io tiamaniere.

813
00:48:56,020 --> 00:48:59,110
Sed la problemo estas se Alice kaj Adam kaj ĉiuj tiuj aliaj A nomoj

814
00:48:59,110 --> 00:49:01,720
finos pli kaj pli tie,

815
00:49:01,720 --> 00:49:04,810
trovi iu povis fini prenante faskon da paŝoj,

816
00:49:04,810 --> 00:49:06,670
bcause vi devas trairi la ligillisto,

817
00:49:06,670 --> 00:49:08,090
kiu estas lineara operacio.

818
00:49:08,090 --> 00:49:14,270
Do vere, tiam, la inserción tempo finfine estas O (n), kie n estas la nombro de elementoj en la listo.

819
00:49:14,270 --> 00:49:21,780
Dividita de, ni arbitre nomas ĝin m, kie m estas la kvanto de kunligita lertaj

820
00:49:21,780 --> 00:49:24,500
ke ni havas en tiu vertikala akso.

821
00:49:24,500 --> 00:49:27,180
En aliaj vortoj, se ni vere supozas uniforma distribuo de nomoj,

822
00:49:27,180 --> 00:49:30,150
tute nerealisma. Estas evidente pli de kelkaj literoj ol aliaj.

823
00:49:30,150 --> 00:49:32,580
>> Sed se ni supozu por la momento uniforma distribuo,

824
00:49:32,580 --> 00:49:37,350
kaj ni n tuta popolo, kaj m tuta ĉenoj

825
00:49:37,350 --> 00:49:40,630
disponebla por ni, tiam la longo de ĉiu el ĉi tiuj katenoj

826
00:49:40,630 --> 00:49:44,380
sufiĉe simple tuj estos la tuta, n dividita per la nombro de ĉenoj.

827
00:49:44,380 --> 00:49:48,900
Do n / m. Sed ĉi tie estas kie ni povas esti ĉiuj matematike lerta.

828
00:49:48,900 --> 00:49:53,030
m estas konstanta, ĉar ne estas fiksa nombro de tiuj.

829
00:49:53,030 --> 00:49:54,620
Vi tuj deklari vian tabelo komence,

830
00:49:54,620 --> 00:49:58,450
kaj ni ne regrandigi la vertikala akso. Per difino, ke restas fiksaj.

831
00:49:58,450 --> 00:50:01,220
Estas nur la horizontala akso, por tiel diri, ke tio ŝanĝas.

832
00:50:01,220 --> 00:50:04,760
Do teknike, ĉi tiu estas konstanto. Do nun, la inserción tempo

833
00:50:04,760 --> 00:50:09,700
estas preskaux O (n).

834
00:50:09,700 --> 00:50:12,410
Por ke ne sentas cxiuj multe pli bone.

835
00:50:12,410 --> 00:50:14,940
Sed kio estas la vero tie? Nu, ĉiuj ĉi tiuj datoj, ĉar semajnoj,

836
00:50:14,940 --> 00:50:20,640
ni estis dirante O (n ²). O (n), 2 x n ², - n, dividita per 2. . . ech.

837
00:50:20,640 --> 00:50:23,580
Estas nur n ². Sed nun, en ĉi tiu parto de la semestro,

838
00:50:23,580 --> 00:50:25,560
ni povas komenci paroli pri la reala mondo denove.

839
00:50:25,560 --> 00:50:31,520
Kaj n / m estas absolute pli rapide ol n sola.

840
00:50:31,520 --> 00:50:35,170
Se vi havas mil nomojn, kaj vi rompi ilin en multnombraj siteloj

841
00:50:35,170 --> 00:50:37,820
por ke vi havas nur dek nomoj en ĉiu el tiuj ĉenoj,

842
00:50:37,820 --> 00:50:41,670
absolute serĉado dek aferojn tuj estos pli rapida ol mil aĵoj.

843
00:50:41,670 --> 00:50:43,740
Kaj tiel unu el la venontaj problemo aroj tuj defias vin

844
00:50:43,740 --> 00:50:46,100
pensi ĝuste ke kvankam, yeah,

845
00:50:46,100 --> 00:50:49,520
asimptote kaj matematike, ĉi tiu estas ankoraŭ nur lineara,

846
00:50:49,520 --> 00:50:51,700
kiu suĉas ĝenerale kiam provante trovi aĵojn.

847
00:50:51,700 --> 00:50:54,530
Fakte, ĝi tuj estos pli rapida ol tiu

848
00:50:54,530 --> 00:50:56,520
pro ĉi tio dividanto.

849
00:50:56,520 --> 00:50:58,310
Kaj do tie estas denove tuj estos ĉi komerco-off

850
00:50:58,310 --> 00:51:01,390
kaj tiu konflikto inter teorio kaj realo,

851
00:51:01,390 --> 00:51:03,550
kaj unu el la kapetoj komencos plenumi en ĉi tiu punkto en la semestro

852
00:51:03,550 --> 00:51:07,510
estas pli de la realo oni kiel ni ia prepari semster la fino,

853
00:51:07,510 --> 00:51:09,280
kiel ni enkonduki la mondo de ttt programado,

854
00:51:09,280 --> 00:51:11,530
kie vere, rendimento tuj rakontos ĉar via uzantoj tuj

855
00:51:11,530 --> 00:51:14,880
komenci senti kaj estimi malriĉa dezajno decidoj.

856
00:51:14,880 --> 00:51:19,950
>> Do kiel vi irados tra implementando kunligita - hash tablo kun 31 eroj?

857
00:51:19,950 --> 00:51:22,600
Kaj la antaŭa ekzemplo estis arbitre pri naskiĝtago.

858
00:51:22,600 --> 00:51:26,190
Se iu havas naskiĝtagon de januaro 1 aŭ februaro 1, ni metos ilin en la sitelo.

859
00:51:26,190 --> 00:51:28,960
Se temas pri januaro 2, februaro 2, marto 2, ni metos ilin en la sitelo.

860
00:51:28,960 --> 00:51:32,220
Tial ĝi estis 31. Kiel vi deklari hash tablo?

861
00:51:32,220 --> 00:51:37,480
Ĝi povas esti sufiĉe simplaj, nodo * tablo estas mia arbitraj nomo por tio, [31].

862
00:51:37,480 --> 00:51:42,400
Tio donas min 31 punteros al nodoj,

863
00:51:42,400 --> 00:51:45,370
kaj kiu min permesas havi 31 punteros al ligitaj listoj

864
00:51:45,370 --> 00:51:48,800
eĉ se tiuj ĉenoj estas komence NULL.

865
00:51:48,800 --> 00:51:54,860
Kion mi volas meti se mi volas konservi "Alice", "Bob", "Charlie"?

866
00:51:54,860 --> 00:51:57,010
Nu, ni bezonas kovri tiujn aferojn en strukturo

867
00:51:57,010 --> 00:52:00,530
ĉar ni bezonas Alico atentigi al Bob, atentigi al Charlie, ks.

868
00:52:00,530 --> 00:52:04,940
Ni ne povas nur havi la nomojn sola, do mi povis krei novan strukturon nomita nodo tie.

869
00:52:04,940 --> 00:52:08,310
>> Kio estas reala nodo? Kio estas nodo en ĉi tiu nova ligitaj listo?

870
00:52:08,310 --> 00:52:11,840
La unua afero, nomita vorto, estas por la persono nomo.

871
00:52:11,840 --> 00:52:14,340
Longo, supozeble, raportu al la maksimuma longo de homa nomo,

872
00:52:14,340 --> 00:52:18,210
kion ajn tio estas, 20, 30, 40 karakteroj en freneza angulo kazoj,

873
00:52:18,210 --> 00:52:22,680
kaj +1 estas por kio? Estas nur la ekstra NULL karaktero, \ 0.

874
00:52:22,680 --> 00:52:27,410
Do tiu nodo estas envolviendo "iu" ene de si mem,

875
00:52:27,410 --> 00:52:29,640
sed ankaŭ deklaras puntero nomis sekva

876
00:52:29,640 --> 00:52:32,580
por ke ni povu ĉeno Alico al Bob al Charlie ks.

877
00:52:32,580 --> 00:52:36,700
Povas esti NULL sed ne nepre devas esti.

878
00:52:36,700 --> 00:52:40,110
Demandojn pri tiuj hash tabloj? Yeah?

879
00:52:40,110 --> 00:52:46,190
[Studenta petante demando, nekomprenebla] An tabelo - bona demando.

880
00:52:46,190 --> 00:52:50,120
Kial estas ĉi char vorto en tabelo anstataŭ nur char *?

881
00:52:50,120 --> 00:52:53,830
En ĉi tiu iom arbitra ekzemplo, mi ne volas havi recurrir

882
00:52:53,830 --> 00:52:56,190
al malloc por ĉiu el la originalaj nomoj.

883
00:52:56,190 --> 00:52:59,530
Mi volis deklari maksimuman kvanton de memoro por la kordo

884
00:52:59,530 --> 00:53:06,020
por ke mi povus kopii en la strukturo Alico \ 0 kaj ne devas trakti malloc kaj libera kaj similaj.

885
00:53:06,020 --> 00:53:11,710
Sed mi povus fari tion, se mi volis esti pli konsciaj de spaco uzo. Bona demando.

886
00:53:11,710 --> 00:53:14,780
Do ni provu ĝeneraligi for de ĉi

887
00:53:14,780 --> 00:53:18,350
kaj enfokusigi la resto de hodiaŭ sur datumstrukturoj pli ĝenerale

888
00:53:18,350 --> 00:53:21,170
kaj aliaj problemoj kiujn ni povas solvi per la sama fundamentojn

889
00:53:21,170 --> 00:53:24,590
kvankam la datumstrukturoj sin povus diferenci en siaj detaloj.

890
00:53:24,590 --> 00:53:27,910
>> Do rezultas en komputiko, arboj estas tre ofta.

891
00:53:27,910 --> 00:53:29,760
Kaj vi povas pensi pri arbo ia kiel familio arbo,

892
00:53:29,760 --> 00:53:31,830
kie estas kelkaj radikoj, iuj matriarca aŭ patriarko,

893
00:53:31,830 --> 00:53:34,540
avino aŭ avo aŭ antaŭe reen,

894
00:53:34,540 --> 00:53:38,880
sub kiuj estas panjo kaj paĉjo aŭ pluraj gefratoj aŭ similaj.

895
00:53:38,880 --> 00:53:42,500
Do arbo strukturo havas nodoj kaj ĝi havas infanojn,

896
00:53:42,500 --> 00:53:45,260
kutime 0 aŭ pli infanoj por ĉiu nodo.

897
00:53:45,260 --> 00:53:47,320
Kaj iuj el la ĵargono, kiun vi vidas en tiu bildo ĉi tie

898
00:53:47,320 --> 00:53:50,630
estas ajna el la malgrandaj infanoj aŭ grandkids sur la randoj

899
00:53:50,630 --> 00:53:52,330
kiu ne havas sagojn emanas de ili,

900
00:53:52,330 --> 00:53:55,070
tiuj estas la tiel nomata folioj, kaj al neniu en la interno

901
00:53:55,070 --> 00:53:58,790
estas ena nodo; vi povas nomi ĝin io kune tiujn liniojn.

902
00:53:58,790 --> 00:54:01,430
Sed tiu strukturo estas sufiĉe komuna. Ĉi tiu estas iom arbitra.

903
00:54:01,430 --> 00:54:04,930
Ni havas unu infano maldekstre, ni havas tri infanojn sur la dekstra,

904
00:54:04,930 --> 00:54:06,830
du infanoj sur la fundo lasis.

905
00:54:06,830 --> 00:54:10,740
Do ni povas havi malsamajn grandeco arboj, sed se ni komencos normigi tion,

906
00:54:10,740 --> 00:54:15,330
kaj vi eble memoras tiun de Patricio video sur duuma serĉo de antaŭa mallonga

907
00:54:15,330 --> 00:54:19,490
linio, duuma serĉo ne devas esti realigita kun tabelo

908
00:54:19,490 --> 00:54:21,410
aŭ pecoj de papero sur tabulon.

909
00:54:21,410 --> 00:54:25,490
Supozu ke vi volis konservi viajn nombroj en pli kompleksaj datumstrukturo.

910
00:54:25,490 --> 00:54:27,680
Vi povus krei arbon kiel ĉi tio.

911
00:54:27,680 --> 00:54:35,290
Vi povus havi nodo deklaris en C, kaj tiu nodo povas havi almenaŭ du elementoj ene de ĝi.

912
00:54:35,290 --> 00:54:39,470
Unu estas la nombro vi volas konservi, kaj la alia estas - nu, ni bezonas unu pli.

913
00:54:39,470 --> 00:54:41,540
La alia estas liaj filoj.

914
00:54:41,540 --> 00:54:45,150
Do jen alia datumstrukturo. Ĉi-foje, nodo estas difinita kiel provizon nombro n

915
00:54:45,150 --> 00:54:49,060
kaj tiam du punteros; maldekstra infano kaj dekstra infano.

916
00:54:49,060 --> 00:54:52,100
Kaj ili estas ne arbitra. Kio estas interesa pri tiu arbo?

917
00:54:52,100 --> 00:55:00,550
>> Kio estas la ŝablono en kiel ni kuŝigis tiun ekster aŭ kiel Patrick metis ĝin en lia video?

918
00:55:00,550 --> 00:55:02,790
Estas speco de preterlasas ke ekzistas iu ordigo okazas ĉi tie,

919
00:55:02,790 --> 00:55:04,460
sed kio estas la simpla regulo? Yeah?

920
00:55:04,460 --> 00:55:08,350
[Studenta respondo, nekomprenebla]

921
00:55:08,350 --> 00:55:12,040
Perfekta. Se vi rigardis en tiu, vi vidos la malgrandaj nombroj maldekstre,

922
00:55:12,040 --> 00:55:14,690
grandaj nombroj maldekstre, sed tio estas vera por ĉiu nodo.

923
00:55:14,690 --> 00:55:20,370
Por ĉiu nodo, lia maldekstra infano malpli ol tio, kaj lia dekstra infano pli granda ol ĝi.

924
00:55:20,370 --> 00:55:25,210
Kion ĉi tio signifas nun estas se mi volas serĉi ĉi datumstrukturo por, ni diru, la numero 44,

925
00:55:25,210 --> 00:55:29,320
Mi devas komenci ĉe la radiko, ĉar kiel kun ĉiu el tiuj pli kompleksaj datumstrukturoj nun,

926
00:55:29,320 --> 00:55:31,910
ni nur havas puntero al unu afero, la komenco.

927
00:55:31,910 --> 00:55:35,010
Kaj en ĉi tiu kazo, la komenco estas la radiko. Ĝi ne estas la ekstrema maldekstra,

928
00:55:35,010 --> 00:55:39,530
ĝi estas la radiko de tiu strukturo. Do mi vidas jen 55, kaj Mi serĉas 44.

929
00:55:39,530 --> 00:55:41,430
Kiu direkto mi volas iri?

930
00:55:41,430 --> 00:55:45,680
Nu, mi volas iri al la maldekstra, ĉar evidente, dekstre tuj estos tro granda.

931
00:55:45,680 --> 00:55:49,050
Do rimarki tie, vi estas ia koncepte batante la arbo en duono

932
00:55:49,050 --> 00:55:51,700
ĉar vi neniam iras malsupren al la dekstra flanko.

933
00:55:51,700 --> 00:55:55,410
Do nun mi iras de la 55 al la 33. Ĝi estas tro malgranda de nombro.

934
00:55:55,410 --> 00:56:01,590
Mi serĉas 44, sed nun mi scias se 44 estas en ĉi tiu arbo, mi povas iri evidente al dekstre.

935
00:56:01,590 --> 00:56:04,460
Do denove, mi rikoltiloj la arbo en duono.

936
00:56:04,460 --> 00:56:06,780
Estas preskaux identaj koncepte al la telefono libro.

937
00:56:06,780 --> 00:56:09,510
Estas identa al kion ni faris kun la paperoj sur la tabulon,

938
00:56:09,510 --> 00:56:13,940
sed ĝi estas pli kompleksa strukturo kiu permesas al ni efektive fari

939
00:56:13,940 --> 00:56:16,880
ĉi dividi kaj venki per dezajno de la algoritmo,

940
00:56:16,880 --> 00:56:19,420
kaj fakte, lauxiris strukturon kiel tiu - whoops.

941
00:56:19,420 --> 00:56:22,870
Lauxiris strukturon kiel tiu, kie ĝi estas nur "iri tiun vojon aŭ iri tiun vojon,"

942
00:56:22,870 --> 00:56:26,870
signifas ĉiuj kiuj kodo kiu fleksiĝis via menso unue kiam apliki ĝin en sekcio

943
00:56:26,870 --> 00:56:31,270
aŭ marŝante tra ĝi hejme, por duuma serĉo, uzante rekursio aŭ ripeta,

944
00:56:31,270 --> 00:56:35,060
ĝi estas doloro en la kolo. Trovu la mezo elemento, tiam faru viajn rondigas supren aŭ malsupren.

945
00:56:35,060 --> 00:56:39,230
>> Jen beleco al ĉi ĉar ni povas nun uzi rekursio denove,

946
00:56:39,230 --> 00:56:43,760
sed multe pli pure. Ja, se vi estas en la nombro 55 kaj vi volas trovi 44,

947
00:56:43,760 --> 00:56:48,450
vi iros restis en cxi tiu kazo, tiam kion vi faras? Vi kuras la ĝusta sama algoritmo.

948
00:56:48,450 --> 00:56:51,560
Vi kontrolu la valoron de la nodo, tiam vi iru maldekstren aŭ dekstren.

949
00:56:51,560 --> 00:56:53,670
Tiam vi kontrolu la valoron de la nodo, iru maldekstren aŭ dekstren.

950
00:56:53,670 --> 00:56:56,710
Ĉi tiu estas perfekte taŭgaj por rekursio.

951
00:56:56,710 --> 00:57:00,920
Do eĉ se en la pasinteco ni faris kelkajn sufiĉe arbitraj ekzemploj engaĝante rekursio

952
00:57:00,920 --> 00:57:03,430
kiu ne bezonas esti rekursie, kun datumoj stuctures,

953
00:57:03,430 --> 00:57:07,820
speciale arboj, ĝi estas perfekta apliko de tiu ideo de prenante problemo,

954
00:57:07,820 --> 00:57:12,920
ŝrumpanta ĝin, kaj tiam solvi la sama tipo de, sed pli malgranda, programo.

955
00:57:12,920 --> 00:57:14,590
>> Do tie estas alia datumstrukturo ke ni povas prezenti.

956
00:57:14,590 --> 00:57:18,760
Ĉi tiu estas desegnita unuavide por serĉi críptico, sed ĉi tiu estas mirinda.

957
00:57:18,760 --> 00:57:25,090
Do ĉi tiu estas datumstrukturo nomata trie, trie, kiu heredis de la vorto reakiro,

958
00:57:25,090 --> 00:57:30,210
kiu ne estas prononcata re-try-val, sed tio estas kion la mondo nomas tion. Pretendas. T-r-i-kaj.

959
00:57:30,210 --> 00:57:35,190
Ĝi estas arbo strukturo de iu tipo, sed ĉiu el la nodoj en trie

960
00:57:35,190 --> 00:57:41,280
ŝajnas esti kio? Kaj jen estas iom iluzia ĉar ĝi estas speco de mallongigita.

961
00:57:41,280 --> 00:57:45,960
Sed ĝi aspektas kiel ĉiu nodo en ĉi trie estas fakte tabelo.

962
00:57:45,960 --> 00:57:48,840
Kaj kvankam la aŭtoro de ĉi tiu figuro ne montris ĝin,

963
00:57:48,840 --> 00:57:54,130
en ĉi tiu kazo, ĉi trie estas datumstrukturo kies celo en la vivo estas por stoki vortoj

964
00:57:54,130 --> 00:57:57,330
kiel Al-l-i-c-e aŭ B-o-b.

965
00:57:57,330 --> 00:58:02,480
Kaj la maniero en kiu ĉi tiuj datumoj tendencas Alice kaj Bob kaj Charlie kaj Anita kaj tiel plu

966
00:58:02,480 --> 00:58:06,970
Estas ĝi uzas aron per kiu stoki Alico en trie,

967
00:58:06,970 --> 00:58:09,820
ni starti je la radika vertico kiu aspektas kiel tabelo,

968
00:58:09,820 --> 00:58:12,080
kaj ĝi estas skribite en stenografio skribmaniero.

969
00:58:12,080 --> 00:58:15,070
La aŭtoro preterlasis abcdefg ĉar ne estis nomoj kun tiu.

970
00:58:15,070 --> 00:58:19,150
Ili nur montris M kaj P kaj T, sed en ĉi tiu kazo,

971
00:58:19,150 --> 00:58:22,780
ni movi sin de Alice kaj Bob kaj Charlie por iuj nomoj, kiuj estas ĉi tie.

972
00:58:22,780 --> 00:58:25,670
Maxwell estas vere en ĉi tiu figuro.

973
00:58:25,670 --> 00:58:29,570
Do kiel faris la aŭtoro vendejo M-a-x-w-e-l-l?

974
00:58:29,570 --> 00:58:36,990
Li aŭ ŝi komencis je la radika vertico, kaj iris al [M], do proksimume 13, la 13-a loko en la tabelo.

975
00:58:36,990 --> 00:58:40,750
Tiam el tie, ne estas puntero.

976
00:58:40,750 --> 00:58:42,760
Al puntero kondukante al alia tabelo.

977
00:58:42,760 --> 00:58:47,880
De tie la aŭtoro indeksita en tiun tabelo en loko A, kiel priskribita tie ĉe supre maldekstre,

978
00:58:47,880 --> 00:58:52,250
kaj tiam li aŭ ŝi sekvis tiun puntero al alia tabelo,

979
00:58:52,250 --> 00:58:55,460
kaj iris al la puntero je situo X.

980
00:58:55,460 --> 00:58:59,840
Tiam en la sekvanta tabelo situo W, E, L, L, kaj tiel plu,

981
00:58:59,840 --> 00:59:03,090
kaj fine, ni vere provas meti bildon al ĉi tio.

982
00:59:03,090 --> 00:59:05,380
Kion faras nodon aspekti en kodo?

983
00:59:05,380 --> 00:59:11,820
Nodo en trie enhavas aron de punteros al pli nodoj.

984
00:59:11,820 --> 00:59:16,090
Sed estas ankaŭ alvenis al esti ia bulea valoro, almenaŭ en ĉi efektivigo.

985
00:59:16,090 --> 00:59:18,770
Mi hazarde nomas ĝin is_word. Kial?

986
00:59:18,770 --> 00:59:22,670
Ĉar kiam vi enmeto Maxwell, vi ne enmeto

987
00:59:22,670 --> 00:59:25,300
ion en tiun datumstrukturo.

988
00:59:25,300 --> 00:59:27,480
Vi ne skribas ro Vi ne skribas X.

989
00:59:27,480 --> 00:59:30,240
Ĉiuj vi faras estas post punteros.

990
00:59:30,240 --> 00:59:33,360
La puntero kiu reprezentas M, tiam la puntero kiu reprezentas A,

991
00:59:33,360 --> 00:59:36,310
tiam la puntero kiu reprezentas X, tiam W, E, L, L,

992
00:59:36,310 --> 00:59:41,950
sed kion vi bezonas fari fine estas ia iru, kontrolu, mi atingis ĉi loko.

993
00:59:41,950 --> 00:59:45,560
Okazis vorto kiu finiĝas ĉi tie en la datumstrukturo.

994
00:59:45,560 --> 00:59:48,190
>> Do kia trie estas vere plena kaj la aŭtoro elektis por reprezenti

995
00:59:48,190 --> 00:59:51,880
tiuj terminuses kun malmulta trianguloj.

996
00:59:51,880 --> 00:59:56,470
Tiu simple volas diri ke la fakto ĉi tiu triangulo estas ĉi tie, ĉi bulea valoro de vera

997
00:59:56,470 --> 00:59:59,200
signifas se vi iras malantaŭen en la arbo,

998
00:59:59,200 --> 01:00:02,420
kiu signifu la vorto nomata Maxwell estas en ĉi.

999
01:00:02,420 --> 01:00:04,870
Sed la vorto foo, ekzemple,

1000
01:00:04,870 --> 01:00:07,970
ne estas en la arbo, ĉar se mi komencas je la radika vertico ĝis tie en supro,

1001
01:00:07,970 --> 01:00:14,030
Ne f pointer, ne o pointer, ne o puntero. Foo ne estas nomo de ĉi tiu vortaro.

1002
01:00:14,030 --> 01:00:22,460
Sed kontraste, Turing, t-u-r-i-n-g. Denove, mi ne stoki t aŭ u aŭ r aŭ mi aŭ n aŭ g.

1003
01:00:22,460 --> 01:00:29,820
Sed mi faris vendejo en ĉi datumstrukturo valoron de vera vojo cxi tie en ĉi tiu nodo - en la arbo

1004
01:00:29,820 --> 01:00:33,030
per opcio ĉi bulea valoro de is_word al vera.

1005
01:00:33,030 --> 01:00:35,740
Tial trie estas speco de ĉi tre interesa meta strukturo,

1006
01:00:35,740 --> 01:00:39,810
kie vi ne vere stoki la vortoj mem por tiu speco de vortaro.

1007
01:00:39,810 --> 01:00:45,100
Por esti klaraj, vi simple stoki jes aŭ ne, estas vorto, kiu finiĝas tie.

1008
01:00:45,100 --> 01:00:46,430
>> Nun kio estas la implikaĵon?

1009
01:00:46,430 --> 01:00:51,120
Se vi havas 150.000 vortojn en vortaro ke vi provas konservi en memoro

1010
01:00:51,120 --> 01:00:53,400
uzante iu kiel ligitaj listo,

1011
01:00:53,400 --> 01:00:56,870
vi tuj havos 150.000 nodoj en via ligitaj listo.

1012
01:00:56,870 --> 01:01:00,250
Kaj trovinte unu el tiuj vortoj alfabete povus preni O (n) tempo.

1013
01:01:00,250 --> 01:01:04,370
Lineara tempo. Sed en la kazo tie de trie,

1014
01:01:04,370 --> 01:01:09,210
kio estas la rula tempo de trovanta vorto?

1015
01:01:09,210 --> 01:01:17,390
Rezultas la beleco ĉi tie estas, ke eĉ se vi havas 149,999 vortoj jam en ĉi tiu vortaro,

1016
01:01:17,390 --> 01:01:20,170
kiel implementado kun ĉi datumstrukturo,

1017
01:01:20,170 --> 01:01:25,560
kiom da tempo estas bezonata por trovi aŭ enmeti pli persono en tiun, kiel Alice, Alice?

1018
01:01:25,560 --> 01:01:30,640
Nu, estas nur 5, eble 6 paŝoj por la fina signo.

1019
01:01:30,640 --> 01:01:32,880
Ĉar la ĉeesto de aliaj nomoj en la strukturo

1020
01:01:32,880 --> 01:01:35,340
ne ricevas laux la vojo de enmeto Alico.

1021
01:01:35,340 --> 01:01:39,640
Cetere, trovante Alico iam estas 150.000 vortoj en tiu ĉi vortaro

1022
01:01:39,640 --> 01:01:41,960
ne ricevas en via maniero de trovado Alico tute ne,

1023
01:01:41,960 --> 01:01:46,880
ĉar Alico estas. . . . . ĉi tie, ĉar mi trovis bulea valoro.

1024
01:01:46,880 --> 01:01:50,920
Kaj se ne estas bulea vera, tiam Alico ne estas en tiu datumstrukturo de vortoj.

1025
01:01:50,920 --> 01:01:56,220
En aliaj vortoj, la rula tempo de trovanta aĵoj kaj enmeto aĵoj en tiu nova

1026
01:01:56,220 --> 01:02:01,920
datumstrukturo de trie estas O de - ĝi estas ne n.

1027
01:02:01,920 --> 01:02:05,730
Ĉar la ĉeesto de 150.000 personoj havas nenian efikon sur Alice, ŝajne.

1028
01:02:05,730 --> 01:02:11,560
Do ni nomas ĝin k, kie k estas la maksimuma longeco de vorto en la angla

1029
01:02:11,560 --> 01:02:14,050
kiu estas tipe ne pli ol 20-iu gravuloj.

1030
01:02:14,050 --> 01:02:17,940
Do k estas konstanto. Do la Holy Grail ni ŝajnas esti trovita nun

1031
01:02:17,940 --> 01:02:26,000
estas tiu de trie, konstanta tempo por enmetas, por serĉoj, por forigoj.

1032
01:02:26,000 --> 01:02:29,170
Ĉar la nombro de aĵoj jam en la strukturo,

1033
01:02:29,170 --> 01:02:32,600
kiu eĉ fizike tie. Denove, ili estas nur ordigi de kontrolis for, jes aŭ ne,

1034
01:02:32,600 --> 01:02:35,050
havas nenian efikon sur lia estonteco rula tempo.

1035
01:02:35,050 --> 01:02:37,940
>> Sed estas alvenis al esti catch, alie ni ne estus malŝparis tiom da tempo

1036
01:02:37,940 --> 01:02:41,460
en ĉiuj tiuj aliaj datumstrukturoj nur por fine atingi la sekreta kiu estas miriga.

1037
01:02:41,460 --> 01:02:46,410
Do kio prezo ni pagas por atingi tiun grandecon ĉi tie? Spaco.

1038
01:02:46,410 --> 01:02:49,010
Tiu afero estas amasa. Kaj la kialo, ke la aŭtoro

1039
01:02:49,010 --> 01:02:52,400
ne prezenti ĝin ĉi tie, rimarki ke ĉiuj tiuj aĵoj kiuj similas arrays,

1040
01:02:52,400 --> 01:02:55,400
li ne eltiris la resto de la arbo, la resto de la trie,

1041
01:02:55,400 --> 01:02:58,060
ĉar ili estas simple ne konvenas al la rakonto.

1042
01:02:58,060 --> 01:03:01,870
Sed ĉiuj tiuj nodoj estas super larĝa, kaj ĉiu nodo en la arbo reprenas

1043
01:03:01,870 --> 01:03:07,780
26 aŭ reale, povus esti 27 signojn ĉar en tiu kazo mi estis inter ili spacon por la apostrofo

1044
01:03:07,780 --> 01:03:09,980
por ke ni povus havi apostrophized vortoj.

1045
01:03:09,980 --> 01:03:14,450
En ĉi tiu kazo, tiuj estas larĝaj tabeloj. Do eĉ se ili ne picutured,

1046
01:03:14,450 --> 01:03:18,190
ĉi okupas amasan kvanton de RAM.

1047
01:03:18,190 --> 01:03:20,670
Kiu povus esti bone, especilly en moderna aparataro,

1048
01:03:20,670 --> 01:03:25,650
sed jen la tradeoff. Ni preni malpli da tempo por pasi pli da spaco.

1049
01:03:25,650 --> 01:03:28,580
Do kie estas tiu tuta iras?

1050
01:03:28,580 --> 01:03:32,640
Nu, ni faru - ni vidu ĉi tie.

1051
01:03:32,640 --> 01:03:39,510
Ni faru salton al ĉi ulo tie.

1052
01:03:39,510 --> 01:03:43,450
>> Kredu ĝin aŭ ne, tiel amuza kiel C estis dum iom da tempo nun,

1053
01:03:43,450 --> 01:03:48,130
ni atingi la punkton en la semestro kie estas momento de transiro al aĵoj pli moderna.

1054
01:03:48,130 --> 01:03:50,950
Aĵoj sur pli alta nivelo. Kaj kvankam dum la sekvaj du semajnoj

1055
01:03:50,950 --> 01:03:54,580
ni ankoraŭ daŭre mergi nin en la mondo de punteros kaj memoro mastrumado

1056
01:03:54,580 --> 01:03:57,210
atingi, ke konsolo, per kiu ni povas tiam konstrui,

1057
01:03:57,210 --> 01:04:01,270
la fino ludo estas finfine enkonduki, ironie, ne ĉi lingvo.

1058
01:04:01,270 --> 01:04:03,330
Ni pasigas, kiel 10 minutoj parolas HTML.

1059
01:04:03,330 --> 01:04:05,950
Ĉiuj HTML estas estas markado lingvon, kaj kia markado lingvo estas

1060
01:04:05,950 --> 01:04:10,220
Estas tiuj serioj de malferma krampoj kaj fermitaj krampoj kiuj diras 'fari ĉi bold'

1061
01:04:10,220 --> 01:04:12,000
'Fari ĉi kursivo' 'fari ĉi centrita.

1062
01:04:12,000 --> 01:04:14,250
Ne ĉiuj kiuj intelekte interesa, sed ĝi estas super utila.

1063
01:04:14,250 --> 01:04:16,650
Kaj estas certe omnipresente tiuj tagoj.

1064
01:04:16,650 --> 01:04:19,450
Sed kio estas potenca sur la mondo de HTML, kaj retejo programado pli ĝenerale,

1065
01:04:19,450 --> 01:04:25,910
konstruas dinamika aĵoj; skribi kodon en lingvoj kiel PHP aŭ Python aŭ Ruby aŭ Java aŭ C #.

1066
01:04:25,910 --> 01:04:30,360
Vere, kion ajn via lingvo de elekto estas, kaj generante HTML dinamike.

1067
01:04:30,360 --> 01:04:32,960
Generante iu nomita CSS dinamike.

1068
01:04:32,960 --> 01:04:35,810
Akvofalo stilo littukoj, kiu estas ankaŭ pri estetiko.

1069
01:04:35,810 --> 01:04:41,360
Kaj tial, kvankam, hodiaŭ, se mi iras al iu retejo kiel la familiara Google.com,

1070
01:04:41,360 --> 01:04:46,100
kaj mi iras por rigardi, programisto, redakti, kiun eble vi faris antaŭe,

1071
01:04:46,100 --> 01:04:49,800
sed tuj vidi fonton, ĉi stuff probable aspektas bela kamufla.

1072
01:04:49,800 --> 01:04:55,320
Sed ĉi tiu estas la suba kodo kiu implementa Google.com.

1073
01:04:55,320 --> 01:04:57,940
Sur la antauxa fino. Kaj efektive ĉio ĉi estas lanugaj estetiko stuff.

1074
01:04:57,940 --> 01:05:01,740
Jen CSS tien. Se mi gardas movo malsupren ni ricevos iun koloron-kodita stuff.

1075
01:05:01,740 --> 01:05:06,890
Ĉi tiu estas HTML. Google kodo aspektas kiel salato, sed se mi vere malfermi alian fenestron,

1076
01:05:06,890 --> 01:05:09,380
ni povas vidi kelkajn strukturo al ĉi tio.

1077
01:05:09,380 --> 01:05:12,640
Se mi malfermos ĉi supre, rimarki tie, estas iom pli legebla.

1078
01:05:12,640 --> 01:05:16,850
Ni tuj vidos nelonge ĉi etikedo, [vorto] estas etikedo,

1079
01:05:16,850 --> 01:05:23,520
HTML, kapo, korpo, div, skripto, tekstujo, naski, centrita, div.

1080
01:05:23,520 --> 01:05:26,770
Kaj jen estas ankaŭ ordigi de kripta-aspekta al unua vido,

1081
01:05:26,770 --> 01:05:30,890
sed ĉio ĉi salaton sekvas iuj ŝablonoj, kaj repetible ŝablonoj,

1082
01:05:30,890 --> 01:05:33,850
por ke iam ni atingos la fundamentojn sube, vi povos skribi kodo kiel tiu

1083
01:05:33,850 --> 01:05:37,550
kaj tiam manipuli kodo kiel ĉi uzante alian lingvon, nomata JavaScript.

1084
01:05:37,550 --> 01:05:40,440
Kaj JavaScript estas lingvo kiu funkcias ene de retumilo

1085
01:05:40,440 --> 01:05:44,380
hodiaŭ ke ni uzas en Harvard kursoj, por la kurso komerca ilo ke Google mapoj uzas

1086
01:05:44,380 --> 01:05:48,660
doni al vi tutan faskon de dinamismo, Facebook donas al vi montri momenteto stato ĝisdatigoj,

1087
01:05:48,660 --> 01:05:51,430
Twitter uzas ĝin por montri al vi tweets momento.

1088
01:05:51,430 --> 01:05:53,820
Ĉio ĉi ni komencos mergi nin in

1089
01:05:53,820 --> 01:05:57,190
Sed alveni, ni bezonas kompreni iom ion pri la interreto.

1090
01:05:57,190 --> 01:06:01,130
Ĉi klipo tie estas nur unu minuto longe, kaj ni supozu por nun ĉi tio estas, fakte,

1091
01:06:01,130 --> 01:06:08,380
kiel la Interreto funkcias kiel teaser por kio estas venonta. Mi donas al vi "Soldatoj de la Reto."

1092
01:06:08,380 --> 01:06:14,720
>> [♫ Malrapida ĥoro muziko ♫]

1093
01:06:14,720 --> 01:06:20,450
[Vira rakontanto] Li venis kun mesaĝo.

1094
01:06:20,450 --> 01:06:23,770
Kun protokolo cxiuj liaj propraj.

1095
01:06:23,770 --> 01:06:37,270
[♫ Faster elektronika muziko ♫]

1096
01:06:37,270 --> 01:06:41,330
Li venis al mondo de cool firewalls, uncaring routers,

1097
01:06:41,330 --> 01:06:45,690
kaj danĝeroj multe pli malbone ol morto.

1098
01:06:45,690 --> 01:06:55,400
Li estas rapida. Li estas forta. Li estas TCP / IP, kaj li havas vian adreson.

1099
01:06:55,400 --> 01:06:59,250
Soldatoj de la Reto.

1100
01:06:59,250 --> 01:07:05,290
[Malan] Sekva semajno, tiam. Interreto. Retejo programado. Ĉi tiu estas CS50.

1101
01:07:05,290 --> 01:07:08,290
[CS50.TV]