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

2
00:00:10,900 --> 00:00:15,860
>> SPEAKER 1: Në rregull, kështu që kjo është
CS50 Ky është fundi i javës pesë.

3
00:00:15,860 --> 00:00:19,220
Dhe kujtojnë se herën e fundit ne
filluar duke kërkuar në të dhënat njohës

4
00:00:19,220 --> 00:00:22,310
Strukturat që filluan për të zgjidhur
Problemet, që filluan për të futur

5
00:00:22,310 --> 00:00:25,640
probleme të reja, por çelësi për këtë
ishte lloj i filetim që ne

6
00:00:25,640 --> 00:00:27,940
filloi të bëjë nga nyje në nyje.

7
00:00:27,940 --> 00:00:30,085
Pra, kjo sigurisht është
një listë e lidhur në formë individuale.

8
00:00:30,085 --> 00:00:31,960
Dhe duke e lidhur në formë individuale,
Unë do të thotë se ka vetëm një

9
00:00:31,960 --> 00:00:33,380
thread mes të secilit prej këtyre nyjeve.

10
00:00:33,380 --> 00:00:35,890
Rezulton se ju mund të bëni njohës
gjëra të tilla si listat e lidhura dyfish

11
00:00:35,890 --> 00:00:38,470
ku ju keni një shigjetë
duke shkuar në të dy drejtimet, e cila

12
00:00:38,470 --> 00:00:40,320
mund të ndihmojë me efikasitet të caktuara.

13
00:00:40,320 --> 00:00:42,000
Por kjo zgjidhur problemin?

14
00:00:42,000 --> 00:00:43,500
Çfarë problemi ka kjo zgjidh?

15
00:00:43,500 --> 00:00:46,620
Pse kemi kujdes të hënën?

16
00:00:46,620 --> 00:00:49,820
Pse, në teori, nuk kemi kujdes të hënën?

17
00:00:49,820 --> 00:00:50,630
Çfarë do të bëni?

18
00:00:50,630 --> 00:00:51,950
>> Audienca: Ne dinamike mund të resize atë.

19
00:00:51,950 --> 00:00:53,740
>> SPEAKER 1: OK, kështu që ne mund të
dinamike resize atë.

20
00:00:53,740 --> 00:00:54,710
Të lumtë të dy prej jush.

21
00:00:54,710 --> 00:00:57,560
Kështu që ju mund dinamike resize këtë
Struktura e të dhënave, ndërsa një grup,

22
00:00:57,560 --> 00:01:00,760
Recall, ju duhet të dini
priori si hapësirë ​​sa të doni

23
00:01:00,760 --> 00:01:03,870
dhe në qoftë se keni nevojë për pak më shumë
hapësirë, ju jeni lloj i nga fat.

24
00:01:03,870 --> 00:01:05,560
Ju duhet të krijoni një grup të tërë të re.

25
00:01:05,560 --> 00:01:07,893
Ju duhet të lëvizin të gjitha tuaj
të dhënat nga njëri në tjetrin,

26
00:01:07,893 --> 00:01:10,600
përfundimisht të lirë array vjetër
në qoftë se ju mund të, dhe pastaj do të vazhdojë.

27
00:01:10,600 --> 00:01:13,891
Të cilat vetëm ndjehet shumë i kushtueshëm dhe shumë
joefikase, dhe në të vërtetë ajo mund të jetë.

28
00:01:13,891 --> 00:01:14,890
Por kjo nuk është e gjitha e mirë.

29
00:01:14,890 --> 00:01:18,180
Ne të paguajë një çmim, atë që ishte një
nga çmimet më të dukshme ne

30
00:01:18,180 --> 00:01:20,550
paguajnë duke përdorur një listë e lidhur?

31
00:01:20,550 --> 00:01:22,825
>> Audienca: Ne duhet të përdorim
hapësirë ​​të dyfishtë për secilën prej tyre.

32
00:01:22,825 --> 00:01:25,200
SPEAKER 1: Yeah, kështu që ne kemi nevojë
të paktën dy herë më shumë hapësirë.

33
00:01:25,200 --> 00:01:27,700
Në fakt, kam kuptuar kjo foto e
edhe pak mashtruese,

34
00:01:27,700 --> 00:01:32,200
sepse në IDE CS50, në një shumë të moderne
kompjutera, një tregues apo një adresë

35
00:01:32,200 --> 00:01:33,700
Nuk është në fakt katër bytes.

36
00:01:33,700 --> 00:01:36,090
Është shumë shpesh këto
ditë tetë bytes, të cilat

37
00:01:36,090 --> 00:01:38,530
nënkupton pjesën e poshtme më
rectangles atje në realitet

38
00:01:38,530 --> 00:01:40,900
janë lloj i dy herë më
i madh si ajo që unë kam vizatuar,

39
00:01:40,900 --> 00:01:44,409
që do të thotë se ju jeni duke përdorur tri herë si
hapësirë ​​më shumë që ne mund të kemi ndryshe.

40
00:01:44,409 --> 00:01:46,700
Tani në të njëjtën kohë, ne jemi
ende duke folur bytes, e drejtë?

41
00:01:46,700 --> 00:01:49,140
Ne nuk jemi domosdoshmërisht duke folur
megabajt apo gigabajt,

42
00:01:49,140 --> 00:01:51,000
përveç rasteve kur këto të dhëna struktura të mëdha.

43
00:01:51,000 --> 00:01:54,510
>> Dhe kështu që sot ne të fillojnë të marrin në konsideratë
se si ne mund të shqyrtojë të dhënat e

44
00:01:54,510 --> 00:01:57,310
më efikase nëse në
fakt të dhënat merr të mëdha.

45
00:01:57,310 --> 00:02:00,360
Por le të përpiqemi të canonicalize
operacionet e para

46
00:02:00,360 --> 00:02:02,460
që ju mund të bëni në këto
llojet e strukturave të të dhënave.

47
00:02:02,460 --> 00:02:04,790
Pra, diçka si një i lidhur
Lista përgjithësisht mbështet

48
00:02:04,790 --> 00:02:07,514
Operacionet pëlqen fshini,
futur, dhe kërko.

49
00:02:07,514 --> 00:02:08,639
Dhe çfarë dua të them me këtë?

50
00:02:08,639 --> 00:02:11,222
Kjo thjesht do të thotë se zakonisht,
në qoftë se njerëzit janë duke përdorur listën e të lidhura,

51
00:02:11,222 --> 00:02:14,287
ata ose dikush tjetër i ka zbatuar
funksionon si fshini, insert,

52
00:02:14,287 --> 00:02:16,120
dhe kërkimit, kështu që ju mund të
vërtetë të bëjë diçka

53
00:02:16,120 --> 00:02:18,030
dobishëm me strukturën dhënave.

54
00:02:18,030 --> 00:02:20,760
Pra, le të marrin një vështrim të shpejtë
se si ne mund të zbatojë

55
00:02:20,760 --> 00:02:24,530
kod për një listë të lidhura si më poshtë.

56
00:02:24,530 --> 00:02:27,885
>> Pra, kjo është vetëm një kod C,
as edhe një program i plotë

57
00:02:27,885 --> 00:02:29,260
se unë me të vërtetë rrahur shpejt lart.

58
00:02:29,260 --> 00:02:32,300
Kjo nuk është në internet në shpërndarjen
Kodi, sepse ajo nuk do të të vërtetë të drejtuar.

59
00:02:32,300 --> 00:02:33,790
Por vini re unë kam vetëm
me një koment tha:

60
00:02:33,790 --> 00:02:36,130
dot dot dot, ka diçka
atje, dot Dot Dot, diçka atje.

61
00:02:36,130 --> 00:02:38,410
Dhe le të vetëm shikoni në
çfarë pjesë lëng janë.

62
00:02:38,410 --> 00:02:40,790
Pra, në përputhje tre,
kujtojnë se kjo është tani

63
00:02:40,790 --> 00:02:45,960
kemi propozuar deklaruar një nyje të fundit
kohë, një nga ato objekte drejtkëndëshe.

64
00:02:45,960 --> 00:02:48,790
Ajo ka një int që ne do të thërrasë N,
por ne mund ta quajmë atë gjë,

65
00:02:48,790 --> 00:02:51,920
dhe pastaj një yll nyje struct quajtur ardhshëm.

66
00:02:51,920 --> 00:02:55,520
Dhe vetëm të jetë i qartë, se dyti
line, në përputhje gjashtë, çfarë është kjo?

67
00:02:55,520 --> 00:02:57,930
Çfarë është ajo bën për ne?

68
00:02:57,930 --> 00:03:01,044
Për shkak se ajo sigurisht duket më
i fshehtë se variablave tonë të zakonshme.

69
00:03:01,044 --> 00:03:02,740
>> Audienca: Kjo e bën atë të lëvizë mbi një.

70
00:03:02,740 --> 00:03:04,650
>> SPEAKER 1: Kjo e bën atë të lëvizë mbi një.

71
00:03:04,650 --> 00:03:08,580
Dhe për të qenë më të saktë,
ai do të ruajë adresën

72
00:03:08,580 --> 00:03:11,582
i nyjës që është menduar të jetë
semantikisht tjetër për të, apo jo?

73
00:03:11,582 --> 00:03:13,540
Pra, kjo nuk do të
domosdoshmërisht të lëvizur asgjë.

74
00:03:13,540 --> 00:03:15,290
Është vetëm do të
ruajtur nje vlere, i cili është

75
00:03:15,290 --> 00:03:17,170
do të jetë adresa
e disa nyjeve të tjera,

76
00:03:17,170 --> 00:03:20,810
dhe kjo është arsyeja pse ne kemi thënë struct
yll nyje, ylli denoting

77
00:03:20,810 --> 00:03:22,370
një tregues apo një adresë.

78
00:03:22,370 --> 00:03:26,390
OK, kështu që tani, nëse ju supozojmë se ne kemi
kjo N dispozicion për ne, dhe le të

79
00:03:26,390 --> 00:03:29,490
supozojmë se dikush tjetër e ka
futur një bandë e tërë e numrave të plotë

80
00:03:29,490 --> 00:03:30,400
në një listë të lidhura.

81
00:03:30,400 --> 00:03:35,640
Dhe kjo listë e lidhur është
vuri në dukje nga disa pika

82
00:03:35,640 --> 00:03:39,040
një listë të quajtur variabël që është
kaluar në këtu si një parametër,

83
00:03:39,040 --> 00:03:43,120
Si mund të shkoj në lidhje me vijën
14 implementimin kërkim?

84
00:03:43,120 --> 00:03:45,990
Me fjalë të tjera, në qoftë se unë jam i zbatimit
funksioni qëllimi i të cilit në jetë

85
00:03:45,990 --> 00:03:48,889
është që të marrë një int dhe pastaj
fillimi i një liste të lidhura,

86
00:03:48,889 --> 00:03:50,430
që është një tregues në listën e lidhur.

87
00:03:50,430 --> 00:03:52,992
Ashtu si i pari, i cili unë mendoj Davidin
ishte vullnetar jonë të hënën,

88
00:03:52,992 --> 00:03:54,700
ai ishte treguar në
tërë i lidhur Lista aktuale e,

89
00:03:54,700 --> 00:03:57,820
kjo është sikur ne jemi duke kaluar
Davidi në si argument tonë këtu.

90
00:03:57,820 --> 00:03:59,990
Si mund të shkoj për traversing këtë listë?

91
00:03:59,990 --> 00:04:04,640
E pra, ajo rezulton se edhe pse
pointers janë relativisht të reja tani për ne,

92
00:04:04,640 --> 00:04:07,010
ne mund të bëjmë këtë relativisht
drejpërdrejtë.

93
00:04:07,010 --> 00:04:09,500
>> Unë jam duke shkuar për të shkuar përpara dhe
deklarojë një ndryshore të përkohshme që

94
00:04:09,500 --> 00:04:12,364
nga konventa është vetëm do
të quhet tregues, ose PTR,

95
00:04:12,364 --> 00:04:14,030
por ju mund të telefononi atë çdo gjë që ju dëshironi.

96
00:04:14,030 --> 00:04:16,470
Dhe unë jam duke shkuar për të nisja
ajo fillimit të lista.

97
00:04:16,470 --> 00:04:20,050
Kështu që ju mund të lloj të mendojnë për këtë
si mua mësuesi ditë të tjera,

98
00:04:20,050 --> 00:04:23,580
lloj i vënë në dikë
në mesin e njerëzve tanë si vullnetarë.

99
00:04:23,580 --> 00:04:26,470
Kështu që unë jam një ndryshore të përkohshme që është
vetëm duke vënë në të njëjtën gjë

100
00:04:26,470 --> 00:04:31,390
se jonë me emrin rastësisht
vullnetar Davidi u gjithashtu vënë në dukje.

101
00:04:31,390 --> 00:04:35,440
Tani ndërsa tregues është
jo null, sepse risjell

102
00:04:35,440 --> 00:04:40,350
që null disa vlera të veçanta rojtar
Në kufirin fundin e listës,

103
00:04:40,350 --> 00:04:44,280
kështu, ndërsa unë nuk jam duke treguar në
terren si vullnetar tonë të fundit

104
00:04:44,280 --> 00:04:47,190
ishte, le të shkojë përpara
dhe të bëjë të mëposhtme.

105
00:04:47,190 --> 00:04:51,820
Nëse pointer-- dhe tani unë lloj i dua
të bëni atë që ne e bëmë me nxënësin

106
00:04:51,820 --> 00:04:57,410
structure-- nëse akrep dot ardhshëm
equals-- më tepër, në qoftë se akrep dot N barabartë

107
00:04:57,410 --> 00:05:02,290
barabartë variabli N, The
Argumenti që është miratuar në,

108
00:05:02,290 --> 00:05:05,370
atëherë unë dua të shkoj përpara
dhe thonë kthim i vërtetë.

109
00:05:05,370 --> 00:05:11,020
Unë kam gjetur numrin N brenda të
një nga nyjet e listën time të lidhur.

110
00:05:11,020 --> 00:05:13,500
Por dot nuk
punon në këtë kontekst,

111
00:05:13,500 --> 00:05:17,260
sepse akrep, PTR, është
me të vërtetë një tregues, një adresë,

112
00:05:17,260 --> 00:05:20,632
ne fakt mund mrekullisht
përdorni në fund një pjesë të sintaksës

113
00:05:20,632 --> 00:05:22,590
se lloj i bën
kuptim intuitiv dhe në fakt

114
00:05:22,590 --> 00:05:27,870
përdorni një shigjetë këtu, që do të thotë të shkojnë nga
që adresa në numrin e plotë atje në.

115
00:05:27,870 --> 00:05:30,160
Pra, kjo është shumë e ngjashme në
Fryma e dot operatori,

116
00:05:30,160 --> 00:05:33,860
por për shkak se nuk është një akrep akrep
dhe jo një vetë struct aktuale,

117
00:05:33,860 --> 00:05:35,380
ne vetëm përdorni arrow.

118
00:05:35,380 --> 00:05:40,620
>> Pra, nëse nyja aktuale që unë,
variabël i përkohshëm, jam duke treguar në

119
00:05:40,620 --> 00:05:43,060
nuk është N, çfarë unë dua të bëj?

120
00:05:43,060 --> 00:05:45,910
E pra, me vullnetarët e mia njeriut
që kemi pasur këtu ditë të tjera,

121
00:05:45,910 --> 00:05:49,710
në qoftë se njeriu i parë ime nuk është një unë
duan, dhe ndoshta e dyta njeriut nuk është

122
00:05:49,710 --> 00:05:52,660
ajo që unë dua, dhe i treti, unë
nevojë për të mbajtur fizikisht në lëvizje.

123
00:05:52,660 --> 00:05:54,690
Ashtu si mund ta hap përmes një listë?

124
00:05:54,690 --> 00:05:57,470
Kur ne kishim një rrjet, ju
vetëm e bëri si unë plus plus.

125
00:05:57,470 --> 00:06:03,660
Por në këtë rast, mjafton të
bëjnë treguesin, merr, tregues, tjetër.

126
00:06:03,660 --> 00:06:07,580
Me fjalë të tjera, fusha e ardhshme
është si të gjithë e duarve lënë

127
00:06:07,580 --> 00:06:10,880
që vullnetarët tona njerëzore të hënën
ishin përdorur për pikë në një nyje të tjera.

128
00:06:10,880 --> 00:06:12,890
Ata ishin fqinj të tyre të ardhshëm.

129
00:06:12,890 --> 00:06:17,060
>> Pra, nëse unë dua të hap nëpër këtë listë,
Unë nuk mund të bëj unë plus plus më,

130
00:06:17,060 --> 00:06:20,120
Unë në vend të kësaj duhet të them
Unë, akrep, po shkon

131
00:06:20,120 --> 00:06:24,650
të barabartë çfarëdo fushë tjetër është,
Fusha tjetër është, fusha tjetër është,

132
00:06:24,650 --> 00:06:28,350
pas të gjitha këtyre duarve lënë
që kemi pasur në skenë duke treguar

133
00:06:28,350 --> 00:06:30,000
të disa vlerave të mëvonshme.

134
00:06:30,000 --> 00:06:32,590
Dhe në qoftë se unë të marrë me
se e tërë përsëritje,

135
00:06:32,590 --> 00:06:39,330
dhe më në fund, unë goditi null mos pasur
N gjetur ende, unë vetëm kthimit të rreme.

136
00:06:39,330 --> 00:06:44,100
Pra, përsëri, të gjitha që ne jemi duke bërë këtu,
si për foto një moment më parë,

137
00:06:44,100 --> 00:06:47,840
ka filluar duke vënë në nivel
fillimi i listës me sa duket.

138
00:06:47,840 --> 00:06:50,970
Dhe atëherë unë kontrolloj, është vlera
Unë jam duke kërkuar për barabartë me nëntë?

139
00:06:50,970 --> 00:06:52,650
Nëse është kështu, unë kthehet e vërtetë dhe unë jam bërë.

140
00:06:52,650 --> 00:06:56,450
Nëse jo, unë rinovuar dorën time,
AKA akrep, në pikën

141
00:06:56,450 --> 00:06:59,540
në vend të shigjetës së ardhshme, dhe
atëherë vendndodhja arrow ardhshëm,

142
00:06:59,540 --> 00:07:00,480
dhe të ardhshëm.

143
00:07:00,480 --> 00:07:03,770
Unë jam thjesht duke ecur nëpër këtë rrjet.

