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

2
00:00:11,860 --> 00:00:13,120
>> GARSIAKALBIS 1: Gerai, kad mes atgal.

3
00:00:13,120 --> 00:00:14,480
Sveiki atvykę į CS50.

4
00:00:14,480 --> 00:00:16,510
Tai savaitės septynių pabaiga.

5
00:00:16,510 --> 00:00:20,200
Taigi priminti, kad paskutinį kartą, mes pradėjome
žiūri truputį sudėtingesnės

6
00:00:20,200 --> 00:00:21,100
duomenų struktūros.

7
00:00:21,100 --> 00:00:25,110
Kadangi iki šiol, visi mes turėjome tikrai
mūsų žinioje buvo tai, masyvo.

8
00:00:25,110 --> 00:00:29,340
>> Bet kol mes išmeskite masyvo taip ne
visi, kad įdomus, o iš tiesų

9
00:00:29,340 --> 00:00:33,570
iš tikrųjų yra, kas yra kai kurių
pliusai šį paprastą duomenų

10
00:00:33,570 --> 00:00:34,560
struktūra iki šiol?

11
00:00:34,560 --> 00:00:36,110
Kas tai gerai?

12
00:00:36,110 --> 00:00:39,450
Tiek, kiek mes matėme?

13
00:00:39,450 --> 00:00:42,540
Ką turite?

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

15
00:00:44,028 --> 00:00:45,020
>> STUDENTŲ: [nesigirdi].

16
00:00:45,020 --> 00:00:45,395
>> GARSIAKALBIS 1: Kas tai?

17
00:00:45,395 --> 00:00:46,410
>> STUDENTŲ: [nesigirdi].

18
00:00:46,410 --> 00:00:47,000
>> GARSIAKALBIS 1: fiksuotas dydis.

19
00:00:47,000 --> 00:00:51,260
Gerai, tai kodėl yra fiksuoto dydžio gerai nors?

20
00:00:51,260 --> 00:00:53,180
>> STUDENTŲ: [nesigirdi].

21
00:00:53,180 --> 00:00:56,240
>> GARSIAKALBIS 1: Gerai, kad tai efektyvus
ta prasme, kad galite skirti

22
00:00:56,240 --> 00:01:00,070
fiksuoto dydžio erdvę, kuri, tikiuosi,
Būtent tiek, kiek

23
00:01:00,070 --> 00:01:01,180
vietos, kiek norite.

24
00:01:01,180 --> 00:01:02,720
Taigi, kad gali būti visiškai pliusas.

25
00:01:02,720 --> 00:01:06,530
>> Kas yra kitas šalutinis masyvo?

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

27
00:01:07,610 --> 00:01:08,750
>> STUDENTŲ: [nesigirdi].

28
00:01:08,750 --> 00:01:09,550
>> GARSIAKALBIS 1: Visi - atsiprašau?

29
00:01:09,550 --> 00:01:11,270
>> STUDENTŲ: [nesigirdi].

30
00:01:11,270 --> 00:01:13,620
>> GARSIAKALBIS 1: Visi atmintyje dėžės
arba vienas šalia kito.

31
00:01:13,620 --> 00:01:15,220
Ir tai naudinga - kodėl?

32
00:01:15,220 --> 00:01:15,970
Tai visiškai teisinga.

33
00:01:15,970 --> 00:01:18,611
Bet kaip mes galime pasinaudoti, kad tiesa?

34
00:01:18,611 --> 00:01:21,500
>> STUDENTŲ: [nesigirdi].

35
00:01:21,500 --> 00:01:24,490
>> GARSIAKALBIS 1: Būtent, mes galime sekti
kur viskas yra tik žinant

36
00:01:24,490 --> 00:01:28,560
vienas adresas, ty adresas
Pirmas baitas tos atminties riekė.

37
00:01:28,560 --> 00:01:30,420
Arba eilutės atveju
iš pirmųjų adresas

38
00:01:30,420 --> 00:01:31,460
char tą eilutę.

39
00:01:31,460 --> 00:01:33,330
Ir iš ten, mes galime rasti
stringo pabaigos.

40
00:01:33,330 --> 00:01:35,710
Mes galime rasti Antroji dalis,
Trečiasis elementas, ir kt.

41
00:01:35,710 --> 00:01:38,740
>> Ir taip išgalvotas būdas aprašyti, kad
būdinga tai, kad matricos mums

42
00:01:38,740 --> 00:01:40,020
laisvosios kreipties.

43
00:01:40,020 --> 00:01:44,330
Tiesiog naudojant kvadratinės laikiklis
notacijos ir skaičius, galite pereiti prie

44
00:01:44,330 --> 00:01:48,070
specifinis elementas masyve
nuolat laiko, didelis O

45
00:01:48,070 --> 00:01:49,810
viena, taip sakant.

46
00:01:49,810 --> 00:01:51,080
>> Bet ten buvo keletas praradimas.

47
00:01:51,080 --> 00:01:53,110
Ką masyvas negali padaryti labai lengvai?

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

49
00:01:55,810 --> 00:01:57,170
Kas tai nėra gerai?

50
00:01:57,170 --> 00:01:58,810
>> STUDENTŲ: [nesigirdi].

51
00:01:58,810 --> 00:01:59,860
>> GARSIAKALBIS 1: Kas tai?

52
00:01:59,860 --> 00:02:00,530
>> STUDENTŲ: [nesigirdi].

53
00:02:00,530 --> 00:02:01,460
>> GARSIAKALBIS 1: Išplečiamas dydžio.

54
00:02:01,460 --> 00:02:04,800
Taigi iš masyvo praradimas yra
tiksliai, kas priešinga

55
00:02:04,800 --> 00:02:05,540
ilguoju yra.

56
00:02:05,540 --> 00:02:07,610
Taigi vienas praradimas yra
kad tai fiksuoto dydžio.

57
00:02:07,610 --> 00:02:09,400
Taigi jūs tikrai negali augti.

58
00:02:09,400 --> 00:02:13,510
Galite perskirstyti didesnį riekė
atmintis, ir tada perkelti senus elementus

59
00:02:13,510 --> 00:02:14,460
į naują masyvą.

60
00:02:14,460 --> 00:02:18,060
Ir tada nemokamai senas masyvas, už
Pavyzdžiui, naudojant malloc arba panašų

61
00:02:18,060 --> 00:02:21,180
funkcija vadinama realloc, kuris
perskirstys atmintį.

62
00:02:21,180 --> 00:02:25,490
>> Realloc, kaip panaikinti, bando duoti jums
atminties tai šalia masyvo

63
00:02:25,490 --> 00:02:26,610
kad jūs jau turite.

64
00:02:26,610 --> 00:02:28,740
Bet tai gali perkelti daiktus
aplink apskritai.

65
00:02:28,740 --> 00:02:30,710
Bet trumpai tariant, kad brangu, tiesa?

66
00:02:30,710 --> 00:02:33,440
Nes jei jūs turite atminties riekė
tai dydis, bet tikrai noriu,

67
00:02:33,440 --> 00:02:36,710
tokio dydžio, ir jūs norite išsaugoti
originalūs elementai, jūs turite

68
00:02:36,710 --> 00:02:40,510
maždaug linijinis laikas kopijavimo procesas
kad turi įvykti nuo

69
00:02:40,510 --> 00:02:41,900
Esu masyvas naujas.

70
00:02:41,900 --> 00:02:44,630
O realybė klausia veikti
sistema vėl ir vėl ir

71
00:02:44,630 --> 00:02:48,340
vėl didelių gabaliukus atmintis gali pradėti
jums kainuoti šiek tiek laiko taip pat.

72
00:02:48,340 --> 00:02:52,250
Taigi tai tiek palaiminimas ir prakeikimas į
nuslėpti, kad šios matricos

73
00:02:52,250 --> 00:02:53,860
yra fiksuoto dydžio.

74
00:02:53,860 --> 00:02:56,790
Bet jei mes pristatome vietoj kažką
kaip šis, kurį mes vadinami Tinkliniai

75
00:02:56,790 --> 00:03:00,580
sąrašas, gausime keletą ilguoju ir
keletas praradimas, čia taip pat.

76
00:03:00,580 --> 00:03:05,780
>> Taigi susijęs sąrašas yra tiesiog duomenų
struktūra sudaryta iš C structs šiame

77
00:03:05,780 --> 00:03:09,850
atveju, jei konstrukto, priminti, yra tik
vieną ar daugiau specifinių konteineris

78
00:03:09,850 --> 00:03:11,100
tipų kintamųjų.

79
00:03:11,100 --> 00:03:16,110
Šiuo atveju, ką duomenų tipai
Atrodo, kad viduje struct kad

80
00:03:16,110 --> 00:03:17,600
Paskutinį kartą mes vadinamas mazgą?

81
00:03:17,600 --> 00:03:19,380
Kiekvienas iš šių stačiakampių yra mazgas.

82
00:03:19,380 --> 00:03:22,660
Ir kiekvienas iš mažesnius stačiakampius
viduje ji yra duomenų tipas.

83
00:03:22,660 --> 00:03:25,300
Kokios gi mes pasakyti
jie buvo pirmadienį?

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

85
00:03:26,478 --> 00:03:27,870
>> STUDENTŲ: [nesigirdi].

86
00:03:27,870 --> 00:03:30,721
>> GARSIAKALBIS 1: kintama ir rodyklė, arba
tiksliau, int n reikšmę,

87
00:03:30,721 --> 00:03:32,180
ir apačioje rodyklę.

88
00:03:32,180 --> 00:03:35,360
Tiek tų atsitikti, kad 32 bitai, bent
jau patiko šį CS50 kompiuteryje

89
00:03:35,360 --> 00:03:37,980
Prietaisą, ir todėl jie
parengti vienodai dydžio.

90
00:03:37,980 --> 00:03:42,260
>> Taigi, kas yra naudojant žymeklį
nors ir atrodo?

91
00:03:42,260 --> 00:03:47,690
Kodėl pridėti šį rodyklę dabar, kai matricos buvo
toks gražus ir švarus ir paprastas?

92
00:03:47,690 --> 00:03:50,460
Kas yra rodyklė darai
mums kiekvienoje iš šių mazgų?

93
00:03:50,460 --> 00:03:52,160
>> STUDENTŲ: [negirdimi].

94
00:03:52,160 --> 00:03:52,465
>> GARSIAKALBIS 1: Būtent.

95
00:03:52,465 --> 00:03:54,120
Tai sakau, jei
Kitas vienas.

96
00:03:54,120 --> 00:03:57,350
Taigi aš tarsi naudoti analogiją
naudojant siūlai rūšiuoti

97
00:03:57,350 --> 00:03:59,180
thread šiuos mazgus kartu.

98
00:03:59,180 --> 00:04:01,760
Ir tai būtent tai, ką mes darome su
patarimų, nes kiekvienas iš jų

99
00:04:01,760 --> 00:04:06,360
gabaliukus atmintį gali arba negali būti
greta, atgal atgal atgal

100
00:04:06,360 --> 00:04:09,500
viduje RAM, nes kiekvieną kartą, kai
skambinti malloc sako, duok man pakankamai

101
00:04:09,500 --> 00:04:12,510
baitų naują mazgas, jis gali
būti čia arba ji gali būti čia.

102
00:04:12,510 --> 00:04:13,120
Tai gali būti čia.

103
00:04:13,120 --> 00:04:13,730
Tai gali būti čia.

104
00:04:13,730 --> 00:04:14,640
Jūs tiesiog nežinau.

105
00:04:14,640 --> 00:04:17,880
>> Tačiau naudojant rodykles į adresais
tie mazgai, galite dygsnio juos

106
00:04:17,880 --> 00:04:22,370
kartu taip, kad atrodo vizualiai
panašus į sąrašą, net jei šie dalykai yra

107
00:04:22,370 --> 00:04:26,770
visi išsikeroti visoje savo vieną ar
savo du ar savo keturių gigabaitų RAM

108
00:04:26,770 --> 00:04:28,760
viduje savo kompiuterį.

109
00:04:28,760 --> 00:04:33,230
>> Taigi neigiama, tada,
susijęs sąrašas yra kas?

110
00:04:33,230 --> 00:04:34,670
Kas yra kaina, kurią mes esame
matyt moka?

111
00:04:34,670 --> 00:04:36,010
>> STUDENTŲ: [nesigirdi].

112
00:04:36,010 --> 00:04:36,920
>> GARSIAKALBIS 1: Daugiau vietos, tiesa?

113
00:04:36,920 --> 00:04:39,340
Mes šiuo atveju dvigubai sumą
vietos, nes mes jau dingo

114
00:04:39,340 --> 00:04:43,500
nuo 32 bitų kiekvieno mazgo, kiekvienam
int, todėl dabar 64 bitus, nes mes turime

115
00:04:43,500 --> 00:04:45,050
išlaikyti aplink žymeklį, taip pat.

116
00:04:45,050 --> 00:04:48,860
Jūs gaunate daugiau veiksmingumo, jei jūsų konstrukto
yra didesnis nei šis paprastas dalykas.

117
00:04:48,860 --> 00:04:52,020
Jei jūs iš tikrųjų turi studentą viduje
kurių eilučių pora už

118
00:04:52,020 --> 00:04:55,430
pavadinimas ir namo, gal ID numeris,
gal kai kurie kiti laukai nedaugiau.

119
00:04:55,430 --> 00:04:59,000
>> Taigi, jei turite pakankamai didelis struct,
tada gal su rodykle kaina

120
00:04:59,000 --> 00:05:00,010
nėra tokia baisi.

121
00:05:00,010 --> 00:05:03,570
Tai kampinio atveju tiek tuo, kad
mes saugojimo toks paprastas primityvus

122
00:05:03,570 --> 00:05:04,760
viduje susijusį sąrašą.

123
00:05:04,760 --> 00:05:05,790
Bet esmė yra ta pati.

124
00:05:05,790 --> 00:05:08,230
Jūs tikrai išleidžia daugiau
atminties, bet jūs gaunate

125
00:05:08,230 --> 00:05:08,990
lankstumą.

126
00:05:08,990 --> 00:05:12,280
Nes dabar jei noriu pridėti elementą
prie šio sąrašo pradžioje

127
00:05:12,280 --> 00:05:14,340
Turiu skirti naują mazgas.

128
00:05:14,340 --> 00:05:17,180
Ir aš turiu tiesiog atnaujinti tuos
rodyklės kažkaip tiesiog perkelti

129
00:05:17,180 --> 00:05:17,980
keletas patarimų aplink.

130
00:05:17,980 --> 00:05:20,580
>> Jei aš noriu įdėti kažką į
viduryje sąraše, aš neturiu

131
00:05:20,580 --> 00:05:24,410
stumti visus į šalį kaip tai darėme
savaičių anksčiau su mūsų savanorių, kurie

132
00:05:24,410 --> 00:05:25,700
atstovavo masyvą.

133
00:05:25,700 --> 00:05:29,470
Galiu tik skirti naują mazgas ir
tada tiesiog nukreipkite rodykles

134
00:05:29,470 --> 00:05:32,290
įvairiomis kryptimis, nes ji neturi
turi likti faktinis

135
00:05:32,290 --> 00:05:35,670
atminties tiesa linija kaip aš sudarytas
tai čia ekrane.

136
00:05:35,670 --> 00:05:38,400
>> Ir tada galiausiai, jei norite įterpti
kažkas ne iš sąrašo pabaigoje, tai

137
00:05:38,400 --> 00:05:39,210
net lengviau.

138
00:05:39,210 --> 00:05:43,320
Tai tarsi savavališkai žymėjimą,
bet 34 yra rodyklė, spėti.

139
00:05:43,320 --> 00:05:46,710
Kas yra jos žymeklis labiausiai vertė
tikėtina, sudarytas tarsi metai

140
00:05:46,710 --> 00:05:47,700
mokykla antena ten?

141
00:05:47,700 --> 00:05:48,920
>> STUDENTŲ: [nesigirdi].

142
00:05:48,920 --> 00:05:49,900
>> GARSIAKALBIS 1: Tai tikriausiai null.

143
00:05:49,900 --> 00:05:52,710
Ir iš tiesų tai yra vienas autoriaus
atstovavimas null.

144
00:05:52,710 --> 00:05:56,310
Ir tai niekinis, nes jūs visiškai
reikia žinoti, kur iš Tinkliniai pabaiga

145
00:05:56,310 --> 00:06:00,050
sąrašas, kitaip jūs nuolat taip ir
taip ir šiuos rodykles

