1
00:00:00,000 --> 00:00:11,860

2
00:00:11,860 --> 00:00:13,120
>> Spreker 1: Alle reg, so ons is terug.

3
00:00:13,120 --> 00:00:14,480
Welkom by CS50.

4
00:00:14,480 --> 00:00:16,510
Dit is die einde van die week sewe.

5
00:00:16,510 --> 00:00:20,200
So onthou dat dit die laaste tyd, het ons begin
kyk na effens meer gesofistikeerd

6
00:00:20,200 --> 00:00:21,100
data strukture.

7
00:00:21,100 --> 00:00:25,110
Sedert tot nou toe, al het ons regtig
tot ons beskikking was dit 'n skikking.

8
00:00:25,110 --> 00:00:29,340
>> Maar voordat ons wegdoen met die skikking as nie
alles wat interessant is, wat dit inderdaad

9
00:00:29,340 --> 00:00:33,570
eintlik is, wat is 'n paar van die
plus punte van hierdie eenvoudige data

10
00:00:33,570 --> 00:00:34,560
struktuur tot dusver?

11
00:00:34,560 --> 00:00:36,110
Wat is dit goed?

12
00:00:36,110 --> 00:00:39,450
So ver as wat ons gesien het?

13
00:00:39,450 --> 00:00:42,540
Wat doen jy het?

14
00:00:42,540 --> 00:00:44,028
Niks nie.

15
00:00:44,028 --> 00:00:45,020
>> STUDENT: [onhoorbaar].

16
00:00:45,020 --> 00:00:45,395
>> Spreker 1: Wat is dit?

17
00:00:45,395 --> 00:00:46,410
>> STUDENT: [onhoorbaar].

18
00:00:46,410 --> 00:00:47,000
>> Spreker 1: vaste grootte.

19
00:00:47,000 --> 00:00:51,260
OK, so is die rede waarom vaste grootte goeie alhoewel?

20
00:00:51,260 --> 00:00:53,180
>> STUDENT: [onhoorbaar].

21
00:00:53,180 --> 00:00:56,240
>> Spreker 1: OK, so dit is effektief in
die sin dat jy 'n kan toeken

22
00:00:56,240 --> 00:01:00,070
vaste bedrag van die ruimte, wat hopelik
is juis soveel

23
00:01:00,070 --> 00:01:01,180
ruimte as wat jy wil.

24
00:01:01,180 --> 00:01:02,720
So wat kan absoluut 'n plus wees.

25
00:01:02,720 --> 00:01:06,530
>> Wat is 'n ander up kant van 'n skikking?

26
00:01:06,530 --> 00:01:07,610
Ja?

27
00:01:07,610 --> 00:01:08,750
>> STUDENT: [onhoorbaar].

28
00:01:08,750 --> 00:01:09,550
>> Spreker 1: Al die - jammer?

29
00:01:09,550 --> 00:01:11,270
>> STUDENT: [onhoorbaar].

30
00:01:11,270 --> 00:01:13,620
>> Spreker 1: Al die bokse in die geheue
of langs mekaar.

31
00:01:13,620 --> 00:01:15,220
En dit is nuttig - hoekom?

32
00:01:15,220 --> 00:01:15,970
Dit is heeltemal waar nie.

33
00:01:15,970 --> 00:01:18,611
Maar hoe kan ons uitbuit dat die waarheid?

34
00:01:18,611 --> 00:01:21,500
>> STUDENT: [onhoorbaar].

35
00:01:21,500 --> 00:01:24,490
>> Spreker 1: Presies, kan ons hou van
waar alles is net deur te weet

36
00:01:24,490 --> 00:01:28,560
een adres, naamlik die adres van die
eerste greep van daardie deel van die geheue.

37
00:01:28,560 --> 00:01:30,420
Of in die geval van die string,
die adres van die eerste

38
00:01:30,420 --> 00:01:31,460
kar in die tou.

39
00:01:31,460 --> 00:01:33,330
En van daar af, kan ons
die einde van die string.

40
00:01:33,330 --> 00:01:35,710
Ons kan die tweede element, die
derde element, en so meer.

41
00:01:35,710 --> 00:01:38,740
>> En so het die fancy manier om te beskryf wat
kenmerk is dat skikkings gee ons

42
00:01:38,740 --> 00:01:40,020
ewekansige toegang.

43
00:01:40,020 --> 00:01:44,330
Net deur die gebruik van die vierkante hakies
notasie en 'n getal is, kan jy spring om te

44
00:01:44,330 --> 00:01:48,070
'n spesifieke element in die skikking
in konstante tyd, 'n groot O

45
00:01:48,070 --> 00:01:49,810
van een, om so te spreek.

46
00:01:49,810 --> 00:01:51,080
>> Maar daar is 'n paar nadele.

47
00:01:51,080 --> 00:01:53,110
Wat 'n skikking nie baie maklik doen?

48
00:01:53,110 --> 00:01:55,810

49
00:01:55,810 --> 00:01:57,170
Wat is dit glad nie goed nie?

50
00:01:57,170 --> 00:01:58,810
>> STUDENT: [onhoorbaar].

51
00:01:58,810 --> 00:01:59,860
>> Spreker 1: Wat is dit?

52
00:01:59,860 --> 00:02:00,530
>> STUDENT: [onhoorbaar].

53
00:02:00,530 --> 00:02:01,460
>> Spreker 1: uit te brei in grootte.

54
00:02:01,460 --> 00:02:04,800
So het die nadele van die skikking is
presies die teenoorgestelde van wat die

55
00:02:04,800 --> 00:02:05,540
upsides is.

56
00:02:05,540 --> 00:02:07,610
So een van die nadele is
dat dit 'n vaste grootte.

57
00:02:07,610 --> 00:02:09,400
So jy kan nie regtig groei nie.

58
00:02:09,400 --> 00:02:13,510
Jy kan weer toe 'n groter deel van
geheue, en dan beweeg die ou elemente

59
00:02:13,510 --> 00:02:14,460
in die nuwe skikking.

60
00:02:14,460 --> 00:02:18,060
En dan is vry om die ou skikking, vir
byvoorbeeld deur die gebruik van malloc of 'n soortgelyke

61
00:02:18,060 --> 00:02:21,180
funksie genoem realloc, wat
reserveert geheue.

62
00:02:21,180 --> 00:02:25,490
>> Realloc, as 'n eenkant, probeer om jou te gee
geheue wat langs die skikking

63
00:02:25,490 --> 00:02:26,610
wat jy reeds het.

64
00:02:26,610 --> 00:02:28,740
Maar dit kan beweeg dinge
om geheel en al.

65
00:02:28,740 --> 00:02:30,710
Maar in kort, dit is duur, reg?

66
00:02:30,710 --> 00:02:33,440
Want as jy 'n stuk van die geheue van
hierdie grootte, maar jy regtig wil een

67
00:02:33,440 --> 00:02:36,710
van hierdie grootte, en jy wil om te bewaar
die oorspronklike elemente, jy het

68
00:02:36,710 --> 00:02:40,510
ongeveer 'n lineêre tyd kopiëring proses
wat moet gebeur uit

69
00:02:40,510 --> 00:02:41,900
ou skikking te nuwe.

70
00:02:41,900 --> 00:02:44,630
En die werklikheid vra die bedryfstelsel
stelsel weer en weer en

71
00:02:44,630 --> 00:02:48,340
weer vir groot dele van die geheue kan begin
kos jou 'n paar keer as well.

72
00:02:48,340 --> 00:02:52,250
So dit is beide 'n seën en 'n vloek in
verbloem die feit dat hierdie skikkings

73
00:02:52,250 --> 00:02:53,860
is van vaste grootte.

74
00:02:53,860 --> 00:02:56,790
Maar as ons in plaas daarvan voer iets
soos hierdie, wat ons noem 'n gekoppelde

75
00:02:56,790 --> 00:03:00,580
lys, kry ons 'n paar upsides en
'n paar nadele ook hier.

76
00:03:00,580 --> 00:03:05,780
>> So 'n gekoppelde lys is bloot 'n data
struktuur bestaan ​​uit C structs in hierdie

77
00:03:05,780 --> 00:03:09,850
geval, waar 'n struct, onthou, is net
'n houer vir een of meer spesifieke

78
00:03:09,850 --> 00:03:11,100
tipes veranderlikes.

79
00:03:11,100 --> 00:03:16,110
In hierdie geval, wat doen die data tipes
lyk binnekant van die struct wees wat

80
00:03:16,110 --> 00:03:17,600
laaste keer dat ons 'n sogenaamde knoop?

81
00:03:17,600 --> 00:03:19,380
Elkeen van hierdie reghoeke is 'n knoop.

82
00:03:19,380 --> 00:03:22,660
En elk van die kleiner reghoeke
binnekant van dit is 'n data tipe.

83
00:03:22,660 --> 00:03:25,300
Watter tipes het ons sê
hulle was op Maandag?

84
00:03:25,300 --> 00:03:26,478
Ja?

85
00:03:26,478 --> 00:03:27,870
>> STUDENT: [onhoorbaar].

86
00:03:27,870 --> 00:03:30,721
>> Spreker 1: 'n veranderlike en 'n wyser, of
meer spesifiek, 'n int, vir n,

87
00:03:30,721 --> 00:03:32,180
en 'n wyser aan die onderkant.

88
00:03:32,180 --> 00:03:35,360
Beide van hulle gebeur om te wees 32 stukkies, by
minste op 'n rekenaar soos hierdie CS50

89
00:03:35,360 --> 00:03:37,980
Apparaat, en so is hulle
getrek ewe groot is.

90
00:03:37,980 --> 00:03:42,260
>> So, wat is die gebruik van die wyser
al vir glo?

91
00:03:42,260 --> 00:03:47,690
Hoekom voeg die pyl nou toe skikkings was
so mooi en skoon en eenvoudig?

92
00:03:47,690 --> 00:03:50,460
Wat is die wyser doen vir
ons in elk van hierdie nodes?

93
00:03:50,460 --> 00:03:52,160
>> STUDENT: [onhoorbaar].

94
00:03:52,160 --> 00:03:52,465
>> Spreker 1: Presies.

95
00:03:52,465 --> 00:03:54,120
Dit is wat jy vertel waar
die volgende een is.

96
00:03:54,120 --> 00:03:57,350
So het ek soort van gebruik van die analogie van die
met behulp van 'n draad te sorteer

97
00:03:57,350 --> 00:03:59,180
ryg hierdie nodes saam.

98
00:03:59,180 --> 00:04:01,760
En dit is presies wat ons doen met
wysers omdat elk van hierdie

99
00:04:01,760 --> 00:04:06,360
stukke van die geheue mag of nie mag wees
aangrensende, om terug te Terug na

100
00:04:06,360 --> 00:04:09,500
binnekant van die geheue, want elke keer as jy
noem malloc sê, gee my genoeg

101
00:04:09,500 --> 00:04:12,510
grepe vir 'n nuwe node, kan dit
hier te wees of dit kan hier te wees.

102
00:04:12,510 --> 00:04:13,120
Dit mag dalk hier te wees.

103
00:04:13,120 --> 00:04:13,730
Dit mag dalk hier te wees.

104
00:04:13,730 --> 00:04:14,640
Jy weet net nie.

105
00:04:14,640 --> 00:04:17,880
>> Maar met behulp van verwysings in die adresse van
diegene nodes, jy kan steek hulle

106
00:04:17,880 --> 00:04:22,370
saam in 'n manier wat lyk visueel
soos 'n lys, selfs al hierdie dinge is

107
00:04:22,370 --> 00:04:26,770
al versprei vind jou een of
u twee of jou vier GB RAM

108
00:04:26,770 --> 00:04:28,760
binnekant van jou eie rekenaar.

109
00:04:28,760 --> 00:04:33,230
>> So het die negatiewe kant, dan,
'n gekoppel lys is wat?

110
00:04:33,230 --> 00:04:34,670
Wat is 'n prys wat ons
blykbaar betaal?

111
00:04:34,670 --> 00:04:36,010
>> STUDENT: [onhoorbaar].

112
00:04:36,010 --> 00:04:36,920
>> Spreker 1: Meer ruimte, reg?

113
00:04:36,920 --> 00:04:39,340
Ons het, in hierdie geval, verdubbel die bedrag
van ruimte, want ons het gegaan

114
00:04:39,340 --> 00:04:43,500
van 32 stukkies vir elke knoop, vir elke
int, so nou 64 stukkies, want ons het om te

115
00:04:43,500 --> 00:04:45,050
hou om 'n wyser as well.

116
00:04:45,050 --> 00:04:48,860
Kry jy meer doeltreffendheid as jou struct
is groter as hierdie eenvoudige ding.

117
00:04:48,860 --> 00:04:52,020
As jy werklik 'n student in
van wat is 'n paar van die snare vir

118
00:04:52,020 --> 00:04:55,430
naam en huis, miskien 'n ID-nommer,
miskien 'n paar ander lande geheel en al.

119
00:04:55,430 --> 00:04:59,000
>> So as jy 'n groot genoeg struct,
dan miskien die koste van die wyser is

120
00:04:59,000 --> 00:05:00,010
nie so 'n groot deal.

121
00:05:00,010 --> 00:05:03,570
Dit is 'n bietjie van 'n hoek geval in daardie
ons stoor so 'n eenvoudige primitiewe

122
00:05:03,570 --> 00:05:04,760
binnekant van die geskakelde lys.

123
00:05:04,760 --> 00:05:05,790
Maar die punt is dieselfde.

124
00:05:05,790 --> 00:05:08,230
Jy is beslis spandeer meer
geheue, maar jy kry

125
00:05:08,230 --> 00:05:08,990
buigsaamheid.

126
00:05:08,990 --> 00:05:12,280
Want nou as ek wil 'n element by te voeg
aan die begin van hierdie lys,

127
00:05:12,280 --> 00:05:14,340
Ek het 'n nuwe node te ken.

128
00:05:14,340 --> 00:05:17,180
En ek moet net as werk
pyle een of ander manier deur net die beweging

129
00:05:17,180 --> 00:05:17,980
'n paar wenke rond.

130
00:05:17,980 --> 00:05:20,580
>> As ek iets wil plaas in die
middel van die lys, ek het nie te

131
00:05:20,580 --> 00:05:24,410
stoot almal opsy soos ons gedoen het in
weke se verlede met ons vrywilligers wat

132
00:05:24,410 --> 00:05:25,700
verteenwoordig 'n skikking.

133
00:05:25,700 --> 00:05:29,470
Ek kan net ken 'n nuwe knoop en
dan net wys die pyle in

134
00:05:29,470 --> 00:05:32,290
verskillende rigtings, omdat dit nie
het om te bly in die werklike

135
00:05:32,290 --> 00:05:35,670
geheue 'n ware lyn soos ek het getrek
dit hier op die skerm.

136
00:05:35,670 --> 00:05:38,400
>> En dan laastens, as jy wil te voeg
iets wat aan die einde van die lys is, is dit

137
00:05:38,400 --> 00:05:39,210
nog makliker.

138
00:05:39,210 --> 00:05:43,320
Dit is 'n soort van arbitrêre notasie,
maar 34 se wyser, neem 'n raaiskoot.

139
00:05:43,320 --> 00:05:46,710
Wat is die waarde van die wyser die meeste
waarskynlik getrek soort van soos 'n ou

140
00:05:46,710 --> 00:05:47,700
skool antenna daar?

141
00:05:47,700 --> 00:05:48,920
>> STUDENT: [onhoorbaar].

142
00:05:48,920 --> 00:05:49,900
>> Spreker 1: Dit is waarskynlik nul.

