1
00:00:00,000 --> 00:00:02,832
>> [Música tocando]

2
00:00:02,832 --> 00:00:05,670

3
00:00:05,670 --> 00:00:08,560
>> Doug LLOYD: OK, entón a
Neste punto do curso,

4
00:00:08,560 --> 00:00:15,300
nós Cubrimos unha morea de conceptos básicos de C.
Sabemos moito sobre variables, arrays,

5
00:00:15,300 --> 00:00:17,610
punteiros, todas esas cousas boas.

6
00:00:17,610 --> 00:00:21,610
Aqueles son todo tipo de construción
para ver como os fundamentos,

7
00:00:21,610 --> 00:00:23,880
pero podemos facer máis, non?

8
00:00:23,880 --> 00:00:27,930
Podemos combinar as cousas
en conxunto de formas interesantes.

9
00:00:27,930 --> 00:00:31,010
>> E así imos facelo, imos comezar
a ramifican-se que C nos dá,

10
00:00:31,010 --> 00:00:35,270
e comezar a crear os nosos propios datos
Usando estas estruturas edificio

11
00:00:35,270 --> 00:00:40,590
bloques xuntos para facer algo
realmente valioso, útil.

12
00:00:40,590 --> 00:00:43,420
Unha forma de facelo é
para falar coleccións.

13
00:00:43,420 --> 00:00:48,360
Entón, por agora tivemos un tipo de datos
estrutura para representar as coleccións

14
00:00:48,360 --> 00:00:51,030
quere valores, valores semellantes.

15
00:00:51,030 --> 00:00:52,350
Iso sería unha matriz.

16
00:00:52,350 --> 00:00:57,020
Temos coleccións de enteiros, ou
coleccións de personaxes e así por diante.

17
00:00:57,020 --> 00:01:00,890
>> Estruturas tamén son un tipo de datos
estrutura para a obtención de información,

18
00:01:00,890 --> 00:01:03,220
pero non é para recoller como valores.

19
00:01:03,220 --> 00:01:08,090
Xeralmente mestura diferentes tipos de datos
xuntos dentro dunha única caixa.

20
00:01:08,090 --> 00:01:10,750
Pero non é en si
usado para encadear

21
00:01:10,750 --> 00:01:16,920
ou conectar xuntos semellante
elementos, como unha matriz.

22
00:01:16,920 --> 00:01:20,960
Arrays son grandes para
elemento de mirar para arriba, pero recordo

23
00:01:20,960 --> 00:01:24,262
que é moi difícil
para introducir unha matriz,

24
00:01:24,262 --> 00:01:26,470
a non ser que estamos introducindo no
o final desa matriz.

25
00:01:26,470 --> 00:01:29,730
>> E o mellor exemplo que eu teño
para iso é a ordenación por inserción.

26
00:01:29,730 --> 00:01:31,650
Se ben se lembran o noso vídeo
na ordenación por inserción,

27
00:01:31,650 --> 00:01:34,110
había unha morea de
gasto parte en ter

28
00:01:34,110 --> 00:01:37,970
para incorporarse elementos, e transferir-los
fóra do camiño para caber algo

29
00:01:37,970 --> 00:01:41,290
no medio da súa matriz.

30
00:01:41,290 --> 00:01:44,690
Arrays tamén sofren doutro
problema, que é a inflexibilidade.

31
00:01:44,690 --> 00:01:47,150
Cando declaramos unha matriz,
obtemos un tiro nel.

32
00:01:47,150 --> 00:01:49,790
Comezamos a dicir, quero
este moitos elementos.

33
00:01:49,790 --> 00:01:51,940
Pode ser de 100, pode
ser 1000, pode

34
00:01:51,940 --> 00:01:55,930
ser X, onde X é un número que o usuario
deunos nun ventá de consola ou no

35
00:01:55,930 --> 00:01:56,630
liña.

36
00:01:56,630 --> 00:01:59,905
>> Pero nós só temos unha oportunidade para el, nós
non pode, entón, dicir oh, de feito eu

37
00:01:59,905 --> 00:02:04,360
precisaba de 101, ou eu precisaba x máis 20.

38
00:02:04,360 --> 00:02:07,910
Demasiado tarde, que xa declarou o
array, e se queremos obter 101 ou x

39
00:02:07,910 --> 00:02:12,050
engade 20, temos a declarar
unha matriz totalmente diferente,

40
00:02:12,050 --> 00:02:15,540
copiar todos os elementos da matriz
sobre, e entón temos o suficiente.

41
00:02:15,540 --> 00:02:19,880
E se estamos errados de novo, o que
se realmente necesitamos 102, ou x máis 40,

42
00:02:19,880 --> 00:02:21,970
temos que facelo de novo.

43
00:02:21,970 --> 00:02:26,250
Entón, eles están moi inflexíbel
para cambiar o tamaño os nosos datos,

44
00:02:26,250 --> 00:02:29,360
pero se combinan algúns
dos principios básicos que xa

45
00:02:29,360 --> 00:02:33,230
Aprende sobre punteiros e estruturas,
en especial a través de memoria dinámica

46
00:02:33,230 --> 00:02:36,180
distribución con malloc, nós
pode pór estes anacos xuntos

47
00:02:36,180 --> 00:02:40,960
para crear un novo dado un structure--
illadamente lista poderiamos dizer-- conectado

48
00:02:40,960 --> 00:02:45,400
que nos permite crecer e
encoller unha colección de valores

49
00:02:45,400 --> 00:02:48,800
e non teremos ningún espazo desperdiçado.

50
00:02:48,800 --> 00:02:53,320
>> Entón, de novo, chamamos esa idea,
esa noción, unha lista ligada.

51
00:02:53,320 --> 00:02:56,320
En particular, neste video que estamos
falando lista vinculada illadamente,

52
00:02:56,320 --> 00:02:59,185
e, a continuación, outro vídeo imos falar
listas sobre dobremente ligadas, que

53
00:02:59,185 --> 00:03:01,560
é só unha variación sobre un tema aquí.

54
00:03:01,560 --> 00:03:05,200
Pero unha lista vinculada illadamente
está composto por nós,

55
00:03:05,200 --> 00:03:08,559
nós só ser un term-- abstracto
é só algo que eu estou chamando

56
00:03:08,559 --> 00:03:10,350
que é unha especie de
estrutura, basicamente, eu son?

57
00:03:10,350 --> 00:03:16,190
Só tes que ir a chamalo dun node-- e este
nó ten dous membros, ou dous campos.

58
00:03:16,190 --> 00:03:20,300
Ten de datos, xeralmente un
enteiro, un personaxe float,

