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

2
00:00:11,860 --> 00:00:13,120
>> SPEAKER 1: Bine, deci ne-am întors.

3
00:00:13,120 --> 00:00:14,480
Bine ati venit la CS50.

4
00:00:14,480 --> 00:00:16,510
Acesta este sfârșitul de săptămâna de șapte.

5
00:00:16,510 --> 00:00:20,200
Astfel amintesc că ultima dată, am început
uita la ceva mai sofisticat

6
00:00:20,200 --> 00:00:21,100
structuri de date.

7
00:00:21,100 --> 00:00:25,110
Deoarece până acum, tot ce am avut într-adevăr
la dispoziția noastră a fost aceasta, o matrice.

8
00:00:25,110 --> 00:00:29,340
>> Dar, înainte de a renunța matrice ca nu
tot ce interesant, care într-adevăr

9
00:00:29,340 --> 00:00:33,570
de fapt este, ce sunt unele din
plusuri de aceste date simple

10
00:00:33,570 --> 00:00:34,560
Structura astfel acum?

11
00:00:34,560 --> 00:00:36,110
Ce e asta bine la?

12
00:00:36,110 --> 00:00:39,450
Măsura în care am văzut-o?

13
00:00:39,450 --> 00:00:42,540
Ce ai?

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

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

16
00:00:45,020 --> 00:00:45,395
>> SPEAKER 1: Ce e asta?

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

18
00:00:46,410 --> 00:00:47,000
>> SPEAKER 1: dimensiune fixă.

19
00:00:47,000 --> 00:00:51,260
OK, deci de ce este dimensiunea fixă ​​bine, deși?

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

21
00:00:53,180 --> 00:00:56,240
>> SPEAKER 1: OK, deci este eficient în
sensul că se poate aloca un

22
00:00:56,240 --> 00:01:00,070
sumă fixă ​​de spațiu, care, sperăm,
Este exact la fel de mult

23
00:01:00,070 --> 00:01:01,180
spațiu, după cum doriți.

24
00:01:01,180 --> 00:01:02,720
Astfel că ar putea fi absolut un plus.

25
00:01:02,720 --> 00:01:06,530
>> Ce este o altă parte dintr-o serie?

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

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

28
00:01:08,750 --> 00:01:09,550
>> SPEAKER 1: Toate - Îmi pare rău?

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

30
00:01:11,270 --> 00:01:13,620
>> SPEAKER 1: Toate cutiile din memorie
sau unul lângă celălalt.

31
00:01:13,620 --> 00:01:15,220
Și că este util - de ce?

32
00:01:15,220 --> 00:01:15,970
Asta e destul de adevărat.

33
00:01:15,970 --> 00:01:18,611
Dar cum putem exploata acest adevăr?

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

35
00:01:21,500 --> 00:01:24,490
>> SPEAKER 1: Exact, putem urmări
unde totul este doar prin cunoașterea

36
00:01:24,490 --> 00:01:28,560
o adresă, și anume adresa
Primul octet din segment de memorie.

37
00:01:28,560 --> 00:01:30,420
Sau în cazul șir,
adresa primului

38
00:01:30,420 --> 00:01:31,460
char în șir.

39
00:01:31,460 --> 00:01:33,330
Și de acolo, putem găsi
sfârșitul șirului.

40
00:01:33,330 --> 00:01:35,710
Putem găsi doilea element,
al treilea element, și așa mai departe.

41
00:01:35,710 --> 00:01:38,740
>> Și așa mod fantezist de a descrie ce
caracteristică este că matrice ne da

42
00:01:38,740 --> 00:01:40,020
acces aleator.

43
00:01:40,020 --> 00:01:44,330
Doar prin utilizarea paranteză
notație și un număr, puteți sări la

44
00:01:44,330 --> 00:01:48,070
un element specific în matrice
în timp constant, Big O

45
00:01:48,070 --> 00:01:49,810
de una, ca să spunem așa.

46
00:01:49,810 --> 00:01:51,080
>> Dar există unele dezavantaje.

47
00:01:51,080 --> 00:01:53,110
Ce un tablou nu face foarte usor?

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

49
00:01:55,810 --> 00:01:57,170
Ce nu e bine la?

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

51
00:01:58,810 --> 00:01:59,860
>> SPEAKER 1: Ce-i asta?

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

53
00:02:00,530 --> 00:02:01,460
>> SPEAKER 1: Extinderea în dimensiune.

54
00:02:01,460 --> 00:02:04,800
Astfel dezavantajele de matrice sunt
exact opusul a ceea ce

55
00:02:04,800 --> 00:02:05,540
Upsides sunt.

56
00:02:05,540 --> 00:02:07,610
Deci, unul din dezavantaje este
că este o dimensiune fixă.

57
00:02:07,610 --> 00:02:09,400
Deci, nu se poate dezvolta cu adevarat.

58
00:02:09,400 --> 00:02:13,510
Puteți realoca o bucată mai mare de
memorie, iar apoi mutați elemente vechi

59
00:02:13,510 --> 00:02:14,460
în noua matrice.

60
00:02:14,460 --> 00:02:18,060
Și apoi liber matrice vechi, pentru
exemplu, prin utilizarea malloc sau unul similar

61
00:02:18,060 --> 00:02:21,180
Funcția numit realloc, care
realoce memorie.

62
00:02:21,180 --> 00:02:25,490
>> Realloc, ca o parte, încearcă să-ți dea
memorie, care e lângă matrice

63
00:02:25,490 --> 00:02:26,610
pe care le au deja.

64
00:02:26,610 --> 00:02:28,740
Dar s-ar putea muta lucrurile
în jurul totul.

65
00:02:28,740 --> 00:02:30,710
Dar, în scurt, că e scump, nu?

66
00:02:30,710 --> 00:02:33,440
Pentru că, dacă aveți o bucată de memorie de
această dimensiune, dar vrei cu adevarat unul

67
00:02:33,440 --> 00:02:36,710
de această dimensiune, și doriți să păstrați
elementele originale, trebuie

68
00:02:36,710 --> 00:02:40,510
aproximativ un proces liniar de copiere timp
care trebuie să se întâmple de la

69
00:02:40,510 --> 00:02:41,900
matrice vechi la nou.

70
00:02:41,900 --> 00:02:44,630
Și realitatea se cere de operare
sistem nou și din nou și

71
00:02:44,630 --> 00:02:48,340
din nou pentru bucăți mari de memorie poate începe
să te coste ceva timp, de asemenea.

72
00:02:48,340 --> 00:02:52,250
Deci, este atât o binecuvântare și un blestem în
ascunde, faptul că aceste tablouri

73
00:02:52,250 --> 00:02:53,860
sunt de dimensiuni fixe.

74
00:02:53,860 --> 00:02:56,790
Dar, dacă vom introduce în schimb ceva
ca aceasta, pe care am numit-o legat

75
00:02:56,790 --> 00:03:00,580
lista, vom obține câteva upsides și
câteva dezavantaje aici.

76
00:03:00,580 --> 00:03:05,780
>> Deci, o lista inlantuita este pur și simplu de date
structură formată dintr-o structura C în acest

77
00:03:05,780 --> 00:03:09,850
caz, în cazul în care un struct, rechemare, este doar
un recipient pentru unul sau mai specifice

78
00:03:09,850 --> 00:03:11,100
tipuri de variabile.

79
00:03:11,100 --> 00:03:16,110
În acest caz, ceea ce face tipurile de date
par a fi interiorul struct care

80
00:03:16,110 --> 00:03:17,600
Ultima dată când am numit un nod?

81
00:03:17,600 --> 00:03:19,380
Fiecare dintre aceste dreptunghiuri este un nod.

82
00:03:19,380 --> 00:03:22,660
Și fiecare dintre dreptunghiuri mai mici
în interiorul acestuia este un tip de date.

83
00:03:22,660 --> 00:03:25,300
Ce tipuri am spus
ei au fost luni?

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

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

86
00:03:27,870 --> 00:03:30,721
>> SPEAKER 1: O variabilă și un pointer, sau
mai precis, un int, pentru n,

87
00:03:30,721 --> 00:03:32,180
și un indicator în partea de jos.

88
00:03:32,180 --> 00:03:35,360
Atât de cei care se întâmplă să fie 32 de biți, la
cel puțin pe un calculator ca aceasta CS50

89
00:03:35,360 --> 00:03:37,980
Aparat, și așa sunt
atras în mod egal în mărime.

90
00:03:37,980 --> 00:03:42,260
>> Deci, ce sunt folosind indicatorul
deși pentru aparent?

91
00:03:42,260 --> 00:03:47,690
De ce adăuga acest săgeată acum, când tablouri au fost
atât de frumos și curat și simplu?

92
00:03:47,690 --> 00:03:50,460
Ce este indicatorul face pentru
ne în fiecare dintre aceste noduri?

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

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

95
00:03:52,465 --> 00:03:54,120
Ea îți spune unde
următoarea este.

96
00:03:54,120 --> 00:03:57,350
Asa ca am un fel de analogia de
folosind un fir pentru a sorta de

97
00:03:57,350 --> 00:03:59,180
firul acestor noduri împreună.

98
00:03:59,180 --> 00:04:01,760
Și asta este exact ceea ce facem cu
indicii deoarece fiecare dintre acestea

99
00:04:01,760 --> 00:04:06,360
bucăți de memorie pot sau nu să fie
învecinate, spate în spate în spate

100
00:04:06,360 --> 00:04:09,500
interior de RAM, pentru că de fiecare dată când
apel malloc zis, da-mi destul de

101
00:04:09,500 --> 00:04:12,510
octeți pentru un nod nou, s-ar putea
fie aici, sau ar putea fi aici.

102
00:04:12,510 --> 00:04:13,120
Ar putea fi aici.

103
00:04:13,120 --> 00:04:13,730
Ar putea fi aici.

104
00:04:13,730 --> 00:04:14,640
Tu chiar nu știu.

105
00:04:14,640 --> 00:04:17,880
>> Dar folosind indicii în adresele
aceste noduri, puteți cusatura le

106
00:04:17,880 --> 00:04:22,370
împreună într-un mod care arată vizual
ca o lista, chiar dacă aceste lucruri sunt

107
00:04:22,370 --> 00:04:26,770
tot răspândit de-a lungul unul sau
două sau cu cele patru GB de memorie RAM

108
00:04:26,770 --> 00:04:28,760
în interiorul propriul computer.

109
00:04:28,760 --> 00:04:33,230
>> Deci dezavantaj, atunci, de
o lista inlantuita este ceea ce?

110
00:04:33,230 --> 00:04:34,670
Ce este un preț suntem
aparent de plată?

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

112
00:04:36,010 --> 00:04:36,920
>> SPEAKER 1: Mai mult spatiu, nu?

113
00:04:36,920 --> 00:04:39,340
Am, în acest caz, a dublat suma
de spațiu pentru că am plecat

114
00:04:39,340 --> 00:04:43,500
de la 32 de biți pentru fiecare nod, pentru fiecare
Int, asa ca acum 64 de biți pentru că trebuie să

115
00:04:43,500 --> 00:04:45,050
să păstreze în jurul un indicator la fel de bine.

116
00:04:45,050 --> 00:04:48,860
Ai mai multă eficiență dacă struct dvs.
este mai mare decât acest lucru simplu.

117
00:04:48,860 --> 00:04:52,020
Dacă aveți de fapt, un elev în interiorul
care este o pereche de siruri de caractere pentru

118
00:04:52,020 --> 00:04:55,430
numele și casa, poate, un număr de identificare,
poate că unele alte domenii cu totul.

119
00:04:55,430 --> 00:04:59,000
>> Deci, dacă aveți un struct suficient de mare,
atunci poate costul indicatorul este

120
00:04:59,000 --> 00:05:00,010
nu o astfel de afacere mare.

121
00:05:00,010 --> 00:05:03,570
Acesta este un pic de un caz colț în care
suntem stocarea unui astfel de simplu primitiv

122
00:05:03,570 --> 00:05:04,760
interiorul listei legat.

123
00:05:04,760 --> 00:05:05,790
Dar ideea este aceeași.

124
00:05:05,790 --> 00:05:08,230
Tu cu siguranta mai multe cheltuieli
memorie, dar vei primi

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

126
00:05:08,990 --> 00:05:12,280
Pentru că acum, dacă vreau să adăugați un element
la începutul acestei liste,

127
00:05:12,280 --> 00:05:14,340
Am să aloce un nou nod.

128
00:05:14,340 --> 00:05:17,180
Și trebuie să actualizeze doar cei
săgeți într-un fel de mișcare doar

129
00:05:17,180 --> 00:05:17,980
câteva indicii în jurul valorii.

130
00:05:17,980 --> 00:05:20,580
>> Dacă vreau să introduceți ceva în
mijlocul listei, eu nu trebuie să

131
00:05:20,580 --> 00:05:24,410
împinge toată lumea la o parte asa cum am facut in
trecut săptămâni cu voluntarii nostri, care

132
00:05:24,410 --> 00:05:25,700
a reprezentat o matrice.

133
00:05:25,700 --> 00:05:29,470
Eu pot aloca doar un nou nod și
apoi doar punctul de săgețile în

134
00:05:29,470 --> 00:05:32,290
direcții diferite, deoarece nu
trebuie să rămână în actuala

135
00:05:32,290 --> 00:05:35,670
memorie o linie adevarat ca am desenat
l aici pe ecran.

136
00:05:35,670 --> 00:05:38,400
>> Și apoi în cele din urmă, în cazul în care doriți să inserați
ceva la sfârșitul listei, e

137
00:05:38,400 --> 00:05:39,210
chiar mai ușor.

138
00:05:39,210 --> 00:05:43,320
Aceasta este un fel de notație arbitrare,
dar indicatorul 34, să ia o presupunere.

139
00:05:43,320 --> 00:05:46,710
Care este valoarea indicatorului sa cea
probabil fel trase de ca un vechi

140
00:05:46,710 --> 00:05:47,700
antena școală acolo?

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

142
00:05:48,920 --> 00:05:49,900
>> SPEAKER 1: Este, probabil, nul.

143
00:05:49,900 --> 00:05:52,710
Și într-adevăr că este un autor
reprezentarea nul.

144
00:05:52,710 --> 00:05:56,310
Și este nul, deoarece absolut
Trebuie să știu unde capătul unui legat

145
00:05:56,310 --> 00:06:00,050
Lista este, ca nu cumva să vă păstrați în urma și
urma și ca urmare a acestor săgeți

146
00:06:00,050 --> 00:06:01,170
la o valoare de gunoi.

147
00:06:01,170 --> 00:06:06,230
Deci, null va însemna că nu există nici o
mai multe noduri la dreptul de numărul 34,

148
00:06:06,230 --> 00:06:07,200
în acest caz.

149
00:06:07,200 --> 00:06:10,270
>> Deci, noi propunem ca putem pune în aplicare
acest nod în cod.

150
00:06:10,270 --> 00:06:12,130
Și am văzut acest tip
de sintaxă înainte.