143
00:05:49,900 --> 00:05:52,710
En inderdaad, dit is een skrywer se
voorstelling van nul.

144
00:05:52,710 --> 00:05:56,310
En dit is nietig omdat jy absoluut
nodig het om te weet waar die einde van 'n gekoppelde

145
00:05:56,310 --> 00:06:00,050
lys is nie, dat jy hou volgende en
volg en na aanleiding van hierdie pyle

146
00:06:00,050 --> 00:06:01,170
tot 'n gemors waarde.

147
00:06:01,170 --> 00:06:06,230
So null sal beteken dat daar geen
meer nodes aan die regterkant van nommer 34,

148
00:06:06,230 --> 00:06:07,200
in hierdie geval.

149
00:06:07,200 --> 00:06:10,270
>> So stel ons voor dat ons kan implementeer
hierdie knoop in die kode.

150
00:06:10,270 --> 00:06:12,130
En ons het gesien hierdie soort
van sintaksis voor.

151
00:06:12,130 --> 00:06:15,090
Typedef definieer net 'n nuwe soort vir
ons, gee ons 'n sinoniem soos

152
00:06:15,090 --> 00:06:17,100
string was vir char *.

153
00:06:17,100 --> 00:06:21,030
In hierdie geval, dit gaan om te gee ons
snelskriknotasie sodat struct node

154
00:06:21,030 --> 00:06:24,010
kan plaas net geskryf word as
knoop, wat is 'n baie skoner.

155
00:06:24,010 --> 00:06:25,360
Dit is 'n baie minder verbose.

156
00:06:25,360 --> 00:06:30,080
>> Binnekant van 'n knoop is blykbaar 'n int
genoem n, en dan 'n struct node *

157
00:06:30,080 --> 00:06:34,670
wat beteken presies wat ons wou die
pyle om te beteken, 'n verwysing na 'n ander

158
00:06:34,670 --> 00:06:36,940
knoop van die presies dieselfde data tipe.

159
00:06:36,940 --> 00:06:40,300
En ek stel voor dat ons 'n kan implementeer
soek funksie soos hierdie, wat op

160
00:06:40,300 --> 00:06:41,890
die eerste oogopslag mag lyk
'n bietjie kompleks.

161
00:06:41,890 --> 00:06:43,330
Maar laat ons sien dit in konteks.

162
00:06:43,330 --> 00:06:45,480
>> Laat my gaan oor na die toestel hier.

163
00:06:45,480 --> 00:06:48,460
Laat my oop 'n lêer genaamd
lys nul dot h.

164
00:06:48,460 --> 00:06:53,950
En dit bevat slegs die definisie ons
het net gesien 'n oomblik gelede vir hierdie data

165
00:06:53,950 --> 00:06:55,390
tipe genoem 'n knoop.

166
00:06:55,390 --> 00:06:57,350
So het ons sit dit in 'n dot h lêer.

167
00:06:57,350 --> 00:07:01,430
>> En as 'n eenkant, selfs al is dit
program wat jy oor om te sien, is

168
00:07:01,430 --> 00:07:05,410
nie al wat kompleks is, is dit inderdaad
konvensie toe te skryf om 'n program te

169
00:07:05,410 --> 00:07:10,270
sit dinge soos data tipes, te trek
konstantes soms, binnekant van jou

170
00:07:10,270 --> 00:07:13,210
kop-lêer en nie noodwendig in
jou C lêer, seker wanneer jou

171
00:07:13,210 --> 00:07:17,370
programme kry groter en groter, sodat
jy weet waar beide om te kyk vir

172
00:07:17,370 --> 00:07:20,840
dokumentasie in sommige gevalle, of
vir basiese dinge soos hierdie, die

173
00:07:20,840 --> 00:07:22,360
definisie van 'n soort.

174
00:07:22,360 --> 00:07:25,680
>> As ek nou oop lys nul dot
c, sien 'n paar dinge.

175
00:07:25,680 --> 00:07:29,090
Dit sluit 'n paar kop lêers, die meeste
waarvan ons nog nooit gesien.

176
00:07:29,090 --> 00:07:31,980
Dit sluit in sy eie kop lêer.

177
00:07:31,980 --> 00:07:35,200
>> En as 'n eenkant, hoekom dit is dubbel
aanhalings hier, in teenstelling met die hoek

178
00:07:35,200 --> 00:07:38,340
tussen hakies op die lyn wat
Ek het daar uitgelig?

179
00:07:38,340 --> 00:07:39,180
>> STUDENT: [onhoorbaar].

180
00:07:39,180 --> 00:07:40,460
>> Spreker 1: Ja so dit is 'n plaaslike lêer.

181
00:07:40,460 --> 00:07:44,300
So as dit is 'n plaaslike lêer van jou eie hier
on line 15, byvoorbeeld, wat jy gebruik

182
00:07:44,300 --> 00:07:46,570
die dubbele aanhalingstekens plaas
van die hoek tussen hakies.

183
00:07:46,570 --> 00:07:48,270
>> Nou is dit 'n soort interessant.

184
00:07:48,270 --> 00:07:51,830
Let daarop dat ek 'n globale het verklaar
veranderlike in hierdie program op die lyn 18

185
00:07:51,830 --> 00:07:55,910
genoem die eerste, die idee dat dit is
gaan na 'n verwysing na die eerste wees

186
00:07:55,910 --> 00:07:59,190
knoop in my geskakelde lys, en ek het
geïnisialiseer dit aan nul, want ek het

187
00:07:59,190 --> 00:08:02,310
nie toegeken enige werklike
nodes net nog nie.

188
00:08:02,310 --> 00:08:07,570
>> Sodat hierdie verteenwoordig, picturaal, wat ons
het 'n oomblik gelede in die prentjie as

189
00:08:07,570 --> 00:08:10,090
dat wyser op die ver
links hand kant.

190
00:08:10,090 --> 00:08:12,260
So nou dat wyser
het nie 'n pyl.

191
00:08:12,260 --> 00:08:14,590
Dit is in plaas net null.

192
00:08:14,590 --> 00:08:17,880
Maar dit verteenwoordig wat sal wees om die
adres van die eerste werklike

193
00:08:17,880 --> 00:08:19,480
node in hierdie lys.

194
00:08:19,480 --> 00:08:22,120
So ek het dit geïmplementeer is 'n globale
want, soos jy sal sien, dit alles

195
00:08:22,120 --> 00:08:25,310
program nie in die lewe is te implementeer
'n gekoppel lys vir my.

196
00:08:25,310 --> 00:08:27,050
>> Nou het ek 'n paar prototipes hier.

197
00:08:27,050 --> 00:08:31,190
Ek het besluit om funksies soos om te implementeer
weglating, invoeging, soek, en

198
00:08:31,190 --> 00:08:31,740
traversal -

199
00:08:31,740 --> 00:08:35,210
die laaste om net loop oor die
lys, druk uit sy elemente.

200
00:08:35,210 --> 00:08:36,750
En nou is hier om my roetine.

201
00:08:36,750 --> 00:08:39,890
En ons sal nie te veel tyd spandeer op
hierdie want dit is soort van, hopelik

202
00:08:39,890 --> 00:08:41,780
ou hoed nou.

203
00:08:41,780 --> 00:08:45,370
>> Ek gaan die volgende te doen,
terwyl die gebruiker werk.

204
00:08:45,370 --> 00:08:47,300
So een, ek gaan om te druk
uit die menu.

205
00:08:47,300 --> 00:08:49,420
En ek het dit as geformateer
skoon as ek kon.

206
00:08:49,420 --> 00:08:52,240
As die gebruiker in een, wat beteken
hulle wil iets om te verwyder.

207
00:08:52,240 --> 00:08:54,560
As die gebruiker in twee, wat beteken
hulle iets wil voeg.

208
00:08:54,560 --> 00:08:55,930
En so meer.

209
00:08:55,930 --> 00:08:58,270
Ek gaan dan gevra
dan vir 'n bevel.

210
00:08:58,270 --> 00:08:59,300
En dan gaan ek getint te gebruik.

211
00:08:59,300 --> 00:09:02,790
>> So, dit is 'n baie eenvoudige menuing
koppeling waar jy hoef net te tik

212
00:09:02,790 --> 00:09:05,270
'n aantal kartering aan een
van daardie opdragte.

213
00:09:05,270 --> 00:09:08,730
En nou, ek het 'n mooi skoon skakelaar
verklaring wat gaan aan te skakel

214
00:09:08,730 --> 00:09:10,090
wat die gebruiker getik in

215
00:09:10,090 --> 00:09:12,180
En as hulle getik een, ek sal
noem verwyder en breek.

216
00:09:12,180 --> 00:09:14,380
As hulle getik twee, ek sal
noem voeg en breek.

217
00:09:14,380 --> 00:09:16,490
>> En nou is ek agterkom het sit elke
van hierdie op dieselfde lyn.

218
00:09:16,490 --> 00:09:18,360
Dit is net 'n stilistiese besluit.

219
00:09:18,360 --> 00:09:20,210
Tipies ons het gesien iets
soos hierdie.

220
00:09:20,210 --> 00:09:23,260
Maar ek het net besluit, eerlik, my program
lyk meer leesbare omdat

221
00:09:23,260 --> 00:09:25,980
dit was net vier gevalle te
net noem dit so.

222
00:09:25,980 --> 00:09:28,360
Heeltemal wettige gebruik van styl.

223
00:09:28,360 --> 00:09:31,480
En ek gaan om dit te doen so lank as wat die
gebruiker het nie 'getik nul, wat ek

224
00:09:31,480 --> 00:09:33,910
besluit sal beteken dat hulle wil hê om op te hou.

225
00:09:33,910 --> 00:09:36,630
>> So nou sien wat ek
gaan om hier te doen.

226
00:09:36,630 --> 00:09:38,650
Ek gaan die lys te glo bevry.

227
00:09:38,650 --> 00:09:40,230
Maar meer op wat in net 'n oomblik.

228
00:09:40,230 --> 00:09:41,640
Laat se eerste uitvoering van hierdie program.

229
00:09:41,640 --> 00:09:45,250
So laat my toe om 'n groter terminale
venster, dot streep lys 0.

230
00:09:45,250 --> 00:09:49,510
Ek gaan om voort te gaan en voeg by
tik twee, 'n aantal soos 50, en nou

231
00:09:49,510 --> 00:09:51,590
sal jy sien die lys is nou 50.

232
00:09:51,590 --> 00:09:53,380
En my teks net scrolled 'n bietjie.

233
00:09:53,380 --> 00:09:55,940
So nou op die lys bevat
die nommer 50.

234
00:09:55,940 --> 00:09:58,220
>> Kom ons doen 'n insetsel deur die neem van twee.

235
00:09:58,220 --> 00:10:01,630
Kom ons tik in die aantal soos een.

236
00:10:01,630 --> 00:10:03,940
Lys is nou een, gevolg deur 50.

237
00:10:03,940 --> 00:10:06,020
So dit is net 'n tekstuele verteenwoordiging
van die lys.

238
00:10:06,020 --> 00:10:10,550
En laat ons voeg een meer aantal soos
die nommer 42, wat hopelik

239
00:10:10,550 --> 00:10:14,620
gaan aan die einde in die middel, as gevolg
hierdie program in die besonder allerhande dit

240
00:10:14,620 --> 00:10:16,320
elemente soos dit plaas hulle.

241
00:10:16,320 --> 00:10:17,220
So daar het ons dit.

242
00:10:17,220 --> 00:10:20,730
Super eenvoudige program wat kan
absoluut gebruik het om 'n skikking, maar ek

243
00:10:20,730 --> 00:10:23,280
gebeur word met behulp van 'n gekoppelde lys
net sodat ek kan dinamiese

244
00:10:23,280 --> 00:10:24,610
groei en krimp dit.

245
00:10:24,610 --> 00:10:28,470
>> So kom ons neem 'n blik vir die soektog, as ek
hardloop opdrag drie, ek wil soek

246
00:10:28,470 --> 00:10:31,040
vir, sê, die getal 43.

247
00:10:31,040 --> 00:10:34,190
En niks is glo gevind is,
want ek het weer geen reaksie.

248
00:10:34,190 --> 00:10:35,010
So kom ons doen dit weer.

249
00:10:35,010 --> 00:10:35,690
Soek.

250
00:10:35,690 --> 00:10:39,520
Kom ons soek vir 50, of liewer soek
42, wat 'n mooi

251
00:10:39,520 --> 00:10:40,850
bietjie subtiele betekenis.

252
00:10:40,850 --> 00:10:42,610
En ek het die betekenis van die lewe daar.

253
00:10:42,610 --> 00:10:44,990
Nommer 42, as jy nie weet nie
die verwysing, Google dit.

254
00:10:44,990 --> 00:10:45,350
Alle regte.

255
00:10:45,350 --> 00:10:47,130
So, wat het hierdie program vir my gedoen?

256
00:10:47,130 --> 00:10:50,660
Dit is net my toegelaat om so te voeg
ver en soek vir elemente.

257
00:10:50,660 --> 00:10:53,650
>> Kom vinnig vorentoe, dan, te
wat funksioneer ons kyk na

258
00:10:53,650 --> 00:10:55,360
op Maandag as 'n teaser.

259
00:10:55,360 --> 00:10:59,620
So hierdie funksie, ek eis, soek
'n element in die lys deur die eerste

260
00:10:59,620 --> 00:11:03,830
een, waarna die gebruiker en dan roep
Getint 'n werklike int te kry

261
00:11:03,830 --> 00:11:05,060
wat jy wil om te soek vir.

262
00:11:05,060 --> 00:11:06,460
>> Toe dit agterkom.

263
00:11:06,460 --> 00:11:10,690
Ek gaan 'n tydelike veranderlike te skep
in lyn 188 geroep wyser -

264
00:11:10,690 --> 00:11:11,270
PTR -

265
00:11:11,270 --> 00:11:12,440
kon noem dit niks.

266
00:11:12,440 --> 00:11:16,140
En dit is 'n verwysing na 'n knoop
want ek sê knoop * daar.

267
00:11:16,140 --> 00:11:19,900
En ek initializing dit gelyk te wees aan
eerste sodat ek effektief het my

268
00:11:19,900 --> 00:11:22,860
vinger, om so te spreek, op die baie
eerste element van die lys.

269
00:11:22,860 --> 00:11:27,460
So as my regterhand hier is PTR ek
wys op dieselfde ding wat die eerste

270
00:11:27,460 --> 00:11:28,670
is wat dui op.

271
00:11:28,670 --> 00:11:31,430
>> So nou terug in die kode,
wat gebeur volgende -

272
00:11:31,430 --> 00:11:35,070
hierdie is 'n algemene paradigma wanneer iterating
meer as 'n struktuur soos 'n

273
00:11:35,070 --> 00:11:35,970
gekoppel lys.

274
00:11:35,970 --> 00:11:40,410
Ek gaan die volgende te doen, terwyl
wyser is nie gelyk aan nul So terwyl

275
00:11:40,410 --> 00:11:47,530
my vinger is nie wys op 'n nul
waarde, indien wyser pyl n gelykes n.

276
00:11:47,530 --> 00:11:52,290
Ons sal die eerste keer kennis dat n is wat die
gebruiker getik per GetInts noem hier.

277
00:11:52,290 --> 00:11:54,280
>> En wyser pyl n beteken wat?

278
00:11:54,280 --> 00:11:59,020
Wel as ons gaan terug na die prentjie hier,
as ek 'n vinger te wys op