144
00:07:03,770 --> 00:07:06,010
>> Pra, përsëri, i cili kujdeset?

145
00:07:06,010 --> 00:07:07,861
Ashtu si ajo që është kjo një përbërës për të?

146
00:07:07,861 --> 00:07:10,360
E pra, kujtoj se ne kemi prezantuar
nocioni i një pirg, e cila

147
00:07:10,360 --> 00:07:15,400
është një e të dhënave abstrakte shkruani për aq sa është e
nuk është një gjë C, kjo nuk është një gjë e CS50,

148
00:07:15,400 --> 00:07:19,430
kjo është një ide abstrakte, kjo ide e
stacking gjëra në krye të njëri-tjetrit

149
00:07:19,430 --> 00:07:21,820
që mund të realizohet në
bunches e mënyra të ndryshme.

150
00:07:21,820 --> 00:07:25,600
Dhe një mënyrë për të propozuar ishte me
një grup, apo me një listë të lidhura.

151
00:07:25,600 --> 00:07:29,570
Dhe kjo rezulton se canonically, një
rafte mbështet të paktën dy operacione.

152
00:07:29,570 --> 00:07:32,320
Dhe fjalë të lëvizje janë shtytje për
shtytje diçka mbi rafte,

153
00:07:32,320 --> 00:07:34,770
si një tabaka të re në
sallë ngrënie, ose pop,

154
00:07:34,770 --> 00:07:39,000
që do të thotë për të hequr larti
tabaka nga rafte në ngrënie

155
00:07:39,000 --> 00:07:41,500
sallë, dhe pastaj ndoshta disa
operacionet e tjera po ashtu.

156
00:07:41,500 --> 00:07:45,770
Pra, si mund të kemi të përcaktuar strukturën
se ne jemi tani duke e quajtur një pirg?

157
00:07:45,770 --> 00:07:50,020
>> E pra, ne kemi të gjithë të parakusht
Sintaksa në dispozicion në C. Unë them,

158
00:07:50,020 --> 00:07:53,830
më jepni një lloj përkufizim të
një struct brenda një pirg,

159
00:07:53,830 --> 00:07:58,030
Unë do të thonë se është një grup, i një
tërë bandë e numrave dhe pastaj madhësi.

160
00:07:58,030 --> 00:08:00,930
Pra, me fjalë të tjera, në qoftë se unë dua
për të zbatuar këtë në kod,

161
00:08:00,930 --> 00:08:03,830
më lejoni të shkoj dhe vetëm lloji i
të nxjerrë atë që kjo është duke thënë.

162
00:08:03,830 --> 00:08:06,317
Pra, kjo është duke thënë, më jepni një
strukturë që e mori një grup,

163
00:08:06,317 --> 00:08:09,400
dhe unë nuk e di se çfarë kapaciteti është,
kjo është me sa duket një konstante që unë kam

164
00:08:09,400 --> 00:08:10,858
përcaktuar diku tjetër, dhe kjo është në rregull.

165
00:08:10,858 --> 00:08:15,260
Por mendoj se është vetëm një,
dy, tre, katër, pesë.

166
00:08:15,260 --> 00:08:16,700
Pra Kapaciteti është 5.

167
00:08:16,700 --> 00:08:21,730
Ky element brenda mia
Struktura do të quhet numra.

168
00:08:21,730 --> 00:08:24,020
Dhe pastaj kam nevojë për një të tillë
variabël tjetër me sa duket

169
00:08:24,020 --> 00:08:27,814
quajtur madhësi që fillimisht unë jam duke shkuar
të parashikojë është nisur në zero.

170
00:08:27,814 --> 00:08:29,730
Nëse nuk ka asgjë në
rafte, madhësia është zero,

171
00:08:29,730 --> 00:08:31,420
dhe kjo është vlera të plehrave në numër.

172
00:08:31,420 --> 00:08:33,450
Unë nuk kam asnjë ide se çfarë është në atje vetëm ende.

173
00:08:33,450 --> 00:08:36,059
>> Pra, nëse unë dua të shtyjë
diçka mbi rafte,

174
00:08:36,059 --> 00:08:40,780
mendoj unë quaj shtytje funksion, dhe
Unë them të shtyjë 50, si numri 50,

175
00:08:40,780 --> 00:08:44,090
ku do ju propozojmë
I tërheq atë në këtë grup?

176
00:08:44,090 --> 00:08:47,124
Ka pesë përgjigje të ndryshme të mundshme.

177
00:08:47,124 --> 00:08:48,790
Ku ju doni të shtyjë numrin 50?

178
00:08:48,790 --> 00:08:51,899
Nëse qëllimi këtu, përsëri, e quajnë
shtytje funksion, të kalojë në një argument

179
00:08:51,899 --> 00:08:52,940
e 50, ku mund ta vënë atë?

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

181
00:08:55,680 --> 00:08:59,052
Pesë possible-- shans 20%
të guessing në mënyrë korrekte.

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

183
00:08:59,896 --> 00:09:00,740
>> Audienca: Larg drejtë.

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

185
00:09:01,990 --> 00:09:08,359
Nuk është tani një shans 25%
të guessing në mënyrë korrekte.

186
00:09:08,359 --> 00:09:09,650
Pra, që në fakt do të jetë mirë.

187
00:09:09,650 --> 00:09:12,770
Nga konventë, unë do të them me një grup,
ne përgjithësi do të fillojë në të majtë,

188
00:09:12,770 --> 00:09:14,519
por ne mund sigurisht
të fillojë në të djathtë.

189
00:09:14,519 --> 00:09:17,478
Pra, spoiler këtu do të jetë unë jam
me siguri do të tërheqë atë në të majtë,

190
00:09:17,478 --> 00:09:20,060
ashtu si në një grup normale, ku
Unë të fillojnë të shkojnë majta në të djathtë.

191
00:09:20,060 --> 00:09:21,780
Por në qoftë se ju mund të shfletoj
aritmetike, gjobë.

192
00:09:21,780 --> 00:09:23,060
Kjo nuk është vetëm konvencionale.

193
00:09:23,060 --> 00:09:24,880
OK, unë duhet të bëjë një
më shumë ndryshim pse.

194
00:09:24,880 --> 00:09:27,710
Tani që unë e kam shtyrë diçka
mbi rafte, çfarë e ardhshme?

195
00:09:27,710 --> 00:09:29,400
>> Të gjithë të drejtë, unë kam për të ardhura madhësinë.

196
00:09:29,400 --> 00:09:32,600
Pra më lejoni të shkoj përpara dhe vetëm
Përditëso kjo, e cila ishte zero.

197
00:09:32,600 --> 00:09:35,950
Dhe në vend që tani, unë jam duke shkuar
për të vënë në vlerën e një.

198
00:09:35,950 --> 00:09:39,460
Dhe tani mendoj unë të shtyjë një tjetër
Numri i mbi rafte, si 51.

199
00:09:39,460 --> 00:09:42,680
E pra, unë kam për të bërë një më shumë
ndryshimi, e cila është deri në madhësi dy.

200
00:09:42,680 --> 00:09:46,100
Dhe pastaj mendoj unë të shtyjë një më shumë
Numri i mbi rafte si 61,

201
00:09:46,100 --> 00:09:52,530
tani kam nevojë për të rinovuar madhësinë një më shumë
kohë, dhe për të marrë vlerën 3 si madhësia.

202
00:09:52,530 --> 00:09:54,690
Dhe tani mendoj unë e quaj pop.

203
00:09:54,690 --> 00:09:57,250
Tani pop, nga konventa,
nuk ka marrë një argument.

204
00:09:57,250 --> 00:10:00,430
Me një pirg, e tërë
Pika e metaforës tray

205
00:10:00,430 --> 00:10:03,450
është se ju nuk keni liri
për të shkuar të marrë atë tabaka, të gjithë ju mund të bëni

206
00:10:03,450 --> 00:10:06,330
është pop atë larti nga
rafte, vetëm për shkak se.

207
00:10:06,330 --> 00:10:08,010
Kjo është ajo që kjo strukturë të dhëna bën.

208
00:10:08,010 --> 00:10:12,250
>> Pra, nga kjo logjikë, nëse unë
thonë pop, çfarë vjen off?

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

210
00:10:13,080 --> 00:10:15,402
Pra, çfarë është me të vërtetë kompjuteri
do të bëni në kujtesë?

211
00:10:15,402 --> 00:10:16,610
Çfarë ka kodi im duhet të bëni?

212
00:10:16,610 --> 00:10:20,330
Çfarë do të propozojë
ne të ndryshojë në ekran?

213
00:10:20,330 --> 00:10:23,410
Çfarë duhet të ndryshojë?

214
00:10:23,410 --> 00:10:24,960
Na vjen keq?

215
00:10:24,960 --> 00:10:26,334
Pra, ne të shpëtoj nga 61.

216
00:10:26,334 --> 00:10:27,500
Kështu që unë mund të patjetër të bëjë atë.

217
00:10:27,500 --> 00:10:28,640
Dhe unë mund të shpëtoj prej 61.

218
00:10:28,640 --> 00:10:30,980
Dhe pastaj çfarë tjetër
ndryshimi duhet të ndodhë?

219
00:10:30,980 --> 00:10:33,160
Madhësia e ndoshta ka për të shkuar mbrapa në dy.

220
00:10:33,160 --> 00:10:34,210
Dhe kështu kjo është në rregull.

221
00:10:34,210 --> 00:10:36,690
Por prisni një minutë, madhësi
një moment më parë ishte tre.

222
00:10:36,690 --> 00:10:38,240
Le të vetëm të bëjë një kontroll të shpejtë mendje e shëndoshë.

223
00:10:38,240 --> 00:10:41,810
Si e dimë se ne
donte për të hequr qafe të 61?

224
00:10:41,810 --> 00:10:42,760
Sepse ne jemi duke popping.

225
00:10:42,760 --> 00:10:46,450
Dhe kështu që unë kam këtë madhësi të dytë të pronës.

226
00:10:46,450 --> 00:10:48,470
>> Prisni një minutë, unë jam
të menduarit prapa në javën e dytë

227
00:10:48,470 --> 00:10:51,660
kur kemi filluar duke folur për
vargjeve, ku kjo ishte vend zero,

228
00:10:51,660 --> 00:10:55,920
kjo ishte një vend, kjo ishte vend
dy, kjo është vendndodhja tre, katër,

229
00:10:55,920 --> 00:10:58,460
kjo duket si
Marrëdhënia në mes të madhësisë

230
00:10:58,460 --> 00:11:02,780
dhe elementi që unë dua për të hequr
nga array duket të jetë vetëm çfarë?

231
00:11:02,780 --> 00:11:05,120
Madhësia minus një.

232
00:11:05,120 --> 00:11:07,786
Dhe kështu kjo është se si si njerëzit
ne e dimë se 61 vjen e para.

233
00:11:07,786 --> 00:11:09,160
Si është kompjuteri do të di?

234
00:11:09,160 --> 00:11:11,701
Kur kodin tuaj, ku ju ndoshta
doni të bëni një madhësi minus,

235
00:11:11,701 --> 00:11:14,950
kështu tre minus një është dy dhe që
do të thotë që ne duam të heqin qafe e 61.

236
00:11:14,950 --> 00:11:18,000
Dhe pastaj ne vërtet mund të rinovuar
madhësia kështu që madhësia tani

237
00:11:18,000 --> 00:11:20,300
shkon nga tre deri në vetëm dy.

238
00:11:20,300 --> 00:11:24,520
Dhe vetëm të jetë pedant, unë jam duke shkuar
të propozojë që unë jam duke bërë, e drejtë?

239
00:11:24,520 --> 00:11:27,660
Ju propozuar intuitivisht
korrekt unë duhet të heqin qafe e 61.

240
00:11:27,660 --> 00:11:30,700
Por nuk e kanë unë lloj i
lloj i marrë shpëtoj prej 61?

241
00:11:30,700 --> 00:11:33,790
Unë e kam harruar në mënyrë efektive
se kjo është në të vërtetë atje.

242
00:11:33,790 --> 00:11:37,680
Dhe mendoj se mbrapa për PSET4, në qoftë se ju keni lexuar
artikulli për mjekësinë ligjore, PDF

243
00:11:37,680 --> 00:11:40,780
që kemi pasur ju djema lexuar, apo ju
do të lexoni këtë javë për PSET4.

244
00:11:40,780 --> 00:11:44,300
Kujtojnë se kjo është në fakt përshtatshëm për
e gjithë ideja e kompjuterit mjekësinë ligjore.

245
00:11:44,300 --> 00:11:47,820
Çfarë një kompjuter në përgjithësi nuk është
ai thjesht harron aty ku diçka është,

246
00:11:47,820 --> 00:11:51,300
por kjo nuk do të shkojnë në dhe si
përpiqen për të zeroja atë apo refuzo

247
00:11:51,300 --> 00:11:54,560
ato pjesë me zero dhe ato
apo ndonjë model tjetër të rastit

248
00:11:54,560 --> 00:11:56,690
nëse ju vetë ta bërë këtë qëllimisht.

249
00:11:56,690 --> 00:11:58,930
Pra, intuita juaj ka qenë
e drejtë, le të heqin qafe e 61.

250
00:11:58,930 --> 00:12:00,650
Por në realitet, ne nuk duhet të shqetësojë.

251
00:12:00,650 --> 00:12:04,040
Ne vetëm duhet të harrojmë se
është atje duke ndryshuar madhësinë tonë.

252
00:12:04,040 --> 00:12:05,662
>> Tani ka një problem me këtë rafte.

253
00:12:05,662 --> 00:12:07,620
Nëse unë mbaj shtyjnë gjërat
mbi rafte, çfarë është

254
00:12:07,620 --> 00:12:11,167
padyshim do të ndodhë
në vetëm një kohë pak momente?

255
00:12:11,167 --> 00:12:12,500
Ne jemi duke shkuar për të drejtuar nga hapësira.

256
00:12:12,500 --> 00:12:13,580
Dhe çfarë bëjmë ne?

257
00:12:13,580 --> 00:12:14,680
Ne jemi lloj i dehur.

258
00:12:14,680 --> 00:12:19,000
Ky zbatim nuk do të le
na resize array, sepse duke përdorur

259
00:12:19,000 --> 00:12:21,240
kjo sintaksë, në qoftë se ju
mendoj se mbrapa në javën e dytë,

260
00:12:21,240 --> 00:12:23,520
një herë ju keni deklaruar
madhësia e një grup,

261
00:12:23,520 --> 00:12:26,780
ne nuk kemi parë ende një mekanizëm ku
ju mund të ndryshojë madhësinë e vektorit.

262
00:12:26,780 --> 00:12:29,020
Dhe me të vërtetë C nuk e ka atë funksion.

263
00:12:29,020 --> 00:12:32,524
Në qoftë se ju thoni Më jep pesë
Nths, i thirrët ata numrat,

264
00:12:32,524 --> 00:12:33,940
kjo është e gjitha që ju jeni do të merrni atë.

265
00:12:33,940 --> 00:12:38,790
Pra, ne bëjmë tani si nga e hëna, kanë
aftësia për të shprehur një zgjidhje

266
00:12:38,790 --> 00:12:42,480
edhe pse, ne vetëm duhet të shkulje
përkufizimi i rafte tonë

267
00:12:42,480 --> 00:12:46,840
të mos jetë një grup i vështirë-koduar,
por vetëm për të ruajtur një adresë.

268
00:12:46,840 --> 00:12:47,890
>> Tani pse është kjo?

269
00:12:47,890 --> 00:12:51,690
Tani ne vetëm duhet të jenë të kënaqur me
fakti që kur programi im shkon,

270
00:12:51,690 --> 00:12:53,730
Unë jam me sa duket duke shkuar për të
duhet të pyesni njerëzore,

271
00:12:53,730 --> 00:12:55,110
Sa numra nuk ju duan për të ruajtur?

272
00:12:55,110 --> 00:12:56,776
Pra, të dhëna duhet të vijë nga diku.

273
00:12:56,776 --> 00:12:59,140
Por një herë unë e di se
numrin, atëherë unë mund vetëm

274
00:12:59,140 --> 00:13:02,470
përdorin atë që të funksionojë për të dhënë
mua një copë e kujtesës?

275
00:13:02,470 --> 00:13:03,580
Unë mund të përdorin malloc.

276
00:13:03,580 --> 00:13:06,710
Dhe unë mund të them ndonjë numër të
bytes Unë dua përsëri për këto Nths.

277
00:13:06,710 --> 00:13:10,910
Dhe të gjitha unë kam për të ruajtur në numrat
ndryshueshme këtu brenda këtij struct

278
00:13:10,910 --> 00:13:13,480
duhet të jetë ajo?

279
00:13:13,480 --> 00:13:18,440
Çfarë në të vërtetë shkon në të
numrat në këtë skenar?

280
00:13:18,440 --> 00:13:21,300
Po, një tregues për të parë
byte e atij copë e kujtesës,

281
00:13:21,300 --> 00:13:24,940
ose më saktë, adresa
nga të parët e këtyre bytes.

282
00:13:24,940 --> 00:13:27,300
Nuk ka rëndësi nëse është një
byte ose një miliardë bytes,

283
00:13:27,300 --> 00:13:28,890
Unë vetëm duhet të kujdesen për të parë.

284
00:13:28,890 --> 00:13:31,530
Sepse ajo që garanton malloc dhe
mi garanton sistemit operativ,

285
00:13:31,530 --> 00:13:34,170
është se copë e kujtesës I
merrni, ajo do të jetë e afërt.

286
00:13:34,170 --> 00:13:35,378
Nuk do të jetë boshllëqe.

287
00:13:35,378 --> 00:13:38,576
Pra, nëse unë kam kërkuar për 50
bytes ose 1,000 bytes,

288
00:13:38,576 --> 00:13:40,450
ata të gjithë do të jenë të
për të kthyer prapa në shpinë.

289
00:13:40,450 --> 00:13:44,500
Dhe për aq kohë sa unë kujtoj se sa i madh, sa
shumë i kërkuar, të gjitha unë duhet të dini

290
00:13:44,500 --> 00:13:46,230
është adresa e parë e tillë.

291
00:13:46,230 --> 00:13:48,660
>> Deri tani ne kemi aftësinë në kod.

292
00:13:48,660 --> 00:13:51,280
Megjithëse, ajo do të na
më shumë kohë për të shkruar këtë ide,

