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

2
00:00:11,460 --> 00:00:12,250
>> DAVID MALAN: Rendben.

3
00:00:12,250 --> 00:00:13,860
Üdv újra a CS50.

4
00:00:13,860 --> 00:00:16,190
Ez a kezdete a 8. héten.

5
00:00:16,190 --> 00:00:21,320
És emlékszem, hogy a probléma meg 5 ért véget
egy kis kihívás.

6
00:00:21,320 --> 00:00:25,210
Tehát feltételezve, hogy vissza az összes
tanítás Fellows és a CA fotói

7
00:00:25,210 --> 00:00:30,480
A card.raw fájlt, akkor jogosult
hogy most meg az összes olyan ember, és

8
00:00:30,480 --> 00:00:34,510
egy szerencsés nyertes hazafelé egy
ezeket a dolgokat, az ugrás mozgás

9
00:00:34,510 --> 00:00:37,450
eszköz, amelyek segítségével a végső
projektek, például.

10
00:00:37,450 --> 00:00:39,860
>> Ez minden évben, vezet
egy kis creepiness.

11
00:00:39,860 --> 00:00:43,480
És amit én gondoltam, csinálni is megosztani
veletek néhány a jegyzeteket, amelyek

12
00:00:43,480 --> 00:00:47,370
ment oda-vissza
a személyzet lista végén.

13
00:00:47,370 --> 00:00:51,110
Például, csak tegnap este, idézet
idézet vége, az egyik a személyzet

14
00:00:51,110 --> 00:00:55,000
tagjai, "Csak volt egy diák kopogás
az ajtómon, hogy egy fotót velem.

15
00:00:55,000 --> 00:00:59,020
Stalker, mondom. "Indult
meglehetősen leíró aztán elköltöztünk

16
00:00:59,020 --> 00:01:02,830
tovább, egy órával később, "volt egy
diák vár rám szakasz után

17
00:01:02,830 --> 00:01:06,080
és volt minden a nevét és fényképét
néhány lapot. "Rendben.

18
00:01:06,080 --> 00:01:09,230
Tehát szervezett, de nem
minden hátborzongató még.

19
00:01:09,230 --> 00:01:12,520
>> Aztán: "Én voltam a városban ezen a hétvégén,
és amikor visszaértem, ott volt a

20
00:01:12,520 --> 00:01:12,630
én

21
00:01:12,630 --> 00:01:16,740
hálószoba. "[nevetés]

22
00:01:16,740 --> 00:01:20,410
DAVID MALAN: Next idézet a személyzet
tag, "egy diák jött a házamba a

23
00:01:20,410 --> 00:01:25,330
Somerville at 4:00 ma reggel. "Next
személyzet, "kaptam az én hotel San

24
00:01:25,330 --> 00:01:30,016
Francisco és a diák várta
nekem a lobby három DSLRs. "

25
00:01:30,016 --> 00:01:31,510
Típusa kamera.

26
00:01:31,510 --> 00:01:34,980
"Én nem is az alkalmazottak ebben a félévben,
hanem egy diák betört a házamba a

27
00:01:34,980 --> 00:01:40,480
reggel és rögzíteni az egészet
Google Glass. "És akkor végül,

28
00:01:40,480 --> 00:01:43,650
"Legalább 12 ember vesztette mohón
vár rám, mikor kiszálltam az

29
00:01:43,650 --> 00:01:44,800
limuzin, aztán

30
00:01:44,800 --> 00:01:46,970
felébredt. "Rendben.

31
00:01:46,970 --> 00:01:57,690
Tehát között a fényképek, ahogy lehet
emlékszem, van ez a fickó itt, hogy ki vagy

32
00:01:57,690 --> 00:02:01,850
is ismert Milo Banana, aki él
Lauren Carvalho, a fejünk

33
00:02:01,850 --> 00:02:02,905
tanítás Fellow.

34
00:02:02,905 --> 00:02:05,170
Milo Milo, gyere ide fiam.

35
00:02:05,170 --> 00:02:06,320
Milo.

36
00:02:06,320 --> 00:02:08,650
Milo.

37
00:02:08,650 --> 00:02:12,230
Ne feledd, van rajta Google Glass, így
mi megmutatjuk, mindezt után.

38
00:02:12,230 --> 00:02:16,190
Tehát ez Milo, ha szeretné
hogy egy fényképet vele utána.

39
00:02:16,190 --> 00:02:18,240
Ha szeretné, hogy néz ki
A közönség is.

40
00:02:18,240 --> 00:02:19,430
OK.

41
00:02:19,430 --> 00:02:20,200
Ez jó felvételeket.

42
00:02:20,200 --> 00:02:22,556
Nos, Milo Banana.

43
00:02:22,556 --> 00:02:23,941
Ó, ne csináld ezt.

44
00:02:23,941 --> 00:02:29,020
>> [Nevetés]

45
00:02:29,020 --> 00:02:29,470
>> OK.

46
00:02:29,470 --> 00:02:34,550
Így egy szót, akkor a mi a tennivaló,
mert ahogy elkezdünk átmenet,

47
00:02:34,550 --> 00:02:38,410
ezen a héten különösen a C-
parancssori környezet PHP és

48
00:02:38,410 --> 00:02:42,720
JavaScript és SQL és HTML-és CSS-ben
A web-alapú környezetben leszünk

49
00:02:42,720 --> 00:02:44,490
felszerelése akkor az összes
nagyobb tudás

50
00:02:44,490 --> 00:02:46,010
lehetséges végső projekteket.

51
00:02:46,010 --> 00:02:49,240
E cél érdekében a kurzus egy
hagyománya szemináriumok, amelyek

52
00:02:49,240 --> 00:02:50,950
vannak érintő témákban
a tanfolyam.

53
00:02:50,950 --> 00:02:54,330
Nagyon kapcsolatos programozás és a
app fejlődés, és így tovább, de

54
00:02:54,330 --> 00:02:57,010
nem feltétlenül által feltárt
során saját tananyag.

55
00:02:57,010 --> 00:03:00,250
>> Tehát, ha lehet, hogy érdekel egy
vagy több az idei szemináriumok,

56
00:03:00,250 --> 00:03:02,530
regisztrálni cs50.net/seminar.

57
00:03:02,530 --> 00:03:06,170
Vannak idősebb szemináriumok
A cs50.net/seminars.

58
00:03:06,170 --> 00:03:10,620
És a naptárban eddig az idei évre
csodálatos Web Apps a Ruby on

59
00:03:10,620 --> 00:03:13,580
Sínek, ami egy alternatív
nyelv PHP.

60
00:03:13,580 --> 00:03:14,900
Számítógépes nyelvészet.

61
00:03:14,900 --> 00:03:18,710
Bevezetés a IOS, amely a
platform, hogy a használt iPhone és

62
00:03:18,710 --> 00:03:19,850
iPad fejlesztés.

63
00:03:19,850 --> 00:03:22,890
JavaScript Web Apps, fogjuk fedezni
, de ezen a szemináriumon, akkor menj

64
00:03:22,890 --> 00:03:24,070
be részletesebben.

65
00:03:24,070 --> 00:03:27,390
>> Leap Motion, így lesz valóban van néhány
A barátaink Leap Motion,

66
00:03:27,390 --> 00:03:29,160
maga a vállalat, csatlakozz hozzánk.

67
00:03:29,160 --> 00:03:31,800
Tomorrow, sőt, hogy a
a gyakorlati szeminárium, ha

68
00:03:31,800 --> 00:03:33,320
az Ön számára.

69
00:03:33,320 --> 00:03:38,770
Meteor.js, egy alternatív technikát
JavaScript segítségével nem a böngészőben,

70
00:03:38,770 --> 00:03:39,970
hanem a szerveren.

71
00:03:39,970 --> 00:03:42,110
Node.js, ami nagyon sok
ebben a szellemben is.

72
00:03:42,110 --> 00:03:43,650
Karcsú Android Design.

73
00:03:43,650 --> 00:03:46,990
Android, hogy egy nagyon népszerű alternatíva
az iOS és a Windows Phone

74
00:03:46,990 --> 00:03:48,790
és más mobil platformokon.

75
00:03:48,790 --> 00:03:51,180
És Web Security aktív védelem.

76
00:03:51,180 --> 00:03:54,590
>> Tehát valójában, ha szeretné
hogy vegyenek részt ebben, hadd

77
00:03:54,590 --> 00:03:55,840
jegyezze meg.

78
00:03:55,840 --> 00:03:57,790
Nagyon boldogok vagyunk, hogy azt mondják, hogy
barátaink a Leap

79
00:03:57,790 --> 00:03:59,140
Motion, mely egy startup -

80
00:03:59,140 --> 00:04:01,300
ez a készülék tényleg most jött
ki néhány hónappal ezelőtt -

81
00:04:01,300 --> 00:04:05,960
kegyesen adományozott 30 ilyen eszközök
Az osztály, mint sok diák, ha

82
00:04:05,960 --> 00:04:08,670
szeretné kölcsönkérni a hardver
felé félév végén, és használja a

83
00:04:08,670 --> 00:04:10,390
tényleges végleges projekt.

84
00:04:10,390 --> 00:04:11,890
Ezek támogatják a több nyelven.

85
00:04:11,890 --> 00:04:16,040
Egyikük sem C, egyikük sem PHP, ezért
megvalósítani egy vagy több ilyen szemináriumok

86
00:04:16,040 --> 00:04:16,899
bizonyulhat az érdeklődés.

87
00:04:16,899 --> 00:04:19,730
És mindegyik lesz forgatták
az esetben, ha nem tudja

88
00:04:19,730 --> 00:04:21,380
részt venni személyesen.

89
00:04:21,380 --> 00:04:25,000
Az ütemterv közzé keresztül
e-mail, ahogy megszilárdul szoba.

90
00:04:25,000 --> 00:04:28,460
>> És végül, ha megy a
projects.cs.50.net, ez egy weboldal

91
00:04:28,460 --> 00:04:31,450
tartunk minden évben, hogy mi meghívjuk
emberek a közösség, kar,

92
00:04:31,450 --> 00:04:36,420
osztályok, a személyzet, és mind a
egy külső CS50 a

93
00:04:36,420 --> 00:04:37,730
javaslatot projektötletek.

94
00:04:37,730 --> 00:04:39,050
Érdekességek a diákcsoportok.

95
00:04:39,050 --> 00:04:40,600
Érdekességek a szervezeti egységek.

96
00:04:40,600 --> 00:04:43,990
Tehát nem pedig ott, ha küzd
A bizonytalanság, hogy mit

97
00:04:43,990 --> 00:04:46,700
magát, szeretne foglalkozni.

98
00:04:46,700 --> 00:04:51,760
>> Így utoljára bevezetett egy vitathatatlanul
bonyolultabb adatstruktúra, mint ahogy azt

99
00:04:51,760 --> 00:04:53,300
látható hét múltban.

100
00:04:53,300 --> 00:04:56,550
Mi volna a tömbök elég
boldogan, mint hasznos, ha

101
00:04:56,550 --> 00:04:58,160
egyszerű adatstruktúra.

102
00:04:58,160 --> 00:05:00,570
Aztán bevezette ezeket, ami
természetesen kapcsolódnak listákat.

103
00:05:00,570 --> 00:05:05,470
És mi volt az egyik motivációja
bevezetésével az adatok szerkezete?

104
00:05:05,470 --> 00:05:06,930
Igen?

105
00:05:06,930 --> 00:05:07,250
Mi ez?

106
00:05:07,250 --> 00:05:08,080
>> Közönség: Dinamikus méretét.

107
00:05:08,080 --> 00:05:09,040
>> DAVID MALAN: Dinamikus méretét.

108
00:05:09,040 --> 00:05:11,890
Tehát míg a tömbben, akkor a
tudja a mérete előre, amikor

109
00:05:11,890 --> 00:05:12,740
Ön osztja azt.

110
00:05:12,740 --> 00:05:14,380
A láncolt lista, akkor nem
Tudnunk kell, hogy.

111
00:05:14,380 --> 00:05:17,610
Ha csak malloc, vagy még általánosabban,
osztja kiegészítő

112
00:05:17,610 --> 00:05:20,720
csomópont, hogy úgy mondjam, minden alkalommal, amikor
szeretné szúrni több adatot.

113
00:05:20,720 --> 00:05:22,670
És csomópont nincs előre meghatározott jelentése.

114
00:05:22,670 --> 00:05:25,580
Ez csak egy általános kifejezés leíró
valamiféle tároló, hogy mi vagyunk

115
00:05:25,580 --> 00:05:29,610
felhasználásával a mi adatstruktúra tárolni
Néhány tétel az érdeklődés, amely ebben az

116
00:05:29,610 --> 00:05:31,750
esetben megtörténhet, hogy egész.

117
00:05:31,750 --> 00:05:33,160
>> De mindig van egy kompromisszum.

118
00:05:33,160 --> 00:05:38,070
Így kapunk dinamikus mérete az adatok
szerkezet, de milyen árat fizetünk?

119
00:05:38,070 --> 00:05:40,040
Mi a hátránya a kapcsolt listák?

120
00:05:40,040 --> 00:05:41,006
Igen?

121
00:05:41,006 --> 00:05:41,980
>> Közönség: több memóriát igényel.

122
00:05:41,980 --> 00:05:44,240
>> DAVID MALAN: többre van szükség,
memória, pontosan hogyan?

123
00:05:44,240 --> 00:05:46,440
>> Közönség: [hangtalan].

124
00:05:46,440 --> 00:05:47,050
>> DAVID MALAN: Pontosan.

125
00:05:47,050 --> 00:05:50,460
Tehát most már mutatókat megkezdéséről
további memória, hogy a korábban

126
00:05:50,460 --> 00:05:53,040
nem volt szükség, mivel az az előnye
egy sor, az természetesen az, hogy

127
00:05:53,040 --> 00:05:54,860
minden rendben van összefüggő, vissza
vissza az vissza, ami

128
00:05:54,860 --> 00:05:56,380
ad véletlen elérésű.

129
00:05:56,380 --> 00:06:00,710
Mivel csak a szögletes zárójel
jelöléssel, vagy nagyobb technikai mutató

130
00:06:00,710 --> 00:06:03,580
számtani, nagyon egyszerű felül
tud hozzáférni

131
00:06:03,580 --> 00:06:05,700
elemek állandó időben.

132
00:06:05,700 --> 00:06:08,975
És valóban, ez a fajta hint
egy ár, amit fizetünk a

133
00:06:08,975 --> 00:06:09,760
láncolt lista.

134
00:06:09,760 --> 00:06:13,890
>> Mi történik a futási ideje
valami, mint a Search, ha azt akarom, hogy

