1
00:00:00,000 --> 00:00:02,832
>> [Speel van musiek]

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

3
00:00:05,670 --> 00:00:08,560
>> DOUG LLOYD: OK, so op
hierdie punt in die kursus,

4
00:00:08,560 --> 00:00:15,300
Ons het 'n groot deel van die basiese beginsels van C. gedek
Ons weet 'n baie oor veranderlikes, skikkings,

5
00:00:15,300 --> 00:00:17,610
wysers, alles wat goeie dinge.

6
00:00:17,610 --> 00:00:21,610
Dit is al die soort van gebou
in te sien as die grondbeginsels,

7
00:00:21,610 --> 00:00:23,880
maar ons kan meer reg doen nie,?

8
00:00:23,880 --> 00:00:27,930
Ons kan dinge kombineer
saam in 'n interessante maniere.

9
00:00:27,930 --> 00:00:31,010
>> En so laat doen, laat ons begin
tot tak uit wat C gee ons,

10
00:00:31,010 --> 00:00:35,270
en begin om ons eie data te skep
strukture gebruik van hierdie gebou

11
00:00:35,270 --> 00:00:40,590
blokke saam om iets te doen
regtig waardevol, nuttig.

12
00:00:40,590 --> 00:00:43,420
Een manier waarop ons kan dit doen, is
om te praat oor versamelings.

13
00:00:43,420 --> 00:00:48,360
So Tot dusver het ons een soort data het
struktuur verteenwoordig versamelings

14
00:00:48,360 --> 00:00:51,030
van hou waardes, dieselfde waardes.

15
00:00:51,030 --> 00:00:52,350
Dit sou 'n verskeidenheid wees.

16
00:00:52,350 --> 00:00:57,020
Ons het versamelings van heelgetalle, of
versamelings van karakters en so aan.

17
00:00:57,020 --> 00:01:00,890
>> Strukture word ook soort van 'n data
struktuur vir die insameling van inligting,

18
00:01:00,890 --> 00:01:03,220
maar dit is nie vir die insameling soos waardes.

19
00:01:03,220 --> 00:01:08,090
Dit meng gewoonlik verskillende tipes data
saam binnekant van 'n enkele vak.

20
00:01:08,090 --> 00:01:10,750
Maar dit is nie self
gebruik om ketting saam

21
00:01:10,750 --> 00:01:16,920
of maak saam soortgelyke
items, soos 'n skikking.

22
00:01:16,920 --> 00:01:20,960
Skikkings is groot vir
element kyk, maar onthou

23
00:01:20,960 --> 00:01:24,262
dat dit baie moeilik
in te voeg in 'n skikking,

24
00:01:24,262 --> 00:01:26,470
tensy ons die inbring by
die einde van daardie skikking.

25
00:01:26,470 --> 00:01:29,730
>> En die beste voorbeeld Ek het
want dit is invoeging soort.

26
00:01:29,730 --> 00:01:31,650
As jy ons video onthou
op invoeging soort,

27
00:01:31,650 --> 00:01:34,110
daar was 'n baie
koste wat betrokke is in wat

28
00:01:34,110 --> 00:01:37,970
af te haal elemente, en skuif
uit die manier om iets te pas

29
00:01:37,970 --> 00:01:41,290
in die middel van jou skikking.

30
00:01:41,290 --> 00:01:44,690
Skikkings ook ly van 'n ander
probleem, wat is onbuigsaamheid.

31
00:01:44,690 --> 00:01:47,150
Wanneer ons verklaar 'n skikking,
ons kry een skoot op dit.

32
00:01:47,150 --> 00:01:49,790
Ons kry om te sê, ek wil
hierdie elemente.

33
00:01:49,790 --> 00:01:51,940
Kan wees 100, kan dit
wees 1000, kan dit

34
00:01:51,940 --> 00:01:55,930
wees x waar x is 'n getal wat die gebruiker
het ons op 'n vinnige of by die opdrag

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

36
00:01:56,630 --> 00:01:59,905
>> Maar ons kry net een skoot op dit, ons
kry nie dan sê oh, eintlik ek

37
00:01:59,905 --> 00:02:04,360
nodig 101, of ek x plus 20 nodig.

38
00:02:04,360 --> 00:02:07,910
Te laat, het ons reeds verklaar dat die
skikking, en as ons wil om te kry 101 of x

39
00:02:07,910 --> 00:02:12,050
plus 20, ons het om te verklaar
'n heeltemal ander skikking,

40
00:02:12,050 --> 00:02:15,540
kopieer al die elemente van die skikking
oor, en dan het ons genoeg.

41
00:02:15,540 --> 00:02:19,880
En wat as ons verkeerd is weer, wat
As ons werklik nodig het 102, of x plus 40,

42
00:02:19,880 --> 00:02:21,970
ons moet dit weer te doen.

43
00:02:21,970 --> 00:02:26,250
Sodat hulle is baie onbuigsaam
vir die grootte van ons data,

44
00:02:26,250 --> 00:02:29,360
maar as ons saam 'n paar te kombineer
van die basiese beginsels wat ons reeds

45
00:02:29,360 --> 00:02:33,230
geleer het oor wysers en strukture,
in die besonder die gebruik van dinamiese geheue

46
00:02:33,230 --> 00:02:36,180
toekenning met malloc, ons
kan hierdie stukke saam te stel

47
00:02:36,180 --> 00:02:40,960
om 'n nuwe data structure-- n skep
enkel geskakelde lys ons dalk say--

48
00:02:40,960 --> 00:02:45,400
wat ons toelaat om te groei en
krimp 'n versameling van waardes

49
00:02:45,400 --> 00:02:48,800
en ons sal nie enige gemors ruimte.

50
00:02:48,800 --> 00:02:53,320
>> So weer, hierdie idee noem ons,
hierdie idee, 'n geskakelde lys.

51
00:02:53,320 --> 00:02:56,320
In die besonder, in hierdie video ons
praat oor enkel gekoppel lys

52
00:02:56,320 --> 00:02:59,185
en dan nog 'n video sal ons praat
oor dubbeld geskakelde lyste, wat

53
00:02:59,185 --> 00:03:01,560
is net 'n variasie op 'n tema hier.

54
00:03:01,560 --> 00:03:05,200
Maar 'n enkel geskakelde lys
bestaan ​​uit nodes,

55
00:03:05,200 --> 00:03:08,559
nodes om net 'n abstrakte term--
dit is net iets wat ek roep

56
00:03:08,559 --> 00:03:10,350
dit is 'n soort van
struktuur, basies, ek is?

57
00:03:10,350 --> 00:03:16,190
Net gaan om dit 'n node-- en dit noem
node het twee lede, of twee velde.

58
00:03:16,190 --> 00:03:20,300
Dit het data, gewoonlik 'n
heelgetal, 'n karakter float,

