1
00:00:00,000 --> 00:00:02,832
>> [Predvaja glasba]

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

3
00:00:05,670 --> 00:00:08,560
>> Doug LLOYD: OK, tako da na
to točko v času,

4
00:00:08,560 --> 00:00:15,300
smo pokrili veliko osnov C.
Vemo veliko o spremenljivke, nizi,

5
00:00:15,300 --> 00:00:17,610
kazalci, vse to dobra stvar.

6
00:00:17,610 --> 00:00:21,610
Tisti, ki so vsi nekako zgradili
V videti kot temeljev,

7
00:00:21,610 --> 00:00:23,880
vendar lahko storimo več, kajne?

8
00:00:23,880 --> 00:00:27,930
Mi lahko združite stvari
skupaj v zanimive načine.

9
00:00:27,930 --> 00:00:31,010
>> In tako naredimo, da začnimo
da vejo iz tega, kar nam daje C,

10
00:00:31,010 --> 00:00:35,270
in začeli ustvarjati lastne podatke
struktur, ki uporabljajo te stavbe

11
00:00:35,270 --> 00:00:40,590
bloki skupaj nekaj narediti
res dragoceno, koristno.

12
00:00:40,590 --> 00:00:43,420
Eden od načinov, da lahko to storite
govoriti o zbirkah.

13
00:00:43,420 --> 00:00:48,360
Torej, če smo imeli eno vrsto podatkov
struktura za predstavitev zbirke

14
00:00:48,360 --> 00:00:51,030
od všeč vrednote, podobne vrednote.

15
00:00:51,030 --> 00:00:52,350
To bi bilo array.

16
00:00:52,350 --> 00:00:57,020
Imamo zbirke števil, ali
zbirke znakov, in tako naprej.

17
00:00:57,020 --> 00:01:00,890
>> Strukture so tudi neke vrste podatkov
struktura za zbiranje informacij,

18
00:01:00,890 --> 00:01:03,220
vendar to ni za zbiranje kot vrednote.

19
00:01:03,220 --> 00:01:08,090
To ponavadi meša različne vrste podatkov
skupaj znotraj enotnega prostora.

20
00:01:08,090 --> 00:01:10,750
Ampak to ni samo po sebi
uporablja za verigo skupaj

21
00:01:10,750 --> 00:01:16,920
ali pa se povežite skupaj podobno
predmetov, kot array.

22
00:01:16,920 --> 00:01:20,960
Polja so super za
element poglej gor, ampak se spomni

23
00:01:20,960 --> 00:01:24,262
da je zelo težko
vstaviti v array,

24
00:01:24,262 --> 00:01:26,470
če smo vstavitvijo
samega konca tega niza.

25
00:01:26,470 --> 00:01:29,730
>> In najboljši primer imam
za to je vstavljanje nekako.

26
00:01:29,730 --> 00:01:31,650
Če se spomnite naš video
na vstavljanja vrste,

27
00:01:31,650 --> 00:01:34,110
ni bilo veliko
odhodek vključen v ob

28
00:01:34,110 --> 00:01:37,970
da poberem elemente in jih prestavite
odročen se prilega nekaj

29
00:01:37,970 --> 00:01:41,290
v sredi svojega polja.

30
00:01:41,290 --> 00:01:44,690
Arrays trpijo tudi drugi
problem, ki je neprožnost.

31
00:01:44,690 --> 00:01:47,150
Ko izjavljamo niz,
smo dobili en strel na njo.

32
00:01:47,150 --> 00:01:49,790
Smo dobili reči, želim
to veliko elementov.

33
00:01:49,790 --> 00:01:51,940
Morda 100, morda pa
bilo 1000, bi bilo

34
00:01:51,940 --> 00:01:55,930
je x, kjer je x število, ki uporabniku
nam je dal na poziv ali na ukaz

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

36
00:01:56,630 --> 00:01:59,905
>> Vendar pa smo dobili le en strel na to, smo
ne dobijo potem pravijo oh, pravzaprav sem

37
00:01:59,905 --> 00:02:04,360
Potrebna 101, ali pa sem potreboval x plus 20.

38
00:02:04,360 --> 00:02:07,910
Prepozno, smo že razglasili
matrika, in če želimo dobiti 101 ali x

39
00:02:07,910 --> 00:02:12,050
plus 20, moramo razglasiti
povsem drugačen matrika,

40
00:02:12,050 --> 00:02:15,540
kopirati vse elemente matrike
več, in potem imamo dovolj.

41
00:02:15,540 --> 00:02:19,880
In kaj, če se bomo spet narobe, kaj
če bomo dejansko potrebovali 102, ali je X plus 40,

42
00:02:19,880 --> 00:02:21,970
moramo to storiti še enkrat.

43
00:02:21,970 --> 00:02:26,250
Torej, oni so zelo neprilagodljiv
za spreminjanje velikosti naše podatke,

44
00:02:26,250 --> 00:02:29,360
če pa združite nekaterih
od osnov, ki smo jih že

45
00:02:29,360 --> 00:02:33,230
spoznavali kazalci in struktur,
zlasti z uporabo dinamičnega pomnilnika

46
00:02:33,230 --> 00:02:36,180
Dodelitev z knjižnične funkcije malloc smo
lahko postavite te koščke

47
00:02:36,180 --> 00:02:40,960
ustvariti novo podatkovno structure-- a
posamič povezani seznam bomo morda say--

48
00:02:40,960 --> 00:02:45,400
ki nam omogoča, da raste in
shrink zbirko vrednot

49
00:02:45,400 --> 00:02:48,800
in ne bomo imeli nobenega zapravljen prostor.

50
00:02:48,800 --> 00:02:53,320
>> Torej še enkrat, pravimo to idejo,
ta pojem, A povezani seznam.

51
00:02:53,320 --> 00:02:56,320
Zlasti v tem videu smo
Govorimo o posamič povezani seznam,

52
00:02:56,320 --> 00:02:59,185
nato pa še video bomo govorili
približno dvakrat povezani seznam, ki

53
00:02:59,185 --> 00:03:01,560
je samo variacija na temo tukaj.

54
00:03:01,560 --> 00:03:05,200
Ampak posamič povezani seznam
je sestavljen iz vozlišč,

55
00:03:05,200 --> 00:03:08,559
vozlišča kot le abstraktna term--
to je samo nekaj Kličem

56
00:03:08,559 --> 00:03:10,350
to je neke vrste
struktura, v bistvu, da sem?

57
00:03:10,350 --> 00:03:16,190
Šele tekoč, da ga pokličete node-- in to
vozlišče ima dva člana, ali dve polji.

58
00:03:16,190 --> 00:03:20,300
Ima podatke, navadno
celo, plovec značaj,

59
00:03:20,300 --> 00:03:23,790
ali je lahko kakšna druga vrsta podatkov
ki ste jo določili s tipom def.

