1
00:00:00,000 --> 00:00:02,730
[Powered by Google Translate] [Sección 6: menos cómodo]

2
00:00:02,730 --> 00:00:05,040
[Nate Hardison] [Harvard University]

3
00:00:05,040 --> 00:00:07,320
[Esta es CS50.] [CS50.TV]

4
00:00:07,320 --> 00:00:11,840
Está bien. Bienvenidos a la sección 6.

5
00:00:11,840 --> 00:00:14,690
Esta semana, vamos a estar hablando de estructuras de datos en la sección,

6
00:00:14,690 --> 00:00:19,780
sobre todo porque el problema de esta semana establece en spellr

7
00:00:19,780 --> 00:00:24,410
hace un montón de exploración diferente estructura de datos.

8
00:00:24,410 --> 00:00:26,520
Hay un montón de maneras diferentes que usted puede ir con el conjunto de problemas,

9
00:00:26,520 --> 00:00:31,570
y las estructuras de datos más le conocemos, las cosas más interesantes que puedes hacer.

10
00:00:31,570 --> 00:00:34,990
>> Así que vamos a empezar. En primer lugar vamos a hablar de las pilas,

11
00:00:34,990 --> 00:00:37,530
los datos de la pila y la cola de estructuras que vamos a hablar.

12
00:00:37,530 --> 00:00:40,560
Las pilas y las colas son realmente útiles cuando empezamos a hablar de los gráficos,

13
00:00:40,560 --> 00:00:44,390
que no vamos a hacer mucho de estos momentos.

14
00:00:44,390 --> 00:00:52,820
Pero son muy buenos para entender una de las grandes estructuras de datos fundamentales de la CS.

15
00:00:52,820 --> 00:00:54,880
La descripción de la especificación conjunto de problemas,

16
00:00:54,880 --> 00:00:59,260
si tirar de él hacia arriba, habla de las pilas como afín a

17
00:00:59,260 --> 00:01:05,239
la pila de bandejas de comidas que usted tiene en la cafetería a los comedores

18
00:01:05,239 --> 00:01:09,680
donde cuando el personal del comedor viene y pone las bandejas de salir a cenar después de haberlos limpiado,

19
00:01:09,680 --> 00:01:12,000
que apilarlos uno encima del otro.

20
00:01:12,000 --> 00:01:15,050
Y luego, cuando los niños vienen a buscar comida,

21
00:01:15,050 --> 00:01:19,490
tiran las bandejas de salida, primero el uno y luego la de abajo, y luego la de abajo de eso.

22
00:01:19,490 --> 00:01:25,190
Así que, en efecto, la primera bandeja que el personal del comedor poner es el último que se ha despegado.

23
00:01:25,190 --> 00:01:32,330
El último que el personal del comedor poner es el primero que se lo llevan fuera para la cena.

24
00:01:32,330 --> 00:01:38,100
En el conjunto de especificaciones problema, que se puede descargar si no lo ha hecho,

25
00:01:38,100 --> 00:01:46,730
hablamos de modelado de una pila stucture datos utilizando este tipo de estructura.

26
00:01:46,730 --> 00:01:51,070
>> Así que lo que tenemos aquí, esto es similar a lo que se presentó en la conferencia,

27
00:01:51,070 --> 00:01:58,120
excepto en la conferencia se presentaron con este enteros en lugar de char * s.

28
00:01:58,120 --> 00:02:06,250
Esto va a ser una pila que almacena qué?

29
00:02:06,250 --> 00:02:09,009
Daniel? ¿Qué estamos almacenando en esta pila?

30
00:02:09,009 --> 00:02:15,260
[Daniel] Strings? >> Estamos almacenar las cadenas en esta pila, exactamente.

31
00:02:15,260 --> 00:02:20,950
Todo lo que debe tener para crear una pila es una matriz

32
00:02:20,950 --> 00:02:23,920
de una capacidad particular, que en este caso,

33
00:02:23,920 --> 00:02:28,020
capacidad va a ser todo en mayúsculas porque es una constante.

34
00:02:28,020 --> 00:02:36,340
Y a continuación, además de la matriz, todo lo que necesita para seguir es el tamaño actual de la matriz.

35
00:02:36,340 --> 00:02:38,980
Una cosa para notar aquí que es una especie de fresco

36
00:02:38,980 --> 00:02:47,060
es que estamos creando la estructura de datos apiladas una encima de otra estructura de datos, la matriz.

37
00:02:47,060 --> 00:02:50,110
Hay diferentes maneras de implementar pilas.

38
00:02:50,110 --> 00:02:54,250
No lo vamos a hacer todavía, pero espero que después de hacer los problemas de lista vinculada,

39
00:02:54,250 --> 00:03:00,520
verás lo fácil que es implementar una pila en la parte superior de una lista enlazada también.

40
00:03:00,520 --> 00:03:02,640
Pero por ahora, vamos a atenernos a las matrices.

41
00:03:02,640 --> 00:03:06,350
Así que de nuevo, todo lo que necesitamos es una matriz y sólo tenemos que seguir el tamaño de la matriz.

42
00:03:06,350 --> 00:03:09,850
[Sam] Lo siento, ¿cómo es que usted dijo que la pila está por encima de las cuerdas?

43
00:03:09,850 --> 00:03:13,440
A mí me parece que las cadenas están dentro de la pila.

44
00:03:13,440 --> 00:03:16,790
[Hardison] Yeah. Estamos creando, estamos dando nuestra amplia estructura de datos -

45
00:03:16,790 --> 00:03:22,130
esa es una gran pregunta. Entonces la pregunta es ¿por qué, por las personas que están viendo esta línea,

46
00:03:22,130 --> 00:03:24,140
¿por qué estamos diciendo que la pila está por encima de las cuerdas,

47
00:03:24,140 --> 00:03:27,990
porque aquí parece que las cuerdas están en el interior de la pila?

48
00:03:27,990 --> 00:03:31,050
Lo cual es totalmente el caso.

49
00:03:31,050 --> 00:03:34,660
Lo que me refería es que tenemos una estructura de datos array.

50
00:03:34,660 --> 00:03:39,290
Tenemos una matriz de char * s, esta matriz de cadenas,

51
00:03:39,290 --> 00:03:45,300
y que se va a añadir a la que con el fin de crear la estructura de datos apilados.

52
00:03:45,300 --> 00:03:48,620
>> Así que una pila es un poco más complejo que una matriz.

53
00:03:48,620 --> 00:03:51,890
Podemos utilizar una matriz para construir una pila.

54
00:03:51,890 --> 00:03:55,810
Así que ahí es donde decimos que la pila se construye en la parte superior de una matriz.

55
00:03:55,810 --> 00:04:02,510
Del mismo modo, como he dicho antes, podemos construir una pila en la parte superior de una lista enlazada.

56
00:04:02,510 --> 00:04:04,960
En lugar de utilizar una matriz para mantener nuestros elementos,

57
00:04:04,960 --> 00:04:10,070
podemos utilizar una lista enlazada para mantener nuestros elementos y construir la pila de alrededor de eso.

58
00:04:10,070 --> 00:04:12,420
Vamos a ver un par de ejemplos, mirando algo de código,

59
00:04:12,420 --> 00:04:14,960
para ver lo que realmente está pasando aquí.

60
00:04:14,960 --> 00:04:23,400
A la izquierda, he tirado lo que struct pila se vería en la memoria

61
00:04:23,400 --> 00:04:28,330
si la capacidad se definieron # para ser cuatro.

62
00:04:28,330 --> 00:04:33,490
Tenemos nuestros cuatro elementos de matriz char *.

63
00:04:33,490 --> 00:04:38,110
Tenemos cadenas [0], las cadenas [1], las cadenas [2], cadenas [3],

64
00:04:38,110 --> 00:04:43,800
y luego de que el espacio para nuestro pasado entero tamaño.

65
00:04:43,800 --> 00:04:46,270
¿Tiene esto sentido? Bien.

66
00:04:46,270 --> 00:04:48,790
Esto es lo que pasa si lo que hago en la derecha,

67
00:04:48,790 --> 00:04:55,790
que será mi código, es declarar sólo una estructura, una estructura apilada llamado s.

68
00:04:55,790 --> 00:05:01,270
Esto es lo que tenemos. Establece esta huella en la memoria.

69
00:05:01,270 --> 00:05:05,590
La primera pregunta aquí es ¿cuáles son los contenidos de esta estructura de pila?

70
00:05:05,590 --> 00:05:09,250
Ahora mismo no son nada, pero no son totalmente nada.

71
00:05:09,250 --> 00:05:13,300
Son este tipo de basura. No tenemos idea de lo que hay en ellos.

72
00:05:13,300 --> 00:05:17,000
Cuando declaramos s de pila, sólo estamos tirando abajo que en la parte superior de la memoria.

73
00:05:17,000 --> 00:05:19,840
Es algo así como declarar int i, y no lo inicializa.

74
00:05:19,840 --> 00:05:21,730
Usted no sabe lo que hay allí. Usted puede leer lo que hay allí,

75
00:05:21,730 --> 00:05:27,690
pero tal vez no sea muy servicial.

76
00:05:27,690 --> 00:05:32,680
Una de las cosas que desea recordar siempre que hacer es inicializar lo que necesita ser inicializado.

77
00:05:32,680 --> 00:05:35,820
En este caso, vamos a inicializar el tamaño sea cero,

78
00:05:35,820 --> 00:05:39,960
porque eso va a llegar a ser muy importante para nosotros.

79
00:05:39,960 --> 00:05:43,450
Podríamos seguir adelante e iniciar todos los punteros, todo el s * char,

80
00:05:43,450 --> 00:05:49,670
a ser algún valor comprensible, probablemente nulo.

81
00:05:49,670 --> 00:05:58,270
Pero no es totalmente necesario que hagamos eso.

82
00:05:58,270 --> 00:06:04,200
>> Ahora, las dos operaciones principales sobre las pilas de verdad?

83
00:06:04,200 --> 00:06:07,610
Alguien se acuerda de la conferencia que lo que usted hace con las pilas? ¿Sí?

84
00:06:07,610 --> 00:06:09,700
[Stella] Empujando y haciendo estallar? >> Exactamente.

85
00:06:09,700 --> 00:06:13,810
Empujando y haciendo estallar son las dos operaciones principales de pilas.

86
00:06:13,810 --> 00:06:17,060
¿Y qué empuje hacer? >> Se pone algo en la parte superior

87
00:06:17,060 --> 00:06:19,300
de la pila, y luego saltan lo quita.

88
00:06:19,300 --> 00:06:23,150
[Hardison] Exactamente. Así empujando empuja algo en la parte superior de la pila.

89
00:06:23,150 --> 00:06:27,700
Es como el personal del comedor poniendo una bandeja de comida en el mostrador.

90
00:06:27,700 --> 00:06:33,630
Y hacer estallar está tomando una bandeja de cena de la pila.

91
00:06:33,630 --> 00:06:36,460
Vamos a ver un par de ejemplos de lo que sucede

92
00:06:36,460 --> 00:06:39,720
cuando empujamos las cosas en la pila.

93
00:06:39,720 --> 00:06:45,110
Si fuéramos a empujar la cadena 'hola' a nuestro stack,

94
00:06:45,110 --> 00:06:49,760
esto es lo que nuestro diagrama se vería ahora.

95
00:06:49,760 --> 00:06:53,410
Vea lo que sucede?

96
00:06:53,410 --> 00:06:56,530
Nos introduce en el primer elemento de nuestra amplia cuerdas

97
00:06:56,530 --> 00:07:01,420
y nos subió nuestro conteo tamaño es 1.

98
00:07:01,420 --> 00:07:05,340
Así que si nos fijamos en la diferencia entre las dos correderas, aquí fue de 0, esto es antes de la inserción.

99
00:07:05,340 --> 00:07:08,690
Aquí está después de la inserción.

100
00:07:08,690 --> 00:07:13,460
Antes de la inserción, después de la inserción.

101
00:07:13,460 --> 00:07:16,860
Y ahora tenemos un elemento de nuestra pila.

102
00:07:16,860 --> 00:07:20,970
Es la cadena "hola", y eso es todo.

103
00:07:20,970 --> 00:07:24,440
Todo lo demás en la matriz, en nuestro array de cadenas, sigue siendo basura.

104
00:07:24,440 --> 00:07:27,070
No lo hemos inicializado.

105
00:07:27,070 --> 00:07:29,410
Digamos que empujar otra cadena a nuestro stack.

106
00:07:29,410 --> 00:07:32,210
Vamos a empujar "mundo" en este momento.

107
00:07:32,210 --> 00:07:35,160
Así que usted puede ver "mundo" aquí va encima de "hola",

108
00:07:35,160 --> 00:07:40,040
y el recuento de tamaño sube a 2.

109
00:07:40,040 --> 00:07:44,520
Ahora podemos empujar "CS50", y que va a ir en la parte superior de nuevo.

110
00:07:44,520 --> 00:07:51,110
Si retrocedemos, se puede ver cómo estamos llevando las cosas en la parte superior de la pila.

111
00:07:51,110 --> 00:07:53,320
Y ahora llegamos al pop.

112
00:07:53,320 --> 00:07:58,910
Cuando nos fuimos algo fuera de la pila, ¿qué pasó?

113
00:07:58,910 --> 00:08:01,540
¿Alguien ve la diferencia? Es muy sutil.

114
00:08:01,540 --> 00:08:05,810
[Estudiante] El tamaño. >> Sí, el tamaño cambiado.

115
00:08:05,810 --> 00:08:09,040
>> ¿Qué más se puede esperar para el cambio?

116
00:08:09,040 --> 00:08:14,280
[Estudiantes] Las cuerdas, también. >> Derecho. Las cuerdas también.

117
00:08:14,280 --> 00:08:17,110
Resulta que cuando lo haces de esta manera,

118
00:08:17,110 --> 00:08:21,960
porque no estamos copiando los elementos en nuestro stack,

