1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Săptămâna 6]

2
00:00:02,000 --> 00:00:04,000
[David J. Malan] [Universitatea Harvard]

3
00:00:04,000 --> 00:00:08,000
[Acest lucru este CS50.] [CS50.TV]

4
00:00:08,000 --> 00:00:12,000
>> Acest lucru este CS50, iar acest lucru este începutul Săptămâna 6,

5
00:00:12,000 --> 00:00:16,000
astfel încât o serie de instrumente noi sunt acum disponibile pentru tine de a profita de,

6
00:00:16,000 --> 00:00:19,000
care primul se numește CS50 Style.

7
00:00:19,000 --> 00:00:22,000
Cote sunt, dacă ești ca mine sau la oricare dintre semenii didactice,

8
00:00:22,000 --> 00:00:26,000
le-ați văzut, probabil, un program al cărui stil arata ceva de genul asta.

9
00:00:26,000 --> 00:00:30,000
Poate începe de tăiere unele colțuri târziu în noapte, sau vei face cu ea mai târziu,

10
00:00:30,000 --> 00:00:32,000
și apoi un TF sau CA vine timpul orelor de birou.

11
00:00:32,000 --> 00:00:34,000
Atunci e greu pentru noi să citească.

12
00:00:34,000 --> 00:00:38,000
Ei bine, acest cod este corect sintactic, și se va compila, și se va desfășura de fapt.

13
00:00:38,000 --> 00:00:40,000
Dar nu e cu siguranta un 5 pentru stil.

14
00:00:40,000 --> 00:00:45,000
>> Dar acum, dacă vom intra în acest director aici,

15
00:00:45,000 --> 00:00:48,000
și observați că am conditions2.c-

16
00:00:48,000 --> 00:00:55,000
și am rula această comandă nouă, style50, pe acest conditions2.c dosar, Enter,

17
00:00:55,000 --> 00:00:57,000
observa că acesta ma informat că a fost stilizat.

18
00:00:57,000 --> 00:01:00,000
Gedit observat că fișierul a fost modificat pe disc,

19
00:01:00,000 --> 00:01:08,000
și dacă fac clic pe reîncărca, toate problemele tale sunt acum automatizate.

20
00:01:08,000 --> 00:01:15,000
[Aplauze]

21
00:01:15,000 --> 00:01:17,000
Asta e unul din lucrurile pe care le-am făcut în acest weekend.

22
00:01:17,000 --> 00:01:20,000
Dau seama că este imperfect, deoarece există unele cod

23
00:01:20,000 --> 00:01:23,000
că pur și simplu nu va fi capabil de a stiliza perfect,

24
00:01:23,000 --> 00:01:26,000
dar realiza acest lucru este acum un instrument puteți profita de

25
00:01:26,000 --> 00:01:33,000
în cazul în care numai pentru a pune în ordine unele dintre cele mai acolade errantly plasat cret si place.

26
00:01:33,000 --> 00:01:36,000
>> Dar mai convingătoare este acum CS50 Data Check.

27
00:01:36,000 --> 00:01:39,000
Cu CS50 Cec, puteți efectua, de fapt, aceleași teste corectitudinii

28
00:01:39,000 --> 00:01:42,000
pe propriul cod care colegii de predare sunt în măsură să.

29
00:01:42,000 --> 00:01:44,000
Acesta este un utilitar linie de comandă care vine acum în aparat

30
00:01:44,000 --> 00:01:46,000
de îndată ce vă faceți un update50 ca pe

31
00:01:46,000 --> 00:01:49,000
PSET 4 caietul de sarcini, și să-l utilizați în esență, ca asta.

32
00:01:49,000 --> 00:01:51,000
Puteti rula check50 comanda.

33
00:01:51,000 --> 00:01:56,000
Apoi, treci într-un argument de linie de comandă, sau mai multe, în general, cunoscut ca un comutator sau un steag.

34
00:01:56,000 --> 00:01:58,000
În general, lucruri care au cratime sunt chemați un comutator

35
00:01:58,000 --> 00:02:02,000
la un program de linie de comandă, așa-c specifică

36
00:02:02,000 --> 00:02:04,000
controalele pe care doriți să le executați.

37
00:02:04,000 --> 00:02:07,000
>> Testele pe care doriți să le executați sunt identificate unic prin acest șir,

38
00:02:07,000 --> 00:02:10,000
2012/pset4/resize.

39
00:02:10,000 --> 00:02:13,000
Cu alte cuvinte, e doar un șir arbitrar, ci unic

40
00:02:13,000 --> 00:02:18,000
pe care le folosim pentru a identifica în mod unic teste de 4 PSET lui corectitudine.

41
00:02:18,000 --> 00:02:21,000
Și apoi să specificați o listă separată spațiu de fișiere pe care doriți să încărcați

42
00:02:21,000 --> 00:02:24,000
Verificați să CS50 pentru analiză.

43
00:02:24,000 --> 00:02:29,000
De exemplu, dacă mă duc în soluția mea aici pentru resize.c-

44
00:02:29,000 --> 00:02:31,000
lasă-mă să deschideți un terminal mai mare fereastră-

45
00:02:31,000 --> 00:02:42,000
și am merge mai departe și a alerga să zicem c-check50 2012/pset4/resize,

46
00:02:42,000 --> 00:02:46,000
si apoi am merge mai departe și specificați numele fișierelor,

47
00:02:46,000 --> 00:02:49,000
resize.c, și a lovit apoi Enter, se comprimă,

48
00:02:49,000 --> 00:02:53,000
it încarcă, se verifică, și am reușit doar o grămadă de teste.

49
00:02:53,000 --> 00:02:59,000
Una în roșu din stanga sus spune că resize.c și BMP există.

50
00:02:59,000 --> 00:03:01,000
Asta a fost de testare. Aceasta a fost întrebarea-am cerut.

51
00:03:01,000 --> 00:03:04,000
Și e nefericită pentru că răspunsul a fost falsă.

52
00:03:04,000 --> 00:03:08,000
Textul de mai jos alb se spune de așteptat să existe bmp.h, și asta e pur si simplu vina mea.

53
00:03:08,000 --> 00:03:11,000
Am uitat să-l trimiti, pentru ca am nevoie pentru a încărca ambele fișiere,

54
00:03:11,000 --> 00:03:14,000
resize.c și bmp.h.

55
00:03:14,000 --> 00:03:17,000
Dar observați acum toate celelalte teste sunt în galben, deoarece acestea nu au rulat,

56
00:03:17,000 --> 00:03:21,000
și astfel fața zâmbitoare este verticală, deoarece el nu este nici fericit, nici trist,

57
00:03:21,000 --> 00:03:25,000
dar trebuie să remedieze această problemă în roșu înainte de aceste alte controale va rula.

58
00:03:25,000 --> 00:03:27,000
>> Lasă-mă să repar asta.

59
00:03:27,000 --> 00:03:30,000
Lasă-mă să zoom out și rulați din nou acest lucru, de data aceasta cu bmp.h, de asemenea,

60
00:03:30,000 --> 00:03:34,000
pe linia de comandă, Enter, și acum, dacă totul merge bine,

61
00:03:34,000 --> 00:03:38,000
se va verifica și apoi să se întoarcă un rezultat de-țineți respirația ta-

62
00:03:38,000 --> 00:03:42,000
toate verde, ceea ce înseamnă că eu fac foarte bine pe PSET 4 până în prezent.

63
00:03:42,000 --> 00:03:44,000
Puteți vedea și deduce din text descriptiv aici

64
00:03:44,000 --> 00:03:47,000
exact ce este testat de noi.

65
00:03:47,000 --> 00:03:49,000
Am testat prima nu există fisierele?

66
00:03:49,000 --> 00:03:51,000
Apoi am testat nu compila resize.c?

67
00:03:51,000 --> 00:03:58,000
Apoi am testat nu-l redimensiona un pixel BMP 1x1-atunci n, factorul de redimensionare, este de 1.

68
00:03:58,000 --> 00:04:01,000
Acum, în cazul în care nu aveți nici o idee despre ceea ce n este, veți odată ce scufunda in PSET 4,

69
00:04:01,000 --> 00:04:04,000
dar faptul că este pur și simplu un bun-simț să verificați pentru a vă asigura că nu ești redimensionare

70
00:04:04,000 --> 00:04:08,000
o imagine la toate, dacă factorul de redimensionare este 1.

71
00:04:08,000 --> 00:04:14,000
În cazul în care, prin contrast, se redimensionează un pixel 1x1 la un 1x1 pixel BMP la 2x2 corect

72
00:04:14,000 --> 00:04:19,000
când n este 2, atunci în mod similar, a mea face în consecință.

73
00:04:19,000 --> 00:04:22,000
>> Pe scurt, acest lucru este menit să, unul, ia de trecere a degetelor

74
00:04:22,000 --> 00:04:25,000
din ecuație chiar înainte de a trimite PSET ta.

75
00:04:25,000 --> 00:04:28,000
Veti sti exact ce TF va ști în curând

76
00:04:28,000 --> 00:04:30,000
când te duci cu privire la trimiterea unele dintre aceste seturi de probleme,

77
00:04:30,000 --> 00:04:34,000
și, de asemenea, motivația pedagogică este într-adevăr să afișezi

78
00:04:34,000 --> 00:04:37,000
oportunitate în fața ta, astfel că atunci când știi a priori

79
00:04:37,000 --> 00:04:39,000
că există bug-uri în codul dvs. și teste care nu sunt trecute,

80
00:04:39,000 --> 00:04:43,000
puteți pune în timp mai eficace în față pentru a rezolva aceste probleme

81
00:04:43,000 --> 00:04:45,000
mai degrabă decât pierde puncte, pentru a primi feedback de la TF dvs.,

82
00:04:45,000 --> 00:04:48,000
și du-te apoi, "Ah," ca și cum aș fi dat seama.

83
00:04:48,000 --> 00:04:50,000
Acum, cel puțin există un instrument pentru a vă ajuta să găsiți asta.

84
00:04:50,000 --> 00:04:52,000
Acesta nu va arate unde bug-ul este, dar vă va spune

85
00:04:52,000 --> 00:04:54,000
ceea ce este simptomatic din ea.

86
00:04:54,000 --> 00:04:57,000
>> Acum realiza testele nu sunt neapărat exhaustivă.

87
00:04:57,000 --> 00:04:59,000
Doar pentru că veți obține un ecran plin de verde fețe zâmbitoare

88
00:04:59,000 --> 00:05:02,000
nu înseamnă codul este perfect, dar aceasta nu înseamnă

89
00:05:02,000 --> 00:05:06,000
că a trecut anumite teste prevăzute de spec..

90
00:05:06,000 --> 00:05:08,000
Uneori nu ne va elibera cecuri.

91
00:05:08,000 --> 00:05:10,000
De exemplu, roman sau film polițist, unul dintre aspectele PSET 4,

92
00:05:10,000 --> 00:05:15,000
este un fel de dezamăgitor dacă am da

93
00:05:15,000 --> 00:05:18,000
Răspunsul la ceea ce este, și există un număr de moduri de a descoperi

94
00:05:18,000 --> 00:05:21,000
care persoana este în acel zgomot roșu.

95
00:05:21,000 --> 00:05:24,000
Spec. va specifica întotdeauna în viitor, pentru PSET 5 mai departe

96
00:05:24,000 --> 00:05:26,000
ce verifică exista pentru tine.

97
00:05:26,000 --> 00:05:28,000
Veți observa că e URL-ul alb la partea de jos.

98
00:05:28,000 --> 00:05:30,000
Pentru moment, aceasta este doar de ieșire de diagnosticare.

99
00:05:30,000 --> 00:05:33,000
Daca vizitati că URL-ul, veți obține o grămadă de mesaje criptice, nebun

100
00:05:33,000 --> 00:05:36,000
că ești binevenit să se uite prin, dar este mai ales pentru personalul

101
00:05:36,000 --> 00:05:41,000
astfel încât să putem diagnostica și a depana bug-uri în check50 sine.

102
00:05:41,000 --> 00:05:46,000
>> Fără formalități, să trecem la unde am rămas.

103
00:05:46,000 --> 00:05:48,000
Biblioteca CS50-am luat de-a gata pentru câteva săptămâni,

104
00:05:48,000 --> 00:05:52,000
dar apoi săptămâna trecută, am început peeling, unul din straturile de ea.

105
00:05:52,000 --> 00:05:55,000
Am început punerea deoparte șir în favoarea a ceea ce în schimb?

106
00:05:55,000 --> 00:05:57,000
[Elevii] Char.

107
00:05:57,000 --> 00:05:59,000
* Char, care a fost un char * tot acest timp,

108
00:05:59,000 --> 00:06:03,000
dar acum nu avem de a pretinde că este un real de date de tip șir.

109
00:06:03,000 --> 00:06:06,000
Mai degrabă, a fost un sinonim pentru felul de char *,

110
00:06:06,000 --> 00:06:09,000
și un șir este o secvență de caractere,

111
00:06:09,000 --> 00:06:14,000
așa că de ce nu se face sens pentru a reprezenta siruri de caractere ca e char *?

112
00:06:14,000 --> 00:06:20,000
Ce face un char * reprezintă, în contextul acestui concept a unui șir?

113
00:06:20,000 --> 00:06:23,000
Da >> [Student]. Primul caracter.

114
00:06:23,000 --> 00:06:25,000
Bine, primul caracter, dar nu destul de primul caracter.

115
00:06:25,000 --> 00:06:27,000
E de-[Studenții] Adresa.

116
00:06:27,000 --> 00:06:29,000
Bine, adresa primului caracter.

117
00:06:29,000 --> 00:06:33,000
Tot ceea ce este necesar pentru a reprezenta un șir în memoria unui computer

118
00:06:33,000 --> 00:06:36,000
este doar adresa unică de octet primul său.

119
00:06:36,000 --> 00:06:38,000
Tu nu au nici măcar să știu cât timp mai este

120
00:06:38,000 --> 00:06:42,000
deoarece cum poți seama de asta dinamic?

121
00:06:42,000 --> 00:06:44,000
[Student] lungimea șirului.

122
00:06:44,000 --> 00:06:48,000
Puteți apela lungimea șirului, excelent, dar cum nu Distanța de muncă șir?

123
00:06:48,000 --> 00:06:50,000
Ce face? Da.

124
00:06:50,000 --> 00:06:52,000
[Student] Continuă să mergi până când veți obține caracterul nul.

125
00:06:52,000 --> 00:06:54,000
Da, exact, doar cu o iterează pentru buclă, în timp ce bucla,

126
00:06:54,000 --> 00:06:57,000
indiferent de la * până la capăt, și sfârșitul este reprezentată

127
00:06:57,000 --> 00:07:01,000
de \ 0, caracterul așa-numitul nul, Nul,

128
00:07:01,000 --> 00:07:05,000
a nu se confunda cu nul, care este un pointer,

129
00:07:05,000 --> 00:07:07,000
care va veni intr-o conversatie din nou astăzi.

130
00:07:07,000 --> 00:07:11,000
>> Am cojit înapoi un strat de GetInt, iar apoi am luat o privire la getString,

131
00:07:11,000 --> 00:07:14,000
și reamintească faptul că aceste două funcții, sau într-adevăr,

132
00:07:14,000 --> 00:07:18,000
GetString, a fost folosind o anumita functie

133
00:07:18,000 --> 00:07:21,000
pentru a analiza, de fapt, care este, citi sau analiza, intrarea utilizatorului.

134
00:07:21,000 --> 00:07:25,000
Și ce a fost asta nouă funcție?

135
00:07:25,000 --> 00:07:27,000
Scanf sau sscanf. Este de fapt, vine într-un arome câteva diferite.

136
00:07:27,000 --> 00:07:31,000
Nu e scanf, sscanf e, nu e fscanf.

137
00:07:31,000 --> 00:07:35,000
Pentru moment, însă, să se concentreze pe cea mai ușor de ilustrat,

138
00:07:35,000 --> 00:07:38,000
și lasă-mă să merg mai departe și deschide în aparat

139
00:07:38,000 --> 00:07:41,000
un fișier ca asta, scanf1.c.

140
00:07:41,000 --> 00:07:43,000
Acesta este un program de super-simplu,

141
00:07:43,000 --> 00:07:46,000
dar care face ceva ce nu am făcut

