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

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

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

4
00:00:08,000 --> 00:00:12,000
>> Això és CS50, i aquest és el començament de la Setmana 6,

5
00:00:12,000 --> 00:00:16,000
així que un parell de noves eines ja estan disponibles per tu per aprofitar,

6
00:00:16,000 --> 00:00:19,000
el primer dels quals es diu CS50 estil.

7
00:00:19,000 --> 00:00:22,000
El més probable és que si ets com jo o qualsevol dels companys docents,

8
00:00:22,000 --> 00:00:26,000
del que has vist un programa l'estil s'assembla una mica alguna cosa com això.

9
00:00:26,000 --> 00:00:30,000
Potser vostè comenci a tallar algunes cantonades a altes hores de la nit, o va a lluitar amb ell més tard,

10
00:00:30,000 --> 00:00:32,000
i després un TF o CA ve en horari d'oficina.

11
00:00:32,000 --> 00:00:34,000
Llavors és difícil per a nosaltres llegir.

12
00:00:34,000 --> 00:00:38,000
Doncs bé, aquest codi és sintàcticament correcta, i compilar voluntat, i s'executarà en realitat.

13
00:00:38,000 --> 00:00:40,000
Però definitivament no és un 5 per estil.

14
00:00:40,000 --> 00:00:45,000
>> Però ara, si ens endinsem en aquest directori here-

15
00:00:45,000 --> 00:00:48,000
i noti que tinc conditions2.c-

16
00:00:48,000 --> 00:00:55,000
i em trobo amb aquest nou ordre, style50, en aquesta conditions2.c arxiu, Intro,

17
00:00:55,000 --> 00:00:57,000
compte que m'ha informat que ha estat estilitzada.

18
00:00:57,000 --> 00:01:00,000
Gedit adonar que l'arxiu ha estat canviat al disc,

19
00:01:00,000 --> 00:01:08,000
i si faig clic a recarregar, tots els seus problemes s'han automatitzat.

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

21
00:01:15,000 --> 00:01:17,000
Aquesta és una de les coses que vam fer aquest cap de setmana.

22
00:01:17,000 --> 00:01:20,000
Reconeixem que és imperfecte, perquè hi ha una mica de codi

23
00:01:20,000 --> 00:01:23,000
que simplement no serà capaç d'estilitzar perfectament,

24
00:01:23,000 --> 00:01:26,000
però s'adonen això és ara una eina que pot aprofitar

25
00:01:26,000 --> 00:01:33,000
encara que només sigui per posar en ordre alguns dels aparells més equivocadament col · locat claus i similars.

26
00:01:33,000 --> 00:01:36,000
>> Però ara és més convincent CS50 Check.

27
00:01:36,000 --> 00:01:39,000
Amb CS50 xec, vostè pot realitzar les proves de regularitat mateixos

28
00:01:39,000 --> 00:01:42,000
en el seu propi codi que els becaris d'ensenyament són capaços de fer-ho.

29
00:01:42,000 --> 00:01:44,000
Aquesta és una utilitat de línia de comandes que es proporciona en l'aparell

30
00:01:44,000 --> 00:01:46,000
tan aviat com ho fa un update50 com per

31
00:01:46,000 --> 00:01:49,000
pset 4 especificacions, i l'utilitza essencialment com aquest.

32
00:01:49,000 --> 00:01:51,000
Executa la comanda check50.

33
00:01:51,000 --> 00:01:56,000
Després es passa un argument de línia d'ordres, o més generalment conegut com un interruptor o una bandera.

34
00:01:56,000 --> 00:01:58,000
En general, les coses que tenen guions es diu un interruptor

35
00:01:58,000 --> 00:02:02,000
a un programa de línia de comandes, de manera que-c especifica

36
00:02:02,000 --> 00:02:04,000
els xecs que desitja executar.

37
00:02:04,000 --> 00:02:07,000
>> Les proves que desitja executar s'identifiquen individualment per aquesta cadena,

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

39
00:02:10,000 --> 00:02:13,000
En altres paraules, això és només una cadena arbitrària però única

40
00:02:13,000 --> 00:02:18,000
que utilitzem per identificar de forma exclusiva les proves 4 pset de correcció.

41
00:02:18,000 --> 00:02:21,000
I llavors s'especifica una llista separada per espais dels arxius que voleu carregar

42
00:02:21,000 --> 00:02:24,000
per CS50 Check per a la seva anàlisi.

43
00:02:24,000 --> 00:02:29,000
Per exemple, si entro a la meva solució aquí per resize.c-

44
00:02:29,000 --> 00:02:31,000
permetin-me obrir un terminal més gran de finestra

45
00:02:31,000 --> 00:02:42,000
i segueixo endavant i executar diguem check50-c 2012/pset4/resize,

46
00:02:42,000 --> 00:02:46,000
i després seguir endavant i especificar els noms dels arxius,

47
00:02:46,000 --> 00:02:49,000
resize.c, a continuació, premeu la tecla Enter, es comprimeix,

48
00:02:49,000 --> 00:02:53,000
que es carrega, es comprova, i m'acaba de fallar un munt de proves.

49
00:02:53,000 --> 00:02:59,000
Qui està en vermell a la part superior esquerra que diu resize.c i bmp existeix.

50
00:02:59,000 --> 00:03:01,000
Aquesta era la prova. Aquesta va ser la pregunta que ens fèiem.

51
00:03:01,000 --> 00:03:04,000
I és trist perquè la resposta era falsa.

52
00:03:04,000 --> 00:03:08,000
El text en blanc sota ella diu espera bmp.h d'existir, i això és simplement la meva culpa.

53
00:03:08,000 --> 00:03:11,000
Em vaig oblidar de pujar, així que he de pujar dos arxius,

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

55
00:03:14,000 --> 00:03:17,000
Però ara notin totes les altres proves són de color groc perquè no s'han executat,

56
00:03:17,000 --> 00:03:21,000
de manera que la cara somrient és vertical perquè no és ni alegre ni trist,

57
00:03:21,000 --> 00:03:25,000
però hem de corregir aquest problema en vermell abans que aquests altres controls s'executarà.

58
00:03:25,000 --> 00:03:27,000
>> Anem a arreglar això.

59
00:03:27,000 --> 00:03:30,000
Permetin-me fer un zoom cap a fora i tornar a executar aquesta, aquest cop amb bmp.h també

60
00:03:30,000 --> 00:03:34,000
en la línia d'ordres, escriviu, i ara, si tot va bé,

61
00:03:34,000 --> 00:03:38,000
que va a revisar i tornar a conseqüència d'aguantar la respiració-

62
00:03:38,000 --> 00:03:42,000
tot verd, el que significa que estic fent realment bé en pset 4 fins al moment.

63
00:03:42,000 --> 00:03:44,000
Vostè pot veure i deduir del text descriptiu aquí

64
00:03:44,000 --> 00:03:47,000
exactament què és el que vam provar.

65
00:03:47,000 --> 00:03:49,000
Provem primer què els arxius existeixen?

66
00:03:49,000 --> 00:03:51,000
Hem provat llavors es compila resize.c?

67
00:03:51,000 --> 00:03:58,000
Després vam provar no canviar la seva mida una BMP de 1x1 píxels quan n, el factor de canvi de mida, és 1.

68
00:03:58,000 --> 00:04:01,000
Ara, si vostè no té idea del que n és que una vegada que explorem pset 4,

69
00:04:01,000 --> 00:04:04,000
sinó que simplement és un simple control per assegurar-se que vostè no és el canvi de mida

70
00:04:04,000 --> 00:04:08,000
una imatge en absolut si el factor de canvi de mida 1.

71
00:04:08,000 --> 00:04:14,000
Si, per contra, canvia la mida d'un píxel de 1x1 per a un 1x1 2x2 píxels a BMP correctament

72
00:04:14,000 --> 00:04:19,000
quan n és 2, llavors similarment, mina de forma consegüent.

73
00:04:19,000 --> 00:04:22,000
>> En definitiva, es pretén, un, prendre la cruïlla dels dits

74
00:04:22,000 --> 00:04:25,000
fora de l'equació adequada per a vostè abans de presentar el seu conjunt de processadors.

75
00:04:25,000 --> 00:04:28,000
Vostè sabrà exactament el que el seu TF aviat sabrà

76
00:04:28,000 --> 00:04:30,000
quan vostè va sobre la presentació d'alguns d'aquests conjunts de problemes,

77
00:04:30,000 --> 00:04:34,000
i també la motivació pedagògica és realment posar

78
00:04:34,000 --> 00:04:37,000
l'oportunitat davant teu perquè quan es coneix a priori

79
00:04:37,000 --> 00:04:39,000
que no hi ha errors en el codi i proves que no es passen,

80
00:04:39,000 --> 00:04:43,000
vostè pot posar en més temps efectiu per avançat per resoldre aquests problemes

81
00:04:43,000 --> 00:04:45,000
en lloc de perdre punts, obtenir retroalimentació de la seva TF,

82
00:04:45,000 --> 00:04:48,000
i després, "Ahh," com jo hauria d'haver imaginat.

83
00:04:48,000 --> 00:04:50,000
Ara almenys hi ha una eina per ajudar a trobar això.

84
00:04:50,000 --> 00:04:52,000
No va a assenyalar que l'error és, però li dirà

85
00:04:52,000 --> 00:04:54,000
el que és un símptoma de la mateixa.

86
00:04:54,000 --> 00:04:57,000
>> Ara s'adonen que les proves no són necessàriament exhaustives.

87
00:04:57,000 --> 00:04:59,000
El fet que vostè rep una pàgina amb la cares somrients verd

88
00:04:59,000 --> 00:05:02,000
no significa que el seu codi és perfecte, però significa

89
00:05:02,000 --> 00:05:06,000
que ha passat certes proves prescrites per l'especificació.

90
00:05:06,000 --> 00:05:08,000
De vegades no ens donarà a conèixer els xecs.

91
00:05:08,000 --> 00:05:10,000
Per exemple, whodunit, un dels aspectes del conjunt de processadors 4,

92
00:05:10,000 --> 00:05:15,000
és una mica decebedor si li donem

93
00:05:15,000 --> 00:05:18,000
la resposta en quant al que és, i hi ha un nombre de maneres de revelar

94
00:05:18,000 --> 00:05:21,000
que la persona està en que el soroll vermell.

95
00:05:21,000 --> 00:05:24,000
L'especificació sempre s'especificaran en el futur per pset 5 en endavant

96
00:05:24,000 --> 00:05:26,000
quins controls hi per a tu.

97
00:05:26,000 --> 00:05:28,000
Es donarà compte de que hi ha aquesta URL blanc a la part inferior.

98
00:05:28,000 --> 00:05:30,000
Per ara, això és només la sortida de diagnòstic.

99
00:05:30,000 --> 00:05:33,000
Si vas a visitar aquesta URL, tindràs un munt de missatges críptics bojos,

100
00:05:33,000 --> 00:05:36,000
que el convidem a mirar a través, però és sobretot per al personal

101
00:05:36,000 --> 00:05:41,000
perquè puguem diagnosticar i depurar errors en check50 si mateix.

102
00:05:41,000 --> 00:05:46,000
>> Sense preàmbuls, anem a passar a on el deixem.

103
00:05:46,000 --> 00:05:48,000
CS50 biblioteca prenem per fet durant algunes setmanes,

104
00:05:48,000 --> 00:05:52,000
però la setmana passada, vam començar traient una de les capes de la mateixa.

105
00:05:52,000 --> 00:05:55,000
Comencem posant de banda cadena a favor del que en el seu lloc?

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

107
00:05:57,000 --> 00:05:59,000
* Char, que ha estat un char * tot aquest temps,

108
00:05:59,000 --> 00:06:03,000
però ara no hem de fer veure que és una cadena de dades actual tipus.

109
00:06:03,000 --> 00:06:06,000
Més aviat, ha estat un sinònim de tipus de char *,

110
00:06:06,000 --> 00:06:09,000
i una cadena és una seqüència de caràcters,

111
00:06:09,000 --> 00:06:14,000
Per què té sentit per representar cadenes com char * s?

112
00:06:14,000 --> 00:06:20,000
Què fa un char * representen en el context d'aquest concepte d'una cadena?

113
00:06:20,000 --> 00:06:23,000
Si. >> [Estudiant] El primer caràcter.

114
00:06:23,000 --> 00:06:25,000
Bé, el primer caràcter, però no és el primer caràcter.

115
00:06:25,000 --> 00:06:27,000
Són els-[Els estudiants] Direcció.

116
00:06:27,000 --> 00:06:29,000
Bé, la direcció del primer caràcter.

117
00:06:29,000 --> 00:06:33,000
Tot el que és necessari per representar una cadena a la memòria d'un ordinador

118
00:06:33,000 --> 00:06:36,000
és només l'adreça de la seva byte molt primer.

119
00:06:36,000 --> 00:06:38,000
Vostè ni tan sols ha de saber quant temps és

120
00:06:38,000 --> 00:06:42,000
perquè com pot vostè donar-se compte d'això dinàmicament?

121
00:06:42,000 --> 00:06:44,000
[Estudiant] longitud de cadena.

122
00:06:44,000 --> 00:06:48,000
Vostè pot trucar longitud de la cadena, excel · lent, però com funciona la cadena de longitud?

123
00:06:48,000 --> 00:06:50,000
Què fer? Si.

124
00:06:50,000 --> 00:06:52,000
[Estudiant] Segueix endavant fins que arribi el caràcter nul.

125
00:06:52,000 --> 00:06:54,000
Sí, exacte, simplement itera amb un bucle for, while,

126
00:06:54,000 --> 00:06:57,000
el de * fins al final, i el final està representat

127
00:06:57,000 --> 00:07:01,000
per \ 0, el caràcter nul trucada, nul,

128
00:07:01,000 --> 00:07:05,000
no confondre amb un valor nul, que és un punter,

129
00:07:05,000 --> 00:07:07,000
que entrarà en la conversa de nou avui.

130
00:07:07,000 --> 00:07:11,000
>> Ens va desprendre una capa de getInt, i després va fer una ullada a GetString,

131
00:07:11,000 --> 00:07:14,000
i recordar que aquestes dues funcions, o en realitat,

132
00:07:14,000 --> 00:07:18,000
GetString, utilitzava una determinada funció

133
00:07:18,000 --> 00:07:21,000
per analitzar en realitat, és a dir, llegir i analitzar, l'entrada de l'usuari.

134
00:07:21,000 --> 00:07:25,000
I quina era aquesta nova funció?

135
00:07:25,000 --> 00:07:27,000
Scanf o sscanf. En realitat, ve en sabors diferents.

136
00:07:27,000 --> 00:07:31,000
Hi ha scanf, hi sscanf, hi fscanf.

137
00:07:31,000 --> 00:07:35,000
Per ara, però, ens centrarem en la més fàcilment il · lustrat,

138
00:07:35,000 --> 00:07:38,000
i m'ho dius a mi seguir endavant i obrir l'aparell

139
00:07:38,000 --> 00:07:41,000
un arxiu d'aquest tipus, scanf1.c.

140
00:07:41,000 --> 00:07:43,000
Aquest és un programa super simple,

141
00:07:43,000 --> 00:07:46,000
sinó que fa una cosa que mai hem fet

142
00:07:46,000 --> 00:07:48,000
sense l'ajuda de la biblioteca CS50.

