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

2
00:00:11,860 --> 00:00:13,120
>> SPEAKER 1: Labi, tāpēc mēs esam atpakaļ.

3
00:00:13,120 --> 00:00:14,480
Laipni lūdzam CS50.

4
00:00:14,480 --> 00:00:16,510
Tas ir beigu septiņiem nedēļā.

5
00:00:16,510 --> 00:00:20,200
Tāpēc atgādinām, ka pēdējo reizi, mēs sākām
meklē nedaudz sarežģītāka

6
00:00:20,200 --> 00:00:21,100
datu struktūras.

7
00:00:21,100 --> 00:00:25,110
Tā kā līdz šim, viss, kas mums bija patiešām
mūsu rīcībā bija tas, masīvs.

8
00:00:25,110 --> 00:00:29,340
>> Taču, pirms mēs izmestu masīvs, jo ne
visu, kas interesants, ko tas patiešām

9
00:00:29,340 --> 00:00:33,570
faktiski ir, kādi ir daži no
plusi šo vienkāršo datu

10
00:00:33,570 --> 00:00:34,560
struktūru līdz šim?

11
00:00:34,560 --> 00:00:36,110
Kas ir tas labi?

12
00:00:36,110 --> 00:00:39,450
Līdz šim, kā mēs esam redzējuši?

13
00:00:39,450 --> 00:00:42,540
Ko jums?

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

15
00:00:44,028 --> 00:00:45,020
>> STUDENTU: [nedzirdama].

16
00:00:45,020 --> 00:00:45,395
>> SPEAKER 1: Kas tas ir?

17
00:00:45,395 --> 00:00:46,410
>> STUDENTU: [nedzirdama].

18
00:00:46,410 --> 00:00:47,000
>> SPEAKER 1: Fiksēta izmēra.

19
00:00:47,000 --> 00:00:51,260
Labi, tad kāpēc ir fiksēta izmēra laba, lai gan?

20
00:00:51,260 --> 00:00:53,180
>> STUDENTU: [nedzirdama].

21
00:00:53,180 --> 00:00:56,240
>> SPEAKER 1: Labi, tāpēc tas ir efektīvs
sajūta, ka jūs varat piešķirt

22
00:00:56,240 --> 00:01:00,070
fiksēta summa telpu, kas, cerams,
Tieši tik daudz

23
00:01:00,070 --> 00:01:01,180
kosmosa, kā jūs vēlaties.

24
00:01:01,180 --> 00:01:02,720
Tātad tas varētu būt absolūti plus.

25
00:01:02,720 --> 00:01:06,530
>> Kas vēl veido puse no masīva?

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

27
00:01:07,610 --> 00:01:08,750
>> STUDENTU: [nedzirdama].

28
00:01:08,750 --> 00:01:09,550
>> SPEAKER 1: Visi - žēl?

29
00:01:09,550 --> 00:01:11,270
>> STUDENTU: [nedzirdama].

30
00:01:11,270 --> 00:01:13,620
>> SPEAKER 1: Visas kastes atmiņā
vai blakus viens otram.

31
00:01:13,620 --> 00:01:15,220
Un tas ir noderīgi, - kāpēc?

32
00:01:15,220 --> 00:01:15,970
Tas ir diezgan patiess.

33
00:01:15,970 --> 00:01:18,611
Bet kā mēs varam izmantot šo patiesību?

34
00:01:18,611 --> 00:01:21,500
>> STUDENTU: [nedzirdama].

35
00:01:21,500 --> 00:01:24,490
>> SPEAKER 1: Tieši tā, mēs varam sekot
kur viss ir vienkārši zinot

36
00:01:24,490 --> 00:01:28,560
viens adrese, proti, no adrese
Pirmais baits šī rieciens atmiņas.

37
00:01:28,560 --> 00:01:30,420
Vai gadījumā, ja no virknes,
adrese no pirmā

38
00:01:30,420 --> 00:01:31,460
char šajā virknē.

39
00:01:31,460 --> 00:01:33,330
Un no turienes, mēs varam atrast
beigām virkni.

40
00:01:33,330 --> 00:01:35,710
Mēs varam atrast uz otro elementu, ka
Trešais elements, un tā tālāk.

41
00:01:35,710 --> 00:01:38,740
>> Un tā iedomātā veids, kā aprakstīt, ka
iezīme ir tā, ka masīvi dod mums

42
00:01:38,740 --> 00:01:40,020
brīvpieejas.

43
00:01:40,020 --> 00:01:44,330
, Tikai izmantojot kvadrātiekava
nošu un numuru, jūs varat pāriet uz

44
00:01:44,330 --> 00:01:48,070
īpašs elements masīva
pastāvīgu laiku, Big O

45
00:01:48,070 --> 00:01:49,810
vienu, lai runāt.

46
00:01:49,810 --> 00:01:51,080
>> Bet tur ir bijuši daži downsides.

47
00:01:51,080 --> 00:01:53,110
Kas masīvs nav darīt ļoti viegli?

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

49
00:01:55,810 --> 00:01:57,170
Kas ir tas nav labi?

50
00:01:57,170 --> 00:01:58,810
>> STUDENTU: [nedzirdama].

51
00:01:58,810 --> 00:01:59,860
>> SPEAKER 1: Kas tas ir?

52
00:01:59,860 --> 00:02:00,530
>> STUDENTU: [nedzirdama].

53
00:02:00,530 --> 00:02:01,460
>> SPEAKER 1: Paplašinot lieluma.

54
00:02:01,460 --> 00:02:04,800
Tātad no masīva downsides ir
tieši pretējs tam, ko

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

56
00:02:05,540 --> 00:02:07,610
Tātad, viens no downsides ir
ka tā ir fiksēta izmēra.

57
00:02:07,610 --> 00:02:09,400
Tātad, jūs nevarat īsti augt.

58
00:02:09,400 --> 00:02:13,510
Jūs varat pārdalīt lielāku rieciens
atmiņa, un pēc tam pārvietot vecās elementus

59
00:02:13,510 --> 00:02:14,460
jaunajā masīvs.

60
00:02:14,460 --> 00:02:18,060
Un tad bez vecā masīvs, lai
Piemēram, izmantojot malloc vai līdzīgu

61
00:02:18,060 --> 00:02:21,180
funkciju sauc realloc, kas
pārdalīt atmiņas.

62
00:02:21,180 --> 00:02:25,490
>> Realloc, kā malā, cenšas dot jums
atmiņa, kas ir blakus masīva

63
00:02:25,490 --> 00:02:26,610
kas jums jau ir.

64
00:02:26,610 --> 00:02:28,740
Bet tas varētu pārvietoties lietas
apkārt vispār.

65
00:02:28,740 --> 00:02:30,710
Bet sakot, tas ir dārgi, vai ne?

66
00:02:30,710 --> 00:02:33,440
Jo, ja jums ir rieciens atmiņas
šis lielums, bet jūs patiešām vēlaties vienu

67
00:02:33,440 --> 00:02:36,710
Šāda izmēra, un jūs vēlaties, lai saglabātu
sākotnējie elementi, jums ir

68
00:02:36,710 --> 00:02:40,510
aptuveni lineārā laika kopēšanas process
kas ir nepieciešams notikt no

69
00:02:40,510 --> 00:02:41,900
Vīrietis masīvu jaunu.

70
00:02:41,900 --> 00:02:44,630
Un realitāte ir jautā darbojas
sistēma atkal un atkal, un

71
00:02:44,630 --> 00:02:48,340
Vēlreiz liels gabalos atmiņas var sākt
izmaksas jums kādu laiku, kā arī.

72
00:02:48,340 --> 00:02:52,250
Tātad, tas ir gan svētība un lāsts, kas
noslēpt, ka šie bloki

73
00:02:52,250 --> 00:02:53,860
ir no noteikta lieluma.

74
00:02:53,860 --> 00:02:56,790
Bet, ja mēs ieviestu, nevis kaut ko
piemēram, tas, ko mēs saucām saistītais

75
00:02:56,790 --> 00:03:00,580
sarakstu, mēs iegūt dažas upsides un
daži downsides arī šeit.

76
00:03:00,580 --> 00:03:05,780
>> Tātad saistīts saraksts ir vienkārši dati
struktūra, kas sastāv no C structs jo šī

77
00:03:05,780 --> 00:03:09,850
gadījumā, ja struktūrai, atsaukšana, ir tikai
konteiners, lai viens vai vairāki specifiski

78
00:03:09,850 --> 00:03:11,100
veidu mainīgajiem lielumiem.

79
00:03:11,100 --> 00:03:16,110
Šajā gadījumā, ko darīt datu tipus
šķiet iekšpusē struktūrai, kas

80
00:03:16,110 --> 00:03:17,600
Pēdējo reizi mēs sauc par mezglu?

81
00:03:17,600 --> 00:03:19,380
Katrs no šiem taisnstūriem ir mezglā.

82
00:03:19,380 --> 00:03:22,660
Un katrs no mazajām taisnstūru
iekšpusē tā ir datu tips.

83
00:03:22,660 --> 00:03:25,300
Kādi bija mēs sakām
tie bija pirmdien?

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

85
00:03:26,478 --> 00:03:27,870
>> STUDENTU: [nedzirdama].

86
00:03:27,870 --> 00:03:30,721
>> SPEAKER 1: mainīga, un rādītājs, vai
precīzāk, int, lai n,

87
00:03:30,721 --> 00:03:32,180
un rādītājs apakšā.

88
00:03:32,180 --> 00:03:35,360
Abi no tiem gadās būt 32 biti, pēc
Vismaz uz datora, piemēram, CS50 šo

89
00:03:35,360 --> 00:03:37,980
Appliance, un lai viņi
sagatavots tikpat lieluma.

90
00:03:37,980 --> 00:03:42,260
>> Tātad, ko izmanto rādītāju
gan attiecībā uz šķietami?

91
00:03:42,260 --> 00:03:47,690
Kāpēc pievienot šīs bultiņas tagad, kad bloki bija
tik jauks un tīrs un vienkāršs?

92
00:03:47,690 --> 00:03:50,460
Kas ir rādītājs dara
mums ir katrs no šiem mezgliem?

93
00:03:50,460 --> 00:03:52,160
>> STUDENTU: [nedzirdama].

94
00:03:52,160 --> 00:03:52,465
>> SPEAKER 1: Tieši tā.

95
00:03:52,465 --> 00:03:54,120
Tā stāsta jums, kur
nākamā ir.

96
00:03:54,120 --> 00:03:57,350
Tāpēc es veida izmantot analoģiju
izmantojot diegu, lai kārtotu ar

97
00:03:57,350 --> 00:03:59,180
pavedienu šos mezglus kopā.

98
00:03:59,180 --> 00:04:01,760
Un tas ir tieši tas, ko mēs darām ar
norādes, jo katrs no tiem

99
00:04:01,760 --> 00:04:06,360
gabalos atmiņas var vai nevar būt
blakus, atpakaļ atpakaļ atpakaļ

100
00:04:06,360 --> 00:04:09,500
iekšpusē RAM, jo katru reizi, kad jūs
zvanu malloc sakot, man pietiek

101
00:04:09,500 --> 00:04:12,510
baiti jaunu mezglu, tas varētu
būt šeit, vai tas varētu būt šeit.

102
00:04:12,510 --> 00:04:13,120
Tas varētu būt šeit.

103
00:04:13,120 --> 00:04:13,730
Tas varētu būt šeit.

104
00:04:13,730 --> 00:04:14,640
Jūs vienkārši nezināt.

105
00:04:14,640 --> 00:04:17,880
>> Bet izmantojot norādes īpaši adresēm
šie mezgli, jūs varat šūt tos

106
00:04:17,880 --> 00:04:22,370
kopā tādā veidā, ka izskatās vizuāli
kā sarakstā, pat tad, ja šīs lietas ir

107
00:04:22,370 --> 00:04:26,770
visu izlīdzina visā jūsu vienu vai
Jūsu divi vai jūsu četru gigabaitu RAM

108
00:04:26,770 --> 00:04:28,760
iekšā savā datorā.

109
00:04:28,760 --> 00:04:33,230
>> Tātad negatīvie, tad,
saistīts saraksts ir tas, ko?

110
00:04:33,230 --> 00:04:34,670
Kāda ir cena, mēs esam
acīmredzot maksā?

111
00:04:34,670 --> 00:04:36,010
>> STUDENTU: [nedzirdama].

112
00:04:36,010 --> 00:04:36,920
>> SPEAKER 1: Vairāk vietas, vai ne?

113
00:04:36,920 --> 00:04:39,340
Mēs esam, šajā gadījumā, divas reizes summu
vietas, jo mēs esam izgājuši

114
00:04:39,340 --> 00:04:43,500
no 32 bitiem uz katru mezglu, par katru
int, tāpēc tagad 64 bitus, jo mums ir

115
00:04:43,500 --> 00:04:45,050
turēt ap rādītāju, kā arī.

116
00:04:45,050 --> 00:04:48,860
Jūs saņemsiet lielāku efektivitāti, ja jūsu struktūrai
ir lielāks nekā šo vienkāršo lietu.

117
00:04:48,860 --> 00:04:52,020
Ja jums tiešām ir students iekšā
no kuriem ir no virknes pāris par

118
00:04:52,020 --> 00:04:55,430
nosaukumu un māju, varbūt ID numurs,
varbūt dažas citas jomas vispār.

119
00:04:55,430 --> 00:04:59,000
>> Tātad, ja jums ir pietiekami liela struct,
tad varbūt par rādītāju izmaksas ir

120
00:04:59,000 --> 00:05:00,010
nav tik liels darījumu.

121
00:05:00,010 --> 00:05:03,570
Tas ir mazliet stūra gadījumā, ar to, ka
mēs esam uzglabātu tik vienkāršs primitīva

122
00:05:03,570 --> 00:05:04,760
iekšpusē saistītajā sarakstā.

123
00:05:04,760 --> 00:05:05,790
Bet punkts ir tas pats.

124
00:05:05,790 --> 00:05:08,230
Jūs esat noteikti tērēt vairāk
atmiņa, bet jūs saņemat

125
00:05:08,230 --> 00:05:08,990
elastību.

126
00:05:08,990 --> 00:05:12,280
Jo tagad, ja es gribu, lai pievienotu elementu
sākumā šī saraksta,

127
00:05:12,280 --> 00:05:14,340
Man ir piešķirt jaunu mezglu.

128
00:05:14,340 --> 00:05:17,180
Un man ir vienkārši atjaunināt tiem
bultas kaut kā, tikai pārvietojot

129
00:05:17,180 --> 00:05:17,980
dažas norādes apkārt.

130
00:05:17,980 --> 00:05:20,580
>> Ja es gribu, lai ievietotu kaut ko uz
vidū saraksta, man nav

131
00:05:20,580 --> 00:05:24,410
push visi malā tāpat kā mēs to darījām
nedēļu agrāk ar mūsu brīvprātīgajiem, kuri

132
00:05:24,410 --> 00:05:25,700
bija masīvs.

133
00:05:25,700 --> 00:05:29,470
Es varu tikai piešķirt jaunu mezglu un
tad vienkārši norādīt uz bultiņām

134
00:05:29,470 --> 00:05:32,290
dažādos virzienos, jo tas nav
ir jāpaliek faktisko

135
00:05:32,290 --> 00:05:35,670
atmiņas patiess līnija, piemēram, es esmu sastādīts
tā šeit uz ekrāna.

136
00:05:35,670 --> 00:05:38,400
>> Un tad visbeidzot, ja jūs vēlaties, lai ievietotu
kaut beigās saraksta, tas ir

137
00:05:38,400 --> 00:05:39,210
vēl vieglāk.

138
00:05:39,210 --> 00:05:43,320
Tas ir sava veida patvaļīgu apzīmējums,
bet 34 ir rādītājs, ņem minējums.

139
00:05:43,320 --> 00:05:46,710
Kāda ir tās rādītāju visvairāk vērtība
iespējams izdarīt veida, piemēram, veco

140
00:05:46,710 --> 00:05:47,700
skola antena tur?

141
00:05:47,700 --> 00:05:48,920
>> STUDENTU: [nedzirdama].

142
00:05:48,920 --> 00:05:49,900
>> SPEAKER 1: Tas ir iespējams, null.

143
00:05:49,900 --> 00:05:52,710
Un tiešām tas ir viens no autora
pārstāvību null.

144
00:05:52,710 --> 00:05:56,310
Un tas ir null, jo jūs absolūti
ir nepieciešams, lai zina, kur beigām linked

