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

2
00:00:00,500 --> 00:00:11,137
[Zenelejátszás]

3
00:00:11,137 --> 00:00:12,220
David J. MALAN: Rendben.

4
00:00:12,220 --> 00:00:13,950
Ez CS50.

5
00:00:13,950 --> 00:00:18,560
Ez a hét öt folytatódott, és mi
Van egy jó hír és egy rossz hír.

6
00:00:18,560 --> 00:00:21,140
Így jó hír, hogy CS50
indít pénteken.

7
00:00:21,140 --> 00:00:24,430
Ha szeretnél csatlakozni hozzánk,
irány a szokásos URL itt.

8
00:00:24,430 --> 00:00:28,670
Még jobb hír, nincs előadás
a jövő hétfő 13.

9
00:00:28,670 --> 00:00:31,970
Valamivel kevesebb jobb hír,
kvíz nulla jövő szerdán.

10
00:00:31,970 --> 00:00:33,840
További részletek
található ezen az URL-t ide.

11
00:00:33,840 --> 00:00:36,340
És az elkövetkező pár napra
fogunk kitöltésével az üres

12
00:00:36,340 --> 00:00:39,234
tekintettel a szobában
hogy mi lesz fenntartva.

13
00:00:39,234 --> 00:00:41,400
Jobb hír, hogy lesz majd
egy kurzus kiterjedő felülvizsgálat

14
00:00:41,400 --> 00:00:43,570
ülés a jövő
Hétfő este.

15
00:00:43,570 --> 00:00:46,270
Maradjanak velünk, hogy a tanfolyam
honlap hely és a részleteket.

16
00:00:46,270 --> 00:00:49,290
Szakaszok, bár ez egy
ünnep, akkor is eleget is.

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

18
00:00:50,490 --> 00:00:52,940
A legjobb hír, előadás jövő pénteken.

19
00:00:52,940 --> 00:00:56,220
Tehát ez egy hagyomány
van, mint egy a tananyag.

20
00:00:56,220 --> 00:00:58,100
Hogy-- lesz csodálatos.

21
00:00:58,100 --> 00:01:02,510
Látni fogja a dolgokat, mint
állandó idő adatszerkezetek

22
00:01:02,510 --> 00:01:04,730
és hash táblák és fák és próbál.

23
00:01:04,730 --> 00:01:07,150
És fogunk beszélni születésnapját problémákat.

24
00:01:07,150 --> 00:01:09,440
Egy csomó dolgot
várja jövő pénteken.

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
Egyébként.

28
00:01:13,190 --> 00:01:17,080
>> Úgy emlékszem, hogy már
összpontosítva ezt a képet, hogy mi van

29
00:01:17,080 --> 00:01:18,980
belsejében a számítógép memóriájában.

30
00:01:18,980 --> 00:01:22,875
Tehát a memória vagy RAM ahol programok
létezik, miközben futsz őket.

31
00:01:22,875 --> 00:01:25,215
Ha duplán rákattint egy
ikon futtatni néhány programot

32
00:01:25,215 --> 00:01:27,520
vagy kattintson duplán egy
icon nyitni néhány fájlt,

33
00:01:27,520 --> 00:01:30,430
meg van töltve a merevlemez
meghajtó vagy szilárdtest-meghajtó

34
00:01:30,430 --> 00:01:34,190
a RAM-ba, Random Access Memory, ahol
él, amíg a készülék ki nem kapcsol,

35
00:01:34,190 --> 00:01:36,700
A laptop fedél bezárul,
vagy kilép a programból.

36
00:01:36,700 --> 00:01:38,960
>> Most, hogy a memória, a
amit valószínűleg

37
00:01:38,960 --> 00:01:41,950
1 gigabájt ezekben a napokban, 2
gigabyte, vagy akár sokkal több,

38
00:01:41,950 --> 00:01:44,420
általában lefektetett
Ha egy adott programhoz

39
00:01:44,420 --> 00:01:47,170
ebben a fajta négyszögletes
fogalmi modell

40
00:01:47,170 --> 00:01:50,860
amelynek megvan a halom alján
és egy csomó más dolog a tetején.

41
00:01:50,860 --> 00:01:53,140
A dolog a legtetején
láttunk ezen a képen

42
00:01:53,140 --> 00:01:55,670
előtt, de soha nem beszélt
az úgynevezett szöveges szegmensben.

43
00:01:55,670 --> 00:01:58,419
Szöveg szegmens csak egy divatos
mondván a nullák és egyesek, hogy

44
00:01:58,419 --> 00:02:01,150
össze a tényleges lefordított program.

45
00:02:01,150 --> 00:02:03,910
>> Tehát, ha dupla kattintás
Microsoft Word a Mac vagy PC,

46
00:02:03,910 --> 00:02:08,030
vagy ha fut pont perjel Mario egy
Linux számítógép a terminál ablak,

47
00:02:08,030 --> 00:02:12,460
A nullák és egyesek alkotó
Szó vagy Mario ideiglenesen tárolja

48
00:02:12,460 --> 00:02:16,610
a számítógép RAM az úgynevezett
szöveg szegmens egy adott programot.

49
00:02:16,610 --> 00:02:19,080
Alatta megy inicializált
és inicializált adat.

50
00:02:19,080 --> 00:02:22,655
Ez a cucc, mint a globális változók,
hogy már nem használják sokan,

51
00:02:22,655 --> 00:02:24,910
de időnként mi már
volt globális változók

52
00:02:24,910 --> 00:02:28,819
vagy statikusan definiált vonósok hogy
Nehéz kódolt szavak, mint a "hello"

53
00:02:28,819 --> 00:02:31,860
hogy nem születnek meg a felhasználó
amelyek kódolva a programba.

54
00:02:31,860 --> 00:02:34,230
>> Most le az alul
van az úgynevezett stack.

55
00:02:34,230 --> 00:02:37,665
És a verem, eddig, voltunk
használ, milyen célból?

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

57
00:02:39,706 --> 00:02:40,997
Mi ez a halom használt?

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

59
00:02:41,160 --> 00:02:42,070
>> Közönség: funkciók.

60
00:02:42,070 --> 00:02:43,320
>> David J. MALAN: A funkciók?

61
00:02:43,320 --> 00:02:44,980
Milyen értelemben funkciókhoz?

62
00:02:44,980 --> 00:02:48,660
>> Közönség: ha hívja a funkció, a
érveket másolja a verembe.

63
00:02:48,660 --> 00:02:49,660
>> David J. MALAN: Pontosan.

64
00:02:49,660 --> 00:02:52,650
Ha hívja a funkció, a
érveket másolja a verembe.

65
00:02:52,650 --> 00:02:56,330
Így minden X vagy Y vagy A vagy B
hogy te halad egy funkció

66
00:02:56,330 --> 00:02:58,680
átmenetileg fel
az úgynevezett stack,

67
00:02:58,680 --> 00:03:02,000
mint az egyik Annenberg
étkező tálcák, és a dolgok,

68
00:03:02,000 --> 00:03:03,190
mint lokális változók.

69
00:03:03,190 --> 00:03:06,290
Ha a foo függvény vagy a csere
funkció van lokális változók,

70
00:03:06,290 --> 00:03:08,602
mint temp, a két
végén a verem.

71
00:03:08,602 --> 00:03:11,560
Most nem fogunk túl sokat beszélni
őket, de ezek a környezeti változók

72
00:03:11,560 --> 00:03:15,690
alul láttunk egy darabig ezelőtt, amikor
Én futzing a billentyűzet egy nap

73
00:03:15,690 --> 00:03:20,050
és elkezdtem hozzáférés dolgok
mint argv 100 vagy argv 1000,

74
00:03:20,050 --> 00:03:22,320
csak elements-- elfelejtem
a numbers-- de

75
00:03:22,320 --> 00:03:24,330
nem kellene hozzáférni engem.

76
00:03:24,330 --> 00:03:26,581
Elkezdtük látni néhány
funky szimbólumok a képernyőn.

77
00:03:26,581 --> 00:03:28,330
Ezek voltak az úgynevezett
környezeti változók

78
00:03:28,330 --> 00:03:32,390
mint globális beállításait a
program vagy a számítógéphez, nem

79
00:03:32,390 --> 00:03:37,090
független a közelmúltban
hiba, hogy megbeszéltük,

80
00:03:37,090 --> 00:03:39,670
Shellshock, hogy a már
sújtó jó néhány számítógép.

81
00:03:39,670 --> 00:03:42,960
>> Most végül, a mai fókusz
mi lesz végül a kupac.

82
00:03:42,960 --> 00:03:44,864
Ez egy másik darabja a memóriát.

83
00:03:44,864 --> 00:03:47,030
És alapvetően mindez
memória ugyanazokat a dolgokat.

84
00:03:47,030 --> 00:03:48,040
Ez ugyanaz a hardver.

85
00:03:48,040 --> 00:03:49,956
Mi csak egyfajta
kezelésére különböző klaszterek

86
00:03:49,956 --> 00:03:51,460
bájtok különböző célokra.

87
00:03:51,460 --> 00:03:56,540
A halom is lesz, ahol a
változók és a memória, amit kér

88
00:03:56,540 --> 00:03:58,810
Az operációs rendszer
ideiglenes tárolására használnak.

89
00:03:58,810 --> 00:04:01,890
>> De van olyan probléma
Itt is, mint a kép is jelzi.

90
00:04:01,890 --> 00:04:05,261
Mi a fajta két
hajó hamarosan összeütközik.

91
00:04:05,261 --> 00:04:08,010
Mert ahogy te és egyre
A verem, és mint látjuk ma

92
00:04:08,010 --> 00:04:11,800
től, mint használ egyre több a
halom, biztosan rossz dolgok történnek.

93
00:04:11,800 --> 00:04:15,054
És valóban, mi válthat ki, hogy
szándékosan vagy akaratlanul.

94
00:04:15,054 --> 00:04:16,970
Így a filmsorozat utolsó
Mikor volt ez a program,

95
00:04:16,970 --> 00:04:20,570
amely nem szolgál semmilyen funkcionális
más célja, mint annak bizonyítására,

96
00:04:20,570 --> 00:04:24,750
hogyan, mint egy rossz ember ténylegesen venni
előnye hibákat valaki programban

97
00:04:24,750 --> 00:04:28,460
és átveszi a programot, vagy akár a
teljes számítógépes rendszer vagy szerver.

98
00:04:28,460 --> 00:04:31,660
Tehát csak a pillanat röviden, te
észre, hogy legfontosabb az alján

99
00:04:31,660 --> 00:04:34,510
vesz parancssorban
érvek, mint egy ARGV.

100
00:04:34,510 --> 00:04:38,480
És van egy hívást egy f,
lényegében egy névtelen nevezett funkció

101
00:04:38,480 --> 00:04:40,250
f, és ez halad argv [1].

102
00:04:40,250 --> 00:04:43,960
>> Tehát bármi szó a felhasználó által a
A prompt után a program nevét,

103
00:04:43,960 --> 00:04:49,310
és akkor ez önkényes funkció fel
top, f, vesz egy string, AKA char *

104
00:04:49,310 --> 00:04:51,720
ahogy már elkezdték megvitatni,
és ez csak kéri, hogy "bar".

105
00:04:51,720 --> 00:04:53,310
De nevezhetjük bárminek.

106
00:04:53,310 --> 00:04:57,470
És akkor azt mondja, belül
f, egy sor karakter

107
00:04:57,470 --> 00:04:59,930
hívott C-- 12 ilyen karaktereket.

108
00:04:59,930 --> 00:05:03,580
>> Most, a történet, amit mesélt
Egy perce, amikor a memóriában

109
00:05:03,580 --> 00:05:06,720
c jelentése, vagy azok 12
karakter lesz a vége?

110
00:05:06,720 --> 00:05:07,570
Csak hogy világos legyen.

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

112
00:05:08,070 --> 00:05:08,590
>> Közönség: A verem.

113
00:05:08,590 --> 00:05:09,420
>> David J. MALAN: A verem.

114
00:05:09,420 --> 00:05:10,720
Így c egy lokális változó.

115
00:05:10,720 --> 00:05:14,079
Kérünk 12 karakter vagy 12 bájt.

116
00:05:14,079 --> 00:05:16,120
Azok fognak a végén
az úgynevezett stack.

117
00:05:16,120 --> 00:05:18,530
Most végre van egy másik funkciója
ez valóban nagyon hasznos,

118
00:05:18,530 --> 00:05:20,571
de már nem igazán használható
magunk, strncopy.

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

120
00:05:21,550 --> 00:05:25,200
Ez azt jelenti, húr példány, de
csak az N betű, n karaktereket.

121
00:05:25,200 --> 00:05:31,990
Így n karakter lesz
másolt rudat c.

122
00:05:31,990 --> 00:05:32,980
És hány?

123
00:05:32,980 --> 00:05:34,110
A hossza a bárban.

124
00:05:34,110 --> 00:05:36,330
Tehát más szavakkal, hogy a
egy vonal, strncopy,

125
00:05:36,330 --> 00:05:39,500
fogja másolni
hatékonyan bár a c.

126
00:05:39,500 --> 00:05:42,340
>> Most, csak azért, hogy milyen előre
A történet tanulsága,

127
00:05:42,340 --> 00:05:44,750
ami potenciálisan problematikus itt?

128
00:05:44,750 --> 00:05:49,710
Annak ellenére, hogy mi ellenőrzése hosszát
A bár és halad azt strncopy,

129
00:05:49,710 --> 00:05:53,145
mi a bél mondom az
még mindig sérült erről a programról?

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

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

132
00:05:55,220 --> 00:05:57,491
>> KÖZÖNSÉG: nem tartalmazza
hely a null karakter.

133
00:05:57,491 --> 00:05:59,990
David J. MALAN: nem tartalmazza
hely a null karakter.

134
00:05:59,990 --> 00:06:02,073
Potenciálisan, ellentétben
korábbi gyakorlat még csak nem is

135
00:06:02,073 --> 00:06:04,810
annyi, mint a plusz 1-től
befogadására, hogy null karakter.

136
00:06:04,810 --> 00:06:06,649
De ez még annál is rosszabb.

137
00:06:06,649 --> 00:06:07,940
Mi mást is mivel nem kell csinálni?

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

139
00:06:08,432 --> 00:06:09,307
>> KÖZÖNSÉG: [nem hallható]

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

141
00:06:15,440 --> 00:06:16,440
David J. MALAN: Tökéletes.

142
00:06:16,440 --> 00:06:18,490
Már bedrótozott 12 szép önkényesen.

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

144
00:06:19,497 --> 00:06:21,330
Ez nem annyira a
probléma, hanem az a tény,

145
00:06:21,330 --> 00:06:25,630
hogy még csak nem is ellenőrizhető, hogy
bár a hossza kisebb, mint 12,

146
00:06:25,630 --> 00:06:28,530
ebben az esetben lesz
nyugodtan tedd be a memóriába

147
00:06:28,530 --> 00:06:30,260
c néven, hogy már kiosztott.