143
00:07:48,000 --> 00:07:51,000
Això aconsegueix un int d'un usuari. Com funciona?

144
00:07:51,000 --> 00:07:53,000
Doncs bé, en la línia 16 hi,

145
00:07:53,000 --> 00:07:56,000
adonar que declarem una x int anomenat, i en aquest moment de la història,

146
00:07:56,000 --> 00:07:58,000
Quin és el valor de x?

147
00:07:58,000 --> 00:08:00,000
[Resposta dels estudiants inaudible]

148
00:08:00,000 --> 00:08:02,000
[David M.] És clar, qui sap, algun valor potencialment escombraries, de manera que en el 17, que acabem d'indicar a l'usuari

149
00:08:02,000 --> 00:08:06,000
dóna'm un nombre, si us plau, i el pas 18 és on es posa interessant.

150
00:08:06,000 --> 00:08:11,000
Scanf sembla demanar prestada una idea de printf en que utilitza aquests codis de format entre cometes.

151
00:08:11,000 --> 00:08:13,000
D% és per suposat un nombre decimal.

152
00:08:13,000 --> 00:08:21,000
Però per què estic passant & x en lloc de x només?

153
00:08:21,000 --> 00:08:24,000
El primer és la correcta. Si.

154
00:08:24,000 --> 00:08:26,000
[Resposta dels estudiants inaudible]

155
00:08:26,000 --> 00:08:31,000
Exactament, si l'objectiu d'aquest programa, igual que el getInt funció en si mateixa,

156
00:08:31,000 --> 00:08:34,000
és aconseguir un int per part de l'usuari que pot passar funcions

157
00:08:34,000 --> 00:08:38,000
totes les variables que vull, però si no passar-los per referència

158
00:08:38,000 --> 00:08:41,000
o per adreça o punter, tots sinònims per als propòsits actuals,

159
00:08:41,000 --> 00:08:46,000
després que la funció no té la capacitat de canviar el contingut d'aquesta variable.

160
00:08:46,000 --> 00:08:49,000
Això passaria en una còpia de la mateixa manera que la versió amb errors d'intercanvi

161
00:08:49,000 --> 00:08:51,000
que ja hem parlat un parell de vegades ara.

162
00:08:51,000 --> 00:08:54,000
>> Però en canvi, en fer & x, estic literalment passant a què?

163
00:08:54,000 --> 00:08:57,000
[Estudiant] La direcció. >> La direcció de x.

164
00:08:57,000 --> 00:09:01,000
És com dibuixar un mapa per a la funció anomenada scanf i dient aquí,

165
00:09:01,000 --> 00:09:04,000
aquestes són indicacions de com un tros de memòria a l'ordinador

166
00:09:04,000 --> 00:09:07,000
que es pot anar emmagatzemar algun sencer polz

167
00:09:07,000 --> 00:09:10,000
Per sscanf fer ara que

168
00:09:10,000 --> 00:09:13,000
quin operador, quin tros de sintaxi es va a haver de fer servir

169
00:09:13,000 --> 00:09:19,000
encara que no podem veure perquè algú va escriure aquesta funció?

170
00:09:19,000 --> 00:09:21,000
En altres paraules - què és això?

171
00:09:21,000 --> 00:09:23,000
[Estudiant] X llegir.

172
00:09:23,000 --> 00:09:27,000
Serà una mica de lectura, però només pel que fa a x aquí.

173
00:09:27,000 --> 00:09:30,000
Si scanf s'està passant la direcció de x,

174
00:09:30,000 --> 00:09:35,000
sintàcticament, quin operador està obligat a existir en algun lloc

175
00:09:35,000 --> 00:09:38,000
dins de l'aplicació, de manera que scanf scanf

176
00:09:38,000 --> 00:09:42,000
en realitat es pot escriure un nombre de 2 a aquesta direcció?

177
00:09:42,000 --> 00:09:44,000
Sí, així que l'arxiu *.

178
00:09:44,000 --> 00:09:47,000
Recordem que el * és el nostre operador per desfer referències, que essencialment significa anar-hi.

179
00:09:47,000 --> 00:09:50,000
>> Quan hagi estat lliurada una adreça, com és el cas aquí,

180
00:09:50,000 --> 00:09:53,000
scanf és, probablement-si en realitat es veia voltant del seu codi font-

181
00:09:53,000 --> 00:09:59,000
fa * x o l'equivalent d'anar realment a aquesta direcció i posar una mica de valor allà.

182
00:09:59,000 --> 00:10:02,000
Ara, pel que fa a com scanf té entrada des del teclat,

183
00:10:02,000 --> 00:10:04,000
anem a agitar les nostres mans per avui.

184
00:10:04,000 --> 00:10:07,000
Simplement assumeix que el sistema operatiu permet parlar sscanf

185
00:10:07,000 --> 00:10:11,000
per el teclat de l'usuari, però en aquest punt ara en línia 19,

186
00:10:11,000 --> 00:10:14,000
quan simplement imprimir x, que sembla ser el cas

187
00:10:14,000 --> 00:10:17,000
scanf que ha posat en int x.

188
00:10:17,000 --> 00:10:19,000
Així és exactament com funciona scanf, i recordar la setmana passada

189
00:10:19,000 --> 00:10:25,000
així és exactament com GetString i getInt i la seva altra família de funcions

190
00:10:25,000 --> 00:10:28,000
en última instància, funciona, encara que amb una lleugera variació com sscanf,

191
00:10:28,000 --> 00:10:31,000
el que significa escanejar una cadena en lloc del teclat.

192
00:10:31,000 --> 00:10:33,000
Però donem una ullada a una variació poc d'això.

193
00:10:33,000 --> 00:10:37,000
En scanf2, realment fotut.

194
00:10:37,000 --> 00:10:42,000
El que està malament, i jo vaig a amagar el comentari que explica tant-

195
00:10:42,000 --> 00:10:47,000
el que està malament amb aquest programa, la versió 2?

196
00:10:47,000 --> 00:10:55,000
Sigui el més tècnica possible aquest moment.

197
00:10:55,000 --> 00:10:57,000
Es veu bastant bé.

198
00:10:57,000 --> 00:11:03,000
Està molt ben marcada, però-

199
00:11:03,000 --> 00:11:07,000
bé, què hem de podar fins més curtes preguntes?

200
00:11:07,000 --> 00:11:17,000
Línia 16. Quina és la línia 16 fa en anglès precisa però tècnica?

201
00:11:17,000 --> 00:11:20,000
Aconseguir una mica incòmode. Sí, Michael.

202
00:11:20,000 --> 00:11:25,000
[Estudiant] S'assenyala a la primera lletra d'una cadena.

203
00:11:25,000 --> 00:11:27,000
>> Bé, prop. Permetin-me d'ajustar una mica.

204
00:11:27,000 --> 00:11:33,000
Referint-se a la primera lletra d'una cadena, es declara una variable anomenada memòria intermèdia

205
00:11:33,000 --> 00:11:36,000
que apunti a la direcció primera d'una cadena,

206
00:11:36,000 --> 00:11:39,000
o més aviat, que s'assenyalen més específicament a un char.

207
00:11:39,000 --> 00:11:42,000
Tingueu en compte que no és en realitat apunta enlloc perquè no hi ha cap operador d'assignació.

208
00:11:42,000 --> 00:11:46,000
No hi ha cap signe d'igual, així que tot el que estem fent és assignar la memòria intermèdia anomenat variable.

209
00:11:46,000 --> 00:11:49,000
Li passa a ser de 32 bits, ja que és un punter,

210
00:11:49,000 --> 00:11:52,000
i el contingut del buffer presumiblement eventualment

211
00:11:52,000 --> 00:11:57,000
contindrà la direcció d'un char, però per ara, el que conté buffer?

212
00:11:57,000 --> 00:11:59,000
Només una mica fals, qui sap, una mica d'escombraries valor,

213
00:11:59,000 --> 00:12:03,000
perquè no s'ha inicialitzat explícitament, de manera que no s'ha d'assumir res.

214
00:12:03,000 --> 00:12:06,000
Bé, ara la línia 17 és-què significa fer la línia 17?

215
00:12:06,000 --> 00:12:08,000
Potser això s'escalfarà això.

216
00:12:08,000 --> 00:12:10,000
S'imprimeix una cadena, no?

217
00:12:10,000 --> 00:12:12,000
Imprimeix cadena si us plau.

218
00:12:12,000 --> 00:12:15,000
>> La línia 18 és una mena de familiar ara que acabem de veure una variació d'aquesta

219
00:12:15,000 --> 00:12:18,000
però amb un codi de format diferent, de manera que en la línia 18,

220
00:12:18,000 --> 00:12:23,000
li estem dient aquí scanf és la direcció d'un tros de memòria.

221
00:12:23,000 --> 00:12:27,000
Vull que soni en una cadena, com es dedueix de% s,

222
00:12:27,000 --> 00:12:32,000
però el problema és que no hem fet un parell de coses aquí.

223
00:12:32,000 --> 00:12:35,000
Quin és un dels problemes?

224
00:12:35,000 --> 00:12:38,000
[Estudiant] Està tractant d'eliminar la referència a un punter nul.

225
00:12:38,000 --> 00:12:41,000
Bé, punters nuls o simplement desconeix el contrari.

226
00:12:41,000 --> 00:12:45,000
Ets lliurant scanf una direcció, però que acaba de dir fa un moment

227
00:12:45,000 --> 00:12:49,000
que aquesta direcció és un valor escombraries perquè en realitat no ens assignar-la a res,

228
00:12:49,000 --> 00:12:53,000
i pel que estem dient scanf disponible ens va posar una corda aquí,

229
00:12:53,000 --> 00:12:56,000
però no sabem on és aquí encara,

230
00:12:56,000 --> 00:12:59,000
pel que no s'han assignat per a la memòria buffer.

231
00:12:59,000 --> 00:13:03,000
D'altra banda, el que tampoc són encara comptant scanf?

232
00:13:03,000 --> 00:13:06,000
Suposem que es tractava d'un tros de memòria, i no era un valor escombraries,

233
00:13:06,000 --> 00:13:09,000
però encara no estàs dient scanf alguna cosa important.

234
00:13:09,000 --> 00:13:12,000
[Estudiant] Quan en realitat, el símbol d'unió.

235
00:13:12,000 --> 00:13:15,000
Ampersand, pel que en aquest cas, està bé.

236
00:13:15,000 --> 00:13:18,000
A causa de límit ja s'ha declarat com un apuntador

237
00:13:18,000 --> 00:13:22,000
amb la peça * de sintaxi, no cal utilitzar ampersand

238
00:13:22,000 --> 00:13:25,000
perquè ja és una direcció, però crec que el van escoltar aquí.

239
00:13:25,000 --> 00:13:27,000
[Estudiant] Com és de gran?

240
00:13:27,000 --> 00:13:29,000
Bé, no estem dient scanf el gran que és aquest tampó,

241
00:13:29,000 --> 00:13:32,000
el que significa que encara que tampó eren un punter,

242
00:13:32,000 --> 00:13:35,000
estem dient scanf, posar una cadena aquí,

243
00:13:35,000 --> 00:13:38,000
però aquí podria ser 2 bytes, que pot ser de 10 bytes, que podria ser un megabyte.

244
00:13:38,000 --> 00:13:41,000
Scanf té ni idea, i perquè es tracta d'un tros de memòria

245
00:13:41,000 --> 00:13:43,000
presumiblement, no és una cadena encara.

246
00:13:43,000 --> 00:13:48,000
No és més que una cadena un cop d'escriure caràcters i un 0 \ a que bona part de la memòria.

247
00:13:48,000 --> 00:13:51,000
Ara és només una mica de bona part de la memòria.

248
00:13:51,000 --> 00:13:55,000
Scanf no se sap quan deixar d'escriure a aquesta adreça.

249
00:13:55,000 --> 00:13:59,000
>> Si recorda alguns exemples en el passat en què s'escriuen a l'atzar en el teclat

250
00:13:59,000 --> 00:14:03,000
intentant desbordar un buffer, i parlem el divendres sobre exactament això.

251
00:14:03,000 --> 00:14:07,000
Si un adversari d'alguna manera injecta en el seu programa una paraula molt més gran

252
00:14:07,000 --> 00:14:10,000
o oració o frase després que esperaves pot envair

253
00:14:10,000 --> 00:14:13,000
un tros de memòria, que pot tenir conseqüències negatives,

254
00:14:13,000 --> 00:14:15,000
com fer-se càrrec de tot el programa en si.

255
00:14:15,000 --> 00:14:17,000
Hem d'arreglar això d'alguna manera.

256
00:14:17,000 --> 00:14:20,000
Permetin-me fer un zoom cap a fora i entrar a la versió 3 d'aquest programa.

257
00:14:20,000 --> 00:14:22,000
Això és una mica millor.

258
00:14:22,000 --> 00:14:24,000
En aquesta versió, notarà la diferència.

259
00:14:24,000 --> 00:14:27,000
En la línia 16, estic de nou que es declara una variable anomenada memòria intermèdia,

260
00:14:27,000 --> 00:14:29,000
però què passa ara?

261
00:14:29,000 --> 00:14:33,000
És un conjunt de 16 caràcters.

262
00:14:33,000 --> 00:14:36,000
Això és bo perquè significa que ara puc dir scanf

263
00:14:36,000 --> 00:14:39,000
aquí és un tros real de memòria.

264
00:14:39,000 --> 00:14:42,000
Gairebé es pot pensar a una matriu com punters ara,

265
00:14:42,000 --> 00:14:44,000
tot i que no són realment equivalents.

266
00:14:44,000 --> 00:14:47,000
Ells es comporten de manera diferent en diferents contextos.

267
00:14:47,000 --> 00:14:50,000
Però és cert que memòria intermèdia fa referència

268
00:14:50,000 --> 00:14:53,000
16 caràcters contigus perquè això és el que una matriu és

269
00:14:53,000 --> 00:14:55,000
i ha estat durant algunes setmanes.

270
00:14:55,000 --> 00:14:59,000
>> Mira, estic dient scanf aquí hi ha un tros de memòria.

271
00:14:59,000 --> 00:15:01,000
Aquesta vegada, és en realitat una part de la memòria,

272
00:15:01,000 --> 00:15:07,000
però per què és aquest programa encara explotable?

273
00:15:07,000 --> 00:15:11,000
Què hi ha de dolent encara?

274
00:15:11,000 --> 00:15:14,000
Ho he dit dóna'm 16 bytes però-

275
00:15:14,000 --> 00:15:16,000
[Estudiant] I si s'escriu en més de 16?

276
00:15:16,000 --> 00:15:20,000
Exactament, què passa si l'usuari escriu en 17 caràcters o caràcters 1700?

277
00:15:20,000 --> 00:15:23,000
De fet, anem a veure si no es ensopegui amb aquest error ara.

278
00:15:23,000 --> 00:15:25,000
És millor, però no és perfecte.

279
00:15:25,000 --> 00:15:28,000
Deixin-me seguir endavant i fer funcionar scanf3 per compilar aquest programa.

280
00:15:28,000 --> 00:15:34,000
Deixa córrer scanf3, String si us plau: hola, i sembla que estem bé.

281
00:15:34,000 --> 00:15:37,000
Vaig a tractar un lleugerament més llarg, hola.