59
00:03:20,300 --> 00:03:23,790
of kan 'n ander tipe data wees
wat jy met 'n soort gedefinieer def.

60
00:03:23,790 --> 00:03:29,290
En dit 'n verwysing na bevat
'n ander node van dieselfde soort.

61
00:03:29,290 --> 00:03:34,710
>> So het ons twee dinge binnekant van
hierdie knoop, data en 'n wyser

62
00:03:34,710 --> 00:03:36,380
na 'n ander knoop.

63
00:03:36,380 --> 00:03:39,370
En as jy begin om te visualiseer
hierdie, kan jy dink oor dit

64
00:03:39,370 --> 00:03:42,280
soos 'n ketting van nodes wat
saam verbind.

65
00:03:42,280 --> 00:03:45,070
Ons het die eerste node, dit
bevat data en 'n wyser

66
00:03:45,070 --> 00:03:49,110
na die tweede knoop, wat bevat
data, en 'n verwysing na die derde knoop.

67
00:03:49,110 --> 00:03:52,940
En so dit is hoekom ons noem dit 'n
geskakelde lys, is hulle met mekaar verbind.

68
00:03:52,940 --> 00:03:56,070
>> Wat beteken hierdie spesiale
node struktuur lyk?

69
00:03:56,070 --> 00:04:01,120
Wel, as jy onthou van ons video op
definieer persoonlike tipes, met tipe def,

70
00:04:01,120 --> 00:04:05,400
kan ons 'n structure-- definieer en
tik definieer 'n struktuur soos hierdie.

71
00:04:05,400 --> 00:04:11,240
tyepdef struct sllist en dan is ek
die gebruik van die woord hier waarde arbitrêr

72
00:04:11,240 --> 00:04:13,891
om enige tipe data regtig aan te dui.

73
00:04:13,891 --> 00:04:16,890
Jy kan slaag op 'n heelgetal of float,
jy kan hê wat jy wil.

74
00:04:16,890 --> 00:04:19,389
Dit is nie beperk tot net
heelgetalle, of iets soos dit.

75
00:04:19,389 --> 00:04:22,790
So waarde is net 'n arbitrêre
tipe data, en dan 'n wyser

76
00:04:22,790 --> 00:04:26,310
na 'n ander node van dieselfde soort.

77
00:04:26,310 --> 00:04:29,690
>> Nou, daar is 'n bietjie catch
hier met die definisie 'n struktuur

78
00:04:29,690 --> 00:04:33,030
wanneer dit 'n self referensiële struktuur.

79
00:04:33,030 --> 00:04:35,340
Ek het 'n tydelike het
naam vir my struktuur.

80
00:04:35,340 --> 00:04:37,640
Aan die einde van die dag het ek
duidelik wil om dit te noem

81
00:04:37,640 --> 00:04:43,030
SLL node, dit is uiteindelik die nuwe
noem deel van my tipe definisie

82
00:04:43,030 --> 00:04:47,450
maar ek kan SLL node gebruik nie
in die middel van hierdie.

83
00:04:47,450 --> 00:04:51,430
Die rede hiervoor is, ek het nie
het 'n soort genoem SLL node

84
00:04:51,430 --> 00:04:55,200
totdat ek getref hierdie laaste punt hier.

85
00:04:55,200 --> 00:04:59,720
Tot op daardie punt, ek het om te hê
'n ander manier om te verwys na hierdie tipe data.

86
00:04:59,720 --> 00:05:02,440
>> En dit is 'n self
referensiële tipe data.

87
00:05:02,440 --> 00:05:06,314
Dit; s 'n data tipe van 'n
struktuur wat 'n data bevat,

88
00:05:06,314 --> 00:05:08,480
en 'n verwysing na 'n ander
struktuur van die dieselfde tipe.

89
00:05:08,480 --> 00:05:11,750
So ek moet in staat wees om te verwys na
hierdie tipe data ten minste tydelik,

90
00:05:11,750 --> 00:05:14,910
so gee dit 'n tydelike
naam van struct sllist

91
00:05:14,910 --> 00:05:18,540
laat my toe om dan sê ek wil 'n
wyser na 'n ander struct sllist,

92
00:05:18,540 --> 00:05:24,690
'n struct sllist ster, en dan
nadat ek die definisie voltooi het,

93
00:05:24,690 --> 00:05:27,220
Ek kan nou noem hierdie tipe 'n SLL knoop.

94
00:05:27,220 --> 00:05:30,520
>> So dit is waarom jy sien daar is
'n tydelike naam hier,

95
00:05:30,520 --> 00:05:31,879
maar 'n permanente naam hier.

96
00:05:31,879 --> 00:05:33,920
Soms jy kan sien
definisies van struktuur,

97
00:05:33,920 --> 00:05:36,570
byvoorbeeld, wat nie
self referensiële dat

98
00:05:36,570 --> 00:05:39,390
nie 'n specific naam nie hier.

99
00:05:39,390 --> 00:05:43,040
Dit sou net sê typedef struct,
oop krullerige brace en definieer dit.

100
00:05:43,040 --> 00:05:45,620
Maar as jy struct is self
referensiële, soos hierdie een is,

101
00:05:45,620 --> 00:05:49,010
wat jy nodig het om 'n spesifiseer
tydelike tik naam.

102
00:05:49,010 --> 00:05:51,310
Maar uiteindelik, nou
dat ons dit gedoen het,

103
00:05:51,310 --> 00:05:53,620
kan ons net verwys na
hierdie nodes, hierdie eenhede,

104
00:05:53,620 --> 00:05:57,900
as SLL nodes vir die doeleindes
van die res van hierdie video.

105
00:05:57,900 --> 00:06:00,900
>> Alle reg, sodat ons weet hoe om
skep 'n geskakelde lys knoop.

106
00:06:00,900 --> 00:06:03,240
Ons weet hoe om te definieer
'n geskakelde lys knoop.

107
00:06:03,240 --> 00:06:06,670
Nou, as ons gaan om te begin
gebruik van hulle inligting in te samel,

108
00:06:06,670 --> 00:06:10,360
daar is 'n paar van die bedrywighede ons
moet verstaan ​​en mee te werk.

109
00:06:10,360 --> 00:06:12,860
Ons moet weet hoe om te skep
'n geskakelde lys uit die lug.

110
00:06:12,860 --> 00:06:14,901
As daar geen lys reeds
ons wil een te begin.

111
00:06:14,901 --> 00:06:16,960
So moet ons in staat wees om
om 'n geskakelde lys te skep,

112
00:06:16,960 --> 00:06:19,130
ons nodig het om seker te soek
deur die skakel lys

113
00:06:19,130 --> 00:06:21,830
om 'n element wat ons soek.

114
00:06:21,830 --> 00:06:24,430
Ons moet in staat wees om in te voeg
nuwe dinge in die lys,

115
00:06:24,430 --> 00:06:25,930
ons wil ons lys om in staat wees om te groei.

