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

2
00:00:11,860 --> 00:00:13,120
>> SPEAKER 1: Rendben, így visszatértek.

3
00:00:13,120 --> 00:00:14,480
Üdvözöljük a CS50.

4
00:00:14,480 --> 00:00:16,510
Ez a vége a hét hét.

5
00:00:16,510 --> 00:00:20,200
Így emlékszem, hogy az utolsó alkalom, elkezdtük
néztem kicsit bonyolultabb

6
00:00:20,200 --> 00:00:21,100
adatszerkezeteket.

7
00:00:21,100 --> 00:00:25,110
Mivel eddig minden volt igazán
a rendelkezésünkre álló volt ez, egy tömbben.

8
00:00:25,110 --> 00:00:29,340
>> De mielőtt dobja a tömb nem
minden érdekes, ami valóban az

9
00:00:29,340 --> 00:00:33,570
valójában, mik az
pluses az egyszerű adatok

10
00:00:33,570 --> 00:00:34,560
struktúra eddig?

11
00:00:34,560 --> 00:00:36,110
Mi ez az jó?

12
00:00:36,110 --> 00:00:39,450
Amennyire láttuk?

13
00:00:39,450 --> 00:00:42,540
Mi van?

14
00:00:42,540 --> 00:00:44,028
Semmi.

15
00:00:44,028 --> 00:00:45,020
>> DIÁK: [hangtalan].

16
00:00:45,020 --> 00:00:45,395
>> SPEAKER 1: Mi ez?

17
00:00:45,395 --> 00:00:46,410
>> DIÁK: [hangtalan].

18
00:00:46,410 --> 00:00:47,000
>> SPEAKER 1: Rögzített méret.

19
00:00:47,000 --> 00:00:51,260
OK, miért is jó, bár fix méret?

20
00:00:51,260 --> 00:00:53,180
>> DIÁK: [hangtalan].

21
00:00:53,180 --> 00:00:56,240
>> SPEAKER 1: OK, így hatékony
az értelemben, hogy lehet lefoglalni a

22
00:00:56,240 --> 00:01:00,070
rögzített méretű tárterület, amely remélhetőleg
pontosan annyi

23
00:01:00,070 --> 00:01:01,180
hely, amit akar.

24
00:01:01,180 --> 00:01:02,720
Ahhoz, hogy lehet, hogy teljesen egy plusz.

25
00:01:02,720 --> 00:01:06,530
>> Mi a másik fejjel a tömb?

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

27
00:01:07,610 --> 00:01:08,750
>> DIÁK: [hangtalan].

28
00:01:08,750 --> 00:01:09,550
>> SPEAKER 1: Az összes - Tessék?

29
00:01:09,550 --> 00:01:11,270
>> DIÁK: [hangtalan].

30
00:01:11,270 --> 00:01:13,620
>> SPEAKER 1: Minden a dobozokat a memóriában
vagy egymás mellett.

31
00:01:13,620 --> 00:01:15,220
És ez hasznos - miért?

32
00:01:15,220 --> 00:01:15,970
Ez teljesen igaz.

33
00:01:15,970 --> 00:01:18,611
De hogyan tudjuk kihasználni ezt az igazságot?

34
00:01:18,611 --> 00:01:21,500
>> DIÁK: [hangtalan].

35
00:01:21,500 --> 00:01:24,490
>> SPEAKER 1: Pontosan tudjuk nyomon követni
ahol minden csak azáltal, hogy ismerik

36
00:01:24,490 --> 00:01:28,560
egy címet, azaz a címét a
első byte, hogy a darab a memóriát.

37
00:01:28,560 --> 00:01:30,420
Illetve abban az esetben a húr,
a cím az első

38
00:01:30,420 --> 00:01:31,460
char-ben, hogy a húr.

39
00:01:31,460 --> 00:01:33,330
És ott találunk
a végén a húr.

40
00:01:33,330 --> 00:01:35,710
Megtalálhatjuk a második elem, a
harmadik elem, és így tovább.

41
00:01:35,710 --> 00:01:38,740
>> És így a divatos módon írja le, hogy
jellemzője, hogy tömbök nekünk

42
00:01:38,740 --> 00:01:40,020
véletlen elérésű.

43
00:01:40,020 --> 00:01:44,330
Csak használja a szögletes zárójel
jelölést, és egy számot, akkor ugorhat

44
00:01:44,330 --> 00:01:48,070
egy adott elem a tömbben
állandó időben, nagy O

45
00:01:48,070 --> 00:01:49,810
az egyik, hogy úgy mondjam.

46
00:01:49,810 --> 00:01:51,080
>> De van itt egy kis árnyoldalai.

47
00:01:51,080 --> 00:01:53,110
Amit egy sor nem túl könnyen?

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

49
00:01:55,810 --> 00:01:57,170
Mi ez az nem jó?

50
00:01:57,170 --> 00:01:58,810
>> DIÁK: [hangtalan].

51
00:01:58,810 --> 00:01:59,860
>> SPEAKER 1: Mi ez?

52
00:01:59,860 --> 00:02:00,530
>> DIÁK: [hangtalan].

53
00:02:00,530 --> 00:02:01,460
>> SPEAKER 1: Táguló méretű.

54
00:02:01,460 --> 00:02:04,800
Így a hátrányai a tömb
éppen az ellenkezője annak, amit a

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

56
00:02:05,540 --> 00:02:07,610
Tehát az egyik hátránya az,
hogy ez egy fix méretű.

57
00:02:07,610 --> 00:02:09,400
Így nem igazán nő meg.

58
00:02:09,400 --> 00:02:13,510
Lehet átcsoportosítása nagyobb darab
memória, majd távolítsa el a régi elemeket

59
00:02:13,510 --> 00:02:14,460
az új tömb.

60
00:02:14,460 --> 00:02:18,060
És akkor szabad a régi tömb, a
Például, segítségével malloc vagy hasonló

61
00:02:18,060 --> 00:02:21,180
nevű függvényt realloc, amely
átcsoportosítása memória.

62
00:02:21,180 --> 00:02:25,490
>> Realloc, mint félre, megpróbálja, hogy az Ön
memória a következő lépés, hogy a tömb

63
00:02:25,490 --> 00:02:26,610
, hogy már van.

64
00:02:26,610 --> 00:02:28,740
De lehet mozgatni a dolgokat
körül teljesen.

65
00:02:28,740 --> 00:02:30,710
De röviden, ez drága, ugye?

66
00:02:30,710 --> 00:02:33,440
Mert ha van egy darab memória
ezt a méretet, de szeretné egy

67
00:02:33,440 --> 00:02:36,710
Az ilyen méretű, és szeretné megőrizni
Az eredeti elemek, akkor

68
00:02:36,710 --> 00:02:40,510
nagyjából lineáris idő másolási folyamat
hogy kell történni

69
00:02:40,510 --> 00:02:41,900
régi tömb az új.

70
00:02:41,900 --> 00:02:44,630
És a valóság azt kéri a működési
rendszer újra és újra és

71
00:02:44,630 --> 00:02:48,340
Ismét nagy darabokban a memóriát lehet kezdeni
kerülni egy kis időt is.

72
00:02:48,340 --> 00:02:52,250
Tehát egyszerre áldás és átok
álcázzák, az a tény, hogy ezek a tömbök

73
00:02:52,250 --> 00:02:53,860
, fix méretű.

74
00:02:53,860 --> 00:02:56,790
De ha be helyette valami
mint ez, amit úgynevezett kapcsolt

75
00:02:56,790 --> 00:03:00,580
lista, akkor kap egy pár upsides és
néhány hátrányai itt is.

76
00:03:00,580 --> 00:03:05,780
>> Tehát egy láncolt lista egyszerűen egy adat
szerkezetét alkotják C struktúrákat ebben

77
00:03:05,780 --> 00:03:09,850
esetben, amikor egy struct, visszahívás, csak
egy tartályt, egy vagy több meghatározott

78
00:03:09,850 --> 00:03:11,100
típusú változók.

79
00:03:11,100 --> 00:03:16,110
Ebben az esetben mit az adattípusok
úgy tűnik, hogy a belső struktúra, amely

80
00:03:16,110 --> 00:03:17,600
utoljára hívott egy csomópont?

81
00:03:17,600 --> 00:03:19,380
Minden ilyen téglalapok egy csomópont.

82
00:03:19,380 --> 00:03:22,660
És az egyes kisebb téglalapok
belül ez az adat típusát.

83
00:03:22,660 --> 00:03:25,300
Milyen mondtunk
voltak hétfőn?

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

85
00:03:26,478 --> 00:03:27,870
>> DIÁK: [hangtalan].

86
00:03:27,870 --> 00:03:30,721
>> SPEAKER 1: A változó, és a mutató, vagy
Pontosabban, egy int, n,

87
00:03:30,721 --> 00:03:32,180
és egy mutatót az alján.

88
00:03:32,180 --> 00:03:35,360
E két történetesen 32 bit, a
legalább egy számítógép, mint a CS50

89
00:03:35,360 --> 00:03:37,980
Készülékhez, és így ők
húzott egyaránt méretű.

90
00:03:37,980 --> 00:03:42,260
>> Tehát mi a mutató
noha a látszólag?

91
00:03:42,260 --> 00:03:47,690
Miért ezt az most, amikor a nyíl tömbök voltak
olyan szép és tiszta és egyszerű?

92
00:03:47,690 --> 00:03:50,460
Mi a mutatót tesz az
minket minden ilyen csomópont?

93
00:03:50,460 --> 00:03:52,160
>> DIÁK: [hangtalan].

94
00:03:52,160 --> 00:03:52,465
>> SPEAKER 1: Pontosan.

95
00:03:52,465 --> 00:03:54,120
Azt mondja, hogy hol
a következőt.

96
00:03:54,120 --> 00:03:57,350
Szóval fajta használat az analógia
egy szál egyfajta

97
00:03:57,350 --> 00:03:59,180
menet ezek a csomópontok egymáshoz.

98
00:03:59,180 --> 00:04:01,760
És pontosan ez az, amit mi csinálunk az
pointerek, mert minden egyes ilyen

99
00:04:01,760 --> 00:04:06,360
darabokat a memória lehet vagy nem lehet
összefüggő, háttal vissza

100
00:04:06,360 --> 00:04:09,500
belső RAM-mal, mert minden egyes alkalommal, amikor
hívja malloc mondván ad nekem elég

101
00:04:09,500 --> 00:04:12,510
byte egy új csomópont, akkor lehet, hogy
hogy itt, vagy lehet, hogy itt.

102
00:04:12,510 --> 00:04:13,120
Lehet, hogy itt.

103
00:04:13,120 --> 00:04:13,730
Lehet, hogy itt.

104
00:04:13,730 --> 00:04:14,640
Csak nem tudom.

105
00:04:14,640 --> 00:04:17,880
>> De a mutatók a címét
azokat a csomópontokat, akkor öltés őket

106
00:04:17,880 --> 00:04:22,370
együtt oly módon, hogy úgy néz ki, vizuálisan
mint egy lista, még ha ezek a dolgok

107
00:04:22,370 --> 00:04:26,770
minden szét az egész egy-
a kettő vagy a négy gigabájt RAM

108
00:04:26,770 --> 00:04:28,760
belül a saját számítógépén.

109
00:04:28,760 --> 00:04:33,230
>> Tehát a hátránya, akkor a
A láncolt lista, mi?

110
00:04:33,230 --> 00:04:34,670
Mi az ára vagyunk
látszólag fizet?

111
00:04:34,670 --> 00:04:36,010
>> DIÁK: [hangtalan].

112
00:04:36,010 --> 00:04:36,920
>> SPEAKER 1: több hely, nem igaz?

113
00:04:36,920 --> 00:04:39,340
Már ebben az esetben, az összeg megduplázódott
a tér, mert mi már elment

114
00:04:39,340 --> 00:04:43,500
32 bit minden csomópont minden egyes
int, így most 64 bites, mert meg kell

115
00:04:43,500 --> 00:04:45,050
folyamatosan mintegy mutató is.

116
00:04:45,050 --> 00:04:48,860
Kapsz hatékonyabb, ha a struktúra
nagyobb, mint ez az egyszerű dolog.

117
00:04:48,860 --> 00:04:52,020
Ha valóban van egy tanuló belül
, amely egy pár húrok

118
00:04:52,020 --> 00:04:55,430
név és a ház, talán egy azonosító számot,
esetleg más területeken összesen.

119
00:04:55,430 --> 00:04:59,000
>> Tehát, ha van egy elég nagy struct,
akkor talán a költségek a mutató

120
00:04:59,000 --> 00:05:00,010
nem olyan nagy dolog.

121
00:05:00,010 --> 00:05:03,570
Ez egy kicsit a sarokban eset, hogy
mi tárolása ilyen egyszerű primitív

122
00:05:03,570 --> 00:05:04,760
belül a láncolt lista.

123
00:05:04,760 --> 00:05:05,790
De a lényeg ugyanaz.

124
00:05:05,790 --> 00:05:08,230
Te határozottan kiadások több
memória, de akkor már

125
00:05:08,230 --> 00:05:08,990
rugalmasság.

126
00:05:08,990 --> 00:05:12,280
Mert most, ha azt akarom, hogy egy elemet
elején ez a lista,

127
00:05:12,280 --> 00:05:14,340
Van hozzá egy új csomópontot.

128
00:05:14,340 --> 00:05:17,180
És azt kell csak frissíteni az
nyilak valahogy csak mozog

129
00:05:17,180 --> 00:05:17,980
Egyes mutatók körül.

130
00:05:17,980 --> 00:05:20,580
>> Ha szeretné szúrni valamit a
közepén a lista, nem kell

131
00:05:20,580 --> 00:05:24,410
tolja félre mindenki, ahogy tettük
hét múlt a mi önkéntesek, akik

132
00:05:24,410 --> 00:05:25,700
képviselte tömb.

133
00:05:25,700 --> 00:05:29,470
Én csak ki egy új csomópontot és
akkor csak pont a nyilak

134
00:05:29,470 --> 00:05:32,290
különböző irányokba, mert nem
kell maradniuk a tényleges

135
00:05:32,290 --> 00:05:35,670
memória egy igazi sort, amit húzott
itt a képernyőn.

136
00:05:35,670 --> 00:05:38,400
>> És akkor végül, ha azt szeretnénk beszúrni
valamit a végén a lista, ez

137
00:05:38,400 --> 00:05:39,210
még könnyebb.

138
00:05:39,210 --> 00:05:43,320
Ez a fajta önkényes jelölés,
de 34 a mutató, hogy egy kitalálni.

139
00:05:43,320 --> 00:05:46,710
Mi az értéke a legtöbb mutató
valószínű húzott valami, mint egy régi

140
00:05:46,710 --> 00:05:47,700
iskola antenna ott?

141
00:05:47,700 --> 00:05:48,920
>> DIÁK: [hangtalan].

142
00:05:48,920 --> 00:05:49,900
>> SPEAKER 1: Talán null.

143
00:05:49,900 --> 00:05:52,710
És valóban, ez az egyik szerző
képviselete null.

144
00:05:52,710 --> 00:05:56,310
És ez null, mert teljesen
tudniuk kell, hol a végén egy kapcsolt