146
00:06:00,050 --> 00:06:01,170
tam tikru šiukšlių vertę.

147
00:06:01,170 --> 00:06:06,230
Taigi null reikš, kad nėra
daugiau mazgų į skaičiaus 34 dešinėje

148
00:06:06,230 --> 00:06:07,200
šiuo atveju.

149
00:06:07,200 --> 00:06:10,270
>> Taigi, mes siūlome, kad galėtume įgyvendinti
tai kodu mazgas.

150
00:06:10,270 --> 00:06:12,130
Ir mes matėme šios rūšies
sintaksė anksčiau.

151
00:06:12,130 --> 00:06:15,090
Typedef tik apibrėžia naują tipą
mus, suteikia mums sinonimas kaip

152
00:06:15,090 --> 00:06:17,100
eilutė buvo skirta char *.

153
00:06:17,100 --> 00:06:21,030
Tokiu atveju, jis ketina duoti mums
Sutrumpintas žymėjimas, kad konstrukto mazgas

154
00:06:21,030 --> 00:06:24,010
gali vietoj tiesiog būti parašyta, kaip
mazgas, kuris yra daug švaresnis.

155
00:06:24,010 --> 00:06:25,360
Tai daug mažiau išsami.

156
00:06:25,360 --> 00:06:30,080
>> Viduje mazgas, matyt int
vadinamas n, ir tada konstrukto mazgas *

157
00:06:30,080 --> 00:06:34,670
o tai reiškia, ką mes norėjome
rodyklės reiškia, žymeklį į kitą

158
00:06:34,670 --> 00:06:36,940
mazgas patį duomenų tipą.

159
00:06:36,940 --> 00:06:40,300
Ir aš siūlau, kad galėtume įgyvendinti
paieškos funkcija, kaip šis, kuris tuo

160
00:06:40,300 --> 00:06:41,890
Iš pirmo žvilgsnio gali atrodyti,
šiek tiek sudėtinga.

161
00:06:41,890 --> 00:06:43,330
Bet pažiūrėkime, tai kontekste.

162
00:06:43,330 --> 00:06:45,480
>> Leiskite man pereiti prie prietaiso čia.

163
00:06:45,480 --> 00:06:48,460
Leiskite man atverti failą pavadinimu
sąrašas nulinis taškas val.

164
00:06:48,460 --> 00:06:53,950
Ir tai yra tik apibrėžimo mes
tik pamačiau prieš akimirką Dėl šios duomenų

165
00:06:53,950 --> 00:06:55,390
tipas vadinamas mazgas.

166
00:06:55,390 --> 00:06:57,350
Taigi, mes įdėti, kad į dot h failą.

167
00:06:57,350 --> 00:07:01,430
>> Ir kaip žemę, nors tai
programa, kad jūs apie pamatyti, yra

168
00:07:01,430 --> 00:07:05,410
ne visi, kad sudėtinga, tai tikrai
konvencija rašant programą

169
00:07:05,410 --> 00:07:10,270
įdėti dalykų, pavyzdžiui, duomenų tipų, traukti
konstantos kartais viduje jūsų

170
00:07:10,270 --> 00:07:13,210
failo antraštės ir nebūtinai
Jūsų failas C, žinoma, kai jūsų

171
00:07:13,210 --> 00:07:17,370
programos gauti didesni ir didesni, todėl, kad
jūs žinote, kur ieškoti tiek

172
00:07:17,370 --> 00:07:20,840
dokumentus tam tikrais atvejais, arba
už pagrindai, pavyzdžiui, tai, kad

173
00:07:20,840 --> 00:07:22,360
apibrėžimas kai tipo.

174
00:07:22,360 --> 00:07:25,680
>> Jei aš dabar atverti sąrašą nulio taškas
c, pastebėti keletą dalykų.

175
00:07:25,680 --> 00:07:29,090
Jis apima keletą antraščių failus, dauguma
iš kurių mes matėme anksčiau.

176
00:07:29,090 --> 00:07:31,980
Ji apima savo antraštės failą.

177
00:07:31,980 --> 00:07:35,200
>> Ir kaip žemę, kodėl tai dvigubai
citatos čia, o ne kampu

178
00:07:35,200 --> 00:07:38,340
kronšteinai ant linijos, kad
Aš pabrėžė ten?

179
00:07:38,340 --> 00:07:39,180
>> STUDENTŲ: [nesigirdi].

180
00:07:39,180 --> 00:07:40,460
>> GARSIAKALBIS 1: Taip taip, tai vietos failas.

181
00:07:40,460 --> 00:07:44,300
Taigi, jei tai vietos failą savo čia
on line 15 Pavyzdžiui, jūs naudojate

182
00:07:44,300 --> 00:07:46,570
į kabutes, o ne
iš kampuotų skliaustuose.

183
00:07:46,570 --> 00:07:48,270
>> Dabar tai yra rūšies įdomus.

184
00:07:48,270 --> 00:07:51,830
Atkreipkite dėmesį, kad aš paskelbė pasaulio
kintamasis šioje programoje eilutė 18

185
00:07:51,830 --> 00:07:55,910
vadinama pirma, idėja, tai
bus rodyklė į pirmąjį

186
00:07:55,910 --> 00:07:59,190
mazgas mano susietą sąrašą, ir aš
inicializuoti tai nulis, nes aš

187
00:07:59,190 --> 00:08:02,310
neskiriami bet tikrasis
mazgai tik dar.

188
00:08:02,310 --> 00:08:07,570
>> Taigi tai reiškia, pavaizduotomis piktogramo, ką mes
pamačiau momentas prieš pat paveikslėlyje kaip

189
00:08:07,570 --> 00:08:10,090
kad toli rodyklė
kairėje pusėje.

190
00:08:10,090 --> 00:08:12,260
Taigi dabar, kad rodyklė
neturi rodyklę.

191
00:08:12,260 --> 00:08:14,590
Ji vietoj yra tik tuščias.

192
00:08:14,590 --> 00:08:17,880
Bet tai reiškia, kas bus
adresas pirmasis faktinis

193
00:08:17,880 --> 00:08:19,480
mazgas šiame sąraše.

194
00:08:19,480 --> 00:08:22,120
Taigi, aš įdiegėme yra pasaulinė
nes, kaip pamatysite, visa tai

195
00:08:22,120 --> 00:08:25,310
programa neveikia gyvenime yra įdiegti
susijęs sąrašas už mane.

196
00:08:25,310 --> 00:08:27,050
>> Dabar aš turiu keletą prototipų čia.

197
00:08:27,050 --> 00:08:31,190
Aš nusprendė įgyvendinti funkcijas, pavyzdžiui,
išbraukta, intarpas, ieškoti, ir

198
00:08:31,190 --> 00:08:31,740
Sankryþos -

199
00:08:31,740 --> 00:08:35,210
paskutinis tiesiog yra pėsčiomis visoje
sąrašas, spausdinti jo elementus.

200
00:08:35,210 --> 00:08:36,750
Ir dabar čia yra pagrindinis mano rutina.

201
00:08:36,750 --> 00:08:39,890
Ir mes ne praleidžia per daug laiko
tai, nes tai yra tarsi, tikiuosi

202
00:08:39,890 --> 00:08:41,780
sena skrybėlę dabar.

203
00:08:41,780 --> 00:08:45,370
>> Aš ruošiuosi padaryti taip,
o vartotojo bendradarbiauja.

204
00:08:45,370 --> 00:08:47,300
Taigi vienas, aš ruošiuosi spausdinti
iš šio meniu.

205
00:08:47,300 --> 00:08:49,420
Ir aš suformatuotas kaip
švariai, kaip galėčiau.

206
00:08:49,420 --> 00:08:52,240
Jei vartotojas įveda į vieną, tai reiškia, kad
jie nori ištrinti kažką.

207
00:08:52,240 --> 00:08:54,560
Jei vartotojas įveda į dvi dalis, tai reiškia, kad
jie nori įterpti kažką.

208
00:08:54,560 --> 00:08:55,930
Ir kt.

209
00:08:55,930 --> 00:08:58,270
Aš ruošiuosi tada greitai
tada komandą.

210
00:08:58,270 --> 00:08:59,300
Ir tada aš ruošiuosi naudoti GetInt.

211
00:08:59,300 --> 00:09:02,790
>> Taigi tai yra tikrai paprasta menuing
sąsaja, kur jūs tiesiog įrašykite

212
00:09:02,790 --> 00:09:05,270
numeris žemėlapių į vieną
iš šių komandų.

213
00:09:05,270 --> 00:09:08,730
Ir dabar turiu gražų švarų jungiklį
pareiškimas, kad ketina įjungti

214
00:09:08,730 --> 00:09:10,090
ką vartotojas turi įvesti in

215
00:09:10,090 --> 00:09:12,180
Ir jei jie atspausdinti vieną, aš
skambinti i ¹ trinti ir pertrauka.

216
00:09:12,180 --> 00:09:14,380
Jei jie spausdinami du, aš
skambinti įterpti ir lūžti.

217
00:09:14,380 --> 00:09:16,490
>> Ir dabar pastebite, aš įdėti kiekvienas
iš jų toje pačioje eilutėje.

218
00:09:16,490 --> 00:09:18,360
Tai tik stilistinė sprendimas.

219
00:09:18,360 --> 00:09:20,210
Paprastai mes matėme kažką
kaip šis.

220
00:09:20,210 --> 00:09:23,260
Bet aš tiesiog nusprendžiau, tiesą sakant, savo programą
atrodė įskaitomas, nes

221
00:09:23,260 --> 00:09:25,980
tai buvo tik keturias bylas
tiesiog įtraukti ją, kaip šis.

222
00:09:25,980 --> 00:09:28,360
Visiškai teisėtas naudojimas stiliaus.

223
00:09:28,360 --> 00:09:31,480
Ir aš ruošiuosi tai padaryti tol, kol
vartotojas dar įvedėte nulio, kurią aš

224
00:09:31,480 --> 00:09:33,910
nusprendė reiškia jie nori mesti rūkyti.

225
00:09:33,910 --> 00:09:36,630
>> Taigi dabar pastebėsite, ką aš
ketina padaryti čia.

226
00:09:36,630 --> 00:09:38,650
Aš ruošiuosi išlaisvinti sąrašą matyt.

227
00:09:38,650 --> 00:09:40,230
Bet daugiau apie tai vos akimirką.

228
00:09:40,230 --> 00:09:41,640
Tegul pirmasis paleisti šią programą.

229
00:09:41,640 --> 00:09:45,250
Taigi leiskite man padaryti didesnį terminalą
langas, taškas velniop sąrašas 0.

230
00:09:45,250 --> 00:09:49,510
Aš ruošiuosi eiti į priekį ir įterpti pagal
rašyti du, kaip 50 numeris, o dabar

231
00:09:49,510 --> 00:09:51,590
pamatysite sąrašas dabar yra 50.

232
00:09:51,590 --> 00:09:53,380
Ir mano tekstas tiesiog išeis šiek tiek.

233
00:09:53,380 --> 00:09:55,940
Taigi dabar pastebėti sąraše yra
skaičius 50.

234
00:09:55,940 --> 00:09:58,220
>> Darykime kitą lapelį, atsižvelgiant du.

235
00:09:58,220 --> 00:10:01,630
Leiskite įvesti į kaip vienas skaičius.

236
00:10:01,630 --> 00:10:03,940
Sąrašas dabar yra viena, o po to 50.

237
00:10:03,940 --> 00:10:06,020
Taigi tai yra tik teksto atstovavimas
iš sąrašo.

238
00:10:06,020 --> 00:10:10,550
Ir tegul įterpti dar vieną numerį, kaip
skaičius 42, kuris, tikiuosi,

239
00:10:10,550 --> 00:10:14,620
ketina baigti per vidurį, nes
Tai visų pirma rūšių programos, kurią ji

240
00:10:14,620 --> 00:10:16,320
elementus, kadangi jis įterpia juos.

241
00:10:16,320 --> 00:10:17,220
Taigi, mes turime jį.

242
00:10:17,220 --> 00:10:20,730
Super paprasta programa, kuri galėtų
visiškai naudojo masyvą, bet aš

243
00:10:20,730 --> 00:10:23,280
atsitiktų būti naudojant susietą sąrašą
tik tiek galiu dinamiškai

244
00:10:23,280 --> 00:10:24,610
plėstis ir trauktis jį.

245
00:10:24,610 --> 00:10:28,470
>> Taigi, galime imtis paieškai atrodo, jei aš
paleisti komandą tris, aš noriu ieškoti

246
00:10:28,470 --> 00:10:31,040
už, tarkim, numeris 43.

247
00:10:31,040 --> 00:10:34,190
Ir nieko matyt rasta,
nes aš gavau atgal jokio atsakymo.

248
00:10:34,190 --> 00:10:35,010
Taigi, galime tai padaryti ir vėl.

249
00:10:35,010 --> 00:10:35,690
Paieška.

250
00:10:35,690 --> 00:10:39,520
Leiskite paieška 50 arba, tiksliau ieškoti
už 42, kuris yra gražus

251
00:10:39,520 --> 00:10:40,850
mažai subtilus prasmę.

252
00:10:40,850 --> 00:10:42,610
Ir radau gyvenimo prasmę ten.

253
00:10:42,610 --> 00:10:44,990
Numeris 42, jei jūs nežinote,
nuoroda tai Google.

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

255
00:10:45,350 --> 00:10:47,130
Taigi, kas šią programą padaryti už mane?

256
00:10:47,130 --> 00:10:50,660
Tai tiesiog leido man įterpti taip
toli ir ieškoti elementų.

257
00:10:50,660 --> 00:10:53,650
>> Leiskite pirmyn, tada į
kad funkcija mes žvilgtelėjau

258
00:10:53,650 --> 00:10:55,360
, pirmadienį, kaip erzina.

259
00:10:55,360 --> 00:10:59,620
Taigi šią funkciją, galiu reikalauti, ieško
sąraše elementas pirmiausia

260
00:10:59,620 --> 00:11:03,830
vienas, paskatino vartotoją ir tada skambinti
GetInt gauti realią int

261
00:11:03,830 --> 00:11:05,060
kad jūs norite ieškoti.

262
00:11:05,060 --> 00:11:06,460
>> Tada pastebėti tai.

263
00:11:06,460 --> 00:11:10,690
Aš ruošiuosi sukurti laikiną kintamąjį
atitinka 188 pavadino rodyklė -

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

265
00:11:11,270 --> 00:11:12,440
galėjo pavadino jį nieko.

266
00:11:12,440 --> 00:11:16,140
Ir tai rodyklė mazgas
nes sakiau mazgas * ten.

267
00:11:16,140 --> 00:11:19,900
Ir aš Inicijuojama, kad ji būtų lygi
pirmas, kad aš iš tikrųjų turiu

268
00:11:19,900 --> 00:11:22,860
pirštas, taip sakant, ant labai
pirmasis elementas iš sąrašo.

269
00:11:22,860 --> 00:11:27,460
Taigi, jei mano dešinioji ranka čia yra PTR aš
nukreipta į tą patį dalyką, kad pirmasis

270
00:11:27,460 --> 00:11:28,670
yra nukreipta į.

271
00:11:28,670 --> 00:11:31,430
>> Taigi dabar vėl kodą,
kas bus toliau -

272
00:11:31,430 --> 00:11:35,070
tai yra bendra paradigma, kai Iteracja
daugiau panašaus struktūra

273
00:11:35,070 --> 00:11:35,970
susijęs sąrašą.

274
00:11:35,970 --> 00:11:40,410
Aš ruošiuosi padaryti taip, o
rodyklė nėra lygus nulis Taigi, nors

275
00:11:40,410 --> 00:11:47,530
mano pirštas nėra nukreipta tam tikru null
vertė, jei rodyklė rodyklė n lygus n.

276
00:11:47,530 --> 00:11:52,290
Mes pirmiausia pastebite, kad n yra kas
vartotojas turi įvesti per GetInts skambinti čia.

277
00:11:52,290 --> 00:11:54,280
>> Ir rodyklė rodyklė n reiškia ką?

278
00:11:54,280 --> 00:11:59,020
Na, jei mes einame atgal į paveikslėlį čia
jei turiu pirštu rodydamas į

279
00:11:59,020 --> 00:12:02,960
kad pirmasis mazgas, kuriame devynių, kad
rodyklė esmės reiškia eiti, kad