116
00:06:25,930 --> 00:06:28,638
En insgelyks, ons wil in staat wees
om dinge uit ons lys te verwyder,

117
00:06:28,638 --> 00:06:30,250
ons wil ons lys om in staat wees om te krimp.

118
00:06:30,250 --> 00:06:32,160
En aan die einde van ons
programme, veral

119
00:06:32,160 --> 00:06:34,550
As jy onthou dat ons
dinamiese toekenning geheue

120
00:06:34,550 --> 00:06:38,337
om hierdie lyste tipies bou,
ons wil almal dat die geheue te bevry

121
00:06:38,337 --> 00:06:39,670
wanneer ons klaar is besig met dit.

122
00:06:39,670 --> 00:06:44,627
En so het ons moet in staat wees om 'n verwyder
hele geskakelde lys in een misluk ophef.

123
00:06:44,627 --> 00:06:46,460
So laat ons gaan deur
sommige van hierdie bedrywighede

124
00:06:46,460 --> 00:06:51,192
en hoe ons hulle kan visualiseer,
praat in pseudokode kode spesifiek.

125
00:06:51,192 --> 00:06:53,150
So wil ons 'n te skep
geskakelde lys, so miskien kan ons

126
00:06:53,150 --> 00:06:56,480
wil 'n funksie te definieer
met hierdie prototipe.

127
00:06:56,480 --> 00:07:01,690
SLL node ster, skep, en ek verby
in een argument, sommige arbitrêre data

128
00:07:01,690 --> 00:07:05,530
tik weer van 'n paar arbitrêre data tipe.

129
00:07:05,530 --> 00:07:10,482
Maar ek returning-- hierdie funksie moet
terug te keer na my 'n wyser, om 'n enkel

130
00:07:10,482 --> 00:07:11,190
geskakelde lys knoop.

131
00:07:11,190 --> 00:07:14,050
Weereens, ons probeer om te skep
'n geskakelde lys uit die lug,

132
00:07:14,050 --> 00:07:17,900
so ek moet 'n verwysing na
dat die lys wanneer ek gedoen het.

133
00:07:17,900 --> 00:07:19,420
>> So, wat is die stappe wat hier betrokke?

134
00:07:19,420 --> 00:07:20,960
Wel, die eerste ding wat ek
gaan doen, is dinamies

135
00:07:20,960 --> 00:07:22,550
toeken ruimte vir 'n nuwe knoop.

136
00:07:22,550 --> 00:07:26,689
Weereens, ons skep dit uit dun
lug, so ons moet malloc ruimte vir dit.

137
00:07:26,689 --> 00:07:28,480
En natuurlik, onmiddellik
nadat ons malloc,

138
00:07:28,480 --> 00:07:31,692
kyk ons ​​altyd om seker te maak dat ons
pointer-- ons nie terug te kry null.

139
00:07:31,692 --> 00:07:33,650
Want as ons probeer
onderdanigheid n null pointer,

140
00:07:33,650 --> 00:07:36,190
ons gaan 'n ly
segfault en ons wil nie dat.

141
00:07:36,190 --> 00:07:39,510
>> Dan wil ons in die veld te vul,
ons wil die veld waarde inisialiseer

142
00:07:39,510 --> 00:07:41,690
en inisialiseer die volgende veld.

143
00:07:41,690 --> 00:07:45,450
En dan wil ons aan- uiteindelik as die
funksie prototipe indicates-- ons wil

144
00:07:45,450 --> 00:07:49,940
om 'n wyser terug na 'n SLL knoop.

145
00:07:49,940 --> 00:07:51,710
So, wat maak hierdie lyk visueel?

146
00:07:51,710 --> 00:07:55,230
Wel, die eerste gaan ons dinamiese
toeken ruimte vir 'n nuwe SLL knoop,

147
00:07:55,230 --> 00:07:58,320
sodat ons malloc-- dis
'n visuele voorstelling

148
00:07:58,320 --> 00:08:00,020
van die node ons net gemaak.

149
00:08:00,020 --> 00:08:02,757
En ons gaan om seker te maak
dit is nie null-- in hierdie geval,

150
00:08:02,757 --> 00:08:04,840
die prentjie wil nie hê
getoon het as dit nie was null,

151
00:08:04,840 --> 00:08:07,298
Ons het uit die geheue sou hardloop,
so ons is goed om daarheen te gaan.

152
00:08:07,298 --> 00:08:10,200
So nou is ons op te tree C,
inisialiseer die veld nodes waarde.

153
00:08:10,200 --> 00:08:12,280
Wel, gebaseer op die funksie
noem ek hier in met,

154
00:08:12,280 --> 00:08:16,700
lyk soos ek wil om te slaag in 6,
So ek sal 6 in die veld waarde.

155
00:08:16,700 --> 00:08:18,865
Nou, inisialiseer die volgende veld.

156
00:08:18,865 --> 00:08:21,640
Wel, wat ek gaan om daar te doen,
daar is niks volgende, regs,

157
00:08:21,640 --> 00:08:23,600
dit is die enigste ding wat in die lys.

158
00:08:23,600 --> 00:08:27,206
So, wat is die volgende ding in die lys?

159
00:08:27,206 --> 00:08:29,660
>> Dit moet nie wys om enigiets, reg.

160
00:08:29,660 --> 00:08:33,600
Daar is niks anders is daar, so wat is
die konsep wat ons ken wat nothing--

161
00:08:33,600 --> 00:08:35,638
verwysings na niks nie?

162
00:08:35,638 --> 00:08:37,929
Dit moet dalk wil ons
'n null pointer daar te vestig,

163
00:08:37,929 --> 00:08:40,178
en Ek sal die nul verteenwoordig
aanwijzer as net 'n rooi boks,

164
00:08:40,178 --> 00:08:41,559
ons kan nie verder gaan nie.

165
00:08:41,559 --> 00:08:44,430
Soos ons sal sien 'n bietjie later,
sal ons uiteindelik kettings

166
00:08:44,430 --> 00:08:46,330
pyle verbind
hierdie nodes saam

167
00:08:46,330 --> 00:08:48,480
maar wanneer jy druk op die
rooi boks, dit is null,

168
00:08:48,480 --> 00:08:51,150
ons kan nie verder gaan nie,
dit is die einde van die lys.

169
00:08:51,150 --> 00:08:53,960
>> En laastens, ons wil net om
terugkeer 'n wyser na hierdie knoop.

170
00:08:53,960 --> 00:08:56,160
So sal ons dit noem nuwe,
en sal 'n nuwe terugkeer

171
00:08:56,160 --> 00:08:59,370
sodat dit gebruik kan word in
Watter funksie het dit geskep.

172
00:08:59,370 --> 00:09:03,100
So is daar gaan ons, het ons 'n enkel geskep
geskakelde lys node uit die lug,

