1
00:00:00,000 --> 00:00:02,730
[Powered by Google Translate] [Seção 6: menos confortável]

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
Tudo bem. Bem-vindo à secção 6.

5
00:00:11,840 --> 00:00:14,690
Esta semana, vamos estar falando sobre estruturas de dados na seção,

6
00:00:14,690 --> 00:00:19,780
principalmente porque o problema desta semana definir em spellr

7
00:00:19,780 --> 00:00:24,410
faz um monte de exploração diferente da estrutura de dados.

8
00:00:24,410 --> 00:00:26,520
Há um monte de maneiras diferentes você pode ir com o conjunto de problemas,

9
00:00:26,520 --> 00:00:31,570
E quanto mais estruturas de dados que você sabe sobre, as coisas mais legais que você pode fazer.

10
00:00:31,570 --> 00:00:34,990
>> Então vamos começar. Primeiro vamos falar sobre pilhas,

11
00:00:34,990 --> 00:00:37,530
dados da pilha e fila estruturas que nós vamos falar sobre.

12
00:00:37,530 --> 00:00:40,560
Pilhas e filas são realmente úteis quando começamos a falar sobre os gráficos,

13
00:00:40,560 --> 00:00:44,390
que nós não vamos fazer tanto de agora.

14
00:00:44,390 --> 00:00:52,820
Mas eles são muito bons para entender um dos grandes estruturas de dados fundamentais do CS.

15
00:00:52,820 --> 00:00:54,880
A descrição na especificação do conjunto de problemas,

16
00:00:54,880 --> 00:00:59,260
Se você puxar-lo, fala sobre pilhas como semelhante a

17
00:00:59,260 --> 00:01:05,239
a pilha de bandejas de refeições que você tem na lanchonete nas salas de jantar

18
00:01:05,239 --> 00:01:09,680
onde quando o jantar a equipe vem e coloca as bandejas de refeições para fora depois que limpa-los,

19
00:01:09,680 --> 00:01:12,000
eles empilhá-los um em cima do outro.

20
00:01:12,000 --> 00:01:15,050
E então, quando as crianças vêm para obter alimentos,

21
00:01:15,050 --> 00:01:19,490
eles puxam as bandejas de fora, primeiro a de cima, então o que está abaixo dela, então a um abaixo disso.

22
00:01:19,490 --> 00:01:25,190
Então, na verdade, a primeira bandeja que o jantar a equipe colocar para baixo é a última que é levado.

23
00:01:25,190 --> 00:01:32,330
O último que o jantar a equipe colocar é o primeiro que é levado para o jantar.

24
00:01:32,330 --> 00:01:38,100
Na especificação do conjunto de problemas, que você pode baixar, se você não tiver,

25
00:01:38,100 --> 00:01:46,730
falamos sobre a modelagem de um stucture dados da pilha usando este tipo de estrutura.

26
00:01:46,730 --> 00:01:51,070
>> Então, o que nós temos aqui, isso é semelhante ao que foi apresentado na aula,

27
00:01:51,070 --> 00:01:58,120
exceto em palestra que apresentou esta com ints ao contrário de char * s.

28
00:01:58,120 --> 00:02:06,250
Esta vai ser uma pilha que armazena o que?

29
00:02:06,250 --> 00:02:09,009
Daniel? O que estamos armazenando nesta pilha?

30
00:02:09,009 --> 00:02:15,260
[Daniel] Cordas? >> Estamos armazenar cadeias nesta pilha, exatamente.

31
00:02:15,260 --> 00:02:20,950
Tudo que você precisa ter para criar uma pilha é um array

32
00:02:20,950 --> 00:02:23,920
de uma capacidade particular, que, neste caso,

33
00:02:23,920 --> 00:02:28,020
capacidade vai ser em todas as tampas, pois é uma constante.

34
00:02:28,020 --> 00:02:36,340
E então, além da matriz, tudo o que precisamos para seguir é o tamanho atual da matriz.

35
00:02:36,340 --> 00:02:38,980
Uma coisa a notar aqui que é legal

36
00:02:38,980 --> 00:02:47,060
é a de que estamos a criar a estrutura de dados empilhada sobre uma outra estrutura, a matriz.

37
00:02:47,060 --> 00:02:50,110
Há diferentes maneiras de implementar pilhas.

38
00:02:50,110 --> 00:02:54,250
Nós não vamos fazer isso bastante ainda, mas espero que depois de fazer os problemas de lista vinculada,

39
00:02:54,250 --> 00:03:00,520
você vai ver como você pode facilmente implementar uma pilha em cima de uma lista ligada também.

40
00:03:00,520 --> 00:03:02,640
Mas, por enquanto, vamos ficar com as matrizes.

41
00:03:02,640 --> 00:03:06,350
Então, novamente, tudo o que precisamos é um array e só precisamos de controlar o tamanho da matriz.

42
00:03:06,350 --> 00:03:09,850
[Sam] Desculpe, por que é que você disse a pilha está no topo das cordas?

43
00:03:09,850 --> 00:03:13,440
Para mim parece que as cordas estão dentro da pilha.

44
00:03:13,440 --> 00:03:16,790
[Hardison] Yeah. Estamos criando, nós estamos levando a nossa matriz de estrutura de dados -

45
00:03:16,790 --> 00:03:22,130
essa é uma grande questão. Então a questão é por isso que, para as pessoas que estão assistindo esta linha,

46
00:03:22,130 --> 00:03:24,140
por que estamos dizendo que a pilha está em cima das cordas,

47
00:03:24,140 --> 00:03:27,990
porque aqui parece que as cordas estão dentro da pilha?

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 estava referindo-se a era que nós temos uma estrutura de dados matriz.

50
00:03:34,660 --> 00:03:39,290
Nós temos uma matriz de char * s, este arranjo de cordas,

51
00:03:39,290 --> 00:03:45,300
e vamos acrescentar a isto, a fim de criar a estrutura de dados empilhados.

52
00:03:45,300 --> 00:03:48,620
>> Assim, uma pilha é um pouco mais complexo do que um array.

53
00:03:48,620 --> 00:03:51,890
Podemos usar uma matriz para construir uma pilha.

54
00:03:51,890 --> 00:03:55,810
Então é aí que nós dizemos que a pilha é construída em cima de uma matriz.

55
00:03:55,810 --> 00:04:02,510
Da mesma forma, como eu disse anteriormente, podemos construir uma pilha em cima de uma lista ligada.

56
00:04:02,510 --> 00:04:04,960
Em vez de usar uma matriz para armazenar os nossos elementos,

57
00:04:04,960 --> 00:04:10,070
poderíamos usar uma lista ligada para manter nossos elementos e construir a pilha em torno disso.

58
00:04:10,070 --> 00:04:12,420
Vamos caminhar através de um par de exemplos, olhando para algum código,

59
00:04:12,420 --> 00:04:14,960
para ver o que está realmente acontecendo aqui.

60
00:04:14,960 --> 00:04:23,400
Na esquerda, eu tenho jogado para baixo o que struct pilha ficaria na memória

61
00:04:23,400 --> 00:04:28,330
se a capacidade de se # definido como sendo quatro.

62
00:04:28,330 --> 00:04:33,490
Nós temos nossos quatro elemento do array char *.

63
00:04:33,490 --> 00:04:38,110
Temos strings [0], strings [1], strings [2], strings [3],

64
00:04:38,110 --> 00:04:43,800
e, em seguida, que o espaço para o nosso passado inteiro tamanho.

65
00:04:43,800 --> 00:04:46,270
Será que isto faz sentido? Okay.

66
00:04:46,270 --> 00:04:48,790
Isto é o que acontece se o que eu faço à direita,

67
00:04:48,790 --> 00:04:55,790
qual será o meu código, é apenas para declarar uma estrutura, uma estrutura chamada empilhados s.

68
00:04:55,790 --> 00:05:01,270
Isto é o que temos. Estabelece esta pegada na memória.

69
00:05:01,270 --> 00:05:05,590
A primeira pergunta aqui é o que são os conteúdos desta struct pilha?

70
00:05:05,590 --> 00:05:09,250
Agora eles não é nada, mas eles não são absolutamente nada.

71
00:05:09,250 --> 00:05:13,300
São este tipo de lixo. Nós não temos idéia do que está neles.

72
00:05:13,300 --> 00:05:17,000
Quando declaramos s pilha, estamos apenas jogando que em cima da memória.

73
00:05:17,000 --> 00:05:19,840
É uma espécie de como declarar int i e não inicializa-la.

74
00:05:19,840 --> 00:05:21,730
Você não sabe o que está lá. Você pode ler o que está lá,

75
00:05:21,730 --> 00:05:27,690
mas não pode ser super útil.

76
00:05:27,690 --> 00:05:32,680
Uma coisa que você quer sempre se lembrar de fazer é inicializar o que precisa ser inicializado.

77
00:05:32,680 --> 00:05:35,820
Neste caso, nós estamos indo para inicializar o tamanho para ser zero,

78
00:05:35,820 --> 00:05:39,960
porque que vai passar a ser muito importante para nós.

79
00:05:39,960 --> 00:05:43,450
Nós poderíamos ir em frente e inicializar todos os ponteiros, todos os s * char,

80
00:05:43,450 --> 00:05:49,670
ser algum valor compreensível, provavelmente nulo.

81
00:05:49,670 --> 00:05:58,270
Mas não é totalmente necessário que façamos isso.

82
00:05:58,270 --> 00:06:04,200
>> Agora, as duas principais operações sobre pilhas são?

83
00:06:04,200 --> 00:06:07,610
Alguém se lembra da palestra que você faz com pilhas? Sim?

84
00:06:07,610 --> 00:06:09,700
[Stella] Empurrando e popping? >> Exatamente.

85
00:06:09,700 --> 00:06:13,810
Empurrando e popping são as duas principais operações sobre pilhas.

86
00:06:13,810 --> 00:06:17,060
E o que fazer pressão? >> Ele coloca algo para o topo

87
00:06:17,060 --> 00:06:19,300
da pilha, e depois leva-lo de estalo.

88
00:06:19,300 --> 00:06:23,150
[Hardison] Exatamente. Então, empurrando empurra algo no topo da pilha.

89
00:06:23,150 --> 00:06:27,700
É como o jantar a equipe colocando uma bandeja de jantar no balcão.

90
00:06:27,700 --> 00:06:33,630
E popping está levando uma bandeja de jantar ao lado da pilha.

91
00:06:33,630 --> 00:06:36,460
Vamos examinar alguns exemplos do que acontece

92
00:06:36,460 --> 00:06:39,720
quando empurrar as coisas para a pilha.

93
00:06:39,720 --> 00:06:45,110
Se fôssemos para empurrar a string 'Olá' para o nosso pilha,

94
00:06:45,110 --> 00:06:49,760
este é o nosso diagrama será parecido agora.

95
00:06:49,760 --> 00:06:53,410
Veja o que acontece?

96
00:06:53,410 --> 00:06:56,530
Nós empurrado para dentro do primeiro elemento de nossa matriz cordas

97
00:06:56,530 --> 00:07:01,420
e elevou a contagem de tamanho para ser 1.

98
00:07:01,420 --> 00:07:05,340
Então, se olharmos para a diferença entre os dois slides, aqui foi de 0, aqui está antes do empurrão.

99
00:07:05,340 --> 00:07:08,690
Aqui é depois do empurrão.

100
00:07:08,690 --> 00:07:13,460
Antes do envio, após a pressão.

101
00:07:13,460 --> 00:07:16,860
E agora temos um elemento em nossa pilha.

102
00:07:16,860 --> 00:07:20,970
É a string "Olá", e é isso.

103
00:07:20,970 --> 00:07:24,440
Tudo o resto na matriz, em nossa matriz cordas, ainda é lixo.

104
00:07:24,440 --> 00:07:27,070
Nós não inicializado ele.

105
00:07:27,070 --> 00:07:29,410
Vamos dizer que empurrar uma outra corda para o nosso pilha.

106
00:07:29,410 --> 00:07:32,210
Nós vamos empurrar "mundo" neste momento.

107
00:07:32,210 --> 00:07:35,160
Assim você pode ver "mundo" aqui vai em cima do "Olá",

108
00:07:35,160 --> 00:07:40,040
e a contagem de tamanho vai até 2.

109
00:07:40,040 --> 00:07:44,520
Agora podemos empurrar "CS50", e que vai em cima novamente.

110
00:07:44,520 --> 00:07:51,110
Se voltar, você pode ver como estamos empurrando as coisas em cima da pilha.

111
00:07:51,110 --> 00:07:53,320
E agora temos a pop.

112
00:07:53,320 --> 00:07:58,910
Quando apareceu alguma coisa fora da pilha, o que aconteceu?

113
00:07:58,910 --> 00:08:01,540
Alguém viu a diferença? É muito sutil.

114
00:08:01,540 --> 00:08:05,810
[Aluno] O tamanho. >> Sim, o tamanho alterado.

115
00:08:05,810 --> 00:08:09,040
>> O que mais você esperar para mudar?

116
00:08:09,040 --> 00:08:14,280
[Aluno] As cordas, também. >> Direito. As cordas também.

117
00:08:14,280 --> 00:08:17,110
Acontece que quando você está fazendo desta forma,

118
00:08:17,110 --> 00:08:21,960
porque não estamos copiando os elementos em nossa pilha,

119
00:08:21,960 --> 00:08:24,670
nós realmente não tem que fazer nada, podemos usar apenas o tamanho