142
00:07:46,000 --> 00:07:48,000
fără ajutorul bibliotecii CS50.

143
00:07:48,000 --> 00:07:51,000
Acest lucru devine o int de la un utilizator. Cum funcționează?

144
00:07:51,000 --> 00:07:53,000
Ei bine, în linia 16 acolo,

145
00:07:53,000 --> 00:07:56,000
observați că ne pronunțăm un x int numit, și în acest moment, în poveste,

146
00:07:56,000 --> 00:07:58,000
ceea ce este valoarea lui x?

147
00:07:58,000 --> 00:08:00,000
[Răspuns studentul neauzit]

148
00:08:00,000 --> 00:08:02,000
[David M.] Corect, cine stie, o valoare gunoi potențial, atât în ​​17, am spune doar utilizatorul

149
00:08:02,000 --> 00:08:06,000
da-mi un număr, vă rugăm, și pasul 18 este în cazul în care acesta devine interesant.

150
00:08:06,000 --> 00:08:11,000
Scanf pare să împrumute de la o idee printf prin faptul că utilizează aceste coduri format în ghilimele.

151
00:08:11,000 --> 00:08:13,000
D% este, desigur, un număr zecimal.

152
00:08:13,000 --> 00:08:21,000
Dar de ce sunt eu de întâlnire, în loc de x & x doar?

153
00:08:21,000 --> 00:08:24,000
Fosta este corectă. Da.

154
00:08:24,000 --> 00:08:26,000
[Răspuns studentul neauzit]

155
00:08:26,000 --> 00:08:31,000
Exact, dacă scopul acestui program, la fel ca GetInt funcția în sine,

156
00:08:31,000 --> 00:08:34,000
este de a obtine o int de la utilizatorul pot trece funcții

157
00:08:34,000 --> 00:08:38,000
toate variabilele vreau, dar dacă nu le trece prin trimitere

158
00:08:38,000 --> 00:08:41,000
sau prin adresa sau prin indicatorul, toate sinonim pentru scopuri de astăzi,

159
00:08:41,000 --> 00:08:46,000
atunci această funcție nu are capacitatea de a schimba conținutul acestei variabile.

160
00:08:46,000 --> 00:08:49,000
Acest lucru ar trece într-un exemplar la fel ca versiunea buggy a swap-ului

161
00:08:49,000 --> 00:08:51,000
pe care le-am vorbit despre câteva ori acum.

162
00:08:51,000 --> 00:08:54,000
>> Dar, în loc, făcând & x, eu sunt literalmente trece în ce?

163
00:08:54,000 --> 00:08:57,000
[Student] adresa. >> Adresa lui x.

164
00:08:57,000 --> 00:09:01,000
E ca și cum desen o hartă pentru funcția scanf numit și spune aici,

165
00:09:01,000 --> 00:09:04,000
acestea sunt orienta spre o bucată de memorie în calculatorul

166
00:09:04,000 --> 00:09:07,000
pe care poti sa te duci stoca unele întreg inch

167
00:09:07,000 --> 00:09:10,000
Pentru sscanf pentru a face acum, că

168
00:09:10,000 --> 00:09:13,000
ce operatorul, ce bucată de sintaxă este că va trebui să utilizeze

169
00:09:13,000 --> 00:09:19,000
chiar dacă nu putem să-l vadă pentru că altcineva a scris această funcție?

170
00:09:19,000 --> 00:09:21,000
Cu alte cuvinte - ce e asta?

171
00:09:21,000 --> 00:09:23,000
[Student] X citit.

172
00:09:23,000 --> 00:09:27,000
Nu va fi o lectură, dar numai în ceea ce privește x aici.

173
00:09:27,000 --> 00:09:30,000
Dacă scanf este trecut adresa lui x,

174
00:09:30,000 --> 00:09:35,000
punct de vedere sintactic, ceea ce operatorul este obligat să existe undeva

175
00:09:35,000 --> 00:09:38,000
în interiorul punerii în aplicare, astfel încât scanf scanf

176
00:09:38,000 --> 00:09:42,000
pot scrie de fapt, un număr de 2 la acea adresă?

177
00:09:42,000 --> 00:09:44,000
Da, așa *.

178
00:09:44,000 --> 00:09:47,000
Amintiti-va ca * este operatorul nostru dereference, care, în esență înseamnă du-te acolo.

179
00:09:47,000 --> 00:09:50,000
>> După ce ați fost înmânat o adresă, așa cum este cazul aici,

180
00:09:50,000 --> 00:09:53,000
scanf este, probabil, de fapt, dacă ne-uitat în jurul valorii de sursa acesteia code-

181
00:09:53,000 --> 00:09:59,000
este de a face * x sau echivalent pentru a merge de fapt la acea adresă și a pus acolo o anumită valoare.

182
00:09:59,000 --> 00:10:02,000
Acum, ca și pentru modul în care scanf primeste de intrare de la tastatură,

183
00:10:02,000 --> 00:10:04,000
ne vom flutura mainile noastre din ziua de azi.

184
00:10:04,000 --> 00:10:07,000
Doar presupunem că sistemul de operare permite sscanf pentru a vorbi

185
00:10:07,000 --> 00:10:11,000
la tastatura utilizatorului, dar în acest moment acum în linia 19,

186
00:10:11,000 --> 00:10:14,000
atunci când am imprima pur și simplu x, pare a fi cazul

187
00:10:14,000 --> 00:10:17,000
scanf care a pus-o în int x.

188
00:10:17,000 --> 00:10:19,000
Asta e exact cum functioneaza scanf, și amintesc săptămâna trecută

189
00:10:19,000 --> 00:10:25,000
asta e exact cum getString și GetInt și familia acestuia a altor funcții

190
00:10:25,000 --> 00:10:28,000
în cele din urmă funcționează, deși cu o ușoară variație ca sscanf,

191
00:10:28,000 --> 00:10:31,000
ceea ce înseamnă scana un șir în loc de tastatură.

192
00:10:31,000 --> 00:10:33,000
Dar haideți să aruncăm o privire la o variație mică a acestui.

193
00:10:33,000 --> 00:10:37,000
În scanf2, de fapt am dat-on bară.

194
00:10:37,000 --> 00:10:42,000
Ceea ce este greșit și-mi voi ascunde comentariu care explica la fel de mult-

195
00:10:42,000 --> 00:10:47,000
ceea ce este în neregulă cu acest program, versiunea 2?

196
00:10:47,000 --> 00:10:55,000
Să fie cât mai tehnic posibil de data asta.

197
00:10:55,000 --> 00:10:57,000
Se pare destul de bine.

198
00:10:57,000 --> 00:11:03,000
E frumos indentat, dar-

199
00:11:03,000 --> 00:11:07,000
bine, cum să-l prune despre despre jos întrebări scurte?

200
00:11:07,000 --> 00:11:17,000
Linia 16. Ce e linia 16 face în limba engleză, dar precis tehnic?

201
00:11:17,000 --> 00:11:20,000
Noțiuni de bază un pic ciudat. Da, Michael.

202
00:11:20,000 --> 00:11:25,000
[Student] E indică spre prima literă a unui șir.

203
00:11:25,000 --> 00:11:27,000
>> Bine, aproape. Permiteți-mi să tweak că un pic.

204
00:11:27,000 --> 00:11:33,000
Arătând spre prima literă a unui șir, se declară o variabilă numită tampon

205
00:11:33,000 --> 00:11:36,000
care va indica la prima adresă a unui șir,

206
00:11:36,000 --> 00:11:39,000
sau, mai degrabă, că va indica mai precis la un char.

207
00:11:39,000 --> 00:11:42,000
Observă că nu este de fapt îndreptat oriunde, deoarece nu exista nici o operatorului de atribuire.

208
00:11:42,000 --> 00:11:46,000
Nu e nici un semn egal, asa ca tot ce facem este alocarea tampon variabila numita.

209
00:11:46,000 --> 00:11:49,000
Se întâmplă să fie 32 de biți, deoarece este un pointer,

210
00:11:49,000 --> 00:11:52,000
și conținutul buffer probabil în cele din urmă

211
00:11:52,000 --> 00:11:57,000
va conține o adresă a unui char, dar pentru acum, ceea ce nu conține tampon?

212
00:11:57,000 --> 00:11:59,000
Doar unele false, cine știe, unii gunoi valoare,

213
00:11:59,000 --> 00:12:03,000
pentru că nu am în mod explicit initializat, așa că nu ar trebui să-și asume nimic.

214
00:12:03,000 --> 00:12:06,000
Ok, deci acum linia 17 este-ceea ce nu face linia 17?

215
00:12:06,000 --> 00:12:08,000
Poate că va incalzi asta.

216
00:12:08,000 --> 00:12:10,000
Se imprimă un șir, nu?

217
00:12:10,000 --> 00:12:12,000
Se imprimă String rog.

218
00:12:12,000 --> 00:12:15,000
>> Linia 18 este un fel de familiară acum în faptul că am văzut doar o variație a acestei

219
00:12:15,000 --> 00:12:18,000
dar cu un cod format diferit, astfel încât în ​​linia 18,

220
00:12:18,000 --> 00:12:23,000
ne spune scanf aici este adresa o bucată de memorie.

221
00:12:23,000 --> 00:12:27,000
Vreau să sune într-un șir, așa cum se sugerează de către% s,

222
00:12:27,000 --> 00:12:32,000
dar problema este că nu am făcut câteva lucruri aici.

223
00:12:32,000 --> 00:12:35,000
Care este una dintre problemele?

224
00:12:35,000 --> 00:12:38,000
[Student] Încearcă să dereference un pointer nul.

225
00:12:38,000 --> 00:12:41,000
Indicii bine, nule sau pur și simplu altfel necunoscute.

226
00:12:41,000 --> 00:12:45,000
Ești predarea scanf o adresă, dar tocmai ai spus-o clipă în urmă

227
00:12:45,000 --> 00:12:49,000
că această adresă este o anumită valoare gunoi, deoarece nu am atribui fapt la nimic,

228
00:12:49,000 --> 00:12:53,000
și așa mai spui scanf merge în mod eficient a pus un șir de aici,

229
00:12:53,000 --> 00:12:56,000
dar nu știm unde este încă aici,

230
00:12:56,000 --> 00:12:59,000
deci nu am alocat efectiv de memorie tampon pentru.

231
00:12:59,000 --> 00:13:03,000
Mai mult decât atât, ceea ce ești, de asemenea, nu spune chiar scanf?

232
00:13:03,000 --> 00:13:06,000
Să presupunem că aceasta a fost o bucată de memorie, și nu a fost o valoare gunoi,

233
00:13:06,000 --> 00:13:09,000
dar tu încă nu spui scanf ceva important.

234
00:13:09,000 --> 00:13:12,000
[Student] În cazul în care este de fapt, ampersand.

235
00:13:12,000 --> 00:13:15,000
Ampersand, astfel încât în ​​acest caz, e în regulă.

236
00:13:15,000 --> 00:13:18,000
Deoarece tampon este deja declarat ca un pointer

237
00:13:18,000 --> 00:13:22,000
cu piesa * de sintaxă, nu avem nevoie de a utiliza ampersand

238
00:13:22,000 --> 00:13:25,000
pentru ca este deja o adresă, dar cred că l-am auzit aici.

239
00:13:25,000 --> 00:13:27,000
[Student] Cât de mare este?

240
00:13:27,000 --> 00:13:29,000
Bine, nu ne spune cât de mare scanf acest buffer este,

241
00:13:29,000 --> 00:13:32,000
ceea ce înseamnă, chiar dacă au fost tampon un pointer,

242
00:13:32,000 --> 00:13:35,000
spunem scanf, a pus un șir de aici,

243
00:13:35,000 --> 00:13:38,000
dar aici ar putea fi 2 octeți, aceasta ar putea fi de 10 bytes, ar putea fi un megabyte.

244
00:13:38,000 --> 00:13:41,000
Scanf are nici o idee, și pentru că aceasta este o bucată de memorie

245
00:13:41,000 --> 00:13:43,000
probabil, nu e un șir încă.

246
00:13:43,000 --> 00:13:48,000
E doar un șir de caractere, odată ce scrie și un 0 \ la faptul că bucata de memorie.

247
00:13:48,000 --> 00:13:51,000
Acum e doar o bucată de memorie.

248
00:13:51,000 --> 00:13:55,000
Scanf nu va ști când să se oprească scris la acea adresă.

249
00:13:55,000 --> 00:13:59,000
>> Dacă vă reamintesc câteva exemple din trecut unde am tastat la întâmplare pe tastatură

250
00:13:59,000 --> 00:14:03,000
încercând să se reverse un tampon, si am vorbit vineri despre exact asta.

251
00:14:03,000 --> 00:14:07,000
În cazul în care un adversar oarecum injecteaza în programul tău un cuvânt mult mai mare

252
00:14:07,000 --> 00:14:10,000
sau o propoziție sau frază, atunci te așteptai puteți depășire

253
00:14:10,000 --> 00:14:13,000
o bucată de memorie, care poate avea consecințe negative,

254
00:14:13,000 --> 00:14:15,000
cum ar fi preluarea întregului program în sine.

255
00:14:15,000 --> 00:14:17,000
Avem nevoie de a remedia această cumva.

256
00:14:17,000 --> 00:14:20,000
Lasă-mă să zoom out și du-te în versiunea 3 a acestui program.

257
00:14:20,000 --> 00:14:22,000
Asta e un pic mai bine.

258
00:14:22,000 --> 00:14:24,000
În această versiune, observați diferența.

259
00:14:24,000 --> 00:14:27,000
În linia 16, am declarat din nou un tampon variabilă numită,

260
00:14:27,000 --> 00:14:29,000
dar ceea ce este acum?

261
00:14:29,000 --> 00:14:33,000
Este o serie de 16 caractere.

262
00:14:33,000 --> 00:14:36,000
Acest lucru este bun pentru că acest lucru înseamnă că pot spune acum scanf

263
00:14:36,000 --> 00:14:39,000
aici este o bucată reală de memorie.

264
00:14:39,000 --> 00:14:42,000
Vă puteți gândi la aproape de matrice ca fiind pointeri acum,

265
00:14:42,000 --> 00:14:44,000
chiar dacă acestea nu sunt de fapt echivalent.

266
00:14:44,000 --> 00:14:47,000
Vor comporta diferit în contexte diferite.

267
00:14:47,000 --> 00:14:50,000
Dar e cu siguranță cazul în care buffer-ul este de afiliere

268
00:14:50,000 --> 00:14:53,000
16 caractere învecinate, deoarece asta e ceea ce este o matrice

269
00:14:53,000 --> 00:14:55,000
și a fost pentru câteva săptămâni acum.

270
00:14:55,000 --> 00:14:59,000
>> Aici, eu spun scanf aici e un segment de memorie.

271
00:14:59,000 --> 00:15:01,000
De această dată, este de fapt o bucata de memorie,

272
00:15:01,000 --> 00:15:07,000
dar de ce este acest program încă de exploatat?

273
00:15:07,000 --> 00:15:11,000
Ce e în neregulă încă?

274
00:15:11,000 --> 00:15:14,000
Am spus să-mi dai 16 bytes, dar-

275
00:15:14,000 --> 00:15:16,000
[Student] Ce dacă tastați în mai mult de 16?

276
00:15:16,000 --> 00:15:20,000
Exact, ce se întâmplă dacă utilizatorul tipurile din 17 caractere sau caractere 1700?

277
00:15:20,000 --> 00:15:23,000
De fapt, hai să vedem dacă nu putem împiedica de această greșeală acum.

278
00:15:23,000 --> 00:15:25,000
E mai bine, dar nu perfect.

279
00:15:25,000 --> 00:15:28,000
Lasă-mă să mergeți mai departe și să rulați make pentru a compila scanf3 acest program.

280
00:15:28,000 --> 00:15:34,000
Lasă-mă să rulați scanf3, te rog String: Buna ziua, am si par a fi în regulă.

281
00:15:34,000 --> 00:15:37,000
Lasă-mă să încerc una ceva mai lung, hello there.

282
00:15:37,000 --> 00:15:42,000
Bine, hai să facem hello there ce mai faci astăzi, Enter.

