1
00:00:00,000 --> 00:00:00,500

2
00:00:00,500 --> 00:00:11,137
[MUSIC JOC]

3
00:00:11,137 --> 00:00:12,220
David J. MALAN: Bine.

4
00:00:12,220 --> 00:00:13,950
Acest lucru este CS50.

5
00:00:13,950 --> 00:00:18,560
Aceasta este saptamana cinci au continuat, iar noi
vești bune și vești proaste.

6
00:00:18,560 --> 00:00:21,140
Deci, o veste bună este că CS50
lanseaza vineri.

7
00:00:21,140 --> 00:00:24,430
Dacă doriți să ni se alăture,
cap de la URL-ul obișnuit aici.

8
00:00:24,430 --> 00:00:28,670
Chiar mai bine de știri, nu prelegere
aceasta vine luni al 13-lea.

9
00:00:28,670 --> 00:00:31,970
Ceva mai bine de știri,
Quiz zero este miercurea viitoare.

10
00:00:31,970 --> 00:00:33,840
Mai multe detalii pot fi
găsite la această adresă URL aici.

11
00:00:33,840 --> 00:00:36,340
Și în următoarele două zile
vom umple golurile

12
00:00:36,340 --> 00:00:39,234
în ceea ce privește camerele
că vom avea rezervate.

13
00:00:39,234 --> 00:00:41,400
Mai bine de știri este că nu va mai
fi o revizuire curs larg

14
00:00:41,400 --> 00:00:43,570
sesiune de acest vin
Luni seara.

15
00:00:43,570 --> 00:00:46,270
Stay tuned pentru a cursului
site-ul de localizare și detalii.

16
00:00:46,270 --> 00:00:49,290
Secțiunile, chiar dacă acesta este un
vacanță, se va întâlni, de asemenea, de asemenea.

17
00:00:49,290 --> 00:00:50,490

18
00:00:50,490 --> 00:00:52,940
Cel mai bun de știri, prelegeri vinerea viitoare.

19
00:00:52,940 --> 00:00:56,220
Deci, aceasta este o tradiție noi
au, conform programei analitice.

20
00:00:56,220 --> 00:00:58,100
Doar-- că va fi uimitor.

21
00:00:58,100 --> 00:01:02,510
Veți vedea lucruri, cum ar fi
structuri de date de timp constant

22
00:01:02,510 --> 00:01:04,730
și tabele de dispersie și copaci și încearcă.

23
00:01:04,730 --> 00:01:07,150
Și vom vorbi despre problemele de ziua de naștere.

24
00:01:07,150 --> 00:01:09,440
O grămadă de chestii
așteaptă vinerea viitoare.

25
00:01:09,440 --> 00:01:11,212

26
00:01:11,212 --> 00:01:12,200
OK.

27
00:01:12,200 --> 00:01:13,190
Oricum.

28
00:01:13,190 --> 00:01:17,080
>> Deci amintesc că am fost
concentrându-se pe această imagine a ceea ce este

29
00:01:17,080 --> 00:01:18,980
în interiorul memoriei calculatorului nostru.

30
00:01:18,980 --> 00:01:22,875
Deci, memorie RAM sau este în cazul în care programele de
Există în timp ce le execută.

31
00:01:22,875 --> 00:01:25,215
Dacă faceți dublu-clic pe un
pictogramă pentru a rula unele programe

32
00:01:25,215 --> 00:01:27,520
sau dublu-clic pe un
pictogramă pentru a deschide un fisier,

33
00:01:27,520 --> 00:01:30,430
e încărcat de pe hard-ul
conduce vehicule sau de pe unitatea SSD

34
00:01:30,430 --> 00:01:34,190
în memoria RAM, Random Access Memory, în cazul în care
trăiește până ce alimentarea înceteazã,

35
00:01:34,190 --> 00:01:36,700
capacul laptop se închide,
sau te-ai lasat programul.

36
00:01:36,700 --> 00:01:38,960
>> Acum, că memoria, de
care, probabil, va trebui

37
00:01:38,960 --> 00:01:41,950
1 Gigabyte aceste zile, 2
gigabytes, sau chiar mult mai mult,

38
00:01:41,950 --> 00:01:44,420
este, în general, prevăzute
pentru un anumit program

39
00:01:44,420 --> 00:01:47,170
în acest fel de formă dreptunghiulară
model conceptual

40
00:01:47,170 --> 00:01:50,860
prin care avem stiva în partea de jos
și o grămadă de alte chestii în partea de sus.

41
00:01:50,860 --> 00:01:53,140
Lucru la foarte de sus
am vazut pe această imagine

42
00:01:53,140 --> 00:01:55,670
înainte, dar niciodată nu a vorbit despre
este așa-numitul segment de text.

43
00:01:55,670 --> 00:01:58,419
Segment text este doar un mod fantezist
de a spune zerouri și cele care

44
00:01:58,419 --> 00:02:01,150
compune programul compilat real.

45
00:02:01,150 --> 00:02:03,910
>> Deci, atunci când dublu-clic
Microsoft Word pe Mac sau PC-ul dvs.,

46
00:02:03,910 --> 00:02:08,030
sau atunci când rulați punct slash Mario pe o
Calculator Linux la fereastra ta terminale,

47
00:02:08,030 --> 00:02:12,460
zerouri și cele care compun
Word sau Mario sunt depozitate temporar

48
00:02:12,460 --> 00:02:16,610
în memoria RAM a computerului în așa-numitul
segment de text pentru un anumit program.

49
00:02:16,610 --> 00:02:19,080
Mai jos, care merge inițializat
și date neinițializate.

50
00:02:19,080 --> 00:02:22,655
Acest lucru este chestii de genul variabile globale,
că noi nu am folosit multe din,

51
00:02:22,655 --> 00:02:24,910
dar uneori ne-am
a avut variabile globale

52
00:02:24,910 --> 00:02:28,819
sau static siruri de caractere definit ca
este greu codificate cuvinte ca "Bună ziua"

53
00:02:28,819 --> 00:02:31,860
care nu sunt luate de la utilizator
care sunt greu codificate în programul tău.

54
00:02:31,860 --> 00:02:34,230
>> Acum, in partea de jos ne
au așa-numitele stivă.

55
00:02:34,230 --> 00:02:37,665
Și stiva, până acum, am fost
folosind pentru ce tipuri de scopuri?

56
00:02:37,665 --> 00:02:39,706

57
00:02:39,706 --> 00:02:40,997
Ce stiva fost folosit pentru?

58
00:02:40,997 --> 00:02:41,160
Da?

59
00:02:41,160 --> 00:02:42,070
>> Audiența: Funcții.

60
00:02:42,070 --> 00:02:43,320
>> David J. MALAN: Pentru funcții?

61
00:02:43,320 --> 00:02:44,980
În ce sens pentru funcții?

62
00:02:44,980 --> 00:02:48,660
>> Audiența: Când apelați o funcție,
Argumentele sunt copiate pe stiva.

63
00:02:48,660 --> 00:02:49,660
>> David J. MALAN: Exact.

64
00:02:49,660 --> 00:02:52,650
Când apelați o funcție, sa
Argumentele sunt copiate pe stiva.

65
00:02:52,650 --> 00:02:56,330
Deci, orice X sau Y sau lui A sau B de
că sunteți trecerea într-o funcție

66
00:02:56,330 --> 00:02:58,680
sunt puse temporar pe
așa-numita stiva,

67
00:02:58,680 --> 00:03:02,000
la fel ca unul din Annenberg
tăvi sală de masă, și, de asemenea lucruri

68
00:03:02,000 --> 00:03:03,190
ca variabile locale.

69
00:03:03,190 --> 00:03:06,290
În cazul în care funcția foo sau de swap-ul
Funcția avea variabile locale,

70
00:03:06,290 --> 00:03:08,602
cum ar fi temperatura, cei doi
ajung pe stiva.

71
00:03:08,602 --> 00:03:11,560
Acum, nu vom vorbi prea mult despre
ei, dar aceste variabile de mediu

72
00:03:11,560 --> 00:03:15,690
în partea de jos am văzut în urmă cu ceva timp, atunci când
Am fost jucându la tastatură o zi

73
00:03:15,690 --> 00:03:20,050
și am început accesarea lucruri
ca argv 100 sau argv 1000,

74
00:03:20,050 --> 00:03:22,320
doar elements-- am uitat
Numere de, dar că

75
00:03:22,320 --> 00:03:24,330
nu ar fi trebuit să fie accesate de către mine.

76
00:03:24,330 --> 00:03:26,581
Am început să văd unele
simboluri ciudate pe ecran.

77
00:03:26,581 --> 00:03:28,330
Acestea au fost așa-numitele
variabilele de mediu

78
00:03:28,330 --> 00:03:32,390
ca setări globale pentru meu
program sau pentru calculatorul meu, nu

79
00:03:32,390 --> 00:03:37,090
nu au legătură cu recenta
bug care am discutat,

80
00:03:37,090 --> 00:03:39,670
Shellshock, care a fost
care afectează destul de câteva calculatoare.

81
00:03:39,670 --> 00:03:42,960
>> Acum în cele din urmă, în centrul atenției astăzi
vom fi în cele din urmă pe heap.

82
00:03:42,960 --> 00:03:44,864
Acesta este un alt segment de memorie.

83
00:03:44,864 --> 00:03:47,030
Și fundamental toate acestea
memorie este aceleasi lucruri.

84
00:03:47,030 --> 00:03:48,040
Este același hardware.

85
00:03:48,040 --> 00:03:49,956
Suntem un fel de
tratarea grupuri diferite

86
00:03:49,956 --> 00:03:51,460
de bytes pentru diferite scopuri.

87
00:03:51,460 --> 00:03:56,540
Heap este, de asemenea, va fi în cazul în care
variabile și memorie pe care le solicita

88
00:03:56,540 --> 00:03:58,810
din sistemul de operare
sunt stocate temporar.

89
00:03:58,810 --> 00:04:01,890
>> Dar există un fel de problemă
aici, ca imagine implică.

90
00:04:01,890 --> 00:04:05,261
Avem un fel de avea două
navele despre a ciocni.

91
00:04:05,261 --> 00:04:08,010
Pentru că așa cum vă folosiți mai mult și mai mult
a stivei, și după cum vom vedea astăzi

92
00:04:08,010 --> 00:04:11,800
mai departe, pe măsură ce utilizați mai mult și mai mult din
morman, cu siguranță lucruri rele s-ar putea întâmpla.

93
00:04:11,800 --> 00:04:15,054
Și într-adevăr, putem induce că
în mod intenționat sau neintenționat.

94
00:04:15,054 --> 00:04:16,970
Deci Cliffhanger trecut
timp a fost acest program,

95
00:04:16,970 --> 00:04:20,570
care nu au servit nici o funcțională
alt scop decât de a demonstra

96
00:04:20,570 --> 00:04:24,750
cum ca un om rău poate lua de fapt,
avantaj de bug-uri în programul cuiva

97
00:04:24,750 --> 00:04:28,460
și preia un program sau chiar un
sistem informatic integral sau server.

98
00:04:28,460 --> 00:04:31,660
Deci, doar pentru a arunca o privire rapidă, tu
observa ca principal în partea de jos

99
00:04:31,660 --> 00:04:34,510
ia în linie de comandă
argumente, ca pe argv.

100
00:04:34,510 --> 00:04:38,480
Și are un apel la o funcție f,
în esență, o funcție fără nume numit

101
00:04:38,480 --> 00:04:40,250
f, și se trece în argv [1].

102
00:04:40,250 --> 00:04:43,960
>> Deci, indiferent de cuvânt a utilizatorului Tipuri de la
prompt după numele acestui program,

103
00:04:43,960 --> 00:04:49,310
și apoi această funcție arbitrară în sus
top, f, are într-un șir, AKA char *,

104
00:04:49,310 --> 00:04:51,720
cum am început să discutăm,
și ea doar o numește "bar".

105
00:04:51,720 --> 00:04:53,310
Dar am putea numi nimic.

106
00:04:53,310 --> 00:04:57,470
Și atunci se declară, în interiorul
f, o serie de personaje

107
00:04:57,470 --> 00:04:59,930
numit C- de 12 astfel de caractere.

108
00:04:59,930 --> 00:05:03,580
>> Acum, de povestea i-am spus
acum un moment, în cazul în care în memorie

109
00:05:03,580 --> 00:05:06,720
este c, sau sunt cele 12
caractere de gând să ajung?

110
00:05:06,720 --> 00:05:07,570
Ca să fie clar.

111
00:05:07,570 --> 00:05:08,070
Da?

112
00:05:08,070 --> 00:05:08,590
>> Audiența: pe stiva.

113
00:05:08,590 --> 00:05:09,420
>> David J. MALAN: pe stiva.

114
00:05:09,420 --> 00:05:10,720
Deci c este o variabilă locală.

115
00:05:10,720 --> 00:05:14,079
Cerem de 12 caractere sau 12 biti.

116
00:05:14,079 --> 00:05:16,120
Cei care vor să ajungă
pe așa-numita stiva.

117
00:05:16,120 --> 00:05:18,530
Acum, în cele din urmă este această altă funcție
care este de fapt destul de util,

118
00:05:18,530 --> 00:05:20,571
dar noi nu am folosit într-adevăr
ea ne, strncopy.

119
00:05:20,571 --> 00:05:21,550

120
00:05:21,550 --> 00:05:25,200
Aceasta înseamnă copie șir, dar
doar pentru n scrisori, n caractere.

121
00:05:25,200 --> 00:05:31,990
Deci, n caractere vor fi
copiate de la bar în c.

122
00:05:31,990 --> 00:05:32,980
Și cât de mulți?

123
00:05:32,980 --> 00:05:34,110
Lungimea bar.

124
00:05:34,110 --> 00:05:36,330
Deci, cu alte cuvinte, că
o linie, strncopy,

125
00:05:36,330 --> 00:05:39,500
se va copia
bar eficient în a c.

126
00:05:39,500 --> 00:05:42,340
>> Acum, doar la fel de anticipa
Morala acestei povești,

127
00:05:42,340 --> 00:05:44,750
ceea ce este potențial problematic aici?

128
00:05:44,750 --> 00:05:49,710
Chiar dacă suntem de verificare lungimea
de bar și se trece în strncopy,

129
00:05:49,710 --> 00:05:53,145
ceea ce este instinctul spune ce este
încă rupt despre acest program?

130
00:05:53,145 --> 00:05:54,410

131
00:05:54,410 --> 00:05:55,220
Da?

132
00:05:55,220 --> 00:05:57,491
>> Audiența: Nu include
cameră pentru caracterul nul.

133
00:05:57,491 --> 00:05:59,990
David J. MALAN: Nu include
cameră pentru caracterul nul.

134
00:05:59,990 --> 00:06:02,073
Potențial, spre deosebire de
practicile din trecut nu ne face chiar

135
00:06:02,073 --> 00:06:04,810
au atât de mult ca un plus de 1 la
găzdui acest caracter nul.

136
00:06:04,810 --> 00:06:06,649
Dar e chiar mai rău decât atât.

137
00:06:06,649 --> 00:06:07,940
Ce altceva putem faptul că nu a făcut?

138
00:06:07,940 --> 00:06:08,432
Da?

139
00:06:08,432 --> 00:06:09,307
>> Audiența: [inaudibil]

140
00:06:09,307 --> 00:06:15,440

141
00:06:15,440 --> 00:06:16,440
David J. MALAN: Perfect.

142
00:06:16,440 --> 00:06:18,490
Am codat greu de 12 destul de arbitrar.

143
00:06:18,490 --> 00:06:19,497

144
00:06:19,497 --> 00:06:21,330
Asta nu este atât de mult
problemă, dar faptul

145
00:06:21,330 --> 00:06:25,630
că nu suntem chiar a verifica dacă
lungimea de bare este mai mică de 12,

