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 é CS50.] [CS50.TV]

4
00:00:07,320 --> 00:00:11,840
Todo ben. Benvido á sección 6.

5
00:00:11,840 --> 00:00:14,690
Esta semana, imos estar fala de estruturas de datos na sección,

6
00:00:14,690 --> 00:00:19,780
principalmente porque o problema desta semana definir spellr

7
00:00:19,780 --> 00:00:24,410
fai unha morea de explotación diferente da estrutura de datos.

8
00:00:24,410 --> 00:00:26,520
Hai unha morea de maneiras diferentes pode ir co conxunto de problemas,

9
00:00:26,520 --> 00:00:31,570
E canto máis estruturas de datos que vostede sabe sobre as cousas máis legais que podes facer.

10
00:00:31,570 --> 00:00:34,990
>> Entón imos comezar. Primeiro imos falar sobre pilas,

11
00:00:34,990 --> 00:00:37,530
datos da pila e cola estruturas que nós imos falar sobre.

12
00:00:37,530 --> 00:00:40,560
Pilas e colas son realmente útiles cando comezamos a falar sobre os gráficos,

13
00:00:40,560 --> 00:00:44,390
que non imos facer tanto agora.

14
00:00:44,390 --> 00:00:52,820
Pero son moi bos para entender un dos grandes estruturas de datos fundamentais do CS.

15
00:00:52,820 --> 00:00:54,880
A descrición da especificación do conxunto de problemas,

16
00:00:54,880 --> 00:00:59,260
Se puxar-lo, fala sobre pilas como semellante a

17
00:00:59,260 --> 00:01:05,239
a pila de bandexas de comidas que ten na lanchonete nas salas de cea

18
00:01:05,239 --> 00:01:09,680
onde cando a cea o equipo vén e pon as bandexas de comida para fóra despois que limpa-los,

19
00:01:09,680 --> 00:01:12,000
eles empilhá-los un por riba do outro.

20
00:01:12,000 --> 00:01:15,050
E entón, cando os nenos veñen para obter alimentos,

21
00:01:15,050 --> 00:01:19,490
eles tiran as bandexas de fóra, primeiro a de arriba, entón o que está abaixo dela, entón a un abaixo diso.

22
00:01:19,490 --> 00:01:25,190
Entón, en realidade, a primeira bandexa que a cea o equipo poñer para abaixo é a última que é levado.

23
00:01:25,190 --> 00:01:32,330
O último que a cea o equipo poñer é o primeiro que se levou a cea.

24
00:01:32,330 --> 00:01:38,100
Na especificación do conxunto de problemas, que podes baixar, se non ten,

25
00:01:38,100 --> 00:01:46,730
falamos sobre a modelaxe dun stucture datos da pila empregando este tipo de estrutura.

26
00:01:46,730 --> 00:01:51,070
>> Entón, o que temos aquí, que é semellante ao que foi presentado na clase,

27
00:01:51,070 --> 00:01:58,120
excepto en charla que presentou esta con ints ao contrario char * s.

28
00:01:58,120 --> 00:02:06,250
Esta vai ser unha pila que almacena o que?

29
00:02:06,250 --> 00:02:09,009
Daniel? O que estamos almacenando nesta pila?

30
00:02:09,009 --> 00:02:15,260
[Daniel] Cordas? >> Estamos almacenar cadeas nesta pila, exactamente.

31
00:02:15,260 --> 00:02:20,950
Todo o que ten que ter para crear unha pila é un array

32
00:02:20,950 --> 00:02:23,920
dunha capacidade particular, que, neste caso,

33
00:02:23,920 --> 00:02:28,020
capacidade vai ser en todas as tapas, pois é unha constante.

34
00:02:28,020 --> 00:02:36,340
E entón, ademais da matriz, todo o que necesitamos para seguir é o tamaño actual da matriz.

35
00:02:36,340 --> 00:02:38,980
Unha cousa a notar aquí que é legal

36
00:02:38,980 --> 00:02:47,060
é que estamos a crear a estrutura de datos empilhada sobre outra estrutura, a matriz.

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

38
00:02:50,110 --> 00:02:54,250
Non imos facelo bastante aínda, pero espero que despois de facer os problemas de lista vinculada,

39
00:02:54,250 --> 00:03:00,520
vai ver como pode facilmente aplicar unha pila enriba dunha lista ligada tamén.

40
00:03:00,520 --> 00:03:02,640
Pero, por agora, imos ir con matrices.

41
00:03:02,640 --> 00:03:06,350
Entón, de novo, todo o que necesitamos é un array e só necesitamos controlar o tamaño da matriz.

42
00:03:06,350 --> 00:03:09,850
[Sam] Sentímolo, por que é o que dixo a pila está na parte superior das cordas?

43
00:03:09,850 --> 00:03:13,440
Para min parece que as cordas están dentro da pila.

44
00:03:13,440 --> 00:03:16,790
[Hardison] Yeah. Estamos creando, nós estamos levando a nosa matriz de estructura de datos -

45
00:03:16,790 --> 00:03:22,130
esta é unha gran cuestión. Entón a cuestión é por iso que, para as persoas que están a asistir esta liña,

46
00:03:22,130 --> 00:03:24,140
por que estamos dicindo que a pila está encima das cordas,

47
00:03:24,140 --> 00:03:27,990
porque aquí parece que as cordas están dentro da pila?

48
00:03:27,990 --> 00:03:31,050
O que é totalmente o caso.

49
00:03:31,050 --> 00:03:34,660
O que eu estaba referíndose a era que nós temos unha estrutura de datos matriz.

50
00:03:34,660 --> 00:03:39,290
Nós temos unha matriz de char * s, este arranxo de cordas,

51
00:03:39,290 --> 00:03:45,300
e imos engadir a isto, a fin de crear a estrutura de datos empilhados.

52
00:03:45,300 --> 00:03:48,620
>> Así, unha pila é un pouco máis complexo que un array.

53
00:03:48,620 --> 00:03:51,890
Podemos usar unha matriz para construír unha pila.

54
00:03:51,890 --> 00:03:55,810
Entón é aí onde nós dicimos que a pila está construída enriba dunha matriz.

55
00:03:55,810 --> 00:04:02,510
Do mesmo xeito, como dixen anteriormente, podemos construír unha pila enriba dunha lista ligada.

56
00:04:02,510 --> 00:04:04,960
En vez de usar unha matriz para almacenar os nosos elementos,

57
00:04:04,960 --> 00:04:10,070
poderiamos usar unha lista ligada a manter os nosos elementos e construír a pila en torno a iso.

58
00:04:10,070 --> 00:04:12,420
Imos camiñar a través de un par de exemplos, mirando para un código,

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

60
00:04:14,960 --> 00:04:23,400
Na esquerda, eu teño xogado para abaixo o que struct pila quedaría na memoria

61
00:04:23,400 --> 00:04:28,330
a capacidade de # definido como catro.

62
00:04:28,330 --> 00:04:33,490
Temos os nosos catro elemento do array char *.

63
00:04:33,490 --> 00:04:38,110
Temos cadeas [0], cadeas, [1] strings [2] strings [3],

64
00:04:38,110 --> 00:04:43,800
e, a continuación, que o espacio para o noso pasado enteiro tamaño.

65
00:04:43,800 --> 00:04:46,270
Será que isto ten sentido? Okay.

66
00:04:46,270 --> 00:04:48,790
Isto é o que pasa se o que fago á dereita,

67
00:04:48,790 --> 00:04:55,790
cal será o meu código, é só para declarar unha estrutura, unha estrutura chamada empilhados s.

68
00:04:55,790 --> 00:05:01,270
Isto é o que temos. Establece esta pegada na memoria.

69
00:05:01,270 --> 00:05:05,590
A primeira pregunta aquí é o que son os contidos struct pila?

70
00:05:05,590 --> 00:05:09,250
Agora non é nada, pero eles non son absolutamente nada.

71
00:05:09,250 --> 00:05:13,300
San este tipo de lixo. Nós non temos idea do que está neles.

72
00:05:13,300 --> 00:05:17,000
Cando declaramos s pila, estamos só xogando que encima da memoria.

73
00:05:17,000 --> 00:05:19,840
É unha especie de como declarar int i non arrincar-la.

74
00:05:19,840 --> 00:05:21,730
Vostede non sabe o que está aí. Podes ler o que está aí,

75
00:05:21,730 --> 00:05:27,690
pero non pode ser super útil.

76
00:05:27,690 --> 00:05:32,680
Unha cousa que quere sempre se lembrar de facer é iniciar o que debe ser inicializar.

77
00:05:32,680 --> 00:05:35,820
Neste caso, nós estamos indo a iniciar o tamaño para ser cero,

78
00:05:35,820 --> 00:05:39,960
porque que vai pasar a ser moi importante para nós.

79
00:05:39,960 --> 00:05:43,450
Nós poderiamos ir adiante e iniciar os punteiros, todos os s * char,

80
00:05:43,450 --> 00:05:49,670
ser un valor comprensible, probablemente nulo.

81
00:05:49,670 --> 00:05:58,270
Pero non é totalmente necesario que fagamos isto.

82
00:05:58,270 --> 00:06:04,200
>> Agora, as dúas principais operacións sobre pilas son?

83
00:06:04,200 --> 00:06:07,610
Alguén se lembra da charla que fai pila? Si?

84
00:06:07,610 --> 00:06:09,700
[Stella] empurrando e popping? >> Exactamente.

85
00:06:09,700 --> 00:06:13,810
Empurrando e popping son as dúas principais operacións sobre pilas.

86
00:06:13,810 --> 00:06:17,060
E o que facer presión? >> Pon algo para o cumio

87
00:06:17,060 --> 00:06:19,300
da pila, e despois leva-lo de estalo.

88
00:06:19,300 --> 00:06:23,150
[Hardison] Exactamente. Entón, empurrando empurra algo na parte superior da pila.

89
00:06:23,150 --> 00:06:27,700
É como a cea o equipo poñendo unha bandexa de cea no mostrador.

90
00:06:27,700 --> 00:06:33,630
E popping está levando unha bandexa de cea á beira da pila.

91
00:06:33,630 --> 00:06:36,460
Imos examinar algúns exemplos do que acontece

92
00:06:36,460 --> 00:06:39,720
cando empurrar as cousas para a pila.

93
00:06:39,720 --> 00:06:45,110
Se fósemos para empurrar a cadea 'Ola' para o noso conxunto,

94
00:06:45,110 --> 00:06:49,760
este é o noso diagrama será coma agora.

95
00:06:49,760 --> 00:06:53,410
Mira o que ocorre?

96
00:06:53,410 --> 00:06:56,530
Nós empurrado para dentro do primeiro elemento da nosa matriz cordas

97
00:06:56,530 --> 00:07:01,420
e elevou a conta de tamaño para ser 1.

98
00:07:01,420 --> 00:07:05,340
Entón, se olharmos para a diferenza entre os dous diapositivas, aquí foi de 0, aquí está antes do pulo.

99
00:07:05,340 --> 00:07:08,690
Aquí é despois do empurrón.

100
00:07:08,690 --> 00:07:13,460
Antes do envío, tras a presión.

101
00:07:13,460 --> 00:07:16,860
E agora temos un elemento na nosa pila.

102
00:07:16,860 --> 00:07:20,970
É a cadea "Ola", e é iso.

103
00:07:20,970 --> 00:07:24,440
Todo o resto na matriz, na nosa matriz cordas, aínda é lixo.

104
00:07:24,440 --> 00:07:27,070
Non inicializar el.

105
00:07:27,070 --> 00:07:29,410
Imos dicir que empurrar outra corda para o noso conxunto.

106
00:07:29,410 --> 00:07:32,210
Nós imos empurrar "mundo" neste momento.

107
00:07:32,210 --> 00:07:35,160
Así podes ver "o mundo" aquí vai enriba do "Ola",

108
00:07:35,160 --> 00:07:40,040
e a conta de tamaño vai ata 2.

109
00:07:40,040 --> 00:07:44,520
Agora podemos empurrar "CS50", e que vai enriba de novo.

110
00:07:44,520 --> 00:07:51,110
Se volver, podes ver como estamos empurrando as cousas enriba da pila.

111
00:07:51,110 --> 00:07:53,320
E agora temos a pop.

112
00:07:53,320 --> 00:07:58,910
Cando apareceu algo fóra da pila, o que pasou?

113
00:07:58,910 --> 00:08:01,540
Alguén viu a diferencia? É moi sutil.

114
00:08:01,540 --> 00:08:05,810
[Alumno] O tamaño. >> Si, o tamaño modificado.

115
00:08:05,810 --> 00:08:09,040
>> O que máis lle esperar para cambiar?

116
00:08:09,040 --> 00:08:14,280
[Alumno] As cordas, tamén. >> Dereito. As cordas tamén.

117
00:08:14,280 --> 00:08:17,110
Acontece que cando está facendo desta forma,

118
00:08:17,110 --> 00:08:21,960
porque non estamos copiando os elementos na nosa pila,

