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

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

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

4
00:00:08,000 --> 00:00:12,000
>> Este é CS50, e este é o inicio da semana 6,

5
00:00:12,000 --> 00:00:16,000
así un par de novas ferramentas están dispoñibles para vostede aproveitar,

6
00:00:16,000 --> 00:00:19,000
o primeiro dos cales é chamado CS50 estilo.

7
00:00:19,000 --> 00:00:22,000
As probabilidades son, se vostede é como eu ou calquera dos compañeiros de ensino,

8
00:00:22,000 --> 00:00:26,000
probablemente xa viu un programa cuxo estilo parece un pouco algo como isto.

9
00:00:26,000 --> 00:00:30,000
Quizais comezar a cortar algúns cantos, tarde de noite, ou vai tratar con isto máis tarde,

10
00:00:30,000 --> 00:00:32,000
e entón un TF ou CA vén máis durante o expediente.

11
00:00:32,000 --> 00:00:34,000
Entón é difícil para nós ler.

12
00:00:34,000 --> 00:00:38,000
Ben, este código é sintaticamente correcta, e ha compilar e vai realmente funcionar.

13
00:00:38,000 --> 00:00:40,000
Pero definitivamente non é un 5 para o estilo.

14
00:00:40,000 --> 00:00:45,000
>> Pero agora, se imos a este directorio aquí-

15
00:00:45,000 --> 00:00:48,000
e entender que eu teño conditions2.c-

16
00:00:48,000 --> 00:00:55,000
e eu corro este novo mando, style50 nesta conditions2.c arquivo, intro

17
00:00:55,000 --> 00:00:57,000
entender que me informou de que foi estilizado.

18
00:00:57,000 --> 00:01:00,000
Gedit entendeu que o ficheiro foi modificado no disco,

19
00:01:00,000 --> 00:01:08,000
e se eu premer en recargar, todos os seus problemas están agora automatizado.

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

21
00:01:15,000 --> 00:01:17,000
Iso é unha das cousas que fixemos este fin de semana.

22
00:01:17,000 --> 00:01:20,000
Entender que é imperfecto porque hai algún código

23
00:01:20,000 --> 00:01:23,000
que simplemente non será capaz de estilizar perfectamente,

24
00:01:23,000 --> 00:01:26,000
pero que esta é agora unha ferramenta que pode aproveitar de

25
00:01:26,000 --> 00:01:33,000
só para aparcar algunhas das claves máis errantly colocado cacheados e afíns.

26
00:01:33,000 --> 00:01:36,000
>> Pero o máis interesante é agora CS50 Check.

27
00:01:36,000 --> 00:01:39,000
Con CS50 Check, realmente pode realizar as probas de corrección mesmos

28
00:01:39,000 --> 00:01:42,000
no seu propio código que os compañeiros de ensino son capaces de.

29
00:01:42,000 --> 00:01:44,000
Este é unha utilidade de liña de comandos que vén agora o aparello

30
00:01:44,000 --> 00:01:46,000
así que fai unha update50 por

31
00:01:46,000 --> 00:01:49,000
pset catro especificacións, e usalo esencialmente coma este.

32
00:01:49,000 --> 00:01:51,000
Corre o check50 mando.

33
00:01:51,000 --> 00:01:56,000
Entón pasa un argumento de liña de comandos, ou, máis xeralmente coñecido como un interruptor ou unha bandeira.

34
00:01:56,000 --> 00:01:58,000
Xeralmente, as cousas que teñen guións son chamados un interruptor

35
00:01:58,000 --> 00:02:02,000
a un programa de liña de comandos, así c especifica

36
00:02:02,000 --> 00:02:04,000
as comprobacións que quere executar.

37
00:02:04,000 --> 00:02:07,000
>> As probas que quere executar son identificados individualmente por esa secuencia,

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

39
00:02:10,000 --> 00:02:13,000
Noutras palabras, iso é só unha secuencia arbitraria, senón única

40
00:02:13,000 --> 00:02:18,000
que usan para identificar probas 4 pset de corrección.

41
00:02:18,000 --> 00:02:21,000
E entón especificar unha lista separada por espazo de arquivos que quere cargar

42
00:02:21,000 --> 00:02:24,000
Comproba a CS50 para a análise.

43
00:02:24,000 --> 00:02:29,000
Por exemplo, se eu ir para a miña solución aquí para resize.c-

44
00:02:29,000 --> 00:02:31,000
deixe-me abrir un maior terminal de ventá

45
00:02:31,000 --> 00:02:42,000
e eu ir adiante e executar digamos check50-c 2012/pset4/resize,

46
00:02:42,000 --> 00:02:46,000
e entón eu ir adiante e especificar os nomes dos ficheiros,

47
00:02:46,000 --> 00:02:49,000
resize.c, e prema a tecla Enter, el comprime,

48
00:02:49,000 --> 00:02:53,000
el leva, el verifica, e eu só fallou unha morea de probas.

49
00:02:53,000 --> 00:02:59,000
O de vermello na esquina superior esquerda di que resize.c e BMP existe.

50
00:02:59,000 --> 00:03:01,000
Ese foi o exame. Esa foi a pregunta que nós fixemos.

51
00:03:01,000 --> 00:03:04,000
E é infeliz porque a resposta era falsa.

52
00:03:04,000 --> 00:03:08,000
O texto en branco debaixo di esperar bmp.h de existir, e iso é simplemente culpa miña.

53
00:03:08,000 --> 00:03:11,000
Eu esquezo de envialo, entón eu teño subir dous arquivos,

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

55
00:03:14,000 --> 00:03:17,000
Pero agora observar todos os outros probas son en amarelo porque non correr,

56
00:03:17,000 --> 00:03:21,000
e así o rostro sorrinte é vertical, porque non é nin feliz nin triste,

57
00:03:21,000 --> 00:03:25,000
pero temos que resolver este problema en vermello antes de esas outras comprobacións será executado.

58
00:03:25,000 --> 00:03:27,000
>> Deixe-me corrixir isto.

59
00:03:27,000 --> 00:03:30,000
Deixe-me afastar e executar de novo esa, esta vez con bmp.h tamén

60
00:03:30,000 --> 00:03:34,000
na liña de comandos, Intro, e agora, se todo funcionar ben,

61
00:03:34,000 --> 00:03:38,000
que vai comprobar e voltar un resultado-Manteña a respiración-

62
00:03:38,000 --> 00:03:42,000
todo verde, o que significa que eu estou indo moi ben en pset 4 ata agora.

63
00:03:42,000 --> 00:03:44,000
Podes ver e deducir do texto descritivo aquí

64
00:03:44,000 --> 00:03:47,000
exactamente que é o que probamos.

65
00:03:47,000 --> 00:03:49,000
Probar primeiro é que os arquivos existen?

66
00:03:49,000 --> 00:03:51,000
A continuación, probar fai compilación resize.c?

67
00:03:51,000 --> 00:03:58,000
Entón nós probamos non é redimensionar unha BMP 1x1 pixel cando n, o factor de cambio de tamaño, é 1.

68
00:03:58,000 --> 00:04:01,000
Agora, se non ten idea do que n é, vai unha vez que mergullo pset 4,

69
00:04:01,000 --> 00:04:04,000
pero que simplemente é unha comprobación de sanidade para asegurarse de que non é o redimensionamento

70
00:04:04,000 --> 00:04:08,000
unha imaxe en todos, o factor de cambio de tamaño é 1.

71
00:04:08,000 --> 00:04:14,000
Se, polo contrario, el redimensiona un pixel 1x1 para un 1x1 pixel BMP para 2x2 correctamente

72
00:04:14,000 --> 00:04:19,000
cando n é 2, entón de forma semellante, formas mina de conformidade.

73
00:04:19,000 --> 00:04:22,000
>> En suma, este é significativo, un, tome a travesía dos dedos

74
00:04:22,000 --> 00:04:25,000
fóra da ecuación dereita antes de enviar o seu pset.

75
00:04:25,000 --> 00:04:28,000
Vostede saberá exactamente o que o seu TF logo saberá

76
00:04:28,000 --> 00:04:30,000
cando vai sobre o envío de algúns deses conxuntos de problemas,

77
00:04:30,000 --> 00:04:34,000
e tamén a motivación pedagóxica é realmente poñer

78
00:04:34,000 --> 00:04:37,000
a oportunidade na fronte de ti para que, cando sabe a priori

79
00:04:37,000 --> 00:04:39,000
que non hai erros no seu código e probas que non están sendo pasados,

80
00:04:39,000 --> 00:04:43,000
pode pór máis eficaz do tempo na fronte para resolver estes problemas

81
00:04:43,000 --> 00:04:45,000
en vez de perder puntos, obter feedback do seu TF,

82
00:04:45,000 --> 00:04:48,000
e despois ir, "Ahh," como eu debería ter percibido iso.

83
00:04:48,000 --> 00:04:50,000
Agora, polo menos, hai unha ferramenta para axudar a atopar isto.

84
00:04:50,000 --> 00:04:52,000
El non vai apuntar onde é o problema, pero el vai dicir

85
00:04:52,000 --> 00:04:54,000
o que é un síntoma da mesma.

86
00:04:54,000 --> 00:04:57,000
>> Agora realizar as probas non son necesariamente exhaustiva.

87
00:04:57,000 --> 00:04:59,000
Só porque ten unha pantalla chea de verde Smiley Faces

88
00:04:59,000 --> 00:05:02,000
non significa que o seu código é perfecto, pero iso non significa

89
00:05:02,000 --> 00:05:06,000
que pasou algunhas probas prescritos pola especificación.

90
00:05:06,000 --> 00:05:08,000
Ás veces a xente non vai liberar cheques.

91
00:05:08,000 --> 00:05:10,000
Por exemplo, whodunit, un dos aspectos da pset 4,

92
00:05:10,000 --> 00:05:15,000
e tipo de decepcionante se nós lle damos

93
00:05:15,000 --> 00:05:18,000
a resposta para o que é, e hai unha serie de formas para revelar

94
00:05:18,000 --> 00:05:21,000
quen é a persoa que o ruído vermello.

95
00:05:21,000 --> 00:05:24,000
A especificación será sempre especificar no futuro para pset en diante 5

96
00:05:24,000 --> 00:05:26,000
o que verifica existir para ti.

97
00:05:26,000 --> 00:05:28,000
Vostede vai entender que hai esa URL en branco no fondo.

98
00:05:28,000 --> 00:05:30,000
Polo momento, esta é só a saída de diagnóstico.

99
00:05:30,000 --> 00:05:33,000
Se visitar a URL, vai ter unha morea de tolos, mensaxes enigmáticas

100
00:05:33,000 --> 00:05:36,000
que está invitado a ollar a través, pero é sobre todo para o persoal

101
00:05:36,000 --> 00:05:41,000
para que poidamos diagnosticar e depurar erros en check50 si.

102
00:05:41,000 --> 00:05:46,000
>> Sen delongas, imos seguir adiante de onde paramos.

103
00:05:46,000 --> 00:05:48,000
CS50 biblioteca tomamos para concedida por algunhas semanas,

104
00:05:48,000 --> 00:05:52,000
pero, a continuación, a semana pasada, comezamos a descascada cara atrás unha das capas do mesmo.

105
00:05:52,000 --> 00:05:55,000
Comezamos poñendo de lado cadea en favor do que en vez diso?

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

107
00:05:57,000 --> 00:05:59,000
* Char, que foi un char * todo este tempo,

108
00:05:59,000 --> 00:06:03,000
pero agora non temos que finxir que é un tipo cadea de datos real.

109
00:06:03,000 --> 00:06:06,000
En vez diso, foi sinónimo de sorte para char *,

110
00:06:06,000 --> 00:06:09,000
e unha cadea é unha secuencia de caracteres,

111
00:06:09,000 --> 00:06:14,000
Entón, por que será que ten sentido para representar cadeas como char * s?

112
00:06:14,000 --> 00:06:20,000
O que fai un char * representan no contexto dese concepto dunha cadea?

113
00:06:20,000 --> 00:06:23,000
Si >> [Estudante] O primeiro carácter.

114
00:06:23,000 --> 00:06:25,000
Bo, o primeiro carácter, pero non é así o primeiro carácter.

115
00:06:25,000 --> 00:06:27,000
É unha [Os alumnos] Enderezo.

116
00:06:27,000 --> 00:06:29,000
Bo, o enderezo do primeiro carácter.

117
00:06:29,000 --> 00:06:33,000
Todo o que é necesario para representar unha cadea na memoria dun ordenador

118
00:06:33,000 --> 00:06:36,000
é só o enderezo único do byte primeiro.

119
00:06:36,000 --> 00:06:38,000
Non ten sequera saber canto tempo é

120
00:06:38,000 --> 00:06:42,000
pois como pode descubrir iso dinamicamente?

121
00:06:42,000 --> 00:06:44,000
[Estudante] lonxitude cadea.

122
00:06:44,000 --> 00:06:48,000
Pode chamar lonxitude da corda, excelente, pero como funciona a lonxitude da corda?

123
00:06:48,000 --> 00:06:50,000
O que fai? Si

124
00:06:50,000 --> 00:06:52,000
[Estudante] Continúe indo ata chegar o carácter nulo.

125
00:06:52,000 --> 00:06:54,000
Si, exactamente, el só interactúa con un loop for, while,

126
00:06:54,000 --> 00:06:57,000
calquera que sexa a partir de * ata o final, e que o final está representada

127
00:06:57,000 --> 00:07:01,000
por \ 0, o personaxe chamado nulo, nulo,

128
00:07:01,000 --> 00:07:05,000
non debe ser confundida coa nulo, o que é un punteiro,

129
00:07:05,000 --> 00:07:07,000
que entrará en conversa de novo hoxe.

130
00:07:07,000 --> 00:07:11,000
>> Nós descascada unha capa de GetInt, e despois demos un ollo no GetString,

131
00:07:11,000 --> 00:07:14,000
e lembrar que estas dúas funcións, ou realmente,

132
00:07:14,000 --> 00:07:18,000
GetString, estaba usando unha determinada función

133
00:07:18,000 --> 00:07:21,000
para realmente analizar, é dicir, ler ou analizar, a entrada do usuario.

134
00:07:21,000 --> 00:07:25,000
E o que foi que nova función?

135
00:07:25,000 --> 00:07:27,000
Scanf ou sscanf. El realmente ven en algúns sabores diferentes.

136
00:07:27,000 --> 00:07:31,000
Hai scanf, hai sscanf, hai fscanf.

137
00:07:31,000 --> 00:07:35,000
De momento, porén, imos centrar o máis facilmente ilustrado,

138
00:07:35,000 --> 00:07:38,000
e deixe-me ir adiante e abrir o dispositivo

139
00:07:38,000 --> 00:07:41,000
un arquivo como este, scanf1.c.

140
00:07:41,000 --> 00:07:43,000
Este é un programa super sinxelo,

141
00:07:43,000 --> 00:07:46,000
pero que fai algo que nunca fixemos

142
00:07:46,000 --> 00:07:48,000
sen a axuda da biblioteca CS50.

143
00:07:48,000 --> 00:07:51,000
Este recibe un int dun usuario. Como funciona isto?

