1
00:00:00,000 --> 00:00:02,832
>> [Glazbom]

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

3
00:00:05,670 --> 00:00:08,560
>> Doug LLOYD: U redu, tako da na
ovom trenutku u tijeku,

4
00:00:08,560 --> 00:00:15,300
smo pokriveni puno osnovama C.
Mi znamo mnogo o varijable, polja,

5
00:00:15,300 --> 00:00:17,610
pokazivače, sve to dobre stvari.

6
00:00:17,610 --> 00:00:21,610
Oni su svi nekako izgrađena
u vidjeti kao osnova,

7
00:00:21,610 --> 00:00:23,880
ali možemo učiniti više, zar ne?

8
00:00:23,880 --> 00:00:27,930
Možemo kombinirati stvari
zajedno na zanimljive načine.

9
00:00:27,930 --> 00:00:31,010
>> I tako ćemo učiniti, počnimo
granaju od onoga što nam daje C,

10
00:00:31,010 --> 00:00:35,270
i početi stvarati vlastitu podataka
strukture pomoću tih zgrada

11
00:00:35,270 --> 00:00:40,590
blokovi zajedno učiniti nešto
jako vrijedan, koristan.

12
00:00:40,590 --> 00:00:43,420
Jedan od načina možemo učiniti je
razgovarati o zbirkama.

13
00:00:43,420 --> 00:00:48,360
Dakle, do sada smo imali jednu vrstu podataka
strukture za zastupanje zbirke

14
00:00:48,360 --> 00:00:51,030
poput vrijednosti, slične vrijednosti.

15
00:00:51,030 --> 00:00:52,350
To će biti niz.

16
00:00:52,350 --> 00:00:57,020
Imamo zbirke brojeva ili
zbirke likova i tako dalje.

17
00:00:57,020 --> 00:01:00,890
>> Strukture su također svojevrsni podataka
strukture za prikupljanje informacija,

18
00:01:00,890 --> 00:01:03,220
ali to nije za prikupljanje kao i vrijednosti.

19
00:01:03,220 --> 00:01:08,090
Obično se miješa različite vrste podataka
zajedno unutar jednog okvira.

20
00:01:08,090 --> 00:01:10,750
Ali to nije samo po sebi
koristi za lanac zajedno

21
00:01:10,750 --> 00:01:16,920
ili spojite zajedno slično
stavke, poput niza.

22
00:01:16,920 --> 00:01:20,960
Nizovi su super za
Element pogledati, ali opoziva

23
00:01:20,960 --> 00:01:24,262
da je vrlo teško
umetnuti u niz,

24
00:01:24,262 --> 00:01:26,470
osim ako smo ugurate
samom kraju tog polja.

25
00:01:26,470 --> 00:01:29,730
>> A najbolji primjer imam
za to je umetanje vrsta.

26
00:01:29,730 --> 00:01:31,650
Ako se sjećate naš video
na umetanje vrsta,

27
00:01:31,650 --> 00:01:34,110
bilo je dosta
rashodi su uključeni u vlasništvo

28
00:01:34,110 --> 00:01:37,970
pokupiti elemente, a pomak ih
zabit da stane nešto

29
00:01:37,970 --> 00:01:41,290
u sredini vaše polje.

30
00:01:41,290 --> 00:01:44,690
Nizovi također pate od drugog
Problem, koji je nefleksibilnost.

31
00:01:44,690 --> 00:01:47,150
Kad smo proglasiti niz,
dobili smo jedan metak u njega.

32
00:01:47,150 --> 00:01:49,790
Mi smo dobili za reći, ja želim
to mnogi elementi.

33
00:01:49,790 --> 00:01:51,940
Moglo bi biti 100, to bi moglo
biti 1.000, to bi moglo

34
00:01:51,940 --> 00:01:55,930
biti x gdje je x broj koji je korisnik
nam je dao na brz ili na zapovijed

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

36
00:01:56,630 --> 00:01:59,905
>> No, možemo samo dobiti jedan metak u njega, mi
ne bi se onda reći o, zapravo sam

37
00:01:59,905 --> 00:02:04,360
potrebno 101 ili mi je trebalo x plus 20.

38
00:02:04,360 --> 00:02:07,910
Prekasno, već smo je proglasio
polje, a ako želimo dobiti 101 ili x

39
00:02:07,910 --> 00:02:12,050
plus 20, moramo proglasiti
potpuno različit niz,

40
00:02:12,050 --> 00:02:15,540
kopirati sve elemente polja
više, a onda imamo dovoljno.

41
00:02:15,540 --> 00:02:19,880
A što ako smo u krivu opet, što
ako mi zapravo treba 102 ili x plus 40,

42
00:02:19,880 --> 00:02:21,970
moramo to učiniti opet.

43
00:02:21,970 --> 00:02:26,250
Dakle, oni su vrlo kruti
za promjenu veličine naše podatke,

44
00:02:26,250 --> 00:02:29,360
ali ako ćemo povezati neke
osnove koje smo već

45
00:02:29,360 --> 00:02:33,230
naučili o pokazivače i objekata,
posebice pomoću dinamičke memorije

46
00:02:33,230 --> 00:02:36,180
Raspodjela s malloc smo
možete staviti ove dijelove zajedno

47
00:02:36,180 --> 00:02:40,960
Za stvaranje nove podatke structure-- A
pojedinačno povezani popis možemo say--

48
00:02:40,960 --> 00:02:45,400
koji nam omogućuje da raste i
smanjiti zbirku vrijednosti

49
00:02:45,400 --> 00:02:48,800
i nećemo imati nikakvu izgubiti prostora.

50
00:02:48,800 --> 00:02:53,320
>> Pa opet, mi zovemo tu ideju,
ovaj pojam, popis povezani.

51
00:02:53,320 --> 00:02:56,320
Konkretno, u ovom videu smo
govori o pojedinačno povezane liste,

52
00:02:56,320 --> 00:02:59,185
a zatim još jedan video ćemo razgovarati
oko dvostruko povezane liste, koje

53
00:02:59,185 --> 00:03:01,560
je samo varijacija na temu ovdje.

54
00:03:01,560 --> 00:03:05,200
No, popis s pojedinačno povezan
se sastoji od čvorova,

55
00:03:05,200 --> 00:03:08,559
čvorovi samo kao apstraktna term--
to je samo nešto što zovem

56
00:03:08,559 --> 00:03:10,350
to je neka vrsta
Struktura, u osnovi, ja sam?

57
00:03:10,350 --> 00:03:16,190
Samo ću nazvati node-- i to
čvor ima dva člana ili dva polja.

58
00:03:16,190 --> 00:03:20,300
Ima podataka, obično
broj, plovak lik,

59
00:03:20,300 --> 00:03:23,790
ili može biti neka druga vrsta podataka
da ste definiran tipa def.