120
00:08:24,670 --> 00:08:28,630
para manter o controle do número de coisas em nossa matriz

121
00:08:28,630 --> 00:08:33,780
para que, quando aparecer de novo, mais uma vez, apenas diminuir nosso tamanho para 1.

122
00:08:33,780 --> 00:08:39,440
Não há necessidade de realmente entrar e substituir nada.

123
00:08:39,440 --> 00:08:41,710
Tipo de funky.

124
00:08:41,710 --> 00:08:46,520
Acontece que nós normalmente simplesmente deixar as coisas sozinho, porque é menos trabalho para nós.

125
00:08:46,520 --> 00:08:50,060
Se nós não temos que voltar e substituir alguma coisa, então por que fazer isso?

126
00:08:50,060 --> 00:08:54,150
Assim, quando aparecer duas vezes fora da pilha, é tudo o que faz diminuir o tamanho de um par de vezes.

127
00:08:54,150 --> 00:08:59,120
E mais uma vez, este é apenas porque não estamos copiando as coisas em nossa pilha.

128
00:08:59,120 --> 00:09:01,320
Sim? Vá em frente.

129
00:09:01,320 --> 00:09:04,460
[Estudante, ininteligível] >> E então o que acontece quando você empurrar algo novo?

130
00:09:04,460 --> 00:09:08,570
Quando você empurrar algo de novo, para onde vai?

131
00:09:08,570 --> 00:09:12,390
Para onde ela vai, Basil? >> Em cordas [1]? >> Direito.

132
00:09:12,390 --> 00:09:14,530
Por que não ir para strings [3]?

133
00:09:14,530 --> 00:09:19,410
[Basil] Porque se esqueceu de que não havia nada em cordas [1] e [2]?

134
00:09:19,410 --> 00:09:24,040
[Hardison] Exatamente. Nossa pilha, essencialmente, "esqueceu" que estava segurando em nada

135
00:09:24,040 --> 00:09:29,480
em cordas [1] ou cordas [2], portanto, quando empurrar "woot",

136
00:09:29,480 --> 00:09:36,670
ele simplesmente coloca que para o elemento em cordas [1].

137
00:09:36,670 --> 00:09:41,590
Há dúvidas sobre como isso funciona, em um nível básico?

138
00:09:41,590 --> 00:09:45,160
[Sam] Assim, este não é dinâmica, de qualquer maneira, em termos de quantidade

139
00:09:45,160 --> 00:09:47,620
ou em termos do tamanho da pilha?

140
00:09:47,620 --> 00:09:56,750
[Hardison] Exatamente. Isto é - o ponto era que esta não era uma pilha dinamicamente growning.

141
00:09:56,750 --> 00:10:02,850
Trata-se de uma pilha que pode conter, no máximo, quatro char * s, no máximo quatro coisas.

142
00:10:02,850 --> 00:10:07,580
Se fôssemos tentar empurrar uma coisa quinto, o que você acha que deve acontecer?

143
00:10:07,580 --> 00:10:11,870
[Estudantes, ininteligível]

144
00:10:11,870 --> 00:10:14,600
[Hardison] Exatamente. Há uma série de coisas que podem acontecer.

145
00:10:14,600 --> 00:10:19,330
Ele poderia seg falha, dependendo do que nós -

146
00:10:19,330 --> 00:10:22,530
exatamente como nós estavam a implementar o back-end.

147
00:10:22,530 --> 00:10:31,740
Ele poderia substituir. Ele poderia ter esse estouro de buffer que falamos em sala de aula.

148
00:10:31,740 --> 00:10:35,240
Qual seria a coisa mais óbvia que pode ser substituído

149
00:10:35,240 --> 00:10:42,370
se tentou empurrar uma coisa extra em nosso pilha?

150
00:10:42,370 --> 00:10:44,550
Então você mencionou um estouro de buffer.

151
00:10:44,550 --> 00:10:47,870
O que pode ser a única coisa que se escreveu mais ou pisou

152
00:10:47,870 --> 00:10:52,320
se transbordou acidentalmente por tentar empurrar uma coisa extra?

153
00:10:52,320 --> 00:10:54,730
[Daniel, ininteligível] Possível. >>

154
00:10:54,730 --> 00:10:58,440
Mas, inicialmente, o que pode acontecer? O que se tentou empurrar uma quarta coisa?

155
00:10:58,440 --> 00:11:06,220
Ele pode substituir o tamanho, pelo menos com este diagrama de memória que temos.

156
00:11:06,220 --> 00:11:10,880
>> Na especificação conjunto de problemas, que é o que nós vamos estar implementando hoje,

157
00:11:10,880 --> 00:11:16,030
o que nós queremos fazer é retornar falso.

158
00:11:16,030 --> 00:11:20,030
Nosso método push vai retornar um valor booleano,

159
00:11:20,030 --> 00:11:22,920
e esse valor booleano será verdade se o impulso sucesso

160
00:11:22,920 --> 00:11:29,730
e falso se não podemos empurrar mais nada, porque a pilha está cheia.

161
00:11:29,730 --> 00:11:33,620
Vamos examinar um pouco de que o código agora.

162
00:11:33,620 --> 00:11:36,400
Aqui é a nossa função push.

163
00:11:36,400 --> 00:11:40,380
Nossa função push para uma pilha vai ter na cadeia para colocar na pilha.

164
00:11:40,380 --> 00:11:45,820
Vai retornar verdadeiro se a string foi empurrado com sucesso

165
00:11:45,820 --> 00:11:51,820
na outra pilha e falso.

166
00:11:51,820 --> 00:11:59,740
Todas as sugestões sobre o que pode ser uma coisa boa primeiro a fazer aqui?

167
00:11:59,740 --> 00:12:20,630
[Sam] Se tamanho é igual capacidade em seguida, retornar falso?

168
00:12:20,630 --> 00:12:23,320
[Hardison] Bingo. Bom trabalho.

169
00:12:23,320 --> 00:12:26,310
Se o tamanho é a capacidade, vamos retornar falso.

170
00:12:26,310 --> 00:12:29,270
Não podemos colocar algo mais em nossa pilha.

171
00:12:29,270 --> 00:12:36,900
Caso contrário, nós queremos colocar algo no topo da pilha.

172
00:12:36,900 --> 00:12:41,670
O que é o "topo da pilha", inicialmente?

173
00:12:41,670 --> 00:12:43,650
[Daniel] Tamanho 0? Tamanho >> 0.

174
00:12:43,650 --> 00:12:49,990
O que é o topo da pilha depois há uma coisa na pilha? Missy, você sabe?

175
00:12:49,990 --> 00:12:52,720
[Missy] um. Tamanho >> é uma, exatamente. Você continuar a acrescentar ao tamanho,

176
00:12:52,720 --> 00:13:01,690
e cada vez que você está colocando no novo elemento no tamanho do índice na matriz.

177
00:13:01,690 --> 00:13:05,470
Nós podemos fazê-lo com esse tipo de one-liner, se isso faz sentido.

178
00:13:05,470 --> 00:13:11,910
Então, nós temos nossa matriz cordas, vamos para acessá-lo no índice tamanho,

179
00:13:11,910 --> 00:13:14,780
e nós apenas estamos indo para guardar nosso char * lá.

180
00:13:14,780 --> 00:13:19,340
Observe como não há como cópia cadeia acontecendo aqui,

181
00:13:19,340 --> 00:13:29,680
não alocação dinâmica de memória?

182
00:13:29,680 --> 00:13:34,440
E então Missy trouxe o que temos agora de fazer,

183
00:13:34,440 --> 00:13:40,570
porque nós temos guardado a cadeia no lugar apropriado na matriz,

184
00:13:40,570 --> 00:13:49,230
e ela disse que tínhamos que aumentar o tamanho de um modo que nós estamos prontos para o impulso seguinte.

185
00:13:49,230 --> 00:13:53,950
Assim, podemos fazer isso com s.size + +.

186
00:13:53,950 --> 00:13:59,330
Neste ponto, nós empurrado para a nossa matriz. Qual é a última coisa que temos que fazer?

187
00:13:59,330 --> 00:14:10,110
[Estudante] retornar true. Retornar >> verdade.

188
00:14:10,110 --> 00:14:14,690
Então é muito simples, um código muito simples. Não muito.

189
00:14:14,690 --> 00:14:17,070
Uma vez que você envolveu sua cabeça em torno de como a pilha funciona,

190
00:14:17,070 --> 00:14:21,910
isso é muito simples de implementar.

191
00:14:21,910 --> 00:14:26,390
>> Agora, a próxima parte deste está surgindo uma corda fora da pilha.

192
00:14:26,390 --> 00:14:29,410
Eu vou dar a vocês algum tempo para trabalhar nisso um pouco.

193
00:14:29,410 --> 00:14:34,320
É quase essencialmente o contrário do que nós fizemos aqui no empurrão.

194
00:14:34,320 --> 00:14:38,510
O que eu tenho feito é, na verdade - oops.

195
00:14:38,510 --> 00:14:48,160
Eu tenha iniciado um aparelho aqui, e no aparelho,

196
00:14:48,160 --> 00:14:53,600
Eu puxei o conjunto de problemas 5 especificação.

197
00:14:53,600 --> 00:15:02,560
Se zoom aqui, podemos ver que eu estou em cdn.cs50.net/2012/fall/psets/pset5.pdf.

198
00:15:02,560 --> 00:15:08,590
Vocês já baixou este código que está localizado aqui, section6.zip?

199
00:15:08,590 --> 00:15:15,030
Tudo bem. Se você não tiver feito isso, faça isso agora, muito rapidamente.

200
00:15:15,030 --> 00:15:22,130
Eu vou fazer isso na minha janela de terminal.

201
00:15:22,130 --> 00:15:25,090
Na verdade, eu fiz isso aqui em cima. Sim.

202
00:15:25,090 --> 00:15:34,730
Sim, Sam? >> Eu tenho uma pergunta sobre por que você disse s.string 's faixas de tamanho = str?

203
00:15:34,730 --> 00:15:42,910
O que é str? É o definido em algum lugar antes, ou - oh, no str char *?

204
00:15:42,910 --> 00:15:47,160
[Hardison] Sim, exatamente. Esse foi o argumento. >> Ah, ok. Desculpe.

205
00:15:47,160 --> 00:15:49,470
[Hardison] Nós estamos especificando a corda para empurrar dentro

206
00:15:49,470 --> 00:15:55,220
A outra questão que possa surgir que nós realmente não falar aqui era

207
00:15:55,220 --> 00:15:58,810
tomamos por certo que tivemos esta variável chamada s

208
00:15:58,810 --> 00:16:02,710
que estava no escopo e acessível para nós.

209
00:16:02,710 --> 00:16:06,960
Tomamos por certo que s foi esta struct pilha.

210
00:16:06,960 --> 00:16:08,930
Então, olhando para trás, este código push,

211
00:16:08,930 --> 00:16:13,450
você pode ver que nós estamos fazendo coisas com esta corda que foi aprovada em

212
00:16:13,450 --> 00:16:19,210
mas então, de repente, estamos acessando s.size, como, de onde s vem?

213
00:16:19,210 --> 00:16:23,020
No código que vamos olhar no arquivo seção

214
00:16:23,020 --> 00:16:27,100
e, em seguida, o material que você estará fazendo em seu problema se põe,

215
00:16:27,100 --> 00:16:32,440
fizemos nossa pilha struct uma variável global

216
00:16:32,440 --> 00:16:36,380
para que possamos ter acesso a ele em todas as nossas funções diferentes

217
00:16:36,380 --> 00:16:40,630
sem ter que manualmente passar ao redor e passá-lo por referência,

218
00:16:40,630 --> 00:16:44,870
fazer todo o tipo de coisa a ele.

219
00:16:44,870 --> 00:16:52,280
Estamos apenas enganando um pouco, se quiser, para fazer as coisas melhor.

220
00:16:52,280 --> 00:16:57,430
E isso é algo que estamos fazendo aqui, porque isso é para se divertir, é mais fácil.

221
00:16:57,430 --> 00:17:02,800
Muitas vezes, você vai ver as pessoas fazem isso, se eles têm uma grande estrutura de dados

222
00:17:02,800 --> 00:17:07,750
que está sendo operado dentro de seu programa.

223
00:17:07,750 --> 00:17:09,560
>> Vamos voltar para o aparelho.

224
00:17:09,560 --> 00:17:15,240
Será que todo mundo com sucesso obter o section6.zip?

225
00:17:15,240 --> 00:17:20,440
Todo mundo descompactá-lo usando section6.zip unzip?

226
00:17:20,440 --> 00:17:27,200
Se você vai para o diretório seção 6 -

227
00:17:27,200 --> 00:17:29,220
aah, em todo o lugar -

228
00:17:29,220 --> 00:17:32,840
e você listar o que tem aqui, você vê que você tem três diferentes arquivos. c.

229
00:17:32,840 --> 00:17:38,350
Você tem uma fila, um sll, que, isoladamente, é ligada lista, e uma pilha.

230
00:17:38,350 --> 00:17:44,600
Se você abrir stack.c,

231
00:17:44,600 --> 00:17:47,330
você pode ver que nós temos essa estrutura definida para nós,

232
00:17:47,330 --> 00:17:51,330
a estrutura exata que nós acabamos de falar nos slides.

233
00:17:51,330 --> 00:17:56,340
Temos a nossa variável global para a pilha,