145
00:05:56,310 --> 00:06:00,050
lista, nehogy tartani a következő, és
következő és az azt követő A nyilak

146
00:06:00,050 --> 00:06:01,170
néhány szemetet értéket.

147
00:06:01,170 --> 00:06:06,230
Így null fogja jelenti, hogy nincs
több csomópont jobbra szám 34,

148
00:06:06,230 --> 00:06:07,200
ebben az esetben.

149
00:06:07,200 --> 00:06:10,270
>> Ezért javaslom, hogy végre
ez a csomópont kódot.

150
00:06:10,270 --> 00:06:12,130
És láttunk ilyen
A szintaxis előtt.

151
00:06:12,130 --> 00:06:15,090
Typedef csak definiál egy új típusú
bennünket, ad nekünk egy szinonimája, mint a

152
00:06:15,090 --> 00:06:17,100
szöveg volt char *.

153
00:06:17,100 --> 00:06:21,030
Ebben az esetben, ez lesz, hogy nekünk
rövidítéseket, hogy a struktúra csomópont

154
00:06:21,030 --> 00:06:24,010
ehelyett csak írható fel
csomópont, ami sokkal tisztább.

155
00:06:24,010 --> 00:06:25,360
Ez egy sokkal kevésbé bőbeszédű.

156
00:06:25,360 --> 00:06:30,080
>> Belsejében egy csomópont látszólag egy int
nevezett n, majd a struct csomópont *

157
00:06:30,080 --> 00:06:34,670
ami azt jelenti, hogy pontosan mit akarunk a
nyilak azt jelenti, egy mutatót egy másik

158
00:06:34,670 --> 00:06:36,940
csomópont pontosan ugyanolyan típusú adatokat.

159
00:06:36,940 --> 00:06:40,300
És azt javaslom, hogy mi is végre egy
keresési funkció, mint ez, ami a

160
00:06:40,300 --> 00:06:41,890
Első pillantásra úgy tűnhet,
egy kicsit bonyolult.

161
00:06:41,890 --> 00:06:43,330
De nézzük, hogy összefüggésben.

162
00:06:43,330 --> 00:06:45,480
>> Hadd menjek át a készülék itt.

163
00:06:45,480 --> 00:06:48,460
Hadd nyit egy fájlt a
lista nulla pont h.

164
00:06:48,460 --> 00:06:53,950
És, hogy csak azokat a definíció is
Most láttam egy pillanatra ezelőtt ez az adat

165
00:06:53,950 --> 00:06:55,390
típusú úgynevezett csomópont.

166
00:06:55,390 --> 00:06:57,350
Így már fel, hogy egy pont h fájlt.

167
00:06:57,350 --> 00:07:01,430
>> És mint félre, bár ez a
program, fogsz látni,

168
00:07:01,430 --> 00:07:05,410
egyáltalán nem olyan bonyolult, hogy ez valóban
egyezmény írásakor a program

169
00:07:05,410 --> 00:07:10,270
a dolgokat, mint a adattípusok, hogy húzza
állandók néha belül a

170
00:07:10,270 --> 00:07:13,210
header fájlt, és nem feltétlenül a
a C fájlt, természetesen, amikor a

171
00:07:13,210 --> 00:07:17,370
programok egyre nagyobbak, így a
tudja, hol kell keresni mind a

172
00:07:17,370 --> 00:07:20,840
dokumentáció egyes esetekben, vagy
az alapok, mint ez, a

173
00:07:20,840 --> 00:07:22,360
meghatározása bizonyos típusú.

174
00:07:22,360 --> 00:07:25,680
>> Ha most nyit lista nulla pont
c, észre néhány dolgot.

175
00:07:25,680 --> 00:07:29,090
Ez magában foglalja a pár header fájl, a legtöbb
amely már látott.

176
00:07:29,090 --> 00:07:31,980
Ez magában foglalja a saját header file.

177
00:07:31,980 --> 00:07:35,200
>> És mint félre, miért ez kétszeres
idézetek itt, szemben a szög

178
00:07:35,200 --> 00:07:38,340
zárójelben a vonalon, hogy
Már kiemelt ott?

179
00:07:38,340 --> 00:07:39,180
>> DIÁK: [hangtalan].

180
00:07:39,180 --> 00:07:40,460
>> SPEAKER 1: Igen, tehát ez egy helyi fájl.

181
00:07:40,460 --> 00:07:44,300
Tehát, ha ez egy helyi fájl a saját itt
on line 15, például, használja

182
00:07:44,300 --> 00:07:46,570
Az idézőjelek helyett
A szögletes zárójelben szerepel.

183
00:07:46,570 --> 00:07:48,270
>> Most ez elég érdekes.

184
00:07:48,270 --> 00:07:51,830
Figyeljük meg, hogy én már kijelentette, a globális
változó a program on-line 18

185
00:07:51,830 --> 00:07:55,910
hívott először, az ötlet is, hogy ez
lesz a mutató az első

186
00:07:55,910 --> 00:07:59,190
node a láncolt lista, és én
inicializálni, hogy nulla, mert én már

187
00:07:59,190 --> 00:08:02,310
nem osztják tényleges
csomópontok csak még.

188
00:08:02,310 --> 00:08:07,570
>> Tehát ez azt jelenti, képszerűen, amit
látta, hogy egy perce a képet

189
00:08:07,570 --> 00:08:10,090
hogy mutató a távoli
bal oldalon.

190
00:08:10,090 --> 00:08:12,260
Tehát most, hogy a mutató
nem rendelkezik egy nyíl.

191
00:08:12,260 --> 00:08:14,590
Ez inkább csak null.

192
00:08:14,590 --> 00:08:17,880
De ez jelenti, hogy mi lesz a
címét az első tényleges

193
00:08:17,880 --> 00:08:19,480
node ebben a listában.

194
00:08:19,480 --> 00:08:22,120
Így megadtam azt a globális
mert, mint látni fogod, mindez

195
00:08:22,120 --> 00:08:25,310
program nem az életben végre
egy láncolt lista számomra.

196
00:08:25,310 --> 00:08:27,050
>> Most már van egy pár prototípus itt.

197
00:08:27,050 --> 00:08:31,190
Úgy döntöttem, hogy végre funkciók, mint a
törlés, beillesztés, keresés, és a

198
00:08:31,190 --> 00:08:31,740
bejárása -

199
00:08:31,740 --> 00:08:35,210
Az utóbbi csak, hogy séta a
lista kinyomtatásával elemei.

200
00:08:35,210 --> 00:08:36,750
És most itt van a fő rutin.

201
00:08:36,750 --> 00:08:39,890
És nem túl sok időt töltenek a
Ezen mivel ez a fajta, remélhetőleg

202
00:08:39,890 --> 00:08:41,780
öreg már.

203
00:08:41,780 --> 00:08:45,370
>> Fogok csinálni a következő,
miközben a felhasználó együttműködik.

204
00:08:45,370 --> 00:08:47,300
Tehát az egyik, megyek nyomtatni
ki ebben a menüben.

205
00:08:47,300 --> 00:08:49,420
És én ezt alakítottuk
tisztán, ahogy csak tudtam.

206
00:08:49,420 --> 00:08:52,240
Ha a felhasználó az egyik, ami azt jelenti,
akarnak törölni valamit.

207
00:08:52,240 --> 00:08:54,560
Ha a felhasználó két, azt jelenti, hogy
akarnak szúrni valamit.

208
00:08:54,560 --> 00:08:55,930
És így tovább.

209
00:08:55,930 --> 00:08:58,270
Megyek, majd gyors
majd a parancs.

210
00:08:58,270 --> 00:08:59,300
És akkor fogom használni getInt.

211
00:08:59,300 --> 00:09:02,790
>> Tehát ez egy nagyon egyszerű menuing
felület, ahol csak be kell gépelni

212
00:09:02,790 --> 00:09:05,270
Számos leképezés egy
olyan parancsokat.

213
00:09:05,270 --> 00:09:08,730
És most van egy szép tiszta switch
nyilatkozat arról, hogy fog bekapcsolni

214
00:09:08,730 --> 00:09:10,090
, amit a felhasználó beírt szöveg

215
00:09:10,090 --> 00:09:12,180
És ha megadtunk, én
hívás törléséhez és szünet.

216
00:09:12,180 --> 00:09:14,380
Ha két gépelt, én
hívja be, és szünet.

217
00:09:14,380 --> 00:09:16,490
>> És most észre tettem minden
Ezek ugyanabban a sorban.

218
00:09:16,490 --> 00:09:18,360
Ez csak egy stilisztikai döntést.

219
00:09:18,360 --> 00:09:20,210
Általában láttunk valamit
, mint ez.

220
00:09:20,210 --> 00:09:23,260
De úgy döntöttem, őszintén szólva, a programom
látszott olvashatóbb, mert

221
00:09:23,260 --> 00:09:25,980
hogy csak négy esetben
csak a lista, mint ez.

222
00:09:25,980 --> 00:09:28,360
Teljesen jogszerű használatát a stílus.

223
00:09:28,360 --> 00:09:31,480
És én fogom csinálni, amíg a
felhasználó még nem írta nulla, ami azt

224
00:09:31,480 --> 00:09:33,910
úgy döntött, akkor azt jelenti, hogy ki akar lépni.

225
00:09:33,910 --> 00:09:36,630
>> Szóval most észre, amit én
fog itt csinálni.

226
00:09:36,630 --> 00:09:38,650
Megyek, hogy kiszabadítsa a lista nyilvánvalóan.

227
00:09:38,650 --> 00:09:40,230
De még az, hogy csak egy pillanatra.

228
00:09:40,230 --> 00:09:41,640
Nézzük először a program futtatásához.

229
00:09:41,640 --> 00:09:45,250
Hadd tegyek egy nagyobb terminál
ablak, pont slash listán 0.

230
00:09:45,250 --> 00:09:49,510
Én megyek előre, és helyezze a
gépelés két, több mint 50, és most

231
00:09:49,510 --> 00:09:51,590
látni fogja a lista most már 50..

232
00:09:51,590 --> 00:09:53,380
És a szöveg csak görgetni egy kicsit.

233
00:09:53,380 --> 00:09:55,940
Tehát most észre a lista
a 50-es.

234
00:09:55,940 --> 00:09:58,220
>> Csináljunk egy betétet, hogy két.

235
00:09:58,220 --> 00:10:01,630
Nézzük írja be a számot, mint egy.

236
00:10:01,630 --> 00:10:03,940
Lista ma már az egyik, majd a 50.

237
00:10:03,940 --> 00:10:06,020
Tehát ez csak egy szöveges megjelenítése
a lista.

238
00:10:06,020 --> 00:10:10,550
És nézzünk be még egy szám, mint
száma 42, ami remélhetőleg

239
00:10:10,550 --> 00:10:14,620
lesz, hogy a végén a közepén, mert a
ezt a programot, a különböző fajtájú is

240
00:10:14,620 --> 00:10:16,320
elemeket, mint betétek azokat.

241
00:10:16,320 --> 00:10:17,220
Tehát ott van rá.

242
00:10:17,220 --> 00:10:20,730
Szuper egyszerű programot, amely
Teljesen használt egy tömb, de

243
00:10:20,730 --> 00:10:23,280
történetesen egy láncolt lista
csak azért, hogy dinamikusan

244
00:10:23,280 --> 00:10:24,610
növekszik, és csökken az.

245
00:10:24,610 --> 00:10:28,470
>> Szóval vessünk egy pillantást a keresést, ha
indítási parancs három akarok keresni

246
00:10:28,470 --> 00:10:31,040
, mondjuk, a 43-as.

247
00:10:31,040 --> 00:10:34,190
És semmi sem úgy tűnik találtak,
mert kaptam vissza semmi válasz.

248
00:10:34,190 --> 00:10:35,010
Szóval ezt újra.

249
00:10:35,010 --> 00:10:35,690
Keresés.

250
00:10:35,690 --> 00:10:39,520
Keressünk 50, vagy inkább keressen
42, amely egy szép

251
00:10:39,520 --> 00:10:40,850
kis finom értelme.

252
00:10:40,850 --> 00:10:42,610
És megtaláltam az élet értelmét is.

253
00:10:42,610 --> 00:10:44,990
Number 42, ha nem tudod
A referencia, a Google is.

254
00:10:44,990 --> 00:10:45,350
Rendben van.

255
00:10:45,350 --> 00:10:47,130
Tehát mi ezt a programot tett velem?

256
00:10:47,130 --> 00:10:50,660
Ez csak lehetővé tette számomra, hogy helyezze így
messze keressen elemekkel.

257
00:10:50,660 --> 00:10:53,650
>> Nézzük gyors előre, aztán, hogy
ezt a funkciót is nézett

258
00:10:53,650 --> 00:10:55,360
hétfőn a teaser.

259
00:10:55,360 --> 00:10:59,620
Tehát ezt a funkciót, azt állítom, keres
egy elemet a listában első

260
00:10:59,620 --> 00:11:03,830
egy, a felhasználó megkérdezése, majd a hívás
GetInt hogy tényleges int

261
00:11:03,830 --> 00:11:05,060
hogy szeretne keresni.

262
00:11:05,060 --> 00:11:06,460
>> Aztán észre.

263
00:11:06,460 --> 00:11:10,690
Megyek, hogy hozzon létre egy ideiglenes változót
sorban 188 nevű mutató -

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

265
00:11:11,270 --> 00:11:12,440
volna nevezte semmit.

266
00:11:12,440 --> 00:11:16,140
És ez egy mutató egy csomópont
mert azt mondtam, node * ott.

267
00:11:16,140 --> 00:11:19,900
És én inicializálása, hogy egyenlő
először úgy, hogy hatékonyan van a

268
00:11:19,900 --> 00:11:22,860
ujj, hogy úgy mondjam, a nagyon
első elemét a lista.

269
00:11:22,860 --> 00:11:27,460
Tehát, ha a jobb kezem itt van PTR vagyok
mutatott ugyanaz a dolog, hogy az első

270
00:11:27,460 --> 00:11:28,670
néz.

271
00:11:28,670 --> 00:11:31,430
>> Tehát most vissza kódot,
mi történik ezután -

272
00:11:31,430 --> 00:11:35,070
ez egy közös paradigma amikor iterációjával
egy szerkezet, mint a

273
00:11:35,070 --> 00:11:35,970
láncolt lista.

274
00:11:35,970 --> 00:11:40,410
Fogok csinálni a következő, míg
mutató nem egyenlő null Tehát miközben

275
00:11:40,410 --> 00:11:47,530
az ujjam nem mutat valami null
érték, ha a mutató nyíl n értéke n.

276
00:11:47,530 --> 00:11:52,290
Majd észre először, hogy n, amit a
felhasználó beírt egy GetInts hívás itt.

277
00:11:52,290 --> 00:11:54,280
>> És a mutató nyíl n mit jelent?

278
00:11:54,280 --> 00:11:59,020
Nos, ha visszamegyünk a kép itt,
ha van egy ujjal mutatva

279
00:11:59,020 --> 00:12:02,960
hogy az első csomópont, amely kilenc, a
arrow lényegében azt jelenti, megy, hogy a

280
00:12:02,960 --> 00:12:08,860
csomópont és megragad a érték helyre n
Ebben az esetben, az adatmező nevezett n.

