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

2
00:00:11,860 --> 00:00:13,120
>> SPEAKER 1: V redu, tako da smo nazaj.

3
00:00:13,120 --> 00:00:14,480
Dobrodošli na CS50.

4
00:00:14,480 --> 00:00:16,510
To je konec sedem teden.

5
00:00:16,510 --> 00:00:20,200
Tako opozarjajo, da je zadnji čas, smo začeli
gledaš nekoliko bolj prefinjene

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

7
00:00:21,100 --> 00:00:25,110
Ker do zdaj smo imeli res
na razpolago je to polje.

8
00:00:25,110 --> 00:00:29,340
>> Toda preden bomo, da ne zavržemo niz
vse to zanimivo, kar v resnici je

9
00:00:29,340 --> 00:00:33,570
dejansko je, kaj so nekateri
pluse te preproste podatkov

10
00:00:33,570 --> 00:00:34,560
Struktura doslej?

11
00:00:34,560 --> 00:00:36,110
Kaj je dobro na to?

12
00:00:36,110 --> 00:00:39,450
Kolikor smo videli?

13
00:00:39,450 --> 00:00:42,540
Kaj imaš?

14
00:00:42,540 --> 00:00:44,028
Nič.

15
00:00:44,028 --> 00:00:45,020
>> ŠTUDENT: [neslišno].

16
00:00:45,020 --> 00:00:45,395
>> SPEAKER 1: Kaj je to?

17
00:00:45,395 --> 00:00:46,410
>> ŠTUDENT: [neslišno].

18
00:00:46,410 --> 00:00:47,000
>> SPEAKER 1: Fiksna velikost.

19
00:00:47,000 --> 00:00:51,260
OK, zakaj je fiksna velikost dobra, čeprav?

20
00:00:51,260 --> 00:00:53,180
>> ŠTUDENT: [neslišno].

21
00:00:53,180 --> 00:00:56,240
>> SPEAKER 1: OK, tako da je učinkovit pri
Občutek, ki ga lahko namenijo

22
00:00:56,240 --> 00:01:00,070
fiksna količina prostora, ki upajmo
Ravno toliko,

23
00:01:00,070 --> 00:01:01,180
prostora, kot želite.

24
00:01:01,180 --> 00:01:02,720
Tako da bi se lahko popolnoma plus.

25
00:01:02,720 --> 00:01:06,530
>> Kaj je še gor stran array?

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

27
00:01:07,610 --> 00:01:08,750
>> ŠTUDENT: [neslišno].

28
00:01:08,750 --> 00:01:09,550
>> SPEAKER 1: Vsi - žal?

29
00:01:09,550 --> 00:01:11,270
>> ŠTUDENT: [neslišno].

30
00:01:11,270 --> 00:01:13,620
>> SPEAKER 1: Vsa polja v pomnilniku
ali drug poleg drugega.

31
00:01:13,620 --> 00:01:15,220
In to je koristno - zakaj?

32
00:01:15,220 --> 00:01:15,970
To je čisto res.

33
00:01:15,970 --> 00:01:18,611
Toda, kako izkoristiti to resnico?

34
00:01:18,611 --> 00:01:21,500
>> ŠTUDENT: [neslišno].

35
00:01:21,500 --> 00:01:24,490
>> SPEAKER 1: Točno tako, lahko spremljate
kjer je vse le s poznavanjem

36
00:01:24,490 --> 00:01:28,560
en naslov, in sicer naslov
prvi bajt ta kos pomnilnika.

37
00:01:28,560 --> 00:01:30,420
Ali v primeru niza,
naslov prve

38
00:01:30,420 --> 00:01:31,460
char v tem nizu.

39
00:01:31,460 --> 00:01:33,330
In od tam lahko najdemo
konca niza.

40
00:01:33,330 --> 00:01:35,710
Mi lahko našli drugega elementa, na
Tretji element, in tako naprej.

41
00:01:35,710 --> 00:01:38,740
>> In tako fancy način opisovanja, da
značilnost je, da nam daje nizi

42
00:01:38,740 --> 00:01:40,020
random access.

43
00:01:40,020 --> 00:01:44,330
Samo z uporabo kvadratni oklepaj
Zapis in številko, lahko skočite na

44
00:01:44,330 --> 00:01:48,070
poseben element v matriki
v enakem času, big O

45
00:01:48,070 --> 00:01:49,810
enega, tako rekoč.

46
00:01:49,810 --> 00:01:51,080
>> Vendar je bilo nekaj slabosti.

47
00:01:51,080 --> 00:01:53,110
Kaj matrika ne naredi zelo enostavno?

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

49
00:01:55,810 --> 00:01:57,170
Kaj ni dobro?

50
00:01:57,170 --> 00:01:58,810
>> ŠTUDENT: [neslišno].

51
00:01:58,810 --> 00:01:59,860
>> SPEAKER 1: Kaj je to?

52
00:01:59,860 --> 00:02:00,530
>> ŠTUDENT: [neslišno].

53
00:02:00,530 --> 00:02:01,460
>> SPEAKER 1: Širitev po velikosti.

54
00:02:01,460 --> 00:02:04,800
Torej Slabosti matrike so
ravno nasprotno od tega, kar

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

56
00:02:05,540 --> 00:02:07,610
Torej, ena od slabosti je
da je fiksno velikost.

57
00:02:07,610 --> 00:02:09,400
Torej vam ne morem raste.

58
00:02:09,400 --> 00:02:13,510
Lahko prerazporediti večji kos
pomnilnik, nato pa stare elemente

59
00:02:13,510 --> 00:02:14,460
v nov niz.

60
00:02:14,460 --> 00:02:18,060
In potem brezplačno stara matrika, za
primer z uporabo malloc ali podobno

61
00:02:18,060 --> 00:02:21,180
Funkcija se imenuje realloc, ki
prerazporeja spomin.

62
00:02:21,180 --> 00:02:25,490
>> Realloc, kot prahi, poskuša, da vam
pomnilnika, ki je poleg niza

63
00:02:25,490 --> 00:02:26,610
da že imate.

64
00:02:26,610 --> 00:02:28,740
Morda pa bi premakniti stvari
okoli celoti.

65
00:02:28,740 --> 00:02:30,710
Ampak na kratko, da je drago, kajne?

66
00:02:30,710 --> 00:02:33,440
Ker če imate kos pomnilnika
te velikosti, ampak res želim eno

67
00:02:33,440 --> 00:02:36,710
te velikosti, in če želite ohraniti
prvotnih elementov, ki ste jih

68
00:02:36,710 --> 00:02:40,510
približno linearni čas, postopek kopiranja
da se mora zgoditi od

69
00:02:40,510 --> 00:02:41,900
stara array nova.

70
00:02:41,900 --> 00:02:44,630
In realnost sprašuje deluje
znova sistema in

71
00:02:44,630 --> 00:02:48,340
Še enkrat lahko začnete velike kose pomnilnika
stalo nekaj časa pa tudi.

72
00:02:48,340 --> 00:02:52,250
Torej je tako blagoslov in prekletstvo v
prikrivajo, dejstvo, da ti nizi

73
00:02:52,250 --> 00:02:53,860
so fiksne velikosti.

74
00:02:53,860 --> 00:02:56,790
Ampak, če bomo namesto tega uvesti nekaj
kot je ta, ki smo poklicani povezano

75
00:02:56,790 --> 00:03:00,580
Seznam smo dobili nekaj upsides in
nekaj slabosti tudi tukaj.

76
00:03:00,580 --> 00:03:05,780
>> Tako povezani seznam je preprosto podatkov
struktura sestavljena iz konstrukti C v tem

77
00:03:05,780 --> 00:03:09,850
Primer, kjer struct, odpoklic, je samo
Posoda za en ali več specifičnih

78
00:03:09,850 --> 00:03:11,100
Vrste spremenljivk.

79
00:03:11,100 --> 00:03:16,110
V tem primeru, kaj storiti, podatkovne tipe
Zdi se, da znotraj struct da

80
00:03:16,110 --> 00:03:17,600
Zadnjič, ko smo poklicali vozlišče?

81
00:03:17,600 --> 00:03:19,380
Vsaka od teh pravokotnika je vozlišče.

82
00:03:19,380 --> 00:03:22,660
In vsak od majhnih pravokotnikov
notri je podatkovni tip.

83
00:03:22,660 --> 00:03:25,300
Katere vrste smo rekli
so bili v ponedeljek?

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

85
00:03:26,478 --> 00:03:27,870
>> ŠTUDENT: [neslišno].

86
00:03:27,870 --> 00:03:30,721
>> SPEAKER 1: spremenljiva in kazalec, ali
natančneje, int, za n

87
00:03:30,721 --> 00:03:32,180
in kazalec na dnu.

88
00:03:32,180 --> 00:03:35,360
Oba tistih zgodi, da se 32 bitov, pri
Vsaj na računalniku, kot je ta CS50

89
00:03:35,360 --> 00:03:37,980
Aparata in tako oni
sestavljen tudi v velikosti.

90
00:03:37,980 --> 00:03:42,260
>> Torej, kaj uporabljate kazalec
čeprav navidezno?

91
00:03:42,260 --> 00:03:47,690
Zakaj dodati ta puščico zdaj, ko so bili nizi
tako lep in čist in preprost?

92
00:03:47,690 --> 00:03:50,460
Kaj je kazalec počne za
nas v vsakem od teh vozlišč?

93
00:03:50,460 --> 00:03:52,160
>> ŠTUDENT: [neslišno].

94
00:03:52,160 --> 00:03:52,465
>> SPEAKER 1: Točno tako.

95
00:03:52,465 --> 00:03:54,120
To vam pove, kje je
Naslednji ena.

96
00:03:54,120 --> 00:03:57,350
Tako sem nekako uporabiti analogijo
uporabljate nit nekako

97
00:03:57,350 --> 00:03:59,180
nit teh vozlišč skupaj.

98
00:03:59,180 --> 00:04:01,760
In to je točno tisto, kar počnemo s
kazalci, saj je vsaka od teh

99
00:04:01,760 --> 00:04:06,360
kose pomnilnika lahko ali pa tudi ne
nedeljive, back to back to back

100
00:04:06,360 --> 00:04:09,500
Notranjost RAM-a, ker vsakič, ko
klic malloc rekel, daj mi dovolj

101
00:04:09,500 --> 00:04:12,510
bajte za novo vozlišče, bi bilo
tukaj ali pa bi bilo tukaj.

102
00:04:12,510 --> 00:04:13,120
Morda bi bilo tukaj.

103
00:04:13,120 --> 00:04:13,730
Morda bi bilo tukaj.

104
00:04:13,730 --> 00:04:14,640
Enostavno ne vem.

105
00:04:14,640 --> 00:04:17,880
>> Vendar z uporabo kazalcev v naslovih
ti vozlišča, lahko šiva jih boste

106
00:04:17,880 --> 00:04:22,370
skupaj na način, ki je videti vizualno
kot seznam, tudi če so te stvari

107
00:04:22,370 --> 00:04:26,770
Vse širijo po vsej vaši enega ali
tvoji dve ali vaše štiri gigabajte RAM

108
00:04:26,770 --> 00:04:28,760
znotraj svojega računalnika.

109
00:04:28,760 --> 00:04:33,230
>> Tako slaba, potem pa,
povezani seznam, kaj?

110
00:04:33,230 --> 00:04:34,670
Kakšna je cena smo
očitno plačuje?

111
00:04:34,670 --> 00:04:36,010
>> ŠTUDENT: [neslišno].

112
00:04:36,010 --> 00:04:36,920
>> SPEAKER 1: Več prostora, kajne?

113
00:04:36,920 --> 00:04:39,340
Smo v tem primeru podvojila količino
prostora, ker smo šli

114
00:04:39,340 --> 00:04:43,500
od 32 bitov za vsako vozlišče, za vsako
int, tako da sedaj 64 bitov, ker moramo

115
00:04:43,500 --> 00:04:45,050
vodi okoli kazalec kot dobro.

116
00:04:45,050 --> 00:04:48,860
Boste dobili večjo učinkovitost, če je vaša struct
je večji od te preproste stvari.

117
00:04:48,860 --> 00:04:52,020
Če ste dejansko imajo študenta v notranjosti
od katerih je nekaj vrvi

118
00:04:52,020 --> 00:04:55,430
Ime in hiša, morda številka,
morda nekaj drugih področjih v celoti.

119
00:04:55,430 --> 00:04:59,000
>> Torej, če imate dovolj velik struct,
potem pa stroški kazalca je

120
00:04:59,000 --> 00:05:00,010
ni tak big deal.

121
00:05:00,010 --> 00:05:03,570
To je malo kota primeru, da
bomo shranjevanje kot preprosta primitivna

122
00:05:03,570 --> 00:05:04,760
Notranjost povezane seznama.

123
00:05:04,760 --> 00:05:05,790
Bistvo pa je enaka.

124
00:05:05,790 --> 00:05:08,230
Ste zagotovo porabi več
spomin, ampak ste dobili

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

126
00:05:08,990 --> 00:05:12,280
Ker zdaj, če želim dodati element
na začetku tega seznama

127
00:05:12,280 --> 00:05:14,340
Imam dodeliti novo vozlišče.

128
00:05:14,340 --> 00:05:17,180
In moram samo posodobiti tistih
Puščice nekako po samo premikanje

129
00:05:17,180 --> 00:05:17,980
Nekaj ​​nasvetov okoli.

130
00:05:17,980 --> 00:05:20,580
>> Če hočem nekaj vstavili v
Sredi seznama, nimam za

131
00:05:20,580 --> 00:05:24,410
potisnite vse prahi, kot smo to storili v
preteklih tednov z našim prostovoljcem, ki

132
00:05:24,410 --> 00:05:25,700
predstavlja matriko.

133
00:05:25,700 --> 00:05:29,470
Jaz lahko samo dodeli novo vozlišče in
potem pa samo točko puščice v

134
00:05:29,470 --> 00:05:32,290
različne smeri, saj ne
morajo ostati v dejanski

135
00:05:32,290 --> 00:05:35,670
spomin res črta, kot sem pripraviti
je tu na zaslonu.

136
00:05:35,670 --> 00:05:38,400
>> In nenazadnje potem, če želite vstaviti
Nekaj ​​konec seznama, je

137
00:05:38,400 --> 00:05:39,210
še lažje.

138
00:05:39,210 --> 00:05:43,320
To je neke vrste samovoljno zapisu
ampak 34 je kazalec, ugibati.

139
00:05:43,320 --> 00:05:46,710
Kakšna je vrednost njenega kazalca najbolj
verjetno sestavljen nekako kot stari

140
00:05:46,710 --> 00:05:47,700
Šola antena tam?

141
00:05:47,700 --> 00:05:48,920
>> ŠTUDENT: [neslišno].

142
00:05:48,920 --> 00:05:49,900
>> SPEAKER 1: Verjetno je nična.

143
00:05:49,900 --> 00:05:52,710
In res, da je ena avtorja
zastopanje nična.

