1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Week 6]

2
00:00:02,000 --> 00:00:04,000
[David J. Malan] [Harvard Universiteit]

3
00:00:04,000 --> 00:00:08,000
[Hierdie is CS50.] [CS50.TV]

4
00:00:08,000 --> 00:00:12,000
>> Dit is CS50, en dit is die begin van die Week 6,

5
00:00:12,000 --> 00:00:16,000
so 'n paar nuwe tools is nou beskikbaar vir jou voordeel te trek uit,

6
00:00:16,000 --> 00:00:19,000
waarvan die eerste CS50 Style genoem.

7
00:00:19,000 --> 00:00:22,000
Kans is as jy soos my of enige van die onderrig-genote,

8
00:00:22,000 --> 00:00:26,000
het jy waarskynlik 'n program gesien wie se styl lyk 'n bietjie iets soos hierdie.

9
00:00:26,000 --> 00:00:30,000
Miskien het jy begin sny 'n paar hoeke laat in die nag, of jy sal hanteer dit later,

10
00:00:30,000 --> 00:00:32,000
en dan 'n TF of CA kom gedurende kantoorure.

11
00:00:32,000 --> 00:00:34,000
Dan is dit moeilik vir ons om te lees.

12
00:00:34,000 --> 00:00:38,000
Wel, hierdie kode is sintakties korrek, en dit sal stel, en dit sal eintlik loop.

13
00:00:38,000 --> 00:00:40,000
Maar dit is beslis nie 'n 5 vir styl.

14
00:00:40,000 --> 00:00:45,000
>> Maar nou, as ons gaan in hierdie gids hier-

15
00:00:45,000 --> 00:00:48,000
en kennis dat ek conditions2.c-

16
00:00:48,000 --> 00:00:55,000
en ek loop hierdie nuwe gebod, style50, op hierdie lêer conditions2.c, Enter,

17
00:00:55,000 --> 00:00:57,000
opmerk dat dit my in kennis gestel dat dit is gestileerd.

18
00:00:57,000 --> 00:01:00,000
Gedit opgemerk dat die lêer op die skyf verander is,

19
00:01:00,000 --> 00:01:08,000
en as ek kliek herlaai, is nou al jou probleme geoutomatiseer.

20
00:01:08,000 --> 00:01:15,000
[Applous]

21
00:01:15,000 --> 00:01:17,000
Dit is een van die dinge wat ons gedoen het hierdie naweek.

22
00:01:17,000 --> 00:01:20,000
Besef dat dit onvolmaak is, want daar is 'n paar kode

23
00:01:20,000 --> 00:01:23,000
dat dit net sal nie in staat wees om perfek te stileer,

24
00:01:23,000 --> 00:01:26,000
maar besef dit is nou 'n instrument wat jy kan neem voordeel van

25
00:01:26,000 --> 00:01:33,000
al was dit net om op te ruim sommige van die meer errantly geplaas krullerige draadjies en die wil.

26
00:01:33,000 --> 00:01:36,000
>> Maar meer dwingende is nou CS50 Check.

27
00:01:36,000 --> 00:01:39,000
Met CS50 Check, kan jy eintlik dieselfde korrektheid toetse verrig

28
00:01:39,000 --> 00:01:42,000
op jou eie kode wat die onderrig genote in staat is om te.

29
00:01:42,000 --> 00:01:44,000
Dit is 'n command line nut wat kom nou in die toestel

30
00:01:44,000 --> 00:01:46,000
so gou as wat jy doen 'n update50 soos per

31
00:01:46,000 --> 00:01:49,000
pset 4 spesifikasies, en jy gebruik dit in wese soos hierdie.

32
00:01:49,000 --> 00:01:51,000
Jy loop die opdrag check50.

33
00:01:51,000 --> 00:01:56,000
Dan moet jy slaag in 'n command line argument, of meer algemeen bekend as 'n skakel of 'n vlag.

34
00:01:56,000 --> 00:01:58,000
In die algemeen, is dinge wat koppeltekens genoem 'n skakelaar

35
00:01:58,000 --> 00:02:02,000
aan 'n command line program, so-c spesifiseer

36
00:02:02,000 --> 00:02:04,000
die kontrole wat jy wil uit te voer.

37
00:02:04,000 --> 00:02:07,000
>> Die toetse wat jy wil uit te voer is uniek geïdentifiseer deur hierdie string,

38
00:02:07,000 --> 00:02:10,000
2012/pset4/resize.

39
00:02:10,000 --> 00:02:13,000
Met ander woorde, dit is net 'n arbitrêre, maar unieke string

40
00:02:13,000 --> 00:02:18,000
wat ons gebruik om te identifiseer pset 4 se korrektheid toetse.

41
00:02:18,000 --> 00:02:21,000
En dan moet jy spesifiseer 'n spasie geskei lys van die lêers wat jy wil oplaai

42
00:02:21,000 --> 00:02:24,000
CS50 Check vir ontleding.

43
00:02:24,000 --> 00:02:29,000
Byvoorbeeld, as ek gaan in my oplossing hier vir resize.c-

44
00:02:29,000 --> 00:02:31,000
laat my oop te maak 'n groter terminale venster-

45
00:02:31,000 --> 00:02:42,000
en ek gaan voort en loop laat ons sê check50-c 2012/pset4/resize,

46
00:02:42,000 --> 00:02:46,000
en dan het ek gaan voort en gee die name van die lêers,

47
00:02:46,000 --> 00:02:49,000
resize.c, en dan druk Enter dit saamgepers,

48
00:02:49,000 --> 00:02:53,000
dit upload, dit kontroleer of dit, en ek versuim het om 'n hele klomp van die toetse.

49
00:02:53,000 --> 00:02:59,000
Die een in rooi op links bo sê dat resize.c en bmp bestaan.

50
00:02:59,000 --> 00:03:01,000
Dit was die toets. Dit was die vraag wat ons gestel het.

51
00:03:01,000 --> 00:03:04,000
En dit is ongelukkig omdat die antwoord vals was.

52
00:03:04,000 --> 00:03:08,000
Sê die wit teks onder dit verwag bmp.h om te bestaan, en dis net my skuld.

53
00:03:08,000 --> 00:03:11,000
Ek het vergeet om dit te laai nie, so ek moet beide lêers te laai,

54
00:03:11,000 --> 00:03:14,000
resize.c en bmp.h.

55
00:03:14,000 --> 00:03:17,000
Maar kyk nou na al die ander toetse in geel omdat hulle nie loop nie,

56
00:03:17,000 --> 00:03:21,000
en so die smiley gesig is vertikale, want hy is nie gelukkig of hartseer,

57
00:03:21,000 --> 00:03:25,000
maar ons het dat die probleem reg te stel in rooi voor die ander tjeks sal loop.

58
00:03:25,000 --> 00:03:27,000
>> Laat ek dit regmaak.

59
00:03:27,000 --> 00:03:30,000
Laat my uitzoomen en heruitzend hierdie, hierdie keer met bmp.h ook

60
00:03:30,000 --> 00:03:34,000
op die command line, Enter, en nou as alles goed gaan,

61
00:03:34,000 --> 00:03:38,000
dit gaan om te kyk en dan terug gevolg van hou asem-

62
00:03:38,000 --> 00:03:42,000
al die groen, wat beteken dat ek regtig goed doen op pset 4 tot dusver.

63
00:03:42,000 --> 00:03:44,000
Jy kan sien en aflei uit die beskrywende teks hier

64
00:03:44,000 --> 00:03:47,000
presies wat dit is wat ons getoets het.

65
00:03:47,000 --> 00:03:49,000
Ons getoets het, die eerste keer nie die lêers bestaan?

66
00:03:49,000 --> 00:03:51,000
Ons het toe getoets doen resize.c saamstel?

67
00:03:51,000 --> 00:03:58,000
Toe het ons getoets het, beteken dit nie die grootte van 'n 1x1-pixel BMP wanneer n, die grootte van faktor, is 1.

68
00:03:58,000 --> 00:04:01,000
Nou, as jy het geen idee wat n, sal jy wanneer jy duik in pset 4,

69
00:04:01,000 --> 00:04:04,000
maar dit is net 'n gesonde verstand gaan om seker te maak dat jy nie resizing

70
00:04:04,000 --> 00:04:08,000
'n beeld as die grootte van faktor is 1.

71
00:04:08,000 --> 00:04:14,000
Indien, in teenstelling, is dit die grootte van 'n 1x1 pixel na 'n 1x1 pixel BMP 2x2 korrek

72
00:04:14,000 --> 00:04:19,000
wanneer n 2, dan is insgelyks, my vorm dienooreenkomstig.

73
00:04:19,000 --> 00:04:22,000
>> In kort, hierdie is bedoel om, een, die kruising van die vingers

74
00:04:22,000 --> 00:04:25,000
uit die vergelyking reg voordat jy 'jou pset.

75
00:04:25,000 --> 00:04:28,000
Jy sal presies weet wat jou TF binnekort sal weet

76
00:04:28,000 --> 00:04:30,000
wanneer jy gaan oor die stuur van sommige van hierdie probleem stelle,

77
00:04:30,000 --> 00:04:34,000
en ook die pedagogiese motivering is regtig te sit

78
00:04:34,000 --> 00:04:37,000
die geleentheid om in die voorkant van jou, sodat wanneer jy weet a priori

79
00:04:37,000 --> 00:04:39,000
dat daar foute in jou kode en toetse is wat nie geslaag het,

80
00:04:39,000 --> 00:04:43,000
jy kan sit in 'n meer effektiewe tyd aan die voorkant om die probleme op te los

81
00:04:43,000 --> 00:04:45,000
eerder as verloor punte, kry terugvoering van jou TF,

82
00:04:45,000 --> 00:04:48,000
en gaan dan, "Ahh," soos ek uitgepluis dat uit.

83
00:04:48,000 --> 00:04:50,000
Nou ten minste daar is 'n hulpmiddel om te help jy vind dat.

84
00:04:50,000 --> 00:04:52,000
Dit gaan nie om uit te wys waar die fout is, maar dit sal jou vertel

85
00:04:52,000 --> 00:04:54,000
wat is simptomaties is van dit.

86
00:04:54,000 --> 00:04:57,000
>> Besef nou die toetse is nie noodwendig volledig nie.

87
00:04:57,000 --> 00:04:59,000
Net omdat jy 'n skerm vol van groen smiley gesigte

88
00:04:59,000 --> 00:05:02,000
beteken nie dat jou kode is volmaak nie, maar dit beteken

89
00:05:02,000 --> 00:05:06,000
dat dit geslaag het om sekere toetse voorgeskryf deur die spec.

90
00:05:06,000 --> 00:05:08,000
Soms sal ons nie vry van tjeks.

91
00:05:08,000 --> 00:05:10,000
Byvoorbeeld, detective verhaal, een van die aspekte van pset 4,

92
00:05:10,000 --> 00:05:15,000
is 'n soort van teleurstellend as ons gee jou

93
00:05:15,000 --> 00:05:18,000
die antwoord as wat dit is, en daar is 'n aantal maniere om te openbaar

94
00:05:18,000 --> 00:05:21,000
wat die persoon is in daardie rooi geraas.

95
00:05:21,000 --> 00:05:24,000
Die spec sal altyd spesifiseer in die toekoms vir pset 5 af

96
00:05:24,000 --> 00:05:26,000
wat bestaan ​​kontroleer vir jou.

97
00:05:26,000 --> 00:05:28,000
Jy sal sien daar is hierdie wit URL aan die onderkant.

98
00:05:28,000 --> 00:05:30,000
Vir nou, dit is net diagnose uitloop.

99
00:05:30,000 --> 00:05:33,000
As jy die URL besoek, kry jy 'n hele klomp van die gek, kriptiese boodskappe

100
00:05:33,000 --> 00:05:36,000
dat jy is welkom om te kyk deur, maar dit is meestal vir die personeel

101
00:05:36,000 --> 00:05:41,000
sodat ons kan diagnoseer en te ontfout foute in check50 self.

102
00:05:41,000 --> 00:05:46,000
>> Sonder ado, laat ons beweeg aan waar ons opgehou het.

103
00:05:46,000 --> 00:05:48,000
CS50 biblioteek wat ons as vanselfsprekend aanvaar vir 'n paar weke,

104
00:05:48,000 --> 00:05:52,000
maar dan verlede week, het ons begin peeling terug een van die lae van dit.

105
00:05:52,000 --> 00:05:55,000
Ons het begin sit eenkant string ten gunste van wat plaas?

106
00:05:55,000 --> 00:05:57,000
[Studente] Char.

107
00:05:57,000 --> 00:05:59,000
Char *, wat is 'n char * al die tyd,

108
00:05:59,000 --> 00:06:03,000
maar nou het ons nie voor te gee dat dit 'n werklike data string-tipe.

109
00:06:03,000 --> 00:06:06,000
Inteendeel, dit is 'n sinoniem van spesies vir char *

110
00:06:06,000 --> 00:06:09,000
en 'n string is 'n reeks van karakters,

111
00:06:09,000 --> 00:06:14,000
so hoekom maak dit sin snare te stel as char * s?

112
00:06:14,000 --> 00:06:20,000
Wat beteken 'n char * verteenwoordig in die konteks van hierdie konsep van 'n string?

113
00:06:20,000 --> 00:06:23,000
Ja >> [Studente] Die eerste karakter.

114
00:06:23,000 --> 00:06:25,000
Goed, die eerste karakter, maar nie heeltemal die eerste karakter.

115
00:06:25,000 --> 00:06:27,000
Dit is die [Studente] Adres.

116
00:06:27,000 --> 00:06:29,000
Goed, die adres van die eerste karakter.

117
00:06:29,000 --> 00:06:33,000
Al wat nodig is om 'n string te verteenwoordig in 'n rekenaar se geheue

118
00:06:33,000 --> 00:06:36,000
is net die unieke adres van sy heel eerste byte.

119
00:06:36,000 --> 00:06:38,000
Jy hoef nie eens te weet hoe lank dit is

120
00:06:38,000 --> 00:06:42,000
want hoe kan jy figuur wat uit dinamies?

121
00:06:42,000 --> 00:06:44,000
[Studente] String lengte.

122
00:06:44,000 --> 00:06:48,000
Jy kan bel string lengte, 'n uitstekende, maar hoe werk string lengte?

123
00:06:48,000 --> 00:06:50,000
Wat doen dit? Ja.

124
00:06:50,000 --> 00:06:52,000
[Studente] hou gaan totdat jy die null karakter.

125
00:06:52,000 --> 00:06:54,000
Ja, presies, is dit iterate net met 'n for-lus, terwyl loop,

126
00:06:54,000 --> 00:06:57,000
ongeag van * tot aan die einde en die einde word verteenwoordig

127
00:06:57,000 --> 00:07:01,000
deur \ 0, die sogenaamde nul karakter, nul,

128
00:07:01,000 --> 00:07:05,000
moet nie verwar word met null, wat is 'n wyser,

129
00:07:05,000 --> 00:07:07,000
wat sal kom in 'n gesprek vandag weer.

130
00:07:07,000 --> 00:07:11,000
>> Ons geskil terug 'n laag van getint, en dan het ons 'n blik op GetString,

131
00:07:11,000 --> 00:07:14,000
en dat beide van daardie werksaamhede, of regtig onthou,

132
00:07:14,000 --> 00:07:18,000
GetString, was die gebruik van 'n sekere funksie

133
00:07:18,000 --> 00:07:21,000
om werklik te verwerk, is dat, lees of te analiseer, die gebruiker se insette.

134
00:07:21,000 --> 00:07:25,000
En wat was dat die nuwe funksie?

135
00:07:25,000 --> 00:07:27,000
Scanf of sscanf. Dit kom eintlik in 'n paar verskillende geure.

136
00:07:27,000 --> 00:07:31,000
Daar is scanf, daar is sscanf, daar is fscanf.

137
00:07:31,000 --> 00:07:35,000
Vir nou, al is, laat se fokus op die een wat die meeste maklik geïllustreer,

138
00:07:35,000 --> 00:07:38,000
en laat my gaan voort en oop te maak in die toestel

139
00:07:38,000 --> 00:07:41,000
'n lêer soos hierdie, scanf1.c.

140
00:07:41,000 --> 00:07:43,000
Dit is 'n super eenvoudige program,