119
00:08:21,960 --> 00:08:24,670
que en realidad no tiene que hacer nada, sólo podemos utilizar el tamaño

120
00:08:24,670 --> 00:08:28,630
hacer un seguimiento de la cantidad de cosas en nuestra amplia

121
00:08:28,630 --> 00:08:33,780
para que cuando aparezca de nuevo, de nuevo sólo disminuir nuestro tamaño a 1.

122
00:08:33,780 --> 00:08:39,440
No hay necesidad de ir en realidad en y sobreescribir cualquier cosa.

123
00:08:39,440 --> 00:08:41,710
Un poco funky.

124
00:08:41,710 --> 00:08:46,520
Resulta que solemos dejar las cosas solo porque es menos trabajo para nosotros.

125
00:08:46,520 --> 00:08:50,060
Si no tenemos que volver atrás y sobrescribir algo, entonces ¿por qué hacerlo?

126
00:08:50,060 --> 00:08:54,150
Así, cuando aparezca el doble de la pila, lo único que hace es disminuir el tamaño de un par de veces.

127
00:08:54,150 --> 00:08:59,120
Y una vez más, esto es sólo porque no estamos copiando cosas en nuestro stack.

128
00:08:59,120 --> 00:09:01,320
¿Sí? Ir por delante.

129
00:09:01,320 --> 00:09:04,460
[Estudiante, ininteligible] >> Y entonces, ¿qué sucede cuando usted empuja algo nuevo?

130
00:09:04,460 --> 00:09:08,570
Cuando se pulsa algo nuevo, ¿adónde va?

131
00:09:08,570 --> 00:09:12,390
¿A dónde va, Basil? En cadenas >> [1]? >> Derecho.

132
00:09:12,390 --> 00:09:14,530
¿Por qué no ir en cadenas [3]?

133
00:09:14,530 --> 00:09:19,410
[Basil] Debido a que se olvidó de que había algo en las cadenas [1] y [2]?

134
00:09:19,410 --> 00:09:24,040
[Hardison] Exactamente. Nuestra pila, en esencia, "se olvidó" que se aferra a cualquier cosa

135
00:09:24,040 --> 00:09:29,480
en las cadenas [1] o cadenas [2], así que cuando nos empujan "woot"

136
00:09:29,480 --> 00:09:36,670
sólo pone eso en el elemento en cadenas [1].

137
00:09:36,670 --> 00:09:41,590
¿Hay alguna pregunta sobre cómo funciona esto, a un nivel básico?

138
00:09:41,590 --> 00:09:45,160
[Sam] Así que esto no es de ninguna manera dinámica, en términos de cantidad

139
00:09:45,160 --> 00:09:47,620
o en términos del tamaño de la pila?

140
00:09:47,620 --> 00:09:56,750
[Hardison] Exactamente. Esto es - el punto era que no se trataba de una pila dinámica growning.

141
00:09:56,750 --> 00:10:02,850
Esta es una pila que puede contener, como máximo, cuatro char * s, en la mayoría de cuatro cosas.

142
00:10:02,850 --> 00:10:07,580
Si fuéramos a tratar de empujar una quinta cosa, ¿qué cree usted que debería ocurrir?

143
00:10:07,580 --> 00:10:11,870
[Los estudiantes], ininteligibles

144
00:10:11,870 --> 00:10:14,600
[Hardison] Exactamente. Hay una serie de cosas que podrían suceder.

145
00:10:14,600 --> 00:10:19,330
Posiblemente podría seg culpa, dependiendo de lo que eran -

146
00:10:19,330 --> 00:10:22,530
¿cómo es exactamente lo que estaban ejecutando el back-end.

147
00:10:22,530 --> 00:10:31,740
Puede sobrescribir. Podría tener que desbordamiento de búfer que hablamos en clase.

148
00:10:31,740 --> 00:10:35,240
¿Cuál sería la cosa más obvia que puede ser sobreescrita

149
00:10:35,240 --> 00:10:42,370
si tratamos de empujar algo extra en nuestra pila?

150
00:10:42,370 --> 00:10:44,550
Así que usted ha mencionado un desbordamiento de búfer.

151
00:10:44,550 --> 00:10:47,870
¿Cuál podría ser la cosa que se escriben sobre o pisoteó

152
00:10:47,870 --> 00:10:52,320
si nos desbordó accidentalmente al tratar de empujar una cosa extra?

153
00:10:52,320 --> 00:10:54,730
[Daniel, ininteligible] >> Posible.

154
00:10:54,730 --> 00:10:58,440
Pero inicialmente, lo que podría ocurrir? ¿Qué pasa si tratamos de empujar una cuarta cosa?

155
00:10:58,440 --> 00:11:06,220
Puede sobrescribir el tamaño, al menos con este esquema de memoria que tenemos.

156
00:11:06,220 --> 00:11:10,880
>> En la especificación conjunto de problemas, que es lo que vamos a estar implementando hoy en día,

157
00:11:10,880 --> 00:11:16,030
lo que quiero hacer es devolver false.

158
00:11:16,030 --> 00:11:20,030
Nuestro método de empuje se va a devolver un valor booleano,

159
00:11:20,030 --> 00:11:22,920
y que el valor booleano será verdadera si el empuje éxito

160
00:11:22,920 --> 00:11:29,730
y falso si no podemos empujar más nada porque la pila está llena.

161
00:11:29,730 --> 00:11:33,620
Vamos a ver un poco de ese código en estos momentos.

162
00:11:33,620 --> 00:11:36,400
Esta es nuestra función push.

163
00:11:36,400 --> 00:11:40,380
Nuestra función push para una pila se va a tomar en la cadena para poner en la pila.

164
00:11:40,380 --> 00:11:45,820
Se va a devolver true si la cadena fue empujado con éxito

165
00:11:45,820 --> 00:11:51,820
de otra manera en la pila y lo falso.

166
00:11:51,820 --> 00:11:59,740
¿Alguna sugerencia sobre lo que podría ser una buena cosa primero que debemos hacer aquí?

167
00:11:59,740 --> 00:12:20,630
[Sam] Si el tamaño es igual a la capacidad de devolver false entonces?

168
00:12:20,630 --> 00:12:23,320
[Hardison] Bingo. Buen trabajo.

169
00:12:23,320 --> 00:12:26,310
Si el tamaño es la capacidad, vamos a devolver false.

170
00:12:26,310 --> 00:12:29,270
No podemos poner nada más en nuestra pila.

171
00:12:29,270 --> 00:12:36,900
De lo contrario, queremos poner algo en la parte superior de la pila.

172
00:12:36,900 --> 00:12:41,670
¿Qué es "la parte superior de la pila," inicialmente?

173
00:12:41,670 --> 00:12:43,650
[Daniel] Tamaño 0? Tamaño >> 0.

174
00:12:43,650 --> 00:12:49,990
¿Cuál es la parte superior de la pila después hay una cosa en la pila? Missy, ¿sabes?

175
00:12:49,990 --> 00:12:52,720
[Missy] Una. Tamaño >> es uno, exactamente. Usted mantener la adición al tamaño,

176
00:12:52,720 --> 00:13:01,690
y cada vez que se está poniendo en el nuevo elemento en el tamaño del índice en la matriz.

177
00:13:01,690 --> 00:13:05,470
Lo podemos hacer con ese tipo de una sola línea, si eso tiene sentido.

178
00:13:05,470 --> 00:13:11,910
Así que tenemos nuestra matriz de cadenas, vamos a acceder a él en el índice de tamaño,

179
00:13:11,910 --> 00:13:14,780
y sólo vamos a guardar nuestro char * en ese país.

180
00:13:14,780 --> 00:13:19,340
Nótese cómo hay ninguna copia cuerda pasando aquí,

181
00:13:19,340 --> 00:13:29,680
no asignación dinámica de la memoria?

182
00:13:29,680 --> 00:13:34,440
Y luego Missy criado lo que ahora tenemos que hacer,

183
00:13:34,440 --> 00:13:40,570
porque hemos guardado la cadena en el lugar apropiado en la matriz,

184
00:13:40,570 --> 00:13:49,230
y ella me dijo que había que aumentar el tamaño de una forma que estamos listos para la siguiente pulsación.

185
00:13:49,230 --> 00:13:53,950
Así que podemos hacer eso con s.size + +.

186
00:13:53,950 --> 00:13:59,330
En este punto, hemos empujado a nuestra matriz. ¿Qué es lo último que tenemos que hacer?

187
00:13:59,330 --> 00:14:10,110
[Estudiante] Devuelve true. >> Volver verdad.

188
00:14:10,110 --> 00:14:14,690
Así que es bastante simple, un código bastante simple. No demasiado.

189
00:14:14,690 --> 00:14:17,070
Una vez que ha envuelto la cabeza en torno a cómo funciona la pila,

190
00:14:17,070 --> 00:14:21,910
esto es bastante sencillo de implementar.

191
00:14:21,910 --> 00:14:26,390
>> Ahora, la siguiente parte de esta está apareciendo una cadena de la pila.

192
00:14:26,390 --> 00:14:29,410
Voy a dar ustedes algo de tiempo para trabajar en esto un poco.

193
00:14:29,410 --> 00:14:34,320
Es casi esencialmente lo contrario de lo que hemos hecho aquí en empuje.

194
00:14:34,320 --> 00:14:38,510
Lo que he hecho es en realidad - oops.

195
00:14:38,510 --> 00:14:48,160
He arrancado un aparato por aquí, y en el aparato,

196
00:14:48,160 --> 00:14:53,600
He tirado el problema conjunto 5 especificación.

197
00:14:53,600 --> 00:15:02,560
Si el zoom aquí, podemos ver que estoy en cdn.cs50.net/2012/fall/psets/pset5.pdf.

198
00:15:02,560 --> 00:15:08,590
¿Han descargado el código que se encuentra aquí, section6.zip?

199
00:15:08,590 --> 00:15:15,030
Está bien. Si usted no ha hecho esto, haz lo otro en este momento, muy rápido.

200
00:15:15,030 --> 00:15:22,130
Lo haré en mi ventana de terminal.

201
00:15:22,130 --> 00:15:25,090
De hecho, me lo hizo aquí. Si.

202
00:15:25,090 --> 00:15:34,730
Sí, Sam? >> Tengo una pregunta acerca de por qué le dijiste s.string 's soportes de tamaño = str?

203
00:15:34,730 --> 00:15:42,910
¿Cuál es str? Es el definido antes en alguna parte, o - oh, en la char * str?

204
00:15:42,910 --> 00:15:47,160
[Hardison] Sí, exactamente. Ese fue el argumento. >> Oh, está bien. Lo siento.

205
00:15:47,160 --> 00:15:49,470
[Hardison] Estamos especificar la cadena de empujar pulg

206
00:15:49,470 --> 00:15:55,220
La otra cuestión que pueda surgir que realmente no hablar de aquí fue

207
00:15:55,220 --> 00:15:58,810
se daba por sentado que tuvimos esta variable llamada s

208
00:15:58,810 --> 00:16:02,710
que era en su alcance y accesible para nosotros.

209
00:16:02,710 --> 00:16:06,960
Nos dieron por sentado que era este s struct pila.

210
00:16:06,960 --> 00:16:08,930
Así que mirando hacia atrás en el código de inserción,

211
00:16:08,930 --> 00:16:13,450
se puede ver que estamos haciendo cosas con esta cadena que quedó aprobada en

212
00:16:13,450 --> 00:16:19,210
pero luego, de repente, estamos accediendo s.size, al igual que, ¿de dónde provienen de s?

213
00:16:19,210 --> 00:16:23,020
En el código que vamos a ver en el archivo de la sección

214
00:16:23,020 --> 00:16:27,100
y entonces las cosas que usted hará en su problema se pone,

215
00:16:27,100 --> 00:16:32,440
hemos hecho nuestra pila struct una variable global

216
00:16:32,440 --> 00:16:36,380
para que podamos tener acceso a ella en todas nuestras funciones diferentes

217
00:16:36,380 --> 00:16:40,630
sin tener que pasar manualmente alrededor y pasarlo por referencia,

218
00:16:40,630 --> 00:16:44,870
hacer todo ese tipo de cosas a ella.

219
00:16:44,870 --> 00:16:52,280
Sólo estamos engañando un poco, si se quiere, para hacer las cosas mejor.

220
00:16:52,280 --> 00:16:57,430
Y eso es algo que estamos haciendo aquí porque es por diversión, es más fácil.

221
00:16:57,430 --> 00:17:02,800
A menudo, usted verá la gente hace esto si tienen una estructura de datos grande

222
00:17:02,800 --> 00:17:07,750
que está siendo operado dentro de su programa.

223
00:17:07,750 --> 00:17:09,560
>> Vamos a ir de nuevo hacia el aparato.

224
00:17:09,560 --> 00:17:15,240
¿Todos con éxito obtener el section6.zip?

225
00:17:15,240 --> 00:17:20,440
Todo el mundo lo descomprima usando section6.zip descomprimir?

226
00:17:20,440 --> 00:17:27,200
Si usted entra en la sección 6 del directorio -

227
00:17:27,200 --> 00:17:29,220
aah, por todo el lugar -

228
00:17:29,220 --> 00:17:32,840
y una lista de lo que hay aquí, se ve que tienes tres archivos diferentes. c.

229
00:17:32,840 --> 00:17:38,350
Usted tiene una cola, una sll, que es la lista simplemente enlazada, y una pila.

230
00:17:38,350 --> 00:17:44,600
Si usted abre stack.c,

231
00:17:44,600 --> 00:17:47,330
se puede ver que tenemos esta estructura definida por nosotros,

232
00:17:47,330 --> 00:17:51,330
la estructura exacta que acabamos de hablar en las diapositivas.

233
00:17:51,330 --> 00:17:56,340
Tenemos nuestra variable global de la pila,

234
00:17:56,340 --> 00:18:00,110
tenemos nuestra función push,

