1
00:00:00,000 --> 00:00:00,500

2
00:00:00,500 --> 00:00:11,137
[Musiikki soi]

3
00:00:11,137 --> 00:00:12,220
DAVID J. MALAN: Okei.

4
00:00:12,220 --> 00:00:13,950
Tämä on CS50.

5
00:00:13,950 --> 00:00:18,560
Tämä on viikolla viisi jatkui, ja me
on hyviä uutisia ja huonoja uutisia.

6
00:00:18,560 --> 00:00:21,140
Niin hyvä uutinen on, että CS50
lanseeraa tänä perjantaina.

7
00:00:21,140 --> 00:00:24,430
Jos haluat liittyä meihin,
suunnata tavallista URL-osoite tähän.

8
00:00:24,430 --> 00:00:28,670
Vielä parempi uutinen, ei luentoa
Ensi maanantaina 13. päivä.

9
00:00:28,670 --> 00:00:31,970
Hieman vähemmän parempi uutinen,
tietokilpailu nolla on ensi keskiviikkona.

10
00:00:31,970 --> 00:00:33,840
Lisätietoja saa
löytää tähän URL-osoite tähän.

11
00:00:33,840 --> 00:00:36,340
Ja parin seuraavan päivän
me voidaan täydentäviä tehtäviä

12
00:00:36,340 --> 00:00:39,234
suhteen huoneita
että olemme pidätetään.

13
00:00:39,234 --> 00:00:41,400
Parempi uutinen on, että siellä tulee
olla kurssin laajuinen tarkastelu

14
00:00:41,400 --> 00:00:43,570
istunto tulevana
Maanantaina illalla.

15
00:00:43,570 --> 00:00:46,270
Pysy kuulolla kurssin
verkkosivuilla sijainti ja yksityiskohdat.

16
00:00:46,270 --> 00:00:49,290
Kohdat, vaikka se on
loma, tapaa myös samoin.

17
00:00:49,290 --> 00:00:50,490

18
00:00:50,490 --> 00:00:52,940
Paras uutinen, luento ensi perjantaina.

19
00:00:52,940 --> 00:00:56,220
Joten tämä on perinne meillä
on, kuten per oppimäärän.

20
00:00:56,220 --> 00:00:58,100
Vain-- se tulee olemaan mahtavaa.

21
00:00:58,100 --> 00:01:02,510
Näet asioita, kuten
vakioaikavälein tietorakenteita

22
00:01:02,510 --> 00:01:04,730
ja hash taulukoita ja puita ja yrittää.

23
00:01:04,730 --> 00:01:07,150
Ja me puhumme syntymäpäivä ongelmia.

24
00:01:07,150 --> 00:01:09,440
Läjän tavaraa
odottaa ensi perjantaina.

25
00:01:09,440 --> 00:01:11,212

26
00:01:11,212 --> 00:01:12,200
OK.

27
00:01:12,200 --> 00:01:13,190
Oli miten oli.

28
00:01:13,190 --> 00:01:17,080
>> Niin muistaa, että olemme olleet
Keskityn tähän kuvan siitä, mitä on

29
00:01:17,080 --> 00:01:18,980
sisällä myös tietokoneen muistiin.

30
00:01:18,980 --> 00:01:22,875
Joten muistin tai RAM on, jos ohjelmat
olemassa, kun käytät niitä.

31
00:01:22,875 --> 00:01:25,215
Jos kaksoisnapsautat
ikoni ajaa jotain ohjelmaa

32
00:01:25,215 --> 00:01:27,520
tai kaksoisnapsauta
kuvake avaa joitakin tiedosto,

33
00:01:27,520 --> 00:01:30,430
se ladataan kiintolevyn
ajaa tai SSD-asemalla

34
00:01:30,430 --> 00:01:34,190
RAM, Random Access Memory, jossa
se elää kunnes virta katkeaa,

35
00:01:34,190 --> 00:01:36,700
kannettavan tietokoneen kansi suljetaan,
tai lopetat ohjelman.

36
00:01:36,700 --> 00:01:38,960
>> Nyt kun muisti, ja
joka luultavasti on

37
00:01:38,960 --> 00:01:41,950
1 gigatavu näinä päivinä, 2
gigatavua, tai jopa enemmän,

38
00:01:41,950 --> 00:01:44,420
on yleensä vahvistetut
tietyn ohjelman

39
00:01:44,420 --> 00:01:47,170
tämäntyyppiseen suorakaiteen
käsitteellinen malli

40
00:01:47,170 --> 00:01:50,860
jolloin meillä on pino alareunassa
ja joukko muita juttuja yläreunassa.

41
00:01:50,860 --> 00:01:53,140
Asia huipulla
olemme nähneet tätä kuvaa

42
00:01:53,140 --> 00:01:55,670
ennen mutta ei koskaan puhunut
on ns tekstin segmentin.

43
00:01:55,670 --> 00:01:58,419
Teksti segmentti on vain hieno tapa
sanoa nollia ja ykkösiä, että

44
00:01:58,419 --> 00:02:01,150
säveltää todellista käännetty ohjelma.

45
00:02:01,150 --> 00:02:03,910
>> Joten kun kaksoisnapsautat
Microsoft Word Macin tai PC: n,

46
00:02:03,910 --> 00:02:08,030
tai kun suoritetaan piste slash Mario
Linux-tietokone teidän pääteikkunaa

47
00:02:08,030 --> 00:02:12,460
nollia ja ykkösiä, jotka muodostavat
Sana tai Mario varastoidaan väliaikaisesti

48
00:02:12,460 --> 00:02:16,610
tietokoneen RAM ns
tekstisegmentin tietyn ohjelman.

49
00:02:16,610 --> 00:02:19,080
Alla, että menee alustettu
ja alustamatonta tiedot.

50
00:02:19,080 --> 00:02:22,655
Tämä on tavaraa kuten globaaleja muuttujia,
että emme ole käytetty monia,

51
00:02:22,655 --> 00:02:24,910
mutta toisinaan olemme
oli yleismuuttujat

52
00:02:24,910 --> 00:02:28,819
tai staattisesti määrätty jouset että
on koodattu sanoja kuten "hei"

53
00:02:28,819 --> 00:02:31,860
joita ei ole otettu sisään käyttäjältä
jotka on koodattu ohjelmaan.

54
00:02:31,860 --> 00:02:34,230
>> Nyt alas alareunassa me
on ns pino.

55
00:02:34,230 --> 00:02:37,665
Ja pino tähän asti olemme olleet
käyttäen millaisia ​​tarkoituksiin?

56
00:02:37,665 --> 00:02:39,706

57
00:02:39,706 --> 00:02:40,997
Mitä pino käytetty?

58
00:02:40,997 --> 00:02:41,160
Joo?

59
00:02:41,160 --> 00:02:42,070
>> Yleisö: toiminnot.

60
00:02:42,070 --> 00:02:43,320
>> DAVID J. MALAN: For toimintoja?

61
00:02:43,320 --> 00:02:44,980
Missä mielessä funktioiden?

62
00:02:44,980 --> 00:02:48,660
>> Yleisö: Kun soitat toiminto,
argumentit kopioidaan pinoon.

63
00:02:48,660 --> 00:02:49,660
>> DAVID J. MALAN: Aivan.

64
00:02:49,660 --> 00:02:52,650
Kun soitat toiminto, sen
argumentit kopioidaan pinoon.

65
00:02:52,650 --> 00:02:56,330
Joten kaikki X: n tai Y: n tai: n tai B: n
että olet meneviä toiminto

66
00:02:56,330 --> 00:02:58,680
tilapäisesti laittaa
ns pino,

67
00:02:58,680 --> 00:03:02,000
aivan kuten yksi Annenberg
ruokasali tarjottimet, ja myös asioita,

68
00:03:02,000 --> 00:03:03,190
kuten paikallisia muuttujia.

69
00:03:03,190 --> 00:03:06,290
Jos foo toiminto tai sivutustilan
toiminto on paikallisia muuttujia,

70
00:03:06,290 --> 00:03:08,602
kuten lämpötila, nämä kaksi
päätyvät pinoon.

71
00:03:08,602 --> 00:03:11,560
Nyt emme puhu liikaa
heitä, mutta nämä ympäristömuuttujat

72
00:03:11,560 --> 00:03:15,690
alareunassa näimme taas sitten kun
Olin futzing näppäimistöllä yksi päivä

73
00:03:15,690 --> 00:03:20,050
ja aloin päästä asioita
kuten argv 100 tai argv 1000,

74
00:03:20,050 --> 00:03:22,320
vain elements-- Unohdan
numbers-- mutta että

75
00:03:22,320 --> 00:03:24,330
ei pitänyt käsiksi minuun.

76
00:03:24,330 --> 00:03:26,581
Aloimme nähdä joitakin
outoja symbolit ruudulla.

77
00:03:26,581 --> 00:03:28,330
Ne olivat niin sanottuja
Ympäristömuuttujien

78
00:03:28,330 --> 00:03:32,390
kuten yleiset asetukset minun
ohjelma tai tietokoneeseeni, ei

79
00:03:32,390 --> 00:03:37,090
liity äskettäin
vika, josta keskustelimme,

80
00:03:37,090 --> 00:03:39,670
Shellshock, joka on ollut
vaivaavat melkoisesti tietokoneita.

81
00:03:39,670 --> 00:03:42,960
>> Nyt lopuksi nykypäivän keskittyy
me lopulta kasaan.

82
00:03:42,960 --> 00:03:44,864
Tämä on toinen kimpale muistia.

83
00:03:44,864 --> 00:03:47,030
Ja pohjimmiltaan kaikki tämä
muisti on samat jutut.

84
00:03:47,030 --> 00:03:48,040
Se on sama kone.

85
00:03:48,040 --> 00:03:49,956
Olemme vain eräänlainen
hoitoon eri klustereiden

86
00:03:49,956 --> 00:03:51,460
tavujen eri tarkoituksiin.

87
00:03:51,460 --> 00:03:56,540
Kasaan myös olemaan missä
muuttujat ja muistin, että pyydät

88
00:03:56,540 --> 00:03:58,810
alkaen käyttöjärjestelmän
tallennetaan väliaikaisesti.

89
00:03:58,810 --> 00:04:01,890
>> Mutta on sellainen ongelma
täällä, koska kuva merkitsee.

90
00:04:01,890 --> 00:04:05,261
Meillä tavallaan on kaksi
aluksia noin törmäävät.

91
00:04:05,261 --> 00:04:08,010
Koska käytät enemmän ja enemmän
pinon, ja kuten näemme tänään

92
00:04:08,010 --> 00:04:11,800
eteenpäin, koska käytät enemmän ja enemmän
kasaan, varmasti pahoja asioita voi tapahtua.

93
00:04:11,800 --> 00:04:15,054
Ja todellakin, me voimme aiheuttaa, että
tahallisesti tai tahattomasti.

94
00:04:15,054 --> 00:04:16,970
Joten jännitysnäytelmä viimeksi
aika oli tämän ohjelman,

95
00:04:16,970 --> 00:04:20,570
joka ei palvele mitään toiminnallista
muuhun tarkoitukseen kuin osoittamaan

96
00:04:20,570 --> 00:04:24,750
miten niin pahis voi itse ottaa
etu bugeja jonkun ohjelman

97
00:04:24,750 --> 00:04:28,460
ja ottaa ohjelman tai jopa
koko tietokonejärjestelmä tai palvelimeen.

98
00:04:28,460 --> 00:04:31,660
Joten vain silmäyksellä lyhyesti, sinun
huomaa, että tärkein alareunassa

99
00:04:31,660 --> 00:04:34,510
ottaa komentoriviltä
argumentteja, kuten per argv.

100
00:04:34,510 --> 00:04:38,480
Ja se on kutsu funktio f,
lähinnä nimetön toiminto nimeltään

101
00:04:38,480 --> 00:04:40,250
f, ja se kulkee argv [1].

102
00:04:40,250 --> 00:04:43,960
>> Joten mitä sana käyttäjä on osoitteessa
nopea jälkeen tämän ohjelman nimi,

103
00:04:43,960 --> 00:04:49,310
ja sitten tämä mielivaltainen funktio ylös
top, f, vie merkkijonon, AKA char *,

104
00:04:49,310 --> 00:04:51,720
kuten olemme alkaneet keskustella,
ja se vain kutsuu sitä "bar".

105
00:04:51,720 --> 00:04:53,310
Mutta voisimme kutsua sitä jotain.

106
00:04:53,310 --> 00:04:57,470
Ja sitten se ilmoittaa, sisältä
f, joukko merkkejä

107
00:04:57,470 --> 00:04:59,930
nimeltään C-- 12 tällaista merkkiä.

108
00:04:59,930 --> 00:05:03,580
>> Nyt, jonka tarina kerroin
hetki sitten, jos muistissa

109
00:05:03,580 --> 00:05:06,720
on C, tai ovat niitä, 12
merkkiä päätyvät?

110
00:05:06,720 --> 00:05:07,570
Vain olla selvä.

111
00:05:07,570 --> 00:05:08,070
Joo?

112
00:05:08,070 --> 00:05:08,590
>> Yleisö: pinoon.

113
00:05:08,590 --> 00:05:09,420
>> DAVID J. MALAN: pinoon.

114
00:05:09,420 --> 00:05:10,720
Joten c on paikallinen muuttuja.

115
00:05:10,720 --> 00:05:14,079
Kysymme 12 merkkiä tai 12 tavua.

116
00:05:14,079 --> 00:05:16,120
Nämä ovat menossa päätyä
on ns pino.

117
00:05:16,120 --> 00:05:18,530
Nyt vihdoin on tämä toinen toiminto
Se on oikeastaan ​​aika hyödyllinen,

118
00:05:18,530 --> 00:05:20,571
mutta emme ole oikeastaan ​​käytetty
sen itse, strncopy.

119
00:05:20,571 --> 00:05:21,550

120
00:05:21,550 --> 00:05:25,200
Se tarkoittaa merkkijonon kopion, mutta
vain n kappaletta kirjaimia, n merkkiä.

121
00:05:25,200 --> 00:05:31,990
Joten n merkkejä ovat
kopioidaan tanko c.

122
00:05:31,990 --> 00:05:32,980
Ja kuinka monta?

123
00:05:32,980 --> 00:05:34,110
Pituus baarissa.

124
00:05:34,110 --> 00:05:36,330
Eli toisin sanoen, että
yksi linja, strncopy,

125
00:05:36,330 --> 00:05:39,500
tulee kopioida
tehokkaasti baarin c.

126
00:05:39,500 --> 00:05:42,340
>> Nyt vain sellainen ennakoida
Tarinan,

127
00:05:42,340 --> 00:05:44,750
mikä on mahdollisesti ongelmallista täällä?

128
00:05:44,750 --> 00:05:49,710
Vaikka me tarkastamme pituus
bar ja kulkee sen strncopy,

129
00:05:49,710 --> 00:05:53,145
mikä on teidän gut kertoo sinulle on
edelleen rikki tästä ohjelmasta?

130
00:05:53,145 --> 00:05:54,410

131
00:05:54,410 --> 00:05:55,220
Joo?

132
00:05:55,220 --> 00:05:57,491
>> Yleisö: Ei sisällä
tilaa null merkki.

133
00:05:57,491 --> 00:05:59,990
DAVID J. MALAN: Ei sisällä
tilaa null merkki.

134
00:05:59,990 --> 00:06:02,073
Mahdollisesti, toisin kuin
Aiemman käytännön emme edes

135
00:06:02,073 --> 00:06:04,810
on niin paljon kuin plus 1
majoittaa että null merkki.

136
00:06:04,810 --> 00:06:06,649
Mutta se on vielä pahempi.

137
00:06:06,649 --> 00:06:07,940
Mitä muuta me vältämme tekemästä?

138
00:06:07,940 --> 00:06:08,432
Joo?

139
00:06:08,432 --> 00:06:09,307
>> Yleisö: [kuulumaton]

140
00:06:09,307 --> 00:06:15,440

141
00:06:15,440 --> 00:06:16,440
DAVID J. MALAN: Perfect.

142
00:06:16,440 --> 00:06:18,490
Olemme koodattu 12 melko mielivaltaisesti.

143
00:06:18,490 --> 00:06:19,497

144
00:06:19,497 --> 00:06:21,330
Se ei ole niin paljon
ongelma, vaan se,