141
00:07:43,000 --> 00:07:46,000
maar wat nie iets wat ons nog nooit voorheen gedoen

142
00:07:46,000 --> 00:07:48,000
sonder die hulp van die CS50 biblioteek.

143
00:07:48,000 --> 00:07:51,000
Dit kry 'n int van 'n gebruiker. Hoe werk dit?

144
00:07:51,000 --> 00:07:53,000
Wel, in line 16 daar,

145
00:07:53,000 --> 00:07:56,000
sien dat ons 'n int genoem x verklaar, en op hierdie punt in die verhaal,

146
00:07:56,000 --> 00:07:58,000
wat is die waarde van x?

147
00:07:58,000 --> 00:08:00,000
[Onhoorbaar student reaksie]

148
00:08:00,000 --> 00:08:02,000
[David M.] Right, wie weet, sommige vullis waarde potensieel, so in 17, ons het net vir die gebruiker

149
00:08:02,000 --> 00:08:06,000
gee my 'n nommer, asseblief, en stap 18 is waar dit raak interessant.

150
00:08:06,000 --> 00:08:11,000
Scanf blyk 'n idee van printf te leen in die sin dat dit gebruik hierdie formaat kodes in aanhalingstekens.

151
00:08:11,000 --> 00:08:13,000
% D is natuurlik 'n desimale getal.

152
00:08:13,000 --> 00:08:21,000
Maar hoekom is ek wat in & x in plaas van net x?

153
00:08:21,000 --> 00:08:24,000
Die voormalige is korrek. Ja.

154
00:08:24,000 --> 00:08:26,000
[Onhoorbaar student reaksie]

155
00:08:26,000 --> 00:08:31,000
Presies, indien die doel van hierdie program, soos die funksie getint self,

156
00:08:31,000 --> 00:08:34,000
is om 'n int te kry van die gebruiker wat ek kan slaag funksies

157
00:08:34,000 --> 00:08:38,000
al die veranderlikes wat ek wil, maar as ek nie slaag nie hulle deur verwysing

158
00:08:38,000 --> 00:08:41,000
of deur adres of by pointer, al sinoniem vir vandag se doeleindes,

159
00:08:41,000 --> 00:08:46,000
dan is dat die funksie het geen vermoë om die inhoud van daardie veranderlike te verander.

160
00:08:46,000 --> 00:08:49,000
Dit sal in 'n kopie, net soos die karretjie weergawe van swap

161
00:08:49,000 --> 00:08:51,000
dat ons het gepraat oor 'n paar keer nou.

162
00:08:51,000 --> 00:08:54,000
>> Maar in plaas daarvan, deur dit te doen en x, ek letterlik in wat verbygaan?

163
00:08:54,000 --> 00:08:57,000
[Studente] Die adres. >> Die adres van x.

164
00:08:57,000 --> 00:09:01,000
Dit is soos die trek van 'n kaart vir die funksie met die naam scanf en sê hier,

165
00:09:01,000 --> 00:09:04,000
dit is aanwysings na 'n stuk van die geheue in die rekenaar

166
00:09:04,000 --> 00:09:07,000
wat jy kan gaan stoor sommige heelgetal.

167
00:09:07,000 --> 00:09:10,000
Ten einde vir sscanf te doen noudat

168
00:09:10,000 --> 00:09:13,000
wat die operateur, is watter stuk van die sintaksis dit gaan te hê om te gebruik

169
00:09:13,000 --> 00:09:19,000
Selfs al kan ons dit nie sien nie, want iemand anders het hierdie funksie?

170
00:09:19,000 --> 00:09:21,000
Met ander woorde - wat is dit?

171
00:09:21,000 --> 00:09:23,000
[Studente] X gelees.

172
00:09:23,000 --> 00:09:27,000
Daar gaan 'n lesing, maar slegs met betrekking tot x hier.

173
00:09:27,000 --> 00:09:30,000
As scanf word verby die adres van x,

174
00:09:30,000 --> 00:09:35,000
sintakties, watter operateur verbind tot êrens bestaan

175
00:09:35,000 --> 00:09:38,000
binnekant van scanf se implementering sodat scanf

176
00:09:38,000 --> 00:09:42,000
kan eintlik skryf 'n aantal 2 na daardie adres?

177
00:09:42,000 --> 00:09:44,000
Ja, so het die *.

178
00:09:44,000 --> 00:09:47,000
Onthou dat die * is ons dereference operateur, wat in wese beteken daar gaan.

179
00:09:47,000 --> 00:09:50,000
>> As jy is oorhandig 'n adres, soos hier die geval is,

180
00:09:50,000 --> 00:09:53,000
scanf is waarskynlik as ons werklik het om die bronkode-

181
00:09:53,000 --> 00:09:59,000
* x of die ekwivalent daarvan om werklik te gaan na die adres en daar 'n bietjie waarde te doen.

182
00:09:59,000 --> 00:10:02,000
Nou, as vir hoe scanf kry insette van die sleutelbord,

183
00:10:02,000 --> 00:10:04,000
ons sal beweeg ons hande uit vir vandag.

184
00:10:04,000 --> 00:10:07,000
Net aanneem dat die bedryfstelsel kan sscanf om te praat

185
00:10:07,000 --> 00:10:11,000
aan die gebruiker se sleutelbord, maar op hierdie punt nou in line 19,

186
00:10:11,000 --> 00:10:14,000
wanneer ons net druk x, dit blyk die geval te wees

187
00:10:14,000 --> 00:10:17,000
wat scanf het 'n int in x.

188
00:10:17,000 --> 00:10:19,000
Dit is presies hoe scanf werk, en onthou verlede week

189
00:10:19,000 --> 00:10:25,000
Dit is presies hoe GetString en getint en sy ander familie van funksies

190
00:10:25,000 --> 00:10:28,000
uiteindelik werk, al is dit met 'n effense afwyking soos sscanf,

191
00:10:28,000 --> 00:10:31,000
wat beteken dat 'n string in plaas van die sleutelbord te scan.

192
00:10:31,000 --> 00:10:33,000
Maar laat ons neem 'n blik op 'n klein afwyking van hierdie.

193
00:10:33,000 --> 00:10:37,000
Ek het eintlik In scanf2, screwed up.

194
00:10:37,000 --> 00:10:42,000
Wat is verkeerd en ek sal die kommentaar wat verduidelik soveel verberg

195
00:10:42,000 --> 00:10:47,000
wat is fout met hierdie program, weergawe 2?

196
00:10:47,000 --> 00:10:55,000
Wees so tegniese as moontlik hierdie tyd.

197
00:10:55,000 --> 00:10:57,000
Dit lyk redelik goed.

198
00:10:57,000 --> 00:11:03,000
Dit is mooi ingekeep nie, maar

199
00:11:03,000 --> 00:11:07,000
okay, hoe oor laat snoei dit korter vrae?

200
00:11:07,000 --> 00:11:17,000
Line 16. Wat is lyn 16 te doen in 'n presiese maar tegniese Engels?

201
00:11:17,000 --> 00:11:20,000
'N bietjie ongemaklik. Ja, Michael.

202
00:11:20,000 --> 00:11:25,000
[Studente] Dit verwys na die eerste letter van 'n string.

203
00:11:25,000 --> 00:11:27,000
>> Okay, naby. Laat my dat 'n bietjie tweak.

204
00:11:27,000 --> 00:11:33,000
Wys na die eerste letter van 'n string, jy waarby 'n veranderlike genoem buffer

205
00:11:33,000 --> 00:11:36,000
wat verwys na die eerste adres van 'n string,

206
00:11:36,000 --> 00:11:39,000
of liewer, dit sal meer spesifiek na 'n char wys.

207
00:11:39,000 --> 00:11:42,000
Kennisgewing dit is eintlik nie te wys op enige plek, want daar is geen opdrag operateur.

208
00:11:42,000 --> 00:11:46,000
Daar is geen gelyke teken, sodat alles wat ons doen, is die toekenning van die veranderlike genaamd buffer.

209
00:11:46,000 --> 00:11:49,000
Dit gebeur te wees 32 stukkies, want dit is 'n wyser,

210
00:11:49,000 --> 00:11:52,000
en die inhoud van die buffer vermoedelik uiteindelik

211
00:11:52,000 --> 00:11:57,000
sal 'n adres van 'n char bevat, maar vir nou, wat beteken buffer bevat?

212
00:11:57,000 --> 00:11:59,000
Net 'n paar pseudo, wie weet, sommige vullis waarde,

213
00:11:59,000 --> 00:12:03,000
want ons het nie uitdruklik dit geïnisialiseer word, so moet ons nie aanvaar enigiets.

214
00:12:03,000 --> 00:12:06,000
Okay, so nou lyn 17 wat nie in lyn 17?

215
00:12:06,000 --> 00:12:08,000
Miskien is dit sal warm hierdie up.

216
00:12:08,000 --> 00:12:10,000
Dit druk 'n string, reg?

217
00:12:10,000 --> 00:12:12,000
Dit druk String asseblief.

218
00:12:12,000 --> 00:12:15,000
>> Line 18 is 'n soort van bekende nou dat ons nou net gesien het 'n variansie van hierdie

219
00:12:15,000 --> 00:12:18,000
maar met 'n ander formaat kode, so in lyn 18,

220
00:12:18,000 --> 00:12:23,000
ons vertel scanf hier is die adres van 'n stuk van die geheue.

221
00:12:23,000 --> 00:12:27,000
Ek wil in 'n tou om jou te bel, soos geïmpliseer deur% s,

222
00:12:27,000 --> 00:12:32,000
maar die probleem is dat ons nie 'n paar van die dinge wat hier gedoen het.

223
00:12:32,000 --> 00:12:35,000
Wat is een van die probleme?

224
00:12:35,000 --> 00:12:38,000
[Studente] Dit is probeer om 'n null-aanwijzer te dereference.

225
00:12:38,000 --> 00:12:41,000
Goed, null, of net anders onbekend wysers.

226
00:12:41,000 --> 00:12:45,000
Jy inhandiging scanf 'n adres, maar jy het net 'n oomblik gelede gesê

227
00:12:45,000 --> 00:12:49,000
dat adres is 'n paar vullis waarde, want ons het nie eintlik dit toewys aan enigiets,

228
00:12:49,000 --> 00:12:53,000
en sodat jy vertel scanf effektief gaan sit 'n string hier,

229
00:12:53,000 --> 00:12:56,000
maar ons weet nie waar is hier nog,

230
00:12:56,000 --> 00:12:59,000
so ons het eintlik nie toegeken geheue vir buffer.

231
00:12:59,000 --> 00:13:03,000
Verder, wat is jy ook nie eens vertel scanf?

232
00:13:03,000 --> 00:13:06,000
Veronderstel dit was 'n stuk van die geheue, en dit was nie 'n gemors waarde,

233
00:13:06,000 --> 00:13:09,000
maar jy nog steeds nie vertel scanf iets belangrik.

234
00:13:09,000 --> 00:13:12,000
[Studente] Waar dit eintlik is, die ampersand.

235
00:13:12,000 --> 00:13:15,000
Ampersand, so in hierdie geval, is dit okay.

236
00:13:15,000 --> 00:13:18,000
Omdat die buffer is reeds as 'n wyser verklaar

237
00:13:18,000 --> 00:13:22,000
met die * stuk van sintaksis, het ons nie nodig ampersand te gebruik

238
00:13:22,000 --> 00:13:25,000
want dit is reeds 'n adres, maar ek dink ek het dit gehoor hier.

239
00:13:25,000 --> 00:13:27,000
[Studente] Hoe groot is dit?

240
00:13:27,000 --> 00:13:29,000
Goed, ons nie vertel scanf hoe groot hierdie buffer is,

241
00:13:29,000 --> 00:13:32,000
wat beteken dat selfs as buffer was 'n wyser,

242
00:13:32,000 --> 00:13:35,000
ons sê scanf, het hier 'n string,

243
00:13:35,000 --> 00:13:38,000
maar hier kan wees 2 grepe, kan dit 10 grepe, kan dit 'n megabyte.

244
00:13:38,000 --> 00:13:41,000
Scanf het geen idee nie, want dit is 'n stuk van die geheue

245
00:13:41,000 --> 00:13:43,000
vermoedelik, dit is nie Nog 'n string.

246
00:13:43,000 --> 00:13:48,000
Dit is net 'n string wanneer jy skryf karakters en 'n \ 0 tot daardie stuk van die geheue.

247
00:13:48,000 --> 00:13:51,000
Nou is dit is net 'n stuk van die geheue.

248
00:13:51,000 --> 00:13:55,000
Scanf sal nie weet wanneer om te stop deur skriftelik daarvoor aansoek te doen by daardie adres.

249
00:13:55,000 --> 00:13:59,000
>> As jy 'n paar voorbeelde in die verlede waar ek lukraak op die sleutelbord getik onthou

250
00:13:59,000 --> 00:14:03,000
probeer om oor te loop van 'n buffer, en ons het gepraat oor presies wat op Vrydag.

251
00:14:03,000 --> 00:14:07,000
As 'n teenstander spuit op een of ander manier in jou program 'n veel groter woord

252
00:14:07,000 --> 00:14:10,000
of sin of frase wat jy verwag jy kan oorrompel

253
00:14:10,000 --> 00:14:13,000
'n stuk van die geheue, wat slegte gevolge kan hê,

254
00:14:13,000 --> 00:14:15,000
soos die neem van oor die hele program self.

255
00:14:15,000 --> 00:14:17,000
Ons moet dit op een of ander manier los.

256
00:14:17,000 --> 00:14:20,000
Laat my zoom uit en gaan in weergawe 3 van hierdie program.

257
00:14:20,000 --> 00:14:22,000
Dit is 'n bietjie beter.

258
00:14:22,000 --> 00:14:24,000
In hierdie weergawe, let op die verskil.

259
00:14:24,000 --> 00:14:27,000
In lyn 16, verklaar ek weer 'n veranderlike genoem buffer,

260
00:14:27,000 --> 00:14:29,000
maar wat is dit nou?

261
00:14:29,000 --> 00:14:33,000
Dit is 'n verskeidenheid van 16 karakters.

262
00:14:33,000 --> 00:14:36,000
Dit is goed, want dit beteken ek kan nou scanf vertel

263
00:14:36,000 --> 00:14:39,000
hier is 'n werklike stuk van die geheue.

264
00:14:39,000 --> 00:14:42,000
Jy kan amper dink van skikkings as verwysings nou,

265
00:14:42,000 --> 00:14:44,000
selfs al is hulle nie eintlik ekwivalent.

266
00:14:44,000 --> 00:14:47,000
Hulle sal anders optree in verskillende kontekste.

267
00:14:47,000 --> 00:14:50,000
Maar dit is beslis die geval dat die buffer verwysingstegnieke

268
00:14:50,000 --> 00:14:53,000
16 aangrensende karakters want dit is wat 'n skikking is

269
00:14:53,000 --> 00:14:55,000
en is vir 'n paar weke nou.

270
00:14:55,000 --> 00:14:59,000
>> Hier, ek vertel scanf hier is 'n stuk van die geheue.

271
00:14:59,000 --> 00:15:01,000
Hierdie keer, dit is eintlik 'n stuk van die geheue,

272
00:15:01,000 --> 00:15:07,000
maar waarom is hierdie program nog exploit?

273
00:15:07,000 --> 00:15:11,000
Wat is nog steeds verkeerd?

274
00:15:11,000 --> 00:15:14,000
Ek het gesê gee my 16 bytes maar-

275
00:15:14,000 --> 00:15:16,000
[Studente] Wat gebeur as hulle tik in meer as 16?

276
00:15:16,000 --> 00:15:20,000
Presies, wat as die gebruiker tipes in 17 karakters of 1700 karakters?

277
00:15:20,000 --> 00:15:23,000
Om die waarheid te sê, laat ons kyk of ons kan nie reis oor hierdie fout nou.

278
00:15:23,000 --> 00:15:25,000
Dit is beter, maar nie volmaak nie.

279
00:15:25,000 --> 00:15:28,000
Laat my voort te gaan en uit te voer maak scanf3 hierdie program saam te stel.

280
00:15:28,000 --> 00:15:34,000
Laat ek hardloop scanf3, String asseblief: hello, en ons lyk okay wees.

