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

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

3
00:00:04,160 --> 00:00:08,720
[Esta es CS50.] [CS50.TV]

4
00:00:08,720 --> 00:00:12,970
Esto es CS50 y este es el fin de semana 6.

5
00:00:12,970 --> 00:00:17,970
Así CS50x, uno de los primeros cursos de Harvard que participan en la iniciativa EDX

6
00:00:17,970 --> 00:00:20,590
de hecho debutó este pasado lunes.

7
00:00:20,590 --> 00:00:23,460
Si a usted le gustaría echar un vistazo a lo que otros en Internet

8
00:00:23,460 --> 00:00:27,180
están siguiendo junto con, usted puede dirigirse a x.cs50.net.

9
00:00:27,180 --> 00:00:30,350
Eso le redirigirá al lugar apropiado en edx.org,

10
00:00:30,350 --> 00:00:34,160
que era donde este y otros cursos del MIT y Berkeley ahora vivimos.

11
00:00:34,160 --> 00:00:38,140
Usted tendrá que registrarse para obtener una cuenta, usted encontrará que el material es en gran parte el mismo

12
00:00:38,140 --> 00:00:42,170
como usted ha tenido este semestre, aunque un par de semanas con retraso, ya que tener todo listo.

13
00:00:42,170 --> 00:00:46,930
Pero lo que los estudiantes en CS50x ahora se ve es una interfaz bastante como éste.

14
00:00:46,930 --> 00:00:50,040
Esto, por ejemplo, es Zamyla liderando el conjunto de problemas paso a paso para 0.

15
00:00:50,040 --> 00:00:54,230
Al iniciar la sesión en edx.org, un estudiante CS50x ve el tipo de cosas

16
00:00:54,230 --> 00:00:57,170
usted esperaría ver en un curso: la conferencia para el lunes,

17
00:00:57,170 --> 00:01:01,650
conferencia para el miércoles, varios cortometrajes, los boletines de problemas, los tutoriales, archivos PDF.

18
00:01:01,650 --> 00:01:04,459
Además, como usted ve aquí, las traducciones automáticas

19
00:01:04,459 --> 00:01:08,390
de las transcripciones inglés al chino, japonés, españoles, italianos,

20
00:01:08,390 --> 00:01:12,810
y un montón de otras lenguas que sin duda será imperfecta

21
00:01:12,810 --> 00:01:15,840
tal como las desplegar mediante programación con algo que se llama una API,

22
00:01:15,840 --> 00:01:18,360
o interfaz de programación de aplicaciones, desde Google

23
00:01:18,360 --> 00:01:21,360
que nos permite convertir Inglés a otros idiomas.

24
00:01:21,360 --> 00:01:24,100
Pero gracias al maravilloso espíritu de algunos voluntarios más de cien,

25
00:01:24,100 --> 00:01:26,940
personas al azar en la Internet que han ofrecido amablemente a participar

26
00:01:26,940 --> 00:01:30,180
en este proyecto, que poco a poco va a mejorar la calidad de las traducciones

27
00:01:30,180 --> 00:01:35,790
haciendo que los humanos corregir los errores que nuestros equipos han hecho.

28
00:01:35,790 --> 00:01:42,330
>> Así que resulta que había unos cuantos estudiantes más aparecer el lunes de lo que inicialmente se esperaba.

29
00:01:42,330 --> 00:01:48,980
De hecho, ahora CS50x cuenta con 100.000 personas a lo largo de los siguientes en casa.

30
00:01:48,980 --> 00:01:54,430
Entonces se da cuenta que todos somos parte de esta clase inaugural de hacer este curso en ciencias de la computación

31
00:01:54,430 --> 00:01:57,370
educación en general, de manera más amplia y accesible.

32
00:01:57,370 --> 00:02:00,130
Y la realidad es ahora, con algunos de estos cursos en línea masivos,

33
00:02:00,130 --> 00:02:04,070
todos ellos comienzan con estos números muy altos, como parece que hemos hecho aquí.

34
00:02:04,070 --> 00:02:08,759
Pero el objetivo, en última instancia, por CS50x es realmente hacer que la gente como muchos hasta la meta como sea posible.

35
00:02:08,759 --> 00:02:12,000
Por su diseño, CS50x va a ser ofrecido desde el pasado lunes

36
00:02:12,000 --> 00:02:17,430
hasta el 15 de abril de 2013, por lo que las personas que tienen compromisos escolares en otras partes,

37
00:02:17,430 --> 00:02:20,990
trabajo, familia, otros conflictos y similares, tienen un poco más de flexibilidad

38
00:02:20,990 --> 00:02:23,640
con la que sumergirse en este curso, que, basta con decir,

39
00:02:23,640 --> 00:02:30,540
es bastante ambiciosa hecho si sólo en el transcurso de tan sólo tres meses durante un semestre normal.

40
00:02:30,540 --> 00:02:34,190
Sin embargo, estos estudiantes serán hacer frente a los boletines de problemas mismos, viendo el mismo contenido,

41
00:02:34,190 --> 00:02:36,350
tener acceso a los mismos pantalones cortos y similares.

42
00:02:36,350 --> 00:02:38,990
Así que darse cuenta de que todos somos verdaderamente juntos en esto.

43
00:02:38,990 --> 00:02:42,360
Y uno de los objetivos finales de CS50x no es sólo para la gente como muchos

44
00:02:42,360 --> 00:02:45,720
a la línea de meta y darles este nuevo entendimiento de la informática

45
00:02:45,720 --> 00:02:49,000
y la programación, sino también para hacer que esta experiencia compartida.

46
00:02:49,000 --> 00:02:52,010
Una de las características definitorias de 50 en el campus, así lo esperamos,

47
00:02:52,010 --> 00:02:56,260
ha sido este tipo de experiencia común, para bien o para mal, a veces,

48
00:02:56,260 --> 00:02:59,480
pero teniendo estas personas se vuelvan hacia la izquierda y hacia la derecha,

49
00:02:59,480 --> 00:03:01,830
y horas de oficina y el hackathon y la feria.

50
00:03:01,830 --> 00:03:04,560
Es un poco más difícil que hacerlo en persona con amigos en línea,

51
00:03:04,560 --> 00:03:10,580
pero CS50x concluirá en abril con la primera CS50 Expo,

52
00:03:10,580 --> 00:03:13,630
que será una adaptación en línea de nuestra idea de la feria

53
00:03:13,630 --> 00:03:18,250
donde estos miles de estudiantes de todo serán invitados a presentar un 1 - a 2 minutos de video,

54
00:03:18,250 --> 00:03:22,480
ya sea un screencast de su proyecto final o video de ellos agitando hola

55
00:03:22,480 --> 00:03:24,490
y hablando de su proyecto y le demos,

56
00:03:24,490 --> 00:03:27,610
al igual que sus predecesores han hecho aquí en el campus de la feria,

57
00:03:27,610 --> 00:03:31,400
de modo que por el final del semestre, se espera tener una exposición mundial

58
00:03:31,400 --> 00:03:37,080
de los proyectos de los estudiantes CS50x 'finales, muy parecida a la que le espera este mes de diciembre en el campus.

59
00:03:37,080 --> 00:03:39,680
Así que más en que en los próximos meses.

60
00:03:39,680 --> 00:03:43,640
>> Con 100.000 estudiantes, sin embargo, viene la necesidad de un CAS poco más.

61
00:03:43,640 --> 00:03:47,590
Teniendo en cuenta que ustedes están abriendo el camino aquí y tomando CS50

62
00:03:47,590 --> 00:03:51,630
varias semanas antes del lanzamiento de este material a la gente en EDX,

63
00:03:51,630 --> 00:03:55,330
damos cuenta de que le encantaría participar ya que muchos de nuestros estudiantes como sea posible en esta iniciativa,

64
00:03:55,330 --> 00:03:58,720
tanto durante el semestre de invierno, así como esta y la próxima primavera.

65
00:03:58,720 --> 00:04:01,620
Así que si usted desea participar en CS50x,

66
00:04:01,620 --> 00:04:07,450
particularmente en unirse a CS50x tratar, la versión de EDX CS50 Discutir,

67
00:04:07,450 --> 00:04:10,140
que muchos de ustedes se han estado utilizando en el campus, el tablón de anuncios en línea,

68
00:04:10,140 --> 00:04:13,040
por favor cabeza a esa URL, vamos a saber quién eres,

69
00:04:13,040 --> 00:04:16,450
porque nos encantaría construir un equipo de estudiantes y profesores y el personal por igual

70
00:04:16,450 --> 00:04:19,630
en el campus que están simplemente jugando bien y ayudando.

71
00:04:19,630 --> 00:04:21,720
Y cuando ven a una cuestión que es familiar para ellos,

72
00:04:21,720 --> 00:04:25,320
que escuche un estudiante informar algún error en alguna parte ahí fuera en algún país en Internet,

73
00:04:25,320 --> 00:04:27,450
y que suena una campana, ya que también tenía ese mismo número

74
00:04:27,450 --> 00:04:32,620
en su d-hall hace algún tiempo, es de esperar entonces usted puede meter su cuchara y compartir su propia experiencia.

75
00:04:32,620 --> 00:04:37,300
Así que por favor participar si usted quisiera.

76
00:04:37,300 --> 00:04:39,360
>> Cursos de ciencias de la computación en la Universidad de Harvard tiene un poco de una tradición,

77
00:04:39,360 --> 00:04:44,730
CS50 entre ellos, de tener un poco de ropa, algo de ropa, que se puede llevar con orgullo

78
00:04:44,730 --> 00:04:49,090
al final del semestre, diciendo muy orgulloso de que haya terminado CS50

79
00:04:49,090 --> 00:04:51,830
y tomó CS50 y similares, y siempre tratamos de involucrar a los estudiantes

80
00:04:51,830 --> 00:04:54,540
en este proceso tanto como sea posible, mediante el cual invitamos,

81
00:04:54,540 --> 00:04:56,900
en esta época del semestre, los estudiantes a presentar sus diseños

82
00:04:56,900 --> 00:04:59,330
el uso de Photoshop, o cualquier herramienta de selección que desea utilizar

83
00:04:59,330 --> 00:05:02,330
si eres un diseñador, a presentar sus diseños para camisetas y sudaderas

84
00:05:02,330 --> 00:05:06,100
y sombrillas y pañuelos para perros pequeños que ahora tenemos y similares.

85
00:05:06,100 --> 00:05:09,370
Y todo es entonces - los ganadores de cada año después se exhibió

86
00:05:09,370 --> 00:05:12,700
en la página web de la asignatura en store.cs50.net.

87
00:05:12,700 --> 00:05:15,790
Todo lo que se vende a un costo allí, pero el sitio web sólo en sí funciona

88
00:05:15,790 --> 00:05:18,330
y permite a las personas elegir los colores y diseños que les gustan.

89
00:05:18,330 --> 00:05:20,420
Así que pensé que acabábamos de compartir algunos de los diseños del año pasado

90
00:05:20,420 --> 00:05:25,130
que estaban en el sitio web, además de este de aquí, que es una tradición anual.

91
00:05:25,130 --> 00:05:29,410
"Cada día estoy Seg Faultn" fue una de las presentaciones del año pasado,

92
00:05:29,410 --> 00:05:32,290
que todavía se encuentra allí para antiguos alumnos.

93
00:05:32,290 --> 00:05:35,820
Hemos tenido este ", CS50, Established 1989".

94
00:05:35,820 --> 00:05:39,010
Uno de nuestros Bowdens, Rob, era muy popular el año pasado.

95
00:05:39,010 --> 00:05:43,480
"Equipo de Bowden" nació, este diseño fue presentado, entre los más vendidos.

96
00:05:43,480 --> 00:05:49,040
Al igual que este de aquí. Mucha gente tenía "fiebre Bowden", de acuerdo a los registros de ventas.

97
00:05:49,040 --> 00:05:52,650
Darse cuenta de lo que ahora podría ser el diseño de ahí, en Internet.

98
00:05:52,650 --> 00:05:57,510
Más detalles sobre este problema en el siguiente establece por venir.

99
00:05:57,510 --> 00:06:00,330
>> Una de las herramientas más: usted ha tenido alguna exposición y espero que ahora

100
00:06:00,330 --> 00:06:02,350
algo de experiencia práctica con GDB,

101
00:06:02,350 --> 00:06:04,570
que es, por supuesto, un depurador y permite manipular

102
00:06:04,570 --> 00:06:09,500
su programa a un nivel bastante bajo, haciendo que tipo de cosas?

103
00:06:09,500 --> 00:06:13,030
¿Qué GDB permiten hacer?

104
00:06:13,030 --> 00:06:15,030
¿Sí? Dame algo. [Respuesta Estudiantil, ininteligible]

105
00:06:15,030 --> 00:06:18,120
Bueno. Entre en la función, por lo que no sólo hay que escribir run

106
00:06:18,120 --> 00:06:22,310
y tienen el golpe programa a través de su totalidad, la impresión de las cosas en la salida estándar.

107
00:06:22,310 --> 00:06:25,190
Más bien, usted puede caminar a través de línea por línea, ya sea escribiendo próximo

108
00:06:25,190 --> 00:06:30,300
a ir línea por línea a línea o paso a sumergirse en una función, típicamente uno que usted escribió.

109
00:06:30,300 --> 00:06:35,240
¿Qué más hace el BGF le permiten hacer? ¿Sí? [Respuesta Estudiantil, ininteligible]

110
00:06:35,240 --> 00:06:38,100
Imprimir variables. Así que si usted quiere hacer un poco de introspección dentro de su programa de

111
00:06:38,100 --> 00:06:41,500
sin tener que recurrir a escribir sentencias printf por todo el lugar,

112
00:06:41,500 --> 00:06:44,600
usted puede imprimir una variable o mostrar una variable.

113
00:06:44,600 --> 00:06:46,710
¿Qué más se puede hacer con un depurador GDB como?

114
00:06:46,710 --> 00:06:49,170
[Respuesta Estudiantil, ininteligible]

115
00:06:49,170 --> 00:06:52,080
Exactamente. Puede establecer puntos de interrupción, se puede decir que la ejecución descanso

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

117
00:06:54,020 --> 00:06:56,800
Se puede decir que la ejecución de descanso en la línea 123.

118
00:06:56,800 --> 00:06:58,950
Y los puntos de interrupción son una técnica muy poderosa

119
00:06:58,950 --> 00:07:01,110
porque si usted tiene una idea general de dónde está su problema

120
00:07:01,110 --> 00:07:05,360
probablemente es, usted no tiene que perder tiempo pasando a través de la totalidad del programa.

121
00:07:05,360 --> 00:07:08,250
Usted puede esencialmente saltar allí y comience a escribir -

122
00:07:08,250 --> 00:07:10,970
paso a paso a través de él con el paso o el siguiente o similar.

123
00:07:10,970 --> 00:07:14,340
Pero el problema con algo como GDB es que te ayuda, los recursos humanos,

124
00:07:14,340 --> 00:07:16,940
encontrar sus problemas y encontrar sus errores.

125
00:07:16,940 --> 00:07:19,470
No necesariamente encontrarlos tanto por ti.

126
00:07:19,470 --> 00:07:23,070
>> Así se introdujo el style50 otro día, que es una herramienta de línea de comandos corto

127
00:07:23,070 --> 00:07:27,500
que trata de estilizar su código un poco más limpio que tú, el ser humano, podría haber hecho.

128
00:07:27,500 --> 00:07:29,530
Pero eso, también, es en realidad una cosa estética.

129
00:07:29,530 --> 00:07:34,110
Pero resulta que hay esta otra herramienta llamada Valgrind que es un poco más arcano de usar.

130
00:07:34,110 --> 00:07:36,860
Su salida es atrozmente críptico a primera vista.

131
00:07:36,860 --> 00:07:39,420
Pero es maravillosamente útil, sobre todo ahora que estamos en la parte del término

132
00:07:39,420 --> 00:07:43,080
donde vas a empezar a usar malloc y la asignación de memoria dinámica.

133
00:07:43,080 --> 00:07:45,420
Las cosas pueden ir muy, muy mal rápidamente.

134
00:07:45,420 --> 00:07:49,320
Porque si usted se olvida de liberar su memoria, o deja de hacer referencia alguna puntero NULL,

135
00:07:49,320 --> 00:07:55,770
o deja de hacer referencia alguna puntero de basura, lo que suele ser el síntoma de que los resultados?

136
00:07:55,770 --> 00:07:59,470
Seg culpa. Y se obtiene el archivo base de una cierta cantidad de kilobytes o megabytes

137
00:07:59,470 --> 00:08:02,990
que representa el estado de la memoria del programa, cuando se estrelló,

138
00:08:02,990 --> 00:08:05,730
pero en última instancia, su programa seg fallas, falla de segmentación,