60
00:03:23,790 --> 00:03:29,290
I ona sadrži pokazivač na
drugi čvor istog tipa.

61
00:03:29,290 --> 00:03:34,710
>> Dakle, imamo dvije stvari unutar
ovaj čvor, podataka i pokazivač

62
00:03:34,710 --> 00:03:36,380
na drugi čvor.

63
00:03:36,380 --> 00:03:39,370
A ako počnete zamišljati
to, možete razmišljati o tome

64
00:03:39,370 --> 00:03:42,280
kao lanac čvorova koji
spojeni zajedno.

65
00:03:42,280 --> 00:03:45,070
Imamo prvi čvor, to
sadrži podatke i pokazivač

66
00:03:45,070 --> 00:03:49,110
na drugi čvor, koji sadrži
Podaci, a pokazivač trećeg čvora.

67
00:03:49,110 --> 00:03:52,940
I tako to je razlog zašto smo ga poziva
povezani popis, oni su međusobno povezani.

68
00:03:52,940 --> 00:03:56,070
>> Što to posebna
čvor struktura izgledati?

69
00:03:56,070 --> 00:04:01,120
Pa, ako se sjećate iz našeg videa na
definiranje prilagođene vrste, s tipom def,

70
00:04:01,120 --> 00:04:05,400
možemo definirati structure-- i
unesite definirati strukturu kao što je ovaj.

71
00:04:05,400 --> 00:04:11,240
tyepdef struct sllist, a onda sam
koristim riječ vrijednosti ovdje proizvoljno

72
00:04:11,240 --> 00:04:13,891
naznačiti bilo koji tip podataka stvarno.

73
00:04:13,891 --> 00:04:16,890
Ti bi mogao proći na cijeli broj ili plovak,
možete imati sve što želite.

74
00:04:16,890 --> 00:04:19,389
To nije ograničeno na samo
cijeli brojevi, ili bilo što slično.

75
00:04:19,389 --> 00:04:22,790
Tako je vrijednost samo proizvoljna
tip podataka, a zatim pokazivač

76
00:04:22,790 --> 00:04:26,310
na drugi čvor istog tipa.

77
00:04:26,310 --> 00:04:29,690
>> Zatim, tu je malo ulov
ovdje definiranje strukture

78
00:04:29,690 --> 00:04:33,030
kada je self referencijalni struktura.

79
00:04:33,030 --> 00:04:35,340
Moram imati privremeni
ime moje strukture.

80
00:04:35,340 --> 00:04:37,640
Na kraju dana sam
očito želite nazvati

81
00:04:37,640 --> 00:04:43,030
SLL čvor, to je u konačnici novi
ime dio mog tipa definicije,

82
00:04:43,030 --> 00:04:47,450
ali ne mogu koristiti SLL čvor
u sredini ove.

83
00:04:47,450 --> 00:04:51,430
Razlog je, nisam
stvorio tip zove SLL čvor

84
00:04:51,430 --> 00:04:55,200
dok sam pogodio ovo konačna točka ovdje.

85
00:04:55,200 --> 00:04:59,720
Do tog trenutka, moram imati
još jedan način da se odnosi na ovu vrstu podataka.

86
00:04:59,720 --> 00:05:02,440
>> A to je self
referentna vrsta podataka.

87
00:05:02,440 --> 00:05:06,314
To, s tip podataka od
struktura koja sadrži podatke,

88
00:05:06,314 --> 00:05:08,480
a pokazivač na drugi
Struktura istog tipa.

89
00:05:08,480 --> 00:05:11,750
Pa moram biti u mogućnosti da se odnose na
Ova vrsta podataka barem privremeno,

90
00:05:11,750 --> 00:05:14,910
tako dajući mu privremeni
naziv struct sllist

91
00:05:14,910 --> 00:05:18,540
mi omogućuje onda reći da želite
pokazivač na drugi struct sllist,

92
00:05:18,540 --> 00:05:24,690
struct sllist zvijezda, a zatim
Nakon što sam završio definiciju,

93
00:05:24,690 --> 00:05:27,220
Ja sada mogu zvati upišite SLL čvor.

94
00:05:27,220 --> 00:05:30,520
>> Dakle, to je razlog zašto možete vidjeti postoji
privremeno ime ovdje,

95
00:05:30,520 --> 00:05:31,879
ali stalni ime ovdje.

96
00:05:31,879 --> 00:05:33,920
Ponekad možete vidjeti
definicije strukture,

97
00:05:33,920 --> 00:05:36,570
na primjer, koji nisu
samouprave referencijalni, da

98
00:05:36,570 --> 00:05:39,390
nemaju ime Specifier ovdje.

99
00:05:39,390 --> 00:05:43,040
To bi samo reći typedef struct,
otvori kovrčavu braće, a potom ga definirati.

100
00:05:43,040 --> 00:05:45,620
Ali, ako ste struct je self
referentna, jer to je jedan,

101
00:05:45,620 --> 00:05:49,010
morate da odredite
privremeni naziv tipa.

102
00:05:49,010 --> 00:05:51,310
Ali u konačnici, sada
da smo to učinili,

103
00:05:51,310 --> 00:05:53,620
mi samo može odnositi na
ovi čvorovi, ove jedinice,

104
00:05:53,620 --> 00:05:57,900
kao SLL čvorova za svrhe
ostatka ovog videa.

105
00:05:57,900 --> 00:06:00,900
>> U redu, tako da znamo kako
stvoriti povezani popis čvor.

106
00:06:00,900 --> 00:06:03,240
Znamo kako definirati
je povezani popis čvor.

107
00:06:03,240 --> 00:06:06,670
Sada, ako ćemo početi
ih koristi za prikupljanje podataka,

108
00:06:06,670 --> 00:06:10,360
postoji nekoliko operacija smo
morate razumjeti i raditi.

109
00:06:10,360 --> 00:06:12,860
Moramo znati kako stvoriti
je povezani popis iz ničega.

110
00:06:12,860 --> 00:06:14,901
Ako nema popisa već,
želimo pokrenuti jednu.

111
00:06:14,901 --> 00:06:16,960
Dakle, moramo biti u stanju
izraditi popis povezani,

112
00:06:16,960 --> 00:06:19,130
trebamo vjerojatno tražiti
kroz popis linkova

113
00:06:19,130 --> 00:06:21,830
pronaći element tražimo.

114
00:06:21,830 --> 00:06:24,430
Moramo biti u mogućnosti ubaciti
nove stvari u popisu,

115
00:06:24,430 --> 00:06:25,930
želimo da naša lista biti u mogućnosti da rastu.

116
00:06:25,930 --> 00:06:28,638
A isto tako, želimo biti u mogućnosti
za brisanje stvari iz našeg popisa,