144
00:05:52,710 --> 00:05:56,310
In to je nična, ker ste popolnoma
morali vedeti, kje konec povezano

145
00:05:56,310 --> 00:06:00,050
Seznam je, da ne boste obdržali naslednje in
sledi in po puščici

146
00:06:00,050 --> 00:06:01,170
do neke smeti vrednosti.

147
00:06:01,170 --> 00:06:06,230
Tako bodo null pomenilo, da ni
več vozlišč na desni strani številka 34,

148
00:06:06,230 --> 00:06:07,200
v tem primeru.

149
00:06:07,200 --> 00:06:10,270
>> Zato predlagamo, da se lahko izvajajo
To vozlišče v kodi.

150
00:06:10,270 --> 00:06:12,130
In smo videli te vrste
sintakse prej.

151
00:06:12,130 --> 00:06:15,090
Typedef samo opredeljuje novo vrsto za
nas, nam daje sinonim všeč

152
00:06:15,090 --> 00:06:17,100
niz je bil za char *.

153
00:06:17,100 --> 00:06:21,030
V tem primeru, se dogaja, da nam
skrajšan zapis, tako da struct vozlišče

154
00:06:21,030 --> 00:06:24,010
lahko namesto tega samo zapišemo kot
vozlišče, ki je veliko čistejši.

155
00:06:24,010 --> 00:06:25,360
To je veliko manj zgovorni.

156
00:06:25,360 --> 00:06:30,080
>> Znotraj vozlišča očitno int
imenujemo n, in nato struct vozlišče *

157
00:06:30,080 --> 00:06:34,670
kar pomeni natanko to, kar smo želeli
puščice pomeni, kazalec na drugo

158
00:06:34,670 --> 00:06:36,940
vozlišče točno isto vrsto podatkov.

159
00:06:36,940 --> 00:06:40,300
In predlagam, da bi morali izvajati
search funkcija, kot je ta, ki je na

160
00:06:40,300 --> 00:06:41,890
prvi pogled se morda zdi
malo zapleteno.

161
00:06:41,890 --> 00:06:43,330
Ampak kaj je to v kontekstu vidim.

162
00:06:43,330 --> 00:06:45,480
>> Naj grem več na napravi tukaj.

163
00:06:45,480 --> 00:06:48,460
Dovolite mi, da odprejo datoteko z imenom
Seznam nič pika h.

164
00:06:48,460 --> 00:06:53,950
In da vsebuje samo definicijo smo zajeli
Pravkar sem videla pred nekaj trenutki za te podatke

165
00:06:53,950 --> 00:06:55,390
Tip se imenuje vozlišče.

166
00:06:55,390 --> 00:06:57,350
Zato smo mu, da v dot h datoteki.

167
00:06:57,350 --> 00:07:01,430
>> In kot prahi, čeprav je to
Program, ki si nadeja je

168
00:07:01,430 --> 00:07:05,410
ni vse tako zapleteno, da je dejansko
Konvencija pri pisanju programa

169
00:07:05,410 --> 00:07:10,270
dal stvari, kot so podatkovne tipe, vleči
konstante včasih znotraj vašega

170
00:07:10,270 --> 00:07:13,210
header datoteko in ne nujno
vaša C datoteka, zagotovo, ko si

171
00:07:13,210 --> 00:07:17,370
Programi dobili večje in večje, tako da
veste, kje iskati tako za

172
00:07:17,370 --> 00:07:20,840
dokumentacijo, v nekaterih primerih, ali
za osnove, kot je ta, v

173
00:07:20,840 --> 00:07:22,360
opredelitev neke vrste.

174
00:07:22,360 --> 00:07:25,680
>> Če bi sedaj odprl seznam ničelno piko
c, opazil nekaj stvari.

175
00:07:25,680 --> 00:07:29,090
Vključuje nekaj header datoteke, večino
od katerih smo videli prej.

176
00:07:29,090 --> 00:07:31,980
Vključuje lastno glavo datoteke.

177
00:07:31,980 --> 00:07:35,200
>> In kot praha, zato da je dvojna
citati tukaj, v nasprotju s kotom

178
00:07:35,200 --> 00:07:38,340
oklepaja na liniji, ki
Bil sem tam izpostavil?

179
00:07:38,340 --> 00:07:39,180
>> ŠTUDENT: [neslišno].

180
00:07:39,180 --> 00:07:40,460
>> SPEAKER 1: Ja, tako da je lokalna datoteka.

181
00:07:40,460 --> 00:07:44,300
Torej, če je lokalna datoteka sami tukaj
na liniji 15, na primer, uporabite

182
00:07:44,300 --> 00:07:46,570
dvojne navednice namesto
od kotne oklepaje.

183
00:07:46,570 --> 00:07:48,270
>> Zdaj je to nekako zanimivo.

184
00:07:48,270 --> 00:07:51,830
Obvestilo, da sem razglasila svetovna
spremenljivka v tem programu na liniji 18

185
00:07:51,830 --> 00:07:55,910
imenovan, ideja pa je to
bo kazalec na prvi

186
00:07:55,910 --> 00:07:59,190
vozlišče v mojem povezanem seznamu, in sem
INITIALIZED na nič, ker sem

187
00:07:59,190 --> 00:08:02,310
ni dodeljena vsako dejansko
vozlišča samo še.

188
00:08:02,310 --> 00:08:07,570
>> Torej to pomeni, slikovno, kar smo
videli pred nekaj trenutki na sliki kot

189
00:08:07,570 --> 00:08:10,090
da kazalec na daleč
levo strani.

190
00:08:10,090 --> 00:08:12,260
Torej sedaj, da kazalec
nima puščico.

191
00:08:12,260 --> 00:08:14,590
Namesto tega je samo nična.

192
00:08:14,590 --> 00:08:17,880
Ampak to pomeni, kaj se bo
naslov Prvo dejansko

193
00:08:17,880 --> 00:08:19,480
vozlišče na tem seznamu.

194
00:08:19,480 --> 00:08:22,120
Tako sem izvajali, je svetovna
ker je, kot boste videli, vse to

195
00:08:22,120 --> 00:08:25,310
Program se v življenju je izvajala
povezani seznam za mene.

196
00:08:25,310 --> 00:08:27,050
>> Zdaj imam nekaj prototipov tukaj.

197
00:08:27,050 --> 00:08:31,190
Odločil sem se za izvajanje funkcij, kot so
brisanje, vstavljanje, iskanje in

198
00:08:31,190 --> 00:08:31,740
prečkanje -

199
00:08:31,740 --> 00:08:35,210
zadnja kot le sprehod čez
Seznam, tiskanje njene elemente.

200
00:08:35,210 --> 00:08:36,750
In sedaj tukaj je moja glavna rutina.

201
00:08:36,750 --> 00:08:39,890
In ne bomo porabili preveč časa
ti, ker je to neke vrste, upajmo

202
00:08:39,890 --> 00:08:41,780
star klobuk, ki ga zdaj.

203
00:08:41,780 --> 00:08:45,370
>> Jaz bom naredil naslednje,
, medtem ko uporabnik sodeluje.

204
00:08:45,370 --> 00:08:47,300
Torej eno, bom za tiskanje
iz tega menija.

205
00:08:47,300 --> 00:08:49,420
In sem ga kot formatiran
gladko, kot sem lahko.

206
00:08:49,420 --> 00:08:52,240
Če uporabnik vnese v enem, kar pomeni, da
hočejo nekaj izbrisati.

207
00:08:52,240 --> 00:08:54,560
Če uporabnik vnese v dvoje, kar pomeni, da
hočejo nekaj vstavili.

208
00:08:54,560 --> 00:08:55,930
In tako naprej.

209
00:08:55,930 --> 00:08:58,270
Bom nato pozval
nato za ukaz.

210
00:08:58,270 --> 00:08:59,300
In potem bom uporabila GetInt.

211
00:08:59,300 --> 00:09:02,790
>> Torej je to res preprosta menuing
vmesnik, kjer boste morali vnesti

212
00:09:02,790 --> 00:09:05,270
število razporejanja v enem
od teh ukazov.

213
00:09:05,270 --> 00:09:08,730
In zdaj imam lepo čisto stikalo
Izjava, da se dogaja, da vklopite

214
00:09:08,730 --> 00:09:10,090
karkoli uporabnik vtipka

215
00:09:10,090 --> 00:09:12,180
In če jih vnesli eno, bom
pokličite izbrisati in break.

216
00:09:12,180 --> 00:09:14,380
Če jih vnesli dva, bom
pokličite vstavite in break.

217
00:09:14,380 --> 00:09:16,490
>> In zdaj napove, sem dal vsak
teh na isti liniji.

218
00:09:16,490 --> 00:09:18,360
To je samo slogovna odločitev.

219
00:09:18,360 --> 00:09:20,210
Po navadi smo videli nekaj
kot je ta.

220
00:09:20,210 --> 00:09:23,260
Ampak tako sem se odločil, odkrito povedano, moj program
je bolj berljivo, saj

221
00:09:23,260 --> 00:09:25,980
je bilo le štiri primere, za
samo seznam, kot je ta.

222
00:09:25,980 --> 00:09:28,360
Povsem zakonito uporabo slogu.

223
00:09:28,360 --> 00:09:31,480
In bom naredil to tako dolgo, dokler
Uporabnik še ni natipkan nič, kar sem

224
00:09:31,480 --> 00:09:33,910
odločil, bo pomenilo, da želijo prenehati.

225
00:09:33,910 --> 00:09:36,630
>> Torej, zdaj opazil, kaj sem
boš naredil tukaj.

226
00:09:36,630 --> 00:09:38,650
Grem osvoboditi seznam očitno.

227
00:09:38,650 --> 00:09:40,230
Ampak več o tem čez nekaj trenutkov.

228
00:09:40,230 --> 00:09:41,640
Poglejmo najprej zagnati ta program.

229
00:09:41,640 --> 00:09:45,250
Naj bo večji terminal
okno, pika seznam poševnica 0.

230
00:09:45,250 --> 00:09:49,510
Jaz grem naprej in ga vstavite
tipkanje dva, več kot 50 let, in zdaj

231
00:09:49,510 --> 00:09:51,590
boste videli seznam je zdaj 50.

232
00:09:51,590 --> 00:09:53,380
In moj tekst samo pomika gor malo.

233
00:09:53,380 --> 00:09:55,940
Torej sedaj opazili, seznam vsebuje
Številka 50.

234
00:09:55,940 --> 00:09:58,220
>> Naredimo še en vložek, ki ga ob dveh.

235
00:09:58,220 --> 00:10:01,630
Kaj je tip v številu kot eno.

236
00:10:01,630 --> 00:10:03,940
Seznam je zdaj eden, ki mu sledi 50.

237
00:10:03,940 --> 00:10:06,020
Torej to je samo tekstovni prikaz
seznama.

238
00:10:06,020 --> 00:10:10,550
In kaj je vstaviti eno večjo številko, kot je
številko 42, ki je upajmo

239
00:10:10,550 --> 00:10:14,620
bo na koncu v sredini, saj
ta program v posamezne sorte je

240
00:10:14,620 --> 00:10:16,320
elementi, saj jim vložki.

241
00:10:16,320 --> 00:10:17,220
Torej tam jo imamo.

242
00:10:17,220 --> 00:10:20,730
Super preprost program, ki bi lahko
Popolnoma so uporabili matriko, ampak sem

243
00:10:20,730 --> 00:10:23,280
zgodi, da se z uporabo seznama povezano
samo zato, da sem lahko dinamično

244
00:10:23,280 --> 00:10:24,610
rastejo in se skrči.

245
00:10:24,610 --> 00:10:28,470
>> Torej, vzemimo si za iskanje, če sem
zaženete ukaz tri, hočem poiskati

246
00:10:28,470 --> 00:10:31,040
za, recimo, številko 43..

247
00:10:31,040 --> 00:10:34,190
In nič ni bilo očitno pokazala,
ker sem dobil nazaj nobenega odgovora.

248
00:10:34,190 --> 00:10:35,010
Torej, naredimo to še enkrat.

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

250
00:10:35,690 --> 00:10:39,520
Poiščimo 50, ali pa gre za iskanje
za 42, kar je lepo

251
00:10:39,520 --> 00:10:40,850
malo subtilen pomen.

252
00:10:40,850 --> 00:10:42,610
In sem našel smisel življenja tam.

253
00:10:42,610 --> 00:10:44,990
Številka 42, če ne veste,
sklic, ga Google.

254
00:10:44,990 --> 00:10:45,350
Vse je v redu.

255
00:10:45,350 --> 00:10:47,130
Torej, kaj je ta program naredil zame?

256
00:10:47,130 --> 00:10:50,660
To je samo dovoli mi, da tako vstaviti
daleč in iskanje elementov.

257
00:10:50,660 --> 00:10:53,650
>> Dajmo hitro naprej, nato pa se
to funkcijo smo pogledal

258
00:10:53,650 --> 00:10:55,360
v ponedeljek, kot teaser.

259
00:10:55,360 --> 00:10:59,620
Torej to funkcijo Trdim, išče
element na seznamu najprej

260
00:10:59,620 --> 00:11:03,830
ena, zaradi česar uporabnika in nato kliče
GetInt, da bi dobili dejanski int

261
00:11:03,830 --> 00:11:05,060
, ki ga želite poiskati.

262
00:11:05,060 --> 00:11:06,460
>> Potem to obvestilo.

263
00:11:06,460 --> 00:11:10,690
Grem, da ustvarite začasno spremenljivko
v skladu 188. imenovano kazalec -

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

265
00:11:11,270 --> 00:11:12,440
Lahko bi jo imenovali ničesar.

266
00:11:12,440 --> 00:11:16,140
In to je kazalec na vozlišče
saj sem rekel vozlišče * tam.

267
00:11:16,140 --> 00:11:19,900
In jaz sem inicializacijo, da je enaka
prvi, tako da sem dejansko imajo moja

268
00:11:19,900 --> 00:11:22,860
prst, tako rekoč na zelo
Prvi element seznama.

269
00:11:22,860 --> 00:11:27,460
Torej, če je moja desna roka tu PTR sem
kaže na isto stvar, ki je prvi

270
00:11:27,460 --> 00:11:28,670
pokrije.

271
00:11:28,670 --> 00:11:31,430
>> Torej, zdaj nazaj v kodi,
kaj se zgodi naslednje -

272
00:11:31,430 --> 00:11:35,070
To je skupna paradigma, ko ponavljanjem
nad strukturo kot

273
00:11:35,070 --> 00:11:35,970
povezani seznam.

274
00:11:35,970 --> 00:11:40,410
Jaz bom pa naredil naslednje
kazalec ni enaka Torej null medtem

275
00:11:40,410 --> 00:11:47,530
moj prst ne kaže na neki nična
vrednost, če kazalec puščica je n enak n.

276
00:11:47,530 --> 00:11:52,290
Bomo opazili, prvič, da je n tisto,
uporabnik vnesli v na GetInts poklical tukaj.

277
00:11:52,290 --> 00:11:54,280
>> In kazalec arrow n pomeni kaj?