144
00:07:51,000 --> 00:07:53,000
Ben, na liña 16 hai,

145
00:07:53,000 --> 00:07:56,000
entender que declaramos un int x chamado, e neste momento da historia,

146
00:07:56,000 --> 00:07:58,000
o que é o valor de x?

147
00:07:58,000 --> 00:08:00,000
[Resposta do alumno inaudível]

148
00:08:00,000 --> 00:08:02,000
[David M.] Dereito, quen sabe, algún valor lixo potencialmente, así, o 17, nós só dicir que o usuario

149
00:08:02,000 --> 00:08:06,000
me dar un número, por favor, e paso 18 é onde está interesante.

150
00:08:06,000 --> 00:08:11,000
Scanf parece prestar unha idea de printf en que el usa eses códigos de formato entre comiñas.

151
00:08:11,000 --> 00:08:13,000
D% é, naturalmente, un número decimal.

152
00:08:13,000 --> 00:08:21,000
Pero por que estou pasando & x no canto de só x?

153
00:08:21,000 --> 00:08:24,000
O primeiro é correcta. Si

154
00:08:24,000 --> 00:08:26,000
[Resposta do alumno inaudível]

155
00:08:26,000 --> 00:08:31,000
Exactamente, o obxectivo do programa, como o GetInt propia función,

156
00:08:31,000 --> 00:08:34,000
é para ter unha int usuario que pode pasar funcións

157
00:08:34,000 --> 00:08:38,000
todas as variables que quero, pero eu non paso-los por referencia

158
00:08:38,000 --> 00:08:41,000
ou por enderezo ou punteiro, todos sinónimos para fins de hoxe,

159
00:08:41,000 --> 00:08:46,000
a continuación, que a función non ten capacidade de cambiar o contido da variable.

160
00:08:46,000 --> 00:08:49,000
Isto pasaría nunha copia así como a versión de buggy de intercambio

161
00:08:49,000 --> 00:08:51,000
que xa falamos sobre algunhas veces agora.

162
00:08:51,000 --> 00:08:54,000
>> Pero en vez diso, facendo & x, eu estou literalmente pasando o que?

163
00:08:54,000 --> 00:08:57,000
[Alumno] O enderezo. >> O enderezo de x.

164
00:08:57,000 --> 00:09:01,000
É como debuxar un mapa para a función chamada scanf e dicindo aquí,

165
00:09:01,000 --> 00:09:04,000
Estas son as direccións para un bloque de memoria no ordenador

166
00:09:04,000 --> 00:09:07,000
que pode ir almacenar algún enteiro dentro

167
00:09:07,000 --> 00:09:10,000
Para que sscanf para facer agora que

168
00:09:10,000 --> 00:09:13,000
o operador, o que parte da sintaxe é que vai ter que usar

169
00:09:13,000 --> 00:09:19,000
aínda que non poida velo porque alguén escribiu esa función?

170
00:09:19,000 --> 00:09:21,000
Noutras palabras - o que é iso?

171
00:09:21,000 --> 00:09:23,000
[Estudante] X ler.

172
00:09:23,000 --> 00:09:27,000
Non vai ser unha lectura, pero só en relación á x aquí.

173
00:09:27,000 --> 00:09:30,000
Se scanf está pasado o enderezo de x,

174
00:09:30,000 --> 00:09:35,000
sintaticamente, o operador está obrigado a existir nalgún lugar

175
00:09:35,000 --> 00:09:38,000
dentro de implantación, de xeito que scanf scanf

176
00:09:38,000 --> 00:09:42,000
Pode realmente escribir un número de 2 a ese enderezo?

177
00:09:42,000 --> 00:09:44,000
Si, entón o *.

178
00:09:44,000 --> 00:09:47,000
Lembre-se de que o * é o noso operador dereference, o que esencialmente significa ir máis alá.

179
00:09:47,000 --> 00:09:50,000
>> Así que ten sido entregado un enderezo, como é o caso aquí,

180
00:09:50,000 --> 00:09:53,000
scanf é, probablemente, se nós realmente mirou ao redor do seu código fonte

181
00:09:53,000 --> 00:09:59,000
está facendo * x ou o equivalente a realmente ir a este enderezo e poñer un valor alí.

182
00:09:59,000 --> 00:10:02,000
Agora, o xeito no que scanf recibe a entrada do teclado,

183
00:10:02,000 --> 00:10:04,000
imos trasfega as mans para fóra para hoxe.

184
00:10:04,000 --> 00:10:07,000
Basta asumir que o sistema operativo permite que sscanf para falar

185
00:10:07,000 --> 00:10:11,000
para o teclado do usuario, pero neste punto agora na liña 19,

186
00:10:11,000 --> 00:10:14,000
cando simplemente imprimir x, parece ser o caso

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

188
00:10:17,000 --> 00:10:19,000
Isto é exactamente como scanf funciona, e lembrar a semana pasada

189
00:10:19,000 --> 00:10:25,000
é exactamente como GetString e GetInt ea súa outra familia de funcións

190
00:10:25,000 --> 00:10:28,000
finalmente funciona, aínda que con lixeira variación como sscanf,

191
00:10:28,000 --> 00:10:31,000
o que significa dixitalizar unha cadea no canto do teclado.

192
00:10:31,000 --> 00:10:33,000
Pero imos dar un ollo a unha pequena variación desta.

193
00:10:33,000 --> 00:10:37,000
En scanf2, realmente errou.

194
00:10:37,000 --> 00:10:42,000
O que está mal, e eu vou ocultar o comentario que explica como moi

195
00:10:42,000 --> 00:10:47,000
o que está mal con este programa, a versión 2?

196
00:10:47,000 --> 00:10:55,000
Sexa tan técnico como posible neste momento.

197
00:10:55,000 --> 00:10:57,000
Parece moi bo.

198
00:10:57,000 --> 00:11:03,000
É ben recuado, pero-

199
00:11:03,000 --> 00:11:07,000
Ok, que tal imos poda-la cara abaixo para preguntas máis curtos?

200
00:11:07,000 --> 00:11:17,000
Liña 16. O que é liña 16 facendo en inglés, pero precisa técnico?

201
00:11:17,000 --> 00:11:20,000
Quedando un pouco raro. Si, Michael.

202
00:11:20,000 --> 00:11:25,000
[Estudante] Está apuntando para a primeira letra dunha cadea.

203
00:11:25,000 --> 00:11:27,000
>> Ok, preto. Deixe-me axustar iso un pouco.

204
00:11:27,000 --> 00:11:33,000
Apuntando para a primeira letra dunha cadea, está declarando unha variable chamada tapón

205
00:11:33,000 --> 00:11:36,000
que pode apuntar para o primeiro enderezo dunha cadea,

206
00:11:36,000 --> 00:11:39,000
ou sexa, que apuntar máis precisamente a unha char.

207
00:11:39,000 --> 00:11:42,000
Teña en conta que non é realmente apuntando para calquera lugar, porque non hai operador de asignación.

208
00:11:42,000 --> 00:11:46,000
Non hai signo igual, entón todo o que estamos facendo é asignación de reserva variable chamada.

209
00:11:46,000 --> 00:11:49,000
El pasa a ser de 32 bits porque é un punteiro,

210
00:11:49,000 --> 00:11:52,000
E o contido de tapón, finalmente, presuntamente

211
00:11:52,000 --> 00:11:57,000
conterá un enderezo de un char, pero por agora, o que tapón contén?

212
00:11:57,000 --> 00:11:59,000
Só algúns teito, quen sabe, algún valor de lixo,

213
00:11:59,000 --> 00:12:03,000
porque non explicitamente inicializar, non debemos asumir nada.

214
00:12:03,000 --> 00:12:06,000
Ok, entón agora é a liña 17-o que fai a liña 17 ten?

215
00:12:06,000 --> 00:12:08,000
Quizais que vai quentar iso.

216
00:12:08,000 --> 00:12:10,000
Ela imprime unha cadea, non?

217
00:12:10,000 --> 00:12:12,000
Ela imprime Cordas por favor.

218
00:12:12,000 --> 00:12:15,000
>> Liña 18 é unha especie de familia agora que acabamos de ver unha variación deste

219
00:12:15,000 --> 00:12:18,000
pero cun código de formato diferente, por iso, en liña 18,

220
00:12:18,000 --> 00:12:23,000
estamos dicindo scanf aquí é o enderezo dun bloque de memoria.

221
00:12:23,000 --> 00:12:27,000
Eu quero que tocar unha corda, como implicado por% s,

222
00:12:27,000 --> 00:12:32,000
pero o problema é que non temos feito algunhas cousas aquí.

223
00:12:32,000 --> 00:12:35,000
O que é un dos problemas?

224
00:12:35,000 --> 00:12:38,000
[Estudante] Está tentando dereference un punteiro nulo.

225
00:12:38,000 --> 00:12:41,000
Bo, punteiros nulos ou só outro xeito descoñecido.

226
00:12:41,000 --> 00:12:45,000
Vostede está entregando scanf un enderezo, pero dixo hai pouco

227
00:12:45,000 --> 00:12:49,000
que ese enderezo é algún valor lixo porque realmente non atribúe-lo a nada,

228
00:12:49,000 --> 00:12:53,000
e por iso está dicindo scanf efectivamente ir colocar unha corda aquí,

229
00:12:53,000 --> 00:12:56,000
pero non sei onde aquí aínda é,

230
00:12:56,000 --> 00:12:59,000
entón nós realmente non teño memoria alocada para buffer.

231
00:12:59,000 --> 00:13:03,000
Ademais, o que tampouco, aínda dicindo scanf?

232
00:13:03,000 --> 00:13:06,000
Supoña que este era un anaco de memoria, e non era un valor de lixo,

233
00:13:06,000 --> 00:13:09,000
pero aínda non está dicindo scanf algo importante.

234
00:13:09,000 --> 00:13:12,000
[Estudante] onde realmente é, o comercial.

235
00:13:12,000 --> 00:13:15,000
Ampersand, polo tanto, neste caso, está todo ben.

236
00:13:15,000 --> 00:13:18,000
Porque o buffer xa está declarado como un punteiro

237
00:13:18,000 --> 00:13:22,000
coa peza * de sintaxe, non necesitamos usar e comercial

238
00:13:22,000 --> 00:13:25,000
porque é xa un enderezo, pero eu creo que oín-lo aquí.

239
00:13:25,000 --> 00:13:27,000
[Estudante] Como grande é?

240
00:13:27,000 --> 00:13:29,000
Bo, non estamos dicindo scanf quão grande ese buffer é,

241
00:13:29,000 --> 00:13:32,000
o que significa que, aínda que fose un tapón punteiro,

242
00:13:32,000 --> 00:13:35,000
estamos dicindo scanf, colocar unha corda aquí,

243
00:13:35,000 --> 00:13:38,000
pero aquí pode ser de 2 bytes, que pode ser de 10 bytes, que podería ser un megabyte.

244
00:13:38,000 --> 00:13:41,000
Scanf non ten idea, e porque este é un anaco da memoria

245
00:13:41,000 --> 00:13:43,000
presuntamente, non é unha secuencia aínda.

246
00:13:43,000 --> 00:13:48,000
É só unha corda unha vez que escribir caracteres e un \ 0 para o bloque de memoria.

247
00:13:48,000 --> 00:13:51,000
Agora é só un anaco de memoria.

248
00:13:51,000 --> 00:13:55,000
Scanf non vai saber cando deixar de escribir a este enderezo.

249
00:13:55,000 --> 00:13:59,000
>> Se lembrar algúns exemplos no pasado que eu aleatoriamente tecleados no teclado

250
00:13:59,000 --> 00:14:03,000
tentando estourar un buffer, e falamos o venres sobre exactamente isto.

251
00:14:03,000 --> 00:14:07,000
Se un adversario de algunha maneira, inxecta no seu programa unha palabra moi grande

252
00:14:07,000 --> 00:14:10,000
ou frase ou ben estaba esperando pode invadida

253
00:14:10,000 --> 00:14:13,000
unha peza de memoria, que pode ter consecuencias malas,

254
00:14:13,000 --> 00:14:15,000
como asumir todo o programa en si.

255
00:14:15,000 --> 00:14:17,000
Necesitamos corrixir isto de algunha maneira.

256
00:14:17,000 --> 00:14:20,000
Deixe-me afastar e ir para a versión 3 do programa.

257
00:14:20,000 --> 00:14:22,000
Isto é un pouco mellor.

258
00:14:22,000 --> 00:14:24,000
Nesta versión, notar a diferenza.

259
00:14:24,000 --> 00:14:27,000
Na liña 16, estou de novo declarar unha variable chamada tapón,

260
00:14:27,000 --> 00:14:29,000
pero o que é iso agora?

261
00:14:29,000 --> 00:14:33,000
É unha matriz de 16 caracteres.

262
00:14:33,000 --> 00:14:36,000
Iso é bo, porque iso significa que podo agora dicir scanf

263
00:14:36,000 --> 00:14:39,000
aquí é unha peza de memoria real.

264
00:14:39,000 --> 00:14:42,000
Vostede case pode pensar en matrices como punteiros, agora,

265
00:14:42,000 --> 00:14:44,000
aínda que eles non son realmente equivalentes.

266
00:14:44,000 --> 00:14:47,000
Se comportan de xeito diferente en diferentes contextos.

267
00:14:47,000 --> 00:14:50,000
Pero é certamente o caso de que o buffer é referencia

268
00:14:50,000 --> 00:14:53,000
16 caracteres contiguos porque é iso que é unha matriz

269
00:14:53,000 --> 00:14:55,000
e foi por algunhas semanas agora.

270
00:14:55,000 --> 00:14:59,000
>> Aquí, eu estou dicindo scanf aquí está un anaco da memoria.

271
00:14:59,000 --> 00:15:01,000
Esta vez é na verdade un anaco da memoria,

272
00:15:01,000 --> 00:15:07,000
senón porque é que este programa aínda explorável?

273
00:15:07,000 --> 00:15:11,000
O que hai de malo aínda?

274
00:15:11,000 --> 00:15:14,000
Eu dixen me dar 16 bytes, pero-

275
00:15:14,000 --> 00:15:16,000
[Alumno] O que se tipo en máis de 16 anos?

276
00:15:16,000 --> 00:15:20,000
Exactamente, e se o usuario escribe 17 caracteres ou carácter 1700?

277
00:15:20,000 --> 00:15:23,000
En realidade, imos ver se non podemos tropezar este erro agora.

278
00:15:23,000 --> 00:15:25,000
É mellor, pero non perfecto.

279
00:15:25,000 --> 00:15:28,000
Deixe-me ir adiante e executar facer scanf3 para compilar este programa.

280
00:15:28,000 --> 00:15:34,000
Déixame correr scanf3, cadea por favor: Ola, e parece que estamos ben.

281
00:15:34,000 --> 00:15:37,000
Deixe-me tentar un pouco máis, Ola alí.

282
00:15:37,000 --> 00:15:42,000
Ok, imos facer Ola alí como está hoxe, Intro.

283
00:15:42,000 --> 00:15:54,000
Obtendo tipo de sorte aquí, imos dicir Ola alí como está.

284
00:15:54,000 --> 00:15:56,000
Drogas.