135
00:06:13,890 --> 00:06:17,270
néhány értéket és belül
A láncolt lista?

136
00:06:17,270 --> 00:06:20,290
Mit jelent a működési idő lesz?

137
00:06:20,290 --> 00:06:21,560
Big O n.

138
00:06:21,560 --> 00:06:24,060
Ha ez a sorrendje?

139
00:06:24,060 --> 00:06:25,440
Mi van, ha az adat struktúra sorrendje?

140
00:06:25,440 --> 00:06:28,640
Lehet, hogy jobban, mint a nagy
O n a keresést?

141
00:06:28,640 --> 00:06:31,700
Nem, mert a legrosszabb esetben ez talán
nagyon jól lehet válogatni, de ez a szám

142
00:06:31,700 --> 00:06:32,950
keres lehet nagy.

143
00:06:32,950 --> 00:06:35,370
Lehet, hogy a szám 100, ami
Előfordulhat, hogy az összes

144
00:06:35,370 --> 00:06:36,410
az utat a végén.

145
00:06:36,410 --> 00:06:39,950
És mivel csak akkor férhet hozzá a kapcsolt
listát a végrehajtás

146
00:06:39,950 --> 00:06:42,690
ahogy az első csomópont, akkor
mindig ilyen a szerencse.

147
00:06:42,690 --> 00:06:47,450
Meg kell áthalad az egészet
az első az utolsó, hogy megtalálják

148
00:06:47,450 --> 00:06:49,150
az a nagy érték, mint 100 fő.

149
00:06:49,150 --> 00:06:51,350
Vagy annak megállapítására, hogy
nincs még ott.

150
00:06:51,350 --> 00:06:55,960
>> Így nem tudja, mit algoritmus adat
szerkezet úgy néz ki, mint ez?

151
00:06:55,960 --> 00:06:59,460
Nem tehetünk bináris keresés, mert a
bináris keresés szükséges, hogy mi volt

152
00:06:59,460 --> 00:07:00,740
véletlen elérésű.

153
00:07:00,740 --> 00:07:04,500
Így egyszerűen ugrani helyről a
helyre anélkül, hogy követni

154
00:07:04,500 --> 00:07:07,080
Ezen zsemlemorzsa formában
Mindezen mutatók.

155
00:07:07,080 --> 00:07:08,300
>> Nos, hogyan is alkalmazzák ezt?

156
00:07:08,300 --> 00:07:12,830
Nos, ha elmegyünk a képernyő itt, ha
akkor gyorsan újraimplementálni az adatok

157
00:07:12,830 --> 00:07:13,440
struktúra -

158
00:07:13,440 --> 00:07:15,670
a kézírás nem minden
jó, de megpróbáljuk.

159
00:07:15,670 --> 00:07:22,030
Tehát typedef struct, és mit tettem
szeretnénk felhívni a dolog itt?

160
00:07:22,030 --> 00:07:22,960
Node.

161
00:07:22,960 --> 00:07:24,580
Úgyhogy minket kezdődött.

162
00:07:24,580 --> 00:07:27,860
És most, mit kell belsejében
az adatszerkezetet, amely egyszeresen

163
00:07:27,860 --> 00:07:28,430
láncolt lista?

164
00:07:28,430 --> 00:07:29,950
Hány területen?

165
00:07:29,950 --> 00:07:30,450
>> Tehát két.

166
00:07:30,450 --> 00:07:31,570
Egy elég egyszerű.

167
00:07:31,570 --> 00:07:33,050
Így int n.

168
00:07:33,050 --> 00:07:35,930
És nevezhetjük n, amit csak akarunk,
de meg kell egy int, ha vagyunk

169
00:07:35,930 --> 00:07:37,660
végrehajtása láncolt lista a ints.

170
00:07:37,660 --> 00:07:41,920
És most mit jelent a második
terület kell?

171
00:07:41,920 --> 00:07:43,460
Struct node *.

172
00:07:43,460 --> 00:07:50,570
Tehát, ha én struct node *, aztán
nevezhetjük ezt is, amit akarok,

173
00:07:50,570 --> 00:07:53,510
de csak hogy világos hívom
mellé, ahogy csináltam.

174
00:07:53,510 --> 00:07:55,270
És aztán majd becsukom a zárójelek.

175
00:07:55,270 --> 00:08:00,700
>> És most, mint a múltkor,
Tettem node ide.

176
00:08:00,700 --> 00:08:03,830
De ha én kijelentette, ez a
node, miért törődöm, hogy olyan

177
00:08:03,830 --> 00:08:07,320
verbose itt kijelentette struktúra
node * mellett, szemben

178
00:08:07,320 --> 00:08:09,210
csak node * a következő lépés?

179
00:08:09,210 --> 00:08:09,904
Igen?

180
00:08:09,904 --> 00:08:12,810
>> Közönség: [hangtalan].

181
00:08:12,810 --> 00:08:14,050
>> DAVID MALAN: Pontosan.

182
00:08:14,050 --> 00:08:14,530
Pontosan.

183
00:08:14,530 --> 00:08:18,320
Mivel a C igazán viszi szó szerint és
csak akkor találkozik a meghatározása csomópont

184
00:08:18,320 --> 00:08:21,230
idáig, akkor nem
hivatkoznak rá itt.

185
00:08:21,230 --> 00:08:24,760
Tehát ez a fajta elsőbbségi
nyilatkozat itt, ami kétségkívül

186
00:08:24,760 --> 00:08:25,390
annál részletesebb.

187
00:08:25,390 --> 00:08:27,810
Struct csomópont, ez azt jelenti,
most már elérheti

188
00:08:27,810 --> 00:08:29,760
belsejében az adatszerkezetet.

189
00:08:29,760 --> 00:08:33,370
>> És mint félre, mert ez
válik egy kicsit szubjektív most,

190
00:08:33,370 --> 00:08:36,230
A csillag technikailag megy itt,
ez megy itt, akkor

191
00:08:36,230 --> 00:08:37,179
még megy a közepén.

192
00:08:37,179 --> 00:08:39,890
Már elfogadott, a stílus útmutató
A kurzus az egyezmény helyezése

193
00:08:39,890 --> 00:08:42,299
a csillag mellett az adatok
típusú, ami ebben az esetben,

194
00:08:42,299 --> 00:08:43,460
lenne struct csomópont.

195
00:08:43,460 --> 00:08:46,620
De észre a sok tankönyvek és
Online referenciák, lehet, hogy valóban

196
00:08:46,620 --> 00:08:48,450
látni a másik oldalon.

197
00:08:48,450 --> 00:08:52,200
De csak észre, hogy a két fog ténylegesen
működik, és egyszerűen ki kell

198
00:08:52,200 --> 00:08:52,970
következetes.

199
00:08:52,970 --> 00:08:53,580
>> Rendben van.

200
00:08:53,580 --> 00:08:55,630
Szóval ez volt a nyilatkozat
A struct csomópont.

201
00:08:55,630 --> 00:08:59,430
De aztán elkezdtem több
kifinomult dolgok.

202
00:08:59,430 --> 00:09:03,410
Például, úgy döntöttünk, hogy be
olyasmi, mint egy hash tábla.

203
00:09:03,410 --> 00:09:08,160
Tehát itt van egy hash tábla méret n
indexei 0-tól a bal felső sarokban, hogy n

204
00:09:08,160 --> 00:09:09,690
mínusz 1 a bal alsó sarokban.

205
00:09:09,690 --> 00:09:11,640
Ez lehet egy hash
táblázat semmit.

206
00:09:11,640 --> 00:09:15,340
De milyen dolgok beszélünk
körülbelül egy hash tábla?

207
00:09:15,340 --> 00:09:18,370
Tárolása, mi?

208
00:09:18,370 --> 00:09:18,800
>> Nevek.

209
00:09:18,800 --> 00:09:20,870
Megtehetjük nevek, mint a
mi a múltkor.

210
00:09:20,870 --> 00:09:22,200
És tényleg, bármi tárolható.

211
00:09:22,200 --> 00:09:24,640
És majd meglátjuk, ezt újra
PHP és JavaScript.

212
00:09:24,640 --> 00:09:28,550
A hash tábla egy szép egyfajta svájci
Bicska, amely lehetővé teszi, hogy tárolja

213
00:09:28,550 --> 00:09:33,690
nagyjából bármit belsejében
azt tömörítő kulcsokat értékeket.

214
00:09:33,690 --> 00:09:34,770
Keys értékekkel.

215
00:09:34,770 --> 00:09:37,800
>> Most ebben az egyszerű esetben, a
gombok csak számok.

216
00:09:37,800 --> 00:09:40,380
Mi megvalósítása hash
tábla, mint egy tömb.

217
00:09:40,380 --> 00:09:43,500
És így a gombok 0,
1, 2, és így tovább.

218
00:09:43,500 --> 00:09:47,200
És így mi, emberek, úgy döntött, utolsó
héten, hogy tudod mit, ha vagyunk

219
00:09:47,200 --> 00:09:50,410
majd neveket, nézzük csak
önkényesen, de elég ésszerűen,

220
00:09:50,410 --> 00:09:54,680
Feltételezem, hogy Alice, egy A név,
majd csak indexelt be 0-ra.

221
00:09:54,680 --> 00:09:58,030
És Bob, a B név lesz indexelve
ba 1, és így tovább.

222
00:09:58,030 --> 00:10:02,490
Tehát volt egy leképezés bemenetek között,
amelyek vonósok, és a hash

223
00:10:02,490 --> 00:10:04,560
helyek, melyek számokat.

224
00:10:04,560 --> 00:10:07,740
>> Annak érdekében, hogy a folyamatot általában ismert
a hash függvényt, és akkor igazán

225
00:10:07,740 --> 00:10:09,130
végrehajtja a kódot.

226
00:10:09,130 --> 00:10:12,080
Ha akartam, hogy végre egy hash függvény
hogy pontosan mit is

227
00:10:12,080 --> 00:10:17,070
csak le az utolsó alkalom, talán
kijelentik, hogy a funkció kerül, mint

228
00:10:17,070 --> 00:10:18,330
input például -

229
00:10:18,330 --> 00:10:22,190
és csináljuk ezt a
képernyő ide.

230
00:10:22,190 --> 00:10:26,180
Ha akartam, hogy végre egy hash
funkció, mondhatnám

231
00:10:26,180 --> 00:10:27,410
valami ilyesmi.

232
00:10:27,410 --> 00:10:29,030
>> Ez lesz, hogy visszatérjen egy int.

233
00:10:29,030 --> 00:10:33,600
Ez lesz az úgynevezett hash, és ez
fog elfogadni érvként a

234
00:10:33,600 --> 00:10:38,920
string, vagy mi lehet a megfelelő most,
és azt mondják char *, hívjuk meg s.

235
00:10:38,920 --> 00:10:43,840
És akkor ezt a funkciót kell tennie,
végül is visszatér egy int.

236
00:10:43,840 --> 00:10:45,990
Most, hogy ez, amely
Nem ennyire egyértelmű.

237
00:10:45,990 --> 00:10:49,510
Fogom végrehajtani ezt a nélkül
formájában hiba ellenőrzése most.

238
00:10:49,510 --> 00:10:55,740
Én csak úgy vakon mondani, vissza
bármi van s konzol 0, mínusz,

239
00:10:55,740 --> 00:10:58,850
mondjuk, a tőke A pontosvessző.

240
00:10:58,850 --> 00:10:59,960
>> Teljesen megtört.

241
00:10:59,960 --> 00:11:02,620
Ez nem tökéletes, mert
Egy, mi van, ha s nulla?

242
00:11:02,620 --> 00:11:04,000
Rossz dolgok fognak történni.

243
00:11:04,000 --> 00:11:07,940
Két, mi van, ha az első betű a
név nem nagybetűvel?

244
00:11:07,940 --> 00:11:09,860
Ez nem fog fordulni
ki jól.

245
00:11:09,860 --> 00:11:11,970
Lehet, hogy a kisbetű
vagy nem betű egyáltalán.

246
00:11:11,970 --> 00:11:15,520
Így teljesen javítani itt,
de ez az alapötlet.

247
00:11:15,520 --> 00:11:19,010
>> Amit leírt a múlt héten szóban, mint
csak egy folyamat feltérképezése Alice

248
00:11:19,010 --> 00:11:23,360
0 és Bob 1 lehet kifejezni
bizonnyal több formulaically a C

249
00:11:23,360 --> 00:11:24,320
működik itt.

250
00:11:24,320 --> 00:11:28,630
Megint hívott hash, vesz egy string
bemenet, és aztán valahogy csinál valamit

251
00:11:28,630 --> 00:11:31,020
azzal, hogy a bemeneti, hogy készítsen egy kimenetet.

252
00:11:31,020 --> 00:11:34,130
Nem úgy, mint a fekete doboz leírás
hogy már régóta kész.

253
00:11:34,130 --> 00:11:36,550
Nem tudom, hogy ez lehet,
dolgozik a motorháztető alatt.

254
00:11:36,550 --> 00:11:40,120
>> A probléma szett 6, az egyik kihívás
az Ön számára, hogy eldöntse, hogy milyen

255
00:11:40,120 --> 00:11:41,920
lesz a hash függvény legyen?

256
00:11:41,920 --> 00:11:45,760
Mi lesz benne, hogy a fekete
doboz, és valószínűleg ez lesz a

257
00:11:45,760 --> 00:11:50,380
kicsit érdekesebb, mint ez, és
határozottan több a hibalehetőség

258
00:11:50,380 --> 00:11:53,180
ellenőrzés, mint az adott
végrehajtását.

259
00:11:53,180 --> 00:11:54,580
>> De a problémák merülnek fel, ugye?

260
00:11:54,580 --> 00:11:57,760
Ha van egy adatstruktúra, mint ez
Egy, mi az egyik probléma,

261
00:11:57,760 --> 00:12:01,600
akkor befut idővel behelyezi
egyre több nevet a

262
00:12:01,600 --> 00:12:02,880
hash tábla?

263
00:12:02,880 --> 00:12:04,630
Kapsz ütközések, ugye?

264
00:12:04,630 --> 00:12:07,560
Mi van, ha Alice és Áron,
két ember, akiknek a neve történt

265
00:12:07,560 --> 00:12:08,190
kezdeni egy?

266
00:12:08,190 --> 00:12:11,660
Ez felveti a kérdést, ahol a
hogy a második ilyen név?

267
00:12:11,660 --> 00:12:15,050
>> Nos, lehet, hogy naiv módon csak tedd
ahol Bob tartozik, de aztán Bob