293
00:13:51,280 --> 00:13:55,900
ne tani mund të shpërndajnë atë kujtesën nga
vetëm ruajtjen e një adresë tjetër atje

294
00:13:55,900 --> 00:13:59,060
në qoftë se ne duam një të madhe apo edhe të
një copë të vogël të kujtesës.

295
00:13:59,060 --> 00:14:00,170
Kështu që këtu për një off tregtisë.

296
00:14:00,170 --> 00:14:01,360
Tani kemi marrë dinamizëm.

297
00:14:01,360 --> 00:14:03,350
Ne ende kemi
contiguousness Unë jam duke pretenduar.

298
00:14:03,350 --> 00:14:05,881
Sepse malloc do të na japë
një copë puqur e kujtesës.

299
00:14:05,881 --> 00:14:08,630
Por kjo do të jetë një dhimbje në
qafa për ne, programues,

300
00:14:08,630 --> 00:14:09,770
që në fakt të kodit lart.

301
00:14:09,770 --> 00:14:10,730
Kjo është vetëm më shumë punë.

302
00:14:10,730 --> 00:14:13,930
Ne kemi nevojë për kodin ngjashme me atë që unë kam qenë
banging jashtë vetëm një moment më parë.

303
00:14:13,930 --> 00:14:16,120
Shumë që mund të bëhet, por ajo shton kompleksitetin.

304
00:14:16,120 --> 00:14:19,520
Dhe kështu kohë zhvillues, programues
Ora është edhe një burim

305
00:14:19,520 --> 00:14:22,520
që ne të mund të kenë nevojë për të shpenzuar
disa kohë për të marrë tipare të reja.

306
00:14:22,520 --> 00:14:24,020
Dhe pastaj sigurisht ka një radhë.

307
00:14:24,020 --> 00:14:26,227
Ne nuk do të shkojë në këtë
një në shumë detaje.

308
00:14:26,227 --> 00:14:27,560
Por kjo është shumë e ngjashme në shpirt.

309
00:14:27,560 --> 00:14:31,220
Unë mund të zbatojë një radhë, dhe
operacionet e saj përkatëse,

310
00:14:31,220 --> 00:14:35,660
enqueue ose dequeue, si të shtoni ose hiqni,
kjo është vetëm një mënyrë për njohës të thënë atë,

311
00:14:35,660 --> 00:14:38,100
enqueue ose dequeue, si më poshtë.

312
00:14:38,100 --> 00:14:41,170
Unë vetëm mund të jap vetes një e strukturës
që përsëri ka një numër të array,

313
00:14:41,170 --> 00:14:44,000
që ka një madhësi përsëri,
por pse nuk kam nevojë për tani

314
00:14:44,000 --> 00:14:46,940
të mbajnë gjurmët e para të një radhë?

315
00:14:46,940 --> 00:14:50,630
Unë nuk duhet të dini
e përparme e rafte tim.

316
00:14:50,630 --> 00:14:53,570
E pra, në qoftë se unë sërish për një
queue-- le të vetëm e vështirë

317
00:14:53,570 --> 00:14:57,870
kodin atë si ka si pesë
integers në këtu potencialisht.

318
00:14:57,870 --> 00:15:00,940
Pra, kjo është zero, një, dy, tre, katër.

319
00:15:00,940 --> 00:15:03,430
Kjo do të jetë
quajtur numra përsëri.

320
00:15:03,430 --> 00:15:06,940
Dhe kjo do të quhet madhësi.

321
00:15:06,940 --> 00:15:10,056
>> Pse nuk mjafton
të ketë vetëm madhësi?

322
00:15:10,056 --> 00:15:11,680
E pra, le të shtyjë ato numra të njëjta në.

323
00:15:11,680 --> 00:15:14,220
Kështu që unë pushed-- unë enqueued, ose shtyrë.

324
00:15:14,220 --> 00:15:20,150
Tani unë do enqueue 50, dhe pastaj
51, dhe pastaj 61, dhe dot dot dot.

325
00:15:20,150 --> 00:15:21,070
Pra, kjo është enqueue.

326
00:15:21,070 --> 00:15:23,176
Unë enqueued 50, pastaj 51, pastaj 61.

327
00:15:23,176 --> 00:15:25,050
Dhe kjo duket identike
në një pirg deri tani,

328
00:15:25,050 --> 00:15:27,190
përveç Unë kam nevojë për të bërë një ndryshim.

329
00:15:27,190 --> 00:15:33,680
Unë kam nevojë për të rinovuar këtë madhësi, kështu që unë shkoj
nga zero në një të dy deri në tre tani.

330
00:15:33,680 --> 00:15:35,760
Si mund të dequeue?

331
00:15:35,760 --> 00:15:36,890
Çfarë ndodh me dequeue?

332
00:15:36,890 --> 00:15:41,950
Kush duhet të vijnë jashtë në këtë listë për herë të parë
në qoftë se është vija në Apple Store?

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

334
00:15:42,780 --> 00:15:44,700
Pra, kjo është lloj i komplikuar këtë herë.

335
00:15:44,700 --> 00:15:47,880
Ndërsa herën e fundit ai ishte super
lehtë për të vetëm të bëjë një madhësi minus,

336
00:15:47,880 --> 00:15:51,440
Unë shkoj në fund të array tim në mënyrë efektive
ku numrat janë, ajo heq 61.

337
00:15:51,440 --> 00:15:52,920
Por unë nuk dua për të hequr 61.

338
00:15:52,920 --> 00:15:55,030
Unë dua të të marrë 50, i cili
ishte atje at 5:00 AM

339
00:15:55,030 --> 00:15:56,790
të vijë deri për
iPhone i ri apo gjësend.

340
00:15:56,790 --> 00:16:01,200
Dhe kështu për të hequr qafe e 50, unë
nuk mund vetëm të bëjë këtë, apo jo?

341
00:16:01,200 --> 00:16:02,547
Unë mund të kalojnë nga 50.

342
00:16:02,547 --> 00:16:04,380
Por ne vetëm thamë
nuk duhet të jetë aq anal

343
00:16:04,380 --> 00:16:06,330
si për të heq nga ose fshehur të dhënat.

344
00:16:06,330 --> 00:16:08,090
Ne vetëm mund të harrojmë se ku është.

345
00:16:08,090 --> 00:16:12,330
>> Por në qoftë se unë të ndryshojë madhësinë e mia tani për
dy, është ky informacion i mjaftueshëm

346
00:16:12,330 --> 00:16:15,711
të dinë se çfarë po ndodh në radhë time?

347
00:16:15,711 --> 00:16:16,680
Jo ne te vertete.

348
00:16:16,680 --> 00:16:19,830
Ashtu si madhësia ime është dy, por
ku fillon radhë,

349
00:16:19,830 --> 00:16:22,980
veçanërisht në qoftë se unë ende kam
ato numra të njëjta në kujtesë.

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

351
00:16:24,260 --> 00:16:27,090
Kështu që unë duhet të mbani mend
tani ku front është.

352
00:16:27,090 --> 00:16:29,630
Dhe kështu si unë propozuar deri
atje, ne do të kemi quajtur vetëm

353
00:16:29,630 --> 00:16:33,729
Front n, fillestar i të cilit
Vlera duhet të ketë qenë çfarë?

354
00:16:33,729 --> 00:16:35,270
Zero, vetëm fillimi i listës.

355
00:16:35,270 --> 00:16:40,876
Por tani përveç decrementing
madhësia, ne vetëm rrisim front.

356
00:16:40,876 --> 00:16:42,000
Tani këtu është një tjetër problem.

357
00:16:42,000 --> 00:16:43,030
Pra, një herë unë do të mbajë.

358
00:16:43,030 --> 00:16:47,520
Supozoni se ky është numri i
si 121, 124, dhe pastaj, dammit,

359
00:16:47,520 --> 00:16:48,610
Unë jam nga hapësira.

360
00:16:48,610 --> 00:16:50,390
Por prisni një minutë, unë nuk jam.

361
00:16:50,390 --> 00:16:55,630
Pra, në këtë pikë në histori,
mendoj se madhësia është një, dy,

362
00:16:55,630 --> 00:17:00,370
tre, katër, kështu mendoj që
Madhësia është katër, front është një,

363
00:17:00,370 --> 00:17:01,621
kështu 51 është në para.

364
00:17:01,621 --> 00:17:04,329
Unë dua të vënë një numër tjetër këtu,
por, dammit, unë jam nga hapësira.

365
00:17:04,329 --> 00:17:06,710
Por unë nuk jam me të vërtetë, e drejtë?

366
00:17:06,710 --> 00:17:11,192
Ku mund të vërë pak
Vlera shtesë, si 171?

367
00:17:11,192 --> 00:17:13,400
Po, unë mund vetëm lloj i
kthehem atje, apo jo?

368
00:17:13,400 --> 00:17:18,161
Dhe pastaj kalojnë jashtë 50, apo
vetëm prishësh atë me 171.

369
00:17:18,161 --> 00:17:20,410
Dhe në qoftë se ju jeni të pyesin se pse
numrat tanë mori aq të rastësishme,

370
00:17:20,410 --> 00:17:24,150
këto janë marrë zakonisht kompjuter
kurse shkenca në Harvard pas CS50.

371
00:17:24,150 --> 00:17:27,510
Por kjo ishte një optimization mirë,
sepse tani unë nuk jam humbur hapësirë.

372
00:17:27,510 --> 00:17:30,750
Unë ende duhet të mbani mend
sa e madhe kjo gjë është totale.

373
00:17:30,750 --> 00:17:31,500
Kjo është pesë totale.

374
00:17:31,500 --> 00:17:33,375
Sepse unë nuk dua të
të fillojë overwriting 51.

375
00:17:33,375 --> 00:17:36,260
Kështu që tani unë jam ende jashtë hapësirës,
kështu të njëjtin problem si më parë.

376
00:17:36,260 --> 00:17:39,140
Por ju mund të shihni se si tani
në kodin tuaj, ju ndoshta

377
00:17:39,140 --> 00:17:41,910
duhet të shkruaj pak më shumë
Kompleksiteti për të bërë që të ndodhë.

378
00:17:41,910 --> 00:17:44,510
Dhe në fakt, çfarë operator
në C ndoshta lejon të

379
00:17:44,510 --> 00:17:48,110
ju magjike bëni kjo qarkore?

380
00:17:48,110 --> 00:17:50,160
Po operatori modulo,
shenjë për qind.

381
00:17:50,160 --> 00:17:53,160
Pra, çfarë është lloj i ftohtë në lidhje me radhë,
edhe pse ne të mbajë vizatim vargjeve

382
00:17:53,160 --> 00:17:56,520
si këto rreshta si të drejtë, në qoftë se ju
lloj të mendojnë për këtë si curving

383
00:17:56,520 --> 00:18:00,341
rreth si një rreth, atëherë vetëm
intuitive ai lloj i punon mendërisht

384
00:18:00,341 --> 00:18:01,590
Unë mendoj se një pak më të pastër.

385
00:18:01,590 --> 00:18:05,190
Ju ende do të duhet të zbatojë
se modeli mendor në kod.

386
00:18:05,190 --> 00:18:07,550
Pra, nuk është se e vështirë,
në fund të fundit, për të zbatuar,

387
00:18:07,550 --> 00:18:12,430
por ne ende humbasin size-- më mirë,
aftësia për të resize, nëse ne e bëjmë këtë.

388
00:18:12,430 --> 00:18:15,310
>> Ne kemi për të hequr qafe grup, ne
zëvendësuar me një tregues të vetme,

389
00:18:15,310 --> 00:18:20,010
dhe pastaj diku në kodin tim unë kam marrë
Një telefonatë çfarë funksionojë në fakt krijojnë

390
00:18:20,010 --> 00:18:23,720
array quajtur numrat?

391
00:18:23,720 --> 00:18:26,190
Malloc, ose ndonjë të ngjashëm
funksion, pikërisht.

392
00:18:26,190 --> 00:18:30,481
Çdo pyetje mbi oxhaqet apo rradhë.

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

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

395
00:18:33,657 --> 00:18:34,240
Pyetje e mirë.

396
00:18:34,240 --> 00:18:35,830
Çfarë modulo do të përdorni këtu.

397
00:18:35,830 --> 00:18:38,520
Pra në përgjithësi, kur duke përdorur
mod, ju do të bëni atë

398
00:18:38,520 --> 00:18:40,620
me madhësinë e
Struktura e tërë e të dhënave.

399
00:18:40,620 --> 00:18:44,120
Pra, diçka si pesë apo kapacitet, nëse
është konstante, është i përfshirë ndoshta.

400
00:18:44,120 --> 00:18:47,100
Por vetëm duke bërë modulo pesë
ndoshta nuk është e mjaftueshme,

401
00:18:47,100 --> 00:18:51,380
sepse ne kemi nevojë të dimë të bëjmë ne
përfundojë rreth këtu ose këtu ose këtu.

402
00:18:51,380 --> 00:18:54,160
Pra, ju jeni me siguri edhe
do të duan të përfshijë

403
00:18:54,160 --> 00:18:57,220
madhësia e sendit, ose
variabli para si.

404
00:18:57,220 --> 00:19:00,140
Pra, kjo është vetëm kjo relativisht e
shprehje e thjeshtë aritmetike,

405
00:19:00,140 --> 00:19:02,000
por modulo do të jetë përbërës kyç.

406
00:19:02,000 --> 00:19:03,330
>> Film kaq të shkurtër, nëse ju do.

407
00:19:03,330 --> 00:19:05,780
Një animacion se disa
folks në një universitet tjetër

408
00:19:05,780 --> 00:19:08,060
vënë së bashku se ne kemi
përshtatur për këtë diskutim.

409
00:19:08,060 --> 00:19:12,630
Ajo përfshin Jack mësimi i
faktet në lidhje me radhët e gjata dhe statistikat.

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

411
00:19:19,010 --> 00:19:21,890
>> FILM: Njëherë e një kohë,
atje ishte një djalë i quajtur Jack.

412
00:19:21,890 --> 00:19:25,330
Kur ai erdhi për të bërë miq,
Jack nuk kanë një aftësi.

413
00:19:25,330 --> 00:19:28,220
Kështu Jack shkoi për të biseduar me
më djalë popullor ai e dinte.

414
00:19:28,220 --> 00:19:30,920
Ai shkoi në Lou dhe e pyeti: Çfarë të bëj?

415
00:19:30,920 --> 00:19:33,400
Lou pa se shoku i tij
ishte me të vërtetë në gjendje të vështirë.

416
00:19:33,400 --> 00:19:36,050
E pra, ai filloi, vetëm
shikoni se si ju jeni të veshur.

417
00:19:36,050 --> 00:19:38,680
A nuk keni ndonjë rroba
me një vështrim të ndryshëm?

418
00:19:38,680 --> 00:19:39,660
Po, tha Jack.

419
00:19:39,660 --> 00:19:40,840
Unë i sigurt bëj.

420
00:19:40,840 --> 00:19:43,320
Ejani në shtëpinë time dhe
Unë do të tregoj ato për ju.

421
00:19:43,320 --> 00:19:44,550
Kështu ata shkuan jashtë për Jack-së.

422
00:19:44,550 --> 00:19:47,520
Dhe Jack tregoi Lou kuti
ku ai ruante të gjitha këmisha e tij,

423
00:19:47,520 --> 00:19:49,260
dhe pantallona e tij dhe çorape e tij.

424
00:19:49,260 --> 00:19:52,290
Lou tha: Unë shoh se ju keni
të gjitha rrobat tuaja në një grumbull.

425
00:19:52,290 --> 00:19:54,870
Pse nuk ju vishni disa
të tjerët herë në pak kohë?

426
00:19:54,870 --> 00:19:58,020
>> Jack tha, mirë, kur unë
hequr rrobat dhe çorape,

427
00:19:58,020 --> 00:20:00,780
I larë ato dhe të vënë
ato larg në kuti.

428
00:20:00,780 --> 00:20:03,210
Pastaj vjen e ardhshme
në mëngjes, dhe lart unë hop.

429
00:20:03,210 --> 00:20:06,380
Unë shkoj në kuti dhe për të marrë
rrobat e mia off krye.

430
00:20:06,380 --> 00:20:09,070
Lou kuptuan shpejt
problemi me Jack.

431
00:20:09,070 --> 00:20:12,080
Ai e mbajti rroba, CD,
dhe libra në rafte.

432
00:20:12,080 --> 00:20:14,420
Kur ai arriti për
diçka për të lexuar ose të veshin,

433
00:20:14,420 --> 00:20:17,100
ai do të zgjedhin librin lartë ose të brendshme.

434
00:20:17,100 --> 00:20:19,500
Atëherë kur ai ishte bërë, ai
do të vënë atë të drejtë përsëri.

435
00:20:19,500 --> 00:20:21,970
Kthehu ajo do të shkojë, në krye të rafte.

436
00:20:21,970 --> 00:20:24,460
Unë e di zgjidhje,
tha një Loud triumfuese.

437
00:20:24,460 --> 00:20:27,090
Ju duhet të mësoni për të
të fillojë duke përdorur një radhë.

438
00:20:27,090 --> 00:20:29,870
Lou mori rrobat e Jack dhe
varur ato në dollap.

439
00:20:29,870 --> 00:20:32,710
Dhe kur ai kishte zbrazur
kuti, ai vetëm flak atë.

440
00:20:32,710 --> 00:20:36,500
>> Pastaj ai tha: tani Jack, në fund të
ditë, të vënë rrobat tuaja të majtë

441
00:20:36,500 --> 00:20:37,990
kur ju vënë ato larg.

442
00:20:37,990 --> 00:20:41,300
Pastaj nesër në mëngjes, kur ju
shih kohë e mirë, të merrni rrobat tuaja

443
00:20:41,300 --> 00:20:43,440
në të djathtë, nga fund të linjës.

444
00:20:43,440 --> 00:20:44,880
A nuk e sheh? tha Lou.

445
00:20:44,880 --> 00:20:46,370
Ajo do të jetë aq e bukur.

446
00:20:46,370 --> 00:20:49,770
Ju do të veshin çdo gjë herë
para se të veshin diçka të dy herë.

447
00:20:49,770 --> 00:20:52,670
Dhe me çdo gjë në rradhë
në dollap e tij dhe raft,

448
00:20:52,670 --> 00:20:55,160
Jack filluar të ndihen
mjaft i sigurt për veten e tij.

