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

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

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

4
00:00:08,720 --> 00:00:12,970
Acest lucru este CS50 și acesta este sfârșitul săptămânii 6.

5
00:00:12,970 --> 00:00:17,970
Deci CS50x, unul dintre primele cursuri la Harvard implicate în inițiativa EDX

6
00:00:17,970 --> 00:00:20,590
într-adevăr, a debutat acest trecut luni.

7
00:00:20,590 --> 00:00:23,460
Dacă doriți să obțineți o bucatica din ceea ce alții pe Internet

8
00:00:23,460 --> 00:00:27,180
sunt acum în urma, împreună cu, vă puteți îndrepta spre x.cs50.net.

9
00:00:27,180 --> 00:00:30,350
Asta vă va redirecționa la locul potrivit pe edx.org,

10
00:00:30,350 --> 00:00:34,160
care a fost în cazul în care acest lucru și alte cursuri de la MIT si Berkeley acum live.

11
00:00:34,160 --> 00:00:38,140
Va trebui să vă înscrieți pentru un cont, veți găsi că materialul este în mare parte același

12
00:00:38,140 --> 00:00:42,170
ca ai avut acest semestru, deși cu câteva săptămâni întârziate, după cum am obține totul gata.

13
00:00:42,170 --> 00:00:46,930
Dar ceea ce elevii din CS50x vor vedea acum este o interfata destul ca aceasta.

14
00:00:46,930 --> 00:00:50,040
Acest lucru, de exemplu, este lider Zamyla walkthrough pentru set de probleme 0.

15
00:00:50,040 --> 00:00:54,230
La conectarea la edx.org, un student CS50x vede felul de lucruri

16
00:00:54,230 --> 00:00:57,170
v-ați aștepta să vedeți într-un curs: curs de luni,

17
00:00:57,170 --> 00:01:01,650
prelegere pentru miercuri, pantaloni scurți diverse, de seturi de probleme, walkthroughs, PDF-uri.

18
00:01:01,650 --> 00:01:04,459
În plus, după cum puteți vedea aici, masina de traduceri

19
00:01:04,459 --> 00:01:08,390
de transcrieri engleză în chineză, japoneză, spaniolă, italiană,

20
00:01:08,390 --> 00:01:12,810
și o grămadă de alte limbi, care va fi cu siguranță imperfectă

21
00:01:12,810 --> 00:01:15,840
așa cum le implementeze în mod programatic folosind ceva numit un API,

22
00:01:15,840 --> 00:01:18,360
sau interfață de programare aplicație, de la Google

23
00:01:18,360 --> 00:01:21,360
care ne permite să convertească din engleză în alte limbi.

24
00:01:21,360 --> 00:01:24,100
Dar, datorită minunatul spirit al unor voluntari sute de plus,

25
00:01:24,100 --> 00:01:26,940
oamenii aleatorii de pe Internet, care au oferit cu amabilitate să se implice

26
00:01:26,940 --> 00:01:30,180
în acest proiect, vom fi îmbunătățirea treptată a calității acestor traduceri

27
00:01:30,180 --> 00:01:35,790
de oameni care au corecteze greșelile pe care calculatoarele noastre au făcut.

28
00:01:35,790 --> 00:01:42,330
>> Deci, se dovedește ne-am câțiva elevi mai arată pe luni decât ne-am așteptat inițial.

29
00:01:42,330 --> 00:01:48,980
De fapt, acum CS50x are 100.000 de oameni în urma de-a lungul la domiciliu.

30
00:01:48,980 --> 00:01:54,430
Deci, dai seama ca sunt toate parte din această clasă de inaugurare a face acest curs în informatică

31
00:01:54,430 --> 00:01:57,370
educație, în general, mai mult, în sens mai larg, accesibil.

32
00:01:57,370 --> 00:02:00,130
Și realitatea este acum, cu unele dintre aceste cursuri on-line masive,

33
00:02:00,130 --> 00:02:04,070
ei încep toate cu aceste numere foarte mari, așa cum se pare că am făcut aici.

34
00:02:04,070 --> 00:02:08,759
Dar obiectiv, în cele din urmă, pentru CS50x este adevărat pentru a obține cât mai multe persoane pentru a linia de sosire cat posibil.

35
00:02:08,759 --> 00:02:12,000
Prin design, CS50x va fi oferit de acest trecut luni

36
00:02:12,000 --> 00:02:17,430
tot drumul prin 15 aprilie 2013, astfel încât oamenii care au angajamente de școală în altă parte,

37
00:02:17,430 --> 00:02:20,990
locul de muncă, familia, alte conflicte și cum ar fi, au o flexibilitate un pic mai mult

38
00:02:20,990 --> 00:02:23,640
cu care să se scufunde în acest curs, care, este suficient să spunem,

39
00:02:23,640 --> 00:02:30,540
este destul de ambițios face numai în cazul în care pe parcursul a doar trei luni în timpul unui semestru obișnuită.

40
00:02:30,540 --> 00:02:34,190
Dar acești studenți vor fi abordarea aceleași seturi problema, vizualizarea același conținut,

41
00:02:34,190 --> 00:02:36,350
au acces la pantaloni scurți și aceleași similare.

42
00:02:36,350 --> 00:02:38,990
Deci dau seama că suntem cu toții într-adevăr în asta împreună.

43
00:02:38,990 --> 00:02:42,360
Și unul dintre obiectivele finale ale CS50x nu este doar de a obține cât mai multe oameni

44
00:02:42,360 --> 00:02:45,720
la linia de sosire și să le dea această înțelegere dobandita de informatică

45
00:02:45,720 --> 00:02:49,000
si programare, dar, de asemenea, să le aibă această experiență împărtășită.

46
00:02:49,000 --> 00:02:52,010
Una dintre caracteristicile definitorii ale 50 din campus, sperăm,

47
00:02:52,010 --> 00:02:56,260
a fost acest tip de experiență comunale, pentru o mai bună sau mai rău pentru, uneori,

48
00:02:56,260 --> 00:02:59,480
dar având în acești oameni să apeleze la stânga la dreapta și de la,

49
00:02:59,480 --> 00:03:01,830
și ore de birou și Hackathon și echitabil.

50
00:03:01,830 --> 00:03:04,560
E un pic mai greu pentru a face acest lucru în persoană cu oameni on-line,

51
00:03:04,560 --> 00:03:10,580
dar CS50x va încheia în aprilie cu prima CS50 Expo,

52
00:03:10,580 --> 00:03:13,630
care va fi o adaptare on-line de ideea noastră de târg

53
00:03:13,630 --> 00:03:18,250
în cazul în care aceste mii de studenți vor fi invitați să prezinte o 1 - la 2 minute de video,

54
00:03:18,250 --> 00:03:22,480
fie un screencast a proiectului lor final sau videoclip le ondularea salut

55
00:03:22,480 --> 00:03:24,490
și vorbesc despre proiectul lor si demoing-l,

56
00:03:24,490 --> 00:03:27,610
la fel ca predecesorii tăi au făcut aici, în campus în târg,

57
00:03:27,610 --> 00:03:31,400
astfel încât, până la sfârșitul semestrului lui, speranța este de a avea o expoziție la nivel mondial

58
00:03:31,400 --> 00:03:37,080
de proiecte ale studenților CS50x "finale, la fel ca ceea ce vă așteaptă în luna decembrie a acestui aici, în campus.

59
00:03:37,080 --> 00:03:39,680
Deci, mai mult pe faptul că, în lunile ce vor urma.

60
00:03:39,680 --> 00:03:43,640
>> Cu 100.000 de studenți, însă, vine o nevoie pentru un AC câteva mai multe.

61
00:03:43,640 --> 00:03:47,590
Având în vedere faptul că voi fac pârtie aici și luând CS50

62
00:03:47,590 --> 00:03:51,630
câteva săptămâni înainte de lansarea acestui material de la oameni pe EDX,

63
00:03:51,630 --> 00:03:55,330
realiza ne-ar plăcea să implice cât mai mulți dintre studenții noștri proprii, astfel cum este posibil în această inițiativă,

64
00:03:55,330 --> 00:03:58,720
atât în ​​timpul semestrului, precum și în această iarnă și acest venirea primăverii.

65
00:03:58,720 --> 00:04:01,620
Deci, dacă doriți să se implice în CS50x,

66
00:04:01,620 --> 00:04:07,450
în special aderarea la CS50x pe Discuss, versiunea EDX a CS50 Discuss,

67
00:04:07,450 --> 00:04:10,140
pe care mulți dintre voi ați fost utilizați în campus, avizier on-line,

68
00:04:10,140 --> 00:04:13,040
vă rugăm să faceți cap la acea adresă URL, să ne spui cine ești,

69
00:04:13,040 --> 00:04:16,450
pentru că ne-ar plăcea să construiască o echipă de studenți și a personalului și de facultate, cât

70
00:04:16,450 --> 00:04:19,630
în campus, care sunt pur și simplu joc de-a lungul și ajutând.

71
00:04:19,630 --> 00:04:21,720
Și când văd o întrebare la care e familiar pentru ei,

72
00:04:21,720 --> 00:04:25,320
auzi un student de raportare unele bug undeva acolo într-o țară pe internet,

73
00:04:25,320 --> 00:04:27,450
și că sună un clopot, deoarece ai avut de asemenea, că aceeași problemă

74
00:04:27,450 --> 00:04:32,620
în sala de dvs. d-ceva timp în urmă, sperăm, le puteti interveni în și împărtăși propria experiență.

75
00:04:32,620 --> 00:04:37,300
Deci, vă rugăm să ia parte, dacă doriți.

76
00:04:37,300 --> 00:04:39,360
>> Cursuri de informatică de la Harvard au un pic de o tradiție,

77
00:04:39,360 --> 00:04:44,730
CS50 printre ei, de a avea unele îmbrăcăminte, niște haine, pe care le puteți purta cu mândrie

78
00:04:44,730 --> 00:04:49,090
la sfârșitul semestrului, spunând destul de mândrie că ai terminat CS50

79
00:04:49,090 --> 00:04:51,830
și a luat CS50 și cum ar fi, și vom încerca mereu să implice elevii

80
00:04:51,830 --> 00:04:54,540
în acest proces cât mai mult posibil, prin care vă invităm,

81
00:04:54,540 --> 00:04:56,900
în jurul valorii de acest timp de semestru, studenții să-și prezinte proiectele

82
00:04:56,900 --> 00:04:59,330
folosind Photoshop, sau orice instrument de alegerea pe care doriți să o utilizați

83
00:04:59,330 --> 00:05:02,330
dacă ești un designer, să prezinte modele de T-shirt și jachete

84
00:05:02,330 --> 00:05:06,100
și umbrele și bandane mici pentru câini avem acum și place.

85
00:05:06,100 --> 00:05:09,370
Și totul este apoi - castigatorii in fiecare an sunt apoi expuse

86
00:05:09,370 --> 00:05:12,700
pe site-ul cursului de la store.cs50.net.

87
00:05:12,700 --> 00:05:15,790
Totul este vândut la cost acolo, dar site-ul în sine funcționează doar

88
00:05:15,790 --> 00:05:18,330
și permite oamenilor de a alege culori si modele pe care le plac.

89
00:05:18,330 --> 00:05:20,420
Așa că m-am gândit parts doar câteva dintre desenele de anul trecut

90
00:05:20,420 --> 00:05:25,130
care au fost pe site-ul pe langa asta aici, care este o tradiție anuală.

91
00:05:25,130 --> 00:05:29,410
"În fiecare zi mă SEG Faultn" a fost unul dintre cele prezentate anul trecut,

92
00:05:29,410 --> 00:05:32,290
care este încă disponibilă acolo pentru absolventi.

93
00:05:32,290 --> 00:05:35,820
Am avut aceasta ", CS50, Infiintata 1989."

94
00:05:35,820 --> 00:05:39,010
Unul dintre Bowdens noastre, Rob, a fost foarte popular de anul trecut.

95
00:05:39,010 --> 00:05:43,480
"Echipa Bowden" sa născut, acest design a fost prezentată, printre vanzatori de top.

96
00:05:43,480 --> 00:05:49,040
Așa cum a fost cel de aici. Mulți oameni au avut "Febra Bowden", în conformitate cu jurnalele de vânzări.

97
00:05:49,040 --> 00:05:52,650
Seama că ar putea fi acum design-ul acolo, pe internet.

98
00:05:52,650 --> 00:05:57,510
Mai multe detalii despre aceasta in urmatoarea problema seturi să vină.

99
00:05:57,510 --> 00:06:00,330
>> Un instrument mai: ai avut ceva de expunere și, sperăm, acum

100
00:06:00,330 --> 00:06:02,350
ceva experienta hands-on cu GDB,

101
00:06:02,350 --> 00:06:04,570
care este, desigur, un depanator și vă permite să manipuleze

102
00:06:04,570 --> 00:06:09,500
programul tau la un nivel destul de scăzut, faci ce fel de lucruri?

103
00:06:09,500 --> 00:06:13,030
Ce înseamnă GDB lasa sa faci?

104
00:06:13,030 --> 00:06:15,030
Da? Dă-mi ceva. [Răspuns Student, neinteligibil]

105
00:06:15,030 --> 00:06:18,120
Bine. Pas în funcție, astfel încât nu trebuie doar să tastați rula

106
00:06:18,120 --> 00:06:22,310
și au lovitură programul prin toate elementele sale, imprimarea lucruri la ieșirea standard.

107
00:06:22,310 --> 00:06:25,190
Mai degrabă, aveți posibilitatea să pas prin ea linie cu linie, fie tastând următoarea

108
00:06:25,190 --> 00:06:30,300
pentru a merge linie cu linie cu linie sau pas să se scufunde într-o funcție, de obicei, una care ai scris.

109
00:06:30,300 --> 00:06:35,240
Ce altceva GDB lasa sa faci? Da? [Răspuns Student, neinteligibil]

110
00:06:35,240 --> 00:06:38,100
Imprima variabile. Deci, dacă vrei să faci un pic de introspecție în interiorul programului

111
00:06:38,100 --> 00:06:41,500
fără a fi nevoie să recurgă la scrierea declarațiile printf peste tot locul,

112
00:06:41,500 --> 00:06:44,600
puteți imprima doar o variabilă sau să afișeze o variabilă.

113
00:06:44,600 --> 00:06:46,710
Ce altceva se poate face cu un program de depanare ca GDB?

114
00:06:46,710 --> 00:06:49,170
[Răspuns Student, neinteligibil]

115
00:06:49,170 --> 00:06:52,080
Exact. Puteți seta puncte de întrerupere, se poate spune executarea pauză

116
00:06:52,080 --> 00:06:54,020
la funcția de principal sau funcția foo.

117
00:06:54,020 --> 00:06:56,800
Se poate spune executarea pauza la linia 123.

118
00:06:56,800 --> 00:06:58,950
Valorile critice și reprezintă o tehnică foarte puternic

119
00:06:58,950 --> 00:07:01,110
pentru că, dacă aveți un sentiment general de unde problema ta

120
00:07:01,110 --> 00:07:05,360
probabil este, nu trebuie să pierdeți timp pas cu pas prin toate elementele programului.

121
00:07:05,360 --> 00:07:08,250
Puteți sări în esență, chiar acolo și apoi începeți să tastați -

122
00:07:08,250 --> 00:07:10,970
intensificarea prin ea cu pas sau următoare sau similar.

123
00:07:10,970 --> 00:07:14,340
Dar captura cu așa ceva GDB este că vă ajută, umană,

124
00:07:14,340 --> 00:07:16,940
găsi problemele tale și pentru a găsi bug-uri dumneavoastră.

125
00:07:16,940 --> 00:07:19,470
Aceasta nu găsiți neapărat le atât de mult pentru tine.

126
00:07:19,470 --> 00:07:23,070
>> Deci, am introdus style50 altă zi, care este un instrument de linie de comandă scurt

127
00:07:23,070 --> 00:07:27,500
care încearcă să stiliza codul tau un pic mai curat decât tine, om, ar putea avea de făcut.

128
00:07:27,500 --> 00:07:29,530
Dar că, de asemenea, este de fapt doar un lucru estetic.

129
00:07:29,530 --> 00:07:34,110
Dar se pare că nu e alt instrument numit Valgrind, care este un pic mai mult pentru a utiliza arcane.

130
00:07:34,110 --> 00:07:36,860
Producția sa este cumplit de criptic la prima vedere.

131
00:07:36,860 --> 00:07:39,420
Dar e minunat util, mai ales acum ca suntem la o parte din termenul de

132
00:07:39,420 --> 00:07:43,080
în cazul în care începi să utilizați malloc și alocarea dinamică a memoriei.

133
00:07:43,080 --> 00:07:45,420
Lucrurile pot merge foarte, foarte greșit repede.

134
00:07:45,420 --> 00:07:49,320
Pentru că dacă vă uitați pentru a elibera memoria, sau ai ceva dereference indicatorul NULL,

135
00:07:49,320 --> 00:07:55,770
sau ai ceva dereference indicatorul de gunoi, ceea ce este de obicei simptomul că rezultatele?

136
00:07:55,770 --> 00:07:59,470
Seg vina. Și veți obține acest fișier de bază de un numar de kiloocteți sau megaocteți

137
00:07:59,470 --> 00:08:02,990
care reprezintă starea memoriei program dumneavoastră atunci când sa prăbușit,

138
00:08:02,990 --> 00:08:05,730
dar în cele din urmă programul SEG defecte, eroare de segmentare,

139
00:08:05,730 --> 00:08:08,450
ceea ce înseamnă ceva rău sa întâmplat aproape întotdeauna legate de