281
00:15:34,000 --> 00:15:37,000
Laat ek probeer om 'n bietjie langer een, hallo daar.

282
00:15:37,000 --> 00:15:42,000
Goed, kom ons nie daar hallo hoe gaan dit vandag, Enter.

283
00:15:42,000 --> 00:15:54,000
Aan die soort van gelukkig hier, laat ons sê hallo daar hoe gaan dit met jou.

284
00:15:54,000 --> 00:15:56,000
Damn dit.

285
00:15:56,000 --> 00:16:03,000
Okay, so ons het gelukkig. Kom ons kyk of ons dit nie kan regmaak.

286
00:16:03,000 --> 00:16:06,000
Nee, dit is nie van plan om my te laat kopieer.

287
00:16:06,000 --> 00:16:09,000
Kom ons probeer dit weer.

288
00:16:09,000 --> 00:16:12,000
Alle reg, staan.

289
00:16:12,000 --> 00:16:20,000
Ons sal sien hoe lank ek kan voorgee om te fokus terwyl jy nog om dit te doen.

290
00:16:20,000 --> 00:16:23,000
Damn dit. Dit is nogal toepaslik, eintlik.

291
00:16:23,000 --> 00:16:26,000
Daar gaan ons.

292
00:16:26,000 --> 00:16:30,000
Punt gemaak.

293
00:16:30,000 --> 00:16:34,000
>> Dit, verleentheid al is dit ook is, dit is ook een van die bronne van groot verwarring

294
00:16:34,000 --> 00:16:38,000
wanneer die skryf van programme wat foute omdat hulle manifesteer

295
00:16:38,000 --> 00:16:40,000
slegs een keer in 'n rukkie soms.

296
00:16:40,000 --> 00:16:43,000
Die werklikheid is dat selfs as jou kode is heeltemal gebreek,

297
00:16:43,000 --> 00:16:46,000
dit dalk net heeltemal gebreek word een keer in 'n rukkie

298
00:16:46,000 --> 00:16:49,000
want soms, in wese wat gebeur is die bedryfstelsel ken

299
00:16:49,000 --> 00:16:52,000
'n bietjie meer geheue as wat jy werklik nodig het om watter rede ook al,

300
00:16:52,000 --> 00:16:57,000
en so niemand anders is met behulp van die geheue na jou stuk van 16 karakters,

301
00:16:57,000 --> 00:17:01,000
so as jy gaan na 17, 18, 19, wat ook al, dit is nie so 'n groot deal.

302
00:17:01,000 --> 00:17:04,000
Nou, die rekenaar, selfs as dit nie crash op daardie punt,

303
00:17:04,000 --> 00:17:09,000
kan uiteindelik gebruik byte nommer 17 of 18 of 19 vir iets anders,

304
00:17:09,000 --> 00:17:14,000
By watter punt jou data wat jy daar te vestig, al is dit buitensporig lank,

305
00:17:14,000 --> 00:17:18,000
gaan kry oorskryf potensieel deur 'n ander funksie.

306
00:17:18,000 --> 00:17:21,000
Dit is nie noodwendig gaan om te bly ongeskonde,

307
00:17:21,000 --> 00:17:23,000
maar dit sal nie noodwendig veroorsaak 'n seg skuld.

308
00:17:23,000 --> 00:17:26,000
Maar in hierdie geval, het ek uiteindelik genoeg karakters

309
00:17:26,000 --> 00:17:29,000
dat ek wesenlik oorskry my segment van die geheue, en bam,

310
00:17:29,000 --> 00:17:33,000
die bedryfstelsel het gesê: "Jammer, dit is nie goed nie, segmentering skuld."

311
00:17:33,000 --> 00:17:38,000
>> En laat ons nou sien as wat nog hier in my directory

312
00:17:38,000 --> 00:17:40,000
kennis dat ek hierdie lêer hier, kern.

313
00:17:40,000 --> 00:17:42,000
Let daarop dat hierdie is weer 'n kern dump genoem.

314
00:17:42,000 --> 00:17:46,000
Dit is in wese 'n lêer wat bevat die inhoud van jou program se geheue

315
00:17:46,000 --> 00:17:48,000
by die punt waar dit neergestort het,

316
00:17:48,000 --> 00:17:51,000
en net 'n klein voorbeeld om hier te probeer laat my gaan hier

317
00:17:51,000 --> 00:17:57,000
en hardloop gdb op scanf3 en dan 1/3 argument genoem kern spesifiseer,

318
00:17:57,000 --> 00:18:01,000
en hier opmerk dat as ek die kode lys,

319
00:18:01,000 --> 00:18:06,000
sal ons in staat wees om te begin soos gewoonlik met gdb loop deur middel van hierdie program,

320
00:18:06,000 --> 00:18:10,000
en ek kan hardloop en so gou as wat ek getref het-as met die stap opdrag in gdb-

321
00:18:10,000 --> 00:18:13,000
so gou as ek die potensieel buggy lyn getref nadat tik in 'n groot string,

322
00:18:13,000 --> 00:18:16,000
Ek sal in staat wees om werklik te identifiseer dit hier.

323
00:18:16,000 --> 00:18:19,000
Meer inligting oor hierdie, maar in artikel in terme van kern dumps

324
00:18:19,000 --> 00:18:22,000
en die wil sodat jy kan eintlik poke rond binnekant van die kern dump

325
00:18:22,000 --> 00:18:27,000
en kyk op watter lyn die program gedruip het jy.

326
00:18:27,000 --> 00:18:32,000
Enige vrae dan op wysers en adresse?

327
00:18:32,000 --> 00:18:36,000
Want vandag op, ons gaan om te begin neem as vanselfsprekend aanvaar dat hierdie dinge bestaan

328
00:18:36,000 --> 00:18:40,000
en ons weet presies wat hulle is.

329
00:18:40,000 --> 00:18:42,000
Ja.

330
00:18:42,000 --> 00:18:46,000
>> [Studente] Hoe kom jy nie 'n ampersand na die volgende aan die deel-

331
00:18:46,000 --> 00:18:48,000
Goeie vraag.

332
00:18:48,000 --> 00:18:51,000
Hoe kom ek het nie 'n ampersand te sit langs die karakter array soos ek gedoen het voorheen

333
00:18:51,000 --> 00:18:53,000
met die meeste van ons voorbeelde?

334
00:18:53,000 --> 00:18:55,000
Die kort antwoord is skikkings is 'n bietjie spesiale.

335
00:18:55,000 --> 00:18:59,000
Jy kan amper dink dat 'n buffer as eintlik 'n adres,

336
00:18:59,000 --> 00:19:03,000
en dit gebeur net so om die geval te wees dat die vierkantige hakienotasie

337
00:19:03,000 --> 00:19:06,000
is 'n gerief sodat ons kan gaan in bracket 0, bracket 1,

338
00:19:06,000 --> 00:19:10,000
bracket 2, sonder die * notasie te gebruik.

339
00:19:10,000 --> 00:19:13,000
Dit is 'n bietjie van 'n wit leuen omdat skikkings en wysers

340
00:19:13,000 --> 00:19:17,000
is, in werklikheid, 'n bietjie anders, maar hulle kan nie altyd dikwels, maar nie gebruik word nie uitruilbaar.

341
00:19:17,000 --> 00:19:21,000
In kort, as 'n funksie word verwag dat 'n wyser na 'n stuk van die geheue,

342
00:19:21,000 --> 00:19:24,000
jy kan slaag dit 'n adres wat deur malloc teruggestuur is,

343
00:19:24,000 --> 00:19:29,000
en ons sal sien malloc weer kort voor lank, of jy kan slaag dit die naam van 'n skikking.

344
00:19:29,000 --> 00:19:32,000
Jy hoef nie ampersand te doen met skikkings, want hulle is reeds

345
00:19:32,000 --> 00:19:34,000
wese graag adresse.

346
00:19:34,000 --> 00:19:36,000
Dit is die een uitsondering.

347
00:19:36,000 --> 00:19:39,000
Die vierkantige hakies maak hulle spesiaal.

348
00:19:39,000 --> 00:19:41,000
>> Kan jy 'n ampersand langs die buffer?

349
00:19:41,000 --> 00:19:43,000
Nie in hierdie geval.

350
00:19:43,000 --> 00:19:46,000
Dit sou werk nie, want, weer, van hierdie hoek geval

351
00:19:46,000 --> 00:19:49,000
waar skikkings is nie eintlik baie adresse.

352
00:19:49,000 --> 00:19:54,000
Maar ons sal miskien kom terug na wat voor lank met ander voorbeelde.

353
00:19:54,000 --> 00:19:56,000
Laat ons hier probeer om 'n probleem op te los.

354
00:19:56,000 --> 00:20:00,000
Ons het 'n datastruktuur wat ons het is gebruik vir 'n geruime tyd bekend as 'n skikking.

355
00:20:00,000 --> 00:20:02,000
Case in point, dit is wat ons moes net.

356
00:20:02,000 --> 00:20:04,000
Maar skikkings het 'n paar upsides en nadele.

357
00:20:04,000 --> 00:20:06,000
Skikkings is mooi waarom?

358
00:20:06,000 --> 00:20:11,000
Wat is een ding wat jy wil-tot die mate wat jy wil skikkings-oor skikkings?

359
00:20:11,000 --> 00:20:13,000
Wat is gerieflik oor hulle? Wat is dwingende?

360
00:20:13,000 --> 00:20:18,000
Hoekom het ons stel hulle in die eerste plek?

361
00:20:18,000 --> 00:20:20,000
Ja.

362
00:20:20,000 --> 00:20:27,000
[Studente] Hulle kan 'n baie van die data te stoor, en jy hoef nie 'n hele ding om te gebruik.

363
00:20:27,000 --> 00:20:29,000
Jy kan gebruik maak van 'n artikel.

364
00:20:29,000 --> 00:20:32,000
Goed, met 'n verskeidenheid wat jy kan 'n baie van die data stoor,

365
00:20:32,000 --> 00:20:35,000
en jy hoef nie noodwendig al van dit te gebruik, so kan jy overallocate,

366
00:20:35,000 --> 00:20:39,000
wat kan gerieflik wees as jy nie vooraf weet nie hoeveel van iets om te verwag.

367
00:20:39,000 --> 00:20:41,000
>> GetString is 'n perfekte voorbeeld.

368
00:20:41,000 --> 00:20:44,000
GetString, wat geskryf is deur ons, het geen idee hoeveel karakters om te verwag,

369
00:20:44,000 --> 00:20:48,000
so is die feit dat ons stukke van die aangrensende geheue kan toewys is goed.

370
00:20:48,000 --> 00:20:51,000
Skikkings ook 'n probleem wat ons het nou 'n paar weke gelede op te los

371
00:20:51,000 --> 00:20:54,000
waar u die kode begin oorgaan in iets baie swak ontwerp.

372
00:20:54,000 --> 00:20:57,000
Onthou dat ek 'n student struktuur Dawid geroep,

373
00:20:57,000 --> 00:21:00,000
en dan dit was eintlik 'n alternatief, maar,

374
00:21:00,000 --> 00:21:04,000
om met 'n veranderlike genoem naam en 'n ander veranderlike genoem, dink ek, die huis,

375
00:21:04,000 --> 00:21:08,000
en 'n ander veranderlike genaamd ID nie, want in daardie storie wou ek dan iets anders te stel

376
00:21:08,000 --> 00:21:11,000
graag Rob in die program, so toe het ek besluit om te wag 'n minuut,

377
00:21:11,000 --> 00:21:13,000
Ek nodig het om hierdie veranderlikes te hernoem.

378
00:21:13,000 --> 00:21:16,000
Kom ons noem my NAME1, ID1, house1.

379
00:21:16,000 --> 00:21:20,000
Kom ons noem Rob se NAME2, house2, ID2.

380
00:21:20,000 --> 00:21:22,000
Maar dan wag 'n minuut, wat oor Tommy?

381
00:21:22,000 --> 00:21:24,000
Dan het ons nog drie veranderlikes.

382
00:21:24,000 --> 00:21:27,000
Ons lei iemand anders, vier stelle van veranderlikes.

383
00:21:27,000 --> 00:21:30,000
Die wêreld het begin om te kry morsige baie vinnig,

384
00:21:30,000 --> 00:21:33,000
so het ons 'structs, en wat is dwingende oor 'n struct?

385
00:21:33,000 --> 00:21:39,000
Wat beteken 'n C struct laat jy doen?

386
00:21:39,000 --> 00:21:42,000
Dit is regtig 'n ongemaklike vandag.

387
00:21:42,000 --> 00:21:44,000
Wat >> [onhoorbaar student reaksie]?

388
00:21:44,000 --> 00:21:47,000
Ja, spesifiek, typedef kan jy 'n nuwe datatipe te skep,

389
00:21:47,000 --> 00:21:51,000
en struct, die struct navraag, kan jy kapselt

390
00:21:51,000 --> 00:21:54,000
konseptueel verwant stukke van data saam

391
00:21:54,000 --> 00:21:56,000
en daarna hulle noem iets soos 'n student.

392
00:21:56,000 --> 00:21:58,000
>> Dit was goed, want nou kan ons modelleer

393
00:21:58,000 --> 00:22:03,000
baie meer soort van konseptueel konsekwent die idee van 'n student in 'n veranderlike

394
00:22:03,000 --> 00:22:07,000
eerder as om na willekeur met een vir 'n string, een vir 'n ID, en so meer.

395
00:22:07,000 --> 00:22:10,000
Skikkings is mooi omdat hulle toelaat dat ons om te begin die skoonmaak van ons kode.

396
00:22:10,000 --> 00:22:13,000
Maar wat is nou 'n nadeel van 'n skikking?

397
00:22:13,000 --> 00:22:15,000
Wat kan jy doen nie? Ja.

398
00:22:15,000 --> 00:22:17,000
[Studente] Jy moet weet hoe groot dit is.

399
00:22:17,000 --> 00:22:19,000
Jy moet weet hoe groot dit is, so dit is soort van 'n pyn.

400
00:22:19,000 --> 00:22:21,000
Dié van julle met 'n vorige programming ervaring weet dat in baie tale,

401
00:22:21,000 --> 00:22:24,000
soos Java, kan jy vra 'n stuk van die geheue, veral 'n skikking,

402
00:22:24,000 --> 00:22:28,000
hoe groot is u, met 'n lengte, eiendom, om so te praat, en dit is regtig handig.

403
00:22:28,000 --> 00:22:32,000
In C, kan jy nie eens noem strlen op 'n generiese verskeidenheid

404
00:22:32,000 --> 00:22:35,000
omdat strlen, soos die woord impliseer, is slegs vir strykinstrumente,

405
00:22:35,000 --> 00:22:39,000
en jy kan uitvind die lengte van 'n string as gevolg van hierdie menslike konvensie

406
00:22:39,000 --> 00:22:43,000
met 'n \ 0, maar 'n skikking, meer generies, is net 'n stuk van die geheue.

407
00:22:43,000 --> 00:22:46,000
As dit is 'n verskeidenheid van ints, is daar nie tot 'n spesiale karakter

408
00:22:46,000 --> 00:22:48,000
aan die einde wag vir jou.

409
00:22:48,000 --> 00:22:50,000
Jy het om te onthou van die lengte van 'n skikking.

410
00:22:50,000 --> 00:22:54,000
Nog 'n nadeel van 'n skikking sy kop in GetString self.

411
00:22:54,000 --> 00:22:59,000
Wat is nog 'n nadeel van 'n skikking?

412
00:22:59,000 --> 00:23:01,000
Meneer, net ek en jy vandag.

413
00:23:01,000 --> 00:23:04,000
[Onhoorbaar student reaksie] >> Dit is wat?

414
00:23:04,000 --> 00:23:06,000
Dit is op die stapel verklaar.

415
00:23:06,000 --> 00:23:09,000
Goed, op die stapel verklaar. Hoekom het jy nie hou nie?

416
00:23:09,000 --> 00:23:13,000
[Studente], want dit raak weer gebruik.

417
00:23:13,000 --> 00:23:15,000
Dit word weer gebruik.

418
00:23:15,000 --> 00:23:18,000
Okay, as jy gebruik om 'n skikking geheue toeken,