281
00:12:08,860 --> 00:12:14,120
>> Mint félre -, és láttuk ezt néhány
héttel ezelőtt, amikor valaki megkérdezte -

282
00:12:14,120 --> 00:12:18,840
Ez a szintaxis az új, de nem
nekünk hatáskörrel, hogy

283
00:12:18,840 --> 00:12:20,040
nem volt már.

284
00:12:20,040 --> 00:12:25,325
Mi volt ez a mondat egyenértékű a
dot jelölés és a csillag egy pár

285
00:12:25,325 --> 00:12:29,490
héttel ezelőtt, amikor hámozott vissza
ez a réteg egy kicsit korán?

286
00:12:29,490 --> 00:12:31,780
>> DIÁK: [hangtalan].

287
00:12:31,780 --> 00:12:38,880
>> SPEAKER 1: Pontosan ez volt a csillag, és
akkor volt csillag dot N, ahol

288
00:12:38,880 --> 00:12:41,930
zárójelek itt, ami úgy néz ki,
őszintén szólva, azt gondolom, hogy sok

289
00:12:41,930 --> 00:12:43,320
több rejtélyes olvasni.

290
00:12:43,320 --> 00:12:46,270
De csillag mutató, mint mindig,
azt jelenti, ott.

291
00:12:46,270 --> 00:12:49,090
És ha már ott van, hogy milyen adatok
mezőt akarsz elérni?

292
00:12:49,090 --> 00:12:52,730
Jól használja a pont jelölést eléréséhez
a struktúrákat adatmező, és

293
00:12:52,730 --> 00:12:54,140
az a célunk n.

294
00:12:54,140 --> 00:12:56,240
>> Őszintén szólva, azt állítják, ez a
csak nehezebb olvasni.

295
00:12:56,240 --> 00:12:58,080
Ez nehezebb emlékezni, ahol
nem a zárójelek megy, a

296
00:12:58,080 --> 00:12:59,030
csillag, és minden adott.

297
00:12:59,030 --> 00:13:02,150
Így a világ elfogadott bizonyos szintaktikai
cukrot, hogy úgy mondjam.

298
00:13:02,150 --> 00:13:04,740
Csak egy szexi szóval,
ez egyenértékű azzal, és

299
00:13:04,740 --> 00:13:05,970
talán intuitív.

300
00:13:05,970 --> 00:13:09,600
Ha a mutató valóban mutató, az
nyíl jelölés azt jelenti, menj oda, és megtalálni

301
00:13:09,600 --> 00:13:11,890
területen ebben az esetben az úgynevezett n.

302
00:13:11,890 --> 00:13:13,660
>> Tehát, ha látom, hogy figyeld meg, mit tegyek.

303
00:13:13,660 --> 00:13:17,430
Egyszerűen nyomtassa ki, találtam százalék i,
csatlakoztatása az értéket, hogy az int.

304
00:13:17,430 --> 00:13:20,730
Hívom aludni egy másodpercig csak ilyen
szünet dolgokat a képernyőn, hogy

305
00:13:20,730 --> 00:13:22,900
hogy a felhasználó egy másik, hogy felszívja
mi történt.

306
00:13:22,900 --> 00:13:24,290
Aztán szünet.

307
00:13:24,290 --> 00:13:26,330
Egyébként, mit tegyek?

308
00:13:26,330 --> 00:13:30,960
Én frissíteni mutató egyenlő
mutató nyílra.

309
00:13:30,960 --> 00:13:35,840
>> Szóval, csak hogy tisztázzuk, ez azt jelenti, menj
ott, a régi iskola jelölést.

310
00:13:35,840 --> 00:13:39,580
Tehát ez csak azt jelenti, hogy megy, hogy bármilyen
akkor mutatott, ami az igen

311
00:13:39,580 --> 00:13:43,660
első esetben én mutat
A struct kilenc benne.

312
00:13:43,660 --> 00:13:44,510
Úgyhogy elment oda.

313
00:13:44,510 --> 00:13:47,880
És akkor a pont jelölés azt jelenti, hogy
kap az érték a jövő.

314
00:13:47,880 --> 00:13:50,470
>> De az érték, annak ellenére, hogy húzott
mint egy szűk, csak egy szám.

315
00:13:50,470 --> 00:13:51,720
Ez egy numerikus cím.

316
00:13:51,720 --> 00:13:55,670
Tehát ez egy sort, hogy a
írt, mint ez, a több rejtélyes

317
00:13:55,670 --> 00:14:00,190
módon, vagy mint ez a valamivel több
intuitív módon, csak azt jelenti, mozog a kezem

318
00:14:00,190 --> 00:14:03,460
az első csomópontból a következő egy,
majd a következő, majd a

319
00:14:03,460 --> 00:14:05,320
következő egy, és így tovább.

320
00:14:05,320 --> 00:14:09,920
>> Így nem tér ki a többi
implementáció beszúrni és törölni

321
00:14:09,920 --> 00:14:14,030
és bejárás, az első két
amely meglehetősen szó.

322
00:14:14,030 --> 00:14:17,010
És azt hiszem, ez elég könnyű, hogy
elveszett, amikor csinálja verbálisan.

323
00:14:17,010 --> 00:14:19,890
De mit tehetünk itt
próbálja meghatározni, hogyan

324
00:14:19,890 --> 00:14:21,640
legjobb, ha ezt vizuálisan.

325
00:14:21,640 --> 00:14:24,800
Mert azt javaslom, hogy ha
szeretné szúrni elemeket ebbe

326
00:14:24,800 --> 00:14:26,680
meglévő listához, amely
öt elem -

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

328
00:14:29,530 --> 00:14:33,300
ha én fogja végrehajtani ezt
kódot, azt kell vizsgálni, hogy hogyan megy

329
00:14:33,300 --> 00:14:34,160
körülbelül ezt.

330
00:14:34,160 --> 00:14:37,720
>> És azt javaslom, apró lépésekben
amely ebben az esetben úgy értem, mit

331
00:14:37,720 --> 00:14:41,090
A lehetséges forgatókönyvek, amit
ütközhet általában?

332
00:14:41,090 --> 00:14:44,120
Végrehajtása során betét kapcsolt
lista, ez csak történik, hogy a

333
00:14:44,120 --> 00:14:46,090
specifikus példája a méret az öt.

334
00:14:46,090 --> 00:14:50,420
Nos, ha azt szeretnénk beszúrni egy számot,
mint mondjuk az első számú, és

335
00:14:50,420 --> 00:14:53,380
fenntartása rendezetten, ahol
nyilván nem az első számú kell

336
00:14:53,380 --> 00:14:55,686
megy a konkrét példát?

337
00:14:55,686 --> 00:14:56,840
, Mint az elején.

338
00:14:56,840 --> 00:15:00,030
>> De mi érdekes van, hogy a
Ha szeretnénk beszúrni egy ebbe

339
00:15:00,030 --> 00:15:04,100
lista, milyen különleges mutató szüksége
frissíteni kell látszólag?

340
00:15:04,100 --> 00:15:04,610
Első.

341
00:15:04,610 --> 00:15:07,830
Szóval azt állítják, hogy ez az első eset
amit érdemes megfontolni, a

342
00:15:07,830 --> 00:15:11,140
forgatókönyv bevonásával behelyezése a
a lista elején.

343
00:15:11,140 --> 00:15:15,400
>> Nézzük tép ki talán egy olyan egyszerű, vagy akár
könnyebb eset, viszonylag szerény.

344
00:15:15,400 --> 00:15:18,110
Tegyük fel, hogy szeretné szúrni a
szám 35 rendezetten.

345
00:15:18,110 --> 00:15:20,600
Nyilvánvalóan tartozik oda.

346
00:15:20,600 --> 00:15:25,320
Tehát mi mutató nyilván fog
frissíteni kell, hogy a forgatókönyv?

347
00:15:25,320 --> 00:15:30,060
34 a mutató egyre nem null
de a címét a struct

348
00:15:30,060 --> 00:15:31,800
amely a 35-ös szám.

349
00:15:31,800 --> 00:15:32,750
Szóval ez esetben kettő.

350
00:15:32,750 --> 00:15:36,190
Így már, én vagyok a fajta kvantálás
mennyi munkát kell tennem itt.

351
00:15:36,190 --> 00:15:39,880
>> És végül, a nyilvánvaló középső eset
sőt, a közepén, ha azt akarom, hogy

352
00:15:39,880 --> 00:15:45,870
be valamit, mint mondjuk 23, hogy megy
a 23 és a 26, de

353
00:15:45,870 --> 00:15:48,680
Most a dolgok egy kicsit
részt azért, mert mi

354
00:15:48,680 --> 00:15:52,800
mutatókat kell változtatni?

355
00:15:52,800 --> 00:15:56,680
Tehát 22 nyilvánvalóan meg kell változtatni
mert nem pont 26. többé.

356
00:15:56,680 --> 00:16:00,320
Azt kell, hogy pont az új csomópont
Majd meg kell kiosztani hívja

357
00:16:00,320 --> 00:16:01,770
malloc, vagy valami hasonló.

358
00:16:01,770 --> 00:16:05,990
>> De akkor azt is kell, hogy az új csomópont, 23
ebben az esetben, hogy a mutató

359
00:16:05,990 --> 00:16:07,870
mutatott kinek?

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

361
00:16:08,560 --> 00:16:10,380
És ott lesz a
műveletek sorrendjét itt.

362
00:16:10,380 --> 00:16:13,410
Mert ha ezt ostobán, és
például kezdő elején

363
00:16:13,410 --> 00:16:16,040
a listán, és a célom az, hogy helyezze 23..

364
00:16:16,040 --> 00:16:18,610
És megnézem, nem is tartozik
Itt, közel kilenc?

365
00:16:18,610 --> 00:16:18,950
Nem.

366
00:16:18,950 --> 00:16:20,670
Vajon ide tartoznak, mellette 17?

367
00:16:20,670 --> 00:16:20,940
Nem.

368
00:16:20,940 --> 00:16:22,530
Nem tartozik ide mellé 22?

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

370
00:16:23,300 --> 00:16:26,400
>> Most, ha én vagyok bolond itt, és nem
gondoltam ez a, talán

371
00:16:26,400 --> 00:16:28,320
osztják az új csomópont a 23.

372
00:16:28,320 --> 00:16:32,080
Lehet, hogy frissíteni a mutatót
a csomópont neve 22, rámutatva

373
00:16:32,080 --> 00:16:33,080
ez az új csomópontot.

374
00:16:33,080 --> 00:16:36,140
És akkor mit kell frissíteni
Az új csomópont mutató lenni?

375
00:16:36,140 --> 00:16:38,120
>> DIÁK: [hangtalan].

376
00:16:38,120 --> 00:16:38,385
>> SPEAKER 1: Pontosan.

377
00:16:38,385 --> 00:16:39,710
Mutatva a 26.

378
00:16:39,710 --> 00:16:45,590
De a fenébe, ha nem már frissíteni
22 a mutató, hogy pont ezt a fickót, és

379
00:16:45,590 --> 00:16:48,260
most már árva, a többi
A lista, hogy úgy mondjam.

380
00:16:48,260 --> 00:16:52,140
Így műveletek sorrendjét itt
lesz fontos.

381
00:16:52,140 --> 00:16:55,100
>> Ehhez tudtam lopni,
mondjuk, hat önkéntes.

382
00:16:55,100 --> 00:16:57,650
És nézzük meg, ha nem tudjuk ezt
vizuálisan helyett code-bölcs.

383
00:16:57,650 --> 00:16:59,330
És van néhány szép stressz
golyó van ma.

384
00:16:59,330 --> 00:17:02,510
OK, mi egy, két, a
vissza - a végén ott.

385
00:17:02,510 --> 00:17:04,530
három, négy, mindketten
srácok a végén.

386
00:17:04,530 --> 00:17:05,579
És öt, hat.

387
00:17:05,579 --> 00:17:05,839
Persze.

388
00:17:05,839 --> 00:17:06,450
Öt és hat.

389
00:17:06,450 --> 00:17:08,390
Rendben, és mi jön
nektek legközelebb.

390
00:17:08,390 --> 00:17:09,640
Rendben, gyere fel.

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

392
00:17:12,010 --> 00:17:14,819
>> Rendben, ha már itt az első,
szeretné, hogy az egyik ügyetlenül

393
00:17:14,819 --> 00:17:16,119
a Google Glass itt?

394
00:17:16,119 --> 00:17:19,075
Rendben, tehát, OK, Üveg,
videofelvétel.

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

396
00:17:22,720 --> 00:17:24,589
OK, te jó menni.

397
00:17:24,589 --> 00:17:27,950
>> Rendben, ha tudtok jönni
Itt már előre elkészített

398
00:17:27,950 --> 00:17:30,110
néhány számot.

399
00:17:30,110 --> 00:17:31,240
Rendben, gyere ide.

400
00:17:31,240 --> 00:17:33,440
És miért nem megy egy kicsit
továbbá, hogy így.

401
00:17:33,440 --> 00:17:35,520
És lássuk, mi a neved,
A Google Glass?

402
00:17:35,520 --> 00:17:35,910
>> DIÁK: Ben.

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

404
00:17:36,230 --> 00:17:38,380
OK, Ben, akkor lesz az első, a szó szoros értelmében.

405
00:17:38,380 --> 00:17:40,580
Így fogunk küldeni
hogy a végén a szakaszban.

406
00:17:40,580 --> 00:17:41,670
Rendben, és a neved?

407
00:17:41,670 --> 00:17:41,990
>> DIÁK: Jason.

408
00:17:41,990 --> 00:17:44,530
>> SPEAKER 1: Jason, OK azt is megtudhatod
legyen kilences szám.

409
00:17:44,530 --> 00:17:46,700
Tehát, ha szeretné követni Ben így.

410
00:17:46,700 --> 00:17:47,010
>> DIÁK: Jill.

411
00:17:47,010 --> 00:17:49,630
>> SPEAKER 1: Jill, te leszel
17, amely, ha én csináltam volna ezt jobban,

412
00:17:49,630 --> 00:17:51,260
intelligens, szerettem volna
kezdődött a másik végén.

413
00:17:51,260 --> 00:17:52,370
Te menj arra.

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

415
00:17:53,030 --> 00:17:53,670
És te?

416
00:17:53,670 --> 00:17:53,980
>> DIÁK: Mary.

417
00:17:53,980 --> 00:17:56,130
>> SPEAKER 1: Mary, akkor 22.

418
00:17:56,130 --> 00:17:58,420
És a neve?

419
00:17:58,420 --> 00:17:58,810
>> DIÁK: Chris.

420
00:17:58,810 --> 00:18:00,100
>> SPEAKER 1: Chris, akkor 26.

421
00:18:00,100 --> 00:18:00,740
És akkor végül.

422
00:18:00,740 --> 00:18:01,400
>> DIÁK: Diana.

423
00:18:01,400 --> 00:18:02,670
>> SPEAKER 1: Diana, akkor 34.

424
00:18:02,670 --> 00:18:03,920
Szóval gyere ide.

425
00:18:03,920 --> 00:18:06,360
>> Rendben, tökéletes sorrendje
érdekében már.