60
00:03:23,790 --> 00:03:29,290
In vsebuje kazalec na
drugo vozlišče istega tipa.

61
00:03:29,290 --> 00:03:34,710
>> Torej imamo dve stvari v notranjosti
to vozlišče, podatki in kazalec

62
00:03:34,710 --> 00:03:36,380
v drugo vozlišče.

63
00:03:36,380 --> 00:03:39,370
In če začnete vizualizirati
to, lahko si misliš o njem

64
00:03:39,370 --> 00:03:42,280
kot verige vozlišč, da
med seboj povezane.

65
00:03:42,280 --> 00:03:45,070
Imamo prvo vozlišče, ga
vsebuje podatke, in kazalec

66
00:03:45,070 --> 00:03:49,110
Na drugo vozlišče, ki vsebuje
Podatki, in kazalec na tretje vozlišče.

67
00:03:49,110 --> 00:03:52,940
In da je, zakaj smo ga poklical
povezani seznam, oni so med seboj povezani.

68
00:03:52,940 --> 00:03:56,070
>> Kaj to posebno
Struktura vozlišče izgledal?

69
00:03:56,070 --> 00:04:01,120
No, če se spomnimo iz naše video na
opredelitev vrst po meri, s tipom def,

70
00:04:01,120 --> 00:04:05,400
moremo opredeliti structure-- in
tip opredeliti strukturo, kot je ta.

71
00:04:05,400 --> 00:04:11,240
tyepdef struct sllist, in potem sem
uporabo vrednosti besedo tukaj samovoljno

72
00:04:11,240 --> 00:04:13,891
kažejo nobenih podatkovni tip res.

73
00:04:13,891 --> 00:04:16,890
Lahko prenese na celo število ali likvidna sredstva,
bi lahko imeli karkoli hočeš.

74
00:04:16,890 --> 00:04:19,389
To ni omejen samo
cela, ali kaj podobnega.

75
00:04:19,389 --> 00:04:22,790
Torej vrednost je samo poljubna
podatkovni tip in nato kazalec

76
00:04:22,790 --> 00:04:26,310
v drugo vozlišče iste vrste.

77
00:04:26,310 --> 00:04:29,690
>> Zdaj pa je malo ulov
tukaj pri opredeljevanju strukture

78
00:04:29,690 --> 00:04:33,030
ko je struktura samo referenčna.

79
00:04:33,030 --> 00:04:35,340
Moram imeti začasna
ime za mojo strukturo.

80
00:04:35,340 --> 00:04:37,640
Ob koncu dneva I
očitno želijo, da ga pokličete

81
00:04:37,640 --> 00:04:43,030
sll vozlišče, ki je na koncu novega
naštejemo del moje definicije tipa,

82
00:04:43,030 --> 00:04:47,450
vendar ne morem uporabljati SLL vozlišče
v sredini tega.

83
00:04:47,450 --> 00:04:51,430
Razlog je, nimam
ustvaril vrsto imenovano SLL vozlišče

84
00:04:51,430 --> 00:04:55,200
dokler nisem udaril to zadnjo točko tukaj.

85
00:04:55,200 --> 00:04:59,720
Do te točke, sem imeti
še en način, da se sklicuje na te vrste podatkov.

86
00:04:59,720 --> 00:05:02,440
>> In to je samo
referenčni podatkovni tip.

87
00:05:02,440 --> 00:05:06,314
To, S tip podatkov
struktura, ki vsebuje podatke,

88
00:05:06,314 --> 00:05:08,480
in kazalec na drugo
Struktura istega tipa.

89
00:05:08,480 --> 00:05:11,750
Tako da moram imeti možnost, da se nanašajo na
Ta podatkovni tip vsaj začasno,

90
00:05:11,750 --> 00:05:14,910
tako da mu daje začasna
ime struct sllist

91
00:05:14,910 --> 00:05:18,540
mi omogoča, da potem reči Hočem
kazalec na drugo struct sllist,

92
00:05:18,540 --> 00:05:24,690
struct sllist zvezda, nato pa
ko sem zaključila z opredelitvijo,

93
00:05:24,690 --> 00:05:27,220
Zdaj lahko imenujemo ta tip sll vozlišče.

94
00:05:27,220 --> 00:05:30,520
>> Torej, to je, zakaj vidite tam
začasno ime tukaj,

95
00:05:30,520 --> 00:05:31,879
ampak stalna ime tukaj.

96
00:05:31,879 --> 00:05:33,920
Včasih boste morda videli
definicije strukture,

97
00:05:33,920 --> 00:05:36,570
na primer, da niso
samo referenčna, da

98
00:05:36,570 --> 00:05:39,390
nimajo tu ime določilo.

99
00:05:39,390 --> 00:05:43,040
To bi šele rekli typedef struct,
odpreti kodrasti opornico, nato pa ga definirati.

100
00:05:43,040 --> 00:05:45,620
Ampak, če ste struct je self
referenčno, saj je to ena stvar,

101
00:05:45,620 --> 00:05:49,010
morate določite
začasno ime tipa.

102
00:05:49,010 --> 00:05:51,310
Ampak na koncu, zdaj
da smo to storili,

103
00:05:51,310 --> 00:05:53,620
bomo lahko sklicujejo le na
ti vozlišča te enote,

104
00:05:53,620 --> 00:05:57,900
kot SLL vozlišč za namene
preostalega ta video.

105
00:05:57,900 --> 00:06:00,900
>> Vse je v redu, tako da vemo, kako
ustvarijo povezani seznam vozlišče.

106
00:06:00,900 --> 00:06:03,240
Vemo, kako opredeliti
vezavni seznam vozlišče.

107
00:06:03,240 --> 00:06:06,670
Zdaj, če bomo za začetek
jih uporabljajo za zbiranje informacij,

108
00:06:06,670 --> 00:06:10,360
tam je nekaj operacij smo
morajo razumeti in delati.

109
00:06:10,360 --> 00:06:12,860
Moramo vedeti, kako ustvariti
vezavni seznam iz zraka.

110
00:06:12,860 --> 00:06:14,901
Če ni seznam že,
želimo začeti eno.

111
00:06:14,901 --> 00:06:16,960
Torej moramo biti sposobni
ustvariti povezan seznam,

112
00:06:16,960 --> 00:06:19,130
moramo verjetno iskati
po seznamu povezavo

113
00:06:19,130 --> 00:06:21,830
poiščite element, ki ga iščemo.

114
00:06:21,830 --> 00:06:24,430
Moramo biti sposobni vstaviti
nove stvari v seznamu,

115
00:06:24,430 --> 00:06:25,930
želimo naš seznam, da bi lahko rasla.

116
00:06:25,930 --> 00:06:28,638
In podobno, želimo, da bi lahko
izbrisati stvari iz našega seznama,

