1
00:00:00,000 --> 00:00:10,900

2
00:00:10,900 --> 00:00:15,860
>> SPEAKER 1: Id-dritt, għalhekk dan huwa
CS50 Dan huwa l-aħħar ta 'ħames ġimgħa.

3
00:00:15,860 --> 00:00:19,220
U tfakkar li aħħar darba aħna
bdiet tħares lejn l-informazzjoni fancier

4
00:00:19,220 --> 00:00:22,310
strutturi li bdew isolvu
problemi, li bdew jintroduċu

5
00:00:22,310 --> 00:00:25,640
problemi ġodda, iżda l-muftieħ għal dan
kien il-tip ta 'kamini li aħna

6
00:00:25,640 --> 00:00:27,940
bdew jagħmlu minn node biex node.

7
00:00:27,940 --> 00:00:30,085
Allura dan il-kors huwa
lista marbuta weħidhom.

8
00:00:30,085 --> 00:00:31,960
U billi marbut waħdu,
I jfisser hemm biss wieħed

9
00:00:31,960 --> 00:00:33,380
ħajt bejn kull ta'dawk il-lymph.

10
00:00:33,380 --> 00:00:35,890
Jirriżulta li tista 'tagħmel fancier
affarijiet simili listi marbuta doppjament

11
00:00:35,890 --> 00:00:38,470
fejn inti għandek vleġġa
għaddejjin fiż-żewġ direzzjonijiet, li

12
00:00:38,470 --> 00:00:40,320
jistgħu jgħinu ma 'ċerti effiċjenzi.

13
00:00:40,320 --> 00:00:42,000
Iżda din solvuta l-problema?

14
00:00:42,000 --> 00:00:43,500
Liema problema ma dan issolvi?

15
00:00:43,500 --> 00:00:46,620
Għaliex ma aħna kura nhar it-Tnejn?

16
00:00:46,620 --> 00:00:49,820
Għaliex, fit-teorija, ma aħna kura nhar it-Tnejn?

17
00:00:49,820 --> 00:00:50,630
X'tikkontrolla do?

18
00:00:50,630 --> 00:00:51,950
>> UDJENZA: Nistgħu dinamiku resize.

19
00:00:51,950 --> 00:00:53,740
>> SPEAKER 1: OK, sabiex inkunu nistgħu
dinamiku resize.

20
00:00:53,740 --> 00:00:54,710
Prosit tnejn inti.

21
00:00:54,710 --> 00:00:57,560
Allura inti tista 'dinamikament resize dan
istruttura tad-data, filwaqt firxa,

22
00:00:57,560 --> 00:01:00,760
irtirar, inti għandek tkun taf
priori kemm l-ispazju trid

23
00:01:00,760 --> 00:01:03,870
u jekk għandek bżonn ta 'aktar ftit
ispazju, int tip ta 'minn xortih.

24
00:01:03,870 --> 00:01:05,560
Inti għandek toħloq firxa sħiħa ġdida.

25
00:01:05,560 --> 00:01:07,893
Int għandek timxi kollha ta 'tiegħek
data minn waħda għall-oħra,

26
00:01:07,893 --> 00:01:10,600
eventwalment ħielsa l-firxa qodma
jekk inti tista ', u mbagħad jipproċedi.

27
00:01:10,600 --> 00:01:13,891
Li biss iħoss jiswew ħafna u ħafna
ineffiċjenti, u tabilħaqq jista 'jkun.

28
00:01:13,891 --> 00:01:14,890
Iżda dan mhux kollox tajjeb.

29
00:01:14,890 --> 00:01:18,180
Qed inħallsu prezz, dak li kien wieħed
tal-prezzijiet aktar ovvji aħna

30
00:01:18,180 --> 00:01:20,550
tħallas permezz tintuża lista marbut?

31
00:01:20,550 --> 00:01:22,825
>> UDJENZA: Irridu użu
ispazju doppja għal kull wieħed.

32
00:01:22,825 --> 00:01:25,200
SPEAKER 1: Yeah, għalhekk għandna bżonn
mill-inqas darbtejn ħafna spazju.

33
00:01:25,200 --> 00:01:27,700
Fil-fatt, I realizzati din l-istampa ta
anki ftit qarrieqa,

34
00:01:27,700 --> 00:01:32,200
minħabba fuq IDE CS50 fil-lott ta 'moderna
kompjuters, pointer jew indirizz

35
00:01:32,200 --> 00:01:33,700
mhuwiex fil-fatt erba 'bytes.

36
00:01:33,700 --> 00:01:36,090
Huwa ħafna drabi dawn
jiem tmien bytes, li

37
00:01:36,090 --> 00:01:38,530
tfisser il-qiegħ l-aktar
rettangoli hemm fir-realtà

38
00:01:38,530 --> 00:01:40,900
huma tip ta 'darbtejn
kbar kif dak li stajt mfassla,

39
00:01:40,900 --> 00:01:44,409
li jfisser li inti qed tuża tliet darbiet
spazju kemm aħna jista 'jkollha mod ieħor.

40
00:01:44,409 --> 00:01:46,700
Issa fl-istess ħin, aħna qed
xorta jitkellem bytes, id-dritt?

41
00:01:46,700 --> 00:01:49,140
Aħna qed mhux neċessarjament jitkellem
megabytes jew gigabytes,

42
00:01:49,140 --> 00:01:51,000
sakemm din id-data istrutturi tikseb big.

43
00:01:51,000 --> 00:01:54,510
>> U hekk illum aħna jibdew jikkunsidraw
kif nistgħu tesplora data

44
00:01:54,510 --> 00:01:57,310
b'mod aktar effiċjenti jekk
fatt l-informazzjoni tkompli tikber.

45
00:01:57,310 --> 00:02:00,360
Imma ejja jippruvaw canonicalize
l-ewwel operazzjonijiet

46
00:02:00,360 --> 00:02:02,460
li inti tista 'tagħmel fuq dawn
tipi ta 'strutturi ta' dejta.

47
00:02:02,460 --> 00:02:04,790
Allura xi ħaġa bħal marbut
Lista ġeneralment jappoġġja

48
00:02:04,790 --> 00:02:07,514
operazzjonijiet simili tħassar,
daħħal, u tfittxija.

49
00:02:07,514 --> 00:02:08,639
U dak li għandi jfisser minn dak?

50
00:02:08,639 --> 00:02:11,222
Li sempliċiment ifisser li s-soltu,
jekk in-nies qed jużaw lista marbuta,

51
00:02:11,222 --> 00:02:14,287
dawn jew xi ħadd ieħor ħa implimentat
funzjonijiet bħall tħassar, daħħal,

52
00:02:14,287 --> 00:02:16,120
u tfittxija, sabiex inti tista '
fil-fatt jagħmlu xi ħaġa

53
00:02:16,120 --> 00:02:18,030
utli ma 'l-istruttura tad-data.

54
00:02:18,030 --> 00:02:20,760
Mela ejja tagħti ħarsa
lejn kif nistgħu jimplimentaw

55
00:02:20,760 --> 00:02:24,530
xi kodiċi għall lista marbut kif ġej.

56
00:02:24,530 --> 00:02:27,885
>> Allura dan huwa biss xi kodiċi C,
lanqas programm sħiħ

57
00:02:27,885 --> 00:02:29,260
li jien verament malajr bit-tarjola up.

58
00:02:29,260 --> 00:02:32,300
Mhuwiex online fid-distribuzzjoni
kodiċi, minħabba li mhux se tmexxi effettivament.

59
00:02:32,300 --> 00:02:33,790
Imma avviż stajt biss
ma kumment qal,

60
00:02:33,790 --> 00:02:36,130
dot dot dot, hemm xi ħaġa
hemm, dot dot dot, xi ħaġa hemmhekk.

61
00:02:36,130 --> 00:02:38,410
U ejja biss ħarsa lejn
dak li l-partijiet mmerraq huma.

62
00:02:38,410 --> 00:02:40,790
Allura fuq il-linja tlieta,
ifakkar li issa dan huwa

63
00:02:40,790 --> 00:02:45,960
aħna pproponiet li tiddikjara node aħħar
ħin, wieħed minn dawk l-oġġetti rettangolari.

64
00:02:45,960 --> 00:02:48,790
Hija għandha int li aħna ser sejħa N,
imma nistgħu sejħa hija xi ħaġa,

65
00:02:48,790 --> 00:02:51,920
u mbagħad stilla node Struct imsejħa jmiss.

66
00:02:51,920 --> 00:02:55,520
U biss li jkun ċar, li t-tieni
linja, fuq il-linja sitt, dak li huwa dan?

67
00:02:55,520 --> 00:02:57,930
X'inhu tagħmel għalina?

68
00:02:57,930 --> 00:03:01,044
Minħabba li ċertament jistenna aktar
cryptic minn varjabbli tas-soltu tagħna.

69
00:03:01,044 --> 00:03:02,740
>> UDJENZA: Dan jagħmilha jimxu wieħed.

70
00:03:02,740 --> 00:03:04,650
>> SPEAKER 1: Dan jagħmilha aktar jimxu wieħed.

71
00:03:04,650 --> 00:03:08,580
U biex ikunu aktar preċiżi,
se taħżen l-indirizz

72
00:03:08,580 --> 00:03:11,582
tal-node li kien ifisser li jkun
semantikament li jmiss lilu, id-dritt?

73
00:03:11,582 --> 00:03:13,540
Allura huwa mhux ser
neċessarjament jimxu xejn.

74
00:03:13,540 --> 00:03:15,290
Huwa biss se
jaħżnu valur, li huwa

75
00:03:15,290 --> 00:03:17,170
se tkun l-indirizz
ta 'xi node oħra,

76
00:03:17,170 --> 00:03:20,810
u hu għalhekk li konna qal Istituzzjonjijiet
star node, l-istilla li turi

77
00:03:20,810 --> 00:03:22,370
pointer jew indirizz.

78
00:03:22,370 --> 00:03:26,390
OK, hekk issa jekk għandek tassumi li għandna
din N disponibbli għalina, u ejja

79
00:03:26,390 --> 00:03:29,490
jassumi li xi ħadd ieħor ħa
mdaħħal mazz sħiħ ta 'numri interi

80
00:03:29,490 --> 00:03:30,400
fi lista marbuta.

81
00:03:30,400 --> 00:03:35,640
U dik il-lista marbuta hija
indikat minn xi punt

82
00:03:35,640 --> 00:03:39,040
a imsejjaħ lista varjabbli li l-
għadda fil hawn bħala parametru,

83
00:03:39,040 --> 00:03:43,120
kif nista tmur dwar linja
14 implimentazzjoni engine?

84
00:03:43,120 --> 00:03:45,990
Fi kliem ieħor, jekk I am implimentazzjoni
funzjoni li l-għan fil-ħajja

85
00:03:45,990 --> 00:03:48,889
huwa li jieħdu int u allura l-
bidu ta 'lista marbuta,

86
00:03:48,889 --> 00:03:50,430
li huwa pointer għal-lista marbuta.

87
00:03:50,430 --> 00:03:52,992
Bħal ewwel, li naħseb David
kien voluntier tagħna nhar it-Tnejn,

88
00:03:52,992 --> 00:03:54,700
kien tipponta lejn
il-lista sħiħa marbuta,

89
00:03:54,700 --> 00:03:57,820
huwa kif jekk aħna qed tgħaddi
David fil bħala argument tagħna hawn.

90
00:03:57,820 --> 00:03:59,990
Kif do we go dwar traversat din il-lista?

91
00:03:59,990 --> 00:04:04,640
Ukoll, jirriżulta li għalkemm
pointers huma relattivament ġodda issa lilna,

92
00:04:04,640 --> 00:04:07,010
nistgħu nagħmlu dan relattivament
jinftiehem.

93
00:04:07,010 --> 00:04:09,500
>> Jien ser jimxi 'l quddiem u
tiddikjara varjabbli temporanju li

94
00:04:09,500 --> 00:04:12,364
b'konvenzjoni huwa biss se
li se jkun jismu pointer, jew PTR,

95
00:04:12,364 --> 00:04:14,030
imma int tista 'sejħa hija xi ħaġa li trid.

96
00:04:14,030 --> 00:04:16,470
U jien ser initialize
dan il-bidu tal-lista.

97
00:04:16,470 --> 00:04:20,050
Allura inti tista 'tip ta think ta' dan
kif me l-għalliem l-oħra jum,

98
00:04:20,050 --> 00:04:23,580
tip ta 'tipponta lejn xi ħadd
fost il-bnedmin tagħna bħala voluntiera.

99
00:04:23,580 --> 00:04:26,470
Hekk jien varjabbli temporanju li l-
biss tipponta fl-istess ħaġa

100
00:04:26,470 --> 00:04:31,390
li tagħna inzerta jismu
voluntier David kien ukoll fakkret.

101
00:04:31,390 --> 00:04:35,440
Issa filwaqt pointer huwa
mhux null, minħabba recall

102
00:04:35,440 --> 00:04:40,350
li null hija xi valur sentinella speċjali
l tiddemarka l-aħħar tal-lista,

103
00:04:40,350 --> 00:04:44,280
so filwaqt Jien ma tipponta lejn il-
art bħal aħħar voluntier tagħna

104
00:04:44,280 --> 00:04:47,190
kien, ejja imorru quddiem
u jagħmel dan li ġej.

105
00:04:47,190 --> 00:04:51,820
Jekk Pointer u issa I tip ta 'tixtieq
biex jagħmlu dak li għamilna mal-istudent

106
00:04:51,820 --> 00:04:57,410
structure-- jekk pointer dot li jmiss
equals-- pjuttost, jekk pointer dot N ugwali

107
00:04:57,410 --> 00:05:02,290
huwa daqs il-varjabbli N, il-
argument li kien għadda fi,

108
00:05:02,290 --> 00:05:05,370
imbagħad Irrid immur quddiem
u jgħidu ritorn vera.

109
00:05:05,370 --> 00:05:11,020
I sabu l-għadd N ġewwa ta '
wieħed mill-lymph tal-lista marbuta tiegħi.

110
00:05:11,020 --> 00:05:13,500
Iżda l-dot m'għadhomx
xogħlijiet f'dan il-kuntest,

111
00:05:13,500 --> 00:05:17,260
minħabba pointer, PTR, huwa
tabilħaqq pointer, indirizz,

112
00:05:17,260 --> 00:05:20,632
aħna attwalment jistgħu wonderfully
użu fl-aħħar biċċa ta 'sintassi

113
00:05:20,632 --> 00:05:22,590
dak it-tip ta 'jagħmel
sens intuwittivi u fil-fatt

114
00:05:22,590 --> 00:05:27,870
użu vleġġa hawn, li jfisser jmorru minn
li tindirizza lill-eqreb numru sħiħ hemmhekk in.

115
00:05:27,870 --> 00:05:30,160
Allura huwa simili ħafna fl
ispirtu lill-operatur dot,

116
00:05:30,160 --> 00:05:33,860
iżda minħabba pointer mhix pointer
u mhux Struct innifisha,

117
00:05:33,860 --> 00:05:35,380
aħna biss jużaw il-vleġġa.

118
00:05:35,380 --> 00:05:40,620
>> Allura jekk il-node attwali li I, l
varjabbli temporanju, am tipponta lejn

119
00:05:40,620 --> 00:05:43,060
mhux N, dak li nixtieq do?

120
00:05:43,060 --> 00:05:45,910
Ukoll, ma 'voluntiera umani tiegħi
li kellna hawn l-oħra jum,

121
00:05:45,910 --> 00:05:49,710
jekk l-ewwel bniedem tiegħi ma jkunx dak I
trid, u forsi t-tieni umana mhix

122
00:05:49,710 --> 00:05:52,660
l-waħda li nixtieq, u t-tielet, I
bżonn li jżommu fiżikament jiċċaqalqu.

123
00:05:52,660 --> 00:05:54,690
Bħal kif nista pass permezz ta 'lista?

124
00:05:54,690 --> 00:05:57,470
Meta kellna firxa, inti
biss ma simili I plus plus.

125
00:05:57,470 --> 00:06:03,660
Iżda f'dan il-każ, huwa biżżejjed li
do pointer, gets, pointer, li jmiss.

126
00:06:03,660 --> 00:06:07,580
Fi kliem ieħor, il-qasam li jmiss
huwa bħall kollha tal-idejn xellug

127
00:06:07,580 --> 00:06:10,880
li l-voluntiera umani tagħna nhar it-Tnejn
kienu qed jużaw punt f'xi node ieħor.

128
00:06:10,880 --> 00:06:12,890
Dawk kienu ġirien tagħhom li jmiss.

129
00:06:12,890 --> 00:06:17,060
>> Mela jekk jien tixtieq li pass permezz din il-lista,
I ma tista 'biss tagħmel I plus plus aktar,

130
00:06:17,060 --> 00:06:20,120
I minflok ngħid
I, pointer, va

131
00:06:20,120 --> 00:06:24,650
daqs il x'ikun il-qasam li jmiss,
qasam jmiss huwa,-qasam li jmiss,

132
00:06:24,650 --> 00:06:28,350
wara kollha ta 'dawk l-idejn xellug
li kellna fuq tipponta istadju

133
00:06:28,350 --> 00:06:30,000
għal xi valuri sussegwenti.

134
00:06:30,000 --> 00:06:32,590
U jekk niġi permezz
li iterazzjoni kollu,

135
00:06:32,590 --> 00:06:39,330
u finalment, I hit null li ma jkollhomx
misjuba N għadhom, I biss ritorn foloz.

136
00:06:39,330 --> 00:06:44,100
Għalhekk għal darb'oħra, dak kollu li aħna qed tagħmel hawn,
kif fis-istampa mument ilu,

137
00:06:44,100 --> 00:06:47,840
qed jibda mill tipponta lejn l-
bidu tal-lista preżumibbilment.

138
00:06:47,840 --> 00:06:50,970
U mbagħad I kontroll, huwa l-valur
I infittex ugwali għal disa?

139
00:06:50,970 --> 00:06:52,650
Jekk iva, I ritorn vera u jien jsir.

140
00:06:52,650 --> 00:06:56,450
Jekk le, I taġġorna naħa tiegħi,
AKA pointer, punt

141
00:06:56,450 --> 00:06:59,540
fil-post tal-vleġġa li jmiss, u
imbagħad lokazzjoni il-vleġġa li jmiss,

142
00:06:59,540 --> 00:07:00,480
u dak li jmiss.

143
00:07:00,480 --> 00:07:03,770
Jien sempliċiment mixi permezz ta 'dan array.

144
00:07:03,770 --> 00:07:06,010
>> Għalhekk għal darb'oħra, quién?

