1
00:00:00,000 --> 00:00:02,520
[Powered by Google Translate] [Setmana 6, continuació]

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

3
00:00:04,160 --> 00:00:08,720
[Aquesta és CS50.] [CS50.TV]

4
00:00:08,720 --> 00:00:12,970
Això és CS50 i aquest és el cap de setmana 6.

5
00:00:12,970 --> 00:00:17,970
Així CS50x, un dels primers cursos de Harvard que participen en la iniciativa EDX

6
00:00:17,970 --> 00:00:20,590
de fet va debutar aquest passat dilluns.

7
00:00:20,590 --> 00:00:23,460
Si a vostè li agradaria fer una ullada al que altres en Internet

8
00:00:23,460 --> 00:00:27,180
estan seguint juntament amb, vostè pot dirigir-se a x.cs50.net.

9
00:00:27,180 --> 00:00:30,350
Això li redirigirà al lloc apropiat en edx.org,

10
00:00:30,350 --> 00:00:34,160
que era on aquest i altres cursos del MIT i Berkeley ara vivim.

11
00:00:34,160 --> 00:00:38,140
Vostè haurà de registrar-se per obtenir un compte, trobareu que el material és en gran part el mateix

12
00:00:38,140 --> 00:00:42,170
com vostè ha tingut aquest semestre, encara que un parell de setmanes amb retard, ja que tenir tot llest.

13
00:00:42,170 --> 00:00:46,930
Però el que els estudiants en CS50x ara es veu és una interfície bastant com aquest.

14
00:00:46,930 --> 00:00:50,040
Això, per exemple, és Zamyla liderant el conjunt de problemes pas a pas per 0.

15
00:00:50,040 --> 00:00:54,230
En iniciar la sessió en edx.org, un estudiant CS50x veu el tipus de coses

16
00:00:54,230 --> 00:00:57,170
vostè esperaria veure en un curs: la conferència per al dilluns,

17
00:00:57,170 --> 00:01:01,650
conferència per al dimecres, diversos curtmetratges, els butlletins de problemes, els tutorials, arxius PDF.

18
00:01:01,650 --> 00:01:04,459
A més, com vostè veu aquí, les traduccions automàtiques

19
00:01:04,459 --> 00:01:08,390
de les transcripcions anglès al xinès, japonès, espanyol, italià,

20
00:01:08,390 --> 00:01:12,810
i un munt d'altres llengües que sens dubte serà imperfecta

21
00:01:12,810 --> 00:01:15,840
tal com les desplegar mitjançant programació amb una cosa que es diu una API,

22
00:01:15,840 --> 00:01:18,360
o interfície de programació d'aplicacions, des de Google

23
00:01:18,360 --> 00:01:21,360
que ens permet convertir Anglès a altres idiomes.

24
00:01:21,360 --> 00:01:24,100
Però gràcies al meravellós esperit d'alguns voluntaris més de cent,

25
00:01:24,100 --> 00:01:26,940
persones a l'atzar a Internet que han ofert amablement a participar

26
00:01:26,940 --> 00:01:30,180
en aquest projecte, que poc a poc va a millorar la qualitat de les traduccions

27
00:01:30,180 --> 00:01:35,790
fent que els humans corregir els errors que els nostres equips han fet.

28
00:01:35,790 --> 00:01:42,330
>> Així que resulta que hi havia uns quants estudiants més aparèixer dilluns del que inicialment s'esperava.

29
00:01:42,330 --> 00:01:48,980
De fet, ara CS50x té 100.000 persones al llarg dels següents a casa.

30
00:01:48,980 --> 00:01:54,430
Llavors s'adona que tots som part d'aquesta classe inaugural de fer aquest curs en ciències de la computació

31
00:01:54,430 --> 00:01:57,370
educació en general, de manera més àmplia i accessible.

32
00:01:57,370 --> 00:02:00,130
I la realitat és ara, amb alguns d'aquests cursos en línia massius,

33
00:02:00,130 --> 00:02:04,070
tots ells comencen amb aquests nombres molt alts, com sembla que hem fet aquí.

34
00:02:04,070 --> 00:02:08,759
Però l'objectiu, en última instància, per CS50x és realment fer que la gent com molts fins a la meta com sigui possible.

35
00:02:08,759 --> 00:02:12,000
Pel seu disseny, CS50x serà ofert des de dilluns passat

36
00:02:12,000 --> 00:02:17,430
fins el 15 d'abril de 2013, per la qual cosa les persones que tenen compromisos escolars en altres parts,

37
00:02:17,430 --> 00:02:20,990
treball, família, altres conflictes i similars, tenen una mica més de flexibilitat

38
00:02:20,990 --> 00:02:23,640
amb la qual submergir-se en aquest curs, que, n'hi ha prou amb dir,

39
00:02:23,640 --> 00:02:30,540
és bastant ambiciosa fet si només en el transcurs de només tres mesos durant un semestre normal.

40
00:02:30,540 --> 00:02:34,190
No obstant això, aquests estudiants seran fer front als butlletins de problemes mateixos, veient el mateix contingut,

41
00:02:34,190 --> 00:02:36,350
tenir accés als mateixos pantalons curts i similars.

42
00:02:36,350 --> 00:02:38,990
Així que adonar-se que tots som veritablement junts en això.

43
00:02:38,990 --> 00:02:42,360
I un dels objectius finals de CS50x no és només per a la gent com molts

44
00:02:42,360 --> 00:02:45,720
a la línia de meta i donar-los aquest nou coneixement de la informàtica

45
00:02:45,720 --> 00:02:49,000
i la programació, sinó també per fer que aquesta experiència compartida.

46
00:02:49,000 --> 00:02:52,010
Una de les característiques definitòries de 50 al campus, així ho esperem,

47
00:02:52,010 --> 00:02:56,260
ha estat aquest tipus d'experiència comú, per bé o per mal, de vegades,

48
00:02:56,260 --> 00:02:59,480
però tenint aquestes persones es tornin cap a l'esquerra i cap a la dreta,

49
00:02:59,480 --> 00:03:01,830
i hores d'oficina i el hackathon i la fira.

50
00:03:01,830 --> 00:03:04,560
És una mica més difícil que fer-ho en persona amb amics en línia,

51
00:03:04,560 --> 00:03:10,580
però CS50x conclourà a l'abril amb la primera CS50 Expo,

52
00:03:10,580 --> 00:03:13,630
que serà una adaptació en línia de la nostra idea de la fira

53
00:03:13,630 --> 00:03:18,250
on aquests milers d'estudiants de tot seran convidats a presentar un 1 - a 2 minuts de vídeo,

54
00:03:18,250 --> 00:03:22,480
ja sigui un screencast del seu projecte final o vídeo d'ells agitant hola

55
00:03:22,480 --> 00:03:24,490
i parlant del seu projecte i li donem,

56
00:03:24,490 --> 00:03:27,610
igual que els seus predecessors han fet aquí al campus de la fira,

57
00:03:27,610 --> 00:03:31,400
de manera que per al final del semestre, s'espera tenir una exposició mundial

58
00:03:31,400 --> 00:03:37,080
dels projectes dels estudiants CS50x 'finals, molt semblant a la que li espera aquest mes de desembre al campus.

59
00:03:37,080 --> 00:03:39,680
Així que més que en els pròxims mesos.

60
00:03:39,680 --> 00:03:43,640
>> Amb 100.000 estudiants, però, ve la necessitat d'un CAS mica més.

61
00:03:43,640 --> 00:03:47,590
Tenint en compte que vostès estan obrint el camí aquí i prenent CS50

62
00:03:47,590 --> 00:03:51,630
diverses setmanes abans del llançament d'aquest material a la gent en EDX,

63
00:03:51,630 --> 00:03:55,330
adonem que li encantaria participar ja que molts dels nostres estudiants com sigui possible en aquesta iniciativa,

64
00:03:55,330 --> 00:03:58,720
tant durant el semestre d'hivern, així com aquesta i la propera primavera.

65
00:03:58,720 --> 00:04:01,620
Així que si vol participar en CS50x,

66
00:04:01,620 --> 00:04:07,450
particularment en unir-se a CS50x tractar, la versió de EDX CS50 Discussió,

67
00:04:07,450 --> 00:04:10,140
que molts de vostès s'han estat utilitzant al campus, al tauler d'anuncis en línia,

68
00:04:10,140 --> 00:04:13,040
si us plau cap a aquesta URL, sabrem qui ets,

69
00:04:13,040 --> 00:04:16,450
perquè ens encantaria construir un equip d'estudiants i professors i el personal per igual

70
00:04:16,450 --> 00:04:19,630
al campus que estan simplement jugant bé i ajudant.

71
00:04:19,630 --> 00:04:21,720
I quan veuen a una qüestió que és familiar per a ells,

72
00:04:21,720 --> 00:04:25,320
que escolti un estudiant informar algun error en algun lloc allà fora en algun país a Internet,

73
00:04:25,320 --> 00:04:27,450
i que sona una campana, ja que també tenia aquest mateix nombre

74
00:04:27,450 --> 00:04:32,620
si d-hall fa algun temps, és d'esperar llavors vostè pot ficar la seva cullera i compartir la seva pròpia experiència.

75
00:04:32,620 --> 00:04:37,300
Així que si us plau participar si li agradaria.

76
00:04:37,300 --> 00:04:39,360
>> Cursos de ciències de la computació a la Universitat de Harvard té una mica d'una tradició,

77
00:04:39,360 --> 00:04:44,730
CS50 entre ells, de tenir una mica de roba, una mica de roba, que es pot portar amb orgull

78
00:04:44,730 --> 00:04:49,090
al final del semestre, dient molt orgullós d'haver acabat CS50

79
00:04:49,090 --> 00:04:51,830
i va prendre CS50 i similars, i sempre intentem involucrar els estudiants

80
00:04:51,830 --> 00:04:54,540
en aquest procés tant com sigui possible, mitjançant el qual convidem,

81
00:04:54,540 --> 00:04:56,900
en aquesta època del semestre, els estudiants a presentar els seus dissenys

82
00:04:56,900 --> 00:04:59,330
l'ús de Photoshop, o qualsevol eina de selecció que voleu utilitzar

83
00:04:59,330 --> 00:05:02,330
si ets un dissenyador, a presentar els seus dissenys per a samarretes i dessuadores

84
00:05:02,330 --> 00:05:06,100
i para-sols i mocadors per a gossos petits que ara tenim i similars.

85
00:05:06,100 --> 00:05:09,370
I tot és llavors - els guanyadors de cada any després es va exhibir

86
00:05:09,370 --> 00:05:12,700
a la pàgina web de l'assignatura en store.cs50.net.

87
00:05:12,700 --> 00:05:15,790
Tot el que es ven a un cost allà, però el lloc web només en si funciona

88
00:05:15,790 --> 00:05:18,330
i permet a les persones triar els colors i dissenys que els agraden.

89
00:05:18,330 --> 00:05:20,420
Així que vaig pensar que acabàvem de compartir alguns dels dissenys de l'any passat

90
00:05:20,420 --> 00:05:25,130
que eren al lloc web, a més d'aquest d'aquí, que és una tradició anual.

91
00:05:25,130 --> 00:05:29,410
"Cada dia estic Seg Faultn" va ser una de les presentacions de l'any passat,

92
00:05:29,410 --> 00:05:32,290
que encara es troba allà per antics alumnes.

93
00:05:32,290 --> 00:05:35,820
Hem tingut aquest ", CS50, Established 1989".

94
00:05:35,820 --> 00:05:39,010
Un dels nostres Bowdens, Rob, era molt popular l'any passat.

95
00:05:39,010 --> 00:05:43,480
"Equip de Bowden" va néixer, aquest disseny va ser presentat, entre els més venuts.

96
00:05:43,480 --> 00:05:49,040
Igual que aquest d'aquí. Molta gent tenia "febre Bowden", d'acord amb els registres de vendes.

97
00:05:49,040 --> 00:05:52,650
Donar-se compte del que ara podria ser el disseny d'aquí, a Internet.

98
00:05:52,650 --> 00:05:57,510
Més detalls sobre aquest problema al següent estableix per venir.

99
00:05:57,510 --> 00:06:00,330
>> Una de les eines més: vostè ha tingut alguna exposició i espero que ara

100
00:06:00,330 --> 00:06:02,350
una mica d'experiència pràctica amb GDB,

101
00:06:02,350 --> 00:06:04,570
que és, per descomptat, un depurador i permet manipular

102
00:06:04,570 --> 00:06:09,500
seu programa a un nivell bastant baix, fent que tipus de coses?

103
00:06:09,500 --> 00:06:13,030
Què GDB permeten fer?

104
00:06:13,030 --> 00:06:15,030
Sí? Dóna'm alguna cosa. [Resposta Estudiantil, inintel · ligible]

105
00:06:15,030 --> 00:06:18,120
Bé. Entre en la funció, de manera que no només cal escriure run

106
00:06:18,120 --> 00:06:22,310
i tenen el cop programa a través del seu totalitat, la impressió de les coses a la sortida estàndard.

107
00:06:22,310 --> 00:06:25,190
Més aviat, vostè pot caminar a través de línia per línia, ja sigui escrivint proper

108
00:06:25,190 --> 00:06:30,300
a anar línia per línia a línia o pas a submergir-se en una funció, típicament un que vostè va escriure.

109
00:06:30,300 --> 00:06:35,240
Què més fa el BGF li permeten fer? Sí? [Resposta Estudiantil, inintel · ligible]

110
00:06:35,240 --> 00:06:38,100
Imprimir variables. Així que si vostè vol fer una mica d'introspecció dins del seu programa de

111
00:06:38,100 --> 00:06:41,500
sense haver de recórrer a escriure sentències printf per tot el lloc,

112
00:06:41,500 --> 00:06:44,600
vostè pot imprimir una variable o mostrar una variable.

113
00:06:44,600 --> 00:06:46,710
Què més es pot fer amb un depurador GDB com?

114
00:06:46,710 --> 00:06:49,170
[Resposta Estudiantil, inintel · ligible]

115
00:06:49,170 --> 00:06:52,080
Exactament. Pot establir punts d'interrupció, es pot dir que l'execució descans

116
00:06:52,080 --> 00:06:54,020
en la funció principal o la funció foo.

117
00:06:54,020 --> 00:06:56,800
Es pot dir que l'execució de descans a la línia 123.

118
00:06:56,800 --> 00:06:58,950
I els punts d'interrupció són una tècnica molt poderosa

119
00:06:58,950 --> 00:07:01,110
perquè si vostè té una idea general d'on és el seu problema

120
00:07:01,110 --> 00:07:05,360
probablement és, vostè no ha de perdre temps passant a través de la totalitat del programa.

121
00:07:05,360 --> 00:07:08,250
Vostè pot essencialment saltar allà i comenci a escriure -

122
00:07:08,250 --> 00:07:10,970
pas a pas a través d'ell amb el pas o el següent o similar.

123
00:07:10,970 --> 00:07:14,340
Però el problema amb alguna cosa com GDB és que t'ajuda, els recursos humans,

124
00:07:14,340 --> 00:07:16,940
trobar els seus problemes i trobar els seus errors.

125
00:07:16,940 --> 00:07:19,470
No necessàriament trobar tant per tu.

126
00:07:19,470 --> 00:07:23,070
>> Així es va introduir el style50 altre dia, que és una eina de línia de comandes curt

127
00:07:23,070 --> 00:07:27,500
que tracta de estilitzar el seu codi una mica més net que tu, l'ésser humà, podria haver fet.

128
00:07:27,500 --> 00:07:29,530
Però això, també, és en realitat una cosa estètica.

129
00:07:29,530 --> 00:07:34,110
Però resulta que hi ha aquesta altra eina anomenada Valgrind que és una mica més arcà d'usar.

130
00:07:34,110 --> 00:07:36,860
La seva sortida és atroçment críptic a primera vista.

131
00:07:36,860 --> 00:07:39,420
Però és meravellosament útil, sobretot ara que estem en la part del terme

132
00:07:39,420 --> 00:07:43,080
on vas a començar a utilitzar malloc i l'assignació de memòria dinàmica.

133
00:07:43,080 --> 00:07:45,420
Les coses poden anar molt, molt malament ràpidament.

134
00:07:45,420 --> 00:07:49,320
Perquè si vostè s'oblida d'alliberar la seva memòria, o deixa de fer referència punter NULL,

135
00:07:49,320 --> 00:07:55,770
o deixa de fer referència punter d'escombraries, el que sol ser el símptoma que els resultats?

136
00:07:55,770 --> 00:07:59,470
Seg culpa. I s'obté l'arxiu base d'una certa quantitat de kilobytes o megabytes