146
00:06:25,630 --> 00:06:28,530
caz în care va fi
în condiții de siguranță să-l pună în memoria

147
00:06:28,530 --> 00:06:30,260
numit C pe care le-am alocat.

148
00:06:30,260 --> 00:06:32,960
Într-adevăr, în cazul în bar este ca
20 de caractere,

149
00:06:32,960 --> 00:06:39,010
această funcție pare să fie copierea
20 de personaje din bar în c, astfel

150
00:06:39,010 --> 00:06:41,310
având cel puțin 8 bytes
că aceasta nu ar trebui să fie.

151
00:06:41,310 --> 00:06:42,690
Asta e implicația aici.

152
00:06:42,690 --> 00:06:44,347
>> Deci, pe scurt programul, rupt.

153
00:06:44,347 --> 00:06:45,180
Nu este o astfel de afacere mare.

154
00:06:45,180 --> 00:06:46,360
Poate că veți obține o eroare de segmentare.

155
00:06:46,360 --> 00:06:47,651
Am avut toate bug-uri în programe.

156
00:06:47,651 --> 00:06:50,196
Noi toți ar putea avea bug-uri
în programe chiar acum.

157
00:06:50,196 --> 00:06:51,320
Dar ceea ce este implicația?

158
00:06:51,320 --> 00:06:54,390
Ei bine, aici este o versiune mărită-in de
poza din memoria computerului meu.

159
00:06:54,390 --> 00:06:56,230
Aceasta este partea de jos a stivei meu.

160
00:06:56,230 --> 00:06:59,644
Și, într-adevăr, în partea de jos este ceea ce-i
numit stivă de rutină părinte, un fel de lux

161
00:06:59,644 --> 00:07:00,560
de a spune că e principal.

162
00:07:00,560 --> 00:07:03,772
Așa că oricine numit funcția
f că vorbim despre.

163
00:07:03,772 --> 00:07:05,230
Deci, aceasta este baza stivei.

164
00:07:05,230 --> 00:07:06,640
Adresa de returnare este ceva nou.

165
00:07:06,640 --> 00:07:08,810
A fost mereu acolo,
fost întotdeauna în acea imagine.

166
00:07:08,810 --> 00:07:10,440
Noi doar nu a atras atenția să-l.

167
00:07:10,440 --> 00:07:15,290
Pentru că se pare că modul în care funcționează este c
că, atunci când o funcție apelează o alta,

168
00:07:15,290 --> 00:07:18,780
nu numai că argumentele pentru care
Funcția împinși pe stiva,

169
00:07:18,780 --> 00:07:22,470
nu numai local, funcția de
variabile împinși pe stiva,

170
00:07:22,470 --> 00:07:26,820
ceva numit o adresă de retur
De asemenea, se pune pe stiva.

171
00:07:26,820 --> 00:07:33,330
Mai precis, în cazul în care apelurile principale Foo, a principalelor
adresa proprie în memorie, bou ceva,

172
00:07:33,330 --> 00:07:38,240
în mod eficient este pus pe stiva
astfel că atunci când se face f executarea ei

173
00:07:38,240 --> 00:07:43,630
știe unde să sări înapoi la text
segment în scopul de a continua executarea.

174
00:07:43,630 --> 00:07:47,760
>> Deci, dacă noi suntem aici conceptual,
în principal, atunci f este chemat.

175
00:07:47,760 --> 00:07:50,200
Cum f știe cine
la un control de mână înapoi?

176
00:07:50,200 --> 00:07:52,020
Ei bine, acest mic
pesmet în roșu aici,

177
00:07:52,020 --> 00:07:54,978
numita adresa de revenire, doar
verificări, ceea ce este că adresa de retur?

178
00:07:54,978 --> 00:07:57,039
Oh, lasă-mă să sări înapoi la principal aici.

179
00:07:57,039 --> 00:07:59,080
Si asta e un pic
de o simplificare,

180
00:07:59,080 --> 00:08:00,750
deoarece zerourile și cele
pentru principal sunt punct de vedere tehnic

181
00:08:00,750 --> 00:08:01,967
aici, în segmentul de tehnologie.

182
00:08:01,967 --> 00:08:03,800
Dar asta e ideea. f
doar trebuie să știe ce

183
00:08:03,800 --> 00:08:06,680
la care controlul în cele din urmă se întoarce.

184
00:08:06,680 --> 00:08:09,790
>> Dar modul în care calculatoarele
s-au pus de mult lucruri

185
00:08:09,790 --> 00:08:12,320
ca variabile locale și
argumente este ca aceasta.

186
00:08:12,320 --> 00:08:17,180
Deci, în partea de sus a acestei imagini în
albastru este cadrul stiva pentru f, astfel încât toate

187
00:08:17,180 --> 00:08:19,630
de memorie care f
în mod special este utilizarea.

188
00:08:19,630 --> 00:08:22,990
Deci prin urmare, observăm că
bar este în această imagine.

189
00:08:22,990 --> 00:08:23,980
Bar a fost argumentul său.

190
00:08:23,980 --> 00:08:27,240
Și am susținut că argumentele pentru
Funcțiile împinși pe stiva.

191
00:08:27,240 --> 00:08:29,910
Și c, desigur, este
De asemenea, în această imagine.

192
00:08:29,910 --> 00:08:33,520
>> Și doar pentru scopuri de notație,
observa în colțul din stânga sus

193
00:08:33,520 --> 00:08:37,020
este ceea ce s-ar fi c suport 0 și
apoi ușor în jos la dreapta

194
00:08:37,020 --> 00:08:38,220
este c suport 11.

195
00:08:38,220 --> 00:08:41,240
Deci, cu alte cuvinte, vă puteți imagina
că există o grilă de bytes

196
00:08:41,240 --> 00:08:44,380
acolo, prima dintre acestea fiind
din stânga sus, de care partea de jos

197
00:08:44,380 --> 00:08:48,360
este ultima din cele 12 bytes.

198
00:08:48,360 --> 00:08:49,930
>> Dar acum, încercați pentru a derula înainte.

199
00:08:49,930 --> 00:08:55,580
Ce se va întâmpla dacă vom trece
într-un bar șir care este mai mult de c?

200
00:08:55,580 --> 00:08:59,130
Și nu ne verifica dacă
este într-adevăr mai mult de 12.

201
00:08:59,130 --> 00:09:03,146
Care parte din această imagine este de gând să
te schimbată de octeți 0, 1, 2, 3,

202
00:09:03,146 --> 00:09:07,890
dot dot dot, 11, și apoi
rău, 12, 13 și 19?

203
00:09:07,890 --> 00:09:11,820
Ce se va întâmpla aici,
dacă deduce din ordinea

204
00:09:11,820 --> 00:09:14,790
care c este 0 suport pe partea de sus
și c suport 11 este un fel de jos

205
00:09:14,790 --> 00:09:15,812
spre dreapta?

206
00:09:15,812 --> 00:09:16,796
Da?

207
00:09:16,796 --> 00:09:19,260
>> Audiența: Ei bine, se întâmplă
pentru a suprascrie char * bar.

208
00:09:19,260 --> 00:09:22,260
>> David J. MALAN: Da, se pare ca
ai de gând să suprascrie char * bar.

209
00:09:22,260 --> 00:09:26,245
Și mai rău, dacă vă trimite într-un foarte lung
șir, ceea ce s-ar putea suprascrie chiar?

210
00:09:26,245 --> 00:09:27,460

211
00:09:27,460 --> 00:09:28,570
Adresa de returnare.

212
00:09:28,570 --> 00:09:31,380
Ceea ce, din nou, este la fel ca un
pesmet pentru a spune programului în cazul în care

213
00:09:31,380 --> 00:09:34,060
pentru a merge înapoi la când f
se face fiind numit.

214
00:09:34,060 --> 00:09:37,140
>> Deci, ce baietii rai de obicei, face
este în cazul în care au venit peste un program de

215
00:09:37,140 --> 00:09:41,290
că sunt curios dacă este
de exploatat, buggy în așa fel

216
00:09:41,290 --> 00:09:43,550
că el sau ea poate lua
profitând de faptul că bug-ul,

217
00:09:43,550 --> 00:09:45,720
în general, ei nu primesc
acest drept pentru prima dată.

218
00:09:45,720 --> 00:09:48,590
Ei doar începe să trimiteți, de exemplu,
siruri de caractere aleatorii în programul tău,

219
00:09:48,590 --> 00:09:50,260
dacă la tastatură,
sau sincer ei, probabil,

220
00:09:50,260 --> 00:09:52,740
scrie un mic program pentru doar
genera în mod automat siruri de caractere,

221
00:09:52,740 --> 00:09:55,430
și începe să trage cu privire la programul dumneavoastră de
trimiterea în o mulțime de diferite intrări

222
00:09:55,430 --> 00:09:56,340
la lungimi diferite.

223
00:09:56,340 --> 00:09:58,990
>> De îndată ce se blochează de program,
asta e un lucru uimitor.

224
00:09:58,990 --> 00:10:01,020
Pentru că înseamnă că
sau ea a descoperit

225
00:10:01,020 --> 00:10:02,660
ceea ce este, probabil, într-adevăr, o problemă.

226
00:10:02,660 --> 00:10:05,830
Și atunci ei pot obține mai inteligent
și începe concentrându-se mai strict

227
00:10:05,830 --> 00:10:07,420
cu privire la modul de a exploata bug.

228
00:10:07,420 --> 00:10:11,480
În special, ceea ce el sau ea s-ar putea
faceți este să trimiteți, în cel mai bun caz, salut.

229
00:10:11,480 --> 00:10:12,210
Nu e mare lucru.

230
00:10:12,210 --> 00:10:14,750
Este un șir care este suficient de scurt.

231
00:10:14,750 --> 00:10:18,100
Dar dacă el sau ea trimite,
și vom generaliza ca,

232
00:10:18,100 --> 00:10:20,890
atac code-- așa zerouri
și cele care fac lucruri

233
00:10:20,890 --> 00:10:25,150
ca rm-rf, care elimina tot
de pe hard disk sau trimite spam-uri

234
00:10:25,150 --> 00:10:27,000
sau cumva ataca masina?

235
00:10:27,000 --> 00:10:29,570
>> Deci, dacă fiecare dintre acestea
literele A reprezintă doar,

236
00:10:29,570 --> 00:10:32,380
conceptual, atac, atac,
atac, atac, un cod rău

237
00:10:32,380 --> 00:10:36,410
că altcineva a scris, dar
în cazul în care persoana este suficient de inteligent

238
00:10:36,410 --> 00:10:40,790
pentru a nu numai să includă toate
acestor rm-RFS, dar, de asemenea

239
00:10:40,790 --> 00:10:46,100
au ultimele sale câteva bytes
fie un număr care corespunde

240
00:10:46,100 --> 00:10:50,540
la adresa lui
sau codul ei de atac propriu

241
00:10:50,540 --> 00:10:53,820
că el sau ea a trecut în doar
furnizându-i în linia de,

242
00:10:53,820 --> 00:10:58,760
puteți păcăli în mod eficient computerul
în observe când f se face executarea,

243
00:10:58,760 --> 00:11:02,400
oh, e timpul pentru mine să sar
înapoi la adresa de returnare roșu.

244
00:11:02,400 --> 00:11:06,070
Dar pentru că el sau ea are într-un fel
suprapus că adresa expeditorului

245
00:11:06,070 --> 00:11:09,602
cu numărul lor,
și acestea sunt destul de inteligent

246
00:11:09,602 --> 00:11:11,560
pentru a fi configurat ca
număr să se refere, în timp ce

247
00:11:11,560 --> 00:11:13,740
a se vedea în partea de sus super-
colțul din stânga-acolo,

248
00:11:13,740 --> 00:11:18,020
adresa efectivă în anii calculator
memoria unora dintre codul lor atac,

249
00:11:18,020 --> 00:11:21,740
un tip rău pot păcăli computerul
în executarea propriu cod lui sau a ei.

250
00:11:21,740 --> 00:11:23,700
>> Și asta cod, din nou, poate fi orice.

251
00:11:23,700 --> 00:11:26,120
Se numește în general
Codul coajă, care este doar

252
00:11:26,120 --> 00:11:29,030
un fel de a spune că nu este
în general, ceva la fel de simplu ca rm-rf.

253
00:11:29,030 --> 00:11:32,340
Este de fapt ceva de genul Bash,
sau un program de real pe care-l dă

254
00:11:32,340 --> 00:11:37,230
sau de control o programatic pentru a executa
orice altceva care doresc să.

255
00:11:37,230 --> 00:11:40,210
Deci, pe scurt, toate astea
derivă din faptul simplu

256
00:11:40,210 --> 00:11:44,490
că această problemă a implicat nu verifica
limitele de matrice dumneavoastră.

257
00:11:44,490 --> 00:11:47,250
Și pentru că modul în care
computere lucru este că ei

258
00:11:47,250 --> 00:11:49,430
folosesc stiva de
în mod eficient, conceptual,

259
00:11:49,430 --> 00:11:54,830
de jos in sus, dar apoi elementele
ai împinge pe stiva crește de sus în jos,

260
00:11:54,830 --> 00:11:56,624
acest lucru este incredibil de problematic.

261
00:11:56,624 --> 00:11:58,290
Acum, există modalități de a lucra în jurul acest lucru.

262
00:11:58,290 --> 00:12:00,800
Și sincer, sunt limbi
cu care să lucreze în jurul acestui.

263
00:12:00,800 --> 00:12:03,100
Java este imun, de exemplu,
la această problemă.

264
00:12:03,100 --> 00:12:04,110
Pentru că ei nu vă dau indicii.

265
00:12:04,110 --> 00:12:05,943
Ei nu-ți dau
adrese de memorie directe.

266
00:12:05,943 --> 00:12:08,560
Deci, cu această putere pe care o avem
pentru a atinge nimic din memorie

267
00:12:08,560 --> 00:12:11,580
Vrem vine, desigur, de mare risc.

268
00:12:11,580 --> 00:12:12,430
>> Deci, ține un ochi.

269
00:12:12,430 --> 00:12:14,596
În cazul în care, sincer, în lunile
sau anii care vor veni, oricand

270
00:12:14,596 --> 00:12:17,740
ai citit despre unele exploatare
de un program sau un server,

271
00:12:17,740 --> 00:12:22,370
dacă ați văzut vreodată un indiciu de ceva
ca un atac buffer overflow,

272
00:12:22,370 --> 00:12:25,390
sau stivă overflow este un alt tip
de atac, similară în spirit,

273
00:12:25,390 --> 00:12:28,770
mult ca inspiră site-ului
nume, dacă îl cunoașteți,

274
00:12:28,770 --> 00:12:33,170
totul vorbește despre doar
revărsare mărimea unele caractere

275
00:12:33,170 --> 00:12:36,200
matrice sau matrice unele mai mult, în general.

276
00:12:36,200 --> 00:12:38,822
Orice întrebări, atunci, pe aceasta?

277
00:12:38,822 --> 00:12:39,780
Nu incercati asta acasa.

278
00:12:39,780 --> 00:12:41,620

279
00:12:41,620 --> 00:12:42,300
>> În regulă.

280
00:12:42,300 --> 00:12:47,270
Deci, malloc până acum a fost noul nostru
prieten în care să putem aloca memorie

281
00:12:47,270 --> 00:12:50,540
că nu știm în mod necesar în
avansa pe care ne-o dorim, asa ca nu avem

282
00:12:50,540 --> 00:12:52,920
codul greu în nostru
Numerele de programe, cum ar fi 12.

283
00:12:52,920 --> 00:12:55,550
Odată ce utilizatorul ne spune cât de mult
Date el sau ea vrea să de intrare,

284
00:12:55,550 --> 00:12:58,000
putem malloc că multă memorie.

285
00:12:58,000 --> 00:13:01,484
>> Deci, malloc se pare, la
măsură am fost folosind-o,