119
00:08:21,960 --> 00:08:24,670
Nós realmente non ten que facer nada, podemos usar só o tamaño

120
00:08:24,670 --> 00:08:28,630
para manter o control do número de cousas na nosa matriz

121
00:08:28,630 --> 00:08:33,780
para que, cando aparecer de novo, unha vez máis, só diminuír noso tamaño 1.

122
00:08:33,780 --> 00:08:39,440
Non hai necesidade de realmente entrar e substituír nada.

123
00:08:39,440 --> 00:08:41,710
Tipo de funky.

124
00:08:41,710 --> 00:08:46,520
Acontece que normalmente simplemente deixar as cousas só, porque é menos traballo para nós.

125
00:08:46,520 --> 00:08:50,060
Se non temos que volver e substituír algo, entón por que facelo?

126
00:08:50,060 --> 00:08:54,150
Así, cando aparecer dúas veces fóra da pila, é todo o que fai diminuír o tamaño dun par de veces.

127
00:08:54,150 --> 00:08:59,120
E unha vez máis, este é só porque non estamos copiando as cousas na nosa pila.

128
00:08:59,120 --> 00:09:01,320
Si? Dalle.

129
00:09:01,320 --> 00:09:04,460
[Estudante, inintelixible] >> E entón o que ocorre cando empurrar algo novo?

130
00:09:04,460 --> 00:09:08,570
Cando empurrar algo novo, onde vai?

131
00:09:08,570 --> 00:09:12,390
Para onde vai, Basil? >> En cordas [1]? >> Dereito.

132
00:09:12,390 --> 00:09:14,530
Por que non ir cadeas [3]?

133
00:09:14,530 --> 00:09:19,410
[Basil] Porque se esqueceu de que non había nada en cordas [1] e [2]?

134
00:09:19,410 --> 00:09:24,040
[Hardison] Exactamente. A nosa pila, esencialmente, "esqueceu" que estaba suxeitando en nada

135
00:09:24,040 --> 00:09:29,480
en cordas [1] ou cordas [2], polo tanto, cando empurrar "woot",

136
00:09:29,480 --> 00:09:36,670
el simplemente pon que o elemento en cordas [1].

137
00:09:36,670 --> 00:09:41,590
Hai dúbidas sobre como funciona isto, nun nivel básico?

138
00:09:41,590 --> 00:09:45,160
[Sam] Así, este non é dinámica, de calquera maneira, en termos de cantidade

139
00:09:45,160 --> 00:09:47,620
ou en virtude do tamaño da pila?

140
00:09:47,620 --> 00:09:56,750
[Hardison] Exactamente. Isto é - o punto era que esta non era unha pila dinámicamente growning.

141
00:09:56,750 --> 00:10:02,850
Trátase de unha pila que pode conter, como máximo, catro char * s, como máximo catro cousas.

142
00:10:02,850 --> 00:10:07,580
Se fósemos tentar empurrar unha cousa quinto, o que pensas que debe ocorrer?

143
00:10:07,580 --> 00:10:11,870
[Estudantes, inintelixible]

144
00:10:11,870 --> 00:10:14,600
[Hardison] Exactamente. Hai unha serie de cousas que poden ocorrer.

145
00:10:14,600 --> 00:10:19,330
Podería seg falla, dependendo do que nós -

146
00:10:19,330 --> 00:10:22,530
exactamente como nós estaban a aplicar o back-end.

147
00:10:22,530 --> 00:10:31,740
El podería substituír. El podería ter ese estourido de buffer que falamos en clase.

148
00:10:31,740 --> 00:10:35,240
Cal sería a cousa máis obvia que pode ser substituído

149
00:10:35,240 --> 00:10:42,370
se intentou empurrar algo extra no noso pila?

150
00:10:42,370 --> 00:10:44,550
Entón mencionar un estourido de buffer.

151
00:10:44,550 --> 00:10:47,870
O que pode ser o único que se escribiu máis ou pisou

152
00:10:47,870 --> 00:10:52,320
se rebordou accidentalmente por tentar empurrar unha cousa extra?

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

154
00:10:54,730 --> 00:10:58,440
Pero, inicialmente, o que pode ocorrer? O que se intentou empurrar unha cuarta cousa?

155
00:10:58,440 --> 00:11:06,220
Pode substituír o tamaño mínimo con este diagrama de memoria que temos.

156
00:11:06,220 --> 00:11:10,880
>> Na especificación conxunto de problemas, que é o que nós imos estar aplicando hoxe,

157
00:11:10,880 --> 00:11:16,030
o que queremos facer é volver falso.

158
00:11:16,030 --> 00:11:20,030
O noso método push vai voltar un valor booleano,

159
00:11:20,030 --> 00:11:22,920
e ese valor booleano será certo o impulso éxito

160
00:11:22,920 --> 00:11:29,730
e falso se non podemos empurrar máis nada, porque a pila está chea.

161
00:11:29,730 --> 00:11:33,620
Imos examinar un pouco de que o código agora.

162
00:11:33,620 --> 00:11:36,400
Aquí é a nosa función push.

163
00:11:36,400 --> 00:11:40,380
A nosa función push para unha pila vai ter na cadea para poñer na pila.

164
00:11:40,380 --> 00:11:45,820
Vai voltar certo a cadea foi empuxado con éxito

165
00:11:45,820 --> 00:11:51,820
na outra pila e teito.

166
00:11:51,820 --> 00:11:59,740
Todas as suxestións sobre o que pode ser unha cousa boa primeiro a facer aquí?

167
00:11:59,740 --> 00:12:20,630
[Sam] Se tamaño é igual capacidade logo retornar falso?

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

169
00:12:23,320 --> 00:12:26,310
Se o tamaño é a capacidade, imos voltar falso.

170
00:12:26,310 --> 00:12:29,270
Non podemos poñer algo máis na nosa pila.

171
00:12:29,270 --> 00:12:36,900
En caso contrario, queremos poñer algo na parte superior da pila.

172
00:12:36,900 --> 00:12:41,670
¿Que é o "principio da 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
Que é o cume da pila despois hai unha cousa na pila? Missy, vostede sabe?

175
00:12:49,990 --> 00:12:52,720
[Missy] un. Tamaño >> é unha, exactamente. Continúa a engadir ao tamaño,

176
00:12:52,720 --> 00:13:01,690
e cada vez que está poñendo no novo elemento no tamaño do índice na matriz.

177
00:13:01,690 --> 00:13:05,470
Podemos facelo con este tipo de one-Liner, se iso ten sentido.

178
00:13:05,470 --> 00:13:11,910
Entón, nós temos a nosa matriz cordas, imos para acceder-lo no índice tamaño,

179
00:13:11,910 --> 00:13:14,780
e nós só estamos indo para gardar o noso char * alí.

180
00:13:14,780 --> 00:13:19,340
Observe como non hai como copia cadea suceder aquí,

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

182
00:13:29,680 --> 00:13:34,440
E entón Missy trouxo o que temos agora de facer,

183
00:13:34,440 --> 00:13:40,570
porque temos gardado a cadea no lugar axeitado na matriz,

184
00:13:40,570 --> 00:13:49,230
e ela dixo que tiña que aumentar o tamaño dun xeito que nós estamos preparados para o impulso seguinte.

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

186
00:13:53,950 --> 00:13:59,330
Neste punto, nós empurrado para a nosa matriz. Cal é a última cousa que temos que facer?

187
00:13:59,330 --> 00:14:10,110
[Estudante] voltar true. Voltar >> verdade.

188
00:14:10,110 --> 00:14:14,690
Entón é moi simple, un código moi sinxelo. Non moito.

189
00:14:14,690 --> 00:14:17,070
Unha vez que implica a súa cabeza en torno a como a pila funciona,

190
00:14:17,070 --> 00:14:21,910
iso é moi sinxelo de implementar.

191
00:14:21,910 --> 00:14:26,390
>> Agora, a próxima parte deste está xurdindo unha corda fóra da pila.

192
00:14:26,390 --> 00:14:29,410
Eu vou dar a vostedes moito tempo para traballar niso un pouco.

193
00:14:29,410 --> 00:14:34,320
É case esencialmente o contrario do que fixemos aquí en empurrón.

194
00:14:34,320 --> 00:14:38,510
O que eu teño feito é, en realidade - Oops.

195
00:14:38,510 --> 00:14:48,160
Eu iniciado un aparello aquí, e no aparello,

196
00:14:48,160 --> 00:14:53,600
Eu puxei o conxunto de problemas 5 especificación.

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

198
00:15:02,560 --> 00:15:08,590
Vós xa baixou este código que está situado aquí, section6.zip?

199
00:15:08,590 --> 00:15:15,030
Todo ben. Se non ten feito isto, fai iso agora, moi rapidamente.

200
00:15:15,030 --> 00:15:22,130
Eu vou facer iso na miña xanela de terminal.

201
00:15:22,130 --> 00:15:25,090
En realidade, eu fixen iso aquí enriba. Si

202
00:15:25,090 --> 00:15:34,730
Si, Sam? >> Eu teño unha pregunta sobre por que dixo s.string 's pistas de tamaño = str?

203
00:15:34,730 --> 00:15:42,910
¿Que é str? É o definido en algún lugar antes, ou - oh, no str char *?

204
00:15:42,910 --> 00:15:47,160
[Hardison] Si, exactamente. Ese foi o argumento. >> Ah, ok. Sentímolo.

205
00:15:47,160 --> 00:15:49,470
[Hardison] Estamos especificando a corda para empurrar dentro

206
00:15:49,470 --> 00:15:55,220
A outra cuestión que poida xurdir que realmente non falar aquí era

207
00:15:55,220 --> 00:15:58,810
tomamos por certo que tivemos esta variable chamada s

208
00:15:58,810 --> 00:16:02,710
que estaba no ámbito e accesible para nós.

209
00:16:02,710 --> 00:16:06,960
Tomamos por certo que s esta struct pila.

210
00:16:06,960 --> 00:16:08,930
Entón, mirando cara atrás, este código push,

211
00:16:08,930 --> 00:16:13,450
podes ver que nós estamos facendo cousas con esta corda que foi aprobada en

212
00:16:13,450 --> 00:16:19,210
pero entón, de súpeto, estamos accedendo s.size, como, onde s vén?

213
00:16:19,210 --> 00:16:23,020
O código que imos ollar no arquivo sección

214
00:16:23,020 --> 00:16:27,100
e, a continuación, o material que estará facendo no seu problema se pon,

215
00:16:27,100 --> 00:16:32,440
fixemos nosa pila struct dunha variable global

216
00:16:32,440 --> 00:16:36,380
para que poidamos ter acceso a el en todas as nosas funcións distintas

217
00:16:36,380 --> 00:16:40,630
sen ter que manualmente pasar ao redor e pasalo por referencia,

218
00:16:40,630 --> 00:16:44,870
facer todo tipo de cousas a el.

219
00:16:44,870 --> 00:16:52,280
Estamos só enganando un pouco, se queres, para facer as cousas mellor.

220
00:16:52,280 --> 00:16:57,430
E iso é algo que estamos facendo aquí, porque iso é para divertirse, é máis fácil.

221
00:16:57,430 --> 00:17:02,800
Moitas veces, vai ver as persoas fan iso, eles teñen unha gran estrutura de datos

222
00:17:02,800 --> 00:17:07,750
que está sendo operado dentro do seu programa.

223
00:17:07,750 --> 00:17:09,560
>> Imos volver para o aparello.

224
00:17:09,560 --> 00:17:15,240
Será que todo o mundo con éxito obter o section6.zip?

225
00:17:15,240 --> 00:17:20,440
Todo o mundo descompactá-lo usando section6.zip unzip?

226
00:17:20,440 --> 00:17:27,200
Se vai para o directorio sección 6 -

227
00:17:27,200 --> 00:17:29,220
aah, en todo o lugar -

228
00:17:29,220 --> 00:17:32,840
e incluír o que aquí, ve que ten tres diferentes arquivos. c.

229
00:17:32,840 --> 00:17:38,350
Ten unha cola, un SLL, que, illadamente, é ligada lista, e unha pila.

230
00:17:38,350 --> 00:17:44,600
Se abrir stack.c,

231
00:17:44,600 --> 00:17:47,330
podes ver que temos esa estrutura definida para nós,

232
00:17:47,330 --> 00:17:51,330
a estrutura exacta que acabamos de falar nos diapositivas.

233
00:17:51,330 --> 00:17:56,340
Temos a nosa variable global para a pila,

234
00:17:56,340 --> 00:18:00,110
Nós temos a nosa función push,

235
00:18:00,110 --> 00:18:04,230
e despois temos a nosa función pop.

236
00:18:04,230 --> 00:18:08,320
Vou poñer o código para empurrar de volta no slide aquí,

237
00:18:08,320 --> 00:18:10,660
pero o que me gustaría que vós que facer é, o mellor da súa capacidade,

238
00:18:10,660 --> 00:18:13,790
ir e aplicar a función pop.

239
00:18:13,790 --> 00:18:18,480
Despois de aplicar, pode compilar este co make de pila,