173
00:09:03,100 --> 00:09:05,920
en nou het ons 'n lys wat ons kan werk.

174
00:09:05,920 --> 00:09:08,260
>> Nou, laat ons sê dat ons reeds
het 'n groot ketting,

175
00:09:08,260 --> 00:09:09,800
en ons wil iets in dit vind.

176
00:09:09,800 --> 00:09:12,716
En ons wil 'n funksie wat gaan
waar of vals terugkeer, afhangende

177
00:09:12,716 --> 00:09:15,840
op die vraag of 'n waarde bestaan ​​in die lys.

178
00:09:15,840 --> 00:09:18,160
'N Funksie prototipe, of
verklaring vir daardie funksie,

179
00:09:18,160 --> 00:09:23,320
kan lyk this-- Bool vind, en
dan wil ons slaag in twee argumente.

180
00:09:23,320 --> 00:09:26,996
>> Die eerste is 'n verwysing na die
eerste element van die geskakelde lys.

181
00:09:26,996 --> 00:09:29,620
Dit is eintlik iets wat jy
wil altyd om tred te hou,

182
00:09:29,620 --> 00:09:33,110
en eintlik dalk iets wees dat
jy kan selfs in 'n globale veranderlike.

183
00:09:33,110 --> 00:09:35,360
Sodra jy 'n lys te skep,
jy altyd, altyd

184
00:09:35,360 --> 00:09:38,990
wil om tred te hou van die baie
eerste element van die lys.

185
00:09:38,990 --> 00:09:43,690
Die manier wat jy kan verwys na al die ander
elemente deur net na die ketting,

186
00:09:43,690 --> 00:09:47,300
sonder om wenke te hou
ongeskonde elke enkele element.

187
00:09:47,300 --> 00:09:50,920
Jy moet net om tred te hou van die eerste hou
een as hulle almal saam vasgeketting.

188
00:09:50,920 --> 00:09:52,460
>> En dan is die tweede ding
ons weer verby in

189
00:09:52,460 --> 00:09:54,376
is arbitrêr some--
watter tipe data ons

190
00:09:54,376 --> 00:09:59,640
soek, want daar is die binnekant van
hopelik een van die nodusse in die lys.

191
00:09:59,640 --> 00:10:00,980
So, wat is die stappe?

192
00:10:00,980 --> 00:10:04,250
Wel, die eerste ding wat ons doen, is
skep ons 'n dwarsleggende wyser

193
00:10:04,250 --> 00:10:06,015
verwys na die lyste kop.

194
00:10:06,015 --> 00:10:08,890
Wel, hoekom doen ons dit doen, ons het reeds
'n wyser op die lyste kop,

195
00:10:08,890 --> 00:10:10,974
Daarom het ons nie beweeg net dat een rond?

196
00:10:10,974 --> 00:10:13,140
Wel, soos ek nou net gesê,
dit is werklik belangrik vir ons

197
00:10:13,140 --> 00:10:17,580
om altyd hou van die
heel eerste element in die lys.

198
00:10:17,580 --> 00:10:21,270
En so dit is eintlik 'n beter
om 'n duplikaat van die skep,

199
00:10:21,270 --> 00:10:25,350
en die gebruik dat rondom, sodat ons nooit beweeg
per ongeluk weg te beweeg, of ons altyd

200
00:10:25,350 --> 00:10:30,430
'n wyser op 'n punt wat
reg op die eerste element van die lys.

201
00:10:30,430 --> 00:10:33,290
So dit is beter om 'n te skep
tweede een wat ons gebruik om te beweeg.

202
00:10:33,290 --> 00:10:35,877
>> Dan het ons net te vergelyk of
die veld waarde op daardie node

203
00:10:35,877 --> 00:10:38,960
is wat ons soek, en as dit
nie, ons het net skuif na die volgende knoop.

204
00:10:38,960 --> 00:10:41,040
En ons hou doen wat
oor en oor en oor,

205
00:10:41,040 --> 00:10:44,811
totdat ons óf vind
die element, of ons getref

206
00:10:44,811 --> 00:10:47,310
null-- ons het die einde bereik
van die lys en dit is nie daar nie.

207
00:10:47,310 --> 00:10:50,540
Dit behoort hopelik lui 'n klokkie
aan jou as net lineêre soek,

208
00:10:50,540 --> 00:10:54,430
ons net replicerende in
'n enkel geskakelde lys struktuur

209
00:10:54,430 --> 00:10:56,280
in plaas van die gebruik van 'n verskeidenheid om dit te doen.

210
00:10:56,280 --> 00:10:58,210
>> So hier is 'n voorbeeld van
'n enkel geskakelde lys.

211
00:10:58,210 --> 00:11:00,043
Hierdie een bestaan ​​uit
vyf knope, en ons het

212
00:11:00,043 --> 00:11:04,330
'n verwysing na die hoof van die
lys, wat lys genoem word.

213
00:11:04,330 --> 00:11:07,385
Die eerste ding wat ons wil doen, is
weer, skep dat traversal wyser.

214
00:11:07,385 --> 00:11:09,760
So het ons nou twee pointers
daardie punt om dieselfde ding.

215
00:11:09,760 --> 00:11:15,025
>> Nou, sien ook hier, ek het nie
moet 'n ruimte vir trav malloc.

216
00:11:15,025 --> 00:11:18,970
Ek het nie gesê trav gelyk malloc
iets wat node bestaan ​​reeds,

217
00:11:18,970 --> 00:11:21,160
dat die ruimte in die geheue bestaan ​​reeds.

218
00:11:21,160 --> 00:11:24,290
So al wat ek eintlik doen, is
skep 'n ander wyser om dit te.

219
00:11:24,290 --> 00:11:28,210
Ek is nie 'n bykomende mallocing
ruimte, net nou twee pointers

220
00:11:28,210 --> 00:11:31,370
verwys na dieselfde ding.

221
00:11:31,370 --> 00:11:33,710
>> So is 2 wat ek is op soek na?

222
00:11:33,710 --> 00:11:37,220
Wel, nee, so in plaas ek is
gaan skuif na die volgende een.

223
00:11:37,220 --> 00:11:41,740
So basies sou ek sê,
trav gelyk trav volgende.

224
00:11:41,740 --> 00:11:43,630
3 wat ek soek, no.

225
00:11:43,630 --> 00:11:45,780
So ek bly om te gaan
deur, totdat uiteindelik

226
00:11:45,780 --> 00:11:48,690
kry om 6 en dit is wat ek soek
vir gebaseer op die funksie oproep

227
00:11:48,690 --> 00:11:51,600
Ek het op die top
daar en so ek gedoen het.

228
00:11:51,600 --> 00:11:54,150
>> Nou, wat as die element Ek is
soek, is nie in die lys,

229
00:11:54,150 --> 00:11:55,510
dit is nog steeds gaan om te werk?

230
00:11:55,510 --> 00:11:57,120
Wel, sien dat die lys
hier is subtiel verskillende,