449
00:20:55,160 --> 00:20:59,720
Të gjitha në sajë të Lou dhe
radhë e tij të mrekullueshme.

450
00:20:59,720 --> 00:21:01,220
SPEAKER 1: Të gjithë të drejtë, kjo është adorable.

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

452
00:21:05,920 --> 00:21:10,080
Pra, ajo që është me të vërtetë ndodh
në nën kapuç tani?

453
00:21:10,080 --> 00:21:12,370
Se ne kemi pointers,
se ne kemi malloc,

454
00:21:12,370 --> 00:21:15,680
se ne kemi aftësinë për të krijuar
chunks e kujtesës për veten

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

456
00:21:16,344 --> 00:21:18,510
Pra, kjo është një foto ne
glimpsed vetëm ditë të tjera.

457
00:21:18,510 --> 00:21:21,180
Ne të vërtetë nuk banojnë
në të, por kjo foto

458
00:21:21,180 --> 00:21:24,180
ka qenë duke shkuar në nën
individualitet për disa javë tani.

459
00:21:24,180 --> 00:21:27,050
Dhe kështu kjo paraqet, vetëm
një drejtkëndësh që ne i kemi tërhequr,

460
00:21:27,050 --> 00:21:28,180
memorie kompjuteri juaj.

461
00:21:28,180 --> 00:21:31,850
Dhe ndoshta kompjuteri juaj, ose CS50
ID, ka një Gigabyte e kujtesës ose RAM

462
00:21:31,850 --> 00:21:33,050
apo dy gigabajt apo katër.

463
00:21:33,050 --> 00:21:34,450
Kjo nuk ka rëndësi.

464
00:21:34,450 --> 00:21:37,240
Sistemi juaj operativ
Windows apo Mac OS apo Linux,

465
00:21:37,240 --> 00:21:41,120
në thelb lejon programin tuaj
të mendojnë se ajo ka qasje

466
00:21:41,120 --> 00:21:42,982
në tërësinë e
memorie kompjuteri juaj,

467
00:21:42,982 --> 00:21:45,440
edhe pse ju mund të konkurrojnë
programe të shumta në të njëjtën kohë.

468
00:21:45,440 --> 00:21:46,990
Pra, në realitet, kjo nuk ka të vërtetë punojnë.

469
00:21:46,990 --> 00:21:49,448
Por kjo është lloj i një iluzion
dhënë për të gjitha programet tuaja.

470
00:21:49,448 --> 00:21:53,110
Pra, nëse keni pasur dy koncerte e RAM, kjo
është se si kompjuteri mund të mendoj për atë.

471
00:21:53,110 --> 00:21:57,110
>> Tani rastësisht, një nga këto
gjëra, njëra prej këtyre segmenteve të kujtesës,

472
00:21:57,110 --> 00:21:58,350
quhet një pirg.

473
00:21:58,350 --> 00:22:01,680
Dhe në të vërtetë në çdo kohë
deri më tani në kodin shkrim

474
00:22:01,680 --> 00:22:05,900
që ju kanë quajtur një
funksion, për shembull Main.

475
00:22:05,900 --> 00:22:08,410
Kujtojnë se çdo herë që unë kam
memorie kompjuteri tërhequr së,

476
00:22:08,410 --> 00:22:10,640
Unë gjithmonë të tërheqë lloj i
gjysma e një drejtkëndësh këtu

477
00:22:10,640 --> 00:22:12,520
dhe nuk e mërzit duke folur
për atë që është më lart.

478
00:22:12,520 --> 00:22:15,980
Sepse kur kryesor është quajtur, unë pretendojnë
që ju të merrni këtë copë e kujtesës

479
00:22:15,980 --> 00:22:16,970
që shkon poshtë këtu.

480
00:22:16,970 --> 00:22:20,650
Dhe në qoftë se kryesore e quajti një funksion
si shkëmbim, shkëmbim dhe shkon këtu.

481
00:22:20,650 --> 00:22:23,720
Dhe kjo rezulton, se është
ku është duke përfunduar.

482
00:22:23,720 --> 00:22:26,277
Në diçka të quajtur një pirg
brenda kujtesën e kompjuterit tuaj.

483
00:22:26,277 --> 00:22:28,360
Tani në fund të ditës,
kjo është vetëm trajton.

484
00:22:28,360 --> 00:22:30,680
Është si bajt zero,
byte një, bajt 2 miliard.

485
00:22:30,680 --> 00:22:33,130
Por në qoftë se ju mendoni rreth saj
si ky objekt drejtkëndëshe,

486
00:22:33,130 --> 00:22:35,130
të gjithë ne jemi duke bërë çdo
herë ne e quajmë një funksion është

487
00:22:35,130 --> 00:22:37,180
layering një fetë të ri të kujtesës.

488
00:22:37,180 --> 00:22:41,700
Ne jemi duke i dhënë këtë funksion një fetë
e kujtesës së vet për të punuar me të.

489
00:22:41,700 --> 00:22:44,490
>> Dhe kujtoj tani se kjo është e rëndësishme.

490
00:22:44,490 --> 00:22:46,400
Sepse në qoftë se ne kemi
diçka si shkëmbim

491
00:22:46,400 --> 00:22:51,610
dhe dy variabla lokale si A dhe B dhe
ne të ndryshojë këto vlera nga një dhe dy

492
00:22:51,610 --> 00:22:55,130
për të dy dhe një, kujtojnë
se kur shkëmbim të kthehet,

493
00:22:55,130 --> 00:22:58,330
kjo është sikur ky fetë
e kujtesës është zhdukur vetëm.

494
00:22:58,330 --> 00:23:00,080
Në realitet, ajo është ende e
atje nga mjekësia ligjore.

495
00:23:00,080 --> 00:23:01,940
Dhe diçka është ende në të vërtetë atje.

496
00:23:01,940 --> 00:23:05,410
Por konceptualisht, është si të
edhe pse kjo është zhdukur plotësisht.

497
00:23:05,410 --> 00:23:10,910
Dhe kështu kryesor nuk di ndonjë nga puna
që është bërë në këtë funksion swap,

498
00:23:10,910 --> 00:23:14,890
nëse është e kaluar në të vërtetë në ato
Argumentet nga akrep ose me referencë.

499
00:23:14,890 --> 00:23:17,790
Tani, zgjidhja themelore
për këtë problem me shkëmbim

500
00:23:17,790 --> 00:23:19,970
po kalon gjërat në me adresë.

501
00:23:19,970 --> 00:23:23,250
Por kjo rezulton, gjithashtu, se çfarë është
qenë duke shkuar në mbi atë pjesë

502
00:23:23,250 --> 00:23:26,330
e drejtkëndësh gjithë kjo kohë është
ende nuk ka më shumë memorie deri atje.

503
00:23:26,330 --> 00:23:28,790
Dhe kur ju dinamike
të siguroj kujtesë,

504
00:23:28,790 --> 00:23:32,020
nëse kjo është brenda e getString, e cila
ne kemi qenë bërë për ju në CS50

505
00:23:32,020 --> 00:23:34,710
bibliotekë, ose në qoftë se ju djema
thërrasë malloc dhe të kërkojë

506
00:23:34,710 --> 00:23:37,950
sistemi operativ për një copë të
kujtesës, kjo nuk vjen nga rafte.

507
00:23:37,950 --> 00:23:40,960
Ajo vjen nga një vend tjetër
në kujtesën e kompjuterit tuaj

508
00:23:40,960 --> 00:23:42,220
që është quajtur grumbull.

509
00:23:42,220 --> 00:23:43,430
Dhe kjo nuk është ndryshe.

510
00:23:43,430 --> 00:23:44,285
Është e njëjta RAM.

511
00:23:44,285 --> 00:23:45,160
Është e njëjta kujtesës.

512
00:23:45,160 --> 00:23:49,080
Është vetëm RAM që është deri
atje në vend të poshtë këtu.

513
00:23:49,080 --> 00:23:50,750
>> Dhe kështu çfarë do të thotë?

514
00:23:50,750 --> 00:23:53,650
E pra, në qoftë se kompjuteri juaj ka
një sasi e caktuar e kujtesës

515
00:23:53,650 --> 00:23:57,450
dhe rafte është në rritje deri, kështu që
për të folur, dhe tog, sipas

516
00:23:57,450 --> 00:23:59,349
në këtë shigjetë, po rritet poshtë.

517
00:23:59,349 --> 00:24:01,140
Me fjalë të tjera, çdo
herë ju e quani malloc,

518
00:24:01,140 --> 00:24:03,430
ju jeni duke i dhënë një fetë
e kujtesës nga lart,

519
00:24:03,430 --> 00:24:06,630
atëherë ndoshta pak më e ulët, atëherë pak
më të ulët, çdo herë që ju e quani malloc,

520
00:24:06,630 --> 00:24:10,100
tog, është përdorimi,
është lloj i në rritje,

521
00:24:10,100 --> 00:24:11,950
rritje afër dhe më afër për çfarë?

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

523
00:24:13,382 --> 00:24:14,840
Pra, e bën këtë të duket si një ide e mirë?

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

525
00:24:18,420 --> 00:24:22,140
Unë do të thotë, kur kjo nuk është e vërtetë e qartë
çfarë tjetër që ju mund të bëni nëse ju vetëm

526
00:24:22,140 --> 00:24:23,910
kanë një sasi e fundme e kujtesës.

527
00:24:23,910 --> 00:24:25,200
Por kjo është sigurisht e keqe.

528
00:24:25,200 --> 00:24:27,920
Këto dy shigjetat janë nga një
përplasje kurs për njëri-tjetrin.

529
00:24:27,920 --> 00:24:31,930
>> Dhe kjo rezulton se djalë i keq, njerëzit që
janë veçanërisht të mira me programimin,

530
00:24:31,930 --> 00:24:36,140
dhe duke u përpjekur të kollitem në kompjuterë,
mund të shfrytëzojnë këtë realitet.

531
00:24:36,140 --> 00:24:38,290
Në fakt, le të konsiderojmë
një copë të vogël.

532
00:24:38,290 --> 00:24:41,350
Pra, ky është një shembull ju mund të lexoni
për më në detaje në Wikipedia.

533
00:24:41,350 --> 00:24:43,100
Ne do të ju pikë në nivel
neni nëse kurioz.

534
00:24:43,100 --> 00:24:45,650
Por ka një sulm në përgjithësi
i njohur si tampon del nga shtrati se

535
00:24:45,650 --> 00:24:49,570
ka ekzistuar për aq kohë sa njerëzit
kanë pasur aftësinë për të manipuluar

536
00:24:49,570 --> 00:24:53,120
memorie kompjuteri, veçanërisht në C.
Pra, ky është një program shumë arbitrare,

537
00:24:53,120 --> 00:24:55,130
por le të lexojnë atë nga poshte lart.

538
00:24:55,130 --> 00:24:57,650
Kryesor në yll argc char argv.

539
00:24:57,650 --> 00:24:59,830
Pra, kjo është një program që merr
argumente command line.

540
00:24:59,830 --> 00:25:03,620
Dhe të gjithë kryesor ka me sa duket është thirrja
një funksion, e quajti atë F për thjeshtësi.

541
00:25:03,620 --> 00:25:04,610
Dhe ai kalon në çfarë?

542
00:25:04,610 --> 00:25:05,490
Argv e një.

543
00:25:05,490 --> 00:25:09,320
Pra, ai kalon në F çfarëdo
fjala është se përdoruesi shtypur

544
00:25:09,320 --> 00:25:11,500
në ftim pas fillimit
Emri i programit në të gjitha.

545
00:25:11,500 --> 00:25:15,730
Aq shumë si Cezarit apo Vigenere, e cila
ju mund të kujtojnë bërë me argv.

546
00:25:15,730 --> 00:25:16,680
>> Pra, çfarë është F?

547
00:25:16,680 --> 00:25:19,760
F merr në një varg
si argument e tij të vetëm,

548
00:25:19,760 --> 00:25:22,100
AKA një yll char, njëjtë
gjë, si një varg.

549
00:25:22,100 --> 00:25:24,920
Dhe ajo që quhet në mënyrë arbitrare
bar në këtë shembull.

550
00:25:24,920 --> 00:25:27,710
Dhe pastaj char c 12,
vetëm në kushtet e laik,

551
00:25:27,710 --> 00:25:31,750
ajo që është char c parantezë 12 duke bërë për ne?

552
00:25:31,750 --> 00:25:33,440
Çfarë të bëjë?

553
00:25:33,440 --> 00:25:36,490
Caktimin e kujtesës, veçanërisht
12 bytes për 12 karaktere.

554
00:25:36,490 --> 00:25:36,990
Pikërisht.

555
00:25:36,990 --> 00:25:40,000
Dhe pastaj vija e fundit, llokoçis dhe
kopje, ju keni ndoshta nuk shihet.

556
00:25:40,000 --> 00:25:43,360
Kjo është një kopje varg
funksioni qëllimi i të cilit në jetë

557
00:25:43,360 --> 00:25:48,160
është të kopjoni argumentin e tij të dytë
në argumentin e saj të parë,

558
00:25:48,160 --> 00:25:51,190
por vetëm deri në një
numër i caktuar i bytes.

559
00:25:51,190 --> 00:25:53,860
Pra, argumenti i tretë thotë:
Sa bytes duhet të kopjoni?

560
00:25:53,860 --> 00:25:56,720
Gjatësia e bar,
çfarëdo përdoruesi shtypur në.

561
00:25:56,720 --> 00:25:59,320
Dhe përmbajtjen e
bar, atë varg, janë

562
00:25:59,320 --> 00:26:02,330
kopjuar në kujtesën vuri në në C.

563
00:26:02,330 --> 00:26:04,060
>> Pra, kjo duket lloj i trashë, dhe kjo është.

564
00:26:04,060 --> 00:26:06,300
Kjo është një shembull i ndërtuar,
por kjo është përfaqësuese

565
00:26:06,300 --> 00:26:10,100
e një klase të vektorëve sulm,
një mënyrë për të sulmuar një program.

566
00:26:10,100 --> 00:26:15,050
Të gjitha është e mirë dhe e mirë në qoftë se përdoruesi
lloje në një fjalë që është 11 karaktere

567
00:26:15,050 --> 00:26:18,040
ose më pak, plus backslash zero.

568
00:26:18,040 --> 00:26:22,830
Çfarë ndodh nëse lloje përdorues në më shumë se
11 ose 12 ose 20 ose 50 karaktere?

569
00:26:22,830 --> 00:26:25,090
Çfarë është ky program do të bëni?

570
00:26:25,090 --> 00:26:29,360
Faji Potencialisht seg. Po shkon
për të verbërisht kopje çdo gjë në bar deri

571
00:26:29,360 --> 00:26:31,750
në gjatësinë e saj, e cila është
fjalë për fjalë çdo gjë në bar,

572
00:26:31,750 --> 00:26:36,307
në adresën e vuri në C. Por C
vetëm i ka dhënë preemptively si 12 bytes.

573
00:26:36,307 --> 00:26:37,640
Por nuk ka asnjë kontroll shtesë.

574
00:26:37,640 --> 00:26:38,700
Nuk ka nëse kushte.

575
00:26:38,700 --> 00:26:40,580
Nuk ka gabim kontrolluar këtu.

576
00:26:40,580 --> 00:26:43,270
>> Dhe kështu ajo që ky program është
do të bëni është vetëm verbërisht

577
00:26:43,270 --> 00:26:45,750
kopjoni një gjë në tjetrën.

578
00:26:45,750 --> 00:26:47,880
Dhe kështu që nëse ne tërheqim këtë
si një foto, këtu është

579
00:26:47,880 --> 00:26:49,860
vetëm një copë të hapësirës kujtesës.

580
00:26:49,860 --> 00:26:53,470
Pra, vini re në fund, ne
kanë bar lokal ndryshueshme.

581
00:26:53,470 --> 00:26:57,330
Kështu që pointer që po ndodh për të store--
më tepër këtë argument lokal që është

582
00:26:57,330 --> 00:26:58,672
duke shkuar për të ruajtur bar string.

583
00:26:58,672 --> 00:27:00,380
Dhe pastaj vini re vetëm
sipër në një pirg,

584
00:27:00,380 --> 00:27:02,505
sepse çdo herë që ju kërkoni
për kujtesën në rafte,

585
00:27:02,505 --> 00:27:04,310
ajo shkon pak
mbi të në pikturë,

586
00:27:04,310 --> 00:27:06,270
njoftim se ne kemi marrë 12 bytes atje.

587
00:27:06,270 --> 00:27:10,690
Një e sipërm të majtë është C kllapa zero dhe
një e drejtë fund është C kllapa 11.

588
00:27:10,690 --> 00:27:12,870
Kjo është vetëm se si kompjuterët
duke shkuar për të hedhur atë jashtë.

589
00:27:12,870 --> 00:27:18,300
Pra, vetëm intuitive, nëse bar ka më shumë
se 12 karaktere në total, duke përfshirë

590
00:27:18,300 --> 00:27:25,790
backslash zero, ku është
12 ose kllapa C 12 do të shkojnë?

591
00:27:25,790 --> 00:27:28,440
Ose më mirë ku është 12
karakter ose karakteri 13,

592
00:27:28,440 --> 00:27:30,900
karakteri njëqindtë shkuar
të përfundojnë në foto?

593
00:27:30,900 --> 00:27:33,400
Mbi ose nën?

594
00:27:33,400 --> 00:27:36,300
>> E drejtë, sepse edhe pse
rafte vetë rritet lart,

595
00:27:36,300 --> 00:27:39,590
një herë ju keni vënë gjëra në
ajo, kjo për arsye të projektimit,

596
00:27:39,590 --> 00:27:41,294
vë kujtesën nga lart poshtë.

597
00:27:41,294 --> 00:27:44,460
Pra, nëse keni më shumë se 12 bytes,
ju jeni do të fillojnë të prishësh bar.

598
00:27:44,460 --> 00:27:47,280
Tani që është një bug, por kjo është
jo me të vërtetë një punë e madhe.

599
00:27:47,280 --> 00:27:51,130
Por kjo është një punë e madhe, sepse nuk ka
më shumë gjëra në vazhdim e sipër në kujtesë.

600
00:27:51,130 --> 00:27:53,074
Kështu që këtu është se si ne mund
vënë përshëndetje, të jetë i qartë.

601
00:27:53,074 --> 00:27:54,490
Nëse unë shtypur në përshëndetje në ftim.