240
00:18:18,480 --> 00:18:22,540
e, a continuación, executar o arquivo executábel pila resultante,

241
00:18:22,540 --> 00:18:28,390
e que pode facer todo ese código de proba aquí abaixo que está na principal.

242
00:18:28,390 --> 00:18:31,060
E principal coida de realmente facer o push e pop chamadas

243
00:18:31,060 --> 00:18:33,220
e asegurarse de que todo pasa ben.

244
00:18:33,220 --> 00:18:36,820
Tamén se inicia o tamaño da pila aquí

245
00:18:36,820 --> 00:18:39,780
así que non se preocupe o arranque iso.

246
00:18:39,780 --> 00:18:42,310
Pode asumir que foi inicializar correctamente

247
00:18:42,310 --> 00:18:48,000
polo tempo que acceder a ela na función de pop.

248
00:18:48,000 --> 00:18:53,530
Isto ten sentido?

249
00:18:53,530 --> 00:19:00,100
Entón, imos alí. Hai o código empurrón.

250
00:19:00,100 --> 00:19:13,210
Eu vou dar a vostedes 5 ou 10 minutos.

251
00:19:13,210 --> 00:19:15,690
E se tes algunha dúbida no ínterim, mentres está de codificación,

252
00:19:15,690 --> 00:19:17,710
pregunta-lle en voz alta.

253
00:19:17,710 --> 00:19:23,080
Entón, se chegar a un punto de discordia, é só pedir.

254
00:19:23,080 --> 00:19:26,030
Deixe-me saber, deixe todo o mundo sabe.

255
00:19:26,030 --> 00:19:28,160
Traballa co seu veciño tamén.

256
00:19:28,160 --> 00:19:30,360
[Daniel] Estamos só aplicando pop agora? Só >> pop.

257
00:19:30,360 --> 00:19:34,200
Aínda que pode copiar a implementación de impulso se quere

258
00:19:34,200 --> 00:19:37,780
de xeito que a proba vai funcionar.

259
00:19:37,780 --> 00:19:41,940
Porque é difícil para probar as cousas ficando en -

260
00:19:41,940 --> 00:19:49,030
ou é difícil probar as cousas pulando para fóra de unha pila se non hai nada na pila para comezar.

261
00:19:49,030 --> 00:19:55,250
>> ¿Que é pop suposto estar volvendo? O elemento dende o principio da pila.

262
00:19:55,250 --> 00:20:01,260
É suposto obter o elemento para fóra da parte superior da pila

263
00:20:01,260 --> 00:20:05,780
e, a continuación, diminuír o tamaño da pila,

264
00:20:05,780 --> 00:20:07,810
e agora perdeu o elemento superior.

265
00:20:07,810 --> 00:20:11,420
E entón voltar o elemento superior.

266
00:20:11,420 --> 00:20:20,080
[Estudante, inintelixible]

267
00:20:20,080 --> 00:20:28,810
[Hardison] Entón, o que pasa se fai iso? [Estudante, inintelixible]

268
00:20:28,810 --> 00:20:34,000
O que acaba pasando é que probablemente está accedendo ou

269
00:20:34,000 --> 00:20:37,350
un elemento que non foi inicializado aínda, para que o seu cálculo

270
00:20:37,350 --> 00:20:39,990
onde o último elemento é desligado.

271
00:20:39,990 --> 00:20:46,260
Entón, aquí, se observar, no impulso, estamos accedendo cordas no elemento s.size

272
00:20:46,260 --> 00:20:48,560
porque é un novo índice.

273
00:20:48,560 --> 00:20:51,460
É o novo cume da pila.

274
00:20:51,460 --> 00:21:01,100
Considerando que, pop, s.size vai ser o seguinte espazo,

275
00:21:01,100 --> 00:21:05,210
o espazo que está na parte superior de todos os elementos no seu stack.

276
00:21:05,210 --> 00:21:10,050
Así, o elemento de nivel máis alto non é s.size,

277
00:21:10,050 --> 00:21:14,930
pero si, é por baixo.

278
00:21:14,930 --> 00:21:19,640
>> A outra cousa a facer cando - en pop,

279
00:21:19,640 --> 00:21:22,030
é que ten que diminuír o tamaño.

280
00:21:22,030 --> 00:21:28,750
Se se lembrar de volta ao noso pequeno diagrama aquí,

281
00:21:28,750 --> 00:21:30,980
realmente, o único que vimos pasar cando chamado pop

282
00:21:30,980 --> 00:21:36,150
era que este tamaño descartado, primeiro en 2, entón a 1.

283
00:21:36,150 --> 00:21:42,620
Entón, cando empuxou un novo elemento ligado, el iría para o lugar axeitado.

284
00:21:42,620 --> 00:21:49,610
[Basil] Se o s.size é 2, entón non vai pasar ao elemento 2,

285
00:21:49,610 --> 00:21:54,400
e despois que desexa que apareza ese elemento fóra?

286
00:21:54,400 --> 00:21:59,510
Entón, se nós fomos para - >> Entón, imos ollar para iso de novo.

287
00:21:59,510 --> 00:22:07,730
Se esta é a pila neste punto

288
00:22:07,730 --> 00:22:12,130
e chamamos pop,

289
00:22:12,130 --> 00:22:16,150
en que o contido é o elemento máis alto?

290
00:22:16,150 --> 00:22:19,300
[Basil] O 2, pero vai aparecer 3. >> Dereito.

291
00:22:19,300 --> 00:22:24,220
Entón é aí que o noso tamaño é 3, pero queremos poñer o elemento no índice 2.

292
00:22:24,220 --> 00:22:29,900
É ese tipo típico de fóra por un que ten o cero-indexación de matrices.

293
00:22:29,900 --> 00:22:36,430
Entón, quere aparecer o terceiro elemento, pero o terceiro elemento non está no índice 3.

294
00:22:36,430 --> 00:22:39,430
E a razón pola que non tes que facer iso unha menos cando estamos empurrando

295
00:22:39,430 --> 00:22:44,120
é porque agora, entender que o elemento máis alto,

296
00:22:44,120 --> 00:22:47,600
se fósemos para empurrar outra cousa para a pila, neste punto,

297
00:22:47,600 --> 00:22:50,360
que quere empurralo lo no índice 3.

298
00:22:50,360 --> 00:23:03,550
E iso só acontece se o tamaño e os índices aliñar cando está empurrando.

299
00:23:03,550 --> 00:23:06,960
>> Quen ten unha implementación do conxunto de traballo?

300
00:23:06,960 --> 00:23:09,690
Ten unha pila de traballar un. Tes pop funcionando aínda?

301
00:23:09,690 --> 00:23:11,890
[Daniel] Si Creo que si.

302
00:23:11,890 --> 00:23:14,610
Programa >> funciona e non seg falhamento, está imprimindo?

303
00:23:14,610 --> 00:23:17,520
Será que imprimir "éxito" cando o fai?

304
00:23:17,520 --> 00:23:22,630
Si Fai apilar, executa-lo, se imprime "éxito" e non vai boom,

305
00:23:22,630 --> 00:23:26,000
entón todo é bo.

306
00:23:26,000 --> 00:23:34,070
Todo ben. Imos pasar o aparello moi rapidamente,

307
00:23:34,070 --> 00:23:46,100
e nós imos camiñar por este.

308
00:23:46,100 --> 00:23:51,110
Se olharmos para o que está a suceder aquí con pop,

309
00:23:51,110 --> 00:23:55,220
Daniel, que foi o primeiro que fixo?

310
00:23:55,220 --> 00:23:58,850
[Daniel] Se s.size é maior que 0.

311
00:23:58,850 --> 00:24:03,120
[Hardison] Okay. E por que fixo iso?

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

313
00:24:05,610 --> 00:24:10,950
[Hardison] Dereito. Quere probar para estar seguro de que s.size é maior que 0;

314
00:24:10,950 --> 00:24:13,280
doutra forma, o que quere que aconteza?

315
00:24:13,280 --> 00:24:16,630
[Daniel] return null? >> Return null, exactamente.

316
00:24:16,630 --> 00:24:20,740
Polo tanto, se s.size é maior que 0. Entón, o que imos facer?

317
00:24:20,740 --> 00:24:25,890
O que imos facer a pila non está baleiro?

318
00:24:25,890 --> 00:24:31,210
[Stella] Vostede diminuír o tamaño? >> Vostede diminuír o tamaño, todo ben.

319
00:24:31,210 --> 00:24:34,440
Entón, como fixo iso? >> S.size--.

320
00:24:34,440 --> 00:24:37,030
[Hardison] Grande. E entón, o que fixo?

321
00:24:37,030 --> 00:24:44,140
[Stella] E entón eu dixo que o retorno s.string [s.size].

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

323
00:24:48,560 --> 00:24:51,940
Se non, regresar nulo. Si, Sam?

324
00:24:51,940 --> 00:24:55,510
[Sam] Por que non necesita ser s.size + 1?

325
00:24:55,510 --> 00:24:58,430
[Hardison] Plus 1? Si >>. >> Entender.

326
00:24:58,430 --> 00:25:00,980
[Sam] Eu penso, porque está levando un fóra,

327
00:25:00,980 --> 00:25:04,290
entón está indo estar volvendo non o que eles pediron.

328
00:25:04,290 --> 00:25:09,400
[Hardison] E iso foi exactamente o que estaban falando con toda esta cuestión de 0 índices.

329
00:25:09,400 --> 00:25:11,380
Entón, se o zoom aquí.

330
00:25:11,380 --> 00:25:15,650
Se olharmos para este cara aquí, podes ver que, cando apareza,

331
00:25:15,650 --> 00:25:19,340
estamos estourando o elemento no índice 2.

332
00:25:19,340 --> 00:25:25,200
>> Entón, nós diminuímos noso tamaño primeiro, despois o noso tamaño corresponde ao índice.

333
00:25:25,200 --> 00:25:39,650
Se non diminuír o tamaño do primeiro, entón temos que facer o tamaño -1 e decremento.

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

335
00:25:45,270 --> 00:25:47,530
Calquera dúbida sobre iso?

336
00:25:47,530 --> 00:25:54,050
Hai unha serie de formas diferentes para escribir iso tamén.

337
00:25:54,050 --> 00:26:03,290
En realidade, podemos facer algo aínda - podemos facer un one-Liner.

338
00:26:03,290 --> 00:26:05,770
Podemos facer un retorno dunha liña.

339
00:26:05,770 --> 00:26:12,980
Así, podemos realmente diminuír antes de volver ao facelo.

340
00:26:12,980 --> 00:26:18,320
Entón, poñer o - antes do s.size.

341
00:26:18,320 --> 00:26:22,060
Isto fai que a liña realmente denso.

342
00:26:22,060 --> 00:26:30,940
Se a diferenza entre o - S e tamaño. S.size -

343
00:26:30,940 --> 00:26:40,130
é que este postfix - que eles chaman de postfix, porque o - vén despois do s.size -

344
00:26:40,130 --> 00:26:47,430
significa que s.size é valorada para efectos de atopar o índice

345
00:26:47,430 --> 00:26:50,410
como é actualmente, cando esta liña é executada,

346
00:26:50,410 --> 00:26:54,290
e despois iso - acontece despois da liña é executada.

347
00:26:54,290 --> 00:27:00,340
Tras o elemento s.size contido é accesible.

348
00:27:00,340 --> 00:27:07,260
E iso non é o que queremos, porque queremos que o decremento ocorrer primeiro.

349
00:27:07,260 --> 00:27:10,990
Othewise, imos estar accedendo a matriz, efectivamente, fóra dos límites.

350
00:27:10,990 --> 00:27:16,850
Nós imos estar accedendo ao elemento sobre o que realmente quere acceder.

351
00:27:16,850 --> 00:27:23,840
Si, Sam? >> É máis rápido ou usar menos memoria RAM para facer en liña ou non?

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

353
00:27:29,620 --> 00:27:34,220
[Sam, inintelixible] >> Si, depende. Podes facer trucos compilador

354
00:27:34,220 --> 00:27:41,580
para obter o compilador para recoñecer que, xeralmente, eu imaxino.

355
00:27:41,580 --> 00:27:44,840
>> Entón, nós mencionados un pouco sobre isto optimización do compilador

356
00:27:44,840 --> 00:27:47,400
que pode facer na compilación,

357
00:27:47,400 --> 00:27:50,580
e ese é o tipo de cousa que un compilador pode ser capaz de descubrir,

358
00:27:50,580 --> 00:27:54,710
como oh, hey, quizais eu poida facer todo isto nunha soa operación,

359
00:27:54,710 --> 00:27:59,420
ao contrario de cargar a variable en tamaño a partir da RAM,

360
00:27:59,420 --> 00:28:03,770
decrementando-lo, gardalo lo de volta para fóra, e despois poñer-lo de volta de novo

361
00:28:03,770 --> 00:28:08,000
para procesar o resto da operación.

362
00:28:08,000 --> 00:28:10,710
Pero, normalmente, non, este non é o tipo de cousas