145
00:07:06,010 --> 00:07:07,861
Bħal dak li huwa dan ingredjent għall?

146
00:07:07,861 --> 00:07:10,360
Ukoll, ifakkar li daħħalna
il-kunċett ta 'ċumnija, li

147
00:07:10,360 --> 00:07:15,400
hija data astratta tip sakemm huwa
mhux xi ħaġa C, mhuwiex xi ħaġa CS50,

148
00:07:15,400 --> 00:07:19,430
huwa ta 'idea astratta, din l-idea ta'
stivar affarijiet fuq quċċata ta 'xulxin

149
00:07:19,430 --> 00:07:21,820
li jistgħu jiġu implimentati
għenieqed ta 'modi differenti.

150
00:07:21,820 --> 00:07:25,600
U mod wieħed aħna propost kien ma
firxa, jew ma 'lista marbuta.

151
00:07:25,600 --> 00:07:29,570
U jirriżulta li kanonikament, a
munzell jappoġġja mill-inqas żewġ operazzjonijiet.

152
00:07:29,570 --> 00:07:32,320
U l-kliem buzz huma timbotta, biex
imbotta xi ħaġa fuq il-munzell,

153
00:07:32,320 --> 00:07:34,770
bħal trej ġdid fil-
dining sala, jew pop,

154
00:07:34,770 --> 00:07:39,000
li jfisser li tneħħi l-topmost
trej mill-munzell fil-dining

155
00:07:39,000 --> 00:07:41,500
sala, u mbagħad forsi xi
operazzjonijiet oħrajn ukoll.

156
00:07:41,500 --> 00:07:45,770
Allura kif tista 'niddefinixxu l-istruttura
li aħna issa qed ssejjaħ munzell?

157
00:07:45,770 --> 00:07:50,020
>> Well, aħna għandna kollha tal-meħtieġa
sintassi għad-dispożizzjoni tagħna fil C. I say,

158
00:07:50,020 --> 00:07:53,830
tagħti me definizzjoni tip ta '
a Struct ġewwa ta 'ċumnija,

159
00:07:53,830 --> 00:07:58,030
Jien se ngħid huwa firxa, ta '
mazz sħiħ ta 'numri u mbagħad daqs.

160
00:07:58,030 --> 00:08:00,930
Allura fi kliem ieħor, jekk irrid
biex jimplimentaw dan il-kodiċi,

161
00:08:00,930 --> 00:08:03,830
let me go u biss tip ta '
jiġbed dak li dan huwa qal.

162
00:08:03,830 --> 00:08:06,317
Allura dan huwa qal, tagħti me a
struttura li ltqajna firxa,

163
00:08:06,317 --> 00:08:09,400
u jien ma nafx f'liema kapaċità hija,
huwa apparentement xi kostanti li stajt

164
00:08:09,400 --> 00:08:10,858
definiti x'imkien ieħor, u li l-multa.

165
00:08:10,858 --> 00:08:15,260
Iżda jissoponi huwa biss wieħed,
tnejn, tlieta, erba ', ħames.

166
00:08:15,260 --> 00:08:16,700
Allura kapaċità hija 5.

167
00:08:16,700 --> 00:08:21,730
Dan l-element ġewwa tal tiegħi
istruttura se tissejjaħ numri.

168
00:08:21,730 --> 00:08:24,020
U mbagħad I bżonn wieħed
varjabbli oħra apparentement

169
00:08:24,020 --> 00:08:27,814
imsejħa daqs li inizjalment jien ser
li jkun stipulat huwa initialized għal żero.

170
00:08:27,814 --> 00:08:29,730
Jekk hemm xejn fil
l-munzell, id-daqs huwa żero,

171
00:08:29,730 --> 00:08:31,420
u huwa l-valuri taż-żibel fin-numru.

172
00:08:31,420 --> 00:08:33,450
Għandi l-ebda idea x'inhu fil hemm għadha biss.

173
00:08:33,450 --> 00:08:36,059
>> Mela jekk jien tixtieq li timbotta
xi ħaġa fuq il-munzell,

174
00:08:36,059 --> 00:08:40,780
suppose I call il-buttuna funzjoni, u
I say push 50, bħan-numru 50,

175
00:08:40,780 --> 00:08:44,090
fejn tipproponi
I tiġbed f'dan array?

176
00:08:44,090 --> 00:08:47,124
Hemm ħames tweġibiet differenti possibbli.

177
00:08:47,124 --> 00:08:48,790
Fejn tridu li timbotta l-għadd 50?

178
00:08:48,790 --> 00:08:51,899
Jekk l-għan hawnhekk, għal darb'oħra, sejħa tal-
push funzjoni, jgħaddu fi argument

179
00:08:51,899 --> 00:08:52,940
ta '50, fejn ma nressaq dan?

180
00:08:52,940 --> 00:08:55,680

181
00:08:55,680 --> 00:08:59,052
Ta 'ħames possible-- 20% ċans
ta guessing korrett.

182
00:08:59,052 --> 00:08:59,896
Iva?

183
00:08:59,896 --> 00:09:00,740
>> UDJENZA: Far dritt.

184
00:09:00,740 --> 00:09:01,990
>> SPEAKER 1: Far dritt.

185
00:09:01,990 --> 00:09:08,359
Issa hemm ċans 25%
ta guessing korrett.

186
00:09:08,359 --> 00:09:09,650
Allura li fil-fatt tkun multa.

187
00:09:09,650 --> 00:09:12,770
B'konvenzjoni, I ser jgħidu ma 'firxa,
aħna ġeneralment tibda fil-xellug,

188
00:09:12,770 --> 00:09:14,519
iżda nistgħu ċertament
tibda fil-lemin.

189
00:09:14,519 --> 00:09:17,478
Allura l-spoiler hawn ikunu jien
probabbilment se tiġbed fuq ix-xellug,

190
00:09:17,478 --> 00:09:20,060
bħad fil-firxa normali fejn
I tibda tmur xellug għal-lemin.

191
00:09:20,060 --> 00:09:21,780
Imma jekk inti tista 'flip
l-aritmetika, multa.

192
00:09:21,780 --> 00:09:23,060
Huwa biss mhux konvenzjonali.

193
00:09:23,060 --> 00:09:24,880
OK, I bżonn tagħmel waħda
bidla aktar għalkemm.

194
00:09:24,880 --> 00:09:27,710
Issa li stajt imbuttat xi ħaġa
fuq il-munzell, xi jmiss?

195
00:09:27,710 --> 00:09:29,400
>> Kull dritt, ikolli inkrement-daqs.

196
00:09:29,400 --> 00:09:32,600
So let me jimxi 'l quddiem u biss
jaġġornaw dan, li kien żero.

197
00:09:32,600 --> 00:09:35,950
U minflok issa, jien ser
li jitqiegħdu fil-valur waħda.

198
00:09:35,950 --> 00:09:39,460
U issa suppose I push ieħor
Numru fuq il-munzell, bħal 51.

199
00:09:39,460 --> 00:09:42,680
Well, I jkollhom jagħmlu waħda aktar
bidla, li jkun sa l-daqs tnejn.

200
00:09:42,680 --> 00:09:46,100
U allura suppose I push waħda aktar
Numru fuq il-munzell bħal 61,

201
00:09:46,100 --> 00:09:52,530
issa I bżonn jaġġornaw id-daqs wieħed aktar
ħin, u jiksbu l-valur 3 skond il-qies.

202
00:09:52,530 --> 00:09:54,690
U issa jissoponi I call pop.

203
00:09:54,690 --> 00:09:57,250
Issa pop, b'konvenzjoni,
ma jieħdu argument.

204
00:09:57,250 --> 00:10:00,430
Bil-munzell, il-sħiħ
punt tal-metafora trej

205
00:10:00,430 --> 00:10:03,450
hija li inti ma għandekx diskrezzjoni
mur jiksbu dak trej, inti kollha tista 'tagħmel

206
00:10:03,450 --> 00:10:06,330
huwa pop l topmost wieħed mill
l-munzell, sempliċement minħabba.

207
00:10:06,330 --> 00:10:08,010
Dak hu li din l-istruttura tad-data ma.

208
00:10:08,010 --> 00:10:12,250
>> Allura billi li l-loġika jekk I
jgħidu pop, dak li jiġi off?

209
00:10:12,250 --> 00:10:13,080
Allura 61.

210
00:10:13,080 --> 00:10:15,402
Allura dak li verament huwa l-kompjuter
se jagħmlu fil-memorja?

211
00:10:15,402 --> 00:10:16,610
Xi jfisser kodiċi tiegħi għandek tagħmel?

212
00:10:16,610 --> 00:10:20,330
What would you tipproponi
nagħmlu l-bidla fuq l-iskrin?

213
00:10:20,330 --> 00:10:23,410
X'għandu jinbidel?

214
00:10:23,410 --> 00:10:24,960
Jiddispjacini?

215
00:10:24,960 --> 00:10:26,334
Allura aħna jeħles 61.

216
00:10:26,334 --> 00:10:27,500
So I definittivament jistgħu jagħmlu dan.

217
00:10:27,500 --> 00:10:28,640
U nista 'jeħles 61.

218
00:10:28,640 --> 00:10:30,980
U allura dak l-oħra
bidla jeħtieġ li jiġri?

219
00:10:30,980 --> 00:10:33,160
Daqs probabbilment irid imur lura għal tnejn.

220
00:10:33,160 --> 00:10:34,210
U hekk li l-multa.

221
00:10:34,210 --> 00:10:36,690
Iżda stenna minuta, daqs
mument ilu kien tlieta.

222
00:10:36,690 --> 00:10:38,240
Ejja biss tagħmel verifika sanità malajr.

223
00:10:38,240 --> 00:10:41,810
Kif ma nafu li aħna
riedu li teħles minn 61?

224
00:10:41,810 --> 00:10:42,760
Għaliex aħna qed popping.

225
00:10:42,760 --> 00:10:46,450
U so I jkollhom din it-tieni daqs proprjetà.

226
00:10:46,450 --> 00:10:48,470
>> Stenna minuta, jien
ħsieb lura għall ġimgħatejn

227
00:10:48,470 --> 00:10:51,660
meta bdejna nitkellmu dwar
arrays, fejn dan kien post żero,

228
00:10:51,660 --> 00:10:55,920
din kienet f'post wieħed, dan kien post
tnejn, dan huwa post tlieta, erba,

229
00:10:55,920 --> 00:10:58,460
jidher qisu l-
relazzjoni bejn id-daqs

230
00:10:58,460 --> 00:11:02,780
u l-element li nixtieq li jitneħħew
mill-firxa jidher li jkun biss dak?

231
00:11:02,780 --> 00:11:05,120
Daqs minus wieħed.

232
00:11:05,120 --> 00:11:07,786
U hekk li kif bħala bnedmin
nafu 61 jiġi l-ewwel.

233
00:11:07,786 --> 00:11:09,160
Kif jgħid il-kompjuter ser tkun taf?

234
00:11:09,160 --> 00:11:11,701
Meta kodiċi tiegħek, fejn inti probabilment
trid tagħmel wieħed nieqes daqs,

235
00:11:11,701 --> 00:11:14,950
hekk tlieta nieqes wieħed hu ta 'tnejn, u li
ifisser irridu li teħles minn 61.

236
00:11:14,950 --> 00:11:18,000
U allura nistgħu tabilħaqq taġġorna
id-daqs hekk li d-daqs issa

237
00:11:18,000 --> 00:11:20,300
jmur minn tlieta sa tnejn biss.

238
00:11:20,300 --> 00:11:24,520
U biss sabiex ikunu pedantic, jien ser
biex jipproponi li jien jsir, right?

239
00:11:24,520 --> 00:11:27,660
You propost intuwittivament
korrett I għandhom jeħles 61.

240
00:11:27,660 --> 00:11:30,700
Imma ma jkunux I tip ta '
tip ta 'gotten rid ta '61?

241
00:11:30,700 --> 00:11:33,790
Stajt effettiv minsija
li huwa attwalment hemm.

242
00:11:33,790 --> 00:11:37,680
U jaħsbu lura għal PSET4, jekk inti stajt taqra
l-artiklu dwar forensika, il-PDF

243
00:11:37,680 --> 00:11:40,780
li kellna inti guys taqra, jew inti
se jaqra din il-ġimgħa għall PSET4.

244
00:11:40,780 --> 00:11:44,300
Ifakkar li dan huwa effettivament germane li
l-idea kollha tal-forensiċi kompjuter.

245
00:11:44,300 --> 00:11:47,820
What a kompjuter ġeneralment ma huwa
hija biss jinsa fejn xi ħaġa,

246
00:11:47,820 --> 00:11:51,300
iżda ma jmorru fi u simili
jippruvaw li tobrox it out jew override

247
00:11:51,300 --> 00:11:54,560
dawk bits biż-żeri u dawk
jew xi mudell każwali ieħor

248
00:11:54,560 --> 00:11:56,690
sakemm inti stess tagħmel hekk deliberatament.

249
00:11:56,690 --> 00:11:58,930
Allura intwizzjoni tiegħek kienet
dritt, ejja jeħles 61.

250
00:11:58,930 --> 00:12:00,650
Iżda fir-realtà, aħna ma għandekx li jolqot.

251
00:12:00,650 --> 00:12:04,040
Jinħtieġ li ninsew li
huwa hemmhekk billi jinbidlu daqs tagħna.

252
00:12:04,040 --> 00:12:05,662
>> Issa hemm problema ma 'dan munzell.

253
00:12:05,662 --> 00:12:07,620
Jekk I iżommu imbuttar affarijiet
fuq il-munzell, x'hemm

254
00:12:07,620 --> 00:12:11,167
ovvjament jiġri
fi ftit ftit żmien mumenti?

255
00:12:11,167 --> 00:12:12,500
Aħna qed tmur biex jispiċċaw l-ispazju.

256
00:12:12,500 --> 00:12:13,580
U dak li nagħmlu?

257
00:12:13,580 --> 00:12:14,680
Aħna tip ta 'invitat.

258
00:12:14,680 --> 00:12:19,000
Din l-implimentazzjoni ma jħallux
us resize l-array, għaliex bl-użu

259
00:12:19,000 --> 00:12:21,240
dan sintassi, jekk inti
think lura għal ġimgħatejn,

260
00:12:21,240 --> 00:12:23,520
ladarba inti ħadthom iddikjarat
id-daqs ta 'firxa,

261
00:12:23,520 --> 00:12:26,780
ma rajniex mekkaniżmu għadu fejn
tista 'tbiddel id-daqs tal-array.

262
00:12:26,780 --> 00:12:29,020
U tabilħaqq C ma jkollux din il-karatteristika.

263
00:12:29,020 --> 00:12:32,524
Jekk inti tgħidli tagħti me ħames
Nths, jsejħulhom numri,

264
00:12:32,524 --> 00:12:33,940
li kollox int ser ġġibu.

265
00:12:33,940 --> 00:12:38,790
Allura nagħmlu issa bħala tat-Tnejn, ikollhom
l-abbiltà li jesprimu soluzzjoni

266
00:12:38,790 --> 00:12:42,480
għalkemm, aħna biss bżonn tweak
id-definizzjoni ta 'munzell tagħna

267
00:12:42,480 --> 00:12:46,840
li ma jkun hemm xi firxa hard-kodifikati,
iżda biss biex jaħżnu l-indirizz.

268
00:12:46,840 --> 00:12:47,890
>> Issa għaliex huwa dan?

269
00:12:47,890 --> 00:12:51,690
Issa aħna biss għandhom tkun komda ma
il-fatt li meta programm tiegħi runs,

270
00:12:51,690 --> 00:12:53,730
Jien preżumibbilment se
għandek titlob il-bniedem,

271
00:12:53,730 --> 00:12:55,110
kemm numri tridu taħżen?

272
00:12:55,110 --> 00:12:56,776
Allura l-input trid tiġi minn x'imkien.

273
00:12:56,776 --> 00:12:59,140
Imma ladarba naf li
numru, allura nista 'biss

274
00:12:59,140 --> 00:13:02,470
użu dak jiffunzjonaw biex jagħtu
me blokki ta 'memorja?

275
00:13:02,470 --> 00:13:03,580
I jistgħu jużaw malloc.

276
00:13:03,580 --> 00:13:06,710
U nista 'ngħid xi numru ta'
bytes Irrid lura għal dawn Nths.

277
00:13:06,710 --> 00:13:10,910
U kollha jien li jaħżen fil-numri
varjabbli hawn ġewwa ta 'dan Struct

278
00:13:10,910 --> 00:13:13,480
għandu jkun dak?

279
00:13:13,480 --> 00:13:18,440
X'inhu dak li attwalment tmur fil-
numri f'dan ix-xenarju?

280
00:13:18,440 --> 00:13:21,300
Yeah, pointer għall-ewwel
byte ta 'dak blokki ta' memorja,

281
00:13:21,300 --> 00:13:24,940
jew b'mod aktar speċifiku,-indirizz
ta 'l-ewwel minn dawn bytes.

282
00:13:24,940 --> 00:13:27,300
Ma jimpurtax jekk huwa wieħed
byte jew biljun bytes,

283
00:13:27,300 --> 00:13:28,890
I biss ħtieġa li jimpurtak mill-ewwel.

284
00:13:28,890 --> 00:13:31,530
Għaliex dak garanziji malloc u
tiegħi garanziji sistema operattiva,

285
00:13:31,530 --> 00:13:34,170
huwa li l-blokki ta 'memorja I
nikseb, li għaddej biex jkun kontigwu.

286
00:13:34,170 --> 00:13:35,378
Hemm mhux ser tkun nuqqasijiet.

287
00:13:35,378 --> 00:13:38,576
Mela jekk stajt talab għal 50
bytes jew 1,000 bytes,

288
00:13:38,576 --> 00:13:40,450
dawn qed kollha ser ikunu
lura lura lura.

289
00:13:40,450 --> 00:13:44,500
U sakemm I remember kif big, kif
ħafna I talab għal, kull I bżonn tkun taf

290
00:13:44,500 --> 00:13:46,230
hija l-ewwel indirizz tali.

291
00:13:46,230 --> 00:13:48,660
>> Allura issa għandna l-ħila fil-kodiċi.

292
00:13:48,660 --> 00:13:51,280
Għalkemm, li għaddej biex tieħu us
aktar ħin biex jikteb dan up,

293
00:13:51,280 --> 00:13:55,900
aħna issa tista 'talloka mill-ġdid li l-memorja billi
biss ħażna f'indirizz differenti hemmhekk

294
00:13:55,900 --> 00:13:59,060
jekk irridu akbar jew saħansitra
blokki iżgħar ta 'memorja.