139
00:08:05,730 --> 00:08:08,450
lo que significa que algo malo ha pasado casi siempre relacionados

140
00:08:08,450 --> 00:08:11,750
a un error relacionado con la memoria que usted ha hecho en alguna parte.

141
00:08:11,750 --> 00:08:14,100
Así Valgrind ayuda a encontrar cosas como esta.

142
00:08:14,100 --> 00:08:17,720
Es una herramienta que se ejecuta, como GDB, después de haber compilado el programa,

143
00:08:17,720 --> 00:08:20,330
pero en lugar de ejecutar el programa directamente, se corre Valgrind

144
00:08:20,330 --> 00:08:23,960
y se pasa a su programa, tal como lo hace con GDB.

145
00:08:23,960 --> 00:08:26,220
Ahora, el uso, para obtener el mejor tipo de salida,

146
00:08:26,220 --> 00:08:30,410
es un poco largo, así que ahí lo alto de la pantalla verás Valgrind-v.

147
00:08:30,410 --> 00:08:35,350
"-V" casi universalmente significa detallado cuando usted está utilizando programas en un equipo Linux.

148
00:08:35,350 --> 00:08:38,770
Por lo tanto, significa escupir más datos que usted puede ser que de forma predeterminada.

149
00:08:38,770 --> 00:08:45,510
"- Comprobar fugas = full." Esto es sólo decir cheque por todas las posibles pérdidas de memoria,

150
00:08:45,510 --> 00:08:49,430
errores que pude haber hecho. Esto, también, es un paradigma común con los programas de Linux.

151
00:08:49,430 --> 00:08:52,710
En general, si usted tiene un argumento de línea de comandos que es un "switch",

152
00:08:52,710 --> 00:08:55,830
que se supone que para cambiar el comportamiento del programa, y ​​es una sola letra,

153
00:08:55,830 --> 00:09:00,310
es-v, pero si eso cambia, sólo por el diseño del programador,

154
00:09:00,310 --> 00:09:05,150
es una palabra completa o una serie de palabras, el argumento de línea de comandos se inicia con -.

155
00:09:05,150 --> 00:09:08,190
Estos son sólo convenciones humanas, pero las vas a ver cada vez más.

156
00:09:08,190 --> 00:09:12,410
Y luego, finalmente, "a.out" es el nombre arbitrario para el programa en este ejemplo en particular.

157
00:09:12,410 --> 00:09:14,640
Y aquí está una salida representativa.

158
00:09:14,640 --> 00:09:22,890
>> Antes de ver lo que esto significa, déjame ir a un fragmento de código por aquí.

159
00:09:22,890 --> 00:09:26,390
Y déjame mover esta fuera del camino, muy pronto,

160
00:09:26,390 --> 00:09:32,120
y vamos a echar un vistazo a memory.c, que es este pequeño ejemplo aquí.

161
00:09:32,120 --> 00:09:36,290
Así que en este programa, quiero hacer un zoom sobre las funciones y preguntas.

162
00:09:36,290 --> 00:09:39,430
Tenemos una función principal que llama a una función, f,

163
00:09:39,430 --> 00:09:45,590
y entonces, ¿qué f proceder a hacer, en Inglés un poco técnico?

164
00:09:45,590 --> 00:09:49,760
¿Qué hace f proceder a hacer?

165
00:09:49,760 --> 00:09:53,680
¿Qué voy a empezar con la línea 20, y la ubicación de la estrella, no importa,

166
00:09:53,680 --> 00:09:56,720
pero sólo voy a ser coherentes con la última conferencia.

167
00:09:56,720 --> 00:09:59,910
¿Cuál es la línea 20 es para nosotros? En el lado de mano izquierda. Vamos a descomponer aún más.

168
00:09:59,910 --> 00:10:02,410
Int * x: ¿qué hacer?

169
00:10:02,410 --> 00:10:04,940
Bien. Se declara un puntero, y ahora vamos a ser aún más técnico.

170
00:10:04,940 --> 00:10:10,230
¿Qué quiere decir, muy concretamente, para declarar un puntero? ¿Alguien más?

171
00:10:10,230 --> 00:10:15,050
¿Sí? [Respuesta Estudiantil, ininteligible] Demasiado lejos.

172
00:10:15,050 --> 00:10:17,060
Así que usted está leyendo al lado derecho del signo igual.

173
00:10:17,060 --> 00:10:20,290
Vamos a centrarnos sólo en el lado izquierdo, justo en int * x.

174
00:10:20,290 --> 00:10:24,700
Esto significa "declarar" un puntero, pero ahora vamos a bucear más profundo a esa definición.

175
00:10:24,700 --> 00:10:28,330
¿Qué quiere decir concretamente, técnicamente significa? ¿Sí?

176
00:10:28,330 --> 00:10:31,940
[Respuesta Estudiantil, ininteligible]

177
00:10:31,940 --> 00:10:35,090
Bien. Se está preparando para guardar una dirección en la memoria.

178
00:10:35,090 --> 00:10:40,680
Bueno. Y vamos a tomar un paso más allá, es declarar una variable, x, que es de 32 bits.

179
00:10:40,680 --> 00:10:44,440
Y yo sé que es de 32 bits porque -?

180
00:10:44,440 --> 00:10:47,390
No es porque es un int, porque es un puntero en este caso.

181
00:10:47,390 --> 00:10:49,650
La coincidencia de que es uno y el mismo con un int,

182
00:10:49,650 --> 00:10:51,970
pero el hecho de que no es la estrella no significa que es un puntero

183
00:10:51,970 --> 00:10:57,300
y en el aparato, como con muchos equipos, pero no todos, los punteros son de 32 bits.

184
00:10:57,300 --> 00:11:01,850
El hardware más moderno, como los últimos Macs, los últimos ordenadores, puede tener punteros de 64 bits,

185
00:11:01,850 --> 00:11:04,160
pero en el aparato, estas cosas son de 32 bits.

186
00:11:04,160 --> 00:11:08,380
Así que vamos a estandarizar en eso. Más concretamente, la historia va como sigue:

187
00:11:08,380 --> 00:11:10,820
Nosotros "declarar" un puntero, lo que quiere decir eso?

188
00:11:10,820 --> 00:11:12,810
Nos preparamos para almacenar una dirección de memoria.

189
00:11:12,810 --> 00:11:15,530
¿Qué significa eso?

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

191
00:11:19,810 --> 00:11:23,810
que pronto va a almacenar la dirección de un número entero.

192
00:11:23,810 --> 00:11:26,470
Y eso es probablemente tan precisos como podamos.

193
00:11:26,470 --> 00:11:31,810
Está bien avanzar a simplificar el mundo y decir declarar un puntero llamado x.

194
00:11:31,810 --> 00:11:35,380
Declara un puntero, pero darse cuenta y entender lo que realmente está pasando

195
00:11:35,380 --> 00:11:38,490
incluso en tan sólo esos pocos caracteres.

196
00:11:38,490 --> 00:11:42,040
>> Ahora, éste es casi un poco más fácil, aunque es una expresión más larga.

197
00:11:42,040 --> 00:11:48,160
Entonces, ¿qué está haciendo esto, eso es resaltada ahora: "malloc (10 * sizeof (int));" ¿Sí?

198
00:11:48,160 --> 00:11:52,350
[Respuesta Estudiantil, ininteligible]

199
00:11:52,350 --> 00:11:58,250
Bueno. Y lo voy a llevar allí. Se asigna una porción de memoria para diez enteros.

200
00:11:58,250 --> 00:12:02,190
Y ahora vamos a bucear un poco más profundo, es la asignación de una parte de la memoria para diez enteros.

201
00:12:02,190 --> 00:12:05,390
Lo que se malloc luego regresar?

202
00:12:05,390 --> 00:12:10,390
La dirección de ese bloque, o, más concretamente, la dirección del primer byte de ese bloque.

203
00:12:10,390 --> 00:12:14,080
¿Cómo entonces soy el programador, para saber dónde está ese pedazo de fines de memoria?

204
00:12:14,080 --> 00:12:18,340
Yo sé que es contigua. Malloc, por definición, le dará una parte contigua de la memoria.

205
00:12:18,340 --> 00:12:21,240
No hay espacios en blanco. Usted tiene acceso a todos los bytes en ese pedazo,

206
00:12:21,240 --> 00:12:26,760
espalda con espalda con espalda, pero ¿cómo puedo saber dónde está el final de este trozo de memoria es?

207
00:12:26,760 --> 00:12:28,850
Cuando se utiliza malloc? [Respuesta Estudiantil, ininteligible] Bueno.

208
00:12:28,850 --> 00:12:30,670
No lo sabes. Usted tiene que recordar.

209
00:12:30,670 --> 00:12:35,960
Tengo que recordar que usé el valor 10, y ni siquiera parecen haber hecho eso aquí.

210
00:12:35,960 --> 00:12:41,000
Sin embargo, la responsabilidad recae enteramente sobre mí. Strlen, que nos hemos vuelto un poco dependientes de las cadenas,

211
00:12:41,000 --> 00:12:45,860
sólo funciona a causa de esta convención de tener \ 0

212
00:12:45,860 --> 00:12:48,840
o este carácter especial nul, NUL, al final de una cadena.

213
00:12:48,840 --> 00:12:51,740
Eso no se sostiene por unos trozos arbitrarios de la memoria.

214
00:12:51,740 --> 00:12:58,590
Todo depende de usted. Así que la línea 20, a continuación, asigna un trozo de memoria

215
00:12:58,590 --> 00:13:02,590
que puede almacenar diez números enteros, y almacena la dirección del primer byte

216
00:13:02,590 --> 00:13:05,610
de ese bloque de memoria en la variable x se llama.

217
00:13:05,610 --> 00:13:11,140
Ergo, que es un puntero. Así que la línea 21, por desgracia, fue un error.

218
00:13:11,140 --> 00:13:16,110
Pero primero, ¿qué está haciendo? Está diciendo tienda en el lugar 10, 0 indexado,

219
00:13:16,110 --> 00:13:19,480
del bloque de memoria llamado x el valor 0.

220
00:13:19,480 --> 00:13:21,510
>> Así cuenta un par de cosas están sucediendo.

221
00:13:21,510 --> 00:13:25,420
A pesar de que x es un puntero, recuperará un par de semanas

222
00:13:25,420 --> 00:13:29,440
que todavía se puede utilizar la notación cuadrada estilo-matriz soporte.

223
00:13:29,440 --> 00:13:36,180
Porque eso es realmente taquigrafía notación para la aritmética de punteros más críptico de futuro.

224
00:13:36,180 --> 00:13:40,320
donde íbamos a hacer algo como esto: Tome la dirección x, mueva más de 10 puntos,

225
00:13:40,320 --> 00:13:44,550
a continuación, ir allí a cualquier dirección se almacena en esa ubicación.

226
00:13:44,550 --> 00:13:48,090
Pero, francamente, esto no es más atroz de leer y sentirse cómodo con.

227
00:13:48,090 --> 00:13:52,900
Así que el mundo suele utilizar los corchetes sólo porque es mucho más amigable para leer.

228
00:13:52,900 --> 00:13:55,140
Pero eso es lo que realmente está pasando debajo de la campana;

229
00:13:55,140 --> 00:13:58,190
x es una dirección no una matriz, per se.

230
00:13:58,190 --> 00:14:02,410
Así que este es el almacenamiento de 0 en lugar 10 en x.

231
00:14:02,410 --> 00:14:06,120
¿Por qué es esto malo? ¿Sí?

232
00:14:06,120 --> 00:14:17,370
[Respuesta Estudiantil, ininteligible] Exactamente.

233
00:14:17,370 --> 00:14:21,100
Sólo nos asignaron diez enteros, pero contamos desde 0 al programar en C,

234
00:14:21,100 --> 00:14:25,690
por lo que tiene acceso a la 0 1 2 3 4 5 6 7 8 9, pero no 10.

235
00:14:25,690 --> 00:14:30,270
Así que, o el programa va a culpa seg o no lo es.

236
00:14:30,270 --> 00:14:32,900
Sin embargo, no se sabe muy bien, lo que es una especie de comportamiento no determinista.

237
00:14:32,900 --> 00:14:35,600
Realmente depende de si tenemos suerte.

238
00:14:35,600 --> 00:14:40,650
Si resulta que el sistema operativo no le importa si utilizo ese byte extra,

239
00:14:40,650 --> 00:14:43,360
a pesar de que no lo ha dado a mí, mi programa no se puede bloquear.

240
00:14:43,360 --> 00:14:46,780
Es crudo, tiene fallos, pero es posible que no vea ese síntoma,

241
00:14:46,780 --> 00:14:48,960
o puede que lo veo de vez en cuando.

242
00:14:48,960 --> 00:14:51,230
Pero la realidad es que el error es, de hecho, existe.

243
00:14:51,230 --> 00:14:54,320
Y es realmente problemático si usted ha escrito un programa que quieres ser correcta,

244
00:14:54,320 --> 00:14:58,840
que ha vendido el programa que la gente está utilizando que cada de vez en cuando se bloquea

245
00:14:58,840 --> 00:15:02,450
porque, por supuesto, esto no es bueno. De hecho, si usted tiene un teléfono Android o un iPhone

246
00:15:02,450 --> 00:15:05,550
y descargar aplicaciones en estos días, si usted ha tenido alguna vez una aplicación para dejar de fumar justo,

247
00:15:05,550 --> 00:15:10,040
de repente desaparece, que es casi siempre el resultado de algún problema relacionado con la memoria,

248
00:15:10,040 --> 00:15:12,830
por lo que el programador pata y anula la referencia de un puntero

249
00:15:12,830 --> 00:15:18,670
que él o ella no debe tener, y el resultado de iOS o Android es matar sólo el programa completo

250
00:15:18,670 --> 00:15:23,080
en lugar de los comportamientos de riesgo definidos o algún tipo de compromiso de seguridad.

251
00:15:23,080 --> 00:15:25,950
>> Hay un error en este otro programa aparte de éste.

252
00:15:25,950 --> 00:15:30,180
¿Qué más he cagado en este programa?

253
00:15:30,180 --> 00:15:32,740
Yo no he practicado lo que he predicado. ¿Sí?

254
00:15:32,740 --> 00:15:34,760
[Respuesta Estudiantil, ininteligible] Bueno.

255
00:15:34,760 --> 00:15:36,880
No he liberado la memoria. Así que la regla de oro ahora

256
00:15:36,880 --> 00:15:43,150
tiene que ser en cualquier momento de llamar malloc, debe llamar libre cuando haya terminado de usar esa memoria.

257
00:15:43,150 --> 00:15:45,610
Ahora, cuando iba yo a querer liberar esta memoria?

258
00:15:45,610 --> 00:15:49,780
Probablemente, asumiendo esta primera línea era correcta, me gustaría hacerlo aquí.

259
00:15:49,780 --> 00:15:55,710
Porque yo no podría, por ejemplo, lo hacen aquí. ¿Por qué?

260
00:15:55,710 --> 00:15:57,860
Justo fuera de su alcance. Así que, aunque estamos hablando de punteros,

261
00:15:57,860 --> 00:16:04,830
esta es una semana 2 o 3 cuestión, donde x es sólo un alcance dentro de las llaves donde se declaró.

262
00:16:04,830 --> 00:16:11,000
Así que definitivamente no se puede liberar allí. Mi única oportunidad de liberarlo es más o menos después de la línea 21.

263
00:16:11,000 --> 00:16:15,170
Este es un programa bastante sencillo, era bastante fácil una vez que tipo de envolvió su mente

264
00:16:15,170 --> 00:16:17,870
en torno a lo que el programa está haciendo, dónde están los errores eran.

265
00:16:17,870 --> 00:16:20,500
E incluso si usted no lo vi al principio, esperamos que sea un poco obvio ahora

266
00:16:20,500 --> 00:16:23,870
que estos errores son bastante fácil de resolver y hacer fácilmente.

267
00:16:23,870 --> 00:16:28,720
Pero cuando un programa tiene más de 12 líneas de largo, que es 50 líneas, 100 líneas de largo,

268
00:16:28,720 --> 00:16:31,150
caminando por el código línea por línea, pensar en ello, lógicamente,

269
00:16:31,150 --> 00:16:35,110
Es posible, pero no muy divertido de hacer, constantemente en busca de errores,

270
00:16:35,110 --> 00:16:38,340
y también es difícil de hacer, y es por eso que una herramienta como Valgrind existe.

271
00:16:38,340 --> 00:16:40,900
Déjenme seguir adelante y hacer esto: déjame abrir la ventana de terminal,

272
00:16:40,900 --> 00:16:45,400
Y no me basta con ejecutar la memoria, porque la memoria parece estar bien.

273
00:16:45,400 --> 00:16:49,180
Estoy teniendo suerte. Que va a byte adicional al final de la matriz