363
00:28:10,710 --> 00:28:20,770
que vai facer o seu programa significativamente máis rápido.

364
00:28:20,770 --> 00:28:26,000
Algunha pregunta sobre pilas?

365
00:28:26,000 --> 00:28:31,360
>> Entón, empurrando e popping. Se vostedes queren experimentar a edición de hacker,

366
00:28:31,360 --> 00:28:33,660
o que fixemos na edición de hacker é realmente ir

367
00:28:33,660 --> 00:28:37,670
e fixo esta pila crecer dinámicamente.

368
00:28:37,670 --> 00:28:43,190
O reto non é todo aquí na función push,

369
00:28:43,190 --> 00:28:48,820
para descubrir como facer esa matriz crecer

370
00:28:48,820 --> 00:28:52,450
como continuar presionando máis e máis elementos na pila.

371
00:28:52,450 --> 00:28:56,000
Non é realmente moi código adicional.

372
00:28:56,000 --> 00:29:00,080
Só unha chamada - vostede ten que lembrar de obter as chamadas malloc alí correctamente,

373
00:29:00,080 --> 00:29:03,310
e despois descubrir cando está indo a chamar realloc.

374
00:29:03,310 --> 00:29:06,090
Isto é un reto divertido se vostede está interesado.

375
00:29:06,090 --> 00:29:11,550
>> Pero, por agora, imos seguir adiante, e imos falar sobre as filas.

376
00:29:11,550 --> 00:29:15,680
Rolar por aquí.

377
00:29:15,680 --> 00:29:19,340
A cola é un irmán preto da pila.

378
00:29:19,340 --> 00:29:25,380
Entón, na pila, as cousas que foron colocadas en último

379
00:29:25,380 --> 00:29:28,810
foron as primeiras cousas a ser recuperados.

380
00:29:28,810 --> 00:29:33,600
Temos este último en entrar, primeiro fóra, ou LIFO, ordenando.

381
00:29:33,600 --> 00:29:38,390
Considerando que, en fila, como sería de esperar a partir de cando está en pé na cola,

382
00:29:38,390 --> 00:29:41,980
a primeira persoa a entrar na cola, o primeiro en entrar na cola,

383
00:29:41,980 --> 00:29:47,630
é a primeira cousa que é recuperada da cola.

384
00:29:47,630 --> 00:29:51,490
As filas tamén son frecuentemente utilizados cando estamos lidando con gráficos,

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

386
00:29:55,560 --> 00:30:00,260
e as filas tamén son útiles para unha morea de outras cousas.

387
00:30:00,260 --> 00:30:06,180
Unha cousa que xorde moitas veces é tentar manter, por exemplo,

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

389
00:30:12,310 --> 00:30:17,650
E pode facer iso con unha matriz. Pode manter unha lista ordenada de cousas nunha matriz,

390
00:30:17,650 --> 00:30:20,650
pero onde que queda complicado é, entón sempre que atopa

391
00:30:20,650 --> 00:30:26,160
o lugar apropiado para introducir a seguinte cousa.

392
00:30:26,160 --> 00:30:28,250
Entón se ten unha matriz de números, do 1 ao 10,

393
00:30:28,250 --> 00:30:31,630
e entón quere ampliar isto para todos os números do 1 ao 100,

394
00:30:31,630 --> 00:30:33,670
e está quedando estes números de forma aleatoria e tentando manter todo

395
00:30:33,670 --> 00:30:40,650
clasificados como pasar, acaba tendo que facer unha chea de cambio.

396
00:30:40,650 --> 00:30:43,910
Con certos tipos de colas e certos tipos de estruturas de datos subxacentes,

397
00:30:43,910 --> 00:30:46,670
realmente pode perder lo moi sinxelo.

398
00:30:46,670 --> 00:30:50,640
Non ten que engadir algo e, a continuación reordene a cousa toda de cada vez.

399
00:30:50,640 --> 00:30:56,770
Non ten que facer unha chea de cambio dos elementos internos arredor.

400
00:30:56,770 --> 00:31:02,990
Cando ollamos para unha fila, vostede ve que - tamén en queue.c no código de sección -

401
00:31:02,990 --> 00:31:10,950
a estrutura que temos dado a vostede realmente é parecida coa estrutura que lle deu unha pila.

402
00:31:10,950 --> 00:31:13,770
>> Hai unha excepción a iso, e que unha excepción

403
00:31:13,770 --> 00:31:21,700
é que temos este enteiro adicional chamado a cabeza,

404
00:31:21,700 --> 00:31:28,120
eo xefe aquí é para manter o control da cabeza da cola,

405
00:31:28,120 --> 00:31:32,160
ou o primeiro elemento na cola.

406
00:31:32,160 --> 00:31:37,470
Con unha pila, fomos capaces de manter o control do elemento que estabamos a piques de recuperar,

407
00:31:37,470 --> 00:31:40,800
ou a parte superior da pila, utilizando só o tamaño,

408
00:31:40,800 --> 00:31:44,220
mentres que cunha cola, estamos tendo que xestione extremos opostos.

409
00:31:44,220 --> 00:31:49,000
Estamos intentando alinhavar as cousas en ao final, pero a continuación, voltar as cousas de fronte.

410
00:31:49,000 --> 00:31:54,640
Así, de forma eficaz, coa cabeza, temos o índice do inicio da fila,

411
00:31:54,640 --> 00:31:58,920
é o tamaño da-nos o índice do fin da cola

412
00:31:58,920 --> 00:32:03,730
para que poidamos recuperar as cousas da cabeza e engadir cousas a cola.

413
00:32:03,730 --> 00:32:06,890
Mentres que a pila, estabamos sempre só trata sobre o cume da pila.

414
00:32:06,890 --> 00:32:08,900
Nunca a acceder ao fondo da pila.

415
00:32:08,900 --> 00:32:12,220
Nós só engadiu cousas para arriba e levou as cousas fóra do arriba

416
00:32:12,220 --> 00:32:17,470
así nós non necesitamos que campo extra dentro da nosa estrutura.

417
00:32:17,470 --> 00:32:20,590
Isto xeralmente ten sentido?

418
00:32:20,590 --> 00:32:27,670
Todo ben. Si, Charlotte? [Charlotte, inintelixible]

419
00:32:27,670 --> 00:32:32,660
[Hardison] Iso é unha gran cuestión, e que foi un que xurdiu en charla.

420
00:32:32,660 --> 00:32:36,290
Quizais camiñando a través de algúns exemplos que ilustran por

421
00:32:36,290 --> 00:32:41,400
nós non queremos usar cordas [0] como xefe de fila.

422
00:32:41,400 --> 00:32:46,770
>> Entón, imaxine que temos a nosa cola, imos chamalo de cola.

423
00:32:46,770 --> 00:32:49,210
En principio, cando temos só instanciado-lo,

424
00:32:49,210 --> 00:32:53,330
cando temos só declarou que, non temos nada inicializar.

425
00:32:53,330 --> 00:32:56,790
É todo lixo. Entón, por suposto que queremos estar seguro de que arrincar

426
00:32:56,790 --> 00:33:00,950
tanto o tamaño e os campos de cabeza a ser 0, algo razoable.

427
00:33:00,950 --> 00:33:05,770
Tamén pode ir adiante e nulo fóra os elementos na nosa cola.

428
00:33:05,770 --> 00:33:09,930
E para facer este axuste diagrama, observe que agora a nosa cola só pode ter tres elementos;

429
00:33:09,930 --> 00:33:13,150
mentres que a nosa pila podería prender catro, a nosa cola só pode ter tres.

430
00:33:13,150 --> 00:33:18,680
E iso é só para facer o axuste diagrama.

431
00:33:18,680 --> 00:33:26,150
A primeira cousa que acontece aquí é que poñer na cola a cadea "ola".

432
00:33:26,150 --> 00:33:30,380
E, así como fixemos coa pila, nada moi diferente aquí,

433
00:33:30,380 --> 00:33:39,230
xogamos a corda no en cordas [0] e incrementar o noso tamaño en 1.

434
00:33:39,230 --> 00:33:42,720
Nós enfileirar "adeus", el e colocar.

435
00:33:42,720 --> 00:33:45,870
Polo tanto, esta parece unha pila para a maior parte.

436
00:33:45,870 --> 00:33:53,230
Nós comezamos aquí, elemento novo, elemento novo, o tamaño segue a subir.

437
00:33:53,230 --> 00:33:56,330
O que acontece neste momento cando queremos desenfileirar algo?

438
00:33:56,330 --> 00:34:01,280
Cando queremos retirarse da cola, que é o elemento que queremos retirarse da fila?

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 librar-se da primeira cadea, este, "ola".

441
00:34:10,960 --> 00:34:13,170
Entón, cal foi a outra cousa que cambiou?

442
00:34:13,170 --> 00:34:17,010
Teña en conta cando apareceu algo fóra da pila, só cambiou o tamaño,

443
00:34:17,010 --> 00:34:22,080
pero aquí temos un par de cousas que cambian.

444
00:34:22,080 --> 00:34:27,440
Non só a cambio de tamaño, pero os cambios de cabeza.

445
00:34:27,440 --> 00:34:31,020
Isto vai de volta ao punto de Charlotte anteriormente:

446
00:34:31,020 --> 00:34:38,699
Por que temos esta cabeza tamén?

447
00:34:38,699 --> 00:34:42,110
Será que ten sentido agora, Charlotte? Tipo de >>.

448
00:34:42,110 --> 00:34:47,500
[Hardison] Kind of? Entón, o que pasou cando dequeued?

449
00:34:47,500 --> 00:34:54,340
O que fixo a cabeza de facelo agora é interesante?

450
00:34:54,340 --> 00:34:56,449
[Charlotte] Ah, porque cambiou - todo ben. Eu vexo.

451
00:34:56,449 --> 00:35:02,090
Porque a cabeza - onde a cabeza está a apuntar cara mudanzas en termos de localización.

452
00:35:02,090 --> 00:35:07,200
Non é máis sempre un índice cero. >> Si, exactamente.

453
00:35:07,200 --> 00:35:17,660
O que pasou foi dequeueing o elemento de alta

454
00:35:17,660 --> 00:35:20,590
foi feito e nós non teñen esa cabeza campo

455
00:35:20,590 --> 00:35:26,880
porque estabamos sempre ligando esa cadea en 0 índice de xefe da nosa fila,

456
00:35:26,880 --> 00:35:30,170
entón teriamos que cambiar o resto da fila de abaixo.

457
00:35:30,170 --> 00:35:36,010
Nós teriamos que cambiar o "adeus" de de cordas [1] as cordas [0].

458
00:35:36,010 --> 00:35:38,760
E cordas [2] para abaixo para cordas [1].

459
00:35:38,760 --> 00:35:43,050
E nós temos que facer iso para toda a lista de elementos,

460
00:35:43,050 --> 00:35:45,110
toda a matriz de elementos.

461
00:35:45,110 --> 00:35:50,490
E cando estamos facendo iso con unha matriz, que queda moi caro.

462
00:35:50,490 --> 00:35:53,340
Entón, aquí, non é un gran negocio. Só temos tres elementos na nosa matriz.

463
00:35:53,340 --> 00:35:57,230
Pero se tivésemos unha fila de miles de elementos ou dun millón de elementos,

464
00:35:57,230 --> 00:36:00,060
e entón, de súpeto, comezan a facer unha chea de dequeue chama a todos en un loop,

465
00:36:00,060 --> 00:36:03,930
as cousas están realmente indo para desacelerar como cambia todo para abaixo constantemente.

466
00:36:03,930 --> 00:36:07,320
Vostede sabe, cambiar por 1, por un cambio de quenda, por 1, por un cambio.

467
00:36:07,320 --> 00:36:13,650
En vez diso, usan esa cabeza, chamamos iso dun "punteiro", a pesar de que non é realmente un punteiro

468
00:36:13,650 --> 00:36:16,430
en sentido estrito, non é un tipo de punteiro.

469
00:36:16,430 --> 00:36:19,410
Non é un * int ou char * ou algo así.

470
00:36:19,410 --> 00:36:28,930
Pero está a apuntar ou indicando o xefe da nosa fila. Si?

471
00:36:28,930 --> 00:36:38,800
>> [Estudante] Como dequeue sabe só pop fóra o que está na cabeza?

472
00:36:38,800 --> 00:36:43,620
[Hardison] Como dequeue saber como pop fóra todo o que está na cabeza? Dereito >>, si.

473
00:36:43,620 --> 00:36:49,050
>> O que está a ver é só o que a cabeza campo está definido.

474
00:36:49,050 --> 00:36:52,710
Así, neste primeiro caso, se miramos ben aquí,

475
00:36:52,710 --> 00:36:55,690
nosa cabeza é 0, 0 índice. >> Dereito.

476
00:36:55,690 --> 00:37:00,500
[Hardison] Entón el só di ben, ben, o elemento no índice 0, a secuencia de "ola",

477
00:37:00,500 --> 00:37:03,050
é o elemento na cabeza da nosa fila.