278
00:11:54,280 --> 00:11:59,020
No, če se vrnemo na sliko tukaj,
če imam s prstom kaže na

279
00:11:59,020 --> 00:12:02,960
da najprej vozlišče, ki vsebuje devet, v
arrow bistvu pomeni, da gre za

280
00:12:02,960 --> 00:12:08,860
vozlišče in zgrabi vrednost na lokaciji n,
v tem primeru podatkovno polje imenovano n.

281
00:12:08,860 --> 00:12:14,120
>> Kot prahi - in smo videli to nekaj
tedni, ko je nekdo vprašal -

282
00:12:14,120 --> 00:12:18,840
Ta besedna zveza je nova, vendar pa ne
nam dajejo pooblastila, da

283
00:12:18,840 --> 00:12:20,040
ni že.

284
00:12:20,040 --> 00:12:25,325
Kakšna je bila ta izraz enakovreden uporabo
dot zapis in zvezda par

285
00:12:25,325 --> 00:12:29,490
tedni, ko smo olupljen nazaj
ta sloj malo prezgodaj?

286
00:12:29,490 --> 00:12:31,780
>> ŠTUDENT: [neslišno].

287
00:12:31,780 --> 00:12:38,880
>> SPEAKER 1: Točno tako, to je zvezda, in
potem je bil zvezda dot n, z

288
00:12:38,880 --> 00:12:41,930
oklepaje tukaj, ki je videti,
odkrito povedano, mislim, da je veliko

289
00:12:41,930 --> 00:12:43,320
bolj skrivnosten brati.

290
00:12:43,320 --> 00:12:46,270
Ampak zvezda kazalec, kot vedno,
sredstvo tja.

291
00:12:46,270 --> 00:12:49,090
In ko si enkrat tam, kaj podatki
Polje želite dostopati?

292
00:12:49,090 --> 00:12:52,730
No uporabljate dot zapis za dostop
Podatkovno polje konstrukti, in jaz

293
00:12:52,730 --> 00:12:54,140
posebej želimo n.

294
00:12:54,140 --> 00:12:56,240
>> Odkrito povedano, bi lahko dejali, to
je samo težje brati.

295
00:12:56,240 --> 00:12:58,080
To je težje, da se spomnimo, kjer
Ne Oklepaji iti,

296
00:12:58,080 --> 00:12:59,030
zvezda in vse to.

297
00:12:59,030 --> 00:13:02,150
Torej svet sprejel nekaj skladenjsko
sladkorja, tako rekoč.

298
00:13:02,150 --> 00:13:04,740
Samo seksi način rekel,
to ustreza, in

299
00:13:04,740 --> 00:13:05,970
morda bolj intuitivno.

300
00:13:05,970 --> 00:13:09,600
Če kazalec je namreč kazalec,
arrow zapis pomeni iti tja in ugotovili

301
00:13:09,600 --> 00:13:11,890
polje v tem primeru se imenuje n.

302
00:13:11,890 --> 00:13:13,660
>> Torej, če se mi zdi, da vidite, kaj počnem.

303
00:13:13,660 --> 00:13:17,430
Jaz preprosto natisniti, sem našel odstotka I,
priklopom na vrednost za to notr.

304
00:13:17,430 --> 00:13:20,730
Kličem spat za eno sekundo, samo da se
pavze stvari na zaslonu

305
00:13:20,730 --> 00:13:22,900
daje uporabniku drugi, da absorbira
kaj se je zgodilo.

306
00:13:22,900 --> 00:13:24,290
In potem sem prekinil.

307
00:13:24,290 --> 00:13:26,330
V nasprotnem primeru, kaj naj storim?

308
00:13:26,330 --> 00:13:30,960
Jaz posodobiti kazalec na enak
kazalec puščico.

309
00:13:30,960 --> 00:13:35,840
>> Torej, samo da bo jasno, to pomeni, da gredo
tam, z mojo staro šolo zapis.

310
00:13:35,840 --> 00:13:39,580
Torej, to samo pomeni, da gre za karkoli
si gledala, ki je v zelo

311
00:13:39,580 --> 00:13:43,660
Prvi primer je, da sem gledala
struct z devetimi v njem.

312
00:13:43,660 --> 00:13:44,510
Tako da sem se šla.

313
00:13:44,510 --> 00:13:47,880
In potem pika zapis pomeni,
dobili vrednost na naslednjo.

314
00:13:47,880 --> 00:13:50,470
>> Ampak vrednost, čeprav je ta pripravljen
kot ozek, je samo številka.

315
00:13:50,470 --> 00:13:51,720
To je številčna naslov.

316
00:13:51,720 --> 00:13:55,670
Torej je to ena vrstica kode, bodisi
napisan tako, bolj nejasna

317
00:13:55,670 --> 00:14:00,190
Tako ali tako, nekoliko
intuitiven način, samo pomeni, da se premaknete roko

318
00:14:00,190 --> 00:14:03,460
od prvega vozlišče naslednjega,
in nato naslednjič, nato

319
00:14:03,460 --> 00:14:05,320
Naslednji, in tako naprej.

320
00:14:05,320 --> 00:14:09,920
>> Tako da ne bo spuščala v drugi
izvedbe vstavljanje in brisanje

321
00:14:09,920 --> 00:14:14,030
in prečkanje, prva dva
ki so precej vključeni.

322
00:14:14,030 --> 00:14:17,010
In mislim, da je zelo enostavno priti
izgubljeni, ko to počne verbalno.

323
00:14:17,010 --> 00:14:19,890
Toda, kaj lahko storimo tukaj
poskušali ugotoviti, kako

324
00:14:19,890 --> 00:14:21,640
najbolje, da to storite vizualno.

325
00:14:21,640 --> 00:14:24,800
Ker bi rad predlagal, da če bomo
želite vstaviti elemente v to

326
00:14:24,800 --> 00:14:26,680
Obstoječi seznam, ki
Ima pet elementov -

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

328
00:14:29,530 --> 00:14:33,300
če bi bili, da bo izvajanje tega v
kodo, da moram razmisliti, kako iti

329
00:14:33,300 --> 00:14:34,160
o tem.

330
00:14:34,160 --> 00:14:37,720
>> In jaz bi predlagal ob baby korake
s katerim sem v tem primeru pomeni, kaj so

331
00:14:37,720 --> 00:14:41,090
možne scenarije, ki smo
lahko naletite na splošno?

332
00:14:41,090 --> 00:14:44,120
Pri izvajanju vložek za vezano
Seznam je to le zgodi, da bo

333
00:14:44,120 --> 00:14:46,090
Konkreten primer velikosti pet.

334
00:14:46,090 --> 00:14:50,420
No, če želite vstaviti številko,
želel povedati številko ena, in

335
00:14:50,420 --> 00:14:53,380
vzdrževanje urejen red, kjer
Očitno pa številka ena potrebujete

336
00:14:53,380 --> 00:14:55,686
gre v tem konkretnem primeru?

337
00:14:55,686 --> 00:14:56,840
Rad na začetku.

338
00:14:56,840 --> 00:15:00,030
>> Ampak kaj je zanimivo je, da
Če želite vstaviti eno v to

339
00:15:00,030 --> 00:15:04,100
Seznam je treba kaj posebnega kazalec
se očitno posodablja?

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

341
00:15:04,610 --> 00:15:07,830
Tako bi lahko dejali, da je to prvi primer
da bomo morda želeli razmisliti,

342
00:15:07,830 --> 00:15:11,140
scenarij, ki vključuje vstavitvijo
začetek seznama.

343
00:15:11,140 --> 00:15:15,400
>> Poglejmo Prebirati off morda tako enostavno, ali celo
lažje primeru, relativno gledano.

344
00:15:15,400 --> 00:15:18,110
Recimo, da želite vstaviti
Številka 35 v razvrščeni vrstnem redu.

345
00:15:18,110 --> 00:15:20,600
To očitno spada tja.

346
00:15:20,600 --> 00:15:25,320
Torej, kaj je kazalec očitno se dogaja, da
je treba posodobiti v tem scenariju?

347
00:15:25,320 --> 00:15:30,060
34 je kazalec postaja ni nič
vendar naslov struct

348
00:15:30,060 --> 00:15:31,800
ki vsebuje številko 35.

349
00:15:31,800 --> 00:15:32,750
Tako da je zadeva dva.

350
00:15:32,750 --> 00:15:36,190
Torej je že, da sem nekako kvantiziranja
koliko dela imam jaz tukaj.

351
00:15:36,190 --> 00:15:39,880
>> In končno, očitno srednji primer je
zares, v sredini, če želim

352
00:15:39,880 --> 00:15:45,870
vstavite nekaj kot recimo 23, ki gre
med 23 in 26, vendar

353
00:15:45,870 --> 00:15:48,680
Zdaj se stvari malo bolj
vključeni, ker, kaj

354
00:15:48,680 --> 00:15:52,800
treba spremeniti nasvetov?

355
00:15:52,800 --> 00:15:56,680
Torej 22 mora seveda treba spremeniti
ker ne morejo navesti 26. anymore.

356
00:15:56,680 --> 00:16:00,320
On potrebuje, da kaže na novo vozlišče, ki
Jaz bom moral dodeliti s klicem

357
00:16:00,320 --> 00:16:01,770
malloc ali lahko enakovredni.

358
00:16:01,770 --> 00:16:05,990
>> Potem pa sem tudi, da je potrebno novo vozlišče, 23
v tem primeru, da ima kazalec

359
00:16:05,990 --> 00:16:07,870
kaže na koga?

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

361
00:16:08,560 --> 00:16:10,380
In tam dogaja, da se
Vrstni red operacij tukaj.

362
00:16:10,380 --> 00:16:13,410
Ker če naredim to neumno, in jaz
na primer začetkom na začetku

363
00:16:13,410 --> 00:16:16,040
Seznam, in moj cilj je, da vstavite 23.

364
00:16:16,040 --> 00:16:18,610
In sem preveriti, ali to spada
Tukaj, v bližini devetih?

365
00:16:18,610 --> 00:16:18,950
Število

366
00:16:18,950 --> 00:16:20,670
Ali to spada sem, poleg 17?

367
00:16:20,670 --> 00:16:20,940
Število

368
00:16:20,940 --> 00:16:22,530
Ali spada tu zraven 22?

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

370
00:16:23,300 --> 00:16:26,400
>> Zdaj, če sem nor sem, in ne
misleč to skozi, morda sem

371
00:16:26,400 --> 00:16:28,320
dodeli svojo novo vozlišče za 23 let.

372
00:16:28,320 --> 00:16:32,080
Jaz bi posodobili kazalec od
vozlišče se imenuje 22, kar kaže

373
00:16:32,080 --> 00:16:33,080
je na novo vozlišče.

374
00:16:33,080 --> 00:16:36,140
In kaj potem moram posodobiti
kazalec za novo enoto je bil?

375
00:16:36,140 --> 00:16:38,120
>> ŠTUDENT: [neslišno].

376
00:16:38,120 --> 00:16:38,385
>> SPEAKER 1: Točno tako.

377
00:16:38,385 --> 00:16:39,710
Kaže na 26 let.

378
00:16:39,710 --> 00:16:45,590
Ampak Hudiča, če nisem že posodobiti
22 je kazalec na točko tega tipa, in

379
00:16:45,590 --> 00:16:48,260
Zdaj imam sirotam, počitka
seznama, tako rekoč.

380
00:16:48,260 --> 00:16:52,140
Torej, vrstni red operacij tukaj
se bo pomembno.

381
00:16:52,140 --> 00:16:55,100
>> Če želite to narediti, da bi lahko kradejo,
recimo, šest prostovoljcev.

382
00:16:55,100 --> 00:16:57,650
In da vidimo, če nam tega ne more storiti
vizualno namesto kode-pametno.

383
00:16:57,650 --> 00:16:59,330
In imamo kak lep stres
Žoge za vas danes.

384
00:16:59,330 --> 00:17:02,510
V redu, kaj pa en, dva, v
nazaj - na koncu tam.

385
00:17:02,510 --> 00:17:04,530
tri, štiri, oba
fantje na koncu.

386
00:17:04,530 --> 00:17:05,579
In pet, šest.

387
00:17:05,579 --> 00:17:05,839
Prepričan.

388
00:17:05,839 --> 00:17:06,450
Pet in šest.

389
00:17:06,450 --> 00:17:08,390
Vse je v redu in bomo prišli
da vaju naslednjič.

390
00:17:08,390 --> 00:17:09,640
Vse je v redu, pridi gor.

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

392
00:17:12,010 --> 00:17:14,819
>> Vse je v redu, ker ste tukaj prvič,
bi želeli, da je eden nerodno

393
00:17:14,819 --> 00:17:16,119
V Google Glass tukaj?

394
00:17:16,119 --> 00:17:19,075
V redu, torej, OK, steklo,
Snemanje videa.

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

396
00:17:22,720 --> 00:17:24,589
OK, ste na dobri poti.

397
00:17:24,589 --> 00:17:27,950
>> Vse je v redu, tako da, če lahko vi pridite
tukaj, sem vnaprej pripravljena

398
00:17:27,950 --> 00:17:30,110
nekaj številk.

399
00:17:30,110 --> 00:17:31,240
Vse je v redu, pridi sem.

400
00:17:31,240 --> 00:17:33,440
In zakaj ne greš malo
naprej v to smer.

401
00:17:33,440 --> 00:17:35,520
In poglejmo, kako ti je ime,
z Google Glass?

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

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

404
00:17:36,230 --> 00:17:38,380
V redu, Ben, boste prvi, dobesedno.

405
00:17:38,380 --> 00:17:40,580
Torej bomo poslali
na koncu stopnje.

406
00:17:40,580 --> 00:17:41,670
Vse je v redu, in ti je ime?

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

408
00:17:41,990 --> 00:17:44,530
>> SPEAKER 1: Jason, OK boste
bo številka devet.

409
00:17:44,530 --> 00:17:46,700
Torej, če želite slediti Ben tak način.

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

411
00:17:47,010 --> 00:17:49,630
>> SPEAKER 1: Jill, si bo
17, ki bi, če bi to več storiti

412
00:17:49,630 --> 00:17:51,260
pametno, bi moral
vpis na drugem koncu.

413
00:17:51,260 --> 00:17:52,370
Ti pojdi tja.

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

415
00:17:53,030 --> 00:17:53,670
In vi ste?

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

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

418
00:17:56,130 --> 00:17:58,420
In tvoje ime?

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

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

421
00:18:00,100 --> 00:18:00,740
In potem na koncu.

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

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

424
00:18:02,670 --> 00:18:03,920
Tako da pridi sem.

425
00:18:03,920 --> 00:18:06,360
>> Vse je v redu, tako da odlično razporejene
naročite že.

426
00:18:06,360 --> 00:18:09,600
In gremo naprej in to
tako da bomo lahko res -

427
00:18:09,600 --> 00:18:11,720
Ben si nekako iščejo
ven v nikjer ni.

428
00:18:11,720 --> 00:18:15,670
OK, tako da gremo naprej in prikazujejo to
z rokami, tako kot sem bil, ravno,