137
00:07:59,470 --> 00:08:02,990
que representa l'estat de la memòria del programa, quan es va estavellar,

138
00:08:02,990 --> 00:08:05,730
però en última instància, el seu programa segons falles, falla de segmentació,

139
00:08:05,730 --> 00:08:08,450
el que significa que alguna cosa dolenta ha passat gairebé sempre relacionats

140
00:08:08,450 --> 00:08:11,750
a un error relacionat amb la memòria que vostè ha fet en algun lloc.

141
00:08:11,750 --> 00:08:14,100
Així Valgrind ajuda a trobar coses com aquesta.

142
00:08:14,100 --> 00:08:17,720
És una eina que s'executa, com GDB, després d'haver compilat el programa,

143
00:08:17,720 --> 00:08:20,330
però en lloc d'executar el programa directament, es corre Valgrind

144
00:08:20,330 --> 00:08:23,960
i es passa al seu programa, tal com ho fa amb GDB.

145
00:08:23,960 --> 00:08:26,220
Ara, l'ús, per obtenir el millor tipus de sortida,

146
00:08:26,220 --> 00:08:30,410
és una mica llarg, així que aquí dalt de la pantalla veuràs Valgrind-v.

147
00:08:30,410 --> 00:08:35,350
"-V" gairebé universalment significa detallat quan vostè està utilitzant programes en un equip Linux.

148
00:08:35,350 --> 00:08:38,770
Per tant, significa escopir més dades que vostè pot ser que per defecte.

149
00:08:38,770 --> 00:08:45,510
"- Comprovar fugues = full." Això és només dir xec per totes les possibles pèrdues de memòria,

150
00:08:45,510 --> 00:08:49,430
errors que vaig poder haver fet. Això, també, és un paradigma comú amb els programes de Linux.

151
00:08:49,430 --> 00:08:52,710
En general, si vostè té un argument de línia d'ordres que és un "switch",

152
00:08:52,710 --> 00:08:55,830
que se suposa que per canviar el comportament del programa, i és una sola lletra,

153
00:08:55,830 --> 00:09:00,310
és-v, però si això canvia, només pel disseny del programador,

154
00:09:00,310 --> 00:09:05,150
és una paraula completa o una sèrie de paraules, l'argument de línia d'ordres s'inicia amb -.

155
00:09:05,150 --> 00:09:08,190
Aquests són només convencions humanes, però les veuràs cada vegada més.

156
00:09:08,190 --> 00:09:12,410
I després, finalment, "a.out" és el nom arbitrari per al programa en aquest exemple en particular.

157
00:09:12,410 --> 00:09:14,640
I aquí hi ha una sortida representativa.

158
00:09:14,640 --> 00:09:22,890
>> Abans de veure el que això significa, deixa anar a un fragment de codi per aquí.

159
00:09:22,890 --> 00:09:26,390
I m'ho dius a mi moure aquesta fora del camí, molt aviat,

160
00:09:26,390 --> 00:09:32,120
i anem a fer una ullada a memory.c, que és aquest petit exemple aquí.

161
00:09:32,120 --> 00:09:36,290
Així que en aquest programa, vull fer un zoom sobre les funcions i preguntes.

162
00:09:36,290 --> 00:09:39,430
Tenim una funció principal que crida a una funció, f,

163
00:09:39,430 --> 00:09:45,590
i llavors, què f procedir a fer, en anglès una mica tècnic?

164
00:09:45,590 --> 00:09:49,760
Què fa f procedir a fer?

165
00:09:49,760 --> 00:09:53,680
Què vaig a començar amb la línia 20, i la ubicació de l'estrella, no importa,

166
00:09:53,680 --> 00:09:56,720
però només vaig a ser coherents amb l'última conferència.

167
00:09:56,720 --> 00:09:59,910
Quina és la línia 20 és per a nosaltres? Al costat de mà esquerra. Anem a descompondre encara més.

168
00:09:59,910 --> 00:10:02,410
Int * x: què fer?

169
00:10:02,410 --> 00:10:04,940
Bé. Es declara un punter, i ara serem encara més tècnic.

170
00:10:04,940 --> 00:10:10,230
Què vol dir, molt concretament, per declarar un punter? Algú més?

171
00:10:10,230 --> 00:10:15,050
Sí? [Resposta Estudiantil, inintel · ligible] Massa lluny.

172
00:10:15,050 --> 00:10:17,060
Així que vostè està llegint a la dreta del signe igual.

173
00:10:17,060 --> 00:10:20,290
Anem a centrar-nos només en el costat esquerre, just a int * x.

174
00:10:20,290 --> 00:10:24,700
Això significa "declarar" un punter, però ara anem a bussejar més profund a aquesta definició.

175
00:10:24,700 --> 00:10:28,330
Què vol dir concretament, tècnicament significa? Sí?

176
00:10:28,330 --> 00:10:31,940
[Resposta Estudiantil, inintel · ligible]

177
00:10:31,940 --> 00:10:35,090
Bé. S'està preparant per guardar una direcció en la memòria.

178
00:10:35,090 --> 00:10:40,680
Bé. I anem a prendre un pas més enllà, és declarar una variable, x, que és de 32 bits.

179
00:10:40,680 --> 00:10:44,440
I jo sé que és de 32 bits perquè -?

180
00:10:44,440 --> 00:10:47,390
No és perquè és un int, perquè és un punter en aquest cas.

181
00:10:47,390 --> 00:10:49,650
La coincidència que és un i el mateix amb un int,

182
00:10:49,650 --> 00:10:51,970
però el fet que no és l'estrella no vol dir que és un punter

183
00:10:51,970 --> 00:10:57,300
i en l'aparell, com amb molts equips, però no tots, els punters són de 32 bits.

184
00:10:57,300 --> 00:11:01,850
El maquinari més modern, com els últims Macs, els últims ordinadors, pot tenir punters de 64 bits,

185
00:11:01,850 --> 00:11:04,160
però en l'aparell, aquestes coses són de 32 bits.

186
00:11:04,160 --> 00:11:08,380
Així que anem a estandarditzar en això. Més concretament, la història va així:

187
00:11:08,380 --> 00:11:10,820
Nosaltres "declarar" un punter, el que vol dir això?

188
00:11:10,820 --> 00:11:12,810
Ens preparem per emmagatzemar una adreça de memòria.

189
00:11:12,810 --> 00:11:15,530
Què significa això?

190
00:11:15,530 --> 00:11:19,810
Creem una variable anomenada x que ocupa 32 bits

191
00:11:19,810 --> 00:11:23,810
que aviat va a emmagatzemar la direcció d'un nombre enter.

192
00:11:23,810 --> 00:11:26,470
I això és probablement tan precisos com puguem.

193
00:11:26,470 --> 00:11:31,810
Està bé avançar a simplificar el món i dir declarar un punter anomenat x.

194
00:11:31,810 --> 00:11:35,380
Declara un punter, però adonar i entendre el que realment està passant

195
00:11:35,380 --> 00:11:38,490
fins i tot en tan sols aquests pocs caràcters.

196
00:11:38,490 --> 00:11:42,040
>> Ara, aquest és gairebé una mica més fàcil, encara que és una expressió més llarga.

197
00:11:42,040 --> 00:11:48,160
Llavors, què està fent això, això és ressaltada ara: "malloc (10 * sizeof (int));" Sí?

198
00:11:48,160 --> 00:11:52,350
[Resposta Estudiantil, inintel · ligible]

199
00:11:52,350 --> 00:11:58,250
Bé. I ho vaig a portar-hi. S'assigna una porció de memòria per a deu punts.

200
00:11:58,250 --> 00:12:02,190
I ara anem a bussejar una mica més profund, és l'assignació d'una part de la memòria per a deu punts.

201
00:12:02,190 --> 00:12:05,390
El que es malloc després tornar?

202
00:12:05,390 --> 00:12:10,390
La direcció d'aquest bloc, o, més concretament, la direcció del primer byte d'aquest bloc.

203
00:12:10,390 --> 00:12:14,080
Com llavors sóc el programador, per saber on és aquest tros de caps de memòria?

204
00:12:14,080 --> 00:12:18,340
Jo sé que és contigua. Malloc, per definició, li donarà una part contigua de la memòria.

205
00:12:18,340 --> 00:12:21,240
No hi ha espais en blanc. Vostè té accés a tots els bytes en aquest tros,

206
00:12:21,240 --> 00:12:26,760
esquena amb esquena amb esquena, però com puc saber on és el final d'aquest tros de memòria és?

207
00:12:26,760 --> 00:12:28,850
Quan s'utilitza malloc? [Resposta Estudiantil, inintel · ligible] Bé.

208
00:12:28,850 --> 00:12:30,670
No ho saps. Vostè ha de recordar.

209
00:12:30,670 --> 00:12:35,960
He de recordar que vaig fer servir el valor 10, i ni tan sols semblen haver fet això aquí.

210
00:12:35,960 --> 00:12:41,000
No obstant això, la responsabilitat recau enterament sobre mi. Strlen, que ens hem tornat una mica dependents de les cadenes,

211
00:12:41,000 --> 00:12:45,860
només funciona a causa d'aquesta convenció de tenir \ 0

212
00:12:45,860 --> 00:12:48,840
o aquest caràcter especial nul, NUL, al final d'una cadena.

213
00:12:48,840 --> 00:12:51,740
Això no es sosté per uns trossos arbitraris de la memòria.

214
00:12:51,740 --> 00:12:58,590
Tot depèn de vostè. Així que la línia 20, a continuació, assigna un tros de memòria

215
00:12:58,590 --> 00:13:02,590
que pot emmagatzemar deu números enters, i emmagatzema la direcció del primer byte

216
00:13:02,590 --> 00:13:05,610
d'aquest bloc de memòria en la variable x es diu.

217
00:13:05,610 --> 00:13:11,140
Ergo, que és un punter. Així que la línia 21, per desgràcia, va ser un error.

218
00:13:11,140 --> 00:13:16,110
Però primer, què està fent? Està dient botiga al lloc 10, 0 indexat,

219
00:13:16,110 --> 00:13:19,480
del bloc de memòria anomenat x el valor 0.

220
00:13:19,480 --> 00:13:21,510
>> Així explica un parell de coses estan succeint.

221
00:13:21,510 --> 00:13:25,420
Tot i que x és un punter, recuperarà un parell de setmanes

222
00:13:25,420 --> 00:13:29,440
que encara es pot utilitzar la notació quadrada estil-matriu suport.

223
00:13:29,440 --> 00:13:36,180
Perquè això és realment taquigrafia notació per l'aritmètica de punters més críptic de futur.

224
00:13:36,180 --> 00:13:40,320
on anàvem a fer alguna cosa com això: neu la x, mogui més de 10 punts,

225
00:13:40,320 --> 00:13:44,550
a continuació, anar-hi a qualsevol direcció s'emmagatzema en aquesta ubicació.

226
00:13:44,550 --> 00:13:48,090
Però, francament, això no és més atroç de llegir i sentir-se còmode amb.

227
00:13:48,090 --> 00:13:52,900
Així que el món sol utilitzar els claudàtors només perquè és molt més amigable per llegir.

228
00:13:52,900 --> 00:13:55,140
Però això és el que realment està passant sota la campana;

229
00:13:55,140 --> 00:13:58,190
x és una adreça no una matriu, per se.

230
00:13:58,190 --> 00:14:02,410
Així que aquest és l'emmagatzematge de 0 a lloc 10 en x.

231
00:14:02,410 --> 00:14:06,120
Per què és això dolent? Sí?

232
00:14:06,120 --> 00:14:17,370
[Resposta Estudiantil, inintel · ligible] Exactament.

233
00:14:17,370 --> 00:14:21,100
Només ens van assignar deu enters, però comptem des de 0 en programar en C,

234
00:14:21,100 --> 00:14:25,690
pel que té accés a la 0 1 2 3 4 5 6 7 8 9, però no 10.

235
00:14:25,690 --> 00:14:30,270
Així que, o el programa serà culpa seg o no ho és.

236
00:14:30,270 --> 00:14:32,900
No obstant això, no se sap ben bé, el que és una mena de comportament no determinista.

237
00:14:32,900 --> 00:14:35,600
Realment depèn de si tenim sort.

238
00:14:35,600 --> 00:14:40,650
Si resulta que el sistema operatiu no li importa si utilitzo aquest byte extra,

239
00:14:40,650 --> 00:14:43,360
tot i que no l'ha donat a mi, el meu programa no es pot bloquejar.

240
00:14:43,360 --> 00:14:46,780
És cru, té fallades, però és possible que no vegi aquest símptoma,

241
00:14:46,780 --> 00:14:48,960
o potser ho veig de tant en tant.

242
00:14:48,960 --> 00:14:51,230
Però la realitat és que l'error és, de fet, existeix.

243
00:14:51,230 --> 00:14:54,320
I és realment problemàtic si vostè ha escrit un programa que vols ser correcta,

244
00:14:54,320 --> 00:14:58,840
que ha venut el programa que la gent està utilitzant que cada de tant en tant es bloqueja

245
00:14:58,840 --> 00:15:02,450
perquè, és clar, això no és bo. De fet, si vostè té un telèfon Android o un iPhone

246
00:15:02,450 --> 00:15:05,550
i descarregar aplicacions en aquests dies, si vostè ha tingut alguna vegada una aplicació per deixar de fumar just,

247
00:15:05,550 --> 00:15:10,040
de sobte desapareix, que és gairebé sempre el resultat d'algun problema relacionat amb la memòria,

248
00:15:10,040 --> 00:15:12,830
de manera que el programador pota i anul · la la referència d'un punter

249
00:15:12,830 --> 00:15:18,670
que ell o ella no ha de tenir, i el resultat de iOS o Android és matar només el programa complet

250
00:15:18,670 --> 00:15:23,080
en lloc dels comportaments de risc definits o algun tipus de compromís de seguretat.

251
00:15:23,080 --> 00:15:25,950
>> Hi ha un error en aquest altre programa a part d'aquest.

252
00:15:25,950 --> 00:15:30,180
Què més he cagat en aquest programa?

253
00:15:30,180 --> 00:15:32,740
Jo no he practicat el que he predicat. Sí?

254
00:15:32,740 --> 00:15:34,760
[Resposta Estudiantil, inintel · ligible] Bé.

255
00:15:34,760 --> 00:15:36,880
No he alliberat la memòria. Així que la regla d'or ara

256
00:15:36,880 --> 00:15:43,150
ha de ser en qualsevol moment de cridar malloc, de trucar lliure quan hagi acabat d'usar aquesta memòria.

257
00:15:43,150 --> 00:15:45,610
Ara, quan anava jo a voler alliberar aquesta memòria?

258
00:15:45,610 --> 00:15:49,780
Probablement, assumint aquesta primera línia era correcta, m'agradaria fer-ho aquí.

259
00:15:49,780 --> 00:15:55,710
Perquè jo no podria, per exemple, ho fan aquí. Per què?

260
00:15:55,710 --> 00:15:57,860
Just fora del seu abast. Així que, encara que estem parlant de punters,

261
00:15:57,860 --> 00:16:04,830
aquesta és una setmana 2 o 3 qüestió, on x és només un abast dins de les claus on es va declarar.

262
00:16:04,830 --> 00:16:11,000
Així que definitivament no es pot alliberar allà. La meva única oportunitat d'alliberar és més o menys després de la línia 21.

263
00:16:11,000 --> 00:16:15,170
Aquest és un programa bastant senzill, era bastant fàcil una vegada que tipus de embolicar la seva ment

264
00:16:15,170 --> 00:16:17,870
entorn al que el programa està fent, on són els errors eren.

265
00:16:17,870 --> 00:16:20,500
I encara que no ho vaig veure al principi, esperem que sigui una mica obvi ara

266
00:16:20,500 --> 00:16:23,870
que aquests errors són bastant fàcil de resoldre i fer fàcilment.

267
00:16:23,870 --> 00:16:28,720
Però quan un programa té més de 12 línies de llarg, que és 50 línies, 100 línies de llarg,

268
00:16:28,720 --> 00:16:31,150
caminant pel codi línia per línia, pensar-hi, lògicament,

269
00:16:31,150 --> 00:16:35,110
És possible, però no gaire divertit de fer, constantment a la recerca d'errors,

270
00:16:35,110 --> 00:16:38,340
i també és difícil de fer, i és per això que una eina com Valgrind existeix.

271
00:16:38,340 --> 00:16:40,900
Deixin-me seguir endavant i fer això: m'ho dius a mi obrir la finestra de terminal,

272
00:16:40,900 --> 00:16:45,400
I no tinc prou amb executar la memòria, perquè la memòria sembla estar bé.