148
00:06:30,260 --> 00:06:32,960
Valóban, ha bár mint
20 karakter hosszú,

149
00:06:32,960 --> 00:06:39,010
Ez a funkció úgy tűnik, hogy a másolás
20 karakter a rudat c, ezáltal

150
00:06:39,010 --> 00:06:41,310
figyelembe legalább 8 bájt
hogy ne legyen.

151
00:06:41,310 --> 00:06:42,690
Ez a gondolat itt.

152
00:06:42,690 --> 00:06:44,347
>> Tehát röviden, hibás program.

153
00:06:44,347 --> 00:06:45,180
Nem olyan nagy ügy.

154
00:06:45,180 --> 00:06:46,360
Lehet, hogy kap egy szegmentációs hiba.

155
00:06:46,360 --> 00:06:47,651
Mindannyian hibásak a programokban.

156
00:06:47,651 --> 00:06:50,196
Mindannyian volna hibát
programok most.

157
00:06:50,196 --> 00:06:51,320
De mi a következménye?

158
00:06:51,320 --> 00:06:54,390
Nos, itt van egy felnagyított változata
hogy kép a számítógép memóriájában.

159
00:06:54,390 --> 00:06:56,230
Ez az alsó az én verem.

160
00:06:56,230 --> 00:06:59,644
És valóban, a legalján az, ami
nevezett szülő rutin verem, divatos módja

161
00:06:59,644 --> 00:07:00,560
mondván, hogy ez fontosabb.

162
00:07:00,560 --> 00:07:03,772
Úgy, hogy aki nevezett funkció
f hogy beszélünk.

163
00:07:03,772 --> 00:07:05,230
Szóval ez a köteg alján.

164
00:07:05,230 --> 00:07:06,640
Visszatérési cím van valami új.

165
00:07:06,640 --> 00:07:08,810
Ez mindig is ott volt,
mindig is azt a képet.

166
00:07:08,810 --> 00:07:10,440
Csak soha nem hívta rá a figyelmet.

167
00:07:10,440 --> 00:07:15,290
Mert kiderül, ahogy a C működik
hogy ha egy függvény meghívja a másik,

168
00:07:15,290 --> 00:07:18,780
nem csak az érvek, hogy a
funkció kap a verembe,

169
00:07:18,780 --> 00:07:22,470
nem csak a függvény helyi
változó kap a verembe,

170
00:07:22,470 --> 00:07:26,820
egy úgynevezett visszatérési cím
is kap tesz a verembe.

171
00:07:26,820 --> 00:07:33,330
Pontosabban, ha a fő hívások ize Main
saját címét a memóriában, ökör valami,

172
00:07:33,330 --> 00:07:38,240
hatékonyan kerül fel a verembe
hogy amikor f történik futtatása

173
00:07:38,240 --> 00:07:43,630
tudja, hogy hol ugrik vissza a szöveg
szegmens annak érdekében, hogy továbbra is a végrehajtó.

174
00:07:43,630 --> 00:07:47,760
>> Tehát, ha itt vagyunk fogalmilag,
A legfontosabb, akkor f hívódik.

175
00:07:47,760 --> 00:07:50,200
Hogyan f, hogy ki
a kézi vezérlés vissza?

176
00:07:50,200 --> 00:07:52,020
Nos, ez a kis
morzsa piros itt,

177
00:07:52,020 --> 00:07:54,978
az úgynevezett visszatérési címet, csak
ellenőrzés, mi az, hogy a feladó címét?

178
00:07:54,978 --> 00:07:57,039
Ó, hadd ugorjon vissza a ide.

179
00:07:57,039 --> 00:07:59,080
És ez egy kicsit
egy leegyszerűsítés,

180
00:07:59,080 --> 00:08:00,750
mert a nullák és egyesek
A fő technikailag

181
00:08:00,750 --> 00:08:01,967
itt a tech szegmensben.

182
00:08:01,967 --> 00:08:03,800
De ez az ötlet. f
csak azt tudni, hogy mi

183
00:08:03,800 --> 00:08:06,680
hogy ahol a szabályozás végül visszamegy.

184
00:08:06,680 --> 00:08:09,790
>> De ahogy a számítógépek
már régen lefektetett dolgok

185
00:08:09,790 --> 00:08:12,320
mint lokális változók és
érvek, mint ez.

186
00:08:12,320 --> 00:08:17,180
Tehát az első kép a
kék a verem keret f, így minden

187
00:08:17,180 --> 00:08:19,630
a memória, hogy f
különösen az használ.

188
00:08:19,630 --> 00:08:22,990
Tehát ennek megfelelően, észreveheti, hogy
bár ezen a képen.

189
00:08:22,990 --> 00:08:23,980
Bár volt az érv.

190
00:08:23,980 --> 00:08:27,240
És azt állította, hogy érvek
funkciókat kap a verembe.

191
00:08:27,240 --> 00:08:29,910
És c, természetesen,
is ezt a képet.

192
00:08:29,910 --> 00:08:33,520
>> És csak a jelölési célokra,
észre a bal felső sarokban

193
00:08:33,520 --> 00:08:37,020
mi kerülne c tartó 0 és
majd enyhén jobbra le

194
00:08:37,020 --> 00:08:38,220
a c konzol 11.

195
00:08:38,220 --> 00:08:41,240
Más szóval, el lehet képzelni
hogy van egy rács bájtok

196
00:08:41,240 --> 00:08:44,380
ott, amelynek első
bal felső, alsó, amely

197
00:08:44,380 --> 00:08:48,360
az utolsó a 12 bájt.

198
00:08:48,360 --> 00:08:49,930
>> De most megpróbál a gyors előre.

199
00:08:49,930 --> 00:08:55,580
Mi fog történni, ha át
egy karakterlánc bárban, ami hosszabb, mint c?

200
00:08:55,580 --> 00:08:59,130
És mi nem ellenőrizhető, hogy
ez valóban több, mint 12.

201
00:08:59,130 --> 00:09:03,146
Melyik része ez a kép fog
kap felülírja byte 0, 1, 2, 3,

202
00:09:03,146 --> 00:09:07,890
dot dot dot, 11, majd a
rossz, 12, 13 19 keresztül?

203
00:09:07,890 --> 00:09:11,820
Mi fog történni itt,
ha arra következtetnek a rendelési

204
00:09:11,820 --> 00:09:14,790
hogy c konzol a 0 a legjobb
és c konzol 11 fajta lefelé

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

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

207
00:09:16,796 --> 00:09:19,260
>> Közönség: Nos, ez lesz
felülírja a char * bár.

208
00:09:19,260 --> 00:09:22,260
>> David J. MALAN: Igen, úgy néz ki, mint
fogsz felülírni char * bár.

209
00:09:22,260 --> 00:09:26,245
És ami még rosszabb, ha küld egy nagyon hosszú
húr, akkor talán még felülírja mi?

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

211
00:09:27,460 --> 00:09:28,570
A feladó címét.

212
00:09:28,570 --> 00:09:31,380
Ami megint, olyan, mint egy
morzsa, hogy elmondja a program, ahol

213
00:09:31,380 --> 00:09:34,060
hogy menjen vissza, amikor f
történik, hogy hívják.

214
00:09:34,060 --> 00:09:37,140
>> Szóval, mi a rossz fiúk általában nem
, ha azok találkoznak a programot

215
00:09:37,140 --> 00:09:41,290
hogy ők kíváncsiak, hogy az
kihasználható, buggy úgy

216
00:09:41,290 --> 00:09:43,550
hogy ő tehet
előnye, hogy a hiba,

217
00:09:43,550 --> 00:09:45,720
általában nem kap
ez jobb az első alkalommal.

218
00:09:45,720 --> 00:09:48,590
Csak megkezdéséhez, például,
véletlenszerű húrok a programba,

219
00:09:48,590 --> 00:09:50,260
akár a billentyűzet,
vagy őszintén valószínűleg

220
00:09:50,260 --> 00:09:52,740
írni egy kis programot, hogy csak
automatikusan generál vonósok,

221
00:09:52,740 --> 00:09:55,430
és meg kell kezdeni dörömböl a program
küldés sok különböző bemenetek

222
00:09:55,430 --> 00:09:56,340
A különböző hosszúságú.

223
00:09:56,340 --> 00:09:58,990
>> Amint a program lefagy,
ez egy csodálatos dolog.

224
00:09:58,990 --> 00:10:01,020
Mert ez azt jelenti, hogy
vagy ő fedezte fel

225
00:10:01,020 --> 00:10:02,660
ami talán valóban egy hiba.

226
00:10:02,660 --> 00:10:05,830
És akkor lehet, hogy több okos
és meg kell kezdeni összpontosítva szűkebben

227
00:10:05,830 --> 00:10:07,420
hogyan kell kihasználni a bogarat.

228
00:10:07,420 --> 00:10:11,480
Különösen, amit ő talán
tennie, hogy küld, a legjobb esetben, helló.

229
00:10:11,480 --> 00:10:12,210
Nem nagy ügy.

230
00:10:12,210 --> 00:10:14,750
Ez egy sor, ami elég rövid.

231
00:10:14,750 --> 00:10:18,100
De mi van, ha ő küld,
és mi általánosítani azt,

232
00:10:18,100 --> 00:10:20,890
támadás code-- így nulla
és is, hogy a dolgok

233
00:10:20,890 --> 00:10:25,150
mint rm-rf, hogy távolítsa el minden
A merevlemez vagy kéretlen levelek küldésére

234
00:10:25,150 --> 00:10:27,000
vagy valamilyen módon megtámadják a gép?

235
00:10:27,000 --> 00:10:29,570
>> Tehát, ha minden ilyen
betűk csak képviseli,

236
00:10:29,570 --> 00:10:32,380
fogalmilag, támadás, támadás,
támadás, támadás, egy rossz kód

237
00:10:32,380 --> 00:10:36,410
hogy valaki más írta, de
ha ez a személy elég okos ahhoz,

238
00:10:36,410 --> 00:10:40,790
hogy nem csak a minden
RM-e RFS, hanem

239
00:10:40,790 --> 00:10:46,100
már ő az utolsó néhány byte
egy szám, amely megfelel

240
00:10:46,100 --> 00:10:50,540
A cím az ő
vagy a saját támadó kódot

241
00:10:50,540 --> 00:10:53,820
hogy ő át mindössze
azáltal, hogy a gyors,

242
00:10:53,820 --> 00:10:58,760
akkor hatékonyan becsapni a számítógép
figyelembe vette észre, amikor az f kész végrehajtása,

243
00:10:58,760 --> 00:11:02,400
Ó, itt az ideje, hogy ugrik
vissza a piros feladó címét.

244
00:11:02,400 --> 00:11:06,070
Hanem azért, mert ő is valahogy
átfedésben hogy visszatérési cím

245
00:11:06,070 --> 00:11:09,602
saját szám,
és ők elég okosak

246
00:11:09,602 --> 00:11:11,560
volna kialakítani, hogy
szám hivatkozni, mint te

247
00:11:11,560 --> 00:11:13,740
lásd a szuper felső
bal sarokban,

248
00:11:13,740 --> 00:11:18,020
az aktuális cím a számítógép
emlékét azok egyes támadó kódot,

249
00:11:18,020 --> 00:11:21,740
rossz ember lehet becsapni a számítógép
a végrehajtó a saját kódját.

250
00:11:21,740 --> 00:11:23,700
>> És a kódot, megint, bármi lehet.

251
00:11:23,700 --> 00:11:26,120
Ez általában az úgynevezett
shell kód, ami csak

252
00:11:26,120 --> 00:11:29,030
oly módon, mondván, hogy ez nem
általában valami olyan egyszerű, mint a rm-rf.

253
00:11:29,030 --> 00:11:32,340
Ez valójában olyasmi, mint Bash,
vagy a tényleges program, amely őt

254
00:11:32,340 --> 00:11:37,230
vagy a programozott ellenőrzés végrehajtását
mást, hogy akarnak.

255
00:11:37,230 --> 00:11:40,210
Tehát röviden, ez az egész
abból az egyszerű tény,

256
00:11:40,210 --> 00:11:44,490
hogy ez a hiba szó nem ellenőrzés
a határait a tömb.

257
00:11:44,490 --> 00:11:47,250
És mivel az út
számítógépek az, hogy a munka

258
00:11:47,250 --> 00:11:49,430
használja az oszlopot
hatékonyan, fogalmilag,

259
00:11:49,430 --> 00:11:54,830
akár alulról, de aztán az elemek
tolja a verembe nő felülről lefelé,

260
00:11:54,830 --> 00:11:56,624
Ez hihetetlenül problematikus.

261
00:11:56,624 --> 00:11:58,290
Nos, vannak olyan módon, hogy a munka körül ezt.

262
00:11:58,290 --> 00:12:00,800
És őszintén szólva, vannak nyelvek
amellyel a munka körül ezt.

263
00:12:00,800 --> 00:12:03,100
Java immunrendszer, például,
hogy az adott kérdés.

264
00:12:03,100 --> 00:12:04,110
Mert nem kapsz mutatókat.

265
00:12:04,110 --> 00:12:05,943
Nem kapsz
közvetlen memória címeket.

266
00:12:05,943 --> 00:12:08,560
Tehát ez az erő, hogy mi
nyúljon semmihez a memóriában

267
00:12:08,560 --> 00:12:11,580
azt akarjuk, jön, igaz, nagy a kockázata.

268
00:12:11,580 --> 00:12:12,430
>> Így tartsa a szemét.

269
00:12:12,430 --> 00:12:14,596
Ha őszintén szólva, a következő hónapokban
vagy az elkövetkező években, bármikor

270
00:12:14,596 --> 00:12:17,740
olvastam néhány kizsákmányolás
a program vagy a szerveren,

271
00:12:17,740 --> 00:12:22,370
Ha valaha is látni egy csipetnyi valami
mint a buffer overflow támadás,

272
00:12:22,370 --> 00:12:25,390
vagy stack túlcsordulás egy másik típusa
A támadás, hasonló szellemben,

273
00:12:25,390 --> 00:12:28,770
mint inspirálja a honlap
neve, ha tudod,

274
00:12:28,770 --> 00:12:33,170
ez mind beszél, csak
tele a mérete néhány karakter

275
00:12:33,170 --> 00:12:36,200
array vagy néhány tömb általában.

276
00:12:36,200 --> 00:12:38,822
Bármilyen kérdése van, akkor ezen?

277
00:12:38,822 --> 00:12:39,780
Ne próbáld ki otthon.

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

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

280
00:12:42,300 --> 00:12:47,270
Tehát malloc eddig volt új
barátom, hogy tudjuk lefoglalni memóriát

281
00:12:47,270 --> 00:12:50,540
hogy nem feltétlenül tudja, hogy a
előre, hogy mi szeretnénk, így nem kell

282
00:12:50,540 --> 00:12:52,920
kemény kód a mi
programok száma, mint a 12.