145
00:06:21,330 --> 00:06:25,630
että emme edes tarkistaa, jos
pituus palkki on pienempi kuin 12,

146
00:06:25,630 --> 00:06:28,530
jolloin se tulee olemaan
turvallista laittaa se muistiin

147
00:06:28,530 --> 00:06:30,260
nimeltään C että olemme varattu.

148
00:06:30,260 --> 00:06:32,960
Todellakin, jos baari on kuin
20 merkkiä pitkä,

149
00:06:32,960 --> 00:06:39,010
tämä toiminto näyttää kopiointi
20 merkkiä tanko c, jolloin

150
00:06:39,010 --> 00:06:41,310
ottaen vähintään 8 tavua
että sen ei pitäisi olla.

151
00:06:41,310 --> 00:06:42,690
Se on seuraus tästä.

152
00:06:42,690 --> 00:06:44,347
>> Niin lyhyt, rikki-ohjelma.

153
00:06:44,347 --> 00:06:45,180
Ei niin iso juttu.

154
00:06:45,180 --> 00:06:46,360
Ehkä saat segmentointi vika.

155
00:06:46,360 --> 00:06:47,651
Meillä kaikilla on ollut vikoja ohjelmissa.

156
00:06:47,651 --> 00:06:50,196
Meillä kaikilla saattaa olla vikoja
ohjelmiin juuri nyt.

157
00:06:50,196 --> 00:06:51,320
Mutta mitä vaikutuksia?

158
00:06:51,320 --> 00:06:54,390
No, tässä lähennettyä versio
että kuva minun tietokoneen muistiin.

159
00:06:54,390 --> 00:06:56,230
Tämä on pohja minun pinon.

160
00:06:56,230 --> 00:06:59,644
Ja todellakin, alareunassa on mitä on
nimeltään vanhempi rutiini pino, hieno tapa

161
00:06:59,644 --> 00:07:00,560
sanoa, että tärkein.

162
00:07:00,560 --> 00:07:03,772
Niin että kuka kutsui toiminto
f että puhumme.

163
00:07:03,772 --> 00:07:05,230
Tämä on siis pinon pohjalle.

164
00:07:05,230 --> 00:07:06,640
Palautusosoite on jotain uutta.

165
00:07:06,640 --> 00:07:08,810
Se on aina ollut siellä,
aina ollut tuossa kuvassa.

166
00:07:08,810 --> 00:07:10,440
Olemme juuri koskaan kiinnittänyt huomiota siihen.

167
00:07:10,440 --> 00:07:15,290
Koska se kääntyy pois tieltä c toimii on
että kun yksi toiminto kutsuu toista,

168
00:07:15,290 --> 00:07:18,780
eivät ainoastaan ​​argumentit, jotka
toiminto työnnetään pinoon,

169
00:07:18,780 --> 00:07:22,470
eivät ainoastaan ​​funktion paikallinen
muuttujat työnnetään pinoon,

170
00:07:22,470 --> 00:07:26,820
jotain kutsutaan paluuosoite
myös saa laittaa pinoon.

171
00:07:26,820 --> 00:07:33,330
Erityisesti jos tärkeimmät puhelut foo Mainin
oma osoite muistiin, ox jotain,

172
00:07:33,330 --> 00:07:38,240
tehokkaasti saa laittaa pinoon
niin että kun f on tehty sen suorittamista

173
00:07:38,240 --> 00:07:43,630
tietää mistä hypätä takaisin tekstiin
segmentti voidakseen jatkaa täytäntöönpanosta.

174
00:07:43,630 --> 00:07:47,760
>> Joten jos olemme täällä käsitteellisesti,
main, niin f saa kutsutaan.

175
00:07:47,760 --> 00:07:50,200
Miten f tiedä kuka
käteen ohjaus takaisin?

176
00:07:50,200 --> 00:07:52,020
No, tämä pieni
breadcrumb punaisella täällä,

177
00:07:52,020 --> 00:07:54,978
nimeltään palautusosoite, se vain
tarkastuksia, mikä on, että tuotto-osoite?

178
00:07:54,978 --> 00:07:57,039
Oi, anna minun hypätä takaisin tärkein täällä.

179
00:07:57,039 --> 00:07:59,080
Ja se on hieman
on liian yksinkertaistava,

180
00:07:59,080 --> 00:08:00,750
koska nollia ja ykkösiä
Pitkien ovat teknisesti

181
00:08:00,750 --> 00:08:01,967
tänne Tech segmentin.

182
00:08:01,967 --> 00:08:03,800
Mutta se ajatus. f
vain on tietää, mitä

183
00:08:03,800 --> 00:08:06,680
missä valvonta lopulta palaa.

184
00:08:06,680 --> 00:08:09,790
>> Mutta niin tietokoneet
ovat jo pitkään säädettyihin asioita

185
00:08:09,790 --> 00:08:12,320
kuten paikalliset muuttujat ja
väitteet on näin.

186
00:08:12,320 --> 00:08:17,180
Joten päälle tätä kuvaa
sininen on pinokehys f, joten kaikki

187
00:08:17,180 --> 00:08:19,630
muistin, että f
Erityisesti on käytössä.

188
00:08:19,630 --> 00:08:22,990
Niin ollen, huomaa, että
Baari on tässä kuvassa.

189
00:08:22,990 --> 00:08:23,980
Baari oli sen väitettä.

190
00:08:23,980 --> 00:08:27,240
Ja me väitti, että argumentit
toimintoja työnnetään pinoon.

191
00:08:27,240 --> 00:08:29,910
Ja c, on tietenkin
Myös tässä kuvassa.

192
00:08:29,910 --> 00:08:33,520
>> Ja vain merkinnällinen tarkoituksiin,
huomaa yläreunassa vasemmassa alakulmassa

193
00:08:33,520 --> 00:08:37,020
on mikä olisi c kiinnike 0 ja
sitten hieman oikealle

194
00:08:37,020 --> 00:08:38,220
on c kiinnike 11.

195
00:08:38,220 --> 00:08:41,240
Eli toisin sanoen, voitte kuvitella
että siellä verkkoon tavua

196
00:08:41,240 --> 00:08:44,380
siellä, joista ensimmäinen on
vasemmassa yläkulmassa, pohja

197
00:08:44,380 --> 00:08:48,360
on viimeinen näistä 12 tavua.

198
00:08:48,360 --> 00:08:49,930
>> Mutta nyt yrittää kelata eteenpäin.

199
00:08:49,930 --> 00:08:55,580
Mitä on tapahtumassa, jos ohitamme
merkkijono baarissa, joka on pidempi kuin c?

200
00:08:55,580 --> 00:08:59,130
Ja emme tarkistaa, jos
se on todellakin yli 12.

201
00:08:59,130 --> 00:09:03,146
Mikä osa tätä kuvaa on menossa
päällekirjoiteta tavujen 0, 1, 2, 3,

202
00:09:03,146 --> 00:09:07,890
dot dot dot, 11, ja sen jälkeen
huono, 12, 13: sta 19?

203
00:09:07,890 --> 00:09:11,820
Mitä tulee tapahtumaan täällä,
jos päätellä tilaaminen

204
00:09:11,820 --> 00:09:14,790
että c kiinnike 0 on ylimmässä
ja c kiinnike 11 on tavallaan alas

205
00:09:14,790 --> 00:09:15,812
oikealle?

206
00:09:15,812 --> 00:09:16,796
Joo?

207
00:09:16,796 --> 00:09:19,260
>> Yleisö: No, se tulee
korvata char * bar.

208
00:09:19,260 --> 00:09:22,260
>> DAVID J. MALAN: Joo, se näyttää
aiot korvata char * bar.

209
00:09:22,260 --> 00:09:26,245
Ja pahempaa, jos lähetät todella pitkä
merkkijono, saatat jopa korvata mitä?

210
00:09:26,245 --> 00:09:27,460

211
00:09:27,460 --> 00:09:28,570
Palautusosoite.

212
00:09:28,570 --> 00:09:31,380
Joka taas on aivan
linkkipolku kertoa ohjelma, jossa

213
00:09:31,380 --> 00:09:34,060
palata kun f
tehdään kutsutaan.

214
00:09:34,060 --> 00:09:37,140
>> Joten mitä pahikset tekevät yleensä
jos he törmännyt ohjelmaan

215
00:09:37,140 --> 00:09:41,290
että he ovat uteliaita siitä on
hyödynnettävissä, buginen siten

216
00:09:41,290 --> 00:09:43,550
että hän voi ottaa
etu, että vika,

217
00:09:43,550 --> 00:09:45,720
yleensä he eivät saa
tämä oikeus ensimmäistä kertaa.

218
00:09:45,720 --> 00:09:48,590
He vain alkavat lähettää esimerkiksi
satunnaisia ​​merkkijonoja omaan ohjelmaan,

219
00:09:48,590 --> 00:09:50,260
onko näppäimistöllä,
tai suoraan sanottuna he luultavasti

220
00:09:50,260 --> 00:09:52,740
kirjoittaa vähän ohjelmaa vain
automaattisesti jouset,

221
00:09:52,740 --> 00:09:55,430
ja alkaa hakkaa oman ohjelman
lähettämistä paljon eri tuotantopanosten

222
00:09:55,430 --> 00:09:56,340
eri pituudet.

223
00:09:56,340 --> 00:09:58,990
>> Heti kun ohjelma kaatuu,
Se on uskomaton juttu.

224
00:09:58,990 --> 00:10:01,020
Koska se tarkoittaa, että hän
tai hän on löytänyt

225
00:10:01,020 --> 00:10:02,660
mikä on luultavasti todellakin bugi.

226
00:10:02,660 --> 00:10:05,830
Ja sitten he voivat saada viisaampi
ja alkaa keskittyä tiukemmin

227
00:10:05,830 --> 00:10:07,420
miten hyödyntää että vika.

228
00:10:07,420 --> 00:10:11,480
Erityisesti mitä hän voisi
tehdä, on lähettää, parhaassa tapauksessa, hei.

229
00:10:11,480 --> 00:10:12,210
No big deal.

230
00:10:12,210 --> 00:10:14,750
Se on merkkijono, joka on riittävän lyhyt.

231
00:10:14,750 --> 00:10:18,100
Mutta entä jos hän lähettää,
ja me yleistää sitä,

232
00:10:18,100 --> 00:10:20,890
hyökkäys code-- niin nollat
ja ne, jotka tekevät asioita

233
00:10:20,890 --> 00:10:25,150
kuten rm-rf, että poistaa kaikki
kiintolevyltä tai lähettää roskapostia

234
00:10:25,150 --> 00:10:27,000
tai jotenkin hyökätä kone?

235
00:10:27,000 --> 00:10:29,570
>> Joten, jos kaikki nämä
kirjaimet vain edustaa,

236
00:10:29,570 --> 00:10:32,380
käsitteellisesti, hyökkäys, hyökkäys,
hyökkäys, hyökkäys, huonoja koodi

237
00:10:32,380 --> 00:10:36,410
että joku muu kirjoitti, mutta
jos kyseinen henkilö on fiksu

238
00:10:36,410 --> 00:10:40,790
paitsi sisältää kaikki
Näiden rm-RFS, mutta myös

239
00:10:40,790 --> 00:10:46,100
on hänen viime tavua
olla numero, joka vastaa

240
00:10:46,100 --> 00:10:50,540
osoitteeseen hänen
tai oman hyökkäyksen koodi

241
00:10:50,540 --> 00:10:53,820
että hän läpäisi vain
antamalla se sitä kysyy,

242
00:10:53,820 --> 00:10:58,760
voit tehokkaasti huijata tietokoneen
tulee huomaamatta, kun f on tehty täytäntöönpanosta,

243
00:10:58,760 --> 00:11:02,400
Voi, se on aika minun hypätä
takaisin punainen palautusosoite.

244
00:11:02,400 --> 00:11:06,070
Mutta koska hän on jotenkin
päällekkäinen paluuosoite

245
00:11:06,070 --> 00:11:09,602
omalla numerolla,
ja he ovat tarpeeksi älykkäitä

246
00:11:09,602 --> 00:11:11,560
on määrittänyt, että
numero viittaa, kun

247
00:11:11,560 --> 00:11:13,740
katso super alkuun
vasemmassa alakulmassa siellä,

248
00:11:13,740 --> 00:11:18,020
todellinen osoite tietokoneen
muisto joidenkin hyökkäys koodi,

249
00:11:18,020 --> 00:11:21,740
pahis voi huijata tietokoneen
osaksi täytäntöönpanovaltion oman koodin.

250
00:11:21,740 --> 00:11:23,700
>> Ja että koodi taas voi olla mitä tahansa.

251
00:11:23,700 --> 00:11:26,120
On yleisesti kutsutaan
kuori-koodi, joka on vain

252
00:11:26,120 --> 00:11:29,030
tapa sanoa, että se ei ole
yleensä jotain niin yksinkertaista kuin rm-rf.

253
00:11:29,030 --> 00:11:32,340
Se on oikeastaan ​​jotain Bash,
tai varsinainen ohjelma, joka antaa hänelle

254
00:11:32,340 --> 00:11:37,230
tai hänen ohjelmallisen säädön suorittamiseksi
muuta, että he haluavat.

255
00:11:37,230 --> 00:11:40,210
Niin lyhyt, tämä kaikki
johtuu yksinkertaisesti siitä,

256
00:11:40,210 --> 00:11:44,490
että tämä vika mukana ei tarkista
rajat matriisisi.

257
00:11:44,490 --> 00:11:47,250
Ja sillä tavalla
tietokoneet työ on, että ne

258
00:11:47,250 --> 00:11:49,430
Käytä pino
tehokkaasti, käsitteellisesti,

259
00:11:49,430 --> 00:11:54,830
alhaalta ylös, mutta sitten elementit
painat pinoon kasvaa ylhäältä alas,

260
00:11:54,830 --> 00:11:56,624
Tämä on uskomattoman ongelmallista.

261
00:11:56,624 --> 00:11:58,290
Nyt on olemassa tapoja kiertää tämän.

262
00:11:58,290 --> 00:12:00,800
Ja rehellisesti, on olemassa muitakin kieliä
jonka kanssa kiertää.

263
00:12:00,800 --> 00:12:03,100
Java on immuuni, esimerkiksi
tähän kysymykseen.

264
00:12:03,100 --> 00:12:04,110
Koska he eivät anna viitteitä.

265
00:12:04,110 --> 00:12:05,943
Ne eivät anna sinulle
suora muisti osoitteita.

266
00:12:05,943 --> 00:12:08,560
Joten tämä voima, joka meillä on
koskematta mihinkään muistiin

267
00:12:08,560 --> 00:12:11,580
Haluamme tulee, tosin suuri riski.

268
00:12:11,580 --> 00:12:12,430
>> Joten pitää silmällä.

269
00:12:12,430 --> 00:12:14,596
Jos rehellisesti sanottuna kuukausina
tai tulevina vuosina, milloin

270
00:12:14,596 --> 00:12:17,740
olet lukenut joitakin hyväksikäyttö
ohjelman tai palvelin,

271
00:12:17,740 --> 00:12:22,370
jos joskus nähdä aavistuksen jotain
kuten puskurin ylivuoto hyökkäys,

272
00:12:22,370 --> 00:12:25,390
tai pinon ylivuoto on toinen tyyppi
hyökkäys, hengeltään samanlainen,

273
00:12:25,390 --> 00:12:28,770
jopa inspiroi sivuston
nimi, jos tiedät sen,

274
00:12:28,770 --> 00:12:33,170
se kaikki puhuvat vain
täynnä koko jokin merkki

275
00:12:33,170 --> 00:12:36,200
array tai jotkut array yleisemmin.

276
00:12:36,200 --> 00:12:38,822
Kysyttävää, niin, tähän?

277
00:12:38,822 --> 00:12:39,780
Älä kokeile tätä kotona.

278
00:12:39,780 --> 00:12:41,620

279
00:12:41,620 --> 00:12:42,300
>> Kunnossa.

280
00:12:42,300 --> 00:12:47,270
Joten malloc on tähän mennessä ollut uuden
ystävä, että voimme varata muistia

281
00:12:47,270 --> 00:12:50,540
että emme välttämättä tiedä
etukäteen, että haluamme niin meillä ei ole

282
00:12:50,540 --> 00:12:52,920
kovaa koodi meidän
ohjelmanumeroita, kuten 12.