234
00:17:56,340 --> 00:18:00,110
nós temos nossa função push,

235
00:18:00,110 --> 00:18:04,230
e depois temos a nossa função pop.

236
00:18:04,230 --> 00:18:08,320
Eu vou colocar o código para empurrar de volta no slide aqui,

237
00:18:08,320 --> 00:18:10,660
mas o que eu gostaria que vocês a fazer é, com o melhor de sua capacidade,

238
00:18:10,660 --> 00:18:13,790
ir e implementar a função pop.

239
00:18:13,790 --> 00:18:18,480
Depois de implementar, você pode compilar este com o make de pilha,

240
00:18:18,480 --> 00:18:22,540
e, em seguida, executar o arquivo executável pilha resultante,

241
00:18:22,540 --> 00:18:28,390
e que irá executar todo esse código de teste aqui em baixo que está na principal.

242
00:18:28,390 --> 00:18:31,060
E principal cuida de realmente fazer o push e pop chamadas

243
00:18:31,060 --> 00:18:33,220
e certificando-se que tudo passa bem.

244
00:18:33,220 --> 00:18:36,820
Também se inicializa o tamanho da pilha aqui

245
00:18:36,820 --> 00:18:39,780
assim você não precisa se preocupar com a inicialização isso.

246
00:18:39,780 --> 00:18:42,310
Você pode assumir que ele foi inicializado corretamente

247
00:18:42,310 --> 00:18:48,000
pelo tempo que você acessá-lo na função de pop.

248
00:18:48,000 --> 00:18:53,530
Isso faz sentido?

249
00:18:53,530 --> 00:19:00,100
Então, vamos lá. Há o código empurrão.

250
00:19:00,100 --> 00:19:13,210
Eu vou dar a vocês 5 ou 10 minutos.

251
00:19:13,210 --> 00:19:15,690
E se você tiver alguma dúvida no ínterim, enquanto você está de codificação,

252
00:19:15,690 --> 00:19:17,710
pergunte-lhe em voz alta.

253
00:19:17,710 --> 00:19:23,080
Então, se você chegar a um ponto de discórdia, é só pedir.

254
00:19:23,080 --> 00:19:26,030
Deixe-me saber, deixe todo mundo sabe.

255
00:19:26,030 --> 00:19:28,160
Trabalhe com seu vizinho também.

256
00:19:28,160 --> 00:19:30,360
[Daniel] Estamos apenas implementando pop agora? Apenas >> pop.

257
00:19:30,360 --> 00:19:34,200
Embora você pode copiar a implementação de impulso se quiser

258
00:19:34,200 --> 00:19:37,780
de modo que o teste irá funcionar.

259
00:19:37,780 --> 00:19:41,940
Porque é difícil para testar as coisas ficando em -

260
00:19:41,940 --> 00:19:49,030
ou, é difícil testar as coisas pulando para fora de uma pilha se não houver nada na pilha para começar.

261
00:19:49,030 --> 00:19:55,250
>> O que é pop suposto estar voltando? O elemento a partir do topo da pilha.

262
00:19:55,250 --> 00:20:01,260
É suposto obter o elemento para fora da parte superior da pilha

263
00:20:01,260 --> 00:20:05,780
e, em seguida, diminuir o tamanho da pilha,

264
00:20:05,780 --> 00:20:07,810
e agora você perdeu o elemento no topo.

265
00:20:07,810 --> 00:20:11,420
E então você retornar o elemento no topo.

266
00:20:11,420 --> 00:20:20,080
[Estudante, ininteligível]

267
00:20:20,080 --> 00:20:28,810
[Hardison] Então, o que acontece se você faz isso? [Estudante, ininteligível]

268
00:20:28,810 --> 00:20:34,000
O que acaba acontecendo é que você provavelmente está acessando ou

269
00:20:34,000 --> 00:20:37,350
um elemento que não foi inicializado ainda, para que o seu cálculo

270
00:20:37,350 --> 00:20:39,990
de onde o último elemento é desligado.

271
00:20:39,990 --> 00:20:46,260
Então, aqui, se você observar, no impulso, estamos acessando cordas no elemento s.size

272
00:20:46,260 --> 00:20:48,560
porque é um novo índice.

273
00:20:48,560 --> 00:20:51,460
É o novo topo da pilha.

274
00:20:51,460 --> 00:21:01,100
Considerando que, pop, s.size vai ser o próximo espaço,

275
00:21:01,100 --> 00:21:05,210
o espaço que está no topo de todos os elementos em seu stack.

276
00:21:05,210 --> 00:21:10,050
Assim, o elemento de nível mais alto não é s.size,

277
00:21:10,050 --> 00:21:14,930
mas sim, é por baixo.

278
00:21:14,930 --> 00:21:19,640
>> A outra coisa a fazer quando você - em pop,

279
00:21:19,640 --> 00:21:22,030
é que você tem que diminuir o tamanho.

280
00:21:22,030 --> 00:21:28,750
Se você se lembrar de volta ao nosso pequeno diagrama aqui,

281
00:21:28,750 --> 00:21:30,980
realmente, a única coisa que vimos acontecer quando chamado pop

282
00:21:30,980 --> 00:21:36,150
era que este tamanho descartado, primeiro a 2, então a 1.

283
00:21:36,150 --> 00:21:42,620
Então, quando empurrou um novo elemento ligado, ele iria para o local adequado.

284
00:21:42,620 --> 00:21:49,610
[Basil] Se o s.size é 2, então ele não iria passar para o elemento 2,

285
00:21:49,610 --> 00:21:54,400
e depois que você gostaria de aparecer esse elemento fora?

286
00:21:54,400 --> 00:21:59,510
Então, se nós fomos para - >> Então, vamos olhar para isso de novo.

287
00:21:59,510 --> 00:22:07,730
Se esta for a pilha neste ponto

288
00:22:07,730 --> 00:22:12,130
e chamamos pop,

289
00:22:12,130 --> 00:22:16,150
em que o índice é o elemento mais alto?

290
00:22:16,150 --> 00:22:19,300
[Basil] No 2, mas vai aparecer 3. >> Direito.

291
00:22:19,300 --> 00:22:24,220
Então é aí que nosso tamanho é 3, mas queremos colocar o elemento no índice 2.

292
00:22:24,220 --> 00:22:29,900
É esse tipo típico de fora por um que você tem com o zero-indexação de matrizes.

293
00:22:29,900 --> 00:22:36,430
Então, você quer aparecer o terceiro elemento, mas o terceiro elemento não está no índice 3.

294
00:22:36,430 --> 00:22:39,430
E a razão pela qual não tem que fazer isso uma menos quando estamos empurrando

295
00:22:39,430 --> 00:22:44,120
é porque agora, você percebe que o elemento mais alto,

296
00:22:44,120 --> 00:22:47,600
se fôssemos para empurrar outra coisa para a pilha, neste ponto,

297
00:22:47,600 --> 00:22:50,360
que gostaria de empurrá-lo no índice 3.

298
00:22:50,360 --> 00:23:03,550
E isso só acontece se o tamanho e os índices alinhar quando você está empurrando.

299
00:23:03,550 --> 00:23:06,960
>> Quem tem uma implementação da pilha de trabalho?

300
00:23:06,960 --> 00:23:09,690
Você tem uma pilha de trabalhar um. Você tem pop funcionando ainda?

301
00:23:09,690 --> 00:23:11,890
[Daniel] Sim. Acho que sim.

302
00:23:11,890 --> 00:23:14,610
Programa >> está funcionando e não seg falhamento, está imprimindo?

303
00:23:14,610 --> 00:23:17,520
Será que imprimir "sucesso" quando você o executa?

304
00:23:17,520 --> 00:23:22,630
Sim. Faça empilhar, executá-lo, se ele imprime "sucesso" e não vai boom,

305
00:23:22,630 --> 00:23:26,000
então tudo é bom.

306
00:23:26,000 --> 00:23:34,070
Tudo bem. Vamos passar para o aparelho muito rapidamente,

307
00:23:34,070 --> 00:23:46,100
e nós vamos caminhar por este.

308
00:23:46,100 --> 00:23:51,110
Se olharmos para o que está acontecendo aqui com pop,

309
00:23:51,110 --> 00:23:55,220
Daniel, que foi a primeira coisa que você fez?

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 você fez isso?

312
00:24:03,120 --> 00:24:05,610
[Daniel] Para se certificar de que havia algo dentro da pilha.

313
00:24:05,610 --> 00:24:10,950
[Hardison] Direito. Você deseja testar para ter certeza de que s.size é maior que 0;

314
00:24:10,950 --> 00:24:13,280
de outra forma, o que você quer que aconteça?

315
00:24:13,280 --> 00:24:16,630
[Daniel] return null? >> Return null, exatamente.

316
00:24:16,630 --> 00:24:20,740
Portanto, se s.size é maior que 0. Então, o que vamos fazer?

317
00:24:20,740 --> 00:24:25,890
O que vamos fazer se a pilha não está vazio?

318
00:24:25,890 --> 00:24:31,210
[Stella] Você diminuir o tamanho? >> Você diminuir o tamanho, tudo bem.

319
00:24:31,210 --> 00:24:34,440
Então, como você fez isso? >> S.size--.

320
00:24:34,440 --> 00:24:37,030
[Hardison] Grande. E então, o que você fez?

321
00:24:37,030 --> 00:24:44,140
[Stella] E então eu disse 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
Caso contrário, você retornar nulo. Sim, Sam?

324
00:24:51,940 --> 00:24:55,510
[Sam] Por que não precisa ser s.size + 1?

325
00:24:55,510 --> 00:24:58,430
[Hardison] Plus 1? Sim >>. >> Entendi.

326
00:24:58,430 --> 00:25:00,980
[Sam] Eu pensei, porque você está levando um fora,

327
00:25:00,980 --> 00:25:04,290
então você está indo estar voltando não o que eles pediram.

328
00:25:04,290 --> 00:25:09,400
[Hardison] E isso foi exatamente o que estavam falando com toda esta questão de 0 índices.

329
00:25:09,400 --> 00:25:11,380
Então, se o zoom aqui.

330
00:25:11,380 --> 00:25:15,650
Se olharmos para esse cara aqui, você pode ver que, quando aparecer,

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ão, nós diminuímos nosso tamanho primeiro, depois o nosso tamanho corresponde ao nosso índice.

333
00:25:25,200 --> 00:25:39,650
Se não diminuir o tamanho do primeiro, então temos que fazer o tamanho -1 e decremento.

334
00:25:39,650 --> 00:25:45,270
Grande. Tudo bem?

335
00:25:45,270 --> 00:25:47,530
Qualquer dúvida sobre isso?

336
00:25:47,530 --> 00:25:54,050
Há uma série de maneiras diferentes para escrever isso também.

337
00:25:54,050 --> 00:26:03,290
Na verdade, podemos fazer algo ainda - nós podemos fazer um one-liner.

338
00:26:03,290 --> 00:26:05,770
Nós podemos fazer um retorno de uma linha.

339
00:26:05,770 --> 00:26:12,980
Assim, podemos realmente diminuir antes de retornar ao fazer isso.

340
00:26:12,980 --> 00:26:18,320
Então, colocar o - antes do s.size.

341
00:26:18,320 --> 00:26:22,060
Isso faz com que a linha realmente denso.

342
00:26:22,060 --> 00:26:30,940
Se a diferença entre o - s e tamanho. S.size -

343
00:26:30,940 --> 00:26:40,130
é que este postfix - que eles chamam de postfix, porque o - vem depois do s.size -

344
00:26:40,130 --> 00:26:47,430
significa que s.size é avaliada para efeitos de encontrar o índice

345
00:26:47,430 --> 00:26:50,410
como é atualmente, quando esta linha é executada,

346
00:26:50,410 --> 00:26:54,290
e depois isso - acontece após a linha é executada.

347
00:26:54,290 --> 00:27:00,340
Após o elemento em s.size índice é acessado.

348
00:27:00,340 --> 00:27:07,260
E isso não é o que queremos, porque queremos que o decremento acontecer primeiro.

349
00:27:07,260 --> 00:27:10,990
Othewise, vamos estar acessando a matriz, efetivamente, fora dos limites.

350
00:27:10,990 --> 00:27:16,850
Nós vamos estar acessando o elemento acima do que realmente deseja acessar.

351
00:27:16,850 --> 00:27:23,840
Sim, Sam? >> É mais rápido ou usar menos memória RAM para fazer em uma linha ou não?

352
00:27:23,840 --> 00:27:29,620
[Hardison] Honestamente, isso realmente depende.

353
00:27:29,620 --> 00:27:34,220
[Sam, ininteligível] >> Sim, depende. Você pode fazer truques compilador

354
00:27:34,220 --> 00:27:41,580
para obter o compilador para reconhecer que, geralmente, eu imagino.

355
00:27:41,580 --> 00:27:44,840
>> Então, nós mencionamos um pouco sobre essas coisas otimização do compilador

356
00:27:44,840 --> 00:27:47,400
que você pode fazer na compilação,

357
00:27:47,400 --> 00:27:50,580
e esse é o tipo de coisa que um compilador pode ser capaz de descobrir,

358
00:27:50,580 --> 00:27:54,710
como oh, hey, talvez eu possa fazer tudo isso em uma única operação,

359
00:27:54,710 --> 00:27:59,420
ao contrário de carregar a variável em tamanho a partir da RAM,