117
00:06:28,638 --> 00:06:30,250
želimo naš seznam, da bi lahko skrči.

118
00:06:30,250 --> 00:06:32,160
In na koncu našega
programi, zlasti

119
00:06:32,160 --> 00:06:34,550
če se spomnimo, da smo
dinamično dodeljevanje pomnilnika

120
00:06:34,550 --> 00:06:38,337
za izgradnjo te sezname običajno,
želimo osvoboditi vse te spomin

121
00:06:38,337 --> 00:06:39,670
ko končamo delo z njim.

122
00:06:39,670 --> 00:06:44,627
In zato moramo biti sposobni izbrisati
Celoten povezani seznam, v enem ne Nalet.

123
00:06:44,627 --> 00:06:46,460
Torej pojdiva skozi
nekateri od teh postopkov

124
00:06:46,460 --> 00:06:51,192
in kako bi jih vizualizirati,
govoril v psevdokoda kodo posebej.

125
00:06:51,192 --> 00:06:53,150
Torej želimo ustvariti
povezani seznam, tako da morda smo

126
00:06:53,150 --> 00:06:56,480
želeli določiti funkcijo
s tem prototipom.

127
00:06:56,480 --> 00:07:01,690
sll vozlišče zvezda, ustvarjanje, in sem mimo
v enem argumentu, nekateri samovoljno podatki

128
00:07:01,690 --> 00:07:05,530
tip spet neke samovoljno vrste podatkov.

129
00:07:05,530 --> 00:07:10,482
Ampak jaz sem returning-- to funkcijo naj bi
vrne k meni kazalec, da za enkrat

130
00:07:10,482 --> 00:07:11,190
povezani seznam vozlišče.

131
00:07:11,190 --> 00:07:14,050
Spet smo poskušali ustvariti
vezavni seznam iz zraka,

132
00:07:14,050 --> 00:07:17,900
tako da moram kazalec na
ta seznam, ko bom končal.

133
00:07:17,900 --> 00:07:19,420
>> Torej, kaj so koraki, ki sodelujejo tukaj?

134
00:07:19,420 --> 00:07:20,960
No, prva stvar, ki sem
tekoč storiti, je dinamično

135
00:07:20,960 --> 00:07:22,550
dodeli prostor za novo vozlišče.

136
00:07:22,550 --> 00:07:26,689
Spet smo ga ustvarili iz tanke
zraka, zato moramo malloc prostora za njo.

137
00:07:26,689 --> 00:07:28,480
In seveda takoj
ko smo malloc,

138
00:07:28,480 --> 00:07:31,692
smo vedno preverite, da je naš
pointer-- nismo dobili nazaj null.

139
00:07:31,692 --> 00:07:33,650
Ker če bomo poskušali
Priklanjanje null kazalec,

140
00:07:33,650 --> 00:07:36,190
bomo trpeti
segfault in ne želimo, da.

141
00:07:36,190 --> 00:07:39,510
>> Potem smo želeli zapolniti na tem področju,
želimo inicializacijo polja vrednosti

142
00:07:39,510 --> 00:07:41,690
in inicializacijo naslednje polje.

143
00:07:41,690 --> 00:07:45,450
In potem smo se želeli to-- koncu kot
Funkcija prototip indicates-- želimo

144
00:07:45,450 --> 00:07:49,940
vrne kazalec na SLL vozlišče.

145
00:07:49,940 --> 00:07:51,710
Torej, kaj bi to izgledal vizualno?

146
00:07:51,710 --> 00:07:55,230
No, najprej bomo dinamično
dodeli prostor za novo SLL vozliščem

147
00:07:55,230 --> 00:07:58,320
zato smo malloc-- da je
vizualna reprezentacija

148
00:07:58,320 --> 00:08:00,020
vozlišča smo pravkar ustvarili.

149
00:08:00,020 --> 00:08:02,757
In smo preverite,
to ni null-- v tem primeru,

150
00:08:02,757 --> 00:08:04,840
slika ne bi imela
prikazano gor, če je bila nična,

151
00:08:04,840 --> 00:08:07,298
mi pa bi zmanjkalo pomnilnika,
tako da smo na dobri poti tja.

152
00:08:07,298 --> 00:08:10,200
Torej, zdaj smo na korak C,
inicializacijo polja vozlišča vrednosti.

153
00:08:10,200 --> 00:08:12,280
No, glede na to funkcijo
poklical sem z igro,

154
00:08:12,280 --> 00:08:16,700
Izgleda želim opraviti v 6,
tako da bom 6 v polju vrednosti.

155
00:08:16,700 --> 00:08:18,865
Zdaj, inicializacijo naslednje polje.

156
00:08:18,865 --> 00:08:21,640
No, kaj bom tam naredil,
nič zraven, kajne,

157
00:08:21,640 --> 00:08:23,600
to je edino v seznamu.

158
00:08:23,600 --> 00:08:27,206
Torej, kaj je naslednja stvar na seznamu?

159
00:08:27,206 --> 00:08:29,660
>> To ne bi smelo poudariti, da nič, kajne.

160
00:08:29,660 --> 00:08:33,600
Nič drugega ni, kaj je
koncept vemo, da je to nothing--

161
00:08:33,600 --> 00:08:35,638
kazalci na nič?

162
00:08:35,638 --> 00:08:37,929
Treba bi bilo morda želimo
postaviti null kazalec tam,

163
00:08:37,929 --> 00:08:40,178
in bom predstavljajo null
kazalec kot le rdeče polje,

164
00:08:40,178 --> 00:08:41,559
ne more iti več naprej.

165
00:08:41,559 --> 00:08:44,430
Kot bomo videli malo kasneje,
bomo morali sčasoma verige

166
00:08:44,430 --> 00:08:46,330
puščic povezovanje
ti vozlišča skupaj,

167
00:08:46,330 --> 00:08:48,480
vendar, ko ste zadeli
rdeče polje, ki je nična,

168
00:08:48,480 --> 00:08:51,150
ne moremo iti dalje,
da je konec seznama.

169
00:08:51,150 --> 00:08:53,960
>> In nazadnje, hočemo samo
vrne kazalec na tem vozlišču.

170
00:08:53,960 --> 00:08:56,160
Torej bomo ga pokličete nov,
in se bo vrnil novo

171
00:08:56,160 --> 00:08:59,370
tako da se lahko uporablja pri
karkoli funkcija je ustvaril.

172
00:08:59,370 --> 00:09:03,100
Torej tam gremo, smo ustvarili posamezno
povezani seznam vozlišče iz zraka,

173
00:09:03,100 --> 00:09:05,920
in zdaj imamo seznam moremo delati.

174
00:09:05,920 --> 00:09:08,260
>> Zdaj, recimo, smo že
imajo veliko verigo