117
00:06:28,638 --> 00:06:30,250
želimo da naša lista biti u mogućnosti smanjiti.

118
00:06:30,250 --> 00:06:32,160
I na kraju našeg
programa, a posebno

119
00:06:32,160 --> 00:06:34,550
Ako se sjećate da smo
dinamički dodjele memorije

120
00:06:34,550 --> 00:06:38,337
graditi ove popise obično,
želimo osloboditi sve te memorije

121
00:06:38,337 --> 00:06:39,670
kad završimo rad s njim.

122
00:06:39,670 --> 00:06:44,627
I tako moramo biti u mogućnosti obrisati
Cijeli povezani popis u jednom uspjeti prepad.

123
00:06:44,627 --> 00:06:46,460
Tako ćemo proći kroz
neke od tih operacija

124
00:06:46,460 --> 00:06:51,192
i kako bi ih vizualizirati,
govori u pseudokod kôd posebno.

125
00:06:51,192 --> 00:06:53,150
Dakle, želimo stvoriti
povezani popis, pa možda smo

126
00:06:53,150 --> 00:06:56,480
Želite definirati funkcije
s ovim prototip.

127
00:06:56,480 --> 00:07:01,690
SLL čvor zvijezda, stvarati, a ja sam prolazu
u jednom argumentu, neke proizvoljne podatke

128
00:07:01,690 --> 00:07:05,530
upišite opet, neke proizvoljne vrste podataka.

129
00:07:05,530 --> 00:07:10,482
Ali ja sam returning-- ovu funkciju treba
povratak na mene pokazivač, do pojedinačno

130
00:07:10,482 --> 00:07:11,190
povezani popis čvor.

131
00:07:11,190 --> 00:07:14,050
Opet, mi pokušavamo stvoriti
je povezani popis iz ničega,

132
00:07:14,050 --> 00:07:17,900
pa mi treba pokazivač
taj popis kad sam učinio.

133
00:07:17,900 --> 00:07:19,420
>> Pa što su koraci uključeni ovdje?

134
00:07:19,420 --> 00:07:20,960
Pa, prvo što sam
učiniti je dinamički

135
00:07:20,960 --> 00:07:22,550
izdvojiti prostor za novi čvor.

136
00:07:22,550 --> 00:07:26,689
Opet, mi smo ga stvara ni iz čega
zrak, tako da ćemo morati malloc prostora za to.

137
00:07:26,689 --> 00:07:28,480
I naravno, odmah
nakon što smo malloc,

138
00:07:28,480 --> 00:07:31,692
uvijek provjerite je li da su naši
pointer-- nismo dobili natrag null.

139
00:07:31,692 --> 00:07:33,650
Jer ako ćemo pokušati
popustljivost null pokazivača,

140
00:07:33,650 --> 00:07:36,190
ćemo trpjeti
segfault i ne želimo to.

141
00:07:36,190 --> 00:07:39,510
>> Zatim želimo ispuniti u polju,
želimo inicijalizirati polje vrijednosti

142
00:07:39,510 --> 00:07:41,690
i inicijalizirati slijedeće polje.

143
00:07:41,690 --> 00:07:45,450
A onda želimo to-- kraju kao
Funkcija prototip indicates-- želimo

144
00:07:45,450 --> 00:07:49,940
da se vrati pokazivač na SLL čvor.

145
00:07:49,940 --> 00:07:51,710
Dakle, ono što bi se ova izgledati vizualno?

146
00:07:51,710 --> 00:07:55,230
Pa, prvo ćemo dinamički
izdvojiti prostor za novi SLL čvor,

147
00:07:55,230 --> 00:07:58,320
pa smo malloc-- to
vizualni prikaz

148
00:07:58,320 --> 00:08:00,020
čvora smo upravo stvorili.

149
00:08:00,020 --> 00:08:02,757
A mi provjerite je li
to nije null-- u ovom slučaju,

150
00:08:02,757 --> 00:08:04,840
slika ne bi
pokazalo se ako je null,

151
00:08:04,840 --> 00:08:07,298
bismo ponestane memorije,
tako da smo dobri ići tamo.

152
00:08:07,298 --> 00:08:10,200
Dakle, sada smo na korak C,
inicijalizirati polje čvorovi vrijednost.

153
00:08:10,200 --> 00:08:12,280
Pa, na temelju ove funkcije
zvati Ja sam koristeći ovdje

154
00:08:12,280 --> 00:08:16,700
Izgleda da želim proći u 6,
pa ću 6 u polju vrijednosti.

155
00:08:16,700 --> 00:08:18,865
Sada, inicijalizirati slijedeće polje.

156
00:08:18,865 --> 00:08:21,640
Pa, što ću učiniti tamo,
ne postoji ništa sljedeći, pravo,

157
00:08:21,640 --> 00:08:23,600
to je jedina stvar na popisu.

158
00:08:23,600 --> 00:08:27,206
Zato što je sljedeća stvar na popisu?

159
00:08:27,206 --> 00:08:29,660
>> To ne bi trebalo ukazati na što, u pravu.

160
00:08:29,660 --> 00:08:33,600
Nema ništa drugo tamo, tako da ono što je
koncept znamo da je to nothing--

161
00:08:33,600 --> 00:08:35,638
upućuje na ništa?

162
00:08:35,638 --> 00:08:37,929
To bi trebao biti možda želimo
staviti null pokazivača tamo,

163
00:08:37,929 --> 00:08:40,178
a ja ću predstavljaju null
pokazivač kao samo crvenu kutiju,

164
00:08:40,178 --> 00:08:41,559
ne možemo ići dalje.

165
00:08:41,559 --> 00:08:44,430
Kao što ćemo vidjeti malo kasnije,
imat ćemo eventualno lanci

166
00:08:44,430 --> 00:08:46,330
strelica povezivanje
ovi čvorovi zajedno,

167
00:08:46,330 --> 00:08:48,480
ali kada hit
crvena kutija, to je null,

168
00:08:48,480 --> 00:08:51,150
ne možemo ići dalje,
to je kraj popisa.

169
00:08:51,150 --> 00:08:53,960
>> I na kraju, mi samo želimo
vratiti pokazivač na ovom čvoru.

170
00:08:53,960 --> 00:08:56,160
Tako ćemo ga zvati novi,
i da će se vratiti novi

171
00:08:56,160 --> 00:08:59,370
tako da se može koristiti u
god funkciju ga je stvorio.

172
00:08:59,370 --> 00:09:03,100
Dakle, tamo idemo, Mi smo stvorili pojedinačno
povezani popis čvor iz ničega,

173
00:09:03,100 --> 00:09:05,920
a sada imamo popis možemo raditi.

174
00:09:05,920 --> 00:09:08,260
>> Sada, recimo već
imaju veliki lanac,