283
00:12:52,920 --> 00:12:55,550
Kun käyttäjä kertoo, kuinka paljon
tietoja hän haluaa syöttää,

284
00:12:55,550 --> 00:12:58,000
Voimme malloc niin paljon muistia.

285
00:12:58,000 --> 00:13:01,484
>> Joten malloc se kääntyy pois, jotta
määrin olemme käyttäneet sitä,

286
00:13:01,484 --> 00:13:03,900
nimenomaisesti viime kerralla, ja sitten
te ovat käyttäneet sitä

287
00:13:03,900 --> 00:13:08,160
varten getstring tietämättään varten
useita viikkoja, kaikki malloc muistista

288
00:13:08,160 --> 00:13:09,820
tulee ns pino.

289
00:13:09,820 --> 00:13:13,852
Ja tästä syystä getstring, esimerkiksi
voi varata muistia dynaamisesti

290
00:13:13,852 --> 00:13:16,060
tietämättä mitä olet
menossa kirjoittaa etukäteen,

291
00:13:16,060 --> 00:13:21,520
käden takaisin osoittimen, joka muisti,
ja että muisti on edelleen sinun pitää,

292
00:13:21,520 --> 00:13:24,080
jälkeenkin getstring palaa.

293
00:13:24,080 --> 00:13:27,450
Koska muistaa kaiken sen jälkeen
pino jatkuvasti menee ylös ja alas,

294
00:13:27,450 --> 00:13:27,950
ylös ja alas.

295
00:13:27,950 --> 00:13:30,230
Ja heti kun se menee
alas, että mitä tahansa muistia

296
00:13:30,230 --> 00:13:33,030
Tätä toimintoa käytetään pitäisi
ei saa käyttää kukaan muu.

297
00:13:33,030 --> 00:13:34,570
Se on roskaa arvot nyt.

298
00:13:34,570 --> 00:13:36,120
>> Mutta keko on täällä.

299
00:13:36,120 --> 00:13:39,360
Ja mikä on mukavaa noin malloc on, että
kun malloc varaa muistia täällä,

300
00:13:39,360 --> 00:13:42,070
se ei ole vaikuttanut, sillä
suurin osa on pino.

301
00:13:42,070 --> 00:13:46,000
Ja niin jokin toiminto voi käyttää
muistin, joka on malloc'd,

302
00:13:46,000 --> 00:13:49,120
jopa toimivat kuin getstring,
senkin jälkeen se palautetaan.

303
00:13:49,120 --> 00:13:51,700
>> Nyt päinvastainen malloc on ilmainen.

304
00:13:51,700 --> 00:13:53,900
Ja todellakin, sääntö sinua
täytyy alkaa hyväksyä

305
00:13:53,900 --> 00:13:58,950
on mikä tahansa, mitä tahansa, milloin käytät malloc
sinun täytyy itse käyttää vapaa, lopulta,

306
00:13:58,950 --> 00:14:00,280
samana osoitin.

307
00:14:00,280 --> 00:14:03,289
Koko tämän ajan olemme kirjallisesti
buginen, buginen koodi, monista syistä.

308
00:14:03,289 --> 00:14:05,580
Mutta joista yksi on ollut
käyttämällä CS50 kirjasto, joka

309
00:14:05,580 --> 00:14:09,010
itsessään on tarkoituksella
buginen, se vuotaa muistia.

310
00:14:09,010 --> 00:14:11,410
Aina kun olen kutsunut getstring
viime viikkoina

311
00:14:11,410 --> 00:14:13,870
Pyydämme toiminta
järjestelmä, Linux, muistin.

312
00:14:13,870 --> 00:14:15,780
Ja et ole kertaakaan antanut sitä takaisin.

313
00:14:15,780 --> 00:14:17,730
Ja tämä ei ole, vuonna
harjoitella, hyvä juttu.

314
00:14:17,730 --> 00:14:20,330
>> Ja Valgrind, yksi
työkalujen käyttöön PSET 4,

315
00:14:20,330 --> 00:14:22,900
tarkoitus on auttaa sinua
nyt löytää vikoja niin.

316
00:14:22,900 --> 00:14:27,060
Mutta onneksi PSET 4 et tarvitse
käyttää CS50 kirjaston tai getstring.

317
00:14:27,060 --> 00:14:31,220
Joten vikoja liittyvät muisti ovat
lopulta olemaan oma.

318
00:14:31,220 --> 00:14:34,060
>> Joten malloc on enemmän kuin vain
kätevä tähän tarkoitukseen.

319
00:14:34,060 --> 00:14:37,420
Voimme todella nyt ratkaista
perustavanlaatuisesti erilaisia ​​ongelmia,

320
00:14:37,420 --> 00:14:41,640
ja pohjimmiltaan ratkaise ongelmia lisää
tehokkaasti viikossa nolla lupaus.

321
00:14:41,640 --> 00:14:44,720
Toistaiseksi tämä on seksikkäin
tietorakenne meillä on ollut.

322
00:14:44,720 --> 00:14:47,804
Ja tietorakenne Tarkoitan vain
tapa käsitteellistää muistia

323
00:14:47,804 --> 00:14:50,720
tavalla, joka ylittää vain sanomalla,
tämä on int, tämä on merkkiä.

324
00:14:50,720 --> 00:14:52,930
Voimme aloittaa klusterin asioita yhdessä.

325
00:14:52,930 --> 00:14:54,460
>> Joten array näytti tältä.

326
00:14:54,460 --> 00:14:57,270
Ja mikä oli keskeinen noin
Asetelma on, että se antaa sinulle

327
00:14:57,270 --> 00:14:59,724
back-to-back paloina
muistin, joista jokainen

328
00:14:59,724 --> 00:15:02,765
tulee olemaan samaa tyyppiä, int,
int, int, int, tai char, char, char,

329
00:15:02,765 --> 00:15:03,330
merkkiä.

330
00:15:03,330 --> 00:15:04,496
Mutta siellä on muutama haittoja.

331
00:15:04,496 --> 00:15:06,570
Tässä esimerkiksi on
taulukon koko kuusi.

332
00:15:06,570 --> 00:15:10,650
Oletetaan täytät tämän array kuusi
numerot ja sitten jostain syystä,

333
00:15:10,650 --> 00:15:13,187
Käyttäjänimesi haluaa antaa
te seitsemännen numeron.

334
00:15:13,187 --> 00:15:14,020
Mistä sinä sen?

335
00:15:14,020 --> 00:15:15,490

336
00:15:15,490 --> 00:15:18,990
>> Mikä on ratkaisu, jos olet
luotu array pinoon,

337
00:15:18,990 --> 00:15:22,030
Esimerkiksi pelkästään viikolla
kaksi merkintää, jotka otimme käyttöön,

338
00:15:22,030 --> 00:15:23,730
neliön kannattimet numero sisällä?

339
00:15:23,730 --> 00:15:25,160

340
00:15:25,160 --> 00:15:27,260
No, sinulla on kuusi
numerot näissä laatikoissa.

341
00:15:27,260 --> 00:15:28,530
Mitä vaistosi olla?

342
00:15:28,530 --> 00:15:29,973
Minne haluaisit laittaa sen?

343
00:15:29,973 --> 00:15:30,860
>> Yleisö: [kuulumaton]

344
00:15:30,860 --> 00:15:31,315
>> DAVID J. MALAN: Anteeksi?

345
00:15:31,315 --> 00:15:32,380
>> Yleisö: Laita se loppuun.

346
00:15:32,380 --> 00:15:33,796
>> DAVID J. MALAN: Laita se loppuun.

347
00:15:33,796 --> 00:15:35,880
Joten hieman yli oikealle,
ulkopuolella tämän laatikon.

348
00:15:35,880 --> 00:15:38,710
Mikä olisi kiva, mutta se
Osoittautuu, et voi tehdä sitä.

349
00:15:38,710 --> 00:15:41,350
Koska jos et ole pyytänyt
Tämän kimpale muistia,

350
00:15:41,350 --> 00:15:44,490
se voi olla sattumaa, että tämä
käytetään jonkin muun muuttujan

351
00:15:44,490 --> 00:15:45,030
kokonaan.

352
00:15:45,030 --> 00:15:49,210
Muistelen viikon tai niin kun loimme
ulos Zamyla ja Davin ja Gabe nimet

353
00:15:49,210 --> 00:15:49,930
muistiin.

354
00:15:49,930 --> 00:15:51,638
He olivat kirjaimellisesti
takaisin takaisin takaisin.

355
00:15:51,638 --> 00:15:53,550
Joten emme voi välttämättä
luottaa siihen, että mitä on

356
00:15:53,550 --> 00:15:55,800
täällä on saatavilla minulle käyttää.

357
00:15:55,800 --> 00:15:56,990
>> Mitä muuta voisi tehdä?

358
00:15:56,990 --> 00:16:00,282
No, kun ymmärtämättä sinua
tarvitsevat taulukon koko seitsemän,

359
00:16:00,282 --> 00:16:02,490
voisit luoda
taulukon koko seitsemän sitten

360
00:16:02,490 --> 00:16:05,950
silmukka tai while-silmukka,
kopioi se uuteen array,

361
00:16:05,950 --> 00:16:09,680
ja sitten jotenkin vain päästä eroon
tämän taulukon tai vain lakata käyttämästä sitä.

362
00:16:09,680 --> 00:16:12,130
Mutta se ei ole erityisen tehokasta.

363
00:16:12,130 --> 00:16:15,340
Lyhyesti, taulukot eivät anna
voit dynaamisesti muuttaa.

364
00:16:15,340 --> 00:16:17,900
>> Niin toisaalta saat
random access, mikä on hämmästyttävä.

365
00:16:17,900 --> 00:16:20,108
Koska se antaa meidän tehdä asioita
kuten hajoita ja hallitse,

366
00:16:20,108 --> 00:16:23,100
Binäärihaku, jotka kaikki olemme
puhui ruudulla täällä.

367
00:16:23,100 --> 00:16:24,950
Mutta maalaat itsesi nurkkaan.

368
00:16:24,950 --> 00:16:27,810
Heti kun osut
lopussa oman array,

369
00:16:27,810 --> 00:16:29,980
sinun täytyy tehdä hyvin
kallis toimenpide

370
00:16:29,980 --> 00:16:33,910
tai kirjoittaa koko joukko koodin
nyt käsitellä tätä ongelmaa.

371
00:16:33,910 --> 00:16:36,680
>> Joten mitä jos sen sijaan meillä oli
jotain kutsutaan lista,

372
00:16:36,680 --> 00:16:38,820
tai linkitetty lista erityisesti?

373
00:16:38,820 --> 00:16:41,930
Mitä jos sen sijaan,
suorakulmioita takaisin takaisin takaisin,

374
00:16:41,930 --> 00:16:45,730
meillä ruutuihin jättää hieman
vähän liikkumavaraa niiden väliin?

375
00:16:45,730 --> 00:16:49,670
Ja vaikka olen laatinut tämän
kuva tai mukauttaa tätä kuvaa

376
00:16:49,670 --> 00:16:54,696
yhdestä tekstien ja tule takaisin
takaisin takaisin hyvin järjestelmällisesti, todellisuudessa,

377
00:16:54,696 --> 00:16:56,820
yksi niistä suorakaide
voisi olla täällä muistissa.

378
00:16:56,820 --> 00:16:58,028
Yksi niistä voisi olla täällä.

379
00:16:58,028 --> 00:17:00,420
Yksi niistä voisi olla täällä,
tänne, ja niin edelleen.

380
00:17:00,420 --> 00:17:02,910
>> Mutta entä jos me kiinnitti,
Tässä tapauksessa, nuolet

381
00:17:02,910 --> 00:17:05,650
että jotenkin yhdistää nämä
suorakulmiot yhteen?

382
00:17:05,650 --> 00:17:08,170
Itse asiassa olemme nähneet teknisen
inkarnaatio nuoli.

383
00:17:08,170 --> 00:17:09,839

384
00:17:09,839 --> 00:17:13,710
Mitä olemme käytetty viime
päivinä, alla huppu,

385
00:17:13,710 --> 00:17:15,210
edustaa nuoli?

386
00:17:15,210 --> 00:17:16,290

387
00:17:16,290 --> 00:17:17,349
Osoitin, eikö?

388
00:17:17,349 --> 00:17:19,780
>> Joten mitä jos sen sijaan,
vain tallentamalla numerot,

389
00:17:19,780 --> 00:17:23,130
kuten 9, 17, 22, 26, 34,
mitä jos emme ole tallennettu

390
00:17:23,130 --> 00:17:27,079
vain puhelinnumeron, mutta osoitin
vierekkäin niin numero?

391
00:17:27,079 --> 00:17:30,690
Niin paljon kuin olisit kierre
neula läpi koko joukko kangasta,

392
00:17:30,690 --> 00:17:32,950
jotenkin sitominen asiat
yhdessä, samoin voi

393
00:17:32,950 --> 00:17:35,550
me viitteitä, kuten
ruumiillistunut nuolilla täällä,

394
00:17:35,550 --> 00:17:38,550
tavallaan kutoa yhteen
Näiden yksittäisten suorakaide

395
00:17:38,550 --> 00:17:41,780
tehokkaasti käyttämällä osoitinta
vierekkäin useita, jotka

396
00:17:41,780 --> 00:17:46,065
eräisiin seuraava numero, joka
osoittaa puolestaan, joissakin seuraava numero?

397
00:17:46,065 --> 00:17:47,940
Eli toisin sanoen, mitä
jos me todella halusimme

398
00:17:47,940 --> 00:17:49,820
toteuttaa jotain tällaista?

399
00:17:49,820 --> 00:17:53,610
No valitettavasti näitä suorakaide,
ainakin yksi 9, 17, 22,

400
00:17:53,610 --> 00:17:57,040
ja niin edelleen, nämä eivät ole enää
kiva neliöitä yhtä numerot.

401
00:17:57,040 --> 00:17:59,960
Pohja, suorakaide
alle 9, esimerkiksi,

402
00:17:59,960 --> 00:18:04,330
edustaa sitä, mikä olisi
olla osoitin, 32 bittiä.

403
00:18:04,330 --> 00:18:09,460
Nyt en ole vielä tiedossa tietotyyppi
C, joka antaa sinulle paitsi int

404
00:18:09,460 --> 00:18:11,630
mutta osoitin kokonaan.

405
00:18:11,630 --> 00:18:15,020
>> Joten mikä on ratkaisu, jos haluamme
keksiä omia vastaus tähän?

406
00:18:15,020 --> 00:18:15,760
Joo?

407
00:18:15,760 --> 00:18:16,640
>> Yleisö: [kuulumaton]

408
00:18:16,640 --> 00:18:17,360
>> DAVID J. MALAN: Mikä tämä on?

409
00:18:17,360 --> 00:18:17,880
>> Yleisö: Uusi rakenne.

410
00:18:17,880 --> 00:18:19,590
>> DAVID J. MALAN: Joo, niin miksi
emme luo uutta rakennetta,

411
00:18:19,590 --> 00:18:20,920
tai C, struct?

412
00:18:20,920 --> 00:18:25,990
Olemme nähneet structs ennen, jos lyhyesti,
jossa käsitellään opiskelijan rakenne

413
00:18:25,990 --> 00:18:27,780
kuten tämä, jolla oli nimi ja talon.

414
00:18:27,780 --> 00:18:31,980
Vuonna PSET 3 Breakout käytit koko
nippu structs-- GRect ja GOvals

415
00:18:31,980 --> 00:18:34,810
että Stanford luotu
cluster tiedot yhdessä.

416
00:18:34,810 --> 00:18:38,580
Joten mitä jos otamme tämän saman ajatuksen
avainsanat "typedef" ja "struct"

417
00:18:38,580 --> 00:18:42,890
ja sitten jotkut opiskelija-erityisiä juttuja,
ja kehittyä tämän huomioon seuraavat:

418
00:18:42,890 --> 00:18:46,210
struct node-- ja solmu on
vain hyvin yleinen tietotekniikassa

419
00:18:46,210 --> 00:18:49,980
termi jotain datarakenteen,
säiliö tietorakenteeseen.

420
00:18:49,980 --> 00:18:53,900
Solmu Väitän joutuu
int n, täysin suoraviivainen,