151
00:06:12,130 --> 00:06:15,090
Typedef definește doar un nou tip de
ne, ne dă un sinonim cum ar fi

152
00:06:15,090 --> 00:06:17,100
șir a fost pentru char *.

153
00:06:17,100 --> 00:06:21,030
În acest caz, o să ne dea
notația prescurtată, astfel încât nodul struct

154
00:06:21,030 --> 00:06:24,010
pot în schimb să fie scris doar ca
nod, care este mult mai curat.

155
00:06:24,010 --> 00:06:25,360
Este mult mai puțin detaliat.

156
00:06:25,360 --> 00:06:30,080
>> În interiorul unui nod este aparent un int
numit n, iar apoi un nod struct *

157
00:06:30,080 --> 00:06:34,670
ceea ce înseamnă exact ceea ce ne-am dorit
săgeți pentru a înțelege, un pointer la un alt

158
00:06:34,670 --> 00:06:36,940
nod de exact același tip de date.

159
00:06:36,940 --> 00:06:40,300
Și eu propun ca am putea pune în aplicare o
funcția de căutare cum ar fi aceasta, care, la

160
00:06:40,300 --> 00:06:41,890
prima vedere ar putea părea
un pic mai complex.

161
00:06:41,890 --> 00:06:43,330
Dar haideți să-l în context vedea.

162
00:06:43,330 --> 00:06:45,480
>> Lasă-mă să merg pe la aparatul aici.

163
00:06:45,480 --> 00:06:48,460
Lasă-mă să deschid un fișier denumit
Lista de zero punct ore.

164
00:06:48,460 --> 00:06:53,950
Și care conține numai definiția ne
doar văzut acum un moment pentru aceste date

165
00:06:53,950 --> 00:06:55,390
tip numit un nod.

166
00:06:55,390 --> 00:06:57,350
Deci, ne-am pus că într-un h Fisier punct.

167
00:06:57,350 --> 00:07:01,430
>> Și ca o parte, chiar dacă această
Programul pe care esti pe cale de a vedea este

168
00:07:01,430 --> 00:07:05,410
Nu toate că complex, este într-adevăr
convenție atunci când scrieți un program pentru

169
00:07:05,410 --> 00:07:10,270
pune lucrurile cum ar fi tipurile de date, pentru a trage
constante, uneori, în interiorul dvs.

170
00:07:10,270 --> 00:07:13,210
fișier antet și nu neapărat în
fișierul C, cu siguranță atunci când vă

171
00:07:13,210 --> 00:07:17,370
Programele obține mai mari și mai mari, astfel încât
știi unde să te uiți atât pentru

172
00:07:17,370 --> 00:07:20,840
Documentația în unele cazuri, sau
pentru elementele de bază, cum ar fi acest lucru,

173
00:07:20,840 --> 00:07:22,360
definiție de un anumit tip.

174
00:07:22,360 --> 00:07:25,680
>> Dacă am deschide lista de zero puncte
C, observa câteva lucruri.

175
00:07:25,680 --> 00:07:29,090
Acesta include câteva fișiere antet, cele mai multe
din care am văzut înainte.

176
00:07:29,090 --> 00:07:31,980
Acesta include propriul fișier antet.

177
00:07:31,980 --> 00:07:35,200
>> Și, ca o paranteză, de ce e dublu
citate aici, spre deosebire de unghiul

178
00:07:35,200 --> 00:07:38,340
paranteze pe linia care
Am subliniat acolo?

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

180
00:07:39,180 --> 00:07:40,460
>> SPEAKER 1: Da, așa este un fișier local.

181
00:07:40,460 --> 00:07:44,300
Deci, dacă este un fișier local de propria dvs. aici
pe linia 15, de exemplu, să utilizați

182
00:07:44,300 --> 00:07:46,570
ghilimelele duble în loc
dintre paranteze.

183
00:07:46,570 --> 00:07:48,270
>> Acum, acest lucru este un fel de interesant.

184
00:07:48,270 --> 00:07:51,830
Observați că am declarat-o la nivel mondial
variabilă în acest program de pe linia 18

185
00:07:51,830 --> 00:07:55,910
denumit în primul rând, ideea fiind acest lucru este
O să fie un pointer la primul

186
00:07:55,910 --> 00:07:59,190
nod în lista mea legată, și am
inițializat la null, pentru că am

187
00:07:59,190 --> 00:08:02,310
Nu alocat nici un real
noduri încă.

188
00:08:02,310 --> 00:08:07,570
>> Deci, aceasta reprezintă, pictural, ceea ce
văzut acum un moment în imagine ca

189
00:08:07,570 --> 00:08:10,090
că indicatorul pe departe
in partea stanga.

190
00:08:10,090 --> 00:08:12,260
Deci, chiar acum, ca indicatorul
nu are o săgeată.

191
00:08:12,260 --> 00:08:14,590
Este în schimb, este doar nul.

192
00:08:14,590 --> 00:08:17,880
Dar aceasta reprezintă ceea ce va fi
adresa primului real

193
00:08:17,880 --> 00:08:19,480
nod în această listă.

194
00:08:19,480 --> 00:08:22,120
Așa că l-am implementat este un nivel global
pentru că, după cum veți vedea, toate acestea

195
00:08:22,120 --> 00:08:25,310
Programul are în viață este punerea în aplicare a
o listă legat de mine.

196
00:08:25,310 --> 00:08:27,050
>> Acum, am câteva prototipuri aici.

197
00:08:27,050 --> 00:08:31,190
Am decis să pună în aplicare caracteristici cum ar fi
ștergere, inserare, căutare, și

198
00:08:31,190 --> 00:08:31,740
traversal -

199
00:08:31,740 --> 00:08:35,210
ultimul fiind doar mers pe jos peste
lista, imprimarea elementele sale.

200
00:08:35,210 --> 00:08:36,750
Și acum, aici e rutina mea principală.

201
00:08:36,750 --> 00:08:39,890
Și nu vom petrece prea mult timp pe
acestea, deoarece aceasta este un fel de, sperăm

202
00:08:39,890 --> 00:08:41,780
pălărie veche de acum.

203
00:08:41,780 --> 00:08:45,370
>> Am de gând să fac următoarele,
în timp ce utilizatorul cooperează.

204
00:08:45,370 --> 00:08:47,300
Deci unul, am de gând să imprima
în acest meniu.

205
00:08:47,300 --> 00:08:49,420
Și l-am formatat ca
curat ca am putut.

206
00:08:49,420 --> 00:08:52,240
Dacă utilizatorul tastează într-o singură, înseamnă că
care doriți să o ștergeți ceva.

207
00:08:52,240 --> 00:08:54,560
Dacă utilizatorul tastează în două, înseamnă că
care doriți să îl inserați ceva.

208
00:08:54,560 --> 00:08:55,930
Și așa mai departe.

209
00:08:55,930 --> 00:08:58,270
Am de gând să solicite apoi
apoi pentru o comandă.

210
00:08:58,270 --> 00:08:59,300
Și apoi am de gând să utilizeze getint.

211
00:08:59,300 --> 00:09:02,790
>> Deci, aceasta este o foarte simplu de meniuri
interfață în cazul în care trebuie doar să tastați

212
00:09:02,790 --> 00:09:05,270
un număr de cartografiere la o
acestor comenzi.

213
00:09:05,270 --> 00:09:08,730
Și acum am un comutator frumos curat
Declarația care va porni

214
00:09:08,730 --> 00:09:10,090
indiferent de utilizatorul tastat inch

215
00:09:10,090 --> 00:09:12,180
Și dacă au scris unul, voi
apel șterge și rupe.

216
00:09:12,180 --> 00:09:14,380
În cazul în care tastat doi, voi
apel introduce și rupe.

217
00:09:14,380 --> 00:09:16,490
>> Și acum observați am pus fiecare
dintre acestea pe aceeași linie.

218
00:09:16,490 --> 00:09:18,360
Aceasta este doar o decizie stilistice.

219
00:09:18,360 --> 00:09:20,210
De obicei am văzut ceva
ca aceasta.

220
00:09:20,210 --> 00:09:23,260
Dar am decis, sincer, programul meu
privit mai ușor de citit, deoarece

221
00:09:23,260 --> 00:09:25,980
a fost doar patru cazuri la
doar lista aceasta.

222
00:09:25,980 --> 00:09:28,360
Utilizarea total legitim de stil.

223
00:09:28,360 --> 00:09:31,480
Și am de gând să fac acest lucru, atât timp cât
utilizatorul nu a tastat la zero, pe care am

224
00:09:31,480 --> 00:09:33,910
a decis va însemna ca doresc sa renunte.

225
00:09:33,910 --> 00:09:36,630
>> Deci, acum observa ce am
de gând să faci aici.

226
00:09:36,630 --> 00:09:38,650
Am de gând să elibereze lista aparent.

227
00:09:38,650 --> 00:09:40,230
Dar mai mult pe faptul că într-o clipă.

228
00:09:40,230 --> 00:09:41,640
Să facem mai întâi acest program.

229
00:09:41,640 --> 00:09:45,250
Deci, lasă-mă să fac un terminal de mare
fereastră, punct lista slash 0.

230
00:09:45,250 --> 00:09:49,510
Am de gând să merg mai departe și se introduce prin
dactilografiere două, un număr asemănător 50, iar acum

231
00:09:49,510 --> 00:09:51,590
veți vedea lista este acum de 50.

232
00:09:51,590 --> 00:09:53,380
Și textul meu doar derulat un pic.

233
00:09:53,380 --> 00:09:55,940
Deci, acum observa lista conține
numărul 50.

234
00:09:55,940 --> 00:09:58,220
>> Să facem o altă introduce prin luarea două.

235
00:09:58,220 --> 00:10:01,630
Să tastați în numărul ca unul.

236
00:10:01,630 --> 00:10:03,940
Lista este acum unul, urmată de 50.

237
00:10:03,940 --> 00:10:06,020
Deci, aceasta este doar o reprezentare textuală
a listei.

238
00:10:06,020 --> 00:10:10,550
Și să introduceți un număr mai ca
numărul 42, care este, sperăm

239
00:10:10,550 --> 00:10:14,620
O să ajung la mijloc, deoarece
acest program, în special felul acesta

240
00:10:14,620 --> 00:10:16,320
elemente ca le introduce.

241
00:10:16,320 --> 00:10:17,220
Deci nu îl avem.

242
00:10:17,220 --> 00:10:20,730
Programul de super-simplu care ar putea
absolut s-au folosit o matrice, dar eu

243
00:10:20,730 --> 00:10:23,280
se întâmplă să fie folosind o listă înlănțuită
doar așa că am putea dinamic

244
00:10:23,280 --> 00:10:24,610
cresc și psihiatru.

245
00:10:24,610 --> 00:10:28,470
>> Deci, haideți să aruncăm o privire de căutare, dacă am
rulați comanda trei, vreau să căutați

246
00:10:28,470 --> 00:10:31,040
pentru, să zicem, numărul 43.

247
00:10:31,040 --> 00:10:34,190
Și nimic nu a fost aparent gasit,
pentru că m-am întors nici un răspuns.

248
00:10:34,190 --> 00:10:35,010
Deci, hai sa facem acest lucru din nou.

249
00:10:35,010 --> 00:10:35,690
Caută.

250
00:10:35,690 --> 00:10:39,520
Să căutare pentru 50, sau mai degrabă căutare
pentru 42, care are o bună

251
00:10:39,520 --> 00:10:40,850
lipsită de sens subtil.

252
00:10:40,850 --> 00:10:42,610
Și am găsit sensul vieții acolo.

253
00:10:42,610 --> 00:10:44,990
Numărul 42, dacă nu știi
de referință, pe Google.

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

255
00:10:45,350 --> 00:10:47,130
Deci, ceea ce a facut acest program pentru mine?

256
00:10:47,130 --> 00:10:50,660
Este pur și simplu mi-a permis pentru a insera astfel
departe și de căutare pentru elemente.

257
00:10:50,660 --> 00:10:53,650
>> Să repede înainte, apoi, să
că funcția am aruncat o privire

258
00:10:53,650 --> 00:10:55,360
, luni, ca un teaser.

259
00:10:55,360 --> 00:10:59,620
Deci această funcție, eu susțin, căutările pentru
un element din lista de prima

260
00:10:59,620 --> 00:11:03,830
unul, în care utilizatorul și apoi apel
Getint pentru a obține un int real

261
00:11:03,830 --> 00:11:05,060
pe care doriți să căutați.

262
00:11:05,060 --> 00:11:06,460
>> Apoi observa acest lucru.

263
00:11:06,460 --> 00:11:10,690
Am de gând să creeze o variabilă temporară
în linie 188 numit pointer -

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

265
00:11:11,270 --> 00:11:12,440
ar fi numit-o nimic.

266
00:11:12,440 --> 00:11:16,140
Și este un pointer la un nod
pentru că am spus nod * acolo.

267
00:11:16,140 --> 00:11:19,900
Și eu inițializare să fie egal cu
în primul rând, astfel că am efectiv am mea

268
00:11:19,900 --> 00:11:22,860
deget, ca să spunem așa, pe foarte
primul element al listei.

269
00:11:22,860 --> 00:11:27,460
Deci, dacă mâna mea aici este PTR am
arătând în același lucru pe care în primul rând

270
00:11:27,460 --> 00:11:28,670
este îndreptat la.

271
00:11:28,670 --> 00:11:31,430
>> Deci, acum din nou în cod,
ceea ce se întâmplă în continuare -

272
00:11:31,430 --> 00:11:35,070
aceasta este o paradigmă comună atunci când iterarea
peste o structură ca o

273
00:11:35,070 --> 00:11:35,970
Lista legate.

274
00:11:35,970 --> 00:11:40,410
Am de gând să fac următoarele în timp ce
indicatorul nu este egal cu NULL, de aceea în timp ce

275
00:11:40,410 --> 00:11:47,530
degetul meu nu este îndreptat la un nul
valoare, dacă sageata n este egal cu n.

276
00:11:47,530 --> 00:11:52,290
Vom observa în primul rând că n este ceea ce
tastat în pe GetInts utilizator numesc aici.

277
00:11:52,290 --> 00:11:54,280
>> Și sageata n ce înseamnă?

278
00:11:54,280 --> 00:11:59,020
Ei bine, dacă ne întoarcem la imaginea de aici,
dacă am un deget îndreptat la

279
00:11:59,020 --> 00:12:02,960
ca primul nod care conține nouă,
săgeata în esență, înseamnă a merge la care

280
00:12:02,960 --> 00:12:08,860
nod și apuca valoarea la locația n,
în acest caz, câmpul de date numit n.

281
00:12:08,860 --> 00:12:14,120
>> Ca o paranteza - și am văzut acest lucru un cuplu
de săptămâni în urmă, când cineva a întrebat -

282
00:12:14,120 --> 00:12:18,840
această sintaxă este nouă, dar nu
ne da puteri pe care le