279
00:11:59,020 --> 00:12:02,960
dat die eerste knoop met nege,
pyl beteken in wese gaan na daardie

280
00:12:02,960 --> 00:12:08,860
knoop en gryp die waarde op plek n,
in hierdie geval, die data veld genaamd n.

281
00:12:08,860 --> 00:12:14,120
>> As 'n eenkant - en ons het dit gesien 'n paar
weke gelede, toe iemand gevra -

282
00:12:14,120 --> 00:12:18,840
hierdie sintaksis is 'n nuwe, maar dit beteken nie
gee ons magte wat ons

283
00:12:18,840 --> 00:12:20,040
nie reeds het.

284
00:12:20,040 --> 00:12:25,325
Wat was hierdie frase gelykstaande aan die gebruik van
dot notasie en ster 'n paar

285
00:12:25,325 --> 00:12:29,490
weke gelede, toe ons geskil terug
hierdie laag 'n bietjie te vroeg?

286
00:12:29,490 --> 00:12:31,780
>> STUDENT: [onhoorbaar].

287
00:12:31,780 --> 00:12:38,880
>> Spreker 1: Presies, dit was star, en
dan was dit ster dot n, met

288
00:12:38,880 --> 00:12:41,930
hakies hier, wat lyk,
eerlik, ek dink 'n baie

289
00:12:41,930 --> 00:12:43,320
meer kripties te lees.

290
00:12:43,320 --> 00:12:46,270
Maar ster wyser, soos altyd,
beteken daar gaan.

291
00:12:46,270 --> 00:12:49,090
En wanneer jy daar is, wat data
gebied wil jy maak?

292
00:12:49,090 --> 00:12:52,730
Wel, jy gebruik maak van die dot-notasie om toegang te verkry
'n structs data veld, en ek

293
00:12:52,730 --> 00:12:54,140
spesifiek wil n.

294
00:12:54,140 --> 00:12:56,240
>> Eerlik, ek sou argumenteer dit
is net moeiliker om te lees.

295
00:12:56,240 --> 00:12:58,080
Dit is moeiliker om te onthou waar
moenie die hakies te gaan, die

296
00:12:58,080 --> 00:12:59,030
ster en al van dat.

297
00:12:59,030 --> 00:13:02,150
So het die wêreld aangeneem 'n sintaktiese
suiker, om so te praat.

298
00:13:02,150 --> 00:13:04,740
Net 'n sexy manier om te sê,
Dit is ekwivalent, en

299
00:13:04,740 --> 00:13:05,970
miskien meer intuïtief.

300
00:13:05,970 --> 00:13:09,600
As wyser is inderdaad 'n wyser, die
pyl skryfwyse beteken daar gaan en vind

301
00:13:09,600 --> 00:13:11,890
die veld in hierdie geval het n.

302
00:13:11,890 --> 00:13:13,660
>> So as ek dit vind, let op wat ek doen.

303
00:13:13,660 --> 00:13:17,430
Ek het net uit te druk, het ek gevind persent i,
steek in die waarde vir daardie int.

304
00:13:17,430 --> 00:13:20,730
Ek noem slaap vir 'n tweede net om te soort
van pouse dinge wat op die skerm te

305
00:13:20,730 --> 00:13:22,900
gee die gebruiker 'n tweede te absorbeer
wat nou net gebeur.

306
00:13:22,900 --> 00:13:24,290
En dan het ek breek.

307
00:13:24,290 --> 00:13:26,330
Anders, wat doen ek?

308
00:13:26,330 --> 00:13:30,960
Ek werk wyser op gelyke
wyser pyl volgende.

309
00:13:30,960 --> 00:13:35,840
>> So net om duidelik te wees, beteken dit gaan
daar is, met behulp van my ou-skool notasie.

310
00:13:35,840 --> 00:13:39,580
So, dit beteken net om te gaan na wat ook al
jy wys op wat in die baie

311
00:13:39,580 --> 00:13:43,660
eerste geval is ek wys op
die struct met nege in dit.

312
00:13:43,660 --> 00:13:44,510
So het ek daar weg is.

313
00:13:44,510 --> 00:13:47,880
En dan is die dot-notasie beteken,
kry die waarde op die volgende.

314
00:13:47,880 --> 00:13:50,470
>> Maar die waarde, selfs al is dit getrek
as 'n smal, is net 'n nommer.

315
00:13:50,470 --> 00:13:51,720
Dit is 'n numeriese adres.

316
00:13:51,720 --> 00:13:55,670
So hierdie een lyn van kode, of
geskryf soos hierdie, die meer kriptiese

317
00:13:55,670 --> 00:14:00,190
manier, of soos hierdie, die effens meer
intuïtiewe manier, beteken net beweeg my hand

318
00:14:00,190 --> 00:14:03,460
vanaf die eerste knoop na die volgende een,
en dan die volgende een, en dan die

319
00:14:03,460 --> 00:14:05,320
volgende een, en so meer.

320
00:14:05,320 --> 00:14:09,920
>> So ons sal nie die bewoners van die ander
implementering van voeg en te verwyder

321
00:14:09,920 --> 00:14:14,030
en traversal, die eerste twee van
wat redelik betrokke is.

322
00:14:14,030 --> 00:14:17,010
En ek dink dit is baie maklik om te kry
verloor wanneer dit mondelings.

323
00:14:17,010 --> 00:14:19,890
Maar wat kan ons hier doen, is om
probeer om te bepaal hoe

324
00:14:19,890 --> 00:14:21,640
dit die beste om visueel te doen.

325
00:14:21,640 --> 00:14:24,800
Want ek wil voorstel dat as ons
wil elemente in te voeg in hierdie

326
00:14:24,800 --> 00:14:26,680
bestaande lys, wat
het vyf elemente -

327
00:14:26,680 --> 00:14:29,530
9, 17, 22, 26, en 33 -

328
00:14:29,530 --> 00:14:33,300
As ek gaan om dit te implementeer in
kode, ek nodig het om te oorweeg hoe om te gaan

329
00:14:33,300 --> 00:14:34,160
oor om dit te doen.

330
00:14:34,160 --> 00:14:37,720
>> En ek stel voor die neem van baba stappe
waarvolgens, in hierdie geval ek bedoel, wat

331
00:14:37,720 --> 00:14:41,090
die moontlike scenario's wat ons
mag teëkom in die algemeen?

332
00:14:41,090 --> 00:14:44,120
Wanneer die implementering insetsel vir 'n gekoppelde
lys, dit gebeur net te wees om 'n

333
00:14:44,120 --> 00:14:46,090
spesifieke voorbeeld van grootte vyf.

334
00:14:46,090 --> 00:14:50,420
Wel, as jy 'n telefoonnommer in te voeg,
wil sê die nommer een, en

335
00:14:50,420 --> 00:14:53,380
die handhawing van orde gesorteer, waar
natuurlik het die nommer een nodig het om te

336
00:14:53,380 --> 00:14:55,686
gaan in hierdie spesifieke voorbeeld?

337
00:14:55,686 --> 00:14:56,840
Soos aan die begin.

338
00:14:56,840 --> 00:15:00,030
>> Maar wat interessant is, is daar daardie
As jy wil om een ​​te voeg in hierdie

339
00:15:00,030 --> 00:15:04,100
lys, wat spesiale wyser moet
word blykbaar opgedateer?

340
00:15:04,100 --> 00:15:04,610
Eerste.

341
00:15:04,610 --> 00:15:07,830
So ek sou argumenteer, is dit die eerste geval
dat ons dalk wil om te oorweeg, 'n

342
00:15:07,830 --> 00:15:11,140
scenario wat voeg by
die begin van die lys.

343
00:15:11,140 --> 00:15:15,400
>> Kom ons aftrek miskien 'n so maklik of selfs
makliker geval, relatief gesproke.

344
00:15:15,400 --> 00:15:18,110
Dink ek wil die te voeg
nommer 35 in gesorteer orde.

345
00:15:18,110 --> 00:15:20,600
Dit behoort duidelik daar.

346
00:15:20,600 --> 00:15:25,320
So, wat wyser natuurlik gaan
bygewerk moet word in daardie scenario?

347
00:15:25,320 --> 00:15:30,060
34 se wyser raak nie null
Maar die adres van die struct

348
00:15:30,060 --> 00:15:31,800
met die nommer 35.

349
00:15:31,800 --> 00:15:32,750
So dit is die geval twee.

350
00:15:32,750 --> 00:15:36,190
So al, ek is soort van quantizing
hoeveel werk ek het om hier te doen.

351
00:15:36,190 --> 00:15:39,880
>> En laastens, die voor die hand liggende middel geval is
Inderdaad, in die middel, as ek wil

352
00:15:39,880 --> 00:15:45,870
voeg iets soos sê 23, wat gaan
tussen die 23 en die 26, maar

353
00:15:45,870 --> 00:15:48,680
nou dinge 'n bietjie meer
betrokke is, omdat wat

354
00:15:48,680 --> 00:15:52,800
verwysings moet verander word?

355
00:15:52,800 --> 00:15:56,680
So 22 moet natuurlik om te verander
want hy kan nie verwys na 26 nie.

356
00:15:56,680 --> 00:16:00,320
Hy moet verwys na die nuwe knoop wat
Ek sal moet ken deur te bel

357
00:16:00,320 --> 00:16:01,770
malloc of 'n ekwivalent.

358
00:16:01,770 --> 00:16:05,990
>> Maar dan moet ek ook dat die nuwe knoop, 23
In hierdie geval, het sy wyser

359
00:16:05,990 --> 00:16:07,870
wys na wie?

360
00:16:07,870 --> 00:16:08,560
26.

361
00:16:08,560 --> 00:16:10,380
En daar gaan wees om 'n
orde van bedrywighede hier.

362
00:16:10,380 --> 00:16:13,410
Want as ek dit doen dwaasheid, en ek
byvoorbeeld begin by die begin van die

363
00:16:13,410 --> 00:16:16,040
die lys, en my doel is om 23 te voeg.

364
00:16:16,040 --> 00:16:18,610
En ek gaan nie, beteken dit behoort
hier, naby nege?

365
00:16:18,610 --> 00:16:18,950
No

366
00:16:18,950 --> 00:16:20,670
Maak dit hoort hier, langs 17?

367
00:16:20,670 --> 00:16:20,940
No

368
00:16:20,940 --> 00:16:22,530
Doen dit hier hoort langs 22?

369
00:16:22,530 --> 00:16:23,300
Ja.

370
00:16:23,300 --> 00:16:26,400
>> Nou as ek dwase hier, en nie
dink dit deur, kan ek

371
00:16:26,400 --> 00:16:28,320
wys my nuwe node vir 23.

372
00:16:28,320 --> 00:16:32,080
Ek kan werk om die verwysing van
die knoop genoem 22, wys

373
00:16:32,080 --> 00:16:33,080
dit by die nuwe knoop.

374
00:16:33,080 --> 00:16:36,140
En dan wat moet ek te werk
die nuwe node se wyser te wees?

375
00:16:36,140 --> 00:16:38,120
>> STUDENT: [onhoorbaar].

376
00:16:38,120 --> 00:16:38,385
>> Spreker 1: Presies.

377
00:16:38,385 --> 00:16:39,710
Wys op 26.

378
00:16:39,710 --> 00:16:45,590
Maar dammit as ek nie reeds werk
22 se muis te wys op hierdie man, en

379
00:16:45,590 --> 00:16:48,260
nou het ek weeskinders, die res
van die lys, om so te spreek.

380
00:16:48,260 --> 00:16:52,140
So orde van bedrywighede hier
gaan belangrik wees.

381
00:16:52,140 --> 00:16:55,100
>> Om dit te doen, kan ek nie steel nie,
sê, ses vrywilligers.

382
00:16:55,100 --> 00:16:57,650
En laat ons kyk of ons kan dit nie doen nie
visueel in plaas van die kode-wyse.

383
00:16:57,650 --> 00:16:59,330
En ons het 'n paar pragtige stres
balle vir jou vandag.

384
00:16:59,330 --> 00:17:02,510
OK, hoe oor een, twee, in die
terug - op die ou end.

385
00:17:02,510 --> 00:17:04,530
drie, vier, albei van julle
ouens op die einde.

386
00:17:04,530 --> 00:17:05,579
En vyf, ses.

387
00:17:05,579 --> 00:17:05,839
Seker nie.

388
00:17:05,839 --> 00:17:06,450
Vyf en ses.

389
00:17:06,450 --> 00:17:08,390
Alle reg, en ons sal kom
om julle volgende keer.

390
00:17:08,390 --> 00:17:09,640
Alle reg, kom op.

391
00:17:09,640 --> 00:17:12,010

392
00:17:12,010 --> 00:17:14,819
>> Alle reg, aangesien jy eers hier,
wil jy die een wees wat ongemaklik

393
00:17:14,819 --> 00:17:16,119
in Google Glass hier?

394
00:17:16,119 --> 00:17:19,075
Alle reg, so, OK, Glass,
'n video opneem.

395
00:17:19,075 --> 00:17:22,720

396
00:17:22,720 --> 00:17:24,589
OK, jy is goed om te gaan.

397
00:17:24,589 --> 00:17:27,950
>> Alle reg, so as jy ouens kan kom oor
Hier het ek berei in advance

398
00:17:27,950 --> 00:17:30,110
'n paar nommers.

399
00:17:30,110 --> 00:17:31,240
Alle reg, kom hier.

400
00:17:31,240 --> 00:17:33,440
En hoekom gaan jy nie 'n bietjie
verder dat die pad.

401
00:17:33,440 --> 00:17:35,520
En laat ons sien, wat is jou naam,
met die Google Glass?

402
00:17:35,520 --> 00:17:35,910
>> STUDENT: Ben.

403
00:17:35,910 --> 00:17:36,230
>> Spreker 1: Ben?

404
00:17:36,230 --> 00:17:38,380
OK, Ben, sal jy eerste wees, letterlik.

405
00:17:38,380 --> 00:17:40,580
So ons gaan jou te stuur
aan die einde van die verhoog.

406
00:17:40,580 --> 00:17:41,670
Alle reg, en jou naam?

407
00:17:41,670 --> 00:17:41,990
>> STUDENT: Jason.

408
00:17:41,990 --> 00:17:44,530
>> Spreker 1: Jason, OK jy sal
wees nommer nege.

409
00:17:44,530 --> 00:17:46,700
So as jy wil Ben dat die pad om te volg.

410
00:17:46,700 --> 00:17:47,010
>> STUDENT: Jill.

411
00:17:47,010 --> 00:17:49,630
>> Spreker 1: Jill, jy gaan te wees
17, wat as ek dit gedoen het meer

412
00:17:49,630 --> 00:17:51,260
intelligent, sou ek
begin aan die ander kant.

413
00:17:51,260 --> 00:17:52,370
Jy gaan op die manier.

414
00:17:52,370 --> 00:17:53,030
22.

415
00:17:53,030 --> 00:17:53,670
En jy is nie?

416
00:17:53,670 --> 00:17:53,980
>> STUDENT: Mary.

417
00:17:53,980 --> 00:17:56,130
>> Spreker 1: Mary, sal jy 22.

418
00:17:56,130 --> 00:17:58,420
En jou naam?

419
00:17:58,420 --> 00:17:58,810
>> STUDENT: Chris.

420
00:17:58,810 --> 00:18:00,100
>> Spreker 1: Chris, sal jy 26.

421
00:18:00,100 --> 00:18:00,740
En dan laastens.

422
00:18:00,740 --> 00:18:01,400
>> STUDENT: Diana.

423
00:18:01,400 --> 00:18:02,670
>> Spreker 1: Diana, sal jy 34.