282
00:15:37,000 --> 00:15:42,000
Bé, anem a fer-ho hola com estàs avui, Enter.

283
00:15:42,000 --> 00:15:54,000
Aconseguir tipus de sort aquí, anem a dir hola com estàs.

284
00:15:54,000 --> 00:15:56,000
Maleïda sigui.

285
00:15:56,000 --> 00:16:03,000
Molt bé, així que vam tenir sort. A veure si podem arreglar això.

286
00:16:03,000 --> 00:16:06,000
No, no deixarà que em còpia.

287
00:16:06,000 --> 00:16:09,000
Anem a intentar-ho de nou.

288
00:16:09,000 --> 00:16:12,000
D'acord, espera.

289
00:16:12,000 --> 00:16:20,000
Anem a veure quant de temps pot pretendre concentrar sense deixar de fer això.

290
00:16:20,000 --> 00:16:23,000
Maleïda sigui. Això és bastant apropiat, en realitat.

291
00:16:23,000 --> 00:16:26,000
Aquí anem.

292
00:16:26,000 --> 00:16:30,000
Punt de fet.

293
00:16:30,000 --> 00:16:34,000
>> Això, compromès encara que també és, també és una de les fonts de gran confusió

294
00:16:34,000 --> 00:16:38,000
en escriure programes que tenen errors, ja que es manifesten

295
00:16:38,000 --> 00:16:40,000
només de tant en tant de vegades.

296
00:16:40,000 --> 00:16:43,000
La realitat és que encara que el codi està completament trencat,

297
00:16:43,000 --> 00:16:46,000
només podria ser completament trencat de tant en tant

298
00:16:46,000 --> 00:16:49,000
perquè de vegades, el que passa és essencialment el sistema operatiu assigna

299
00:16:49,000 --> 00:16:52,000
una mica més de memòria del que realment necessita per qualsevol raó,

300
00:16:52,000 --> 00:16:57,000
i perquè ningú més està utilitzant la memòria immediatament després del seu tros de 16 caràcters,

301
00:16:57,000 --> 00:17:01,000
així que si vas a 17, 18, 19, el que sigui, no és una gran cosa.

302
00:17:01,000 --> 00:17:04,000
Ara, l'equip, encara que no xoc en aquest punt,

303
00:17:04,000 --> 00:17:09,000
eventualment podria utilitzar el byte número 17 o 18 o 19 anys per a una altra cosa,

304
00:17:09,000 --> 00:17:14,000
moment en què les dades que vostè va posar en el seu lloc, encara que sigui excessivament llarg,

305
00:17:14,000 --> 00:17:18,000
serà sobreescrit potencialment per alguna altra funció.

306
00:17:18,000 --> 00:17:21,000
No necessàriament ha de romandre intacta,

307
00:17:21,000 --> 00:17:23,000
però no necessàriament causarà un error seg.

308
00:17:23,000 --> 00:17:26,000
Però en aquest cas, finalment em va proporcionar suficients caràcters

309
00:17:26,000 --> 00:17:29,000
que essencialment superat meu segment de la memòria, i bam,

310
00:17:29,000 --> 00:17:33,000
el sistema operatiu, va dir: "Em sap greu, això no és culpa bo, segmentació".

311
00:17:33,000 --> 00:17:38,000
>> I ara anem a veure si el que queda aquí en el meu directori

312
00:17:38,000 --> 00:17:40,000
adonar que tinc aquest arxiu aquí, el nucli.

313
00:17:40,000 --> 00:17:42,000
Tingueu en compte que això es va tornar a demanar un bolcat de memòria.

314
00:17:42,000 --> 00:17:46,000
Bàsicament es tracta d'un arxiu que conté el contingut de la memòria del programa

315
00:17:46,000 --> 00:17:48,000
en el punt en què es va estavellar,

316
00:17:48,000 --> 00:17:51,000
i només per provar un petit exemple aquí m'ho dius a mi entrar aquí

317
00:17:51,000 --> 00:17:57,000
i executar gdb en scanf3 i especifiqui un tercer argument anomenat nucli,

318
00:17:57,000 --> 00:18:01,000
i notar aquí que si la llista de codis,

319
00:18:01,000 --> 00:18:06,000
serem capaços, com de costum amb gdb per començar a caminar a través d'aquest programa,

320
00:18:06,000 --> 00:18:10,000
i puc córrer i tan bon punt em va colpejar, com a pas amb la comanda a gdb-

321
00:18:10,000 --> 00:18:13,000
tan bon punt vaig arribar a la línia potencialment amb errors després d'escriure en una cadena enorme,

322
00:18:13,000 --> 00:18:16,000
Vaig a ser capaç d'identificar realment aquí.

323
00:18:16,000 --> 00:18:19,000
Més sobre això, però, en la secció en termes de bolcats de memòria

324
00:18:19,000 --> 00:18:22,000
i similar, de manera que en realitat es pot furgar a l'interior del bolcat de memòria

325
00:18:22,000 --> 00:18:27,000
i veure en quina línia del programa que va fallar.

326
00:18:27,000 --> 00:18:32,000
Qualsevol pregunta llavors sobre indicadors i sobre les adreces?

327
00:18:32,000 --> 00:18:36,000
Perquè avui en endavant, anem a començar a donar per fet que aquestes coses existeixen

328
00:18:36,000 --> 00:18:40,000
i sabem exactament el que són.

329
00:18:40,000 --> 00:18:42,000
Sí

330
00:18:42,000 --> 00:18:46,000
>> [Estudiant] Com és que vostè no ha de posar un signe al costat de la part-

331
00:18:46,000 --> 00:18:48,000
Bona pregunta.

332
00:18:48,000 --> 00:18:51,000
Com arribar no havia de posar un signe al costat de la matriu de caràcters com ho vaig fer anteriorment

333
00:18:51,000 --> 00:18:53,000
amb la majoria dels nostres exemples?

334
00:18:53,000 --> 00:18:55,000
La resposta curta és arrays són una mica especial.

335
00:18:55,000 --> 00:18:59,000
Gairebé es pot pensar com un amortidor en realitat ser una adreça,

336
00:18:59,000 --> 00:19:03,000
i dóna la casualitat passar que la notació de claudàtors

337
00:19:03,000 --> 00:19:06,000
és una conveniència perquè puguem entrar en suport 0, suport 1,

338
00:19:06,000 --> 00:19:10,000
suport 2, sense haver d'utilitzar la notació *.

339
00:19:10,000 --> 00:19:13,000
Això és una mica d'una mentida piadosa perquè arrays i punters

340
00:19:13,000 --> 00:19:17,000
són, de fet, una mica diferent, però poden sovint, però no sempre s'usen de manera intercanviable.

341
00:19:17,000 --> 00:19:21,000
En resum, quan una funció espera un punter a un bloc de memòria,

342
00:19:21,000 --> 00:19:24,000
vostè pot passar una direcció que va ser retornat per malloc,

343
00:19:24,000 --> 00:19:29,000
i veurem malloc nou abans d'hora, o pot passar el nom d'una matriu.

344
00:19:29,000 --> 00:19:32,000
No ha de fer arranjaments amb ampersand perquè ja estan

345
00:19:32,000 --> 00:19:34,000
essencialment com adreces.

346
00:19:34,000 --> 00:19:36,000
Aquesta és l'única excepció.

347
00:19:36,000 --> 00:19:39,000
Els claudàtors fan especials.

348
00:19:39,000 --> 00:19:41,000
>> Podria posar un signe al costat del buffer?

349
00:19:41,000 --> 00:19:43,000
No en aquest cas.

350
00:19:43,000 --> 00:19:46,000
Això no funcionaria perquè, de nou, aquest cas de cantonada

351
00:19:46,000 --> 00:19:49,000
on les matrius no són realment molt adreces.

352
00:19:49,000 --> 00:19:54,000
Però potser tornarem a que en poc temps amb altres exemples.

353
00:19:54,000 --> 00:19:56,000
Tractarem de resoldre un problema.

354
00:19:56,000 --> 00:20:00,000
Tenim una estructura de dades que hem estat utilitzant des de fa algun temps es coneix com una matriu.

355
00:20:00,000 --> 00:20:02,000
El cas en qüestió, això és el que acabem de tenir.

356
00:20:02,000 --> 00:20:04,000
Però matrius tenen alguns upsides i desavantatges.

357
00:20:04,000 --> 00:20:06,000
Les matrius són agradables per què?

358
00:20:06,000 --> 00:20:11,000
Què és una cosa que es vol-en la mesura que t'agrada matrius-sobre les matrius?

359
00:20:11,000 --> 00:20:13,000
Què és convenient sobre ells? Què és convincent?

360
00:20:13,000 --> 00:20:18,000
Per què els introduïm en el primer lloc?

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

362
00:20:20,000 --> 00:20:27,000
[Estudiant] Es pot emmagatzemar una gran quantitat de dades, i vostè no ha de fer servir una cosa sencera.

363
00:20:27,000 --> 00:20:29,000
Pot utilitzar una secció.

364
00:20:29,000 --> 00:20:32,000
Bé, amb un arsenal que pot emmagatzemar una gran quantitat de dades,

365
00:20:32,000 --> 00:20:35,000
i no necessàriament ha d'utilitzar tot això, així que vostè pot overallocate,

366
00:20:35,000 --> 00:20:39,000
que podria ser convenient si vostè no sap per endavant quants d'alguna cosa que esperar.

367
00:20:39,000 --> 00:20:41,000
>> GetString és un exemple perfecte.

368
00:20:41,000 --> 00:20:44,000
GetString, escrit per nosaltres, no té idea de com chars que cal esperar,

369
00:20:44,000 --> 00:20:48,000
de manera que el fet que es pot assignar trossos de memòria contigua és bo.

370
00:20:48,000 --> 00:20:51,000
Les matrius també resoldre un problema que vam veure un parell de setmanes ara

371
00:20:51,000 --> 00:20:54,000
on el codi comença a delegar en alguna cosa molt mal dissenyat.

372
00:20:54,000 --> 00:20:57,000
Recordem que he creat una estructura estudiant anomenat David,

373
00:20:57,000 --> 00:21:00,000
i llavors que era en realitat una alternativa, però,

374
00:21:00,000 --> 00:21:04,000
a tenir un nom de variable anomenada i una altra variable anomenada, crec, casa,

375
00:21:04,000 --> 00:21:08,000
i una altra variable anomenada identificació perquè en aquesta història que llavors volia introduir una mica més

376
00:21:08,000 --> 00:21:11,000
Igual que Rob en el programa, de manera que després vaig decidir esperar un minut,

377
00:21:11,000 --> 00:21:13,000
He de canviar el nom d'aquestes variables.

378
00:21:13,000 --> 00:21:16,000
Anem a trucar a la meva Nom1, ID1, house1.

379
00:21:16,000 --> 00:21:20,000
Anem a trucar a Rob nombre2, casa2, ID2.

380
00:21:20,000 --> 00:21:22,000
Però espera un moment, què passa amb Tommy?

381
00:21:22,000 --> 00:21:24,000
Després vam tenir tres variables més.

382
00:21:24,000 --> 00:21:27,000
Hem introduït algun altre, quatre conjunts de variables.

383
00:21:27,000 --> 00:21:30,000
El món va començar a causar problemes molt ràpidament,

384
00:21:30,000 --> 00:21:33,000
per la qual cosa va introduir les estructures, i el que és atractiu en una estructura?

385
00:21:33,000 --> 00:21:39,000
Què fa un struct C permeten fer?

386
00:21:39,000 --> 00:21:42,000
És molt difícil avui en dia.

387
00:21:42,000 --> 00:21:44,000
Què? >> [Resposta dels estudiants inaudible]

388
00:21:44,000 --> 00:21:47,000
Sí, en concret, typedef permet crear un nou tipus de dades,

389
00:21:47,000 --> 00:21:51,000
i estructura, la paraula clau struct, li permet encapsular

390
00:21:51,000 --> 00:21:54,000
peces relacionades conceptualment de dades, juntament

391
00:21:54,000 --> 00:21:56,000
i després d'això en diuen alguna cosa així com un estudiant.

392
00:21:56,000 --> 00:21:58,000
>> Això va ser bo, perquè ara podem modelar

393
00:21:58,000 --> 00:22:03,000
espècie molt més conceptualment coherent la noció d'un estudiant en una variable

394
00:22:03,000 --> 00:22:07,000
en lloc de tenir una forma arbitrària per una cadena, una per a un ID, i així successivament.

395
00:22:07,000 --> 00:22:10,000
Les matrius són agradables perquè ens permet començar a netejar el nostre codi.

396
00:22:10,000 --> 00:22:13,000
Però el que és un inconvenient ara d'una matriu?

397
00:22:13,000 --> 00:22:15,000
El que no pot fer? Si.

398
00:22:15,000 --> 00:22:17,000
[Estudiant] Vostè ha de saber el gran que és.

399
00:22:17,000 --> 00:22:19,000
Vostè ha de saber el gran que és, així que és un tipus de dolor.

400
00:22:19,000 --> 00:22:21,000
Aquells de vostès que tenen experiència prèvia en programació saben que en una gran quantitat d'idiomes,

401
00:22:21,000 --> 00:22:24,000
com Java, vostè pot demanar un tros de memòria, en concret una matriu,

402
00:22:24,000 --> 00:22:28,000
el gran que ets, amb una longitud, posició econòmica, per dir-ho, i això és molt convenient.

403
00:22:28,000 --> 00:22:32,000
En C, ni tan sols es pot trucar strlen en una matriu genèrica

404
00:22:32,000 --> 00:22:35,000
perquè strlen, com la paraula ho indica, és només per a cordes,

405
00:22:35,000 --> 00:22:39,000
i es pot calcular la longitud d'una cadena a causa d'aquesta convenció humana

406
00:22:39,000 --> 00:22:43,000
de tenir un 0 \, sinó una matriu, més genèricament, és només una part de la memòria.

407
00:22:43,000 --> 00:22:46,000
Si es tracta d'una matriu d'enters, no serà una cosa de caràcter especial

408
00:22:46,000 --> 00:22:48,000
al final t'espera.

409
00:22:48,000 --> 00:22:50,000
Cal recordar la longitud d'una matriu.

410
00:22:50,000 --> 00:22:54,000
Un altre aspecte negatiu d'una matriu aixecat el cap en GetString si mateix.

411
00:22:54,000 --> 00:22:59,000
Quin és altra desavantatge d'una matriu?

412
00:22:59,000 --> 00:23:01,000
Senyor, només tu i jo avui.

413
00:23:01,000 --> 00:23:04,000
[Resposta dels estudiants inaudible] >> És què?

414
00:23:04,000 --> 00:23:06,000
Ha declarat a la pila.

415
00:23:06,000 --> 00:23:09,000
D'acord, va declarar a la pila. Per què no t'agrada?

416
00:23:09,000 --> 00:23:13,000
[Estudiant] A causa que es reutilitzen.

417
00:23:13,000 --> 00:23:15,000
Es reutilitzen.

418
00:23:15,000 --> 00:23:18,000
Bé, si s'utilitza una matriu per assignar memòria,

419
00:23:18,000 --> 00:23:21,000
no es pot, per exemple, tornar perquè està a la pila.

420
00:23:21,000 --> 00:23:23,000
Bé, això és un desavantatge.

421
00:23:23,000 --> 00:23:25,000
I una altra amb una matriu?