231
00:11:57,120 --> 00:11:59,410
en dit is 'n ander ding wat
belangrik om met geskakelde lyste,

232
00:11:59,410 --> 00:12:01,780
jy hoef nie te bewaar
hulle in 'n bepaalde orde.

233
00:12:01,780 --> 00:12:05,390
Jy kan as jy wil, maar
jy dalk al opgemerk

234
00:12:05,390 --> 00:12:09,310
dat ons nie hou van
watter getal element is ons by.

235
00:12:09,310 --> 00:12:13,150
>> En dit is soort van 'n handel dat ons
met geskakelde lys verse skikkings,

236
00:12:13,150 --> 00:12:15,300
is dit ons het nie
ewetoeganklike nie.

237
00:12:15,300 --> 00:12:18,150
Ons kan nie net sê, ek wil
om te gaan na die 0 element,

238
00:12:18,150 --> 00:12:21,410
of die 6 element van my skikking,
wat ek kan doen in 'n skikking.

239
00:12:21,410 --> 00:12:25,080
Ek kan nie sê ek wil om te gaan na die
0 element, of die 6 element,

240
00:12:25,080 --> 00:12:30,360
of die 25 element van my geskakelde lys,
daar is geen indeks wat verband hou met hulle.

241
00:12:30,360 --> 00:12:33,660
En so is dit nie regtig saak
as ons ons lys te bewaar ten einde.

242
00:12:33,660 --> 00:12:36,080
As jy wil om jou
kan seker nie, maar daar is

243
00:12:36,080 --> 00:12:38,567
geen rede waarom hulle nodig het om
bewaar in enige volgorde.

244
00:12:38,567 --> 00:12:40,400
So weer, laat ons probeer
vind 6 in hierdie lys.

245
00:12:40,400 --> 00:12:43,200
Wel, ons begin by die
begin, het ons nie vind 6,

246
00:12:43,200 --> 00:12:47,690
en dan voortgaan ons nie vind
6, totdat ons uiteindelik hier.

247
00:12:47,690 --> 00:12:52,790
So nou trav punte na die node
met 8 en ses is nie daar.

248
00:12:52,790 --> 00:12:55,250
>> So die volgende stap sou wees
om te gaan na die volgende wyser,

249
00:12:55,250 --> 00:12:57,440
so sê trav gelyk trav volgende.

250
00:12:57,440 --> 00:13:00,750
Wel, trav volgende, aangedui deur
die rooi boks, is van nul.

251
00:13:00,750 --> 00:13:03,020
So daar is nêrens anders om
gaan, en so op hierdie punt

252
00:13:03,020 --> 00:13:06,120
kan ons aflei dat ons bereik het
die einde van die geskakelde lys,

253
00:13:06,120 --> 00:13:07,190
en 6 is nie daar.

254
00:13:07,190 --> 00:13:10,980
En dit sou teruggestuur
valse in hierdie geval.

255
00:13:10,980 --> 00:13:14,540
>> OK, hoe kan ons voeg 'n nuwe
nodus in die lys?

256
00:13:14,540 --> 00:13:17,310
So het ons in staat om te skep nie
'n geskakelde lys van nêrens,

257
00:13:17,310 --> 00:13:19,370
maar ons wil waarskynlik
bou van 'n ketting en nie

258
00:13:19,370 --> 00:13:22,620
skep 'n klomp van die verskillende lyste.

259
00:13:22,620 --> 00:13:25,700
Ons wil 'n lys te hê wat
het 'n klomp van die nodes in dit,

260
00:13:25,700 --> 00:13:28,040
nie 'n klomp van die lyste met 'n enkele knoop.

261
00:13:28,040 --> 00:13:31,260
So kan ons nie net te hou met die skep
funksie ons vroeër gedefinieer, nou is ons

262
00:13:31,260 --> 00:13:33,860
wil plaas in 'n
lys wat reeds bestaan.

263
00:13:33,860 --> 00:13:36,499
>> So hierdie geval, ons gaan
om te slaag in twee argumente,

264
00:13:36,499 --> 00:13:39,290
die wyser na die hoof van daardie
gekoppel lys wat ons wil om te voeg by.

265
00:13:39,290 --> 00:13:40,910
Weereens, dit is hoekom dit so
belangrik dat ons altyd

266
00:13:40,910 --> 00:13:43,400
hou van dit, want
dit is die enigste manier waarop ons regtig

267
00:13:43,400 --> 00:13:46,690
het om te verwys na die hele lys is
net deur 'n wyser na die eerste element.

268
00:13:46,690 --> 00:13:49,360
So ons wil om te slaag in 'n
wyser na daardie eerste element,

269
00:13:49,360 --> 00:13:52,226
en alles wat waarde wat ons
wil byvoeg by die lys.

270
00:13:52,226 --> 00:13:54,600
En uiteindelik die funksie
gaan 'n wyser terug

271
00:13:54,600 --> 00:13:57,980
om die nuwe hoof van 'n geskakelde lys.

272
00:13:57,980 --> 00:13:59,700
>> Wat is die stappe wat hier betrokke?

273
00:13:59,700 --> 00:14:02,249
Wel, net soos met die skep,
ons nodig het om dinamiese toewys

274
00:14:02,249 --> 00:14:05,540
ruimte vir 'n nuwe node, en kyk om te maak
dat ons nie uit die geheue loop, weer,

275
00:14:05,540 --> 00:14:07,150
want ons is met behulp van malloc.

276
00:14:07,150 --> 00:14:09,080
Dan wil ons vul
en voeg die node,

277
00:14:09,080 --> 00:14:12,730
so het die getal, ongeag
Val is, in die knoop.

278
00:14:12,730 --> 00:14:17,310
Ons wil die node voeg by
die begin van die geskakelde lys.

279
00:14:17,310 --> 00:14:19,619
>> Daar is 'n rede dat ek
dit wil doen, en dit

280
00:14:19,619 --> 00:14:21,910
die moeite werd om 'n tweede kan wees
om die video hier breek,

281
00:14:21,910 --> 00:14:25,860
en dink oor die rede waarom ek wil
voeg aan die begin van 'n gekoppelde

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

283
00:14:26,589 --> 00:14:28,630
Weereens, ek vroeër genoem
dat dit nie regtig

284
00:14:28,630 --> 00:14:33,020
saak as ons bewaar word in enige
orde, so miskien is dit 'n leidraad.

285
00:14:33,020 --> 00:14:36,040
En jy sien wat gaan gebeur as ons
wou aan- of net 'n tweede

286
00:14:36,040 --> 00:14:37,360
gelede toe ons gaan
deur 'n soektog wat jy

287
00:14:37,360 --> 00:14:39,235
wat kan sien nie, mag
gebeur as ons probeer

288
00:14:39,235 --> 00:14:41,330
te voeg aan die einde van die lys.