424
00:18:02,670 --> 00:18:03,920
So jy kom op hier.

425
00:18:03,920 --> 00:18:06,360
>> Alle reg, so perfek gesorteer
gelas reeds.

426
00:18:06,360 --> 00:18:09,600
En laat ons gaan voort en doen dit
sodat ons kan regtig -

427
00:18:09,600 --> 00:18:11,720
Ben jy is net soort van kyk
uit na nêrens.

428
00:18:11,720 --> 00:18:15,670
OK, so laat ons gaan voort en stel dit
die gebruik van arms, baie soos ek was, presies,

429
00:18:15,670 --> 00:18:16,250
wat gaan aan.

430
00:18:16,250 --> 00:18:19,540
So gaan voort en gee julle 'n
voet of twee met mekaar het.

431
00:18:19,540 --> 00:18:22,900
En voort te gaan en wys met die een hand te
wie jy moet wys word by

432
00:18:22,900 --> 00:18:23,470
gebaseer op hierdie.

433
00:18:23,470 --> 00:18:25,890
En as jy null net wys
reguit af na die vloer.

434
00:18:25,890 --> 00:18:27,690
OK, so goed.

435
00:18:27,690 --> 00:18:32,290
>> So nou het ons 'n gekoppelde lys, en laat my
stel dat ek die rol van speel

436
00:18:32,290 --> 00:18:35,110
PTR, so ek sal nie die moeite
uitvoering van hierdie rond.

437
00:18:35,110 --> 00:18:37,830
En dan - iemand dom konvensie -
jy kan noem dit wat jy wil -

438
00:18:37,830 --> 00:18:39,800
voorganger wyser, pred wyser -

439
00:18:39,800 --> 00:18:43,930
dit is net die bynaam wat ons in
ons voorbeeld kode aan my linkerhand.

440
00:18:43,930 --> 00:18:47,240
Die ander kant wat gaan word om
spoor van wie is wie in die

441
00:18:47,240 --> 00:18:48,400
volgende scenario's.

442
00:18:48,400 --> 00:18:52,390
>> So dink, in die eerste, ek wil om uit te ruk af
dat die eerste voorbeeld van die inbring, sê

443
00:18:52,390 --> 00:18:54,330
20, in die lys.

444
00:18:54,330 --> 00:18:57,160
So ek gaan iemand nodig
verpersoonlik die nommer 20 vir ons.

445
00:18:57,160 --> 00:18:58,950
So ek moet malloc iemand
van die gehoor.

446
00:18:58,950 --> 00:18:59,380
Kom up.

447
00:18:59,380 --> 00:19:00,340
Wat is jou naam?

448
00:19:00,340 --> 00:19:01,300
>> STUDENT: Brian.

449
00:19:01,300 --> 00:19:05,270
>> Spreker 1: Brian, alles reg, sodat jy
sal die knoop met 20 wees.

450
00:19:05,270 --> 00:19:06,810
Alle reg, kom hier.

451
00:19:06,810 --> 00:19:10,025
En natuurlik, waar
beteken Brian behoort?

452
00:19:10,025 --> 00:19:12,190
So, in die middel van - eintlik,
wag 'n minuut.

453
00:19:12,190 --> 00:19:13,420
Ons doen dit buite orde.

454
00:19:13,420 --> 00:19:17,170
Ons is die maak van hierdie 'n baie moeiliker
as wat dit moet wees by die eerste.

455
00:19:17,170 --> 00:19:21,210
OK, gaan ons gratis Brian
en realloc Brian as vyf.

456
00:19:21,210 --> 00:19:23,680
>> OK, so nou wil ons in te voeg
Brian as vyf.

457
00:19:23,680 --> 00:19:25,960
So kom hier langs
Ben vir net 'n oomblik.

458
00:19:25,960 --> 00:19:28,250
En jy kan vermoedelik vertel
waar hierdie storie gaan.

459
00:19:28,250 --> 00:19:30,500
Maar laat ons dink mooi oor
die einde van bedrywighede.

460
00:19:30,500 --> 00:19:32,880
En dit is juis hierdie visuele
wat gaan om te reël om

461
00:19:32,880 --> 00:19:34,080
met die voorbeeld kode.

462
00:19:34,080 --> 00:19:40,120
So hier het ek PTR wys aanvanklik
nie by Ben, per se nie, maar op watter

463
00:19:40,120 --> 00:19:43,245
waarde wat hy bevat, wat in hierdie geval
is - wat is jou naam nou weer?

464
00:19:43,245 --> 00:19:43,670
>> STUDENT: Jason.

465
00:19:43,670 --> 00:19:47,350
>> Spreker 1: Jason, sodat beide Ben en ek is
wys op Jason op hierdie oomblik.

466
00:19:47,350 --> 00:19:49,700
So nou het ek om te bepaal,
waar kom Brian behoort?

467
00:19:49,700 --> 00:19:53,500
Dus is die enigste ding wat ek het toegang tot
nou is sy n data item.

468
00:19:53,500 --> 00:19:58,280
So ek gaan om seker te maak, is
Brian minder as Jason?

469
00:19:58,280 --> 00:19:59,770
Die antwoord is waar.

470
00:19:59,770 --> 00:20:03,680
>> So, wat moet nou gebeur,
in die korrekte volgorde?

471
00:20:03,680 --> 00:20:07,120
Ek het hoeveel verwysings na werk
in totaal in hierdie storie?

472
00:20:07,120 --> 00:20:10,720
Waar my hand is nog steeds wys na
Jason, en jou hand - as jy wil

473
00:20:10,720 --> 00:20:12,930
sit jou hand soos, soort van, ek
weet nie, 'n vraagteken.

474
00:20:12,930 --> 00:20:14,070
OK, goed.

475
00:20:14,070 --> 00:20:15,670
>> Alle reg, sodat jy
'n paar kandidate.

476
00:20:15,670 --> 00:20:20,500
Óf Ben of ek of Brian of Jason
of enigiemand anders, wat

477
00:20:20,500 --> 00:20:21,370
wysers te verander?

478
00:20:21,370 --> 00:20:23,260
Hoeveel in totaal?

479
00:20:23,260 --> 00:20:24,080
>> OK, so twee.

480
00:20:24,080 --> 00:20:27,090
My wyser nie regtig meer saak nie
want ek is net tydelik.

481
00:20:27,090 --> 00:20:31,370
So dit is hierdie twee ouens, vermoedelik,
beide Ben en Brian.

482
00:20:31,370 --> 00:20:34,410
So laat ek stel voor dat ons werk
Ben, want hy is die eerste.

483
00:20:34,410 --> 00:20:36,350
Die eerste element van hierdie lys
nou gaan wees Brian.

484
00:20:36,350 --> 00:20:38,070
So Ben punt Brian.

485
00:20:38,070 --> 00:20:39,320
OK, wat nou?

486
00:20:39,320 --> 00:20:41,950

487
00:20:41,950 --> 00:20:43,460
>> Wie word gewys na wie?

488
00:20:43,460 --> 00:20:44,710
>> STUDENT: [onhoorbaar].

489
00:20:44,710 --> 00:20:46,180
>> Spreker 1: OK so Brian het
te wys op Jason.

490
00:20:46,180 --> 00:20:48,360
Maar ek het tred verloor wat wyser?

491
00:20:48,360 --> 00:20:49,980
Weet ek waar Jason is?

492
00:20:49,980 --> 00:20:50,790
>> STUDENT: [onhoorbaar].

493
00:20:50,790 --> 00:20:52,620
>> Spreker 1: Dit doen nie, want ek is
die tydelike wyser.

494
00:20:52,620 --> 00:20:55,110
En vermoedelik, het ek nie verander nie
te wys op die nuwe knoop.

495
00:20:55,110 --> 00:20:58,300
Sodat ons kan eenvoudig Brian punt
by wie ek wys op.

496
00:20:58,300 --> 00:20:59,000
En ons klaar is.

497
00:20:59,000 --> 00:21:01,890
So geval een, voeg by die
die begin van die lys.

498
00:21:01,890 --> 00:21:02,950
Daar was twee belangrike stappe.

499
00:21:02,950 --> 00:21:06,750
Een, ons het Ben by te werk, en dan
ons het ook Brian te werk.

500
00:21:06,750 --> 00:21:09,230
En dan het ek hoef nie te pla
traipsing deur die res van die

501
00:21:09,230 --> 00:21:12,680
lys, want ons het reeds bevind sy
plek, want hy behoort aan die

502
00:21:12,680 --> 00:21:14,080
links van die eerste element.

503
00:21:14,080 --> 00:21:15,400
>> Alle reg, so mooi eenvoudig.

504
00:21:15,400 --> 00:21:18,110
In werklikheid, voel soos ons is amper
die maak van hierdie te ingewikkeld.

505
00:21:18,110 --> 00:21:20,240
So laat ons nou aftrek die einde
van die lys, en sien

506
00:21:20,240 --> 00:21:21,380
die kompleksiteit begin.

507
00:21:21,380 --> 00:21:24,560
So as ek nou alloc van die gehoor.

508
00:21:24,560 --> 00:21:25,540
Iemand wil hê om 55 te speel?

509
00:21:25,540 --> 00:21:26,700
Alle reg, sien ek jou hand eerste.

510
00:21:26,700 --> 00:21:29,620
Kom up.

511
00:21:29,620 --> 00:21:30,030
Ja.

512
00:21:30,030 --> 00:21:31,177
Wat is jou naam?

513
00:21:31,177 --> 00:21:32,310
>> STUDENT: [onhoorbaar].

514
00:21:32,310 --> 00:21:33,240
>> Spreker 1: Habata.

515
00:21:33,240 --> 00:21:33,890
OK, kom op.

516
00:21:33,890 --> 00:21:35,730
Jy sal die nommer 55 wees.

517
00:21:35,730 --> 00:21:37,820
So jy, natuurlik, behoort
aan die einde van die lys.

518
00:21:37,820 --> 00:21:41,850
So laat speel die simulasie met my
synde die PTR vir net 'n oomblik.

519
00:21:41,850 --> 00:21:44,050
So ek gaan eers te wys op
wat Ben is wys.

520
00:21:44,050 --> 00:21:45,900
Ons is albei wys nou by Brian.

521
00:21:45,900 --> 00:21:48,420
So 55 is nie minder nie as vyf.

522
00:21:48,420 --> 00:21:52,510
So ek gaan myself te werk deur
wys na Brian se volgende wyser, wat

523
00:21:52,510 --> 00:21:54,450
nou is natuurlik Jason.

524
00:21:54,450 --> 00:21:57,310
55 is nie minder nie as nege, so
Ek gaan PTR te werk.

525
00:21:57,310 --> 00:21:58,890
Ek gaan PTR te werk.

526
00:21:58,890 --> 00:22:02,290
Ek gaan PTR te werk
Ek gaan PTR te werk.

527
00:22:02,290 --> 00:22:05,060
En ek gaan - hmm, wat is
jou naam nou weer?

528
00:22:05,060 --> 00:22:05,560
>> STUDENT: Diana.

529
00:22:05,560 --> 00:22:09,190
>> Spreker 1: Diana is wys, natuurlik,
by null met haar linkerhand.

530
00:22:09,190 --> 00:22:13,030
So, waar Habata eintlik
behoort duidelik?

531
00:22:13,030 --> 00:22:15,050
Aan die linkerkant, hier.

532
00:22:15,050 --> 00:22:19,460
So, hoe weet ek haar hier te plaas
Ek dink ek het screwed up.

533
00:22:19,460 --> 00:22:22,420
Want wat is PTR kuns
hierdie oomblik in tyd?

534
00:22:22,420 --> 00:22:23,240
Null.

535
00:22:23,240 --> 00:22:25,580
Dus, selfs al is, visueel, kan ons
duidelik sien al hierdie

536
00:22:25,580 --> 00:22:26,610
ouens hier op die verhoog.

537
00:22:26,610 --> 00:22:29,680
Ek het nie tred gehou het met die vorige
persoon in die lys.

538
00:22:29,680 --> 00:22:33,210
Ek het nie 'n vinger te wys,
in hierdie geval, die knoop nommer 34.

539
00:22:33,210 --> 00:22:34,760
>> So laat ons begin eintlik dit oor.

540
00:22:34,760 --> 00:22:37,560
So nou is ek regtig nodig
'n tweede plaaslike veranderlike.

541
00:22:37,560 --> 00:22:40,980
En dit is wat jy sien in die
werklike monster C-kode, waar as Ek gaan,

542
00:22:40,980 --> 00:22:45,860
toe ek my hand na die punt
Jason, en daardeur verlaat Brian agter, ek

543
00:22:45,860 --> 00:22:51,440
beter begin met my linkerhand te
werk waar ek was, so dat as ek gaan

544
00:22:51,440 --> 00:22:52,700
deur middel van hierdie lys -

545
00:22:52,700 --> 00:22:55,040
meer ongemaklik as wat ek bedoel
nou hier visueel -

546
00:22:55,040 --> 00:22:56,740
Ek gaan om te kry om die
einde van die lys.

547
00:22:56,740 --> 00:23:00,020
>> Hierdie hand is nog nul, wat is mooi
nutteloos, anders as om aan te dui

548
00:23:00,020 --> 00:23:02,980
Ek is duidelik aan die einde van die lys,
maar nou ten minste ek het dit

549
00:23:02,980 --> 00:23:08,270
voorganger wyser wys hier, so
nou wat hande en wat wysers

550
00:23:08,270 --> 00:23:10,150
bygewerk moet word?

551
00:23:10,150 --> 00:23:13,214
Wie se hand wil jy
om weer instel eerste?

552
00:23:13,214 --> 00:23:15,190
>> STUDENT: [onhoorbaar].

553
00:23:15,190 --> 00:23:16,220
>> Spreker 1: OK, so Diana se.

554
00:23:16,220 --> 00:23:21,110
Waar wil jy om te wys
Diana se linker muis op?

555
00:23:21,110 --> 00:23:23,620
Op 55, vermoedelik, sodat
Ons het daar plaas.

556
00:23:23,620 --> 00:23:25,560
En waar moet 55 wyser gaan?

557
00:23:25,560 --> 00:23:27,000
Down, wat null.

558
00:23:27,000 --> 00:23:28,890
En my hande, op hierdie punt, doen nie
saak nie, want hulle was net

559
00:23:28,890 --> 00:23:30,070
tydelike veranderlikes.

560
00:23:30,070 --> 00:23:31,030
So nou is ons klaar is.

561
00:23:31,030 --> 00:23:34,650
>> So die bykomende kompleksiteit daar - en
dit is nie so moeilik om te implementeer,

562
00:23:34,650 --> 00:23:38,660
maar ons moet 'n sekondêre veranderlike te maak
seker dat voordat ek skuif my reg

563
00:23:38,660 --> 00:23:42,140
hand, ek werk om die waarde van my linkerhand
hand, pred wyser in hierdie geval, so

564
00:23:42,140 --> 00:23:45,860
dat ek 'n sleep wyser
rekord te hou van waar ek was.

565
00:23:45,860 --> 00:23:49,360
Nou as 'n eenkant, as jy dink hierdie
deur, dit voel soos dit is 'n

566
00:23:49,360 --> 00:23:51,490
klein irriterende te hê om te hou
spoor van die linkerhand.

567
00:23:51,490 --> 00:23:54,015
>> Wat sou 'n ander oplossing
om hierdie probleem gewees het?

568
00:23:54,015 --> 00:23:56,500
As jy die data te herontwerp
struktuur wat ons praat

