1
00:00:00,000 --> 00:00:02,832
>> [RIPRODUZIONE DI BRANI MUSICALI]

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

3
00:00:05,670 --> 00:00:08,560
>> DOUG LLOYD: OK, così a
questo punto nel corso,

4
00:00:08,560 --> 00:00:15,300
abbiamo coperto un sacco di basi di C.
Sappiamo molto di variabili, gli array,

5
00:00:15,300 --> 00:00:17,610
puntatori, tutta quella roba buona.

6
00:00:17,610 --> 00:00:21,610
Questi sono tutti i tipi di costruito
per vedere come i fondamentali,

7
00:00:21,610 --> 00:00:23,880
ma possiamo fare di più, giusto?

8
00:00:23,880 --> 00:00:27,930
Possiamo combinare le cose
insieme in modi interessanti.

9
00:00:27,930 --> 00:00:31,010
>> E così facciamo che, cominciamo
di espandersi di ciò che ci dà C,

10
00:00:31,010 --> 00:00:35,270
e iniziare a creare la nostra dati
strutture con questi edifici

11
00:00:35,270 --> 00:00:40,590
blocchi insieme per fare qualcosa
veramente prezioso, utile.

12
00:00:40,590 --> 00:00:43,420
Un modo in cui possiamo farlo è
per parlare di collezioni.

13
00:00:43,420 --> 00:00:48,360
Così finora abbiamo avuto un tipo di dati
struttura per rappresentare collezioni

14
00:00:48,360 --> 00:00:51,030
di come i valori, valori simili.

15
00:00:51,030 --> 00:00:52,350
Sarebbe un array.

16
00:00:52,350 --> 00:00:57,020
Abbiamo collezioni di numeri interi, o
raccolte di caratteri e così via.

17
00:00:57,020 --> 00:01:00,890
>> Le strutture sono anche una sorta di dati
Struttura per la raccolta di informazioni,

18
00:01:00,890 --> 00:01:03,220
ma non è per la raccolta come valori.

19
00:01:03,220 --> 00:01:08,090
Di solito mescola diversi tipi di dati
insieme all'interno di un unico pacchetto.

20
00:01:08,090 --> 00:01:10,750
Ma non è per sé
utilizzato per concatenare

21
00:01:10,750 --> 00:01:16,920
o collegare insieme simile
elementi, come un array.

22
00:01:16,920 --> 00:01:20,960
Gli array sono grandi per
elemento guardare in alto, ma il richiamo

23
00:01:20,960 --> 00:01:24,262
che è molto difficile
inserire in un array,

24
00:01:24,262 --> 00:01:26,470
a meno che non ci stiamo inserendo in
alla fine di tale matrice.

25
00:01:26,470 --> 00:01:29,730
>> E il miglior esempio ho
per questo è insertion sort.

26
00:01:29,730 --> 00:01:31,650
Se vi ricordate il nostro video
su insertion sort,

27
00:01:31,650 --> 00:01:34,110
c'era un sacco di
spesa coinvolti nell'avere

28
00:01:34,110 --> 00:01:37,970
per raccogliere gli elementi, e li sposterà
fuori strada per adattarsi qualcosa

29
00:01:37,970 --> 00:01:41,290
nel mezzo dell'array.

30
00:01:41,290 --> 00:01:44,690
Array soffrono anche di un altro
problema, che è mancanza di flessibilità.

31
00:01:44,690 --> 00:01:47,150
Quando si dichiara un array,
otteniamo un solo colpo a questo.

32
00:01:47,150 --> 00:01:49,790
Arriviamo a dire, voglio
questo molti elementi.

33
00:01:49,790 --> 00:01:51,940
Potrebbe essere 100, potrebbe
essere 1.000, potrebbe

34
00:01:51,940 --> 00:01:55,930
essere x dove x è un numero che l'utente
ci ha dato al prompt o al comando

35
00:01:55,930 --> 00:01:56,630
Linea.

36
00:01:56,630 --> 00:01:59,905
>> Ma abbiamo solo un colpo a questo, abbiamo
Non capisco per poi dire oh, in realtà io

37
00:01:59,905 --> 00:02:04,360
necessaria 101, o avevo bisogno di x più 20.

38
00:02:04,360 --> 00:02:07,910
Troppo tardi, abbiamo già dichiarato la
matrice, e se vogliamo ottenere 101 o x

39
00:02:07,910 --> 00:02:12,050
più 20, dobbiamo dichiarare
una serie completamente diversa,

40
00:02:12,050 --> 00:02:15,540
copiare tutti gli elementi della matrice
sopra, e poi abbiamo abbastanza.

41
00:02:15,540 --> 00:02:19,880
E se siamo di nuovo sbagliato, cosa
se abbiamo effettivamente bisogno 102, o x più 40,

42
00:02:19,880 --> 00:02:21,970
dobbiamo farlo di nuovo.

43
00:02:21,970 --> 00:02:26,250
Quindi sono molto poco flessibile
per il ridimensionamento nostri dati,

44
00:02:26,250 --> 00:02:29,360
ma se uniamo insieme alcuni
dei principi fondamentali che abbiamo già

45
00:02:29,360 --> 00:02:33,230
imparato a conoscere i puntatori e delle strutture,
in particolare utilizzando la memoria dinamica

46
00:02:33,230 --> 00:02:36,180
assegnazione con malloc, ci
può mettere insieme questi pezzi

47
00:02:36,180 --> 00:02:40,960
per creare nuovi dati structure-- un
concatenata lista potremmo say--

48
00:02:40,960 --> 00:02:45,400
che ci permette di crescere e
compattare un insieme di valori

49
00:02:45,400 --> 00:02:48,800
e non avremo alcun spreco di spazio.

50
00:02:48,800 --> 00:02:53,320
>> Così ancora una volta, che noi chiamiamo questa idea,
questa nozione, un elenco collegato.

51
00:02:53,320 --> 00:02:56,320
In particolare, in questo video siamo
parlando di lista concatenata,

52
00:02:56,320 --> 00:02:59,185
e poi un altro video ne parleremo
liste su doppiamente collegate, che

53
00:02:59,185 --> 00:03:01,560
è solo una variazione sul tema qui.

54
00:03:01,560 --> 00:03:05,200
Ma una lista concatenata
è composto da nodi,

55
00:03:05,200 --> 00:03:08,559
nodi solo di essere un term-- astratto
è solo una cosa che sto chiamando

56
00:03:08,559 --> 00:03:10,350
che è una sorta di
struttura, in fondo, io sono?

57
00:03:10,350 --> 00:03:16,190
Basta andare a chiamare un node-- e questo
nodo ha due membri, o due campi.

58
00:03:16,190 --> 00:03:20,300
Ha i dati, di solito un
integer, float un personaggio,

59
00:03:20,300 --> 00:03:23,790
o potrebbe essere qualche altro tipo di dati
che avete definito con un tipo def.