602
00:27:54,490 --> 00:27:59,330
H-E-L-L-O backslash zero, mbaron brenda
këto 12 bytes, dhe ne jemi super të sigurt.

603
00:27:59,330 --> 00:28:00,330
Gjithcka eshte mire.

604
00:28:00,330 --> 00:28:03,020
Por në qoftë se unë lloji diçka
gjatë, potencialisht është

605
00:28:03,020 --> 00:28:05,860
do të na zvarrisë në hapësirë ​​bar.

606
00:28:05,860 --> 00:28:08,405
Por më keq akoma, ajo kthehet
jashtë gjithë kësaj kohe,

607
00:28:08,405 --> 00:28:11,530
edhe pse ne kurrë nuk kam biseduar për
ajo, rafte është përdorur për gjëra të tjera.

608
00:28:11,530 --> 00:28:13,560
Kjo nuk është vetëm ndryshoret lokale.

609
00:28:13,560 --> 00:28:15,100
>> C është një gjuhë nivel shumë të ulët.

610
00:28:15,100 --> 00:28:17,810
Dhe kjo lloj fshehurazi
përdor rafte edhe

611
00:28:17,810 --> 00:28:21,260
për të kujtuar kur një
Funksioni quhet, çfarë

612
00:28:21,260 --> 00:28:26,040
adresa është e funksionit të mëparshëm,
kështu që mund të hidhen përsëri në atë funksion.

613
00:28:26,040 --> 00:28:29,980
Pra, kur thirrjet kryesore të bie në ujdi, në mesin e
gjërat e shtyrë mbi rafte

614
00:28:29,980 --> 00:28:34,380
nuk janë vetëm këmbime ndryshoret lokale,
ose argumentet e saj, gjithashtu shtyu fshehurazi

615
00:28:34,380 --> 00:28:37,510
mbi rafte si të përfaqësuar
nga fetë e kuqe këtu,

616
00:28:37,510 --> 00:28:40,520
është adresa e kryesor fizikisht
në kujtesën e kompjuterit tuaj,

617
00:28:40,520 --> 00:28:44,180
kështu që kur shkëmbim është bërë, kompjuteri
e di se kam nevojë për të shkuar mbrapa në kryesore

618
00:28:44,180 --> 00:28:46,760
dhe të përfundojë ekzekutimin e funksionit kryesor.

619
00:28:46,760 --> 00:28:51,960
Pra, kjo është e rrezikshme tani, sepse në qoftë se
lloje përdorues në edhe më shumë se përshëndetje,

620
00:28:51,960 --> 00:28:57,030
të tilla që input të përdoruesit clobbers
ose overwrites atë pjesë të kuqe,

621
00:28:57,030 --> 00:28:59,820
logjikisht nëse kompjuteri-së
vetëm duke shkuar për të marrë verbërisht

622
00:28:59,820 --> 00:29:03,830
se bytes në atë fetë e kuqe janë
adresën në të cilën ai duhet të kthehet,

623
00:29:03,830 --> 00:29:09,020
çfarë nëse kundërshtari është mjaft i zgjuar apo
fat të mjaftueshme për të vënë një sekuencë e bytes

624
00:29:09,020 --> 00:29:13,450
atje që duket si një adresë,
por kjo është adresa e kodit

625
00:29:13,450 --> 00:29:18,730
se ai apo ajo dëshiron kompjuterin
për të ekzekutuar në vend të kryesor?

626
00:29:18,730 --> 00:29:21,670
>> Me fjalë të tjera, në qoftë se ajo që
përdorues është shtypur në prompt,

627
00:29:21,670 --> 00:29:23,850
nuk është vetëm diçka
si i padëmshëm hello,

628
00:29:23,850 --> 00:29:28,210
por është e vërtetë kodin që është ekuivalent
për të fshirë të gjitha dosjet e këtij përdoruesit?

629
00:29:28,210 --> 00:29:30,060
Ose email fjalëkalimin e tyre për mua?

630
00:29:30,060 --> 00:29:31,940
Ose të fillojnë prerjet e tyre
tasteve, e drejtë?

631
00:29:31,940 --> 00:29:34,920
Nuk është një mënyrë, le të përcaktojnë sot,
se ata mund të shkruani jo vetëm përshëndetje

632
00:29:34,920 --> 00:29:36,711
bota apo emrin e tyre,
ata mund të në thelb

633
00:29:36,711 --> 00:29:39,570
kalojë në kod, zero dhe
ato, që kompjuteri

634
00:29:39,570 --> 00:29:43,450
gabime për të dy kodit dhe një adresë.

635
00:29:43,450 --> 00:29:48,950
Pra, megjithëse disi abstrakte, në qoftë se
lloje përdorues në kodin mjaftueshme kundërshtuese

636
00:29:48,950 --> 00:29:52,330
se ne do të përgjithësojmë këtu si
A. Një është sulm apo kundërshtarë.

637
00:29:52,330 --> 00:29:53,140
Sende kështu që vetëm të këqija.

638
00:29:53,140 --> 00:29:55,306
Ne nuk e kujdesit në lidhje me
Numrat apo zero, ose ato

639
00:29:55,306 --> 00:29:59,470
sot, të tilla që ju të përfundojë
overwriting atë pjesë të kuqe,

640
00:29:59,470 --> 00:30:01,580
vini re se rend e bytes.

641
00:30:01,580 --> 00:30:05,020
O 835 C zero tetë zero.

642
00:30:05,020 --> 00:30:08,960
Dhe tani si artikull Wikipedia këtu
ka propozuar, në qoftë se ju tani vërtetë të filloni

643
00:30:08,960 --> 00:30:12,460
etiketimin bytes në kompjuterit tuaj
kujtesës, çfarë artikull Wikipedia është

644
00:30:12,460 --> 00:30:19,060
propozues është se, çfarë nëse adresa
e atij bajt e sipërm të majtë është 80 C 0 3508.

645
00:30:19,060 --> 00:30:22,200
>> Me fjalë të tjera, në qoftë se djalë i keq është
mjaft i zgjuar me kodin e tij ose të saj

646
00:30:22,200 --> 00:30:26,650
të vërtetë vënë një numër këtu se
korrespondon me adresën e kodit

647
00:30:26,650 --> 00:30:29,180
ai ose ajo injektuar
në kompjuter, ju

648
00:30:29,180 --> 00:30:31,050
mund të gënjejnë në kompjuter
në bërë asgjë.

649
00:30:31,050 --> 00:30:34,140
Heqja fotografi, emailing
gjëra, nuhatës trafikut tuaj,

650
00:30:34,140 --> 00:30:36,710
fjalë për fjalë çdo gjë mund të jetë
injektuar në kompjuter.

651
00:30:36,710 --> 00:30:39,220
Dhe kështu një del nga shtrati tampon
Sulmi në thelbin e vet

652
00:30:39,220 --> 00:30:43,530
është vetëm një budalla, budalla
parësor i një grup që

653
00:30:43,530 --> 00:30:45,840
nuk kanë kontrolluar kufijtë e saj.

654
00:30:45,840 --> 00:30:48,850
Dhe kjo është ajo që është super i rrezikshëm
dhe njëkohësisht super të fuqishme

655
00:30:48,850 --> 00:30:52,560
në C është se ne vërtet kemi
Qasje për të kudo në kujtesën.

656
00:30:52,560 --> 00:30:55,320
Është e deri te ne, programuesit,
që shkruani kodin origjinale

657
00:30:55,320 --> 00:30:59,330
për të kontrolluar kohëzgjatjen e mallkuar e ndonjë
vargjeve që ne jemi duke manipuluar.

658
00:30:59,330 --> 00:31:00,750
Pra, të jetë i qartë, çfarë është fix?

659
00:31:00,750 --> 00:31:03,190
Nëse do të rrokulliset përsëri në këtë
kodi, unë nuk duhet vetëm

660
00:31:03,190 --> 00:31:08,000
ndryshojë gjatësinë e bar, çfarë
tjetër duhet të jenë të kontrolluar?

661
00:31:08,000 --> 00:31:10,620
Çfarë tjetër duhet të jetë bërë për të
parandaluar këtë sulm krejtësisht?

662
00:31:10,620 --> 00:31:14,110
Unë nuk dua të them vetëm verbërisht
që ju duhet të kopje sa më shumë bytes

663
00:31:14,110 --> 00:31:16,140
si është gjatësia e bar.

664
00:31:16,140 --> 00:31:18,910
Dua të them, kopjoni si
shumë bytes siç janë në bar

665
00:31:18,910 --> 00:31:24,090
deri në të alokuar
kujtesës, ose 12 maksimalisht.

666
00:31:24,090 --> 00:31:27,450
Kështu që kam nevojë për një lloj të në qoftë se gjendja
që e bën të kontrolluar kohëzgjatjen e bar,

667
00:31:27,450 --> 00:31:32,800
por në qoftë se ajo tejkalon 12, ne kodin vetëm e vështirë
12 si distancë maksimale të mundshme.

668
00:31:32,800 --> 00:31:35,910
Ndryshe e ashtuquajtura tampon
sulm del nga shtrati mund të ndodhë.

669
00:31:35,910 --> 00:31:38,451
Në fund të këtyre slides,
në qoftë se ju jeni kurioz për të lexuar më shumë

670
00:31:38,451 --> 00:31:41,200
është artikull aktual origjinal
në qoftë se ju dëshironi të marrë një sy.

671
00:31:41,200 --> 00:31:44,550
>> Por tani, në mesin e çmimeve
paguar këtu ishte joefikasiteti.

672
00:31:44,550 --> 00:31:46,680
Kështu që ishte një i shpejtë
vështrim në atë nivel të ulët

673
00:31:46,680 --> 00:31:49,709
Problemet mund të lindin tani që ne
kanë qasje në kujtesë kompjuterit.

674
00:31:49,709 --> 00:31:51,750
Por një tjetër problem ne
tashmë ngecur hënën

675
00:31:51,750 --> 00:31:53,800
ishte vetëm joefikasiteti
nga një listë e lidhur.

676
00:31:53,800 --> 00:31:56,019
Ne jemi prapa në kohë lineare.

677
00:31:56,019 --> 00:31:57,560
Ne nuk kemi një rrjet të puthitur.

678
00:31:57,560 --> 00:31:58,980
Ne nuk kemi qasje të rastit.

679
00:31:58,980 --> 00:32:00,710
Ne nuk mund të përdorë katror simbol kllapa.

680
00:32:00,710 --> 00:32:04,590
Ne fjalë për fjalë duhet të përdorni një lak, ndërsa
si ajo që kam shkruar një moment më parë.

681
00:32:04,590 --> 00:32:09,740
Por të hënën, kemi pohuar se ne mund të
zvarriten përsëri në fushën e efikasitetit

682
00:32:09,740 --> 00:32:13,040
arritur diçka që është
logaritmike ndoshta, ose më mirë akoma,

683
00:32:13,040 --> 00:32:16,120
ndoshta edhe diçka që është
ashtuquajtura kohë konstante.

684
00:32:16,120 --> 00:32:19,840
Pra, si mund ta bëjmë atë duke përdorur këto të reja
mjetet, këto adresa, këto pointers,

685
00:32:19,840 --> 00:32:22,210
dhe fillesë gjërat e vet tonë?

686
00:32:22,210 --> 00:32:23,960
E pra, mendoj se
këtu, këto janë një bandë

687
00:32:23,960 --> 00:32:27,170
e numrave që ne duam për të ruajtur në një
Struktura e të dhënave dhe të kërkimit në mënyrë efikase.

688
00:32:27,170 --> 00:32:30,960
Ne mund absolutisht rewind në javë
dy, hedhin ato në një rrjet,

689
00:32:30,960 --> 00:32:33,150
dhe kërko ato duke përdorur search binar.

690
00:32:33,150 --> 00:32:34,040
Përça dhe sundo.

691
00:32:34,040 --> 00:32:37,720
Dhe në fakt ju ka shkruajtur
Kërko binar në PSET3,

692
00:32:37,720 --> 00:32:40,100
ku ju zbatuar programin gjeni.

693
00:32:40,100 --> 00:32:40,890
Por ju e dini se çfarë.

694
00:32:40,890 --> 00:32:45,060
Nuk është lloj i një më të
mënyrë e zgjuar për të bërë këtë.

695
00:32:45,060 --> 00:32:47,390
Kjo është pak më shumë
sofistikuar dhe kjo ndoshta

696
00:32:47,390 --> 00:32:50,830
na lejon të shohim se pse binar
Kërkimi është aq shumë më e shpejtë.

697
00:32:50,830 --> 00:32:52,980
Së pari, le të prezantoj
nocioni i një peme.

698
00:32:52,980 --> 00:32:54,730
E cila edhe pse në
Pemët realitet lloj i

699
00:32:54,730 --> 00:32:57,730
rritet si ky, në botën e kompjuterit
shkenca ata lloj i rriten në rënie

700
00:32:57,730 --> 00:33:00,830
si një pemë familjare, ku ju duhet
gjyshërit tuaj ose gjyshërit e madhe

701
00:33:00,830 --> 00:33:04,580
ose gjësend në krye, patriarkun dhe
matriarch e familjes, vetëm një

702
00:33:04,580 --> 00:33:07,930
ashtuquajtura rrënjë, nyje, më poshtë
të cilat janë fëmijët e saj,

703
00:33:07,930 --> 00:33:11,442
më poshtë të cilat janë fëmijët e saj, ose
Pasardhësit e tij në përgjithësi.

704
00:33:11,442 --> 00:33:13,400
Dhe kushdo varur jashtë
në fund të familjes

705
00:33:13,400 --> 00:33:16,070
pemë, përveç të qënit
më i ri në familje,

706
00:33:16,070 --> 00:33:19,520
mund të jetë vetëm generically
quajtur gjethet e pemës.

707
00:33:19,520 --> 00:33:21,800
>> Pra, kjo është vetëm një bandë
e fjalëve dhe përkufizimet

708
00:33:21,800 --> 00:33:25,790
për diçka të quajtur një pemë në kompjuterin
shkenca, ashtu si një pemë familjare.

709
00:33:25,790 --> 00:33:28,770
Por ka incarnations njohës
e pemeve, njëri prej të cilëve

710
00:33:28,770 --> 00:33:30,780
është quajtur një pemë binare e kërkimit.

711
00:33:30,780 --> 00:33:34,380
Dhe ju mund të lloj i vë në lojë
përveç asaj që kjo gjë e bën.

712
00:33:34,380 --> 00:33:37,180
E pra, kjo është binar në çfarë kuptimi?

713
00:33:37,180 --> 00:33:41,455
Ku ka binar ardhur nga këtu?

714
00:33:41,455 --> 00:33:41,955
Na vjen keq?

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

716
00:33:45,961 --> 00:33:47,210
Kjo nuk është aq shumë një ose ose.

717
00:33:47,210 --> 00:33:52,000
Kjo është më shumë se secili prej nyjeve nuk ka
më shumë se dy fëmijë, siç e shohim këtu.

718
00:33:52,000 --> 00:33:54,990
Në përgjithësi, një tree-- dhe
prindërit dhe gjyshërit

719
00:33:54,990 --> 00:33:57,640
mund të ketë sa më shumë fëmijë apo
grandkids si ata në fakt duan,

720
00:33:57,640 --> 00:34:00,820
dhe kështu për shembull nuk kemi tre
Fëmijët off se nyje djathtë,

721
00:34:00,820 --> 00:34:05,480
por në një pemë binare, një nyje ka
zero, një, ose dy fëmijë maksimalisht.

722
00:34:05,480 --> 00:34:08,496
Dhe kjo është një pronë e bukur,
sepse në qoftë se është e mbuluar nga dy,

723
00:34:08,496 --> 00:34:10,620
ne do të jetë në gjendje të
të marrë një bazë të vogël log dy

724
00:34:10,620 --> 00:34:11,975
veprim ndodh këtu në fund të fundit.

725
00:34:11,975 --> 00:34:13,350
Pra, ne kemi diçka logaritmike.

726
00:34:13,350 --> 00:34:14,558
Por më shumë se në një moment.

727
00:34:14,558 --> 00:34:19,810
Kërko pemë do të thotë se numrat janë
rregulluar tillë që fëmija e majtë të

728
00:34:19,810 --> 00:34:22,429
vlerë është më e madhe se rrënjës.

729
00:34:22,429 --> 00:34:26,010
Dhe fëmija e saj është e drejtë
më të mëdha se rrënjë.

730
00:34:26,010 --> 00:34:29,290
Me fjalë të tjera, në qoftë se ju merrni ndonjë nga
nyjet, qarqet në këtë foto,

731
00:34:29,290 --> 00:34:31,840
dhe shikon në të majtë të saj
fëmijë dhe fëmija e saj e drejtë,

732
00:34:31,840 --> 00:34:34,739
e para duhet të jetë më pak se,
e dyta duhet të jetë më i madh se.

733
00:34:34,739 --> 00:34:36,159
Pra, mendje e shëndoshë kontrolloni 55.

734
00:34:36,159 --> 00:34:37,780
Ajo ka lënë fëmijë është 33.

735
00:34:37,780 --> 00:34:38,620
Kjo është më pak se.

736
00:34:38,620 --> 00:34:40,929
55, fëmija i saj e drejtë është 77.

737
00:34:40,929 --> 00:34:41,783
Kjo është më e madhe se.

738
00:34:41,783 --> 00:34:43,199
Dhe kjo është një përkufizim gjithkund rekursive.

739
00:34:43,199 --> 00:34:46,480
Ne mund të kontrolloni çdo një nga ato
nyjet dhe i njëjti model do të mbajë.

740
00:34:46,480 --> 00:34:49,389
>> Pra, çfarë është e bukur në një
Kërkimi pemë binare, është

741
00:34:49,389 --> 00:34:52,204
se një, ne mund të zbatojë atë
me një struct, ashtu si kjo.

742
00:34:52,204 --> 00:34:54,620
Dhe, edhe pse ne jemi duke hedhur
shumë strukturave në tuaj,

743
00:34:54,620 --> 00:34:56,560
ata janë disi
intuitive tani shpresë.

744
00:34:56,560 --> 00:35:00,570
Sintaksa është ende misterioze e sigurt,
por përmbajtja e një nyje në këtë

745
00:35:00,570 --> 00:35:02,786
context-- dhe do të vazhdojmë të
përdorur fjalën nyje,

746
00:35:02,786 --> 00:35:04,910
nëse kjo është një drejtkëndësh
në ekran ose një rreth,