286
00:13:01,484 --> 00:13:03,900
explicit ultimul timp, și apoi
voi au fost folosind-o

287
00:13:03,900 --> 00:13:08,160
pentru getString în necunoștință de
câteva săptămâni, toate de memorie malloc lui

288
00:13:08,160 --> 00:13:09,820
vine de la așa-numita grămadă.

289
00:13:09,820 --> 00:13:13,852
Și acesta este motivul pentru getstring, de exemplu,
poate aloca memorie dinamic

290
00:13:13,852 --> 00:13:16,060
fără a ști de ce ești
O să tastați în avans,

291
00:13:16,060 --> 00:13:21,520
te dai înapoi un pointer la care memoria,
și că memoria este încă a ta de a păstra,

292
00:13:21,520 --> 00:13:24,080
chiar și după getString întoarce.

293
00:13:24,080 --> 00:13:27,450
Deoarece amintesc după toate că
stiva este în mod constant merge în sus și în jos,

294
00:13:27,450 --> 00:13:27,950
în sus și în jos.

295
00:13:27,950 --> 00:13:30,230
Și, de îndată ce merge
jos, înseamnă că orice memorie

296
00:13:30,230 --> 00:13:33,030
această funcție ar trebui folosit
nu fi folosit de oricine altcineva.

297
00:13:33,030 --> 00:13:34,570
Este valori de gunoi acum.

298
00:13:34,570 --> 00:13:36,120
>> Dar heap este de până aici.

299
00:13:36,120 --> 00:13:39,360
Și ce e frumos despre malloc este că
când malloc alocă memorie de până aici,

300
00:13:39,360 --> 00:13:42,070
nu este afectat, pentru
cea mai mare parte, prin stivă.

301
00:13:42,070 --> 00:13:46,000
Și astfel orice funcție poate accesa
memorie care a fost malloc'd,

302
00:13:46,000 --> 00:13:49,120
chiar printr-o funcție ca getstring,
chiar și după ce acesta este returnat.

303
00:13:49,120 --> 00:13:51,700
>> Acum, reciproca de malloc este gratuit.

304
00:13:51,700 --> 00:13:53,900
Și într-adevăr, regula va
nevoie pentru a începe de adoptare a

305
00:13:53,900 --> 00:13:58,950
este orice, orice, orice dată când utilizați malloc
trebuie să te folosească gratuit, în cele din urmă,

306
00:13:58,950 --> 00:14:00,280
pe care același indicator.

307
00:14:00,280 --> 00:14:03,289
În tot acest timp am fost scris
buggy, cod buggy, pentru mai multe motive.

308
00:14:03,289 --> 00:14:05,580
Dar dintre care unul a fost
folosind biblioteca CS50, care

309
00:14:05,580 --> 00:14:09,010
în sine este în mod deliberat
buggy, ea pierderi de memorie.

310
00:14:09,010 --> 00:14:11,410
De fiecare dată când am sunat getstring
în ultimele câteva săptămâni

311
00:14:11,410 --> 00:14:13,870
cerem de operare
sistem, Linux, pentru memorie.

312
00:14:13,870 --> 00:14:15,780
Și tu nu au mai dat o dată înapoi.

313
00:14:15,780 --> 00:14:17,730
Și acest lucru nu este, în
practica, un lucru bun.

314
00:14:17,730 --> 00:14:20,330
>> Și Valgrind, unul dintre
instrumente introduse în PSET 4,

315
00:14:20,330 --> 00:14:22,900
este totul despre ajutându-vă
acum găsi bug-uri de genul asta.

316
00:14:22,900 --> 00:14:27,060
Dar, din fericire pentru PSET 4 nu ai nevoie de
să utilizeze biblioteca CS50 sau getString.

317
00:14:27,060 --> 00:14:31,220
Deci, orice bug-uri legate de memorie sunt
în cele din urmă va fi a ta.

318
00:14:31,220 --> 00:14:34,060
>> Deci, malloc este mai mult decât
convenabil pentru acest scop.

319
00:14:34,060 --> 00:14:37,420
Putem de fapt, acum rezolva
fundamental diferite probleme,

320
00:14:37,420 --> 00:14:41,640
și de a rezolva în mod fundamental mai multe probleme
eficient ca pe promisiunea săptămână la zero lui.

321
00:14:41,640 --> 00:14:44,720
Până în prezent aceasta este cea mai sexy
structură de date care le-am avut.

322
00:14:44,720 --> 00:14:47,804
Și de structură de date doar vreau sa spun
o cale de memorie conceptualiza

323
00:14:47,804 --> 00:14:50,720
într-un mod care merge dincolo de doar spun,
aceasta este o int, acesta este un char.

324
00:14:50,720 --> 00:14:52,930
Putem începe la lucruri de grup împreună.

325
00:14:52,930 --> 00:14:54,460
>> Deci, o serie arata ca aceasta.

326
00:14:54,460 --> 00:14:57,270
Și ceea ce a fost esențial în aproximativ o
matrice este că vă oferă

327
00:14:57,270 --> 00:14:59,724
back-to-back bucăți de
memorie, fiecare dintre acestea

328
00:14:59,724 --> 00:15:02,765
va fi de același tip, int,
int, int, int, sau char, char, char,

329
00:15:02,765 --> 00:15:03,330
char.

330
00:15:03,330 --> 00:15:04,496
Dar există câteva dezavantaje.

331
00:15:04,496 --> 00:15:06,570
Aceasta, de exemplu, este
o serie de dimensiuni șase.

332
00:15:06,570 --> 00:15:10,650
Să presupunem că vă umple acest tablou cu șase
numere și apoi, din diverse motive,

333
00:15:10,650 --> 00:15:13,187
dvs. de utilizator vrea să dea
te un număr al șaptelea.

334
00:15:13,187 --> 00:15:14,020
Unde l-ai pus?

335
00:15:14,020 --> 00:15:15,490

336
00:15:15,490 --> 00:15:18,990
>> Care este soluția în cazul în care aveți
a creat o matrice pe stiva,

337
00:15:18,990 --> 00:15:22,030
de exemplu, doar cu săptămâna
două notație că am introdus,

338
00:15:22,030 --> 00:15:23,730
de paranteze pătrate, cu un număr de interior?

339
00:15:23,730 --> 00:15:25,160

340
00:15:25,160 --> 00:15:27,260
Ei bine, ai șase
numere în aceste cutii.

341
00:15:27,260 --> 00:15:28,530
Ce-ar fi instinctele tale?

342
00:15:28,530 --> 00:15:29,973
În cazul în care ai vrea să-l puneți?

343
00:15:29,973 --> 00:15:30,860
>> Audiența: [inaudibil]

344
00:15:30,860 --> 00:15:31,315
>> David J. MALAN: Imi pare rau?

345
00:15:31,315 --> 00:15:32,380
>> Audiența: Pune-l pe final.

346
00:15:32,380 --> 00:15:33,796
>> David J. MALAN: Pune-l pe final.

347
00:15:33,796 --> 00:15:35,880
Deci, doar pe la dreapta,
in afara de aceasta cutie.

348
00:15:35,880 --> 00:15:38,710
Care ar fi frumos, dar ea
se dovedește că nu poți face asta.

349
00:15:38,710 --> 00:15:41,350
Pentru că dacă tu nu ai cerut
pentru acest segment de memorie,

350
00:15:41,350 --> 00:15:44,490
ar putea fi de o coincidență faptul că această
este utilizat de către o altă variabilă

351
00:15:44,490 --> 00:15:45,030
cu totul.

352
00:15:45,030 --> 00:15:49,210
Gandeste-te o săptămână sau asa ca atunci cand am pus
în numele Zamyla și Davin și Gabe

353
00:15:49,210 --> 00:15:49,930
în memorie.

354
00:15:49,930 --> 00:15:51,638
Ei au fost literalmente
spate în spate la spate.

355
00:15:51,638 --> 00:15:53,550
Deci, nu putem neapărat
încredere că tot ceea ce a

356
00:15:53,550 --> 00:15:55,800
aici este disponibil pentru mine de a utiliza.

357
00:15:55,800 --> 00:15:56,990
>> Deci, ce altceva ar putea face?

358
00:15:56,990 --> 00:16:00,282
Ei bine, odată ce și dea seama
au nevoie de o serie de dimensiuni șapte,

359
00:16:00,282 --> 00:16:02,490
ai putea crea doar un
matrice de dimensiune șapte apoi utilizați

360
00:16:02,490 --> 00:16:05,950
pentru o buclă sau o buclă în timp ce,
copiați-l în noua matrice,

361
00:16:05,950 --> 00:16:09,680
și apoi într-un fel chiar a scăpa de
această matrice sau doar nu o mai utilizați.

362
00:16:09,680 --> 00:16:12,130
Dar asta nu e deosebit de eficient.

363
00:16:12,130 --> 00:16:15,340
Pe scurt, tablouri nu lasa
tu redimensiona dinamic.

364
00:16:15,340 --> 00:16:17,900
>> Deci, pe de o parte te
cu acces aleator, care este uimitor.

365
00:16:17,900 --> 00:16:20,108
Pentru că ne permite să facem lucruri
ca divide și cuceri,

366
00:16:20,108 --> 00:16:23,100
binar de căutare, toate de care ne-am
a vorbit despre pe ecran aici.

367
00:16:23,100 --> 00:16:24,950
Dar vopsea te într-un colț.

368
00:16:24,950 --> 00:16:27,810
De îndată ce te-a lovit
la sfârșitul anului matrice dumneavoastră,

369
00:16:27,810 --> 00:16:29,980
ce trebuie să faci un foarte
operație costisitoare

370
00:16:29,980 --> 00:16:33,910
sau scrie o grămadă de cod
să se ocupe acum de această problemă.

371
00:16:33,910 --> 00:16:36,680
>> Deci, ce se întâmplă dacă în loc am avut
ceva numit-o listă,

372
00:16:36,680 --> 00:16:38,820
sau o listă legată în special?

373
00:16:38,820 --> 00:16:41,930
Ce dacă în loc de a avea
dreptunghiuri spate în spate în spate,

374
00:16:41,930 --> 00:16:45,730
avem dreptunghiuri care lasă un pic
pic de loc de manevră între ele?

375
00:16:45,730 --> 00:16:49,670
Și chiar dacă mi-am atras acest
imagine sau adaptat această imagine

376
00:16:49,670 --> 00:16:54,696
de la unul dintre textele aici pentru a reveni la
spate în spate foarte ordonat, în realitate,

377
00:16:54,696 --> 00:16:56,820
unul dintre aceste dreptunghiuri
ar putea fi aici în memorie.

378
00:16:56,820 --> 00:16:58,028
Una dintre ele ar putea fi de până aici.

379
00:16:58,028 --> 00:17:00,420
Una dintre ele ar putea fi de până aici,
aici, și așa mai departe.

380
00:17:00,420 --> 00:17:02,910
>> Dar dacă ne-am desenat,
în acest caz, săgeți

381
00:17:02,910 --> 00:17:05,650
care se leagă într-un fel aceste
dreptunghiuri împreună?

382
00:17:05,650 --> 00:17:08,170
Într-adevăr, am văzut o tehnică
încarnare a unei săgeți.

383
00:17:08,170 --> 00:17:09,839

384
00:17:09,839 --> 00:17:13,710
Ce am folosit în ultimii ani
zile în care, sub capota,

385
00:17:13,710 --> 00:17:15,210
este reprezentativ pentru o săgeată?

386
00:17:15,210 --> 00:17:16,290

387
00:17:16,290 --> 00:17:17,349
Un pointer, corect?

388
00:17:17,349 --> 00:17:19,780
>> Și ce dacă, în loc de
doar stochează numerele,

389
00:17:19,780 --> 00:17:23,130
cum ar fi 9, 17, 22, 26, 34,
ceea ce, dacă noi nu este stocat

390
00:17:23,130 --> 00:17:27,079
doar un număr, ci un pointer
lângă fiecare astfel de număr?

391
00:17:27,079 --> 00:17:30,690
Așa că de mult ca tine ar firul o
ac printr-o grămadă de material,

392
00:17:30,690 --> 00:17:32,950
lucrurile într-un fel de legare
împreună, în mod similar se poate

393
00:17:32,950 --> 00:17:35,550
noi cu indicii, ar fi
încarnat de săgeți aici,

394
00:17:35,550 --> 00:17:38,550
fel de a tese împreună
aceste dreptunghiuri individuale

395
00:17:38,550 --> 00:17:41,780
prin utilizarea în mod eficient un pointer
lângă fiecare număr care

396
00:17:41,780 --> 00:17:46,065
indică un numar viitor, care
subliniază, la rândul său, un numar viitor?

397
00:17:46,065 --> 00:17:47,940
Cu alte cuvinte, ce
dacă ne-am dorit de fapt

398
00:17:47,940 --> 00:17:49,820
să pună în aplicare ceva de genul asta?

399
00:17:49,820 --> 00:17:53,610
Ei bine, din păcate, aceste dreptunghiuri,
cel puțin unul cu 9, 17, 22,

400
00:17:53,610 --> 00:17:57,040
și așa mai departe, acestea nu mai sunt
pătrate frumos cu numere unice.

401
00:17:57,040 --> 00:17:59,960
De jos, dreptunghi
9 de mai jos, de exemplu,

402
00:17:59,960 --> 00:18:04,330
reprezinta ceea ce ar trebui să
să fie un pointer, 32 de biți.

403
00:18:04,330 --> 00:18:09,460
Acum, eu nu sunt încă conștienți de orice tip de date
în C, care vă oferă nu numai un int

404
00:18:09,460 --> 00:18:11,630
dar un pointer cu totul.

405
00:18:11,630 --> 00:18:15,020
>> Deci, care este solutia, dacă vrem
pentru a inventa propria noastră răspuns la acest lucru?

406
00:18:15,020 --> 00:18:15,760
Da?

407
00:18:15,760 --> 00:18:16,640
>> Audiența: [inaudibil]

408
00:18:16,640 --> 00:18:17,360
>> David J. MALAN: Ce-i asta?

409
00:18:17,360 --> 00:18:17,880
>> Audiența: structura noua.

410
00:18:17,880 --> 00:18:19,590
>> David J. MALAN: Da, așa că de ce
nu ne-am crea o nouă structură,

411
00:18:19,590 --> 00:18:20,920
sau într-C, o struct?

412
00:18:20,920 --> 00:18:25,990
Am văzut structs înainte, dacă pentru scurt timp,
în cazul în care ne-am ocupat cu o structură de student

413
00:18:25,990 --> 00:18:27,780
ca aceasta, care a avut un nume și o casă.

414
00:18:27,780 --> 00:18:31,980
În PSET 3 Breakout ați utilizat un întreg
buchet de GRect structs-- și GOvals

415
00:18:31,980 --> 00:18:34,810
că Stanford creat pentru a
informații grup împreună.

416
00:18:34,810 --> 00:18:38,580
Deci, dacă am lua această aceeași idee de
cuvintele cheie "typedef" și "struct"

417
00:18:38,580 --> 00:18:42,890
și apoi unele chestii-elev specific,
și să evolueze în acest următoarele:

418
00:18:42,890 --> 00:18:46,210
typedef struct node-- și nod este
doar un informatică foarte generic

419
00:18:46,210 --> 00:18:49,980
Termenul pentru ceva într-o structură de date,
un recipient într-o structură de date.

420
00:18:49,980 --> 00:18:53,900
Un nod eu pretind va avea
un int n, total simplu,

421
00:18:53,900 --> 00:18:58,810
și apoi un pic mai criptic,
această a doua linie, nod struct * viitor.

422
00:18:58,810 --> 00:19:01,300
Dar, în termeni tehnici mai puțin,
ceea ce este că a doua linie

423
00:19:01,300 --> 00:19:02,980
de cod în interiorul acolade?

