1
00:00:00,000 --> 00:00:02,832
>> [Prehrávanie hudby]

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

3
00:00:05,670 --> 00:00:08,560
>> DOUG LLOYD: OK, tak na
tento bod v priebehu,

4
00:00:08,560 --> 00:00:15,300
sme sa vzťahuje mnoho základy C.
Vieme, že veľa o premenných, polí,

5
00:00:15,300 --> 00:00:17,610
ukazovatele, že všetky dobré veci.

6
00:00:17,610 --> 00:00:21,610
Tí, ktorí sú nejako postavený
Ak chcete zobraziť ako základy,

7
00:00:21,610 --> 00:00:23,880
ale môžeme urobiť viac, že ​​jo?

8
00:00:23,880 --> 00:00:27,930
Môžeme kombinovať veci
spolu zaujímavými spôsobmi.

9
00:00:27,930 --> 00:00:31,010
>> A tak poďme to urobiť, začnime
vetviť, čo C nám dáva,

10
00:00:31,010 --> 00:00:35,270
a začať vytvárať vlastné údaje
štruktúry pomocou týchto stavebných

11
00:00:35,270 --> 00:00:40,590
bloky dohromady niečo robiť
naozaj cenné, užitočné.

12
00:00:40,590 --> 00:00:43,420
Jeden spôsob, ako to môžeme urobiť, je
hovoriť o zbierok.

13
00:00:43,420 --> 00:00:48,360
Tak zatiaľ sme mali jeden druh dát
štruktúra pre zastupovanie kolekcií

14
00:00:48,360 --> 00:00:51,030
z páči hodnoty, podobné hodnoty.

15
00:00:51,030 --> 00:00:52,350
To by byť pole.

16
00:00:52,350 --> 00:00:57,020
Máme zbierky celé čísla, alebo
zbierky postáv a tak ďalej.

17
00:00:57,020 --> 00:01:00,890
>> Štruktúry sú tiež akýsi dát
štruktúra pre zber informácií,

18
00:01:00,890 --> 00:01:03,220
ale nie je to pre zbieranie ako hodnoty.

19
00:01:03,220 --> 00:01:08,090
To zvyčajne sa miešajú rôzne dátové typy
spolu vnútri jedinej krabici.

20
00:01:08,090 --> 00:01:10,750
Ale nie je to samo o sebe
použité k reťazcu spoločne

21
00:01:10,750 --> 00:01:16,920
alebo sa pripojiť dohromady podobné
predmety, ako pole.

22
00:01:16,920 --> 00:01:20,960
Polia sú skvelé pre
prvok vzhlédnout, ale Recall

23
00:01:20,960 --> 00:01:24,262
že je to veľmi ťažké
pre vloženie do matice,

24
00:01:24,262 --> 00:01:26,470
ak sme na vkladanie
do samého konca tohto poľa.

25
00:01:26,470 --> 00:01:29,730
>> A najlepším príkladom mám
pre ktoré je insertion sort.

26
00:01:29,730 --> 00:01:31,650
Ak si spomínate na naše video
na vloženie druhu,

27
00:01:31,650 --> 00:01:34,110
tam bolo veľa
výdavkom pri majúce

28
00:01:34,110 --> 00:01:37,970
vyzdvihnúť prvky a presunúť ich
z cesty, aby sa zmestili niečo

29
00:01:37,970 --> 00:01:41,290
do stredu vášho poľa.

30
00:01:41,290 --> 00:01:44,690
Pole tiež trpí inou
Problém, ktorý je nepružnosť.

31
00:01:44,690 --> 00:01:47,150
Keď sme sa vyhlásiť poľa,
dostaneme jeden pokus na to.

32
00:01:47,150 --> 00:01:49,790
Dostávame sa povedať, chcem
Táto mnoho prvkov.

33
00:01:49,790 --> 00:01:51,940
Môže byť 100, môže to
byť 1000, by to mohlo

34
00:01:51,940 --> 00:01:55,930
byť x, kde x je číslo, ktoré užívateľ
Dal nám na výzvu alebo na príkaz

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

36
00:01:56,630 --> 00:01:59,905
>> Ale my sme len jeden pokus na to, my
nedostanú do tej doby hovoria oh, som vlastne

37
00:01:59,905 --> 00:02:04,360
potreboval 101, alebo som potreboval X plus 20.

38
00:02:04,360 --> 00:02:07,910
Príliš neskoro, sme už vyhlásila
poľa, a ak chceme získať 101 alebo x

39
00:02:07,910 --> 00:02:12,050
zvýšenej o 20, musíme vyhlásiť,
úplne iná poľa,

40
00:02:12,050 --> 00:02:15,540
skopírovať všetky prvky poľa
cez, a potom máme dosť.

41
00:02:15,540 --> 00:02:19,880
A čo keď sme opäť zle, čo
ak by sme skutočne potrebujú 102, alebo X plus 40,

42
00:02:19,880 --> 00:02:21,970
musíme to urobiť znovu.

43
00:02:21,970 --> 00:02:26,250
Takže sú veľmi nepružné
pre zmenu veľkosti naše dáta,

44
00:02:26,250 --> 00:02:29,360
ale ak by sme skombinovať niektoré
základy, ktoré sme už

45
00:02:29,360 --> 00:02:33,230
dozvedeli o ukazovatele a štruktúr,
najmä s využitím dynamickej pamäte

46
00:02:33,230 --> 00:02:36,180
alokácie s malloc, my
môže dať tieto kúsky dohromady

47
00:02:36,180 --> 00:02:40,960
Ak chcete vytvoriť nové dáta structure-- A
jednotlivo spojené zoznam by sme mohli say--

48
00:02:40,960 --> 00:02:45,400
ktorý nám umožňuje rast a
zmenšiť súbor hodnôt,

49
00:02:45,400 --> 00:02:48,800
a nebudeme mať žiadnu zbytočný priestor.

50
00:02:48,800 --> 00:02:53,320
>> Takže znovu, nazývame túto myšlienku,
tento pojem, pripojený zoznam.

51
00:02:53,320 --> 00:02:56,320
Najmä v tomto videu sme
hovorí o jednotlivo Google zoznamu

52
00:02:56,320 --> 00:02:59,185
a potom ďalšie videá si pohovoríme
asi dvojnásobne spojové zoznamy, ktoré

53
00:02:59,185 --> 00:03:01,560
je len variáciou na tému tu.

54
00:03:01,560 --> 00:03:05,200
Ale single previazaný zoznam
sa skladá z uzlov,

55
00:03:05,200 --> 00:03:08,559
uzly byť len abstraktné term--
Je to proste niečo volám

56
00:03:08,559 --> 00:03:10,350
to je druh
štruktúra, v podstate, ja som?

57
00:03:10,350 --> 00:03:16,190
Len tak to nazývať node-- a to
uzol má dvoch členov, alebo dve polia.

58
00:03:16,190 --> 00:03:20,300
To má dáta, zvyčajne
integer, charakter float,