273
00:16:45,400 --> 00:16:49,180
Estic tenint sort. Que va a byte addicional al final de la matriu

274
00:16:49,180 --> 00:16:51,060
no sembla ser massa problemàtic.

275
00:16:51,060 --> 00:16:56,370
Però em deixa, però, fer una comprovació de validesa, la qual cosa significa per comprovar

276
00:16:56,370 --> 00:16:58,320
si és o no és realment correcte.

277
00:16:58,320 --> 00:17:04,690
>> Així que farem Valgrind-v - Fuga-check = complet,

278
00:17:04,690 --> 00:17:07,520
i després el nom del programa en aquest cas és la memòria, no a.out.

279
00:17:07,520 --> 00:17:10,760
Així que permetin-me anar endavant i fer-ho. Premeu Enter.

280
00:17:10,760 --> 00:17:14,109
Estimat Déu. Aquesta és la seva sortida, i això és el que he fet referència abans.

281
00:17:14,109 --> 00:17:17,550
Però, si aprens a llegir a través de tots els disbarats aquí,

282
00:17:17,550 --> 00:17:20,760
la major part d'aquesta producció és només de diagnòstic que no és tan interessant.

283
00:17:20,760 --> 00:17:24,829
El que l'ull realment vol estar buscant és qualsevol menció d'error o no vàlid.

284
00:17:24,829 --> 00:17:26,800
Paraules que suggereixen problemes.

285
00:17:26,800 --> 00:17:29,340
I, de fet, anem a veure el que va malament aquí baix.

286
00:17:29,340 --> 00:17:35,230
Tinc un resum d'algun tipus, "en ús a la sortida:. 40 bytes en blocs de 1"

287
00:17:35,230 --> 00:17:38,750
No estic realment segur del que un bloc és encara, però 40 bytes

288
00:17:38,750 --> 00:17:41,260
en realitat se sent com si pogués esbrinar on que ve.

289
00:17:41,260 --> 00:17:45,030
40 bytes. Per què són de 40 bytes en ús a la sortida?

290
00:17:45,030 --> 00:17:48,780
I més concretament, si ens desplacem fins aquí,

291
00:17:48,780 --> 00:17:54,520
Per què he perdut definitivament 40 bytes? Sí?

292
00:17:54,520 --> 00:17:59,520
[Resposta Estudiantil, inintel · ligible] Perfect. Sí, exactament.

293
00:17:59,520 --> 00:18:03,540
Hi havia deu números enters, i cada un d'ells és la mida de 4, o 32 bits,

294
00:18:03,540 --> 00:18:08,300
així que he perdut 40 bytes precisament perquè, com vostè proposa, no he anomenat lliure.

295
00:18:08,300 --> 00:18:13,460
Això és un error, i ara anem a mirar cap avall una mica més i veure al costat d'aquest,

296
00:18:13,460 --> 00:18:16,900
"No vàlid escriure de mida 4". Ara, què és això?

297
00:18:16,900 --> 00:18:21,150
Aquesta adreça s'expressa el que la notació de base, pel que sembla?

298
00:18:21,150 --> 00:18:23,640
Això és hexadecimal, i cada vegada que veu un nombre que comença amb 0x,

299
00:18:23,640 --> 00:18:29,410
significa hexadecimal, el que vam fer allà per, crec, conjunt de processadors 0 a la secció de preguntes,

300
00:18:29,410 --> 00:18:34,090
que era només per fer un exercici d'escalfament, la conversió de decimal a hexadecimal a binari i així successivament.

301
00:18:34,090 --> 00:18:39,220
Hexadecimal, només per convenció humana, generalment s'utilitza per representar els punters

302
00:18:39,220 --> 00:18:41,570
o, més generalment, es dirigeix. És només una convenció,

303
00:18:41,570 --> 00:18:45,340
perquè és una mica més fàcil de llegir, que és una mica més compacte que alguna cosa com decimal,

304
00:18:45,340 --> 00:18:47,720
i binari és inútil per a la majoria dels éssers humans per al seu ús.

305
00:18:47,720 --> 00:18:50,840
I ara què vol dir això? Bé, sembla que hi ha una escriptura no vàlid

306
00:18:50,840 --> 00:18:54,480
de mida 4 en la línia 21 de memory.c.

307
00:18:54,480 --> 00:18:59,180
Així que anem a tornar a la línia 21, i de fet, és que d'escriptura no vàlid.

308
00:18:59,180 --> 00:19:02,640
Així Valgrind no se celebrarà del tot la meva mà i em digui el que la solució és,

309
00:19:02,640 --> 00:19:05,520
però es detecta que estic fent una escriptura vàlida.

310
00:19:05,520 --> 00:19:08,800
Estic tocant 4 bytes que no ha de ser, i pel que sembla això és perquè,

311
00:19:08,800 --> 00:19:13,960
com vostè ha assenyalat, estic fent [10] en lloc de [9] màximament

312
00:19:13,960 --> 00:19:16,660
o [0] o alguna cosa intermedi.

313
00:19:16,660 --> 00:19:19,690
Amb Valgrind, es donen compte en qualsevol moment que ara estem escrivint un programa

314
00:19:19,690 --> 00:19:24,190
que utilitza punters i utilitza la memòria, i malloc més específicament,

315
00:19:24,190 --> 00:19:27,080
definitivament entrar en l'hàbit de córrer tant temps

316
00:19:27,080 --> 00:19:30,890
però molt fàcil de copiar i enganxar comandaments de Valgrind

317
00:19:30,890 --> 00:19:32,650
per veure si hi ha alguns errors en aquest país.

318
00:19:32,650 --> 00:19:34,820
I serà aclaparador cada vegada que veus la sortida,

319
00:19:34,820 --> 00:19:39,430
però només a través d'analitzar visualment la totalitat del producte i veure si vostè veu les mencions d'errors

320
00:19:39,430 --> 00:19:43,190
o advertències o invàlida o perduda.

321
00:19:43,190 --> 00:19:46,200
Les paraules que sonen com et vas equivocar en algun lloc.

322
00:19:46,200 --> 00:19:48,580
Així que adonar-se que és una nova eina en la seva caixa d'eines.

323
00:19:48,580 --> 00:19:51,270
>> Ara el dilluns, vam tenir un munt de gent ve fins aquí

324
00:19:51,270 --> 00:19:53,150
i representar la noció d'una llista enllaçada.

325
00:19:53,150 --> 00:20:00,970
I presentem la llista enllaçada com una solució a quin és el problema?

326
00:20:00,970 --> 00:20:04,590
Sí? [Resposta Estudiantil, inintel · ligible] Bé.

327
00:20:04,590 --> 00:20:06,530
Les matrius no poden tenir memòria que s'agrega a ells.

328
00:20:06,530 --> 00:20:09,440
Si assigna una matriu de mida 10, això és tot el que hi ha.

329
00:20:09,440 --> 00:20:13,690
Vostè pot trucar a una funció com realloc si inicialment anomenada malloc,

330
00:20:13,690 --> 00:20:17,580
i que pot tractar de créixer la matriu si no hi ha espai cap al final d'ella

331
00:20:17,580 --> 00:20:21,610
que ningú més està utilitzant, i si no hi ha, s'acaba de trobar un tros més gran a un altre lloc.

332
00:20:21,610 --> 00:20:25,040
Però llavors es copiarà tots aquests bytes en la nova matriu.

333
00:20:25,040 --> 00:20:28,310
Això sona com una solució molt correcta.

334
00:20:28,310 --> 00:20:34,790
Per què és poc atractiu?

335
00:20:34,790 --> 00:20:36,940
Vull dir que funciona, els éssers humans han resolt aquest problema.

336
00:20:36,940 --> 00:20:40,710
Per què hem de resoldre el dilluns amb llistes enllaçades? Sí?

337
00:20:40,710 --> 00:20:44,060
[Resposta Estudiantil, inintel · ligible] Podria ser molt llarg.

338
00:20:44,060 --> 00:20:49,260
De fet, cada vegada que vostè està trucant malloc o calloc o realloc, que és una més,

339
00:20:49,260 --> 00:20:52,470
qualsevol vostè temps, el programa, estan parlant amb el sistema operatiu,

340
00:20:52,470 --> 00:20:54,310
que tendeixen a frenar el programa de sota.

341
00:20:54,310 --> 00:20:57,470
I si vostè està fent aquest tipus de coses en els bucles, en realitat està alentint.

342
00:20:57,470 --> 00:21:00,740
No vas a notar això per al més simple de "Hello World" programes de tipus,

343
00:21:00,740 --> 00:21:04,300
però en programes molt més grans, fent que el sistema operatiu i una altra per a la memòria

344
00:21:04,300 --> 00:21:07,520
o donar de nou una i altra vegada no sol ser una bona cosa.

345
00:21:07,520 --> 00:21:11,210
A més, és només una espècie d'intel · lectual - és una completa pèrdua de temps.

346
00:21:11,210 --> 00:21:16,490
Per què assignar més memòria i més, el risc de copiar tot en la nova matriu,

347
00:21:16,490 --> 00:21:21,980
si vostè té una alternativa que li permet assignar memòria només el que realment necessita?

348
00:21:21,980 --> 00:21:24,130
Així que hi ha avantatges i desavantatges a aquí.

349
00:21:24,130 --> 00:21:26,730
Un dels avantatges és que ara tenim dinamisme.

350
00:21:26,730 --> 00:21:29,100
No importa on els trossos de memòria són que són gratuïtes,

351
00:21:29,100 --> 00:21:32,070
Només pot ordenar de crear aquestes molles de pa a través de punters

352
00:21:32,070 --> 00:21:34,470
per encadenar la cistella sencera units entre si.

353
00:21:34,470 --> 00:21:36,470
Però em pagar almenys un preu.

354
00:21:36,470 --> 00:21:40,060
>> Què he de renunciar a obtenir llistes enllaçades?

355
00:21:40,060 --> 00:21:42,470
Sí? [Resposta Estudiantil, inintel · ligible] Bé.

356
00:21:42,470 --> 00:21:45,650
Vostè necessita més memòria. Ara necessito espai per a aquests indicadors,

357
00:21:45,650 --> 00:21:47,900
i en el cas d'aquesta super llista enllaçada simple

358
00:21:47,900 --> 00:21:51,410
que només està tractant d'emmagatzemar sencers, que són 4 bytes, seguim dient

359
00:21:51,410 --> 00:21:54,240
així, un punter és de 4 bytes, de manera que ara hem duplicat literalment

360
00:21:54,240 --> 00:21:57,290
la quantitat de memòria que necessita només per emmagatzemar aquesta llista.

361
00:21:57,290 --> 00:21:59,680
Però una vegada més, es tracta d'un compromís constant en la informàtica

362
00:21:59,680 --> 00:22:03,440
entre el temps i l'espai i el desenvolupament, l'esforç i altres recursos.

363
00:22:03,440 --> 00:22:06,630
Quin és altra desavantatge d'usar una llista enllaçada? Sí?

364
00:22:06,630 --> 00:22:10,150
[Resposta Estudiantil, inintel · ligible]

365
00:22:10,150 --> 00:22:12,600
Bé. No és tan fàcil d'accedir. Ja no podem aprofitar

366
00:22:12,600 --> 00:22:15,530
setmana 0 principis com dividir i conquerir.

367
00:22:15,530 --> 00:22:18,220
I més específicament, la recerca binària. Perquè tot i que els éssers humans

368
00:22:18,220 --> 00:22:20,400
pot veure més o menys on la meitat d'aquesta llista és,

369
00:22:20,400 --> 00:22:25,840
l'equip només sap que aquesta llista enllaçada comença en la direcció anomenat primer.

370
00:22:25,840 --> 00:22:28,250
I això és 0x123 o alguna cosa per l'estil.

371
00:22:28,250 --> 00:22:30,990
I l'única manera que el programa pot trobar l'element central

372
00:22:30,990 --> 00:22:33,350
en realitat és buscar tota la llista.

373
00:22:33,350 --> 00:22:35,500
I tot i així, literalment, ha de buscar en tota la llista perquè

374
00:22:35,500 --> 00:22:38,950
fins i tot una vegada que arribi l'element central seguint els punters,

375
00:22:38,950 --> 00:22:42,380
et, el programa, no tenen idea de quant temps aquesta llista és, en potència,

376
00:22:42,380 --> 00:22:45,250
fins arribar a la final de la mateixa, i com saber programació

377
00:22:45,250 --> 00:22:48,600
que estem al final d'una llista enllaçada?

378
00:22:48,600 --> 00:22:51,120
Hi ha un punter NULL especial, de manera que una vegada més, una convenció.

379
00:22:51,120 --> 00:22:53,870
En lloc d'utilitzar aquest punter, definitivament no volem que sigui un valor escombraries

380
00:22:53,870 --> 00:22:57,750
apuntant en algun lloc fora de l'escenari, volem que sigui la mà cap avall, NULL,

381
00:22:57,750 --> 00:23:01,530
així que tenim aquest terme en aquesta estructura de dades perquè sapiguem on acaba.

382
00:23:01,530 --> 00:23:03,410
>> Què passa si volem manipular això?

383
00:23:03,410 --> 00:23:05,980
Vam fer la major part d'això visualment, i amb els éssers humans,

384
00:23:05,980 --> 00:23:07,630
però el que si volem fer una inserció?

385
00:23:07,630 --> 00:23:12,360
Així que la llista original de 9, 17, 20, 22, 29, 34.

386
00:23:12,360 --> 00:23:16,730
I si després volia malloc espai per al número 55, un node per a això,

387
00:23:16,730 --> 00:23:20,730
i després volem inserir 55 a la llista de la mateixa manera que vam fer el dilluns?

388
00:23:20,730 --> 00:23:23,690
Com podem fer això? Bé, Anita es va acostar i ella va caminar essencialment la llista.

389
00:23:23,690 --> 00:23:27,500
Ella va començar en el primer element, després el següent, el següent, el següent, el següent, el següent.

390
00:23:27,500 --> 00:23:29,500
Finalment va colpejar la mà esquerra fins al fons

391
00:23:29,500 --> 00:23:34,480
i es va adonar oh, aquest és NULL. Llavors, què manipulació de punters que havia de fer?

392
00:23:34,480 --> 00:23:37,980
La persona que estava a l'extrem, número 34, necessitava la seva mà esquerra aixecada

393
00:23:37,980 --> 00:23:46,220
per assenyalar als 55, 55 necessitaven el seu braç esquerre cap avall per ser el nou terminador NULL. Fet.

394
00:23:46,220 --> 00:23:49,540
Bastant fàcil d'inserir 55 a una llista ordenada.

395
00:23:49,540 --> 00:23:51,800
I com podria aquest aspecte?

396
00:23:51,800 --> 00:23:55,690
>> Deixin-me seguir endavant i obrir alguns exemple de codi aquí.

397
00:23:55,690 --> 00:23:58,120
Vaig a obrir gedit, i em va deixar obrir dos arxius primer.

398
00:23:58,120 --> 00:24:02,050
Un d'ells és list1.h, i permetin-me recordar-los que aquest era el tros de codi

399
00:24:02,050 --> 00:24:04,920
que es va utilitzar per representar un node.

400
00:24:04,920 --> 00:24:13,040
Un node té tant una crida int n i un punter proper anomenat que simplement apunta el següent en la llista.

401
00:24:13,040 --> 00:24:15,450
Que es troba ara en un arxiu. H. Per què?

402
00:24:15,450 --> 00:24:19,090
Hi ha una convenció, i no s'han aprofitat d'això una quantitat enorme de nosaltres mateixos,

403
00:24:19,090 --> 00:24:22,220
però la persona que va escriure funcions printf i altres

404
00:24:22,220 --> 00:24:27,150
va donar com a regal al món totes aquestes funcions en escriure un fitxer anomenat stdio.h.

405
00:24:27,150 --> 00:24:30,950
I després hi ha string.h, i després hi Map.h, i no tots aquests arxius h

406
00:24:30,950 --> 00:24:34,410
que es pot haver vist o utilitzat durant el terme escrit per altres persones.

407
00:24:34,410 --> 00:24:38,470
Normalment, en els. Arxius h són úniques coses com typedefs

408
00:24:38,470 --> 00:24:42,310
o declaracions de tipus personalitzats o declaracions de constants.

409
00:24:42,310 --> 00:24:47,890
No posar les implementacions funcions 'en els arxius de capçalera.

410
00:24:47,890 --> 00:24:50,570
Es posa, en canvi, només els seus prototips.

411
00:24:50,570 --> 00:24:53,050
Poses les coses que vols compartir amb el món el que necessiten