421
00:18:53,900 --> 00:18:58,810
ja sitten hieman arvoituksellisesti,
tämä toinen linja, struct solmu * seuraavaksi.

422
00:18:58,810 --> 00:19:01,300
Mutta vähemmän teknisiä termejä,
mikä on että toisen linjan

423
00:19:01,300 --> 00:19:02,980
Koodin sisällä aaltosulkeita?

424
00:19:02,980 --> 00:19:03,737
Joo?

425
00:19:03,737 --> 00:19:04,851
>> Yleisö: [kuulumaton]

426
00:19:04,851 --> 00:19:06,600
DAVID J. MALAN:
osoitin toiseen solmuun.

427
00:19:06,600 --> 00:19:09,910
Niin tosin lauseenrakenteen hieman arvoituksellinen.

428
00:19:09,910 --> 00:19:13,250
Mutta jos olet lukenut sen kirjaimellisesti,
seuraava on muuttujan nimenä.

429
00:19:13,250 --> 00:19:14,410
Mikä on sen tietotyyppi?

430
00:19:14,410 --> 00:19:18,206
Se on vähän monisanainen tällä kertaa,
mutta se on tyyppiä struct solmu *.

431
00:19:18,206 --> 00:19:22,960
Tahansa olemme nähneet jotain tähden, että
tarkoittaa että se on osoitin, että tietotyyppi.

432
00:19:22,960 --> 00:19:26,810
Joten seuraavaksi on ilmeisesti
Osoitin struct solmu.

433
00:19:26,810 --> 00:19:28,310
>> Nyt, mikä on struct solmu?

434
00:19:28,310 --> 00:19:31,044
No, huomaa näet ne
samat sanat oikeassa yläkulmassa.

435
00:19:31,044 --> 00:19:33,960
Ja todellakin, näet myös sana
"Solmu" täällä alhaalla vasemmalla.

436
00:19:33,960 --> 00:19:35,640
Ja tämä on oikeastaan ​​vain mukavuussyistä.

437
00:19:35,640 --> 00:19:39,930
Huomaa, että meidän opiskelija määritelmä
siellä on sana "opiskelija" vain kerran.

438
00:19:39,930 --> 00:19:42,510
Ja se johtuu siitä, opiskelija
esine ei ollut itseensä viittaavan.

439
00:19:42,510 --> 00:19:45,340
Mikään ei sisällä opiskelija
joka tarvitsee tuoda toisen opiskelijan,

440
00:19:45,340 --> 00:19:45,610
persay.

441
00:19:45,610 --> 00:19:47,630
Se olisi eräänlainen
outo todellisessa maailmassa.

442
00:19:47,630 --> 00:19:50,880
>> Mutta solmun linkitetty
lista, mehän haluamme solmun

443
00:19:50,880 --> 00:19:53,970
olla viite on samanlainen tarkoitus.

444
00:19:53,970 --> 00:19:57,900
Ja niin huomaat muutoksen tässä ole
vain mitä sisällä aaltosulkumerkkien.

445
00:19:57,900 --> 00:20:00,800
Mutta lisäämme sanan "solmu"
yläosassa sekä

446
00:20:00,800 --> 00:20:02,930
lisäämällä sen pohjaan
sijasta "opiskelija".

447
00:20:02,930 --> 00:20:06,000
Ja tämä on vain tekninen yksityiskohta
niin että, jälleen, tietosi rakenne

448
00:20:06,000 --> 00:20:11,380
voi olla itseensä viittaavan, niin että
solmu voi osoittaa toiselle tällaiselle solmuun.

449
00:20:11,380 --> 00:20:13,840
>> Joten mitä tämä lopulta
menossa merkitsee meille?

450
00:20:13,840 --> 00:20:17,560
No, yksi, tätä tavaraa sisällä
on sisältö meidän solmun.

451
00:20:17,560 --> 00:20:19,360
Tämä juttu täällä,
oikeassa yläkulmassa, on vain niin

452
00:20:19,360 --> 00:20:20,860
että, jälleen, voimme viitata itseämme.

453
00:20:20,860 --> 00:20:23,401
Ja sitten syrjäisimpien tavaraa,
vaikka solmu on uusi termi,

454
00:20:23,401 --> 00:20:25,500
ehkä se on silti
sama kuin opiskelija ja mitä

455
00:20:25,500 --> 00:20:27,520
oli alla huppu SPL.

456
00:20:27,520 --> 00:20:31,095
>> Joten jos nyt halunnut aloittaa
täytäntöönpanossa linkitetty lista,

457
00:20:31,095 --> 00:20:33,220
miten voisi käännämme
jotain tällaista koodia?

458
00:20:33,220 --> 00:20:35,350
No, haluan vain nähdä
esimerkki ohjelmasta, joka

459
00:20:35,350 --> 00:20:36,840
tosiasiallisesti käyttää linkitetty lista.

460
00:20:36,840 --> 00:20:40,870
Keskuudessa nykypäivän jakelu koodi
on ohjelma nimeltä List Zero.

461
00:20:40,870 --> 00:20:44,980
Ja jos juoksen tämän olen luonut erittäin
yksinkertainen GUI, graafinen käyttöliittymä,

462
00:20:44,980 --> 00:20:46,460
mutta se on oikeastaan ​​vain printf.

463
00:20:46,460 --> 00:20:50,930
Ja nyt olen antanut itselleni muutaman valikon
options-- poistaa, lisätä, haku,

464
00:20:50,930 --> 00:20:51,750
ja Traverse.

465
00:20:51,750 --> 00:20:52,630
Ja Lopeta.

466
00:20:52,630 --> 00:20:55,970
Nämä ovat vain yhteisiä operaatioita
tietorakenne tunnetaan linkkilista.

467
00:20:55,970 --> 00:20:58,409
>> Nyt Delete on menossa
poistaa numeron luettelosta.

468
00:20:58,409 --> 00:21:00,200
Insert tulee lisätä
numeron luetteloon.

469
00:21:00,200 --> 00:21:02,181
Haku on menossa katsomaan
Numeron luettelossa.

470
00:21:02,181 --> 00:21:04,930
Ja poikittainen on vain hieno tapa
sanoa, kävele listalle

471
00:21:04,930 --> 00:21:06,245
tulostaa sen, mutta siinäpä se.

472
00:21:06,245 --> 00:21:07,720
Älä muuta sitä millään tavalla.

473
00:21:07,720 --> 00:21:08,570
>> Joten kokeile tätä.

474
00:21:08,570 --> 00:21:10,160
Mennään eteenpäin ja tyypin 2.

475
00:21:10,160 --> 00:21:12,710
Ja sitten aion
lisätä numeron, sanovat 9.

476
00:21:12,710 --> 00:21:13,620
Enter.

477
00:21:13,620 --> 00:21:17,480
Ja nyt ohjelma on vain
ohjelmoitu sanoa, lista on nyt 9.

478
00:21:17,480 --> 00:21:20,190
Nyt, jos menen eteenpäin ja
älä laita se uudelleen, anna

479
00:21:20,190 --> 00:21:23,680
minun mennä eteenpäin ja loitontaa ja kirjoita 17.

480
00:21:23,680 --> 00:21:25,770
Nyt lista on 9, sitten 17.

481
00:21:25,770 --> 00:21:27,750
Jos en laita se takaisin, katsotaanpa ohittaa yhden.

482
00:21:27,750 --> 00:21:32,400
Sen sijaan 22, joka on pakkauksessa olemme
etsinyt täällä, haluan siirtyä eteenpäin

483
00:21:32,400 --> 00:21:34,630
ja aseta 26 seuraava.

484
00:21:34,630 --> 00:21:36,230
Joten aion kirjoittaa 26.

485
00:21:36,230 --> 00:21:37,755
Luettelo on odotan.

486
00:21:37,755 --> 00:21:40,630
Mutta nyt vain nähdä, jos tämä koodi
tulee olla joustava, haluan nyt

487
00:21:40,630 --> 00:21:43,520
tyyppi 22, joista ainakin
käsitteellisesti, jos olemme

488
00:21:43,520 --> 00:21:46,520
Pidä tämä lajitellaan, joka on todellakin
olemaan toinen tavoite juuri nyt,

489
00:21:46,520 --> 00:21:48,690
pitäisi mennä välillä 17 ja 26.

490
00:21:48,690 --> 00:21:50,270
Joten osuin Enter.

491
00:21:50,270 --> 00:21:51,380
Todellakin, että toimii.

492
00:21:51,380 --> 00:21:54,950
Ja nyt haluan lisätä
viimeinen, per kuva, 34.

493
00:21:54,950 --> 00:21:55,450
>> Kunnossa.

494
00:21:55,450 --> 00:21:58,980
Joten nyt haluan ilmoittaa, että
Poista ja Traverse ja haku tehdä,

495
00:21:58,980 --> 00:21:59,760
itse asiassa toimi.

496
00:21:59,760 --> 00:22:04,180
Itse asiassa, jos en suorita haku, katsotaanpa
etsi numero 22, Enter.

497
00:22:04,180 --> 00:22:05,010
Se löytyi 22.

498
00:22:05,010 --> 00:22:07,580
Niin sitähän tämä
Ohjelman List Zero tekee.

499
00:22:07,580 --> 00:22:10,230
>> Mutta mitä todella tapahtuu
siitä, että toteuttaa tämä?

500
00:22:10,230 --> 00:22:14,530
No, ensin voisin olla, ja todellakin
Minulla ei ole, tiedosto nimeltä list0.h.

501
00:22:14,530 --> 00:22:16,540

502
00:22:16,540 --> 00:22:20,690
Ja jossain on tämä
linja, typedef, struct solmu,

503
00:22:20,690 --> 00:22:24,850
Sitten minulla on aaltosulkeita, int n, ja
Sitten struct-- mikä oli määritelmän?

504
00:22:24,850 --> 00:22:26,530

505
00:22:26,530 --> 00:22:28,545
Struct solmu seuraavaksi.

506
00:22:28,545 --> 00:22:29,920

507
00:22:29,920 --> 00:22:31,045
Joten tarvitsemme tähti.

508
00:22:31,045 --> 00:22:33,420
Nyt teknisesti pääsemme
tapana piirtämällä täällä.

509
00:22:33,420 --> 00:22:35,670
Saatat nähdä oppikirjoja ja
Online viittaukset siihen siellä.

510
00:22:35,670 --> 00:22:36,660
Se on toiminnallisesti vastaava.

511
00:22:36,660 --> 00:22:37,980
Itse asiassa tämä on hieman enemmän tyypillinen.

512
00:22:37,980 --> 00:22:40,563
Mutta olen sitä, mitä
teimme viime kerralla ja tehdä tämän.

513
00:22:40,563 --> 00:22:42,350
Ja sitten lopuksi, aion tehdä tämän.

514
00:22:42,350 --> 00:22:45,550
>> Joten otsikkotiedosto
jonnekin, vuonna list0.h

515
00:22:45,550 --> 00:22:49,200
tänään on tämä struct määritelmä,
ja ehkä joitakin muita juttuja.

516
00:22:49,200 --> 00:22:52,580
Samaan aikaan list0c siellä
olemaan muutamia asioita.

517
00:22:52,580 --> 00:22:54,740
Mutta me aiomme vain
aloittaa eikä lopettaa tämän.

518
00:22:54,740 --> 00:22:59,690
List0.h on tiedosto haluan
sisällyttää minun C-tiedosto.

519
00:22:59,690 --> 00:23:03,910
Ja sitten jossain vaiheessa olen
menossa on int, tärkein, mitätöidä.

520
00:23:03,910 --> 00:23:06,530
Ja sitten aion
joitakin tehtävälista on täällä.

521
00:23:06,530 --> 00:23:10,620
Olen myös menossa
prototyyppi, kuten mitätön, haku, int,

522
00:23:10,620 --> 00:23:13,610
n, jonka tarkoitus elämässä on
etsiä elementti.

523
00:23:13,610 --> 00:23:18,310
Ja sitten täällä olen väittänyt
Nykypäivän koodia, mitätön, haku, int, n,

524
00:23:18,310 --> 00:23:21,020
ei puolipiste mutta avoin aaltosulkeita.

525
00:23:21,020 --> 00:23:25,049
Ja nyt haluan jotenkin hakea
varten elementti tässä listassa.

526
00:23:25,049 --> 00:23:27,340
Mutta meillä ei ole tarpeeksi
kuvaruudussa vielä.

527
00:23:27,340 --> 00:23:29,800
En ole oikeastaan
edusti luetteloa.

528
00:23:29,800 --> 00:23:33,070
Joten yksi tapa voisimme toteuttaa
linkitetty lista ohjelmassa

529
00:23:33,070 --> 00:23:37,520
on Olen sellainen halua tehdä jotain
kuten Julistan linkitetyn listan tänne.

530
00:23:37,520 --> 00:23:40,520
Yksinkertaisuuden vuoksi aion tehdä
tämä globaali, vaikka yleensä me

531
00:23:40,520 --> 00:23:41,645
ei pitäisi tehdä tätä liikaa.

532
00:23:41,645 --> 00:23:43,260
Mutta se yksinkertaistaa tätä esimerkkiä.

533
00:23:43,260 --> 00:23:45,890
Joten en halua julistaa
linkitetyn listan tänne.

534
00:23:45,890 --> 00:23:47,010
Nyt, miten voisin tehdä?

535
00:23:47,010 --> 00:23:48,810

536
00:23:48,810 --> 00:23:50,750
>> Tässä on kuva linkitetyn listan.

537
00:23:50,750 --> 00:23:53,030
Ja en oikein
tiedä tällä hetkellä, miten

538
00:23:53,030 --> 00:23:56,710
Aion edetä edustavat
niin monet asiat vain yhdellä

539
00:23:56,710 --> 00:23:58,040
muuttuja muistiin.

540
00:23:58,040 --> 00:23:59,160
Mutta muistelen hetki.

541
00:23:59,160 --> 00:24:00,830
Koko ajan meillä on ollut
jouset, jonka sitten

542
00:24:00,830 --> 00:24:02,913
paljastuu paneelit
merkkiä, jonka sitten

543
00:24:02,913 --> 00:24:05,740
paljasti vain olla osoitin
ensimmäisen merkin

544
00:24:05,740 --> 00:24:08,890
riviksi merkkiä
joka on null irtisanotaan.

545
00:24:08,890 --> 00:24:13,530
Niin, että logiikka, ja tämän
kuva tavallaan kylvö ajatuksiasi,

546
00:24:13,530 --> 00:24:17,964
Mitä me oikeastaan ​​kirjoittaa meidän
koodi edustaa linkitetty lista?

547
00:24:17,964 --> 00:24:21,130
Kuinka paljon tästä tietoa tarvitsemme
vangita C-koodia, sanoisit?

548
00:24:21,130 --> 00:24:22,654

549
00:24:22,654 --> 00:24:23,154
Joo?

550
00:24:23,154 --> 00:24:24,738
>> Yleisö: Tarvitsemme osoitin solmuun.

551
00:24:24,738 --> 00:24:26,237
David J. MALAN: osoitin solmuun.

552
00:24:26,237 --> 00:24:29,320
Erityisesti, mikä solmu Olisiko
vaistot olla pitää osoitin?

553
00:24:29,320 --> 00:24:30,026
>> YLEISÖ: ensimmäiseen solmuun.

554
00:24:30,026 --> 00:24:31,942
>> DAVID J. MALAN: Joo,
luultavasti vain ensimmäinen.

555
00:24:31,942 --> 00:24:34,030
Ja huomaa, ensimmäinen
solmu on erilainen muoto.

556
00:24:34,030 --> 00:24:37,690
Se on vain puolet koko struct,
koska se on todellakin vain osoitin.

557
00:24:37,690 --> 00:24:44,650
Joten mitä voit todella tehdä, on ilmoittaa
linkitetty lista on tyyppiä solmu *.

558
00:24:44,650 --> 00:24:47,780
Ja haluan vain kutsua sitä ensin
ja alustaa sen nollaamaan.

559
00:24:47,780 --> 00:24:49,910
Joten null taas on tulossa
kuvaan tässä.

560
00:24:49,910 --> 00:24:53,620
Ei vain null käytetään kuten erityinen
paluuarvo asioita, kuten getstring

561
00:24:53,620 --> 00:24:57,770
ja malloc, nolla on myös nolla
osoitin, ettei osoitin,

562
00:24:57,770 --> 00:24:58,430
jos haluatte.

