1
00:00:00,000 --> 00:00:02,832
>> [Přehrávání 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 průběhu,

4
00:00:08,560 --> 00:00:15,300
jsme se vztahuje mnoho základy C.
Víme, že hodně o proměnných, polí,

5
00:00:15,300 --> 00:00:17,610
ukazatele, že všechny dobré věci.

6
00:00:17,610 --> 00:00:21,610
Ti, kteří jsou nějak postavený
Chcete-li zobrazit jako základy,

7
00:00:21,610 --> 00:00:23,880
ale můžeme udělat víc, že ​​jo?

8
00:00:23,880 --> 00:00:27,930
Můžeme kombinovat věci
spolu zajímavými způsoby.

9
00:00:27,930 --> 00:00:31,010
>> A tak pojďme to udělat, začněme
větvit, co C nám dává,

10
00:00:31,010 --> 00:00:35,270
a začít vytvářet vlastní údaje
struktury pomocí těchto stavebních

11
00:00:35,270 --> 00:00:40,590
bloky dohromady něco dělat
opravdu cenné, užitečné.

12
00:00:40,590 --> 00:00:43,420
Jeden způsob, jak to můžeme udělat, je
mluvit o sbírek.

13
00:00:43,420 --> 00:00:48,360
Tak zatím jsme měli jeden druh dat
struktura pro zastupování kolekcí

14
00:00:48,360 --> 00:00:51,030
z líbí hodnoty, podobné hodnoty.

15
00:00:51,030 --> 00:00:52,350
To by být pole.

16
00:00:52,350 --> 00:00:57,020
Máme sbírky celá čísla, nebo
sbírky postav a tak dále.

17
00:00:57,020 --> 00:01:00,890
>> Struktury jsou také jakýsi dat
struktura pro sběr informací,

18
00:01:00,890 --> 00:01:03,220
ale není to pro sbírání jako hodnoty.

19
00:01:03,220 --> 00:01:08,090
To obvykle se mísí různé datové typy
spolu uvnitř jediné krabici.

20
00:01:08,090 --> 00:01:10,750
Ale není to samo o sobě
použity k řetězci společně

21
00:01:10,750 --> 00:01:16,920
nebo se připojit dohromady podobné
předměty, jako pole.

22
00:01:16,920 --> 00:01:20,960
Pole jsou skvělé pro
prvek vzhlédnout, ale Recall

23
00:01:20,960 --> 00:01:24,262
že je to velmi obtížné
pro vložení do matice,

24
00:01:24,262 --> 00:01:26,470
pokud jsme na vkládání
do samého konce tohoto pole.

25
00:01:26,470 --> 00:01:29,730
>> A nejlepším příkladem mám
pro které je insertion sort.

26
00:01:29,730 --> 00:01:31,650
Pokud si vzpomínáte na naše video
na vložení druhu,

27
00:01:31,650 --> 00:01:34,110
tam bylo hodně
výdajem při mající

28
00:01:34,110 --> 00:01:37,970
vyzvednout prvky a přesunout je
z cesty, aby se vešly něco

29
00:01:37,970 --> 00:01:41,290
do středu vašeho pole.

30
00:01:41,290 --> 00:01:44,690
Pole také trpí jinou
Problém, který je nepružnost.

31
00:01:44,690 --> 00:01:47,150
Když jsme se prohlásit pole,
dostaneme jeden pokus na to.

32
00:01:47,150 --> 00:01:49,790
Dostáváme se říci, chci
Tato mnoho prvků.

33
00:01:49,790 --> 00:01:51,940
Může být 100, může to
být 1000, by to mohlo

34
00:01:51,940 --> 00:01:55,930
být x, kde x je číslo, které uživatel
Dal nám na výzvu nebo na příkaz

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

36
00:01:56,630 --> 00:01:59,905
>> Ale my jsme jen jeden pokus na to, my
nedostanou do té doby říkají oh, jsem vlastně

37
00:01:59,905 --> 00:02:04,360
potřeboval 101, nebo jsem potřeboval X plus 20.

38
00:02:04,360 --> 00:02:07,910
Příliš pozdě, jsme již prohlásila
pole, a chceme-li získat 101 nebo x

39
00:02:07,910 --> 00:02:12,050
zvýšené o 20, musíme prohlásit,
úplně jiná pole,

40
00:02:12,050 --> 00:02:15,540
zkopírovat všechny prvky pole
přes, a pak máme dost.

41
00:02:15,540 --> 00:02:19,880
A co když jsme opět špatně, co
pokud bychom skutečně potřebují 102, nebo X plus 40,

42
00:02:19,880 --> 00:02:21,970
musíme to udělat znovu.

43
00:02:21,970 --> 00:02:26,250
Takže jsou velmi neflexibilní
pro změnu velikosti naše data,

44
00:02:26,250 --> 00:02:29,360
ale pokud bychom zkombinovat některé
základy, které jsme již

45
00:02:29,360 --> 00:02:33,230
dozvěděli o ukazatele a struktur,
zejména s využitím dynamické paměti

46
00:02:33,230 --> 00:02:36,180
alokace s malloc, my
může dát tyto kousky dohromady

47
00:02:36,180 --> 00:02:40,960
Chcete-li vytvořit nová data structure-- A
jednotlivě spojeny seznam bychom mohli say--

48
00:02:40,960 --> 00:02:45,400
který nám umožňuje růst a
zmenšit soubor hodnot,

49
00:02:45,400 --> 00:02:48,800
a nebudeme mít žádnou zbytečný prostor.

50
00:02:48,800 --> 00:02:53,320
>> Takže znovu, nazýváme tuto myšlenku,
tento pojem, připojený seznam.

51
00:02:53,320 --> 00:02:56,320
Zejména v tomto videu jsme
mluví o jednotlivě Google seznamu

52
00:02:56,320 --> 00:02:59,185
a pak další videa si promluvíme
asi dvojnásobně spojové seznamy, které

53
00:02:59,185 --> 00:03:01,560
je jen variací na téma zde.

54
00:03:01,560 --> 00:03:05,200
Ale singly provázaný seznam
se skládá z uzlů,

55
00:03:05,200 --> 00:03:08,559
uzly být jen abstraktní term--
Je to prostě něco volám

56
00:03:08,559 --> 00:03:10,350
to je druh
struktura, v podstatě, já jsem?

57
00:03:10,350 --> 00:03:16,190
Jen tak to nazývat node-- a to
uzel má dva členy, nebo dvě pole.

58
00:03:16,190 --> 00:03:20,300
To má data, obvykle
integer, charakter float,

59
00:03:20,300 --> 00:03:23,790
nebo by mohl být nějaký jiný typ dat
že jste definovali pomocí typu def.

60
00:03:23,790 --> 00:03:29,290
A obsahuje ukazatel na
jiný uzel stejného typu.

61
00:03:29,290 --> 00:03:34,710
>> Takže máme dvě věci uvnitř
tento uzel, dat a ukazatel

62
00:03:34,710 --> 00:03:36,380
do jiného uzlu.

63
00:03:36,380 --> 00:03:39,370
A pokud začnete vizualizovat
to, můžete si o tom myslíte

64
00:03:39,370 --> 00:03:42,280
jako řetěz uzlů, které
jsou spojeny dohromady.

65
00:03:42,280 --> 00:03:45,070
Máme první uzel, to
obsahuje data, a ukazatel

66
00:03:45,070 --> 00:03:49,110
do druhého uzlu, který obsahuje
dat, a ukazatel na třetí uzlu.

67
00:03:49,110 --> 00:03:52,940
A tak to je důvod, proč jsme ho hovoru
spojový seznam, oni jsou navzájem propojeny.

68
00:03:52,940 --> 00:03:56,070
>> Co to zvláštní
Struktura uzel vypadat?

69
00:03:56,070 --> 00:04:01,120
No, pokud si vzpomínám z našeho videa na
definování vlastních typů, s typem def,

70
00:04:01,120 --> 00:04:05,400
můžeme definovat structure-- a
zadejte definovat strukturu, jako je tento.

71
00:04:05,400 --> 00:04:11,240
tyepdef struct sllist, a pak jsem
pomocí hodnoty slovo zde libovolně

72
00:04:11,240 --> 00:04:13,891
uvést jakýkoli typ dat, opravdu.

73
00:04:13,891 --> 00:04:16,890
Dalo by se přenést na celé číslo nebo plováku,
byste mohli mít, co chcete.

74
00:04:16,890 --> 00:04:19,389
To není omezen jen
celá čísla, nebo něco takového.

75
00:04:19,389 --> 00:04:22,790
Takže hodnota je pouze libovolná
datový typ, a pak ukazatel

76
00:04:22,790 --> 00:04:26,310
do jiného uzlu stejného typu.

77
00:04:26,310 --> 00:04:29,690
>> Nyní, tam je trochu háček
Zde se definuje strukturu

78
00:04:29,690 --> 00:04:33,030
když je to struktura vlastní referenční.

79
00:04:33,030 --> 00:04:35,340
Musím mít dočasnou
jméno pro mou strukturu.

80
00:04:35,340 --> 00:04:37,640
Na konci dne jsem
jasně to chcete nazývat

81
00:04:37,640 --> 00:04:43,030
SLL uzel, to je nakonec nový
jméno část mé definice typu,

82
00:04:43,030 --> 00:04:47,450
ale nemohu použít SLL uzel
ve středu tohoto.

83
00:04:47,450 --> 00:04:51,430
Důvodem je, nemám
vytvořil typ nazvaný SLL uzel

84
00:04:51,430 --> 00:04:55,200
až jsem narazila tento poslední bod zde.

85
00:04:55,200 --> 00:04:59,720
Až do tohoto bodu, musím mít
jiný způsob, jak se odkazovat na tento typ dat.

86
00:04:59,720 --> 00:05:02,440
>> A to je samo
referenční datový typ.

87
00:05:02,440 --> 00:05:06,314
Je to, to je typ dat
Struktura, která obsahuje údaje,

88
00:05:06,314 --> 00:05:08,480
a ukazatel na další
struktura stejného typu.

89
00:05:08,480 --> 00:05:11,750
Tak jsem třeba, aby bylo možné odkazovat na
Tento typ dat alespoň dočasně,

90
00:05:11,750 --> 00:05:14,910
tak dávat to dočasné
Jméno struct sllist

91
00:05:14,910 --> 00:05:18,540
mi umožňuje pak řekněte Chci
ukazatel do jiného struct sllist,

92
00:05:18,540 --> 00:05:24,690
struct sllist hvězda, a poté
poté, co jsem dokončil definici,

93
00:05:24,690 --> 00:05:27,220
I nyní může říkat tento typ uzel SLL.

94
00:05:27,220 --> 00:05:30,520
>> Takže to je důvod, proč jste vidět, že je to
dočasný název tady,

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

96
00:05:31,879 --> 00:05:33,920
Někdy můžete vidět
definice struktury,

97
00:05:33,920 --> 00:05:36,570
například, že nejsou
vlastní referenční, že

98
00:05:36,570 --> 00:05:39,390
nemají zde jméno specifikátor.

99
00:05:39,390 --> 00:05:43,040
To by jen říct typedef struct,
otevřít složená závorka a pak ji definovat.

100
00:05:43,040 --> 00:05:45,620
Ale pokud jste struct je self
Referenční, protože tento je,

101
00:05:45,620 --> 00:05:49,010
je třeba specifikovat
dočasný název typu.

102
00:05:49,010 --> 00:05:51,310
Ale nakonec, teď
že jsme udělali to,

103
00:05:51,310 --> 00:05:53,620
můžeme jen odkazovat na
tyto uzly, tyto jednotky,

104
00:05:53,620 --> 00:05:57,900
jako SLL uzly pro účely
zbytku tohoto videa.

105
00:05:57,900 --> 00:06:00,900
>> Dobře, takže víme, jak
vytvořit propojený seznamu uzlů.

106
00:06:00,900 --> 00:06:03,240
Víme, jak definovat
propojený seznam uzel.

107
00:06:03,240 --> 00:06:06,670
Teď, když jdeme na začátek
jejich použití shromažďovat informace,

108
00:06:06,670 --> 00:06:10,360
tam je několik operací jsme
musí pochopit a pracovat s.

109
00:06:10,360 --> 00:06:12,860
Potřebujeme vědět, jak vytvořit
propojený seznam ze vzduchu.

110
00:06:12,860 --> 00:06:14,901
Pokud není žádný seznam už,
chceme začít jeden.

111
00:06:14,901 --> 00:06:16,960
Proto musíme být schopni
vytvořit propojený seznam,

112
00:06:16,960 --> 00:06:19,130
musíme pravděpodobně hledat
v seznamu odkazů

113
00:06:19,130 --> 00:06:21,830
nalézt prvek, co hledáme.

114
00:06:21,830 --> 00:06:24,430
Musíme být schopni vložit
nové věci do seznamu,

115
00:06:24,430 --> 00:06:25,930
chceme náš seznam, aby mohl růst.

116
00:06:25,930 --> 00:06:28,638
A stejně, chceme být schopni
odstranit věci z našeho seznamu,

117
00:06:28,638 --> 00:06:30,250
chceme, aby náš seznam, aby bylo možné zmenšovat.

118
00:06:30,250 --> 00:06:32,160
A na konci našeho
programy, zejména

119
00:06:32,160 --> 00:06:34,550
Pokud si vzpomínáte, že jsme
dynamicky přidělování paměti

120
00:06:34,550 --> 00:06:38,337
vytvořit tyto seznamy typicky,
chceme osvobodit všechny, že paměť

121
00:06:38,337 --> 00:06:39,670
Když jsme hotovi s ní pracovat.

122
00:06:39,670 --> 00:06:44,627
A proto musíme být schopni Chcete-li odstranit
Celý spojový seznam v jednom selhání swoop.

123
00:06:44,627 --> 00:06:46,460
Takže pojďme projít
některé z těchto operací

124
00:06:46,460 --> 00:06:51,192
a jak je můžeme představit,
mluví v pseudokódu kódu specificky.

125
00:06:51,192 --> 00:06:53,150
Takže chceme vytvořit
spojový seznam, takže možná jsme

126
00:06:53,150 --> 00:06:56,480
chcete definovat funkci
s tímto prototypem.

127
00:06:56,480 --> 00:07:01,690
SLL uzel hvězda, tvořit, a já jsem kolem
v jednom argumentu, někteří libovolná data

128
00:07:01,690 --> 00:07:05,530
typ opět nějakého libovolného typu dat.

129
00:07:05,530 --> 00:07:10,482
Ale já jsem returning-- tuto funkci by měl
vrátit ke mně ukazatel, na singly

130
00:07:10,482 --> 00:07:11,190
spojový seznam uzel.

131
00:07:11,190 --> 00:07:14,050
Opět platí, že se snažíme o vytvoření
propojený seznam ze vzduchu,

132
00:07:14,050 --> 00:07:17,900
takže musím ukazatel
tento seznam, když jsem udělal.

133
00:07:17,900 --> 00:07:19,420
>> Takže jaké jsou kroky zde jedná?

134
00:07:19,420 --> 00:07:20,960
No, první věc, já jsem
chystá udělat, je dynamicky

135
00:07:20,960 --> 00:07:22,550
přidělit prostor pro nový uzel.

136
00:07:22,550 --> 00:07:26,689
Opět jsme vytvořit to z tenké
vzduch, takže musíme malloc prostor pro to.

137
00:07:26,689 --> 00:07:28,480
A samozřejmě okamžitě
poté, co jsme malloc,

138
00:07:28,480 --> 00:07:31,692
vždy zkontrolujte, zda, že naše
pointer-- jsme nedostali zpátky null.

139
00:07:31,692 --> 00:07:33,650
Vzhledem k tomu, když se budeme snažit a
podřízenost ukazatele null,

140
00:07:33,650 --> 00:07:36,190
budeme trpět
segfault a my nechceme, že.

141
00:07:36,190 --> 00:07:39,510
>> Pak jsme se chcete vyplnit v této oblasti,
chceme inicializovat hodnota pole

142
00:07:39,510 --> 00:07:41,690
a inicializovat další pole.

143
00:07:41,690 --> 00:07:45,450
A pak chceme to-- nakonec jako
prototyp funkce indicates-- chceme

144
00:07:45,450 --> 00:07:49,940
vrátit ukazatel na uzel SLL.

145
00:07:49,940 --> 00:07:51,710
Tak co, aby to vypadat vizuálně?

146
00:07:51,710 --> 00:07:55,230
No, v první budeme dynamicky
přidělit prostor pro nové SLL uzlu,

147
00:07:55,230 --> 00:07:58,320
takže jsme malloc-- to
vizuální reprezentace

148
00:07:58,320 --> 00:08:00,020
uzlu jsme právě vytvořili.

149
00:08:00,020 --> 00:08:02,757
A zkontrolujte, zda
to není null-- v tomto případě,

150
00:08:02,757 --> 00:08:04,840
obraz nebude mít
ukázal, jestli je to null,

151
00:08:04,840 --> 00:08:07,298
bychom dostatek paměti,
tak jsme dobré tam jít.

152
00:08:07,298 --> 00:08:10,200
Takže teď jsme ke kroku C,
inicializaci pole uzly hodnoty.

153
00:08:10,200 --> 00:08:12,280
No, na základě této funkci
volejte Já používám zde,

154
00:08:12,280 --> 00:08:16,700
vypadá to chci předat 6,
Takže budu 6 v hodnotovém poli.

155
00:08:16,700 --> 00:08:18,865
Nyní, inicializovat další pole.

156
00:08:18,865 --> 00:08:21,640
No, co mám dělat tam,
není nic, co dál, vpravo,

157
00:08:21,640 --> 00:08:23,600
to je jediná věc, v seznamu.

158
00:08:23,600 --> 00:08:27,206
Takže to, co je další věc na seznamu?

159
00:08:27,206 --> 00:08:29,660
>> Nemělo by ukazovat na nic, že ​​jo.

160
00:08:29,660 --> 00:08:33,600
Nic jiného tam, tak to, co je
pojetí víme, že je to nothing--

161
00:08:33,600 --> 00:08:35,638
ukazatele na nic?

162
00:08:35,638 --> 00:08:37,929
Mělo by to být snad chceme
dát ukazatele null tam,

163
00:08:37,929 --> 00:08:40,178
a já představují null
ukazatel jak jen červené pole,

164
00:08:40,178 --> 00:08:41,559
nemůžeme jít dál.

165
00:08:41,559 --> 00:08:44,430
Jak budeme o něco vidět později,
budeme mít nakonec i řetězy

166
00:08:44,430 --> 00:08:46,330
šipek připojení
tyto uzly dohromady,

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

168
00:08:48,480 --> 00:08:51,150
nemůžeme jít dál,
že je konec seznamu.

169
00:08:51,150 --> 00:08:53,960
>> A konečně, chceme jen, aby
vrátit ukazatel do tohoto uzlu.

170
00:08:53,960 --> 00:08:56,160
Takže budeme říkat nový,
a vrátí nový

171
00:08:56,160 --> 00:08:59,370
takže jej lze použít v
bez ohledu na funkci ji vytvořil.

172
00:08:59,370 --> 00:09:03,100
Takže tam jdeme, jsme vytvořili singly
spojový seznam uzel ze vzduchu,

173
00:09:03,100 --> 00:09:05,920
a teď máme seznam, můžeme pracovat.

174
00:09:05,920 --> 00:09:08,260
>> Nyní řekněme, že už
mají velký řetěz,

175
00:09:08,260 --> 00:09:09,800
a chceme najít něco, co v něm.

176
00:09:09,800 --> 00:09:12,716
A chceme funkci, která se děje
vrátit true nebo false, v závislosti

177
00:09:12,716 --> 00:09:15,840
na tom, zda hodnota existuje v tomto seznamu.

178
00:09:15,840 --> 00:09:18,160
Funkce prototyp, nebo
Prohlášení pro tuto funkci,

179
00:09:18,160 --> 00:09:23,320
může vypadat jako tohle-- bool najít, a
pak chceme předat dva argumenty.

180
00:09:23,320 --> 00:09:26,996
>> První z nich, je ukazatel na
První prvek v Google seznamu.

181
00:09:26,996 --> 00:09:29,620
To je ve skutečnosti něco, co budete
vždy chtějí sledovat,

182
00:09:29,620 --> 00:09:33,110
a ve skutečnosti by mohlo být něco, co
si dokonce dát do globální proměnné.

183
00:09:33,110 --> 00:09:35,360
Jakmile si vytvořit seznam,
vždycky, vždycky

184
00:09:35,360 --> 00:09:38,990
Chcete sledovat velmi
První prvek seznamu.

185
00:09:38,990 --> 00:09:43,690
Tímto způsobem se můžete obrátit na všechny ostatní
prvky podle právě v návaznosti na řetěz,

186
00:09:43,690 --> 00:09:47,300
aniž by museli držet ukazatele
neporušené na každý prvek.

187
00:09:47,300 --> 00:09:50,920
Jediné, co potřebujete mít přehled o první
jedno, pokud se všichni zřetězeno.

188
00:09:50,920 --> 00:09:52,460
>> A pak druhá věc
jsme kolem znovu

189
00:09:52,460 --> 00:09:54,376
je libovolně some--
bez ohledu na typ dat jsme

190
00:09:54,376 --> 00:09:59,640
hledá je uvnitř
doufejme, že jeden z uzlů v seznamu.

191
00:09:59,640 --> 00:10:00,980
Takže jaké jsou kroky?

192
00:10:00,980 --> 00:10:04,250
No, první věc, kterou děláme, je
vytvoříme příčný ukazatel

193
00:10:04,250 --> 00:10:06,015
ukazující na seznamech hlavy.

194
00:10:06,015 --> 00:10:08,890
No, proč to děláme, že jsme již
mají ukazatel na seznamech hlavě,

195
00:10:08,890 --> 00:10:10,974
proč ne my jen přesunout, že jedna kolem?

196
00:10:10,974 --> 00:10:13,140
No, jak jsem právě řekl,
je to opravdu důležité pro nás

197
00:10:13,140 --> 00:10:17,580
vždy sledovat z
Úplně první prvek v seznamu.

198
00:10:17,580 --> 00:10:21,270
A tak je to vlastně lepší
vytvořit duplikát, který,

199
00:10:21,270 --> 00:10:25,350
a použít se pohybovat, takže jsme nikdy
náhodně vzdálit, nebo vždy

200
00:10:25,350 --> 00:10:30,430
mají ukazatel v určitém okamžiku, který je
přímo na první prvek v seznamu.

201
00:10:30,430 --> 00:10:33,290
Takže je lepší vytvořit
Druhý, který používáme k pohybu.

202
00:10:33,290 --> 00:10:35,877
>> Pak jsme jen porovnat, zda
hodnota pole v tomto uzlu

203
00:10:35,877 --> 00:10:38,960
je to, co hledáme, a pokud je to
ne, jen jsme přesunout na další uzel.

204
00:10:38,960 --> 00:10:41,040
A my jsme pokračovat v tom, že
přes, a znovu, a znovu,

205
00:10:41,040 --> 00:10:44,811
dokud buď najít
prvek, nebo si hit

206
00:10:44,811 --> 00:10:47,310
null-- jsme došli na konec
seznamu a je to tam není.

207
00:10:47,310 --> 00:10:50,540
To by mělo snad neříká
aby vás jako právě lineární vyhledávání,

208
00:10:50,540 --> 00:10:54,430
jsme jen replikace ji
singly spojový seznam struktura

209
00:10:54,430 --> 00:10:56,280
namísto použití pole, jak to udělat.

210
00:10:56,280 --> 00:10:58,210
>> Tak tady je příklad
singly provázaný seznam.

211
00:10:58,210 --> 00:11:00,043
Ten se skládá z
pět uzlů, a my máme

212
00:11:00,043 --> 00:11:04,330
ukazatel na hlavě
Seznam, který se nazývá seznam.

213
00:11:04,330 --> 00:11:07,385
První věc, kterou chceme udělat, je
znovu vytvořit tuto traversal ukazatel.

214
00:11:07,385 --> 00:11:09,760
Takže teď máme dva ukazatele
tento bod na stejnou věc.

215
00:11:09,760 --> 00:11:15,025
>> Teď, všimněte si i zde, já ne
muset malloc žádný prostor pro trav.

216
00:11:15,025 --> 00:11:18,970
Neřekl jsem, že trav rovná malloc
něco, že uzel již existuje,

217
00:11:18,970 --> 00:11:21,160
že prostor v paměti již existuje.

218
00:11:21,160 --> 00:11:24,290
Takže všechno, co jsem vlastně dělá, je
vytvoření další ukazatel na něj.

219
00:11:24,290 --> 00:11:28,210
Nejsem mallocing další
prostor, stačí nyní dva ukazatele

220
00:11:28,210 --> 00:11:31,370
směřující ke stejné věci.

221
00:11:31,370 --> 00:11:33,710
>> Takže je 2 to, co jsem hledal?

222
00:11:33,710 --> 00:11:37,220
No, takže místo toho jsem si
budeme stěhovat do další.

223
00:11:37,220 --> 00:11:41,740
Takže v podstatě bych řekl,
trav se rovná trav další.

224
00:11:41,740 --> 00:11:43,630
Je 3 to, co jsem hledal, no.

225
00:11:43,630 --> 00:11:45,780
Tak jsem i nadále jít
díky, až nakonec

226
00:11:45,780 --> 00:11:48,690
dostat se až 6, což je to, co jsem hledal
pro založené na volání funkce

227
00:11:48,690 --> 00:11:51,600
I mají v horní části
tam, a tak jsem udělal.

228
00:11:51,600 --> 00:11:54,150
>> A teď, co když element, že jsem
hledáte, není v seznamu,

229
00:11:54,150 --> 00:11:55,510
je to ještě bude fungovat?

230
00:11:55,510 --> 00:11:57,120
No, zjistíte, že seznam
zde je nepatrně odlišný,

231
00:11:57,120 --> 00:11:59,410
a to je další věc, která je
důležité s provázané seznamy,

232
00:11:59,410 --> 00:12:01,780
nemusíte zachovat
je v libovolném pořadí.

233
00:12:01,780 --> 00:12:05,390
Můžete, pokud chcete, ale
možná jste již zaznamenali

234
00:12:05,390 --> 00:12:09,310
že nejsme sledování
jaký počet element jsme na.

235
00:12:09,310 --> 00:12:13,150
>> A to je druh z jednoho obchodu, který jsme
mají s Google seznamu veršů polí,

236
00:12:13,150 --> 00:12:15,300
Je to nemáme
náhodný přístup ještě.

237
00:12:15,300 --> 00:12:18,150
Nemůžeme jen tak říci, chci
jít na 0. prvku,

238
00:12:18,150 --> 00:12:21,410
nebo 6. náplní mé pole,
což se dá dělat v poli.

239
00:12:21,410 --> 00:12:25,080
Nemůžu říct, že chci jít do
0. prvek, nebo 6. element,

240
00:12:25,080 --> 00:12:30,360
nebo 25. prvek mého seznamu Google,
není index spojený s nimi.

241
00:12:30,360 --> 00:12:33,660
A tak to nezáleží
pokud bychom zachovat náš seznam v pořadí.

242
00:12:33,660 --> 00:12:36,080
Pokud chcete, aby vás
Určitě může, ale je tu

243
00:12:36,080 --> 00:12:38,567
žádný důvod, proč je třeba, aby
být zachovány v libovolném pořadí.

244
00:12:38,567 --> 00:12:40,400
Takže znovu, pojďme se pokusit
najít 6 v tomto seznamu.

245
00:12:40,400 --> 00:12:43,200
No, začneme u
začátek, nenajdeme 6,

246
00:12:43,200 --> 00:12:47,690
a pak pokračujeme nenalezení
6, dokud se nakonec dostat sem.

247
00:12:47,690 --> 00:12:52,790
Takže právě teď trav body do uzlu
obsahující 8, a šest není tam.

248
00:12:52,790 --> 00:12:55,250
>> Takže dalším krokem by bylo
přejdete na další ukazatel,

249
00:12:55,250 --> 00:12:57,440
tak říci, trav rovná trav další.

250
00:12:57,440 --> 00:13:00,750
No, trav další, indikováno
Tamní červená krabička, je null.

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

252
00:13:03,020 --> 00:13:06,120
můžeme konstatovat, že jsme dosáhli
konec seznamu Google,

253
00:13:06,120 --> 00:13:07,190
a 6 není tam.

254
00:13:07,190 --> 00:13:10,980
A to by se vrátil
false v tomto případě.

255
00:13:10,980 --> 00:13:14,540
>> OK, jak jsme se vložit nový
uzel do Google seznamu?

256
00:13:14,540 --> 00:13:17,310
Takže jsme byli schopni vytvořit
propojený seznam z ničeho,

257
00:13:17,310 --> 00:13:19,370
ale pravděpodobně chtít
vybudovat řetězce a nikoliv

258
00:13:19,370 --> 00:13:22,620
vytvořit spoustu odlišných seznamů.

259
00:13:22,620 --> 00:13:25,700
Chceme mít jeden seznam, který
má spoustu uzlů v něm,

260
00:13:25,700 --> 00:13:28,040
ne banda seznamů s jedním uzlem.

261
00:13:28,040 --> 00:13:31,260
Takže můžeme nejen udržet pomocí Vytvořit
Funkce jsme definovali dříve, teď jsme

262
00:13:31,260 --> 00:13:33,860
chtějí vložit do
Seznam, který již existuje.

263
00:13:33,860 --> 00:13:36,499
>> Takže tomto případě, jdeme
předat dva argumenty,

264
00:13:36,499 --> 00:13:39,290
ukazatel na hlavě, který
spojový seznam, který chceme přidat.

265
00:13:39,290 --> 00:13:40,910
Opět platí, že je důvod, proč je to tak
důležité, že jsme vždy

266
00:13:40,910 --> 00:13:43,400
sledovat to, protože
je to jediný způsob, jak skutečně

267
00:13:43,400 --> 00:13:46,690
muset odkazovat se na celý seznam je
jen tím, že ukazatel na první prvek.

268
00:13:46,690 --> 00:13:49,360
Takže chceme předat v
ukazatel na tento první prvek,

269
00:13:49,360 --> 00:13:52,226
a bez ohledu na hodnotu, kterou
chcete přidat do seznamu.

270
00:13:52,226 --> 00:13:54,600
A nakonec tato funkce
bude vrátí ukazatel

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

272
00:13:57,980 --> 00:13:59,700
>> Jaké jsou kroky zde jedná?

273
00:13:59,700 --> 00:14:02,249
No, stejně jako u vytvářet,
musíme dynamicky přidělovat

274
00:14:02,249 --> 00:14:05,540
prostor pro nový uzel, a zkontrolujte,
jisti, že nemáme dostatek paměti, znovu,

275
00:14:05,540 --> 00:14:07,150
proto, že jsme pomocí malloc.

276
00:14:07,150 --> 00:14:09,080
Pak chceme naplnit
a vložte uzlu,

277
00:14:09,080 --> 00:14:12,730
tak dal číslo, bez ohledu
val je, do uzlu.

278
00:14:12,730 --> 00:14:17,310
Chceme vložit uzel na
začátek Google seznamu.

279
00:14:17,310 --> 00:14:19,619
>> Tam je důvod, proč jsem
to chceš udělat, a to

280
00:14:19,619 --> 00:14:21,910
může být stojí za sekundu
pozastavit video zde,

281
00:14:21,910 --> 00:14:25,860
a přemýšlet o tom, proč bych chtěl
vložit na začátku propojenou

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

283
00:14:26,589 --> 00:14:28,630
Opět jsem se zmínil dříve,
že to opravdu není

284
00:14:28,630 --> 00:14:33,020
jedno, jestli se nám to uchovat v jakémkoli
pořádek, takže možná je to stopa.

285
00:14:33,020 --> 00:14:36,040
A jsi viděl, co by se stalo, kdybychom
Chtěl to-- nebo jen na vteřinu

286
00:14:36,040 --> 00:14:37,360
Před když jsme jeli
pomocí vyhledávání vám

287
00:14:37,360 --> 00:14:39,235
mohl vidět, co by mohlo
se stalo, kdybychom se snažili

288
00:14:39,235 --> 00:14:41,330
pro vložení na konec seznamu.

289
00:14:41,330 --> 00:14:44,750
Protože my nemají
ukazatel na konec seznamu.

290
00:14:44,750 --> 00:14:47,490
>> Takže důvod, proč bych chtěl
pro vložení na začátku,

291
00:14:47,490 --> 00:14:49,380
je proto, že jsem to udělat okamžitě.

292
00:14:49,380 --> 00:14:52,730
Mám ukazatel na začátku, a
uvidíme to v vizuální ve vteřině.

293
00:14:52,730 --> 00:14:55,605
Ale pokud chci vložit na konec,
Musím začít od začátku,

294
00:14:55,605 --> 00:14:58,760
přejít celou cestu až do
konec, a poté jej přidají.

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

296
00:15:01,420 --> 00:15:04,140
stala by se o n
provoz, se vrací

297
00:15:04,140 --> 00:15:06,720
k naší diskusi o
výpočetní složitost.

298
00:15:06,720 --> 00:15:10,140
To by se stát o n provozu, kde
i seznam dostal větší a větší,

299
00:15:10,140 --> 00:15:13,310
a větší, bude to čím dál
obtížnější křižovat něco

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 opravdu snadné
připínáček něco na začátku,

302
00:15:17,410 --> 00:15:19,060
jste vždy na začátku.

303
00:15:19,060 --> 00:15:21,620
>> A uvidíme opět vizuální tohoto.

304
00:15:21,620 --> 00:15:24,100
A pak jednou jsme skončili, jakmile
jsme vložil nový uzel,

305
00:15:24,100 --> 00:15:26,880
Chceme se vrátit náš ukazatel
nový šéf propojeného seznamu, který

306
00:15:26,880 --> 00:15:29,213
od té doby jsme vkládání u
začátek, bude skutečně

307
00:15:29,213 --> 00:15:31,060
ukazatel na uzlu jsme právě vytvořené.

308
00:15:31,060 --> 00:15:33,280
Pojďme si to představit,
protože si myslím, že to pomůže.

309
00:15:33,280 --> 00:15:36,661
>> Tak tady je náš seznam, skládá se z
čtyři prvky, uzel obsahující 15,

310
00:15:36,661 --> 00:15:38,410
což ukazuje na uzel
obsahující 9, který

311
00:15:38,410 --> 00:15:41,370
poukazuje na uzlu, který obsahuje 13,
což ukazuje na uzel obsahující

312
00:15:41,370 --> 00:15:44,840
10, který má null
ukazatel pro svou další ukazatel

313
00:15:44,840 --> 00:15:47,010
tak to je konec seznamu.

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

315
00:15:50,200 --> 00:15:52,720
na začátku tohoto
seznam, co budeme dělat?

316
00:15:52,720 --> 00:15:58,770
No, v první jsme malloc prostor pro
uzel, a pak jsme dali 12 tam.

317
00:15:58,770 --> 00:16:02,211
>> Takže teď jsme se dosáhne
bod rozhodnutí, že jo?

318
00:16:02,211 --> 00:16:03,960
Máme pár
ukazatele, které jsme mohli

319
00:16:03,960 --> 00:16:06,770
pohyb, který bychom měli přesunout jako první?

320
00:16:06,770 --> 00:16:09,250
Měli bychom udělat 12 přejděte na
Nový šéf list--

321
00:16:09,250 --> 00:16:13,020
nebo promiňte, bychom měli 12
poukazují na staré čele seznamu?

322
00:16:13,020 --> 00:16:15,319
Nebo bychom měli říci, že
Seznam nyní začíná na 12.

323
00:16:15,319 --> 00:16:17,110
Tam je rozdíl
tam, a my se podíváme

324
00:16:17,110 --> 00:16:19,870
na to, co se děje s oběma v druhém.

325
00:16:19,870 --> 00:16:23,350
>> Ale toto vede k
skvělé téma pro postranním panelu

326
00:16:23,350 --> 00:16:26,280
což je, že jeden z
nejkomplikovanější věci s spojových seznamů

327
00:16:26,280 --> 00:16:30,980
je uspořádat ukazatele
ve správném pořadí.

328
00:16:30,980 --> 00:16:34,520
Pokud se pohybovat věcmi mimo provoz,
můžete skončit nechtěně

329
00:16:34,520 --> 00:16:36,050
orphaning zbytek seznamu.

330
00:16:36,050 --> 00:16:37,300
A tady je příklad toho.

331
00:16:37,300 --> 00:16:40,540
Tak pojďme s myšlenkou of--
No, my jsme právě vytvořili 12.

332
00:16:40,540 --> 00:16:43,180
Víme, že 12 bude
nový šéf seznamu,

333
00:16:43,180 --> 00:16:47,660
a tak proč ne my jen přesunout
ukazatel seznam tam bodu.

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

335
00:16:49,070 --> 00:16:51,560
Takže nyní kde dělá 12 další bod?

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

337
00:16:54,580 --> 00:16:57,250
jako lidé, je to opravdu jasné, k nám.

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

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

340
00:17:02,720 --> 00:17:05,869
>> Jsme ztratili schopnost se odkazovat na 15.

341
00:17:05,869 --> 00:17:11,460
Nemůžeme říci, nový šipku vedle rovná
něco, nic tam není.

342
00:17:11,460 --> 00:17:13,510
Ve skutečnosti jsme se osiřelý
zbytek seznamu

343
00:17:13,510 --> 00:17:16,465
Tím máme
náhodně zlomený řetěz.

344
00:17:16,465 --> 00:17:18,089
A my rozhodně nechceme dělat.

345
00:17:18,089 --> 00:17:20,000
>> Takže pojďme zpět a zkuste to znovu.

346
00:17:20,000 --> 00:17:24,060
Možná, že správná věc
je stanovit další ukazatele 12 je

347
00:17:24,060 --> 00:17:28,290
na staré čele seznamu první,
pak se můžeme přesunout na seznam u konce.

348
00:17:28,290 --> 00:17:30,420
A ve skutečnosti, že je
správné pořadí, že my

349
00:17:30,420 --> 00:17:32,836
je třeba dodržovat, když jsme
pracuje s jednotlivě propojeného seznamu.

350
00:17:32,836 --> 00:17:36,460
Vždy chceme připojit
nový prvek do seznamu,

351
00:17:36,460 --> 00:17:41,010
Než jsme se tento druh
důležitým krokem změny

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

353
00:17:43,360 --> 00:17:46,740
Opět platí, že je to tak zásadní věc,
Nechceme ztratit přehled o tom.

354
00:17:46,740 --> 00:17:49,310
>> Proto chceme, aby se ujistil, že
vše se připoutal spolu,

355
00:17:49,310 --> 00:17:52,040
Než jsme se přesunout tento ukazatel.

356
00:17:52,040 --> 00:17:55,300
A tak by to bylo správné pořadí,
který je pro připojení 12 do seznamu,

357
00:17:55,300 --> 00:17:57,630
pak říkají, že seznam začíná 12.

358
00:17:57,630 --> 00:18:00,860
Pokud se nám řekl, že seznam začíná na 12 a
pak se pokusil připojení 12 do seznamu,

359
00:18:00,860 --> 00:18:02,193
jsme již viděli, co se stane.

360
00:18:02,193 --> 00:18:04,920
Ztrácíme seznamu omylem.

361
00:18:04,920 --> 00:18:06,740
>> OK, takže ještě jedna věc, o čem mluvit.

362
00:18:06,740 --> 00:18:09,750
Co když chceme zbavit
celý spojený seznam najednou?

363
00:18:09,750 --> 00:18:11,750
Opět jsme mallocing
všechno tento prostor, a tak jsme

364
00:18:11,750 --> 00:18:13,351
třeba jej uvolnit, když budeme hotovi.

365
00:18:13,351 --> 00:18:15,350
Takže nyní chceme smazat
celý provázaný seznam.

366
00:18:15,350 --> 00:18:16,850
No, co chceme dělat?

367
00:18:16,850 --> 00:18:20,460
>> Jestliže jsme dosáhli ukazatele null, my
chtějí zastavit, jinak, stačí smazat

368
00:18:20,460 --> 00:18:23,420
zbytek seznamu a pak mě osvobodil.

369
00:18:23,420 --> 00:18:28,890
Odstraňte zbytek seznamu,
a pak uvolnit aktuální uzel.

370
00:18:28,890 --> 00:18:32,850
Co to zní jako,
Jakou technikou máme povídali

371
00:18:32,850 --> 00:18:35,440
o dříve Zní to jako?

372
00:18:35,440 --> 00:18:39,560
Odstranit všichni ostatní, pak
vrátit a odstranit mě.

373
00:18:39,560 --> 00:18:42,380
>> To je rekurze, jsme učinil
problém o něco menší,

374
00:18:42,380 --> 00:18:46,910
říkáme smazat každého
jiného, ​​pak můžete mě odstranit.

375
00:18:46,910 --> 00:18:50,940
A dále po silnici, která uzel
řekne, odstranit všechny ostatní.

376
00:18:50,940 --> 00:18:53,940
Ale nakonec se dostaneme k
místo, kde je seznam null,

377
00:18:53,940 --> 00:18:55,310
a to je naše základna případ.

378
00:18:55,310 --> 00:18:57,010
>> Takže pojďme se podívat na to,
a jak to může fungovat.

379
00:18:57,010 --> 00:18:59,759
Tak tady je náš seznam, je to stejné
Seznam právě jsme mluvili 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 hodně textu tady, ale
Doufejme, že vizualizace pomůže.

382
00:19:04,200 --> 00:19:08,557
>> Tak jsme have-- a také jsem vytáhl
up našeho stack frames ilustrace

383
00:19:08,557 --> 00:19:10,890
z našeho videa na volání komíny,
a doufejme, že to všechno

384
00:19:10,890 --> 00:19:13,260
společně vám ukáže, co se děje.

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

386
00:19:14,510 --> 00:19:17,830
Pokud dojdeme null
ukazatel, zastavit, jinak,

387
00:19:17,830 --> 00:19:21,320
odstraní zbytek seznamu,
pak uvolnění aktuální uzel.

388
00:19:21,320 --> 00:19:25,700
Takže teď, list--
ukazatel, že jsme

389
00:19:25,700 --> 00:19:28,410
předáním zničit body do 12 let.

390
00:19:28,410 --> 00:19:33,340
12 není ukazatele null, takže jsme
chystá odstranit zbytek seznamu.

391
00:19:33,340 --> 00:19:35,450
>> Co vymazání
Zbytek z nás zapojit?

392
00:19:35,450 --> 00:19:37,950
No, to znamená, že dodávání
zavolat zničit, řekl

393
00:19:37,950 --> 00:19:42,060
že 15 let je na začátku
Zbytek seznamu chceme zničit.

394
00:19:42,060 --> 00:19:47,480
A tak se výzva ke zničení
12 je v jistém smyslu v pořadí.

395
00:19:47,480 --> 00:19:52,690
Je to zmrazené tam a čekal,
zavolat zničit 15, dokončit svou práci.

396
00:19:52,690 --> 00:19:56,280
>> No, 15 není nulový ukazatel, a
takže to bude říkat, v pořádku,

397
00:19:56,280 --> 00:19:58,450
dobře, odstraňte zbytek seznamu.

398
00:19:58,450 --> 00:20:00,760
Zbytek seznamu začíná
9, a tak jsme si jen

399
00:20:00,760 --> 00:20:04,514
počkejte, až se odstranit vše, co
věci, pak se vrátit a odstranit mě.

400
00:20:04,514 --> 00:20:06,680
No 9 to bude říkat, no,
Nejsem nulový ukazatel,

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

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

403
00:20:11,805 --> 00:20:15,550
13 říká, já nejsem nulový ukazatel,
totéž, to projde kolem babku.

404
00:20:15,550 --> 00:20:17,930
10 není ukazatele null, 10
obsahuje ukazatele null,

405
00:20:17,930 --> 00:20:20,200
ale 10 není sám
null ukazatel právě teď,

406
00:20:20,200 --> 00:20:22,470
a tak předá dolar příliš.

407
00:20:22,470 --> 00:20:25,560
>> A nyní seznam body tam, ho
Opravdu by chtěl poukázat na some--

408
00:20:25,560 --> 00:20:28,710
kdybych měla více prostoru v obraze,
že by chtěl poukázat na nějaký náhodný vesmíru

409
00:20:28,710 --> 00:20:29,960
že nevíme, co to je.

410
00:20:29,960 --> 00:20:34,680
To je nulový ukazatel ačkoli, seznam
je doslova nyní nastaven, že je to hodnota null.

411
00:20:34,680 --> 00:20:36,820
Je to ukázal hned v té červeného pole.

412
00:20:36,820 --> 00:20:39,960
Dosáhli jsme ukazatele null, takže
můžeme zastavit, a my jsme udělali.

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

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

415
00:20:47,017 --> 00:20:48,600
Jestliže jsme dosáhli nulový ukazatel, zastavit.

416
00:20:48,600 --> 00:20:51,290
Nechceme dělat nic, my
nemůže uvolnit ukazatele null,

417
00:20:51,290 --> 00:20:55,070
jsme neměli malloc jakýkoli
prostor, a tak jsme hotovi.

418
00:20:55,070 --> 00:20:57,590
Takže funkce rámu
je zničena, a my jsme

419
00:20:57,590 --> 00:21:00,930
resume-- jsme tam, kde jsme opustili
off s příští nejvyšší, což

420
00:21:00,930 --> 00:21:02,807
Je to tmavě modrý rámeček zde.

421
00:21:02,807 --> 00:21:04,390
Tak jsme vyzvednout přesně tam, kde jsme skončili.

422
00:21:04,390 --> 00:21:06,598
Vypouští jsme zbytku
Seznam již, takže teď jsme

423
00:21:06,598 --> 00:21:08,000
chystá uvolnit aktuální uzly.

424
00:21:08,000 --> 00:21:12,920
Takže teď se můžeme osvobodit tento uzel, a teď
jsme došli na konec funkce.

425
00:21:12,920 --> 00:21:16,810
A tak, že funkce rám je zničena,
a my vyzvednout na světle modrou.

426
00:21:16,810 --> 00:21:20,650
>> Tak to says-- už jsem done--
vypustit zbytek seznamu, tak

427
00:21:20,650 --> 00:21:23,140
osvobodí aktuální uzel.

428
00:21:23,140 --> 00:21:26,520
A teď je žlutý rámeček
zpátky na vrcholu zásobníku.

429
00:21:26,520 --> 00:21:29,655
A tak jak vidíte, jsme nyní
ničí seznam zprava doleva.

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

431
00:21:33,710 --> 00:21:37,280
>> Co by se stalo, i když,
pokud jsme dělali věci špatně?

432
00:21:37,280 --> 00:21:39,410
Stejně jako když jsme se pokoušeli
přidat prvek.

433
00:21:39,410 --> 00:21:41,909
Pokud bychom zpackal řetěz, pokud
jsme se nepřipojili ukazatele

434
00:21:41,909 --> 00:21:44,690
ve správném pořadí, kdybychom
jen osvobodil první prvek,

435
00:21:44,690 --> 00:21:47,420
pokud jsme právě propuštěny
vedoucí seznamu, teď jsme

436
00:21:47,420 --> 00:21:49,642
nemají žádný způsob, jak se odkazovat na
zbytek seznamu.

437
00:21:49,642 --> 00:21:51,350
A tak budeme mít
osiřelé všechno,

438
00:21:51,350 --> 00:21:53,880
měli bychom to, co je
volal k nevracení paměti.

439
00:21:53,880 --> 00:21:56,800
Pokud si vzpomínáte z našeho videa
dynamické přidělování paměti,

440
00:21:56,800 --> 00:21:58,650
to není moc dobrá věc.

441
00:21:58,650 --> 00:22:00,810
>> Tak jak jsem řekl, že
jsou několik operací

442
00:22:00,810 --> 00:22:04,010
že musíme použít k práci
s spojový seznam efektivně.

443
00:22:04,010 --> 00:22:08,430
A možná jste si všimli jsem vynechat jeden,
smazání jednoho prvku z propojeného

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

445
00:22:09,064 --> 00:22:10,980
Důvod, proč jsem to udělal
Je to vlastně druh

446
00:22:10,980 --> 00:22:14,360
ošidné přemýšlet o tom, jak odstranit
jediný prvek z singly

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

448
00:22:15,600 --> 00:22:19,950
Musíme být schopni přeskočit
něco v seznamu, který

449
00:22:19,950 --> 00:22:22,975
znamená, že jsme si na point-- my
chcete smazat tuto node--

450
00:22:22,975 --> 00:22:25,350
ale aby se to dělá tak, abychom
neztratí žádné informace,

451
00:22:25,350 --> 00:22:30,530
musíme spojit to
uzel sem, sem.

452
00:22:30,530 --> 00:22:33,390
>> Tak jsem to udělal špatně nejspíš
z vizuálního hlediska.

453
00:22:33,390 --> 00:22:36,830
Takže jsme na začátku našeho
seznam, jsme vyřizováno,

454
00:22:36,830 --> 00:22:40,510
chceme smazat tento uzel.

455
00:22:40,510 --> 00:22:43,440
Pokud bychom prostě odstranit,
jsme zlomený řetěz.

456
00:22:43,440 --> 00:22:45,950
Tento uzel tady
se vztahuje na všechno ostatní,

457
00:22:45,950 --> 00:22:48,260
že obsahuje řetězec od tady na ven.

458
00:22:48,260 --> 00:22:51,190
>> Takže to, co musíme udělat skutečně
poté, co se dostaneme do tohoto bodu,

459
00:22:51,190 --> 00:22:56,670
je musíme udělat krok zpět jeden, a
připojení tohoto uzlu do tohoto uzlu,

460
00:22:56,670 --> 00:22:58,590
takže se pak můžeme smazat
ten uprostřed.

461
00:22:58,590 --> 00:23:02,120
Ale jednotlivě propojené seznamy ne
poskytují nám způsob, jak jít zpět.

462
00:23:02,120 --> 00:23:05,160
Takže potřebujeme buď udržet
dva ukazatele, a přesunout je

463
00:23:05,160 --> 00:23:09,527
druh off kroku, jeden za
ostatní, jak jsme jít, nebo dostat do bodu,

464
00:23:09,527 --> 00:23:11,110
a pak poslat další ukazatel přes.

465
00:23:11,110 --> 00:23:13,150
A jak můžete vidět, to
může dostat trochu chaotický.

466
00:23:13,150 --> 00:23:15,360
Naštěstí, máme
Další způsob, jak vyřešit to,

467
00:23:15,360 --> 00:23:17,810
když mluvíme o dvojnásobně spojových seznamů.

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

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