268
00:12:15,050 --> 00:12:17,300
olyan csavaros, ha megpróbálja
be a nevét a következő és

269
00:12:17,300 --> 00:12:18,240
nincs hely neki.

270
00:12:18,240 --> 00:12:21,400
Szóval lehet, hogy fel Bob hol van Charlie,
és el tudják képzelni ezt a nagyon gyorsan

271
00:12:21,400 --> 00:12:23,020
háruló egy kis rendetlenség.

272
00:12:23,020 --> 00:12:25,600
Valami lineáris a végén, ahol a
Csak meg kell keresni az egészet

273
00:12:25,600 --> 00:12:28,190
keres Alice és Bob
vagy Aaron vagy Charlie.

274
00:12:28,190 --> 00:12:33,230
>> Tehát ahelyett, hogy azt javasolta, ahelyett, hogy csak
lineárisan szondázás nyitott terek

275
00:12:33,230 --> 00:12:36,450
és plopping a nevét ott,
javasolt szakértő megközelítés.

276
00:12:36,450 --> 00:12:41,740
A hash tábla végre még egy
tömb indexek, de az adatok típusát

277
00:12:41,740 --> 00:12:44,500
az indexek már voltak mutatók.

278
00:12:44,500 --> 00:12:47,360
Mutatók mi?

279
00:12:47,360 --> 00:12:48,730
Mutatók láncolt listák.

280
00:12:48,730 --> 00:12:53,330
>> Mert emlékszem, hogy a csatolt lista
tényleg csak egy mutató egy csomópont, és

281
00:12:53,330 --> 00:12:57,110
A csomópont a következő mezőre, és a csomópont
van egy következő mezőre, és így tovább.

282
00:12:57,110 --> 00:13:00,690
Így most már gondolni a tömb
A bal oldali egy hash táblát

283
00:13:00,690 --> 00:13:01,820
ami a láncolt lista.

284
00:13:01,820 --> 00:13:07,000
Az előnye, hogy melyik az, ha kap egy
ütközés között Alice és Áron,

285
00:13:07,000 --> 00:13:09,300
mit csinálsz a
második ilyen ember?

286
00:13:09,300 --> 00:13:14,150
Csak csatlakoztassa őt a
végén, vagy akár a kezdet

287
00:13:14,150 --> 00:13:15,490
, hogy a láncolt lista.

288
00:13:15,490 --> 00:13:17,340
>> És valóban, most csak a tészta
hogy csak egy pillanatra.

289
00:13:17,340 --> 00:13:18,640
Hol lenne a legtöbb értelme?

290
00:13:18,640 --> 00:13:22,060
Ha be Alice, és ő végül a
Az első hely, akkor megpróbálom

291
00:13:22,060 --> 00:13:25,310
Aaron be nevét, és ott
nyilván egy ütközés, rakjam

292
00:13:25,310 --> 00:13:27,400
neki az elején
A láncolt lista?

293
00:13:27,400 --> 00:13:30,944
Ez az, hogy az első helyre,
vagy végén?

294
00:13:30,944 --> 00:13:31,440
>> Közönség: [hangtalan].

295
00:13:31,440 --> 00:13:31,990
>> DAVID MALAN: OK.

296
00:13:31,990 --> 00:13:32,490
Hallottam elején.

297
00:13:32,490 --> 00:13:33,903
Miért az elején?

298
00:13:33,903 --> 00:13:34,750
>> Közönség: [hangtalan].

299
00:13:34,750 --> 00:13:34,940
>> DAVID MALAN: OK.

300
00:13:34,940 --> 00:13:36,520
Ez ábécé, így szép.

301
00:13:36,520 --> 00:13:37,330
Ez egy jó tulajdonság.

302
00:13:37,330 --> 00:13:39,335
Ez megment egy kis időt potenciálisan.

303
00:13:39,335 --> 00:13:43,290
Ez nem engedi bináris keresést, de
Lehet, legalább tudja, hogy kitörjön

304
00:13:43,290 --> 00:13:47,340
egy hurok, ha látom, jól vagyok, ahogy
Aaron múltban lenne ebben

305
00:13:47,340 --> 00:13:48,310
rendezett láncolt lista.

306
00:13:48,310 --> 00:13:50,360
Nincs vesztegetni az időmet keres
egészen a végéig.

307
00:13:50,360 --> 00:13:51,530
Szóval ez ésszerű.

308
00:13:51,530 --> 00:13:54,710
Miért más is a beszúrni kívánt
Az ütköző név a

309
00:13:54,710 --> 00:13:56,660
elején a lista?

310
00:13:56,660 --> 00:13:57,397
Mi ez?

311
00:13:57,397 --> 00:13:58,680
>> Közönség: [hangtalan].

312
00:13:58,680 --> 00:14:00,820
>> DAVID MALAN: Lehet, hogy egy hosszú ideig
hogy az a lista végére.

313
00:14:00,820 --> 00:14:02,490
És valóban, a hosszabb és hosszabb.

314
00:14:02,490 --> 00:14:04,920
Minél több neveket beszúrni a
Kezdjünk egy, a hosszabb,

315
00:14:04,920 --> 00:14:06,280
láncot fog kapni.

316
00:14:06,280 --> 00:14:07,890
A hosszabb, összefüggő
lista fog kapni.

317
00:14:07,890 --> 00:14:09,420
Szóval tényleg csak
az idejét vesztegeti.

318
00:14:09,420 --> 00:14:14,070
Lehet, hogy te jobb megőrzése
állandó behelyezésének időpontjával, nagy O 1,

319
00:14:14,070 --> 00:14:18,470
által mindig amivel az ütköző nevet
az elején a láncolt lista,

320
00:14:18,470 --> 00:14:21,230
és nem annyira aggasztó
a válogatás.

321
00:14:21,230 --> 00:14:22,600
>> Mi a legjobb megoldás?

322
00:14:22,600 --> 00:14:23,320
Ez világos.

323
00:14:23,320 --> 00:14:26,140
Ez a fajta attól függ, mi a
eloszlás, amit a minta

324
00:14:26,140 --> 00:14:27,850
A neveket behelyezésekor.

325
00:14:27,850 --> 00:14:29,430
Ez nem feltétlenül
nyilvánvaló válasz.

326
00:14:29,430 --> 00:14:33,100
De itt az, megint,
tervezési lehetőséget.

327
00:14:33,100 --> 00:14:37,220
>> Szóval akkor nézett ez a dolog, ami
valóban a másik nagy lehetőség

328
00:14:37,220 --> 00:14:38,180
A p-set 6.

329
00:14:38,180 --> 00:14:41,770
És észre, ha még nem tette meg,
Zamyla merülés mindkét, hash

330
00:14:41,770 --> 00:14:43,260
asztalok és próbálkozás, részletesebben.

331
00:14:43,260 --> 00:14:45,630
És a video Walkthrough az
ágyazott p-set spec.

332
00:14:45,630 --> 00:14:46,590
Ez egy Trie -

333
00:14:46,590 --> 00:14:51,670
T-R-I-E. És mi volt érdekes
az volt, hogy a működési idő

334
00:14:51,670 --> 00:14:59,510
keres egy nevet, mint a Maxwell
utoljára, nagy volt Ó, mi?

335
00:14:59,510 --> 00:15:01,040
Mi ez?

336
00:15:01,040 --> 00:15:01,920
>> Közönség: A betűk száma.

337
00:15:01,920 --> 00:15:02,550
>> DAVID MALAN: száma leveleket.

338
00:15:02,550 --> 00:15:03,210
Hallottam két dolgot.

339
00:15:03,210 --> 00:15:04,630
Betűk száma és a folyamatos idő.

340
00:15:04,630 --> 00:15:05,540
Szóval megy az első.

341
00:15:05,540 --> 00:15:06,410
A betűk száma.

342
00:15:06,410 --> 00:15:10,195
Nos, ez az adat struktúra, emlékszem, az
mint egy fa, egy családfát, minden

343
00:15:10,195 --> 00:15:12,860
akinek a csomópontok alkotják a tömbök.

344
00:15:12,860 --> 00:15:16,300
És ezek a tömbök mutatókat
más ilyen csomópontok, vagy más ilyen

345
00:15:16,300 --> 00:15:17,670
tömbök a fán.

346
00:15:17,670 --> 00:15:22,890
>> Tehát, ha azt akartuk, hogy majd meg
hogy Maxwell van itt, lehet, hogy el

347
00:15:22,890 --> 00:15:26,890
Az első tömb, az egyik legfontosabb a
a fa, az úgynevezett gyökér, tetején

348
00:15:26,890 --> 00:15:30,521
A Trie, és kövesse az m mutató,
akkor a mutató, akkor x,

349
00:15:30,521 --> 00:15:31,710
W, E, L, L.

350
00:15:31,710 --> 00:15:34,910
És akkor, amikor látom, néhány speciális szimbólum,
jelöli itt, mint egy háromszög.

351
00:15:34,910 --> 00:15:38,480
A kód látni fogod, javasoljuk, hogy
végre egy bool, csak azt mondom, igen

352
00:15:38,480 --> 00:15:40,540
vagy nem, a szó megáll itt.

353
00:15:40,540 --> 00:15:45,270
>> Nos, ha már elment a M-A-X-W-E-L-L,
érzés hét, talán

354
00:15:45,270 --> 00:15:48,910
nyolc, ha megy valaki mellette, nyolc
lépéseket, hogy megtalálja Maxwell.

355
00:15:48,910 --> 00:15:53,050
Vagy nevezzük K. De emlékszem utolsó
alkalommal, azt állította, hogy ha van

356
00:15:53,050 --> 00:15:57,540
reálisan maximum hosszúság
szó, mint a 40-valami furcsa karakterek, a

357
00:15:57,540 --> 00:16:00,810
maximális hossza azt jelenti,
állandó érték.

358
00:16:00,810 --> 00:16:05,770
Szóval tényleg, igen, ez technikailag nagy O
8 vagy 7, vagy igazán nagy O K. azonban

359
00:16:05,770 --> 00:16:09,420
ha van egy véges kupakot milyen
K lehet, hogy ez egy állandó.

360
00:16:09,420 --> 00:16:12,080
És ez nagy O 1-es
a végén a nap.

361
00:16:12,080 --> 00:16:13,040
>> Nem a valós világban.

362
00:16:13,040 --> 00:16:15,960
Nem, ha tényleg kezdeni nézni
az óra, mint a program fut.

363
00:16:15,960 --> 00:16:20,690
Ez feltétlenül lesz egy kicsit
lassabb, mint igazán állandó

364
00:16:20,690 --> 00:16:21,840
időt egy lépésben.

365
00:16:21,840 --> 00:16:25,540
Ez lesz hét-nyolc lépés,
de ez sokkal, de sokkal jobb

366
00:16:25,540 --> 00:16:30,080
mint egy algoritmus, mint a nagy O n, hogy
méretétől függ, hogy mi van a

367
00:16:30,080 --> 00:16:31,220
adatstruktúra.

368
00:16:31,220 --> 00:16:34,970
>> Figyeljük meg a fejjel itt tudjuk be
egy millió további nevek ebbe

369
00:16:34,970 --> 00:16:38,170
adatstruktúra, de hány lépés
ez fog minket megtalálni

370
00:16:38,170 --> 00:16:40,480
Maxwell ebben az esetben?

371
00:16:40,480 --> 00:16:40,780
Nincs.

372
00:16:40,780 --> 00:16:41,820
Ő nem befolyásolja.

373
00:16:41,820 --> 00:16:45,480
És a mai napig, nem hiszem, hogy láttam
egy példa egy adatstruktúra vagy

374
00:16:45,480 --> 00:16:48,560
algoritmus teljesen
befolyásolja a külső

375
00:16:48,560 --> 00:16:50,040
viselkedések, mint ezt.

376
00:16:50,040 --> 00:16:51,160
De ez nem lehet csodálatos.

377
00:16:51,160 --> 00:16:52,900
Ez nem lehet az egyetlen megoldás
a p-set

378
00:16:52,900 --> 00:16:53,570
>> És ez nem az.

379
00:16:53,570 --> 00:16:55,980
Ez nem szükségszerűen az adatok
struktúra kell vonzódik,

380
00:16:55,980 --> 00:16:58,220
mert mint hash táblák, kompromisszum.

381
00:16:58,220 --> 00:17:00,500
Mi az ár, amit fizetni itt?

382
00:17:00,500 --> 00:17:00,940
Memória.

383
00:17:00,940 --> 00:17:02,890
Úgy értem, ez egy kegyetlen
memória.

384
00:17:02,890 --> 00:17:05,569
És akkor nem igazán látom itt, mert
A szerző ezt a képet

385
00:17:05,569 --> 00:17:09,420
nyilvánvalóan csonka összes tömbök,
és nem látunk sok A és a

386
00:17:09,420 --> 00:17:12,700
B és C és a Q és a Y
és Z ezen tömbök.

387
00:17:12,700 --> 00:17:13,630
De ott vannak.

388
00:17:13,630 --> 00:17:17,660
>> Minden ilyen csomópontok egy egész tömb
néhány 26 vagy több bájt, mindegyik

389
00:17:17,660 --> 00:17:19,170
ami egy levelet.

390
00:17:19,170 --> 00:17:22,920
27. a mi esetünkben, hogy tudjuk támogatni
aposztrófok a probléma meg.

391
00:17:22,920 --> 00:17:27,030
Tehát ez az adat struktúra valóban,
Nagyon sűrű és széles.

392
00:17:27,030 --> 00:17:30,880
És ez csak talán a végén lassul
dolgokat, vagy legalábbis olcsóbb a

393
00:17:30,880 --> 00:17:32,240
sokkal több helyet.

394
00:17:32,240 --> 00:17:34,020
De ismétlem, levonhatjuk
összehasonlítás itt.

395
00:17:34,020 --> 00:17:39,190
>> Emlékezzünk egy kicsit vissza, hogy sok mindent elért
izgalmasabb futó időt válogatás

396
00:17:39,190 --> 00:17:42,880
ha az általunk használt merge sort, de az ár
fizettünk elérni n log n merge

397
00:17:42,880 --> 00:17:46,930
sort kell, hogy töltünk
még milyen erőforrás?

398
00:17:46,930 --> 00:17:47,690
Több hely.

399
00:17:47,690 --> 00:17:50,530
Szükségünk volt egy másodlagos tömb
másolni az embereket, mint

400
00:17:50,530 --> 00:17:51,620
mi itt a színpadon.

401
00:17:51,620 --> 00:17:55,880
Tehát újra, nincs egyértelmű győztes,
de csak szubjektív tervezés

402
00:17:55,880 --> 00:17:57,710
döntéseket kell hozni.