280
00:12:02,960 --> 00:12:08,860
mazgas ir patraukti už vietos n vertę,
šiuo atveju duomenų laukas vadinamas n.

281
00:12:08,860 --> 00:12:14,120
>> Kaip žemę - ir pamatėme šį pora
savaičių atgal, kai kažkas paklausė -

282
00:12:14,120 --> 00:12:18,840
šį sintaksė yra nauja, bet jis nėra
mums įgaliojimus, kad mes

283
00:12:18,840 --> 00:12:20,040
dar nebuvo.

284
00:12:20,040 --> 00:12:25,325
Kas buvo ši frazė atitinka naudojant
taško žymėjimas ir žvaigždės pora

285
00:12:25,325 --> 00:12:29,490
savaičių atgal, kai mes nulupus
šis sluoksnis šiek tiek per anksti?

286
00:12:29,490 --> 00:12:31,780
>> STUDENTŲ: [nesigirdi].

287
00:12:31,780 --> 00:12:38,880
>> GARSIAKALBIS 1: Būtent, tai buvo žvaigždė, ir
tada ji buvo žvaigždė taškas n, su

288
00:12:38,880 --> 00:12:41,930
skliaustai čia, kuri atrodo,
atvirai, manau, kad daug

289
00:12:41,930 --> 00:12:43,320
daugiau paslaptingas skaityti.

290
00:12:43,320 --> 00:12:46,270
Bet žvaigždė žymeklis, kaip visada,
reiškia eiti ten.

291
00:12:46,270 --> 00:12:49,090
Ir kai jūs ten, kokie duomenys
laukas jūs norite pasiekti?

292
00:12:49,090 --> 00:12:52,730
Na jūs naudojate dot žymėjimą naudotis
structs duomenų laukas, ir aš

293
00:12:52,730 --> 00:12:54,140
konkrečiai norite n.

294
00:12:54,140 --> 00:12:56,240
>> Atvirai kalbant, aš norėčiau ginčytis tai
yra tik sunkiau skaityti.

295
00:12:56,240 --> 00:12:58,080
Tai sunkiau prisiminti, kur
Ar skliaustuose eiti,

296
00:12:58,080 --> 00:12:59,030
žvaigždė ir visa tai.

297
00:12:59,030 --> 00:13:02,150
Taigi pasaulis priėmė kai sintaksinė
cukraus, taip sakant.

298
00:13:02,150 --> 00:13:04,740
Tiesiog seksualus būdas pasakyti,
tai atitinka ir

299
00:13:04,740 --> 00:13:05,970
galbūt labiau intuityvus.

300
00:13:05,970 --> 00:13:09,600
Jei rodyklė yra iš tikrųjų rodyklė,
rodyklių notacijos reiškia eiti ten ir rasite

301
00:13:09,600 --> 00:13:11,890
šiuo atveju laukas vadinamas n.

302
00:13:11,890 --> 00:13:13,660
>> Taigi, jei aš galėčiau jį rasti, pastebėti, ką darau.

303
00:13:13,660 --> 00:13:17,430
Aš tiesiog atsispausdinti, radau proc I
prijungti į tos int vertę.

304
00:13:17,430 --> 00:13:20,730
Aš vadinu miegoti vieną sekundę tiesiog natūra
iš pristabdyti dalykų ekrane

305
00:13:20,730 --> 00:13:22,900
suteikti vartotojui antra sugerti
kas atsitiko.

306
00:13:22,900 --> 00:13:24,290
Ir tada aš pertraukos.

307
00:13:24,290 --> 00:13:26,330
Priešingu atveju, ką man daryti?

308
00:13:26,330 --> 00:13:30,960
Aš atnaujinti žymiklį lygūs
rodyklė rodyklė kitą.

309
00:13:30,960 --> 00:13:35,840
>> Taigi, tiesiog, kad būtų aišku, tai reiškia eiti
ten, naudodami savo senosios mokyklos žymėjimą.

310
00:13:35,840 --> 00:13:39,580
Taigi tai tiesiog reiškia eiti į whatever
jūs nukreipta į, kuris labai

311
00:13:39,580 --> 00:13:43,660
Pirmasis atvejis aš nukreipta į
su devynių jame struct.

312
00:13:43,660 --> 00:13:44,510
Taigi, aš nuėjo ten.

313
00:13:44,510 --> 00:13:47,880
Ir tada taškas žymėjimas reiškia,
gauti vertę kitą.

314
00:13:47,880 --> 00:13:50,470
>> Bet vertė, nors jis sudarytas
kaip siauras, tik skaičius.

315
00:13:50,470 --> 00:13:51,720
Tai skaitmeninis adresą.

316
00:13:51,720 --> 00:13:55,670
Taigi tai viena eilutė kodo, ar
parašyta, kaip šis, daugiau paslaptingas

317
00:13:55,670 --> 00:14:00,190
būdu, arba, kaip šis, šiek tiek daugiau
intuityvus būdas, tiesiog reiškia, perkelti savo ranką

318
00:14:00,190 --> 00:14:03,460
nuo pirmojo mazgo į kitą,
ir tada kitą, ir tada

319
00:14:03,460 --> 00:14:05,320
kitą, ir taip toliau.

320
00:14:05,320 --> 00:14:09,920
>> Taigi mes ne gyventi dėl kitų
realizacijos įterpti ir ištrinti

321
00:14:09,920 --> 00:14:14,030
ir Sankryþos, pirmieji du
kuris yra gana dalyvauja.

322
00:14:14,030 --> 00:14:17,010
Ir manau, kad tai gana lengva gauti
prarastomis tada, kai tai daryti žodžiu.

323
00:14:17,010 --> 00:14:19,890
Bet ką mes galime padaryti čia
pabandyti nustatyti, kaip

324
00:14:19,890 --> 00:14:21,640
geriausia tai padaryti vizualiai.

325
00:14:21,640 --> 00:14:24,800
Nes aš norėčiau pasiūlyti, kad, jei mes
norite įterpti elementus į tai

326
00:14:24,800 --> 00:14:26,680
esamą sąrašą, kuris
turi penkis elementus -

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

328
00:14:29,530 --> 00:14:33,300
jei aš buvo ketiname įgyvendinti tai
kodas, man reikia apsvarstyti, kaip eiti

329
00:14:33,300 --> 00:14:34,160
apie tai daryti.

330
00:14:34,160 --> 00:14:37,720
>> Ir aš norėčiau pasiūlyti, atsižvelgiant kūdikio žingsnius
pagal kurią, šiuo atveju aš turiu galvoje, kas yra

331
00:14:37,720 --> 00:14:41,090
galimi scenarijai, kad mes
gali susidurti apskritai?

332
00:14:41,090 --> 00:14:44,120
Įgyvendinant įdėklas Tinkliniai
sąrašas, tai tiesiog atsitinka būti

333
00:14:44,120 --> 00:14:46,090
Konkretus pavyzdys dydžio penki.

334
00:14:46,090 --> 00:14:50,420
Na, jei norite įterpti numerį,
norėčiau pasakyti, kad numeris vienas, ir

335
00:14:50,420 --> 00:14:53,380
išlaikyti surūšiuoti užsakymą, kur
akivaizdžiai nėra numeris vienas turi

336
00:14:53,380 --> 00:14:55,686
eiti šiuo konkrečiu pavyzdžiu?

337
00:14:55,686 --> 00:14:56,840
Kaip pradžioje.

338
00:14:56,840 --> 00:15:00,030
>> Bet įdomiausia yra tai, kad
jei norite įterpti vieną į šią

339
00:15:00,030 --> 00:15:04,100
sąrašas, kokių specialiųjų rodyklė turi
būti atnaujintas matyt?

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

341
00:15:04,610 --> 00:15:07,830
Taigi aš norėčiau ginčytis, tai yra pirmas atvejis
kad mes galbūt norėsite apsvarstyti,

342
00:15:07,830 --> 00:15:11,140
scenarijų įtraukiant įstatykite
sąrašo pradžioje.

343
00:15:11,140 --> 00:15:15,400
>> Leiskite roviau gal taip paprasta, ar net
lengviau atveju, santykinai kalbant.

344
00:15:15,400 --> 00:15:18,110
Tarkime, aš noriu įterpti
į rūšiuotų kad 35 skaičius.

345
00:15:18,110 --> 00:15:20,600
Tai akivaizdžiai priklauso ten.

346
00:15:20,600 --> 00:15:25,320
Taigi, kas rodyklė akivaizdžiai ketina
turi būti atnaujinami tokiu atveju?

347
00:15:25,320 --> 00:15:30,060
34 s žymeklis tampa NOT NULL
bet iš struct adresas

348
00:15:30,060 --> 00:15:31,800
, kuriame yra skaičius 35.

349
00:15:31,800 --> 00:15:32,750
Štai atveju du.

350
00:15:32,750 --> 00:15:36,190
Taigi jau, aš tarsi Kvantas
kiek darbo turiu padaryti čia.

351
00:15:36,190 --> 00:15:39,880
>> Ir, pagaliau, akivaizdu, vidutinio atvejis
Iš tiesų, per vidurį, jei noriu

352
00:15:39,880 --> 00:15:45,870
įterpti kažką panašaus pasakyti 23, kuris eina
tarp 23 ir 26, bet

353
00:15:45,870 --> 00:15:48,680
dabar ko gauti šiek tiek daugiau
naudojami, nes tai, ką

354
00:15:48,680 --> 00:15:52,800
rodykles reikia keisti?

355
00:15:52,800 --> 00:15:56,680
Taigi 22 akivaizdžiai turi būti pakeista
nes jis negali nurodyti 26 nebėra.

356
00:15:56,680 --> 00:16:00,320
Jam reikia, kad rodytų į naujas mazgas, kad
Aš turiu skirti telefonu

357
00:16:00,320 --> 00:16:01,770
malloc arba kitu lygiaverčiu.

358
00:16:01,770 --> 00:16:05,990
>> Bet tada aš taip pat reikia, kad naujas mazgas, 23
šiuo atveju, turi turėti savo rodyklę

359
00:16:05,990 --> 00:16:07,870
nukreipta į ką?

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

361
00:16:08,560 --> 00:16:10,380
Ir ten bus
Užsakyti operacijų čia.

362
00:16:10,380 --> 00:16:13,410
Nes jei aš tai kvailai, ir aš
pavyzdžiui, pradėkite nuo pradžios

363
00:16:13,410 --> 00:16:16,040
sąrašas, o mano tikslas yra įdėti 23.

364
00:16:16,040 --> 00:16:18,610
Ir aš patikrinti, ar ji priklauso
Čia, netoli devynių?

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

366
00:16:18,950 --> 00:16:20,670
Ar tai priklauso čia, šalia 17?

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

368
00:16:20,940 --> 00:16:22,530
Ar tai priklauso čia šalia 22?

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

370
00:16:23,300 --> 00:16:26,400
>> Dabar, jei aš kvailas čia, o ne
galvoju, kad šis pro galėčiau

371
00:16:26,400 --> 00:16:28,320
skirti savo naują mazgą 23.

372
00:16:28,320 --> 00:16:32,080
Galiu atnaujinti žymiklį nuo
mazgas vadinamas 22, rodydamas

373
00:16:32,080 --> 00:16:33,080
tai ne naujas mazgas.

374
00:16:33,080 --> 00:16:36,140
Ir tada, ką aš turiu atnaujinti
naujos mazgo rodyklė būti?

375
00:16:36,140 --> 00:16:38,120
>> STUDENTŲ: [nesigirdi].

376
00:16:38,120 --> 00:16:38,385
>> GARSIAKALBIS 1: Būtent.

377
00:16:38,385 --> 00:16:39,710
Nukreipta į 26.

378
00:16:39,710 --> 00:16:45,590
Bet velniai, jei aš ne jau atnaujinti
22 'žymeklis atkreipti į šį vaikiną, ir

379
00:16:45,590 --> 00:16:48,260
dabar turiu našlaičius, poilsio
sąrašo, taip sakant.

380
00:16:48,260 --> 00:16:52,140
Taigi, kad veiklos čia
bus svarbus.

381
00:16:52,140 --> 00:16:55,100
>> Norėdami tai padaryti, galėčiau pavogti,
tarkim, šešių savanorių.

382
00:16:55,100 --> 00:16:57,650
Ir tegul pamatyti, jei mes negalime padaryti
vizualiai vietoj kodo išmintingas.

383
00:16:57,650 --> 00:16:59,330
Ir mes turime keletą gražių stresą
rutuliai jums šiandien.

384
00:16:59,330 --> 00:17:02,510
Gerai, kaip apie vieną, du, į
atgal - nuo pabaigos.

385
00:17:02,510 --> 00:17:04,530
trijų, keturių, jums abiems
vaikinai pabaigos.

386
00:17:04,530 --> 00:17:05,579
Ir penkių, šešių.

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

388
00:17:05,839 --> 00:17:06,450
Penkių ir šešių.

389
00:17:06,450 --> 00:17:08,390
Visos teisės ir mes ateiti
Jums, vaikinai kitą kartą.

390
00:17:08,390 --> 00:17:09,640
Viskas gerai, ateiti iki.

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

392
00:17:12,010 --> 00:17:14,819
>> Viskas gerai, nes esate čia pirma,
norėtumėte būti vienas nerangiai

393
00:17:14,819 --> 00:17:16,119
"Google" Stiklo čia?

394
00:17:16,119 --> 00:17:19,075
Gerai, taip, gerai, Stiklas,
filmuoti.

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

396
00:17:22,720 --> 00:17:24,589
Gerai, jūs gerai eiti.

397
00:17:24,589 --> 00:17:27,950
>> Visos teisės, todėl, jei jus vaikinai gali ateiti per
čia aš iš anksto paruošti

398
00:17:27,950 --> 00:17:30,110
kai kurie numeriai.

399
00:17:30,110 --> 00:17:31,240
Gerai, eikš čia.

400
00:17:31,240 --> 00:17:33,440
Ir kodėl gi ne jums eiti šiek tiek
toliau, kad taip.

401
00:17:33,440 --> 00:17:35,520
Pažiūrėkime, kas yra jūsų vardas,
su "Google" stiklo?

402
00:17:35,520 --> 00:17:35,910
>> STUDENTŲ: Ben.

403
00:17:35,910 --> 00:17:36,230
>> GARSIAKALBIS 1: Benas?

404
00:17:36,230 --> 00:17:38,380
Gerai, Benas, jums bus pirmasis, tiesiogine prasme.

405
00:17:38,380 --> 00:17:40,580
Taigi, mes ketiname atsiųsti
iki etapo pabaigos.

406
00:17:40,580 --> 00:17:41,670
Visos teisės ir tavo vardas?

407
00:17:41,670 --> 00:17:41,990
>> STUDENTŲ: Jason.

408
00:17:41,990 --> 00:17:44,530
>> GARSIAKALBIS 1: Jasonas Gerai jums
būti numeris devyni.

409
00:17:44,530 --> 00:17:46,700
Taigi, jei norite sekti Ben kad taip.

410
00:17:46,700 --> 00:17:47,010
>> STUDENTŲ: Jill.

411
00:17:47,010 --> 00:17:49,630
>> GARSIAKALBIS 1: Jill, jūs ketinate būti
17, kuri, jei aš padariau tai daugiau

412
00:17:49,630 --> 00:17:51,260
protingai, aš norėčiau turėti
pradėjo kitame gale.

413
00:17:51,260 --> 00:17:52,370
Jūs eikite, kad taip.

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

415
00:17:53,030 --> 00:17:53,670
Ir jūs esate?

416
00:17:53,670 --> 00:17:53,980
>> STUDENTŲ: Marija.

417
00:17:53,980 --> 00:17:56,130
>> GARSIAKALBIS 1: Marija, jums bus 22.

418
00:17:56,130 --> 00:17:58,420
Ir jūsų vardas?

419
00:17:58,420 --> 00:17:58,810
>> STUDENTŲ: Chris.

420
00:17:58,810 --> 00:18:00,100
>> GARSIAKALBIS 1: Chris, jums bus 26.

421
00:18:00,100 --> 00:18:00,740
Ir tada galiausiai.

422
00:18:00,740 --> 00:18:01,400
>> STUDENTŲ Diana.

423
00:18:01,400 --> 00:18:02,670
>> GARSIAKALBIS 1 Diana, jums bus 34.

424
00:18:02,670 --> 00:18:03,920
Taigi, jūs ateiti čia.

425
00:18:03,920 --> 00:18:06,360
>> Visos teisės, todėl puikiai surūšiuoti
užsisakyti jau.