429
00:18:15,670 --> 00:18:16,250
kaj se dogaja.

430
00:18:16,250 --> 00:18:19,540
Tako da gredo naprej in da sebi
stopal ali dve med seboj.

431
00:18:19,540 --> 00:18:22,900
In gredo naprej in točko z eno roko na
Kdor morate biti obrnjena

432
00:18:22,900 --> 00:18:23,470
temelji na tem.

433
00:18:23,470 --> 00:18:25,890
In če ste null samo točko
naravnost na tla.

434
00:18:25,890 --> 00:18:27,690
V redu, dobro.

435
00:18:27,690 --> 00:18:32,290
>> Torej, zdaj imamo povezan seznam, in dovolite mi,
Predlagam, da bom imel vlogo

436
00:18:32,290 --> 00:18:35,110
PTR, tako da ne bo motilo
da bi se to okoli.

437
00:18:35,110 --> 00:18:37,830
In potem - kdo neumen konvencija -
lahko pokličete to, kar hočeš -

438
00:18:37,830 --> 00:18:39,800
Predhodnik kazalec, PRED kazalec -

439
00:18:39,800 --> 00:18:43,930
to je samo vzdevek smo dali v
naša vzorčna koda za levico.

440
00:18:43,930 --> 00:18:47,240
Po drugi strani, da bodo vodenje
Spremljajte kdo je kdo v

441
00:18:47,240 --> 00:18:48,400
po scenarije.

442
00:18:48,400 --> 00:18:52,390
>> Torej predvidevam, prvič, rad bi odtrgal off
da je prvi primer vstavljanje, pravijo

443
00:18:52,390 --> 00:18:54,330
20, v seznamu.

444
00:18:54,330 --> 00:18:57,160
Torej bom potreboval nekoga, ki bi
poosebljajo številko 20 za nas.

445
00:18:57,160 --> 00:18:58,950
Tako da moram malloc nekom
iz občinstva.

446
00:18:58,950 --> 00:18:59,380
Pridi gor.

447
00:18:59,380 --> 00:19:00,340
Kako ti je ime?

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

449
00:19:01,300 --> 00:19:05,270
>> SPEAKER 1: Brian, vse v redu, tako da
mora biti vozlišče, ki vsebuje 20.

450
00:19:05,270 --> 00:19:06,810
Vse je v redu, pridi sem.

451
00:19:06,810 --> 00:19:10,025
In seveda, kjer
Brian ne pripada?

452
00:19:10,025 --> 00:19:12,190
Torej, v sredini - pravzaprav
Čakaj malo.

453
00:19:12,190 --> 00:19:13,420
To delamo v okvari.

454
00:19:13,420 --> 00:19:17,170
Mi smo to kar veliko težje
kot ga je treba na prvi.

455
00:19:17,170 --> 00:19:21,210
OK, gremo na prostem Brian
in realloc Brian kot pet.

456
00:19:21,210 --> 00:19:23,680
>> OK, zdaj želimo vstaviti
Brian kot pet.

457
00:19:23,680 --> 00:19:25,960
Torej, pridi sem zraven
Ben le za trenutek.

458
00:19:25,960 --> 00:19:28,250
In lahko povem, predvidoma
če ta zgodba se dogaja.

459
00:19:28,250 --> 00:19:30,500
Ampak kaj je dobro premisliti o
Vrstni red operacij.

460
00:19:30,500 --> 00:19:32,880
In to je točno to vizualna
da se dogaja, da line up

461
00:19:32,880 --> 00:19:34,080
s to oznako vzorca.

462
00:19:34,080 --> 00:19:40,120
Torej, tukaj sem PTR sprva kaže
ni na Bena, per se, ampak ne glede na

463
00:19:40,120 --> 00:19:43,245
cenimo je vsebuje, kar je v tem primeru
je - kaj je spet ti je ime?

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

465
00:19:43,670 --> 00:19:47,350
>> SPEAKER 1: Jason, tako da sta Ben in jaz
kaže na Jasona v tem trenutku.

466
00:19:47,350 --> 00:19:49,700
Torej, zdaj moram ugotoviti,
kadar Brian pripada?

467
00:19:49,700 --> 00:19:53,500
Torej, edina stvar, imam dostop do
Zdaj je njegov podatek n.

468
00:19:53,500 --> 00:19:58,280
Torej grem preveriti, se
Brian manj kot Jasona?

469
00:19:58,280 --> 00:19:59,770
Odgovor je res.

470
00:19:59,770 --> 00:20:03,680
>> Torej, kaj je zdaj zgodilo,
v pravilnem vrstnem redu?

471
00:20:03,680 --> 00:20:07,120
Moram posodobiti, koliko nasvetov
skupaj v tej zgodbi?

472
00:20:07,120 --> 00:20:10,720
Kje je moja roka je še vedno kaže na
Jason in roko - če želite

473
00:20:10,720 --> 00:20:12,930
dvigni roko, kot so, nekako sem
Ne vem, vprašaj.

474
00:20:12,930 --> 00:20:14,070
V redu, dobro.

475
00:20:14,070 --> 00:20:15,670
>> Vse je v redu, tako da boste imeli
nekaj kandidatov.

476
00:20:15,670 --> 00:20:20,500
Bodisi Ben ali jaz ali Brian ali Jason
ali pa vsi ostali, ki

477
00:20:20,500 --> 00:20:21,370
kazalci morali spremeniti?

478
00:20:21,370 --> 00:20:23,260
Koliko skupaj?

479
00:20:23,260 --> 00:20:24,080
>> OK, tako da dva.

480
00:20:24,080 --> 00:20:27,090
Moj kazalec sploh ni pomembno več
ker sem samo začasno.

481
00:20:27,090 --> 00:20:31,370
Tako da je ta dva fanta, domnevno
sta Ben in Brian.

482
00:20:31,370 --> 00:20:34,410
Naj predlagam, da posodobite
Ben, saj je on prvi.

483
00:20:34,410 --> 00:20:36,350
Prvi element tega seznama
Zdaj bo Brian.

484
00:20:36,350 --> 00:20:38,070
Torej Ben točka na Briana.

485
00:20:38,070 --> 00:20:39,320
OK, kaj zdaj?

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

487
00:20:41,950 --> 00:20:43,460
>> Kdo opozoril na koga?

488
00:20:43,460 --> 00:20:44,710
>> ŠTUDENT: [neslišno].

489
00:20:44,710 --> 00:20:46,180
>> SPEAKER 1: OK, tako da ima Brian
opozoriti na Jasona.

490
00:20:46,180 --> 00:20:48,360
Ampak sem izgubil skladbo tega kazalca?

491
00:20:48,360 --> 00:20:49,980
Ne vem, kje je Jason?

492
00:20:49,980 --> 00:20:50,790
>> ŠTUDENT: [neslišno].

493
00:20:50,790 --> 00:20:52,620
>> SPEAKER 1: jaz, ker sem
začasna kazalec.

494
00:20:52,620 --> 00:20:55,110
In verjetno so se nisem spremenil
opozoriti na novo vozlišče.

495
00:20:55,110 --> 00:20:58,300
Tako bomo lahko preprosto Brian točko
V kdor sem gledala.

496
00:20:58,300 --> 00:20:59,000
In sva končala.

497
00:20:59,000 --> 00:21:01,890
Torej velja eno, vstavljanje na
začetek seznama.

498
00:21:01,890 --> 00:21:02,950
Obstajali sta dve ključni koraki.

499
00:21:02,950 --> 00:21:06,750
Ena moramo posodobiti ben in nato
imamo tudi posodobiti Brian.

500
00:21:06,750 --> 00:21:09,230
In potem mi ni treba ukvarjati
traipsing skozi preostanek

501
00:21:09,230 --> 00:21:12,680
seznam, ker smo že našel
mesto, ker je pripadal

502
00:21:12,680 --> 00:21:14,080
levo prvega elementa.

503
00:21:14,080 --> 00:21:15,400
>> V redu, torej precej enostavna.

504
00:21:15,400 --> 00:21:18,110
V bistvu se počuti, kot da sva skoraj
bi to preveč zapleteno.

505
00:21:18,110 --> 00:21:20,240
Torej, kaj je zdaj drobovja off konec
seznama, in videli, če

506
00:21:20,240 --> 00:21:21,380
Kompleksnost začne.

507
00:21:21,380 --> 00:21:24,560
Torej, če zdaj, jaz alloc iz občinstva.

508
00:21:24,560 --> 00:21:25,540
Kdo rad igral 55?

509
00:21:25,540 --> 00:21:26,700
Vse je v redu, sem prvič videl svojo roko.

510
00:21:26,700 --> 00:21:29,620
Pridi gor.

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

512
00:21:30,030 --> 00:21:31,177
Kako ti je ime?

513
00:21:31,177 --> 00:21:32,310
>> ŠTUDENT: [neslišno].

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

515
00:21:33,240 --> 00:21:33,890
OK, pridi gor.

516
00:21:33,890 --> 00:21:35,730
Boste številka 55.

517
00:21:35,730 --> 00:21:37,820
Tako da, seveda, pripadajo
na koncu seznama.

518
00:21:37,820 --> 00:21:41,850
Torej, kaj je Replay simulacijo z mano
da PTR za trenutek.

519
00:21:41,850 --> 00:21:44,050
Tako da sem jih prej opozoriti na
karkoli Ben je obrnjena.

520
00:21:44,050 --> 00:21:45,900
Mi smo tako kaže zdaj na Briana.

521
00:21:45,900 --> 00:21:48,420
Torej 55 ne manj kot pet.

522
00:21:48,420 --> 00:21:52,510
Torej bom sam posodablja z
kaže na naslednji kazalec Brianovem, ki

523
00:21:52,510 --> 00:21:54,450
Zdaj je seveda Jasona.

524
00:21:54,450 --> 00:21:57,310
55 ni manjša od devet, tako da
Bom posodobiti PTR.

525
00:21:57,310 --> 00:21:58,890
Bom posodobiti PTR.

526
00:21:58,890 --> 00:22:02,290
Bom posodobiti PTR
Jaz bom za posodobitev PTR.

527
00:22:02,290 --> 00:22:05,060
In bom - hmm, kaj je
ime?

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

529
00:22:05,560 --> 00:22:09,190
>> SPEAKER 1: Diana je poudaril, seveda,
na ničelno z levico.

530
00:22:09,190 --> 00:22:13,030
Torej, če ne Habata dejansko
očitno pripada?

531
00:22:13,030 --> 00:22:15,050
Na levi strani, tukaj.

532
00:22:15,050 --> 00:22:19,460
Torej, kako naj vem, da bi jo dal tukaj
Mislim, da sem zamočil.

533
00:22:19,460 --> 00:22:22,420
Ker tisto, kar je PTR umetnost
ta trenutek?

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

535
00:22:23,240 --> 00:22:25,580
Torej, čeprav, vizualno, ne moremo
očitno videti vse te

536
00:22:25,580 --> 00:22:26,610
Fantje tukaj na odru.

537
00:22:26,610 --> 00:22:29,680
Sem ne hranijo spremljali prejšnja
oseba na seznamu.

538
00:22:29,680 --> 00:22:33,210
Nimam s prstom kaže ven,
V tem primeru je vozlišče številka 34.

539
00:22:33,210 --> 00:22:34,760
>> Torej, kaj je pravzaprav začetek tega konec.

540
00:22:34,760 --> 00:22:37,560
Torej, zdaj sem dejansko ne potrebujejo,
Druga lokalna spremenljivka.

541
00:22:37,560 --> 00:22:40,980
In to je tisto, kar boste videli v
Dejanski vzorec C kodo, kjer, kot sem šel,

542
00:22:40,980 --> 00:22:45,860
ko sem posodobiti svojo desno roko na točko
Jason, zato je ostalo Brian zadaj, jaz

543
00:22:45,860 --> 00:22:51,440
bolje začeti z mojo levo roko
posodobiti, kjer sem bil, da sem lahko grem

544
00:22:51,440 --> 00:22:52,700
skozi ta seznam -

545
00:22:52,700 --> 00:22:55,040
bolj nerodno kot sem nameraval
Zdaj tukaj vizualno -

546
00:22:55,040 --> 00:22:56,740
Jaz bom priti do
konec seznama.

547
00:22:56,740 --> 00:23:00,020
>> Ta kombinacija je še vedno nič, kar je precej
neuporabna, razen da se nakaže

548
00:23:00,020 --> 00:23:02,980
Jaz sem očitno na koncu seznama,
ampak zdaj vsaj imam to

549
00:23:02,980 --> 00:23:08,270
Predhodnik kazalec kaže tukaj, tako da
kaj zdaj roke in kaj kazalci potrebujete

550
00:23:08,270 --> 00:23:10,150
treba posodobiti?

551
00:23:10,150 --> 00:23:13,214
Čigava roka hočeš
preoblikovati prvi?

552
00:23:13,214 --> 00:23:15,190
>> ŠTUDENT: [neslišno].

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

554
00:23:16,220 --> 00:23:21,110
Kam želite poudariti
Levi kazalec Dianina na?

555
00:23:21,110 --> 00:23:23,620
Na 55, verjetno, da
smo tam vstavi.

556
00:23:23,620 --> 00:23:25,560
In kje bi 55. kazalec iti?

557
00:23:25,560 --> 00:23:27,000
Navzdol, kar je nično.

558
00:23:27,000 --> 00:23:28,890
In moje roke, na tej točki, ne
pomembno, ker so bili samo

559
00:23:28,890 --> 00:23:30,070
začasne spremenljivke.

560
00:23:30,070 --> 00:23:31,030
Torej, zdaj smo storili.

561
00:23:31,030 --> 00:23:34,650
>> Torej dodatno kompleksnost tam - in
to ni tako težko izvajati,

562
00:23:34,650 --> 00:23:38,660
vendar potrebujemo sekundarne spremenljivke, da bi
Preverite, preden sem premakniti svoj prav

563
00:23:38,660 --> 00:23:42,140
roko, sem posodobiti vrednost moja leva
roko, PRED kazalec v tem primeru, tako

564
00:23:42,140 --> 00:23:45,860
da imam zadnjo kazalec
slediti, kje sem bil.

565
00:23:45,860 --> 00:23:49,360
Zdaj, kot prahi, če si to mislil
skozi ta občutek, kot da je

566
00:23:49,360 --> 00:23:51,490
malo siten, da morajo voditi
Spremljajte ta leve roke.

567
00:23:51,490 --> 00:23:54,015
>> Kaj bi druga rešitev
tega problema so?

568
00:23:54,015 --> 00:23:56,500
Če imaš za preoblikovanje podatkov
Struktura govorimo

569
00:23:56,500 --> 00:23:59,630
skozi prav zdaj?

570
00:23:59,630 --> 00:24:02,690
Če se to nekako zdi malo
siten, da imajo, recimo, dva kazalca

571
00:24:02,690 --> 00:24:08,430
tekoč skozi seznam, kdo bi lahko
so v idealnem svetu, ohranja