283
00:12:18,840 --> 00:12:20,040
nu au deja.

284
00:12:20,040 --> 00:12:25,325
Care a fost această frază echivalentă cu ajutorul
punct notație și stele, un cuplu

285
00:12:25,325 --> 00:12:29,490
de săptămâni în urmă, când am detasat-o inapoi
acest strat un pic prematur?

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

287
00:12:31,780 --> 00:12:38,880
>> SPEAKER 1: Exact, era stele, și
apoi a fost stea dot n, cu

288
00:12:38,880 --> 00:12:41,930
paranteze aici, care arată,
sincer, cred că o mulțime

289
00:12:41,930 --> 00:12:43,320
mai criptic de citit.

290
00:12:43,320 --> 00:12:46,270
Dar indicatorul stele, ca întotdeauna,
înseamnă du-te acolo.

291
00:12:46,270 --> 00:12:49,090
Și odată ce ești acolo, ce date
câmp vrei să acceseze?

292
00:12:49,090 --> 00:12:52,730
Ei bine, utilizați notația punct de acces
un câmp structs de date, și eu

293
00:12:52,730 --> 00:12:54,140
în mod special vreau n.

294
00:12:54,140 --> 00:12:56,240
>> Sincer, aș spune acest lucru
este doar mai greu de citit.

295
00:12:56,240 --> 00:12:58,080
Este mai greu să-și amintească unde
face paranteze merge,

296
00:12:58,080 --> 00:12:59,030
stele, și toate astea.

297
00:12:59,030 --> 00:13:02,150
Deci, lumea a adoptat unele sintactic
zahăr, ca să spunem așa.

298
00:13:02,150 --> 00:13:04,740
Doar un mod sexy de a spune,
aceasta este echivalent, și

299
00:13:04,740 --> 00:13:05,970
probabil, mai mult intuitiv.

300
00:13:05,970 --> 00:13:09,600
Dacă indicatorul este într-adevăr un pointer,
săgeată mijloace de notare du-te acolo și de a găsi

301
00:13:09,600 --> 00:13:11,890
domeniul în acest caz numit n.

302
00:13:11,890 --> 00:13:13,660
>> Deci, dacă am găsi, observa ceea ce fac.

303
00:13:13,660 --> 00:13:17,430
Eu pur si simplu imprima, am găsit la suta I,
conectarea în valoare pentru că Int.

304
00:13:17,430 --> 00:13:20,730
Eu numesc somn timp de o secundă doar la fel
de pauză lucrurile de pe ecran pentru a

305
00:13:20,730 --> 00:13:22,900
da utilizatorului un al doilea pentru a absorbi
ceea ce sa întâmplat.

306
00:13:22,900 --> 00:13:24,290
Și apoi m-am rupe.

307
00:13:24,290 --> 00:13:26,330
În caz contrar, ce să fac?

308
00:13:26,330 --> 00:13:30,960
Am actualiza indicatorul la egal
săgeata de lângă indicator.

309
00:13:30,960 --> 00:13:35,840
>> Deci, doar pentru a fi clar, acest lucru înseamnă du-te
acolo, cu ajutorul meu de notație de școală veche.

310
00:13:35,840 --> 00:13:39,580
Deci, acest lucru înseamnă doar pentru a merge la orice
te îndreptat la, care, în foarte

311
00:13:39,580 --> 00:13:43,660
Primul caz este arăt eu la
struct cu nouă în ea.

312
00:13:43,660 --> 00:13:44,510
Așa că m-am dus acolo.

313
00:13:44,510 --> 00:13:47,880
Și apoi notația punct înseamnă,
obține valoarea la următorul.

314
00:13:47,880 --> 00:13:50,470
>> Dar valoarea, chiar dacă este desenat
ca o îngustă, este doar un număr.

315
00:13:50,470 --> 00:13:51,720
Este o adresă numerică.

316
00:13:51,720 --> 00:13:55,670
Deci, aceasta linie de cod, dacă
scris ca aceasta, mai criptic

317
00:13:55,670 --> 00:14:00,190
fel, sau ca aceasta, puțin mai
mod intuitiv, înseamnă doar mișca mâna mea

318
00:14:00,190 --> 00:14:03,460
de la primul nod la următoarea,
și apoi următoarea, și apoi

319
00:14:03,460 --> 00:14:05,320
următorul, și așa mai departe.

320
00:14:05,320 --> 00:14:09,920
>> Deci, nu vom insista pe de altă parte
implementari de insera și șterge

321
00:14:09,920 --> 00:14:14,030
și traversal, primele două
care sunt destul de implicat.

322
00:14:14,030 --> 00:14:17,010
Și cred că este destul de ușor pentru a obține
a pierdut atunci când o fac verbal.

323
00:14:17,010 --> 00:14:19,890
Dar ce putem face aici este
încearcă să determine modul în care

324
00:14:19,890 --> 00:14:21,640
cel mai bun de a face acest lucru vizual.

325
00:14:21,640 --> 00:14:24,800
Pentru că eu propun ca, dacă ne
doriți să inserați elemente în acest

326
00:14:24,800 --> 00:14:26,680
Lista existente, care
are cinci elemente -

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

328
00:14:29,530 --> 00:14:33,300
dacă am fost de gând să pună în aplicare acest lucru în
cod, trebuie să ia în considerare modul în care pentru a merge

329
00:14:33,300 --> 00:14:34,160
despre a face acest lucru.

330
00:14:34,160 --> 00:14:37,720
>> Și mi-ar propune luarea de măsuri pentru copii
prin care, în acest caz Adică, ce sunt

331
00:14:37,720 --> 00:14:41,090
scenariile posibile pe care le
s-ar putea întâlni, în general?

332
00:14:41,090 --> 00:14:44,120
La punerea în aplicare introduce pentru un legat
lista, acest lucru se întâmplă doar pentru a fi o

333
00:14:44,120 --> 00:14:46,090
exemplu specific de dimensiunea cinci.

334
00:14:46,090 --> 00:14:50,420
Ei bine, dacă doriți să introduceți un număr,
ca spun numărul unu, și

335
00:14:50,420 --> 00:14:53,380
menținerea ordinii sortate, unde
evident, nu numărul unu trebuie să

336
00:14:53,380 --> 00:14:55,686
du-te în acest exemplu specific?

337
00:14:55,686 --> 00:14:56,840
Ca la început.

338
00:14:56,840 --> 00:15:00,030
>> Dar ceea ce este interesant este faptul că
dacă doriți să introduceți o în acest

339
00:15:00,030 --> 00:15:04,100
lista, ceea ce indicatorul nevoi speciale
să fie actualizate aparent?

340
00:15:04,100 --> 00:15:04,610
În primul rând.

341
00:15:04,610 --> 00:15:07,830
Deci, aș spune, acesta este primul caz
pe care am putea dori să ia în considerare, un

342
00:15:07,830 --> 00:15:11,140
scenariu care implică introducerea la
la începutul listei.

343
00:15:11,140 --> 00:15:15,400
>> Să smulge poate un fel de ușor sau chiar
caz mai usor, relativ vorbind.

344
00:15:15,400 --> 00:15:18,110
Să presupunem că doriți să introduceți
Numărul 35 în ordine sortată.

345
00:15:18,110 --> 00:15:20,600
Este, evident, aparține acolo.

346
00:15:20,600 --> 00:15:25,320
Deci, ceea ce, evident, indicatorul se va
trebuie să fie actualizate în acest scenariu?

347
00:15:25,320 --> 00:15:30,060
Indicatorul 34 a devenit nu null
dar adresa struct

348
00:15:30,060 --> 00:15:31,800
care conține numărul 35.

349
00:15:31,800 --> 00:15:32,750
Așa că e cazul doi.

350
00:15:32,750 --> 00:15:36,190
Deci, deja, eu sunt un fel de cuantificarea
cât de mult de lucru trebuie să fac aici.

351
00:15:36,190 --> 00:15:39,880
>> Și, în sfârșit, în cazul mijloc evident este
Într-adevăr, în mijloc, dacă vreau să

352
00:15:39,880 --> 00:15:45,870
introduce ceva de genul spun 23, care merge
între 23 și 26, dar

353
00:15:45,870 --> 00:15:48,680
acum lucrurile devin un pic mai mult
implicat pentru că ceea ce

354
00:15:48,680 --> 00:15:52,800
indicii trebuie să fie schimbat?

355
00:15:52,800 --> 00:15:56,680
Deci, 22, evident, trebuie să fie schimbat
pentru că el nu mai poate indica 26.

356
00:15:56,680 --> 00:16:00,320
El are nevoie pentru a indica noul nod care
Va trebui să aloce de apel

357
00:16:00,320 --> 00:16:01,770
malloc sau ceva echivalent.

358
00:16:01,770 --> 00:16:05,990
>> Dar apoi am nevoie, de asemenea, că noul nod, 23
în acest caz, să aibă pe indicatorul acesteia

359
00:16:05,990 --> 00:16:07,870
arătând la cine?

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

361
00:16:08,560 --> 00:16:10,380
Și acolo va fi o
ordinea de operațiuni aici.

362
00:16:10,380 --> 00:16:13,410
Pentru că dacă fac acest lucru prostește, și eu
de exemplu încep de la începutul

363
00:16:13,410 --> 00:16:16,040
lista, iar scopul meu este de a introduce 23.

364
00:16:16,040 --> 00:16:18,610
Și am verifica, îi aparține
aici, aproape nouă?

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

366
00:16:18,950 --> 00:16:20,670
Îi aparține aici, alături de 17?

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

368
00:16:20,940 --> 00:16:22,530
Are aparține aici alături de 22?

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

370
00:16:23,300 --> 00:16:26,400
>> Acum, dacă eu sunt o prostie aici, și nu
gândire acest lucru prin intermediul, am putea

371
00:16:26,400 --> 00:16:28,320
aloca noua mea nod de 23.

372
00:16:28,320 --> 00:16:32,080
S-ar putea actualiza indicatorul de
nodul numit 22, arătând

373
00:16:32,080 --> 00:16:33,080
se la noul nod.

374
00:16:33,080 --> 00:16:36,140
Și atunci ce trebuie să actualizeze
indicatorul noul nod de a fi?

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

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

377
00:16:38,385 --> 00:16:39,710
Arătând la 26.

378
00:16:39,710 --> 00:16:45,590
Dar, la naiba, dacă nu au actualizat deja
Indicatorul 22 de la punctul de la acest tip, și

379
00:16:45,590 --> 00:16:48,260
acum am orfani, restul
a listei, ca să spunem așa.

380
00:16:48,260 --> 00:16:52,140
Deci, ordinea operațiunilor aici
va fi important.

381
00:16:52,140 --> 00:16:55,100
>> Pentru a face acest lucru am putut fura,
spune, șase voluntari.

382
00:16:55,100 --> 00:16:57,650
Și să vedem dacă nu putem face acest lucru
vizual în loc de cod-înțelept.

383
00:16:57,650 --> 00:16:59,330
Si ne-am unele stres minunat
bile pentru tine azi.

384
00:16:59,330 --> 00:17:02,510
OK, ce zici de unul, doi, în
inapoi - la sfârșitul acolo.

385
00:17:02,510 --> 00:17:04,530
trei, patru, amândoi
Tipii de pe final.

386
00:17:04,530 --> 00:17:05,579
Și cinci, șase.

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

388
00:17:05,839 --> 00:17:06,450
Cinci și șase.

389
00:17:06,450 --> 00:17:08,390
Bine și vom veni
cu voi data viitoare.

390
00:17:08,390 --> 00:17:09,640
În regulă, haide sus.

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

392
00:17:12,010 --> 00:17:14,819
>> Bine, dacă tot ești aici în primul rând,
doriți să fie un dur

393
00:17:14,819 --> 00:17:16,119
în Google Glass aici?

394
00:17:16,119 --> 00:17:19,075
În regulă, deci, bine, sticla,
înregistra un videoclip.

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

396
00:17:22,720 --> 00:17:24,589
OK, tu esti bine să plec.

397
00:17:24,589 --> 00:17:27,950
>> În regulă, deci, dacă voi putea veni peste
aici, am pregătit în avans

398
00:17:27,950 --> 00:17:30,110
unele numere.

399
00:17:30,110 --> 00:17:31,240
Bine, vino aici.

400
00:17:31,240 --> 00:17:33,440
Și de ce nu te duci un pic
în continuare în acest fel.

401
00:17:33,440 --> 00:17:35,520
Și să vedem, care e numele tău,
cu sticlă Google?

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

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

404
00:17:36,230 --> 00:17:38,380
Bine, Ben, va fi primul, literalmente.

405
00:17:38,380 --> 00:17:40,580
Așa că am de gând să vă trimită
la sfârșitul etapei.

406
00:17:40,580 --> 00:17:41,670
Bine, și numele tău?

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

408
00:17:41,990 --> 00:17:44,530
>> SPEAKER 1: Jason, OK veți
fie numărul nouă.

409
00:17:44,530 --> 00:17:46,700
Deci, dacă doriți să urmați Ben în acest fel.

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

411
00:17:47,010 --> 00:17:49,630
>> SPEAKER 1: Jill, ai de gând să fie
17, care, dacă am făcut acest lucru mai mult

412
00:17:49,630 --> 00:17:51,260
inteligent, mi-ar fi
început la celălalt capăt.

413
00:17:51,260 --> 00:17:52,370
Tu du-te pe acolo.

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

415
00:17:53,030 --> 00:17:53,670
Și tu ești?

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

417
00:17:53,980 --> 00:17:56,130
>> SPEAKER 1: Maria, vei fi 22.

418
00:17:56,130 --> 00:17:58,420
Si numele tau este?

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

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

421
00:18:00,100 --> 00:18:00,740
Și apoi în cele din urmă.

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

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

424
00:18:02,670 --> 00:18:03,920
Deci, vino aici.

425
00:18:03,920 --> 00:18:06,360
>> În regulă, atât de perfect sortate
comanda deja.

426
00:18:06,360 --> 00:18:09,600
Și să mergem mai departe și de a face acest lucru
astfel încât să putem într-adevăr -

427
00:18:09,600 --> 00:18:11,720
Ben esti doar un fel de a privi
afară, în nicăieri acolo.

428
00:18:11,720 --> 00:18:15,670
OK, deci să mergem mai departe și descrie acest
folosind arme, la fel ca am fost, mai exact,

429
00:18:15,670 --> 00:18:16,250
ce se întâmplă.

430
00:18:16,250 --> 00:18:19,540
Deci, mergeți mai departe și să vă o
picior sau două dintre voi.

431
00:18:19,540 --> 00:18:22,900
Și mergeți mai departe și punctul cu o singură mână a
oricine ar trebui să fie îndreptat la

432
00:18:22,900 --> 00:18:23,470
pe baza acestei.

433
00:18:23,470 --> 00:18:25,890
Și dacă ești nulă doar punctul
drept în jos la podea.

434
00:18:25,890 --> 00:18:27,690
OK, asa de bine.