426
00:18:06,360 --> 00:18:09,600
Ir eikime į priekį ir tai padaryti
kad mes galime tikrai -

427
00:18:09,600 --> 00:18:11,720
Ben jūs tik rūšies ieškote
išeiti į niekur ten.

428
00:18:11,720 --> 00:18:15,670
Gerai, kad galime eiti į priekį ir vaizduoti tai
naudojant rankas, panašiai kaip aš, būtent,

429
00:18:15,670 --> 00:18:16,250
kas vyksta.

430
00:18:16,250 --> 00:18:19,540
Taigi, eikite į priekį ir suteikti sau
pėdų arba du tarp savęs.

431
00:18:19,540 --> 00:18:22,900
Ir eiti į priekį ir taškas viena ranka
jei kas jums turėtų būti nukreipta į

432
00:18:22,900 --> 00:18:23,470
remiantis tai.

433
00:18:23,470 --> 00:18:25,890
Ir jei jūs null tiesiog atkreipti
tiesiai žemyn prie grindų.

434
00:18:25,890 --> 00:18:27,690
Gerai, kad gerai.

435
00:18:27,690 --> 00:18:32,290
>> Taigi dabar mes turime susietą sąrašą, ir leiskite man
pasiūlyti, kad aš žaisti vaidmenį

436
00:18:32,290 --> 00:18:35,110
PTR, todėl aš ne nerimauti
atliekant šį kartą aplink.

437
00:18:35,110 --> 00:18:37,830
Ir tada - kažkas kvailas konvencija -
galite skambinti šiuo ką tik norite -

438
00:18:37,830 --> 00:18:39,800
pirmtakas rodyklė, pred rodyklė -

439
00:18:39,800 --> 00:18:43,930
tai tik slapyvardis mes pasidavė
mūsų mėginio kodą į savo kairę ranką.

440
00:18:43,930 --> 00:18:47,240
Kita vertus, kad bus išlaikyti
sekti, kas yra kas

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

442
00:18:48,400 --> 00:18:52,390
>> Taigi manau, kad, pirma, noriu roviau
kad pirmasis pavyzdys įterpiant, tarkim

443
00:18:52,390 --> 00:18:54,330
20, į sąrašą.

444
00:18:54,330 --> 00:18:57,160
Taigi, aš ruošiuosi reikia ką nors
įkūnija numeris 20 mums.

445
00:18:57,160 --> 00:18:58,950
Taigi man reikia malloc nors
iš auditorijos.

446
00:18:58,950 --> 00:18:59,380
Ateik iki.

447
00:18:59,380 --> 00:19:00,340
Koks tavo vardas?

448
00:19:00,340 --> 00:19:01,300
>> STUDENTŲ Brian.

449
00:19:01,300 --> 00:19:05,270
>> GARSIAKALBIS 1: Brian, viskas gerai, todėl jūs
turi būti mazgo, kurių sudėtyje yra 20.

450
00:19:05,270 --> 00:19:06,810
Gerai, eikš čia.

451
00:19:06,810 --> 00:19:10,025
Ir akivaizdu, kur
nėra Brian priklauso?

452
00:19:10,025 --> 00:19:12,190
Taigi, į vidurį - iš tikrųjų,
palauk.

453
00:19:12,190 --> 00:19:13,420
Mes darome tai iš eilės.

454
00:19:13,420 --> 00:19:17,170
Mes darome tai dalis sunkiau
nei ji turi būti pirmas.

455
00:19:17,170 --> 00:19:21,210
Gerai, mes ketiname nemokamai Brian
ir realloc Brian kaip penkių.

456
00:19:21,210 --> 00:19:23,680
>> Gerai, kad dabar mes norime įterpti
Brian kaip penkių.

457
00:19:23,680 --> 00:19:25,960
Taigi eikš čia šalia
Benas tik akimirką.

458
00:19:25,960 --> 00:19:28,250
Ir jūs galite tikriausiai pasakys
kur ši istorija vyksta.

459
00:19:28,250 --> 00:19:30,500
Bet tegul kruopščiai galvoti apie
iš operacijų eiliškumas.

460
00:19:30,500 --> 00:19:32,880
Ir tai būtent ši vaizdo
kad ketina išsirikiuoti

461
00:19:32,880 --> 00:19:34,080
su tuo mėginio kodą.

462
00:19:34,080 --> 00:19:40,120
Taigi čia aš PTR nukreipta pradžių
ne Ben, per se, bet kokia

463
00:19:40,120 --> 00:19:43,245
Vertiname jis yra, kuris šiuo atveju
yra - kas tavo vardas?

464
00:19:43,245 --> 00:19:43,670
>> STUDENTŲ: Jason.

465
00:19:43,670 --> 00:19:47,350
>> GARSIAKALBIS 1: Jason, todėl tiek Benas ir aš
nukreipta į Jason šiuo metu.

466
00:19:47,350 --> 00:19:49,700
Taigi dabar turiu nustatyti,
kur veikia Brian priklauso?

467
00:19:49,700 --> 00:19:53,500
Taigi vienintelis dalykas, aš turėti prieigą prie
dabar yra jo n duomenų elementas.

468
00:19:53,500 --> 00:19:58,280
Taigi, aš ruošiuosi patikrinti, yra
Brian mažiau nei Jason?

469
00:19:58,280 --> 00:19:59,770
Atsakymas yra tiesa.

470
00:19:59,770 --> 00:20:03,680
>> Taigi, ką dabar turi įvykti,
teisinga tvarka?

471
00:20:03,680 --> 00:20:07,120
Man reikia atnaujinti, kiek patarimų
iš viso šioje istorijoje?

472
00:20:07,120 --> 00:20:10,720
Kur mano ranka vis dar nukreipta į
Jason, o jūsų ranka - jei norite

473
00:20:10,720 --> 00:20:12,930
įdėti savo ranką, kaip, tarsi aš
Nežinau, klaustuką.

474
00:20:12,930 --> 00:20:14,070
Gerai, gerai.

475
00:20:14,070 --> 00:20:15,670
>> Gerai, taigi jūs neturite
keli kandidatai.

476
00:20:15,670 --> 00:20:20,500
Bet Benas arba I ar Brian ar Jason
ar visi kiti, kurie

477
00:20:20,500 --> 00:20:21,370
rodykles reikia pakeisti?

478
00:20:21,370 --> 00:20:23,260
Kiek iš viso?

479
00:20:23,260 --> 00:20:24,080
>> Gerai, kad du.

480
00:20:24,080 --> 00:20:27,090
Mano rodyklė tikrai ne klausimas nebėra
nes aš tik laikinas.

481
00:20:27,090 --> 00:20:31,370
Todėl šie du vaikinai, matyt,
tiek Benas ir Brian.

482
00:20:31,370 --> 00:20:34,410
Taigi leiskite man pasiūlyti, kad mes atnaujinti
Benas, nes jis pirmas.

483
00:20:34,410 --> 00:20:36,350
Pirmasis elementas iš šio sąrašo
dabar bus Brian.

484
00:20:36,350 --> 00:20:38,070
Taigi Benas taškas Brian.

485
00:20:38,070 --> 00:20:39,320
Gerai, dabar ką?

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

487
00:20:41,950 --> 00:20:43,460
>> Kas gauna nurodė kam?

488
00:20:43,460 --> 00:20:44,710
>> STUDENTŲ: [nesigirdi].

489
00:20:44,710 --> 00:20:46,180
>> GARSIAKALBIS 1: Gerai, kad Brian
, pabrėžiama, Jason.

490
00:20:46,180 --> 00:20:48,360
Bet aš prarado stebėti, kad žymeklis?

491
00:20:48,360 --> 00:20:49,980
Ar aš žinau, kur Jasonas yra?

492
00:20:49,980 --> 00:20:50,790
>> STUDENTŲ: [nesigirdi].

493
00:20:50,790 --> 00:20:52,620
>> GARSIAKALBIS 1: aš, nes aš
laikinas žymeklis.

494
00:20:52,620 --> 00:20:55,110
Ir matyt, aš nepasikeitė
atkreipti į naujas mazgas.

495
00:20:55,110 --> 00:20:58,300
Taigi, mes galime tiesiog Brian tašką
ne tas, kas aš nukreipta į.

496
00:20:58,300 --> 00:20:59,000
Ir mes padaryti.

497
00:20:59,000 --> 00:21:01,890
Taigi, jei vienas, įterpimas į
pradžioje sąrašo.

498
00:21:01,890 --> 00:21:02,950
Yra du pagrindiniai žingsniai.

499
00:21:02,950 --> 00:21:06,750
Vienas iš jų, mes turime atnaujinti Ben, tada
mes taip pat turime atnaujinti Brian.

500
00:21:06,750 --> 00:21:09,230
Ir tada aš neturiu nerimauti
traipsing per likusį

501
00:21:09,230 --> 00:21:12,680
sąrašas, nes mes jau rado savo
vieta, nes jis priklausė

502
00:21:12,680 --> 00:21:14,080
paliko pirmojo elemento.

503
00:21:14,080 --> 00:21:15,400
>> Gerai, kad gana paprasta.

504
00:21:15,400 --> 00:21:18,110
Tiesą sakant, jaučiasi mes beveik
todėl tai pernelyg sudėtinga.

505
00:21:18,110 --> 00:21:20,240
Taigi tegul dabar roviau pabaigos
sąrašo, ir pamatyti, kur

506
00:21:20,240 --> 00:21:21,380
sudėtingumas prasideda.

507
00:21:21,380 --> 00:21:24,560
Taigi, jei dabar, aš alloy iš auditorijos.

508
00:21:24,560 --> 00:21:25,540
Kiekvienas nori žaisti 55?

509
00:21:25,540 --> 00:21:26,700
Gerai, aš pamačiau savo ranką pirmas.

510
00:21:26,700 --> 00:21:29,620
Ateik iki.

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

512
00:21:30,030 --> 00:21:31,177
Koks tavo vardas?

513
00:21:31,177 --> 00:21:32,310
>> STUDENTŲ: [nesigirdi].

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

515
00:21:33,240 --> 00:21:33,890
Gerai, ateik iki.

516
00:21:33,890 --> 00:21:35,730
Būsite skaičius 55.

517
00:21:35,730 --> 00:21:37,820
Taigi, jūs, žinoma, priklauso
prie sąrašo pabaigoje.

518
00:21:37,820 --> 00:21:41,850
Taigi leiskite pakartoti modeliavimą su manimi
yra PTR tik akimirką.

519
00:21:41,850 --> 00:21:44,050
Taigi, aš pirmą kartą ketina atkreipti į
kokia BEN'S nukreipta į.

520
00:21:44,050 --> 00:21:45,900
Mes abu nukreipta dabar Brian.

521
00:21:45,900 --> 00:21:48,420
Taigi 55 yra ne mažesnis nei penki.

522
00:21:48,420 --> 00:21:52,510
Taigi, aš ruošiuosi atnaujinti save pagal
nukreipta į Briano kitą žymeklis, kuris

523
00:21:52,510 --> 00:21:54,450
Dabar, žinoma, Jason.

524
00:21:54,450 --> 00:21:57,310
55 yra ne mažiau kaip devynių, todėl
Aš ruošiuosi atnaujinti ptr.

525
00:21:57,310 --> 00:21:58,890
Aš ruošiuosi atnaujinti ptr.

526
00:21:58,890 --> 00:22:02,290
Aš ruošiuosi atnaujinti PTR
Aš ketina atnaujinti ptr.

527
00:22:02,290 --> 00:22:05,060
Ir aš ruošiuosi - Hmm, kas
tavo vardas?

528
00:22:05,060 --> 00:22:05,560
>> STUDENTŲ Diana.

529
00:22:05,560 --> 00:22:09,190
>> GARSIAKALBIS 1: Diana nukreipta, žinoma,
ne niekiniu su savo kaire ranka.

530
00:22:09,190 --> 00:22:13,030
Taigi, kur veikia Habata tikrųjų
priklauso aiškiai?

531
00:22:13,030 --> 00:22:15,050
Į kairę, čia.

532
00:22:15,050 --> 00:22:19,460
Taigi, kaip man žinoti, kad įdėti ją čia
Manau, kad aš įsukus.

533
00:22:19,460 --> 00:22:22,420
Nes tai, kas yra PTR menas
tai laiko momentas?

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

535
00:22:23,240 --> 00:22:25,580
Taigi, nors vizualiai galime
akivaizdžiai matyti visi jie

536
00:22:25,580 --> 00:22:26,610
vaikinai čia ant scenos.

537
00:22:26,610 --> 00:22:29,680
Aš ne nuolat stebėti iš ankstesnių
asmuo sąraše.

538
00:22:29,680 --> 00:22:33,210
Aš neturiu pirštą nurodydamas, kad
šiuo atveju mazgas numeris 34.

539
00:22:33,210 --> 00:22:34,760
>> Taigi, galime iš tikrųjų pradėti tai per.

540
00:22:34,760 --> 00:22:37,560
Taigi, dabar aš iš tikrųjų reikia
Antrasis vietos kintamąjį.

541
00:22:37,560 --> 00:22:40,980
Ir tai, ką jūs matote
Tikrasis bandinys C kodas, kur, kaip aš einu,

542
00:22:40,980 --> 00:22:45,860
kai aš atnaujinti savo dešinę ranką į tašką
Jasonas paliekant Brian atsilieka, aš

543
00:22:45,860 --> 00:22:51,440
geriau pradėti naudoti savo kairę ranką į
atnaujinti kur aš buvau, kad, kaip aš einu

544
00:22:51,440 --> 00:22:52,700
per šį sąrašą -

545
00:22:52,700 --> 00:22:55,040
daugiau nerangiai nei aš skirtas
dabar čia vizualiai -

546
00:22:55,040 --> 00:22:56,740
Aš ruošiuosi gauti
pabaigoje sąrašo.

547
00:22:56,740 --> 00:23:00,020
>> Ši ranka vis dar null, kuri yra gana
nenaudingas, išskyrus tai, kad nurodyti

548
00:23:00,020 --> 00:23:02,980
Aš aiškiai sąrašo pabaigoje,
bet dabar bent turiu tai

549
00:23:02,980 --> 00:23:08,270
pirmtakas rodyklė nukreipta čia, todėl
kas dabar rankas ir kas patarimų turi

550
00:23:08,270 --> 00:23:10,150
būti atnaujintas?

551
00:23:10,150 --> 00:23:13,214
Kieno ranka tu nori
pertvarkyti pirmąjį?

552
00:23:13,214 --> 00:23:15,190
>> STUDENTŲ: [nesigirdi].

553
00:23:15,190 --> 00:23:16,220
>> GARSIAKALBIS 1: Gerai, kad Dianos.

554
00:23:16,220 --> 00:23:21,110
Jeigu jūs norite nurodyti
Dianos kairę rodyklė ne?

555
00:23:21,110 --> 00:23:23,620
Ne 55, matyt, todėl, kad
mes įterpiami ten.

556
00:23:23,620 --> 00:23:25,560
Ir kur turėtų 55 rodyklė eiti?

557
00:23:25,560 --> 00:23:27,000
Žemyn, ty null.

558
00:23:27,000 --> 00:23:28,890
Ir mano rankos, šiuo metu, ar ne
klausimas, nes jie buvo tik

559
00:23:28,890 --> 00:23:30,070
laikini kintamieji.

560
00:23:30,070 --> 00:23:31,030
Taigi dabar mes padaryti.

561
00:23:31,030 --> 00:23:34,650
>> Taigi papildomas sudėtingumas ten - ir
tai nereiškia, kad sunku įgyvendinti,

562
00:23:34,650 --> 00:23:38,660
bet mums reikia vidurinį kintamąjį pateikti
įsitikinkite, kad prieš man perkelti savo teisę

563
00:23:38,660 --> 00:23:42,140
Kita vertus, aš atnaujinti mano kairę vertę
Kita vertus, pred žymeklis šiuo atveju, todėl

564
00:23:42,140 --> 00:23:45,860
kad turiu gale žymeklį
sekti kur buvau.

565
00:23:45,860 --> 00:23:49,360
Dabar, kaip panaikinti, jei jūs galvojate tai
per, tai jaučiasi, kad tai

566
00:23:49,360 --> 00:23:51,490
šiek tiek erzina, kad nuolat
sekti šios kaire ranka.

567
00:23:51,490 --> 00:23:54,015
>> Kas būtų kitas sprendimas
Šios problemos buvo?