572
00:24:08,430 --> 00:24:10,160
informacije, ki jih potrebujemo?

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

574
00:24:11,360 --> 00:24:12,610
>> ŠTUDENT: [neslišno].

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

576
00:24:15,160 --> 00:24:16,150
>> SPEAKER 1: Točno tako.

577
00:24:16,150 --> 00:24:19,130
Pravica do tam je pravzaprav zanimivo
Kalčki ideje.

578
00:24:19,130 --> 00:24:22,470
In ta ideja prejšnjega kazalca,
kaže na prejšnji element.

579
00:24:22,470 --> 00:24:25,580
Kaj pa, če sem pooseblja da
Notranjost seznamu samo?

580
00:24:25,580 --> 00:24:27,810
In to se dogaja, da je težko predstavljati
to brez vsega papirja

581
00:24:27,810 --> 00:24:28,830
padejo na tla.

582
00:24:28,830 --> 00:24:31,860
Recimo, da ti fantje uporabljajo tako
rokami, da ima prejšnja

583
00:24:31,860 --> 00:24:35,950
kazalec, in naslednji kazalec, s čimer
izvedbenih kaj bomo klic dvakrat

584
00:24:35,950 --> 00:24:36,830
povezani seznam.

585
00:24:36,830 --> 00:24:41,090
Ki bi mi dovolite, da nekako previjanje,
veliko lažje brez mene

586
00:24:41,090 --> 00:24:43,800
programer, da bi predolgo
sledenje ročno -

587
00:24:43,800 --> 00:24:44,980
resnično ročno -

588
00:24:44,980 --> 00:24:47,280
na to, kje sem bil prej
na seznamu.

589
00:24:47,280 --> 00:24:48,110
Tako da ne bo naredil.

590
00:24:48,110 --> 00:24:50,950
Bomo keep it simple, ker je to
dogaja, da pridejo po ceni, dvakrat

591
00:24:50,950 --> 00:24:53,450
veliko prostora za napotke,
Če želite še enega.

592
00:24:53,450 --> 00:24:55,760
Ampak to je res pogosti
podatkovna struktura znana kot

593
00:24:55,760 --> 00:24:57,410
dvojno povezani seznam.

594
00:24:57,410 --> 00:25:01,310
>> Naredimo končno primer tukaj in dal
ti fantje iz njihove bede.

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

596
00:25:03,270 --> 00:25:05,320
Pridi gor iz hodnika tam.

597
00:25:05,320 --> 00:25:06,280
V redu, kako ti je ime?

598
00:25:06,280 --> 00:25:07,440
>> ŠTUDENT: [neslišno].

599
00:25:07,440 --> 00:25:07,855
>> SPEAKER 1: Oprostite?

600
00:25:07,855 --> 00:25:08,480
>> ŠTUDENT: [neslišno].

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

602
00:25:09,410 --> 00:25:10,230
OK, pridi gor.

603
00:25:10,230 --> 00:25:11,910
Si je 20.

604
00:25:11,910 --> 00:25:14,720
Očitno si bodo
spadajo med 17. in 22..

605
00:25:14,720 --> 00:25:16,150
Naj se naučijo svojo lekcijo.

606
00:25:16,150 --> 00:25:18,150
Jaz bom za začetek kazalec
kaže na Briana.

607
00:25:18,150 --> 00:25:21,190
In jaz bom moral svojo levo roko
posodobi le Brian kot sem premakniti

608
00:25:21,190 --> 00:25:23,600
Jason, preverjanje pa 20 manj kot devet?

609
00:25:23,600 --> 00:25:24,060
Število

610
00:25:24,060 --> 00:25:25,430
Je 20 manj kot 17?

611
00:25:25,430 --> 00:25:25,880
Število

612
00:25:25,880 --> 00:25:27,450
Je 20 manj kot 22?

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

614
00:25:28,440 --> 00:25:34,070
Torej, kaj kazalci ali roke, je treba spremeniti
kje ste zdaj kaže?

615
00:25:34,070 --> 00:25:37,070
>> Tako da lahko naredimo 17 kaže na 20..

616
00:25:37,070 --> 00:25:37,860
Tako, da je v redu.

617
00:25:37,860 --> 00:25:40,080
Kje želimo poudariti
kazalec zdaj?

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

619
00:25:41,330 --> 00:25:45,410
In vemo, kje je 22, še enkrat hvala
po mojem začasno kazalcem.

620
00:25:45,410 --> 00:25:46,760
Tako da smo v redu tam.

621
00:25:46,760 --> 00:25:49,440
Torej zaradi tega začasno skladiščenje
Sem redno spremljali, kje so vsi.

622
00:25:49,440 --> 00:25:55,055
In sedaj lahko vizualno šel v katerih
vam pripada, in zdaj moramo 1, 2, 3,

623
00:25:55,055 --> 00:25:58,410
4, 5, 6, 7, 8, 9 stres kroglice,
in aplavz za

624
00:25:58,410 --> 00:25:59,770
ti fantje, če bi lahko.

625
00:25:59,770 --> 00:26:00,410
Lepo opravljeno.

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

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

628
00:26:06,330 --> 00:26:09,860
In lahko vodijo kosov
papirja kot spominki.

629
00:26:09,860 --> 00:26:15,930
>> V redu, torej, verjemite mi, da je veliko
lažje prehodili, da se z

630
00:26:15,930 --> 00:26:17,680
ljudje, kot pa je z dejanskim kodo.

631
00:26:17,680 --> 00:26:22,690
Ampak, kaj boste našli čez nekaj trenutkov
Zdaj, je isti - oh, hvala.

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

633
00:26:23,630 --> 00:26:29,360
je, da boste ugotovili, da iste podatke
struktura, povezani seznam, lahko dejansko

634
00:26:29,360 --> 00:26:33,200
uporabi kot sestavino še
sofisticirane podatkovne strukture.

635
00:26:33,200 --> 00:26:37,620
>> In zavedati tudi, da je tema tukaj je, da
smo absolutno uvedli več

636
00:26:37,620 --> 00:26:40,060
kompleksnost v izvajanju
to algoritem.

637
00:26:40,060 --> 00:26:43,940
Vstavljanje, in če smo šli skozi to,
brisanje in iskanje, je malo

638
00:26:43,940 --> 00:26:46,660
bolj zapletena, kot to
je s paleto.

639
00:26:46,660 --> 00:26:48,040
Vendar pa smo pridobili nekaj dinamiko.

640
00:26:48,040 --> 00:26:50,180
Smo dobili prilagodljivo strukturo podatkov.

641
00:26:50,180 --> 00:26:54,010
>> Ampak še enkrat, bomo plačali ceno ob nekaterih
dodatno kompleksnost, tako v

642
00:26:54,010 --> 00:26:54,910
njeno izvajanje.

643
00:26:54,910 --> 00:26:56,750
In smo obupal naključni dostop.

644
00:26:56,750 --> 00:27:00,450
In če sem iskren, tam ni nekaj lepih
čiščenje diapozitiv ga lahko dam, da

645
00:27:00,450 --> 00:27:03,120
pravi, tukaj je, zakaj povezani seznam
je bolje kot matrike.

646
00:27:03,120 --> 00:27:04,100
In ostati pri tem.

647
00:27:04,100 --> 00:27:07,520
Ker je tema ponovno pojavila že zdaj,
bolj pa v prihodnjih tednih, je

648
00:27:07,520 --> 00:27:10,200
da ni nujno
pravilen odgovor.

649
00:27:10,200 --> 00:27:13,830
>> To je razlog, zakaj imamo ločeno os
zasnove za problemskih sklopov.

650
00:27:13,830 --> 00:27:17,700
To bo zelo konteksta
ali želite uporabljati te podatke

651
00:27:17,700 --> 00:27:21,750
struktura ali da ena, in bo
odvisno, kaj je pomembno za vas v smislu

652
00:27:21,750 --> 00:27:24,620
virov in kompleksnosti.

653
00:27:24,620 --> 00:27:28,830
>> Ampak naj predlagajo, da idealne podatki
struktura, sveti gral, bi bilo

654
00:27:28,830 --> 00:27:32,200
nekaj, kar je konstanten čas,
ne glede na to, koliko stvari je

655
00:27:32,200 --> 00:27:36,940
znotraj njega, ne da bi bilo neverjetno, če
Struktura podatkov je vrnilo odgovore na

656
00:27:36,940 --> 00:27:37,920
konstantna čas.

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

658
00:27:38,330 --> 00:27:40,110
Ta beseda je v velikem slovarju.

659
00:27:40,110 --> 00:27:41,550
Ali ne, ta beseda ni.

660
00:27:41,550 --> 00:27:43,270
Ali vsak tak problem obstaja.

661
00:27:43,270 --> 00:27:46,360
No, da vidimo, če ne moremo vsaj
narediti korak v smeri, da.

662
00:27:46,360 --> 00:27:50,190
>> Dovolite mi, da predlaga novo strukturo podatkov, ki
se lahko uporabljajo za različne stvari,

663
00:27:50,190 --> 00:27:52,260
v tem primeru se imenuje razpršene tabele.

664
00:27:52,260 --> 00:27:55,590
In tako smo pravzaprav nazaj pogledoval
na polju, v tem primeru, in

665
00:27:55,590 --> 00:28:00,550
nekoliko arbitrarno, sem to pripraviti
hash tabelo kot matriko z nekakšno

666
00:28:00,550 --> 00:28:02,810
dvodimenzionalna matrika -

667
00:28:02,810 --> 00:28:05,410
oziroma je to tu upodobljen kot dva
dimenzionalni array - ampak to je samo

668
00:28:05,410 --> 00:28:10,770
matrika velikosti 26, tako da, če
pokličite array, namizni nosilec

669
00:28:10,770 --> 00:28:12,440
nič je pravokotnik na vrhu.

670
00:28:12,440 --> 00:28:15,090
Tabela nosilec 25 je pravokotnik
na dnu.

671
00:28:15,090 --> 00:28:18,620
In to je, kako lahko narišem podatkov
struktura, v kateri želim shraniti

672
00:28:18,620 --> 00:28:19,790
ljudi, saj imena.

673
00:28:19,790 --> 00:28:24,370
>> Torej, na primer, in ne bom sestaviti
Celotna stvar tukaj v zgornjem delu, če sem

674
00:28:24,370 --> 00:28:29,160
je ta niz, ki sem zdaj dogaja, da
klic razpršene tabele, in to je še

675
00:28:29,160 --> 00:28:31,360
lokacija nič.

676
00:28:31,360 --> 00:28:34,840
To tukaj je lokacija
ena, in tako naprej.

677
00:28:34,840 --> 00:28:37,880
Trdim, da želim, da se ti podatki uporabijo
struktura, zaradi razprave

678
00:28:37,880 --> 00:28:42,600
Shranjevanje imen ljudi, Alice in Bob
Charlie in druga taka imena.

679
00:28:42,600 --> 00:28:46,110
Tako da mislim o tem sedaj začetkov
, recimo, slovarja

680
00:28:46,110 --> 00:28:47,520
z veliko besedami.

681
00:28:47,520 --> 00:28:49,435
Se zgodi, da bodo imena
v našem primeru tukaj.

682
00:28:49,435 --> 00:28:52,560
In to je vse preveč Germane, morda, da
izvajanje črkovalnik, kot smo

683
00:28:52,560 --> 00:28:54,400
Morda za problem nastaviti šest.

684
00:28:54,400 --> 00:28:59,300
>> Torej, če imamo niz skupni velikosti 26
tako, da je to 25. mesto

685
00:28:59,300 --> 00:29:03,390
na dnu, in trdim, da je Alice
Prva beseda v slovarju

686
00:29:03,390 --> 00:29:07,260
Imena, ki jih želim vstaviti v RAM,
v to strukturo podatkov, kjer so

687
00:29:07,260 --> 00:29:12,480
instinkt vam pove, da je Alice
Ime mora iti v tej matriki?

688
00:29:12,480 --> 00:29:13,510
>> Imamo 26 možnosti.

689
00:29:13,510 --> 00:29:14,990
Kadar želimo, da bi jo dali?

690
00:29:14,990 --> 00:29:16,200
Mi ji želimo v razredu nič, kajne?

691
00:29:16,200 --> 00:29:18,280
Za Alice, recimo, da nič.

692
00:29:18,280 --> 00:29:20,110
In B bo ena in C bosta dve.

693
00:29:20,110 --> 00:29:22,600
Torej bomo napisali
Alice ime tu gor.

694
00:29:22,600 --> 00:29:24,890
Če bomo nato vstavite Bob njegov
Ime bo šel tukaj.

695
00:29:24,890 --> 00:29:27,280
Charlie bo šel tukaj.

696
00:29:27,280 --> 00:29:30,500
In tako dalje navzdol skozi
ta struktura podatkov.

697
00:29:30,500 --> 00:29:32,090
>> To je čudovito strukturo podatkov.

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

699
00:29:32,730 --> 00:29:37,460
No, kar je čas teka
vstavite ime človeškega je v to

700
00:29:37,460 --> 00:29:39,850
podatkovna struktura prav zdaj?

701
00:29:39,850 --> 00:29:43,702
Glede na to, da je ta tabela izvaja,
resnično, kot matriko.

702
00:29:43,702 --> 00:29:44,940
No to je stalen čas.

703
00:29:44,940 --> 00:29:45,800
To je zaradi enega.

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

705
00:29:46,360 --> 00:29:48,630
>> No, kako ugotoviti,
kjer Alice pripada?

706
00:29:48,630 --> 00:29:51,000
Gledaš črko njenega imena?

707
00:29:51,000 --> 00:29:51,490
Prvi.

708
00:29:51,490 --> 00:29:54,350
In lahko dobite tam, če je niz,
ki ga pravkar gledamo na vrvico

709
00:29:54,350 --> 00:29:55,200
Nosilec nič.

710
00:29:55,200 --> 00:29:57,110
Torej Ničti značaja niza.

711
00:29:57,110 --> 00:29:57,610
To je enostavno.

712
00:29:57,610 --> 00:30:00,350
To smo storili v CRYPTO
Prirejanje tedni.

713
00:30:00,350 --> 00:30:05,310
In potem, ko veš, da Alice
Pismo je kapital, lahko odštejemo

714
00:30:05,310 --> 00:30:08,160
off 65 ali premoženja A sam,
ki nam daje nič.

715
00:30:08,160 --> 00:30:10,940
Tako zdaj vemo, da Alice pripada
na lokaciji nič.

716
00:30:10,940 --> 00:30:14,240
>> In glede na kazalec do teh podatkov
struktura, neke vrste, kako dolgo

717
00:30:14,240 --> 00:30:18,840
pa vzemi me, da bi našli lokacijo
nič v matriki?

718
00:30:18,840 --> 00:30:22,080
Samo en korak, prav je konstanten čas
zaradi bralno smo

719
00:30:22,080 --> 00:30:23,780
Predlagana je bila značilnost matrike.

720
00:30:23,780 --> 00:30:28,570
Torej na kratko, poskušal ugotoviti, kaj se je indeks
o je ime Alice, ki je v