283
00:15:42,000 --> 00:15:54,000
Noțiuni de bază un fel de norocos aici, hai să spunem hello there ce mai faci.

284
00:15:54,000 --> 00:15:56,000
La naiba.

285
00:15:56,000 --> 00:16:03,000
Bine, așa că am avut noroc. Să vedem dacă nu putem rezolva această problemă.

286
00:16:03,000 --> 00:16:06,000
Nu, nu o să-mi copia.

287
00:16:06,000 --> 00:16:09,000
Să mai încercăm o dată.

288
00:16:09,000 --> 00:16:12,000
În regulă, stand by.

289
00:16:12,000 --> 00:16:20,000
Vom vedea cât de mult pot pretinde să se concentreze în timp ce faci asta încă.

290
00:16:20,000 --> 00:16:23,000
La naiba. Asta e destul de caz, de fapt.

291
00:16:23,000 --> 00:16:26,000
Acolo mergem.

292
00:16:26,000 --> 00:16:30,000
Punctul făcut.

293
00:16:30,000 --> 00:16:34,000
>> Acest lucru, de asemenea, jenant deși este, este de asemenea una dintre sursele de confuzie mare

294
00:16:34,000 --> 00:16:38,000
atunci când scrieți programe care au bug-uri, deoarece acestea se manifestă

295
00:16:38,000 --> 00:16:40,000
doar o singură dată într-un timp uneori.

296
00:16:40,000 --> 00:16:43,000
Realitatea este că, chiar dacă codul dvs. este complet rupt,

297
00:16:43,000 --> 00:16:46,000
ar putea fi complet rupt o dată într-un timp

298
00:16:46,000 --> 00:16:49,000
pentru că, uneori, în esență, ceea ce se întâmplă este alocă sistemului de operare

299
00:16:49,000 --> 00:16:52,000
o memorie pic mai mult decat ai de fapt nevoie pentru orice motiv,

300
00:16:52,000 --> 00:16:57,000
și astfel încât nimeni altcineva foloseste memorie imediat dupa bucată ta de 16 caractere,

301
00:16:57,000 --> 00:17:01,000
așa că, dacă te duci la 17, 18, 19, oricare ar fi, nu e un astfel de afacere mare.

302
00:17:01,000 --> 00:17:04,000
Acum, calculatorul, chiar dacă nu accident în acel moment,

303
00:17:04,000 --> 00:17:09,000
ar putea folosi în cele din urmă numărul de octeți 17 sau 18 sau 19 pentru altceva,

304
00:17:09,000 --> 00:17:14,000
la care punctul datele pe care le pune acolo, deși excesiv de lungă,

305
00:17:14,000 --> 00:17:18,000
este mergi la a lua suprascrise potențial de o alta functie.

306
00:17:18,000 --> 00:17:21,000
Nu e neapărat o să rămână intacte,

307
00:17:21,000 --> 00:17:23,000
dar nu va provoca în mod necesar o defecțiune seg.

308
00:17:23,000 --> 00:17:26,000
Dar în acest caz, am furnizat în cele din urmă caractere suficiente

309
00:17:26,000 --> 00:17:29,000
că am depășit în esență, segmentul meu de memorie, și bam,

310
00:17:29,000 --> 00:17:33,000
sistemul de operare a spus, "Îmi pare rău, că nu e vina bine, segmentare."

311
00:17:33,000 --> 00:17:38,000
>> Și să vedem acum dacă ceea ce rămâne aici, în directorul meu de-

312
00:17:38,000 --> 00:17:40,000
observați că am acest fișier aici, de bază.

313
00:17:40,000 --> 00:17:42,000
Observați că aceasta se numește din nou o groapa de bază.

314
00:17:42,000 --> 00:17:46,000
Este în esență un fișier care conține conținutul memoriei programului tău

315
00:17:46,000 --> 00:17:48,000
la punctul în care sa prăbușit,

316
00:17:48,000 --> 00:17:51,000
și doar să încerce un exemplu pic aici, lasă-mă să merg aici

317
00:17:51,000 --> 00:17:57,000
și a alerga gdb pe scanf3 și apoi specificați un al treilea argument numit miez,

318
00:17:57,000 --> 00:18:01,000
și observați aici, că, dacă am lista codul,

319
00:18:01,000 --> 00:18:06,000
vom fi capabili, ca de obicei, cu gdb pentru a începe de mers pe jos prin intermediul acestui program,

320
00:18:06,000 --> 00:18:10,000
si eu pot rula și de îndată ce am lovit-ca cu comanda pas în gdb-

321
00:18:10,000 --> 00:18:13,000
de îndată ce m-am lovit linia potențial buggy, după tastarea într-un șir imens,

322
00:18:13,000 --> 00:18:16,000
Voi fi în măsură să identifice, de fapt aici.

323
00:18:16,000 --> 00:18:19,000
Mai multe despre acest lucru, deși, în secțiunea din punct de vedere al haldelor de bază

324
00:18:19,000 --> 00:18:22,000
și ca, astfel încât să puteți împinge de fapt, în jurul valorii de interiorul haldei de bază

325
00:18:22,000 --> 00:18:27,000
si vezi pe ce linie programul a eșuat.

326
00:18:27,000 --> 00:18:32,000
Orice întrebări, apoi pe pointeri și pe adresele?

327
00:18:32,000 --> 00:18:36,000
Pentru că astăzi, ne-am de gând să începeți să luați pentru a acordat ca aceste lucruri exista

328
00:18:36,000 --> 00:18:40,000
și știm exact ce sunt.

329
00:18:40,000 --> 00:18:42,000
Da.

330
00:18:42,000 --> 00:18:46,000
>> [Student] Cum de nu ai avut de a pune un ampersand lângă partea-

331
00:18:46,000 --> 00:18:48,000
Bună întrebare.

332
00:18:48,000 --> 00:18:51,000
Cum de nu am avut de a pune un ampersand lângă matrice de caractere cum am făcut-o anterior

333
00:18:51,000 --> 00:18:53,000
cu cele mai multe dintre exemplele noastre?

334
00:18:53,000 --> 00:18:55,000
Răspunsul scurt este matrice sunt un pic aparte.

335
00:18:55,000 --> 00:18:59,000
Vă puteți gândi la aproape un tampon ca fiind de fapt o adresă,

336
00:18:59,000 --> 00:19:03,000
și doar așa se întâmplă să fie cazul în care pătrat suportul notația

337
00:19:03,000 --> 00:19:06,000
este o comoditate, astfel încât să putem intra în suport 0, suport 1,

338
00:19:06,000 --> 00:19:10,000
Suport 2, fără a fi nevoie de a utiliza notația *.

339
00:19:10,000 --> 00:19:13,000
Asta e un pic de o minciună albă, deoarece tablouri și pointeri

340
00:19:13,000 --> 00:19:17,000
sunt, de fapt, un pic diferit, dar ele pot fi de multe ori, dar nu întotdeauna folosite alternativ.

341
00:19:17,000 --> 00:19:21,000
Pe scurt, atunci când o funcție se așteaptă un pointer la o bucată de memorie,

342
00:19:21,000 --> 00:19:24,000
aveți posibilitatea să treci, fie ea o adresă care a fost returnat de malloc,

343
00:19:24,000 --> 00:19:29,000
și vom vedea din nou înainte de malloc lung, sau puteți trece-l numele unui tablou.

344
00:19:29,000 --> 00:19:32,000
Tu nu trebuie să faci ampersand cu matrice, deoarece acestea sunt deja

345
00:19:32,000 --> 00:19:34,000
în esență, ca adrese.

346
00:19:34,000 --> 00:19:36,000
Asta e singura excepție.

347
00:19:36,000 --> 00:19:39,000
Parantezele pătrate a le face speciale.

348
00:19:39,000 --> 00:19:41,000
>> Puteți să puneți un ampersand lângă tampon?

349
00:19:41,000 --> 00:19:43,000
Nu în acest caz.

350
00:19:43,000 --> 00:19:46,000
Asta nu ar funcționa, deoarece, din nou, de acest caz colț

351
00:19:46,000 --> 00:19:49,000
în cazul în care nu sunt destul de matrice, de fapt adrese.

352
00:19:49,000 --> 00:19:54,000
Dar vom veni, probabil, înapoi la faptul că înainte de lung, cu alte exemple.

353
00:19:54,000 --> 00:19:56,000
Să încercăm să rezolve o problemă aici.

354
00:19:56,000 --> 00:20:00,000
Avem o structură de date pe care le-am folosit de ceva timp cunoscut ca un tablou.

355
00:20:00,000 --> 00:20:02,000
Cazul de față, asta e ceea ce am avut.

356
00:20:02,000 --> 00:20:04,000
Dar matrice avea unele dezavantaje și upsides.

357
00:20:04,000 --> 00:20:06,000
Matrice sunt frumoase ce?

358
00:20:06,000 --> 00:20:11,000
Ce e un lucru care vă place, în măsura în care vă place matrice Despre matrici?

359
00:20:11,000 --> 00:20:13,000
Ce e convenabil despre ei? Ce e convingatoare?

360
00:20:13,000 --> 00:20:18,000
De ce am le introducă în primul rând?

361
00:20:18,000 --> 00:20:20,000
Da.

362
00:20:20,000 --> 00:20:27,000
[Student] Acestea pot stoca o mulțime de date, și nu trebuie să utilizați un lucru întreg.

363
00:20:27,000 --> 00:20:29,000
Aveți posibilitatea să utilizați o secțiune.

364
00:20:29,000 --> 00:20:32,000
Bine, cu o matrice se pot stoca o mulțime de date,

365
00:20:32,000 --> 00:20:35,000
și nu trebuie neapărat să utilizeze toate de ea, astfel încât să puteți overallocate,

366
00:20:35,000 --> 00:20:39,000
care ar putea fi convenabil dacă nu știe în avans cum mulți dintre ceva să se aștepte.

367
00:20:39,000 --> 00:20:41,000
>> GetString este un exemplu perfect.

368
00:20:41,000 --> 00:20:44,000
GetString, scrisă de noi, nu are nici o idee cum de multe caractere să se aștepte,

369
00:20:44,000 --> 00:20:48,000
astfel faptul că putem aloca bucăți de memorie contiguă este bun.

370
00:20:48,000 --> 00:20:51,000
Matricele rezolva, de asemenea, o problemă-am văzut acum câteva săptămâni acum

371
00:20:51,000 --> 00:20:54,000
în cazul în care codul dvs. începe să revină în ceva foarte prost proiectat.

372
00:20:54,000 --> 00:20:57,000
Amintiti-va ca am creat o structura elev a chemat pe David,

373
00:20:57,000 --> 00:21:00,000
și apoi că a fost de fapt o alternativă, însă,

374
00:21:00,000 --> 00:21:04,000
pentru a avea un nume de variabilă numită și o altă variabilă numit, cred, casa,

375
00:21:04,000 --> 00:21:08,000
și un alt variabilă numită ID-ul, deoarece în această poveste pe care am vrut apoi să introducă altceva

376
00:21:08,000 --> 00:21:11,000
Rob place în program, așa că am decis apoi așteptați un minut,

377
00:21:11,000 --> 00:21:13,000
Am nevoie pentru a redenumi aceste variabile.

378
00:21:13,000 --> 00:21:16,000
Să numim mea NAME1, ID1, house1.

379
00:21:16,000 --> 00:21:20,000
Să numim lui Rob nume2, house2, ID2.

380
00:21:20,000 --> 00:21:22,000
Dar apoi așteptați un minut, ceea ce despre Tommy?

381
00:21:22,000 --> 00:21:24,000
Apoi am avut trei mai multe variabile.

382
00:21:24,000 --> 00:21:27,000
Am introdus altcineva, patru seturi de variabile.

383
00:21:27,000 --> 00:21:30,000
Lumea a început să se dezordonat foarte repede,

384
00:21:30,000 --> 00:21:33,000
deci am introdus struct, și ceea ce e convingatoare despre un struct?

385
00:21:33,000 --> 00:21:39,000
Ce face un struct C lăsa să faci?

386
00:21:39,000 --> 00:21:42,000
E foarte ciudat azi.

387
00:21:42,000 --> 00:21:44,000
Ce >> [elevului răspunsul neauzit]?

388
00:21:44,000 --> 00:21:47,000
Da, în mod special, typedef vă permite să creați un nou tip de date,

389
00:21:47,000 --> 00:21:51,000
și struct, cuvântul cheie struct, vă permite să îngloba

390
00:21:51,000 --> 00:21:54,000
piese conceptual legate de date, împreună

391
00:21:54,000 --> 00:21:56,000
și, ulterior, le numim ceva ca un elev.

392
00:21:56,000 --> 00:21:58,000
>> Asta a fost bună pentru că acum putem modela

393
00:21:58,000 --> 00:22:03,000
un fel mult mai mult din punct de vedere conceptual coerentă noțiunea de un student într-o variabilă

394
00:22:03,000 --> 00:22:07,000
, mai degrabă decât având în mod arbitrar unul pentru un șir, unul pentru un ID, și așa mai departe.

395
00:22:07,000 --> 00:22:10,000
Matricile sunt frumoase, deoarece acestea ne permit să înceapă curățarea codul nostru.

396
00:22:10,000 --> 00:22:13,000
Dar ceea ce este un dezavantaj acum de o matrice?

397
00:22:13,000 --> 00:22:15,000
Ceea ce nu pot face? Da.

398
00:22:15,000 --> 00:22:17,000
[Student] Trebuie sa stii cat de mare este.

399
00:22:17,000 --> 00:22:19,000
Trebuie să știi cât de mare este, deci este un fel de durere.

400
00:22:19,000 --> 00:22:21,000
Aceia dintre voi cu experienta in programare prealabilă știu că într-o mulțime de limbi,

401
00:22:21,000 --> 00:22:24,000
cum ar fi Java, puteți solicita o bucată de memorie, mai precis o matrice,

402
00:22:24,000 --> 00:22:28,000
cât de mare ești, cu o lungime, de proprietate, ca să spunem așa, și asta e foarte convenabil.

403
00:22:28,000 --> 00:22:32,000
În C, nu puteți apela chiar strlen pe o matrice generică

404
00:22:32,000 --> 00:22:35,000
deoarece strlen, după cum cuvântul implică, este doar pentru siruri de caractere,

405
00:22:35,000 --> 00:22:39,000
și vă puteți da seama lungimii unui șir din cauza acestei convenții umane

406
00:22:39,000 --> 00:22:43,000
de a avea o 0 \, ci o matrice, mai generic, este doar o bucată de memorie.

407
00:22:43,000 --> 00:22:46,000
Dacă e o serie de Ints, nu va fi un caracter special

408
00:22:46,000 --> 00:22:48,000
la sfârșitul așteptare pentru tine.

409
00:22:48,000 --> 00:22:50,000
Trebuie sa ne amintim lungimea unui array.

410
00:22:50,000 --> 00:22:54,000
Un alt dezavantaj al unei matrice crescute capul în getString sine.

411
00:22:54,000 --> 00:22:59,000
Ce este un alt dezavantaj al unei matrice?

412
00:22:59,000 --> 00:23:01,000
Domnule, doar tu și cu mine azi.

413
00:23:01,000 --> 00:23:04,000
[Răspuns studentul nu pot fi auzite] >> E ce?

414
00:23:04,000 --> 00:23:06,000
Este declarat pe stiva.

415
00:23:06,000 --> 00:23:09,000
Bine, a declarat pe stiva. De ce nu vă place asta?

416
00:23:09,000 --> 00:23:13,000
[Student], deoarece este reutilizat.

417
00:23:13,000 --> 00:23:15,000
Acesta devine refolosite.

418
00:23:15,000 --> 00:23:18,000
Bine, dacă utilizați o matrice pentru a aloca memorie,

419
00:23:18,000 --> 00:23:21,000
nu se poate, de exemplu, să îl înapoieze pentru că e pe stivă.

420
00:23:21,000 --> 00:23:23,000
Bine, asta e un dezavantaj.

421
00:23:23,000 --> 00:23:25,000
Și cum despre celălalt cu o matrice?

422
00:23:25,000 --> 00:23:28,000
După ce-l aloce, ești un fel de greșit, dacă aveți nevoie de mai mult spațiu

423
00:23:28,000 --> 00:23:30,000
decât faptul că are matrice.