140
00:08:08,450 --> 00:08:11,750
pentru o greșeală de memorie legate de faptul că ai făcut undeva.

141
00:08:11,750 --> 00:08:14,100
Deci, Valgrind vă ajută să găsiți lucruri de genul asta.

142
00:08:14,100 --> 00:08:17,720
Este un instrument pe care îl executați, cum ar fi PIB, după ce ați compilat programul tău,

143
00:08:17,720 --> 00:08:20,330
ci, mai degrabă decât a rula programul direct, aveți o Valgrind

144
00:08:20,330 --> 00:08:23,960
și tu treci să-l program, la fel cum ai face cu GDB.

145
00:08:23,960 --> 00:08:26,220
Acum, de utilizare, pentru a obține cel mai bun fel de iesire,

146
00:08:26,220 --> 00:08:30,410
este un pic cam lung, astfel încât chiar acolo deasupra ecranului de care vă veți vedea Valgrind-v.

147
00:08:30,410 --> 00:08:35,350
"-V" aproape universal înseamnă detaliat când sunteți folosind programele de pe un computer Linux.

148
00:08:35,350 --> 00:08:38,770
Deci, aceasta înseamnă scuipa mai multe date decât s-ar putea în mod implicit.

149
00:08:38,770 --> 00:08:45,510
"- Scurgere-check = plin." Acest lucru este pur și simplu spune de selectare pentru toate posibile scurgeri de memorie,

150
00:08:45,510 --> 00:08:49,430
greșelile pe care am putea-au făcut. Acest lucru, de asemenea, este o paradigmă comună cu programe Linux.

151
00:08:49,430 --> 00:08:52,710
În general, în cazul în care aveți un argument linie de comandă care este un "comutator",

152
00:08:52,710 --> 00:08:55,830
care ar trebui sa schimbe comportamentul programului, și este o singură literă,

153
00:08:55,830 --> 00:09:00,310
e-V, dar în cazul în care este pornit, doar prin designul programator,

154
00:09:00,310 --> 00:09:05,150
este un cuvânt plin sau o serie de cuvinte, argumentul linia de comanda începe cu -.

155
00:09:05,150 --> 00:09:08,190
Acestea sunt doar convenții omenești, dar le vei vedea din ce în ce.

156
00:09:08,190 --> 00:09:12,410
Și apoi, în cele din urmă, "a.out" este nume arbitrar pentru program în acest exemplu particular.

157
00:09:12,410 --> 00:09:14,640
Și aici e ceva de ieșire reprezentative.

158
00:09:14,640 --> 00:09:22,890
>> Înainte de a ne uităm la ceea ce ar putea însemna că, lasă-mă să merg pe la un fragment de cod aici.

159
00:09:22,890 --> 00:09:26,390
Și lasă-mă să mute asta din drum, în curând,

160
00:09:26,390 --> 00:09:32,120
și haideți să aruncăm o privire la memory.c, care este acest exemplu scurt aici.

161
00:09:32,120 --> 00:09:36,290
Deci, în acest program, permiteți-mi să mări cu privire la funcțiile și întrebări.

162
00:09:36,290 --> 00:09:39,430
Avem o funcție principală, care apelează o funcție, f,

163
00:09:39,430 --> 00:09:45,590
și apoi ce face f procedează pentru a face, în limba engleză ușor tehnic?

164
00:09:45,590 --> 00:09:49,760
Ce face f proceda să fac?

165
00:09:49,760 --> 00:09:53,680
Cum despre Voi începe cu linia 20, și locul stelei nu contează,

166
00:09:53,680 --> 00:09:56,720
dar voi fi doar în concordanță aici cu ultima prelegere.

167
00:09:56,720 --> 00:09:59,910
Ce e linia 20 nu pentru noi? Pe partea stângă. Ne vom rupe în jos în continuare.

168
00:09:59,910 --> 00:10:02,410
Int * x: Ce face asta?

169
00:10:02,410 --> 00:10:04,940
Bine. Este declarare un pointer, iar acum sa fie chiar mai tehnic.

170
00:10:04,940 --> 00:10:10,230
Ce înseamnă, foarte concret, să declare un pointer? Altcineva?

171
00:10:10,230 --> 00:10:15,050
Da? [Răspuns Student, neinteligibil] Prea departe.

172
00:10:15,050 --> 00:10:17,060
Deci, sunteți de lectură pe partea dreaptă a semnului egal.

173
00:10:17,060 --> 00:10:20,290
Să ne concentrăm doar pe partea stângă, doar pe int * x.

174
00:10:20,290 --> 00:10:24,700
Aceasta se "declară" un pointer, dar acum hai să se arunca cu capul în mai profundă a acestei definiții.

175
00:10:24,700 --> 00:10:28,330
Ce înseamnă asta concret, punct de vedere tehnic înseamnă? Da?

176
00:10:28,330 --> 00:10:31,940
[Răspuns Student, neinteligibil]

177
00:10:31,940 --> 00:10:35,090
Bine. Acesta se pregătește pentru a salva o adresă în memorie.

178
00:10:35,090 --> 00:10:40,680
Bine. Și să ia acest pas mai departe, se declara o variabila, x, asta e 32 de biți.

179
00:10:40,680 --> 00:10:44,440
Și știu că e pe 32 de biți, deoarece -?

180
00:10:44,440 --> 00:10:47,390
Nu e pentru ca este un int, pentru că este un pointer în acest caz.

181
00:10:47,390 --> 00:10:49,650
Coincidență faptul că este una și aceeași cu o int,

182
00:10:49,650 --> 00:10:51,970
dar faptul că e steaua nu înseamnă acest lucru este un pointer

183
00:10:51,970 --> 00:10:57,300
și în aparat, ca și în multe calculatoare, dar nu toate, pointerii sunt 32 de biți.

184
00:10:57,300 --> 00:11:01,850
Pe hardware-ul modern, mai mult ca cele mai recente Mac-uri, cele mai recente PC-uri, este posibil să aveți 64-bit pointeri,

185
00:11:01,850 --> 00:11:04,160
dar în aparat, aceste lucruri sunt 32 de biți.

186
00:11:04,160 --> 00:11:08,380
Deci, vom standardiza pe asta. Mai concret, povestea merge, după cum urmează:

187
00:11:08,380 --> 00:11:10,820
Noi "declară" un pointer; ce înseamnă asta?

188
00:11:10,820 --> 00:11:12,810
Ne pregătim pentru a stoca o adresă de memorie.

189
00:11:12,810 --> 00:11:15,530
Ce înseamnă asta?

190
00:11:15,530 --> 00:11:19,810
Vom crea un variabila x zisul care preia 32 de biți

191
00:11:19,810 --> 00:11:23,810
care va stoca în curând adresa un număr întreg.

192
00:11:23,810 --> 00:11:26,470
Și asta e, probabil, la fel de precisă ca putem obtine.

193
00:11:26,470 --> 00:11:31,810
E bine avansează pentru a simplifica lume și spun doar declară un pointer numit x.

194
00:11:31,810 --> 00:11:35,380
Declară un pointer, dar dau seama și să înțeleagă ce se întâmplă de fapt pe

195
00:11:35,380 --> 00:11:38,490
chiar și în doar câteva acele caractere.

196
00:11:38,490 --> 00:11:42,040
>> Acum, asta e aproape un pic mai ușor, chiar dacă este o expresie mai mult.

197
00:11:42,040 --> 00:11:48,160
Deci, ce este acest sens, care este evidențiat acum: "malloc (10 * sizeof (int));" Da?

198
00:11:48,160 --> 00:11:52,350
[Răspuns Student, neinteligibil]

199
00:11:52,350 --> 00:11:58,250
Bine. Și am să-l duc acolo. E o bucată alocarea de memorie pentru zece numere întregi.

200
00:11:58,250 --> 00:12:02,190
Și acum să intrăm puțin mai adânc în; este alocarea unui segment de memorie pentru zece numere întregi.

201
00:12:02,190 --> 00:12:05,390
Ceea ce este malloc se întoarce apoi?

202
00:12:05,390 --> 00:12:10,390
Adresa de faptul că bucata, sau, mai concret, adresa primul octet din bucată.

203
00:12:10,390 --> 00:12:14,080
Cum sunt eu atunci, programator, să știe unde se termină că bucata de memorie?

204
00:12:14,080 --> 00:12:18,340
Știu că e contiguu. Malloc, prin definiție, vă va da o bucată de memorie contiguă.

205
00:12:18,340 --> 00:12:21,240
Nu există lacune în ea. Aveți acces la fiecare octet în bucată,

206
00:12:21,240 --> 00:12:26,760
spate în spate în spate, dar cum nu știu unde la sfârșitul acestui segment de memorie este?

207
00:12:26,760 --> 00:12:28,850
Când utilizați malloc? [Răspuns Student, neinteligibil] Bine.

208
00:12:28,850 --> 00:12:30,670
Tu nu faci. Trebuie să vă amintiți.

209
00:12:30,670 --> 00:12:35,960
Trebuie să ne amintim că am folosit valoarea 10, iar eu nu par chiar să fi făcut asta aici.

210
00:12:35,960 --> 00:12:41,000
Dar sarcina este în întregime pe mine. Strlen, care am devenit ușor bazeaza pe pentru siruri de caractere,

211
00:12:41,000 --> 00:12:45,860
functioneaza doar din cauza acestei convenții de a avea \ 0

212
00:12:45,860 --> 00:12:48,840
sau acest caracter special Nul, NUL, la sfârșitul unui șir.

213
00:12:48,840 --> 00:12:51,740
Asta nu deține doar pentru bucăți arbitrare de memorie.

214
00:12:51,740 --> 00:12:58,590
E la latitudinea dumitale. Deci linia 20, apoi, alocă o bucată de memorie

215
00:12:58,590 --> 00:13:02,590
care poate stoca zece numere întregi, și îl stochează adresa primul octet

216
00:13:02,590 --> 00:13:05,610
de faptul că segment de memorie în variabila x sunat.

217
00:13:05,610 --> 00:13:11,140
Ergo, care este un pointer. Deci linia 21, din păcate, a fost o greșeală.

218
00:13:11,140 --> 00:13:16,110
Dar, mai întâi, ceea ce o face? Se spune magazin la locația 10, 0 indexate,

219
00:13:16,110 --> 00:13:19,480
de segment de memorie numite x valoarea 0.

220
00:13:19,480 --> 00:13:21,510
>> Deci, observați o serie de lucruri se întâmplă.

221
00:13:21,510 --> 00:13:25,420
Chiar dacă x este un pointer, amintesc de la câteva săptămâni în urmă

222
00:13:25,420 --> 00:13:29,440
pe care le puteți utiliza în continuare matrice de tip notație suport pătrat.

223
00:13:29,440 --> 00:13:36,180
Pentru că asta e de fapt scurt-mână notație pentru aritmetică indicatorul mai criptic-aspect.

224
00:13:36,180 --> 00:13:40,320
în cazul în care ne-ar face ceva de genul asta: Ia adresa x, mutați peste 10 locuri,

225
00:13:40,320 --> 00:13:44,550
apoi du-te acolo la orice adresă este stocată în acea locație.

226
00:13:44,550 --> 00:13:48,090
Dar sincer, aceasta este doar atroce de a citi și a obține confortabil cu.

227
00:13:48,090 --> 00:13:52,900
Deci, lumea folosește de obicei între paranteze drepte doar pentru că este atât de mult mai uman-friendly pentru a citi.

228
00:13:52,900 --> 00:13:55,140
Dar asta e ceea ce se întâmplă cu adevărat sub capota;

229
00:13:55,140 --> 00:13:58,190
x este o adresă, nu o matrice, în sine.

230
00:13:58,190 --> 00:14:02,410
Deci, acest lucru este stocarea 0 la 10 în locația x.

231
00:14:02,410 --> 00:14:06,120
De ce este acest rau? Da?

232
00:14:06,120 --> 00:14:17,370
[Răspuns Student, neinteligibil] Exact.

233
00:14:17,370 --> 00:14:21,100
Am alocat doar zece Ints, dar ne bazam de la 0 la programarea în C,

234
00:14:21,100 --> 00:14:25,690
astfel încât să aveți acces la 0 1 2 3 4 5 6 7 8 9, dar nu 10.

235
00:14:25,690 --> 00:14:30,270
Deci, fie programul este de gând să vina segmentul sau nu este.

236
00:14:30,270 --> 00:14:32,900
Dar noi nu știm cu adevărat, aceasta este un fel de un comportament nedeterminist.

237
00:14:32,900 --> 00:14:35,600
Este într-adevăr depinde de faptul dacă vom avea noroc.

238
00:14:35,600 --> 00:14:40,650
Dacă se dovedește că sistemul de operare nu se supără dacă am folosi că octet suplimentar,

239
00:14:40,650 --> 00:14:43,360
chiar dacă nu le-a dat la mine, programul meu nu s-ar putea prăbuși.

240
00:14:43,360 --> 00:14:46,780
E crud, e buggy, dar ar putea să nu vezi că simptom,

241
00:14:46,780 --> 00:14:48,960
sau s-ar putea vedea doar o singură dată într-un timp.

242
00:14:48,960 --> 00:14:51,230
Dar realitatea este ca bug-ul este, de fapt, nu există.

243
00:14:51,230 --> 00:14:54,320
Și e foarte problematic dacă ați scris un program pe care doriți să fie corecte,

244
00:14:54,320 --> 00:14:58,840
pe care le-am vândut programul pe care oamenii folosesc ca de fiecare dată într-un timp eroare

245
00:14:58,840 --> 00:15:02,450
pentru că, desigur, acest lucru nu este bun. De fapt, dacă aveți un telefon Android sau un iPhone

246
00:15:02,450 --> 00:15:05,550
și vă descărca aplicații în aceste zile, în cazul în care v-ați avut vreodată o aplicație renunta,

247
00:15:05,550 --> 00:15:10,040
toate dintr-o dată el dispare, asta e aproape întotdeauna rezultatul unor problema de memorie legate de,

248
00:15:10,040 --> 00:15:12,830
prin care programatorul stricat și dereferenced un pointer

249
00:15:12,830 --> 00:15:18,670
că el sau ea nu ar trebui să aibă, și rezultatul de iOS sau Android este de a ucide doar programul complet

250
00:15:18,670 --> 00:15:23,080
mai degrabă decât un comportament nedefinit de risc sau un fel de compromis de securitate.

251
00:15:23,080 --> 00:15:25,950
>> Nu e un bug în altă acest program în afară de asta.

252
00:15:25,950 --> 00:15:30,180
Ce altceva am stricat în acest program?

253
00:15:30,180 --> 00:15:32,740
Eu nu am practicat ceea ce am predicat. Da?

254
00:15:32,740 --> 00:15:34,760
[Răspuns Student, neinteligibil] Bine.

255
00:15:34,760 --> 00:15:36,880
Nu am eliberat de memorie. Deci, regula de degetul mare acum

256
00:15:36,880 --> 00:15:43,150
trebuie să fie oricând te sun malloc, trebuie să apelați gratuit, atunci când ați terminat utilizarea acestei memorie.

257
00:15:43,150 --> 00:15:45,610
Acum, când aș vrea să eliberez această memorie?

258
00:15:45,610 --> 00:15:49,780
Probabil, presupunând că aceasta prima linie a fost actualizată, aș vrea să o fac aici.

259
00:15:49,780 --> 00:15:55,710
Pentru că nu am putut, de exemplu, o fac aici. De ce?

260
00:15:55,710 --> 00:15:57,860
Doar afara domeniului de aplicare. Deci, chiar dacă vorbim despre pointeri,

261
00:15:57,860 --> 00:16:04,830
aceasta este o săptămână 2 sau 3 cauză, în cazul în care x este numai în domeniul de aplicare interiorul acolade în cazul în care acesta a fost declarat.

262
00:16:04,830 --> 00:16:11,000
Deci, cu siguranta ai nu se poate elibera de acolo. Singura mea sansa de a se elibera este de aproximativ după linia 21.

263
00:16:11,000 --> 00:16:15,170
Acesta este un program destul de simplu, că a fost destul de ușor, odată ce fel de înfășurat mintea ta

264
00:16:15,170 --> 00:16:17,870
în jurul valorii de ceea ce face programul, în cazul în care greșelile au fost.

265
00:16:17,870 --> 00:16:20,500
Și chiar dacă nu l-am vazut la prima, să sperăm că e un pic evident acum

266
00:16:20,500 --> 00:16:23,870
că aceste greșeli sunt destul de ușor de rezolvat și ușor de făcut.

267
00:16:23,870 --> 00:16:28,720
Dar atunci când un program este mai mult de 12 de linii lungi, e 50 de linii lungi, 100 de linii de lung,

268
00:16:28,720 --> 00:16:31,150
de mers pe jos prin linia codul de linie, gândindu prin ea logic,

269
00:16:31,150 --> 00:16:35,110
este posibil, dar nu deosebit de distractiv de a face, în mod constant în căutarea de bug-uri,

270
00:16:35,110 --> 00:16:38,340
și este, de asemenea, dificil de a face, si asta e motivul pentru care un instrument ca Valgrind există.

271
00:16:38,340 --> 00:16:40,900
Lasă-mă să mergeți mai departe și face acest lucru: să-mi deschid fereastra mea terminale,

272
00:16:40,900 --> 00:16:45,400
și nu mă lăsa să ruleze doar de memorie, pentru ca memoria pare să fie bine.

273
00:16:45,400 --> 00:16:49,180
Primesc norocos. Mergând la faptul că octet suplimentare la sfârșitul matrice