422
00:23:25,000 --> 00:23:28,000
Quan l'assigni, ets una mica fotut si necessita més espai

423
00:23:28,000 --> 00:23:30,000
que la matriu té.

424
00:23:30,000 --> 00:23:34,000
>> A continuació presentem, recordar, malloc, que ens va donar la capacitat d'assignar dinàmicament la memòria.

425
00:23:34,000 --> 00:23:37,000
Però, i si intentem un món totalment diferent?

426
00:23:37,000 --> 00:23:40,000
Què passa si volem resoldre un parell d'aquests problemes

427
00:23:40,000 --> 00:23:45,000
així que en comptes, la meva ploma s'ha adormit aquí-

428
00:23:45,000 --> 00:23:51,000
I si en lloc volia crear essencialment un món que ja no és així?

429
00:23:51,000 --> 00:23:56,000
Aquesta és una matriu, i, per descomptat, aquest tipus d'es deteriora un cop es prem el final de la matriu,

430
00:23:56,000 --> 00:24:00,000
i ara ja no té espai per a un altre nombre enter o un altre caràcter.

431
00:24:00,000 --> 00:24:03,000
Què passaria si una espècie de forma preventiva dir així, per què no relaxar

432
00:24:03,000 --> 00:24:07,000
Aquest requisit que tots aquests trossos de memòria siguin contigus esquena amb esquena,

433
00:24:07,000 --> 00:24:10,000
i per què no, quan necessito un int o char a,

434
00:24:10,000 --> 00:24:12,000
m'acaba de donar espai per a una d'elles?

435
00:24:12,000 --> 00:24:14,000
I quan necessito un altre, dóna'm un altre espai,

436
00:24:14,000 --> 00:24:16,000
i quan necessito un altre, dóna'm un altre espai.

437
00:24:16,000 --> 00:24:19,000
L'avantatge que ara és que si algú més

438
00:24:19,000 --> 00:24:21,000
pren la memòria per aquí, res de l'altre món.

439
00:24:21,000 --> 00:24:25,000
Em quedo amb aquest tros addicional de memòria aquí i després d'aquest.

440
00:24:25,000 --> 00:24:28,000
>> Ara, l'únic problema aquí és que aquest gairebé se sent com si tingués

441
00:24:28,000 --> 00:24:30,000
un munt de diferents variables.

442
00:24:30,000 --> 00:24:33,000
Això se sent com cinc diferents variables potencialment.

443
00:24:33,000 --> 00:24:36,000
Però i si ens roben una idea de les cadenes

444
00:24:36,000 --> 00:24:41,000
d'alguna manera com puguem vincular aquestes coses conceptualment, i el que si em va fer això?

445
00:24:41,000 --> 00:24:44,000
Aquest és el meu fletxa molt mal dibuixat.

446
00:24:44,000 --> 00:24:46,000
Però suposem que cada un d'aquests trossos de la memòria

447
00:24:46,000 --> 00:24:52,000
va assenyalar a l'altra, i aquest noi, que no té germans, a la seva dreta,

448
00:24:52,000 --> 00:24:54,000
no té cap fletxa tals.

449
00:24:54,000 --> 00:24:56,000
Això és de fet el que s'anomena una llista enllaçada.

450
00:24:56,000 --> 00:25:00,000
Aquesta és una nova estructura de dades que ens permet assignar un bloc de memòria,

451
00:25:00,000 --> 00:25:03,000
després un altre, després un altre, després un altre, cada vegada que vulguem

452
00:25:03,000 --> 00:25:07,000
durant un programa, i recordem que tots estan d'alguna manera relacionats amb

453
00:25:07,000 --> 00:25:11,000
literalment encadenar junts, i ho vam fer aquí gràficament amb una fletxa.

454
00:25:11,000 --> 00:25:15,000
Però en el codi, quin seria el mecanisme a través del qual vostè pot connectar d'alguna manera,

455
00:25:15,000 --> 00:25:20,000
gairebé com Scratch, un fragment a un altre tros?

456
00:25:20,000 --> 00:25:22,000
Podríem utilitzar un punter, oi?

457
00:25:22,000 --> 00:25:25,000
Perquè, en realitat la fletxa que va des de la plaça superior esquerra,

458
00:25:25,000 --> 00:25:31,000
aquest tipus aquí a aquesta, podria contenir dins d'aquest quadrat

459
00:25:31,000 --> 00:25:34,000
no només alguns sencers, no només alguns char, però el que si realment assignats

460
00:25:34,000 --> 00:25:37,000
una mica més d'espai perquè ara,

461
00:25:37,000 --> 00:25:41,000
cada un dels meus trossos de la memòria, tot i que això costarà,

462
00:25:41,000 --> 00:25:45,000
ara es veu una mica més rectangular on un dels trossos de memòria

463
00:25:45,000 --> 00:25:47,000
s'utilitza per a un nombre, com el número 1,

464
00:25:47,000 --> 00:25:50,000
i després, si aquest noi emmagatzema el número 2,

465
00:25:50,000 --> 00:25:52,000
aquest fragment altre de memòria s'utilitza per una fletxa,

466
00:25:52,000 --> 00:25:54,000
o més concretament, un punter.

467
00:25:54,000 --> 00:25:59,000
I suposo que guardar el número 3 per aquí mentre jo faig servir això per apuntar a aquest tipus,

468
00:25:59,000 --> 00:26:02,000
i ara aquest tipus, suposarem que només vol tres trossos com de la memòria.

469
00:26:02,000 --> 00:26:05,000
Vaig a dibuixar una línia a través d'això, el que indica nul.

470
00:26:05,000 --> 00:26:07,000
No hi ha un caràcter addicional.

471
00:26:07,000 --> 00:26:10,000
>> De fet, així és com podem anar sobre l'aplicació

472
00:26:10,000 --> 00:26:12,000
una cosa que es diu una llista enllaçada.

473
00:26:12,000 --> 00:26:18,000
Una llista enllaçada és una estructura de dades nova, i és un pas endavant cap a

474
00:26:18,000 --> 00:26:21,000
molt més elegants estructures de dades que comencen a resoldre problemes

475
00:26:21,000 --> 00:26:23,000
al llarg de les línies dels problemes de tipus Facebook i Google problemes de tipus

476
00:26:23,000 --> 00:26:26,000
on hi ha enormes conjunts de dades, i ja no es talla

477
00:26:26,000 --> 00:26:29,000
per emmagatzemar tot contigua i usar alguna cosa com a recerca lineal

478
00:26:29,000 --> 00:26:31,000
o fins i tot alguna cosa com a recerca binària.

479
00:26:31,000 --> 00:26:33,000
Vols encara millors temps de carrera.

480
00:26:33,000 --> 00:26:37,000
De fet, un dels sants Grials parlarem més endavant aquesta setmana o la propera

481
00:26:37,000 --> 00:26:41,000
és un algorisme el temps d'execució és constant.

482
00:26:41,000 --> 00:26:44,000
En altres paraules, sempre es pren la mateixa quantitat de temps, sense importar

483
00:26:44,000 --> 00:26:47,000
el gran que és l'entrada, i que de fet seria convincent,

484
00:26:47,000 --> 00:26:49,000
fins i tot més que alguna cosa logarítmica.

485
00:26:49,000 --> 00:26:51,000
Què és això a la pantalla aquí?

486
00:26:51,000 --> 00:26:55,000
Cadascun dels rectangles és exactament el que acaba de dibuixar a mà.

487
00:26:55,000 --> 00:26:59,000
Però el que tot el camí de l'esquerra és una variable especial.

488
00:26:59,000 --> 00:27:02,000
Serà un únic punter perquè el Gotcha 01:00

489
00:27:02,000 --> 00:27:04,000
amb una llista enllaçada, com es diuen aquestes coses,

490
00:27:04,000 --> 00:27:09,000
és que vostè ha de penjar en un extrem de la llista enllaçada.

491
00:27:09,000 --> 00:27:13,000
>> Igual que amb una cadena, vostè ha de saber la direcció del primer caràcter.

492
00:27:13,000 --> 00:27:15,000
Mateix tracte per les llistes enllaçades.

493
00:27:15,000 --> 00:27:19,000
Vostè ha de saber la direcció del primer fragment de memòria

494
00:27:19,000 --> 00:27:25,000
perquè a partir d'allà, es pot arribar a qualsevol altre.

495
00:27:25,000 --> 00:27:27,000
El dolent.

496
00:27:27,000 --> 00:27:30,000
Quin preu estem pagant per aquesta versatilitat de tenir una dinàmica

497
00:27:30,000 --> 00:27:34,000
estructura de dades important que si mai necessita més memòria, està bé,

498
00:27:34,000 --> 00:27:37,000
només assignar un tros més i dibuixar un punter de

499
00:27:37,000 --> 00:27:39,000
la vella a la nova cua de la llista?

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

501
00:27:41,000 --> 00:27:43,000
[Estudiant] Es necessita espai d'aproximadament dues vegades més.

502
00:27:43,000 --> 00:27:45,000
Es necessita espai doble, així que això és definitivament un desavantatge, ja que hem vist aquest

503
00:27:45,000 --> 00:27:48,000
equilibri entre abans de temps i espai i flexibilitat

504
00:27:48,000 --> 00:27:51,000
on per ara, no necessitem 32 bits per a cada un d'aquests nombres.

505
00:27:51,000 --> 00:27:57,000
Realment necessitem 64, 32 per al nombre i 32 per al punter.

506
00:27:57,000 --> 00:27:59,000
Però bé, tinc 2 GB de RAM.

507
00:27:59,000 --> 00:28:02,000
Un augment de 32 bits aquí i aquí no sembla tan gran d'un acord.

508
00:28:02,000 --> 00:28:05,000
No obstant això, per als conjunts de dades enormes, que sens dubte es suma a, literalment, el doble.

509
00:28:05,000 --> 00:28:09,000
Quin és altra desavantatge ara, o quina funció li donem cap amunt,

510
00:28:09,000 --> 00:28:12,000
si representem llistes de coses amb una llista enllaçada i no una matriu?

511
00:28:12,000 --> 00:28:14,000
[Estudiant] No es pot recórrer cap enrere.

512
00:28:14,000 --> 00:28:16,000
No es pot recórrer cap enrere, així que ets una mica fotuts si tu te'n vas

513
00:28:16,000 --> 00:28:19,000
d'esquerra a dreta utilitzant un bucle o un bucle while

514
00:28:19,000 --> 00:28:21,000
i llavors te n'adones, "Oh, jo vull anar de nou al principi de la llista."

515
00:28:21,000 --> 00:28:26,000
No és possible perquè aquests punters només van d'esquerra a dreta, com indiquen les fletxes.

516
00:28:26,000 --> 00:28:29,000
>> Ara, vostè pot recordar el principi de la llista amb una altra variable,

517
00:28:29,000 --> 00:28:31,000
però això és una complexitat a tenir en compte.

518
00:28:31,000 --> 00:28:35,000
Una matriu, no importa el lluny que vagi, sempre pot fer menys, menys, menys, menys

519
00:28:35,000 --> 00:28:37,000
i torna d'on vas venir.

520
00:28:37,000 --> 00:28:40,000
Quin és altra desavantatge aquí? Si.

521
00:28:40,000 --> 00:28:43,000
[Pregunta estudiant inaudible]

522
00:28:43,000 --> 00:28:47,000
Podria, per la qual cosa ha fet que acaba de proposar una estructura de dades anomenada llista doblement enllaçada,

523
00:28:47,000 --> 00:28:50,000
i, de fet, hauria afegir un altre punter a cada un d'aquests rectangles

524
00:28:50,000 --> 00:28:53,000
que va l'altra direcció, l'avantatge que

525
00:28:53,000 --> 00:28:55,000
Ara es pot recórrer d'anada i tornada,

526
00:28:55,000 --> 00:28:59,000
el desavantatge que ara s'està utilitzant tres vegades més memòria que fem servir per

527
00:28:59,000 --> 00:29:04,000
i també afegir complexitat en termes del codi que ha d'escriure per fer-ho bé.

528
00:29:04,000 --> 00:29:08,000
Però tots aquests són potser les compensacions raonables, si la inversió és més important.

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

530
00:29:10,000 --> 00:29:12,000
[Estudiant] Tampoc es pot tenir una llista enllaçada 2D.

531
00:29:12,000 --> 00:29:16,000
Bé, realment no es pot tenir una llista 2D vinculat.

532
00:29:16,000 --> 00:29:18,000
Podries. No és tan fàcil com una matriu.

533
00:29:18,000 --> 00:29:21,000
Igual que una matriu, fer claudàtor obert, suport tancat, suport obert, tancat suport,

534
00:29:21,000 --> 00:29:23,000
i s'obté una estructura de 2 dimensions.

535
00:29:23,000 --> 00:29:26,000
Es podria implementar una llista de 2 dimensions vinculades

536
00:29:26,000 --> 00:29:29,000
Si ho fa, com vostè proposa-un tercer indicador per a cadascuna d'aquestes coses,

537
00:29:29,000 --> 00:29:34,000
i si penses en una altra llista que li arriba estil 3D

538
00:29:34,000 --> 00:29:40,000
de la pantalla per a tots nosaltres, que és una altra cadena d'algun tipus.

539
00:29:40,000 --> 00:29:45,000
Podríem fer-ho, però no és tan simple com escriure obertura de claudàtors, claudàtors. Si.

540
00:29:45,000 --> 00:29:48,000
[Pregunta estudiant inaudible]

541
00:29:48,000 --> 00:29:50,000
Bé, així que això és un truc real.

542
00:29:50,000 --> 00:29:54,000
>> Aquests algorismes que hem sospirat altra vegada, com oh, recerca binària,

543
00:29:54,000 --> 00:29:57,000
vostè pot buscar en una matriu de nombres en el tauler

544
00:29:57,000 --> 00:30:01,000
o una llibreta de telèfons molt més ràpidament si utilitza divideix i venceràs

545
00:30:01,000 --> 00:30:05,000
i un algorisme de recerca binària, però la recerca binari requereix dos supòsits.

546
00:30:05,000 --> 00:30:09,000
Un d'ells, que les dades van ser ordenats.

547
00:30:09,000 --> 00:30:11,000
Ara, podeu mantenir aquesta resolt,

548
00:30:11,000 --> 00:30:14,000
així que potser això no és una preocupació, però també suposa la recerca binària

549
00:30:14,000 --> 00:30:18,000
que tenia accés aleatori a la llista de números,

550
00:30:18,000 --> 00:30:21,000
i una gran varietat li permet tenir accés a l'atzar, i per l'accés aleatori,

551
00:30:21,000 --> 00:30:24,000
Vull dir que si et donen una sèrie, quant de temps li pren

552
00:30:24,000 --> 00:30:26,000
per arribar al suport de 0?

553
00:30:26,000 --> 00:30:29,000
Una operació, vostè només ha d'utilitzar [0] i ja hi és.

554
00:30:29,000 --> 00:30:33,000
Quants passos es necessiten per arribar a la ubicació 10?

555
00:30:33,000 --> 00:30:36,000
Un pas, vostè només ha d'anar a [10] i que ets.

556
00:30:36,000 --> 00:30:40,000
Per contra, com s'aconsegueix que el sencer 10 en una llista enllaçada?

557
00:30:40,000 --> 00:30:42,000
Cal començar pel principi, ja que només està recordant