59
00:03:20,300 --> 00:03:23,790
ou podería ser algún outro tipo de datos
que teña definido cun tipo def.

60
00:03:23,790 --> 00:03:29,290
E que contén unha ligazón para
outro nó do mesmo tipo.

61
00:03:29,290 --> 00:03:34,710
>> Polo tanto, temos dúas cousas dentro
ese nó, de datos e un punteiro

62
00:03:34,710 --> 00:03:36,380
a outro nodo.

63
00:03:36,380 --> 00:03:39,370
E se comezar a ver
iso, pode pensar sobre iso

64
00:03:39,370 --> 00:03:42,280
como unha cadea de nós que
están ligados entre si.

65
00:03:42,280 --> 00:03:45,070
Temos o primeiro nodo, el
contén os datos, e un punteiro

66
00:03:45,070 --> 00:03:49,110
para o segundo no, a cal contén
de datos, e un punteiro para o terceiro nó.

67
00:03:49,110 --> 00:03:52,940
E é por iso que chamamos
lista ligada, están unidos entre si.

68
00:03:52,940 --> 00:03:56,070
>> O que fai este especial
estrutura de nó parece?

69
00:03:56,070 --> 00:04:01,120
Ben, se se lembra do noso vídeo sobre
definir tipos personalizados, co tipo de definición,

70
00:04:01,120 --> 00:04:05,400
podemos definir unha structure-- e
escriba definir unha estrutura como esta.

71
00:04:05,400 --> 00:04:11,240
tyepdef struct sllist, e entón eu son
usando a palabra valor arbitrariamente aquí

72
00:04:11,240 --> 00:04:13,891
para indicar calquera tipo de datos realmente.

73
00:04:13,891 --> 00:04:16,890
Podería pasar un enteiro ou float,
pode que o que quere.

74
00:04:16,890 --> 00:04:19,389
Non hai restricións para só
enteiros, ou algo así.

75
00:04:19,389 --> 00:04:22,790
Así, o valor é só unha arbitraria
Tipo de datos e, a continuación, un punteiro

76
00:04:22,790 --> 00:04:26,310
a outro nodo do mesmo tipo.

77
00:04:26,310 --> 00:04:29,690
>> Agora, hai un pouco de captura
aquí cunha estrutura que define

78
00:04:29,690 --> 00:04:33,030
cando é unha estrutura auto referencial.

79
00:04:33,030 --> 00:04:35,340
Eu teño que ter un temporal
nomear a miña estrutura.

80
00:04:35,340 --> 00:04:37,640
Ao final do día,
claramente queren chamalo

81
00:04:37,640 --> 00:04:43,030
SLL nó, que é en definitiva, o novo
nomear parte da miña definición de tipo,

82
00:04:43,030 --> 00:04:47,450
pero eu non podo usar nó SLL
no medio deste.

83
00:04:47,450 --> 00:04:51,430
A razón de ser, eu non teño
creou un tipo chamado nó SLL

84
00:04:51,430 --> 00:04:55,200
ata que eu bati ese punto final aquí.

85
00:04:55,200 --> 00:04:59,720
Até aquel momento, eu teño que ter
outra forma de referirse a este tipo de datos.

86
00:04:59,720 --> 00:05:02,440
>> E esta é unha auto-
tipo de datos referencial.

87
00:05:02,440 --> 00:05:06,314
; S un tipo de datos
que contén unha estrutura de datos,

88
00:05:06,314 --> 00:05:08,480
e un punteiro a outra
estrutura do mesmo tipo.

89
00:05:08,480 --> 00:05:11,750
Entón eu teño poder referirse a
este tipo de datos, polo menos temporalmente,

90
00:05:11,750 --> 00:05:14,910
así dándolle un temporal
nome struct sllist

91
00:05:14,910 --> 00:05:18,540
permíteme, a continuación, dicir que eu quero un
punteiro a outro sllist struct,

92
00:05:18,540 --> 00:05:24,690
unha estrela struct sllist, e, a continuación,
despois de que eu feitas as definición,

93
00:05:24,690 --> 00:05:27,220
Agora podo chamar este tipo de un nó de SLL.

94
00:05:27,220 --> 00:05:30,520
>> É por iso que ve que hai
un nome temporal aquí,

95
00:05:30,520 --> 00:05:31,879
pero un nome permanente aquí.

96
00:05:31,879 --> 00:05:33,920
Ás veces podes ver
definicións de estrutura,

97
00:05:33,920 --> 00:05:36,570
por exemplo, que non son
auto referencial, que

98
00:05:36,570 --> 00:05:39,390
non ten un nome especificador aquí.

99
00:05:39,390 --> 00:05:43,040
El só diría typedef struct,
abrir chaveta e, a continuación, define-lo.

100
00:05:43,040 --> 00:05:45,620
Pero se é struct é auto-
referencial, como este é,

101
00:05:45,620 --> 00:05:49,010
precisa especificar un
nome do tipo temporal.

102
00:05:49,010 --> 00:05:51,310
Pero, ao final, agora
que fixemos iso,

103
00:05:51,310 --> 00:05:53,620
podemos só referirse a
eses nós, estas unidades,

104
00:05:53,620 --> 00:05:57,900
como nodos SLL con fins
do resto deste vídeo.

105
00:05:57,900 --> 00:06:00,900
>> Todo ben, entón sabemos como
crear un nó lista ligada.

106
00:06:00,900 --> 00:06:03,240
Sabemos como configurar
un nó de lista ligada.

107
00:06:03,240 --> 00:06:06,670
Agora, se nós estamos indo para comezar
usando os para recoller información,

108
00:06:06,670 --> 00:06:10,360
hai un par de operacións que
necesitan entender e traballar con el.

109
00:06:10,360 --> 00:06:12,860
Necesitamos saber como crear
unha lista ligada fóra do ar.

110
00:06:12,860 --> 00:06:14,901
Se non hai ningunha lista xa,
queremos comezar un.

111
00:06:14,901 --> 00:06:16,960
Entón, necesitamos ser capaces
para crear unha lista ligada,

112
00:06:16,960 --> 00:06:19,130
necesitamos probablemente buscar
a través da lista de ligazóns

113
00:06:19,130 --> 00:06:21,830
para atopar un elemento que estamos buscando.

114
00:06:21,830 --> 00:06:24,430
Necesitamos ser capaces de inserir
cousas novas para a lista,

115
00:06:24,430 --> 00:06:25,930
queremos que a nosa lista para poder crecer.

116
00:06:25,930 --> 00:06:28,638
E do mesmo xeito, queremos ser capaces
para borrar as cousas da nosa lista,