145
00:05:56,310 --> 00:06:00,050
saraksts ir, citādi jums saglabāt tekstu un
sekojot un ievērojot šos bultas

146
00:06:00,050 --> 00:06:01,170
uz kādu atkritumu vērtībai.

147
00:06:01,170 --> 00:06:06,230
Tātad null nozīmēs, ka tur nav
vairāk mezglus pa labi no 34 numuru,

148
00:06:06,230 --> 00:06:07,200
šajā gadījumā.

149
00:06:07,200 --> 00:06:10,270
>> Tāpēc mēs ierosinām, ka mēs varam īstenot
tas mezglu kodu.

150
00:06:10,270 --> 00:06:12,130
Un mēs esam redzējuši šāda veida
sintakses agrāk.

151
00:06:12,130 --> 00:06:15,090
Typedef tikai nosaka jaunu veidu
mums, dod mums sinonīmu, piemēram,

152
00:06:15,090 --> 00:06:17,100
string bija char *.

153
00:06:17,100 --> 00:06:21,030
Šajā gadījumā, tas notiek, lai dotu mums
saīsināts apzīmējums lai struct mezglā

154
00:06:21,030 --> 00:06:24,010
var nevis vienkārši rakstīts kā
mezgls, kas ir daudz tīrītājs.

155
00:06:24,010 --> 00:06:25,360
Tas ir daudz mazāk runīgs.

156
00:06:25,360 --> 00:06:30,080
>> Iekšpusē mezglā ir acīmredzami int
sauc n, un pēc tam struktūrai mezgls *

157
00:06:30,080 --> 00:06:34,670
kas nozīmē tieši to, ko mēs vēlējāmies
bultas nozīmē, rādītāju uz otru

158
00:06:34,670 --> 00:06:36,940
mezgla tieši tādu pašu datu tipu.

159
00:06:36,940 --> 00:06:40,300
Un es ierosinu, ka mēs varētu īstenot
meklēšanas funkciju, piemēram, tas, kas tajā

160
00:06:40,300 --> 00:06:41,890
pirmā acu uzmetiena varētu šķist
mazliet sarežģīta.

161
00:06:41,890 --> 00:06:43,330
Bet pieņemsim redzēt to kontekstā.

162
00:06:43,330 --> 00:06:45,480
>> Ļaujiet man iet vairāk nekā uz ierīci šeit.

163
00:06:45,480 --> 00:06:48,460
Ļaujiet man atvērt failu ar nosaukumu
Saraksts nulle dot st.

164
00:06:48,460 --> 00:06:53,950
Un tas ir tikai definīciju mēs
tikko redzēju pirms brīža šos datus

165
00:06:53,950 --> 00:06:55,390
veids, ko sauc par mezglu.

166
00:06:55,390 --> 00:06:57,350
Tāpēc mēs esam izveidojuši kas stājas dot h failā.

167
00:06:57,350 --> 00:07:01,430
>> Un kā malā, lai gan tas
programma, ka jūs gatavojaties redzēt, ir

168
00:07:01,430 --> 00:07:05,410
ne viss, kas sarežģīts, tas ir patiešām
konvencija, rakstot programmu, lai

169
00:07:05,410 --> 00:07:10,270
nodot lietas, piemēram, datu tipu, lai vilktu
konstantes reizēm, iekšpusē jūsu

170
00:07:10,270 --> 00:07:13,210
header failu un ne vienmēr
Jūsu C failu, protams, ja jūsu

171
00:07:13,210 --> 00:07:17,370
programmām iegūt lielāku un lielāku, lai
jūs zināt, kur meklēt gan

172
00:07:17,370 --> 00:07:20,840
dokumentācija, atsevišķos gadījumos, vai
attiecībā uz pamatiem, piemēram, tas, ka

173
00:07:20,840 --> 00:07:22,360
definīcija dažu tipu.

174
00:07:22,360 --> 00:07:25,680
>> Ja es tagad atvērt sarakstu nulle dot
c, ievērosiet dažas lietas.

175
00:07:25,680 --> 00:07:29,090
Tā ietver dažas header failus, lielākā daļa
par ko mēs esam redzējuši iepriekš.

176
00:07:29,090 --> 00:07:31,980
Tas ietver savu header failu.

177
00:07:31,980 --> 00:07:35,200
>> Un kā malā, tāpēc tas ir dubultā
citātus šeit, atšķirībā no leņķa

178
00:07:35,200 --> 00:07:38,340
iekavās uz līnijas, kas
Es esmu uzsvērusi tur?

179
00:07:38,340 --> 00:07:39,180
>> STUDENTU: [nedzirdama].

180
00:07:39,180 --> 00:07:40,460
>> SPEAKER 1: Jā, tā tas ir vietējais fails.

181
00:07:40,460 --> 00:07:44,300
Tātad, ja tas ir vietējais fails savu šeit
15 līnijas, piemēram, jūs izmantojat

182
00:07:44,300 --> 00:07:46,570
pēdiņas vietā
no leņķveida iekavās.

183
00:07:46,570 --> 00:07:48,270
>> Tagad tas ir diezgan interesants.

184
00:07:48,270 --> 00:07:51,830
Ievērojiet, ka es esmu atzīts pasaules
mainīgais šajā programmā 18 līnijas

185
00:07:51,830 --> 00:07:55,910
sauc pirmkārt, ideja ir, tas ir
būs rādītājs uz pirmo

186
00:07:55,910 --> 00:07:59,190
mezglu manā saistītajā sarakstā, un es esmu
inicializēts tai null, jo es esmu

187
00:07:59,190 --> 00:08:02,310
nav piešķirts faktiska
mezgli tikai yet.

188
00:08:02,310 --> 00:08:07,570
>> Tātad tas nozīmē, gleznieciski, ko mēs
redzēju pirms brīža attēlā kā

189
00:08:07,570 --> 00:08:10,090
ka rādītājs par tālu
Kreisajā pusē.

190
00:08:10,090 --> 00:08:12,260
Tāpēc tagad, ka rādītājs
nav bultiņu.

191
00:08:12,260 --> 00:08:14,590
Tā vietā ir tikai nulle.

192
00:08:14,590 --> 00:08:17,880
Bet tas ir to, kas būs
adrese Pirmajām

193
00:08:17,880 --> 00:08:19,480
mezglu šajā sarakstā.

194
00:08:19,480 --> 00:08:22,120
Tāpēc es esmu īstenota tā ir globāla
jo, kā jūs redzēsiet, tas viss

195
00:08:22,120 --> 00:08:25,310
Programmā nav dzīvē ir jāīsteno
saistīts saraksts par mani.

196
00:08:25,310 --> 00:08:27,050
>> Tagad es esam ieguvuši dažas prototipus šeit.

197
00:08:27,050 --> 00:08:31,190
Es nolēmu, lai īstenotu funkcijas, piemēram,
dzēšanu, ievietošanas, meklējot, un

198
00:08:31,190 --> 00:08:31,740
šķērsošana -

199
00:08:31,740 --> 00:08:35,210
pēdējais vienkārši ir staigāt pāri
sarakstā, izdrukāt savus elementus.

200
00:08:35,210 --> 00:08:36,750
Un tagad šeit ir mans galvenais rutīnas.

201
00:08:36,750 --> 00:08:39,890
Un mēs ne tērēt pārāk daudz laika
šiem, jo ​​tas ir sava veida, cerams

202
00:08:39,890 --> 00:08:41,780
veco cepuri, ko tagad.

203
00:08:41,780 --> 00:08:45,370
>> Es esmu gatavojas veikt šādas darbības,
kamēr lietotājs sadarbojas.

204
00:08:45,370 --> 00:08:47,300
Tātad viena, es esmu gatavojas drukāt
veic šo izvēlni.

205
00:08:47,300 --> 00:08:49,420
Un es esmu formatēti to kā
tīri kā es varētu.

206
00:08:49,420 --> 00:08:52,240
Ja lietotājs vienā, tas nozīmē, ka
viņi vēlas, lai izdzēstu kaut ko.

207
00:08:52,240 --> 00:08:54,560
Ja lietotājs veidu divi, tas nozīmē, ka
viņi vēlas, lai ievietotu kaut ko.

208
00:08:54,560 --> 00:08:55,930
Un tā tālāk.

209
00:08:55,930 --> 00:08:58,270
Es esmu gatavojas, lai pēc tam ātri
tad uz komandu.

210
00:08:58,270 --> 00:08:59,300
Un tad es esmu gatavojas izmantot GetInt.

211
00:08:59,300 --> 00:09:02,790
>> Tātad tas ir ļoti vienkāršs menuing
interfeisu, kur jūs vienkārši ir veids

212
00:09:02,790 --> 00:09:05,270
numurs kartēšanas uz vienu
no šīm komandām.

213
00:09:05,270 --> 00:09:08,730
Un tagad man ir jauka tīru slēdzi
paziņojumu, kas notiek, lai ieslēgtu

214
00:09:08,730 --> 00:09:10,090
kāds lietotājs drukāti collas

215
00:09:10,090 --> 00:09:12,180
Un, ja tie drukāti vienu, es ņemšu
zvanu dzēst un pauze.

216
00:09:12,180 --> 00:09:14,380
Ja tie drukāti divi, es ņemšu
zvanu ievietot un lauzt.

217
00:09:14,380 --> 00:09:16,490
>> Un tagad novērojat es esmu likts katrā
no tiem uz vienas līnijas.

218
00:09:16,490 --> 00:09:18,360
Tas ir tikai stilistiskās lēmums.

219
00:09:18,360 --> 00:09:20,210
Parasti mēs esam redzējuši kaut ko
kā šis.

220
00:09:20,210 --> 00:09:23,260
Bet es tikko nolēma, atklāti sakot, mana programma
izskatījās vairāk lasāms, jo

221
00:09:23,260 --> 00:09:25,980
tas bija tikai četri gadījumi,
tikai sarakstu to, kā šis.

222
00:09:25,980 --> 00:09:28,360
Pilnīgi likumīgu izmantošanu stilu.

223
00:09:28,360 --> 00:09:31,480
Un es esmu gatavojas darīt to tik ilgi, kamēr
lietotājs nav ievadījis nulli, ko es

224
00:09:31,480 --> 00:09:33,910
nolēma nozīmēs viņi vēlas atmest.

225
00:09:33,910 --> 00:09:36,630
>> Tāpēc tagad paziņojums, ko es esmu
gatavojas darīt šeit.

226
00:09:36,630 --> 00:09:38,650
Es esmu gatavojas, lai atbrīvotu sarakstu acīmredzot.

227
00:09:38,650 --> 00:09:40,230
Bet vairāk par to tikai brīdi.

228
00:09:40,230 --> 00:09:41,640
Pieņemsim vispirms palaist šo programmu.

229
00:09:41,640 --> 00:09:45,250
Tātad, ļaujiet man sniegt lielāku termināli
logu, dot slash sarakstu 0.

230
00:09:45,250 --> 00:09:49,510
Es iešu uz priekšu un ievietojiet ar
ierakstot divi, skaitlis, piemēram, 50, un tagad

231
00:09:49,510 --> 00:09:51,590
jūs redzēsiet saraksts tagad ir 50.

232
00:09:51,590 --> 00:09:53,380
Un mans teksts vienkārši ritinot uz augšu mazliet.

233
00:09:53,380 --> 00:09:55,940
Tāpēc tagad paziņojums sarakstā ir
numuru 50.

234
00:09:55,940 --> 00:09:58,220
>> Darīsim citas ieliktni, veicot divus.

235
00:09:58,220 --> 00:10:01,630
Let 's tipa numuru, piemēram, vienu.

236
00:10:01,630 --> 00:10:03,940
Saraksts ir tagad viens, kam seko 50.

237
00:10:03,940 --> 00:10:06,020
Tātad tas ir tikai tekstuālu pārstāvība
no saraksta.

238
00:10:06,020 --> 00:10:10,550
Un pieņemsim ievietot vēl vienu numuru, piemēram,
skaitlis 42, kas ir cerams

239
00:10:10,550 --> 00:10:14,620
gatavojas galu galā vidū, jo
šī programma jo īpaši veidu tā

240
00:10:14,620 --> 00:10:16,320
elementus kā tas ievieto tos.

241
00:10:16,320 --> 00:10:17,220
Tātad mums ir tā.

242
00:10:17,220 --> 00:10:20,730
Super vienkārša programma, kas varētu
absolūti ir izmantots masīvu, bet es

243
00:10:20,730 --> 00:10:23,280
gadās būt, izmantojot saistītu sarakstu
tikai, lai es varētu dinamiski

244
00:10:23,280 --> 00:10:24,610
augt un sarauties to.

245
00:10:24,610 --> 00:10:28,470
>> Tātad, pieņemsim to apskatīt meklēšanas, ja es
palaist komandu trīs, es gribu, lai meklētu

246
00:10:28,470 --> 00:10:31,040
, teiksim, uz numuru 43.

247
00:10:31,040 --> 00:10:34,190
Un nekas netika acīmredzot atrasts,
tāpēc, ka es saņēmu atpakaļ nekādu atbildi.

248
00:10:34,190 --> 00:10:35,010
Tātad, pieņemsim darīt atkal.

249
00:10:35,010 --> 00:10:35,690
Meklēt.

250
00:10:35,690 --> 00:10:39,520
Pieņemsim meklēt 50, vai drīzāk meklēt
par 42, kas ir patīkami

251
00:10:39,520 --> 00:10:40,850
maz smalks nozīme.

252
00:10:40,850 --> 00:10:42,610
Un es atklāju dzīves jēgu tur.

253
00:10:42,610 --> 00:10:44,990
Numuru 42, ja jūs nezināt,
atsauces, Google to.

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

255
00:10:45,350 --> 00:10:47,130
Tātad, kādi ir šo programmu darīts attiecībā uz mani?

256
00:10:47,130 --> 00:10:50,660
Tas ir tikai ļāva man, lai ievietotu tādējādi
tālu un meklēt elementiem.

257
00:10:50,660 --> 00:10:53,650
>> Pieņemsim ātri uz priekšu, tad, lai
ka funkcija mēs paskatījās

258
00:10:53,650 --> 00:10:55,360
pirmdien kā teaser.

259
00:10:55,360 --> 00:10:59,620
Tātad šo funkciju, es apgalvot, meklē
elements sarakstā ar pirmo

260
00:10:59,620 --> 00:11:03,830
viens, pamudinot lietotājam, un tad zvana
GetInt iegūt faktisko int

261
00:11:03,830 --> 00:11:05,060
ka jūs vēlaties meklēt.

262
00:11:05,060 --> 00:11:06,460
>> Tad paziņojums šo.

263
00:11:06,460 --> 00:11:10,690
Es esmu gatavojas izveidot pagaidu mainīgo
188 rindā sauc rādītājs -

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

265
00:11:11,270 --> 00:11:12,440
varēja saukt tā neko.

266
00:11:12,440 --> 00:11:16,140
Un tas ir rādītājs, lai mezglu
tāpēc es teicu mezglā * tur.

267
00:11:16,140 --> 00:11:19,900
Un es esmu inicializēšana, ka tas ir vienāds ar
Pirmais tāpēc, ka man faktiski ir mana

268
00:11:19,900 --> 00:11:22,860
pirkstu, tā sakot, par ļoti
pirmais elements no saraksta.

269
00:11:22,860 --> 00:11:27,460
Tātad, ja mana labā roka šeit ir PTR es esmu
norāda uz vienu un to pašu, kas pirmo reizi

270
00:11:27,460 --> 00:11:28,670
ir vērsta uz.

271
00:11:28,670 --> 00:11:31,430
>> Tāpēc tagad atkal kodu,
kas notiek tālāk -

272
00:11:31,430 --> 00:11:35,070
tas ir kopīgs paradigma, kad atkārtojot
pār struktūru, piemēram,

273
00:11:35,070 --> 00:11:35,970
saistīts saraksts.

274
00:11:35,970 --> 00:11:40,410
Es esmu gatavojas veikt šādas darbības, kamēr
rādītājs nav vienāds ar null Tāpēc, kamēr

275
00:11:40,410 --> 00:11:47,530
mans pirksts nav vērsta uz kādu null
vērtība, ja rādītājs bultiņa n ir vienāds ar n.

276
00:11:47,530 --> 00:11:52,290
Mēs ievērosiet, ka, pirmkārt, n ir tas, ko
lietotājs drukāti uz GetInts zvanu šeit.

277
00:11:52,290 --> 00:11:54,280
>> Un rādītājs arrow n nozīmē ko?

278
00:11:54,280 --> 00:11:59,020
Nu, ja mēs ejam atpakaļ uz attēlu šeit,
ja man ir pirkstu norādot uz