274
00:16:49,180 --> 00:16:51,060
nu pare să fie prea problematice.

275
00:16:51,060 --> 00:16:56,370
Dar lasă-mă să, cu toate acestea, face o verificare bun-simț, ceea ce înseamnă doar pentru a verifica

276
00:16:56,370 --> 00:16:58,320
indiferent dacă aceasta este sau nu de fapt corectă.

277
00:16:58,320 --> 00:17:04,690
>> Deci, hai sa facem Valgrind-V - scurgeri de check-= complet,

278
00:17:04,690 --> 00:17:07,520
și apoi numele programului în acest caz este de memorie nu, a.out.

279
00:17:07,520 --> 00:17:10,760
Așa că lasă-mă să mergeți mai departe și de a face acest lucru. Apăsați Enter.

280
00:17:10,760 --> 00:17:14,109
Dragă Dumnezeu. Acest lucru este producția, iar acest lucru este ceea ce am făcut aluzie la mai devreme.

281
00:17:14,109 --> 00:17:17,550
Dar, în cazul în care veți învăța să citiți prin toate prostii aici,

282
00:17:17,550 --> 00:17:20,760
cea mai mare parte acest lucru este doar de ieșire de diagnosticare, care nu e interesant.

283
00:17:20,760 --> 00:17:24,829
Ceea ce ochiul tău vrea cu adevărat să fie căutați este orice mențiune de eroare sau este nevalid.

284
00:17:24,829 --> 00:17:26,800
Cuvinte care sugereaza probleme.

285
00:17:26,800 --> 00:17:29,340
Și într-adevăr, să vedem ce se întâmplă greșit aici.

286
00:17:29,340 --> 00:17:35,230
Am un rezumat de un anumit fel, "în uz la ieșire: 40. Bytes in 1 blocuri"

287
00:17:35,230 --> 00:17:38,750
Nu sunt sigur ce este un bloc este încă, dar 40 octeți

288
00:17:38,750 --> 00:17:41,260
de fapt, se simte ca și cum am putut da seama de unde vine de la faptul că.

289
00:17:41,260 --> 00:17:45,030
40 bytes. De ce sunt de 40 octeți în uz la ieșire?

290
00:17:45,030 --> 00:17:48,780
Și, mai precis, dacă vom derula în jos aici,

291
00:17:48,780 --> 00:17:54,520
de ce am pierdut cu siguranta 40 octeți? Da?

292
00:17:54,520 --> 00:17:59,520
[Răspuns Student, neinteligibil] Perfect. Da, exact.

293
00:17:59,520 --> 00:18:03,540
Au fost zece numere întregi, și fiecare dintre acestea este dimensiunea de 4, sau 32 biți,

294
00:18:03,540 --> 00:18:08,300
așa că am pierdut exact 40 bytes, deoarece, așa cum a propus, nu am sunat gratuit.

295
00:18:08,300 --> 00:18:13,460
Asta e un bug, și acum să ne uităm în jos un pic mai departe și să vedem de lângă acest lucru,

296
00:18:13,460 --> 00:18:16,900
"Invalid scriu de marimea 4." Acum, ce e asta?

297
00:18:16,900 --> 00:18:21,150
Această adresă este exprimat ceea ce notația de bază, aparent?

298
00:18:21,150 --> 00:18:23,640
Acest lucru este hexazecimal, și de fiecare dată când vedeți un număr, începând cu 0x,

299
00:18:23,640 --> 00:18:29,410
inseamna hexazecimal, pe care am făcut drumul înapoi în, cred, PSET 0 a lui secțiunea de întrebări,

300
00:18:29,410 --> 00:18:34,090
care a fost doar pentru a face un exercițiu de warmup, conversie zecimal în hexazecimal în binar și așa mai departe.

301
00:18:34,090 --> 00:18:39,220
Hexadecimal, doar prin convenție umană, este de obicei folosit pentru a reprezenta indicii

302
00:18:39,220 --> 00:18:41,570
sau, mai general, se adresează. E doar o convenție,

303
00:18:41,570 --> 00:18:45,340
deoarece este un pic mai ușor de citit, e un pic mai compact decat ceva de genul zecimal,

304
00:18:45,340 --> 00:18:47,720
și binar este inutil pentru majoritatea oamenilor de a utiliza.

305
00:18:47,720 --> 00:18:50,840
Deci, acum, ce înseamnă? Ei bine, se pare ca exista o scriere nevalidă

306
00:18:50,840 --> 00:18:54,480
de marimea 4 pe linia 21 din memory.c.

307
00:18:54,480 --> 00:18:59,180
Așa că hai să ne întoarcem la linia 21, și într-adevăr, aici este faptul că de scriere nevalid.

308
00:18:59,180 --> 00:19:02,640
Deci, Valgrind nu este de gând să dețină complet mâna mea și să-mi spui ce este fix,

309
00:19:02,640 --> 00:19:05,520
dar este detectarea că eu fac o scriere nevalid.

310
00:19:05,520 --> 00:19:08,800
Mă ating 4 octeți că nu ar trebui să fie, și se pare că asta e cauza,

311
00:19:08,800 --> 00:19:13,960
cum ați subliniat, fac [10] în loc de [9] maximal

312
00:19:13,960 --> 00:19:16,660
sau [0] sau ceva în între.

313
00:19:16,660 --> 00:19:19,690
Cu Valgrind, dau seama de fiecare dată când scrii acum un program de

314
00:19:19,690 --> 00:19:24,190
care utilizează indicii și folosește memoria, și malloc mai precis,

315
00:19:24,190 --> 00:19:27,080
cu siguranta a intra în obiceiul de a gestiona acest timp

316
00:19:27,080 --> 00:19:30,890
dar foarte ușor de copiat și inserat comanda Valgrind

317
00:19:30,890 --> 00:19:32,650
pentru a vedea dacă există unele erori acolo.

318
00:19:32,650 --> 00:19:34,820
Și o să fie copleșitoare de fiecare dată când vezi ieșire,

319
00:19:34,820 --> 00:19:39,430
ci doar prin analiza vizual toată producția și a vedea dacă vezi menționează de erori

320
00:19:39,430 --> 00:19:43,190
sau avertismente sau este invalid sau pierdere.

321
00:19:43,190 --> 00:19:46,200
Orice cuvinte care sună ca ti-ai pus undeva.

322
00:19:46,200 --> 00:19:48,580
Deci dau seama că e un instrument nou în setul de instrumente dumneavoastră.

323
00:19:48,580 --> 00:19:51,270
>> Acum, pe luni, am avut o grămadă de oameni vin aici

324
00:19:51,270 --> 00:19:53,150
și reprezintă noțiunea de listă legată.

325
00:19:53,150 --> 00:20:00,970
Și am introdus lista de legat ca o soluție la ceea ce problema?

326
00:20:00,970 --> 00:20:04,590
Da? [Răspuns Student, neinteligibil] Bine.

327
00:20:04,590 --> 00:20:06,530
Matricele nu poate avea memoria adăugată pentru ei.

328
00:20:06,530 --> 00:20:09,440
Dacă ați aloca o matrice de marimea 10, asta e tot ce ai.

329
00:20:09,440 --> 00:20:13,690
Puteti apela o funcție ca realloc dacă te-a sunat inițial malloc,

330
00:20:13,690 --> 00:20:17,580
și care poate încerca să crească matrice în cazul în care nu există spațiu spre sfârșitul anului acesta

331
00:20:17,580 --> 00:20:21,610
că nimeni altcineva nu foloseste, iar daca nu e, se va găsi doar tu o bucată mai mare în altă parte.

332
00:20:21,610 --> 00:20:25,040
Dar apoi se va copia toate aceste octeți în matrice nou.

333
00:20:25,040 --> 00:20:28,310
Aceasta pare a fi o soluție foarte corect.

334
00:20:28,310 --> 00:20:34,790
De ce este acest neatractiv?

335
00:20:34,790 --> 00:20:36,940
Vreau să spun că funcționează, oamenii s-au rezolvat această problemă.

336
00:20:36,940 --> 00:20:40,710
De ce am nevoie pentru a rezolva aceasta, luni, cu liste legate? Da?

337
00:20:40,710 --> 00:20:44,060
[Răspuns Student, neinteligibil] Aceasta ar putea lua o lungă perioadă de timp.

338
00:20:44,060 --> 00:20:49,260
De fapt, de fiecare dată când suni malloc sau realloc sau calloc, care este încă una,

339
00:20:49,260 --> 00:20:52,470
orice moment, programul, vorbesc la sistemul de operare,

340
00:20:52,470 --> 00:20:54,310
aveți tendința de a încetini programul de jos.

341
00:20:54,310 --> 00:20:57,470
Și dacă faci aceste tipuri de lucruri în bucle, te încetinirea lucruri cu adevărat în jos.

342
00:20:57,470 --> 00:21:00,740
Tu nu vei observa acest lucru pentru mai simplă a "Hello World" programe de tip,

343
00:21:00,740 --> 00:21:04,300
dar în programe mult mai mari, solicitând sistemul de operare din nou și din nou, pentru memorie

344
00:21:04,300 --> 00:21:07,520
sau dându-i înapoi din nou și din nou tinde să nu fie un lucru bun.

345
00:21:07,520 --> 00:21:11,210
În plus, e doar un fel de intelectual - este o pierdere de timp.

346
00:21:11,210 --> 00:21:16,490
De ce aloca mai multă memorie și mai mult, riscul de copierea totul în matrice noua,

347
00:21:16,490 --> 00:21:21,980
dacă aveți o alternativă care vă permite să aloce memorie doar la fel de mult ca tine de fapt nevoie?

348
00:21:21,980 --> 00:21:24,130
Deci, nu e plusuri și minusuri de aici.

349
00:21:24,130 --> 00:21:26,730
Unul dintre plusurile acum este că avem dinamism.

350
00:21:26,730 --> 00:21:29,100
Nu contează în cazul în care bucăți de memorie sunt că sunt liberi,

351
00:21:29,100 --> 00:21:32,070
Eu pot sorta doar de a crea aceste pesmet prin pointeri

352
00:21:32,070 --> 00:21:34,470
sa string lista mea toată legate împreună.

353
00:21:34,470 --> 00:21:36,470
Dar am plăti cel puțin un preț.

354
00:21:36,470 --> 00:21:40,060
>> Ce trebuie să renunțe la obținerea listelor legate?

355
00:21:40,060 --> 00:21:42,470
Da? [Răspuns Student, neinteligibil] Bine.

356
00:21:42,470 --> 00:21:45,650
Ai nevoie de mai multă memorie. Acum am nevoie de spațiu pentru aceste indicii,

357
00:21:45,650 --> 00:21:47,900
și, în cazul acestei liste simplu super-legată

358
00:21:47,900 --> 00:21:51,410
care este doar încearcă să stocheze întregi, care sunt de 4 octeți, ne tot spun

359
00:21:51,410 --> 00:21:54,240
Ei bine, un indicator este de 4 octeți, așa că acum am literalmente dublat

360
00:21:54,240 --> 00:21:57,290
cantitatea de memorie am nevoie doar pentru a stoca această listă.

361
00:21:57,290 --> 00:21:59,680
Dar, din nou, acest lucru este un compromis constant în informatică

362
00:21:59,680 --> 00:22:03,440
între timp și spațiu și, efortul de dezvoltare și alte resurse.

363
00:22:03,440 --> 00:22:06,630
Ce este un alt dezavantaj de a folosi o listă legată? Da?

364
00:22:06,630 --> 00:22:10,150
[Răspuns Student, neinteligibil]

365
00:22:10,150 --> 00:22:12,600
Bine. Nu la fel de ușor de accesat. Noi nu mai poate pârghie

366
00:22:12,600 --> 00:22:15,530
Săptămâna 0 principii ca dezbina si cucereste.

367
00:22:15,530 --> 00:22:18,220
Și, mai precis, căutare binară. Deoarece, chiar dacă noi, oamenii,

368
00:22:18,220 --> 00:22:20,400
poate vedea în cazul în care aproximativ mijlocul acestei liste este,

369
00:22:20,400 --> 00:22:25,840
calculatorul știe doar că această listă legată pornește de la adresa numit primul.

370
00:22:25,840 --> 00:22:28,250
Și asta e 0x123 sau ceva de genul asta.

371
00:22:28,250 --> 00:22:30,990
Și singura modalitate programul poate găsi elementul din mijloc

372
00:22:30,990 --> 00:22:33,350
este de a căuta, de fapt intreaga lista.

373
00:22:33,350 --> 00:22:35,500
Și chiar și atunci, pur și simplu trebuie să caute intreaga lista, deoarece

374
00:22:35,500 --> 00:22:38,950
chiar odată ce ajunge elementul din mijloc urmând indicii,

375
00:22:38,950 --> 00:22:42,380
te, programul, nu au nici o idee cât de mult această listă este, potențial,

376
00:22:42,380 --> 00:22:45,250
până când te-a lovit la sfârșitul anului acesta, si de unde stii programare

377
00:22:45,250 --> 00:22:48,600
că ești la capătul unei liste legate?

378
00:22:48,600 --> 00:22:51,120
E un pointer NULL specială, astfel încât, din nou, o convenție.

379
00:22:51,120 --> 00:22:53,870
Mai degrabă decât utiliza acest indicator, am cu siguranță nu vreau să fie o valoare gunoi

380
00:22:53,870 --> 00:22:57,750
îndreptat pe scena undeva, vrem să fie o parte în jos, NULL,

381
00:22:57,750 --> 00:23:01,530
astfel încât să avem această terminus în această structură de date, astfel știm unde se termină.

382
00:23:01,530 --> 00:23:03,410
>> Ce se întâmplă dacă vrem să manipuleze acest lucru?

383
00:23:03,410 --> 00:23:05,980
Am făcut cea mai mare a acestui punct de vedere vizual, și cu oamenii,

384
00:23:05,980 --> 00:23:07,630
dar ce se întâmplă dacă vrem să facem o introducere?

385
00:23:07,630 --> 00:23:12,360
Deci, lista inițială a fost de 9, 17, 20, 22, 29, 34.

386
00:23:12,360 --> 00:23:16,730
Ce se întâmplă dacă am vrut să apoi spațiu malloc pentru numărul de 55 de ani, un nod pentru ea,

387
00:23:16,730 --> 00:23:20,730
și apoi vrem să inserați 55 în lista la fel cum am făcut-o luni?

388
00:23:20,730 --> 00:23:23,690
Cum facem acest lucru? Ei bine, Anita a venit și ea a mers în esență, lista.

389
00:23:23,690 --> 00:23:27,500
Ea a început de la primul element, apoi următoarea, urmatoarea, urmatoarea, urmatoarea, urmatoarea.

390
00:23:27,500 --> 00:23:29,500
În cele din urmă a lovit din stânga tot drumul în jos

391
00:23:29,500 --> 00:23:34,480
si realizat oh, asta este NULL. Deci, ce manipulare indicatorul necesar să fie făcut?

392
00:23:34,480 --> 00:23:37,980
Persoana care a fost pe final, numarul 34, este necesar mâna stângă ridicată

393
00:23:37,980 --> 00:23:46,220
la punctul de la 55, 55 nevoie de brațul stâng îndreptat în jos pentru a fi noul NULL terminator. Adoptată.

394
00:23:46,220 --> 00:23:49,540
Destul de ușor pentru a insera 55 într-o listă sortată.

395
00:23:49,540 --> 00:23:51,800
Și cum ar putea arăta asta?

396
00:23:51,800 --> 00:23:55,690
>> Lasă-mă să mergeți mai departe și să se deschidă unele exemplu de cod aici.

397
00:23:55,690 --> 00:23:58,120
Voi deschide gedit, și lasă-mă să deschid două fișiere primul.

398
00:23:58,120 --> 00:24:02,050
Unul este list1.h, și permiteți-mi să reamintesc doar că aceasta a fost bucată de cod

399
00:24:02,050 --> 00:24:04,920
pe care am folosit pentru a reprezenta un nod.

400
00:24:04,920 --> 00:24:13,040
Un nod are atât un int n numit și un indicator numit în continuare că doar punctele de lucru următoare în listă.

401
00:24:13,040 --> 00:24:15,450
Care este acum într-un fișier. H.. De ce?

402
00:24:15,450 --> 00:24:19,090
E această convenție, și nu am profitat de aceasta o sumă uriașă noi înșine,

403
00:24:19,090 --> 00:24:22,220
dar persoana care a scris funcțiile printf și alte

404
00:24:22,220 --> 00:24:27,150
a dat ca un cadou pentru lumea toate aceste funcții prin scrierea unui fișier numit stdio.h.

405
00:24:27,150 --> 00:24:30,950
Și apoi există string.h, iar apoi e map.h, și există toate aceste fișiere h

406
00:24:30,950 --> 00:24:34,410
pe care le-ar putea fi văzut sau utilizate în timpul termenului scrise de alte persoane.

407
00:24:34,410 --> 00:24:38,470
De obicei, în aceste fișiere sunt h. Singurele lucruri cum ar fi typedefs

408
00:24:38,470 --> 00:24:42,310
sau declarații de tipuri personalizate sau declarații de constante.

409
00:24:42,310 --> 00:24:47,890
Tu nu pune implementari funcții "în fișiere antet.

410
00:24:47,890 --> 00:24:50,570
Ai pus, în schimb, doar prototipuri lor.

411
00:24:50,570 --> 00:24:53,050
Ai pus lucrurile pe care doriți să le partajați cu lumea ceea ce au nevoie