117
00:06:28,638 --> 00:06:30,250
queremos que a nosa lista para poder encoller.

118
00:06:30,250 --> 00:06:32,160
E ao final da nosa
programas, especialmente

119
00:06:32,160 --> 00:06:34,550
se recorda que somos
reservar dinamicamente a memoria

120
00:06:34,550 --> 00:06:38,337
para construír estas listas normalmente,
queremos liberar toda a memoria que

121
00:06:38,337 --> 00:06:39,670
cando terminarmos de traballar con el.

122
00:06:39,670 --> 00:06:44,627
E por iso temos que ser capaces de borrar un
Toda lista ligada nunha rusga falla.

123
00:06:44,627 --> 00:06:46,460
Entón, imos pasar por
Algunhas destas tarefas

124
00:06:46,460 --> 00:06:51,192
e como podemos visualiza-los,
falando en código pseudocódigo especificamente.

125
00:06:51,192 --> 00:06:53,150
Por iso, queremos crear unha
lista ligada, entón quizais nós

126
00:06:53,150 --> 00:06:56,480
quere definir unha función
con este prototipo.

127
00:06:56,480 --> 00:07:01,690
SLL estrela no, crear, e eu estou pasando
nun argumento, algúns datos arbitrarios

128
00:07:01,690 --> 00:07:05,530
escriba de novo, de calquera tipo de datos arbitrario.

129
00:07:05,530 --> 00:07:10,482
Pero eu estou returning-- esta función debe
volver para min un punteiro, a un illadamente

130
00:07:10,482 --> 00:07:11,190
nó lista ligada.

131
00:07:11,190 --> 00:07:14,050
Unha vez máis, estamos intentando crear
unha lista ligada fóra do ar,

132
00:07:14,050 --> 00:07:17,900
entón eu teño un punteiro para
esa lista cando rematar.

133
00:07:17,900 --> 00:07:19,420
>> Entón, cales son os pasos implicadas aquí?

134
00:07:19,420 --> 00:07:20,960
Ben, o primeiro que eu son
vai facer é dinámicamente

135
00:07:20,960 --> 00:07:22,550
reservar espazo para un novo nodo.

136
00:07:22,550 --> 00:07:26,689
Unha vez máis, estamos creando-o para fora da fina
aire, polo que necesitamos espazo malloc para el.

137
00:07:26,689 --> 00:07:28,480
E, por suposto, inmediatamente
despois que malloc,

138
00:07:28,480 --> 00:07:31,692
sempre asegúrese de que o noso
pointer-- non volver nulo.

139
00:07:31,692 --> 00:07:33,650
Porque se nós intentamos e
deferencia un punteiro nulo,

140
00:07:33,650 --> 00:07:36,190
imos sufrir un
segfault e nós non queremos iso.

141
00:07:36,190 --> 00:07:39,510
>> Entón, nós queremos encher o campo,
queremos iniciar o campo de valor

142
00:07:39,510 --> 00:07:41,690
e iniciar o próximo campo.

143
00:07:41,690 --> 00:07:45,450
E entón nós queremos a--, finalmente, como o
función prototipo indicates-- queremos

144
00:07:45,450 --> 00:07:49,940
para voltar un punteiro para un nó SLL.

145
00:07:49,940 --> 00:07:51,710
Entón, o que facer este ollar como visualmente?

146
00:07:51,710 --> 00:07:55,230
Ben, primeiro imos dinamicamente
reservar espazo para un novo nodo SLL,

147
00:07:55,230 --> 00:07:58,320
por iso, que é malloc--
unha representación visual

148
00:07:58,320 --> 00:08:00,020
do nodo que acabamos de crear.

149
00:08:00,020 --> 00:08:02,757
E nós comproba se
non é null-- neste caso

150
00:08:02,757 --> 00:08:04,840
a imaxe non tería
aparecido se era nulo,

151
00:08:04,840 --> 00:08:07,298
teriamos quedar sen memoria,
polo que é bo para ir alí.

152
00:08:07,298 --> 00:08:10,200
Entón, agora estamos a paso C,
iniciar o campo nodos valor.

153
00:08:10,200 --> 00:08:12,280
Ben, con base nesa función
chamar que está a usar aquí,

154
00:08:12,280 --> 00:08:16,700
parece que quero pasar en 6,
entón eu vou 6 no campo de valor.

155
00:08:16,700 --> 00:08:18,865
Agora, iniciar o próximo campo.

156
00:08:18,865 --> 00:08:21,640
Ben, o que eu vou facer alí,
non hai nada ao lado, á dereita,

157
00:08:21,640 --> 00:08:23,600
esta é a única cousa na lista.

158
00:08:23,600 --> 00:08:27,206
Entón, cal é a seguinte cousa na lista?

159
00:08:27,206 --> 00:08:29,660
>> Non debe apuntar para calquera cousa, certo.

160
00:08:29,660 --> 00:08:33,600
Non hai máis nada alí, entón o que é
o concepto sabemos de que se nothing--

161
00:08:33,600 --> 00:08:35,638
punteiros para nada?

162
00:08:35,638 --> 00:08:37,929
Debe ser posible queremos
para poñer un punteiro nulo alí,

163
00:08:37,929 --> 00:08:40,178
e eu vou representar o nulo
punteiro como só unha caixa vermella,

164
00:08:40,178 --> 00:08:41,559
non podemos ir máis lonxe.

165
00:08:41,559 --> 00:08:44,430
Como veremos un pouco máis tarde,
imos ter finalmente cadeas

166
00:08:44,430 --> 00:08:46,330
de frechas que ligan
destes nós, en conxunto

167
00:08:46,330 --> 00:08:48,480
pero cando bate a
caixa vermella, que é nula,

168
00:08:48,480 --> 00:08:51,150
non podemos ir máis lonxe,
ese é o fin da lista.

169
00:08:51,150 --> 00:08:53,960
>> E, finalmente, nós só queremos
voltar un punteiro para ese nó.

170
00:08:53,960 --> 00:08:56,160
Entón, imos chamalo de novo,
e volverá novo

171
00:08:56,160 --> 00:08:59,370
de xeito que se pode empregar en
calquera función creou.

172
00:08:59,370 --> 00:09:03,100
Entón alí imos nós, Creamos un illadamente
nó lista ligada fóra do ar,

173
00:09:03,100 --> 00:09:05,920
e agora temos unha lista podemos traballar con.

174
00:09:05,920 --> 00:09:08,260
>> Agora, imos dicir que xa
ten unha gran cadea,