424
00:19:02,980 --> 00:19:03,737
Da?

425
00:19:03,737 --> 00:19:04,851
>> Audiența: [inaudibil]

426
00:19:04,851 --> 00:19:06,600
David J. MALAN: A
pointer la un alt nod.

427
00:19:06,600 --> 00:19:09,910
Deci, desigur, sintaxa un pic criptic.

428
00:19:09,910 --> 00:19:13,250
Dar dacă l-ai citit literal,
următor este numele unei variabile.

429
00:19:13,250 --> 00:19:14,410
Care este tipul de date?

430
00:19:14,410 --> 00:19:18,206
Este un pic verbose acest timp,
dar e de nod struct tip *.

431
00:19:18,206 --> 00:19:22,960
De fiecare dată când am văzut ceva stele, care
înseamnă că este un pointer la acest tip de date.

432
00:19:22,960 --> 00:19:26,810
Deci, data viitoare este aparent o
pointer la un nod struct.

433
00:19:26,810 --> 00:19:28,310
>> Acum, ceea ce este un nod struct?

434
00:19:28,310 --> 00:19:31,044
Ei bine, observați ce vedeți pe cei
aceleași cuvinte de la dreapta sus.

435
00:19:31,044 --> 00:19:33,960
Și într-adevăr, veți vedea, de asemenea, cuvântul
"Nod" aici, la stânga jos.

436
00:19:33,960 --> 00:19:35,640
Și aceasta este de fapt doar o comoditate.

437
00:19:35,640 --> 00:19:39,930
Observați că în definiția noastră de student
acolo este cuvântul "elev" doar o singură dată.

438
00:19:39,930 --> 00:19:42,510
Și asta pentru că un elev
obiect nu a fost auto-referențială.

439
00:19:42,510 --> 00:19:45,340
Nu e nimic în interiorul unui elev
care trebuie să indice un alt student,

440
00:19:45,340 --> 00:19:45,610
persay.

441
00:19:45,610 --> 00:19:47,630
Asta ar fi un fel de
ciudat în lumea reală.

442
00:19:47,630 --> 00:19:50,880
>> Dar, cu un nod într-o legătură
Lista, noi vrem un nod

443
00:19:50,880 --> 00:19:53,970
să fie referențial pentru un obiect similar.

444
00:19:53,970 --> 00:19:57,900
Și astfel observa schimbarea de aici nu este
doar ceea ce este în interiorul acolade.

445
00:19:57,900 --> 00:20:00,800
Dar vom adăuga cuvântul "nod"
în partea de sus, precum și

446
00:20:00,800 --> 00:20:02,930
adăugându-l la partea de jos
în loc de "elev".

447
00:20:02,930 --> 00:20:06,000
Și acesta este doar un detaliu tehnic
astfel încât, din nou, structura de date

448
00:20:06,000 --> 00:20:11,380
poate fi auto-referențială, astfel încât o
nod poate indica un alt astfel de nod.

449
00:20:11,380 --> 00:20:13,840
>> Deci, ce este aceasta în cele din urmă
va însemna pentru noi?

450
00:20:13,840 --> 00:20:17,560
Ei bine, unul, chestia asta interior
este conținutul nod noastre.

451
00:20:17,560 --> 00:20:19,360
Acest lucru aici,
dreapta sus, este doar atât

452
00:20:19,360 --> 00:20:20,860
că, din nou, ne putem referi la noi înșine.

453
00:20:20,860 --> 00:20:23,401
Și atunci lucrurile exterior,
chiar dacă nodul este un termen nou,

454
00:20:23,401 --> 00:20:25,500
poate, este încă
la fel ca elev și ce

455
00:20:25,500 --> 00:20:27,520
a fost sub capota din SPL.

456
00:20:27,520 --> 00:20:31,095
>> Deci, dacă am vrut acum să înceapă
punerea în aplicare a acestei liste legate,

457
00:20:31,095 --> 00:20:33,220
Cum am putea traduce
ceva de genul asta de cod?

458
00:20:33,220 --> 00:20:35,350
Ei bine, hai sa vedem un
exemplu de program care

459
00:20:35,350 --> 00:20:36,840
de fapt utilizează o listă de legat.

460
00:20:36,840 --> 00:20:40,870
Printre cod de distribuție de astăzi
este un program numită lista Zero.

461
00:20:40,870 --> 00:20:44,980
Și dacă am alerga aceasta am creat un super-
GUI simplu, Interfață grafică pentru utilizator,

462
00:20:44,980 --> 00:20:46,460
dar este de fapt doar printf.

463
00:20:46,460 --> 00:20:50,930
Și acum mi-am dat un meniu câteva
options-- Delete, Insert, Căutare,

464
00:20:50,930 --> 00:20:51,750
și Traverse.

465
00:20:51,750 --> 00:20:52,630
Și ieși.

466
00:20:52,630 --> 00:20:55,970
Acestea sunt operațiuni de doar comune cu privire la un
structura de date cunoscut ca o listă de link.

467
00:20:55,970 --> 00:20:58,409
>> Acum, Delete se va
șterge un număr din lista.

468
00:20:58,409 --> 00:21:00,200
Introduceți va adăuga
un număr la lista.

469
00:21:00,200 --> 00:21:02,181
Căutare este de gând să se uite
pentru un număr în listă.

470
00:21:02,181 --> 00:21:04,930
Și traverse este doar un mod fantezist
de a spune, mers pe jos prin listă,

471
00:21:04,930 --> 00:21:06,245
imprimare-l, dar asta este.

472
00:21:06,245 --> 00:21:07,720
Nu-l schimba în niciun fel.

473
00:21:07,720 --> 00:21:08,570
>> Așa că hai să încercăm.

474
00:21:08,570 --> 00:21:10,160
Să mergem mai departe și de tip 2.

475
00:21:10,160 --> 00:21:12,710
Și apoi am de gând să
introduce numărul, spune 9.

476
00:21:12,710 --> 00:21:13,620
Enter.

477
00:21:13,620 --> 00:21:17,480
Și acum programul meu este doar
programat să spun, lista este acum 9.

478
00:21:17,480 --> 00:21:20,190
Acum, dacă am merge mai departe și
introduceți din nou, să

479
00:21:20,190 --> 00:21:23,680
mă duc mai departe și zoom out și de tip în 17.

480
00:21:23,680 --> 00:21:25,770
Acum, lista mea este 9, atunci 17.

481
00:21:25,770 --> 00:21:27,750
Dacă fac introduce din nou, să sărim unul.

482
00:21:27,750 --> 00:21:32,400
În loc de 22, ca pe imaginea care le-am
au uitat la aici, lasă-mă să sară înainte

483
00:21:32,400 --> 00:21:34,630
și introduceți 26 următor.

484
00:21:34,630 --> 00:21:36,230
Așa că am de gând să tastați 26.

485
00:21:36,230 --> 00:21:37,755
Lista este ca ma astept.

486
00:21:37,755 --> 00:21:40,630
Dar acum, doar pentru a vedea dacă acest cod
va fi flexibil, lasă-mă acum

487
00:21:40,630 --> 00:21:43,520
tip 22, care cel puțin
conceptual, dacă suntem

488
00:21:43,520 --> 00:21:46,520
menținându acest sortate, care este într-adevăr
Va fi un alt obiectiv chiar acum,

489
00:21:46,520 --> 00:21:48,690
ar trebui să meargă în între 17 și 26.

490
00:21:48,690 --> 00:21:50,270
Așa că am lovit Enter.

491
00:21:50,270 --> 00:21:51,380
Într-adevăr, care funcționează.

492
00:21:51,380 --> 00:21:54,950
Iar acum lasă-mă să introduceți
trecut, pe imaginea, 34.

493
00:21:54,950 --> 00:21:55,450
>> În regulă.

494
00:21:55,450 --> 00:21:58,980
Deci, de acum lasă-mă să stipuleze că
Ștergeți și Traverse și Căutare fac,

495
00:21:58,980 --> 00:21:59,760
în fapt, locul de muncă.

496
00:21:59,760 --> 00:22:04,180
De fapt, dacă am fugi de căutare, să
caută numărul 22, Enter.

497
00:22:04,180 --> 00:22:05,010
Aceasta a constatat 22.

498
00:22:05,010 --> 00:22:07,580
Deci, asta este ceea ce această
Programul Lista Zero face.

499
00:22:07,580 --> 00:22:10,230
>> Dar ceea ce se intampla de fapt
pe care implementeaza aceasta?

500
00:22:10,230 --> 00:22:14,530
Ei bine, în primul rând s-ar putea avea, și într-adevăr
Eu am, un fișier numit list0.h.

501
00:22:14,530 --> 00:22:16,540

502
00:22:16,540 --> 00:22:20,690
Și undeva acolo este aceasta
linie, typedef, nod struct,

503
00:22:20,690 --> 00:22:24,850
atunci am bretele mele cret, int n, și
atunci struct-- ce a fost definiția?

504
00:22:24,850 --> 00:22:26,530

505
00:22:26,530 --> 00:22:28,545
Nod Struct următor.

506
00:22:28,545 --> 00:22:29,920

507
00:22:29,920 --> 00:22:31,045
Deci, avem nevoie de steaua.

508
00:22:31,045 --> 00:22:33,420
Acum punct de vedere tehnic de a intra în
obiceiul de a atrage aici.

509
00:22:33,420 --> 00:22:35,670
S-ar putea vedea manualele și
referințe on-line se face acolo.

510
00:22:35,670 --> 00:22:36,660
Este echivalent funcțional.

511
00:22:36,660 --> 00:22:37,980
De fapt, acesta este un pic mai tipic.

512
00:22:37,980 --> 00:22:40,563
Dar voi fi în concordanță cu ceea ce
am făcut ultima dată și de a face acest lucru.

513
00:22:40,563 --> 00:22:42,350
Și apoi în cele din urmă, am de gând să fac asta.

514
00:22:42,350 --> 00:22:45,550
>> Deci, într-un fișier antet
undeva, în list0.h

515
00:22:45,550 --> 00:22:49,200
astăzi este această definiție struct,
și poate alte chestii.

516
00:22:49,200 --> 00:22:52,580
Între timp, în list0c există
O să fie câteva lucruri.

517
00:22:52,580 --> 00:22:54,740
Dar vom doar
începe și nu termin asta.

518
00:22:54,740 --> 00:22:59,690
List0.h este un fișier vreau
să includă în dosarul meu C.

519
00:22:59,690 --> 00:23:03,910
Și apoi, la un moment dat am
Va trebui int, principal, anularea.

520
00:23:03,910 --> 00:23:06,530
Și apoi am de gând să
au unele probleme de rezolvat aici.

521
00:23:06,530 --> 00:23:10,620
Am, de asemenea, de gând să aibă o
prototip, cum ar fi gol, căutare, int,

522
00:23:10,620 --> 00:23:13,610
n, al cărei scop în viață este
pentru a căuta un element.

523
00:23:13,610 --> 00:23:18,310
Și apoi aici am pretinde în
Codul de astăzi, gol, căutare, int, n,

524
00:23:18,310 --> 00:23:21,020
nu virgulă dar acolade deschise.

525
00:23:21,020 --> 00:23:25,049
Și acum vreau să caute într-un fel
pentru un element din această listă.

526
00:23:25,049 --> 00:23:27,340
Dar noi nu avem suficient
informații pe ecran încă.

527
00:23:27,340 --> 00:23:29,800
Nu am de fapt,
reprezentat lista sine.

528
00:23:29,800 --> 00:23:33,070
Deci, într-un fel am putea pune în aplicare
o listă legat într-un program

529
00:23:33,070 --> 00:23:37,520
este am un fel de vrei să faci ceva
ca să declare lista inlantuita aici.

530
00:23:37,520 --> 00:23:40,520
Pentru simplitate, am de gând să facă
acest globală, chiar dacă, în general, ne

531
00:23:40,520 --> 00:23:41,645
nu ar trebui să facă acest lucru prea mult.

532
00:23:41,645 --> 00:23:43,260
Dar va simplifica acest exemplu.

533
00:23:43,260 --> 00:23:45,890
Deci, vreau să declar
o listă legat aici.

534
00:23:45,890 --> 00:23:47,010
Acum, cum s-ar putea să fac asta?

535
00:23:47,010 --> 00:23:48,810

536
00:23:48,810 --> 00:23:50,750
>> Iată imaginea unei liste legate.

537
00:23:50,750 --> 00:23:53,030
Și eu nu prea
știe în acest moment cât de

538
00:23:53,030 --> 00:23:56,710
Am de gând să merg despre reprezentarea
atât de multe lucruri cu un fel

539
00:23:56,710 --> 00:23:58,040
variabilă în memorie.

540
00:23:58,040 --> 00:23:59,160
Dar gandeste-te înapoi o clipă.

541
00:23:59,160 --> 00:24:00,830
În tot acest timp am avut
siruri de caractere, pe care apoi

542
00:24:00,830 --> 00:24:02,913
dovedit a fi matrici de
personaje, pe care apoi

543
00:24:02,913 --> 00:24:05,740
dovedit a fi doar un pointer
la primul caracter

544
00:24:05,740 --> 00:24:08,890
într-o matrice de caractere
care este nul reziliat.

545
00:24:08,890 --> 00:24:13,530
Deci, conform acestei logici, și cu această
imagine fel de însămânțare gandurile tale,

546
00:24:13,530 --> 00:24:17,964
ceea ce trebuie să ne scrie de fapt în nostru
cod pentru a reprezenta o listă înlănțuită?

547
00:24:17,964 --> 00:24:21,130
Cât de mult de această informație avem nevoie
pentru a capta în cod C, ai spune?

548
00:24:21,130 --> 00:24:22,654

549
00:24:22,654 --> 00:24:23,154
Da?

550
00:24:23,154 --> 00:24:24,738
>> Audiența: Avem nevoie de un pointer la un nod.

551
00:24:24,738 --> 00:24:26,237
David J. MALAN: Un pointer la un nod.

552
00:24:26,237 --> 00:24:29,320
În special, care nod ar ta
Instinctele fi de a păstra un pointer la?

553
00:24:29,320 --> 00:24:30,026
>> Audiența: primul nod.

554
00:24:30,026 --> 00:24:31,942
>> David J. MALAN: Da,
probabil doar primul.

555
00:24:31,942 --> 00:24:34,030
Și observați, primul
nod este o formă diferită.

556
00:24:34,030 --> 00:24:37,690
E doar jumătate din dimensiunea struct,
pentru că este într-adevăr doar un pointer.

557
00:24:37,690 --> 00:24:44,650
Deci, ce se poate face într-adevăr este declara
o listă înlănțuită a fi de tip nod *.

558
00:24:44,650 --> 00:24:47,780
Și hai să-i spunem întâi
și se inițializa la null.

559
00:24:47,780 --> 00:24:49,910
Deci nul, din nou, este venirea
în imaginea de aici.

560
00:24:49,910 --> 00:24:53,620
Nu numai ca este nul folosit ca ca un special
Valoarea de retur pentru lucruri cum ar fi getstring

561
00:24:53,620 --> 00:24:57,770
și malloc, nul este de asemenea zero
pointer, lipsa unui pointer,

562
00:24:57,770 --> 00:24:58,430
dacă vrei.

563
00:24:58,430 --> 00:25:00,309
Aceasta înseamnă doar nimic nu este încă aici.

564
00:25:00,309 --> 00:25:02,100
Acum întâi, am fi putut
numit acest ceva.

565
00:25:02,100 --> 00:25:04,200
Aș fi putut numit-o "listă"
sau orice număr de alte lucruri.

566
00:25:04,200 --> 00:25:06,960
Dar eu voi spune "primul", astfel încât
Liniile-l cu această imagine.

567
00:25:06,960 --> 00:25:10,280
Deci, la fel ca un șir poate fi reprezentat
cu adresa de primul octet,