295
00:13:59,060 --> 00:14:00,170
Allura hawnhekk għal off-kummerċ.

296
00:14:00,170 --> 00:14:01,360
Issa irridu jiksbu dinamiżmu.

297
00:14:01,360 --> 00:14:03,350
Għad għandna
contiguousness Jien titlob.

298
00:14:03,350 --> 00:14:05,881
Minħabba malloc se tagħtina
blokki kontigwi ta 'memorja.

299
00:14:05,881 --> 00:14:08,630
Iżda dan se jkunu uġigħ fl
l-għonq għalina, il-programmer,

300
00:14:08,630 --> 00:14:09,770
li attwalment kodiċi up.

301
00:14:09,770 --> 00:14:10,730
Huwa biss aktar xogħol.

302
00:14:10,730 --> 00:14:13,930
Għandna bżonn kodiċi simili għal dak I kien
banging out ftit mument ilu.

303
00:14:13,930 --> 00:14:16,120
Doable ħafna, iżda żżid kumplessità.

304
00:14:16,120 --> 00:14:19,520
U hekk time iżviluppatur, programmer
ħin għadu riżorsa ieħor

305
00:14:19,520 --> 00:14:22,520
li nistgħu bżonn li jonfqu
xi żmien biex tikseb karatteristiċi ġodda.

306
00:14:22,520 --> 00:14:24,020
U allura naturalment hemm kju.

307
00:14:24,020 --> 00:14:26,227
Aħna mhux se jmorru fis dan
wieħed b'reqqa.

308
00:14:26,227 --> 00:14:27,560
Imma hija simili ħafna fl-ispirtu.

309
00:14:27,560 --> 00:14:31,220
I jista 'jimplimenta kju, u
operazzjonijiet korrispondenti tagħha,

310
00:14:31,220 --> 00:14:35,660
enqueue jew dequeue, bħal iżżid jew tneħħi,
huwa biss mod fancier ta 'tgħid dan,

311
00:14:35,660 --> 00:14:38,100
enqueue jew dequeue, kif ġej.

312
00:14:38,100 --> 00:14:41,170
I tista 'biss jagħtu lili nnifsi Istituzzjonjijiet
li għal darb'oħra għandu firxa numru, il

313
00:14:41,170 --> 00:14:44,000
li għal darb'oħra għandu daqs,
iżda għaliex għandi issa jeħtieġ

314
00:14:44,000 --> 00:14:46,940
li jżommu rekord ta 'quddiem tal-kju?

315
00:14:46,940 --> 00:14:50,630
I ma kellhomx bżonn tkun taf
quddiem tal munzell tiegħi.

316
00:14:50,630 --> 00:14:53,570
Ukoll, jekk I darb'oħra għal
queue-- ejja biss hard

317
00:14:53,570 --> 00:14:57,870
kodiċi bħala li bħall ħamsa
interi fil hawn potenzjalment.

318
00:14:57,870 --> 00:15:00,940
Allura dan huwa żero, wieħed, tnejn, tlieta, erbgħa.

319
00:15:00,940 --> 00:15:03,430
Dan se jkun
imsejħa numri mill-ġdid.

320
00:15:03,430 --> 00:15:06,940
U dan se tissejjaħ daqs.

321
00:15:06,940 --> 00:15:10,056
>> Għaliex huwa mhux biżżejjed
li għadek daqs?

322
00:15:10,056 --> 00:15:11,680
Well, ejja timbotta dawn l-istess numri fuq.

323
00:15:11,680 --> 00:15:14,220
So I pushed-- I enqueued, jew imbuttat.

324
00:15:14,220 --> 00:15:20,150
Now I ser enqueue 50, u mbagħad
51, u mbagħad 61, u dot dot dot.

325
00:15:20,150 --> 00:15:21,070
Allura dak enqueue.

326
00:15:21,070 --> 00:15:23,176
I enqueued 50, imbagħad 51, imbagħad 61.

327
00:15:23,176 --> 00:15:25,050
U li tidher identika
li munzell s'issa,

328
00:15:25,050 --> 00:15:27,190
ħlief I do għandek bżonn tagħmel bidla waħda.

329
00:15:27,190 --> 00:15:33,680
I bżonn jaġġornaw dan id-daqs, so I go
minn żero għal wieħed li 2-3 issa.

330
00:15:33,680 --> 00:15:35,760
Kif nista dequeue?

331
00:15:35,760 --> 00:15:36,890
X'jiġri ma 'dequeue?

332
00:15:36,890 --> 00:15:41,950
Min għandu come off din il-lista l-ewwel
jekk huwa l-linja fil-Apple Aħżen?

333
00:15:41,950 --> 00:15:42,780
Allura 50.

334
00:15:42,780 --> 00:15:44,700
Allura huwa tip ta delikati dan iż-żmien.

335
00:15:44,700 --> 00:15:47,880
Billi aħħar darba li kien super
faċli biex biss tagħmel wieħed nieqes daqs,

336
00:15:47,880 --> 00:15:51,440
I nikseb l-aħħar tal-firxa tiegħi b'mod effettiv
fejn in-numri huma, tneħħi 61.

337
00:15:51,440 --> 00:15:52,920
Imma jien ma jridux li jitneħħew 61.

338
00:15:52,920 --> 00:15:55,030
I tixtieq li tieħu 50, li
kien hemm fil 05:00

339
00:15:55,030 --> 00:15:56,790
għal-linja up għall-
iPhone jew whatnot ġdid.

340
00:15:56,790 --> 00:16:01,200
U dan biex jeħles ta '50, I
tista 'mhux biss tagħmel dan, id-dritt?

341
00:16:01,200 --> 00:16:02,547
I jistgħu jaqsmu l-50.

342
00:16:02,547 --> 00:16:04,380
Iżda aħna biss qal aħna
ma għandhom ikunu tant anali

343
00:16:04,380 --> 00:16:06,330
kif li tobrox jew jaħbu l-informazzjoni.

344
00:16:06,330 --> 00:16:08,090
Nistgħu biss tinsa fejn hu.

345
00:16:08,090 --> 00:16:12,330
>> Imma jekk jien tibdil fid-daqs tiegħi issa biex
tnejn, huwa dan it-tagħrif biżżejjed

346
00:16:12,330 --> 00:16:15,711
li tkun taf x'inhu għaddej fil-kju tiegħi?

347
00:16:15,711 --> 00:16:16,680
Mhux ezatt.

348
00:16:16,680 --> 00:16:19,830
Bħal daqs tiegħi huwa tnejn, iżda
fejn ma l-kju jibda,

349
00:16:19,830 --> 00:16:22,980
speċjalment jekk I għad għandhom
dawn l-istess numri fil-memorja.

350
00:16:22,980 --> 00:16:24,260
50, 51, 61.

351
00:16:24,260 --> 00:16:27,090
So I bżonn li wieħed jiftakar
issa fejn il-quddiem hu.

352
00:16:27,090 --> 00:16:29,630
U hekk kif ipproponejt up
hemm, aħna ser għadek imsejħa

353
00:16:29,630 --> 00:16:33,729
Quddiem nth, li inizzjali
valur kellu jkun dak?

354
00:16:33,729 --> 00:16:35,270
Żero, biss il-bidu tal-lista.

355
00:16:35,270 --> 00:16:40,876
Imma issa minbarra decrementing
id-daqs, aħna biss inkrement quddiem.

356
00:16:40,876 --> 00:16:42,000
Issa hawn problema oħra.

357
00:16:42,000 --> 00:16:43,030
Allura ladarba I jibqgħu għaddejjin.

358
00:16:43,030 --> 00:16:47,520
Ejja ngħidu dan huwa n-numru ta '
bħal 121, 124, u mbagħad, dammit,

359
00:16:47,520 --> 00:16:48,610
Jien l-ispazju.

360
00:16:48,610 --> 00:16:50,390
Iżda stenna minuta, jien ma.

361
00:16:50,390 --> 00:16:55,630
Allura f'dan il-punt fl-istorja,
jissoponi li d-daqs huwa wieħed, tnejn,

362
00:16:55,630 --> 00:17:00,370
tlieta, erba ', sabiex jissoponi li l-
daqs huwa erba, il-quddiem huwa wieħed,

363
00:17:00,370 --> 00:17:01,621
hekk 51 ikun fuq quddiem.

364
00:17:01,621 --> 00:17:04,329
I tixtieq li tqiegħed numru ieħor hawnhekk,
iżda, dammit, jien l-ispazju.

365
00:17:04,329 --> 00:17:06,710
Imma jien ma verament, right?

366
00:17:06,710 --> 00:17:11,192
Fejn jista I jqajjem xi
valur addizzjonali, bħal 171?

367
00:17:11,192 --> 00:17:13,400
Yeah, I jistgħu biss tip ta '
jmorru lura hemmhekk, id-dritt?

368
00:17:13,400 --> 00:17:18,161
U mbagħad jaqsmu l-50, jew
biss jissostitwixxu bl 171.

369
00:17:18,161 --> 00:17:20,410
U jekk int mintix għaliex
numri tagħna ltqajna hekk każwali,

370
00:17:20,410 --> 00:17:24,150
dawn huma komunement jittieħdu kompjuter
korsijiet tax-xjenza fil-Harvard wara CS50.

371
00:17:24,150 --> 00:17:27,510
Iżda dan kien ottimizzazzjoni tajba,
għaliex issa jien ma ħela ispazju.

372
00:17:27,510 --> 00:17:30,750
I still għandek tiftakar
kemm hu kbir dan il-ħaġa hija totali.

373
00:17:30,750 --> 00:17:31,500
Huwa ħamsa totali.

374
00:17:31,500 --> 00:17:33,375
Minħabba I ma jridux
tibda kitba fuq 51.

375
00:17:33,375 --> 00:17:36,260
Allura issa I am għadhom barra mill-ispazju,
hekk l-istess problema bħal qabel.

376
00:17:36,260 --> 00:17:39,140
Iżda int tista 'tara kif issa
fil-kodiċi tiegħek, inti probabilment

377
00:17:39,140 --> 00:17:41,910
jkollhom jiktbu ftit aktar
kumplessità li naraw li dan iseħħ.

378
00:17:41,910 --> 00:17:44,510
U fil-fatt, dak operatur
fis-C probabbilment tikri

379
00:17:44,510 --> 00:17:48,110
inti magically tagħmel dan il-ċirkolarità?

380
00:17:48,110 --> 00:17:50,160
Yeah l-operatur modulo,
is-sinjal fil-mija.

381
00:17:50,160 --> 00:17:53,160
Allura x'inhu l-tip ta 'kessaħ dwar kju,
anke jekk inżommu tpinġija arrays

382
00:17:53,160 --> 00:17:56,520
kif dawn il-linji dritti simili, jekk inti
tip ta 'jaħsbu dwar dan bħala b'tidwira

383
00:17:56,520 --> 00:18:00,341
madwar bħala ċirku, allura biss
intuwittivament dan it-tip ta jaħdem mentalment

384
00:18:00,341 --> 00:18:01,590
I think ftit aktar nadif.

385
00:18:01,590 --> 00:18:05,190
Inti xorta jkollhom jimplimentaw
dan il-mudell mentali fil-kodiċi.

386
00:18:05,190 --> 00:18:07,550
Allura mhux li iebes,
finalment, biex jimplimentaw,

387
00:18:07,550 --> 00:18:12,430
imma aħna xorta jitilfu l-size-- pjuttost, il-
abbiltà li resize, sakemm nagħmlu dan.

388
00:18:12,430 --> 00:18:15,310
>> Għandna biex jeħles mill-firxa, aħna
tibdilha ma 'pointer waħda,

389
00:18:15,310 --> 00:18:20,010
u mbagħad x'imkien fil-kodiċi tiegħi stajt ltqajna
Sejħa dak jiffunzjonaw li attwalment joħolqu

390
00:18:20,010 --> 00:18:23,720
l-array imsejħa numri?

391
00:18:23,720 --> 00:18:26,190
Malloc, jew xi simili
funzjoni, eżattament.

392
00:18:26,190 --> 00:18:30,481
Kwalunkwe mistoqsijiet dwar stacks jew kjuwijiet.

393
00:18:30,481 --> 00:18:30,980
Yeah?

394
00:18:30,980 --> 00:18:33,657

395
00:18:33,657 --> 00:18:34,240
Tajba kwistjoni.

396
00:18:34,240 --> 00:18:35,830
What modulo would you tuża hawn.

397
00:18:35,830 --> 00:18:38,520
Allura ġenerali, meta jużaw
mod, inti tagħmel dan

398
00:18:38,520 --> 00:18:40,620
mad-daqs tal-
istruttura data sħiħa.

399
00:18:40,620 --> 00:18:44,120
Allura xi ħaġa simili ħamsa jew il-kapaċità, jekk
huwa kostanti, huwa probabbilment involut.

400
00:18:44,120 --> 00:18:47,100
Iżda biss tagħmel modulo ħamsa
probabbilment ma jkunx biżżejjed,

401
00:18:47,100 --> 00:18:51,380
għaliex għandna bżonn inkunu nafu għandna
perimetrika hawn jew hawn jew hawn.

402
00:18:51,380 --> 00:18:54,160
Allura int probabilment wkoll
tmur jridu jinvolvu

403
00:18:54,160 --> 00:18:57,220
id-daqs tal-ħaġa, jew
il-varjabbli quddiem ukoll.

404
00:18:57,220 --> 00:19:00,140
Allura huwa biss dan relattivament
espressjoni aritmetika sempliċi,

405
00:19:00,140 --> 00:19:02,000
iżda modulo tkun l-ingredjent ewlieni.

406
00:19:02,000 --> 00:19:03,330
>> Film tant qasir jekk inti se.

407
00:19:03,330 --> 00:19:05,780
Animazzjoni li xi
folks fil università oħra

408
00:19:05,780 --> 00:19:08,060
jitqiegħdu flimkien li konna
adattati għal din id-diskussjoni.

409
00:19:08,060 --> 00:19:12,630
Dan jinvolvi Jack tagħlim tal-
fatti dwar kjuwijiet u stats.

410
00:19:12,630 --> 00:19:19,010

411
00:19:19,010 --> 00:19:21,890
>> FILM: Darba waħda,
kien hemm Guy msemmija Jack.

412
00:19:21,890 --> 00:19:25,330
Meta ġie biex jagħmlu ħbieb,
Jack ma kellux knack.

413
00:19:25,330 --> 00:19:28,220
Allura Jack marru li tkellem lill-
aktar popolari Guy kien jaf.

414
00:19:28,220 --> 00:19:30,920
Huwa mar Lou u staqsa, What do I do?

415
00:19:30,920 --> 00:19:33,400
Lou raw li l-ħabib tiegħu
kien verament f'diffikultà.

416
00:19:33,400 --> 00:19:36,050
Ukoll, huwa beda, biss
tfittex kif int dressed.

417
00:19:36,050 --> 00:19:38,680
Ma inti xi ħwejjeġ
bil-ħarsa differenti?

418
00:19:38,680 --> 00:19:39,660
Iva, qal Jack.

419
00:19:39,660 --> 00:19:40,840
I żgur do.

420
00:19:40,840 --> 00:19:43,320
Come to my house u
I ser juru lilhom lilek.

421
00:19:43,320 --> 00:19:44,550
Allura dawn marru off għall Jack.

422
00:19:44,550 --> 00:19:47,520
U Jack wera Lou-kaxxa
fejn hu miżmum shirts kollha tiegħu,

423
00:19:47,520 --> 00:19:49,260
u pants tiegħu, u kalzetti tiegħu.

424
00:19:49,260 --> 00:19:52,290
Lou qal, I ara inti għandek
ħwejjeġ kollha tiegħek fil-pile.

425
00:19:52,290 --> 00:19:54,870
Għaliex ma tilbes xi
oħrajn darba awhile?

426
00:19:54,870 --> 00:19:58,020
>> Jack qal, ukoll, meta I
neħħi ħwejjeġ u kalzetti,

427
00:19:58,020 --> 00:20:00,780
I aħsilhom u mqiegħda
bogħod minnhom fil-kaxxa.

428
00:20:00,780 --> 00:20:03,210
Imbagħad jiġi l-li jmiss
filgħodu, u sa I ħops.

429
00:20:03,210 --> 00:20:06,380
I tmur fil-kaxxa u jiksbu
ħwejjeġ tiegħi off-quċċata.

430
00:20:06,380 --> 00:20:09,070
Lou rrealizzaw malajr
il-problema ma Jack.

431
00:20:09,070 --> 00:20:12,080
Hu jinżamm ħwejjeġ, CD,
u kotba fil-munzell.

432
00:20:12,080 --> 00:20:14,420
Meta huwa laħaq għal
xi ħaġa li taqra jew li jilbsu,

433
00:20:14,420 --> 00:20:17,100
huwa d jagħżlu l-ktieb quċċata jew ħwejjeġ ta 'taħt.

434
00:20:17,100 --> 00:20:19,500
Imbagħad meta kien sar, huwa
ipoġġiha dritt lura.

435
00:20:19,500 --> 00:20:21,970
Back dan imur, fuq nett tal-munzell.

436
00:20:21,970 --> 00:20:24,460
Naf li l-soluzzjoni,
qal Loud trijonfanti.

437
00:20:24,460 --> 00:20:27,090
Għandek bżonn biex jitgħallmu biex
tibda tuża kju.

438
00:20:27,090 --> 00:20:29,870
Lou ħa ħwejjeġ Jack u
mdendla minnhom fil-closet.

439
00:20:29,870 --> 00:20:32,710
U meta huwa kien jitbattal
l-kaxxa, hu biss tossed dan.

440
00:20:32,710 --> 00:20:36,500
>> Imbagħad qal, issa Jack, fl-aħħar tal
il-jum, tpoġġi ħwejjeġ tiegħek fuq ix-xellug

441
00:20:36,500 --> 00:20:37,990
meta inti tpoġġi lilhom bogħod.

442
00:20:37,990 --> 00:20:41,300
Imbagħad għada filgħodu meta inti
tara l-xemx, jiksbu ħwejjeġ tiegħek

443
00:20:41,300 --> 00:20:43,440
fuq il-lemin, mill-aħħar tal-linja.

444
00:20:43,440 --> 00:20:44,880
Ma tara? qal Lou.

445
00:20:44,880 --> 00:20:46,370
Se jkun hekk sbieħ.

446
00:20:46,370 --> 00:20:49,770
Int ser ikollok jilbsu kollox ladarba
qabel tilbes xi ħaġa darbtejn.

447
00:20:49,770 --> 00:20:52,670
U ma 'kollox fil-kjuwijiet
fil closet tiegħu u ixkaffa,