289
00:14:41,330 --> 00:14:44,750
Omdat ons nie 'n het
wyser na die einde van die lys.

290
00:14:44,750 --> 00:14:47,490
>> So die rede dat ek wil
te voeg aan die begin,

291
00:14:47,490 --> 00:14:49,380
is omdat ek dit dadelik kan doen.

292
00:14:49,380 --> 00:14:52,730
Ek het 'n wyser aan die begin, en
ons sal sien dit in 'n visuele in 'n tweede.

293
00:14:52,730 --> 00:14:55,605
Maar as ek wil voeg aan die einde,
Ek moet begin by die begin,

294
00:14:55,605 --> 00:14:58,760
deurkruis al die pad na die
einde nie, en ryg dit op.

295
00:14:58,760 --> 00:15:01,420
So dit sou beteken dat
invoeging aan die einde van die lys

296
00:15:01,420 --> 00:15:04,140
sou 'n o van N geword
operasie, gaan terug

297
00:15:04,140 --> 00:15:06,720
om ons bespreking van
rekenkundige kompleksiteit.

298
00:15:06,720 --> 00:15:10,140
Dit sou 'n O van n operasie, waar geword
as die lys het groter en groter,

299
00:15:10,140 --> 00:15:13,310
en groter word, sal dit meer geword en
meer moeilik om iets te ryg

300
00:15:13,310 --> 00:15:14,661
op aan die einde.

301
00:15:14,661 --> 00:15:17,410
Maar dit is altyd baie maklik om te
ryg iets aan die begin,

302
00:15:17,410 --> 00:15:19,060
jy altyd aan die begin.

303
00:15:19,060 --> 00:15:21,620
>> En ons sal nie weer sien 'n visuele hiervan.

304
00:15:21,620 --> 00:15:24,100
En dan wanneer ons klaar is, een keer
ons het die nuwe node ingevoeg,

305
00:15:24,100 --> 00:15:26,880
wil ons ons wyser terug na
die nuwe hoof van 'n geskakelde lys, wat

306
00:15:26,880 --> 00:15:29,213
aangesien ons die inbring by die
begin, sal eintlik

307
00:15:29,213 --> 00:15:31,060
'n verwysing na die knoop ons net gemaak.

308
00:15:31,060 --> 00:15:33,280
Kom ons visualiseer dit
want ek dink dit sal help.

309
00:15:33,280 --> 00:15:36,661
>> So hier is ons lys, dit bestaan ​​uit
vier elemente, 'n knoop met 15,

310
00:15:36,661 --> 00:15:38,410
wat dui op 'n node
bevat 9, wat

311
00:15:38,410 --> 00:15:41,370
dui op 'n node met 13,
wat dui op 'n node met

312
00:15:41,370 --> 00:15:44,840
10, wat die nul het
wyser as sy volgende wyser

313
00:15:44,840 --> 00:15:47,010
so dit is die einde van die lys.

314
00:15:47,010 --> 00:15:50,200
So wil ons 'n plaas
nuwe node met die waarde 12

315
00:15:50,200 --> 00:15:52,720
aan die begin van hierdie
lys, wat doen ons?

316
00:15:52,720 --> 00:15:58,770
Wel, die eerste malloc ons ruimte vir die
knoop, en dan sit ons 12 daar.

317
00:15:58,770 --> 00:16:02,211
>> So nou het ons bereik 'n
besluit punt, reg?

318
00:16:02,211 --> 00:16:03,960
Ons het 'n paar van die
wysers wat ons kon

319
00:16:03,960 --> 00:16:06,770
beweeg, wat 'n mens moet ons eers beweeg?

320
00:16:06,770 --> 00:16:09,250
Moet ons 12 punt om
die nuwe hoof van die list--

321
00:16:09,250 --> 00:16:13,020
of verskoon my, moet ons 12
verwys na die ou hoof van die lys?

322
00:16:13,020 --> 00:16:15,319
Of moet ons sê dat die
lys begin nou op 12.

323
00:16:15,319 --> 00:16:17,110
Daar is 'n onderskeid
daar, en ons sal kyk

324
00:16:17,110 --> 00:16:19,870
wat gebeur met beide in 'n tweede.

325
00:16:19,870 --> 00:16:23,350
>> Maar dit lei tot 'n
groot onderwerp vir sidebar,

326
00:16:23,350 --> 00:16:26,280
wat is dat een van die
moeilijkste dinge met geskakelde lyste

327
00:16:26,280 --> 00:16:30,980
is om die wysers te reël
in die korrekte volgorde.

328
00:16:30,980 --> 00:16:34,520
As jy dinge beweeg buite orde,
kan jy per ongeluk beland

329
00:16:34,520 --> 00:16:36,050
orphaning die res van die lys.

330
00:16:36,050 --> 00:16:37,300
En hier is 'n voorbeeld.

331
00:16:37,300 --> 00:16:40,540
So laat ons gaan met die idee of--
Wel, ons het net geskep 12.

332
00:16:40,540 --> 00:16:43,180
Ons weet 12 gaan wees
die nuwe hoof van die lys,

333
00:16:43,180 --> 00:16:47,660
en so hoekom doen ons nie net beweeg
die lys wyser om daar te wys.

334
00:16:47,660 --> 00:16:49,070
>> OK, so dit is goed.

335
00:16:49,070 --> 00:16:51,560
So nou waar kom 12 volgende punt?

336
00:16:51,560 --> 00:16:54,580
Ek bedoel, visueel kan ons sien
dat dit sal wys tot 15,

337
00:16:54,580 --> 00:16:57,250
as mense dit regtig duidelik aan ons.

338
00:16:57,250 --> 00:17:00,300
Hoe weet die rekenaar?

339
00:17:00,300 --> 00:17:02,720
Ons het niks
wys na 15 nie, reg?

340
00:17:02,720 --> 00:17:05,869
>> Ons het 'n vermoë om te verwys na 15 verloor het.

341
00:17:05,869 --> 00:17:11,460
Ons kan nie 'n nuwe pyltjie langs gelykes sê
iets, daar is niks daar.

342
00:17:11,460 --> 00:17:13,510
In werklikheid, het ons gelaat
die res van die lys

343
00:17:13,510 --> 00:17:16,465
deur dit te doen, het ons
toevallig gebreek die ketting.

344
00:17:16,465 --> 00:17:18,089
En ons wil beslis nie om dit te doen.

345
00:17:18,089 --> 00:17:20,000
>> So laat terug te gaan en probeer weer.

346
00:17:20,000 --> 00:17:24,060
Dalk is dit die regte ding om te doen
is tot 12 se volgende wyser stel

347
00:17:24,060 --> 00:17:28,290
om die ou hoof van die lys,
dan kan ons die lys beweeg oor.

348
00:17:28,290 --> 00:17:30,420
En in die feit dat die
korrekte sodat ons