721
00:30:28,570 --> 00:30:32,610
V tem primeru, je, ali naj samo reševanje
da nič, kjer B je eden in C

722
00:30:32,610 --> 00:30:34,900
dva, kipec, ki izvajajo
konstanten čas.

723
00:30:34,900 --> 00:30:38,510
Pravkar sem moral pogledati na svojem prvem pismu,
ugotoviti, kje je nič

724
00:30:38,510 --> 00:30:40,460
array je tudi stalen čas.

725
00:30:40,460 --> 00:30:42,140
Tako tehnično, da je
kot dveh korakih zdaj.

726
00:30:42,140 --> 00:30:43,330
Ampak to je še vedno konstantna.

727
00:30:43,330 --> 00:30:46,880
Zato pravimo, da je velik O enega, tako da smo jih
vstavi Alice v tej tabeli, v

728
00:30:46,880 --> 00:30:48,440
konstantna čas.

729
00:30:48,440 --> 00:30:50,960
>> Ampak seveda, jaz pa
Naivno sem, kajne?

730
00:30:50,960 --> 00:30:53,240
Kaj pa, če je Aaron v razredu?

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

732
00:30:53,990 --> 00:30:57,230
Ali katera koli druga imena, ki se začnejo z
A. Kam gremo postaviti

733
00:30:57,230 --> 00:31:00,800
da oseba, kajne?

734
00:31:00,800 --> 00:31:03,420
Mislim, zdaj pa je samo tri
ljudje na mizi, tako da morda smo

735
00:31:03,420 --> 00:31:07,490
bi dal Aaron na lokaciji
nič ena dva tri.

736
00:31:07,490 --> 00:31:09,480
>> Prav, bi jaz dal tukaj.

737
00:31:09,480 --> 00:31:13,350
Ampak potem, če bomo poskušali vstaviti Davida v
ta seznam, kjer se David iti?

738
00:31:13,350 --> 00:31:15,170
Sedaj naš sistem začne lomljenje
dol, kajne?

739
00:31:15,170 --> 00:31:19,210
Ker zdaj David konča tukaj
če Aaron je pravzaprav tukaj.

740
00:31:19,210 --> 00:31:23,060
In tako zdaj ves ta zamisel o
čista struktura podatkov, ki nam daje

741
00:31:23,060 --> 00:31:28,010
Časovna konstanta vstavljanja ni več
konstanten čas, ker moram

742
00:31:28,010 --> 00:31:31,240
preveri, oh, prekleto, nekdo je že
V Alice lokaciji.

743
00:31:31,240 --> 00:31:35,320
>> Dovolite mi, da sonda preostanek teh podatkov
struktura, ki išče mesto, da dajo

744
00:31:35,320 --> 00:31:37,130
nekdo kot ime Aronovo.

745
00:31:37,130 --> 00:31:39,390
In tako, da preveč se začenja
da se linearno časa.

746
00:31:39,390 --> 00:31:42,710
Poleg tega, če želite takoj poiskati
Aaron v tej strukturi podatkov, in

747
00:31:42,710 --> 00:31:45,430
preveri, in ime Aronova ni tukaj.

748
00:31:45,430 --> 00:31:47,960
Idealno bi bilo, bi si rekel Aronu
ne strukture podatkov.

749
00:31:47,960 --> 00:31:51,530
Ampak, če vam začeli delati prostor za
Aaron treba, kjer je prišlo do D

750
00:31:51,530 --> 00:31:55,600
ali E, da, v najslabšem primeru, morajo preveriti
celotno strukturo podatkov, v

751
00:31:55,600 --> 00:31:59,480
čemer je devolves v nekaj
linearna velikosti tabele.

752
00:31:59,480 --> 00:32:00,920
>> Torej vse v redu, bom to popraviti.

753
00:32:00,920 --> 00:32:04,200
Problem je v tem, da sem imel
26 elementov v tem polju.

754
00:32:04,200 --> 00:32:05,000
Dovolite mi, da jo spremeni.

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

756
00:32:06,010 --> 00:32:10,600
Dovolite mi, da jo spremeni tako, da namesto počutje
velikost 26 v celoti, opazili dno

757
00:32:10,600 --> 00:32:12,720
Indeks se bo spremenilo na n minus 1.

758
00:32:12,720 --> 00:32:16,610
Če 26 je očitno premajhen za ljudi "
Imena, saj je na tisoče

759
00:32:16,610 --> 00:32:20,830
Imena svetu, kaj je samo da
v 100 ali 1000 ali 10.000.

760
00:32:20,830 --> 00:32:22,960
Reciva, namenijo veliko več prostora.

761
00:32:22,960 --> 00:32:27,230
>> No, da ne padajo nujno
verjetnost, da ne bomo imeli dva

762
00:32:27,230 --> 00:32:31,510
ljudje z imeni, ki se začnejo z, in
tako, da boš poskusil postaviti

763
00:32:31,510 --> 00:32:33,120
Imena na lokaciji nič še.

764
00:32:33,120 --> 00:32:36,850
Še vedno se dogaja, da trčijo, ki
pomeni, da smo še vedno potrebujejo rešitev za povišanje

765
00:32:36,850 --> 00:32:41,020
Alice in Aron in Alicia in drugo
Imena se začnejo z A drugje.

766
00:32:41,020 --> 00:32:43,460
Toda kako veliko težavo je to?

767
00:32:43,460 --> 00:32:46,870
Kakšna je verjetnost, da boste
imajo trčenja v podatkovnem

768
00:32:46,870 --> 00:32:48,240
struktura, kot je ta?

769
00:32:48,240 --> 00:32:52,570
>> No, naj me - se bomo vrnili
na to vprašanje tukaj.

770
00:32:52,570 --> 00:32:55,530
In poglej, kako bi lahko
rešiti najprej.

771
00:32:55,530 --> 00:32:58,480
Dovolite mi, dvigni ta predlog tukaj.

772
00:32:58,480 --> 00:33:02,020
Kaj smo pravkar opisali, je algoritem,
hevristična imenujemo linearna

773
00:33:02,020 --> 00:33:05,030
sondiranje, pri čemer, če si se potrudil, da vstavite
Nekaj ​​je tukaj v teh podatkov

774
00:33:05,030 --> 00:33:08,920
strukture, ki se imenuje razpršene tabele,
in ni prostora tam,

775
00:33:08,920 --> 00:33:12,000
resnično sonda podatkovne strukture
preverjanje, ali je to na voljo?

776
00:33:12,000 --> 00:33:13,430
Je ta na voljo, je to na voljo?

777
00:33:13,430 --> 00:33:13,980
Je to na voljo?

778
00:33:13,980 --> 00:33:17,550
In ko končno je, da vstavite
ime, ki ga je prvotno namenjen

779
00:33:17,550 --> 00:33:19,370
drugje na tem mestu.

780
00:33:19,370 --> 00:33:23,360
Ampak v najslabšem primeru, le mesto
lahko zelo dno podatkov

781
00:33:23,360 --> 00:33:25,090
struktura, zelo konec niza.

782
00:33:25,090 --> 00:33:30,130
>> Torej linearni sondiranje, v najslabšem primeru,
devolves v linearnem algoritmu, kjer

783
00:33:30,130 --> 00:33:34,500
Aaron, če se zgodi, da se vstavi zadnji
V tej strukturi podatkov, morda je

784
00:33:34,500 --> 00:33:39,540
zadenejo ob tej prvi lokaciji, vendar
nato pa na koncu z slabe sreče na koncu.

785
00:33:39,540 --> 00:33:43,940
Torej to ni konstantna
Čas sveti gral za nas.

786
00:33:43,940 --> 00:33:47,650
Ta pristop vstavljanje elementov v
struktura podatkov se imenuje hašiš

787
00:33:47,650 --> 00:33:52,050
miza ne zdi, da je konstantna čas
vsaj ne v splošnem primeru.

788
00:33:52,050 --> 00:33:54,000
To lahko prenesejo v nekaj linearno.

789
00:33:54,000 --> 00:33:56,970
>> Pa kaj, če bomo rešili trčenj
Nekoliko drugače?

790
00:33:56,970 --> 00:34:00,740
Torej, tukaj je bolj prefinjene
pristop, kar je še vedno

791
00:34:00,740 --> 00:34:02,800
imenovane razpršene tabele.

792
00:34:02,800 --> 00:34:05,890
In hašiš, kot prahi, kaj
Mislim, je kazalo, da

793
00:34:05,890 --> 00:34:07,070
Sem prej omenil.

794
00:34:07,070 --> 00:34:09,810
Za razpršitev kaj lahko
misel kot glagol.

795
00:34:09,810 --> 00:34:13,690
>> Torej, če ste hash Alice je ime,
hash funkcijo, če se tako izrazim,

796
00:34:13,690 --> 00:34:14,710
bi se morali vrniti številko.

797
00:34:14,710 --> 00:34:18,199
V tem primeru je nič, če ji pripada na
lokacija nič, ena, če ji pripada na

798
00:34:18,199 --> 00:34:20,000
lokacija ena, in tako naprej.

799
00:34:20,000 --> 00:34:24,360
Torej moj hash funkcija je bila doslej
super enostavna, samo gledaš

800
00:34:24,360 --> 00:34:26,159
Prva črka v imenu nekoga drugega.

801
00:34:26,159 --> 00:34:29,090
Ampak hash funkcija je kot
vhod nekateri podatek,

802
00:34:29,090 --> 00:34:30,210
string, int, karkoli.

803
00:34:30,210 --> 00:34:32,239
In to izpljune tipično številko.

804
00:34:32,239 --> 00:34:35,739
In ta številka je, če da so podatki
element sodi v podatkovno strukturo

805
00:34:35,739 --> 00:34:37,800
Tukaj znan kot razpršene tabele.

806
00:34:37,800 --> 00:34:41,400
>> Torej samo intuitivno, to je
nekoliko drugačen kontekst.

807
00:34:41,400 --> 00:34:44,170
To dejansko se nanaša na primer
vključujejo rojstni dnevi, kjer je

808
00:34:44,170 --> 00:34:46,850
tam je lahko toliko kot
31 dni v mesecu.

809
00:34:46,850 --> 00:34:52,239
Toda kaj je ta oseba odloči, da bo
storiti v primeru trka?

810
00:34:52,239 --> 00:34:55,304
Kontekst zdaj pa ne trk
Imena, vendar trčenja na rojstne dneve,

811
00:34:55,304 --> 00:35:00,760
Če dve osebi enako rojstni dan
2. oktobra, na primer.

812
00:35:00,760 --> 00:35:02,120
>> ŠTUDENT: [neslišno].

813
00:35:02,120 --> 00:35:05,010
>> SPEAKER 1: Ja, tukaj imamo
vzvoda, povezanih seznamov.

814
00:35:05,010 --> 00:35:07,830
Zato malo drugače zgleda
kot smo jo narisal prej.

815
00:35:07,830 --> 00:35:10,790
Ampak mi zdi, da imajo na matriko
na levi strani.

816
00:35:10,790 --> 00:35:13,230
To je en indeks, ne za
posebnega razloga.

817
00:35:13,230 --> 00:35:14,630
Vendar je še vedno polje.

818
00:35:14,630 --> 00:35:16,160
To je niz kazalcev.

819
00:35:16,160 --> 00:35:20,670
In vsak od teh elementov, vsak
Ti krogi ali poševnico - slash

820
00:35:20,670 --> 00:35:23,970
predstavlja nična - vsak od teh
kazalci se očitno kaže na

821
00:35:23,970 --> 00:35:25,730
kaj podatkovna struktura?

822
00:35:25,730 --> 00:35:26,890
Povezani seznam.

823
00:35:26,890 --> 00:35:30,530
>> Torej, zdaj imamo možnost, da
Težko kodo v našem programu

824
00:35:30,530 --> 00:35:32,010
velikost tabele.

825
00:35:32,010 --> 00:35:35,360
V tem primeru vemo, da nikoli
več kot 31 dni v mesecu.

826
00:35:35,360 --> 00:35:38,480
Tako težko kodiranje vrednost, kot je 31.
smiselno v tem kontekstu.

827
00:35:38,480 --> 00:35:42,700
V okviru imen, težko kodiranje
26 je dopustno, da ljudje jev

828
00:35:42,700 --> 00:35:46,340
Imena šele z, na primer,
abeceda, ki vključuje do Z.

829
00:35:46,340 --> 00:35:50,180
>> Mi lahko Natrpati jih vsi v teh podatkov
Struktura dokler, ko smo dobili

830
00:35:50,180 --> 00:35:55,330
trčenje, mi ne dajo imena tukaj,
smo namesto da teh celic

831
00:35:55,330 --> 00:36:00,270
ne kot strune sami, ampak kot
kazalci, na primer, Alice.

832
00:36:00,270 --> 00:36:03,660
In potem Alice še en kazalec
drugo ime se začne z

833
00:36:03,660 --> 00:36:06,150
A. In Bob pravzaprav gre tukaj.

834
00:36:06,150 --> 00:36:10,850
>> In če je drugo ime se začne
z B, je konča tukaj.

835
00:36:10,850 --> 00:36:15,070
In tako vsak od elementov te
Tabela dva, če smo oblikovali to

836
00:36:15,070 --> 00:36:17,350
malo bolj spretno -

837
00:36:17,350 --> 00:36:18,125
no -

838
00:36:18,125 --> 00:36:22,950
Če smo oblikovali to malo več
pametno, zdaj postane prilagodljivo podatke

839
00:36:22,950 --> 00:36:27,720
struktura, kjer ni težko meja
o tem, koliko elementov lahko vstavite

840
00:36:27,720 --> 00:36:30,700
v tem, ker če imate
trčenje, da je v redu.

841
00:36:30,700 --> 00:36:34,690
Samo pojdi naprej in ga dodajte
kar smo videli malo nazaj je bila

842
00:36:34,690 --> 00:36:38,290
znana kot povezan seznam.

843
00:36:38,290 --> 00:36:39,690
>> Pa kaj je premor za trenutek.

844
00:36:39,690 --> 00:36:42,570
Kakšna je verjetnost trka
Na prvem mestu?

845
00:36:42,570 --> 00:36:45,480
Dobro, morda bom več razmišljal, morda
Jaz sem nad inženiring ta problem,

846
00:36:45,480 --> 00:36:46,370
saj veste kaj?

847
00:36:46,370 --> 00:36:49,070
Ja, lahko prišli do samovoljne
Primeri off vrhu moje glave, kot

848
00:36:49,070 --> 00:36:52,870
Allison in Aron, ampak v resnici,
saj enakomerna porazdelitev

849
00:36:52,870 --> 00:36:56,990
vhodov, da je nekaj naključnih vložki
v strukturo podatkov, kaj je res

850
00:36:56,990 --> 00:36:58,580
Verjetnost trčenja?

851
00:36:58,580 --> 00:37:01,670
No, izkaže, da je dejansko
super visoka.

852
00:37:01,670 --> 00:37:03,850
Dovolite mi, da posploševati to
Problem je, kot je ta.