60
00:03:23,790 --> 00:03:29,290
E contiene un puntatore
altro nodo dello stesso tipo.

61
00:03:29,290 --> 00:03:34,710
>> Quindi abbiamo due cose dentro di
questo nodo, i dati e un puntatore

62
00:03:34,710 --> 00:03:36,380
ad un altro nodo.

63
00:03:36,380 --> 00:03:39,370
E se si inizia a visualizzare i
questo, si può pensare a questo proposito

64
00:03:39,370 --> 00:03:42,280
come una catena di nodi che
sono collegati tra loro.

65
00:03:42,280 --> 00:03:45,070
Abbiamo il primo nodo,
contiene dati e un puntatore

66
00:03:45,070 --> 00:03:49,110
al secondo nodo, che contiene
dati e un puntatore al terzo nodo.

67
00:03:49,110 --> 00:03:52,940
Ed è per questo che lo chiamiamo
lista collegata, stanno collegati tra loro.

68
00:03:52,940 --> 00:03:56,070
>> Che cosa significa questo speciale
struttura del nodo assomigliare?

69
00:03:56,070 --> 00:04:01,120
Beh, se vi ricordate dal nostro video
definire tipi personalizzati, con il tipo di definizione,

70
00:04:01,120 --> 00:04:05,400
possiamo definire un structure-- e
digitare definire una struttura come questa.

71
00:04:05,400 --> 00:04:11,240
tyepdef struct sllist, e poi io sono
utilizzando il valore parola qui arbitrariamente

72
00:04:11,240 --> 00:04:13,891
per indicare qualsiasi tipo di dati davvero.

73
00:04:13,891 --> 00:04:16,890
Si potrebbe passare un intero o float,
si potrebbe avere quello che vuoi.

74
00:04:16,890 --> 00:04:19,389
Non è limitato al solo
interi, o qualcosa di simile.

75
00:04:19,389 --> 00:04:22,790
Quindi il valore è solo un arbitrario
il tipo di dati, e quindi un puntatore

76
00:04:22,790 --> 00:04:26,310
ad un altro nodo dello stesso tipo.

77
00:04:26,310 --> 00:04:29,690
>> Ora, c'è un po 'di cattura
qui con definenti una struttura

78
00:04:29,690 --> 00:04:33,030
quando si tratta di una struttura auto referenziale.

79
00:04:33,030 --> 00:04:35,340
Devo avere una temporanea
nome per la mia struttura.

80
00:04:35,340 --> 00:04:37,640
Alla fine della giornata ho
vuole chiaramente chiamarlo

81
00:04:37,640 --> 00:04:43,030
nodo SLL, che è in ultima analisi, il nuovo
nome parte della mia definizione del tipo,

82
00:04:43,030 --> 00:04:47,450
ma non posso usare il nodo sll
nel mezzo di questo.

83
00:04:47,450 --> 00:04:51,430
Il motivo è, non ho
creato un tipo chiamato nodo sll

84
00:04:51,430 --> 00:04:55,200
fino a quando mi ha colpito questo ultimo punto qui.

85
00:04:55,200 --> 00:04:59,720
Fino a quel punto, devo avere
un altro modo per fare riferimento a questo tipo di dati.

86
00:04:59,720 --> 00:05:02,440
>> E questo è un auto
tipo di dati di riferimento.

87
00:05:02,440 --> 00:05:06,314
It; s un tipo di dati di un
struttura che contiene un dato,

88
00:05:06,314 --> 00:05:08,480
e un puntatore a un'altra
struttura dello stesso tipo.

89
00:05:08,480 --> 00:05:11,750
Così ho bisogno di essere in grado di fare riferimento a
questo tipo di dati almeno temporaneamente,

90
00:05:11,750 --> 00:05:14,910
così dando una temporanea
nome di struct sllist

91
00:05:14,910 --> 00:05:18,540
mi permette di dire che voglio poi un
puntatore ad un'altra sllist struct,

92
00:05:18,540 --> 00:05:24,690
una stella struct sllist, e poi
dopo che ho completato la definizione,

93
00:05:24,690 --> 00:05:27,220
Ora posso chiamare questo tipo un nodo sll.

94
00:05:27,220 --> 00:05:30,520
>> Ecco, questo è il motivo per cui si vede non c'è
un nome temporaneo qui,

95
00:05:30,520 --> 00:05:31,879
ma un nome permanente qui.

96
00:05:31,879 --> 00:05:33,920
A volte si potrebbe vedere
definizioni di struttura,

97
00:05:33,920 --> 00:05:36,570
per esempio, che non sono
autoreferenziale, che

98
00:05:36,570 --> 00:05:39,390
non hanno un nome identificatore qui.

99
00:05:39,390 --> 00:05:43,040
Sarebbe solo dire typedef struct,
aprire parentesi graffa e quindi definirlo.

100
00:05:43,040 --> 00:05:45,620
Ma se siete struct è auto
referenziale, come questo è,

101
00:05:45,620 --> 00:05:49,010
è necessario specificare un
Nome tipo temporaneo.

102
00:05:49,010 --> 00:05:51,310
Ma alla fine, ora
che abbiamo fatto questo,

103
00:05:51,310 --> 00:05:53,620
possiamo solo fare riferimento al
questi nodi, queste unità,

104
00:05:53,620 --> 00:05:57,900
come nodi SLL a fini
del resto di questo video.

105
00:05:57,900 --> 00:06:00,900
>> Va bene, quindi sappiamo come
creare un nodo lista collegata.

106
00:06:00,900 --> 00:06:03,240
Sappiamo come definire
un nodo lista collegata.

107
00:06:03,240 --> 00:06:06,670
Ora, se stiamo per iniziare
che li utilizzano per raccogliere informazioni,

108
00:06:06,670 --> 00:06:10,360
ci sono un paio di operazioni che
bisogno di capire e lavorare con.

109
00:06:10,360 --> 00:06:12,860
Abbiamo bisogno di sapere come creare
una lista collegata dal nulla.

110
00:06:12,860 --> 00:06:14,901
Se non c'è la lista già,
vogliamo iniziare uno.

111
00:06:14,901 --> 00:06:16,960
Quindi abbiamo bisogno di essere in grado
per creare una lista collegata,

112
00:06:16,960 --> 00:06:19,130
abbiamo bisogno di cercare probabilmente
attraverso l'elenco di link

113
00:06:19,130 --> 00:06:21,830
per trovare un elemento che stiamo cercando.

114
00:06:21,830 --> 00:06:24,430
Dobbiamo poter inserire
cose nuove nella lista,

115
00:06:24,430 --> 00:06:25,930
vogliamo che la nostra lista per essere in grado di crescere.

116
00:06:25,930 --> 00:06:28,638
E allo stesso modo, noi vogliamo essere in grado
per cancellare le cose dalla nostra lista,