424
00:23:30,000 --> 00:23:34,000
>> Apoi am introdus, rechemare, malloc, care ne-a dat capacitatea de a aloca dinamic memorie.

425
00:23:34,000 --> 00:23:37,000
Dar ce se întâmplă dacă am încercat-o lume cu totul alta?

426
00:23:37,000 --> 00:23:40,000
Ce se întâmplă dacă am vrut să rezolve o serie de aceste probleme

427
00:23:40,000 --> 00:23:45,000
asa ca am loc de-pen-ul meu a adormit aici,

428
00:23:45,000 --> 00:23:51,000
Ce se întâmplă dacă am vrut să creăm loc în esență, o lume care nu mai este așa?

429
00:23:51,000 --> 00:23:56,000
Aceasta este o matrice, și, desigur, acest tip de deteriorează o dată ne-am lovit la sfârșitul matrice,

430
00:23:56,000 --> 00:24:00,000
iar eu acum nu mai am spațiu pentru un alt număr întreg sau un alt caracter.

431
00:24:00,000 --> 00:24:03,000
Ce se întâmplă dacă am un fel de prevenitor spun bine, de ce nu ne relaxa

432
00:24:03,000 --> 00:24:07,000
această cerință ca toate aceste bucati de memorie contiguă fie spate în spate,

433
00:24:07,000 --> 00:24:10,000
si de ce nu, atunci când am nevoie de un int sau un char,

434
00:24:10,000 --> 00:24:12,000
da-mi spațiu pentru una dintre ele?

435
00:24:12,000 --> 00:24:14,000
Și când am nevoie de altul, da-mi un alt spațiu,

436
00:24:14,000 --> 00:24:16,000
și atunci când am nevoie de un alt, dă-mi un alt spațiu.

437
00:24:16,000 --> 00:24:19,000
Avantajul de care acum este că, dacă altcineva

438
00:24:19,000 --> 00:24:21,000
ia memorie de aici, nu e mare lucru.

439
00:24:21,000 --> 00:24:25,000
Voi lua această bucată suplimentară de memorie aici și apoi aceasta.

440
00:24:25,000 --> 00:24:28,000
>> Acum, Captura doar aici este faptul că această aproape simte ca am

441
00:24:28,000 --> 00:24:30,000
o gramada de variabile diferite.

442
00:24:30,000 --> 00:24:33,000
Acest lucru se simte ca cinci variabile diferite de potential.

443
00:24:33,000 --> 00:24:36,000
Dar ce se întâmplă dacă am fura o idee din siruri de caractere

444
00:24:36,000 --> 00:24:41,000
prin care ne lega cumva aceste lucruri împreună conceptual, și ce dacă am făcut asta?

445
00:24:41,000 --> 00:24:44,000
Acest lucru este mea de săgeată foarte slab trase.

446
00:24:44,000 --> 00:24:46,000
Dar să presupunem că fiecare din aceste bucăți de memorie

447
00:24:46,000 --> 00:24:52,000
arătat la alta, iar acest tip, care nu are nici fratele său la dreapta,

448
00:24:52,000 --> 00:24:54,000
nu are nici o săgeată astfel.

449
00:24:54,000 --> 00:24:56,000
Acest lucru este, de fapt, ceea ce se numește o listă legat.

450
00:24:56,000 --> 00:25:00,000
Aceasta este o structură de date nouă, care ne permite să aloce un segment de memorie,

451
00:25:00,000 --> 00:25:03,000
apoi alta, apoi alta, apoi alta, în orice moment dorim

452
00:25:03,000 --> 00:25:07,000
în timpul unui program, și ne amintim că toate acestea sunt într-un fel legate de

453
00:25:07,000 --> 00:25:11,000
prin înlănțuirea literalmente le împreună, și am făcut-o aici, pictural cu o săgeată.

454
00:25:11,000 --> 00:25:15,000
Dar în cod, ceea ce ar fi mecanismul prin care ai putea conecta cumva,

455
00:25:15,000 --> 00:25:20,000
aproape ca Scratch, o bucată la alta bucată?

456
00:25:20,000 --> 00:25:22,000
Am putea folosi un pointer, nu?

457
00:25:22,000 --> 00:25:25,000
Deoarece într-adevăr pe săgeata care se întâmplă de la pătrat din stânga sus,

458
00:25:25,000 --> 00:25:31,000
acest tip aici cu acesta, ar putea conține în interiorul acestui pătrat

459
00:25:31,000 --> 00:25:34,000
nu doar unele Ints, nu doar un char, dar dacă de fapt am alocat

460
00:25:34,000 --> 00:25:37,000
un spațiu suplimentar pic, astfel că acum,

461
00:25:37,000 --> 00:25:41,000
fiecare dintre bucăți mele de memorie, chiar dacă acest lucru este de gând să mă coste,

462
00:25:41,000 --> 00:25:45,000
acum pare un pic mai mult dreptunghiulară în cazul în care una dintre bucăți de memorie

463
00:25:45,000 --> 00:25:47,000
este folosit pentru un număr, cum ar fi numărul 1,

464
00:25:47,000 --> 00:25:50,000
și apoi, dacă acest tip stochează numărul 2,

465
00:25:50,000 --> 00:25:52,000
această bucată de alte memorie este folosit pentru o săgeată,

466
00:25:52,000 --> 00:25:54,000
sau mai concret, un pointer.

467
00:25:54,000 --> 00:25:59,000
Și să presupunem că am păstra numărul 3 de aici în timp ce eu folosesc aceasta pentru a indica la tipul ăla,

468
00:25:59,000 --> 00:26:02,000
și acum tipul ăsta, să presupunem Vreau doar trei bucati astfel de memorie.

469
00:26:02,000 --> 00:26:05,000
Voi trage o linie prin care, indicând nul.

470
00:26:05,000 --> 00:26:07,000
Nu există nici un caracter suplimentar.

471
00:26:07,000 --> 00:26:10,000
>> Într-adevăr, acest lucru este modul în care putem merge despre punerea în aplicare a

472
00:26:10,000 --> 00:26:12,000
ceva ce se numește o listă legat.

473
00:26:12,000 --> 00:26:18,000
O listă legată este o structura de date nouă, și este o piatră de temelie spre

474
00:26:18,000 --> 00:26:21,000
structuri de date mult mai frumoase, care încep să rezolve problemele

475
00:26:21,000 --> 00:26:23,000
de-a lungul liniilor de Facebook-tip problemelor și Google de tip probleme

476
00:26:23,000 --> 00:26:26,000
în cazul în care aveți seturi imense de date, și nu-l mai taie

477
00:26:26,000 --> 00:26:29,000
pentru a stoca și de a folosi tot ceea ce contiguously ceva de genul căutare liniară

478
00:26:29,000 --> 00:26:31,000
sau chiar ceva de genul căutare binară.

479
00:26:31,000 --> 00:26:33,000
Vrei ori chiar mai bune de funcționare.

480
00:26:33,000 --> 00:26:37,000
De fapt, una dintre cele mai grails sfinte vom vorbi despre mai târziu în această săptămână sau viitoare

481
00:26:37,000 --> 00:26:41,000
este un algoritm al cărui timp de rulare este constantă.

482
00:26:41,000 --> 00:26:44,000
Cu alte cuvinte, este nevoie întotdeauna aceeași cantitate de timp, indiferent de

483
00:26:44,000 --> 00:26:47,000
cât de mare de intrare este, și că ar fi într-adevăr convingătoare,

484
00:26:47,000 --> 00:26:49,000
chiar mai mult decât ceva logaritmică.

485
00:26:49,000 --> 00:26:51,000
Ce este acest lucru pe ecran aici?

486
00:26:51,000 --> 00:26:55,000
Fiecare dintre dreptunghiuri este exact ceea ce am desenat de mână.

487
00:26:55,000 --> 00:26:59,000
Dar lucrul tot drumul din stânga este o variabilă specială.

488
00:26:59,000 --> 00:27:02,000
O să fie un pointer unic, pentru că Te-am prins o

489
00:27:02,000 --> 00:27:04,000
cu o listă legată, astfel cum aceste lucruri sunt numite,

490
00:27:04,000 --> 00:27:09,000
este că trebuie să stea pe un capăt al listei legate.

491
00:27:09,000 --> 00:27:13,000
>> La fel ca și cu un șir de caractere, trebuie să știți adresa char primul.

492
00:27:13,000 --> 00:27:15,000
Aceeași afacere pentru listele legate.

493
00:27:15,000 --> 00:27:19,000
Trebuie să știi adresa bucată primul de memorie

494
00:27:19,000 --> 00:27:25,000
pentru că de acolo, puteți ajunge la fiecare celălalt.

495
00:27:25,000 --> 00:27:27,000
Dezavantaj.

496
00:27:27,000 --> 00:27:30,000
Ce preț vom plăti pentru această versatilitate de a avea o dinamică

497
00:27:30,000 --> 00:27:34,000
sizable structură de date pe care, dacă avem nevoie de tot mai multă memorie, fin,

498
00:27:34,000 --> 00:27:37,000
aloca doar o bucată mai mult și trage un pointer la

499
00:27:37,000 --> 00:27:39,000
vechi la coada noua listă?

500
00:27:39,000 --> 00:27:41,000
Da.

501
00:27:41,000 --> 00:27:43,000
[Student] Este nevoie de spațiu aproximativ de două ori la fel de mult.

502
00:27:43,000 --> 00:27:45,000
Este nevoie de spațiu de două ori la fel de mult, așa că e cu siguranta un dezavantaj, și am văzut această

503
00:27:45,000 --> 00:27:48,000
compromis între înainte de timp și spațiu și flexibilitate

504
00:27:48,000 --> 00:27:51,000
în cazul în care până acum, nu avem nevoie de 32 biti pentru fiecare dintre aceste numere.

505
00:27:51,000 --> 00:27:57,000
Avem nevoie de 64 de ani, 32 pentru numărul și 32 pentru indicatorul.

506
00:27:57,000 --> 00:27:59,000
Dar, hei, am 2 GB de RAM.

507
00:27:59,000 --> 00:28:02,000
Adăugarea unui alt 32 de biți aici si aici nu pare că mare lucru.

508
00:28:02,000 --> 00:28:05,000
Dar, pentru seturi mari de date, cu siguranta se adaugă până la literalmente de două ori la fel de mult.

509
00:28:05,000 --> 00:28:09,000
Ce e un alt dezavantaj acum, sau ce caracteristică nu ne dăm bătuți,

510
00:28:09,000 --> 00:28:12,000
dacă ne reprezintă liste de lucruri cu o listă legată, și nu un tablou?

511
00:28:12,000 --> 00:28:14,000
[Student] Nu-l poți traversa spate.

512
00:28:14,000 --> 00:28:16,000
Nu-l poți traversa inapoi, deci ești un fel de greșit, dacă sunteți de mers pe jos

513
00:28:16,000 --> 00:28:19,000
de la stânga la dreapta folosind un pentru buclă sau o buclă în timp ce

514
00:28:19,000 --> 00:28:21,000
și apoi îți dai seama, "Oh, vreau să mă întorc la începutul listei."

515
00:28:21,000 --> 00:28:26,000
Tu nu pot, deoarece aceste indicii merge doar de la stânga la dreapta, după cum indică săgețile.

516
00:28:26,000 --> 00:28:29,000
>> Acum, ați putea aminti începutul listei cu o altă variabilă,

517
00:28:29,000 --> 00:28:31,000
dar asta e un complexitate a păstra în minte.

518
00:28:31,000 --> 00:28:35,000
O matrice, indiferent cât de departe te duci, poti sa faci mereu minus, minus, minus, minus

519
00:28:35,000 --> 00:28:37,000
și du-te înapoi de unde ai venit.

520
00:28:37,000 --> 00:28:40,000
Ce este un alt dezavantaj aici? Da.

521
00:28:40,000 --> 00:28:43,000
[Întrebare elev neauzit]

522
00:28:43,000 --> 00:28:47,000
Ai putea, deci ai de fapt, a propus doar o structură de date numit-o listă dublu legat,

523
00:28:47,000 --> 00:28:50,000
și într-adevăr, ar trebui să adăugați un alt indicator pentru fiecare dintre aceste dreptunghiuri

524
00:28:50,000 --> 00:28:53,000
care merge cealalta directie, capul de care

525
00:28:53,000 --> 00:28:55,000
este acum puteți traversa înainte și înapoi,

526
00:28:55,000 --> 00:28:59,000
Dezavantajul de care este acum pe care îl utilizați de trei ori mai multa memorie ca am folosit pentru a

527
00:28:59,000 --> 00:29:04,000
și, de asemenea, adăugarea de complexitate în ceea ce privește codul pe care trebuie să scrie să-l dreapta.

528
00:29:04,000 --> 00:29:08,000
Dar toate acestea sunt, probabil, foarte compromisuri rezonabile, dacă inversare este mai important.

529
00:29:08,000 --> 00:29:10,000
Da.

530
00:29:10,000 --> 00:29:12,000
[Student] Puteți, de asemenea, nu poate avea o listă 2D legat.

531
00:29:12,000 --> 00:29:16,000
Bine, nu poți avea într-adevăr o listă legată 2D.

532
00:29:16,000 --> 00:29:18,000
Ai putea. Nu e aproape la fel de ușor ca o matrice.

533
00:29:18,000 --> 00:29:21,000
Ca un tablou, ce faci suport deschis, suport închis, suport deschis, închis suport,

534
00:29:21,000 --> 00:29:23,000
și veți obține o anumită structură de 2-dimensionale.

535
00:29:23,000 --> 00:29:26,000
Ai putea pune în aplicare o listă 2-dimensionale legate de

536
00:29:26,000 --> 00:29:29,000
dacă faci add-a propus ca tine-un pointer treia la fiecare dintre aceste lucruri,

537
00:29:29,000 --> 00:29:34,000
și dacă te gândești la o altă listă vine la tine de stil 3D

538
00:29:34,000 --> 00:29:40,000
de la ecran pentru noi toți, care este doar un alt lant de un anumit fel.

539
00:29:40,000 --> 00:29:45,000
Am putea face asta, dar nu e la fel de simplu ca tastând suport deschis, suport patrat. Da.

540
00:29:45,000 --> 00:29:48,000
[Întrebare elev neauzit]

541
00:29:48,000 --> 00:29:50,000
Bine, astfel încât acesta este un fotbalist adevarat.

542
00:29:50,000 --> 00:29:54,000
>> Aceste algoritmi pe care le-am pined peste, cum ar fi oh, căutare binară,

543
00:29:54,000 --> 00:29:57,000
puteți căuta o serie de numere de la bord

544
00:29:57,000 --> 00:30:01,000
sau o carte de telefon atât de mult mai rapid dacă utilizați dezbina si cucereste

545
00:30:01,000 --> 00:30:05,000
și un algoritm de căutare binară, dar binar de căutare este necesar două ipoteze.

546
00:30:05,000 --> 00:30:09,000
Una, că datele au fost sortate.

547
00:30:09,000 --> 00:30:11,000
Acum, putem păstra probabil acest sortate,

548
00:30:11,000 --> 00:30:14,000
asa ca poate asta nu e un motiv de îngrijorare, dar, de asemenea, presupune căutarea binară

549
00:30:14,000 --> 00:30:18,000
pe care ați avut acces aleatoriu la lista de numere,

550
00:30:18,000 --> 00:30:21,000
și o matrice vă permite să aveți acces aleatoriu, și de acces aleatoriu,

551
00:30:21,000 --> 00:30:24,000
Adică, dacă ai dat-o matrice, cât de mult timp este să luați

552
00:30:24,000 --> 00:30:26,000
pentru a ajunge la reglaj 0?

553
00:30:26,000 --> 00:30:29,000
O singură operațiune, utilizați doar [0] si tu esti acolo.

554
00:30:29,000 --> 00:30:33,000
Câți pași este nevoie pentru a ajunge la locația 10?

555
00:30:33,000 --> 00:30:36,000
Un pas, te duci la [10] și că ești acolo.

556
00:30:36,000 --> 00:30:40,000
Prin contrast, cum ajungi la întreg zecea într-o listă legată?

557
00:30:40,000 --> 00:30:42,000
Trebuie să începem cu începutul, deoarece esti doar amintindu-