426
00:18:06,360 --> 00:18:09,600
És menjünk előre, és ezt
, hogy mi is valójában -

427
00:18:09,600 --> 00:18:11,720
Ben te csak ilyen keres
ki a semmiből ott.

428
00:18:11,720 --> 00:18:15,670
OK, menjünk előre, és ábrázolja a
a fegyverek, ugyanúgy, mint én, pontosan,

429
00:18:15,670 --> 00:18:16,250
mi folyik itt.

430
00:18:16,250 --> 00:18:19,540
Így megy előre, és hogy a magatok
gyalog vagy két magatok között.

431
00:18:19,540 --> 00:18:22,900
És megy előre, és pont egy kézzel
aki ha kell mutat

432
00:18:22,900 --> 00:18:23,470
ennek alapján.

433
00:18:23,470 --> 00:18:25,890
És ha null csak pont
egyenesen a földre.

434
00:18:25,890 --> 00:18:27,690
OK, így a jó.

435
00:18:27,690 --> 00:18:32,290
>> Tehát most van egy láncolt lista, és hagyd, hogy
javasolja, hogy fogok játszani

436
00:18:32,290 --> 00:18:35,110
PTR, így nem zavarja
hordozó körül.

437
00:18:35,110 --> 00:18:37,830
És akkor - valaki hülye egyezmény -
hívhatja ezt, amit akarsz -

438
00:18:37,830 --> 00:18:39,800
elődje mutató, pred mutató -

439
00:18:39,800 --> 00:18:43,930
ez csak a beceneve adtunk a
a minta kódot a bal kezét.

440
00:18:43,930 --> 00:18:47,240
Másrészt, hogy fog tartani
követni, hogy ki kicsoda a

441
00:18:47,240 --> 00:18:48,400
következő forgatókönyvek.

442
00:18:48,400 --> 00:18:52,390
>> Tegyük fel, hogy először is azt akarom, hogy tépni le
hogy az első példa a behelyezése, mondjuk

443
00:18:52,390 --> 00:18:54,330
20. a listán.

444
00:18:54,330 --> 00:18:57,160
Szóval lesz szüksége, hogy valaki
testesítik meg a 20-as számú számunkra.

445
00:18:57,160 --> 00:18:58,950
Szóval kell valaki malloc
a közönség.

446
00:18:58,950 --> 00:18:59,380
Gyere fel.

447
00:18:59,380 --> 00:19:00,340
Mi a neve?

448
00:19:00,340 --> 00:19:01,300
>> DIÁK: Brian.

449
00:19:01,300 --> 00:19:05,270
>> SPEAKER 1: Brian, rendben, így
kell lennie a csomópont, amely 20.

450
00:19:05,270 --> 00:19:06,810
Rendben, gyere ide.

451
00:19:06,810 --> 00:19:10,025
És természetesen, ahol
Brian nem tartozik?

452
00:19:10,025 --> 00:19:12,190
Tehát, a közepén - valójában,
várj egy percet.

453
00:19:12,190 --> 00:19:13,420
Mi ezt elromlott.

454
00:19:13,420 --> 00:19:17,170
Mi, hogy ez egy sokkal nehezebb
mint azt kell először.

455
00:19:17,170 --> 00:19:21,210
OK, fogunk szabad Brian
és realloc Brian öt.

456
00:19:21,210 --> 00:19:23,680
>> OK, így most már a beszúrni kívánt
Brian öt.

457
00:19:23,680 --> 00:19:25,960
Úgyhogy gyere ide mellé
Ben egy pillanatra.

458
00:19:25,960 --> 00:19:28,250
És akkor valószínűleg mondani
ahol ez a történet lesz.

459
00:19:28,250 --> 00:19:30,500
De nézzük alaposan gondolja át,
a műveletek sorrendjét.

460
00:19:30,500 --> 00:19:32,880
És pontosan ez a vizuális
hogy fog sorban

461
00:19:32,880 --> 00:19:34,080
azzal a minta kódot.

462
00:19:34,080 --> 00:19:40,120
Tehát itt már PTR mutató kezdetben
Ben nem önmagában, hanem bármilyen

463
00:19:40,120 --> 00:19:43,245
értékeljük azt tartalmaz, ami ebben az esetben
az, - mi is a neved?

464
00:19:43,245 --> 00:19:43,670
>> DIÁK: Jason.

465
00:19:43,670 --> 00:19:47,350
>> SPEAKER 1: Jason, így mindkét Ben és én
mutatott Jason ebben a pillanatban.

466
00:19:47,350 --> 00:19:49,700
Így most azt kell meghatározni,
hol Brian tartozik?

467
00:19:49,700 --> 00:19:53,500
Tehát az egyetlen dolog, amit férhetnek hozzá
most az ő n adat elemet.

468
00:19:53,500 --> 00:19:58,280
Így fogom ellenőrizni, a
Brian kevesebb, mint Jason?

469
00:19:58,280 --> 00:19:59,770
A válasz igaz.

470
00:19:59,770 --> 00:20:03,680
>> Tehát mi most meg kell történnie,
a helyes sorrendben?

471
00:20:03,680 --> 00:20:07,120
Meg kell frissíteni, hogy hány mutatók
összesen ebben a történetben?

472
00:20:07,120 --> 00:20:10,720
Ahol a kezem még mindig mutat
Jason, és a kezét -, ha azt szeretné, hogy

473
00:20:10,720 --> 00:20:12,930
tegye a kezét, mint a, fajta, én
Nem tudom, a kérdőjel.

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

475
00:20:14,070 --> 00:20:15,670
>> Rendben, akkor
néhány jelöltet.

476
00:20:15,670 --> 00:20:20,500
Vagy Ben vagy én, vagy Brian, vagy Jason
vagy bárki más, ami

477
00:20:20,500 --> 00:20:21,370
mutatókat kell változtatni?

478
00:20:21,370 --> 00:20:23,260
Hányan vannak összesen?

479
00:20:23,260 --> 00:20:24,080
>> OK, így kettő.

480
00:20:24,080 --> 00:20:27,090
My mutató nem igazán számít már
mert én vagyok csak átmeneti.

481
00:20:27,090 --> 00:20:31,370
Tehát ez a két fickó, feltehetően,
a Ben és Brian.

482
00:20:31,370 --> 00:20:34,410
Hadd javaslom, hogy frissítse
Ben, mivel ő az első.

483
00:20:34,410 --> 00:20:36,350
Az első elem a lista
most lesz Brian.

484
00:20:36,350 --> 00:20:38,070
Így Ben pont Brian.

485
00:20:38,070 --> 00:20:39,320
OK, most mi lesz?

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

487
00:20:41,950 --> 00:20:43,460
>> Ki lesz mutatott kinek?

488
00:20:43,460 --> 00:20:44,710
>> DIÁK: [hangtalan].

489
00:20:44,710 --> 00:20:46,180
>> SPEAKER 1: OK, így Brian
pont a Jason.

490
00:20:46,180 --> 00:20:48,360
De én elvesztettem a fonalat, hogy a mutató?

491
00:20:48,360 --> 00:20:49,980
Nem tudom, hol van Jason?

492
00:20:49,980 --> 00:20:50,790
>> DIÁK: [hangtalan].

493
00:20:50,790 --> 00:20:52,620
>> SPEAKER 1: Én, mert én vagyok
az ideiglenes pointer.

494
00:20:52,620 --> 00:20:55,110
És feltehetőleg már nem változott
pont az új csomópontot.

495
00:20:55,110 --> 00:20:58,300
Tehát egyszerűen Brian pont
at aki vagyok mutatva.

496
00:20:58,300 --> 00:20:59,000
És kész.

497
00:20:59,000 --> 00:21:01,890
Tehát ha az egyik, beillesztés a
a lista elején.

498
00:21:01,890 --> 00:21:02,950
Két fontos lépés.

499
00:21:02,950 --> 00:21:06,750
Egy, meg kell frissíteni Ben, majd
mi is frissíteni Brian.

500
00:21:06,750 --> 00:21:09,230
És akkor nem kell bajlódnia
traipsing keresztül a többi

501
00:21:09,230 --> 00:21:12,680
lista, mert már megtalálta a
hely, mert tartozott a

502
00:21:12,680 --> 00:21:14,080
maradt az első elemet.

503
00:21:14,080 --> 00:21:15,400
>> Rendben, elég egyértelmű.

504
00:21:15,400 --> 00:21:18,110
Sőt, úgy érzi, már majdnem
hogy ez túl bonyolult.

505
00:21:18,110 --> 00:21:20,240
Szóval már tépni le a végén
A lista, és hol

506
00:21:20,240 --> 00:21:21,380
összetettsége elindul.

507
00:21:21,380 --> 00:21:24,560
Tehát, ha most én alloc a közönség.

508
00:21:24,560 --> 00:21:25,540
Bárki, aki szeretne játszani 55?

509
00:21:25,540 --> 00:21:26,700
Rendben, láttam a kezét először.

510
00:21:26,700 --> 00:21:29,620
Gyere fel.

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

512
00:21:30,030 --> 00:21:31,177
Mi a neve?

513
00:21:31,177 --> 00:21:32,310
>> DIÁK: [hangtalan].

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

515
00:21:33,240 --> 00:21:33,890
OK, gyere fel.

516
00:21:33,890 --> 00:21:35,730
Te leszel a szám 55.

517
00:21:35,730 --> 00:21:37,820
Szóval, persze, tartozik
végén a listán.

518
00:21:37,820 --> 00:21:41,850
Szóval visszajátszani a szimulációt velem
hogy a PTR egy pillanatra.

519
00:21:41,850 --> 00:21:44,050
Szóval először fog mutatni
bármi Ben mutatott.

520
00:21:44,050 --> 00:21:45,900
Mindketten mutat most Brian.

521
00:21:45,900 --> 00:21:48,420
Tehát 55 nem kevesebb, mint öt.

522
00:21:48,420 --> 00:21:52,510
Így fogom frissíteni magam
mutatott Brian következő mutató, aki

523
00:21:52,510 --> 00:21:54,450
Most természetesen Jason.

524
00:21:54,450 --> 00:21:57,310
55 nem kevesebb, mint kilenc, így
Fogom frissíteni PTR.

525
00:21:57,310 --> 00:21:58,890
Fogom frissíteni PTR.

526
00:21:58,890 --> 00:22:02,290
Fogom frissíteni PTR
Fogok frissíteni PTR.

527
00:22:02,290 --> 00:22:05,060
És fogok - hmm, mi
a neve?

528
00:22:05,060 --> 00:22:05,560
>> DIÁK: Diana.

529
00:22:05,560 --> 00:22:09,190
>> SPEAKER 1: Diana mutat, persze,
A null a bal kezével.

530
00:22:09,190 --> 00:22:13,030
Szóval, ha nem Habata valójában
tartozik tisztán?

531
00:22:13,030 --> 00:22:15,050
Balra, itt.

532
00:22:15,050 --> 00:22:19,460
Szóval, honnan tudom, hogy őt itt
Azt hiszem, elrontottam.

533
00:22:19,460 --> 00:22:22,420
Mert ami PTR művészet
ebben a pillanatban?

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

535
00:22:23,240 --> 00:22:25,580
Tehát még akkor is, vizuálisan, tudjuk
természetesen az összes ilyen

536
00:22:25,580 --> 00:22:26,610
srácok itt a színpadon.

537
00:22:26,610 --> 00:22:29,680
Én nem tartom számon az előző
személy a listán.

538
00:22:29,680 --> 00:22:33,210
Nincs egy ujjal rámutatva,
ebben az esetben a csomópont a 34.

539
00:22:33,210 --> 00:22:34,760
>> Szóval tényleg kezd túl rajta.

540
00:22:34,760 --> 00:22:37,560
Szóval most tényleg nem kell
Egy másik helyi változót.

541
00:22:37,560 --> 00:22:40,980
És ez az, amit látni fogja a
tényleges minta C kód, ahol, ahogy megy,

542
00:22:40,980 --> 00:22:45,860
amikor frissíteni a jobb kezem, hogy pont
Jason, így hagyva maga mögött Brian, én

543
00:22:45,860 --> 00:22:51,440
Jobb lenne, ha a bal kezemet, hogy
frissítés, ahol voltam, hogy amint megyek

544
00:22:51,440 --> 00:22:52,700
át ezt a listát -

545
00:22:52,700 --> 00:22:55,040
több ügyetlenül, mint akartam
most itt vizuálisan -

546
00:22:55,040 --> 00:22:56,740
Megyek, hogy a
a lista végén.

547
00:22:56,740 --> 00:23:00,020
>> Ez a kéz még mindig nulla, ami elég
haszontalan, kivéve, hogy jelzi

548
00:23:00,020 --> 00:23:02,980
Én egyértelműen az a lista végén,
de most legalább már ezt

549
00:23:02,980 --> 00:23:08,270
elődje mutató pointer van, így
most mi kéz és milyen mutatókat kell

550
00:23:08,270 --> 00:23:10,150
frissíteni kell?

551
00:23:10,150 --> 00:23:13,214
Kinek a keze akarsz
átalakítására az első?

552
00:23:13,214 --> 00:23:15,190
>> DIÁK: [hangtalan].

553
00:23:15,190 --> 00:23:16,220
>> SPEAKER 1: OK, Diana.

554
00:23:16,220 --> 00:23:21,110
Hol szeretne mutatni
Diana bal mutató at?

555
00:23:21,110 --> 00:23:23,620
A 55., feltehetően úgy, hogy
már be oda.

556
00:23:23,620 --> 00:23:25,560
És ha kell, 55 mutató menni?

557
00:23:25,560 --> 00:23:27,000
Le, ami null.

558
00:23:27,000 --> 00:23:28,890
És a kezem, ezen a ponton, nem
számít, mert ők csak

559
00:23:28,890 --> 00:23:30,070
ideiglenes változókat.

560
00:23:30,070 --> 00:23:31,030
Tehát most végeztünk.

561
00:23:31,030 --> 00:23:34,650
>> Így a további komplexitás ott - és
ez nem olyan nehéz végrehajtani,

562
00:23:34,650 --> 00:23:38,660
de szükségünk van egy másodlagos változó, hogy a
meg arról, hogy mielőtt mozgatni a jobb

563
00:23:38,660 --> 00:23:42,140
viszont tudom frissíteni az érték a bal
kéz, pred mutató ebben az esetben, így

564
00:23:42,140 --> 00:23:45,860
hogy van egy hátsó mutató
nyomon követni, hogy hol vagyok.

565
00:23:45,860 --> 00:23:49,360
Most, mint egy félre, ha azt gondolva, ez
keresztül, ez olyan, mintha egy

566
00:23:49,360 --> 00:23:51,490
kicsit bosszantó, hogy meg kell tartani
nyomon a bal kezét.

567
00:23:51,490 --> 00:23:54,015
>> Mi lenne más megoldást
erre a problémára volna?

568
00:23:54,015 --> 00:23:56,500
Ha megvan átalakítása az adatok
szerkezet beszélünk

569
00:23:56,500 --> 00:23:59,630
a most?

570
00:23:59,630 --> 00:24:02,690
Ha ez csak egyfajta érzi, egy kicsit
bosszantó, hogy, mint a két mutató