285
00:15:56,000 --> 00:16:03,000
Ok, entón tivemos sorte. Imos ver se non podemos fixar iso.

286
00:16:03,000 --> 00:16:06,000
Non, iso non me vai deixar copiar.

287
00:16:06,000 --> 00:16:09,000
Imos tentar de novo.

288
00:16:09,000 --> 00:16:12,000
Todo ben, prepara-se.

289
00:16:12,000 --> 00:16:20,000
Imos ver canto tempo podo finxir foco mentres aínda está facendo iso.

290
00:16:20,000 --> 00:16:23,000
Drogas. Iso é moi apropiado, en realidade.

291
00:16:23,000 --> 00:16:26,000
Alí imos nós.

292
00:16:26,000 --> 00:16:30,000
Punto fixo.

293
00:16:30,000 --> 00:16:34,000
>> Isto, embaraçando aínda que tamén sexa, é tamén unha das fontes de gran confusión

294
00:16:34,000 --> 00:16:38,000
ao escribir programas que teñen erros, porque se manifestan

295
00:16:38,000 --> 00:16:40,000
só de cando en vez, ás veces.

296
00:16:40,000 --> 00:16:43,000
A realidade é que, mesmo se o código está completamente roto,

297
00:16:43,000 --> 00:16:46,000
el só podería ser completamente roto de cando en vez

298
00:16:46,000 --> 00:16:49,000
porque ás veces, esencialmente, o que pasa é que o sistema operativo aloca

299
00:16:49,000 --> 00:16:52,000
un pouco máis de memoria do que realmente precisa, por calquera razón,

300
00:16:52,000 --> 00:16:57,000
e para que ninguén máis está a usar a memoria pronto tras o seu anaco de 16 caracteres,

301
00:16:57,000 --> 00:17:01,000
por iso, se vai para 17, 18, 19, calquera que sexa, non é un negocio tan grande.

302
00:17:01,000 --> 00:17:04,000
Agora, o ordenador, aínda que non falla nese punto,

303
00:17:04,000 --> 00:17:09,000
Pode, eventualmente, usar o número de bytes de 17 ou 18 ou 19 para outra cousa,

304
00:17:09,000 --> 00:17:14,000
momento no que os datos que poñer alí, aínda que excesivamente longo,

305
00:17:14,000 --> 00:17:18,000
vai ser substituídas potencialmente por algunha outra función.

306
00:17:18,000 --> 00:17:21,000
Non é necesariamente vai permanecer intacta,

307
00:17:21,000 --> 00:17:23,000
pero non vai necesariamente provocar un fallo seg.

308
00:17:23,000 --> 00:17:26,000
Pero, neste caso, eu finalmente desde caracteres suficientes

309
00:17:26,000 --> 00:17:29,000
que esencialmente superado meu segmento de memoria, e listo,

310
00:17:29,000 --> 00:17:33,000
o sistema operativo, dixo: "Sentímolo, iso non é fallo de segmento de boa calidade."

311
00:17:33,000 --> 00:17:38,000
>> E imos ver agora o que permanece aquí no meu directorio

312
00:17:38,000 --> 00:17:40,000
entender que eu teño ese arquivo aquí, o núcleo.

313
00:17:40,000 --> 00:17:42,000
Nótese que esta é unha vez máis chamado core dump.

314
00:17:42,000 --> 00:17:46,000
É esencialmente un arquivo que contén o contido da memoria do seu programa

315
00:17:46,000 --> 00:17:48,000
ao momento en que deixou de funcionar,

316
00:17:48,000 --> 00:17:51,000
e só para tratar un pequeno exemplo aquí, deixe-me entrar aquí

317
00:17:51,000 --> 00:17:57,000
e executar o gdb no scanf3 e seleccione un terceiro argumento chamado núcleo,

318
00:17:57,000 --> 00:18:01,000
e notar aquí que eu listar o código,

319
00:18:01,000 --> 00:18:06,000
nós imos ser capaces, como de costume co gdb para comezar a camiñar a través deste programa,

320
00:18:06,000 --> 00:18:10,000
e eu poida executa-lo e así que eu bater-como co comando paso na gdb-

321
00:18:10,000 --> 00:18:13,000
así que alcanzou a liña de buggy potencialmente despois de escribir unha secuencia enorme,

322
00:18:13,000 --> 00:18:16,000
Eu vou ser capaz de realmente identificar-lo aquí.

323
00:18:16,000 --> 00:18:19,000
Máis sobre iso, con todo, na sección en termos de core dumps

324
00:18:19,000 --> 00:18:22,000
e así por diante, así que realmente pode bisbilhotar dentro do core dump

325
00:18:22,000 --> 00:18:27,000
e ver en que liña o programa non ten.

326
00:18:27,000 --> 00:18:32,000
Algunha preguntas, entón en punteiros e enderezos?

327
00:18:32,000 --> 00:18:36,000
Porque hoxe, imos comezar a tomar por certo que esas cousas existen

328
00:18:36,000 --> 00:18:40,000
e sabemos exactamente o que son.

329
00:18:40,000 --> 00:18:42,000
Si

330
00:18:42,000 --> 00:18:46,000
>> [Estudante] Como é que non tes que poñer un comercial ao lado da parte

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

332
00:18:48,000 --> 00:18:51,000
Como é que eu non teño que poñer un comercial ao lado da matriz de caracteres como eu fixen anteriormente

333
00:18:51,000 --> 00:18:53,000
coa maioría dos nosos exemplos?

334
00:18:53,000 --> 00:18:55,000
A resposta curta é matrices son un pouco especial.

335
00:18:55,000 --> 00:18:59,000
Vostede case pode pensar un tapón como realmente un enderezo,

336
00:18:59,000 --> 00:19:03,000
e iso só pasa de ser o caso de que a notación de colchete

337
00:19:03,000 --> 00:19:06,000
é unha conveniencia para que poidamos entrar en soporte 0, franxa 1,

338
00:19:06,000 --> 00:19:10,000
franxa 2, sen ter que utilizar a notación *.

339
00:19:10,000 --> 00:19:13,000
Isto é un pouco de unha mentira porque as matrices e punteiros

340
00:19:13,000 --> 00:19:17,000
son, en realidade, un pouco diferente, pero que moitas veces pode, pero non sempre ser usados ​​indistintamente.

341
00:19:17,000 --> 00:19:21,000
En suma, cando a función está esperando un punteiro para un bloque de memoria,

342
00:19:21,000 --> 00:19:24,000
pode pasar un enderezo que foi retornado por malloc,

343
00:19:24,000 --> 00:19:29,000
e imos ver malloc novo antes de tempo, ou pode pasarlle o nome dunha matriz.

344
00:19:29,000 --> 00:19:32,000
Non ten que facer comercial con matrices porque eles xa están

345
00:19:32,000 --> 00:19:34,000
esencialmente, como enderezos.

346
00:19:34,000 --> 00:19:36,000
Esa é a única excepción.

347
00:19:36,000 --> 00:19:39,000
Os corchetes fan especiais.

348
00:19:39,000 --> 00:19:41,000
>> Vostede podería poñer un comercial á beira do tapón?

349
00:19:41,000 --> 00:19:43,000
Non neste caso.

350
00:19:43,000 --> 00:19:46,000
Iso non vai funcionar porque, de novo, desta esquina caso

351
00:19:46,000 --> 00:19:49,000
onde matrices non son moi realmente enderezos.

352
00:19:49,000 --> 00:19:54,000
Pero imos quizais volva para que en pouco tempo con outros exemplos.

353
00:19:54,000 --> 00:19:56,000
Imos tentar resolver un problema aquí.

354
00:19:56,000 --> 00:20:00,000
Temos unha estrutura de datos que temos benvida a empregar durante algún tempo coñecida como unha matriz.

355
00:20:00,000 --> 00:20:02,000
O caso en cuestión, é o que acabamos de ter.

356
00:20:02,000 --> 00:20:04,000
Pero matrices teñen algún upsides e inconvenientes.

357
00:20:04,000 --> 00:20:06,000
Matrices son agradables porque?

358
00:20:06,000 --> 00:20:11,000
¿Que é unha cousa que lle gusta, na medida en que lle gusta matrices-sobre matrices?

359
00:20:11,000 --> 00:20:13,000
O que é conveniente sobre eles? O que é interesante?

360
00:20:13,000 --> 00:20:18,000
Por que nós presenta-los en primeiro lugar?

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

362
00:20:20,000 --> 00:20:27,000
[Estudante] Poden almacenar unha gran cantidade de datos, e non ten que usar unha cousa toda.

363
00:20:27,000 --> 00:20:29,000
Pode usar unha sección.

364
00:20:29,000 --> 00:20:32,000
Bo, con unha matriz pode almacenar unha gran cantidade de datos,

365
00:20:32,000 --> 00:20:35,000
e non necesariamente ten que usar todo isto, para que poida overallocate,

366
00:20:35,000 --> 00:20:39,000
o que pode ser cómodo se non sabe de antemán cantos de algo que esperar.

367
00:20:39,000 --> 00:20:41,000
>> GetString é un exemplo perfecto.

368
00:20:41,000 --> 00:20:44,000
GetString, escrito por nós, non ten idea de cantos chars que esperar,

369
00:20:44,000 --> 00:20:48,000
de xeito que o feito de que podemos reservar bloques de memoria contigua é bo.

370
00:20:48,000 --> 00:20:51,000
Matrices tamén resolver un problema que vimos hai unhas semanas agora

371
00:20:51,000 --> 00:20:54,000
onde o código empeza a transformarse en algo moi mal deseñado.

372
00:20:54,000 --> 00:20:57,000
Lembre que eu creei unha estrutura estudante chamado David,

373
00:20:57,000 --> 00:21:00,000
e despois que foi realmente unha alternativa, porén,

374
00:21:00,000 --> 00:21:04,000
a ter unha variable chamada nome e outra variable chamada, eu creo, casa,

375
00:21:04,000 --> 00:21:08,000
e outra variable chamada ID, porque nesa historia entón eu quería introducir algo máis

376
00:21:08,000 --> 00:21:11,000
Rob gusta o programa, entón eu decidir esperar un minuto

377
00:21:11,000 --> 00:21:13,000
Eu teño cambiar o nome destas variables.

378
00:21:13,000 --> 00:21:16,000
Imos chamar de meu nome1, ID1, house1.

379
00:21:16,000 --> 00:21:20,000
Imos chamar Rob nome2, house2, ID2.

380
00:21:20,000 --> 00:21:22,000
Pero, entón, agarde un minuto, o que dicir de Tommy?

381
00:21:22,000 --> 00:21:24,000
Entón tivemos tres variables máis.

382
00:21:24,000 --> 00:21:27,000
Nós introducimos a alguén, catro conxuntos de variables.

383
00:21:27,000 --> 00:21:30,000
O mundo comezou a ficar confuso moi rapidamente,

384
00:21:30,000 --> 00:21:33,000
para que introduciu estruturas, eo que é interesante sobre unha estrutura?

385
00:21:33,000 --> 00:21:39,000
O que fai un struct C permiten que fai?

386
00:21:39,000 --> 00:21:42,000
É realmente estraño hoxe.

387
00:21:42,000 --> 00:21:44,000
O que? >> [Resposta do alumno inaudível]

388
00:21:44,000 --> 00:21:47,000
Si, en concreto, typedef permite crear un novo tipo de datos,

389
00:21:47,000 --> 00:21:51,000
e estrutura, a palabra clave struct, permite encapsular

390
00:21:51,000 --> 00:21:54,000
pezas conceptualmente relacionados de datos xunto

391
00:21:54,000 --> 00:21:56,000
e, posteriormente, chamalos de algo así como un estudante.

392
00:21:56,000 --> 00:21:58,000
>> Isto foi bo, porque agora podemos modelar

393
00:21:58,000 --> 00:22:03,000
especie moito máis consistente conceptualmente a noción dun estudante nunha variable

394
00:22:03,000 --> 00:22:07,000
en vez de ter unha forma arbitraria para unha cadea, un a un ID, e así por diante.

395
00:22:07,000 --> 00:22:10,000
Matrices son bos porque nos permiten comezar a limpar o noso código.

396
00:22:10,000 --> 00:22:13,000
Pero o que é unha desvantaxe agora dunha matriz?

397
00:22:13,000 --> 00:22:15,000
O que non pode facer? Si

398
00:22:15,000 --> 00:22:17,000
[Estudante] Ten que saber o quão grande é.

399
00:22:17,000 --> 00:22:19,000
Ten que saber como é grande, por iso é un tipo de dor.

400
00:22:19,000 --> 00:22:21,000
Aqueles de vós con experiencia previa en programación sabe que unha morea de linguas,

401
00:22:21,000 --> 00:22:24,000
como Java, pode pedir un anaco de memoria, especialmente dunha matriz,

402
00:22:24,000 --> 00:22:28,000
quão grande é vostede, cunha lonxitude de, propiedade, por así dicir, e iso é realmente cómodo.

403
00:22:28,000 --> 00:22:32,000
C, non pode sequera chamarse strlen nunha matriz xenérica

404
00:22:32,000 --> 00:22:35,000
porque strlen, como a palabra indica, é só para cordas,

405
00:22:35,000 --> 00:22:39,000
e pode descubrir a lonxitude dunha cadea a causa deste convenio humana

406
00:22:39,000 --> 00:22:43,000
de ter un \ 0, pero un conxunto, máis xenericamente, é só unha peza de memoria.

407
00:22:43,000 --> 00:22:46,000
Se é unha matriz de enteiros, non vai ser un carácter especial

408
00:22:46,000 --> 00:22:48,000
ao final esperando por ti.

409
00:22:48,000 --> 00:22:50,000
Ten que lembrar a lonxitude dunha matriz.

410
00:22:50,000 --> 00:22:54,000
Outro punto negativo dunha matriz elevou a súa cabeza GetString si.

411
00:22:54,000 --> 00:22:59,000
O que é outra desvantaxe dunha matriz?

412
00:22:59,000 --> 00:23:01,000
Señor, só eu e vostede hoxe.

413
00:23:01,000 --> 00:23:04,000
[Resposta do alumno inaudível] >> E o que?

414
00:23:04,000 --> 00:23:06,000
El é declarado na pila.

415
00:23:06,000 --> 00:23:09,000
Ok, declarou na pila. Por que non gusta?

416
00:23:09,000 --> 00:23:13,000
[Estudante], porque é reutilizada.

417
00:23:13,000 --> 00:23:15,000
El está reutilizados.

418
00:23:15,000 --> 00:23:18,000
Ok, se usa unha matriz para reservar memoria

419
00:23:18,000 --> 00:23:21,000
non pode, por exemplo, devolve-lo, porque é na pila.

420
00:23:21,000 --> 00:23:23,000
Ok, iso é unha desvantaxe.

421
00:23:23,000 --> 00:23:25,000
E canto a outro con unha matriz?

422
00:23:25,000 --> 00:23:28,000
Unha vez que afecta-lo, é do tipo parafuso, se precisa de máis espazo

423
00:23:28,000 --> 00:23:30,000
que a matriz ten.

424
00:23:30,000 --> 00:23:34,000
>> Entón, nós introducimos, malloc recall, que nos deu a capacidade de asignar dinamicamente a memoria.