558
00:30:42,000 --> 00:30:45,000
el començament d'una llista enllaçada, igual que una cadena es recorda

559
00:30:45,000 --> 00:30:48,000
per la direcció del seu primer caràcter, i en veure que int 10

560
00:30:48,000 --> 00:30:53,000
o que el caràcter 10 º en una cadena, vostè ha de buscar tota la maleïda cosa.

561
00:30:53,000 --> 00:30:55,000
>> Un cop més, no anem a resoldre tots els nostres problemes.

562
00:30:55,000 --> 00:31:00,000
Estem introduint altres nous, però realment depèn del que estiguis tractant de dissenyar per.

563
00:31:00,000 --> 00:31:04,000
Quant a l'aplicació d'aquesta, es pot demanar prestada una idea que l'estructura dels estudiants.

564
00:31:04,000 --> 00:31:07,000
La sintaxi és molt similar, excepte que ara, la idea és una mica més abstracte

565
00:31:07,000 --> 00:31:09,000
que la casa i el nom i DNI.

566
00:31:09,000 --> 00:31:13,000
Però jo proposo que podria tenir una estructura de dades en C

567
00:31:13,000 --> 00:31:17,000
que es diu node, com l'última paraula a la diapositiva indica,

568
00:31:17,000 --> 00:31:21,000
dins d'un node, i un node és un contenidor genèric en ciències de la computació.

569
00:31:21,000 --> 00:31:25,000
En general es dibuixa com un cercle o un quadrat o un rectangle com ho hem fet.

570
00:31:25,000 --> 00:31:27,000
I en aquesta estructura de dades, tenim un enter, n,

571
00:31:27,000 --> 00:31:29,000
pel que és el número que voleu emmagatzemar.

572
00:31:29,000 --> 00:31:36,000
Però què és aquesta segona línia, struct node * següent?

573
00:31:36,000 --> 00:31:40,000
Per què és correcte o quin paper té aquesta cosa,

574
00:31:40,000 --> 00:31:42,000
encara que és una mica críptic, a primera vista?

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

576
00:31:44,000 --> 00:31:46,000
[Resposta dels estudiants inaudible]

577
00:31:46,000 --> 00:31:50,000
Exactament, de manera que el tipus de botí * que és un punter d'algun tipus.

578
00:31:50,000 --> 00:31:53,000
El nom d'aquest punter és arbitràriament proper,

579
00:31:53,000 --> 00:32:00,000
però ens podria haver anomenat qualsevol cosa que vulguem, però què té això punter a punt?

580
00:32:00,000 --> 00:32:03,000
[Estudiant] Un altre node. >> Exactament, apunta a un altre node tal.

581
00:32:03,000 --> 00:32:05,000
>> Ara, això és una mena de curiositat de C.

582
00:32:05,000 --> 00:32:09,000
Recordem que C és llegit per un compilador dalt a baix, d'esquerra a dreta,

583
00:32:09,000 --> 00:32:13,000
el que significa que si, això és una mica diferent del que hem fet amb l'estudiant.

584
00:32:13,000 --> 00:32:16,000
Quan definim un estudiant, que en realitat no va posar una paraula allà.

585
00:32:16,000 --> 00:32:18,000
Simplement va dir typedef.

586
00:32:18,000 --> 00:32:20,000
Després vam tenir id int nom, cadena, cadena de casa,

587
00:32:20,000 --> 00:32:23,000
i després estudiant a la part inferior de l'estructura.

588
00:32:23,000 --> 00:32:26,000
Aquesta declaració és una mica diferent, ja que,

589
00:32:26,000 --> 00:32:28,000
de nou, el compilador de C és una mica ximple.

590
00:32:28,000 --> 00:32:30,000
És només va a llegir de dalt a baix,

591
00:32:30,000 --> 00:32:33,000
així que si arriba a la 2 ª línia aquí

592
00:32:33,000 --> 00:32:37,000
on es declara pròxim i ho veu, oh, aquí hi ha una variable anomenada següent.

593
00:32:37,000 --> 00:32:39,000
És un punter a un node d'estructura.

594
00:32:39,000 --> 00:32:42,000
El compilador es donarà compte del que és un node d'estructura?

595
00:32:42,000 --> 00:32:44,000
Mai he sentit parlar d'això abans,

596
00:32:44,000 --> 00:32:47,000
perquè el node de paraula d'una altra manera no podria aparèixer

597
00:32:47,000 --> 00:32:49,000
fins a la part inferior, de manera que és aquesta redundància.

598
00:32:49,000 --> 00:32:53,000
Has de dir struct node aquí, que després es pot escurçar més tard

599
00:32:53,000 --> 00:32:56,000
gràcies a typedef aquí baix, però és perquè

600
00:32:56,000 --> 00:33:02,000
estem fent referència a l'estructura en si mateixa a l'interior de l'estructura.

601
00:33:02,000 --> 00:33:05,000
Aquest és el Gotcha ningú allà.

602
00:33:05,000 --> 00:33:07,000
>> Alguns problemes interessants sorgiran.

603
00:33:07,000 --> 00:33:09,000
Tenim una llista de nombres. Com inserir-hi?

604
00:33:09,000 --> 00:33:11,000
Com podem buscar? Com esborrar d'ella?

605
00:33:11,000 --> 00:33:13,000
Sobretot ara que hem de gestionar tots aquests consells.

606
00:33:13,000 --> 00:33:15,000
Vostè va pensar que eren punters espècie d'al · lucinant

607
00:33:15,000 --> 00:33:17,000
quan tenia un d'ells tractant de llegir un int a ella.

608
00:33:17,000 --> 00:33:20,000
Ara hem de manipular la pena una llista sencera.

609
00:33:20,000 --> 00:33:22,000
Per què no ens prenem el nostre fill de 5 minuts de descans aquí, i després vaig a portar

610
00:33:22,000 --> 00:33:34,000
algunes persones a l'escenari per fer exactament això.

611
00:33:34,000 --> 00:33:36,000
>> C és molt més divertit quan és representada.

612
00:33:36,000 --> 00:33:39,000
Que literalment vol ser el primer?

613
00:33:39,000 --> 00:33:41,000
Molt bé, anem a dalt. Vostè està en primer lloc.

614
00:33:41,000 --> 00:33:44,000
Qui vol ser 9? Bé, 9.

615
00:33:44,000 --> 00:33:46,000
Què hi ha de 9? 17?

616
00:33:46,000 --> 00:33:51,000
Una camarilla poc aquí. 22 i 26 a la fila davantera.

617
00:33:51,000 --> 00:33:53,000
I llavors què hi ha algú per aquí que se la mira.

618
00:33:53,000 --> 00:33:57,000
Vostè és 34. Bé, de 34 anys, anem a dalt.

619
00:33:57,000 --> 00:33:59,000
En primer lloc és allà. Bé, els quatre de vostès.

620
00:33:59,000 --> 00:34:01,000
I qui li diem a 9?

621
00:34:01,000 --> 00:34:04,000
Qui és el nostre 9?

622
00:34:04,000 --> 00:34:07,000
Qui realment vol ser 9? Molt bé, anem, a les 9.

623
00:34:07,000 --> 00:34:10,000
Aquí anem.

624
00:34:10,000 --> 00:34:13,000
34, ens trobarem allà.

625
00:34:13,000 --> 00:34:17,000
La primera part és fer-vos veure així.

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

627
00:34:21,000 --> 00:34:25,000
Si pots suportar de banda, perquè ens malloc en un moment.

628
00:34:25,000 --> 00:34:29,000
>> Bé, bé.

629
00:34:29,000 --> 00:34:32,000
Està bé, excel · lent, així que anem a fer-li un parell de preguntes.

630
00:34:32,000 --> 00:34:34,000
I en realitat, quin és el teu nom? >> Anita.

631
00:34:34,000 --> 00:34:37,000
Anita, està bé, vine aquí.

632
00:34:37,000 --> 00:34:41,000
Anita ens ajudarà a resoldre un tipus de pregunta bastant simple en principi,

633
00:34:41,000 --> 00:34:44,000
que és com trobar si un valor és a la llista?

634
00:34:44,000 --> 00:34:48,000
Ara, notin que la primera, representada aquí per Lucas,

635
00:34:48,000 --> 00:34:52,000
és una mica diferent, de manera que el seu paper és deliberadament de banda

636
00:34:52,000 --> 00:34:55,000
perquè no és tan alt i no ocupa tants bits,

637
00:34:55,000 --> 00:34:58,000
tot i que tècnicament té la mateixa mida de paper que acaba de girar.

638
00:34:58,000 --> 00:35:01,000
Però és una mica diferent, ja que té només 32 bits per a un punter,

639
00:35:01,000 --> 00:35:05,000
i tots aquests nois són de 64 bits, la meitat dels quals és el nombre, la meitat dels quals és un punter.

640
00:35:05,000 --> 00:35:08,000
No obstant això, el punter no es representa, per tant si vostès podrien torpemente

641
00:35:08,000 --> 00:35:12,000
usi la mà esquerra per apuntar a la persona al teu costat.

642
00:35:12,000 --> 00:35:14,000
I tu ets el número 34. ¿Et dius?

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

644
00:35:16,000 --> 00:35:19,000
Ari, pel que en realitat, mantingui el paper a la mà dreta i la mà esquerra va cap avall.

645
00:35:19,000 --> 00:35:21,000
Vostè declara nul l'esquerra.

646
00:35:21,000 --> 00:35:24,000
>> Ara la nostra imatge humana és molt consistent.

647
00:35:24,000 --> 00:35:26,000
Això és realment com funcionen els punters.

648
00:35:26,000 --> 00:35:29,000
I si es pot arrugar una mica aquesta manera així que no estic en el teu camí.

649
00:35:29,000 --> 00:35:34,000
Anita aquí, em trobareu el número 22,

650
00:35:34,000 --> 00:35:40,000
però suposen una restricció dels éssers humans no suporta fulls de paper,

651
00:35:40,000 --> 00:35:43,000
però aquesta és una llista, i només té Lluc per començar

652
00:35:43,000 --> 00:35:46,000
perquè és, literalment, el primer indicador.

653
00:35:46,000 --> 00:35:51,000
Suposem que vostè mateix és un punter, i pel que també tenen la capacitat d'apuntar a alguna cosa.

654
00:35:51,000 --> 00:35:56,000
Per què no començar per assenyalar exactament el que Lluc està assenyalant?

655
00:35:56,000 --> 00:35:58,000
Bé, i dóna'm promulgar això per aquí.

656
00:35:58,000 --> 00:36:04,000
Només pel bé de la discussió, deixa que tiri cap amunt una pàgina en blanc aquí.

657
00:36:04,000 --> 00:36:06,000
Com s'escriu el teu nom? >> Anita.

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

659
00:36:08,000 --> 00:36:18,000
Diguem node * anita = lucas.

660
00:36:18,000 --> 00:36:22,000
Bé, no us crida lucas. Hauríem trucar a vostè primer.

661
00:36:22,000 --> 00:36:25,000
Per què és de fet compatible amb la realitat aquí?

662
00:36:25,000 --> 00:36:27,000
Un, en primer lloc ja existeix.

663
00:36:27,000 --> 00:36:30,000
En primer lloc s'ha assignat presumiblement en algun lloc per aquí.

664
00:36:30,000 --> 00:36:35,000
Node * primer, i s'ha assignat una llista d'alguna manera.

665
00:36:35,000 --> 00:36:37,000
No sé com va succeir. Això va passar abans que comencés la classe.

666
00:36:37,000 --> 00:36:40,000
Aquesta llista vinculada dels éssers humans ha estat creada.

667
00:36:40,000 --> 00:36:44,000
I ara, en aquest moment de la història, tot això succeeix en Facebook, aparentment després-

668
00:36:44,000 --> 00:36:49,000
en aquest punt de la història, Anita s'ha inicialitzat a ser igual al primer,

669
00:36:49,000 --> 00:36:51,000
el que no significa que els punts d'Anita a Lluc.

670
00:36:51,000 --> 00:36:53,000
Més aviat, apunta al que apunta

671
00:36:53,000 --> 00:36:57,000
perquè la mateixa direcció que està dins dels 32 bits - Lluc 1, 2, 3 -

672
00:36:57,000 --> 00:37:01,000
és ara també a l'interior d'Anita 32 bits - 1, 2, 3.

673
00:37:01,000 --> 00:37:05,000
>> Trobi ara 22. Com faria vostè per fer això?

674
00:37:05,000 --> 00:37:07,000
Què és aquest punt? >> Per al que sigui.

675
00:37:07,000 --> 00:37:11,000
Assenyaleu el que sigui, així que endavant i representar el millor que pots aquí.

676
00:37:11,000 --> 00:37:15,000
Bé, bé, i ara vostè està assenyalant, quin és el teu nom amb 22?

677
00:37:15,000 --> 00:37:18,000
Ramon. >> Ramon, de manera que Ramon és la celebració de 22.

678
00:37:18,000 --> 00:37:20,000
Ara ha fet un xec.

679
00:37:20,000 --> 00:37:24,000
Té Ramon == 22, i si és així, per exemple, es pot tornar realitat.

680
00:37:24,000 --> 00:37:26,000
Permetin-me, mentre aquests nois són aquí alguna cosa maldestre-

681
00:37:26,000 --> 00:37:32,000
m'ho dius a mi fer alguna cosa ràpidament com bool trobar.

682
00:37:32,000 --> 00:37:37,000
Vaig a seguir endavant i dir (llista de nodes *, int n).

683
00:37:37,000 --> 00:37:39,000
Estaré de tornada amb vostès. Només he d'escriure una mica de codi.

684
00:37:39,000 --> 00:37:45,000
I ara vaig a seguir endavant i fer això, el node * anita list =.

685
00:37:45,000 --> 00:37:51,000
I seguiré endavant i dir while (anita! = NULL).

686
00:37:51,000 --> 00:37:57,000
>> La metàfora aquí és aconseguir una mica estirat, però al mateix temps (anita! = NULL), què és el que vull fer?

687
00:37:57,000 --> 00:38:03,000
Necessito alguna manera de fer referència a

688
00:38:03,000 --> 00:38:05,000
el sencer que Anita està assenyalant.

689
00:38:05,000 --> 00:38:08,000
En el passat, quan vam estructures, que és un node,

690
00:38:08,000 --> 00:38:11,000
hem utilitzat la notació de punts, i ens diria alguna cosa així com

691
00:38:11,000 --> 00:38:15,000
anita.n, però el problema aquí és que Anita no és una estructura en si.

692
00:38:15,000 --> 00:38:17,000
Què és?

693
00:38:17,000 --> 00:38:21,000
Ella és un punter, així que realment, si volem utilitzar aquesta notació punt-

694
00:38:21,000 --> 00:38:23,000
i això va a semblar una mica críptic deliberadament-

695
00:38:23,000 --> 00:38:28,000
hem de fer alguna cosa com anar a mà esquerra el que Anita està apuntant a

696
00:38:28,000 --> 00:38:31,000
i després el camp anomenat núm.

697
00:38:31,000 --> 00:38:35,000
Anita és un punter, però el que és * anita?

698
00:38:35,000 --> 00:38:38,000
Què trobes quan vas al que Anita està assenyalant?

699
00:38:38,000 --> 00:38:42,000
Una estructura, un node, i una retirada node,, té un camp anomenat n