403
00:17:57,710 --> 00:17:58,060
>> Rendben van.

404
00:17:58,060 --> 00:17:59,130
Szóval, mi a helyzet ezzel?

405
00:17:59,130 --> 00:18:02,050
Bárki, aki ismeri, amely D-Hall?

406
00:18:02,050 --> 00:18:02,440
OK.

407
00:18:02,440 --> 00:18:03,170
Így hárman nem.

408
00:18:03,170 --> 00:18:03,750
Mather House.

409
00:18:03,750 --> 00:18:05,070
Tehát ez a Mather étkezőjében.

410
00:18:05,070 --> 00:18:09,650
Lefogadom, minden étkezőben van
halom tálcák, mint ez.

411
00:18:09,650 --> 00:18:11,950
És ez valóban reprezentatív
valamit most már

412
00:18:11,950 --> 00:18:13,050
nyilván látott már.

413
00:18:13,050 --> 00:18:14,850
Úgy hívják, hogy szó szerint egy verem.

414
00:18:14,850 --> 00:18:18,970
És a verem, tekintve a
számítógép memóriája, ahol adat megy

415
00:18:18,970 --> 00:18:20,460
míg a funkciók, hogy hívják.

416
00:18:20,460 --> 00:18:23,410
>> Például, milyen dolgok
a verem tekintetében a

417
00:18:23,410 --> 00:18:27,420
Memória kialakítása már tárgyalt
hetekben múltban?

418
00:18:27,420 --> 00:18:28,736
Mi ez?

419
00:18:28,736 --> 00:18:29,670
>> Közönség: hívások a funkciókat.

420
00:18:29,670 --> 00:18:30,260
>> DAVID MALAN: Sajnálom.

421
00:18:30,260 --> 00:18:31,210
>> Közönség: hívások a funkciókat.

422
00:18:31,210 --> 00:18:33,590
>> DAVID MALAN: kéri a funkciók, de
pontosabban, mi van az egyes

423
00:18:33,590 --> 00:18:35,340
a keretek?

424
00:18:35,340 --> 00:18:37,220
Milyen dolgokat?

425
00:18:37,220 --> 00:18:37,460
Igen.

426
00:18:37,460 --> 00:18:38,500
Tehát lokális változók.

427
00:18:38,500 --> 00:18:43,080
Bármikor szükségünk van egy kis helyi tároló,
mint érv, vagy int I, vagy int

428
00:18:43,080 --> 00:18:45,940
temp, vagy bármi, a helyi
változó, voltunk

429
00:18:45,940 --> 00:18:47,210
üzembe, hogy a verem.

430
00:18:47,210 --> 00:18:49,610
És ez egy verem, mert
, hogy a réteg ötlet.

431
00:18:49,610 --> 00:18:52,940
Csak olyan mérkőzés a valóságnak,
a koncepció figyelemmel.

432
00:18:52,940 --> 00:18:56,650
>> De kiderül, hogy egy köteg is
kell tekinteni, mint egy adat struktúra, egy

433
00:18:56,650 --> 00:19:00,110
alternatíva, hogy egy sor, egy másik
egy láncolt lista.

434
00:19:00,110 --> 00:19:02,770
Valami fogalmilag sokkal érdekesebb
még lehet, hogy a

435
00:19:02,770 --> 00:19:06,030
megvalósíthatók bármelyik ezek
dolgok, de ez egy más típusú

436
00:19:06,030 --> 00:19:09,140
adatstruktúra támogatja, de tényleg,
csak két művelet.

437
00:19:09,140 --> 00:19:11,000
De lehet hozzá a szakértő
funkciók, mint ezek.

438
00:19:11,000 --> 00:19:12,180
De ezek az alapok -

439
00:19:12,180 --> 00:19:13,510
push és pop.

440
00:19:13,510 --> 00:19:19,240
>> És az ötlet egy halom, hogy ha én
van itt, vagy anélkül Annenberg

441
00:19:19,240 --> 00:19:22,880
tudva, egy tálcát a szomszédból
A 9-es szám rajta.

442
00:19:22,880 --> 00:19:23,870
Tehát csak egy int.

443
00:19:23,870 --> 00:19:26,990
És azt akarom, hogy álljon a rá az adatokat
szerkezet, amely jelenleg üres.

444
00:19:26,990 --> 00:19:28,790
Tekintsük ezt az alján a verem.

445
00:19:28,790 --> 00:19:33,150
Én nyomja ezt a számot 9-re a
verem, és most ott van.

446
00:19:33,150 --> 00:19:36,040
>> De az érdekes dolog a stack
az, hogy ha most akarja nyomni

447
00:19:36,040 --> 00:19:40,210
más érték, mint a 17, és nyomja
ez a verembe, azt fogom tenni

448
00:19:40,210 --> 00:19:43,290
az egyetlen intuitív dolog, én csak megy
hogy azt ott, ahol mi, emberek

449
00:19:43,290 --> 00:19:45,180
hajlamos lenne, hogy azt, a tetejére.

450
00:19:45,180 --> 00:19:48,850
De ami igazán érdekes már
az, hogyan jutok 9-kor?

451
00:19:48,850 --> 00:19:50,670
Tudod, én nem mentes némi erőfeszítést.

452
00:19:50,670 --> 00:19:54,070
>> Szóval mi az érdekes a
a verem, hogy a tervezés,

453
00:19:54,070 --> 00:19:56,330
ez egy LIFO adatszerkezet.

454
00:19:56,330 --> 00:19:59,680
Silly leírási módja
utolsó, first out.

455
00:19:59,680 --> 00:20:03,280
Tehát az utolsó szám
ebben az időben 17 éves volt.

456
00:20:03,280 --> 00:20:07,540
Tehát, ha azt akarom, hogy a pop valamit le
a verem, akkor csak 17.

457
00:20:07,540 --> 00:20:11,890
Szóval van egy kötelező sorrendben
műveletek itt, ahol az utolsó elem

458
00:20:11,890 --> 00:20:14,260
az is, hogy az első egyet.

459
00:20:14,260 --> 00:20:16,440
Ezért a rövidítése, LIFO.

460
00:20:16,440 --> 00:20:19,160
>> Miért lehet ez hasznos lehet?

461
00:20:19,160 --> 00:20:22,690
Vannak-e összefüggésben, amelyben azt
szeretnék egy adatstruktúra, mint ez?

462
00:20:22,690 --> 00:20:24,810
Nos, ez bizonyára hasznos
belsejében egy számítógép.

463
00:20:24,810 --> 00:20:29,050
Tehát operációs rendszerek egyértelműen ezt
milyen adatszerkezetet stack.

464
00:20:29,050 --> 00:20:32,800
Azt is látni ugyanezt a gondolatot
amikor a weboldalakat.

465
00:20:32,800 --> 00:20:35,890
Így ezen a héten és a jövő héten, és azon túl,
és ahogy végrehajtásának megkezdése web

466
00:20:35,890 --> 00:20:39,490
oldalakat egy nyelv nevű HTML, akkor
ténylegesen használni egy adat struktúra, mint

467
00:20:39,490 --> 00:20:42,690
ez határozza meg, hogy ha az oldal
helyesen formázott.

468
00:20:42,690 --> 00:20:47,170
Mivel fogod az összes internetes oldalak követik
egyfajta hierarchia, egy bemélyedés

469
00:20:47,170 --> 00:20:52,030
lehet, amely a végén a nap, hogy egy
fa struktúra a motorháztető alatt.

470
00:20:52,030 --> 00:20:53,620
Így még az, hogy csak egy kicsit.

471
00:20:53,620 --> 00:20:56,560
>> De most nézzük javasolni
pillanat, hogyan megyünk a

472
00:20:56,560 --> 00:20:58,830
ami mi a verem?

473
00:20:58,830 --> 00:21:03,370
Hadd javaslom, hogy végre
a verem a kódot, mint ez.

474
00:21:03,370 --> 00:21:07,990
Tehát egy köteg megy, hogy belsejébe
két dolog, egy sor, az úgynevezett tálcák,

475
00:21:07,990 --> 00:21:09,510
csak hogy összhangban van a demo.

476
00:21:09,510 --> 00:21:12,660
És az egyes elemek, hogy a tömbben
lesz a típus int.

477
00:21:12,660 --> 00:21:14,740
És kapacitás feltehetőleg mi?

478
00:21:14,740 --> 00:21:18,796
Mert én nem írtam a
teljes definíció.

479
00:21:18,796 --> 00:21:21,535
>> Ez talán a legnagyobb
a tömb méretét.

480
00:21:21,535 --> 00:21:25,150
És ez valószínűleg nyilvánított éles
meghatározzák a tetején a fájl, néhány

481
00:21:25,150 --> 00:21:28,450
fajta állandó viszonyokat
a puszta nagybetűs.

482
00:21:28,450 --> 00:21:32,250
Tehát valahol kapacitás meghatározása
mivel a lehető legnagyobb méretet.

483
00:21:32,250 --> 00:21:35,590
Eközben belsejében az adatstruktúra
néven egy halom nem lesz

484
00:21:35,590 --> 00:21:38,630
egész szám lehet, csak ismert
egyszerűen a méret.

485
00:21:38,630 --> 00:21:43,400
>> Tehát, ha én, hogy képviselje ezt most
képszerűen, tegyük fel, hogy ez a

486
00:21:43,400 --> 00:21:48,070
egész fekete doboz képviseli a verem.

487
00:21:48,070 --> 00:21:50,070
Belül van két változó között.

488
00:21:50,070 --> 00:21:54,780
Így fogom felhívni a
első a méret.

489
00:21:54,780 --> 00:21:57,420
És a második fogok
felhívni tömbként.

490
00:21:57,420 --> 00:22:01,060
>> De csak, hogy a dolgok rendben,
általában szeretném felhívni egy tömb, mint a

491
00:22:01,060 --> 00:22:04,910
, de ez a fajta szép
ha egyezik valóság, vagy

492
00:22:04,910 --> 00:22:06,230
egyezik a mentális modell.

493
00:22:06,230 --> 00:22:12,880
Hadd inkább felhívni a tömb
függőlegesen, ami csak ismét

494
00:22:12,880 --> 00:22:13,840
művész előadásában.

495
00:22:13,840 --> 00:22:16,610
Nem igazán számít, hogy mit
van a motorháztető alatt.

496
00:22:16,610 --> 00:22:20,350
És azt mondom, hogy az alapértelmezés szerint,
kapacitás lesz három.

497
00:22:20,350 --> 00:22:23,480
Szóval ez lesz a 0 helyen, a
lesz hely 1, ez

498
00:22:23,480 --> 00:22:25,740
lesz hely 2.

499
00:22:25,740 --> 00:22:29,330
>> Ha megvesztegetni egy stressz labdát, lenne
valaki szeretné, hogy jöjjön fel, és futtassa a

500
00:22:29,330 --> 00:22:30,870
fórumon itt egy pillanatra?

501
00:22:30,870 --> 00:22:31,960
OK, láttam a kezét először.

502
00:22:31,960 --> 00:22:33,950
Gyere fel.

503
00:22:33,950 --> 00:22:36,500
Rendben van.

504
00:22:36,500 --> 00:22:38,760
Tehát azt hiszem, hogy Steven.

505
00:22:38,760 --> 00:22:40,035
Gyere fel.

506
00:22:40,035 --> 00:22:40,770
Rendben van.

507
00:22:40,770 --> 00:22:46,760
>> De tegyük most hátra a kezdeti
állam a világon, ahol azt

508
00:22:46,760 --> 00:22:52,180
éppen bejelentették a verem, és ez
lesz a kapacitás három.

509
00:22:52,180 --> 00:22:54,470
De a méret még nem határozták meg.

510
00:22:54,470 --> 00:22:56,100
Tálcák még nem határozták meg.

511
00:22:56,100 --> 00:22:57,300
Így egy-két kérdést.

512
00:22:57,300 --> 00:23:01,310
És hadd adjak mic így Ön
aktívabban részt venni ebben.

513
00:23:01,310 --> 00:23:05,190
>> Tehát mi van belül a méret ebben a pillanatban
az időben, ha minden, amit tett,

514
00:23:05,190 --> 00:23:09,340
kijelentette, a verem
egy sort?

515
00:23:09,340 --> 00:23:10,100
>> Steven: Nem sok.

516
00:23:10,100 --> 00:23:12,080
>> DAVID MALAN: OK, nem sok.

517
00:23:12,080 --> 00:23:14,410
Nem tudjuk, hogy mi van benne a méret,
tudjuk, hogy mi van benne

518
00:23:14,410 --> 00:23:16,330
Ennek a tömbnek itt?

519
00:23:16,330 --> 00:23:18,630
>> Steven: csak véletlenszerű kódot, igaz?

520
00:23:18,630 --> 00:23:20,220
Just -

521
00:23:20,220 --> 00:23:23,230
>> DAVID MALAN: Igen, megyek
hívják kód, de a véletlen -

522
00:23:23,230 --> 00:23:23,820
>> Steven: A dolgok.

523
00:23:23,820 --> 00:23:28,290
>> DAVID MALAN: Dolgok, mint véletlen

524
00:23:28,290 --> 00:23:28,870
>> Steven: Bit.

525
00:23:28,870 --> 00:23:29,530
>> DAVID MALAN: Bit, igaz?

526
00:23:29,530 --> 00:23:31,190
Tehát szemét értékek, nem igaz?

527
00:23:31,190 --> 00:23:33,470
Így permutációk 0-t és 1-es.

528
00:23:33,470 --> 00:23:35,920
Maradványai a korábbi használat
az a memória.

529
00:23:35,920 --> 00:23:38,150
És nem igazán tudom, mi az értékeket
vannak, ezért általában felhívni őket

530
00:23:38,150 --> 00:23:38,930
mint kérdőjelek.

531
00:23:38,930 --> 00:23:41,990
>> Tehát az első dolog, amit még valószínűleg
szeretne majd csinálni itt -

532
00:23:41,990 --> 00:23:46,630
és hadd ezen a területen belül
onnan a név - tálcákat.

533
00:23:46,630 --> 00:23:49,540
Mit kellene feltehetően inicializálása
mérete, ha azt akarjuk, hogy

534
00:23:49,540 --> 00:23:51,040
elkezdené alkalmazni ezt a stack?

535
00:23:51,040 --> 00:23:53,070
>> Steven: Tray sub 3.

536
00:23:53,070 --> 00:23:53,910
>> DAVID MALAN: Szóval, OK.

537
00:23:53,910 --> 00:23:56,710
Ahhoz, hogy tiszta, kapacitás nyilvánítják
máshol három.