175
00:09:08,260 --> 00:09:09,800
e queremos atopar algo nel.

176
00:09:09,800 --> 00:09:12,716
E queremos unha función que está a suceder
para volver verdadeiro ou falso, dependendo

177
00:09:12,716 --> 00:09:15,840
sobre se existe un valor da lista.

178
00:09:15,840 --> 00:09:18,160
Un prototipo de función, ou
declaración para esa función,

179
00:09:18,160 --> 00:09:23,320
pode parecer isto-- bool atopar, e
entón queremos pasar en dous argumentos.

180
00:09:23,320 --> 00:09:26,996
>> O primeiro, é un punteiro para o
primeiro elemento da lista ligada.

181
00:09:26,996 --> 00:09:29,620
Isto é realmente algo que vai
sempre quere seguir,

182
00:09:29,620 --> 00:09:33,110
e, de feito, pode ser algo que
vostede mesmo poñer nunha variable global.

183
00:09:33,110 --> 00:09:35,360
Despois de crear unha lista,
sempre, sempre

184
00:09:35,360 --> 00:09:38,990
quere manter o control do propio
primeiro elemento da lista.

185
00:09:38,990 --> 00:09:43,690
Desta forma, pode referirse a todos os outros
elementos por só seguindo a cadea,

186
00:09:43,690 --> 00:09:47,300
sen ter que manter punteiros
intacta para cada elemento.

187
00:09:47,300 --> 00:09:50,920
Só ten manter o control do primeiro
un, se eles están todos encadeados.

188
00:09:50,920 --> 00:09:52,460
>> E, a continuación, a segunda cousa
estamos pasando de novo

189
00:09:52,460 --> 00:09:54,376
é arbitrariamente some--
calquera que sexa o tipo de datos que estamos

190
00:09:54,376 --> 00:09:59,640
buscando existe dentro
espero que un dos nós da lista.

191
00:09:59,640 --> 00:10:00,980
Entón, cales son os pasos?

192
00:10:00,980 --> 00:10:04,250
Ben, o primeiro que facemos é
creamos un punteiro transversal

193
00:10:04,250 --> 00:10:06,015
apuntando á cabeza listas.

194
00:10:06,015 --> 00:10:08,890
Ben, por que facemos iso, nós xa
ter un punteiro na cabeza listas,

195
00:10:08,890 --> 00:10:10,974
por que non imos só mover dun en torno a?

196
00:10:10,974 --> 00:10:13,140
Ben, como dixen,
que é realmente importante para nós

197
00:10:13,140 --> 00:10:17,580
manter sempre o control do
primeiro elemento da lista.

198
00:10:17,580 --> 00:10:21,270
E por iso é realmente mellor
para crear un duplicado de que,

199
00:10:21,270 --> 00:10:25,350
e usar isto para moverse, polo que nunca
accidentalmente afastarse, ou sempre

200
00:10:25,350 --> 00:10:30,430
ter un punteiro nalgún punto que é
dereito sobre o primeiro elemento da lista.

201
00:10:30,430 --> 00:10:33,290
Polo tanto, é mellor crear un
un segundo que usan para mover.

202
00:10:33,290 --> 00:10:35,877
>> A continuación, pode comparar se
O campo de valor en que nodo

203
00:10:35,877 --> 00:10:38,960
é o que estamos a buscar, e se é
Non, só pasar ao seguinte nodo.

204
00:10:38,960 --> 00:10:41,040
E nós continuar facendo iso
máis, e máis, e máis,

205
00:10:41,040 --> 00:10:44,811
ata que quere atopar
o elemento, ou se loita

206
00:10:44,811 --> 00:10:47,310
null-- chegamos á final
da lista e non está alí.

207
00:10:47,310 --> 00:10:50,540
Este debe esperamos tocar unha campá
para ti como só busca lineal,

208
00:10:50,540 --> 00:10:54,430
estamos só réplica-lo
unha estrutura de lista vinculada illadamente

209
00:10:54,430 --> 00:10:56,280
en vez de usar unha matriz para facelo.

210
00:10:56,280 --> 00:10:58,210
>> Entón aquí está un exemplo de
unha lista vinculada illadamente.

211
00:10:58,210 --> 00:11:00,043
Este consiste
cinco nós, e temos

212
00:11:00,043 --> 00:11:04,330
un punteiro para a cabeza do
lista, que se chama lista.

213
00:11:04,330 --> 00:11:07,385
O primeiro que quero facer é
de novo, crear ese punteiro travesía.

214
00:11:07,385 --> 00:11:09,760
Polo tanto, temos agora dous punteiros
que ligan con o mesmo.

215
00:11:09,760 --> 00:11:15,025
>> Agora, observe aquí tamén, eu non fixen
ten que malloc calquera espazo para Trav.

216
00:11:15,025 --> 00:11:18,970
Eu non dixen trav igual malloc
algo, ese nó xa existe,

217
00:11:18,970 --> 00:11:21,160
ese espazo na memoria xa existe.

218
00:11:21,160 --> 00:11:24,290
Entón, todo o que eu estou facendo realmente é
creando un outro punteiro para el.

219
00:11:24,290 --> 00:11:28,210
Non estou mallocing un adicional
espazo, só ten agora dous punteiros

220
00:11:28,210 --> 00:11:31,370
apuntando para o mesmo.

221
00:11:31,370 --> 00:11:33,710
>> Entón é 2 o que estou buscando?

222
00:11:33,710 --> 00:11:37,220
Ben, non, en vez eu son
vai pasar á seguinte.

223
00:11:37,220 --> 00:11:41,740
Entón, basicamente, eu diría,
trav igual trav seguinte.

224
00:11:41,740 --> 00:11:43,630
3 é o que eu estou buscando, non.

225
00:11:43,630 --> 00:11:45,780
Entón eu continuar a ir
través, ata que finalmente

226
00:11:45,780 --> 00:11:48,690
chegar a 6, que é o que estou buscando
para con base na chamada de función

227
00:11:48,690 --> 00:11:51,600
Teño na parte superior
alí, e así que eu son feito.

228
00:11:51,600 --> 00:11:54,150
>> Agora, e se o elemento que eu son
buscar non está na lista,

229
00:11:54,150 --> 00:11:55,510
é que aínda vai funcionar?

230
00:11:55,510 --> 00:11:57,120
Ben, teña en conta que a lista
aquí é sutilmente diferente,

231
00:11:57,120 --> 00:11:59,410
e esta é outra cousa que é
importante con listas ligadas,

232
00:11:59,410 --> 00:12:01,780
non ten que preservar
los en calquera orde particular.