235
00:18:00,110 --> 00:18:04,230
y luego tenemos nuestra función pop.

236
00:18:04,230 --> 00:18:08,320
Voy a poner el código para hacer retroceder a la diapositiva aquí,

237
00:18:08,320 --> 00:18:10,660
pero lo que me gustaría que ustedes hacen es, a lo mejor de su capacidad,

238
00:18:10,660 --> 00:18:13,790
ir y poner en práctica la función pop.

239
00:18:13,790 --> 00:18:18,480
Una vez que haya puesto en práctica, puede compilar con make esta pila,

240
00:18:18,480 --> 00:18:22,540
a continuación, ejecute el archivo ejecutable pila resultante,

241
00:18:22,540 --> 00:18:28,390
y que se extenderá todo este código de prueba aquí que está en principal.

242
00:18:28,390 --> 00:18:31,060
Y principal se encarga realmente de hacer el push y pop llamadas

243
00:18:31,060 --> 00:18:33,220
y asegurarse de que todo va a través de todo derecho.

244
00:18:33,220 --> 00:18:36,820
También se inicializa el tamaño de la pila aquí

245
00:18:36,820 --> 00:18:39,780
por lo que no tiene que preocuparse de que la inicialización.

246
00:18:39,780 --> 00:18:42,310
Se puede suponer que ha sido correctamente inicializado

247
00:18:42,310 --> 00:18:48,000
en el momento en que acceda a ella en la función pop.

248
00:18:48,000 --> 00:18:53,530
¿Eso tiene sentido?

249
00:18:53,530 --> 00:19:00,100
Así que aquí vamos. Ahí está el código de inserción.

250
00:19:00,100 --> 00:19:13,210
Voy a daros 5 o 10 minutos.

251
00:19:13,210 --> 00:19:15,690
Y si usted tiene alguna pregunta en el ínterin mientras estás codificación,

252
00:19:15,690 --> 00:19:17,710
por favor pregunte en voz alta.

253
00:19:17,710 --> 00:19:23,080
Así que si se llega a un punto de estancamiento, solo pregunte.

254
00:19:23,080 --> 00:19:26,030
Déjame saber, que todo el mundo sabe.

255
00:19:26,030 --> 00:19:28,160
Trabaje con su vecino también.

256
00:19:28,160 --> 00:19:30,360
[Daniel] Estamos implementación pop en este momento? >> Just pop.

257
00:19:30,360 --> 00:19:34,200
Aunque usted puede copiar la aplicación de empuje si desea

258
00:19:34,200 --> 00:19:37,780
de modo que la prueba funcionará.

259
00:19:37,780 --> 00:19:41,940
Debido a que es difícil probar que las cosas se en -

260
00:19:41,940 --> 00:19:49,030
o, es difícil de probar cosas que hacen estallar fuera de una pila si no hay nada en la pila, para empezar.

261
00:19:49,030 --> 00:19:55,250
>> ¿Qué es el pop supone que se repitan? El elemento de la parte superior de la pila.

262
00:19:55,250 --> 00:20:01,260
Se supone que para obtener el elemento fuera de la parte superior de la pila

263
00:20:01,260 --> 00:20:05,780
y luego disminuir el tamaño de la pila,

264
00:20:05,780 --> 00:20:07,810
y ahora que ha perdido el elemento en la parte superior.

265
00:20:07,810 --> 00:20:11,420
Y luego que devuelva el elemento en la parte superior.

266
00:20:11,420 --> 00:20:20,080
[Estudiante, ininteligible]

267
00:20:20,080 --> 00:20:28,810
[Hardison] Entonces, ¿qué pasa si se hace eso? [Estudiante, ininteligible]

268
00:20:28,810 --> 00:20:34,000
Lo que termina pasando es que estás probablemente para acceder a cualquiera de los dos

269
00:20:34,000 --> 00:20:37,350
un elemento que no se ha inicializado todavía, por lo que su cálculo

270
00:20:37,350 --> 00:20:39,990
de donde el último elemento es está apagado.

271
00:20:39,990 --> 00:20:46,260
Así que aquí, si te fijas, en el impulso, estamos accediendo cadenas en el elemento s.size

272
00:20:46,260 --> 00:20:48,560
porque se trata de un nuevo índice.

273
00:20:48,560 --> 00:20:51,460
Es el nuevo tope de la pila.

274
00:20:51,460 --> 00:21:01,100
Mientras que en el pop, s.size va a ser el siguiente espacio,

275
00:21:01,100 --> 00:21:05,210
El espacio que hay en la parte superior de todos los elementos de la pila.

276
00:21:05,210 --> 00:21:10,050
De modo que el elemento de más arriba no es s.size,

277
00:21:10,050 --> 00:21:14,930
sino más bien, es por debajo de él.

278
00:21:14,930 --> 00:21:19,640
>> La otra cosa que hacer cuando - en el pop,

279
00:21:19,640 --> 00:21:22,030
se le tiene que disminuir el tamaño.

280
00:21:22,030 --> 00:21:28,750
Si usted recuerda de nuevo a nuestro pequeño diagrama aquí,

281
00:21:28,750 --> 00:21:30,980
en realidad, lo único que vimos sucediendo cuando llamamos pop

282
00:21:30,980 --> 00:21:36,150
era que este tamaño disminuido, primero a 2, y luego a 1.

283
00:21:36,150 --> 00:21:42,620
Luego, cuando empujó un nuevo elemento en adelante, seguiría en el lugar adecuado.

284
00:21:42,620 --> 00:21:49,610
[Basil] Si el s.size es 2, entonces ¿no sería ir al elemento 2,

285
00:21:49,610 --> 00:21:54,400
y luego que te gustaría hacer estallar ese elemento fuera?

286
00:21:54,400 --> 00:21:59,510
Así que si nos fuimos a - >> Así que echemos un vistazo a esto de nuevo.

287
00:21:59,510 --> 00:22:07,730
Si esta es nuestra pila en este momento

288
00:22:07,730 --> 00:22:12,130
y llamamos pop,

289
00:22:12,130 --> 00:22:16,150
en qué índice es el elemento de más arriba?

290
00:22:16,150 --> 00:22:19,300
[Basil] A los 2, pero va a aparecer 3. >> Derecho.

291
00:22:19,300 --> 00:22:24,220
Así que ahí es donde nuestro tamaño es 3, pero queremos que aparezca el elemento en el índice 2.

292
00:22:24,220 --> 00:22:29,900
Es ese tipo típico de apagado por una que usted tiene con el cero de la indexación de arrays.

293
00:22:29,900 --> 00:22:36,430
Así que usted quiere meter el tercer elemento, pero el tercer elemento no está en el índice 3.

294
00:22:36,430 --> 00:22:39,430
Y la razón por la que no tienes que hacer eso menos 1 cuando estamos empujando

295
00:22:39,430 --> 00:22:44,120
se debe a que en estos momentos, te das cuenta de que el elemento de más arriba,

296
00:22:44,120 --> 00:22:47,600
si eran para empujar algo más en la pila en este punto,

297
00:22:47,600 --> 00:22:50,360
nos gustaría que empujarla en el índice 3.

298
00:22:50,360 --> 00:23:03,550
Y da la casualidad de que el tamaño y los índices alineados cuando usted está empujando.

299
00:23:03,550 --> 00:23:06,960
>> ¿Quién tiene una implementación de la pila de trabajo?

300
00:23:06,960 --> 00:23:09,690
Tienes un montón de trabajo uno. ¿Tiene pop trabajando todavía?

301
00:23:09,690 --> 00:23:11,890
[Daniel] Sí. Creo que sí.

302
00:23:11,890 --> 00:23:14,610
Programa >> está corriendo y no seg fallamiento, se está imprimiendo?

303
00:23:14,610 --> 00:23:17,520
¿Se imprimirá el "éxito" cuando se ejecuta?

304
00:23:17,520 --> 00:23:22,630
Si. Hacer apilar, ejecutarlo, si imprime el "éxito" y no va boom,

305
00:23:22,630 --> 00:23:26,000
entonces todo está bien.

306
00:23:26,000 --> 00:23:34,070
Está bien. Vamos a repasar el aparato muy rápido,

307
00:23:34,070 --> 00:23:46,100
y vamos a caminar a través de este.

308
00:23:46,100 --> 00:23:51,110
Si nos fijamos en lo que está pasando aquí con el pop,

309
00:23:51,110 --> 00:23:55,220
Daniel, ¿qué fue lo primero que hiciste?

310
00:23:55,220 --> 00:23:58,850
[Daniel] Si s.size es mayor que 0.

311
00:23:58,850 --> 00:24:03,120
[Hardison] Bueno. ¿Y por qué has hecho eso?

312
00:24:03,120 --> 00:24:05,610
[Daniel] Para asegurarse de que había algo dentro de la pila.

313
00:24:05,610 --> 00:24:10,950
[Hardison] Derecho. ¿Quieres poner a prueba para asegurarse de que s.size es mayor que 0;

314
00:24:10,950 --> 00:24:13,280
de lo contrario, ¿qué quieres que pase?

315
00:24:13,280 --> 00:24:16,630
[Daniel] null retorno? Nulo >> Retorno, exactamente.

316
00:24:16,630 --> 00:24:20,740
Así que si s.size es mayor que 0. Entonces, ¿qué vamos a hacer?

317
00:24:20,740 --> 00:24:25,890
¿Qué hacemos si la pila no está vacía?

318
00:24:25,890 --> 00:24:31,210
[Stella] Usted disminuir el tamaño? >> Usted disminuir el tamaño, está bien.

319
00:24:31,210 --> 00:24:34,440
Entonces, ¿cómo hiciste eso? >> S.size--.

320
00:24:34,440 --> 00:24:37,030
[Hardison] Great. Y entonces, ¿qué hiciste?

321
00:24:37,030 --> 00:24:44,140
[Stella] Y entonces me dijo que el regreso s.string [s.size].

322
00:24:44,140 --> 00:24:48,560
[Hardison] Great.

323
00:24:48,560 --> 00:24:51,940
De lo contrario, devuelve null. Sí, Sam?

324
00:24:51,940 --> 00:24:55,510
[Sam] ¿Por qué no lo necesita para ser s.size + 1?

325
00:24:55,510 --> 00:24:58,430
[Hardison] Plus 1? Sí >>. >> Lo tengo.

326
00:24:58,430 --> 00:25:00,980
[Sam] pensé porque usted toma con 1,

327
00:25:00,980 --> 00:25:04,290
entonces usted va a regresar no es el que ellos pidieron.

328
00:25:04,290 --> 00:25:09,400
[Hardison] Y esto era justo lo que estábamos hablando con todo este tema de 0 índices.

329
00:25:09,400 --> 00:25:11,380
Así que si amplía aquí.

330
00:25:11,380 --> 00:25:15,650
Si nos fijamos en este tipo aquí, se puede ver que cuando el pop,

331
00:25:15,650 --> 00:25:19,340
estamos haciendo estallar el elemento de índice 2.

332
00:25:19,340 --> 00:25:25,200
>> Por lo tanto, disminuir el tamaño de nuestra primera, entonces nuestro tamaño coincide con nuestro índice.

333
00:25:25,200 --> 00:25:39,650
Si no disminuir el tamaño de la primera, entonces tenemos que ver tamaño -1 y decremento.

334
00:25:39,650 --> 00:25:45,270
Grande. ¿Todo bien?

335
00:25:45,270 --> 00:25:47,530
¿Tiene preguntas sobre esto?

336
00:25:47,530 --> 00:25:54,050
Hay un número de formas diferentes de escribir esto.

337
00:25:54,050 --> 00:26:03,290
De hecho, podemos hacer algo todavía - podemos hacer una sola línea.

338
00:26:03,290 --> 00:26:05,770
Podemos hacer una declaración de una línea.

339
00:26:05,770 --> 00:26:12,980
Así que en realidad puede disminuir antes de que volvamos a hacerlo.

340
00:26:12,980 --> 00:26:18,320
Así que poner el - antes de la s.size.

341
00:26:18,320 --> 00:26:22,060
Eso hace que la línea realmente denso.

342
00:26:22,060 --> 00:26:30,940
Cuando la diferencia entre el -. S tamaño y s.size--

343
00:26:30,940 --> 00:26:40,130
es que este sufijo - lo llaman porque el sufijo - viene después de la s.size--

344
00:26:40,130 --> 00:26:47,430
significa que s.size se evalúa a los efectos de encontrar el índice

345
00:26:47,430 --> 00:26:50,410
como lo es en la actualidad cuando se ejecuta esta línea,

346
00:26:50,410 --> 00:26:54,290
y luego esto - que sucede después de la línea se ejecuta.

347
00:26:54,290 --> 00:27:00,340
Después de que el elemento en s.size índice se accede.

348
00:27:00,340 --> 00:27:07,260
Y eso no es lo que queremos, porque queremos que el decremento que suceda primero.

349
00:27:07,260 --> 00:27:10,990
Othewise, vamos a estar accediendo a la matriz, efectivamente, fuera del campo.

350
00:27:10,990 --> 00:27:16,850
Vamos a estar accediendo al elemento superior a la que realmente desea acceder.

351
00:27:16,850 --> 00:27:23,840
Sí, Sam? >> ¿Es más rápido y usa menos memoria RAM para hacer en una sola línea o no?

352
00:27:23,840 --> 00:27:29,620
[Hardison] Honestamente, realmente depende.

353
00:27:29,620 --> 00:27:34,220
[Sam, ininteligible] >> Sí, depende. Usted puede hacer trucos de compilación

354
00:27:34,220 --> 00:27:41,580
para obtener el compilador de reconocer que, por lo general, me imagino.

355
00:27:41,580 --> 00:27:44,840
>> Para ello hemos mencionado un poco sobre estas cosas optimización del compilador

356
00:27:44,840 --> 00:27:47,400
que se puede hacer en la recopilación,

357
00:27:47,400 --> 00:27:50,580
y ese es el tipo de cosa que un compilador puede ser capaz de entender,