412
00:24:53,050 --> 00:24:55,640
, în scopul de a compila codul lor. Deci, doar pentru a intra în acest obicei,

413
00:24:55,640 --> 00:24:59,110
ne-am decis să facem același lucru. Nu e mult, în list1.h,

414
00:24:59,110 --> 00:25:02,070
dar am pus ceva care ar putea fi de interes pentru oameni din lume

415
00:25:02,070 --> 00:25:05,030
care doresc să utilizeze implementarea lista noastră de legat.

416
00:25:05,030 --> 00:25:08,040
Acum, în list1.c, nu voi trece prin toată chestia asta

417
00:25:08,040 --> 00:25:11,390
pentru ca e un pic cam lung, acest program, dar să rulați-l reala rapid la prompt.

418
00:25:11,390 --> 00:25:15,720
Lasă-mă să compileze List1, permiteți-mi să executați, apoi List1, și ceea ce veți vedea este

419
00:25:15,720 --> 00:25:18,070
am simulat am un program simplu pic aici

420
00:25:18,070 --> 00:25:20,990
care este de gând să-mi permite să adăugați și să eliminați numere într-o listă.

421
00:25:20,990 --> 00:25:24,310
Așa că lasă-mă să mergeți mai departe și tastați 3 pentru 3 opțiunea de meniu.

422
00:25:24,310 --> 00:25:27,880
Vreau să inserați numărul de - hai sa facem primul număr, care a fost de 9,

423
00:25:27,880 --> 00:25:30,550
si acum am spus că lista este acum 9.

424
00:25:30,550 --> 00:25:33,760
Lasă-mă să mergeți mai departe și face o altă inserție, așa că am lovit opțiunea de meniu 3.

425
00:25:33,760 --> 00:25:36,760
Ce număr vreau să inserați? 17.

426
00:25:36,760 --> 00:25:39,220
Enter. Și eu voi face doar una mai mult.

427
00:25:39,220 --> 00:25:41,720
Lasă-mă să introduceți numărul 22.

428
00:25:41,720 --> 00:25:45,850
Deci avem începuturile lista legate de faptul că am avut în format de slide-o clipă în urmă.

429
00:25:45,850 --> 00:25:48,740
Cum se intampla de fapt această inserție?

430
00:25:48,740 --> 00:25:52,000
Într-adevăr, 22 este acum la sfârșitul listei.

431
00:25:52,000 --> 00:25:55,050
Deci, i-am spus povestea pe scena de luni și reșapate chiar acum

432
00:25:55,050 --> 00:25:57,460
trebuie să fie, de fapt se intampla in cod.

433
00:25:57,460 --> 00:25:59,700
Să aruncăm o privire. Lasă-mă să defilați în jos în acest dosar.

434
00:25:59,700 --> 00:26:01,720
Vom treacă peste unele din functiile,

435
00:26:01,720 --> 00:26:05,630
dar vom merge în jos la, să zicem, funcția de inserare.

436
00:26:05,630 --> 00:26:11,720
>> Să vedem cum merge despre introducerea unui nou nod în această listă legată.

437
00:26:11,720 --> 00:26:14,550
În cazul în care este declarată listă? Ei bine, hai să parcurgeți tot drumul până în partea de sus,

438
00:26:14,550 --> 00:26:19,970
și observați că lista mea de legat este în esență, a declarat ca un indicator unic, care e initial NULL.

439
00:26:19,970 --> 00:26:23,180
Deci, eu sunt, folosind o variabilă globală aici, care, în general, le-am predicat împotriva

440
00:26:23,180 --> 00:26:25,280
deoarece face codul un pic murdar pentru a menține,

441
00:26:25,280 --> 00:26:29,080
e un fel de leneș, de obicei, dar nu e leneș și nu e greșit și nu e rău

442
00:26:29,080 --> 00:26:33,660
dacă scopul programului tău de limbă de mare în viață este de a simula o listă legat.

443
00:26:33,660 --> 00:26:35,460
Care este exact ceea ce facem.

444
00:26:35,460 --> 00:26:39,100
Deci, mai degrabă decât să constate acest lucru în principal și apoi trebuie să-l treacă la orice funcție

445
00:26:39,100 --> 00:26:42,640
am scris în acest program, în loc să ne dăm seama oh, hai sa facem doar la nivel mondial

446
00:26:42,640 --> 00:26:47,060
deoarece întregul scop al acestui program este de a demonstra unul și numai o singură listă legată.

447
00:26:47,060 --> 00:26:50,700
Așa că se simte bine. Aici sunt prototipuri mele, și nu va trece prin toate acestea,

448
00:26:50,700 --> 00:26:55,800
dar am scris o funcție de ștergere, o funcție găsi, o funcție de inserare, și o funcție de traverse.

449
00:26:55,800 --> 00:26:59,080
Dar haideți să mergem acum înapoi la funcția de inserare

450
00:26:59,080 --> 00:27:01,490
și a vedea modul în care aceasta funcționează aici.

451
00:27:01,490 --> 00:27:09,940
Inserare este pe linia - aici vom merge.

452
00:27:09,940 --> 00:27:12,850
Inserare. Asa ca nu ia nici un argument, pentru că vom cere

453
00:27:12,850 --> 00:27:15,930
interiorul utilizare a acestei funcții pentru numărul care doriți să îl inserați.

454
00:27:15,930 --> 00:27:19,410
Dar, mai întâi, ne pregătim pentru a le da ceva spatiu.

455
00:27:19,410 --> 00:27:22,050
Aceasta este un fel de copy si paste din alt exemplu.

456
00:27:22,050 --> 00:27:25,110
În acest caz, am fost alocarea unui int, de data aceasta vom aloca un nod.

457
00:27:25,110 --> 00:27:27,910
Nu-mi amintesc cu adevărat cât de multe bytes-un nod este, dar asta e bine.

458
00:27:27,910 --> 00:27:30,460
Sizeof poate da seama de asta pentru mine.

459
00:27:30,460 --> 00:27:33,340
Și de ce sunt eu de verificare pentru NULL în linie 120?

460
00:27:33,340 --> 00:27:37,530
Ce ar putea merge prost în linie 119? Da?

461
00:27:37,530 --> 00:27:40,530
[Răspuns Student, neinteligibil]

462
00:27:40,530 --> 00:27:43,440
Bine. Doar ar putea fi cazul în care l-am cerut prea multă memorie

463
00:27:43,440 --> 00:27:47,020
sau ceva nu e în regulă și sistemul de operare nu are suficiente bytes să-mi dea,

464
00:27:47,020 --> 00:27:50,640
așa că semnalează cât mai mult prin returnarea NULL, iar dacă nu verifica faptul că

465
00:27:50,640 --> 00:27:54,710
și am orbește proceda pentru a utiliza adresa întors, ar putea fi NULL.

466
00:27:54,710 --> 00:27:58,400
Ar putea fi o valoare necunoscută, nu este un lucru bun dacă nu -

467
00:27:58,400 --> 00:28:00,590
de fapt, nu va fi o valoare necunoscută. Ar putea fi NULL, deci nu vreau

468
00:28:00,590 --> 00:28:02,550
să abuzeze de ea și de risc dereferencing-l.

469
00:28:02,550 --> 00:28:07,410
În cazul în care se întâmplă, mă întorc doar și vom preface ca și cum nu am primit inapoi nici de memorie, la toate.

470
00:28:07,410 --> 00:28:12,270
>> În caz contrar, spun utilizatorul să-mi dai un număr pentru a insera, eu numesc GetInt vechiul nostru prieten,

471
00:28:12,270 --> 00:28:15,530
și apoi aceasta a fost noua sintaxă am introdus pe luni.

472
00:28:15,530 --> 00:28:20,320
"Newptr-> n" înseamnă să ia adresa care va fost dat de malloc

473
00:28:20,320 --> 00:28:23,490
care reprezintă primul octet al unui obiect nou nod,

474
00:28:23,490 --> 00:28:26,860
și apoi du-te la câmp denumit nr.

475
00:28:26,860 --> 00:28:35,270
O mică întrebare trivia: Acesta este echivalent cu ceea ce linie de cod criptic mai mult?

476
00:28:35,270 --> 00:28:38,110
Cum altfel aș fi putut fi scris asta? Vrei să ia o lovitură de cuțit?

477
00:28:38,110 --> 00:28:41,480
[Răspuns Student, neinteligibil]

478
00:28:41,480 --> 00:28:44,870
Bine. Utilizarea nr., Dar nu e la fel de simplu ca asta.

479
00:28:44,870 --> 00:28:47,090
Ce am mai întâi trebuie să fac? [Răspuns Student, neinteligibil]

480
00:28:47,090 --> 00:28:52,730
Bine. Am nevoie pentru a face * newptr.n.

481
00:28:52,730 --> 00:28:55,610
Deci, acest lucru este indicatorul spune noi este evident o adresă. De ce?

482
00:28:55,610 --> 00:28:59,520
Pentru că a fost returnat de malloc. * Newptr spune "du-te acolo",

483
00:28:59,520 --> 00:29:02,970
și apoi odată ce ești acolo, atunci puteți folosi mai familiare. n,

484
00:29:02,970 --> 00:29:05,730
dar aceasta doar pare un pic urât, mai ales în cazul în care noi, oamenii, sunt de gând să

485
00:29:05,730 --> 00:29:10,360
egal indicii cu săgeți tot timpul, lumea a standardizat pe această notație săgeată,

486
00:29:10,360 --> 00:29:12,320
care face exact acelasi lucru.

487
00:29:12,320 --> 00:29:16,070
Astfel încât să utilizați numai -> notația atunci când lucru pe stânga este un pointer.

488
00:29:16,070 --> 00:29:18,790
În caz contrar, dacă e un struct reală, utilizați nr..

489
00:29:18,790 --> 00:29:25,800
Și apoi asta: De ce am inițializa newptr-> de lângă NULL?

490
00:29:25,800 --> 00:29:28,610
Noi nu vrem o mână stângă marionetă off de la sfârșitul etapei.

491
00:29:28,610 --> 00:29:31,630
Ne dorim ca aceasta îndreptată direct în jos, ceea ce înseamnă sfârșitul acestei liste

492
00:29:31,630 --> 00:29:34,980
ar putea fi de la acest nod, așa că mai bine asigurați-vă că este NULL.

493
00:29:34,980 --> 00:29:38,460
Și, în general, initializarea variabilelor sau membrii de date și structs

494
00:29:38,460 --> 00:29:40,470
la ceva este doar bună practică.

495
00:29:40,470 --> 00:29:45,170
Doar permițându-gunoiului există și va continua să existe, în general, te scoate din necaz

496
00:29:45,170 --> 00:29:48,650
în cazul în care ați uitat să faci ceva mai târziu.

497
00:29:48,650 --> 00:29:51,590
>> Iată câteva cazuri. Aceasta, din nou, este funcția de inserare,

498
00:29:51,590 --> 00:29:54,930
și primul lucru pe care am verificati daca este variabilă numită în primul rând,

499
00:29:54,930 --> 00:29:58,240
că variabila globală este NULL, înseamnă că nu există nici o listă legată.

500
00:29:58,240 --> 00:30:02,460
Noi nu am introdus nici numere, asa ca e banal pentru a introduce acest număr curent

501
00:30:02,460 --> 00:30:05,240
în listă, pentru că pur și simplu aparține la începutul listei.

502
00:30:05,240 --> 00:30:08,100
Deci asta a fost atunci când Anita a fost doar stau aici singur, pretinzând

503
00:30:08,100 --> 00:30:11,390
nimeni altcineva nu a fost aici pe scenă până când am alocat un nod,

504
00:30:11,390 --> 00:30:13,940
atunci ea ar putea ridica mâna pentru prima dată,

505
00:30:13,940 --> 00:30:17,420
în cazul în care toată lumea a venit pe scenă după ea luni.

506
00:30:17,420 --> 00:30:22,900
Acum aici, aceasta este o verificare în cazul în care ceva trebuie să spun, dacă nodul nou valoarea n

507
00:30:22,900 --> 00:30:27,370
este <valoarea lui n în primul nod curent,

508
00:30:27,370 --> 00:30:29,930
înseamnă că există o listă care este legat început.

509
00:30:29,930 --> 00:30:32,330
E cel puțin un nod în listă, dar acest nou tip

510
00:30:32,330 --> 00:30:37,230
înainte de a aparține, așa că avem nevoie să se miște lucrurile în jurul valorii.

511
00:30:37,230 --> 00:30:43,450
Cu alte cuvinte, în cazul în care lista a început doar cu, să zicem,

512
00:30:43,450 --> 00:30:48,100
doar numărul 17, care e - de fapt, putem face acest lucru mai clar.

513
00:30:48,100 --> 00:30:56,010
Dacă începem povestea noastră cu un indicator numit aici în primul rând,

514
00:30:56,010 --> 00:30:59,870
și inițial este NULL, si vom introduce numarul 9,

515
00:30:59,870 --> 00:31:02,510
numărul 9 în mod clar parte la începutul listei.

516
00:31:02,510 --> 00:31:07,400
Așa că hai să ne prefacem că malloced doar adresa sau numărul 9 și a pus-o aici.

517
00:31:07,400 --> 00:31:13,170
Dacă prima este de 9 în mod implicit, primul scenariu am discutat înseamnă doar punctul hai tipul ăsta aici,

518
00:31:13,170 --> 00:31:15,790
lasă ca NULL, acum avem numărul 9.

519
00:31:15,790 --> 00:31:18,280
Numărul următor dorim să introduceți este 17.

520
00:31:18,280 --> 00:31:22,420
17 aparține aici, așa că vom avea de a face unele pas cu pas logic prin asta.

521
00:31:22,420 --> 00:31:26,060
Asa ca hai sa schimb, inainte de a face asta, hai să pretindem că ne-am dorit pentru a introduce numărul 8.

522
00:31:26,060 --> 00:31:28,650
>> Deci, doar de dragul lui comoditate, am de gând să atrag aici.

523
00:31:28,650 --> 00:31:30,760
Dar tine minte, malloc poate pune cel mai oriunde.

524
00:31:30,760 --> 00:31:33,460
Dar, de dragul desenului, am să-l pun aici.

525
00:31:33,460 --> 00:31:38,440
Așa că am alocat prefac doar un nod pentru numărul 8, aceasta este NULL în mod implicit.

526
00:31:38,440 --> 00:31:42,800
Ceea ce trebuie să se întâmple acum? Un tânăr de lucruri.

527
00:31:42,800 --> 00:31:47,090
Am făcut această greșeală pe scena in data de luni în cazul în care vom completa un pointer ca aceasta,

528
00:31:47,090 --> 00:31:51,890
apoi a făcut acest lucru, și apoi am susținut - am orfani oricine altcineva pe scenă.

529
00:31:51,890 --> 00:31:54,350
Pentru că tu Cant - ordinea operațiunilor de aici este importantă,

530
00:31:54,350 --> 00:31:58,760
pentru că acum ne-am pierdut acest nod 9, care este doar un fel de plutire în spațiu.

531
00:31:58,760 --> 00:32:01,150
Deci, acest lucru nu a fost abordarea dreapta pe luni.

532
00:32:01,150 --> 00:32:03,330
Mai întâi trebuie să facem altceva.

533
00:32:03,330 --> 00:32:06,280
Starea lumii arata ca acest lucru. Inițial, 8 a fost alocat.

534
00:32:06,280 --> 00:32:10,550
Ceea ce ar fi o modalitate mai bună de a insera 8?

535
00:32:10,550 --> 00:32:14,720
În loc de actualizarea acestui indicator în primul rând, actualizat doar asta aici în loc.

536
00:32:14,720 --> 00:32:17,720
Deci, avem nevoie de o linie de cod care va transforma acest personaj NULL

537
00:32:17,720 --> 00:32:22,020
într-un indicator real care este îndreptat la nodul 9,

538
00:32:22,020 --> 00:32:27,970
și apoi ne putem schimba în condiții de siguranță de la punctul de la prima tipul ăsta aici.

539
00:32:27,970 --> 00:32:31,330
Acum avem o listă, o listă legată, din două elemente.

540
00:32:31,330 --> 00:32:33,580
Și ce înseamnă acest fapt arata ca aici?

541
00:32:33,580 --> 00:32:36,900
Dacă ne uităm la codul, observați că am făcut exact acest lucru.

542
00:32:36,900 --> 00:32:41,970
Am spus newptr, și în această poveste, a fost îndreptat newptr la tipul ăsta.

543
00:32:41,970 --> 00:32:45,520
>> Așa că lasă-mă să elaboreze un lucru mai mult, și ar trebui să au lăsat camera un pic mai mult pentru acest lucru.

544
00:32:45,520 --> 00:32:48,540
Deci, iartă desen micuță.

545
00:32:48,540 --> 00:32:52,140
Acest tip se numește newptr.

546
00:32:52,140 --> 00:32:57,940
Aceasta este variabila am declarat câteva rânduri mai devreme, în linie - chiar deasupra 25.

547
00:32:57,940 --> 00:33:03,430
Și se indică la 8. Deci, atunci când spun newptr-> urmator, asta înseamnă du-te la struct

548
00:33:03,430 --> 00:33:07,910
care este indicat a fi puțin prin newptr, deci iată-ne, du-te acolo.

549
00:33:07,910 --> 00:33:13,990
Atunci săgeata spune obține următorul câmp, și apoi = este pus spune ce valoare acolo?

550
00:33:13,990 --> 00:33:17,280
Valoare care a fost, în primul, ceea ce a fost în valoare de primul?