563
00:24:58,430 --> 00:25:00,309
Se vain tarkoittaa, mikään ei ole vielä täällä.

564
00:25:00,309 --> 00:25:02,100
Nyt ensin, olisin voinut
kutsui tätä kaikkea.

565
00:25:02,100 --> 00:25:04,200
Olisin voinut kutsui sitä "listan"
tai useita muita asioita.

566
00:25:04,200 --> 00:25:06,960
Mutta soitan sitä "ensimmäinen" niin, että
se on linjassa tämän kuvan.

567
00:25:06,960 --> 00:25:10,280
Joten aivan kuten merkkijono voidaan esittää
osoitteen kanssa sen ensimmäinen tavu,

568
00:25:10,280 --> 00:25:11,280
niin voi linkitetty lista.

569
00:25:11,280 --> 00:25:13,480
Ja näemme muita tietoja
rakenteet ovat edustettuina

570
00:25:13,480 --> 00:25:16,700
vain yksi osoitin,
32-bittinen nuoli osoittaen

571
00:25:16,700 --> 00:25:18,740
aivan ensimmäisen solmun rakenteessa.

572
00:25:18,740 --> 00:25:20,340
>> Mutta nyt katsotaanpa ennakoida ongelma.

573
00:25:20,340 --> 00:25:23,230
Jos olen vain muistaa
minun ohjelma osoite

574
00:25:23,230 --> 00:25:27,220
Ensimmäisen solmun, ensimmäinen
suorakulmio tässä tietorakenne,

575
00:25:27,220 --> 00:25:31,760
mikä oli parempi olla kyse siitä
täytäntöönpanoa muun listalta?

576
00:25:31,760 --> 00:25:35,820
Mikä on avain yksityiskohta, joka menee
varmistamiseksi tämä todella toimii?

577
00:25:35,820 --> 00:25:39,250
Ja "oikeasti toimii" I
Tarkoitan, aivan kuten merkkijono,

578
00:25:39,250 --> 00:25:42,180
antaa meidän mennä ensimmäinen merkki
vuonna Davin nimi toiseen,

579
00:25:42,180 --> 00:25:44,755
kolmanteen, että
Neljäs, loppuun asti,

580
00:25:44,755 --> 00:25:47,880
Mistä tiedämme, milloin olemme lopussa
linkitetyn listan, joka näyttää tältä?

581
00:25:47,880 --> 00:25:50,035

582
00:25:50,035 --> 00:25:50,660
Kun se on tyhjä.

583
00:25:50,660 --> 00:25:53,640
Ja olen edusti tällainen kuin
kuten sähkö-insinööri voimin,

584
00:25:53,640 --> 00:25:56,420
pikku maadoitus
symboli, tapaisena.

585
00:25:56,420 --> 00:25:58,246
Mutta se vain tarkoittaa, null tässä tapauksessa.

586
00:25:58,246 --> 00:26:00,370
Voit piirtää haluamansa määrän
tavoilla, mutta tämän kirjoittajan

587
00:26:00,370 --> 00:26:02,800
tapahtui käyttää tätä symbolia täällä.

588
00:26:02,800 --> 00:26:06,260
>> Niin kauan kuin olemme nauhassa
kaikki nämä solmut yhdessä,

589
00:26:06,260 --> 00:26:08,600
vain muistaa missä
Ensimmäinen on, niin kauan

590
00:26:08,600 --> 00:26:11,760
niin laitamme erikoissymboli osoitteessa
viimeinen solmu listassa,

591
00:26:11,760 --> 00:26:15,130
ja käytämme null, koska se on
mitä meillä on käytettävissämme,

592
00:26:15,130 --> 00:26:16,480
tämä lista on valmis.

593
00:26:16,480 --> 00:26:20,190
Ja vaikka minä vain antaa sinulle osoittimen
ensimmäinen elementti, te, ohjelmoija,

594
00:26:20,190 --> 00:26:22,486
voi varmasti käyttää loput siitä.

595
00:26:22,486 --> 00:26:24,360
Mutta katsotaanpa anna mielissä
vaeltaa hieman,

596
00:26:24,360 --> 00:26:26,140
jos ne eivät ole jo
aivan wandered-- mitä

597
00:26:26,140 --> 00:26:28,723
olemaan käyntiaika
löytää jotain seuraavista?

598
00:26:28,723 --> 00:26:30,450

599
00:26:30,450 --> 00:26:33,470
Hitto, se on iso O n,
joka ei ole huono, oikeudenmukaisuus.

600
00:26:33,470 --> 00:26:34,800
Mutta se on lineaarinen.

601
00:26:34,800 --> 00:26:37,980
Olemme luopuneet mitä ominaisuutta
Taulukoiden siirtämällä lisää

602
00:26:37,980 --> 00:26:43,130
kohti tätä kuvaa dynaamisesti
kudottu yhteen tai siihen solmuja?

603
00:26:43,130 --> 00:26:44,970

604
00:26:44,970 --> 00:26:46,687
Olemme luopuneet random access.

605
00:26:46,687 --> 00:26:48,770
Array on mukavaa, koska
matemaattisesti kaiken

606
00:26:48,770 --> 00:26:50,340
on palannut takaisin takaisin takaisin.

607
00:26:50,340 --> 00:26:52,370
Vaikka tämä kuva
näyttää aika, ja jopa

608
00:26:52,370 --> 00:26:55,830
vaikka se näyttää nämä solmut
ovat hyvin erillään toisistaan, todellisuudessa

609
00:26:55,830 --> 00:26:56,830
he voisivat olla missä tahansa.

610
00:26:56,830 --> 00:27:01,590
OX1, OX50, Ox123, Ox99, nämä
solmut voi olla missä tahansa.

611
00:27:01,590 --> 00:27:05,960
Koska malloc ei varata muistia
kasaan, mutta kaikkialla kasaan.

612
00:27:05,960 --> 00:27:09,080
Et välttämättä tiedä, että se on
tulee takaisin takaisin takaisin.

613
00:27:09,080 --> 00:27:12,460
Ja niin tätä kuvaa todellisuudesta n
ei tule olemaan ihan näin kaunis.

614
00:27:12,460 --> 00:27:16,140
>> Joten se tulee ottaa vähän
työtä toteuttaa tätä toimintoa.

615
00:27:16,140 --> 00:27:17,880
Joten toteuttaa haun nyt.

616
00:27:17,880 --> 00:27:20,250
Ja näemme, millaisia
näppärä tapa tehdä tämä.

617
00:27:20,250 --> 00:27:24,660
Joten jos olen hakutoiminto ja
Olen antanut muuttuja, kokonaisluku n

618
00:27:24,660 --> 00:27:28,490
etsiä, minun täytyy tietää
uusi syntaksi etsii sisällä

619
00:27:28,490 --> 00:27:32,400
rakenne, joka on
osoitti, löytää n.

620
00:27:32,400 --> 00:27:33,210
Joten tehdään tämä.

621
00:27:33,210 --> 00:27:36,030
>> Joten ensin aion mennä
eteenpäin ja julistaa solmu *.

622
00:27:36,030 --> 00:27:39,400
Ja aion kutsua sitä
osoitin, vain sopimuksen mukaan.

623
00:27:39,400 --> 00:27:41,710
Ja aion alustaa sen ensin.

624
00:27:41,710 --> 00:27:43,770
Ja nyt en voi tehdä tätä
useilla tavoilla.

625
00:27:43,770 --> 00:27:45,436
Mutta aion olla yhteinen lähestymistapa.

626
00:27:45,436 --> 00:27:50,180
Vaikka osoitin ei ole yhtä suuri
null, ja se on voimassa syntaksin.

627
00:27:50,180 --> 00:27:54,550
Ja se tarkoittaa vain toimi seuraavasti, joten
kunhan et osoita mitään.

628
00:27:54,550 --> 00:27:55,800
Mitä haluan tehdä?

629
00:27:55,800 --> 00:28:01,939
>> Jos osoitin dot n, haluan tulla takaisin
vastaavasti, equals-- vastaa mitä?

630
00:28:01,939 --> 00:28:03,105
Mikä arvo etsin?

631
00:28:03,105 --> 00:28:04,920

632
00:28:04,920 --> 00:28:06,590
Varsinainen n että hyväksyttiin.

633
00:28:06,590 --> 00:28:09,020
Joten tässä on toinen ominaisuus
C ja monilla kielillä.

634
00:28:09,020 --> 00:28:13,705
Vaikka rakenne nimeltään solmu
on arvo n, täysin laillista

635
00:28:13,705 --> 00:28:17,530
että myös paikallinen argumentti
tai muuttuja Kutsutaan.

636
00:28:17,530 --> 00:28:20,085
Sillä vaikka me, joilla
ihmisten silmissä, voidaan erottaa

637
00:28:20,085 --> 00:28:22,087
että tämä n on oletettavasti
eroaa tästä n.

638
00:28:22,087 --> 00:28:23,420
Koska syntaksi on erilainen.

639
00:28:23,420 --> 00:28:26,211
Sinulla piste ja osoitin,
tämä yksi ei ole olemassakaan.

640
00:28:26,211 --> 00:28:27,290
Joten tämä on OK.

641
00:28:27,290 --> 00:28:29,120
Se on OK kutsua niitä samoja asioita.

642
00:28:29,120 --> 00:28:32,380
>> Jos en löydät tämän, olen
menossa haluavat tehdä jotain

643
00:28:32,380 --> 00:28:35,000
kuin ilmoittaa, että löysimme n.

644
00:28:35,000 --> 00:28:37,930
Ja jätämme että
kommentoida tai pseudokoodilla koodia.

645
00:28:37,930 --> 00:28:40,190
Else, ja tässä
mielenkiintoinen osa, mitä

646
00:28:40,190 --> 00:28:47,320
En halua tehdä, jos nykyinen solmu
ei sisällä n että välitän?

647
00:28:47,320 --> 00:28:50,700
Miten saavuttaa seuraava?

648
00:28:50,700 --> 00:28:53,710
Jos sormella
hetki on PTR, ja se on

649
00:28:53,710 --> 00:28:55,920
osoittaen tahansa
ensimmäinen on suunnattu,

650
00:28:55,920 --> 00:28:59,290
miten voin siirtää sormi
seuraavaan solmuun koodi?

651
00:28:59,290 --> 00:29:01,915
No, mitä linkkipolun olemme
menossa seuraamaan tässä asiassa?

652
00:29:01,915 --> 00:29:03,464

653
00:29:03,464 --> 00:29:04,380
Yleisö: [kuulumaton].

654
00:29:04,380 --> 00:29:05,630
DAVID J. MALAN: Joo, niin seuraavaksi.

655
00:29:05,630 --> 00:29:06,640

656
00:29:06,640 --> 00:29:09,824
Joten jos menen takaisin minun
koodi täällä, todellakin, olen

657
00:29:09,824 --> 00:29:12,990
aio mennä eteenpäin ja sanoa osoitin, joka
on vain väliaikainen variable-- se on

658
00:29:12,990 --> 00:29:15,320
outo nimi, PTR, mutta
se on aivan kuin temp--

659
00:29:15,320 --> 00:29:19,234
Aion asettaa osoittimen
yhtä suuri kuin mikä tahansa osoitin on--

660
00:29:19,234 --> 00:29:22,150
ja uudestaan, tämä tulee olemaan
vähän buginen moment-- piste seuraavaksi.

661
00:29:22,150 --> 00:29:23,551

662
00:29:23,551 --> 00:29:26,550
Toisin sanoen, aion ottaa minun
sormi, joka on suunnattu tähän solmuun

663
00:29:26,550 --> 00:29:31,247
täällä ja aion sanoa, tiedäthän
mitä, katsomaan seuraavaan kenttään

664
00:29:31,247 --> 00:29:33,330
ja siirrä sormea
mitä se on suunnattu.

665
00:29:33,330 --> 00:29:35,163
Ja tämä tulee
toista, toista, toista.

666
00:29:35,163 --> 00:29:37,630
Mutta kun ei minun sormi
lakata tekemästä yhtään mitään?

667
00:29:37,630 --> 00:29:40,095
Heti mitä riviä koodia potkuja?

668
00:29:40,095 --> 00:29:40,970
Yleisö: [kuulumaton]

669
00:29:40,970 --> 00:29:43,060
DAVID J. MALAN: Jos kohta taas
osoitin ei ole yhtä suuri null.

670
00:29:43,060 --> 00:29:44,900
Jossain vaiheessa minun sormen
aiotaan osoittaen null

671
00:29:44,900 --> 00:29:47,070
ja aion toteuttaa
se on tämän listan loppuun.

672
00:29:47,070 --> 00:29:48,910
Nyt, tämä on hieman
valkoinen valhe yksinkertaisuuden.

673
00:29:48,910 --> 00:29:51,580
On käynyt ilmi, että vaikka me
juuri oppinut tämän dot merkintä

674
00:29:51,580 --> 00:29:55,220
Rakenteita, osoitin ei ole struct.

675
00:29:55,220 --> 00:29:56,580
PTR on mitä?

676
00:29:56,580 --> 00:29:58,350
Vain olla enemmän nitpicky.

677
00:29:58,350 --> 00:29:59,720

678
00:29:59,720 --> 00:30:01,360
Se on osoitin solmuun.

679
00:30:01,360 --> 00:30:03,120
Se ei ole solmu itse.

680
00:30:03,120 --> 00:30:06,650
Jos minulla ei ollut tähti täällä, osoitin
absolutely-- se on solmu.

681
00:30:06,650 --> 00:30:08,650
Tämä on kuin viikolla yksi
ilmoitus muuttuja,

682
00:30:08,650 --> 00:30:10,120
vaikka sana "solmu", on uusi.

683
00:30:10,120 --> 00:30:13,860
>> Mutta heti kun esittelemme
tähti, se on nyt osoitin solmuun.

684
00:30:13,860 --> 00:30:17,960
Ja valitettavasti et voi käyttää
dot merkintätapa osoitin.

685
00:30:17,960 --> 00:30:21,070
Sinun täytyy käyttää nuoli
merkintätapa, joka häkellyttävän,

686
00:30:21,070 --> 00:30:23,470
on ensimmäistä kertaa kaikki pala
syntaksin näyttää intuitiivinen.

687
00:30:23,470 --> 00:30:25,245
Tämä kirjaimellisesti näyttää nuoli.

688
00:30:25,245 --> 00:30:26,370
Ja niin se on hyvä asia.

689
00:30:26,370 --> 00:30:28,995
Ja täällä kirjaimellisesti
näyttää nuoli.

690
00:30:28,995 --> 00:30:31,870
Joten luulen, että se la-- en
taidan yli-syyllistyneet here-- I

691
00:30:31,870 --> 00:30:34,120
taitaa olla viimeinen uusi kappale
syntaksin aiomme nähdä.

692
00:30:34,120 --> 00:30:36,500
Ja onneksi se on todellakin
hieman enemmän intuitiivinen.

693
00:30:36,500 --> 00:30:40,090
>> Nyt niille teistä, jotka
ehkä mieluummin vanha tapa,

694
00:30:40,090 --> 00:30:42,550
voit silti käyttää dot merkintä.

695
00:30:42,550 --> 00:30:45,380
Mutta kohti Maanantain
keskustelun, ensin

696
00:30:45,380 --> 00:30:50,530
täytyy mennä sinne, mene että
käsitellä, ja sitten käyttää kenttään.

697
00:30:50,530 --> 00:30:51,897
Joten tämä on myös oikea.

698
00:30:51,897 --> 00:30:53,730
Ja suoraan sanottuna, tämä on
hieman pikkutarkka.

699
00:30:53,730 --> 00:30:56,530
Olet kirjaimellisesti sanoen dereference
osoitin ja mennä sinne.

700
00:30:56,530 --> 00:30:59,320
Sitten napata .N, kenttä Kutsutaan.

701
00:30:59,320 --> 00:31:01,370
Mutta rehellisesti sanottuna, kukaan ei halua
kirjoittaa tai lukea tätä.

702
00:31:01,370 --> 00:31:03,620
Ja niin maailma keksitty
nuoli merkintätapa, joka

703
00:31:03,620 --> 00:31:06,980
on sama, samanlainen,
se on vain syntaktista sokeria.

704
00:31:06,980 --> 00:31:10,570
Niin hieno tapa sanoa tämä
näyttää paremmalta, tai näyttää yksinkertaisempi.