175
00:09:08,260 --> 00:09:09,800
in želimo, da bi našli nekaj v njej.

176
00:09:09,800 --> 00:09:12,716
In želimo funkcijo, ki se dogaja
vrne true ali false, odvisno

177
00:09:12,716 --> 00:09:15,840
o tem, ali obstaja vrednost na tem seznamu.

178
00:09:15,840 --> 00:09:18,160
Funkcija prototip, ali
Izjava za to funkcijo,

179
00:09:18,160 --> 00:09:23,320
bi izgledal this-- bool najti, in
potem želimo prenesti v dveh argumentov.

180
00:09:23,320 --> 00:09:26,996
>> Prvi kazalec na
Prvi element povezani seznam.

181
00:09:26,996 --> 00:09:29,620
To je pravzaprav nekaj, kar boste
vedno želeli, da bi spremljali,

182
00:09:29,620 --> 00:09:33,110
in dejansko je lahko nekaj, kar
si celo dal v globalne spremenljivke.

183
00:09:33,110 --> 00:09:35,360
Ko ustvarite seznam,
vedno, vedno

184
00:09:35,360 --> 00:09:38,990
želijo, da bi spremljali zelo
Prvi element seznama.

185
00:09:38,990 --> 00:09:43,690
Na ta način se lahko nanašajo na vse druge
Elementi, ki jih samo po verigo,

186
00:09:43,690 --> 00:09:47,300
ne da voditi kazalce
nedotaknjen, da vsak element.

187
00:09:47,300 --> 00:09:50,920
Morate le, da spremljate prvi
ena, če oni vsi priklenjen skupaj.

188
00:09:50,920 --> 00:09:52,460
>> In potem druga stvar
smo mimo znova

189
00:09:52,460 --> 00:09:54,376
je samovoljno some--
ne glede na tip podatkov smo

190
00:09:54,376 --> 00:09:59,640
išče obstajajo znotraj
upamo eden izmed vozlišč v seznamu.

191
00:09:59,640 --> 00:10:00,980
Torej, kaj so koraki?

192
00:10:00,980 --> 00:10:04,250
No, prva stvar, ki mi je
ustvarimo prečni kazalec

193
00:10:04,250 --> 00:10:06,015
kaže na seznamih glavo.

194
00:10:06,015 --> 00:10:08,890
No, zakaj smo to storili, smo že
ima kazalec na seznamih verjeti,

195
00:10:08,890 --> 00:10:10,974
zakaj ne bomo samo premaknete, da je eden okoli?

196
00:10:10,974 --> 00:10:13,140
No, kot sem rekel,
to je res pomembno za nas

197
00:10:13,140 --> 00:10:17,580
da vedno spremljate
Prvi element v seznamu.

198
00:10:17,580 --> 00:10:21,270
In zato je dejansko boljša
ustvariti dvojnik, ki,

199
00:10:21,270 --> 00:10:25,350
in uporabo, da se premaknete okoli, tako da ne bomo nikoli
nehote odmakne, ali smo vedno

200
00:10:25,350 --> 00:10:30,430
imajo kazalec na neki točki, ki je
prav na prvi element seznama.

201
00:10:30,430 --> 00:10:33,290
Torej je bolje, da ustvarite
Drugi, ki jih uporabljamo za premikanje.

202
00:10:33,290 --> 00:10:35,877
>> Potem smo samo primerjati, ali
polje vrednost na tem vozlišču

203
00:10:35,877 --> 00:10:38,960
je tisto, kar smo iskali, in če je
Ne, samo premaknete na naslednje vozlišče.

204
00:10:38,960 --> 00:10:41,040
In bomo vztrajati početje, da
več, in več, in več,

205
00:10:41,040 --> 00:10:44,811
dokler ne bomo niti našli
element, ali smo zadeli

206
00:10:44,811 --> 00:10:47,310
null-- smo dosegli konec
seznama in je ni tam.

207
00:10:47,310 --> 00:10:50,540
To bi, upajmo, zvonil zvonec
za vas, kot samo linearno iskanje,

208
00:10:50,540 --> 00:10:54,430
smo samo posnemajo v
za enkrat povezani seznam struktura

209
00:10:54,430 --> 00:10:56,280
namesto z matriko, da to storite.

210
00:10:56,280 --> 00:10:58,210
>> Torej, tukaj je primer
za enkrat povezani seznam.

211
00:10:58,210 --> 00:11:00,043
Ta je sestavljen iz
pet vozlišč, in imamo

212
00:11:00,043 --> 00:11:04,330
kazalec vodjo
Seznam, ki se imenuje seznam.

213
00:11:04,330 --> 00:11:07,385
Prva stvar, ki jo želite storiti, je
ponovno ustvarite, da prečkanje kazalec.

214
00:11:07,385 --> 00:11:09,760
Tako da imamo zdaj dve kazalce
ki kažejo na isto stvar.

215
00:11:09,760 --> 00:11:15,025
>> Zdaj, obvestilo tudi tukaj, nisem
morali malloc nobenega prostora za trav.

216
00:11:15,025 --> 00:11:18,970
Nisem rekel, trav enaka malloc
nekaj, da je vozlišče že obstaja,

217
00:11:18,970 --> 00:11:21,160
da je prostor v pomnilniku že obstaja.

218
00:11:21,160 --> 00:11:24,290
Torej, vse sem pravzaprav počne, je
ustvariti nov kazalec na njej.

219
00:11:24,290 --> 00:11:28,210
Nisem mallocing dodaten
prostora, samo imajo zdaj dve kazalce

220
00:11:28,210 --> 00:11:31,370
kaže na isto stvar.

221
00:11:31,370 --> 00:11:33,710
>> Torej je 2, kar iščem?

222
00:11:33,710 --> 00:11:37,220
No, no, tako da namesto da sem
dogaja, da se premaknete na naslednjo.

223
00:11:37,220 --> 00:11:41,740
Torej v bistvu jaz bi rekel,
trav trav enaka naslednji.

224
00:11:41,740 --> 00:11:43,630
3, kar iščem, ne.

225
00:11:43,630 --> 00:11:45,780
Tako sem še naprej iti
skozi, dokler sčasoma

226
00:11:45,780 --> 00:11:48,690
priti do 6, ki je tisto, kar sem iskal
Za temelji na klicu funkcije

227
00:11:48,690 --> 00:11:51,600
Moram na vrhu
tam, in tako sem storil.

228
00:11:51,600 --> 00:11:54,150
>> Zdaj, kaj če je element sem
iščete, ni na seznamu,

229
00:11:54,150 --> 00:11:55,510
se še vedno dogaja, da deluje?

230
00:11:55,510 --> 00:11:57,120
No, opazil, da se seznam
tukaj je nekoliko drugačna,

231
00:11:57,120 --> 00:11:59,410
in to je še ena stvar, ki je
pomembno pri povezanih seznamov,