538
00:23:56,710 --> 00:23:58,570
És ez az, amit én is használtam
kiosztani a tömb.

539
00:23:58,570 --> 00:24:03,535
Méret fog hivatkozni, hogy hány
tálcák jelenleg a verem.

540
00:24:03,535 --> 00:24:03,880
>> Steven: Zero.

541
00:24:03,880 --> 00:24:04,460
>> DAVID MALAN: Így kell nulla.

542
00:24:04,460 --> 00:24:07,760
Így megy előre, és minden ujját,
rajzoljon egy nulla méretű.

543
00:24:07,760 --> 00:24:08,440
Rendben van.

544
00:24:08,440 --> 00:24:10,920
Akkor most, mi van ennek a
itt, nem tudjuk.

545
00:24:10,920 --> 00:24:12,160
Ezek tényleg csak szemetet értékeket.

546
00:24:12,160 --> 00:24:14,800
Így lehet rajzolni kérdőjelek, de
maradjunk a tábla tiszta már

547
00:24:14,800 --> 00:24:16,300
mert nem számít
mi van ott.

548
00:24:16,300 --> 00:24:19,130
Nem kell, hogy inicializálja a tömböt
semmit, mert ha tudjuk, hogy

549
00:24:19,130 --> 00:24:23,100
a méret a verem nulla, nos,
nem nézett semmit

550
00:24:23,100 --> 00:24:25,590
ez egyébként a tömb
Ezen a ponton az időben.

551
00:24:25,590 --> 00:24:29,970
>> Ezért most tételezzük fel, hogy nyomja meg a
9-es szám a verembe.

552
00:24:29,970 --> 00:24:33,750
Hogyan kellene frissíteni az adatstruktúra
belül a fekete doboz?

553
00:24:33,750 --> 00:24:35,540
Milyen értékeket kell változtatni?

554
00:24:35,540 --> 00:24:36,200
>> Steven: Within -

555
00:24:36,200 --> 00:24:37,400
a méret?

556
00:24:37,400 --> 00:24:37,650
>> DAVID MALAN: OK.

557
00:24:37,650 --> 00:24:38,770
Méret váljon, mi?

558
00:24:38,770 --> 00:24:39,580
>> Steven: Méret lenne az egyik.

559
00:24:39,580 --> 00:24:39,870
>> DAVID MALAN: OK.

560
00:24:39,870 --> 00:24:41,110
Így a méret kell, hogy legyen.

561
00:24:41,110 --> 00:24:42,540
Így ezt egy pár módon.

562
00:24:42,540 --> 00:24:46,920
Hadd adjak, most a
ujj egy radír.

563
00:24:46,920 --> 00:24:47,260
Rendben van.

564
00:24:47,260 --> 00:24:49,960
, Akkor most az ujját egy ecsettel.

565
00:24:49,960 --> 00:24:50,330
Rendben van.

566
00:24:50,330 --> 00:24:52,820
És most mit kell változtatni,
Nyilvánvaló, hogy az adatstruktúra?

567
00:24:52,820 --> 00:24:57,060
>> Steven: megyünk a
alulról felfelé 9-ig.

568
00:24:57,060 --> 00:24:57,760
>> DAVID MALAN: 9.

569
00:24:57,760 --> 00:24:58,420
OK, jó.

570
00:24:58,420 --> 00:25:01,550
Tehát még mindig nem számít, mi a
helyen, egy-két, mert ők

571
00:25:01,550 --> 00:25:04,520
szemét értékeket, de ne zavarja
keres ott, mert mérete

572
00:25:04,520 --> 00:25:07,540
azt mondja, hogy csak az első elem
valóban jogos.

573
00:25:07,540 --> 00:25:10,400
Szóval most nyomja rá a 17 listán.

574
00:25:10,400 --> 00:25:11,830
Mi történik ezen a képen?

575
00:25:11,830 --> 00:25:14,720
>> Steven: Szóval méretet fog menni a kettő.

576
00:25:14,720 --> 00:25:15,300
>> DAVID MALAN: OK.

577
00:25:15,300 --> 00:25:16,070
Te radír -

578
00:25:16,070 --> 00:25:16,810
hoppá.

579
00:25:16,810 --> 00:25:18,026
Te egy radír.

580
00:25:18,026 --> 00:25:18,840
>> Steven: radír.

581
00:25:18,840 --> 00:25:19,720
>> DAVID MALAN: Te egy ecsettel.

582
00:25:19,720 --> 00:25:20,560
>> Steven: Brush.

583
00:25:20,560 --> 00:25:20,920
>> DAVID MALAN: OK.

584
00:25:20,920 --> 00:25:21,600
És még?

585
00:25:21,600 --> 00:25:22,600
>> Steven: És akkor mi -

586
00:25:22,600 --> 00:25:22,915
>> DAVID MALAN: szorgalmaztuk 17.

587
00:25:22,915 --> 00:25:24,760
>> Steven: Kitartunk 17 a tetején, így -

588
00:25:24,760 --> 00:25:25,710
>> DAVID MALAN: OK, jó.

589
00:25:25,710 --> 00:25:27,040
>> Steven: - ejtse le.

590
00:25:27,040 --> 00:25:27,530
>> DAVID MALAN: Rendben.

591
00:25:27,530 --> 00:25:27,940
Egyre egyszerű.

592
00:25:27,940 --> 00:25:29,300
Nem fogok segíteni ebben az időben.

593
00:25:29,300 --> 00:25:30,510
Nyomja 22..

594
00:25:30,510 --> 00:25:31,720
>> Steven: Kész.

595
00:25:31,720 --> 00:25:34,870
Válás radír.

596
00:25:34,870 --> 00:25:37,340
Kezdek egy ecsettel.

597
00:25:37,340 --> 00:25:39,340
És akkor én üzembe 22.

598
00:25:39,340 --> 00:25:40,100
>> DAVID MALAN: 22.

599
00:25:40,100 --> 00:25:40,620
Kiváló.

600
00:25:40,620 --> 00:25:41,380
Tehát még egyszer.

601
00:25:41,380 --> 00:25:44,280
Én most megy, hogy álljon
a verembe 26.

602
00:25:44,280 --> 00:25:46,350
>> Steven: Ó.

603
00:25:46,350 --> 00:25:50,278
Ó istenem.

604
00:25:50,278 --> 00:25:52,520
Tényleg elkapott ki őr.

605
00:25:52,520 --> 00:25:53,703
>> DAVID MALAN: Ön nem
látni a jövő?

606
00:25:53,703 --> 00:25:55,930
>> Steven: Nem láttam a jövő.

607
00:25:55,930 --> 00:25:58,756
Tudnánk újra kezdeti kapacitása?

608
00:25:58,756 --> 00:25:59,790
>> DAVID MALAN: Ez egy jó kérdés.

609
00:25:59,790 --> 00:26:02,360
Így már egyfajta festett magunkat
a sarokban itt.

610
00:26:02,360 --> 00:26:06,740
Tényleg nem jó ki Steven
mert már kiosztott a tömb

611
00:26:06,740 --> 00:26:09,130
statikusan, hogy úgy mondjam, belülről
az adatszerkezetet.

612
00:26:09,130 --> 00:26:12,170
És most már lényegében kemény kódolt
azt, hogy a méret három.

613
00:26:12,170 --> 00:26:14,170
Tehát nem igazán újraelosztása azt.

614
00:26:14,170 --> 00:26:20,020
>> Tudtuk, ha mentünk vissza, azt
újra tálcák, hogy egy mutató, amely

615
00:26:20,020 --> 00:26:22,300
mi majd malloc kéznél memória.

616
00:26:22,300 --> 00:26:25,050
Mert ha megvan a memóriát
a kupac keresztül malloc, mi

617
00:26:25,050 --> 00:26:26,430
aztán kiszabadítani.

618
00:26:26,430 --> 00:26:29,630
De mielőtt felszabadítása, mi lehetett
átcsoportosítása egy nagyobb darab memória,

619
00:26:29,630 --> 00:26:31,330
frissíti a mutatót, és így tovább.

620
00:26:31,330 --> 00:26:33,500
De most, ez nagyon
A legjobb, amit tehetünk.

621
00:26:33,500 --> 00:26:36,360
Push és Pop feltehetőleg lesz
hogy a jel valamilyen hiba.

622
00:26:36,360 --> 00:26:40,270
>> Így például, a végrehajtás
push visszatérhet a bool, amely

623
00:26:40,270 --> 00:26:42,390
korábban tért vissza igaz, igaz, igaz.

624
00:26:42,390 --> 00:26:48,390
De a negyedik alkalom, hogy megy, hogy
hogy visszatérjen hamis, például.

625
00:26:48,390 --> 00:26:48,540
Rendben van.

626
00:26:48,540 --> 00:26:49,540
Nagyon jól sikerült.

627
00:26:49,540 --> 00:26:50,060
Gratulálok.

628
00:26:50,060 --> 00:26:52,160
Megérdemled a stressz labdát ma.

629
00:26:52,160 --> 00:26:53,110
>> [Taps]

630
00:26:53,110 --> 00:26:54,382
>> Steven: Köszönöm.

631
00:26:54,382 --> 00:26:55,680
>> DAVID MALAN: Köszönöm.

632
00:26:55,680 --> 00:26:59,740
OK, így ez úgy tűnik, hogy nem sok
Egy lépés előre, nem igaz?

633
00:26:59,740 --> 00:27:01,410
Leírtuk az adatok szerkezetét.

634
00:27:01,410 --> 00:27:02,320
Ez volt meggyőző, nem?

635
00:27:02,320 --> 00:27:03,200
Operációs rendszerek tetszik.

636
00:27:03,200 --> 00:27:06,360
Úgy látszik, a web is, hogy ezzel,
és más alkalmazásokat is.

637
00:27:06,360 --> 00:27:10,870
De milyen hülye korlátozás, hogy nem vagyunk
vissza a fajta a hét két határérték

638
00:27:10,870 --> 00:27:12,880
ahol már fix méretű tömbök.

639
00:27:12,880 --> 00:27:15,010
>> Tehát valóban egy pár
hogyan tudnánk megoldani ezt.

640
00:27:15,010 --> 00:27:18,750
Tudtuk dinamikusan osztja a tömb,
nem nehéz kódolás, mint én már

641
00:27:18,750 --> 00:27:22,600
itt történik, hanem újra kijelentette
ez, csak hogy világos legyen, mint

642
00:27:22,600 --> 00:27:23,830
valami ilyesmi.

643
00:27:23,830 --> 00:27:29,040
Int * tálcák, nem döntő
a kapacitás még.

644
00:27:29,040 --> 00:27:35,460
De amikor állapítsa meg a stack máshol
az én kódot, tudtam akkor hívja malloc,

645
00:27:35,460 --> 00:27:38,250
kap a címét egy darab
memória, és én hozzá

646
00:27:38,250 --> 00:27:39,980
a címet a tálcákat.

647
00:27:39,980 --> 00:27:43,340
>> Aztán, mivel ez csak egy darab
memória, nem tudtam tovább használni tér

648
00:27:43,340 --> 00:27:45,450
konzol jelölést a szokásos módon.

649
00:27:45,450 --> 00:27:49,020
Mert megint van valami a
funkcionális megfelelője tömbök és

650
00:27:49,020 --> 00:27:50,820
darabokban a memóriát, hogy jön
vissza malloc.

651
00:27:50,820 --> 00:27:53,090
Tudjuk kezelni az egyik, mint a másik
a mutató számtani vagy

652
00:27:53,090 --> 00:27:54,440
szögletes zárójel jelölést.

653
00:27:54,440 --> 00:27:55,660
Tehát ez az egyik megközelítés.

654
00:27:55,660 --> 00:28:00,120
>> De hogyan lehet, hogy más is alkalmazzák ezt a
azonos adatstruktúra, esetleg?

655
00:28:00,120 --> 00:28:00,280
Nem igaz?

656
00:28:00,280 --> 00:28:04,530
Úgy érzem, mi csak megoldotta ezt a
probléma, mint egy héttel ezelőtt.

657
00:28:04,530 --> 00:28:08,860
Mi volt a megoldás erre a problémára
hogy Steven ütközött?

658
00:28:08,860 --> 00:28:10,370
Tehát láncolt listák, igaz.

659
00:28:10,370 --> 00:28:13,410
>> Ha a probléma az, hogy mi vagyunk festés
magunkat szögletre elosztása

660
00:28:13,410 --> 00:28:17,580
előre túl kevés a memória, hogy
akkor meg kell valahogy kezelni, nos,

661
00:28:17,580 --> 00:28:19,880
miért nem csak elkerülni, hogy
ki összesen?

662
00:28:19,880 --> 00:28:26,170
Miért nem csak kijelentik tálcák lenni
mutató egy csomópont, ergo a láncolt lista,

663
00:28:26,170 --> 00:28:30,740
majd egyszerűen osztja új csomópontok
minden alkalommal Steven szükséges, hogy illeszkedjen a

664
00:28:30,740 --> 00:28:32,400
számot az adatszerkezetet.

665
00:28:32,400 --> 00:28:34,200
>> Így a kép meg kell változtatni.

666
00:28:34,200 --> 00:28:38,220
Ez nem lesz olyan tiszta és
egyszerű, mint most egy sor három ints.

667
00:28:38,220 --> 00:28:42,970
Most lesz egy mutató a
struct, és hogy a struktúra fog

668
00:28:42,970 --> 00:28:44,830
egy int, és a következő mutató.

669
00:28:44,830 --> 00:28:47,670
Meg fog vezetni, hogy a mutató segítségével
másik ilyen struktúra a

670
00:28:47,670 --> 00:28:48,600
egy ilyen struktúra.

671
00:28:48,600 --> 00:28:50,560
Így a kép valójában
egy kicsit Messier-.

672
00:28:50,560 --> 00:28:52,950
És mi volna nyilak árukapcsolás
mindent együtt.

673
00:28:52,950 --> 00:28:55,280
>> De ez rendben van, igaz, mert a
láttunk, hogyan kell ezt csinálni.

674
00:28:55,280 --> 00:28:58,180
És ha egyszer kap kényelmes
végrehajtása olyasmi, mint egy kapcsolt

675
00:28:58,180 --> 00:29:01,450
lista, amit meg kell tennie, ha
úgy dönt, hogy végre egy hash tábla

676
00:29:01,450 --> 00:29:05,120
külön láncolás a p-set 6, akkor
használni, mint egy építőköve, vagy

677
00:29:05,120 --> 00:29:08,870
összetevő vagy Scratch beszélni, a
eljárás, amit teszel, akkor

678
00:29:08,870 --> 00:29:12,560
létrehozta a saját puzzle-darab
, amit aztán újra.