419
00:23:18,000 --> 00:23:21,000
jy kan nie, byvoorbeeld, stuur dit terug, want dit is op die stapel.

420
00:23:21,000 --> 00:23:23,000
Goed, dit is 'n nadeel.

421
00:23:23,000 --> 00:23:25,000
En hoe oor 'n ander met 'n skikking?

422
00:23:25,000 --> 00:23:28,000
Sodra jy dit toeken, jy is soort van geskroef as jy meer ruimte nodig

423
00:23:28,000 --> 00:23:30,000
as dié skikking.

424
00:23:30,000 --> 00:23:34,000
>> Dan het ons ', onthou, malloc, wat aan ons gegee het die vermoë om dinamiese geheue toeken.

425
00:23:34,000 --> 00:23:37,000
Maar wat as ons probeer om 'n ander wêreld altesaam?

426
00:23:37,000 --> 00:23:40,000
Wat gebeur as ons wou 'n paar van die probleme op te los

427
00:23:40,000 --> 00:23:45,000
sodat ons plaas my pen het aan die slaap geraak hier-

428
00:23:45,000 --> 00:23:51,000
Wat gebeur as ons plaas wou in wese 'n wêreld wat nie meer soos hierdie?

429
00:23:51,000 --> 00:23:56,000
Dit is 'n skikking, en, natuurlik, hierdie soort van verswak wanneer ons die einde van die skikking getref het,

430
00:23:56,000 --> 00:24:00,000
en ek nou nie meer ruimte vir 'n ander heelgetal of 'n ander karakter.

431
00:24:00,000 --> 00:24:03,000
Wat gebeur as ons soort van preemptively goed sê, hoekom doen ons nie verslap

432
00:24:03,000 --> 00:24:07,000
hierdie vereiste dat al hierdie stukke van die geheue aangrensende rug aan rug,

433
00:24:07,000 --> 00:24:10,000
en waarom dit nie doen nie, wanneer ek nodig het 'n int of 'n char,

434
00:24:10,000 --> 00:24:12,000
gee my net ruimte vir een van hulle?

435
00:24:12,000 --> 00:24:14,000
En wanneer ek nodig het 'n ander, gee my 'n ander ruimte,

436
00:24:14,000 --> 00:24:16,000
en wanneer ek nodig het 'n ander, gee my 'n ander ruimte.

437
00:24:16,000 --> 00:24:19,000
Die voordeel van wat is nou dat as iemand anders

438
00:24:19,000 --> 00:24:21,000
neem die geheue hier, geen big deal nie.

439
00:24:21,000 --> 00:24:25,000
Ek sal hierdie bykomende stuk van die geheue hier en dan is hierdie een.

440
00:24:25,000 --> 00:24:28,000
>> Nou, die enigste vangs hier is dat dit byna voel soos ek het

441
00:24:28,000 --> 00:24:30,000
'n hele klomp van verskillende veranderlikes.

442
00:24:30,000 --> 00:24:33,000
Dit voel soos vyf verskillende veranderlikes potensieel.

443
00:24:33,000 --> 00:24:36,000
Maar wat as ons 'n idee steel van snare

444
00:24:36,000 --> 00:24:41,000
waardeur ons die een of ander manier verbind hierdie dinge saam konseptueel, en wat as ek dit gedoen het?

445
00:24:41,000 --> 00:24:44,000
Dit is my baie swak getrek pyl.

446
00:24:44,000 --> 00:24:46,000
Maar veronderstel dat elk van hierdie stukke van die geheue

447
00:24:46,000 --> 00:24:52,000
wys na die ander, en hierdie man, wat geen broer of suster tot sy reg,

448
00:24:52,000 --> 00:24:54,000
het nie so 'pyl.

449
00:24:54,000 --> 00:24:56,000
Dit is in die feit wat genoem word 'n geskakelde lys.

450
00:24:56,000 --> 00:25:00,000
Dit is 'n nuwe data struktuur wat ons in staat stel om 'n stuk van die geheue toe te ken,

451
00:25:00,000 --> 00:25:03,000
en dan die ander, en dan die ander, en dan die ander, enige tyd wil ons

452
00:25:03,000 --> 00:25:07,000
tydens 'n program, en ons onthou dat hulle almal op een of ander manier verwante

453
00:25:07,000 --> 00:25:11,000
deur letterlik aaneenskakeling hulle saam, en ons het dit gedoen picturaal hier met 'n pyl.

454
00:25:11,000 --> 00:25:15,000
Maar in die kode, wat sou die meganisme via wat jy kan op een of ander manier verbind,

455
00:25:15,000 --> 00:25:20,000
amper soos Scratch, een stuk na 'n ander stuk?

456
00:25:20,000 --> 00:25:22,000
Ons kan gebruik maak van 'n wyser, reg?

457
00:25:22,000 --> 00:25:25,000
Omdat regtig die pyltjie wat gaan van die boonste linkerkantste blokkie,

458
00:25:25,000 --> 00:25:31,000
hierdie man hier aan hierdie een, kan binne bevat van hierdie vierkant

459
00:25:31,000 --> 00:25:34,000
nie net 'n paar ints, nie net 'n paar char, maar wat as ek eintlik toegeken

460
00:25:34,000 --> 00:25:37,000
'n bietjie ekstra ruimte, sodat nou,

461
00:25:37,000 --> 00:25:41,000
elk van my stukke van die geheue, selfs al is dit gaan my kos,

462
00:25:41,000 --> 00:25:45,000
nou lyk 'n bietjie meer reghoekige waar een van die stukke van die geheue

463
00:25:45,000 --> 00:25:47,000
gebruik word vir 'n aantal, soos die aantal 1,

464
00:25:47,000 --> 00:25:50,000
en dan as hierdie man slaan die nommer 2,

465
00:25:50,000 --> 00:25:52,000
hierdie ander stuk van die geheue wat gebruik word vir 'n pyl,

466
00:25:52,000 --> 00:25:54,000
of meer konkreet, 'n wyser.

467
00:25:54,000 --> 00:25:59,000
En dink ek stoor die getal 3 hier terwyl Ek gebruik dit om te wys dat die man,

468
00:25:59,000 --> 00:26:02,000
en nou is hierdie man, laat ons veronderstel ek wil net drie sulke stukke van die geheue.

469
00:26:02,000 --> 00:26:05,000
Ek sal 'n streep trek deur, wat daarop dui null.

470
00:26:05,000 --> 00:26:07,000
Daar is geen addisionele karakter.

471
00:26:07,000 --> 00:26:10,000
>> Inderdaad, dit is hoe ons kan gaan oor die uitvoering van

472
00:26:10,000 --> 00:26:12,000
iets wat 'n geskakelde lys genoem.

473
00:26:12,000 --> 00:26:18,000
'N geskakelde lys is 'n nuwe data struktuur, en dit is 'n stepping stone in die rigting van

474
00:26:18,000 --> 00:26:21,000
baie liefhebber data strukture wat begin om probleme op te los

475
00:26:21,000 --> 00:26:23,000
langs die lyne van die Facebook-tipe probleme en Google-tipe probleme

476
00:26:23,000 --> 00:26:26,000
waar jy het 'n groot datastelle, en dit nie meer sny dit

477
00:26:26,000 --> 00:26:29,000
om alles te contiguously stoor en gebruik om iets soos lineêre soek

478
00:26:29,000 --> 00:26:31,000
of selfs iets soos die binêre soek.

479
00:26:31,000 --> 00:26:33,000
Jy wil nog beter hardloop tye.

480
00:26:33,000 --> 00:26:37,000
Om die waarheid te sê, een van die Heilige Grails ons praat oor later hierdie week of volgende

481
00:26:37,000 --> 00:26:41,000
is 'n algoritme waarvan die looptyd is konstant.

482
00:26:41,000 --> 00:26:44,000
Met ander woorde, dit neem altyd die dieselfde hoeveelheid van die tyd maak nie saak

483
00:26:44,000 --> 00:26:47,000
hoe groot die inset is, en dit sou inderdaad dwingende,

484
00:26:47,000 --> 00:26:49,000
selfs meer so as iets logaritmiese.

485
00:26:49,000 --> 00:26:51,000
Wat is dit hier op die skerm?

486
00:26:51,000 --> 00:26:55,000
Elkeen van die reghoeke is presies wat ek net met die hand geteken het.

487
00:26:55,000 --> 00:26:59,000
Maar die ding wat al die pad aan die linkerkant is 'n spesiale veranderlike.

488
00:26:59,000 --> 00:27:02,000
Dit gaan om 'n enkele wyser wees nie, want die een Gotcha

489
00:27:02,000 --> 00:27:04,000
met 'n geskakelde lys, as hierdie dinge genoem word,

490
00:27:04,000 --> 00:27:09,000
is wat jy het om op te hang op een einde van die geskakelde lys.

491
00:27:09,000 --> 00:27:13,000
>> Net soos met 'n string, jy moet die adres van die eerste kar om te weet.

492
00:27:13,000 --> 00:27:15,000
Dieselfde deal vir geskakelde lyste.

493
00:27:15,000 --> 00:27:19,000
Jy het die adres van die eerste stuk van die geheue te leer ken

494
00:27:19,000 --> 00:27:25,000
as gevolg van daar af het, kan jy elke ander een.

495
00:27:25,000 --> 00:27:27,000
Nadeel.

496
00:27:27,000 --> 00:27:30,000
Watter prys ons betaal vir hierdie veelsydigheid van 'n dinamiese

497
00:27:30,000 --> 00:27:34,000
aansienlike data struktuur wat as ons ooit meer geheue nodig het, fyn,

498
00:27:34,000 --> 00:27:37,000
ken net nog een stuk en trek 'n verwysing van

499
00:27:37,000 --> 00:27:39,000
die ou na die nuwe stert van die lys?

500
00:27:39,000 --> 00:27:41,000
Ja.

501
00:27:41,000 --> 00:27:43,000
[Studente] Dit neem ongeveer twee keer soveel ruimte.

502
00:27:43,000 --> 00:27:45,000
Dit neem twee keer soveel ruimte, so dit is beslis 'n nadeel, en ons het dit gesien

503
00:27:45,000 --> 00:27:48,000
nadeel voor tussen tyd en ruimte en buigsaamheid

504
00:27:48,000 --> 00:27:51,000
waar deur die nou, ons hoef nie 32 stukkies vir elk van hierdie getalle.

505
00:27:51,000 --> 00:27:57,000
Ons regtig nodig het 64, 32 vir die aantal en 32 vir die wyser.

506
00:27:57,000 --> 00:27:59,000
Maar hey, ek het 'n 2 GB RAM.

507
00:27:59,000 --> 00:28:02,000
Voeg 'n ander 32 stukkies hier en hier lyk nie dat die groot van 'n deal.

508
00:28:02,000 --> 00:28:05,000
Maar vir groot datastelle, dit voeg beslis letterlik twee keer soveel.

509
00:28:05,000 --> 00:28:09,000
Wat is nou 'n ander nadeel, of watter funksie gee ons,

510
00:28:09,000 --> 00:28:12,000
as ons verteenwoordig lyste van dinge met 'n geskakelde lys en nie 'n skikking nie?

511
00:28:12,000 --> 00:28:14,000
[Studente] Jy kan nie deurkruis dit agteruit.

512
00:28:14,000 --> 00:28:16,000
Jy kan nie deurkruis dit agteruit, so jy is soort van geskroef as jy loop

513
00:28:16,000 --> 00:28:19,000
van links na regs met behulp van 'n lus of 'n while lus

514
00:28:19,000 --> 00:28:21,000
en dan moet jy besef, "O, ek wil om terug te gaan na die begin van die lys."

515
00:28:21,000 --> 00:28:26,000
Jy kan nie omdat hierdie wysers net gaan van links na regs as die pyle dui.

516
00:28:26,000 --> 00:28:29,000
>> Nou, kan jy dink aan die begin van die lys met 'n ander veranderlike,

517
00:28:29,000 --> 00:28:31,000
maar dit is 'n kompleksiteit in gedagte te hou.

518
00:28:31,000 --> 00:28:35,000
'N skikking nie saak hoe ver jy gaan, kan jy altyd doen minus, minus, minus, minus

519
00:28:35,000 --> 00:28:37,000
en gaan terug waarvandaan jy gekom het.

520
00:28:37,000 --> 00:28:40,000
Wat is 'n ander nadeel hier? Ja.

521
00:28:40,000 --> 00:28:43,000
[Onhoorbaar student vraag]

522
00:28:43,000 --> 00:28:47,000
Jy kan dit so is, jy het eintlik net 'n datastruktuur bekend as 'n dubbel geskakelde lys voorgestel,

523
00:28:47,000 --> 00:28:50,000
en inderdaad, sou jy nog 'n wyser voeg aan elkeen van hierdie reghoeke

524
00:28:50,000 --> 00:28:53,000
wat die ander rigting gaan, die kop van

525
00:28:53,000 --> 00:28:55,000
is jy nou heen en weer kan deurkruis,

526
00:28:55,000 --> 00:28:59,000
die nadeel wat jy nou gebruik drie keer soveel geheue soos ons gebruik om te

527
00:28:59,000 --> 00:29:04,000
en ook die toevoeging van kompleksiteit in terme van die kode wat jy moet skryf dit reg te kry.

528
00:29:04,000 --> 00:29:08,000
Maar hierdie is almal miskien baie redelike werkinge, as die terugskrywing is meer belangrik.

529
00:29:08,000 --> 00:29:10,000
Ja.

530
00:29:10,000 --> 00:29:12,000
[Studente] Jy kan ook nie 'n 2D-geskakelde lys.

531
00:29:12,000 --> 00:29:16,000
Goed, jy kan nie regtig 'n 2D-geskakelde lys.

532
00:29:16,000 --> 00:29:18,000
Jy kan. Dit is nie naastenby so maklik as 'n skikking.

533
00:29:18,000 --> 00:29:21,000
Soos 'n skikking, jy oop bracket, geslote bracket, oop bracket, gesluit bracket,

534
00:29:21,000 --> 00:29:23,000
en jy kry 'n 2-dimensionele struktuur.

535
00:29:23,000 --> 00:29:26,000
Jy kan 'n 2-dimensionele geskakelde lys te implementeer

536
00:29:26,000 --> 00:29:29,000
as jy dit doen add-as jy 1/3 wyser voorgestel aan elkeen van hierdie dinge,

537
00:29:29,000 --> 00:29:34,000
en as jy dink oor 'n ander lys wat op jou 3D styl

538
00:29:34,000 --> 00:29:40,000
van die skerm vir almal van ons, wat net nog 'n ketting van 'n soort.

539
00:29:40,000 --> 00:29:45,000
Ons kan dit doen, maar dit is nie so eenvoudig soos die tik van oop bracket, vierkante bracket. Ja.

540
00:29:45,000 --> 00:29:48,000
[Onhoorbaar student vraag]

541
00:29:48,000 --> 00:29:50,000
Goed, so dit is 'n ware skopper.

542
00:29:50,000 --> 00:29:54,000
>> Hierdie algoritmes wat ons het, soos oh, binêre soek gaan verby,

543
00:29:54,000 --> 00:29:57,000
jy kan 'n skikking van getalle op die bord soek

544
00:29:57,000 --> 00:30:01,000
of 'n telefoon boek so veel vinniger as jy gebruik te verdeel en oorwin

545
00:30:01,000 --> 00:30:05,000
en 'n binêre soek algoritme, maar binêre soek benodig twee aannames.

546
00:30:05,000 --> 00:30:09,000
Een, dat die data gesorteer.

547
00:30:09,000 --> 00:30:11,000
Nou kan ons waarskynlik hou dit gesorteer,

548
00:30:11,000 --> 00:30:14,000
so miskien is dit is nie 'n probleem nie, maar binêre soek ook aanvaar

549
00:30:14,000 --> 00:30:18,000
wat jy gehad het random access tot die lys van getalle,

550
00:30:18,000 --> 00:30:21,000
en 'n skikking kan jy random access te hê, en deur random access,

551
00:30:21,000 --> 00:30:24,000
Ek bedoel as jy 'n skikking, hoeveel tyd neem dit jou

552
00:30:24,000 --> 00:30:26,000
te kry te bracket 0?

553
00:30:26,000 --> 00:30:29,000
Een operasie, gebruik jy net [0] en jy is reg daar.