283
00:12:52,920 --> 00:12:55,550
Ha a felhasználó azt mondja, hogy mennyi
adatokat, vagy akar bemenet,

284
00:12:55,550 --> 00:12:58,000
akkor malloc, hogy sok memóriát.

285
00:12:58,000 --> 00:13:01,484
>> Így malloc kiderül, hogy a
mennyiben már nem, pedig,

286
00:13:01,484 --> 00:13:03,900
kifejezetten utoljára, majd a
srácok már használja

287
00:13:03,900 --> 00:13:08,160
A getString tudatlanul az
Néhány hét minden malloc memória

288
00:13:08,160 --> 00:13:09,820
származik az úgynevezett kupac.

289
00:13:09,820 --> 00:13:13,852
És ez az, amiért getString, például,
lehet lefoglalni memóriát dinamikusan

290
00:13:13,852 --> 00:13:16,060
anélkül, hogy tudnánk, mit te
majd írja előre,

291
00:13:16,060 --> 00:13:21,520
adja vissza a mutatót, hogy az emlékezet,
és hogy az emlékezet még mindig a tiéd, hogy,

292
00:13:21,520 --> 00:13:24,080
után is getString visszatér.

293
00:13:24,080 --> 00:13:27,450
Mivel a visszahívás után is, hogy a
verem folyamatosan megy fel és le,

294
00:13:27,450 --> 00:13:27,950
felfelé és lefelé.

295
00:13:27,950 --> 00:13:30,230
És amint megy
le, hogy minden olyan memória

296
00:13:30,230 --> 00:13:33,030
ezt a funkciót használni kellene
nem használhatja bárki más.

297
00:13:33,030 --> 00:13:34,570
Ez szemét értékeket most.

298
00:13:34,570 --> 00:13:36,120
>> De a rakás itt.

299
00:13:36,120 --> 00:13:39,360
És mi a szép a malloc, hogy
ha malloc memóriát itt,

300
00:13:39,360 --> 00:13:42,070
ez nem befolyásolja, a
legnagyobb részben a verem.

301
00:13:42,070 --> 00:13:46,000
És így minden funkció eléréséhez
memória, amelyet malloc segítségével lefoglalt,

302
00:13:46,000 --> 00:13:49,120
még egy funkció, mint a getstring,
után is vissza.

303
00:13:49,120 --> 00:13:51,700
>> Most az ellenkezője a malloc ingyenes.

304
00:13:51,700 --> 00:13:53,900
És valóban, a szabály akkor
kell kezdeni elfogadása

305
00:13:53,900 --> 00:13:58,950
minden olyan, minden, minden alkalommal, amikor használja malloc
akkor magad használni szabad, végül,

306
00:13:58,950 --> 00:14:00,280
ugyanezen mutató.

307
00:14:00,280 --> 00:14:03,289
Egész idő alatt mi is írásban
hibás, hibás kód, több okból.

308
00:14:03,289 --> 00:14:05,580
De az egyik, amely már
a CS50 könyvtár, amely

309
00:14:05,580 --> 00:14:09,010
Maga szándékosan
buggy, azt memóriavesztést.

310
00:14:09,010 --> 00:14:11,410
Minden alkalommal, amikor már hívott getstring
Az elmúlt néhány hét alatt

311
00:14:11,410 --> 00:14:13,870
kérünk az üzemeltetési
rendszer, a Linux, a memória.

312
00:14:13,870 --> 00:14:15,780
És még egyszer sem adott vissza.

313
00:14:15,780 --> 00:14:17,730
És ez nem, a
gyakorlat, egy jó dolog.

314
00:14:17,730 --> 00:14:20,330
>> És Valgrind egyik
eszközök bevezetett Pset 4,

315
00:14:20,330 --> 00:14:22,900
szól segít
most meg a hibákat, mint ezt.

316
00:14:22,900 --> 00:14:27,060
De szerencsére az Pset 4 nem szükséges
használja a CS50 könyvtár vagy getstring.

317
00:14:27,060 --> 00:14:31,220
Tehát bármilyen hibát kapcsolatos emlékezet
végül lesz saját.

318
00:14:31,220 --> 00:14:34,060
>> Tehát malloc több, mint
kényelmes erre a célra.

319
00:14:34,060 --> 00:14:37,420
Mi is valójában már megoldani
alapvetően eltérő problémákkal,

320
00:14:37,420 --> 00:14:41,640
és alapvetően megoldja a felmerült problémákat
hatékonyan hetente nulla ígérete.

321
00:14:41,640 --> 00:14:44,720
Eddig ez a legszexisebb
adatstruktúra már volt.

322
00:14:44,720 --> 00:14:47,804
És adatstruktúra Úgy értem
egy módja fogalomalkotó memória

323
00:14:47,804 --> 00:14:50,720
oly módon, hogy túlmutat csak azt mondom,
ez egy int, ez egy char.

324
00:14:50,720 --> 00:14:52,930
Elkezdhetjük klaszter dolgokat.

325
00:14:52,930 --> 00:14:54,460
>> Tehát egy sor így nézett ki.

326
00:14:54,460 --> 00:14:57,270
És mi volt a kulcs, körülbelül egy
tömb, hogy ad

327
00:14:57,270 --> 00:14:59,724
back-to-back darabok
memória, amelyek mindegyike

328
00:14:59,724 --> 00:15:02,765
lesz az azonos típusú, int,
int, int, int vagy char, char, char,

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

330
00:15:03,330 --> 00:15:04,496
De van egy rossz oldala is.

331
00:15:04,496 --> 00:15:06,570
Ez például,
tömb mérete hat.

332
00:15:06,570 --> 00:15:10,650
Tegyük fel, hogy töltse ki ezt a tömböt hat
számokat, majd bármilyen okból,

333
00:15:10,650 --> 00:15:13,187
a felhasználó akarja adni
Ön egy hetedik számot.

334
00:15:13,187 --> 00:15:14,020
Hová tetted?

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

336
00:15:15,490 --> 00:15:18,990
>> Mi a megoldás, ha
létrehozott egy tömböt a verem,

337
00:15:18,990 --> 00:15:22,030
például, csak a hét
két jelölés, hogy mi vezetett,

338
00:15:22,030 --> 00:15:23,730
A szögletes zárójelben egy szám benne?

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

340
00:15:25,160 --> 00:15:27,260
Nos, van hat
számok ezekben a dobozokban.

341
00:15:27,260 --> 00:15:28,530
Mi lenne az ösztönök is?

342
00:15:28,530 --> 00:15:29,973
Hol akarod, hogy ez?

343
00:15:29,973 --> 00:15:30,860
>> KÖZÖNSÉG: [nem hallható]

344
00:15:30,860 --> 00:15:31,315
>> David J. MALAN: Tessék?

345
00:15:31,315 --> 00:15:32,380
>> Közönség: Tedd a végén.

346
00:15:32,380 --> 00:15:33,796
>> David J. MALAN: Tedd a végén.

347
00:15:33,796 --> 00:15:35,880
Így alig több mint a jobb,
kívül ezt a dobozt.

348
00:15:35,880 --> 00:15:38,710
Ami jó lenne, de azt
Kiderül, hogy nem tehetem meg.

349
00:15:38,710 --> 00:15:41,350
Mert ha már nem kérte
e darab memória,

350
00:15:41,350 --> 00:15:44,490
ez lehet véletlen, hogy ez a
által használt más változó

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

352
00:15:45,030 --> 00:15:49,210
Gondolj vissza egy hét múlva, amikor meghatározott
ki Zamyla és Davin és Gabe nevét

353
00:15:49,210 --> 00:15:49,930
a memóriában.

354
00:15:49,930 --> 00:15:51,638
Ezek szó szerint
vissza háttal.

355
00:15:51,638 --> 00:15:53,550
Tehát nem feltétlenül
bízom benne, hogy bármi a

356
00:15:53,550 --> 00:15:55,800
itt áll rendelkezésre, hogy használjam.

357
00:15:55,800 --> 00:15:56,990
>> Szóval, mit lehet tenni?

358
00:15:56,990 --> 00:16:00,282
Nos, amint rájött, hogy
szüksége van egy sor méret hét,

359
00:16:00,282 --> 00:16:02,490
akkor csak létre
tömb mérete hét majd

360
00:16:02,490 --> 00:16:05,950
a for ciklus vagy egy while ciklus,
másold be az új tömb,

361
00:16:05,950 --> 00:16:09,680
és aztán valahogy csak megszabadulni
ezt a tömböt, vagy éppen ne használja azt.

362
00:16:09,680 --> 00:16:12,130
De ez nem különösebben hatékony.

363
00:16:12,130 --> 00:16:15,340
Röviden, a tömbök ne engedd
dinamikusan átméretezi.

364
00:16:15,340 --> 00:16:17,900
>> Így egyrészt kapsz
véletlen elérésű, ami elképesztő.

365
00:16:17,900 --> 00:16:20,108
Mert ez lehetővé teszi számunkra, hogy a dolgokat
mint oszd meg és uralkodj,

366
00:16:20,108 --> 00:16:23,100
bináris keresés, mind amit már
beszélt a képernyőn itt.

367
00:16:23,100 --> 00:16:24,950
De festeni magad a sarokba.

368
00:16:24,950 --> 00:16:27,810
Amint eléred
a végén a tömb,

369
00:16:27,810 --> 00:16:29,980
meg kell csinálni egy nagyon
drága működés

370
00:16:29,980 --> 00:16:33,910
vagy írjon egy csomó kód
most kezelni ezt a problémát.

371
00:16:33,910 --> 00:16:36,680
>> Szóval, mi lenne, ha inkább volt
egy úgynevezett listán,

372
00:16:36,680 --> 00:16:38,820
vagy a kapcsolt lista különösen?

373
00:16:38,820 --> 00:16:41,930
Mi van, ha ahelyett, hogy
téglalapok vissza, hogy háttal,

374
00:16:41,930 --> 00:16:45,730
van téglalapok hagy egy kis
kis kígyózik szoba között?

375
00:16:45,730 --> 00:16:49,670
És bár én készült ez
kép vagy alkalmassá ezt a képet

376
00:16:49,670 --> 00:16:54,696
az egyik a szövegek itt, hogy újra
háttal nagyon rendezett, a valóságban,

377
00:16:54,696 --> 00:16:56,820
az egyik ilyen téglalap
Lehet itt a memóriában.

378
00:16:56,820 --> 00:16:58,028
Egyikük lehet itt.

379
00:16:58,028 --> 00:17:00,420
Egyikük lehet itt,
ide, és így tovább.

380
00:17:00,420 --> 00:17:02,910
>> De mi van, ha rajzolt,
Ebben az esetben, nyilak

381
00:17:02,910 --> 00:17:05,650
hogy valahogy össze ezt a
téglalapok együtt?

382
00:17:05,650 --> 00:17:08,170
Sőt, láttunk egy technikai
megtestesülése egy nyíl.

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

384
00:17:09,839 --> 00:17:13,710
Mit használtunk az elmúlt
nap, hogy a motorháztető alatt,

385
00:17:13,710 --> 00:17:15,210
reprezentatív nyíl?

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

387
00:17:16,290 --> 00:17:17,349
A mutató, igaz?

388
00:17:17,349 --> 00:17:19,780
>> Mi van, ha ahelyett, hogy
csak tárolja a számokat,

389
00:17:19,780 --> 00:17:23,130
mint a 9., 17., 22., 26., 34.,
Mi van, ha a tárolt nem

390
00:17:23,130 --> 00:17:27,079
csak egy telefonszámot, de a mutató
mellett minden ilyen szám?

391
00:17:27,079 --> 00:17:30,690
Annak érdekében, hogy ugyanúgy, mint akkor menet a
tűt egy csomó szövet,

392
00:17:30,690 --> 00:17:32,950
valahogy árukapcsolás dolgok
együtt, mint szintén

393
00:17:32,950 --> 00:17:35,550
mi a mutatók, mint
inkarnálódott nyilak itt,

394
00:17:35,550 --> 00:17:38,550
fajta szövik együtt
ezek az egyes téglalapok

395
00:17:38,550 --> 00:17:41,780
által ténylegesen egy mutató
mellett minden szám

396
00:17:41,780 --> 00:17:46,065
rámutat néhány a következő számot, hogy
mutat, viszont, néhány a következő szám?

397
00:17:46,065 --> 00:17:47,940
Más szóval, mi
ha valóban akarta

398
00:17:47,940 --> 00:17:49,820
végrehajtása ilyesmit?

399
00:17:49,820 --> 00:17:53,610
Hát sajnos, ezek a téglalap,
legalább az egyik a 9., 17., 22.,

400
00:17:53,610 --> 00:17:57,040
és így tovább, ezek már nem
szép terek egyetlen számokat.

401
00:17:57,040 --> 00:17:59,960
Az alsó, téglalap
9 alatti, például,

402
00:17:59,960 --> 00:18:04,330
képviseli azt, amit kellene
egy mutató, 32 bit.

403
00:18:04,330 --> 00:18:09,460
Nos, én nem vagyok még tisztában bármilyen adattípus
C-ben, hogy ad nem csak egy int

404
00:18:09,460 --> 00:18:11,630
de a mutató teljesen.

405
00:18:11,630 --> 00:18:15,020
>> Szóval, mi a megoldás, ha azt akarjuk
kitalálni a saját válasza erre?

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

407
00:18:15,760 --> 00:18:16,640
>> KÖZÖNSÉG: [nem hallható]

408
00:18:16,640 --> 00:18:17,360
>> David J. MALAN: Mi ez?

409
00:18:17,360 --> 00:18:17,880
>> Közönség: új struktúrát.

410
00:18:17,880 --> 00:18:19,590
>> David J. MALAN: Igen, miért
nem hozunk létre egy új struktúra,

411
00:18:19,590 --> 00:18:20,920
vagy C, a struktúra?

412
00:18:20,920 --> 00:18:25,990
Láttuk Struktúrák korábban, ha röviden,
ahol foglalkozott a diák szerkezet

413
00:18:25,990 --> 00:18:27,780
mint ez, akinek a neve és a házat.

414
00:18:27,780 --> 00:18:31,980
A Pset 3 kitörési használt egész
csomó structs-- GRect és GOvals

415
00:18:31,980 --> 00:18:34,810
hogy Stanford létrehozott
fürtinformációit együtt.

416
00:18:34,810 --> 00:18:38,580
Szóval, mi lenne, ha ezt azonos ötlet
a kulcsszavak "typedef" és "struct"

417
00:18:38,580 --> 00:18:42,890
majd néhány diák-specifikus dolog,
és fejlődik ez a következő:

418
00:18:42,890 --> 00:18:46,210
typedef struct node-- és csomópont
csak egy nagyon általános számítógép-tudomány

419
00:18:46,210 --> 00:18:49,980
kifejezés valamit egy adat struktúra,
egy tartályt egy adatszerkezetet.

420
00:18:49,980 --> 00:18:53,900
A csomópont Állítom megy, hogy
egy int n, teljesen egyértelmű,