425
00:23:34,000 --> 00:23:37,000
Pero o que se intentou un mundo completamente diferente?

426
00:23:37,000 --> 00:23:40,000
O que se quería resolver algúns destes problemas

427
00:23:40,000 --> 00:23:45,000
por iso, en vez miña pluma-dorme aquí-

428
00:23:45,000 --> 00:23:51,000
o que se quería esencialmente en vez de crear un mundo que xa non é así?

429
00:23:51,000 --> 00:23:56,000
Trata-se dunha matriz, e, por suposto, este tipo de deterioración, xa que alcanzou o fin da matriz,

430
00:23:56,000 --> 00:24:00,000
e agora non ten máis espazo para outro enteiro ou outro personaxe.

431
00:24:00,000 --> 00:24:03,000
E se nós medio que preventivamente dicir ben, por que non imos relaxarse

432
00:24:03,000 --> 00:24:07,000
esta esixencia de que todos eses anacos de memoria ser contiguo volta atrás,

433
00:24:07,000 --> 00:24:10,000
e por que non, cando eu teño un int ou char,

434
00:24:10,000 --> 00:24:12,000
me dea espazo para un deles?

435
00:24:12,000 --> 00:24:14,000
E cando eu ter outro, dá-me un outro espazo,

436
00:24:14,000 --> 00:24:16,000
e cando precisa de outro, dáme un outro espazo.

437
00:24:16,000 --> 00:24:19,000
A vantaxe de que agora é que, se alguén

438
00:24:19,000 --> 00:24:21,000
leva a memoria por aquí, non é gran cousa.

439
00:24:21,000 --> 00:24:25,000
Vou levar este anaco adicional de memoria aquí e despois este.

440
00:24:25,000 --> 00:24:28,000
>> Agora, o único problema aquí é que está case se sente como eu teño

441
00:24:28,000 --> 00:24:30,000
todo un conxunto de variables diferentes.

442
00:24:30,000 --> 00:24:33,000
Iso séntese como cinco diferentes variables potencialmente.

443
00:24:33,000 --> 00:24:36,000
Pero o que se roubar unha idea de cordas

444
00:24:36,000 --> 00:24:41,000
en que, dalgún xeito vincular estas cousas xuntas conceptualmente, e que se eu fixese iso?

445
00:24:41,000 --> 00:24:44,000
Esta é a miña frecha moi mal deseñado.

446
00:24:44,000 --> 00:24:46,000
Pero supoña que cada un destes anacos de memoria

447
00:24:46,000 --> 00:24:52,000
apuntou para o outro, e este cara, que non ten ningún irmán á súa dereita,

448
00:24:52,000 --> 00:24:54,000
non ten ningunha frecha tal.

449
00:24:54,000 --> 00:24:56,000
Este é de feito o que se chama unha lista ligada.

450
00:24:56,000 --> 00:25:00,000
Esta é unha nova estrutura de datos que nos permite reservar un bloque de memoria,

451
00:25:00,000 --> 00:25:03,000
despois outra, despois outra, despois outra, a calquera hora que queremos

452
00:25:03,000 --> 00:25:07,000
durante un programa, e lembre que todos eles son de algunha maneira relacionados

453
00:25:07,000 --> 00:25:11,000
por, literalmente, encadeando os, e nós fixemos iso pictoricamente aquí cunha frecha.

454
00:25:11,000 --> 00:25:15,000
Pero no código, o que sería o mecanismo a través do cal puidese dalgún xeito se conectar,

455
00:25:15,000 --> 00:25:20,000
case como scratch, un anaco de outro anaco?

456
00:25:20,000 --> 00:25:22,000
Nós poderiamos usar un punteiro, non?

457
00:25:22,000 --> 00:25:25,000
Porque realmente a frecha que vai da praza superior esquerda,

458
00:25:25,000 --> 00:25:31,000
este cara aquí a esta, podería conter dentro da praza

459
00:25:31,000 --> 00:25:34,000
non só algúns ints, non só algúns char, pero o que si realmente alocada

460
00:25:34,000 --> 00:25:37,000
un pouco de espazo extra para que agora,

461
00:25:37,000 --> 00:25:41,000
Cada un dos meus anacos de memoria, aínda que iso me vai custar,

462
00:25:41,000 --> 00:25:45,000
agora parece un pouco máis longo no que un dos bloques de memoria

463
00:25:45,000 --> 00:25:47,000
é usado para un número, así como o número 1,

464
00:25:47,000 --> 00:25:50,000
e, a continuación, se este tipo almacena o número 2,

465
00:25:50,000 --> 00:25:52,000
este anaco de outra memoria é usada para unha frecha,

466
00:25:52,000 --> 00:25:54,000
ou máis concretamente, un punteiro.

467
00:25:54,000 --> 00:25:59,000
E supoña que almacenar o número 3 por aquí, mentres eu uso iso para apuntar para este cara,

468
00:25:59,000 --> 00:26:02,000
e agora este cara, imos supor que eu só quero eses tres anacos de memoria.

469
00:26:02,000 --> 00:26:05,000
Vou debuxar unha liña por iso, indicando nulo.

470
00:26:05,000 --> 00:26:07,000
Non hai personaxe adicional.

471
00:26:07,000 --> 00:26:10,000
>> En realidade, esta é a forma na que podemos ir sobre a aplicación de

472
00:26:10,000 --> 00:26:12,000
algo que se chama unha lista ligada.

473
00:26:12,000 --> 00:26:18,000
Unha lista ligada é unha nova estrutura de datos, e é un trampolín para a

474
00:26:18,000 --> 00:26:21,000
moi afeccionado estruturas de datos que comezan a resolver problemas

475
00:26:21,000 --> 00:26:23,000
ao longo das liñas de Facebook tipo de problemas e problemas de tipo Google

476
00:26:23,000 --> 00:26:26,000
onde ten enormes conxuntos de datos, e xa non corta

477
00:26:26,000 --> 00:26:29,000
para almacenar todo de forma contigua e utilizar algo como procura lineal

478
00:26:29,000 --> 00:26:31,000
ou mesmo algo así como investigación binaria.

479
00:26:31,000 --> 00:26:33,000
Queres mesmo mellores tempos de execución.

480
00:26:33,000 --> 00:26:37,000
De feito, un dos obxectivos primordiais imos falar máis tarde esta semana ou a próxima

481
00:26:37,000 --> 00:26:41,000
é un algoritmo cuxo tempo de carreira é constante.

482
00:26:41,000 --> 00:26:44,000
Noutras palabras, ten sempre a mesma cantidade de tempo, non importa

483
00:26:44,000 --> 00:26:47,000
como é grande a entrada, e que sería de feito interesante,

484
00:26:47,000 --> 00:26:49,000
ata máis que algo logarítmica.

485
00:26:49,000 --> 00:26:51,000
¿Que é iso na pantalla aquí?

486
00:26:51,000 --> 00:26:55,000
Cada un dos rectángulos é o que eu deseño a man.

487
00:26:55,000 --> 00:26:59,000
Pero a cousa toda a maneira á esquerda é unha variable especial.

488
00:26:59,000 --> 00:27:02,000
Vai ser un punteiro único porque a única pegadinha

489
00:27:02,000 --> 00:27:04,000
con unha lista ligada, como esas cousas son chamados,

490
00:27:04,000 --> 00:27:09,000
é que ten para coller a unha final da lista de relacionados.

491
00:27:09,000 --> 00:27:13,000
>> Así como cunha corda, ten que saber o enderezo do primeiro carácter.

492
00:27:13,000 --> 00:27:15,000
Mesmo para listas ligadas.

493
00:27:15,000 --> 00:27:19,000
Ten que saber o enderezo do primeiro anaco de memoria

494
00:27:19,000 --> 00:27:25,000
porque de alí, pode chegar a calquera outro.

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

496
00:27:27,000 --> 00:27:30,000
Cal é o prezo que estamos pagando por esa versatilidade de ter un dinámicamente

497
00:27:30,000 --> 00:27:34,000
estrutura de datos de tamaño considerable que se algunha vez precisa de máis memoria, todo ben,

498
00:27:34,000 --> 00:27:37,000
simplemente reservar un anaco e deseñar un punteiro de

499
00:27:37,000 --> 00:27:39,000
da antiga para a nova cola da lista?

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

501
00:27:41,000 --> 00:27:43,000
[Estudante] É preciso espazo de preto de dúas veces máis.

502
00:27:43,000 --> 00:27:45,000
El ocupa un espazo dúas veces maior, de xeito que é sempre unha desvantaxe, e vimos que

503
00:27:45,000 --> 00:27:48,000
cambio antes entre tempo e espazo e flexibilidade

504
00:27:48,000 --> 00:27:51,000
onde por agora, non precisamos de 32 bits para cada un deses números.

505
00:27:51,000 --> 00:27:57,000
Nós realmente necesitamos de 64, 32 o número e 32 para o punteiro.

506
00:27:57,000 --> 00:27:59,000
Pero, ei, eu teño 2 gigabytes de memoria RAM.

507
00:27:59,000 --> 00:28:02,000
Engadindo máis 32 bits aquí e aquí non parece que de un gran negocio.

508
00:28:02,000 --> 00:28:05,000
Pero para grandes conxuntos de datos, en definitiva engade-se, literalmente, o dobre.

509
00:28:05,000 --> 00:28:09,000
O que é outra desvantaxe agora, ou o que é o que imos característica desistir,

510
00:28:09,000 --> 00:28:12,000
representar listas de cousas con unha lista ligada e non unha matriz?

511
00:28:12,000 --> 00:28:14,000
[Estudante] Non pode atravesa-lo cara atrás.

512
00:28:14,000 --> 00:28:16,000
Vostede non pode cruzalo cara atrás, entón é do tipo parafuso, se está camiñando

513
00:28:16,000 --> 00:28:19,000
de esquerda a dereita, cun loop ou un loop while

514
00:28:19,000 --> 00:28:21,000
e entón entender, "Oh, eu quero volver para o inicio da lista."

515
00:28:21,000 --> 00:28:26,000
Vostede non pode porque estes punteiros só ir de esquerda a dereita, como as frechas indican.

516
00:28:26,000 --> 00:28:29,000
>> Agora, vostede podería lembrar o inicio da lista, con outra variable,

517
00:28:29,000 --> 00:28:31,000
pero iso é unha complexidade para manter presente.

518
00:28:31,000 --> 00:28:35,000
Unha matriz, non importa o quão lonxe vai, sempre pode facer menos, menos, menos, menos

519
00:28:35,000 --> 00:28:37,000
e volver de onde veu.

520
00:28:37,000 --> 00:28:40,000
O que é outra desvantaxe aquí? Si

521
00:28:40,000 --> 00:28:43,000
[Pregunta estudante inaudível]

522
00:28:43,000 --> 00:28:47,000
Vostede podería, entón realmente acaba de propoñer unha estrutura de datos chamado de lista doblemente ligada,

523
00:28:47,000 --> 00:28:50,000
e, en realidade, lle gustaría engadir outro punteiro a cada un deses rectángulos

524
00:28:50,000 --> 00:28:53,000
que vai outra dirección, ao contrario do que

525
00:28:53,000 --> 00:28:55,000
é que agora pode atravesar a outro,

526
00:28:55,000 --> 00:28:59,000
a desvantaxe de que agora está a usar tres veces máis memoria que acostumabamos

527
00:28:59,000 --> 00:29:04,000
e tamén aumentar a complexidade en termos de código que ten que escribir para acertar.

528
00:29:04,000 --> 00:29:08,000
Pero todos estes son quizais compensacións razoables, a reversión é máis importante.

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

530
00:29:10,000 --> 00:29:12,000
[Estudante] Tamén non pode ter unha lista 2D vinculado.

531
00:29:12,000 --> 00:29:16,000
Bo, non pode realmente ter unha lista 2D conectados.

532
00:29:16,000 --> 00:29:18,000
Vostede podería. Non é tan fácil como unha matriz.

533
00:29:18,000 --> 00:29:21,000
Como un array, fai soporte aberto, soporte pechada, soporte aberto, pechado soporte,

534
00:29:21,000 --> 00:29:23,000
e terá unha estrutura 2-dimensional.

535
00:29:23,000 --> 00:29:26,000
Vostede podería aplicar unha lista de 2-dimensional conectados

536
00:29:26,000 --> 00:29:29,000
Se engadir, como propuxo un punteiro terceiro cada unha desas cousas,

537
00:29:29,000 --> 00:29:34,000
e pensar en outra lista que vén vostede estilo 3D

538
00:29:34,000 --> 00:29:40,000
da pantalla para todos nós, que é só unha outra corrente de calquera tipo.

539
00:29:40,000 --> 00:29:45,000
Nós poderiamos facelo, pero non é tan sinxelo como escribir soporte aberto, colchete. Si

540
00:29:45,000 --> 00:29:48,000
[Pregunta estudante inaudível]

541
00:29:48,000 --> 00:29:50,000
Bo, entón iso é un retroceso real.

542
00:29:50,000 --> 00:29:54,000
>> Estes algoritmos que temos pined máis, como oh, busca binaria,

543
00:29:54,000 --> 00:29:57,000
pode buscar unha matriz de números na tarxeta

544
00:29:57,000 --> 00:30:01,000
ou un libro de teléfono moito máis rápido utilizar dividir e conquistar

545
00:30:01,000 --> 00:30:05,000
é un algoritmo de procura binaria, pero busca binaria necesarios dous supostos.

546
00:30:05,000 --> 00:30:09,000
Un, que os datos foron clasificados.

547
00:30:09,000 --> 00:30:11,000
Agora, podemos manter este presuntamente clasificados,

548
00:30:11,000 --> 00:30:14,000
quizais por iso non é unha preocupación, pero de busca binaria tamén asumiu

549
00:30:14,000 --> 00:30:18,000
que tivo acceso aleatorio a lista de números,

550
00:30:18,000 --> 00:30:21,000
e unha matriz permite que teña acceso aleatorio, e de acceso aleatorio,

551
00:30:21,000 --> 00:30:24,000
Quero dicir, se está dado unha matriz, canto tempo leva para ti

552
00:30:24,000 --> 00:30:26,000
para chegar ao soporte de 0?

553
00:30:26,000 --> 00:30:29,000
Unha operación, pode usar [0] e está aí.

554
00:30:29,000 --> 00:30:33,000
Cantos pasos que hai que para chegar ao lugar 10?

555
00:30:33,000 --> 00:30:36,000
Un paso, é só ir a [10] e está alí.

556
00:30:36,000 --> 00:30:40,000
Por outra banda, como comeza o número enteiro 10 nunha lista ligada?

557
00:30:40,000 --> 00:30:42,000
Ten que comezar ao principio, porque só está lembrando

558
00:30:42,000 --> 00:30:45,000
o inicio dunha lista ligada, como unha cadea está lembrado

559
00:30:45,000 --> 00:30:48,000
polo enderezo do seu primeiro char, e ao descubrir que int 10

560
00:30:48,000 --> 00:30:53,000
ou que o carácter 10 en unha secuencia, ten que buscar a cousa toda.

561
00:30:53,000 --> 00:30:55,000
>> De novo, non estamos resolvendo todos os nosos problemas.