554
00:30:29,000 --> 00:30:33,000
Hoeveel treë sal dit neem om te kry om plek 10?

555
00:30:33,000 --> 00:30:36,000
Een stap, jy gaan net na [10] en jy daar is.

556
00:30:36,000 --> 00:30:40,000
In teenstelling hiermee, hoe jy na die 10de heelgetal in 'n geskakelde lys?

557
00:30:40,000 --> 00:30:42,000
Jy het om te begin by die begin, omdat jy net onthou

558
00:30:42,000 --> 00:30:45,000
die begin van 'n geskakelde lys, net soos 'n string word onthou

559
00:30:45,000 --> 00:30:48,000
deur die adres van sy eerste kar, en dat 10th Int te vind

560
00:30:48,000 --> 00:30:53,000
of dat die 10de karakter in 'n string, jy moet die hele damn ding om te soek.

561
00:30:53,000 --> 00:30:55,000
>> Weereens, is ons nie die oplossing van al ons probleme.

562
00:30:55,000 --> 00:31:00,000
Ons is die bekendstelling van nuwe kinders, maar dit hang af van wat jy probeer om te ontwerp vir.

563
00:31:00,000 --> 00:31:04,000
In terme van die uitvoering van hierdie, kan ons 'n idee te leen van daardie student struktuur.

564
00:31:04,000 --> 00:31:07,000
Die sintaksis is baie soortgelyk, behalwe nou die idee is om 'n bietjie meer abstrak

565
00:31:07,000 --> 00:31:09,000
as huis en naam en ID.

566
00:31:09,000 --> 00:31:13,000
Maar ek stel voor dat ons 'n data struktuur in C

567
00:31:13,000 --> 00:31:17,000
wat genoem word node, as die laaste woord op die slide suggereer,

568
00:31:17,000 --> 00:31:21,000
binnekant van 'n nodus, en 'n node is net 'n generiese houer in rekenaarwetenskap.

569
00:31:21,000 --> 00:31:25,000
Dit word gewoonlik voorgestel as 'n sirkel of 'n vierkant of reghoek soos ons gedoen het.

570
00:31:25,000 --> 00:31:27,000
En in hierdie data struktuur, ons het 'n int, n,

571
00:31:27,000 --> 00:31:29,000
so dit is die getal wat ek wil om te stoor.

572
00:31:29,000 --> 00:31:36,000
Maar wat is hierdie tweede lyn, struct node * volgende?

573
00:31:36,000 --> 00:31:40,000
Hoekom is dit korrek is, of watter rol hierdie ding speel,

574
00:31:40,000 --> 00:31:42,000
selfs al is dit 'n bietjie kripties met die eerste oogopslag?

575
00:31:42,000 --> 00:31:44,000
Ja.

576
00:31:44,000 --> 00:31:46,000
[Onhoorbaar student reaksie]

577
00:31:46,000 --> 00:31:50,000
Presies, so die * soort buit dat dit is 'n wyser van een of ander aard.

578
00:31:50,000 --> 00:31:53,000
Die naam van die wyser is arbitrêr volgende,

579
00:31:53,000 --> 00:32:00,000
maar ons kan dit genoem het enigiets wat ons wil hê, maar wat doen dit wyser punt?

580
00:32:00,000 --> 00:32:03,000
[Studente] Nog node >> Presies, dit wys na 'n ander sodanige node.

581
00:32:03,000 --> 00:32:05,000
>> Nou, hierdie is 'n soort van 'n nuuskierigheid van C.

582
00:32:05,000 --> 00:32:09,000
Onthou dat C word gelees deur 'n samesteller van bo na onder, links na regs,

583
00:32:09,000 --> 00:32:13,000
wat beteken dat indien-dit is 'n bietjie anders as wat ons gedoen het met die student.

584
00:32:13,000 --> 00:32:16,000
Wanneer ons 'n student gedefinieer, het ons eintlik nie 'n woord nie.

585
00:32:16,000 --> 00:32:18,000
Dit het net gesê typedef.

586
00:32:18,000 --> 00:32:20,000
Dan het ons int id, string string huis,

587
00:32:20,000 --> 00:32:23,000
en dan student aan die onderkant van die struct.

588
00:32:23,000 --> 00:32:26,000
Hierdie verklaring is 'n bietjie anders, want

589
00:32:26,000 --> 00:32:28,000
weer, die C compiler is 'n bietjie dom.

590
00:32:28,000 --> 00:32:30,000
Dit gaan slegs om van bo na onder te lees,

591
00:32:30,000 --> 00:32:33,000
so as dit bereik die 2de lyn hier

592
00:32:33,000 --> 00:32:37,000
waar die volgende verklaar word en dit sien, oh, hier is 'n veranderlike genaamd volgende.

593
00:32:37,000 --> 00:32:39,000
Dit is 'n wyser na 'n struct node.

594
00:32:39,000 --> 00:32:42,000
Die opsteller gaan om te besef wat is 'n struct node?

595
00:32:42,000 --> 00:32:44,000
Ek het nog nooit gehoor het van hierdie ding voor,

596
00:32:44,000 --> 00:32:47,000
omdat die woord node anders kan verskyn nie

597
00:32:47,000 --> 00:32:49,000
tot op die bodem, so daar is hierdie oortolligheid.

598
00:32:49,000 --> 00:32:53,000
Jy het struct node om hier te sê, wat kan jy dan later verkort

599
00:32:53,000 --> 00:32:56,000
te danke aan typedef af hier, maar dit is omdat

600
00:32:56,000 --> 00:33:02,000
ons verwysing na die struktuur self binnekant van die struktuur.

601
00:33:02,000 --> 00:33:05,000
Dis die een Gotcha daar.

602
00:33:05,000 --> 00:33:07,000
>> 'N paar interessante probleme gaan ontstaan.

603
00:33:07,000 --> 00:33:09,000
Ons het 'n lys van getalle. Hoe voeg ons in dit?

604
00:33:09,000 --> 00:33:11,000
Hoe soek ons ​​dit? Hoe verwyder ons van dit?

605
00:33:11,000 --> 00:33:13,000
Veral nou dat ons al hierdie wenke te bestuur.

606
00:33:13,000 --> 00:33:15,000
Jy het gedink wysers was soort van mind-buiging

607
00:33:15,000 --> 00:33:17,000
as jy het een van hulle net probeer om 'n int om dit te lees.

608
00:33:17,000 --> 00:33:20,000
Nou het ons 'n volledige lys is die moeite werd te manipuleer.

609
00:33:20,000 --> 00:33:22,000
Waarom neem ons nie ons 5-minute breek hier, en dan sal ons bring

610
00:33:22,000 --> 00:33:34,000
sommige mense op die verhoog te doen presies dit.

611
00:33:34,000 --> 00:33:36,000
>> C is baie meer pret as dit opgetree het.

612
00:33:36,000 --> 00:33:39,000
Wie sou letterlik wil eerste wees?

613
00:33:39,000 --> 00:33:41,000
Okay, kom op. Jy is die eerste.

614
00:33:41,000 --> 00:33:44,000
Wie sou wil wees 9? Okay, 9.

615
00:33:44,000 --> 00:33:46,000
Hoe oor 9? 17?

616
00:33:46,000 --> 00:33:51,000
'N bietjie kliek hier. 22 en 26 in die voorry.

617
00:33:51,000 --> 00:33:53,000
En dan hoe oor iemand daar gewys.

618
00:33:53,000 --> 00:33:57,000
Jy is 34. Okay, 34, kom op maksimum.

619
00:33:57,000 --> 00:33:59,000
Eerste is daar. Okay, al vier van julle ouens.

620
00:33:59,000 --> 00:34:01,000
En wie het ons sê vir 9?

621
00:34:01,000 --> 00:34:04,000
Wie is ons 9?

622
00:34:04,000 --> 00:34:07,000
Wie wil regtig te wees 9? Alle reg, kom op, wees 9.

623
00:34:07,000 --> 00:34:10,000
Hier gaan ons.

624
00:34:10,000 --> 00:34:13,000
34, sal ons julle ontmoet daar.

625
00:34:13,000 --> 00:34:17,000
Die eerste deel is julle lyk soos wat.

626
00:34:17,000 --> 00:34:21,000
26, 22, 17, 'n goeie.

627
00:34:21,000 --> 00:34:25,000
As jy kan staan ​​uit na die kant, want ons gaan om jou te malloc in 'n oomblik.

628
00:34:25,000 --> 00:34:29,000
>> Goed, goed.

629
00:34:29,000 --> 00:34:32,000
Okay, uitstekend, so ons vra 'n paar vrae hier.

630
00:34:32,000 --> 00:34:34,000
En eintlik, wat is jou naam? >> Anita.

631
00:34:34,000 --> 00:34:37,000
Anita, okay, hier oor kom.

632
00:34:37,000 --> 00:34:41,000
Anita gaan om ons te help soort van los een van redelik eenvoudige vraag in die eerste,

633
00:34:41,000 --> 00:34:44,000
wat is hoe kry jy of 'n waarde is in die lys?

634
00:34:44,000 --> 00:34:48,000
Nou, let op dat die eerste, hier verteenwoordig deur Lucas,

635
00:34:48,000 --> 00:34:52,000
is 'n bietjie anders, en so sy stuk papier is doelbewus sywaarts

636
00:34:52,000 --> 00:34:55,000
want dit is nie heeltemal so hoog en neem nie soveel stukkies,

637
00:34:55,000 --> 00:34:58,000
alhoewel tegnies hy het dieselfde grootte papier gedraai.

638
00:34:58,000 --> 00:35:01,000
Maar hy is 'n bietjie anders in die sin dat hy slegs 32 stukkies vir 'n wyser,

639
00:35:01,000 --> 00:35:05,000
en al hierdie ouens is 64 stukkies, waarvan die helfte van die getal, waarvan die helfte is 'n wyser.

640
00:35:05,000 --> 00:35:08,000
Maar die wyser nie uitgebeeld word nie, so as julle ouens kan 'n bietjie ongemaklik

641
00:35:08,000 --> 00:35:12,000
Gebruik jou linkerhand om te wys op die persoon langs jou.

642
00:35:12,000 --> 00:35:14,000
En jy is nommer 34. Wat is jou naam?

643
00:35:14,000 --> 00:35:16,000
Ari.

644
00:35:16,000 --> 00:35:19,000
Ari, so werklik, in besit wees van die papier in jou regterhand, en linkerhand gaan reguit af.

645
00:35:19,000 --> 00:35:21,000
Jy verteenwoordig null aan die linkerkant.

646
00:35:21,000 --> 00:35:24,000
>> Nou is ons menslike beeld is baie konsekwent.

647
00:35:24,000 --> 00:35:26,000
Dit is eintlik hoe wysers werk.

648
00:35:26,000 --> 00:35:29,000
En as jy kan 'n bietjie opfrommel hierdie manier, so ek is nie in jou pad.

649
00:35:29,000 --> 00:35:34,000
Anita hier, vind ek die getal 22,

650
00:35:34,000 --> 00:35:40,000
maar neem 'n beperking van mense hou stukkies papier,

651
00:35:40,000 --> 00:35:43,000
maar dit is 'n lys, en jy het net Lucas om te begin met

652
00:35:43,000 --> 00:35:46,000
want hy is letterlik die eerste wyser.

653
00:35:46,000 --> 00:35:51,000
Veronderstel jy self is 'n wyser, en so moet jy ook die vermoë om te wys op iets.

654
00:35:51,000 --> 00:35:56,000
Hoekom het jy nie begin deur te wys presies wat Lucas wys?

655
00:35:56,000 --> 00:35:58,000
Goeie, en laat my verorden dit uit hier.

656
00:35:58,000 --> 00:36:04,000
Net ter wille van die bespreking, laat my toe om 'n leë bladsy.

657
00:36:04,000 --> 00:36:06,000
Hoe spel jy jou naam? >> Anita.

658
00:36:06,000 --> 00:36:08,000
Okay, Anita.

659
00:36:08,000 --> 00:36:18,000
Kom ons sê node * anita = lucas.

660
00:36:18,000 --> 00:36:22,000
Wel, moet ons nie noem julle lucas. Ons moet noem jy die eerste keer.

661
00:36:22,000 --> 00:36:25,000
Hoekom is dit in werklikheid in ooreenstemming met die werklikheid hier?

662
00:36:25,000 --> 00:36:27,000
Een, in die eerste bestaan ​​reeds.

663
00:36:27,000 --> 00:36:30,000
Eerste is vermoedelik iewers toegeken hier.

664
00:36:30,000 --> 00:36:35,000
Node * Eerste, en dit toegeken is 'n lys op een of ander manier.

665
00:36:35,000 --> 00:36:37,000
Ek weet nie hoe dit gebeur het. Wat gebeur het voor die klas begin.

666
00:36:37,000 --> 00:36:40,000
Hierdie geskakelde lys van die mens geskep is.

667
00:36:40,000 --> 00:36:44,000
En nou, op hierdie punt in die storie - dit is al op Facebook gaan blykbaar later

668
00:36:44,000 --> 00:36:49,000
op hierdie punt in die verhaal, het Anita geïnisialiseer om gelyk te wees na die eerste,

669
00:36:49,000 --> 00:36:51,000
Dit beteken nie dat Anita punte by Lucas.

670
00:36:51,000 --> 00:36:53,000
Inteendeel, sy wys wat hy wys na

671
00:36:53,000 --> 00:36:57,000
omdat die dieselfde adres en onder dieselfde naam wat is binnekant van Lucas se 32 stukkies - 1, 2, 3

672
00:36:57,000 --> 00:37:01,000
is nou ook binnekant van Anita se 32 stukkies - 1, 2, 3.

673
00:37:01,000 --> 00:37:05,000
>> Vind nou 22. Hoe sou jy te werk gaan om dit te doen?

674
00:37:05,000 --> 00:37:07,000
Wat is dit? >> Point wat ookal.

675
00:37:07,000 --> 00:37:11,000
Verwys na wat ookal, so gaan voort en tree dit uit as beste wat jy kan hier.

676
00:37:11,000 --> 00:37:15,000
Goed, goed, en nou is jy wys op wat is jou naam met 22?

677
00:37:15,000 --> 00:37:18,000
Ramon. >> Ramon, so Ramon hou 22.

678
00:37:18,000 --> 00:37:20,000
Jy het nou 'n tjek gedoen.

679
00:37:20,000 --> 00:37:24,000
Is Ramon == 22, en indien wel, byvoorbeeld, kan ons terugkeer waar.

680
00:37:24,000 --> 00:37:26,000
Laat my terwyl hierdie ouens hier staan ​​ietwat ongemaklik

681
00:37:26,000 --> 00:37:32,000
laat my iets te doen vinnig soos Bool vind.

682
00:37:32,000 --> 00:37:37,000
Ek gaan om voort te gaan en sê (node ​​* lys, int n).

683
00:37:37,000 --> 00:37:39,000
Ek kom gou terug wees met julle ouens. Ek het net 'n kode te skryf.

684
00:37:39,000 --> 00:37:45,000
En nou is ek gaan om voort te gaan en doen, node * anita = lys.

685
00:37:45,000 --> 00:37:51,000
En ek gaan om voort te gaan en sê, terwyl (Anita = null).

686
00:37:51,000 --> 00:37:57,000
>> Die metafoor hier is 'n bietjie gerek, maar terwyl (anita = NULL!), Wat ek wil om dit te doen?

687
00:37:57,000 --> 00:38:03,000
Ek moet een of ander manier van verwysing

688
00:38:03,000 --> 00:38:05,000
die heelgetal dat Anita wys.

689
00:38:05,000 --> 00:38:08,000
In die verlede, toe ons strukture, wat 'n node is,

690
00:38:08,000 --> 00:38:11,000
ons gebruik die dot-notasie, en ons wil iets sê

691
00:38:11,000 --> 00:38:15,000
anita.n, maar die probleem hier is dat Anita nie 'n struct per se.

692
00:38:15,000 --> 00:38:17,000
Wat is sy?

693
00:38:17,000 --> 00:38:21,000
Sy is 'n wyser, so regtig, as ons wil dit dot te gebruik notasie-

694
00:38:21,000 --> 00:38:23,000
en dit gaan om doelbewus 'n bietjie kripties te kyk