59
00:03:20,300 --> 00:03:23,790
alebo by mohol byť nejaký iný typ dát
že ste definovali pomocou typu def.

60
00:03:23,790 --> 00:03:29,290
A obsahuje ukazovateľ na
iný uzol rovnakého typu.

61
00:03:29,290 --> 00:03:34,710
>> Takže máme dve veci vo vnútri
tento uzol, dát a ukazovateľ

62
00:03:34,710 --> 00:03:36,380
do iného uzla.

63
00:03:36,380 --> 00:03:39,370
A ak začnete vizualizovať
to, môžete si o tom myslíte

64
00:03:39,370 --> 00:03:42,280
ako reťaz uzlov, ktoré
sú spojené dohromady.

65
00:03:42,280 --> 00:03:45,070
Máme prvý uzol, to
obsahuje dáta, a ukazovateľ

66
00:03:45,070 --> 00:03:49,110
do druhého uzla, ktorý obsahuje
dát, a ukazovateľ na tretiu uzla.

67
00:03:49,110 --> 00:03:52,940
A tak to je dôvod, prečo sme ho hovoru
spájať zoznam, oni sú navzájom prepojené.

68
00:03:52,940 --> 00:03:56,070
>> Čo to zvláštne
Štruktúra uzol vyzerať?

69
00:03:56,070 --> 00:04:01,120
No, ak si spomínam z nášho videa na
definovanie vlastných typov, s typom def,

70
00:04:01,120 --> 00:04:05,400
môžeme definovať structure-- a
zadajte definovať štruktúru, ako je tento.

71
00:04:05,400 --> 00:04:11,240
tyepdef struct sllist, a potom som
pomocou hodnoty slovo tu ľubovoľne

72
00:04:11,240 --> 00:04:13,891
uviesť akýkoľvek typ dát, naozaj.

73
00:04:13,891 --> 00:04:16,890
Dalo by sa preniesť na celé číslo alebo plaváku,
by ste mohli mať, čo chcete.

74
00:04:16,890 --> 00:04:19,389
To nie je obmedzený len
celé čísla, alebo niečo také.

75
00:04:19,389 --> 00:04:22,790
Takže hodnota je len ľubovoľná
dátový typ, a potom ukazovateľ

76
00:04:22,790 --> 00:04:26,310
do iného uzla rovnakého typu.

77
00:04:26,310 --> 00:04:29,690
>> Teraz, tam je trochu háčik
Tu sa definuje štruktúru

78
00:04:29,690 --> 00:04:33,030
keď je to štruktúra vlastné referenčné.

79
00:04:33,030 --> 00:04:35,340
Musím mať dočasnú
meno pre moju štruktúru.

80
00:04:35,340 --> 00:04:37,640
Na konci dňa som
jasne to chcete nazývať

81
00:04:37,640 --> 00:04:43,030
SLL uzol, to je nakoniec nový
meno časť mojej definície typu,

82
00:04:43,030 --> 00:04:47,450
ale nemôžem použiť SLL uzol
v stredu tohto.

83
00:04:47,450 --> 00:04:51,430
Dôvodom je, nemám
vytvoril typ nazvaný SLL uzol

84
00:04:51,430 --> 00:04:55,200
až som narazila tento posledný bod tu.

85
00:04:55,200 --> 00:04:59,720
Až do tohto bodu, musím mať
iný spôsob, ako sa odkazovať na tento typ dát.

86
00:04:59,720 --> 00:05:02,440
>> A to je samo
referenčné dátový typ.

87
00:05:02,440 --> 00:05:06,314
Je to, to je typ dát
Štruktúra, ktorá obsahuje údaje,

88
00:05:06,314 --> 00:05:08,480
a ukazovateľ na ďalšie
štruktúra rovnakého typu.

89
00:05:08,480 --> 00:05:11,750
Tak som potrebné, aby bolo možné odkazovať na
Tento typ dát aspoň dočasne,

90
00:05:11,750 --> 00:05:14,910
tak dávať to dočasné
Meno struct sllist

91
00:05:14,910 --> 00:05:18,540
mi umožňuje potom povedzte Chcem
ukazovateľ do iného struct sllist,

92
00:05:18,540 --> 00:05:24,690
struct sllist hviezda, a potom
potom, čo som dokončil definíciu,

93
00:05:24,690 --> 00:05:27,220
Aj teraz môže hovoriť tento typ uzol SLL.

94
00:05:27,220 --> 00:05:30,520
>> Takže to je dôvod, prečo ste vidieť, že je to
dočasný názov tu,

95
00:05:30,520 --> 00:05:31,879
ale trvalé meno sem.

96
00:05:31,879 --> 00:05:33,920
Niekedy môžete vidieť
definície štruktúry,

97
00:05:33,920 --> 00:05:36,570
napríklad, že nie sú
vlastný referenčný, že

98
00:05:36,570 --> 00:05:39,390
nemajú tu meno Špecifikátor.

99
00:05:39,390 --> 00:05:43,040
To by len povedať typedef struct,
otvoriť zložená zátvorka a potom ju definovať.

100
00:05:43,040 --> 00:05:45,620
Ale ak ste struct je self
Referenčný, pretože tento je,

101
00:05:45,620 --> 00:05:49,010
je potrebné špecifikovať
dočasný názov typu.

102
00:05:49,010 --> 00:05:51,310
Ale nakoniec, teraz
že sme urobili to,

103
00:05:51,310 --> 00:05:53,620
môžeme len odkazovať na
tieto uzly, tieto jednotky,

104
00:05:53,620 --> 00:05:57,900
ako SLL uzly na účely
zvyšku tohto videa.

105
00:05:57,900 --> 00:06:00,900
>> Dobre, takže vieme, ako
vytvoriť prepojený zoznamu uzlov.

106
00:06:00,900 --> 00:06:03,240
Vieme, ako definovať
prepojený zoznam uzol.

107
00:06:03,240 --> 00:06:06,670
Teraz, keď ideme na začiatok
ich použitie zhromažďovať informácie,

108
00:06:06,670 --> 00:06:10,360
tam je niekoľko operácií sme
musí pochopiť a pracovať s.

109
00:06:10,360 --> 00:06:12,860
Potrebujeme vedieť, ako vytvoriť
prepojený zoznam zo vzduchu.

110
00:06:12,860 --> 00:06:14,901
Ak nie je žiadny zoznam už,
chceme začať jeden.

111
00:06:14,901 --> 00:06:16,960
Preto musíme byť schopní
vytvoriť prepojený zoznam,

112
00:06:16,960 --> 00:06:19,130
musíme pravdepodobne hľadať
v zozname odkazov

113
00:06:19,130 --> 00:06:21,830
nájsť prvok, čo hľadáme.

114
00:06:21,830 --> 00:06:24,430
Musíme byť schopní vložiť
nové veci do zoznamu,

115
00:06:24,430 --> 00:06:25,930
chceme náš zoznam, aby mohol rásť.

116
00:06:25,930 --> 00:06:28,638
A rovnako, chceme byť schopní
odstrániť veci z nášho zoznamu,