274
00:16:49,180 --> 00:16:51,060
no parece ser demasiado problemático.

275
00:16:51,060 --> 00:16:56,370
Pero me deja, no obstante, hacer una comprobación de validez, lo cual significa para comprobar

276
00:16:56,370 --> 00:16:58,320
si es o no es realmente correcto.

277
00:16:58,320 --> 00:17:04,690
>> Así que vamos a hacer valgrind-v - Fuga-check = completo,

278
00:17:04,690 --> 00:17:07,520
y luego el nombre del programa en este caso es la memoria, no a.out.

279
00:17:07,520 --> 00:17:10,760
Así que déjame ir adelante y hacerlo. Pulse Enter.

280
00:17:10,760 --> 00:17:14,109
Querido Dios. Esta es su salida, y esto es lo que he aludido antes.

281
00:17:14,109 --> 00:17:17,550
Pero, si aprendes a leer a través de todos los disparates aquí,

282
00:17:17,550 --> 00:17:20,760
la mayor parte de esta producción es sólo de diagnóstico que no es tan interesante.

283
00:17:20,760 --> 00:17:24,829
Lo que el ojo realmente quiere estar buscando es cualquier mención de error o no válido.

284
00:17:24,829 --> 00:17:26,800
Palabras que sugieren problemas.

285
00:17:26,800 --> 00:17:29,340
Y, de hecho, vamos a ver lo que va mal aquí abajo.

286
00:17:29,340 --> 00:17:35,230
Tengo un resumen de algún tipo, "en uso en la salida:. 40 bytes en bloques de 1"

287
00:17:35,230 --> 00:17:38,750
No estoy realmente seguro de lo que un bloque es todavía, pero 40 bytes

288
00:17:38,750 --> 00:17:41,260
en realidad se siente como si pudiera averiguar dónde que viene.

289
00:17:41,260 --> 00:17:45,030
40 bytes. ¿Por qué son de 40 bytes en uso en la salida?

290
00:17:45,030 --> 00:17:48,780
Y más concretamente, si nos desplazamos hasta aquí,

291
00:17:48,780 --> 00:17:54,520
¿por qué he perdido definitivamente 40 bytes? ¿Sí?

292
00:17:54,520 --> 00:17:59,520
[Respuesta Estudiantil, ininteligible] Perfect. Sí, exactamente.

293
00:17:59,520 --> 00:18:03,540
Había diez números enteros, y cada uno de ellos es el tamaño de 4, o 32 bits,

294
00:18:03,540 --> 00:18:08,300
así que he perdido 40 bytes precisamente porque, como usted propone, no he llamado libre.

295
00:18:08,300 --> 00:18:13,460
Eso es un error, y ahora vamos a mirar hacia abajo un poco más y ver al lado de este,

296
00:18:13,460 --> 00:18:16,900
"No válido escribir de tamaño 4". Ahora, ¿qué es esto?

297
00:18:16,900 --> 00:18:21,150
Esta dirección se expresa lo que la notación de base, al parecer?

298
00:18:21,150 --> 00:18:23,640
Esto es hexadecimal, y cada vez que ve un número que comienza con 0x,

299
00:18:23,640 --> 00:18:29,410
significa hexadecimal, lo que hicimos allá por, creo, conjunto de procesadores 0 en la sección de preguntas,

300
00:18:29,410 --> 00:18:34,090
que era sólo para hacer un ejercicio de calentamiento, la conversión de decimal a hexadecimal a binario y así sucesivamente.

301
00:18:34,090 --> 00:18:39,220
Hexadecimal, sólo por convención humana, generalmente se utiliza para representar los punteros

302
00:18:39,220 --> 00:18:41,570
o, más generalmente, se dirige. Es sólo una convención,

303
00:18:41,570 --> 00:18:45,340
porque es un poco más fácil de leer, que es un poco más compacto que algo como decimal,

304
00:18:45,340 --> 00:18:47,720
y binario es inútil para la mayoría de los seres humanos para su uso.

305
00:18:47,720 --> 00:18:50,840
¿Y ahora qué quiere decir esto? Bueno, parece que hay una escritura no válido

306
00:18:50,840 --> 00:18:54,480
de tamaño 4 en la línea 21 de memory.c.

307
00:18:54,480 --> 00:18:59,180
Así que vamos a volver a la línea 21, y de hecho, es que de escritura no válido.

308
00:18:59,180 --> 00:19:02,640
Así Valgrind no se va a celebrar por completo mi mano y me diga lo que la solución es,

309
00:19:02,640 --> 00:19:05,520
pero se detecta que estoy haciendo una escritura válida.

310
00:19:05,520 --> 00:19:08,800
Estoy tocando 4 bytes que no debe ser, y al parecer eso es porque,

311
00:19:08,800 --> 00:19:13,960
como usted ha señalado, estoy haciendo [10] en lugar de [9] máximamente

312
00:19:13,960 --> 00:19:16,660
o [0] o algo intermedio.

313
00:19:16,660 --> 00:19:19,690
Con Valgrind, se dan cuenta en cualquier momento que ahora estamos escribiendo un programa

314
00:19:19,690 --> 00:19:24,190
que utiliza punteros y utiliza la memoria, y malloc más específicamente,

315
00:19:24,190 --> 00:19:27,080
definitivamente entrar en el hábito de correr tanto tiempo

316
00:19:27,080 --> 00:19:30,890
pero muy fácil de copiar y pegar comandos de Valgrind

317
00:19:30,890 --> 00:19:32,650
para ver si hay algunos errores en ese país.

318
00:19:32,650 --> 00:19:34,820
Y va a ser abrumador cada vez que ves la salida,

319
00:19:34,820 --> 00:19:39,430
pero sólo a través de analizar visualmente la totalidad del producto y ver si usted ve las menciones de errores

320
00:19:39,430 --> 00:19:43,190
o advertencias o inválida o perdida.

321
00:19:43,190 --> 00:19:46,200
Las palabras que suenan como te equivocaste en alguna parte.

322
00:19:46,200 --> 00:19:48,580
Así que darse cuenta de que es una nueva herramienta en su caja de herramientas.

323
00:19:48,580 --> 00:19:51,270
>> Ahora el lunes, tuvimos un montón de gente viene hasta aquí

324
00:19:51,270 --> 00:19:53,150
y representar la noción de una lista enlazada.

325
00:19:53,150 --> 00:20:00,970
Y presentamos la lista enlazada como una solución a cuál es el problema?

326
00:20:00,970 --> 00:20:04,590
¿Sí? [Respuesta Estudiantil, ininteligible] Bueno.

327
00:20:04,590 --> 00:20:06,530
Las matrices no pueden tener memoria que se agrega a ellos.

328
00:20:06,530 --> 00:20:09,440
Si asigna una matriz de tamaño 10, eso es todo lo que hay.

329
00:20:09,440 --> 00:20:13,690
Usted puede llamar a una función como realloc si inicialmente llamada malloc,

330
00:20:13,690 --> 00:20:17,580
y que puede tratar de crecer la matriz si no hay espacio hacia el final de ella

331
00:20:17,580 --> 00:20:21,610
que nadie más está usando, y si no hay, se acaba de encontrar un pedazo más grande a otro lugar.

332
00:20:21,610 --> 00:20:25,040
Pero entonces se copiará todos esos bytes en la nueva matriz.

333
00:20:25,040 --> 00:20:28,310
Esto suena como una solución muy correcta.

334
00:20:28,310 --> 00:20:34,790
¿Por qué es poco atractivo?

335
00:20:34,790 --> 00:20:36,940
Quiero decir que funciona, los seres humanos han resuelto este problema.

336
00:20:36,940 --> 00:20:40,710
¿Por qué tenemos que resolver el lunes con listas enlazadas? ¿Sí?

337
00:20:40,710 --> 00:20:44,060
[Respuesta Estudiantil, ininteligible] Podría tomar mucho tiempo.

338
00:20:44,060 --> 00:20:49,260
De hecho, cada vez que usted está llamando malloc o calloc o realloc, que es una más,

339
00:20:49,260 --> 00:20:52,470
cualquier usted tiempo, el programa, están hablando con el sistema operativo,

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

341
00:20:54,310 --> 00:20:57,470
Y si usted está haciendo este tipo de cosas en los bucles, en realidad está ralentizando.

342
00:20:57,470 --> 00:21:00,740
No vas a notar esto para el más simple de "Hello World" programas de tipo,

343
00:21:00,740 --> 00:21:04,300
pero en programas mucho más grandes, haciendo que el sistema operativo y otra vez para la memoria

344
00:21:04,300 --> 00:21:07,520
o dar de nuevo una y otra vez no suele ser una buena cosa.

345
00:21:07,520 --> 00:21:11,210
Además, es sólo una especie de intelectual - es una completa pérdida de tiempo.

346
00:21:11,210 --> 00:21:16,490
¿Por qué asignar más memoria y más, el riesgo de copiar todo en la nueva matriz,

347
00:21:16,490 --> 00:21:21,980
si usted tiene una alternativa que le permite asignar memoria sólo lo que realmente necesita?

348
00:21:21,980 --> 00:21:24,130
Así que hay ventajas y desventajas en aquí.

349
00:21:24,130 --> 00:21:26,730
Una de las ventajas es que ahora tenemos dinamismo.

350
00:21:26,730 --> 00:21:29,100
No importa donde los trozos de memoria son que son gratuitas,

351
00:21:29,100 --> 00:21:32,070
Sólo puede ordenar de crear estas migas de pan a través de punteros

352
00:21:32,070 --> 00:21:34,470
para encadenar mi lista entera unidos entre sí.

353
00:21:34,470 --> 00:21:36,470
Pero me pagar al menos un precio.

354
00:21:36,470 --> 00:21:40,060
>> ¿Qué tengo que renunciar a obtener listas enlazadas?

355
00:21:40,060 --> 00:21:42,470
¿Sí? [Respuesta Estudiantil, ininteligible] Bueno.

356
00:21:42,470 --> 00:21:45,650
Usted necesita más memoria. Ahora necesito espacio para estos indicadores,

357
00:21:45,650 --> 00:21:47,900
y en el caso de esta super lista enlazada simple

358
00:21:47,900 --> 00:21:51,410
que sólo está tratando de almacenar enteros, que son 4 bytes, seguimos diciendo

359
00:21:51,410 --> 00:21:54,240
así, un puntero es de 4 bytes, por lo que ahora hemos duplicado literalmente

360
00:21:54,240 --> 00:21:57,290
la cantidad de memoria que necesita sólo para almacenar esta lista.

361
00:21:57,290 --> 00:21:59,680
Pero una vez más, se trata de un compromiso constante en la informática

362
00:21:59,680 --> 00:22:03,440
entre el tiempo y el espacio y el desarrollo, el esfuerzo y otros recursos.

363
00:22:03,440 --> 00:22:06,630
¿Cuál es otra desventaja de usar una lista enlazada? ¿Sí?

364
00:22:06,630 --> 00:22:10,150
[Respuesta Estudiantil, ininteligible]

365
00:22:10,150 --> 00:22:12,600
Bueno. No es tan fácil de acceder. Ya no podemos aprovechar

366
00:22:12,600 --> 00:22:15,530
semana 0 principios como dividir y conquistar.

367
00:22:15,530 --> 00:22:18,220
Y más específicamente, la búsqueda binaria. Porque a pesar de que los seres humanos

368
00:22:18,220 --> 00:22:20,400
puede ver más o menos donde la mitad de esta lista es,

369
00:22:20,400 --> 00:22:25,840
el equipo sólo sabe que esta lista enlazada comienza en la dirección llamado primero.

370
00:22:25,840 --> 00:22:28,250
Y eso es 0x123 o algo por el estilo.

371
00:22:28,250 --> 00:22:30,990
Y la única manera que el programa puede encontrar el elemento central

372
00:22:30,990 --> 00:22:33,350
en realidad es buscar toda la lista.

373
00:22:33,350 --> 00:22:35,500
Y aun así, literalmente, tiene que buscar en toda la lista porque

374
00:22:35,500 --> 00:22:38,950
incluso una vez que llegue el elemento central siguiendo los punteros,

375
00:22:38,950 --> 00:22:42,380
te, el programa, no tienen idea de cuánto tiempo esta lista es, en potencia,

376
00:22:42,380 --> 00:22:45,250
hasta llegar a la final de la misma, y ​​¿cómo saber programación

377
00:22:45,250 --> 00:22:48,600
que estamos al final de una lista enlazada?

378
00:22:48,600 --> 00:22:51,120
Hay un puntero NULL especial, por lo que una vez más, una convención.

379
00:22:51,120 --> 00:22:53,870
En lugar de utilizar este puntero, definitivamente no queremos que sea un valor basura

380
00:22:53,870 --> 00:22:57,750
apuntando en algún lugar fuera del escenario, queremos que sea la mano hacia abajo, NULL,

381
00:22:57,750 --> 00:23:01,530
así que tenemos este término en esta estructura de datos para que sepamos dónde termina.

382
00:23:01,530 --> 00:23:03,410
>> ¿Qué pasa si queremos manipular esto?

383
00:23:03,410 --> 00:23:05,980
Hicimos la mayor parte de esto visualmente, y con los seres humanos,

384
00:23:05,980 --> 00:23:07,630
pero lo que si queremos hacer una inserción?

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

386
00:23:12,360 --> 00:23:16,730
¿Y si luego quería malloc espacio para el número 55, un nodo para ello,

387
00:23:16,730 --> 00:23:20,730
y luego queremos insertar 55 en la lista al igual que hicimos el lunes?

388
00:23:20,730 --> 00:23:23,690
¿Cómo podemos hacer esto? Bueno, Anita se acercó y ella caminó esencialmente la lista.

389
00:23:23,690 --> 00:23:27,500
Ella comenzó en el primer elemento, luego el siguiente, el siguiente, el siguiente, el siguiente, el siguiente.

390
00:23:27,500 --> 00:23:29,500
Por último golpeó la mano izquierda hasta el fondo

391
00:23:29,500 --> 00:23:34,480
y se dio cuenta oh, este es NULL. Entonces, ¿qué manipulación de punteros que había que hacer?

392
00:23:34,480 --> 00:23:37,980
La persona que estaba en el extremo, número 34, necesitaba su mano izquierda levantada

393
00:23:37,980 --> 00:23:46,220
para señalar a los 55, 55 necesitaban su brazo izquierdo hacia abajo para ser el nuevo terminador NULL. Hecho.

394
00:23:46,220 --> 00:23:49,540
Bastante fácil de insertar 55 en una lista ordenada.

395
00:23:49,540 --> 00:23:51,800
¿Y cómo podría este aspecto?

396
00:23:51,800 --> 00:23:55,690
>> Déjenme seguir adelante y abrir algunos ejemplo de código aquí.

397
00:23:55,690 --> 00:23:58,120
Voy a abrir gedit, y me dejó abrir dos archivos primero.

398
00:23:58,120 --> 00:24:02,050
Uno de ellos es list1.h, y permítanme recordarles que este era el trozo de código

399
00:24:02,050 --> 00:24:04,920
que se utilizó para representar un nodo.

400
00:24:04,920 --> 00:24:13,040
Un nodo tiene tanto un llamado int n y un puntero próximo llamado que simplemente apunta a lo siguiente en la lista.

401
00:24:13,040 --> 00:24:15,450
Que se encuentra ahora en un archivo. H. ¿Por qué?

402
00:24:15,450 --> 00:24:19,090
Hay una convención, y no se han aprovechado de esto una cantidad enorme de nosotros mismos,

403
00:24:19,090 --> 00:24:22,220
pero la persona que escribió funciones printf y otros

404
00:24:22,220 --> 00:24:27,150
dio como regalo al mundo todas esas funciones al escribir un archivo llamado stdio.h.

405
00:24:27,150 --> 00:24:30,950
Y luego está string.h, y luego está Map.h, y no todos estos archivos h

406
00:24:30,950 --> 00:24:34,410
que se puede haber visto o utilizado durante el término escrito por otras personas.

407
00:24:34,410 --> 00:24:38,470
Normalmente, en los. Archivos h son únicas cosas como typedefs

408
00:24:38,470 --> 00:24:42,310
o declaraciones de tipos personalizados o declaraciones de constantes.

409
00:24:42,310 --> 00:24:47,890
No poner las implementaciones funciones 'en los archivos de cabecera.

410
00:24:47,890 --> 00:24:50,570
Se pone, en cambio, sólo sus prototipos.

411
00:24:50,570 --> 00:24:53,050
Pones las cosas que quieres compartir con el mundo lo que necesitan

412
00:24:53,050 --> 00:24:55,640
con el fin de compilar su código. Así que para entrar en este hábito,

413
00:24:55,640 --> 00:24:59,110
decidimos hacer lo mismo. No hay mucho en list1.h,