562
00:30:55,000 --> 00:31:00,000
Estamos introducindo novos, pero realmente depende do que está intentando proxectar a.

563
00:31:00,000 --> 00:31:04,000
En termos de aplicación do presente, podemos pedir unha idea de que a estrutura do alumno.

564
00:31:04,000 --> 00:31:07,000
A sintaxe é moi semellante, só que agora, a idea é un pouco máis abstracto

565
00:31:07,000 --> 00:31:09,000
casa e nome e ID.

566
00:31:09,000 --> 00:31:13,000
Pero propoño que nós poderíamos ter unha estrutura de datos en C

567
00:31:13,000 --> 00:31:17,000
que se chama nodo, como a última palabra sobre o slide suxire,

568
00:31:17,000 --> 00:31:21,000
dentro dun nodo, e un nó é só un contenedor xenérico en ciencia da computación.

569
00:31:21,000 --> 00:31:25,000
Xeralmente é deseñada como un círculo ou un cadrado ou rectángulo, como temos feito.

570
00:31:25,000 --> 00:31:27,000
E nesta estrutura de datos, que ten un int, n,

571
00:31:27,000 --> 00:31:29,000
de xeito que é o número que eu queira gardar.

572
00:31:29,000 --> 00:31:36,000
Pero o que é esa segunda liña, struct node * próximo?

573
00:31:36,000 --> 00:31:40,000
Por que iso é correcto, ou cal o papel que este xogo cousa,

574
00:31:40,000 --> 00:31:42,000
aínda que sexa un pouco enigmática, a primeira vista?

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

576
00:31:44,000 --> 00:31:46,000
[Resposta do alumno inaudível]

577
00:31:46,000 --> 00:31:50,000
Exactamente, por iso o tipo * do espólio que é un punteiro de calquera tipo.

578
00:31:50,000 --> 00:31:53,000
O nome deste punteiro é arbitrariamente seguinte

579
00:31:53,000 --> 00:32:00,000
pero poderiamos chamar calquera cousa que queremos, pero o que fai este punto punteiro para?

580
00:32:00,000 --> 00:32:03,000
[Estudante] Outro nó. >> Exactamente, el apunta a outro nodo tal.

581
00:32:03,000 --> 00:32:05,000
>> Agora, iso é unha especie de curiosidade de C.

582
00:32:05,000 --> 00:32:09,000
Lembre que C é lido por un top compilador para abaixo, de esquerda a dereita,

583
00:32:09,000 --> 00:32:13,000
que significa que se iso é un pouco diferente do que fixemos co alumnado.

584
00:32:13,000 --> 00:32:16,000
Cando definimos un estudante, que se non poñer unha palabra alí.

585
00:32:16,000 --> 00:32:18,000
El só dixo typedef.

586
00:32:18,000 --> 00:32:20,000
Entón tivemos int id nome, corda, corda casa,

587
00:32:20,000 --> 00:32:23,000
e, a continuación, na parte inferior do estudante da estrutura.

588
00:32:23,000 --> 00:32:26,000
Esta declaración é un pouco diferente, porque,

589
00:32:26,000 --> 00:32:28,000
novo, o compilador C é un pouco idiota.

590
00:32:28,000 --> 00:32:30,000
El só vai ler de arriba para abaixo,

591
00:32:30,000 --> 00:32:33,000
así que se atinxe a liña 2 aquí

592
00:32:33,000 --> 00:32:37,000
onde próxima está declarada e ve Oh, aquí está unha variable chamada seguinte.

593
00:32:37,000 --> 00:32:39,000
É un punteiro para un nó de estrutura.

594
00:32:39,000 --> 00:32:42,000
O compilador vai entender o que é un nodo de estrutura?

595
00:32:42,000 --> 00:32:44,000
Eu nunca oín falar desa cousa antes,

596
00:32:44,000 --> 00:32:47,000
porque o nodo palabra non poderían aparecer

597
00:32:47,000 --> 00:32:49,000
ata o fondo, para que haxa esta redundancia.

598
00:32:49,000 --> 00:32:53,000
Ten que dicir no struct aquí, o que pode reducir máis tarde

599
00:32:53,000 --> 00:32:56,000
grazas a typedef aquí, pero iso é porque

600
00:32:56,000 --> 00:33:02,000
estamos referenciando a estrutura en si no interior da estrutura.

601
00:33:02,000 --> 00:33:05,000
Esa é a única pegadinha aí.

602
00:33:05,000 --> 00:33:07,000
>> Algúns problemas interesantes van xurdir.

603
00:33:07,000 --> 00:33:09,000
Temos unha lista de números. Como imos introducir nel?

604
00:33:09,000 --> 00:33:11,000
Como é que imos procura-lo? Como podemos eliminar iso?

605
00:33:11,000 --> 00:33:13,000
Especialmente agora que temos que xestionar todos eses punteiros.

606
00:33:13,000 --> 00:33:15,000
Vostede pensou punteiros eran unha especie de alucinante

607
00:33:15,000 --> 00:33:17,000
cando tiña un deles só tentando ler un int para el.

608
00:33:17,000 --> 00:33:20,000
Agora, temos que manipular o valor dunha lista enteira.

609
00:33:20,000 --> 00:33:22,000
Por que non imos tomar o noso intervalo de 5 minutos aquí, e entón nós imos levar

610
00:33:22,000 --> 00:33:34,000
algunhas persoas ata o escenario para facer exactamente isto.

611
00:33:34,000 --> 00:33:36,000
>> C é moito máis divertido cando é encenado.

612
00:33:36,000 --> 00:33:39,000
Quen ía literalmente quere ser o primeiro?

613
00:33:39,000 --> 00:33:41,000
Ok, imos alí cara arriba. Vostede está en primeiro lugar.

614
00:33:41,000 --> 00:33:44,000
Quen quere ser o 9? Ok, 9.

615
00:33:44,000 --> 00:33:46,000
Como preto de 9? 17?

616
00:33:46,000 --> 00:33:51,000
A panelinha aquí. 22 e 26 en que a liña da fronte.

617
00:33:51,000 --> 00:33:53,000
E entón, que tal alguén alí sendo apuntada.

618
00:33:53,000 --> 00:33:57,000
Está 34. Ok, de 34 anos, vén para arriba.

619
00:33:57,000 --> 00:33:59,000
Primeiro está alí. Ok, todos os catro de vós.

620
00:33:59,000 --> 00:34:01,000
E quen foi que dixo para 9?

621
00:34:01,000 --> 00:34:04,000
Quen é o noso 9?

622
00:34:04,000 --> 00:34:07,000
Quen realmente quere ser 9? Todo ben, imos alí, ser 9.

623
00:34:07,000 --> 00:34:10,000
Aquí imos nós.

624
00:34:10,000 --> 00:34:13,000
34, nós imos atopalo por alí.

625
00:34:13,000 --> 00:34:17,000
A primeira parte é facervos ollar como aquel.

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

627
00:34:21,000 --> 00:34:25,000
Se pode estar ao lado, porque estamos indo a malloc vostede nun momento.

628
00:34:25,000 --> 00:34:29,000
>> Bo, moi bo.

629
00:34:29,000 --> 00:34:32,000
Ok, excelente, así que imos pedir un par de preguntas aquí.

630
00:34:32,000 --> 00:34:34,000
E, en realidade, cal é o seu nome? >> Anita.

631
00:34:34,000 --> 00:34:37,000
Anita, todo ben, veña ata aquí.

632
00:34:37,000 --> 00:34:41,000
Anita vai axudar a resolver un tipo de pregunta moi simple, en primeiro lugar,

633
00:34:41,000 --> 00:34:44,000
que é como atopar ou non un valor está na lista?

634
00:34:44,000 --> 00:34:48,000
Agora, observe que o primeiro, representado aquí por Lucas,

635
00:34:48,000 --> 00:34:52,000
é un pouco diferente, e por iso o seu anaco de papel é deliberadamente de lado

636
00:34:52,000 --> 00:34:55,000
porque non é tan alto e non toma-se como moitos bits,

637
00:34:55,000 --> 00:34:58,000
Aínda que tecnicamente ten o mesmo tamaño de papel só rodado.

638
00:34:58,000 --> 00:35:01,000
Pero é un pouco diferente, xa que el ten só 32 bits para un punteiro,

639
00:35:01,000 --> 00:35:05,000
e todos eses caras son de 64 bits, a metade dos cales é o número, a metade dos cales é un punteiro.

640
00:35:05,000 --> 00:35:08,000
Pero o punteiro non é retratado, por iso, se vostedes puidesen un pouco sen xeito

641
00:35:08,000 --> 00:35:12,000
Use a man esquerda para apuntar para a persoa ao seu lado.

642
00:35:12,000 --> 00:35:14,000
E é o número 34. Cal é o seu nome?

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

644
00:35:16,000 --> 00:35:19,000
Ari, polo tanto, en realidade, manter o papel na súa man dereita, ea man esquerda vai directo para abaixo.

645
00:35:19,000 --> 00:35:21,000
Vostede declara nulo á esquerda.

646
00:35:21,000 --> 00:35:24,000
>> Agora o noso retrato humano é moi consistente.

647
00:35:24,000 --> 00:35:26,000
Isto é, en realidade, como os punteiros traballar.

648
00:35:26,000 --> 00:35:29,000
E se pode amasar un pouco desa forma que eu non estou no seu camiño.

649
00:35:29,000 --> 00:35:34,000
Anita aquí, atopar-me o número 22,

650
00:35:34,000 --> 00:35:40,000
pero asumir unha restricción de non seres humanos seguro anacos de papel,

651
00:35:40,000 --> 00:35:43,000
pero esta é unha lista, e só ten Lucas para comezar

652
00:35:43,000 --> 00:35:46,000
porque é, literalmente, o primeiro punteiro.

653
00:35:46,000 --> 00:35:51,000
Supoña que vostede mesmo é un punteiro, e que tamén ten a capacidade de apuntar algo.

654
00:35:51,000 --> 00:35:56,000
Por que non comezar por apuntar exactamente o que Lucas está a apuntar?

655
00:35:56,000 --> 00:35:58,000
Bo, deixe-me e aprobar isto aquí.

656
00:35:58,000 --> 00:36:04,000
Só por unha cuestión de debate, deixe-me tirar para arriba unha páxina en branco aquí.

657
00:36:04,000 --> 00:36:06,000
Como se escribe o seu nome? >> Anita.

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

659
00:36:08,000 --> 00:36:18,000
Digamos nodo * Anita = Lucas.

660
00:36:18,000 --> 00:36:22,000
Ben, non debemos chamalo de Lucas. Debemos chamalo primeiro.

661
00:36:22,000 --> 00:36:25,000
Por que iso é de feito consistente coa realidade aquí?

662
00:36:25,000 --> 00:36:27,000
Un primeiro xa existe.

663
00:36:27,000 --> 00:36:30,000
Primeiro foi asignado nalgún lugar, presumiblemente, aquí enriba.

664
00:36:30,000 --> 00:36:35,000
* Primeiro no, e que foi asignada unha lista de algunha maneira.

665
00:36:35,000 --> 00:36:37,000
Eu non sei como isto aconteceu. Iso aconteceu antes da clase comezar.

666
00:36:37,000 --> 00:36:40,000
Esta lista ligada de seres humanos foi creado.

667
00:36:40,000 --> 00:36:44,000
E agora, neste momento da historia, todo iso é ir en Facebook, aparentemente, máis tarde,

668
00:36:44,000 --> 00:36:49,000
neste punto da historia, Anita foi inicializada para ser igual ao primeiro,

669
00:36:49,000 --> 00:36:51,000
o que non significa que os puntos de Anita en Lucas.

670
00:36:51,000 --> 00:36:53,000
En vez diso, ela apunta para o que apunta a

671
00:36:53,000 --> 00:36:57,000
pois o mesmo enderezo que está dentro de 32 bits - Lucas 1, 2, 3 -

672
00:36:57,000 --> 00:37:01,000
agora tamén dentro de 32 Anita bits - 1, 2, 3.

673
00:37:01,000 --> 00:37:05,000
>> Agora, atopar 22. Como vai facer sobre iso?

674
00:37:05,000 --> 00:37:07,000
O que é que o punto? >> Para o que sexa.

675
00:37:07,000 --> 00:37:11,000
Apunte para o que quere, entón vai adiante e actuar para fóra o mellor que poida aquí.

676
00:37:11,000 --> 00:37:15,000
Bo, bo, e agora está a apuntar o que é o seu nome, con 22?

677
00:37:15,000 --> 00:37:18,000
Ramón. >> Ramon, entón Ramón está seguro 22.

678
00:37:18,000 --> 00:37:20,000
Xa fixo un cheque.

679
00:37:20,000 --> 00:37:24,000
O Ramón == 22, e se é así, por exemplo, podemos volver verdade.

680
00:37:24,000 --> 00:37:26,000
Deixe-me, mentres estes faces estar aquí un pouco sen xeito,

681
00:37:26,000 --> 00:37:32,000
deixe-me facer algo axiña, como bool atopar.

682
00:37:32,000 --> 00:37:37,000
Eu estou indo a ir adiante e dicir (lista * nodo, int n).

683
00:37:37,000 --> 00:37:39,000
Eu estarei de volta con vós. Eu só teño que escribir un código.

684
00:37:39,000 --> 00:37:45,000
E agora eu estou indo a ir adiante e facelo, o * Anita = lista.

685
00:37:45,000 --> 00:37:51,000
E eu estou indo a ir adiante e dicir ao mesmo tempo (Anita! = NULL).

686
00:37:51,000 --> 00:37:57,000
>> A metáfora aquí está quedando un pouco estirado, pero mentres (Anita! = NULL), o que quero facer?

687
00:37:57,000 --> 00:38:03,000
Eu teño algunha forma de referenciar

688
00:38:03,000 --> 00:38:05,000
o enteiro que Anita está a apuntar.

689
00:38:05,000 --> 00:38:08,000
No pasado, cando se estruturas, o que é un nodo,

690
00:38:08,000 --> 00:38:11,000
usamos a notación de punto, e queremos dicir algo así como

691
00:38:11,000 --> 00:38:15,000
anita.n, pero o problema aquí é que Anita non é unha estrutura en si.

692
00:38:15,000 --> 00:38:17,000
O que é?

693
00:38:17,000 --> 00:38:21,000
Ela é un punteiro, por iso mesmo, se quere usar esta notación de punto

694
00:38:21,000 --> 00:38:23,000
e este vai mirar deliberadamente un pouco enigmática-

695
00:38:23,000 --> 00:38:28,000
temos que facer algo, como ir a man esquerda o que Anita está a apuntar cara

696
00:38:28,000 --> 00:38:31,000
e en seguida, obter o campo chamado n.

697
00:38:31,000 --> 00:38:35,000
Anita é un punteiro, pero o que é * Anita?

698
00:38:35,000 --> 00:38:38,000
¿Que pensas cando vai para o que Anita está a apuntar?

699
00:38:38,000 --> 00:38:42,000
A estrutura, un nó e un nó de recordo, ten un campo chamado n

700
00:38:42,000 --> 00:38:47,000
porque, lembre, estes dous campos, próximos e n,

701
00:38:47,000 --> 00:38:50,000
que vimos hai pouco aquí.