117
00:06:28,638 --> 00:06:30,250
chceme, aby náš zoznam, aby bolo možné zmenšovať.

118
00:06:30,250 --> 00:06:32,160
A na konci nášho
programy, najmä

119
00:06:32,160 --> 00:06:34,550
Ak si spomínate, že sme
dynamicky prideľovanie pamäte

120
00:06:34,550 --> 00:06:38,337
vytvoriť tieto zoznamy typicky,
chceme oslobodiť všetkých, že pamäť

121
00:06:38,337 --> 00:06:39,670
Keď sme hotoví s ňou pracovať.

122
00:06:39,670 --> 00:06:44,627
A preto musíme byť schopní Ak chcete odstrániť
Celý spájať zoznam v jednom zlyhania Swoop.

123
00:06:44,627 --> 00:06:46,460
Takže poďme prejsť
niektoré z týchto operácií

124
00:06:46,460 --> 00:06:51,192
a ako ich môžeme predstaviť,
hovorí v pseudokódu kóde špecificky.

125
00:06:51,192 --> 00:06:53,150
Takže chceme vytvoriť
spájať zoznam, takže možno sme

126
00:06:53,150 --> 00:06:56,480
chcete definovať funkciu
s týmto prototypom.

127
00:06:56,480 --> 00:07:01,690
SLL uzol hviezda, tvoriť, a ja som okolo
v jednom argumentu, niektorí ľubovoľné dáta

128
00:07:01,690 --> 00:07:05,530
typ opäť nejakého ľubovoľného typu dát.

129
00:07:05,530 --> 00:07:10,482
Ale ja som returning-- túto funkciu by mal
vrátiť ku mne ukazovateľ, na single

130
00:07:10,482 --> 00:07:11,190
spájať zoznam uzol.

131
00:07:11,190 --> 00:07:14,050
Opäť platí, že sa snažíme o vytvorenie
prepojený zoznam zo vzduchu,

132
00:07:14,050 --> 00:07:17,900
takže musím ukazovateľ
tento zoznam, keď som urobil.

133
00:07:17,900 --> 00:07:19,420
>> Takže aké sú kroky tu ide?

134
00:07:19,420 --> 00:07:20,960
No, prvá vec, ja som
chystá urobiť, je dynamicky

135
00:07:20,960 --> 00:07:22,550
prideliť priestor pre nový uzol.

136
00:07:22,550 --> 00:07:26,689
Opäť sme vytvoriť to z tenkej
vzduch, takže musíme malloc priestor pre to.

137
00:07:26,689 --> 00:07:28,480
A samozrejme okamžite
potom, čo sme malloc,

138
00:07:28,480 --> 00:07:31,692
vždy skontrolujte, či, že naše
pointer-- sme nedostali naspäť null.

139
00:07:31,692 --> 00:07:33,650
Vzhľadom k tomu, keď sa budeme snažiť a
podriadenosť ukazovatele null,

140
00:07:33,650 --> 00:07:36,190
budeme trpieť
segfault a my nechceme, že.

141
00:07:36,190 --> 00:07:39,510
>> Potom sme sa chcete vyplniť v tejto oblasti,
chceme inicializovať hodnota poľa

142
00:07:39,510 --> 00:07:41,690
a inicializovať ďalšie pole.

143
00:07:41,690 --> 00:07:45,450
A potom chceme to-- nakoniec ako
prototyp funkcie indicates-- chceme

144
00:07:45,450 --> 00:07:49,940
vrátiť ukazovateľ na uzol SLL.

145
00:07:49,940 --> 00:07:51,710
Tak čo, aby to vyzerať vizuálne?

146
00:07:51,710 --> 00:07:55,230
No, v prvom budeme dynamicky
prideliť priestor pre nové SLL uzla,

147
00:07:55,230 --> 00:07:58,320
takže sme malloc-- to
vizuálne reprezentácie

148
00:07:58,320 --> 00:08:00,020
uzla sme práve vytvorili.

149
00:08:00,020 --> 00:08:02,757
A skontrolujte, či
to nie je null-- v tomto prípade,

150
00:08:02,757 --> 00:08:04,840
obraz nebude mať
ukázal, či je to null,

151
00:08:04,840 --> 00:08:07,298
by sme dostatok pamäte,
tak sme dobré tam ísť.

152
00:08:07,298 --> 00:08:10,200
Takže teraz sme na krok C,
inicializáciu poľa uzly hodnoty.

153
00:08:10,200 --> 00:08:12,280
No, na základe tejto funkcii
volajte Ja používam tu,

154
00:08:12,280 --> 00:08:16,700
vyzerá to chcem odovzdať 6,
Takže budem 6 v poli hodnoty.

155
00:08:16,700 --> 00:08:18,865
Teraz, inicializovať ďalšie pole.

156
00:08:18,865 --> 00:08:21,640
No, čo mám robiť tam,
nie je nič, čo ďalej, vpravo,

157
00:08:21,640 --> 00:08:23,600
to je jediná vec, v zozname.

158
00:08:23,600 --> 00:08:27,206
Takže to, čo je ďalšia vec na zozname?

159
00:08:27,206 --> 00:08:29,660
>> Nemalo by ukazovať na nič, že jo.

160
00:08:29,660 --> 00:08:33,600
Nič iné tam, tak to, čo je
poňatie vieme, že je to nothing--

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

162
00:08:35,638 --> 00:08:37,929
Malo by to byť snáď chceme
dať ukazovatele null tam,

163
00:08:37,929 --> 00:08:40,178
a ja predstavujú null
ukazovateľ ako len červené pole,

164
00:08:40,178 --> 00:08:41,559
nemôžeme ísť ďalej.

165
00:08:41,559 --> 00:08:44,430
Ako budeme o niečo vidieť neskôr,
budeme mať nakoniec aj reťaze

166
00:08:44,430 --> 00:08:46,330
šípok pripojenie
tieto uzly dohromady,

167
00:08:46,330 --> 00:08:48,480
ale keď narazí na
červené pole, to je null,

168
00:08:48,480 --> 00:08:51,150
nemôžeme ísť ďalej,
že je koniec zoznamu.

169
00:08:51,150 --> 00:08:53,960
>> A konečne, chceme len, aby
vrátiť ukazovateľ do tohto uzla.

170
00:08:53,960 --> 00:08:56,160
Takže budeme hovoriť nový,
a vráti nový

171
00:08:56,160 --> 00:08:59,370
takže ho možno použiť v
bez ohľadu na funkciu ju vytvoril.

172
00:08:59,370 --> 00:09:03,100
Takže tam ideme, sme vytvorili single
spájať zoznam uzol zo vzduchu,

173
00:09:03,100 --> 00:09:05,920
a teraz máme zoznam, môžeme pracovať.

174
00:09:05,920 --> 00:09:08,260
>> Teraz povedzme, že už
majú veľký reťaz,

175
00:09:08,260 --> 00:09:09,800
a chceme nájsť niečo, čo v ňom.

176
00:09:09,800 --> 00:09:12,716
A chceme funkciu, ktorá sa deje
vrátiť true alebo false, v závislosti