360
00:27:59,420 --> 00:28:03,770
decrementando-lo, guardá-lo de volta para fora, e depois colocá-lo de volta novamente

361
00:28:03,770 --> 00:28:08,000
para processar o resto da operação.

362
00:28:08,000 --> 00:28:10,710
Mas, normalmente, não, este não é o tipo de coisa

363
00:28:10,710 --> 00:28:20,770
que vai fazer o seu programa significativamente mais rápido.

364
00:28:20,770 --> 00:28:26,000
Mais alguma pergunta sobre pilhas?

365
00:28:26,000 --> 00:28:31,360
>> Então, empurrando e popping. Se vocês querem experimentar a edição de hacker,

366
00:28:31,360 --> 00:28:33,660
o que temos feito na edição de hacker é realmente ido

367
00:28:33,660 --> 00:28:37,670
e fez esta pilha crescer dinamicamente.

368
00:28:37,670 --> 00:28:43,190
O desafio não é principalmente aqui na função push,

369
00:28:43,190 --> 00:28:48,820
para descobrir como fazer essa matriz crescer

370
00:28:48,820 --> 00:28:52,450
como você continuar pressionando mais e mais elementos sobre a pilha.

371
00:28:52,450 --> 00:28:56,000
Não é realmente muito código adicional.

372
00:28:56,000 --> 00:29:00,080
Apenas uma chamada para - você tem de se lembrar de obter as chamadas para malloc lá corretamente,

373
00:29:00,080 --> 00:29:03,310
e depois descobrir quando você está indo para chamar realloc.

374
00:29:03,310 --> 00:29:06,090
Isso é um desafio divertido se você estiver interessado.

375
00:29:06,090 --> 00:29:11,550
>> Mas, por enquanto, vamos seguir em frente, e vamos falar sobre as filas.

376
00:29:11,550 --> 00:29:15,680
Rolar por aqui.

377
00:29:15,680 --> 00:29:19,340
A fila é um irmão perto da pilha.

378
00:29:19,340 --> 00:29:25,380
Então, na pilha, as coisas que foram colocadas em último

379
00:29:25,380 --> 00:29:28,810
foram as primeiras coisas a ser recuperados.

380
00:29:28,810 --> 00:29:33,600
Temos este último a entrar, primeiro fora, ou LIFO, ordenando.

381
00:29:33,600 --> 00:29:38,390
Considerando que, em fila, como seria de esperar a partir de quando você está em pé na fila,

382
00:29:38,390 --> 00:29:41,980
a primeira pessoa a entrar na fila, a primeira coisa a entrar na fila,

383
00:29:41,980 --> 00:29:47,630
é a primeira coisa que é recuperada da fila.

384
00:29:47,630 --> 00:29:51,490
As filas também são frequentemente utilizados quando estamos lidando com gráficos,

385
00:29:51,490 --> 00:29:55,560
como falamos brevemente com pilhas,

386
00:29:55,560 --> 00:30:00,260
e as filas também são úteis para um monte de outras coisas.

387
00:30:00,260 --> 00:30:06,180
Uma coisa que surge muitas vezes é tentar manter, por exemplo,

388
00:30:06,180 --> 00:30:12,310
uma lista ordenada de elementos.

389
00:30:12,310 --> 00:30:17,650
E você pode fazer isso com uma matriz. Você pode manter uma lista ordenada de coisas em uma matriz,

390
00:30:17,650 --> 00:30:20,650
mas onde que fica complicado é, então você sempre tem que encontrar

391
00:30:20,650 --> 00:30:26,160
o lugar apropriado para inserir a próxima coisa.

392
00:30:26,160 --> 00:30:28,250
Então se você tem uma matriz de números, de 1 a 10,

393
00:30:28,250 --> 00:30:31,630
e então você quer expandir isso para todos os números de 1 a 100,

394
00:30:31,630 --> 00:30:33,670
e você está ficando estes números de forma aleatória e tentando manter tudo

395
00:30:33,670 --> 00:30:40,650
classificados como você passar, você acaba tendo que fazer um monte de mudança.

396
00:30:40,650 --> 00:30:43,910
Com certos tipos de filas e certos tipos de estruturas de dados subjacentes,

397
00:30:43,910 --> 00:30:46,670
você pode realmente mantê-lo bastante simples.

398
00:30:46,670 --> 00:30:50,640
Você não tem que adicionar alguma coisa e, em seguida reordene a coisa toda de cada vez.

399
00:30:50,640 --> 00:30:56,770
Nem você tem que fazer um monte de mudança dos elementos internos ao redor.

400
00:30:56,770 --> 00:31:02,990
Quando olhamos para uma fila, você vê que - também em queue.c no código de seção -

401
00:31:02,990 --> 00:31:10,950
a estrutura que temos dado a você realmente é parecida com a estrutura que lhe deu de uma pilha.

402
00:31:10,950 --> 00:31:13,770
>> Há uma exceção a isso, e que uma exceção

403
00:31:13,770 --> 00:31:21,700
é que temos este inteiro adicional chamado a cabeça,

404
00:31:21,700 --> 00:31:28,120
eo chefe aqui é para manter o controle da cabeça da fila,

405
00:31:28,120 --> 00:31:32,160
ou o primeiro elemento na fila.

406
00:31:32,160 --> 00:31:37,470
Com uma pilha, fomos capazes de manter o controle do elemento que estávamos prestes a recuperar,

407
00:31:37,470 --> 00:31:40,800
ou a parte superior da pilha, utilizando apenas o tamanho,

408
00:31:40,800 --> 00:31:44,220
enquanto que com uma fila, estamos tendo que lidar com extremos opostos.

409
00:31:44,220 --> 00:31:49,000
Estamos tentando alinhavar as coisas em no final, mas em seguida, retornar as coisas de frente.

410
00:31:49,000 --> 00:31:54,640
Assim, de forma eficaz, com a cabeça, temos o índice do início da fila,

411
00:31:54,640 --> 00:31:58,920
e o tamanho dá-nos o índice do fim da fila

412
00:31:58,920 --> 00:32:03,730
para que possamos recuperar as coisas da cabeça e acrescentar coisas a cauda.

413
00:32:03,730 --> 00:32:06,890
Enquanto que com a pilha, estávamos sempre apenas lida com o topo da pilha.

414
00:32:06,890 --> 00:32:08,900
Nunca tinha a aceder ao fundo da pilha.

415
00:32:08,900 --> 00:32:12,220
Nós só acrescentou coisas para cima e levou as coisas fora do topo

416
00:32:12,220 --> 00:32:17,470
assim nós não precisamos que campo extra dentro da nossa estrutura.

417
00:32:17,470 --> 00:32:20,590
Isso geralmente faz sentido?

418
00:32:20,590 --> 00:32:27,670
Tudo bem. Sim, Charlotte? [Charlotte, ininteligível]

419
00:32:27,670 --> 00:32:32,660
[Hardison] Isso é uma grande questão, e que foi um que surgiu em palestra.

420
00:32:32,660 --> 00:32:36,290
Talvez caminhando através de alguns exemplos que ilustram por

421
00:32:36,290 --> 00:32:41,400
nós não queremos usar cordas [0] como chefe de fila.

422
00:32:41,400 --> 00:32:46,770
>> Então, imagine que temos a nossa fila, vamos chamá-lo de fila.

423
00:32:46,770 --> 00:32:49,210
No início, quando temos apenas instanciado-lo,

424
00:32:49,210 --> 00:32:53,330
quando temos apenas declarou que, não temos nada inicializado.

425
00:32:53,330 --> 00:32:56,790
É tudo lixo. Então, é claro que nós queremos ter certeza de que nós inicializar

426
00:32:56,790 --> 00:33:00,950
tanto o tamanho e os campos de cabeça para ser 0, algo razoável.

427
00:33:00,950 --> 00:33:05,770
Nós também pode ir em frente e nulo fora os elementos na nossa fila.

428
00:33:05,770 --> 00:33:09,930
E para fazer este ajuste diagrama, observe que agora a nossa fila só pode ter três elementos;

429
00:33:09,930 --> 00:33:13,150
enquanto que a nossa pilha poderia prender quatro, nossa fila só pode ter três.

430
00:33:13,150 --> 00:33:18,680
E isso é só para fazer o ajuste diagrama.

431
00:33:18,680 --> 00:33:26,150
A primeira coisa que acontece aqui é que colocar na fila a string "oi".

432
00:33:26,150 --> 00:33:30,380
E, assim como fizemos com a pilha, nada muito diferente aqui,

433
00:33:30,380 --> 00:33:39,230
jogamos a corda no em cordas [0] e incrementar o nosso tamanho em 1.

434
00:33:39,230 --> 00:33:42,720
Nós enfileirar "adeus", ele é colocado.

435
00:33:42,720 --> 00:33:45,870
Portanto, esta parece uma pilha para a maior parte.

436
00:33:45,870 --> 00:33:53,230
Nós começamos aqui, elemento novo, elemento novo, o tamanho continua a subir.

437
00:33:53,230 --> 00:33:56,330
O que acontece neste momento quando queremos desenfileirar alguma coisa?

438
00:33:56,330 --> 00:34:01,280
Quando queremos retirar da fila, que é o elemento que queremos retirar da fila?

439
00:34:01,280 --> 00:34:04,110
[Basil] Strings [0]. >> Zero. Exatamente, Basil.

440
00:34:04,110 --> 00:34:10,960
Queremos livrar-se da primeira cadeia, este, "oi".

441
00:34:10,960 --> 00:34:13,170
Então, qual foi a outra coisa que mudou?

442
00:34:13,170 --> 00:34:17,010
Observe quando apareceu algo fora da pilha, só mudou o tamanho,

443
00:34:17,010 --> 00:34:22,080
mas aqui, temos um par de coisas que mudam.

444
00:34:22,080 --> 00:34:27,440
Não só a alteração de tamanho, mas as alterações de cabeça.

445
00:34:27,440 --> 00:34:31,020
Isso vai de volta ao ponto de Charlotte anteriormente:

446
00:34:31,020 --> 00:34:38,699
Por que temos esta cabeça também?

447
00:34:38,699 --> 00:34:42,110
Será que faz sentido agora, Charlotte? Tipo de >>.

448
00:34:42,110 --> 00:34:47,500
[Hardison] Kind of? Então, o que aconteceu quando dequeued?

449
00:34:47,500 --> 00:34:54,340
O que fez a cabeça de fazer isso agora é interessante?

450
00:34:54,340 --> 00:34:56,449
[Charlotte] Ah, porque ele mudou - tudo bem. Eu vejo.

451
00:34:56,449 --> 00:35:02,090
Porque a cabeça - onde a cabeça está apontando para mudanças em termos de localização.

452
00:35:02,090 --> 00:35:07,200
Não é mais sempre a um índice zero. >> Sim, exatamente.

453
00:35:07,200 --> 00:35:17,660
O que aconteceu foi dequeueing se o elemento de alta

454
00:35:17,660 --> 00:35:20,590
foi feito e nós não têm essa cabeça campo

455
00:35:20,590 --> 00:35:26,880
porque estávamos sempre ligando essa string em 0 índice de o chefe da nossa fila,

456
00:35:26,880 --> 00:35:30,170
então nós teríamos que mudar o resto da fila de baixo.

457
00:35:30,170 --> 00:35:36,010
Nós teríamos que mudar o "adeus" de de cordas [1] para as cordas [0].

458
00:35:36,010 --> 00:35:38,760
E cordas [2] para baixo para cordas [1].

459
00:35:38,760 --> 00:35:43,050
E nós temos que fazer isso 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 quando estamos fazendo isso com uma matriz, que fica muito caro.

462
00:35:50,490 --> 00:35:53,340
Então, aqui, não é um grande negócio. Só temos três elementos na nossa matriz.

463
00:35:53,340 --> 00:35:57,230
Mas se tivéssemos uma fila de milhares de elementos ou de um milhão de elementos,

464
00:35:57,230 --> 00:36:00,060
e então, de repente, começamos a fazer um monte de dequeue chama a todos em um loop,

465
00:36:00,060 --> 00:36:03,930
as coisas estão realmente indo para desacelerar como ele muda tudo para baixo constantemente.

466
00:36:03,930 --> 00:36:07,320
Você sabe, mudar por 1, por uma mudança de turno, por 1, por uma mudança.

467
00:36:07,320 --> 00:36:13,650
Em vez disso, usamos essa cabeça, chamamos isso de um "ponteiro", apesar de que não é realmente um ponteiro

468
00:36:13,650 --> 00:36:16,430
em sentido estrito, não é um tipo de ponteiro.

469
00:36:16,430 --> 00:36:19,410
Não é um * int ou um char * ou qualquer coisa assim.

470
00:36:19,410 --> 00:36:28,930
Mas está apontando ou indicando o chefe da nossa fila. Sim?

471
00:36:28,930 --> 00:36:38,800
>> [Estudante] Como dequeue sabe apenas pop fora o que está na cabeça?

472
00:36:38,800 --> 00:36:43,620
[Hardison] Como dequeue saber como pop fora tudo o que está na cabeça? Direito >>, sim.

473
00:36:43,620 --> 00:36:49,050
>> O que ele está vendo é apenas o que a cabeça campo está definido.

474
00:36:49,050 --> 00:36:52,710
Assim, neste primeiro caso, se olharmos bem aqui,

475
00:36:52,710 --> 00:36:55,690
nossa cabeça é 0, 0 índice. >> Direito.