349
00:17:30,420 --> 00:17:32,836
moet volg wanneer ons
werk met enkel geskakelde lys.

350
00:17:32,836 --> 00:17:36,460
Ons wil altyd die verbinding
nuwe element in die lys,

351
00:17:36,460 --> 00:17:41,010
voordat ons daardie soort van te neem
belangrike stap van die verandering van

352
00:17:41,010 --> 00:17:43,360
waar die hoof van die geskakelde lys is.

353
00:17:43,360 --> 00:17:46,740
Weereens, dit is so 'n fundamentele ding,
ons wil nie om tred te hou van dit verloor.

354
00:17:46,740 --> 00:17:49,310
>> So wil ons seker maak dat
alles saam vasgeketting,

355
00:17:49,310 --> 00:17:52,040
voordat ons dat wyser.

356
00:17:52,040 --> 00:17:55,300
En so sou dit die korrekte volgorde wees,
wat is om aan te sluit 12 op die lys,

357
00:17:55,300 --> 00:17:57,630
dan sê dat die lys begin 'n 12.

358
00:17:57,630 --> 00:18:00,860
As ons sê die lys begin op 12 en
dan probeer om aan te sluit 12 op die lys,

359
00:18:00,860 --> 00:18:02,193
ons het reeds gesien wat gebeur.

360
00:18:02,193 --> 00:18:04,920
Ons verloor die lys per ongeluk.

361
00:18:04,920 --> 00:18:06,740
>> OK, so een ding om oor te praat.

362
00:18:06,740 --> 00:18:09,750
Wat as ons wil ontslae te raak van
'n hele gelyktydig geskakelde lys?

363
00:18:09,750 --> 00:18:11,750
Weereens, ons mallocing
al hierdie spasie, en so het ons

364
00:18:11,750 --> 00:18:13,351
nodig het om dit te bevry wanneer ons klaar is.

365
00:18:13,351 --> 00:18:15,350
So nou wil ons verwyder
die hele geskakelde lys.

366
00:18:15,350 --> 00:18:16,850
Wel, doen wat ons wil doen?

367
00:18:16,850 --> 00:18:20,460
>> As ons die nul wyser bereik het, het ons
wil om te stop, anders, net verwyder

368
00:18:20,460 --> 00:18:23,420
die res van die lys en dan bevry my.

369
00:18:23,420 --> 00:18:28,890
Verwyder die res van die lys,
en bevry dan is die huidige knoop.

370
00:18:28,890 --> 00:18:32,850
Wat beteken dat die klank soos,
Watter tegniek het ons gepraat

371
00:18:32,850 --> 00:18:35,440
oor voorheen Klink dit?

372
00:18:35,440 --> 00:18:39,560
Verwyder almal anders, dan
kom terug en my verwyder.

373
00:18:39,560 --> 00:18:42,380
>> Dit is rekursie, het ons die
probleem 'n bietjie kleiner,

374
00:18:42,380 --> 00:18:46,910
ons sê almal verwyder
anders, dan kan jy vir my verwyder.

375
00:18:46,910 --> 00:18:50,940
En verder af in die pad, wat node
sal sê, almal anders te verwyder.

376
00:18:50,940 --> 00:18:53,940
Maar uiteindelik sal ons die kry
punt waar die lys is null,

377
00:18:53,940 --> 00:18:55,310
en dit is ons basis geval.

378
00:18:55,310 --> 00:18:57,010
>> So laat ons neem 'n blik op hierdie,
en hoe dit kan werk.

379
00:18:57,010 --> 00:18:59,759
So hier is ons lys, dit is dieselfde
ons lys is net te praat oor,

380
00:18:59,759 --> 00:19:00,980
en daar is die stappe.

381
00:19:00,980 --> 00:19:04,200
Daar is 'n baie van die teks hier nie, maar
Hopelik sal die visualisering sal help.

382
00:19:04,200 --> 00:19:08,557
>> Sodat ons have-- en ek het ook getrek
up ons stapel rame illustrasie

383
00:19:08,557 --> 00:19:10,890
van ons video op die oproep stapels,
en hopelik al hierdie

384
00:19:10,890 --> 00:19:13,260
saam sal jou wys wat aangaan.

385
00:19:13,260 --> 00:19:14,510
So hier is ons pseudokode-kode.

386
00:19:14,510 --> 00:19:17,830
As ons 'n nul bereik
wyser, stop, anders,

387
00:19:17,830 --> 00:19:21,320
verwyder die res van die lys,
bevry dan is die huidige knoop.

388
00:19:21,320 --> 00:19:25,700
So nou, list--
die wyser dat ons

389
00:19:25,700 --> 00:19:28,410
verby in om punte te vernietig 12.

390
00:19:28,410 --> 00:19:33,340
12 is nie 'n nul pointer, so ons is
gaan na die res van die lys verwyder.

391
00:19:33,340 --> 00:19:35,450
>> Wat is die verwydering van die
res van ons wat betrokke is?

392
00:19:35,450 --> 00:19:37,950
Wel, dit beteken om 'n
bel om te vernietig, sê

393
00:19:37,950 --> 00:19:42,060
dat 15 is die begin van die
res van die lys wat ons wil vernietig.

394
00:19:42,060 --> 00:19:47,480
En so het die oproep om te vernietig
12 is 'n soort van op te hou.

395
00:19:47,480 --> 00:19:52,690
Dit is daar gevries, en wag vir die
bel om te vernietig 15, om sy werk te voltooi.

396
00:19:52,690 --> 00:19:56,280
>> Wel, 15 is nie 'n nul pointer, en
so dit gaan om te sê, alles reg,

397
00:19:56,280 --> 00:19:58,450
Wel, verwyder die res van die lys.

398
00:19:58,450 --> 00:20:00,760
Die res van die lys begin
op 9, en so ons sal net

399
00:20:00,760 --> 00:20:04,514
wag totdat jy al verwyder wat
dinge, kom dan terug en my verwyder.

400
00:20:04,514 --> 00:20:06,680
Wel 9 gaan om te sê, goed,
Ek is nie 'n nul pointer,

401
00:20:06,680 --> 00:20:09,020
so verwyder die res van die lys van hier.

402
00:20:09,020 --> 00:20:11,805
En so probeer en vernietig 13.

403
00:20:11,805 --> 00:20:15,550
13 sê, ek is nie null pointer,
dieselfde ding, dit gaan die bok.

404
00:20:15,550 --> 00:20:17,930
10 is nie null pointer, 10
bevat 'n null pointer,

405
00:20:17,930 --> 00:20:20,200
maar 10 is nie op sigself 'n
null nou Pointer,

406
00:20:20,200 --> 00:20:22,470
en so is dit verby die bok ook.

407
00:20:22,470 --> 00:20:25,560
>> En nou is daar 'n lys van punte, is dit
regtig wys some--