448
00:20:52,670 --> 00:20:55,160
Jack bdew iħossu
pjuttost ċert ta lilu nnifsu.

449
00:20:55,160 --> 00:20:59,720
Grazzi għall Lou u
kju isbaħ tiegħu.

450
00:20:59,720 --> 00:21:01,220
SPEAKER 1: Id-dritt, huwa adorable.

451
00:21:01,220 --> 00:21:05,920

452
00:21:05,920 --> 00:21:10,080
Allura dak li ġie verament għaddejjin
fuq minn taħt il-barnuża issa?

453
00:21:10,080 --> 00:21:12,370
Li għandna pointers,
li għandna malloc,

454
00:21:12,370 --> 00:21:15,680
li aħna għandna l-kapaċità li joħolqu
biċċiet ta 'memorja għalina

455
00:21:15,680 --> 00:21:16,344
dinamiku.

456
00:21:16,344 --> 00:21:18,510
Allura dan huwa stampa aħna
glimpsed biss l-oħra jum.

457
00:21:18,510 --> 00:21:21,180
Aħna ma verament nitkellem
fuqha, iżda din l-istampa

458
00:21:21,180 --> 00:21:24,180
ilu għaddej taħt
il-barnuża għal ġimgħat issa.

459
00:21:24,180 --> 00:21:27,050
U għalhekk dan jirrappreżenta, just
rettangolu li konna mfassla,

460
00:21:27,050 --> 00:21:28,180
memorja tal-kompjuter tiegħek.

461
00:21:28,180 --> 00:21:31,850
U forsi kompjuter tiegħek, jew CS50
ID, għandha gigabyte ta 'memorja jew RAM

462
00:21:31,850 --> 00:21:33,050
jew tnejn gigabytes jew erbgħa.

463
00:21:33,050 --> 00:21:34,450
Hija ma verament kwistjoni.

464
00:21:34,450 --> 00:21:37,240
Sistema operattiva tiegħek
Windows jew Mac OS jew Linux,

465
00:21:37,240 --> 00:21:41,120
essenzjalment jippermetti program tiegħek
biex jaħsbu li għandu aċċess

466
00:21:41,120 --> 00:21:42,982
għall-totalità tal
memorja tal-kompjuter tiegħek,

467
00:21:42,982 --> 00:21:45,440
anki jekk inti tista 'tkun qed taħdem
programmi multipli f'daqqa.

468
00:21:45,440 --> 00:21:46,990
Allura fir-realtà, li ma verament jaħdmu.

469
00:21:46,990 --> 00:21:49,448
Iżda huwa tip ta 'illużjoni
mogħtija lill-programmi kollha tiegħek.

470
00:21:49,448 --> 00:21:53,110
Mela jekk kellek żewġ gigs ta 'RAM, dan
huwa kif l-kompjuter tista 'taħseb minnha.

471
00:21:53,110 --> 00:21:57,110
>> Issa inzerta, waħda minn dawn
affarijiet, wieħed minn dawn is-segmenti ta 'memorja,

472
00:21:57,110 --> 00:21:58,350
tissejjaħ munzell.

473
00:21:58,350 --> 00:22:01,680
U fil-fatt kwalunkwe ħin
s'issa bil-miktub kodiċi

474
00:22:01,680 --> 00:22:05,900
li inti sejħu
funzjoni, per eżempju prinċipali.

475
00:22:05,900 --> 00:22:08,410
Ifakkar li kull darba stajt
memorja mfassla s kompjuter,

476
00:22:08,410 --> 00:22:10,640
Jien dejjem tiġbed tip ta '
nofs ta 'rettangolu hawn

477
00:22:10,640 --> 00:22:12,520
u ma jolqot jitkellem
dwar x'hemm fuq.

478
00:22:12,520 --> 00:22:15,980
Għaliex meta prinċipali huwa msejjaħ, I jitolbu
li inti tikseb dan sliver ta 'memorja

479
00:22:15,980 --> 00:22:16,970
li jinżel hawn.

480
00:22:16,970 --> 00:22:20,650
U jekk ewlenija imsejħa funzjoni
bħal tpartit, sew swap tmur hawn.

481
00:22:20,650 --> 00:22:23,720
U jirriżulta, li l-
fejn huwa jispiċċa.

482
00:22:23,720 --> 00:22:26,277
Fuq xi ħaġa imsejħa 'ċumnija
ġewwa tal-memorja tal-kompjuter tiegħek.

483
00:22:26,277 --> 00:22:28,360
Issa fl-aħħar tal-ġurnata,
dan huwa biss tindirizza.

484
00:22:28,360 --> 00:22:30,680
Huwa simili byte żero,
byte wieħed, byte 2 biljuni.

485
00:22:30,680 --> 00:22:33,130
Imma jekk inti taħseb dwarha
kif dan l-oġġett rettangolari,

486
00:22:33,130 --> 00:22:35,130
kollha li aħna qed tagħmel kull
ħin nitolbu funzjoni hija

487
00:22:35,130 --> 00:22:37,180
saffi porzjon ġdid ta 'memorja.

488
00:22:37,180 --> 00:22:41,700
Aħna qed tagħti dik il-funzjoni porzjon
tal-memorja tagħha stess biex jaħdmu ma '.

489
00:22:41,700 --> 00:22:44,490
>> U tfakkar issa li dan huwa importanti.

490
00:22:44,490 --> 00:22:46,400
Għaliex jekk aħna għandna
xi ħaġa bħal tpartit

491
00:22:46,400 --> 00:22:51,610
u żewġ varjabbli lokali bħall A u B u
nagħmlu l-bidla dawk il-valuri minn wieħed u tnejn

492
00:22:51,610 --> 00:22:55,130
għal żewġ u wieħed, irtirar
li meta swap jirritorna,

493
00:22:55,130 --> 00:22:58,330
huwa bħallikieku dan porzjon
tal-memorja huwa biss marret.

494
00:22:58,330 --> 00:23:00,080
Fir-realtà, huwa għadu
hemm forensically.

495
00:23:00,080 --> 00:23:01,940
U xi ħaġa għadu attwalment hemm.

496
00:23:01,940 --> 00:23:05,410
Iżda kunċettwali, huwa daqs li
għalkemm huwa kompletament marret.

497
00:23:05,410 --> 00:23:10,910
U hekk prinċipali ma jafx xi waħda minn dawn xogħol
li sar f'dik il-funzjoni tpartit,

498
00:23:10,910 --> 00:23:14,890
sakemm huwa attwalment mgħoddija f'dawk
argumenti mid pointer jew b'referenza.

499
00:23:14,890 --> 00:23:17,790
Issa, is-soluzzjoni fundamentali
biex din il-problema ma 'swap

500
00:23:17,790 --> 00:23:19,970
hija tgħaddi affarijiet fil mill-indirizz.

501
00:23:19,970 --> 00:23:23,250
Iżda jirriżulta, wisq, x'hemm
ilu għaddej hawn fuq dik il-parti

502
00:23:23,250 --> 00:23:26,330
tar-rettangolu dan il-ħin huwa
iżda hemm aktar memorja up hemm.

503
00:23:26,330 --> 00:23:28,790
U meta inti dinamikament
jalloka memorja,

504
00:23:28,790 --> 00:23:32,020
jekk huwa ġewwa tal GetString, li
aħna kont qed tagħmel għalik fil-CS50

505
00:23:32,020 --> 00:23:34,710
librerija, jew jekk inti guys
sejħa malloc u jistaqsi

506
00:23:34,710 --> 00:23:37,950
is-sistema operattiva għal blokki ta '
memorja, dan ma jaqax mill-munzell.

507
00:23:37,950 --> 00:23:40,960
Jidħol minn post ieħor
fil-memorja tal-kompjuter tiegħek

508
00:23:40,960 --> 00:23:42,220
li sejjaħ-borġ.

509
00:23:42,220 --> 00:23:43,430
U li mhux xi differenti.

510
00:23:43,430 --> 00:23:44,285
Huwa l-istess RAM.

511
00:23:44,285 --> 00:23:45,160
Huwa l-istess memorja.

512
00:23:45,160 --> 00:23:49,080
Huwa biss l-RAM li f'idejn
hemm minflok stabbiliti hawn.

513
00:23:49,080 --> 00:23:50,750
>> U hekk xi jfisser?

514
00:23:50,750 --> 00:23:53,650
Ukoll, jekk il-kompjuter tiegħek
ammont finit ta 'memorja

515
00:23:53,650 --> 00:23:57,450
u l-munzell hu jikbru, hekk
biex jitkellmu, u l-borġ, skond

516
00:23:57,450 --> 00:23:59,349
għal dan vleġġa, qed jikber l isfel.

517
00:23:59,349 --> 00:24:01,140
Fi kliem ieħor, kull
darba li inti sejħa malloc,

518
00:24:01,140 --> 00:24:03,430
int qed jingħataw porzjon
tal-memorja minn fuq,

519
00:24:03,430 --> 00:24:06,630
allura forsi ftit aktar baxxa, imbagħad ftit
aktar baxxi, kull darba li inti sejħa malloc,

520
00:24:06,630 --> 00:24:10,100
-borġ, huwa l-użu,
qed tip ta 'tkabbir,

521
00:24:10,100 --> 00:24:11,950
jikber eqreb u eqreb lejn xiex?

522
00:24:11,950 --> 00:24:13,382
Il-munzell.

523
00:24:13,382 --> 00:24:14,840
Allura ma dan jidher bħala idea tajba?

524
00:24:14,840 --> 00:24:18,420

525
00:24:18,420 --> 00:24:22,140
I mean, fejn mhuwiex verament ċara
dak li inkella tista 'tagħmel jekk inti biss

526
00:24:22,140 --> 00:24:23,910
jkollhom ammont finit ta 'memorja.

527
00:24:23,910 --> 00:24:25,200
Iżda dan huwa żgur ħażin.

528
00:24:25,200 --> 00:24:27,920
Dawn iż-żewġ vleġeġ huma fuq
crash kors għal xulxin.

529
00:24:27,920 --> 00:24:31,930
>> U jirriżulta li Guy ħażina, folks li
huma partikolarment tajba mal-programmazzjoni,

530
00:24:31,930 --> 00:24:36,140
u jippruvaw Hack fil-kompjuters,
jistgħu jisfruttaw din ir-realtà.

531
00:24:36,140 --> 00:24:38,290
Fil-fatt, ejja jikkunsidraw
snippet ftit.

532
00:24:38,290 --> 00:24:41,350
Allura dan huwa eżempju inti tista 'taqra
dwar f'aktar dettall fuq il-Wikipedija.

533
00:24:41,350 --> 00:24:43,100
Aħna ser punt inti fil-
artikolu jekk kurjużi.

534
00:24:43,100 --> 00:24:45,650
Iżda hemm xi attakk ġeneralment
magħrufa bħala overflow buffer li

535
00:24:45,650 --> 00:24:49,570
ilha teżisti sakemm bnedmin
kellhom il-ħila biex jimmanipulaw

536
00:24:49,570 --> 00:24:53,120
memorja tal-kompjuter, speċjalment fil C.
Allura dan huwa programm arbitrarja ħafna,

537
00:24:53,120 --> 00:24:55,130
imma ejja taqrah mill-qiegħ up.

538
00:24:55,130 --> 00:24:57,650
Main fis star char argC ARGV.

539
00:24:57,650 --> 00:24:59,830
Allura huwa programm li jieħu
argumenti kmand linja.

540
00:24:59,830 --> 00:25:03,620
U kollha prinċipali ma jidher li huwa call
funzjoni, sejħa hija F għas-sempliċità.

541
00:25:03,620 --> 00:25:04,610
U tgħaddi fil xiex?

542
00:25:04,610 --> 00:25:05,490
ARGV ta 'wieħed.

543
00:25:05,490 --> 00:25:09,320
Għalhekk jgħaddi fil F x'ikun
il-kelma hija li l-utent ittajpjat

544
00:25:09,320 --> 00:25:11,500
fil-pront wara l-
isem tal-programm fil-livelli kollha.

545
00:25:11,500 --> 00:25:15,730
Tant simili Caesar jew Vigenere, li
inti tista 'recall tagħmel ma' ARGV.

546
00:25:15,730 --> 00:25:16,680
>> Allura x'inhi l F?

547
00:25:16,680 --> 00:25:19,760
F ittieħdet fi string
kif argument unika tiegħu,

548
00:25:19,760 --> 00:25:22,100
AKA stilla char, l-istess
ħaġa, bħala sekwenza.

549
00:25:22,100 --> 00:25:24,920
U huwa msejjaħ arbitrarju
bar f'dan l-eżempju.

550
00:25:24,920 --> 00:25:27,710
U imbagħad xawwat c 12,
biss f'termini laymans,

551
00:25:27,710 --> 00:25:31,750
dak li huwa char c parentesi 12 tagħmel għalina?

552
00:25:31,750 --> 00:25:33,440
X'hemm do?

553
00:25:33,440 --> 00:25:36,490
Allokazzjoni memorja, speċifikament
12 bytes għal 12 Chars.

554
00:25:36,490 --> 00:25:36,990
Eżattament.

555
00:25:36,990 --> 00:25:40,000
U allura l-aħħar linja, ħawwad u
kopja, inti ħadthom probabbilment ma bbenefikawx.

556
00:25:40,000 --> 00:25:43,360
Din hija kopja string
funzjoni li l-għan fil-ħajja

557
00:25:43,360 --> 00:25:48,160
huwa li kopja tieni argument tagħha
fis-ewwel argument tagħha,

558
00:25:48,160 --> 00:25:51,190
iżda biss sa
Ċertu numru ta 'bytes.

559
00:25:51,190 --> 00:25:53,860
Allura l-tielet argument jgħid,
kemm bytes għandek kopja?

560
00:25:53,860 --> 00:25:56,720
It-tul ta 'bar,
ikun x'ikun l-utent ittajpjat fil.

561
00:25:56,720 --> 00:25:59,320
U l-kontenut ta '
bar, li string, huma

562
00:25:59,320 --> 00:26:02,330
ikkopjata fil-memorja osservat f'mill C.

563
00:26:02,330 --> 00:26:04,060
>> Allura dan jidher tip ta 'stupid, u huwa.

564
00:26:04,060 --> 00:26:06,300
Dan huwa eżempju artifiċjali,
imma hija rappreżentattiva

565
00:26:06,300 --> 00:26:10,100
ta 'klassi ta' vetturi attakk,
mod ta 'jattakkaw programm.

566
00:26:10,100 --> 00:26:15,050
Kollox huwa multa u tajba jekk l-utent
tipi Fi ftit kliem li l-11-karattri

567
00:26:15,050 --> 00:26:18,040
jew inqas, flimkien mal-backslash żero.

568
00:26:18,040 --> 00:26:22,830
X'jiġri jekk it-tipi utent f'aktar minn
11 jew 12 jew 20 jew 50 karattru?

569
00:26:22,830 --> 00:26:25,090
X'hemm dan il-programm se jagħmlu?

570
00:26:25,090 --> 00:26:29,360
Tort Potenzjalment SEG. Huwa ser
li bl-addoċċ kopja kollox bar up

571
00:26:29,360 --> 00:26:31,750
t-tul tiegħu, li huwa
litteralment kollox fil-bar,

572
00:26:31,750 --> 00:26:36,307
fil-indirizz indikat fil C. Iżda C
għandha biss preemptively mogħti bħala 12 bytes.

573
00:26:36,307 --> 00:26:37,640
Iżda hemm ebda verifika addizzjonali.

574
00:26:37,640 --> 00:26:38,700
M'hemm l-ebda jekk il-kondizzjonijiet.

575
00:26:38,700 --> 00:26:40,580
M'hemm l-ebda żball iċċekkjar hawn.

576
00:26:40,580 --> 00:26:43,270
>> U iva, liema dan il-programm huwa
se tagħmel huwa biss bl-addoċċ

577
00:26:43,270 --> 00:26:45,750
kopja ħaġa waħda għall-oħra.

578
00:26:45,750 --> 00:26:47,880
U hekk jekk aħna tiġbed
bħala stampa, hawn

579
00:26:47,880 --> 00:26:49,860
biss sliver ta 'l-ispazju memorja.

580
00:26:49,860 --> 00:26:53,470
Allura avviż fil-qiegħ, aħna
għandhom il-bar varjabbli lokali.

581
00:26:53,470 --> 00:26:57,330
Allura li pointer li għaddej biex store--
pjuttost li argument lokali li l-

582
00:26:57,330 --> 00:26:58,672
ser taħżen l-bar sekwenza.

583
00:26:58,672 --> 00:27:00,380
U mbagħad avviż biss
fuq minnu fix munzell,

584
00:27:00,380 --> 00:27:02,505
għaliex kull darba li inti ssaqsi
għall-memorja fuq il-munzell,

585
00:27:02,505 --> 00:27:04,310
din tmur ftit
hawn fuq pictorially,

586
00:27:04,310 --> 00:27:06,270
avviż li konna ltqajna 12 bytes hemmhekk.

587
00:27:06,270 --> 00:27:10,690
Il-wieħed fuq tax-xellug huwa C parentesi żero u
l-waħda qiegħ dritt huwa Ċ parentesi 11.

588
00:27:10,690 --> 00:27:12,870
Li jinsab biss kif il-kompjuters
ser jistabbilixxu dan jitwettaq.

589
00:27:12,870 --> 00:27:18,300
Hekk biss intuwittivament, jekk bar għandha aktar
minn 12 karattri fit-total, inklużi

590
00:27:18,300 --> 00:27:25,790
l-backslash żero, fejn huwa l-
12 jew il-kategorija C 12 se jmorru?

591
00:27:25,790 --> 00:27:28,440
Jew pjuttost fejn huwa l-12
karattru jew il-karattru 13,

592
00:27:28,440 --> 00:27:30,900
il-karattru mija jmorru
li jispiċċaw fl-istampa?

593
00:27:30,900 --> 00:27:33,400
Fuq jew taħt?

594
00:27:33,400 --> 00:27:36,300
>> Dritt, għaliex anki jekk
il-munzell innifsu tikber fuq,

595
00:27:36,300 --> 00:27:39,590
ladarba inti ħadthom tpoġġi Jittieħed fil
dan, għal raġunijiet tad-disinn,

596
00:27:39,590 --> 00:27:41,294
ipoġġi l-memorja minn fuq għal isfel.

597
00:27:41,294 --> 00:27:44,460
Mela jekk inti ħadthom ltqajna aktar minn 12 bytes,
int ser tibda biex jissostitwixxu bar.