695
00:38:23,000 --> 00:38:28,000
ons het iets te doen gaan net die Anita se linkerhand wys

696
00:38:28,000 --> 00:38:31,000
en dan kry die veld genaamd n.

697
00:38:31,000 --> 00:38:35,000
Anita is 'n wyser, maar wat is * anita?

698
00:38:35,000 --> 00:38:38,000
Wat kry jy wanneer jy na wat Anita wys?

699
00:38:38,000 --> 00:38:42,000
'N struct, 'n node en 'n knoop, onthou, het 'n veld met die naam van n

700
00:38:42,000 --> 00:38:47,000
want dit het, onthou, hierdie 2 velde, langs en n,

701
00:38:47,000 --> 00:38:50,000
wat ons gesien het 'n oomblik gelede hier.

702
00:38:50,000 --> 00:38:53,000
>> Om werklik te boots in die kode,

703
00:38:53,000 --> 00:39:02,000
ons kan dit doen en sê as ((* anita) n == n), die n wat ek soek.

704
00:39:02,000 --> 00:39:04,000
Let daarop dat die funksie in die aantal wat ek omgee geslaag.

705
00:39:04,000 --> 00:39:10,000
Dan kan ek gaan voort en doen iets soos return true.

706
00:39:10,000 --> 00:39:12,000
Anders, as dit nie die geval is, nie wat ek wil om dit te doen?

707
00:39:12,000 --> 00:39:19,000
Hoe vertaal ek om te kodeer wat Anita het so intuïtief deur die loop deur die lys?

708
00:39:19,000 --> 00:39:26,000
Wat moet ek doen om hier te simuleer Anita neem dat die stap aan die linkerkant, dat die stap aan die linkerkant?

709
00:39:26,000 --> 00:39:28,000
[Onhoorbaar student reaksie] >> Wat is dit?

710
00:39:28,000 --> 00:39:30,000
[Onhoorbaar student reaksie]

711
00:39:30,000 --> 00:39:34,000
Goed, nie 'n slegte idee nie, maar in die verlede, toe ons dit gedoen het, het ons gedoen anita + +

712
00:39:34,000 --> 00:39:37,000
want dit sou die getal 1 byvoeg Anita

713
00:39:37,000 --> 00:39:40,000
wat sou tipies wys op die volgende persoon, soos Ramon,

714
00:39:40,000 --> 00:39:44,000
of die persoon langs hom, of die naaste aan hom persoon af die lyn.

715
00:39:44,000 --> 00:39:49,000
Maar dit is nie baie goed hier, want wat het hierdie ding lyk soos in die geheue?

716
00:39:49,000 --> 00:39:54,000
Nie dat. Ons het om te skakel.

717
00:39:54,000 --> 00:40:00,000
Dit lyk soos dit in die geheue, en selfs al het ek 1 en 2 en 3 naby aan mekaar getrek het,

718
00:40:00,000 --> 00:40:03,000
As ons regtig simuleer hierdie kan jy ouens, terwyl hy nog wys op die dieselfde mense,

719
00:40:03,000 --> 00:40:07,000
kan sommige van julle 'n ewekansige stap terug, sommige van julle 'n ewekansige stap vorentoe?

720
00:40:07,000 --> 00:40:10,000
>> Hierdie gemors is nog steeds 'n geskakelde lys,

721
00:40:10,000 --> 00:40:13,000
maar hierdie ouens kan enige plek in die geheue,

722
00:40:13,000 --> 00:40:15,000
so anita + + is nie van plan om te werk waarom?

723
00:40:15,000 --> 00:40:19,000
Wat is op plek anita + +?

724
00:40:19,000 --> 00:40:21,000
Wie weet.

725
00:40:21,000 --> 00:40:24,000
Dit is 'n paar ander waarde wat net so gebeur word interposed

726
00:40:24,000 --> 00:40:28,000
onder al van hierdie nodes deur die kans, omdat ons nie met behulp van 'n skikking.

727
00:40:28,000 --> 00:40:30,000
Ons toegeken elk van hierdie nodes individueel.

728
00:40:30,000 --> 00:40:32,000
Okay, as jy ouens kan julle skoon back-up.

729
00:40:32,000 --> 00:40:37,000
Laat my voor dat in plaas van anita + +, ons doen in plaas anita kry

730
00:40:37,000 --> 00:40:42,000
goed, hoekom ons nie gaan na watter Anita wys en dan doen. volgende?

731
00:40:42,000 --> 00:40:45,000
Met ander woorde, ons gaan na Ramon, wat hou van die getal 22,

732
00:40:45,000 --> 00:40:51,000
en dan volgende is asof Anita sou die kopiëring van sy linker hand wyser.

733
00:40:51,000 --> 00:40:54,000
Maar sy wou nie verder gaan as Ramon omdat ons gevind 22.

734
00:40:54,000 --> 00:40:56,000
Maar dit sou die idee wees. Nou, hierdie is 'n god aaklige gemors.

735
00:40:56,000 --> 00:40:59,000
Honestly, niemand sal ooit onthou hierdie sintaksis, en so gelukkig,

736
00:40:59,000 --> 00:41:04,000
dit is eintlik 'n bietjie doelbewuste-oh, het jy nie eintlik sien wat ek geskryf het.

737
00:41:04,000 --> 00:41:08,000
Dit sou meer oortuigend as wat jy kan. Voila!

738
00:41:08,000 --> 00:41:10,000
>> Agter die skerms, het ek die oplossing van die probleem op hierdie manier.

739
00:41:10,000 --> 00:41:14,000
Anita, om daardie stap te neem aan die linkerkant,

740
00:41:14,000 --> 00:41:18,000
eerste, ons gaan na die adres wat Anita wys

741
00:41:18,000 --> 00:41:23,000
en waar sy sal vind nie net n, wat ons net nagegaan word vir vergelyking se onthalwe,

742
00:41:23,000 --> 00:41:25,000
maar jy sal ook die volgende - in hierdie geval,

743
00:41:25,000 --> 00:41:28,000
Ramon se linkerhand verwys na die volgende nodus in die lys.

744
00:41:28,000 --> 00:41:32,000
Maar dit is die god-verskriklik gemors waarna ek vroeër verwys,

745
00:41:32,000 --> 00:41:34,000
maar dit blyk C laat ons vereenvoudig hierdie.

746
00:41:34,000 --> 00:41:40,000
In plaas van die skryf (* anita), kan ons plaas net skryf anita-> n,

747
00:41:40,000 --> 00:41:45,000
en dit is presies dieselfde ding funksioneel nie, maar dit is 'n baie meer intuïtief,

748
00:41:45,000 --> 00:41:48,000
en dit is 'n baie meer in ooreenstemming met die beeld wat ons het is teken

749
00:41:48,000 --> 00:41:50,000
al hierdie tyd met behulp van pyle.

750
00:41:50,000 --> 00:41:57,000
>> Ten slotte, doen wat ons moet doen is om aan die einde van hierdie program?

751
00:41:57,000 --> 00:42:00,000
Daar is een lyn van kode oorblywende.

752
00:42:00,000 --> 00:42:02,000
Teruggee wat?

753
00:42:02,000 --> 00:42:05,000
Vals is, want as ons deur die hele while lus

754
00:42:05,000 --> 00:42:10,000
en Anita is, in werklikheid, null, wat beteken sy het al die pad na die einde van die lys

755
00:42:10,000 --> 00:42:12,000
waar sy wys wat is jou naam nou weer?

756
00:42:12,000 --> 00:42:15,000
Ari >> Ari se linkerhand, wat null.

757
00:42:15,000 --> 00:42:18,000
Anita is nou null, en ek besef jy net hier staan ​​ongemaklik in limbo

758
00:42:18,000 --> 00:42:21,000
want ek gaan op 'n monoloog hier,

759
00:42:21,000 --> 00:42:23,000
maar ons sal behels dat jy weer in net 'n oomblik.

760
00:42:23,000 --> 00:42:27,000
Anita, is van nul by daardie punt in die verhaal, so die while lus beëindig,

761
00:42:27,000 --> 00:42:30,000
en ons het om terug te keer vals want as sy het al die pad na Ari se null pointer

762
00:42:30,000 --> 00:42:34,000
dan was daar geen nommer wat sy in die lys gesoek.

763
00:42:34,000 --> 00:42:39,000
Ons kan skoon up, maar dit is 'n redelik goeie implementering

764
00:42:39,000 --> 00:42:43,000
van 'n traversal funksie, 'n funksie vir 'n geskakelde lys.

765
00:42:43,000 --> 00:42:48,000
Dit is nog steeds lineêre soek, maar dit is nie so eenvoudig as + + 'n wyser

766
00:42:48,000 --> 00:42:52,000
of + + 'n i-veranderlike want nou kan ons nie raai

767
00:42:52,000 --> 00:42:54,000
waar elk van hierdie nodes in die geheue is.

768
00:42:54,000 --> 00:42:57,000
Ons het letterlik volg die spoor van broodkrummels of, meer spesifiek,

769
00:42:57,000 --> 00:43:00,000
pointers te kry van een node na 'n ander.

770
00:43:00,000 --> 00:43:02,000
>> Nou, laat ons probeer om 'n ander een. Anita, wil jy om terug te kom hier?

771
00:43:02,000 --> 00:43:06,000
Waarom ons nie voort te gaan en die toekenning van 'n ander persoon uit die gehoor?

772
00:43:06,000 --> 00:43:08,000
Malloc-wat is jou naam? >> Rebecca.

773
00:43:08,000 --> 00:43:10,000
Rebecca. Rebecca is malloced uit die gehoor,

774
00:43:10,000 --> 00:43:13,000
en sy is nou die stoor van die getal 55.

775
00:43:13,000 --> 00:43:17,000
En die doel by die hand is nou vir Anita te voeg

776
00:43:17,000 --> 00:43:22,000
Rebecca in die geskakelde lys hier in die toepaslike plek.

777
00:43:22,000 --> 00:43:24,000
Kom oor hier vir 'n oomblik.

778
00:43:24,000 --> 00:43:28,000
Ek gedoen het iets soos hierdie.

779
00:43:28,000 --> 00:43:32,000
Ek gedoen het node *. En wat is jou naam nou weer?

780
00:43:32,000 --> 00:43:34,000
Rebecca. >> Rebecca, okay.

781
00:43:34,000 --> 00:43:41,000
Rebecca kry malloc (sizeof (node)).

782
00:43:41,000 --> 00:43:44,000
Net soos ons in die verlede toegeken dinge soos studente en noem maar op,

783
00:43:44,000 --> 00:43:46,000
moet ons die grootte van die node, so nou is Rebekka

784
00:43:46,000 --> 00:43:49,000
wys op wat?

785
00:43:49,000 --> 00:43:52,000
Rebecca het twee velde binnekant van haar, waarvan een is 55.

786
00:43:52,000 --> 00:43:55,000
Kom ons doen wat, Rebecca-> = 55.

787
00:43:55,000 --> 00:44:00,000
Maar dan rebecca-> Volgende moet nou wees soos, haar hand is 'n soort van wie weet?

788
00:44:00,000 --> 00:44:03,000
Dit wys op 'n sekere vullis waarde, so hoekom doen jy nie vir 'n goeie maatreël

789
00:44:03,000 --> 00:44:07,000
ons ten minste doen dit sodat linkerhand is nou aan haar kant.

790
00:44:07,000 --> 00:44:09,000
Nou Anita, neem dit van hier af.

791
00:44:09,000 --> 00:44:11,000
Jy het Rebecca toegeken is.

792
00:44:11,000 --> 00:44:20,000
Gaan voort en vind waar ons moet sit Rebecca.

793
00:44:20,000 --> 00:44:25,000
Goed, baie goed.

794
00:44:25,000 --> 00:44:28,000
Goed, goed, en nou is ons het jou nodig om 'n bietjie van rigting te verskaf,

795
00:44:28,000 --> 00:44:30,000
sodat jy bereik het Ari.

796
00:44:30,000 --> 00:44:33,000
Sy linkerhand is, is van nul, maar Rebecca behoort duidelik aan die regterkant,

797
00:44:33,000 --> 00:44:36,000
so hoe het ons hierdie geskakelde lys te verander

798
00:44:36,000 --> 00:44:38,000
ten einde Rebecca in die toepaslike plek in te voeg?

799
00:44:38,000 --> 00:44:42,000
As jy kan letterlik mense se linkerhand beweeg om as dit nodig is,

800
00:44:42,000 --> 00:44:48,000
ons sal die probleem op daardie manier op te los.

801
00:44:48,000 --> 00:44:52,000
Goed, goed, en intussen, Rebecca se linkerhand is nou deur haar kant.

802
00:44:52,000 --> 00:44:54,000
>> Dit was te maklik.

803
00:44:54,000 --> 00:44:57,000
Kom ons probeer om die toekenning-we're byna gedoen het, 20.

804
00:44:57,000 --> 00:44:59,000
Okay, kom op.

805
00:44:59,000 --> 00:45:04,000
20 toegeken is, so laat my gaan voort en sê weer hier

806
00:45:04,000 --> 00:45:07,000
ons het net gedoen node * saad.

807
00:45:07,000 --> 00:45:11,000
Ons het malloc (sizeof (node)).

808
00:45:11,000 --> 00:45:16,000
Ons doen dan presies dieselfde sintaks soos ons gedoen het voor vir 20,

809
00:45:16,000 --> 00:45:20,000
en ek sal langs = NULL doen, en nou is dit tot Anita

810
00:45:20,000 --> 00:45:23,000
jy in die geskakelde lys te voeg, as jy kan dat presies dieselfde rol speel.

811
00:45:23,000 --> 00:45:30,000
Uit te voer.

812
00:45:30,000 --> 00:45:32,000
Goed.

813
00:45:32,000 --> 00:45:38,000
Nou dink goed na voordat jy begin beweeg links hande om.

814
00:45:38,000 --> 00:45:46,000
Jy verreweg vandag het die mees ongemaklike rol.

815
00:45:46,000 --> 00:45:59,000
Wie se hand moet eerste verskuif?

816
00:45:59,000 --> 00:46:02,000
Okay, wag, ek 'n paar nee se ek hoor.

817
00:46:02,000 --> 00:46:07,000
As sommige mense sou beleefd om te help om 'n ongemaklike situasie op te los hier.

818
00:46:07,000 --> 00:46:11,000
Wie se linkerhand moet eers miskien bygewerk? Ja.

819
00:46:11,000 --> 00:46:13,000
[Studente] Saad.

820
00:46:13,000 --> 00:46:15,000
Okay, Saad, waarom, al is?

821
00:46:15,000 --> 00:46:17,000
[Onhoorbaar student reaksie]

822
00:46:17,000 --> 00:46:19,000
Goed so, want as ons beweeg-wat is jou naam? >> Marshall.

823
00:46:19,000 --> 00:46:22,000
Marshall, as ons beweeg sy hand af na nul,

824
00:46:22,000 --> 00:46:25,000
nou het ons letterlik wees gelaat is vier mense in hierdie lys

825
00:46:25,000 --> 00:46:29,000
want hy was die enigste ding wat wys op Ramon en almal aan die linkerkant,

826
00:46:29,000 --> 00:46:31,000
so afhangende van wat wyser was sleg.

827
00:46:31,000 --> 00:46:33,000
Kom ons maak ongedaan dat.

828
00:46:33,000 --> 00:46:37,000
Goed, en nou gaan voort en beweeg die toepaslike linkerhand wys op Ramon.

829
00:46:37,000 --> 00:46:39,000
Dit voel 'n bietjie oorbodig.

830
00:46:39,000 --> 00:46:41,000
Nou is daar twee mense wys op Ramon, maar dit is goed

831
00:46:41,000 --> 00:46:43,000
want nou hoe anders werk ons ​​die lys?

832
00:46:43,000 --> 00:46:48,000
Watter ander hand om te beweeg?

833
00:46:48,000 --> 00:46:53,000
Uitstekend, het ons nou 'n geheue verloor?

834
00:46:53,000 --> 00:46:57,000
Nee, so goed is, laat ons kyk of ons kan dit nie weer breek.

835
00:46:57,000 --> 00:47:00,000
>> Mallocing een laaste keer, nommer 5.

836
00:47:00,000 --> 00:47:04,000
Al die pad terug, op neer kom.