117
00:06:28,638 --> 00:06:30,250
vogliamo che la nostra lista per essere in grado di ridursi.

118
00:06:30,250 --> 00:06:32,160
E alla fine della nostra
programmi, in particolare

119
00:06:32,160 --> 00:06:34,550
se vi ricordate che siamo
allocare dinamicamente la memoria

120
00:06:34,550 --> 00:06:38,337
per costruire queste liste tipicamente,
vogliamo liberare tutta questa memoria

121
00:06:38,337 --> 00:06:39,670
quando avremo finito a lavorare con esso.

122
00:06:39,670 --> 00:06:44,627
E così abbiamo bisogno di essere in grado di eliminare un
tutta la lista collegata a un sicuro colpo solo.

123
00:06:44,627 --> 00:06:46,460
Quindi cerchiamo di passare attraverso
alcune di queste operazioni

124
00:06:46,460 --> 00:06:51,192
e come possiamo visualizzarli,
a parlare in codice pseudocodice in particolare.

125
00:06:51,192 --> 00:06:53,150
Quindi, vogliamo creare un
lista collegata, così forse noi

126
00:06:53,150 --> 00:06:56,480
voler definire una funzione
con questo prototipo.

127
00:06:56,480 --> 00:07:01,690
SLL nodo stella, creare, e sto passando
in un solo argomento, alcuni dati arbitrari

128
00:07:01,690 --> 00:07:05,530
digitare nuovamente, di un certo tipo di dati arbitrari.

129
00:07:05,530 --> 00:07:10,482
Ma sto returning-- questa funzione dovrebbe
tornare a me un puntatore, per un singolarmente

130
00:07:10,482 --> 00:07:11,190
nodo lista collegata.

131
00:07:11,190 --> 00:07:14,050
Anche in questo caso, stiamo cercando di creare
una lista collegata dal nulla,

132
00:07:14,050 --> 00:07:17,900
quindi ho bisogno di un puntatore a
quella lista quando ho finito.

133
00:07:17,900 --> 00:07:19,420
>> Ma quali sono i passi necessari qui?

134
00:07:19,420 --> 00:07:20,960
Beh, prima cosa di cui sono
intenzione di fare è dinamicamente

135
00:07:20,960 --> 00:07:22,550
allocare spazio per un nuovo nodo.

136
00:07:22,550 --> 00:07:26,689
Ancora una volta, stiamo creando fuori sottile
aria, quindi abbiamo bisogno di spazio malloc per essa.

137
00:07:26,689 --> 00:07:28,480
E, naturalmente, subito
dopo che malloc,

138
00:07:28,480 --> 00:07:31,692
abbiamo sempre controlliamo a fare in modo che il nostro
pointer-- non abbiamo ottenuto indietro nulla.

139
00:07:31,692 --> 00:07:33,650
Perché se cerchiamo di
deferenza un puntatore nullo,

140
00:07:33,650 --> 00:07:36,190
stiamo andando a subire un
segfault e non vogliamo questo.

141
00:07:36,190 --> 00:07:39,510
>> Poi vogliamo compilare il campo,
vogliamo inizializzare il campo del valore

142
00:07:39,510 --> 00:07:41,690
e inizializzare il campo successivo.

143
00:07:41,690 --> 00:07:45,450
E poi vogliamo a-- alla fine come il
prototipo di funzione indicates-- vogliamo

144
00:07:45,450 --> 00:07:49,940
per restituire un puntatore ad un nodo sll.

145
00:07:49,940 --> 00:07:51,710
Quindi, ciò che rende questo aspetto visivo?

146
00:07:51,710 --> 00:07:55,230
Beh, prima che andremo a dinamicamente
allocare spazio per un nuovo nodo sll,

147
00:07:55,230 --> 00:07:58,320
così abbiamo malloc-- che è
una rappresentazione visiva

148
00:07:58,320 --> 00:08:00,020
del nodo che abbiamo appena creato.

149
00:08:00,020 --> 00:08:02,757
E noi verifichiamo
non è null-- in questo caso,

150
00:08:02,757 --> 00:08:04,840
l'immagine non avrebbe
mostrato su se fosse nullo,

151
00:08:04,840 --> 00:08:07,298
avremmo esaurito la memoria,
così stiamo bene di andare lì.

152
00:08:07,298 --> 00:08:10,200
Così ora siamo alla fase C,
inizializzare il campo del valore nodi.

153
00:08:10,200 --> 00:08:12,280
Ebbene, sulla base di questa funzione
Chiamo sto usando qui,

154
00:08:12,280 --> 00:08:16,700
sembra che io voglio passare a 6,
Così io 6 nel campo del valore.

155
00:08:16,700 --> 00:08:18,865
Ora, inizializzare il campo successivo.

156
00:08:18,865 --> 00:08:21,640
Beh, quello che sto andando a fare lì,
non vi è nulla accanto, a destra,

157
00:08:21,640 --> 00:08:23,600
questa è l'unica cosa nella lista.

158
00:08:23,600 --> 00:08:27,206
Allora, qual è la prossima cosa nella lista?

159
00:08:27,206 --> 00:08:29,660
>> Non dovrebbe puntare a qualsiasi cosa, a destra.

160
00:08:29,660 --> 00:08:33,600
Non c'è niente altro là, così che cosa è
il concetto che sappiamo di che è nothing--

161
00:08:33,600 --> 00:08:35,638
puntatori a nulla?

162
00:08:35,638 --> 00:08:37,929
Dovrebbe essere forse vogliamo
di mettere un puntatore nullo lì,

163
00:08:37,929 --> 00:08:40,178
e io rappresento il nulla
puntatore come solo una scatola rossa,

164
00:08:40,178 --> 00:08:41,559
non possiamo andare oltre.

165
00:08:41,559 --> 00:08:44,430
Come vedremo un po 'più tardi,
avremo infine catene

166
00:08:44,430 --> 00:08:46,330
di frecce di collegamento
questi nodi insieme,

167
00:08:46,330 --> 00:08:48,480
ma quando si colpisce la
scatola rossa, che è nullo,

168
00:08:48,480 --> 00:08:51,150
non possiamo andare oltre,
questa è la fine della lista.

169
00:08:51,150 --> 00:08:53,960
>> E, infine, vogliamo solo
restituire un puntatore a questo nodo.

170
00:08:53,960 --> 00:08:56,160
Così che chiameremo nuovo,
e tornerà nuovo

171
00:08:56,160 --> 00:08:59,370
in modo che possa essere utilizzato in
qualsiasi funzione creata.

172
00:08:59,370 --> 00:09:03,100
Così ci si va, Abbiamo creato un singolarmente
nodo lista collegata dal nulla,

173
00:09:03,100 --> 00:09:05,920
e ora abbiamo una lista possiamo lavorare con.