569
00:23:56,500 --> 00:23:59,630
deur nou?

570
00:23:59,630 --> 00:24:02,690
As dit net 'n soort van voel 'n bietjie
irriterende te hê, soos, twee wysers

571
00:24:02,690 --> 00:24:08,430
gaan deur die lys, kan wie anders
het, in 'n ideale wêreld, in stand gehou

572
00:24:08,430 --> 00:24:10,160
inligting wat ons nodig het?

573
00:24:10,160 --> 00:24:11,360
Ja?

574
00:24:11,360 --> 00:24:12,610
>> STUDENT: [onhoorbaar].

575
00:24:12,610 --> 00:24:15,160

576
00:24:15,160 --> 00:24:16,150
>> Spreker 1: Presies.

577
00:24:16,150 --> 00:24:19,130
Reg so daar is eintlik 'n interessante
kiem van 'n idee.

578
00:24:19,130 --> 00:24:22,470
En die idee van 'n vorige wyser,
wys op die vorige element.

579
00:24:22,470 --> 00:24:25,580
Wat as ek net vergestalt wat
binnekant van die lys self?

580
00:24:25,580 --> 00:24:27,810
En dit gaan moeilik wees om te visualiseer
dit sonder om al die papier

581
00:24:27,810 --> 00:24:28,830
val op die vloer.

582
00:24:28,830 --> 00:24:31,860
Maar veronderstel dat hierdie ouens gebruik om beide
van hul hande 'n vorige te hê

583
00:24:31,860 --> 00:24:35,950
wyser, en 'n volgende wyser, en daardeur
die uitvoering van wat ons noem 'n dubbel

584
00:24:35,950 --> 00:24:36,830
gekoppel lys.

585
00:24:36,830 --> 00:24:41,090
Dit sou toelaat om my te sorteer van rewind,
veel makliker sonder my, die

586
00:24:41,090 --> 00:24:43,800
programmeerder, om te hou
spoor die hand -

587
00:24:43,800 --> 00:24:44,980
waarlik hand -

588
00:24:44,980 --> 00:24:47,280
van waar ek voorheen
in die lys.

589
00:24:47,280 --> 00:24:48,110
So sal ons dit nie doen nie.

590
00:24:48,110 --> 00:24:50,950
Ons sal dit eenvoudig te hou, want dit is
gaan om te kom teen 'n prys, twee keer so

591
00:24:50,950 --> 00:24:53,450
veel ruimte vir die wysers,
As jy wil 'n tweede een.

592
00:24:53,450 --> 00:24:55,760
Maar dit is inderdaad 'n gemeenskaplike
data struktuur bekend as 'n

593
00:24:55,760 --> 00:24:57,410
dubbel gekoppel lys.

594
00:24:57,410 --> 00:25:01,310
>> Kom ons doen die laaste voorbeeld hier en
hierdie ouens uit hulle ellende.

595
00:25:01,310 --> 00:25:03,270
So malloc 20.

596
00:25:03,270 --> 00:25:05,320
Kom op uit die paadjie is daar.

597
00:25:05,320 --> 00:25:06,280
Alle reg, wat is jou naam?

598
00:25:06,280 --> 00:25:07,440
>> STUDENT: [onhoorbaar].

599
00:25:07,440 --> 00:25:07,855
>> Spreker 1: Sorry?

600
00:25:07,855 --> 00:25:08,480
>> STUDENT: [onhoorbaar].

601
00:25:08,480 --> 00:25:09,410
>> Spreker 1: Demeron?

602
00:25:09,410 --> 00:25:10,230
OK kom up.

603
00:25:10,230 --> 00:25:11,910
Jy sal wees 20.

604
00:25:11,910 --> 00:25:14,720
Jy het natuurlik gaan
behoort tussen 17 en 22.

605
00:25:14,720 --> 00:25:16,150
So laat my leer my les.

606
00:25:16,150 --> 00:25:18,150
Ek gaan wyser te begin
wys na Brian.

607
00:25:18,150 --> 00:25:21,190
En ek gaan my linkerhand te hê
net werk na Brian as ek skuif na

608
00:25:21,190 --> 00:25:23,600
Jason, kontrolering doen 20 minder as nege?

609
00:25:23,600 --> 00:25:24,060
No

610
00:25:24,060 --> 00:25:25,430
Is 20 minder as 17?

611
00:25:25,430 --> 00:25:25,880
No

612
00:25:25,880 --> 00:25:27,450
Is 20 minder as 22?

613
00:25:27,450 --> 00:25:28,440
Ja.

614
00:25:28,440 --> 00:25:34,070
So, wat verwysings of hande nodig om te verander
waar hulle nou wys?

615
00:25:34,070 --> 00:25:37,070
>> So ons kan doen 17 wys op 20.

616
00:25:37,070 --> 00:25:37,860
So dit is goed.

617
00:25:37,860 --> 00:25:40,080
Waar wil ons te wys
jou wyser nou?

618
00:25:40,080 --> 00:25:41,330
Op 22.

619
00:25:41,330 --> 00:25:45,410
En ons weet waar 22 is, weer dankie
tot my tydelike wyser.

620
00:25:45,410 --> 00:25:46,760
So ons is OK daar.

621
00:25:46,760 --> 00:25:49,440
So as gevolg van hierdie tydelike berging
Ek het tred gehou waar almal is.

622
00:25:49,440 --> 00:25:55,055
En nou kan jy visueel gaan in waar
jy behoort, en nou moet ons 1, 2, 3,

623
00:25:55,055 --> 00:25:58,410
4, 5, 6, 7, 8, 9 stress balle,
en 'n rondte van applous vir

624
00:25:58,410 --> 00:25:59,770
hierdie ouens, as ons kon.

625
00:25:59,770 --> 00:26:00,410
Mooi gedoen.

626
00:26:00,410 --> 00:26:05,320
>> [Applous]

627
00:26:05,320 --> 00:26:06,330
>> Spreker 1: Alle reg.

628
00:26:06,330 --> 00:26:09,860
En jy mag die stukke
papier as aandenkings.

629
00:26:09,860 --> 00:26:15,930
>> Alle reg, so, glo my dit is 'n baie
makliker om te loop deur wat met

630
00:26:15,930 --> 00:26:17,680
die mens as wat dit is met die werklike kode.

631
00:26:17,680 --> 00:26:22,690
Maar wat jy sal vind in net 'n oomblik
nou, is dat dieselfde - O, dankie.

632
00:26:22,690 --> 00:26:23,630
Dankie -

633
00:26:23,630 --> 00:26:29,360
is dat jy dat dieselfde data sal vind
struktuur, 'n gekoppelde lys, kan eintlik

634
00:26:29,360 --> 00:26:33,200
gebruik word as 'n boublok om selfs meer
gesofistikeerde data strukture.

635
00:26:33,200 --> 00:26:37,620
>> En besef ook die tema hier is dat
Ons het absoluut ingestel meer

636
00:26:37,620 --> 00:26:40,060
kompleksiteit in die implementering
van hierdie algoritme.

637
00:26:40,060 --> 00:26:43,940
Inplanting, en as ons deur dit gegaan,
skrap en soek, is 'n bietjie

638
00:26:43,940 --> 00:26:46,660
meer ingewikkeld as wat dit
was met 'n skikking.

639
00:26:46,660 --> 00:26:48,040
Maar ons kry 'n bietjie dinamika.

640
00:26:48,040 --> 00:26:50,180
Ons kry 'n aangepaste data struktuur.

641
00:26:50,180 --> 00:26:54,010
>> Maar weereens, ons betaal 'n prys van 'n paar
bykomende kompleksiteit, beide in

642
00:26:54,010 --> 00:26:54,910
die uitvoering daarvan.

643
00:26:54,910 --> 00:26:56,750
En ons opgegee ewekansige toegang.

644
00:26:56,750 --> 00:27:00,450
En om eerlik te wees, is daar nie 'n paar mooi
skoon te skuif ek kan gee wat

645
00:27:00,450 --> 00:27:03,120
sê hier is die rede waarom 'n gekoppelde lys
is beter as 'n skikking.

646
00:27:03,120 --> 00:27:04,100
En laat dit op daardie.

647
00:27:04,100 --> 00:27:07,520
Omdat die tema herhaling nou, selfs
meer so in die komende weke, is

648
00:27:07,520 --> 00:27:10,200
dat daar nie noodwendig
'n korrekte antwoord.

649
00:27:10,200 --> 00:27:13,830
>> Dit is hoekom ons die afsonderlike as
van die ontwerp vir die probleem stelle.

650
00:27:13,830 --> 00:27:17,700
Dit sal baie konteks sensitiewe
of jy wil hierdie inligting te gebruik

651
00:27:17,700 --> 00:27:21,750
struktuur of dat 'n mens, en dit sal
afhang van wat vir jou saak maak in terme

652
00:27:21,750 --> 00:27:24,620
van hulpbronne en kompleksiteit.

653
00:27:24,620 --> 00:27:28,830
>> Maar laat ek stel voor dat die ideale data
struktuur, die heilige graal, sou wees

654
00:27:28,830 --> 00:27:32,200
iets wat konstant tyd,
ongeag van hoeveel dinge is

655
00:27:32,200 --> 00:27:36,940
binne-in, dit sal nie verbasend as 'n
data struktuur teruggekeer antwoorde in

656
00:27:36,940 --> 00:27:37,920
konstante tyd.

657
00:27:37,920 --> 00:27:38,330
Ja.

658
00:27:38,330 --> 00:27:40,110
Hierdie woord is in jou groot woordeboek.

659
00:27:40,110 --> 00:27:41,550
Of nee, hierdie woord is nie.

660
00:27:41,550 --> 00:27:43,270
Of enige so 'n probleem daar.

661
00:27:43,270 --> 00:27:46,360
Wel, laat ons kyk of ons nie ten minste
neem 'n stap in die rigting wat.

662
00:27:46,360 --> 00:27:50,190
>> Laat my stel 'n nuwe data struktuur wat
kan gebruik word vir verskillende dinge,

663
00:27:50,190 --> 00:27:52,260
In hierdie geval het 'n hash tafel.

664
00:27:52,260 --> 00:27:55,590
En so is ons eintlik terug na skrams
by 'n skikking, in hierdie geval, en

665
00:27:55,590 --> 00:28:00,550
ietwat arbitrêr, het ek opgestel om hierdie
hash tafel as 'n skikking met die soort van 'n

666
00:28:00,550 --> 00:28:02,810
twee-dimensionele skikking -

667
00:28:02,810 --> 00:28:05,410
of eerder dit hier uitgebeeld as 'n twee
dimensionele skikking - maar dit is net

668
00:28:05,410 --> 00:28:10,770
'n skikking van grootte 26, soos dat as ons
noem die skikking, tafel bracket

669
00:28:10,770 --> 00:28:12,440
zero is die reghoek aan die bokant.

670
00:28:12,440 --> 00:28:15,090
Table bracket 25 is die reghoek
aan die onderkant.

671
00:28:15,090 --> 00:28:18,620
En dit is hoe ek 'n data kan trek
struktuur in wat ek wil om te stoor

672
00:28:18,620 --> 00:28:19,790
mense se name.

673
00:28:19,790 --> 00:28:24,370
>> So byvoorbeeld, en ek sal nie trek die
hele ding hier op die oorhoofse, as ek

674
00:28:24,370 --> 00:28:29,160
het hierdie skikking, wat ek nou gaan
roep 'n hash tafel, en dit is weer

675
00:28:29,160 --> 00:28:31,360
plek nul.

676
00:28:31,360 --> 00:28:34,840
Dit is hier plek
een, en so meer.

677
00:28:34,840 --> 00:28:37,880
Ek eis dat ek wil hê om hierdie inligting te gebruik
struktuur, ter wille van die bespreking,

678
00:28:37,880 --> 00:28:42,600
mense se name op te slaan, Alice en Bob
en Charlie en ander sulke name.

679
00:28:42,600 --> 00:28:46,110
So dink van hierdie nou as die begin
van, sê, 'n woordeboek

680
00:28:46,110 --> 00:28:47,520
met baie van die woorde.

681
00:28:47,520 --> 00:28:49,435
Dit gebeur om te wees name
In ons voorbeeld hier.

682
00:28:49,435 --> 00:28:52,560
En dit is al te related, miskien, te
implementering van 'n speltoetser, soos ons

683
00:28:52,560 --> 00:28:54,400
dalk vir die probleem wat ses.

684
00:28:54,400 --> 00:28:59,300
>> So as ons het 'n verskeidenheid van die totale grootte 26
sodat dit is die 25ste plek

685
00:28:59,300 --> 00:29:03,390
aan die onderkant, en ek beweer dat Alice is
die eerste woord in die woordeboek van

686
00:29:03,390 --> 00:29:07,260
name wat ek wil in te voeg in geheue,
in hierdie data struktuur, waar is

687
00:29:07,260 --> 00:29:12,480
instink vertel dat Alice se
naam moet gaan in hierdie reeks?

688
00:29:12,480 --> 00:29:13,510
>> Ons het 26 opsies.

689
00:29:13,510 --> 00:29:14,990
Waar ons wil om haar te sit?

690
00:29:14,990 --> 00:29:16,200
Ons wil haar in hakies nul, reg?

691
00:29:16,200 --> 00:29:18,280
A vir Alice, kom ons noem dat die nul.

692
00:29:18,280 --> 00:29:20,110
En B sal een wees, en C sal twee.

693
00:29:20,110 --> 00:29:22,600
So ons gaan om te skryf
Alice se naam hier.

694
00:29:22,600 --> 00:29:24,890
As ons dan voeg Bob, sy
naam kom hier.

695
00:29:24,890 --> 00:29:27,280
Charlie sal hier gaan.

696
00:29:27,280 --> 00:29:30,500
En so meer af deur
hierdie data struktuur.

697
00:29:30,500 --> 00:29:32,090
>> Dit is 'n wonderlike data struktuur.

698
00:29:32,090 --> 00:29:32,730
Hoekom?

699
00:29:32,730 --> 00:29:37,460
Wel, wat is die loop van die tyd van
voeg 'n mens se naam in hierdie

700
00:29:37,460 --> 00:29:39,850
data struktuur nou?

701
00:29:39,850 --> 00:29:43,702
Gegee dat hierdie tabel geïmplementeer word,
waarlik, as 'n skikking.

702
00:29:43,702 --> 00:29:44,940
Wel dit is konstante tyd.

703
00:29:44,940 --> 00:29:45,800
Dit is om van die een.

704
00:29:45,800 --> 00:29:46,360
Hoekom?

705
00:29:46,360 --> 00:29:48,630
>> Wel, hoe bepaal jy
waar Alice behoort?

706
00:29:48,630 --> 00:29:51,000
Jy kyk na watter letter van haar naam?

707
00:29:51,000 --> 00:29:51,490
Die eerste.

708
00:29:51,490 --> 00:29:54,350
En jy kan daar kom, al is dit 'n string,
deur net te kyk na string

709
00:29:54,350 --> 00:29:55,200
bracket nul.

710
00:29:55,200 --> 00:29:57,110
So het die nulde karakter van die string.

711
00:29:57,110 --> 00:29:57,610
Dit is maklik.

712
00:29:57,610 --> 00:30:00,350
Ons het dit in die crypto
opdrag weke gelede.

713
00:30:00,350 --> 00:30:05,310
En dan wanneer jy weet dat Alice se
letter A is kapitaal, kan ons trek

714
00:30:05,310 --> 00:30:08,160
af 65 of kapitaal 'n self,
wat gee ons 'n nul.