571
00:24:02,690 --> 00:24:08,430
megy át a listát, ki más
van, egy ideális világban, fenn

572
00:24:08,430 --> 00:24:10,160
információt, amire szükségünk van?

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

574
00:24:11,360 --> 00:24:12,610
>> DIÁK: [hangtalan].

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

576
00:24:15,160 --> 00:24:16,150
>> SPEAKER 1: Pontosan.

577
00:24:16,150 --> 00:24:19,130
Jobb így valójában egy érdekes
csírája egy ötletem.

578
00:24:19,130 --> 00:24:22,470
És ez az ötlet, a korábbi mutató,
mutatott az előző elem.

579
00:24:22,470 --> 00:24:25,580
Mi van, ha én csak testet öltött, hogy
belül a lista is?

580
00:24:25,580 --> 00:24:27,810
És ez lesz nehéz elképzelni
ez nem az összes papírt

581
00:24:27,810 --> 00:24:28,830
alá a földre.

582
00:24:28,830 --> 00:24:31,860
De tegyük fel, hogy ezek a srácok egyaránt használható
a kezüket, hogy a korábbi

583
00:24:31,860 --> 00:24:35,950
mutató, és a következő mutató, ami
végrehajtási mit fogunk hívni kétszeresen

584
00:24:35,950 --> 00:24:36,830
láncolt lista.

585
00:24:36,830 --> 00:24:41,090
Ez lehetővé tenné, hogy valahogy vissza,
sokkal könnyebben nélkülem, a

586
00:24:41,090 --> 00:24:43,800
programozó, kelljen tartani
pálya kézzel -

587
00:24:43,800 --> 00:24:44,980
igazán kézzel -

588
00:24:44,980 --> 00:24:47,280
hogy hol voltam korábban
a listán.

589
00:24:47,280 --> 00:24:48,110
Így nem fogja megtenni.

590
00:24:48,110 --> 00:24:50,950
Tartjuk, hogy egyszerű, mert ez
fog jönni az ára, kétszer

591
00:24:50,950 --> 00:24:53,450
sok helyet a mutató,
ha egy második.

592
00:24:53,450 --> 00:24:55,760
De ez valóban közös
adatstruktúra néven

593
00:24:55,760 --> 00:24:57,410
kétszeresen láncolt lista.

594
00:24:57,410 --> 00:25:01,310
>> Csináljuk az utolsó példa itt, és tegye
ezek a srácok ki a nyomor.

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

596
00:25:03,270 --> 00:25:05,320
Gyere fel Az ott folyosón.

597
00:25:05,320 --> 00:25:06,280
Rendben, mi a neve?

598
00:25:06,280 --> 00:25:07,440
>> DIÁK: [hangtalan].

599
00:25:07,440 --> 00:25:07,855
>> SPEAKER 1: Tessék?

600
00:25:07,855 --> 00:25:08,480
>> DIÁK: [hangtalan].

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

602
00:25:09,410 --> 00:25:10,230
OK gyere fel.

603
00:25:10,230 --> 00:25:11,910
Te leszel 20.

604
00:25:11,910 --> 00:25:14,720
Nyilvánvalóan lesz
tartoznak, 17 és 22.

605
00:25:14,720 --> 00:25:16,150
Hadd tanuljanak a leckét.

606
00:25:16,150 --> 00:25:18,150
Fogom kezdeni mutató
mutatott Brian.

607
00:25:18,150 --> 00:25:21,190
És megyek, hogy a bal oldali
csak frissíteni Brian, ahogy mozog a

608
00:25:21,190 --> 00:25:23,600
Jason, ellenőrzés nem 20 kevesebb, mint kilenc?

609
00:25:23,600 --> 00:25:24,060
Nem.

610
00:25:24,060 --> 00:25:25,430
20 kevesebb, mint 17?

611
00:25:25,430 --> 00:25:25,880
Nem.

612
00:25:25,880 --> 00:25:27,450
20 kevesebb, mint 22?

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

614
00:25:28,440 --> 00:25:34,070
Tehát mi mutatók vagy kézzel kell változtatni
ahol ők mutatnak most?

615
00:25:34,070 --> 00:25:37,070
>> Így nem tehetünk 17 mutat 20.

616
00:25:37,070 --> 00:25:37,860
Szóval ez rendben van.

617
00:25:37,860 --> 00:25:40,080
Hol akarunk mutatni
a mutatót most?

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

619
00:25:41,330 --> 00:25:45,410
És tudjuk, hol 22, újra köszönöm
az én ideiglenes mutató.

620
00:25:45,410 --> 00:25:46,760
Így rendben vagyunk ott.

621
00:25:46,760 --> 00:25:49,440
Tehát azért, mert az átmeneti tárolás
Én folyamatosan követni, ahol mindenki.

622
00:25:49,440 --> 00:25:55,055
És most már vizuálisan menni, ahol
tartozol, és most van szükségünk az 1., 2., 3.,

623
00:25:55,055 --> 00:25:58,410
4, 5, 6, 7, 8, 9 stressz labda,
és a tapsot

624
00:25:58,410 --> 00:25:59,770
ezek a srácok, ha tudnánk.

625
00:25:59,770 --> 00:26:00,410
Szép munka.

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

627
00:26:05,320 --> 00:26:06,330
>> SPEAKER 1: Rendben.

628
00:26:06,330 --> 00:26:09,860
És lehet, hogy a darab
A papír emlékei.

629
00:26:09,860 --> 00:26:15,930
>> Rendben,, hidd el nekem, hogy ez egy nagyon
könnyebb séta, hogy a

630
00:26:15,930 --> 00:26:17,680
az emberek, mint azt a tényleges kódot.

631
00:26:17,680 --> 00:26:22,690
De mit talál egy pillanat
most, hogy ugyanaz - oh, köszönöm.

632
00:26:22,690 --> 00:26:23,630
Köszönöm -

633
00:26:23,630 --> 00:26:29,360
az, hogy rájössz, hogy ugyanazokat az adatokat
szerkezet, a láncolt lista, akkor valójában

634
00:26:29,360 --> 00:26:33,200
lehet használni, mint egy építőelem, hogy még jobban
kifinomult adatstruktúrák.

635
00:26:33,200 --> 00:26:37,620
>> És észre is a téma az, hogy
már teljesen be több

636
00:26:37,620 --> 00:26:40,060
komplexitás a végrehajtási
az algoritmus.

637
00:26:40,060 --> 00:26:43,940
Beillesztése, és ha ment keresztül,
törlés és keresés, egy kicsit

638
00:26:43,940 --> 00:26:46,660
bonyolultabb, mint amilyennek
volt egy sor.

639
00:26:46,660 --> 00:26:48,040
De szert dinamizmus.

640
00:26:48,040 --> 00:26:50,180
Kapunk adaptív adatstruktúra.

641
00:26:50,180 --> 00:26:54,010
>> De ismétlem, fizetünk az ára némi
tovább bonyolítaná, mind a

642
00:26:54,010 --> 00:26:54,910
végrehajtó.

643
00:26:54,910 --> 00:26:56,750
És mi feladta véletlen hozzáférésű.

644
00:26:56,750 --> 00:27:00,450
És hogy őszinte legyek, nincs valami jó
tiszta dia tudok adni, hogy

645
00:27:00,450 --> 00:27:03,120
Itt az áll, ezért a láncolt lista
jobb, mint egy tömb.

646
00:27:03,120 --> 00:27:04,100
És ennyiben.

647
00:27:04,100 --> 00:27:07,520
Mivel a téma reoccurring most, még
inkább a következő hetekben, a

648
00:27:07,520 --> 00:27:10,200
hogy nem feltétlenül
a helyes válasz.

649
00:27:10,200 --> 00:27:13,830
>> Ezért van külön tengelyen
A design probléma határozza.

650
00:27:13,830 --> 00:27:17,700
Ez nagyon környezetfüggő
hogy szeretnénk-e használni ezeket az adatokat

651
00:27:17,700 --> 00:27:21,750
szerkezet vagy hogy az egyik, és ez lesz
attól függ, hogy mit számít az Ön szempontjából

652
00:27:21,750 --> 00:27:24,620
az erőforrások és a komplexitás.

653
00:27:24,620 --> 00:27:28,830
>> De hadd javasoljuk, hogy az ideális az adatok
szerkezet, a Szent Grál lenne

654
00:27:28,830 --> 00:27:32,200
valamit, ami állandó az időben,
függetlenül attól, hogy mennyi a cucc

655
00:27:32,200 --> 00:27:36,940
benne, nem lenne csodálatos, ha a
adatstruktúra vissza válaszok

656
00:27:36,940 --> 00:27:37,920
állandó idő.

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

658
00:27:38,330 --> 00:27:40,110
Ez a szó a nagy szótárban.

659
00:27:40,110 --> 00:27:41,550
Vagy nem, ez a szó nem.

660
00:27:41,550 --> 00:27:43,270
Vagy az ilyen probléma.

661
00:27:43,270 --> 00:27:46,360
Nos, nézzük meg, ha nem tudjuk, legalább
egy lépést felé, hogy a.

662
00:27:46,360 --> 00:27:50,190
>> Hadd javaslat új adatszerkezet, amely
lehet használni a különböző dolgokat,

663
00:27:50,190 --> 00:27:52,260
ebben az esetben úgynevezett hash tábla.

664
00:27:52,260 --> 00:27:55,590
És így, hogy tényleg vissza pillantva
egy sor, a jelen esetben, és a

665
00:27:55,590 --> 00:28:00,550
némileg önkényesen, már húzott ezt
hash tábla, mint egy tömböt egyfajta

666
00:28:00,550 --> 00:28:02,810
kétdimenziós tömb -

667
00:28:02,810 --> 00:28:05,410
vagy inkább ez látható itt a két
dimenziós tömb -, de ez csak

668
00:28:05,410 --> 00:28:10,770
egy sor mérete 26, oly módon, hogy ha mi
hívja a tömb, asztali tartó

669
00:28:10,770 --> 00:28:12,440
nulla a téglalapot a tetején.

670
00:28:12,440 --> 00:28:15,090
Asztali tartó 25 a téglalap
az alján.

671
00:28:15,090 --> 00:28:18,620
És így talán rajzolni adat
szerkezet, amelyben szeretnék tárolni

672
00:28:18,620 --> 00:28:19,790
emberek nevét.

673
00:28:19,790 --> 00:28:24,370
>> Így például, és nem fogom felhívni a
egész dolog itt a felső, ha

674
00:28:24,370 --> 00:28:29,160
volt ez a tömb, amit én most megyek
hívja a hash tábla, és ez újra

675
00:28:29,160 --> 00:28:31,360
hely nulla.

676
00:28:31,360 --> 00:28:34,840
Ez itt a hely
egy, és így tovább.

677
00:28:34,840 --> 00:28:37,880
Azt állítom, hogy szeretném használni ezeket az adatokat
szerkezet, a vita kedvéért,

678
00:28:37,880 --> 00:28:42,600
tárolására emberek nevét, Alice és Bob
Charlie és egyéb ilyen neveket.

679
00:28:42,600 --> 00:28:46,110
Így gondolom, ez most, mint a kezdet
, mondjuk, a szótár

680
00:28:46,110 --> 00:28:47,520
sok szó.

681
00:28:47,520 --> 00:28:49,435
Történetesen neveket
a példánkban itt.

682
00:28:49,435 --> 00:28:52,560
És ez nagyon is illenek, talán, hogy
megvalósítása a helyesírás-ellenőrző, hiszen

683
00:28:52,560 --> 00:28:54,400
esetlegesen a probléma meg hat.

684
00:28:54,400 --> 00:28:59,300
>> Tehát, ha van egy sor teljes méret 26
úgy, hogy ez az a 25. helyen

685
00:28:59,300 --> 00:29:03,390
az alján, és azt állítják, hogy Alice
Az első szó a szótárban

686
00:29:03,390 --> 00:29:07,260
neveket akarok szúrni RAM,
ebbe adatstruktúra, hol

687
00:29:07,260 --> 00:29:12,480
ösztönök mondom, hogy Alice
név kell menni ebben a tömbben?

688
00:29:12,480 --> 00:29:13,510
>> Van 26 opció.

689
00:29:13,510 --> 00:29:14,990
Ahol szeretnénk tenni vele?

690
00:29:14,990 --> 00:29:16,200
Azt akarom, hogy a konzol nulla, igaz?

691
00:29:16,200 --> 00:29:18,280
A Alice, hívjuk, hogy nulla.

692
00:29:18,280 --> 00:29:20,110
És lesz az egyik B, és C lesz két.

693
00:29:20,110 --> 00:29:22,600
Így fogunk írni
Alice nevét itt.

694
00:29:22,600 --> 00:29:24,890
Ha majd helyezze Bob, a
név megy itt.

695
00:29:24,890 --> 00:29:27,280
Charlie megy itt.

696
00:29:27,280 --> 00:29:30,500
És így tovább lefelé
ez az adat struktúrát.

697
00:29:30,500 --> 00:29:32,090
>> Ez egy csodálatos adatstruktúra.

698
00:29:32,090 --> 00:29:32,730
Miért?

699
00:29:32,730 --> 00:29:37,460
Nos, mi a futási ideje
behelyezése ember nevét ebbe a

700
00:29:37,460 --> 00:29:39,850
adatstruktúra most?

701
00:29:39,850 --> 00:29:43,702
Tekintettel arra, hogy ez a tábla megvalósul,
Valóban, mint egy tömb.

702
00:29:43,702 --> 00:29:44,940
Hát ez konstans id.

703
00:29:44,940 --> 00:29:45,800
Ez sorrendben az egyik.

704
00:29:45,800 --> 00:29:46,360
Miért?

705
00:29:46,360 --> 00:29:48,630
>> Nos, hogyan lehet megállapítani,
ahol Alice tartozik?

706
00:29:48,630 --> 00:29:51,000
Akkor nézd meg melyik betű a nevét?

707
00:29:51,000 --> 00:29:51,490
Az első.

708
00:29:51,490 --> 00:29:54,350
És akkor oda, ha ez egy string,
hogy csak nézte szöveg

709
00:29:54,350 --> 00:29:55,200
konzol nulla.

710
00:29:55,200 --> 00:29:57,110
Így a nulladik jellegét a húr.

711
00:29:57,110 --> 00:29:57,610
Ez könnyű.

712
00:29:57,610 --> 00:30:00,350
Mi volt, hogy a titkosítási
feladat hete.

713
00:30:00,350 --> 00:30:05,310
És majd ha egyszer tudja, hogy Alice
betű tőkének, tudjuk kivonni

714
00:30:05,310 --> 00:30:08,160
off 65 vagy a tőke A saját maga,
hogy ad nekünk nulla.

715
00:30:08,160 --> 00:30:10,940
Tehát most már tudjuk, hogy Alice tartozik
a helyszínen nulla.

716
00:30:10,940 --> 00:30:14,240
>> És mivel a mutatót az adatok
szerkezet, valamilyen, mennyi ideig tart

717
00:30:14,240 --> 00:30:18,840
akkor vigyél találni helyre
nullára tömb?

718
00:30:18,840 --> 00:30:22,080
Csak egy lépés, igaz ez konstans id
azért, mert a véletlen elérésű mi