421
00:18:53,900 --> 00:18:58,810
, majd egy kicsit rejtélyesen,
A második vonal, struct csomópont * mellett.

422
00:18:58,810 --> 00:19:01,300
De kevesebb technikai értelemben,
mi az, hogy a második sor

423
00:19:01,300 --> 00:19:02,980
kód belsejében a kapcsos zárójelek?

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

425
00:19:03,737 --> 00:19:04,851
>> KÖZÖNSÉG: [nem hallható]

426
00:19:04,851 --> 00:19:06,600
David J. MALAN: A
Mutató a másik csomópont.

427
00:19:06,600 --> 00:19:09,910
Tehát igaz, mondattani kissé rejtélyes.

428
00:19:09,910 --> 00:19:13,250
De ha olvasod a szó szoros értelmében,
következő a neve a változó.

429
00:19:13,250 --> 00:19:14,410
Mi a adattípus?

430
00:19:14,410 --> 00:19:18,206
Ez egy kicsit bőbeszédű ebben az időben,
de ez a típus struct csomópont *.

431
00:19:18,206 --> 00:19:22,960
Minden alkalommal láttunk valami csillag, hogy
azt jelenti, hogy egy mutatót, amely az adatok típusát.

432
00:19:22,960 --> 00:19:26,810
Így a következő látszólag a
pointert a struct csomópont.

433
00:19:26,810 --> 00:19:28,310
>> Nos, mi a struct csomópont?

434
00:19:28,310 --> 00:19:31,044
Nos, észre látod azokat
ugyanazokat a szavakat a jobb felső sarokban.

435
00:19:31,044 --> 00:19:33,960
És valóban, akkor is látni a szó
"Node" itt a bal alsó sarokban.

436
00:19:33,960 --> 00:19:35,640
És ez valójában csak a kényelem.

437
00:19:35,640 --> 00:19:39,930
Figyeljük meg, hogy a mi hallgatói definíció
ott van a "diák" csak egyszer.

438
00:19:39,930 --> 00:19:42,510
És ez azért van, mert egy diák
objektum nem önreferenciálisak.

439
00:19:42,510 --> 00:19:45,340
Nincs benne semmi a diák
hogy kell, hogy pont a másik diák,

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

441
00:19:45,610 --> 00:19:47,630
Ez lenne a fajta
furcsa a valós világban.

442
00:19:47,630 --> 00:19:50,880
>> De egy csomópont a kapcsolt
lista, mi szeretnénk egy csomópont

443
00:19:50,880 --> 00:19:53,970
hogy referenciális egy hasonló objektumot.

444
00:19:53,970 --> 00:19:57,900
És így a változást itt nem
csak mi van benne a kapcsos zárójeleket.

445
00:19:57,900 --> 00:20:00,800
De hozzá a "csomópont"
a tetején, valamint

446
00:20:00,800 --> 00:20:02,930
hozzátéve, hogy az alsó
helyett "tanuló".

447
00:20:02,930 --> 00:20:06,000
És ez csak egy technikai részlet
úgy, hogy ismét az adatok szerkezete

448
00:20:06,000 --> 00:20:11,380
lehet saját referenciális, úgy, hogy a
csomópont is pont egy ilyen csomópont.

449
00:20:11,380 --> 00:20:13,840
>> Szóval mi ez a végső soron
fog jelenteni számunkra?

450
00:20:13,840 --> 00:20:17,560
Nos, az egyik, ez a cucc benne
a tartalma a csomópontot.

451
00:20:17,560 --> 00:20:19,360
Ez a dolog itt,
jobb felső, csak annyira

452
00:20:19,360 --> 00:20:20,860
hogy ismét tudunk hivatkozni magunkat.

453
00:20:20,860 --> 00:20:23,401
És akkor a legtávolabbi dolog,
noha csomópont egy új kifejezés,

454
00:20:23,401 --> 00:20:25,500
talán még mindig a
ugyanaz, mint a diák, és milyen

455
00:20:25,500 --> 00:20:27,520
volt a motorháztető alatt az SPL.

456
00:20:27,520 --> 00:20:31,095
>> Tehát, ha most akartam kezdeni
végrehajtásáért láncolt lista,

457
00:20:31,095 --> 00:20:33,220
hogyan tudnánk fordítani
valami ilyesmit kell a kódot?

458
00:20:33,220 --> 00:20:35,350
Nos, nézzük meg egy
Például, hogy a program

459
00:20:35,350 --> 00:20:36,840
valójában használ láncolt lista.

460
00:20:36,840 --> 00:20:40,870
Napjaink eloszlás kód
egy program neve List Zero.

461
00:20:40,870 --> 00:20:44,980
És ha én vezetem ezt hoztam létre egy szuper
egyszerű GUI, grafikus felhasználói felület,

462
00:20:44,980 --> 00:20:46,460
de ez tényleg csak printf.

463
00:20:46,460 --> 00:20:50,930
És most adtam magamnak néhány menüt
options-- Törlés, Beszúrás, Keresés,

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

465
00:20:51,750 --> 00:20:52,630
És kilép.

466
00:20:52,630 --> 00:20:55,970
Ezek csak a közös műveleteket a
adatstruktúra ismert, mint egy link listát.

467
00:20:55,970 --> 00:20:58,409
>> Most, Törlés fog
Szám törlése a listából.

468
00:20:58,409 --> 00:21:00,200
Insert fog hozzá
egy számot a listához.

469
00:21:00,200 --> 00:21:02,181
Keresés fog nézni
A szám a listán.

470
00:21:02,181 --> 00:21:04,930
És áthalad csak egy divatos módon
mondván, séta a listán,

471
00:21:04,930 --> 00:21:06,245
nyomtassa ki, de ennyi.

472
00:21:06,245 --> 00:21:07,720
Ne változtassa meg semmilyen módon.

473
00:21:07,720 --> 00:21:08,570
>> Szóval próbáld ki ezt.

474
00:21:08,570 --> 00:21:10,160
Menjünk előre, és 2-es típusú.

475
00:21:10,160 --> 00:21:12,710
És akkor fogok
helyezze be a számot, mondjuk 9.

476
00:21:12,710 --> 00:21:13,620
Az Enter billentyűt.

477
00:21:13,620 --> 00:21:17,480
És most a program csak
programozva, hogy mondjam, a lista már 9.

478
00:21:17,480 --> 00:21:20,190
Most, ha jól megy előre, és
Ne helyezze be újra, legyen

479
00:21:20,190 --> 00:21:23,680
menjek előre, és kicsinyítés és írja 17.

480
00:21:23,680 --> 00:21:25,770
Most a lista 9, majd 17.

481
00:21:25,770 --> 00:21:27,750
Ha megteszem helyezze újra, ugorjunk egyet.

482
00:21:27,750 --> 00:21:32,400
Ahelyett, hogy 22, mint egy kép mi már
már néztem itt, hadd ugrik előre

483
00:21:32,400 --> 00:21:34,630
és helyezze 26 Következő.

484
00:21:34,630 --> 00:21:36,230
Így fogok 26-os típus.

485
00:21:36,230 --> 00:21:37,755
Íme, a lista gondolom.

486
00:21:37,755 --> 00:21:40,630
De most, csak azért, hogy ha ez a kód
lesz rugalmas, hadd most

487
00:21:40,630 --> 00:21:43,520
22 típusú, amelyek közül legalább
fogalmilag, ha vagyunk

488
00:21:43,520 --> 00:21:46,520
Tartsa ezt válogatni, ami valóban
lesz egy másik cél most,

489
00:21:46,520 --> 00:21:48,690
kell menni a 17 és 26.

490
00:21:48,690 --> 00:21:50,270
Szóval az Enter leütése.

491
00:21:50,270 --> 00:21:51,380
Sőt, ami működik.

492
00:21:51,380 --> 00:21:54,950
És most hadd tegye be a
Végül, egy a kép, 34.

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

494
00:21:55,450 --> 00:21:58,980
Tehát most hadd előírják, hogy
Törlés és Traverse és Search csinálni,

495
00:21:58,980 --> 00:21:59,760
sőt, a munka.

496
00:21:59,760 --> 00:22:04,180
Sőt, ha én futni Search, nézzük
megkeresi a szám 22, Enter.

497
00:22:04,180 --> 00:22:05,010
Úgy ítélte meg, 22.

498
00:22:05,010 --> 00:22:07,580
Szóval, ez az, amit ez a
programok listája Zero nem.

499
00:22:07,580 --> 00:22:10,230
>> De mi is történt valójában
az, hogy megvalósítja ezt?

500
00:22:10,230 --> 00:22:14,530
Nos, először talán van, sőt
Nekem van egy nevű fájlt list0.h.

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

502
00:22:16,540 --> 00:22:20,690
És valahol itt van ez a
vonal, typedef struct csomópont,

503
00:22:20,690 --> 00:22:24,850
akkor ott van a kapcsos zárójelek, int n, és
akkor struct-- mi volt a meghatározás?

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

505
00:22:26,530 --> 00:22:28,545
Struct csomópont mellett.

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

507
00:22:29,920 --> 00:22:31,045
Tehát szükségünk van a csillag.

508
00:22:31,045 --> 00:22:33,420
Most technikailag belemennénk
a szokás rajz itt.

509
00:22:33,420 --> 00:22:35,670
Lehet látni a tankönyvek és
Online referenciák csinálni ott.

510
00:22:35,670 --> 00:22:36,660
Ez funkcionálisan egyenértékű.

511
00:22:36,660 --> 00:22:37,980
Tény, hogy ez egy kicsit több jellemző.

512
00:22:37,980 --> 00:22:40,563
De én leszek, ami megfelel
mi a múltkor, és nem ezt.

513
00:22:40,563 --> 00:22:42,350
És akkor végül, fogom csinálni.

514
00:22:42,350 --> 00:22:45,550
>> Tehát egy header fájlban
valahol, a list0.h

515
00:22:45,550 --> 00:22:49,200
ma ez a struktúra definíció,
és talán néhány egyéb dolog.

516
00:22:49,200 --> 00:22:52,580
Eközben list0c van
lesz egy pár dolgot.

517
00:22:52,580 --> 00:22:54,740
De megyünk csak
kezdeni és nem befejezni ezt.

518
00:22:54,740 --> 00:22:59,690
List0.h egy fájl akarok
tartalmazza az én C fájlban.

519
00:22:59,690 --> 00:23:03,910
Aztán egy bizonyos ponton vagyok
lesz int, a fő, semmis.

520
00:23:03,910 --> 00:23:06,530
És akkor fogok
néhány to-do itt.

521
00:23:06,530 --> 00:23:10,620
Én is megyek, hogy egy
prototípus, mint üres, keresés, int,

522
00:23:10,620 --> 00:23:13,610
n, amelynek célja az életben
keresni egy elem.

523
00:23:13,610 --> 00:23:18,310
És akkor itt azt állítják,
A mai kód, érvénytelen, keresés, int, n,

524
00:23:18,310 --> 00:23:21,020
nincs pontosvessző, de nyitott kapcsos zárójeleket.

525
00:23:21,020 --> 00:23:25,049
És most szeretném valahogy keresni
Egy elem a listában.

526
00:23:25,049 --> 00:23:27,340
De nem elég
információ a képernyőn még.

527
00:23:27,340 --> 00:23:29,800
Én valójában nem
képviselte a lista is.

528
00:23:29,800 --> 00:23:33,070
Tehát az egyik módja, hogy végre
A láncolt lista egy programban

529
00:23:33,070 --> 00:23:37,520
A Valahogy akarok valamit
mint kinyilváníthatja láncolt lista itt.

530
00:23:37,520 --> 00:23:40,520
Az egyszerűség kedvéért, én csinálok
ez a globális, bár általában mi

531
00:23:40,520 --> 00:23:41,645
nem kell ezt túl sokat.

532
00:23:41,645 --> 00:23:43,260
De ez egyszerűsíti ezt a példát.

533
00:23:43,260 --> 00:23:45,890
Szóval azt akarom, hogy állapítsa
láncolt lista itt.

534
00:23:45,890 --> 00:23:47,010
Nos, hogyan lehet ilyet?

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

536
00:23:48,810 --> 00:23:50,750
>> Itt van a kép egy láncolt lista.

537
00:23:50,750 --> 00:23:53,030
És én nem igazán
tudják, abban a pillanatban, hogy

538
00:23:53,030 --> 00:23:56,710
Én megyek a képviselő
Olyan sok dolog csak egy

539
00:23:56,710 --> 00:23:58,040
változó a memóriában.

540
00:23:58,040 --> 00:23:59,160
De gondolj vissza egy pillanatra.

541
00:23:59,160 --> 00:24:00,830
Egész idő alatt is megvolt
vonósok, amit aztán

542
00:24:00,830 --> 00:24:02,913
kiderült, hogy a tömbök
karakter, amit aztán

543
00:24:02,913 --> 00:24:05,740
kiderült, hogy csak egy mutató
Az első karakter

544
00:24:05,740 --> 00:24:08,890
egy sor karakter
ez null megszűnik.

545
00:24:08,890 --> 00:24:13,530
Tehát a logika, és ezzel
kép a fajta vetés a gondolatait,

546
00:24:13,530 --> 00:24:17,964
mit kell valójában írni mi
kód, hogy képviselje a láncolt lista?

547
00:24:17,964 --> 00:24:21,130
Mennyi ezen információk nem is kell
hogy rögzítse a C kód, mit mondana?

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

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

550
00:24:23,154 --> 00:24:24,738
>> Közönség: Szükségünk van egy mutató egy csomópont.

551
00:24:24,738 --> 00:24:26,237
David J. MALAN: A mutató egy csomópont.

552
00:24:26,237 --> 00:24:29,320
Különösen, ami csomópont lenne az
ösztönök lehet tartani a mutatót?

553
00:24:29,320 --> 00:24:30,026
>> KÖZÖNSÉG: Az első csomópont.

554
00:24:30,026 --> 00:24:31,942
>> David J. MALAN: Igen,
talán csak az első.

555
00:24:31,942 --> 00:24:34,030
, És vegyük észre, az első
csomópont egy másik formája.

556
00:24:34,030 --> 00:24:37,690
Ez csak feleakkora a struct,
mert ez tényleg csak egy mutató.

557
00:24:37,690 --> 00:24:44,650
Szóval, mit lehet valóban tenni is kijelentik
A láncolt lista, hogy típusú csomópont *.

558
00:24:44,650 --> 00:24:47,780
És hívjuk csak először
és inicializálása null.

559
00:24:47,780 --> 00:24:49,910
Tehát null ismét jön
a kép itt.

560
00:24:49,910 --> 00:24:53,620
Nem csak a null használják, mint a speciális
visszatérési érték a dolgok, mint getstring

561
00:24:53,620 --> 00:24:57,770
és malloc, null is a nulla
mutató, nincs meg az a mutató,

562
00:24:57,770 --> 00:24:58,430
ha úgy tetszik.

563
00:24:58,430 --> 00:25:00,309
Ez csak azt jelenti, semmi még itt.