551
00:33:17,280 --> 00:33:21,930
În primul rând a fost îndreptat la acest nod, astfel încât înseamnă aceasta ar trebui să arate acum la acest nod.

552
00:33:21,930 --> 00:33:25,660
Cu alte cuvinte, ceea ce pare chiar dacă o mizerie ridicol cu ​​scrisul meu,

553
00:33:25,660 --> 00:33:28,620
ceea ce este o idee simpla de a muta doar în jurul valorii de aceste săgeți

554
00:33:28,620 --> 00:33:31,560
se traduce la Codul cu doar acest liner unul.

555
00:33:31,560 --> 00:33:38,110
Păstrează ceea ce este în primul următorul câmp și apoi actualizați ceea ce este de fapt prima.

556
00:33:38,110 --> 00:33:40,900
Să mergem mai departe și fast-forward, prin unele dintre acestea,

557
00:33:40,900 --> 00:33:44,220
si uita-te numai la această inserție coada pentru acum.

558
00:33:44,220 --> 00:33:51,210
Să presupunem că am ajunge la punctul în care mi se pare că următorul câmp de unii nod este NULL.

559
00:33:51,210 --> 00:33:53,410
Și la acest punct, în poveste, un detaliu pe care am atenua peste

560
00:33:53,410 --> 00:33:58,170
este ca am introdus un alt indicator de până aici, în linie 142, indicatorul predecesorul.

561
00:33:58,170 --> 00:34:01,320
În esență, în acest moment, în poveste, o dată lista devine lung,

562
00:34:01,320 --> 00:34:04,800
Am facut un fel de nevoie să-l meargă cu două degete pentru că dacă merg prea departe,

563
00:34:04,800 --> 00:34:08,219
amintesc într-o singură listă de lungime, nu poți merge înapoi.

564
00:34:08,219 --> 00:34:13,659
Deci, această idee a predptr este degetul meu stâng, și newptr - nu newptr.

565
00:34:13,659 --> 00:34:17,199
Un alt indicator care este aici este degetul meu altul, iar eu sunt doar un fel de mers pe jos lista.

566
00:34:17,199 --> 00:34:22,179
Asta e motivul pentru care există. Dar haideți să ia în considerare doar unul dintre cazurile mai simple aici.

567
00:34:22,179 --> 00:34:26,620
În cazul în care câmpul pe care indicatorul de pe lângă este NULL, ceea ce e implicație logică?

568
00:34:26,620 --> 00:34:30,840
Dacă sunt dipozitive de această listă și te-a lovit un pointer nul?

569
00:34:30,840 --> 00:34:35,780
Esti la sfârșitul listei, și astfel codul pentru a adăuga acest element, atunci o altă

570
00:34:35,780 --> 00:34:41,230
este un fel de intuitivă, care va avea următorul nod al cărui pointer este NULL,

571
00:34:41,230 --> 00:34:46,120
astfel încât acesta este în prezent NULL, si schimba-l, totuși, să fie adresa de nod nou.

572
00:34:46,120 --> 00:34:52,260
Deci, noi suntem doar desen în codul săgeata care am desenat pe scenă prin ridicarea mâna cuiva stânga.

573
00:34:52,260 --> 00:34:54,070
>> Și cazul în care voi flutur mâinile puțin pentru moment,

574
00:34:54,070 --> 00:34:58,020
doar pentru că cred că e ușor să te pierzi atunci când o facem în acest tip de mediu,

575
00:34:58,020 --> 00:35:00,600
este de verificare pentru inserare la mijlocul lui lista.

576
00:35:00,600 --> 00:35:03,220
Dar, doar intuitiv, ceea ce trebuie să se întâmple în cazul în care doriți să dau seama

577
00:35:03,220 --> 00:35:06,600
în cazul în care unele număr aparține în mijloc este ca nu trebuie sa-l meargă

578
00:35:06,600 --> 00:35:09,510
cu mai mult de un deget, mai mult de un pointer,

579
00:35:09,510 --> 00:35:12,920
seama de unde îi aparține de verificare este elementul <cel curent,

580
00:35:12,920 --> 00:35:15,450
> Curentă, și o dată ce găsiți acel loc,

581
00:35:15,450 --> 00:35:20,400
atunci va trebui să faci acest tip de joc în cazul în care vă mutați coajă de indicii în jurul valorii de foarte mare atenție.

582
00:35:20,400 --> 00:35:23,850
Și acest răspuns, în cazul în care doriți să motiv, prin acest lucru la domiciliu pe cont propriu,

583
00:35:23,850 --> 00:35:28,340
se reduce doar la aceste două linii de cod, dar ordinea acestor linii este foarte importantă.

584
00:35:28,340 --> 00:35:31,390
Pentru că dacă te las cuiva mana si ridica altcineva e în ordine greșită,

585
00:35:31,390 --> 00:35:34,580
din nou, ai putea ajunge orphaning listă.

586
00:35:34,580 --> 00:35:39,500
Pentru a rezuma mai mult conceptual, introducerea la coada este relativ simplă.

587
00:35:39,500 --> 00:35:42,940
Inserare la cap este, de asemenea, relativ simplă,

588
00:35:42,940 --> 00:35:45,580
dar trebuie să vă actualizați un indicator suplimentar de această dată

589
00:35:45,580 --> 00:35:47,930
pentru a stoarce numărul 5 în lista de aici,

590
00:35:47,930 --> 00:35:51,560
și apoi inserarea în mijlocul presupune un efort chiar mai mult,

591
00:35:51,560 --> 00:35:56,130
la foarte atent introduce numărul 20 în locația corectă,

592
00:35:56,130 --> 00:35:58,350
care este între 17 și 22.

593
00:35:58,350 --> 00:36:02,700
Deci, aveți nevoie pentru a face ceva de genul avea noul nod 20 de puncte la 22,

594
00:36:02,700 --> 00:36:08,470
și apoi, indicatorul care nodului trebuie să fie actualizate ultima dată?

595
00:36:08,470 --> 00:36:10,630
E 17, pentru a insera de fapt.

596
00:36:10,630 --> 00:36:14,080
Deci, din nou, voi amâna codul actual pentru că punerea în aplicare particular.

597
00:36:14,080 --> 00:36:17,280
>> La prima vedere, e un pic coplesitor, dar este de fapt doar o buclă infinită

598
00:36:17,280 --> 00:36:21,770
care este looping, looping, looping, looping, și de rupere de îndată ce te-a lovit indicatorul NULL,

599
00:36:21,770 --> 00:36:24,590
moment în care se poate face inserarea necesare.

600
00:36:24,590 --> 00:36:30,960
Acest lucru, atunci, este reprezentantul legată de inserare cod listă.

601
00:36:30,960 --> 00:36:34,590
Asta a fost un fel de mult, si se simte ca și cum ne-am rezolvat o problemă,

602
00:36:34,590 --> 00:36:36,940
dar am introdus o un întreg alta. Sincer, ne-am petrecut tot acest timp

603
00:36:36,940 --> 00:36:40,540
pe mare O și Ω și timpul de funcționare, încercând să rezolve problemele mai repede,

604
00:36:40,540 --> 00:36:43,270
și aici facem un pas mare înapoi, se simte.

605
00:36:43,270 --> 00:36:45,380
Și totuși, dacă scopul este de a stoca date,

606
00:36:45,380 --> 00:36:48,010
se simte ca Sfântul Graal, așa cum am mai spus, luni, ar fi cu adevărat

607
00:36:48,010 --> 00:36:50,470
pentru a stoca lucruri instantaneu.

608
00:36:50,470 --> 00:36:53,930
>> De fapt, să presupunem că am făcut lista pune deoparte pentru un moment legat

609
00:36:53,930 --> 00:36:56,000
și am introdus în locul noțiunea de tabel.

610
00:36:56,000 --> 00:36:59,110
Și să ne gândim doar de o masă pentru un moment ca o matrice.

611
00:36:59,110 --> 00:37:03,790
Această matrice și acest caz are aici unele elemente de 26, 0 25, prin

612
00:37:03,790 --> 00:37:07,940
și să presupunem că aveți nevoie de ceva bucată de depozitare pentru numele:

613
00:37:07,940 --> 00:37:10,350
Alice si Bob și Charlie și cum ar fi.

614
00:37:10,350 --> 00:37:12,880
Și ai nevoie de o anumită structură de date pentru a stoca aceste nume.

615
00:37:12,880 --> 00:37:15,000
Ei bine, ai putea folosi ceva de genul o listă legată

616
00:37:15,000 --> 00:37:20,260
și ai putea merge lista de introducerea Alice înainte de Bob și Charlie după Bob și așa mai departe.

617
00:37:20,260 --> 00:37:23,850
Și, de fapt, în cazul în care doriți să vedeți codul de genul asta ca o paranteza,

618
00:37:23,850 --> 00:37:27,230
știu că în list2.h, facem exact acest lucru.

619
00:37:27,230 --> 00:37:30,610
Nu vom trece prin acest cod, dar aceasta este o variantă de primul exemplu

620
00:37:30,610 --> 00:37:34,640
care introduce un struct parte ne-am mai văzut înainte de elev numitul,

621
00:37:34,640 --> 00:37:40,330
si atunci ce este de fapt stochează în lista de legat este un pointer la o structură de elev

622
00:37:40,330 --> 00:37:44,520
, mai degrabă decât un număr întreg simplu pic, nr.

623
00:37:44,520 --> 00:37:46,900
Deci dai seama că e cod acolo, care implică siruri de caractere reale,

624
00:37:46,900 --> 00:37:49,940
dar dacă obiectivul la îndemână într-adevăr acum este de a aborda problema eficienței,

625
00:37:49,940 --> 00:37:53,380
nu ar fi frumos dacă suntem dat un obiect numit Alice,

626
00:37:53,380 --> 00:37:56,020
vrem să o pună în locul potrivit într-o structură de date,

627
00:37:56,020 --> 00:37:58,860
se simte ca și cum ar fi într-adevăr frumos să afișezi doar Alice,

628
00:37:58,860 --> 00:38:01,180
al cărui nume începe cu A, în prima locatie.

629
00:38:01,180 --> 00:38:05,270
Și Bob, al cărui nume începe cu B, în a doua locație.

630
00:38:05,270 --> 00:38:09,580
Cu o matrice, sau să începem numindu-l un tabel, un tabel hash de la faptul că,

631
00:38:09,580 --> 00:38:13,650
putem face exact acest lucru. Dacă ni se dă un nume ca Alice,

632
00:38:13,650 --> 00:38:16,700
un șir de caractere ca Alice, unde poti sa pui un-L-i-c-e?

633
00:38:16,700 --> 00:38:20,540
Avem nevoie de o hueristic. Avem nevoie de o funcție pentru a lua unele de intrare ca Alice

634
00:38:20,540 --> 00:38:24,610
și să se întoarcă un răspuns, "Pune Alice în această locație."

635
00:38:24,610 --> 00:38:28,720
Și această funcție, această cutie neagra, va fi numit o funcție hash.

636
00:38:28,720 --> 00:38:32,330
>> O funcție hash este ceva care are o intrare, cum ar fi "Alice",

637
00:38:32,330 --> 00:38:38,080
și se întoarce la tine, de obicei, locația numerică, în unele structuri de date în cazul în care Alice îi aparține.

638
00:38:38,080 --> 00:38:40,830
În acest caz, funcția hash nostru ar trebui să fie relativ simplă.

639
00:38:40,830 --> 00:38:47,510
Funcția hash noastră ar trebui să spun, dacă ți sa dat "Alice", pe care personajul trebuie să-mi pasă?

640
00:38:47,510 --> 00:38:55,660
Primul. Așa că mă uit la [0], iar apoi spun, dacă [0] este un caracter, returna numărul 0.

641
00:38:55,660 --> 00:39:01,130
Dacă e B, întoarce 1. Dacă C e, întoarce 2, și așa mai departe.

642
00:39:01,130 --> 00:39:05,940
Toate index 0, și că mi-ar permite să inserați Alice si Bob, apoi, apoi Charlie și așa mai departe

643
00:39:05,940 --> 00:39:10,960
în această structură de date. Dar există o problemă.

644
00:39:10,960 --> 00:39:13,060
Ce se întâmplă dacă Anita vine din nou?

645
00:39:13,060 --> 00:39:17,510
În cazul în care nu am pus Anita? Numele ei, de asemenea, începe cu litera A,

646
00:39:17,510 --> 00:39:20,330
și se simte ca și cum am făcut-o mizerie și mai mare a acestei probleme.

647
00:39:20,330 --> 00:39:24,380
Avem acum inserarea imediată, inserarea constanta de timp, într-o structură de date

648
00:39:24,380 --> 00:39:27,100
, mai degrabă decât mai rău caz liniar,

649
00:39:27,100 --> 00:39:29,510
dar ce putem face cu Anita în acest caz?

650
00:39:29,510 --> 00:39:34,110
Care sunt cele două opțiuni, într-adevăr? Da?

651
00:39:34,110 --> 00:39:37,410
[Răspuns Student, neinteligibil] Ok, deci am putea avea o altă dimensiune.

652
00:39:37,410 --> 00:39:42,320
Asta e bine. Astfel încât să putem construi lucruri în 3D așa cum am vorbit despre verbal luni.

653
00:39:42,320 --> 00:39:46,700
Am putea adăuga un alt acces aici, dar să presupunem că nu, am încercat să păstreze acest simplu.

654
00:39:46,700 --> 00:39:50,160
Scopul întregii aici este de a avea imediat constantă timp de acces,

655
00:39:50,160 --> 00:39:52,170
Deci, asta e adăugând complexitate prea mult.

656
00:39:52,170 --> 00:39:55,970
Care sunt alte opțiuni atunci când încearcă să inserați Anita in aceasta structura de date? Da?

657
00:39:55,970 --> 00:39:58,610
[Răspuns Student, neinteligibil] Bine. Deci, am putea muta în jos oricine altcineva,

658
00:39:58,610 --> 00:40:03,040
cum ar fi Charlie ghionturi jos Bob și Alice, iar apoi am pus Anita în cazul în care ea într-adevăr vrea să fie.

659
00:40:03,040 --> 00:40:05,660
>> Desigur, acum, e un efect secundar al acestei.

660
00:40:05,660 --> 00:40:09,000
Această structură de date este, probabil, util nu pentru că vrem să inserați o dată pe oameni

661
00:40:09,000 --> 00:40:11,250
ci pentru că vrem să verificați dacă sunt acolo mai târziu

662
00:40:11,250 --> 00:40:13,600
dacă vrem să imprime toate numele din structura de date.

663
00:40:13,600 --> 00:40:15,850
Am de gând să faci ceva cu aceste date în cele din urmă.

664
00:40:15,850 --> 00:40:20,810
Așa că acum am un fel de filetat peste Alice, care nu mai este în cazul în care ea ar trebui sa fie.

665
00:40:20,810 --> 00:40:23,880
Nici nu este Bob, și nici nu este Charlie.

666
00:40:23,880 --> 00:40:26,060
Deci, poate că acest lucru nu este o idee prea bună.

667
00:40:26,060 --> 00:40:28,830
Dar, într-adevăr, aceasta este o opțiune. Am putea schimba toată lumea în jos,

668
00:40:28,830 --> 00:40:32,240
sau naiba, Anita a venit târziu pentru joc, de ce nu am pus doar Anita

669
00:40:32,240 --> 00:40:35,870
Nu aici, nu aici, nu aici, hai să punem doar ea un pic mai jos în listă.

670
00:40:35,870 --> 00:40:38,680
Dar, apoi, această problemă începe să revină din nou.

671
00:40:38,680 --> 00:40:41,630
S-ar putea fi capabil de a găsi Alice instantaneu, pe baza unui nume primul ei.

672
00:40:41,630 --> 00:40:44,320
Și Bob instantaneu, și Charlie. Dar apoi te uiți pentru Anita,

673
00:40:44,320 --> 00:40:46,360
și vezi tu, hmm, Alice este în modul.

674
00:40:46,360 --> 00:40:48,770
Ei bine, lasă-mă să verificați de mai jos Alice. Bob nu este Anita.

675
00:40:48,770 --> 00:40:51,850
Charlie nu este Anita. Oh, nu există Anita.

676
00:40:51,850 --> 00:40:54,720
Și dacă veți continua ca trenul de logică tot drumul,

677
00:40:54,720 --> 00:41:00,690
ce e momentul cel mai rău caz de funcționare de a gasi sau de a introduce Anita în această structură de date nouă?

678
00:41:00,690 --> 00:41:03,280
Este O (n), nu?

679
00:41:03,280 --> 00:41:06,280
Pentru că, în cel mai rău caz, nu e Alice, Bob, Charlie. . .

680
00:41:06,280 --> 00:41:10,150
tot drumul până la cineva pe nume "Y", deci nu e doar un singur loc rămas.

681
00:41:10,150 --> 00:41:13,950
Din fericire, nu avem nici cea numita "Z", asa ca am pus la Anita foarte jos.

682
00:41:13,950 --> 00:41:16,040
>> Nu ne-am rezolvat cu adevarat problema.

683
00:41:16,040 --> 00:41:19,890
Deci, poate avem nevoie de a introduce această a treia dimensiune.

684
00:41:19,890 --> 00:41:22,230
Și se pare că, dacă facem introduce această a treia dimensiune,

685
00:41:22,230 --> 00:41:25,240
nu putem face acest lucru perfect, dar Sfântul Graal va fi obtinerea

686
00:41:25,240 --> 00:41:28,370
constantă în timp inserarea si insertii dinamice, astfel încât