702
00:38:50,000 --> 00:38:53,000
>> Para realmente imitar iso no código,

703
00:38:53,000 --> 00:39:02,000
poderiamos facer, e dicir se ((* Anita). n == n), o n que eu estou buscando.

704
00:39:02,000 --> 00:39:04,000
Teña en conta que a función foi aprobada no número que me interesa.

705
00:39:04,000 --> 00:39:10,000
Entón eu podo ir adiante e facer algo como certo retorno.

706
00:39:10,000 --> 00:39:12,000
Outra cousa, se este non é o caso, o que quero facer?

707
00:39:12,000 --> 00:39:19,000
Como traduzo para codificar o que Anita fixo intuitivamente andando a través da lista?

708
00:39:19,000 --> 00:39:26,000
¿Que debo facer aquí para simular Anita dar ese paso cara á esquerda, que paso a esquerda?

709
00:39:26,000 --> 00:39:28,000
[Resposta do alumno inaudível] >> ¿Que é iso?

710
00:39:28,000 --> 00:39:30,000
[Resposta do alumno inaudível]

711
00:39:30,000 --> 00:39:34,000
Bo, non é unha idea malo, pero no pasado, cando fixemos iso, fixemos Anita + +

712
00:39:34,000 --> 00:39:37,000
porque que quere engadir o número 1 para Anita,

713
00:39:37,000 --> 00:39:40,000
que normalmente apuntar á seguinte persoa, como Ramón,

714
00:39:40,000 --> 00:39:44,000
ou a persoa próxima a el, ou a persoa próxima a el para abaixo da liña.

715
00:39:44,000 --> 00:39:49,000
Pero iso non é moi bo aquí, porque o que esa cousa parece na memoria?

716
00:39:49,000 --> 00:39:54,000
Non é iso. Temos que desactivar iso.

717
00:39:54,000 --> 00:40:00,000
Parece que este na memoria, e aínda que eu teña deseñado 1 e 2 e 3 preto un do outro,

718
00:40:00,000 --> 00:40:03,000
realmente simular este-Vostedes poden, aínda apuntando para as mesmas persoas,

719
00:40:03,000 --> 00:40:07,000
algúns de vostedes poden dar un paso atrás aleatoria, algúns de vostedes un paso ao chou para adiante?

720
00:40:07,000 --> 00:40:10,000
>> Esta confusión é aínda unha lista ligada,

721
00:40:10,000 --> 00:40:13,000
pero estes faces poderían estar en calquera lugar na memoria,

722
00:40:13,000 --> 00:40:15,000
así Anita + + non vai funcionar por que?

723
00:40:15,000 --> 00:40:19,000
O que está en lugar Anita + +?

724
00:40:19,000 --> 00:40:21,000
Quen sabe.

725
00:40:21,000 --> 00:40:24,000
E algún outro valor que só pasa a ser interposta

726
00:40:24,000 --> 00:40:28,000
entre todos eses nós por casualidade, porque non estamos usando unha matriz.

727
00:40:28,000 --> 00:40:30,000
Nós asignado a cada un destes nós individualmente.

728
00:40:30,000 --> 00:40:32,000
Ok, se vostedes poden limpar-se de volta.

729
00:40:32,000 --> 00:40:37,000
Deixe-me propor que, en vez de Anita + +, que en vez facer Anita queda-

730
00:40:37,000 --> 00:40:42,000
así, por que non imos para o que quere que Anita está a apuntar e despois facer. próximo?

731
00:40:42,000 --> 00:40:45,000
Noutras palabras, imos para Ramón, que está sostendo o número 22,

732
00:40:45,000 --> 00:40:51,000
e despois. seguinte é como se Anita sería copiar o punteiro man esquerda.

733
00:40:51,000 --> 00:40:54,000
Pero ela non quixo ir máis lonxe do que Ramón porque atopamos 22.

734
00:40:54,000 --> 00:40:56,000
Pero iso sería a idea. Agora, iso é unha desorde horrible.

735
00:40:56,000 --> 00:40:59,000
Honesta, ninguén vai lembrar esta sintaxe, e así, por sorte,

736
00:40:59,000 --> 00:41:04,000
en realidade é un pouco deliberada-oh, non realmente ver o que eu escribín.

737
00:41:04,000 --> 00:41:08,000
Isto sería máis convincente se puidese. Listo!

738
00:41:08,000 --> 00:41:10,000
>> Detrás das escenas, eu estaba resolvendo o problema desa forma.

739
00:41:10,000 --> 00:41:14,000
Anita, para dar ese paso cara á esquerda,

740
00:41:14,000 --> 00:41:18,000
en primeiro lugar, nós ir ao enderezo que Anita está a apuntar cara

741
00:41:18,000 --> 00:41:23,000
e onde vai atopar non só n, que verifiquei só para efectos de comparación,

742
00:41:23,000 --> 00:41:25,000
pero tamén vai atopar preto - neste caso,

743
00:41:25,000 --> 00:41:28,000
Man esquerda Ramón, apuntando para o próximo nó na lista.

744
00:41:28,000 --> 00:41:32,000
Pero esta é a desorde horrible a que me refire anteriormente,

745
00:41:32,000 --> 00:41:34,000
pero acontece C nos permite simplificar isto.

746
00:41:34,000 --> 00:41:40,000
En vez de escribir (* Anita), podemos no canto de só escribir Anita-> n,

747
00:41:40,000 --> 00:41:45,000
e é exactamente a mesma cousa funcionalmente, pero é moito máis intuitivo,

748
00:41:45,000 --> 00:41:48,000
e é moito máis consistente coa imaxe que temos está a deseñar

749
00:41:48,000 --> 00:41:50,000
todo ese tempo usando as frechas.

750
00:41:50,000 --> 00:41:57,000
>> Por fin, o que necesitamos facer ao final deste programa?

751
00:41:57,000 --> 00:42:00,000
Hai unha liña de código restante.

752
00:42:00,000 --> 00:42:02,000
Devolver o que?

753
00:42:02,000 --> 00:42:05,000
Falso, porque se pasar todo o loop while

754
00:42:05,000 --> 00:42:10,000
e Anita é, de feito, nulo, isto significa que percorreu todo o camiño para o fin da lista

755
00:42:10,000 --> 00:42:12,000
onde ela estaba apuntando-o que é o seu nome?

756
00:42:12,000 --> 00:42:15,000
Ari man esquerda. >> Ari, que é nulo.

757
00:42:15,000 --> 00:42:18,000
Anita agora é nulo, e eu entender que está de pé aquí sen xeito no limbo

758
00:42:18,000 --> 00:42:21,000
porque eu estou saíndo nun monólogo aquí,

759
00:42:21,000 --> 00:42:23,000
pero imos facela-lo novo en só un momento.

760
00:42:23,000 --> 00:42:27,000
Anita é nulo nese punto da historia, de xeito que o loop while remata,

761
00:42:27,000 --> 00:42:30,000
e nós temos que voltar falso, porque se ela ten todo o camiño para punteiro nulo de Ari

762
00:42:30,000 --> 00:42:34,000
entón non había número que buscou na lista.

763
00:42:34,000 --> 00:42:39,000
Podemos borrar iso tamén, pero esa é unha implementación moi boa, entón

764
00:42:39,000 --> 00:42:43,000
dunha función de paso, unha función para atopar unha lista ligada.

765
00:42:43,000 --> 00:42:48,000
É aínda busca lineal, pero non é tan sinxelo como un punteiro + +

766
00:42:48,000 --> 00:42:52,000
ou + + dunha variable i porque agora non podemos adiviñar

767
00:42:52,000 --> 00:42:54,000
en que cada un destes nós se atopan na memoria.

768
00:42:54,000 --> 00:42:57,000
Temos que, literalmente, seguir a pista de migas de pan ou, máis especificamente,

769
00:42:57,000 --> 00:43:00,000
punteiros, para comezar a partir dun nodo a outro.

770
00:43:00,000 --> 00:43:02,000
>> Agora imos tratar de outro. Anita, quere volver para aquí?

771
00:43:02,000 --> 00:43:06,000
Por que non imos adiante e reservar outra persoa do público?

772
00:43:06,000 --> 00:43:08,000
Malloc cal é o seu nome? >> Rebecca.

773
00:43:08,000 --> 00:43:10,000
Rebecca. Rebecca foi malloced do público,

774
00:43:10,000 --> 00:43:13,000
e ela é agora almacenar o número 55.

775
00:43:13,000 --> 00:43:17,000
E o obxectivo en mans agora é a Anita para introducir

776
00:43:17,000 --> 00:43:22,000
Rebecca na lista ligada aquí no seu lugar apropiado.

777
00:43:22,000 --> 00:43:24,000
Veña aquí por un momento.

778
00:43:24,000 --> 00:43:28,000
Eu teño feito algo así.

779
00:43:28,000 --> 00:43:32,000
Eu fixen * nodo. E cal é o seu nome?

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

781
00:43:34,000 --> 00:43:41,000
Rebecca queda malloc (sizeof (nó)).

782
00:43:41,000 --> 00:43:44,000
Así coma nós alocamos cousas como estudantes e outros enfeites no pasado,

783
00:43:44,000 --> 00:43:46,000
Temos o tamaño do nó, para agora Rebecca

784
00:43:46,000 --> 00:43:49,000
está a apuntar cara o que?

785
00:43:49,000 --> 00:43:52,000
Rebecca ten dous campos dentro dela, un dos cales é 55.

786
00:43:52,000 --> 00:43:55,000
Imos facer o que Rebecca-> = 55.

787
00:43:55,000 --> 00:44:00,000
Pero, entón, Rebecca-> seguinte debe ser-como agora, a man del é unha especie de, quen sabe?

788
00:44:00,000 --> 00:44:03,000
Está apuntando para un valor de lixo, entón por que non facer para unha boa medida

789
00:44:03,000 --> 00:44:07,000
que polo menos facelo para que a man esquerda está agora ao seu lado.

790
00:44:07,000 --> 00:44:09,000
Agora Anita, leva-lo a partir de aquí.

791
00:44:09,000 --> 00:44:11,000
Tes Rebecca sendo atribuídos.

792
00:44:11,000 --> 00:44:20,000
Dalle descubrir onde hai que poñer Rebecca.

793
00:44:20,000 --> 00:44:25,000
Bo, moi bo.

794
00:44:25,000 --> 00:44:28,000
Ok, bo, e agora necesitamos de ti para proporcionar un pouco de dirección,

795
00:44:28,000 --> 00:44:30,000
de xeito que alcanzou Ari.

796
00:44:30,000 --> 00:44:33,000
Súa man esquerda é nulo, pero Rebecca pertence claramente á dereita,

797
00:44:33,000 --> 00:44:36,000
Entón como é que nós temos que cambiar este ligada

798
00:44:36,000 --> 00:44:38,000
a fin de introducir Rebecca no lugar axeitado?

799
00:44:38,000 --> 00:44:42,000
Se pode, literalmente, mover as mans das persoas de esquerda en torno a como necesario,

800
00:44:42,000 --> 00:44:48,000
nós imos resolver o problema desa forma.

801
00:44:48,000 --> 00:44:52,000
Ok, bo, e, con todo, a man esquerda de Rebecca xa está ao seu lado.

802
00:44:52,000 --> 00:44:54,000
>> Iso foi moi fácil.

803
00:44:54,000 --> 00:44:57,000
Imos tentar reservar-estamos case listo, 20.

804
00:44:57,000 --> 00:44:59,000
Ok, imos alí cara arriba.

805
00:44:59,000 --> 00:45:04,000
20 foi asignado, entón deixe-me ir adiante e dicir de novo aquí

806
00:45:04,000 --> 00:45:07,000
Nós acabamos de facer Saad * nodo.

807
00:45:07,000 --> 00:45:11,000
Temos malloc (sizeof (nó)).

808
00:45:11,000 --> 00:45:16,000
A continuación, facer a mesma sintaxe exacta como fixemos antes do 20,

809
00:45:16,000 --> 00:45:20,000
e eu vou facer = NULL seguinte, e agora cómpre a Anita

810
00:45:20,000 --> 00:45:23,000
introduza na lista ligada, se podería desempeñar ese papel exacto.

811
00:45:23,000 --> 00:45:30,000
Executar.

812
00:45:30,000 --> 00:45:32,000
Ok, bo.

813
00:45:32,000 --> 00:45:38,000
Agora pense con coidado antes de lle comezar a mover a man esquerda ao redor.

814
00:45:38,000 --> 00:45:46,000
Ten, de lonxe, o papel máis difícil hoxe.

815
00:45:46,000 --> 00:45:59,000
Cuxa man debe ser movido en primeiro lugar?

816
00:45:59,000 --> 00:46:02,000
Ok, agarde, eu estou escoitando algunhas n º.

817
00:46:02,000 --> 00:46:07,000
Algunhas persoas educadores quere axudar a resolver unha situación embarazosa aquí.

818
00:46:07,000 --> 00:46:11,000
Cuxa man esquerda debe ser actualizado primeiro, quizais? Si

819
00:46:11,000 --> 00:46:13,000
[Estudante] Saad.

820
00:46:13,000 --> 00:46:15,000
Ok, Saad, por que, entón?

821
00:46:15,000 --> 00:46:17,000
[Resposta do alumno inaudível]

822
00:46:17,000 --> 00:46:19,000
Bo, porque se mover cal é o seu nome? >> Marshall.

823
00:46:19,000 --> 00:46:22,000
Marshall, mover a súa man primeiro para abaixo a nulo,

824
00:46:22,000 --> 00:46:25,000
agora temos literalmente orfos catro persoas na lista

825
00:46:25,000 --> 00:46:29,000
porque era a única cousa a apuntar cara Ramon e todos á esquerda,

826
00:46:29,000 --> 00:46:31,000
de xeito que a actualización primeiro punteiro era malo.

827
00:46:31,000 --> 00:46:33,000
Imos desfacer isto.

828
00:46:33,000 --> 00:46:37,000
Bo, e agora vai adiante e pasar a man apropiado esquerda apuntando para Ramón.

829
00:46:37,000 --> 00:46:39,000
Iso séntese un pouco redundante.

830
00:46:39,000 --> 00:46:41,000
Agora hai dúas persoas apuntando para Ramon, pero iso é bo

831
00:46:41,000 --> 00:46:43,000
porque agora que doutra forma é que imos actualizar a lista?

832
00:46:43,000 --> 00:46:48,000
O que por outra banda ten que se mover?

833
00:46:48,000 --> 00:46:53,000
Excelente, agora temos perdido a memoria?

834
00:46:53,000 --> 00:46:57,000
Non, todo ben, imos ver se non podemos romper esta unha vez máis.

835
00:46:57,000 --> 00:47:00,000
>> Mallocing unha última vez, o número 5.

836
00:47:00,000 --> 00:47:04,000
En todo o camiño de volta, veña para abaixo.

837
00:47:04,000 --> 00:47:08,000
É moi emocionante.

838
00:47:08,000 --> 00:47:15,000
[Aplausos]

839
00:47:15,000 --> 00:47:17,000
Cal é o seu nome? >> Ron.

840
00:47:17,000 --> 00:47:19,000
Ron, ok, está malloced como número 5.