564
00:25:00,309 --> 00:25:02,100
Most először, nem tudtam volna
hívják ezt a valamit.

565
00:25:02,100 --> 00:25:04,200
Tudtam volna nevezte "lista"
vagy számos más dolog.

566
00:25:04,200 --> 00:25:06,960
De én hívom, hogy "első", hogy a
egy vonalba ezzel a képpel.

567
00:25:06,960 --> 00:25:10,280
Tehát, mint egy húr is képviselteti magát
A cím az első byte,

568
00:25:10,280 --> 00:25:11,280
így lehet a láncolt lista.

569
00:25:11,280 --> 00:25:13,480
És majd meglátjuk egyéb adatok
szerkezetek képviseli

570
00:25:13,480 --> 00:25:16,700
csak egy mutató,
32 bites arrow, rámutatva

571
00:25:16,700 --> 00:25:18,740
a nagyon első csomópont a szerkezetben.

572
00:25:18,740 --> 00:25:20,340
>> De most nézzük előre a probléma.

573
00:25:20,340 --> 00:25:23,230
Ha én csak emlékezni
a programom a cím

574
00:25:23,230 --> 00:25:27,220
Az első csomópont, az első
téglalap adatstruktúrát,

575
00:25:27,220 --> 00:25:31,760
mi volt jobb a helyzet a
végrehajtása a többi az én lista?

576
00:25:31,760 --> 00:25:35,820
Mi az a legfontosabb részlet, hogy fog
Ennek biztosítása tényleg működik?

577
00:25:35,820 --> 00:25:39,250
És a "tényleg működik" I
jelent, mint egy húr,

578
00:25:39,250 --> 00:25:42,180
lehetővé teszi számunkra, megy az első karakter
A Davin nevét a második,

579
00:25:42,180 --> 00:25:44,755
A harmadik, hogy a
negyedik, hogy a legvégén,

580
00:25:44,755 --> 00:25:47,880
honnan tudjuk, hogy mikor vagyunk a végén
A láncolt lista, amely úgy néz ki, mint ez?

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

582
00:25:50,035 --> 00:25:50,660
Mikor ez null.

583
00:25:50,660 --> 00:25:53,640
És már képviselte ezt a fajta, mint
mint villamosmérnök hatalom,

584
00:25:53,640 --> 00:25:56,420
A kis földelés
szimbólum, a fajta.

585
00:25:56,420 --> 00:25:58,246
De ez csak azt jelenti, null ebben az esetben.

586
00:25:58,246 --> 00:26:00,370
Tudod felhívni minden olyan szám
módon, de ez a szerző

587
00:26:00,370 --> 00:26:02,800
történt, hogy ezt a szimbólumot itt.

588
00:26:02,800 --> 00:26:06,260
>> Mindaddig, amíg mi drót
mindezen csomópontok együtt,

589
00:26:06,260 --> 00:26:08,600
csak elfelejtette, hogy hová
Az első az, amíg

590
00:26:08,600 --> 00:26:11,760
mint mi, hogy egy speciális szimbólum
az utolsó csomópont a listán,

591
00:26:11,760 --> 00:26:15,130
és fogjuk használni null, mert az
mi van elérhető számunkra,

592
00:26:15,130 --> 00:26:16,480
ez a lista teljes.

593
00:26:16,480 --> 00:26:20,190
És még ha csak kapsz egy mutatót
az első elem, te, a programozó,

594
00:26:20,190 --> 00:26:22,486
biztosan tudja elérni a többi.

595
00:26:22,486 --> 00:26:24,360
De hagyjuk, a fejében
vándorolni egy kicsit,

596
00:26:24,360 --> 00:26:26,140
ha ők még nem
egészen wandered-- mi

597
00:26:26,140 --> 00:26:28,723
lesz a menetideje
találni valami ebben a listában?

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

599
00:26:30,450 --> 00:26:33,470
A fenébe is, ez nagy O n
ami nem rossz, a méltányosság.

600
00:26:33,470 --> 00:26:34,800
De ez lineáris.

601
00:26:34,800 --> 00:26:37,980
Adtunk fel, amit a szolgáltatás
A tömbök mozgatásával több

602
00:26:37,980 --> 00:26:43,130
felé ezt a képet dinamikusan
szőtt együtt vagy kapcsolt csomópont?

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

604
00:26:44,970 --> 00:26:46,687
Már feladta véletlen hozzáférésű.

605
00:26:46,687 --> 00:26:48,770
Egy tömb szép, mert
matematikailag minden

606
00:26:48,770 --> 00:26:50,340
vissza vissza a háttal.

607
00:26:50,340 --> 00:26:52,370
Annak ellenére, hogy ezt a képet
úgy néz ki, szép, és még

608
00:26:52,370 --> 00:26:55,830
de úgy néz ki, mint ezek a csomópontok
szépen egymástól távol, a valóságban

609
00:26:55,830 --> 00:26:56,830
akkor bárhol lehet.

610
00:26:56,830 --> 00:27:01,590
OX1, Ox50, Ox123, Ox99, ezeket
csomópontok bárhol lehet.

611
00:27:01,590 --> 00:27:05,960
Mivel a malloc nem lefoglalni memóriát
a kupac, de bárhol a kupac.

612
00:27:05,960 --> 00:27:09,080
Nem feltétlenül tudják, hogy ez
lesz vissza háttal.

613
00:27:09,080 --> 00:27:12,460
És ezt a képet a valóság
Nem lesz elég a szép.

614
00:27:12,460 --> 00:27:16,140
>> Szóval ez fog tartani egy kis
dolgozni, hogy végrehajtja-e ezt a funkciót.

615
00:27:16,140 --> 00:27:17,880
Szóval végre a Keresés gombra.

616
00:27:17,880 --> 00:27:20,250
És majd meglátjuk, egyfajta
okos módja ennek.

617
00:27:20,250 --> 00:27:24,660
Tehát, ha én vagyok a kereső funkció és
Kapok egy változó, egész n

618
00:27:24,660 --> 00:27:28,490
keresni, azt kell tudni, hogy a
új szintaxis keresett belül

619
00:27:28,490 --> 00:27:32,400
A szerkezet, ami
rámutatott arra, hogy ahhoz, hogy megtaláld n.

620
00:27:32,400 --> 00:27:33,210
Így csináljuk.

621
00:27:33,210 --> 00:27:36,030
>> Tehát először fogok menni
előre, és állapítsa meg a csomópont *.

622
00:27:36,030 --> 00:27:39,400
És én fogom nevezni
mutató, csak a konvenció.

623
00:27:39,400 --> 00:27:41,710
És én fogom inicializálása először.

624
00:27:41,710 --> 00:27:43,770
És most én is ezt
számos módon.

625
00:27:43,770 --> 00:27:45,436
De én, hogy egy közös megközelítés.

626
00:27:45,436 --> 00:27:50,180
Bár a mutató nem egyenlő
null, és ez érvényes szintaxis.

627
00:27:50,180 --> 00:27:54,550
És ez csak azt jelenti, nem a következő, így
Amíg te nem mutatott semmit.

628
00:27:54,550 --> 00:27:55,800
Mit akarok?

629
00:27:55,800 --> 00:28:01,939
>> Ha a mutató pont n, hadd jöjjön vissza
az, hogy equals-- egyenlő mi?

630
00:28:01,939 --> 00:28:03,105
Milyen értéket keressek?

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

632
00:28:04,920 --> 00:28:06,590
A tényleges n, amit átadott.

633
00:28:06,590 --> 00:28:09,020
Tehát itt van egy másik funkció
C és több nyelven.

634
00:28:09,020 --> 00:28:13,705
Annak ellenére, hogy a szerkezet az úgynevezett csomópont
értéke n, teljesen jogos

635
00:28:13,705 --> 00:28:17,530
hogy is van egy helyi érv
vagy változó hívott n.

636
00:28:17,530 --> 00:28:20,085
Mert még mi, a
az emberi szem képes megkülönböztetni

637
00:28:20,085 --> 00:28:22,087
n értéke, hogy ez feltehetően
ettől eltérő n.

638
00:28:22,087 --> 00:28:23,420
Mivel a szintaxis más.

639
00:28:23,420 --> 00:28:26,211
Van egy pont, és a mutató,
mivel ez egy nem ilyen dolog.

640
00:28:26,211 --> 00:28:27,290
Tehát ez rendben van.

641
00:28:27,290 --> 00:28:29,120
Ez rendben van, hogy hívja őket ugyanazokat a dolgokat.

642
00:28:29,120 --> 00:28:32,380
>> Ha találsz ezt, én vagyok
szeretne majd csinálni valamit

643
00:28:32,380 --> 00:28:35,000
mint bejelenteni, hogy megtaláltuk az n.

644
00:28:35,000 --> 00:28:37,930
És mi hagyjuk, hogy a
megjegyzést vagy pszeudokódja kódot.

645
00:28:37,930 --> 00:28:40,190
Else, és itt van a
érdekes rész, amit

646
00:28:40,190 --> 00:28:47,320
nem akarok, ha a jelenlegi csomópont
nem tartalmaz n, hogy érdekel?

647
00:28:47,320 --> 00:28:50,700
Hogyan elérni a következő?

648
00:28:50,700 --> 00:28:53,710
Ha az ujját a
pillanat PTR, és ez

649
00:28:53,710 --> 00:28:55,920
mutatva bármilyen
először mutat meg,

650
00:28:55,920 --> 00:28:59,290
hogyan mozog az ujjam
A következő csomópont kódot?

651
00:28:59,290 --> 00:29:01,915
Nos, mi a morzsa vagyunk
fogja követni ebben az esetben?

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

653
00:29:03,464 --> 00:29:04,380
KÖZÖNSÉG: [nem hallható].

654
00:29:04,380 --> 00:29:05,630
David J. MALAN: Igen, így a következő.

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

656
00:29:06,640 --> 00:29:09,824
Tehát, ha megyek vissza a
kód van, sőt, én vagyok

657
00:29:09,824 --> 00:29:12,990
menni előre, és azt mondják, mutató, amely
csak egy átmeneti változó-- ez

658
00:29:12,990 --> 00:29:15,320
a furcsa nevet, PTR, de
ez olyan, mint temp--

659
00:29:15,320 --> 00:29:19,234
Megyek be mutató
egyenlő bármi mutató fektettünk--

660
00:29:19,234 --> 00:29:22,150
és újra, ez lesz a
kicsit bugos a moment-- pont található.

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

662
00:29:23,551 --> 00:29:26,550
Más szóval, fogom vinni a
ujj mutatna ezen a csomóponton

663
00:29:26,550 --> 00:29:31,247
itt fogom mondani, tudod
mi, vessen egy pillantást a következő mező

664
00:29:31,247 --> 00:29:33,330
és mozgassa az ujját
bármi is mutatna.

665
00:29:33,330 --> 00:29:35,163
És ez fog
ismétlés, ismétlés, ismétlés.

666
00:29:35,163 --> 00:29:37,630
De ha nem az ujjam
abba egyáltalán?

667
00:29:37,630 --> 00:29:40,095
Amint milyen kódsort beindul?

668
00:29:40,095 --> 00:29:40,970
KÖZÖNSÉG: [nem hallható]

669
00:29:40,970 --> 00:29:43,060
David J. MALAN: Ha pont, míg
mutató nem egyenlő null.

670
00:29:43,060 --> 00:29:44,900
Egy bizonyos ponton az ujjam a
lesz mutatva null

671
00:29:44,900 --> 00:29:47,070
és fogok megvalósítani
itt a vége ennek a listának.

672
00:29:47,070 --> 00:29:48,910
Nos, ez egy kicsit
fehér hazugság az egyszerűség kedvéért.

673
00:29:48,910 --> 00:29:51,580
Kiderült, hogy még akkor is,
csak tanultam ezt pont jelölés

674
00:29:51,580 --> 00:29:55,220
szerkezetekhez, mutató nem egy struktúra.

675
00:29:55,220 --> 00:29:56,580
ptr mi?

676
00:29:56,580 --> 00:29:58,350
Csak, hogy több nitpicky.

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

678
00:29:59,720 --> 00:30:01,360
Ez egy mutató, hogy a csomópont.

679
00:30:01,360 --> 00:30:03,120
Ez nem egy csomópont is.

680
00:30:03,120 --> 00:30:06,650
Ha nem volt csillag itt, mutató
absolutely-- ez a csomópont.

681
00:30:06,650 --> 00:30:08,650
Ez olyan, mint a héten egy
nyilatkozat a változó,

682
00:30:08,650 --> 00:30:10,120
még akkor is, ha a "csomópont" új.

683
00:30:10,120 --> 00:30:13,860
>> De amint bemutatjuk a
csillag, ez most a mutatót egy csomóponthoz.

684
00:30:13,860 --> 00:30:17,960
És sajnos nem tudja használni
A pont jelölése a mutató.

685
00:30:17,960 --> 00:30:21,070
Ki kell használni a nyíl
jelölést, ami feltűnően,

686
00:30:21,070 --> 00:30:23,470
az első alkalommal egy darab
A szintaxis néz intuitív.

687
00:30:23,470 --> 00:30:25,245
Ez a szó szerint úgy néz ki, mint a nyíl.

688
00:30:25,245 --> 00:30:26,370
És ez egy jó dolog.

689
00:30:26,370 --> 00:30:28,995
És itt szó szerint
úgy néz ki, mint egy nyíl.

690
00:30:28,995 --> 00:30:31,870
Szóval úgy gondolom, hogy ez a la-- én nem
hiszem, túl elkötelezi itt-- I

691
00:30:31,870 --> 00:30:34,120
gondolom, hogy ez az utolsó új darab
A szintaxis fogunk látni.

692
00:30:34,120 --> 00:30:36,500
És szerencsére, ez valóban
egy kicsit intuitív.

693
00:30:36,500 --> 00:30:40,090
>> Nos, azok számára, akik
talán inkább a régi módon,

694
00:30:40,090 --> 00:30:42,550
továbbra is használhatja a pont jelölést.

695
00:30:42,550 --> 00:30:45,380
De ahogy egy hétfői
beszélgetés, először

696
00:30:45,380 --> 00:30:50,530
kell menni oda, megy, hogy
címét, majd lépjen be a területen.

697
00:30:50,530 --> 00:30:51,897
Szóval ez is helyes.

698
00:30:51,897 --> 00:30:53,730
És őszintén szólva, ez a
kicsit pedáns.

699
00:30:53,730 --> 00:30:56,530
Te szó szerint azt mondja, dereference
a mutató és ott.

700
00:30:56,530 --> 00:30:59,320
Ezután fogd .N, a terület az úgynevezett n.

701
00:30:59,320 --> 00:31:01,370
De őszintén szólva, senki sem akar
írja vagy olvassa el ezt.

702
00:31:01,370 --> 00:31:03,620
És így a világ kitalált
A nyíl jelölés, amely

703
00:31:03,620 --> 00:31:06,980
egyenértékű, azonos,
ez csak szintaktikai cukor.