705
00:31:10,570 --> 00:31:12,296
>> Joten nyt aion tehdä yhden asian.

706
00:31:12,296 --> 00:31:15,420
Aion sanoa "tauolla", kun olen
löytyi niin en pidä etsimässä sitä.

707
00:31:15,420 --> 00:31:17,620
Mutta tämä on ydin
of hakutoiminto.

708
00:31:17,620 --> 00:31:21,710
Mutta se on paljon helpompaa, vuonna
Lopulta ei kulkea koodin.

709
00:31:21,710 --> 00:31:25,570
Tämä on todellakin muodollinen täytäntöönpano
haku nykypäivän jakelu koodia.

710
00:31:25,570 --> 00:31:30,530
Uskallan väittää, että insertti ei ole
Erityisen hauskaa kulkea

711
00:31:30,530 --> 00:31:33,180
visuaalisesti, eikä poistaa, vaikka
vaikka lopussa päivän

712
00:31:33,180 --> 00:31:35,460
he pohjimmiltaan melko
yksinkertainen heuristiikka.

713
00:31:35,460 --> 00:31:36,330
>> Joten tehdään tämä.

714
00:31:36,330 --> 00:31:39,250
Jos sinulla huumori minut tänne, tein
tuo joukko stressi pallot.

715
00:31:39,250 --> 00:31:40,620
Toin joukko numeroita.

716
00:31:40,620 --> 00:31:46,562
Ja saisimme vain muutamia vapaaehtoisia
edustaa 9, 17, 20, 22, 29, ja 34?

717
00:31:46,562 --> 00:31:48,270
Niin olennaisesti kaikki
kuka täällä tänään.

718
00:31:48,270 --> 00:31:50,170

719
00:31:50,170 --> 00:31:52,760
Se oli yksi, kaksi, kolme,
neljä, viisi, kuusi ihmistä.

720
00:31:52,760 --> 00:31:55,740
Ja olen pyytänyt go-- nähdä, ei
yksi takana nostaa kätensä.

721
00:31:55,740 --> 00:32:01,910
OK, yksi, kaksi, kolme, neljä,
five-- anna minun ladata balance-- kuusi.

722
00:32:01,910 --> 00:32:03,051
OK, olet kuusi tule ylös.

723
00:32:03,051 --> 00:32:04,050
Tarvitsemme muita ihmisiä.

724
00:32:04,050 --> 00:32:05,460
Toimme ylimääräistä stressiä pallot.

725
00:32:05,460 --> 00:32:08,200
Ja jos voisit varten
vain hetken, linja

726
00:32:08,200 --> 00:32:10,490
itsenne vain
kuten tämä kuva täällä.

727
00:32:10,490 --> 00:32:15,200

728
00:32:15,200 --> 00:32:15,959
>> Kunnossa.

729
00:32:15,959 --> 00:32:17,125
Katsotaan, mikä on nimesi?

730
00:32:17,125 --> 00:32:17,550
>> Yleisö: Andrew.

731
00:32:17,550 --> 00:32:18,800
>> DAVID J. MALAN: Andrew,
olet numero 9.

732
00:32:18,800 --> 00:32:19,540
Hauska tavata.

733
00:32:19,540 --> 00:32:20,400
Tässä mennään.

734
00:32:20,400 --> 00:32:21,593

735
00:32:21,593 --> 00:32:22,176
Yleisö: Jen.

736
00:32:22,176 --> 00:32:22,662
DAVID J. MALAN: Jen.

737
00:32:22,662 --> 00:32:23,162
David.

738
00:32:23,162 --> 00:32:23,765
Numero 17.

739
00:32:23,765 --> 00:32:24,950

740
00:32:24,950 --> 00:32:25,450
Kyllä?

741
00:32:25,450 --> 00:32:26,400
>> Yleisö: Olen Julia.

742
00:32:26,400 --> 00:32:26,980
>> DAVID J. MALAN: Julia, David.

743
00:32:26,980 --> 00:32:27,545
Numero 20.

744
00:32:27,545 --> 00:32:28,507

745
00:32:28,507 --> 00:32:29,340
Yleisö: Christian.

746
00:32:29,340 --> 00:32:30,715
DAVID J. MALAN: Christian, David.

747
00:32:30,715 --> 00:32:31,541
Numero 22.

748
00:32:31,541 --> 00:32:32,040
Ja?

749
00:32:32,040 --> 00:32:32,649
>> Yleisö: JP.

750
00:32:32,649 --> 00:32:33,440
DAVID J. MALAN: JP.

751
00:32:33,440 --> 00:32:34,880
Numero 29.

752
00:32:34,880 --> 00:32:37,080
Joten mene eteenpäin ja saada in-- Uh oh.

753
00:32:37,080 --> 00:32:38,486

754
00:32:38,486 --> 00:32:38,985
Uh oh.

755
00:32:38,985 --> 00:32:39,650

756
00:32:39,650 --> 00:32:40,150
Valmiustilassa.

757
00:32:40,150 --> 00:32:41,360

758
00:32:41,360 --> 00:32:42,390
20.

759
00:32:42,390 --> 00:32:43,682
Onko kellään merkki?

760
00:32:43,682 --> 00:32:44,890
Yleisö: Minulla Sharpie.

761
00:32:44,890 --> 00:32:45,660
DAVID J. MALAN: Sinulla Sharpie?

762
00:32:45,660 --> 00:32:46,159
OK.

763
00:32:46,159 --> 00:32:47,577

764
00:32:47,577 --> 00:32:49,160
Ja ei kellään paperia?

765
00:32:49,160 --> 00:32:51,562

766
00:32:51,562 --> 00:32:52,270
Säästä luento.

767
00:32:52,270 --> 00:32:53,810

768
00:32:53,810 --> 00:32:55,362
Tule.

769
00:32:55,362 --> 00:32:56,320
Yleisö: Meillä sitä.

770
00:32:56,320 --> 00:32:57,600
DAVID J. MALAN: Saimme sen?

771
00:32:57,600 --> 00:32:58,577
Okei, kiitos.

772
00:32:58,577 --> 00:33:01,380

773
00:33:01,380 --> 00:33:02,520
Tässä sitä mennään.

774
00:33:02,520 --> 00:33:03,582
Oliko tämä sinulta?

775
00:33:03,582 --> 00:33:04,540
Olet juuri pelasti päivän.

776
00:33:04,540 --> 00:33:05,670

777
00:33:05,670 --> 00:33:07,220
Niin 29.

778
00:33:07,220 --> 00:33:10,510

779
00:33:10,510 --> 00:33:11,110
Kunnossa.

780
00:33:11,110 --> 00:33:13,360

781
00:33:13,360 --> 00:33:14,890
Olen kirjoitettu väärin 29, mutta OK.

782
00:33:14,890 --> 00:33:15,720
Mennä eteenpäin.

783
00:33:15,720 --> 00:33:18,114
Okei, minä annan sinulle
kynän takaisin hetkellisesti.

784
00:33:18,114 --> 00:33:19,280
Joten meillä on nämä ihmiset täällä.

785
00:33:19,280 --> 00:33:20,330
Mennään yksi muu.

786
00:33:20,330 --> 00:33:23,750
Gabe, haluatko pelata
ensimmäinen elementti täällä?

787
00:33:23,750 --> 00:33:25,705
Me tarvitsemme sinua kohtaan
näitä hienoja ihmisiä.

788
00:33:25,705 --> 00:33:26,930

789
00:33:26,930 --> 00:33:31,030
Joten 9, 17, 20, 22, lajitella
29, ja sitten 34.

790
00:33:31,030 --> 00:33:32,160

791
00:33:32,160 --> 00:33:33,325
Eksytimmekö joku?

792
00:33:33,325 --> 00:33:33,950
Minulla on 34.

793
00:33:33,950 --> 00:33:36,730
Jos did-- OK, joka haluaa olla 34?

794
00:33:36,730 --> 00:33:37,605
OK, tule ylös, 34.

795
00:33:37,605 --> 00:33:39,280

796
00:33:39,280 --> 00:33:41,220
Okei, tämä on
arvoinen huipentuma.

797
00:33:41,220 --> 00:33:41,550
Mikä sinun nimesi on?

798
00:33:41,550 --> 00:33:42,040
>> Yleisö: Peter.

799
00:33:42,040 --> 00:33:43,456
>> DAVID J. MALAN: Peter, tule ylös.

800
00:33:43,456 --> 00:33:46,810
Okei, joten tässä on
koko joukko solmuja.

801
00:33:46,810 --> 00:33:49,060
Jokainen teistä kaverit edustaa
yksi näistä suorakulmioita.

802
00:33:49,060 --> 00:33:51,930
Gabe, hieman outoa
ihminen, edustaa ensin.

803
00:33:51,930 --> 00:33:54,850
Joten hänen osoitin on hieman pienempi
ruudulla kuin kaikki muutkin.

804
00:33:54,850 --> 00:33:58,120
Ja tässä tapauksessa kukin vasemmalla
kädet tulee joko kohta alas,

805
00:33:58,120 --> 00:34:01,085
mikä edustaa null, joten
vain puuttuminen osoittimen,

806
00:34:01,085 --> 00:34:03,210
tai se tulee voida osoittaa
solmussa vieressäsi.

807
00:34:03,210 --> 00:34:05,440
>> Joten nyt jos koristavat
itsenne kuten kuva

808
00:34:05,440 --> 00:34:07,585
täällä, mennä eteenpäin ja kohta
toisilleen, ja Gabe

809
00:34:07,585 --> 00:34:11,030
erityisesti suunnattu
numero 9 edustaa luetteloon.

810
00:34:11,030 --> 00:34:14,050
OK, ja numero 34, vasemmalla kädellä
pitäisi vain olla suunnattu lattiaan.

811
00:34:14,050 --> 00:34:15,750
>> OK, joten tämä on linkitetty lista.

812
00:34:15,750 --> 00:34:17,580
Joten tämä on skenaario kyseessä.

813
00:34:17,580 --> 00:34:20,210
Ja todellakin, tämä on tyypillinen
luokan ongelmia

814
00:34:20,210 --> 00:34:21,929
että saatat yrittää ratkaista koodilla.

815
00:34:21,929 --> 00:34:25,020
Haluat lopulta lisätä
uusi elementti luettelosta.

816
00:34:25,020 --> 00:34:27,494
Tässä tapauksessa aiomme
kokeile asettaa numero 55.

817
00:34:27,494 --> 00:34:28,500

818
00:34:28,500 --> 00:34:30,860
Mutta siellä tulee olemaan
eri tapauksissa harkita.

819
00:34:30,860 --> 00:34:34,409
Ja todellakin, tämä tulee olemaan yksi
iso-kuva takeaways täällä on,

820
00:34:34,409 --> 00:34:35,659
mitkä ovat eri tapauksia.

821
00:34:35,659 --> 00:34:39,120
Mitä eri jos olosuhteet tai
oksat, että ohjelma voisi olla?

822
00:34:39,120 --> 00:34:42,024
>> No, numero yrität
insertti, jonka tiedämme nyt olevan 55,

823
00:34:42,024 --> 00:34:44,650
mutta jos et tiedä
etukäteen, rohkenen sanoa

824
00:34:44,650 --> 00:34:47,840
kuuluu ainakin kolmeen
mahdolliset tilanteet.

825
00:34:47,840 --> 00:34:49,717
Missä lienee uusi elementti olla?

826
00:34:49,717 --> 00:34:51,050
Yleisö: Ja lopussa tai keskellä.

827
00:34:51,050 --> 00:34:54,150
DAVID J. MALAN: Lopussa, vuonna
keskellä tai alussa.

828
00:34:54,150 --> 00:34:56,650
Joten väitän siellä ainakin
kolme ongelmaa meidän on ratkaistava.

829
00:34:56,650 --> 00:34:58,691
Valitaan mitä ehkä
luultavasti yksinkertaisin

830
00:34:58,691 --> 00:35:01,090
yksi, jos uusi elementti
kuuluu alussa.

831
00:35:01,090 --> 00:35:04,040
Joten aion olla koodin melko
kuten haku, jonka minä vain kirjoitti.

832
00:35:04,040 --> 00:35:07,670
Ja aion olla PTR, joka
Minä edustan täällä minun sormi,

833
00:35:07,670 --> 00:35:08,370
kuten tavallista.

834
00:35:08,370 --> 00:35:12,430
>> Ja muistaa, mitä arvoa
me alustaa PTR?

835
00:35:12,430 --> 00:35:15,300
Joten me alustetaan se nollaamaan aluksi.

836
00:35:15,300 --> 00:35:16,410

837
00:35:16,410 --> 00:35:19,770
Mutta mitä sitten me teimme, kun olemme
olivat sisällä hakutoiminto?

838
00:35:19,770 --> 00:35:20,940

839
00:35:20,940 --> 00:35:24,870
Asetimme sen yhtä ensin,
mikä ei tarkoita näin.

840
00:35:24,870 --> 00:35:25,890

841
00:35:25,890 --> 00:35:30,570
Jos otan PTR yhtä ensin, mitä
olisi käteni todella olla suunnattu?

842
00:35:30,570 --> 00:35:31,070
Oikea.

843
00:35:31,070 --> 00:35:33,290
Joten jos Gabe ja minä menemme
olla samoja arvoja täällä,

844
00:35:33,290 --> 00:35:34,760
meidän molemmat pisteeseen numero 9.

845
00:35:34,760 --> 00:35:36,420
>> Joten tämä oli alku meidän tarina.

846
00:35:36,420 --> 00:35:38,700
Ja nyt tämä on vain yksinkertainen,
vaikka syntaksi on uusi.

847
00:35:38,700 --> 00:35:40,580
Käsitteellisesti tämä on vain lineaarinen haku.

848
00:35:40,580 --> 00:35:42,750
On 55 yhtä kuin 9?

849
00:35:42,750 --> 00:35:45,559
Tai pikemminkin, sanokaamme alle 9.

850
00:35:45,559 --> 00:35:47,600
Koska Yritän
selvittää, mihin 55.

851
00:35:47,600 --> 00:35:51,270
Alle 9, alle 17, alle
yli 20, alle 22, alle 29,

852
00:35:51,270 --> 00:35:52,510
alle 34, ei.

853
00:35:52,510 --> 00:35:55,080
Joten nyt olemme asiassa
yksi vähintään kolme.

854
00:35:55,080 --> 00:35:59,910
>> Jos haluan lisätä 55 tänne, mitä
riviä koodia täytyy saada toteuttaa?

855
00:35:59,910 --> 00:36:01,890
Miten tämä kuva
ihmisten täytyy muuttaa?

856
00:36:01,890 --> 00:36:03,181
Mitä teen vasemmalla kädellä?

857
00:36:03,181 --> 00:36:04,530

858
00:36:04,530 --> 00:36:07,360
Tämän pitäisi olla null aluksi,
koska olen lopussa luettelosta.

859
00:36:07,360 --> 00:36:09,318
Ja mitä pitäisi tapahtua
täällä Pietarin kanssa oli?

860
00:36:09,318 --> 00:36:10,520

861
00:36:10,520 --> 00:36:12,430
Hän on toki osoittaa minulle.

862
00:36:12,430 --> 00:36:15,580
Joten väitän siellä ainakin kaksi riviä
koodia mallikoodi tänään

863
00:36:15,580 --> 00:36:18,570
joka tulee toteuttaa tämän
skenaario lisätään 55 häntää.

864
00:36:18,570 --> 00:36:20,950
Ja voisin olla joku hop
ja vain edustavat 55?

865
00:36:20,950 --> 00:36:22,200
Okei, olet uuden 55.

866
00:36:22,200 --> 00:36:23,580

867
00:36:23,580 --> 00:36:27,054
>> Joten nyt mitä jos seuraavaksi
skenaario tulee pitkin,

868
00:36:27,054 --> 00:36:29,720
ja haluamme lisätä osoitteessa
alussa tai pään listalta?

869
00:36:29,720 --> 00:36:31,100
Ja mikä on nimesi, numero 55?

870
00:36:31,100 --> 00:36:31,420
>> Yleisö: Jack.

871
00:36:31,420 --> 00:36:32,295
>> DAVID J. MALAN: Jack?

872
00:36:32,295 --> 00:36:33,585
OK, kiva tavata.

873
00:36:33,585 --> 00:36:34,210
Tervetuloa.