719
00:30:22,080 --> 00:30:23,780
tervezett volt jellemző egy tömb.

720
00:30:23,780 --> 00:30:28,570
Tehát röviden, kitalálni, mi az index
Alice neve, amely, a

721
00:30:28,570 --> 00:30:32,610
Ebben az esetben egy, vagy nézzük csak megoldani
hogy a nullára, ahol B jelentése egy és C jelentése

722
00:30:32,610 --> 00:30:34,900
két, kitalálni, hogy ki
állandó idő.

723
00:30:34,900 --> 00:30:38,510
Csak meg kell nézni az első betű,
kitalálni, ahol a nulla egy

724
00:30:38,510 --> 00:30:40,460
tömb is konstans id.

725
00:30:40,460 --> 00:30:42,140
Szóval technikailag ez
mint két lépést most.

726
00:30:42,140 --> 00:30:43,330
De ez még mindig állandó.

727
00:30:43,330 --> 00:30:46,880
Így hívják azt a nagy O egy, így már
be Alice ebbe táblázat

728
00:30:46,880 --> 00:30:48,440
állandó idő.

729
00:30:48,440 --> 00:30:50,960
>> De persze én vagyok, hogy
naiv, igaz?

730
00:30:50,960 --> 00:30:53,240
Mi van, ha van egy Aaron az osztályban?

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

732
00:30:53,990 --> 00:30:57,230
Vagy bármely más kezdődő nevek
A. Hová megyünk, hogy

733
00:30:57,230 --> 00:31:00,800
a személy, nem igaz?

734
00:31:00,800 --> 00:31:03,420
Úgy értem, most már csak három
az emberek az asztalra, így talán

735
00:31:03,420 --> 00:31:07,490
meg kell oldania Aaron a helyszínen
nulla egy kettő három.

736
00:31:07,490 --> 00:31:09,480
>> Igen, tudtam hogy egy itt.

737
00:31:09,480 --> 00:31:13,350
De aztán, ha megpróbáljuk beilleszteni a David
ez a lista, hol David menni?

738
00:31:13,350 --> 00:31:15,170
Most a rendszer elindul törés
le, ugye?

739
00:31:15,170 --> 00:31:19,210
Mert most David végül itt
ha Aaron valóban itt.

740
00:31:19,210 --> 00:31:23,060
És most ez az egész ötlet, hogy a
tiszta adatszerkezet, amely ad nekünk

741
00:31:23,060 --> 00:31:28,010
konstans idő beszúrások már nem
állandó idő, mert muszáj

742
00:31:28,010 --> 00:31:31,240
ellenőrzés, ó, fenébe, valaki már
Alice helyét.

743
00:31:31,240 --> 00:31:35,320
>> Hadd szonda a többi az adatok
szerkezet, keres egy helyet, hogy

744
00:31:35,320 --> 00:31:37,130
valaki, mint Aaron nevét.

745
00:31:37,130 --> 00:31:39,390
És így is kezd
hogy lineáris időt.

746
00:31:39,390 --> 00:31:42,710
Sőt, ha most akarja találni a
Aaron ebben adatstruktúra, és

747
00:31:42,710 --> 00:31:45,430
ellenőrzés, és Aaron neve nincs itt.

748
00:31:45,430 --> 00:31:47,960
Ideális esetben, akkor csak annyit, Aaron
nem az adatszerkezetet.

749
00:31:47,960 --> 00:31:51,530
De ha elkezd teret
Aaron, ahol kellett volna a D

750
00:31:51,530 --> 00:31:55,600
vagy E, akkor a legrosszabb esetben is ellenőrizni
az egész adatstruktúra, a

751
00:31:55,600 --> 00:31:59,480
az esetben hárul valami
lineáris a méret az asztal.

752
00:31:59,480 --> 00:32:00,920
>> Szóval minden rendben, én hozom a.

753
00:32:00,920 --> 00:32:04,200
A probléma itt az, hogy volt
26 elemek ebben a tömbben.

754
00:32:04,200 --> 00:32:05,000
Hadd változtatni.

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

756
00:32:06,010 --> 00:32:10,600
Hadd megváltoztatnunk, hogy elég, hogy a
méret 26 összesen észre az alsó

757
00:32:10,600 --> 00:32:12,720
index meg fog változni, hogy n mínusz 1.

758
00:32:12,720 --> 00:32:16,610
Ha a 26 túlságosan kicsi az ember "
nevet, mert van több ezer

759
00:32:16,610 --> 00:32:20,830
nevét a világ, nézzük csak, hogy
100 vagy 1000 vagy 10000.

760
00:32:20,830 --> 00:32:22,960
Nézzük csak lefoglalni sokkal több helyet.

761
00:32:22,960 --> 00:32:27,230
>> Nos, ez nem feltétlenül csökken
a valószínűsége, hogy nem lesz két

762
00:32:27,230 --> 00:32:31,510
emberek kezdődő nevek A, és
igen, akkor is megpróbálom, hogy egy

763
00:32:31,510 --> 00:32:33,120
nevű helyen lévő nulla is.

764
00:32:33,120 --> 00:32:36,850
Ők még mindig tart összeütközik, ami
azt jelenti, hogy továbbra is szükség van a megoldás, hogy terjesszen

765
00:32:36,850 --> 00:32:41,020
Alice és Áron és Alicia és más
kezdődő nevek A máshol.

766
00:32:41,020 --> 00:32:43,460
De milyen nagy probléma ez?

767
00:32:43,460 --> 00:32:46,870
Mi a valószínűsége, hogy
van ütközés adat

768
00:32:46,870 --> 00:32:48,240
szerkezet, mint ez?

769
00:32:48,240 --> 00:32:52,570
>> Nos, hadd - visszajövünk
erre a kérdésre itt.

770
00:32:52,570 --> 00:32:55,530
És nézd meg, hogy mi is
oldja meg először.

771
00:32:55,530 --> 00:32:58,480
Hadd húzza fel a javaslat itt.

772
00:32:58,480 --> 00:33:02,020
Amit most leírt egy algoritmus,
A heurisztikus nevű lineáris

773
00:33:02,020 --> 00:33:05,030
szondázás amely, ha megpróbálta beilleszteni
valami itt az adatok

774
00:33:05,030 --> 00:33:08,920
szerkezet, amely az úgynevezett hash tábla,
és nincs helye ott,

775
00:33:08,920 --> 00:33:12,000
igazán szonda az adatstruktúra
ellenőrzés, ez elérhető?

776
00:33:12,000 --> 00:33:13,430
Vajon ez elérhető ez elérhető?

777
00:33:13,430 --> 00:33:13,980
Ez elérhető?

778
00:33:13,980 --> 00:33:17,550
És amikor végül az, hogy helyezze be a
név, amelyet eredetileg

779
00:33:17,550 --> 00:33:19,370
máshol az adott helyen.

780
00:33:19,370 --> 00:33:23,360
De a legrosszabb esetben az egyetlen helyszínen
lehet a legalján az adatok

781
00:33:23,360 --> 00:33:25,090
szerkezet, a legvégén a tömbben.

782
00:33:25,090 --> 00:33:30,130
>> Tehát lineáris szondázás, a legrosszabb esetben,
hárul lineáris algoritmus, ahol

783
00:33:30,130 --> 00:33:34,500
Áron ha történetesen be utolsó
ebben adatstruktúra, talán

784
00:33:34,500 --> 00:33:39,540
ütköznek az első helyen, de
majd a végén a balszerencse a legvégén.

785
00:33:39,540 --> 00:33:43,940
Tehát ez nem egy konstans
idő szent grál számunkra.

786
00:33:43,940 --> 00:33:47,650
Ez a megközelítés a behelyezése elemek
egy adatstruktúra úgynevezett hash

787
00:33:47,650 --> 00:33:52,050
táblázat nem úgy tűnik, hogy állandó idő
legalábbis nem az általános esetben.

788
00:33:52,050 --> 00:33:54,000
Ez ruházni valami lineáris.

789
00:33:54,000 --> 00:33:56,970
>> Mi van, ha elhatározzuk ütközések
Kicsit másképp?

790
00:33:56,970 --> 00:34:00,740
Tehát itt egy kifinomultabb
megközelítés, mi még mindig

791
00:34:00,740 --> 00:34:02,800
úgynevezett hash tábla.

792
00:34:02,800 --> 00:34:05,890
És hash, Mellesleg, mit
Úgy értem, az index

793
00:34:05,890 --> 00:34:07,070
Utaltam korábban.

794
00:34:07,070 --> 00:34:09,810
A hash valami lehet
úgy, mint egy ige.

795
00:34:09,810 --> 00:34:13,690
>> Tehát, ha hash Alice egy név,
a hash függvényt, hogy úgy mondjam,

796
00:34:13,690 --> 00:34:14,710
vissza kell adnia egy számot.

797
00:34:14,710 --> 00:34:18,199
Ebben az esetben nulla, ha tartozik a
elhelyezkedés nulla, egy, ha ő tartozik a

798
00:34:18,199 --> 00:34:20,000
helyen egy, és így tovább.

799
00:34:20,000 --> 00:34:24,360
Szóval a hash függvényt eddig volt
szuper egyszerű, csak nézte a

800
00:34:24,360 --> 00:34:26,159
első betűje valaki nevét.

801
00:34:26,159 --> 00:34:29,090
De egy hash függvényt veszi
input néhány adat, a

802
00:34:29,090 --> 00:34:30,210
string, int, mindegy.

803
00:34:30,210 --> 00:34:32,239
És kiköpi általában egy számot.

804
00:34:32,239 --> 00:34:35,739
És ez a szám az, ahol az adatok
elem tartozik egy adatstruktúra

805
00:34:35,739 --> 00:34:37,800
ismert itt, mint egy hash tábla.

806
00:34:37,800 --> 00:34:41,400
>> Tehát csak ösztönösen, hogy ez a
kicsit más kontextusban.

807
00:34:41,400 --> 00:34:44,170
Ez valójában utal egy példa
beleértve születésnapok, ahol

808
00:34:44,170 --> 00:34:46,850
nem lehet kevesebb, mint
31 nap a hónapban.

809
00:34:46,850 --> 00:34:52,239
De mi ez a személy úgy dönt, hogy
teendő az ütközés?

810
00:34:52,239 --> 00:34:55,304
Context már lenni, nem ütközése
nevek, de az ütközést a születésnapok,

811
00:34:55,304 --> 00:35:00,760
ha két ember azonos születésnapját
Az október 2., például.

812
00:35:00,760 --> 00:35:02,120
>> DIÁK: [hangtalan].

813
00:35:02,120 --> 00:35:05,010
>> SPEAKER 1: Igen, itt van
bevonását a kapcsolt listák.

814
00:35:05,010 --> 00:35:07,830
Tehát úgy néz ki, egy kicsit másképp
, mint ahogy azt korábban felhívta.

815
00:35:07,830 --> 00:35:10,790
De úgy tűnik, hogy egy tömb
a bal oldalon.

816
00:35:10,790 --> 00:35:13,230
Ez az egyik index nélkül
különösebb oka.

817
00:35:13,230 --> 00:35:14,630
De ez még mindig egy tömb.

818
00:35:14,630 --> 00:35:16,160
Ez egy sor mutató.

819
00:35:16,160 --> 00:35:20,670
És minden egyes ilyen elemek mindegyike
Ezekben a körökben vagy perjel - a perjel

820
00:35:20,670 --> 00:35:23,970
képviselő null - mindegyik
pointerek látszólag mutat

821
00:35:23,970 --> 00:35:25,730
milyen adatokat szerkezet?

822
00:35:25,730 --> 00:35:26,890
A láncolt lista.

823
00:35:26,890 --> 00:35:30,530
>> Tehát most már képesek
kemény kódot a programunk

824
00:35:30,530 --> 00:35:32,010
a méret a táblázat.

825
00:35:32,010 --> 00:35:35,360
Ebben az esetben tudjuk, soha nem
több mint 31 nap egy hónapban.

826
00:35:35,360 --> 00:35:38,480
Olyan nehéz, mint a kódolás értéke 31
ésszerű ebben az összefüggésben.

827
00:35:38,480 --> 00:35:42,700
Keretében a nevek, kemény kódolás
26 nem ésszerűtlen emberek

828
00:35:42,700 --> 00:35:46,340
csak megnevezések kezdődik, például,
Az ábécé érintő át Z.

829
00:35:46,340 --> 00:35:50,180
>> Tudjuk teletölteni őket be, hogy az adatok
struktúra amíg, ha kap egy

830
00:35:50,180 --> 00:35:55,330
ütközés, akkor ne tegye a neveket itt,
azt gondolom, ahelyett, hogy ezen sejtek

831
00:35:55,330 --> 00:36:00,270
nem vonósok magukat, de
mutatókat, például, Alice.

832
00:36:00,270 --> 00:36:03,660
És akkor Alice még egy mutató
másik karakterrel kezdődő

833
00:36:03,660 --> 00:36:06,150
A. És Bob valóban megy itt.

834
00:36:06,150 --> 00:36:10,850
>> És ha van egy másik karakterrel kezdődő
A B-ben végül ide.

835
00:36:10,850 --> 00:36:15,070
És így az egyes elemeket a
asztal két, ha tervezte ezt a

836
00:36:15,070 --> 00:36:17,350
kicsit ügyesen -

837
00:36:17,350 --> 00:36:18,125
gyerünk -

838
00:36:18,125 --> 00:36:22,950
ha tervezte ezt egy kicsit
ügyesen, most lesz egy adaptív adat

839
00:36:22,950 --> 00:36:27,720
szerkezet, ahol nincs hard limit
hogy hány elemet lehet beilleszteni

840
00:36:27,720 --> 00:36:30,700
bele, mert ha van
ütközés, ez rendben van.

841
00:36:30,700 --> 00:36:34,690
Csak megy előre, és hozzáfűzi, hogy
amit láttunk egy kicsit ezelőtt még

842
00:36:34,690 --> 00:36:38,290
úgynevezett láncolt lista.

843
00:36:38,290 --> 00:36:39,690
>> Nos, nézzük szünetet egy pillanatra.

844
00:36:39,690 --> 00:36:42,570
Mi a valószínűsége, hogy egy ütközés
az első helyen?

845
00:36:42,570 --> 00:36:45,480
Rendben, lehet, hogy én mint gondoltam, talán
Túl vagyok mérnöki ezt a problémát,

846
00:36:45,480 --> 00:36:46,370
mert tudod, mit?

847
00:36:46,370 --> 00:36:49,070
Igen, jöhet akár tetszőleges
példák le a fejem tetején, mint a

848
00:36:49,070 --> 00:36:52,870
Allison és Aaron, de a valóságban,
adott egyenletes eloszlását

849
00:36:52,870 --> 00:36:56,990
bemenet, hogy van néhány véletlenszerű betoldások
egy adatstruktúra, ami igazán

850
00:36:56,990 --> 00:36:58,580
a valószínűsége, hogy egy ütközés?

851
00:36:58,580 --> 00:37:01,670
Nos kiderült, valójában
szuper magas.

852
00:37:01,670 --> 00:37:03,850
Hadd általánosítani ezt
probléma, mint ez.