476
00:36:55,690 --> 00:37:00,500
[Hardison] Então ele só diz bem, bem, o elemento no índice 0, a seqüência de "oi",

477
00:37:00,500 --> 00:37:03,050
é o elemento na cabeça da nossa fila.

478
00:37:03,050 --> 00:37:05,570
Então, vamos para desenfileirar esse cara.

479
00:37:05,570 --> 00:37:09,800
E isso vai ser o elemento que é devolvido para o chamador.

480
00:37:09,800 --> 00:37:14,540
Sim, Saad? Assim, a cabeça >> basicamente define o - onde você está indo para indexá-lo?

481
00:37:14,540 --> 00:37:17,750
Isso é o começo? Sim >>. Ok >>.

482
00:37:17,750 --> 00:37:22,900
[Hardison] que está se tornando o novo começo para a nossa matriz.

483
00:37:22,900 --> 00:37:28,930
Então, quando você desenfileirar alguma coisa, tudo que você precisa fazer é acessar o elemento no índice q.head,

484
00:37:28,930 --> 00:37:32,240
e que será o elemento que pretende retirar da fila.

485
00:37:32,240 --> 00:37:34,930
Você também tem que diminuir o tamanho.

486
00:37:34,930 --> 00:37:39,430
Vamos ver um pouco as coisas ficam um pouco complicado com isso.

487
00:37:39,430 --> 00:37:46,520
Nós desenfileirar, e agora, se enfileirar novamente,

488
00:37:46,520 --> 00:37:51,300
onde é que vamos colocar na fila?

489
00:37:51,300 --> 00:37:55,000
Onde é que o próximo elemento ir na nossa fila?

490
00:37:55,000 --> 00:37:57,980
Dizer que queremos colocar na fila a string "CS".

491
00:37:57,980 --> 00:38:02,240
Em qual índice ela vai? [Os alunos] Strings [2]. >> Dois.

492
00:38:02,240 --> 00:38:04,980
Por 2 e não 0?

493
00:38:04,980 --> 00:38:13,570
[Basil] Porque agora a cabeça é 1, de modo que é como o início da lista?

494
00:38:13,570 --> 00:38:21,220
[Hardison] Direito. E o que indica o fim da lista?

495
00:38:21,220 --> 00:38:23,290
O que estávamos usando para indicar o final da nossa fila?

496
00:38:23,290 --> 00:38:25,970
A cabeça é o chefe da nossa fila, o início da nossa fila.

497
00:38:25,970 --> 00:38:29,530
O que é o fim da nossa fila? [Os alunos] Tamanho. Tamanho >>, exatamente.

498
00:38:29,530 --> 00:38:36,360
Assim, nossos novos elementos entrar em tamanho, e os elementos que tiramos sair na cabeça.

499
00:38:36,360 --> 00:38:45,390
Quando enfileirar o próximo elemento, estamos colocando-o em no tamanho.

500
00:38:45,390 --> 00:38:48,530
[Estudante] Antes de colocar isso em porém, tamanho era um, certo?

501
00:38:48,530 --> 00:38:55,690
[Hardison] Direito. Portanto, não muito em tamanho. + Tamanho, não um, mas a cabeça +.

502
00:38:55,690 --> 00:38:59,990
Porque nós mudou tudo pela quantidade cabeça.

503
00:38:59,990 --> 00:39:14,270
Então, aqui, agora temos uma fila de tamanho 1 que começa no índice 1.

504
00:39:14,270 --> 00:39:20,730
A cauda é índice 2. Sim?

505
00:39:20,730 --> 00:39:25,780
>> [Aluno] O que acontece quando você dequeue strings [0], e as cordas "slots de memória

506
00:39:25,780 --> 00:39:29,420
apenas se esvaziou, basicamente, ou simplesmente esquecida?

507
00:39:29,420 --> 00:39:34,700
[Hardison] Yeah. Neste sentido, estamos apenas esquecê-los.

508
00:39:34,700 --> 00:39:42,640
Se estivéssemos armazenar cópias deles para -

509
00:39:42,640 --> 00:39:46,310
muitas estruturas de dados, muitas vezes, armazenar as suas próprias cópias dos elementos

510
00:39:46,310 --> 00:39:51,760
de modo que a pessoa que gere a estrutura de dados não têm que se preocupar

511
00:39:51,760 --> 00:39:53,650
sobre onde todos os ponteiros estão indo.

512
00:39:53,650 --> 00:39:56,000
A estrutura de dados segura para tudo, segura a todas as cópias,

513
00:39:56,000 --> 00:39:59,580
para se certificar de que tudo persiste de forma adequada.

514
00:39:59,580 --> 00:40:03,140
No entanto, neste caso, estas estruturas de dados apenas, para simplificar,

515
00:40:03,140 --> 00:40:05,580
não estão fazendo cópias de tudo o que estamos armazenando em-los.

516
00:40:05,580 --> 00:40:08,630
[Estudante] Então este é um conjunto contínuo de -? Sim >>.

517
00:40:08,630 --> 00:40:14,350
Se olharmos para trás, o que a definição foi desta estrutura, é.

518
00:40:14,350 --> 00:40:19,110
É apenas uma matriz padrão, como você viu,

519
00:40:19,110 --> 00:40:24,280
uma matriz de char * s.

520
00:40:24,280 --> 00:40:26,340
Será que -? >> Sim, eu estava pensando

521
00:40:26,340 --> 00:40:29,130
se você eventualmente ficar sem memória, de certa forma,

522
00:40:29,130 --> 00:40:32,330
se você tem todos esses lugares vazios em sua matriz?

523
00:40:32,330 --> 00:40:36,390
[Hardison] Sim, é um bom ponto.

524
00:40:36,390 --> 00:40:41,530
>> Se olharmos para o que aconteceu agora, neste ponto,

525
00:40:41,530 --> 00:40:46,350
nós preenchemos a nossa fila, que parece.

526
00:40:46,350 --> 00:40:50,390
Mas nós não temos realmente cheio nossa fila

527
00:40:50,390 --> 00:40:57,710
porque temos uma fila que é tamanho 2, mas começa no índice 1,

528
00:40:57,710 --> 00:41:02,160
porque é onde nosso ponteiro cabeça.

529
00:41:02,160 --> 00:41:08,400
Como você estava dizendo, esse elemento em strings [0], no índice 0, não está realmente lá.

530
00:41:08,400 --> 00:41:10,450
Não está na nossa fila de mais.

531
00:41:10,450 --> 00:41:16,460
Nós apenas não se preocupou em ir e substituí-lo quando dequeued-lo.

532
00:41:16,460 --> 00:41:18,700
Assim, mesmo que parece que estamos sem memória, nós realmente não temos.

533
00:41:18,700 --> 00:41:23,270
Esse ponto está disponível para nós para usar.

534
00:41:23,270 --> 00:41:29,310
O comportamento adequado, se fôssemos tentar algo primeira dequeue

535
00:41:29,310 --> 00:41:34,420
como "bye", que seria pop bye fora.

536
00:41:34,420 --> 00:41:38,460
Agora a nossa fila começa no índice 2 e é de tamanho 1.

537
00:41:38,460 --> 00:41:42,240
E agora, se tentarmos e enfileirar algo novo, digamos, 50,

538
00:41:42,240 --> 00:41:47,880
50 deve ir neste lugar no índice 0

539
00:41:47,880 --> 00:41:51,270
porque ele ainda está disponível para nós. Sim, Saad?

540
00:41:51,270 --> 00:41:53,630
[Saad] Isso acontece automaticamente?

541
00:41:53,630 --> 00:41:56,150
[Hardison] Isso não acontece muito automaticamente. Você tem que fazer a matemática

542
00:41:56,150 --> 00:42:00,380
para fazer o trabalho, mas essencialmente o que temos feito é que acabamos enrolado.

543
00:42:00,380 --> 00:42:04,070
[Saad] E tudo bem se isso tem um buraco no meio dela?

544
00:42:04,070 --> 00:42:08,720
[Hardison] É se podemos fazer a matemática funcionar corretamente.

545
00:42:08,720 --> 00:42:15,470
>> E acontece que isso não é realmente difícil de fazer com o operador mod.

546
00:42:15,470 --> 00:42:20,040
Assim como fizemos com César e as coisas de criptografia,

547
00:42:20,040 --> 00:42:25,190
usando mod, podemos fazer as coisas para envolver e continuar

548
00:42:25,190 --> 00:42:28,090
ao redor e ao redor com nossa fila,

549
00:42:28,090 --> 00:42:32,180
manter esse ponteiro cabeça se movendo.

550
00:42:32,180 --> 00:42:38,840
Note-se que o tamanho é sempre respeitando o número de elementos, na verdade, dentro da fila.

551
00:42:38,840 --> 00:42:43,110
E isso é apenas o ponteiro de cabeça que mantém bicicleta passar.

552
00:42:43,110 --> 00:42:49,660
Se olharmos para o que aconteceu aqui, se voltar para o início,

553
00:42:49,660 --> 00:42:55,020
e você só vê o que acontece na cabeça

554
00:42:55,020 --> 00:42:58,240
quando enfileirar algo, nada aconteceu com a cabeça.

555
00:42:58,240 --> 00:43:00,970
Quando enfileirados outra coisa, nada aconteceu com a cabeça.

556
00:43:00,970 --> 00:43:04,130
Assim que dequeued algo, a cabeça vai-se por um.

557
00:43:04,130 --> 00:43:06,600
Nós enfileirado algo, não acontece nada na cabeça.

558
00:43:06,600 --> 00:43:11,060
Quando desenfileirar alguma coisa, de repente, a cabeça é incrementado.

559
00:43:11,060 --> 00:43:14,660
Quando enfileirar algo, não acontece nada na cabeça.

560
00:43:14,660 --> 00:43:20,240
>> O que aconteceria, neste ponto, se fôssemos desenfileirar algo de novo?

561
00:43:20,240 --> 00:43:23,240
Todos os pensamentos? O que aconteceria com a cabeça?

562
00:43:23,240 --> 00:43:27,190
O que deve acontecer com a cabeça

563
00:43:27,190 --> 00:43:32,990
se fôssemos para desenfileirar outra coisa?

564
00:43:32,990 --> 00:43:35,400
A cabeça agora está no índice 2,

565
00:43:35,400 --> 00:43:38,920
o que significa que a cabeça da fila é strings [2].

566
00:43:38,920 --> 00:43:44,280
[Estudante] Que retorna 0? >> Ele deve retornar a 0. Ela deve envolver em torno de volta, exatamente.

567
00:43:44,280 --> 00:43:48,440
Até agora, cada vez que chamado dequeue, estamos adicionando um na cabeça,

568
00:43:48,440 --> 00:43:50,960
adicionar um para a cabeça, adicione uma para a cabeça, adicione uma para a cabeça.

569
00:43:50,960 --> 00:43:58,400
Assim que esse ponteiro cabeça fica para o último índice em nossa matriz,

570
00:43:58,400 --> 00:44:05,650
então temos que envolvê-la de volta ao redor para o começo, voltar a 0.

571
00:44:05,650 --> 00:44:09,900
[Charlotte] O que determina a capacidade da fila em uma pilha?

572
00:44:09,900 --> 00:44:13,120
[Hardison] Neste caso, acabamos usando sido uma constante # definido. Ok >>.

573
00:44:13,120 --> 00:44:19,590
[Hardison] No arquivo c real., Você pode entrar e mexer com ele um pouco

574
00:44:19,590 --> 00:44:21,710
e torná-lo tão grande ou tão pouco como você quer.

575
00:44:21,710 --> 00:44:25,310
[Charlotte] Então, quando você está tornando-se uma fila, como você faz o computador saiba

576
00:44:25,310 --> 00:44:29,120
como grande você quer a pilha para ser?

577
00:44:29,120 --> 00:44:31,700
[Hardison] Isso é uma grande questão.

578
00:44:31,700 --> 00:44:34,800
Há um par de maneiras. Um é apenas para defini-lo na frente

579
00:44:34,800 --> 00:44:42,050
e dizer que isso vai ser uma fila que tem 4 elementos ou 50 elementos ou 10.000.

580
00:44:42,050 --> 00:44:45,430
A outra maneira é fazer o que as pessoas estão fazendo edição de hackers

581
00:44:45,430 --> 00:44:52,310
e criar funções para ter sua fila crescer dinamicamente como mais coisas são adicionados dentro

582
00:44:52,310 --> 00:44:54,740
>> [Charlotte] Então, para ir com a primeira opção, o que você usa sintaxe

583
00:44:54,740 --> 00:44:57,830
para dizer ao programa que é o tamanho da fila?

584
00:44:57,830 --> 00:45:04,780
[Hardison] Ah. Então, vamos sair dessa.

585
00:45:04,780 --> 00:45:12,650
Eu ainda estou em stack.c aqui, então eu estou indo só para rolar até o topo aqui.

586
00:45:12,650 --> 00:45:17,920
Você pode ver isso aqui? Este é o # define capacidade 10.

587
00:45:17,920 --> 00:45:24,600
E isso é quase exatamente a mesma sintaxe que temos para fila.

588
00:45:24,600 --> 00:45:28,390
Exceto na fila, temos que o campo estrutura extra aqui.

589
00:45:28,390 --> 00:45:32,760
[Charlotte] Oh, eu pensei que a capacidade significava a capacidade para a cadeia.