558
00:30:42,000 --> 00:30:45,000
începutul unei liste legate, la fel ca un șir este amintit

559
00:30:45,000 --> 00:30:48,000
de adresa char primul său, și pentru a găsi că int zecea

560
00:30:48,000 --> 00:30:53,000
sau că personajul zecea într-un șir, trebuie să căutați totul naibii.

561
00:30:53,000 --> 00:30:55,000
>> Din nou, nu suntem rezolvarea tuturor problemelor noastre.

562
00:30:55,000 --> 00:31:00,000
Suntem introducerea de noi, dar într-adevăr depinde de ceea ce sunteți încercarea de a proiecta pentru.

563
00:31:00,000 --> 00:31:04,000
În ceea ce privește punerea în aplicare a prezentei de, putem împrumuta o idee de la care structura de student.

564
00:31:04,000 --> 00:31:07,000
Sintaxa este foarte asemanatoare, cu exceptia acum, ideea este un pic mai abstract

565
00:31:07,000 --> 00:31:09,000
decât casa și numele și ID-ul.

566
00:31:09,000 --> 00:31:13,000
Dar eu propun ca am putea avea o structură de date în C

567
00:31:13,000 --> 00:31:17,000
care este numit nod, ca ultimul cuvânt pe diapozitiv sugerează,

568
00:31:17,000 --> 00:31:21,000
în interiorul unui nod, și un nod este doar un container generic în informatică.

569
00:31:21,000 --> 00:31:25,000
Este, de obicei, elaborat ca un cerc sau un pătrat sau dreptunghi ca am facut.

570
00:31:25,000 --> 00:31:27,000
Și în această structură de date, avem un int, n,

571
00:31:27,000 --> 00:31:29,000
asa ca asta e numarul vreau pentru a stoca.

572
00:31:29,000 --> 00:31:36,000
Dar ce este această a doua linie, struct nod * următor?

573
00:31:36,000 --> 00:31:40,000
De ce este acest lucru corect, sau ce rol are acest joc lucru,

574
00:31:40,000 --> 00:31:42,000
chiar daca e un pic criptic, la prima vedere?

575
00:31:42,000 --> 00:31:44,000
Da.

576
00:31:44,000 --> 00:31:46,000
[Răspuns studentul neauzit]

577
00:31:46,000 --> 00:31:50,000
Exact, deci un fel de * prăzii că este un pointer de un anumit fel.

578
00:31:50,000 --> 00:31:53,000
Numele acestui indicator este arbitrar următoare,

579
00:31:53,000 --> 00:32:00,000
dar am putut numi orice vrem, dar ceea ce face acest punct pointer la?

580
00:32:00,000 --> 00:32:03,000
[Student] Un alt nod >> Exact,. Punctele de la un alt nod astfel.

581
00:32:03,000 --> 00:32:05,000
>> Acum, acest lucru este un fel de curiozitate a lui C.

582
00:32:05,000 --> 00:32:09,000
Reamintească faptul că C este citit de un compilator de sus în jos, de la stânga la dreapta,

583
00:32:09,000 --> 00:32:13,000
ceea ce înseamnă că, dacă-acest lucru este un pic diferit de ceea ce am făcut cu elevul.

584
00:32:13,000 --> 00:32:16,000
Când ne-am definit un student, am de fapt, nu a pus o vorbă acolo.

585
00:32:16,000 --> 00:32:18,000
Pur și simplu a spus typedef.

586
00:32:18,000 --> 00:32:20,000
Apoi am avut int id, nume șir de caractere, șir casa,

587
00:32:20,000 --> 00:32:23,000
și apoi student la partea de jos a struct.

588
00:32:23,000 --> 00:32:26,000
Această declarație este un pic diferit, deoarece,

589
00:32:26,000 --> 00:32:28,000
din nou, compilatorul C este un pic prost.

590
00:32:28,000 --> 00:32:30,000
E doar de gând să citesc de sus în jos,

591
00:32:30,000 --> 00:32:33,000
așa că, dacă se ajunge la linia de două aici

592
00:32:33,000 --> 00:32:37,000
în cazul în care este declarată următor și-l vede, oh, aici e o variabilă numită următoare.

593
00:32:37,000 --> 00:32:39,000
E un pointer la un nod struct.

594
00:32:39,000 --> 00:32:42,000
Compilator este de gând să realizeze ceea ce este un nod struct?

595
00:32:42,000 --> 00:32:44,000
N-am mai auzit de chestia asta înainte,

596
00:32:44,000 --> 00:32:47,000
deoarece nodul cuvântul nu s-ar putea să apară altfel

597
00:32:47,000 --> 00:32:49,000
până la partea de jos, astfel încât nu există această redundanță.

598
00:32:49,000 --> 00:32:53,000
Trebuie sa spui nod struct aici, pe care le pot scurta apoi mai târziu

599
00:32:53,000 --> 00:32:56,000
datorită typedef aici, dar acest lucru este din cauza

600
00:32:56,000 --> 00:33:02,000
ne fac referire la structura însăși interiorul structurii.

601
00:33:02,000 --> 00:33:05,000
Asta e prins de acolo.

602
00:33:05,000 --> 00:33:07,000
>> Unele probleme interesante sunt de gând să apară.

603
00:33:07,000 --> 00:33:09,000
Avem o listă de numere. Cum putem introduce în ea?

604
00:33:09,000 --> 00:33:11,000
Cum l-am căuta? Cum putem sterge din el?

605
00:33:11,000 --> 00:33:13,000
Mai ales acum că avem de a gestiona toate aceste indicii.

606
00:33:13,000 --> 00:33:15,000
Te-ai gândit indicii au fost un fel de minte-îndoire

607
00:33:15,000 --> 00:33:17,000
când ai avut unul dintre ei doar încearcă să citească un int la acesta.

608
00:33:17,000 --> 00:33:20,000
Acum avem de a manipula în valoare de o lista intreaga lui.

609
00:33:20,000 --> 00:33:22,000
De ce nu luăm nostru de 5 minute de pauză aici, și apoi vom aduce

610
00:33:22,000 --> 00:33:34,000
unii oameni până pe scenă pentru a face exact acest lucru.

611
00:33:34,000 --> 00:33:36,000
>> C este mult mai distractiv atunci când este acționat.

612
00:33:36,000 --> 00:33:39,000
Cine ar dori să fie primul literal?

613
00:33:39,000 --> 00:33:41,000
Bine, vino sus. Sunteți primul.

614
00:33:41,000 --> 00:33:44,000
Cine ar dori să fie 9? Bine, 9.

615
00:33:44,000 --> 00:33:46,000
Ce zici de 9? 17?

616
00:33:46,000 --> 00:33:51,000
Un pic de clica aici. 22 și 26 din acel rând față.

617
00:33:51,000 --> 00:33:53,000
Și apoi cum despre cineva acolo fiind subliniat de la.

618
00:33:53,000 --> 00:33:57,000
Sunteți 34. Bine, 34, vino sus.

619
00:33:57,000 --> 00:33:59,000
În primul rând este acolo. Bine, toate cele patru dintre voi.

620
00:33:59,000 --> 00:34:01,000
Și cine ne-am spus pentru 9?

621
00:34:01,000 --> 00:34:04,000
Cine este de 9 nostru?

622
00:34:04,000 --> 00:34:07,000
Cine vrea cu adevărat să fie 9? În regulă, haide, să fie 9.

623
00:34:07,000 --> 00:34:10,000
Aici vom merge.

624
00:34:10,000 --> 00:34:13,000
34, vă vom întâlni acolo.

625
00:34:13,000 --> 00:34:17,000
Prima parte este de a face vă arate ca asta.

626
00:34:17,000 --> 00:34:21,000
26, 22, 17, bine.

627
00:34:21,000 --> 00:34:25,000
Dacă puteți sta într-o parte, pentru că am de gând să vă malloc într-un moment.

628
00:34:25,000 --> 00:34:29,000
>> Bine, bine.

629
00:34:29,000 --> 00:34:32,000
Bine, excelent, deci hai să ceară câteva întrebări aici.

630
00:34:32,000 --> 00:34:34,000
Și, de fapt, care e numele tau? >> Anita.

631
00:34:34,000 --> 00:34:37,000
Anita, bine, vino aici.

632
00:34:37,000 --> 00:34:41,000
Anita este de gând să ne ajute fel de a rezolva o întrebare destul de simplă în primul rând,

633
00:34:41,000 --> 00:34:44,000
care este modul în care vă găsiți dacă este sau nu este o valoare în listă?

634
00:34:44,000 --> 00:34:48,000
Acum, observăm că în primul rând, reprezentată aici de Lucas,

635
00:34:48,000 --> 00:34:52,000
este un pic diferit, și așa mai departe bucată de hârtie sa este în mod deliberat lateral

636
00:34:52,000 --> 00:34:55,000
pentru că nu e la fel de inalt si nu se ia ca multi biti,

637
00:34:55,000 --> 00:34:58,000
punct de vedere tehnic, chiar dacă el are aceeași dimensiune a hârtiei doar rotit.

638
00:34:58,000 --> 00:35:01,000
Dar e un pic diferit, în care el este doar 32 de biți pentru un pointer,

639
00:35:01,000 --> 00:35:05,000
și toate aceste tipi sunt 64 de biți, din care jumătate este numărul, din care jumatate este un pointer.

640
00:35:05,000 --> 00:35:08,000
Dar indicatorul nu este reprezentată, așa că dacă voi putea oarecum penibil

641
00:35:08,000 --> 00:35:12,000
folosi mana stanga la punctul de la persoana de lângă tine.

642
00:35:12,000 --> 00:35:14,000
Și tu ești numărul 34. Care e numele tău?

643
00:35:14,000 --> 00:35:16,000
Ari.

644
00:35:16,000 --> 00:35:19,000
Ari, așa, de fapt, țineți hârtia în mâna dreaptă, mâna stângă și merge direct în jos.

645
00:35:19,000 --> 00:35:21,000
Tu reprezinți nul pe stânga.

646
00:35:21,000 --> 00:35:24,000
>> Acum, imaginea noastră umană este foarte consistent.

647
00:35:24,000 --> 00:35:26,000
Aceasta este de fapt modul în care funcționează pointeri.

648
00:35:26,000 --> 00:35:29,000
Și dacă poți mesteca cu zgomot un pic acest fel, asa ca nu sunt in drumul tau.

649
00:35:29,000 --> 00:35:34,000
Anita aici, găsește-mi numărul 22,

650
00:35:34,000 --> 00:35:40,000
dar presupun o constrângere de a nu oamenii rezistă bucăți de hârtie,

651
00:35:40,000 --> 00:35:43,000
dar aceasta este o listă, iar tu trebuie doar să înceapă cu Lucas

652
00:35:43,000 --> 00:35:46,000
pentru că el este literalmente indicatorul primul.

653
00:35:46,000 --> 00:35:51,000
Să presupunem că vă sunt un pointer, și așa ai prea capacitatea de a indica la ceva.

654
00:35:51,000 --> 00:35:56,000
De ce nu începi prin a indica la exact ceea ce Lucas este îndreptat la?

655
00:35:56,000 --> 00:35:58,000
Bine, și lasă-mă să adopte asta de aici.

656
00:35:58,000 --> 00:36:04,000
Doar de dragul discuției, permiteți-mi să trag o pagină goală aici.

657
00:36:04,000 --> 00:36:06,000
Cum se scrie numele tau? >> Anita.

658
00:36:06,000 --> 00:36:08,000
Bine, Anita.

659
00:36:08,000 --> 00:36:18,000
Să spunem nod * Anita = Lucas.

660
00:36:18,000 --> 00:36:22,000
Ei bine, noi nu ar trebui să-ți spun Lucas. Ar trebui să te sun mai întâi.

661
00:36:22,000 --> 00:36:25,000
De ce este acest fapt, în conformitate cu realitatea aici?

662
00:36:25,000 --> 00:36:27,000
Unul, primul deja există.

663
00:36:27,000 --> 00:36:30,000
În primul rând a fost alocată probabil undeva aici.

664
00:36:30,000 --> 00:36:35,000
Nod * în primul rând, și a fost alocată o listă într-un fel.

665
00:36:35,000 --> 00:36:37,000
Nu știu cum sa întâmplat. Asta sa întâmplat înainte de a începe clasa.

666
00:36:37,000 --> 00:36:40,000
Această listă legată de om a fost creat.

667
00:36:40,000 --> 00:36:44,000
Și acum, în acest moment, în povestea-toate acestea sunt întâmplă pe Facebook aparent mai târziu,

668
00:36:44,000 --> 00:36:49,000
în acest moment, în poveste, Anita a fost pregătit pentru a fi egală cu prima,

669
00:36:49,000 --> 00:36:51,000
ceea ce nu înseamnă că punctele de Anita la Lucas.

670
00:36:51,000 --> 00:36:53,000
Mai degrabă, ea arată la ceea ce el arată spre

671
00:36:53,000 --> 00:36:57,000
deoarece aceeași adresă care este în interiorul a lui Lucas 32 biti - 1, 2, 3 -

672
00:36:57,000 --> 00:37:01,000
este acum, de asemenea, în interiorul Anita 32 de biți - 1, 2, 3.

673
00:37:01,000 --> 00:37:05,000
>> Găsi acum 22. Cum ti-ar merge despre a face acest lucru?

674
00:37:05,000 --> 00:37:07,000
Ce e asta ideea? >> La orice.

675
00:37:07,000 --> 00:37:11,000
Indicați spre orice, merge atât de departe și de a acționa este mai bun ca tine poate aici.

676
00:37:11,000 --> 00:37:15,000
Bine, bine, iar acum te-arătând spre ceea ce este numele tau cu 22?

677
00:37:15,000 --> 00:37:18,000
Ramon. >> Ramon, astfel încât Ramon rezistă 22.

678
00:37:18,000 --> 00:37:20,000
Ați făcut acum un cec.

679
00:37:20,000 --> 00:37:24,000
Are Ramon == 22, și, dacă da, de exemplu, ne putem întoarce adevărat.

680
00:37:24,000 --> 00:37:26,000
Lasă-mă să-în timp ce băieții ăștia stau aici, oarecum penibil-

681
00:37:26,000 --> 00:37:32,000
lasa-ma sa fac ceva rapid ca bool găsi.

682
00:37:32,000 --> 00:37:37,000
Am de gând să merg mai departe și spun (nod * lista, int n).

683
00:37:37,000 --> 00:37:39,000
Voi reveni imediat cu voi. Trebuie doar să scrie un cod.

684
00:37:39,000 --> 00:37:45,000
Și acum am de gând să merg mai departe și de a face acest lucru, nod * Anita lista =.

685
00:37:45,000 --> 00:37:51,000
Și am de gând să merg mai departe și spun în timp ce (Anita = NULL!).

686
00:37:51,000 --> 00:37:57,000
>> Metafora aici este obtinerea un pic întins, dar în timp ce (Anita = NULL!), Ceea ce vreau să fac?

687
00:37:57,000 --> 00:38:03,000
Am nevoie de un fel de referire

688
00:38:03,000 --> 00:38:05,000
întreg care Anita este îndreptat la.

689
00:38:05,000 --> 00:38:08,000
În trecut, atunci când am avut structuri, care este un nod,

690
00:38:08,000 --> 00:38:11,000
am folosit notația punct, și ne-ar spune ceva de genul

691
00:38:11,000 --> 00:38:15,000
anita.n, dar problema este că Anita nu este o struct în sine.

692
00:38:15,000 --> 00:38:17,000
Ce este ea?

693
00:38:17,000 --> 00:38:21,000
E un pointer, deci într-adevăr, dacă dorim să folosim această notație dot-

694
00:38:21,000 --> 00:38:23,000
și acest lucru este de gând să arate în mod deliberat un pic criptic-

695
00:38:23,000 --> 00:38:28,000
trebuie să facem ceva de genul du-te la mâna stângă, indiferent Anita este îndreptat la

696
00:38:28,000 --> 00:38:31,000
și de a lua apoi câmp denumit nr.

697
00:38:31,000 --> 00:38:35,000
Anita este un pointer, dar ceea ce este * anita?

698
00:38:35,000 --> 00:38:38,000
Ce ți se pare atunci cand te duci la ce Anita este îndreptat la?