478
00:37:03,050 --> 00:37:05,570
Entón, imos para desenfileirar este cara.

479
00:37:05,570 --> 00:37:09,800
E iso vai ser un elemento que é devolto para o chamador.

480
00:37:09,800 --> 00:37:14,540
Si, Saad? Así, a cabeza >> basicamente define o - onde está indo para indexa-lo?

481
00:37:14,540 --> 00:37:17,750
Isto é o comezo? Si >>. Ok >>.

482
00:37:17,750 --> 00:37:22,900
[Hardison] que se está facendo o novo comezo para a nosa matriz.

483
00:37:22,900 --> 00:37:28,930
Entón, cando desenfileirar algo, todo o que precisa facer é acceder ao elemento no índice q.head,

484
00:37:28,930 --> 00:37:32,240
e que será o elemento que desexa eliminar da cola.

485
00:37:32,240 --> 00:37:34,930
Tamén ten que diminuír o tamaño.

486
00:37:34,930 --> 00:37:39,430
Imos ver un pouco as cousas están un pouco complicado con iso.

487
00:37:39,430 --> 00:37:46,520
Nós desenfileirar, e agora, se enfileirar novo,

488
00:37:46,520 --> 00:37:51,300
onde é que imos poñer na cola?

489
00:37:51,300 --> 00:37:55,000
Onde é que o próximo elemento ir na nosa cola?

490
00:37:55,000 --> 00:37:57,980
Dicir que queren pór na cola a cadea "CS".

491
00:37:57,980 --> 00:38:02,240
En cal índice vai? [Os alumnos] Strings [2]. >> Dous.

492
00:38:02,240 --> 00:38:04,980
Por 2 e non 0?

493
00:38:04,980 --> 00:38:13,570
[Basil] Porque agora a cabeza é 1, polo que é como o inicio da lista?

494
00:38:13,570 --> 00:38:21,220
[Hardison] Dereito. E o que indica o fin da lista?

495
00:38:21,220 --> 00:38:23,290
O que estabamos usando para indicar o final da nosa fila?

496
00:38:23,290 --> 00:38:25,970
A cabeza é o xefe da nosa fila, o inicio da nosa fila.

497
00:38:25,970 --> 00:38:29,530
O que é o fin da nosa fila? [Os alumnos] Tamaño. Tamaño >>, exactamente.

498
00:38:29,530 --> 00:38:36,360
Así, os nosos novos elementos entrar en tamaño, e os elementos que tiramos saír na cabeza.

499
00:38:36,360 --> 00:38:45,390
Cando enfileirar o seguinte elemento, estamos poñendo o en no tamaño.

500
00:38:45,390 --> 00:38:48,530
[Estudante] Antes de poñer isto en porén, tamaño era un, non?

501
00:38:48,530 --> 00:38:55,690
[Hardison] Dereito. Polo tanto, non moito en tamaño. + Tamaño, non un, pero a cabeza +.

502
00:38:55,690 --> 00:38:59,990
Porque cambiou todo pola cantidade cabeza.

503
00:38:59,990 --> 00:39:14,270
Entón, aquí, agora temos unha cola de tamaño 1 que comeza no índice 1.

504
00:39:14,270 --> 00:39:20,730
A cola é índice 2. Si?

505
00:39:20,730 --> 00:39:25,780
>> [Alumno] O que acontece cando dequeue cadeas [0], e as cordas "slots de memoria

506
00:39:25,780 --> 00:39:29,420
só se baleirou, basicamente, ou simplemente esquecida?

507
00:39:29,420 --> 00:39:34,700
[Hardison] Yeah. Neste sentido, estamos só esquece-los.

508
00:39:34,700 --> 00:39:42,640
Se estivésemos almacenar copias deles para -

509
00:39:42,640 --> 00:39:46,310
moitas estruturas de datos, moitas veces, almacenar as súas propias copias dos elementos

510
00:39:46,310 --> 00:39:51,760
de xeito que a persoa que xestiona a estrutura de datos non teñen que se preocupar

511
00:39:51,760 --> 00:39:53,650
sobre onde todos os punteiros están indo.

512
00:39:53,650 --> 00:39:56,000
A estrutura de datos segura para todo, suxeita a todas as copias,

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

514
00:39:59,580 --> 00:40:03,140
Con todo, neste caso, estas estruturas de datos só para simplificar,

515
00:40:03,140 --> 00:40:05,580
non están facendo copias de todo o que estamos almacenando en los.

516
00:40:05,580 --> 00:40:08,630
[Estudante] Entón este é un conxunto continuo de -? Si >>.

517
00:40:08,630 --> 00:40:14,350
Se miramos cara atrás, o que a definición foi desta estrutura é.

518
00:40:14,350 --> 00:40:19,110
É só unha matriz defecto, como viu,

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

520
00:40:24,280 --> 00:40:26,340
Será que -? >> Si, eu estaba pensando

521
00:40:26,340 --> 00:40:29,130
Se finalmente se esgote a memoria, de certa forma,

522
00:40:29,130 --> 00:40:32,330
se ten todos eses lugares baleiros na súa matriz?

523
00:40:32,330 --> 00:40:36,390
[Hardison] Si, é un bo punto.

524
00:40:36,390 --> 00:40:41,530
>> Se olharmos para o que pasou agora, neste punto,

525
00:40:41,530 --> 00:40:46,350
nós preenchemos a nosa cola, que parece.

526
00:40:46,350 --> 00:40:50,390
Pero nós non temos realmente cheo nosa cola

527
00:40:50,390 --> 00:40:57,710
porque temos unha fila que é tamaño 2, pero comeza o índice 1,

528
00:40:57,710 --> 00:41:02,160
porque é onde o noso punteiro cabeza.

529
00:41:02,160 --> 00:41:08,400
Como estaba dicindo, ese elemento en cadeas [0], o índice 0, non está realmente alí.

530
00:41:08,400 --> 00:41:10,450
Non está na nosa cola de máis.

531
00:41:10,450 --> 00:41:16,460
Nós só non se preocupou en ir e substitúe-lo cando dequeued-lo.

532
00:41:16,460 --> 00:41:18,700
Así, aínda que parece que estamos sen memoria, nós realmente non temos.

533
00:41:18,700 --> 00:41:23,270
Este punto está dispoñible para nós para usar.

534
00:41:23,270 --> 00:41:29,310
O comportamento adecuado, se fósemos tentar algo primeira dequeue

535
00:41:29,310 --> 00:41:34,420
como "bye", que sería pop bye fóra.

536
00:41:34,420 --> 00:41:38,460
Agora a nosa cola comeza o índice 2 e é de tamaño 1.

537
00:41:38,460 --> 00:41:42,240
E agora, se intentemos e enfileirar algo novo, digamos, 50,

538
00:41:42,240 --> 00:41:47,880
50 debe ir neste lugar no índice 0

539
00:41:47,880 --> 00:41:51,270
porque aínda está dispoñible para nós. Si, Saad?

540
00:41:51,270 --> 00:41:53,630
[Saad] Isto acontece automaticamente?

541
00:41:53,630 --> 00:41:56,150
[Hardison] Isto non acontece moito automaticamente. Ten que facer a matemática

542
00:41:56,150 --> 00:42:00,380
para facer o traballo, pero esencialmente o que fixemos é que acabamos enrolado.

543
00:42:00,380 --> 00:42:04,070
[Saad] E todo ben se isto ten un buraco no medio dela?

544
00:42:04,070 --> 00:42:08,720
[Hardison] e podemos facer as matemáticas funcionar correctamente.

545
00:42:08,720 --> 00:42:15,470
>> E resulta que iso non é realmente difícil de facer co operador mod.

546
00:42:15,470 --> 00:42:20,040
Así como fixemos con César e as cousas de cifrado,

547
00:42:20,040 --> 00:42:25,190
usando mod, podemos facer as cousas para involucrar e continuar

548
00:42:25,190 --> 00:42:28,090
arredor e arredor coa nosa cola,

549
00:42:28,090 --> 00:42:32,180
manter ese punteiro cabeza movendo.

550
00:42:32,180 --> 00:42:38,840
Nótese que o tamaño é sempre respectando o número de elementos, en realidade, dentro da cola.

551
00:42:38,840 --> 00:42:43,110
E iso é só o punteiro de cabeza que mantén bicicleta pasar.

552
00:42:43,110 --> 00:42:49,660
Se olharmos para o que pasou aquí, se volver para o inicio,

553
00:42:49,660 --> 00:42:55,020
e só ve o que pasa na cabeza

554
00:42:55,020 --> 00:42:58,240
cando enfileirar algo, nada aconteceu coa cabeza.

555
00:42:58,240 --> 00:43:00,970
Cando enfileirados outra cousa, nada aconteceu coa cabeza.

556
00:43:00,970 --> 00:43:04,130
Así que dequeued algo, a cabeza vai a por un.

557
00:43:04,130 --> 00:43:06,600
Nós enfileirado algo, non pasa nada na cabeza.

558
00:43:06,600 --> 00:43:11,060
Cando desenfileirar algo, de súpeto, a cabeza é incrementado.

559
00:43:11,060 --> 00:43:14,660
Cando enfileirar algo, non pasa nada na cabeza.

560
00:43:14,660 --> 00:43:20,240
>> O que sucedería, neste punto, se fósemos desenfileirar algo de novo?

561
00:43:20,240 --> 00:43:23,240
Todos os pensamentos? O que sucedería coa cabeza?

562
00:43:23,240 --> 00:43:27,190
O que debe ocorrer con cabeza

563
00:43:27,190 --> 00:43:32,990
se fósemos para desenfileirar outra cousa?

564
00:43:32,990 --> 00:43:35,400
A cabeza agora está no índice 2,

565
00:43:35,400 --> 00:43:38,920
o que significa que a cabeza da cola é cadeas [2].

566
00:43:38,920 --> 00:43:44,280
[Estudante] que retorna 0? >> Debe volver a 0. Debe involucrar en torno a volta, exactamente.

567
00:43:44,280 --> 00:43:48,440
Ata agora, cada vez que chama dequeue, estamos engadindo unha na cabeza,

568
00:43:48,440 --> 00:43:50,960
engadir un para a cabeza, engade unha para a cabeza, engade unha para a cabeza.

569
00:43:50,960 --> 00:43:58,400
Así que ese punteiro cabeza queda para o último índice na nosa matriz,

570
00:43:58,400 --> 00:44:05,650
entón temos que implica-la de volta ao redor para o comezo, voltar a 0.

571
00:44:05,650 --> 00:44:09,900
[Charlotte] O que determina a capacidade da fila nunha pila?

572
00:44:09,900 --> 00:44:13,120
[Hardison] Neste caso, acabamos usando ser unha constante # definido. Ok >>.

573
00:44:13,120 --> 00:44:19,590
[Hardison] O arquivo c real., Pode poñerse e xogar con el un pouco

574
00:44:19,590 --> 00:44:21,710
e facelo tan grande ou tan pouco como quere.

575
00:44:21,710 --> 00:44:25,310
[Charlotte] Entón, cando está facendo-se nunha cola, como fai o ordenador sabe

576
00:44:25,310 --> 00:44:29,120
como gran quere a pila para ser?

577
00:44:29,120 --> 00:44:31,700
[Hardison] Iso é unha gran cuestión.

578
00:44:31,700 --> 00:44:34,800
Hai un par de formas. Un é para define-lo na fronte

579
00:44:34,800 --> 00:44:42,050
e dicir que iso vai ser unha cola que ten 4 elementos ou 50 elementos ou 10.000.

580
00:44:42,050 --> 00:44:45,430
A outra forma é facer o que a xente está facendo edición de hackers

581
00:44:45,430 --> 00:44:52,310
e crear funcións para ter a súa cola crecer dinámicamente como máis cousas son engadidos dentro

582
00:44:52,310 --> 00:44:54,740
>> [Charlotte] Entón, para ir coa primeira opción, o que usa sintaxe

583
00:44:54,740 --> 00:44:57,830
para dicir ao programa que é o tamaño da cola?

584
00:44:57,830 --> 00:45:04,780
[Hardison] Ah. Entón, imos saír desta.

585
00:45:04,780 --> 00:45:12,650
Eu aínda estou en stack.c aquí, entón eu estou indo só para rolar ata o cumio aquí.

586
00:45:12,650 --> 00:45:17,920
Podes ver iso aquí? Este é o # define capacidade 10.

587
00:45:17,920 --> 00:45:24,600
E iso é case exactamente a mesma sintaxe que temos para cola.

588
00:45:24,600 --> 00:45:28,390
Excepto na cola, temos que o campo estrutura extra aquí.

589
00:45:28,390 --> 00:45:32,760
[Charlotte] Oh, eu penso que a capacidade significaba a capacidade para a cadea.

590
00:45:32,760 --> 00:45:36,770
[Hardison] Ah. >> Iso é o lonxitude máxima da palabra. >> Entender.

591
00:45:36,770 --> 00:45:41,180
Si A capacidade aquí - que é un gran punto.