679
00:29:12,560 --> 00:29:17,090
Tehát kompromisszumok, de a lehetséges megoldásokat
hogy már tényleg látott.

680
00:29:17,090 --> 00:29:20,560
>> Így elég gyakran, látod ezt minden
két évvel, amikor az Apple kiadások

681
00:29:20,560 --> 00:29:23,060
valami új, és az egész őrültek
sorakoznak kívül az Apple

682
00:29:23,060 --> 00:29:27,050
boltba vásárolni marginális
frissíteni a hardver.

683
00:29:27,050 --> 00:29:30,420
Ezt mondom, hogy rendben van, mert a
Én egyike vagyok azoknak az embereknek.

684
00:29:30,420 --> 00:29:35,140
Szóval milyen adatstruktúra
jelenthet ez a valóság?

685
00:29:35,140 --> 00:29:36,980
>> Nos, ez egy sor, egy sor.

686
00:29:36,980 --> 00:29:40,270
Így a brit nevezném általában a
sor, úgyhogy ez egy szép név.

687
00:29:40,270 --> 00:29:44,960
És a két művelet, hogy a sor
támogatja hívjuk a Enqueue

688
00:29:44,960 --> 00:29:48,900
működés és a dequeue működés,
amelyek hasonló

689
00:29:48,900 --> 00:29:50,120
szellem push és pop.

690
00:29:50,120 --> 00:29:54,060
Ez csak valami különböző
egyezmény, amit mi meghívjuk ezeket.

691
00:29:54,060 --> 00:29:57,680
De sorba állítását valamit azt, hogy adjunk
vagy helyezze azt az adatszerkezetet.

692
00:29:57,680 --> 00:29:59,570
A dequeue jelenti, hogy távolítsa el azt.

693
00:29:59,570 --> 00:30:05,170
De míg a verem egy LIFO adat
szerkezet, a sorban az első az,

694
00:30:05,170 --> 00:30:06,740
first out adatstruktúra.

695
00:30:06,740 --> 00:30:10,050
>> Ha te vagy az első, aki a sorban,
lesz az első, aki kap

696
00:30:10,050 --> 00:30:12,420
a sorból, és vásárolni az új eszközt.

697
00:30:12,420 --> 00:30:18,070
Képzeld el, hogy ezek az emberek ideges lenne
ha az Apple helyett használt verem, a

698
00:30:18,070 --> 00:30:21,250
Például, hogy hajtsák végre a szedés
fel az új játék.

699
00:30:21,250 --> 00:30:24,310
Tehát sorok értelme, természetesen, és
el tudunk képzelni mindenféle

700
00:30:24,310 --> 00:30:27,480
alkalmazások, feltehetően, a sorok,
különösen, ha azt szeretné, méltányosság.

701
00:30:27,480 --> 00:30:30,040
Szóval, hogyan lehet, hogy mi végre ezeket
mint egy adatstruktúra?

702
00:30:30,040 --> 00:30:33,680
>> Nos, azt javaslom, hogy mi is
kell csinálni így.

703
00:30:33,680 --> 00:30:35,225
Így fogok most számokat.

704
00:30:35,225 --> 00:30:38,190
Szóval majd tartsa egyszerű, és nem
feltétlenül beszélünk szempontjából tálcák.

705
00:30:38,190 --> 00:30:40,220
Csak számok, hogy az emberek az ütött.

706
00:30:40,220 --> 00:30:43,760
Kapacitás fog ismét rögzítse a
száma az embereknek, hogy lehet

707
00:30:43,760 --> 00:30:46,900
Ezen a vonalon három-
bármilyen más értéket.

708
00:30:46,900 --> 00:30:50,760
>> De azt javaslom, hogy el kell követni
nem csak a méret a

709
00:30:50,760 --> 00:30:52,370
sor, hogy sok dolog benne.

710
00:30:52,370 --> 00:30:56,310
Így a méret a jelenlegi méret, kapacitás
a legnagyobb méret.

711
00:30:56,310 --> 00:30:58,540
Csak újra nómenklatúra
megállapodás szerint.

712
00:30:58,540 --> 00:31:03,680
Miért kell egy újabb int belső
Egy sor nyomon követni, hogy ki van

713
00:31:03,680 --> 00:31:05,365
első a sorban?

714
00:31:05,365 --> 00:31:07,930

715
00:31:07,930 --> 00:31:10,910
Miért kell tennem, hogy ebben az esetben?

716
00:31:10,910 --> 00:31:14,750

717
00:31:14,750 --> 00:31:16,190
>> Nos, hogy ez a kép
fog változni?

718
00:31:16,190 --> 00:31:19,280
Én talán újra a legtöbb
ezt a képet.

719
00:31:19,280 --> 00:31:21,480
Hadd menjek előre, és törli, mi van itt.

720
00:31:21,480 --> 00:31:24,580
Majd ad ez egy kicsit
más néven itt.

721
00:31:24,580 --> 00:31:28,930
Menjünk megszabadulni a 17, menjünk megszabadulni
A 9, menjünk megszabadulni a 3.

722
00:31:28,930 --> 00:31:30,410
És tegyük hozzá még valami.

723
00:31:30,410 --> 00:31:34,710
Azt javaslom, hogy el kell nyomon követni
az első a listán, ami csak

724
00:31:34,710 --> 00:31:35,570
lesz egy int is.

725
00:31:35,570 --> 00:31:36,550
És fogunk tartani, hogy egyszerű.

726
00:31:36,550 --> 00:31:37,740
Nem láncolt lista most.

727
00:31:37,740 --> 00:31:40,900
>> Majd elismerem, hogy fogunk
bump ellen ezt a határt.

728
00:31:40,900 --> 00:31:43,720
De mit akarok látni,
történni ebben az időben?

729
00:31:43,720 --> 00:31:47,240
Tegyük fel, hogy megyek előre, és az első
ember jön a sorban, és a

730
00:31:47,240 --> 00:31:48,560
ez a 9-es számú.

731
00:31:48,560 --> 00:31:49,680
Mi a stressz labda.

732
00:31:49,680 --> 00:31:51,330
Lehet lopni, mondjuk, két vagy három ember?

733
00:31:51,330 --> 00:31:52,690
Egy, kettő, három?

734
00:31:52,690 --> 00:31:53,120
Gyere fel.

735
00:31:53,120 --> 00:31:56,022
Már az első, mert a
fogjuk, hogy ez egy gyors.

736
00:31:56,022 --> 00:31:59,415
>> Mindannyian most lesz
egy rajongó fiú sort Apple.

737
00:31:59,415 --> 00:32:03,970

738
00:32:03,970 --> 00:32:06,210
Akkor nem kap az Apple hardver
a végén ez mégis.

739
00:32:06,210 --> 00:32:06,500
Rendben van.

740
00:32:06,500 --> 00:32:09,430
Szóval 9-es számú, akkor
17-es szám, 22-es számú.

741
00:32:09,430 --> 00:32:12,130
Ezek tetszőleges számok, mint a
diák azonosítók vagy miegymás.

742
00:32:12,130 --> 00:32:14,550
És csak egy pillanatra, kezdjük
elkezd hozzá dolgokat.

743
00:32:14,550 --> 00:32:16,000
És én futni a fórumon itt ebben az időben.

744
00:32:16,000 --> 00:32:19,570
>> Tehát ebben az esetben, már inicializált
Az első, hogy -

745
00:32:19,570 --> 00:32:22,380
Igazából nem igazán érdekel, mi a
elöl van, mert a mérete nulla.

746
00:32:22,380 --> 00:32:24,480
Szóval ez lehet, hogy csak
egy kérdőjel.

747
00:32:24,480 --> 00:32:26,170
Ezek mind kérdőjelek.

748
00:32:26,170 --> 00:32:29,880
Tehát most elkezdjük, hogy valóban látni néhány
emberek sorakoznak a boltban.

749
00:32:29,880 --> 00:32:33,320
>> Tehát, ha a 9., te vagy az első
ott 5:00, megy előre, és sorban,

750
00:32:33,320 --> 00:32:34,210
vagy este.

751
00:32:34,210 --> 00:32:34,580
OK.

752
00:32:34,580 --> 00:32:35,940
Tehát most 9 itt.

753
00:32:35,940 --> 00:32:37,940
Tehát 9-ben az első a listán.

754
00:32:37,940 --> 00:32:41,440
Szóval megyek előre, és frissíti
mérete az aktuális adatok

755
00:32:41,440 --> 00:32:44,740
szerkezet már nem lehet 0,
hanem, hogy 1.

756
00:32:44,740 --> 00:32:47,630
Megyek, hogy 9-én a
előtt a listából.

757
00:32:47,630 --> 00:32:51,020
Hadd menjek előre, és váltani a képernyő
így láthatjuk múlt minket.

758
00:32:51,020 --> 00:32:53,220
>> És most mit akarok
, hogy elöl?

759
00:32:53,220 --> 00:32:56,240
Fogom nyomon követni, hogy a
első a sorban most

760
00:32:56,240 --> 00:32:58,570
a 0 helyen.

761
00:32:58,570 --> 00:33:00,510
Mert ami mellett fog történni?

762
00:33:00,510 --> 00:33:03,000
Nos, tegyük fel, most sorba állítását
17 is.

763
00:33:03,000 --> 00:33:04,510
Így hop sorban van.

764
00:33:04,510 --> 00:33:07,060
És ismét, a fajta ajtót, hogy a
üzlet lesz itt.

765
00:33:07,060 --> 00:33:08,700
Tehát most adtam 17.

766
00:33:08,700 --> 00:33:10,810
És bár ezek a srácok blokkolja
a képernyőn, ez rendben van,

767
00:33:10,810 --> 00:33:12,300
mert látjuk, hogy itt.

768
00:33:12,300 --> 00:33:12,910
Bocsánat.

769
00:33:12,910 --> 00:33:13,810
>> Közönség: tudunk mozogni -

770
00:33:13,810 --> 00:33:14,660
>> DAVID MALAN: Nem, ez rendben van.

771
00:33:14,660 --> 00:33:16,000
Hatalmas ott.

772
00:33:16,000 --> 00:33:18,580
Tehát 17 most belül a sorban.

773
00:33:18,580 --> 00:33:21,332
Meg kell frissíteni, amely
mezők most mégis?

774
00:33:21,332 --> 00:33:23,210
OK, határozottan méret.

775
00:33:23,210 --> 00:33:26,430
És mi van elöl?

776
00:33:26,430 --> 00:33:27,040
OK, nem.

777
00:33:27,040 --> 00:33:30,200
Front nem kell változtatni, mert a
ellentétben a verem, akkor

778
00:33:30,200 --> 00:33:31,370
szeretné, hogy a méltányosság.

779
00:33:31,370 --> 00:33:35,150
Tehát, ha 9 jött először, azt akarjuk, 9
, hogy az első a sorból

780
00:33:35,150 --> 00:33:36,420
és a boltba.

781
00:33:36,420 --> 00:33:37,220
>> Valójában, lássuk ezt.

782
00:33:37,220 --> 00:33:42,235
Mielőtt be 22, nézzük
megy előre, és dequeue 9.

783
00:33:42,235 --> 00:33:42,970
Mi a neved?

784
00:33:42,970 --> 00:33:43,680
>> Közönség: Jake.

785
00:33:43,680 --> 00:33:45,440
>> DAVID MALAN: Jake megy
hogy dequeued most.

786
00:33:45,440 --> 00:33:48,050
Így kap járni a boltba.

787
00:33:48,050 --> 00:33:49,880
És úgy, mintha a boltban
ott van.

788
00:33:49,880 --> 00:33:51,970
Akkor most mit kell - DIT-dit-dit!

789
00:33:51,970 --> 00:33:53,400
Mit kell most történni?

790
00:33:53,400 --> 00:33:54,490
Tervezési döntés.

791
00:33:54,490 --> 00:33:56,825
Tehát nem egy rossz ösztön, de -
mi is a neved?

792
00:33:56,825 --> 00:33:57,090
>> Közönség: David.

793
00:33:57,090 --> 00:33:57,500
>> DAVID MALAN: David.

794
00:33:57,500 --> 00:33:58,810
Szóval, mit tett Dávid?

795
00:33:58,810 --> 00:34:02,590
Megpróbálta rendezni az adatok rögzítése
struktúra és áttérés a helyzetét

796
00:34:02,590 --> 00:34:04,100
Jake a korábbi helyen.

797
00:34:04,100 --> 00:34:06,740
És ez rendben van, ha hajlandóak vagyunk
elfogadja, hogy, mint egy

798
00:34:06,740 --> 00:34:08,199
végrehajtás részletesen.

799
00:34:08,199 --> 00:34:11,100
De először nézzük frissíti az adatokat
szerkezet mielőtt csinálni.

800
00:34:11,100 --> 00:34:14,139
Mert nem tetszik az ötlet minden
az emberek változó ebben a sorban.

801
00:34:14,139 --> 00:34:17,360
>> Ez nem nagy ügy, ha David csinálja
egy lépés, de a lényeg, szerintem vissza

802
00:34:17,360 --> 00:34:20,360
amikor már nyolc önkéntesek a
színpad és tettünk, mint az elhelyezési

803
00:34:20,360 --> 00:34:22,600
sort, ahol meg kellett kezdeni
mozog mindenki körül.

804
00:34:22,600 --> 00:34:23,790
Hogy van drága, ugye?

805
00:34:23,790 --> 00:34:28,330
Ez tesz engem szervilizmus a nagy O
n, nagy O n négyzeten újra.

806
00:34:28,330 --> 00:34:30,650
Ez nem érzi, mint
az ideális eredményt.

807
00:34:30,650 --> 00:34:32,080
>> Szóval csak frissíteni ezt.

808
00:34:32,080 --> 00:34:35,120
Tehát a méret a sorban
2. már nem.

809
00:34:35,120 --> 00:34:37,090
Ez most csak 1.

810
00:34:37,090 --> 00:34:40,360
De most már frissíteni valamit
Én nem frissíti korábban, a

811
00:34:40,360 --> 00:34:41,130
előtt a listából.

812
00:34:41,130 --> 00:34:45,420
Én is csak azt mondom, hogy a hely 1?

813
00:34:45,420 --> 00:34:49,770
Tehát most már szemét érték itt,
szemét érték itt, és David a

814
00:34:49,770 --> 00:34:51,469
közepén a szemetet.

815
00:34:51,469 --> 00:34:54,980
De az adatstruktúra
még mindig érintetlen.

816
00:34:54,980 --> 00:34:58,540
>> És valóban, nem is kell
változás Jake korábbi számát