874
00:36:34,210 --> 00:36:36,640
Joten nyt aiomme
lisätä vaikkapa numero 5.

875
00:36:36,640 --> 00:36:39,840
Tässä toisessa tapauksessa
kolme keksimme ennen.

876
00:36:39,840 --> 00:36:43,050
Joten jos 5 kuuluu alussa,
Katsotaanpa, miten voimme selvittää asia.

877
00:36:43,050 --> 00:36:46,310
Olen alustaa minun ptr
osoitin numero 9 uudelleen.

878
00:36:46,310 --> 00:36:49,140
Ja tajusin, oh, 5 on alle 9.

879
00:36:49,140 --> 00:36:50,880
Korjatkaa tämä kuva meille.

880
00:36:50,880 --> 00:36:54,820
Joiden kädet, Gaben tai Daavidin
tai-- mikä numero 9: n nimi?

881
00:36:54,820 --> 00:36:55,740
>> Yleisö: Jen.

882
00:36:55,740 --> 00:36:58,406
>> DAVID J. MALAN: Jen hands--
joka kätemme täytyy muuttaa?

883
00:36:58,406 --> 00:36:58,905

884
00:36:58,905 --> 00:37:00,970
OK, joten Gabe muistuttaa, mitä nyt?

885
00:37:00,970 --> 00:37:01,640
Minua.

886
00:37:01,640 --> 00:37:02,750
Olen uusi solmu.

887
00:37:02,750 --> 00:37:04,870
Joten minä vain sellainen liikkua
Näytä se visuaalisesti.

888
00:37:04,870 --> 00:37:06,435
Ja sillä välin mitä voin todeta, että?

889
00:37:06,435 --> 00:37:07,910

890
00:37:07,910 --> 00:37:09,020
Silti jossa minä osoitan.

891
00:37:09,020 --> 00:37:10,000
Joten se siitä.

892
00:37:10,000 --> 00:37:13,717
Joten oikeastaan ​​yksi rivi koodikorjaukset
tässä kysymyksessä, se näyttäisi.

893
00:37:13,717 --> 00:37:14,800
Kunnossa, niin se on hyvä.

894
00:37:14,800 --> 00:37:17,580
Ja voi joku olla paikanpitäjä 5?

895
00:37:17,580 --> 00:37:18,080
Tule ylös.

896
00:37:18,080 --> 00:37:20,270

897
00:37:20,270 --> 00:37:21,320
Saamme sinut seuraavan kerran.

898
00:37:21,320 --> 00:37:24,280
>> Okei, joten now-- ja
Sivuhuomautuksena, nimet

899
00:37:24,280 --> 00:37:28,510
En tee nimenomaista mainintaa oikeus
nyt pred osoitin, edeltäjä osoitin

900
00:37:28,510 --> 00:37:31,260
ja uuden osoittimen, joka on
vain annetut nimet

901
00:37:31,260 --> 00:37:35,280
näytteessä koodin viitteitä tai
käteni Sellainen osoittaa ympärillä.

902
00:37:35,280 --> 00:37:36,060
Mikä sinun nimesi on?

903
00:37:36,060 --> 00:37:36,700
>> Yleisö: Christine.

904
00:37:36,700 --> 00:37:37,100
>> DAVID J. MALAN: Christine.

905
00:37:37,100 --> 00:37:38,090
Tervetuloa.

906
00:37:38,090 --> 00:37:42,180
Okei, joten Tarkastellaan nyt
hieman harmittaa skenaario,

907
00:37:42,180 --> 00:37:46,350
jolloin haluan lisätä
jotain 26 tähän.

908
00:37:46,350 --> 00:37:47,090
20?

909
00:37:47,090 --> 00:37:47,590
Mitä?

910
00:37:47,590 --> 00:37:50,510
Nämä are-- hyvä, että meillä on tämä kynä.

911
00:37:50,510 --> 00:37:51,955
Okei, 20.

912
00:37:51,955 --> 00:37:53,640

913
00:37:53,640 --> 00:37:57,570
Jos joku voisi saada toisen palan
paperin valmis, juuri case-- kunnossa.

914
00:37:57,570 --> 00:37:58,370
Oh, mielenkiintoinen.

915
00:37:58,370 --> 00:37:59,760

916
00:37:59,760 --> 00:38:02,390
No tämä on esimerkki
luennon bugi.

917
00:38:02,390 --> 00:38:03,894
OK niin mikä nimesi olikaan?

918
00:38:03,894 --> 00:38:04,560
Yleisö: Julia.

919
00:38:04,560 --> 00:38:07,559
DAVID J. MALAN: Julia, voitko pop
pois ja teeskennellä olit koskaan siellä?

920
00:38:07,559 --> 00:38:09,040
OK, tämä ei koskaan tapahtunut.

921
00:38:09,040 --> 00:38:09,680
Kiitos.

922
00:38:09,680 --> 00:38:12,180
Joten kai haluamme lisätä
Julia tähän linkitetty lista.

923
00:38:12,180 --> 00:38:13,780
Hän on numero 20.

924
00:38:13,780 --> 00:38:15,530
Ja tietysti hän on
menossa kuuluvat osoitteessa

925
00:38:15,530 --> 00:38:17,521
begin-- eivät viittaa vielä mitään.

926
00:38:17,521 --> 00:38:20,020
Joten kätesi voi sellaista olla
alas null tai jotkut roskat arvo.

927
00:38:20,020 --> 00:38:21,210
Kerrotaan nopean tarinan.

928
00:38:21,210 --> 00:38:22,980
Olen suunnattu numero 5 tällä kertaa.

929
00:38:22,980 --> 00:38:23,880
Sitten voin tarkistaa 9.

930
00:38:23,880 --> 00:38:25,130
Sitten voin tarkistaa 17.

931
00:38:25,130 --> 00:38:26,247
Sitten voin tarkistaa 22.

932
00:38:26,247 --> 00:38:27,650

933
00:38:27,650 --> 00:38:32,485
Ja ymmärrän, ooh, Julia
tarvitsee mennä ennen 22.

934
00:38:32,485 --> 00:38:33,580

935
00:38:33,580 --> 00:38:34,660
Joten mitä pitää tapahtua?

936
00:38:34,660 --> 00:38:35,786

937
00:38:35,786 --> 00:38:36,910
Joiden kädet täytyy muuttaa?

938
00:38:36,910 --> 00:38:38,360
Julia, minun, tai--
Mikä sinun nimesi olikaan?

939
00:38:38,360 --> 00:38:39,230
>> Yleisö: Christian.

940
00:38:39,230 --> 00:38:40,060
>> DAVID J. MALAN: Christian tai?

941
00:38:40,060 --> 00:38:40,560
>> Yleisö: Andy.

942
00:38:40,560 --> 00:38:40,905
>> DAVID J. MALAN: Andy.

943
00:38:40,905 --> 00:38:41,654
Christian tai Andy?

944
00:38:41,654 --> 00:38:44,280

945
00:38:44,280 --> 00:38:45,690
Andy tarvitsee pisteeseen?

946
00:38:45,690 --> 00:38:46,780

947
00:38:46,780 --> 00:38:47,341
Julia.

948
00:38:47,341 --> 00:38:47,840
Kunnossa.

949
00:38:47,840 --> 00:38:48,960
Joten Andy, haluatko pisteeseen Julia?

950
00:38:48,960 --> 00:38:50,120
Mutta hetkinen.

951
00:38:50,120 --> 00:38:53,260
Vuonna tarina tähän mennessä,
Olen tavallaan yksi

952
00:38:53,260 --> 00:38:56,800
vastuussa, siinä mielessä, että
osoitin on asia, joka on

953
00:38:56,800 --> 00:38:57,850
liikkuvat läpi listan.

954
00:38:57,850 --> 00:39:00,800
Meillä saattaa olla nimi Andy, mutta
ei ole muuttuja nimeltään Andy.

955
00:39:00,800 --> 00:39:04,320
Ainoa muuttuja meillä on
Ensimmäinen, joka on edustettuna Gabe.

956
00:39:04,320 --> 00:39:07,690
>> Joten tämä on todella, miksi näin
asti olemme ei tarvita tätä.

957
00:39:07,690 --> 00:39:10,846
Mutta nyt ruudulla on
mainita jälleen ennustearvo osoittimen.

958
00:39:10,846 --> 00:39:11,970
Joten anna minun olla täsmällisempi.

959
00:39:11,970 --> 00:39:14,820
Jos tämä on osoitin, minulla oli parempi
saada hieman enemmän älykkäitä

960
00:39:14,820 --> 00:39:15,950
minun iterointia.

961
00:39:15,950 --> 00:39:19,580
Jos et pahastu eletään täällä
taas osoittaa täällä, osoittaa täällä.

962
00:39:19,580 --> 00:39:22,500
Mutta haluan olla ennustearvo osoitin,
edeltäjä osoitin, joka on

963
00:39:22,500 --> 00:39:24,740
Tällainen suunnattu
elementti Olin juuri.

964
00:39:24,740 --> 00:39:27,330
Joten kun menen tänne, nyt
minun vasen käsi päivityksiä.

965
00:39:27,330 --> 00:39:29,370
Kun menen tänne minun vasen käsi päivityksiä.

966
00:39:29,370 --> 00:39:33,090
Ja nyt minulla ei vain osoitin
elementti, joka menee jälkeen Julia,

967
00:39:33,090 --> 00:39:36,300
Minulla on vielä osoitin
Andy, elementti ennen.

968
00:39:36,300 --> 00:39:39,430
Joten sinulla on mahdollisuus saada tietää,
korppujauhoja, jos haluatte,

969
00:39:39,430 --> 00:39:41,500
kaikki vaaditun viitteitä.

970
00:39:41,500 --> 00:39:43,710
>> Joten jos olen osoittaen
Andy ja olen myös osoittaa

971
00:39:43,710 --> 00:39:47,105
klo Christian, joiden kädet
Nyt olisi todettava muualla?

972
00:39:47,105 --> 00:39:48,770

973
00:39:48,770 --> 00:39:51,960
Joten Andy voi nyt osoitat Julia.

974
00:39:51,960 --> 00:39:54,460
Julia voi nyt osoitat Christian.

975
00:39:54,460 --> 00:39:56,950
Koska hän voi kopioida minun
oikean käden osoitin.

976
00:39:56,950 --> 00:40:00,044
Ja että tehokkaasti vie sinut
takaisin tähän paikkaan täällä.

977
00:40:00,044 --> 00:40:02,460
Niin lyhyt, vaikka tämä
vie meidät tavallaan ikuisesti

978
00:40:02,460 --> 00:40:04,510
itse päivittää
linkitetty lista, ymmärtää

979
00:40:04,510 --> 00:40:06,580
että toiminta
ovat suhteellisen yksinkertaisia.

980
00:40:06,580 --> 00:40:10,030
Se on yksi, kaksi, kolme
riviä koodia lopulta.

981
00:40:10,030 --> 00:40:12,780
Mutta kiedottu nämä
riviä koodia oletettavasti

982
00:40:12,780 --> 00:40:16,350
on vähän logiikkaa, joka tehokkaasti
kysyy kysymyksen, missä olemme?

983
00:40:16,350 --> 00:40:18,970
Olemmeko alussa,
keskimmäinen, tai loppua?

984
00:40:18,970 --> 00:40:21,890
>> Nyt varmasti joitakin muita
toiminnot voisimme toteuttaa.

985
00:40:21,890 --> 00:40:24,880
Ja nämä kuvat täällä vain kuvata
mitä me vain teimme ihmisten kanssa.

986
00:40:24,880 --> 00:40:26,080
Entä poisto?

987
00:40:26,080 --> 00:40:30,650
Jos haluan esimerkiksi
Poista numero 34 tai 55,

988
00:40:30,650 --> 00:40:34,680
Saatan olla samanlaista koodia,
mutta aion tarvitaan yksi tai kaksi vaihetta.

989
00:40:34,680 --> 00:40:36,110
Koska mitä uutta?

990
00:40:36,110 --> 00:40:40,460
Jos poistan jonkun lopussa,
kuten numero 55 ja sitten 34,

991
00:40:40,460 --> 00:40:42,995
mitä täytyy myös muuttaa kuin minä, että?

992
00:40:42,995 --> 00:40:44,870
Täytyy ole evict--
Mikä sinun nimesi olikaan?

993
00:40:44,870 --> 00:40:45,380
>> Yleisö: Jack.

994
00:40:45,380 --> 00:40:46,255
>> DAVID J. MALAN: Jack.

995
00:40:46,255 --> 00:40:49,770
Minun on paitsi evict-- ilmaiseksi Jack,
niin kirjaimellisesti soittaa ilmaiseksi Jack, tai ainakin

996
00:40:49,770 --> 00:40:53,530
osoitin sielläkin, mutta nyt
Tarvittavien muutosten Peter?

997
00:40:53,530 --> 00:40:55,510
Hänen kätensä parempi alkaa osoittaa alaspäin.

998
00:40:55,510 --> 00:40:59,300
Koska heti kun kehotan ilmaiseksi
Jack, jos Pietarin vielä osoittaen Jack

999
00:40:59,300 --> 00:41:02,530
ja siksi pitää liikkumisesta
lista ja käyttää tätä osoitinta,

1000
00:41:02,530 --> 00:41:05,650
silloin meidän vanha ystävä segmentointi
vika voi todella potkia.

1001
00:41:05,650 --> 00:41:07,860
Koska olemme antaneet
muisti takaisin Jack.

1002
00:41:07,860 --> 00:41:10,760
>> Voit pysyä siellä
hankalasti vain hetken.

1003
00:41:10,760 --> 00:41:13,410
Koska meillä on vain pari
loppukäsittelyinä harkita.

1004
00:41:13,410 --> 00:41:15,600
Pään poistaminen luettelosta,
tai beginning-- ja tämä on

1005
00:41:15,600 --> 00:41:16,349
vähän harmittaa.

1006
00:41:16,349 --> 00:41:19,640
Koska meidän täytyy tietää, että Gabe
on sellainen erityinen tässä ohjelmassa.

1007
00:41:19,640 --> 00:41:21,440
Koska todellakin, hänellä on oma osoitin.

1008
00:41:21,440 --> 00:41:24,860
Hän ei vain on suunnattu,
kuten lähes kaikki muutkin täällä.

1009
00:41:24,860 --> 00:41:28,112
>> Joten kun pää luettelo on
poistettiin, joiden kädet täytyy muuttaa nyt?

1010
00:41:28,112 --> 00:41:29,070
Mikä nimesi olikaan?

1011
00:41:29,070 --> 00:41:29,450
>> Yleisö: Christine.

1012
00:41:29,450 --> 00:41:31,408
>> DAVID J. MALAN: Olen kauhea
klo nimiä, ilmeisesti.

1013
00:41:31,408 --> 00:41:34,011
Joten Christine ja Gabe,
joiden kädet täytyy muuttaa

1014
00:41:34,011 --> 00:41:36,510
kun yritämme poistaa Christine,
numero 5, kuvasta?

1015
00:41:36,510 --> 00:41:37,550

1016
00:41:37,550 --> 00:41:38,820
OK, joten tehkäämme Gabe.

1017
00:41:38,820 --> 00:41:40,950
Gabe menee kohtaan,
oletettavasti, numero 9.

1018
00:41:40,950 --> 00:41:42,230

1019
00:41:42,230 --> 00:41:44,642
Mutta mitä seuraavaksi pitäisi tapahtua?

1020
00:41:44,642 --> 00:41:46,600
Yleisö: Christine pitäisi
olla null [äänetön].

1021
00:41:46,600 --> 00:41:50,244
DAVID J. MALAN: OK, meidän pitäisi luultavasti
make-- kuulin "null" jonnekin.

1022
00:41:50,244 --> 00:41:51,410
Yleisö: Null ja vapaa häntä.

1023
00:41:51,410 --> 00:41:51,855
DAVID J. MALAN: null mitä?

1024
00:41:51,855 --> 00:41:53,074
Yleisö: Null ja vapaa häntä.

1025
00:41:53,074 --> 00:41:54,490
DAVID J. MALAN: Null ja vapaa häntä.

1026
00:41:54,490 --> 00:41:55,422
Joten tämä on erittäin helppoa.

1027
00:41:55,422 --> 00:41:58,380
Ja se on täydellinen, että olet nyt tavallaan
seisovan siellä, ei omistaja.