175
00:09:08,260 --> 00:09:09,800
i želimo pronaći nešto u njemu.

176
00:09:09,800 --> 00:09:12,716
I želimo funkciju koja se događa
da se vrati true ili false, ovisno

177
00:09:12,716 --> 00:09:15,840
o tome da li postoji vrijednost u tom popisu.

178
00:09:15,840 --> 00:09:18,160
Funkcija prototip, ili
izjava za tu funkciju,

179
00:09:18,160 --> 00:09:23,320
može izgledati this-- bool naći i
onda želimo proći u dva argumenta.

180
00:09:23,320 --> 00:09:26,996
>> Prvi je pokazivač na
Prvi element popisa povezane.

181
00:09:26,996 --> 00:09:29,620
To je zapravo nešto što ćete
uvijek žele pratiti,

182
00:09:29,620 --> 00:09:33,110
i zapravo bi moglo biti nešto što
Možete čak staviti u globalnoj varijabli.

183
00:09:33,110 --> 00:09:35,360
Nakon što stvorite popis,
ti uvijek, uvijek

184
00:09:35,360 --> 00:09:38,990
želite pratiti vrlo
Prvi element liste.

185
00:09:38,990 --> 00:09:43,690
Na taj način možete se odnose na sve ostale
elemenata samo nakon lanac,

186
00:09:43,690 --> 00:09:47,300
bez da upućuje
netaknut svakog pojedinog elementa.

187
00:09:47,300 --> 00:09:50,920
Vi samo trebate pratiti prvi
jednom, ako su svi ti ulancane.

188
00:09:50,920 --> 00:09:52,460
>> A onda je druga stvar
mi prolaze u jednom

189
00:09:52,460 --> 00:09:54,376
je proizvoljno some--
Bez obzira na vrstu podataka smo

190
00:09:54,376 --> 00:09:59,640
u potrazi za ne postoji unutar
nadamo se jedan od čvorova u popisu.

191
00:09:59,640 --> 00:10:00,980
Pa što su koraci?

192
00:10:00,980 --> 00:10:04,250
Pa, prva stvar koju radimo je
stvaramo poprečnog pokazivač

193
00:10:04,250 --> 00:10:06,015
ukazujući na listi glavu.

194
00:10:06,015 --> 00:10:08,890
Pa, zašto mi to učiniti, već smo
imati pokazivač na listama glave,

195
00:10:08,890 --> 00:10:10,974
zašto ne bismo samo premjestiti da je jedan oko?

196
00:10:10,974 --> 00:10:13,140
Pa, kao što sam upravo rekao,
to je jako važno za nas

197
00:10:13,140 --> 00:10:17,580
uvijek pratiti
prvi element u listi.

198
00:10:17,580 --> 00:10:21,270
I to je zapravo bolje
stvoriti duplikat toga,

199
00:10:21,270 --> 00:10:25,350
i koristiti da bi se kretati tako mi nikada
slučajno odmaknuti, ili ćemo uvijek

200
00:10:25,350 --> 00:10:30,430
imaju pokazivač u nekom trenutku koji je
Pravo na prvom elementu popisa.

201
00:10:30,430 --> 00:10:33,290
Tako da je bolje stvoriti
Drugi koji koristimo za pomicanje.

202
00:10:33,290 --> 00:10:35,877
>> Onda smo samo usporediti li
Polje vrijednosti na tom čvoru

203
00:10:35,877 --> 00:10:38,960
je ono što tražimo, a ako je
Ne, mi samo premjestiti na sljedeći čvor.

204
00:10:38,960 --> 00:10:41,040
A mi bi da radi
više, i više, i više,

205
00:10:41,040 --> 00:10:44,811
dok ne bilo naći
element, ili ćemo udariti

206
00:10:44,811 --> 00:10:47,310
null-- smo stigli do kraja
popisa i to ne postoji.

207
00:10:47,310 --> 00:10:50,540
Ovaj nadamo trebao zvono zvoni
za vas kao samo linearno pretraživanje,

208
00:10:50,540 --> 00:10:54,430
mi smo samo replicira u
pojedinačno povezani popis strukture

209
00:10:54,430 --> 00:10:56,280
umjesto koristeći niz to učiniti.

210
00:10:56,280 --> 00:10:58,210
>> Dakle ovdje je primjer
popis pojedinačno povezani.

211
00:10:58,210 --> 00:11:00,043
Ovaj se sastoji od
pet čvorova, a imamo

212
00:11:00,043 --> 00:11:04,330
pointer na glavi od
Popis, koji se zove popis.

213
00:11:04,330 --> 00:11:07,385
Prva stvar koju želite učiniti je
opet, napravite obuhvaćanje pokazivač.

214
00:11:07,385 --> 00:11:09,760
Dakle, sada imamo dva pokazivače
koji ukazuju na istu stvar.

215
00:11:09,760 --> 00:11:15,025
>> Sada, obavijest i ovdje, nisam
moraju malloc bilo prostora za Trav.

216
00:11:15,025 --> 00:11:18,970
Nisam rekao Trav jednak malloc
nešto, da je čvor već postoji,

217
00:11:18,970 --> 00:11:21,160
da je prostor u memoriji već postoji.

218
00:11:21,160 --> 00:11:24,290
Dakle, sve sam zapravo radiš je
stvarajući još jedan pokazivač na nju.

219
00:11:24,290 --> 00:11:28,210
Neću mallocing dodatni
prostor, upravo su dva pokazivače

220
00:11:28,210 --> 00:11:31,370
ukazujući na istu stvar.

221
00:11:31,370 --> 00:11:33,710
>> Tako je 2 ono što tražim?

222
00:11:33,710 --> 00:11:37,220
Pa, ne, pa umjesto da sam
će se premjestiti na sljedeću.

223
00:11:37,220 --> 00:11:41,740
Tako je u osnovi, rekao bih,
trav jednak Trav sljedeći.

224
00:11:41,740 --> 00:11:43,630
Je 3 ono što ja tražim, ne.

225
00:11:43,630 --> 00:11:45,780
Tako sam i dalje ići
putem, dok na kraju

226
00:11:45,780 --> 00:11:48,690
doći do 6 što je ono što tražim
za temelje na funkciji poziva

227
00:11:48,690 --> 00:11:51,600
Imam na vrhu
tamo, pa sam učinio.

228
00:11:51,600 --> 00:11:54,150
>> Sad, što ako je element sam
tražite nije na popisu,

229
00:11:54,150 --> 00:11:55,510
Je li još uvijek ide na posao?

230
00:11:55,510 --> 00:11:57,120
Pa, primijetiti da je popis
Ovdje je suptilno različita,

231
00:11:57,120 --> 00:11:59,410
i to je još jedna stvar koja je
važno s povezanim popisima,