279
00:11:59,020 --> 00:12:02,960
ka pirmais mezgls, kurā deviņi, to
arrow būtībā nozīmē iet, ka

280
00:12:02,960 --> 00:12:08,860
mezglu un paķert vērtību atrašanās n,
Šajā gadījumā, datu lauks sauc n.

281
00:12:08,860 --> 00:12:14,120
>> Kā malā - un mēs redzējām šo pāris
nedēļas atpakaļ, kad kāds jautāja -

282
00:12:14,120 --> 00:12:18,840
Šī sintakse ir jauns, bet tas nav
dod mums pilnvaras, kas mums

283
00:12:18,840 --> 00:12:20,040
nebija jau ir.

284
00:12:20,040 --> 00:12:25,325
Kāda bija šī frāze līdzvērtīgs izmantojot
dot nošu un zvaigžņu pāris

285
00:12:25,325 --> 00:12:29,490
nedēļas atpakaļ, kad mēs mizoti atpakaļ
šis slānis mazliet priekšlaicīgi?

286
00:12:29,490 --> 00:12:31,780
>> STUDENTU: [nedzirdama].

287
00:12:31,780 --> 00:12:38,880
>> SPEAKER 1: Tieši tā, tas bija zvaigzne, un
tad tas bija star dot n, ar

288
00:12:38,880 --> 00:12:41,930
iekavas šeit, kas izskatās,
godīgi sakot, es domāju, ka daudz

289
00:12:41,930 --> 00:12:43,320
vairāk noslēpumains, lai lasītu.

290
00:12:43,320 --> 00:12:46,270
Bet zvaigzne rādītājs, kā vienmēr,
nozīmē iet uz turieni.

291
00:12:46,270 --> 00:12:49,090
Un, kad jūs esat tur, kādi dati
lauka jūs vēlaties piekļūt?

292
00:12:49,090 --> 00:12:52,730
Nu jūs izmantojat dot apzīmējumu, lai piekļūtu
structs datu lauks, un es

293
00:12:52,730 --> 00:12:54,140
īpaši vēlas n.

294
00:12:54,140 --> 00:12:56,240
>> Atklāti sakot, es teiktu, tas
ir tikai grūtāk lasīt.

295
00:12:56,240 --> 00:12:58,080
Tas ir grūtāk atcerēties, kur
Vai iekavas iet,

296
00:12:58,080 --> 00:12:59,030
zvaigzne, un visu to.

297
00:12:59,030 --> 00:13:02,150
Tātad pasaule pieņēma dažus sintaktisko
cukurs, lai runāt.

298
00:13:02,150 --> 00:13:04,740
Tikai sexy veids, kā pateikt,
tas ir ekvivalents, un

299
00:13:04,740 --> 00:13:05,970
iespējams, vairāk intuitīvi.

300
00:13:05,970 --> 00:13:09,600
Ja rādītājs ir patiešām rādītājs,
arrow notācija nozīmē iet tur un atrast

301
00:13:09,600 --> 00:13:11,890
Šajā gadījumā lauks sauc n.

302
00:13:11,890 --> 00:13:13,660
>> Tātad, ja man šķiet, pamanīt to, ko es daru.

303
00:13:13,660 --> 00:13:17,430
Es vienkārši izdrukāt, es atklāju procentiem I,
tapām vērtību šajā int.

304
00:13:17,430 --> 00:13:20,730
Es aicinu gulēt vienu sekundi tikai natūrā
gada pauzes lietas uz ekrāna, lai

305
00:13:20,730 --> 00:13:22,900
dod lietotājam otrs, lai absorbētu
kas tikko notika.

306
00:13:22,900 --> 00:13:24,290
Un tad es pārkāpšu.

307
00:13:24,290 --> 00:13:26,330
Pretējā gadījumā, ko man darīt?

308
00:13:26,330 --> 00:13:30,960
Es atjaunināt rādītāju uz vienlīdzīgu
rādītāju bultiņas blakus.

309
00:13:30,960 --> 00:13:35,840
>> Tik vienkārši, lai būtu skaidrs, tas nozīmē iet
tur, izmantojot manu old-school notācija.

310
00:13:35,840 --> 00:13:39,580
Tātad tas nozīmē tikai doties uz whatever
jūs norādot uz, kas ir ļoti

311
00:13:39,580 --> 00:13:43,660
Pirmā lieta ir tā, es esmu norādot uz
struktūrai ar deviņiem tajā.

312
00:13:43,660 --> 00:13:44,510
Tāpēc es esmu gājusi tur.

313
00:13:44,510 --> 00:13:47,880
Un tad dot pieraksts nozīmē,
saņemt vērtību nākamo.

314
00:13:47,880 --> 00:13:50,470
>> Bet vērtība, pat ja tas ir sastādīts
kā šaurs, ir tikai skaitlis.

315
00:13:50,470 --> 00:13:51,720
Tas ir ciparu adrese.

316
00:13:51,720 --> 00:13:55,670
Tāpēc šī līnija kods, vai
rakstīts, piemēram, tas, vairāk mistisks

317
00:13:55,670 --> 00:14:00,190
veidā, vai, piemēram, tas, nedaudz
intuitīvā veidā, vienkārši nozīmē pārvietot manu roku

318
00:14:00,190 --> 00:14:03,460
no pirmā mezgla uz nākamo,
un pēc tam blakus viens, un pēc tam

319
00:14:03,460 --> 00:14:05,320
Nākamais vienu, un tā tālāk.

320
00:14:05,320 --> 00:14:09,920
>> Tāpēc mēs ne aiztures par otru
implementācijas ievietot un dzēst

321
00:14:09,920 --> 00:14:14,030
un šķērsošana, pirmais divi no
, kas ir diezgan iesaistīti.

322
00:14:14,030 --> 00:14:17,010
Un es domāju, ka tas ir diezgan viegli nokļūt
zaudētas, kad to dara mutiski.

323
00:14:17,010 --> 00:14:19,890
Bet ko mēs varam darīt, šeit ir
mēģināt noteikt, kā

324
00:14:19,890 --> 00:14:21,640
vislabāk to darīt vizuāli.

325
00:14:21,640 --> 00:14:24,800
Tā kā es ierosinu, ka, ja mēs
vēlaties ievietot elementus šajā

326
00:14:24,800 --> 00:14:26,680
esošais saraksts, kurā
ir pieci elementi -

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

328
00:14:29,530 --> 00:14:33,300
ja man bija gatavojas, lai īstenotu šo
kods, man ir nepieciešams apsvērt, kā iet

329
00:14:33,300 --> 00:14:34,160
par to izdarīt.

330
00:14:34,160 --> 00:14:37,720
>> Un es ierosinu veikt bērnu pasākumus
, saskaņā ar kuru, šajā gadījumā es domāju, kas ir

331
00:14:37,720 --> 00:14:41,090
iespējamos scenārijus, kas mums
varētu rasties kopumā?

332
00:14:41,090 --> 00:14:44,120
Īstenojot ieliktni, lai saistītu
sarakstā, tas vienkārši notiek, ir

333
00:14:44,120 --> 00:14:46,090
Konkrēts piemērs piecu izmēru.

334
00:14:46,090 --> 00:14:50,420
Nu, ja jūs vēlaties, lai ievietotu numuru,
gribētu teikt, ka numur viens, un

335
00:14:50,420 --> 00:14:53,380
uzturot sakārtoti secībā, kur
acīmredzot nav numur viens ir nepieciešams, lai

336
00:14:53,380 --> 00:14:55,686
iet šajā konkrētajā piemērā?

337
00:14:55,686 --> 00:14:56,840
Tāpat kā gada sākumā.

338
00:14:56,840 --> 00:15:00,030
>> Bet kas ir interesanti ir tas, ka
Ja vēlaties ievietot vienu uz to

339
00:15:00,030 --> 00:15:04,100
sarakstā, ko īpaša rādītājs vajadzībām
jāatjaunina acīmredzami?

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

341
00:15:04,610 --> 00:15:07,830
Tāpēc es teiktu, šis ir pirmais gadījums
ka mēs varētu vēlēties apsvērt,

342
00:15:07,830 --> 00:15:11,140
scenārijs ietver ievietojot tajā
sākums sarakstā.

343
00:15:11,140 --> 00:15:15,400
>> Let 's nošķīt varbūt tik viegli vai pat
vieglāka gadījumā, relatīvi runājot.

344
00:15:15,400 --> 00:15:18,110
Pieņemsim, ka es gribu, lai ievietotu
ir sakārtoti secībā 35 numuru.

345
00:15:18,110 --> 00:15:20,600
Tas, protams, pieder tur.

346
00:15:20,600 --> 00:15:25,320
Tātad, kādi rādītājs acīmredzot gatavojas
ir jāatjaunina šajā scenārijā?

347
00:15:25,320 --> 00:15:30,060
34 ir rādītājs kļūst ne null
bet adrese struktūrai

348
00:15:30,060 --> 00:15:31,800
, kas satur skaitli 35.

349
00:15:31,800 --> 00:15:32,750
Tātad, tas ir gadījums divi.

350
00:15:32,750 --> 00:15:36,190
Tāpēc jau es esmu veida quantizing
cik daudz darba, man ir jādara šeit.

351
00:15:36,190 --> 00:15:39,880
>> Un, visbeidzot, skaidrs vidū lieta ir
protams, pa vidu, ja es gribu

352
00:15:39,880 --> 00:15:45,870
ievietot kaut ko līdzīgu 23 teiksim, kas iet
starp 23 un 26, bet

353
00:15:45,870 --> 00:15:48,680
Tagad lietas iegūt nedaudz vairāk
iesaistīti, jo to, ko

354
00:15:48,680 --> 00:15:52,800
norādes ir jāmaina?

355
00:15:52,800 --> 00:15:56,680
Tātad 22 acīmredzot ir jāmaina
tāpēc, ka viņš nevar norādīt uz 26 vairs.

356
00:15:56,680 --> 00:16:00,320
Viņam vajag, lai norādītu uz jaunu mezglu, kas
Es ņemšu, lai sadalītu pa tālruni

357
00:16:00,320 --> 00:16:01,770
malloc vai kādu līdzvērtīgu.

358
00:16:01,770 --> 00:16:05,990
>> Bet tad es arī nepieciešams, ka jaunu mezglu, 23
Šajā gadījumā, lai tās rādītājs

359
00:16:05,990 --> 00:16:07,870
norādot uz kuriem?

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

361
00:16:08,560 --> 00:16:10,380
Un tur būs
Lai darbību šeit.

362
00:16:10,380 --> 00:16:13,410
Jo ja es to muļķīgi, un es
, piemēram, sākuma sākumā

363
00:16:13,410 --> 00:16:16,040
sarakstu, un mans mērķis ir, lai ievietotu 23.

364
00:16:16,040 --> 00:16:18,610
Un es varētu pārbaudīt, vai tas pieder
Šeit, netālu no deviņiem?

365
00:16:18,610 --> 00:16:18,950
Nē.

366
00:16:18,950 --> 00:16:20,670
Vai tas pieder šeit, pie 17?

367
00:16:20,670 --> 00:16:20,940
Nē.

368
00:16:20,940 --> 00:16:22,530
Vai tas pieder šeit, pie 22?

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

370
00:16:23,300 --> 00:16:26,400
>> Tagad, ja es esmu muļķīgi šeit, un ne
domāšana tas cauri, es varētu

371
00:16:26,400 --> 00:16:28,320
piešķirt savu jauno mezglu 23.

372
00:16:28,320 --> 00:16:32,080
Es varētu atjaunināt rādītāju no
mezglu sauc 22, norādot

373
00:16:32,080 --> 00:16:33,080
tas pie jaunu mezglu.

374
00:16:33,080 --> 00:16:36,140
Un tad ko man ir, lai atjauninātu
jaunā mezgla rādītājs būt?

375
00:16:36,140 --> 00:16:38,120
>> STUDENTU: [nedzirdama].

376
00:16:38,120 --> 00:16:38,385
>> SPEAKER 1: Tieši tā.

377
00:16:38,385 --> 00:16:39,710
Norādot uz 26.

378
00:16:39,710 --> 00:16:45,590
Bet, dammit, ja man nav jau atjaunināt
22 ir rādītājs norādīt uz šo puisis, un

379
00:16:45,590 --> 00:16:48,260
tagad man ir bāreņi, atpūtas
saraksta, lai runāt.

380
00:16:48,260 --> 00:16:52,140
Tātad, lai darbību šeit
būs svarīgi.

381
00:16:52,140 --> 00:16:55,100
>> Lai to izdarītu es varētu nozagt,
teiksim, seši brīvprātīgie.

382
00:16:55,100 --> 00:16:57,650
Un pieņemsim redzēt, ja mēs nevaram izdarīt
vizuāli nevis koda gudrs.

383
00:16:57,650 --> 00:16:59,330
Un mums ir daži jauki stress
bumbas jums šodien.

384
00:16:59,330 --> 00:17:02,510
OK, kā apmēram viens, divi, jo
atpakaļ - uz beigām tur.

385
00:17:02,510 --> 00:17:04,530
trīs, četri, jums abiem
puiši uz gada beigām.

386
00:17:04,530 --> 00:17:05,579
Un pieciem, sešiem.

387
00:17:05,579 --> 00:17:05,839
Pārliecināts.

388
00:17:05,839 --> 00:17:06,450
Piecus un sešus.

389
00:17:06,450 --> 00:17:08,390
Visas tiesības, un mēs nāksim
jums puiši nākamreiz.

390
00:17:08,390 --> 00:17:09,640
Labi, come on augšu.

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

392
00:17:12,010 --> 00:17:14,819
>> Labi, jo jūs esat šeit pirmo reizi,
Jūs vēlētos, lai būtu viens neveikli

393
00:17:14,819 --> 00:17:16,119
Google Glass šeit?

394
00:17:16,119 --> 00:17:19,075
Labi, jā, OK, stikla,
ierakstītu video.

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

396
00:17:22,720 --> 00:17:24,589
Labi, jūs esat labi iet.

397
00:17:24,589 --> 00:17:27,950
>> Visas tiesības, tādēļ, ja jūs guys var nākt pāri
šeit, es esmu gatava iepriekš

398
00:17:27,950 --> 00:17:30,110
daži skaitļi.

399
00:17:30,110 --> 00:17:31,240
Visas tiesības, nāk vairāk nekā šeit.

400
00:17:31,240 --> 00:17:33,440
Un kāpēc nav jums iet mazliet
turklāt šādā veidā.

401
00:17:33,440 --> 00:17:35,520
Un redzēsim, kāds ir tavs vārds,
ar Google Glass?

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

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

404
00:17:36,230 --> 00:17:38,380
Labi, Ben, jums būs, pirmkārt, burtiski.

405
00:17:38,380 --> 00:17:40,580
Tāpēc mēs esam gatavojas nosūtīt jums
līdz beigām posmā.

406
00:17:40,580 --> 00:17:41,670
Visas tiesības, un jūsu vārds?

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

408
00:17:41,990 --> 00:17:44,530
>> 1 SPEAKER: Jason, OK jūs
būtu numur deviņi.

409
00:17:44,530 --> 00:17:46,700
Tātad, ja jūs vēlaties sekot Ben, ka veidā.

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

411
00:17:47,010 --> 00:17:49,630
>> SPEAKER 1: Jill, jūs esat būs
17, kas, ja es gribētu darīt šo vairāk

412
00:17:49,630 --> 00:17:51,260
gudri, es būtu
sākās pie otrā galā.

413
00:17:51,260 --> 00:17:52,370
Jums iet šo ceļu.

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

415
00:17:53,030 --> 00:17:53,670
Un jūs esat?

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

417
00:17:53,980 --> 00:17:56,130
>> SPEAKER 1: Marija, jums būs 22.

418
00:17:56,130 --> 00:17:58,420
Un jūsu vārds ir?

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

420
00:17:58,810 --> 00:18:00,100
>> 1 SPEAKER: Chris, jums būs 26.

421
00:18:00,100 --> 00:18:00,740
Un tad visbeidzot.

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

423
00:18:01,400 --> 00:18:02,670
>> 1 SPEAKER: Diana, jums būs 34.

424
00:18:02,670 --> 00:18:03,920
Tātad jums nāk vairāk nekā šeit.

425
00:18:03,920 --> 00:18:06,360
>> Visas tiesības, tik perfekts sakārtoti
pasūtīt jau.

426
00:18:06,360 --> 00:18:09,600
Un iesim uz priekšu un darīt to
lai mēs varētu tiešām -