412
00:24:53,050 --> 00:24:55,640
amb la finalitat de compilar el codi. Així que per entrar en aquest hàbit,

413
00:24:55,640 --> 00:24:59,110
vam decidir fer el mateix. No hi ha molt a list1.h,

414
00:24:59,110 --> 00:25:02,070
però hem posat alguna cosa que podria ser d'interès per a les persones en el món

415
00:25:02,070 --> 00:25:05,030
que volen utilitzar la nostra aplicació llista enllaçada.

416
00:25:05,030 --> 00:25:08,040
Ara, en list1.c, no vaig a anar a través de tot aquest assumpte

417
00:25:08,040 --> 00:25:11,390
perquè és una mica llarg, aquest programa, però anem a executar realment ràpid en l'indicador.

418
00:25:11,390 --> 00:25:15,720
Permetin-me compilar list1, deixa a continuació, executeu list1, i el que veurem és

419
00:25:15,720 --> 00:25:18,070
hem simulat un programa petit i senzill aquí

420
00:25:18,070 --> 00:25:20,990
que permetrà a mi per afegir i treure els números d'una llista.

421
00:25:20,990 --> 00:25:24,310
Així que seguirem endavant i m'escrigui 3 per l'opció de menú 3.

422
00:25:24,310 --> 00:25:27,880
Vull inserir el nombre - de deixar fer el primer nombre, que tenia 9 anys,

423
00:25:27,880 --> 00:25:30,550
i ara em diuen que la llista és ara 9.

424
00:25:30,550 --> 00:25:33,760
Deixa anar endavant i fer-ho una altra inserció, de manera que vaig arribar a l'opció de menú 3.

425
00:25:33,760 --> 00:25:36,760
A quin nombre desitja inserir? 17.

426
00:25:36,760 --> 00:25:39,220
Retorn. I faré un més.

427
00:25:39,220 --> 00:25:41,720
Permetin-me introduir el número 22.

428
00:25:41,720 --> 00:25:45,850
Així que tenim el començament de la llista enllaçada que teníem en forma de diapositives fa un moment.

429
00:25:45,850 --> 00:25:48,740
Com és aquesta inserció succeint realment?

430
00:25:48,740 --> 00:25:52,000
En efecte, 22 es troba ara al final de la llista.

431
00:25:52,000 --> 00:25:55,050
Així que la història ens diu a l'escenari el dilluns i tornar a tapar just ara

432
00:25:55,050 --> 00:25:57,460
en realitat ha d'estar succeint en el codi.

433
00:25:57,460 --> 00:25:59,700
Anem a fer una ullada. Permetin-me baixi aquest arxiu.

434
00:25:59,700 --> 00:26:01,720
Anem a passar per alt algunes de les funcions,

435
00:26:01,720 --> 00:26:05,630
però anirem a, per exemple, la funció d'inserció.

436
00:26:05,630 --> 00:26:11,720
>> Anem a veure com fem per inserir un nou node a la llista enllaçada.

437
00:26:11,720 --> 00:26:14,550
On és la llista declarat? Bé, anem a recórrer tot el camí fins a la part superior,

438
00:26:14,550 --> 00:26:19,970
i noti que la cistella enllaçada és essencialment declarada com a únic punter és NULL inicialment.

439
00:26:19,970 --> 00:26:23,180
Així que estic utilitzant una variable global aquí, que en general hem predicat contra

440
00:26:23,180 --> 00:26:25,280
perquè fa que el seu codi una mica complicat de mantenir,

441
00:26:25,280 --> 00:26:29,080
és una espècie de mandrós, en general, però no és mandrós i no és dolent i no és dolent

442
00:26:29,080 --> 00:26:33,660
si sol propòsit del seu programa en la vida és per simular una llista enllaçada.

443
00:26:33,660 --> 00:26:35,460
Que és exactament el que estem fent.

444
00:26:35,460 --> 00:26:39,100
Així que en lloc de declarar això en principal i després haver de passar a totes les funcions

445
00:26:39,100 --> 00:26:42,640
hem escrit en aquest programa, en lloc realitzar oh, anem a fer-global

446
00:26:42,640 --> 00:26:47,060
perquè tot el propòsit d'aquest programa és demostrar una i només una llista enllaçada.

447
00:26:47,060 --> 00:26:50,700
Així que se sent bé. Aquí són les meves prototips, i no anem a anar a través de tots ells,

448
00:26:50,700 --> 00:26:55,800
però vaig escriure una funció d'eliminació, una funció de recerca, una funció d'inserció, i una funció de desplaçament.

449
00:26:55,800 --> 00:26:59,080
Però ara anem a anar de nou a la funció d'inserció

450
00:26:59,080 --> 00:27:01,490
i veure com es treballa aquí.

451
00:27:01,490 --> 00:27:09,940
Insert està en línia - aquí anem.

452
00:27:09,940 --> 00:27:12,850
Insereix. Així que no té cap argument, perquè demanarem

453
00:27:12,850 --> 00:27:15,930
l'usuari dins d'aquesta funció per al número que voleu inserir.

454
00:27:15,930 --> 00:27:19,410
Però abans, ens preparem per donar-los una mica d'espai.

455
00:27:19,410 --> 00:27:22,050
Aquesta és una espècie de copiar i enganxar des de l'altre exemple.

456
00:27:22,050 --> 00:27:25,110
En aquest cas, l'estaven assignant un int, aquest cop estem assignant un node.

457
00:27:25,110 --> 00:27:27,910
Jo no me'n recordo quants bytes d'un node és, però això està bé.

458
00:27:27,910 --> 00:27:30,460
Sizeof pot adonar-se d'això per mi.

459
00:27:30,460 --> 00:27:33,340
I per què estic comprovant NULL en la línia 120?

460
00:27:33,340 --> 00:27:37,530
Què podria sortir malament en la línia 119? Sí?

461
00:27:37,530 --> 00:27:40,530
[Resposta Estudiantil, inintel · ligible]

462
00:27:40,530 --> 00:27:43,440
Bé. Només podria donar-se el cas que li he demanat massa memòria

463
00:27:43,440 --> 00:27:47,020
o que alguna cosa va malament i el sistema operatiu no té suficients bytes per donar-me,

464
00:27:47,020 --> 00:27:50,640
pel que assenyala tant en tornar NULL, i si no comproven que

465
00:27:50,640 --> 00:27:54,710
i jo cegament procedir a utilitzar l'adreça retornada, pot ser NULL.

466
00:27:54,710 --> 00:27:58,400
Podria ser algun valor desconegut, no és una bona cosa si no jo -

467
00:27:58,400 --> 00:28:00,590
en realitat no serà un valor desconegut. Pot ser NULL, pel que no vull

468
00:28:00,590 --> 00:28:02,550
per abusar-ne i arriscar-se a dereferencing ella.

469
00:28:02,550 --> 00:28:07,410
Si això passa, jo acabo de tornar i anem a fer veure que no he tingut cap record en absolut.

470
00:28:07,410 --> 00:28:12,270
>> En cas contrari, li dic a l'usuari donar-me un número per inserir, que dic la nostra getInt vell amic,

471
00:28:12,270 --> 00:28:15,530
i aquesta era la nova sintaxi es va introduir el dilluns.

472
00:28:15,530 --> 00:28:20,320
'Newptr-> n' significa prendre la direcció que li van donar per malloc

473
00:28:20,320 --> 00:28:23,490
que representa el primer byte d'un objecte nou node,

474
00:28:23,490 --> 00:28:26,860
i després anar al camp anomenat núm.

475
00:28:26,860 --> 00:28:35,270
Una pregunta de la trivia poc: Això és equivalent al que la línia més críptica de codi?

476
00:28:35,270 --> 00:28:38,110
Com podria jo haver escrit això? Vols prendre una punyalada?

477
00:28:38,110 --> 00:28:41,480
[Resposta Estudiantil, inintel · ligible]

478
00:28:41,480 --> 00:28:44,870
Bé. Usant el núm., Però no és tan simple com això.

479
00:28:44,870 --> 00:28:47,090
Què és el primer que fer? [Resposta Estudiantil, inintel · ligible]

480
00:28:47,090 --> 00:28:52,730
Bé. He de fer newptr.n *.

481
00:28:52,730 --> 00:28:55,610
Així que això ens diu nou punter és òbviament una adreça. Per què?

482
00:28:55,610 --> 00:28:59,520
Com que va ser retornat per malloc. El newptr * dient "anar-hi"

483
00:28:59,520 --> 00:29:02,970
i després una vegada que estàs allà, llavors vostè pot utilitzar el més familiar. n,

484
00:29:02,970 --> 00:29:05,730
però això només es veu una mica lleig, sobretot si els éssers humans es van a

485
00:29:05,730 --> 00:29:10,360
elaborar indicadors amb fletxes tot el temps, el món s'ha estandarditzat en aquesta notació fletxa,

486
00:29:10,360 --> 00:29:12,320
que fa exactament el mateix.

487
00:29:12,320 --> 00:29:16,070
Pel que només utilitzi l'opció -> notació quan la cosa de l'esquerra és un punter.

488
00:29:16,070 --> 00:29:18,790
En cas contrari, si es tracta d'una estructura real, utilitzeu el núm ..

489
00:29:18,790 --> 00:29:25,800
I després això: Per què inicialitzar newptr-> següent a NULL?

490
00:29:25,800 --> 00:29:28,610
No volem que una mà esquerra penjant fora de la final de l'etapa.

491
00:29:28,610 --> 00:29:31,630
Volem que apunta cap avall, el que significa que al final d'aquesta llista

492
00:29:31,630 --> 00:29:34,980
podria ser en aquest node, així que millor assegurar-se que és NULL.

493
00:29:34,980 --> 00:29:38,460
I, en general, la inicialització de les variables o dels seus membres de dades i estructures

494
00:29:38,460 --> 00:29:40,470
a alguna cosa que és només una bona pràctica.

495
00:29:40,470 --> 00:29:45,170
Deixar simplement escombraries existeixen i seguiran existint generalment et fica en problemes

496
00:29:45,170 --> 00:29:48,650
si vostè s'oblida de fer alguna cosa en el futur.

497
00:29:48,650 --> 00:29:51,590
>> Aquí hi ha uns pocs casos. Això, de nou, és la funció d'inserció,

498
00:29:51,590 --> 00:29:54,930
i el primer que comprovar és si la variable anomenada en primer lloc,

499
00:29:54,930 --> 00:29:58,240
aquesta variable global és NULL, que vol dir que no hi ha llista enllaçada.

500
00:29:58,240 --> 00:30:02,460
No hem introduït cap número, per la qual cosa és trivial per inserir aquest nombre actual

501
00:30:02,460 --> 00:30:05,240
a la llista, ja que només pertany al començament de la llista.

502
00:30:05,240 --> 00:30:08,100
Així que això va ser quan Anita estava dret allà sola, pretenent

503
00:30:08,100 --> 00:30:11,390
no hi havia ningú més per aquí a l'escenari fins que ens van assignar un node,

504
00:30:11,390 --> 00:30:13,940
llavors podria aixecar la mà per primera vegada,

505
00:30:13,940 --> 00:30:17,420
si tothom havia arribat a l'etapa després d'ella el dilluns.

506
00:30:17,420 --> 00:30:22,900
Ara aquí, aquest és un petit escac que he de dir si el nou node de valor de n

507
00:30:22,900 --> 00:30:27,370
és <que el valor de n en el primer node actual,

508
00:30:27,370 --> 00:30:29,930
això vol dir que hi ha una llista enllaçada que ha començat.

509
00:30:29,930 --> 00:30:32,330
Hi ha almenys un node a la llista, però aquest noi nou

510
00:30:32,330 --> 00:30:37,230
pertany davant seu, així que hem de moure les coses.

511
00:30:37,230 --> 00:30:43,450
En altres paraules, si la llista ha començat amb només, diguem,

512
00:30:43,450 --> 00:30:48,100
només el número 17, que és el - en realitat, no podem fer-ho més clarament.

513
00:30:48,100 --> 00:30:56,010
Si comencem la nostra història amb un punter aquí es diu en primer lloc,

514
00:30:56,010 --> 00:30:59,870
i al principi és NULL, i ens inseriu el número 9,

515
00:30:59,870 --> 00:31:02,510
el número 9 pertany clarament al començament de la llista.

516
00:31:02,510 --> 00:31:07,400
Així que anem a pretendre que només malloced l'adreça o el número 9 i el va posar aquí.

517
00:31:07,400 --> 00:31:13,170
Si el primer és de 9 per defecte, el primer escenari hem parlat només de mig punt que anem a aquest tipus aquí,

518
00:31:13,170 --> 00:31:15,790
deixar això com NULL, ara tenim el número 9.

519
00:31:15,790 --> 00:31:18,280
El següent número que voleu inserir és de 17.

520
00:31:18,280 --> 00:31:22,420
17 pertany per aquí, així que haurem de fer una mica de lògica pas a pas a través d'aquest.

521
00:31:22,420 --> 00:31:26,060
Així que en el seu lloc, abans de fer això, anem a suposar que volem inserir el número 8.

522
00:31:26,060 --> 00:31:28,650
>> Així que, per conveniència, vaig a trucar aquí.

523
00:31:28,650 --> 00:31:30,760
Però recordi, malloc pot posar gairebé qualsevol lloc.

524
00:31:30,760 --> 00:31:33,460
Però pel bé de dibuix, ho vaig a posar aquí.

525
00:31:33,460 --> 00:31:38,440
Així que pretendre que acabo d'assignar un node per al número 8, el que és nul per defecte.

526
00:31:38,440 --> 00:31:42,800
I ara què ha de passar? Un parell de coses.

527
00:31:42,800 --> 00:31:47,090
Hem fet aquest error a l'escenari dilluns al que actualitza un punter d'aquest tipus,

528
00:31:47,090 --> 00:31:51,890
després ho va fer, i després va afirmar - que han quedat orfes a tots els altres en l'escenari.

529
00:31:51,890 --> 00:31:54,350
Perquè puc - l'ordre de les operacions aquí és important,

530
00:31:54,350 --> 00:31:58,760
perquè ara que hem perdut aquest node 9, que és només una espècie de surar en l'espai.

531
00:31:58,760 --> 00:32:01,150
Així que això no és l'enfocament correcte de dilluns.

532
00:32:01,150 --> 00:32:03,330
Primer hem de fer alguna cosa més.

533
00:32:03,330 --> 00:32:06,280
L'estat del món es veu així. Inicialment, 8 ha estat assignada.

534
00:32:06,280 --> 00:32:10,550
Quina seria una millor manera d'inserir 8?

535
00:32:10,550 --> 00:32:14,720
En comptes d'actualitzar aquest primer indicador, només actualitzar aquest d'aquí el seu lloc.

536
00:32:14,720 --> 00:32:17,720
Així que tenim una línia de codi que es convertirà aquest caràcter NULL

537
00:32:17,720 --> 00:32:22,020
en un indicador real que s'assenyala en el node 9,

538
00:32:22,020 --> 00:32:27,970
i llavors amb seguretat pot canviar primer a assenyalar a aquest tipus aquí.

539
00:32:27,970 --> 00:32:31,330
Ara tenim una llista, una llista enllaçada, de dos elements.

540
00:32:31,330 --> 00:32:33,580
I què significa això realment es veuen com aquí?

541
00:32:33,580 --> 00:32:36,900
Si ens fixem en el codi, observi que he fet exactament això.

542
00:32:36,900 --> 00:32:41,970
He dit newptr, i en aquesta història, newptr assenyalava a aquest tipus.

543
00:32:41,970 --> 00:32:45,520
>> Així que permetin-me treure una cosa més, i jo hauria d'haver deixat l'habitació d'una mica més d'això.

544
00:32:45,520 --> 00:32:48,540
Així de perdonar el petit dibuix diminut.

545
00:32:48,540 --> 00:32:52,140
Aquest noi es diu newptr.

546
00:32:52,140 --> 00:32:57,940
Aquesta és la variable que declarem unes poques línies abans, en línia - just per sobre de 25.

547
00:32:57,940 --> 00:33:03,430
I està apuntant a 8. Així que quan dic newptr-> següent, el que significa anar a l'estructura

548
00:33:03,430 --> 00:33:07,910
que està sent apuntat per newptr, així que aquí estem, anar-hi.

549
00:33:07,910 --> 00:33:13,990
A continuació, a la fletxa que diu obtenir el següent camp i faci el signe = diu quin valor posar allà?

550
00:33:13,990 --> 00:33:17,280
El valor que es trobava en primer lloc, quin valor estava en primer lloc?