174
00:09:05,920 --> 00:09:08,260
>> Ora, diciamo che già
avere una grande catena,

175
00:09:08,260 --> 00:09:09,800
e vogliamo trovare qualcosa.

176
00:09:09,800 --> 00:09:12,716
E noi vogliamo una funzione che sta andando
a restituire true o false, a seconda

177
00:09:12,716 --> 00:09:15,840
se esiste un valore in quella lista.

178
00:09:15,840 --> 00:09:18,160
Un prototipo di funzione, o
dichiarazione per quella funzione,

179
00:09:18,160 --> 00:09:23,320
potrebbe apparire come questo-- Bool trovare, e
poi vogliamo passare due argomenti.

180
00:09:23,320 --> 00:09:26,996
>> Il primo, è un puntatore al
primo elemento della lista collegata.

181
00:09:26,996 --> 00:09:29,620
Questo è in realtà qualcosa che ti
sempre voglia di tenere traccia di,

182
00:09:29,620 --> 00:09:33,110
e in realtà potrebbe essere qualcosa che
ancora messo in una variabile globale.

183
00:09:33,110 --> 00:09:35,360
Una volta creata una lista,
sempre, sempre

184
00:09:35,360 --> 00:09:38,990
vuole tenere traccia del molto
primo elemento della lista.

185
00:09:38,990 --> 00:09:43,690
In questo modo è possibile fare riferimento a tutti gli altri
gli elementi da solo seguendo la catena,

186
00:09:43,690 --> 00:09:47,300
senza dover tenere puntatori
intatto per ogni singolo elemento.

187
00:09:47,300 --> 00:09:50,920
Hai solo bisogno di tenere traccia del primo
uno se sono tutti collegati tra loro.

188
00:09:50,920 --> 00:09:52,460
>> E poi la seconda cosa
stiamo passando di nuovo

189
00:09:52,460 --> 00:09:54,376
è some-- arbitrariamente
qualunque sia il tipo di dati che siamo

190
00:09:54,376 --> 00:09:59,640
cercando c'è dentro di
speriamo che uno dei nodi della lista.

191
00:09:59,640 --> 00:10:00,980
Ma quali sono i passaggi?

192
00:10:00,980 --> 00:10:04,250
Beh, la prima cosa che facciamo è
creiamo un puntatore trasversale

193
00:10:04,250 --> 00:10:06,015
che punta alla testa liste.

194
00:10:06,015 --> 00:10:08,890
Beh, perché lo facciamo, abbiamo già
un puntatore alla testa liste,

195
00:10:08,890 --> 00:10:10,974
perché non solo che muoviamo un giro?

196
00:10:10,974 --> 00:10:13,140
Beh, come ho appena detto,
è davvero importante per noi

197
00:10:13,140 --> 00:10:17,580
tenere sempre traccia del
primo elemento della lista.

198
00:10:17,580 --> 00:10:21,270
E così in realtà è meglio
creare un duplicato di questo,

199
00:10:21,270 --> 00:10:25,350
e l'uso che per muoversi quindi non abbiamo mai
spostare accidentalmente via, o sempre

200
00:10:25,350 --> 00:10:30,430
avere un puntatore ad un certo punto che è
proprio sul primo elemento della lista.

201
00:10:30,430 --> 00:10:33,290
Quindi è meglio creare un
secondo quella che usiamo per muoversi.

202
00:10:33,290 --> 00:10:35,877
>> Poi abbiamo appena confrontare se
il campo di valore a quel nodo

203
00:10:35,877 --> 00:10:38,960
è quello che stiamo cercando, e se è
Non ci basta spostare al nodo successivo.

204
00:10:38,960 --> 00:10:41,040
E continuiamo a farlo
oltre, e oltre, e oltre,

205
00:10:41,040 --> 00:10:44,811
fino a quando non sia trovato
l'elemento, o ci ha colpito

206
00:10:44,811 --> 00:10:47,310
null-- abbiamo raggiunto la fine
della lista e non è lì.

207
00:10:47,310 --> 00:10:50,540
Questo dovrebbe auspicabilmente suonare un campanello
a voi come appena ricerca lineare,

208
00:10:50,540 --> 00:10:54,430
stiamo solo replicando in
una struttura della lista concatenata

209
00:10:54,430 --> 00:10:56,280
invece di utilizzare una vasta gamma di farlo.

210
00:10:56,280 --> 00:10:58,210
>> Quindi, ecco un esempio di
una lista concatenata.

211
00:10:58,210 --> 00:11:00,043
Questo consiste
cinque nodi, e abbiamo

212
00:11:00,043 --> 00:11:04,330
un puntatore alla testa della
lista, che si chiama lista.

213
00:11:04,330 --> 00:11:07,385
La prima cosa che vogliamo fare è
ancora una volta, creare tale puntatore attraversamento.

214
00:11:07,385 --> 00:11:09,760
Così abbiamo ora due puntatori
che scegliere la stessa cosa.

215
00:11:09,760 --> 00:11:15,025
>> Ora, si noti anche qui, non l'ho fatto
devono malloc qualsiasi spazio per trav.

216
00:11:15,025 --> 00:11:18,970
Non ho detto trav uguale malloc
qualcosa, quel nodo esiste già,

217
00:11:18,970 --> 00:11:21,160
che lo spazio nella memoria esiste già.

218
00:11:21,160 --> 00:11:24,290
Quindi tutto quello che sto facendo è in realtà
la creazione di un altro puntatore a esso.

219
00:11:24,290 --> 00:11:28,210
Non sto mallocing un ulteriore
spazio, basta avere ora due puntatori

220
00:11:28,210 --> 00:11:31,370
indicando la stessa cosa.

221
00:11:31,370 --> 00:11:33,710
>> Così è 2 quello che sto cercando?

222
00:11:33,710 --> 00:11:37,220
Beh, no, così invece sono
andando a passare al successivo.

223
00:11:37,220 --> 00:11:41,740
Quindi, fondamentalmente direi,
trav uguale trav prossimo.

224
00:11:41,740 --> 00:11:43,630
È 3 quello che sto cercando, no.

225
00:11:43,630 --> 00:11:45,780
Così continuo a andare
attraverso, fino alla fine

226
00:11:45,780 --> 00:11:48,690
arrivare a 6, che è quello che sto cercando
in base a una chiamata di funzione

227
00:11:48,690 --> 00:11:51,600
Ho in cima
lì, e così ho finito.

228
00:11:51,600 --> 00:11:54,150
>> Ora, che cosa se l'elemento sono
cercando non è presente nella lista,

229
00:11:54,150 --> 00:11:55,510
sta ancora andare a lavorare?

230
00:11:55,510 --> 00:11:57,120
Beh, si noti che la lista
qui è sottilmente diverso,

231
00:11:57,120 --> 00:11:59,410
e questa è un'altra cosa che è
importante con liste collegate,