435
00:18:27,690 --> 00:18:32,290
>> Deci, acum avem o listă legat, și lasă-mă să
propune ca voi juca rolul de

436
00:18:32,290 --> 00:18:35,110
PTR, asa ca nu va deranja
transportă acest jurul.

437
00:18:35,110 --> 00:18:37,830
Și apoi - Convenția prost pe cineva -
puteți apela acest tot ce vrei -

438
00:18:37,830 --> 00:18:39,800
indicatorul predecesorul, indicatorul pred -

439
00:18:39,800 --> 00:18:43,930
e doar porecla am dat în
Codul nostru de probă la mâna stângă.

440
00:18:43,930 --> 00:18:47,240
De altă parte, care va fi păstrarea
urmări de cine este cine în

441
00:18:47,240 --> 00:18:48,400
următoarele scenarii.

442
00:18:48,400 --> 00:18:52,390
>> Deci presupun, în primul rând, vreau să smulge
că primul exemplu de inserare, spune

443
00:18:52,390 --> 00:18:54,330
20, în lista.

444
00:18:54,330 --> 00:18:57,160
Așa că am de gând să nevoie de cineva pentru a
întruchipează numărul 20 pentru noi.

445
00:18:57,160 --> 00:18:58,950
Așa că am nevoie de cineva malloc
din public.

446
00:18:58,950 --> 00:18:59,380
Hai sus.

447
00:18:59,380 --> 00:19:00,340
Care e numele tău?

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

449
00:19:01,300 --> 00:19:05,270
>> SPEAKER 1: Brian, bine, astfel încât să
este nodul care conține 20.

450
00:19:05,270 --> 00:19:06,810
Bine, vino aici.

451
00:19:06,810 --> 00:19:10,025
Și, evident, în cazul în care
face parte Brian?

452
00:19:10,025 --> 00:19:12,190
Deci, în mijlocul - de fapt,
așteptați un minut.

453
00:19:12,190 --> 00:19:13,420
Facem asta de ordine.

454
00:19:13,420 --> 00:19:17,170
Vom face acest lucru mult mai greu
decât aceasta trebuie să fie la început.

455
00:19:17,170 --> 00:19:21,210
OK, vom liber Brian
și realloc Brian ca cinci.

456
00:19:21,210 --> 00:19:23,680
>> OK, deci acum ne-o dorim pentru a insera
Brian ca cinci.

457
00:19:23,680 --> 00:19:25,960
Deci, vino aici lângă
Ben pentru doar o clipă.

458
00:19:25,960 --> 00:19:28,250
Și tu poți spune probabil
în cazul în care această poveste se întâmplă.

459
00:19:28,250 --> 00:19:30,500
Dar să ne gândim cu atenție la
ordinea operațiilor.

460
00:19:30,500 --> 00:19:32,880
Și este tocmai această vizuală
care se va alinia

461
00:19:32,880 --> 00:19:34,080
cu exemplul de cod.

462
00:19:34,080 --> 00:19:40,120
Deci, aici am PTR îndreptat inițial
nu la Ben, per se, ci la orice

463
00:19:40,120 --> 00:19:43,245
apreciază el conține, care în acest caz
este - ceea ce este numele tau?

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

465
00:19:43,670 --> 00:19:47,350
>> SPEAKER 1: Jason, astfel încât atât Ben și eu sunt
arătând spre Jason în acest moment.

466
00:19:47,350 --> 00:19:49,700
Deci, acum trebuie să determine,
care face parte Brian?

467
00:19:49,700 --> 00:19:53,500
Așa că singurul lucru pe care am acces la
acum este n elementul lui de date.

468
00:19:53,500 --> 00:19:58,280
Așa că am de gând să verifice, este
Brian mai puțin de Jason?

469
00:19:58,280 --> 00:19:59,770
Răspunsul este adevărat.

470
00:19:59,770 --> 00:20:03,680
>> Deci, ce acum trebuie să se întâmple,
în ordinea corectă?

471
00:20:03,680 --> 00:20:07,120
Am nevoie pentru a actualiza cât de multe indicii
În total, în această poveste?

472
00:20:07,120 --> 00:20:10,720
În cazul în care mâna mea este încă îndreptat la
Jason, și mâna ta - dacă doriți să

473
00:20:10,720 --> 00:20:12,930
pune mâna cum ar fi, un fel de, I
Nu știu, un semn de întrebare.

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

475
00:20:14,070 --> 00:20:15,670
>> Bine, deci aveți
câțiva candidați.

476
00:20:15,670 --> 00:20:20,500
Fie Ben sau I sau Brian sau Jason
sau oricine altcineva, care

477
00:20:20,500 --> 00:20:21,370
indicii nevoie pentru a schimba?

478
00:20:21,370 --> 00:20:23,260
Câte în total?

479
00:20:23,260 --> 00:20:24,080
>> OK, deci doi.

480
00:20:24,080 --> 00:20:27,090
Indicatorul mea nu mai contează cu adevărat
pentru că eu sunt doar temporare.

481
00:20:27,090 --> 00:20:31,370
Deci, este doi tipi, probabil,
atât Ben și Brian.

482
00:20:31,370 --> 00:20:34,410
Deci, permiteți-mi să propun ca noi actualizam
Ben, deoarece el e primul.

483
00:20:34,410 --> 00:20:36,350
Primul element al acestei liste
este acum de gând să fie Brian.

484
00:20:36,350 --> 00:20:38,070
Deci, punctul de Ben la Brian.

485
00:20:38,070 --> 00:20:39,320
OK, acum ce?

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

487
00:20:41,950 --> 00:20:43,460
>> Care devine subliniat la cine?

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

489
00:20:44,710 --> 00:20:46,180
>> SPEAKER 1: OK așa Brian are
la punctul de la Jason.

490
00:20:46,180 --> 00:20:48,360
Dar am pierdut evidența că indicatorul?

491
00:20:48,360 --> 00:20:49,980
Nu știu unde Jason este?

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

493
00:20:50,790 --> 00:20:52,620
>> SPEAKER 1: Eu fac, deoarece sunt
indicatorul temporar.

494
00:20:52,620 --> 00:20:55,110
Și probabil, nu s-au schimbat
la punctul de la noul nod.

495
00:20:55,110 --> 00:20:58,300
Astfel încât să putem avea pur și simplu Brian punct
la cine am îndreptat la.

496
00:20:58,300 --> 00:20:59,000
Și am terminat.

497
00:20:59,000 --> 00:21:01,890
Deci caz unul, introducerea la
începutul listei.

498
00:21:01,890 --> 00:21:02,950
Au existat două etape cheie.

499
00:21:02,950 --> 00:21:06,750
Unul, trebuie să actualizeze Ben, și apoi
avem, de asemenea, pentru a actualiza Brian.

500
00:21:06,750 --> 00:21:09,230
Și atunci nu trebuie să deranjez
plimbatul prin restul de

501
00:21:09,230 --> 00:21:12,680
lista, pentru că am găsit deja sa
locație, pentru că el a aparținut

502
00:21:12,680 --> 00:21:14,080
stânga a primului element.

503
00:21:14,080 --> 00:21:15,400
>> În regulă, deci destul de simplă.

504
00:21:15,400 --> 00:21:18,110
De fapt, se simte ca suntem aproape
face acest lucru prea complicat.

505
00:21:18,110 --> 00:21:20,240
Deci, haideți să smulgă acum pe final
din lista, și să vedem unde

506
00:21:20,240 --> 00:21:21,380
complexitatea începe.

507
00:21:21,380 --> 00:21:24,560
Așa că, dacă acum, am alloc din public.

508
00:21:24,560 --> 00:21:25,540
Oricine vrea să joace 55?

509
00:21:25,540 --> 00:21:26,700
În regulă, am văzut mâna întâi.

510
00:21:26,700 --> 00:21:29,620
Hai sus.

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

512
00:21:30,030 --> 00:21:31,177
Care e numele tău?

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

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

515
00:21:33,240 --> 00:21:33,890
OK, hai sus.

516
00:21:33,890 --> 00:21:35,730
Vei fi numărul 55.

517
00:21:35,730 --> 00:21:37,820
Deci tu, desigur, fac parte
la sfârșitul listei.

518
00:21:37,820 --> 00:21:41,850
Deci, haideți să relua simularea cu mine
fiind PTR pentru o clipă.

519
00:21:41,850 --> 00:21:44,050
Deci, eu sunt în primul rând de gând să arate la
indiferent de Ben pointing la.

520
00:21:44,050 --> 00:21:45,900
Suntem amândoi arătând acum la Brian.

521
00:21:45,900 --> 00:21:48,420
Deci 55 nu este mai mic de cinci.

522
00:21:48,420 --> 00:21:52,510
Așa că am de gând să mă actualiza prin
arătând spre viitor indicatorul lui Brian, care

523
00:21:52,510 --> 00:21:54,450
acum este, desigur, Jason.

524
00:21:54,450 --> 00:21:57,310
55 nu este mai mică de nouă, așa
Am de gând să actualizeze PTR.

525
00:21:57,310 --> 00:21:58,890
Am de gând să actualizeze PTR.

526
00:21:58,890 --> 00:22:02,290
Am de gând să actualizeze PTR
Am de gând să actualizeze PTR.

527
00:22:02,290 --> 00:22:05,060
Și am de gând să - hmm, ce-i
numele tau din nou?

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

529
00:22:05,560 --> 00:22:09,190
>> SPEAKER 1: Diana este îndreptat, desigur,
la zero cu mâna stângă.

530
00:22:09,190 --> 00:22:13,030
Deci, în cazul în care nu Habata de fapt,
apartin in mod clar?

531
00:22:13,030 --> 00:22:15,050
La stânga, aici.

532
00:22:15,050 --> 00:22:19,460
Deci, cum știu să o pun aici
Cred că am greșit.

533
00:22:19,460 --> 00:22:22,420
Pentru că ceea ce este PTR arta
acest moment?

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

535
00:22:23,240 --> 00:22:25,580
Deci, chiar dacă, vizual, putem
evident vezi toate aceste

536
00:22:25,580 --> 00:22:26,610
baieti aici pe scenă.

537
00:22:26,610 --> 00:22:29,680
Nu am ținut cont de precedent
persoană din lista.

538
00:22:29,680 --> 00:22:33,210
Nu am un deget subliniind,
în acest caz, numărul nodului 34.

539
00:22:33,210 --> 00:22:34,760
>> Să începem de fapt, acest peste.

540
00:22:34,760 --> 00:22:37,560
Așa că acum am de fapt, nu au nevoie de
a doua variabile locale.

541
00:22:37,560 --> 00:22:40,980
Și asta este ceea ce veți vedea în
codul actual C eșantion, în cazul în care așa cum am merge,

542
00:22:40,980 --> 00:22:45,860
când am actualiza mâna mea dreaptă la punctul
Jason, lăsând astfel în urmă Brian, am

543
00:22:45,860 --> 00:22:51,440
începe mai bine folosind mâna stângă pentru a
actualiza unde am fost, astfel încât, mă duc

544
00:22:51,440 --> 00:22:52,700
prin această listă -

545
00:22:52,700 --> 00:22:55,040
mai dur decât am intenționat
acum aici vizual -

546
00:22:55,040 --> 00:22:56,740
Am de gând să ajung la
sfârșitul listei.

547
00:22:56,740 --> 00:23:00,020
>> Această mână este încă nul, care este destul
inutil, altele decât pentru a indica

548
00:23:00,020 --> 00:23:02,980
Sunt în mod clar la sfârșitul listei,
dar acum cel puțin am asta

549
00:23:02,980 --> 00:23:08,270
indicatorul predecesorul arătând aici, așa
acum ceea ce mâinile și ce indicii au nevoie

550
00:23:08,270 --> 00:23:10,150
să fie actualizate?

551
00:23:10,150 --> 00:23:13,214
A cărui mână vrei
la primul reconfigura?

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

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

554
00:23:16,220 --> 00:23:21,110
În cazul în care vrei să subliniez
Indicatorul la stânga Diana de la?

555
00:23:21,110 --> 00:23:23,620
La 55, se presupune, astfel încât
am introdus acolo.

556
00:23:23,620 --> 00:23:25,560
Și unde ar trebui să meargă 55 de indicatorul?

557
00:23:25,560 --> 00:23:27,000
Jos, reprezentând nul.

558
00:23:27,000 --> 00:23:28,890
Și mâinile mele, la acest moment, nu
contează, pentru că acestea au fost doar

559
00:23:28,890 --> 00:23:30,070
variabile temporare.

560
00:23:30,070 --> 00:23:31,030
Deci, acum am terminat.

561
00:23:31,030 --> 00:23:34,650
>> Deci, complexitatea suplimentare de acolo - și
nu e greu de implementat,

562
00:23:34,650 --> 00:23:38,660
dar avem nevoie de o variabilă secundar de a face
vă că înainte de a mă muta dreptul meu

563
00:23:38,660 --> 00:23:42,140
de mână, să-mi actualizez valoarea stânga mea
parte, indicatorul pred în acest caz, astfel

564
00:23:42,140 --> 00:23:45,860
că am un pointer la final
pentru a urmări unde am fost.

565
00:23:45,860 --> 00:23:49,360
Acum, ca o paranteză, dacă te gândești acest
prin, acest lucru se simte ca este un

566
00:23:49,360 --> 00:23:51,490
puțin enervant să aibă de a păstra
urmări din această mână stângă.

567
00:23:51,490 --> 00:23:54,015
>> Ceea ce ar fi o altă soluție
la aceste probleme au fost?

568
00:23:54,015 --> 00:23:56,500
Dacă ai de a restructura datele
Structura vorbim

569
00:23:56,500 --> 00:23:59,630
prin chiar acum?

570
00:23:59,630 --> 00:24:02,690
Dacă acest tip doar de simte un pic
enervant de a avea, ca, doi pointeri

571
00:24:02,690 --> 00:24:08,430
trece prin lista, cine altcineva ar putea
au, într-o lume ideală, menținut

572
00:24:08,430 --> 00:24:10,160
informațiile de care avem nevoie?

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

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

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

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

577
00:24:16,150 --> 00:24:19,130
Chiar astfel încât nu este de fapt un interesant
germeni de o idee.

578
00:24:19,130 --> 00:24:22,470
Și această idee de un pointer anterior,
îndreptat la elementul anterior.

579
00:24:22,470 --> 00:24:25,580
Ce se întâmplă dacă am întruchipat că
interiorul listei sine?

580
00:24:25,580 --> 00:24:27,810
Și că va fi greu de vizualizat
acest lucru fără toată hârtia

581
00:24:27,810 --> 00:24:28,830
care se încadrează la podea.

582
00:24:28,830 --> 00:24:31,860
Dar să presupunem că acești oameni folosit atât
de mâinile lor pentru a avea un precedent

583
00:24:31,860 --> 00:24:35,950
pointer, iar un pointer viitor, astfel
punerea în aplicare a ceea ce vom numi un dublu

584
00:24:35,950 --> 00:24:36,830
Lista legate.