817
00:34:58,540 --> 00:35:00,460
9, mert kit érdekel.

818
00:35:00,460 --> 00:35:04,470
Van elég információt most a
méret, Tudom, hogy van egy ember

819
00:35:04,470 --> 00:35:05,030
ez a sor.

820
00:35:05,030 --> 00:35:08,340
És tudom, hogy ez a személy
van hely 1, nem 0-ra.

821
00:35:08,340 --> 00:35:09,760
Én nem számítva.

822
00:35:09,760 --> 00:35:11,300
Tehát 1 is.

823
00:35:11,300 --> 00:35:13,410
Így az adatok szerkezete még mindig rendben van.

824
00:35:13,410 --> 00:35:14,330
>> Nos, mi történik ezután?

825
00:35:14,330 --> 00:35:15,010
Nézzük Enqueue -

826
00:35:15,010 --> 00:35:15,370
mi a neve?

827
00:35:15,370 --> 00:35:16,160
>> Közönség: Callen.

828
00:35:16,160 --> 00:35:16,580
>> DAVID MALAN: Callen.

829
00:35:16,580 --> 00:35:20,770
Nézzük sorba állításához Callen és
22 már a sorban.

830
00:35:20,770 --> 00:35:22,300
Akkor most mi kell változtatni itt?

831
00:35:22,300 --> 00:35:24,380
Front nem fog
változtatni, természetesen.

832
00:35:24,380 --> 00:35:27,160
Méret fog változni, hogy ismét a 2.

833
00:35:27,160 --> 00:35:31,590
És végül itt 22, 9 még mindig jelen van,
de ez gyakorlatilag egy

834
00:35:31,590 --> 00:35:32,600
szemét érték most.

835
00:35:32,600 --> 00:35:35,910
Ez csak egy maradványa Jake múlt.

836
00:35:35,910 --> 00:35:39,200
>> Most mi történik, ha
Én dequeue David?

837
00:35:39,200 --> 00:35:41,560
Még egy utolsó műtét, dequeue David.

838
00:35:41,560 --> 00:35:46,070
Mi is elmozdulhatnak, de azt javaslom, nézzük
csinálni, mint kis munka lehetséges.

839
00:35:46,070 --> 00:35:50,280
Most a adatstruktúra megy
vissza méretben 2-1.

840
00:35:50,280 --> 00:35:53,730
De az első a sorban
most lesz 2.

841
00:35:53,730 --> 00:35:56,640
Nem kell változtatni ezeket a számokat
most még, mert ők

842
00:35:56,640 --> 00:35:58,230
csak szemetet értékeket.

843
00:35:58,230 --> 00:35:59,720
>> De most mi történik?

844
00:35:59,720 --> 00:36:03,280
Tegyük fel, hogy sorba állítását magam, 26?

845
00:36:03,280 --> 00:36:05,890
Úgy érzem, tartozom ide.

846
00:36:05,890 --> 00:36:06,890
Szóval, hogy enqueued.

847
00:36:06,890 --> 00:36:08,760
Szóval ilyen ide tartozom.

848
00:36:08,760 --> 00:36:11,300
És annak ellenére, hogy nem egészen
értékelik ezt vizuálisan a színpadon,

849
00:36:11,300 --> 00:36:15,075
mert van bőven, nekem
nem állt itt, miért?

850
00:36:15,075 --> 00:36:16,290
>> Közönség: Te a határokat.

851
00:36:16,290 --> 00:36:16,370
>> DAVID MALAN: Így van.

852
00:36:16,370 --> 00:36:16,940
Én vagyok a határokat.

853
00:36:16,940 --> 00:36:19,330
Már indexelt túl
határai a tömb.

854
00:36:19,330 --> 00:36:23,420
Nagyon kellene az egyik
három lehetséges helyszín.

855
00:36:23,420 --> 00:36:25,150
Hol van a legtöbb természetes, hogy menjen?

856
00:36:25,150 --> 00:36:27,760
Azt javaslom, hogy hitelből
egy hét egy trükk.

857
00:36:27,760 --> 00:36:30,150
A mod operátor, százalékban.

858
00:36:30,150 --> 00:36:36,850
Mert én gyakorlatilag állt
3 helyzet, de én 3 mod kapacitás

859
00:36:36,850 --> 00:36:40,250
így 3 százalékos jel, 3 -

860
00:36:40,250 --> 00:36:40,970
teljesítmény az 3.

861
00:36:40,970 --> 00:36:41,720
Mi ez?

862
00:36:41,720 --> 00:36:43,700
Mi a maradék, ha
akkor osszuk 3 * 3?

863
00:36:43,700 --> 00:36:44,070
0-ra.

864
00:36:44,070 --> 00:36:48,140
>> Tehát, hogy hozza nekem volt Jake,
ami valóban jó.

865
00:36:48,140 --> 00:36:50,370
Tehát most a végrehajtás
ez a dolog fog

866
00:36:50,370 --> 00:36:51,250
egy kicsit a fejem.

867
00:36:51,250 --> 00:36:53,740
Ez tényleg csak egy sort
A fejfájás, a kód.

868
00:36:53,740 --> 00:36:56,580
De legalább most már szemét
érték itt, de van két

869
00:36:56,580 --> 00:36:57,910
törvényes ints itt.

870
00:36:57,910 --> 00:37:04,160
És azt állítják, hogy most már kész
pontosan mit kell tennie, amíg

871
00:37:04,160 --> 00:37:08,600
mi a változás, amit Jake
érték volt, hogy 26..

872
00:37:08,600 --> 00:37:12,110
>> Most már elég információ még
integritásának fenntartása

873
00:37:12,110 --> 00:37:13,060
Ezen adatok szerkezetét.

874
00:37:13,060 --> 00:37:17,160
Még mindig olyan jártál, amikor
szeretné szúrni négy vagy több teljes

875
00:37:17,160 --> 00:37:20,740
elemeket, de azt legalább, hogy elég
hatékony ez az állandó

876
00:37:20,740 --> 00:37:21,740
időt, sőt.

877
00:37:21,740 --> 00:37:27,150
Nem kell aggódnia, változó
mindenki, ahogy David hajlam volt.

878
00:37:27,150 --> 00:37:30,816
>> Bármilyen kérdése a halom,
vagy a sor?

879
00:37:30,816 --> 00:37:32,184
>> Közönség: az oka annak,
szükséges méretet, hogy tudd

880
00:37:32,184 --> 00:37:34,010
hol van a személy?

881
00:37:34,010 --> 00:37:34,770
>> DAVID MALAN: Pontosan.

882
00:37:34,770 --> 00:37:38,230
Tudnom kell, hogy a méret a tömb
mert kell, hogy pontosan hogyan

883
00:37:38,230 --> 00:37:41,940
sok ilyen értékek legitim,
és így, hogy találok hová tegye

884
00:37:41,940 --> 00:37:42,800
a következő személyt.

885
00:37:42,800 --> 00:37:43,300
Pontosan.

886
00:37:43,300 --> 00:37:44,580
A mérete -

887
00:37:44,580 --> 00:37:46,360
Igazából nem frissíti e még.

888
00:37:46,360 --> 00:37:48,380
Én hozzá magam a 26.

889
00:37:48,380 --> 00:37:51,760
A méret már nem 1, hanem 2.

890
00:37:51,760 --> 00:37:57,780
Tehát most ez valóban segít megtalálni a
A lista élére, ami nem 0, nem

891
00:37:57,780 --> 00:37:59,250
1, de 2 lehet.

892
00:37:59,250 --> 00:38:01,665
Az első a lista
valóban a 22.

893
00:38:01,665 --> 00:38:05,120
Mert jött először, így kell
megengedett a boltba előttem,

894
00:38:05,120 --> 00:38:08,780
bár vizuálisan állok
közelebb a boltba.

895
00:38:08,780 --> 00:38:09,220
>> Minden rendben?

896
00:38:09,220 --> 00:38:12,410
A tapsot ezek a srácok
és mi hagyjuk őket onnan.

897
00:38:12,410 --> 00:38:17,090
>> [Taps]

898
00:38:17,090 --> 00:38:18,150
>> DAVID MALAN: arra, hogy majd
tartsa a tálcát.

899
00:38:18,150 --> 00:38:20,760
Láttuk, mi történik, ha
akarsz, de lehet, hogy nem.

900
00:38:20,760 --> 00:38:21,590
Rendben van.

901
00:38:21,590 --> 00:38:25,380
És most mi marad nekünk?

902
00:38:25,380 --> 00:38:28,900
Nos, hadd javasoljuk, hogy van egy
néhány más adatszerkezeteket tudtunk

903
00:38:28,900 --> 00:38:33,810
elkezd hozzátéve, hogy a szerszámkészlet, amely
valóban elég, elég releváns

904
00:38:33,810 --> 00:38:35,270
merülünk a webes dolgokat.

905
00:38:35,270 --> 00:38:38,150
Ami megint van valamilyen kapcsolat
a fák formájában

906
00:38:38,150 --> 00:38:40,550
úgynevezett DOM, a dokumentum
objektum modell.

907
00:38:40,550 --> 00:38:42,370
De majd meglátjuk többet
hogy nemsokára.

908
00:38:42,370 --> 00:38:46,260
>> Hadd javaslom definitionally hogy
hívási fa most mi lehet ismert

909
00:38:46,260 --> 00:38:48,820
inkább egy családfát, ahol
néhány őse a

910
00:38:48,820 --> 00:38:49,790
gyökerei a fa.

911
00:38:49,790 --> 00:38:54,480
A patriarchális vagy matriarcha a
éppen a fa tetején.

912
00:38:54,480 --> 00:38:56,700
Anélkül, hogy házastársa, ebben az esetben.

913
00:38:56,700 --> 00:39:00,940
De most mit fogunk hívni
gyerekek, amelyek a csomópontok, hogy lefagy

914
00:39:00,940 --> 00:39:05,480
le a bal vagy a jobb gyermek gyermek,
nyilak ábrázolt itt.

915
00:39:05,480 --> 00:39:10,490
>> Más szóval, egy fa adatstruktúra
A számítógép, a fa nulla

916
00:39:10,490 --> 00:39:11,480
vagy több csomópont.

917
00:39:11,480 --> 00:39:13,500
Ha van legalább egy csomóponthoz,
hogy hívják a gyökér.

918
00:39:13,500 --> 00:39:15,700
Ez a dolog, hogy a vizuálisan
felhívjuk a tetején.

919
00:39:15,700 --> 00:39:20,280
És csomópont, mint minden más csomóponthoz is
nulla, egy, vagy két, vagy három,

920
00:39:20,280 --> 00:39:23,600
vagy ahogy sok gyerek a
adatstruktúra támogatja.

921
00:39:23,600 --> 00:39:29,150
Ebben az esetben, a gyökér, a tároló
értéke egy, két gyermeke van, a 2. és 3.

922
00:39:29,150 --> 00:39:33,020
így általában véve 2 a bal
gyermek-és 3 a jobb fia.

923
00:39:33,020 --> 00:39:36,940
>> És amikor most az 5., 6., és
7, 6 nevezhetnénk a középső gyerek.

924
00:39:36,940 --> 00:39:38,940
Ha a négy gyerek,
lesz zavaró.

925
00:39:38,940 --> 00:39:42,260
Tehát ne használja ezt a fajta
A parancsikon szóban.

926
00:39:42,260 --> 00:39:44,580
De ez tényleg csak egy családfát.

927
00:39:44,580 --> 00:39:48,880
És a levelek itt a csomópontok
maguk nincsenek gyerekek.

928
00:39:48,880 --> 00:39:52,540
Azt tedd le az alján a fa.

929
00:39:52,540 --> 00:39:56,940
>> Szóval, hogyan lehet, hogy mi végre egy fa,
csak két gyermek maximálisan?

930
00:39:56,940 --> 00:39:58,410
Majd ez egy bináris fa.

931
00:39:58,410 --> 00:40:00,960
Bi jelenti ismét két, ebben a
esetében, mint a bináris.

932
00:40:00,960 --> 00:40:04,830
És így ez lehet nulla, egy,
vagy két gyerek maximálisan.

933
00:40:04,830 --> 00:40:08,650
>> Én javaslom, hogy hajtsák végre a csomópont
az, hogy a struktúra egy int n,

934
00:40:08,650 --> 00:40:11,910
, majd két mutató, az egyik neve
balra, az egyik neve van.

935
00:40:11,910 --> 00:40:14,830
De ezek csak szép
önkényes egyezmények.

936
00:40:14,830 --> 00:40:18,170
És mi szép most, különösen, ha
fajta küzdött fogalmilag

937
00:40:18,170 --> 00:40:21,300
rekurzió, vagy úgy gondolta, hogy ez nem volt
tényleg megoldás semmire,

938
00:40:21,300 --> 00:40:23,120
különösen akkor, ha lehetne
elfogy a memória.

939
00:40:23,120 --> 00:40:26,600
Most, hogy beszélünk az adatok
struktúrák és algoritmusok, amelyek lehetővé teszik

940
00:40:26,600 --> 00:40:31,030
bennünket, hogy áthalad, és manipulálni őket,
Kiderül, hogy a rekurzió jön vissza

941
00:40:31,030 --> 00:40:34,240
sokkal vonzóbb
ha nem szép módon.

942
00:40:34,240 --> 00:40:38,670
>> Szóval ez azt javaslom a végrehajtása
A keresés funkcióval.

943
00:40:38,670 --> 00:40:39,870
Mivel két bemenet -

944
00:40:39,870 --> 00:40:41,570
így gondolom, hogy ez egy fekete doboz.

945
00:40:41,570 --> 00:40:46,560
Mivel két bemenet, n, int, és a
mutató egy fa, egy mutatót a

946
00:40:46,560 --> 00:40:50,020
csomópont, vagy tényleg a fa gyökerét, azt
azt állítják, hogy ez a funkció visszatérhet

947
00:40:50,020 --> 00:40:53,530
igaz vagy hamis, ezt az értéket n
belül van ez a fa.

948
00:40:53,530 --> 00:40:55,210
>> Mi van a fekete doboz?

949
00:40:55,210 --> 00:40:57,440
Nos, négy ága.

950
00:40:57,440 --> 00:40:58,385
Az első csak ellenőrzi.

951
00:40:58,385 --> 00:41:00,490
Ha a fa null, csak vissza hamis.

952
00:41:00,490 --> 00:41:04,580
Ha nincs csomópont, nincs n,
nincs több, csak vissza hamis.

953
00:41:04,580 --> 00:41:12,330
Ha mégis, n, az értéket, amit keresel
A kevesebb, mint fa nyíl n, és