232
00:11:59,410 --> 00:12:01,780
non c'è bisogno di conservare
li in un ordine particolare.

233
00:12:01,780 --> 00:12:05,390
Si può se si vuole, ma
avrete già notato

234
00:12:05,390 --> 00:12:09,310
che non stiamo tenendo traccia di
che numero elemento siamo al.

235
00:12:09,310 --> 00:12:13,150
>> E questo è una sorta di un commercio che noi
avere con lista collegata versi array,

236
00:12:13,150 --> 00:12:15,300
è vero non abbiamo
accesso casuale più.

237
00:12:15,300 --> 00:12:18,150
Non possiamo solo dire, voglio
per andare all'elemento 0,

238
00:12:18,150 --> 00:12:21,410
o il 6 ° elemento della mia matrice,
che posso fare in un array.

239
00:12:21,410 --> 00:12:25,080
Non posso dire che voglio andare al
Elemento 0i, o il sesto elemento,

240
00:12:25,080 --> 00:12:30,360
o l'elemento 25 della mia lista collegata,
non c'è alcun indice ad essi associati.

241
00:12:30,360 --> 00:12:33,660
E così non ha molta importanza
se conserviamo la nostra lista in ordine.

242
00:12:33,660 --> 00:12:36,080
Se vuoi te
certamente possibile, ma c'è

243
00:12:36,080 --> 00:12:38,567
alcun motivo per cui hanno bisogno di
conservati in qualsiasi ordine.

244
00:12:38,567 --> 00:12:40,400
Così ancora una volta, proviamo e
trovare 6 in questa lista.

245
00:12:40,400 --> 00:12:43,200
Bene, iniziamo a
inizio, non troviamo 6,

246
00:12:43,200 --> 00:12:47,690
e allora non continuiamo a trovare
6, fino a quando alla fine abbiamo arrivare a qui.

247
00:12:47,690 --> 00:12:52,790
Così giusti punti ora trav al nodo
contenenti 8, e sei non è lì.

248
00:12:52,790 --> 00:12:55,250
>> Quindi il passo successivo sarebbe
per andare al puntatore prossimo,

249
00:12:55,250 --> 00:12:57,440
così dicono trav uguale trav prossimo.

250
00:12:57,440 --> 00:13:00,750
Ebbene, trav successiva, indicata da
la scatola rossa c'è, è nullo.

251
00:13:00,750 --> 00:13:03,020
Quindi non c'è nessun altro posto dove
andare, e quindi a questo punto

252
00:13:03,020 --> 00:13:06,120
possiamo concludere che abbiamo raggiunto
alla fine della lista collegata,

253
00:13:06,120 --> 00:13:07,190
e 6 non è in là.

254
00:13:07,190 --> 00:13:10,980
E sarebbe restituito
falso in questo caso.

255
00:13:10,980 --> 00:13:14,540
>> OK, come possiamo inserire un nuovo
nodo alla lista linkata?

256
00:13:14,540 --> 00:13:17,310
Così siamo stati in grado di creare
una lista collegata dal nulla,

257
00:13:17,310 --> 00:13:19,370
ma probabilmente vogliamo
costruire una catena e non

258
00:13:19,370 --> 00:13:22,620
creare un gruppo di liste distinte.

259
00:13:22,620 --> 00:13:25,700
Vogliamo avere una lista che
ha un sacco di nodi in esso,

260
00:13:25,700 --> 00:13:28,040
non un gruppo di liste con un singolo nodo.

261
00:13:28,040 --> 00:13:31,260
Così non possiamo continuare ad usare la Creazione
Funzione abbiamo definito in precedenza, ora siamo

262
00:13:31,260 --> 00:13:33,860
vuole inserire in un
lista che già esiste.

263
00:13:33,860 --> 00:13:36,499
>> Quindi questo caso, stiamo andando
per passare a due argomenti,

264
00:13:36,499 --> 00:13:39,290
il puntatore alla testa di tale
lista che vogliamo aggiungere alla collegata.

265
00:13:39,290 --> 00:13:40,910
Anche in questo caso, è per questo che è così
importante che abbiamo sempre

266
00:13:40,910 --> 00:13:43,400
tenere traccia di esso, perché
è l'unico modo per davvero

267
00:13:43,400 --> 00:13:46,690
devono riferirsi alla completa lista è
semplicemente un puntatore al primo elemento.

268
00:13:46,690 --> 00:13:49,360
Quindi vogliamo passare a una
puntatore a quel primo elemento,

269
00:13:49,360 --> 00:13:52,226
e qualunque valore che
vuole aggiungere alla lista.

270
00:13:52,226 --> 00:13:54,600
E alla fine di questa funzione
sta per restituire un puntatore

271
00:13:54,600 --> 00:13:57,980
per il nuovo capo di una lista collegata.

272
00:13:57,980 --> 00:13:59,700
>> Quali sono i passi necessari qui?

273
00:13:59,700 --> 00:14:02,249
Beh, proprio come con creare,
abbiamo bisogno di allocare dinamicamente

274
00:14:02,249 --> 00:14:05,540
lo spazio per un nuovo nodo, e controllare per
sicuri di non esaurire la memoria, ancora una volta,

275
00:14:05,540 --> 00:14:07,150
perché stiamo usando malloc.

276
00:14:07,150 --> 00:14:09,080
Poi vogliamo popolare
e inserire il nodo,

277
00:14:09,080 --> 00:14:12,730
così si può mettere il numero, qualunque
val è, nel nodo.

278
00:14:12,730 --> 00:14:17,310
Vogliamo inserire il nodo
All'inizio della lista collegata.

279
00:14:17,310 --> 00:14:19,619
>> C'è una ragione che io
vuole fare questo, ed è

280
00:14:19,619 --> 00:14:21,910
potrebbe essere la pena di prendere un secondo
per mettere in pausa il video qui,

281
00:14:21,910 --> 00:14:25,860
e riflettere sul perché dovrei voler
inserire all'inizio di una collegata

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

283
00:14:26,589 --> 00:14:28,630
Ancora una volta, ho detto in precedenza
che in realtà non

284
00:14:28,630 --> 00:14:33,020
importa se conserviamo in alcun
ordine, quindi forse questo è un indizio.

285
00:14:33,020 --> 00:14:36,040
E avete visto che cosa accadrebbe se noi
voluto a-- o da solo un secondo

286
00:14:36,040 --> 00:14:37,360
fa, quando stavamo andando
attraverso ricerca si

287
00:14:37,360 --> 00:14:39,235
poteva vedere quello che potrebbe
succederebbe se stavamo cercando

288
00:14:39,235 --> 00:14:41,330
inserire alla fine della lista.

289
00:14:41,330 --> 00:14:44,750
Perché noi non abbiamo un
puntatore alla fine della lista.

290
00:14:44,750 --> 00:14:47,490
>> Quindi la ragione che vorrei
inserire all'inizio,