568
00:23:54,015 --> 00:23:56,500
Jei turite pertvarkyti duomenis
struktūra mes kalbame

569
00:23:56,500 --> 00:23:59,630
per dabar?

570
00:23:59,630 --> 00:24:02,690
Jeigu tai tik rūšies jaučiasi tiek
erzina, kad, pavyzdžiui, dvi rodykles

571
00:24:02,690 --> 00:24:08,430
išgyvena sąrašo, kuris dar gali
buvo, idealiame pasaulyje, prižiūrima

572
00:24:08,430 --> 00:24:10,160
informacija, kad mums reikia?

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

574
00:24:11,360 --> 00:24:12,610
>> STUDENTŲ: [nesigirdi].

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

576
00:24:15,160 --> 00:24:16,150
>> GARSIAKALBIS 1: Būtent.

577
00:24:16,150 --> 00:24:19,130
Teisę taip, ten tikrai įdomu
gemalai idėja.

578
00:24:19,130 --> 00:24:22,470
Ir tai praėjusiais rodyklė idėja,
nukreipta į ankstesnį elementą.

579
00:24:22,470 --> 00:24:25,580
Ką daryti, jei aš tiesiog įkūnijo kad
viduje paties sąrašo?

580
00:24:25,580 --> 00:24:27,810
Ir tai bus sunku įsivaizduoti
tai be visų popieriaus

581
00:24:27,810 --> 00:24:28,830
sumažės iki grindų.

582
00:24:28,830 --> 00:24:31,860
Bet tarkime, kad šie vaikinai naudojami tiek
iš jų rankų, kad ankstesnė

583
00:24:31,860 --> 00:24:35,950
rodyklė, ir kitą rodyklė, taip
įgyvendinti tai, ką mes vadiname dvigubai

584
00:24:35,950 --> 00:24:36,830
susijęs sąrašą.

585
00:24:36,830 --> 00:24:41,090
Tai leistų man rūšiuoti atgal,
daug lengviau be manęs,

586
00:24:41,090 --> 00:24:43,800
programuotojas, turintis išlaikyti
sekti rankiniu būdu -

587
00:24:43,800 --> 00:24:44,980
tikrai rankiniu būdu -

588
00:24:44,980 --> 00:24:47,280
, kur buvau anksčiau
sąraše.

589
00:24:47,280 --> 00:24:48,110
Taigi mes negalime padaryti.

590
00:24:48,110 --> 00:24:50,950
Mes keep it simple, nes tai
vyksta jį ateiti kainą, du kartus

591
00:24:50,950 --> 00:24:53,450
daug erdvės, rodyklės,
jei norite antrasis.

592
00:24:53,450 --> 00:24:55,760
Bet tai iš tikrųjų yra bendroji
duomenų struktūra vadinama

593
00:24:55,760 --> 00:24:57,410
dvigubai susijęs sąrašas.

594
00:24:57,410 --> 00:25:01,310
>> Padarykim galutinį pavyzdį čia ir įdėti
šie iš savo kančių vaikinai.

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

596
00:25:03,270 --> 00:25:05,320
Nagi iki nuo altoriaus ten.

597
00:25:05,320 --> 00:25:06,280
Gerai, kas yra jūsų vardas?

598
00:25:06,280 --> 00:25:07,440
>> STUDENTŲ: [nesigirdi].

599
00:25:07,440 --> 00:25:07,855
>> GARSIAKALBIS 1: Atsiprašome?

600
00:25:07,855 --> 00:25:08,480
>> STUDENTŲ: [nesigirdi].

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

602
00:25:09,410 --> 00:25:10,230
Gerai ateiti iki.

603
00:25:10,230 --> 00:25:11,910
Jūs turi būti 20.

604
00:25:11,910 --> 00:25:14,720
Jūs akivaizdžiai ketina
priklausyti nuo 17 iki 22.

605
00:25:14,720 --> 00:25:16,150
Taigi leiskite man sužinoti savo pamoką.

606
00:25:16,150 --> 00:25:18,150
Aš ruošiuosi pradėti rodyklę
nukreipta į Brian.

607
00:25:18,150 --> 00:25:21,190
Ir aš ruošiuosi mano kairę ranką
tik atnaujinti Brian kaip aš pereiti prie

608
00:25:21,190 --> 00:25:23,600
Jasonas patikrinimo metu 20 mažiau nei devynių?

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

610
00:25:24,060 --> 00:25:25,430
Yra 20 mažiau nei 17?

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

612
00:25:25,880 --> 00:25:27,450
Yra 20 mažiau kaip 22?

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

614
00:25:28,440 --> 00:25:34,070
Taigi, kas patarimų ar rankas reikia pakeisti
kur jie nukreipta dabar?

615
00:25:34,070 --> 00:25:37,070
>> Taigi, mes galime padaryti, 17 nukreipta į 20.

616
00:25:37,070 --> 00:25:37,860
Taigi, kad viskas gerai.

617
00:25:37,860 --> 00:25:40,080
Kur norime atkreipti
Jūsų rodyklė dabar?

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

619
00:25:41,330 --> 00:25:45,410
Ir mes žinome, kur 22, vėlgi dėka
mano laikinas žymeklis.

620
00:25:45,410 --> 00:25:46,760
Taigi mes Gerai ten.

621
00:25:46,760 --> 00:25:49,440
Taigi dėl šio laikino saugojimo
Aš nuolat stebėti, kur visi yra.

622
00:25:49,440 --> 00:25:55,055
Ir dabar jūs galite vizualiai eiti į kur
jūs priklausote, ir dabar mes turime 1, 2, 3,

623
00:25:55,055 --> 00:25:58,410
4, 5, 6, 7, 8, 9 streso rutuliai,
ir ar plojimų už

624
00:25:58,410 --> 00:25:59,770
šie vaikinai, jei galėtume.

625
00:25:59,770 --> 00:26:00,410
Gražiai padaryta.

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

627
00:26:05,320 --> 00:26:06,330
>> GARSIAKALBIS 1: Gerai.

628
00:26:06,330 --> 00:26:09,860
Ir tu gali laikyti gabalus
Popieriaus kaip suvenyrai.

629
00:26:09,860 --> 00:26:15,930
>> Gerai, taip, pasitikėk manimi, tai daug
lengviau eiti per, kad su

630
00:26:15,930 --> 00:26:17,680
žmonės, nei ji yra su realiais kodą.

631
00:26:17,680 --> 00:26:22,690
Bet kas jums rasti tik akimirką
dabar yra tas pats - oi, ačiū.

632
00:26:22,690 --> 00:26:23,630
Ačiū -

633
00:26:23,630 --> 00:26:29,360
yra tai, kad jūs pamatysite, kad tuos pačius duomenis
struktūra, susijusi sąrašas, iš tikrųjų gali

634
00:26:29,360 --> 00:26:33,200
būti naudojama kaip statybinis blokas su dar
Sudėtingesnės duomenų struktūros.

635
00:26:33,200 --> 00:26:37,620
>> Ir suvokti pernelyg tema čia yra, kad
mes visiškai pristatė daugiau

636
00:26:37,620 --> 00:26:40,060
sudėtingumo į įgyvendinimo
Šio algoritmo.

637
00:26:40,060 --> 00:26:43,940
Intarpas, ir jei mes nuėjome per ją,
išbraukta ir paieška, yra šiek tiek

638
00:26:43,940 --> 00:26:46,660
sudėtingesnis nei
buvo su masyvo.

639
00:26:46,660 --> 00:26:48,040
Bet mes gauti šiek tiek dinamiškumo.

640
00:26:48,040 --> 00:26:50,180
Mes gauname prisitaikanti duomenų struktūrą.

641
00:26:50,180 --> 00:26:54,010
>> Bet vėl, mes mokėti tam tikra kaina
papildomas sudėtingumas, tiek

642
00:26:54,010 --> 00:26:54,910
jį įgyvendinant.

643
00:26:54,910 --> 00:26:56,750
Ir mes atsisakė laisvą prieigą.

644
00:26:56,750 --> 00:27:00,450
Ir tiesą sakant, ten nėra kažkoks gražus
valyti skaidrę aš galiu duoti jums, kad

645
00:27:00,450 --> 00:27:03,120
sako čia yra, kodėl susijęs sąrašas
yra geriau nei masyvo.

646
00:27:03,120 --> 00:27:04,100
Ir palikti jį tuo.

647
00:27:04,100 --> 00:27:07,520
Kadangi tema pasikartoja dabar net
labiau, kad per ateinančias savaites, yra

648
00:27:07,520 --> 00:27:10,200
kad nebūtinai
Teisingas atsakymas.

649
00:27:10,200 --> 00:27:13,830
>> Tai kodėl mes turime atskirą ašį
iš dizaino problema rinkinių.

650
00:27:13,830 --> 00:27:17,700
Tai bus labai konteksto
ar norite naudoti šiuos duomenis

651
00:27:17,700 --> 00:27:21,750
struktūra arba kad vienas, ir tai bus
priklauso nuo to, ką jums rūpi požiūriu

652
00:27:21,750 --> 00:27:24,620
išteklių ir sudėtingumo.

653
00:27:24,620 --> 00:27:28,830
>> Bet leiskite man pasiūlyti, kad idealus duomenys
struktūra, Gralis, būtų

654
00:27:28,830 --> 00:27:32,200
kažkas, kad pastovus laikas,
nepriklausomai nuo to, kiek medžiaga yra

655
00:27:32,200 --> 00:27:36,940
viduje, ar nebūtų nuostabu, jei
duomenų struktūra grįžo atsakymus

656
00:27:36,940 --> 00:27:37,920
pastovus laikas.

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

658
00:27:38,330 --> 00:27:40,110
Šis žodis yra jūsų didžiulis žodyną.

659
00:27:40,110 --> 00:27:41,550
Ar ne, šis žodis nėra.

660
00:27:41,550 --> 00:27:43,270
Arba bet tokia problema egzistuoja.

661
00:27:43,270 --> 00:27:46,360
Na pažiūrėkime, jei mes negalime bent
imtis siekiant šio žingsnio.

662
00:27:46,360 --> 00:27:50,190
>> Leiskite man pasiūlyti naują duomenų struktūrą, kuri
gali būti naudojami įvairių dalykų,

663
00:27:50,190 --> 00:27:52,260
šiuo atveju vadinamas maišos lentelė.

664
00:27:52,260 --> 00:27:55,590
Ir taip mes iš tikrųjų grįžti į skaitydamas
ne masyvo, šiuo atveju, ir

665
00:27:55,590 --> 00:28:00,550
šiek tiek savavališkai, aš sudarytas šis
maišos lentelė kaip su rūšies masyvo

666
00:28:00,550 --> 00:28:02,810
dvimatis masyvas -

667
00:28:02,810 --> 00:28:05,410
ar veikiau jis vaizduojamas čia kaip du
masyvas - bet tai tik

668
00:28:05,410 --> 00:28:10,770
dydžio 26 masyvas, pavyzdžiui, kad jei mes
skambinti masyvo staliukas, stalas laikiklis

669
00:28:10,770 --> 00:28:12,440
nulis viršuje stačiakampis.

670
00:28:12,440 --> 00:28:15,090
Stalo laikiklis 25 yra stačiakampis
apačioje.

671
00:28:15,090 --> 00:28:18,620
Ir tai, kaip aš galėtų vilkti duomenis
struktūrą, kurioje aš noriu laikyti

672
00:28:18,620 --> 00:28:19,790
žmonių vardus.

673
00:28:19,790 --> 00:28:24,370
>> Taigi, pavyzdžiui, ir aš ne atkreipti
Visa tai čia Viršuje, jei aš

674
00:28:24,370 --> 00:28:29,160
turėjo tai, masyvas, kurį aš dabar ketina
skambinti maišos lentelę, ir tai dar kartą

675
00:28:29,160 --> 00:28:31,360
vieta nuliui.

676
00:28:31,360 --> 00:28:34,840
Tai čia vieta
vienas, ir kt.

677
00:28:34,840 --> 00:28:37,880
Galiu reikalauti, kad aš noriu naudoti šiuos duomenis
struktūra, siekiant aptarti labui,

678
00:28:37,880 --> 00:28:42,600
saugoti žmonių vardus, Alisa ir Bobas
ir Čarlis ir kiti tokie pavadinimai.

679
00:28:42,600 --> 00:28:46,110
Taigi manau, tai dabar kaip pradžia
, tarkim, į žodyną

680
00:28:46,110 --> 00:28:47,520
su daug žodžių.

681
00:28:47,520 --> 00:28:49,435
Jie atsitiktų būti pavadinimai
Mūsų pavyzdyje čia.

682
00:28:49,435 --> 00:28:52,560
Ir visa tai per Germane, ko gero,
įgyvendinti rašybos tikrintuvą, kaip mes

683
00:28:52,560 --> 00:28:54,400
galėtų būti, problema nustatyti šešių.

684
00:28:54,400 --> 00:28:59,300
>> Taigi, jei mes turime bendro dydžio 26 masyvas
todėl, kad tai yra 25 vieta

685
00:28:59,300 --> 00:29:03,390
apačioje, ir galiu reikalauti, kad Alice
Pirmasis žodis žodyne

686
00:29:03,390 --> 00:29:07,260
vardai, noriu įterpti į RAM,
į šią duomenų struktūros, kur

687
00:29:07,260 --> 00:29:12,480
instinktai sakau, kad Alisos
pavadinimas turėtų eiti šiame masyve?

688
00:29:12,480 --> 00:29:13,510
>> Mes turime 26 variantų.

689
00:29:13,510 --> 00:29:14,990
Jeigu mes norime įdėti ją?

690
00:29:14,990 --> 00:29:16,200
Norime ją grupėje nulio, tiesa?

691
00:29:16,200 --> 00:29:18,280
Už Alice, pavadinkime, kad nulį.

692
00:29:18,280 --> 00:29:20,110
Ir B bus vienas ir C bus du.

693
00:29:20,110 --> 00:29:22,600
Taigi, mes ketiname rašyti
Alisos vardas čia.

694
00:29:22,600 --> 00:29:24,890
Jei mes tada įdėkite Bob, jo
pavadinimas bus eiti čia.

695
00:29:24,890 --> 00:29:27,280
Čarlis bus čia.

696
00:29:27,280 --> 00:29:30,500
Ir taip toliau žemyn per
tai duomenų struktūra.

697
00:29:30,500 --> 00:29:32,090
>> Tai nuostabi duomenų struktūra.

698
00:29:32,090 --> 00:29:32,730
Kodėl?

699
00:29:32,730 --> 00:29:37,460
Na, kas yra veikimo laikas
įterpiant žmogaus vardą į šią

700
00:29:37,460 --> 00:29:39,850
Duomenų struktūra dabar?

701
00:29:39,850 --> 00:29:43,702
Atsižvelgiant į tai, kad šioje lentelėje bus įgyvendinta,
tikrai, kaip masyvo.

702
00:29:43,702 --> 00:29:44,940
Na tai pastovus laikas.

703
00:29:44,940 --> 00:29:45,800
Tai, kad vienas.

704
00:29:45,800 --> 00:29:46,360
Kodėl?

705
00:29:46,360 --> 00:29:48,630
>> Na, kaip jūs nustatote,
kur Alisa priklauso?

706
00:29:48,630 --> 00:29:51,000
Jūs žiūrite kuris laiške savo vardą?

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

708
00:29:51,490 --> 00:29:54,350
Ir jūs galite gauti ten, jei tai eilutė,
tiesiog žiūri eilutę

709
00:29:54,350 --> 00:29:55,200
laikiklis nuliui.

710
00:29:55,200 --> 00:29:57,110
Taigi nulinis pobūdžio eilutę.

711
00:29:57,110 --> 00:29:57,610
Tai paprasta.

712
00:29:57,610 --> 00:30:00,350
Mes padarėme, kad kriptografija
priskyrimo savaites.

713
00:30:00,350 --> 00:30:05,310
Ir tada, kai jūs žinote, kad Alisos
laiškas yra kapitalo, mes galime atimti

714
00:30:05,310 --> 00:30:08,160
nuo 65 ar sostinę pati,
, kuri suteikia mums nulį.

715
00:30:08,160 --> 00:30:10,940
Taigi dabar mes žinome, kad pati Alice priklauso
ne vietoje nulio.

716
00:30:10,940 --> 00:30:14,240
>> Ir atsižvelgiant į rodyklę į šiuos duomenis
struktūra, tam tikros rūšies, kiek laiko