747
00:35:04,910 --> 00:35:08,970
kjo është vetëm një enë të përgjithshme,
në këtë rast të një pemë, si ai

748
00:35:08,970 --> 00:35:11,780
ne pamë, ne kemi nevojë për një numër të plotë
në secilën prej nyjeve

749
00:35:11,780 --> 00:35:15,460
dhe pastaj kam nevojë për dy Pointers treguar
për fëmijën e majtë dhe të djathtë të fëmijës,

750
00:35:15,460 --> 00:35:16,590
përkatësisht.

751
00:35:16,590 --> 00:35:20,730
Pra, kjo është se si ne mund
zbatuar që në një struct.

752
00:35:20,730 --> 00:35:22,315
Dhe si mund ta zbatojë atë në kodin?

753
00:35:22,315 --> 00:35:26,730
E pra, le të marrin një shpejtë
Shikojeni këtë shembull të vogël.

754
00:35:26,730 --> 00:35:29,820
Kjo nuk është funksionale, por unë kam
kopjohet dhe të ngjit atë strukturë.

755
00:35:29,820 --> 00:35:33,510
Dhe në qoftë se funksioni im për një binar
pemë Kërkimi quhet kërkimit,

756
00:35:33,510 --> 00:35:36,980
dhe kjo merr dy argumente,
një numër të plotë n dhe një tregues

757
00:35:36,980 --> 00:35:41,400
në një nyje, kështu një tregues për pemë
ose një tregues për rrënjët e një pemë,

758
00:35:41,400 --> 00:35:43,482
Si mund të shkoj në lidhje me kërkim për N?

759
00:35:43,482 --> 00:35:45,440
E pra, së pari, sepse unë jam i
që kanë të bëjnë me pointers,

760
00:35:45,440 --> 00:35:46,750
Unë jam duke shkuar për të bërë një kontroll mendje e shëndoshë.

761
00:35:46,750 --> 00:35:54,279
Nëse barabartë pemë është e barabartë null, eshte N
në këtë pemë apo jo në këtë pemë?

762
00:35:54,279 --> 00:35:55,070
Ajo nuk mund të jetë, e drejtë?

763
00:35:55,070 --> 00:35:56,870
Nëse unë jam e kaluara null,
nuk ka asgjë atje.

764
00:35:56,870 --> 00:35:59,230
Unë mund edhe të vetëm
verbërisht thonë kthimit të rreme.

765
00:35:59,230 --> 00:36:04,050
Në qoftë se ju më jepni asgjë, unë me siguri nuk mund të
gjeni ndonjë N. numrin Pra, çfarë tjetër mund unë

766
00:36:04,050 --> 00:36:04,750
shikoni tani?

767
00:36:04,750 --> 00:36:12,830
Unë jam duke shkuar për të thënë edhe tjetër nëse n është
më pak se çdo gjë që është në nyjen pemë

768
00:36:12,830 --> 00:36:16,300
që unë kam qenë dorëzuar vlerën N.

769
00:36:16,300 --> 00:36:20,270
Me fjalë të tjera, nëse numri unë jam
kërkoni për, N, është më pak se nyjen

770
00:36:20,270 --> 00:36:21,340
që unë jam duke kërkuar në.

771
00:36:21,340 --> 00:36:23,190
Dhe nyja unë jam duke kërkuar
në është quajtur dru,

772
00:36:23,190 --> 00:36:26,370
dhe kujtojnë nga shembulli i mëparshëm
për të marrë në vlerën në një tregues,

773
00:36:26,370 --> 00:36:28,310
I përdorin arrow simbol.

774
00:36:28,310 --> 00:36:35,960
Pra, nëse N është më pak se pemë shigjetë
N, unë dua të shkoj konceptualisht majtë.

775
00:36:35,960 --> 00:36:38,590
Si mund të shpreh kërkim lënë?

776
00:36:38,590 --> 00:36:41,560
Për të qenë të qartë, në qoftë se kjo është
fotografia në fjalë,

777
00:36:41,560 --> 00:36:44,612
dhe unë kam kaluar se larti
shigjetë që është vënë poshtë.

778
00:36:44,612 --> 00:36:45,570
Kjo është pema akrep ime.

779
00:36:45,570 --> 00:36:48,060
Unë jam vënë në rrënjë të pemës.

780
00:36:48,060 --> 00:36:52,100
Dhe unë jam duke kërkuar të themi, për
numrin 44, në mënyrë arbitrare.

781
00:36:52,100 --> 00:36:55,300
Është 44 me pak se ose
më i madh se 55 padyshim?

782
00:36:55,300 --> 00:36:56,360
Pra, kjo është më pak se.

783
00:36:56,360 --> 00:36:58,760
Dhe kështu kjo nëse kusht vlen.

784
00:36:58,760 --> 00:37:03,981
Pra konceptualisht, çfarë unë dua të
kërko tjetër në qoftë se unë jam duke kërkuar për 44?

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

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

787
00:37:08,310 --> 00:37:11,100
>> Pikërisht, unë dua të
kërko fëmijën e majtë,

788
00:37:11,100 --> 00:37:12,789
ose nën-pema u largua nga kjo foto.

789
00:37:12,789 --> 00:37:14,830
Dhe në fakt, më lejoni përmes
foto poshtë këtu

790
00:37:14,830 --> 00:37:17,770
për vetëm një moment, që nga
Unë nuk mund ta heq këtë.

791
00:37:17,770 --> 00:37:21,150
Nëse unë të fillojë këtu në 55, dhe
Unë e di se vlera 44

792
00:37:21,150 --> 00:37:23,180
Unë jam duke kërkuar për të është që të
e majta, kjo është lloj

793
00:37:23,180 --> 00:37:26,010
e si marramendës librin e telefonit në
gjysma ose marramendës pemë në gjysmë.

794
00:37:26,010 --> 00:37:29,660
Unë nuk duhet të kujdesen për
tërë kjo gjysma e pemës.

795
00:37:29,660 --> 00:37:33,270
Dhe akoma, interesant në aspektin e
Struktura, kjo gjë mbi këtu se

796
00:37:33,270 --> 00:37:36,682
fillon me 33, që në vetvete
është një pemë binare e kërkimit.

797
00:37:36,682 --> 00:37:39,890
Unë i thashë fjalën rekursive para sepse
në të vërtetë kjo është një strukturë e të dhënave që

798
00:37:39,890 --> 00:37:41,707
sipas definicionit është rekursive.

799
00:37:41,707 --> 00:37:44,540
Ju mund të keni një pemë që është kjo
i madh, por çdo njëri prej fëmijëve të saj

800
00:37:44,540 --> 00:37:46,870
përfaqëson një pemë vetëm një pak më të vogël.

801
00:37:46,870 --> 00:37:50,910
Në vend të saj të qënit gjysh
ose gjyshe, tani ajo është vetëm nëna

802
00:37:50,910 --> 00:37:54,300
or-- unë nuk mund të mos say-- mom
apo baba, që do të jetë i çuditshëm.

803
00:37:54,300 --> 00:37:59,000
Në vend të dy fëmijët atje
do të jetë si vëlla e motër.

804
00:37:59,000 --> 00:38:01,120
Një brez i ri pemën familjare.

805
00:38:01,120 --> 00:38:02,900
Por strukturore, kjo është e njëjta ide.

806
00:38:02,900 --> 00:38:06,790
Dhe kjo rezulton unë kam një funksion
me të cilën unë mund të kërkoni një kërkim binar

807
00:38:06,790 --> 00:38:07,290
pemë.

808
00:38:07,290 --> 00:38:08,680
Ajo quhet kërkimit.

809
00:38:08,680 --> 00:38:17,870
Unë të kërkuar për N në pemë shigjetë majtë
përndryshe nëse n eshte me e madhe se vlera

810
00:38:17,870 --> 00:38:18,870
se unë jam aktualisht në.

811
00:38:18,870 --> 00:38:20,800
55 në histori një moment më parë.

812
00:38:20,800 --> 00:38:23,780
Unë kam një funksion të quajtur
kërkim që unë mund vetëm

813
00:38:23,780 --> 00:38:29,660
kalojë N kjo dhe Recursively kërko
nën-pemë dhe vetëm kthimi

814
00:38:29,660 --> 00:38:30,620
çfarëdo që përgjigja.

815
00:38:30,620 --> 00:38:33,530
Tjetër unë kam marrë disa rastin përfundimtar bazë këtu.

816
00:38:33,530 --> 00:38:35,310
>> Çfarë është rasti i fundit?

817
00:38:35,310 --> 00:38:36,570
Tree është ose i pavlefshëm.

818
00:38:36,570 --> 00:38:39,980
Vlera Unë jam duke kërkuar për ose është
pak se saj ose më e madhe se sa

819
00:38:39,980 --> 00:38:42,610
ose e barabartë me të.

820
00:38:42,610 --> 00:38:44,750
Dhe unë mund të them të barabartë
të barabartë, por logjikisht kjo është

821
00:38:44,750 --> 00:38:46,500
ekuivalent me vetëm duke thënë tjetër këtu.

822
00:38:46,500 --> 00:38:49,150
Aq e vërtetë është se si unë të gjeni diçka.

823
00:38:49,150 --> 00:38:51,710
Kështu që shpresojmë se kjo është një
edhe shembulli më bindëse

824
00:38:51,710 --> 00:38:54,900
se funksionit budallaqe sigma
ne e bëmë një leksione pak prapa,

825
00:38:54,900 --> 00:38:58,360
ku ajo ishte po aq e lehtë për t'u përdorur një lak
për të numëruar të gjithë numrat nga një

826
00:38:58,360 --> 00:39:02,390
të N. këtu me një strukturë të dhënave
që në vetvete është Recursively

827
00:39:02,390 --> 00:39:07,050
përcaktuar dhe të tërhequr Recursively, tani ne
kanë aftësinë për të shprehur veten

828
00:39:07,050 --> 00:39:09,780
në kodin që vetë është rekursive.

829
00:39:09,780 --> 00:39:12,580
Pra, kjo është e njëjta kod e saktë këtu.

830
00:39:12,580 --> 00:39:14,400
>> Pra, çfarë probleme të tjera mund të zgjidhim?

831
00:39:14,400 --> 00:39:18,160
Pra, një hap të shpejtë larg nga
frutorë, për një moment të vetëm.

832
00:39:18,160 --> 00:39:20,130
Këtu është, të themi, flamurin gjerman.

833
00:39:20,130 --> 00:39:22,020
Dhe nuk ka mënyrë të qartë një
model për këtë flamur.

834
00:39:22,020 --> 00:39:23,811
Dhe nuk ka shumë
flamuj në botë që

835
00:39:23,811 --> 00:39:27,560
janë aq e thjeshtë sa kjo në aspektin
të ngjyrave të tyre dhe modeleve.

836
00:39:27,560 --> 00:39:31,930
Por mendoj se ky është ruajtur si një
GIF, ose nje JPEG, ose bitmap, ose nje ping,

837
00:39:31,930 --> 00:39:34,240
ndonjë file format grafik
me të cilat ju jeni të njohur,

838
00:39:34,240 --> 00:39:36,460
disa prej të cilave ne jemi
duke luajtur me në PSET4.

839
00:39:36,460 --> 00:39:41,550
Kjo nuk duket i vlefshëm për të ruajtur
pixel e zezë, e zezë pixel, pixel e zezë,

840
00:39:41,550 --> 00:39:44,790
dot, dot, dot, një bandë e tërë e
piksel zezë për scanline parë,

841
00:39:44,790 --> 00:39:47,430
ose rresht, pastaj një bandë e tërë e
të njëjtën gjë, atëherë një bandë e tërë

842
00:39:47,430 --> 00:39:49,530
e njëjtë, dhe pastaj një
tërë bandë e pixels kuqe,

843
00:39:49,530 --> 00:39:53,020
pixels kuqe, pixel e kuqe, pastaj një e tërë
bandë e pixels verdhë, e verdhë, e drejtë?

844
00:39:53,020 --> 00:39:55,050
>> Ka joefikasiteti i tillë këtu.

845
00:39:55,050 --> 00:39:59,040
Si do të ju intuitive
compress flamurin gjerman

846
00:39:59,040 --> 00:40:01,320
nëse zbaton atë si një skedar?

847
00:40:01,320 --> 00:40:04,940
Ashtu si çfarë informacioni ne nuk mund të
mërzit ruajtjen në disk në mënyrë

848
00:40:04,940 --> 00:40:08,040
për të ulur madhësinë tonë skedarëve nga si
një megabyte në një kilobyte, diçka

849
00:40:08,040 --> 00:40:09,430
më të vogla?

850
00:40:09,430 --> 00:40:13,130
Aty qëndron tepricë
këtu të jetë i qartë?

851
00:40:13,130 --> 00:40:13,880
Çfarë mund të bëni?

852
00:40:13,880 --> 00:40:14,380
Po?

853
00:40:14,380 --> 00:40:21,380

854
00:40:21,380 --> 00:40:21,970
Pikërisht.

855
00:40:21,970 --> 00:40:24,550
Pse nuk lejoni më mirë se mbaj mend
ngjyra e çdo pixel mallkuar

856
00:40:24,550 --> 00:40:28,200
ashtu si ju jeni duke bërë në PSET4
me format file bitmap,

857
00:40:28,200 --> 00:40:32,060
pse nuk ju vetëm të përfaqësojë
kolona pari nga e majta e pixels, për shembull

858
00:40:32,060 --> 00:40:35,370
një bandë e pixels zeza, një bandë
e kuqe, dhe një bandë e verdhë,

859
00:40:35,370 --> 00:40:39,210
dhe pastaj vetëm disi shifroj
Ideja e përsëritur këtë 100 herë

860
00:40:39,210 --> 00:40:41,020
ose të përsëritur këtë 1,000 herë?

861
00:40:41,020 --> 00:40:43,430
Ku 100 apo 1000 është
vetëm një numër i plotë, kështu që ju

862
00:40:43,430 --> 00:40:47,290
mund të merrni larg me vetëm një numër të vetëm
në vend të qindra ose mijëra

863
00:40:47,290 --> 00:40:48,270
pixel e tjera.

864
00:40:48,270 --> 00:40:50,990
Dhe me të vërtetë, kjo është se si ne
mund të compress flamurin gjerman.

865
00:40:50,990 --> 00:40:51,490
Dhe

866
00:40:51,490 --> 00:40:53,470
Tani ajo që në lidhje me flamurin francez?

867
00:40:53,470 --> 00:40:58,930
Dhe një lloj i vogël
ushtrim mendor, që flamuri

868
00:40:58,930 --> 00:41:01,040
mund të jetë i ngjeshur shumë në disk?

869
00:41:01,040 --> 00:41:05,720
Flamuri gjerman ose francez
flamuri, nëse e marrim këtë qasje?

870
00:41:05,720 --> 00:41:08,490
Flamuri gjerman, sepse nuk ka
më tepricë horizontale.

871
00:41:08,490 --> 00:41:12,190
Dhe me dashje, shumë skedar grafik
Formatet vërtet punojnë si scan linjat

872
00:41:12,190 --> 00:41:12,830
horizontalisht.

873
00:41:12,830 --> 00:41:14,674
Ata mund të punojnë
vertikalisht, vetëm njerëzimi

874
00:41:14,674 --> 00:41:17,090
vjet më parë vendosi që ne do të
përgjithësisht mendojnë rresht gjëra

875
00:41:17,090 --> 00:41:18,880
nga rresht në vend të kolonës me kolonën.

876
00:41:18,880 --> 00:41:20,820
Pra, me të vërtetë, nëse ju keni qenë
për të parë në dosjen

877
00:41:20,820 --> 00:41:24,670
Madhësia e një flamur gjerman dhe një francez
flamurin, për sa kohë që rezoluta është

878
00:41:24,670 --> 00:41:27,530
e njëjta, të njëjtën gjerësi
dhe lartësi, kjo

879
00:41:27,530 --> 00:41:31,580
këtu do të jetë më e madhe, sepse ju
keni për të përsëritur veten tri herë.

880
00:41:31,580 --> 00:41:35,570
Ju duhet të specifikoni blu, të përsëritur
veten, e bardhë, e përsëris veten, e kuqe,

881
00:41:35,570 --> 00:41:36,740
përsëris veten.

882
00:41:36,740 --> 00:41:39,000
Ju nuk mund të shkoni të gjithë
mënyra në të djathtë.

883
00:41:39,000 --> 00:41:41,200
Dhe si një mënjanë, për të bërë
qartë compression

884
00:41:41,200 --> 00:41:43,910
është kudo, nëse këto janë
katër korniza nga një video-- ju

885
00:41:43,910 --> 00:41:45,890
mund të kujtojmë se një film
ose video është përgjithësisht

886
00:41:45,890 --> 00:41:47,286
si 29 ose 30 korniza për sekondë.

887
00:41:47,286 --> 00:41:50,410
Është si një libër të vogël rrokullisje ku ju
vetëm shikoni imazhit, imazhi, imazhi, imazhi,

888
00:41:50,410 --> 00:41:54,410
Imazhi vetëm super të shpejtë kështu që duket sikur
aktorët në ekran janë duke lëvizur.

889
00:41:54,410 --> 00:41:57,130
Këtu është një bletë qullos në
krye të një buqetë me lule.

890
00:41:57,130 --> 00:41:59,790
Dhe pse kjo mund të jetë lloj i
vështirë për të parë në shikim të parë,

891
00:41:59,790 --> 00:42:04,020
e vetmja gjë që lëviz në
ky film është bee.

892
00:42:04,020 --> 00:42:06,880
>> Çfarë është memec në lidhje me ruajtjen
Video ngjeshur?

893
00:42:06,880 --> 00:42:11,420
Kjo është lloj i një humbje në dyqan video
si katër imazhe pothuajse identike që

894
00:42:11,420 --> 00:42:13,670
ndryshojnë vetëm për aq sa ku bee është.

895
00:42:13,670 --> 00:42:16,280
Ju mund të hedhin larg më
e atij informacioni

896
00:42:16,280 --> 00:42:20,190
dhe mos harroni vetëm, për shembull,
korniza e parë dhe frame kaluar,

897
00:42:20,190 --> 00:42:22,180
korniza kryesore qoftë se ju keni
dëgjuar ndonjëherë fjalën,

898
00:42:22,180 --> 00:42:24,337
dhe vetëm dyqan në
mesme ku bee është.