687
00:41:28,370 --> 00:41:30,960
nu avem la greu-cod-o serie de dimensiune 26.

688
00:41:30,960 --> 00:41:34,400
Noi putem introduce cât mai multe nume ca vrem, dar să luăm nostru de 5 minute de pauză aici

689
00:41:34,400 --> 00:41:38,790
și de a face apoi că în mod corespunzător.

690
00:41:38,790 --> 00:41:46,020
Bine. Am setat povestea destul de artificial acolo

691
00:41:46,020 --> 00:41:48,670
prin alegerea Alice si Bob, apoi, apoi Charlie și apoi Anita,

692
00:41:48,670 --> 00:41:51,000
al cărui nume a fost, evident, de gând să se ciocnesc cu Alice.

693
00:41:51,000 --> 00:41:54,120
Dar întrebarea pe care am ajuns, luni, cu cat este doar probabilă este

694
00:41:54,120 --> 00:41:56,370
pe care le-ar obține aceste tipuri de coliziuni? Cu alte cuvinte,

695
00:41:56,370 --> 00:42:00,490
în cazul în care vom începe să utilizați această structură de tabel, care este de fapt doar o matrice,

696
00:42:00,490 --> 00:42:02,460
în acest caz, de 26 de locații,

697
00:42:02,460 --> 00:42:05,740
Ce se întâmplă dacă intrări noastre sunt distribuite uniform în loc?

698
00:42:05,740 --> 00:42:09,620
Nu e artificial Alice si Bob și Charlie și David și așa mai departe în ordine alfabetică,

699
00:42:09,620 --> 00:42:12,380
este repartizată în mod uniform de la A la Z.

700
00:42:12,380 --> 00:42:15,220
>> Poate vom avea noroc si nu vom avea două O să lui sau două a lui B

701
00:42:15,220 --> 00:42:17,640
cu o probabilitate foarte mare, dar ca cineva a subliniat,

702
00:42:17,640 --> 00:42:20,730
dacă am generalizat această problemă și nu 0 - 25

703
00:42:20,730 --> 00:42:26,060
dar, spune, 0 prin 364 sau 65, de multe ori numărul de zile într-un an tipic,

704
00:42:26,060 --> 00:42:31,170
și a cerut întrebare, "Care este probabilitatea ca noi doi în această cameră au aceeași zi de naștere?"

705
00:42:31,170 --> 00:42:34,600
Pune-i o altă cale, care e probabilitatea ca noi doi avem un nume începând cu A?

706
00:42:34,600 --> 00:42:37,190
Un fel de întrebare este același, dar acest lucru spațiu de adrese,

707
00:42:37,190 --> 00:42:39,940
acest spațiu de căutare, este mai mare în cazul aniversari,

708
00:42:39,940 --> 00:42:42,820
pentru că avem atât de mult mai multe zile în an decat litere din alfabet.

709
00:42:42,820 --> 00:42:44,910
Care este probabilitatea unei coliziuni?

710
00:42:44,910 --> 00:42:48,410
Ei bine, ne putem gândi la acest lucru prin imaginind matematica sens opus.

711
00:42:48,410 --> 00:42:50,580
Care este probabilitatea de a nu coliziuni?

712
00:42:50,580 --> 00:42:53,970
Ei bine, această expresie aici, spune că ceea ce este probabilitatea

713
00:42:53,970 --> 00:42:58,770
dacă există doar o singură persoană în această cameră, că au o zi de naștere unic?

714
00:42:58,770 --> 00:43:01,190
E 100%. Pentru că dacă nu există decât o singură persoană în cameră,

715
00:43:01,190 --> 00:43:03,940
lui sau ziua ei de naștere poate fi oricare dintre cele 365 de zile din an.

716
00:43:03,940 --> 00:43:08,650
Deci, opțiunile de 365/365 dă-mi o valoare de 1.

717
00:43:08,650 --> 00:43:11,250
Deci, probabilitatea în cauză, la moment este doar 1.

718
00:43:11,250 --> 00:43:13,270
Dar dacă există oa doua persoană în cameră,

719
00:43:13,270 --> 00:43:16,490
ce e probabilitatea ca ziua de nastere a acestora este diferit?

720
00:43:16,490 --> 00:43:20,680
Nu e doar 364 zile posibile, ignorând ani bisecți,

721
00:43:20,680 --> 00:43:23,580
pentru ziua lor de a nu intra în coliziune cu alte persoane.

722
00:43:23,580 --> 00:43:31,920
Deci, 364/365. În cazul în care o terță persoană vine în, e 363/365, și așa mai departe.

723
00:43:31,920 --> 00:43:35,790
Așa că am păstra înmulțirea acestor fracțiuni, care devin mai mici și mai mici,

724
00:43:35,790 --> 00:43:40,720
să dau seama ce este probabilitatea ca toți dintre noi au aniversari unice?

725
00:43:40,720 --> 00:43:43,570
Dar atunci putem, desigur, să ia doar ca răspuns și întoarceți-l în jurul valorii de

726
00:43:43,570 --> 00:43:47,210
și de a face un minus toate că, o expresie vom ajunge în cele din urmă

727
00:43:47,210 --> 00:43:51,250
dacă vă amintiți din spate a cărților de matematică, se pare ceva de acest fel,

728
00:43:51,250 --> 00:43:54,590
care este mult mai ușor de interpretat grafic.

729
00:43:54,590 --> 00:43:57,820
Și acest grafic aici are pe axa x numărul de aniversari,

730
00:43:57,820 --> 00:44:02,030
sau numărul de persoane cu aniversari, și pe axa y este probabilitatea unui meci.

731
00:44:02,030 --> 00:44:06,060
Și ce acest lucru este să spun este că, dacă aveți, să zicem, chiar,

732
00:44:06,060 --> 00:44:10,860
hai să aleagă ceva de genul 22, 23.

733
00:44:10,860 --> 00:44:13,160
Dacă e 22 sau 23 de persoane în cameră,

734
00:44:13,160 --> 00:44:17,100
probabilitatea ca doi dintre acei oameni foarte puține sunt de gând să aibă aceeași zi de naștere

735
00:44:17,100 --> 00:44:19,560
este de fapt super-mare, combinatorially.

736
00:44:19,560 --> 00:44:23,450
50% cote că într-o clasă de doar 22 de persoane, un seminar, practic,

737
00:44:23,450 --> 00:44:25,790
2 dintre aceste persoane sunt de gând să aibă aceeași zi de naștere.

738
00:44:25,790 --> 00:44:28,520
Pentru că există atât de multe moduri în care puteți avea aceeași zi de naștere.

739
00:44:28,520 --> 00:44:31,110
Chiar mai rău, dacă te uiți la partea dreaptă a diagramei,

740
00:44:31,110 --> 00:44:34,040
de timpul pe care îl aveți o clasă cu 58 de elevi în ea,

741
00:44:34,040 --> 00:44:39,270
probabilitatea de 2 persoane au ziua de nastere este mare super, super, aproape 100%.

742
00:44:39,270 --> 00:44:41,880
Acum, că e un fel de fapt amuzant despre viața reală.

743
00:44:41,880 --> 00:44:45,850
>> Dar implicațiile, acum, pentru structuri de date și stocare a informațiilor

744
00:44:45,850 --> 00:44:51,100
înseamnă că doar presupunând că aveți un frumos, curat de distribuție, uniformă a datelor

745
00:44:51,100 --> 00:44:53,650
și aveți o gamă destul de mare pentru a se potrivi o grămadă de lucruri

746
00:44:53,650 --> 00:44:59,360
nu înseamnă că ai de gând să obțineți de oameni in locatii unice.

747
00:44:59,360 --> 00:45:03,810
Vei avea coliziuni. Deci, această noțiune de hashing, cum e numit,

748
00:45:03,810 --> 00:45:07,450
ținând seama de o intrare ca "Alice", și masaj-l într-un fel

749
00:45:07,450 --> 00:45:10,190
și apoi revenind un răspuns cum ar fi 0 sau 1 sau 2.

750
00:45:10,190 --> 00:45:17,500
Noțiuni de bază înapoi o parte din producția această funcție este afectat de această probabilitate de coliziune.

751
00:45:17,500 --> 00:45:19,530
Deci, cum putem descurca acele coliziuni?

752
00:45:19,530 --> 00:45:21,940
Ei bine, de la un caz, putem lua ideea că a fost sugerat.

753
00:45:21,940 --> 00:45:25,100
Ne putem schimba doar toata lumea jos, sau poate, pur și simplu, un pic mai mult,

754
00:45:25,100 --> 00:45:29,870
mai degrabă decât oricine altcineva mișcare, să mergem doar la Anita partea de jos a locului disponibil.

755
00:45:29,870 --> 00:45:32,810
Deci, în cazul în care Alice este în 0, Bob este în 1, Charlie este în 2,

756
00:45:32,810 --> 00:45:35,260
vom pune în locul în care Anita 3.

757
00:45:35,260 --> 00:45:38,860
Și aceasta este o tehnica in structuri de date numit liniară palpare.

758
00:45:38,860 --> 00:45:41,310
Liniară pentru că te plimbi doar această linie, și tu ești un fel de palpare

759
00:45:41,310 --> 00:45:43,640
pentru locuri disponibile în structura de date.

760
00:45:43,640 --> 00:45:46,210
Desigur, aceasta revine în O (n).

761
00:45:46,210 --> 00:45:49,590
În cazul în care structura de date este într-adevăr plin, e 25 de oameni în ea deja,

762
00:45:49,590 --> 00:45:54,120
și apoi Anita vine, ea se termină până la ceea ce ar fi locația Z, și asta e bine.

763
00:45:54,120 --> 00:45:56,540
Ea încă se potrivește, și putem so găsim mai târziu.

764
00:45:56,540 --> 00:46:00,100
>> Dar acest lucru a fost contrară obiectivului de accelerarea lucrurile.

765
00:46:00,100 --> 00:46:02,530
Și ce dacă am introdus, în schimb această a treia dimensiune?

766
00:46:02,530 --> 00:46:06,400
Această tehnică se numește, în general, înlănțuirea separată, sau cu lanturi.

767
00:46:06,400 --> 00:46:10,030
Și ce-un tabel hash este acum, această structură de tabel,

768
00:46:10,030 --> 00:46:13,450
tabelul este doar un tablou de pointeri.

769
00:46:13,450 --> 00:46:18,230
Dar ceea ce aceste indicii indica este ghici ce?

770
00:46:18,230 --> 00:46:21,970
O listă legate. Și ce dacă luăm cea mai bună a acestor două lumi?

771
00:46:21,970 --> 00:46:26,500
Noi folosim matrice pentru indicii inițiale

772
00:46:26,500 --> 00:46:32,070
în structura de date astfel încât să putem merge instantaneu de la [0] [1], [30] sau așa mai departe,

773
00:46:32,070 --> 00:46:36,480
dar astfel încât să avem o oarecare flexibilitate si putem potrivi Anita și Alice și Adam

774
00:46:36,480 --> 00:46:38,630
precum și orice alte Un nume,

775
00:46:38,630 --> 00:46:43,470
lăsăm în schimb alte axe cresc arbitrar.

776
00:46:43,470 --> 00:46:47,340
Și, în cele din urmă am, începând de luni, au capacitatea de expresiv că cu lista legat.

777
00:46:47,340 --> 00:46:49,530
Putem crește o structură de date arbitrar.

778
00:46:49,530 --> 00:46:52,450
Alternativ, am putea face doar un imens 2-dimensionale matrice,

779
00:46:52,450 --> 00:46:57,190
dar asta va fi o situație îngrozitoare, dacă unul dintre rânduri dintr-o matrice 2-dimensional

780
00:46:57,190 --> 00:47:01,280
nu este suficient de mare pentru persoana suplimentară al cărei nume se întâmplă pentru a începe cu A.

781
00:47:01,280 --> 00:47:04,200
Doamne ferește, avem de a realoca un imens 2-dimensionale structura

782
00:47:04,200 --> 00:47:06,600
doar pentru că există atât de mulți oameni, a numit un

783
00:47:06,600 --> 00:47:09,480
mai ales atunci când există atât de puțini oameni cu numele Z ceva.

784
00:47:09,480 --> 00:47:12,170
E doar de gând să fie un foarte rare structură de date.

785
00:47:12,170 --> 00:47:15,400
Deci nu e perfect prin orice mijloace, dar acum avem cel puțin au capacitatea de

786
00:47:15,400 --> 00:47:19,090
pentru a găsi instantaneu în cazul în care Alice sau Anita aparține,

787
00:47:19,090 --> 00:47:21,090
cel puțin în ceea ce privește axa verticală,

788
00:47:21,090 --> 00:47:25,850
și apoi trebuie doar să decidă în cazul în care pentru a pune Anita sau Alice în această listă legată.

789
00:47:25,850 --> 00:47:32,480
Dacă nu ne pasă de sortare lucruri, cât de repede am putea introduce Alice într-o structură ca asta?

790
00:47:32,480 --> 00:47:35,370
E timpul constanta. Noi indicele în [0], iar în cazul în care nu există nici o cuiva,

791
00:47:35,370 --> 00:47:37,550
Alice merge la începutul acestei liste legate.

792
00:47:37,550 --> 00:47:40,000
Dar asta nu e o afacere uriașă. Pentru că dacă Anita apoi vine de-a lungul

793
00:47:40,000 --> 00:47:42,160
un numar de pasi mai târziu, în cazul în care nu aparține Anita?

794
00:47:42,160 --> 00:47:45,140
Ei bine, [0]. OOP. Alice este deja în această listă legată.

795
00:47:45,140 --> 00:47:47,760
>> Dar dacă nu ne pasă de sortare aceste nume,

796
00:47:47,760 --> 00:47:53,580
ne putem muta pur și simplu peste Alice, inserați Anita, dar chiar că este constanta de timp.

797
00:47:53,580 --> 00:47:57,010
Chiar daca nu e Alice și Adam și toate aceste alte nume A,

798
00:47:57,010 --> 00:47:59,410
nu e într-adevăr le schimba fizic. De ce?

799
00:47:59,410 --> 00:48:04,090
Pentru că am făcut aici cu lista legate, care cunoaște aceste noduri au fost oricum sunt?

800
00:48:04,090 --> 00:48:06,550
Tot ce trebuie sa faci este sa treci de pesmet.

801
00:48:06,550 --> 00:48:10,930
Mutare în jurul valorii de săgețile, nu trebuie să se deplaseze fizic orice date în jurul valorii de.

802
00:48:10,930 --> 00:48:14,610
Deci, putem insera Anita, în acest caz, instantaneu. Constantă de timp.

803
00:48:14,610 --> 00:48:20,250
Deci avem constantă timp de căutare, și constantă în timp inserarea de cineva ca Anita.

804
00:48:20,250 --> 00:48:22,740
Dar un fel de a simplifica lumii.

805
00:48:22,740 --> 00:48:28,510
Ce se întâmplă dacă am mai târziu doriți să găsiți Alice?

806
00:48:28,510 --> 00:48:31,050
Ce se întâmplă dacă am mai târziu doriți să găsiți Alice?

807
00:48:31,050 --> 00:48:35,690
Câți pași se că va dura?

808
00:48:35,690 --> 00:48:37,850
[Răspuns Student, neinteligibil]

809
00:48:37,850 --> 00:48:40,950
Exact. Numărul de persoane înainte de Alice în lista de legat.

810
00:48:40,950 --> 00:48:45,420
Deci, nu e destul de perfect, pentru că structura noastră de date, din nou, are acest acces pe verticală

811
00:48:45,420 --> 00:48:50,240
și apoi are aceste liste linked suspendate - de fapt, să nu-l trage o matrice o.

812
00:48:50,240 --> 00:48:56,020
Acesta a acestor liste legate agățat jos de pe ea, care arata ceva de genul asta.

813
00:48:56,020 --> 00:48:59,110
Dar problema este dacă Alice și Adam și toate aceste alte nume A

814
00:48:59,110 --> 00:49:01,720
ajung mai mult și mai mult acolo,

815
00:49:01,720 --> 00:49:04,810
găsirea cineva ar putea sfârșesc prin a lua o grămadă de pași,

816
00:49:04,810 --> 00:49:06,670
bcause trebuie să traverseze lista de legat,

817
00:49:06,670 --> 00:49:08,090
care este o operație liniară.

818
00:49:08,090 --> 00:49:14,270
Deci într-adevăr, atunci, în cele din urmă de timp inserare este O (n), unde n este numărul de elemente din listă.

819
00:49:14,270 --> 00:49:21,780
Împărțit de, hai să numim aceasta arbitrar m, unde m este numărul de liste legate

820
00:49:21,780 --> 00:49:24,500
pe care o avem în această axă verticală.

821
00:49:24,500 --> 00:49:27,180
Cu alte cuvinte, daca ne asumam cu adevarat o distribuție uniformă de nume,

822
00:49:27,180 --> 00:49:30,150
total nerealiste. Există, evident, mai mult de câteva scrisori decât altele.

823
00:49:30,150 --> 00:49:32,580
>> Dar dacă presupunem, pentru moment, o distribuție uniformă,

824
00:49:32,580 --> 00:49:37,350
și ne-am n totalul persoanelor, și lanțuri m totale

825
00:49:37,350 --> 00:49:40,630
disponibile pentru noi, atunci durata de fiecare dintre aceste lanțuri

826
00:49:40,630 --> 00:49:44,380
destul de simplu va fi totală, n împărțit la numărul de lanțuri.

827
00:49:44,380 --> 00:49:48,900
Deci, N / m. Dar aici e în cazul în care putem fi cu toții matematic inteligent.