427
00:18:09,600 --> 00:18:11,720
Ben jūs vienkārši veida meklē
ārā nekur tur.

428
00:18:11,720 --> 00:18:15,670
Labi, tāpēc iesim uz priekšu un attēlot šo
izmantojot rokas, līdzīgi man bija, tieši tā,

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

430
00:18:16,250 --> 00:18:19,540
Tik iet uz priekšu un dot sev
pēdu vai starp sevi divi.

431
00:18:19,540 --> 00:18:22,900
Un iet uz priekšu, un norādīt ar vienu roku
Kurš jums būtu vērsti

432
00:18:22,900 --> 00:18:23,470
pamatojoties uz šo.

433
00:18:23,470 --> 00:18:25,890
Un, ja jūs esat null tikai punkts
taisni uz leju uz grīdas.

434
00:18:25,890 --> 00:18:27,690
Labi, tik labi.

435
00:18:27,690 --> 00:18:32,290
>> Tāpēc tagad mums ir saistīts saraksts, un ļaujiet man
ierosina, ka es spēlēt lomu

436
00:18:32,290 --> 00:18:35,110
PTR, tāpēc es ne apnikt
veicot šo apkārt.

437
00:18:35,110 --> 00:18:37,830
Un tad - kāds stulbi konvencija -
Jūs varat zvanīt šo kaut ko vēlaties -

438
00:18:37,830 --> 00:18:39,800
priekšgājējs rādītājs, ieteik rādītājs -

439
00:18:39,800 --> 00:18:43,930
tas ir tikai segvārds mums padevās
mūsu parauga kodu uz manu kreiso roku.

440
00:18:43,930 --> 00:18:47,240
No otras puses, kas būs tur
līdzi, kas ir kas

441
00:18:47,240 --> 00:18:48,400
pēc scenārijus.

442
00:18:48,400 --> 00:18:52,390
>> Tātad pieņemsim, ka, pirmkārt, es vēlos nošķīt
ka pirmais piemērs ievietojot, teiksim

443
00:18:52,390 --> 00:18:54,330
20, uz sarakstu.

444
00:18:54,330 --> 00:18:57,160
Tāpēc es esmu gatavojas ir nepieciešams kāds, lai
iemieso numuru 20 uz mums.

445
00:18:57,160 --> 00:18:58,950
Tāpēc man ir nepieciešams malloc kādam
no auditorijas.

446
00:18:58,950 --> 00:18:59,380
Nāciet uz augšu.

447
00:18:59,380 --> 00:19:00,340
Kāds ir Jūsu vārds?

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

449
00:19:01,300 --> 00:19:05,270
>> SPEAKER 1: Brian, labi, lai jūs
ir mezgls, kas satur 20.

450
00:19:05,270 --> 00:19:06,810
Visas tiesības, nāk vairāk nekā šeit.

451
00:19:06,810 --> 00:19:10,025
Un, protams, ja
tas Brian pieder?

452
00:19:10,025 --> 00:19:12,190
Tātad, pa vidu - faktiski,
pagaidiet minūti.

453
00:19:12,190 --> 00:19:13,420
Mēs darām to iziet no ierindas.

454
00:19:13,420 --> 00:19:17,170
Mēs esam padarot šo daudz grūtāk
, nekā tai vajadzētu būt sākumā.

455
00:19:17,170 --> 00:19:21,210
Labi, mēs ejam uz brīvu Brian
un realloc Brian kā pieci.

456
00:19:21,210 --> 00:19:23,680
>> Labi, tāpēc tagad mēs vēlamies, lai ievietotu
Brian kā pieci.

457
00:19:23,680 --> 00:19:25,960
Lai nāk vairāk nekā šeit pie
Ben tikai brīdi.

458
00:19:25,960 --> 00:19:28,250
Un jūs varat iespējams pateikt
ja šis stāsts turpinās.

459
00:19:28,250 --> 00:19:30,500
Bet pieņemsim rūpīgi apdomāt
rīkojums darbību.

460
00:19:30,500 --> 00:19:32,880
Un tas ir tieši tas vizuāli
kas notiek, lai rindā

461
00:19:32,880 --> 00:19:34,080
ar šo parauga kodu.

462
00:19:34,080 --> 00:19:40,120
Tātad, šeit es esmu PTR norādot sākotnēji
nav Ben, per se, bet neatkarīgi

463
00:19:40,120 --> 00:19:43,245
augstu viņš ir, kas šajā gadījumā
ir - kāda ir Jūsu vārds atkal?

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

465
00:19:43,670 --> 00:19:47,350
>> 1 SPEAKER: Jason, lai gan Ben, un es esam
norādot uz Jason šajā brīdī.

466
00:19:47,350 --> 00:19:49,700
Tāpēc tagad man ir, lai noteiktu,
ja nav Brian pieder?

467
00:19:49,700 --> 00:19:53,500
Tātad vienīgā lieta, man ir pieeja
tagad ir viņa n datu postenis.

468
00:19:53,500 --> 00:19:58,280
Tāpēc es esmu gatavojas, lai pārbaudītu, ir
Brian mazāk nekā Jason?

469
00:19:58,280 --> 00:19:59,770
Atbilde ir taisnība.

470
00:19:59,770 --> 00:20:03,680
>> Tā, kādi tagad ir nepieciešams notikt,
pareizā secībā?

471
00:20:03,680 --> 00:20:07,120
Man vajag, lai atjauninātu cik norādes
kopumā šajā stāstā?

472
00:20:07,120 --> 00:20:10,720
Kur mana roka joprojām norādot uz
Jason, un jūsu rokas - ja vēlaties

473
00:20:10,720 --> 00:20:12,930
nodot savu roku, piemēram, sava veida, es
nezinu, jautājuma zīmi.

474
00:20:12,930 --> 00:20:14,070
Labi, labi.

475
00:20:14,070 --> 00:20:15,670
>> Labi, tāpēc jums ir
daži kandidāti.

476
00:20:15,670 --> 00:20:20,500
Nu Ben, vai es, vai Brian vai Jason
vai ikviens cits, kas

477
00:20:20,500 --> 00:20:21,370
norādes nepieciešams mainīt?

478
00:20:21,370 --> 00:20:23,260
Cik kopumā?

479
00:20:23,260 --> 00:20:24,080
>> Labi, tāpēc divi.

480
00:20:24,080 --> 00:20:27,090
Mans rādītājs nav īsti jautājums vairs
jo es esmu tikai īslaicīga.

481
00:20:27,090 --> 00:20:31,370
Tātad, tas ir šie divi puiši, iespējams,
gan Ben un Brian.

482
00:20:31,370 --> 00:20:34,410
Tātad, ļaujiet man ieteikt, ka mēs atjaunināt
Ben, jo viņš ir pirmais.

483
00:20:34,410 --> 00:20:36,350
Pirmais elements no šī saraksta
tagad būs Brian.

484
00:20:36,350 --> 00:20:38,070
Tātad Ben punkts, Brian.

485
00:20:38,070 --> 00:20:39,320
Labi, tagad ko?

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

487
00:20:41,950 --> 00:20:43,460
>> Kurš izpaužas norādīja kam?

488
00:20:43,460 --> 00:20:44,710
>> STUDENTU: [nedzirdama].

489
00:20:44,710 --> 00:20:46,180
>> SPEAKER 1: Labi, tāpēc Brian ir
norādīt uz Jason.

490
00:20:46,180 --> 00:20:48,360
Bet es esmu zaudējis dziesmu no šīs rādītājs?

491
00:20:48,360 --> 00:20:49,980
Vai es zinu, kur Jason ir?

492
00:20:49,980 --> 00:20:50,790
>> STUDENTU: [nedzirdama].

493
00:20:50,790 --> 00:20:52,620
>> SPEAKER 1: man, jo es esmu
pagaidu rādītājs.

494
00:20:52,620 --> 00:20:55,110
Un, iespējams, man nav mainījies
norādīt uz jaunu mezglu.

495
00:20:55,110 --> 00:20:58,300
Tātad, mēs varam vienkārši ir Brian punkts
pie tam, kurš es esmu norādot uz.

496
00:20:58,300 --> 00:20:59,000
Un mēs esam darīts.

497
00:20:59,000 --> 00:21:01,890
Tātad, viens gadījums, ievietošanas pie
sākumā sarakstā.

498
00:21:01,890 --> 00:21:02,950
Tur bija divi galvenie pasākumi.

499
00:21:02,950 --> 00:21:06,750
Viens, mums ir, lai atjauninātu ben, un pēc tam
mums ir arī atjaunināt Brian.

500
00:21:06,750 --> 00:21:09,230
Un tad man nav jāuztraucas
traipsing visā pārējā

501
00:21:09,230 --> 00:21:12,680
sarakstā, jo mēs jau atrasts viņa
vieta, jo viņš piederēja

502
00:21:12,680 --> 00:21:14,080
pa kreisi no pirmā elementa.

503
00:21:14,080 --> 00:21:15,400
>> Labi, tāpēc diezgan vienkārši.

504
00:21:15,400 --> 00:21:18,110
Faktiski, uzskata, tāpat kā mēs esam gandrīz
padarot šo pārāk sarežģīta.

505
00:21:18,110 --> 00:21:20,240
Tātad, pieņemsim tagad raut pie beigām
no saraksta, un redzēt, kur

506
00:21:20,240 --> 00:21:21,380
sarežģītība sākas.

507
00:21:21,380 --> 00:21:24,560
Tātad, ja tagad, es alloc no auditorijas.

508
00:21:24,560 --> 00:21:25,540
Ikviens vēlas spēlēt 55?

509
00:21:25,540 --> 00:21:26,700
Labi, es redzēju savu roku pirmās.

510
00:21:26,700 --> 00:21:29,620
Nāciet uz augšu.

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

512
00:21:30,030 --> 00:21:31,177
Kāds ir Jūsu vārds?

513
00:21:31,177 --> 00:21:32,310
>> STUDENTU: [nedzirdama].

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

515
00:21:33,240 --> 00:21:33,890
Labi, nāc uz augšu.

516
00:21:33,890 --> 00:21:35,730
Jūs būsiet numuru 55.

517
00:21:35,730 --> 00:21:37,820
Tātad, jūs, protams, pieder
beigās saraksta.

518
00:21:37,820 --> 00:21:41,850
Tātad, pieņemsim atkārtot simulācija ar mani
ir PTR tikai brīdi.

519
00:21:41,850 --> 00:21:44,050
Tāpēc es esmu pirmo reizi gatavojas norādīt uz
neatkarīgi Ben ir vērsti.

520
00:21:44,050 --> 00:21:45,900
Mēs abi norādot tagad Brian.

521
00:21:45,900 --> 00:21:48,420
Tātad, 55 ir ne mazāks par pieci.

522
00:21:48,420 --> 00:21:52,510
Tāpēc es esmu gatavojas atjaunināt sevi ar
norādot uz Brian nākamais rādītājs, kurš

523
00:21:52,510 --> 00:21:54,450
Tagad, protams, Jason.

524
00:21:54,450 --> 00:21:57,310
55 ir ne mazāks par deviņiem, tā
Es esmu gatavojas atjaunināt PTR.

525
00:21:57,310 --> 00:21:58,890
Es esmu gatavojas atjaunināt PTR.

526
00:21:58,890 --> 00:22:02,290
Es esmu gatavojas atjaunināt PTR
Es gatavojas atjaunināt PTR.

527
00:22:02,290 --> 00:22:05,060
Un es esmu gatavojas - hmm, kas ir
Jūsu vārds atkal?

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

529
00:22:05,560 --> 00:22:09,190
>> SPEAKER 1: Diana ir vērsta, protams,
uz nulli ar savu kreiso roku.

530
00:22:09,190 --> 00:22:13,030
Tātad, ja nav Habata faktiski
pieder skaidri?

531
00:22:13,030 --> 00:22:15,050
Pa kreisi, šeit.

532
00:22:15,050 --> 00:22:19,460
Tātad, kā es varu zināt likt viņai šeit
Es domāju, ka es esmu ieskrūvē augšu.

533
00:22:19,460 --> 00:22:22,420
Jo, ko PTR mākslas
šajā brīdī?

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

535
00:22:23,240 --> 00:22:25,580
Tātad, lai gan vizuāli, mēs varam
protams, redzēt visus šos

536
00:22:25,580 --> 00:22:26,610
puiši šeit uz skatuves.

537
00:22:26,610 --> 00:22:29,680
Man nav tur līdzi iepriekšējo
persona sarakstā.

538
00:22:29,680 --> 00:22:33,210
Man nav pirkstu norādot,,
Šajā gadījumā, mezglu skaits 34.

539
00:22:33,210 --> 00:22:34,760
>> Tā ļauj faktiski sākt šo pāri.

540
00:22:34,760 --> 00:22:37,560
Tāpēc tagad es tiešām ir nepieciešams
Otrais lokālais mainīgais.

541
00:22:37,560 --> 00:22:40,980
Un tas ir tas, ko jūs redzēsiet
faktiskais paraugu C kodu, kur, kā man iet,

542
00:22:40,980 --> 00:22:45,860
kad es mainīšu labo roku norādīt
Jason, tādējādi atstājot Brian aiz muguras, es

543
00:22:45,860 --> 00:22:51,440
labāk sākt, izmantojot manu kreiso roku
atjaunināt kur es bija, tā, ka kā es iet

544
00:22:51,440 --> 00:22:52,700
caur šo sarakstu -

545
00:22:52,700 --> 00:22:55,040
vairāk neveikli nekā es paredzēts
tagad šeit vizuāli -

546
00:22:55,040 --> 00:22:56,740
Es esmu gatavojas nokļūt
saraksta beigās.

547
00:22:56,740 --> 00:23:00,020
>> Šī roka ir vēl null, kas ir diezgan
bezjēdzīgi, izņemot, lai norādītu

548
00:23:00,020 --> 00:23:02,980
Es skaidri beigās no saraksta,
bet tagad vismaz man ir šī

549
00:23:02,980 --> 00:23:08,270
priekštecis rādītājs norādot šeit, tāpēc
Tagad to, kas rokās un kas norādes nepieciešams

550
00:23:08,270 --> 00:23:10,150
jāatjauno?

551
00:23:10,150 --> 00:23:13,214
Kuru roku tu gribi
pārveidot pirmo?

552
00:23:13,214 --> 00:23:15,190
>> STUDENTU: [nedzirdama].

553
00:23:15,190 --> 00:23:16,220
>> SPEAKER 1: Labi, tāpēc Diānas.

554
00:23:16,220 --> 00:23:21,110
Ja jūs vēlaties norādīt
Diānas kreisi rādītājs ir?

555
00:23:21,110 --> 00:23:23,620
Pie 55, iespējams, tā ka
mēs esam ievietota tur.

556
00:23:23,620 --> 00:23:25,560
Un kur ir 55 rādītājs doties?

557
00:23:25,560 --> 00:23:27,000
Uz leju, kas pārstāv null.

558
00:23:27,000 --> 00:23:28,890
Un manas rokas, šajā brīdī, nav
nozīmes, jo tie bija vienkārši

559
00:23:28,890 --> 00:23:30,070
pagaidu mainīgie.

560
00:23:30,070 --> 00:23:31,030
Tāpēc tagad mēs esam darīts.

561
00:23:31,030 --> 00:23:34,650
>> Tātad papildu sarežģījumus tur - un
tas nav tik grūti īstenot,

562
00:23:34,650 --> 00:23:38,660
bet mums ir nepieciešama sekundāra mainīgo, lai padarītu
pārliecinieties, ka pirms es pārvietot manu tiesības

563
00:23:38,660 --> 00:23:42,140
No otras puses, es atjaunināt vērtību manu kreiso
No otras puses, Pred rādītājs šajā gadījumā, tā

564
00:23:42,140 --> 00:23:45,860
ka man ir trailing rādītājs
izsekot, kur es biju.

565
00:23:45,860 --> 00:23:49,360
Tagad kā malā, ja jūs domājat šo
cauri, tas uzskata, tāpat kā tas ir

566
00:23:49,360 --> 00:23:51,490
mazliet kaitinošas ir, lai saglabātu
izsekot šīs kreisās rokas.

567
00:23:51,490 --> 00:23:54,015
>> Kas būtu cits risinājums
Šīs problēmas ir bijušas?

568
00:23:54,015 --> 00:23:56,500
Ja jums pārveidot datus
struktūru mēs runājam

569
00:23:56,500 --> 00:23:59,630
izmantojot tieši tagad?

570
00:23:59,630 --> 00:24:02,690
Ja tas tikai veida jūtas nedaudz
kaitinošas ir, piemēram, divas norādes