414
00:24:59,110 --> 00:25:02,070
pero hemos puesto algo que podría ser de interés para las personas en el mundo

415
00:25:02,070 --> 00:25:05,030
que quieren utilizar nuestra aplicación lista enlazada.

416
00:25:05,030 --> 00:25:08,040
Ahora, en list1.c, no voy a ir a través de todo este asunto

417
00:25:08,040 --> 00:25:11,390
porque es un poco largo, este programa, pero vamos a ejecutarlo realmente rápido en el indicador.

418
00:25:11,390 --> 00:25:15,720
Permítanme compilar list1, déjame a continuación, ejecute list1, y lo que veremos es

419
00:25:15,720 --> 00:25:18,070
hemos simulado un programa pequeño y sencillo aquí

420
00:25:18,070 --> 00:25:20,990
que va a permitir a mí para agregar y quitar los números de una lista.

421
00:25:20,990 --> 00:25:24,310
Así que vamos a seguir adelante y me escriba 3 para la opción de menú 3.

422
00:25:24,310 --> 00:25:27,880
Quiero insertar el número - de dejar hacer el primer número, que tenía 9 años,

423
00:25:27,880 --> 00:25:30,550
y ahora me dicen que la lista es ahora 9.

424
00:25:30,550 --> 00:25:33,760
Déjame ir adelante y hacerlo otra inserción, por lo que llegué a la opción de menú 3.

425
00:25:33,760 --> 00:25:36,760
¿A qué número desea insertar? 17.

426
00:25:36,760 --> 00:25:39,220
Intro. Y voy a hacer uno más.

427
00:25:39,220 --> 00:25:41,720
Permítanme introducir el número 22.

428
00:25:41,720 --> 00:25:45,850
Así que tenemos el comienzo de la lista enlazada que teníamos en forma de diapositivas hace un momento.

429
00:25:45,850 --> 00:25:48,740
¿Cómo es esta inserción sucediendo realmente?

430
00:25:48,740 --> 00:25:52,000
En efecto, 22 se encuentra ahora en el final de la lista.

431
00:25:52,000 --> 00:25:55,050
Así que la historia nos dice en el escenario el lunes y volver a tapar justo ahora

432
00:25:55,050 --> 00:25:57,460
en realidad debe estar sucediendo en el código.

433
00:25:57,460 --> 00:25:59,700
Vamos a echar un vistazo. Permítanme baje este archivo.

434
00:25:59,700 --> 00:26:01,720
Vamos a pasar por alto algunas de las funciones,

435
00:26:01,720 --> 00:26:05,630
pero vamos a ir a, por ejemplo, la función de inserción.

436
00:26:05,630 --> 00:26:11,720
>> Vamos a ver cómo hacemos para insertar un nuevo nodo en la lista enlazada.

437
00:26:11,720 --> 00:26:14,550
¿Dónde está la lista declarado? Bueno, vamos a recorrer todo el camino hasta la parte superior,

438
00:26:14,550 --> 00:26:19,970
y note que mi lista enlazada es esencialmente declarada como único puntero es NULL inicialmente.

439
00:26:19,970 --> 00:26:23,180
Así que estoy utilizando una variable global aquí, que en general hemos predicado contra

440
00:26:23,180 --> 00:26:25,280
porque hace que su código un poco complicado de mantener,

441
00:26:25,280 --> 00:26:29,080
es una especie de perezoso, por lo general, pero no es perezoso y no es malo y no es malo

442
00:26:29,080 --> 00:26:33,660
si solo propósito de su programa en la vida es para simular una lista enlazada.

443
00:26:33,660 --> 00:26:35,460
Que es exactamente lo que estamos haciendo.

444
00:26:35,460 --> 00:26:39,100
Así que en lugar de declarar esto en principal y luego tener que pasar a todas las funciones

445
00:26:39,100 --> 00:26:42,640
hemos escrito en este programa, en lugar realizar oh, vamos a hacerla global

446
00:26:42,640 --> 00:26:47,060
porque todo el propósito de este programa es demostrar una y sólo una lista enlazada.

447
00:26:47,060 --> 00:26:50,700
Así que se siente bien. Aquí están mis prototipos, y no vamos a ir a través de todos ellos,

448
00:26:50,700 --> 00:26:55,800
pero escribí una función de eliminación, una función de búsqueda, una función de inserción, y una función de desplazamiento.

449
00:26:55,800 --> 00:26:59,080
Pero ahora vamos a ir de nuevo a la función de inserción

450
00:26:59,080 --> 00:27:01,490
y ver cómo se trabaja aquí.

451
00:27:01,490 --> 00:27:09,940
Insert está en línea - aquí vamos.

452
00:27:09,940 --> 00:27:12,850
Insertar. Así que no tiene ningún argumento, porque vamos a pedir

453
00:27:12,850 --> 00:27:15,930
el usuario dentro de esta función para el número que desee insertar.

454
00:27:15,930 --> 00:27:19,410
Pero antes, nos preparamos para darles un poco de espacio.

455
00:27:19,410 --> 00:27:22,050
Esta es una especie de copiar y pegar desde el otro ejemplo.

456
00:27:22,050 --> 00:27:25,110
En ese caso, le estaban asignando un int, esta vez estamos asignando un nodo.

457
00:27:25,110 --> 00:27:27,910
Yo no me acuerdo cuántos bytes de un nodo es, pero eso está bien.

458
00:27:27,910 --> 00:27:30,460
Sizeof puede darse cuenta de eso por mí.

459
00:27:30,460 --> 00:27:33,340
Y ¿por qué estoy comprobando NULL en la línea 120?

460
00:27:33,340 --> 00:27:37,530
¿Qué podría salir mal en la línea 119? ¿Sí?

461
00:27:37,530 --> 00:27:40,530
[Respuesta Estudiantil, ininteligible]

462
00:27:40,530 --> 00:27:43,440
Bueno. Sólo podría darse el caso de que le he pedido demasiada memoria

463
00:27:43,440 --> 00:27:47,020
o que algo anda mal y el sistema operativo no tiene suficientes bytes para darme,

464
00:27:47,020 --> 00:27:50,640
por lo que señala tanto al devolver NULL, y si no comprueban que

465
00:27:50,640 --> 00:27:54,710
y yo ciegamente proceder a utilizar la dirección devuelta, puede ser NULL.

466
00:27:54,710 --> 00:27:58,400
Podría ser algún valor desconocido, no es una buena cosa a menos que yo -

467
00:27:58,400 --> 00:28:00,590
en realidad no será un valor desconocido. Puede ser NULL, por lo que no quiero

468
00:28:00,590 --> 00:28:02,550
para abusar de ella y arriesgarse a dereferencing ella.

469
00:28:02,550 --> 00:28:07,410
Si eso sucede, yo acabo de volver y vamos a fingir que no he tenido ningún recuerdo en absoluto.

470
00:28:07,410 --> 00:28:12,270
>> De lo contrario, le digo al usuario darme un número para insertar, que llamo nuestra getInt viejo amigo,

471
00:28:12,270 --> 00:28:15,530
y ésta era la nueva sintaxis se introdujo el lunes.

472
00:28:15,530 --> 00:28:20,320
'Newptr-> n' significa tomar la dirección que le dieron por malloc

473
00:28:20,320 --> 00:28:23,490
que representa el primer byte de un objeto nuevo nodo,

474
00:28:23,490 --> 00:28:26,860
y luego ir al campo llamado n.

475
00:28:26,860 --> 00:28:35,270
Una pregunta de la trivia poco: Esto es equivalente a lo que la línea más críptica de código?

476
00:28:35,270 --> 00:28:38,110
¿Cómo podría yo haber escrito esto? ¿Quieres tomar una puñalada?

477
00:28:38,110 --> 00:28:41,480
[Respuesta Estudiantil, ininteligible]

478
00:28:41,480 --> 00:28:44,870
Bueno. Usando el n., Pero no es tan simple como esto.

479
00:28:44,870 --> 00:28:47,090
¿Qué es lo primero que hacer? [Respuesta Estudiantil, ininteligible]

480
00:28:47,090 --> 00:28:52,730
Bueno. Tengo que hacer newptr.n *.

481
00:28:52,730 --> 00:28:55,610
Así que esto nos dice nuevo puntero es obviamente una dirección. ¿Por qué?

482
00:28:55,610 --> 00:28:59,520
Debido a que fue devuelto por malloc. El newptr * diciendo "ir allí"

483
00:28:59,520 --> 00:29:02,970
y luego una vez que estás allí, entonces usted puede utilizar el más familiar. n,

484
00:29:02,970 --> 00:29:05,730
pero esto sólo se ve un poco feo, sobre todo si los seres humanos se van a

485
00:29:05,730 --> 00:29:10,360
elaborar indicadores con flechas todo el tiempo, el mundo se ha estandarizado en esta notación flecha,

486
00:29:10,360 --> 00:29:12,320
que hace exactamente lo mismo.

487
00:29:12,320 --> 00:29:16,070
Por lo que sólo utilice la opción -> notación cuando la cosa de la izquierda es un puntero.

488
00:29:16,070 --> 00:29:18,790
De lo contrario, si se trata de una estructura real, utilice el n..

489
00:29:18,790 --> 00:29:25,800
Y luego esto: ¿Por qué inicializar newptr-> siguiente a NULL?

490
00:29:25,800 --> 00:29:28,610
No queremos que una mano izquierda colgando fuera de la final de la etapa.

491
00:29:28,610 --> 00:29:31,630
Queremos que apunta hacia abajo, lo que significa que al final de esta lista

492
00:29:31,630 --> 00:29:34,980
podría ser en este nodo, así que mejor asegurarse de que es NULL.

493
00:29:34,980 --> 00:29:38,460
Y, en general, la inicialización de las variables o de sus miembros de datos y estructuras

494
00:29:38,460 --> 00:29:40,470
a algo que es sólo una buena práctica.

495
00:29:40,470 --> 00:29:45,170
Dejar simplemente basura existen y seguirán existiendo generalmente te mete en problemas

496
00:29:45,170 --> 00:29:48,650
si usted se olvida de hacer algo en el futuro.

497
00:29:48,650 --> 00:29:51,590
>> Aquí hay unos pocos casos. Esto, de nuevo, es la función de inserción,

498
00:29:51,590 --> 00:29:54,930
y lo primero que comprobar es si la variable llamada en primer lugar,

499
00:29:54,930 --> 00:29:58,240
esa variable global es NULL, que significa que no hay lista enlazada.

500
00:29:58,240 --> 00:30:02,460
No hemos introducido ningún número, por lo que es trivial para insertar este número actual

501
00:30:02,460 --> 00:30:05,240
en la lista, ya que sólo pertenece al comienzo de la lista.

502
00:30:05,240 --> 00:30:08,100
Así que esto fue cuando Anita estaba de pie allí sola, pretendiendo

503
00:30:08,100 --> 00:30:11,390
no había nadie más por aquí en el escenario hasta que nos asignaron un nodo,

504
00:30:11,390 --> 00:30:13,940
entonces podría levantar la mano por primera vez,

505
00:30:13,940 --> 00:30:17,420
si todo el mundo había llegado a la etapa después de ella el lunes.

506
00:30:17,420 --> 00:30:22,900
Ahora aquí, este es un pequeño jaque que tengo que decir si el nuevo nodo de valor de n

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

508
00:30:27,370 --> 00:30:29,930
eso significa que hay una lista enlazada que ha comenzado.

509
00:30:29,930 --> 00:30:32,330
Hay por lo menos un nodo en la lista, pero este chico nuevo

510
00:30:32,330 --> 00:30:37,230
pertenece ante sí, así que tenemos que mover las cosas.

511
00:30:37,230 --> 00:30:43,450
En otras palabras, si la lista ha comenzado con sólo, digamos,

512
00:30:43,450 --> 00:30:48,100
sólo el número 17, que es el - en realidad, no podemos hacer esto más claramente.

513
00:30:48,100 --> 00:30:56,010
Si comenzamos nuestra historia con un puntero aquí se llama en primer lugar,

514
00:30:56,010 --> 00:30:59,870
y en un principio es NULL, y nos inserte el número 9,

515
00:30:59,870 --> 00:31:02,510
el número 9 pertenece claramente al comienzo de la lista.

516
00:31:02,510 --> 00:31:07,400
Así que vamos a pretender que sólo malloced la dirección o el número 9 y lo puso aquí.

517
00:31:07,400 --> 00:31:13,170
Si el primer es de 9 por defecto, el primer escenario hemos hablado sólo de medio punto que vamos a este tipo aquí,

518
00:31:13,170 --> 00:31:15,790
dejar esto como NULL, ahora tenemos el número 9.

519
00:31:15,790 --> 00:31:18,280
El siguiente número que desee insertar es de 17.

520
00:31:18,280 --> 00:31:22,420
17 pertenece por aquí, así que vamos a tener que hacer un poco de lógica paso a paso a través de este.

521
00:31:22,420 --> 00:31:26,060
Así que en su lugar, antes de hacer eso, vamos a suponer que queremos insertar el número 8.

522
00:31:26,060 --> 00:31:28,650
>> Así que, por conveniencia, voy a llamar aquí.

523
00:31:28,650 --> 00:31:30,760
Pero recuerde, malloc puede poner casi cualquier lugar.

524
00:31:30,760 --> 00:31:33,460
Pero por el bien de dibujo, lo voy a poner aquí.

525
00:31:33,460 --> 00:31:38,440
Así que pretender que acabo de asignar un nodo para el número 8, lo que es nulo por defecto.

526
00:31:38,440 --> 00:31:42,800
¿Y ahora qué tiene que pasar? Un par de cosas.

527
00:31:42,800 --> 00:31:47,090
Hemos hecho este error en el escenario el lunes en el que actualiza un puntero de este tipo,

528
00:31:47,090 --> 00:31:51,890
luego lo hizo, y luego afirmó - que han quedado huérfanos a todos los demás en el escenario.

529
00:31:51,890 --> 00:31:54,350
Porque puedo - el orden de las operaciones aquí es importante,

530
00:31:54,350 --> 00:31:58,760
porque ahora que hemos perdido este nodo 9, que es sólo una especie de flotar en el espacio.

531
00:31:58,760 --> 00:32:01,150
Así que esto no es el enfoque correcto del lunes.

532
00:32:01,150 --> 00:32:03,330
Primero tenemos que hacer algo más.

533
00:32:03,330 --> 00:32:06,280
El estado del mundo se ve así. Inicialmente, 8 ha sido asignada.

534
00:32:06,280 --> 00:32:10,550
¿Cuál sería una mejor manera de insertar 8?

535
00:32:10,550 --> 00:32:14,720
En lugar de actualizar este primer indicador, sólo actualizar este de aquí su lugar.

536
00:32:14,720 --> 00:32:17,720
Así que tenemos una línea de código que se va a convertir este carácter NULL

537
00:32:17,720 --> 00:32:22,020
en un indicador real que se señala en el nodo 9,

538
00:32:22,020 --> 00:32:27,970
y entonces con seguridad puede cambiar primero en señalar a este tipo aquí.

539
00:32:27,970 --> 00:32:31,330
Ahora tenemos una lista, una lista enlazada, de dos elementos.

540
00:32:31,330 --> 00:32:33,580
¿Y qué significa esto realmente se ven como aquí?

541
00:32:33,580 --> 00:32:36,900
Si nos fijamos en el código, observe que he hecho exactamente eso.

542
00:32:36,900 --> 00:32:41,970
He dicho newptr, y en esta historia, newptr señalaba a este tipo.

543
00:32:41,970 --> 00:32:45,520
>> Así que déjame sacar una cosa más, y yo debería haber dejado la habitación de un poco más de esto.

544
00:32:45,520 --> 00:32:48,540
Así que perdonar al pequeño dibujo diminuto.

545
00:32:48,540 --> 00:32:52,140
Este chico se llama newptr.

546
00:32:52,140 --> 00:32:57,940
Esa es la variable que declaramos unas pocas líneas antes, en línea - justo por encima de 25.

547
00:32:57,940 --> 00:33:03,430
Y está apuntando a 8. Así que cuando digo newptr-> siguiente, lo que significa ir a la estructura

548
00:33:03,430 --> 00:33:07,910
que está siendo apuntado por newptr, así que aquí estamos, ir allí.

549
00:33:07,910 --> 00:33:13,990
A continuación, en la flecha que está diciendo obtener el siguiente campo y haga el signo = está diciendo qué valor colocar allí?

550
00:33:13,990 --> 00:33:17,280
El valor que se encontraba en primer lugar; qué valor estaba en primer lugar?

551
00:33:17,280 --> 00:33:21,930
En primer lugar se señala en este nodo, por lo que significa esto ahora debe apuntar a este nodo.

552
00:33:21,930 --> 00:33:25,660
En otras palabras, aunque lo que parece un lío ridículo con mi letra,