233
00:12:01,780 --> 00:12:05,390
Vostede pode, se quere, pero
xa debe ter notado

234
00:12:05,390 --> 00:12:09,310
que non estamos mantendo o control de
o elemento de número estamos.

235
00:12:09,310 --> 00:12:13,150
>> E iso é un tipo de comercio que
ten con lista ligada versos arrays,

236
00:12:13,150 --> 00:12:15,300
é que non temos
acceso aleatorio máis.

237
00:12:15,300 --> 00:12:18,150
Non podemos só dicir, quero
para ir ao elemento 0,

238
00:12:18,150 --> 00:12:21,410
ou o elemento sexto da miña matriz,
que podo facer nunha matriz.

239
00:12:21,410 --> 00:12:25,080
Non podo dicir que eu quero ir ao
Elemento 0, ou o elemento 6,

240
00:12:25,080 --> 00:12:30,360
ou o elemento 25 da miña lista ligada,
non hai ningún índice asociado con eles.

241
00:12:30,360 --> 00:12:33,660
E por iso realmente non importa
preservarse nosa lista en orde.

242
00:12:33,660 --> 00:12:36,080
Se quere vostede
certamente poden, pero hai

243
00:12:36,080 --> 00:12:38,567
ningunha razón para que precisan
ser preservados en calquera orde.

244
00:12:38,567 --> 00:12:40,400
Entón, de novo, imos tratar
6 atopar nesta lista.

245
00:12:40,400 --> 00:12:43,200
Ben, imos comezar con
comezando, non atopamos 6,

246
00:12:43,200 --> 00:12:47,690
e entón non seguir a atopar
6, ata que, finalmente, chegar a aquí.

247
00:12:47,690 --> 00:12:52,790
Tan seguro puntos agora trav para o no
contendo 8, e seis non está alí.

248
00:12:52,790 --> 00:12:55,250
>> Así, o seguinte paso sería
para ir ao seguinte punteiro,

249
00:12:55,250 --> 00:12:57,440
así din trav igual trav seguinte.

250
00:12:57,440 --> 00:13:00,750
Ben, Trav seguinte, indicada pola
a caixa vermella alí, é nulo.

251
00:13:00,750 --> 00:13:03,020
Polo tanto, non hai ningún outro lugar para
ir, e por iso neste momento

252
00:13:03,020 --> 00:13:06,120
podemos concluír que chegamos
o fin da lista ligada,

253
00:13:06,120 --> 00:13:07,190
e 6 non está alí.

254
00:13:07,190 --> 00:13:10,980
E iso sería devolto
false neste caso.

255
00:13:10,980 --> 00:13:14,540
>> OK, como é que imos introducir unha nova
nó na lista vinculada?

256
00:13:14,540 --> 00:13:17,310
Entón, nós temos sido capaces de crear
unha lista vinculada da nada,

257
00:13:17,310 --> 00:13:19,370
pero probablemente quere
construír unha cadea e non

258
00:13:19,370 --> 00:13:22,620
crear un grupo de listas distintas.

259
00:13:22,620 --> 00:13:25,700
Queremos ter unha lista que
ten unha morea de nós na mesma,

260
00:13:25,700 --> 00:13:28,040
non unha morea de listas cun único nodo.

261
00:13:28,040 --> 00:13:31,260
Polo tanto, non podemos só seguir usando o Crear
función que definimos anteriormente, agora nós

262
00:13:31,260 --> 00:13:33,860
quere inserir un
lista que xa existe.

263
00:13:33,860 --> 00:13:36,499
>> Entón, neste caso, imos
para pasar en dous argumentos,

264
00:13:36,499 --> 00:13:39,290
o punteiro para a cabeza do que
lista que quere engadir á conectados.

265
00:13:39,290 --> 00:13:40,910
De novo, é por iso que é tan
importante que sempre

266
00:13:40,910 --> 00:13:43,400
seguir, porque
é a única forma de realmente

267
00:13:43,400 --> 00:13:46,690
ten que referirse a toda a lista é
só por un punteiro para o primeiro elemento.

268
00:13:46,690 --> 00:13:49,360
Por iso, queremos pasar nun
punteiro para ese primeiro elemento,

269
00:13:49,360 --> 00:13:52,226
e calquera valor que
quere engadir á lista.

270
00:13:52,226 --> 00:13:54,600
E, finalmente, esta función
vai voltar un punteiro

271
00:13:54,600 --> 00:13:57,980
ao novo xefe dunha lista ligada.

272
00:13:57,980 --> 00:13:59,700
>> Cales son os pasos implicadas aquí?

273
00:13:59,700 --> 00:14:02,249
Ben, así como coa crear,
necesitamos reservar dinamicamente

274
00:14:02,249 --> 00:14:05,540
espazo para un novo nodo, e asegúrese
garantir que non quede sen memoria, outra vez,

275
00:14:05,540 --> 00:14:07,150
porque estamos usando malloc.

276
00:14:07,150 --> 00:14:09,080
Entón, nós queremos encher
e introducir o no,

277
00:14:09,080 --> 00:14:12,730
de xeito que o número, o que quere
val é, para o no.

278
00:14:12,730 --> 00:14:17,310
Queremos introducir o no en
o inicio da lista encadeada.

279
00:14:17,310 --> 00:14:19,619
>> Hai unha razón para que eu
quero facer iso, e

280
00:14:19,619 --> 00:14:21,910
pode valer a pena tomar un segundo
para deter o vídeo aquí,

281
00:14:21,910 --> 00:14:25,860
e pensar por que eu ía querer
introducir no inicio dun conectado

282
00:14:25,860 --> 00:14:26,589
lista.

283
00:14:26,589 --> 00:14:28,630
Unha vez máis, eu mencionen anteriormente
que realmente non

284
00:14:28,630 --> 00:14:33,020
importa si preservalo-lo en calquera
orde, polo tanto, é posible que unha pista.

285
00:14:33,020 --> 00:14:36,040
E viu o que acontecería se nós
quería a-- ou só un segundo

286
00:14:36,040 --> 00:14:37,360
atrás, cando estabamos indo
a través de busca vostede

287
00:14:37,360 --> 00:14:39,235
podía ver o que pode
deberse estabamos intentando

288
00:14:39,235 --> 00:14:41,330
para introducir no fin da lista.

289
00:14:41,330 --> 00:14:44,750
Porque non temos un
punteiro para o fin da lista.

290
00:14:44,750 --> 00:14:47,490
>> Polo tanto, a razón que me gustaría
para introducir no inicio,

291
00:14:47,490 --> 00:14:49,380
é porque eu podo facelo inmediatamente.