715
00:30:08,160 --> 00:30:10,940
So ons weet nou dat Alice behoort
by plek nul.

716
00:30:10,940 --> 00:30:14,240
>> En die lig van 'n verwysing na hierdie data
struktuur, van 'n soort, hoe lank

717
00:30:14,240 --> 00:30:18,840
dit neem my plek te vind
nul in 'n skikking?

718
00:30:18,840 --> 00:30:22,080
Net 'n stap, reg Dit is konstante
as gevolg van die ewekansige toegang ons

719
00:30:22,080 --> 00:30:23,780
voorgestelde was 'n kenmerk van 'n skikking.

720
00:30:23,780 --> 00:30:28,570
Dus, in kort, uitzoeken wat die indeks
van Alice se naam is, wat is, in

721
00:30:28,570 --> 00:30:32,610
hierdie geval, is A, of laat ons net los
wat aan nul is, waar B is een en C is

722
00:30:32,610 --> 00:30:34,900
twee, besyfering dat uit
konstant tyd.

723
00:30:34,900 --> 00:30:38,510
Ek het net om te kyk na haar eerste brief,
uitzoeken waar nul is 'n

724
00:30:38,510 --> 00:30:40,460
skikking is ook konstante tyd.

725
00:30:40,460 --> 00:30:42,140
So tegnies dit is
soos twee stappe nou.

726
00:30:42,140 --> 00:30:43,330
Maar dit is nog steeds konstant.

727
00:30:43,330 --> 00:30:46,880
So ons noem dat die groot O van een, so ons het
ingevoeg Alice in hierdie tabel in

728
00:30:46,880 --> 00:30:48,440
konstante tyd.

729
00:30:48,440 --> 00:30:50,960
>> Maar natuurlik, ek word
naïef hier, reg?

730
00:30:50,960 --> 00:30:53,240
Wat as daar 'n Aaron in die klas?

731
00:30:53,240 --> 00:30:53,990
Of Alicia?

732
00:30:53,990 --> 00:30:57,230
Of enige ander name wat begin met
A. Waar gaan ons te sit

733
00:30:57,230 --> 00:31:00,800
daardie persoon, reg?

734
00:31:00,800 --> 00:31:03,420
Ek meen, nou is daar net drie
mense op die tafel, so miskien kan ons

735
00:31:03,420 --> 00:31:07,490
moet sit Aaron op plek
nul een twee drie.

736
00:31:07,490 --> 00:31:09,480
>> Reg, kan ek 'n hier.

737
00:31:09,480 --> 00:31:13,350
Maar dan, as ons probeer om Dawid te voeg in
hierdie lys, nie waar Dawid gaan?

738
00:31:13,350 --> 00:31:15,170
Nou ons stelsel begin breek
af, reg?

739
00:31:15,170 --> 00:31:19,210
Want nou David eindig hier
As Aaron is eintlik hier.

740
00:31:19,210 --> 00:31:23,060
En so nou hierdie hele idee van 'n
skoon data struktuur wat gee ons

741
00:31:23,060 --> 00:31:28,010
konstante tyd invoegings is nie meer
konstante tyd, want ek het om te

742
00:31:28,010 --> 00:31:31,240
kyk, o, o bliksem, iemand is reeds
op Alice se plek.

743
00:31:31,240 --> 00:31:35,320
>> Laat my ondersoek die res van hierdie data
struktuur, op soek na 'n plek om te sit

744
00:31:35,320 --> 00:31:37,130
iemand soos Aaron se naam.

745
00:31:37,130 --> 00:31:39,390
En so het dit ook begin
lineêre tyd te neem.

746
00:31:39,390 --> 00:31:42,710
Verder, as jy wil nou die te vind
Aaron in hierdie data struktuur, en jy

747
00:31:42,710 --> 00:31:45,430
gaan, en Aaron se naam is nie hier nie.

748
00:31:45,430 --> 00:31:47,960
Ideaal, jy wil net sê Aaron se
nie in die data struktuur.

749
00:31:47,960 --> 00:31:51,530
Maar as jy begin om ruimte vir
Aaron waar daar moes gewees het 'n D

750
00:31:51,530 --> 00:31:55,600
of 'n E, julle, die ergste geval, het om seker te maak
die hele data struktuur, in

751
00:31:55,600 --> 00:31:59,480
welke geval dit wentel in iets
lineêre in die grootte van die tabel.

752
00:31:59,480 --> 00:32:00,920
>> So alles reg is, sal ek dit regmaak.

753
00:32:00,920 --> 00:32:04,200
Die probleem hier is dat ek moes
26 elemente in die skikking.

754
00:32:04,200 --> 00:32:05,000
Laat my dit verander.

755
00:32:05,000 --> 00:32:06,010
Oeps.

756
00:32:06,010 --> 00:32:10,600
Laat my dit verander sodat eerder welsyn van
grootte 26 in totaal, kennis van die onderkant

757
00:32:10,600 --> 00:32:12,720
indeks gaan verander na n minus 1.

758
00:32:12,720 --> 00:32:16,610
As 26 is duidelik te klein is vir die mens se
name, want daar is duisende

759
00:32:16,610 --> 00:32:20,830
name van die wêreld, laat ons net maak
in 100 of 1000 of 10000.

760
00:32:20,830 --> 00:32:22,960
Laat ons net ken 'n baie meer ruimte.

761
00:32:22,960 --> 00:32:27,230
>> Wel, dit beteken nie noodwendig afneem
die waarskynlikheid dat ons nie sal twee

762
00:32:27,230 --> 00:32:31,510
mense met name wat begin met A, en
ja, jy gaan probeer om 'n te sit

763
00:32:31,510 --> 00:32:33,120
name op plek nul steeds.

764
00:32:33,120 --> 00:32:36,850
Hulle is nog steeds gaan om te bots, wat
beteken dat ons nog nodig het om 'n oplossing te sit

765
00:32:36,850 --> 00:32:41,020
Alice en Aaron en Alicia en ander
name wat begin met 'n elders.

766
00:32:41,020 --> 00:32:43,460
Maar hoe veel van 'n probleem is dit?

767
00:32:43,460 --> 00:32:46,870
Wat is die waarskynlikheid dat jy
het botsings in 'n data

768
00:32:46,870 --> 00:32:48,240
struktuur soos hierdie?

769
00:32:48,240 --> 00:32:52,570
>> Wel, laat my - ons sal terugkom
op die vraag hier.

770
00:32:52,570 --> 00:32:55,530
En kyk hoe ons kan
los dit die eerste keer.

771
00:32:55,530 --> 00:32:58,480
Laat my toe om hierdie voorstel hier.

772
00:32:58,480 --> 00:33:02,020
Wat ons nou net beskryf is 'n algoritme,
'n heuristiese genoem lineêre

773
00:33:02,020 --> 00:33:05,030
indringende waardeur, as jy probeer om te voeg
iets wat hier in hierdie data

774
00:33:05,030 --> 00:33:08,920
struktuur, wat genoem word 'n hash tafel,
en daar is geen plek oor nie, jy

775
00:33:08,920 --> 00:33:12,000
waarlik ondersoek die data struktuur
nagaan, is dit beskikbaar?

776
00:33:12,000 --> 00:33:13,430
Is dit beskikbaar is, is dit beskikbaar?

777
00:33:13,430 --> 00:33:13,980
Is dit beskikbaar?

778
00:33:13,980 --> 00:33:17,550
En toe dit uiteindelik, jy plaas die
naam wat jy oorspronklik bedoel

779
00:33:17,550 --> 00:33:19,370
elders op die plek.

780
00:33:19,370 --> 00:33:23,360
Maar in die ergste geval, die enigste plek
dalk die heel onderkant van die data wees

781
00:33:23,360 --> 00:33:25,090
struktuur, die einde van die skikking.

782
00:33:25,090 --> 00:33:30,130
>> So lineêre indringende, in die ergste geval,
wentel in 'n lineêre algoritme waar

783
00:33:30,130 --> 00:33:34,500
Aaron, as hy gebeur te word ingevoeg laaste
in hierdie data struktuur, kan hy

784
00:33:34,500 --> 00:33:39,540
bots met die eerste plek nie, maar
dan eindig deur slegte geluk aan die einde.

785
00:33:39,540 --> 00:33:43,940
Dit is dus nie 'n konstante
tyd heilige graal vir ons.

786
00:33:43,940 --> 00:33:47,650
Hierdie benadering van die inbring elemente in
'n data struktuur genaamd 'n gemors

787
00:33:47,650 --> 00:33:52,050
tafel lyk nie konstante tyd
ten minste nie in die algemene geval.

788
00:33:52,050 --> 00:33:54,000
Dit kan oorgaan in iets lineêre.

789
00:33:54,000 --> 00:33:56,970
>> So wat as ons los botsings
ietwat anders?

790
00:33:56,970 --> 00:34:00,740
So hier is 'n meer gesofistikeerde
nader aan wat nog

791
00:34:00,740 --> 00:34:02,800
bekend as 'n hash tafel.

792
00:34:02,800 --> 00:34:05,890
En deur hash, as 'n eenkant, wat
Ek bedoel is die indeks wat

793
00:34:05,890 --> 00:34:07,070
Ek verwys na vroeër.

794
00:34:07,070 --> 00:34:09,810
Om hash iets kan wees
beskou as 'n werkwoord.

795
00:34:09,810 --> 00:34:13,690
>> So as jy hash Alice is 'n naam,
'n hash funksie, om so te praat,

796
00:34:13,690 --> 00:34:14,710
moet terugkeer 'n nommer.

797
00:34:14,710 --> 00:34:18,199
In hierdie geval is nul as sy behoort aan
plek nul, een of sy behoort op

798
00:34:18,199 --> 00:34:20,000
plek een, en so meer.

799
00:34:20,000 --> 00:34:24,360
So my hash funksie tot dusver
super eenvoudige, net na die

800
00:34:24,360 --> 00:34:26,159
eerste letter in iemand se naam.

801
00:34:26,159 --> 00:34:29,090
Maar 'n hash funksie neem as
insette 'n stuk van data, 'n

802
00:34:29,090 --> 00:34:30,210
string, 'n int, wat ook al.

803
00:34:30,210 --> 00:34:32,239
En dit spoeg tipies 'n aantal.

804
00:34:32,239 --> 00:34:35,739
En dat die getal is waar dat die data
element behoort in 'n data struktuur

805
00:34:35,739 --> 00:34:37,800
bekend hier as 'n hash tafel.

806
00:34:37,800 --> 00:34:41,400
>> Dus net intuïtief, dit is 'n
effens ander konteks.

807
00:34:41,400 --> 00:34:44,170
Dit is eintlik verwys na 'n voorbeeld
waarby verjaarsdae, waar

808
00:34:44,170 --> 00:34:46,850
is daar dalk soveel as
31 dae in die maand.

809
00:34:46,850 --> 00:34:52,239
Maar wat het hierdie persoon besluit om te
doen in die geval van 'n botsing?

810
00:34:52,239 --> 00:34:55,304
Konteks nou geplaas word en nie 'n botsing van
name nie, maar 'n botsing van verjaarsdae,

811
00:34:55,304 --> 00:35:00,760
As twee mense het dieselfde verjaarsdag op
2 Oktober, byvoorbeeld.

812
00:35:00,760 --> 00:35:02,120
>> STUDENT: [onhoorbaar].

813
00:35:02,120 --> 00:35:05,010
>> Spreker 1: Ja, so hier het ons '
die benutting van geskakelde lyste.

814
00:35:05,010 --> 00:35:07,830
So dit lyk 'n bietjie anders
as ons het dit vroeër.

815
00:35:07,830 --> 00:35:10,790
Maar ons verskyn het om 'n skikking
op die linkerkant.

816
00:35:10,790 --> 00:35:13,230
Dit is een indeks, vir geen
spesifieke rede.

817
00:35:13,230 --> 00:35:14,630
Maar dit is nog steeds 'n skikking.

818
00:35:14,630 --> 00:35:16,160
Dit is 'n verskeidenheid van wysers.

819
00:35:16,160 --> 00:35:20,670
En elkeen van hierdie elemente, elk van
hierdie sirkels of houe - die streep

820
00:35:20,670 --> 00:35:23,970
verteenwoordig null - elk van hierdie
wysers is blykbaar verwys na

821
00:35:23,970 --> 00:35:25,730
wat data struktuur?

822
00:35:25,730 --> 00:35:26,890
'N geskakelde lys.

823
00:35:26,890 --> 00:35:30,530
>> So nou het ons die vermoë om te
harde kode in ons program

824
00:35:30,530 --> 00:35:32,010
die grootte van die tabel.

825
00:35:32,010 --> 00:35:35,360
In hierdie geval, ons weet daar is nooit
meer as 31 dae in 'n maand.

826
00:35:35,360 --> 00:35:38,480
So hard kodering 'n waarde soos 31 is
redelike in daardie konteks.

827
00:35:38,480 --> 00:35:42,700
In die konteks van die name, hard kodering
26 is nie onredelik nie om mense se

828
00:35:42,700 --> 00:35:46,340
name net begin met, byvoorbeeld,
die alfabet wat 'n deur Z.

829
00:35:46,340 --> 00:35:50,180
>> Ons kan inprop hulle almal in die data
struktuur so lank as wat, toe kry ons 'n

830
00:35:50,180 --> 00:35:55,330
botsing, het ons nie die name hier,
ons dink in plaas van hierdie selle

831
00:35:55,330 --> 00:36:00,270
nie as stringe self nie, maar as
verwysings na, byvoorbeeld, Alice.

832
00:36:00,270 --> 00:36:03,660
En dan Alice kan nog 'n wyser
na 'n ander naam begin met

833
00:36:03,660 --> 00:36:06,150
A. En Bob gaan eintlik oor hier.

834
00:36:06,150 --> 00:36:10,850
>> En as daar 'n ander naam begin
met B, hy beland hier.

835
00:36:10,850 --> 00:36:15,070
En so het elk van die elemente van hierdie
tafel twee, as ons ontwerp dat dit '

836
00:36:15,070 --> 00:36:17,350
bietjie meer slim -

837
00:36:17,350 --> 00:36:18,125
kom op -

838
00:36:18,125 --> 00:36:22,950
As ons ontwerp dat dit 'n bietjie meer
slim, word nou 'n aangepaste data

839
00:36:22,950 --> 00:36:27,720
struktuur, waar daar is geen harde limiet
op hoeveel elemente wat jy kan voeg

840
00:36:27,720 --> 00:36:30,700
in dit, want as jy nie '
'n botsing, dit is goed.

841
00:36:30,700 --> 00:36:34,690
Net voort te gaan en voeg dit te
wat ons gesien het 'n bietjie gelede was

842
00:36:34,690 --> 00:36:38,290
bekend as 'n geskakelde lys.

843
00:36:38,290 --> 00:36:39,690
>> Wel, laat ons breek vir net 'n oomblik.

844
00:36:39,690 --> 00:36:42,570
Wat is die waarskynlikheid van 'n botsing
in die eerste plek?

845
00:36:42,570 --> 00:36:45,480
Reg, miskien is ek oor dink, miskien
Ek is meer as Ingenieurswese Die probleem is,

846
00:36:45,480 --> 00:36:46,370
want jy weet wat?

847
00:36:46,370 --> 00:36:49,070
Ja, ek kan kom met 'n arbitrêre
voorbeelde uit die top van my kop soos

848
00:36:49,070 --> 00:36:52,870
Allison en Aaron, maar in werklikheid,
gegee 'n eenvormige verspreiding van

849
00:36:52,870 --> 00:36:56,990
insette, wat is 'n paar random invoegings
in 'n data struktuur, wat werklik