837
00:47:04,000 --> 00:47:08,000
Dit is baie opwindend.

838
00:47:08,000 --> 00:47:15,000
[Applous]

839
00:47:15,000 --> 00:47:17,000
Wat is jou naam? >> Ron.

840
00:47:17,000 --> 00:47:19,000
Ron, okay, jy malloced as nommer 5.

841
00:47:19,000 --> 00:47:23,000
Ons het net uitgevoer kode wat byna identies is aan hierdie

842
00:47:23,000 --> 00:47:26,000
met net 'n ander naam.

843
00:47:26,000 --> 00:47:28,000
Uitstekend.

844
00:47:28,000 --> 00:47:38,000
Nou, Anita, baie geluk invoeging nommer 5 in die lys nou.

845
00:47:38,000 --> 00:47:43,000
Goed is, en?

846
00:47:43,000 --> 00:47:47,000
Uitstekend, so dit is regtig die derde van drie in totaal gevalle.

847
00:47:47,000 --> 00:47:49,000
Ons moes eers iemand aan die einde, Rebecca.

848
00:47:49,000 --> 00:47:51,000
Ons het toe iemand in die middel.

849
00:47:51,000 --> 00:47:53,000
Nou het ons iemand aan die begin, en in hierdie voorbeeld,

850
00:47:53,000 --> 00:47:56,000
ons het nou om Lucas te werk vir die eerste keer

851
00:47:56,000 --> 00:48:00,000
want die eerste element in die lys het nou te wys op 'n nuwe node,

852
00:48:00,000 --> 00:48:03,000
wat op sy beurt, wys by node nommer 9.

853
00:48:03,000 --> 00:48:06,000
>> Dit was 'n uiters ongemaklike demonstrasie, ek is seker,

854
00:48:06,000 --> 00:48:08,000
so 'n groot applous vir hierdie ouens as jy kon.

855
00:48:08,000 --> 00:48:11,000
Mooi gedoen.

856
00:48:11,000 --> 00:48:17,000
Dis al. Jy behou jou stukkies papier as 'n bietjie geheue.

857
00:48:17,000 --> 00:48:22,000
Dit blyk dat om dit te doen in die kode

858
00:48:22,000 --> 00:48:26,000
is nie heeltemal so eenvoudig as net bewegende hande om

859
00:48:26,000 --> 00:48:28,000
en wys wysers op verskillende dinge.

860
00:48:28,000 --> 00:48:31,000
Maar besef dat wanneer dit tyd om iets soos te implementeer

861
00:48:31,000 --> 00:48:34,000
'n geskakelde lys of 'n variant van dit as jy fokus op baie

862
00:48:34,000 --> 00:48:38,000
hierdie basiese beginsels, die byt-grootte probleme wat ek het om uit te vind,

863
00:48:38,000 --> 00:48:43,000
is dit hand of hierdie hand, besef dat wat andersins 'n redelik komplekse program

864
00:48:43,000 --> 00:48:47,000
kan, in werklikheid, verminder word tot redelik eenvoudige boustene soos hierdie.

865
00:48:47,000 --> 00:48:51,000
>> Kom ons neem dinge in 'n meer gesofistikeerde rigting.

866
00:48:51,000 --> 00:48:53,000
Ons het nou die idee van die geskakelde lys.

867
00:48:53,000 --> 00:48:57,000
Ons het ook te danke aan die voorstel daar agter 'n dubbel geskakelde lys,

868
00:48:57,000 --> 00:49:01,000
wat lyk amper dieselfde, maar nou moet ons twee wysers binnekant van die struct

869
00:49:01,000 --> 00:49:05,000
in plaas van een, en ons kan waarskynlik noem dié wenke vorige en die volgende

870
00:49:05,000 --> 00:49:08,000
of links of regs, maar ons doen, in werklikheid, moet twee van hulle.

871
00:49:08,000 --> 00:49:10,000
Die kode sal 'n bietjie meer betrokke.

872
00:49:10,000 --> 00:49:12,000
Anita sou gehad het om meer werk om hier te doen op die verhoog.

873
00:49:12,000 --> 00:49:15,000
Maar ons kan seker daardie soort struktuur te implementeer.

874
00:49:15,000 --> 00:49:19,000
In terme van die bestuur van tyd, al is, wat sou die loop van die tyd

875
00:49:19,000 --> 00:49:24,000
vir Anita van die vind van 'n aantal n in 'n geskakelde lys nou?

876
00:49:24,000 --> 00:49:27,000
Nog steeds groot O van n, so dit is nie beter as lineêre soek.

877
00:49:27,000 --> 00:49:29,000
Ons kan dit nie doen om die binêre soek, al is, weer.

878
00:49:29,000 --> 00:49:34,000
Hoekom is dit die geval? Jy kan nie rond spring.

879
00:49:34,000 --> 00:49:36,000
Selfs al het ons natuurlik al die mense op die verhoog sien,

880
00:49:36,000 --> 00:49:39,000
en Anita kon eyeballed dit en sê: "Hier is die middel van die lys,"

881
00:49:39,000 --> 00:49:42,000
sy sou nie weet dat as sy was die program op die rekenaar

882
00:49:42,000 --> 00:49:47,000
omdat die enigste ding wat sy gehad het om te grendel op aan die begin van die scenario

883
00:49:47,000 --> 00:49:50,000
was Lucas, wat was die eerste wyser.

884
00:49:50,000 --> 00:49:53,000
Sy sou noodwendig die skakels te volg,

885
00:49:53,000 --> 00:49:56,000
tel haar totdat sy gevind dat ongeveer die middel,

886
00:49:56,000 --> 00:49:58,000
en selfs dan is sy nie van plan om te weet wanneer sy die middel bereik

887
00:49:58,000 --> 00:50:01,000
tensy sy gaan al die pad tot die einde toe om uit te vind hoeveel daar is,

888
00:50:01,000 --> 00:50:05,000
dan backtracks en ook dit sou moeilik wees, tensy jy gehad het

889
00:50:05,000 --> 00:50:07,000
'n dubbel gekoppel lys van een of ander aard.

890
00:50:07,000 --> 00:50:10,000
>> Oplos van enkele probleme vandag, maar die bekendstelling van ander.

891
00:50:10,000 --> 00:50:12,000
Wat oor 'n ander datastruktuur altesaam?

892
00:50:12,000 --> 00:50:15,000
Dit is 'n foto van die bak in Mather House,

893
00:50:15,000 --> 00:50:19,000
en in hierdie geval het ons 'n datastruktuur ons soort het ook reeds praat.

894
00:50:19,000 --> 00:50:22,000
Ons het gepraat oor 'n stapel in die konteks van die geheue,

895
00:50:22,000 --> 00:50:26,000
en dit is doelbewus soort genoem omdat 'n stapel in die bepalings van die geheue

896
00:50:26,000 --> 00:50:31,000
is effektief 'n datastruktuur wat meer en meer dinge lae bo-op dit.

897
00:50:31,000 --> 00:50:35,000
Maar die interessante ding oor 'n stapel, soos die geval is in werklikheid,

898
00:50:35,000 --> 00:50:38,000
is dat dit 'n spesiale soort data struktuur.

899
00:50:38,000 --> 00:50:42,000
Dit is 'n datastruktuur waardeur die eerste element in

900
00:50:42,000 --> 00:50:46,000
is die laaste element.

901
00:50:46,000 --> 00:50:50,000
As jy die eerste skinkbord geplaas word op die stapel,

902
00:50:50,000 --> 00:50:53,000
jy gaan ongelukkig die laaste skinkbord geneem moet word van die stapel af,

903
00:50:53,000 --> 00:50:55,000
en dit is nie noodwendig 'n goeie ding nie.

904
00:50:55,000 --> 00:50:58,000
Omgekeerd, kan jy dink oor dit die ander manier om,

905
00:50:58,000 --> 00:51:02,000
die laaste is die eerste uit.

906
00:51:02,000 --> 00:51:05,000
>> Nou, 'n scenario na vore kom waar 'n stapel

907
00:51:05,000 --> 00:51:08,000
data struktuur waar jy daardie eiendom

908
00:51:08,000 --> 00:51:13,000
van die laaste in, eerste uit, is eintlik interessant?

909
00:51:13,000 --> 00:51:16,000
Is dit 'n goeie ding? Is dit 'n slegte ding?

910
00:51:16,000 --> 00:51:19,000
Dit is beslis 'n slegte ding is as die bak was nie almal identies

911
00:51:19,000 --> 00:51:21,000
en hulle was almal spesiale verskillende kleure of iets anders,

912
00:51:21,000 --> 00:51:24,000
en die kleur wat jy wil, is al die pad aan die onderkant.

913
00:51:24,000 --> 00:51:26,000
Van die kursus, kan jy nie kry wat sonder groot moeite.

914
00:51:26,000 --> 00:51:28,000
Jy het om te begin van die bo-en werk jou pad af.

915
00:51:28,000 --> 00:51:31,000
Net so, wat as jy een van hierdie fan seuns

916
00:51:31,000 --> 00:51:34,000
wat wag op die hele nag probeer om 'n iPhone en in lyn te kry

917
00:51:34,000 --> 00:51:36,000
op 'n plek soos hierdie?

918
00:51:36,000 --> 00:51:40,000
Sou dit nie lekker wees as die Apple Store

919
00:51:40,000 --> 00:51:42,000
was 'n stapel data struktuur?

920
00:51:42,000 --> 00:51:44,000
Yay? Nee?

921
00:51:44,000 --> 00:51:47,000
Dit is net goed vir die mense wat wys op die laaste minuut

922
00:51:47,000 --> 00:51:50,000
en dan die tou af geruk kry.

923
00:51:50,000 --> 00:51:52,000
En in die feit, die feit dat ek is so geneig om tou te sê

924
00:51:52,000 --> 00:51:56,000
is eintlik in ooreenstemming met wat ons sou noem hierdie soort data struktuur,

925
00:51:56,000 --> 00:51:59,000
een in werklikheid waar die einde maak nie saak,

926
00:51:59,000 --> 00:52:02,000
en jy wil die eerste een in die eerste een te wees uit

927
00:52:02,000 --> 00:52:04,000
indien slegs ter wille van die mens regverdigheid.

928
00:52:04,000 --> 00:52:07,000
Ons sal oor die algemeen noem dat 'n tou data struktuur.

929
00:52:07,000 --> 00:52:11,000
>> Dit blyk uit behalwe geskakelde lyste, kan ons begin deur gebruik te maak van hierdie basiese idees

930
00:52:11,000 --> 00:52:15,000
en begin met die skep van nuwe en verskillende tipes oplossings vir probleme.

931
00:52:15,000 --> 00:52:19,000
Byvoorbeeld, in die geval van 'n stapel, kan ons 'n stapel verteenwoordig

932
00:52:19,000 --> 00:52:22,000
met behulp van 'n data-struktuur soos hierdie, sou ek voorstel.

933
00:52:22,000 --> 00:52:26,000
In hierdie geval, het ek verklaar 'n struct, en ek het gesê binnekant van die struktuur

934
00:52:26,000 --> 00:52:30,000
is 'n skikking van getalle en dan 'n veranderlike genoem grootte,

935
00:52:30,000 --> 00:52:33,000
en ek gaan hierdie ding noem 'n stapel.

936
00:52:33,000 --> 00:52:35,000
Nou, waarom dit eintlik werk?

937
00:52:35,000 --> 00:52:43,000
In die geval van 'n stapel, kan ek dit effektief trek op die skerm as 'n skikking.

938
00:52:43,000 --> 00:52:47,000
Hier is my stapel. Dit is my nommers.

939
00:52:47,000 --> 00:52:50,000
En ons sal hulle trek soos hierdie, hierdie, hierdie, hierdie, hierdie.

940
00:52:50,000 --> 00:52:53,000
En dan het ek 'n paar ander data lid hier,

941
00:52:53,000 --> 00:52:58,000
wat genoem word grootte, so dit is grootte, en dit is getalle,

942
00:52:58,000 --> 00:53:02,000
en gesamentlik, die hele iPad hier een stapel struktuur.

943
00:53:02,000 --> 00:53:07,000
Nou, by verstek, grootte het vermoedelik het geïnisialiseer word na 0,

944
00:53:07,000 --> 00:53:11,000
en wat is binnekant van die skikking van getalle aanvanklik

945
00:53:11,000 --> 00:53:14,000
toe ek die eerste keer 'n skikking toeken?

946
00:53:14,000 --> 00:53:16,000
Gemors. Wie weet? En dit maak eintlik nie saak nie.

947
00:53:16,000 --> 00:53:20,000
Dit maak nie saak as dit is 1, 2, 3, 4, 5, heeltemal lukraak

948
00:53:20,000 --> 00:53:25,000
deur slegte geluk in my struktuur gestoor, want so lank as wat ek weet is dat die grootte van die stapel

949
00:53:25,000 --> 00:53:29,000
0 is, dan weet ek programmaties, kyk nie by enige van die elemente in die skikking.

950
00:53:29,000 --> 00:53:31,000
Dit maak nie saak wat daar staan.

951
00:53:31,000 --> 00:53:34,000
Moenie kyk na hulle, as sou die implikasie van 'n grootte van 0.

952
00:53:34,000 --> 00:53:38,000
>> Maar dink nou ek gaan voort en voeg iets in die stapel.

953
00:53:38,000 --> 00:53:42,000
Ek wil hê dat die getal 5 in te voeg, so ek het nommer 5 hier,

954
00:53:42,000 --> 00:53:45,000
en dan wat sit ek hier neer?

955
00:53:45,000 --> 00:53:48,000
Nou wil ek eintlik sit 1 vir die grootte,

956
00:53:48,000 --> 00:53:50,000
en nou is die stapel van grootte 1.

957
00:53:50,000 --> 00:53:53,000
Wat gebeur as ek gaan voort en voeg die nommer, laat ons sê, 7 volgende?

958
00:53:53,000 --> 00:53:57,000
Dit is dan kry opgedateer 2, en dan sal ons doen 9,

959
00:53:57,000 --> 00:54:02,000
en dan is dit word opgedateer tot 3.

960
00:54:02,000 --> 00:54:05,000
Maar die interessante kenmerk van hierdie stapel is dat

961
00:54:05,000 --> 00:54:09,000
Ek veronderstel watter element te verwyder as ek wil pop

962
00:54:09,000 --> 00:54:12,000
iets af van die stapel, om so te praat?

963
00:54:12,000 --> 00:54:14,000
9 sou die eerste ding om te gaan.

964
00:54:14,000 --> 00:54:18,000
Hoe moet die prentjie verander as ek wil 'n element van die stapel af te pop,

965
00:54:18,000 --> 00:54:20,000
graag 'n skinkbord in Mather?

966
00:54:20,000 --> 00:54:22,000
Ja >> [Studente] Set grootte 2.

967
00:54:22,000 --> 00:54:27,000
Presies, is al wat ek doen stel grootte 2, en wat moet ek doen met die skikking?

968
00:54:27,000 --> 00:54:29,000
Ek het nie iets te doen.

969
00:54:29,000 --> 00:54:32,000
Ek kon net anale te wees, sit daar 'n 0 of 'n -1 of iets om aan te dui

970
00:54:32,000 --> 00:54:34,000
dat dit nie 'n ligitieme waarde, maar dit maak nie saak nie, want

971
00:54:34,000 --> 00:54:37,000
Ek kan teken buite die skikking self hoe lank dit is

972
00:54:37,000 --> 00:54:41,000
sodat Ek weet net te kyk na die eerste twee elemente in die skikking.

973
00:54:41,000 --> 00:54:47,000
Nou, as ek gaan en voeg die getal 8 tot hierdie skikking, hoe verander die prentjie volgende?

974
00:54:47,000 --> 00:54:50,000
Dit word 8, en dit word 3.

975
00:54:50,000 --> 00:54:52,000
Ek sny 'n paar hoeke hier.

976
00:54:52,000 --> 00:54:56,000
Nou het ons 5, 7, 8, en ons is terug na 'n grootte van 3.

977
00:54:56,000 --> 00:54:58,000
Dit is redelik maklik om te implementeer,

978
00:54:58,000 --> 00:55:06,000
maar wanneer gaan ons hierdie ontwerp besluit om te betreur?