571
00:24:02,690 --> 00:24:08,430
iet caur sarakstu, kurš gan cits varētu
ir, ideālā pasaulē, uztur

572
00:24:08,430 --> 00:24:10,160
informāciju, kas mums ir vajadzīgs?

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

574
00:24:11,360 --> 00:24:12,610
>> STUDENTU: [nedzirdama].

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

576
00:24:15,160 --> 00:24:16,150
>> SPEAKER 1: Tieši tā.

577
00:24:16,150 --> 00:24:19,130
Labi, lai tur tiešām interesants
dīgļi ideja.

578
00:24:19,130 --> 00:24:22,470
Un šī ideja par iepriekšējo rādītāju,
norādot iepriekšējā elementa.

579
00:24:22,470 --> 00:24:25,580
Ko darīt, ja es tikai iemieso ka
iekšpusē no saraksta pati?

580
00:24:25,580 --> 00:24:27,810
Un tas būs grūti iztēloties
tas bez visiem papīra

581
00:24:27,810 --> 00:24:28,830
nokrīt uz grīdas.

582
00:24:28,830 --> 00:24:31,860
Bet pieņemsim, ka šie puiši izmanto gan
viņu rokās, lai būtu iepriekšējo

583
00:24:31,860 --> 00:24:35,950
rādītājs, un blakus rādītājs, tādējādi
īstenot to, ko mēs saucam divtik

584
00:24:35,950 --> 00:24:36,830
saistīts saraksts.

585
00:24:36,830 --> 00:24:41,090
Tas ļauj man, lai sakārtotu ar attītu atpakaļ,
daudz vieglāk bez manis,

586
00:24:41,090 --> 00:24:43,800
programmētājs, kam, lai saglabātu
izsekot manuāli -

587
00:24:43,800 --> 00:24:44,980
patiesi manuāli -

588
00:24:44,980 --> 00:24:47,280
, kur es biju agrāk
sarakstā.

589
00:24:47,280 --> 00:24:48,110
Tāpēc mēs nevarēsim darīt.

590
00:24:48,110 --> 00:24:50,950
Mēs turpināsim to vienkārši tāpēc, ka tas ir
nāks par cenu, divreiz

591
00:24:50,950 --> 00:24:53,450
daudz vietas, lai norādes,
Ja jūs vēlaties otru.

592
00:24:53,450 --> 00:24:55,760
Bet tas ir patiešām kopēja
datu struktūra pazīstams kā

593
00:24:55,760 --> 00:24:57,410
divkārt saistīts saraksts.

594
00:24:57,410 --> 00:25:01,310
>> Darīsim galīgo piemēru šeit un nodot
šie puiši, kas to postu.

595
00:25:01,310 --> 00:25:03,270
Tātad 20 malloc.

596
00:25:03,270 --> 00:25:05,320
Nāc uz augšu no eju tur.

597
00:25:05,320 --> 00:25:06,280
Labi, kāds ir tavs vārds?

598
00:25:06,280 --> 00:25:07,440
>> STUDENTU: [nedzirdama].

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

600
00:25:07,855 --> 00:25:08,480
>> STUDENTU: [nedzirdama].

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

602
00:25:09,410 --> 00:25:10,230
OK, come on augšu.

603
00:25:10,230 --> 00:25:11,910
Tev ir 20.

604
00:25:11,910 --> 00:25:14,720
Jūs, protams, gatavojas
pieder starp 17 un 22.

605
00:25:14,720 --> 00:25:16,150
Tātad, ļaujiet man mācīties, mana mācība.

606
00:25:16,150 --> 00:25:18,150
Es esmu gatavojas sākt rādītāju
norādot uz Brian.

607
00:25:18,150 --> 00:25:21,190
Un es esmu nāksies manu kreiso roku
tikai atjaunināt ar Brian, kā es pārietu uz

608
00:25:21,190 --> 00:25:23,600
Jason, pārbaude nav 20 mazāk nekā deviņi?

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

610
00:25:24,060 --> 00:25:25,430
Ir par 20 mazāk nekā 17?

611
00:25:25,430 --> 00:25:25,880
Nē.

612
00:25:25,880 --> 00:25:27,450
Ir par 20 mazāk nekā 22?

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

614
00:25:28,440 --> 00:25:34,070
Tātad, ko norādes vai rokas jāmaina
kur viņi norāda tagad?

615
00:25:34,070 --> 00:25:37,070
>> Tātad, mēs varam darīt 17 norāda uz 20.

616
00:25:37,070 --> 00:25:37,860
Tātad, tas ir jauki.

617
00:25:37,860 --> 00:25:40,080
Kur mēs vēlamies norādīt
Jūsu rādītājs tagad?

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

619
00:25:41,330 --> 00:25:45,410
Un mēs zinām, kur 22 ir, atkal pateicoties
uz manu pagaidu rādītājs.

620
00:25:45,410 --> 00:25:46,760
Tāpēc mēs esam OK tur.

621
00:25:46,760 --> 00:25:49,440
Tāpēc, ka šīs pagaidu uzglabāšanas
Es esmu tur līdzi, kur visi ir.

622
00:25:49,440 --> 00:25:55,055
Un tagad jūs varat vizuāli iedziļināties, kur
jums pieder, un tagad mums ir 1, 2, 3,

623
00:25:55,055 --> 00:25:58,410
4, 5, 6, 7, 8, 9 stresa bumbas,
un kārtu aplausi par

624
00:25:58,410 --> 00:25:59,770
šie puiši, ja mēs varētu.

625
00:25:59,770 --> 00:26:00,410
Labi darīts.

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

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

628
00:26:06,330 --> 00:26:09,860
Un jūs varat saglabāt gabalus
papīra, kā mementos.

629
00:26:09,860 --> 00:26:15,930
>> Labi, tāpēc, ticiet man, tas ir daudz
vieglāk staigāt cauri, ka ar

630
00:26:15,930 --> 00:26:17,680
cilvēkiem, nekā tas ir ar faktisko kodu.

631
00:26:17,680 --> 00:26:22,690
Bet ko jūs atradīsiet tikai brīdi
Tagad ir tā, ka tas pats - ak, paldies.

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

633
00:26:23,630 --> 00:26:29,360
ir tas, ka jūs atradīsiet, ka tos pašus datus
struktūru, saistīts saraksts, faktiski var

634
00:26:29,360 --> 00:26:33,200
tikt izmantoti kā celtniecības bloku pat vairāk
sarežģītas datu struktūras.

635
00:26:33,200 --> 00:26:37,620
>> Un realizēt pārāk tēma šeit ir tas, ka
mēs esam absolūti ieviesa vairāk

636
00:26:37,620 --> 00:26:40,060
sarežģītība vērā īstenošanu
Šī algoritma.

637
00:26:40,060 --> 00:26:43,940
Ievietošanas, un, ja mēs devāmies caur to,
dzēšanu un meklēšana, ir nedaudz

638
00:26:43,940 --> 00:26:46,660
sarežģītāka, nekā tas
bija ar masīvu.

639
00:26:46,660 --> 00:26:48,040
Bet mēs gūstam zināmu dinamiku.

640
00:26:48,040 --> 00:26:50,180
Mēs saņemam adaptīvā datu struktūra.

641
00:26:50,180 --> 00:26:54,010
>> Bet atkal, mēs maksājam cenu ar dažu
papildu sarežģījumus, gan

642
00:26:54,010 --> 00:26:54,910
to īsteno.

643
00:26:54,910 --> 00:26:56,750
Un mēs esam atteikušies brīva piekļuve.

644
00:26:56,750 --> 00:27:00,450
Un, ja godīgi, tur nav kādu jauku
tīrīt slaidu es varu dot jums, ka

645
00:27:00,450 --> 00:27:03,120
saka, ka šeit ir iemesls, kāpēc saistīts saraksts
ir labāka nekā masīva.

646
00:27:03,120 --> 00:27:04,100
Un atstāt to, ka.

647
00:27:04,100 --> 00:27:07,520
Tāpēc, ka tēma atkārtošanos tagad, pat
jo vairāk tāpēc, ka tuvākajās nedēļās, ir

648
00:27:07,520 --> 00:27:10,200
ka tur ne vienmēr
Pareizā atbilde.

649
00:27:10,200 --> 00:27:13,830
>> Tas ir iemesls, kāpēc mums ir atsevišķas ass
no dizaina problēmu kopas.

650
00:27:13,830 --> 00:27:17,700
Tas būs ļoti konteksta jutīga
vai jūs vēlaties izmantot šos datus

651
00:27:17,700 --> 00:27:21,750
struktūra vai ka viens, un tas tiks
atkarīgi no faktiem, kas jums attiecībā

652
00:27:21,750 --> 00:27:24,620
resursu un sarežģītību.

653
00:27:24,620 --> 00:27:28,830
>> Bet ļaujiet man ieteikt, ka ideāls dati
struktūru, Svētais Grāls, būtu

654
00:27:28,830 --> 00:27:32,200
kaut kas ir nemainīgs laiks,
neatkarīgi no tā, cik daudz sīkumi

655
00:27:32,200 --> 00:27:36,940
tā iekšpusē, tas nebūtu pārsteidzoši, ja
datu struktūra atgriezās atbildes

656
00:27:36,940 --> 00:27:37,920
pastāvīgu laiku.

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

658
00:27:38,330 --> 00:27:40,110
Šis vārds ir jūsu milzīgs vārdnīcā.

659
00:27:40,110 --> 00:27:41,550
Vai nē, šis vārds nav.

660
00:27:41,550 --> 00:27:43,270
Vai jebkura šāda problēma pastāv.

661
00:27:43,270 --> 00:27:46,360
Nu pieņemsim redzēt, ja mēs nevaram vismaz
spert soli pretim kas.

662
00:27:46,360 --> 00:27:50,190
>> Ļaujiet man piedāvāt jaunu datu struktūra, kas
var izmantot dažādas lietas,

663
00:27:50,190 --> 00:27:52,260
šajā gadījumā sauc hash tabulu.

664
00:27:52,260 --> 00:27:55,590
Un tāpēc mēs esam patiesībā atpakaļ uz glancing
pie masīva, šajā gadījumā, un

665
00:27:55,590 --> 00:28:00,550
nedaudz patvaļīgi, es esmu sastādīts šis
hash tabulu kā masīva ar veida

666
00:28:00,550 --> 00:28:02,810
divdimensiju masīvs -

667
00:28:02,810 --> 00:28:05,410
vai drīzāk tā ir attēlota šeit kā divām trešdaļām balsu
dimensiju masīvs - bet tas ir tikai

668
00:28:05,410 --> 00:28:10,770
masīvs 26 izmēra, piemēram, ka, ja mēs
zvaniet masīva galda, galda kronšteins

669
00:28:10,770 --> 00:28:12,440
nulle ir taisnstūris augšpusē.

670
00:28:12,440 --> 00:28:15,090
Galda skava 25 ir taisnstūris
apakšā.

671
00:28:15,090 --> 00:28:18,620
Un tas ir, kā es varētu vilkt datu
struktūru, kurā es gribu saglabāt

672
00:28:18,620 --> 00:28:19,790
cilvēku vārdus.

673
00:28:19,790 --> 00:28:24,370
>> Tātad, piemēram, un es ne izdarīt
viss šeit uz virs galvas, ja es

674
00:28:24,370 --> 00:28:29,160
bija šis masīvs, ko es esmu tagad gatavojas
zvanīt hash tabulu, un tas ir atkal

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

676
00:28:31,360 --> 00:28:34,840
Tas šeit ir vieta
viena, un tā tālāk.

677
00:28:34,840 --> 00:28:37,880
Man apgalvo, ka es vēlos, lai izmantotu šos datus
struktūru, lai nodrošinātu diskusiju,

678
00:28:37,880 --> 00:28:42,600
lai saglabātu cilvēku vārdus, Alise un Bobs
un Čārlijs un citi šādi nosaukumi.

679
00:28:42,600 --> 00:28:46,110
Tāpēc domāju, ka par to tagad, jo pirmsākumiem
, teiksim, vārdnīcu

680
00:28:46,110 --> 00:28:47,520
ar daudz vārdiem.

681
00:28:47,520 --> 00:28:49,435
Tie gadās būt vārdi
mūsu piemērs šeit.

682
00:28:49,435 --> 00:28:52,560
Un tas ir pārāk piederīgs, iespējams, līdz
īstenojot pareizrakstības pārbaudītājs, kā mēs

683
00:28:52,560 --> 00:28:54,400
var būt par problēmu, kas seši.

684
00:28:54,400 --> 00:28:59,300
>> Tātad, ja mums ir masīva kopējo platību 26
tā, ka tas ir 25 vieta

685
00:28:59,300 --> 00:29:03,390
apakšā, un es pretenziju, ka Alise
pirmais vārds vārdnīcā

686
00:29:03,390 --> 00:29:07,260
vārdi, kas es gribu ievietot RAM,
šajā datu struktūru, kur ir

687
00:29:07,260 --> 00:29:12,480
instinkti stāsta, ka Alises
nosaukums ir jāiet šajā masīvā?

688
00:29:12,480 --> 00:29:13,510
>> Mums ir 26 iespējas.

689
00:29:13,510 --> 00:29:14,990
Kur mēs gribam likt viņai?

690
00:29:14,990 --> 00:29:16,200
Mēs vēlamies viņai nulles grupā, vai ne?

691
00:29:16,200 --> 00:29:18,280
Par Alice, sauksim šo nulli.

692
00:29:18,280 --> 00:29:20,110
Un B būs viens, un C būs divi.

693
00:29:20,110 --> 00:29:22,600
Tāpēc mēs esam gatavojas rakstīt
Alises vārds šeit.

694
00:29:22,600 --> 00:29:24,890
Ja mēs pēc tam ievietojiet Bob, viņa
Vārds dosies šeit.

695
00:29:24,890 --> 00:29:27,280
Čārlija iet šeit.

696
00:29:27,280 --> 00:29:30,500
Un tā tālāk uz leju pa
Šī datu struktūra.

697
00:29:30,500 --> 00:29:32,090
>> Tas ir brīnišķīgs datu struktūra.

698
00:29:32,090 --> 00:29:32,730
Kāpēc?

699
00:29:32,730 --> 00:29:37,460
Nu, kas ir darbības laiks
ievietojot cilvēka vārdu uz to

700
00:29:37,460 --> 00:29:39,850
Datu struktūra tieši tagad?

701
00:29:39,850 --> 00:29:43,702
Ņemot vērā, ka šī tabula tiek īstenota,
patiesi, kā masīvu.

702
00:29:43,702 --> 00:29:44,940
Nu tas ir nemainīgs laiks.

703
00:29:44,940 --> 00:29:45,800
Tas ir rīkojums par vienu.

704
00:29:45,800 --> 00:29:46,360
Kāpēc?

705
00:29:46,360 --> 00:29:48,630
>> Nu, kā jūs noteikt,
kur Alice pieder?

706
00:29:48,630 --> 00:29:51,000
Paskatās, kas burtu viņas vārdu?

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

708
00:29:51,490 --> 00:29:54,350
Un jūs varat tur nokļūt, ja tas ir string,
, tikai aplūkojot virkni

709
00:29:54,350 --> 00:29:55,200
kronšteins nulle.

710
00:29:55,200 --> 00:29:57,110
Tātad 0. raksturu virkni.

711
00:29:57,110 --> 00:29:57,610
Tas ir viegli.

712
00:29:57,610 --> 00:30:00,350
Mēs did, ka kriptogrāfiskā
sadalījumu nedēļas atpakaļ.

713
00:30:00,350 --> 00:30:05,310
Un tad, kad jūs zināt, ka Alises
burts ir kapitāls, mēs varam atņemt

714
00:30:05,310 --> 00:30:08,160
off 65 vai kapitāla A pati,
kas dod mums nulli.

715
00:30:08,160 --> 00:30:10,940
Tātad, mēs tagad zinām, ka Alise pieder
nulles atrašanās vietu.

716
00:30:10,940 --> 00:30:14,240
>> Un, ņemot vērā rādītāju uz šiem datiem
struktūru, dažu šķirot, cik ilgi

717
00:30:14,240 --> 00:30:18,840
paies man atrast vietu
nullei masīvā?

718
00:30:18,840 --> 00:30:22,080
Tikai viens solis, labi tas ir pastāvīgs laiks
jo brīvpieejas mums

719
00:30:22,080 --> 00:30:23,780
Ierosinātais bija iezīme masīva.

720
00:30:23,780 --> 00:30:28,570
Tātad īsumā, norādītas, ko indekss
no Alises nosaukums ir, kas ir, jo