585
00:24:36,830 --> 00:24:41,090
Asta mi-ar permite pentru a sorta de înapoi,
mult mai ușor, fără mine,

586
00:24:41,090 --> 00:24:43,800
programator, având pentru a menține
urmări manual -

587
00:24:43,800 --> 00:24:44,980
cu adevărat manual -

588
00:24:44,980 --> 00:24:47,280
de unde am fost anterior
În lista.

589
00:24:47,280 --> 00:24:48,110
Deci, nu vom face asta.

590
00:24:48,110 --> 00:24:50,950
Vom păstrați-l simplu, pentru că
Va veni la un preț de două ori mai

591
00:24:50,950 --> 00:24:53,450
mult spațiu pentru indicii,
dacă vrei un al doilea.

592
00:24:53,450 --> 00:24:55,760
Dar asta e într-adevăr un comun
structura de date cunoscut ca un

593
00:24:55,760 --> 00:24:57,410
de două ori lista de legat.

594
00:24:57,410 --> 00:25:01,310
>> Să facem un exemplu final de aici și pune-
tipii ăștia din mizerie lor.

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

596
00:25:03,270 --> 00:25:05,320
Haide sus de culoar acolo.

597
00:25:05,320 --> 00:25:06,280
În regulă, care e numele tău?

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

599
00:25:07,440 --> 00:25:07,855
>> SPEAKER 1: Imi pare rau?

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

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

602
00:25:09,410 --> 00:25:10,230
OK vin pe sus.

603
00:25:10,230 --> 00:25:11,910
Tu trebuie să fie de 20.

604
00:25:11,910 --> 00:25:14,720
Tu, evident, se vor
aparțin între 17 și 22.

605
00:25:14,720 --> 00:25:16,150
Deci, lasă-mă să învețe lecția mea.

606
00:25:16,150 --> 00:25:18,150
Am de gând să înceapă indicatorul
arătând la Brian.

607
00:25:18,150 --> 00:25:21,190
Și am de gând să aibă mâna stângă
actualiza doar la Brian cum am muta la

608
00:25:21,190 --> 00:25:23,600
Jason, verificarea are 20 de mai puțin de nouă?

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

610
00:25:24,060 --> 00:25:25,430
Este 20 mai puțin de 17?

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

612
00:25:25,880 --> 00:25:27,450
Este 20 mai puțin de 22?

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

614
00:25:28,440 --> 00:25:34,070
Deci, ce indicii sau mâini nevoie pentru a schimba
unde se indică acum?

615
00:25:34,070 --> 00:25:37,070
>> Deci, putem face 17 arătând la 20.

616
00:25:37,070 --> 00:25:37,860
Așa că e bine.

617
00:25:37,860 --> 00:25:40,080
Unde vrem să sublinieze
indicatorul acum?

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

619
00:25:41,330 --> 00:25:45,410
Și știm unde 22 este, din nou, datorită
la indicatorul mea temporar.

620
00:25:45,410 --> 00:25:46,760
Deci suntem bine acolo.

621
00:25:46,760 --> 00:25:49,440
Deci, din cauza acestei depozitare temporară
Am ținut evidența în care toată lumea este.

622
00:25:49,440 --> 00:25:55,055
Si acum poti sa te duci vizual în cazul în care
faci parte, iar acum avem nevoie de 1, 2, 3,

623
00:25:55,055 --> 00:25:58,410
4, 5, 6, 7, 8, 9 bile de stres,
și o rundă de aplauze pentru

624
00:25:58,410 --> 00:25:59,770
tipii ăștia, dacă am putea.

625
00:25:59,770 --> 00:26:00,410
Bine făcut.

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

627
00:26:05,320 --> 00:26:06,330
>> SPEAKER 1: În regulă.

628
00:26:06,330 --> 00:26:09,860
Și s-ar putea păstra piesele
de hârtie amintiri.

629
00:26:09,860 --> 00:26:15,930
>> În regulă, deci, ai încredere în mine este o foarte mult
mai ușor să treci prin asta cu

630
00:26:15,930 --> 00:26:17,680
oameni decât este cu codul actual.

631
00:26:17,680 --> 00:26:22,690
Dar ceea ce veți găsi într-o clipă
acum, este același - Oh, vă mulțumesc.

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

633
00:26:23,630 --> 00:26:29,360
este că veți găsi că aceleași date
structura, o lista inlantuita, poate de fapt,

634
00:26:29,360 --> 00:26:33,200
fi utilizat ca o componentă a chiar mai mult
structuri de date sofisticate.

635
00:26:33,200 --> 00:26:37,620
>> Și dau seama prea tema aici este că
am absolut introdus mai mult

636
00:26:37,620 --> 00:26:40,060
complexitate în aplicare
acestui algoritm.

637
00:26:40,060 --> 00:26:43,940
Inserție, și dacă am trecut prin ea,
ștergere și căutare, este un pic

638
00:26:43,940 --> 00:26:46,660
mai complicat decât
a fost cu o matrice.

639
00:26:46,660 --> 00:26:48,040
Dar am castigat un dinamism.

640
00:26:48,040 --> 00:26:50,180
Am obține o structură adaptivă de date.

641
00:26:50,180 --> 00:26:54,010
>> Dar, din nou, vom plăti un preț de a avea unele
complexitate suplimentară, atât în

642
00:26:54,010 --> 00:26:54,910
punerea sa în aplicare.

643
00:26:54,910 --> 00:26:56,750
Și suntem renunțat acces aleator.

644
00:26:56,750 --> 00:27:00,450
Și pentru a fi sincer, nu e ceva frumos
curat diapozitiv pot să vă dau că

645
00:27:00,450 --> 00:27:03,120
spune aici este de ce o lista inlantuita
este mai mult decât un tablou.

646
00:27:03,120 --> 00:27:04,100
Și lăsați-l la asta.

647
00:27:04,100 --> 00:27:07,520
Deoarece tema reapariția acum, chiar
cu atât mai mult în următoarele săptămâni, este

648
00:27:07,520 --> 00:27:10,200
că nu e neapărat
un răspuns corect.

649
00:27:10,200 --> 00:27:13,830
>> Acesta este motivul pentru care am axa separat
de proiectare pentru seturi de probleme.

650
00:27:13,830 --> 00:27:17,700
Acesta va fi foarte sensibil la context
dacă doriți să utilizați aceste date

651
00:27:17,700 --> 00:27:21,750
structură sau să rețină, și se va
depinde de ceea ce conteaza pentru tine din punct de vedere

652
00:27:21,750 --> 00:27:24,620
de resurse și complexitate.

653
00:27:24,620 --> 00:27:28,830
>> Dar permiteți-mi să propun ca datele ideale
structura, Sfântul Graal, ar fi

654
00:27:28,830 --> 00:27:32,200
ceva care este constanta de timp,
indiferent de cât de multe lucruri este

655
00:27:32,200 --> 00:27:36,940
în interiorul acestuia, nu ar fi extraordinar dacă o
Structura de date a revenit răspunsuri în

656
00:27:36,940 --> 00:27:37,920
constanta de timp.

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

658
00:27:38,330 --> 00:27:40,110
Acest cuvânt este în dicționar ta imens.

659
00:27:40,110 --> 00:27:41,550
Sau nu, acest cuvânt nu este.

660
00:27:41,550 --> 00:27:43,270
Sau orice astfel de problemă acolo.

661
00:27:43,270 --> 00:27:46,360
Ei bine, să vedem dacă nu putem cel puțin
ia un pas spre asta.

662
00:27:46,360 --> 00:27:50,190
>> Permiteți-mi să propun o nouă structură de date care
pot fi folosite pentru lucruri diferite,

663
00:27:50,190 --> 00:27:52,260
în acest caz numit o tabela de dispersie.

664
00:27:52,260 --> 00:27:55,590
Și așa suntem de fapt, înapoi la uite
la o matrice, în acest caz, și

665
00:27:55,590 --> 00:28:00,550
oarecum arbitrar, am desenat asta
tabelul hash ca un tablou cu un fel de

666
00:28:00,550 --> 00:28:02,810
tablou bidimensional -

667
00:28:02,810 --> 00:28:05,410
sau mai degrabă este descris aici ca un doi
matrice dimensionale - dar aceasta este doar

668
00:28:05,410 --> 00:28:10,770
o matrice de dimensiune 26, astfel că, dacă ne
sunați la masa matrice, suport de masă

669
00:28:10,770 --> 00:28:12,440
Zero este dreptunghi în partea de sus.

670
00:28:12,440 --> 00:28:15,090
Tabelul suport 25 este dreptunghi
în partea de jos.

671
00:28:15,090 --> 00:28:18,620
Și acest lucru este modul în care s-ar putea trage de date
structura în care doresc să stocheze

672
00:28:18,620 --> 00:28:19,790
oamenilor nume.

673
00:28:19,790 --> 00:28:24,370
>> Deci, de exemplu, și nu voi trage
totul aici, pe deasupra, dacă am

674
00:28:24,370 --> 00:28:29,160
a avut această matrice, pe care am acum de gând să
apela un tabel hash, iar acest lucru este din nou

675
00:28:29,160 --> 00:28:31,360
locație zero.

676
00:28:31,360 --> 00:28:34,840
Acest lucru aici este locație
unul, și așa mai departe.

677
00:28:34,840 --> 00:28:37,880
Eu susțin că vreau să utilizeze aceste date
structura, de dragul discuției,

678
00:28:37,880 --> 00:28:42,600
pentru a stoca nume de persoane, Alice și Bob
și Charlie și alte nume, cum.

679
00:28:42,600 --> 00:28:46,110
Deci, cred că de asta acum ca inceputurile
de, să zicem, un dicționar

680
00:28:46,110 --> 00:28:47,520
cu o mulțime de cuvinte.

681
00:28:47,520 --> 00:28:49,435
Se întâmplă să fie numele
în exemplul nostru aici.

682
00:28:49,435 --> 00:28:52,560
Și acest lucru este prea Germane, probabil, la
implementarea unui corector ortografic, așa cum am

683
00:28:52,560 --> 00:28:54,400
s-ar putea ca problema stabilit șase.

684
00:28:54,400 --> 00:28:59,300
>> Deci, dacă avem o serie de mărimea totală 26
astfel că aceasta este locația 25

685
00:28:59,300 --> 00:29:03,390
în partea de jos, și eu susțin că Alice este
primul cuvânt în dicționarul de

686
00:29:03,390 --> 00:29:07,260
nume pe care vreau să insera în memoria RAM,
în această structură de date, în cazul în care sunt

687
00:29:07,260 --> 00:29:12,480
instincte care vă spune că Alice
Numele ar trebui să meargă în acest tablou?

688
00:29:12,480 --> 00:29:13,510
>> Avem 26 de opțiuni.

689
00:29:13,510 --> 00:29:14,990
În cazul în care vrem să-i dea?

690
00:29:14,990 --> 00:29:16,200
Ne-o doresc în paranteză la zero, nu?

691
00:29:16,200 --> 00:29:18,280
O pentru Alice, sa-i spunem că la zero.

692
00:29:18,280 --> 00:29:20,110
Și B va fi una, și C va fi de două.

693
00:29:20,110 --> 00:29:22,600
Așa că am de gând să scrie
Numele lui Alice aici.

694
00:29:22,600 --> 00:29:24,890
Dacă vom introduce apoi Bob, sa
Numele va merge aici.

695
00:29:24,890 --> 00:29:27,280
Charlie va merge aici.

696
00:29:27,280 --> 00:29:30,500
Și așa mai departe în jos, prin
această structură de date.

697
00:29:30,500 --> 00:29:32,090
>> Aceasta este o structură de date minunat.

698
00:29:32,090 --> 00:29:32,730
De ce?

699
00:29:32,730 --> 00:29:37,460
Ei bine, ceea ce este timpul de funcționare a
introducerea numelui unui om în această

700
00:29:37,460 --> 00:29:39,850
structura de date acum?

701
00:29:39,850 --> 00:29:43,702
Având în vedere că acest tabel este pusă în aplicare,
într-adevăr, ca o matrice.

702
00:29:43,702 --> 00:29:44,940
Ei bine, e timpul constanta.

703
00:29:44,940 --> 00:29:45,800
Este ordin de unul.

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

705
00:29:46,360 --> 00:29:48,630
>> Ei bine, cum a face tu a determina
unde Alice aparține?

706
00:29:48,630 --> 00:29:51,000
Te uiți la care scrisoarea de numele ei?

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

708
00:29:51,490 --> 00:29:54,350
Și poți ajunge acolo, dacă e un șir,
de doar uita la șir

709
00:29:54,350 --> 00:29:55,200
suport zero.

710
00:29:55,200 --> 00:29:57,110
Deci, caracterul zero din șir.

711
00:29:57,110 --> 00:29:57,610
Asta e ușor.

712
00:29:57,610 --> 00:30:00,350
Am făcut asta în cripto
Acum săptămâni de atribuire.

713
00:30:00,350 --> 00:30:05,310
Și apoi, o dată ce știi că e Alice
scrisoare este de capital o, putem scădea

714
00:30:05,310 --> 00:30:08,160
pe 65 sau capitalul A sine,
care ne dă zero.

715
00:30:08,160 --> 00:30:10,940
Deci, noi stim acum ca Alice aparține
la locația zero.

716
00:30:10,940 --> 00:30:14,240
>> Și dat un pointer la aceste date
structura, de un anumit fel, cât timp nu

717
00:30:14,240 --> 00:30:18,840
mi iau pentru a găsi locația
zero, într-o matrice?

718
00:30:18,840 --> 00:30:22,080
Doar un singur pas, chiar e constanta de timp
cauza acces aleator ne

719
00:30:22,080 --> 00:30:23,780
propus a fost o caracteristică a unei matrice.

720
00:30:23,780 --> 00:30:28,570
Deci, pe scurt, imaginind ce indicele
de numele lui Alice este, care este, în

721
00:30:28,570 --> 00:30:32,610
acest caz, este un, sau să rezolve doar
care la zero, în cazul în care B este unul și C este

722
00:30:32,610 --> 00:30:34,900
doi, imaginind că în
este constanta de timp.

723
00:30:34,900 --> 00:30:38,510
Trebuie doar să te uiți la prima scrisoare,
imaginind în cazul zero, este un

724
00:30:38,510 --> 00:30:40,460
matrice este, de asemenea, de timp constant.

725
00:30:40,460 --> 00:30:42,140
Deci, punct de vedere tehnic, care este
ca doi pași acum.

726
00:30:42,140 --> 00:30:43,330
Dar asta e tot constant.

727
00:30:43,330 --> 00:30:46,880
Deci, noi numim asta Big O de unul, așa că am
inserat Alice în acest tabel în

728
00:30:46,880 --> 00:30:48,440
constanta de timp.

729
00:30:48,440 --> 00:30:50,960
>> Dar, desigur, eu fiind
naiv aici, nu?

730
00:30:50,960 --> 00:30:53,240
Ce se întâmplă dacă există un Aaron în clasă?

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