979
00:55:06,000 --> 00:55:09,000
Wanneer begin dinge doen baie, baie verkeerd om te gaan? Ja.

980
00:55:09,000 --> 00:55:11,000
[Onhoorbaar student reaksie]

981
00:55:11,000 --> 00:55:13,000
As jy wil om terug te gaan en kry die eerste element wat jy sit in

982
00:55:13,000 --> 00:55:18,000
>> Dit blyk uit hier, selfs al is 'n stapel is 'n verskeidenheid onder die kap,

983
00:55:18,000 --> 00:55:21,000
hierdie data strukture het ons begin praat oor die algemeen ook bekend as

984
00:55:21,000 --> 00:55:25,000
abstrakte data strukture waardeur hoe hulle geïmplementeer

985
00:55:25,000 --> 00:55:27,000
is heeltemal afgesien van die punt.

986
00:55:27,000 --> 00:55:31,000
'N data struktuur soos 'n stapel veronderstel is om ondersteuning toe te voeg

987
00:55:31,000 --> 00:55:35,000
bedrywighede soos druk, wat stoot 'n skinkbord op die stapel,

988
00:55:35,000 --> 00:55:39,000
en pop, wat hef 'n element van die stapel, en dit is dit.

989
00:55:39,000 --> 00:55:43,000
As jy iemand anders se kode wat reeds geïmplementeer was om af te laai

990
00:55:43,000 --> 00:55:46,000
hierdie ding genaamd 'n stapel, sou daardie persoon geskryf het

991
00:55:46,000 --> 00:55:49,000
slegs twee funksies vir jou, stoot en pop, wie se enigste doel in die lewe

992
00:55:49,000 --> 00:55:51,000
sou wees om presies dit te doen.

993
00:55:51,000 --> 00:55:54,000
Jy of hom of haar wat daardie program geïmplementeer

994
00:55:54,000 --> 00:55:58,000
sou gewees het heeltemal die een om te besluit hoe om te implementeer

995
00:55:58,000 --> 00:56:00,000
die semantiek van die stoot en knal onder die kap

996
00:56:00,000 --> 00:56:03,000
of die funksionaliteit van stoot en knal.

997
00:56:03,000 --> 00:56:07,000
En ek het hier 'n bietjie kortsigtig besluit

998
00:56:07,000 --> 00:56:10,000
deur die implementering van van my stapel met hierdie eenvoudige data van die struktuur waarom?

999
00:56:10,000 --> 00:56:12,000
Wanneer gaan hierdie data struktuur breek?

1000
00:56:12,000 --> 00:56:18,000
Op watter punt het ek 'n fout om terug te keer wanneer die gebruiker versoek druk, byvoorbeeld?

1001
00:56:18,000 --> 00:56:20,000
[Studente] As daar geen meer ruimte.

1002
00:56:20,000 --> 00:56:23,000
Presies, as daar is nie meer spasie, indien ek kapasiteit oorskry het,

1003
00:56:23,000 --> 00:56:27,000
wat alle pette, want dit dui daarop dat dit 'n soort van globale konstante.

1004
00:56:27,000 --> 00:56:30,000
Wel, dan is ek net gaan om te sê, "Jammer, ek kan nie 'n ander waarde stoot

1005
00:56:30,000 --> 00:56:32,000
op die stapel, "graag in Mather.

1006
00:56:32,000 --> 00:56:36,000
>> Op 'n sekere punt, gaan hulle die boonste deel van daardie klein kabinet te tref.

1007
00:56:36,000 --> 00:56:39,000
Daar is geen meer ruimte of kapasiteit in die stapel, op watter punt is daar is 'n soort van fout.

1008
00:56:39,000 --> 00:56:42,000
Hulle het die element om iewers anders te stel, die skinkbord iewers anders,

1009
00:56:42,000 --> 00:56:44,000
of nêrens op alle.

1010
00:56:44,000 --> 00:56:47,000
Nou, met 'n tou, kan ons dit implementeer 'n bietjie anders.

1011
00:56:47,000 --> 00:56:50,000
'N tou is 'n bietjie anders in dat onder die kap, dit geïmplementeer kan word

1012
00:56:50,000 --> 00:56:54,000
as 'n skikking, maar waarom, in hierdie geval, ek stel

1013
00:56:54,000 --> 00:56:59,000
ook 'n hoof element wat die hoof van die lys,

1014
00:56:59,000 --> 00:57:06,000
die voorkant van die lys, die eerste persoon in die lyn by die Apple Store, benewens grootte?

1015
00:57:06,000 --> 00:57:14,000
Hoekom het ek hier 'n bykomende stuk van die data?

1016
00:57:14,000 --> 00:57:16,000
Dink terug aan watter nommers is

1017
00:57:16,000 --> 00:57:18,000
as ek geteken het dit soos volg.

1018
00:57:18,000 --> 00:57:21,000
Veronderstel dit is nou 'n tou in plaas van 'n stapel,

1019
00:57:21,000 --> 00:57:24,000
die verskil wat net soos die Apple Store-queue is regverdig.

1020
00:57:24,000 --> 00:57:27,000
Die eerste persoon in die lyn by die begin van die lys, nommer 5 in hierdie geval,

1021
00:57:27,000 --> 00:57:30,000
hy of sy gaan word laat in die winkel eerste.

1022
00:57:30,000 --> 00:57:32,000
Kom ons doen dit.

1023
00:57:32,000 --> 00:57:35,000
Veronderstel dat dit die toestand van my tou op hierdie oomblik in die tyd, en nou die Apple Store

1024
00:57:35,000 --> 00:57:39,000
oop en die eerste persoon, nommer 5, is in die winkel gelei.

1025
00:57:39,000 --> 00:57:43,000
Hoe verander ek die prentjie nou dat ek de-queued is die eerste persoon

1026
00:57:43,000 --> 00:57:47,000
aan die voorkant van die lyn?

1027
00:57:47,000 --> 00:57:50,000
Wat is dit >> [Studente] Verander die tou.

1028
00:57:50,000 --> 00:57:52,000
Verander die kop, so 5 verdwyn.

1029
00:57:52,000 --> 00:57:56,000
In werklikheid, is dit asof die beste manier om dit te doen?

1030
00:57:56,000 --> 00:58:00,000
In werklikheid, is dit asof hierdie man verdwyn.

1031
00:58:00,000 --> 00:58:03,000
Wat sou nommer 7 in 'n werklike winkel?

1032
00:58:03,000 --> 00:58:05,000
Hulle sou 'n groot stap vorentoe te neem.

1033
00:58:05,000 --> 00:58:08,000
>> Maar wat kom ons om te waardeer wanneer dit kom by skikkings

1034
00:58:08,000 --> 00:58:10,000
en beweeg dinge rondom?

1035
00:58:10,000 --> 00:58:12,000
Dit is soort van 'n vermorsing van jou tyd, reg?

1036
00:58:12,000 --> 00:58:16,000
Hoekom het jy so anale as die eerste persoon te hê

1037
00:58:16,000 --> 00:58:21,000
aan die begin van die lyn by fisies die begin van die stuk van die geheue?

1038
00:58:21,000 --> 00:58:23,000
Dit is heeltemal onnodig. Hoekom?

1039
00:58:23,000 --> 00:58:26,000
Wat ek kan net onthou in plaas >> [onhoorbaar student reaksie]?

1040
00:58:26,000 --> 00:58:30,000
Presies, ek kan net onthou met hierdie addisionele data lid kop

1041
00:58:30,000 --> 00:58:34,000
wat nou die hoof van die lys is nie meer 0, wat dit was 'n oomblik gelede.

1042
00:58:34,000 --> 00:58:39,000
Nou is dit eintlik die aantal 1. Op hierdie manier, ek kry 'n effense optimalisering.

1043
00:58:39,000 --> 00:58:44,000
Net omdat ek de-queued is iemand uit lyn aan die begin van die lyn by die Apple Store

1044
00:58:44,000 --> 00:58:47,000
beteken nie almal te skuif, wat onthou is 'n lineêre werking.

1045
00:58:47,000 --> 00:58:50,000
Ek kan plaas konstante spandeer tyd net

1046
00:58:50,000 --> 00:58:53,000
en dan bereik 'n baie vinniger reaksie.

1047
00:58:53,000 --> 00:58:56,000
Maar die prys wat ek betaal is wat addisionele prestasie te verkry

1048
00:58:56,000 --> 00:58:58,000
en nie met almal te skuif?

1049
00:58:58,000 --> 00:59:01,000
Ja >> [onhoorbaar student antwoord].

1050
00:59:01,000 --> 00:59:04,000
Meer mense kan byvoeg, goed, dat die probleem is ortogonale

1051
00:59:04,000 --> 00:59:07,000
aan die feit dat ons nie die verskuiwing van mense rondom.

1052
00:59:07,000 --> 00:59:11,000
Dit is nog steeds 'n skikking, so of ons nie almal skuif of nie-

1053
00:59:11,000 --> 00:59:13,000
O, ek sien wat jy bedoel, okay.

1054
00:59:13,000 --> 00:59:16,000
Eintlik, ek stem saam met wat jy sê dat dit is amper asof

1055
00:59:16,000 --> 00:59:19,000
ons nou nooit gaan die begin van hierdie skikking te gebruik nie

1056
00:59:19,000 --> 00:59:22,000
want as ek verwyder 5, dan hef ek 7.

1057
00:59:22,000 --> 00:59:24,000
Maar ek het net mense aan die regterkant.

1058
00:59:24,000 --> 00:59:28,000
>> Dit voel asof ek mors ruimte, en uiteindelik my tou disintegreer in glad niks nie,

1059
00:59:28,000 --> 00:59:31,000
sodat ons kan net mense wraparound,

1060
00:59:31,000 --> 00:59:35,000
en ons kon dink regtig as 'n soort van omsendbrief struktuur van die skikking,

1061
00:59:35,000 --> 00:59:38,000
maar ons gebruik wat operateur in C daardie soort van wraparound te doen?

1062
00:59:38,000 --> 00:59:40,000
[Onhoorbaar student reaksie] >> Die modulo-operateur.

1063
00:59:40,000 --> 00:59:43,000
Dit sou 'n bietjie lastig deur te dink hoe doen jy die wraparound,

1064
00:59:43,000 --> 00:59:46,000
maar ons kan dit doen, en ons kon begin om mense wat gebruik word om die voorkant van die lyn,

1065
00:59:46,000 --> 00:59:52,000
maar ons het net met die hoof veranderlike wat die werklike hoof van die lyn is eintlik onthou.

1066
00:59:52,000 --> 00:59:57,000
Wat as, in plaas daarvan, ons doel uiteindelik, al is,

1067
00:59:57,000 --> 01:00:00,000
was om te kyk getalle, soos ons hier het op die verhoog met Anita,

1068
01:00:00,000 --> 01:00:02,000
maar ons wil regtig die beste van al hierdie wêrelde?

1069
01:00:02,000 --> 01:00:05,000
Ons wil meer gesofistikeerd as skikking kan

1070
01:00:05,000 --> 01:00:09,000
, want ons wil die vermoë om dinamiese groei van die data struktuur.

1071
01:00:09,000 --> 01:00:12,000
Maar ons wil nie 'n beroep op iets wat ons daarop gewys

1072
01:00:12,000 --> 01:00:15,000
in die eerste lesing was nie 'n optimale algoritme,

1073
01:00:15,000 --> 01:00:17,000
wat van lineêre soek.

1074
01:00:17,000 --> 01:00:21,000
Dit blyk dat jy kan bereik, in werklikheid,

1075
01:00:21,000 --> 01:00:24,000
of ten minste naby aan konstante tyd, waardeur iemand soos Anita,

1076
01:00:24,000 --> 01:00:27,000
as sy haar datastruktuur instel nie te wees 'n geskakelde lys,

1077
01:00:27,000 --> 01:00:30,000
nie 'n stapel te wees, nie om 'n tou te word, kan, in werklikheid,

1078
01:00:30,000 --> 01:00:33,000
kom met 'n datastruktuur wat dit moontlik maak om haar te kyk op dinge,

1079
01:00:33,000 --> 01:00:37,000
selfs woorde, nie net getalle, in wat ons noem konstante.

1080
01:00:37,000 --> 01:00:40,000
>> En in die feit, vooruit kyk, een van die psets in hierdie klas is byna altyd

1081
01:00:40,000 --> 01:00:43,000
'n implementering van 'n speltoetser, waardeur

1082
01:00:43,000 --> 01:00:46,000
gee ons jou weer n paar 150,000 Engelse woorde en die doel is om

1083
01:00:46,000 --> 01:00:51,000
laai wat in die geheue en vinnig in staat wees om vrae van die vorm te beantwoord

1084
01:00:51,000 --> 01:00:54,000
is hierdie woord korrek gespel?

1085
01:00:54,000 --> 01:00:58,000
En dit sou regtig suig as jy het om te itereer deur die hele 150.000 woorde om dit te beantwoord.

1086
01:00:58,000 --> 01:01:02,000
Maar, in werklikheid, sal ons sien dat ons dit kan doen in 'n baie, baie vinnig tyd.

1087
01:01:02,000 --> 01:01:06,000
En dit gaan die uitvoering van iets genoem 'n hash tafel te betrek,

1088
01:01:06,000 --> 01:01:09,000
en selfs al met die eerste oogopslag hierdie ding genoem 'n hash tafel gaan

1089
01:01:09,000 --> 01:01:12,000
Laat ons bereik hierdie super vinnige reaksie tye,

1090
01:01:12,000 --> 01:01:18,000
dit blyk dat daar in werklikheid 'n probleem.

1091
01:01:18,000 --> 01:01:23,000
Wanneer dit tyd is hierdie ding genaamd-weer te implementeer, ek doen dit weer.

1092
01:01:23,000 --> 01:01:25,000
Ek is die enigste een hier.

1093
01:01:25,000 --> 01:01:28,000
Wanneer dit tyd is om die implementering van hierdie ding genoem 'n hash tafel,

1094
01:01:28,000 --> 01:01:30,000
ons gaan te hê om 'n besluit te maak.

1095
01:01:30,000 --> 01:01:32,000
Hoe groot moet eintlik hierdie ding?

1096
01:01:32,000 --> 01:01:36,000
En wanneer ons begin die invoeging van getalle in hierdie hash tafel,

1097
01:01:36,000 --> 01:01:38,000
hoe gaan ons hulle in so 'n manier te stoor

1098
01:01:38,000 --> 01:01:42,000
wat ons kan kry hulle terug so gou as ons het hulle in?

1099
01:01:42,000 --> 01:01:45,000
Maar ons sal sien voor lank dat hierdie vraag van

1100
01:01:45,000 --> 01:01:48,000
wanneer almal se verjaarsdag is in die klas sal wees redelik related.

1101
01:01:48,000 --> 01:01:51,000
Dit blyk dat in hierdie kamer, het ons 'n paar honderd mense het,

1102
01:01:51,000 --> 01:01:56,000
sodat die kans dat twee van ons het dieselfde verjaarsdag waarskynlik is redelik hoog is.

1103
01:01:56,000 --> 01:01:58,000
Wat as daar net 40 van ons in hierdie kamer?

1104
01:01:58,000 --> 01:02:02,000
Wat is die kans van twee mense wat dieselfde verjaarsdag?

1105
01:02:02,000 --> 01:02:04,000
[Studente] Meer as 50%.

1106
01:02:04,000 --> 01:02:06,000
Ja, meer as 50%. Trouens, ek het selfs 'n grafiek.

1107
01:02:06,000 --> 01:02:08,000
Dit blyk uit-en dit is regtig net 'n sneak preview-

1108
01:02:08,000 --> 01:02:12,000
indien daar is net 58 van ons in hierdie kamer, die waarskynlikheid van 2 van ons

1109
01:02:12,000 --> 01:02:16,000
wat dieselfde verjaarsdag is uiters hoog, byna 100%,

1110
01:02:16,000 --> 01:02:20,000
en dit gaan 'n hele klomp van die seer vir ons te laat op Woensdag.

1111
01:02:20,000 --> 01:02:24,000
>> Met wat gesê het, laat ons hier verdaag. Ons sal sien dat jy op Woensdag.

1112
01:02:24,000 --> 01:02:28,000
[Applous]

1113
01:02:28,000 --> 01:02:30,000
[CS50.TV]