704
00:31:06,980 --> 00:31:10,570
Így divatos szóval ezt
jobban néz ki, vagy úgy néz ki, egyszerűbb.

705
00:31:10,570 --> 00:31:12,296
>> Szóval most fogok csinálni egy másik dolog.

706
00:31:12,296 --> 00:31:15,420
Fogom mondani, hogy "szünet", ha én már
találtam, így nem tartja keresi.

707
00:31:15,420 --> 00:31:17,620
De ez a lényeg
a kereső funkció.

708
00:31:17,620 --> 00:31:21,710
De ez sokkal könnyebb, a
end, nem a séta a kódot.

709
00:31:21,710 --> 00:31:25,570
Valóban ez a formális végrehajtását
A keresés a mai eloszlás kódot.

710
00:31:25,570 --> 00:31:30,530
Merem állítani, hogy betét nem
különösen szórakoztató a séta

711
00:31:30,530 --> 00:31:33,180
vizuálisan, sem törölni, még
bár a végén a nap

712
00:31:33,180 --> 00:31:35,460
úgy szűkülnek le, hogy meglehetősen
egyszerű heurisztika.

713
00:31:35,460 --> 00:31:36,330
>> Így csináljuk.

714
00:31:36,330 --> 00:31:39,250
Ha lesz humor ide, tettem
hogy egy csomó stressz labda.

715
00:31:39,250 --> 00:31:40,620
Hoztam egy csomó számot.

716
00:31:40,620 --> 00:31:46,562
És tudnánk, hogy csak néhány önkéntesek
hogy képviselje 9., 17., 20., 22., 29., és 34.?

717
00:31:46,562 --> 00:31:48,270
Tehát lényegében mindenki
ki van itt ma.

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

719
00:31:50,170 --> 00:31:52,760
Ez volt az egyik, kettő, három,
négy, öt, hat ember.

720
00:31:52,760 --> 00:31:55,740
És én már kérte van-- látni, nem
az egyik a hátsó emeli a kezét.

721
00:31:55,740 --> 00:32:01,910
OK, egy, kettő, három, négy,
five-- hadd töltse balance-- hat.

722
00:32:01,910 --> 00:32:03,051
OK, akkor hat gyere fel.

723
00:32:03,051 --> 00:32:04,050
Szükségünk lesz a többi ember.

724
00:32:04,050 --> 00:32:05,460
Hoztunk extra stressz labda.

725
00:32:05,460 --> 00:32:08,200
És ha, a
Csak egy pillanat, vonal

726
00:32:08,200 --> 00:32:10,490
magatokat csak
szeret ezt a képet itt.

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

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

729
00:32:15,959 --> 00:32:17,125
Lássuk, mi a neve?

730
00:32:17,125 --> 00:32:17,550
>> Közönség: Andrew.

731
00:32:17,550 --> 00:32:18,800
>> David J. MALAN: Andrew,
Ön szám 9.

732
00:32:18,800 --> 00:32:19,540
Örülök, hogy találkoztunk.

733
00:32:19,540 --> 00:32:20,400
Itt van.

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

735
00:32:21,593 --> 00:32:22,176
Közönség: 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
Number 17.

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

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

741
00:32:25,450 --> 00:32:26,400
>> Közönség: Én vagyok Julia.

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

743
00:32:26,980 --> 00:32:27,545
20. számú.

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

745
00:32:28,507 --> 00:32:29,340
Közönség: Christian.

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

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

748
00:32:31,541 --> 00:32:32,040
És?

749
00:32:32,040 --> 00:32:32,649
>> Közönség: JP.

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

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

752
00:32:34,880 --> 00:32:37,080
Így megy előre, és kap 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
Készenlét.

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
Van valakinek egy marker?

760
00:32:43,682 --> 00:32:44,890
Közönség: Van egy Sharpie.

761
00:32:44,890 --> 00:32:45,660
David J. MALAN: Van egy 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
És van valakinek egy darab papírt?

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

766
00:32:51,562 --> 00:32:52,270
Mentse el az előadás.

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

768
00:32:53,810 --> 00:32:55,362
Gyerünk.

769
00:32:55,362 --> 00:32:56,320
Közönség: Van rá.

770
00:32:56,320 --> 00:32:57,600
David J. MALAN: Megvan?

771
00:32:57,600 --> 00:32:58,577
Rendben, köszönöm.

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

773
00:33:01,380 --> 00:33:02,520
Itt vagyunk.

774
00:33:02,520 --> 00:33:03,582
Vajon ez tőled?

775
00:33:03,582 --> 00:33:04,540
Épp most mentette meg a napot.

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

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

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

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

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

781
00:33:13,360 --> 00:33:14,890
Én elgépelt 29, de az OK gombra.

782
00:33:14,890 --> 00:33:15,720
Rajta.

783
00:33:15,720 --> 00:33:18,114
Rendben, adok
a toll vissza egy pillanatra.

784
00:33:18,114 --> 00:33:19,280
Tehát ezek az emberek itt.

785
00:33:19,280 --> 00:33:20,330
Nézzük meg egy másik.

786
00:33:20,330 --> 00:33:23,750
Gabe, mit szeretne játszani
az első elem itt?

787
00:33:23,750 --> 00:33:25,705
Szükségünk lesz, hogy pont
ezeken a szép emberek.

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

789
00:33:26,930 --> 00:33:31,030
Tehát 9., 17., 20., 22., sort
29, majd 34.

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

791
00:33:32,160 --> 00:33:33,325
Vajon elveszíteni valakit?

792
00:33:33,325 --> 00:33:33,950
Van egy 34.

793
00:33:33,950 --> 00:33:36,730
Ahol did-- OK, aki azt akarja, hogy 34?

794
00:33:36,730 --> 00:33:37,605
OK, gyere fel, 34.

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

796
00:33:39,280 --> 00:33:41,220
Rendben, ez lesz
megéri a csúcspontja.

797
00:33:41,220 --> 00:33:41,550
Mi a neve?

798
00:33:41,550 --> 00:33:42,040
>> Közönség: Peter.

799
00:33:42,040 --> 00:33:43,456
>> David J. MALAN: Peter, gyere fel.

800
00:33:43,456 --> 00:33:46,810
Rendben, itt egy
csomó csomópontok.

801
00:33:46,810 --> 00:33:49,060
Minden srácok jelent
az egyik ilyen téglalapok.

802
00:33:49,060 --> 00:33:51,930
Gabe, a kissé furcsa
ember, ki képviseli az első.

803
00:33:51,930 --> 00:33:54,850
Így a mutató egy kicsit kisebb
a képernyőn, mint mindenki más.

804
00:33:54,850 --> 00:33:58,120
És ebben az esetben mindegyik a bal
kezet fog vagy pont le,

805
00:33:58,120 --> 00:34:01,085
ezáltal képviselő null, így
hanem a hiánya egy mutatót,

806
00:34:01,085 --> 00:34:03,210
vagy ez lesz mutatva
egy csomópont melletted.

807
00:34:03,210 --> 00:34:05,440
>> Tehát most, ha szépít
magatokat, mint a képen

808
00:34:05,440 --> 00:34:07,585
itt, megy előre, és pont
minden más, a Gabe

809
00:34:07,585 --> 00:34:11,030
különösen mutatva
9-es szám, hogy képviselje a listán.

810
00:34:11,030 --> 00:34:14,050
OK, és 34-a bal kezét
kéne mutasson a padlóra.

811
00:34:14,050 --> 00:34:15,750
>> OK, így ez a láncolt lista.

812
00:34:15,750 --> 00:34:17,580
Tehát ez a forgatókönyv a kérdéses.

813
00:34:17,580 --> 00:34:20,210
És valóban, ez a reprezentatív
egy osztály a problémák

814
00:34:20,210 --> 00:34:21,929
hogy lehet, megpróbálják megoldani a kódot.

815
00:34:21,929 --> 00:34:25,020
Azt akarod, hogy végül beilleszteni
egy új elemet a lista.

816
00:34:25,020 --> 00:34:27,494
Ebben az esetben, mi lesz
próbálja meg behelyezni a szám 55.

817
00:34:27,494 --> 00:34:28,500

818
00:34:28,500 --> 00:34:30,860
De lesz
különböző esetek, hogy fontolja meg.

819
00:34:30,860 --> 00:34:34,409
És valóban, ez lesz az egyik
A nagy kép elvitelre itt, az,

820
00:34:34,409 --> 00:34:35,659
Melyek a különböző eseteket.

821
00:34:35,659 --> 00:34:39,120
Melyek a ha a körülmények vagy
ágak, hogy a program esetleg?

822
00:34:39,120 --> 00:34:42,024
>> Nos, a szám akarsz
betét, amely most már tudjuk, hogy 55,

823
00:34:42,024 --> 00:34:44,650
de ha nem tudja,
előre, merem állítani

824
00:34:44,650 --> 00:34:47,840
beleesik legalább három
lehetséges helyzetek.

825
00:34:47,840 --> 00:34:49,717
Ahol lehet, hogy egy új elem az?

826
00:34:49,717 --> 00:34:51,050
Közönség: És a végén, vagy középen.

827
00:34:51,050 --> 00:34:54,150
David J. MALAN: A végén, a
a középső, vagy az elején.

828
00:34:54,150 --> 00:34:56,650
Tehát azt állítom, van legalább
három problémát meg kell oldani.

829
00:34:56,650 --> 00:34:58,691
Nézzük választani, mi van talán
vitathatatlanul a legegyszerűbb

830
00:34:58,691 --> 00:35:01,090
egyik, ahol az új elem
tartozik az elején.

831
00:35:01,090 --> 00:35:04,040
Szóval lesz kód meglehetősen
mint keresni, amit csak írtam.

832
00:35:04,040 --> 00:35:07,670
És én megyek is PTR, amely
Én képviselek az ujjam,

833
00:35:07,670 --> 00:35:08,370
mint mindig.

834
00:35:08,370 --> 00:35:12,430
>> És ne feledd, milyen értéket
jutottunk inicializálni PTR?

835
00:35:12,430 --> 00:35:15,300
Így inicializáltuk NULL kezdetben.

836
00:35:15,300 --> 00:35:16,410

837
00:35:16,410 --> 00:35:19,770
De akkor mit tegyünk, ha már
volt benne keresési funkció?

838
00:35:19,770 --> 00:35:20,940

839
00:35:20,940 --> 00:35:24,870
Mi meg azt egyenlő az első,
ami nem jelenti ezt.

840
00:35:24,870 --> 00:35:25,890

841
00:35:25,890 --> 00:35:30,570
Ha én meg PTR egyenlő az első, amit
meg a kezem tényleg mutat?

842
00:35:30,570 --> 00:35:31,070
Jobb.

843
00:35:31,070 --> 00:35:33,290
Tehát, ha Gabe és én
hogy egyenlő értékek itt,

844
00:35:33,290 --> 00:35:34,760
kell mindkét pont a szám 9.

845
00:35:34,760 --> 00:35:36,420
>> Tehát ez volt a kezdete a történet.

846
00:35:36,420 --> 00:35:38,700
És most ez csak egyszerű,
bár a szintaxis új.

847
00:35:38,700 --> 00:35:40,580
Fogalmi ez csak lineáris keresést.

848
00:35:40,580 --> 00:35:42,750
55 egyenlő 9?

849
00:35:42,750 --> 00:35:45,559
Vagy inkább, mondjuk kevesebb, mint 9.

850
00:35:45,559 --> 00:35:47,600
Mert próbálok
kitalálni, hová tegye 55.

851
00:35:47,600 --> 00:35:51,270
Kevesebb, mint 9, kevesebb, mint 17, kevesebb
mint 20, kevesebb, mint 22, kevesebb, mint 29,

852
00:35:51,270 --> 00:35:52,510
kevesebb, mint 34, no.

853
00:35:52,510 --> 00:35:55,080
Tehát most vagyunk abban az esetben,
egyike legalább három.

854
00:35:55,080 --> 00:35:59,910
>> Ha a beszúrni kívánt 55 ide, mit
sornyi kódot kell, hogy végre?

855
00:35:59,910 --> 00:36:01,890
Hogyan működik ez a kép
az emberek meg kell változtatni?

856
00:36:01,890 --> 00:36:03,181
Mit csináljak a bal kezemmel?

857
00:36:03,181 --> 00:36:04,530

858
00:36:04,530 --> 00:36:07,360
Ez legyen null kezdetben,
mert én vagyok az a lista végén.

859
00:36:07,360 --> 00:36:09,318
És mi történik
itt Peter, ugye?

860
00:36:09,318 --> 00:36:10,520

861
00:36:10,520 --> 00:36:12,430
Ő lehet a baj, hogy pont nekem.

862
00:36:12,430 --> 00:36:15,580
Tehát azt állítom, van legalább két sor
A kód a minta kódját a mai

863
00:36:15,580 --> 00:36:18,570
hogy fogja végrehajtani ezt
forgatókönyv, hozzátéve 55 a farok.

864
00:36:18,570 --> 00:36:20,950
És tudtam, hogy valaki hop
és csak képvisel 55?

865
00:36:20,950 --> 00:36:22,200
Rendben, te vagy az új 55.

866
00:36:22,200 --> 00:36:23,580

867
00:36:23,580 --> 00:36:27,054
>> Így most mi van, ha a következő
forgatókönyv jön,

868
00:36:27,054 --> 00:36:29,720
és szeretnénk beszúrni a
elején vagy a fejét ez a lista?

869
00:36:29,720 --> 00:36:31,100
És mi a neve, száma 55?

870
00:36:31,100 --> 00:36:31,420
>> Közönség: Jack.

871
00:36:31,420 --> 00:36:32,295
>> David J. MALAN: Jack?

872
00:36:32,295 --> 00:36:33,585
OK, örülök, hogy találkoztunk.

873
00:36:33,585 --> 00:36:34,210
Üdvözöljük a fedélzeten.

874
00:36:34,210 --> 00:36:36,640
Tehát most megyünk
helyezze, mondjuk, az 5-ös szám.

875
00:36:36,640 --> 00:36:39,840
Itt a második esetben a
három kitaláltunk előtt.

876
00:36:39,840 --> 00:36:43,050
Tehát, ha 5 tartozik az elején,
nézzük meg, hogyan látjuk, hogy ki.

877
00:36:43,050 --> 00:36:46,310
Én inicializálni a ptr
mutató a 9-es szám újra.

878
00:36:46,310 --> 00:36:49,140
És rájöttem, ó, 5 kevesebb, mint 9.

879
00:36:49,140 --> 00:36:50,880
Csináld ezt a képet nekünk.

880
00:36:50,880 --> 00:36:54,820
Kinek a keze, Gabe és Dávid
vagy-- mi 9-es szám neve?

881
00:36:54,820 --> 00:36:55,740
>> Közönség: Jen.

882
00:36:55,740 --> 00:36:58,406
>> David J. MALAN: Jen hands--
amely a kezünkből kell változtatni?

883
00:36:58,406 --> 00:36:58,905