954
00:41:12,330 --> 00:41:15,180
Csak hogy tisztázzuk, mit jelent, ha
Írok fát, majd a nyíl

955
00:41:15,180 --> 00:41:18,150
jelölés, n?

956
00:41:18,150 --> 00:41:18,690
Pontosan.

957
00:41:18,690 --> 00:41:21,970
Ez azt jelenti, hogy a hivatkozás feloldási
pointer nevű fa.

958
00:41:21,970 --> 00:41:26,750
Menj oda, és majd bejutni, hogy a
csomópont, és kap a területen az úgynevezett n.

959
00:41:26,750 --> 00:41:30,810
És hasonlítsa össze a tényleges n volt
átment Search ellene.

960
00:41:30,810 --> 00:41:35,390
>> Tehát, ha n kisebb, mint az n érték
A fa csomópont is, jól,

961
00:41:35,390 --> 00:41:36,720
mit jelent ez?

962
00:41:36,720 --> 00:41:40,690
Ez semmit nem jelent az első pillantásra.

963
00:41:40,690 --> 00:41:40,900
Nem igaz?

964
00:41:40,900 --> 00:41:45,560
Mint amikor van egy sor
értékeket, ami biztosan tetszeni alkalmazni bináris

965
00:41:45,560 --> 00:41:48,290
keresés egyfajta szakadék
és uralkodj.

966
00:41:48,290 --> 00:41:51,790
De mit feltételezés volt meg kell, hogy
bináris keresés működik egyáltalán

967
00:41:51,790 --> 00:41:54,510
A telefonkönyv és
korábban példa?

968
00:41:54,510 --> 00:41:55,530
>> Hogyan kell válogatni.

969
00:41:55,530 --> 00:41:59,490
Szóval finomítani meghatározása fa
Itt nem csak egy fa, amely

970
00:41:59,490 --> 00:42:00,880
bármilyen gyermekek száma.

971
00:42:00,880 --> 00:42:04,700
Nem csak egy bináris fa, amely
0, 1, vagy 2 maximálisan.

972
00:42:04,700 --> 00:42:09,700
De mint egy bináris keresést fa, vagy BST,
ami csak egy divatos szóval a

973
00:42:09,700 --> 00:42:15,430
bináris fa olyan, hogy minden csomópont
bal gyermek, ha jelen van,

974
00:42:15,430 --> 00:42:16,830
kevesebb, mint a csomópont.

975
00:42:16,830 --> 00:42:20,170
És minden csomópont jobb fia,
ha jelen van, a nagyobb

976
00:42:20,170 --> 00:42:21,740
mint maga a csomópont.

977
00:42:21,740 --> 00:42:25,200
>> Más szóval, ha úgy döntesz, hogy dolgozzon
a fa ki, mind a számok

978
00:42:25,200 --> 00:42:30,620
gondosan egyensúlyban ilyen, hogy ha
van 55, mint a gyökér, 33 mehet

979
00:42:30,620 --> 00:42:33,090
hogy a bal, mert kevesebb, mint 55.

980
00:42:33,090 --> 00:42:36,430
77 mehet a jogát, mivel
ez több mint 55.

981
00:42:36,430 --> 00:42:40,750
De most észre, ugyanazt a meghatározást,
ez egy rekurzív definíció szóban,

982
00:42:40,750 --> 00:42:42,600
kell alkalmazni 33.

983
00:42:42,600 --> 00:42:47,610
33 bal gyermeke kisebb legyen, mint az,
és 33 jobb gyermek, 44, meg kell

984
00:42:47,610 --> 00:42:48,580
nagyobb, mint azt.

985
00:42:48,580 --> 00:42:51,670
>> Tehát ez egy bináris keresést fa, és
Azt javaslom, egy kis

986
00:42:51,670 --> 00:42:53,910
rekurzió, akkor most meg n.

987
00:42:53,910 --> 00:42:59,160
Tehát, ha n kisebb, mint az érték n, ami
jelenlegi csomópont, én megyek

988
00:42:59,160 --> 00:43:04,090
előre, és punt, hogy úgy mondjam, és csak
vissza, amit a válasz a

989
00:43:04,090 --> 00:43:08,470
keres n a
fa bal fia.

990
00:43:08,470 --> 00:43:11,370
Figyeljük meg újra, ez a funkció csak
vár csomópont csillag,

991
00:43:11,370 --> 00:43:12,780
mutató egy csomópont.

992
00:43:12,780 --> 00:43:17,360
Így biztosan meg tudom csinálni, csak fa
Balra mutató nyíl, ami ahhoz vezet,

993
00:43:17,360 --> 00:43:18,400
nekem egy másik csomópont.

994
00:43:18,400 --> 00:43:19,480
De mi az, hogy a csomópont?

995
00:43:19,480 --> 00:43:22,820
>> Nos, a ezt a nyilatkozatot,
bal csak egy mutató, hogy a csak

996
00:43:22,820 --> 00:43:27,090
azt jelenti, hogy én halad a keresési funkció
egy másik mutató, azaz

997
00:43:27,090 --> 00:43:30,750
az, amelyik
a bal gyerek fa.

998
00:43:30,750 --> 00:43:36,040
Tehát ebben az esetben a mutató 33, ha a
ez a mi minta input Közben, ha

999
00:43:36,040 --> 00:43:40,740
n értéke nagyobb, mint az n érték a
jelenlegi csomópont a fában, akkor én vagyok

1000
00:43:40,740 --> 00:43:43,370
megyek előre, és punt a másik
irányba, és csak annyit, én nem

1001
00:43:43,370 --> 00:43:47,280
tudom, hogy ez az érték n a fán,
de azt tudom, hogy az, hogy végig a

1002
00:43:47,280 --> 00:43:49,090
jobb ág, hogy úgy mondjam.

1003
00:43:49,090 --> 00:43:53,120
Hadd hívjam fel rekurzívan megkeresi,
leadott n újra, de halad a

1004
00:43:53,120 --> 00:43:54,580
mutató az én jobb fia.

1005
00:43:54,580 --> 00:44:00,020
>> Más szóval, ha én vagyok jelenleg 55
és én keresek 99, tudom, hogy 99

1006
00:44:00,020 --> 00:44:04,270
nagyobb, mint 55, úgyhogy ahogy téptem
A telefonkönyv héttel ezelőtt, és

1007
00:44:04,270 --> 00:44:07,140
rendben zajlott, hasonlóan vagyunk
fog menni itt.

1008
00:44:07,140 --> 00:44:11,960
És nem tudom, hogy ez az én jobb
gyerek, és ez nem 77 van, de

1009
00:44:11,960 --> 00:44:13,210
Tudom, hogy ebben az irányban.

1010
00:44:13,210 --> 00:44:18,770
Így hívom keresést a jobb gyermek,
77., és hagyja, hogy keresési alak ki

1011
00:44:18,770 --> 00:44:24,950
ott van, ha 99 ebben tetszőleges
példa valójában ott van.

1012
00:44:24,950 --> 00:44:26,900
>> Else, mi a végső helyzet?

1013
00:44:26,900 --> 00:44:28,620
Ha a fa null egy eset.

1014
00:44:28,620 --> 00:44:31,890
Ha n kisebb, mint a jelenlegi csomópont
értéke egy másik eset.

1015
00:44:31,890 --> 00:44:35,120
Ha n nagyobb, mint a jelenlegi
csomópont értéke egy harmadik eset.

1016
00:44:35,120 --> 00:44:38,250
Mi a negyedik és egyben utolsó eset?

1017
00:44:38,250 --> 00:44:39,480
Azt hiszem, az esetek, nem igaz?

1018
00:44:39,480 --> 00:44:44,690
Meg kell adni, hogy az n értéke
jelenlegi csomópont, hogy én vagyok az.

1019
00:44:44,690 --> 00:44:49,640
>> Tehát, ha én keresem 55 ezen a ponton
a történetben, hogy a fióktelep a

1020
00:44:49,640 --> 00:44:51,780
fa visszatér igaz.

1021
00:44:51,780 --> 00:44:55,380
Tehát mi az érdekes az, hogy mi
valójában, ellentétben hét múlt, azt a fajta

1022
00:44:55,380 --> 00:44:56,740
A két alap esetben.

1023
00:44:56,740 --> 00:44:58,300
És nem kell
legyen minden a tetején.

1024
00:44:58,300 --> 00:45:01,390
A felső egy alapeset, mert ha a
fa null, nincs semmi köze.

1025
00:45:01,390 --> 00:45:03,410
Csak vissza kemény kódolt
értéke hamis.

1026
00:45:03,410 --> 00:45:07,400
>> Az alsó ág van valami a
alapértelmezett, ahol ha már ellenőrizték

1027
00:45:07,400 --> 00:45:11,550
null, már ellenőrzik, ha kell,
maradt, de nem lehet, most már

1028
00:45:11,550 --> 00:45:14,640
ellenőrzik, ha kell, van, de
nem kell, egyértelműen azt kell

1029
00:45:14,640 --> 00:45:15,870
ott, ahol vagyunk.

1030
00:45:15,870 --> 00:45:16,780
Ez egy alapeset.

1031
00:45:16,780 --> 00:45:19,920
Tehát van két rekurzív esetben
szendvics ott középen.

1032
00:45:19,920 --> 00:45:21,630
De én írtam
ez bármilyen sorrendben.

1033
00:45:21,630 --> 00:45:24,520
Csak azt gondoltam, hogy ilyen filc természetes
először ellenőrizze a lehetséges hiba

1034
00:45:24,520 --> 00:45:28,340
majd ellenőrizze balra, majd ellenőrizze van, akkor
Feltételezem, hogy te vagy a csomópont

1035
00:45:28,340 --> 00:45:30,630
te tényleg keres.

1036
00:45:30,630 --> 00:45:36,240
>> Miért lehet ez hasznos lehet?

1037
00:45:36,240 --> 00:45:37,910
Így kiderül -

1038
00:45:37,910 --> 00:45:42,110
és hadd ugrani egy teaser
, hogy itt van az interneten.

1039
00:45:42,110 --> 00:45:44,920
Fogunk kezdeni a nem
programozási nyelv az első, de a

1040
00:45:44,920 --> 00:45:46,030
jelölőnyelv.

1041
00:45:46,030 --> 00:45:48,740
A jelölőnyelv, hogy az egyik, hogy ez
hasonló szellemben programozási

1042
00:45:48,740 --> 00:45:51,715
nyelv, de nem adja meg a
képes kifejezni magát logikailag.

1043
00:45:51,715 --> 00:45:55,070
Csak ad arra, hogy
kifejezni magát szerkezetileg.

1044
00:45:55,070 --> 00:45:57,960
>> Hol szeretne tenni valamit
az oldalon, a weboldal?

1045
00:45:57,960 --> 00:45:59,200
Milyen színű akarsz csinálni?

1046
00:45:59,200 --> 00:46:00,950
Milyen betűméret akarsz csinálni?

1047
00:46:00,950 --> 00:46:02,970
Milyen szavakat, hogy tényleg
szeretné a honlapon?

1048
00:46:02,970 --> 00:46:04,060
Szóval ez egy jelölőnyelv.

1049
00:46:04,060 --> 00:46:07,690
De aztán nagyon gyorsan be
JavaScript, amely egy teljes körű

1050
00:46:07,690 --> 00:46:08,560
programozási nyelv.

1051
00:46:08,560 --> 00:46:12,530
Nagyon hasonló szintaktikai megjelenésű
a C, de lesz egy kis

1052
00:46:12,530 --> 00:46:15,200
szép, erősebb,
felhasználóbarát funkciók.

1053
00:46:15,200 --> 00:46:18,050
>> És az egyik a frusztráció ebben
pont a félévben, hogy mi lesz

1054
00:46:18,050 --> 00:46:22,065
hamarosan végre helyesírás-ben sokkal kevesebb
sornyi kódot más nyelvek

1055
00:46:22,065 --> 00:46:25,580
mint a C is lehetővé teszi, de az ész
mi hamarosan érteni.

1056
00:46:25,580 --> 00:46:27,750
Ez lesz az első ilyen weboldal.

1057
00:46:27,750 --> 00:46:30,120
Ez lesz teljesen underwhelming,
Az első, amit tenni.

1058
00:46:30,120 --> 00:46:31,400
Ez egyszerűen azt mondják, hello world.

1059
00:46:31,400 --> 00:46:34,010
De ha még soha nem láttad
előtt, ez a HTML,

1060
00:46:34,010 --> 00:46:35,670
HyperText Markup Language.

1061
00:46:35,670 --> 00:46:39,310
>> Ha megy, hogy egy bizonyos menüpontra
legtöbb olyan böngészővel, bármilyen internetes oldalt

1062
00:46:39,310 --> 00:46:43,160
Az internet, láthatjuk a HTML
hogy néhány ember azt írta, hogy

1063
00:46:43,160 --> 00:46:44,400
létre, hogy a web oldalon.

1064
00:46:44,400 --> 00:46:47,850
És ez valószínűleg nem úgy néz ki,
rövid, vagy tiszta, mint ez.

1065
00:46:47,850 --> 00:46:51,400
De ez mintáját követik e
nyitott zárójelet és vágás és

1066
00:46:51,400 --> 00:46:53,660
betűk és potenciálisan számokat.

1067
00:46:53,660 --> 00:46:56,770
>> Gondoltam, kapsz egy teaser
Az, hogy mit lesz képes tenni

1068
00:46:56,770 --> 00:46:57,950
bevétele után CS50.

1069
00:46:57,950 --> 00:47:02,620
Hadd menjen cs.harvard.edu / rabolni,
saját Rob Bowden honlapján.

1070
00:47:02,620 --> 00:47:06,080
Tette ezt a számunkra.

1071
00:47:06,080 --> 00:47:07,490
Szóval hamarosan képes erre.

1072
00:47:07,490 --> 00:47:10,660
És azt is, hogy mit hallott
ma reggel -

1073
00:47:10,660 --> 00:47:12,480
mit hallott ma reggel -

1074
00:47:12,480 --> 00:47:13,780
>> [HAMSTER DANCE MUSIC]

1075
00:47:13,780 --> 00:47:15,702
>> - Meg fogja tudni, hogy ezt a.

1076
00:47:15,702 --> 00:47:16,790
Ez vár ránk szerdán.

1077
00:47:16,790 --> 00:47:17,791
Majd meglátjuk, akkor majd.

1078
00:47:17,791 --> 00:47:22,950
>> [HAMSTER DANCE MUSIC]

1079
00:47:22,950 --> 00:47:24,300
DAVID MALAN: A következő CS50 -

1080
00:47:24,300 --> 00:47:31,670