853
00:37:03,850 --> 00:37:08,890
>> Torej, v sobi n CS50 študentov, kar je
Verjetnost, da vsaj

854
00:37:08,890 --> 00:37:11,010
dva študenta v sobi
imajo isti rojstni dan?

855
00:37:11,010 --> 00:37:13,346
Torej ni kaj. Nekaj ​​hund -

856
00:37:13,346 --> 00:37:16,790
200, 300 ljudi tukaj in več
sto ljudi doma danes.

857
00:37:16,790 --> 00:37:20,670
Torej, če si hotel, da se vprašamo, kaj je
verjetnost dve osebi

858
00:37:20,670 --> 00:37:23,930
v tej sobi, ki ima enako rojstni dan,
bomo lahko to ugotovite.

859
00:37:23,930 --> 00:37:26,250
In trdim, pravzaprav obstajata dve
ljudje z istim rojstni dan.

860
00:37:26,250 --> 00:37:29,560
>> Na primer, ali kdo
ima danes rojstni dan?

861
00:37:29,560 --> 00:37:31,340
Včeraj?

862
00:37:31,340 --> 00:37:32,590
Jutri?

863
00:37:32,590 --> 00:37:35,980
Vse je v redu, tako da se zdi, kot da bom
da ima za to 363 ali tako več

864
00:37:35,980 --> 00:37:39,500
krat, da dejansko ugotovimo,
če imamo trčenje.

865
00:37:39,500 --> 00:37:42,350
Ali pa bi samo to matematično
namesto tediously

866
00:37:42,350 --> 00:37:43,200
to.

867
00:37:43,200 --> 00:37:44,500
In predlaga naslednje.

868
00:37:44,500 --> 00:37:48,740
>> Zato sem predlagal, da bi lahko modelirati
Verjetnost dveh ljudi, ki imajo

869
00:37:48,740 --> 00:37:55,320
Enako, kot rojstni dan verjetnostjo 1.
minus verjetnost, da nihče, ki ima

870
00:37:55,320 --> 00:37:56,290
Enako rojstni dan.

871
00:37:56,290 --> 00:37:59,960
Tako, da se to, kar je samo
fancy način pisanja tega, za

872
00:37:59,960 --> 00:38:03,090
Prva oseba v sobi, on ali ona
ima lahko eno od možnosti

873
00:38:03,090 --> 00:38:07,370
rojstni dnevi ob predpostavki, 365 dni v letu,
se opravičujem oseb

874
00:38:07,370 --> 00:38:08,760
29. februar rojstni dan.

875
00:38:08,760 --> 00:38:13,470
>> Torej prva oseba v tej sobi je prost
da imajo poljubno število rojstne dneve

876
00:38:13,470 --> 00:38:18,280
od 365 možnosti tako, da
potrudili se bomo, da 365 deljeno z 365,

877
00:38:18,280 --> 00:38:18,990
ki je ena.

878
00:38:18,990 --> 00:38:22,700
Naslednji, v prostoru, če želimo
se izogne ​​trčenju, lahko le

879
00:38:22,700 --> 00:38:26,460
ima njegov ali njen rojstni dan o tem, kako
veliko različnih možnih dni?

880
00:38:26,460 --> 00:38:27,610
364.

881
00:38:27,610 --> 00:38:31,430
Torej drugi mandat v tem izrazu
v bistvu gre ta matematika za nas

882
00:38:31,430 --> 00:38:33,460
z odštevanjem off en možen dan.

883
00:38:33,460 --> 00:38:36,390
Potem Naslednji dan Naslednji dan
Naslednji dan do celotnega števila

884
00:38:36,390 --> 00:38:38,100
oseb v sobi.

885
00:38:38,100 --> 00:38:41,290
>> In če bomo potem pa razmisli, kaj potem je
verjetnost, ne pa vsakdo, ki ima

886
00:38:41,290 --> 00:38:45,265
edinstvene rojstni dnevi, ampak spet 1 minus
da je tisto, kar smo dobili, je izraz

887
00:38:45,265 --> 00:38:47,810
da lahko zelo domišljisko
videti takole.

888
00:38:47,810 --> 00:38:50,330
Ampak to je bolj zanimivo
pogled na vizualno.

889
00:38:50,330 --> 00:38:55,120
To je graf, kjer na x-osi je
število oseb v sobi,

890
00:38:55,120 --> 00:38:56,180
število rojstnih dni.

891
00:38:56,180 --> 00:38:59,840
Na osi y je verjetnost
kakšnega trčenja, dve osebi

892
00:38:59,840 --> 00:39:01,230
ob isti rojstni dan.

893
00:39:01,230 --> 00:39:05,020
>> In takeaway iz te krivulje je
da takoj, ko dobiš všeč 40

894
00:39:05,020 --> 00:39:11,110
študente, ti si na 90% verjetnostjo
combinatorically dveh

895
00:39:11,110 --> 00:39:13,550
ljudje ali več, ki imajo
Enako rojstni dan.

896
00:39:13,550 --> 00:39:18,600
In ko prideš do 58 ljudi všeč, da je
skoraj 100% priložnost dveh

897
00:39:18,600 --> 00:39:21,310
ljudje v prostoru se dogaja, da imajo
Enako rojstni dan, čeprav je

898
00:39:21,310 --> 00:39:26,650
365 ali 366 možnih vedra in
Samo 58 ljudi v sobi.

899
00:39:26,650 --> 00:39:29,900
Samo statistično boste verjetno
dobili trčenja, ki na kratko

900
00:39:29,900 --> 00:39:31,810
motivira to razpravo.

901
00:39:31,810 --> 00:39:35,890
Da tudi če bomo dobili fancy tukaj, in
začeli ob teh verig, smo še vedno

902
00:39:35,890 --> 00:39:36,950
dogaja, da imajo trkov.

903
00:39:36,950 --> 00:39:42,710
>> Tako da se postavlja vprašanje, kaj je
Stroški dela vstavljanje in brisanje

904
00:39:42,710 --> 00:39:44,850
v podatkovno strukturo, kot je ta?

905
00:39:44,850 --> 00:39:46,630
No naj predlagajo -

906
00:39:46,630 --> 00:39:51,570
in naj se vrnem na zaslonu nad
tukaj - če smo n elemente

907
00:39:51,570 --> 00:39:56,330
seznam, tako da, če poskušamo vstaviti
n elementi, in imamo

908
00:39:56,330 --> 00:39:58,050
koliko skupno vedra?

909
00:39:58,050 --> 00:40:03,450
Recimo 31 skupna vedra
v primeru rojstnih dni.

910
00:40:03,450 --> 00:40:09,240
Kaj je največja dolžina enega
teh verig potencialno?

911
00:40:09,240 --> 00:40:12,670
>> Če spet tam 31 mogoče
rojstni dnevi v določenem mesecu.

912
00:40:12,670 --> 00:40:14,580
In mi smo samo skupki vsakogar -

913
00:40:14,580 --> 00:40:15,580
to je pravzaprav neumen primer.

914
00:40:15,580 --> 00:40:16,960
Naredimo 26 namesto.

915
00:40:16,960 --> 00:40:20,890
Torej, če dejansko imajo ljudje, katerih imena
začnete z do Z, s čimer

916
00:40:20,890 --> 00:40:22,780
nas 26 možnosti.

917
00:40:22,780 --> 00:40:25,920
In smo z uporabo podatkovne strukture, kot so
Tisti, ki smo pravkar videli, s katerim imamo

918
00:40:25,920 --> 00:40:30,210
niz kazalcev, od katerih
opozarja na povezanem seznamu, kjer je

919
00:40:30,210 --> 00:40:32,360
Prvi seznam je vsakdo
z imenom Alice.

920
00:40:32,360 --> 00:40:35,770
Drugi list je vsak z
ime se začne z, začenši

921
00:40:35,770 --> 00:40:36,980
z B, in tako naprej.

922
00:40:36,980 --> 00:40:41,020
>> Kakšna je verjetnost, dolžina vsakega od
ti seznami če predpostavimo, lepo čist

923
00:40:41,020 --> 00:40:45,410
distribucija imen prek Ž
vsej strukture podatkov?

924
00:40:45,410 --> 00:40:50,210
Tam je n ljudi v strukturi podatkov
deljeno z 26, če oni lepo

925
00:40:50,210 --> 00:40:52,110
razširila čez celotno
struktura podatkov.

926
00:40:52,110 --> 00:40:54,970
Torej, dolžina vsakega od teh
verige je N deljeno z 26.

927
00:40:54,970 --> 00:40:57,380
Ampak v veliki O zapisu, kaj je to?

928
00:40:57,380 --> 00:41:00,100

929
00:41:00,100 --> 00:41:02,440
Kaj je to res?

930
00:41:02,440 --> 00:41:04,150
Torej je res samo n, kajne?

931
00:41:04,150 --> 00:41:06,620
Ker smo rekli v preteklosti,
mo, da si delimo s 26.

932
00:41:06,620 --> 00:41:08,710
Da, v resnici pa je hitrejši.

933
00:41:08,710 --> 00:41:12,720
Ampak v teoriji, to ni bistveno
vse to hitreje.

934
00:41:12,720 --> 00:41:16,040
>> Torej mi ne zdi, da je vse to veliko
bližje tej sveti gral.

935
00:41:16,040 --> 00:41:17,750
Dejstvo je, da je to le linearni čas.

936
00:41:17,750 --> 00:41:20,790
Heck, na tej točki, zakaj ne bomo
le z eno ogromno povezan seznam?

937
00:41:20,790 --> 00:41:23,510
Zakaj ne bi raje uporabite ena velika
polje za shranjevanje imen

938
00:41:23,510 --> 00:41:25,010
vsi v sobi?

939
00:41:25,010 --> 00:41:28,280
No, obstaja še vedno nekaj
prepričljiv o razpršene tabele?

940
00:41:28,280 --> 00:41:30,810
Ali obstaja še kaj prepričljiv
o strukturi podatkov

941
00:41:30,810 --> 00:41:33,940
ki je videti takole?

942
00:41:33,940 --> 00:41:35,182
To.

943
00:41:35,182 --> 00:41:37,050
>> ŠTUDENT: [neslišno].

944
00:41:37,050 --> 00:41:39,840
>> SPEAKER 1: Ja, in še enkrat, če je le
linearni čas algoritem in

945
00:41:39,840 --> 00:41:42,780
linearna struktura podatki času, zakaj ne jaz
samo shranite ime vsakogar, v veliki

946
00:41:42,780 --> 00:41:44,210
matrika, ali v velikem povezana seznamu?

947
00:41:44,210 --> 00:41:47,010
In neha CS toliko težje
kot je treba?

948
00:41:47,010 --> 00:41:49,600

949
00:41:49,600 --> 00:41:53,190
Kaj je prepričljiv zaradi tega, čeprav
čeprav sem popraskal ven?

950
00:41:53,190 --> 00:41:54,930
>> ŠTUDENT: [neslišno].

951
00:41:54,930 --> 00:41:57,040
>> SPEAKER 1: Vstavljeno ne?

952
00:41:57,040 --> 00:41:58,140
Drago več.

953
00:41:58,140 --> 00:42:03,390
Torej vložki potencialno lahko še vedno
konstantna čas, čeprav vaši podatki

954
00:42:03,390 --> 00:42:07,910
Struktura izgleda takole, niz
kazalcev, od katerih je vsaka kaže na

955
00:42:07,910 --> 00:42:09,550
potencialno povezani seznam.

956
00:42:09,550 --> 00:42:15,220
Kako bi lahko dosegli konstantno
Čas vstavljanje imen?

957
00:42:15,220 --> 00:42:16,280
Ga držijo v ospredju, kajne?

958
00:42:16,280 --> 00:42:19,290
>> Če bomo žrtvovati design cilj iz
prej, ko smo želeli ohraniti

959
00:42:19,290 --> 00:42:22,650
ime vsakogar, na primer, razporejene,
ali vse številke v fazi razporejene,

960
00:42:22,650 --> 00:42:25,020
Predpostavimo, da imamo
unsorted povezani seznam.

961
00:42:25,020 --> 00:42:29,960
To nas stane le enega ali dva koraka,
kot v primeru Ben in Brian

962
00:42:29,960 --> 00:42:32,750
prej, da vstavite element pri
začetek seznama.

963
00:42:32,750 --> 00:42:36,090
Torej, če nam ni mar za razvrščanje vse
imen, ki se začnejo z ali vse

964
00:42:36,090 --> 00:42:39,660
imena se začnejo s črko B, lahko še vedno
dosegli konstantno čas vstavitve.

965
00:42:39,660 --> 00:42:43,900
Zdaj si gor Alice ali Boba ali katero koli ime
na splošno je še kaj?

966
00:42:43,900 --> 00:42:48,100
To je velik O n deljeno z 26, v
idealen primer, kjer so vsi enakomerno

967
00:42:48,100 --> 00:42:51,190
porazdeljena, kjer obstaja toliko je
kot so Z., kar je verjetno

968
00:42:51,190 --> 00:42:52,220
nerealno.

969
00:42:52,220 --> 00:42:53,880
Ampak to je še vedno linearna.

970
00:42:53,880 --> 00:42:57,120
>> Ampak tukaj smo prišli nazaj do točke
od asimptotičnega zapis počutje

971
00:42:57,120 --> 00:42:58,600
teoretično res.

972
00:42:58,600 --> 00:43:02,960
Toda v resničnem svetu, če trdim, da
moj program lahko storimo nekaj 26-krat

973
00:43:02,960 --> 00:43:06,210
hitreje kot tvoj, katerih program,
boš raje uporabljate?

974
00:43:06,210 --> 00:43:09,660
Tvoje ali moje, ki
je 26-krat hitreje?

975
00:43:09,660 --> 00:43:14,320
Realno, oseba, ki je 26.
krat hitreje, čeprav teoretično

976
00:43:14,320 --> 00:43:18,790
naši algoritmi tečejo v isti
asimptotska teče čas.

977
00:43:18,790 --> 00:43:20,940
>> Dovolite mi, da predlagam drugačen
Rešitev v celoti.

978
00:43:20,940 --> 00:43:24,380
In če to ne bo razstrelil svoj um,
smo iz podatkovnih struktur.

979
00:43:24,380 --> 00:43:27,420
Torej to je to Trie -

980
00:43:27,420 --> 00:43:28,520
nekako neumno ime.

981
00:43:28,520 --> 00:43:32,880
Prihaja od dostopov in Beseda
so napisane Trsta, t-r-i-e, ker

982
00:43:32,880 --> 00:43:34,450
Tečaj iskanje zveni Trsta.

983
00:43:34,450 --> 00:43:36,580
Ampak to je zgodovina
iz besednega Trsta.

984
00:43:36,580 --> 00:43:40,980
>> Torej Trie je res neke vrste drevesa,
in to je tudi igra na te besede.

985
00:43:40,980 --> 00:43:46,330
In čeprav ga ne morete povsem videli
z vizualizacijo, Trie je

986
00:43:46,330 --> 00:43:50,790
drevo strukturirane, kot družinsko drevo
en prednik na vrhu in še mnogo