699
00:38:38,000 --> 00:38:42,000
Un struct, un nod, și un nod, rechemare, are un câmp denumit n

700
00:38:42,000 --> 00:38:47,000
pentru că le-a, amintesc, aceste 2 domenii, pentru următoarele și n,

701
00:38:47,000 --> 00:38:50,000
că am văzut acum un moment chiar aici.

702
00:38:50,000 --> 00:38:53,000
>> Pentru a imita de fapt, acest cod în,

703
00:38:53,000 --> 00:39:02,000
am putea face acest lucru și spun că dacă ((* Anita). n == n), n care caut.

704
00:39:02,000 --> 00:39:04,000
Observați că funcția a fost trecut în numărul îmi pasă.

705
00:39:04,000 --> 00:39:10,000
Atunci pot merge mai departe și de a face ceva de genul return true.

706
00:39:10,000 --> 00:39:12,000
Altfel, în cazul în care nu e cazul, ceea ce vreau să fac?

707
00:39:12,000 --> 00:39:19,000
Cum traduc pentru a coda ce Anita a făcut atât de intuitiv de mers pe jos prin lista?

708
00:39:19,000 --> 00:39:26,000
Ce ar trebui să fac aici, pentru a simula Anita a lua acest pas la stânga, ca pas spre stânga?

709
00:39:26,000 --> 00:39:28,000
[Răspuns studentul nu pot fi auzite] >> Ce e asta?

710
00:39:28,000 --> 00:39:30,000
[Răspuns studentul neauzit]

711
00:39:30,000 --> 00:39:34,000
Bine, nu este o idee rea, dar în trecut, atunci când am făcut asta, am făcut anita + +

712
00:39:34,000 --> 00:39:37,000
deoarece acest lucru ar adăuga numărul 1 la Anita,

713
00:39:37,000 --> 00:39:40,000
care ar indica de obicei, la următoarea persoană, cum ar fi Ramon,

714
00:39:40,000 --> 00:39:44,000
sau persoana de lângă el, sau lângă el persoanei în jos linie.

715
00:39:44,000 --> 00:39:49,000
Dar asta nu e destul de bun aici, pentru că ceea ce înseamnă acest lucru arata ca in memoria?

716
00:39:49,000 --> 00:39:54,000
Nu asta. Trebuie să dezactivați asta.

717
00:39:54,000 --> 00:40:00,000
Se pare ca acest lucru în memorie, și chiar dacă le-am atras 1 și 2 și 3 aproape unul de altul,

718
00:40:00,000 --> 00:40:03,000
dacă dorim cu adevărat simula această-can voi, în timp ce încă arătând spre aceleași persoane,

719
00:40:03,000 --> 00:40:07,000
poate unii dintre voi ia un pas înapoi aleatoare, unii dintre voi un pas înainte întâmplare?

720
00:40:07,000 --> 00:40:10,000
>> Această mizerie este încă o listă legat,

721
00:40:10,000 --> 00:40:13,000
dar tipii ăștia ar putea fi oriunde în memorie,

722
00:40:13,000 --> 00:40:15,000
astfel Anita + + nu este de gând să lucreze de ce?

723
00:40:15,000 --> 00:40:19,000
Ce e la locația Anita + +?

724
00:40:19,000 --> 00:40:21,000
Cine stie.

725
00:40:21,000 --> 00:40:24,000
E o alta valoare pe care doar așa se întâmplă să fi interpus

726
00:40:24,000 --> 00:40:28,000
Printre toate aceste noduri de șansă pentru că nu utilizați un tablou.

727
00:40:28,000 --> 00:40:30,000
Ne alocate în fiecare dintre aceste noduri individual.

728
00:40:30,000 --> 00:40:32,000
Bine, dacă voi puteți să vă curăța înapoi.

729
00:40:32,000 --> 00:40:37,000
Permiteți-mi să propun ca in loc de Anita + +, am loc facem anita se-

730
00:40:37,000 --> 00:40:42,000
Ei bine, de ce nu mergem la orice Anita este îndreptat la și de a face apoi. viitoare?

731
00:40:42,000 --> 00:40:45,000
Cu alte cuvinte, vom merge la Ramon, care a deține numărul 22,

732
00:40:45,000 --> 00:40:51,000
și apoi următor este. ca și cum ar fi copierea Anita indicatorul mâna stângă.

733
00:40:51,000 --> 00:40:54,000
Dar ea nu va merge mai departe decât Ramon pentru că am găsit 22.

734
00:40:54,000 --> 00:40:56,000
Dar asta ar fi ideea. Acum, acest lucru este un dezastru zeu-groaznic.

735
00:40:56,000 --> 00:40:59,000
Sincer, nimeni nu va aminti vreodată această sintaxă, și așa fericire,

736
00:40:59,000 --> 00:41:04,000
de fapt e un pic deliberată-oh, nu ai vedea de fapt ceea ce am scris.

737
00:41:04,000 --> 00:41:08,000
Acest lucru ar fi mai convingătoare dacă ai putea. Voila!

738
00:41:08,000 --> 00:41:10,000
>> În spatele scenei, am fost rezolvarea problemei în acest fel.

739
00:41:10,000 --> 00:41:14,000
Anita, sa faca acest pas la stânga,

740
00:41:14,000 --> 00:41:18,000
în primul rând, facem mergem la adresa pe care Anita este îndreptat la

741
00:41:18,000 --> 00:41:23,000
și în cazul în care ea va găsi nu numai n, pe care tocmai am verificat de dragul lui comparație,

742
00:41:23,000 --> 00:41:25,000
dar veți găsi, de asemenea, următoarea - în acest caz,

743
00:41:25,000 --> 00:41:28,000
Mâna stângă a lui Ramon, ce indică spre nodul următor din listă.

744
00:41:28,000 --> 00:41:32,000
Dar acest lucru este mizerie zeul-îngrozitor la care m-am referit mai devreme,

745
00:41:32,000 --> 00:41:34,000
dar se pare că C ne permite să simplifice acest lucru.

746
00:41:34,000 --> 00:41:40,000
În loc de scris (* anita), se poate scrie în schimb doar anita-> n,

747
00:41:40,000 --> 00:41:45,000
si este exact același lucru funcțional, dar e mult mai intuitiv,

748
00:41:45,000 --> 00:41:48,000
si e mult mai în concordanță cu imaginea pe care ne-am fost de desen

749
00:41:48,000 --> 00:41:50,000
în tot acest timp cu ajutorul săgeților.

750
00:41:50,000 --> 00:41:57,000
>> În cele din urmă, ceea ce avem nevoie pentru a face la sfârșitul acestui program?

751
00:41:57,000 --> 00:42:00,000
Există o linie de cod rămase.

752
00:42:00,000 --> 00:42:02,000
Reveniți ce?

753
00:42:02,000 --> 00:42:05,000
Fals, pentru că dacă vom trece prin întreaga buclă în timp ce

754
00:42:05,000 --> 00:42:10,000
Anita și este, de fapt, nulă, înseamnă că ea a mers tot drumul până la sfârșitul listei

755
00:42:10,000 --> 00:42:12,000
în cazul în care ea a fost îndreptat la-care e numele tău din nou?

756
00:42:12,000 --> 00:42:15,000
Ari Ari >>. Lui mâna stângă, care este nul.

757
00:42:15,000 --> 00:42:18,000
Anita este acum nul, si imi dau seama ca esti doar stai aici penibil în uitare

758
00:42:18,000 --> 00:42:21,000
pentru că am de gând off pe un monolog aici,

759
00:42:21,000 --> 00:42:23,000
dar vă vom implica din nou într-o clipă.

760
00:42:23,000 --> 00:42:27,000
Anita este nulă în acel moment, în poveste, astfel încât în ​​timp ce bucla se termină,

761
00:42:27,000 --> 00:42:30,000
și trebuie să ne întoarcem fals, deoarece în cazul în care ea a ajuns tot drumul spre pointer nul lui Ari

762
00:42:30,000 --> 00:42:34,000
atunci nu era nici un număr pe care ea a căutat în listă.

763
00:42:34,000 --> 00:42:39,000
Noi putem curăța acest prea, dar aceasta este o implementare destul de buna, apoi

764
00:42:39,000 --> 00:42:43,000
a unei funcții traversal, o găsi funcție pentru o listă legată.

765
00:42:43,000 --> 00:42:48,000
E încă căutare liniară, dar nu e la fel de simplu ca un indicator + +

766
00:42:48,000 --> 00:42:52,000
sau + + o variabila i că acum nu putem ghici

767
00:42:52,000 --> 00:42:54,000
în cazul în care fiecare dintre aceste noduri sunt în memorie.

768
00:42:54,000 --> 00:42:57,000
Noi trebuie să urmeze traseul literalmente de pesmet sau, mai precis,

769
00:42:57,000 --> 00:43:00,000
pointeri, pentru a obține de la un nod la altul.

770
00:43:00,000 --> 00:43:02,000
>> Acum, hai sa incercam alta. Anita, vrei să vii înapoi aici?

771
00:43:02,000 --> 00:43:06,000
De ce nu mergem mai departe și să aloce o altă persoană din public?

772
00:43:06,000 --> 00:43:08,000
Malloc-Care este numele tau? >> Rebecca.

773
00:43:08,000 --> 00:43:10,000
Rebecca. Rebecca a fost malloced de audiență,

774
00:43:10,000 --> 00:43:13,000
și ea este acum stocarea numărul 55.

775
00:43:13,000 --> 00:43:17,000
Și gol la îndemână acum este pentru Anita pentru a insera

776
00:43:17,000 --> 00:43:22,000
Rebecca în lista legat aici, în locul său adecvat.

777
00:43:22,000 --> 00:43:24,000
Vino aici pentru o clipă.

778
00:43:24,000 --> 00:43:28,000
Am făcut ceva de genul asta.

779
00:43:28,000 --> 00:43:32,000
Am facut nod *. Si ceea ce este numele tau din nou?

780
00:43:32,000 --> 00:43:34,000
Rebecca. >> Rebecca, bine.

781
00:43:34,000 --> 00:43:41,000
Rebecca devine malloc (sizeof (nod)).

782
00:43:41,000 --> 00:43:44,000
La fel cum am alocat lucruri, cum ar fi studenții și fleacuri în trecut,

783
00:43:44,000 --> 00:43:46,000
avem nevoie de dimensiunea nodului, asa ca acum Rebecca

784
00:43:46,000 --> 00:43:49,000
este îndreptat la ce?

785
00:43:49,000 --> 00:43:52,000
Rebecca are două câmpuri din interiorul ei, dintre care unul este de 55.

786
00:43:52,000 --> 00:43:55,000
Să facem ceea ce, Rebecca-> = 55.

787
00:43:55,000 --> 00:44:00,000
Dar apoi Rebecca-> următor ar trebui să fie-dori acum, mâna ei este un fel de cine știe?

788
00:44:00,000 --> 00:44:03,000
Se indică, la o valoare gunoi, așa că de ce nu pentru o bună măsură

789
00:44:03,000 --> 00:44:07,000
am cel puțin face acest lucru, astfel încât mâna stângă este acum la partea ei.

790
00:44:07,000 --> 00:44:09,000
Acum Anita, luați-o de aici.

791
00:44:09,000 --> 00:44:11,000
Ai Rebecca-au fost alocate.

792
00:44:11,000 --> 00:44:20,000
Du-te și pentru a găsi în cazul în care ar trebui să punem Rebecca.

793
00:44:20,000 --> 00:44:25,000
Bine, foarte bine.

794
00:44:25,000 --> 00:44:28,000
Bine, bine, și acum avem nevoie de tine pentru a oferi un pic de direcție,

795
00:44:28,000 --> 00:44:30,000
deci ai ajuns Ari.

796
00:44:30,000 --> 00:44:33,000
Mâna stângă este nul, dar Rebecca aparține în mod clar drept,

797
00:44:33,000 --> 00:44:36,000
asa cum avem de a modifica această listă legată

798
00:44:36,000 --> 00:44:38,000
în scopul de a introduce Rebecca în locul potrivit?

799
00:44:38,000 --> 00:44:42,000
Dacă ai putea muta literalmente mâinile oamenilor stânga în jurul valorii de cum este necesar,

800
00:44:42,000 --> 00:44:48,000
vom rezolva problema în acest fel.

801
00:44:48,000 --> 00:44:52,000
Bine, bine, și în același timp, mâna stângă a lui Rebecca este acum de partea ei.

802
00:44:52,000 --> 00:44:54,000
>> Asta a fost prea ușor.

803
00:44:54,000 --> 00:44:57,000
Să încercăm alocarea-Suntem aproape gata, 20.

804
00:44:57,000 --> 00:44:59,000
Bine, vino sus.

805
00:44:59,000 --> 00:45:04,000
20 a fost alocat, asa ca lasa-ma merge mai departe și spune din nou aici

806
00:45:04,000 --> 00:45:07,000
am facut doar * Saad nod.

807
00:45:07,000 --> 00:45:11,000
Avem malloc (sizeof (nod)).

808
00:45:11,000 --> 00:45:16,000
Noi facem atunci exact aceeasi sintaxa așa cum am făcut înainte de 20,

809
00:45:16,000 --> 00:45:20,000
și voi face în continuare NULL =, iar acum este de până la Anita

810
00:45:20,000 --> 00:45:23,000
pentru a insera vă în lista de legat, dacă ați putea juca acest rol exact același lucru.

811
00:45:23,000 --> 00:45:30,000
Executare.

812
00:45:30,000 --> 00:45:32,000
Bine, bine.

813
00:45:32,000 --> 00:45:38,000
Acum, gândește-te bine înainte de a începe să mișcați mâinile în jurul valorii de stânga.

814
00:45:38,000 --> 00:45:46,000
Ai de departe ai rolul cel mai ciudat astăzi.

815
00:45:46,000 --> 00:45:59,000
A cărui mână ar trebui să fie mutate mai întâi?

816
00:45:59,000 --> 00:46:02,000
Bine, stai, am auzit niște nr.

817
00:46:02,000 --> 00:46:07,000
În cazul în care unii oameni ar dori să ajute la rezolvarea politicos o situație penibilă aici.

818
00:46:07,000 --> 00:46:11,000
Mâna stângă a căror ar trebui să fie actualizate prima poate? Da.

819
00:46:11,000 --> 00:46:13,000
[Student] a lui Saad.

820
00:46:13,000 --> 00:46:15,000
Bine, a lui Saad, de ce, totuși?

821
00:46:15,000 --> 00:46:17,000
[Răspuns studentul neauzit]

822
00:46:17,000 --> 00:46:19,000
Bine, pentru că dacă am muta-care e numele tau? >> Marshall.

823
00:46:19,000 --> 00:46:22,000
Marshall, dacă vom muta mana primul până la nul,

824
00:46:22,000 --> 00:46:25,000
acum ne-am orfani literalmente patru oameni în această listă

825
00:46:25,000 --> 00:46:29,000
pentru că el a fost singurul lucru arătând spre Ramon și toată lumea la stânga,

826
00:46:29,000 --> 00:46:31,000
actualizarea astfel încât indicatorul primul a fost rău.

827
00:46:31,000 --> 00:46:33,000
Să anula asta.

828
00:46:33,000 --> 00:46:37,000
Bine, și acum mergeți mai departe și pentru a muta mâna stângă indică corespunzător la Ramon.

829
00:46:37,000 --> 00:46:39,000
Acest lucru se simte un pic redundant.

830
00:46:39,000 --> 00:46:41,000
Acum nu mai e la doi oameni îndreptate Ramon, dar asta e bine

831
00:46:41,000 --> 00:46:43,000
deoarece acum cum altfel ne actualiza lista?

832
00:46:43,000 --> 00:46:48,000
Ce altă parte, are să se mute?

833
00:46:48,000 --> 00:46:53,000
Excelent, au acum ne-am pierdut orice memorie?

834
00:46:53,000 --> 00:46:57,000
Nu, atât de bine, să vedem dacă nu putem rupe de această dată mai mult.

835
00:46:57,000 --> 00:47:00,000
>> Mallocing pentru ultima oară, numărul 5.

836
00:47:00,000 --> 00:47:04,000
Tot felul în spate, haide jos.

837
00:47:04,000 --> 00:47:08,000
E foarte interesant.