590
00:45:32,760 --> 00:45:36,770
[Hardison] Ah. >> Isso é o comprimento máximo da palavra. >> Entendi.

591
00:45:36,770 --> 00:45:41,180
Sim. A capacidade aqui - que é um grande ponto.

592
00:45:41,180 --> 00:45:44,000
E isso é algo que é complicado

593
00:45:44,000 --> 00:45:49,480
porque o que temos declarado aqui é uma matriz de char * s.

594
00:45:49,480 --> 00:45:52,770
Uma matriz de ponteiros.

595
00:45:52,770 --> 00:45:56,690
Esta é uma matriz de caracteres.

596
00:45:56,690 --> 00:46:01,690
Este é provavelmente o que você viu quando você foi declarar seus buffers para o arquivo I / O,

597
00:46:01,690 --> 00:46:06,840
quando você foi criar strings manualmente na pilha.

598
00:46:06,840 --> 00:46:09,090
No entanto, o que temos aqui é uma matriz de char * s.

599
00:46:09,090 --> 00:46:13,400
Então, é uma matriz de ponteiros.

600
00:46:13,400 --> 00:46:18,350
Na verdade, se o zoom para fora e olharmos o que está acontecendo aqui

601
00:46:18,350 --> 00:46:23,140
na apresentação, você vê que os elementos reais, os dados de caracteres

602
00:46:23,140 --> 00:46:26,180
não é armazenada dentro da própria matriz.

603
00:46:26,180 --> 00:46:42,690
O que está armazenada dentro de nossa matriz aqui são ponteiros para os dados de caracteres.

604
00:46:42,690 --> 00:46:52,560
Okay. Então, vimos como o tamanho da fila é como com a pilha,

605
00:46:52,560 --> 00:46:58,670
o tamanho respeita sempre o número de elementos na fila no momento.

606
00:46:58,670 --> 00:47:02,720
Depois de fazer 2 enfileira, o tamanho é 2.

607
00:47:02,720 --> 00:47:07,110
Depois de fazer uma dequeue o tamanho agora é 1.

608
00:47:07,110 --> 00:47:09,330
Depois de fazer outra enqueue o tamanho está de volta a 2.

609
00:47:09,330 --> 00:47:12,340
Assim, o tamanho definitivamente respeita ao número de elementos na fila,

610
00:47:12,340 --> 00:47:15,580
e depois a cabeça apenas mantém ciclismo.

611
00:47:15,580 --> 00:47:20,210
Ele vai de 0-1-2, 0-1-2, 0-1-2.

612
00:47:20,210 --> 00:47:25,620
E toda vez que nós chamamos dequeue, o ponteiro cabeça é incrementado para o próximo índice.

613
00:47:25,620 --> 00:47:29,930
E se a cabeça está prestes a passar por cima, ele volta para 0.

614
00:47:29,930 --> 00:47:34,870
Então, com isso, podemos escrever a função dequeue.

615
00:47:34,870 --> 00:47:40,200
E vamos deixar a função enqueue para vocês para implementar em seu lugar.

616
00:47:40,200 --> 00:47:45,880
>> Quando desenfileirar um elemento de nossa fila,

617
00:47:45,880 --> 00:47:55,490
qual foi a primeira coisa que Daniel fez quando começou a escrever a função pop para pilhas?

618
00:47:55,490 --> 00:48:00,490
Deixe-me ouvir de alguém que não tenha falado ainda.

619
00:48:00,490 --> 00:48:06,710
Vamos ver, Saad, você se lembra o que Daniel fez o que a primeira coisa quando escreveu pop?

620
00:48:06,710 --> 00:48:08,860
[Saad] Não foi, foi - >> Ele testou para alguma coisa.

621
00:48:08,860 --> 00:48:12,140
[Saad] Se o tamanho for maior do que 0. >> Exatamente.

622
00:48:12,140 --> 00:48:14,390
E o que foi que o teste para?

623
00:48:14,390 --> 00:48:19,090
[Saad] Isso foi um teste para ver se há alguma coisa dentro da matriz.

624
00:48:19,090 --> 00:48:23,210
[Hardison] Yeah. Exatamente. Então você não pode aparecer qualquer coisa fora da pilha, se ele está vazio.

625
00:48:23,210 --> 00:48:26,510
Da mesma forma, não se pode retirar da fila qualquer coisa de uma fila se ele está vazio.

626
00:48:26,510 --> 00:48:30,420
Qual é a primeira coisa que devemos fazer em nossa função dequeue aqui, que você acha?

627
00:48:30,420 --> 00:48:33,860
[Saad] Se o tamanho for maior do que 0? Sim >>.

628
00:48:33,860 --> 00:48:37,710
Neste caso, eu realmente apenas testado para ver se ele é 0.

629
00:48:37,710 --> 00:48:42,240
Se for 0, podemos retornar nulo.

630
00:48:42,240 --> 00:48:45,280
Mas a lógica exatamente o mesmo.

631
00:48:45,280 --> 00:48:49,110
E vamos continuar com isso.

632
00:48:49,110 --> 00:48:54,600
Se o tamanho não é 0, onde é o elemento que queremos retirar da fila?

633
00:48:54,600 --> 00:48:58,550
[Saad] Na cabeça? >> Exatamente.

634
00:48:58,550 --> 00:49:01,720
Nós podemos apenas retirar o primeiro elemento em nossa fila

635
00:49:01,720 --> 00:49:07,040
acessando o elemento na cabeça.

636
00:49:07,040 --> 00:49:14,630
Nada louco.

637
00:49:14,630 --> 00:49:19,620
Depois disso, o que devemos fazer? O que tem que acontecer?

638
00:49:19,620 --> 00:49:23,740
Qual foi a outra coisa que falamos no dequeue?

639
00:49:23,740 --> 00:49:28,130
Duas coisas tem que acontecer, porque a nossa fila mudou.

640
00:49:28,130 --> 00:49:35,640
[Daniel] Reduzir o tamanho. >> Nós temos de reduzir o tamanho e aumentar a cabeça? Exatamente.

641
00:49:35,640 --> 00:49:40,600
Para aumentar a cabeça, não podemos apenas cega aumentar a cabeça, lembre-se.

642
00:49:40,600 --> 00:49:45,080
Não podemos apenas fazer queue.head + +.

643
00:49:45,080 --> 00:49:51,630
Temos também a incluir este mod pela capacidade.

644
00:49:51,630 --> 00:49:54,740
E por que nós mod pela capacidade, Stella?

645
00:49:54,740 --> 00:49:58,680
[Stella] Porque ele tem que envolver. >> Exatamente.

646
00:49:58,680 --> 00:50:04,750
Nós mod pela capacidade porque tem que envolver a volta a 0.

647
00:50:04,750 --> 00:50:07,400
Então, agora, neste momento, podemos fazer o que disse Daniel.

648
00:50:07,400 --> 00:50:12,700
Nós podemos diminuir o tamanho.

649
00:50:12,700 --> 00:50:29,170
E então podemos simplesmente retornar o elemento que estava no início da fila.

650
00:50:29,170 --> 00:50:34,000
Olha o tipo de gnarly em primeiro lugar. Você pode ter uma pergunta. Desculpe?

651
00:50:34,000 --> 00:50:37,260
>> [Sam] Por que é o primeiro no topo da fila? Onde é que isso vai?

652
00:50:37,260 --> 00:50:42,480
[Hardison] Vem da quarta linha do fundo.

653
00:50:42,480 --> 00:50:46,060
Depois que testar para ter certeza de que a nossa fila não está vazia,

654
00:50:46,060 --> 00:50:54,100
nós retiramos char * primeiro, retire o elemento que está sentado no índice cabeça

655
00:50:54,100 --> 00:50:58,680
de nossa matriz, da nossa matriz cordas >>, e chamada que primeiro?

656
00:50:58,680 --> 00:51:04,500
[Hardison] E chamamos isso de primeira. Sim.

657
00:51:04,500 --> 00:51:09,850
Só para acompanhar isso, por que você acha que nós tivemos que fazer isso?

658
00:51:09,850 --> 00:51:18,270
[Sam] Cada primeiro está apenas retornando q.strings [q.head]? Sim >>.

659
00:51:18,270 --> 00:51:23,830
>> Porque estamos fazendo isso mudança do q.head com a função mod,

660
00:51:23,830 --> 00:51:27,810
e não há maneira de fazer isso dentro da linha de retorno também.

661
00:51:27,810 --> 00:51:31,640
[Hardison] Exatamente. Você está no local. Sam está totalmente reconhecidas.

662
00:51:31,640 --> 00:51:36,800
A razão pela qual teve de retirar o primeiro elemento em nossa fila e armazená-lo em uma variável

663
00:51:36,800 --> 00:51:43,030
é porque esta linha que tinha a apenas q.head,

664
00:51:43,030 --> 00:51:47,030
há o operador mod lá não é algo que podemos fazer

665
00:51:47,030 --> 00:51:51,230
e tê-lo em vigor na cabeça sem - em uma única linha.

666
00:51:51,230 --> 00:51:54,480
Então, nós realmente temos que tirar o primeiro elemento, em seguida, ajuste a cabeça,

667
00:51:54,480 --> 00:52:00,430
ajustar o tamanho, e, em seguida, retornar o elemento que tirou.

668
00:52:00,430 --> 00:52:02,680
E isso é algo que vamos ver surgir mais tarde com

669
00:52:02,680 --> 00:52:04,920
listas ligadas, como brincar com eles.

670
00:52:04,920 --> 00:52:08,410
Muitas vezes, quando você está liberando ou eliminação de listas ligadas

671
00:52:08,410 --> 00:52:13,500
é preciso lembrar o próximo elemento, o ponteiro próximo de uma lista ligada

672
00:52:13,500 --> 00:52:16,330
antes de descartar o atual.

673
00:52:16,330 --> 00:52:23,580
Porque senão você jogar fora a informação do que resta na lista.

674
00:52:23,580 --> 00:52:34,160
Agora, se você vai para o seu aparelho, você abre queue.c-x fora deste.

675
00:52:34,160 --> 00:52:39,390
Então, se eu abrir queue.c, deixe-me zoom aqui,

676
00:52:39,390 --> 00:52:44,970
você vai ver que você tem um arquivo similar para o futuro.

677
00:52:44,970 --> 00:52:49,200
Parecidas arquivo com o que tínhamos antes com stack.c.

678
00:52:49,200 --> 00:52:54,690
Nós temos a nossa estrutura de fila definida apenas como vimos nos slides.

679
00:52:54,690 --> 00:52:59,870
>> Nós temos a nossa função enqueue que é para você fazer.

680
00:52:59,870 --> 00:53:04,340
E nós temos a função dequeue aqui.

681
00:53:04,340 --> 00:53:06,870
A função dequeue no arquivo é não implementado,

682
00:53:06,870 --> 00:53:13,230
mas vou colocá-lo de volta no PowerPoint para que você possa digitá-lo, se quiser.

683
00:53:13,230 --> 00:53:16,690
Assim, para os próximos 5 minutos ou mais, vocês trabalham em enqueue

684
00:53:16,690 --> 00:53:22,570
que é quase o contrário do dequeue.

685
00:53:22,570 --> 00:53:29,560
Você não tem que ajustar cabeça quando você está enqueueing, mas o que você tem que ajustar?

686
00:53:29,560 --> 00:53:38,920
Tamanho. Então, quando você enqueue, a cabeça permanece intocada, o tamanho é alterado.

687
00:53:38,920 --> 00:53:46,920
Mas é preciso um pouco de - você vai ter que brincar com essa mod

688
00:53:46,920 --> 00:53:57,560
para descobrir exatamente o que o índice do novo elemento deve ser inserido no.

689
00:53:57,560 --> 00:54:03,080
Então, eu vou dar a vocês um pouco, colocar desenfileirar volta no slide,

690
00:54:03,080 --> 00:54:05,200
e como vocês têm perguntas, gritar-los para que possamos

691
00:54:05,200 --> 00:54:09,220
todos falam sobre eles como um grupo.

692
00:54:09,220 --> 00:54:13,960
Além disso, com o tamanho que você não - quando você ajustar o tamanho, você pode sempre -

693
00:54:13,960 --> 00:54:18,720
você tem para modificar o tamanho de sempre? [Daniel] Não. >> Você não tem para modificar o tamanho, a direita.

694
00:54:18,720 --> 00:54:24,260
Como o tamanho sempre, se você está - supondo que você está administrando as coisas de forma adequada,

695
00:54:24,260 --> 00:54:30,840
o tamanho será sempre entre 0 e 3.

696
00:54:30,840 --> 00:54:38,680
Onde você tem que mod quando você está fazendo enqueue?

697
00:54:38,680 --> 00:54:41,060
[Estudante] Só para a cabeça. Só >> para a cabeça, exatamente.

698
00:54:41,060 --> 00:54:44,620
E por que você tem de mod em tudo em enqueue?

699
00:54:44,620 --> 00:54:48,830
Quando é uma situação em que você tem que mod?

700
00:54:48,830 --> 00:54:53,630
[Estudante] Se você tem coisas em espaços, como em espaços 1 e 2,

701
00:54:53,630 --> 00:54:55,950
e depois que você precisava para acrescentar algo a 0.

702
00:54:55,950 --> 00:55:02,570
[Hardison] Sim, exatamente. Então, se o ponteiro cabeça está no fim,

703
00:55:02,570 --> 00:55:14,210
ou se o seu tamanho, mais a sua cabeça é maior, ou melhor, vai envolver em torno da fila.