884
00:36:58,905 --> 00:37:00,970
OK, így Gabe rámutat, hogy mi most?

885
00:37:00,970 --> 00:37:01,640
Rám.

886
00:37:01,640 --> 00:37:02,750
Én vagyok az új csomópontot.

887
00:37:02,750 --> 00:37:04,870
Úgyhogy csak ilyen lépés
ide meg vizuálisan.

888
00:37:04,870 --> 00:37:06,435
És közben mit pont ezt?

889
00:37:06,435 --> 00:37:07,910

890
00:37:07,910 --> 00:37:09,020
Mégis hol vagyok mutatva.

891
00:37:09,020 --> 00:37:10,000
Szóval ennyi.

892
00:37:10,000 --> 00:37:13,717
Szóval tényleg egy sor kód javítások
ez a bizonyos kérdés, úgy tűnik.

893
00:37:13,717 --> 00:37:14,800
Rendben, ez jó.

894
00:37:14,800 --> 00:37:17,580
És valaki egy helykitöltő 5?

895
00:37:17,580 --> 00:37:18,080
Gyere fel.

896
00:37:18,080 --> 00:37:20,270

897
00:37:20,270 --> 00:37:21,320
Kapsz legközelebb.

898
00:37:21,320 --> 00:37:24,280
>> Rendben, now-- és
Mellesleg, a neveket

899
00:37:24,280 --> 00:37:28,510
Nem én kifejezett említést jog
Most, pred mutató, elődje mutató

900
00:37:28,510 --> 00:37:31,260
és az új mutató, az
csak a neveket adott

901
00:37:31,260 --> 00:37:35,280
a minta kódot a mutatók vagy
a kezem, hogy ez a fajta mutat körül.

902
00:37:35,280 --> 00:37:36,060
Mi a neve?

903
00:37:36,060 --> 00:37:36,700
>> Közönség: Christine.

904
00:37:36,700 --> 00:37:37,100
>> David J. MALAN: Christine.

905
00:37:37,100 --> 00:37:38,090
Üdvözöljük a fedélzeten.

906
00:37:38,090 --> 00:37:42,180
Rendben, nézzük meg most
némileg bosszantó forgatókönyv,

907
00:37:42,180 --> 00:37:46,350
amelynek szeretnék beilleszteni
valami hasonló 26 ebbe.

908
00:37:46,350 --> 00:37:47,090
20?

909
00:37:47,090 --> 00:37:47,590
Mi az?

910
00:37:47,590 --> 00:37:50,510
Ezek a are-- jó dolog, amit meg ezt a tollat.

911
00:37:50,510 --> 00:37:51,955
Rendben, 20.

912
00:37:51,955 --> 00:37:53,640

913
00:37:53,640 --> 00:37:57,570
Ha valaki tudna még egy darab
papír kész, csak case-- minden rendben.

914
00:37:57,570 --> 00:37:58,370
Oh, érdekes.

915
00:37:58,370 --> 00:37:59,760

916
00:37:59,760 --> 00:38:02,390
Hát ez egy példa
Egy előadás bug.

917
00:38:02,390 --> 00:38:03,894
OK, így mi is a neved?

918
00:38:03,894 --> 00:38:04,560
Közönség: Julia.

919
00:38:04,560 --> 00:38:07,559
David J. MALAN: Julia, tudsz pop
, és tégy úgy, mintha soha ott?

920
00:38:07,559 --> 00:38:09,040
OK, ez soha nem történt meg.

921
00:38:09,040 --> 00:38:09,680
Köszönöm.

922
00:38:09,680 --> 00:38:12,180
Tegyük fel, hogy szeretnénk beilleszteni
Julia ebbe láncolt lista.

923
00:38:12,180 --> 00:38:13,780
Ő a 20. számú.

924
00:38:13,780 --> 00:38:15,530
És persze ő
fog tartozni a

925
00:38:15,530 --> 00:38:17,521
begin-- nem mutatnak meg semmit.

926
00:38:17,521 --> 00:38:20,020
Hogy a keze is olyan lehet
le null vagy valami szemetet értéket.

927
00:38:20,020 --> 00:38:21,210
Mondjuk el a rövid történetet.

928
00:38:21,210 --> 00:38:22,980
Én mutatva 5. szám ebben az időben.

929
00:38:22,980 --> 00:38:23,880
Aztán nézd 9.

930
00:38:23,880 --> 00:38:25,130
Aztán nézd 17.

931
00:38:25,130 --> 00:38:26,247
Aztán nézd 22.

932
00:38:26,247 --> 00:38:27,650

933
00:38:27,650 --> 00:38:32,485
És rájöttem, ó, Julia
kell menni, mielőtt 22.

934
00:38:32,485 --> 00:38:33,580

935
00:38:33,580 --> 00:38:34,660
Tehát mi kell történnie?

936
00:38:34,660 --> 00:38:35,786

937
00:38:35,786 --> 00:38:36,910
Kinek a kezében kell változtatni?

938
00:38:36,910 --> 00:38:38,360
Julia, az enyém, vagy--
mi a neved?

939
00:38:38,360 --> 00:38:39,230
>> Közönség: Christian.

940
00:38:39,230 --> 00:38:40,060
>> David J. MALAN: keresztény vagy?

941
00:38:40,060 --> 00:38:40,560
>> Közönség: Andy.

942
00:38:40,560 --> 00:38:40,905
>> David J. MALAN: Andy.

943
00:38:40,905 --> 00:38:41,654
Keresztény vagy Andy?

944
00:38:41,654 --> 00:38:44,280

945
00:38:44,280 --> 00:38:45,690
Andy kell mutatni?

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
Rendben.

949
00:38:47,840 --> 00:38:48,960
Szóval Andy, akarsz rámutatni Julia?

950
00:38:48,960 --> 00:38:50,120
De várjunk csak egy percet.

951
00:38:50,120 --> 00:38:53,260
A történet eddig,
Én vagyok az a fajta egy

952
00:38:53,260 --> 00:38:56,800
felelős, abban az értelemben, hogy a
mutató az a dolog, ami

953
00:38:56,800 --> 00:38:57,850
halad át a listát.

954
00:38:57,850 --> 00:39:00,800
Lehet, hogy egy nevet Andy, de
nincs változó nevű Andy.

955
00:39:00,800 --> 00:39:04,320
Az egyetlen változó van az
Először is, aki képviseli Gabe.

956
00:39:04,320 --> 00:39:07,690
>> Tehát ez valójában miért így
messzire nem szükséges ezt.

957
00:39:07,690 --> 00:39:10,846
De most a képernyőn van
beszélve ismét a Pred mutató.

958
00:39:10,846 --> 00:39:11,970
Szóval hadd legyek egyértelmű.

959
00:39:11,970 --> 00:39:14,820
Ha ez a mutató, már jobb
egy kicsit intelligensebb

960
00:39:14,820 --> 00:39:15,950
az én iteráció.

961
00:39:15,950 --> 00:39:19,580
Ha nem baj, hogy megy át itt
megint mutatott itt, rámutatva itt.

962
00:39:19,580 --> 00:39:22,500
De hadd van Pred mutató,
elődje mutató, az

963
00:39:22,500 --> 00:39:24,740
fajta mutatott a
elem most voltam.

964
00:39:24,740 --> 00:39:27,330
Tehát, ha elmegyek itt, most
a bal oldali frissítéseket.

965
00:39:27,330 --> 00:39:29,370
Mikor megy itt a bal oldali frissítéseket.

966
00:39:29,370 --> 00:39:33,090
És most már nem csak egy mutató,
az elem, hogy megy után Julia,

967
00:39:33,090 --> 00:39:36,300
Még mindig van egy mutatót
Andy, az elem előtt.

968
00:39:36,300 --> 00:39:39,430
Így van hozzáférése, lényegében,
zsemlemorzsa, ha úgy tetszik,

969
00:39:39,430 --> 00:39:41,500
hogy az összes szükséges mutatók.

970
00:39:41,500 --> 00:39:43,710
>> Tehát, ha én mutatott
Andy és én is mutat

971
00:39:43,710 --> 00:39:47,105
A keresztény, akiknek a kezén
most meg kell mutatni máshol?

972
00:39:47,105 --> 00:39:48,770

973
00:39:48,770 --> 00:39:51,960
Így Andy már mutatni Julia.

974
00:39:51,960 --> 00:39:54,460
Julia most mutatni Christian.

975
00:39:54,460 --> 00:39:56,950
Mert lehet másolni a
jobb keze mutató.

976
00:39:56,950 --> 00:40:00,044
És hogy hatékonyan hozza meg
vissza erre a helyre itt.

977
00:40:00,044 --> 00:40:02,460
Tehát röviden, bár ez a
elvisz minket a fajta örökre

978
00:40:02,460 --> 00:40:04,510
hogy valóban frissítéséhez
láncolt lista, észre

979
00:40:04,510 --> 00:40:06,580
hogy a műveletek
viszonylag egyszerű.

980
00:40:06,580 --> 00:40:10,030
Ez az egy, kettő, három
sornyi kódot végül.

981
00:40:10,030 --> 00:40:12,780
De köré azokat
sornyi kódot feltehetően

982
00:40:12,780 --> 00:40:16,350
egy kis logika, amely hatékonyan
felteszi a kérdést, hol vagyunk?

983
00:40:16,350 --> 00:40:18,970
Vagyunk az elején,
a középső, vagy a végén?

984
00:40:18,970 --> 00:40:21,890
>> Nos, biztosan vannak más
művelet talán végre.

985
00:40:21,890 --> 00:40:24,880
És ezek a képek itt csak ábrázol
amit most tett az emberekkel.

986
00:40:24,880 --> 00:40:26,080
Mi a eltávolítása?

987
00:40:26,080 --> 00:40:30,650
Ha azt akarom, hogy, például,
távolítsa el a számot 34 vagy 55,

988
00:40:30,650 --> 00:40:34,680
Talán van ugyanolyan kód,
de fogok kell egy vagy két lépésben.

989
00:40:34,680 --> 00:40:36,110
Mert mi újság?

990
00:40:36,110 --> 00:40:40,460
Ha leveszem valaki a végén,
mint szám 55, majd 34,

991
00:40:40,460 --> 00:40:42,995
mit is kell változtatni, mint én, hogy?

992
00:40:42,995 --> 00:40:44,870
Én, hogy ne evict--
mi a neved?

993
00:40:44,870 --> 00:40:45,380
>> Közönség: Jack.

994
00:40:45,380 --> 00:40:46,255
>> David J. MALAN: Jack.

995
00:40:46,255 --> 00:40:49,770
Én nem csak evict-- szabad Jack,
így a szó szoros értelmében hívás ingyenes Jack, vagy legalábbis

996
00:40:49,770 --> 00:40:53,530
a mutató ott is, de most már
mit kell változtatni a Peter?

997
00:40:53,530 --> 00:40:55,510
Keze jobban indul lefelé.

998
00:40:55,510 --> 00:40:59,300
Mert amint hívom mentes a
Jack, ha Péter még mindig mutat Jack

999
00:40:59,300 --> 00:41:02,530
és ezért folyamatosan áthaladó
a listát, és nem férhet hozzá ehhez mutató,

1000
00:41:02,530 --> 00:41:05,650
ez az, amikor a régi barát szegmentáció
hiba talán valóban rúg.

1001
00:41:05,650 --> 00:41:07,860
Mert már adott a
memória vissza Jack.

1002
00:41:07,860 --> 00:41:10,760
>> Akkor ott
ügyetlenül egy pillanatra.

1003
00:41:10,760 --> 00:41:13,410
Mert már csak egy pár
utolsó művelet, hogy fontolja meg.

1004
00:41:13,410 --> 00:41:15,600
Eltávolítása a lista élére,
vagy a beginning-- és ez a

1005
00:41:15,600 --> 00:41:16,349
Egy kicsit bosszantó.

1006
00:41:16,349 --> 00:41:19,640
Mert tudnunk kell, hogy Gabe
egyfajta különleges ebben a programban.

1007
00:41:19,640 --> 00:41:21,440
Mert valóban, ő a saját mutató.

1008
00:41:21,440 --> 00:41:24,860
Ő nem csak, hogy rámutatott,
mint szinte mindenki más itt.

1009
00:41:24,860 --> 00:41:28,112
>> Tehát, amikor a feje a lista
eltávolították, akinek keze kell változtatni most?

1010
00:41:28,112 --> 00:41:29,070
Mi a neved?

1011
00:41:29,070 --> 00:41:29,450
>> Közönség: Christine.

1012
00:41:29,450 --> 00:41:31,408
>> David J. MALAN: vagyok szörnyű
A nevek, látszólag.

1013
00:41:31,408 --> 00:41:34,011
Tehát Christine és Gabe,
akinek a kezében kell változtatni

1014
00:41:34,011 --> 00:41:36,510
amikor megpróbáljuk eltávolítani Christine,
5-ös, a kép?

1015
00:41:36,510 --> 00:41:37,550

1016
00:41:37,550 --> 00:41:38,820
OK, így csináljuk Gabe.

1017
00:41:38,820 --> 00:41:40,950
Gabe fog mutatni,
Feltételezhető, hogy a 9-es szám.

1018
00:41:40,950 --> 00:41:42,230

1019
00:41:42,230 --> 00:41:44,642
De mi a következő lépés történjen?

1020
00:41:44,642 --> 00:41:46,600
Közönség: Christine kellene
null [nem hallható].

1021
00:41:46,600 --> 00:41:50,244
David J. MALAN: OK, akkor valószínűleg
make-- hallottam "null" valahol.

1022
00:41:50,244 --> 00:41:51,410
Közönség: Null és szabad neki.

1023
00:41:51,410 --> 00:41:51,855
David J. MALAN: NULL mi?

1024
00:41:51,855 --> 00:41:53,074
Közönség: Null és szabad neki.

1025
00:41:53,074 --> 00:41:54,490
David J. MALAN: Null és szabad neki.

1026
00:41:54,490 --> 00:41:55,422
Tehát ez nagyon egyszerű.

1027
00:41:55,422 --> 00:41:58,380
És ez így tökéletes, hogy te most már sort
ott áll, nem tartozik.

1028
00:41:58,380 --> 00:42:00,430
Mert már
függetlenített a listából.

1029
00:42:00,430 --> 00:42:02,820
Már ténylegesen
árva a listából.

1030
00:42:02,820 --> 00:42:07,770
És így még jobban hívják szabad most
Christine adni, hogy az emlékezet vissza.

1031
00:42:07,770 --> 00:42:10,240
Ellenkező esetben minden egyes alkalommal, amikor
törölni egy csomópontot a listából

1032
00:42:10,240 --> 00:42:14,230
mi lehet, hogy a lista
rövidebb, de valójában nem csökkenő

1033
00:42:14,230 --> 00:42:15,096
a méret a memóriában.

1034
00:42:15,096 --> 00:42:17,720
És ha folyamatosan hozzá és
hozzátéve, hozzátéve, a dolgok a listán,