828
00:49:48,900 --> 00:49:53,030
m este o constantă, pentru că există un număr fix de acestea.

829
00:49:53,030 --> 00:49:54,620
Ai de gând să declare matrice la început,

830
00:49:54,620 --> 00:49:58,450
și nu suntem redimensionarea axei verticale. Prin definiție, care rămâne fixat.

831
00:49:58,450 --> 00:50:01,220
E doar axa orizontală, ca să spunem așa, care este schimbarea.

832
00:50:01,220 --> 00:50:04,760
Deci punct de vedere tehnic, acest lucru este o constantă. Deci, acum, inserarea de timp

833
00:50:04,760 --> 00:50:09,700
Este destul de mult O (n).

834
00:50:09,700 --> 00:50:12,410
Așa că nu se simte tot atât de mult mai bine.

835
00:50:12,410 --> 00:50:14,940
Dar ceea ce este adevărul aici? Ei bine, în tot acest timp, de săptămâni,

836
00:50:14,940 --> 00:50:20,640
am spus O (n ²). O (n), 2 x N ², - n, împărțit la 2. . . ech.

837
00:50:20,640 --> 00:50:23,580
E doar ² n. Dar acum, în această parte a semestrului,

838
00:50:23,580 --> 00:50:25,560
putem începem să vorbim despre lumea reală din nou.

839
00:50:25,560 --> 00:50:31,520
Și n / m este absolut mai rapid decât n pace.

840
00:50:31,520 --> 00:50:35,170
Dacă aveți o mie de nume, și le rupe în sus, în compartimente multiple

841
00:50:35,170 --> 00:50:37,820
astfel încât să aveți doar zece nume din fiecare dintre aceste lanțuri,

842
00:50:37,820 --> 00:50:41,670
căutarea absolut zece lucruri va fi mai rapid decât o mie de lucruri.

843
00:50:41,670 --> 00:50:43,740
Și astfel unul din seturile de probleme viitoare este de gând să vă provocare

844
00:50:43,740 --> 00:50:46,100
să se gândească exact că, deși, da,

845
00:50:46,100 --> 00:50:49,520
asimptotic și matematic, acest lucru este încă doar liniar,

846
00:50:49,520 --> 00:50:51,700
care e de rahat, în general, atunci când încearcă să găsească lucruri.

847
00:50:51,700 --> 00:50:54,530
În realitate, aceasta va fi mai rapid decât cel

848
00:50:54,530 --> 00:50:56,520
din aceasta cauza divizor.

849
00:50:56,520 --> 00:50:58,310
Și deci nu e din nou va fi acest compromis

850
00:50:58,310 --> 00:51:01,390
și acest conflict între teorie și realitate,

851
00:51:01,390 --> 00:51:03,550
și unul dintre butoanele va începe de cotitură în acest moment, în semestrul

852
00:51:03,550 --> 00:51:07,510
este mai mult de realitate, o așa cum am un fel de pregătiți pentru sfârșitul lui semster,

853
00:51:07,510 --> 00:51:09,280
cum vom introduce lumea de programare web,

854
00:51:09,280 --> 00:51:11,530
în cazul în care într-adevăr, performanța va conta, deoarece utilizatorii sunt de gând să

855
00:51:11,530 --> 00:51:14,880
începe să se simtă și să aprecieze decizii proaste de proiectare.

856
00:51:14,880 --> 00:51:19,950
>> Deci, cum te duci despre punerea în aplicare a unui legat - un tabel hash cu 31 de elemente?

857
00:51:19,950 --> 00:51:22,600
Și exemplul anterior a fost arbitrar despre aniversari.

858
00:51:22,600 --> 00:51:26,190
Dacă cineva are o zi de naștere de la 1 ianuarie sau februarie 1, le vom pune în acest galeata.

859
00:51:26,190 --> 00:51:28,960
Dacă e 02 ianuarie, 2 februarie, 2 martie, le vom pune în acest galeata.

860
00:51:28,960 --> 00:51:32,220
Asta e motivul pentru care a fost de 31. Cum vă declara un tabel hash?

861
00:51:32,220 --> 00:51:37,480
Ea poate fi destul de simplu, de masă * nod este numele meu arbitrar pentru aceasta, [31].

862
00:51:37,480 --> 00:51:42,400
Acest lucru îmi dă 31 pointeri la noduri,

863
00:51:42,400 --> 00:51:45,370
și care îmi permite să aibă 31 pointeri la preturi legate de

864
00:51:45,370 --> 00:51:48,800
chiar dacă aceste lanțuri sunt inițial NULL.

865
00:51:48,800 --> 00:51:54,860
Ce vreau să afișezi dacă vreau să stocați "Alice", "Bob", "Charlie"?

866
00:51:54,860 --> 00:51:57,010
Ei bine, avem nevoie să-și încheie aceste lucruri într-o structură

867
00:51:57,010 --> 00:52:00,530
pentru că avem nevoie de Alice la punctul lui Bob, pentru a indica Charlie, și așa mai departe.

868
00:52:00,530 --> 00:52:04,940
Noi nu putem avea doar numele singur, așa că am putea crea o nouă structură numită nod aici.

869
00:52:04,940 --> 00:52:08,310
>> Ce este un nod real? Ce este un nod în această listă nouă legat?

870
00:52:08,310 --> 00:52:11,840
Primul lucru, numit cuvânt, este pentru numele persoanei.

871
00:52:11,840 --> 00:52:14,340
LUNGIME, probabil, se referă la lungimea maximă a numelui unui om,

872
00:52:14,340 --> 00:52:18,210
indiferent de faptul că este, 20, 30, 40 de caractere în cazuri de colt nebun,

873
00:52:18,210 --> 00:52:22,680
și +1 este pentru ce? E doar caracterul NULL plus, \ 0.

874
00:52:22,680 --> 00:52:27,410
Deci, acest nod este împachetarea "ceva" in interiorul de la sine,

875
00:52:27,410 --> 00:52:29,640
dar, de asemenea, declară un pointer numit următoare

876
00:52:29,640 --> 00:52:32,580
astfel încât să putem lanțul de Alice la Bob să Charlie și așa mai departe.

877
00:52:32,580 --> 00:52:36,700
Poate fi NULL, dar nu trebuie neapărat să fie.

878
00:52:36,700 --> 00:52:40,110
Orice întrebări cu privire la aceste tabele de dispersie? Da?

879
00:52:40,110 --> 00:52:46,190
[Student cere întrebare, neinteligibil] O matrice - întrebare bună.

880
00:52:46,190 --> 00:52:50,120
De ce este acest cuvânt char într-o matrice, mai degrabă decât doar char *?

881
00:52:50,120 --> 00:52:53,830
În acest exemplu oarecum arbitrară, nu am vrut să aibă de a recurge

882
00:52:53,830 --> 00:52:56,190
la malloc pentru fiecare dintre numele originale.

883
00:52:56,190 --> 00:52:59,530
Am vrut să declare o sumă maximă de memorie pentru șirul

884
00:52:59,530 --> 00:53:06,020
astfel încât am putut copia în structura Alice \ 0 și nu trebuie să se confrunte cu malloc și gratuit și similar.

885
00:53:06,020 --> 00:53:11,710
Dar am putea face asta dacă aș fi vrut să fie mai conștienți de utilizarea spațiului. Bună întrebare.

886
00:53:11,710 --> 00:53:14,780
Deci, haideți să încercăm să generalizeze departe de acest

887
00:53:14,780 --> 00:53:18,350
și să se concentreze pe restul de astăzi, în general, mai multe structuri de date

888
00:53:18,350 --> 00:53:21,170
și alte probleme pe care le pot rezolva folosind aceleași fundamente

889
00:53:21,170 --> 00:53:24,590
chiar dacă structurile de date se pot diferi în datele lor.

890
00:53:24,590 --> 00:53:27,910
>> Deci, se dovedește în informatică, copacii sunt foarte frecvente.

891
00:53:27,910 --> 00:53:29,760
Și vă puteți gândi la un fel de copac ca un arbore genealogic,

892
00:53:29,760 --> 00:53:31,830
în cazul în care există unele rădăcini, unele matriarch sau patriarh,

893
00:53:31,830 --> 00:53:34,540
bunica sau bunicul sau mai devreme spate,

894
00:53:34,540 --> 00:53:38,880
sub care sunt mama și tata sau frații sau diverse place.

895
00:53:38,880 --> 00:53:42,500
Deci, o structură arborescentă are noduri si are copii,

896
00:53:42,500 --> 00:53:45,260
de obicei 0 sau mai multe copii pentru fiecare nod.

897
00:53:45,260 --> 00:53:47,320
Și unii dintre jargon pe care le vedeți în această imagine aici

898
00:53:47,320 --> 00:53:50,630
este oricare dintre copiii mici sau nepoții pe marginile

899
00:53:50,630 --> 00:53:52,330
care nu au săgeți care provin de la ei,

900
00:53:52,330 --> 00:53:55,070
acestea sunt frunzele așa-numitele, și oricine de pe interior

901
00:53:55,070 --> 00:53:58,790
este un nod interior; puteți apela acest ceva de-a lungul acestor linii.

902
00:53:58,790 --> 00:54:01,430
Dar această structură este destul de comună. Asta e un pic arbitrar.

903
00:54:01,430 --> 00:54:04,930
Avem un copil pe stânga, avem trei copii de pe dreapta,

904
00:54:04,930 --> 00:54:06,830
doi copii de pe partea din stânga jos.

905
00:54:06,830 --> 00:54:10,740
Astfel încât să putem avea diferite dimensiuni copaci, dar dacă vom începe să standardizeze lucruri,

906
00:54:10,740 --> 00:54:15,330
și s-ar putea aminti acest videoclip de la Patrick în binar de căutare de pe o anterior

907
00:54:15,330 --> 00:54:19,490
căutare on-line, binare nu trebuie să fie puse în aplicare cu o matrice

908
00:54:19,490 --> 00:54:21,410
sau bucăți de hârtie pe o tablă.

909
00:54:21,410 --> 00:54:25,490
Să presupunem că ai vrut să stocați numere intr-o structura mai sofisticată de date.

910
00:54:25,490 --> 00:54:27,680
Ai putea crea un copac ca asta.

911
00:54:27,680 --> 00:54:35,290
Ai putea avea un nod declarată în C, iar acel nod poate avea cel puțin două elemente în interiorul de ea.

912
00:54:35,290 --> 00:54:39,470
Unul este numărul pe care doriți să stocați, iar cealaltă este - ei bine, avem nevoie de unul mai mult.

913
00:54:39,470 --> 00:54:41,540
Cealaltă este copiilor săi.

914
00:54:41,540 --> 00:54:45,150
Deci, aici e altă structură de date. De data aceasta, un nod este definit ca stocarea unui număr n

915
00:54:45,150 --> 00:54:49,060
și apoi doi pointeri, copil stânga și dreapta copil.

916
00:54:49,060 --> 00:54:52,100
Și nu sunt arbitrare. Ce este interesant despre acest copac?

917
00:54:52,100 --> 00:55:00,550
>> Care e modelul în modul în care ne-am stabilit asta sau cum Patrick, aceasta este prevăzut în filme lui?

918
00:55:00,550 --> 00:55:02,790
E un fel de evident că există unele sortare întâmplă pe aici,

919
00:55:02,790 --> 00:55:04,460
dar ceea ce e regula simpla? Da?

920
00:55:04,460 --> 00:55:08,350
[Răspuns Student, neinteligibil]

921
00:55:08,350 --> 00:55:12,040
Eveniment. Dacă vă arunca o privire la acest lucru, veți vedea numerele de mici de pe partea stângă,

922
00:55:12,040 --> 00:55:14,690
Numerele mari de pe partea stângă, dar asta e valabil pentru fiecare nod.

923
00:55:14,690 --> 00:55:20,370
Pentru fiecare nod, copilul său din stânga mai puțin de ea, și copilul său drept mai mare decât acesta.

924
00:55:20,370 --> 00:55:25,210
Ce înseamnă acest lucru este acum dacă vreau să căutați această structură de date pentru, să zicem, numărul 44,

925
00:55:25,210 --> 00:55:29,320
Trebuie să înceapă de la rădăcină, pentru că așa cum, cu toate aceste structuri mai complexe de date acum,

926
00:55:29,320 --> 00:55:31,910
avem doar un pointer la un singur lucru, la început.

927
00:55:31,910 --> 00:55:35,010
Și în acest caz, începutul este radacina. Nu e capătul din stânga,

928
00:55:35,010 --> 00:55:39,530
e rădăcina acestei structuri. Vad ca aici e 55, iar eu caut 44.

929
00:55:39,530 --> 00:55:41,430
În ce direcție vreau să merg?

930
00:55:41,430 --> 00:55:45,680
Ei bine, eu vreau să merg la stânga, pentru că în mod evident, la dreapta va fi prea mare.

931
00:55:45,680 --> 00:55:49,050
Deci observați aici, tu ești un fel de tocare conceptual copac în jumătate

932
00:55:49,050 --> 00:55:51,700
pentru că nu sunteți niciodată merge în jos pe partea dreaptă.

933
00:55:51,700 --> 00:55:55,410
Așa că acum mă duc la 55 la 33. E prea mic al unui număr.

934
00:55:55,410 --> 00:56:01,590
Caut 44, dar acum știu că dacă 44 este, în acest copac, pot merge, evident, la dreapta.

935
00:56:01,590 --> 00:56:04,460
Deci, din nou, eu sunt tăierea copac în jumătate.

936
00:56:04,460 --> 00:56:06,780
E destul de mult identice conceptual la cartea de telefon.

937
00:56:06,780 --> 00:56:09,510
Este identic cu ceea ce am făcut cu lucrările de pe tablă,

938
00:56:09,510 --> 00:56:13,940
dar este o structura mult mai sofisticat, care ne permite să facem efectiv

939
00:56:13,940 --> 00:56:16,880
acest dezbina si cucereste prin proiectarea algoritmului,

940
00:56:16,880 --> 00:56:19,420
și, de fapt, traverseaza o structura ca asta - Ups.

941
00:56:19,420 --> 00:56:22,870
Traversarea unei structuri de acest fel, în cazul în care e doar "du-te acest fel sau du-te în acest fel,"

942
00:56:22,870 --> 00:56:26,870
înseamnă că tot codul care îndoit mintea ta la început atunci când la punctul de punere în aplicare

943
00:56:26,870 --> 00:56:31,270
sau mers pe jos prin ea acasă, pentru căutare binară, folosind recursivitate sau iterație,

944
00:56:31,270 --> 00:56:35,060
este o durere în gât. Găsiți elementul din mijloc, apoi alegeți rotunjirea în sus sau în jos.

945
00:56:35,060 --> 00:56:39,230
>> E o frumusete la acest lucru, deoarece putem folosi acum recursivitate din nou,

946
00:56:39,230 --> 00:56:43,760
dar mult mai curat. Într-adevăr, dacă ești la numărul 55 și doriți să găsiți 44,

947
00:56:43,760 --> 00:56:48,450
te duci lăsat în acest caz, atunci ce faci? Puteti rula algoritm exact același.

948
00:56:48,450 --> 00:56:51,560
Ai verificat valoarea de nod, apoi te duci la stânga sau la dreapta.

949
00:56:51,560 --> 00:56:53,670
Apoi, verificați valoarea nodului, du-te la stânga sau la dreapta.

950
00:56:53,670 --> 00:56:56,710
Acest lucru este perfect potrivit pentru recursia.

951
00:56:56,710 --> 00:57:00,920
Deci, chiar dacă, în trecut, am făcut câteva exemple destul de arbitrare care implică recursivitate

952
00:57:00,920 --> 00:57:03,430
care nu au nevoie să fie recursiv, cu stuctures de date,

953
00:57:03,430 --> 00:57:07,820
mai ales copaci, este o aplicare perfecta a acestei idei de a lua o problemă,

954
00:57:07,820 --> 00:57:12,920
scădere el, și apoi rezolvarea același tip de, dar mai mici, programul.

955
00:57:12,920 --> 00:57:14,590
>> Deci, există o altă structură de date pe care le pot introduce.

956
00:57:14,590 --> 00:57:18,760
Acesta este conceput la prima vedere, să se uite criptic, dar asta e uimitor.

957
00:57:18,760 --> 00:57:25,090
Deci, aceasta este o structura de date numita trie, trie, care este moștenit de la recuperarea cuvântul,

958
00:57:25,090 --> 00:57:30,210
care nu se pronunță re-try-val, dar asta e ceea ce lumea numește aceste lucruri. Incearca. T-r-i-e.

959
00:57:30,210 --> 00:57:35,190
Este o structură arborescentă de un anumit fel, dar fiecare dintre noduri într-un trie

960
00:57:35,190 --> 00:57:41,280
pare a fi ceea ce? Și aceasta este un pic înșelătoare, pentru că e un fel de prescurtate.

961
00:57:41,280 --> 00:57:45,960
Dar se pare ca fiecare nod din acest trie este de fapt o matrice.

962
00:57:45,960 --> 00:57:48,840
Și chiar dacă autorul această diagramă nu le-a arătat,

963
00:57:48,840 --> 00:57:54,130
în acest caz, această trie este o structura de date al cărui scop în viață este de a stoca cuvinte

964
00:57:54,130 --> 00:57:57,330
cum ar fi A-L-i-c-e sau B-o-b.

965
00:57:57,330 --> 00:58:02,480
Și modul în care aceste date la magazine de Alice si Bob și Charlie și Anita și așa mai departe