568
00:25:10,280 --> 00:25:11,280
deci poate o listă înlănțuită.

569
00:25:11,280 --> 00:25:13,480
Și vom vedea alte date
Structurile fi reprezentat

570
00:25:13,480 --> 00:25:16,700
cu doar un singur indicator,
o săgeată pe 32 de biți, arătând

571
00:25:16,700 --> 00:25:18,740
chiar la primul nod în structură.

572
00:25:18,740 --> 00:25:20,340
>> Dar acum să anticipeze o problemă.

573
00:25:20,340 --> 00:25:23,230
Dacă am doar amintindu-
în programul meu adresa

574
00:25:23,230 --> 00:25:27,220
din primul nod, primul
dreptunghi în această structură de date,

575
00:25:27,220 --> 00:25:31,760
ceea ce a avut mai bine în dosarul
punerea în aplicare a restului lista mea?

576
00:25:31,760 --> 00:25:35,820
Ce este un detaliu cheie care va
pentru a asigura acest lucru funcționează de fapt?

577
00:25:35,820 --> 00:25:39,250
Și prin "funcționează de fapt" I
Adică, mai mult ca un șir de caractere,

578
00:25:39,250 --> 00:25:42,180
ne permite să mergem de la primul caracter
în nume Davin la a doua,

579
00:25:42,180 --> 00:25:44,755
a treia, pentru a
al patrulea, până la capăt,

580
00:25:44,755 --> 00:25:47,880
cum știm când suntem la sfârșitul
de o lista inlantuita care arata ca aceasta?

581
00:25:47,880 --> 00:25:50,035

582
00:25:50,035 --> 00:25:50,660
Când este nul.

583
00:25:50,660 --> 00:25:53,640
Și l-am reprezentat acest tip de ca
ca o putere inginer electric,

584
00:25:53,640 --> 00:25:56,420
cu mic impamantare
simbol, de felul.

585
00:25:56,420 --> 00:25:58,246
Dar asta înseamnă doar nul în acest caz.

586
00:25:58,246 --> 00:26:00,370
Puteți să-l trage orice număr
de moduri, dar acest autor

587
00:26:00,370 --> 00:26:02,800
sa întâmplat de a folosi acest simbol aici.

588
00:26:02,800 --> 00:26:06,260
>> Atât timp cât suntem înșirare
toate aceste noduri împreună,

589
00:26:06,260 --> 00:26:08,600
numai amintindu unde
Prima dintre ele este, atât de mult timp

590
00:26:08,600 --> 00:26:11,760
ca am pus un simbol special la
ultimul nod din lista,

591
00:26:11,760 --> 00:26:15,130
și vom folosi nul, pentru că asta e
ceea ce avem la dispoziție pentru a ne,

592
00:26:15,130 --> 00:26:16,480
această listă este completă.

593
00:26:16,480 --> 00:26:20,190
Și chiar dacă doar vă dau un pointer la
primul element, tu, programator,

594
00:26:20,190 --> 00:26:22,486
pot accesa cu siguranță restul.

595
00:26:22,486 --> 00:26:24,360
Dar să-l lăsăm mințile voastre
rătăcesc un pic,

596
00:26:24,360 --> 00:26:26,140
în cazul în care nu sunt deja
destul de wandered-- ceea ce-i

597
00:26:26,140 --> 00:26:28,723
va fi timpul de execuție a
găsi ceva în această listă?

598
00:26:28,723 --> 00:26:30,450

599
00:26:30,450 --> 00:26:33,470
La naiba, e O mare de n,
care nu este rău, în corectitudine.

600
00:26:33,470 --> 00:26:34,800
Dar este liniară.

601
00:26:34,800 --> 00:26:37,980
Am renunțat la ceea ce caracteristică
de tablouri de mișcare mai mult

602
00:26:37,980 --> 00:26:43,130
față de această imagine de dinamic
țesute împreună sau noduri legate?

603
00:26:43,130 --> 00:26:44,970

604
00:26:44,970 --> 00:26:46,687
Am renunțat acces aleator.

605
00:26:46,687 --> 00:26:48,770
Un tablou este frumos, pentru că
matematic totul

606
00:26:48,770 --> 00:26:50,340
este spate în spate la spate în spate.

607
00:26:50,340 --> 00:26:52,370
Chiar dacă această imagine
pare destul, și chiar

608
00:26:52,370 --> 00:26:55,830
deși se pare că aceste noduri
sunt bine distanțate, în realitate

609
00:26:55,830 --> 00:26:56,830
acestea ar putea fi oriunde.

610
00:26:56,830 --> 00:27:01,590
OX1, Ox50, Ox123, Ox99, acestea
noduri ar putea fi oriunde.

611
00:27:01,590 --> 00:27:05,960
Pentru ca malloc nu aloca memorie
din grămada, dar oriunde în grămada.

612
00:27:05,960 --> 00:27:09,080
Nu știi neapărat că este
Va fi înapoi la spate în spate.

613
00:27:09,080 --> 00:27:12,460
Și astfel, această imagine în realitate lui
nu va fi destul de acest frumos.

614
00:27:12,460 --> 00:27:16,140
>> Deci, va fi nevoie de un pic de
de lucru pentru a pune în aplicare această funcție.

615
00:27:16,140 --> 00:27:17,880
Deci, haideți să pună în aplicare de cautare acum.

616
00:27:17,880 --> 00:27:20,250
Și vom vedea un fel de
mod inteligent de a face acest lucru.

617
00:27:20,250 --> 00:27:24,660
Deci, dacă eu sunt o funcție de căutare și
Am dat o variabilă, întreg n

618
00:27:24,660 --> 00:27:28,490
să caute, am nevoie să știu
nou sintaxă pentru căutarea în interiorul

619
00:27:28,490 --> 00:27:32,400
unei structuri care este
a subliniat, pentru a găsi n.

620
00:27:32,400 --> 00:27:33,210
Deci, hai sa facem acest lucru.

621
00:27:33,210 --> 00:27:36,030
>> Deci, primul am de gând să merg
înainte și să declare un nod *.

622
00:27:36,030 --> 00:27:39,400
Și am de gând să-l numesc
pointer, doar prin convenție.

623
00:27:39,400 --> 00:27:41,710
Și am de gând să-l inițializa la primul.

624
00:27:41,710 --> 00:27:43,770
Și acum pot face acest lucru
într-un număr de moduri.

625
00:27:43,770 --> 00:27:45,436
Dar am de gând să ia o abordare comună.

626
00:27:45,436 --> 00:27:50,180
In timp ce indicatorul nu este egal cu
nul, și asta e valabil sintaxă.

627
00:27:50,180 --> 00:27:54,550
Și aceasta înseamnă doar procedați în felul următor, așa
timp cât nu te îndreptat la nimic.

628
00:27:54,550 --> 00:27:55,800
Ce vreau să fac?

629
00:27:55,800 --> 00:28:01,939
>> În cazul în care indicatorul punct n, lasă-mă să vin înapoi
pentru că, equals-- este egal cu ce?

630
00:28:01,939 --> 00:28:03,105
Ce valoare caut?

631
00:28:03,105 --> 00:28:04,920

632
00:28:04,920 --> 00:28:06,590
N efectiv care a fost trecut în.

633
00:28:06,590 --> 00:28:09,020
Deci, aici este o altă caracteristică
de C și mai multe limbi.

634
00:28:09,020 --> 00:28:13,705
Chiar dacă structura numita nodul
n are o valoare, cu totul legitim

635
00:28:13,705 --> 00:28:17,530
să aibă, de asemenea, un argument locală
sau variabilă numită n.

636
00:28:17,530 --> 00:28:20,085
Deoarece chiar noi, cu
ochii omului, se poate distinge

637
00:28:20,085 --> 00:28:22,087
că această n este probabil
diferit de acesta n.

638
00:28:22,087 --> 00:28:23,420
Deoarece sintaxa este diferită.

639
00:28:23,420 --> 00:28:26,211
Ai un punct și un pointer,
întrucât acesta nu are un astfel de lucru.

640
00:28:26,211 --> 00:28:27,290
Deci, acest lucru este OK.

641
00:28:27,290 --> 00:28:29,120
Asta e OK să-i numească aceleași lucruri.

642
00:28:29,120 --> 00:28:32,380
>> Dacă eu ți se pare acest lucru, eu sunt
O să vrei să faci ceva

643
00:28:32,380 --> 00:28:35,000
ca anunțăm că am găsit n.

644
00:28:35,000 --> 00:28:37,930
Și vom lăsa ca pe un
comentariu sau cod pseudocod.

645
00:28:37,930 --> 00:28:40,190
Altfel, și aici e
parte interesant, ceea ce

646
00:28:40,190 --> 00:28:47,320
nu vreau să fac în cazul în care nodul curent
nu se conțin n care îmi pasă?

647
00:28:47,320 --> 00:28:50,700
Cum pot obține următoarele?

648
00:28:50,700 --> 00:28:53,710
Dacă degetul meu de la
moment este PTR, și este

649
00:28:53,710 --> 00:28:55,920
arătând la orice
Primul este îndreptat la,

650
00:28:55,920 --> 00:28:59,290
cum pot muta degetul meu
la urmatorul nod din cod?

651
00:28:59,290 --> 00:29:01,915
Ei bine, ceea ce e de pesmet suntem
va urma în acest caz?

652
00:29:01,915 --> 00:29:03,464

653
00:29:03,464 --> 00:29:04,380
Audiența: [inaudibil].

654
00:29:04,380 --> 00:29:05,630
David J. MALAN: Da, așa următor.

655
00:29:05,630 --> 00:29:06,640

656
00:29:06,640 --> 00:29:09,824
Deci, dacă mă întorc la meu
Codul aici, într-adevăr, eu sunt

657
00:29:09,824 --> 00:29:12,990
merge mai departe și spune pointer, care
este doar un variable-- temporar este

658
00:29:12,990 --> 00:29:15,320
un nume ciudat, ptr, dar
e la fel ca temp--

659
00:29:15,320 --> 00:29:19,234
Am de gând să se stabilească pointer
egal cu orice pointer este--

660
00:29:19,234 --> 00:29:22,150
și din nou, acest lucru va fi o
puțin buggy pentru un punct moment-- următor.

661
00:29:22,150 --> 00:29:23,551

662
00:29:23,551 --> 00:29:26,550
Cu alte cuvinte, am de gând să-mi iau
deget care este îndreptat la acest nod

663
00:29:26,550 --> 00:29:31,247
aici și am de gând să spun, știi
ceea ce, arunca o privire la următorul câmp

664
00:29:31,247 --> 00:29:33,330
și mișcați-vă degetul
orice este îndreptat la.

665
00:29:33,330 --> 00:29:35,163
Și acest lucru se întâmplă pentru
Repet, repet, repeta.

666
00:29:35,163 --> 00:29:37,630
Dar când nu-mi degetul
nu mai faci nimic, la toate?

667
00:29:37,630 --> 00:29:40,095
De îndată ce ceea ce linie de lovituri de cod în?

668
00:29:40,095 --> 00:29:40,970
Audiența: [inaudibil]

669
00:29:40,970 --> 00:29:43,060
David J. MALAN: Dacă punctul în timp ce
pointer nu este egal cu NULL.

670
00:29:43,060 --> 00:29:44,900
La un moment dat mi degetul lui
va fi îndreptată la nul

671
00:29:44,900 --> 00:29:47,070
și am de gând să dau seama
că e sfârșitul acestei liste.

672
00:29:47,070 --> 00:29:48,910
Acum, acest lucru este un pic
minciună albă pentru simplitate.

673
00:29:48,910 --> 00:29:51,580
Se pare că, deși noi
doar învățat această notație punct

674
00:29:51,580 --> 00:29:55,220
pentru structuri, indicatorul nu este o struct.

675
00:29:55,220 --> 00:29:56,580
ptr este ceea ce?

676
00:29:56,580 --> 00:29:58,350
Doar pentru a fi mai nitpicky.

677
00:29:58,350 --> 00:29:59,720

678
00:29:59,720 --> 00:30:01,360
Este un pointer la un nod.

679
00:30:01,360 --> 00:30:03,120
Nu este un nod în sine.

680
00:30:03,120 --> 00:30:06,650
Dacă aș fi avut nici o stea aici, pointer
absolutely-- este un nod.

681
00:30:06,650 --> 00:30:08,650
Aceasta este ca o saptamana
declarație a unei variabile,

682
00:30:08,650 --> 00:30:10,120
chiar dacă cuvântul "nod" este nou.

683
00:30:10,120 --> 00:30:13,860
>> Dar, de îndată ce vom introduce o
stele, este acum un pointer la un nod.

684
00:30:13,860 --> 00:30:17,960
Și, din păcate, nu puteți utiliza
notația punct de un pointer.

685
00:30:17,960 --> 00:30:21,070
Trebuie să utilizați săgeata
notație, care, surprinzător,

686
00:30:21,070 --> 00:30:23,470
este pentru prima dată orice piesă
de sintaxă arată intuitiv.

687
00:30:23,470 --> 00:30:25,245
Acest lucru pur și simplu arată ca o săgeată.

688
00:30:25,245 --> 00:30:26,370
Și așa că e un lucru bun.

689
00:30:26,370 --> 00:30:28,995
Și aici literalmente
arata ca o săgeată.

690
00:30:28,995 --> 00:30:31,870
Deci, eu cred că e la-- eu nu fac
că am peste-comiterea aici-- I

691
00:30:31,870 --> 00:30:34,120
Cred că e ultima piesă nouă
de sintaxă vom vedea.

692
00:30:34,120 --> 00:30:36,500
Și din fericire, este într-adevăr
un pic mai mult intuitiv.

693
00:30:36,500 --> 00:30:40,090
>> Acum, pentru cei dintre voi care
s-ar putea prefera vechiul mod,

694
00:30:40,090 --> 00:30:42,550
puteți utiliza în continuare notația punct.

695
00:30:42,550 --> 00:30:45,380
Dar, conform luni de
conversație, am primul

696
00:30:45,380 --> 00:30:50,530
Trebuie să mergem acolo, du-te la asta
adresa, iar apoi accesați acest domeniu.

697
00:30:50,530 --> 00:30:51,897
Deci, acest lucru este, de asemenea, corect.

698
00:30:51,897 --> 00:30:53,730
Și sincer, aceasta este o
puțin mai pedant.

699
00:30:53,730 --> 00:30:56,530
Ești pur și simplu spunând dereference
indicatorul și du-te acolo.

700
00:30:56,530 --> 00:30:59,320
Apoi apuca .n, câmpul numit n.

701
00:30:59,320 --> 00:31:01,370
Dar, sincer, nimeni nu vrea
pentru a introduce sau de a citi acest lucru.

702
00:31:01,370 --> 00:31:03,620
Și astfel lumea a inventat
notația săgeată, care

703
00:31:03,620 --> 00:31:06,980
este echivalent, identic,
e doar zahăr sintactic.

704
00:31:06,980 --> 00:31:10,570
Deci, un mod elegant de a spune acest lucru
arata mai bine, sau arata mai simplu.

705
00:31:10,570 --> 00:31:12,296
>> Așa că acum am de gând să fac un lucru.

706
00:31:12,296 --> 00:31:15,420
Am de gând să spun "pauză" o dată am
Am găsit-o așa că nu sa mai caut pentru ea.

707
00:31:15,420 --> 00:31:17,620
Dar aceasta este esența
de o funcție de căutare.

708
00:31:17,620 --> 00:31:21,710
Dar e mult mai ușor, în
end, pentru a nu umbla prin codul.

709
00:31:21,710 --> 00:31:25,570
Aceasta este într-adevăr implementarea formală
de căutare în codul de distributie de astăzi.

710
00:31:25,570 --> 00:31:30,530
Îndrăznesc să spun că inserție nu este
mai ales distractiv de a merge prin