700
00:38:42,000 --> 00:38:47,000
perquè ha, recorden, aquests dos camps, pròxims i N,

701
00:38:47,000 --> 00:38:50,000
que vam veure fa un moment aquí.

702
00:38:50,000 --> 00:38:53,000
>> Per imitar aquest fet en el codi,

703
00:38:53,000 --> 00:39:02,000
podríem fer això i dir if ((* anita). == n n), la núm que jo estic buscant.

704
00:39:02,000 --> 00:39:04,000
Observeu que la funció es va aprovar en el nombre que m'importa.

705
00:39:04,000 --> 00:39:10,000
Llavors puc seguir endavant i fer alguna cosa com a veritable retorn.

706
00:39:10,000 --> 00:39:12,000
Si no, si aquest no és el cas, què és el que vull fer?

707
00:39:12,000 --> 00:39:19,000
Com tradueixo per codificar el que Anita va fer intuïtivament a peu a través de la llista?

708
00:39:19,000 --> 00:39:26,000
Què he de fer aquí per simular Anita donar aquest pas a l'esquerra, aquest pas cap a l'esquerra?

709
00:39:26,000 --> 00:39:28,000
[Resposta dels estudiants inaudible] >> Què és això?

710
00:39:28,000 --> 00:39:30,000
[Resposta dels estudiants inaudible]

711
00:39:30,000 --> 00:39:34,000
Bé, no és una mala idea, però en el passat, quan hàgim fet això, hem fet anita + +

712
00:39:34,000 --> 00:39:37,000
perquè això augmentaria el nombre 1 a Anita,

713
00:39:37,000 --> 00:39:40,000
que normalment apuntar a la següent persona, igual que Ramon,

714
00:39:40,000 --> 00:39:44,000
o la persona al seu costat, o la persona al seu costat de la línia.

715
00:39:44,000 --> 00:39:49,000
Però això no és molt bo, perquè el que aquí està aquesta cosa sembla a la memòria?

716
00:39:49,000 --> 00:39:54,000
No és això. Hem de desactivar això.

717
00:39:54,000 --> 00:40:00,000
Sembla que aquest en la memòria, i encara que he dibuixat 1 i 2 i 3 prop un de l'altre,

718
00:40:00,000 --> 00:40:03,000
si realment fer veure que aquesta-can nois, sense deixar d'apuntar a la mateixa gent,

719
00:40:03,000 --> 00:40:07,000
Potser alguns de vosaltres fer un pas enrere a l'atzar, alguns de vosaltres un pas endavant a l'atzar?

720
00:40:07,000 --> 00:40:10,000
>> Aquest desordre és encara una llista enllaçada,

721
00:40:10,000 --> 00:40:13,000
però aquests nois poden estar en qualsevol lloc en la memòria,

722
00:40:13,000 --> 00:40:15,000
així anita + + no funcionarà això?

723
00:40:15,000 --> 00:40:19,000
El que està en posició anita + +?

724
00:40:19,000 --> 00:40:21,000
Qui sap.

725
00:40:21,000 --> 00:40:24,000
És un altre valor que el que passa és que s'interposa

726
00:40:24,000 --> 00:40:28,000
entre tots aquests nodes d'atzar perquè no estem utilitzant una matriu.

727
00:40:28,000 --> 00:40:30,000
Hem assignat cadascun d'aquests nodes de forma individual.

728
00:40:30,000 --> 00:40:32,000
Bé, si vostès mateixos poden netejar de nou.

729
00:40:32,000 --> 00:40:37,000
Permetin-me proposar que en lloc de anita + +, que en comptes fer anita es-

730
00:40:37,000 --> 00:40:42,000
bé, per què no ens anem al que Anita està assenyalant i després fer. després?

731
00:40:42,000 --> 00:40:45,000
En altres paraules, anem a Ramon, que està sostenint el número 22,

732
00:40:45,000 --> 00:40:51,000
i llavors. següent és com si Anita es copia el punter esquerre.

733
00:40:51,000 --> 00:40:54,000
Però ella no va voler anar més enllà de Ramon perquè trobem 22.

734
00:40:54,000 --> 00:40:56,000
Però aquesta seria la idea. Ara, això és un embolic espantós.

735
00:40:56,000 --> 00:40:59,000
Honestament, potser hem oblidat aquesta sintaxi, i per sort,

736
00:40:59,000 --> 00:41:04,000
en realitat és una mica deliberada-oh, no va veure el que vaig escriure.

737
00:41:04,000 --> 00:41:08,000
Això seria més convincent si pogués. Voila!

738
00:41:08,000 --> 00:41:10,000
>> Darrere de les escenes, estava resolent el problema d'aquesta manera.

739
00:41:10,000 --> 00:41:14,000
Anita, per fer el pas a l'esquerra,

740
00:41:14,000 --> 00:41:18,000
en primer lloc, que et vagis a l'adreça que Anita està apuntant a

741
00:41:18,000 --> 00:41:23,000
i en la qual es troba no només n, que acaba de comprovar per efectes de comparació,

742
00:41:23,000 --> 00:41:25,000
però també es troba a prop - en aquest cas,

743
00:41:25,000 --> 00:41:28,000
Ramon mà esquerra apuntant al següent node a la llista.

744
00:41:28,000 --> 00:41:32,000
Però aquest és l'embolic espantós al qual m'he referit abans,

745
00:41:32,000 --> 00:41:34,000
però resulta que C ens permet simplificar això.

746
00:41:34,000 --> 00:41:40,000
En lloc d'escriure (* anita), es pot en comptes de escriure anita-> n,

747
00:41:40,000 --> 00:41:45,000
i és exactament el mateix funcionalment, però és molt més intuïtiu,

748
00:41:45,000 --> 00:41:48,000
i és molt més coherent amb la imatge que hem vingut assenyalant

749
00:41:48,000 --> 00:41:50,000
tot aquest temps utilitzant fletxes.

750
00:41:50,000 --> 00:41:57,000
>> Finalment, què és el que hem de fer al final d'aquest programa?

751
00:41:57,000 --> 00:42:00,000
Hi ha una línia de codi restant.

752
00:42:00,000 --> 00:42:02,000
Tornar què?

753
00:42:02,000 --> 00:42:05,000
Fals, perquè si arribem a través de tot el cicle while

754
00:42:05,000 --> 00:42:10,000
i Anita és, de fet, null, això vol dir que ella va ser tot el camí fins al final de la llista

755
00:42:10,000 --> 00:42:12,000
on ella assenyalava, quin és el teu nom?

756
00:42:12,000 --> 00:42:15,000
Mà esquerra Ari. >> Ari, que és nul.

757
00:42:15,000 --> 00:42:18,000
Anita és ara nul, i m'adono que vostè està aquí de peu amb malaptesa als llimbs

758
00:42:18,000 --> 00:42:21,000
perquè m'estic anant per un monòleg aquí,

759
00:42:21,000 --> 00:42:23,000
però et involucren de nou en un moment.

760
00:42:23,000 --> 00:42:27,000
Anita és nul en aquest punt de la història, de manera que el bucle while acaba,

761
00:42:27,000 --> 00:42:30,000
i hem de tornar falsa, perquè si ella té tot el camí a punter nul Ari

762
00:42:30,000 --> 00:42:34,000
llavors no hi havia un nombre que va buscar a la llista.

763
00:42:34,000 --> 00:42:39,000
Podem netejar això també, però aquesta és una aplicació molt bona llavors

764
00:42:39,000 --> 00:42:43,000
d'una funció de recorregut, una funció per trobar una llista enllaçada.

765
00:42:43,000 --> 00:42:48,000
Encara recerca lineal, però no és tan simple com un punter + +

766
00:42:48,000 --> 00:42:52,000
+ + O una variable i perquè ara no podem endevinar

767
00:42:52,000 --> 00:42:54,000
on cada un d'aquests nodes són a la memòria.

768
00:42:54,000 --> 00:42:57,000
Hem de seguir literalment el rastre de molles de pa o, més específicament,

769
00:42:57,000 --> 00:43:00,000
punters, per anar d'un node a un altre.

770
00:43:00,000 --> 00:43:02,000
>> Ara anem a provar amb l'altra. Anita, vols tornar aquí?

771
00:43:02,000 --> 00:43:06,000
Per què no seguir endavant i assignar a una altra persona de l'audiència?

772
00:43:06,000 --> 00:43:08,000
Malloc-com et dius? >> Rebecca.

773
00:43:08,000 --> 00:43:10,000
Rebecca. Rebecca ha estat malloced de l'audiència,

774
00:43:10,000 --> 00:43:13,000
i ella està emmagatzemant el número 55.

775
00:43:13,000 --> 00:43:17,000
I l'objectiu que ens ocupa ara és que Anita per inserir

776
00:43:17,000 --> 00:43:22,000
Rebecca a la llista enllaçada aquí en el seu lloc apropiat.

777
00:43:22,000 --> 00:43:24,000
Vine aquí un moment.

778
00:43:24,000 --> 00:43:28,000
Jo he fet alguna cosa com això.

779
00:43:28,000 --> 00:43:32,000
He fet * node. I quin és el teu nom?

780
00:43:32,000 --> 00:43:34,000
Rebecca. >> Rebecca, està bé.

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

782
00:43:41,000 --> 00:43:44,000
Igual que hem destinat coses com els estudiants i altres coses en el passat,

783
00:43:44,000 --> 00:43:46,000
necessitem la mida del node, de manera que Rebecca ara

784
00:43:46,000 --> 00:43:49,000
està assenyalant en què?

785
00:43:49,000 --> 00:43:52,000
Rebecca té dos camps dins d'ella, un dels quals és 55.

786
00:43:52,000 --> 00:43:55,000
Anem a fer el que, Rebecca-> = 55.

787
00:43:55,000 --> 00:44:00,000
Però llavors Rebecca-> servidor ha d'-com ara, amb la mà és una espècie de qui sap?

788
00:44:00,000 --> 00:44:03,000
Està apuntant a un cert valor escombraries, així que per què no fer una bona mesura

789
00:44:03,000 --> 00:44:07,000
que almenys fer això perquè la mà esquerra està ara al seu costat.

790
00:44:07,000 --> 00:44:09,000
Ara Anita, a partir d'aquí.

791
00:44:09,000 --> 00:44:11,000
Cal Rebecca se li hagin assignat.

792
00:44:11,000 --> 00:44:20,000
Seguir endavant i trobar on hem de posar Rebecca.

793
00:44:20,000 --> 00:44:25,000
Bé, molt bé.

794
00:44:25,000 --> 00:44:28,000
Bé, bé, i ara necessitem que ens proporcioni una mica de direcció,

795
00:44:28,000 --> 00:44:30,000
pel que ha arribat a Ari.

796
00:44:30,000 --> 00:44:33,000
La seva mà esquerra és nul, però Rebecca pertany clarament a la dreta,

797
00:44:33,000 --> 00:44:36,000
així que com hem de modificar aquesta llista enllaçada

798
00:44:36,000 --> 00:44:38,000
amb la finalitat d'inserir Rebecca en el lloc apropiat?

799
00:44:38,000 --> 00:44:42,000
Si vostè pot literalment moure les mans de la gent d'esquerra al voltant de com sigui necessari,

800
00:44:42,000 --> 00:44:48,000
arreglarem el problema d'aquesta manera.

801
00:44:48,000 --> 00:44:52,000
Bé, bé, i mentrestant, la mà esquerra de Rebecca és ara al seu costat.

802
00:44:52,000 --> 00:44:54,000
>> Això va ser massa fàcil.

803
00:44:54,000 --> 00:44:57,000
Tractarem d'assignar-estem gairebé llestos, 20.

804
00:44:57,000 --> 00:44:59,000
Molt bé, anem a dalt.

805
00:44:59,000 --> 00:45:04,000
20 ha estat assignat, així que vaig a seguir endavant i dir una altra vegada aquí

806
00:45:04,000 --> 00:45:07,000
que acabem de fer SAAD node *.

807
00:45:07,000 --> 00:45:11,000
Tenim malloc (sizeof (node)).

808
00:45:11,000 --> 00:45:16,000
A continuació, fer la mateixa sintaxi exacta com ho vam fer abans per a 20,

809
00:45:16,000 --> 00:45:20,000
i jo faré el següent = NULL, i ara li toca a Anita

810
00:45:20,000 --> 00:45:23,000
que s'insereix en la llista enllaçada, si poguessis jugar aquest mateix paper exacte.

811
00:45:23,000 --> 00:45:30,000
Executar.

812
00:45:30,000 --> 00:45:32,000
Bé, bé.

813
00:45:32,000 --> 00:45:38,000
Ara pensa detingudament abans de començar a moure les mans esquerra al voltant.

814
00:45:38,000 --> 00:45:46,000
Vostè té, amb molt, el paper més difícil avui en dia.

815
00:45:46,000 --> 00:45:59,000
La mà es va moure per primera vegada?

816
00:45:59,000 --> 00:46:02,000
Bé, espera, estic escoltant alguns no.

817
00:46:02,000 --> 00:46:07,000
Si algunes persones cortesament li agradaria ajudar a resoldre una situació difícil aquí.

818
00:46:07,000 --> 00:46:11,000
La mà esquerra ha de ser actualitzat primer, potser? Si.

819
00:46:11,000 --> 00:46:13,000
[Estudiant] Saad.

820
00:46:13,000 --> 00:46:15,000
Bé, Saad, per què, doncs?

821
00:46:15,000 --> 00:46:17,000
[Resposta dels estudiants inaudible]

822
00:46:17,000 --> 00:46:19,000
Bé, perquè si ens movem, quin és el teu nom? >> Marshall.

823
00:46:19,000 --> 00:46:22,000
Marshall, si movem la mà primer i deu en null,

824
00:46:22,000 --> 00:46:25,000
ara hem literalment orfes a quatre persones en aquesta llista

825
00:46:25,000 --> 00:46:29,000
perquè era l'únic que assenyala al Ramón i tothom a l'esquerra,

826
00:46:29,000 --> 00:46:31,000
de manera que l'actualització primer indicador era dolent.

827
00:46:31,000 --> 00:46:33,000
Anem a desfer això.

828
00:46:33,000 --> 00:46:37,000
Bé, i ara seguir endavant i moure la mà esquerra apuntant a l'adequat Ramon.

829
00:46:37,000 --> 00:46:39,000
Això se sent una mica redundant.

830
00:46:39,000 --> 00:46:41,000
Ara hi ha dues persones apuntant a Ramon, però això està bé

831
00:46:41,000 --> 00:46:43,000
perquè ara quina altra manera podem actualitzar la llista?

832
00:46:43,000 --> 00:46:48,000
El que per altra banda s'ha de moure?

833
00:46:48,000 --> 00:46:53,000
Molt bé, ara hem perdut la memòria?

834
00:46:53,000 --> 00:46:57,000
No, tot va bé, anem a veure si no podem trencar una vegada més.

835
00:46:57,000 --> 00:47:00,000
>> Mallocing per última vegada, el número 5.

836
00:47:00,000 --> 00:47:04,000
Tot el camí de tornada, anem cap avall.

837
00:47:04,000 --> 00:47:08,000
És molt emocionant.

838
00:47:08,000 --> 00:47:15,000
[Aplaudiment]

839
00:47:15,000 --> 00:47:17,000
¿Et dius? >> Ron.