732
00:30:53,990 --> 00:30:57,230
Sau orice alte nume începând cu
A. În cazul în care vom pune

733
00:30:57,230 --> 00:31:00,800
acea persoana, nu?

734
00:31:00,800 --> 00:31:03,420
Adică, acum există doar trei
oamenii de pe masa, asa ca poate ne

735
00:31:03,420 --> 00:31:07,490
ar trebui să pună Aaron la locație
zero, unu, doi, trei.

736
00:31:07,490 --> 00:31:09,480
>> Dreapta, am putea pune o aici.

737
00:31:09,480 --> 00:31:13,350
Dar apoi, în cazul în care vom încerca să introduceți David în
această listă, în cazul în care se merge pe David?

738
00:31:13,350 --> 00:31:15,170
Acum, sistemul nostru începe de rupere
jos, dreapta?

739
00:31:15,170 --> 00:31:19,210
Pentru că acum David se termină aici
dacă Aaron este, de fapt aici.

740
00:31:19,210 --> 00:31:23,060
Iar acum ideea asta de a avea un
Structura de date curat, care ne dă

741
00:31:23,060 --> 00:31:28,010
inserții constantă de timp nu mai este
constanta de timp, pentru că trebuie să

742
00:31:28,010 --> 00:31:31,240
verifica, oh, la dracu, e cineva deja
în locul lui Alice.

743
00:31:31,240 --> 00:31:35,320
>> Permiteți-mi sonda restul acestor date
structură, în căutarea unui loc de a pune

744
00:31:35,320 --> 00:31:37,130
cineva ca numele lui Aaron.

745
00:31:37,130 --> 00:31:39,390
Și astfel încât prea începe
să ia timp liniar.

746
00:31:39,390 --> 00:31:42,710
Mai mult decât atât, atunci când doriți să găsiți
Aaron în această structură de date, și tu

747
00:31:42,710 --> 00:31:45,430
verifica, și numele lui Aaron nu este aici.

748
00:31:45,430 --> 00:31:47,960
În mod ideal, ar spune doar lui Aaron
nu în structura de date.

749
00:31:47,960 --> 00:31:51,530
Dar dacă ai face începe a face loc pentru
Aaron unde ar fi fost un D

750
00:31:51,530 --> 00:31:55,600
sau un E, tu, cel mai rău caz, trebuie să verificați
structura de date întreg, în

751
00:31:55,600 --> 00:31:59,480
caz în care revine în ceva
liniar în dimensiunea tabelului.

752
00:31:59,480 --> 00:32:00,920
>> Deci în regulă, voi rezolva aceasta.

753
00:32:00,920 --> 00:32:04,200
Problema aici este că am avut
26 elemente în această matrice.

754
00:32:04,200 --> 00:32:05,000
Lasă-mă să-l schimbe.

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

756
00:32:06,010 --> 00:32:10,600
Lasă-mă să-l schimbe, astfel ca, mai degraba fiind de
dimensiune 26 în total, observa în partea de jos

757
00:32:10,600 --> 00:32:12,720
indicele se va schimba la n minus 1.

758
00:32:12,720 --> 00:32:16,610
Dacă 26 este în mod clar prea mic pentru om "
nume, pentru că există mii de

759
00:32:16,610 --> 00:32:20,830
numele din lume, hai să facem doar
în 100 sau 1000 sau 10000.

760
00:32:20,830 --> 00:32:22,960
Să aloce doar o mult mai mult spațiu.

761
00:32:22,960 --> 00:32:27,230
>> Bine că nu scade în mod necesar
probabilitatea că nu vom avea două

762
00:32:27,230 --> 00:32:31,510
oameni cu nume începând cu A, și
Deci, ai de gând să încerce să pună un

763
00:32:31,510 --> 00:32:33,120
nume de la locație la zero încă.

764
00:32:33,120 --> 00:32:36,850
Ei încă de gând să se ciocnesc, care
înseamnă că avem nevoie de o soluție pentru a pune

765
00:32:36,850 --> 00:32:41,020
Alice și Aaron și Alicia și alte
Nume care încep cu A în altă parte.

766
00:32:41,020 --> 00:32:43,460
Dar cât de mult de o problema este aceasta?

767
00:32:43,460 --> 00:32:46,870
Care este probabilitatea ca
au coliziunilor de date

768
00:32:46,870 --> 00:32:48,240
structura ca aceasta?

769
00:32:48,240 --> 00:32:52,570
>> Ei bine, lasa-ma sa - vom reveni
la această întrebare aici.

770
00:32:52,570 --> 00:32:55,530
Si uita-te la cum am putea
rezolve mai întâi.

771
00:32:55,530 --> 00:32:58,480
Lasă-mă să trageți în sus această propunere aici.

772
00:32:58,480 --> 00:33:02,020
Ceea ce am descris este un algoritm,
o euristică numit liniar

773
00:33:02,020 --> 00:33:05,030
sondare în care, dacă ați încercat să introduceți
ceva aici, în aceste date

774
00:33:05,030 --> 00:33:08,920
structura, care se numește o tabela de dispersie,
și nu e loc acolo, te

775
00:33:08,920 --> 00:33:12,000
sonda cu adevărat structura de date
verificarea, este aceasta disponibilă?

776
00:33:12,000 --> 00:33:13,430
Este aceasta, este disponibil acest disponibilă?

777
00:33:13,430 --> 00:33:13,980
Este aceasta disponibilă?

778
00:33:13,980 --> 00:33:17,550
Și când în cele din urmă este, de a introduce
numele pe care ați intenționat inițial

779
00:33:17,550 --> 00:33:19,370
în altă parte la acea locație.

780
00:33:19,370 --> 00:33:23,360
Dar, în cel mai rău caz, singurul loc
ar putea fi foarte jos a datelor

781
00:33:23,360 --> 00:33:25,090
structura, la capăt de matrice.

782
00:33:25,090 --> 00:33:30,130
>> Deci liniar sondare, în cel mai rău caz,
decurge într-un algoritm liniar unde

783
00:33:30,130 --> 00:33:34,500
Aaron, dacă se întâmplă să fie introdusă trecut
în această structură de date, el ar putea

784
00:33:34,500 --> 00:33:39,540
ciocnesc cu aceasta prima locatie, dar
apoi termina de ghinion la sfârșitul.

785
00:33:39,540 --> 00:33:43,940
Deci, acest lucru nu este o constantă
timp Sfântul Graal pentru noi.

786
00:33:43,940 --> 00:33:47,650
Această abordare a elementelor introduce în
o structură de date numită o distribuire

787
00:33:47,650 --> 00:33:52,050
tabel nu pare să fie constantă de timp
cel puțin nu în cazul general.

788
00:33:52,050 --> 00:33:54,000
Se poate revin în ceva liniar.

789
00:33:54,000 --> 00:33:56,970
>> Deci, dacă am rezolva coliziuni
oarecum diferit?

790
00:33:56,970 --> 00:34:00,740
Deci, aici este o mult mai sofisticat
abordare a ceea ce e mai

791
00:34:00,740 --> 00:34:02,800
numit un tabel hash.

792
00:34:02,800 --> 00:34:05,890
Și de hash, ca o paranteza, ceea ce
Vreau să spun este indicele care

793
00:34:05,890 --> 00:34:07,070
Am menționat mai devreme.

794
00:34:07,070 --> 00:34:09,810
Pentru ceva hash poate fi
gândit ca un verb.

795
00:34:09,810 --> 00:34:13,690
>> Deci, dacă hash Alice e un nume,
o funcție hash, ca să spunem așa,

796
00:34:13,690 --> 00:34:14,710
ar trebui să returneze un număr.

797
00:34:14,710 --> 00:34:18,199
În acest caz este zero în cazul în care ea aparține la
locație de zero, unul în cazul în care ea aparține la

798
00:34:18,199 --> 00:34:20,000
locație, și așa mai departe.

799
00:34:20,000 --> 00:34:24,360
Deci funcția mea de hash a fost până acum
super-simplu, doar uita la

800
00:34:24,360 --> 00:34:26,159
Prima literă din numele cuiva.

801
00:34:26,159 --> 00:34:29,090
Dar o funcție hash are ca
intrare unele bucata de date, o

802
00:34:29,090 --> 00:34:30,210
string, un întreg, indiferent de.

803
00:34:30,210 --> 00:34:32,239
Și-l scuipă de obicei un număr.

804
00:34:32,239 --> 00:34:35,739
Și că numărul este în cazul în care datele
Elementul aparține într-o structură de date

805
00:34:35,739 --> 00:34:37,800
cunoscut aici ca un tabel hash.

806
00:34:37,800 --> 00:34:41,400
>> Deci, doar intuitiv, acesta este un
ușor diferită context.

807
00:34:41,400 --> 00:34:44,170
Aceasta este, de fapt se referă la un exemplu
care implică de naștere, în cazul în care

808
00:34:44,170 --> 00:34:46,850
ar putea fi la fel de multe ca
31 zile din luna.

809
00:34:46,850 --> 00:34:52,239
Dar ce această persoană decide să
face în cazul unei coliziuni?

810
00:34:52,239 --> 00:34:55,304
Contextul fiind acum nu, o coliziune de
nume, ci o coliziune de nastere,

811
00:34:55,304 --> 00:35:00,760
În cazul în care două persoane au aceeași zi de naștere pe
2 octombrie, de exemplu.

812
00:35:00,760 --> 00:35:02,120
>> STUDENT: [inaudibil].

813
00:35:02,120 --> 00:35:05,010
>> SPEAKER 1: Da, așa că aici avem
pârghie de liste legate.

814
00:35:05,010 --> 00:35:07,830
Deci, se pare un pic diferit
decât l-am desenat mai devreme.

815
00:35:07,830 --> 00:35:10,790
Dar noi par să aibă la o serie
pe partea stângă.

816
00:35:10,790 --> 00:35:13,230
Asta e un index, pentru nici o
motiv special.

817
00:35:13,230 --> 00:35:14,630
Dar este încă un tablou.

818
00:35:14,630 --> 00:35:16,160
Este o serie de indicii.

819
00:35:16,160 --> 00:35:20,670
Și fiecare dintre aceste elemente, fiecare dintre
aceste cercuri sau oblice - slash

820
00:35:20,670 --> 00:35:23,970
reprezentând nul - fiecare dintre acestea
indicii se pare că indică spre

821
00:35:23,970 --> 00:35:25,730
ce structura de date?

822
00:35:25,730 --> 00:35:26,890
O listă legat.

823
00:35:26,890 --> 00:35:30,530
>> Deci, acum avem capacitatea de a
Codul greu în programul nostru de

824
00:35:30,530 --> 00:35:32,010
dimensiunea tabelului.

825
00:35:32,010 --> 00:35:35,360
În acest caz, știm că nu e niciodată
mai mult de 31 de zile într-o lună.

826
00:35:35,360 --> 00:35:38,480
Atât de greu de codificare o valoare ca 31 este
rezonabile în acest context.

827
00:35:38,480 --> 00:35:42,700
În contextul de nume, greu de codificare
26 nu este nerezonabil-l oamenilor

828
00:35:42,700 --> 00:35:46,340
nume încep numai cu, de exemplu,
alfabetul implică o prin Z.

829
00:35:46,340 --> 00:35:50,180
>> Putem ghiftui-le pe toate în care datele
Structura atât timp cât, atunci când avem o

830
00:35:50,180 --> 00:35:55,330
coliziune, nu punem numele aici,
noi în loc ca aceste celule

831
00:35:55,330 --> 00:36:00,270
nu ca șiruri înșiși, ci ca
indicii pentru, de exemplu, Alice.

832
00:36:00,270 --> 00:36:03,660
Și apoi Alice poate avea un alt indicator
la un alt nume care începe cu

833
00:36:03,660 --> 00:36:06,150
A. Și Bob merge de fapt aici.

834
00:36:06,150 --> 00:36:10,850
>> Și dacă există un alt nume de pornire
cu B, se sfârșește aici.

835
00:36:10,850 --> 00:36:15,070
Și astfel fiecare dintre elementele acestui
tabel cu două, dacă ne conceput acest o

836
00:36:15,070 --> 00:36:17,350
ceva mai inteligent -

837
00:36:17,350 --> 00:36:18,125
haide -

838
00:36:18,125 --> 00:36:22,950
dacă am conceput aceasta un pic mai mult
inteligent, acum devine o de date adaptive

839
00:36:22,950 --> 00:36:27,720
structură, în cazul în care nu există o limită greu
pe cât de multe elemente puteți introduce

840
00:36:27,720 --> 00:36:30,700
în ea pentru că dacă nu au
o coliziune, asta e bine.

841
00:36:30,700 --> 00:36:34,690
Doar mergeți mai departe și adăugați-l la
ceea ce am văzut un pic în urmă a fost

842
00:36:34,690 --> 00:36:38,290
cunoscut ca o listă legată.

843
00:36:38,290 --> 00:36:39,690
>> Ei bine, să ne oprim pentru un moment.

844
00:36:39,690 --> 00:36:42,570
Care este probabilitatea unei coliziuni
în primul rând?

845
00:36:42,570 --> 00:36:45,480
Dreapta, poate eu sunt peste gândesc, poate
Sunt mai mult de inginerie această problemă,

846
00:36:45,480 --> 00:36:46,370
pentru că știi ce?

847
00:36:46,370 --> 00:36:49,070
Da, eu pot veni cu arbitrară
exemple de pe partea de sus a capului meu, cum ar fi

848
00:36:49,070 --> 00:36:52,870
Allison și Aaron, dar, în realitate,
dat o distribuție uniformă a

849
00:36:52,870 --> 00:36:56,990
intrări, care este un inserții aleatoare
într-o structură de date, ceea ce este cu adevărat

850
00:36:56,990 --> 00:36:58,580
probabilitatea unei coliziuni?

851
00:36:58,580 --> 00:37:01,670
Ei bine, se dovedește, de fapt
foarte mare.

852
00:37:01,670 --> 00:37:03,850
Lasă-mă să generalizeze această
Problema este ca aceasta.

853
00:37:03,850 --> 00:37:08,890
>> Deci, într-o cameră de n CS50 elevi, ceea ce este
probabilitatea ca cel puțin

854
00:37:08,890 --> 00:37:11,010
doi studenți în cameră
au aceeași zi de naștere?

855
00:37:11,010 --> 00:37:13,346
Deci, nu e ceea ce. un Hund câteva -

856
00:37:13,346 --> 00:37:16,790
200, 300 de oameni aici și mai multe
sute de oameni de la domiciliu de azi.

857
00:37:16,790 --> 00:37:20,670
Deci, dacă ai vrut să ne întrebăm ce este
probabilitatea de două persoane

858
00:37:20,670 --> 00:37:23,930
în această cameră care au aceeași zi de naștere,
ne putem da seama asta.

859
00:37:23,930 --> 00:37:26,250
Și eu pretind de fapt, există două
oameni cu aceeași zi de naștere.