553
00:33:25,660 --> 00:33:28,620
¿qué es una idea simple de mover sólo alrededor de estas flechas

554
00:33:28,620 --> 00:33:31,560
se traduce a código con sólo este trazador de líneas.

555
00:33:31,560 --> 00:33:38,110
Guarde lo que está en primer lugar en el siguiente campo y luego actualizar lo primero que realmente es.

556
00:33:38,110 --> 00:33:40,900
Vamos a seguir adelante y avance rápido a través de algo de esto,

557
00:33:40,900 --> 00:33:44,220
y que busque sólo en esta inserción cola por ahora.

558
00:33:44,220 --> 00:33:51,210
Supongamos que llego al punto en que me parece que el siguiente campo de un nodo es NULL.

559
00:33:51,210 --> 00:33:53,410
Y en este punto de la historia, un detalle que me estoy pasando por alto

560
00:33:53,410 --> 00:33:58,170
es que he introducido otro puntero hasta aquí en la línea 142, el puntero predecesor.

561
00:33:58,170 --> 00:34:01,320
Esencialmente, en este momento de la historia, una vez que la lista se hace larga,

562
00:34:01,320 --> 00:34:04,800
Yo como que tenga que caminar con dos dedos porque si voy demasiado lejos,

563
00:34:04,800 --> 00:34:08,219
Recuerdo que en una sola lista larga duración, no se puede volver atrás.

564
00:34:08,219 --> 00:34:13,659
Así que esta idea de predptr es mi dedo izquierdo, y newptr - no newptr.

565
00:34:13,659 --> 00:34:17,199
Otro indicador que está aquí es mi otro dedo, y yo soy sólo un poco de caminar en la lista.

566
00:34:17,199 --> 00:34:22,179
Es por eso que existe. Pero vamos a considerar sólo uno de los casos más simples aquí.

567
00:34:22,179 --> 00:34:26,620
Si el campo al lado de ese puntero es NULL, ¿cuál es la implicación lógica?

568
00:34:26,620 --> 00:34:30,840
Si usted está atravesando esta lista y te encuentras con un puntero NULL?

569
00:34:30,840 --> 00:34:35,780
Usted está en el final de la lista, por lo que el código para agregar este elemento a continuación, un adicional

570
00:34:35,780 --> 00:34:41,230
es un género de lo intuitivo tomará ese nodo cuya próxima puntero es NULL,

571
00:34:41,230 --> 00:34:46,120
así que esto es actualmente NULL, y cambiarlo, sin embargo, es la dirección del nuevo nodo.

572
00:34:46,120 --> 00:34:52,260
Así que estamos dibujando en el código de la flecha que dibujamos en el escenario por levantar la mano izquierda de una persona.

573
00:34:52,260 --> 00:34:54,070
>> Y el caso que voy a agitar las manos menos por ahora,

574
00:34:54,070 --> 00:34:58,020
sólo porque creo que es fácil perderse cuando lo hacemos en este tipo de entorno,

575
00:34:58,020 --> 00:35:00,600
es la comprobación de inserción en la parte media de la lista.

576
00:35:00,600 --> 00:35:03,220
Pero sólo intuitivamente, lo que debe suceder si usted quiere averiguar

577
00:35:03,220 --> 00:35:06,600
donde algún número debe colocarse en el centro es que tienes que caminar

578
00:35:06,600 --> 00:35:09,510
con más de un dedo, más de un puntero,

579
00:35:09,510 --> 00:35:12,920
averiguar donde debe estar por comprobar es el elemento <el actual,

580
00:35:12,920 --> 00:35:15,450
> La actual, y una vez que encuentre ese lugar,

581
00:35:15,450 --> 00:35:20,400
entonces usted tiene que hacer este tipo de juego de la cáscara en la que se mueven alrededor de los punteros con mucho cuidado.

582
00:35:20,400 --> 00:35:23,850
Y esa respuesta, si lo desea a la razón a través de esto en casa por su cuenta,

583
00:35:23,850 --> 00:35:28,340
se reduce sólo a estas dos líneas de código, pero el orden de las líneas es súper importante.

584
00:35:28,340 --> 00:35:31,390
Porque si se le cae la mano de alguien y levantar otra persona en el orden equivocado,

585
00:35:31,390 --> 00:35:34,580
una vez más, que podría terminar dejando huérfanos a la lista.

586
00:35:34,580 --> 00:35:39,500
Para resumir conceptualmente más, la inserción de la cola es relativamente sencillo.

587
00:35:39,500 --> 00:35:42,940
La inserción en la cabeza es también relativamente sencillo,

588
00:35:42,940 --> 00:35:45,580
pero hay que actualizar un puntero adicional en esta ocasión

589
00:35:45,580 --> 00:35:47,930
para exprimir el número 5 en la lista aquí,

590
00:35:47,930 --> 00:35:51,560
y luego introducirse en el medio implica un esfuerzo aún más,

591
00:35:51,560 --> 00:35:56,130
para insertar cuidadosamente el número 20 en su ubicación correcta,

592
00:35:56,130 --> 00:35:58,350
que es entre 17 y 22.

593
00:35:58,350 --> 00:36:02,700
Así que hay que hacer algo como tener el nuevo nodo de 20 puntos a 22,

594
00:36:02,700 --> 00:36:08,470
y, a continuación, puntero que nodo necesita ser actualizado por última?

595
00:36:08,470 --> 00:36:10,630
Es 17 que en realidad insertarlo.

596
00:36:10,630 --> 00:36:14,080
Así que de nuevo, voy a aplazar el código real para que la aplicación particular.

597
00:36:14,080 --> 00:36:17,280
>> A primera vista, es un poco abrumador, pero no deja de ser un bucle infinito

598
00:36:17,280 --> 00:36:21,770
que está lazo, lazo, lazo, lazo, y romper tan pronto como se golpeó el puntero NULL,

599
00:36:21,770 --> 00:36:24,590
momento en el que usted puede hacer la inserción requerida.

600
00:36:24,590 --> 00:36:30,960
Esto, entonces, es el representante código vinculado inserción lista.

601
00:36:30,960 --> 00:36:34,590
Eso fue un poco mucho, y se siente como que hemos resuelto un problema,

602
00:36:34,590 --> 00:36:36,940
pero hemos introducido un otro conjunto. Francamente, nos hemos pasado todo este tiempo

603
00:36:36,940 --> 00:36:40,540
en gran O y Ω y el tiempo de funcionamiento, tratando de resolver los problemas más rápidamente,

604
00:36:40,540 --> 00:36:43,270
y aquí estamos dando un gran paso hacia atrás, se siente.

605
00:36:43,270 --> 00:36:45,380
Y, sin embargo, si el objetivo es almacenar los datos,

606
00:36:45,380 --> 00:36:48,010
se siente como el Santo Grial, como dijimos el lunes, sería realmente

607
00:36:48,010 --> 00:36:50,470
para guardar las cosas al instante.

608
00:36:50,470 --> 00:36:53,930
>> En efecto, supongamos que hemos hecho la lista a un lado por un momento vinculado

609
00:36:53,930 --> 00:36:56,000
y que en vez introducido el concepto de una mesa.

610
00:36:56,000 --> 00:36:59,110
Y vamos a pensar en una mesa por un momento como una matriz.

611
00:36:59,110 --> 00:37:03,790
Esta matriz y este caso aquí tiene unos 26 elementos, del 0 al 25,

612
00:37:03,790 --> 00:37:07,940
y supongo que necesitaba un poco pedazo de almacenamiento para los nombres:

613
00:37:07,940 --> 00:37:10,350
Alice y Bob y Charlie y similares.

614
00:37:10,350 --> 00:37:12,880
Y se necesita algún tipo de estructura de datos para almacenar esos nombres.

615
00:37:12,880 --> 00:37:15,000
Bueno, podrías usar algo como una lista enlazada

616
00:37:15,000 --> 00:37:20,260
y se podía caminar por la lista de insertar Alice antes de que Bob y Charlie después de que Bob y así sucesivamente.

617
00:37:20,260 --> 00:37:23,850
Y, de hecho, si usted quiere ver un código como el que en un aparte,

618
00:37:23,850 --> 00:37:27,230
Sabemos que en list2.h, hacemos exactamente eso.

619
00:37:27,230 --> 00:37:30,610
No vamos a entrar a través de este código, pero esto es una variante del ejemplo primero

620
00:37:30,610 --> 00:37:34,640
que introduce una estructura que hayamos visto antes estudiante llamado,

621
00:37:34,640 --> 00:37:40,330
y entonces lo que realmente almacena en la lista enlazada es un puntero a una estructura estudiante

622
00:37:40,330 --> 00:37:44,520
en lugar de un número entero pequeño y sencillo, n.

623
00:37:44,520 --> 00:37:46,900
Así que darse cuenta de que hay código hay que implica cadenas reales,

624
00:37:46,900 --> 00:37:49,940
pero si el objetivo que nos ocupa realmente ahora es abordar el problema de la eficiencia,

625
00:37:49,940 --> 00:37:53,380
¿No sería bueno si se nos da un objeto llamado Alice,

626
00:37:53,380 --> 00:37:56,020
queremos ponerla en el lugar adecuado en una estructura de datos,

627
00:37:56,020 --> 00:37:58,860
se siente como que sería muy agradable para poner sólo Alice,

628
00:37:58,860 --> 00:38:01,180
cuyo nombre comienza con A, en la primera ubicación.

629
00:38:01,180 --> 00:38:05,270
Y Bob, cuyo nombre empieza por B, en la segunda ubicación.

630
00:38:05,270 --> 00:38:09,580
Con una matriz, o vamos a empezar a llamar a una mesa, una tabla hash en que,

631
00:38:09,580 --> 00:38:13,650
podemos hacer exactamente eso. Si nos dan un nombre como Alice,

632
00:38:13,650 --> 00:38:16,700
una cadena como Alice, ¿dónde poner A-l-i-c-e?

633
00:38:16,700 --> 00:38:20,540
Necesitamos un hueristic. Necesitamos una función para tomar alguna entrada como Alicia

634
00:38:20,540 --> 00:38:24,610
y devolver una respuesta: "Pon Alice en este lugar."

635
00:38:24,610 --> 00:38:28,720
Y esta función, este cuadro de negro, se va a llamar una función hash.

636
00:38:28,720 --> 00:38:32,330
>> Una función hash es algo que toma una entrada, como "Alice",

637
00:38:32,330 --> 00:38:38,080
y vuelve a la que, por lo general, la ubicación numérica en alguna estructura de datos donde Alice pertenece.

638
00:38:38,080 --> 00:38:40,830
En este caso, nuestra función de hash debe ser relativamente simple.

639
00:38:40,830 --> 00:38:47,510
Nuestra función hash debe decir, si se le da "Alice", que personaje me debe importar?

640
00:38:47,510 --> 00:38:55,660
La primera de ellas. Así que miro a [0], y luego me dicen si [0] es un personaje, devuelva el número 0.

641
00:38:55,660 --> 00:39:01,130
Si es B, devolverá 1. Si se trata de C, volver 2, y así sucesivamente.

642
00:39:01,130 --> 00:39:05,940
Todos índice 0, y que me permita insertar Alice y Bob y Charlie y así sucesivamente

643
00:39:05,940 --> 00:39:10,960
en esta estructura de datos. Pero hay un problema.

644
00:39:10,960 --> 00:39:13,060
¿Y si Anita viene otra vez?

645
00:39:13,060 --> 00:39:17,510
¿Dónde ponemos Anita? Su nombre también empieza con la letra A,

646
00:39:17,510 --> 00:39:20,330
y se siente como que hemos hecho un lío aún mayor de este problema.

647
00:39:20,330 --> 00:39:24,380
Ahora tenemos la inserción inmediata, inserción constante de tiempo, en una estructura de datos

648
00:39:24,380 --> 00:39:27,100
en vez de peor caso lineal,

649
00:39:27,100 --> 00:39:29,510
pero ¿qué podemos hacer con Anita en este caso?

650
00:39:29,510 --> 00:39:34,110
¿Cuáles son las dos opciones, ¿en serio? ¿Sí?

651
00:39:34,110 --> 00:39:37,410
[Respuesta Estudiantil, ininteligible] Bueno, por lo que podríamos tener otra dimensión.

652
00:39:37,410 --> 00:39:42,320
Eso es bueno. Así que podemos construir cosas en 3D como hablamos verbalmente el lunes.

653
00:39:42,320 --> 00:39:46,700
Podríamos añadir otro acceso aquí, pero supongo que no, estoy tratando de mantener esto simple.

654
00:39:46,700 --> 00:39:50,160
El objetivo general aquí es tener inmediato acceso en tiempo constante,

655
00:39:50,160 --> 00:39:52,170
de modo que está agregar demasiada complejidad.

656
00:39:52,170 --> 00:39:55,970
¿Cuáles son las otras opciones cuando se trata de insertar Anita en esta estructura de datos? ¿Sí?

657
00:39:55,970 --> 00:39:58,610
[Respuesta Estudiantil, ininteligible] Bueno. Así que nos podíamos mover todos los demás hacia abajo,

658
00:39:58,610 --> 00:40:03,040
como Charlie codazos por Bob y Alice, y luego ponemos Anita donde ella realmente quiere ser.

659
00:40:03,040 --> 00:40:05,660
>> Por supuesto, ahora, no hay un efecto secundario de esto.

660
00:40:05,660 --> 00:40:09,000
Esta estructura de datos es probablemente útil no porque queremos insertar la gente una vez

661
00:40:09,000 --> 00:40:11,250
sino porque queremos comprobar si estás allí más tarde

662
00:40:11,250 --> 00:40:13,600
si queremos imprimir todos los nombres en la estructura de datos.

663
00:40:13,600 --> 00:40:15,850
Vamos a hacer algo con estos datos con el tiempo.

664
00:40:15,850 --> 00:40:20,810
Así que ahora tengo clase de jodido Alice, que ya no está donde se supone que debe ser.

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

666
00:40:23,880 --> 00:40:26,060
Así que tal vez esta no es una idea tan buena.

667
00:40:26,060 --> 00:40:28,830
Pero en realidad, esta es una opción. Podríamos pasar a todo el mundo,

668
00:40:28,830 --> 00:40:32,240
o diablos, Anita llegó tarde al juego, ¿por qué no acaba de poner Anita

669
00:40:32,240 --> 00:40:35,870
aquí no, aquí no, aquí no, vamos a ponerla un poco más abajo en la lista.

670
00:40:35,870 --> 00:40:38,680
Pero el problema comienza a delegar de nuevo.

671
00:40:38,680 --> 00:40:41,630
Usted puede ser capaz de encontrar al instante Alice, basada en su nombre.

672
00:40:41,630 --> 00:40:44,320
Y Bob instante, y Charlie. Pero luego buscar Anita,

673
00:40:44,320 --> 00:40:46,360
y ya ves, hmm, Alice se encuentra en el camino.

674
00:40:46,360 --> 00:40:48,770
Bueno, déjame ver por debajo de Alice. Bob no es Anita.

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

676
00:40:51,850 --> 00:40:54,720
Y si continúa esa línea de la lógica hasta el final,

677
00:40:54,720 --> 00:41:00,690
¿cuál es el tiempo de ejecución del peor caso de encontrar o insertar Anita en esta nueva estructura de datos?

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

679
00:41:03,280 --> 00:41:06,280
Debido a que en el peor de los casos, no es Alice, Bob, Charlie. . .

680
00:41:06,280 --> 00:41:10,150
todo el camino a alguien que se llama "Y", por lo que sólo hay un lugar a la izquierda.

681
00:41:10,150 --> 00:41:13,950
Afortunadamente, no tenemos a nadie llamado "Z", así que pusimos Anita en la parte inferior.

682
00:41:13,950 --> 00:41:16,040
>> Realmente no hemos resuelto ese problema.

683
00:41:16,040 --> 00:41:19,890
Así que tal vez es necesario introducir esta tercera dimensión.

684
00:41:19,890 --> 00:41:22,230
Y resulta que, si estamos de introducir esta tercera dimensión,

685
00:41:22,230 --> 00:41:25,240
no podemos hacer esto perfectamente, pero el Santo Grial se va a conseguir

686
00:41:25,240 --> 00:41:28,370
constante de tiempo de inserción y las inserciones dinámicos de modo que

687
00:41:28,370 --> 00:41:30,960
no tenemos que codificar una matriz de tamaño 26.

688
00:41:30,960 --> 00:41:34,400
Podemos insertar tantos nombres como queramos, pero vamos a tomar nuestro hijo de 5 minutos de descanso aquí

689
00:41:34,400 --> 00:41:38,790
y luego hacerlo correctamente.

690
00:41:38,790 --> 00:41:46,020
Está bien. Puse la historia hasta bastante artificial no