840
00:47:17,000 --> 00:47:19,000
Ron, està bé, està malloced com el número 5.

841
00:47:19,000 --> 00:47:23,000
Acabem d'executar codi que és gairebé idèntica a aquests

842
00:47:23,000 --> 00:47:26,000
amb un nom diferent.

843
00:47:26,000 --> 00:47:28,000
Excel · lent.

844
00:47:28,000 --> 00:47:38,000
Ara, Anita, bona sort inserir el número 5 a la llista ara.

845
00:47:38,000 --> 00:47:43,000
Bé, i?

846
00:47:43,000 --> 00:47:47,000
Molt bé, així que això és realment el tercer dels tres casos totals.

847
00:47:47,000 --> 00:47:49,000
Primer vam tenir algú a la final, Rebecca.

848
00:47:49,000 --> 00:47:51,000
Després vam tenir algú en el medi.

849
00:47:51,000 --> 00:47:53,000
Ara tenim a algú al començament, i en aquest exemple,

850
00:47:53,000 --> 00:47:56,000
que ara havia de actualitzar Lluc per primera vegada

851
00:47:56,000 --> 00:48:00,000
perquè el primer element a la llista ara ha de apuntar a un nou node,

852
00:48:00,000 --> 00:48:03,000
que, al seu torn, s'assenyala en el nombre de node 9.

853
00:48:03,000 --> 00:48:06,000
>> Aquesta va ser una demostració enormement difícil, estic segur,

854
00:48:06,000 --> 00:48:08,000
de manera que un gran aplaudiment per aquests nois si poguessis.

855
00:48:08,000 --> 00:48:11,000
Molt ben fet.

856
00:48:11,000 --> 00:48:17,000
Això és tot. Vostè pot guardar els seus trossos de paper com una mica de memòria.

857
00:48:17,000 --> 00:48:22,000
Resulta que fent això en el codi

858
00:48:22,000 --> 00:48:26,000
no és tan simple com moure les mans al voltant de

859
00:48:26,000 --> 00:48:28,000
i apuntant els punters en diferents coses.

860
00:48:28,000 --> 00:48:31,000
Però adonar-se que quan arribi el moment de posar en pràctica una mena

861
00:48:31,000 --> 00:48:34,000
una llista enllaçada o una variant d'aquest, si et centres en realitat

862
00:48:34,000 --> 00:48:38,000
aquests fonaments bàsics, els problemes de mida d'un mos que he de esbrinar,

863
00:48:38,000 --> 00:48:43,000
És aquesta mà o la mà d'això, adonar-se que el que és un programa bastant complex

864
00:48:43,000 --> 00:48:47,000
pot, de fet, ser reduït a elements bàsics bastant simples com aquest.

865
00:48:47,000 --> 00:48:51,000
>> Anem a prendre les coses en una direcció més sofisticat encara.

866
00:48:51,000 --> 00:48:53,000
Ara tenim la noció de la llista enllaçada.

867
00:48:53,000 --> 00:48:57,000
També tenim, gràcies al suggeriment de tornar-hi, una llista doblement enllaçada,

868
00:48:57,000 --> 00:49:01,000
que es veu gairebé el mateix, però ara tenim dos punters dins de l'estructura

869
00:49:01,000 --> 00:49:05,000
en comptes d'un, i probablement podríem anomenar els punters anterior i següent

870
00:49:05,000 --> 00:49:08,000
o cap a l'esquerra o cap a la dreta, però, de fet, la necessitat de dos d'ells.

871
00:49:08,000 --> 00:49:10,000
El codi hauria de ser una mica més complicat.

872
00:49:10,000 --> 00:49:12,000
Anita hauria hagut de fer més feina aquí a l'escenari.

873
00:49:12,000 --> 00:49:15,000
Però sens dubte podríem posar en pràctica aquest tipus d'estructura.

874
00:49:15,000 --> 00:49:19,000
En termes de temps d'execució, però, quin seria el temps d'execució

875
00:49:19,000 --> 00:49:24,000
per Anita de trobar un nombre n en una llista enllaçada ara?

876
00:49:24,000 --> 00:49:27,000
Així i gran O de n, així que no és millor que la recerca lineal.

877
00:49:27,000 --> 00:49:29,000
No podem fer una recerca binària, encara que, de nou.

878
00:49:29,000 --> 00:49:34,000
Per què va ser així? No es pot saltar al voltant.

879
00:49:34,000 --> 00:49:36,000
Tot i que, òbviament, veure tots els humans a l'escenari,

880
00:49:36,000 --> 00:49:39,000
i Anita podria haver eyeballed i va dir: "Aquí està la meitat de la llista,"

881
00:49:39,000 --> 00:49:42,000
ella no sap que si ella fos el programa d'ordinador

882
00:49:42,000 --> 00:49:47,000
perquè l'únic que havia de aferrar-se a al començament de l'escenari

883
00:49:47,000 --> 00:49:50,000
va ser Lucas, que va ser el primer indicador.

884
00:49:50,000 --> 00:49:53,000
Ella necessàriament hauria de seguir aquests vincles,

885
00:49:53,000 --> 00:49:56,000
comptant el seu camí fins que va trobar aproximadament la meitat,

886
00:49:56,000 --> 00:49:58,000
i tot i així, ella no sabrà quan ella va arribar a la meitat

887
00:49:58,000 --> 00:50:01,000
llevat que hi va tot el camí fins al final per saber quants són,

888
00:50:01,000 --> 00:50:05,000
després fa marxa enrere, i això també seria difícil a menys que vostè tenia

889
00:50:05,000 --> 00:50:07,000
una llista doblement enllaçada d'algun tipus.

890
00:50:07,000 --> 00:50:10,000
>> Solució de problemes avui, però introduint altres.

891
00:50:10,000 --> 00:50:12,000
Què passa amb una estructura de dades completament diferent?

892
00:50:12,000 --> 00:50:15,000
Aquesta és una fotografia de les safates en Mather House,

893
00:50:15,000 --> 00:50:19,000
i en aquest cas, tenim una estructura de dades també hem de tipus ja s'ha parlant.

894
00:50:19,000 --> 00:50:22,000
Parlem d'una pila en el context de la memòria,

895
00:50:22,000 --> 00:50:26,000
i que és una espècie de anomenat perquè deliberadament una pila en els termes de la memòria

896
00:50:26,000 --> 00:50:31,000
és efectivament una estructura de dades que té més coses i més capes a la part superior de la mateixa.

897
00:50:31,000 --> 00:50:35,000
Però l'interessant d'una pila, com és el cas en la realitat,

898
00:50:35,000 --> 00:50:38,000
és que és un tipus especial d'estructura de dades.

899
00:50:38,000 --> 00:50:42,000
És una estructura de dades mitjançant el qual el primer element de

900
00:50:42,000 --> 00:50:46,000
és l'últim element fora.

901
00:50:46,000 --> 00:50:50,000
Si és la primera safata que es posa a la pila,

902
00:50:50,000 --> 00:50:53,000
que serà desgraciadament l'última safata a ser retirat de la pila,

903
00:50:53,000 --> 00:50:55,000
i això no és necessàriament una cosa bona.

904
00:50:55,000 --> 00:50:58,000
Per contra, es pot pensar que a l'inrevés,

905
00:50:58,000 --> 00:51:02,000
és l'últim dels primers a sortir.

906
00:51:02,000 --> 00:51:05,000
>> Ara, algun escenari vénen a la ment les de tenir una pila

907
00:51:05,000 --> 00:51:08,000
estructura de dades on s'ha de la propietat

908
00:51:08,000 --> 00:51:13,000
l'últim a entrar, primer a sortir, és realment convincent?

909
00:51:13,000 --> 00:51:16,000
¿Això és bo? ¿Això és dolent?

910
00:51:16,000 --> 00:51:19,000
És definitivament una cosa dolenta si les safates no eren tots idèntics

911
00:51:19,000 --> 00:51:21,000
i tots eren diferents colors especials o el que sigui,

912
00:51:21,000 --> 00:51:24,000
i el color que vull és tot el camí a la part inferior.

913
00:51:24,000 --> 00:51:26,000
Per descomptat, vostè no pot aconseguir que, sense gran esforç.

914
00:51:26,000 --> 00:51:28,000
Cal començar per la part superior i treballi cap avall.

915
00:51:28,000 --> 00:51:31,000
De la mateixa manera, què passaria si fos un d'aquests nois del ventilador

916
00:51:31,000 --> 00:51:34,000
que espera tota la nit tractant d'aconseguir un iPhone i comarca

917
00:51:34,000 --> 00:51:36,000
en un lloc com aquest?

918
00:51:36,000 --> 00:51:40,000
¿No seria agradable si la botiga d'Apple

919
00:51:40,000 --> 00:51:42,000
eren una estructura de dades de la pila?

920
00:51:42,000 --> 00:51:44,000
Yay? Nay?

921
00:51:44,000 --> 00:51:47,000
Només és bo per les persones que apareixen en l'últim minut

922
00:51:47,000 --> 00:51:50,000
i després es va treure de la cua.

923
00:51:50,000 --> 00:51:52,000
I de fet, el fet que estava inclinat de manera que dir cua

924
00:51:52,000 --> 00:51:56,000
en realitat és consistent amb el que podríem anomenar aquest tipus d'estructura de dades,

925
00:51:56,000 --> 00:51:59,000
una realitat on l'ordre no importa,

926
00:51:59,000 --> 00:52:02,000
i desitja que el primer a ser el primer a sortir

927
00:52:02,000 --> 00:52:04,000
encara que només sigui pel bé de la justícia humana.

928
00:52:04,000 --> 00:52:07,000
En general, vaig a trucar a això una estructura de dades cua.

929
00:52:07,000 --> 00:52:11,000
>> Resulta que a més de les llistes enllaçades, podem començar a utilitzar aquestes mateixes idees bàsiques

930
00:52:11,000 --> 00:52:15,000
i començar a crear nous i diferents tipus de solucions als problemes.

931
00:52:15,000 --> 00:52:19,000
Per exemple, en el cas d'una pila, que podria representar una pila

932
00:52:19,000 --> 00:52:22,000
utilitzant una estructura de dades com aquest, m'agradaria proposar.

933
00:52:22,000 --> 00:52:26,000
En aquest cas, he declarat una estructura, i ho he dit en l'interior d'aquesta estructura

934
00:52:26,000 --> 00:52:30,000
és una matriu de nombres i després una variable anomenada,

935
00:52:30,000 --> 00:52:33,000
i jo vaig a trucar a això una pila.

936
00:52:33,000 --> 00:52:35,000
Ara, per què aquesta realitat?

937
00:52:35,000 --> 00:52:43,000
En el cas d'una pila, podria treure això de manera efectiva a la pantalla com una matriu.

938
00:52:43,000 --> 00:52:47,000
Aquí està el meu stack. Aquests són els meus números.

939
00:52:47,000 --> 00:52:50,000
I anem a dibuixar com això, això, això, això, això.

940
00:52:50,000 --> 00:52:53,000
I després tinc algun membre de dades diferent aquí,

941
00:52:53,000 --> 00:52:58,000
que s'anomena grandària, de manera que aquest és la mida, i això és nombres,

942
00:52:58,000 --> 00:53:02,000
i col · lectivament, l'iPad sencer aquí representa una estructura de pila.

943
00:53:02,000 --> 00:53:07,000
Ara, per defecte, la mida presumiblement ha de ser inicialitzat a 0,

944
00:53:07,000 --> 00:53:11,000
i el que hi ha dins de la matriu de nombres inicialment

945
00:53:11,000 --> 00:53:14,000
quan per primera vegada assignar una matriu?

946
00:53:14,000 --> 00:53:16,000
Garbage. Qui sap? I en realitat no importa.

947
00:53:16,000 --> 00:53:20,000
Tant se val si és 1, 2, 3, 4, 5, completament a l'atzar

948
00:53:20,000 --> 00:53:25,000
per la mala sort emmagatzemada en l'estructura del meu perquè mentre jo sé que la mida de la pila

949
00:53:25,000 --> 00:53:29,000
és 0, llavors sé programació, no es veuen en cap dels elements de la matriu.

950
00:53:29,000 --> 00:53:31,000
No importa el que hi ha.

951
00:53:31,000 --> 00:53:34,000
No miris a ells, com seria la implicació d'una mida de 0.

952
00:53:34,000 --> 00:53:38,000
>> Però suposem ara segueixo endavant i inseriu alguna cosa a la pila.

953
00:53:38,000 --> 00:53:42,000
Vull inserir el número 5, de manera que posar aquí el número 5,

954
00:53:42,000 --> 00:53:45,000
i després ho poso aquí baix?

955
00:53:45,000 --> 00:53:48,000
Ara realment posar 1 per la mida,

956
00:53:48,000 --> 00:53:50,000
i ara la pila és de grandària 1.

957
00:53:50,000 --> 00:53:53,000
Què passa si segueixo endavant i afegir el nombre, diguem, 7 després?

958
00:53:53,000 --> 00:53:57,000
Això després s'actualitza a 2, i després farem 9,

959
00:53:57,000 --> 00:54:02,000
i després aquesta s'actualitza a 3.

960
00:54:02,000 --> 00:54:05,000
Però ara la característica interessant d'aquesta pila és que

961
00:54:05,000 --> 00:54:09,000
Se suposa que he de treure l'element que si vull fer esclatar

962
00:54:09,000 --> 00:54:12,000
alguna cosa fora de la pila, per així dir-ho?

963
00:54:12,000 --> 00:54:14,000
9 seria el primer que ha d'anar.

964
00:54:14,000 --> 00:54:18,000
Com ha de canviar la imatge si vull treure un element de la pila,

965
00:54:18,000 --> 00:54:20,000
Igual que una safata en Mather?

966
00:54:20,000 --> 00:54:22,000
Si. >> [Estudiant] Fixar la mida a 2.

967
00:54:22,000 --> 00:54:27,000
Exactament, l'únic que fer és ajustar la mida a 2, i ho faig amb la matriu?

968
00:54:27,000 --> 00:54:29,000
Jo no he de fer res.

969
00:54:29,000 --> 00:54:32,000
Podria, només per ser anal, posar un 0 o -1 allà o alguna cosa per significar

970
00:54:32,000 --> 00:54:34,000
que aquest no és un valor de fiar, però això no importa perquè

971
00:54:34,000 --> 00:54:37,000
Puc gravar fora de la pròpia matriu quant temps és

972
00:54:37,000 --> 00:54:41,000
perquè jo sàpiga només es veu en els dos primers elements d'aquesta matriu.

973
00:54:41,000 --> 00:54:47,000
Ara, si em vaig i afegir el número 8 d'aquesta sèrie, com canviar la imatge a continuació?

974
00:54:47,000 --> 00:54:50,000
Això es converteix en 8, i això es converteix en 3.

975
00:54:50,000 --> 00:54:52,000
Vaig a tallar algunes cantonades aquí.

976
00:54:52,000 --> 00:54:56,000
Ara tenim 5, 7, 8, i estem de tornada a una mida de 3.

977
00:54:56,000 --> 00:54:58,000
Això és bastant fàcil d'implementar,

978
00:54:58,000 --> 00:55:06,000
però quan anem a lamentar aquesta decisió de disseny?

979
00:55:06,000 --> 00:55:09,000
Quan les coses comencen a anar malament, molt malament? Si.