177
00:09:12,716 --> 00:09:15,840
na tom, či hodnota existuje v tomto zozname.

178
00:09:15,840 --> 00:09:18,160
Funkcia prototyp, alebo
Vyhlásenie pre túto funkciu,

179
00:09:18,160 --> 00:09:23,320
môže vyzerať ako tohle-- bool nájsť, a
potom chceme odovzdať dva argumenty.

180
00:09:23,320 --> 00:09:26,996
>> Prvý z nich, je ukazovateľ na
Prvý prvok v Google zoznamu.

181
00:09:26,996 --> 00:09:29,620
To je v skutočnosti niečo, čo budete
vždy chcú sledovať,

182
00:09:29,620 --> 00:09:33,110
a v skutočnosti by mohlo byť niečo, čo
si dokonca dať do globálne premenné.

183
00:09:33,110 --> 00:09:35,360
Akonáhle si vytvoriť zoznam,
vždy, vždy

184
00:09:35,360 --> 00:09:38,990
Chcete sledovať veľmi
Prvý prvok zoznamu.

185
00:09:38,990 --> 00:09:43,690
Týmto spôsobom sa môžete obrátiť na všetky ostatné
prvky podľa práve v nadväznosti na reťaz,

186
00:09:43,690 --> 00:09:47,300
bez toho aby museli držať ukazovatele
neporušené na každý prvok.

187
00:09:47,300 --> 00:09:50,920
Jediné, čo potrebujete mať prehľad o prvú
jedno, pokiaľ sa všetci zreťazenie.

188
00:09:50,920 --> 00:09:52,460
>> A potom druhá vec
sme okolo znovu

189
00:09:52,460 --> 00:09:54,376
je ľubovoľne some--
bez ohľadu na typ dát sme

190
00:09:54,376 --> 00:09:59,640
hľadá je vnútri
dúfajme, že jeden z uzlov v zozname.

191
00:09:59,640 --> 00:10:00,980
Takže aké sú kroky?

192
00:10:00,980 --> 00:10:04,250
No, prvá vec, ktorú robíme, je
vytvoríme priečny ukazovateľ

193
00:10:04,250 --> 00:10:06,015
ukazujúci na zoznamoch hlavy.

194
00:10:06,015 --> 00:10:08,890
No, prečo to robíme, že sme už
majú ukazovateľ na zoznamoch hlave,

195
00:10:08,890 --> 00:10:10,974
prečo nie my len presunúť, že jedna okolo?

196
00:10:10,974 --> 00:10:13,140
No, ako som práve povedal,
je to naozaj dôležité pre nás

197
00:10:13,140 --> 00:10:17,580
vždy sledovať z
Úplne prvý prvok v zozname.

198
00:10:17,580 --> 00:10:21,270
A tak je to vlastne lepšie
vytvoriť duplikát, ktorý,

199
00:10:21,270 --> 00:10:25,350
a použiť sa pohybovať, takže sme nikdy
náhodne vzdialiť, alebo vždy

200
00:10:25,350 --> 00:10:30,430
majú ukazovateľ v určitom okamihu, ktorý je
priamo na prvý prvok v zozname.

201
00:10:30,430 --> 00:10:33,290
Takže je lepšie vytvoriť
Druhý, ktorý používame k pohybu.

202
00:10:33,290 --> 00:10:35,877
>> Potom sme len porovnať, či
hodnota poľa v tomto uzle

203
00:10:35,877 --> 00:10:38,960
je to, čo hľadáme, a ak je to
nie, len sme presunúť na ďalší uzol.

204
00:10:38,960 --> 00:10:41,040
A my sme pokračovať v tom, že
cez, a znovu, a znovu,

205
00:10:41,040 --> 00:10:44,811
kým buď nájsť
prvok, alebo si hit

206
00:10:44,811 --> 00:10:47,310
null-- sme došli na koniec
zoznamu a je to tam nie je.

207
00:10:47,310 --> 00:10:50,540
To by malo snáď nehovorí
aby vás ako práve lineárny vyhľadávania,

208
00:10:50,540 --> 00:10:54,430
sme len replikácie ju
single spájať zoznam štruktúra

209
00:10:54,430 --> 00:10:56,280
namiesto použitia poľa, ako to urobiť.

210
00:10:56,280 --> 00:10:58,210
>> Tak tu je príklad
single previazaný zoznam.

211
00:10:58,210 --> 00:11:00,043
Ten sa skladá z
päť uzlov, a my máme

212
00:11:00,043 --> 00:11:04,330
ukazovateľ na hlave
Zoznam, ktorý sa nazýva zoznam.

213
00:11:04,330 --> 00:11:07,385
Prvá vec, ktorú chceme urobiť, je
znovu vytvoriť túto traversal ukazovateľ.

214
00:11:07,385 --> 00:11:09,760
Takže teraz máme dva ukazovatele
tento bod na rovnakú vec.

215
00:11:09,760 --> 00:11:15,025
>> Teraz, všimnite si aj tu, ja nie
musieť malloc žiadny priestor pre tráv.

216
00:11:15,025 --> 00:11:18,970
Nepovedal som, že tráv rovná malloc
niečo, že uzol už existuje,

217
00:11:18,970 --> 00:11:21,160
že priestor v pamäti už existuje.

218
00:11:21,160 --> 00:11:24,290
Takže všetko, čo som vlastne robí, je
vytvorenie ďalšej ukazovateľ na neho.

219
00:11:24,290 --> 00:11:28,210
Nie som mallocing ďalšie
priestor, stačí teraz dva ukazovatele

220
00:11:28,210 --> 00:11:31,370
smerujúce k rovnakej veci.

221
00:11:31,370 --> 00:11:33,710
>> Takže je 2 to, čo som hľadal?

222
00:11:33,710 --> 00:11:37,220
No, takže namiesto toho som si
budeme sťahovať do ďalšej.

223
00:11:37,220 --> 00:11:41,740
Takže v podstate by som povedal,
tráv sa rovná tráv ďalšie.

224
00:11:41,740 --> 00:11:43,630
Je 3 to, čo som hľadal, no.

225
00:11:43,630 --> 00:11:45,780
Tak som aj naďalej ísť
vďaka, až nakoniec

226
00:11:45,780 --> 00:11:48,690
dostať sa až 6, čo je to, čo som hľadal
pre založené na volanie funkcie

227
00:11:48,690 --> 00:11:51,600
Aj majú v hornej časti
tam, a tak som urobil.

228
00:11:51,600 --> 00:11:54,150
>> A teraz, čo keď element, že som
hľadáte, nie je v zozname,

229
00:11:54,150 --> 00:11:55,510
je to ešte bude fungovať?

230
00:11:55,510 --> 00:11:57,120
No, zistíte, že zoznam
tu je nepatrne odlišný,

231
00:11:57,120 --> 00:11:59,410
a to je ďalšia vec, ktorá je
dôležité s previazané zoznamy,