853
00:37:03,850 --> 00:37:08,890
>> Tehát egy szoba n CS50 diákok, mi
a valószínűsége, hogy legalább

854
00:37:08,890 --> 00:37:11,010
két diák a szobában
ugyanaz a születésnapja?

855
00:37:11,010 --> 00:37:13,346
Tehát van mit. néhány hund -

856
00:37:13,346 --> 00:37:16,790
200, 300 ember van itt, és számos
száz ember otthon ma.

857
00:37:16,790 --> 00:37:20,670
Tehát, ha akarta, hogy megkérdezzük magunktól, mi
a valószínűsége, hogy két ember

858
00:37:20,670 --> 00:37:23,930
ebben a szobában, azonos születésnapja,
akkor ezt meg.

859
00:37:23,930 --> 00:37:26,250
És azt állítják, valóban van két
emberek azonos születésnapját.

860
00:37:26,250 --> 00:37:29,560
>> Például valaki, aki
van születésnapja ma?

861
00:37:29,560 --> 00:37:31,340
Tegnap?

862
00:37:31,340 --> 00:37:32,590
Holnap?

863
00:37:32,590 --> 00:37:35,980
Rendben, olyan érzés, mintha megyek
hogy kell ezt 363 vagy több olyan

864
00:37:35,980 --> 00:37:39,500
alkalommal valóban kitalálni
ha van egy ütközés.

865
00:37:39,500 --> 00:37:42,350
Vagy csak ezt matematikailag
nem unalmasan

866
00:37:42,350 --> 00:37:43,200
ezt.

867
00:37:43,200 --> 00:37:44,500
És javaslatot tesz a következő.

868
00:37:44,500 --> 00:37:48,740
>> Tehát azt javaslom, hogy mi is modellezni
valószínűsége a két ember, amelyek a

869
00:37:48,740 --> 00:37:55,320
ugyanaz, mint a születésnapja valószínűsége 1
mínusz a valószínűsége, ha senkinek nincs

870
00:37:55,320 --> 00:37:56,290
ugyanaz születésnapját.

871
00:37:56,290 --> 00:37:59,960
Tehát, hogy ezt, és ez még csak a
divatos módon írom ezt, mert a

872
00:37:59,960 --> 00:38:03,090
első, aki a szobában, ő
lehet bármilyen egyik lehetséges

873
00:38:03,090 --> 00:38:07,370
Születésnap feltételezve 365 nap az évben,
Elnézést kérek, hogy személyek

874
00:38:07,370 --> 00:38:08,760
A február 29. születésnapját.

875
00:38:08,760 --> 00:38:13,470
>> Tehát az első, aki ebben a szobában ingyenes
hogy tetszőleges számú születésnapok

876
00:38:13,470 --> 00:38:18,280
ki a 365 lehetőség, hogy a
fogjuk csinálni, hogy 365 osztva 365,

877
00:38:18,280 --> 00:38:18,990
amely az egyik.

878
00:38:18,990 --> 00:38:22,700
A következő személy a szobában, ha a cél
hogy elkerülje az ütközést, csak akkor

879
00:38:22,700 --> 00:38:26,460
hogy ő születésnapja, hogyan
különböző lehetséges napig?

880
00:38:26,460 --> 00:38:27,610
364.

881
00:38:27,610 --> 00:38:31,430
Tehát a második tag ez a kifejezés
lényegében ezzel, hogy a matematika a számunkra

882
00:38:31,430 --> 00:38:33,460
levonjuk le egy lehetséges nap.

883
00:38:33,460 --> 00:38:36,390
, Majd a következő napon, a következő napon, a
Másnap le a teljes számát

884
00:38:36,390 --> 00:38:38,100
Az ember a szobában.

885
00:38:38,100 --> 00:38:41,290
>> És ha akkor úgy, akkor mi
a valószínűsége, nem a velük

886
00:38:41,290 --> 00:38:45,265
egyedi születésnapok, de megint 1 mínusz
hogy, amit kap egy kifejezés

887
00:38:45,265 --> 00:38:47,810
, ami nagyon fancifully
néz ki.

888
00:38:47,810 --> 00:38:50,330
De ez sokkal érdekesebb
nézni vizuálisan.

889
00:38:50,330 --> 00:38:55,120
Ez egy olyan grafikon, ahol az x-tengely
a száma, akik a szobában, a

890
00:38:55,120 --> 00:38:56,180
számú születésnapokat.

891
00:38:56,180 --> 00:38:59,840
Az y-tengelyen a valószínűsége,
Egy ütközés, két ember

892
00:38:59,840 --> 00:39:01,230
azonos születésnapját.

893
00:39:01,230 --> 00:39:05,020
>> És a elvihető ez a görbe
hogy amint kapsz, mint 40

894
00:39:05,020 --> 00:39:11,110
diákok, akkor akár egy 90%-os valószínűséggel
combinatorically két

895
00:39:11,110 --> 00:39:13,550
ember, vagy több kellene
ugyanaz születésnapját.

896
00:39:13,550 --> 00:39:18,600
És ha egyszer eljut tetszik 58 ember számára
közel 100%-a egy esélyt a két

897
00:39:18,600 --> 00:39:21,310
ember a szobában megy, hogy a
ugyanaz születésnapja, bár ott van

898
00:39:21,310 --> 00:39:26,650
365 vagy 366 lehetséges vödör, és
csak 58 ember a szobában.

899
00:39:26,650 --> 00:39:29,900
Csak statisztikailag akkor valószínű, hogy
kap ütközések, ami rövid

900
00:39:29,900 --> 00:39:31,810
motiválja ezt a vitát.

901
00:39:31,810 --> 00:39:35,890
Ez még akkor is, ha kap képzelet itt, és
indul, amelyek ezeket a láncokat, mi még mindig

902
00:39:35,890 --> 00:39:36,950
megy, hogy ütközések.

903
00:39:36,950 --> 00:39:42,710
>> Ahhoz, hogy felveti a kérdést, hogy mi az a
költsége a beszúrások és törlések

904
00:39:42,710 --> 00:39:44,850
egy adat struktúra, mint ez?

905
00:39:44,850 --> 00:39:46,630
Hát hadd javaslom -

906
00:39:46,630 --> 00:39:51,570
és hadd menjek vissza a képernyő fölött
Itt - ha még n elemek

907
00:39:51,570 --> 00:39:56,330
listán, így ha próbálunk beilleszteni
n eleme, és mi

908
00:39:56,330 --> 00:39:58,050
összesen hány vödör?

909
00:39:58,050 --> 00:40:03,450
Mondjuk 31 teljes vödör
abban az esetben, születésnapok.

910
00:40:03,450 --> 00:40:09,240
Mi a maximális hossza egy
E láncok potenciálisan?

911
00:40:09,240 --> 00:40:12,670
>> Ha ismét van 31 lehetséges
születésnapja egy adott hónapban.

912
00:40:12,670 --> 00:40:14,580
És mi csak összecsomósodása mindenki számára -

913
00:40:14,580 --> 00:40:15,580
valójában ez egy hülye példa.

914
00:40:15,580 --> 00:40:16,960
Csináljuk 26 helyett.

915
00:40:16,960 --> 00:40:20,890
Tehát ha valóban az emberek, akiknek a neve
Először A-tól Z-ig, ezáltal

916
00:40:20,890 --> 00:40:22,780
us 26-lehetőségeket.

917
00:40:22,780 --> 00:40:25,920
És mi egy adatstruktúra, mint a
az, amit most láttam, ahol van

918
00:40:25,920 --> 00:40:30,210
egy sor mutatók, amelyek mindegyike
rámutat, hogy a láncolt lista, ahol a

919
00:40:30,210 --> 00:40:32,360
első lista mindenki
a neve Alice.

920
00:40:32,360 --> 00:40:35,770
A második lista minden a
karakterrel kezdődő A, kezdve

921
00:40:35,770 --> 00:40:36,980
B-vel, és így tovább.

922
00:40:36,980 --> 00:40:41,020
>> Mi várható hossza egyenként
ezeket a listákat, ha azt feltételezzük, a szép tiszta

923
00:40:41,020 --> 00:40:45,410
eloszlása ​​név A-tól Z-ig
az egész adatstruktúra?

924
00:40:45,410 --> 00:40:50,210
Van n ember a adatstruktúra
osztva 26, ha ők szépen

925
00:40:50,210 --> 00:40:52,110
szét az egész
adatstruktúra.

926
00:40:52,110 --> 00:40:54,970
Így a hossza minden egyes ilyen
láncok n osztva 26.

927
00:40:54,970 --> 00:40:57,380
De nagy O jelölés, mi ez?

928
00:40:57,380 --> 00:41:00,100

929
00:41:00,100 --> 00:41:02,440
Mi ez valójában?

930
00:41:02,440 --> 00:41:04,150
Szóval ez tényleg csak n, igaz?

931
00:41:04,150 --> 00:41:06,620
Mert már azt mondta a múltban,
hogy pfuj akkor osszuk 26.

932
00:41:06,620 --> 00:41:08,710
Igen, valójában gyorsabb.

933
00:41:08,710 --> 00:41:12,720
De elméletileg ez nem alapvetően
minden gyorsabb.

934
00:41:12,720 --> 00:41:16,040
>> Tehát nem úgy tűnik, hogy olyan sokat
közelebb a szent grál.

935
00:41:16,040 --> 00:41:17,750
Valójában ez csak lineáris időben.

936
00:41:17,750 --> 00:41:20,790
Heck, ezen a ponton, miért nem vagyunk
csak használ egy hatalmas láncolt lista?

937
00:41:20,790 --> 00:41:23,510
Miért nem csak használ egy nagy
tömb tárolja a nevét

938
00:41:23,510 --> 00:41:25,010
mindenki a szobában?

939
00:41:25,010 --> 00:41:28,280
Nos, van még valami,
vonzó egy hash tábla?

940
00:41:28,280 --> 00:41:30,810
Van még valami meggyőző
körülbelül egy adatstruktúra

941
00:41:30,810 --> 00:41:33,940
hogy néz ki?

942
00:41:33,940 --> 00:41:35,182
Ezt.

943
00:41:35,182 --> 00:41:37,050
>> DIÁK: [hangtalan].

944
00:41:37,050 --> 00:41:39,840
>> SPEAKER 1: Igen, és újra, ha ez csak
a lineáris idő algoritmus, és a

945
00:41:39,840 --> 00:41:42,780
lineáris idő adatstruktúra, miért nem
csak tárolja mindenki nevét egy nagy

946
00:41:42,780 --> 00:41:44,210
tömb, vagy egy nagy láncolt lista?

947
00:41:44,210 --> 00:41:47,010
És ne tegyenek CS sokkal nehezebb
mint amilyennek lennie kellene?

948
00:41:47,010 --> 00:41:49,600

949
00:41:49,600 --> 00:41:53,190
Mi vonzó ebben, még
bár karcos ki?

950
00:41:53,190 --> 00:41:54,930
>> DIÁK: [hangtalan].

951
00:41:54,930 --> 00:41:57,040
>> SPEAKER 1: Inszerciók nem?

952
00:41:57,040 --> 00:41:58,140
Drága többé.

953
00:41:58,140 --> 00:42:03,390
Így beszúrások potenciálisan még mindig
állandó idő, akkor is, ha az adatok

954
00:42:03,390 --> 00:42:07,910
szerkezet úgy néz ki, mint ez, egy sor
mutatók, amelyek mindegyike mutat

955
00:42:07,910 --> 00:42:09,550
potenciálisan láncolt lista.

956
00:42:09,550 --> 00:42:15,220
Hogyan lehetne elérni állandó
idő beillesztése a nevek?

957
00:42:15,220 --> 00:42:16,280
Dobd az első, ugye?

958
00:42:16,280 --> 00:42:19,290
>> Ha áldozatot design gól
korábban, ahol szerettünk volna, hogy

959
00:42:19,290 --> 00:42:22,650
mindenki nevét, például a válogatott,
vagy az összes számot a színpadon sorrendje,

960
00:42:22,650 --> 00:42:25,020
Feltételezzük, hogy van egy
rendezetlen láncolt lista.

961
00:42:25,020 --> 00:42:29,960
Ez csak a költségek számunkra egy vagy két lépésben,
mint abban az esetben, Ben és Brian

962
00:42:29,960 --> 00:42:32,750
korábban, hogy helyezzen be egy elemet a
a lista elején.

963
00:42:32,750 --> 00:42:36,090
Tehát, ha nem érdekel szétválogatja
A kezdődő nevek A vagy az összes

964
00:42:36,090 --> 00:42:39,660
A kezdődő nevek B, még mindig
érdekében állandó idő behelyezés.

965
00:42:39,660 --> 00:42:43,900
Most felnézett Alice vagy Bob vagy név
általában még mit?

966
00:42:43,900 --> 00:42:48,100
Ez elég nagy O n osztva 26, a
Ideális esetben, ha mindenki egységesen

967
00:42:48,100 --> 00:42:51,190
elosztott, ahol van annyi A.
mint ahány Z, ami valószínűleg

968
00:42:51,190 --> 00:42:52,220
irreális.

969
00:42:52,220 --> 00:42:53,880
De ez még mindig lineáris.

970
00:42:53,880 --> 00:42:57,120
>> De itt, mi jön vissza a pont
aszimptotikus jelölés, hogy

971
00:42:57,120 --> 00:42:58,600
elméletileg igaz.

972
00:42:58,600 --> 00:43:02,960
De a valóságban, ha azt állítom, hogy
a program nem valami 26-szer

973
00:43:02,960 --> 00:43:06,210
gyorsabb, mint a tiéd, amelynek programjában
fogsz, hogy inkább a?

974
00:43:06,210 --> 00:43:09,660
Tiéd, vagy az enyém, ami
26-szer gyorsabb?

975
00:43:09,660 --> 00:43:14,320
Reálisan a személy, akinek a 26
szer gyorsabb, még ha elméletileg

976
00:43:14,320 --> 00:43:18,790
az algoritmusok futnak ugyanabban
aszimptotikus futási ideje.

977
00:43:18,790 --> 00:43:20,940
>> Hadd javasolni egy másik
megoldás összesen.

978
00:43:20,940 --> 00:43:24,380
És ha ez nem fúj a fejedben,
kifutunk az adatszerkezeteket.

979
00:43:24,380 --> 00:43:27,420
Szóval ez az a Trie -

980
00:43:27,420 --> 00:43:28,520
milyen hülye név.

981
00:43:28,520 --> 00:43:32,880
Jön a lekérdezések, és a szó
van írva Trie t-r-i-e, mert az

982
00:43:32,880 --> 00:43:34,450
Természetesen visszakeresés hangzik Trie.

983
00:43:34,450 --> 00:43:36,580
De ez a történelem
a szó Trie.

984
00:43:36,580 --> 00:43:40,980
>> Tehát egy Trie valóban valamilyen fa,
és ez is egy játék a szó.

985
00:43:40,980 --> 00:43:46,330
És annak ellenére, hogy nem igazán látom
ezzel a megjelenítés, a Trie egy

986
00:43:46,330 --> 00:43:50,790
fa struktúrájú, mint a családfa
egyik őse a tetején, és még sok

987
00:43:50,790 --> 00:43:54,530
Az unokák és dédunokák
a levelek alján.