592
00:45:41,180 --> 00:45:44,000
E iso é algo que é complicado

593
00:45:44,000 --> 00:45:49,480
porque o que temos declarado aquí é unha matriz de char * s.

594
00:45:49,480 --> 00:45:52,770
Unha matriz de punteiros.

595
00:45:52,770 --> 00:45:56,690
Esta é unha matriz de caracteres.

596
00:45:56,690 --> 00:46:01,690
Este é probablemente o que viu cando foi declarar os seus buffers para o arquivo I / O,

597
00:46:01,690 --> 00:46:06,840
cando foi crear cadeas manualmente na pila.

598
00:46:06,840 --> 00:46:09,090
Con todo, o que temos aquí é unha matriz de char * s.

599
00:46:09,090 --> 00:46:13,400
Entón, é unha matriz de punteiros.

600
00:46:13,400 --> 00:46:18,350
En realidade, o zoom para fóra, e miramos o que está a suceder aquí

601
00:46:18,350 --> 00:46:23,140
na presentación, ve que os elementos reais, os datos de carácter

602
00:46:23,140 --> 00:46:26,180
non se garda dentro da propia matriz.

603
00:46:26,180 --> 00:46:42,690
O que está almacenada dentro da nosa matriz aquí son punteiros para os datos de caracteres.

604
00:46:42,690 --> 00:46:52,560
Okay. Entón, vimos como o tamaño da cola é como a pila,

605
00:46:52,560 --> 00:46:58,670
o tamaño respecta sempre o número de elementos na cola neste momento.

606
00:46:58,670 --> 00:47:02,720
Despois de facer 2 enfileira, o tamaño é 2.

607
00:47:02,720 --> 00:47:07,110
Despois de facer unha dequeue o tamaño agora é 1.

608
00:47:07,110 --> 00:47:09,330
Despois de facer outra enqueue o tamaño está de volta a 2.

609
00:47:09,330 --> 00:47:12,340
Así, o tamaño definitivamente respecta ao número de elementos na cola,

610
00:47:12,340 --> 00:47:15,580
e despois a cabeza só mantén ciclismo.

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

612
00:47:20,210 --> 00:47:25,620
E cada vez que chamamos dequeue, o punteiro cabeza é incrementado para o próximo curso.

613
00:47:25,620 --> 00:47:29,930
E a cabeza está a piques de pasar por riba, el volve a 0.

614
00:47:29,930 --> 00:47:34,870
Entón, con iso, podemos escribir a función dequeue.

615
00:47:34,870 --> 00:47:40,200
E imos deixar a función enqueue para vós para aplicar no seu lugar.

616
00:47:40,200 --> 00:47:45,880
>> Cando desenfileirar un elemento da nosa fila,

617
00:47:45,880 --> 00:47:55,490
cal foi o primeiro que Daniel fixo cando comezou a escribir a función pop para pilas?

618
00:47:55,490 --> 00:48:00,490
Deixe-me escoitar de alguén que non teña falado aínda.

619
00:48:00,490 --> 00:48:06,710
Imos ver, Saad, se recorda o que Daniel fixo o que a primeira cousa cando escribiu pop?

620
00:48:06,710 --> 00:48:08,860
[Saad] Non foi - >> El probou algo.

621
00:48:08,860 --> 00:48:12,140
[Saad] Se o tamaño é maior que 0. >> Exactamente.

622
00:48:12,140 --> 00:48:14,390
E o que foi que o exame para?

623
00:48:14,390 --> 00:48:19,090
[Saad] Iso foi unha proba para ver se hai algo dentro da matriz.

624
00:48:19,090 --> 00:48:23,210
[Hardison] Yeah. Exactamente. Entón non pode aparecer calquera cousa fóra da pila, se está baleiro.

625
00:48:23,210 --> 00:48:26,510
Do mesmo xeito, non se pode retirar da fila calquera cousa de unha fila se está baleiro.

626
00:48:26,510 --> 00:48:30,420
Cal é a primeira cousa que temos que facer a nosa función dequeue aquí, que pensas?

627
00:48:30,420 --> 00:48:33,860
[Saad] Se o tamaño é maior que 0? Si >>.

628
00:48:33,860 --> 00:48:37,710
Neste caso, realmente só probado para ver se é 0.

629
00:48:37,710 --> 00:48:42,240
Se é 0, podemos volver nulo.

630
00:48:42,240 --> 00:48:45,280
Pero a lóxica exactamente o mesmo.

631
00:48:45,280 --> 00:48:49,110
E imos seguir con iso.

632
00:48:49,110 --> 00:48:54,600
Se o tamaño non é 0, onde é o elemento que queremos retirarse da fila?

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

634
00:48:58,550 --> 00:49:01,720
Podemos só retirar o primeiro elemento na nosa cola

635
00:49:01,720 --> 00:49:07,040
acceder ao elemento na cabeza.

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

637
00:49:14,630 --> 00:49:19,620
Despois diso, o que temos que facer? O que ten que ocorrer?

638
00:49:19,620 --> 00:49:23,740
Cal foi a outra cousa que falamos no dequeue?

639
00:49:23,740 --> 00:49:28,130
Dúas cousas ten que acontecer, porque a nosa cola cambiou.

640
00:49:28,130 --> 00:49:35,640
[Daniel] Reducir o tamaño. >> Temos de reducir o tamaño e aumentar a cabeza? Exactamente.

641
00:49:35,640 --> 00:49:40,600
Para aumentar a cabeza, non podemos só cega aumentar a cabeza, lembre-se.

642
00:49:40,600 --> 00:49:45,080
Non podemos só facer queue.head + +.

643
00:49:45,080 --> 00:49:51,630
Temos tamén a incluír este mod pola capacidade.

644
00:49:51,630 --> 00:49:54,740
E por que mod por capacidade, Stella?

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

646
00:49:58,680 --> 00:50:04,750
Nós mod pola capacidade porque ten que implicar a volta a 0.

647
00:50:04,750 --> 00:50:07,400
Entón, agora, neste momento, podemos facer o que dixo Daniel.

648
00:50:07,400 --> 00:50:12,700
Podemos diminuír o tamaño.

649
00:50:12,700 --> 00:50:29,170
E entón podemos simplemente devolver o elemento que estaba no inicio da fila.

650
00:50:29,170 --> 00:50:34,000
Mira o tipo de gnarly en primeiro lugar. Pode ter unha pregunta. Sentímolo?

651
00:50:34,000 --> 00:50:37,260
>> [Sam] Por que é o primeiro na parte superior da fila? Onde é que isto vai?

652
00:50:37,260 --> 00:50:42,480
[Hardison] Vén da cuarta liña do fondo.

653
00:50:42,480 --> 00:50:46,060
Despois de que probar para estar seguro de que a nosa cola non está baleira,

654
00:50:46,060 --> 00:50:54,100
nós retiramos char * En primeiro lugar, elimina o elemento que está sentado no índice cabeza

655
00:50:54,100 --> 00:50:58,680
da nosa matriz, da nosa matriz cordas >>, e chamada que primeiro?

656
00:50:58,680 --> 00:51:04,500
[Hardison] E chamamos iso de primeira. Si

657
00:51:04,500 --> 00:51:09,850
Só para acompañar iso, por que pensas que tivemos que facer iso?

658
00:51:09,850 --> 00:51:18,270
[Sam] Cada primeiro só retornando q.strings [q.head]? Si >>.

659
00:51:18,270 --> 00:51:23,830
>> Porque estamos facendo isto cambio q.head coa función mod,

660
00:51:23,830 --> 00:51:27,810
e non hai forma de facelo dentro da liña de retorno tamén.

661
00:51:27,810 --> 00:51:31,640
[Hardison] Exactamente. Vostede está no lugar. Sam está totalmente recoñecidas.

662
00:51:31,640 --> 00:51:36,800
A razón pola que tivo que retirar o primeiro elemento na nosa cola e almacena-lo nunha variable

663
00:51:36,800 --> 00:51:43,030
é porque esta liña que só q.head,

664
00:51:43,030 --> 00:51:47,030
hai operador mod alí non é algo que podemos facer

665
00:51:47,030 --> 00:51:51,230
e telo en vigor na cabeza sen - nunha única liña.

666
00:51:51,230 --> 00:51:54,480
Entón, nós realmente temos que aproveitar o primeiro elemento, a continuación, axuste a cabeza,

667
00:51:54,480 --> 00:52:00,430
axustar o tamaño, e, a continuación, voltar o elemento que tirou.

668
00:52:00,430 --> 00:52:02,680
E iso é algo que imos ver xurdir máis tarde con

669
00:52:02,680 --> 00:52:04,920
listas ligadas, como xogar con eles.

670
00:52:04,920 --> 00:52:08,410
Moitas veces, cando está liberando ou eliminación de listas ligadas

671
00:52:08,410 --> 00:52:13,500
hai que lembrar o seguinte elemento, o punteiro preto dunha lista ligada

672
00:52:13,500 --> 00:52:16,330
antes de descartar o actual.

673
00:52:16,330 --> 00:52:23,580
Porque senón tirar a información que queda na lista.

674
00:52:23,580 --> 00:52:34,160
Agora, se vai para o seu dispositivo, abre queue.c X fóra deste.

675
00:52:34,160 --> 00:52:39,390
Entón, se eu abrir queue.c, deixe-me zoom aquí,

676
00:52:39,390 --> 00:52:44,970
vai ver que ten un arquivo similar para o futuro.

677
00:52:44,970 --> 00:52:49,200
Parecidas ficheiro co que tiñamos antes con stack.c.

678
00:52:49,200 --> 00:52:54,690
Nós temos a nosa estrutura de cola definida só como vimos nos diapositivas.

679
00:52:54,690 --> 00:52:59,870
>> Nós temos a nosa función enqueue que é para facer.

680
00:52:59,870 --> 00:53:04,340
E nós temos a función dequeue aquí.

681
00:53:04,340 --> 00:53:06,870
A función dequeue no arquivo non implementado,

682
00:53:06,870 --> 00:53:13,230
pero vou poñer-lo de volta en PowerPoint para que poida escriba-lo, se queres.

683
00:53:13,230 --> 00:53:16,690
Así, para os próximos 5 minutos ou máis, vostedes traballan en enqueue

684
00:53:16,690 --> 00:53:22,570
que é case o contrario do dequeue.

685
00:53:22,570 --> 00:53:29,560
Non ten que axustar cabeza cando está enqueueing, pero o que ten que axustar?

686
00:53:29,560 --> 00:53:38,920
Tamaño. Entón, cando enqueue, a cabeza permanece intocada, o tamaño é alterado.

687
00:53:38,920 --> 00:53:46,920
Mais é preciso un pouco de - vostede vai ter que xogar con esa mod

688
00:53:46,920 --> 00:53:57,560
para descubrir o que o índice do novo elemento debe ser inserido no.

689
00:53:57,560 --> 00:54:03,080
Entón, eu vou dar a vostedes un pouco, poñer desenfileirar volta no slide,

690
00:54:03,080 --> 00:54:05,200
e como vostedes teñen preguntas, berrar-los para que poidamos

691
00:54:05,200 --> 00:54:09,220
todos falan sobre eles como un grupo.

692
00:54:09,220 --> 00:54:13,960
Ademais, o tamaño que non - cando axustar o tamaño, pode sempre -

693
00:54:13,960 --> 00:54:18,720
ten para modificar o tamaño de sempre? [Daniel] Non >> Non ten para modificar o tamaño, a dereita.

694
00:54:18,720 --> 00:54:24,260
Como o tamaño sempre, se está - supoñendo que está administrando as cousas de forma adecuada,

695
00:54:24,260 --> 00:54:30,840
o tamaño será sempre entre 0 e 3.

696
00:54:30,840 --> 00:54:38,680
Onde ten que mod cando está facendo enqueue?

697
00:54:38,680 --> 00:54:41,060
[Estudante] Só a cabeza. Só >> para a cabeza, exactamente.

698
00:54:41,060 --> 00:54:44,620
E por que ten de mod en todo enqueue?

699
00:54:44,620 --> 00:54:48,830
Cando é unha situación en que ten que mod?

700
00:54:48,830 --> 00:54:53,630
[Estudante] Se ten cousas en espazos como en espazos 1 e 2,

701
00:54:53,630 --> 00:54:55,950
e despois que necesitas para engadir algo a 0.

702
00:54:55,950 --> 00:55:02,570
[Hardison] Si, exactamente. Entón, se o punteiro cabeza está no fin,

703
00:55:02,570 --> 00:55:14,210
ou se o seu tamaño, máis a súa cabeza é grande, ou mellor, vai involucrar en torno á cola.

704
00:55:14,210 --> 00:55:17,830
>> Entón, nesa situación que temos aquí enriba no slide agora,

705
00:55:17,830 --> 00:55:24,370
se eu queira poñer na cola algo agora,

706
00:55:24,370 --> 00:55:31,110
queremos algo enfileirar no índice 0.

707
00:55:31,110 --> 00:55:35,450
Entón, se ollar para onde o 50 vai, e eu chamo enqueue 50,