838
00:47:08,000 --> 00:47:15,000
[Aplauze]

839
00:47:15,000 --> 00:47:17,000
Care e numele tău? >> Ron.

840
00:47:17,000 --> 00:47:19,000
Ron, bine, ești malloced ca numărul 5.

841
00:47:19,000 --> 00:47:23,000
Am executat doar codul care este aproape identic cu acestea

842
00:47:23,000 --> 00:47:26,000
doar cu un nume diferit.

843
00:47:26,000 --> 00:47:28,000
Excelent.

844
00:47:28,000 --> 00:47:38,000
Acum, Anita, noroc introducerea numărul 5 în lista de acum.

845
00:47:38,000 --> 00:47:43,000
Bine, și?

846
00:47:43,000 --> 00:47:47,000
Excelent, astfel încât acesta este într-adevăr al treilea trei cazuri totale.

847
00:47:47,000 --> 00:47:49,000
Am avut cineva pentru prima oara la sfârșitul anului, Rebecca.

848
00:47:49,000 --> 00:47:51,000
Am avut atunci cineva în mijloc.

849
00:47:51,000 --> 00:47:53,000
Acum avem pe cineva de la început, și, în acest exemplu,

850
00:47:53,000 --> 00:47:56,000
am avut acum pentru a actualiza Lucas pentru prima dată

851
00:47:56,000 --> 00:48:00,000
deoarece primul element din listă are acum la punctul de la un nod nou,

852
00:48:00,000 --> 00:48:03,000
care, la rândul său, este îndreptat la numărul nodului 9.

853
00:48:03,000 --> 00:48:06,000
>> Aceasta a fost o demonstrație extrem de incomode, sunt sigur,

854
00:48:06,000 --> 00:48:08,000
asa o rundă de aplauze pentru acești tipi, dacă ai putea.

855
00:48:08,000 --> 00:48:11,000
Bine lucrat.

856
00:48:11,000 --> 00:48:17,000
Asta e tot. Puteți păstra piesele tale de hârtie ca o amintire putin.

857
00:48:17,000 --> 00:48:22,000
Se pare că a face acest lucru în cod

858
00:48:22,000 --> 00:48:26,000
nu este la fel de simplu ca mutarea doar mâinile în jurul valorii de

859
00:48:26,000 --> 00:48:28,000
și arătând indicii de la lucruri diferite.

860
00:48:28,000 --> 00:48:31,000
Dar dau seama că, atunci când vine vorba de timp pentru a pune în aplicare ceva de genul

861
00:48:31,000 --> 00:48:34,000
o listă legat sau o variantă a acesteia, dacă vă concentrați asupra adevarat

862
00:48:34,000 --> 00:48:38,000
aceste fundamente de bază, problemele musca-size le am să dau seama,

863
00:48:38,000 --> 00:48:43,000
este această mână sau mâna asta, dau seama că ceea ce este de altfel un program destul de complex

864
00:48:43,000 --> 00:48:47,000
poate, de fapt, să fie redusă la blocurile destul de simple, cum ar fi acest lucru.

865
00:48:47,000 --> 00:48:51,000
>> Să luăm lucrurile într-o direcție mult mai sofisticat încă.

866
00:48:51,000 --> 00:48:53,000
Avem acum noțiunea de listă legată.

867
00:48:53,000 --> 00:48:57,000
Avem, de asemenea, datorită-sugestia acolo-o listă de două ori legat,

868
00:48:57,000 --> 00:49:01,000
care arata aproape la fel, dar acum avem doi pointeri interiorul struct

869
00:49:01,000 --> 00:49:05,000
în loc de una, și am putea numi, probabil, aceste indicii precedent și următor

870
00:49:05,000 --> 00:49:08,000
sau la stânga sau la dreapta, dar noi nu, de fapt, nevoie de doi dintre ei.

871
00:49:08,000 --> 00:49:10,000
Codul ar fi un pic mai implicat.

872
00:49:10,000 --> 00:49:12,000
Anita ar fi trebuit să facă mai mult de lucru aici, pe scena.

873
00:49:12,000 --> 00:49:15,000
Dar am putea implementa cu siguranță, acest tip de structură.

874
00:49:15,000 --> 00:49:19,000
În ceea ce privește timpul de funcționare, însă, ceea ce ar fi timpul de funcționare

875
00:49:19,000 --> 00:49:24,000
Anita pentru a găsi un număr n într-o listă legată acum?

876
00:49:24,000 --> 00:49:27,000
Încă mare O din N, deci nu e mai bună decât căutarea liniară.

877
00:49:27,000 --> 00:49:29,000
Noi nu putem face binar de căutare, deși, din nou.

878
00:49:29,000 --> 00:49:34,000
De ce a fost cazul? Nu poți să sari în jurul valorii de.

879
00:49:34,000 --> 00:49:36,000
Chiar dacă am vedea în mod evident toti oamenii de pe scena,

880
00:49:36,000 --> 00:49:39,000
Anita și ar fi putut să-l eyeballed și a zis: "Iată mijlocul listei,"

881
00:49:39,000 --> 00:49:42,000
ea nu ar ști că, dacă ar fi fost program de calculator

882
00:49:42,000 --> 00:49:47,000
deoarece singurul lucru pe care a trebuit sa dispozitivul de blocare pe la începutul scenariului

883
00:49:47,000 --> 00:49:50,000
a fost Lucas, care a fost primul indicatorul.

884
00:49:50,000 --> 00:49:53,000
Ea ar trebui neapărat să urmeze aceste link-uri,

885
00:49:53,000 --> 00:49:56,000
numărare felul ei până când a găsit aproximativ mijloc,

886
00:49:56,000 --> 00:49:58,000
și chiar și atunci, ea nu va ști când ea a ajuns la mijloc

887
00:49:58,000 --> 00:50:01,000
cu excepția cazului în ea merge tot drumul până la sfârșit să ne dăm seama cât de multe sunt,

888
00:50:01,000 --> 00:50:05,000
apoi backtracks, și că prea ar fi greu dacă nu ai avut

889
00:50:05,000 --> 00:50:07,000
o listă de două ori legat de un anumit fel.

890
00:50:07,000 --> 00:50:10,000
>> Rezolvarea unor probleme de astăzi, dar introducerea altora.

891
00:50:10,000 --> 00:50:12,000
Ce zici de o structură de date cu totul alta?

892
00:50:12,000 --> 00:50:15,000
Aceasta este o fotografie a tăvilor în Mather House,

893
00:50:15,000 --> 00:50:19,000
și, în acest caz, avem o structură de date care le-am, de asemenea, un fel de deja vorbit despre.

894
00:50:19,000 --> 00:50:22,000
Am vorbit despre un teanc în contextul de memorie,

895
00:50:22,000 --> 00:50:26,000
și că e un fel de mod deliberat, deoarece numit un teanc în termeni de memorie

896
00:50:26,000 --> 00:50:31,000
este efectiv o structură de date care are mai multe lucruri și mai așezate pe partea de sus a acesteia.

897
00:50:31,000 --> 00:50:35,000
Dar lucrul interesant despre o stivă, așa cum este cazul în realitate,

898
00:50:35,000 --> 00:50:38,000
este faptul că este un tip special de structuri de date.

899
00:50:38,000 --> 00:50:42,000
Este o structura de date prin care primul element din

900
00:50:42,000 --> 00:50:46,000
este ultimul element afară.

901
00:50:46,000 --> 00:50:50,000
Dacă sunteți tava prima care urmează să fie pus pe stivă,

902
00:50:50,000 --> 00:50:53,000
ai de gând să fie, din păcate, tava ultimul care urmează să fie luate de pe stivă,

903
00:50:53,000 --> 00:50:55,000
Și asta nu e neaparat un lucru bun.

904
00:50:55,000 --> 00:50:58,000
În schimb, vă puteți gândi la asta invers,

905
00:50:58,000 --> 00:51:02,000
ultimul este primul ieșit.

906
00:51:02,000 --> 00:51:05,000
>> Acum, nu orice scenarii vin în minte în cazul în care având o stivă

907
00:51:05,000 --> 00:51:08,000
structură de date în cazul în care aveți că proprietatea

908
00:51:08,000 --> 00:51:13,000
din ultimul, în primul rând, este, de fapt convingătoare?

909
00:51:13,000 --> 00:51:16,000
Este un lucru bun? Este ca un lucru rău?

910
00:51:16,000 --> 00:51:19,000
E cu siguranta un lucru rău, în cazul în care tăvile nu au fost toate identice

911
00:51:19,000 --> 00:51:21,000
și ei au fost toate culorile speciale sau diferite fleacuri,

912
00:51:21,000 --> 00:51:24,000
și culoarea dorită este tot drumul de la partea de jos.

913
00:51:24,000 --> 00:51:26,000
Desigur, nu se poate obține că fără mare efort.

914
00:51:26,000 --> 00:51:28,000
Va trebui să înceapă de la partea de sus și de a lucra drum în jos.

915
00:51:28,000 --> 00:51:31,000
În mod similar, dacă ai fost unul dintre acesti baieti ventilator

916
00:51:31,000 --> 00:51:34,000
care așteaptă toată noaptea încercarea de a obține un iPhone și liniile de sus

917
00:51:34,000 --> 00:51:36,000
într-un loc ca ăsta?

918
00:51:36,000 --> 00:51:40,000
Nu ar fi frumos dacă Apple Store

919
00:51:40,000 --> 00:51:42,000
au fost o structură de date stiva?

920
00:51:42,000 --> 00:51:44,000
Yay? Nay?

921
00:51:44,000 --> 00:51:47,000
E numai bun pentru oamenii care apar la ultimul minut

922
00:51:47,000 --> 00:51:50,000
și de a lua apoi smuls coada.

923
00:51:50,000 --> 00:51:52,000
Și, de fapt, faptul că am fost atât de înclinați să spunem coadă

924
00:51:52,000 --> 00:51:56,000
este de fapt în concordanță cu ceea ce noi am numi acest tip de structură de date,

925
00:51:56,000 --> 00:51:59,000
una în realitate, în cazul în care ordinea este importantă,

926
00:51:59,000 --> 00:52:02,000
și doriți primul pentru a fi primul din

927
00:52:02,000 --> 00:52:04,000
dacă numai pentru motive de echitate umane.

928
00:52:04,000 --> 00:52:07,000
Vom numi, în general, că o structură de date coadă.

929
00:52:07,000 --> 00:52:11,000
>> Se pare că în afară de listele legate, putem începe să utilizați aceste idei de bază aceleași

930
00:52:11,000 --> 00:52:15,000
și să înceapă crearea de noi tipuri și diferite de soluții la probleme.

931
00:52:15,000 --> 00:52:19,000
De exemplu, în cazul unei stive, am putea reprezenta o stivă

932
00:52:19,000 --> 00:52:22,000
utilizând o structură de date de acest fel, mi-ar propune.

933
00:52:22,000 --> 00:52:26,000
În acest caz, am declarat o struct, și am spus interiorul acestei structuri

934
00:52:26,000 --> 00:52:30,000
este o serie de numere și apoi o dimensiune variabilă numită,

935
00:52:30,000 --> 00:52:33,000
și am de gând pentru a apela acest lucru o stivă.

936
00:52:33,000 --> 00:52:35,000
Acum, de ce înseamnă acest lucru de fapt?

937
00:52:35,000 --> 00:52:43,000
În cazul în care un stack, am putea trage acest mod eficient pe ecran ca o matrice.

938
00:52:43,000 --> 00:52:47,000
Aici este stack-ul meu. Acestea sunt numerele mele.

939
00:52:47,000 --> 00:52:50,000
Și le vom trage ca aceasta, acest, acest, acest, acest lucru.

940
00:52:50,000 --> 00:52:53,000
Și apoi am unele state alte date aici,

941
00:52:53,000 --> 00:52:58,000
care se numește dimensiune, astfel încât aceasta este dimensiunea, și acest lucru este numere,

942
00:52:58,000 --> 00:53:02,000
și colectiv, iPad întregul aici reprezinta o structura stiva.

943
00:53:02,000 --> 00:53:07,000
Acum, în mod implicit, dimensiunea a ajuns probabil să fie inițializat la 0,

944
00:53:07,000 --> 00:53:11,000
și ceea ce este în interiorul matrice de numere inițial

945
00:53:11,000 --> 00:53:14,000
atunci când am aloca o matrice primul?

946
00:53:14,000 --> 00:53:16,000
Gunoi. Cine știe? Și nu contează de fapt.

947
00:53:16,000 --> 00:53:20,000
Nu contează dacă acest lucru este de 1, 2, 3, 4, 5, complet aleator

948
00:53:20,000 --> 00:53:25,000
de ghinion stocate în structura mea, deoarece atâta timp cât știu că dimensiunea stivei

949
00:53:25,000 --> 00:53:29,000
este 0, atunci știu programatic, nu te uita la oricare din elementele din matrice.

950
00:53:29,000 --> 00:53:31,000
Nu contează ce e acolo.

951
00:53:31,000 --> 00:53:34,000
Nu te uita la ei, cum ar fi implicarea de o dimensiune de 0.

952
00:53:34,000 --> 00:53:38,000
>> Dar să presupunem acum merge mai departe și introduceți ceva în stivă.

953
00:53:38,000 --> 00:53:42,000
Vreau să inserați numărul 5, așa că am pus aici numărul 5,

954
00:53:42,000 --> 00:53:45,000
si apoi ce am pus aici?

955
00:53:45,000 --> 00:53:48,000
Acum aș pune de fapt în jos 1 pentru dimensiunea,

956
00:53:48,000 --> 00:53:50,000
iar acum stack este de marimea 1.

957
00:53:50,000 --> 00:53:53,000
Ce se întâmplă dacă am merge mai departe și introduceți numărul, să zicem, 7 următor?

958
00:53:53,000 --> 00:53:57,000
Acest lucru devine apoi actualizat la 2, iar apoi vom face 9,

959
00:53:57,000 --> 00:54:02,000
și apoi acest lucru devine actualizat la 3.

960
00:54:02,000 --> 00:54:05,000
Dar caracteristica interesanta a acestui stack acum este faptul că

961
00:54:05,000 --> 00:54:09,000
Eu ar trebui să elimine elementul pe care dacă vreau să pop

962
00:54:09,000 --> 00:54:12,000
ceva de pe stiva, ca să spunem așa?

963
00:54:12,000 --> 00:54:14,000
9 ar fi primul lucru pentru a merge.

964
00:54:14,000 --> 00:54:18,000
Cum ar trebui să schimbe imaginea, dacă vreau să pop un element de pe stivă,

965
00:54:18,000 --> 00:54:20,000
ca de mult o tavă în Mather?

966
00:54:20,000 --> 00:54:22,000
Da >> [elevului] Setați dimensiunea la 2..

967
00:54:22,000 --> 00:54:27,000
Exact, tot ce fac este setat dimensiunea la 2, și ce fac cu matrice?

968
00:54:27,000 --> 00:54:29,000
Eu nu trebuie să fac nimic.

969
00:54:29,000 --> 00:54:32,000
Aș putea, doar pentru a fi anal, a pus un 0 acolo sau un -1 sau ceva pentru a semnifica

970
00:54:32,000 --> 00:54:34,000
faptul că aceasta nu este o valoare legit, dar nu contează, deoarece

971
00:54:34,000 --> 00:54:37,000
Eu pot înregistra în afara matrice în sine cât de mult este

972
00:54:37,000 --> 00:54:41,000
astfel încât să știu uita doar la primele două elemente din această matrice.

973
00:54:41,000 --> 00:54:47,000
Acum, dacă mă duc și se adaugă numărul 8 de la acest tablou, cum se schimba imaginea următoare?

974
00:54:47,000 --> 00:54:50,000
Acest lucru devine 8, iar acest lucru devine 3.

975
00:54:50,000 --> 00:54:52,000
Sunt de tăiere a colțurilor câteva aici.

976
00:54:52,000 --> 00:54:56,000
Acum avem 5, 7, 8, și ne-am întors la o dimensiune de 3.

977
00:54:56,000 --> 00:54:58,000
Acest lucru este destul de simplu pentru a pune în aplicare,

978
00:54:58,000 --> 00:55:06,000
dar atunci când vom regreta această decizie de design?