598
00:27:44,460 --> 00:27:47,280
Issa li l-bug, imma hija
mhux verament big deal.

599
00:27:47,280 --> 00:27:51,130
Iżda huwa big deal, għaliex hemm
Jittieħed aktar għaddejjin fil-memorja.

600
00:27:51,130 --> 00:27:53,074
Allura hawnhekk kif nistgħu
jitqiegħdu hello, li huma ċari.

601
00:27:53,074 --> 00:27:54,490
Jekk I ittajpjat fil bonjour fil-prompt.

602
00:27:54,490 --> 00:27:59,330
Backslash zero H-E-L-L-O, jispiċċa fil
dawk 12 bytes, u aħna qed super sikur.

603
00:27:59,330 --> 00:28:00,330
Kollox huwa tajjeb.

604
00:28:00,330 --> 00:28:03,020
Imma jekk jien xi ħaġa tip
itwal, potenzjalment huwa

605
00:28:03,020 --> 00:28:05,860
ser creep fl-ispazju bar.

606
00:28:05,860 --> 00:28:08,405
Iżda agħar għadu, jirriżulta
out dan il-ħin,

607
00:28:08,405 --> 00:28:11,530
anke jekk aħna qatt ma stajt tkellem dwar
dan, il-munzell huwa użat għall-għalf oħra.

608
00:28:11,530 --> 00:28:13,560
Huwa mhux biss varjabbli lokali.

609
00:28:13,560 --> 00:28:15,100
>> C hija lingwa f'livell baxx ħafna.

610
00:28:15,100 --> 00:28:17,810
U tip ta 'segretament
juża l-munzell wkoll

611
00:28:17,810 --> 00:28:21,260
li tiftakar meta
funzjoni hija magħrufa, liema

612
00:28:21,260 --> 00:28:26,040
l-indirizz huwa tal-funzjoni ta 'qabel,
sabiex ikun jista 'tiżdied lura għal dik il-funzjoni.

613
00:28:26,040 --> 00:28:29,980
Allura meta sejħiet ewlenin tpartit, fost
l-affarijiet imbuttat fuq il-munzell

614
00:28:29,980 --> 00:28:34,380
huma mhux biss swaps varjabbli lokali,
jew argumenti tagħha, wkoll segretament imbuttat

615
00:28:34,380 --> 00:28:37,510
fuq il-munzell kif rappreżentat
billi dak il-porzjon aħmar hawn,

616
00:28:37,510 --> 00:28:40,520
huwa l-indirizz ta 'prinċipali fiżikament
fil-memorja tal-kompjuter tiegħek,

617
00:28:40,520 --> 00:28:44,180
b'tali mod li meta swap isir, il-kompjuter
jaf I bżonn li jmorru lura għal main

618
00:28:44,180 --> 00:28:46,760
u finitura jesegwixxi l-funzjoni prinċipali.

619
00:28:46,760 --> 00:28:51,960
Allura dan huwa perikoluż issa, għaliex jekk
it-tipi utent fil ukoll aktar minn bonjour,

620
00:28:51,960 --> 00:28:57,030
tali li l-input l-utent clobbers
jew overwrites dik is-sezzjoni aħmar,

621
00:28:57,030 --> 00:28:59,820
loġikament jekk il-kompjuter
biss ser bl-addoċċ jassumi

622
00:28:59,820 --> 00:29:03,830
li l-bytes f'dak porzjon aħmar huma
l-indirizz fejn għandu jirritorna,

623
00:29:03,830 --> 00:29:09,020
X'jiġri jekk l-avversarju huwa intelliġenti biżżejjed jew
xortik tajba biżżejjed li jitqiegħed sekwenza ta 'bytes

624
00:29:09,020 --> 00:29:13,450
hemmhekk li tidher bħal indirizz,
imma hija l-indirizz tal-kodiċi

625
00:29:13,450 --> 00:29:18,730
li hu jew hi trid il-kompjuter
li jesegwixxi minflok prinċipali?

626
00:29:18,730 --> 00:29:21,670
>> Fi kliem ieħor, jekk dak il-
utent huwa ittajpjar fil-pront,

627
00:29:21,670 --> 00:29:23,850
mhix biss xi ħaġa
bħal innokwa hello,

628
00:29:23,850 --> 00:29:28,210
iżda huwa attwalment kodiċi li s ekwivalenti
li jitħassar fajls kollha din utent?

629
00:29:28,210 --> 00:29:30,060
Jew email password tagħhom lili?

630
00:29:30,060 --> 00:29:31,940
Jew jibdew qtugħ tagħhom
keystrokes, id-dritt?

631
00:29:31,940 --> 00:29:34,920
Hemm mod, ejja jistipulaw llum,
li dawn jistgħu tip fil mhux biss bonjour

632
00:29:34,920 --> 00:29:36,711
dinja jew l-isem tagħhom,
dawn jistgħu essenzjalment

633
00:29:36,711 --> 00:29:39,570
jgħaddu bi kodiċi, żerijiet u
dawk, li l-kompjuter

634
00:29:39,570 --> 00:29:43,450
żbalji kemm għall-kodiċi u l-indirizz.

635
00:29:43,450 --> 00:29:48,950
Allura għalkemm kemmxejn astratt, jekk il-
tipi utent fil-kodiċi tal-kontradittorju biżżejjed

636
00:29:48,950 --> 00:29:52,330
li aħna ser tiġġeneralizza hawn bħala
A. A hija attakk jew avversarji.

637
00:29:52,330 --> 00:29:53,140
Jittieħed hekk biss ħżiena.

638
00:29:53,140 --> 00:29:55,306
Aħna ma jimpurtahom dwar il-
numri jew l-żerijiet jew dawk

639
00:29:55,306 --> 00:29:59,470
illum, b'tali mod li inti tispiċċa
kitba fuq dik it-taqsima aħmar,

640
00:29:59,470 --> 00:30:01,580
avviż li sekwenza ta 'bytes.

641
00:30:01,580 --> 00:30:05,020
O 835 C żero tmienja żero.

642
00:30:05,020 --> 00:30:08,960
U issa kif artikolu Wikipedija hawn
ippropona, jekk inti issa attwalment tibda

643
00:30:08,960 --> 00:30:12,460
ittikkettjar tal-bytes fil-kompjuter tiegħek
memorja, dak l-artikolu Wikipedia huwa

644
00:30:12,460 --> 00:30:19,060
tipproponi tkun li, dak jekk l-indirizz
ta 'dak byte fuq tax-xellug huwa 80 C 0 3508.

645
00:30:19,060 --> 00:30:22,200
>> Fi kliem ieħor, jekk il-Guy ħażina hija
intelliġenti biżżejjed bil-kodiċi tiegħu jew tagħha

646
00:30:22,200 --> 00:30:26,650
li fil-fatt imqiegħda numru hawnhekk li
jikkorrispondi għall-indirizz tal-kodiċi

647
00:30:26,650 --> 00:30:29,180
hu jew hi injettata
fil-kompjuter, inti

648
00:30:29,180 --> 00:30:31,050
jista trick il-kompjuter
fis tagħmel xejn.

649
00:30:31,050 --> 00:30:34,140
It-tneħħija fajls, email
affarijiet, xamm traffiku tiegħek,

650
00:30:34,140 --> 00:30:36,710
litteralment xejn jista 'jkun
injettat fil-kompjuter.

651
00:30:36,710 --> 00:30:39,220
U għalhekk overflow buffer
attakk fil-qalba tagħha

652
00:30:39,220 --> 00:30:43,530
huwa biss stupid, stupid
prevalenti ta 'firxa li

653
00:30:43,530 --> 00:30:45,840
ma kellux konfini tagħha ċċekkjati.

654
00:30:45,840 --> 00:30:48,850
U dan huwa dak li huwa super perikoluż
u simultanjament super qawwija

655
00:30:48,850 --> 00:30:52,560
fis-C hija li aħna tabilħaqq għandhom
aċċess għall kullimkien fil-memorja.

656
00:30:52,560 --> 00:30:55,320
Huwa f'idejn lilna, il-programmers,
li jiktbu l-kodiċi oriġinali

657
00:30:55,320 --> 00:30:59,330
biex jiċċekkja l-tul darn ta 'kwalunkwe
arrays li aħna qed manipulazzjoni.

658
00:30:59,330 --> 00:31:00,750
Allura biex tkun ċara, x'inhu l-jiffissaw?

659
00:31:00,750 --> 00:31:03,190
Jekk aħna roll lura għal din
kodiċi, I m'għandhomx biss

660
00:31:03,190 --> 00:31:08,000
jibdlu t-tul ta 'bar, dak
inkella għandi jiġi verifikat?

661
00:31:08,000 --> 00:31:10,620
X'iktar għandi tkun qiegħda tagħmel biex
jipprevjenu dan l-attakk kollox?

662
00:31:10,620 --> 00:31:14,110
Ma rridx li biss bl-addoċċ jgħidu
li inti għandek kopja kif ħafna bytes

663
00:31:14,110 --> 00:31:16,140
kif huwa t-tul ta 'bar.

664
00:31:16,140 --> 00:31:18,910
Irrid ngħid, kopja kif
ħafna bytes kif huma bar

665
00:31:18,910 --> 00:31:24,090
sal-allokati
memorja, jew 12 maximally.

666
00:31:24,090 --> 00:31:27,450
So I bżonn xi tip ta 'jekk il-kundizzjoni
li ma tivverifika t-tul ta 'bar,

667
00:31:27,450 --> 00:31:32,800
imma jekk dan jaqbeż 12, aħna kodiċi biss hard
12 bħala l-akbar distanza possibbli.

668
00:31:32,800 --> 00:31:35,910
Inkella l-buffer hekk imsejħa
attakk overflow jista 'jiġri.

669
00:31:35,910 --> 00:31:38,451
Fil-qiegħ ta 'dawk slajds,
jekk int kurjużi biex taqra aktar

670
00:31:38,451 --> 00:31:41,200
huwa l-artikolu oriġinali attwali
jekk inti tixtieq li tagħti ħarsa.

671
00:31:41,200 --> 00:31:44,550
>> Imma issa, fost l-prezzijiet
mħallsa hawn kien ineffiċjenzi.

672
00:31:44,550 --> 00:31:46,680
Allura li kien malajr
Ħarsa livell baxx lejn dak

673
00:31:46,680 --> 00:31:49,709
problemi jistgħu jinqalgħu issa li aħna
ikollhom aċċess għall-memorja tal-kompjuter.

674
00:31:49,709 --> 00:31:51,750
Iżda problema oħra aħna
diġà stumbled fuq it-tnejn

675
00:31:51,750 --> 00:31:53,800
kien biss il-ineffiċjenza
ta 'lista marbuta.

676
00:31:53,800 --> 00:31:56,019
Aħna lura għal żmien lineari.

677
00:31:56,019 --> 00:31:57,560
Aħna m'għadx għandhom firxa kontigwi.

678
00:31:57,560 --> 00:31:58,980
Aħna ma jkollhom aċċess bl-addoċċ.

679
00:31:58,980 --> 00:32:00,710
Aħna ma tistax tuża notazzjoni parentesi kwadri.

680
00:32:00,710 --> 00:32:04,590
Aħna litteralment jkollu juża loop filwaqt
bħal dak I kiteb mument ilu.

681
00:32:04,590 --> 00:32:09,740
Iżda nhar it-Tnejn, aħna qal li nistgħu
creep lura fil-isfera ta 'effiċjenza

682
00:32:09,740 --> 00:32:13,040
kisba xi ħaġa li
logaritmika forsi, jew aħjar għadhom,

683
00:32:13,040 --> 00:32:16,120
forsi anki xi ħaġa li
hekk imsejħa time kostanti.

684
00:32:16,120 --> 00:32:19,840
Allura kif nistgħu nagħmlu dan billi jużaw dawn ġdida
għodod, dawn l-indirizzi, dawn pointers,

685
00:32:19,840 --> 00:32:22,210
u kamini affarijiet ta 'tagħna stess?

686
00:32:22,210 --> 00:32:23,960
Ukoll, ejja ngħidu li
hawn, dawn huma mazz

687
00:32:23,960 --> 00:32:27,170
ta 'numri li rridu li jaħżen fil-
istruttura tad-data u tfittxija effiċjenti.

688
00:32:27,170 --> 00:32:30,960
Aħna assolutament jistgħu Rewind għal ġimgħa
tnejn, tarmi dawn fi firxa,

689
00:32:30,960 --> 00:32:33,150
u tfittxija billi jużaw search binarja.

690
00:32:33,150 --> 00:32:34,040
Iddividi u conquer.

691
00:32:34,040 --> 00:32:37,720
U fil-fatt li kiteb
tfittxija binarju fil PSET3,

692
00:32:37,720 --> 00:32:40,100
fejn inti implimentax il-programm isibu.

693
00:32:40,100 --> 00:32:40,890
Imma inti taf liema.

694
00:32:40,890 --> 00:32:45,060
Hemm tip ta 'aktar
mod għaqlija li jagħmlu dan.

695
00:32:45,060 --> 00:32:47,390
Huwa ftit aktar
sofistikati u forsi

696
00:32:47,390 --> 00:32:50,830
jippermetti li tara għaliex binarju
tfittxija hija tant malajr.

697
00:32:50,830 --> 00:32:52,980
L-ewwel, ejja jintroduċu
il-kunċett ta 'siġra.

698
00:32:52,980 --> 00:32:54,730
Li anki jekk fil
siġar realtà tip ta '

699
00:32:54,730 --> 00:32:57,730
jikbru bħal dan, fid-dinja tal-kompjuter
xjenza huma tip ta 'jikbru isfel

700
00:32:57,730 --> 00:33:00,830
bħal siġra tal-familja, fejn inti għandek
nanniet tiegħek jew in-nanniet kbira

701
00:33:00,830 --> 00:33:04,580
jew whatnot fil-quċċata, il-patrijarka u
l-matriarch tal-familja, biss wieħed

702
00:33:04,580 --> 00:33:07,930
hekk imsejħa għeruq, node, hawn taħt
li huma tfal tagħha,

703
00:33:07,930 --> 00:33:11,442
hawn taħt li huma tfal tagħha, jew
dixxendenti tiegħu b'mod aktar ġenerali.

704
00:33:11,442 --> 00:33:13,400
U ħadd mdendlin off
l-qiegħ tal-familja

705
00:33:13,400 --> 00:33:16,070
siġra, minbarra li l-
iżgħar fil-familja,

706
00:33:16,070 --> 00:33:19,520
jista 'wkoll jkun biss ġenerikament
imsejjaħ il-weraq tas-siġra.

707
00:33:19,520 --> 00:33:21,800
>> Allura dan huwa biss mazz
ta 'kliem u definizzjonijiet

708
00:33:21,800 --> 00:33:25,790
għal xi ħaġa imsejħa siġra fil-kompjuter
xjenza, ħafna bħal siġra tal-familja.

709
00:33:25,790 --> 00:33:28,770
Iżda hemm incarnations fancier
ta 'siġar, li waħda minnhom

710
00:33:28,770 --> 00:33:30,780
jissejjaħ siġra tfittxija binarju.

711
00:33:30,780 --> 00:33:34,380
U inti tista 'tip ta' tease
apparti dak dan ħaġa ma.

712
00:33:34,380 --> 00:33:37,180
Ukoll, huwa binarju fis F'liema sens?

713
00:33:37,180 --> 00:33:41,455
Fejn ma l-binarju jiġu minn hawn?

714
00:33:41,455 --> 00:33:41,955
Jiddispjacini?

715
00:33:41,955 --> 00:33:45,961

716
00:33:45,961 --> 00:33:47,210
Huwa mhux tant l waħda jew.

717
00:33:47,210 --> 00:33:52,000
Huwa aktar li kull wieħed mill-lymph m'għandha l-ebda
aktar minn żewġt itfal, kif naraw hawn.

718
00:33:52,000 --> 00:33:54,990
B'mod ġenerali, tree-- u
ġenituri tiegħek u nanniet

719
00:33:54,990 --> 00:33:57,640
jista 'jkollhom bħala ħafna tfal jew
grandkids kif huma attwalment jixtiequ,

720
00:33:57,640 --> 00:34:00,820
u għalhekk per eżempju hemm għandna tliet
tfal off li node lemin,

721
00:34:00,820 --> 00:34:05,480
iżda fil-siġra binarju, node għandha
żero, wieħed, jew żewġt itfal maximally.

722
00:34:05,480 --> 00:34:08,496
U li l-proprjetà sbieħ,
għaliex jekk huwa mgħotti b tnejn,

723
00:34:08,496 --> 00:34:10,620
aħna qed tmur biex tkun tista '
jiksbu log bażi ftit tnejn

724
00:34:10,620 --> 00:34:11,975
azzjoni għaddejjin hawn finalment.

725
00:34:11,975 --> 00:34:13,350
Allura aħna għandna xi ħaġa logaritmika.

726
00:34:13,350 --> 00:34:14,558
Iżda aktar fuq li fil-mument.

727
00:34:14,558 --> 00:34:19,810
Fittex siġra ifisser li n-numri huma
rranġati b'tali mod li l-wild xellug

728
00:34:19,810 --> 00:34:22,429
valur huwa akbar mill-għerq.

729
00:34:22,429 --> 00:34:26,010
U tat-tfal id-dritt tagħha huwa
akbar mill-għerq.

730
00:34:26,010 --> 00:34:29,290
Fi kliem ieħor, jekk inti tieħu xi waħda minn dawn
lymph,-ċrieki fil din l-istampa,

731
00:34:29,290 --> 00:34:31,840
u tħares lejn xellug tagħha
tfal u tat-tfal dritt tiegħu,

732
00:34:31,840 --> 00:34:34,739
l-ewwel għandu jkun inqas minn,
it-tieni għandu jkun akbar minn.

733
00:34:34,739 --> 00:34:36,159
Allura sanità jiċċekkjaw 55.

734
00:34:36,159 --> 00:34:37,780
Huwa ħalla tfal 33.

735
00:34:37,780 --> 00:34:38,620
Huwa inqas minn.

736
00:34:38,620 --> 00:34:40,929
55, tfal id-dritt tagħha huwa 77.

737
00:34:40,929 --> 00:34:41,783
Huwa akbar minn.

738
00:34:41,783 --> 00:34:43,199
U li definizzjoni rikursivi.

739
00:34:43,199 --> 00:34:46,480
Nistgħu jivverifikaw kull wieħed minn dawk
lymph u l-istess mudell kien iżomm.

740
00:34:46,480 --> 00:34:49,389
>> Allura x'hemm sbieħ fil-
siġra tfittxija binarju, huwa