292
00:14:49,380 --> 00:14:52,730
Eu teño un punteiro en principio, e
imos ver iso nun visual nun segundo.

293
00:14:52,730 --> 00:14:55,605
Pero se eu queira inserir o final,
Teño que comezar de inicio,

294
00:14:55,605 --> 00:14:58,760
percorrer todo o camiño para a
final, e despois predica-la por diante.

295
00:14:58,760 --> 00:15:01,420
Entón, iso significaría que
introducir no fin da lista

296
00:15:01,420 --> 00:15:04,140
se tornaría un o de n
operación, volvendo

297
00:15:04,140 --> 00:15:06,720
para a nosa discusión de
complexidade computacional.

298
00:15:06,720 --> 00:15:10,140
El tiña se tornado un o de n operación, onde
como a lista quedou maior e máis grande,

299
00:15:10,140 --> 00:15:13,310
e máis grande, que vai facer máis e
máis difícil para alinhavar algo

300
00:15:13,310 --> 00:15:14,661
en ao final.

301
00:15:14,661 --> 00:15:17,410
Pero sempre moi doado
alinhavar algo en en principio,

302
00:15:17,410 --> 00:15:19,060
está sempre no inicio.

303
00:15:19,060 --> 00:15:21,620
>> E nós imos ver un visual desta novo.

304
00:15:21,620 --> 00:15:24,100
E, a continuación, xa que estamos a facer, xa
temos Insírese o novo nó,

305
00:15:24,100 --> 00:15:26,880
queremos volver noso punteiro para
o novo xefe dunha lista ligada, o que

306
00:15:26,880 --> 00:15:29,213
xa que estamos introducindo no
comezando, vai ser realmente

307
00:15:29,213 --> 00:15:31,060
un punteiro para o no que acabamos de crear.

308
00:15:31,060 --> 00:15:33,280
Imos ver esta,
porque eu creo que vai axudar.

309
00:15:33,280 --> 00:15:36,661
>> Entón aquí está a nosa lista, que consiste en
catro elementos, contendo un nó 15,

310
00:15:36,661 --> 00:15:38,410
o que apunta a un nodo
contén 9, que

311
00:15:38,410 --> 00:15:41,370
apunta a un nodo que contén 13,
o que apunta a un nodo que conteña

312
00:15:41,370 --> 00:15:44,840
10, que ten o nulo
punteiro como o seu próximo punteiro

313
00:15:44,840 --> 00:15:47,010
de xeito que é o final da lista.

314
00:15:47,010 --> 00:15:50,200
Por iso, queremos introducir un
novo nodo co valor 12

315
00:15:50,200 --> 00:15:52,720
a comezos do presente
lista, o que imos facer?

316
00:15:52,720 --> 00:15:58,770
Ben, primeiro nós malloc espazo para a
no, e, a continuación, imos poñer 12 en alí.

317
00:15:58,770 --> 00:16:02,211
>> Entón, agora chegamos a un
punto de decisión, non?

318
00:16:02,211 --> 00:16:03,960
Temos un par de
punteiros que puidésemos

319
00:16:03,960 --> 00:16:06,770
mover, que debemos avanzar en primeiro lugar?

320
00:16:06,770 --> 00:16:09,250
Temos que facer 12 puntos para
o novo xefe da lista--

321
00:16:09,250 --> 00:16:13,020
ou me desculpar, temos que facer 12
apuntar ao antigo xefe da lista?

322
00:16:13,020 --> 00:16:15,319
Ou deberiamos dicir que o
lista agora comeza a 12.

323
00:16:15,319 --> 00:16:17,110
Hai unha distinción
alí, e nós ollaremos

324
00:16:17,110 --> 00:16:19,870
o que pasa con ambos nun segundo.

325
00:16:19,870 --> 00:16:23,350
>> Pero isto conduce a un
gran tema para a barra lateral,

326
00:16:23,350 --> 00:16:26,280
que é un dos que o
as cousas máis complicadas con listas ligadas

327
00:16:26,280 --> 00:16:30,980
é organizar os punteiros
na orde correcta.

328
00:16:30,980 --> 00:16:34,520
Se mover as cousas fóra de orde,
pode acabar accidentalmente

329
00:16:34,520 --> 00:16:36,050
orphaning resto da lista.

330
00:16:36,050 --> 00:16:37,300
E aquí está un exemplo diso.

331
00:16:37,300 --> 00:16:40,540
Entón, imos ir coa idea de--
ben, que acabamos de crear 12.

332
00:16:40,540 --> 00:16:43,180
Sabemos 12 será
o novo xefe da lista,

333
00:16:43,180 --> 00:16:47,660
e así por que non imos só mover
o punteiro lista para apuntar alí.

334
00:16:47,660 --> 00:16:49,070
>> OK, entón iso é bo.

335
00:16:49,070 --> 00:16:51,560
Entón, agora onde é que 12 seguinte punto?

336
00:16:51,560 --> 00:16:54,580
Quero dicir, visualmente vemos
que apuntar para 15,

337
00:16:54,580 --> 00:16:57,250
como seres humanos é moi evidente para nós.

338
00:16:57,250 --> 00:17:00,300
Como o ordenador sabe?

339
00:17:00,300 --> 00:17:02,720
Non temos nada
apuntando a máis 15, non?

340
00:17:02,720 --> 00:17:05,869
>> Perdemos calquera capacidade de referirse a 15.

341
00:17:05,869 --> 00:17:11,460
Non podemos dicir nova frecha ao lado equals
algo, non hai nada alí.

342
00:17:11,460 --> 00:17:13,510
De feito, temos orfos
resto da lista

343
00:17:13,510 --> 00:17:16,465
ao facelo, temos
accidentalmente rompe a cadea.

344
00:17:16,465 --> 00:17:18,089
E nós certamente non queremos facelo.

345
00:17:18,089 --> 00:17:20,000
>> Entón, imos volver e tentar de novo.

346
00:17:20,000 --> 00:17:24,060
Quizais a cousa ben a facer
está situado á beira do punteiro 12

347
00:17:24,060 --> 00:17:28,290
ao antigo xefe da primeira lista,
entón podemos mover a lista máis.

348
00:17:28,290 --> 00:17:30,420
E, de feito, que é o
orde correcta que

349
00:17:30,420 --> 00:17:32,836
necesitamos seguir cando estamos
Traballando con unha lista vinculada illadamente.

350
00:17:32,836 --> 00:17:36,460
Sempre queremos conectar o
novo elemento da lista,

351
00:17:36,460 --> 00:17:41,010
antes de tomar este tipo de
importante paso de modificación