979
00:55:06,000 --> 00:55:09,000
Când lucrurile încep să meargă foarte, foarte greșit? Da.

980
00:55:09,000 --> 00:55:11,000
[Răspuns studentul neauzit]

981
00:55:11,000 --> 00:55:13,000
Când vrei să te întorci și să obțină primul element-ai pus inch

982
00:55:13,000 --> 00:55:18,000
>> Se pare că aici, chiar dacă o stivă este o matrice sub capota,

983
00:55:18,000 --> 00:55:21,000
aceste structuri de date care le-am început să vorbim despre sunt, de asemenea, în general, cunoscut sub numele de

984
00:55:21,000 --> 00:55:25,000
structuri de date abstracte, prin modul în care sunt puse în aplicare

985
00:55:25,000 --> 00:55:27,000
este complet pe langa subiect.

986
00:55:27,000 --> 00:55:31,000
O structură de date ca o stivă se presupune a adăuga suport

987
00:55:31,000 --> 00:55:35,000
operațiuni, cum ar fi împingere, care împinge o tavă pe stivă,

988
00:55:35,000 --> 00:55:39,000
și pop, care elimină un element din stivă, și asta e tot.

989
00:55:39,000 --> 00:55:43,000
Dacă ar fi să descărcați codul altcuiva care deja puse în aplicare

990
00:55:43,000 --> 00:55:46,000
acest lucru numit-o stivă, acea persoană ar fi scris

991
00:55:46,000 --> 00:55:49,000
doar două funcții pentru tine, împinge și pop, al cărui unic scop în viață

992
00:55:49,000 --> 00:55:51,000
ar fi să facă exact acest lucru.

993
00:55:51,000 --> 00:55:54,000
Tu sau el sau ea care a implementat acest program

994
00:55:54,000 --> 00:55:58,000
ar fi fost în întregime o să decidă cum să pună în aplicare

995
00:55:58,000 --> 00:56:00,000
semantica de împingere și popping sub capota

996
00:56:00,000 --> 00:56:03,000
sau funcționalitatea de a impinge și popping.

997
00:56:03,000 --> 00:56:07,000
Și am luat o decizie oarecum miop aici

998
00:56:07,000 --> 00:56:10,000
prin punerea în aplicare a stack-ul meu cu această structură de date simplu de ce?

999
00:56:10,000 --> 00:56:12,000
Atunci când face acest lucru pauză structuri de date?

1000
00:56:12,000 --> 00:56:18,000
În ce moment trebuie să am pentru a reveni o eroare atunci când utilizatorul solicită împinge, de exemplu?

1001
00:56:18,000 --> 00:56:20,000
[Student] În cazul în care nu există mai mult spațiu.

1002
00:56:20,000 --> 00:56:23,000
Exact, dacă nu există spațiu nici mai mult, dacă l-am depășit capacitatea,

1003
00:56:23,000 --> 00:56:27,000
care este toate capacele, deoarece sugerează că e un fel de constantă la nivel mondial.

1004
00:56:27,000 --> 00:56:30,000
Ei bine, atunci eu sunt doar de gând să trebuie să spun, "Îmi pare rău, eu nu pot împinge o altă valoare

1005
00:56:30,000 --> 00:56:32,000
pe stivă, "ca de mult în Mather.

1006
00:56:32,000 --> 00:56:36,000
>> La un moment dat, au de gând să lovit partea de sus a cabinetului mic.

1007
00:56:36,000 --> 00:56:39,000
Nu e nici mai mult spațiu sau de capacitate, în stivă, moment în care exista un fel de eroare.

1008
00:56:39,000 --> 00:56:42,000
Ei trebuie să pună elementul în altă parte, tava de altă parte,

1009
00:56:42,000 --> 00:56:44,000
sau nicăieri deloc.

1010
00:56:44,000 --> 00:56:47,000
Acum, cu o coada, am putea implementa un pic diferit.

1011
00:56:47,000 --> 00:56:50,000
O coadă este un pic diferită în faptul că sub capota, acesta poate fi pus în aplicare

1012
00:56:50,000 --> 00:56:54,000
ca o matrice, dar de ce, în acest caz, eu propun

1013
00:56:54,000 --> 00:56:59,000
să aibă, de asemenea, un element de cap care reprezintă capul listei,

1014
00:56:59,000 --> 00:57:06,000
partea din față a listei, prima persoană la coadă la magazin Apple, în plus față de dimensiunea?

1015
00:57:06,000 --> 00:57:14,000
De ce am nevoie de o bucată suplimentară de date aici?

1016
00:57:14,000 --> 00:57:16,000
Gandeste-te la ceea ce numere este

1017
00:57:16,000 --> 00:57:18,000
dacă am desenat-l, după cum urmează.

1018
00:57:18,000 --> 00:57:21,000
Să presupunem că acest lucru este acum o coadă în loc de o stivă,

1019
00:57:21,000 --> 00:57:24,000
diferența fiind-ca Apple Store-coada este corect.

1020
00:57:24,000 --> 00:57:27,000
Prima persoană la coadă la începutul listei, numărul 5 în acest caz,

1021
00:57:27,000 --> 00:57:30,000
el sau ea este de gând să fie lăsați în primul magazin.

1022
00:57:30,000 --> 00:57:32,000
Să facem asta.

1023
00:57:32,000 --> 00:57:35,000
Să presupunem că aceasta este starea de coada mea în acest moment, iar acum magazinul Apple

1024
00:57:35,000 --> 00:57:39,000
se deschide și prima persoană, numărul 5, este condus în magazin.

1025
00:57:39,000 --> 00:57:43,000
Cum pot schimba imaginea de acum că am dezinstalate-coadă prima persoană

1026
00:57:43,000 --> 00:57:47,000
la partea din față a liniei?

1027
00:57:47,000 --> 00:57:50,000
Ce-i asta >> [Student]? Schimbați coada.

1028
00:57:50,000 --> 00:57:52,000
Modificarea cap, așa 5 dispare.

1029
00:57:52,000 --> 00:57:56,000
În realitate, e ca și cum cel mai bine-how-ul pentru a face acest lucru?

1030
00:57:56,000 --> 00:58:00,000
În realitate, e ca și cum tipul ăsta dispare.

1031
00:58:00,000 --> 00:58:03,000
Ce ar face numărul 7 intr-un magazin real?

1032
00:58:03,000 --> 00:58:05,000
Acestea ar avea un mare pas înainte.

1033
00:58:05,000 --> 00:58:08,000
>> Dar ceea ce am ajuns să apreciem atunci când vine vorba de matrice

1034
00:58:08,000 --> 00:58:10,000
și se deplasează în jurul valorii de lucruri?

1035
00:58:10,000 --> 00:58:12,000
Asta e un fel de pierdere de timp, nu?

1036
00:58:12,000 --> 00:58:16,000
De ce trebuie să fie atât de anal pentru a avea prima persoană

1037
00:58:16,000 --> 00:58:21,000
de la începutul liniei de la fizic începutul bucată de memorie?

1038
00:58:21,000 --> 00:58:23,000
Asta e complet inutil. De ce?

1039
00:58:23,000 --> 00:58:26,000
Ce-aș putea să amintesc doar locul >> [elevului răspunsul neauzit]?

1040
00:58:26,000 --> 00:58:30,000
Exact, am putea aminti doar cu acest cap de date suplimentare membru

1041
00:58:30,000 --> 00:58:34,000
că, în prezent cap de listă nu mai este 0, care a fost un moment în urmă.

1042
00:58:34,000 --> 00:58:39,000
Acum e de fapt numărul 1. În acest fel, am obține o optimizare ușoară.

1043
00:58:39,000 --> 00:58:44,000
Doar pentru că am dezinstalate-coadă pe cineva de la linie la începutul liniei de la magazinul Apple

1044
00:58:44,000 --> 00:58:47,000
nu înseamnă că toți trebuie să se schimbe, care amintesc este o operație liniară.

1045
00:58:47,000 --> 00:58:50,000
Eu pot petrece timpul în loc singura constantă

1046
00:58:50,000 --> 00:58:53,000
și pentru a atinge apoi un raspuns mult mai rapid.

1047
00:58:53,000 --> 00:58:56,000
Dar prețul Plătesc este ceea ce a obține că performanțele suplimentare

1048
00:58:56,000 --> 00:58:58,000
și să nu fi nevoie să schimbe toată lumea?

1049
00:58:58,000 --> 00:59:01,000
Da >> [elevului răspunsul neauzit].

1050
00:59:01,000 --> 00:59:04,000
Pot adăuga mai multe persoane, ei bine, această problemă este ortogonală

1051
00:59:04,000 --> 00:59:07,000
pentru faptul că nu vom schimba oamenii în jurul valorii de.

1052
00:59:07,000 --> 00:59:11,000
E încă un tablou, astfel încât indiferent dacă suntem sau nu trece toata lumea sau nu-

1053
00:59:11,000 --> 00:59:13,000
oh, am vedea ce vrei să spui, bine.

1054
00:59:13,000 --> 00:59:16,000
De fapt, eu sunt de acord cu ceea ce spui, în sensul că e aproape ca și cum

1055
00:59:16,000 --> 00:59:19,000
niciodată nu vom acum de gând să utilizeze începutul acestei matrice mai

1056
00:59:19,000 --> 00:59:22,000
pentru că dacă am scoate 5, apoi m-am scoate 7.

1057
00:59:22,000 --> 00:59:24,000
Dar am pus doar oameni la dreapta.

1058
00:59:24,000 --> 00:59:28,000
>> Se simte ca și cum aș pierde spațiu, și în cele din urmă mi se dezintegrează în coada de nimic, la toate,

1059
00:59:28,000 --> 00:59:31,000
asa ca am putea avea doar oameni curbat,

1060
00:59:31,000 --> 00:59:35,000
și am putea gândi la această matrice într-adevăr ca un fel de structură circulară,

1061
00:59:35,000 --> 00:59:38,000
dar vom folosi ceea ce operatorul în C pentru a face acest tip de curbat?

1062
00:59:38,000 --> 00:59:40,000
[Răspuns studentul nu pot fi auzite] >> Operatorul modulo.

1063
00:59:40,000 --> 00:59:43,000
Acesta ar fi un pic enervant de a gândi, prin modul în care faci curbat,

1064
00:59:43,000 --> 00:59:46,000
dar am putea face acest lucru, și am putea începe să punem oamenii la ceea ce folosit pentru a fi partea din față a liniei,

1065
00:59:46,000 --> 00:59:52,000
dar ne amintim doar cu această variabilă cap care șeful real al liniei este de fapt.

1066
00:59:52,000 --> 00:59:57,000
Ce se întâmplă dacă, în schimb, obiectivul nostru în cele din urmă, totuși,

1067
00:59:57,000 --> 01:00:00,000
a fost de a căuta numere, așa cum am făcut-o aici, pe scenă cu Anita,

1068
01:00:00,000 --> 01:00:02,000
dar ne dorim într-adevăr cel mai bun din toate aceste lumi?

1069
01:00:02,000 --> 01:00:05,000
Ne dorim mai mult de sofisticare matrice permite

1070
01:00:05,000 --> 01:00:09,000
pentru că vrem capacitatea de a dezvolta dinamic structura de date.

1071
01:00:09,000 --> 01:00:12,000
Dar noi nu vrem să aibă de a recurge la ceva ce am arătat

1072
01:00:12,000 --> 01:00:15,000
în primă lectură nu a fost un algoritm optim,

1073
01:00:15,000 --> 01:00:17,000
că de căutare liniară.

1074
01:00:17,000 --> 01:00:21,000
Se pare că se poate, de fapt, atingerea

1075
01:00:21,000 --> 01:00:24,000
sau cel puțin aproape de constanta de timp, prin care cineva ca Anita,

1076
01:00:24,000 --> 01:00:27,000
dacă ea configurează structura ei de date să nu fie o listă legat,

1077
01:00:27,000 --> 01:00:30,000
să nu fie o stivă, să nu fie o coadă, ar putea, de fapt,

1078
01:00:30,000 --> 01:00:33,000
veni cu o structură de date care îi permite să privească lucrurile,

1079
01:00:33,000 --> 01:00:37,000
chiar cuvinte, nu doar numere, în ceea ce vom numi timp constant.

1080
01:00:37,000 --> 01:00:40,000
>> Și, de fapt, privind în perspectivă, una dintre cele mai psets din această categorie este aproape întotdeauna

1081
01:00:40,000 --> 01:00:43,000
punerea în aplicare a unui spellchecker, prin care

1082
01:00:43,000 --> 01:00:46,000
noi vă oferim din nou câteva cuvinte în limba engleză și 150000 scopul este de a

1083
01:00:46,000 --> 01:00:51,000
încărca în memorie și cei rapid fie în măsură să răspundă la întrebări de forma

1084
01:00:51,000 --> 01:00:54,000
este acest cuvânt scris corect?

1085
01:00:54,000 --> 01:00:58,000
Și ar suge într-adevăr, dacă ați avut pentru a itera prin toate cuvintele 150000 a răspunde la această.

1086
01:00:58,000 --> 01:01:02,000
Dar, de fapt, vom vedea că o putem face in timp foarte, foarte rapid.

1087
01:01:02,000 --> 01:01:06,000
Și se va implica ceva punerea în aplicare a numit un tabel hash,

1088
01:01:06,000 --> 01:01:09,000
și chiar dacă la prima vedere acest lucru numit un tabel hash este de gând să

1089
01:01:09,000 --> 01:01:12,000
sa ne putem atinge aceste momente super-rapide de răspuns,

1090
01:01:12,000 --> 01:01:18,000
se dovedește că există, de fapt, o problemă.

1091
01:01:18,000 --> 01:01:23,000
Când vine vorba de timp pentru a pune în aplicare acest lucru numit din nou, eu o fac din nou.

1092
01:01:23,000 --> 01:01:25,000
Eu sunt singurul de aici.

1093
01:01:25,000 --> 01:01:28,000
Când vine vorba de timp pentru punerea în aplicare acest lucru numit un tabel hash,

1094
01:01:28,000 --> 01:01:30,000
vom avea de a face o decizie.

1095
01:01:30,000 --> 01:01:32,000
Cât de mare ar trebui să fie de fapt acest lucru?

1096
01:01:32,000 --> 01:01:36,000
Și când vom începe să numere inserarea în acest tabel hash,

1097
01:01:36,000 --> 01:01:38,000
cum am de gând să le stocați într-un mod

1098
01:01:38,000 --> 01:01:42,000
pe care le putem lua înapoi cât mai repede le-am în?

1099
01:01:42,000 --> 01:01:45,000
Dar vom vedea în scurt timp că această chestiune a

1100
01:01:45,000 --> 01:01:48,000
atunci când toată lumea ziua de nastere a lui este în clasa va fi destul de Germane.

1101
01:01:48,000 --> 01:01:51,000
Se pare că, în această cameră, am luat câteva sute de persoane,

1102
01:01:51,000 --> 01:01:56,000
astfel sansele ca doi dintre noi au aceeași zi de naștere este, probabil, destul de mare.

1103
01:01:56,000 --> 01:01:58,000
Ce se întâmplă dacă au existat doar 40 de noi în această cameră?

1104
01:01:58,000 --> 01:02:02,000
Care sunt sansele de a două persoane care au aceeași zi de naștere?

1105
01:02:02,000 --> 01:02:04,000
[Elevii] Peste 50%.

1106
01:02:04,000 --> 01:02:06,000
Da, peste 50%. De fapt, chiar am adus-o diagramă.

1107
01:02:06,000 --> 01:02:08,000
Se pare-și acest lucru este de fapt doar un sneak-preview

1108
01:02:08,000 --> 01:02:12,000
în cazul în care există numai 58 de noi în această cameră, probabilitatea de 2 dintre noi

1109
01:02:12,000 --> 01:02:16,000
având în aceeași zi de naștere este extrem de mare, de aproape 100%,

1110
01:02:16,000 --> 01:02:20,000
și că va provoca o grămadă de răni pentru noi, miercuri.

1111
01:02:20,000 --> 01:02:24,000
>> Cu care a spus, hai să amână aici. Ne vedem miercuri.

1112
01:02:24,000 --> 01:02:28,000
[Aplauze]

1113
01:02:28,000 --> 01:02:30,000
[CS50.TV]