841
00:47:19,000 --> 00:47:23,000
Acaba de executado o código que é case idéntico a estes

842
00:47:23,000 --> 00:47:26,000
con só un nome diferente.

843
00:47:26,000 --> 00:47:28,000
Excelente.

844
00:47:28,000 --> 00:47:38,000
Agora, Anita, boa sorte introducir o número 5 na lista agora.

845
00:47:38,000 --> 00:47:43,000
Bo, e?

846
00:47:43,000 --> 00:47:47,000
Excelente, así que este é realmente o terceiro de tres casos en total.

847
00:47:47,000 --> 00:47:49,000
Primeiro tivemos alguén ao final, Rebecca.

848
00:47:49,000 --> 00:47:51,000
Entón, tivo alguén no medio.

849
00:47:51,000 --> 00:47:53,000
Agora temos a alguén no inicio, e, neste exemplo,

850
00:47:53,000 --> 00:47:56,000
agora tivo que actualizar Lucas por primeira vez

851
00:47:56,000 --> 00:48:00,000
porque o primeiro elemento na lista agora ten que apuntar cara a un novo nodo,

852
00:48:00,000 --> 00:48:03,000
que, á súa vez, está a apuntar o número de nodo 9.

853
00:48:03,000 --> 00:48:06,000
>> Esta foi unha demostración moi raro, eu estou seguro,

854
00:48:06,000 --> 00:48:08,000
así un gran aplauso para estes faces se puidese.

855
00:48:08,000 --> 00:48:11,000
Ben feito.

856
00:48:11,000 --> 00:48:17,000
Isto é todo. Pode manter os seus anacos de papel como un pouco de memoria.

857
00:48:17,000 --> 00:48:22,000
Acontece que facelo no código

858
00:48:22,000 --> 00:48:26,000
non é tan sinxelo coma mover as mans en torno a

859
00:48:26,000 --> 00:48:28,000
e apuntando punteiros en cousas distintas.

860
00:48:28,000 --> 00:48:31,000
Pero entender que cando chega a hora de implementar algo

861
00:48:31,000 --> 00:48:34,000
unha lista ligada ou unha variante do que se concentrarse en realidade

862
00:48:34,000 --> 00:48:38,000
estes fundamentos básicos, os problemas de mordida de tamaño que eu teño que descubrir,

863
00:48:38,000 --> 00:48:43,000
é esta man ou este lado, entender que o que é outra forma de un programa bastante complexo

864
00:48:43,000 --> 00:48:47,000
pode, de feito, ser reducida a bloques de construción moi sinxelo coma este.

865
00:48:47,000 --> 00:48:51,000
>> Imos levar as cousas para unha dirección máis sofisticado aínda.

866
00:48:51,000 --> 00:48:53,000
Temos agora a noción de lista ligada.

867
00:48:53,000 --> 00:48:57,000
Temos tamén, grazas á suxestión alí atrás-unha lista dobremente ligada,

868
00:48:57,000 --> 00:49:01,000
que parece ser case a mesma, pero agora temos dous punteiros dentro da estrutura

869
00:49:01,000 --> 00:49:05,000
en vez de unha, e probablemente poderiamos chamar os punteiros anterior e seguinte

870
00:49:05,000 --> 00:49:08,000
ou á esquerda ou á dereita, pero, de feito, ten que dous deles.

871
00:49:08,000 --> 00:49:10,000
O código sería un pouco máis complicado.

872
00:49:10,000 --> 00:49:12,000
Anita tería que facer máis traballo aquí no escenario.

873
00:49:12,000 --> 00:49:15,000
Pero seguramente poderiamos aplicar este tipo de estrutura.

874
00:49:15,000 --> 00:49:19,000
En termos de tempo de funcionamento, con todo, o que sería o tempo de execución

875
00:49:19,000 --> 00:49:24,000
por Anita de atopar un n número nunha lista ligada agora?

876
00:49:24,000 --> 00:49:27,000
O aínda grande de n, non é mellor que a procura lineal.

877
00:49:27,000 --> 00:49:29,000
Non podemos facer busca binaria, aínda que, unha vez máis.

878
00:49:29,000 --> 00:49:34,000
Por que isto ocorre? Vostede non pode saltar.

879
00:49:34,000 --> 00:49:36,000
Aínda que ver, obviamente, todos os seres humanos no escenario,

880
00:49:36,000 --> 00:49:39,000
e Anita podería eyeballed e dixo: "Aquí está a medio da lista",

881
00:49:39,000 --> 00:49:42,000
non sabería que, se fose un programa de ordenador

882
00:49:42,000 --> 00:49:47,000
porque o único que tiña que coller-se no inicio do escenario

883
00:49:47,000 --> 00:49:50,000
era Lucas, que foi o primeiro punteiro.

884
00:49:50,000 --> 00:49:53,000
Ela necesariamente que seguir estes enlaces,

885
00:49:53,000 --> 00:49:56,000
contando o seu camiño ata que atopou preto de medio,

886
00:49:56,000 --> 00:49:58,000
e aínda así, ela non vai saber cando alcanzou o medio

887
00:49:58,000 --> 00:50:01,000
a menos que vai todo o camiño ata o final para descubrir cantos son,

888
00:50:01,000 --> 00:50:05,000
despois volve atrás, e que tamén sería difícil, a menos que tivo

889
00:50:05,000 --> 00:50:07,000
unha lista dobremente ligada dalgún tipo.

890
00:50:07,000 --> 00:50:10,000
>> Resolución dalgúns problemas hoxe, pero a introdución de outros.

891
00:50:10,000 --> 00:50:12,000
E sobre unha estrutura de datos completamente diferente?

892
00:50:12,000 --> 00:50:15,000
Esta é unha foto das bandexas en Mather House,

893
00:50:15,000 --> 00:50:19,000
e, neste caso, temos unha estrutura de datos que temos tamén unha especie de posto falando.

894
00:50:19,000 --> 00:50:22,000
Nós conversas sobre unha pila no contexto da memoria,

895
00:50:22,000 --> 00:50:26,000
e que é unha especie de deliberadamente chamado porque unha morea de conformidade de memoria

896
00:50:26,000 --> 00:50:31,000
é efectivamente unha estrutura de datos que ten máis e máis cousas en capas enriba del.

897
00:50:31,000 --> 00:50:35,000
Pero o máis interesante sobre unha pila, como é o caso na realidade,

898
00:50:35,000 --> 00:50:38,000
é que é un tipo especial de estrutura de datos.

899
00:50:38,000 --> 00:50:42,000
É unha estrutura de datos en que o primeiro elemento

900
00:50:42,000 --> 00:50:46,000
é o último elemento para fóra.

901
00:50:46,000 --> 00:50:50,000
Se é a primeira bandexa para ser colocadas na pila,

902
00:50:50,000 --> 00:50:53,000
vai ser, lamentablemente, a bandexa último a ser eliminado da pila,

903
00:50:53,000 --> 00:50:55,000
e iso non é necesariamente unha cousa boa.

904
00:50:55,000 --> 00:50:58,000
Por outra banda, pode pensar sobre el o camiño inverso,

905
00:50:58,000 --> 00:51:02,000
o último é o primeiro en saír.

906
00:51:02,000 --> 00:51:05,000
>> Agora, os escenarios veñen á mente que ter unha pila

907
00:51:05,000 --> 00:51:08,000
estrutura de datos, onde ten que a propiedade

908
00:51:08,000 --> 00:51:13,000
do último, en primeiro lugar, é realmente atractivo?

909
00:51:13,000 --> 00:51:16,000
Iso é unha cousa boa? É que unha cousa ruín?

910
00:51:16,000 --> 00:51:19,000
É en definitiva, unha cousa ruín as bandexas non eran todos iguais

911
00:51:19,000 --> 00:51:21,000
e todos eles eran diferentes cores especiais ou outros enfeites,

912
00:51:21,000 --> 00:51:24,000
ea cor que quere é todo o camiño na parte inferior.

913
00:51:24,000 --> 00:51:26,000
Por suposto, non se pode lograr que sen gran esforzo.

914
00:51:26,000 --> 00:51:28,000
Ten que comezar dende o principio e traballar súa maneira para abaixo.

915
00:51:28,000 --> 00:51:31,000
Do mesmo xeito, se fose un deses nenos de fans

916
00:51:31,000 --> 00:51:34,000
que espera toda a noite intentando conseguir un iPhone e aliñar

917
00:51:34,000 --> 00:51:36,000
nun lugar coma este?

918
00:51:36,000 --> 00:51:40,000
Non sería bo se a tenda de Apple

919
00:51:40,000 --> 00:51:42,000
foron unha estrutura de datos de pila?

920
00:51:42,000 --> 00:51:44,000
Yay? Non?

921
00:51:44,000 --> 00:51:47,000
Só é bo para as persoas que aparecen no último minuto posible

922
00:51:47,000 --> 00:51:50,000
e despois arranquei a cola.

923
00:51:50,000 --> 00:51:52,000
E, en realidade, o feito de que eu estaba tan inclinado a dicir cola

924
00:51:52,000 --> 00:51:56,000
é realmente consistente co que chamariamos este tipo de estrutura de datos,

925
00:51:56,000 --> 00:51:59,000
un na realidade onde a orde non importa,

926
00:51:59,000 --> 00:52:02,000
e quere que o primeiro en ser o primeiro en saír

927
00:52:02,000 --> 00:52:04,000
aínda que só por unha cuestión de equidade humana.

928
00:52:04,000 --> 00:52:07,000
Imos chamar xeral de que unha estrutura de datos cola.

929
00:52:07,000 --> 00:52:11,000
>> Acontece que ademais de listas ligadas, podemos comezar a usar esas mesmas ideas básicas

930
00:52:11,000 --> 00:52:15,000
e comezar a crear novos tipos e diferentes solucións aos problemas.

931
00:52:15,000 --> 00:52:19,000
Por exemplo, no caso de que unha pila, que pode representar unha pila

932
00:52:19,000 --> 00:52:22,000
usando unha estrutura de datos coma este, gustaríame propoñer.

933
00:52:22,000 --> 00:52:26,000
Neste caso, eu teño declarado un struct, e eu xa dixen dentro desta estrutura

934
00:52:26,000 --> 00:52:30,000
é unha matriz de números e, a continuación, un tamaño variable chamada,

935
00:52:30,000 --> 00:52:33,000
e eu vou chamar esa cousa de unha pila.

936
00:52:33,000 --> 00:52:35,000
Agora, por que isto realmente funciona?

937
00:52:35,000 --> 00:52:43,000
No caso de que unha pila, podería deseñar esa eficacia na pantalla como unha matriz.

938
00:52:43,000 --> 00:52:47,000
Aquí é a miña pila. Estes son os meus números.

939
00:52:47,000 --> 00:52:50,000
E nós imos chamar-lles como este, este, este, este, este.

940
00:52:50,000 --> 00:52:53,000
E entón eu teño algún membro doutros datos aquí,

941
00:52:53,000 --> 00:52:58,000
que se chama de tamaño, de xeito que este é o tamaño, e isto é números,

942
00:52:58,000 --> 00:53:02,000
e colectivamente, o iPad todo aquí representa unha estrutura de pila.

943
00:53:02,000 --> 00:53:07,000
Agora, por defecto, o tamaño presuntamente ten que ser inicializar a 0,

944
00:53:07,000 --> 00:53:11,000
e que está dentro da matriz de números inicialmente

945
00:53:11,000 --> 00:53:14,000
cando reservar unha matriz?

946
00:53:14,000 --> 00:53:16,000
Lixo. Quen sabe? E iso realmente non importa.

947
00:53:16,000 --> 00:53:20,000
Non importa se é 1, 2, 3, 4, 5, de forma completamente aleatoria

948
00:53:20,000 --> 00:53:25,000
pola mala sorte almacenados na miña estrutura, porque desde que sei que o tamaño da pila

949
00:53:25,000 --> 00:53:29,000
é 0, entón eu sei que programaticamente, non mire para calquera dos elementos do array.

950
00:53:29,000 --> 00:53:31,000
Non importa o que está aí.

951
00:53:31,000 --> 00:53:34,000
Non mire para eles, como sería a implicación dun tamaño de 0.

952
00:53:34,000 --> 00:53:38,000
>> Pero supoña que agora vai adiante e introducir algo na pila.

953
00:53:38,000 --> 00:53:42,000
Quero introducir o número 5, entón eu coloque o número 5 aquí,

954
00:53:42,000 --> 00:53:45,000
e entón o que eu poño aquí?

955
00:53:45,000 --> 00:53:48,000
Agora eu realmente poñer para abaixo 1 para o tamaño,

956
00:53:48,000 --> 00:53:50,000
e agora, a pila é de tamaño 1.

957
00:53:50,000 --> 00:53:53,000
E se eu ir adiante e escribir o número, digamos, 7 próximo?

958
00:53:53,000 --> 00:53:57,000
Iso, entón, é actualizado a 2, e despois imos facer 9,

959
00:53:57,000 --> 00:54:02,000
e entón esta é actualizado a 3.

960
00:54:02,000 --> 00:54:05,000
Pero a característica interesante agora esta pila é que

961
00:54:05,000 --> 00:54:09,000
Eu teño que borrar elemento que se eu queira pop

962
00:54:09,000 --> 00:54:12,000
algo fóra da pila, por así dicir?

963
00:54:12,000 --> 00:54:14,000
9 sería a primeira cousa a ir.

964
00:54:14,000 --> 00:54:18,000
Como a imaxe debe cambiar se eu queira aparecer un elemento da pila,

965
00:54:18,000 --> 00:54:20,000
Moi parecido cunha bandexa na Mather?

966
00:54:20,000 --> 00:54:22,000
Si >> [Estudante] tamaño definido para 2.

967
00:54:22,000 --> 00:54:27,000
Exactamente, todo o que fago é facer que o tamaño para 2, eo que fago coa matriz?

968
00:54:27,000 --> 00:54:29,000
Eu non teño que facer nada.

969
00:54:29,000 --> 00:54:32,000
Eu podería, só para ser anal, engada un 0 alí ou -1 ou algo para referirse a

970
00:54:32,000 --> 00:54:34,000
que este non é un valor legal, pero non importa porque

971
00:54:34,000 --> 00:54:37,000
Podo gravar fóra do conxunto en si o tempo que

972
00:54:37,000 --> 00:54:41,000
para que eu saiba só ollar para os dous primeiros elementos desta matriz.

973
00:54:41,000 --> 00:54:47,000
Agora, se eu for e engadir o número de 8 a esa matriz, como é que o cadro cambie a continuación?

974
00:54:47,000 --> 00:54:50,000
Isto torna-se 8, e isto fai-se 3.

975
00:54:50,000 --> 00:54:52,000
Estou cortando algúns cantos aquí.

976
00:54:52,000 --> 00:54:56,000
Agora temos 5, 7, 8, e estamos de volta a un tamaño de 3.

977
00:54:56,000 --> 00:54:58,000
Isto é moi sinxelo de implementar,

978
00:54:58,000 --> 00:55:06,000
pero cando é que imos lamentar esta decisión deseño?

979
00:55:06,000 --> 00:55:09,000
Cando as cousas comezan a ir moi, moi malo? Si