352
00:17:41,010 --> 00:17:43,360
onde a cabeza da lista ligada é.

353
00:17:43,360 --> 00:17:46,740
De novo, iso é unha cousa tan fundamental,
nós non queremos perder o control dela.

354
00:17:46,740 --> 00:17:49,310
>> Entón, nós queremos estar seguro de que
todo é encadenados,

355
00:17:49,310 --> 00:17:52,040
antes de pasar ese punteiro.

356
00:17:52,040 --> 00:17:55,300
E así esta sería a orde correcta,
o cal é para chamar á súa lista 12,

357
00:17:55,300 --> 00:17:57,630
a continuación, dicir que a lista comeza a 12.

358
00:17:57,630 --> 00:18:00,860
Se dixo que a lista comeza o 12 e
a continuación, intentou conectar 12 da lista,

359
00:18:00,860 --> 00:18:02,193
xa vimos o que pasa.

360
00:18:02,193 --> 00:18:04,920
Perdemos a lista por erro.

361
00:18:04,920 --> 00:18:06,740
>> OK, entón unha cousa para falar.

362
00:18:06,740 --> 00:18:09,750
E se a xente quere se librar de
toda unha lista ligada dunha vez?

363
00:18:09,750 --> 00:18:11,750
Unha vez máis, estamos mallocing
todo este espazo, e por iso,

364
00:18:11,750 --> 00:18:13,351
que liberalo la cando estamos a facer.

365
00:18:13,351 --> 00:18:15,350
Entón, agora queremos eliminar
a listaxe ligada.

366
00:18:15,350 --> 00:18:16,850
Ben, o que queremos facer?

367
00:18:16,850 --> 00:18:20,460
>> Se nós alcanzamos o punteiro nulo, nós
quere parar, se non, pode borrar

368
00:18:20,460 --> 00:18:23,420
resto da lista e, a continuación, me liberar.

369
00:18:23,420 --> 00:18:28,890
Eliminar o resto da lista,
e, a continuación, liberar o no actual.

370
00:18:28,890 --> 00:18:32,850
O que significa que o son como,
cal técnica falamos

371
00:18:32,850 --> 00:18:35,440
sobre anteriormente é que o son como?

372
00:18:35,440 --> 00:18:39,560
Eliminar todos os outros, a continuación,
volver e me eliminar.

373
00:18:39,560 --> 00:18:42,380
>> Isto é recursão, fixemos o
problema un pouco menor,

374
00:18:42,380 --> 00:18:46,910
estamos dicindo eliminar todos
máis, entón podes me eliminar.

375
00:18:46,910 --> 00:18:50,940
E máis abaixo na estrada, ese nó
vai dicir, eliminar todos os outros.

376
00:18:50,940 --> 00:18:53,940
Pero finalmente imos chegar ao
momento en que a lista é nulo,

377
00:18:53,940 --> 00:18:55,310
e este é o noso caso base.

378
00:18:55,310 --> 00:18:57,010
>> Entón, imos dar un ollo niso,
e como iso pode funcionar.

379
00:18:57,010 --> 00:18:59,759
Entón aquí está a nosa lista, é o mesmo
lista que estaban falando sobre,

380
00:18:59,759 --> 00:19:00,980
e hai os pasos.

381
00:19:00,980 --> 00:19:04,200
Hai unha morea de texto aquí, pero
espero que a visualización vai axudar.

382
00:19:04,200 --> 00:19:08,557
>> Entón, nós have-- e eu tamén tirou
a nosa pila de cadros ilustración

383
00:19:08,557 --> 00:19:10,890
do noso vídeo sobre pilas de chamadas,
e espero que todo isto

384
00:19:10,890 --> 00:19:13,260
xuntos ha amosar-lle o que está pasando.

385
00:19:13,260 --> 00:19:14,510
Entón aquí está o noso código pseudocódigo.

386
00:19:14,510 --> 00:19:17,830
Se chegamos a un valor nulo
punteiro, parar, se non,

387
00:19:17,830 --> 00:19:21,320
eliminar o resto da lista,
logo liberar o no actual.

388
00:19:21,320 --> 00:19:25,700
Entón, agora, lista--
o punteiro do que somos

389
00:19:25,700 --> 00:19:28,410
pasando para destruír a 12 puntos.

390
00:19:28,410 --> 00:19:33,340
12 non é un punteiro nulo, polo que estamos
indo para eliminar o resto da lista.

391
00:19:33,340 --> 00:19:35,450
>> ¿Que é a exclusión do
resto de nós implicados?

392
00:19:35,450 --> 00:19:37,950
Ben, iso significa facer unha
chamar para destruír, dicindo

393
00:19:37,950 --> 00:19:42,060
15 é que o inicio do
resto da lista queremos destruír.

394
00:19:42,060 --> 00:19:47,480
E así a chamada para destruír
12 é unha especie de en espera.

395
00:19:47,480 --> 00:19:52,690
Está conxelado alí, esperando o
chamar para destruír 15, para rematar o seu traballo.

396
00:19:52,690 --> 00:19:56,280
>> Ben, 15 non é un punteiro nulo, e
polo que vai dicir, todo ben,

397
00:19:56,280 --> 00:19:58,450
ben, elimine o resto da lista.

398
00:19:58,450 --> 00:20:00,760
O resto da lista comeza
ás 9, e por iso imos só

399
00:20:00,760 --> 00:20:04,514
espera ata que exclúa todo o que
material, a continuación, volver e borrar min.

400
00:20:04,514 --> 00:20:06,680
Ben 9 vai dicir, ben,
Eu non son un punteiro nulo,

401
00:20:06,680 --> 00:20:09,020
así eliminar o resto da lista a partir de aquí.

402
00:20:09,020 --> 00:20:11,805
E así intentar destruír 13.

403
00:20:11,805 --> 00:20:15,550
13 di: Non son punteiro nulo,
mesmo, el pasa o buck.

404
00:20:15,550 --> 00:20:17,930
10 non é punteiro nulo, 10
contén un punteiro nulo,

405
00:20:17,930 --> 00:20:20,200
10, pero non é ela mesma unha
Punteiro Nulo agora,

406
00:20:20,200 --> 00:20:22,470
e así que pasa o balón tamén.

407
00:20:22,470 --> 00:20:25,560
>> E agora incluír puntos alí,
realmente chama a atención sobre some--

408
00:20:25,560 --> 00:20:28,710
se eu tivese máis espazo na imaxe,
el chama a atención sobre un espazo chou

409
00:20:28,710 --> 00:20:29,960
que non sabemos o que é.