358
00:27:50,580 --> 00:27:54,710
como oh, hey, tal vez pueda hacer todo esto en una sola operación,

359
00:27:54,710 --> 00:27:59,420
en oposición a la carga de la variable en tamaño de RAM,

360
00:27:59,420 --> 00:28:03,770
decreciendo, almacenándolo a salir, y luego vuelva a cargar

361
00:28:03,770 --> 00:28:08,000
para procesar el resto de esta operación.

362
00:28:08,000 --> 00:28:10,710
Pero por lo general, no, este no es el tipo de cosas

363
00:28:10,710 --> 00:28:20,770
que va a hacer su programa mucho más rápido.

364
00:28:20,770 --> 00:28:26,000
¿Alguna pregunta más sobre las pilas?

365
00:28:26,000 --> 00:28:31,360
>> Así que empujar y hacer estallar. Si ustedes quieren probar la edición pirata informático,

366
00:28:31,360 --> 00:28:33,660
lo que hemos hecho en la edición pirata es en realidad ido

367
00:28:33,660 --> 00:28:37,670
e hicieron de esta pila de crecer de forma dinámica.

368
00:28:37,670 --> 00:28:43,190
El reto no es principalmente aquí en la función push,

369
00:28:43,190 --> 00:28:48,820
para encontrar la manera de hacer crecer esa matriz

370
00:28:48,820 --> 00:28:52,450
a medida que seguir empujando más y más elementos en la pila.

371
00:28:52,450 --> 00:28:56,000
En realidad no es un código adicional en exceso.

372
00:28:56,000 --> 00:29:00,080
Sólo una llamada a - usted tiene que recordar para conseguir las llamadas a malloc ahí correctamente,

373
00:29:00,080 --> 00:29:03,310
y luego averiguar cuándo va a llamar realloc.

374
00:29:03,310 --> 00:29:06,090
Eso es un reto divertido si te interesa.

375
00:29:06,090 --> 00:29:11,550
>> Pero por el momento, vamos a seguir adelante, y vamos a hablar de las colas.

376
00:29:11,550 --> 00:29:15,680
Desplácese por aquí.

377
00:29:15,680 --> 00:29:19,340
La cola es un hermano cerca de la pila.

378
00:29:19,340 --> 00:29:25,380
Así que en la pila, las cosas que se pusieron en última

379
00:29:25,380 --> 00:29:28,810
fueron las primeras cosas para luego ser recuperados.

380
00:29:28,810 --> 00:29:33,600
Tenemos este último en entrar, primero en salir, o UEPS, hacer el pedido.

381
00:29:33,600 --> 00:29:38,390
Mientras que en la cola, como era de esperar a partir de cuando se está de pie en la fila,

382
00:29:38,390 --> 00:29:41,980
la primera persona que entra en la línea, lo primero que debe entrar en la cola,

383
00:29:41,980 --> 00:29:47,630
es lo primero que se recupera de la cola.

384
00:29:47,630 --> 00:29:51,490
Las colas también se utiliza a menudo cuando estamos tratando con gráficos,

385
00:29:51,490 --> 00:29:55,560
como hemos hablado brevemente con pilas,

386
00:29:55,560 --> 00:30:00,260
y las colas también son útiles para un montón de otras cosas.

387
00:30:00,260 --> 00:30:06,180
Una cosa que surge a menudo está tratando de mantener, por ejemplo,

388
00:30:06,180 --> 00:30:12,310
una lista ordenada de elementos.

389
00:30:12,310 --> 00:30:17,650
Y usted puede hacer esto con una matriz. Puede mantener una lista ordenada de las cosas en una matriz,

390
00:30:17,650 --> 00:30:20,650
pero en los que se complica es entonces siempre hay que encontrar

391
00:30:20,650 --> 00:30:26,160
el lugar adecuado para insertar la siguiente cosa.

392
00:30:26,160 --> 00:30:28,250
Así que si usted tiene una matriz de números, del 1 al 10,

393
00:30:28,250 --> 00:30:31,630
y luego desea ampliar eso a todos los números de 1 a 100,

394
00:30:31,630 --> 00:30:33,670
y que está recibiendo estos números en orden aleatorio y tratando de mantener todo

395
00:30:33,670 --> 00:30:40,650
ordenados a medida que avanza, usted termina encima de tener que hacer un montón de cambio.

396
00:30:40,650 --> 00:30:43,910
Con ciertos tipos de colas y ciertos tipos de estructuras de datos subyacentes,

397
00:30:43,910 --> 00:30:46,670
en realidad se puede mantener bastante simple.

398
00:30:46,670 --> 00:30:50,640
Usted no tiene que añadir algo y luego barajar la cosa entera cada vez.

399
00:30:50,640 --> 00:30:56,770
Tampoco hay que hacer un montón de desplazamiento de los elementos internos a la redonda.

400
00:30:56,770 --> 00:31:02,990
Cuando nos fijamos en una cola, se ve que - también en queue.c en el código de sección -

401
00:31:02,990 --> 00:31:10,950
la estructura que le hemos dado es muy similar a la estructura que le dio para una pila.

402
00:31:10,950 --> 00:31:13,770
>> Hay una excepción a esto, y que una excepción

403
00:31:13,770 --> 00:31:21,700
es que tenemos este entero adicional llama la cabeza,

404
00:31:21,700 --> 00:31:28,120
y la cabeza aquí es para hacer el seguimiento de la cabeza de la cola,

405
00:31:28,120 --> 00:31:32,160
o el primer elemento en la cola.

406
00:31:32,160 --> 00:31:37,470
Con una pila, hemos sido capaces de hacer un seguimiento de los elementos que estábamos a punto de recuperar,

407
00:31:37,470 --> 00:31:40,800
o la parte superior de la pila, utilizando sólo el tamaño,

408
00:31:40,800 --> 00:31:44,220
mientras que con una cola, vamos a tener que lidiar con los extremos opuestos.

409
00:31:44,220 --> 00:31:49,000
Estamos tratando de virar las cosas en al final, pero luego regresan las cosas de frente.

410
00:31:49,000 --> 00:31:54,640
Así que efectivamente, con la cabeza, que tiene el índice del principio de la cola,

411
00:31:54,640 --> 00:31:58,920
y el tamaño nos da el índice del final de la cola

412
00:31:58,920 --> 00:32:03,730
para que podamos recuperar las cosas de la cabeza y añadir cosas a la cola.

413
00:32:03,730 --> 00:32:06,890
Mientras que con la pila, sólo estábamos nunca tratar con la parte superior de la pila.

414
00:32:06,890 --> 00:32:08,900
Nunca tuvimos que acceder a la parte inferior de la pila.

415
00:32:08,900 --> 00:32:12,220
Sólo añade cosas a la cima y tomó las cosas fuera de la parte superior

416
00:32:12,220 --> 00:32:17,470
así que no necesito ese campo adicional en el interior de nuestro struct.

417
00:32:17,470 --> 00:32:20,590
¿Eso generalmente tiene sentido?

418
00:32:20,590 --> 00:32:27,670
Está bien. Sí, Charlotte? [Charlotte, ininteligible]

419
00:32:27,670 --> 00:32:32,660
[Hardison] Eso es una gran pregunta, y que fue el que ocurrió en la conferencia.

420
00:32:32,660 --> 00:32:36,290
Tal vez caminando a través de algunos ejemplos que ilustran por qué

421
00:32:36,290 --> 00:32:41,400
no queremos usar cadenas [0] como la cabeza de la cola.

422
00:32:41,400 --> 00:32:46,770
>> Así que imaginen que tenemos nuestra cola, vamos a llamarlo cola.

423
00:32:46,770 --> 00:32:49,210
Al principio, cuando acabo de instancia,

424
00:32:49,210 --> 00:32:53,330
cuando acabamos de lo declarado, no hemos inicializado nada.

425
00:32:53,330 --> 00:32:56,790
Es todo basura. Así que, por supuesto, queremos asegurarnos de que inicializar

426
00:32:56,790 --> 00:33:00,950
tanto el tamaño y los campos de cabeza a ser 0, algo razonable.

427
00:33:00,950 --> 00:33:05,770
También podríamos seguir adelante y nulos los elementos en nuestra cola.

428
00:33:05,770 --> 00:33:09,930
Y para hacer este ajuste diagrama, note que ahora nuestra cola sólo puede contener tres elementos;

429
00:33:09,930 --> 00:33:13,150
mientras que nuestra pila podría tener cuatro, nuestra cola sólo puede tener tres.

430
00:33:13,150 --> 00:33:18,680
Y eso es sólo para hacer el ajuste diagrama.

431
00:33:18,680 --> 00:33:26,150
Lo primero que sucede aquí es que encolar la cadena "hola".

432
00:33:26,150 --> 00:33:30,380
Y al igual que hicimos con la pila, nada terriblemente diferente aquí,

433
00:33:30,380 --> 00:33:39,230
tiramos la cuerda de las cuerdas [0] y aumentar nuestro tamaño en 1.

434
00:33:39,230 --> 00:33:42,720
Nos encolar "bye", consigue poner.

435
00:33:42,720 --> 00:33:45,870
Por lo tanto esto se parece a una pila en su mayor parte.

436
00:33:45,870 --> 00:33:53,230
Empezamos aquí, nuevo elemento, el elemento nuevo, el tamaño sigue subiendo.

437
00:33:53,230 --> 00:33:56,330
¿Qué sucede en este momento en el que queremos quitar de la cola algo?

438
00:33:56,330 --> 00:34:01,280
Cuando queremos quitar de la cola, que es el elemento que queremos quitar de la cola?

439
00:34:01,280 --> 00:34:04,110
[Basil] Strings [0]. >> Cero. Exactamente, Basil.

440
00:34:04,110 --> 00:34:10,960
Queremos deshacernos de la primera cadena, este "hola".

441
00:34:10,960 --> 00:34:13,170
Entonces, ¿cuál era la otra cosa que ha cambiado?

442
00:34:13,170 --> 00:34:17,010
Aviso cuando nos fuimos algo fuera de la pila, que acaba de cambiar el tamaño,

443
00:34:17,010 --> 00:34:22,080
pero en este caso, tenemos un par de cosas que cambian.

444
00:34:22,080 --> 00:34:27,440
No sólo el cambio de tamaño, pero los cambios de cabeza.

445
00:34:27,440 --> 00:34:31,020
Esto va de nuevo a punto de Charlotte antes:

446
00:34:31,020 --> 00:34:38,699
¿por qué tenemos esta cabeza también?

447
00:34:38,699 --> 00:34:42,110
¿Tiene sentido ahora, Charlotte? Tipo de >>.

448
00:34:42,110 --> 00:34:47,500
[Hardison] Algo así? ¿Y qué pasó cuando nos quita de la cola?

449
00:34:47,500 --> 00:34:54,340
¿Qué hizo la cabeza hacer eso ahora es interesante?

450
00:34:54,340 --> 00:34:56,449
[Charlotte] Oh, porque cambió - está bien. Ya veo.

451
00:34:56,449 --> 00:35:02,090
Debido a que la cabeza - donde la cabeza apunta a los cambios en términos de la ubicación.

452
00:35:02,090 --> 00:35:07,200
Ya no es siempre el índice cero. >> Sí, exactamente.

453
00:35:07,200 --> 00:35:17,660
Lo que sucedió fue desencolado si el elemento de alta

454
00:35:17,660 --> 00:35:20,590
se hizo y no teníamos este campo de la cabeza

455
00:35:20,590 --> 00:35:26,880
porque siempre estábamos llamando a esta cadena a 0 Índice de la cabeza de nuestra cola,

456
00:35:26,880 --> 00:35:30,170
entonces tendríamos que pasar el resto de la cola hacia abajo.

457
00:35:30,170 --> 00:35:36,010
Tendríamos que cambiar "bye" de en cadenas [1] para las cadenas [0].

458
00:35:36,010 --> 00:35:38,760
Y las cadenas [2] hasta llegar a las cadenas [1].

459
00:35:38,760 --> 00:35:43,050
Y tendríamos que hacer esto por toda la lista de elementos,

460
00:35:43,050 --> 00:35:45,110
todo el conjunto de elementos.

461
00:35:45,110 --> 00:35:50,490
Y cuando hacemos esto con una matriz, que se pone muy costoso.

462
00:35:50,490 --> 00:35:53,340
Así que aquí, no es una gran cosa. Sólo tenemos tres elementos de nuestra matriz.

463
00:35:53,340 --> 00:35:57,230
Pero si tuviéramos una cola de un millar de elementos o un millón de elementos,

464
00:35:57,230 --> 00:36:00,060
y luego, de repente, empezamos a hacer un montón de quitar de la cola llama a todos en un bucle,

465
00:36:00,060 --> 00:36:03,930
las cosas realmente van a disminuir a medida que se desplaza por todo constantemente.

466
00:36:03,930 --> 00:36:07,320
Ya sabes, cambiar por 1, por un cambio, cambio por 1, cambio en 1.

467
00:36:07,320 --> 00:36:13,650
En su lugar, se utiliza esta cabeza, lo llamamos un "puntero", aunque en realidad no es un puntero

468
00:36:13,650 --> 00:36:16,430
en sentido estricto, no es un tipo de puntero.

469
00:36:16,430 --> 00:36:19,410
No es un * int o char * ni nada de eso.

470
00:36:19,410 --> 00:36:28,930
Pero se señala o indica el jefe de nuestra cola. ¿Sí?

471
00:36:28,930 --> 00:36:38,800
>> [Estudiante] ¿Cómo quitar de la cola saber hacer estallar justo al lado de lo que está a la cabeza?

472
00:36:38,800 --> 00:36:43,620
[Hardison] ¿Cómo quitar de la cola saber cómo hacer estallar todo lo que está en la cabeza? Derecho >>, sí.

473
00:36:43,620 --> 00:36:49,050
>> Lo que está viendo es simplemente cualquiera que sea el campo de cabecera se establece en.