232
00:11:59,410 --> 00:12:01,780
ne morate sačuvati
ih u bilo kojem određenom redoslijedu.

233
00:12:01,780 --> 00:12:05,390
Možete ako želite, ali
možda ste već primjetili

234
00:12:05,390 --> 00:12:09,310
da nismo praćenje
što je broj elemenata smo na.

235
00:12:09,310 --> 00:12:13,150
>> I to je vrsta jednoj trgovini da mi
imati s povezanom popisu stihova polja,

236
00:12:13,150 --> 00:12:15,300
Je li to nemamo
izravnim pristupom više.

237
00:12:15,300 --> 00:12:18,150
Ne možemo samo reći, ja želim
ići na 0th elementa,

238
00:12:18,150 --> 00:12:21,410
ili 6. element moje polje,
što ja mogu učiniti u nizu.

239
00:12:21,410 --> 00:12:25,080
Ne mogu reći da želim ići na
0. element ili 6. elementa,

240
00:12:25,080 --> 00:12:30,360
ili 25. element mom popisu povezane,
nema indeks povezane s njima.

241
00:12:30,360 --> 00:12:33,660
I tako se to zapravo ne smeta
ako smo sačuvati naš popis u redu.

242
00:12:33,660 --> 00:12:36,080
Ako želite tebe
svakako može, ali postoji

243
00:12:36,080 --> 00:12:38,567
nema razloga zašto im je potrebno
očuvati u bilo kojem redoslijedu.

244
00:12:38,567 --> 00:12:40,400
Pa opet, pokušajmo i
naći 6 u ovom popisu.

245
00:12:40,400 --> 00:12:43,200
Pa, mi početi na
početak, ne nalazimo 6,

246
00:12:43,200 --> 00:12:47,690
a onda nećemo nastaviti nalaz
6, dok smo na kraju doći do ovdje.

247
00:12:47,690 --> 00:12:52,790
Tako sada Trav ukazuje na čvoru
sadrži 8, a šest je nije tamo.

248
00:12:52,790 --> 00:12:55,250
>> Dakle, sljedeći korak će biti
ići na sljedeću pokazivač,

249
00:12:55,250 --> 00:12:57,440
tako kažu trav jednak Trav sljedeći.

250
00:12:57,440 --> 00:13:00,750
Pa, Trav sljedeći, naznačeno
crveni okvir postoji, je null.

251
00:13:00,750 --> 00:13:03,020
Dakle, postoji nigdje drugdje
idu, pa u ovom trenutku

252
00:13:03,020 --> 00:13:06,120
možemo zaključiti da smo postigli
kraj popisa povezani,

253
00:13:06,120 --> 00:13:07,190
i 6 nije tamo.

254
00:13:07,190 --> 00:13:10,980
I to bi se vratio
netočno u ovom slučaju.

255
00:13:10,980 --> 00:13:14,540
>> U redu, kako ćemo umetnuti novi
čvor u popis povezani?

256
00:13:14,540 --> 00:13:17,310
Tako smo bili u mogućnosti stvoriti
je povezani popis niotkuda,

257
00:13:17,310 --> 00:13:19,370
ali vjerojatno želite
izgraditi lanac, a ne

258
00:13:19,370 --> 00:13:22,620
stvoriti hrpu različitih popisa.

259
00:13:22,620 --> 00:13:25,700
Želimo imati jedan popis koji
ima hrpa čvorova u njemu,

260
00:13:25,700 --> 00:13:28,040
Ne hrpa liste s jednim čvor.

261
00:13:28,040 --> 00:13:31,260
Dakle, ne možemo zadržati samo pomoću Napravite
Funkcija smo definirali ranije, sada smo

262
00:13:31,260 --> 00:13:33,860
želite umetnuti u
popis koji već postoji.

263
00:13:33,860 --> 00:13:36,499
>> Dakle ovom slučaju, idemo
proći u dva argumenta,

264
00:13:36,499 --> 00:13:39,290
pokazivač na glavu da
povezani popis koji želimo dodati.

265
00:13:39,290 --> 00:13:40,910
Opet, to je razlog zašto je tako
važno da se uvijek

266
00:13:40,910 --> 00:13:43,400
pratiti, jer
to je jedini način na koji smo stvarno

267
00:13:43,400 --> 00:13:46,690
moraju odnositi na cijeli popis
samo pokazivač na prvi element.

268
00:13:46,690 --> 00:13:49,360
Zato želimo proći u
pokazivač na taj prvi element,

269
00:13:49,360 --> 00:13:52,226
i što god mi vrijednost
želite dodati na popis.

270
00:13:52,226 --> 00:13:54,600
I na kraju ova funkcija
će se vratiti pokazivač

271
00:13:54,600 --> 00:13:57,980
za novog šefa popisu povezane.

272
00:13:57,980 --> 00:13:59,700
>> Koji su koraci uključeni ovdje?

273
00:13:59,700 --> 00:14:02,249
Pa, baš kao i sa stvaranje,
moramo dinamički alocirati

274
00:14:02,249 --> 00:14:05,540
prostor za novi čvor i provjerite
sigurno mi ne ponestane memorije, opet,

275
00:14:05,540 --> 00:14:07,150
jer mi koristimo malloc.

276
00:14:07,150 --> 00:14:09,080
Zatim želimo popuniti
i umetnite čvor,

277
00:14:09,080 --> 00:14:12,730
pa stavite broj, bez obzira na
Val je u čvor.

278
00:14:12,730 --> 00:14:17,310
Želimo umetnuti čvor na
početak popisa povezane.

279
00:14:17,310 --> 00:14:19,619
>> Postoji razlog što sam
želite to učiniti, i to

280
00:14:19,619 --> 00:14:21,910
moglo biti vrijedno uzimanje trenutak
za pauziranje video ovdje,

281
00:14:21,910 --> 00:14:25,860
i razmišljati o tome zašto bih želio
ubacite u početku povezan

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

283
00:14:26,589 --> 00:14:28,630
Opet, što sam spomenuo ranije
da ne stvarno

284
00:14:28,630 --> 00:14:33,020
smeta ako smo ga sačuvati u bilo
red, pa možda je to trag.

285
00:14:33,020 --> 00:14:36,040
A ste vidjeli što će se dogoditi ako
Želio to-- ili samo na sekundu

286
00:14:36,040 --> 00:14:37,360
Prije kad smo išli
kroz potragu si

287
00:14:37,360 --> 00:14:39,235
mogao vidjeti što bi moglo
dogoditi ako smo pokušali

288
00:14:39,235 --> 00:14:41,330
umetnuti na kraju liste.

289
00:14:41,330 --> 00:14:44,750
Jer mi nemaju
pokazivač na kraju liste.

290
00:14:44,750 --> 00:14:47,490
>> Dakle razlog da bih htio
umetnuti na početku,