860
00:37:26,250 --> 00:37:29,560
>> De exemplu, nu oricine
are ziua de nastere astazi?

861
00:37:29,560 --> 00:37:31,340
Ieri?

862
00:37:31,340 --> 00:37:32,590
Mâine?

863
00:37:32,590 --> 00:37:35,980
Bine, asa ca se simte ca și cum am de gând
să aibă de a face acest lucru 363 sau cam asa ceva mai mult

864
00:37:35,980 --> 00:37:39,500
ori să dau de fapt de
dacă avem o coliziune.

865
00:37:39,500 --> 00:37:42,350
Sau am putea face doar acest lucru matematic
mai degrabă decât plictisitor

866
00:37:42,350 --> 00:37:43,200
face acest lucru.

867
00:37:43,200 --> 00:37:44,500
Și propune următoarele.

868
00:37:44,500 --> 00:37:48,740
>> Deci, eu propun ca am putea modela
probabilitatea de două persoane care au

869
00:37:48,740 --> 00:37:55,320
aceeași zi de naștere ca probabilitatea de 1
minus probabilitatea de nimeni având

870
00:37:55,320 --> 00:37:56,290
aceeași zi de naștere.

871
00:37:56,290 --> 00:37:59,960
Deci, pentru a obține acest lucru, iar aceasta este doar
mod fantezist de a scrie acest lucru, pentru

872
00:37:59,960 --> 00:38:03,090
Prima persoană în cameră, el sau ea
poate avea oricare dintre posibil

873
00:38:03,090 --> 00:38:07,370
Zile de nastere presupunând 365 zile în an,
cu scuze pentru persoanele cu

874
00:38:07,370 --> 00:38:08,760
Data nasterii 29 februarie.

875
00:38:08,760 --> 00:38:13,470
>> Deci, prima persoană din această cameră este liber
pentru a avea orice număr de zile de naștere

876
00:38:13,470 --> 00:38:18,280
din cele 365 de posibilități, astfel încât
Vom face asta 365 împărțit la 365,

877
00:38:18,280 --> 00:38:18,990
care este unul.

878
00:38:18,990 --> 00:38:22,700
Următoarea persoană în cameră, dacă scopul
este de a evita o coliziune, poate doar

879
00:38:22,700 --> 00:38:26,460
au ziua lui sau a ei cu privire la modul
multe zile diferite posibile?

880
00:38:26,460 --> 00:38:27,610
364.

881
00:38:27,610 --> 00:38:31,430
Deci, al doilea termen în această expresie este
face în esență, că matematica pentru noi

882
00:38:31,430 --> 00:38:33,460
scăzând off o zi posibil.

883
00:38:33,460 --> 00:38:36,390
Și apoi a doua zi, a doua zi,
doua zi până la numărul total

884
00:38:36,390 --> 00:38:38,100
de persoane în cameră.

885
00:38:38,100 --> 00:38:41,290
>> Și dacă apoi ne gândim, ce este atunci
probabilitatea nu de toată lumea avea

886
00:38:41,290 --> 00:38:45,265
Zile de nastere unice, dar din nou 1 minus
că, ceea ce avem este o expresie

887
00:38:45,265 --> 00:38:47,810
care poate fi foarte fancifully
arata ca aceasta.

888
00:38:47,810 --> 00:38:50,330
Dar este mult mai interesant
să se uite la vizual.

889
00:38:50,330 --> 00:38:55,120
Aceasta este o diagramă care pe axa x este
numărul de persoane în cameră,

890
00:38:55,120 --> 00:38:56,180
numărul de zile de naștere.

891
00:38:56,180 --> 00:38:59,840
Pe axa y este probabilitatea
de o coliziune, două persoane

892
00:38:59,840 --> 00:39:01,230
având aceeași zi de naștere.

893
00:39:01,230 --> 00:39:05,020
>> Și Takeaway din această curbă este
că de îndată ce ajungi să-ți placă 40

894
00:39:05,020 --> 00:39:11,110
elevi, te-ai trezit la o probabilitate de 90%
combinatorically de două

895
00:39:11,110 --> 00:39:13,550
sau mai multe persoane care au
aceeași zi de naștere.

896
00:39:13,550 --> 00:39:18,600
Și odată ce ajungi să-ți placă 58 de persoane este
aproape 100% din o șansă două

897
00:39:18,600 --> 00:39:21,310
persoane în cameră vor avea
aceeași zi de naștere, chiar dacă există

898
00:39:21,310 --> 00:39:26,650
365 sau 366 de găleți posibile, și
doar 58 persoane in camera.

899
00:39:26,650 --> 00:39:29,900
Doar statistic, esti probabil pentru a
obține coliziuni, care în scurt

900
00:39:29,900 --> 00:39:31,810
motivează această discuție.

901
00:39:31,810 --> 00:39:35,890
Asta chiar dacă avem de lux aici, și
începe cu aceste lanțuri, suntem încă

902
00:39:35,890 --> 00:39:36,950
va avea coliziuni.

903
00:39:36,950 --> 00:39:42,710
>> Astfel că duce la intrebarea, ce este
costul de a face inserări și ștergeri

904
00:39:42,710 --> 00:39:44,850
într-o structură de date ca asta?

905
00:39:44,850 --> 00:39:46,630
Ei bine, lasă-mă să propun -

906
00:39:46,630 --> 00:39:51,570
și lasă-mă să mă întorc la ecranul peste
aici - dacă ne-am n elemente în

907
00:39:51,570 --> 00:39:56,330
lista, deci, dacă încercăm să introduceți
n elemente, și avem

908
00:39:56,330 --> 00:39:58,050
câte totalul găleți?

909
00:39:58,050 --> 00:40:03,450
Să zicem 31 Total găleți
în caz de naștere.

910
00:40:03,450 --> 00:40:09,240
Care este lungimea maximă a unui
din aceste lanțuri potențial?

911
00:40:09,240 --> 00:40:12,670
>> În cazul în care din nou nu e posibil 31
Zile de nastere într-o lună.

912
00:40:12,670 --> 00:40:14,580
Și noi suntem doar agregare toată lumea -

913
00:40:14,580 --> 00:40:15,580
de fapt asta e un exemplu prost.

914
00:40:15,580 --> 00:40:16,960
Să facem 26 în loc.

915
00:40:16,960 --> 00:40:20,890
Deci, dacă au de fapt oameni ale căror nume
începe cu A la Z, oferind astfel

916
00:40:20,890 --> 00:40:22,780
ne 26 de posibilități.

917
00:40:22,780 --> 00:40:25,920
Și suntem folosind o structura de date ca
cel pe care tocmai am văzut, prin care ne-am

918
00:40:25,920 --> 00:40:30,210
o serie de indicii, fiecare dintre acestea
indică o listă înlănțuită unde

919
00:40:30,210 --> 00:40:32,360
Prima listă este toată lumea
cu numele de Alice.

920
00:40:32,360 --> 00:40:35,770
A doua listă este fiecare cu
nume care începe cu A, incepand

921
00:40:35,770 --> 00:40:36,980
cu B, și așa mai departe.

922
00:40:36,980 --> 00:40:41,020
>> Care este lungimea probabil de fiecare dintre
aceste liste dacă presupunem un frumos curat

923
00:40:41,020 --> 00:40:45,410
distribuirea de nume de la A la Z
întreaga structură de date întreg?

924
00:40:45,410 --> 00:40:50,210
Există n oameni din structura de date
împărțit la 26, în cazul în care acestea sunt frumos

925
00:40:50,210 --> 00:40:52,110
răspândit peste tot
structură de date.

926
00:40:52,110 --> 00:40:54,970
Deci lungimea fiecăreia dintre aceste
lanțurilor este n împărțit la 26.

927
00:40:54,970 --> 00:40:57,380
Dar în O notație mare, ce e asta?

928
00:40:57,380 --> 00:41:00,100

929
00:41:00,100 --> 00:41:02,440
Ce este că într-adevăr?

930
00:41:02,440 --> 00:41:04,150
Deci, este într-adevăr doar n, nu?

931
00:41:04,150 --> 00:41:06,620
Pentru că am spus în trecut,
care uf vă împărțiți de 26.

932
00:41:06,620 --> 00:41:08,710
Da, în realitate, este mai rapid.

933
00:41:08,710 --> 00:41:12,720
Dar, în teorie, nu este fundamental
toate că mai repede.

934
00:41:12,720 --> 00:41:16,040
>> Deci, noi nu par a fi tot atât de mult
mai aproape de aceasta Sfântul Graal.

935
00:41:16,040 --> 00:41:17,750
De fapt, aceasta este doar timpul liniar.

936
00:41:17,750 --> 00:41:20,790
La naiba, la acest moment, de ce nu ne
folosesc doar o listă uriașă legat?

937
00:41:20,790 --> 00:41:23,510
De ce nu am folosi doar un singur mare
matrice pentru a stoca numele de

938
00:41:23,510 --> 00:41:25,010
toată lumea din cameră?

939
00:41:25,010 --> 00:41:28,280
Ei bine, există încă ceva
convingatoare despre un tabel hash?

940
00:41:28,280 --> 00:41:30,810
Există încă ceva convingătoare
despre o structură de date

941
00:41:30,810 --> 00:41:33,940
care arata ca aceasta?

942
00:41:33,940 --> 00:41:35,182
Acest lucru.

943
00:41:35,182 --> 00:41:37,050
>> STUDENT: [inaudibil].

944
00:41:37,050 --> 00:41:39,840
>> SPEAKER 1: Corect, și din nou, în cazul în care este doar
un algoritm de timp liniar, și un

945
00:41:39,840 --> 00:41:42,780
structura de date timp liniar, de ce nu am
stoca doar numele tuturor într-o mare

946
00:41:42,780 --> 00:41:44,210
matrice, sau într-o listă mare legat?

947
00:41:44,210 --> 00:41:47,010
Și nu mai face CS atât de mult mai greu
decât aceasta trebuie să fie?

948
00:41:47,010 --> 00:41:49,600

949
00:41:49,600 --> 00:41:53,190
Ce este convingătoare despre acest lucru, chiar
deși l-am zgâriat afară?

950
00:41:53,190 --> 00:41:54,930
>> STUDENT: [inaudibil].

951
00:41:54,930 --> 00:41:57,040
>> SPEAKER 1: Inserturi nu sunt?

952
00:41:57,040 --> 00:41:58,140
Mai scump.

953
00:41:58,140 --> 00:42:03,390
Deci, insertii potențial ar putea încă
să fie constantă de timp, chiar dacă datele

954
00:42:03,390 --> 00:42:07,910
Structura arata ca aceasta, o serie de
indicii, fiecare dintre care este îndreptat la

955
00:42:07,910 --> 00:42:09,550
eventual o listă înlănțuită.

956
00:42:09,550 --> 00:42:15,220
Cum ai putut obține constant
introducerea timpul de nume?

957
00:42:15,220 --> 00:42:16,280
Stick-l în față, dreapta?

958
00:42:16,280 --> 00:42:19,290
>> Dacă ne sacrificăm un obiectiv de proiectare de la
mai devreme, în cazul în care ne-am dorit să păstreze

959
00:42:19,290 --> 00:42:22,650
numele tuturor, de exemplu, sortate,
sau toate numerele de pe scena sortate,

960
00:42:22,650 --> 00:42:25,020
să presupunem că avem o
nesortate lista legat.

961
00:42:25,020 --> 00:42:29,960
Ea doar ne costă una sau două trepte,
ca în cazul lui Ben și Brian

962
00:42:29,960 --> 00:42:32,750
mai devreme, pentru a insera un element la
la începutul listei.

963
00:42:32,750 --> 00:42:36,090
Deci, dacă nu ne pasă de sortare toate
dintre numele care încep cu A sau toate

964
00:42:36,090 --> 00:42:39,660
nume încep cu litera B, putem încă
realiza introducerea constanta de timp.

965
00:42:39,660 --> 00:42:43,900
Acum în căutarea de până Alice sau Bob sau orice nume
mai general, este încă ce?

966
00:42:43,900 --> 00:42:48,100
E mare de O n împărțit la 26, în
cazul ideal în care toată lumea este uniform

967
00:42:48,100 --> 00:42:51,190
distribuite, în cazul în care nu există la fel de multe lui A
cum există lui Z, care este probabil

968
00:42:51,190 --> 00:42:52,220
nerealiste.

969
00:42:52,220 --> 00:42:53,880
Dar care este încă liniar.

970
00:42:53,880 --> 00:42:57,120
>> Dar aici, ne întoarcem la punctul de
de notație asimptotice a fi

971
00:42:57,120 --> 00:42:58,600
teoretic adevărat.

972
00:42:58,600 --> 00:43:02,960
Dar în lumea reală, dacă eu pretind că
Programul meu poate face ceva de 26 de ori

973
00:43:02,960 --> 00:43:06,210
mai rapid decât al tău, al căror program de
ai de gând să preferați să utilizați?

974
00:43:06,210 --> 00:43:09,660
A ta sau a mea, care
este de 26 ori mai rapid?

975
00:43:09,660 --> 00:43:14,320
Realist, persoana a cărei este 26
ori mai rapid, chiar dacă teoretic

976
00:43:14,320 --> 00:43:18,790
algoritmi noastre rula în același
asimptotic timp de funcționare.

977
00:43:18,790 --> 00:43:20,940
>> Permiteți-mi propune un alt
soluție cu totul.

978
00:43:20,940 --> 00:43:24,380
Și dacă acest lucru nu sufla mintea ta,
nu mai avem structuri de date.

979
00:43:24,380 --> 00:43:27,420
Deci, acest lucru este un trie -

980
00:43:27,420 --> 00:43:28,520
un fel de nume stupid.

981
00:43:28,520 --> 00:43:32,880
Ea vine de la extragerilor, iar cuvântul
este scris trie, t-r-i-e, din cauza

982
00:43:32,880 --> 00:43:34,450
Preluare curs sună ca trie.

983
00:43:34,450 --> 00:43:36,580
Dar asta e istorie
a trie cuvântului.

984
00:43:36,580 --> 00:43:40,980
>> Deci, un trie este într-adevăr un fel de copac,
și este, de asemenea, un joc pe acel cuvânt.

985
00:43:40,980 --> 00:43:46,330
Și, chiar dacă nu pot vedea destul de
cu această vizualizare, un trie este un

986
00:43:46,330 --> 00:43:50,790
arbore structurat, ca un arbore genealogic cu
un strămoș în partea de sus și o mulțime

987
00:43:50,790 --> 00:43:54,530
de nepoti si stranepoti
ca frunzele de pe jos.

988
00:43:54,530 --> 00:43:58,100
Dar fiecare nod într-un trie este un tablou.

989
00:43:58,100 --> 00:44:00,680
Și este într-o matrice - și hai să
simplifica prea mult pentru un moment - este un

990
00:44:00,680 --> 00:44:04,600
matrice, în acest caz, de mărimea 26, în cazul în care
fiecare nod din nou, este o matrice de dimensiune