474
00:36:49,050 --> 00:36:52,710
Así que en este primer caso, si miramos aquí mismo,

475
00:36:52,710 --> 00:36:55,690
nuestra cabeza es 0, 0 índice. >> Derecho.

476
00:36:55,690 --> 00:37:00,500
[Hardison] Tan sólo dice bien, bien, el elemento en el índice 0, la cadena "hola",

477
00:37:00,500 --> 00:37:03,050
Es el elemento a la cabeza de nuestra cola.

478
00:37:03,050 --> 00:37:05,570
Así que vamos a quitar de la cola de ese tipo.

479
00:37:05,570 --> 00:37:09,800
Y eso va a ser el elemento que se devuelve al llamador.

480
00:37:09,800 --> 00:37:14,540
Sí, Saad? >> Así que la cabeza, básicamente, establece la - a donde vas a índice?

481
00:37:14,540 --> 00:37:17,750
Ese es el comienzo de la misma? Sí >>. >> Okay.

482
00:37:17,750 --> 00:37:22,900
[Hardison] Eso es convertirse en el nuevo comienzo de nuestra matriz.

483
00:37:22,900 --> 00:37:28,930
Así que cuando usted quitar de la cola algo, todo lo que tienes que hacer es acceder al elemento en el índice q.head,

484
00:37:28,930 --> 00:37:32,240
y que será el elemento que desea quitar de la cola.

485
00:37:32,240 --> 00:37:34,930
Usted también tiene que disminuir el tamaño.

486
00:37:34,930 --> 00:37:39,430
Vamos a ver un poco en donde las cosas se ponen un poco difícil con esto.

487
00:37:39,430 --> 00:37:46,520
Nos quitar de la cola, y ahora, si nos encolar nuevamente,

488
00:37:46,520 --> 00:37:51,300
¿dónde encolar?

489
00:37:51,300 --> 00:37:55,000
¿De dónde viene el elemento siguiente ir en nuestra cola?

490
00:37:55,000 --> 00:37:57,980
Digamos que queremos poner en cola la cadena "CS".

491
00:37:57,980 --> 00:38:02,240
En qué índice se ha ido? [Los estudiantes] Strings [2]. >> Dos.

492
00:38:02,240 --> 00:38:04,980
¿Por qué no 2 y 0?

493
00:38:04,980 --> 00:38:13,570
[Basil] Porque ahora la cabeza es 1, por lo que es como el inicio de la lista?

494
00:38:13,570 --> 00:38:21,220
[Hardison] Derecho. Y lo que indica el final de la lista?

495
00:38:21,220 --> 00:38:23,290
¿De qué estábamos usando para indicar el final de nuestra cola?

496
00:38:23,290 --> 00:38:25,970
La cabeza es la cabeza de nuestra cola, el principio de nuestra cola.

497
00:38:25,970 --> 00:38:29,530
¿Cuál es el fin de nuestra cola? [Los estudiantes] tamaño. >> Tamaño, exactamente.

498
00:38:29,530 --> 00:38:36,360
Así que nuestros nuevos elementos a ir en tamaño, y los elementos que tomamos de salir en cabeza.

499
00:38:36,360 --> 00:38:45,390
Al poner en cola el siguiente elemento, lo estamos poniendo a tamaño.

500
00:38:45,390 --> 00:38:48,530
[Estudiante] Antes de poner eso en si, el tamaño era de 1, ¿no?

501
00:38:48,530 --> 00:38:55,690
[Hardison] Derecho. Así que no bastante en tamaño. Tamaño + no, +1, pero la cabeza +.

502
00:38:55,690 --> 00:38:59,990
Debido a que cambió todo por la cantidad cabeza.

503
00:38:59,990 --> 00:39:14,270
Así que aquí, ahora tenemos una cola de tamaño 1 que comienza en el índice 1.

504
00:39:14,270 --> 00:39:20,730
La cola es de índice 2. ¿Sí?

505
00:39:20,730 --> 00:39:25,780
>> [Estudiante] ¿Qué sucede cuando usted dequeue cadenas [0], y las ranuras de las cuerdas en la memoria

506
00:39:25,780 --> 00:39:29,420
sólo se vacían, en el fondo, o simplemente olvidado?

507
00:39:29,420 --> 00:39:34,700
[Hardison] Yeah. En este sentido, nos estamos olvidando.

508
00:39:34,700 --> 00:39:42,640
Si estuviéramos almacenar copias de ellos -

509
00:39:42,640 --> 00:39:46,310
muchas estructuras de datos a menudo se almacenan sus propias copias de los elementos

510
00:39:46,310 --> 00:39:51,760
de modo que la persona que gestiona la estructura de datos no tiene que preocuparse

511
00:39:51,760 --> 00:39:53,650
sobre el que todos los punteros se dirige.

512
00:39:53,650 --> 00:39:56,000
La estructura de datos se aferra a todo, se aferra a todas las copias,

513
00:39:56,000 --> 00:39:59,580
para asegurarse de que todo lo que persiste adecuadamente.

514
00:39:59,580 --> 00:40:03,140
Sin embargo, en este caso, estas estructuras de datos sólo, por simplicidad,

515
00:40:03,140 --> 00:40:05,580
no están haciendo copias de todo lo que estamos almacenando en ellos.

516
00:40:05,580 --> 00:40:08,630
[Estudiante] Por lo tanto se trata de una serie continua de -? Sí >>.

517
00:40:08,630 --> 00:40:14,350
Si miramos hacia atrás en lo que fue la definición de esta estructura, lo es.

518
00:40:14,350 --> 00:40:19,110
Es sólo un conjunto estándar como se ha visto,

519
00:40:19,110 --> 00:40:24,280
una matriz de char * s.

520
00:40:24,280 --> 00:40:26,340
¿Eso - >> Sí, me estaba preguntando

521
00:40:26,340 --> 00:40:29,130
si finalmente se quedará sin memoria, hasta cierto punto,

522
00:40:29,130 --> 00:40:32,330
si usted tiene todos estos lugares vacíos en la matriz?

523
00:40:32,330 --> 00:40:36,390
[Hardison] Sí, eso es un buen punto.

524
00:40:36,390 --> 00:40:41,530
>> Si nos fijamos en lo que ha ocurrido ahora en este momento,

525
00:40:41,530 --> 00:40:46,350
hemos llenado nuestra cola, como se ve.

526
00:40:46,350 --> 00:40:50,390
Pero en realidad no hemos llenado nuestra cola

527
00:40:50,390 --> 00:40:57,710
porque tenemos una cola que es talla 2, pero comienza en el índice 1,

528
00:40:57,710 --> 00:41:02,160
porque ahí es donde nuestro puntero cabeza.

529
00:41:02,160 --> 00:41:08,400
Como usted decía, ese elemento en cadenas [0], en el índice 0, no está realmente allí.

530
00:41:08,400 --> 00:41:10,450
No está en nuestra cola más.

531
00:41:10,450 --> 00:41:16,460
Simplemente no se molestó en entrar y escribir sobre ella cuando lo quite de la cola.

532
00:41:16,460 --> 00:41:18,700
Así que, aunque parece que nos hemos quedado sin memoria, que realmente no tienen.

533
00:41:18,700 --> 00:41:23,270
Ese lugar está disponible para nuestro uso.

534
00:41:23,270 --> 00:41:29,310
El comportamiento apropiado, si fuéramos a tratar de quitar de la cola y la primera cosa

535
00:41:29,310 --> 00:41:34,420
como "adiós", que debería salir despedida fuera.

536
00:41:34,420 --> 00:41:38,460
Ahora nuestro cola empieza en el índice 2 y es de tamaño 1.

537
00:41:38,460 --> 00:41:42,240
Y ahora, si tratamos de poner en cola algo más, digamos 50,

538
00:41:42,240 --> 00:41:47,880
50 años deben ir en este punto en el índice 0

539
00:41:47,880 --> 00:41:51,270
porque todavía disponible para nosotros. Sí, Saad?

540
00:41:51,270 --> 00:41:53,630
[Saad] ¿Esto sucederá de forma automática?

541
00:41:53,630 --> 00:41:56,150
[Hardison] No pasa absolutamente automáticamente. Hay que hacer las cuentas

542
00:41:56,150 --> 00:42:00,380
para hacer que funcione, pero en esencia lo que hemos hecho es que hemos acaba de terminar su alrededor.

543
00:42:00,380 --> 00:42:04,070
[Saad] Y está bien si este tiene un agujero en el medio de ella?

544
00:42:04,070 --> 00:42:08,720
[Hardison] Lo es si podemos hacer que las matemáticas funcionan de manera adecuada.

545
00:42:08,720 --> 00:42:15,470
>> Y resulta que eso no es realmente tan difícil de hacer con el operador mod.

546
00:42:15,470 --> 00:42:20,040
Así que al igual que hicimos con César y el material criptográfico,

547
00:42:20,040 --> 00:42:25,190
utilizando mod, podemos hacer las cosas para envolver y seguir adelante

548
00:42:25,190 --> 00:42:28,090
alrededor y alrededor y alrededor con nuestra cola,

549
00:42:28,090 --> 00:42:32,180
mantener ese puntero cabeza se mueve alrededor.

550
00:42:32,180 --> 00:42:38,840
Observe que el tamaño está respetando siempre el número de elementos en realidad dentro de la cola.

551
00:42:38,840 --> 00:42:43,110
Y es sólo el puntero de cabeza que se mantiene en bicicleta a través.

552
00:42:43,110 --> 00:42:49,660
Si nos fijamos en lo que sucedió aquí, si nos remontamos al principio,

553
00:42:49,660 --> 00:42:55,020
y que acaba de ver lo que sucede en la cabeza

554
00:42:55,020 --> 00:42:58,240
cuando encolar algo, no pasó nada en la cabeza.

555
00:42:58,240 --> 00:43:00,970
Cuando en cola otra cosa, no pasó nada en la cabeza.

556
00:43:00,970 --> 00:43:04,130
Tan pronto como se quita de la cola algo, la cabeza se incrementa en uno.

557
00:43:04,130 --> 00:43:06,600
Tenemos algo en cola, no pasa nada en la cabeza.

558
00:43:06,600 --> 00:43:11,060
Al quitar de la cola algo, de repente la cabeza se incrementa.

559
00:43:11,060 --> 00:43:14,660
Cuando encolar algo, no pasa nada a la cabeza.

560
00:43:14,660 --> 00:43:20,240
>> ¿Qué pasaría en este momento si tuviéramos que quitar de la cola algo nuevo?

561
00:43:20,240 --> 00:43:23,240
¿Alguna idea? ¿Qué le pasaría a la cabeza?

562
00:43:23,240 --> 00:43:27,190
¿Qué debe pasar con la cabeza

563
00:43:27,190 --> 00:43:32,990
si tuviéramos que quitar de la cola algo más?

564
00:43:32,990 --> 00:43:35,400
La cabeza ahora mismo está en el índice 2,

565
00:43:35,400 --> 00:43:38,920
lo que significa que la cabeza de la cola es strings [2].

566
00:43:38,920 --> 00:43:44,280
[Estudiante] Lo cual devuelve 0? >> Se debe volver a 0. Se debe envolver la vuelta, exactamente.

567
00:43:44,280 --> 00:43:48,440
Hasta ahora, cada vez que se llama quitar de la cola, hemos estado agregando uno a la cabeza,

568
00:43:48,440 --> 00:43:50,960
añadir uno a la cabeza, agregar uno a la cabeza, agregar uno a la cabeza.

569
00:43:50,960 --> 00:43:58,400
Tan pronto como el puntero de cabeza llega al último índice en nuestra matriz,

570
00:43:58,400 --> 00:44:05,650
entonces tenemos que concluir la vuelta al principio, vuelve a 0.

571
00:44:05,650 --> 00:44:09,900
[Charlotte] ¿Qué determina la capacidad de la cola en una pila?

572
00:44:09,900 --> 00:44:13,120
[Hardison] En este caso, sólo hemos estado utilizando una constante # define. >> Okay.

573
00:44:13,120 --> 00:44:19,590
[Hardison] en el archivo actual. C, se puede ir en barro y con él un poco

574
00:44:19,590 --> 00:44:21,710
y hacerlo tan grande o tan pequeño como usted quiera.

575
00:44:21,710 --> 00:44:25,310
[Charlotte] Así que cuando usted está haciendo una cola, ¿cómo hacer que el equipo sabe

576
00:44:25,310 --> 00:44:29,120
el tamaño que desea que la pila sea?

577
00:44:29,120 --> 00:44:31,700
[Hardison] Eso es una gran pregunta.

578
00:44:31,700 --> 00:44:34,800
Hay un par de maneras. Una de ellas es simplemente definir por adelantado

579
00:44:34,800 --> 00:44:42,050
y decir que esto va a ser una cola que tiene 4 elementos o elementos 50 o 10.000.

580
00:44:42,050 --> 00:44:45,430
La otra forma es hacer lo que la gente de edición de hackers están haciendo

581
00:44:45,430 --> 00:44:52,310
y crear funciones para que su cola crece dinámicamente a medida que se añaden más cosas pulg

582
00:44:52,310 --> 00:44:54,740
>> [Charlotte] Así que para ir con la primera opción, lo que la sintaxis se utiliza

583
00:44:54,740 --> 00:44:57,830
para decirle al programa cuál es el tamaño de la cola?

584
00:44:57,830 --> 00:45:04,780
[Hardison] Ah. Así que vamos a salir de esto.

585
00:45:04,780 --> 00:45:12,650
Todavía estoy en stack.c aquí, así que sólo voy a desplazarse hasta la parte superior aquí.

586
00:45:12,650 --> 00:45:17,920
¿Puedes ver esto aquí? Este es el # define capacidad 10.

587
00:45:17,920 --> 00:45:24,600
Y esto es casi exactamente la misma sintaxis que tenemos para la cola.

588
00:45:24,600 --> 00:45:28,390
Excepto en la cola, tenemos que struct campo adicional aquí.