988
00:43:54,530 --> 00:43:58,100
De minden csomópont egy Trie egy tömb.

989
00:43:58,100 --> 00:44:00,680
És ez egy sor - és gyerünk
leegyszerűsíti egy pillanatra - ez egy

990
00:44:00,680 --> 00:44:04,600
tömb, ebben az esetben, a méret 26, ahol a
minden csomópont ismét tömb mérete

991
00:44:04,600 --> 00:44:09,000
26, ahol a nulladik eleme, hogy
Egy tömb képvisel, és az utolsó

992
00:44:09,000 --> 00:44:11,810
elem minden ilyen
array képvisel Z.

993
00:44:11,810 --> 00:44:15,520
>> Tehát azt javaslom tehát, hogy ezek az adatok
szerkezet, úgynevezett Trie, lehet

994
00:44:15,520 --> 00:44:17,600
is használják tárolására szavakat.

995
00:44:17,600 --> 00:44:21,740
Láttunk egy perce, hogy hogyan tudnánk tárolni
szavakkal, vagy ebben az esetben nevek, és mi

996
00:44:21,740 --> 00:44:25,440
korábban láttuk, hogyan lehet tárolni számokat,
de ha arra összpontosítunk nevű vagy húrok

997
00:44:25,440 --> 00:44:27,460
itt, észre, mi az érdekes.

998
00:44:27,460 --> 00:44:32,210
Azt állítom, hogy a név Maxwell
belsejében ez adatstruktúra.

999
00:44:32,210 --> 00:44:33,730
Hol látod Maxwell?

1000
00:44:33,730 --> 00:44:35,140
>> DIÁK: [hangtalan].

1001
00:44:35,140 --> 00:44:36,240
>> SPEAKER 1: a bal oldalon.

1002
00:44:36,240 --> 00:44:39,910
Szóval, mi az érdekes az ezen adatok
struktúra nem tárolja a

1003
00:44:39,910 --> 00:44:46,200
húr M-A-X-W-E-L-L backslash zérus, minden
folyamatosak, mit csinál helyette

1004
00:44:46,200 --> 00:44:46,890
követi.

1005
00:44:46,890 --> 00:44:50,510
Ha ez egy Trie mint adatszerkezet,
Minden amelynek csomópont ismét egy tömb,

1006
00:44:50,510 --> 00:44:54,650
és szeretné tárolni Maxwell, először
index, így a gyökér csomópontot, így

1007
00:44:54,650 --> 00:44:57,810
beszélni, a legfelső csomópont,
a helyszínen M, igaz, így

1008
00:44:57,810 --> 00:44:59,160
nagyjából a közepén.

1009
00:44:59,160 --> 00:45:03,740
Aztán onnan, kövesse a
mutató egy gyermek csomópontok, hogy úgy mondjam.

1010
00:45:03,740 --> 00:45:06,150
Így a családfa értelemben
kövesse lefelé.

1011
00:45:06,150 --> 00:45:09,030
És, hogy a vezető, hogy egy másik csomópont
a bal oldalon van, ami

1012
00:45:09,030 --> 00:45:10,540
csak egy tömb.

1013
00:45:10,540 --> 00:45:14,710
>> És aztán, ha szeretné tárolni Maxwell,
megtalálja a mutató, amely képviseli

1014
00:45:14,710 --> 00:45:16,430
A, amely az ezt itt.

1015
00:45:16,430 --> 00:45:17,840
Akkor menj a következő csomópontra.

1016
00:45:17,840 --> 00:45:20,100
És vegyük észre - ez az, amiért a kép
egy kicsit megtévesztő -

1017
00:45:20,100 --> 00:45:21,990
ez a csomópont meg szuper apró.

1018
00:45:21,990 --> 00:45:26,050
De ahhoz, hogy a megfelelő e jelentése Y és Z.
Ez csak a szerző a csonka

1019
00:45:26,050 --> 00:45:27,630
képet úgy, hogy valójában
látni a dolgokat.

1020
00:45:27,630 --> 00:45:30,400
Egyébként ezt a képet
lenne rendkívül széles.

1021
00:45:30,400 --> 00:45:36,180
Tehát most már index a helyre X, akkor
W, E, majd L, majd L. Akkor mi

1022
00:45:36,180 --> 00:45:37,380
a kíváncsiság?

1023
00:45:37,380 --> 00:45:41,250
>> Nos, ha már ezt a fajta új
hogy, hogyan kell tárolni a string a

1024
00:45:41,250 --> 00:45:44,500
adatstruktúra, még mindig szükség van, hogy
lényegében ellenőrizze le az adatok

1025
00:45:44,500 --> 00:45:47,250
szerkezet egy szót itt ér véget.

1026
00:45:47,250 --> 00:45:50,830
Más szóval, minden egyes ilyen csomópontok
valahogy meg kell emlékezni, hogy mi

1027
00:45:50,830 --> 00:45:53,500
tulajdonképpen követi az összes ilyen mutatók
és így egy kicsit

1028
00:45:53,500 --> 00:45:58,370
morzsát alján itt ezen
szerkezet, hogy jelezze M-A-X-W-E-L-L

1029
00:45:58,370 --> 00:46:00,230
sőt ez az adat struktúrában.

1030
00:46:00,230 --> 00:46:02,040
>> Így lehet, hogy ezt a következő.

1031
00:46:02,040 --> 00:46:06,810
Minden csomópont a képen már csak
látta az egyik, egy sor mérete 27.

1032
00:46:06,810 --> 00:46:10,550
És ez most 27, mert o meg hat,
akkor tényleg kapsz egy aposztróf,

1033
00:46:10,550 --> 00:46:13,590
így lehet nevek, mint O'Reilly
és mások aposztróf.

1034
00:46:13,590 --> 00:46:14,820
De ugyanezt a gondolatot.

1035
00:46:14,820 --> 00:46:17,710
Minden egyes ilyen elemek
array pont egy struct

1036
00:46:17,710 --> 00:46:19,320
csomópont, így csak egy csomópont.

1037
00:46:19,320 --> 00:46:21,430
Tehát ez nagyon emlékeztet
a mi kapcsolt lista.

1038
00:46:21,430 --> 00:46:24,550
>> És akkor van egy logikai, amit majd
hívás szó, ami csak lesz

1039
00:46:24,550 --> 00:46:29,120
igaz, ha a szó véget ér ezen a
levél a fában.

1040
00:46:29,120 --> 00:46:32,870
Hatékonyan képviseli a kis
háromszög láttunk egy perce.

1041
00:46:32,870 --> 00:46:37,190
Tehát, ha egy szót ér véget, hogy a csomópont
fa, ez a szó a területen lesz igaz,

1042
00:46:37,190 --> 00:46:41,990
amely fogalmilag ki ellenőrzi, vagy
mi ez a rajz háromszög, igen ott

1043
00:46:41,990 --> 00:46:44,080
szó itt.

1044
00:46:44,080 --> 00:46:45,120
>> Tehát ez egy Trie.

1045
00:46:45,120 --> 00:46:48,540
És most az a kérdés, hogy mi
az a működési idő?

1046
00:46:48,540 --> 00:46:49,930
Ez nagy O n?

1047
00:46:49,930 --> 00:46:51,410
Van valami más?

1048
00:46:51,410 --> 00:46:57,330
Nos, ha még n nevek az adatok
szerkezet, Maxwell, hogy csak az egyik

1049
00:46:57,330 --> 00:47:02,330
nekik, mi a futási ideje
behelyezése vagy találni Maxwell?

1050
00:47:02,330 --> 00:47:06,230

1051
00:47:06,230 --> 00:47:09,050
Mi a működési idő
beillesztése Maxwell?

1052
00:47:09,050 --> 00:47:11,740
Ha van n más nevek
már az asztalra?

1053
00:47:11,740 --> 00:47:12,507
Igen?

1054
00:47:12,507 --> 00:47:15,429
>> DIÁK: [hangtalan].

1055
00:47:15,429 --> 00:47:17,550
>> SPEAKER 1: Igen, ez a hosszúság
a név, ugye?

1056
00:47:17,550 --> 00:47:24,420
Tehát a-M-X-W-E-L-l, így úgy érzi, mint ez
algoritmus nagy O hét.

1057
00:47:24,420 --> 00:47:26,580
Most, természetesen, a név
hossza változó.

1058
00:47:26,580 --> 00:47:27,380
Lehet, hogy egy rövid nevet.

1059
00:47:27,380 --> 00:47:28,600
Lehet, hogy ez egy hosszabb nevet.

1060
00:47:28,600 --> 00:47:33,390
De mi a legfontosabb az, hogy
ez egy állandó szám.

1061
00:47:33,390 --> 00:47:36,810
És lehet, hogy nem is állandó,
De Isten, ha reálisan, a

1062
00:47:36,810 --> 00:47:41,570
szótár, ott valószínűleg néhány határ
A betűk száma a

1063
00:47:41,570 --> 00:47:43,820
személy nevét az adott országban.

1064
00:47:43,820 --> 00:47:46,940
>> És így feltételezhetjük, hogy
értéke egy konstans.

1065
00:47:46,940 --> 00:47:47,750
Nem tudom, mi az.

1066
00:47:47,750 --> 00:47:50,440
Ez valószínűleg nagyobb, mint
azt hiszem, ez az.

1067
00:47:50,440 --> 00:47:52,720
Mert mindig van néhány sarok
esetében egy őrült hosszú név.

1068
00:47:52,720 --> 00:47:56,360
Így nevezzük k, de ez még mindig egy
állandó feltehetően, mert minden

1069
00:47:56,360 --> 00:48:00,190
név a világon, legalábbis egy
adott országban, hogy a hosszú vagy

1070
00:48:00,190 --> 00:48:01,780
rövidebb, így állandó.

1071
00:48:01,780 --> 00:48:04,490
De amikor már mondott valamit, nagy
O konstans érték, mi az

1072
00:48:04,490 --> 00:48:07,760
tényleg megfelel?

1073
00:48:07,760 --> 00:48:10,420
Ez tényleg ugyanaz
azt mondta konstans id.

1074
00:48:10,420 --> 00:48:11,530
>> Most már olyan csalás, nem?

1075
00:48:11,530 --> 00:48:15,340
Mi olyan kihasználva néhány elmélet
itt, azt mondani, hogy jó, sorrendje k

1076
00:48:15,340 --> 00:48:17,450
valójában csak annak az egy,
és ez állandó időben.

1077
00:48:17,450 --> 00:48:18,200
De ez tényleg az.

1078
00:48:18,200 --> 00:48:22,550
Mivel a kulcs itt az, hogy betekintést
ha még n neveket már a

1079
00:48:22,550 --> 00:48:26,010
adatstruktúra és betét Maxwell,
az az összeg, időt vesz igénybe, hogy

1080
00:48:26,010 --> 00:48:29,530
be Maxwell egyáltalán érintett
hogy milyen sokan

1081
00:48:29,530 --> 00:48:31,100
vannak az adatstruktúra?

1082
00:48:31,100 --> 00:48:31,670
Nem úgy tűnik, hogy.

1083
00:48:31,670 --> 00:48:36,280
Ha lenne egy milliárd több elemet erre
Trie, majd helyezze Maxwell, a

1084
00:48:36,280 --> 00:48:38,650
ő egyáltalán érinti?

1085
00:48:38,650 --> 00:48:39,050
Nem.

1086
00:48:39,050 --> 00:48:42,950
És ez semmihez sem a nap adatok
struktúrák láttunk eddig, ahol a

1087
00:48:42,950 --> 00:48:46,820
futási idejét az algoritmus
teljesen független, hogy mennyi

1088
00:48:46,820 --> 00:48:51,430
cucc, vagy még nincs
az, hogy az adatok szerkezetét.

1089
00:48:51,430 --> 00:48:54,650
>> És így ezzel nyújt Önnek most egy
lehetőséget p szett hat, amely

1090
00:48:54,650 --> 00:48:58,310
Ismét járnak végrehajtási saját
helyesírás-ellenőrző, olvasás 150000

1091
00:48:58,310 --> 00:49:01,050
szóval, hogyan lehet a legjobban tárolni, hogy
nem feltétlenül nyilvánvaló.

1092
00:49:01,050 --> 00:49:04,030
És bár én törekedtem megtalálni
a Szent Grál, én nem

1093
00:49:04,030 --> 00:49:05,330
azt állítják, hogy a Trie van.

1094
00:49:05,330 --> 00:49:09,810
Tény, hogy a hash tábla lehet nagyon jól
bizonyítani, hogy sokkal hatékonyabb.

1095
00:49:09,810 --> 00:49:10,830
De ezek csak -

1096
00:49:10,830 --> 00:49:14,620
ez csak egy a tervezési döntések
akkor meg kell tenni.

1097
00:49:14,620 --> 00:49:18,920
>> De a záró vegyük 50, vagy úgy
másodperc, hogy egy kandikál, mi van

1098
00:49:18,920 --> 00:49:22,190
előre, a jövő héten, és azon túl is átmeneti
ebből a parancssorból

1099
00:49:22,190 --> 00:49:26,220
világ, ha a C programok dolgokat web
alapú és nyelvek, mint a PHP és a

1100
00:49:26,220 --> 00:49:30,350
JavaScript és az interneten is,
protokollokat, mint a HTTP, amely akkor már

1101
00:49:30,350 --> 00:49:32,870
magától értetődőnek évek
most, és gépelt legtöbb minden

1102
00:49:32,870 --> 00:49:34,440
nap, talán, vagy látott.

1103
00:49:34,440 --> 00:49:37,420
És kezdjük, hogy húzza vissza a
réteg, ami az interneten.

1104
00:49:37,420 --> 00:49:40,650
És mi az a kód, amely
alapja a mai eszközök.

1105
00:49:40,650 --> 00:49:43,230
Így 50 másodperc a teaser itt.

1106
00:49:43,230 --> 00:49:46,570
Adok Warriors a Net.

1107
00:49:46,570 --> 00:49:51,370
>> [VIDEÓ LEJÁTSZÁS]

1108
00:49:51,370 --> 00:49:56,764
>> -Jött egy üzenet.

1109
00:49:56,764 --> 00:50:00,687
A protokoll minden saját.

1110
00:50:00,687 --> 00:50:13,370

1111
00:50:13,370 --> 00:50:19,780
Azért jött, hogy a világ kegyetlen tűzfalak,
nemtörődöm routerek, és a veszélyek sokkal

1112
00:50:19,780 --> 00:50:22,600
rosszabb, mint a halál.

1113
00:50:22,600 --> 00:50:23,590
Ő gyors.

1114
00:50:23,590 --> 00:50:25,300
Ő erős.

1115
00:50:25,300 --> 00:50:27,700
Ő TCPIP.

1116
00:50:27,700 --> 00:50:30,420
És van a címét.

1117
00:50:30,420 --> 00:50:32,920

1118
00:50:32,920 --> 00:50:34,590
Warriors a Net.

1119
00:50:34,590 --> 00:50:35,290
>> [END VIDEÓ LEJÁTSZÁS]

1120
00:50:35,290 --> 00:50:38,070
>> SPEAKER 1: Így az internet
kell dolgozni a jövő héten.

1121
00:50:38,070 --> 00:50:40,406