850
00:36:56,990 --> 00:36:58,580
die waarskynlikheid van 'n botsing?

851
00:36:58,580 --> 00:37:01,670
Wel blyk, dit is eintlik
super hoog.

852
00:37:01,670 --> 00:37:03,850
Laat my veralgemeen hierdie
probleem is as dit.

853
00:37:03,850 --> 00:37:08,890
>> So in 'n kamer van n CS50 studente, wat is
die waarskynlikheid dat ten minste

854
00:37:08,890 --> 00:37:11,010
twee studente in die kamer
het dieselfde verjaarsdag?

855
00:37:11,010 --> 00:37:13,346
So is daar wat. 'n paar Hund -

856
00:37:13,346 --> 00:37:16,790
200, 300 mense hier en verskeie
honderd mense by die huis vandag.

857
00:37:16,790 --> 00:37:20,670
So as jy wil om onsself te vra wat is
die waarskynlikheid van twee mense

858
00:37:20,670 --> 00:37:23,930
in hierdie kamer met dieselfde verjaarsdag,
ons kan uitvind dit uit.

859
00:37:23,930 --> 00:37:26,250
En ek eis eintlik is daar twee
mense met dieselfde verjaardag.

860
00:37:26,250 --> 00:37:29,560
>> Byvoorbeeld, nie almal
het verjaar vandag?

861
00:37:29,560 --> 00:37:31,340
Gister?

862
00:37:31,340 --> 00:37:32,590
Môre?

863
00:37:32,590 --> 00:37:35,980
Alle reg, sodat dit voel asof ek gaan
om hierdie 363 of so meer te doen

864
00:37:35,980 --> 00:37:39,500
keer om werklik uit te vind
As ons nie 'n botsing.

865
00:37:39,500 --> 00:37:42,350
Of ons kan net doen dit wiskundig
eerder as tediously

866
00:37:42,350 --> 00:37:43,200
om dit te doen.

867
00:37:43,200 --> 00:37:44,500
En stel die volgende.

868
00:37:44,500 --> 00:37:48,740
>> So ek stel voor dat ons die kan modelleer
waarskynlikheid van twee mense wat die

869
00:37:48,740 --> 00:37:55,320
dieselfde verjaarsdag as die waarskynlikheid van 1
minus die waarskynlikheid van niemand wat

870
00:37:55,320 --> 00:37:56,290
dieselfde verjaarsdag.

871
00:37:56,290 --> 00:37:59,960
So om dit te kry, en dit is net die
fancy manier van die skryf van hierdie, vir die

872
00:37:59,960 --> 00:38:03,090
eerste persoon in die kamer, het hy of sy
kan enige een van die moontlike

873
00:38:03,090 --> 00:38:07,370
verjaarsdae aanvaarding van 365 dae in die jaar,
Met apologie aan persone met

874
00:38:07,370 --> 00:38:08,760
die Februarie-29ste verjaardag.

875
00:38:08,760 --> 00:38:13,470
>> So het die eerste persoon in die kamer is gratis
enige aantal verjaarsdae te hê

876
00:38:13,470 --> 00:38:18,280
uit die 365 moontlikhede sodat
ons sal doen wat 365 gedeel deur 365,

877
00:38:18,280 --> 00:38:18,990
Dit is een.

878
00:38:18,990 --> 00:38:22,700
Die volgende persoon in die kamer, indien die doel
is 'n botsing te vermy, kan slegs

879
00:38:22,700 --> 00:38:26,460
sy of haar verjaardag op hoe
baie verskillende moontlike dae?

880
00:38:26,460 --> 00:38:27,610
364.

881
00:38:27,610 --> 00:38:31,430
So het die tweede termyn in hierdie uitdrukking is
wese doen wat wiskunde vir ons

882
00:38:31,430 --> 00:38:33,460
deur af te trek uit 'n moontlike dag.

883
00:38:33,460 --> 00:38:36,390
En dan is die volgende dag, die volgende dag, die
volgende dag af tot die totale aantal

884
00:38:36,390 --> 00:38:38,100
van die mense in die kamer.

885
00:38:38,100 --> 00:38:41,290
>> En as ons dan kyk, wat is dan
die waarskynlikheid nie van almal wat

886
00:38:41,290 --> 00:38:45,265
unieke verjaarsdae, maar weer 1 minus
dat, wat ons kry, is 'n uitdrukking

887
00:38:45,265 --> 00:38:47,810
wat kan baie denkbeeldig
lyk.

888
00:38:47,810 --> 00:38:50,330
Maar dit is meer interessant
om te kyk na visueel.

889
00:38:50,330 --> 00:38:55,120
Dit is 'n grafiek waar op die x-as
die aantal mense wat in die kamer, die

890
00:38:55,120 --> 00:38:56,180
aantal verjaarsdae.

891
00:38:56,180 --> 00:38:59,840
Op die y-as is die waarskynlikheid
van 'n botsing, twee mense

892
00:38:59,840 --> 00:39:01,230
wat dieselfde verjaarsdag.

893
00:39:01,230 --> 00:39:05,020
>> En die afhaal van die kurwe is
dat sodra jy 40 te hou

894
00:39:05,020 --> 00:39:11,110
studente nie, is jy op 'n 90% waarskynlikheid
combinatorically van twee

895
00:39:11,110 --> 00:39:13,550
mense of meer met
dieselfde verjaarsdag.

896
00:39:13,550 --> 00:39:18,600
En as jy een van 58 mense is dit te hou
byna 100% van 'n kans om die twee

897
00:39:18,600 --> 00:39:21,310
mense in die kamer gaan die te hê
dieselfde verjaarsdag, selfs al is daar

898
00:39:21,310 --> 00:39:26,650
365 of 366 moontlik emmers, en
Slegs 58 mense in die kamer.

899
00:39:26,650 --> 00:39:29,900
Net statisties jy geneig om te
kry botsings, wat in 'n kort

900
00:39:29,900 --> 00:39:31,810
motiveer hierdie bespreking.

901
00:39:31,810 --> 00:39:35,890
Dat selfs as ons fancy hier, en
begin met die kettings, ons is nog steeds

902
00:39:35,890 --> 00:39:36,950
gaan botsings te hê.

903
00:39:36,950 --> 00:39:42,710
>> Sodat lei tot die vraag, wat is die
koste om invoegings en delesies

904
00:39:42,710 --> 00:39:44,850
in 'n data struktuur soos hierdie?

905
00:39:44,850 --> 00:39:46,630
Wel, laat my stel -

906
00:39:46,630 --> 00:39:51,570
en laat my terug te gaan na die skerm oor
hier - as ons met n elemente in die

907
00:39:51,570 --> 00:39:56,330
lys, so as ons probeer om te voeg
n elemente, en ons het

908
00:39:56,330 --> 00:39:58,050
hoeveel totale emmers?

909
00:39:58,050 --> 00:40:03,450
Kom ons sê 31 totale emmers
in die geval van verjaarsdae.

910
00:40:03,450 --> 00:40:09,240
Wat is die maksimum lengte van een
van hierdie kettings potensieel?

911
00:40:09,240 --> 00:40:12,670
>> As weer daar is 31 moontlike
verjaarsdae in 'n gegewe maand.

912
00:40:12,670 --> 00:40:14,580
En ons is net geplant almal -

913
00:40:14,580 --> 00:40:15,580
eintlik is dit 'n stupid voorbeeld.

914
00:40:15,580 --> 00:40:16,960
Kom ons doen 26 plaas.

915
00:40:16,960 --> 00:40:20,890
So as eintlik mense wie se name
begin met 'n deur Z, waardeur

916
00:40:20,890 --> 00:40:22,780
ons 26 moontlikhede.

917
00:40:22,780 --> 00:40:25,920
En ons is met behulp van 'n data struktuur soos
die een wat ons nou net gesien het, waardeur ons 'n

918
00:40:25,920 --> 00:40:30,210
'n verskeidenheid van wysers, wat elk
dui op 'n geskakelde lys waar die

919
00:40:30,210 --> 00:40:32,360
eerste lys is almal
met die naam Alice.

920
00:40:32,360 --> 00:40:35,770
Die tweede lys is elke met die
noem wat begin met A, begin

921
00:40:35,770 --> 00:40:36,980
met B, en so meer.

922
00:40:36,980 --> 00:40:41,020
>> Wat is die waarskynlike lengte van elk van
die lyste indien ons aanvaar 'n mooi skoon

923
00:40:41,020 --> 00:40:45,410
verspreiding van name 'n deur Z
oor die hele data struktuur?

924
00:40:45,410 --> 00:40:50,210
Daar is 'n volk in die data struktuur
gedeel deur 26, as hulle mooi

925
00:40:50,210 --> 00:40:52,110
versprei oor die hele
data struktuur.

926
00:40:52,110 --> 00:40:54,970
So het die lengte van elk van hierdie
kettings is n gedeel deur 26.

927
00:40:54,970 --> 00:40:57,380
Maar in 'n groot O-notasie, wat is dit?

928
00:40:57,380 --> 00:41:00,100

929
00:41:00,100 --> 00:41:02,440
Wat is dit regtig?

930
00:41:02,440 --> 00:41:04,150
So dit is regtig net n, reg?

931
00:41:04,150 --> 00:41:06,620
Want ons het gesê in die verlede,
dat ugh jy deel deur 26.

932
00:41:06,620 --> 00:41:08,710
Ja, in werklikheid is dit is vinniger.

933
00:41:08,710 --> 00:41:12,720
Maar in teorie, is dit nie fundamenteel
alles wat vinniger.

934
00:41:12,720 --> 00:41:16,040
>> So lyk ons ​​nie te wees nie alles wat veel
nader aan die heilige graal.

935
00:41:16,040 --> 00:41:17,750
Trouens, dit is net lineêre tyd.

936
00:41:17,750 --> 00:41:20,790
Heck, op hierdie punt, hoekom doen ons nie
gebruik net een groot gekoppel lys?

937
00:41:20,790 --> 00:41:23,510
Hoekom doen ons nie net gebruik om 'n groot
verskeidenheid van die name van die stoor

938
00:41:23,510 --> 00:41:25,010
almal in die kamer?

939
00:41:25,010 --> 00:41:28,280
Wel, is daar nog iets
dwingende oor 'n hash tafel?

940
00:41:28,280 --> 00:41:30,810
Is daar nog iets dwingende
oor 'n data struktuur

941
00:41:30,810 --> 00:41:33,940
wat lyk soos hierdie?

942
00:41:33,940 --> 00:41:35,182
Dit.

943
00:41:35,182 --> 00:41:37,050
>> STUDENT: [onhoorbaar].

944
00:41:37,050 --> 00:41:39,840
>> Spreker 1: Right, en weer is dit net
'n lineêre tyd algoritme, en 'n

945
00:41:39,840 --> 00:41:42,780
lineêre tyd data struktuur, hoekom het ek nie
net slaan almal se naam in 'n groot

946
00:41:42,780 --> 00:41:44,210
skikking, of in 'n groot gekoppel lys?

947
00:41:44,210 --> 00:41:47,010
En ophou om CS soveel harder
as wat dit moet wees?

948
00:41:47,010 --> 00:41:49,600

949
00:41:49,600 --> 00:41:53,190
Wat is dwingende oor hierdie, selfs
al het ek gekrap dit uit?

950
00:41:53,190 --> 00:41:54,930
>> STUDENT: [onhoorbaar].

951
00:41:54,930 --> 00:41:57,040
>> Spreker 1: invoegings is nie?

952
00:41:57,040 --> 00:41:58,140
Duur nie.

953
00:41:58,140 --> 00:42:03,390
So invoegings potensieel kan nog steeds
wees konstante tyd, selfs as jou data

954
00:42:03,390 --> 00:42:07,910
struktuur lyk soos hierdie, 'n verskeidenheid van
wysers, is elk van wat dui op

955
00:42:07,910 --> 00:42:09,550
potensieel 'n geskakelde lys.

956
00:42:09,550 --> 00:42:15,220
Hoe kan jy bereik konstante
tyd inplaas van name?

957
00:42:15,220 --> 00:42:16,280
Plak dit in die voorkant, reg?

958
00:42:16,280 --> 00:42:19,290
>> As ons offer 'n ontwerp doel van
vroeër, waar ons wou hou

959
00:42:19,290 --> 00:42:22,650
elkeen se naam, byvoorbeeld, gesorteer,
of al die nommers wat op die verhoog gesorteer,

960
00:42:22,650 --> 00:42:25,020
veronderstel dat ons 'n
ongesorteerde gekoppel lys.

961
00:42:25,020 --> 00:42:29,960
Dit kos ons net een of twee stappe,
soos in die geval van Ben en Brian

962
00:42:29,960 --> 00:42:32,750
Vroeër, in te voeg 'n element by
die begin van die lys.

963
00:42:32,750 --> 00:42:36,090
So as ons nie omgee sorteer al
van die name wat begin met A of al

964
00:42:36,090 --> 00:42:39,660
die name wat begin met B, kan ons nog
bereik konstante tyd te voeg.

965
00:42:39,660 --> 00:42:43,900
Nou kyk op Alice of Bob of enige naam
meer algemeen is nog wat?

966
00:42:43,900 --> 00:42:48,100
Dit is 'n groot O van n gedeel deur 26, in die
ideale geval waar almal is eenvormig

967
00:42:48,100 --> 00:42:51,190
versprei, waar daar soveel A se
as daar Z's, wat waarskynlik

968
00:42:51,190 --> 00:42:52,220
onrealisties.

969
00:42:52,220 --> 00:42:53,880
Maar dit is nog steeds lineêre.

970
00:42:53,880 --> 00:42:57,120
>> Maar hier is ons, ons kom terug na die punt
van asimptotiese notasie om

971
00:42:57,120 --> 00:42:58,600
teoreties waar.

972
00:42:58,600 --> 00:43:02,960
Maar in die werklike wêreld, as ek beweer dat
my program kan iets doen 26 keer

973
00:43:02,960 --> 00:43:06,210
vinniger as joune, wie se program
gaan jy verkies om met behulp van?

974
00:43:06,210 --> 00:43:09,660
Joune of myne, wat
is 26 keer vinniger?

975
00:43:09,660 --> 00:43:14,320
Realisties, die persoon wie is 26
keer vinniger, selfs al is teoreties

976
00:43:14,320 --> 00:43:18,790
ons algoritmes in dieselfde
asimptotiese loop van die tyd.

977
00:43:18,790 --> 00:43:20,940
>> Laat my stel 'n ander
oplossing geheel en al.

978
00:43:20,940 --> 00:43:24,380
En as dit nie blaas nie jou gedagtes,
Ons is uit die data strukture.

979
00:43:24,380 --> 00:43:27,420
So dit is dit 'n Trie -

980
00:43:27,420 --> 00:43:28,520
soort van 'n stupid naam.

981
00:43:28,520 --> 00:43:32,880
Dit kom van Retrievals, en die woord
gespel Trie, t-r-i-e, as gevolg van

982
00:43:32,880 --> 00:43:34,450
Natuurlik herwinning klink soos Trie.

983
00:43:34,450 --> 00:43:36,580
Maar dit is die geskiedenis
van die woord Trie.

984
00:43:36,580 --> 00:43:40,980
>> So 'n Trie is inderdaad 'n soort van die boom,
en dit is ook 'n toneelstuk op daardie woord.

985
00:43:40,980 --> 00:43:46,330
En selfs al is jy kan baie dit nie sien nie
met hierdie visualisering, 'n tydstip waarop 'n