589
00:45:28,390 --> 00:45:32,760
[Charlotte] Oh, pensé que la capacidad de decir la capacidad de la cadena.

590
00:45:32,760 --> 00:45:36,770
[Hardison] Ah. >> Esta es la longitud máxima de la palabra. >> Lo tengo.

591
00:45:36,770 --> 00:45:41,180
Si. La capacidad aquí - que es un gran punto.

592
00:45:41,180 --> 00:45:44,000
Y esto es algo que es difícil

593
00:45:44,000 --> 00:45:49,480
porque lo que hemos declarado aquí es una matriz de char * s.

594
00:45:49,480 --> 00:45:52,770
Una matriz de punteros.

595
00:45:52,770 --> 00:45:56,690
Este es un arreglo de caracteres.

596
00:45:56,690 --> 00:46:01,690
Esto es probablemente lo que he visto cuando he estado declarando sus buffers para el archivo de E / S,

597
00:46:01,690 --> 00:46:06,840
cuando usted ha sido la creación de cadenas de forma manual en la pila.

598
00:46:06,840 --> 00:46:09,090
Sin embargo, lo que tenemos aquí es una matriz de char * s.

599
00:46:09,090 --> 00:46:13,400
Así que es una matriz de punteros.

600
00:46:13,400 --> 00:46:18,350
En realidad, si se amplía hacia fuera y vemos lo que está pasando aquí

601
00:46:18,350 --> 00:46:23,140
en la presentación, se ve que los elementos reales, los datos de carácter

602
00:46:23,140 --> 00:46:26,180
no se almacena dentro de la propia matriz.

603
00:46:26,180 --> 00:46:42,690
¿Qué está almacenada dentro de nuestra amplia aquí son punteros a los datos de caracteres.

604
00:46:42,690 --> 00:46:52,560
Bien. Así hemos visto cómo el tamaño de la cola es igual que con la pila,

605
00:46:52,560 --> 00:46:58,670
el tamaño respeta siempre el número de elementos actualmente en la cola.

606
00:46:58,670 --> 00:47:02,720
Después de hacer 2 pone en cola, el tamaño es 2.

607
00:47:02,720 --> 00:47:07,110
Después de hacer una dequeue el tamaño es ahora 1.

608
00:47:07,110 --> 00:47:09,330
Después de hacer otro en cola el tamaño es una copia de seguridad a 2.

609
00:47:09,330 --> 00:47:12,340
Así, el tamaño definitivamente respete el número de elementos en la cola,

610
00:47:12,340 --> 00:47:15,580
y luego la cabeza sólo sigue el ciclismo.

611
00:47:15,580 --> 00:47:20,210
Va de 0-1-2, 0-1-2, 0-1-2.

612
00:47:20,210 --> 00:47:25,620
Y cada vez que llamamos a quitar de la cola, el puntero de cabeza se incrementa al índice siguiente.

613
00:47:25,620 --> 00:47:29,930
Y si la cabeza está a punto de pasar, se vuelve de nuevo a 0.

614
00:47:29,930 --> 00:47:34,870
Así que con eso, podemos escribir la función de quitar de la cola.

615
00:47:34,870 --> 00:47:40,200
Y vamos a salir de la función de puesta en cola para ustedes para poner en práctica en su lugar.

616
00:47:40,200 --> 00:47:45,880
>> Al quitar de la cola un elemento de nuestra cola,

617
00:47:45,880 --> 00:47:55,490
¿qué fue lo primero que hizo Daniel cuando comenzamos a escribir la función pop para pilas?

618
00:47:55,490 --> 00:48:00,490
Quiero oír de alguien que no ha hablado todavía.

619
00:48:00,490 --> 00:48:06,710
Vamos a ver, Saad, ¿te acuerdas de lo que Daniel hizo lo que la primera cosa cuando escribió pop?

620
00:48:06,710 --> 00:48:08,860
[Saad] No se, fue - >> Probó por algo.

621
00:48:08,860 --> 00:48:12,140
[Saad] Si el tamaño es mayor que 0. >> Exactamente.

622
00:48:12,140 --> 00:48:14,390
¿Y qué era que las pruebas de?

623
00:48:14,390 --> 00:48:19,090
[Saad] Eso estaba probando para ver si hay algo en el interior de la matriz.

624
00:48:19,090 --> 00:48:23,210
[Hardison] Yeah. Exactamente. Por lo que no puede hacer estallar cualquier cosa fuera de la pila si está vacío.

625
00:48:23,210 --> 00:48:26,510
Del mismo modo, no se puede quitar de la cola desde una cola si está vacío.

626
00:48:26,510 --> 00:48:30,420
¿Qué es lo primero que debemos hacer en nuestra función de quitar de la cola aquí, ¿te parece?

627
00:48:30,420 --> 00:48:33,860
[Saad] Si el tamaño es mayor que 0? Sí >>.

628
00:48:33,860 --> 00:48:37,710
En este caso, he hecho sólo una prueba para ver si es 0.

629
00:48:37,710 --> 00:48:42,240
Si es 0, se puede devolver null.

630
00:48:42,240 --> 00:48:45,280
Pero la lógica misma.

631
00:48:45,280 --> 00:48:49,110
Y vamos a seguir con esto.

632
00:48:49,110 --> 00:48:54,600
Si el tamaño no es 0, ¿dónde está el elemento que desea quitar de la cola?

633
00:48:54,600 --> 00:48:58,550
[Saad] A la cabeza? >> Exactamente.

634
00:48:58,550 --> 00:49:01,720
Sólo podemos sacar el primer elemento de nuestra cola

635
00:49:01,720 --> 00:49:07,040
mediante el acceso al elemento en la cabeza.

636
00:49:07,040 --> 00:49:14,630
Nada loco.

637
00:49:14,630 --> 00:49:19,620
Después de eso, ¿qué debemos hacer? ¿Qué tiene que pasar?

638
00:49:19,620 --> 00:49:23,740
¿Cuál era la otra cosa que hemos hablado en quitar de la cola?

639
00:49:23,740 --> 00:49:28,130
Dos cosas tienen que ocurrir, porque nuestra cola ha cambiado.

640
00:49:28,130 --> 00:49:35,640
[Daniel] Reducir el tamaño. >> Tenemos que reducir el tamaño y aumentar la cabeza? Exactamente.

641
00:49:35,640 --> 00:49:40,600
Para aumentar la cabeza, no podemos simplemente a ciegas aumentan la cabeza, recuerda.

642
00:49:40,600 --> 00:49:45,080
No podemos hacer queue.head + +.

643
00:49:45,080 --> 00:49:51,630
Tenemos que incluir también este mod por la capacidad.

644
00:49:51,630 --> 00:49:54,740
¿Y por qué mod por la capacidad, Stella?

645
00:49:54,740 --> 00:49:58,680
[Stella] Porque tiene que envolver. >> Exactamente.

646
00:49:58,680 --> 00:50:04,750
Nos mod por la capacidad, ya que tiene que envolver alrededor de nuevo a 0.

647
00:50:04,750 --> 00:50:07,400
Así que ahora, en este punto, podemos hacer lo que dijo Daniel.

648
00:50:07,400 --> 00:50:12,700
Podemos disminuir el tamaño.

649
00:50:12,700 --> 00:50:29,170
Y entonces sólo puede devolver el elemento que estaba en la parte superior de la cola.

650
00:50:29,170 --> 00:50:34,000
Se parece un poco al principio gnarly. Es posible que tenga una pregunta. ¿Cómo dice?

651
00:50:34,000 --> 00:50:37,260
>> [Sam] ¿Por qué es primero en la parte superior de la cola? ¿De dónde viene eso?

652
00:50:37,260 --> 00:50:42,480
[Hardison] Viene de la cuarta línea de la parte inferior.

653
00:50:42,480 --> 00:50:46,060
Después de realizar pruebas para asegurarse de que nuestra cola no está vacía,

654
00:50:46,060 --> 00:50:54,100
nos retiramos char * primero, sacar el elemento que está sentado en el índice cabeza

655
00:50:54,100 --> 00:50:58,680
de nuestra matriz, de nuestra amplia cuerdas, llamada >> y que por primera vez?

656
00:50:58,680 --> 00:51:04,500
[Hardison] Y lo llamamos primero. Si.

657
00:51:04,500 --> 00:51:09,850
Sólo para dar seguimiento a eso, ¿por qué crees que teníamos que hacer eso?

658
00:51:09,850 --> 00:51:18,270
[Sam] Cada primero se acaban de volver q.strings [q.head]? Sí >>.

659
00:51:18,270 --> 00:51:23,830
>> Porque estamos haciendo este cambio de la q.head con la función mod,

660
00:51:23,830 --> 00:51:27,810
y no hay manera de hacerlo dentro de la línea de retorno también.

661
00:51:27,810 --> 00:51:31,640
[Hardison] Exactamente. Usted es el clavo. Sam está totalmente en el clavo.

662
00:51:31,640 --> 00:51:36,800
La razón por la que tuvo que retirarse el primer elemento de nuestra cola y almacenarlo en una variable

663
00:51:36,800 --> 00:51:43,030
se debe a que esta línea donde habíamos q.head justo,

664
00:51:43,030 --> 00:51:47,030
ahí está el operador mod en que no es algo que podamos hacer

665
00:51:47,030 --> 00:51:51,230
y que tenga efecto en la cabeza sin - en una sola línea.

666
00:51:51,230 --> 00:51:54,480
Así que en realidad tenemos que sacar al primer elemento, a continuación, ajuste la cabeza,

667
00:51:54,480 --> 00:52:00,430
ajustar el tamaño, y luego devolver el elemento que nos retiramos.

668
00:52:00,430 --> 00:52:02,680
Y esto es algo que veremos surgir más tarde con

669
00:52:02,680 --> 00:52:04,920
listas enlazadas, como jugar con ellos.

670
00:52:04,920 --> 00:52:08,410
A menudo, cuando usted está liberando o la eliminación de las listas enlazadas

671
00:52:08,410 --> 00:52:13,500
es necesario recordar el siguiente elemento, el puntero siguiente de una lista enlazada

672
00:52:13,500 --> 00:52:16,330
antes de disponer de la actual.

673
00:52:16,330 --> 00:52:23,580
Porque de otra manera de deshacerse de la información de lo que queda en la lista.

674
00:52:23,580 --> 00:52:34,160
Ahora, si usted va a su dispositivo, se abre queue.c--x de esto.

675
00:52:34,160 --> 00:52:39,390
Así que si abro queue.c, déjame zoom aquí,

676
00:52:39,390 --> 00:52:44,970
verás que tiene un archivo de aspecto similar.

677
00:52:44,970 --> 00:52:49,200
De aspecto similar al archivo de lo que teníamos antes con stack.c.

678
00:52:49,200 --> 00:52:54,690
Tenemos nuestra estructura de cola definida tal y como vimos en las diapositivas.

679
00:52:54,690 --> 00:52:59,870
>> Tenemos nuestra función en cola que es para que usted pueda hacer.

680
00:52:59,870 --> 00:53:04,340
Y tenemos la función de quitar de la cola aquí.

681
00:53:04,340 --> 00:53:06,870
La función de quitar de la cola en el archivo no se ha implementado,

682
00:53:06,870 --> 00:53:13,230
pero lo voy a poner de nuevo en el PowerPoint para que pueda escribirlo, si lo desea.

683
00:53:13,230 --> 00:53:16,690
Así que para los próximos 5 minutos más o menos, ustedes trabajan en enqueue

684
00:53:16,690 --> 00:53:22,570
que es casi lo contrario de quitar de la cola.

685
00:53:22,570 --> 00:53:29,560
Usted no tiene que ajustar la cabeza cuando estás encolamos, pero ¿qué tiene que ajustar?

686
00:53:29,560 --> 00:53:38,920
Tamaño. Así que cuando en cola, la cabeza se mantiene intacto, el tamaño se cambia.

687
00:53:38,920 --> 00:53:46,920
Pero se necesita un poco de - usted tendrá que jugar con ese mod

688
00:53:46,920 --> 00:53:57,560
de averiguar exactamente lo que el índice del elemento nuevo debe insertarse al.

689
00:53:57,560 --> 00:54:03,080
Así que voy a dar a ustedes un poco, poner quitar de la cola de nuevo en la diapositiva,

690
00:54:03,080 --> 00:54:05,200
y como ustedes tienen preguntas, les gritan para que podamos

691
00:54:05,200 --> 00:54:09,220
todos hablan de ellos como grupo.

692
00:54:09,220 --> 00:54:13,960
Además, con el tamaño que no - al ajustar el tamaño, siempre puedes hacer solo -

693
00:54:13,960 --> 00:54:18,720
Qué tiene que mod el tamaño cada vez? [Daniel] >> No. Usted no tiene que mod del tamaño, claro.

694
00:54:18,720 --> 00:54:24,260
Debido a que el tamaño siempre, si TU ESTAS - asumiendo que usted está manejando las cosas adecuadamente,

695
00:54:24,260 --> 00:54:30,840
el tamaño siempre será de entre 0 y 3.

696
00:54:30,840 --> 00:54:38,680
¿Dónde hay que mod cuando estás haciendo en cola?

697
00:54:38,680 --> 00:54:41,060
[Estudiante] Sólo para la cabeza. >> Solo para la cabeza, exactamente.

698
00:54:41,060 --> 00:54:44,620
¿Y por qué tienes que mod en absoluto en enqueue?

699
00:54:44,620 --> 00:54:48,830
Cuando se trata de una situación en la que tendría que mod?

700
00:54:48,830 --> 00:54:53,630
[Estudiante] Si tienes cosas en espacios, como en los espacios 1 y 2,

701
00:54:53,630 --> 00:54:55,950
y entonces tenía que añadir algo a 0.

702
00:54:55,950 --> 00:55:02,570
[Hardison] Sí, exactamente. Así que si su cabeza es puntero en el final,