232
00:11:59,410 --> 00:12:01,780
nimate ohraniti
jih v določenem vrstnem redu.

233
00:12:01,780 --> 00:12:05,390
Lahko, če hočeš, ampak
ste morda že opazili

234
00:12:05,390 --> 00:12:09,310
da nismo sledenja
kaj več element smo na.

235
00:12:09,310 --> 00:12:13,150
>> In to je nekako eni trgovini, ki smo
imajo s povezano seznamu verzov nizi,

236
00:12:13,150 --> 00:12:15,300
se nimamo
bralno več.

237
00:12:15,300 --> 00:12:18,150
Ne moremo samo reči, želim
iti v 0th element,

238
00:12:18,150 --> 00:12:21,410
ali 6. element mojega array,
ki lahko storim v matriki.

239
00:12:21,410 --> 00:12:25,080
Ne morem reči, želim iti na
0. element, ali 6. element,

240
00:12:25,080 --> 00:12:30,360
ali 25. element mojega povezanega seznama,
ni indeks, povezane z njimi.

241
00:12:30,360 --> 00:12:33,660
In tako v resnici ne važno
če želimo ohraniti naš seznam v vrstnem redu.

242
00:12:33,660 --> 00:12:36,080
Če želite, da vas
seveda lahko, vendar pa je

243
00:12:36,080 --> 00:12:38,567
Nobenega razloga ni, zakaj jih potrebujejo za
shranijo v poljubnem vrstnem redu.

244
00:12:38,567 --> 00:12:40,400
Torej še enkrat, poskusimo in
našli 6 na tem seznamu.

245
00:12:40,400 --> 00:12:43,200
No, bomo začeti izvajati
začenja, ne bomo našli 6,

246
00:12:43,200 --> 00:12:47,690
in potem bomo še naprej ne najde
6, dokler ne bomo na koncu dobili tukaj.

247
00:12:47,690 --> 00:12:52,790
Torej, zdaj trav kaže na vozlišču
vsebuje 8, in šest ni tam.

248
00:12:52,790 --> 00:12:55,250
>> Tako da bi naslednji korak
da gredo na naslednjo kazalec,

249
00:12:55,250 --> 00:12:57,440
tako pravijo trav trav enaka naslednji.

250
00:12:57,440 --> 00:13:00,750
No, trav zraven, označena z
rdeče polje obstaja, je nična.

251
00:13:00,750 --> 00:13:03,020
Torej obstaja nikjer drugje na
iti, in zato na tej točki

252
00:13:03,020 --> 00:13:06,120
lahko sklepamo, da smo dosegli
Konec povezani seznam,

253
00:13:06,120 --> 00:13:07,190
in 6 ne noter.

254
00:13:07,190 --> 00:13:10,980
In bi se vrnil
false v tem primeru.

255
00:13:10,980 --> 00:13:14,540
>> OK, kako vstavite novo
vozlišče v povezano seznamu?

256
00:13:14,540 --> 00:13:17,310
Torej smo bili sposobni ustvariti
vezavni seznam od nikoder,

257
00:13:17,310 --> 00:13:19,370
vendar smo verjetno želeli
izgradnjo verige in ne

258
00:13:19,370 --> 00:13:22,620
ustvariti kup različnih seznamov.

259
00:13:22,620 --> 00:13:25,700
Želimo, da imajo en seznam, ki
ima kup vozlišč v njem,

260
00:13:25,700 --> 00:13:28,040
ne kup seznamov z enim vozliščem.

261
00:13:28,040 --> 00:13:31,260
Torej ne moremo kar naprej uporabljate Ustvari
Funkcija smo opredelili že prej, zdaj smo

262
00:13:31,260 --> 00:13:33,860
želite vstaviti v
Seznam, ki že obstaja.

263
00:13:33,860 --> 00:13:36,499
>> Torej tem primeru bomo
prenesti v dveh argumentov,

264
00:13:36,499 --> 00:13:39,290
kazalec z glavo, ki
povezani seznam, ki ga želimo dodati.

265
00:13:39,290 --> 00:13:40,910
Še enkrat, to je razlog, zakaj je tako
pomembno je, da smo vedno

266
00:13:40,910 --> 00:13:43,400
spremljate to, ker
to je edini način, da res

267
00:13:43,400 --> 00:13:46,690
imajo, da se nanašajo na celoten seznam
samo s kazalcem na prvem elementu.

268
00:13:46,690 --> 00:13:49,360
Torej želimo prenesti v
kazalec na ta prvi element,

269
00:13:49,360 --> 00:13:52,226
in ne glede na vrednost, ki jo
želite dodati na seznam.

270
00:13:52,226 --> 00:13:54,600
In na koncu je ta funkcija
se dogaja, da se vrnete kazalec

271
00:13:54,600 --> 00:13:57,980
novemu glavo povezanega seznama.

272
00:13:57,980 --> 00:13:59,700
>> Kateri koraki so vključeni tukaj?

273
00:13:59,700 --> 00:14:02,249
No, tako kot pri ustvarjanju,
moramo dinamično dodeli

274
00:14:02,249 --> 00:14:05,540
prostor za novo vozlišče, in preverite,
prepričan, da ne bo zmanjkalo pomnilnika, še enkrat,

275
00:14:05,540 --> 00:14:07,150
ker smo s pomočjo malloc.

276
00:14:07,150 --> 00:14:09,080
Potem želimo zapolnijo
in vstavite vozlišče,

277
00:14:09,080 --> 00:14:12,730
tako dal številko, ne glede na
val je v vozlišče.

278
00:14:12,730 --> 00:14:17,310
Želimo, da vstavite vozlišče na
začetek povezani seznam.

279
00:14:17,310 --> 00:14:19,619
>> Obstaja razlog, da sem
želeli, da to stori, in to

280
00:14:19,619 --> 00:14:21,910
bi bilo vredno vzeti trenutek
da začasno ustavite video tukaj,

281
00:14:21,910 --> 00:14:25,860
in razmišljati o tem, zakaj bi hotel
vstavite na začetku vezana

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

283
00:14:26,589 --> 00:14:28,630
Spet sem že prej omenil
da to ni res

284
00:14:28,630 --> 00:14:33,020
važno, če smo ga ohranili v vseh
Da, tako da morda je to namig.

285
00:14:33,020 --> 00:14:36,040
In ste videli, kaj bi se zgodilo, če bi
Želeli to-- ali samo sekundo

286
00:14:36,040 --> 00:14:37,360
nazaj, ko smo šli
skozi iskanje si

287
00:14:37,360 --> 00:14:39,235
lahko videli, kaj lahko
se zgodilo, če bomo skušali

288
00:14:39,235 --> 00:14:41,330
vstaviti na koncu seznama.