704
00:55:14,210 --> 00:55:17,830
>> Então, nessa situação que nós temos aqui em cima no slide agora,

705
00:55:17,830 --> 00:55:24,370
se eu quiser colocar na fila alguma coisa 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ão, se você olhar para onde o 50 vai, e eu chamo enqueue 50,

708
00:55:35,450 --> 00:55:40,840
vai lá no fundo. Ele vai em 0 índice.

709
00:55:40,840 --> 00:55:44,160
Ele substitui o 'oi' que já foi retirado da fila.

710
00:55:44,160 --> 00:55:46,210
[Daniel] Não tome o cuidado de que em dequeue já?

711
00:55:46,210 --> 00:55:50,550
Por que fazer qualquer coisa com a cabeça em enqueue?

712
00:55:50,550 --> 00:55:55,770
[Hardison] Ah, então você não está modificando a cabeça, me desculpe.

713
00:55:55,770 --> 00:56:02,310
Mas você tem que usar o operador mod quando você está acessando

714
00:56:02,310 --> 00:56:04,250
o elemento que você quer colocar na fila quando você está acessando

715
00:56:04,250 --> 00:56:06,960
o próximo elemento na sua fila.

716
00:56:06,960 --> 00:56:10,960
[Basil] Eu não fiz isso, e eu tenho "sucesso" por lá.

717
00:56:10,960 --> 00:56:13,370
[Daniel] Oh, eu entendo o que você está dizendo.

718
00:56:13,370 --> 00:56:16,240
[Hardison] Então você didn't - você fez no q.size?

719
00:56:16,240 --> 00:56:20,670
[Basil] Yeah. Eu só mudou de lado, eu não fiz nada com a cabeça.

720
00:56:20,670 --> 00:56:24,300
[Hardison] Você realmente não tem que repor a cabeça para ser qualquer coisa,

721
00:56:24,300 --> 00:56:31,650
mas quando você índice na matriz cordas,

722
00:56:31,650 --> 00:56:39,500
você realmente tem que ir em frente e calcular onde o próximo elemento é,

723
00:56:39,500 --> 00:56:44,230
withe porque a pilha, o elemento seguinte na sua pilha sempre foi

724
00:56:44,230 --> 00:56:48,740
no índice correspondente ao tamanho.

725
00:56:48,740 --> 00:56:55,850
Se olharmos para trás até à nossa função push pilha,

726
00:56:55,850 --> 00:57:03,100
podemos sempre plunk em nosso novo elemento à direita no tamanho do índice.

727
00:57:03,100 --> 00:57:06,710
Considerando que, com a fila, não podemos fazer isso

728
00:57:06,710 --> 00:57:10,340
porque, se estamos nesta situação,

729
00:57:10,340 --> 00:57:18,130
se enfileirado 50 cadeia de nosso novo iria bem no strings [1]

730
00:57:18,130 --> 00:57:20,540
que não queremos fazer.

731
00:57:20,540 --> 00:57:41,200
Queremos ter a nova cadeia ir no índice 0.

732
00:57:41,200 --> 00:57:44,320
>> Alguém - sim? [Estudante] Eu tenho uma pergunta, mas não é realmente relacionados.

733
00:57:44,320 --> 00:57:48,160
O que significa quando alguém apenas chama algo como ponteiro pred?

734
00:57:48,160 --> 00:57:51,260
O que é que o nome curto para? Eu sei que é apenas um nome.

735
00:57:51,260 --> 00:57:59,110
[Hardison] ponteiro Pred? Vamos ver. Em que contexto?

736
00:57:59,110 --> 00:58:01,790
[Aluno] Foi para a inserção. Posso pedir-lhe mais tarde, se você quiser

737
00:58:01,790 --> 00:58:03,920
porque realmente não é relacionado, mas eu só -

738
00:58:03,920 --> 00:58:07,300
[Hardison] Do código de David inserção de aula?

739
00:58:07,300 --> 00:58:10,860
Podemos puxar isso e falar sobre isso.

740
00:58:10,860 --> 00:58:15,550
Vamos falar sobre isso a seguir, uma vez que temos de listas ligadas.

741
00:58:15,550 --> 00:58:21,440
>> Então, vamos muito rápido olhar para o que a função enqueue parece.

742
00:58:21,440 --> 00:58:26,530
Qual foi a primeira coisa que as pessoas tentaram fazer em sua linha enqueue? Para esta fila?

743
00:58:26,530 --> 00:58:29,960
Semelhante ao que você fez para a pilha de empurrar.

744
00:58:29,960 --> 00:58:32,080
O que você fez, Stella?

745
00:58:32,080 --> 00:58:35,050
[Stella, ininteligível]

746
00:58:35,050 --> 00:58:45,700
[Hardison] Exatamente. If (q.size CAPACIDADE ==) -

747
00:58:45,700 --> 00:58:54,720
Eu preciso colocar o meu aparelho no lugar certo - retornar falso.

748
00:58:54,720 --> 00:59:01,370
Zoom em um pouco. Okay.

749
00:59:01,370 --> 00:59:03,800
Agora, qual é a próxima coisa que temos que fazer?

750
00:59:03,800 --> 00:59:11,370
Assim como com a pilha, e inserida no lugar certo.

751
00:59:11,370 --> 00:59:16,010
E assim o que era o lugar certo para inserir essa?

752
00:59:16,010 --> 00:59:23,170
Com a pilha era o tamanho do índice, com isso, não é bem assim.

753
00:59:23,170 --> 00:59:30,210
[Daniel] Eu tenho q.head--ou - q.strings >>? >> Sim.

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 provavelmente deseja colocar parênteses em torno deste

756
00:59:42,740 --> 00:59:48,830
de modo que nós estamos começando a precedência apropriada e de modo que é cleart a todos.

757
00:59:48,830 --> 00:59:55,800
E definir que igual? >> Para str? >> Para str. Grande.

758
00:59:55,800 --> 01:00:00,160
E agora o que é a última coisa que temos de fazer?

759
01:00:00,160 --> 01:00:06,780
Assim como fizemos na pilha. >> Incrementar o tamanho? >> Incrementar o tamanho.

760
01:00:06,780 --> 01:00:13,830
Boom. E então, uma vez que o código inicial só retornou falso por padrão,

761
01:00:13,830 --> 01:00:27,460
nós queremos mudar isso para true se tudo passa e tudo vai bem.

762
01:00:27,460 --> 01:00:33,050
Tudo bem. Isso é um monte de informações para seção.

763
01:00:33,050 --> 01:00:39,480
Nós não somos muito mais. Nós queremos falar muito rapidamente sobre isoladamente ligados listas.

764
01:00:39,480 --> 01:00:44,010
Vou colocar isto para que possamos voltar a ele mais tarde.

765
01:00:44,010 --> 01:00:50,850
Mas vamos voltar para a nossa apresentação para apenas mais alguns slides.

766
01:00:50,850 --> 01:00:53,790
Então enqueue é TODO, agora temos feito isso.

767
01:00:53,790 --> 01:00:57,430
>> Agora vamos dar uma olhada isoladamente ligados listas.

768
01:00:57,430 --> 01:01:00,040
Nós conversamos sobre isso mais um pouco na palestra.

769
01:01:00,040 --> 01:01:02,540
Como muitos de vocês viu a demo onde tivemos pessoas

770
01:01:02,540 --> 01:01:08,220
desajeitadamente apontando para outros números e cada uma exploração? >> Eu estava nessa.

771
01:01:08,220 --> 01:01:16,620
>> O que vocês acham? Fiz isso, espero que desmistificar estes um pouco?

772
01:01:16,620 --> 01:01:25,990
Com uma lista, verifica-se que lidar com esse tipo que nós vamos chamar um nó.

773
01:01:25,990 --> 01:01:32,520
Considerando que, com a fila ea pilha que tínhamos estruturas que nós chamamos de fila na pilha,

774
01:01:32,520 --> 01:01:34,860
tivemos esses nova fila em tipos de pilha,

775
01:01:34,860 --> 01:01:39,240
aqui uma lista realmente é feita apenas de um monte de nós.

776
01:01:39,240 --> 01:01:45,920
Da mesma forma que as cordas são apenas um monte de chars todos alinhados ao lado do outro.

777
01:01:45,920 --> 01:01:50,650
Uma lista ligada é apenas um nó e outro nó e outro nó e outro nó.

778
01:01:50,650 --> 01:01:55,080
E, em vez de esmagar todos os nós e armazená-los em conjunto de forma contígua

779
01:01:55,080 --> 01:01:58,090
todos ao lado uns dos outros na memória,

780
01:01:58,090 --> 01:02:04,470
ter este ponteiro próximo nos permite armazenar os nós onde quer que, de forma aleatória.

781
01:02:04,470 --> 01:02:10,500
E, em seguida, o tipo de fio de todos eles em conjunto para o ponto de um para o outro.

782
01:02:10,500 --> 01:02:15,850
>> E o que era a grande vantagem que esta teve sobre uma matriz?

783
01:02:15,850 --> 01:02:21,680
Sobre tudo o armazenamento de forma contígua apenas preso ao lado do outro?

784
01:02:21,680 --> 01:02:24,190
Você se lembra? Sim? >> Alocação de memória dinâmica?

785
01:02:24,190 --> 01:02:27,220
>> Alocação de memória dinâmica em que sentido?

786
01:02:27,220 --> 01:02:31,780
[Estudante] Em que você pode continuar fazendo-o maior e você não tem que mover o conjunto inteiro?

787
01:02:31,780 --> 01:02:40,940
[Hardison] Exatamente. Assim, com uma matriz, quando você quer colocar um novo elemento para o meio,

788
01:02:40,940 --> 01:02:45,320
você tem que mudar tudo para o espaço.

789
01:02:45,320 --> 01:02:47,880
E como falamos com a fila,

790
01:02:47,880 --> 01:02:50,080
é por isso que manter o ponteiro cabeça,

791
01:02:50,080 --> 01:02:52,050
de modo que não estamos constantemente mudando as coisas.

792
01:02:52,050 --> 01:02:54,520
Porque isso fica caro, se você tem uma grande matriz

793
01:02:54,520 --> 01:02:57,130
e você está constantemente fazendo essas inserções aleatórias.

794
01:02:57,130 --> 01:03:00,820
Considerando que, com uma lista, tudo que você tem a fazer é jogá-lo em um novo nó,

795
01:03:00,820 --> 01:03:06,330
ajustar os ponteiros, e está feito.

796
01:03:06,330 --> 01:03:10,940
O que suga sobre isso?

797
01:03:10,940 --> 01:03:16,830
Afora o fato de que não é tão fácil de trabalhar como uma matriz? Sim?

798
01:03:16,830 --> 01:03:22,980
[Daniel] Bem, eu acho que é muito mais difícil de acessar um elemento específico na lista ligada?

799
01:03:22,980 --> 01:03:30,470
[Hardison] Você não pode simplesmente pular de um elemento arbitrário no meio da lista de relacionados.

800
01:03:30,470 --> 01:03:33,800
Como é que você tem que fazer isso em vez disso? >> Você tem que percorrer a coisa toda.

801
01:03:33,800 --> 01:03:35,660
[Hardison] Yeah. Você tem que passar por um de cada vez, uma de cada vez.

802
01:03:35,660 --> 01:03:38,480
É uma enorme - é uma dor.

803
01:03:38,480 --> 01:03:41,550
Qual é a outra - não há outra queda para isso.

804
01:03:41,550 --> 01:03:45,340
[Basil] Você não pode ir para a frente e para trás? Você tem que ir uma direção?

805
01:03:45,340 --> 01:03:48,570
[Hardison] Yeah. Então, como vamos resolver isso, às vezes?

806
01:03:48,570 --> 01:03:53,370
[Basil] duplamente vinculada listas? >> Exatamente. Há listas duplamente ligadas.

807
01:03:53,370 --> 01:03:55,540
Há também - muito?

808
01:03:55,540 --> 01:03:57,620
>> [Sam] É o mesmo que usar a coisa que pred -

809
01:03:57,620 --> 01:04:01,090
Acabei de me lembrar, não é isso que a coisa é para pred?

810
01:04:01,090 --> 01:04:05,850
Não é que entre dupla e individualmente?

811
01:04:05,850 --> 01:04:10,020
Olhar [Hardison] Vamos para o que exatamente ele estava fazendo.

812
01:04:10,020 --> 01:04:15,760
Então, vamos lá. Aqui está a lista de códigos.

813
01:04:15,760 --> 01:04:25,620
Aqui temos predptr, aqui. É isso o que você estava falando?

814
01:04:25,620 --> 01:04:30,750
Portanto, este foi - ele está liberando uma lista e ele está tentando armazenar um ponteiro para ele.

815
01:04:30,750 --> 01:04:35,000
Este não é o dobro, vinculada isoladamente-listas.

816
01:04:35,000 --> 01:04:40,090
Podemos falar mais sobre isso mais tarde uma vez que este está falando sobre a liberação da lista

817
01:04:40,090 --> 01:04:42,900
e eu quero mostrar algumas outras coisas primeiro.

818
01:04:42,900 --> 01:04:51,480
mas é só - é lembrar o valor de ptr

819
01:04:51,480 --> 01:04:54,170
[Estudante] Ah, é ponteiro precedente? Sim >>.

820
01:04:54,170 --> 01:05:04,070
Para que possamos então incrementar ptr-se antes que, então, livre predptr que é.