291
00:14:47,490 --> 00:14:49,380
je zato što ja mogu učiniti odmah.

292
00:14:49,380 --> 00:14:52,730
Imam pokazivač na početku i
ćemo vidjeti u vizualnom u sekundi.

293
00:14:52,730 --> 00:14:55,605
Ali ako želite umetnuti na kraju,
Moram početi na početku,

294
00:14:55,605 --> 00:14:58,760
prošli sve do
kraj, a zatim ga pričvrstiti na.

295
00:14:58,760 --> 00:15:01,420
Dakle, to bi značilo da
umetanje na kraju liste

296
00:15:01,420 --> 00:15:04,140
će postati O n
rad, ide natrag

297
00:15:04,140 --> 00:15:06,720
u našu raspravu o
računalna složenost.

298
00:15:06,720 --> 00:15:10,140
To bi postati O n rada, gdje
kao popis dobio veći i veći,

299
00:15:10,140 --> 00:15:13,310
i veći, to će postati sve više i
teže tack nešto

300
00:15:13,310 --> 00:15:14,661
na je na kraju.

301
00:15:14,661 --> 00:15:17,410
Ali to je uvijek jako jednostavno
tack nešto na na početku,

302
00:15:17,410 --> 00:15:19,060
ti si uvijek na početku.

303
00:15:19,060 --> 00:15:21,620
>> I vidjet ćemo vizualni to opet.

304
00:15:21,620 --> 00:15:24,100
I onda odjednom smo učinili, jednom
smo umetnuli novi čvor,

305
00:15:24,100 --> 00:15:26,880
želimo vratiti našu pokazivač
novi šef popisu povezani, što

306
00:15:26,880 --> 00:15:29,213
jer smo umetanje Na
početak, zapravo će biti

307
00:15:29,213 --> 00:15:31,060
pokazivač na čvor smo upravo stvorili.

308
00:15:31,060 --> 00:15:33,280
Idemo vizualizirati to,
jer mislim da ću vam pomoći.

309
00:15:33,280 --> 00:15:36,661
>> Dakle, ovdje je naš popis, a sastoji se od
četiri elementa, čvor koji sadrži 15,

310
00:15:36,661 --> 00:15:38,410
što ukazuje na čvoru
sadrži 9, koji je

311
00:15:38,410 --> 00:15:41,370
ukazuje na čvor koji sadrži 13,
što ukazuje na čvor koji sadrži

312
00:15:41,370 --> 00:15:44,840
10, koji ima nula
Pokazivač kao svoj sljedeći pokazivač

313
00:15:44,840 --> 00:15:47,010
tako da je kraj popisa.

314
00:15:47,010 --> 00:15:50,200
Dakle, želimo umetanje
novi čvor s vrijednošću 12

315
00:15:50,200 --> 00:15:52,720
na početku ovog
Popis, što nam je činiti?

316
00:15:52,720 --> 00:15:58,770
Pa, prvo smo malloc prostor za
čvor, a onda smo stavili 12 tamo.

317
00:15:58,770 --> 00:16:02,211
>> Dakle, sada smo postignut
Odluka točka, zar ne?

318
00:16:02,211 --> 00:16:03,960
Imamo par
upućuje da smo mogli

319
00:16:03,960 --> 00:16:06,770
kretati, koje smo trebali pomaknuti prvi?

320
00:16:06,770 --> 00:16:09,250
Hoćemo li napraviti 12 točku
novi šef list--

321
00:16:09,250 --> 00:16:13,020
ili me ispričajte, trebali smo napraviti 12
ukazuju na staru glavu na popisu?

322
00:16:13,020 --> 00:16:15,319
Ili bismo trebali reći da je
Lista sada počinje u 12.

323
00:16:15,319 --> 00:16:17,110
Postoji razlika
tamo, a mi ćemo gledati

324
00:16:17,110 --> 00:16:19,870
na ono što se događa s obje u sekundi.

325
00:16:19,870 --> 00:16:23,350
>> No, to dovodi do
super tema za sidebar,

326
00:16:23,350 --> 00:16:26,280
što je to jedan od
trickiest stvari s povezanim popisima

327
00:16:26,280 --> 00:16:30,980
se dogovoriti pokazivače
u ispravnom redoslijedu.

328
00:16:30,980 --> 00:16:34,520
Ako premjestite stvari iz reda,
možete završiti slučajno

329
00:16:34,520 --> 00:16:36,050
orphaning ostatak liste.

330
00:16:36,050 --> 00:16:37,300
I ovdje je primjer toga.

331
00:16:37,300 --> 00:16:40,540
Dakle, idemo s idejom of--
Pa, upravo smo stvorili 12.

332
00:16:40,540 --> 00:16:43,180
Znamo 12 će biti
novi šef popisa,

333
00:16:43,180 --> 00:16:47,660
pa zašto ne bismo samo premjestiti
popis pokazivač ukazati tamo.

334
00:16:47,660 --> 00:16:49,070
>> U redu, tako da je dobro.

335
00:16:49,070 --> 00:16:51,560
Pa sad, gdje se 12 slijedeću točku?

336
00:16:51,560 --> 00:16:54,580
Mislim, vizualno možemo vidjeti
da će ukazati na 15.,

337
00:16:54,580 --> 00:16:57,250
kao ljudi to je stvarno očito za nas.

338
00:16:57,250 --> 00:17:00,300
Kako računalo zna?

339
00:17:00,300 --> 00:17:02,720
Nemamo ništa
ukazujući na 15 više, zar ne?

340
00:17:02,720 --> 00:17:05,869
>> Izgubili smo svaku mogućnost da se odnosi na 15.

341
00:17:05,869 --> 00:17:11,460
Ne možemo reći novi strelicu pored equals
nešto, nema ničega.

342
00:17:11,460 --> 00:17:13,510
U stvari, mi smo bez roditelja
ostatak popisa

343
00:17:13,510 --> 00:17:16,465
na taj način, mi smo
slučajno razbiti lanac.

344
00:17:16,465 --> 00:17:18,089
I sigurno ne želite to učiniti.

345
00:17:18,089 --> 00:17:20,000
>> Tako ćemo se vratiti i pokušati to opet.

346
00:17:20,000 --> 00:17:24,060
Možda je prava stvar za učiniti
je postaviti 12 je sljedeći pokazivač

347
00:17:24,060 --> 00:17:28,290
na staru glavu na popisu prvog,
onda možemo pomaknuti popis više.

348
00:17:28,290 --> 00:17:30,420
I, u stvari, da je
točno da bismo

349
00:17:30,420 --> 00:17:32,836
trebate slijediti kad smo
rad s jednostruko povezane liste.

350
00:17:32,836 --> 00:17:36,460
Mi uvijek želimo spojiti
Novi element u popisu,