966
00:58:02,480 --> 00:58:06,970
se foloseste o matrice prin care pentru a stoca Alice într-un trie,

967
00:58:06,970 --> 00:58:09,820
vom începe de la nodul rădăcină, care arata ca o matrice,

968
00:58:09,820 --> 00:58:12,080
și că a fost scrisă în notație stenografie.

969
00:58:12,080 --> 00:58:15,070
Autorul a omis abcdefg, deoarece nu au nici un nume cu asta.

970
00:58:15,070 --> 00:58:19,150
Ei au aratat numai M și P și T, dar în acest caz,

971
00:58:19,150 --> 00:58:22,780
Să se mute departe de Alice si Bob și Charlie unor nume care sunt aici.

972
00:58:22,780 --> 00:58:25,670
Maxwell este, de fapt, în această diagramă.

973
00:58:25,670 --> 00:58:29,570
Deci, cum a făcut magazin autorul M-o-x-w-e-l-am?

974
00:58:29,570 --> 00:58:36,990
El sau ea a început la nodul rădăcină, și sa dus la [M], deci aproximativ 13, 13, în locația matrice.

975
00:58:36,990 --> 00:58:40,750
Apoi de acolo, e un pointer.

976
00:58:40,750 --> 00:58:42,760
Un pointer care să conducă la o altă matrice.

977
00:58:42,760 --> 00:58:47,880
De acolo autorul indexate în care matrice în locul A, astfel cum este descris acolo la stânga sus,

978
00:58:47,880 --> 00:58:52,250
și atunci el sau ea a urmat un alt pointer la matrice,

979
00:58:52,250 --> 00:58:55,460
și a mers la indicatorul la locatia X.

980
00:58:55,460 --> 00:58:59,840
Apoi, în următoarea locație matrice W, E, L, L, și așa mai departe,

981
00:58:59,840 --> 00:59:03,090
și, în sfârșit, să încercăm de fapt, de a pune o imagine la acest lucru.

982
00:59:03,090 --> 00:59:05,380
Ce face un aspect nod ca în codul?

983
00:59:05,380 --> 00:59:11,820
Un nod într-un trie conține o serie de indicatori către mai multe noduri.

984
00:59:11,820 --> 00:59:16,090
Dar există, de asemenea, trebuie să fie un fel de valoare boolean, cel puțin în această punere în aplicare.

985
00:59:16,090 --> 00:59:18,770
I se întâmplă să-l numesc is_word. De ce?

986
00:59:18,770 --> 00:59:22,670
Pentru că atunci când ești introducerea Maxwell, nu ești inserarea

987
00:59:22,670 --> 00:59:25,300
nimic în această structură de date.

988
00:59:25,300 --> 00:59:27,480
Tu nu scrii M. Tu nu scrii X.

989
00:59:27,480 --> 00:59:30,240
Tot ce faci este în urma pointeri.

990
00:59:30,240 --> 00:59:33,360
Indicatorul care reprezintă M, atunci indicatorul care reprezintă o,

991
00:59:33,360 --> 00:59:36,310
atunci indicatorul care reprezintă X, apoi W, E, L, L,

992
00:59:36,310 --> 00:59:41,950
dar ceea ce trebuie să facă la sfârșitul este un fel de du-te, verifica, am ajuns la această locație.

993
00:59:41,950 --> 00:59:45,560
Nu a fost un cuvânt care se încheie aici, în structura de date.

994
00:59:45,560 --> 00:59:48,190
>> Deci, ceea ce este cu adevărat un trie umplut cu și autorul a ales să reprezinte

995
00:59:48,190 --> 00:59:51,880
aceste terminuses cu triunghiuri mici.

996
00:59:51,880 --> 00:59:56,470
Acest lucru înseamnă doar că faptul acestui triunghi e aici, această valoare boolean de adevărate

997
00:59:56,470 --> 00:59:59,200
înseamnă că, dacă te duci înapoi în copac,

998
00:59:59,200 --> 01:00:02,420
ceea ce înseamnă un cuvânt numit Maxwell este în acest sens.

999
01:00:02,420 --> 01:00:04,870
Dar cuvântul foo, de exemplu,

1000
01:00:04,870 --> 01:00:07,970
nu este în copac, pentru că dacă am începe de la nodul rădăcină până aici, la partea de sus,

1001
01:00:07,970 --> 01:00:14,030
Nu e nici indicatorul f, nu indicatorul o, nu o indicatorul. Foo nu este un nume în acest dicționar.

1002
01:00:14,030 --> 01:00:22,460
Dar, prin contrast, Turing, T-u-r-i-n-g. Din nou, nu am păstra t sau u sau r sau I sau N sau g..

1003
01:00:22,460 --> 01:00:29,820
Dar am făcut-o în magazinul această structură de date o valoare de adevărata cale până aici, în acest nod - în copac

1004
01:00:29,820 --> 01:00:33,030
prin setarea acestei valori boolean a is_word la true.

1005
01:00:33,030 --> 01:00:35,740
Deci, un trie este un fel de meta acestei structuri foarte interesant,

1006
01:00:35,740 --> 01:00:39,810
în cazul în care nu ești într-adevăr stocarea cuvintele ei înșiși pentru acest tip de dicționar.

1007
01:00:39,810 --> 01:00:45,100
Pentru a fi clar, esti doar stocarea da sau nu, există un cuvânt care se termină aici.

1008
01:00:45,100 --> 01:00:46,430
>> Acum, ce e implicație?

1009
01:00:46,430 --> 01:00:51,120
Dacă aveți 150,000 cuvinte într-un dicționar care sunteți încercarea de a stoca în memorie

1010
01:00:51,120 --> 01:00:53,400
folosind ceva de genul o listă legată,

1011
01:00:53,400 --> 01:00:56,870
aveți de gând să aibă 150000 noduri în lista dvs. de legat.

1012
01:00:56,870 --> 01:01:00,250
Și de a găsi unul dintre aceste cuvinte ar putea lua în ordine alfabetică O (n).

1013
01:01:00,250 --> 01:01:04,370
Liniară de timp. Dar, în cazul aici un trie,

1014
01:01:04,370 --> 01:01:09,210
ceea ce este timpul de rulare a găsi un cuvânt?

1015
01:01:09,210 --> 01:01:17,390
Se pare că frumusețea este că, chiar dacă aveți deja 149,999 cuvinte, în acest dicționar,

1016
01:01:17,390 --> 01:01:20,170
puse în aplicare cu aceasta structura de date,

1017
01:01:20,170 --> 01:01:25,560
cât de mult timp este nevoie pentru a găsi o persoană sau inserați mai mult în faptul că, la fel ca Alice, Alice?

1018
01:01:25,560 --> 01:01:30,640
Ei bine, e doar 5, poate 6 pasi pentru caracter la final.

1019
01:01:30,640 --> 01:01:32,880
Din cauza presense de alte nume din structura

1020
01:01:32,880 --> 01:01:35,340
nu intra in modul de inserare Alice.

1021
01:01:35,340 --> 01:01:39,640
Mai mult decât atât, găsirea Alice o dată acolo sunt 150,000 cuvinte în acest dicționar

1022
01:01:39,640 --> 01:01:41,960
nu lua in drumul tau de a găsi Alice, la toate,

1023
01:01:41,960 --> 01:01:46,880
pentru ca Alice este. . . . . aici, pentru că am găsit o valoare boolean.

1024
01:01:46,880 --> 01:01:50,920
Și dacă nu există nici un boolean adevărat, atunci Alice nu este în această structură de date de cuvinte.

1025
01:01:50,920 --> 01:01:56,220
Cu alte cuvinte, timpul de rulare a găsi lucruri și inserarea lucruri în această nouă

1026
01:01:56,220 --> 01:02:01,920
Structura de date a trie este O a - nu e n.

1027
01:02:01,920 --> 01:02:05,730
Din cauza presense de 150.000 de oameni nu are nici un efect asupra Alice, se pare.

1028
01:02:05,730 --> 01:02:11,560
Deci, hai să spunem k, unde k este lungimea maximă a unui cuvânt în limba engleză

1029
01:02:11,560 --> 01:02:14,050
care este de obicei nu mai mult de 20 si ceva de caractere.

1030
01:02:14,050 --> 01:02:17,940
Deci, k este o constantă. Deci, Sfântul Graal se pare că am găsit acum

1031
01:02:17,940 --> 01:02:26,000
este faptul că de un timp trie, constanta pentru inserții, pentru căutările, pentru ștergeri.

1032
01:02:26,000 --> 01:02:29,170
Deoarece numărul de lucruri deja în structura,

1033
01:02:29,170 --> 01:02:32,600
care nu sunt chiar fizic acolo. Din nou, acestea sunt sortați doar de verificat off, da sau nu,

1034
01:02:32,600 --> 01:02:35,050
nu are nici un impact asupra acesteia timp de funcționare în viitor.

1035
01:02:35,050 --> 01:02:37,940
>> Dar nu trebuie sa fie o captură, altfel nu ne-ar fi pierdut atât de mult timp

1036
01:02:37,940 --> 01:02:41,460
cu privire la toate aceste structuri alte date doar pentru a ajunge în cele din urmă la un secret care este uimitor.

1037
01:02:41,460 --> 01:02:46,410
Deci, ce preț plătim pentru a realiza acest lucru măreția aici? Spațiu.

1038
01:02:46,410 --> 01:02:49,010
Acest lucru este masiv. Și motivul pentru care autorul

1039
01:02:49,010 --> 01:02:52,400
nu l prezinte aici, observăm că toate aceste lucruri care arata ca matrice,

1040
01:02:52,400 --> 01:02:55,400
el nu a trage restul de copac, restul trie,

1041
01:02:55,400 --> 01:02:58,060
pentru că ei nu sunt doar relevante pentru poveste.

1042
01:02:58,060 --> 01:03:01,870
Dar toate aceste noduri sunt super largi, și fiecare nod din arbore preia

1043
01:03:01,870 --> 01:03:07,780
26 sau, de fapt, ar putea fi 27 de caractere, deoarece, în acest caz, am fost, inclusiv spațiu pentru apostrof

1044
01:03:07,780 --> 01:03:09,980
astfel încât să putem avea cuvinte apostrophized.

1045
01:03:09,980 --> 01:03:14,450
În acest caz, acestea sunt tablouri mari. Deci, chiar dacă ei nu sunt picutured,

1046
01:03:14,450 --> 01:03:18,190
aceasta ia o cantitate masivă de memorie RAM.

1047
01:03:18,190 --> 01:03:20,670
Care ar putea fi bine, especilly în hardware modernă,

1048
01:03:20,670 --> 01:03:25,650
dar asta e compromisul. Vom ajunge mai putin timp de a petrece mai mult spațiu.

1049
01:03:25,650 --> 01:03:28,580
Deci, în cazul în care se întâmplă toate astea?

1050
01:03:28,580 --> 01:03:32,640
Ei bine, hai să facem - să vedem aici.

1051
01:03:32,640 --> 01:03:39,510
Să facem un salt la tipul ăsta aici.

1052
01:03:39,510 --> 01:03:43,450
>> Credeti sau nu, distractiv la fel de mult ca și C a fost de ceva timp acum,

1053
01:03:43,450 --> 01:03:48,130
suntem atingerea punctului în semestrul în care este timpul să treceți la lucruri mai moderne.

1054
01:03:48,130 --> 01:03:50,950
Lucrurile pe un nivel superior. Și chiar dacă pentru următoarele două săptămâni

1055
01:03:50,950 --> 01:03:54,580
vom continua să ne cufunda în lumea de indicii și de gestionare a memoriei

1056
01:03:54,580 --> 01:03:57,210
pentru a obține că mângâierea cu care putem construi apoi pe,

1057
01:03:57,210 --> 01:04:01,270
Jocul final este în cele din urmă să se introducă, în mod ironic, nu această limbă.

1058
01:04:01,270 --> 01:04:03,330
Vom petrece, cam 10 minute vorbind despre HTML.

1059
01:04:03,330 --> 01:04:05,950
Toate HTML este este un limbaj de marcare, și ceea ce este un limbaj de marcare

1060
01:04:05,950 --> 01:04:10,220
aceste serii este de paranteze deschise și închise brațe care spun că "face acest îndrăzneț"

1061
01:04:10,220 --> 01:04:12,000
"Face acest cursive" "face acest centrat."

1062
01:04:12,000 --> 01:04:14,250
Nu e tot ce intelectual interesant, dar e foarte util.

1063
01:04:14,250 --> 01:04:16,650
Și e cu siguranță omniprezent în aceste zile.

1064
01:04:16,650 --> 01:04:19,450
Dar ceea ce este puternic despre lumea de HTML, si programare web, în ​​general, mai mult,

1065
01:04:19,450 --> 01:04:25,910
este construirea lucruri dinamice; scrierea de cod în limbaje cum ar fi PHP sau Python sau Ruby sau Java sau C #.

1066
01:04:25,910 --> 01:04:30,360
Într-adevăr, indiferent de limba dvs. de alegere este, și generând HTML dinamic.

1067
01:04:30,360 --> 01:04:32,960
Generarea ceva numit CSS dinamic.

1068
01:04:32,960 --> 01:04:35,810
Cascading Style Sheets, care este, de asemenea, despre estetica.

1069
01:04:35,810 --> 01:04:41,360
Și astfel, chiar dacă, astăzi, dacă mă duc la unele site ca Google.com familiar,

1070
01:04:41,360 --> 01:04:46,100
și mă duc pentru a vizualiza, dezvoltator, sursa de vedere, pe care poate le-ați făcut înainte,

1071
01:04:46,100 --> 01:04:49,800
dar merge pentru a vedea sursa, chestia asta pare destul de probabil criptic.

1072
01:04:49,800 --> 01:04:55,320
Dar acest lucru este cod de bază care implementează Google.com.

1073
01:04:55,320 --> 01:04:57,940
Pe partea din fata. Și de fapt, toate acestea sunt lucruri pufoase estetica.

1074
01:04:57,940 --> 01:05:01,740
Acest lucru este CSS aici. Dacă am ține de defilare în jos vom obține unele chestii de culori diferite.

1075
01:05:01,740 --> 01:05:06,890
Acest lucru este HTML. Codul de Google arata ca un dezastru, dar dacă am deschide de fapt o altă fereastră,

1076
01:05:06,890 --> 01:05:09,380
putem vedea unele structuri la acest lucru.

1077
01:05:09,380 --> 01:05:12,640
Dacă aș deschide acest sus, observați aici, e un pic mai ușor de citit.

1078
01:05:12,640 --> 01:05:16,850
Vom vedea în scurt timp această etichetă, [cuvântul] este o etichetă,

1079
01:05:16,850 --> 01:05:23,520
HTML, cap, corp, div, script-ul, zona de text, durata, centrat, div.

1080
01:05:23,520 --> 01:05:26,770
Și acest lucru este, de asemenea, sorta de criptic cu aspect de la prima vedere,

1081
01:05:26,770 --> 01:05:30,890
dar toate mizeria asta urmeaza anumite tipare, modele și repetabile,

1082
01:05:30,890 --> 01:05:33,850
astfel că, odată ce vom obține elementele de bază în jos, vei fi capabil de a scrie cod ca acest

1083
01:05:33,850 --> 01:05:37,550
și manipula apoi cod ca acest lucru utilizând un alt limbaj, numit JavaScript.

1084
01:05:37,550 --> 01:05:40,440
Și JavaScript este un limbaj care rulează în interiorul unui browser

1085
01:05:40,440 --> 01:05:44,380
astăzi că vom folosi pe cursurile de la Harvard, pentru instrumentul de cumpărături curs care utilizează Google Maps

1086
01:05:44,380 --> 01:05:48,660
pentru a vă oferi o gramada de dinamism, Facebook vă oferă pentru a vedea actualizările de stare instant,

1087
01:05:48,660 --> 01:05:51,430
Stare de nervozitate îl folosește pentru a vă arăta tweets instantaneu.

1088
01:05:51,430 --> 01:05:53,820
Toate acestea vom începe să ne cufunda inch

1089
01:05:53,820 --> 01:05:57,190
Dar pentru a ajunge acolo, avem nevoie să înțelegem ceva despre internet.

1090
01:05:57,190 --> 01:06:01,130
Acest clip aici este doar un minut lung, și să presupunem pentru moment acest lucru este, de fapt,

1091
01:06:01,130 --> 01:06:08,380
cum Internetul funcționează ca un teaser pentru ceea ce e pe cale să vină. Eu vă dau "Warriors of Net."

1092
01:06:08,380 --> 01:06:14,720
>> [♫ Muzica ♫ Slow cor]

1093
01:06:14,720 --> 01:06:20,450
[Naratorul Barbat] El a venit cu un mesaj.

1094
01:06:20,450 --> 01:06:23,770
Cu un protocol de tot lui.

1095
01:06:23,770 --> 01:06:37,270
[♫ muzica electronica mai repede ♫]

1096
01:06:37,270 --> 01:06:41,330
El a venit într-o lume de firewall-uri interesante, nepăsător routere,

1097
01:06:41,330 --> 01:06:45,690
și pericolele mult mai rele decât moartea.

1098
01:06:45,690 --> 01:06:55,400
E rapid. E puternic. E TCP / IP, și el are adresa ta.

1099
01:06:55,400 --> 01:06:59,250
Warriors of Net.

1100
01:06:59,250 --> 01:07:05,290
[Malan] Săptămâna viitoare, atunci. Internetul. Programare web. Acest lucru este CS50.

1101
01:07:05,290 --> 01:07:08,290
[CS50.TV]