708
00:55:35,450 --> 00:55:40,840
vai alí no fondo. El vai en 0 índice.

709
00:55:40,840 --> 00:55:44,160
El substitúe o 'ola' que xa foi retirado da cola.

710
00:55:44,160 --> 00:55:46,210
[Daniel] Non Tomé o coidado de que en dequeue xa?

711
00:55:46,210 --> 00:55:50,550
Por que facer algo coa cabeza en enqueue?

712
00:55:50,550 --> 00:55:55,770
[Hardison] Ah, entón non está modificando a cabeza, me desculpe.

713
00:55:55,770 --> 00:56:02,310
Pero tes que usar o operador mod cando está accedendo

714
00:56:02,310 --> 00:56:04,250
o elemento que quere poñer na cola cando está accedendo

715
00:56:04,250 --> 00:56:06,960
o seguinte elemento na súa cola.

716
00:56:06,960 --> 00:56:10,960
[Basil] Eu non fixen iso, e eu teño "éxito" por alí.

717
00:56:10,960 --> 00:56:13,370
[Daniel] Oh, eu entendo o que está dicindo.

718
00:56:13,370 --> 00:56:16,240
[Hardison] Entón didn't - fixo no q.size?

719
00:56:16,240 --> 00:56:20,670
[Basil] Yeah. Eu só cambiou de lado, eu non fixen nada coa cabeza.

720
00:56:20,670 --> 00:56:24,300
[Hardison] Realmente non ten que restaurar a cabeza para ser calquera cousa,

721
00:56:24,300 --> 00:56:31,650
pero cando índice na matriz cordas,

722
00:56:31,650 --> 00:56:39,500
realmente ten que ir adiante e calcular onde o próximo elemento,

723
00:56:39,500 --> 00:56:44,230
withe porque a pila, o elemento seguinte na súa pila sempre foi

724
00:56:44,230 --> 00:56:48,740
no índice correspondente ao tamaño.

725
00:56:48,740 --> 00:56:55,850
Se miramos cara atrás ata a nosa función push pila,

726
00:56:55,850 --> 00:57:03,100
podemos sempre plunk no noso novo elemento á dereita no tamaño do índice.

727
00:57:03,100 --> 00:57:06,710
Considerando que, coa cola, non podemos facelo

728
00:57:06,710 --> 00:57:10,340
porque, se estamos nesta situación,

729
00:57:10,340 --> 00:57:18,130
se enfileirado 50 cadea de noso novo ía ben no strings [1]

730
00:57:18,130 --> 00:57:20,540
que non queremos facer.

731
00:57:20,540 --> 00:57:41,200
Queremos ter a nova cadea ir no índice 0.

732
00:57:41,200 --> 00:57:44,320
>> Alguén - si? [Estudante] Eu teño unha pregunta, pero non é realmente relacionados.

733
00:57:44,320 --> 00:57:48,160
O que significa cando alguén só chama algo así como punteiro pred?

734
00:57:48,160 --> 00:57:51,260
O que é que o nome curto para? Sei que é só un nome.

735
00:57:51,260 --> 00:57:59,110
[Hardison] punteiro Pred? Imos ver. En que contexto?

736
00:57:59,110 --> 00:58:01,790
[Alumno] Foi para a inserción. Podo pedir-lle máis tarde, se quere

737
00:58:01,790 --> 00:58:03,920
porque realmente non é relacionado, pero eu só -

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

739
00:58:07,300 --> 00:58:10,860
Podemos tirar isto e falar sobre iso.

740
00:58:10,860 --> 00:58:15,550
Imos falar sobre iso a continuación, unha vez que temos de listas ligadas.

741
00:58:15,550 --> 00:58:21,440
>> Entón, imos moi rápido ollar para o que a función enqueue parece.

742
00:58:21,440 --> 00:58:26,530
Cal foi o primeiro que as persoas tentaron facer na súa liña enqueue? Para esta fila?

743
00:58:26,530 --> 00:58:29,960
Semellante ao que fixo para a pila de empurrar.

744
00:58:29,960 --> 00:58:32,080
O que fixo, Stella?

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

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

747
00:58:45,700 --> 00:58:54,720
Eu teño poñer o meu dispositivo no lugar seguro - regresar falso.

748
00:58:54,720 --> 00:59:01,370
Zoom un pouco. Okay.

749
00:59:01,370 --> 00:59:03,800
Agora, cal é a seguinte cousa que temos que facer?

750
00:59:03,800 --> 00:59:11,370
Así como coa pila, e inserida no lugar seguro.

751
00:59:11,370 --> 00:59:16,010
E así o que era o lugar seguro para introducir esa?

752
00:59:16,010 --> 00:59:23,170
Coa pila era o tamaño do índice, con iso, non é ben así.

753
00:59:23,170 --> 00:59:30,210
[Daniel] Eu teño q.head--ou - q.strings >>? >> Si

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

755
00:59:40,470 --> 00:59:42,740
[Hardison] Nós probablemente quere poñer parénteses en torno a este

756
00:59:42,740 --> 00:59:48,830
de xeito que nós estamos comezando a precedencia axeitada e de modo que é cleart a todos.

757
00:59:48,830 --> 00:59:55,800
E establecer que igual? >> Para str? >> Para str. Grande.

758
00:59:55,800 --> 01:00:00,160
E agora o que é a última cousa que temos que facer?

759
01:00:00,160 --> 01:00:06,780
Así como fixemos na pila. >> Incrementar o tamaño? >> Incrementar o tamaño.

760
01:00:06,780 --> 01:00:13,830
Boom. E entón, xa que o código de inicio só retornou falso por defecto,

761
01:00:13,830 --> 01:00:27,460
queremos cambiar isto para true todo pasa e todo vai ben.

762
01:00:27,460 --> 01:00:33,050
Todo ben. Isto é unha morea de información para sección.

763
01:00:33,050 --> 01:00:39,480
Non somos moito máis. Queremos falar moi rapidamente sobre illadamente conectados listas.

764
01:00:39,480 --> 01:00:44,010
Vou poñer isto para que poidamos volver a el máis tarde.

765
01:00:44,010 --> 01:00:50,850
Pero imos voltar a nosa presentación para só algúns diapositivas.

766
01:00:50,850 --> 01:00:53,790
Entón enqueue é todo, agora temos feito isto.

767
01:00:53,790 --> 01:00:57,430
>> Agora imos dar un ollo illadamente conectados listas.

768
01:00:57,430 --> 01:01:00,040
Nós conversas sobre iso un pouco máis na charla.

769
01:01:00,040 --> 01:01:02,540
Como moitos de vostedes viu a demo onde tivemos persoas

770
01:01:02,540 --> 01:01:08,220
desajeitadamente apuntando a outros números e cada unha explotación? >> Eu estaba nesa.

771
01:01:08,220 --> 01:01:16,620
>> O que vostedes pensan? Fixen iso, espero que desmitificar estes un pouco?

772
01:01:16,620 --> 01:01:25,990
Cunha lista, verifícase que xestione ese tipo que nós imos chamar un nó.

773
01:01:25,990 --> 01:01:32,520
Considerando que, coa cola ea pila que tiñamos estruturas que chamamos de cola na pila,

774
01:01:32,520 --> 01:01:34,860
tivemos estes nova fila en tipos de pila,

775
01:01:34,860 --> 01:01:39,240
aquí unha lista realmente está feita só de unha morea de nós.

776
01:01:39,240 --> 01:01:45,920
Do mesmo xeito que as cordas son só unha morea de chars todo aliñados ao lado do outro.

777
01:01:45,920 --> 01:01:50,650
Unha lista ligada é só un nó e outro no e outro no e outro nodo.

778
01:01:50,650 --> 01:01:55,080
E, en vez de esmagar todos os nós e almacena-los en conxunto de forma contigua

779
01:01:55,080 --> 01:01:58,090
todos á beira uns dos outros na memoria,

780
01:01:58,090 --> 01:02:04,470
ter este punteiro próximo nos permite almacenar os nós onde queira que, de forma aleatoria.

781
01:02:04,470 --> 01:02:10,500
E, a continuación, o tipo de fío de todos eles en conxunto para o punto de un para o outro.

782
01:02:10,500 --> 01:02:15,850
>> E o que era a gran vantaxe que esta tivo sobre unha matriz?

783
01:02:15,850 --> 01:02:21,680
Sobre todo o almacenamento de forma contigua só preso ao lado do outro?

784
01:02:21,680 --> 01:02:24,190
Vostede recorda? Si? >> Alocação de memoria dinámica?

785
01:02:24,190 --> 01:02:27,220
>> Alocação de memoria dinámica en que sentido?

786
01:02:27,220 --> 01:02:31,780
[Estudante] En que pode continuar facendo-o máis grande e non ten que mover o conxunto enteiro?

787
01:02:31,780 --> 01:02:40,940
[Hardison] Exactamente. Así, con unha matriz, cando quere poñer un novo elemento para o medio,

788
01:02:40,940 --> 01:02:45,320
ten que cambiar todo para o espazo.

789
01:02:45,320 --> 01:02:47,880
E como falamos coa cola,

790
01:02:47,880 --> 01:02:50,080
é por iso que manter o punteiro cabeza,

791
01:02:50,080 --> 01:02:52,050
de xeito que non estamos constantemente cambiando as cousas.

792
01:02:52,050 --> 01:02:54,520
Porque iso queda caro, se ten unha gran matriz

793
01:02:54,520 --> 01:02:57,130
e está constantemente facendo esas insercións aleatorias.

794
01:02:57,130 --> 01:03:00,820
Considerando que, con unha lista, todo o que tes que facer é xoga-lo en un novo nodo,

795
01:03:00,820 --> 01:03:06,330
axustar os punteiros, e está feito.

796
01:03:06,330 --> 01:03:10,940
O que suga sobre iso?

797
01:03:10,940 --> 01:03:16,830
Fóra o feito de que non é tan fácil de traballar como unha matriz? Si?

798
01:03:16,830 --> 01:03:22,980
[Daniel] Ben, eu creo que é moito máis difícil de acceder a un elemento específico na lista ligada?

799
01:03:22,980 --> 01:03:30,470
[Hardison] Non pode simplemente saltar dun elemento arbitrario no medio da lista de relacionados.

800
01:03:30,470 --> 01:03:33,800
Como é que ten que facer iso en vez diso? >> Ten que percorrer a cousa toda.

801
01:03:33,800 --> 01:03:35,660
[Hardison] Yeah. Ten que pasar por un de cada vez, unha de cada vez.

802
01:03:35,660 --> 01:03:38,480
É unha enorme - é unha dor.

803
01:03:38,480 --> 01:03:41,550
Cal é a outra - non hai outra caída para iso.

804
01:03:41,550 --> 01:03:45,340
[Basil] Vostede non pode ir para adiante e cara atrás? Ten que ir nunha dirección?

805
01:03:45,340 --> 01:03:48,570
[Hardison] Yeah. Entón, como imos solucionar isto, ás veces?

806
01:03:48,570 --> 01:03:53,370
[Basil] dobremente vinculada listas? >> Exactamente. Hai listas dobremente ligadas.

807
01:03:53,370 --> 01:03:55,540
Hai tamén - moi?

808
01:03:55,540 --> 01:03:57,620
>> [Sam] É o mesmo que usar a cousa que pred -

809
01:03:57,620 --> 01:04:01,090
Acaba de me lembrar, non é iso que a cousa é para pred?

810
01:04:01,090 --> 01:04:05,850
Non é que entre dobre e individual?

811
01:04:05,850 --> 01:04:10,020
Ollar [Hardison] Imos para o que exactamente estaba facendo.

812
01:04:10,020 --> 01:04:15,760
Entón, imos alí. Aquí está a lista de códigos.

813
01:04:15,760 --> 01:04:25,620
Aquí temos predptr, aquí. É iso o que estaba falando?

814
01:04:25,620 --> 01:04:30,750
Polo tanto, este foi - está liberando unha lista e está intentando gardar un punteiro para el.

815
01:04:30,750 --> 01:04:35,000
Este non é o dobre, vinculada illadamente-listas.

816
01:04:35,000 --> 01:04:40,090
Podemos falar máis sobre iso máis tarde xa que este está falando sobre a liberación da lista

817
01:04:40,090 --> 01:04:42,900
e quero mostrar algunhas outras cousas primeiro.

818
01:04:42,900 --> 01:04:51,480
pero é só - é lembrar o valor de PTR

819
01:04:51,480 --> 01:04:54,170
[Estudante] Ah, é punteiro precedente? Si >>.

820
01:04:54,170 --> 01:05:04,070
Para que poidamos entón incrementar PTR-se antes de que, entón, libre predptr que é.

821
01:05:04,070 --> 01:05:09,130
Porque nós non podemos PTR libre e despois chamar PTR = PTR vén, non?

822
01:05:09,130 --> 01:05:11,260
Iso sería malo.

823
01:05:11,260 --> 01:05:20,940
Entón imos ver, de novo este cara.