899
00:42:24,337 --> 00:42:26,170
Dhe ju nuk keni për të
ruajtur të gjithë të kuq,

900
00:42:26,170 --> 00:42:28,330
dhe blu, dhe
Vlerat e gjelbër si edhe.

901
00:42:28,330 --> 00:42:31,200
Pra, kjo do të thotë vetëm se
compression është kudo.

902
00:42:31,200 --> 00:42:34,900
Kjo është një teknikë që ne shpesh e përdorim
ose të marrë për të dhënë këto ditë.

903
00:42:34,900 --> 00:42:38,750
>> Por si mund të ngjesh tekst?

904
00:42:38,750 --> 00:42:40,450
Si ju shkoni në lidhje me compressing tekst?

905
00:42:40,450 --> 00:42:45,410
E pra, secili nga personazhet në
Ascii është një bajt, ose tetë bit.

906
00:42:45,410 --> 00:42:47,360
Dhe kjo është lloj i heshtur, e drejtë?

907
00:42:47,360 --> 00:42:51,160
Sepse ju ndoshta tipit A
dhe E dhe I dhe O dhe U shumë

908
00:42:51,160 --> 00:42:55,270
më shpesh se si W ose Q apo Z,
në varësi të gjuhës në të cilën

909
00:42:55,270 --> 00:42:56,610
ju jeni me shkrim me siguri.

910
00:42:56,610 --> 00:42:59,600
Dhe kështu që pse jemi duke përdorur
tetë bit për çdo letër,

911
00:42:59,600 --> 00:43:02,040
duke përfshirë së paku
letra popullore, e drejtë?

912
00:43:02,040 --> 00:43:05,300
Pse të mos i përdorin më pak bit për
shkronjat super popullore,

913
00:43:05,300 --> 00:43:07,760
si E, gjërat që ju me mend
për herë të parë në Wheel of Fortune,

914
00:43:07,760 --> 00:43:10,450
dhe përdorin më shumë bit për
shkronjat më pak popullor?

915
00:43:10,450 --> 00:43:10,950
Përse?

916
00:43:10,950 --> 00:43:13,130
Sepse ne jemi vetëm do të
përdorin ato më shpesh.

917
00:43:13,130 --> 00:43:15,838
>> E pra, ajo rezulton se ka pasur
bërë përpjekje për të bërë këtë.

918
00:43:15,838 --> 00:43:18,630
Dhe në qoftë se ju kujtohet nga klasa
shkollës ose shkollën e mesme, kodin Morse.

919
00:43:18,630 --> 00:43:20,400
Kodi Morse ka dots
dhe dashes që mund të jetë

920
00:43:20,400 --> 00:43:24,270
transmetuar përgjatë një tel si
Dashuri apo sinjalet e disa lloj.

921
00:43:24,270 --> 00:43:25,930
Por kodin Morse është një super të pastër.

922
00:43:25,930 --> 00:43:29,010
Kjo është lloj i një sistemi binar në
që ju keni pika ose dashes.

923
00:43:29,010 --> 00:43:30,977
Por në qoftë se ju shihni, për shembull, dy pika.

924
00:43:30,977 --> 00:43:33,810
Ose në qoftë se ju mendoni përsëri për operatorin
që shkon si bip, bip, bip,

925
00:43:33,810 --> 00:43:36,760
bip, duke goditur një shkas të vogël
që transmeton një sinjal,

926
00:43:36,760 --> 00:43:40,360
në qoftë se ju, marrësi, merr dy
pika, çfarë mesazhi keni marrë?

927
00:43:40,360 --> 00:43:43,490
Krejtësisht arbitrare.

928
00:43:43,490 --> 00:43:44,450
>> Unë?

929
00:43:44,450 --> 00:43:45,060
Unë?

930
00:43:45,060 --> 00:43:47,500
Ose çfarë? Për apo unë?

931
00:43:47,500 --> 00:43:49,570
Ndoshta ajo ishte vetëm dy e drejtë ë s?

932
00:43:49,570 --> 00:43:52,480
Pra, nuk ka ky problem
i decodability me Morse

933
00:43:52,480 --> 00:43:54,890
Kodi, ku përveç nëse
Personi i dërguar që ju mesazh

934
00:43:54,890 --> 00:43:59,510
në fakt pushimeve kështu që ju mund të lloj nga
shohin ose dëgjojnë boshllëqet midis shkronjave,

935
00:43:59,510 --> 00:44:02,990
kjo nuk është e mjaftueshme vetëm për të
dërgoni një rrjedhë e zero dhe ato,

936
00:44:02,990 --> 00:44:05,610
ose pika dhe dashes,
sepse nuk ka paqartësi.

937
00:44:05,610 --> 00:44:08,640
E është një pikë e vetme, kështu që nëse ju
shohim dy pika ose dëgjojnë dy pika,

938
00:44:08,640 --> 00:44:11,254
ndoshta është dy E-së apo ndoshta kjo është një I.

939
00:44:11,254 --> 00:44:13,670
Pra, ne kemi nevojë për një sistem që është një
pak më të zgjuar se kaq.

940
00:44:13,670 --> 00:44:16,851
Pra, një njeri i quajtur Huffman vjet
më parë doli me pikërisht këtë.

941
00:44:16,851 --> 00:44:18,600
Pra, ne jemi vetëm duke shkuar
për të marrë një shikim të shpejtë

942
00:44:18,600 --> 00:44:20,114
se si pemët janë të përshtatshëm për këtë.

943
00:44:20,114 --> 00:44:22,530
Le të supozojmë se kjo është një
Mesazhi budalla ju dëshironi të dërgoni,

944
00:44:22,530 --> 00:44:26,342
i përbërë nga vetëm A, B, C-së D's dhe E-së,
por ka shumë tepricë këtu.

945
00:44:26,342 --> 00:44:27,550
Kjo nuk është menduar të jetë anglisht.

946
00:44:27,550 --> 00:44:28,341
Kjo nuk është e koduar.

947
00:44:28,341 --> 00:44:30,540
Është vetëm një mesazh budalla
me shumë përsëritje.

948
00:44:30,540 --> 00:44:34,010
Pra, nëse ju në të vërtetë të mbështeteni nga të gjitha
A-së, B-së, C-së, D's, dhe E-së, këtu është

949
00:44:34,010 --> 00:44:34,890
frekuenca.

950
00:44:34,890 --> 00:44:37,800
20% e letrave janë
A-së, 45% e letrave

951
00:44:37,800 --> 00:44:39,660
janë të E-së dhe tre frekuenca të tjera.

952
00:44:39,660 --> 00:44:41,960
Ne të numëruara deri atje me dorë
dhe vetëm e bëri matematikë.

953
00:44:41,960 --> 00:44:44,579
>> Pra, rezulton se
Huffman, disa kohë më parë,

954
00:44:44,579 --> 00:44:46,620
e kuptuan se, ju e dini
çfarë, në qoftë se unë të fillojë ndërtimin e

955
00:44:46,620 --> 00:44:51,172
një pemë, apo pyll e pemëve, në qoftë se ju do të,
si më poshtë, unë mund të bëjë në vijim.

956
00:44:51,172 --> 00:44:53,880
Unë jam duke shkuar për të dhënë një nyje për secilin
nga letrat që i intereson

957
00:44:53,880 --> 00:44:55,530
dhe unë jam duke shkuar për të ruajtur
brenda kësaj nyje

958
00:44:55,530 --> 00:44:58,610
frekuencat si një pikë lundrues
vlerën, ose ju mund të përdorni atë një N, gjithashtu,

959
00:44:58,610 --> 00:45:00,210
por ne do të përdorim vetëm një noton këtu.

960
00:45:00,210 --> 00:45:03,100
Dhe algorithm që
ai propozoi është se ju

961
00:45:03,100 --> 00:45:07,210
marrë këtë pyll të nyjeve të vetme
pemë, pemë aq super të shkurtër,

962
00:45:07,210 --> 00:45:11,920
dhe ju filloni lidh ato me
grupe të reja, prindërit e rinj, nëse ju do.

963
00:45:11,920 --> 00:45:16,150
Dhe ju bëni këtë duke zgjedhur
dy frekuenca më të vogla në një kohë.

964
00:45:16,150 --> 00:45:18,110
Kështu që unë e mori 10% dhe 10%.

965
00:45:18,110 --> 00:45:19,090
Kam krijuar një nyje të re.

966
00:45:19,090 --> 00:45:20,910
Dhe unë e quaj nyjen ri 20%.

967
00:45:20,910 --> 00:45:22,750
>> Të cilat dy nyjet unë kombinoj tjetër?

968
00:45:22,750 --> 00:45:23,810
Kjo është pak i paqartë.

969
00:45:23,810 --> 00:45:26,643
Pra, ka disa raste qoshe për
konsiderojnë, por për të mbajtur gjërat e bukur,

970
00:45:26,643 --> 00:45:29,300
Unë jam duke shkuar për të zgjedhur 20% -
Unë tani injorojnë fëmijët.

971
00:45:29,300 --> 00:45:33,640
Unë jam duke shkuar për të zgjedhur 20% dhe
15% dhe të tërheqë dy tehe të reja.

972
00:45:33,640 --> 00:45:35,624
Dhe tani cilën dy nyjet
mund logjikisht kombinohen?

973
00:45:35,624 --> 00:45:38,540
Ignore gjithë fëmijët, të gjithë të
nipër e mbesa, vetëm shikoni në rrënjët

974
00:45:38,540 --> 00:45:39,070
tani.

975
00:45:39,070 --> 00:45:42,220
Të cilat dy nyje mund të lidhë së bashku?

976
00:45:42,220 --> 00:45:44,530
Pika dy dhe 0.35.

977
00:45:44,530 --> 00:45:45,890
Pra, më lejoni të nxjerrë dy tehe të reja.

978
00:45:45,890 --> 00:45:47,570
Dhe pastaj unë kam marrë vetëm një majtë.

979
00:45:47,570 --> 00:45:48,650
Kështu që këtu është një pemë.

980
00:45:48,650 --> 00:45:51,160
Dhe ajo është hartuar me qëllim
të duken lloj i bukur,

981
00:45:51,160 --> 00:45:55,870
por vini re se edges kanë
gjithashtu janë etiketuar zero dhe një.

982
00:45:55,870 --> 00:45:59,510
Pra, të gjitha skajet e majtë janë zero
në mënyrë arbitrare, por në vazhdimësi.

983
00:45:59,510 --> 00:46:01,170
Të gjitha skajet e drejta janë ato.

984
00:46:01,170 --> 00:46:05,070
>> Dhe kështu ajo që Hoffman të propozuar është,
në qoftë se ju doni për të përfaqësuar një B,

985
00:46:05,070 --> 00:46:10,080
në vend se të përfaqësojnë numrin 66 si
një Ascii cila është tetë bit tërë,

986
00:46:10,080 --> 00:46:13,360
ju e dini se çfarë, vetëm dyqan
model zero, zero, zero,

987
00:46:13,360 --> 00:46:17,030
zero, sepse kjo është rruga
nga pema ime, pemë zotit Huffman-së,

988
00:46:17,030 --> 00:46:18,600
në fletë nga rrënja.

989
00:46:18,600 --> 00:46:20,970
Nëse ju doni për të ruajtur një
E, nga ana tjetër, nuk

990
00:46:20,970 --> 00:46:26,290
dërgoni tetë bit që përfaqësojnë një E.
Në vend të kësaj, dërgoni çfarë modeli i bit?

991
00:46:26,290 --> 00:46:26,890
Një.

992
00:46:26,890 --> 00:46:30,410
Dhe çfarë është e mirë për këtë është
E kjo është letra më popullor,

993
00:46:30,410 --> 00:46:32,340
dhe ju jeni duke përdorur
Kodi më të shkurtër për të.

994
00:46:32,340 --> 00:46:34,090
I ardhshëm më popullore
Letra duket si ajo

995
00:46:34,090 --> 00:46:37,380
ishte A. Dhe kështu sa bit
që ai të propozojë duke përdorur për këtë?

996
00:46:37,380 --> 00:46:38,270
Zero, një.

997
00:46:38,270 --> 00:46:41,060
>> Dhe për shkak se ajo është zbatuar
si këtë pemë, tani për tani

998
00:46:41,060 --> 00:46:43,350
më lejoni të përcaktojnë ka
nuk ka paqartësi si në Morse

999
00:46:43,350 --> 00:46:46,090
Kodi, sepse të gjithë e
letra që ju intereson

1000
00:46:46,090 --> 00:46:48,780
janë në fund të këtyre skajet.

1001
00:46:48,780 --> 00:46:50,580
Pra, kjo është vetëm një
Aplikimi i një pemë.

1002
00:46:50,580 --> 00:46:52,538
Kjo is-- dhe unë do të valë
dora ime kjo si ju

1003
00:46:52,538 --> 00:46:55,570
mund të zbatojë këtë si një strukturë C.

1004
00:46:55,570 --> 00:46:58,260
Ne vetëm duhet për të kombinuar
një simbol, si një char,

1005
00:46:58,260 --> 00:46:59,910
dhe frekuenca në majtë dhe të djathtë.

1006
00:46:59,910 --> 00:47:02,510
Por le të shohim në dy
shembujt e fundit që ju do të

1007
00:47:02,510 --> 00:47:06,070
merrni mjaft të njohur me pas
Quiz zero në problemin vendosur pesë.

1008
00:47:06,070 --> 00:47:09,210
>> Pra, nuk është struktura e të dhënave
i njohur si një tryezë hash.

1009
00:47:09,210 --> 00:47:12,247
Dhe një tabelë hash është lloj i
ftohet në atë që ka kova.

1010
00:47:12,247 --> 00:47:14,830
Dhe mendoj që ka katër kova
këtu, vetëm katër hapësira bosh.

1011
00:47:14,830 --> 00:47:20,830
Këtu është një kuvertë të kartave, dhe këtu është
klub, lopatë, klubi, diamante, klubi,

1012
00:47:20,830 --> 00:47:25,960
diamante, klub, diamante,
clubs-- kështu që kjo është e rastit.

1013
00:47:25,960 --> 00:47:30,330
Zemra, hearts-- kështu që unë jam
bucketizing gjitha inputeve këtu.

1014
00:47:30,330 --> 00:47:32,430
Dhe një nevojë tabelë hash
për të parë në kontributin tuaj,

1015
00:47:32,430 --> 00:47:34,850
dhe pastaj të vënë atë në një farë
zhvillohet bazuar në atë që ju shihni.

1016
00:47:34,850 --> 00:47:35,600
Kjo është një algoritmi.

1017
00:47:35,600 --> 00:47:37,980
Dhe unë isha duke përdorur një super
algoritëm të thjeshtë vizuale.

1018
00:47:37,980 --> 00:47:40,030
Pjesa më e vështirë e cila ishte
kujtuar atë fotografitë ishin.

1019
00:47:40,030 --> 00:47:41,590
Dhe pastaj nuk ka katër gjëra totale.

1020
00:47:41,590 --> 00:47:45,440
>> Tani oxhaqet janë në rritje, e cila
është një gjë e qëllimshme dizajn këtu.

1021
00:47:45,440 --> 00:47:46,540
Por, çfarë tjetër mund të bëj?

1022
00:47:46,540 --> 00:47:49,080
Pra, në fakt këtu kemi një
bandë e librave të vjetër i provimeve të shkollës.

1023
00:47:49,080 --> 00:47:51,240
Supozoni se një bandë e
emrat e studentëve janë në këtu.

1024
00:47:51,240 --> 00:47:52,570
Këtu është një tabelë e madhe hash.

1025
00:47:52,570 --> 00:47:54,867
Në vend të katër kova,
Unë kam, le të themi 26.

1026
00:47:54,867 --> 00:47:57,950
Dhe ne nuk duam të shkuar të marrë hua 26
gjëra nga jashtë [? Annenberg?], Kështu që

1027
00:47:57,950 --> 00:48:00,289
këtu është pesë që përfaqësojnë
Një anë Z. Dhe në qoftë se unë

1028
00:48:00,289 --> 00:48:03,580
shoh një student emri i të cilit fillon me A,
Unë jam duke shkuar për të vënë tij ose quiz e saj atje.

1029
00:48:03,580 --> 00:48:08,850
Nëse dikush fillon me C, atje,
A-- në fakt, nuk dua të bëj atë.

1030
00:48:08,850 --> 00:48:10,060
B shkon mbi këtu.

1031
00:48:10,060 --> 00:48:13,390
Kështu që unë kam marrë A dhe B dhe C. Dhe
Tani këtu është një tjetër Një studente.

1032
00:48:13,390 --> 00:48:16,212
Por nëse kjo tabelë hash është
realizuar me një grup,

1033
00:48:16,212 --> 00:48:17,920
Unë jam lloj i dehur
në këtë pikë, e drejtë?

1034
00:48:17,920 --> 00:48:19,510
Unë lloj i duhet të vënë këtë diku.

1035
00:48:19,510 --> 00:48:24,380
>> Pra, një mënyrë unë mund të zgjidhin këtë është, gjithë
e drejtë, A është e zënë, B është e zënë, C është i zënë.

1036
00:48:24,380 --> 00:48:28,880
Unë jam duke shkuar për të vënë atë në D. Pra, në
së pari, unë kam qasje të rastit të menjëhershme

1037
00:48:28,880 --> 00:48:31,064
secilit prej kova për nxënës.

1038
00:48:31,064 --> 00:48:33,230
Por tani kjo është lloj i transferuar
në diçka lineare,

1039
00:48:33,230 --> 00:48:36,750
sepse në qoftë se unë dua të kërkoni për dikë
emri i të cilit fillon me një, unë kontrolloni këtu.

1040
00:48:36,750 --> 00:48:38,854
Por në qoftë se kjo nuk është një
Studenti Unë jam duke kërkuar për,

1041
00:48:38,854 --> 00:48:41,520
Unë lloj i duhet të fillojnë kontrollin
kova, sepse ajo që kam bërë

1042
00:48:41,520 --> 00:48:44,530
ishte lloj i linear
hetim strukturën e të dhënave.

1043
00:48:44,530 --> 00:48:47,710
Një mënyrë e trashë për të thënë vetëm shikoni
për hapjen e parë në dispozicion,

1044
00:48:47,710 --> 00:48:51,850
dhe të vënë si një plan B, kështu që të flasin,
ose plan D në këtë rast, vlera e

1045
00:48:51,850 --> 00:48:53,340
në atë vend në vend.