741
00:34:49,389 --> 00:34:52,204
li wieħed, nistgħu jimplimentawha
bil-Struct, bħad dan.

742
00:34:52,204 --> 00:34:54,620
U anki jekk aħna qed jitfg
lottijiet ta 'strutturi f'livell tiegħek,

743
00:34:54,620 --> 00:34:56,560
dawn qed pjuttost
intuwittivi issa nisperaw.

744
00:34:56,560 --> 00:35:00,570
Is-sintassi għadu arcane ċerta,
iżda l-kontenut ta 'node f'dan

745
00:35:00,570 --> 00:35:02,786
context-- u nżommu
jużaw il-node kelma,

746
00:35:02,786 --> 00:35:04,910
jekk huwa rettangolu
fuq l-iskrin jew ċirku,

747
00:35:04,910 --> 00:35:08,970
huwa biss ftit kontenitur ġenerika,
f'dan il-każ ta 'siġra, bħal dak

748
00:35:08,970 --> 00:35:11,780
rajna, għandna bżonn integer
f'kull wieħed mill-lymph

749
00:35:11,780 --> 00:35:15,460
u mbagħad I bżonn żewġ pointers tipponta
għat-tarbija xellug u l-wild dritt,

750
00:35:15,460 --> 00:35:16,590
rispettivament.

751
00:35:16,590 --> 00:35:20,730
Allura li kif nistgħu
jimplimentaw dik fil-Struct.

752
00:35:20,730 --> 00:35:22,315
U kif tista I timplimentah fil-kodiċi?

753
00:35:22,315 --> 00:35:26,730
Well, ejja tagħti quick
ħarsa lejn dan l-eżempju ċkejkna.

754
00:35:26,730 --> 00:35:29,820
Mhuwiex funzjonali, imma stajt
kkupjati u pasted dik l-istruttura.

755
00:35:29,820 --> 00:35:33,510
U jekk il-funzjoni tiegħi għal binarja
siġra tfittxija tissejjaħ tfittxija,

756
00:35:33,510 --> 00:35:36,980
u dan jieħu żewġ argumenti,
integer N u werrej li

757
00:35:36,980 --> 00:35:41,400
għal node, so a pointer għall-siġra
jew pointer l-għerq ta 'siġra,

758
00:35:41,400 --> 00:35:43,482
kif nista tmur dwar tiftix għal N?

759
00:35:43,482 --> 00:35:45,440
Ukoll, l-ewwel, għaliex jien
jittrattaw pointers,

760
00:35:45,440 --> 00:35:46,750
Jien ser tagħmel verifika sanità.

761
00:35:46,750 --> 00:35:54,279
Jekk ugwali siġra ugwali null, hija N
f'dan siġra jew le f'dan il-siġra?

762
00:35:54,279 --> 00:35:55,070
Ma jistax ikun, right?

763
00:35:55,070 --> 00:35:56,870
Jekk I am passat null,
hemm xejn hemmhekk.

764
00:35:56,870 --> 00:35:59,230
I tista 'ukoll biss
addoċċ jgħidu ritorn foloz.

765
00:35:59,230 --> 00:36:04,050
Jekk inti tagħti me xejn, I żgur ma tistax
ssib xi numru N. Allura x'iktar jista I

766
00:36:04,050 --> 00:36:04,750
check issa?

767
00:36:04,750 --> 00:36:12,830
Jien se ngħid ukoll inkella jekk N hija
inqas minn dak kollu li huwa fil-node siġra

768
00:36:12,830 --> 00:36:16,300
li stajt ġiet valur N mogħtija.

769
00:36:16,300 --> 00:36:20,270
Fi kliem ieħor, jekk in-numru jien
tfittex, N, hija inqas mill-node

770
00:36:20,270 --> 00:36:21,340
li jien tħares lejn.

771
00:36:21,340 --> 00:36:23,190
U l-node I infittex
fil jissejjaħ siġra,

772
00:36:23,190 --> 00:36:26,370
u jitlob lura mingħandhom il-eżempju preċedenti
li jiksbu fil-valur fil-pointer,

773
00:36:26,370 --> 00:36:28,310
I jużaw in-notazzjoni vleġġa.

774
00:36:28,310 --> 00:36:35,960
Mela jekk N hija inqas minn vleġġa siġra
N, nixtieq li kunċettwalment tmur xellug.

775
00:36:35,960 --> 00:36:38,590
Kif nista jesprimu tiftix xellug?

776
00:36:38,590 --> 00:36:41,560
Biex ikunu ċari, jekk dan huwa
l-istampa in kwistjoni,

777
00:36:41,560 --> 00:36:44,612
u stajt ġiet mgħoddija li topmost
vleġġa li l-tipponta 'l isfel.

778
00:36:44,612 --> 00:36:45,570
C'est pointer siġra tiegħi.

779
00:36:45,570 --> 00:36:48,060
Jien tipponta lejn l-għerq tal-siġra.

780
00:36:48,060 --> 00:36:52,100
U jien infittxu jiġifieri, għal
in-numru 44, arbitrarju.

781
00:36:52,100 --> 00:36:55,300
Huwa 44 jew anqas jew
iktar minn 55 ovvjament?

782
00:36:55,300 --> 00:36:56,360
Dan huwa inqas minn.

783
00:36:56,360 --> 00:36:58,760
U hekk dan jekk il-kundizzjoni tapplika.

784
00:36:58,760 --> 00:37:03,981
Allura kunċettwalment, dak li nixtieq li
tfittxija jmiss jekk I infittex 44?

785
00:37:03,981 --> 00:37:04,480
Yeah?

786
00:37:04,480 --> 00:37:08,310

787
00:37:08,310 --> 00:37:11,100
>> Eżattament, nixtieq li
tfittex il-wild xellug,

788
00:37:11,100 --> 00:37:12,789
jew is-siġra xellug tal din l-istampa.

789
00:37:12,789 --> 00:37:14,830
U fil-fatt, let me permezz
l-istampa isfel hawn

790
00:37:14,830 --> 00:37:17,770
għal ftit mument, peress
I ma jistgħu scratch dan out.

791
00:37:17,770 --> 00:37:21,150
Jekk nibda hawn fuq 55, u
Naf li l-valur 44

792
00:37:21,150 --> 00:37:23,180
I infittex huwa li
fuq ix-xellug, huwa tip

793
00:37:23,180 --> 00:37:26,010
ta 'prodotti simili dmugħ-ktieb tat-telefon fil
nofs jew dmugħ-siġra fil nofs.

794
00:37:26,010 --> 00:37:29,660
I m'għadx għandhom jimpurtahom
Din it-taqsima kollu tas-siġra.

795
00:37:29,660 --> 00:37:33,270
And yet, curiously f'termini tal-
istruttura, dan il-ħaġa minn hawn li

796
00:37:33,270 --> 00:37:36,682
jibda bil 33, li hi stess
hija siġra tfittxija binarju.

797
00:37:36,682 --> 00:37:39,890
I qal li l-kelma rikursivi qabel minħabba
tabilħaqq din hija struttura ta 'data li

798
00:37:39,890 --> 00:37:41,707
skond id-definizzjoni hija rikursivi.

799
00:37:41,707 --> 00:37:44,540
Inti jista 'jkollhom siġra li l-din
big, iżda kull waħda ta 'tfal tagħha

800
00:37:44,540 --> 00:37:46,870
jirrappreżenta siġra biss ftit iżgħar.

801
00:37:46,870 --> 00:37:50,910
Minflok ma jkun nanniet
jew nannu, issa huwa biss mom

802
00:37:50,910 --> 00:37:54,300
or-- I ma jistgħux say-- ma mom
jew dad, li jkun stramb.

803
00:37:54,300 --> 00:37:59,000
Minflok l-żewġt itfal hemmhekk
tkun simili brother u aħwa.

804
00:37:59,000 --> 00:38:01,120
Ġenerazzjoni ġdida ta 'l-siġra tal-familja.

805
00:38:01,120 --> 00:38:02,900
Iżda strutturalment, huwa l-istess idea.

806
00:38:02,900 --> 00:38:06,790
U jirriżulta I għandhom funzjoni
li magħhom I tista 'tfittex tfittxija binarja

807
00:38:06,790 --> 00:38:07,290
siġra.

808
00:38:07,290 --> 00:38:08,680
Huwa sejjaħ tfittxija.

809
00:38:08,680 --> 00:38:17,870
I tfittxija għal N siġra vleġġa xellug
inkella jekk N hija ikbar mill-valur

810
00:38:17,870 --> 00:38:18,870
li jien bħalissa.

811
00:38:18,870 --> 00:38:20,800
55 fl-istorja mument ilu.

812
00:38:20,800 --> 00:38:23,780
I jkollhom funzjoni msejħa
tfittxija li nista 'biss

813
00:38:23,780 --> 00:38:29,660
jgħaddu N dan u recursively tfittxija
is-sub-tree u biss ritorn

814
00:38:29,660 --> 00:38:30,620
tkun xi tkun din ir-risposta.

815
00:38:30,620 --> 00:38:33,530
Else Stajt ltqajna xi każ bażiku finali hawnhekk.

816
00:38:33,530 --> 00:38:35,310
>> X'inhu l-każ finali?

817
00:38:35,310 --> 00:38:36,570
Tree huwa jew null.

818
00:38:36,570 --> 00:38:39,980
Il-valur jien kemm infittxu huwa
inqas minn jew akbar minn dik

819
00:38:39,980 --> 00:38:42,610
jew ugwali għal dan.

820
00:38:42,610 --> 00:38:44,750
U nista 'ngħid ugwali
ugwali, iżda loġikament huwa

821
00:38:44,750 --> 00:38:46,500
ekwivalenti għal biss qal ieħor hawn.

822
00:38:46,500 --> 00:38:49,150
Allura vera hija kif I issib xi ħaġa.

823
00:38:49,150 --> 00:38:51,710
Allura nisperaw li dan huwa
anki eżempju aktar konvinċenti

824
00:38:51,710 --> 00:38:54,900
milli l-funzjoni sigma stupid
għamilna ftit lectures lura,

825
00:38:54,900 --> 00:38:58,360
fejn kien daqstant faċli biex jintuża linja
biex jingħaddu l-numri minn wieħed

826
00:38:58,360 --> 00:39:02,390
N. Hawnhekk bi struttura data
li hi stess hija recursively

827
00:39:02,390 --> 00:39:07,050
definiti u recursively mfassla, issa aħna
l-abbiltà li jesprimu nfusna

828
00:39:07,050 --> 00:39:09,780
fil-kodiċi li hi stess hija rikursivi.

829
00:39:09,780 --> 00:39:12,580
Allura dan huwa l-istess kodiċi eżatt hawn.

830
00:39:12,580 --> 00:39:14,400
>> Allura liema problemi oħra nistgħu issolvi?

831
00:39:14,400 --> 00:39:18,160
Allura pass quick bogħod mill
siġar għall ftit mument.

832
00:39:18,160 --> 00:39:20,130
Hawnhekk jiġifieri, jgħidu, il-bandiera Ġermaniża.

833
00:39:20,130 --> 00:39:22,020
U hemm b'mod ċar
mudell għal din il-bandiera.

834
00:39:22,020 --> 00:39:23,811
U hemm lottijiet ta '
bnadar fid-dinja li

835
00:39:23,811 --> 00:39:27,560
huma sempliċi kemm dan f'termini
ta 'kuluri tagħhom u l-mudelli.

836
00:39:27,560 --> 00:39:31,930
Iżda jissoponi li din hija maħżuna bħala
Gif, jew JPEG, jew Bitmap, jew ping,

837
00:39:31,930 --> 00:39:34,240
kwalunkwe format tal-fajl grafika
li magħhom int familjari,

838
00:39:34,240 --> 00:39:36,460
li wħud minnhom aħna qed
playing magħhom PSET4.

839
00:39:36,460 --> 00:39:41,550
Dan ma jidhirx utli li jaħżen
pixel iswed, pixel iswed, pixel iswed,

840
00:39:41,550 --> 00:39:44,790
dot, dot, dot, mazz sħiħ ta '
pixels iswed għall-ewwel scanline,

841
00:39:44,790 --> 00:39:47,430
jew ringiela, allura mazz sħiħ ta '
l-istess, allura mazz sħiħ

842
00:39:47,430 --> 00:39:49,530
tal-istess, u mbagħad
mazz sħiħ ta 'aħmar pixels,

843
00:39:49,530 --> 00:39:53,020
pixels ħomor, aħmar pixels, imbagħad kollu
mazz ta 'isfar pixels, isfar, id-dritt?

844
00:39:53,020 --> 00:39:55,050
>> Hemm tali ineffiċjenza hawn.

845
00:39:55,050 --> 00:39:59,040
Kif inti intuwittivament
jikkompressa l-bandiera Ġermaniża

846
00:39:59,040 --> 00:40:01,320
jekk jimplimentawh bħala fajl?

847
00:40:01,320 --> 00:40:04,940
Bħal liema informazzjoni tista aħna ma
jolqot ħażna fuq diska sabiex

848
00:40:04,940 --> 00:40:08,040
li jnaqqas daqs tal-fajl tagħna minn bħall
a megabyte għal kilobyte, xi ħaġa

849
00:40:08,040 --> 00:40:09,430
iżgħar?

850
00:40:09,430 --> 00:40:13,130
Fejn tinsab il-redundancy
hawn biex tkun ċara?

851
00:40:13,130 --> 00:40:13,880
Liema jista inti tagħmel?

852
00:40:13,880 --> 00:40:14,380
Yeah?

853
00:40:14,380 --> 00:40:21,380

854
00:40:21,380 --> 00:40:21,970
Eżattament.

855
00:40:21,970 --> 00:40:24,550
Għaliex ma pjuttost milli tiftakar
il-kulur ta 'kull pixel darn

856
00:40:24,550 --> 00:40:28,200
bħad inti qed tagħmel fil PSET4
mal-format tal-fajl Bitmap,

857
00:40:28,200 --> 00:40:32,060
għaliex ma inti biss jirrappreżentaw il-
kolonna fuq ix-xellug ta 'pixels, per eżempju

858
00:40:32,060 --> 00:40:35,370
mazz ta 'iswed pixels, mazz
ta 'aħmar, u mazz ta' isfar,

859
00:40:35,370 --> 00:40:39,210
u mbagħad biss b'xi mod encode l
idea ta irrepeti dan 100 darba

860
00:40:39,210 --> 00:40:41,020
jew irrepeti dan 1,000 darba?

861
00:40:41,020 --> 00:40:43,430
Fejn 100 jew 1000 hija
biss integer, sabiex inti

862
00:40:43,430 --> 00:40:47,290
jista 'jitbiegħed ma biss numru wieħed
minflok mijiet jew eluf

863
00:40:47,290 --> 00:40:48,270
pixels ta addizzjonali.

864
00:40:48,270 --> 00:40:50,990
U fil-fatt, li kif aħna
jista jikkompressa l-bandiera Ġermaniża.

865
00:40:50,990 --> 00:40:51,490
U

866
00:40:51,490 --> 00:40:53,470
Issa dak dwar il-bandiera Franċiża?

867
00:40:53,470 --> 00:40:58,930
U ftit xi tip ta '
eżerċizzju mentali, li flag

868
00:40:58,930 --> 00:41:01,040
jista 'jkun kompressat aktar fuq diska?

869
00:41:01,040 --> 00:41:05,720
Il-bandiera Ġermaniża jew l-Franċiż
bandiera, jekk nieħdu dak l-approċċ?

870
00:41:05,720 --> 00:41:08,490
Il-bandiera Ġermaniża, għaliex hemm
aktar redundancy orizzontali.

871
00:41:08,490 --> 00:41:12,190
U mid-disinn, fajl grafika ħafna
formati tabilħaqq jaħdmu linji kif scan

872
00:41:12,190 --> 00:41:12,830
orizzontalment.

873
00:41:12,830 --> 00:41:14,674
Huma jistgħu jaħdmu
vertikalment, biss umanità

874
00:41:14,674 --> 00:41:17,090
snin deċiżi ilu li aħna ser
ġeneralment jaħsbu ta 'affarijiet ringiela

875
00:41:17,090 --> 00:41:18,880
billi ringiela minflok kolonna minn kolonna.

876
00:41:18,880 --> 00:41:20,820
Mela jekk inti kienu tabilħaqq
li tħares lejn il-fajl

877
00:41:20,820 --> 00:41:24,670
daqs ta 'bandiera Ġermaniża u Franċiża
bandiera, sakemm ir-riżoluzzjoni hija

878
00:41:24,670 --> 00:41:27,530
l-istess, l-istess wisa '
u l-għoli, dan wieħed

879
00:41:27,530 --> 00:41:31,580
hawn se tkun akbar, għaliex inti
jkollhom jirrepetu lilek innifsek tliet darbiet.

880
00:41:31,580 --> 00:41:35,570
Għandek tispeċifika blu, irrepeti
yourself, abjad, irrepeti yourself, aħmar,

881
00:41:35,570 --> 00:41:36,740
irrepeti yourself.

882
00:41:36,740 --> 00:41:39,000
Inti ma tistax biss jmorru kollha
il-mod lejn il-lemin.

883
00:41:39,000 --> 00:41:41,200
U bħala twarrib, li jagħmlu
ċar l-kompressjoni

884
00:41:41,200 --> 00:41:43,910
hija kullimkien, jekk dawn huma
erba frames minn video-- inti

885
00:41:43,910 --> 00:41:45,890
jista tfakkar li movie
jew video huwa ġeneralment

886
00:41:45,890 --> 00:41:47,286
bħal 29 jew 30 frejm kull sekonda.

887
00:41:47,286 --> 00:41:50,410
Huwa bħal ktieb flip ftit fejn inti
biss tara l-immaġni, immaġni, immaġni, immaġni,

888
00:41:50,410 --> 00:41:54,410
immaġni biss super fast hekk jidher qisu
l-atturi fuq l-iskrin mexjin.

889
00:41:54,410 --> 00:41:57,130
Hawn naħla bagħlija fuq
quċċata ta mazz ta 'fjuri.

890
00:41:57,130 --> 00:41:59,790
U għalkemm jista 'jkun it-tip ta'
diffiċli li wieħed jara ewwel daqqa t'għajn,

891
00:41:59,790 --> 00:42:04,020
l-unika ħaġa li jiċċaqilqu fil
dan movie huwa l-naħla.

892
00:42:04,020 --> 00:42:06,880
>> X'inhu dumb dwar ħażna
video mhux kompressat?

893
00:42:06,880 --> 00:42:11,420
Huwa tip ta 'ħela li jaħżen video
kif erba immaġini kważi identiċi li