232
00:11:59,410 --> 00:12:01,780
nemusíte zachovať
je v ľubovoľnom poradí.

233
00:12:01,780 --> 00:12:05,390
Môžete, ak chcete, ale
možno ste už zaznamenali

234
00:12:05,390 --> 00:12:09,310
že nie sme sledovanie
aký počet element sme na.

235
00:12:09,310 --> 00:12:13,150
>> A to je druh z jedného obchodu, ktorý sme
majú s Google zoznamu veršov polí,

236
00:12:13,150 --> 00:12:15,300
Je to nemáme
náhodný prístup ešte.

237
00:12:15,300 --> 00:12:18,150
Nemôžeme len tak povedať, chcem
ísť na 0. prvku,

238
00:12:18,150 --> 00:12:21,410
alebo 6. náplňou mojej poľa,
čo sa dá robiť v poli.

239
00:12:21,410 --> 00:12:25,080
Nemôžem povedať, že chcem ísť do
0. prvok, alebo 6. element,

240
00:12:25,080 --> 00:12:30,360
alebo 25. prvok môjho zoznamu Google,
nie je index spojený s nimi.

241
00:12:30,360 --> 00:12:33,660
A tak to nezáleží
ak by sme zachovať náš zoznam v poradí.

242
00:12:33,660 --> 00:12:36,080
Ak chcete, aby vás
Určite môže, ale je tu

243
00:12:36,080 --> 00:12:38,567
žiadny dôvod, prečo je potrebné, aby
byť zachované v ľubovoľnom poradí.

244
00:12:38,567 --> 00:12:40,400
Takže znova, poďme sa pokúsiť
nájsť 6 v tomto zozname.

245
00:12:40,400 --> 00:12:43,200
No, začneme u
začiatok, nenájdeme 6,

246
00:12:43,200 --> 00:12:47,690
a potom pokračujeme nenájdenia
6, kým sa nakoniec dostať sem.

247
00:12:47,690 --> 00:12:52,790
Takže práve teraz tráv body do uzla
obsahujúce 8, a šesť nie je tam.

248
00:12:52,790 --> 00:12:55,250
>> Takže ďalším krokom by bolo
prejdete na ďalší ukazovateľ,

249
00:12:55,250 --> 00:12:57,440
tak povedať, tráv rovná tráv ďalšie.

250
00:12:57,440 --> 00:13:00,750
No, tráv ďalšie, indikované
Tamojší červená krabička, je null.

251
00:13:00,750 --> 00:13:03,020
Takže tam kam inam
go, a tak v tomto bode

252
00:13:03,020 --> 00:13:06,120
môžeme konštatovať, že sme dosiahli
koniec zoznamu Google,

253
00:13:06,120 --> 00:13:07,190
a 6 nie je tam.

254
00:13:07,190 --> 00:13:10,980
A to by sa vrátil
false v tomto prípade.

255
00:13:10,980 --> 00:13:14,540
>> OK, ako sme sa vložiť nový
uzol do Google zoznamu?

256
00:13:14,540 --> 00:13:17,310
Takže sme boli schopní vytvoriť
prepojený zoznam z ničoho,

257
00:13:17,310 --> 00:13:19,370
ale pravdepodobne chcieť
vybudovať reťazca a nie

258
00:13:19,370 --> 00:13:22,620
vytvoriť veľa odlišných zoznamov.

259
00:13:22,620 --> 00:13:25,700
Chceme mať jeden zoznam, ktorý
má veľa uzlov v ňom,

260
00:13:25,700 --> 00:13:28,040
nie banda zoznamov s jedným uzlom.

261
00:13:28,040 --> 00:13:31,260
Takže môžeme nielen udržať pomocou Vytvoriť
Funkcie sme definovali skôr, teraz sme

262
00:13:31,260 --> 00:13:33,860
chcú vložiť do
Zoznam, ktorý už existuje.

263
00:13:33,860 --> 00:13:36,499
>> Takže tomto prípade, ideme
odovzdať dva argumenty,

264
00:13:36,499 --> 00:13:39,290
ukazovateľ na hlave, ktorý
spájať zoznam, ktorý chceme pridať.

265
00:13:39,290 --> 00:13:40,910
Opäť platí, že je dôvod, prečo je to tak
dôležité, že sme vždy

266
00:13:40,910 --> 00:13:43,400
sledovať to, pretože
je to jediný spôsob, ako skutočne

267
00:13:43,400 --> 00:13:46,690
musieť odkazovať sa na celý zoznam je
len tým, že ukazovateľ na prvý prvok.

268
00:13:46,690 --> 00:13:49,360
Takže chceme odovzdať v
ukazovateľ na tento prvý prvok,

269
00:13:49,360 --> 00:13:52,226
a bez ohľadu na hodnotu, ktorú
chcete pridať do zoznamu.

270
00:13:52,226 --> 00:13:54,600
A nakoniec táto funkcia
bude vráti ukazovateľ

271
00:13:54,600 --> 00:13:57,980
na nového šéfa prepojeného zoznamu.

272
00:13:57,980 --> 00:13:59,700
>> Aké sú kroky tu ide?

273
00:13:59,700 --> 00:14:02,249
No, rovnako ako u vytvárať,
musíme dynamicky prideľovať

274
00:14:02,249 --> 00:14:05,540
priestor pre nový uzol, a skontrolujte,
istí, že nemáme dostatok pamäte, znova,

275
00:14:05,540 --> 00:14:07,150
preto, že sme pomocou malloc.

276
00:14:07,150 --> 00:14:09,080
Potom chceme naplniť
a vložte uzla,

277
00:14:09,080 --> 00:14:12,730
tak dal číslo, bez ohľadu
val je, do uzla.

278
00:14:12,730 --> 00:14:17,310
Chceme vložiť uzol na
začiatok Google zoznamu.

279
00:14:17,310 --> 00:14:19,619
>> Tam je dôvod, prečo som
to chceš urobiť, a to

280
00:14:19,619 --> 00:14:21,910
môže byť stojí za sekundu
pozastaviť video tu,

281
00:14:21,910 --> 00:14:25,860
a premýšľať o tom, prečo by som chcel
vložiť na začiatku prepojenú

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

283
00:14:26,589 --> 00:14:28,630
Opäť som sa zmienil skôr,
že to naozaj nie je

284
00:14:28,630 --> 00:14:33,020
jedno, či sa nám to uchovať v akomkoľvek
poriadok, takže možno je to stopa.

285
00:14:33,020 --> 00:14:36,040
A si videl, čo by sa stalo, keby sme
Chcel to-- alebo len na sekundu

286
00:14:36,040 --> 00:14:37,360
Pred keď sme išli
pomocou vyhľadávania vám

287
00:14:37,360 --> 00:14:39,235
mohol vidieť, čo by mohlo
sa stalo, keby sme sa snažili

288
00:14:39,235 --> 00:14:41,330
pre vloženie na koniec zoznamu.

289
00:14:41,330 --> 00:14:44,750
Pretože my nemajú
ukazovateľ na koniec zoznamu.