691
00:41:46,020 --> 00:41:48,670
por la elección de Alice y Bob y Charlie y Anita,

692
00:41:48,670 --> 00:41:51,000
cuyo nombre fue, obviamente, va a chocar con Alice.

693
00:41:51,000 --> 00:41:54,120
Pero la pregunta que terminó el lunes con es cuán probable es

694
00:41:54,120 --> 00:41:56,370
que se podrían obtener este tipo de colisiones? En otras palabras,

695
00:41:56,370 --> 00:42:00,490
si empezamos a utilizar esta estructura tabular, que es en realidad una matriz,

696
00:42:00,490 --> 00:42:02,460
en este caso de 26 sitios,

697
00:42:02,460 --> 00:42:05,740
¿Y si en vez nuestras entradas están uniformemente distribuidos?

698
00:42:05,740 --> 00:42:09,620
No es artificialmente Alice y Bob y Charlie y David, y así sucesivamente por orden alfabético,

699
00:42:09,620 --> 00:42:12,380
está distribuida uniformemente sobre la A a la Z.

700
00:42:12,380 --> 00:42:15,220
>> Tal vez sólo tendremos que tener suerte y que no vamos a tener dos A o B de dos

701
00:42:15,220 --> 00:42:17,640
con una probabilidad muy alta, pero como alguien ha señalado,

702
00:42:17,640 --> 00:42:20,730
si se generalizó este problema y no hacer 0 a 25

703
00:42:20,730 --> 00:42:26,060
pero, por ejemplo, de 0 a 364 o 65 años, a menudo el número de días en un año típico,

704
00:42:26,060 --> 00:42:31,170
y la pregunta, "¿Cuál es la probabilidad de que dos de nosotros en esta sala tienen el mismo cumpleaños?"

705
00:42:31,170 --> 00:42:34,600
Dicho de otra manera, ¿cuál es la probabilidad de que dos de nosotros tiene un nombre que comienza con A?

706
00:42:34,600 --> 00:42:37,190
El tipo de pregunta es la misma, pero este espacio de direcciones,

707
00:42:37,190 --> 00:42:39,940
este espacio de búsqueda, es más grande en el caso de cumpleaños,

708
00:42:39,940 --> 00:42:42,820
porque tenemos más de tantos días en el año que las letras del alfabeto.

709
00:42:42,820 --> 00:42:44,910
¿Cuál es la probabilidad de una colisión?

710
00:42:44,910 --> 00:42:48,410
Bueno, podemos pensar en esto por averiguar las matemáticas en sentido contrario.

711
00:42:48,410 --> 00:42:50,580
¿Cuál es la probabilidad de colisiones no?

712
00:42:50,580 --> 00:42:53,970
Pues bien, esta expresión aquí dice que lo que es la probabilidad

713
00:42:53,970 --> 00:42:58,770
si hay una sola persona en este salón, que celebra su cumpleaños único?

714
00:42:58,770 --> 00:43:01,190
Es 100%. Porque si hay una sola persona en la habitación,

715
00:43:01,190 --> 00:43:03,940
su cumpleaños puede ser cualquiera de los 365 días del año.

716
00:43:03,940 --> 00:43:08,650
Así que las opciones de 365/365 me da un valor de 1.

717
00:43:08,650 --> 00:43:11,250
Así que la probabilidad de que se trate en el momento es sólo 1.

718
00:43:11,250 --> 00:43:13,270
Pero si hay una segunda persona en la habitación,

719
00:43:13,270 --> 00:43:16,490
¿cuál es la probabilidad de que su cumpleaños es diferente?

720
00:43:16,490 --> 00:43:20,680
Sólo hay 364 días posibles, haciendo caso omiso de los años bisiestos,

721
00:43:20,680 --> 00:43:23,580
para su cumpleaños no chocar con las otras personas.

722
00:43:23,580 --> 00:43:31,920
Así que 364/365. Si una tercera persona entra, es 363/365, y así sucesivamente.

723
00:43:31,920 --> 00:43:35,790
Así que seguimos multiplicando estas fracciones, que son cada vez más pequeños,

724
00:43:35,790 --> 00:43:40,720
para averiguar cuál es la probabilidad de que todos nosotros tenemos cumpleaños únicos?

725
00:43:40,720 --> 00:43:43,570
Pero podemos, por supuesto, acaba de tomar esa respuesta y darle la vuelta alrededor

726
00:43:43,570 --> 00:43:47,210
y hacer 1 menos todo eso, una expresión que finalmente va a conseguir

727
00:43:47,210 --> 00:43:51,250
si te acuerdas de la parte posterior de sus libros de matemáticas, se ve un poco de algo como esto,

728
00:43:51,250 --> 00:43:54,590
que es mucho más fácil de interpretar gráficamente.

729
00:43:54,590 --> 00:43:57,820
Y aquí tiene este gráfico en el eje x el número de cumpleaños,

730
00:43:57,820 --> 00:44:02,030
o el número de personas con cumpleaños, y sobre el eje y es la probabilidad de una coincidencia.

731
00:44:02,030 --> 00:44:06,060
Y lo que esto quiere decir es que si usted tiene, digamos, incluso,

732
00:44:06,060 --> 00:44:10,860
vamos a elegir algo así como 22, 23.

733
00:44:10,860 --> 00:44:13,160
Si hay 22 o 23 personas en la sala,

734
00:44:13,160 --> 00:44:17,100
la probabilidad de que dos de esas pocas personas van a tener el mismo cumpleaños

735
00:44:17,100 --> 00:44:19,560
en realidad es súper alta, combinatoria.

736
00:44:19,560 --> 00:44:23,450
50% de probabilidad de que en una clase de sólo 22 personas, un seminario, prácticamente,

737
00:44:23,450 --> 00:44:25,790
2 de esas personas van a tener el mismo cumpleaños.

738
00:44:25,790 --> 00:44:28,520
Porque hay muchas maneras en que usted puede tener el mismo cumpleaños.

739
00:44:28,520 --> 00:44:31,110
Peor aún, si nos fijamos en la parte derecha de la tabla,

740
00:44:31,110 --> 00:44:34,040
por el tiempo que tiene una clase con 58 estudiantes en el mismo,

741
00:44:34,040 --> 00:44:39,270
la probabilidad de que dos personas que tienen un alto cumpleaños es super, super, cerca del 100%.

742
00:44:39,270 --> 00:44:41,880
Ahora, eso es una especie de hecho de la diversión de la vida real.

743
00:44:41,880 --> 00:44:45,850
>> Pero las implicaciones, ahora, por las estructuras de datos y almacenamiento de información

744
00:44:45,850 --> 00:44:51,100
significa que sólo suponiendo que tiene un bonito, limpio distribución uniforme de los datos

745
00:44:51,100 --> 00:44:53,650
y tiene una amplia lo suficientemente grande para un montón de cosas

746
00:44:53,650 --> 00:44:59,360
no significa que usted va a hacer que la gente en lugares únicos.

747
00:44:59,360 --> 00:45:03,810
Vas a tener colisiones. Así que esta noción de hashing, como se le llama,

748
00:45:03,810 --> 00:45:07,450
teniendo una entrada como "Alice" y el masaje de alguna manera

749
00:45:07,450 --> 00:45:10,190
y luego volver a una respuesta como 0 ó 1 ó 2.

750
00:45:10,190 --> 00:45:17,500
Volviendo un poco de la salida de función que está plagada de esta probabilidad de colisión.

751
00:45:17,500 --> 00:45:19,530
¿Cómo podemos manejar esas colisiones?

752
00:45:19,530 --> 00:45:21,940
Pues bien, en el primer caso, podemos tomar la idea que se sugiere.

753
00:45:21,940 --> 00:45:25,100
Sólo podemos cambiar a todo el mundo, o tal vez, un poco más simple,

754
00:45:25,100 --> 00:45:29,870
en lugar de todo el mundo se mueven más, vamos a mover Anita a la parte inferior del sitio disponible.

755
00:45:29,870 --> 00:45:32,810
Así que si Alice se encuentra en 0, Bob está en 1, Charlie está en 2,

756
00:45:32,810 --> 00:45:35,260
sólo tendremos que poner Anita del punto 3.

757
00:45:35,260 --> 00:45:38,860
Y esta es una técnica en la estructura de datos llamada sondeo lineal.

758
00:45:38,860 --> 00:45:41,310
Lineal porque estás caminando esta línea, y usted es una especie de sondeo

759
00:45:41,310 --> 00:45:43,640
para los puntos disponibles en la estructura de datos.

760
00:45:43,640 --> 00:45:46,210
Por supuesto, esto se convirtiera en O (n).

761
00:45:46,210 --> 00:45:49,590
Si la estructura de datos es muy completo, hay 25 personas en lo que ya,

762
00:45:49,590 --> 00:45:54,120
y entonces Anita llega, ella termina en lo que sería la ubicación Z, y eso está bien.

763
00:45:54,120 --> 00:45:56,540
Ella todavía le queda, y podemos encontrarla más tarde.

764
00:45:56,540 --> 00:46:00,100
>> Pero esto es contrario al objetivo de acelerar las cosas.

765
00:46:00,100 --> 00:46:02,530
Entonces, ¿qué pasaría si en vez introducida esta tercera dimensión?

766
00:46:02,530 --> 00:46:06,400
Esta técnica se denomina generalmente encadenamiento separado, o que tiene cadenas.

767
00:46:06,400 --> 00:46:10,030
Y lo que una tabla hash es, esta estructura tabular,

768
00:46:10,030 --> 00:46:13,450
la tabla es sólo un conjunto de punteros.

769
00:46:13,450 --> 00:46:18,230
Pero lo que los punteros señalar es conjetura qué?

770
00:46:18,230 --> 00:46:21,970
Una lista enlazada. ¿Y qué si tomamos lo mejor de ambos mundos?

771
00:46:21,970 --> 00:46:26,500
Nosotros usamos arrays para los índices iniciales

772
00:46:26,500 --> 00:46:32,070
en la estructura de datos por lo que al instante se puede ir a [0] [1], [30] o así sucesivamente,

773
00:46:32,070 --> 00:46:36,480
pero para que tengamos un poco de flexibilidad y podemos encajar Anita y Alice y Adam

774
00:46:36,480 --> 00:46:38,630
y cualquier otro Un nombre,

775
00:46:38,630 --> 00:46:43,470
en lugar de dejar que el otro eje crecer arbitrariamente.

776
00:46:43,470 --> 00:46:47,340
Y por último, a partir del lunes, tienen esa capacidad expresiva con lista enlazada.

777
00:46:47,340 --> 00:46:49,530
Se puede cultivar una estructura de datos arbitraria.

778
00:46:49,530 --> 00:46:52,450
Como alternativa, podríamos hacer una enorme variedad 2-dimensional,

779
00:46:52,450 --> 00:46:57,190
pero eso va a ser una situación terrible si una de las filas de una matriz 2-dimensional

780
00:46:57,190 --> 00:47:01,280
no es lo suficientemente grande como para que la persona adicional cuyo nombre pasa a comenzar con A.

781
00:47:01,280 --> 00:47:04,200
Dios nos libre de tener que reasignar un enorme 2-dimensional estructura

782
00:47:04,200 --> 00:47:06,600
sólo porque hay tantas personas nombradas A,

783
00:47:06,600 --> 00:47:09,480
especialmente cuando hay tan pocas personas nombradas algo Z.

784
00:47:09,480 --> 00:47:12,170
Es sólo va a ser una estructura de datos muy escasos.

785
00:47:12,170 --> 00:47:15,400
Así que no es perfecto, por cualquier medio, pero ahora al menos tenemos la capacidad

786
00:47:15,400 --> 00:47:19,090
para encontrar al instante en que Alice o Anita pertenece,

787
00:47:19,090 --> 00:47:21,090
al menos en términos del eje vertical,

788
00:47:21,090 --> 00:47:25,850
y entonces sólo tenemos que decidir dónde poner Anita o Alicia en el país de esta lista vinculada.

789
00:47:25,850 --> 00:47:32,480
Si no se preocupan por resolver las cosas, con qué rapidez podemos insertar Alice en una estructura como esta?

790
00:47:32,480 --> 00:47:35,370
Es tiempo constante. Nos índice en [0], y si no hay uno,

791
00:47:35,370 --> 00:47:37,550
Alice va al comienzo de la lista vinculada.

792
00:47:37,550 --> 00:47:40,000
Pero eso no es un gran negocio. Porque si Anita luego viene

793
00:47:40,000 --> 00:47:42,160
un cierto número de pasos más adelante, ¿de dónde Anita pertenece?

794
00:47:42,160 --> 00:47:45,140
Bueno, [0]. Programación orientada a objetos. Alice se encuentra en esa lista enlazada.

795
00:47:45,140 --> 00:47:47,760
>> Pero si no te importa la clasificación de estos nombres,

796
00:47:47,760 --> 00:47:53,580
que sólo puede moverse a través de Alice, insertar Anita, pero incluso eso es la constante de tiempo.

797
00:47:53,580 --> 00:47:57,010
Incluso si no hay Alice y Adam y todos estos otros nombres A,

798
00:47:57,010 --> 00:47:59,410
en realidad no es que cambiando físicamente. ¿Por qué?

799
00:47:59,410 --> 00:48:04,090
Debido a que acabamos de hacer aquí con lista enlazada, quién sabe fueron estos nodos son de todos modos?

800
00:48:04,090 --> 00:48:06,550
Todo lo que tienes que hacer es mover el pan rallado.

801
00:48:06,550 --> 00:48:10,930
Mueva las flechas alrededor, usted no tiene que mover físicamente los datos alrededor.

802
00:48:10,930 --> 00:48:14,610
Así que podemos insertar Anita, en ese caso, al instante. Constante de tiempo.

803
00:48:14,610 --> 00:48:20,250
Así que tenemos tiempo constante de búsqueda, y la constante de tiempo de inserción de alguien como Anita.

804
00:48:20,250 --> 00:48:22,740
Pero especie de simplificar en exceso el mundo.

805
00:48:22,740 --> 00:48:28,510
¿Y si más adelante desea encontrar a Alice?

806
00:48:28,510 --> 00:48:31,050
¿Y si más adelante desea encontrar a Alice?

807
00:48:31,050 --> 00:48:35,690
¿Cuántos pasos se que va a tomar?

808
00:48:35,690 --> 00:48:37,850
[Respuesta Estudiantil, ininteligible]

809
00:48:37,850 --> 00:48:40,950
Exactamente. El número de personas antes de que Alicia en el país de la lista enlazada.

810
00:48:40,950 --> 00:48:45,420
Así que no es del todo perfecto, porque nuestra estructura de datos, una vez más, tiene este acceso vertical

811
00:48:45,420 --> 00:48:50,240
y entonces tiene estas listas enlazadas que cuelgan - en realidad, no hay que dibujarlo una matriz.

812
00:48:50,240 --> 00:48:56,020
Ha estas listas enlazadas colgando de ella que se parece un poco algo como esto.

813
00:48:56,020 --> 00:48:59,110
Pero el problema es que si Alice y Adam y todos estos otros nombres un

814
00:48:59,110 --> 00:49:01,720
terminan más y más allá,

815
00:49:01,720 --> 00:49:04,810
encontrar a alguien podría acabar teniendo un montón de pasos,

816
00:49:04,810 --> 00:49:06,670
bcause tienes que recorrer la lista enlazada,

817
00:49:06,670 --> 00:49:08,090
que es una operación lineal.

818
00:49:08,090 --> 00:49:14,270
Así que en realidad, entonces, el tiempo de inserción en última instancia es O (n), donde n es el número de elementos en la lista.

819
00:49:14,270 --> 00:49:21,780
Dividido por, vamos arbitrariamente llamamos m, donde m es el número de listas enlazadas

820
00:49:21,780 --> 00:49:24,500
que tenemos en este eje vertical.

821
00:49:24,500 --> 00:49:27,180
En otras palabras, si realmente suponen una distribución uniforme de los nombres,

822
00:49:27,180 --> 00:49:30,150
totalmente irreal. Obviamente hay más de unas cartas que otros.

823
00:49:30,150 --> 00:49:32,580
>> Pero si suponemos por el momento una distribución uniforme,

824
00:49:32,580 --> 00:49:37,350
y tenemos n personas en total, y las cadenas de m totales

825
00:49:37,350 --> 00:49:40,630
disponibles para nosotros, entonces la longitud de cada una de estas cadenas

826
00:49:40,630 --> 00:49:44,380
bastante simplemente va a ser el total, n dividido por el número de cadenas.

827
00:49:44,380 --> 00:49:48,900
Entonces n / m. Pero aquí es donde podemos ser matemáticamente todo listo.

828
00:49:48,900 --> 00:49:53,030
m es una constante, ya que hay un número fijo de éstos.

829
00:49:53,030 --> 00:49:54,620
Usted va a declarar el array al principio,