894
00:42:11,420 --> 00:42:13,670
differenti biss safejn fejn il-naħla hu.

895
00:42:13,670 --> 00:42:16,280
Inti tista tarmi l bogħod aktar
ta 'dik l-informazzjoni

896
00:42:16,280 --> 00:42:20,190
u ftakar biss, per eżempju,
l-ewwel frame u l-aħħar qafas,

897
00:42:20,190 --> 00:42:22,180
frejms importanti jekk inti stajt
qatt semgħu l-kelma,

898
00:42:22,180 --> 00:42:24,337
u biss jaħżnu fil-
nofs meta l-naħla hu.

899
00:42:24,337 --> 00:42:26,170
U inti ma għandekx
taħżen kollha tal-roża,

900
00:42:26,170 --> 00:42:28,330
u l-blu, u l
Valuri aħdar kif ukoll.

901
00:42:28,330 --> 00:42:31,200
Allura dan huwa li jgħidu biss li
kompressjoni hija kullimkien.

902
00:42:31,200 --> 00:42:34,900
Huwa ta 'teknika aħna sikwit jużaw
jew jieħdu għal mogħtija f'dawn il-jiem.

903
00:42:34,900 --> 00:42:38,750
>> Imma kif taħseb li jikkompressa test?

904
00:42:38,750 --> 00:42:40,450
Kif inti tmur dwar kompressjoni test?

905
00:42:40,450 --> 00:42:45,410
Ukoll, kull wieħed mill-karattri fit
Ascii huwa byte wieħed, jew tmien bits.

906
00:42:45,410 --> 00:42:47,360
U dan huwa tip ta 'mutu, right?

907
00:42:47,360 --> 00:42:51,160
Għaliex inti probabilment tip A
u E u I u O u U ħafna

908
00:42:51,160 --> 00:42:55,270
aktar spiss milli bħal W jew Q jew Z,
jiddependi fuq il-lingwa li fiha

909
00:42:55,270 --> 00:42:56,610
int bil-miktub żgur.

910
00:42:56,610 --> 00:42:59,600
U hekk għaliex aħna jużaw
tmien bits għal kull ittra,

911
00:42:59,600 --> 00:43:02,040
inkluż l-inqas
ittri popolari, id-dritt?

912
00:43:02,040 --> 00:43:05,300
Għaliex ma jużaw inqas bits għal
l-ittri super popolari,

913
00:43:05,300 --> 00:43:07,760
bħall E, l-affarijiet inti raden
ewwel fil tmun tas Fortune,

914
00:43:07,760 --> 00:43:10,450
u l-użu aktar bits għal
l-ittri inqas popolari?

915
00:43:10,450 --> 00:43:10,950
Għaliex?

916
00:43:10,950 --> 00:43:13,130
Għaliex aħna qed biss ser
jużawhom inqas frekwenti.

917
00:43:13,130 --> 00:43:15,838
>> Ukoll, jirriżulta li kien hemm
Kien tentattivi magħmula biex jagħmlu dan.

918
00:43:15,838 --> 00:43:18,630
U jekk inti recall mill-grad
iskola jew skola għolja, kodiċi Morse.

919
00:43:18,630 --> 00:43:20,400
Kodiċi Morse għandha tikek
u daxxijiet li jista 'jkun

920
00:43:20,400 --> 00:43:24,270
trasmessi tul wajer kif
ħsejjes jew is-sinjali ta 'xi tip.

921
00:43:24,270 --> 00:43:25,930
Iżda kodiċi Morse huwa super nadif.

922
00:43:25,930 --> 00:43:29,010
Huwa tip ta 'sistema binarja fil
li inti għandek tikek jew dashes.

923
00:43:29,010 --> 00:43:30,977
Imma jekk inti tara, per eżempju, żewġ tikek.

924
00:43:30,977 --> 00:43:33,810
Jew jekk inti taħseb lura lill-operatur
li tmur bħal ħoss, ħoss, ħoss,

925
00:43:33,810 --> 00:43:36,760
ħoss, laqtu grillu ftit
li jittrasmetti sinjal,

926
00:43:36,760 --> 00:43:40,360
jekk inti, il-benefiċjarju, jirċievi żewġ
tikek, dak messaġġ irċevejt?

927
00:43:40,360 --> 00:43:43,490
Kompletament arbitrarja.

928
00:43:43,490 --> 00:43:44,450
>> I?

929
00:43:44,450 --> 00:43:45,060
I?

930
00:43:45,060 --> 00:43:47,500
Jew dak about-- jew I?

931
00:43:47,500 --> 00:43:49,570
Forsi kien biss tnejn id-dritt E ta?

932
00:43:49,570 --> 00:43:52,480
Allura hemm din il-problema
tal decodability ma Morse

933
00:43:52,480 --> 00:43:54,890
kodiċi, fejn sakemm il-
persuna li tibgħat il-messaġġ inti

934
00:43:54,890 --> 00:43:59,510
attwalment pauses sabiex inti tista sort ta
tara jew tisma l-lakuni bejn ittri,

935
00:43:59,510 --> 00:44:02,990
mhuwiex biżżejjed biss biex
tibgħat nixxiegħa ta 'żerijiet u dawk,

936
00:44:02,990 --> 00:44:05,610
jew tikek u daxxijiet,
għaliex hemm ambigwità.

937
00:44:05,610 --> 00:44:08,640
E huwa dot wieħed, hekk jekk inti
tara żewġ tikek jew tisma żewġ tikek,

938
00:44:08,640 --> 00:44:11,254
forsi huwa s tnejn E jew forsi huwa wieħed I.

939
00:44:11,254 --> 00:44:13,670
Għalhekk għandna bżonn ta 'sistema li l-
ftit aktar għaqlija minn dak.

940
00:44:13,670 --> 00:44:16,851
Allura raġel jismu snin Huffman
ilu ħarāet bil eżattament dan.

941
00:44:16,851 --> 00:44:18,600
Allura aħna qed biss jmorru
li tieħu t'għajn malajr

942
00:44:18,600 --> 00:44:20,114
lejn kif siġar huma germane għal dan.

943
00:44:20,114 --> 00:44:22,530
Ejja ngħidu li dan huwa xi
messaġġ stupid inti tixtieq li tibgħat,

944
00:44:22,530 --> 00:44:26,342
komposta minn ftit A, B, D'C iu E, il
imma hemm ħafna ta 'redundancy hawn.

945
00:44:26,342 --> 00:44:27,550
Mhuwiex maħsub li jkun l-Ingliż.

946
00:44:27,550 --> 00:44:28,341
Mhuwiex encrypted.

947
00:44:28,341 --> 00:44:30,540
Huwa biss messaġġ stupid
ma 'lottijiet ta' ripetizzjoni.

948
00:44:30,540 --> 00:44:34,010
Mela jekk inti fil-fatt għadd out kollha l-
'A, B, Ċ, D, u E tal, hawn

949
00:44:34,010 --> 00:44:34,890
il-frekwenza.

950
00:44:34,890 --> 00:44:37,800
20% ta 'l-ittri huma
'A, 45% ta' l-ittri

951
00:44:37,800 --> 00:44:39,660
huma s E, u tliet frekwenzi oħra.

952
00:44:39,660 --> 00:44:41,960
Aħna jingħaddu up hemm manwalment
u biss ma l-matematika.

953
00:44:41,960 --> 00:44:44,579
>> Għalhekk jirriżulta li
Huffman, xi żmien ilu,

954
00:44:44,579 --> 00:44:46,620
induna li, inti taf
dak, jekk nibda bini

955
00:44:46,620 --> 00:44:51,172
siġra, jew għall-foresti ta 'siġar, jekk inti se,
kif ġej, I tista 'tagħmel dan li ġej.

956
00:44:51,172 --> 00:44:53,880
Jien ser tagħti lil kull node
mill-ittri li I jimpurtahom

957
00:44:53,880 --> 00:44:55,530
u jien ser taħżen
ġewwa ta 'dik node

958
00:44:55,530 --> 00:44:58,610
il-frekwenzi bħala b'punt li jvarja
valur, jew inti tista 'tagħmel użu minnha għal N, wisq,

959
00:44:58,610 --> 00:45:00,210
imma aħna ser biss użu float hawn.

960
00:45:00,210 --> 00:45:03,100
U l-algoritmu li
huwa propost huwa li inti

961
00:45:03,100 --> 00:45:07,210
jieħdu din foresti ta 'node wieħed
siġar, siġar hekk super qasir,

962
00:45:07,210 --> 00:45:11,920
u tibda konnessjoni tagħhom ma '
gruppi ġodda, ġenituri l-ġodda, jekk inti se.

963
00:45:11,920 --> 00:45:16,150
U inti tagħmel dan billi jagħżlu l-
żewġ frekwenzi iżgħar kull darba.

964
00:45:16,150 --> 00:45:18,110
So I ħa 10% u 10%.

965
00:45:18,110 --> 00:45:19,090
I joħolqu node ġdid.

966
00:45:19,090 --> 00:45:20,910
U I-sejħa tal node ġdid 20%.

967
00:45:20,910 --> 00:45:22,750
>> Liema tnejn lymph I jikkombinaw jmiss?

968
00:45:22,750 --> 00:45:23,810
Huwa ftit ambigwa.

969
00:45:23,810 --> 00:45:26,643
Allura hemm xi każijiet rokna sa
jikkunsidraw, iżda li żżomm affarijiet pretty,

970
00:45:26,643 --> 00:45:29,300
Jien ser jagħżlu 20% -
I issa jinjora t-tfal.

971
00:45:29,300 --> 00:45:33,640
Jien ser jagħżlu 20% u
15% u jisiltu żewġ truf ġodda.

972
00:45:33,640 --> 00:45:35,624
U issa li żewġ nodi
do I loġikament jikkombinaw?

973
00:45:35,624 --> 00:45:38,540
Injora-tfal kollha, kollha l-
neputijiet, biss ħarsa lejn l-għeruq

974
00:45:38,540 --> 00:45:39,070
issa.

975
00:45:39,070 --> 00:45:42,220
Liema tnejn lymph nista jorbtu flimkien?

976
00:45:42,220 --> 00:45:44,530
Punt tnejn u 0.35.

977
00:45:44,530 --> 00:45:45,890
So let me jisiltu żewġ truf ġodda.

978
00:45:45,890 --> 00:45:47,570
U allura stajt biss ltqajna wieħed xellug.

979
00:45:47,570 --> 00:45:48,650
Allura hawnhekk siġra.

980
00:45:48,650 --> 00:45:51,160
U huwa kien imfassal apposta
tfittex tip ta 'pretty,

981
00:45:51,160 --> 00:45:55,870
iżda tinnota li t-trufijiet għandhom
wkoll ġiet ittikkettjata żero u wieħed.

982
00:45:55,870 --> 00:45:59,510
Sabiex kollha tat-truf tax-xellug huma żero
arbitrarju, iżda b'mod konsistenti.

983
00:45:59,510 --> 00:46:01,170
L-truf dritt huma dawk.

984
00:46:01,170 --> 00:46:05,070
>> U iva, liema Hoffman propost jiġifieri,
jekk inti tixtieq li jirrappreżentaw B,

985
00:46:05,070 --> 00:46:10,080
aktar milli jirrappreżentaw in-numru 66 kif
l ASCII li huwa tmien bits kollu,

986
00:46:10,080 --> 00:46:13,360
inti taf liema, just maħżen
il-mudell żero, żero, żero,

987
00:46:13,360 --> 00:46:17,030
żero, għaliex dak l-passaġġ
minn siġra tiegħi, siġra Sur Huffman, il

988
00:46:17,030 --> 00:46:18,600
il-weraq mill-għeruq.

989
00:46:18,600 --> 00:46:20,970
Jekk inti tixtieq li taħżen
E, b'kuntrast, ma

990
00:46:20,970 --> 00:46:26,290
tibgħat tmien bits li jirrappreżentaw E.
Minflok, tibgħat dak mudell ta 'bits?

991
00:46:26,290 --> 00:46:26,890
One.

992
00:46:26,890 --> 00:46:30,410
U x'hemm sbieħ dwar dan hija
li E hija l-ittra l-aktar popolari,

993
00:46:30,410 --> 00:46:32,340
u inti qed tuża l-
kodiċi iqsar għal dan.

994
00:46:32,340 --> 00:46:34,090
Li jmiss aktar popolari
ittra qisu

995
00:46:34,090 --> 00:46:37,380
kien A. U hekk kif ħafna bits
ma hu jipproponi li jużaw għal dan?

996
00:46:37,380 --> 00:46:38,270
Zero, wieħed.

997
00:46:38,270 --> 00:46:41,060
>> U għaliex dan huwa implimentat
kif din is-siġra, għal issa

998
00:46:41,060 --> 00:46:43,350
let me jistipulaw hemm
ebda ambigwità bħal fil Morse

999
00:46:43,350 --> 00:46:46,090
kodiċi, minħabba kollha ta 'l-
ittri li jimpurtahom

1000
00:46:46,090 --> 00:46:48,780
huma fl-aħħar ta 'dawn truf.

1001
00:46:48,780 --> 00:46:50,580
Allura li jinsab biss wieħed
applikazzjoni ta 'siġra.

1002
00:46:50,580 --> 00:46:52,538
Dan is-- u jien ser mewġa
naħa tiegħi f'dan kif inti

1003
00:46:52,538 --> 00:46:55,570
tista jimplimentaw dan bħala struttura C.

1004
00:46:55,570 --> 00:46:58,260
Jinħtieġ li jgħaqqdu
simbolu, bħal char,

1005
00:46:58,260 --> 00:46:59,910
u l-frekwenza tax-xellug u lemin.

1006
00:46:59,910 --> 00:47:02,510
Imma ejja nħarsu lejn żewġ
Eżempji finali li inti ser

1007
00:47:02,510 --> 00:47:06,070
jiksbu pjuttost familjari ma 'wara
kwizz żero problema stabbiliti ħamsa.

1008
00:47:06,070 --> 00:47:09,210
>> Għalhekk hemm l-istruttura tad-data
magħruf bħala mejda hash.

1009
00:47:09,210 --> 00:47:12,247
U tabella hash huwa tip ta
jibred fid li għandha bramel.

1010
00:47:12,247 --> 00:47:14,830
U jissoponi hemm erba bramel
hawn, biss erba spazji vojta.

1011
00:47:14,830 --> 00:47:20,830
Hawn gverta ta 'karti, u hawn huwa
klabb, spade, klabb, djamanti, klabb,

1012
00:47:20,830 --> 00:47:25,960
djamanti, klabb, djamanti,
clubs-- għalhekk dan huwa l-każwali.

1013
00:47:25,960 --> 00:47:30,330
Qlub, hearts-- hekk jien
bucketizing kollha tal-inputs hawn.

1014
00:47:30,330 --> 00:47:32,430
U ħtiġijiet mejda hash
li tħares lejn input tiegħek,

1015
00:47:32,430 --> 00:47:34,850
u mbagħad titqiegħed f'ċertu
post ibbażati fuq dak li tara.

1016
00:47:34,850 --> 00:47:35,600
Huwa ta 'algoritmu.

1017
00:47:35,600 --> 00:47:37,980
UI kienet qed tuża super
algoritmu viżwali sempliċi.

1018
00:47:37,980 --> 00:47:40,030
Il-parti l-agħar tagħha kien
ftakar dak l-istampi kienu.

1019
00:47:40,030 --> 00:47:41,590
U allura hemm erba 'affarijiet totali.

1020
00:47:41,590 --> 00:47:45,440
>> Issa l-stacks kienu qed tikber, li
hija ħaġa disinn deliberat hawn.

1021
00:47:45,440 --> 00:47:46,540
Imma dak li inkella jista 'nagħmel?

1022
00:47:46,540 --> 00:47:49,080
Allura fil-fatt hawnhekk għandna
mazz ta 'qodma kotba eżami iskola.

1023
00:47:49,080 --> 00:47:51,240
Ejja ngħidu li mazz ta '
ismijiet istudenti are here fuq.

1024
00:47:51,240 --> 00:47:52,570
Hawn tabella hash akbar.

1025
00:47:52,570 --> 00:47:54,867
Minflok erba bramel,
Għandi, ejja ngħidu 26.

1026
00:47:54,867 --> 00:47:57,950
U aħna ma jridu jmorru tissellef 26
affarijiet minn barra [? Annenberg?], Hekk

1027
00:47:57,950 --> 00:48:00,289
hawnhekk ħames dak jirrappreżentaw
A permezz Z. U jekk jien

1028
00:48:00,289 --> 00:48:03,580
tara student li ismu jibda bl A,
Jien ser tpoġġi tiegħu jew kwizz tagħha hemmhekk.

1029
00:48:03,580 --> 00:48:08,850
Jekk xi ħadd jibda bil Ċ, hemmhekk,
A-- attwalment, ma riedx li tagħmel dan.

1030
00:48:08,850 --> 00:48:10,060
B tmur minn hawn.

1031
00:48:10,060 --> 00:48:13,390
So I ħadthom ltqajna A u B u C. U
issa hawnhekk student ieħor A.

1032
00:48:13,390 --> 00:48:16,212
Iżda jekk din it-tabella hash huwa
implimentati ma 'firxa,

1033
00:48:16,212 --> 00:48:17,920
Jien tip ta 'invitat
f'dan il-punt, id-dritt?

1034
00:48:17,920 --> 00:48:19,510
I tip ta 'bżonn li jdaħħlu dan x'imkien.

1035
00:48:19,510 --> 00:48:24,380
>> Allura mod wieħed I tista 'ssolvi din hija, kollha
dritt, A huwa busy, B hija okkupata, C hija okkupata.

1036
00:48:24,380 --> 00:48:28,880
Jien ser jniżżlu fil D. Għalhekk fl
ewwel, I jkollhom aċċess immedjat bl-addoċċ

1037
00:48:28,880 --> 00:48:31,064
għal kull bramel għall-istudenti.

1038
00:48:31,064 --> 00:48:33,230
Imma issa huwa tip ta 'devoluti
fis lineari xi ħaġa,

1039
00:48:33,230 --> 00:48:36,750
għaliex jekk I trid tfittex għal xi ħadd
isem tiegħu jibda bi A, I check hawn.

1040
00:48:36,750 --> 00:48:38,854
Iżda jekk dan ma jkunx il-A
student I infittex,

1041
00:48:38,854 --> 00:48:41,520
I tip ta 'għandek tibda ikkontrollar
l bramel, għaliex dak li għamilt

1042
00:48:41,520 --> 00:48:44,530
kien tip ta 'lineari
sonda l-istruttura tad-data.