1028
00:41:58,380 --> 00:42:00,430
Koska olet ollut
irrotettu luettelosta.

1029
00:42:00,430 --> 00:42:02,820
Olet samalla ollut
orvoksi listasta.

1030
00:42:02,820 --> 00:42:07,770
Ja niin meidän on parasta soittaa ilmaiseksi nyt
Christine antaa että muisti takaisin.

1031
00:42:07,770 --> 00:42:10,240
Muuten joka kerta
poistaa solmun listasta

1032
00:42:10,240 --> 00:42:14,230
saatamme tehdä lista
lyhyempi, mutta ei oikeastaan ​​laskussa

1033
00:42:14,230 --> 00:42:15,096
koon muistiin.

1034
00:42:15,096 --> 00:42:17,720
Joten jos pitää lisätä ja
lisäämällä, lisäämällä asioita listalle

1035
00:42:17,720 --> 00:42:19,280
tietokone saattaa hidastua
ja hitaammin ja hitaammin,

1036
00:42:19,280 --> 00:42:21,740
koska olen loppumassa
muistiin, vaikka en ole oikeastaan

1037
00:42:21,740 --> 00:42:25,580
käyttäen Christine tavut
muistia enää.

1038
00:42:25,580 --> 00:42:28,500
>> Joten lopulta on muitakin
skenaarioita, ja course-- poisto

1039
00:42:28,500 --> 00:42:30,640
keskellä, poisto
lopussa, kuten näimme.

1040
00:42:30,640 --> 00:42:32,348
Mutta mielenkiintoisempaa
Nyt haasteena on

1041
00:42:32,348 --> 00:42:34,770
olemaan harkita tarkasti
mitä käyntiaika on.

1042
00:42:34,770 --> 00:42:36,640
Niin ei vain voi pitää
paperinpaloja, jos Gabe,

1043
00:42:36,640 --> 00:42:38,640
et mielessä antaa
jokainen stressipallo.

1044
00:42:38,640 --> 00:42:42,100
Kiitos paljon meidän linkitetty lista
Vapaaehtoisten täällä, jos voisit.

1045
00:42:42,100 --> 00:42:45,320
>> [APPLAUSE]

1046
00:42:45,320 --> 00:42:46,700
>> DAVID J. MALAN: Okei.

1047
00:42:46,700 --> 00:42:51,110
Joten pari analyyttinen
kysymyksiä niin, jos voisin.

1048
00:42:51,110 --> 00:42:59,670
Olemme nähneet tämän merkintätapa ennen,
iso O ja omega, ylärajan

1049
00:42:59,670 --> 00:43:02,520
ja alarajat
ajoaika noin algoritmin.

1050
00:43:02,520 --> 00:43:04,950
Joten harkita vain
pari kysymystä.

1051
00:43:04,950 --> 00:43:07,090
>> Yksi, ja sanoimme sen
ennen, mikä on käynnissä

1052
00:43:07,090 --> 00:43:10,647
aika etsiä
lista kannalta iso O?

1053
00:43:10,647 --> 00:43:13,480
Mikä yläraja käynnissä
aika etsiä linkitetyn listan

1054
00:43:13,480 --> 00:43:16,340
toteutettuna vapaaehtoistemme täällä?

1055
00:43:16,340 --> 00:43:17,820
Se on iso O n, lineaarinen.

1056
00:43:17,820 --> 00:43:20,630
Koska pahimmassa tapauksessa,
elementti, kuten 55,

1057
00:43:20,630 --> 00:43:23,830
saatamme olla etsimässä voisi olla,
Jack oli aina lopussa.

1058
00:43:23,830 --> 00:43:28,250
Ja valitettavasti, toisin kuin array
emme voi saada fancy tällä kertaa.

1059
00:43:28,250 --> 00:43:31,820
Vaikka kaikki meidän ihmiset olivat
lajitellaan pienistä elementeistä, 5,

1060
00:43:31,820 --> 00:43:35,900
kaikki tavalla jopa isompi elementti,
55, joka on yleensä hyvä asia.

1061
00:43:35,900 --> 00:43:38,815
Mutta mitä se oletus
enää antaa meille mahdollisuuden tehdä?

1062
00:43:38,815 --> 00:43:39,775

1063
00:43:39,775 --> 00:43:40,650
Yleisö: [kuulumaton]

1064
00:43:40,650 --> 00:43:40,920
DAVID J. MALAN: Sano uudestaan?

1065
00:43:40,920 --> 00:43:41,800
Yleisö: Random access.

1066
00:43:41,800 --> 00:43:43,049
DAVID J. MALAN: Random access.

1067
00:43:43,049 --> 00:43:46,330
Ja taas se tarkoittaa, emme voi mitään
enää käytä heikko nollia, intuitio,

1068
00:43:46,330 --> 00:43:49,365
ja ilmeisyyttä binäärilukujen
etsiä ja jakaa ja valloittaa.

1069
00:43:49,365 --> 00:43:51,240
Sillä vaikka me
Ihmiset voisivat ilmeisesti

1070
00:43:51,240 --> 00:43:54,610
nähdä, että Andy tai kristitty olivat
suunnilleen keskellä luettelon,

1071
00:43:54,610 --> 00:43:57,670
tiedämme vain, että
tietokone kuorimalla lista

1072
00:43:57,670 --> 00:43:59,029
alusta alkaen.

1073
00:43:59,029 --> 00:44:00,570
Joten olemme luopuneet että random access.

1074
00:44:00,570 --> 00:44:04,380
>> Niin iso O n on nyt ylempi
sidottu meidän hakuaika.

1075
00:44:04,380 --> 00:44:07,920
Entä omega etsiä?

1076
00:44:07,920 --> 00:44:11,535
Mikä on alaraja etsimisestä
joillekin numero tässä listassa?

1077
00:44:11,535 --> 00:44:12,410
Yleisö: [kuulumaton]

1078
00:44:12,410 --> 00:44:13,040
DAVID J. MALAN: Sano uudestaan?

1079
00:44:13,040 --> 00:44:13,420
Yleisö: Yksi.

1080
00:44:13,420 --> 00:44:13,800
DAVID J. MALAN: One.

1081
00:44:13,800 --> 00:44:14,760
Niin vakioaikaisia.

1082
00:44:14,760 --> 00:44:17,020
Parhaassa tapauksessa Christine on
todellakin alussa luettelon.

1083
00:44:17,020 --> 00:44:19,020
Ja etsimme
numero 5, joten löysimme hänet.

1084
00:44:19,020 --> 00:44:19,787
Joten no big deal.

1085
00:44:19,787 --> 00:44:22,370
Mutta hänellä olevan
luettelon alkuun tässä asiassa.

1086
00:44:22,370 --> 00:44:23,745
Entä jotain Delete?

1087
00:44:23,745 --> 00:44:24,717

1088
00:44:24,717 --> 00:44:26,300
Mitä jos haluat poistaa elementin?

1089
00:44:26,300 --> 00:44:29,200
Mikä on yläraja ja alaraja
poistamisesta jotain sidoksissa

1090
00:44:29,200 --> 00:44:29,699
listata?

1091
00:44:29,699 --> 00:44:35,195

1092
00:44:35,195 --> 00:44:36,070
Yleisö: [kuulumaton]

1093
00:44:36,070 --> 00:44:36,420
DAVID J. MALAN: Sano uudestaan?

1094
00:44:36,420 --> 00:44:37,067
Yleisö: n.

1095
00:44:37,067 --> 00:44:38,900
DAVID J. MALAN: n on
todellakin yläraja.

1096
00:44:38,900 --> 00:44:41,700
Koska pahimmassa tapauksessa yritämme
poistaa Jack, kuten me vain teimme.

1097
00:44:41,700 --> 00:44:43,050
Hän on aina lopussa.

1098
00:44:43,050 --> 00:44:45,419
Vie meidät ikuisesti, tai
n vaiheet löytää hänet.

1099
00:44:45,419 --> 00:44:46,460
Niin, että yläraja.

1100
00:44:46,460 --> 00:44:47,430
Se on lineaarinen, varmasti.

1101
00:44:47,430 --> 00:44:50,970
Ja parhaassa tapauksessa ajoaika, tai
alarajoja parhaassa tapauksessa

1102
00:44:50,970 --> 00:44:51,975
olisi vakioaikaisia.

1103
00:44:51,975 --> 00:44:54,600
Koska ehkä me yritetään poistaa
Christine, ja me vain onnekas

1104
00:44:54,600 --> 00:44:55,558
hän alussa.

1105
00:44:55,558 --> 00:44:56,350
Hetkinen.

1106
00:44:56,350 --> 00:44:59,370
Gabe oli myös alussa,
ja meillä oli myös päivittää Gabe.

1107
00:44:59,370 --> 00:45:01,150
Niin että ei ollut vain yksi askel.

1108
00:45:01,150 --> 00:45:04,210
Onko siis todellakin jatkuvaa
aikaa, parhaassa tapauksessa

1109
00:45:04,210 --> 00:45:06,345
poistaa pienimmän alkion?

1110
00:45:06,345 --> 00:45:07,360

1111
00:45:07,360 --> 00:45:10,960
Se on, vaikka se voi olla kaksi,
kolme tai jopa 100 riviä koodia,

1112
00:45:10,960 --> 00:45:14,000
jos se on sama määrä
linjat, ei joissakin silmukka,

1113
00:45:14,000 --> 00:45:16,577
ja riippumaton koko
luettelon, ehdottomasti.

1114
00:45:16,577 --> 00:45:18,660
Poistamalla elementin
listan alkuun,

1115
00:45:18,660 --> 00:45:21,940
vaikka meidän on käsiteltävä
Gabe, on yhä jatkuva aika.

1116
00:45:21,940 --> 00:45:24,220
>> Joten tämä tuntuu
massiivinen askel taaksepäin.

1117
00:45:24,220 --> 00:45:27,000
Ja mitä ajanhukkaa
jos viikolla yksi ja viikko

1118
00:45:27,000 --> 00:45:30,250
nolla meillä oli paitsi
pseudokoodilla koodi mutta varsinainen koodi

1119
00:45:30,250 --> 00:45:35,780
toteuttaa jotain, joka on log
base n, tai kirjaudu pikemminkin N, pohja 2,

1120
00:45:35,780 --> 00:45:37,150
kannalta sen käyntiaika.

1121
00:45:37,150 --> 00:45:40,710
Joten miksi hitossa haluaisimme aloittaa
käyttäen jotain linkitetty lista?

1122
00:45:40,710 --> 00:45:41,517
Joo.

1123
00:45:41,517 --> 00:45:44,022
>> Yleisö: Joten voit lisätä
elementtejä array.

1124
00:45:44,022 --> 00:45:46,230
DAVID J. MALAN: Voit siis
lisätä elementtejä array.

1125
00:45:46,230 --> 00:45:47,550
Ja tämäkin on temaattinen.

1126
00:45:47,550 --> 00:45:49,740
Ja jatkamme nähdä
tämä, tämä kompromissi, paljon

1127
00:45:49,740 --> 00:45:51,573
kuten olemme nähneet
kompromissi yhdistämisjäljitystä tavallaan.

1128
00:45:51,573 --> 00:45:54,606
Voisimme todella nopeuttaa
etsiä tai lajittelu, pikemminkin

1129
00:45:54,606 --> 00:45:57,480
jos käytämme hieman enemmän tilaa ja
on vielä kimpale muistia

1130
00:45:57,480 --> 00:45:58,760
tai matriisia yhdistämisen lajitella.

1131
00:45:58,760 --> 00:46:01,270
Mutta kulutamme enemmän
tilaa, mutta säästämme aikaa.

1132
00:46:01,270 --> 00:46:04,820
Tässä tapauksessa olemme
luopumassa aikaa, mutta olemme

1133
00:46:04,820 --> 00:46:08,170
saada joustavuutta,
dynaamisuus jos haluatte,

1134
00:46:08,170 --> 00:46:10,280
joka on kiistatta myönteinen ominaisuus.

1135
00:46:10,280 --> 00:46:11,520
>> Olemme myös menoja tilaa.

1136
00:46:11,520 --> 00:46:13,710
Missä mielessä on sidoksissa
luetella kalliimpia

1137
00:46:13,710 --> 00:46:15,700
suhteen tilaa kuin array?

1138
00:46:15,700 --> 00:46:18,379

1139
00:46:18,379 --> 00:46:19,920
Jos on ylimääräistä tilaa tulee?

1140
00:46:19,920 --> 00:46:20,460
Joo?

1141
00:46:20,460 --> 00:46:21,800
>> Yleisö: [kuulumaton] osoitin.

1142
00:46:21,800 --> 00:46:23,310
>> DAVID J. MALAN: Joo, me
myös osoitin.

1143
00:46:23,310 --> 00:46:25,560
Joten tämä on minorly ärsyttävää
että enää am

1144
00:46:25,560 --> 00:46:27,780
Olen tallentamiseen vain int
edustaa int.

1145
00:46:27,780 --> 00:46:30,990
Olen tallentamiseen int ja
osoitin, joka on myös 32 bittiä.

1146
00:46:30,990 --> 00:46:33,470
Joten olen kirjaimellisesti kaksinkertaistaa
paljon tilaa mukana.

1147
00:46:33,470 --> 00:46:36,040
Niin, että kompromisseja, mutta
se kun on kyse int.

1148
00:46:36,040 --> 00:46:39,580
Oletetaan, että et ole tallentamiseen int,
mutta kai jokainen näistä suorakaide

1149
00:46:39,580 --> 00:46:43,290
tai kaikkien näiden ihmisten edusti
sana, Englanti sana, joka

1150
00:46:43,290 --> 00:46:46,430
voi olla viisi merkkiä, 10
merkkiä, ehkä jopa enemmän.

1151
00:46:46,430 --> 00:46:49,940
Sitten lisätään vain 32 enemmän bittejä
saattaa aiheuttaa vähemmän iso juttu.

1152
00:46:49,940 --> 00:46:52,160
>> Mitä jos jokainen opiskelijat
mielenosoitukseen

1153
00:46:52,160 --> 00:46:55,107
olivat kirjaimellisesti opiskelija structs että
on nimet ja taloja ja ehkä

1154
00:46:55,107 --> 00:46:57,065
puhelinnumeroita ja Twitter
käsittelee ja vastaavat.

1155
00:46:57,065 --> 00:46:59,564
Joten kaikki kentät aloitimme
puhumme toinen päivä,

1156
00:46:59,564 --> 00:47:02,410
paljon vähemmän iso juttu kuin
meidän solmut saavat mielenkiintoisempaa

1157
00:47:02,410 --> 00:47:05,972
ja iso viettää, eh, ylimääräinen
osoitin vain liittää ne yhteen.

1158
00:47:05,972 --> 00:47:07,180
Mutta tosiaan, se on kompromissi.

1159
00:47:07,180 --> 00:47:09,560
Ja todellakin, koodi on
monimutkaisempi, koska sinun

1160
00:47:09,560 --> 00:47:11,770
katso kuorimalla läpi
että erityinen esimerkki.

1161
00:47:11,770 --> 00:47:14,302
Mutta mitä jos oli
Joissakin Graalin malja täällä.

1162
00:47:14,302 --> 00:47:17,010
Mitä jos emme ota askel
taaksepäin mutta valtava edistysaskel

1163
00:47:17,010 --> 00:47:19,180
ja toteuttaa datan
rakenne, jonka kautta me

1164
00:47:19,180 --> 00:47:22,870
voi löytää elementtejä, kuten Jack tai
Christine tai muita osia

1165
00:47:22,870 --> 00:47:25,870
Tässä array totta vakioaikavälein?

1166
00:47:25,870 --> 00:47:26,920
Haku on jatkuva.

1167
00:47:26,920 --> 00:47:28,320
Delete on vakio.

1168
00:47:28,320 --> 00:47:29,570
Insertti on vakio.

1169
00:47:29,570 --> 00:47:32,260
Kaikki nämä toiminnot ovat vakioita.

1170
00:47:32,260 --> 00:47:33,750
Se olisi meidän pyhä Graal.

1171
00:47:33,750 --> 00:47:36,690
Ja sinne me
poimia seuraavan kerran.

1172
00:47:36,690 --> 00:47:38,600
Nähdään sitten.

1173
00:47:38,600 --> 00:47:39,371