289
00:14:41,330 --> 00:14:44,750
Ker ne bomo imeli
kazalec na koncu seznama.

290
00:14:44,750 --> 00:14:47,490
>> Torej razlog, da bi si želel
vstaviti na začetku,

291
00:14:47,490 --> 00:14:49,380
je zato, ker sem lahko to storite takoj.

292
00:14:49,380 --> 00:14:52,730
Imam kazalec na začetku, in
bomo to videli v vizualni v sekundi.

293
00:14:52,730 --> 00:14:55,605
Ampak, če hočem vstaviti na koncu,
Moram začeti na začetku,

294
00:14:55,605 --> 00:14:58,760
prečkanje vso pot do
konec, in ga nato prečenje.

295
00:14:58,760 --> 00:15:01,420
Tako, da bi to pomenilo, da je
vstavljanje na koncu seznama

296
00:15:01,420 --> 00:15:04,140
bi postala o n
delovanje, vrača

297
00:15:04,140 --> 00:15:06,720
za našo razpravo
računska zahtevnost.

298
00:15:06,720 --> 00:15:10,140
To bi postalo o n delovanja, kjer
kot seznam dobil večji in večji,

299
00:15:10,140 --> 00:15:13,310
in večje, da bomo postali bolj in
težje prečenje nekaj

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

301
00:15:14,661 --> 00:15:17,410
Ampak to je vedno zelo enostavno
prečenje nekaj na na začetku,

302
00:15:17,410 --> 00:15:19,060
ste vedno na začetku.

303
00:15:19,060 --> 00:15:21,620
>> In bomo videli še vizualni tega.

304
00:15:21,620 --> 00:15:24,100
In potem, ko bomo končali enkrat
smo vstavili novo vozlišče,

305
00:15:24,100 --> 00:15:26,880
želimo vrniti našo kazalec
novi vodja povezanega seznama, ki

306
00:15:26,880 --> 00:15:29,213
saj smo vstavljanje Na
začenši bo dejansko

307
00:15:29,213 --> 00:15:31,060
kazalec na vozlišče smo pravkar ustvarili.

308
00:15:31,060 --> 00:15:33,280
Oglejmo vizualizirati to,
ker mislim, da bom pomagal.

309
00:15:33,280 --> 00:15:36,661
>> Torej, tukaj je naš seznam, je sestavljena iz
štirje elementi, vozlišče, ki vsebuje 15,

310
00:15:36,661 --> 00:15:38,410
kar kaže na vozlišču
ki vsebuje 9, ki

311
00:15:38,410 --> 00:15:41,370
kaže na vozlišče, ki vsebuje 13,
kar kaže na vozlišče vsebuje

312
00:15:41,370 --> 00:15:44,840
10, ki ima null
kazalec kot svoji naslednji kazalec

313
00:15:44,840 --> 00:15:47,010
tako da je konec seznama.

314
00:15:47,010 --> 00:15:50,200
Zato želimo, da vstavite
Novo vozlišče z vrednostjo 12

315
00:15:50,200 --> 00:15:52,720
na začetku tega
seznam, kaj naj naredimo?

316
00:15:52,720 --> 00:15:58,770
No, najprej smo malloc prostor za
vozlišče, nato pa dal 12 noter.

317
00:15:58,770 --> 00:16:02,211
>> Torej, zdaj smo doseže
Odločitev točka, kajne?

318
00:16:02,211 --> 00:16:03,960
Imamo nekaj
kazalci, da smo lahko

319
00:16:03,960 --> 00:16:06,770
premakniti, eden od njiju naj gremo najprej?

320
00:16:06,770 --> 00:16:09,250
Moramo narediti 12 točk do
Novi vodja list--

321
00:16:09,250 --> 00:16:13,020
ali oprostite, moramo narediti 12
opozarjajo na stari glavi seznama?

322
00:16:13,020 --> 00:16:15,319
Ali bi morali reči, da je
seznam zdaj se začne pri 12.

323
00:16:15,319 --> 00:16:17,110
Tam je razlikovati
tam, in bomo pogled

324
00:16:17,110 --> 00:16:19,870
kaj se zgodi z obema v sekundi.

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

326
00:16:23,350 --> 00:16:26,280
ki je, da je eden izmed
najtežavnejših stvari s povezanimi seznami

327
00:16:26,280 --> 00:16:30,980
je urediti kazalce
v pravilnem zaporedju.

328
00:16:30,980 --> 00:16:34,520
Če ste premakniti stvari v okvari,
lahko končajo po nesreči

329
00:16:34,520 --> 00:16:36,050
orphaning preostanek seznama.

330
00:16:36,050 --> 00:16:37,300
In tukaj je primer tega.

331
00:16:37,300 --> 00:16:40,540
Torej, pojdimo z idejo of--
dobro, smo pravkar ustvarili 12.

332
00:16:40,540 --> 00:16:43,180
Vemo 12 se bo
novi vodja seznama

333
00:16:43,180 --> 00:16:47,660
in zakaj ne bi kar preselila
seznam kazalec tam točko.

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

335
00:16:49,070 --> 00:16:51,560
Torej, zdaj, ko pa 12 naslednjo točko?

336
00:16:51,560 --> 00:16:54,580
Mislim, vizualno lahko vidimo,
da bo to imelo za 15,

337
00:16:54,580 --> 00:16:57,250
saj človeka je res očitno, da nas.

338
00:16:57,250 --> 00:17:00,300
Kako računalnik vedeli?

339
00:17:00,300 --> 00:17:02,720
Nimamo ničesar
kaže, da 15 več, kajne?

340
00:17:02,720 --> 00:17:05,869
>> Izgubili smo kakršno koli možnost, da se sklicujem na 15.

341
00:17:05,869 --> 00:17:11,460
Ne moremo reči, novo puščico zraven enaka
nekaj, nič ni tam.

342
00:17:11,460 --> 00:17:13,510
V bistvu smo osiroteli
preostanek seznama

343
00:17:13,510 --> 00:17:16,465
s tem, ki smo jih
po nesreči zlomili verigo.

344
00:17:16,465 --> 00:17:18,089
In mi zagotovo ne želite, da to storim.

345
00:17:18,089 --> 00:17:20,000
>> Torej vrnimo se in poskusite s tem še enkrat.

346
00:17:20,000 --> 00:17:24,060
Mogoče je prava stvar
je določiti 12 na naslednjo kazalec

347
00:17:24,060 --> 00:17:28,290
na stari glavi seznama prvega,
potem lahko gremo seznam čez.

348
00:17:28,290 --> 00:17:30,420
In z dejstvom, da je
pravilno, da bomo

349
00:17:30,420 --> 00:17:32,836
morate slediti, ko smo
delo s posamezno povezano seznama.

350
00:17:32,836 --> 00:17:36,460
Vedno smo želeli povezati
Nov element v seznamu,