1043
00:48:44,530 --> 00:48:47,710
Mod stupid ta 'tgħid biss ħarsa
għall-ewwel ftuħ disponibbli,

1044
00:48:47,710 --> 00:48:51,850
u mqiegħda bħala pjan B, biex ngħidu hekk,
jew pjan D f'dan il-każ, il-valur

1045
00:48:51,850 --> 00:48:53,340
f'dak il-lok minflok.

1046
00:48:53,340 --> 00:48:56,470
Dan huwa biss hekk li jekk inti stajt
ltqajna 26 postijiet u l-ebda istudenti

1047
00:48:56,470 --> 00:49:00,600
bl-isem Q jew Z, jew xi ħaġa bħal
li, għall-inqas inti qed tuża l-ispazju.

1048
00:49:00,600 --> 00:49:03,140
>> Iżda aħna stajt diġà raw aktar
soluzzjonijiet għaqlija hawn, id-dritt?

1049
00:49:03,140 --> 00:49:04,870
What would you do minflok
jekk għandek xi ħabta?

1050
00:49:04,870 --> 00:49:06,670
Jekk żewġ persuni jkollhom
l-isem A, dak li

1051
00:49:06,670 --> 00:49:09,160
kienu aktar intelliġenti jew
Soluzzjoni intuwittivi milli sempliċiment

1052
00:49:09,160 --> 00:49:12,840
tqegħid A fejn D suppost tkun?

1053
00:49:12,840 --> 00:49:14,810
Għaliex ma I biss jmorru
[barra? Annenberg?],

1054
00:49:14,810 --> 00:49:19,960
bħal malloc, node ieħor, poġġih
hawn, u mbagħad iwettqu l Student hawn.

1055
00:49:19,960 --> 00:49:22,120
I hekk li essenzjalment ikollhom
xi tip ta 'firxa,

1056
00:49:22,120 --> 00:49:25,590
jew forsi aktar elegantly kif aħna qed
jibdew biex tara lista marbuta.

1057
00:49:25,590 --> 00:49:29,520
>> U hekk tabella hash hija struttura
li jista 'jidher biss bħal din,

1058
00:49:29,520 --> 00:49:33,900
iżda aktar cleverly, inti xi ħaġa imsejħa
chaining separata, li biha tabella hash

1059
00:49:33,900 --> 00:49:38,340
pjuttost sempliċement firxa, kull wieħed
l-elementi tagħhom ma jkunx numru,

1060
00:49:38,340 --> 00:49:40,470
hija nnifisha lista marbuta.

1061
00:49:40,470 --> 00:49:45,080
Hekk li tikseb aċċess super fast
jiddeċiedu fejn issir hash valur tiegħek biex.

1062
00:49:45,080 --> 00:49:48,059
Ħafna bħall mal-eżempju cards,
I għamel deċiżjonijiet super malajr.

1063
00:49:48,059 --> 00:49:49,600
Qlub tmur hawn, djamanti tmur hawn.

1064
00:49:49,600 --> 00:49:52,180
Istess hawn, A tmur hawn,
D tmur hawn, B tmur hawn.

1065
00:49:52,180 --> 00:49:55,740
Allura super fast ħarsa-ups, u jekk
jiġri li jinżel fit każ

1066
00:49:55,740 --> 00:49:59,429
kolliżjonijiet fejn inti ħadthom ltqajna, żewġ
nies bl-istess isem, tajjeb allura

1067
00:49:59,429 --> 00:50:00,970
inti biss tibda jgħaqqduhom flimkien.

1068
00:50:00,970 --> 00:50:03,900
U forsi inti jżommhom magħżula
alfabetikament, forsi inti ma.

1069
00:50:03,900 --> 00:50:05,900
Imma l-anqas issa għandna l-dinamiżmu.

1070
00:50:05,900 --> 00:50:10,250
Allura fuq naħa waħda għandna super fast
ħin kostanti, u tip ta 'żmien lineari

1071
00:50:10,250 --> 00:50:14,110
involut jekk dawn il-listi marbuta
tibda tikseb ftit twil.

1072
00:50:14,110 --> 00:50:16,880
>> Allura dan it-tip ta 'iblah,
snin Joke geeky ilu.

1073
00:50:16,880 --> 00:50:19,590
Fil-CS50 Hack-a-Thon,
meta l-istudenti check in,

1074
00:50:19,590 --> 00:50:22,040
xi TF jew CA kull sena
jaħseb huwa umoristiċi li imqiegħda

1075
00:50:22,040 --> 00:50:27,772
sinjal bħal dan, fejn hija biss
ifisser li jekk isem tiegħek tibda ma 'A,

1076
00:50:27,772 --> 00:50:28,870
jmorru b'dan il-mod.

1077
00:50:28,870 --> 00:50:31,110
Jekk tibda ismek
ma 'B, mur this-- OK,

1078
00:50:31,110 --> 00:50:33,290
huwa umoristiċi forsi aktar tard fil-semestru.

1079
00:50:33,290 --> 00:50:36,420
Iżda hemm ieħor
mod ta 'kif isir dan, wisq.

1080
00:50:36,420 --> 00:50:37,410
Come lura għal dak.

1081
00:50:37,410 --> 00:50:38,600
>> Allura hemm din l-istruttura.

1082
00:50:38,600 --> 00:50:40,420
U dan huwa aħħar tagħna
istruttura għal-lum,

1083
00:50:40,420 --> 00:50:42,400
li hija xi ħaġa imsejħa trie.

1084
00:50:42,400 --> 00:50:47,140
T-R-I-E, li għal xi raġuni huwa qasir
għall-irkupru, iżda huwa msejjaħ trie.

1085
00:50:47,140 --> 00:50:51,389
Allura trie hija ieħor interessanti
amalgama ta 'lott ta' dawn l-ideat.

1086
00:50:51,389 --> 00:50:52,930
Huwa siġra, li konna rajna qabel.

1087
00:50:52,930 --> 00:50:54,180
Mhuwiex siġra tfittxija binarju.

1088
00:50:54,180 --> 00:50:58,410
Huwa siġra ma 'kwalunkwe numru ta' tfal,
iżda kull wieħed mill-tfal fi trie

1089
00:50:58,410 --> 00:51:00,090
huwa firxa.

1090
00:51:00,090 --> 00:51:04,790
Firxa ta 'daqs, jiġifieri, 26 jew forsi 27
jekk inti tixtieq li tappoġġja ismijiet hyphenated

1091
00:51:04,790 --> 00:51:06,790
jew apostrophes fl-ismijiet tan-nies.

1092
00:51:06,790 --> 00:51:08,280
>> U għalhekk din hija struttura ta 'data.

1093
00:51:08,280 --> 00:51:10,290
U jekk inti tħares minn fuq
għal isfel, bħal jekk inti

1094
00:51:10,290 --> 00:51:13,710
tħares lejn il-node quċċata hemm, M, huwa
tipponta lejn il-ħaġa fuq ix-xellug hemm,

1095
00:51:13,710 --> 00:51:17,665
li mbagħad A, X, W, E, L, L. Dan huwa
biss struttura data li b'mod arbitrarju

1096
00:51:17,665 --> 00:51:19,120
huwa ħażna ismijiet tan-nies.

1097
00:51:19,120 --> 00:51:25,720
U Maxwell tkunx maħżuna mis ftit wara
triq ta 'firxa biex array biex array.

1098
00:51:25,720 --> 00:51:30,050
Imma x'hemm aqwa dwar trie huwa
li, billi lista marbuta u anke

1099
00:51:30,050 --> 00:51:34,520
firxa, l-aħjar aħna stajt qatt gotten huwa
żmien lineari jew il-ħin logaritmika tfittex

1100
00:51:34,520 --> 00:51:35,600
xi ħadd up.

1101
00:51:35,600 --> 00:51:40,530
F'din l-istruttura tad-data ta 'trie, jekk
istruttura tad-data tiegħi isem wieħed fih

1102
00:51:40,530 --> 00:51:43,720
u jien infittxu Maxwell, jien
ser issib lilu pretty malajr.

1103
00:51:43,720 --> 00:51:47,910
I biss tfittex M-A-X-W-E-L-L. Jekk
din l-istruttura tad-data, għall-kuntrarju,

1104
00:51:47,910 --> 00:51:51,830
jekk N hija miljun, jekk ikun hemm
miljun ismijiet f'din l-istruttura tad-data,

1105
00:51:51,830 --> 00:51:57,100
Maxwell għadu għaddej li jkun
discoverable wara biss M-A--X W-E-L-L

1106
00:51:57,100 --> 00:51:58,090
passi.

1107
00:51:58,090 --> 00:52:01,276
U passi David-- D-A-V-I-D.

1108
00:52:01,276 --> 00:52:03,400
Fi kliem ieħor, permezz tal-bini
struttura data li l-

1109
00:52:03,400 --> 00:52:07,240
ltqajna kollha ta 'dawn arrays, li kollha
infushom jappoġġjaw l-aċċess bl-addoċċ,

1110
00:52:07,240 --> 00:52:11,090
I tista 'tibda tfittex up Popolari
isem użu ta 'ammont ta' ħin li l-

1111
00:52:11,090 --> 00:52:14,340
proporzjonali għall mhux in-numru
ta 'affarijiet fl-istruttura tad-data,

1112
00:52:14,340 --> 00:52:16,330
bħal miljun ismijiet eżistenti.

1113
00:52:16,330 --> 00:52:20,135
L-ammont ta 'ħin li tieħu lili biex isibu
M-A--X W-E-L-L f'din l-istruttura tad-data huwa

1114
00:52:20,135 --> 00:52:22,260
proporzjonali ma 'l-
daqs tal-istruttura tad-data,

1115
00:52:22,260 --> 00:52:25,930
iżda għat-tul tal-isem.

1116
00:52:25,930 --> 00:52:28,440
U realistiku l-
ismijiet aħna qed tfittex up

1117
00:52:28,440 --> 00:52:29,970
huma qatt ser tkun crazy twil.

1118
00:52:29,970 --> 00:52:32,600
Forsi xi ħadd ikollu karattru 10
isem, 20 isem karattru.

1119
00:52:32,600 --> 00:52:33,900
Huwa ċertament finite, id-dritt?

1120
00:52:33,900 --> 00:52:37,110
Hemm umana fid-Dinja li
għandu l-isem itwal possibbli,

1121
00:52:37,110 --> 00:52:39,920
iżda li isem huwa kostanti
tul valur, id-dritt?

1122
00:52:39,920 --> 00:52:41,980
Ma jvarjaw fid ebda sens.

1123
00:52:41,980 --> 00:52:45,090
Allura b'dan il-mod, konna
kisbu istruttura tad-data

1124
00:52:45,090 --> 00:52:47,800
li huwa żmien kostanti ħarsa-up.

1125
00:52:47,800 --> 00:52:50,670
Hija ma tieħu għadd ta 'passi
skond it-tul tal-input,

1126
00:52:50,670 --> 00:52:54,250
iżda mhux in-numru ta 'isem
fl-istruttura tad-data.

1127
00:52:54,250 --> 00:52:58,700
Allura jekk aħna doppju tal-għadd ta 'ismijiet
sena d-dieħla minn biljun għal żewġ biljun,

1128
00:52:58,700 --> 00:53:03,720
sejba Maxwell se jieħu
l-istess numru eżatt ta 'seba' passi

1129
00:53:03,720 --> 00:53:04,650
biex issib lilu.

1130
00:53:04,650 --> 00:53:08,810
U hekk aħna jidhru li kisbu
Grail qaddis tagħna ta 'running time.

1131
00:53:08,810 --> 00:53:10,860
>> Allura ftit avviżi malajr.

1132
00:53:10,860 --> 00:53:11,850
Quiz żero huwa ġejjin up.

1133
00:53:11,850 --> 00:53:14,600
Aktar dwar dan fuq il-websajt tal-kors ta
matul il-koppja li jmiss ta 'ġranet.

1134
00:53:14,600 --> 00:53:17,120
Tnejn lecture-- huwa btala
hawn fil-Harvard nhar it-Tnejn.

1135
00:53:17,120 --> 00:53:18,850
Mhuwiex fi New Haven,
hekk aħna qed tieħu l-klassi

1136
00:53:18,850 --> 00:53:20,310
lejn New Haven għall taħdita nhar it-Tnejn.

1137
00:53:20,310 --> 00:53:22,550
Kollox se jkun iffilmjati
u streaming live bħas-soltu,

1138
00:53:22,550 --> 00:53:24,900
imma ejja tispiċċa llum
bit-tieni clip 30

1139
00:53:24,900 --> 00:53:26,910
imsejħa "Ħsibijiet Deep"
billi Daven Farnham, li

1140
00:53:26,910 --> 00:53:30,850
kienet ispirata aħħar sena sas-Sibt
"Ħsibijiet Deep" Night Live s

1141
00:53:30,850 --> 00:53:35,700
billi Jack Handy, li
għandu issa jagħmel sens.

1142
00:53:35,700 --> 00:53:38,810
>> FILM: U issa, "Deep
Ħsibijiet "mill Daven Farnham.

1143
00:53:38,810 --> 00:53:42,100

1144
00:53:42,100 --> 00:53:42,870
Tabella hash.

1145
00:53:42,870 --> 00:53:45,940

1146
00:53:45,940 --> 00:53:47,660
>> SPEAKER 1: Id-dritt, li hu għal issa.

1147
00:53:47,660 --> 00:53:48,805
Aħna ser tara int ġimgħa d-dieħla.

1148
00:53:48,805 --> 00:53:55,380

1149
00:53:55,380 --> 00:53:56,680
>> Doug: Biex tara li fl-azzjoni.

1150
00:53:56,680 --> 00:53:58,304
Mela ejja tagħti ħarsa lejn dak id-dritt issa.

1151
00:53:58,304 --> 00:53:59,890
Allura hawnhekk, għandna firxa mhux magħżul.

1152
00:53:59,890 --> 00:54:04,860
>> IAN: Doug, inti tista 'tmur quddiem u jerġgħu jibdew
dan għal wieħed biss sekonda, jekk jogħġbok.

1153
00:54:04,860 --> 00:54:08,562
Kull dritt, kameras huma rolling, hekk
azzjoni kull meta int lest, Doug, OK?

1154
00:54:08,562 --> 00:54:11,020
Doug: Kull dritt, hekk dak li aħna
hawn huwa firxa mhux magħżul.

1155
00:54:11,020 --> 00:54:13,960
U stajt kkulurita l-elementi kollha
aħmar li jindika li huwa, fil-fatt,

1156
00:54:13,960 --> 00:54:14,460
mhux magħżul.

1157
00:54:14,460 --> 00:54:17,960
Allura tfakkar li l-ewwel ħaġa li nagħmlu
hija aħna issolvi l-nofs xellug tal-firxa.

1158
00:54:17,960 --> 00:54:20,630
Imbagħad aħna issolvi d-dritt
nofs il-firxa.

1159
00:54:20,630 --> 00:54:22,830
U ya-da, ya-da, ya-da,
aħna jingħaqdu flimkien.

1160
00:54:22,830 --> 00:54:24,520
U aħna jkollhom firxa kompletament separat kif.

1161
00:54:24,520 --> 00:54:25,360
Allura li kif jingħaqdu sort xogħlijiet.

1162
00:54:25,360 --> 00:54:27,109
>> IAN: Whoa, Whoa, Whoa,
maqtugħ, imqatta ', imqatta, maqtugħin.

1163
00:54:27,109 --> 00:54:30,130
Doug, inti ma tistax biss ya-da, ya-da,
ya-da, triqtek tip jingħaqdu.

1164
00:54:30,130 --> 00:54:31,970
>> Doug: I biss għamlet.

1165
00:54:31,970 --> 00:54:32,832
Huwa tal-multa.

1166
00:54:32,832 --> 00:54:33,540
We qed imorru tajjeb.

1167
00:54:33,540 --> 00:54:34,760
Ejja biss iżommu rolling.

1168
00:54:34,760 --> 00:54:35,380
Allura xorta,

1169
00:54:35,380 --> 00:54:37,800
>> IAN: Int għandek tispjega
aktar bis-sħiħ minn dak.

1170
00:54:37,800 --> 00:54:39,999
Li jinsab biss mhux biżżejjed.

1171
00:54:39,999 --> 00:54:41,790
Doug: Ian, aħna ma
bżonn li jmorru lura għal wieħed.

1172
00:54:41,790 --> 00:54:42,350
Huwa tal-multa.

1173
00:54:42,350 --> 00:54:45,690
Allura xorta, jekk aħna nkomplu bil merge--
Ian, aħna qed fil-nofs ta 'iffilmjar.

1174
00:54:45,690 --> 00:54:46,612
>> IAN: I know.

1175
00:54:46,612 --> 00:54:49,320
U ma nistgħux biss ya-da, ya-da,
ya-da, permezz tal-proċess kollu.

1176
00:54:49,320 --> 00:54:52,200
Int għandek tispjega kif il-
żewġ naħat tikseb magħquda flimkien.

1177
00:54:52,200 --> 00:54:53,570
>> Doug: Iżda aħna stajt diġà
spjega kif it-tnejn sides--

1178
00:54:53,570 --> 00:54:55,321
>> IAN: You ħadthom biss murija
minnhom firxa jingħaqdu.

1179
00:54:55,321 --> 00:54:56,486
Doug: Huma jafu l-proċess.

1180
00:54:56,486 --> 00:54:57,172
Huma qed multa.

1181
00:54:57,172 --> 00:54:58,380
Imxejna marret fuqha għaxar darbiet.

1182
00:54:58,380 --> 00:55:00,330
>> IAN: Inti biss skipped dritt fuqha.

1183
00:55:00,330 --> 00:55:03,360
Aħna wieħed imur lura lejn, inti
ma tista 'inti ya-da, ya-da fuqha.

1184
00:55:03,360 --> 00:55:05,480
Dritt kollox, lura għal wieħed.

1185
00:55:05,480 --> 00:55:07,833
>> Doug: irrid immur lura
kollha permezz ta 'l-pjastri?

1186
00:55:07,833 --> 00:55:08,332
Alla tiegħi.

1187
00:55:08,332 --> 00:55:11,008

1188
00:55:11,008 --> 00:55:13,004
Huwa bħall-sitt darba, Ian.

1189
00:55:13,004 --> 00:55:13,940
Huwa tal-multa.

1190
00:55:13,940 --> 00:55:15,200
>> IAN: Kull dritt.

1191
00:55:15,200 --> 00:55:16,590
Inti lest?

1192
00:55:16,590 --> 00:55:17,400
Great.

1193
00:55:17,400 --> 00:55:18,950
Azzjoni.