703
00:55:02,570 --> 00:55:14,210
o si el tamaño de su cabeza es más grande, o más bien, se va a envolver alrededor de la cola.

704
00:55:14,210 --> 00:55:17,830
>> Así que en esta situación que tenemos aquí en la diapositiva en este momento,

705
00:55:17,830 --> 00:55:24,370
si quiero poner en cola algo en este momento,

706
00:55:24,370 --> 00:55:31,110
queremos poner en cola algo en el índice 0.

707
00:55:31,110 --> 00:55:35,450
Así que si nos fijamos en que el 50 va y me llama enqueue 50,

708
00:55:35,450 --> 00:55:40,840
y sale allí abajo en la parte inferior. Va en índice 0.

709
00:55:40,840 --> 00:55:44,160
Sustituye a la 'hola' que fue quitado de la cola ya.

710
00:55:44,160 --> 00:55:46,210
[Daniel] No se cuida de que en quitar de la cola ya?

711
00:55:46,210 --> 00:55:50,550
¿Por qué hacer algo con la cabeza puesta en cola?

712
00:55:50,550 --> 00:55:55,770
[Hardison] Oh, así que no estamos modificando la cabeza, lo siento.

713
00:55:55,770 --> 00:56:02,310
Pero usted tiene que utilizar el operador mod cuando se está accediendo

714
00:56:02,310 --> 00:56:04,250
el elemento que desea poner en cola cuando se está accediendo

715
00:56:04,250 --> 00:56:06,960
el siguiente elemento en la cola.

716
00:56:06,960 --> 00:56:10,960
[Basil] Yo no lo hice, y me dieron el "éxito" en ese país.

717
00:56:10,960 --> 00:56:13,370
[Daniel] Oh, entiendo lo que estás diciendo.

718
00:56:13,370 --> 00:56:16,240
[Hardison] Así que didn't - usted acaba de hacer en q.size?

719
00:56:16,240 --> 00:56:20,670
[Basil] Yeah. Acabo de cambiar lados, yo no hice nada con la cabeza.

720
00:56:20,670 --> 00:56:24,300
[Hardison] En realidad no tiene que restablecer la cabeza para ser cualquier cosa,

721
00:56:24,300 --> 00:56:31,650
pero cuando se índice en la matriz cuerdas,

722
00:56:31,650 --> 00:56:39,500
de hecho tienes que seguir adelante y calcular donde el elemento siguiente es,

723
00:56:39,500 --> 00:56:44,230
porque withe la pila, el siguiente elemento de la pila siempre fue

724
00:56:44,230 --> 00:56:48,740
en el índice correspondiente al tamaño.

725
00:56:48,740 --> 00:56:55,850
Si echamos la vista atrás hacia nuestra función push pila,

726
00:56:55,850 --> 00:57:03,100
siempre podemos desembolsar en nuestro elemento nuevo a la derecha en el tamaño del índice.

727
00:57:03,100 --> 00:57:06,710
Mientras que con la cola, no podemos hacer eso

728
00:57:06,710 --> 00:57:10,340
porque si estamos en esta situación,

729
00:57:10,340 --> 00:57:18,130
si tenemos en cola 50 nuestra cadena de nuevo a la derecha en cadenas [1]

730
00:57:18,130 --> 00:57:20,540
que no queremos hacer.

731
00:57:20,540 --> 00:57:41,200
Queremos tener la nueva cadena va en el índice 0.

732
00:57:41,200 --> 00:57:44,320
>> ¿Alguien - ¿Sí? [Estudiante] Tengo una pregunta, pero no es realmente relacionados.

733
00:57:44,320 --> 00:57:48,160
¿Qué significa cuando alguien se llama algo así como puntero pred?

734
00:57:48,160 --> 00:57:51,260
¿Cuál es la abreviatura de ese nombre? Sé que es sólo un nombre.

735
00:57:51,260 --> 00:57:59,110
[Hardison] Pred puntero? Vamos a ver. ¿En qué contexto?

736
00:57:59,110 --> 00:58:01,790
[Estudiante] Era para la inserción. Te puedo preguntar después si quieres

737
00:58:01,790 --> 00:58:03,920
porque no es realmente relacionados, pero sólo I -

738
00:58:03,920 --> 00:58:07,300
[Hardison] Desde el código de inserción de David de conferencia?

739
00:58:07,300 --> 00:58:10,860
Podemos lograr eso y hablar de eso.

740
00:58:10,860 --> 00:58:15,550
Hablaremos de eso después, una vez que lleguemos a listas enlazadas.

741
00:58:15,550 --> 00:58:21,440
>> Así que vamos muy rápido vistazo a lo que la función de puesta en cola parece.

742
00:58:21,440 --> 00:58:26,530
¿Qué fue lo primero que la gente trató de hacer en su línea de puesta en cola? En esta cola?

743
00:58:26,530 --> 00:58:29,960
Al igual que lo que hiciste por pila empujando.

744
00:58:29,960 --> 00:58:32,080
¿Qué hiciste, Stella?

745
00:58:32,080 --> 00:58:35,050
[Stella, ininteligible]

746
00:58:35,050 --> 00:58:45,700
[Hardison] Exactamente. Si (q.size CAPACIDAD ==) -

747
00:58:45,700 --> 00:58:54,720
Tengo que poner mis llaves en el lugar correcto - devuelve falso.

748
00:58:54,720 --> 00:59:01,370
Acercar un poco. Bien.

749
00:59:01,370 --> 00:59:03,800
Ahora, ¿qué es lo siguiente que tenemos que hacer?

750
00:59:03,800 --> 00:59:11,370
Al igual que con la pila, y se inserta en el lugar correcto.

751
00:59:11,370 --> 00:59:16,010
Y lo que era el lugar adecuado para insertar eso?

752
00:59:16,010 --> 00:59:23,170
Con la pila era tamaño del índice, con esto no es exactamente eso.

753
00:59:23,170 --> 00:59:30,210
[Daniel] Tengo q.head--o - q.strings >>? >> Yeah.

754
00:59:30,210 --> 00:59:40,470
q.strings [+ q.head q.size mod CAPACIDAD]?

755
00:59:40,470 --> 00:59:42,740
[Hardison] Es probable que quiera poner entre paréntesis esta

756
00:59:42,740 --> 00:59:48,830
por lo que estamos recibiendo la adecuada prioridad y por lo que es cleart a todo el mundo.

757
00:59:48,830 --> 00:59:55,800
Y establece que la igualdad? >> Para str? >> Para str. Grande.

758
00:59:55,800 --> 01:00:00,160
Y ahora, ¿qué es lo último que tenemos que hacer?

759
01:00:00,160 --> 01:00:06,780
Al igual que hicimos en la pila. >> Incrementar el tamaño? >> Incrementar el tamaño.

760
01:00:06,780 --> 01:00:13,830
Boom. Y luego, ya que el código de arranque sólo devuelve false de forma predeterminada,

761
01:00:13,830 --> 01:00:27,460
queremos cambiar esta propiedad a true si todo va a través y todo va bien.

762
01:00:27,460 --> 01:00:33,050
Está bien. Eso es un montón de información para la sección.

763
01:00:33,050 --> 01:00:39,480
No estamos muy encima. Queremos hablar muy rápido sobre simplemente enlazada listas.

764
01:00:39,480 --> 01:00:44,010
Voy a poner esto para que podamos volver a ella más tarde.

765
01:00:44,010 --> 01:00:50,850
Pero volvamos a nuestra presentación por unos pocos más diapositivas.

766
01:00:50,850 --> 01:00:53,790
Así enqueue es TODO, ahora lo hemos hecho.

767
01:00:53,790 --> 01:00:57,430
>> Ahora echemos un vistazo a simplemente enlazada listas.

768
01:00:57,430 --> 01:01:00,040
Hablamos de estos un poco más en clase.

769
01:01:00,040 --> 01:01:02,540
¿Cuántos de ustedes vieron la demostración en la que había gente

770
01:01:02,540 --> 01:01:08,220
torpemente señalando a cada uno de los otros números y explotación? >> Yo estaba en eso.

771
01:01:08,220 --> 01:01:16,620
>> ¿Qué piensan ustedes? ¿Eso, espero que desmitificar estos poco un poco?

772
01:01:16,620 --> 01:01:25,990
Con una lista, resulta que nos ocupamos de este tipo que vamos a llamar a un nodo.

773
01:01:25,990 --> 01:01:32,520
Mientras que con la cola y pila que nos tomamos las estructuras que nos llaman a la cola en la pila,

774
01:01:32,520 --> 01:01:34,860
teníamos estas nueva cola en los tipos de pila,

775
01:01:34,860 --> 01:01:39,240
aquí una lista está realmente formado por un grupo de nodos.

776
01:01:39,240 --> 01:01:45,920
De la misma manera que las cadenas son más que un montón de caracteres todos alineados uno al lado del otro.

777
01:01:45,920 --> 01:01:50,650
Una lista enlazada es sólo un nodo y nodo a otro ya otro nodo y el nodo a otro.

778
01:01:50,650 --> 01:01:55,080
Y en lugar de romper todos los nodos entre sí y su almacenamiento contigua

779
01:01:55,080 --> 01:01:58,090
todos uno al lado del otro en la memoria,

780
01:01:58,090 --> 01:02:04,470
teniendo este puntero siguiente nos permite almacenar los nodos donde sea, al azar.

781
01:02:04,470 --> 01:02:10,500
Y a continuación, tipo de alambre a todos juntos para señalar de una a la siguiente.

782
01:02:10,500 --> 01:02:15,850
>> ¿Y cuál fue la gran ventaja que esto tiene sobre una matriz?

783
01:02:15,850 --> 01:02:21,680
Durante todo el almacenamiento contigua justo pegado uno al lado del otro?

784
01:02:21,680 --> 01:02:24,190
¿Te acuerdas? ¿Sí? Asignación dinámica de memoria >>?

785
01:02:24,190 --> 01:02:27,220
>> Asignación dinámica de memoria en qué sentido?

786
01:02:27,220 --> 01:02:31,780
[Estudiante] En que se puede seguir haciendo más grande y usted no tiene que mover el conjunto completo?

787
01:02:31,780 --> 01:02:40,940
[Hardison] Exactamente. Así que con una matriz, cuando usted quiere poner un nuevo elemento en el medio de ella,

788
01:02:40,940 --> 01:02:45,320
usted tiene que cambiar todo para hacer espacio.

789
01:02:45,320 --> 01:02:47,880
Y como hablamos con la cola,

790
01:02:47,880 --> 01:02:50,080
es por eso que mantener ese puntero cabeza,

791
01:02:50,080 --> 01:02:52,050
por lo que no estamos cambiando constantemente las cosas.

792
01:02:52,050 --> 01:02:54,520
Debido a que resulta caro si tienes una gran variedad

793
01:02:54,520 --> 01:02:57,130
y que está constantemente haciendo estas inserciones aleatorias.

794
01:02:57,130 --> 01:03:00,820
Mientras que con una lista, lo único que tienes que hacer es tirar en un nuevo nodo,

795
01:03:00,820 --> 01:03:06,330
ajustar los punteros, y ya está.

796
01:03:06,330 --> 01:03:10,940
¿Qué mierda sobre esto?

797
01:03:10,940 --> 01:03:16,830
Aparte del hecho de que no es tan fácil de trabajar como una matriz? ¿Sí?

798
01:03:16,830 --> 01:03:22,980
[Daniel] Bueno, creo que es mucho más difícil tener acceso a un elemento específico de la lista enlazada?

799
01:03:22,980 --> 01:03:30,470
[Hardison] No se puede saltar a un elemento arbitrario en el medio de tu lista enlazada.

800
01:03:30,470 --> 01:03:33,800
¿Cómo se tiene que hacer en su lugar? >> Usted tiene que recorrer toda la cosa.

801
01:03:33,800 --> 01:03:35,660
[Hardison] Yeah. Usted tiene que ir a través de uno en uno, uno a la vez.

802
01:03:35,660 --> 01:03:38,480
Es un enorme - es un dolor.

803
01:03:38,480 --> 01:03:41,550
¿Cuál es la otra - no hay otra caída a esto.

804
01:03:41,550 --> 01:03:45,340
[Basil] No se puede ir hacia adelante y hacia atrás? Tienes que ir a una dirección?

805
01:03:45,340 --> 01:03:48,570
[Hardison] Yeah. Entonces, ¿cómo resolver esto, algunas veces?

806
01:03:48,570 --> 01:03:53,370
[Basil] doblemente enlazada listas? >> Exactamente. Hay listas doblemente enlazadas.

807
01:03:53,370 --> 01:03:55,540
Hay también - lo siento?

808
01:03:55,540 --> 01:03:57,620
>> [Sam] ¿Es eso lo mismo que usar lo que pred -

809
01:03:57,620 --> 01:04:01,090
Acabo de recordar, ¿no es lo que la cosa pred sirve?

810
01:04:01,090 --> 01:04:05,850
¿No es en el medio y doblemente solos?

811
01:04:05,850 --> 01:04:10,020
Mirada [Hardison] Vamos a qué es exactamente lo que estaba haciendo.

812
01:04:10,020 --> 01:04:15,760
Así que aquí vamos. Aquí está la lista de códigos.

813
01:04:15,760 --> 01:04:25,620
Aquí tenemos predptr, aquí. ¿Es esto lo que estabas hablando?

814
01:04:25,620 --> 01:04:30,750
Así que esta fue - que ha liberando una lista y que está tratando de almacenar un puntero a él.

815
01:04:30,750 --> 01:04:35,000
Esta no es la doblemente, ligada simple-listas.

816
01:04:35,000 --> 01:04:40,090
Podemos hablar más sobre esto más adelante ya que se habla de la liberación de la lista

817
01:04:40,090 --> 01:04:42,900
y quiero mostrar algunas otras cosas primero.

818
01:04:42,900 --> 01:04:51,480
pero es igual - es recordar el valor de ptr