717
00:30:14,240 --> 00:30:18,840
jis mane rasti vietą
nulio masyvo?

718
00:30:18,840 --> 00:30:22,080
Tik vienas žingsnis, tiesa Tai pastovus laikas
dėl laisvosios kreipties mes

719
00:30:22,080 --> 00:30:23,780
Siūlomas buvo masyvo funkcija.

720
00:30:23,780 --> 00:30:28,570
Taigi trumpai tariant, suprasti, kas puslapis
iš Alisos vardas, kuris yra

721
00:30:28,570 --> 00:30:32,610
šiuo atveju yra, ar galime tik išspręsti
kad iki nulio, kur B yra viena, o C

722
00:30:32,610 --> 00:30:34,900
du, suprasti, kad iš
yra pastovus laikas.

723
00:30:34,900 --> 00:30:38,510
Aš tiesiog pažvelgti į savo pirmąjį laišką,
suprasti, kur nulis

724
00:30:38,510 --> 00:30:40,460
masyvo taip pat pastovus laikas.

725
00:30:40,460 --> 00:30:42,140
Taigi, techniškai tai
kaip dviem etapais dabar.

726
00:30:42,140 --> 00:30:43,330
Bet tai dar pastovi.

727
00:30:43,330 --> 00:30:46,880
Taigi mes vadiname, kad didelis Ö vieną, todėl mes
įterpiamas Alisa į šią lentelę

728
00:30:46,880 --> 00:30:48,440
pastovus laikas.

729
00:30:48,440 --> 00:30:50,960
>> Bet, žinoma, aš vis
naivus čia, tiesa?

730
00:30:50,960 --> 00:30:53,240
Ką daryti, jei ten klasėje Aaronas?

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

732
00:30:53,990 --> 00:30:57,230
Arba bet kokie kiti pavadinimai, pradedant
A. Kur mes einame įdėti

733
00:30:57,230 --> 00:31:00,800
kad asmuo, tiesa?

734
00:31:00,800 --> 00:31:03,420
Aš turiu galvoje, dabar yra tik trys
žmonės ant stalo, tai gal mes

735
00:31:03,420 --> 00:31:07,490
reikia įdėti Aaroną vietą
nulis vienas du trys.

736
00:31:07,490 --> 00:31:09,480
>> Teisė, galėčiau įdėti čia.

737
00:31:09,480 --> 00:31:13,350
Bet tada, jei mes stengiamės įdėti Dovydą į
Šis sąrašas, kur veikia Davidas einate?

738
00:31:13,350 --> 00:31:15,170
Dabar mūsų sistema pradeda skaidyti
žemyn, dešinėn?

739
00:31:15,170 --> 00:31:19,210
Kadangi dabar Davidas baigiasi čia
jei Aaronas tikrųjų čia.

740
00:31:19,210 --> 00:31:23,060
Ir todėl dabar ši idėja turėti
švarus duomenų struktūra, kuri suteikia mums

741
00:31:23,060 --> 00:31:28,010
nuolat laiko intarpai nebėra
pastovus laikas, nes turiu

742
00:31:28,010 --> 00:31:31,240
patikrinti, oi, velnių, kažkas jau
ne Alisos vietą.

743
00:31:31,240 --> 00:31:35,320
>> Leiskite zondas šių duomenų pailsėti
struktūra, ieško vietoje įdėti

744
00:31:35,320 --> 00:31:37,130
kažkas panašaus Aarono vardą.

745
00:31:37,130 --> 00:31:39,390
Ir todėl, kad per daug pradeda
priimti linijinį laiką.

746
00:31:39,390 --> 00:31:42,710
Be to, jei jūs dabar norite rasti
Aaronas šioje duomenų struktūros, ir jūs

747
00:31:42,710 --> 00:31:45,430
patikrinti ir Aarono vardas čia nėra.

748
00:31:45,430 --> 00:31:47,960
Būtų idealu, jei būtų tiesiog pasakyti Aarono
nėra duomenų struktūrą.

749
00:31:47,960 --> 00:31:51,530
Bet jei jūs pradėsite uždirbti vietos
Aaronas, kur turėjo būti D

750
00:31:51,530 --> 00:31:55,600
arba E, tu, blogiausiu atveju, turi patikrinti,
Visa duomenų struktūra, kad

751
00:31:55,600 --> 00:31:59,480
tokiu atveju ji pereina į kažką
tiesinė stalo dydžio.

752
00:31:59,480 --> 00:32:00,920
>> Taigi viskas gerai, aš tai pataisyti.

753
00:32:00,920 --> 00:32:04,200
Problema čia yra, kad aš
26 elementų šiame masyve.

754
00:32:04,200 --> 00:32:05,000
Leiskite pakeiskite jį.

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

756
00:32:06,010 --> 00:32:10,600
Leiskite man pakeisti jį taip, kad, o gerovė
iš viso 26 dydis, atkreipkite dėmesį dugną

757
00:32:10,600 --> 00:32:12,720
indeksas ketina pakeisti iki n minus 1.

758
00:32:12,720 --> 00:32:16,610
Jei 26 yra aiškiai per maža, žmonės "
pavadinimai, nes ten yra tūkstančiai

759
00:32:16,610 --> 00:32:20,830
pavadinimai pasaulyje, tegul tiesiog padaryti
iš 100 ar 1000 ar 10.000.

760
00:32:20,830 --> 00:32:22,960
Tegul tik skirti daug daugiau vietos.

761
00:32:22,960 --> 00:32:27,230
>> Na tai nebūtinai sumažės
Tikimybė, kad mes ne turėti du

762
00:32:27,230 --> 00:32:31,510
žmonės, kurių vardai prasideda ir
Taigi, jūs ketinate pabandyti įdėti

763
00:32:31,510 --> 00:32:33,120
vardus vietos nulio vietoje.

764
00:32:33,120 --> 00:32:36,850
Jie dar ketina susidurti, kuris
reiškia, kad mes vis dar reikia išspręsti įdėti

765
00:32:36,850 --> 00:32:41,020
Alisa ir Aaronas ir Alicia ir kiti
Vardai prasidedantys su A kitur.

766
00:32:41,020 --> 00:32:43,460
Bet kiek yra problema tai?

767
00:32:43,460 --> 00:32:46,870
Kas yra tikimybė, kad jūs
turi susidūrimų į duomenų

768
00:32:46,870 --> 00:32:48,240
struktūra, kaip tai?

769
00:32:48,240 --> 00:32:52,570
>> Na, leiskite man - mes grįžti
į šį klausimą čia.

770
00:32:52,570 --> 00:32:55,530
Ir pažvelgti, kaip mes galime
spręsti pirmiausia.

771
00:32:55,530 --> 00:32:58,480
Leiskite atsigriebti šį pasiūlymą čia.

772
00:32:58,480 --> 00:33:02,020
Ką mes ką tik aprašytos yra algoritmas,
euristinis vadinamas linijinis

773
00:33:02,020 --> 00:33:05,030
zondavimo, pagal kurią, jei jūs bandėte įdėti
kažkas čia šiuos duomenis

774
00:33:05,030 --> 00:33:08,920
struktūra, kuri yra vadinama maišos lentelė,
ir ten nėra vietos ten, jūs

775
00:33:08,920 --> 00:33:12,000
tikrai zondas duomenų struktūros
patikrinti, ar tai galima?

776
00:33:12,000 --> 00:33:13,430
Ar tai Turimas tai galima?

777
00:33:13,430 --> 00:33:13,980
Ar tai galima?

778
00:33:13,980 --> 00:33:17,550
Ir kai jis pagaliau yra įdėsite
pavadinimą, kad jūs iš pradžių skirti

779
00:33:17,550 --> 00:33:19,370
kitur toje vietoje.

780
00:33:19,370 --> 00:33:23,360
Tačiau blogiausiu atveju, tik vietoje
gali būti labai apačioje duomenis

781
00:33:23,360 --> 00:33:25,090
struktūra, labai pabaiga masyvo.

782
00:33:25,090 --> 00:33:30,130
>> Taigi linijinis zondavimas, blogiausiu atveju,
pereina į linijiniu algoritmu, kur

783
00:33:30,130 --> 00:33:34,500
Aaronas, jei jis atsitinka įterpiamas paskutinis
Šiame duomenų struktūros, jis gali

784
00:33:34,500 --> 00:33:39,540
susiduria su šios pirmosios vietos, tačiau
tada baigtis nesėkme pačioje pabaigoje.

785
00:33:39,540 --> 00:33:43,940
Taigi tai nėra pastovus
laikas Gralis mums.

786
00:33:43,940 --> 00:33:47,650
Šis įterpimą elementų požiūris į
duomenų struktūra vadinama maišos

787
00:33:47,650 --> 00:33:52,050
stalo neatrodo, kad būti pastovus laikas
bent jau ne bendrojo byloje.

788
00:33:52,050 --> 00:33:54,000
Jis gali perduoti į kažką linijinis.

789
00:33:54,000 --> 00:33:56,970
>> Taigi ką daryti, jei mes išspręsti susidūrimų
šiek tiek kitaip?

790
00:33:56,970 --> 00:34:00,740
Taigi čia vis sudėtingesnės
požiūris į tai, kas dar

791
00:34:00,740 --> 00:34:02,800
vadinama maišos lentelė.

792
00:34:02,800 --> 00:34:05,890
Ir maiša, nes žemę, ką
Aš turiu galvoje, yra puslapis, kad

793
00:34:05,890 --> 00:34:07,070
Aš nurodytas anksčiau.

794
00:34:07,070 --> 00:34:09,810
Norėdami maišos kažkas gali būti
suvokiami kaip veiksmažodis.

795
00:34:09,810 --> 00:34:13,690
>> Taigi, jei jūs maišos Alisos pavadinimas,
maišos funkcija, taip sakant,

796
00:34:13,690 --> 00:34:14,710
turėtų grįžti numerį.

797
00:34:14,710 --> 00:34:18,199
Šiuo atveju yra nulis, jei ji priklauso ne
vieta nulis, vienas, jei ji priklauso ne

798
00:34:18,199 --> 00:34:20,000
vieta viena, ir kt.

799
00:34:20,000 --> 00:34:24,360
Taigi, mano maišos funkcija iki šiol buvo
super paprasta, tik žiūri

800
00:34:24,360 --> 00:34:26,159
pirmoji raidė kieno nors vardu.

801
00:34:26,159 --> 00:34:29,090
Bet maišos funkcija priima kaip
įėjimas kai duomenų vienetą,

802
00:34:29,090 --> 00:34:30,210
eilutę, int, nesvarbu.

803
00:34:30,210 --> 00:34:32,239
Ir tai išspjauna specifiniu numerį.

804
00:34:32,239 --> 00:34:35,739
Ir šis skaičius yra kur, kad duomenys
elementas priklauso ir duomenų struktūros

805
00:34:35,739 --> 00:34:37,800
žinoma, čia kaip maišos lentelė.

806
00:34:37,800 --> 00:34:41,400
>> Taigi tiesiog intuityviai, tai
šiek tiek kitokiame kontekste.

807
00:34:41,400 --> 00:34:44,170
Tai iš tikrųjų yra nuoroda į pavyzdį
dalyvauja gimtadieniai, jei

808
00:34:44,170 --> 00:34:46,850
ten gali būti tiek, kiek
31 dienų mėnesį.

809
00:34:46,850 --> 00:34:52,239
Bet ką šis asmuo nusprendžia
daryti susidūrimo atveju?

810
00:34:52,239 --> 00:34:55,304
Kontekstas dabar yra, o ne susidūrimas
pavadinimai, bet apie gimtadienius susidūrimo,

811
00:34:55,304 --> 00:35:00,760
jei du žmonės turi tą patį gimtadienį
spalio 2 d, pvz.

812
00:35:00,760 --> 00:35:02,120
>> STUDENTŲ: [nesigirdi].

813
00:35:02,120 --> 00:35:05,010
>> GARSIAKALBIS 1: Taip, kad čia mes turime
sverto sujungtų sąrašus.

814
00:35:05,010 --> 00:35:07,830
Taigi atrodo šiek tiek kitaip
nei mes išsitraukė jį anksčiau.

815
00:35:07,830 --> 00:35:10,790
Bet mes, atrodo, turi masyvo
kairėje pusėje.

816
00:35:10,790 --> 00:35:13,230
Tai vienas indeksas, ne
ypatingos priežasties.

817
00:35:13,230 --> 00:35:14,630
Bet tai dar masyvo.

818
00:35:14,630 --> 00:35:16,160
Tai rodykles masyvo.

819
00:35:16,160 --> 00:35:20,670
Ir kiekvienas iš šių elementų, kiekvienas
šių apskritimų nerijos - velniop

820
00:35:20,670 --> 00:35:23,970
ty niekinis - kiekvienas iš jų
patarimų, matyt, nukreipta į

821
00:35:23,970 --> 00:35:25,730
kas duomenų struktūra?

822
00:35:25,730 --> 00:35:26,890
Susijęs sąrašą.

823
00:35:26,890 --> 00:35:30,530
>> Taigi dabar mes turime galimybę į
sunku kodą į mūsų programą

824
00:35:30,530 --> 00:35:32,010
pateiktos lentelės dydis.

825
00:35:32,010 --> 00:35:35,360
Tokiu atveju, mes žinome, kad niekada
daugiau nei 31 dienų per mėnesį.

826
00:35:35,360 --> 00:35:38,480
Taigi sunku kodavimo kaip 31 vertę,
pagrįstas šiame kontekste.

827
00:35:38,480 --> 00:35:42,700
Į pavadinimų kontekste, sunku kodavimo
26 nėra nepagrįsta tai sudaro žmonių

828
00:35:42,700 --> 00:35:46,340
pavadinimai tik pradėti, pavyzdžiui,
abėcėlė dalyvauja per Z.

829
00:35:46,340 --> 00:35:50,180
>> Mes galime prisikimšti juos visus į tą duomenų
struktūra tol, kol, kai mes gauti

830
00:35:50,180 --> 00:35:55,330
susidūrimo, mes ne pateikti pavardes čia
mes vietoj galvoti apie šių ląstelių

831
00:35:55,330 --> 00:36:00,270
ne kaip stygos patys, bet kaip
rodykles į, pavyzdžiui, Alice.

832
00:36:00,270 --> 00:36:03,660
Ir tada Alisa gali turėti kitą žymeklį
su kitu pavadinimu, pradedant

833
00:36:03,660 --> 00:36:06,150
A. Ir Bobas tikrųjų vyksta čia.

834
00:36:06,150 --> 00:36:10,850
>> Ir jei yra dar vienas pavadinimas prasideda
su B, jis baigiasi čia.

835
00:36:10,850 --> 00:36:15,070
Ir todėl kiekvienas iš šio elementų
stalo du, jei mes sukūrėme šį

836
00:36:15,070 --> 00:36:17,350
šiek tiek daugiau gudriai -

837
00:36:17,350 --> 00:36:18,125
come on -

838
00:36:18,125 --> 00:36:22,950
jei mes sukūrėme tai šiek tiek daugiau
protingai, dabar tampa prisitaikanti duomenis

839
00:36:22,950 --> 00:36:27,720
struktūra, kurioje nėra sunku apriboti
nuo to, kiek elementų galite įterpti

840
00:36:27,720 --> 00:36:30,700
į jį, nes jei jūs turite
susidūrimo, tai gerai.

841
00:36:30,700 --> 00:36:34,690
Tiesiog eikite į priekį ir pridėti jį prie
ką mes matėme šiek tiek atgal buvo

842
00:36:34,690 --> 00:36:38,290
žinomas kaip susietą sąrašą.

843
00:36:38,290 --> 00:36:39,690
>> Na galime pristabdyti tik akimirką.

844
00:36:39,690 --> 00:36:42,570
Kokia susidūrimo tikimybė
į pirmąją vietą?

845
00:36:42,570 --> 00:36:45,480
Teisė, gal aš per galvoju, gal
Aš per inžinerinių šią problemą,

846
00:36:45,480 --> 00:36:46,370
nes jūs žinote, ką?

847
00:36:46,370 --> 00:36:49,070
Taip, galiu sugalvoti savavališkai
pavyzdžių Off mano galvos viršaus, pavyzdžiui,

848
00:36:49,070 --> 00:36:52,870
Allison ir Aaronas, bet iš tikrųjų,
nes tolygiai pasiskirstytų

849
00:36:52,870 --> 00:36:56,990
įėjimai, kad yra keletas atsitiktinių intarpai
į duomenų struktūros, kas iš tikrųjų yra