551
00:33:17,280 --> 00:33:21,930
En primer lloc s'assenyala en aquest node, pel que significa això ara ha d'apuntar a aquest node.

552
00:33:21,930 --> 00:33:25,660
En altres paraules, encara que el que sembla un embolic ridícul amb la meva lletra,

553
00:33:25,660 --> 00:33:28,620
Què és una idea simple de moure només al voltant d'aquestes fletxes

554
00:33:28,620 --> 00:33:31,560
es tradueix a codi amb només aquest traçador de línies.

555
00:33:31,560 --> 00:33:38,110
Guardi el que està en primer lloc al següent camp i després actualitzar el primer que realment és.

556
00:33:38,110 --> 00:33:40,900
Seguirem endavant i avanç ràpid a través d'alguna cosa d'això,

557
00:33:40,900 --> 00:33:44,220
i que únicament busqui en aquesta inserció col per ara.

558
00:33:44,220 --> 00:33:51,210
Suposem que arribo al punt en què em sembla que el següent camp d'un node és NULL.

559
00:33:51,210 --> 00:33:53,410
I en aquest punt de la història, un detall que m'estic passant per alt

560
00:33:53,410 --> 00:33:58,170
és que he introduït un altre punter fins aquí a la línia 142, el punter predecessor.

561
00:33:58,170 --> 00:34:01,320
Essencialment, en aquest moment de la història, una vegada que la llista es fa llarga,

562
00:34:01,320 --> 00:34:04,800
Jo com que hagi de caminar amb dos dits perquè si vaig massa lluny,

563
00:34:04,800 --> 00:34:08,219
Recordo que en una sola llista llarga durada, no es pot tornar enrere.

564
00:34:08,219 --> 00:34:13,659
Així que aquesta idea de predptr és meu dit esquerre, i newptr - no newptr.

565
00:34:13,659 --> 00:34:17,199
Un altre indicador que aquí és el meu altre dit, i jo sóc només una mica de caminar a la llista.

566
00:34:17,199 --> 00:34:22,179
És per això que existeix. Però considerarem només un dels casos més simples aquí.

567
00:34:22,179 --> 00:34:26,620
Si el camp al costat d'aquest punter és NULL, quina és la implicació lògica?

568
00:34:26,620 --> 00:34:30,840
Si vostè està travessant aquesta llista i et trobes amb un punter NULL?

569
00:34:30,840 --> 00:34:35,780
Vostè és al final de la llista, de manera que el codi per afegir aquest element a continuació, un addicional

570
00:34:35,780 --> 00:34:41,230
és un gènere del que intuïtiu prendrà aquest node la pròxima punter és NULL,

571
00:34:41,230 --> 00:34:46,120
així que això és actualment NULL, i canviar, però, és l'adreça del nou node.

572
00:34:46,120 --> 00:34:52,260
Així que estem dibuixant en el codi de la fletxa que dibuixem a l'escenari per aixecar la mà esquerra d'una persona.

573
00:34:52,260 --> 00:34:54,070
>> I el cas que vaig a agitar les mans menys per ara,

574
00:34:54,070 --> 00:34:58,020
només perquè crec que és fàcil perdre quan ho fem en aquest tipus d'entorn,

575
00:34:58,020 --> 00:35:00,600
és la comprovació d'inserció en la part mitjana de la llista.

576
00:35:00,600 --> 00:35:03,220
Però només intuïtivament, el que ha de passar si vostè vol esbrinar

577
00:35:03,220 --> 00:35:06,600
on algun nombre s'ha de posar en el centre és que has de caminar

578
00:35:06,600 --> 00:35:09,510
amb més d'un dit, més d'un punter,

579
00:35:09,510 --> 00:35:12,920
esbrinar on ha d'estar per comprovar és l'element <l'actual,

580
00:35:12,920 --> 00:35:15,450
> L'actual, i una vegada que trobi aquest lloc,

581
00:35:15,450 --> 00:35:20,400
llavors vostè ha de fer aquest tipus de joc de la closca on es mouen al voltant dels punters amb molta cura.

582
00:35:20,400 --> 00:35:23,850
I aquesta resposta, si ho desitja a la raó a través d'això a casa pel seu compte,

583
00:35:23,850 --> 00:35:28,340
es redueix només a aquestes dues línies de codi, però l'ordre de les línies és súper important.

584
00:35:28,340 --> 00:35:31,390
Perquè si li cau la mà d'algú i aixecar una altra persona en l'ordre equivocat,

585
00:35:31,390 --> 00:35:34,580
una vegada més, que podria acabar deixant orfes a la llista.

586
00:35:34,580 --> 00:35:39,500
Per resumir conceptualment més, la inserció de la cua és relativament senzill.

587
00:35:39,500 --> 00:35:42,940
La inserció al cap és també relativament senzill,

588
00:35:42,940 --> 00:35:45,580
però cal actualitzar un punter addicional en aquesta ocasió

589
00:35:45,580 --> 00:35:47,930
per esprémer el número 5 a la llista aquí,

590
00:35:47,930 --> 00:35:51,560
i després introduir-se en el medi implica un esforç encara més,

591
00:35:51,560 --> 00:35:56,130
per inserir acuradament el número 20 en la seva ubicació correcta,

592
00:35:56,130 --> 00:35:58,350
que és entre 17 i 22.

593
00:35:58,350 --> 00:36:02,700
Així que cal fer alguna cosa com tenir el nou node de 20 punts a 22,

594
00:36:02,700 --> 00:36:08,470
i, a continuació, punter que node necessita ser actualitzat per darrera?

595
00:36:08,470 --> 00:36:10,630
És 17 que en realitat inserir.

596
00:36:10,630 --> 00:36:14,080
Així que de nou, vaig a ajornar el codi real perquè l'aplicació particular.

597
00:36:14,080 --> 00:36:17,280
>> A primera vista, és una mica aclaparador, però no deixa de ser un bucle infinit

598
00:36:17,280 --> 00:36:21,770
que està llaç, llaç, llaç, llaç, i trencar tan aviat com es va colpejar el punter NULL,

599
00:36:21,770 --> 00:36:24,590
moment en què vostè pot fer la inserció requerida.

600
00:36:24,590 --> 00:36:30,960
Això, llavors, és el representant codi vinculat inserció llista.

601
00:36:30,960 --> 00:36:34,590
Això va ser una mica molt, i se sent com que hem resolt un problema,

602
00:36:34,590 --> 00:36:36,940
però hem introduït un altre conjunt. Francament, ens hem passat tot aquest temps

603
00:36:36,940 --> 00:36:40,540
en gran O i Ω i el temps de funcionament, tractant de resoldre els problemes més ràpidament,

604
00:36:40,540 --> 00:36:43,270
i aquí estem donant un gran pas cap enrere, se sent.

605
00:36:43,270 --> 00:36:45,380
I, no obstant això, si l'objectiu és emmagatzemar les dades,

606
00:36:45,380 --> 00:36:48,010
se sent com el Sant Grial, com vam dir el dilluns, seria realment

607
00:36:48,010 --> 00:36:50,470
per guardar les coses a l'instant.

608
00:36:50,470 --> 00:36:53,930
>> En efecte, suposem que hem fet la llista de banda per un moment vinculat

609
00:36:53,930 --> 00:36:56,000
i que en comptes introduït el concepte d'una taula.

610
00:36:56,000 --> 00:36:59,110
I anem a pensar en una taula per un moment com una matriu.

611
00:36:59,110 --> 00:37:03,790
Aquesta matriu i aquest cas aquí té uns 26 elements, del 0 al 25,

612
00:37:03,790 --> 00:37:07,940
i suposo que necessitava una mica tros d'emmagatzematge per als noms:

613
00:37:07,940 --> 00:37:10,350
Alice i Bob i Charlie i similars.

614
00:37:10,350 --> 00:37:12,880
I es necessita algun tipus d'estructura de dades per emmagatzemar aquests noms.

615
00:37:12,880 --> 00:37:15,000
Bé, podries utilitzar alguna cosa com una llista enllaçada

616
00:37:15,000 --> 00:37:20,260
i es podia caminar per la llista d'inserir Alice abans que Bob i Charlie després que Bob i així successivament.

617
00:37:20,260 --> 00:37:23,850
I, de fet, si vostè vol veure un codi com el que en un a part,

618
00:37:23,850 --> 00:37:27,230
Sabem que en list2.h, fem exactament això.

619
00:37:27,230 --> 00:37:30,610
No entrarem a través d'aquest codi, però això és una variant del exemple primer

620
00:37:30,610 --> 00:37:34,640
que introdueix una estructura que hàgim vist abans estudiant anomenat,

621
00:37:34,640 --> 00:37:40,330
i llavors el que realment emmagatzema en la llista enllaçada és un punter a una estructura estudiant

622
00:37:40,330 --> 00:37:44,520
en lloc d'un nombre enter petit i senzill, núm.

623
00:37:44,520 --> 00:37:46,900
Així que adonar-se que hi ha codi cal implica cadenes reals,

624
00:37:46,900 --> 00:37:49,940
però si l'objectiu que ens ocupa realment ara és abordar el problema de l'eficiència,

625
00:37:49,940 --> 00:37:53,380
No seria bo si se'ns dóna un objecte anomenat Alice,

626
00:37:53,380 --> 00:37:56,020
volem posar-la al lloc adequat en una estructura de dades,

627
00:37:56,020 --> 00:37:58,860
se sent com que seria molt agradable per posar només Alice,

628
00:37:58,860 --> 00:38:01,180
el nom comença amb A, a la primera ubicació.

629
00:38:01,180 --> 00:38:05,270
I Bob, el nom comença per B, en la segona ubicació.

630
00:38:05,270 --> 00:38:09,580
Amb una matriu, o anem a començar a cridar a una taula, una taula hash en què,

631
00:38:09,580 --> 00:38:13,650
podem fer exactament això. Si ens donen un nom com Alice,

632
00:38:13,650 --> 00:38:16,700
una cadena com Alice, on posar A-l-i-c-i?

633
00:38:16,700 --> 00:38:20,540
Necessitem un hueristic. Necessitem una funció per prendre alguna entrada com Alícia

634
00:38:20,540 --> 00:38:24,610
i tornar una resposta: "Posa Alice en aquest lloc."

635
00:38:24,610 --> 00:38:28,720
I aquesta funció, aquest quadre de negre, es dirà una funció hash.

636
00:38:28,720 --> 00:38:32,330
>> Una funció hash és una cosa que pren una entrada, com "Alice",

637
00:38:32,330 --> 00:38:38,080
i torna a la qual, en general, la ubicació numèrica en alguna estructura de dades on Alice pertany.

638
00:38:38,080 --> 00:38:40,830
En aquest cas, la nostra funció de hash ha de ser relativament simple.

639
00:38:40,830 --> 00:38:47,510
La nostra funció hash ha de dir, si se li dóna "Alice", que el personatge em deu importar?

640
00:38:47,510 --> 00:38:55,660
La primera d'elles. Així que miro [0], i després em diuen si [0] és un personatge, torni el número 0.

641
00:38:55,660 --> 00:39:01,130
Si és B, tornarà 1. Si es tracta de C, tornar 2, i així successivament.

642
00:39:01,130 --> 00:39:05,940
Tots índex 0, i que em permeti inserir Alice i Bob i Charlie i així successivament

643
00:39:05,940 --> 00:39:10,960
en aquesta estructura de dades. Però hi ha un problema.

644
00:39:10,960 --> 00:39:13,060
I si Anita ve una altra vegada?

645
00:39:13,060 --> 00:39:17,510
On posem Anita? El seu nom també comença amb la lletra A,

646
00:39:17,510 --> 00:39:20,330
i se sent com que hem fet un embolic encara més gran d'aquest problema.

647
00:39:20,330 --> 00:39:24,380
Ara tenim la inserció immediata, inserció constant de temps, en una estructura de dades

648
00:39:24,380 --> 00:39:27,100
en comptes de pitjor cas lineal,

649
00:39:27,100 --> 00:39:29,510
però què podem fer amb Anita en aquest cas?

650
00:39:29,510 --> 00:39:34,110
Quines són les dues opcions, de debò? Sí?

651
00:39:34,110 --> 00:39:37,410
[Resposta Estudiantil, inintel · ligible] Bé, pel que podríem tenir una altra dimensió.

652
00:39:37,410 --> 00:39:42,320
Això és bo. Així que podem construir coses en 3D com parlem verbalment dilluns.

653
00:39:42,320 --> 00:39:46,700
Podríem afegir un altre accés aquí, però suposo que no, estic tractant de mantenir això simple.

654
00:39:46,700 --> 00:39:50,160
L'objectiu general aquí és tenir immediat accés en temps constant,

655
00:39:50,160 --> 00:39:52,170
de manera que està afegir massa complexitat.

656
00:39:52,170 --> 00:39:55,970
Quines són les altres opcions quan es tracta d'inserir Anita en aquesta estructura de dades? Sí?

657
00:39:55,970 --> 00:39:58,610
[Resposta Estudiantil, inintel · ligible] Bé. Així que ens podíem moure tots els altres cap avall,

658
00:39:58,610 --> 00:40:03,040
com Charlie cops de colze per Bob i Alice, i després posem Anita on ella realment vol ser.

659
00:40:03,040 --> 00:40:05,660
>> Per descomptat, ara, no hi ha un efecte secundari d'això.

660
00:40:05,660 --> 00:40:09,000
Aquesta estructura de dades és probablement útil no perquè volem inserir la gent un cop

661
00:40:09,000 --> 00:40:11,250
sinó perquè volem comprovar si estàs allà més tard

662
00:40:11,250 --> 00:40:13,600
si volem imprimir tots els noms en l'estructura de dades.

663
00:40:13,600 --> 00:40:15,850
Anem a fer alguna cosa amb aquestes dades amb el temps.

664
00:40:15,850 --> 00:40:20,810
Així que ara tinc classe de fotut Alice, que ja no és on se suposa que ha de ser.

665
00:40:20,810 --> 00:40:23,880
Ni Bob ni és Charlie.

666
00:40:23,880 --> 00:40:26,060
Així que potser aquesta no és una idea tan bona.

667
00:40:26,060 --> 00:40:28,830
Però en realitat, aquesta és una opció. Podríem passar a tothom,

668
00:40:28,830 --> 00:40:32,240
o diables, Anita va arribar tard al joc, per què no acaba de posar Anita

669
00:40:32,240 --> 00:40:35,870
aquí no, aquí no, aquí no, anem a posar una mica més avall en la llista.

670
00:40:35,870 --> 00:40:38,680
Però el problema comença a delegar de nou.

671
00:40:38,680 --> 00:40:41,630
Vostè pot ser capaç de trobar l'instant Alice, basada en nom seu.

672
00:40:41,630 --> 00:40:44,320
I Bob instant, i Charlie. Però després buscar Anita,

673
00:40:44,320 --> 00:40:46,360
i ja veus, hmm, Alice es troba en el camí.

674
00:40:46,360 --> 00:40:48,770
Bé, deixa veure per sota d'Alice. Bob no és Anita.

675
00:40:48,770 --> 00:40:51,850
Charlie no és Anita. Oh, no és Anita.

676
00:40:51,850 --> 00:40:54,720
I si continua aquesta línia de la lògica fins al final,

677
00:40:54,720 --> 00:41:00,690
Quin és el temps d'execució del pitjor cas de trobar o inserir Anita en aquesta nova estructura de dades?

678
00:41:00,690 --> 00:41:03,280
És O (n), no?

679
00:41:03,280 --> 00:41:06,280
Com que en el pitjor dels casos, no és Alice, Bob, Charlie. . .

680
00:41:06,280 --> 00:41:10,150
tot el camí a algú que es diu "I", de manera que només hi ha un lloc a l'esquerra.

681
00:41:10,150 --> 00:41:13,950
Afortunadament, no tenim a ningú anomenat "Z", així que vam posar Anita a la part inferior.

682
00:41:13,950 --> 00:41:16,040
>> Realment no hem resolt aquest problema.

683
00:41:16,040 --> 00:41:19,890
Així que potser cal introduir aquesta tercera dimensió.

684
00:41:19,890 --> 00:41:22,230
I resulta que, si estem d'introduir aquesta tercera dimensió,

685
00:41:22,230 --> 00:41:25,240
no podem fer això perfectament, però el Sant Grial s'aconseguirà

686
00:41:25,240 --> 00:41:28,370
constant de temps d'inserció i les insercions dinàmics de manera que

687
00:41:28,370 --> 00:41:30,960
no hem de codificar una matriu de mida 26.

688
00:41:30,960 --> 00:41:34,400
Podem inserir tants noms com vulguem, però prendrem nostre fill de 5 minuts de descans aquí