986
00:43:46,330 --> 00:43:50,790
boom gestruktureer is, soos 'n familie boom met
'n voorloper op die top en baie

987
00:43:50,790 --> 00:43:54,530
van kleinkinders en agterkleinkinders
as blare aan die onderkant.

988
00:43:54,530 --> 00:43:58,100
Maar elke knoop in 'n tydstip waarop 'n skikking.

989
00:43:58,100 --> 00:44:00,680
En dit is in 'n skikking - en laat
eenvoudig vir 'n oomblik - dit is 'n

990
00:44:00,680 --> 00:44:04,600
skikking, in hierdie geval, die grootte 26, waar
elke knoop weer 'n skikking van die grootte

991
00:44:04,600 --> 00:44:09,000
26, waar die nulde element in daardie
verskeidenheid verteenwoordig 'n, en die laaste

992
00:44:09,000 --> 00:44:11,810
element in elke sodanige
verskeidenheid verteenwoordig Z.

993
00:44:11,810 --> 00:44:15,520
>> So ek stel voor, dan, dat hierdie data
struktuur, bekend as 'n Trie, kan

994
00:44:15,520 --> 00:44:17,600
gebruik ook woorde op te slaan.

995
00:44:17,600 --> 00:44:21,740
Ons het 'n oomblik gelede hoe ons kon slaan
woorde, of in hierdie geval name, en ons

996
00:44:21,740 --> 00:44:25,440
vroeër gesien het hoe ons getalle kan stoor,
maar as ons fokus op name of snare

997
00:44:25,440 --> 00:44:27,460
hier, sien wat is interessant.

998
00:44:27,460 --> 00:44:32,210
Ek beweer dat die naam Maxwell is
binnekant van die data struktuur.

999
00:44:32,210 --> 00:44:33,730
Waar sien jy Maxwell?

1000
00:44:33,730 --> 00:44:35,140
>> STUDENT: [onhoorbaar].

1001
00:44:35,140 --> 00:44:36,240
>> Spreker 1: Op die linkerkant.

1002
00:44:36,240 --> 00:44:39,910
So, wat is interessant met hierdie data
struktuur is eerder as die winkel

1003
00:44:39,910 --> 00:44:46,200
string M-A-X-W-E-L-L agteroorskuisstreep nul, al
contiguously, wat jy plaas nie

1004
00:44:46,200 --> 00:44:46,890
volg.

1005
00:44:46,890 --> 00:44:50,510
As dit is 'n Trie soos data struktuur,
elk van wie se knope is weer 'n skikking,

1006
00:44:50,510 --> 00:44:54,650
en jy wil Maxwell te slaan, moet jy eers
indeks en so die wortel se knoop, sodat

1007
00:44:54,650 --> 00:44:57,810
te spreek, het die boonste knoop,
by plek M, regs, so

1008
00:44:57,810 --> 00:44:59,160
rofweg in die middel.

1009
00:44:59,160 --> 00:45:03,740
En dan van daar af, jy volg 'n
wyser na 'n kind nodes, om so te praat.

1010
00:45:03,740 --> 00:45:06,150
So in die stamboom sin,
volg jy dit afwaarts.

1011
00:45:06,150 --> 00:45:09,030
En dit lei jou na 'n ander node
aan die linkerkant is daar, wat

1012
00:45:09,030 --> 00:45:10,540
net nog 'n skikking.

1013
00:45:10,540 --> 00:45:14,710
>> En dan as jy wil Maxwell te slaan,
vind jy die wyser wat verteenwoordig

1014
00:45:14,710 --> 00:45:16,430
A, wat is hierdie een hier.

1015
00:45:16,430 --> 00:45:17,840
Dan gaan jy na die volgende knoop.

1016
00:45:17,840 --> 00:45:20,100
En kennis - dit is die rede waarom die foto's
'n bietjie mislei -

1017
00:45:20,100 --> 00:45:21,990
hierdie knoop lyk super klein.

1018
00:45:21,990 --> 00:45:26,050
Maar aan die regterkant van hierdie is Y en Z.
Dit is net die skrywer het kapt die

1019
00:45:26,050 --> 00:45:27,630
prentjie sodat jy eintlik
sien dinge.

1020
00:45:27,630 --> 00:45:30,400
Andersins hierdie foto
sou wees uiters wyd.

1021
00:45:30,400 --> 00:45:36,180
So nou kan jy indeks in plek X, dan
W, dan E, dan is L, dan L. Dan wat is

1022
00:45:36,180 --> 00:45:37,380
hierdie nuuskierigheid?

1023
00:45:37,380 --> 00:45:41,250
>> Wel, as ons die gebruik van hierdie soort van nuwe
neem oor hoe om 'n string op te slaan in 'n

1024
00:45:41,250 --> 00:45:44,500
data struktuur, het jy nog nodig het om te
wese gaan af in die data

1025
00:45:44,500 --> 00:45:47,250
struktuur wat 'n woord hier eindig.

1026
00:45:47,250 --> 00:45:50,830
Met ander woorde, elk van hierdie nodes
een of ander manier het om te onthou dat ons

1027
00:45:50,830 --> 00:45:53,500
eintlik gevolg van al hierdie wenke
en laat 'n bietjie

1028
00:45:53,500 --> 00:45:58,370
brood krummel aan die onderkant hier van hierdie
struktuur M-A-X-W-E-L-L aan te dui is

1029
00:45:58,370 --> 00:46:00,230
inderdaad in hierdie data struktuur.

1030
00:46:00,230 --> 00:46:02,040
>> So ons kan dit doen as volg.

1031
00:46:02,040 --> 00:46:06,810
Elkeen van die nodes in die prentjie wat ons net
gesien het, het een, 'n skikking van grootte 27.

1032
00:46:06,810 --> 00:46:10,550
En dit is nou 27, want in p stel ses,
ons sal eintlik gee jou 'n toespraak,

1033
00:46:10,550 --> 00:46:13,590
sodat ons kan name soos O'Reilly
en ander met apostrofs.

1034
00:46:13,590 --> 00:46:14,820
Maar dieselfde idee.

1035
00:46:14,820 --> 00:46:17,710
Elkeen van hierdie elemente in die
verskeidenheid punte na 'n struct

1036
00:46:17,710 --> 00:46:19,320
knoop, sodat net 'n knoop.

1037
00:46:19,320 --> 00:46:21,430
So dit is baie herinner
van ons gekoppelde lys.

1038
00:46:21,430 --> 00:46:24,550
>> En dan het ek 'n Boole, wat ek sal
noem woord, wat net gaan om te wees

1039
00:46:24,550 --> 00:46:29,120
waar as 'n woord eindig op hierdie
nodus in die boom.

1040
00:46:29,120 --> 00:46:32,870
Dit verteenwoordig effektief die klein
driehoek het ons 'n oomblik gelede.

1041
00:46:32,870 --> 00:46:37,190
So as 'n woord eindig op daardie knoop in die
boom, sal die woord veld waar te wees,

1042
00:46:37,190 --> 00:46:41,990
wat konseptueel kontrole af, of
ons is die opstel van hierdie driehoek, ja daar

1043
00:46:41,990 --> 00:46:44,080
is 'n woord hier.

1044
00:46:44,080 --> 00:46:45,120
>> So dit is 'n Trie.

1045
00:46:45,120 --> 00:46:48,540
En nou is die vraag, wat
is sy loop van die tyd?

1046
00:46:48,540 --> 00:46:49,930
Is dit groot O van n?

1047
00:46:49,930 --> 00:46:51,410
Is dit iets anders?

1048
00:46:51,410 --> 00:46:57,330
Wel, as jy het n 'name in die data
struktuur, Maxwell om net een van

1049
00:46:57,330 --> 00:47:02,330
hulle, wat is die loop van die tyd van
voeg of te vind Maxwell?

1050
00:47:02,330 --> 00:47:06,230

1051
00:47:06,230 --> 00:47:09,050
Wat is die loop van die tyd
inbring van Maxwell?

1052
00:47:09,050 --> 00:47:11,740
As daar 'n ander name
reeds in die tabel?

1053
00:47:11,740 --> 00:47:12,507
Ja?

1054
00:47:12,507 --> 00:47:15,429
>> STUDENT: [onhoorbaar].

1055
00:47:15,429 --> 00:47:17,550
>> Spreker 1: Ja, dit is die lengte
van die naam, reg?

1056
00:47:17,550 --> 00:47:24,420
So M-a-x-w-e-l-l so dit voel soos hierdie
algoritme is 'n groot O van sewe.

1057
00:47:24,420 --> 00:47:26,580
Nou, natuurlik, die naam
sal wissel in lengte.

1058
00:47:26,580 --> 00:47:27,380
Miskien is dit 'n kort naam.

1059
00:47:27,380 --> 00:47:28,600
Miskien is dit 'n langer naam.

1060
00:47:28,600 --> 00:47:33,390
Maar wat is die sleutel hier is dat
dit is 'n konstante getal is.

1061
00:47:33,390 --> 00:47:36,810
En miskien is dit nie regtig konstant,
maar God, as realisties, in 'n

1062
00:47:36,810 --> 00:47:41,570
woordeboek, daar is waarskynlik 'n beperking
op die aantal letters in 'n

1063
00:47:41,570 --> 00:47:43,820
persoon se naam in 'n spesifieke land.

1064
00:47:43,820 --> 00:47:46,940
>> En so kan ons aanvaar dat
waarde 'n konstante is.

1065
00:47:46,940 --> 00:47:47,750
Ek weet nie wat dit is.

1066
00:47:47,750 --> 00:47:50,440
Dit is waarskynlik groter as
ons dink dit is.

1067
00:47:50,440 --> 00:47:52,720
Want daar is altyd 'n hoek
geval met 'n gek lang naam.

1068
00:47:52,720 --> 00:47:56,360
So kom ons noem dit k, maar dit is nog steeds 'n
konstante vermoedelik, want elke

1069
00:47:56,360 --> 00:48:00,190
naam in die wêreld, ten minste in 'n
bepaalde land, is dat lengte of

1070
00:48:00,190 --> 00:48:01,780
korter, so dit is 'n konstante.

1071
00:48:01,780 --> 00:48:04,490
Maar toe het ons iets gesê het is 'n groot
O van 'n konstante waarde, wat is dit

1072
00:48:04,490 --> 00:48:07,760
regtig gelykstaande aan?

1073
00:48:07,760 --> 00:48:10,420
Dit is regtig dieselfde ding
gesê konstante tyd.

1074
00:48:10,420 --> 00:48:11,530
>> Nou is ons 'n soort van bedrog, reg?

1075
00:48:11,530 --> 00:48:15,340
Ons is soort van gebruik te maak van 'n teorie
hier om te sê dat goed, einde van k is

1076
00:48:15,340 --> 00:48:17,450
regtig net om van die een,
en dit is konstante tyd.

1077
00:48:17,450 --> 00:48:18,200
Maar dit is regtig nie.

1078
00:48:18,200 --> 00:48:22,550
Omdat die sleutel insig hier is dat
As ons n 'name reeds in hierdie

1079
00:48:22,550 --> 00:48:26,010
data struktuur, en ons insetsel Maxwell,
is die bedrag van die tyd wat dit neem om ons te

1080
00:48:26,010 --> 00:48:29,530
voeg Maxwell aan alle geaffekteerde
deur hoeveel ander mense

1081
00:48:29,530 --> 00:48:31,100
is in die data struktuur?

1082
00:48:31,100 --> 00:48:31,670
Lyk nie te wees nie.

1083
00:48:31,670 --> 00:48:36,280
As ek 'n miljard meer elemente aan hierdie
Trie, en voeg dan Maxwell, is

1084
00:48:36,280 --> 00:48:38,650
Hy ten alle geraak?

1085
00:48:38,650 --> 00:48:39,050
No

1086
00:48:39,050 --> 00:48:42,950
En dit is in teenstelling met enige van die dag data
strukture wat ons tot dusver gesien het, waar

1087
00:48:42,950 --> 00:48:46,820
die loop van die tyd van jou algoritme
heeltemal onafhanklik van hoeveel

1088
00:48:46,820 --> 00:48:51,430
dinge is of nie reeds
in die data struktuur.

1089
00:48:51,430 --> 00:48:54,650
>> En so met hierdie bied jy is nou 'n
geleentheid vir p stel ses, wat sal

1090
00:48:54,650 --> 00:48:58,310
weer betrek die uitvoering van jou eie
speltoetser, lees in 150000

1091
00:48:58,310 --> 00:49:01,050
woorde, hoe om die beste wat te stoor
is nie noodwendig voor die hand liggend.

1092
00:49:01,050 --> 00:49:04,030
En al het ek daarna gestreef om uit te vind
die heilige graal, ek doen nie

1093
00:49:04,030 --> 00:49:05,330
beweer dat 'n Trie is.

1094
00:49:05,330 --> 00:49:09,810
In werklikheid, 'n hash tafel kan baie goed
blyk te wees baie meer doeltreffend.

1095
00:49:09,810 --> 00:49:10,830
Maar dit is net -

1096
00:49:10,830 --> 00:49:14,620
dit is net een van die ontwerp besluite te neem
jy sal hê om te maak.

1097
00:49:14,620 --> 00:49:18,920
>> Maar in die sluiting van Kom ons neem 50 of so
sekondes 'n blik op wat lê te neem

1098
00:49:18,920 --> 00:49:22,190
voor volgende week en buite ons oorgang
van hierdie opdrag lyn

1099
00:49:22,190 --> 00:49:26,220
wêreld as C programme dinge web
gebaseer en tale soos PHP en

1100
00:49:26,220 --> 00:49:30,350
JavaScript en die internet self,
protokolle soos HTTP, wat jy het

1101
00:49:30,350 --> 00:49:32,870
vanselfsprekend vir die jaar
nou, en getikte meeste elke

1102
00:49:32,870 --> 00:49:34,440
dag, miskien, of gesien het.

1103
00:49:34,440 --> 00:49:37,420
En ons sal begin om te skil terug die
lae van wat is die internet.

1104
00:49:37,420 --> 00:49:40,650
En wat is die kode wat
onderlê vandag se gereedskap.

1105
00:49:40,650 --> 00:49:43,230
So 50 sekondes van hierdie teaser hier.

1106
00:49:43,230 --> 00:49:46,570
Ek gee jou Warriors van die Net.

1107
00:49:46,570 --> 00:49:51,370
>> [Video speel]

1108
00:49:51,370 --> 00:49:56,764
>> -Hy het gekom met 'n boodskap.

1109
00:49:56,764 --> 00:50:00,687
Met 'n protokol al sy eie.

1110
00:50:00,687 --> 00:50:13,370

1111
00:50:13,370 --> 00:50:19,780
Hy het gekom om 'n wêreld van wrede firewalls,
onverskillige routers, en gevare ver

1112
00:50:19,780 --> 00:50:22,600
erger as die dood.

1113
00:50:22,600 --> 00:50:23,590
Hy is vinnig.

1114
00:50:23,590 --> 00:50:25,300
Hy is sterk.

1115
00:50:25,300 --> 00:50:27,700
Hy is TCPIP.

1116
00:50:27,700 --> 00:50:30,420
En hy het jou adres.

1117
00:50:30,420 --> 00:50:32,920

1118
00:50:32,920 --> 00:50:34,590
Warriors van die Net.

1119
00:50:34,590 --> 00:50:35,290
>> [Einde video-vertoning]

1120
00:50:35,290 --> 00:50:38,070
>> Spreker 1: Dit is hoe die internet
sal werk as van volgende week.

1121
00:50:38,070 --> 00:50:40,406