850
00:36:56,990 --> 00:36:58,580
iš susidūrimo tikimybė?

851
00:36:58,580 --> 00:37:01,670
Na Pasirodo, tai tikrai
Super didelis.

852
00:37:01,670 --> 00:37:03,850
Leiskite man apibendrinti tai
Problema yra, kaip šis.

853
00:37:03,850 --> 00:37:08,890
>> Taigi daugelyje n kambarį CS50 studentų, kas
Tikimybė, kad bent

854
00:37:08,890 --> 00:37:11,010
du studentai kambarį
turi tas pačias gimtadienis?

855
00:37:11,010 --> 00:37:13,346
Taigi yra kas. keletas Hund -

856
00:37:13,346 --> 00:37:16,790
200, 300 žmonės čia ir keletas
šimtai žmonių namuose šiandien.

857
00:37:16,790 --> 00:37:20,670
Taigi, jei jūs norėjote paklausti savęs, kas
du žmonės tikimybė

858
00:37:20,670 --> 00:37:23,930
Šiame kambaryje, turintys tą patį gimtadienį,
galime suprasti tai.

859
00:37:23,930 --> 00:37:26,250
Ir galiu reikalauti iš tikrųjų yra du
žmonės su tuo pačiu gimtadienį.

860
00:37:26,250 --> 00:37:29,560
>> Pavyzdžiui, ar kas
turi šiandien švenčia gimtadienį?

861
00:37:29,560 --> 00:37:31,340
Vakar?

862
00:37:31,340 --> 00:37:32,590
Rytoj?

863
00:37:32,590 --> 00:37:35,980
Gerai, kad jis jaučiasi kaip aš ruošiuosi
turėti tai padaryti 363 arba tiek daugiau

864
00:37:35,980 --> 00:37:39,500
kartus tikrųjų išsiaiškinti
jei mes turime susidūrimo.

865
00:37:39,500 --> 00:37:42,350
Arba mes galime tiesiog padaryti tai matematiškai
o ne nuobodžiai

866
00:37:42,350 --> 00:37:43,200
tai daryti.

867
00:37:43,200 --> 00:37:44,500
Ir pasiūlyti veiksmus.

868
00:37:44,500 --> 00:37:48,740
>> Taigi, aš siūlau, kad mes galime modeliuoti
Tikimybė, du žmonės, turintys

869
00:37:48,740 --> 00:37:55,320
pats gimtadienis kaip 1 tikimybe
atėmus niekas turintys tikimybė

870
00:37:55,320 --> 00:37:56,290
pats gimtadienis.

871
00:37:56,290 --> 00:37:59,960
Taigi, norint gauti tai, ir tai tik
išgalvotas būdas tai rašau, nes

872
00:37:59,960 --> 00:38:03,090
pirmas žmogus į kambarį, jis ar ji
gali turėti bet įmanoma vieną

873
00:38:03,090 --> 00:38:07,370
gimtadieniai darant prielaidą, kad 365 dienų per metus,
su atsiprašymą asmenims, turintiems

874
00:38:07,370 --> 00:38:08,760
29 Vas gimtadienis.

875
00:38:08,760 --> 00:38:13,470
>> Taigi, pirmas žmogus šiame kambaryje nemokamai
turėti jokių gimtadienių numeris

876
00:38:13,470 --> 00:38:18,280
iš 365 galimybių, kad
mes tai padarysime 365 padalintas iš 365,

877
00:38:18,280 --> 00:38:18,990
kuri yra viena.

878
00:38:18,990 --> 00:38:22,700
Kitas asmuo kambaryje, jei tikslas
yra išvengti susidūrimo, galime tik

879
00:38:22,700 --> 00:38:26,460
jo arba jos gimtadienis, kaip
daug įvairių galimų dienų?

880
00:38:26,460 --> 00:38:27,610
364.

881
00:38:27,610 --> 00:38:31,430
Taigi antroji kadencija šiame išraiškos
esmės daro tą matematiką mums

882
00:38:31,430 --> 00:38:33,460
atėmus ne vieną galimą dieną.

883
00:38:33,460 --> 00:38:36,390
Ir tada kitą dieną, kitą dieną,
Kitą dieną iki bendro skaičiaus

884
00:38:36,390 --> 00:38:38,100
žmonių kambaryje.

885
00:38:38,100 --> 00:38:41,290
>> Ir jei mes tada apsvarstyti, ką gi
ne kiekvienas asmuo tikimybė

886
00:38:41,290 --> 00:38:45,265
unikalių gimtadieniai, tačiau ir vėl 1 atėmus
kad tai, ką mes gauti yra išraiška

887
00:38:45,265 --> 00:38:47,810
kuri gali labai Fantazyjnie
atrodyti taip.

888
00:38:47,810 --> 00:38:50,330
Bet tai įdomiau
ieškoti vizualiai.

889
00:38:50,330 --> 00:38:55,120
Tai schema kur ant x ašies yra
žmonių skaičius kambaryje,

890
00:38:55,120 --> 00:38:56,180
skaičius gimtadienius.

891
00:38:56,180 --> 00:38:59,840
Į Y ašies yra tikimybė,
dėl susidūrimo, du žmonės

892
00:38:59,840 --> 00:39:01,230
turintys tą patį gimtadienį.

893
00:39:01,230 --> 00:39:05,020
>> Ir Pagal šią kreivę išsinešimui yra
kad kaip tik jums patinka 40

894
00:39:05,020 --> 00:39:11,110
studentų, esate į 90% tikimybe
combinatorically dviejų

895
00:39:11,110 --> 00:39:13,550
žmonės ar daugiau turintys
pats gimtadienis.

896
00:39:13,550 --> 00:39:18,600
Ir kai jums patinka 58 žmonėms tai
beveik 100% progos dviejų

897
00:39:18,600 --> 00:39:21,310
žmonių kambaryje teks
pats gimtadienis, nors ten

898
00:39:21,310 --> 00:39:26,650
365 arba 366 galimi kaušai ir
tik 58 žmonių kambaryje.

899
00:39:26,650 --> 00:39:29,900
Tiesiog statistiškai jūs greičiausiai
gauti susidūrimų, kuris trumpai

900
00:39:29,900 --> 00:39:31,810
motyvuoja šią diskusiją.

901
00:39:31,810 --> 00:39:35,890
Kad net jei mes gauti išgalvotas čia, ir
pradėti turintys šių grandines, mes vis dar

902
00:39:35,890 --> 00:39:36,950
teks susidūrimų.

903
00:39:36,950 --> 00:39:42,710
>> Taigi, kad kyla klausimas, kas yra
kaina tai įkišimo ir naikinimus

904
00:39:42,710 --> 00:39:44,850
į duomenų struktūros, kaip tai?

905
00:39:44,850 --> 00:39:46,630
Na leiskite man pasiūlyti -

906
00:39:46,630 --> 00:39:51,570
ir leiskite man grįžti prie ekrano per
čia - jei mes n elementų

907
00:39:51,570 --> 00:39:56,330
sąrašas, todėl, jei mes bandome įterpti
n elementų, ir mes turime

908
00:39:56,330 --> 00:39:58,050
kiek iš viso kibirai?

909
00:39:58,050 --> 00:40:03,450
Tarkime, kad 31 iš viso kibirus
į gimtadienius atveju.

910
00:40:03,450 --> 00:40:09,240
Koks maksimalus ilgis vieno
Šių tinklų potencialiai?

911
00:40:09,240 --> 00:40:12,670
>> Jei vėl ten 31 galima
Gimtadieniai tam tikrą mėnesį.

912
00:40:12,670 --> 00:40:14,580
Ir mes tiesiog drumzlių visus -

913
00:40:14,580 --> 00:40:15,580
iš tikrųjų tai kvailas pavyzdys.

914
00:40:15,580 --> 00:40:16,960
Padarykim 26 vietoj.

915
00:40:16,960 --> 00:40:20,890
Taigi, jei iš tikrųjų turi žmones, kurių vardai ir pavardės
pradėti iki Z, taip suteikiant

916
00:40:20,890 --> 00:40:22,780
mus 26 galimybių.

917
00:40:22,780 --> 00:40:25,920
Ir mes naudojame duomenų struktūrą kaip
vienas mes tik pamačiau, kai mes turime

918
00:40:25,920 --> 00:40:30,210
rodykles masyvas, kurių kiekvienas
atkreipia dėmesį į susietą sąrašą, kur

919
00:40:30,210 --> 00:40:32,360
Pirmasis sąrašas yra visi
su pavadinimu Alisa.

920
00:40:32,360 --> 00:40:35,770
Antrame sąraše yra visos su
pavadinimas pradedant, pradedant

921
00:40:35,770 --> 00:40:36,980
su B, ir kt.

922
00:40:36,980 --> 00:40:41,020
>> Kas greičiausiai ilgis kiekvieno
šie sąrašai jei mes manome, gražus švarus

923
00:40:41,020 --> 00:40:45,410
paskirstymo pavadinimų iki Z
visoje duomenų struktūros?

924
00:40:45,410 --> 00:40:50,210
Yra n žmonių duomenų struktūros
padalintas iš 26, jei jie gražiai

925
00:40:50,210 --> 00:40:52,110
paskirstyti per visą
duomenų struktūra.

926
00:40:52,110 --> 00:40:54,970
Taigi kiekvienos iš šių ilgis
tinklai yra n dalijamas iš 26.

927
00:40:54,970 --> 00:40:57,380
Tačiau didelis O žymėjimą, kas tai?

928
00:40:57,380 --> 00:41:00,100

929
00:41:00,100 --> 00:41:02,440
Kas tai tikrai?

930
00:41:02,440 --> 00:41:04,150
Taigi tai tikrai tik n, tiesa?

931
00:41:04,150 --> 00:41:06,620
Kadangi mes jau sakiau anksčiau,
kad ugh jums padalinti iš 26.

932
00:41:06,620 --> 00:41:08,710
Taip, iš tikrųjų jis yra greitesnis.

933
00:41:08,710 --> 00:41:12,720
Tačiau teoriškai tai nėra iš esmės
visa tai greičiau.

934
00:41:12,720 --> 00:41:16,040
>> Taigi mes neatrodo, kad būti visi, kad daug
arčiau šio Gralis.

935
00:41:16,040 --> 00:41:17,750
Tiesą sakant, tai yra tik linijinis laikas.

936
00:41:17,750 --> 00:41:20,790
Heck, šiuo metu, kodėl ne mes
tiesiog naudoti vienas didžiulis susijęs sąrašą?

937
00:41:20,790 --> 00:41:23,510
Kodėl mes tiesiog naudoti vienas didžiulis
masyvas saugoti vardai

938
00:41:23,510 --> 00:41:25,010
visi į kambarį?

939
00:41:25,010 --> 00:41:28,280
Na, ar dar kažkas
įtikinamų apie maišos lentelė?

940
00:41:28,280 --> 00:41:30,810
Ar yra dar kažkas įtikinamų
apie duomenų struktūros

941
00:41:30,810 --> 00:41:33,940
kad atrodo taip?

942
00:41:33,940 --> 00:41:35,182
Tai.

943
00:41:35,182 --> 00:41:37,050
>> STUDENTŲ: [nesigirdi].

944
00:41:37,050 --> 00:41:39,840
>> GARSIAKALBIS 1: Teisė, ir dar kartą, jei tai tik
linijinis laikas algoritmas ir

945
00:41:39,840 --> 00:41:42,780
linijinis laiko duomenų struktūra, kodėl ne aš
tiesiog laikyti kiekvieno vardą didelis

946
00:41:42,780 --> 00:41:44,210
masyvas, arba į didelį susijusios sąraše?

947
00:41:44,210 --> 00:41:47,010
Ir nebedaryti CS tiek daug sunkiau
nei ji turi būti?

948
00:41:47,010 --> 00:41:49,600

949
00:41:49,600 --> 00:41:53,190
Kas yra įtikinamų apie tai, net
nors aš subraižyti jį?

950
00:41:53,190 --> 00:41:54,930
>> STUDENTŲ: [nesigirdi].

951
00:41:54,930 --> 00:41:57,040
>> GARSIAKALBIS 1 intarpai yra ne?

952
00:41:57,040 --> 00:41:58,140
Brangus nebėra.

953
00:41:58,140 --> 00:42:03,390
Taigi intarpai potencialiai galėtų dar
būti pastovus laikas, net jei jūsų duomenų

954
00:42:03,390 --> 00:42:07,910
struktūra atrodo taip, masyvas
patarimų, kurių kiekviena yra nukreipta į

955
00:42:07,910 --> 00:42:09,550
potencialiai Tinkliniai sąrašą.

956
00:42:09,550 --> 00:42:15,220
Kaip tu galėjai pasiekti pastovus
laikas įterpimo vardų?

957
00:42:15,220 --> 00:42:16,280
Klijuoti jį į priekį, tiesa?

958
00:42:16,280 --> 00:42:19,290
>> Jei mes paaukoti dizaino įvarčio
anksčiau, kur mes norėjome išlaikyti

959
00:42:19,290 --> 00:42:22,650
kiekvienas vardas, pavyzdžiui, rūšiuojami,
ar visi ant scenos numerius rūšiuojami,

960
00:42:22,650 --> 00:42:25,020
tarkime, kad turime
Unsorted susijęs sąrašą.

961
00:42:25,020 --> 00:42:29,960
Tai kainuoja tik mums vieną ar du žingsnius,
Kaip ir Ben ir Brian atveju

962
00:42:29,960 --> 00:42:32,750
anksčiau, įterpti elementą į
sąrašo pradžioje.

963
00:42:32,750 --> 00:42:36,090
Taigi, jei mes nerūpi rūšiavimo visas
pavadinimų, prasidedančių arba visas

964
00:42:36,090 --> 00:42:39,660
vardai prasidedantys raide B, mes vis dar galime
pasiekti pastovią laiko užpildymui.

965
00:42:39,660 --> 00:42:43,900
Dabar žiūrint Alisa arba Bob arba bet kokį vardą
apskritai dar kas?

966
00:42:43,900 --> 00:42:48,100
Tai didelis O n dalijamas iš 26 visų
idealus atvejis, kai visi yra vienodai

967
00:42:48,100 --> 00:42:51,190
paskirstyti, kur yra tiek daug s
nes yra Z, kuris yra tikriausiai

968
00:42:51,190 --> 00:42:52,220
nerealus.

969
00:42:52,220 --> 00:42:53,880
Bet tai dar tiesinis.

970
00:42:53,880 --> 00:42:57,120
>> Bet čia mes einame atgal iki taško,
iš asimptotinėje notacijos Būdama

971
00:42:57,120 --> 00:42:58,600
teoriškai tiesa.

972
00:42:58,600 --> 00:43:02,960
Tačiau realiame pasaulyje, jei galiu reikalauti, kad
mano programa gali ką nors padaryti 26 kartų

973
00:43:02,960 --> 00:43:06,210
greičiau nei jūsų, kurių programa
jūs ketinate nori naudojate?

974
00:43:06,210 --> 00:43:09,660
Jūsų arba mano, kuris
yra 26 kartų greičiau?

975
00:43:09,660 --> 00:43:14,320
Nereikėtų pamiršti, kad asmuo, kurio yra 26
kartų greičiau, net jei teoriškai

976
00:43:14,320 --> 00:43:18,790
mūsų algoritmai paleisti pats
asymptotic darbo.

977
00:43:18,790 --> 00:43:20,940
>> Leiskite man pasiūlyti skirtingi
sprendimas apskritai.

978
00:43:20,940 --> 00:43:24,380
Ir jei tai nėra smūgis apsigalvoti,
mes iš duomenų struktūrų.

979
00:43:24,380 --> 00:43:27,420
Taigi, tai jis trie -

980
00:43:27,420 --> 00:43:28,520
rūšies kvailas pavadinimas.

981
00:43:28,520 --> 00:43:32,880
Jis kilęs iš paieškų, o žodis
rašomas TRIE, T-R-i-E, nes

982
00:43:32,880 --> 00:43:34,450
kursas paieška skamba kaip TRIE.

983
00:43:34,450 --> 00:43:36,580
Bet tai istorija
žodžio TRIE.

984
00:43:36,580 --> 00:43:40,980
>> Taigi trie yra iš tiesų, kai medžių rūšis,
ir tai taip pat tą žodį žaisti.

985
00:43:40,980 --> 00:43:46,330
Ir nors jums gali ne visai matyti
su šiuo vizualizacija, trie yra