291
00:14:47,490 --> 00:14:49,380
è perché posso farlo subito.

292
00:14:49,380 --> 00:14:52,730
Ho un puntatore all'inizio, e
vedremo questo in un visivo in un secondo.

293
00:14:52,730 --> 00:14:55,605
Ma se voglio inserire alla fine,
Devo cominciare dall'inizio,

294
00:14:55,605 --> 00:14:58,760
attraversare fino al
fine, e poi virare su.

295
00:14:58,760 --> 00:15:01,420
Quindi ciò significherebbe che
inserendo alla fine della lista

296
00:15:01,420 --> 00:15:04,140
sarebbe diventato un o di n
operazione, andando indietro

297
00:15:04,140 --> 00:15:06,720
alla nostra discussione di
complessità computazionale.

298
00:15:06,720 --> 00:15:10,140
Sarebbe diventato un o di un'operazione n, dove
come la lista ha ottenuto più grande, e più grande,

299
00:15:10,140 --> 00:15:13,310
e più grande, che diventerà sempre
più difficile da virare qualcosa

300
00:15:13,310 --> 00:15:14,661
on alla fine.

301
00:15:14,661 --> 00:15:17,410
Ma è sempre molto facile
virare qualcosa all'inizio,

302
00:15:17,410 --> 00:15:19,060
sei sempre all'inizio.

303
00:15:19,060 --> 00:15:21,620
>> E vedremo di nuovo una visuale di questo.

304
00:15:21,620 --> 00:15:24,100
E poi una volta che abbiamo finito, una volta
abbiamo inserito il nuovo nodo,

305
00:15:24,100 --> 00:15:26,880
vogliamo tornare il nostro puntatore
il nuovo capo di una lista collegata, che

306
00:15:26,880 --> 00:15:29,213
dal momento che stiamo inserendo in
inizio, sarà effettivamente

307
00:15:29,213 --> 00:15:31,060
un puntatore al nodo appena creato.

308
00:15:31,060 --> 00:15:33,280
Cerchiamo di visualizzare questo,
perché penso che ti aiuto.

309
00:15:33,280 --> 00:15:36,661
>> Quindi, ecco la nostra lista, si compone di
quattro elementi, un nodo contenente 15,

310
00:15:36,661 --> 00:15:38,410
che punta a un nodo
contenente 9, che

311
00:15:38,410 --> 00:15:41,370
punta a un nodo contenente 13,
che punti a un nodo che contiene

312
00:15:41,370 --> 00:15:44,840
10, che ha il nullo
puntatore come sua prossima puntatore

313
00:15:44,840 --> 00:15:47,010
di modo che è la fine della lista.

314
00:15:47,010 --> 00:15:50,200
Quindi vogliamo inserire un
nuovo nodo con il valore 12

315
00:15:50,200 --> 00:15:52,720
all'inizio di questo
lista, cosa facciamo?

316
00:15:52,720 --> 00:15:58,770
Beh, per prima cosa malloc spazio per il
nodo, e poi abbiamo messo 12 in là.

317
00:15:58,770 --> 00:16:02,211
>> Così ora abbiamo raggiunto un
punto di decisione, giusto?

318
00:16:02,211 --> 00:16:03,960
Abbiamo un paio di
puntatori che potremmo

319
00:16:03,960 --> 00:16:06,770
muoviamo, quale dobbiamo passare prima?

320
00:16:06,770 --> 00:16:09,250
Dobbiamo fare 12 punti per
il nuovo capo del list--

321
00:16:09,250 --> 00:16:13,020
o mi scusi, dobbiamo fare 12
puntare alla vecchia testa della lista?

322
00:16:13,020 --> 00:16:15,319
O dovremmo dire che la
lista ora inizia alle 12.

323
00:16:15,319 --> 00:16:17,110
C'è una distinzione
lì, e vedremo

324
00:16:17,110 --> 00:16:19,870
a ciò che accade con entrambi in un secondo.

325
00:16:19,870 --> 00:16:23,350
>> Ma questo porta ad un
grande tema per la barra laterale,

326
00:16:23,350 --> 00:16:26,280
che è quello della
le cose più delicate con liste collegate

327
00:16:26,280 --> 00:16:30,980
è quello di organizzare i puntatori
nell'ordine corretto.

328
00:16:30,980 --> 00:16:34,520
Se si sposta le cose in ordine,
si può finire accidentalmente

329
00:16:34,520 --> 00:16:36,050
orfano il resto della lista.

330
00:16:36,050 --> 00:16:37,300
Ed ecco un esempio di questo.

331
00:16:37,300 --> 00:16:40,540
Quindi cerchiamo di andare con l'idea di--
bene, abbiamo appena creato 12.

332
00:16:40,540 --> 00:16:43,180
Sappiamo che 12 sta per essere
il nuovo capo della lista,

333
00:16:43,180 --> 00:16:47,660
e allora perché non ci muoviamo solo
il puntatore lista a punto lì.

334
00:16:47,660 --> 00:16:49,070
>> Ok, va bene.

335
00:16:49,070 --> 00:16:51,560
Così ora da dove viene il 12 prossimo punto?

336
00:16:51,560 --> 00:16:54,580
Voglio dire, visivamente possiamo vedere
che punterà a 15,

337
00:16:54,580 --> 00:16:57,250
come gli esseri umani è davvero ovvio per noi.

338
00:16:57,250 --> 00:17:00,300
Come fa sapere il computer?

339
00:17:00,300 --> 00:17:02,720
Noi non abbiamo nulla
che punta a 15 più, giusto?

340
00:17:02,720 --> 00:17:05,869
>> Abbiamo perso ogni capacità di fare riferimento a 15.

341
00:17:05,869 --> 00:17:11,460
Non possiamo dire nuova freccia accanto eguali
qualcosa, non c'è niente lì.

342
00:17:11,460 --> 00:17:13,510
In realtà, abbiamo orfani
il resto della lista

343
00:17:13,510 --> 00:17:16,465
così facendo, abbiamo
accidentalmente rotto la catena.

344
00:17:16,465 --> 00:17:18,089
E noi certamente non vogliamo farlo.

345
00:17:18,089 --> 00:17:20,000
>> Quindi cerchiamo di tornare indietro e provare di nuovo.

346
00:17:20,000 --> 00:17:24,060
Forse la cosa giusta da fare
è quello di impostare 12 del prossimo puntatore

347
00:17:24,060 --> 00:17:28,290
alla vecchia testa del primo elenco,
allora possiamo spostare la lista sopra.

348
00:17:28,290 --> 00:17:30,420
Ed infatti, che è il
ordine corretto che noi

349
00:17:30,420 --> 00:17:32,836
devono seguire quando siamo
lavorare con la lista concatenata.

350
00:17:32,836 --> 00:17:36,460
Vogliamo sempre di collegare il
nuovo elemento nella lista,