689
00:41:34,400 --> 00:41:38,790
i després fer-ho correctament.

690
00:41:38,790 --> 00:41:46,020
Està bé. Vaig posar la història fins bastant artificial no

691
00:41:46,020 --> 00:41:48,670
per l'elecció d'Alice i Bob i Charlie i Anita,

692
00:41:48,670 --> 00:41:51,000
el nom va ser, òbviament, va a xocar amb Alice.

693
00:41:51,000 --> 00:41:54,120
Però la pregunta que va acabar dilluns amb és com de probable és

694
00:41:54,120 --> 00:41:56,370
que es podrien obtenir aquest tipus de col · lisions? En altres paraules,

695
00:41:56,370 --> 00:42:00,490
si comencem a utilitzar aquesta estructura tabular, que és en realitat una matriu,

696
00:42:00,490 --> 00:42:02,460
en aquest cas de 26 llocs,

697
00:42:02,460 --> 00:42:05,740
I si en lloc nostres entrades estan uniformement distribuïts?

698
00:42:05,740 --> 00:42:09,620
No és artificialment Alice i Bob i Charlie i David, i així successivament per ordre alfabètic,

699
00:42:09,620 --> 00:42:12,380
està distribuïda uniformement sobre l'A a la Z.

700
00:42:12,380 --> 00:42:15,220
>> Potser només haurem de tenir sort i que no tindrem dos A o B de dos

701
00:42:15,220 --> 00:42:17,640
amb una probabilitat molt alta, però com algú ha assenyalat,

702
00:42:17,640 --> 00:42:20,730
si es va generalitzar aquest problema i no fer 0-25

703
00:42:20,730 --> 00:42:26,060
però, per exemple, de 0 a 364 o 65 anys, sovint el nombre de dies en un any típic,

704
00:42:26,060 --> 00:42:31,170
i la pregunta, "¿Quina és la probabilitat que dos de nosaltres en aquesta sala tenen el mateix aniversari?"

705
00:42:31,170 --> 00:42:34,600
Dit d'una altra manera, quina és la probabilitat que dos de nosaltres té un nom que comença amb A?

706
00:42:34,600 --> 00:42:37,190
El tipus de pregunta és la mateixa, però aquest espai d'adreces,

707
00:42:37,190 --> 00:42:39,940
aquest espai de recerca, és més gran en el cas d'aniversari,

708
00:42:39,940 --> 00:42:42,820
perquè tenim més de tants dies l'any que les lletres de l'alfabet.

709
00:42:42,820 --> 00:42:44,910
Quina és la probabilitat d'una col · lisió?

710
00:42:44,910 --> 00:42:48,410
Bé, podem pensar en això per esbrinar les matemàtiques en sentit contrari.

711
00:42:48,410 --> 00:42:50,580
Quina és la probabilitat de col · lisions no?

712
00:42:50,580 --> 00:42:53,970
Doncs bé, aquesta expressió aquí diu que el que és la probabilitat

713
00:42:53,970 --> 00:42:58,770
si hi ha una sola persona en aquest saló, que celebra el seu aniversari únic?

714
00:42:58,770 --> 00:43:01,190
És 100%. Perquè si hi ha una sola persona a l'habitació,

715
00:43:01,190 --> 00:43:03,940
seu aniversari pot ser qualsevol dels 365 dies de l'any.

716
00:43:03,940 --> 00:43:08,650
Així que les opcions de 365/365 em dóna un valor d'1.

717
00:43:08,650 --> 00:43:11,250
Així que la probabilitat que es tracti en el moment és només 1.

718
00:43:11,250 --> 00:43:13,270
Però si hi ha una segona persona a l'habitació,

719
00:43:13,270 --> 00:43:16,490
Quina és la probabilitat que el seu aniversari és diferent?

720
00:43:16,490 --> 00:43:20,680
Només hi ha 364 dies possibles, fent cas omís dels anys de traspàs,

721
00:43:20,680 --> 00:43:23,580
pel seu aniversari no xocar amb les altres persones.

722
00:43:23,580 --> 00:43:31,920
Així que 364/365. Si una tercera persona entra, és 363/365, i així successivament.

723
00:43:31,920 --> 00:43:35,790
Així que seguim multiplicant aquestes fraccions, que són cada vegada més petits,

724
00:43:35,790 --> 00:43:40,720
per esbrinar quina és la probabilitat que tots nosaltres tenim aniversari únics?

725
00:43:40,720 --> 00:43:43,570
Però podem, és clar, acaba de prendre aquesta resposta i donar-li la volta al voltant

726
00:43:43,570 --> 00:43:47,210
i fer 1 menys tot això, una expressió que finalment va a aconseguir

727
00:43:47,210 --> 00:43:51,250
si et recordes de la part posterior dels seus llibres de matemàtiques, es veu una mica d'alguna cosa com això,

728
00:43:51,250 --> 00:43:54,590
que és molt més fàcil d'interpretar gràficament.

729
00:43:54,590 --> 00:43:57,820
I aquí té aquest gràfic en l'eix x el nombre d'aniversari,

730
00:43:57,820 --> 00:44:02,030
o el nombre de persones amb aniversari, i sobre l'eix i és la probabilitat d'una coincidència.

731
00:44:02,030 --> 00:44:06,060
I el que això vol dir és que si vostè té, diguem, fins i tot,

732
00:44:06,060 --> 00:44:10,860
anem a triar una cosa així com 22, 23.

733
00:44:10,860 --> 00:44:13,160
Si hi ha 22 o 23 persones a la sala,

734
00:44:13,160 --> 00:44:17,100
la probabilitat que dues d'aquestes poques persones tindran el mateix aniversari

735
00:44:17,100 --> 00:44:19,560
en realitat és súper alta, combinatòria.

736
00:44:19,560 --> 00:44:23,450
50% de probabilitat que en una classe de només 22 persones, un seminari, pràcticament,

737
00:44:23,450 --> 00:44:25,790
2 de aquestes persones tindran el mateix aniversari.

738
00:44:25,790 --> 00:44:28,520
Perquè hi ha moltes maneres en què vostè pot tenir el mateix aniversari.

739
00:44:28,520 --> 00:44:31,110
Pitjor encara, si ens fixem en la part dreta de la taula,

740
00:44:31,110 --> 00:44:34,040
pel temps que té una classe amb 58 estudiants en el mateix,

741
00:44:34,040 --> 00:44:39,270
la probabilitat que dues persones que tenen un alt aniversari és super, super, prop del 100%.

742
00:44:39,270 --> 00:44:41,880
Ara, això és una mena de fet de la diversió de la vida real.

743
00:44:41,880 --> 00:44:45,850
>> Però les implicacions, ara, per les estructures de dades i emmagatzematge d'informació

744
00:44:45,850 --> 00:44:51,100
significa que només suposant que té un bonic, net distribució uniforme de les dades

745
00:44:51,100 --> 00:44:53,650
i té una àmplia prou gran per a un munt de coses

746
00:44:53,650 --> 00:44:59,360
no vol dir que vostè va a fer que la gent en llocs únics.

747
00:44:59,360 --> 00:45:03,810
Vas a tenir col · lisions. Així que aquesta noció de hashing, com se l'anomena,

748
00:45:03,810 --> 00:45:07,450
tenint una entrada com "Alice" i el massatge d'alguna manera

749
00:45:07,450 --> 00:45:10,190
i després tornar a una resposta com 0 o 1 o 2.

750
00:45:10,190 --> 00:45:17,500
Tornant una mica de la sortida de funció que està plena d'aquesta probabilitat de col · lisió.

751
00:45:17,500 --> 00:45:19,530
Com podem gestionar aquestes col · lisions?

752
00:45:19,530 --> 00:45:21,940
Doncs bé, en el primer cas, podem prendre la idea que es suggereix.

753
00:45:21,940 --> 00:45:25,100
Només podem canviar a tot el món, o potser, una mica més simple,

754
00:45:25,100 --> 00:45:29,870
en comptes del món es mouen més, mourem Anita a la part inferior del lloc disponible.

755
00:45:29,870 --> 00:45:32,810
Així que si Alice es troba en 0, Bob està en 1, Charlie està a 2,

756
00:45:32,810 --> 00:45:35,260
només haurem de posar Anita del punt 3.

757
00:45:35,260 --> 00:45:38,860
I aquesta és una tècnica en l'estructura de dades anomenada sondeig lineal.

758
00:45:38,860 --> 00:45:41,310
Lineal perquè estàs caminant aquesta línia, i vostè és una espècie de sondeig

759
00:45:41,310 --> 00:45:43,640
per als punts disponibles en l'estructura de dades.

760
00:45:43,640 --> 00:45:46,210
Per descomptat, això es convertís en O (n).

761
00:45:46,210 --> 00:45:49,590
Si l'estructura de dades és molt complet, hi ha 25 persones en el que ja,

762
00:45:49,590 --> 00:45:54,120
i llavors Anita arriba, ella acaba en el que seria la ubicació Z, i això està bé.

763
00:45:54,120 --> 00:45:56,540
Ella encara li queda, i podem trobar més tard.

764
00:45:56,540 --> 00:46:00,100
>> Però això és contrari a l'objectiu d'accelerar les coses.

765
00:46:00,100 --> 00:46:02,530
Llavors, què passaria si en comptes introduïda aquesta tercera dimensió?

766
00:46:02,530 --> 00:46:06,400
Aquesta tècnica s'anomena generalment encadenament separat, o que té cadenes.

767
00:46:06,400 --> 00:46:10,030
I el que una taula hash és, aquesta estructura tabular,

768
00:46:10,030 --> 00:46:13,450
la taula és només un conjunt de punters.

769
00:46:13,450 --> 00:46:18,230
Però el que els punters assenyalar és conjectura què?

770
00:46:18,230 --> 00:46:21,970
Una llista enllaçada. I què si prenem el millor d'ambdós mons?

771
00:46:21,970 --> 00:46:26,500
Nosaltres fem servir arrays per als índexs inicials

772
00:46:26,500 --> 00:46:32,070
en l'estructura de dades de manera que a l'instant es pot anar a [0] [1], [30] o així successivament,

773
00:46:32,070 --> 00:46:36,480
però perquè tinguem una mica de flexibilitat i podem encaixar Anita i Alice i Adam

774
00:46:36,480 --> 00:46:38,630
i qualsevol altre Un nom,

775
00:46:38,630 --> 00:46:43,470
en lloc de deixar que l'altre eix créixer arbitràriament.

776
00:46:43,470 --> 00:46:47,340
I finalment, a partir de dilluns, tenen aquesta capacitat expressiva amb llista enllaçada.

777
00:46:47,340 --> 00:46:49,530
Es pot conrear una estructura de dades arbitrària.

778
00:46:49,530 --> 00:46:52,450
Com a alternativa, podríem fer una enorme varietat 2-dimensional,

779
00:46:52,450 --> 00:46:57,190
però això serà una situació terrible si una de les files d'una matriu 2-dimensional

780
00:46:57,190 --> 00:47:01,280
no és prou gran com perquè la persona addicional el nom passa a començar amb A.

781
00:47:01,280 --> 00:47:04,200
Déu ens lliure d'haver de reassignar un enorme 2-dimensional estructura

782
00:47:04,200 --> 00:47:06,600
només perquè hi ha tantes persones nomenades A,

783
00:47:06,600 --> 00:47:09,480
especialment quan hi ha tan poques persones nomenades alguna cosa Z.

784
00:47:09,480 --> 00:47:12,170
És només serà una estructura de dades molt escassos.

785
00:47:12,170 --> 00:47:15,400
Així que no és perfecte, per qualsevol mitjà, però ara almenys tenim la capacitat

786
00:47:15,400 --> 00:47:19,090
per trobar l'instant en què Alice o Anita pertany,

787
00:47:19,090 --> 00:47:21,090
si més no en termes de l'eix vertical,

788
00:47:21,090 --> 00:47:25,850
i llavors només hem de decidir on posar Anita o Alícia al país d'aquesta llista vinculada.

789
00:47:25,850 --> 00:47:32,480
Si no es preocupen per resoldre les coses, amb quina rapidesa podem inserir Alice en una estructura com aquesta?

790
00:47:32,480 --> 00:47:35,370
És temps constant. Ens índex en [0], i si no n'hi ha un,

791
00:47:35,370 --> 00:47:37,550
Alice va al començament de la llista vinculada.

792
00:47:37,550 --> 00:47:40,000
Però això no és un gran negoci. Perquè si Anita després ve

793
00:47:40,000 --> 00:47:42,160
un cert nombre de passos més endavant, d'on Anita pertany?

794
00:47:42,160 --> 00:47:45,140
Bé, [0]. Programació orientada a objectes. Alice es troba en aquesta llista enllaçada.

795
00:47:45,140 --> 00:47:47,760
>> Però si no et fa res la classificació d'aquests noms,

796
00:47:47,760 --> 00:47:53,580
que només pot moure a través d'Alice, inserir Anita, però fins i tot això és la constant de temps.

797
00:47:53,580 --> 00:47:57,010
Encara que no hi ha Alice i Adam i tots aquests altres noms A,

798
00:47:57,010 --> 00:47:59,410
en realitat no és que canviant físicament. Per què?

799
00:47:59,410 --> 00:48:04,090
Com que acabem de fer aquí amb llista enllaçada, qui sap van ser aquests nodes són de totes maneres?

800
00:48:04,090 --> 00:48:06,550
Tot el que has de fer és moure el pa ratllat.

801
00:48:06,550 --> 00:48:10,930
Moveu les fletxes voltant, vostè no ha de moure físicament les dades al voltant.

802
00:48:10,930 --> 00:48:14,610
Així que podem inserir Anita, en aquest cas, a l'instant. Constant de temps.

803
00:48:14,610 --> 00:48:20,250
Així que tenim temps constant de recerca, i la constant de temps d'inserció d'algú com Anita.

804
00:48:20,250 --> 00:48:22,740
Però espècie de simplificar en excés el món.

805
00:48:22,740 --> 00:48:28,510
I si més endavant decidiu trobar Alice?

806
00:48:28,510 --> 00:48:31,050
I si més endavant decidiu trobar Alice?

807
00:48:31,050 --> 00:48:35,690
Quants passos es que prendrà?

808
00:48:35,690 --> 00:48:37,850
[Resposta Estudiantil, inintel · ligible]

809
00:48:37,850 --> 00:48:40,950
Exactament. El nombre de persones abans que Alícia al país de la llista enllaçada.

810
00:48:40,950 --> 00:48:45,420
Així que no és del tot perfecte, perquè la nostra estructura de dades, un cop més, té aquest accés vertical

811
00:48:45,420 --> 00:48:50,240
i llavors té aquestes llistes enllaçades que pengen - en realitat, no cal dibuixar una matriu.

812
00:48:50,240 --> 00:48:56,020
Ha aquestes llistes enllaçades penjant d'ella que s'assembla una mica alguna cosa com això.

813
00:48:56,020 --> 00:48:59,110
Però el problema és que si Alice i Adam i tots aquests altres noms un

814
00:48:59,110 --> 00:49:01,720
acaben més i més enllà,

815
00:49:01,720 --> 00:49:04,810
trobar algú podria acabar tenint un munt de passos,

816
00:49:04,810 --> 00:49:06,670
bcause has de recórrer la llista enllaçada,

817
00:49:06,670 --> 00:49:08,090
que és una operació lineal.

818
00:49:08,090 --> 00:49:14,270
Així que en realitat, llavors, el temps d'inserció en última instància és O (n), on n és el nombre d'elements a la llista.

819
00:49:14,270 --> 00:49:21,780
Dividit per, anem arbitràriament anomenem m, on m és el nombre de llistes enllaçades

820
00:49:21,780 --> 00:49:24,500
que tenim en aquest eix vertical.

821
00:49:24,500 --> 00:49:27,180
En altres paraules, si realment suposen una distribució uniforme dels noms,

822
00:49:27,180 --> 00:49:30,150
totalment irreal. Òbviament hi ha més d'unes cartes que altres.

823
00:49:30,150 --> 00:49:32,580
>> Però si suposem de moment una distribució uniforme,

824
00:49:32,580 --> 00:49:37,350
i tenim n persones en total, i les cadenes de m totals

825
00:49:37,350 --> 00:49:40,630
disponibles per a nosaltres, llavors la longitud de cadascuna d'aquestes cadenes

826
00:49:40,630 --> 00:49:44,380
bastant simplement serà el total, n dividit pel nombre de cadenes.

827
00:49:44,380 --> 00:49:48,900
Llavors n / m. Però aquí és on podem ser matemàticament tot llest.