351
00:17:36,460 --> 00:17:41,010
preden smo vzeli to vrsto
Pomemben korak spreminjanja

352
00:17:41,010 --> 00:17:43,360
kjer je vodja povezanega seznama je.

353
00:17:43,360 --> 00:17:46,740
Še enkrat, da je tako temeljna stvar,
ne želimo, da bo zmanjkalo tem.

354
00:17:46,740 --> 00:17:49,310
>> Zato želimo zagotoviti, da
vse je priklenjen skupaj,

355
00:17:49,310 --> 00:17:52,040
preden gremo ta kazalec.

356
00:17:52,040 --> 00:17:55,300
In tako bi bilo to v pravilnem vrstnem redu,
ki je povezati 12 na seznamu,

357
00:17:55,300 --> 00:17:57,630
potem pa pravijo, da se seznam začne 12.

358
00:17:57,630 --> 00:18:00,860
Če smo rekli, seznam se začne pri 12 in
nato poskuša povezati 12 na seznamu,

359
00:18:00,860 --> 00:18:02,193
smo že videli, kaj se zgodi.

360
00:18:02,193 --> 00:18:04,920
Izgubimo seznam po pomoti.

361
00:18:04,920 --> 00:18:06,740
>> OK, še ena stvar, da govoriti o tem.

362
00:18:06,740 --> 00:18:09,750
Kaj pa, če želimo, da se znebite
celotno povezan seznam naenkrat?

363
00:18:09,750 --> 00:18:11,750
Spet smo mallocing
vse to prostor, in tako smo

364
00:18:11,750 --> 00:18:13,351
morate sprostiti, ko bomo končali.

365
00:18:13,351 --> 00:18:15,350
Torej, zdaj smo želeli izbrisati
celoten povezani seznam.

366
00:18:15,350 --> 00:18:16,850
No, kaj želimo narediti?

367
00:18:16,850 --> 00:18:20,460
>> Če smo dosegli null kazalec smo
želeli ustaviti, sicer šele izbrisati

368
00:18:20,460 --> 00:18:23,420
ostali na seznamu, nato pa me je osvobodil.

369
00:18:23,420 --> 00:18:28,890
Izbrišite preostanek seznama,
in nato sprostite trenutno vozlišče.

370
00:18:28,890 --> 00:18:32,850
Kaj to zvok všeč,
kaj tehniko smo govorili

371
00:18:32,850 --> 00:18:35,440
o prej pa to zvok všeč?

372
00:18:35,440 --> 00:18:39,560
Izbriši vsakogar drugega, potem
vrnil in izbrisati me.

373
00:18:39,560 --> 00:18:42,380
>> To je rekurzija, smo tokrat na
problem malo manjši,

374
00:18:42,380 --> 00:18:46,910
smo govoriš izbrisati vsakogar
drugega, potem lahko izbrišete me.

375
00:18:46,910 --> 00:18:50,940
In še naprej po cesti, ki vozlišče
bodo rekli, izbrisati vsi ostali.

376
00:18:50,940 --> 00:18:53,940
Ampak na koncu bomo dobili do
točka, kjer je seznam null,

377
00:18:53,940 --> 00:18:55,310
in to je naša baza primera.

378
00:18:55,310 --> 00:18:57,010
>> Tako da je lahko pogled na to,
in kako bi to lahko delovalo.

379
00:18:57,010 --> 00:18:59,759
Torej, tukaj je naš seznam, to je enako
Seznam smo samo govoriš,

380
00:18:59,759 --> 00:19:00,980
in tam je korake.

381
00:19:00,980 --> 00:19:04,200
Tam je veliko besedila tukaj, ampak
upajmo, da bo vizualizacija pomaga.

382
00:19:04,200 --> 00:19:08,557
>> Tako smo have-- in tudi jaz potegnil
up naši konzoli okvirjev sliki

383
00:19:08,557 --> 00:19:10,890
iz naše video na klic nizov,
in upajmo, da vse to

384
00:19:10,890 --> 00:19:13,260
skupaj vam bo pokazal, kaj se dogaja.

385
00:19:13,260 --> 00:19:14,510
Torej, tukaj je naša psevdokoda koda.

386
00:19:14,510 --> 00:19:17,830
Če bomo dosegli null
kazalec, nehaj, sicer

387
00:19:17,830 --> 00:19:21,320
izbrisati ostanek seznama,
nato sprostiti trenutno vozlišče.

388
00:19:21,320 --> 00:19:25,700
Torej sedaj, list--
kazalec, da smo

389
00:19:25,700 --> 00:19:28,410
poteka v uničiti točk, do 12.

390
00:19:28,410 --> 00:19:33,340
12 ni null kazalec, tako da smo
dogaja, da se črta preostanek seznama.

391
00:19:33,340 --> 00:19:35,450
>> Kaj je izbrisali
ostali vpleteni?

392
00:19:35,450 --> 00:19:37,950
No, to pomeni izdelavo
klic, da se uniči, rekoč:

393
00:19:37,950 --> 00:19:42,060
da 15 je na začetku
Preostanek seznamu želimo uničiti.

394
00:19:42,060 --> 00:19:47,480
In zato je poziv, da se uniči
12 je nekako na čakanju.

395
00:19:47,480 --> 00:19:52,690
Prav tam je zamrznjen, čakanja na
klic, da se uniči 15, da konča svoje delo.

396
00:19:52,690 --> 00:19:56,280
>> No, 15 ni null kazalec, in
tako da je hotel reči, vse v redu,

397
00:19:56,280 --> 00:19:58,450
dobro, izbrišite preostanek seznama.

398
00:19:58,450 --> 00:20:00,760
Preostanek seznama začne
ob 9., tako da bomo in samo

399
00:20:00,760 --> 00:20:04,514
počakajte, dokler ne boste izbrisali vse,
stvari, potem pa pridi nazaj in izbrisati me.

400
00:20:04,514 --> 00:20:06,680
No 9 dogaja reči, dobro,
Nisem null kazalec,

401
00:20:06,680 --> 00:20:09,020
tako izbrisati ostanek seznam od tukaj.

402
00:20:09,020 --> 00:20:11,805
In zato poskusite in uničiti 13.

403
00:20:11,805 --> 00:20:15,550
13 pravi, da nisem null kazalec,
Ista stvar, saj prehaja buck.

404
00:20:15,550 --> 00:20:17,930
10 ni null kazalec, 10
vsebuje null kazalec,

405
00:20:17,930 --> 00:20:20,200
ampak 10 je sam po sebi ni
null kazalec prav zdaj,

406
00:20:20,200 --> 00:20:22,470
in tako prehaja buck preveč.

407
00:20:22,470 --> 00:20:25,560
>> In zdaj seznam točk tam, ga
Res bi opozoril, da some--