351
00:17:36,460 --> 00:17:41,010
prije nego što smo uzeti takav
važan korak promjene

352
00:17:41,010 --> 00:17:43,360
gdje je voditelj popisa povezan je.

353
00:17:43,360 --> 00:17:46,740
Opet, to je takva temeljna stvar,
ne želimo izgubiti trag o tome.

354
00:17:46,740 --> 00:17:49,310
>> Dakle, želimo biti sigurni da
sve ulancane,

355
00:17:49,310 --> 00:17:52,040
Prije nego smo prešli tu pokazivač.

356
00:17:52,040 --> 00:17:55,300
I tako će to biti ispravan redoslijed,
što je za spajanje 12 na listi,

357
00:17:55,300 --> 00:17:57,630
onda kažu da se popis počinje 12.

358
00:17:57,630 --> 00:18:00,860
Ako smo rekli popis počinje u 12 i
a zatim pokušao spojiti 12 na listi,

359
00:18:00,860 --> 00:18:02,193
već smo vidjeli što se događa.

360
00:18:02,193 --> 00:18:04,920
Gubimo popis greškom.

361
00:18:04,920 --> 00:18:06,740
>> U redu, tako da još jedna stvar o čemu razgovarati.

362
00:18:06,740 --> 00:18:09,750
Što ako želimo riješiti
cijeli povezani popis odjednom?

363
00:18:09,750 --> 00:18:11,750
Opet, mi smo mallocing
sve to prostor, pa smo

364
00:18:11,750 --> 00:18:13,351
treba ga osloboditi kad završimo.

365
00:18:13,351 --> 00:18:15,350
Dakle, sada želimo obrisati
cijeli povezani popis.

366
00:18:15,350 --> 00:18:16,850
Pa, što želimo učiniti?

367
00:18:16,850 --> 00:18:20,460
>> Ako smo postigli nultu pokazivač, mi
želite prestati, inače, jednostavno izbrišite

368
00:18:20,460 --> 00:18:23,420
ostatak popisa, a zatim osloboditi me.

369
00:18:23,420 --> 00:18:28,890
Brisanje ostatak popisa,
a zatim osloboditi trenutni čvor.

370
00:18:28,890 --> 00:18:32,850
Što to zvuči kao,
koju tehniku ​​ima smo razgovarali

371
00:18:32,850 --> 00:18:35,440
o prije to zvuči kao?

372
00:18:35,440 --> 00:18:39,560
Brisanje i svi drugi, onda
vratiti i obrisati me.

373
00:18:39,560 --> 00:18:42,380
>> To je rekurzija smo napravili
Problem malo manji,

374
00:18:42,380 --> 00:18:46,910
Govorimo izbrisati svi
drugo, onda možete me izbrisati.

375
00:18:46,910 --> 00:18:50,940
I dalje niz cestu, koja čvor
reći će izbrisati svi ostali.

376
00:18:50,940 --> 00:18:53,940
Ali s vremenom ćemo na
točka u kojoj je popis ništavan,

377
00:18:53,940 --> 00:18:55,310
i to je naš osnovni scenarij.

378
00:18:55,310 --> 00:18:57,010
>> Tako ćemo pogledati ovaj,
i kako to može raditi.

379
00:18:57,010 --> 00:18:59,759
Dakle, ovdje je naš popis, to je ista
popis samo smo pričali o,

380
00:18:59,759 --> 00:19:00,980
a tu je korake.

381
00:19:00,980 --> 00:19:04,200
Ima puno teksta ovdje, ali
nadamo se vizualizacija će vam pomoći.

382
00:19:04,200 --> 00:19:08,557
>> Tako smo have-- i sam izvukao
do našeg stog okviri slici

383
00:19:08,557 --> 00:19:10,890
iz naše video na poziv dimnjaka,
i nadamo se sve to

384
00:19:10,890 --> 00:19:13,260
zajedno će vam pokazati što se događa.

385
00:19:13,260 --> 00:19:14,510
Dakle, ovdje je naš pseudokod broj.

386
00:19:14,510 --> 00:19:17,830
Ako dođe do null
pokazivač, zaustavi, inače,

387
00:19:17,830 --> 00:19:21,320
izbrisati ostatak popisa,
zatim osloboditi trenutni čvor.

388
00:19:21,320 --> 00:19:25,700
Tako sada, list--
pokazivač da smo

389
00:19:25,700 --> 00:19:28,410
prolaze uništiti bodova 12.

390
00:19:28,410 --> 00:19:33,340
12 nije null pointer, tako da smo
će izbrisati ostatak liste.

391
00:19:33,340 --> 00:19:35,450
>> Što se brisanja
Ostatak od nas koji su uključeni?

392
00:19:35,450 --> 00:19:37,950
Pa, to znači stvaranje
pozvati uništiti, govoreći

393
00:19:37,950 --> 00:19:42,060
da 15 je početak
Ostatak popisa želimo uništiti.

394
00:19:42,060 --> 00:19:47,480
I tako je poziv da uništi
12 je vrsta na čekanju.

395
00:19:47,480 --> 00:19:52,690
To je zamrznuta tamo, čekajući
pozvati uništiti 15, završiti svoj posao.

396
00:19:52,690 --> 00:19:56,280
>> Pa, 15 nije NULL pokazivač, te
pa to će reći, u redu,

397
00:19:56,280 --> 00:19:58,450
dobro, izbrisati ostatak liste.

398
00:19:58,450 --> 00:20:00,760
Ostatak popisa počinje
u 9, i tako samo ćemo

399
00:20:00,760 --> 00:20:04,514
pričekajte dok ne izbrišete sve
stvari, a onda se vratiti i obrisati me.

400
00:20:04,514 --> 00:20:06,680
Pa 9 će reći, dobro,
Nisam null pointer,

401
00:20:06,680 --> 00:20:09,020
tako izbrisati ostatak popisa odavde.

402
00:20:09,020 --> 00:20:11,805
I tako pokušati uništiti 13.

403
00:20:11,805 --> 00:20:15,550
13 kaže, nisam NULL pokazivač,
Ista stvar, to prolazi mužjak.

404
00:20:15,550 --> 00:20:17,930
10 nije NULL pokazivač, 10
sadrži null pokazivača,

405
00:20:17,930 --> 00:20:20,200
ali 10 je sama po sebi nije
null pokazivač upravo sada,

406
00:20:20,200 --> 00:20:22,470
i tako to prolazi mužjak previše.

407
00:20:22,470 --> 00:20:25,560
>> A sada popis bodove tamo, to
stvarno bi ukazati na some--

408
00:20:25,560 --> 00:20:28,710
ako sam imao više prostora u slici,
to bi ukazati na neke slučajnim prostora

409
00:20:28,710 --> 00:20:29,960
da ne znamo što je to.