711
00:31:30,530 --> 00:31:33,180
vizual, nici nu este șterge, chiar
deși la sfârșitul zilei

712
00:31:33,180 --> 00:31:35,460
se fierbe până la destul de
euristici simple.

713
00:31:35,460 --> 00:31:36,330
>> Deci, hai sa facem acest lucru.

714
00:31:36,330 --> 00:31:39,250
Dacă veți umor mine aici, am făcut
aduce o grămadă de mingi de stres.

715
00:31:39,250 --> 00:31:40,620
Am adus o grămadă de numere.

716
00:31:40,620 --> 00:31:46,562
Și am putea obține doar câteva voluntari
pentru a reprezenta 9, 17, 20, 22, 29, și 34?

717
00:31:46,562 --> 00:31:48,270
Deci, în esență, toată lumea
cine e aici azi.

718
00:31:48,270 --> 00:31:50,170

719
00:31:50,170 --> 00:31:52,760
Asta a fost una, două, trei,
patru, cinci, șase oameni.

720
00:31:52,760 --> 00:31:55,740
Și am fost rugat să go-- vedea, nu
una în partea din spate ridică mâinile lor.

721
00:31:55,740 --> 00:32:01,910
OK, unu, doi, trei, patru,
cinci-- lasă-mă să încarce balance-- șase.

722
00:32:01,910 --> 00:32:03,051
OK, ai șase haide sus.

723
00:32:03,051 --> 00:32:04,050
Vom avea nevoie de alte persoane.

724
00:32:04,050 --> 00:32:05,460
Am adus bile suplimentare de stres.

725
00:32:05,460 --> 00:32:08,200
Și dacă ai putea, pentru
doar o clipă, linie

726
00:32:08,200 --> 00:32:10,490
vă în sus doar
mult de această imagine aici.

727
00:32:10,490 --> 00:32:15,200

728
00:32:15,200 --> 00:32:15,959
>> În regulă.

729
00:32:15,959 --> 00:32:17,125
Să vedem, care e numele tău?

730
00:32:17,125 --> 00:32:17,550
>> Audiența: Andrew.

731
00:32:17,550 --> 00:32:18,800
>> David J. MALAN: Andrew,
sunteti numărul 9.

732
00:32:18,800 --> 00:32:19,540
Mă bucur să te cunosc.

733
00:32:19,540 --> 00:32:20,400
Aici te duci.

734
00:32:20,400 --> 00:32:21,593

735
00:32:21,593 --> 00:32:22,176
Audiența: Jen.

736
00:32:22,176 --> 00:32:22,662
David J. MALAN: Jen.

737
00:32:22,662 --> 00:32:23,162
David.

738
00:32:23,162 --> 00:32:23,765
Numărul 17.

739
00:32:23,765 --> 00:32:24,950

740
00:32:24,950 --> 00:32:25,450
Da?

741
00:32:25,450 --> 00:32:26,400
>> Audiența: Eu sunt Julia.

742
00:32:26,400 --> 00:32:26,980
>> David J. MALAN: Julia, David.

743
00:32:26,980 --> 00:32:27,545
Numărul 20.

744
00:32:27,545 --> 00:32:28,507

745
00:32:28,507 --> 00:32:29,340
Audiența: Christian.

746
00:32:29,340 --> 00:32:30,715
David J. MALAN: Christian, David.

747
00:32:30,715 --> 00:32:31,541
Numărul 22.

748
00:32:31,541 --> 00:32:32,040
Și?

749
00:32:32,040 --> 00:32:32,649
>> Audiența: JP.

750
00:32:32,649 --> 00:32:33,440
David J. MALAN: JP.

751
00:32:33,440 --> 00:32:34,880
Numărul 29.

752
00:32:34,880 --> 00:32:37,080
Deci, mergeți mai departe și a obține in-- Uh oh.

753
00:32:37,080 --> 00:32:38,486

754
00:32:38,486 --> 00:32:38,985
Uh oh.

755
00:32:38,985 --> 00:32:39,650

756
00:32:39,650 --> 00:32:40,150
Standby.

757
00:32:40,150 --> 00:32:41,360

758
00:32:41,360 --> 00:32:42,390
20.

759
00:32:42,390 --> 00:32:43,682
Are cineva un marker?

760
00:32:43,682 --> 00:32:44,890
Audiența: Am un Sharpie.

761
00:32:44,890 --> 00:32:45,660
David J. MALAN: Ai un Sharpie?

762
00:32:45,660 --> 00:32:46,159
OK.

763
00:32:46,159 --> 00:32:47,577

764
00:32:47,577 --> 00:32:49,160
Și nimeni nu avea o bucată de hârtie?

765
00:32:49,160 --> 00:32:51,562

766
00:32:51,562 --> 00:32:52,270
Salvați curs.

767
00:32:52,270 --> 00:32:53,810

768
00:32:53,810 --> 00:32:55,362
Haide.

769
00:32:55,362 --> 00:32:56,320
Audiența: L-am prins.

770
00:32:56,320 --> 00:32:57,600
David J. MALAN: Ne-am prins?

771
00:32:57,600 --> 00:32:58,577
Bine, mulțumesc.

772
00:32:58,577 --> 00:33:01,380

773
00:33:01,380 --> 00:33:02,520
Aici vom merge.

774
00:33:02,520 --> 00:33:03,582
A fost aceasta de la tine?

775
00:33:03,582 --> 00:33:04,540
Tocmai ai salvat ziua.

776
00:33:04,540 --> 00:33:05,670

777
00:33:05,670 --> 00:33:07,220
Deci, 29.

778
00:33:07,220 --> 00:33:10,510

779
00:33:10,510 --> 00:33:11,110
În regulă.

780
00:33:11,110 --> 00:33:13,360

781
00:33:13,360 --> 00:33:14,890
Am scris gresit 29, dar OK.

782
00:33:14,890 --> 00:33:15,720
Dă-i drumul.

783
00:33:15,720 --> 00:33:18,114
Bine, eu voi da
pen-ul înapoi pentru moment.

784
00:33:18,114 --> 00:33:19,280
Deci avem acesti oameni aici.

785
00:33:19,280 --> 00:33:20,330
Hai să o alta.

786
00:33:20,330 --> 00:33:23,750
Gabe, vrei să joci
primul element aici?

787
00:33:23,750 --> 00:33:25,705
Avem nevoie de tine la punctul
la acesti oameni fine.

788
00:33:25,705 --> 00:33:26,930

789
00:33:26,930 --> 00:33:31,030
Deci 9, 17, 20, 22, sortare
de 29, apoi 34.

790
00:33:31,030 --> 00:33:32,160

791
00:33:32,160 --> 00:33:33,325
Am pierdut pe cineva?

792
00:33:33,325 --> 00:33:33,950
Am un 34.

793
00:33:33,950 --> 00:33:36,730
În cazul în care did-- OK, care vrea să fie 34?

794
00:33:36,730 --> 00:33:37,605
OK, hai sus, 34.

795
00:33:37,605 --> 00:33:39,280

796
00:33:39,280 --> 00:33:41,220
Bine, acest lucru va fi
bine în valoare de punctul culminant.

797
00:33:41,220 --> 00:33:41,550
Care e numele tău?

798
00:33:41,550 --> 00:33:42,040
>> Audiența: Peter.

799
00:33:42,040 --> 00:33:43,456
>> David J. MALAN: Peter, haide sus.

800
00:33:43,456 --> 00:33:46,810
În regulă, așa că aici e un
grămadă de noduri.

801
00:33:46,810 --> 00:33:49,060
Fiecare dintre voi reprezintă
unul dintre aceste dreptunghiuri.

802
00:33:49,060 --> 00:33:51,930
Și Gabe, ușor ciudat
om, reprezinta primul.

803
00:33:51,930 --> 00:33:54,850
Deci, indicatorul său este un pic mai mic
pe ecran decât oricine altcineva.

804
00:33:54,850 --> 00:33:58,120
Și în acest caz, fiecare din stânga
mâini este de gând să fie punctul de jos,

805
00:33:58,120 --> 00:34:01,085
reprezentând astfel null, așa
doar absenta unui pointer,

806
00:34:01,085 --> 00:34:03,210
sau o să fie îndreptat
la un nod de lângă tine.

807
00:34:03,210 --> 00:34:05,440
>> Deci, acum, dacă împodobesc
vă cum ar fi imaginea

808
00:34:05,440 --> 00:34:07,585
aici, mergeți mai departe și punct
unul la altul, cu Gabe

809
00:34:07,585 --> 00:34:11,030
în îndreptat special la
numărul 9 a reprezenta listă.

810
00:34:11,030 --> 00:34:14,050
OK, și numărul 34, mâna stângă
doar ar trebui să fie îndreptată la podea.

811
00:34:14,050 --> 00:34:15,750
>> OK, deci aceasta este lista legat.

812
00:34:15,750 --> 00:34:17,580
Deci, acesta este scenariul în cauză.

813
00:34:17,580 --> 00:34:20,210
Și într-adevăr, aceasta este reprezentativ
a unei clase de probleme

814
00:34:20,210 --> 00:34:21,929
care s-ar putea încerca să rezolve cu cod.

815
00:34:21,929 --> 00:34:25,020
Vrei să inserați în cele din urmă
un element nou în listă.

816
00:34:25,020 --> 00:34:27,494
În acest caz, vom
încercați să introduceți numărul 55.

817
00:34:27,494 --> 00:34:28,500

818
00:34:28,500 --> 00:34:30,860
Dar nu va fi
cazuri diferite să ia în considerare.

819
00:34:30,860 --> 00:34:34,409
Și într-adevăr, acest lucru va fi un
de-imaginea de ansamblu takeaways aici, este,

820
00:34:34,409 --> 00:34:35,659
care sunt diferite cazuri.

821
00:34:35,659 --> 00:34:39,120
Care sunt diferitele cazul în care condițiile sau
ramuri care programul ar putea avea?

822
00:34:39,120 --> 00:34:42,024
>> Ei bine, numărul pe care încercați să
inserție, care știm acum să fie 55,

823
00:34:42,024 --> 00:34:44,650
dar dacă nu știai
în prealabil, îndrăznesc să spun

824
00:34:44,650 --> 00:34:47,840
se încadrează în cel puțin trei
situații posibile.

825
00:34:47,840 --> 00:34:49,717
În cazul în care s-ar putea fi un element nou?

826
00:34:49,717 --> 00:34:51,050
Audiența: Și la sfârșitul sau mijlocul.

827
00:34:51,050 --> 00:34:54,150
David J. MALAN: La sfârșitul anului, în
la mijloc, sau la început.

828
00:34:54,150 --> 00:34:56,650
Așa că pretind că sunt cel puțin
trei probleme trebuie să rezolve.

829
00:34:56,650 --> 00:34:58,691
Să alegem ce este, probabil,
fără îndoială, cea mai simplă

830
00:34:58,691 --> 00:35:01,090
unul, în cazul în care noul element
aparține la început.

831
00:35:01,090 --> 00:35:04,040
Așa că am de gând să aibă cod destul de
cum ar fi de căutare, pe care am scris doar.

832
00:35:04,040 --> 00:35:07,670
Și am de gând să aibă ptr, care
Voi reprezenta aici cu degetul,

833
00:35:07,670 --> 00:35:08,370
ca de obicei.

834
00:35:08,370 --> 00:35:12,430
>> Și amintiți-vă, ce valoare
am inițializa ptr a?

835
00:35:12,430 --> 00:35:15,300
Deci, l-am pregătit pentru a null inițial.

836
00:35:15,300 --> 00:35:16,410

837
00:35:16,410 --> 00:35:19,770
Dar atunci ce am face o dată ne-am
au fost în funcție de căutare?

838
00:35:19,770 --> 00:35:20,940

839
00:35:20,940 --> 00:35:24,870
Ne-am propus o egal cu primul,
ceea ce nu înseamnă a face acest lucru.

840
00:35:24,870 --> 00:35:25,890

841
00:35:25,890 --> 00:35:30,570
Dacă am setat ptr egal cu primul, ceea ce
ar trebui să fie într-adevăr mâna arătând spre?

842
00:35:30,570 --> 00:35:31,070
Corect.

843
00:35:31,070 --> 00:35:33,290
Deci, dacă Gabe și cu mine vom
a fi valori egale aici,

844
00:35:33,290 --> 00:35:34,760
avem nevoie de atât punct la numărul 9.

845
00:35:34,760 --> 00:35:36,420
>> Deci asta a fost inceputul povestii noastre.

846
00:35:36,420 --> 00:35:38,700
Iar acum acest lucru este doar simplu,
chiar dacă sintaxa este nou.

847
00:35:38,700 --> 00:35:40,580
Conceptual acest lucru este doar de căutare liniară.

848
00:35:40,580 --> 00:35:42,750
Este 55 egal cu 9?

849
00:35:42,750 --> 00:35:45,559
Sau, mai degrabă, să spunem mai puțin de 9.

850
00:35:45,559 --> 00:35:47,600
Pentru că încerc să
dau seama unde să pună 55.

851
00:35:47,600 --> 00:35:51,270
Mai puțin de 9, la mai puțin de 17, mai puțin
mult de 20, mai mic de 22, mai mic de 29,

852
00:35:51,270 --> 00:35:52,510
mai puțin de 34, nr.

853
00:35:52,510 --> 00:35:55,080
Deci, acum suntem în caz
unul din cel puțin trei.

854
00:35:55,080 --> 00:35:59,910
>> Dacă vreau să insera peste 55 de ani aici, ceea ce
de linii de cod au nevoie pentru a obține executat?

855
00:35:59,910 --> 00:36:01,890
Cum această imagine de
oamenii au nevoie pentru a schimba?

856
00:36:01,890 --> 00:36:03,181
Ce să fac cu mana stanga?

857
00:36:03,181 --> 00:36:04,530

858
00:36:04,530 --> 00:36:07,360
Acest lucru ar trebui să fie nul inițial,
pentru că eu sunt de la sfârșitul listei.

859
00:36:07,360 --> 00:36:09,318
Și ce ar trebui să se întâmple
aici cu Peter, a fost?

860
00:36:09,318 --> 00:36:10,520

861
00:36:10,520 --> 00:36:12,430
El, evident, va indica mine.

862
00:36:12,430 --> 00:36:15,580
Așa că pretind că sunt cel puțin două linii
de cod în codul proba de azi

863
00:36:15,580 --> 00:36:18,570
care va pune în aplicare această
scenariu de adăugarea de 55 la coada.

864
00:36:18,570 --> 00:36:20,950
Și aș putea avea cineva hop
și chiar reprezintă 55?

865
00:36:20,950 --> 00:36:22,200
Bine, tu esti nou 55.

866
00:36:22,200 --> 00:36:23,580

867
00:36:23,580 --> 00:36:27,054
>> Deci, acum, ce se întâmplă dacă următorul
scenariu vine,

868
00:36:27,054 --> 00:36:29,720
și dorim să introduceți la
început sau capul acestei liste?

869
00:36:29,720 --> 00:36:31,100
Și care e numele tău, numărul 55?

870
00:36:31,100 --> 00:36:31,420
>> Audiența: Jack.

871
00:36:31,420 --> 00:36:32,295
>> David J. MALAN: Jack?

872
00:36:32,295 --> 00:36:33,585
OK, mă bucur să te cunosc.

873
00:36:33,585 --> 00:36:34,210
Bine ai venit la bord.

874
00:36:34,210 --> 00:36:36,640
Deci, acum vom
introduce, de exemplu, numărul 5.

875
00:36:36,640 --> 00:36:39,840
Aici este al doilea caz de
trei am venit cu înainte.

876
00:36:39,840 --> 00:36:43,050
Deci, dacă 5 aparține la început,
hai sa vedem cum putem afla asta.

877
00:36:43,050 --> 00:36:46,310
Am inițializa ptr meu
pointer la numărul 9 din nou.