980
00:55:09,000 --> 00:55:11,000
[Resposta do alumno inaudível]

981
00:55:11,000 --> 00:55:13,000
Cando se quere volver e incorporarse o primeiro elemento que poñer dentro

982
00:55:13,000 --> 00:55:18,000
>> Acontece aquí, aínda que unha pila é unha matriz debaixo do capó,

983
00:55:18,000 --> 00:55:21,000
esas estruturas de datos que xa comezou a falar xeralmente tamén son coñecidos como

984
00:55:21,000 --> 00:55:25,000
abstractos estruturas de datos polo cal como son aplicadas

985
00:55:25,000 --> 00:55:27,000
é totalmente fóra de cuestión.

986
00:55:27,000 --> 00:55:31,000
Unha estrutura de datos como unha pila se quere engadir soporte

987
00:55:31,000 --> 00:55:35,000
operacións como impulso, que empuxa unha bandexa para a pila,

988
00:55:35,000 --> 00:55:39,000
e pop, que elimina un elemento da pila, e é iso.

989
00:55:39,000 --> 00:55:43,000
Se tivese que baixar código doutra persoa que xa implantadas

990
00:55:43,000 --> 00:55:46,000
esta cousa chamada unha pila, esa persoa tería escrito

991
00:55:46,000 --> 00:55:49,000
só dúas funcións para ti, push e pop, cuxo único propósito na vida

992
00:55:49,000 --> 00:55:51,000
sería facer exactamente isto.

993
00:55:51,000 --> 00:55:54,000
Vostede ou el ou a ela que aplicou o programa

994
00:55:54,000 --> 00:55:58,000
sería enteiramente un para decidir como aplicar

995
00:55:58,000 --> 00:56:00,000
a semántica de empurrar e aparecendo debaixo do capó

996
00:56:00,000 --> 00:56:03,000
ou a función de empurrar e popping.

997
00:56:03,000 --> 00:56:07,000
E eu fixen unha decisión un tanto miope aquí

998
00:56:07,000 --> 00:56:10,000
a través da implementación da miña pila con esta estrutura de datos simples por que?

999
00:56:10,000 --> 00:56:12,000
Cando é que esta pausa estrutura de datos?

1000
00:56:12,000 --> 00:56:18,000
En que punto eu teño que voltar un erro cando o usuario chama push, por exemplo?

1001
00:56:18,000 --> 00:56:20,000
[Estudante] Se non hai máis espazo.

1002
00:56:20,000 --> 00:56:23,000
Exactamente, se hai non máis espazo, se superou a capacidade,

1003
00:56:23,000 --> 00:56:27,000
que é todo en maiúsculas, porque suxire que é algún tipo de constante global.

1004
00:56:27,000 --> 00:56:30,000
Ben, entón eu só vou ter que dicir: "Sentímolo, eu non podo empuxar outro valor

1005
00:56:30,000 --> 00:56:32,000
na pila ", así como en Mather.

1006
00:56:32,000 --> 00:56:36,000
>> Nalgún momento, eles van bater a parte de arriba do despacho que pouco.

1007
00:56:36,000 --> 00:56:39,000
Non hai máis espazo ou capacidade de pila, momento no que hai algún tipo de erro.

1008
00:56:39,000 --> 00:56:42,000
Teñen que poñer o elemento noutro lugar, a bandexa en outro lugar,

1009
00:56:42,000 --> 00:56:44,000
ou en lugar ningún.

1010
00:56:44,000 --> 00:56:47,000
Agora, con unha fila, podemos implementar lo un pouco diferente.

1011
00:56:47,000 --> 00:56:50,000
Unha cola é un pouco diferente, no que, baixo o capo, pode ser aplicado

1012
00:56:50,000 --> 00:56:54,000
como unha matriz, pero por que, neste caso, estou propondo

1013
00:56:54,000 --> 00:56:59,000
ter tamén un elemento de cabeza que representa a cabeza de lista,

1014
00:56:59,000 --> 00:57:06,000
a fronte da lista, a primeira persoa da cola na tenda de Apple, ademais de tamaño?

1015
00:57:06,000 --> 00:57:14,000
Por que eu teño unha peza adicional de datos aquí?

1016
00:57:14,000 --> 00:57:16,000
Debería de volta para o que os números e

1017
00:57:16,000 --> 00:57:18,000
se eu deseño deste xeito.

1018
00:57:18,000 --> 00:57:21,000
Supoñamos que esta é agora unha fila, en vez de unha pila,

1019
00:57:21,000 --> 00:57:24,000
a diferenza ser-así como a cola de almacenamento de Apple é xusto.

1020
00:57:24,000 --> 00:57:27,000
A primeira persoa en liña no inicio da lista, o número 5, neste caso,

1021
00:57:27,000 --> 00:57:30,000
el ou ela vai quedar na primeira tenda.

1022
00:57:30,000 --> 00:57:32,000
Imos facelo.

1023
00:57:32,000 --> 00:57:35,000
Supoñamos que este é o estado da miña cola neste momento no tempo, e agora a tenda de Apple

1024
00:57:35,000 --> 00:57:39,000
Abre ea primeira persoa, número 5, é conducido para a tenda.

1025
00:57:39,000 --> 00:57:43,000
¿Como cambiar o cadro, agora que eu de-cola a primeira persoa

1026
00:57:43,000 --> 00:57:47,000
na parte da fronte da liña?

1027
00:57:47,000 --> 00:57:50,000
¿Que é iso? >> [Estudante] Cambiar a cola.

1028
00:57:50,000 --> 00:57:52,000
Cambiar a cabeza, para 5 desaparece.

1029
00:57:52,000 --> 00:57:56,000
En realidade, é coma se, a mellor forma de facelo?

1030
00:57:56,000 --> 00:58:00,000
En realidade, é coma se este cara desaparece.

1031
00:58:00,000 --> 00:58:03,000
Cal sería o número 7 facer nunha tenda real?

1032
00:58:03,000 --> 00:58:05,000
Eles ían dar un gran paso cara a adiante.

1033
00:58:05,000 --> 00:58:08,000
>> Pero o que temos benvida a apreciar cando se trata de matrices

1034
00:58:08,000 --> 00:58:10,000
e mover as cousas?

1035
00:58:10,000 --> 00:58:12,000
Isto é un desperdicio do seu tempo, non?

1036
00:58:12,000 --> 00:58:16,000
Por que ten que ser tan anal como ter a primeira persoa

1037
00:58:16,000 --> 00:58:21,000
no inicio da liña de física o inicio do bloque de memoria?

1038
00:58:21,000 --> 00:58:23,000
Isto é completamente innecesario. Por que?

1039
00:58:23,000 --> 00:58:26,000
O que eu podería só lembrar en vez diso? >> [Resposta do alumno inaudível]

1040
00:58:26,000 --> 00:58:30,000
Exactamente, eu podería só lembrar con esta cabeza adicional membro de datos

1041
00:58:30,000 --> 00:58:34,000
que agora o cabeza da lista non é 0, o que foi un momento atrás.

1042
00:58:34,000 --> 00:58:39,000
Agora é realmente o número 1. Desta forma, recibín unha optimización leve.

1043
00:58:39,000 --> 00:58:44,000
Só porque eu teño de-cola alguén de liña no inicio da liña na tenda de Apple

1044
00:58:44,000 --> 00:58:47,000
non significa que todo o mundo ten que cambiar, que recall é unha operación lineal.

1045
00:58:47,000 --> 00:58:50,000
Podo pasar o tempo en vez única constante

1046
00:58:50,000 --> 00:58:53,000
e, a continuación, obter unha resposta moito máis rápida.

1047
00:58:53,000 --> 00:58:56,000
Pero o prezo que eu estou pagando o que gañar ese adicional de desempeño

1048
00:58:56,000 --> 00:58:58,000
e non ter que cambiar todos?

1049
00:58:58,000 --> 00:59:01,000
Si >> [Resposta do alumno inaudível]

1050
00:59:01,000 --> 00:59:04,000
Pode engadir máis persoas, así, o problema é ortogonal

1051
00:59:04,000 --> 00:59:07,000
ao feito de que nós non estamos cambiando as persoas en todo.

1052
00:59:07,000 --> 00:59:11,000
É aínda unha matriz para se imos ou non cambiar todos ou non

1053
00:59:11,000 --> 00:59:13,000
oh, eu vexo o que quere dicir, todo ben.

1054
00:59:13,000 --> 00:59:16,000
En realidade, eu estou de acordo co que está dicindo que é case como se

1055
00:59:16,000 --> 00:59:19,000
nós nunca imos agora a usar o inicio desta matriz máis

1056
00:59:19,000 --> 00:59:22,000
porque se eu eliminar 5, entón eu eliminar 7.

1057
00:59:22,000 --> 00:59:24,000
Pero eu só poñer a xente cara á dereita.

1058
00:59:24,000 --> 00:59:28,000
>> Parece que eu estou perdendo espazo e, finalmente, a miña cola se desintegra en nada,

1059
00:59:28,000 --> 00:59:31,000
polo tanto, pode só ter contorno persoas,

1060
00:59:31,000 --> 00:59:35,000
e podemos pensar desa matriz realmente como unha especie de estrutura circular,

1061
00:59:35,000 --> 00:59:38,000
pero usamos o operador en C para facer este tipo de contorno?

1062
00:59:38,000 --> 00:59:40,000
[Resposta do alumno inaudível] >> O operador módulo.

1063
00:59:40,000 --> 00:59:43,000
Sería un pouco aburrido para pensar en como fai a envolvente,

1064
00:59:43,000 --> 00:59:46,000
pero podería facelo, e nós poderiamos comezar a poñer as persoas no que adoitaba ser a fronte da liña,

1065
00:59:46,000 --> 00:59:52,000
pero lembre-se con esta variable cabeza que a cabeza dunha liña realmente é.

1066
00:59:52,000 --> 00:59:57,000
E se, en vez diso, o noso obxectivo, en última análise, non obstante,

1067
00:59:57,000 --> 01:00:00,000
era para buscar números, como fixemos aquí no escenario con Anita,

1068
01:00:00,000 --> 01:00:02,000
pero nós realmente queremos o mellor de todos os mundos?

1069
01:00:02,000 --> 01:00:05,000
Queremos máis que sofisticación matriz permite

1070
01:00:05,000 --> 01:00:09,000
porque queremos que a capacidade de crecer de forma dinámica a estrutura de datos.

1071
01:00:09,000 --> 01:00:12,000
Pero nós non queremos ter que recorrer a algo que indicamos

1072
01:00:12,000 --> 01:00:15,000
na primeira conferencia non era un algoritmo óptimo,

1073
01:00:15,000 --> 01:00:17,000
o de procura lineal.

1074
01:00:17,000 --> 01:00:21,000
Acontece que pode, de feito, alcanzar

1075
01:00:21,000 --> 01:00:24,000
ou polo menos preto de tempo constante, en que alguén como Anita,

1076
01:00:24,000 --> 01:00:27,000
se establece a estrutura de datos non ser unha lista ligada,

1077
01:00:27,000 --> 01:00:30,000
a non ser unha pila, a non ser nunha cola, pode, en realidade,

1078
01:00:30,000 --> 01:00:33,000
chegar a unha estrutura de datos que permite ver as cousas,

1079
01:00:33,000 --> 01:00:37,000
mesmo modo, non só en números, o que chamamos tempo constante.

1080
01:00:37,000 --> 01:00:40,000
>> E, de feito, mirando cara adiante, unha das serie de exercicios nesta clase é case sempre

1081
01:00:40,000 --> 01:00:43,000
a implementación dun corrector ortográfico, que

1082
01:00:43,000 --> 01:00:46,000
nós dámoslle algunhas palabras novo 150.000 ingleses eo obxectivo é

1083
01:00:46,000 --> 01:00:51,000
cargar os a memoria e rapidamente ser capaz de responder ás preguntas do formulario

1084
01:00:51,000 --> 01:00:54,000
é esta palabra soletrada correctamente?

1085
01:00:54,000 --> 01:00:58,000
E sería realmente mamar se tivese que percorrer todos os 150 mil palabras para responder a iso.

1086
01:00:58,000 --> 01:01:02,000
Pero, en realidade, nós imos ver que podemos facelo en tempo moi, moi rápido.

1087
01:01:02,000 --> 01:01:06,000
E vai implicar algo implementación chamada táboa hash,

1088
01:01:06,000 --> 01:01:09,000
e aínda que a primeira vista esa cousa chamada unha táboa hash vai

1089
01:01:09,000 --> 01:01:12,000
imos acadar estes super-rápidas tempos de resposta,

1090
01:01:12,000 --> 01:01:18,000
verifícase que hai, de feito, un problema.

1091
01:01:18,000 --> 01:01:23,000
Cando chega a hora de implementar esta cousa chamada de novo, eu estou facendo iso de novo.

1092
01:01:23,000 --> 01:01:25,000
Eu son o único aquí.

1093
01:01:25,000 --> 01:01:28,000
Cando chega a hora de implementar esa cousa chamada unha táboa hash,

1094
01:01:28,000 --> 01:01:30,000
Nós imos ter que tomar unha decisión.

1095
01:01:30,000 --> 01:01:32,000
Cal debe ser esa cousa realmente ser?

1096
01:01:32,000 --> 01:01:36,000
E cando comezamos a inserción de números para esta táboa hash,

1097
01:01:36,000 --> 01:01:38,000
como é que imos para almacena-los de tal forma

1098
01:01:38,000 --> 01:01:42,000
que pode levalos de volta o máis rápido que chegamos los?

1099
01:01:42,000 --> 01:01:45,000
Pero imos ver antes de tempo que esta cuestión de

1100
01:01:45,000 --> 01:01:48,000
Cando o aniversario de todos está na clase será moi pertinente.

1101
01:01:48,000 --> 01:01:51,000
Acontece que nesta sala, temos algunhas centenas de persoas,

1102
01:01:51,000 --> 01:01:56,000
así as posibilidades de que dous de nós teñen a mesma data de aniversario é probablemente moi elevado.

1103
01:01:56,000 --> 01:01:58,000
E se houbese só 40 nós nesta sala?

1104
01:01:58,000 --> 01:02:02,000
Cales son as posibilidades de dúas persoas que teñen a mesma data de aniversario?

1105
01:02:02,000 --> 01:02:04,000
[Os alumnos] Máis do 50%.

1106
01:02:04,000 --> 01:02:06,000
Si, máis do 50%. En realidade, eu aínda trouxo un gráfico.

1107
01:02:06,000 --> 01:02:08,000
Acontece, e iso é realmente só un sneak preview-

1108
01:02:08,000 --> 01:02:12,000
hai só 58 nós nesta sala, a probabilidade de dous de nós

1109
01:02:12,000 --> 01:02:16,000
ter a mesma data de aniversario é moi alta, case o 100%,

1110
01:02:16,000 --> 01:02:20,000
e que vai causar unha morea de dor para nós o mércores.

1111
01:02:20,000 --> 01:02:24,000
>> Con iso dito, imos atrasar aquí. Vemo-nos o mércores.

1112
01:02:24,000 --> 01:02:28,000
[Aplausos]

1113
01:02:28,000 --> 01:02:30,000
[CS50.TV]