821
01:05:04,070 --> 01:05:09,130
Porque nós não podemos ptr livre e depois chamar ptr = ptr vem, certo?

822
01:05:09,130 --> 01:05:11,260
Isso seria ruim.

823
01:05:11,260 --> 01:05:20,940
Então vamos ver, de volta para esse cara.

824
01:05:20,940 --> 01:05:23,900
>> A outra coisa ruim sobre listas é que, enquanto que com uma matriz

825
01:05:23,900 --> 01:05:26,520
temos apenas todos os elementos próprios empilhadas lado a lado,

826
01:05:26,520 --> 01:05:29,050
Aqui também temos introduzido este ponteiro.

827
01:05:29,050 --> 01:05:34,060
Portanto, há um pedaço adicional de memória que estamos tendo de usar

828
01:05:34,060 --> 01:05:37,910
para cada elemento que nós estamos guardando em nossa lista.

829
01:05:37,910 --> 01:05:40,030
Nós temos flexibilidade, mas tem um custo.

830
01:05:40,030 --> 01:05:42,230
Ele vem com esse tempo, custo

831
01:05:42,230 --> 01:05:45,270
e ele vem com esse custo de memória também.

832
01:05:45,270 --> 01:05:47,800
Tempo, no sentido de que agora temos de passar por cada elemento na matriz

833
01:05:47,800 --> 01:05:58,670
para encontrar o índice de 10, ou que teria sido índice 10 em uma matriz.

834
01:05:58,670 --> 01:06:01,230
>> Só muito rapidamente, quando diagrama de fora destas listas,

835
01:06:01,230 --> 01:06:05,980
normalmente temos para a cabeça da lista ou o primeiro ponteiro da lista

836
01:06:05,980 --> 01:06:08,010
e note que este é um ponteiro verdade.

837
01:06:08,010 --> 01:06:11,100
É apenas 4 bytes. Não é um nó em si.

838
01:06:11,100 --> 01:06:17,120
Então você vê que ele não tem valor int nele, nenhum ponteiro próxima nele.

839
01:06:17,120 --> 01:06:20,790
É literalmente apenas um ponteiro.

840
01:06:20,790 --> 01:06:23,550
Vai apontar para algo que é uma estrutura de nó real.

841
01:06:23,550 --> 01:06:28,480
[Sam] Um ponteiro chamado nó? >> Este é - não. Este é um ponteiro para algo do tipo de nó.

842
01:06:28,480 --> 01:06:32,540
É um ponteiro para uma estrutura de nó. >> Ah, ok.

843
01:06:32,540 --> 01:06:36,870
Diagrama sobre o código, esquerda à direita.

844
01:06:36,870 --> 01:06:42,190
Podemos defini-lo como nulo, o que é uma boa maneira de começar.

845
01:06:42,190 --> 01:06:49,850
Quando você diagrama, você quer escrevê-lo como nulo ou você colocar uma linha através dele assim.

846
01:06:49,850 --> 01:06:53,910
>> Uma das maneiras mais fáceis de trabalhar com listas,

847
01:06:53,910 --> 01:06:57,430
e pedimos que tanto prepend e anexar para ver as diferenças entre os dois,

848
01:06:57,430 --> 01:07:01,320
prepending mas é definitivamente mais fácil.

849
01:07:01,320 --> 01:07:05,790
Quando você precede, este é o lugar onde você - quando você prepend (7),

850
01:07:05,790 --> 01:07:10,050
você vai criar a estrutura do nó

851
01:07:10,050 --> 01:07:13,870
e você definir primeiro a apontar para ele, porque agora, já que ele prefixado,

852
01:07:13,870 --> 01:07:17,240
ele vai estar no início da lista.

853
01:07:17,240 --> 01:07:22,540
Se prepend (3), que cria um outro nó, mas agora 3 vem antes do 7.

854
01:07:22,540 --> 01:07:31,130
Então estamos essencialmente empurrando as coisas para a nossa lista.

855
01:07:31,130 --> 01:07:34,720
Agora, você pode ver que prepend, às vezes as pessoas chamam de empurrar,

856
01:07:34,720 --> 01:07:39,600
porque você está empurrando um novo elemento em sua lista.

857
01:07:39,600 --> 01:07:43,270
Também é fácil de apagar na frente de uma lista.

858
01:07:43,270 --> 01:07:45,650
Então, as pessoas, muitas vezes chamada de pop.

859
01:07:45,650 --> 01:07:52,200
E dessa maneira, você pode emular uma pilha usando uma lista ligada.

860
01:07:52,200 --> 01:07:57,880
Gritos. Desculpe, agora estamos entrando em acréscimo. Então aqui nós prefixado (7), agora nós prepend (3).

861
01:07:57,880 --> 01:08:02,600
Se prefixado algo mais para esta lista, se prefixado (4),

862
01:08:02,600 --> 01:08:06,540
então temos 4 e depois 3 e depois 7.

863
01:08:06,540 --> 01:08:14,220
Então nós poderia pop e remover 4, remove 3, remova 7.

864
01:08:14,220 --> 01:08:16,500
Muitas vezes, a forma mais intuitiva de pensar sobre isso é com acréscimo.

865
01:08:16,500 --> 01:08:20,310
Então eu diagramado para fora o que seria parecido com acrescentar aqui.

866
01:08:20,310 --> 01:08:23,380
Aqui, anexado (7) não parece ser diferente

867
01:08:23,380 --> 01:08:25,160
porque há apenas um elemento na lista.

868
01:08:25,160 --> 01:08:28,620
E anexando (3) coloca-lo no final.

869
01:08:28,620 --> 01:08:31,020
Talvez você pode ver agora o truque com append

870
01:08:31,020 --> 01:08:36,600
é que desde que nós só sabemos onde o início da lista é,

871
01:08:36,600 --> 01:08:39,450
para anexar a uma lista que você tem que andar todo o caminho através da lista

872
01:08:39,450 --> 01:08:46,500
para chegar ao fim, parar, em seguida, construir o nó e tudo dólar baixo.

873
01:08:46,500 --> 01:08:50,590
Ligue todas as coisas para cima.

874
01:08:50,590 --> 01:08:55,170
Assim, com prepend, como acabamos rasgou esta muito rapidamente,

875
01:08:55,170 --> 01:08:58,170
quando você precede a uma lista, é bastante simples.

876
01:08:58,170 --> 01:09:02,960
>> Você faz o seu novo nó, envolvem algum alocação dinâmica de memória.

877
01:09:02,960 --> 01:09:09,830
Então aqui nós estamos fazendo um struct nó usando malloc.

878
01:09:09,830 --> 01:09:14,710
Então malloc estamos usando porque isso vai reservar memória para nós para mais tarde

879
01:09:14,710 --> 01:09:20,350
porque nós não queremos isso - nós queremos essa memória a persistir por um longo tempo.

880
01:09:20,350 --> 01:09:25,350
E nós temos um ponteiro para o espaço na memória que nós apenas alocado.

881
01:09:25,350 --> 01:09:29,260
Usamos tamanho de nó, não somar os campos.

882
01:09:29,260 --> 01:09:31,899
Nós não gerar manualmente o número de bytes,

883
01:09:31,899 --> 01:09:39,750
em vez disso, use sizeof para que saibamos que estamos recebendo um número adequado de bytes.

884
01:09:39,750 --> 01:09:43,660
Temos certeza de que o nosso para testar chamada malloc conseguiu.

885
01:09:43,660 --> 01:09:47,939
Isso é algo que você quer fazer em geral.

886
01:09:47,939 --> 01:09:52,590
Em máquinas modernas, a falta de memória não é algo que é fácil

887
01:09:52,590 --> 01:09:56,610
a menos que você está a atribuição de uma tonelada de coisas e fazer uma lista enorme,

888
01:09:56,610 --> 01:10:02,220
mas se você está construindo coisas para, digamos, como um iPhone ou um Android,

889
01:10:02,220 --> 01:10:05,230
você tem recursos limitados de memória, especialmente se você está fazendo algo intenso.

890
01:10:05,230 --> 01:10:08,300
Portanto, é bom para entrar em prática.

891
01:10:08,300 --> 01:10:10,510
>> Repare que eu usei algumas funções diferentes aqui

892
01:10:10,510 --> 01:10:12,880
que você já viu que são uma espécie de novo.

893
01:10:12,880 --> 01:10:15,870
Então fprintf é como printf

894
01:10:15,870 --> 01:10:21,320
exceto seu primeiro argumento é o fluxo para o qual você deseja imprimir.

895
01:10:21,320 --> 01:10:23,900
Neste caso, queremos imprimir para a cadeia de erro padrão

896
01:10:23,900 --> 01:10:29,410
que é diferente do padrão outstream.

897
01:10:29,410 --> 01:10:31,620
Por padrão, ele mostra-se no mesmo lugar.

898
01:10:31,620 --> 01:10:34,600
Ela também imprime ao terminal, mas você pode -

899
01:10:34,600 --> 01:10:38,790
usando os comandos que você aprendeu sobre as técnicas de redirecionamento,

900
01:10:38,790 --> 01:10:42,290
que você aprendeu na vídeo de Tommy por conjunto de problemas 4, você pode direcioná-lo

901
01:10:42,290 --> 01:10:47,900
para diferentes áreas e, depois, sair, aqui, sai do seu programa.

902
01:10:47,900 --> 01:10:50,440
É essencialmente como voltar da principal,

903
01:10:50,440 --> 01:10:53,600
exceto que nós usamos, porque aqui saída de retorno não vai fazer nada.

904
01:10:53,600 --> 01:10:57,140
Nós não estamos no principal, para retorno não sair do programa como nós queremos.

905
01:10:57,140 --> 01:11:03,020
Então, nós usamos a função de saída e dar-lhe um código de erro.

906
01:11:03,020 --> 01:11:11,890
Então, aqui vamos definir campo o novo nó de valor, o seu campo i igual a i, e então conectá-lo.

907
01:11:11,890 --> 01:11:15,530
Montamos ponteiro seguinte, o novo nó para que ele aponte para o primeiro,

908
01:11:15,530 --> 01:11:20,460
e depois na primeira vai agora apontar para o novo nó.

909
01:11:20,460 --> 01:11:25,120
Estas primeiras linhas de código, estamos realmente construindo o novo nó.

910
01:11:25,120 --> 01:11:27,280
Nem as duas últimas linhas desta função, mas os primeiros.

911
01:11:27,280 --> 01:11:30,290
Você pode realmente sair em uma função, em uma função auxiliar.

912
01:11:30,290 --> 01:11:32,560
Que muitas vezes é o que eu faço é, eu retirá-lo em uma função,

913
01:11:32,560 --> 01:11:36,040
Eu chamo-lhe algo como nó de construção,

914
01:11:36,040 --> 01:11:40,410
e que mantém a função prepend muito pequena, com apenas 3 linhas de então.

915
01:11:40,410 --> 01:11:48,710
Eu faço uma chamada para o meu função do nó de construção, e então eu tudo fio para cima.

916
01:11:48,710 --> 01:11:51,970
>> A última coisa que eu quero te mostrar,

917
01:11:51,970 --> 01:11:54,030
e eu vou deixar você fazer append e tudo o que em seu próprio país,

918
01:11:54,030 --> 01:11:57,500
é como iterar sobre uma lista.

919
01:11:57,500 --> 01:12:00,780
Há um monte de maneiras diferentes de abordar uma lista.

920
01:12:00,780 --> 01:12:03,140
Neste caso, vamos encontrar o comprimento de uma lista.

921
01:12:03,140 --> 01:12:06,570
Então, vamos começar com comprimento = 0.

922
01:12:06,570 --> 01:12:11,580
Isto é muito semelhante à escrita strlen para uma cadeia.

923
01:12:11,580 --> 01:12:17,780
Isso é o que eu quero mostrar para você, este laço for bem aqui.

924
01:12:17,780 --> 01:12:23,530
Parece meio funk, não é o habitual int i = 0, i <qualquer que seja, i + +.

925
01:12:23,530 --> 01:12:34,920
Em vez disso, está a inicializar a variável n ser o início da lista.

926
01:12:34,920 --> 01:12:40,620
E então, quando a nossa variável iterator não é nulo, nós continuar.

927
01:12:40,620 --> 01:12:46,340
Isto porque, por convenção, o fim da nossa lista será nulo.

928
01:12:46,340 --> 01:12:48,770
E, em seguida, para incrementar, em vez de fazer + +,

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 você preencher as lacunas aqui porque estamos fora do tempo.

931
01:13:00,410 --> 01:13:09,300
Mas manter isso em mente como você trabalhar em Série de Exercícios seus spellr.

932
01:13:09,300 --> 01:13:11,650
Listas ligadas, se você está implementando uma tabela hash,

933
01:13:11,650 --> 01:13:14,010
vai certamente ser muito útil.

934
01:13:14,010 --> 01:13:21,780
E, tendo esta expressão para looping sobre as coisas vão tornar a vida muito mais fácil, eu espero.

935
01:13:21,780 --> 01:13:25,910
Qualquer dúvida, rapidamente?

936
01:13:25,910 --> 01:13:28,920
[Sam] Será que você enviar o sll concluído e sc?

937
01:13:28,920 --> 01:13:38,360
[Hardison] Yeah. Eu vou enviar lâminas concluídas e pilha sll concluído e queue.cs.

938
01:13:38,360 --> 01:13:41,360
[CS50.TV]