721
00:30:28,570 --> 00:30:32,610
Šajā gadījumā ir, vai pieņemsim tikai atrisināt
ka uz nulli, kur B ir viens un C ir

722
00:30:32,610 --> 00:30:34,900
divi, norādītas ka no
ir nemainīgs laika.

723
00:30:34,900 --> 00:30:38,510
Man vienkārši ir jāskatās uz savu pirmo burtu,
norādītas, kur nulle ir

724
00:30:38,510 --> 00:30:40,460
masīvs ir arī pastāvīgs laiks.

725
00:30:40,460 --> 00:30:42,140
Tātad, tehniski tas ir
tāpat kā divos posmos tagad.

726
00:30:42,140 --> 00:30:43,330
Bet tas joprojām ir nemainīgs.

727
00:30:43,330 --> 00:30:46,880
Tātad, mēs to saucam par lielu O viens, tāpēc mēs esam
ievietota Alice šajā tabulā

728
00:30:46,880 --> 00:30:48,440
pastāvīgu laiku.

729
00:30:48,440 --> 00:30:50,960
>> Bet, protams, es esmu to
naivs šeit, vai ne?

730
00:30:50,960 --> 00:30:53,240
Ko darīt, ja tur klasē Ārons?

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

732
00:30:53,990 --> 00:30:57,230
Vai kādi citi nosaukumi, kas sākas ar
A. Uz kurieni mēs ejam, lai

733
00:30:57,230 --> 00:31:00,800
šī persona, vai ne?

734
00:31:00,800 --> 00:31:03,420
Es domāju, tagad tur ir tikai trīs
cilvēki, uz galda, tāpēc varbūt mēs

735
00:31:03,420 --> 00:31:07,490
vajadzētu likt Āronu atrašanās vietā
nulle viens divi trīs.

736
00:31:07,490 --> 00:31:09,480
>> Labi, es varētu likt šeit.

737
00:31:09,480 --> 00:31:13,350
Bet tad, ja mēs mēģinātu ievietot Dāvidu vērā
šis saraksts, kur tas Dāvids iet?

738
00:31:13,350 --> 00:31:15,170
Tagad mūsu sistēma sāk sadalīšana
uz leju, pa labi?

739
00:31:15,170 --> 00:31:19,210
Jo tagad Deivids nonāks šeit
ja Aaron ir faktiski šeit.

740
00:31:19,210 --> 00:31:23,060
Un tāpēc tagad šī ideja, kam
tīrs datu struktūra, kas dod mums

741
00:31:23,060 --> 00:31:28,010
konstantā ievietošanas vairs nav
pastāvīgu laiku, jo man ir

742
00:31:28,010 --> 00:31:31,240
pārbauda, ​​ak, Damnit, kādam jau
pie Alises vietā.

743
00:31:31,240 --> 00:31:35,320
>> Ļaujiet man zonde pārējo šo datu
struktūru, meklē vietas likt

744
00:31:35,320 --> 00:31:37,130
kāds, piemēram, Ārona vārdu.

745
00:31:37,130 --> 00:31:39,390
Un tā, ka arī sāk
veikt lineāru laiku.

746
00:31:39,390 --> 00:31:42,710
Turklāt, ja jūs tagad vēlaties, lai atrastu
Aaron šajā datu struktūra, un jūs

747
00:31:42,710 --> 00:31:45,430
pārbaude, un Ārona vārds nav šeit.

748
00:31:45,430 --> 00:31:47,960
Vislabāk, ja jūs vienkārši pateikt Ārona
ne ar datu struktūru.

749
00:31:47,960 --> 00:31:51,530
Bet, ja jūs sākat padarot telpu
Aaron kur būtu bijis D

750
00:31:51,530 --> 00:31:55,600
vai E, jūs, sliktākajā gadījumā, ir jāpārbauda
visa datu struktūra, kas

751
00:31:55,600 --> 00:31:59,480
tādā gadījumā tas tiek nodots uz kaut ko
lineāra lielumu tabulā.

752
00:31:59,480 --> 00:32:00,920
>> Tātad viss, labi, es jums salabot.

753
00:32:00,920 --> 00:32:04,200
Problēma šeit ir tā, ka man bija
26 elementi šajā masīvā.

754
00:32:04,200 --> 00:32:05,000
Ļaujiet man to mainīt.

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

756
00:32:06,010 --> 00:32:10,600
Ļaujiet man mainīt tā, lai drīzāk labklājību
kopumā 26 izmērs, paziņojums dibenu

757
00:32:10,600 --> 00:32:12,720
indekss mainīsies līdz n mīnusa 1.

758
00:32:12,720 --> 00:32:16,610
Ja 26 ir acīmredzami pārāk mazs cilvēkam "
vārdus, jo tur ir tūkstošiem

759
00:32:16,610 --> 00:32:20,830
nosaukumi pasaulē, pieņemsim tikai darīt
ar 100 vai 1000 vai 10000.

760
00:32:20,830 --> 00:32:22,960
Pieņemsim tikai piešķirt daudz vairāk vietas.

761
00:32:22,960 --> 00:32:27,230
>> Labi, ka ne vienmēr samazinās
varbūtība, ka mums nebūs divi

762
00:32:27,230 --> 00:32:31,510
cilvēki ar nosaukumiem, kas sākas ar A, un
tā, jūs gatavojas, lai mēģinātu likt

763
00:32:31,510 --> 00:32:33,120
nosaukumi atrašanās vietā nulles joprojām.

764
00:32:33,120 --> 00:32:36,850
Viņi joprojām turpinās, lai saduras, kas
nozīmē, ka mums joprojām ir nepieciešams risinājums likt

765
00:32:36,850 --> 00:32:41,020
Alise un Ārons un Alicia un citi
nosaukumi, kas sākas ar A citur.

766
00:32:41,020 --> 00:32:43,460
Bet cik daudz problēmu tas ir?

767
00:32:43,460 --> 00:32:46,870
Kāda ir varbūtība, ka jūs
ir sadursmju ar datu

768
00:32:46,870 --> 00:32:48,240
struktūra, kā šis?

769
00:32:48,240 --> 00:32:52,570
>> Nu, ļaujiet man - mēs atgriezīsimies
uz šo jautājumu šeit.

770
00:32:52,570 --> 00:32:55,530
Un skatīties, kā mēs varētu
atrisināt tā pirmo reizi.

771
00:32:55,530 --> 00:32:58,480
Ļaujiet man uzvilkt šo priekšlikumu šeit.

772
00:32:58,480 --> 00:33:02,020
Ko mēs tikko aprakstīts ir algoritms,
heiristisko sauc par lineāru

773
00:33:02,020 --> 00:33:05,030
zondēšana saskaņā ar kuru, ja esat mēģinājuši ievietot
kaut kas šeit šiem datiem

774
00:33:05,030 --> 00:33:08,920
struktūru, ko sauc hash galds,
un tur nav vietas tur, jūs

775
00:33:08,920 --> 00:33:12,000
patiesi zonde datu struktūra
pārbaudot, tas ir pieejams?

776
00:33:12,000 --> 00:33:13,430
Vai tas ir pieejams tas ir pieejams?

777
00:33:13,430 --> 00:33:13,980
Vai tas ir pieejams?

778
00:33:13,980 --> 00:33:17,550
Un, kad tas beidzot ir, jūs ievietojiet
nosaukt, ka jūs sākotnēji paredzēts

779
00:33:17,550 --> 00:33:19,370
citur šajā vietā.

780
00:33:19,370 --> 00:33:23,360
Bet sliktākajā gadījumā, tikai vieta
varētu būt ļoti apakšā no datu

781
00:33:23,360 --> 00:33:25,090
struktūra, pašās beigās no masīva.

782
00:33:25,090 --> 00:33:30,130
>> Tātad lineāra zondēšana, sliktākajā gadījumā,
devolves par lineāru algoritmu, kurā

783
00:33:30,130 --> 00:33:34,500
Ārons, ja viņš notiek, ir ievietota pagājušajā
Šajā datu struktūra, viņš varētu

784
00:33:34,500 --> 00:33:39,540
saduras ar šo pirmo vietu, bet
tad galu ar sliktu luck pašās beigās.

785
00:33:39,540 --> 00:33:43,940
Tātad tas nav konstants
laiks Svētais Grāls mums.

786
00:33:43,940 --> 00:33:47,650
Šī pieeja ievietojot elementiem iekļaut
datu struktūra sauc hash

787
00:33:47,650 --> 00:33:52,050
tabulā nav, šķiet, ir nemainīga laiks
vismaz ne vispārējā gadījumā.

788
00:33:52,050 --> 00:33:54,000
Tas var pāriet uz kaut ko lineāro.

789
00:33:54,000 --> 00:33:56,970
>> Tātad, ko tad, ja mēs atrisināt sadursmes
nedaudz savādāk?

790
00:33:56,970 --> 00:34:00,740
Tātad, šeit ir daudz sarežģītākas
pieeja, kas ir vēl

791
00:34:00,740 --> 00:34:02,800
sauc hash tabulu.

792
00:34:02,800 --> 00:34:05,890
Un hash, kā malā, ko
Es domāju, ir rādītājs, ka

793
00:34:05,890 --> 00:34:07,070
Es minēju iepriekš.

794
00:34:07,070 --> 00:34:09,810
Lai hash kaut ko var būt
domā kā darbības vārds.

795
00:34:09,810 --> 00:34:13,690
>> Tātad, ja jūs Hash Alise ir vārds,
hash funkciju, tā sakot,

796
00:34:13,690 --> 00:34:14,710
vajadzētu atgriezties numuru.

797
00:34:14,710 --> 00:34:18,199
Šajā gadījumā ir nulle, ja viņa pieder pie
vieta nulle, viens, ja viņa pieder pie

798
00:34:18,199 --> 00:34:20,000
vieta viena, un tā tālāk.

799
00:34:20,000 --> 00:34:24,360
Tātad mans Hash funkcija līdz šim ir bijis
super vienkārši, tikai apskatot

800
00:34:24,360 --> 00:34:26,159
Pirmais burts ir kāds vārda.

801
00:34:26,159 --> 00:34:29,090
Bet hash funkcija ir pieņemts,
input daži gabals no datiem,

802
00:34:29,090 --> 00:34:30,210
string, int, neatkarīgi.

803
00:34:30,210 --> 00:34:32,239
Un tas atklepo tipiski numuru.

804
00:34:32,239 --> 00:34:35,739
Un šis skaits ir, ja, ka dati
elements pieder ar datu struktūru

805
00:34:35,739 --> 00:34:37,800
pazīstams šeit kā hash tabulu.

806
00:34:37,800 --> 00:34:41,400
>> Tik vienkārši intuitīvi, tas ir
nedaudz citā kontekstā.

807
00:34:41,400 --> 00:34:44,170
Tas patiesībā ir, atsaucoties uz piemēru
iesaistot dzimšanas dienas, ja

808
00:34:44,170 --> 00:34:46,850
tur varētu būt tikpat daudz kā
31 dienas mēnesī.

809
00:34:46,850 --> 00:34:52,239
Bet ko šī persona nolemj
do, kas sadursmes gadījumā?

810
00:34:52,239 --> 00:34:55,304
Konteksts tagad ir, nevis sadursme
nosaukumi, bet sadursme dzimšanas dienas,

811
00:34:55,304 --> 00:35:00,760
ja divi cilvēki ir tāda pati dzimšanas dienu
2 oktobris, piemēram.

812
00:35:00,760 --> 00:35:02,120
>> STUDENTU: [nedzirdama].

813
00:35:02,120 --> 00:35:05,010
>> SPEAKER 1: Jā, tāpēc šeit mēs esam
pārplūšanu saistītas sarakstiem.

814
00:35:05,010 --> 00:35:07,830
Tātad, tas izskatās nedaudz savādāk
nekā mēs izvilka to agrāk.

815
00:35:07,830 --> 00:35:10,790
Bet mēs, šķiet, ir masīvs
kreisajā pusē.

816
00:35:10,790 --> 00:35:13,230
Tas ir viens rādītājs, ne
īpašs iemesls.

817
00:35:13,230 --> 00:35:14,630
Bet tas joprojām ir masīvs.

818
00:35:14,630 --> 00:35:16,160
Tas ir masīvs norādes.

819
00:35:16,160 --> 00:35:20,670
Un katrs no šiem elementiem, katrs no
šīs aprindas vai slīpsvītras - slash

820
00:35:20,670 --> 00:35:23,970
pārstāvot null - katram no šiem
norādes ir acīmredzami vērsta uz

821
00:35:23,970 --> 00:35:25,730
kādi datu struktūra?

822
00:35:25,730 --> 00:35:26,890
Saistīts saraksts.

823
00:35:26,890 --> 00:35:30,530
>> Tāpēc tagad mums ir iespēja
grūti kodu mūsu programmā

824
00:35:30,530 --> 00:35:32,010
izmērs no tabulā.

825
00:35:32,010 --> 00:35:35,360
Šajā gadījumā, mēs zinām, ka nekad
vairāk nekā 31 dienas mēnesī.

826
00:35:35,360 --> 00:35:38,480
Tik grūti kodēšanas vērtību, piemēram, 31 ir
saprātīgi šajā kontekstā.

827
00:35:38,480 --> 00:35:42,700
Saistībā ar nosaukumiem, grūti kodēšana
26 nav nesaprātīgi tas Tautas

828
00:35:42,700 --> 00:35:46,340
nosaukumi sākas tikai ar, piemēram,
alfabēts iesaistot caur Z.

829
00:35:46,340 --> 00:35:50,180
>> Mēs varam piestūķēt tos visus šos datus
struktūra tik ilgi, kamēr, kad mēs nokļūt

830
00:35:50,180 --> 00:35:55,330
sadursme, mēs nelieciet vārdus šeit,
tā vietā mēs domājam par šīm šūnām

831
00:35:55,330 --> 00:36:00,270
nevis kā stīgas paši, bet kā
norādes uz to, piemēram, Alice.

832
00:36:00,270 --> 00:36:03,660
Un tad Alice var būt vēl viens rādītājs
uz citu nosaukumu, sākot ar

833
00:36:03,660 --> 00:36:06,150
A. Un Bobs faktiski iet vairāk nekā šeit.

834
00:36:06,150 --> 00:36:10,850
>> Un, ja tur ir cits nosaukums sākas
ar B, viņš nonāk vairāk nekā šeit.

835
00:36:10,850 --> 00:36:15,070
Un tā katru šo elementu
galda divas, ja mēs paredzēti šajā

836
00:36:15,070 --> 00:36:17,350
nedaudz vairāk gudri -

837
00:36:17,350 --> 00:36:18,125
come on -

838
00:36:18,125 --> 00:36:22,950
ja mēs izstrādājām šo nedaudz vairāk
gudri, tagad kļūst par adaptīvu datu

839
00:36:22,950 --> 00:36:27,720
struktūra, kurā nav grūti ierobežot
no tā, cik daudz elementi var ievietot

840
00:36:27,720 --> 00:36:30,700
par to, jo, ja jums ir
sadursmes, tas ir jauki.

841
00:36:30,700 --> 00:36:34,690
Vienkārši iet uz priekšu un pievienot to
tas, ko mēs redzējām mazliet atpakaļ bija

842
00:36:34,690 --> 00:36:38,290
pazīstams kā saistītu sarakstu.

843
00:36:38,290 --> 00:36:39,690
>> Nu pieņemsim pauzi tikai brīdi.

844
00:36:39,690 --> 00:36:42,570
Kas ir no sadursmes varbūtība
pirmajā vietā?

845
00:36:42,570 --> 00:36:45,480
Labi, varbūt es esmu vairāk domāju, varbūt
Es esmu vairāk nekā inženierzinātnes šo problēmu,

846
00:36:45,480 --> 00:36:46,370
tāpēc, ka jūs zināt, ko?

847
00:36:46,370 --> 00:36:49,070
Jā, es varētu nākt klajā ar patvaļīgu
piemēri off augšpusē manu galvu, piemēram,

848
00:36:49,070 --> 00:36:52,870
Allison un Ārons, bet patiesībā,
dota vienota sadale

849
00:36:52,870 --> 00:36:56,990
ieejas, ka ir daži izlases iespraudumiem
uz datu struktūru, kas patiešām ir

850
00:36:56,990 --> 00:36:58,580
varbūtība sadursmes?

851
00:36:58,580 --> 00:37:01,670
Nu izrādās, tas ir faktiski
super augsts.

852
00:37:01,670 --> 00:37:03,850
Ļaujiet man vispārināt šo
problēma ir kā šī.