980
00:55:09,000 --> 00:55:11,000
[Resposta dels estudiants inaudible]

981
00:55:11,000 --> 00:55:13,000
Quan vulgui tornar enrere i obtenir el primer element que vostè posa endins

982
00:55:13,000 --> 00:55:18,000
>> Aquí és tot i que una pila és una matriu sota la caputxa,

983
00:55:18,000 --> 00:55:21,000
aquestes estructures de dades que hem començat parlant també es coneix generalment com

984
00:55:21,000 --> 00:55:25,000
estructures abstractes de dades de manera que la forma en què s'implementen

985
00:55:25,000 --> 00:55:27,000
és completament en aquest punt.

986
00:55:27,000 --> 00:55:31,000
Una estructura de dades com una pila que se suposa per afegir suport

987
00:55:31,000 --> 00:55:35,000
operacions com d'empenta, que empeny una safata a la pila,

988
00:55:35,000 --> 00:55:39,000
i el pop, que elimina un element de la pila, i això és tot.

989
00:55:39,000 --> 00:55:43,000
Si es va a descarregar codi d'una altra persona que ja ha implementat

990
00:55:43,000 --> 00:55:46,000
això que s'anomena una pila, aquesta persona hauria escrit

991
00:55:46,000 --> 00:55:49,000
només dues funcions per a vostè, empenta i pop, amb un únic propòsit en la vida

992
00:55:49,000 --> 00:55:51,000
seria fer exactament això.

993
00:55:51,000 --> 00:55:54,000
Vostè o ell o ella qui va implementar aquest programa

994
00:55:54,000 --> 00:55:58,000
hauria estat completament el que decideix com implementar

995
00:55:58,000 --> 00:56:00,000
la semàntica d'empènyer i fer esclatar sota de la caputxa

996
00:56:00,000 --> 00:56:03,000
o la funcionalitat d'empènyer i fer esclatar.

997
00:56:03,000 --> 00:56:07,000
I he pres una decisió una mica miop aquí

998
00:56:07,000 --> 00:56:10,000
mitjançant la implementació del meu stack amb aquesta estructura de dades simple per què?

999
00:56:10,000 --> 00:56:12,000
Quan es fa aquesta ruptura estructura de dades?

1000
00:56:12,000 --> 00:56:18,000
En quin moment he de tornar un error quan l'usuari crida push, per exemple?

1001
00:56:18,000 --> 00:56:20,000
[Estudiant] Si no hi ha més espai.

1002
00:56:20,000 --> 00:56:23,000
Exactament, si hi ha espai no més, si m'he excedit la capacitat,

1003
00:56:23,000 --> 00:56:27,000
que és tot en majúscules, ja que suggereix que es tracta d'una espècie de constant global.

1004
00:56:27,000 --> 00:56:30,000
Bé, llavors em vaig a haver de dir: "Ho sento, no puc empènyer altre valor

1005
00:56:30,000 --> 00:56:32,000
a la pila ", igual que en Mather.

1006
00:56:32,000 --> 00:56:36,000
>> En algun moment, arribaran a la part superior d'aquest armari petit.

1007
00:56:36,000 --> 00:56:39,000
No hi ha més espai o la capacitat de la pila, moment en què hi ha algun tipus d'error.

1008
00:56:39,000 --> 00:56:42,000
Han de posar l'element en un altre lloc, la safata en un altre lloc,

1009
00:56:42,000 --> 00:56:44,000
o res en absolut.

1010
00:56:44,000 --> 00:56:47,000
Ara, amb una cua, podríem aplicar una mica diferent.

1011
00:56:47,000 --> 00:56:50,000
Una cua és una mica diferent en què sota la campana, es pot implementar

1012
00:56:50,000 --> 00:56:54,000
com una matriu, però per què, en aquest cas, estic proposant

1013
00:56:54,000 --> 00:56:59,000
tenir també un element de cap que representa el cap de la llista,

1014
00:56:59,000 --> 00:57:06,000
al capdavant de la llista, la primera persona a la fila a la botiga d'Apple, a més de mida?

1015
00:57:06,000 --> 00:57:14,000
Per què necessito una peça addicional de les dades en aquesta llista?

1016
00:57:14,000 --> 00:57:16,000
Penseu en el que els números es

1017
00:57:16,000 --> 00:57:18,000
si he elaborat la següent manera.

1018
00:57:18,000 --> 00:57:21,000
Suposem que aquesta és ara una cua en lloc d'una pila,

1019
00:57:21,000 --> 00:57:24,000
amb la diferència-igual que la botiga d'Apple-cua és just.

1020
00:57:24,000 --> 00:57:27,000
La primera persona en línia al començament de la llista, el número 5 en aquest cas,

1021
00:57:27,000 --> 00:57:30,000
ell o ella es deixarà a la primera botiga.

1022
00:57:30,000 --> 00:57:32,000
Farem això.

1023
00:57:32,000 --> 00:57:35,000
Suposem que aquest és l'estat del meu cua en aquest moment en el temps, i ara la botiga d'Apple

1024
00:57:35,000 --> 00:57:39,000
s'obre i la primera persona, número 5, és conduït a la botiga.

1025
00:57:39,000 --> 00:57:43,000
Com puc canviar la imatge ara que he de-cua la primera persona

1026
00:57:43,000 --> 00:57:47,000
a la part davantera de la línia?

1027
00:57:47,000 --> 00:57:50,000
Què és això? >> [Estudiant] Canvieu la cua.

1028
00:57:50,000 --> 00:57:52,000
Canvieu el cap, així que 5 desapareix.

1029
00:57:52,000 --> 00:57:56,000
En realitat, és com si-la millor manera de fer això?

1030
00:57:56,000 --> 00:58:00,000
En realitat, és com si aquest home desapareix.

1031
00:58:00,000 --> 00:58:03,000
Quin seria el número 7 en fer una botiga real?

1032
00:58:03,000 --> 00:58:05,000
Es donaria un pas endavant molt important.

1033
00:58:05,000 --> 00:58:08,000
>> Però què hem arribat a apreciar el que es fa a les matrius

1034
00:58:08,000 --> 00:58:10,000
i movent coses de lloc?

1035
00:58:10,000 --> 00:58:12,000
Això és una mica d'una pèrdua de temps, oi?

1036
00:58:12,000 --> 00:58:16,000
Per què has de ser tan anal com per tenir la primera persona

1037
00:58:16,000 --> 00:58:21,000
en l'inici de la línia en físicament l'inici de la porció de la memòria?

1038
00:58:21,000 --> 00:58:23,000
Això és completament innecessari. Per què?

1039
00:58:23,000 --> 00:58:26,000
Què podria jo recordi en el seu lloc? >> [Inaudible resposta dels estudiants]

1040
00:58:26,000 --> 00:58:30,000
Exactament, jo només podia recordar amb aquest cap de membre de dades addicional

1041
00:58:30,000 --> 00:58:34,000
que ara el cap de la llista ja no és 0, el que era fa un moment.

1042
00:58:34,000 --> 00:58:39,000
Ara en realitat és el número 1. D'aquesta manera, si una optimització lleu.

1043
00:58:39,000 --> 00:58:44,000
El fet que he de-cua a algú de línia a l'inici de la línia a la botiga d'Apple

1044
00:58:44,000 --> 00:58:47,000
no vol dir que tothom ha de canviar, el que recordo és una operació lineal.

1045
00:58:47,000 --> 00:58:50,000
Jo en canvi constant poden passar temps sol

1046
00:58:50,000 --> 00:58:53,000
i aconseguir llavors una resposta molt més ràpida.

1047
00:58:53,000 --> 00:58:56,000
Però el preu que estic pagant és el que guanyar que el rendiment addicional

1048
00:58:56,000 --> 00:58:58,000
i no haver de canviar tot el món?

1049
00:58:58,000 --> 00:59:01,000
Si. >> [Inaudible resposta dels estudiants]

1050
00:59:01,000 --> 00:59:04,000
Podeu afegir més persones, bé, aquest problema és ortogonal

1051
00:59:04,000 --> 00:59:07,000
al fet que no estem canviant la gent al seu voltant.

1052
00:59:07,000 --> 00:59:11,000
Encara és una matriu, de manera que si no canviem tots o no-

1053
00:59:11,000 --> 00:59:13,000
Oh, ja veig el que vols dir, està bé.

1054
00:59:13,000 --> 00:59:16,000
En realitat, estic d'acord amb el que dius que és gairebé com si

1055
00:59:16,000 --> 00:59:19,000
estem ara mai va a utilitzar l'inici d'aquesta sèrie ja

1056
00:59:19,000 --> 00:59:22,000
perquè si em trec 5, llavors em trec 7.

1057
00:59:22,000 --> 00:59:24,000
Però jo només posar a la gent a la dreta.

1058
00:59:24,000 --> 00:59:28,000
>> Se sent com que estic perdent l'espai, i amb el temps la meva cua es desintegra en el no res,

1059
00:59:28,000 --> 00:59:31,000
de manera que només podria tenir envoltant persones,

1060
00:59:31,000 --> 00:59:35,000
i podríem pensar en aquesta sèrie realment com una mena d'estructura circular,

1061
00:59:35,000 --> 00:59:38,000
però el fem servir operador en C per fer aquest tipus d'envolupant?

1062
00:59:38,000 --> 00:59:40,000
[Resposta dels estudiants inaudible] >> L'operador de mòdul.

1063
00:59:40,000 --> 00:59:43,000
Seria una mica molest per pensar en com es fa l'envoltant,

1064
00:59:43,000 --> 00:59:46,000
però podríem fer-ho, i podríem començar a posar a les persones en el que va ser el front de la línia,

1065
00:59:46,000 --> 00:59:52,000
però només recorda amb aquesta variable cap que el cap real de la línia és en realitat.

1066
00:59:52,000 --> 00:59:57,000
I si, per contra, el nostre objectiu en última instància, però,

1067
00:59:57,000 --> 01:00:00,000
va anar a buscar nombres, com ho vam fer aquí a l'escenari amb Anita,

1068
01:00:00,000 --> 01:00:02,000
però realment volen el millor de tots aquests mons?

1069
01:00:02,000 --> 01:00:05,000
Volem més sofisticació que permet array

1070
01:00:05,000 --> 01:00:09,000
perquè volem que la capacitat de créixer de forma dinàmica l'estructura de dades.

1071
01:00:09,000 --> 01:00:12,000
Però no vull haver de recórrer a una cosa que hem assenyalat

1072
01:00:12,000 --> 01:00:15,000
a la primera conferència no va ser un algoritme òptim,

1073
01:00:15,000 --> 01:00:17,000
que de recerca lineal.

1074
01:00:17,000 --> 01:00:21,000
Resulta que es pot, de fet, aconseguir

1075
01:00:21,000 --> 01:00:24,000
o almenys prop de la constant de temps, de manera que algú com Anita,

1076
01:00:24,000 --> 01:00:27,000
si es configura l'estructura de dades per no ser una llista enllaçada,

1077
01:00:27,000 --> 01:00:30,000
de no ser una pila, per no ser una cua, podria, de fet,

1078
01:00:30,000 --> 01:00:33,000
arribar a una estructura de dades que li permet mirar les coses,

1079
01:00:33,000 --> 01:00:37,000
fins i tot paraules, no només números, en el que anomenarem constant de temps.

1080
01:00:37,000 --> 01:00:40,000
>> I de fet, mirant cap endavant, un dels conjunts de processadors d'aquesta classe és gairebé sempre

1081
01:00:40,000 --> 01:00:43,000
una implementació d'un comprovador d'ortografia, mitjançant el qual

1082
01:00:43,000 --> 01:00:46,000
et donem una altra vegada algunes paraules angleses 150.000 i l'objectiu és

1083
01:00:46,000 --> 01:00:51,000
carregar a la memòria d'aquells i ràpidament ser capaços de respondre a les preguntes de la forma

1084
01:00:51,000 --> 01:00:54,000
aquesta paraula s'escriu correctament?

1085
01:00:54,000 --> 01:00:58,000
I realment seria un fàstic si ha de recórrer els 150.000 paraules per contestar això.

1086
01:00:58,000 --> 01:01:02,000
Però, de fet, veurem que podem fer en un temps molt, molt ràpid.

1087
01:01:02,000 --> 01:01:06,000
I va a implicar alguna cosa aplicació anomenada taula hash,

1088
01:01:06,000 --> 01:01:09,000
i encara que a primera vista aquesta cosa anomenada taula hash es va a

1089
01:01:09,000 --> 01:01:12,000
anem a aconseguir aquests temps súper ràpids de resposta,

1090
01:01:12,000 --> 01:01:18,000
resulta que existeix de fet un problema.

1091
01:01:18,000 --> 01:01:23,000
Quan arriba el moment de posar en pràctica aquesta cosa anomenada de nou, ho estic fent de nou.

1092
01:01:23,000 --> 01:01:25,000
Jo sóc l'únic aquí.

1093
01:01:25,000 --> 01:01:28,000
Quan arriba el moment de l'aplicació d'aquesta cosa anomenada taula hash,

1094
01:01:28,000 --> 01:01:30,000
haurem de prendre una decisió.

1095
01:01:30,000 --> 01:01:32,000
Què tan gran ha de ser aquesta cosa en realitat?

1096
01:01:32,000 --> 01:01:36,000
I quan vam començar a inserir nombres en aquesta taula hash,

1097
01:01:36,000 --> 01:01:38,000
Com podem guardar-los de forma

1098
01:01:38,000 --> 01:01:42,000
que puguem tornar a sortir tan ràpid com ens les van donar en?

1099
01:01:42,000 --> 01:01:45,000
Però ja veurem d'aquí a poc, que aquesta qüestió de

1100
01:01:45,000 --> 01:01:48,000
quan és l'aniversari de tots en la classe serà molt afí.

1101
01:01:48,000 --> 01:01:51,000
Resulta que en aquesta sala, tenim uns pocs centenars de persones,

1102
01:01:51,000 --> 01:01:56,000
així que les probabilitats que dues de nosaltres tenim el mateix aniversari és probablement bastant alt.

1103
01:01:56,000 --> 01:01:58,000
Què passa si només hi havia 40 de nosaltres en aquesta sala?

1104
01:01:58,000 --> 01:02:02,000
Quines són les probabilitats de que dues persones tinguin el mateix aniversari?

1105
01:02:02,000 --> 01:02:04,000
[Els estudiants] Més del 50%.

1106
01:02:04,000 --> 01:02:06,000
Si, més de 50%. De fet, fins i tot em va portar una carta.

1107
01:02:06,000 --> 01:02:08,000
Resulta que-i això és realment només un avançament de vista prèvia

1108
01:02:08,000 --> 01:02:12,000
si només hi ha 58 de nosaltres en aquesta sala, la probabilitat que 2 de nosaltres

1109
01:02:12,000 --> 01:02:16,000
tinguin el mateix aniversari és enormement alt, gairebé el 100%,

1110
01:02:16,000 --> 01:02:20,000
i això va a causar una gran quantitat de dany per a nosaltres el dimecres.

1111
01:02:20,000 --> 01:02:24,000
>> Dit això, anem a aixecar la sessió aquí. Ens veiem el dimecres.

1112
01:02:24,000 --> 01:02:28,000
[Aplaudiment]

1113
01:02:28,000 --> 01:02:30,000
[CS50.TV]