1046
00:48:53,340 --> 00:48:56,470
Kjo është vetëm kështu që në qoftë se ju keni
mori 26 vende dhe nuk ka studentë

1047
00:48:56,470 --> 00:49:00,600
me Q emrin apo Z, ose diçka të tillë
që, të paktën ju jeni duke përdorur hapësirë.

1048
00:49:00,600 --> 00:49:03,140
>> Por ne kemi parë tashmë më shumë
zgjidhje zgjuar këtu, apo jo?

1049
00:49:03,140 --> 00:49:04,870
Çfarë do të bëni në vend
në qoftë se ju keni një përplasje?

1050
00:49:04,870 --> 00:49:06,670
Në qoftë se dy njerëz kanë
emri i A, çfarë do

1051
00:49:06,670 --> 00:49:09,160
kanë qenë të zgjuar ose më shumë
zgjidhje intuitive se vetëm

1052
00:49:09,160 --> 00:49:12,840
Duke vënë një ku D është menduar të jetë?

1053
00:49:12,840 --> 00:49:14,810
Pse nuk mundem të shkojnë vetëm
jashtë [? Annenberg?],

1054
00:49:14,810 --> 00:49:19,960
si malloc, një tjetër nyje, e vënë atë
këtu, dhe pastaj të vënë që një student këtu.

1055
00:49:19,960 --> 00:49:22,120
Kështu që unë në thelb kam
një lloj i një grup,

1056
00:49:22,120 --> 00:49:25,590
ose ndoshta më shumë elegante si ne jemi
duke filluar për të parë një listë e lidhur.

1057
00:49:25,590 --> 00:49:29,520
>> Dhe kështu një tabelë hash është një strukturë
që mund të duken vetëm si kjo,

1058
00:49:29,520 --> 00:49:33,900
por më shumë cleverly, ju diçka që quhet
chaining veçantë, ku një tabelë hash

1059
00:49:33,900 --> 00:49:38,340
thjesht është një grup, secili prej
Elementet cilës nuk është një numër,

1060
00:49:38,340 --> 00:49:40,470
në vetvete është një listë e lidhur.

1061
00:49:40,470 --> 00:49:45,080
Në mënyrë që ju të merrni qasje super të shpejtë
të vendosë se ku të hash vlerën tuaj për të.

1062
00:49:45,080 --> 00:49:48,059
Ashtu si me shembullin karta,
Kam bërë vendime të super të shpejtë.

1063
00:49:48,059 --> 00:49:49,600
Zemra shkon këtu, diamante shkon këtu.

1064
00:49:49,600 --> 00:49:52,180
Same këtu, A shkon këtu,
D shkon këtu, B shkon këtu.

1065
00:49:52,180 --> 00:49:55,740
Pra, super të shpejtë look-ups, dhe në qoftë se
ju ndodh që të kandidojë në një rast

1066
00:49:55,740 --> 00:49:59,429
goditjet ku ju keni marrë, dy
njerëz me të njëjtin emër, edhe atëherë

1067
00:49:59,429 --> 00:50:00,970
ju vetëm të fillojnë të lidh ato së bashku.

1068
00:50:00,970 --> 00:50:03,900
Dhe ndoshta ju mbani ato të renditura
alfabetikisht, ndoshta ju nuk e bëni.

1069
00:50:03,900 --> 00:50:05,900
Por të paktën tani kemi dinamizmin.

1070
00:50:05,900 --> 00:50:10,250
Pra, në njërën anë kemi super të shpejtë
kohë konstante, dhe lloj i kohës lineare

1071
00:50:10,250 --> 00:50:14,110
i përfshirë në qoftë se këto lista të lidhura
të fillojë të marrë një pak më të gjatë.

1072
00:50:14,110 --> 00:50:16,880
>> Pra, ky lloj i një trashë,
shaka vjet më geeky më parë.

1073
00:50:16,880 --> 00:50:19,590
Në CS50 hack-a-thon,
kur nxënësit kontrolloni në,

1074
00:50:19,590 --> 00:50:22,040
disa TF ose CA çdo vit
mendon se është qesharake për të vënë

1075
00:50:22,040 --> 00:50:27,772
një shenjë si kjo, ku ai vetëm
do të thotë në qoftë se emri juaj fillon me një A,

1076
00:50:27,772 --> 00:50:28,870
shkojnë në këtë mënyrë.

1077
00:50:28,870 --> 00:50:31,110
Në qoftë se emri juaj fillon
me një B, shko this-- OK,

1078
00:50:31,110 --> 00:50:33,290
kjo është qesharake ndoshta më vonë në semestër.

1079
00:50:33,290 --> 00:50:36,420
Por ka një tjetër
mënyrë për ta bërë këtë, too.

1080
00:50:36,420 --> 00:50:37,410
Kthehuni në atë.

1081
00:50:37,410 --> 00:50:38,600
>> Pra, nuk është kjo strukturë.

1082
00:50:38,600 --> 00:50:40,420
Dhe kjo është e fundit ynë
Struktura për sot,

1083
00:50:40,420 --> 00:50:42,400
e cila është diçka që quhet një Trie.

1084
00:50:42,400 --> 00:50:47,140
T-R-I-E, e cila për disa arsye është e shkurtër
për rikthim, por ajo që quhet Trie.

1085
00:50:47,140 --> 00:50:51,389
Pra, një Trie është një tjetër interesante
amalgamë e një shumë prej këtyre ideve.

1086
00:50:51,389 --> 00:50:52,930
Kjo është një pemë, që kemi parë më parë.

1087
00:50:52,930 --> 00:50:54,180
Kjo nuk është një pemë binare e kërkimit.

1088
00:50:54,180 --> 00:50:58,410
Kjo është një pemë me ndonjë numër të fëmijëve,
por secili prej të fëmijëve në një Trie

1089
00:50:58,410 --> 00:51:00,090
është një koleksion.

1090
00:51:00,090 --> 00:51:04,790
Një grup i madhësisë, të themi, 26 ose ndoshta 27
në qoftë se ju doni të mbështetur emrat shkruar me vizë

1091
00:51:04,790 --> 00:51:06,790
ose apostrofat në emrat e njerëzve.

1092
00:51:06,790 --> 00:51:08,280
>> Dhe kështu kjo është një strukturë e të dhënave.

1093
00:51:08,280 --> 00:51:10,290
Dhe në qoftë se ju shikoni nga lart
deri në fund, si në qoftë se ju

1094
00:51:10,290 --> 00:51:13,710
shikoni në nyjen e lartë atje, M, është
duke treguar për gjë pari nga e majta atje,

1095
00:51:13,710 --> 00:51:17,665
i cili është atëherë A, X, W, E, L, L. Kjo
vetëm një strukturë të dhëna që në mënyrë arbitrare

1096
00:51:17,665 --> 00:51:19,120
është ruajtjen emrat e njerëzve.

1097
00:51:19,120 --> 00:51:25,720
Dhe Maxwell është ruajtur nga vetëm pas
një rrugë e vektorit në grup në rrjet.

1098
00:51:25,720 --> 00:51:30,050
Por ajo që është e mahnitshme rreth një Trie është
se, ndërsa një listë të lidhura dhe madje

1099
00:51:30,050 --> 00:51:34,520
një grup, më të mirë që kemi marrë ndonjëherë është
Ora linear ose kohë logaritmike kërkim

1100
00:51:34,520 --> 00:51:35,600
dikush lart.

1101
00:51:35,600 --> 00:51:40,530
Në këtë strukturë të dhënave të një Trie, nëse
Struktura e të dhënave im ka një emër në të

1102
00:51:40,530 --> 00:51:43,720
dhe unë jam duke kërkuar për Maxwell, unë jam
duke shkuar për të gjetur atë shumë shpejt.

1103
00:51:43,720 --> 00:51:47,910
Unë vetëm shikoni për M-A-X-W-E-L-L. Nëse
kjo strukturë të dhëna, nga ana tjetër,

1104
00:51:47,910 --> 00:51:51,830
nëse N është një milion, në qoftë se ka një
milion emra në këtë strukturë të të dhënave,

1105
00:51:51,830 --> 00:51:57,100
Maxwell është ende do të jetë
discoverable pas vetëm M-A-X-E-W-L-L

1106
00:51:57,100 --> 00:51:58,090
hapa.

1107
00:51:58,090 --> 00:52:01,276
Dhe David-- D-A-V-I-D hapa.

1108
00:52:01,276 --> 00:52:03,400
Me fjalë të tjera, duke ndërtuar
një strukturë e të dhënave që është

1109
00:52:03,400 --> 00:52:07,240
mori të gjitha këto vargjeve, të cilat
vetë mbështesin qasje të rastit,

1110
00:52:07,240 --> 00:52:11,090
Unë mund të filloni të kërkoni deri të njerëzve
emri duke përdorur një sasi të kohës që është

1111
00:52:11,090 --> 00:52:14,340
proporcional me numrin jo
i gjërave në strukturën e të dhënave,

1112
00:52:14,340 --> 00:52:16,330
si një milion emra ekzistuese.

1113
00:52:16,330 --> 00:52:20,135
Sasinë e kohës që duhet për mua për të gjetur
M-A-X-E-W-L-L në këtë strukturë të dhënave është

1114
00:52:20,135 --> 00:52:22,260
nuk proporcional me
madhësia e strukturës së të dhënave,

1115
00:52:22,260 --> 00:52:25,930
por gjatësia e emri.

1116
00:52:25,930 --> 00:52:28,440
Dhe realisht
emra ne jemi duke kërkuar deri

1117
00:52:28,440 --> 00:52:29,970
kurrë nuk do të jetë i çmendur gjatë.

1118
00:52:29,970 --> 00:52:32,600
Ndoshta dikush ka karakter 10
emri, 20 emër karakter.

1119
00:52:32,600 --> 00:52:33,900
Është sigurisht fundme, e drejtë?

1120
00:52:33,900 --> 00:52:37,110
Nuk është një njeri mbi tokë që
ka emrin më të gjatë të jetë e mundur,

1121
00:52:37,110 --> 00:52:39,920
por se emri është një konstante
Gjatësia vlera, e drejtë?

1122
00:52:39,920 --> 00:52:41,980
Ajo nuk ndryshon në asnjë kuptim.

1123
00:52:41,980 --> 00:52:45,090
Pra, në këtë mënyrë, ne kemi
arritur një strukturë të dhënave

1124
00:52:45,090 --> 00:52:47,800
se është koha konstante look-up.

1125
00:52:47,800 --> 00:52:50,670
Ajo ka marrë një numër hapash
në varësi të gjatësisë së dhëna,

1126
00:52:50,670 --> 00:52:54,250
por jo edhe numrin e emrit
në strukturën e të dhënave.

1127
00:52:54,250 --> 00:52:58,700
Pra, nëse ne dyfishojë numrin e emrave
vitin e ardhshëm nga një miliard në dy miliardë,

1128
00:52:58,700 --> 00:53:03,720
gjetje Maxwell do të marrë
Numri i saktë të njëjtën e shtatë hapa

1129
00:53:03,720 --> 00:53:04,650
për të gjetur atë.

1130
00:53:04,650 --> 00:53:08,810
Dhe kështu që ne duket se kanë arritur
Gral jonë e shenjtë për drejtimin e kohës.

1131
00:53:08,810 --> 00:53:10,860
>> Pra, një çift i njoftimeve shpejtë.

1132
00:53:10,860 --> 00:53:11,850
Quiz zero po afrohet.

1133
00:53:11,850 --> 00:53:14,600
Më shumë se në faqen e internetit të kursit
gjatë dy ditëve të ardhshme.

1134
00:53:14,600 --> 00:53:17,120
Hënës lecture-- kjo është një festë
këtu në Harvard të hënën.

1135
00:53:17,120 --> 00:53:18,850
Kjo nuk është në New Haven,
kështu që ne jemi duke marrë klasën

1136
00:53:18,850 --> 00:53:20,310
për Haven re për leksion të hënën.

1137
00:53:20,310 --> 00:53:22,550
Çdo gjë do të jetë filmuar
dhe Transmetuar jetojnë si zakonisht,

1138
00:53:22,550 --> 00:53:24,900
por le të përfundojë sot
me një clip 30 dytë

1139
00:53:24,900 --> 00:53:26,910
quajtur "Mendime thellë"
nga Daven Farnham, e cila

1140
00:53:26,910 --> 00:53:30,850
u frymëzua vitin e kaluar nga e shtuna
"Mendimet e thellë" Night Live s

1141
00:53:30,850 --> 00:53:35,700
nga Jack i dobishëm, i cili
tani duhet të bëjë kuptim.

1142
00:53:35,700 --> 00:53:38,810
>> FILM: Dhe tani, "Thellë
Mendime "nga Daven Farnham.

1143
00:53:38,810 --> 00:53:42,100

1144
00:53:42,100 --> 00:53:42,870
Tabelë Hash.

1145
00:53:42,870 --> 00:53:45,940

1146
00:53:45,940 --> 00:53:47,660
>> SPEAKER 1: Në rregull, kjo është ajo tani për tani.

1147
00:53:47,660 --> 00:53:48,805
Ne do të shihemi javën e ardhshme.

1148
00:53:48,805 --> 00:53:55,380

1149
00:53:55,380 --> 00:53:56,680
>> DOUG: Për të parë atë në veprim.

1150
00:53:56,680 --> 00:53:58,304
Pra, le të marrin një vështrim në atë të drejtë tani.

1151
00:53:58,304 --> 00:53:59,890
Kështu që këtu, ne kemi një rrjet Unsorted.

1152
00:53:59,890 --> 00:54:04,860
>> IAN: Doug, ju mund të shkoni përpara dhe restart
kjo për vetëm një të dytë, ju lutem.

1153
00:54:04,860 --> 00:54:08,562
Të gjithë të drejtë, kamerat janë kodrina, kështu
veprim sa herë që ju jeni gati, Doug, OK?

1154
00:54:08,562 --> 00:54:11,020
DOUG: Të gjithë të drejtë, kështu që ajo që ne
kemi këtu është një koleksion Unsorted.

1155
00:54:11,020 --> 00:54:13,960
Dhe unë e kam me ngjyrë të gjitha elementet
kuqe për të treguar se ajo është, në fakt,

1156
00:54:13,960 --> 00:54:14,460
Unsorted.

1157
00:54:14,460 --> 00:54:17,960
Kështu kujtojnë se gjëja e parë që ne bëjmë
është ne lloj gjysmën e majtë të vektorit.

1158
00:54:17,960 --> 00:54:20,630
Pastaj ne lloj të drejtën
gjysma e vektorit.

1159
00:54:20,630 --> 00:54:22,830
Dhe ya-da, ya-da, ya-da,
ne bashkojë ato së bashku.

1160
00:54:22,830 --> 00:54:24,520
Dhe ne kemi një rrjet krejtësisht të renditura.

1161
00:54:24,520 --> 00:54:25,360
Pra, kjo është se si të bashkohen lloj funksionon.

1162
00:54:25,360 --> 00:54:27,109
>> IAN: Whoa, ee, ee,
prerë, të prerë, të prerë, të prerë.

1163
00:54:27,109 --> 00:54:30,130
Doug, ju nuk mund vetëm ya-da, ya-da,
ya-da, në rrugën tuaj nëpërmjet merge lloj.

1164
00:54:30,130 --> 00:54:31,970
>> DOUG: Unë vetëm e bëri.

1165
00:54:31,970 --> 00:54:32,832
Kjo është në rregull.

1166
00:54:32,832 --> 00:54:33,540
Ne jemi të mirë për të shkuar.

1167
00:54:33,540 --> 00:54:34,760
Le të vetëm i mbajnë kodrina.

1168
00:54:34,760 --> 00:54:35,380
Pra, gjithsesi,

1169
00:54:35,380 --> 00:54:37,800
>> IAN: Ju keni për të shpjeguar
atë më të plotë se kaq.

1170
00:54:37,800 --> 00:54:39,999
Kjo nuk është vetëm e mjaftueshme.

1171
00:54:39,999 --> 00:54:41,790
DOUG: Ian, ne nuk bëjmë
duhet të kthehemi në një.

1172
00:54:41,790 --> 00:54:42,350
Kjo është në rregull.

1173
00:54:42,350 --> 00:54:45,690
Pra, gjithsesi, në qoftë se ne vazhdojmë me merge--
Ian, ne jemi në mes të xhirimeve.

1174
00:54:45,690 --> 00:54:46,612
>> IAN: Unë e di.

1175
00:54:46,612 --> 00:54:49,320
Dhe ne nuk mund vetëm ya-da, ya-da,
ya-da, përmes procesit të tërë.

1176
00:54:49,320 --> 00:54:52,200
Ju duhet të shpjegojë se si
dy palët të bashkohen së bashku.

1177
00:54:52,200 --> 00:54:53,570
>> DOUG: Por ne kemi tashmë
shpjegoi se si dy sides--

1178
00:54:53,570 --> 00:54:55,321
>> IAN: Ju keni treguar vetëm
ata një grup bashkojë.

1179
00:54:55,321 --> 00:54:56,486
DOUG: Ata e dinë procesin.

1180
00:54:56,486 --> 00:54:57,172
Ata janë në rregull.

1181
00:54:57,172 --> 00:54:58,380
Ne kemi shkuar mbi të dhjetë herë.

1182
00:54:58,380 --> 00:55:00,330
>> IAN: Ju vetëm skipped drejtë mbi të.

1183
00:55:00,330 --> 00:55:03,360
Ne jemi duke shkuar prapa në një, ju
nuk mund ti ya-da, da ya-mbi të.

1184
00:55:03,360 --> 00:55:05,480
Të gjithë të drejtë, kthehet në një.

1185
00:55:05,480 --> 00:55:07,833
>> DOUG: Më duhet të kthehem
nëpër të gjitha slides?

1186
00:55:07,833 --> 00:55:08,332
Perëndia im.

1187
00:55:08,332 --> 00:55:11,008

1188
00:55:11,008 --> 00:55:13,004
Kjo është si herën e gjashtë, Ian.

1189
00:55:13,004 --> 00:55:13,940
Kjo është në rregull.

1190
00:55:13,940 --> 00:55:15,200
>> IAN: Në rregull.

1191
00:55:15,200 --> 00:55:16,590
Jeni gati?

1192
00:55:16,590 --> 00:55:17,400
I madh.

1193
00:55:17,400 --> 00:55:18,950
Veprim.