853
00:37:03,850 --> 00:37:08,890
>> Tātad telpā ar n CS50 studenti, kas ir
varbūtība, ka vismaz

854
00:37:08,890 --> 00:37:11,010
divi studenti telpā
ir pašas dzimšanas diena?

855
00:37:11,010 --> 00:37:13,346
Tātad tur ir kas. daži Hund -

856
00:37:13,346 --> 00:37:16,790
200, 300 cilvēki šeit un vairākām
simti cilvēku mājās šodien.

857
00:37:16,790 --> 00:37:20,670
Tātad, ja jums gribēju jautāt sev, kas ir
varbūtība divi cilvēki

858
00:37:20,670 --> 00:37:23,930
šajā telpā, kam ir tāda pati dzimšanas,
mēs varam skaitlis šo out.

859
00:37:23,930 --> 00:37:26,250
Un es varu pieprasīt patiesībā ir divi
cilvēki ar tādu pašu dzimšanas dienā.

860
00:37:26,250 --> 00:37:29,560
>> Piemēram, vai kāds
ir dzimšanas diena šodien?

861
00:37:29,560 --> 00:37:31,340
Vakar?

862
00:37:31,340 --> 00:37:32,590
Rīt?

863
00:37:32,590 --> 00:37:35,980
Labi, lai tā uzskata, tāpat kā es esmu gatavojas
lai to darīt 363, vai arī tā vairāk

864
00:37:35,980 --> 00:37:39,500
reizes, lai tiešām noskaidrotu
ja mums ir sadursmi.

865
00:37:39,500 --> 00:37:42,350
Vai mēs varētu vienkārši darīt matemātiski
nevis tediously

866
00:37:42,350 --> 00:37:43,200
darot.

867
00:37:43,200 --> 00:37:44,500
Un ierosināt sekojošo.

868
00:37:44,500 --> 00:37:48,740
>> Tāpēc es ierosinu, ka mēs varētu modelēt
varbūtība, ka diviem cilvēkiem, kam

869
00:37:48,740 --> 00:37:55,320
pats dzimšanas diena kā varbūtību 1
mīnus varbūtība, ka neviens, kam

870
00:37:55,320 --> 00:37:56,290
pats dzimšanas diena.

871
00:37:56,290 --> 00:37:59,960
Tātad, lai iegūtu šo, un tas ir tikai
iedomātā veids, kā rakstot šo, lai

872
00:37:59,960 --> 00:38:03,090
pirmais cilvēks telpā, viņš vai viņa
var būt jebkura no šīm iespējams

873
00:38:03,090 --> 00:38:07,370
dzimšanas dienas, pieņemot, 365 dienas gadā,
ar atvainošanos personām ar

874
00:38:07,370 --> 00:38:08,760
februāris 29 dzimšanas dienu.

875
00:38:08,760 --> 00:38:13,470
>> Tātad, pirmais cilvēks šajā telpā ir bez maksas
lai jebkuru skaitu dzimšanas dienas

876
00:38:13,470 --> 00:38:18,280
no 365 iespējām, lai
mēs darīsim, ka 365 dalīts ar 365,

877
00:38:18,280 --> 00:38:18,990
, kas ir viens.

878
00:38:18,990 --> 00:38:22,700
Nākamajai personai telpā, ja mērķis
ir, lai izvairītos no sadursmes, var tikai

879
00:38:22,700 --> 00:38:26,460
ir viņa vai viņas dzimšanas dienu par to, kā
daudzi un dažādi iespējamie dienās?

880
00:38:26,460 --> 00:38:27,610
364.

881
00:38:27,610 --> 00:38:31,430
Tātad otrais termins šajā izpausmes ir
būtībā dara, ka math par mums

882
00:38:31,430 --> 00:38:33,460
atņemot off vienu iespējamo dienu.

883
00:38:33,460 --> 00:38:36,390
Un tad nākamajā dienā, nākamajā dienā,
Otrā dienā uz leju, lai kopējā

884
00:38:36,390 --> 00:38:38,100
cilvēku telpā.

885
00:38:38,100 --> 00:38:41,290
>> Un, ja mēs pēc tam apsvērt, kādi tad ir
varbūtība nav ikvienam, kam

886
00:38:41,290 --> 00:38:45,265
unikālas dzimšanas dienas, bet atkal 1 mīnus
tas, ko mēs saņemam, ir izteiksme

887
00:38:45,265 --> 00:38:47,810
ka var ļoti fancifully
izskatās šādi.

888
00:38:47,810 --> 00:38:50,330
Bet tas ir vairāk interesanti
apskatīt vizuāli.

889
00:38:50,330 --> 00:38:55,120
Tas ir diagramma, kur uz x ass ir
cilvēku skaits telpā,

890
00:38:55,120 --> 00:38:56,180
numurs dzimšanas dienas.

891
00:38:56,180 --> 00:38:59,840
Uz y-ass ir varbūtība
no sadursmes, divi cilvēki

892
00:38:59,840 --> 00:39:01,230
kam ir tāda pati dzimšanas diena.

893
00:39:01,230 --> 00:39:05,020
>> Un no šīs līknes takeaway ir
ka tiklīdz jums patīk 40

894
00:39:05,020 --> 00:39:11,110
studenti, jūs pat pie 90% varbūtību
combinatorically divu

895
00:39:11,110 --> 00:39:13,550
cilvēkiem vai vairāk, kam
pats dzimšanas diena.

896
00:39:13,550 --> 00:39:18,600
Un, kad jums patīk 58 cilvēkiem, tas ir
gandrīz 100% no iespēju divu

897
00:39:18,600 --> 00:39:21,310
cilvēki telpā nāksies
pats dzimšanas diena, lai gan tur ir

898
00:39:21,310 --> 00:39:26,650
365 vai 366 iespējamie kausi, un
Tikai 58 cilvēki telpā.

899
00:39:26,650 --> 00:39:29,900
Vienkārši statistiski jūs varētu
get sadursmes, kas īsā

900
00:39:29,900 --> 00:39:31,810
motivē šo diskusiju.

901
00:39:31,810 --> 00:39:35,890
Ka, pat ja mēs fancy šeit, un
sākat ar šo ķēdes, mēs joprojām esam

902
00:39:35,890 --> 00:39:36,950
nāksies sadursmes.

903
00:39:36,950 --> 00:39:42,710
>> Tā, ka Rodas jautājums, kāda ir
izmaksas, kā to ievietošanas un dzēšanas

904
00:39:42,710 --> 00:39:44,850
par datu struktūru, piemēram, tas?

905
00:39:44,850 --> 00:39:46,630
Nu ļaujiet man ieteikt -

906
00:39:46,630 --> 00:39:51,570
un ļaujiet man iet atpakaļ uz ekrāna vairāk
šeit - ja mums ir n elementi

907
00:39:51,570 --> 00:39:56,330
sarakstā, tāpēc, ja mēs cenšamies, lai ievietotu
n elementi, un mums ir

908
00:39:56,330 --> 00:39:58,050
cik kopā kausi?

909
00:39:58,050 --> 00:40:03,450
Teiksim 31 Kopā kausi
gadījumā, dzimšanas dienas.

910
00:40:03,450 --> 00:40:09,240
Kāds ir maksimālais garums ir viena
no šīs ķēdes, iespējami?

911
00:40:09,240 --> 00:40:12,670
>> Ja atkal tur ir 31 iespējas
dzimšanas dienu, kas attiecīgajā mēnesī.

912
00:40:12,670 --> 00:40:14,580
Un mēs esam tikai salipšanu ikvienam -

913
00:40:14,580 --> 00:40:15,580
patiesībā tas ir muļķīgs piemērs.

914
00:40:15,580 --> 00:40:16,960
Darīsim 26 vietā.

915
00:40:16,960 --> 00:40:20,890
Tātad, ja tiešām ir cilvēki, kuru vārdi
sākt ar līdz Z, tādējādi dodot

916
00:40:20,890 --> 00:40:22,780
mums 26 iespējas.

917
00:40:22,780 --> 00:40:25,920
Un mēs esam, izmantojot datu struktūra, piemēram,
kuru mēs tikko redzējām, ar kuru mēs esam

918
00:40:25,920 --> 00:40:30,210
masīvu norādes, katrs no kuriem
norāda uz saistītā sarakstā, ja to

919
00:40:30,210 --> 00:40:32,360
Pirmais saraksts ir visi
ar nosaukumu Alice.

920
00:40:32,360 --> 00:40:35,770
Otrajā sarakstā ir katrs ar
nosaukt sākot ar, sākot

921
00:40:35,770 --> 00:40:36,980
ar B, un tā tālāk.

922
00:40:36,980 --> 00:40:41,020
>> To, kas ir iespējams, garums no katras no
šie saraksti, ja mēs pieņemam, skaistu tīru

923
00:40:41,020 --> 00:40:45,410
izplatīšana vārdu, izmantojot Z
visā datu struktūru?

924
00:40:45,410 --> 00:40:50,210
Tur ir n cilvēki, datu struktūru
dalīts ar 26, ja viņi labi

925
00:40:50,210 --> 00:40:52,110
sadalīts pa visu
datu struktūra.

926
00:40:52,110 --> 00:40:54,970
Tā garums no katra no tām
ķēdes ir n dalot ar 26.

927
00:40:54,970 --> 00:40:57,380
Bet Big O notācija, kas tas ir?

928
00:40:57,380 --> 00:41:00,100

929
00:41:00,100 --> 00:41:02,440
Kas ir tas, ka tiešām?

930
00:41:02,440 --> 00:41:04,150
Tātad, tas ir tiešām tikai n, vai ne?

931
00:41:04,150 --> 00:41:06,620
Tāpēc, ka mēs esam teica agrāk,
ka ugh jūs izdalot ar 26.

932
00:41:06,620 --> 00:41:08,710
Jā, patiesībā tas ir ātrāk.

933
00:41:08,710 --> 00:41:12,720
Bet teorētiski, tas nav būtiski
viss, kas ātrāk.

934
00:41:12,720 --> 00:41:16,040
>> Tāpēc mums nav, šķiet, ir viss, kas daudz
tuvāk šim Svētais Grāls.

935
00:41:16,040 --> 00:41:17,750
Faktiski, tas ir tikai lineārs laiks.

936
00:41:17,750 --> 00:41:20,790
Heck, šajā brīdī, kāpēc ne mēs
tikai izmantot vienu milzīgu saistīts saraksts?

937
00:41:20,790 --> 00:41:23,510
Kāpēc ne mēs tikai izmantot viens milzīgs
masīvs, lai saglabātu vārdus

938
00:41:23,510 --> 00:41:25,010
ikvienam istabā?

939
00:41:25,010 --> 00:41:28,280
Nu, tur vēl kaut kas
pārliecinoši par hash tabulu?

940
00:41:28,280 --> 00:41:30,810
Vai ir vēl kaut kas pārliecinoši
par datu struktūru

941
00:41:30,810 --> 00:41:33,940
ka izskatās šādi?

942
00:41:33,940 --> 00:41:35,182
Tas.

943
00:41:35,182 --> 00:41:37,050
>> STUDENTU: [nedzirdama].

944
00:41:37,050 --> 00:41:39,840
>> SPEAKER 1: labi, un, ja tā ir tikai
lineāra laiks algoritmu, un

945
00:41:39,840 --> 00:41:42,780
lineārā laika datu struktūra, kāpēc ne es
tikai glabāt ikviena vārdu liels

946
00:41:42,780 --> 00:41:44,210
masīvs, vai arī lielā saistīts sarakstu?

947
00:41:44,210 --> 00:41:47,010
Un pārtraukt nākt klajā ar CS tik daudz grūtāk
nekā tai vajadzētu būt?

948
00:41:47,010 --> 00:41:49,600

949
00:41:49,600 --> 00:41:53,190
Kas ir pārliecinoši par to, pat
lai gan es saskrāpēts to ārā?

950
00:41:53,190 --> 00:41:54,930
>> STUDENTU: [nedzirdama].

951
00:41:54,930 --> 00:41:57,040
>> SPEAKER 1: Iespraudumi nav?

952
00:41:57,040 --> 00:41:58,140
Dārgi vairs.

953
00:41:58,140 --> 00:42:03,390
Tātad ievietošanas potenciāli varētu vēl
ir nemainīgs laikā, pat tad, ja jūsu dati

954
00:42:03,390 --> 00:42:07,910
struktūra izskatās šādi, masīvs
norādes, katrs no kuriem ir pavērsts

955
00:42:07,910 --> 00:42:09,550
potenciāli saistīts saraksts.

956
00:42:09,550 --> 00:42:15,220
Kā jūs varētu panākt pastāvīgu
laiks ievietošanas nosaukumus?

957
00:42:15,220 --> 00:42:16,280
Stick to priekšā, vai ne?

958
00:42:16,280 --> 00:42:19,290
>> Ja mēs upurēt dizaina mērķi no
agrāk, ja mēs vēlējāmies, lai saglabātu

959
00:42:19,290 --> 00:42:22,650
ikviena cilvēka vārdu, piemēram, sakārtoti,
vai visu uz skatuves numuriem sakārtoti,

960
00:42:22,650 --> 00:42:25,020
pieņemsim, ka mums ir
nešķiroti saistīts saraksts.

961
00:42:25,020 --> 00:42:29,960
Tas tikai izmaksas mums vienu vai divus soļus,
piemēram, attiecībā uz Ben un Brian

962
00:42:29,960 --> 00:42:32,750
agrāk, lai ievietotu elements ir
sākums sarakstā.

963
00:42:32,750 --> 00:42:36,090
Tātad, ja mums nav jārūpējas par šķirošanas visu
no nosaukumiem, kas sākas ar vai visiem

964
00:42:36,090 --> 00:42:39,660
nosaukumi, kas sākas ar burtu B, mēs joprojām var
panāktu pastāvīgu laiku ievietošanas.

965
00:42:39,660 --> 00:42:43,900
Tagad meklē up Alise vai Bobs vai jebkuru nosaukumu
kopumā ir vēl kāda?

966
00:42:43,900 --> 00:42:48,100
Tas ir liels n O dalīts ar 26, jo
Ideāls gadījums, kad visi ir vienādi

967
00:42:48,100 --> 00:42:51,190
izplatīt, ja tur ir tik daudz s
kā tur ir z, kas, iespējams, ir

968
00:42:51,190 --> 00:42:52,220
nereāls.

969
00:42:52,220 --> 00:42:53,880
Bet tas joprojām ir lineāra.

970
00:42:53,880 --> 00:42:57,120
>> Bet šeit mēs nonākam atpakaļ uz punktu
gada asimptotiskās notācijas pagaidām

971
00:42:57,120 --> 00:42:58,600
teorētiski taisnība.

972
00:42:58,600 --> 00:43:02,960
Bet reālajā pasaulē, ja man apgalvo, ka
mana programma var darīt kaut 26 reizes

973
00:43:02,960 --> 00:43:06,210
ātrāk nekā jums, kuru programma
jūs gatavojas vēlaties izmantot?

974
00:43:06,210 --> 00:43:09,660
Jūsu vai raktuves, kas
ir 26 reizes ātrāks?

975
00:43:09,660 --> 00:43:14,320
Reāli, persona, kura ir 26
reizes ātrāk, pat tad, ja teorētiski

976
00:43:14,320 --> 00:43:18,790
mūsu algoritmi darbojas pats
asimptotiskā darbības laiks.

977
00:43:18,790 --> 00:43:20,940
>> Ļaujiet man piedāvāt atšķirīgu
risinājums vispār.

978
00:43:20,940 --> 00:43:24,380
Un, ja tas nav trieciens jūsu prātā,
mēs esam no datu struktūras.

979
00:43:24,380 --> 00:43:27,420
Tātad šis ir tas Trie -

980
00:43:27,420 --> 00:43:28,520
sava veida stulba nosaukumu.

981
00:43:28,520 --> 00:43:32,880
Tas nāk no ieguves, un vārdu
tekstā ir ierakstīts Trie, t-r-i-e, jo no

982
00:43:32,880 --> 00:43:34,450
kurss izguves izklausās Trie.

983
00:43:34,450 --> 00:43:36,580
Bet tas ir vēsture
vārda Trie.

984
00:43:36,580 --> 00:43:40,980
>> Tātad Trie ir tiešām sava veida koku,
un tas ir arī saspēle šo vārdu.

985
00:43:40,980 --> 00:43:46,330
Un, pat ja jūs nevar gluži redzēt
ar šo vizualizāciju, Trie ir

986
00:43:46,330 --> 00:43:50,790
koku strukturēti, kā ģimenes koku ar
viens sencis augšā un daudz