986
00:43:46,330 --> 00:43:50,790
medžio struktūra, kaip šeimos medį
viena protėvis viršuje ir daug

987
00:43:50,790 --> 00:43:54,530
anūkai ir proanūkiai
kaip palieka ant dugno.

988
00:43:54,530 --> 00:43:58,100
Tačiau kiekvienas į TRIE mazgas yra masyvas.

989
00:43:58,100 --> 00:44:00,680
Ir tai masyve - ir tegul
per daug supaprastinti for a moment, - tai

990
00:44:00,680 --> 00:44:04,600
masyvas, šiuo atveju, dydžio 26, kur
kiekvienas mazgas vėl yra dydžio masyvas

991
00:44:04,600 --> 00:44:09,000
26, kur nulinis elementas, kad
masyvuose, o paskutinis

992
00:44:09,000 --> 00:44:11,810
elementas kiekvienas toks
masyvas yra Z.

993
00:44:11,810 --> 00:44:15,520
>> Taigi aš siūlau, tada, kad šie duomenys
struktūra, vadinama TRIE, gali būti

994
00:44:15,520 --> 00:44:17,600
naudojamas taip pat saugoti žodžius.

995
00:44:17,600 --> 00:44:21,740
Mes matėme metu senumo, kaip mes galime laikyti
Kitaip tariant, ar šiuo atveju pavadinimų, ir mes

996
00:44:21,740 --> 00:44:25,440
matėme, kaip mes galime laikyti numerius,
bet jei mes orientuojamės į pavadinimų ar tinkleliuose

997
00:44:25,440 --> 00:44:27,460
čia pastebėti tai, kas įdomu.

998
00:44:27,460 --> 00:44:32,210
Galiu reikalauti, kad vardas Maxwell
viduje šios duomenų struktūros.

999
00:44:32,210 --> 00:44:33,730
Kur matote Maxwell?

1000
00:44:33,730 --> 00:44:35,140
>> STUDENTŲ: [nesigirdi].

1001
00:44:35,140 --> 00:44:36,240
>> GARSIAKALBIS 1: Kairėje.

1002
00:44:36,240 --> 00:44:39,910
Taigi, kas įdomu šiuos duomenis
struktūra, o ne saugoti

1003
00:44:39,910 --> 00:44:46,200
styginių M-X-W-El-L-L Backslash nulis, visi
Kaimynystėje, ką jūs, o ne daryti

1004
00:44:46,200 --> 00:44:46,890
laikosi.

1005
00:44:46,890 --> 00:44:50,510
Jei tai, pavyzdžiui, duomenų struktūros trie,
kiekvieno iš jų mazgų vėl masyvas,

1006
00:44:50,510 --> 00:44:54,650
ir norite išsaugoti Maxwell, pirmiausia
indeksas ir taip šaknis mazge, todėl

1007
00:44:54,650 --> 00:44:57,810
kalbėti, viršutinį mazgą,
ne vietos M, teisė, todėl

1008
00:44:57,810 --> 00:44:59,160
maždaug į vidurį.

1009
00:44:59,160 --> 00:45:03,740
Ir iš ten, jums sekti
rodyklė vaikas mazgai, taip sakant.

1010
00:45:03,740 --> 00:45:06,150
Taigi, šeimos medį prasme,
jums sekti jį žemyn.

1011
00:45:06,150 --> 00:45:09,030
Ir, kad nuves jus į kitą mazgą
Kairėje, kuris yra

1012
00:45:09,030 --> 00:45:10,540
tik dar vienas masyvas.

1013
00:45:10,540 --> 00:45:14,710
>> Ir tada, jei norite išsaugoti Maxwell,
Jums susirasti žymiklį, kuri atstovauja

1014
00:45:14,710 --> 00:45:16,430
, O tai yra vienas iš čia.

1015
00:45:16,430 --> 00:45:17,840
Tada jūs einate į kitą mazgą.

1016
00:45:17,840 --> 00:45:20,100
Ir pranešimas - tai kodėl paveikslėlio
šiek tiek klaidinantis -

1017
00:45:20,100 --> 00:45:21,990
tai mazgas atrodo super maža.

1018
00:45:21,990 --> 00:45:26,050
Tačiau šios teisės yra Y ir Z.
Tai tiesiog autorius sutrumpintas

1019
00:45:26,050 --> 00:45:27,630
paveikslėlį tiek, kad jūs iš tikrųjų
pamatyti dalykus.

1020
00:45:27,630 --> 00:45:30,400
Priešingu atveju šį paveiksliuką
Būtų labai platus.

1021
00:45:30,400 --> 00:45:36,180
Taigi, dabar jūs indeksą į vietos X, tada
W Tada E, tada L, tada L. Tada kas

1022
00:45:36,180 --> 00:45:37,380
tai smalsumas?

1023
00:45:37,380 --> 00:45:41,250
>> Na, jei mes naudojame šią naujos rūšies
imtis, kaip saugoti eilutę

1024
00:45:41,250 --> 00:45:44,500
duomenų struktūra, jums vis tiek reikia
iš esmės patikrinti išjungti duomenų

1025
00:45:44,500 --> 00:45:47,250
struktūra, kad žodis baigiasi čia.

1026
00:45:47,250 --> 00:45:50,830
Kitaip tariant, kiekvienas iš šių mazgų
kažkaip turi prisiminti, kad mes

1027
00:45:50,830 --> 00:45:53,500
laikytasi visų šių patarimų
ir palieka mažai

1028
00:45:53,500 --> 00:45:58,370
duonos trupiniai apačioje čia šio
struktūra rodo, M-A-X-W-e-L-L yra

1029
00:45:58,370 --> 00:46:00,230
Iš tiesų šioje duomenų struktūra.

1030
00:46:00,230 --> 00:46:02,040
>> Taigi, mes galime tai padaryti taip.

1031
00:46:02,040 --> 00:46:06,810
Kiekvienas iš paveikslėlio Mes tiesiog mazgų
Pjūklas turi vieną, dydžio 27 masyvo.

1032
00:46:06,810 --> 00:46:10,550
Ir tai dabar 27, nes p nustatytas šešių,
mes tikrai suteiks jums kabutes,

1033
00:46:10,550 --> 00:46:13,590
todėl mes galime turėti tokius pavadinimus kaip O'Reilly
ir kiti su kabutes.

1034
00:46:13,590 --> 00:46:14,820
Bet pati idėja.

1035
00:46:14,820 --> 00:46:17,710
Kiekvienas iš šių elementų
masyvo nukreipia į struct

1036
00:46:17,710 --> 00:46:19,320
mazgų, vartotojų tad tiesiog mazgas.

1037
00:46:19,320 --> 00:46:21,430
Taigi tai yra labai primenantis
mūsų susietą sąrašą.

1038
00:46:21,430 --> 00:46:24,550
>> Ir tada aš turiu Būlio, kurį aš
skambinti žodį, kuris yra tik bus

1039
00:46:24,550 --> 00:46:29,120
tiesa, jei žodis baigiasi tai
mazgas medžio.

1040
00:46:29,120 --> 00:46:32,870
Jis efektyviai atstovauja mažai
trikampis matėme prieš akimirką.

1041
00:46:32,870 --> 00:46:37,190
Taigi, jei žodis baigiasi tos mazgas
medis, kad žodis laukas bus tiesa,

1042
00:46:37,190 --> 00:46:41,990
kuris konceptualiai Odfajkowanie arba
mes piešimo Šis trikampis, taip nėra

1043
00:46:41,990 --> 00:46:44,080
yra žodis čia.

1044
00:46:44,080 --> 00:46:45,120
>> Taigi tai yra trie.

1045
00:46:45,120 --> 00:46:48,540
Ir dabar klausimas, ką
yra jo veikimo laikas?

1046
00:46:48,540 --> 00:46:49,930
Ar tai didelis O n?

1047
00:46:49,930 --> 00:46:51,410
Ar tai kažkas kita?

1048
00:46:51,410 --> 00:46:57,330
Na, jei jūs turite n vardus šiuos duomenis
struktūra, Maksvelo gerovę tik vienas

1049
00:46:57,330 --> 00:47:02,330
jiems, kas yra veikimo laikas
įdėdami arba rasti Maxwell?

1050
00:47:02,330 --> 00:47:06,230

1051
00:47:06,230 --> 00:47:09,050
Kas važiavimo laikas
įterpti Maxwell?

1052
00:47:09,050 --> 00:47:11,740
Jei yra n kitų pavadinimų
jau stalo?

1053
00:47:11,740 --> 00:47:12,507
Taip?

1054
00:47:12,507 --> 00:47:15,429
>> STUDENTŲ: [nesigirdi].

1055
00:47:15,429 --> 00:47:17,550
>> GARSIAKALBIS 1: Taip, tai ilgis
vardo, tiesa?

1056
00:47:17,550 --> 00:47:24,420
Taigi M-x-w-e-l-l, kad jis jaučiasi kaip tai
algoritmas yra didelis O iš septynių.

1057
00:47:24,420 --> 00:47:26,580
Dabar, žinoma, pavadinimas
ilgis gali būti įvairus.

1058
00:47:26,580 --> 00:47:27,380
Gal tai sutrumpintas pavadinimas.

1059
00:47:27,380 --> 00:47:28,600
Gal tai jau pavadinimas.

1060
00:47:28,600 --> 00:47:33,390
Bet kas svarbiausia čia yra tai, kad
tai pastovus skaičius.

1061
00:47:33,390 --> 00:47:36,810
O gal tai nėra labai pastovus,
Bet Dievas, jei realiai, į

1062
00:47:36,810 --> 00:47:41,570
žodyną, ten tikriausiai kai riba
dėl laiškų skaičių

1063
00:47:41,570 --> 00:47:43,820
asmens vardas konkrečioje šalyje.

1064
00:47:43,820 --> 00:47:46,940
>> Ir taip mes galime manyti, kad
vertė yra pastovi.

1065
00:47:46,940 --> 00:47:47,750
Aš nežinau, kas tai yra.

1066
00:47:47,750 --> 00:47:50,440
Tai tikriausiai didesnis nei
mes manome, kad ji yra.

1067
00:47:50,440 --> 00:47:52,720
Nes ten visada kai kampas
atveju su crazy ilgu pavadinimu.

1068
00:47:52,720 --> 00:47:56,360
Taigi galime vadinti k, bet jis vis dar
pastovus matyt, nes kiekvienas

1069
00:47:56,360 --> 00:48:00,190
vardas pasaulyje, bent jau
pirma šalis, yra tai, kad ilgis arba

1070
00:48:00,190 --> 00:48:01,780
trumpesnis, todėl pastovus.

1071
00:48:01,780 --> 00:48:04,490
Bet kai mes kažką pasakė yra didelis
O iš pastovios vertės, kas tai

1072
00:48:04,490 --> 00:48:07,760
tikrai atitiks?

1073
00:48:07,760 --> 00:48:10,420
Tai tikrai tas pats
kaip sako pastovų laiką.

1074
00:48:10,420 --> 00:48:11,530
>> Dabar mes rūšies sukčiavimo, tiesa?

1075
00:48:11,530 --> 00:48:15,340
Mes rūšies sverto tam tikrą teoriją
čia pasakyti, kad gerai, kad iš K

1076
00:48:15,340 --> 00:48:17,450
tikrai tik kad vienas,
ir tai pastovus laikas.

1077
00:48:17,450 --> 00:48:18,200
Bet ji tikrai yra.

1078
00:48:18,200 --> 00:48:22,550
Kadangi pagrindinė įžvalga yra ta, kad
jei mes n vardus jau tai

1079
00:48:22,550 --> 00:48:26,010
duomenų struktūra, ir mes įterpti Maksvelo
yra laiko užtrunka mus

1080
00:48:26,010 --> 00:48:29,530
įterpti Maxwell kiek nenukenčia
pagal tai, kiek kiti žmonės

1081
00:48:29,530 --> 00:48:31,100
yra duomenų struktūros?

1082
00:48:31,100 --> 00:48:31,670
Ar neatrodo, kad būti.

1083
00:48:31,670 --> 00:48:36,280
Jeigu aš turėjo milijardą daugiau elementų į šį
trie ir įdėkite Maxwell, yra

1084
00:48:36,280 --> 00:48:38,650
jis išvis veikia?

1085
00:48:38,650 --> 00:48:39,050
Ne.

1086
00:48:39,050 --> 00:48:42,950
Ir tai, skirtingai nei bet kuriuo paros duomenų
struktūros mes matėme iki šiol, kur

1087
00:48:42,950 --> 00:48:46,820
veikimo laikas jūsų algoritmas
visiškai nepriklausomi nuo to, kiek

1088
00:48:46,820 --> 00:48:51,430
medžiaga yra ar nėra jau
toje duomenų struktūra.

1089
00:48:51,430 --> 00:48:54,650
>> Ir taip su tai suteikia jums dabar yra
galimybė šešių rinkinys p, kuris bus

1090
00:48:54,650 --> 00:48:58,310
vėl įtraukti įgyvendinant savo
Rašybos tikrintuvas, skaityti 150.000

1091
00:48:58,310 --> 00:49:01,050
žodžiai, kaip geriausia laikyti, kad
nebūtinai yra akivaizdūs.

1092
00:49:01,050 --> 00:49:04,030
Ir nors aš tikėjosi rasti
Gralis, aš ne

1093
00:49:04,030 --> 00:49:05,330
teigia, kad trie yra.

1094
00:49:05,330 --> 00:49:09,810
Tiesą sakant, maišos lentelė gali labai gerai
įrodyti, kad bus daug efektyvesnis.

1095
00:49:09,810 --> 00:49:10,830
Tačiau tai tik -

1096
00:49:10,830 --> 00:49:14,620
tai tik vienas iš dizaino sprendimus
jūs turite padaryti.

1097
00:49:14,620 --> 00:49:18,920
>> Tačiau uždarymo Paimkime 50 ar taip
sekundžių pažvelkite, kas slypi žvilgtelėti

1098
00:49:18,920 --> 00:49:22,190
prieš kitą savaitę ir vėliau mes pereiti
iš šio komandinės eilutės

1099
00:49:22,190 --> 00:49:26,220
pasaulyje, jei C programos dalykų internete
pagrįstas ir kalba kaip PHP ir

1100
00:49:26,220 --> 00:49:30,350
JavaScript ir interneto pati,
protokolai, pavyzdžiui, HTTP, kurios jūs

1101
00:49:30,350 --> 00:49:32,870
savaime suprantamu dalyku metų
dabar, ir įvedėte labiausiai kiekvienas

1102
00:49:32,870 --> 00:49:34,440
dieną, galbūt, ar matė.

1103
00:49:34,440 --> 00:49:37,420
Ir mes pradėsime žievelės atgal
sluoksniai, kas yra internetas.

1104
00:49:37,420 --> 00:49:40,650
Ir kas yra kodas, kuris
scenarijumi grindžiamos šiandienos įrankiai.

1105
00:49:40,650 --> 00:49:43,230
Taigi 50 sekundžių šio erzina čia.

1106
00:49:43,230 --> 00:49:46,570
Aš jums Warriors internete.

1107
00:49:46,570 --> 00:49:51,370
>> [VIDEO PLAYBACK]

1108
00:49:51,370 --> 00:49:56,764
>> -Jis atėjo su pranešimu.

1109
00:49:56,764 --> 00:50:00,687
Su protokolu, visi jo paties.

1110
00:50:00,687 --> 00:50:13,370

1111
00:50:13,370 --> 00:50:19,780
Jis atėjo į žiaurių ugniasienių pasaulyje,
uncaring maršrutizatoriai, ir pavojus toli

1112
00:50:19,780 --> 00:50:22,600
blogiau, nei mirties.

1113
00:50:22,600 --> 00:50:23,590
Jis greitas.

1114
00:50:23,590 --> 00:50:25,300
Jis stiprus.

1115
00:50:25,300 --> 00:50:27,700
Jis TCPIP.

1116
00:50:27,700 --> 00:50:30,420
Ir jis gavo savo adresą.

1117
00:50:30,420 --> 00:50:32,920

1118
00:50:32,920 --> 00:50:34,590
Warriors internete.

1119
00:50:34,590 --> 00:50:35,290
>> [PABAIGA VIDEO PLAYBACK]

1120
00:50:35,290 --> 00:50:38,070
>> GARSIAKALBIS 1: Štai kaip interneto
turi veikti kaip kitą savaitę.

1121
00:50:38,070 --> 00:50:40,406