410
00:20:29,960 --> 00:20:34,680
É o punteiro nulo, porén, a lista
é, literalmente, agora defínese valores nulos.

411
00:20:34,680 --> 00:20:36,820
El está a apuntar cara a dereita dentro desa caixa vermella.

412
00:20:36,820 --> 00:20:39,960
Chegamos a un punteiro nulo, polo
podemos parar, e estamos a facer.

413
00:20:39,960 --> 00:20:46,230
>> E así que cadro vermello é agora-- no
parte superior da stack-- ese é o cadro activo,

414
00:20:46,230 --> 00:20:47,017
pero está feito.

415
00:20:47,017 --> 00:20:48,600
Se chegamos a un punteiro nulo, pare.

416
00:20:48,600 --> 00:20:51,290
Nós non facemos nada, nós
non pode liberar un punteiro nulo,

417
00:20:51,290 --> 00:20:55,070
non malloc calquera
espazo, e por iso estamos a facer.

418
00:20:55,070 --> 00:20:57,590
Entón, ese cadro función
é destruído, e nós

419
00:20:57,590 --> 00:21:00,930
resume-- nós incorporarse onde paramos
fóra co máis elevado seguinte, que

420
00:21:00,930 --> 00:21:02,807
é este cadro azul escuro aquí.

421
00:21:02,807 --> 00:21:04,390
Entón, nós incorporarse exactamente onde paramos.

422
00:21:04,390 --> 00:21:06,598
Nós excluído o resto do
lista xa, entón agora estamos

423
00:21:06,598 --> 00:21:08,000
vai liberar os nós actuais.

424
00:21:08,000 --> 00:21:12,920
Entón agora podemos liberar este nodo, e agora
chegamos ao final da función.

425
00:21:12,920 --> 00:21:16,810
E así que o cadro función é destruído,
e nós incorporarse na unha luz azul.

426
00:21:16,810 --> 00:21:20,650
>> Por iso, says-- Xa done--
a exclusión do resto da lista, para

427
00:21:20,650 --> 00:21:23,140
liberar o no actual.

428
00:21:23,140 --> 00:21:26,520
E agora o marco amarela é
de volta ao principio da pila.

429
00:21:26,520 --> 00:21:29,655
E así como se pode ver, estamos agora
destruíndo a lista da dereita á esquerda.

430
00:21:29,655 --> 00:21:33,710

431
00:21:33,710 --> 00:21:37,280
>> Que acontecería, porén,
se tivésemos feito as cousas de forma incorrecta?

432
00:21:37,280 --> 00:21:39,410
Así como cando tentamos
engadir un elemento.

433
00:21:39,410 --> 00:21:41,909
Se errei a cadea, se
non conectar os punteiros

434
00:21:41,909 --> 00:21:44,690
na orde correcta, se nós
só liberado o primeiro elemento,

435
00:21:44,690 --> 00:21:47,420
se nós só liberou o
cabeza da lista, agora nós

436
00:21:47,420 --> 00:21:49,642
non teñen ningunha maneira para referirse a
resto da lista.

437
00:21:49,642 --> 00:21:51,350
E por iso, tería
orfas todo,

438
00:21:51,350 --> 00:21:53,880
teriamos que é
chamado de fuga de memoria.

439
00:21:53,880 --> 00:21:56,800
Se se lembrar do noso vídeo
na distribución dinámica de memoria,

440
00:21:56,800 --> 00:21:58,650
iso non é cousa moi boa.

441
00:21:58,650 --> 00:22:00,810
>> Entón, como dixen, hai
varias operacións

442
00:22:00,810 --> 00:22:04,010
que necesitamos usar para traballar
con lista ligada de forma eficaz.

443
00:22:04,010 --> 00:22:08,430
E pode notar que omitido nun,
excluíndo un único elemento a partir dun conectado

444
00:22:08,430 --> 00:22:09,064
lista.

445
00:22:09,064 --> 00:22:10,980
A razón pola que eu fixen iso
é que é realmente tipo de

446
00:22:10,980 --> 00:22:14,360
complicado para pensar sobre como eliminar
un único elemento dunha illadamente

447
00:22:14,360 --> 00:22:15,600
lista ligada.

448
00:22:15,600 --> 00:22:19,950
Necesitamos ser capaces de pasar por riba
algo na lista, que

449
00:22:19,950 --> 00:22:22,975
Significa chegar a un que ponto--
quere borrar este node--

450
00:22:22,975 --> 00:22:25,350
pero, a fin de facelo así que
non perda ningunha información,

451
00:22:25,350 --> 00:22:30,530
necesitamos conectar este
nó aquí, aquí.

452
00:22:30,530 --> 00:22:33,390
>> Entón eu probablemente fixen iso mal
a partir dunha perspectiva visual.

453
00:22:33,390 --> 00:22:36,830
Entón, estamos no inicio da nosa
lista, estamos a proceder a través de,

454
00:22:36,830 --> 00:22:40,510
que quere eliminar este nodo.

455
00:22:40,510 --> 00:22:43,440
Se nós só excluílo,
nós quebramos a corrente.

456
00:22:43,440 --> 00:22:45,950
Este nodo aquí
refírese a todo o demais,

457
00:22:45,950 --> 00:22:48,260
contén a cadea de agora en diante.

458
00:22:48,260 --> 00:22:51,190
>> Entón, o que necesitamos facer, de feito,
despois de chegar a este punto,

459
00:22:51,190 --> 00:22:56,670
é que necesitamos dar un paso atrás un, e
conectar ese nó durante a ese nó,

460
00:22:56,670 --> 00:22:58,590
para que poidamos, a continuación, eliminar
o un no medio.

461
00:22:58,590 --> 00:23:02,120
Pero as listas vinculada illadamente non facer
nos ofrecer unha forma de ir cara atrás.

462
00:23:02,120 --> 00:23:05,160
Entón, necesitamos quere manter
dous punteiros, e mover los

463
00:23:05,160 --> 00:23:09,527
especie de off paso, un detrás do
outros como nós imos, ou chegar a un punto

464
00:23:09,527 --> 00:23:11,110
e, a continuación, enviar outro punteiro completamente.

465
00:23:11,110 --> 00:23:13,150
E como se pode ver,
pode ser un pouco confuso.

466
00:23:13,150 --> 00:23:15,360
Afortunadamente, temos
outra forma de resolver isto,

467
00:23:15,360 --> 00:23:17,810
cando falamos de listas dobremente ligadas.

468
00:23:17,810 --> 00:23:20,720
>> Eu son Doug Lloyd, este é CS50.

469
00:23:20,720 --> 00:23:22,298