828
00:49:48,900 --> 00:49:53,030
m és una constant, ja que hi ha un nombre fix d'aquests.

829
00:49:53,030 --> 00:49:54,620
Vostè va a declarar l'array al principi,

830
00:49:54,620 --> 00:49:58,450
i no estem canviant la mida de l'eix vertical. Per definició, que roman fix.

831
00:49:58,450 --> 00:50:01,220
És només l'eix horitzontal, per dir-ho, això està canviant.

832
00:50:01,220 --> 00:50:04,760
Així que, tècnicament, és una constant. Així que ara, el temps d'inserció

833
00:50:04,760 --> 00:50:09,700
és més o menys O (n).

834
00:50:09,700 --> 00:50:12,410
Així que no se sent tot el que molt millor.

835
00:50:12,410 --> 00:50:14,940
Però, què és la veritat? Bé, tot aquest temps, durant setmanes,

836
00:50:14,940 --> 00:50:20,640
que hem estat dient O (n ²). O (n), 2 x n ², - n, dividit per 2. . . ech.

837
00:50:20,640 --> 00:50:23,580
És només ² n. Però ara, en aquesta part del semestre,

838
00:50:23,580 --> 00:50:25,560
podem començar a parlar sobre el món real de nou.

839
00:50:25,560 --> 00:50:31,520
I n / m és absolutament més ràpid que només n sol.

840
00:50:31,520 --> 00:50:35,170
Si vostè té mil noms, i els trenquen en cubs múltiples

841
00:50:35,170 --> 00:50:37,820
de manera que només té deu noms en cadascuna d'aquestes cadenes,

842
00:50:37,820 --> 00:50:41,670
buscant absolutament deu coses que serà més ràpid que un miler de coses.

843
00:50:41,670 --> 00:50:43,740
I així, un dels conjunts de problemes futurs serà desafiar

844
00:50:43,740 --> 00:50:46,100
a pensar exactament que tot i que, sí,

845
00:50:46,100 --> 00:50:49,520
asimptòticament i matemàticament, això és només lineal,

846
00:50:49,520 --> 00:50:51,700
que aspira, en general, quan es tracta de trobar les coses.

847
00:50:51,700 --> 00:50:54,530
En realitat, serà més ràpid que el

848
00:50:54,530 --> 00:50:56,520
perquè d'aquest divisor.

849
00:50:56,520 --> 00:50:58,310
Així que hi ha de nou serà aquest trade-off

850
00:50:58,310 --> 00:51:01,390
i aquest conflicte entre la teoria i la realitat,

851
00:51:01,390 --> 00:51:03,550
i un dels comandaments començarà a girar en aquest punt en el semestre

852
00:51:03,550 --> 00:51:07,510
és més aviat l'única realitat com una mena de preparació per a la final semster,

853
00:51:07,510 --> 00:51:09,280
com es presenta el món de la programació web,

854
00:51:09,280 --> 00:51:11,530
on realment, el rendiment explicarà perquè els usuaris van a

855
00:51:11,530 --> 00:51:14,880
comença a sentir i apreciar les males decisions de disseny.

856
00:51:14,880 --> 00:51:19,950
>> Llavors, com vostè va sobre la implementació d'un vinculat - una taula hash amb 31 elements?

857
00:51:19,950 --> 00:51:22,600
I l'exemple anterior va ser arbitràriament els aniversaris.

858
00:51:22,600 --> 00:51:26,190
Si algú té un aniversari l'1 de gener o l'1 de febrer, les posarem en aquest cub.

859
00:51:26,190 --> 00:51:28,960
Si es tracta de 02 de gener, 2 de febrer, 2 de març, els posarem en aquest cub.

860
00:51:28,960 --> 00:51:32,220
És per això que tenia 31 anys. Com es declara una taula hash?

861
00:51:32,220 --> 00:51:37,480
Pot ser molt simple, taula * node és el meu nom arbitrari per a ell, [31].

862
00:51:37,480 --> 00:51:42,400
Això em dóna 31 punters a nodes,

863
00:51:42,400 --> 00:51:45,370
i que em permet tenir 31 punters a llistes enllaçades

864
00:51:45,370 --> 00:51:48,800
fins i tot si aquestes cadenes són inicialment NULL.

865
00:51:48,800 --> 00:51:54,860
Què és el que vull fer si vull guardar "Alice", "Bob", "Charlie"?

866
00:51:54,860 --> 00:51:57,010
Bé, hem de embolicar les coses en una estructura

867
00:51:57,010 --> 00:52:00,530
perquè necessitem Alice perquè apunti a Bob, perquè apunti a Charlie, i així successivament.

868
00:52:00,530 --> 00:52:04,940
No podem tenir els noms sols, de manera que podria crear una nova estructura anomenada node aquí.

869
00:52:04,940 --> 00:52:08,310
>> Què és un node real? Què és un node en aquesta nova llista lligada?

870
00:52:08,310 --> 00:52:11,840
El primer, anomenat paraula, és el nom de la persona.

871
00:52:11,840 --> 00:52:14,340
LONGITUD, presumiblement, es refereix a la longitud màxima del nom d'un ésser humà,

872
00:52:14,340 --> 00:52:18,210
sigui el que sigui, 20, 30, 40 personatges en casos extrems bojos,

873
00:52:18,210 --> 00:52:22,680
i un és per què? És només el caràcter NULL extra, \ 0.

874
00:52:22,680 --> 00:52:27,410
Així que aquest node està acabant "alguna cosa" dins de si mateixa,

875
00:52:27,410 --> 00:52:29,640
sinó que també declara un punter anomenat proper

876
00:52:29,640 --> 00:52:32,580
perquè puguem cadena Alice a Bob a Charlie i així successivament.

877
00:52:32,580 --> 00:52:36,700
Pot ser NULL, però no necessàriament ha de ser.

878
00:52:36,700 --> 00:52:40,110
Qualsevol pregunta sobre aquestes taules hash? Sí?

879
00:52:40,110 --> 00:52:46,190
[Estudiant que fa la pregunta, inintel · ligible] Matriu - bona pregunta.

880
00:52:46,190 --> 00:52:50,120
Per què és aquesta paraula char en una matriu en lloc de només char *?

881
00:52:50,120 --> 00:52:53,830
En aquest exemple un tant arbitrari, no vull haver de recórrer

882
00:52:53,830 --> 00:52:56,190
a malloc per a cada un dels noms originals.

883
00:52:56,190 --> 00:52:59,530
Jo volia declarar una quantitat màxima de memòria per a la cadena

884
00:52:59,530 --> 00:53:06,020
perquè jo pogués copiar en l'estructura Alice \ 0 i no haver de bregar amb malloc i lliure i similars.

885
00:53:06,020 --> 00:53:11,710
Però podria fer-ho si volia ser més conscients de l'ús de l'espai. Bona pregunta.

886
00:53:11,710 --> 00:53:14,780
Així que anem a tractar de generalitzar lluny d'aquest

887
00:53:14,780 --> 00:53:18,350
i enfocar la resta d'avui en estructures de dades més generalment

888
00:53:18,350 --> 00:53:21,170
i altres problemes que es poden resoldre utilitzant els mateixos fonaments

889
00:53:21,170 --> 00:53:24,590
tot i que les estructures de dades es poden diferir en els seus detalls.

890
00:53:24,590 --> 00:53:27,910
>> Així que resulta en ciències de la computació, els arbres són molt comuns.

891
00:53:27,910 --> 00:53:29,760
I es pot pensar en una espècie d'arbre com un arbre genealògic,

892
00:53:29,760 --> 00:53:31,830
on hi ha algunes arrels, alguns matriarca o patriarca,

893
00:53:31,830 --> 00:53:34,540
àvia o l'avi o l'esquena abans,

894
00:53:34,540 --> 00:53:38,880
sota de la qual són mare i pare o germans diferents o similars.

895
00:53:38,880 --> 00:53:42,500
Així que una estructura d'arbre té nodes i té fills,

896
00:53:42,500 --> 00:53:45,260
normalment 0 o més fills de cada node.

897
00:53:45,260 --> 00:53:47,320
I alguns de l'argot que vostè veu en aquest dibuix aquí

898
00:53:47,320 --> 00:53:50,630
és qualsevol dels fills o néts petits a les vores

899
00:53:50,630 --> 00:53:52,330
que no tenen fletxes que emanen d'ells,

900
00:53:52,330 --> 00:53:55,070
aquestes són les fulles anomenats, i qualsevol persona a l'interior

901
00:53:55,070 --> 00:53:58,790
és un node intern, es pot dir qualsevol cosa per l'estil.

902
00:53:58,790 --> 00:54:01,430
No obstant això, aquesta estructura és bastant comú. Aquest és una mica arbitrària.

903
00:54:01,430 --> 00:54:04,930
Tenim un nen de l'esquerra, tenim tres fills a la dreta,

904
00:54:04,930 --> 00:54:06,830
dos nens a la part inferior esquerra.

905
00:54:06,830 --> 00:54:10,740
Així que podem tenir diferents arbres de mida, però si comencem a normalitzar les coses,

906
00:54:10,740 --> 00:54:15,330
i es pot recordar aquest vídeo de Patricio, en la recerca binària d'un curt anterior

907
00:54:15,330 --> 00:54:19,490
recerca en línia, binari no ha de ser implementat amb una matriu

908
00:54:19,490 --> 00:54:21,410
o trossos de paper en una pissarra.

909
00:54:21,410 --> 00:54:25,490
Suposem que voleu emmagatzemar els nombres en una estructura de dades més sofisticada.

910
00:54:25,490 --> 00:54:27,680
Es pot crear un arbre com aquest.

911
00:54:27,680 --> 00:54:35,290
Podria tenir un node declara en C, i que el node pot tenir com a mínim dos elements del seu interior.

912
00:54:35,290 --> 00:54:39,470
Un d'ells és el número que voleu emmagatzemar, i l'altre és - bé, necessitem un més.

913
00:54:39,470 --> 00:54:41,540
Els altres són els seus fills.

914
00:54:41,540 --> 00:54:45,150
Així que aquí està una altra estructura de dades. Aquesta vegada, un node es defineix com l'emmagatzematge d'un nombre n

915
00:54:45,150 --> 00:54:49,060
i després dos punters, fill esquerre i el fill dret.

916
00:54:49,060 --> 00:54:52,100
I no són arbitràries. El que és interessant sobre aquest arbre?

917
00:54:52,100 --> 00:55:00,550
>> Quin és el patró de la manera en què hem establert això o com Patrick es presenta en el seu vídeo?

918
00:55:00,550 --> 00:55:02,790
És bastant obvi que hi ha una classificació que passa aquí,

919
00:55:02,790 --> 00:55:04,460
però quina és la regla simple? Sí?

920
00:55:04,460 --> 00:55:08,350
[Resposta Estudiantil, inintel · ligible]

921
00:55:08,350 --> 00:55:12,040
Perfecte. Si fes un cop d'ull a això, veurà els números petits a l'esquerra,

922
00:55:12,040 --> 00:55:14,690
els grans nombres de l'esquerra, però això és cert per a cada node.

923
00:55:14,690 --> 00:55:20,370
Per a cada node, el seu fill esquerre menor que ell, i el seu fill gran dret que ell.

924
00:55:20,370 --> 00:55:25,210
El que això significa és que si vull cercar en aquesta estructura de dades per, per exemple, el número 44,

925
00:55:25,210 --> 00:55:29,320
He de començar des de l'arrel, perquè igual que amb totes aquestes estructures de dades més complexes ara,

926
00:55:29,320 --> 00:55:31,910
només tenim un punter a una sola cosa, el principi.

927
00:55:31,910 --> 00:55:35,010
I en aquest cas, el principi és l'arrel. No és l'extrem esquerre,

928
00:55:35,010 --> 00:55:39,530
que és l'arrel d'aquesta estructura. Així que veig aquí és de 55 anys, i estic buscant 44.

929
00:55:39,530 --> 00:55:41,430
En quina direcció vull anar?

930
00:55:41,430 --> 00:55:45,680
Bé, jo vull anar a l'esquerra, perquè, òbviament, a la dreta serà massa gran.

931
00:55:45,680 --> 00:55:49,050
Així notar aquí, estàs de sort conceptualment tallar l'arbre per la meitat

932
00:55:49,050 --> 00:55:51,700
perquè mai vas a baix a la dreta.

933
00:55:51,700 --> 00:55:55,410
Així que ara me n'aniré de la 55 a la 33. És massa petit d'un nombre.

934
00:55:55,410 --> 00:56:01,590
Estic buscant a 44, però ara sé que si 44 és en aquest arbre, puc anar, òbviament, a la dreta.

935
00:56:01,590 --> 00:56:04,460
Així que de nou, estic podant l'arbre per la meitat.

936
00:56:04,460 --> 00:56:06,780
És gairebé idèntic conceptualment a la guia telefònica.

937
00:56:06,780 --> 00:56:09,510
És idèntic al que vam fer amb els papers a la pissarra,

938
00:56:09,510 --> 00:56:13,940
però és una estructura més sofisticada que ens permet fer realitat

939
00:56:13,940 --> 00:56:16,880
aquest divideix i venceràs per disseny de l'algorisme,

940
00:56:16,880 --> 00:56:19,420
i, de fet, que travessa una estructura com aquesta - crits.

941
00:56:19,420 --> 00:56:22,870
Travessant una estructura com aquesta, on és només "anar per aquest camí o anar per aquest camí"

942
00:56:22,870 --> 00:56:26,870
significa tot el codi que es va inclinar a la seva ment en un primer moment, al posar-la en la secció

943
00:56:26,870 --> 00:56:31,270
o caminar a través d'ell a casa, per a la recerca binària, utilitzant recursió o iteració,

944
00:56:31,270 --> 00:56:35,060
és un dolor al coll. Busqui l'element central, a continuació, fer el seu arrodoniment cap amunt o cap avall.

945
00:56:35,060 --> 00:56:39,230
>> Hi ha una bellesa en això perquè ara podem utilitzar la recursivitat de nou,

946
00:56:39,230 --> 00:56:43,760
però molt més neta. De fet, si vostè és al número 55 i que desitja trobar 44,

947
00:56:43,760 --> 00:56:48,450
vostè va a l'esquerra en aquest cas, llavors, què fa vostè? Vostè corre el mateix algoritme exacte.

948
00:56:48,450 --> 00:56:51,560
Es comprova el valor del node, aneu a l'esquerra oa la dreta.

949
00:56:51,560 --> 00:56:53,670
A continuació, comproveu el valor del node, aneu a l'esquerra oa la dreta.

950
00:56:53,670 --> 00:56:56,710
Això s'adapta perfectament a la recursivitat.

951
00:56:56,710 --> 00:57:00,920
Així que, encara que en el passat hem fet alguns exemples bastant arbitràries que impliquen recursió

952
00:57:00,920 --> 00:57:03,430
que no tenia per què ser recursiu, amb stuctures de dades,

953
00:57:03,430 --> 00:57:07,820
especialment els arbres, és una perfecta aplicació d'aquesta idea de tenir un problema,

954
00:57:07,820 --> 00:57:12,920
contracció, i després resoldre el mateix tipus de, però més petit programa,.

955
00:57:12,920 --> 00:57:14,590
>> Així que hi ha una altra estructura de dades que podem introduir.

956
00:57:14,590 --> 00:57:18,760
Aquest està dissenyat a primera vista, sembla críptic, però això és increïble.

957
00:57:18,760 --> 00:57:25,090
Així que aquesta és una estructura de dades anomenada triennis, triennis, que s'hereta de la recuperació de paraules,

958
00:57:25,090 --> 00:57:30,210
que no es pronuncia re-try-val, però això és el que el món anomena aquestes coses. Tracta. T-r-i-i.

959
00:57:30,210 --> 00:57:35,190
Es tracta d'una estructura d'arbre d'algun tipus, però cada un dels nodes en un triennis

960
00:57:35,190 --> 00:57:41,280
sembla què? I això és una mica enganyós, ja que és una espècie de abreujat.

961
00:57:41,280 --> 00:57:45,960
Però sembla que cada node en aquest trienni és en realitat una matriu.

962
00:57:45,960 --> 00:57:48,840
I tot i que l'autor d'aquest diagrama no ho ha demostrat,

963
00:57:48,840 --> 00:57:54,130
en aquest cas, aquest triennis és una estructura de dades el propòsit a la vida és per emmagatzemar paraules

964
00:57:54,130 --> 00:57:57,330
com A-l-i-c-i o B-ob-.

965
00:57:57,330 --> 00:58:02,480
I la manera com aquestes dades emmagatzema Alice i Bob i Charlie i Anita i altres