987
00:43:50,790 --> 00:43:54,530
par mazbērniem un lielu mazbērniem
kā atstāj uz grunts.

988
00:43:54,530 --> 00:43:58,100
Bet katrs savā Trie mezgls ir masīvs.

989
00:43:58,100 --> 00:44:00,680
Un tas ir masīvā - un pieņemsim
pārspīlēju brīdi - tas ir

990
00:44:00,680 --> 00:44:04,600
masīvs, šajā gadījumā, no 26 izmēra, kur
katrs mezgls atkal ir masīvs izmēra

991
00:44:04,600 --> 00:44:09,000
26, kur 0. Elements, kas
masīvs pārstāv, un pēdējā

992
00:44:09,000 --> 00:44:11,810
elements, katrs šāds
masīvs pārstāv Z.

993
00:44:11,810 --> 00:44:15,520
>> Tāpēc es ierosinu, tad, ka šie dati
struktūra, kas pazīstams kā Trie, var būt

994
00:44:15,520 --> 00:44:17,600
izmantot arī, lai saglabātu vārdus.

995
00:44:17,600 --> 00:44:21,740
Mēs redzējām pirms brīža, kā mēs varētu uzglabāt
Citiem vārdiem sakot, vai šajā gadījumā vārdu, un mēs

996
00:44:21,740 --> 00:44:25,440
redzēja agrāk kā mēs varam saglabāt numurus,
bet, ja mēs koncentrējamies uz nosaukumiem vai virknes

997
00:44:25,440 --> 00:44:27,460
šeit, paziņojums, kas ir interesanti.

998
00:44:27,460 --> 00:44:32,210
Man apgalvo, ka vārds Maxwell ir
iekšpusē no šī datu struktūru.

999
00:44:32,210 --> 00:44:33,730
Kur jūs redzat Maxwell?

1000
00:44:33,730 --> 00:44:35,140
>> STUDENTU: [nedzirdama].

1001
00:44:35,140 --> 00:44:36,240
>> SPEAKER 1: Pa kreisi.

1002
00:44:36,240 --> 00:44:39,910
Tātad, kas ir interesanti ar šiem datiem
struktūra ir nevis veikalā ar

1003
00:44:39,910 --> 00:44:46,200
string M-A-X-W-E-L-L slīpsvītru nulle, visi
contiguously, ko jūs, nevis darīt

1004
00:44:46,200 --> 00:44:46,890
seko.

1005
00:44:46,890 --> 00:44:50,510
Ja tas ir Trie, piemēram, datu struktūru,
kuriem katram mezglu atkal masīvs,

1006
00:44:50,510 --> 00:44:54,650
un jūs vēlaties saglabāt Maxwell, vispirms
indekss un tā saknes ir mezglā, lai

1007
00:44:54,650 --> 00:44:57,810
runāt, augšējais mezglu,
pēc atrašanās M, pa labi, tā

1008
00:44:57,810 --> 00:44:59,160
aptuveni uz centru.

1009
00:44:59,160 --> 00:45:03,740
Un tad no turienes, jums sekot
rādītāju uz bērnu mezglu, lai runāt.

1010
00:45:03,740 --> 00:45:06,150
Tātad ciltskoku nozīmē,
jums sekot to uz leju.

1011
00:45:06,150 --> 00:45:09,030
Un tas noved jūs uz citu mezglu
pa kreisi tur, kas ir

1012
00:45:09,030 --> 00:45:10,540
tikai citā masīvs.

1013
00:45:10,540 --> 00:45:14,710
>> Un tad, ja jūs vēlaties saglabāt Maxwell,
Jūs atradīsiet rādītāju, kas pārstāv

1014
00:45:14,710 --> 00:45:16,430
, Kas ir šī viena šeit.

1015
00:45:16,430 --> 00:45:17,840
Tad jums doties uz nākamo mezglu.

1016
00:45:17,840 --> 00:45:20,100
Un paziņojums - tas ir iemesls, kāpēc bildes
nedaudz maldinošs -

1017
00:45:20,100 --> 00:45:21,990
šis mezgls izskatās super niecīga.

1018
00:45:21,990 --> 00:45:26,050
Bet uz tā labajā pusē ir Y un Z.
Tas ir tikai autors ir saīsināts

1019
00:45:26,050 --> 00:45:27,630
attēlu, lai jūs faktiski
redz lietas.

1020
00:45:27,630 --> 00:45:30,400
Pretējā gadījumā šo attēlu
varētu būt ļoti plašs.

1021
00:45:30,400 --> 00:45:36,180
Tātad tagad jūs indekss par atrašanās vietu X, tad
W, tad E, tad L, pēc tam L. Tad to, kas ir

1022
00:45:36,180 --> 00:45:37,380
tas zinātkāre?

1023
00:45:37,380 --> 00:45:41,250
>> Nu, ja mēs, izmantojot šāda veida jaunas
uzņemties par to, kā saglabāt virknes

1024
00:45:41,250 --> 00:45:44,500
datu struktūra, jums joprojām ir nepieciešams
būtībā ir pārbaudīt pie datos

1025
00:45:44,500 --> 00:45:47,250
struktūra, vārds beidzas šeit.

1026
00:45:47,250 --> 00:45:50,830
Citiem vārdiem sakot, katrs no šiem mezgliem
kaut kā ir jāatceras, ka mēs

1027
00:45:50,830 --> 00:45:53,500
faktiski sekoja visi šie norādes
un atstāj maz

1028
00:45:53,500 --> 00:45:58,370
maizes druskas apakšā šeit šā
struktūra, lai norādītu, M-A-X-W-E-L-L ir

1029
00:45:58,370 --> 00:46:00,230
tiešām šajā datu struktūra.

1030
00:46:00,230 --> 00:46:02,040
>> Tātad, mēs varētu darīt šādi.

1031
00:46:02,040 --> 00:46:06,810
Katrs no attēla, mēs tikai mezgliem
motorzāģis ir viens, masīvs 27 izmēra.

1032
00:46:06,810 --> 00:46:10,550
Un tas tagad ir 27, jo p noteikti seši,
mēs faktiski dod jums apostrofu,

1033
00:46:10,550 --> 00:46:13,590
lai mēs varētu būt nosaukumi, piemēram, O'Reilly
un citi ar apostrofus.

1034
00:46:13,590 --> 00:46:14,820
Bet pati ideja.

1035
00:46:14,820 --> 00:46:17,710
Katrs no šiem elementiem
masīvs norāda uz struct

1036
00:46:17,710 --> 00:46:19,320
mezglā, lai tikai mezglā.

1037
00:46:19,320 --> 00:46:21,430
Tātad tas ir ļoti atgādina
Mūsu saistītajā sarakstā.

1038
00:46:21,430 --> 00:46:24,550
>> Un tad man ir Būla, ko es ņemšu
zvanu vārdu, kas ir tikai būs

1039
00:46:24,550 --> 00:46:29,120
taisnība, ja vārds beidzas šis
mezglu kokā.

1040
00:46:29,120 --> 00:46:32,870
Tā faktiski ir maz
trijstūris mēs redzējām pirms brīža.

1041
00:46:32,870 --> 00:46:37,190
Tātad, ja vārds beidzas tajā mezglā
koks, ka vārds lauks būs taisnība,

1042
00:46:37,190 --> 00:46:41,990
, kas ir konceptuāli pārbaudīt off, vai
mēs pie šī trīsstūris, jā

1043
00:46:41,990 --> 00:46:44,080
ir vārds šeit.

1044
00:46:44,080 --> 00:46:45,120
>> Tātad šī ir Trie.

1045
00:46:45,120 --> 00:46:48,540
Un tagad jautājums ir, ko
ir tās darbības laiks?

1046
00:46:48,540 --> 00:46:49,930
Vai tas ir liels O n?

1047
00:46:49,930 --> 00:46:51,410
Vai tas ir kaut kas cits?

1048
00:46:51,410 --> 00:46:57,330
Nu, ja jums ir n nosaukumus šiem datiem
struktūru, Maxwell ir tikai viens no

1049
00:46:57,330 --> 00:47:02,330
tiem, kas ir darba laiks
Ievietojot vai atrast Maxwell?

1050
00:47:02,330 --> 00:47:06,230

1051
00:47:06,230 --> 00:47:09,050
Kāds ir darba laiks
ievietojot Maxwell?

1052
00:47:09,050 --> 00:47:11,740
Ja tur ir n citi nosaukumi
jau galda?

1053
00:47:11,740 --> 00:47:12,507
Yeah?

1054
00:47:12,507 --> 00:47:15,429
>> STUDENTU: [nedzirdama].

1055
00:47:15,429 --> 00:47:17,550
>> SPEAKER 1: Jā, tas ir garums
nosaukuma, vai ne?

1056
00:47:17,550 --> 00:47:24,420
Tātad, M-a-x-W-e-l-l, lai tā uzskata, piemēram, tas
algoritms ir liels O septiņi.

1057
00:47:24,420 --> 00:47:26,580
Tagad, protams, nosaukums
atšķiras pēc garuma.

1058
00:47:26,580 --> 00:47:27,380
Varbūt tas ir īsais nosaukums.

1059
00:47:27,380 --> 00:47:28,600
Varbūt tas ir garāks nosaukumu.

1060
00:47:28,600 --> 00:47:33,390
Bet kas ir galvenais šeit ir tas, ka
tas ir konstante.

1061
00:47:33,390 --> 00:47:36,810
Un varbūt tas nav īsti nemainīgs,
bet, dievs, ja reāli, jo

1062
00:47:36,810 --> 00:47:41,570
vārdnīcu, tur droši vien dažas robeža
par burtu skaits, kas

1063
00:47:41,570 --> 00:47:43,820
personas vārds kādā konkrētā valstī.

1064
00:47:43,820 --> 00:47:46,940
>> Un tā mēs varam pieņemt, ka
vērtība ir nemainīga.

1065
00:47:46,940 --> 00:47:47,750
Es nezinu, kas tas ir.

1066
00:47:47,750 --> 00:47:50,440
Tas ir iespējams, lielāks nekā
mēs uzskatām, ka ir.

1067
00:47:50,440 --> 00:47:52,720
Tāpēc, ka tur vienmēr ir dažas stūra
gadījumā ar crazy garu nosaukumu.

1068
00:47:52,720 --> 00:47:56,360
Tāpēc sauksim to k, bet tas joprojām
nemainīgs iespējams, jo katrs

1069
00:47:56,360 --> 00:48:00,190
vārds pasaulē, vismaz
konkrētā valstī, ir tas, ka garums vai

1070
00:48:00,190 --> 00:48:01,780
īsāks, tāpēc tas ir nemainīgs.

1071
00:48:01,780 --> 00:48:04,490
Bet, kad mēs esam kaut ko teica, ir liels
O par konstantu vērtību, kas ir kas

1072
00:48:04,490 --> 00:48:07,760
tiešām atbilst?

1073
00:48:07,760 --> 00:48:10,420
Tas ir patiešām pats
kā saka pastāvīgu laiku.

1074
00:48:10,420 --> 00:48:11,530
>> Tagad mēs esam sava veida krāpšanos, vai ne?

1075
00:48:11,530 --> 00:48:15,340
Mēs esam veida piesaistot kādu teoriju
šeit teikt, ka labi, lai k ir

1076
00:48:15,340 --> 00:48:17,450
tiešām tikai pasūtīt vienu,
un tas ir nemainīgs laiks.

1077
00:48:17,450 --> 00:48:18,200
Bet tas tiešām ir.

1078
00:48:18,200 --> 00:48:22,550
Jo galvenais ieskatu šeit ir tas, ka
ja mums ir n vārdi jau šajā

1079
00:48:22,550 --> 00:48:26,010
datu struktūra, un mēs ievietot Maxwell,
ir laika daudzums, kas nepieciešams, lai mēs

1080
00:48:26,010 --> 00:48:29,530
ievietot Maxwell vispār skarto
pēc tā, cik daudz citu cilvēku

1081
00:48:29,530 --> 00:48:31,100
ir datu struktūra?

1082
00:48:31,100 --> 00:48:31,670
Nešķiet būt.

1083
00:48:31,670 --> 00:48:36,280
Ja man būtu miljards vairāk elementiem, lai šis
Trie, un pēc tam ievietojiet Maxwell, tiek

1084
00:48:36,280 --> 00:48:38,650
viņš vispār ietekmē?

1085
00:48:38,650 --> 00:48:39,050
Nē.

1086
00:48:39,050 --> 00:48:42,950
Un tas ir atšķirībā no jebkura no dienas datu
struktūras, mēs esam redzējuši līdz šim, kur

1087
00:48:42,950 --> 00:48:46,820
darba laiks jūsu algoritms ir
pilnīgi neatkarīgi no tā, cik daudz

1088
00:48:46,820 --> 00:48:51,430
sīkumi ir vai nav jau
šajā datu struktūra.

1089
00:48:51,430 --> 00:48:54,650
>> Un tā ar šo sniedz jums tagad ir
iespēja p kopumu sešiem, kas būs

1090
00:48:54,650 --> 00:48:58,310
atkal iesaistīt īsteno savu
pareizrakstības pārbaudītājs, lasot 150000

1091
00:48:58,310 --> 00:49:01,050
Citiem vārdiem sakot, kā labāk uzglabāt, ka
ne vienmēr ir acīmredzama.

1092
00:49:01,050 --> 00:49:04,030
Un, lai gan es esmu vēlējusies, lai atrastu
Svētais Grāls, man nav

1093
00:49:04,030 --> 00:49:05,330
apgalvo, ka Trie ir.

1094
00:49:05,330 --> 00:49:09,810
Faktiski, hash tabulu var ļoti labi
izrādīties daudz efektīvāka.

1095
00:49:09,810 --> 00:49:10,830
Bet tie ir tikai -

1096
00:49:10,830 --> 00:49:14,620
tas ir tikai viens no dizains lēmumus
Jums būs jāveic.

1097
00:49:14,620 --> 00:49:18,920
>> Bet noslēguma pieņemsim 50, vai arī tā
sekundes, lai palūkoties, kādi slēpjas

1098
00:49:18,920 --> 00:49:22,190
priekšu nākamnedēļ, un pēc mēs pārejas
No šīs komandrindas

1099
00:49:22,190 --> 00:49:26,220
pasaulē, ja C programmas uz lietām tīmeklī
pamatā, un valodas, piemēram, PHP, un

1100
00:49:26,220 --> 00:49:30,350
JavaScript un internets pats par sevi,
protokolus, piemēram, HTTP, ko jūs esat

1101
00:49:30,350 --> 00:49:32,870
pašsaprotama gadiem
tagad, un drukāti biežāk kā reizi

1102
00:49:32,870 --> 00:49:34,440
diena, varbūt, vai redzējis.

1103
00:49:34,440 --> 00:49:37,420
Un mēs sāksim ar mizu atpakaļ
slāņi Kas ir internets.

1104
00:49:37,420 --> 00:49:40,650
Un kāda ir kods, kas
ir pamatā mūsdienu instrumenti.

1105
00:49:40,650 --> 00:49:43,230
Tātad 50 sekundes šajā teaser šeit.

1106
00:49:43,230 --> 00:49:46,570
Es jums Warriors par Net.

1107
00:49:46,570 --> 00:49:51,370
>> [VIDEO PLAYBACK]

1108
00:49:51,370 --> 00:49:56,764
>> -Viņš nāca ar ziņojumu.

1109
00:49:56,764 --> 00:50:00,687
Ar protokolu visiem viņa paša.

1110
00:50:00,687 --> 00:50:13,370

1111
00:50:13,370 --> 00:50:19,780
Viņš nāca pasaulē, nežēlīgi ugunsmūri,
uncaring maršrutētāji, un briesmas tālu

1112
00:50:19,780 --> 00:50:22,600
ļaunāks par nāvi.

1113
00:50:22,600 --> 00:50:23,590
Viņš ir ātrs.

1114
00:50:23,590 --> 00:50:25,300
Viņš ir spēcīgs.

1115
00:50:25,300 --> 00:50:27,700
Viņš ir TCPIP.

1116
00:50:27,700 --> 00:50:30,420
Un viņš dabūja savu adresi.

1117
00:50:30,420 --> 00:50:32,920

1118
00:50:32,920 --> 00:50:34,590
Karavīri Net.

1119
00:50:34,590 --> 00:50:35,290
>> [END VIDEO PLAYBACK]

1120
00:50:35,290 --> 00:50:38,070
>> SPEAKER 1: Tas ir kā internets
strādā no nākamās nedēļas.

1121
00:50:38,070 --> 00:50:40,406