824
01:05:20,940 --> 01:05:23,900
>> A outra cousa ruín sobre listas é que, mentres que cunha matriz

825
01:05:23,900 --> 01:05:26,520
temos só todos os elementos propios apiladas de xeito conxunto,

826
01:05:26,520 --> 01:05:29,050
Aquí tamén temos introducido este punteiro.

827
01:05:29,050 --> 01:05:34,060
Polo tanto, hai unha peza adicional de memoria que estamos tendo que usar

828
01:05:34,060 --> 01:05:37,910
para cada elemento que estamos gardando na nosa lista.

829
01:05:37,910 --> 01:05:40,030
Temos flexibilidade, pero ten un custo.

830
01:05:40,030 --> 01:05:42,230
El vén con ese tempo, custo

831
01:05:42,230 --> 01:05:45,270
e el vén con ese custo de memoria tamén.

832
01:05:45,270 --> 01:05:47,800
Tempo, no sentido de que agora temos que pasar por cada elemento na matriz

833
01:05:47,800 --> 01:05:58,670
para atopar o índice de 10, ou que sería índice 10 nunha matriz.

834
01:05:58,670 --> 01:06:01,230
>> Só moi rapidamente, cando diagrama de fóra destas listas,

835
01:06:01,230 --> 01:06:05,980
normalmente temos a cabeza da lista ou o primeiro punteiro da lista

836
01:06:05,980 --> 01:06:08,010
e teña en conta que este é un punteiro verdade.

837
01:06:08,010 --> 01:06:11,100
É só 4 bytes. Non é un nó en si.

838
01:06:11,100 --> 01:06:17,120
Entón ve que non ten valor int nel, ningún punteiro próxima nel.

839
01:06:17,120 --> 01:06:20,790
É literalmente só un punteiro.

840
01:06:20,790 --> 01:06:23,550
Vai apuntar para algo que é unha estrutura de nodo real.

841
01:06:23,550 --> 01:06:28,480
[Sam] Un punteiro chamado nó? >> Este é - non. Este é un punteiro para algo do tipo de nodo.

842
01:06:28,480 --> 01:06:32,540
É un punteiro para unha estrutura de nodo. >> Ah, ok.

843
01:06:32,540 --> 01:06:36,870
Diagrama sobre o código, esquerda á dereita.

844
01:06:36,870 --> 01:06:42,190
Podemos definilo como nulo, o que é unha boa forma de comezar.

845
01:06:42,190 --> 01:06:49,850
Cando diagrama, quere gravala-lo como nulo ou poñer unha liña a través del así.

846
01:06:49,850 --> 01:06:53,910
>> Unha das formas máis fáciles de traballar con listas,

847
01:06:53,910 --> 01:06:57,430
e pedimos que tanto prepend e achegar para ver as diferenzas entre os dous,

848
01:06:57,430 --> 01:07:01,320
prepending pero é sempre máis fácil.

849
01:07:01,320 --> 01:07:05,790
Cando precede, este é o lugar onde - cando prepend (7),

850
01:07:05,790 --> 01:07:10,050
vai crear a estrutura do nodo

851
01:07:10,050 --> 01:07:13,870
e definir primeiro a apuntar cara a el, porque agora, xa que prefixado,

852
01:07:13,870 --> 01:07:17,240
vai estar no inicio da lista.

853
01:07:17,240 --> 01:07:22,540
Se prepend (3), que crea un outro no, pero agora 3 vén antes do 7.

854
01:07:22,540 --> 01:07:31,130
Entón estamos esencialmente empurrando as cousas para a nosa lista.

855
01:07:31,130 --> 01:07:34,720
Agora, podes ver que prepend, ás veces, as persoas chaman de empurrar,

856
01:07:34,720 --> 01:07:39,600
porque está empurrando un novo elemento na súa lista.

857
01:07:39,600 --> 01:07:43,270
Tamén é doado de borrar diante de unha lista.

858
01:07:43,270 --> 01:07:45,650
Entón, as persoas moitas veces chamada de pop.

859
01:07:45,650 --> 01:07:52,200
E desta maneira, pode emular unha pila empregando unha lista ligada.

860
01:07:52,200 --> 01:07:57,880
Gritos. Sentímolo, agora estamos entrando en aumento. Entón aquí nós prefixado (7), agora prepend (3).

861
01:07:57,880 --> 01:08:02,600
Se prefixado algo máis desta lista, se prefixado (4),

862
01:08:02,600 --> 01:08:06,540
entón temos 4 e logo 3 e despois 7.

863
01:08:06,540 --> 01:08:14,220
Entón nós podería pop e eliminar 4, elimina 3, elimine 7.

864
01:08:14,220 --> 01:08:16,500
Moitas veces, a forma máis intuitiva de pensar sobre iso é con aumento.

865
01:08:16,500 --> 01:08:20,310
Entón eu diagramado para fóra o que sería parecido engadir aquí.

866
01:08:20,310 --> 01:08:23,380
Aquí, adxunto (7) non parece ser diferente

867
01:08:23,380 --> 01:08:25,160
porque hai só un elemento da lista.

868
01:08:25,160 --> 01:08:28,620
E anexando (3) pon-lo ao final.

869
01:08:28,620 --> 01:08:31,020
Quizais podes ver agora o truco con append

870
01:08:31,020 --> 01:08:36,600
é que dende que nós só sabemos onde o principio da lista,

871
01:08:36,600 --> 01:08:39,450
Para achegar a unha lista que ten que andar todo o camiño a través da lista

872
01:08:39,450 --> 01:08:46,500
para chegar ao fin, deixar, a continuación, construír o nó e todo dólar abaixo.

873
01:08:46,500 --> 01:08:50,590
Chame todas as cousas para arriba.

874
01:08:50,590 --> 01:08:55,170
Así, con prepend, como acabamos resgou esta moi rapidamente,

875
01:08:55,170 --> 01:08:58,170
cando precede a unha lista, é moi sinxelo.

876
01:08:58,170 --> 01:09:02,960
>> Fai o seu novo nodo, implica algún distribución dinámica de memoria.

877
01:09:02,960 --> 01:09:09,830
Entón aquí estamos facendo un struct nodo usando malloc.

878
01:09:09,830 --> 01:09:14,710
Entón malloc estamos usando porque iso vai reservar memoria para nós para máis tarde

879
01:09:14,710 --> 01:09:20,350
porque nós non queremos iso - queremos esa memoria a continuar por un longo tempo.

880
01:09:20,350 --> 01:09:25,350
E nós temos un punteiro para o espazo na memoria que só alocado.

881
01:09:25,350 --> 01:09:29,260
Usan tamaño nó, non sumar os campos.

882
01:09:29,260 --> 01:09:31,899
Non xerar a man o número de bytes,

883
01:09:31,899 --> 01:09:39,750
en vez diso, use sizeof para que saibamos que estamos recibindo un número adecuado de bytes.

884
01:09:39,750 --> 01:09:43,660
Temos seguro de que o noso para probar chamada malloc conseguiu.

885
01:09:43,660 --> 01:09:47,939
Iso é algo que quere facer en xeral.

886
01:09:47,939 --> 01:09:52,590
En máquinas modernas, a falta de memoria non é algo que é fácil

887
01:09:52,590 --> 01:09:56,610
a menos que está a asignación dunha tonelada de cousas e facer unha lista enorme,

888
01:09:56,610 --> 01:10:02,220
pero se está construíndo cousas para, digamos, como un iPhone ou un Android,

889
01:10:02,220 --> 01:10:05,230
ten recursos limitados de memoria, especialmente se está facendo algo intenso.

890
01:10:05,230 --> 01:10:08,300
Polo tanto, é bo para poñerse en práctica.

891
01:10:08,300 --> 01:10:10,510
>> Repare que eu usei algunhas funcións diferentes aquí

892
01:10:10,510 --> 01:10:12,880
que xa viu que son unha especie de novo.

893
01:10:12,880 --> 01:10:15,870
Entón fprintf é como printf

894
01:10:15,870 --> 01:10:21,320
excepto o seu primeiro argumento é o fluxo para o que quere imprimir.

895
01:10:21,320 --> 01:10:23,900
Neste caso, queremos imprimir a cadea de erro estándar

896
01:10:23,900 --> 01:10:29,410
que é distinto do estándar outstream.

897
01:10:29,410 --> 01:10:31,620
Por defecto, el mostra-se no mesmo lugar.

898
01:10:31,620 --> 01:10:34,600
Ela tamén imprime á terminal, pero pode -

899
01:10:34,600 --> 01:10:38,790
usando os comandos que aprendeu sobre as técnicas de redirección,

900
01:10:38,790 --> 01:10:42,290
que aprendeu na video de Tommy por conxunto de problemas 4, pode dirixilas-lo

901
01:10:42,290 --> 01:10:47,900
para diferentes áreas e, despois, saír, aquí, sae do seu programa.

902
01:10:47,900 --> 01:10:50,440
É esencialmente como volver de inicio,

903
01:10:50,440 --> 01:10:53,600
agás que usamos, porque aquí saída de retorno non vai facer nada.

904
01:10:53,600 --> 01:10:57,140
Non estamos no inicio, para retorno non saír do programa como queremos.

905
01:10:57,140 --> 01:11:03,020
Entón, usamos a función de saída e darlle un código de erro.

906
01:11:03,020 --> 01:11:11,890
Entón, aquí imos definir campo novo nodo de valor, o seu campo i igual a i, e entón conecta-lo.

907
01:11:11,890 --> 01:11:15,530
Montar punteiro seguinte, o novo nó para que apunte cara ao primeiro,

908
01:11:15,530 --> 01:11:20,460
e despois na primeira vai agora apuntar para o novo nodo.

909
01:11:20,460 --> 01:11:25,120
Estas primeiras liñas de código, estamos realmente construíndo o novo nodo.

910
01:11:25,120 --> 01:11:27,280
Nin as dúas últimas liñas desta función, pero os primeiros.

911
01:11:27,280 --> 01:11:30,290
Pode realmente saír nunha función, nunha función auxiliar.

912
01:11:30,290 --> 01:11:32,560
Que moitas veces é o que fago é, eu retirala-lo nunha función,

913
01:11:32,560 --> 01:11:36,040
Eu chamo-lle algo como o de construción,

914
01:11:36,040 --> 01:11:40,410
e que mantén a función prepend moi pequena, con só 3 liñas de entón.

915
01:11:40,410 --> 01:11:48,710
Fago unha chamada para o meu función do nó de construción, e entón eu todo fíos para arriba.

916
01:11:48,710 --> 01:11:51,970
>> A última cousa que quero te amosar,

917
01:11:51,970 --> 01:11:54,030
e eu vou deixar facer append e todo o que no seu propio país,

918
01:11:54,030 --> 01:11:57,500
é como iterar sobre unha lista.

919
01:11:57,500 --> 01:12:00,780
Hai unha morea de maneiras diferentes de abordar unha lista.

920
01:12:00,780 --> 01:12:03,140
Neste caso, imos atopar a lonxitude dunha lista.

921
01:12:03,140 --> 01:12:06,570
Entón, imos comezar coa lonxitude = 0.

922
01:12:06,570 --> 01:12:11,580
Isto é moi semellante á escritura strlen para unha cadea.

923
01:12:11,580 --> 01:12:17,780
Iso é o que quero amosar para ti, este lazo for ben aquí.

924
01:12:17,780 --> 01:12:23,530
Parece medio funk, non é o habitual int i = 0, i <calquera que sexa, i + +.

925
01:12:23,530 --> 01:12:34,920
En vez diso, está a iniciar a variable n ser o inicio da lista.

926
01:12:34,920 --> 01:12:40,620
E entón, cando a nosa variable iterator non é nulo, nós continuar.

927
01:12:40,620 --> 01:12:46,340
Isto porque, por convención, o fin da nosa lista será nulo.

928
01:12:46,340 --> 01:12:48,770
E, a continuación, para incrementar, en vez de facer + +,

929
01:12:48,770 --> 01:12:57,010
o equivalente lista ligada de + + é n = n-> seguinte.

930
01:12:57,010 --> 01:13:00,410
>> Eu vou deixar cubrir as lagoas aquí porque estamos fóra do tempo.

931
01:13:00,410 --> 01:13:09,300
Pero manter isto presente como traballar en serie de exercicios seus spellr.

932
01:13:09,300 --> 01:13:11,650
Listas ligadas, se está aplicando unha táboa hash,

933
01:13:11,650 --> 01:13:14,010
vai certamente ser moi útil.

934
01:13:14,010 --> 01:13:21,780
E, tendo esta expresión para looping sobre as cousas van facer a vida moito máis fácil, eu espero.

935
01:13:21,780 --> 01:13:25,910
Calquera dúbida, rapidamente?

936
01:13:25,910 --> 01:13:28,920
[Sam] Será que enviar o SLL completado e sc?

937
01:13:28,920 --> 01:13:38,360
[Hardison] Yeah. Vou enviar láminas concluídas e pila SLL completado e queue.cs.

938
01:13:38,360 --> 01:13:41,360
[CS50.TV]