819
01:04:51,480 --> 01:04:54,170
[Estudiante] Oh, es puntero precedente? Sí >>.

820
01:04:54,170 --> 01:05:04,070
Así que entonces sí puede incrementar ptr antes de entonces libre predptr lo es.

821
01:05:04,070 --> 01:05:09,130
Porque no podemos gratis ptr y luego llamar a ptr = ptr siguiente, ¿no?

822
01:05:09,130 --> 01:05:11,260
Eso sería malo.

823
01:05:11,260 --> 01:05:20,940
Así que vamos a ver, de nuevo a este hombre.

824
01:05:20,940 --> 01:05:23,900
>> La otra cosa mala acerca de las listas es que, si bien con una serie

825
01:05:23,900 --> 01:05:26,520
sólo tenemos todos los elementos mismos apilados uno junto al otro,

826
01:05:26,520 --> 01:05:29,050
aquí también hemos introducido este puntero.

827
01:05:29,050 --> 01:05:34,060
Así que hay una porción adicional de memoria que estamos teniendo que utilizar

828
01:05:34,060 --> 01:05:37,910
para cada elemento que se está almacenando en nuestra lista.

829
01:05:37,910 --> 01:05:40,030
Tenemos la flexibilidad, pero tiene un costo.

830
01:05:40,030 --> 01:05:42,230
Viene con el costo de tiempo,

831
01:05:42,230 --> 01:05:45,270
y viene con este coste de memoria también.

832
01:05:45,270 --> 01:05:47,800
Tiempo en el sentido de que ahora tenemos que ir a través de cada elemento de la matriz

833
01:05:47,800 --> 01:05:58,670
para encontrar el índice de uno a 10, o que habría sido índice 10 en una matriz.

834
01:05:58,670 --> 01:06:01,230
>> Sólo muy rápido, cuando nos diagrama cabo estas listas,

835
01:06:01,230 --> 01:06:05,980
normalmente nos aferramos a la cabeza de la lista o el primer indicador de la lista

836
01:06:05,980 --> 01:06:08,010
y cuenta que este es un puntero verdadero.

837
01:06:08,010 --> 01:06:11,100
Está a sólo 4 bytes. No es un nodo en sí.

838
01:06:11,100 --> 01:06:17,120
Así que ya ves que no tiene ningún valor int en ella, ningún puntero siguiente en el mismo.

839
01:06:17,120 --> 01:06:20,790
Es, literalmente, sólo un puntero.

840
01:06:20,790 --> 01:06:23,550
Se va a apuntar a algo que es una struct nodo actual.

841
01:06:23,550 --> 01:06:28,480
[Sam] Puntero llamado nodo? >> Esta es - no. Este es un puntero a algo de tipo nodo.

842
01:06:28,480 --> 01:06:32,540
Es un puntero a una estructura de nodo. >> Oh, está bien.

843
01:06:32,540 --> 01:06:36,870
Diagrama sobre el código de la izquierda, a la derecha.

844
01:06:36,870 --> 01:06:42,190
Podemos ponerlo en null, lo que es una buena manera de empezar.

845
01:06:42,190 --> 01:06:49,850
Cuando lo diagrama, o bien escribir como nulo o se pone una línea a través de él de esa manera.

846
01:06:49,850 --> 01:06:53,910
>> Una de las maneras más fáciles para trabajar con listas,

847
01:06:53,910 --> 01:06:57,430
y les pedimos hacer las dos cosas anteponer y anexar a ver las diferencias entre los dos,

848
01:06:57,430 --> 01:07:01,320
pero anteponiendo es definitivamente más fácil.

849
01:07:01,320 --> 01:07:05,790
Cuando se antepone, aquí es donde usted - cuando usted prepend (7),

850
01:07:05,790 --> 01:07:10,050
vas y crear la estructura de nodo

851
01:07:10,050 --> 01:07:13,870
y se establece primero en señalarlo, porque ahora, ya que se antepone,

852
01:07:13,870 --> 01:07:17,240
que va a estar al principio de la lista.

853
01:07:17,240 --> 01:07:22,540
Si prepend (3), que crea otro nodo, pero 3 ahora viene antes de las 7.

854
01:07:22,540 --> 01:07:31,130
Así que básicamente estás llevando las cosas a nuestra lista.

855
01:07:31,130 --> 01:07:34,720
Ahora, usted puede ver que anteponer, a veces lo llaman empujar,

856
01:07:34,720 --> 01:07:39,600
porque usted está empujando un nuevo elemento en su lista.

857
01:07:39,600 --> 01:07:43,270
También es fácil de borrar en la parte delantera de una lista.

858
01:07:43,270 --> 01:07:45,650
Así que la gente suele llamar a ese pop.

859
01:07:45,650 --> 01:07:52,200
Y de esa forma, se puede emular una pila utilizando una lista enlazada.

860
01:07:52,200 --> 01:07:57,880
Whoops. Lo siento, ahora estamos entrando en anexados. Así que aquí estamos antepuesto (7), ahora prepend (3).

861
01:07:57,880 --> 01:08:02,600
Si se antepone otra cosa en esta lista, si se antepone (4),

862
01:08:02,600 --> 01:08:06,540
entonces tendríamos 4 y luego 3 y luego 7.

863
01:08:06,540 --> 01:08:14,220
Entonces podríamos pop y quitar 4, quitar 3, retire 7.

864
01:08:14,220 --> 01:08:16,500
A menudo, la forma más intuitiva de pensar en esto es con anexados.

865
01:08:16,500 --> 01:08:20,310
Así que he diagramado lo que se vería con añadir aquí.

866
01:08:20,310 --> 01:08:23,380
En este sentido, añade (7) no se ve diferente

867
01:08:23,380 --> 01:08:25,160
porque sólo hay un elemento en la lista.

868
01:08:25,160 --> 01:08:28,620
Y añadiendo (3) lo pone al final.

869
01:08:28,620 --> 01:08:31,020
Tal vez usted puede ver ahora el truco con append

870
01:08:31,020 --> 01:08:36,600
es que desde que sólo sabe dónde está el principio de la lista es,

871
01:08:36,600 --> 01:08:39,450
para anexar a una lista de lo que tienes que caminar todo el camino a través de la lista

872
01:08:39,450 --> 01:08:46,500
para llegar a la final, detener, a continuación, crear el nodo y todo plunk abajo.

873
01:08:46,500 --> 01:08:50,590
Cablear todas las cosas.

874
01:08:50,590 --> 01:08:55,170
Así que con prefijo, como se acaba de copiar a través de este muy rápido,

875
01:08:55,170 --> 01:08:58,170
cuando se antepone a una lista, que es bastante simple.

876
01:08:58,170 --> 01:09:02,960
>> Usted hace su nuevo nodo, implican alguna asignación de memoria dinámica.

877
01:09:02,960 --> 01:09:09,830
Así que aquí estamos haciendo un struct nodo usando malloc.

878
01:09:09,830 --> 01:09:14,710
Así que estamos usando malloc, ya que va a dejar de lado la memoria por nosotros para más adelante

879
01:09:14,710 --> 01:09:20,350
porque no queremos que esto - queremos que esta memoria a persistir durante mucho tiempo.

880
01:09:20,350 --> 01:09:25,350
Y tenemos un puntero al espacio en la memoria que acaba de ser asignado.

881
01:09:25,350 --> 01:09:29,260
Utilizamos tamaño del nodo, no concretamos los campos.

882
01:09:29,260 --> 01:09:31,899
No generar manualmente el número de bytes,

883
01:09:31,899 --> 01:09:39,750
en lugar de eso usar sizeof para que sepamos que estamos recibiendo la cantidad adecuada de bytes.

884
01:09:39,750 --> 01:09:43,660
Nos aseguramos de probar que nuestra llamada malloc éxito.

885
01:09:43,660 --> 01:09:47,939
Esto es algo que quiero hacer en general.

886
01:09:47,939 --> 01:09:52,590
En las máquinas modernas, quedando sin memoria no es algo que es fácil

887
01:09:52,590 --> 01:09:56,610
a menos que la asignación de un montón de cosas y hacer una lista enorme,

888
01:09:56,610 --> 01:10:02,220
pero si usted está construyendo cosas para, por ejemplo, como un iPhone o Android an,

889
01:10:02,220 --> 01:10:05,230
que tienen recursos limitados de memoria, especialmente si usted está haciendo algo intenso.

890
01:10:05,230 --> 01:10:08,300
Así que es bueno tener en la práctica.

891
01:10:08,300 --> 01:10:10,510
>> Tenga en cuenta que he usado un par de funciones diferentes aquí

892
01:10:10,510 --> 01:10:12,880
que usted ha visto que son una especie de nuevo.

893
01:10:12,880 --> 01:10:15,870
Así fprintf es como printf

894
01:10:15,870 --> 01:10:21,320
excepto su primer argumento es la corriente a la que desea imprimir.

895
01:10:21,320 --> 01:10:23,900
En este caso, queremos imprimir en la cadena de error estándar

896
01:10:23,900 --> 01:10:29,410
que es diferente de la outStream estándar.

897
01:10:29,410 --> 01:10:31,620
Por defecto se muestra en el mismo lugar.

898
01:10:31,620 --> 01:10:34,600
También imprime a la terminal, pero se puede -

899
01:10:34,600 --> 01:10:38,790
utilizando los comandos que ha aprendido acerca de las técnicas de redireccionamiento,

900
01:10:38,790 --> 01:10:42,290
que aprendimos en vídeo de Tommy como conjunto de problemas 4, puede dirigirla

901
01:10:42,290 --> 01:10:47,900
a las diferentes áreas, a continuación, salir, aquí, sale de su programa.

902
01:10:47,900 --> 01:10:50,440
Básicamente se trata de como volver a principal,

903
01:10:50,440 --> 01:10:53,600
excepto que utilizamos salida porque aquí retorno no hará nada.

904
01:10:53,600 --> 01:10:57,140
No estamos en principal, por lo que regresa no se salga del programa como nosotros queremos.

905
01:10:57,140 --> 01:11:03,020
Por eso, utilizamos la función de salida y darle un código de error.

906
01:11:03,020 --> 01:11:11,890
Entonces aquí nos pusimos campo del nuevo nodo de valor, su campo i sea igual a i, y luego lo cablear.

907
01:11:11,890 --> 01:11:15,530
Hemos establecido puntero siguiente del nuevo nodo para señalar a la primera,

908
01:11:15,530 --> 01:11:20,460
y luego primera ahora apuntará al nuevo nodo.

909
01:11:20,460 --> 01:11:25,120
Estas primeras líneas de código, en realidad estamos construyendo el nuevo nodo.

910
01:11:25,120 --> 01:11:27,280
No las dos últimas líneas de esta función, pero los primeros.

911
01:11:27,280 --> 01:11:30,290
En realidad se puede extraer en una función, en una función auxiliar.

912
01:11:30,290 --> 01:11:32,560
Eso es muchas veces lo que hago es que me tire en una función,

913
01:11:32,560 --> 01:11:36,040
Yo lo llamo algo como nodo de generación,

914
01:11:36,040 --> 01:11:40,410
y que mantiene la función prepend bastante pequeño, es sólo 3 líneas a continuación.

915
01:11:40,410 --> 01:11:48,710
Hago una llamada a mi función de nodo de generación, y entonces todo alambre hacia arriba.

916
01:11:48,710 --> 01:11:51,970
>> La última cosa que quiero mostrarte,

917
01:11:51,970 --> 01:11:54,030
y voy a dejar que hagas append y todo eso por su cuenta,

918
01:11:54,030 --> 01:11:57,500
es la forma de iterar sobre una lista.

919
01:11:57,500 --> 01:12:00,780
Hay un montón de maneras diferentes para iterar sobre una lista.

920
01:12:00,780 --> 01:12:03,140
En este caso, vamos a calcular la longitud de una lista.

921
01:12:03,140 --> 01:12:06,570
Así que empezamos con longitud = 0.

922
01:12:06,570 --> 01:12:11,580
Esto es muy similar a la escritura strlen para una cadena.

923
01:12:11,580 --> 01:12:17,780
Esto es lo que quiero mostrar, para este circuito aquí.

924
01:12:17,780 --> 01:12:23,530
Se parece un poco cobarde, no es el típico int i = 0, i <lo que sea, i + +.

925
01:12:23,530 --> 01:12:34,920
En su lugar, está la inicialización de nuestra variable n como el comienzo de la lista.

926
01:12:34,920 --> 01:12:40,620
Y entonces, mientras la variable iterador no es nulo, es seguir adelante.

927
01:12:40,620 --> 01:12:46,340
Esto se debe a que, por convención, el final de la lista será nulo.

928
01:12:46,340 --> 01:12:48,770
Y a continuación, para incrementar, en lugar de hacer + +,

929
01:12:48,770 --> 01:12:57,010
el equivalente lista vinculada de + + es n = n-> siguiente.

930
01:12:57,010 --> 01:13:00,410
>> Voy a dejar de llenar los vacíos aquí porque estamos fuera de tiempo.

931
01:13:00,410 --> 01:13:09,300
Pero hay que tener esto en mente a medida que trabaja en conjuntos de procesadores tus spellr.

932
01:13:09,300 --> 01:13:11,650
Las listas enlazadas, si está implementando una tabla hash,

933
01:13:11,650 --> 01:13:14,010
sin duda vendrá en muy práctico.

934
01:13:14,010 --> 01:13:21,780
Y tener este idioma para recorrer las cosas van a hacer la vida mucho más fácil, con suerte.

935
01:13:21,780 --> 01:13:25,910
Cualquier pregunta, rápidamente?

936
01:13:25,910 --> 01:13:28,920
[Sam] ¿Va a enviar el terminado sll y sc?

937
01:13:28,920 --> 01:13:38,360
[Hardison] Yeah. Voy a enviar diapositivas terminadas y la pila completa sll y queue.cs.

938
01:13:38,360 --> 01:13:41,360
[CS50.TV]