408
00:20:25,560 --> 00:20:28,710
če bi imel več prostora v sliki,
da bi opozoril na nekaj naključno prostor

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

410
00:20:29,960 --> 00:20:34,680
To je null kazalec, čeprav seznam
je dobesedno sedaj nastavljena je vrednost null.

411
00:20:34,680 --> 00:20:36,820
To se kaže prav znotraj tega rdečega polja.

412
00:20:36,820 --> 00:20:39,960
Dosegli smo null kazalec, tako
moremo ustaviti, in smo končali.

413
00:20:39,960 --> 00:20:46,230
>> In da vijolična okvir je now-- Na
Vrh stack-- da je aktivna okvir,

414
00:20:46,230 --> 00:20:47,017
vendar pa je to storjeno.

415
00:20:47,017 --> 00:20:48,600
Če smo dosegli ničelni kazalec, stop.

416
00:20:48,600 --> 00:20:51,290
Mi ne storiti ničesar, smo
ni mogel znebiti null kazalec,

417
00:20:51,290 --> 00:20:55,070
nismo malloc koli
prostor, in tako smo storili.

418
00:20:55,070 --> 00:20:57,590
Torej, to funkcijo okvirja
uniči, in smo

419
00:20:57,590 --> 00:21:00,930
resume-- bomo pick up, kjer se nam z leve
off z naslednjo najvišjo enega, ki

420
00:21:00,930 --> 00:21:02,807
je ta temno modra frame tukaj.

421
00:21:02,807 --> 00:21:04,390
Tako smo dvignili tam, kjer smo končali.

422
00:21:04,390 --> 00:21:06,598
Mi črta ostalega
seznam že, zdaj smo

423
00:21:06,598 --> 00:21:08,000
bo osvobodil sedanjih vozlišč.

424
00:21:08,000 --> 00:21:12,920
Torej, zdaj smo lahko osvobodi to vozlišče, in zdaj
smo prišli do konca funkcije.

425
00:21:12,920 --> 00:21:16,810
In tako je ta funkcija okvir uničena,
in smo se dvignili na svetlo modri.

426
00:21:16,810 --> 00:21:20,650
>> Tako je says-- sem že done--
brisanje preostanek seznama, tako da

427
00:21:20,650 --> 00:21:23,140
sprostiti trenutno vozlišče.

428
00:21:23,140 --> 00:21:26,520
In zdaj je dobil rumeni okvir je
nazaj na vrhu kupa.

429
00:21:26,520 --> 00:21:29,655
In tako, kot vidite, mi smo zdaj
uničevanje seznama od desne proti levi.

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

431
00:21:33,710 --> 00:21:37,280
>> Kaj bi se zgodilo, čeprav,
če smo naredili stvari v napačno smer?

432
00:21:37,280 --> 00:21:39,410
Tako kot ko smo poskušali
dodati element.

433
00:21:39,410 --> 00:21:41,909
Če bomo zamočil verige, če je
nismo povezati kazalce

434
00:21:41,909 --> 00:21:44,690
v pravilnem vrstnem redu, če bomo
Samo sprosti prvi element,

435
00:21:44,690 --> 00:21:47,420
če smo le osvobodil
Vodja seznamu, zdaj smo

436
00:21:47,420 --> 00:21:49,642
ne način, da se sklicujem
preostanek seznama.

437
00:21:49,642 --> 00:21:51,350
In tako bi imeli
osiroteli vse,

438
00:21:51,350 --> 00:21:53,880
mi pa bi imeli kaj
imenujemo pomnilnika.

439
00:21:53,880 --> 00:21:56,800
Če se spomnite iz naše video
na dinamično dodeljevanje pomnilnika,

440
00:21:56,800 --> 00:21:58,650
da ni zelo dobra stvar.

441
00:21:58,650 --> 00:22:00,810
>> Torej, kot sem rekel, ni
več operacij

442
00:22:00,810 --> 00:22:04,010
da moramo uporabiti za delo
učinkovito povezani seznam.

443
00:22:04,010 --> 00:22:08,430
In ste morda opazili izpustijo enega sem,
brisanje en sam element iz povezanega

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

445
00:22:09,064 --> 00:22:10,980
Razlog, da sem storil, da
je, da je pravzaprav neke vrste

446
00:22:10,980 --> 00:22:14,360
težavno, da razmišljajo o tem, kako izbrisati
en sam element od A enkrat

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

448
00:22:15,600 --> 00:22:19,950
Moramo biti sposobni preskočiti
Nekaj ​​na seznamu, ki je

449
00:22:19,950 --> 00:22:22,975
pomeni, da smo prišli do Point-- mi
želite izbrisati ta node--

450
00:22:22,975 --> 00:22:25,350
ampak, da bi bi bilo, zato smo
ne izgubijo vse informacije,

451
00:22:25,350 --> 00:22:30,530
moramo povezati ta
node tukaj, tukaj.

452
00:22:30,530 --> 00:22:33,390
>> Torej sem verjetno naredil narobe
vizualnega vidika.

453
00:22:33,390 --> 00:22:36,830
Torej smo na začetku našega
seznam, mi nadaljujemo skozi,

454
00:22:36,830 --> 00:22:40,510
želimo izbrisati to vozlišče.

455
00:22:40,510 --> 00:22:43,440
Če smo ga šele izbrisati,
smo zlomili verigo.

456
00:22:43,440 --> 00:22:45,950
To vozlišče tukaj
nanaša na vse ostalo,

457
00:22:45,950 --> 00:22:48,260
da vsebuje verigo od tu naprej.

458
00:22:48,260 --> 00:22:51,190
>> Torej, kaj moramo storiti, dejansko
potem, ko smo prišli do te točke,

459
00:22:51,190 --> 00:22:56,670
se moramo korak nazaj eno, in
povezati to vozlišče v to vozlišče,

460
00:22:56,670 --> 00:22:58,590
tako da bomo lahko nato izbrišite
tista na sredini.

461
00:22:58,590 --> 00:23:02,120
Ampak posamič povezani seznami ne
da nam je pot nazaj.

462
00:23:02,120 --> 00:23:05,160
Zato moramo bodisi obdržati
dva kazalca, in jih premakniti

463
00:23:05,160 --> 00:23:09,527
nekako off koraku, eden za
drugo, ko gremo, ali priti do točke

464
00:23:09,527 --> 00:23:11,110
in nato pošlje drugo kazalec skozi.

465
00:23:11,110 --> 00:23:13,150
In kot vidite, jo
lahko dobili malo grdo.

466
00:23:13,150 --> 00:23:15,360
Na srečo smo imeli
še en način rešiti da,

467
00:23:15,360 --> 00:23:17,810
ko govorimo o dvakrat povezanih seznamov.

468
00:23:17,810 --> 00:23:20,720
>> Sem Doug Lloyd, to je CS50.

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