410
00:20:29,960 --> 00:20:34,680
To je nulta pokazivač ipak, popis
je doslovno sada postavljena je vrijednost null.

411
00:20:34,680 --> 00:20:36,820
To pokazuje upravo u toj crvenoj kutiji.

412
00:20:36,820 --> 00:20:39,960
Došli smo null pointer, tako
možemo zaustaviti, a mi smo učinili.

413
00:20:39,960 --> 00:20:46,230
>> I tako da ljubičasta okvir now-- Na
vrh stack-- to je aktivni okvir,

414
00:20:46,230 --> 00:20:47,017
ali to je učinjeno.

415
00:20:47,017 --> 00:20:48,600
Ako smo postigli null pokazivača, zaustaviti.

416
00:20:48,600 --> 00:20:51,290
Mi ne radimo ništa, mi
ne može osloboditi null pokazivača,

417
00:20:51,290 --> 00:20:55,070
nismo malloc bilo
prostor, pa smo gotovi.

418
00:20:55,070 --> 00:20:57,590
Dakle tu funkciju okvira
je uništen, a mi

419
00:20:57,590 --> 00:21:00,930
resume-- smo pokupiti gdje smo ostavili
off sa sljedećim najvećim jedan, koji

420
00:21:00,930 --> 00:21:02,807
ovo tamno plavi okvir ovdje.

421
00:21:02,807 --> 00:21:04,390
Tako smo pokupiti tamo gdje smo stali.

422
00:21:04,390 --> 00:21:06,598
Izbrisali smo ostatak od
Popis je već, tako da sada smo

423
00:21:06,598 --> 00:21:08,000
će osloboditi trenutne čvorova.

424
00:21:08,000 --> 00:21:12,920
Tako sada možemo osloboditi ovaj čvor, a sada
Došli smo do kraja funkciju.

425
00:21:12,920 --> 00:21:16,810
I tako da funkcija okvir je uništen,
i mi pokupiti na svijetlo plave boje.

426
00:21:16,810 --> 00:21:20,650
>> Tako da says-- sam već done--
brisanje ostatak popisa, tako da

427
00:21:20,650 --> 00:21:23,140
osloboditi trenutni čvor.

428
00:21:23,140 --> 00:21:26,520
A sada žuti okvir
natrag na vrh dimnjaka.

429
00:21:26,520 --> 00:21:29,655
I tako, kao što vidite, mi smo sada
uništavanje popis s desna na lijevo.

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

431
00:21:33,710 --> 00:21:37,280
>> Što bi se dogodilo, ipak,
Ako smo učinili stvari na krivi način?

432
00:21:37,280 --> 00:21:39,410
Baš kao i kada smo pokušali
dodati element.

433
00:21:39,410 --> 00:21:41,909
Ako zabrljao lanac, ako
nismo povezati pokazivače

434
00:21:41,909 --> 00:21:44,690
u ispravnom redoslijedu, ako
Samo oslobodi prvi element,

435
00:21:44,690 --> 00:21:47,420
ako mi samo oslobodio
voditelj popisa, sada smo

436
00:21:47,420 --> 00:21:49,642
nema načina da se odnosi na
ostatak liste.

437
00:21:49,642 --> 00:21:51,350
I tako bismo imali
roditelja je sve,

438
00:21:51,350 --> 00:21:53,880
mi bi imali ono što je
naziva otjecanje memorije.

439
00:21:53,880 --> 00:21:56,800
Ako se sjećate iz našeg videa
na dinamičke dodjele memorije,

440
00:21:56,800 --> 00:21:58,650
to nije vrlo dobra stvar.

441
00:21:58,650 --> 00:22:00,810
>> Dakle, kao što sam rekao, ne postoji
više operacija

442
00:22:00,810 --> 00:22:04,010
da trebamo koristiti za rad
sa povezane popis učinkovito.

443
00:22:04,010 --> 00:22:08,430
A možda ste primijetili sam izostavljen jedan,
brisanje jednog elementa iz povezani

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

445
00:22:09,064 --> 00:22:10,980
Razlog zbog kojeg sam to učinio
je to je zapravo vrsta

446
00:22:10,980 --> 00:22:14,360
lukav razmišljati o tome kako izbrisati
jedan element iz pojedinačno

447
00:22:14,360 --> 00:22:15,600
povezani popis.

448
00:22:15,600 --> 00:22:19,950
Moramo biti u stanju preskočiti
nešto u popisu, koji

449
00:22:19,950 --> 00:22:22,975
znači da smo dobili na point-- mi
želite izbrisati ovu node--

450
00:22:22,975 --> 00:22:25,350
ali kako to napraviti tako da smo
ne gube bilo kakve informacije,

451
00:22:25,350 --> 00:22:30,530
moramo povezati ovo
čvor ovdje, ovdje.

452
00:22:30,530 --> 00:22:33,390
>> Tako sam vjerojatno učinio krivo
iz vizualne perspektive.

453
00:22:33,390 --> 00:22:36,830
Tako smo na početku naše
Popis, mi smo napreduje kroz,

454
00:22:36,830 --> 00:22:40,510
želimo obrisati ovaj čvor.

455
00:22:40,510 --> 00:22:43,440
Ako smo samo ga izbrisati,
smo slomljena lanac.

456
00:22:43,440 --> 00:22:45,950
Ovaj čvor ovdje
odnosi se na sve drugo,

457
00:22:45,950 --> 00:22:48,260
sadrži lanac od ovdje na van.

458
00:22:48,260 --> 00:22:51,190
>> Dakle, ono što trebamo učiniti je zapravo
nakon što smo dobili na ovom mjestu,

459
00:22:51,190 --> 00:22:56,670
je potrebno da se korak natrag jedan, i
spojiti ovaj čvor u ovaj čvor,

460
00:22:56,670 --> 00:22:58,590
pa onda možeš izbrisati
onaj u sredini.

461
00:22:58,590 --> 00:23:02,120
Ali pojedinačno povezani popisi ne
pružaju nam način da ide unatrag.

462
00:23:02,120 --> 00:23:05,160
Dakle, moramo ni čuvati
Dva naputke, i premjestiti ih

463
00:23:05,160 --> 00:23:09,527
vrsta off koraka, jedan iza
druge kao što idemo, ili doći do točke

464
00:23:09,527 --> 00:23:11,110
a zatim poslati još pokazivač preko.

465
00:23:11,110 --> 00:23:13,150
I kao što možete vidjeti, to
može dobiti malo neuredan.

466
00:23:13,150 --> 00:23:15,360
Srećom, imamo
još jedan način da se riješi to,

467
00:23:15,360 --> 00:23:17,810
kada govorimo o dvostruko povezanim popisima.

468
00:23:17,810 --> 00:23:20,720
>> Ja sam Doug Lloyd, ovo je CS50.

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