290
00:14:44,750 --> 00:14:47,490
>> Takže dôvod, prečo by som chcel
pre vloženie na začiatku,

291
00:14:47,490 --> 00:14:49,380
je preto, že som to urobiť okamžite.

292
00:14:49,380 --> 00:14:52,730
Mám ukazovateľ na začiatku, a
uvidíme to v vizuálnej v sekunde.

293
00:14:52,730 --> 00:14:55,605
Ale ak chcem vložiť na koniec,
Musím začať od začiatku,

294
00:14:55,605 --> 00:14:58,760
prejsť celú cestu až do
koniec, a potom ho pridajú.

295
00:14:58,760 --> 00:15:01,420
Takže to by znamenalo, že
vložením na koniec zoznamu

296
00:15:01,420 --> 00:15:04,140
stala by sa o n
prevádzku, sa vracia

297
00:15:04,140 --> 00:15:06,720
k našej diskusii o
výpočtovej zložitosť.

298
00:15:06,720 --> 00:15:10,140
To by sa stať o n prevádzky, kde
aj zoznam dostal väčšie a väčšie,

299
00:15:10,140 --> 00:15:13,310
a väčší, bude to čím ďalej
ťažšie križovať niečo

300
00:15:13,310 --> 00:15:14,661
Na konci.

301
00:15:14,661 --> 00:15:17,410
Ale je to vždy naozaj ľahké
pripináčika niečo na začiatku,

302
00:15:17,410 --> 00:15:19,060
ste vždy na začiatku.

303
00:15:19,060 --> 00:15:21,620
>> A uvidíme opäť vizuálne tohto.

304
00:15:21,620 --> 00:15:24,100
A potom raz sme skončili, akonáhle
sme vložil nový uzol,

305
00:15:24,100 --> 00:15:26,880
Chceme sa vrátiť náš ukazovateľ
nový šéf prepojeného zoznamu, ktorý

306
00:15:26,880 --> 00:15:29,213
od tej doby sme vkladanie u
začiatok, bude skutočne

307
00:15:29,213 --> 00:15:31,060
ukazovateľ na uzle sme práve vytvorené.

308
00:15:31,060 --> 00:15:33,280
Poďme si to predstaviť,
pretože si myslím, že to pomôže.

309
00:15:33,280 --> 00:15:36,661
>> Tak tu je náš zoznam, skladá sa z
štyri prvky, uzol obsahujúci 15,

310
00:15:36,661 --> 00:15:38,410
čo ukazuje na uzol
obsahujúce 9, ktorý

311
00:15:38,410 --> 00:15:41,370
poukazuje na uzle, ktorý obsahuje 13,
čo ukazuje na uzol obsahujúce

312
00:15:41,370 --> 00:15:44,840
10, ktorý má null
ukazovateľ pre svoju ďalšiu ukazovateľ

313
00:15:44,840 --> 00:15:47,010
tak to je koniec zoznamu.

314
00:15:47,010 --> 00:15:50,200
Takže chceme vložiť
nový uzol s hodnotou 12

315
00:15:50,200 --> 00:15:52,720
na začiatku tohto
zoznam, čo budeme robiť?

316
00:15:52,720 --> 00:15:58,770
No, v prvom sme malloc priestor pre
uzol, a potom sme dali 12 tam.

317
00:15:58,770 --> 00:16:02,211
>> Takže teraz sme sa dosiahne
bod rozhodnutia, že jo?

318
00:16:02,211 --> 00:16:03,960
Máme pár
ukazovatele, ktoré sme mohli

319
00:16:03,960 --> 00:16:06,770
pohyb, ktorý by sme mali presunúť ako prvý?

320
00:16:06,770 --> 00:16:09,250
Mali by sme urobiť 12 prejdite na
Nový šéf list--

321
00:16:09,250 --> 00:16:13,020
alebo prepáčte, by sme mali 12
poukazujú na staré čele zoznamu?

322
00:16:13,020 --> 00:16:15,319
Alebo by sme mali povedať, že
Zoznam teraz začína na 12.

323
00:16:15,319 --> 00:16:17,110
Tam je rozdiel
tam, a my sa pozrieme

324
00:16:17,110 --> 00:16:19,870
na to, čo sa deje s oboma v druhom.

325
00:16:19,870 --> 00:16:23,350
>> Ale toto vedie k
skvelé tému pre bočnom paneli

326
00:16:23,350 --> 00:16:26,280
čo je, že jeden z
najkomplikovanejšie veci s spojových zoznamov

327
00:16:26,280 --> 00:16:30,980
je usporiadať ukazovatele
v správnom poradí.

328
00:16:30,980 --> 00:16:34,520
Pokiaľ sa pohybovať vecami mimo prevádzku,
môžete skončiť nechtiac

329
00:16:34,520 --> 00:16:36,050
orphaning zvyšok zoznamu.

330
00:16:36,050 --> 00:16:37,300
A tu je príklad toho.

331
00:16:37,300 --> 00:16:40,540
Tak poďme s myšlienkou of--
No, my sme práve vytvorili 12.

332
00:16:40,540 --> 00:16:43,180
Vieme, že 12 bude
nový šéf zoznamu,

333
00:16:43,180 --> 00:16:47,660
a tak prečo nie my len presunúť
ukazovateľ zoznam tam bodu.

334
00:16:47,660 --> 00:16:49,070
>> OK, tak to je dobre.

335
00:16:49,070 --> 00:16:51,560
Takže teraz kde robí 12 ďalší bod?

336
00:16:51,560 --> 00:16:54,580
Myslím, vizuálne vidíme
že to bude ukazovať na 15,

337
00:16:54,580 --> 00:16:57,250
ako ľudia, je to naozaj jasné, k nám.

338
00:16:57,250 --> 00:17:00,300
Ako počítač vie?

339
00:17:00,300 --> 00:17:02,720
Nemáme nič
ukázal na 15 už, že jo?

340
00:17:02,720 --> 00:17:05,869
>> Sme stratili schopnosť sa odkazovať na 15.

341
00:17:05,869 --> 00:17:11,460
Nemôžeme povedať, nový šípku vedľa rovná
niečo, nič tam nie je.

342
00:17:11,460 --> 00:17:13,510
V skutočnosti sme sa osirelý
zvyšok zoznamu

343
00:17:13,510 --> 00:17:16,465
Tým máme
náhodne zlomený reťaz.

344
00:17:16,465 --> 00:17:18,089
A my rozhodne nechceme robiť.

345
00:17:18,089 --> 00:17:20,000
>> Takže poďme späť a skúste to znova.

346
00:17:20,000 --> 00:17:24,060
Možno, že správna vec
je stanoviť ďalšie ukazovatele 12 je

347
00:17:24,060 --> 00:17:28,290
na staré čele zoznamu prvý,
potom sa môžeme presunúť na zoznam u konca.

348
00:17:28,290 --> 00:17:30,420
A v skutočnosti, že je
správne poradie, že my

349
00:17:30,420 --> 00:17:32,836
treba dodržiavať, keď sme
pracuje s jednotlivo prepojeného zoznamu.