878
00:36:46,310 --> 00:36:49,140
Și am realizat, oh, 5 este mai mică de 9.

879
00:36:49,140 --> 00:36:50,880
Deci rezolva această imagine pentru noi.

880
00:36:50,880 --> 00:36:54,820
Al cui mâinile, lui Gabe sau lui David
sau-- care e numele lui numărul 9?

881
00:36:54,820 --> 00:36:55,740
>> Audiența: Jen.

882
00:36:55,740 --> 00:36:58,406
>> David J. MALAN: hands-- lui Jen
care de mâinile noastre trebuie să se schimbe?

883
00:36:58,406 --> 00:36:58,905

884
00:36:58,905 --> 00:37:00,970
OK, deci Gabe arată la ce acum?

885
00:37:00,970 --> 00:37:01,640
La mine.

886
00:37:01,640 --> 00:37:02,750
Eu sunt noul nod.

887
00:37:02,750 --> 00:37:04,870
Deci, eu doar un fel de mișcare
aici pentru a vedea vizual.

888
00:37:04,870 --> 00:37:06,435
Și între timp ce eu subliniez asta?

889
00:37:06,435 --> 00:37:07,910

890
00:37:07,910 --> 00:37:09,020
Totuși unde am îndreptat.

891
00:37:09,020 --> 00:37:10,000
Deci, asta este.

892
00:37:10,000 --> 00:37:13,717
Așa că într-adevăr o linie de remedieri de cod
această problemă, s-ar părea.

893
00:37:13,717 --> 00:37:14,800
În regulă, așa că e bine.

894
00:37:14,800 --> 00:37:17,580
Și poate cineva să fie un substituent pentru 5?

895
00:37:17,580 --> 00:37:18,080
Hai sus.

896
00:37:18,080 --> 00:37:20,270

897
00:37:20,270 --> 00:37:21,320
Vă vom lua data viitoare.

898
00:37:21,320 --> 00:37:24,280
>> În regulă, așa acum-- și
Ca o paranteza, numele

899
00:37:24,280 --> 00:37:28,510
Nu fac referire în mod explicit de drept
acum, pointer pred, predecesorul pointer

900
00:37:28,510 --> 00:37:31,260
și noi pointer, care este
doar numele dat

901
00:37:31,260 --> 00:37:35,280
în codul eșantion de indicii sau
mâinile mele că e un fel de indicare în jurul.

902
00:37:35,280 --> 00:37:36,060
Care e numele tău?

903
00:37:36,060 --> 00:37:36,700
>> Audiența: Christine.

904
00:37:36,700 --> 00:37:37,100
>> David J. MALAN: Christine.

905
00:37:37,100 --> 00:37:38,090
Bine ai venit la bord.

906
00:37:38,090 --> 00:37:42,180
Bine, să luăm în considerare acum
un scenariu ceva mai enervant,

907
00:37:42,180 --> 00:37:46,350
prin care vreau să inserați
ceva de genul 26 în asta.

908
00:37:46,350 --> 00:37:47,090
20?

909
00:37:47,090 --> 00:37:47,590
Ce?

910
00:37:47,590 --> 00:37:50,510
Acestea esti-- lucru bun avem acest stilou.

911
00:37:50,510 --> 00:37:51,955
În regulă, 20.

912
00:37:51,955 --> 00:37:53,640

913
00:37:53,640 --> 00:37:57,570
În cazul în care cineva ar putea primi o altă bucată de
hârtie gata, doar în case-- bine.

914
00:37:57,570 --> 00:37:58,370
Oh, interesant.

915
00:37:58,370 --> 00:37:59,760

916
00:37:59,760 --> 00:38:02,390
Ei bine, acesta este un exemplu
de un bug curs.

917
00:38:02,390 --> 00:38:03,894
OK deci care e numele tau?

918
00:38:03,894 --> 00:38:04,560
Audiența: Julia.

919
00:38:04,560 --> 00:38:07,559
David J. MALAN: Julia, puteți pop
afară și te prefaci că nu au fost niciodată acolo?

920
00:38:07,559 --> 00:38:09,040
OK, nu sa întâmplat acest lucru.

921
00:38:09,040 --> 00:38:09,680
Mulțumesc.

922
00:38:09,680 --> 00:38:12,180
Deci, să presupunem că vrem introduce
Julia în această listă înlănțuită.

923
00:38:12,180 --> 00:38:13,780
Ea este numărul 20.

924
00:38:13,780 --> 00:38:15,530
Și, desigur, e
O să fac la

925
00:38:15,530 --> 00:38:17,521
incepem nu punct la nimic încă.

926
00:38:17,521 --> 00:38:20,020
Deci, mâna ta poate fi un fel de
jos null sau o valoare gunoi.

927
00:38:20,020 --> 00:38:21,210
Să spun povestea rapid.

928
00:38:21,210 --> 00:38:22,980
Am îndreptat în număr de 5 acest moment.

929
00:38:22,980 --> 00:38:23,880
Apoi am verificat 9.

930
00:38:23,880 --> 00:38:25,130
Apoi am verifica 17.

931
00:38:25,130 --> 00:38:26,247
Apoi am verifica 22.

932
00:38:26,247 --> 00:38:27,650

933
00:38:27,650 --> 00:38:32,485
Și îmi dau seama, ooh, Julia
trebuie să meargă înainte de 22.

934
00:38:32,485 --> 00:38:33,580

935
00:38:33,580 --> 00:38:34,660
Deci, ceea ce trebuie să se întâmple?

936
00:38:34,660 --> 00:38:35,786

937
00:38:35,786 --> 00:38:36,910
A cui mâini nevoie pentru a schimba?

938
00:38:36,910 --> 00:38:38,360
Julia, a mea, sau--
Care e numele tău?

939
00:38:38,360 --> 00:38:39,230
>> Audiența: Christian.

940
00:38:39,230 --> 00:38:40,060
>> David J. MALAN: Christian sau?

941
00:38:40,060 --> 00:38:40,560
>> Audiența: Andy.

942
00:38:40,560 --> 00:38:40,905
>> David J. MALAN: Andy.

943
00:38:40,905 --> 00:38:41,654
Christian sau Andy?

944
00:38:41,654 --> 00:38:44,280

945
00:38:44,280 --> 00:38:45,690
Andy trebuie să arate la?

946
00:38:45,690 --> 00:38:46,780

947
00:38:46,780 --> 00:38:47,341
Julia.

948
00:38:47,341 --> 00:38:47,840
În regulă.

949
00:38:47,840 --> 00:38:48,960
Deci Andy, vrei sa arate la Julia?

950
00:38:48,960 --> 00:38:50,120
Dar stai un minut.

951
00:38:50,120 --> 00:38:53,260
În povestea până acum,
Eu sunt genul de unul

952
00:38:53,260 --> 00:38:56,800
responsabil, în sensul că
pointer este un lucru care este

953
00:38:56,800 --> 00:38:57,850
se deplasează prin lista.

954
00:38:57,850 --> 00:39:00,800
Am putea avea un nume pentru Andy, dar
nu exista nici o variabilă numită Andy.

955
00:39:00,800 --> 00:39:04,320
Singura variabilă avem este
în primul rând, care este reprezentat de Gabe.

956
00:39:04,320 --> 00:39:07,690
>> Deci, acesta este de fapt motivul pentru astfel
acum nu am nevoie de asta.

957
00:39:07,690 --> 00:39:10,846
Dar acum pe ecran este
vorbim din nou de pointer pred.

958
00:39:10,846 --> 00:39:11,970
Așa că lasă-mă să fiu mai explicit.

959
00:39:11,970 --> 00:39:14,820
În cazul în care acest lucru este pointer, am avut mai bine
obține un pic mai inteligent

960
00:39:14,820 --> 00:39:15,950
despre repetare mea.

961
00:39:15,950 --> 00:39:19,580
Dacă nu te superi mea trece printr aici
din nou, arătând aici, arătând aici.

962
00:39:19,580 --> 00:39:22,500
Dar permiteți-mi să aibă un pointer pred,
predecesorul pointer, care este

963
00:39:22,500 --> 00:39:24,740
fel de îndreptat la
Element Am fost doar la.

964
00:39:24,740 --> 00:39:27,330
Așa că atunci când merg aici, acum
actualizările mele din stânga.

965
00:39:27,330 --> 00:39:29,370
Când mă duc aici actualizările mele de la mâna stângă.

966
00:39:29,370 --> 00:39:33,090
Și acum am nu numai un pointer la
elementul care merge după Julia,

967
00:39:33,090 --> 00:39:36,300
Mai am un pointer la
Andy, elementul înainte.

968
00:39:36,300 --> 00:39:39,430
Deci, aveți acces, în esență,
pesmet, dacă vreți,

969
00:39:39,430 --> 00:39:41,500
la toate indicii necesare.

970
00:39:41,500 --> 00:39:43,710
>> Deci, dacă am îndreptat la
Andy și eu sunt, de asemenea, indică

971
00:39:43,710 --> 00:39:47,105
la Christian, ale căror mâini
acum trebuie să se arate în altă parte?

972
00:39:47,105 --> 00:39:48,770

973
00:39:48,770 --> 00:39:51,960
Deci, Andy poate indica acum la Julia.

974
00:39:51,960 --> 00:39:54,460
Julia pot indica acum la Christian.

975
00:39:54,460 --> 00:39:56,950
Pentru că ea poate copia mea
pointer mâna dreaptă a lui.

976
00:39:56,950 --> 00:40:00,044
Și pe care le pune în mod eficient
înapoi în acest loc aici.

977
00:40:00,044 --> 00:40:02,460
Deci, pe scurt, chiar dacă aceasta
este de a lua noi un fel de pentru totdeauna

978
00:40:02,460 --> 00:40:04,510
pentru a actualiza de fapt o
Lista legate, realiza

979
00:40:04,510 --> 00:40:06,580
că operațiunile
sunt relativ simple.

980
00:40:06,580 --> 00:40:10,030
Este de unul, doi, trei
de linii de cod în cele din urmă.

981
00:40:10,030 --> 00:40:12,780
Dar înfășurat în jurul celor
de linii de cod probabil în

982
00:40:12,780 --> 00:40:16,350
este un pic de logică pe care în mod eficient
pune întrebarea, unde suntem?

983
00:40:16,350 --> 00:40:18,970
Suntem la început,
la mijloc, sau la sfârșit?

984
00:40:18,970 --> 00:40:21,890
>> Acum, există cu siguranță o altă
operațiuni s-ar putea pune în aplicare.

985
00:40:21,890 --> 00:40:24,880
Și aceste poze aici doar descrie
ceea ce tocmai am făcut-o cu oamenii.

986
00:40:24,880 --> 00:40:26,080
Ce despre eliminarea?

987
00:40:26,080 --> 00:40:30,650
Dacă vreau să, de exemplu,
elimina numărul 34 sau 55,

988
00:40:30,650 --> 00:40:34,680
S-ar putea avea același tip de cod,
dar am de gând să nevoie de unul sau doi pași.

989
00:40:34,680 --> 00:40:36,110
Pentru că ce mai e nou?

990
00:40:36,110 --> 00:40:40,460
Dacă am scoate cineva la sfârșitul anului,
cum ar fi numărul 55 și apoi 34,

991
00:40:40,460 --> 00:40:42,995
ceea ce are, de asemenea, să se schimbe ca să fac asta?

992
00:40:42,995 --> 00:40:44,870
Nu am să evict--
Care e numele tău?

993
00:40:44,870 --> 00:40:45,380
>> Audiența: Jack.

994
00:40:45,380 --> 00:40:46,255
>> David J. MALAN: Jack.

995
00:40:46,255 --> 00:40:49,770
Trebuie să nu numai evict-- liber Jack,
astfel suna literalmente liber Jack, sau cel puțin

996
00:40:49,770 --> 00:40:53,530
indicatorul acolo, dar acum
ceea ce trebuie să se schimbe cu Peter?

997
00:40:53,530 --> 00:40:55,510
Mâna lui mai bine începe cu vârful în jos.

998
00:40:55,510 --> 00:40:59,300
Pentru că, de îndată ce suna gratuit la
Jack, dacă Petru încă îndreptat la Jack

999
00:40:59,300 --> 00:41:02,530
și eu, prin urmare, să păstreze traversează
lista și accesa acest indicator,

1000
00:41:02,530 --> 00:41:05,650
atunci prietenul nostru segmentare vechi
vina s-ar putea lovi cu piciorul în fapt.

1001
00:41:05,650 --> 00:41:07,860
Pentru că ne-am dat
memorie înapoi la Jack.

1002
00:41:07,860 --> 00:41:10,760
>> Poți să stai acolo
neîndemânatic pentru doar o clipă.

1003
00:41:10,760 --> 00:41:13,410
Pentru ca avem doar un cuplu
operațiuni finale să ia în considerare.

1004
00:41:13,410 --> 00:41:15,600
Scoaterea capul listei,
sau beginning-- și asta e

1005
00:41:15,600 --> 00:41:16,349
un pic enervant.

1006
00:41:16,349 --> 00:41:19,640
Pentru că trebuie să știm că Gabe
este un fel de special la acest program.

1007
00:41:19,640 --> 00:41:21,440
Pentru că, într-adevăr, el are propria lui pointer.

1008
00:41:21,440 --> 00:41:24,860
El nu a fost doar a subliniat, la,
ca este aproape oricine altcineva de aici.

1009
00:41:24,860 --> 00:41:28,112
>> Deci, atunci când capul listei este
îndepărtat, ale cărui mâini au nevoie pentru a schimba acum?

1010
00:41:28,112 --> 00:41:29,070
Care e numele tău?

1011
00:41:29,070 --> 00:41:29,450
>> Audiența: Christine.

1012
00:41:29,450 --> 00:41:31,408
>> David J. MALAN: Sunt groaznic
la nume, aparent.

1013
00:41:31,408 --> 00:41:34,011
Deci, Christine și Gabe,
ale căror mâini au nevoie pentru a schimba

1014
00:41:34,011 --> 00:41:36,510
atunci când încercați să eliminați Christine,
numărul 5, de la imaginea?

1015
00:41:36,510 --> 00:41:37,550

1016
00:41:37,550 --> 00:41:38,820
OK, așa că hai să facem Gabe.

1017
00:41:38,820 --> 00:41:40,950
Gabe se va indica,
probabil, la numărul 9.

1018
00:41:40,950 --> 00:41:42,230

1019
00:41:42,230 --> 00:41:44,642
Dar ce viitor trebuie să se întâmple?

1020
00:41:44,642 --> 00:41:46,600
Audiența: Christine ar trebui
fi nul [neauzit].

1021
00:41:46,600 --> 00:41:50,244
David J. MALAN: OK, ar trebui, probabil,
make-- am auzit "nul" pe undeva.

1022
00:41:50,244 --> 00:41:51,410
Audiența: Null și liber ei.

1023
00:41:51,410 --> 00:41:51,855
David J. MALAN: NULL ce?

1024
00:41:51,855 --> 00:41:53,074
Audiența: Null și liber ei.

1025
00:41:53,074 --> 00:41:54,490
David J. MALAN: Null și liber ei.

1026
00:41:54,490 --> 00:41:55,422
Deci, acest lucru este foarte simplu.

1027
00:41:55,422 --> 00:41:58,380
Și e perfect ca esti acum un fel
de a sta acolo, nu aparțin.

1028
00:41:58,380 --> 00:42:00,430
Pentru că ai fost
decuplat din lista.

1029
00:42:00,430 --> 00:42:02,820
Ai fost efectiv
orfani din listă.

1030
00:42:02,820 --> 00:42:07,770
Și așa ne-am numi mai bine gratuit acum pe
Christine a da ca memoria înapoi.

1031
00:42:07,770 --> 00:42:10,240
În caz contrar, de fiecare dată când
șterge un nod din lista