408
00:20:25,560 --> 00:20:28,710
as ek het meer ruimte in die beeld,
dit sou wys om 'n paar random ruimte

409
00:20:28,710 --> 00:20:29,960
dat ons nie weet wat dit is.

410
00:20:29,960 --> 00:20:34,680
Dit is die nul pointer al is, die lys
is letterlik nou ingestel dis waardes null.

411
00:20:34,680 --> 00:20:36,820
Dit wys dat die reg binne rooi boks.

412
00:20:36,820 --> 00:20:39,960
Ons het 'n nul pointer, so
ons kan stop, en ons gedoen het.

413
00:20:39,960 --> 00:20:46,230
>> En sodat pers raam is now-- by die
top van stack-- dit is die aktiewe raam,

414
00:20:46,230 --> 00:20:47,017
maar dit is gedoen.

415
00:20:47,017 --> 00:20:48,600
As ons 'n null pointer bereik het, te stop.

416
00:20:48,600 --> 00:20:51,290
Ons het nie iets te doen, ons
kan nie bevry n null pointer,

417
00:20:51,290 --> 00:20:55,070
ons het nie enige malloc
ruimte, en so het ons klaar.

418
00:20:55,070 --> 00:20:57,590
Sodat funksie raam
vernietig, en ons

419
00:20:57,590 --> 00:21:00,930
resume-- ons haal waar ons opgehou
af met die volgende hoogste een, wat

420
00:21:00,930 --> 00:21:02,807
is dit donker blou raam hier.

421
00:21:02,807 --> 00:21:04,390
Sodat ons haal reg waar ons opgehou het.

422
00:21:04,390 --> 00:21:06,598
Ons verwyder die res van die
lys reeds, so nou is ons

423
00:21:06,598 --> 00:21:08,000
gaan die huidige nodes te bevry.

424
00:21:08,000 --> 00:21:12,920
So nou kan ons bevry van hierdie knoop, en nou
ons het die einde van die funksie bereik.

425
00:21:12,920 --> 00:21:16,810
En sodat funksie raam is vernietig,
en ons haal by die lig blou.

426
00:21:16,810 --> 00:21:20,650
>> So dit says-- Ek het reeds done--
die verwydering van die res van die lys, so

427
00:21:20,650 --> 00:21:23,140
bevry die huidige knoop.

428
00:21:23,140 --> 00:21:26,520
En nou het die geel raam is
terug op die top van die stapel.

429
00:21:26,520 --> 00:21:29,655
En so soos jy sien, ons is nou
die vernietiging van die lys van regs na links.

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

431
00:21:33,710 --> 00:21:37,280
>> Wat sou gebeur het, al is,
as ons dinge gedoen het die verkeerde manier?

432
00:21:37,280 --> 00:21:39,410
Net soos wanneer ons probeer
om 'n element te voeg.

433
00:21:39,410 --> 00:21:41,909
As ons deurmekaar die ketting, as
ons het nie die wysers koppel

434
00:21:41,909 --> 00:21:44,690
in die korrekte volgorde, as ons
net die eerste element bevry,

435
00:21:44,690 --> 00:21:47,420
as ons net bevry die
hoof van die lys, nou is ons

436
00:21:47,420 --> 00:21:49,642
het geen manier om te verwys na
die res van die lys.

437
00:21:49,642 --> 00:21:51,350
En so sal ons moet
gelaat alles,

438
00:21:51,350 --> 00:21:53,880
ons sou gehad het, wat is
bekend as 'n geheue lek.

439
00:21:53,880 --> 00:21:56,800
As jy onthou van ons video
op dinamiese geheuetoekenning,

440
00:21:56,800 --> 00:21:58,650
dit is nie 'n baie goeie ding.

441
00:21:58,650 --> 00:22:00,810
>> So as ek gesê het, is daar
is verskeie operasies

442
00:22:00,810 --> 00:22:04,010
wat ons nodig het om te gebruik om te werk
met geskakelde lys effektief.

443
00:22:04,010 --> 00:22:08,430
En jy dalk opgemerk het ek uitgelaat een
verwydering van 'n enkele element van 'n gekoppelde

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

445
00:22:09,064 --> 00:22:10,980
Die rede waarom ek dit gedoen het
is dit eintlik soort

446
00:22:10,980 --> 00:22:14,360
moeilik om te dink oor hoe om te verwyder
'n enkele element van 'n enkel

447
00:22:14,360 --> 00:22:15,600
geskakelde lys.

448
00:22:15,600 --> 00:22:19,950
Ons moet in staat wees om oor te slaan
iets in die lys, wat

449
00:22:19,950 --> 00:22:22,975
beteken ons kry 'n point-- ons
wil hierdie node-- verwyder

450
00:22:22,975 --> 00:22:25,350
maar om dit so te maak ons
nie enige inligting nie verloor nie,

451
00:22:25,350 --> 00:22:30,530
ons nodig het om hierdie verbinding
node oor hier, hier.

452
00:22:30,530 --> 00:22:33,390
>> So ek het waarskynlik wat verkeerd
uit 'n visuele perspektief.

453
00:22:33,390 --> 00:22:36,830
So ons is aan die begin van ons
lys, ons vorder deur middel van,

454
00:22:36,830 --> 00:22:40,510
Ons wil hierdie node verwyder.

455
00:22:40,510 --> 00:22:43,440
As ons net dit verwyder,
ons het die ketting gebreek.

456
00:22:43,440 --> 00:22:45,950
Dit node hier
verwys na alles,

457
00:22:45,950 --> 00:22:48,260
dit bevat die ketting van hier op uit.

458
00:22:48,260 --> 00:22:51,190
>> So, wat ons nodig het om werklik te doen
nadat ons kry om hierdie punt,

459
00:22:51,190 --> 00:22:56,670
is wat ons nodig het om terug te stap een, en
koppel hierdie node oor hierdie knoop,

460
00:22:56,670 --> 00:22:58,590
sodat ons kan dan verwyder
die een in die middel.

461
00:22:58,590 --> 00:23:02,120
Maar enkel geskakelde lyste te doen nie
bied ons 'n manier om terug te gaan.

462
00:23:02,120 --> 00:23:05,160
So moet ons óf hou
twee wysers, en hulle beweeg

463
00:23:05,160 --> 00:23:09,527
soort van af stap, een agter die
ander soos ons gaan, of kry 'n punt

464
00:23:09,527 --> 00:23:11,110
en dan stuur 'n ander wyser deur.

465
00:23:11,110 --> 00:23:13,150
En soos jy kan sien, is dit
kan 'n bietjie slordig te kry.

466
00:23:13,150 --> 00:23:15,360
Gelukkig het ons
'n ander manier om op te los nie,

467
00:23:15,360 --> 00:23:17,810
wanneer ons praat oor dubbeld geskakelde lyste.

468
00:23:17,810 --> 00:23:20,720
>> Ek is Doug Lloyd, dit is CS50.

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