830
00:49:54,620 --> 00:49:58,450
y no estamos cambiando el tamaño del eje vertical. Por definición, que permanece fijo.

831
00:49:58,450 --> 00:50:01,220
Es sólo el eje horizontal, por así decirlo, eso está cambiando.

832
00:50:01,220 --> 00:50:04,760
Así que, técnicamente, es una constante. Así que ahora, el tiempo de inserción

833
00:50:04,760 --> 00:50:09,700
es más o menos O (n).

834
00:50:09,700 --> 00:50:12,410
Así que no se siente todo lo que mucho mejor.

835
00:50:12,410 --> 00:50:14,940
Pero, ¿qué es la verdad? Bueno, todo este tiempo, durante semanas,

836
00:50:14,940 --> 00:50:20,640
que hemos estado diciendo O (n ²). O (n), 2 x n ², - n, dividido por 2. . . ech.

837
00:50:20,640 --> 00:50:23,580
Es sólo ² n. Pero ahora, en esta parte del semestre,

838
00:50:23,580 --> 00:50:25,560
podemos empezar a hablar sobre el mundo real otra vez.

839
00:50:25,560 --> 00:50:31,520
Y n / m es absolutamente más rápido que sólo n solo.

840
00:50:31,520 --> 00:50:35,170
Si usted tiene mil nombres, y les rompen en cubos múltiples

841
00:50:35,170 --> 00:50:37,820
de modo que sólo tiene diez nombres en cada una de estas cadenas,

842
00:50:37,820 --> 00:50:41,670
buscando absolutamente diez cosas que va a ser más rápido que un millar de cosas.

843
00:50:41,670 --> 00:50:43,740
Y así, uno de los conjuntos de problemas futuros va a desafiar

844
00:50:43,740 --> 00:50:46,100
a pensar exactamente que a pesar de que, sí,

845
00:50:46,100 --> 00:50:49,520
asintóticamente y matemáticamente, esto es sólo lineal,

846
00:50:49,520 --> 00:50:51,700
que aspira, en general, cuando se trata de encontrar las cosas.

847
00:50:51,700 --> 00:50:54,530
En realidad, va a ser más rápido que el

848
00:50:54,530 --> 00:50:56,520
porque de este divisor.

849
00:50:56,520 --> 00:50:58,310
Así que hay de nuevo va a ser este trade-off

850
00:50:58,310 --> 00:51:01,390
y este conflicto entre la teoría y la realidad,

851
00:51:01,390 --> 00:51:03,550
y uno de los mandos comenzará a girar en este punto en el semestre

852
00:51:03,550 --> 00:51:07,510
es más bien la única realidad como una especie de preparación para la final semster,

853
00:51:07,510 --> 00:51:09,280
como se presenta el mundo de la programación web,

854
00:51:09,280 --> 00:51:11,530
donde realmente, el rendimiento va a contar porque los usuarios van a

855
00:51:11,530 --> 00:51:14,880
comienza a sentir y apreciar las malas decisiones de diseño.

856
00:51:14,880 --> 00:51:19,950
>> Entonces, ¿cómo usted va sobre la implementación de un vinculado - una tabla hash con 31 elementos?

857
00:51:19,950 --> 00:51:22,600
Y el ejemplo anterior fue arbitrariamente los cumpleaños.

858
00:51:22,600 --> 00:51:26,190
Si alguien tiene un cumpleaños el 1 de enero o el 1 de febrero, las pondremos en este cubo.

859
00:51:26,190 --> 00:51:28,960
Si se trata de 02 de enero, 2 de febrero, 2 de marzo, los vamos a poner en este cubo.

860
00:51:28,960 --> 00:51:32,220
Es por eso que tenía 31 años. ¿Cómo se declara una tabla hash?

861
00:51:32,220 --> 00:51:37,480
Puede ser muy simple, mesa * nodo es mi nombre arbitrario para él, [31].

862
00:51:37,480 --> 00:51:42,400
Esto me da 31 punteros a nodos,

863
00:51:42,400 --> 00:51:45,370
y que me permite tener 31 punteros a listas enlazadas

864
00:51:45,370 --> 00:51:48,800
incluso si esas cadenas son inicialmente NULL.

865
00:51:48,800 --> 00:51:54,860
¿Qué es lo que quiero hacer si quiero guardar "Alice", "Bob", "Charlie"?

866
00:51:54,860 --> 00:51:57,010
Bueno, tenemos que envolver las cosas en una estructura

867
00:51:57,010 --> 00:52:00,530
porque necesitamos Alice para que apunte a Bob, para que apunte a Charlie, y así sucesivamente.

868
00:52:00,530 --> 00:52:04,940
No podemos tener los nombres solos, por lo que podría crear una nueva estructura llamada nodo aquí.

869
00:52:04,940 --> 00:52:08,310
>> ¿Qué es un nodo real? ¿Qué es un nodo en esta nueva lista ligada?

870
00:52:08,310 --> 00:52:11,840
Lo primero, llamado palabra, es el nombre de la persona.

871
00:52:11,840 --> 00:52:14,340
LONGITUD, presumiblemente, se refiere a la longitud máxima del nombre de un ser humano,

872
00:52:14,340 --> 00:52:18,210
sea ​​lo que sea, 20, 30, 40 personajes en casos extremos locos,

873
00:52:18,210 --> 00:52:22,680
y uno es para qué? Es sólo el carácter NULL extra, \ 0.

874
00:52:22,680 --> 00:52:27,410
Así que este nodo está terminando "algo" dentro de sí misma,

875
00:52:27,410 --> 00:52:29,640
sino que también declara un puntero llamado próximo

876
00:52:29,640 --> 00:52:32,580
para que podamos cadena Alice a Bob a Charlie y así sucesivamente.

877
00:52:32,580 --> 00:52:36,700
Puede ser NULL, pero no necesariamente tiene que ser.

878
00:52:36,700 --> 00:52:40,110
Cualquier pregunta sobre estas tablas hash? ¿Sí?

879
00:52:40,110 --> 00:52:46,190
[Estudiante que hace la pregunta, ininteligible] Matriz - buena pregunta.

880
00:52:46,190 --> 00:52:50,120
¿Por qué es esta palabra char en una matriz en lugar de sólo char *?

881
00:52:50,120 --> 00:52:53,830
En este ejemplo un tanto arbitrario, no quiero tener que recurrir

882
00:52:53,830 --> 00:52:56,190
a malloc para cada uno de los nombres originales.

883
00:52:56,190 --> 00:52:59,530
Yo quería declarar una cantidad máxima de memoria para la cadena

884
00:52:59,530 --> 00:53:06,020
para que yo pudiera copiar en la estructura Alice \ 0 y no tener que lidiar con malloc y libre y similares.

885
00:53:06,020 --> 00:53:11,710
Pero podría hacerlo si quería ser más conscientes del uso del espacio. Buena pregunta.

886
00:53:11,710 --> 00:53:14,780
Así que vamos a tratar de generalizar lejos de este

887
00:53:14,780 --> 00:53:18,350
y enfocar el resto de hoy en estructuras de datos más generalmente

888
00:53:18,350 --> 00:53:21,170
y otros problemas que se pueden resolver utilizando los mismos fundamentos

889
00:53:21,170 --> 00:53:24,590
a pesar de que las estructuras de datos se pueden diferir en sus pormenores.

890
00:53:24,590 --> 00:53:27,910
>> Así que resulta en ciencias de la computación, los árboles son muy comunes.

891
00:53:27,910 --> 00:53:29,760
Y se puede pensar en una especie de árbol como un árbol genealógico,

892
00:53:29,760 --> 00:53:31,830
donde hay algunas raíces, algunos matriarca o patriarca,

893
00:53:31,830 --> 00:53:34,540
abuela o el abuelo o la espalda antes,

894
00:53:34,540 --> 00:53:38,880
debajo de la cual son mamá y papá o hermanos diferentes o similares.

895
00:53:38,880 --> 00:53:42,500
Así que una estructura de árbol tiene nodos y tiene hijos,

896
00:53:42,500 --> 00:53:45,260
normalmente 0 o más hijos de cada nodo.

897
00:53:45,260 --> 00:53:47,320
Y algunos de la jerga que usted ve en este dibujo aquí

898
00:53:47,320 --> 00:53:50,630
es cualquiera de los hijos o nietos pequeños en los bordes

899
00:53:50,630 --> 00:53:52,330
que no tienen flechas que emanan de ellos,

900
00:53:52,330 --> 00:53:55,070
esas son las hojas llamados, y cualquier persona en el interior

901
00:53:55,070 --> 00:53:58,790
es un nodo interno, se le puede llamar cualquier cosa por el estilo.

902
00:53:58,790 --> 00:54:01,430
Sin embargo, esta estructura es bastante común. Éste es un poco arbitraria.

903
00:54:01,430 --> 00:54:04,930
Tenemos un niño de la izquierda, tenemos tres hijos a la derecha,

904
00:54:04,930 --> 00:54:06,830
dos niños en la parte inferior izquierda.

905
00:54:06,830 --> 00:54:10,740
Así que podemos tener diferentes árboles de tamaño, pero si empezamos a normalizar las cosas,

906
00:54:10,740 --> 00:54:15,330
y se puede recordar este vídeo de Patricio, en la búsqueda binaria de un corto anterior

907
00:54:15,330 --> 00:54:19,490
búsqueda en línea, binario no tiene que ser implementado con una matriz

908
00:54:19,490 --> 00:54:21,410
o trozos de papel en una pizarra.

909
00:54:21,410 --> 00:54:25,490
Supongamos que desea almacenar los números en una estructura de datos más sofisticada.

910
00:54:25,490 --> 00:54:27,680
Se puede crear un árbol como éste.

911
00:54:27,680 --> 00:54:35,290
Podría tener un nodo declara en C, y que el nodo puede tener al menos dos elementos de su interior.

912
00:54:35,290 --> 00:54:39,470
Uno de ellos es el número que desea almacenar, y el otro es - bueno, necesitamos uno más.

913
00:54:39,470 --> 00:54:41,540
Los otros son sus hijos.

914
00:54:41,540 --> 00:54:45,150
Así que aquí está otra estructura de datos. Esta vez, un nodo se define como el almacenamiento de un número n

915
00:54:45,150 --> 00:54:49,060
y luego dos punteros, hijo izquierdo y el hijo derecho.

916
00:54:49,060 --> 00:54:52,100
Y no son arbitrarias. Lo que es interesante acerca de este árbol?

917
00:54:52,100 --> 00:55:00,550
>> ¿Cuál es el patrón en la forma en que hemos establecido esto o cómo Patrick se presenta en su video?

918
00:55:00,550 --> 00:55:02,790
Es bastante obvio que hay una clasificación que pasa aquí,

919
00:55:02,790 --> 00:55:04,460
pero ¿cuál es la regla simple? ¿Sí?

920
00:55:04,460 --> 00:55:08,350
[Respuesta Estudiantil, ininteligible]

921
00:55:08,350 --> 00:55:12,040
Perfecto. Si usted echa un vistazo a esto, verá los números pequeños a la izquierda,

922
00:55:12,040 --> 00:55:14,690
los grandes números de la izquierda, pero eso es cierto para cada nodo.

923
00:55:14,690 --> 00:55:20,370
Para cada nodo, su hijo izquierdo menor que él, y su hijo mayor derecho que él.

924
00:55:20,370 --> 00:55:25,210
Lo que esto significa es que si quiero buscar en esta estructura de datos para, por ejemplo, el número 44,

925
00:55:25,210 --> 00:55:29,320
Tengo que empezar desde la raíz, porque al igual que con todas estas estructuras de datos más complejas ahora,

926
00:55:29,320 --> 00:55:31,910
sólo tenemos un puntero a una sola cosa, el principio.

927
00:55:31,910 --> 00:55:35,010
Y en este caso, el principio es la raíz. No es el extremo izquierdo,

928
00:55:35,010 --> 00:55:39,530
que es la raíz de esta estructura. Así que veo aquí es de 55 años, y estoy buscando 44.

929
00:55:39,530 --> 00:55:41,430
En qué dirección quiero ir?

930
00:55:41,430 --> 00:55:45,680
Bueno, yo quiero ir a la izquierda, porque, obviamente, a la derecha va a ser demasiado grande.

931
00:55:45,680 --> 00:55:49,050
Así que notar aquí, estás de suerte conceptualmente cortar el árbol por la mitad

932
00:55:49,050 --> 00:55:51,700
porque nunca vas abajo a la derecha.

933
00:55:51,700 --> 00:55:55,410
Así que ahora me iré de la 55 a la 33. Es demasiado pequeño de un número.

934
00:55:55,410 --> 00:56:01,590
Estoy buscando a 44, pero ahora sé que si 44 es en este árbol, puedo ir, obviamente, a la derecha.

935
00:56:01,590 --> 00:56:04,460
Así que de nuevo, estoy podando el árbol por la mitad.

936
00:56:04,460 --> 00:56:06,780
Es casi idéntico conceptualmente a la guía telefónica.

937
00:56:06,780 --> 00:56:09,510
Es idéntico a lo que hicimos con los papeles en la pizarra,

938
00:56:09,510 --> 00:56:13,940
pero es una estructura más sofisticada que nos permite hacer realidad

939
00:56:13,940 --> 00:56:16,880
este divide y vencerás por diseño del algoritmo,

940
00:56:16,880 --> 00:56:19,420
y, de hecho, que atraviesa una estructura como esta - gritos.

941
00:56:19,420 --> 00:56:22,870
Atravesando una estructura como esta, donde es sólo "ir por este camino o ir por ese camino"

942
00:56:22,870 --> 00:56:26,870
significa todo el código que se inclinó a su mente en un primer momento, al ponerla en la sección

943
00:56:26,870 --> 00:56:31,270
o caminar a través de él en casa, para la búsqueda binaria, utilizando recursión o iteración,

944
00:56:31,270 --> 00:56:35,060
es un dolor en el cuello. Busque el elemento central, a continuación, hacer su redondeo hacia arriba o hacia abajo.

945
00:56:35,060 --> 00:56:39,230
>> Hay una belleza en esto porque ahora podemos utilizar la recursividad de nuevo,

946
00:56:39,230 --> 00:56:43,760
pero mucho más limpia. De hecho, si usted está en el número 55 y que desea encontrar 44,

947
00:56:43,760 --> 00:56:48,450
usted va a la izquierda en este caso, entonces, ¿qué hace usted? Usted corre el mismo algoritmo exacto.

948
00:56:48,450 --> 00:56:51,560
Se comprueba el valor del nodo, vaya a la izquierda oa la derecha.

949
00:56:51,560 --> 00:56:53,670
A continuación, compruebe el valor del nodo, vaya a la izquierda oa la derecha.

950
00:56:53,670 --> 00:56:56,710
Esto se adapta perfectamente a la recursividad.

951
00:56:56,710 --> 00:57:00,920
Así que, aunque en el pasado hemos hecho algunos ejemplos bastante arbitrarias que implican recursión

952
00:57:00,920 --> 00:57:03,430
que no tenía por qué ser recursivo, con stuctures de datos,

953
00:57:03,430 --> 00:57:07,820
especialmente los árboles, es una perfecta aplicación de esta idea de tener un problema,

954
00:57:07,820 --> 00:57:12,920
contracción, y luego resolver el mismo tipo de, pero más pequeño programa,.

955
00:57:12,920 --> 00:57:14,590
>> Así que hay otra estructura de datos que podemos introducir.

956
00:57:14,590 --> 00:57:18,760
Éste está diseñado a primera vista, parecer críptico, pero esto es increíble.

957
00:57:18,760 --> 00:57:25,090
Así que esta es una estructura de datos llamada trie, trie, que se hereda de la recuperación de palabras,

958
00:57:25,090 --> 00:57:30,210
que no se pronuncia re-try-val, pero eso es lo que el mundo llama a estas cosas. Trata. T-r-i-e.

959
00:57:30,210 --> 00:57:35,190
Se trata de una estructura de árbol de algún tipo, pero cada uno de los nodos en un trie

960
00:57:35,190 --> 00:57:41,280
parece ser qué? Y esto es un poco engañoso, ya que es una especie de abreviado.

961
00:57:41,280 --> 00:57:45,960
Pero parece que cada nodo en este trie es en realidad una matriz.

962
00:57:45,960 --> 00:57:48,840
Y a pesar de que el autor de este diagrama no lo ha demostrado,

963
00:57:48,840 --> 00:57:54,130
en este caso, este trie es una estructura de datos cuyo propósito en la vida es para almacenar palabras

964
00:57:54,130 --> 00:57:57,330
como A-l-i-c-e o B-o b-.

965
00:57:57,330 --> 00:58:02,480
Y la forma en que estos datos almacena Alice y Bob y Charlie y Anita y demás