351
00:17:36,460 --> 00:17:41,010
prima di prendere questo tipo di
passo importante di cambiamento

352
00:17:41,010 --> 00:17:43,360
dove la testa della lista collegata è.

353
00:17:43,360 --> 00:17:46,740
Ancora una volta, questa è una cosa fondamentale,
noi non vogliamo perdere la traccia di esso.

354
00:17:46,740 --> 00:17:49,310
>> Quindi vogliamo fare in modo che
tutto è incatenato insieme,

355
00:17:49,310 --> 00:17:52,040
prima di passare tale puntatore.

356
00:17:52,040 --> 00:17:55,300
E quindi questo sarebbe l'ordine corretto,
che è di collegare 12 alla lista,

357
00:17:55,300 --> 00:17:57,630
poi dire che l'elenco inizia una 12.

358
00:17:57,630 --> 00:18:00,860
Se abbiamo detto che la lista inizia alle 12 e
poi ha cercato di connettersi 12 alla lista,

359
00:18:00,860 --> 00:18:02,193
abbiamo già visto cosa succede.

360
00:18:02,193 --> 00:18:04,920
Perdiamo la lista per errore.

361
00:18:04,920 --> 00:18:06,740
>> OK, una cosa di cui parlare.

362
00:18:06,740 --> 00:18:09,750
Che cosa succede se si vuole sbarazzarsi di
un intero collegata lista in una sola volta?

363
00:18:09,750 --> 00:18:11,750
Ancora una volta, stiamo mallocing
tutto questo spazio, e quindi abbiamo

364
00:18:11,750 --> 00:18:13,351
bisogno di liberarlo quando abbiamo finito.

365
00:18:13,351 --> 00:18:15,350
Così ora vogliamo eliminare
l'intera lista collegata.

366
00:18:15,350 --> 00:18:16,850
Ebbene, che cosa vogliamo fare?

367
00:18:16,850 --> 00:18:20,460
>> Se abbiamo raggiunto il puntatore nullo, abbiamo
vuole fermare, altrimenti, basta eliminare

368
00:18:20,460 --> 00:18:23,420
il resto della lista e poi liberami.

369
00:18:23,420 --> 00:18:28,890
Eliminare il resto della lista,
e quindi liberare il nodo corrente.

370
00:18:28,890 --> 00:18:32,850
Che cosa significa che suonano come,
quale tecnica abbiamo abbiamo parlato

371
00:18:32,850 --> 00:18:35,440
circa in precedenza fa quel suono come?

372
00:18:35,440 --> 00:18:39,560
Eliminare tutti gli altri, quindi
tornare e mi cancellare.

373
00:18:39,560 --> 00:18:42,380
>> Che è la ricorsione, che abbiamo fatto la
problema un po 'più piccolo,

374
00:18:42,380 --> 00:18:46,910
stiamo dicendo cancellare tutti
altro, allora è possibile eliminare me.

375
00:18:46,910 --> 00:18:50,940
E a valle della strada, tale nodo
dirà, eliminare tutti gli altri.

376
00:18:50,940 --> 00:18:53,940
Ma alla fine ci arriveremo al
punto in cui la lista è nullo,

377
00:18:53,940 --> 00:18:55,310
e questo è il nostro caso base.

378
00:18:55,310 --> 00:18:57,010
>> Quindi, diamo uno sguardo a questo,
e come questo potrebbe funzionare.

379
00:18:57,010 --> 00:18:59,759
Quindi, ecco la nostra lista, è la stessa
Elenchiamo stavamo parlando,

380
00:18:59,759 --> 00:19:00,980
e ci sono i gradini.

381
00:19:00,980 --> 00:19:04,200
C'è un sacco di testo qui, ma
speriamo che la visualizzazione sarà di aiuto.

382
00:19:04,200 --> 00:19:08,557
>> Così abbiamo have-- e ho anche tirato
il nostro stack frame illustrazione

383
00:19:08,557 --> 00:19:10,890
dal nostro video su stack di chiamate,
e speriamo che tutto questo

384
00:19:10,890 --> 00:19:13,260
insieme vi mostrerà ciò che sta succedendo.

385
00:19:13,260 --> 00:19:14,510
Quindi, ecco il nostro codice pseudocodice.

386
00:19:14,510 --> 00:19:17,830
Se raggiungiamo un nullo
puntatore, stop, altrimenti,

387
00:19:17,830 --> 00:19:21,320
eliminare il resto della lista,
quindi liberare il nodo corrente.

388
00:19:21,320 --> 00:19:25,700
Così adesso, list--
il puntatore che siamo

389
00:19:25,700 --> 00:19:28,410
passando per distruggere punti a 12.

390
00:19:28,410 --> 00:19:33,340
12 non è un puntatore nullo, quindi siamo
andando a cancellare il resto della lista.

391
00:19:33,340 --> 00:19:35,450
>> Che cosa è l'eliminazione del
resto di noi ha coinvolto?

392
00:19:35,450 --> 00:19:37,950
Beh, significa fare un
chiamata a distruggere, dicendo

393
00:19:37,950 --> 00:19:42,060
15 che è l'inizio della
resto della lista che vogliamo distruggere.

394
00:19:42,060 --> 00:19:47,480
E così la chiamata a distruggere
12 è di tipo in attesa.

395
00:19:47,480 --> 00:19:52,690
E 'congelato lì, in attesa del
chiamare per distruggere 15, per completare il suo lavoro.

396
00:19:52,690 --> 00:19:56,280
>> Beh, 15 non è un puntatore nullo, e
così sta andando a dire, va bene,

397
00:19:56,280 --> 00:19:58,450
bene, cancellare il resto della lista.

398
00:19:58,450 --> 00:20:00,760
Il resto della lista inizia
a 9, e quindi dobbiamo solo

399
00:20:00,760 --> 00:20:04,514
attendere che si elimina tutto ciò che
roba, poi tornare e mi cancellare.

400
00:20:04,514 --> 00:20:06,680
Ben 9 sta per dire, beh,
Io non sono un puntatore nullo,

401
00:20:06,680 --> 00:20:09,020
così cancellare il resto della lista da qui.

402
00:20:09,020 --> 00:20:11,805
E così cercare di distruggere 13.

403
00:20:11,805 --> 00:20:15,550
13 dice, io non sono puntatore nullo,
stessa cosa, passa la patata bollente.

404
00:20:15,550 --> 00:20:17,930
10 non è puntatore nullo, 10
contiene un puntatore nullo,

405
00:20:17,930 --> 00:20:20,200
ma 10 non è di per sé un
Null Pointer in questo momento,

406
00:20:20,200 --> 00:20:22,470
e così passa il dollaro troppo.

407
00:20:22,470 --> 00:20:25,560
>> E ora elencare punti lì,
sarebbe davvero puntare a some--