991
00:44:04,600 --> 00:44:09,000
26, în cazul în care elementul de grad zero în acel
matrice reprezintă O, iar ultimul

992
00:44:09,000 --> 00:44:11,810
Elementul în fiecare astfel de
matrice reprezintă Z.

993
00:44:11,810 --> 00:44:15,520
>> Așa că propun, atunci, că aceste date
Structura, cunoscut ca un trie, poate fi

994
00:44:15,520 --> 00:44:17,600
folosit, de asemenea, pentru a stoca cuvinte.

995
00:44:17,600 --> 00:44:21,740
Am văzut acum un moment cum am putea stoca
cuvinte, sau în acest caz nume, iar noi

996
00:44:21,740 --> 00:44:25,440
vazut mai devreme cum putem stoca numere,
dar dacă ne concentrăm pe numele sau siruri de caractere

997
00:44:25,440 --> 00:44:27,460
aici, observa ceea ce e interesant.

998
00:44:27,460 --> 00:44:32,210
Eu susțin că numele de Maxwell este
în interiorul acestei structuri de date.

999
00:44:32,210 --> 00:44:33,730
În cazul în care vrei să vezi Maxwell?

1000
00:44:33,730 --> 00:44:35,140
>> STUDENT: [inaudibil].

1001
00:44:35,140 --> 00:44:36,240
>> SPEAKER 1: La stânga.

1002
00:44:36,240 --> 00:44:39,910
Deci, ceea ce este interesant cu aceste date
Structura este, mai degrabă decât magazin

1003
00:44:39,910 --> 00:44:46,200
șir M-A-X-W-E-L-L backslash la zero, toate
adiacent, ceea ce fac în schimb

1004
00:44:46,200 --> 00:44:46,890
urmărește.

1005
00:44:46,890 --> 00:44:50,510
Dacă acesta este un trie ca structura de date,
fiecare dintre noduri a căror este din nou o matrice,

1006
00:44:50,510 --> 00:44:54,650
și doriți să stocați Maxwell, mai întâi
index și astfel nodul rădăcina lui, așa

1007
00:44:54,650 --> 00:44:57,810
de a vorbi, nodul cel mai de sus,
la locație M, dreapta, așa

1008
00:44:57,810 --> 00:44:59,160
aproximativ în mijloc.

1009
00:44:59,160 --> 00:45:03,740
Și apoi de acolo, să urmați un
pointer la un copil noduri, ca să spunem așa.

1010
00:45:03,740 --> 00:45:06,150
Deci, în sensul arborele genealogic al familiei,
tu-l urmeze în jos.

1011
00:45:06,150 --> 00:45:09,030
Și care va conduce la un alt nod
pe stânga există, care este

1012
00:45:09,030 --> 00:45:10,540
doar un alt tablou.

1013
00:45:10,540 --> 00:45:14,710
>> Și apoi, dacă doriți să stocați Maxwell,
veți găsi indicatorul care reprezintă

1014
00:45:14,710 --> 00:45:16,430
O, care este cel de aici.

1015
00:45:16,430 --> 00:45:17,840
Apoi te duci la urmatorul nod.

1016
00:45:17,840 --> 00:45:20,100
Și observați - acesta este motivul pentru care imaginea lui
un pic înșelătoare -

1017
00:45:20,100 --> 00:45:21,990
acest nod arata super mic.

1018
00:45:21,990 --> 00:45:26,050
Dar în partea dreaptă a acestei este Y și Z.
Este doar autorul a trunchiat

1019
00:45:26,050 --> 00:45:27,630
imagine, astfel încât să de fapt
vezi lucruri.

1020
00:45:27,630 --> 00:45:30,400
În caz contrar, această imagine
ar fi extrem de mare.

1021
00:45:30,400 --> 00:45:36,180
Deci, acum vă indice în locația X, atunci
W, apoi E, atunci L, atunci L. Atunci ce-i

1022
00:45:36,180 --> 00:45:37,380
această curiozitate?

1023
00:45:37,380 --> 00:45:41,250
>> Ei bine, dacă vom folosi acest tip de noi
ia cu privire la modul de a stoca un șir într-un

1024
00:45:41,250 --> 00:45:44,500
structura de date, tot trebuie să
în esență bifa în datele

1025
00:45:44,500 --> 00:45:47,250
Structura că un cuvânt se termină aici.

1026
00:45:47,250 --> 00:45:50,830
Cu alte cuvinte, fiecare dintre aceste noduri
într-un fel trebuie să ne amintim că noi

1027
00:45:50,830 --> 00:45:53,500
urmată de fapt, toate aceste indicii
și pleacă un pic

1028
00:45:53,500 --> 00:45:58,370
miez de pâine în partea de jos a acestei aici
Structura a indica M-A-X-W-E-L-L este

1029
00:45:58,370 --> 00:46:00,230
într-adevăr, în această structură de date.

1030
00:46:00,230 --> 00:46:02,040
>> Deci, am putea face acest lucru, după cum urmează.

1031
00:46:02,040 --> 00:46:06,810
Fiecare dintre nodurile din imagine ne-am
ferăstrău are o, o serie de dimensiuni 27.

1032
00:46:06,810 --> 00:46:10,550
Și este acum 27, pentru că în p. stabilit șase,
vom da de fapt un apostrof,

1033
00:46:10,550 --> 00:46:13,590
astfel încât să putem avea nume ca O'Reilly
și altele cu apostrofuri.

1034
00:46:13,590 --> 00:46:14,820
Dar, aceeași idee.

1035
00:46:14,820 --> 00:46:17,710
Fiecare dintre aceste elemente în
puncte de matrice pentru o struct

1036
00:46:17,710 --> 00:46:19,320
nod, astfel încât doar un nod.

1037
00:46:19,320 --> 00:46:21,430
Deci, acest lucru este foarte amintește
din lista noastră legate.

1038
00:46:21,430 --> 00:46:24,550
>> Și apoi am un Boolean, pe care voi
apel cuvânt, care este doar de gând să fi

1039
00:46:24,550 --> 00:46:29,120
adevărat dacă un cuvânt se termină la acest
nod din arbore.

1040
00:46:29,120 --> 00:46:32,870
Aceasta reprezintă efectiv mic
triunghi am văzut acum o clipă.

1041
00:46:32,870 --> 00:46:37,190
Deci, dacă un cuvânt se termină la acel nod în
copac, că domeniul cuvânt va fi adevărat,

1042
00:46:37,190 --> 00:46:41,990
care este conceptual verificarea off, sau
suntem desen acestui triunghi, da acolo

1043
00:46:41,990 --> 00:46:44,080
este un cuvânt aici.

1044
00:46:44,080 --> 00:46:45,120
>> Deci, acesta este un trie.

1045
00:46:45,120 --> 00:46:48,540
Și acum întrebarea este, ce
este de timp de funcționare?

1046
00:46:48,540 --> 00:46:49,930
Este Big O de n?

1047
00:46:49,930 --> 00:46:51,410
Este altceva?

1048
00:46:51,410 --> 00:46:57,330
Ei bine, dacă ați n nume în aceste date
structura, Maxwell fiind doar unul dintre

1049
00:46:57,330 --> 00:47:02,330
ei, ceea ce este timpul de funcționare a
introducerea sau găsirea Maxwell?

1050
00:47:02,330 --> 00:47:06,230

1051
00:47:06,230 --> 00:47:09,050
Care este timpul de funcționare
de inserarea Maxwell?

1052
00:47:09,050 --> 00:47:11,740
Dacă există alte nume n
deja în tabel?

1053
00:47:11,740 --> 00:47:12,507
Da?

1054
00:47:12,507 --> 00:47:15,429
>> STUDENT: [inaudibil].

1055
00:47:15,429 --> 00:47:17,550
>> SPEAKER 1: Da, e lungimea
de nume, nu?

1056
00:47:17,550 --> 00:47:24,420
Deci M-a-x-w-e-l-l, astfel se simte ca aceasta
Algoritmul este Big O de șapte.

1057
00:47:24,420 --> 00:47:26,580
Acum, desigur, numele
va varia în lungime.

1058
00:47:26,580 --> 00:47:27,380
Poate e un nume scurt.

1059
00:47:27,380 --> 00:47:28,600
Poate e un nume mai lung.

1060
00:47:28,600 --> 00:47:33,390
Dar ceea ce este esențial aici este că
este un număr constant.

1061
00:47:33,390 --> 00:47:36,810
Și poate că nu e chiar constantă,
Dar Dumnezeu, în cazul în care realist, într-o

1062
00:47:36,810 --> 00:47:41,570
dicționar, există probabil unele limite
privind numărul de litere într-un

1063
00:47:41,570 --> 00:47:43,820
Numele persoanei într-o anumită țară.

1064
00:47:43,820 --> 00:47:46,940
>> Și deci putem presupune că
Valoarea este o constantă.

1065
00:47:46,940 --> 00:47:47,750
Nu știu ce este.

1066
00:47:47,750 --> 00:47:50,440
Este, probabil, mai mare decât
credem ca este.

1067
00:47:50,440 --> 00:47:52,720
Pentru că există întotdeauna un colț
caz cu un nume nebun lung.

1068
00:47:52,720 --> 00:47:56,360
Deci, haideți să-l k numesc, dar este încă un
constantă probabil, pentru că fiecare

1069
00:47:56,360 --> 00:48:00,190
nume în lume, cel puțin într-o
țară special, este faptul că lungimea sau

1070
00:48:00,190 --> 00:48:01,780
mai scurte, deci este constant.

1071
00:48:01,780 --> 00:48:04,490
Dar când am spus ceva este mare
O, de o valoare constantă, ce-i asta

1072
00:48:04,490 --> 00:48:07,760
într-adevăr echivalente?

1073
00:48:07,760 --> 00:48:10,420
Asta e într-adevăr același lucru
ar fi spus constanta de timp.

1074
00:48:10,420 --> 00:48:11,530
>> Acum suntem un fel de înșelăciune, nu?

1075
00:48:11,530 --> 00:48:15,340
Suntem un fel de pârghie unor teorii
aici să spun că bine, ordinea de K este

1076
00:48:15,340 --> 00:48:17,450
Chiar dispune doar de un singur,
și este constanta de timp.

1077
00:48:17,450 --> 00:48:18,200
Dar de fapt este.

1078
00:48:18,200 --> 00:48:22,550
Pentru că perspectiva cheie aici este că
dacă ne-am n nume deja în această

1079
00:48:22,550 --> 00:48:26,010
structura de date, si vom introduce Maxwell,
este cantitatea de timp ne duce la

1080
00:48:26,010 --> 00:48:29,530
introduceți Maxwell la toate afectate
de cât de multe alte persoane

1081
00:48:29,530 --> 00:48:31,100
sunt în structura de date?

1082
00:48:31,100 --> 00:48:31,670
Nu par a fi.

1083
00:48:31,670 --> 00:48:36,280
Dacă am avut un miliard de mai multe elemente de la această
trie, și apoi introduceți Maxwell, este

1084
00:48:36,280 --> 00:48:38,650
el la toate afectate?

1085
00:48:38,650 --> 00:48:39,050
Nu.

1086
00:48:39,050 --> 00:48:42,950
Și că este, spre deosebire de oricare dintre datele de zi
Structurile am văzut până acum, în cazul în care

1087
00:48:42,950 --> 00:48:46,820
timpul de rulare a algoritmului este
complet independent de cât de mult

1088
00:48:46,820 --> 00:48:51,430
lucruri este sau nu este deja
în care structura de date.

1089
00:48:51,430 --> 00:48:54,650
>> Și astfel, cu aceasta oferă acum este un
oportunitate pentru p set de șase, care va

1090
00:48:54,650 --> 00:48:58,310
din nou implica implementarea propriu
corector ortografic, citind în 150.000

1091
00:48:58,310 --> 00:49:01,050
cuvinte, cum cel mai bine pentru a stoca că
nu este neapărat evident.

1092
00:49:01,050 --> 00:49:04,030
Și, deși am aspirat pentru a găsi
Sfântul Graal, eu nu fac

1093
00:49:04,030 --> 00:49:05,330
susțin că un trie este.

1094
00:49:05,330 --> 00:49:09,810
De fapt, un tabel hash ar putea foarte bine
se dovedesc a fi mult mai eficient.

1095
00:49:09,810 --> 00:49:10,830
Dar acestea sunt doar -

1096
00:49:10,830 --> 00:49:14,620
care este doar una dintre deciziile de design
va trebui să facă.

1097
00:49:14,620 --> 00:49:18,920
>> Dar, in incheiere sa ia 50 sau cam asa ceva
secunde pentru a lua o privire la ceea ce se află

1098
00:49:18,920 --> 00:49:22,190
înainte de săptămâna viitoare și dincolo de noi tranziție
din această linie de comandă

1099
00:49:22,190 --> 00:49:26,220
lume, dacă programe C la lucruri web
bazat și limbi, cum ar fi PHP și

1100
00:49:26,220 --> 00:49:30,350
JavaScript și internet în sine,
protocoale cum ar fi HTTP, pe care le-ați

1101
00:49:30,350 --> 00:49:32,870
luate pentru a acordat de ani
acum, și în format text cele mai multe fiecare

1102
00:49:32,870 --> 00:49:34,440
zi, poate, sau văzut.

1103
00:49:34,440 --> 00:49:37,420
Și vom începe să coaja înapoi
straturi de ceea ce este pe internet.

1104
00:49:37,420 --> 00:49:40,650
Și ceea ce este codul care
sta la baza instrumente de astăzi.

1105
00:49:40,650 --> 00:49:43,230
Deci, 50 secunde ale acestui teaser aici.

1106
00:49:43,230 --> 00:49:46,570
Eu vă dau Warriors of Net.

1107
00:49:46,570 --> 00:49:51,370
>> [Redare video]

1108
00:49:51,370 --> 00:49:56,764
>> -A venit cu un mesaj.

1109
00:49:56,764 --> 00:50:00,687
Cu un protocol de toate propria sa.

1110
00:50:00,687 --> 00:50:13,370

1111
00:50:13,370 --> 00:50:19,780
El a venit la o lume de firewall-uri crude,
routere nepăsătoare, și pericolele departe

1112
00:50:19,780 --> 00:50:22,600
mai rău decât moartea.

1113
00:50:22,600 --> 00:50:23,590
E rapid.

1114
00:50:23,590 --> 00:50:25,300
E puternic.

1115
00:50:25,300 --> 00:50:27,700
E TCPIP.

1116
00:50:27,700 --> 00:50:30,420
Si are adresa dvs..

1117
00:50:30,420 --> 00:50:32,920

1118
00:50:32,920 --> 00:50:34,590
Warriors a fileului.

1119
00:50:34,590 --> 00:50:35,290
>> [END redare video]

1120
00:50:35,290 --> 00:50:38,070
>> SPEAKER 1: Acesta este modul în care internetul
va lucra ca de saptamana viitoare.

1121
00:50:38,070 --> 00:50:40,406