966
00:58:02,480 --> 00:58:06,970
Se utiliza una matriz para almacenar el cual Alicia en el país de un trie,

967
00:58:06,970 --> 00:58:09,820
se comienza en el nodo raíz que se parece a una matriz,

968
00:58:09,820 --> 00:58:12,080
y que ha sido escrito en notación abreviada.

969
00:58:12,080 --> 00:58:15,070
El autor omite abcdefg porque no había nombres con eso.

970
00:58:15,070 --> 00:58:19,150
Ellos sólo mostró M y P y T, pero en este caso,

971
00:58:19,150 --> 00:58:22,780
vamos a pasar lejos de Alice y Bob y Charlie a algunos nombres que están aquí.

972
00:58:22,780 --> 00:58:25,670
Maxwell es en realidad en este diagrama.

973
00:58:25,670 --> 00:58:29,570
Entonces, ¿cómo hizo el autor tienda M-a-x-w-e-l-l?

974
00:58:29,570 --> 00:58:36,990
Él o ella empezó en el nodo raíz, y se fue a [M], de modo más o menos 13, la 13 ª posición en la matriz.

975
00:58:36,990 --> 00:58:40,750
Luego, desde allí, hay un puntero.

976
00:58:40,750 --> 00:58:42,760
Un puntero que lleva a otra matriz.

977
00:58:42,760 --> 00:58:47,880
A partir de ahí el autor indexada en esa matriz en la posición A, como se muestra en la parte superior izquierda hay,

978
00:58:47,880 --> 00:58:52,250
y entonces él o ella siguió a ese puntero a otra matriz,

979
00:58:52,250 --> 00:58:55,460
y se fue al puntero en la ubicación X.

980
00:58:55,460 --> 00:58:59,840
Luego, en la siguiente ubicación matriz W, E, L, L, y así sucesivamente,

981
00:58:59,840 --> 00:59:03,090
y, por último, vamos a tratar de poner en realidad una imagen a esta.

982
00:59:03,090 --> 00:59:05,380
¿Cómo es un nodo como en el código?

983
00:59:05,380 --> 00:59:11,820
Un nodo en un trie contiene una matriz de punteros a más nodos.

984
00:59:11,820 --> 00:59:16,090
Pero también hay que ser algún tipo de valor booleano, por lo menos en esta implementación.

985
00:59:16,090 --> 00:59:18,770
Sucede que me llaman is_word. ¿Por qué?

986
00:59:18,770 --> 00:59:22,670
Porque cuando vas a insertar Maxwell, usted no está insertando

987
00:59:22,670 --> 00:59:25,300
nada en esta estructura de datos.

988
00:59:25,300 --> 00:59:27,480
No estás escribiendo M. No estás escribiendo X.

989
00:59:27,480 --> 00:59:30,240
Todo lo que estamos haciendo es seguir punteros.

990
00:59:30,240 --> 00:59:33,360
El puntero que representa M, entonces el puntero que representa A,

991
00:59:33,360 --> 00:59:36,310
a continuación, el puntero que representa X, entonces W, E, L, L,

992
00:59:36,310 --> 00:59:41,950
pero lo que hay que hacer al final es una especie de ir, pasar, llegué a este lugar.

993
00:59:41,950 --> 00:59:45,560
Había una palabra que termina aquí, en la estructura de datos.

994
00:59:45,560 --> 00:59:48,190
>> Entonces, ¿qué es realmente un trie llena y el autor eligió para representar

995
00:59:48,190 --> 00:59:51,880
estas estaciones terminales con pequeños triángulos.

996
00:59:51,880 --> 00:59:56,470
Esto sólo significa que el hecho de este triángulo está aquí, este valor booleano de true

997
00:59:56,470 --> 00:59:59,200
significa que si usted va hacia atrás en el árbol,

998
00:59:59,200 --> 01:00:02,420
lo que significa una palabra llamada Maxwell está en esto.

999
01:00:02,420 --> 01:00:04,870
Pero la palabra foo, por ejemplo,

1000
01:00:04,870 --> 01:00:07,970
no está en el árbol, porque si me pongo en el nodo raíz hasta aquí en la parte superior,

1001
01:00:07,970 --> 01:00:14,030
No hay ningún indicador f, o no puntero, puntero o no. Foo no es un nombre en este diccionario.

1002
01:00:14,030 --> 01:00:22,460
Pero por el contrario, Turing, t-u-r-i-n-g. Una vez más, no almacenar o u t o r i o n o o g.

1003
01:00:22,460 --> 01:00:29,820
Pero lo hice tienda en esta estructura de datos un valor de verdadero camino aquí en este nodo - en el árbol

1004
01:00:29,820 --> 01:00:33,030
estableciendo este valor booleano de is_word en true.

1005
01:00:33,030 --> 01:00:35,740
Así que un trie es una especie de esta estructura meta muy interesante,

1006
01:00:35,740 --> 01:00:39,810
donde usted no está realmente almacenar las palabras mismas de este tipo de diccionario.

1007
01:00:39,810 --> 01:00:45,100
Para que quede claro, sólo estás almacenando sí o no, hay una palabra que termina aquí.

1008
01:00:45,100 --> 01:00:46,430
>> Ahora, ¿cuál es la implicación?

1009
01:00:46,430 --> 01:00:51,120
Si tiene 150.000 palabras en un diccionario que usted está tratando de almacenar en la memoria

1010
01:00:51,120 --> 01:00:53,400
usando algo como una lista enlazada,

1011
01:00:53,400 --> 01:00:56,870
usted va a tener 150.000 nodos en la lista enlazada.

1012
01:00:56,870 --> 01:01:00,250
Y encontrar una de esas palabras alfabéticamente podría tomar O (n) tiempo.

1013
01:01:00,250 --> 01:01:04,370
El tiempo lineal. Pero en el caso aquí de un trie,

1014
01:01:04,370 --> 01:01:09,210
¿cuál es el tiempo de duración de la búsqueda de una palabra?

1015
01:01:09,210 --> 01:01:17,390
Resulta que la belleza aquí es que incluso si usted tiene ya 149.999 palabras en este diccionario,

1016
01:01:17,390 --> 01:01:20,170
tal como se aplica con esta estructura de datos,

1017
01:01:20,170 --> 01:01:25,560
¿cuánto tiempo se tarda en encontrar o insertar una persona más en eso, como Alice, Alice?

1018
01:01:25,560 --> 01:01:30,640
Bueno, es sólo 5, tal vez 6 pasos para el carácter final.

1019
01:01:30,640 --> 01:01:32,880
Debido a que el presense de otros nombres en la estructura

1020
01:01:32,880 --> 01:01:35,340
no ponerse en el camino de la inserción de Alice.

1021
01:01:35,340 --> 01:01:39,640
Por otra parte, la búsqueda de Alice vez hay 150.000 palabras en este diccionario

1022
01:01:39,640 --> 01:01:41,960
no ponerse en su camino de búsqueda de Alice en absoluto,

1023
01:01:41,960 --> 01:01:46,880
porque Alice es. . . . . aquí, porque me encontré con un valor booleano.

1024
01:01:46,880 --> 01:01:50,920
Y si no hay valor booleano verdadero, entonces Alicia no está en esta estructura de datos de palabras.

1025
01:01:50,920 --> 01:01:56,220
En otras palabras, el tiempo de ejecución de encontrar cosas y la inserción de las cosas en este nuevo

1026
01:01:56,220 --> 01:02:01,920
estructura de datos del trie es de O - no es n.

1027
01:02:01,920 --> 01:02:05,730
Debido a que el presense de 150.000 personas no tiene efecto en Alice, parece.

1028
01:02:05,730 --> 01:02:11,560
Así que vamos a llamarlo k, donde k es la longitud máxima de una palabra en Inglés

1029
01:02:11,560 --> 01:02:14,050
que es típicamente no más de 20-algo caracteres.

1030
01:02:14,050 --> 01:02:17,940
Así que k es una constante. Así que el Santo Grial parece que hemos encontrado ahora

1031
01:02:17,940 --> 01:02:26,000
es la de un tiempo trie, constante para las inserciones, para las búsquedas, para las deleciones.

1032
01:02:26,000 --> 01:02:29,170
Debido a que el número de cosas que ya están en la estructura,

1033
01:02:29,170 --> 01:02:32,600
que ni siquiera son físicamente allí. Una vez más, son sólo una especie de marcado, sí o no,

1034
01:02:32,600 --> 01:02:35,050
no tiene impacto en su tiempo de funcionamiento futuro.

1035
01:02:35,050 --> 01:02:37,940
>> Pero tiene que haber una trampa, de lo contrario no habría perdido tanto tiempo

1036
01:02:37,940 --> 01:02:41,460
en todas estas estructuras de datos sólo para finalmente llegar a la un secreto que es increíble.

1037
01:02:41,460 --> 01:02:46,410
Entonces, ¿qué precio estamos pagando para alcanzar esta grandeza en esta lista? Espacio.

1038
01:02:46,410 --> 01:02:49,010
Esta cosa es enorme. Y la razón de que el autor

1039
01:02:49,010 --> 01:02:52,400
no lo presentamos aquí, note que todas estas cosas que se parecen a las matrices,

1040
01:02:52,400 --> 01:02:55,400
no sacó el resto del árbol, el resto de la trie,

1041
01:02:55,400 --> 01:02:58,060
porque no son sólo relevantes para la historia.

1042
01:02:58,060 --> 01:03:01,870
Pero todos estos ganglios son super amplia, y cada nodo en el árbol de toma

1043
01:03:01,870 --> 01:03:07,780
26 o en realidad, podría ser 27 caracteres porque en este caso yo estaba con espacio para que el apóstrofe

1044
01:03:07,780 --> 01:03:09,980
para que podamos tener palabras apostrofó.

1045
01:03:09,980 --> 01:03:14,450
En este caso, se trata de amplias gamas. Así que, aunque no están picutured,

1046
01:03:14,450 --> 01:03:18,190
esto toma una cantidad masiva de RAM.

1047
01:03:18,190 --> 01:03:20,670
Lo que podría estar bien, especilly en hardware moderno,

1048
01:03:20,670 --> 01:03:25,650
pero esa es la compensación. Tenemos menos tiempo por el gasto de más espacio.

1049
01:03:25,650 --> 01:03:28,580
Entonces, ¿dónde está todo esto va a ir?

1050
01:03:28,580 --> 01:03:32,640
Bueno, vamos a hacer - vamos a ver aquí.

1051
01:03:32,640 --> 01:03:39,510
Vamos a hacer un salto a este tipo aquí.

1052
01:03:39,510 --> 01:03:43,450
>> Lo creas o no, tan divertido como C ha sido por algún tiempo,

1053
01:03:43,450 --> 01:03:48,130
estamos llegando a un punto en el semestre en que es el momento de hacer la transición a las cosas más modernas.

1054
01:03:48,130 --> 01:03:50,950
Las cosas en un nivel superior. Y a pesar de que durante el próximo par de semanas

1055
01:03:50,950 --> 01:03:54,580
todavía nos siguen nos sumergimos en el mundo de los punteros y la gestión de memoria

1056
01:03:54,580 --> 01:03:57,210
para conseguir que la comodidad con la que se puede construir,

1057
01:03:57,210 --> 01:04:01,270
el final del juego es en última instancia a introducir, irónicamente, no esta lengua.

1058
01:04:01,270 --> 01:04:03,330
Pasaremos, como 10 minutos hablando sobre HTML.

1059
01:04:03,330 --> 01:04:05,950
Todos HTML es un lenguaje de marcas, y lo que es un lenguaje de marcas

1060
01:04:05,950 --> 01:04:10,220
Es esta serie de corchetes abiertos y cerrados soportes que dicen "hacer esta audaz"

1061
01:04:10,220 --> 01:04:12,000
"Hacer esto" cursiva "hacer esta centrada.

1062
01:04:12,000 --> 01:04:14,250
No es todo lo que intelectualmente interesante, pero es muy útil.

1063
01:04:14,250 --> 01:04:16,650
Y sin duda es omnipresente en estos días.

1064
01:04:16,650 --> 01:04:19,450
Pero lo que es de gran alcance sobre el mundo de HTML y programación web en general,

1065
01:04:19,450 --> 01:04:25,910
está construyendo cosas dinámicas, escribir código en lenguajes como PHP o Python o Ruby o Java o C #.

1066
01:04:25,910 --> 01:04:30,360
En definitiva, sea cual sea su idioma de elección es, y generar HTML dinámicamente.

1067
01:04:30,360 --> 01:04:32,960
Generación de algo llamado CSS dinámicamente.

1068
01:04:32,960 --> 01:04:35,810
Hojas de estilo en cascada, que es también la estética.

1069
01:04:35,810 --> 01:04:41,360
Y así, a pesar de que, hoy en día, si voy a algún sitio web Google.com como el familiar,

1070
01:04:41,360 --> 01:04:46,100
y voy a ver, desarrollador, ver código fuente, lo que tal vez usted ha hecho antes,

1071
01:04:46,100 --> 01:04:49,800
pero vamos a ver el código fuente, esto probablemente se ve bastante críptico.

1072
01:04:49,800 --> 01:04:55,320
Pero este es el código subyacente que implementa Google.com.

1073
01:04:55,320 --> 01:04:57,940
En la parte delantera. Y en realidad todo esto es materia estética suave y esponjosa.

1074
01:04:57,940 --> 01:05:01,740
Este es el CSS aquí. Si mantengo el desplazamiento hacia abajo vamos a conseguir algunas cosas con códigos de color.

1075
01:05:01,740 --> 01:05:06,890
Esto es HTML. Código de Google parece un lío, pero si realmente abrir una ventana diferente,

1076
01:05:06,890 --> 01:05:09,380
podemos ver cierta estructura a esta.

1077
01:05:09,380 --> 01:05:12,640
Si abro esto, notar aquí, que es un poco más legible.

1078
01:05:12,640 --> 01:05:16,850
Vamos a ver dentro de poco esta etiqueta, [palabra] es una etiqueta,

1079
01:05:16,850 --> 01:05:23,520
HTML, cabeza, cuerpo, div, la escritura, el área de texto, la anchura, centrada, div.

1080
01:05:23,520 --> 01:05:26,770
Y esto es también una especie de misterioso aspecto a primera vista,

1081
01:05:26,770 --> 01:05:30,890
pero todo este lío sigue ciertos patrones y los patrones repetibles,

1082
01:05:30,890 --> 01:05:33,850
de modo que una vez que tengamos los fundamentos abajo, usted será capaz de escribir código como este

1083
01:05:33,850 --> 01:05:37,550
y luego manipular código como este usando otro lenguaje, llamado JavaScript.

1084
01:05:37,550 --> 01:05:40,440
Y JavaScript es un lenguaje que se ejecuta dentro de un navegador

1085
01:05:40,440 --> 01:05:44,380
hoy que utilizamos en los cursos de la Universidad de Harvard, por supuesto, comprar la herramienta que utiliza Google maps

1086
01:05:44,380 --> 01:05:48,660
para darle un montón de dinamismo, Facebook te da para mostrar actualizaciones instantáneas de estado,

1087
01:05:48,660 --> 01:05:51,430
Twitter se utiliza para mostrar mensajes de twitter instante.

1088
01:05:51,430 --> 01:05:53,820
Todo esto, comenzaremos a sumergirnos pulg

1089
01:05:53,820 --> 01:05:57,190
Pero para llegar allí, tenemos que entender un poco sobre el Internet.

1090
01:05:57,190 --> 01:06:01,130
El vídeo aquí es sólo un minuto de duración, y vamos a suponer por ahora esto es, de hecho,

1091
01:06:01,130 --> 01:06:08,380
cómo funciona Internet como un teaser de lo que está por venir. Te doy "Guerreros de la Red".

1092
01:06:08,380 --> 01:06:14,720
>> [♫ ♫ música lenta coro]

1093
01:06:14,720 --> 01:06:20,450
[Narrador] Él vino con un mensaje.

1094
01:06:20,450 --> 01:06:23,770
Con un protocolo de todos los suyos.

1095
01:06:23,770 --> 01:06:37,270
[♫ ♫ música electrónica más rápida]

1096
01:06:37,270 --> 01:06:41,330
Él vino a un mundo de firewalls fresco, despreocupado routers,

1097
01:06:41,330 --> 01:06:45,690
y los peligros mucho peores que la muerte.

1098
01:06:45,690 --> 01:06:55,400
Es rápido. Es fuerte. Él es TCP / IP, y tiene su domicilio.

1099
01:06:55,400 --> 01:06:59,250
Los guerreros de la red.

1100
01:06:59,250 --> 01:07:05,290
[Malan] La semana que viene, entonces. La Internet. Programación web. Esto es CS50.

1101
01:07:05,290 --> 01:07:08,290
[CS50.TV]