1032
00:42:10,240 --> 00:42:14,230
am putea fi a face lista
mai scurt, dar nu chiar în scădere

1033
00:42:14,230 --> 00:42:15,096
dimensiunea în memorie.

1034
00:42:15,096 --> 00:42:17,720
Și așa, dacă am păstra adăugarea și
adaugand, adăugând lucruri de pe lista,

1035
00:42:17,720 --> 00:42:19,280
calculatorul meu s-ar putea obține mai lent
și mai lent și mai lent,

1036
00:42:19,280 --> 00:42:21,740
pentru că eu sunt pe punctul de a
memorie, chiar dacă eu nu sunt de fapt

1037
00:42:21,740 --> 00:42:25,580
folosind bytes Christine
de memorie mai.

1038
00:42:25,580 --> 00:42:28,500
>> Deci, în cele din urmă, există alte
scenarii, de îndepărtare bineinteles--

1039
00:42:28,500 --> 00:42:30,640
în mijloc, eliminarea
la sfârșitul anului, așa cum am văzut.

1040
00:42:30,640 --> 00:42:32,348
Dar mai interesant
provocare acum este

1041
00:42:32,348 --> 00:42:34,770
va fi să ia în considerare exact
ceea ce este timpul de execuție.

1042
00:42:34,770 --> 00:42:36,640
Deci, nu numai că puteți să vă păstrați
bucăți de hârtie, în cazul în care, Gabe,

1043
00:42:36,640 --> 00:42:38,640
nu te superi da
toată lumea o minge de stres.

1044
00:42:38,640 --> 00:42:42,100
Vă mulțumesc foarte mult pentru a lista noastră legată
de voluntari aici, dacă ai putea.

1045
00:42:42,100 --> 00:42:45,320
>> [Aplauze]

1046
00:42:45,320 --> 00:42:46,700
>> David J. MALAN: Bine.

1047
00:42:46,700 --> 00:42:51,110
Deci, un cuplu de analiză
întrebări atunci, dacă aș putea.

1048
00:42:51,110 --> 00:42:59,670
Am văzut această notație înainte,
O mare și omega, limite superioare

1049
00:42:59,670 --> 00:43:02,520
și limite mai mici de pe
Timp de câteva algoritm care rulează.

1050
00:43:02,520 --> 00:43:04,950
Deci, să luăm în considerare doar
câteva întrebări.

1051
00:43:04,950 --> 00:43:07,090
>> O, și am spus-o
înainte, ceea ce este în funcțiune

1052
00:43:07,090 --> 00:43:10,647
timp de căutare pentru a
Lista în termeni de mare O?

1053
00:43:10,647 --> 00:43:13,480
Ce este o limită superioară de funcționare
timp de a căuta o listă înlănțuită

1054
00:43:13,480 --> 00:43:16,340
puse în aplicare de către voluntarii nostri aici?

1055
00:43:16,340 --> 00:43:17,820
Este O mare de n, liniare.

1056
00:43:17,820 --> 00:43:20,630
Pentru că, în cel mai rău caz,
elementul, cum ar fi 55,

1057
00:43:20,630 --> 00:43:23,830
am putea fi în căutarea de ar fi în cazul în care
Jack a fost, tot drumul de la sfârșitul.

1058
00:43:23,830 --> 00:43:28,250
Și, din păcate, spre deosebire de o matrice
nu putem obține de lux de data asta.

1059
00:43:28,250 --> 00:43:31,820
Chiar dacă toți oamenii noștri au fost
clasificate în funcție de elementele de mici, 5,

1060
00:43:31,820 --> 00:43:35,900
tot drumul până la elementul mai mare,
55, care este de obicei un lucru bun.

1061
00:43:35,900 --> 00:43:38,815
Dar ceea ce face ca ipoteza
nu mai ne permit să facem?

1062
00:43:38,815 --> 00:43:39,775

1063
00:43:39,775 --> 00:43:40,650
Audiența: [inaudibil]

1064
00:43:40,650 --> 00:43:40,920
David J. MALAN: Spune din nou?

1065
00:43:40,920 --> 00:43:41,800
Audiența: acces aleator.

1066
00:43:41,800 --> 00:43:43,049
David J. MALAN: acces aleator.

1067
00:43:43,049 --> 00:43:46,330
Și la rândul său, înseamnă că putem să nu
mai folosi zerouri slab, intuiție,

1068
00:43:46,330 --> 00:43:49,365
și evidență a folosi binar
de căutare și diviza și cuceri.

1069
00:43:49,365 --> 00:43:51,240
Pentru că, chiar dacă ne-am
oamenii ar putea, evident,

1070
00:43:51,240 --> 00:43:54,610
vedea că Andy sau creștin-au
aproximativ în mijlocul listei,

1071
00:43:54,610 --> 00:43:57,670
Știm doar că în calitate de
calculator de skimming pe lista

1072
00:43:57,670 --> 00:43:59,029
de la bun început.

1073
00:43:59,029 --> 00:44:00,570
Așa că am renunțat la care acces aleator.

1074
00:44:00,570 --> 00:44:04,380
>> O atât de mare de n acum este superioară
legat pe timp de căutare.

1075
00:44:04,380 --> 00:44:07,920
Ce despre omega de căutare nostru?

1076
00:44:07,920 --> 00:44:11,535
Care este cea mai mică legat la căutare
pentru un numar din această listă?

1077
00:44:11,535 --> 00:44:12,410
Audiența: [inaudibil]

1078
00:44:12,410 --> 00:44:13,040
David J. MALAN: Spune din nou?

1079
00:44:13,040 --> 00:44:13,420
Audiența: Unul.

1080
00:44:13,420 --> 00:44:13,800
David J. MALAN: Unu.

1081
00:44:13,800 --> 00:44:14,760
Deci timp constantă.

1082
00:44:14,760 --> 00:44:17,020
În cel mai bun caz, Christine este
într-adevăr, la începutul listei.

1083
00:44:17,020 --> 00:44:19,020
Și căutăm
numărul 5, asa ca am găsit-o.

1084
00:44:19,020 --> 00:44:19,787
Deci, nu e mare lucru.

1085
00:44:19,787 --> 00:44:22,370
Dar ea trebuie să fie la
începând din lista din acest caz.

1086
00:44:22,370 --> 00:44:23,745
Ce zici de ceva de genul Delete?

1087
00:44:23,745 --> 00:44:24,717

1088
00:44:24,717 --> 00:44:26,300
Ce se întâmplă dacă doriți să ștergeți un element?

1089
00:44:26,300 --> 00:44:29,200
Care este limita superioară a și limita inferioară
la ștergerea ceva de la o legătură

1090
00:44:29,200 --> 00:44:29,699
lista?

1091
00:44:29,699 --> 00:44:35,195

1092
00:44:35,195 --> 00:44:36,070
Audiența: [inaudibil]

1093
00:44:36,070 --> 00:44:36,420
David J. MALAN: Spune din nou?

1094
00:44:36,420 --> 00:44:37,067
Audiența: n.

1095
00:44:37,067 --> 00:44:38,900
David J. MALAN: n este
într-adevăr, limita superioară.

1096
00:44:38,900 --> 00:44:41,700
Pentru că, în cel mai rău caz vom încerca
pentru a șterge Jack, ca tocmai am făcut-o.

1097
00:44:41,700 --> 00:44:43,050
El e tot drumul la sfârșitul anului.

1098
00:44:43,050 --> 00:44:45,419
Ne ia pentru totdeauna, sau
n pași să-l găsească.

1099
00:44:45,419 --> 00:44:46,460
Deci, asta e o limită superioară.

1100
00:44:46,460 --> 00:44:47,430
Asta e liniar, sigur.

1101
00:44:47,430 --> 00:44:50,970
Și cel mai bun caz temporizare, sau
limitele inferioare, în cel mai bun caz

1102
00:44:50,970 --> 00:44:51,975
ar fi timp constant.

1103
00:44:51,975 --> 00:44:54,600
Pentru că poate că încercați să ștergeți
Christine, și ne-am noroc

1104
00:44:54,600 --> 00:44:55,558
ea e la început.

1105
00:44:55,558 --> 00:44:56,350
Acum, așteptați un minut.

1106
00:44:56,350 --> 00:44:59,370
Gabe a fost, de asemenea, la început,
și am avut, de asemenea, pentru a actualiza Gabe.

1107
00:44:59,370 --> 00:45:01,150
Așa că nu a fost doar un pas.

1108
00:45:01,150 --> 00:45:04,210
Deci, este într-adevăr constant
timp, în cel mai bun caz,

1109
00:45:04,210 --> 00:45:06,345
pentru a îndepărta cel mai mic element?

1110
00:45:06,345 --> 00:45:07,360

1111
00:45:07,360 --> 00:45:10,960
Este, cu toate că ar putea fi de două,
trei, sau chiar 100 de linii de cod,

1112
00:45:10,960 --> 00:45:14,000
dacă e același număr de
linii, nu în unele buclă,

1113
00:45:14,000 --> 00:45:16,577
și independent de dimensiunea
listei, absolut.

1114
00:45:16,577 --> 00:45:18,660
Ștergerea elementului la
începutul listei,

1115
00:45:18,660 --> 00:45:21,940
chiar dacă avem de-a face cu
Gabe, este încă timp constant.

1116
00:45:21,940 --> 00:45:24,220
>> Deci, aceasta pare a fi o
pas masiv înapoi.

1117
00:45:24,220 --> 00:45:27,000
Și ce o pierdere de timp
în cazul în care, în săptămâna de o săptămână și

1118
00:45:27,000 --> 00:45:30,250
zero, am avut nu numai
Codul pseudocod dar codul actual

1119
00:45:30,250 --> 00:45:35,780
să pună în aplicare ceva care este log
de bază n, sau jurnal, mai degrabă, de n, baza 2,

1120
00:45:35,780 --> 00:45:37,150
în ceea ce privește timpul de rulare.

1121
00:45:37,150 --> 00:45:40,710
Deci, de ce naiba ne-ar dori să înceapă
folosind ceva de genul o listă de legat?

1122
00:45:40,710 --> 00:45:41,517
Da.

1123
00:45:41,517 --> 00:45:44,022
>> Audiența: Deci, puteți adăuga
elemente la matrice.

1124
00:45:44,022 --> 00:45:46,230
David J. MALAN: Deci, poți
adăuga elemente la matrice.

1125
00:45:46,230 --> 00:45:47,550
Și acest lucru este de asemenea tematic.

1126
00:45:47,550 --> 00:45:49,740
Și vom continua pentru a vedea
aceasta, acest compromis, mult

1127
00:45:49,740 --> 00:45:51,573
ca am vazut-o
trade-off cu îmbinare tip.

1128
00:45:51,573 --> 00:45:54,606
Am putea accelera într-adevăr în sus
căutare sau de sortare, mai degrabă,

1129
00:45:54,606 --> 00:45:57,480
dacă ne petrecem un pic mai mult spațiu și
au o bucată suplimentară a unei memorii

1130
00:45:57,480 --> 00:45:58,760
sau o serie de îmbinare fel.

1131
00:45:58,760 --> 00:46:01,270
Dar ne petrecem mai mult
spațiu, dar ne-am economisi timp.

1132
00:46:01,270 --> 00:46:04,820
În acest caz, suntem
renunțarea la timp, dar suntem

1133
00:46:04,820 --> 00:46:08,170
câștigă flexibilitate,
dinamism, dacă vrei,

1134
00:46:08,170 --> 00:46:10,280
care este, fără îndoială, o trăsătură pozitivă.

1135
00:46:10,280 --> 00:46:11,520
>> Ne petrecem de asemenea spațiu.

1136
00:46:11,520 --> 00:46:13,710
În ce sens este o legătură
Lista mai scump

1137
00:46:13,710 --> 00:46:15,700
în termeni de spațiu decât un tablou?

1138
00:46:15,700 --> 00:46:18,379

1139
00:46:18,379 --> 00:46:19,920
În cazul în care este spatiul in plus vine de la?

1140
00:46:19,920 --> 00:46:20,460
Da?

1141
00:46:20,460 --> 00:46:21,800
>> Audiența: [inaudibil] pointer.

1142
00:46:21,800 --> 00:46:23,310
>> David J. MALAN: Da, ne-am
au, de asemenea, indicatorul.

1143
00:46:23,310 --> 00:46:25,560
Deci, aceasta este minorly enervant
în care nu mai sunt

1144
00:46:25,560 --> 00:46:27,780
Am stocarea doar un int
pentru a reprezenta un întreg.

1145
00:46:27,780 --> 00:46:30,990
Am stocarea un int și un
pointer, care este de asemenea de 32 de biți.

1146
00:46:30,990 --> 00:46:33,470
Deci, eu sunt literalmente dublarea
cantitatea de spațiu implicat.

1147
00:46:33,470 --> 00:46:36,040
Deci, asta e un compromis, dar
care este în cazul Int.

1148
00:46:36,040 --> 00:46:39,580
Să presupunem că nu ești stocarea int,
dar să presupunem că fiecare dintre aceste dreptunghiuri

1149
00:46:39,580 --> 00:46:43,290
sau fiecare dintre acesti oameni a fost reprezentând
un cuvânt, un cuvânt englezesc, care

1150
00:46:43,290 --> 00:46:46,430
ar putea fi de cinci caractere, 10
caractere, poate chiar mai mult.

1151
00:46:46,430 --> 00:46:49,940
Apoi, adăugând doar 32 mai mulți biți
s-ar putea să fie mai puțin de o afacere mare.

1152
00:46:49,940 --> 00:46:52,160
>> Ce se întâmplă dacă fiecare dintre elevi
în demonstrația

1153
00:46:52,160 --> 00:46:55,107
au fost literalmente o structura de studenți care
au nume și case și poate

1154
00:46:55,107 --> 00:46:57,065
numere de telefon și Twitter
mânere și altele asemenea.

1155
00:46:57,065 --> 00:46:59,564
Așa că toate câmpurile am început
vorbim despre ieri,

1156
00:46:59,564 --> 00:47:02,410
mult mai puțin de o afacere de mare ca
noduri noastre devin mai interesante

1157
00:47:02,410 --> 00:47:05,972
și mare să-și petreacă, nu-i așa, o suplimentare de
pointer doar pentru a le lega împreună.

1158
00:47:05,972 --> 00:47:07,180
Dar, într-adevăr, este un compromis.

1159
00:47:07,180 --> 00:47:09,560
Și într-adevăr, codul este
mai complex, după cum veți

1160
00:47:09,560 --> 00:47:11,770
a se vedea de skimming prin
acel exemplu particular.

1161
00:47:11,770 --> 00:47:14,302
Dar dacă s-au
unele Sfântul Graal aici.

1162
00:47:14,302 --> 00:47:17,010
Ce se întâmplă dacă nu luăm un pas
înapoi, dar un pas înainte masiv

1163
00:47:17,010 --> 00:47:19,180
și să pună în aplicare o de date
structură prin care noi

1164
00:47:19,180 --> 00:47:22,870
Puteți găsi elemente, cum ar fi Jack sau
Christine sau orice alte elemente

1165
00:47:22,870 --> 00:47:25,870
în această matrice în adevăratul timp constant?

1166
00:47:25,870 --> 00:47:26,920
Search este constant.

1167
00:47:26,920 --> 00:47:28,320
Ștergeți este constantă.

1168
00:47:28,320 --> 00:47:29,570
Introduceți este constantă.

1169
00:47:29,570 --> 00:47:32,260
Toate aceste operațiuni sunt constante.

1170
00:47:32,260 --> 00:47:33,750
Asta ar fi Graal nostru sfânt.

1171
00:47:33,750 --> 00:47:36,690
Și că este în cazul în care ne-am
va ridica data viitoare.

1172
00:47:36,690 --> 00:47:38,600
Ne vedem atunci.

1173
00:47:38,600 --> 00:47:39,371