408
00:20:25,560 --> 00:20:28,710
se avessi più spazio nell'immagine,
sarebbe puntare a qualche spazio casuale

409
00:20:28,710 --> 00:20:29,960
che non sappiamo di cosa si tratta.

410
00:20:29,960 --> 00:20:34,680
E 'il puntatore nullo, però, la lista
è letteralmente ora impostato è valori nulli.

411
00:20:34,680 --> 00:20:36,820
Si punta a destra dentro quella scatola rossa.

412
00:20:36,820 --> 00:20:39,960
Abbiamo raggiunto un puntatore nullo, così
possiamo fermarci, e abbiamo finito.

413
00:20:39,960 --> 00:20:46,230
>> E così quella cornice viola è now-- al
cima stack-- che è il frame attivo,

414
00:20:46,230 --> 00:20:47,017
ma è fatto.

415
00:20:47,017 --> 00:20:48,600
Se abbiamo raggiunto un puntatore nullo, stop.

416
00:20:48,600 --> 00:20:51,290
Noi non facciamo nulla,
non può liberare un puntatore nullo,

417
00:20:51,290 --> 00:20:55,070
non abbiamo alcun malloc
spazio, e così abbiamo finito.

418
00:20:55,070 --> 00:20:57,590
In modo che la funzione telaio
è distrutta, e noi

419
00:20:57,590 --> 00:21:00,930
resume-- prendiamo dove abbiamo lasciato
off con immediatamente superiore, che

420
00:21:00,930 --> 00:21:02,807
è questa cornice blu scuro qui.

421
00:21:02,807 --> 00:21:04,390
Quindi prendiamo a destra dove abbiamo lasciato.

422
00:21:04,390 --> 00:21:06,598
Abbiamo cancellato il resto del
lista già, quindi ora siamo

423
00:21:06,598 --> 00:21:08,000
andando a liberare i nodi attuali.

424
00:21:08,000 --> 00:21:12,920
Così ora possiamo liberare questo nodo, e ora
abbiamo raggiunto la fine della funzione.

425
00:21:12,920 --> 00:21:16,810
E così quella cornice funzione è distrutta,
e prendiamo la luce blu.

426
00:21:16,810 --> 00:21:20,650
>> Così says-- ho già done--
eliminando il resto della lista, così

427
00:21:20,650 --> 00:21:23,140
liberare il nodo corrente.

428
00:21:23,140 --> 00:21:26,520
E ora la cornice gialla è
torna in cima alla pila.

429
00:21:26,520 --> 00:21:29,655
E così come vedete, siamo ora
distruggendo la lista da destra a sinistra.

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

431
00:21:33,710 --> 00:21:37,280
>> Cosa sarebbe successo, però,
se avessimo fatto le cose nel modo sbagliato?

432
00:21:37,280 --> 00:21:39,410
Proprio come quando abbiamo provato
aggiungere un elemento.

433
00:21:39,410 --> 00:21:41,909
Se abbiamo incasinato la catena, se
noi non colleghiamo i puntatori

434
00:21:41,909 --> 00:21:44,690
nell'ordine corretto, se
appena liberato il primo elemento,

435
00:21:44,690 --> 00:21:47,420
se abbiamo appena liberato il
capo della lista, ora siamo

436
00:21:47,420 --> 00:21:49,642
hanno modo di consultare
il resto della lista.

437
00:21:49,642 --> 00:21:51,350
E così avremmo
orfano tutto,

438
00:21:51,350 --> 00:21:53,880
avremmo avuto ciò che è
chiamato una perdita di memoria.

439
00:21:53,880 --> 00:21:56,800
Se vi ricordate dal nostro video
sulla allocazione dinamica della memoria,

440
00:21:56,800 --> 00:21:58,650
che non è cosa molto buona.

441
00:21:58,650 --> 00:22:00,810
>> Così come ho detto, ci
sono diverse operazioni

442
00:22:00,810 --> 00:22:04,010
che abbiamo bisogno di usare per lavorare
con lista concatenata in modo efficace.

443
00:22:04,010 --> 00:22:08,430
E avrete notato ho omesso uno,
l'eliminazione di un singolo elemento da una collegata

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

445
00:22:09,064 --> 00:22:10,980
La ragione per cui l'ho fatto
è che è in realtà una specie di

446
00:22:10,980 --> 00:22:14,360
difficile pensare a come eliminare
un singolo elemento da una singolarmente

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

448
00:22:15,600 --> 00:22:19,950
Dobbiamo essere in grado di saltare
qualcosa nella lista, che

449
00:22:19,950 --> 00:22:22,975
mezzi si arriva a un noi Point--
di voler eliminare questo node--

450
00:22:22,975 --> 00:22:25,350
ma per fare in modo che
non perdere alcuna informazione,

451
00:22:25,350 --> 00:22:30,530
abbiamo bisogno di collegare questo
nodo qui, qui.

452
00:22:30,530 --> 00:22:33,390
>> Quindi probabilmente ho fatto male
da un punto di vista visivo.

453
00:22:33,390 --> 00:22:36,830
Quindi siamo all'inizio del nostro
lista, stiamo procedendo attraverso,

454
00:22:36,830 --> 00:22:40,510
vogliamo eliminare questo nodo.

455
00:22:40,510 --> 00:22:43,440
Se è sufficiente eliminarlo,
abbiamo rotto la catena.

456
00:22:43,440 --> 00:22:45,950
Questo nodo qui
si riferisce a tutto il resto,

457
00:22:45,950 --> 00:22:48,260
contiene la catena da qui in avanti.

458
00:22:48,260 --> 00:22:51,190
>> Allora cosa dobbiamo fare in realtà
dopo siamo arrivati ​​a questo punto,

459
00:22:51,190 --> 00:22:56,670
è dobbiamo fare un passo indietro di un, e
collegare questo nodo verso questo nodo,

460
00:22:56,670 --> 00:22:58,590
in modo che possiamo eliminare
quella nel mezzo.

461
00:22:58,590 --> 00:23:02,120
Ma le liste concatenate semplici non lo fanno
noi fornire un modo per tornare indietro.

462
00:23:02,120 --> 00:23:05,160
Quindi abbiamo bisogno di mantenere o
due puntatori, e spostarli

463
00:23:05,160 --> 00:23:09,527
sorta di passo off, uno dietro l'
altro come andiamo, o arrivare a un punto

464
00:23:09,527 --> 00:23:11,110
e poi inviare un altro puntatore attraverso.

465
00:23:11,110 --> 00:23:13,150
E come potete vedere,
può ottenere un po 'disordinato.

466
00:23:13,150 --> 00:23:15,360
Per fortuna, abbiamo
un altro modo per risolvere questo,

467
00:23:15,360 --> 00:23:17,810
quando si parla di liste doppiamente collegate.

468
00:23:17,810 --> 00:23:20,720
>> Sono Doug Lloyd, questo è CS50.

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