350
00:17:32,836 --> 00:17:36,460
Vždy chceme pripojiť
nový prvok do zoznamu,

351
00:17:36,460 --> 00:17:41,010
Než sme sa tento druh
dôležitým krokom zmeny

352
00:17:41,010 --> 00:17:43,360
kde v čele zoznamu je Google.

353
00:17:43,360 --> 00:17:46,740
Opäť platí, že je to tak zásadnú vec,
Nechceme stratiť prehľad o tom.

354
00:17:46,740 --> 00:17:49,310
>> Preto chceme, aby sa uistil, že
všetko sa pripútal spolu,

355
00:17:49,310 --> 00:17:52,040
Než sme sa presunúť tento ukazovateľ.

356
00:17:52,040 --> 00:17:55,300
A tak by to bolo správne poradie,
ktorý je pre pripojenie 12 do zoznamu,

357
00:17:55,300 --> 00:17:57,630
potom hovoria, že zoznam začína 12.

358
00:17:57,630 --> 00:18:00,860
Ak sa nám povedal, že zoznam začína na 12 a
potom sa pokúsil pripojenie 12 do zoznamu,

359
00:18:00,860 --> 00:18:02,193
sme už videli, čo sa stane.

360
00:18:02,193 --> 00:18:04,920
Strácame zoznamu omylom.

361
00:18:04,920 --> 00:18:06,740
>> OK, takže ešte jedna vec, o čom hovoriť.

362
00:18:06,740 --> 00:18:09,750
Čo ak chceme zbaviť
celý spojený zoznam naraz?

363
00:18:09,750 --> 00:18:11,750
Opäť sme mallocing
všetko tento priestor, a tak sme

364
00:18:11,750 --> 00:18:13,351
treba ho uvoľniť, keď budeme hotoví.

365
00:18:13,351 --> 00:18:15,350
Takže teraz chceme zmazať
celý previazaný zoznam.

366
00:18:15,350 --> 00:18:16,850
No, čo chceme robiť?

367
00:18:16,850 --> 00:18:20,460
>> Ak sme dosiahli ukazovatele null, my
chcú zastaviť, inak, stačí zmazať

368
00:18:20,460 --> 00:18:23,420
zvyšok zoznamu a potom ma oslobodil.

369
00:18:23,420 --> 00:18:28,890
Odstráňte zvyšok zoznamu,
a potom uvoľniť aktuálny uzol.

370
00:18:28,890 --> 00:18:32,850
Čo to znie ako,
Akú technikou máme rozprávali

371
00:18:32,850 --> 00:18:35,440
o skôr Znie to ako?

372
00:18:35,440 --> 00:18:39,560
Odstrániť všetci ostatní, potom
vrátiť a odstrániť ma.

373
00:18:39,560 --> 00:18:42,380
>> To je rekurzia, sme urobil
problém o niečo menší,

374
00:18:42,380 --> 00:18:46,910
hovoríme zmazať každého
iné, potom môžete ma odstrániť.

375
00:18:46,910 --> 00:18:50,940
A ďalej po ceste, ktorá uzol
povie, odstrániť všetky ostatné.

376
00:18:50,940 --> 00:18:53,940
Ale nakoniec sa dostaneme k
miesto, kde je zoznam null,

377
00:18:53,940 --> 00:18:55,310
a to je naša základňa prípad.

378
00:18:55,310 --> 00:18:57,010
>> Takže poďme sa pozrieť na to,
a ako to môže fungovať.

379
00:18:57,010 --> 00:18:59,759
Tak tu je náš zoznam, je to rovnaké
Zoznam práve sme hovorili o,

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

381
00:19:00,980 --> 00:19:04,200
Je tu veľa textu tu, ale
Dúfajme, že vizualizácia pomôže.

382
00:19:04,200 --> 00:19:08,557
>> Tak sme have-- a tiež som vytiahol
up nášho stack frames ilustrácie

383
00:19:08,557 --> 00:19:10,890
z nášho videa na volanie komíny,
a dúfajme, že to všetko

384
00:19:10,890 --> 00:19:13,260
spoločne vám ukáže, čo sa deje.

385
00:19:13,260 --> 00:19:14,510
Tak tu je náš pseudokód kód.

386
00:19:14,510 --> 00:19:17,830
Ak dôjdeme null
ukazovateľ, zastaviť, inak,

387
00:19:17,830 --> 00:19:21,320
odstráni zvyšok zoznamu,
potom uvoľnenie aktuálnej uzol.

388
00:19:21,320 --> 00:19:25,700
Takže teraz, list--
ukazovateľ, že sme

389
00:19:25,700 --> 00:19:28,410
odovzdaním zničiť body do 12 rokov.

390
00:19:28,410 --> 00:19:33,340
12 nie je ukazovatele null, takže sme
chystá odstrániť zvyšok zoznamu.

391
00:19:33,340 --> 00:19:35,450
>> Čo vymazanie
Zvyšok z nás zapojiť?

392
00:19:35,450 --> 00:19:37,950
No, to znamená, že dodávanie
zavolať zničiť, povedal

393
00:19:37,950 --> 00:19:42,060
že 15 rokov je na začiatku
Zvyšok zoznamu chceme zničiť.

394
00:19:42,060 --> 00:19:47,480
A tak sa výzva k zničeniu
12 je v istom zmysle v poradí.

395
00:19:47,480 --> 00:19:52,690
Je to mrazené tam a čakal,
zavolať zničiť 15, dokončiť svoju prácu.

396
00:19:52,690 --> 00:19:56,280
>> No, 15 nie je nulový ukazovateľ, a
takže to bude hovoriť, v poriadku,

397
00:19:56,280 --> 00:19:58,450
dobre, odstráňte zvyšok zoznamu.

398
00:19:58,450 --> 00:20:00,760
Zvyšok zoznamu začína
9, a tak sme si len

399
00:20:00,760 --> 00:20:04,514
počkajte, až sa odstrániť všetko, čo
veci, potom sa vrátiť a odstrániť ma.

400
00:20:04,514 --> 00:20:06,680
No 9 to bude hovoriť, no,
Nie som nulový ukazovateľ,

401
00:20:06,680 --> 00:20:09,020
takže ostatní vymažte zoznam tu.

402
00:20:09,020 --> 00:20:11,805
A tak sa snaží a zničiť 13.

403
00:20:11,805 --> 00:20:15,550
13 hovorí, ja nie som nulový ukazovateľ,
to isté, to prejde okolo babku.

404
00:20:15,550 --> 00:20:17,930
10 nie je ukazovatele null, 10
obsahuje ukazovatele null,

405
00:20:17,930 --> 00:20:20,200
ale 10 nie je sám
null ukazovateľ práve teraz,

406
00:20:20,200 --> 00:20:22,470
a tak odovzdá dolár príliš.

407
00:20:22,470 --> 00:20:25,560
>> A teraz zoznam body tam, ho
Naozaj by chcel poukázať na some--