1035
00:42:17,720 --> 00:42:19,280
a számítógép lehet, hogy lassabb
és lassabb és lassabb,

1036
00:42:19,280 --> 00:42:21,740
mert én fut ki
memória, akkor is, ha én nem vagyok valójában

1037
00:42:21,740 --> 00:42:25,580
a Christine bytes
memória többé.

1038
00:42:25,580 --> 00:42:28,500
>> Így a végén vannak más
forgatókönyvek, a course-- eltávolítás

1039
00:42:28,500 --> 00:42:30,640
középen, eltávolítás
a végén, ahogy láttuk.

1040
00:42:30,640 --> 00:42:32,348
De sokkal érdekesebb
kihívás most az,

1041
00:42:32,348 --> 00:42:34,770
lesz, hogy fontolja meg pontosan
mi a működési idő.

1042
00:42:34,770 --> 00:42:36,640
Tehát nem csak tudja tartani a
darab papír, ha Gabe,

1043
00:42:36,640 --> 00:42:38,640
nem bánnád ad
mindenki a stressz labdát.

1044
00:42:38,640 --> 00:42:42,100
Köszönöm szépen, hogy a láncolt lista
Az önkéntesek itt, ha lehet.

1045
00:42:42,100 --> 00:42:45,320
>> [Taps]

1046
00:42:45,320 --> 00:42:46,700
>> David J. MALAN: Rendben.

1047
00:42:46,700 --> 00:42:51,110
Tehát egy pár analitikai
kérdés akkor, ha tehetném.

1048
00:42:51,110 --> 00:42:59,670
Láttuk ezt a jelölést korábban,
nagy O és az Omega, a felső korlátok

1049
00:42:59,670 --> 00:43:02,520
és alsó határ a
futási ideje néhány algoritmus.

1050
00:43:02,520 --> 00:43:04,950
Tehát nézzük csak
egy pár kérdést.

1051
00:43:04,950 --> 00:43:07,090
>> Egyet, és azt mondta, hogy
előtt, mi a futó

1052
00:43:07,090 --> 00:43:10,647
keresés ideje a
lista szempontjából nagy O?

1053
00:43:10,647 --> 00:43:13,480
Mi egy felső határt a futó
ideje keres a láncolt lista

1054
00:43:13,480 --> 00:43:16,340
végrehajtott önkénteseink itt?

1055
00:43:16,340 --> 00:43:17,820
Ez a nagy O N lineáris.

1056
00:43:17,820 --> 00:43:20,630
Mert a legrosszabb esetben,
az elem, mint a 55,

1057
00:43:20,630 --> 00:43:23,830
mi lehet, hogy keres lehet, ahol a
Jack volt, egészen a végén.

1058
00:43:23,830 --> 00:43:28,250
És sajnos, ellentétben egy tömb
nem tudjuk divatos ebben az időben.

1059
00:43:28,250 --> 00:43:31,820
Annak ellenére, hogy minden a mi az emberek voltak,
sorrendje a kis elemeket, 5,

1060
00:43:31,820 --> 00:43:35,900
egészen a nagyobb elem,
55, ez általában egy jó dolog.

1061
00:43:35,900 --> 00:43:38,815
De mit csinál az a feltételezés
már nem teszi lehetővé számunkra, hogy nem?

1062
00:43:38,815 --> 00:43:39,775

1063
00:43:39,775 --> 00:43:40,650
KÖZÖNSÉG: [nem hallható]

1064
00:43:40,650 --> 00:43:40,920
David J. MALAN: Mondd még egyszer?

1065
00:43:40,920 --> 00:43:41,800
Közönség: Random hozzáférés.

1066
00:43:41,800 --> 00:43:43,049
David J. MALAN: Véletlen hozzáférés.

1067
00:43:43,049 --> 00:43:46,330
És viszont, hogy azt jelenti, hogy nincs
már nem használja gyenge nulla, intuíció,

1068
00:43:46,330 --> 00:43:49,365
és nyilvánvaló a bináris
keresés és oszd meg és uralkodj.

1069
00:43:49,365 --> 00:43:51,240
Mert még akkor is,
emberek képesek nyilvánvalóan

1070
00:43:51,240 --> 00:43:54,610
látom, hogy Andy vagy keresztény volt
nagyjából a közepén a lista,

1071
00:43:54,610 --> 00:43:57,670
Annyit tudunk, hogy egy
számítógép futást a lista

1072
00:43:57,670 --> 00:43:59,029
a kezdetektől fogva.

1073
00:43:59,029 --> 00:44:00,570
Így már feladta, hogy a véletlen hozzáférés.

1074
00:44:00,570 --> 00:44:04,380
>> Tehát nagy O n most a felső
kötött a keresési idő.

1075
00:44:04,380 --> 00:44:07,920
Mi a helyzet omega a keresési?

1076
00:44:07,920 --> 00:44:11,535
Mi ez az alsó határ a keresést
néhány szám a listán?

1077
00:44:11,535 --> 00:44:12,410
KÖZÖNSÉG: [nem hallható]

1078
00:44:12,410 --> 00:44:13,040
David J. MALAN: Mondd még egyszer?

1079
00:44:13,040 --> 00:44:13,420
Közönség: Egy.

1080
00:44:13,420 --> 00:44:13,800
David J. MALAN: Egy.

1081
00:44:13,800 --> 00:44:14,760
Így állandó idő.

1082
00:44:14,760 --> 00:44:17,020
A legjobb esetben, Christine
sőt az elején a lista.

1083
00:44:17,020 --> 00:44:19,020
És keresünk
5-ös, így találtunk rá.

1084
00:44:19,020 --> 00:44:19,787
Tehát nem nagy ügy.

1085
00:44:19,787 --> 00:44:22,370
De kell, hogy legyen a
a lista elején ebben az esetben.

1086
00:44:22,370 --> 00:44:23,745
Mi valami hasonló Delete?

1087
00:44:23,745 --> 00:44:24,717

1088
00:44:24,717 --> 00:44:26,300
Mi van, ha azt szeretné, hogy törölni egy elemet?

1089
00:44:26,300 --> 00:44:29,200
Mi az a felső határ és az alsó határ
A törlés valamit a kapcsolt

1090
00:44:29,200 --> 00:44:29,699
listát?

1091
00:44:29,699 --> 00:44:35,195

1092
00:44:35,195 --> 00:44:36,070
KÖZÖNSÉG: [nem hallható]

1093
00:44:36,070 --> 00:44:36,420
David J. MALAN: Mondd még egyszer?

1094
00:44:36,420 --> 00:44:37,067
Közönség: n.

1095
00:44:37,067 --> 00:44:38,900
David J. MALAN: n
valóban a felső határ.

1096
00:44:38,900 --> 00:44:41,700
Mert a legrosszabb esetben igyekszünk
törölni Jack, mint mi most nem.

1097
00:44:41,700 --> 00:44:43,050
Ő egészen a végén.

1098
00:44:43,050 --> 00:44:45,419
Visz minket örökre, vagy
n lépéseket, hogy megtalálja őt.

1099
00:44:45,419 --> 00:44:46,460
Szóval ez egy felső korlátot.

1100
00:44:46,460 --> 00:44:47,430
Ez lineáris, biztos.

1101
00:44:47,430 --> 00:44:50,970
És a legjobb esetben futási idő vagy
az alsó határt a legjobb esetben

1102
00:44:50,970 --> 00:44:51,975
lenne állandó idő.

1103
00:44:51,975 --> 00:44:54,600
Mert talán megpróbáljuk törölni
Christine, és mi csak szerencséd

1104
00:44:54,600 --> 00:44:55,558
ő az elején.

1105
00:44:55,558 --> 00:44:56,350
Várj egy percet.

1106
00:44:56,350 --> 00:44:59,370
Gabe volt az elején,
és mi is kellett frissíteni Gabe.

1107
00:44:59,370 --> 00:45:01,150
Szóval ez nem csak egy lépés.

1108
00:45:01,150 --> 00:45:04,210
Így van ez valóban állandó
időben, a legjobb esetben,

1109
00:45:04,210 --> 00:45:06,345
hogy távolítsa el a legkisebb elem?

1110
00:45:06,345 --> 00:45:07,360

1111
00:45:07,360 --> 00:45:10,960
Ez, bár lehet, hogy két,
három, vagy akár 100 sornyi kódot,

1112
00:45:10,960 --> 00:45:14,000
ha ez azonos számú
vonalak, nem néhány hurok,

1113
00:45:14,000 --> 00:45:16,577
és független a méret
A lista, teljesen.

1114
00:45:16,577 --> 00:45:18,660
Törlése az elem,
az elején a lista,

1115
00:45:18,660 --> 00:45:21,940
akkor is, ha meg kell foglalkozni
Gabe még mindig állandó idő.

1116
00:45:21,940 --> 00:45:24,220
>> Szóval, ez úgy tűnik, mint egy
hatalmas lépés visszafelé.

1117
00:45:24,220 --> 00:45:27,000
És micsoda időpocsékolás
Ha a hét egy és hét

1118
00:45:27,000 --> 00:45:30,250
nulla volt nem csak
pszeudokódja kód de a tényleges kód

1119
00:45:30,250 --> 00:45:35,780
végrehajtani valamit, ami log
alap n, vagy jelentkezzen, inkább, n, 2-es alapú,

1120
00:45:35,780 --> 00:45:37,150
tekintve a működési idő.

1121
00:45:37,150 --> 00:45:40,710
Akkor miért a fene azt szeretnénk kezdeni
használ valamit, mint a láncolt lista?

1122
00:45:40,710 --> 00:45:41,517
Igen.

1123
00:45:41,517 --> 00:45:44,022
>> Közönség: így hozzá
elemeket a tömb.

1124
00:45:44,022 --> 00:45:46,230
David J. MALAN: így
hozzá elemeket a tömb.

1125
00:45:46,230 --> 00:45:47,550
És ez is a tematikus.

1126
00:45:47,550 --> 00:45:49,740
És mi továbbra is látni
ez, ez a trade-off, sok

1127
00:45:49,740 --> 00:45:51,573
mint láttuk a
trade-off a merge sort.

1128
00:45:51,573 --> 00:45:54,606
Mi tényleg felgyorsíthatja
keresés vagy válogatás, inkább,

1129
00:45:54,606 --> 00:45:57,480
ha kiad egy kicsit több helyet és
egy további darab memória

1130
00:45:57,480 --> 00:45:58,760
vagy egy tömb a merge sort.

1131
00:45:58,760 --> 00:46:01,270
De többet költenek
helyet, de időt takaríthat meg.

1132
00:46:01,270 --> 00:46:04,820
Ebben az esetben, mi
feladom idő, de vagyunk

1133
00:46:04,820 --> 00:46:08,170
egyre rugalmasság,
dinamizmus ha úgy tetszik,

1134
00:46:08,170 --> 00:46:10,280
amely vitathatatlanul pozitív funkciót.

1135
00:46:10,280 --> 00:46:11,520
>> Mi is a kiadások helyet.

1136
00:46:11,520 --> 00:46:13,710
Milyen értelemben kapcsolt
lista drágább

1137
00:46:13,710 --> 00:46:15,700
szempontjából a tér, mint egy tömb?

1138
00:46:15,700 --> 00:46:18,379

1139
00:46:18,379 --> 00:46:19,920
Hol van az extra helyet jön?

1140
00:46:19,920 --> 00:46:20,460
Igen?

1141
00:46:20,460 --> 00:46:21,800
>> KÖZÖNSÉG: [nem hallható] mutató.

1142
00:46:21,800 --> 00:46:23,310
>> David J. MALAN: Igen,
is a mutató.

1143
00:46:23,310 --> 00:46:25,560
Tehát ez minorly bosszantó
hogy többé nem am

1144
00:46:25,560 --> 00:46:27,780
Én tárolása csak egy int
képviseletére int.

1145
00:46:27,780 --> 00:46:30,990
Én tárolása egy int és a
mutatót, ami szintén 32 bit.

1146
00:46:30,990 --> 00:46:33,470
Szóval szó szerint megduplázódott
az összeg a tér szó.

1147
00:46:33,470 --> 00:46:36,040
Szóval ez egy trade-off, de
ez abban az esetben, int.

1148
00:46:36,040 --> 00:46:39,580
Tegyük fel, hogy te nem tárolja int,
de tegyük fel, mindegyik téglalap

1149
00:46:39,580 --> 00:46:43,290
vagy minden egyes ilyen emberre volt képviselő
Egy szó, egy angol szó, amely

1150
00:46:43,290 --> 00:46:46,430
Lehet, hogy öt karakter, 10
karakter, talán még jobban.

1151
00:46:46,430 --> 00:46:49,940
Akkor hozzá csak 32 több bit
Lehet, hogy kevésbé a nagy dolog.

1152
00:46:49,940 --> 00:46:52,160
>> Mi van, ha minden a diákok
a demonstráció

1153
00:46:52,160 --> 00:46:55,107
szó szerint diák struktúrákat az
neveket és házak, és talán

1154
00:46:55,107 --> 00:46:57,065
telefonszámok és a Twitter
kezeli és a hasonlók.

1155
00:46:57,065 --> 00:46:59,564
Tehát az összes mezőt kezdtük
beszélt a minap,

1156
00:46:59,564 --> 00:47:02,410
sokkal kisebb a nagy dolog, mint
a csomópontok minél több érdekes

1157
00:47:02,410 --> 00:47:05,972
és nagy költeni, ugye, egy további
mutató csak azok összekötésére.

1158
00:47:05,972 --> 00:47:07,180
De valóban, ez egy trade-off.

1159
00:47:07,180 --> 00:47:09,560
És valóban, a kód
bonyolultabb, mint majd

1160
00:47:09,560 --> 00:47:11,770
lásd a lapoz
hogy az adott példa.

1161
00:47:11,770 --> 00:47:14,302
De mi van, ha nem volt
néhány szent grál itt.

1162
00:47:14,302 --> 00:47:17,010
Mi lenne, ha nem egy lépést
hátra, hanem egy hatalmas lépés előre

1163
00:47:17,010 --> 00:47:19,180
és végrehajtása adat
szerkezet, amelyen keresztül mi

1164
00:47:19,180 --> 00:47:22,870
megtalálható elemeket, mint a Jack vagy
Christine vagy bármely más elemek

1165
00:47:22,870 --> 00:47:25,870
ebben tömb igazi konstans időben?

1166
00:47:25,870 --> 00:47:26,920
Search állandó.

1167
00:47:26,920 --> 00:47:28,320
Törlés állandó.

1168
00:47:28,320 --> 00:47:29,570
Betét állandó.

1169
00:47:29,570 --> 00:47:32,260
Mindezek a műveletek állandó.

1170
00:47:32,260 --> 00:47:33,750
Ez lenne a szent grál.

1171
00:47:33,750 --> 00:47:36,690
És ez az, ahol mi
felveszi legközelebb.

1172
00:47:36,690 --> 00:47:38,600
Viszlát akkor.

1173
00:47:38,600 --> 00:47:39,371