987
00:43:50,790 --> 00:43:54,530
z vnuki in pravnuki
saj ima na dnu.

988
00:43:54,530 --> 00:43:58,100
Ampak vsako vozlišče v Trsta je matrika.

989
00:43:58,100 --> 00:44:00,680
In to je v paleto - in naj
poenostavljam za trenutek - to je

990
00:44:00,680 --> 00:44:04,600
matrika, v tem primeru, velikosti 26, kjer
vsako vozlišče spet je matrika velikosti

991
00:44:04,600 --> 00:44:09,000
26, kjer Ničti element, ki
matrika predstavlja, in nazadnje

992
00:44:09,000 --> 00:44:11,810
element pri vsaki tak
matrika predstavlja Z.

993
00:44:11,810 --> 00:44:15,520
>> Torej predlagam torej, da so ti podatki
struktura, znan kot Trsta, lahko

994
00:44:15,520 --> 00:44:17,600
Uporablja se tudi za shranjevanje besede.

995
00:44:17,600 --> 00:44:21,740
Smo videli pred nekaj trenutki, kako smo lahko shranite
besede, ali v tem primeru imena, in smo

996
00:44:21,740 --> 00:44:25,440
videl prej, kako lahko shranjujete številke,
ampak, če se osredotočimo na imena ali kitah

997
00:44:25,440 --> 00:44:27,460
je, da vidite, kaj je zanimivo.

998
00:44:27,460 --> 00:44:32,210
Trdim, da je ime Maxwell
znotraj te strukture podatkov.

999
00:44:32,210 --> 00:44:33,730
Kje vidite Maxwell?

1000
00:44:33,730 --> 00:44:35,140
>> ŠTUDENT: [neslišno].

1001
00:44:35,140 --> 00:44:36,240
>> SPEAKER 1: Na levi.

1002
00:44:36,240 --> 00:44:39,910
Torej, kaj je zanimivo s temi podatki
Struktura je namesto trgovini z

1003
00:44:39,910 --> 00:44:46,200
Niz M-A-X-W-E-L-L nagibnica nič, vse
contiguously, kaj si namesto tega

1004
00:44:46,200 --> 00:44:46,890
sledi.

1005
00:44:46,890 --> 00:44:50,510
Če je to Trie kot strukturo podatkov
katerih posamična vozlišča spet matrika,

1006
00:44:50,510 --> 00:44:54,650
in želite shraniti Maxwell, morate najprej
indeks in tako korena je vozlišče, tako

1007
00:44:54,650 --> 00:44:57,810
govoriti, je vrhunsko vozlišče,
na lokaciji M, desno, tako

1008
00:44:57,810 --> 00:44:59,160
približno v sredini.

1009
00:44:59,160 --> 00:45:03,740
In potem od tam, sledite
kazalec otroka vozlišč, tako rekoč.

1010
00:45:03,740 --> 00:45:06,150
Torej v smislu družinskega drevesa,
jo slediti navzdol.

1011
00:45:06,150 --> 00:45:09,030
In da vas vodi v drugo vozlišče
na levi pa, ki je

1012
00:45:09,030 --> 00:45:10,540
samo še en niz.

1013
00:45:10,540 --> 00:45:14,710
>> In potem, če želite shraniti Maxwell,
boste našli kazalec, ki predstavlja

1014
00:45:14,710 --> 00:45:16,430
, Ki je tale.

1015
00:45:16,430 --> 00:45:17,840
Potem greš na naslednje vozlišče.

1016
00:45:17,840 --> 00:45:20,100
In obvestilo - to je razlog, zakaj je slika
malo vara -

1017
00:45:20,100 --> 00:45:21,990
To vozlišče videti super majhen.

1018
00:45:21,990 --> 00:45:26,050
Toda na desni strani to Y in Z.
To je samo avtor je okrnjena

1019
00:45:26,050 --> 00:45:27,630
slike, tako da si dejansko
vidim stvari.

1020
00:45:27,630 --> 00:45:30,400
V nasprotnem primeru to sliko
bi bilo zelo širok.

1021
00:45:30,400 --> 00:45:36,180
Torej, zdaj ste indeks v mestu X, nato
W, potem E, nato L, nato pa L. In kaj je

1022
00:45:36,180 --> 00:45:37,380
to radovednost?

1023
00:45:37,380 --> 00:45:41,250
>> No, če smo z uporabo te vrste novo
da o tem, kako shraniti niz v

1024
00:45:41,250 --> 00:45:44,500
struktura podatkov, morate še vedno
v bistvu odkljukajo v podatkih

1025
00:45:44,500 --> 00:45:47,250
Struktura, da beseda konča tukaj.

1026
00:45:47,250 --> 00:45:50,830
Z drugimi besedami, vsak od teh vozlišč
Nekako se je treba zavedati, da smo

1027
00:45:50,830 --> 00:45:53,500
dejansko sledi vseh teh kazalcev
in puščajo le malo

1028
00:45:53,500 --> 00:45:58,370
Prezla na dnu je te
strukture, ki označuje M-A-X-W-E-L-L je

1029
00:45:58,370 --> 00:46:00,230
dejansko je v tej strukturi podatkov.

1030
00:46:00,230 --> 00:46:02,040
>> Tako smo lahko to stori, kot sledi.

1031
00:46:02,040 --> 00:46:06,810
Vsaka od vozlišč v sliki smo le
žaga ima eno, matrike velikosti 27.

1032
00:46:06,810 --> 00:46:10,550
In to je zdaj 27, ker je v p nastavite šest,
bomo dejansko vam opuščaj,

1033
00:46:10,550 --> 00:46:13,590
tako da bomo lahko imeli imena, kot O'Reilly
in druge s opuščaji.

1034
00:46:13,590 --> 00:46:14,820
Ampak isto idejo.

1035
00:46:14,820 --> 00:46:17,710
Vsak od teh elementov
matrične kaže na struct

1036
00:46:17,710 --> 00:46:19,320
vozlišče, tako da samo vozlišče.

1037
00:46:19,320 --> 00:46:21,430
Tako da je to zelo spominja
našega povezanega seznama.

1038
00:46:21,430 --> 00:46:24,550
>> In potem imam logičnim, kar bom
klic besedo, ki je šele bo

1039
00:46:24,550 --> 00:46:29,120
Res, če beseda konča na ta
vozlišče v drevesu.

1040
00:46:29,120 --> 00:46:32,870
To dejansko pomeni malo
trikotnik smo videli pred nekaj trenutki.

1041
00:46:32,870 --> 00:46:37,190
Torej, če se beseda konča na tem vozlišču v
drevo, da bo beseda polje bilo res,

1042
00:46:37,190 --> 00:46:41,990
, ki je konceptualno preverjanje off, ali
smo risanje ta trikotnik, da obstaja

1043
00:46:41,990 --> 00:46:44,080
je tu ključna beseda.

1044
00:46:44,080 --> 00:46:45,120
>> Torej je to Trie.

1045
00:46:45,120 --> 00:46:48,540
In zdaj vprašanje je, kaj
je svoj čas teče?

1046
00:46:48,540 --> 00:46:49,930
Je velik O n?

1047
00:46:49,930 --> 00:46:51,410
Ali je kaj drugega?

1048
00:46:51,410 --> 00:46:57,330
No, če ste n imena v teh podatkov
struktura, Maxwell so le eden

1049
00:46:57,330 --> 00:47:02,330
jim, kaj je čas teče
vstavljanje ali iskanju Maxwell?

1050
00:47:02,330 --> 00:47:06,230

1051
00:47:06,230 --> 00:47:09,050
Kaj je čas delovanja
vstavljanje Maxwell?

1052
00:47:09,050 --> 00:47:11,740
Če je n druga imena
že na mizi?

1053
00:47:11,740 --> 00:47:12,507
Ja?

1054
00:47:12,507 --> 00:47:15,429
>> ŠTUDENT: [neslišno].

1055
00:47:15,429 --> 00:47:17,550
>> SPEAKER 1: Ja, to je dolžina
imena, kajne?

1056
00:47:17,550 --> 00:47:24,420
Torej M-x-w-e-l-l, da se zdi, kot to
Algoritem je velik O sedem.

1057
00:47:24,420 --> 00:47:26,580
Zdaj je seveda ime
različno dolgi.

1058
00:47:26,580 --> 00:47:27,380
Morda je to kratko ime.

1059
00:47:27,380 --> 00:47:28,600
Mogoče je daljša imena.

1060
00:47:28,600 --> 00:47:33,390
Toda kaj je ključ v tem, da
je nespremenjeno število.

1061
00:47:33,390 --> 00:47:36,810
In morda to ni res konstanten,
Toda Bog, če je realno, v

1062
00:47:36,810 --> 00:47:41,570
slovar, tam je verjetno nekaj omejitev
na število črk v

1063
00:47:41,570 --> 00:47:43,820
Ime osebe v določeni državi.

1064
00:47:43,820 --> 00:47:46,940
>> In tako lahko sklepamo, da
vrednost je konstantna.

1065
00:47:46,940 --> 00:47:47,750
Ne vem, kaj je.

1066
00:47:47,750 --> 00:47:50,440
Verjetno je večja od
mislimo, da je.

1067
00:47:50,440 --> 00:47:52,720
Zato, ker je vedno nekaj kotiček
Primer z noro dolgo ime.

1068
00:47:52,720 --> 00:47:56,360
Torej, kaj je to k poklicati, vendar je še vedno
stalna verjetno, ker je vsak

1069
00:47:56,360 --> 00:48:00,190
ime v svetu, vsaj v
predvsem država, je, da je dolžina ali

1070
00:48:00,190 --> 00:48:01,780
krajši, tako da je konstantna.

1071
00:48:01,780 --> 00:48:04,490
Toda, ko smo povedal, da je nekaj velikega
O izmed konstantno vrednost, kaj je to

1072
00:48:04,490 --> 00:48:07,760
res enaka?

1073
00:48:07,760 --> 00:48:10,420
To je res ista stvar
kot pravim stalno čas.

1074
00:48:10,420 --> 00:48:11,530
>> Zdaj smo nekako varanje, kajne?

1075
00:48:11,530 --> 00:48:15,340
Mi smo nekako vplivno nekaj teorije
Tukaj reči, da dobro, da bi v K

1076
00:48:15,340 --> 00:48:17,450
res samo odredi enega,
in je konstantna čas.

1077
00:48:17,450 --> 00:48:18,200
Vendar je res.

1078
00:48:18,200 --> 00:48:22,550
Ker je ključni vpogled v tem, da
če smo n imena že v tem

1079
00:48:22,550 --> 00:48:26,010
podatkovne strukture, in mi vložek Maxwell,
je čas, ki ga nas popelje

1080
00:48:26,010 --> 00:48:29,530
vstavite Maxwell na vseh prizadetih
s tem, koliko drugih ljudi

1081
00:48:29,530 --> 00:48:31,100
v podatkovno strukturo?

1082
00:48:31,100 --> 00:48:31,670
Ne zdi, da bo.

1083
00:48:31,670 --> 00:48:36,280
Če bi imel milijardo več elementov za to
Trie in nato vstavite Maxwell, ki je

1084
00:48:36,280 --> 00:48:38,650
je sploh vpliva?

1085
00:48:38,650 --> 00:48:39,050
Število

1086
00:48:39,050 --> 00:48:42,950
In to je za razliko od vseh podatkov dan
strukture smo videli doslej, kjer

1087
00:48:42,950 --> 00:48:46,820
čas vaše algoritem teče, je
popolnoma neodvisna od koliko

1088
00:48:46,820 --> 00:48:51,430
stvar je ali ni že
V tej strukturi podatkov.

1089
00:48:51,430 --> 00:48:54,650
>> In tako s tem daje sedaj je
Priložnost za p niz šestih, ki bo

1090
00:48:54,650 --> 00:48:58,310
spet vključevalo izvajanje svoje
črkovalnik, branje na 150.000

1091
00:48:58,310 --> 00:49:01,050
besede, kako najbolje hraniti, da
ni nujno očitna.

1092
00:49:01,050 --> 00:49:04,030
In čeprav sem hrepenela, da bi našli
sveti gral, ne vem

1093
00:49:04,030 --> 00:49:05,330
trdijo, da je Trie.

1094
00:49:05,330 --> 00:49:09,810
V resnici, lahko razpršena tabela zelo dobro
izkaže, da je veliko bolj učinkovito.

1095
00:49:09,810 --> 00:49:10,830
Ampak to so le -

1096
00:49:10,830 --> 00:49:14,620
to je samo ena od konstrukcijskih odločitev
boste morali narediti.

1097
00:49:14,620 --> 00:49:18,920
>> Toda v zapiranju vzemimo 50 ali tako
sekund, da si oglejte, kaj se skriva

1098
00:49:18,920 --> 00:49:22,190
naprej naslednji teden in naprej smo prehod
od tega ukazni vrstici

1099
00:49:22,190 --> 00:49:26,220
svetu, če C programi na stvari spletu
temelji in jeziki, kot so PHP in

1100
00:49:26,220 --> 00:49:30,350
JavaScript in internet sam,
protokolov, kot so HTTP, ki ste

1101
00:49:30,350 --> 00:49:32,870
samoumevno let
sedaj, in natipkana najbolje vsak

1102
00:49:32,870 --> 00:49:34,440
dan, morda, ali videli.

1103
00:49:34,440 --> 00:49:37,420
In bomo začeli lupine nazaj
plasti, kaj je internet.

1104
00:49:37,420 --> 00:49:40,650
In kakšna je koda, ki
osnovane današnji orodja.

1105
00:49:40,650 --> 00:49:43,230
Torej 50 sekund te teaser tukaj.

1106
00:49:43,230 --> 00:49:46,570
Dam ti bojevniki Net.

1107
00:49:46,570 --> 00:49:51,370
>> [Predvajanje videa]

1108
00:49:51,370 --> 00:49:56,764
>> -Prišel je s sporočilom.

1109
00:49:56,764 --> 00:50:00,687
S protokolom vse svoje lastne.

1110
00:50:00,687 --> 00:50:13,370

1111
00:50:13,370 --> 00:50:19,780
Prišel je v svetu krutih požarnih zidov,
neskrbni usmerjevalniki, in nevarnosti daleč

1112
00:50:19,780 --> 00:50:22,600
hujše od smrti.

1113
00:50:22,600 --> 00:50:23,590
Hiter je.

1114
00:50:23,590 --> 00:50:25,300
On je močan.

1115
00:50:25,300 --> 00:50:27,700
On je TCPIP.

1116
00:50:27,700 --> 00:50:30,420
In ima svoj naslov.

1117
00:50:30,420 --> 00:50:32,920

1118
00:50:32,920 --> 00:50:34,590
Bojevniki Net.

1119
00:50:34,590 --> 00:50:35,290
>> [END predvajanje videa]

1120
00:50:35,290 --> 00:50:38,070
>> SPEAKER 1: To je, kako internet
deluje kot naslednji teden.

1121
00:50:38,070 --> 00:50:40,406