408
00:20:25,560 --> 00:20:28,710
keby som mala viac priestoru v obraze,
že by chcel poukázať na nejaký náhodný vesmíru

409
00:20:28,710 --> 00:20:29,960
že nevieme, čo to je.

410
00:20:29,960 --> 00:20:34,680
To je nulový ukazovateľ hoci, zoznam
je doslova teraz nastavený, že je to hodnota null.

411
00:20:34,680 --> 00:20:36,820
Je to ukázal hneď v tej červeného poľa.

412
00:20:36,820 --> 00:20:39,960
Dosiahli sme ukazovatele null, takže
môžeme zastaviť, a my sme urobili.

413
00:20:39,960 --> 00:20:46,230
>> A tak, že rám je fialová now-- at the
Vrchol stack-- to je aktívny rám,

414
00:20:46,230 --> 00:20:47,017
ale je to hotovo.

415
00:20:47,017 --> 00:20:48,600
Ak sme dosiahli nulový ukazovateľ, zastaviť.

416
00:20:48,600 --> 00:20:51,290
Nechceme robiť nič, my
nemôže uvoľniť ukazovatele null,

417
00:20:51,290 --> 00:20:55,070
sme nemali malloc akýkoľvek
priestor, a tak sme hotoví.

418
00:20:55,070 --> 00:20:57,590
Takže funkcie rámu
je zničená, a my sme

419
00:20:57,590 --> 00:21:00,930
resume-- sme tam, kde sme opustili
off s budúci najvyššia, čo

420
00:21:00,930 --> 00:21:02,807
Je to tmavo modrý rámik tu.

421
00:21:02,807 --> 00:21:04,390
Tak sme vyzdvihnúť presne tam, kde sme skončili.

422
00:21:04,390 --> 00:21:06,598
Vypúšťa sme zvyšku
Zoznam už, takže teraz sme

423
00:21:06,598 --> 00:21:08,000
chystá uvoľniť aktuálny uzly.

424
00:21:08,000 --> 00:21:12,920
Takže teraz sa môžeme oslobodiť tento uzol, a teraz
sme došli na koniec funkcie.

425
00:21:12,920 --> 00:21:16,810
A tak, že funkcia rám je zničená,
a my vyzdvihnúť na svetlo modrou.

426
00:21:16,810 --> 00:21:20,650
>> Tak to says-- už som done--
vypustiť zvyšok zoznamu, tak

427
00:21:20,650 --> 00:21:23,140
oslobodí aktuálny uzol.

428
00:21:23,140 --> 00:21:26,520
A teraz je žltý rámček
späť na vrchole zásobníka.

429
00:21:26,520 --> 00:21:29,655
A tak ako vidíte, sme teraz
ničí zoznam sprava doľava.

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

431
00:21:33,710 --> 00:21:37,280
>> Čo by sa stalo, aj keď,
ak sme robili veci zle?

432
00:21:37,280 --> 00:21:39,410
Rovnako ako keď sme sa pokúšali
pridať prvok.

433
00:21:39,410 --> 00:21:41,909
Ak by sme spackal reťaz, ak
sme sa nepripojili ukazovatele

434
00:21:41,909 --> 00:21:44,690
v správnom poradí, keby sme
len oslobodil prvý prvok,

435
00:21:44,690 --> 00:21:47,420
ak sme práve prepustené
vedúci zoznamu, teraz sme

436
00:21:47,420 --> 00:21:49,642
nemajú žiadny spôsob, ako sa odkazovať na
zvyšok zoznamu.

437
00:21:49,642 --> 00:21:51,350
A tak budeme mať
osirelé všetko,

438
00:21:51,350 --> 00:21:53,880
mali by sme to, čo je
volal k pretečeniu pamäte.

439
00:21:53,880 --> 00:21:56,800
Ak si spomínate z nášho videa
dynamické prideľovanie pamäte,

440
00:21:56,800 --> 00:21:58,650
to nie je moc dobrá vec.

441
00:21:58,650 --> 00:22:00,810
>> Tak ako som povedal, že
sú niekoľko operácií

442
00:22:00,810 --> 00:22:04,010
že musíme použiť na prácu
s spájať zoznam efektívne.

443
00:22:04,010 --> 00:22:08,430
A možno ste si všimli som vynechať jeden,
zmazanie jedného prvku z prepojeného

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

445
00:22:09,064 --> 00:22:10,980
Dôvod, prečo som to urobil
Je to vlastne druh

446
00:22:10,980 --> 00:22:14,360
zradné premýšľať o tom, ako odstrániť
jediný prvok z singly

447
00:22:14,360 --> 00:22:15,600
spájať zoznam.

448
00:22:15,600 --> 00:22:19,950
Musíme byť schopní preskočiť
niečo v zozname, ktorý

449
00:22:19,950 --> 00:22:22,975
znamená, že sme si na point-- my
chcete zmazať túto node--

450
00:22:22,975 --> 00:22:25,350
ale aby sa to robí tak, aby sme
nestratí žiadne informácie,

451
00:22:25,350 --> 00:22:30,530
musíme spojiť to
uzol sem, sem.

452
00:22:30,530 --> 00:22:33,390
>> Tak som to urobil zle nejspíš
z vizuálneho hľadiska.

453
00:22:33,390 --> 00:22:36,830
Takže sme na začiatku nášho
zoznam, sme vybavovaných,

454
00:22:36,830 --> 00:22:40,510
chceme zmazať tento uzol.

455
00:22:40,510 --> 00:22:43,440
Ak by sme jednoducho odstrániť,
sme zlomený reťaz.

456
00:22:43,440 --> 00:22:45,950
Tento uzol tu
sa vzťahuje na všetko ostatné,

457
00:22:45,950 --> 00:22:48,260
že obsahuje reťazec od tady na von.

458
00:22:48,260 --> 00:22:51,190
>> Takže to, čo musíme urobiť skutočne
potom, čo sa dostaneme do tohto bodu,

459
00:22:51,190 --> 00:22:56,670
ich musíme urobiť krok späť jeden, a
pripojenie tohto uzla do tohto uzla,

460
00:22:56,670 --> 00:22:58,590
takže sa potom môžeme zmazať
ten uprostred.

461
00:22:58,590 --> 00:23:02,120
Ale jednotlivo prepojené zoznamy nie
poskytujú nám spôsob, ako ísť späť.

462
00:23:02,120 --> 00:23:05,160
Takže potrebujeme buď udržať
dva ukazovatele, a presunúť ich

463
00:23:05,160 --> 00:23:09,527
druh off kroku, jeden za
ostatné, ako sme ísť, alebo dostať do bodu,

464
00:23:09,527 --> 00:23:11,110
a potom poslať ďalší ukazovateľ cez.

465
00:23:11,110 --> 00:23:13,150
A ako môžete vidieť, to
môže dostať trochu chaotický.

466
00:23:13,150 --> 00:23:15,360
Našťastie, máme
Ďalší spôsob, ako vyriešiť to,

467
00:23:15,360 --> 00:23:17,810
keď hovoríme o dvojnásobne spojových zoznamov.

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

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