966
00:58:02,480 --> 00:58:06,970
S'utilitza una matriu per emmagatzemar el qual Alícia al país d'un triennis,

967
00:58:06,970 --> 00:58:09,820
es comença en el node arrel que s'assembla a una matriu,

968
00:58:09,820 --> 00:58:12,080
i que ha estat escrit en notació abreujada.

969
00:58:12,080 --> 00:58:15,070
L'autor omet abcdefg perquè no havia noms amb això.

970
00:58:15,070 --> 00:58:19,150
Ells només va mostrar M i P i T, però en aquest cas,

971
00:58:19,150 --> 00:58:22,780
passarem lluny d'Alice i Bob i Charlie a alguns noms que són aquí.

972
00:58:22,780 --> 00:58:25,670
Maxwell és en realitat en aquest diagrama.

973
00:58:25,670 --> 00:58:29,570
Llavors, com va fer l'autor botiga M-a-x-w-i-l-l?

974
00:58:29,570 --> 00:58:36,990
Ell o ella va començar en el node arrel, i es va anar a [M], de manera més o menys 13, la 13 ª posició en la matriu.

975
00:58:36,990 --> 00:58:40,750
Després, des d'allà, hi ha un punter.

976
00:58:40,750 --> 00:58:42,760
Un punter que porta a una altra matriu.

977
00:58:42,760 --> 00:58:47,880
A partir d'aquí l'autor indexada en aquesta matriu en la posició A, com es mostra a la part superior esquerra hi ha,

978
00:58:47,880 --> 00:58:52,250
i llavors ell o ella va seguir a aquest punter a una altra matriu,

979
00:58:52,250 --> 00:58:55,460
i se'n va anar al punter en la ubicació X.

980
00:58:55,460 --> 00:58:59,840
Després, a la següent ubicació matriu W, E, L, L, i així successivament,

981
00:58:59,840 --> 00:59:03,090
i, finalment, tractarem de posar en realitat una imatge a aquesta.

982
00:59:03,090 --> 00:59:05,380
Com és un node com en el codi?

983
00:59:05,380 --> 00:59:11,820
Un node en un trienni conté una matriu de punters a més nodes.

984
00:59:11,820 --> 00:59:16,090
Però també cal ser algun tipus de valor booleà, si més no en aquesta implementació.

985
00:59:16,090 --> 00:59:18,770
Passa que em diuen is_word. Per què?

986
00:59:18,770 --> 00:59:22,670
Perquè quan vas a inserir Maxwell, vostè no està inserint

987
00:59:22,670 --> 00:59:25,300
res en aquesta estructura de dades.

988
00:59:25,300 --> 00:59:27,480
No estàs escrivint M. No estàs escrivint X.

989
00:59:27,480 --> 00:59:30,240
Tot el que estem fent és seguir punters.

990
00:59:30,240 --> 00:59:33,360
El punter que representa M, llavors el punter que representa A,

991
00:59:33,360 --> 00:59:36,310
a continuació, el punter que representa X, llavors W, E, L, L,

992
00:59:36,310 --> 00:59:41,950
però el que cal fer al final és una espècie d'anar, passar, vaig arribar a aquest lloc.

993
00:59:41,950 --> 00:59:45,560
Hi havia una paraula que acaba aquí, en l'estructura de dades.

994
00:59:45,560 --> 00:59:48,190
>> Llavors, què és realment un trienni plena i l'autor va triar per representar

995
00:59:48,190 --> 00:59:51,880
aquestes estacions terminals amb petits triangles.

996
00:59:51,880 --> 00:59:56,470
Això només vol dir que el fet d'aquest triangle és aquí, aquest valor booleà de true

997
00:59:56,470 --> 00:59:59,200
vol dir que si vostè va cap enrere en l'arbre,

998
00:59:59,200 --> 01:00:02,420
el que significa una paraula anomenada Maxwell està en això.

999
01:00:02,420 --> 01:00:04,870
Però la paraula foo, per exemple,

1000
01:00:04,870 --> 01:00:07,970
No heu arbre, perquè si em poso en el node arrel fins aquí a la part superior,

1001
01:00:07,970 --> 01:00:14,030
No hi ha cap indicador f, o no punter, punter o no. Foo no és un nom en aquest diccionari.

1002
01:00:14,030 --> 01:00:22,460
Però per contra, Turing, t-o-r-i-n-g. Un cop més, no emmagatzemar o o t o r i o n o g.

1003
01:00:22,460 --> 01:00:29,820
Però ho vaig fer botiga en aquesta estructura de dades un valor de veritable camí aquí en aquest node - a l'arbre

1004
01:00:29,820 --> 01:00:33,030
establint aquest valor booleà de is_word a true.

1005
01:00:33,030 --> 01:00:35,740
Així que un trienni és una espècie d'aquesta estructura meta molt interessant,

1006
01:00:35,740 --> 01:00:39,810
on vostè no està realment emmagatzemar les paraules mateixes d'aquest tipus de diccionari.

1007
01:00:39,810 --> 01:00:45,100
Perquè quedi clar, només estàs emmagatzemant si o no, hi ha una paraula que acaba aquí.

1008
01:00:45,100 --> 01:00:46,430
>> Ara, quina és la implicació?

1009
01:00:46,430 --> 01:00:51,120
Si té 150.000 paraules en un diccionari que vostè està tractant d'emmagatzemar en la memòria

1010
01:00:51,120 --> 01:00:53,400
utilitzen una part com una llista enllaçada,

1011
01:00:53,400 --> 01:00:56,870
vostè va a tenir 150.000 nodes a la llista enllaçada.

1012
01:00:56,870 --> 01:01:00,250
I trobar una d'aquestes paraules alfabèticament podria prendre O (n) temps.

1013
01:01:00,250 --> 01:01:04,370
El temps lineal. Però en el cas aquí d'un triennis,

1014
01:01:04,370 --> 01:01:09,210
Quin és el temps de durada de la recerca d'una paraula?

1015
01:01:09,210 --> 01:01:17,390
Resulta que la bellesa aquí és que encara que vostè té ja 149.999 paraules en aquest diccionari,

1016
01:01:17,390 --> 01:01:20,170
tal com s'aplica amb aquesta estructura de dades,

1017
01:01:20,170 --> 01:01:25,560
Quant de temps es triga a trobar o inserir una persona més en això, com Alice, Alice?

1018
01:01:25,560 --> 01:01:30,640
Bé, és només 5, potser 6 passos per al caràcter final.

1019
01:01:30,640 --> 01:01:32,880
Com que el presense d'altres noms en l'estructura

1020
01:01:32,880 --> 01:01:35,340
no posar-se en el camí de la inserció d'Alice.

1021
01:01:35,340 --> 01:01:39,640
D'altra banda, la recerca d'Alice vegada hi ha 150.000 paraules en aquest diccionari

1022
01:01:39,640 --> 01:01:41,960
no posar-se en el seu camí de recerca d'Alice en absolut,

1023
01:01:41,960 --> 01:01:46,880
perquè Alice és. . . . . aquí, perquè em vaig trobar amb un valor booleà.

1024
01:01:46,880 --> 01:01:50,920
I si no hi ha valor booleà veritable, llavors Alícia no està en aquesta estructura de dades de paraules.

1025
01:01:50,920 --> 01:01:56,220
En altres paraules, el temps d'execució de trobar coses i la inserció de les coses en aquest nou

1026
01:01:56,220 --> 01:02:01,920
estructura de dades del trienni és de O - no és n.

1027
01:02:01,920 --> 01:02:05,730
Com que el presense de 150.000 persones no té efecte en Alice, sembla.

1028
01:02:05,730 --> 01:02:11,560
Així que anem a dir k, on k és la longitud màxima d'una paraula en anglès

1029
01:02:11,560 --> 01:02:14,050
que és típicament no més de 20-alguna cosa caràcters.

1030
01:02:14,050 --> 01:02:17,940
Així que k és una constant. Així que el Sant Grial sembla que hem trobat ara

1031
01:02:17,940 --> 01:02:26,000
és la d'un temps triennis, constant per les insercions, per les recerques, per les delecions.

1032
01:02:26,000 --> 01:02:29,170
Com que el nombre de coses que ja estan en l'estructura,

1033
01:02:29,170 --> 01:02:32,600
que ni tan sols són físicament allà. Un cop més, són només una espècie de marcat, si o no,

1034
01:02:32,600 --> 01:02:35,050
no té impacte en el seu temps de funcionament futur.

1035
01:02:35,050 --> 01:02:37,940
>> Però hi ha d'haver un parany, en cas contrari no hauria perdut tant de temps

1036
01:02:37,940 --> 01:02:41,460
en totes aquestes estructures de dades només per finalment arribar a la un secret que és increïble.

1037
01:02:41,460 --> 01:02:46,410
Llavors, ¿quin preu estem pagant per assolir aquesta grandesa en aquesta llista? Espai.

1038
01:02:46,410 --> 01:02:49,010
Aquesta cosa és enorme. I la raó que l'autor

1039
01:02:49,010 --> 01:02:52,400
no ho presentem aquí, noti que totes aquestes coses que s'assemblen a les matrius,

1040
01:02:52,400 --> 01:02:55,400
no va treure la resta de l'arbre, la resta de la triennis,

1041
01:02:55,400 --> 01:02:58,060
perquè no són només rellevants per a la història.

1042
01:02:58,060 --> 01:03:01,870
Però tots aquests ganglis són super àmplia, i cada node en l'arbre de presa

1043
01:03:01,870 --> 01:03:07,780
26 o en realitat, podria ser 27 caràcters perquè en aquest cas jo estava amb espai perquè l'apòstrof

1044
01:03:07,780 --> 01:03:09,980
perquè puguem tenir paraules apòstrof.

1045
01:03:09,980 --> 01:03:14,450
En aquest cas, es tracta d'àmplies gammes. Així que, encara que no estan picutured,

1046
01:03:14,450 --> 01:03:18,190
això pren una quantitat massiva de RAM.

1047
01:03:18,190 --> 01:03:20,670
El que podria estar bé, especilly en maquinari modern,

1048
01:03:20,670 --> 01:03:25,650
però aquesta és la compensació. Tenim menys temps per la despesa de més espai.

1049
01:03:25,650 --> 01:03:28,580
Llavors, on està tot això anirà?

1050
01:03:28,580 --> 01:03:32,640
Bé, anem a fer - anem a veure aquí.

1051
01:03:32,640 --> 01:03:39,510
Anem a fer un salt a aquest tipus aquí.

1052
01:03:39,510 --> 01:03:43,450
>> El creguis o no, tan divertit com C ha estat per algun temps,

1053
01:03:43,450 --> 01:03:48,130
estem arribant a un punt en el semestre en que és el moment de fer la transició a les coses més modernes.

1054
01:03:48,130 --> 01:03:50,950
Les coses en un nivell superior. I tot i que durant el proper parell de setmanes

1055
01:03:50,950 --> 01:03:54,580
encara ens segueixen ens submergim en el món dels punters i la gestió de memòria

1056
01:03:54,580 --> 01:03:57,210
per aconseguir que la comoditat amb la qual es pot construir,

1057
01:03:57,210 --> 01:04:01,270
al final del joc és en última instància a introduir, irònicament, no aquesta llengua.

1058
01:04:01,270 --> 01:04:03,330
Passarem, com 10 minuts parlant HTML.

1059
01:04:03,330 --> 01:04:05,950
Tots HTML és un llenguatge de marques, i el que és un llenguatge de marques

1060
01:04:05,950 --> 01:04:10,220
És aquesta sèrie de claudàtors oberts i tancats suports que diuen "fer aquesta audaç"

1061
01:04:10,220 --> 01:04:12,000
"Fer això" cursiva "fer aquesta centrada.

1062
01:04:12,000 --> 01:04:14,250
No és tot el que intel · lectualment interessant, però és molt útil.

1063
01:04:14,250 --> 01:04:16,650
I sens dubte és omnipresent en aquests dies.

1064
01:04:16,650 --> 01:04:19,450
Però el que és de gran abast sobre el món d'HTML i programació web en general,

1065
01:04:19,450 --> 01:04:25,910
està construint coses dinàmiques, a programar en llenguatges com PHP o Python o Ruby o Java o C #.

1066
01:04:25,910 --> 01:04:30,360
En definitiva, sigui quin sigui el seu idioma d'elecció és, i generar HTML dinàmicament.

1067
01:04:30,360 --> 01:04:32,960
Generació d'una cosa anomenada CSS dinàmicament.

1068
01:04:32,960 --> 01:04:35,810
Fulls d'estil en cascada, que és també l'estètica.

1069
01:04:35,810 --> 01:04:41,360
I així, tot i que, avui en dia, si vaig a algun lloc web Google.com com el familiar,

1070
01:04:41,360 --> 01:04:46,100
i vaig a veure, desenvolupador, edita, el que potser vostè ha fet abans,

1071
01:04:46,100 --> 01:04:49,800
però anem a veure el codi font, això probablement es veu bastant críptic.

1072
01:04:49,800 --> 01:04:55,320
Però aquest és el codi subjacent que implementa Google.com.

1073
01:04:55,320 --> 01:04:57,940
A la part davantera. I en realitat tot això és matèria estètica suau i esponjosa.

1074
01:04:57,940 --> 01:05:01,740
Aquest és el CSS aquí. Si mantinc el desplaçament cap avall aconseguirem algunes coses amb codis de color.

1075
01:05:01,740 --> 01:05:06,890
Això és HTML. Codi de Google sembla un embolic, però si realment obrir una finestra diferent,

1076
01:05:06,890 --> 01:05:09,380
podem veure certa estructura a aquesta.

1077
01:05:09,380 --> 01:05:12,640
Si obro això, notar aquí, que és una mica més llegible.

1078
01:05:12,640 --> 01:05:16,850
Anem a veure ben aviat aquesta etiqueta, [paraula] és una etiqueta,

1079
01:05:16,850 --> 01:05:23,520
HTML, cap, cos, div, l'escriptura, l'àrea de text, l'amplada, centrada, div.

1080
01:05:23,520 --> 01:05:26,770
I això és també una espècie de misteriós aspecte a primera vista,

1081
01:05:26,770 --> 01:05:30,890
però tot aquest embolic segueix certs patrons i els patrons repetibles,

1082
01:05:30,890 --> 01:05:33,850
de manera que una vegada que tinguem els fonaments baix, vostè serà capaç d'escriure codi com aquest

1083
01:05:33,850 --> 01:05:37,550
i després manipular codi com aquest fent servir un altre llenguatge, anomenat JavaScript.

1084
01:05:37,550 --> 01:05:40,440
I JavaScript és un llenguatge que s'executa dins d'un navegador

1085
01:05:40,440 --> 01:05:44,380
avui que utilitzem en els cursos de la Universitat de Harvard, per descomptat, comprar l'eina que utilitza Google maps

1086
01:05:44,380 --> 01:05:48,660
per donar-li un munt de dinamisme, Facebook et dóna per mostrar actualitzacions instantànies d'estat,

1087
01:05:48,660 --> 01:05:51,430
Twitter s'utilitza per mostrar missatges de twitter instant.

1088
01:05:51,430 --> 01:05:53,820
Tot això, començarem a submergir polz

1089
01:05:53,820 --> 01:05:57,190
Però per arribar-hi, hem d'entendre una mica sobre l'Internet.

1090
01:05:57,190 --> 01:06:01,130
El vídeo aquí és només un minut de durada, i suposarem per ara això és, de fet,

1091
01:06:01,130 --> 01:06:08,380
com funciona Internet com un teaser del que està per venir. Et dono "Guerrers de la Xarxa".

1092
01:06:08,380 --> 01:06:14,720
>> [♫ ♫ música lenta cor]

1093
01:06:14,720 --> 01:06:20,450
[Narrador] Ell va venir amb un missatge.

1094
01:06:20,450 --> 01:06:23,770
Amb un protocol de tots els seus.

1095
01:06:23,770 --> 01:06:37,270
[♫ ♫ música electrònica més ràpida]

1096
01:06:37,270 --> 01:06:41,330
Ell va venir a un món de tallafocs fresc, despreocupat routers,

1097
01:06:41,330 --> 01:06:45,690
i els perills molt pitjors que la mort.

1098
01:06:45,690 --> 01:06:55,400
És ràpid. És fort. Ell és TCP / IP, i té el seu domicili.

1099
01:06:55,400 --> 01:06:59,250
Els guerrers de la xarxa.

1100
01:06:59,250 --> 01:07:05,290
[Malan] La setmana que ve, llavors. La Internet. Programació web. Això és CS50.

1101
01:07:05,290 --> 01:07:08,290
[CS50.TV]