1
00:00:07,260 --> 00:00:10,050
[Powered by Google Translate] V programovaní, často potrebujeme reprezentovať zoznamy hodnôt,

2
00:00:10,050 --> 00:00:12,840
napríklad názvy študentov v sekcii

3
00:00:12,840 --> 00:00:15,100
alebo ich skóre na poslednej kvízu.

4
00:00:15,100 --> 00:00:17,430
>> V jazyku C, vyhlásila polia môžu byť použité

5
00:00:17,430 --> 00:00:19,160
uložiť zoznamy.

6
00:00:19,160 --> 00:00:21,200
Je to jednoduché vymenovať prvky zoznamu

7
00:00:21,200 --> 00:00:23,390
uložené v poli, a ak budete potrebovať pre prístup k

8
00:00:23,390 --> 00:00:25,050
alebo upraviť Ith prvok zoznamu

9
00:00:25,050 --> 00:00:27,570
pre nejaký svojvoľný index I,

10
00:00:27,570 --> 00:00:29,910
ktorý môže byť vykonaný v konštantnom čase,

11
00:00:29,910 --> 00:00:31,660
ale pole majú nevýhody.

12
00:00:31,660 --> 00:00:33,850
>> Keď sme ich deklarovať, že sme povinní povedať

13
00:00:33,850 --> 00:00:35,900
up front, aké veľké sú,

14
00:00:35,900 --> 00:00:38,160
že je, koľko prvkov, ktoré môžu uložiť

15
00:00:38,160 --> 00:00:40,780
a ako veľké tieto prvky sú, ktorá je určená ich typu.

16
00:00:40,780 --> 00:00:45,450
Napríklad, int ARR (10)

17
00:00:45,450 --> 00:00:48,220
možno uložiť 10 položiek

18
00:00:48,220 --> 00:00:50,200
že sú o veľkosti typu int.

19
00:00:50,200 --> 00:00:52,590
>> Nemôžeme zmeniť celý rad jeho veľkosť po uverejnení.

20
00:00:52,590 --> 00:00:55,290
Musíme vytvoriť nové pole, ak chceme uložiť viac prvkov.

21
00:00:55,290 --> 00:00:57,410
Dôvodom toto obmedzenie existuje, je, že naša

22
00:00:57,410 --> 00:00:59,040
Program ukladá celý rad

23
00:00:59,040 --> 00:01:02,310
ako súvislý kus pamäte.

24
00:01:02,310 --> 00:01:04,500
Povedzme to je vyrovnávacia pamäť, kde sa uloží v našom poli.

25
00:01:04,500 --> 00:01:06,910
Tam by mohlo byť iné premenné

26
00:01:06,910 --> 00:01:08,310
Nachádza sa hneď vedľa poľa

27
00:01:08,310 --> 00:01:10,060
v pamäti, takže nemôžeme

28
00:01:10,060 --> 00:01:12,060
len aby polia väčšie.

29
00:01:12,060 --> 00:01:15,700
>> Niekedy sme chceli obchodovať Array je rýchly prístup k dátam rýchlosťou

30
00:01:15,700 --> 00:01:17,650
o trochu viac flexibility.

31
00:01:17,650 --> 00:01:20,380
Zadajte spájať zoznam, ďalšie základné údaje štruktúra

32
00:01:20,380 --> 00:01:22,360
nemusíte byť oboznámení s

33
00:01:22,360 --> 00:01:24,200
Na vysokej úrovni,

34
00:01:24,200 --> 00:01:26,840
spájať zoznam ukladá dáta v poradí uzlov

35
00:01:26,840 --> 00:01:29,280
, Ktoré sú vzájomne prepojené s odkazmi,

36
00:01:29,280 --> 00:01:31,760
Odtiaľ názov "spájať zoznam."

37
00:01:31,760 --> 00:01:33,840
Ako uvidíme, tento rozdiel v dizajne

38
00:01:33,840 --> 00:01:35,500
vedie k rôznym výhodám a nevýhodám

39
00:01:35,500 --> 00:01:37,000
ako pole.

40
00:01:37,000 --> 00:01:39,840
>> Tu je nejaký kód C pre veľmi jednoduché prepojeného zoznamu celých čísel.

41
00:01:39,840 --> 00:01:42,190
Môžete vidieť, že sme zástupcovia každý uzol

42
00:01:42,190 --> 00:01:45,520
v zozname ako struct, ktorý obsahuje 2 veci,

43
00:01:45,520 --> 00:01:47,280
číslo uložiť tzv "val"

44
00:01:47,280 --> 00:01:50,460
a odkaz na ďalšie uzol v zozname

45
00:01:50,460 --> 00:01:52,990
ktoré predstavujú ako ukazovateľ s názvom "Ďalší."

46
00:01:54,120 --> 00:01:56,780
Týmto spôsobom, možno sledovať celý zoznam

47
00:01:56,780 --> 00:01:58,790
iba s jedným ukazovateľ na uzol 1st,

48
00:01:58,790 --> 00:02:01,270
a potom môžeme sledovať ďalšie ukazovatele

49
00:02:01,270 --> 00:02:03,130
na druhej uzla,

50
00:02:03,130 --> 00:02:05,280
na 3. uzla,

51
00:02:05,280 --> 00:02:07,000
na 4. uzla,

52
00:02:07,000 --> 00:02:09,889
a tak ďalej, až kým sa na koniec zoznamu.

53
00:02:10,520 --> 00:02:12,210
>> Tie by mohli byť schopní vidieť 1 výhodu to má

54
00:02:12,210 --> 00:02:14,490
cez statické pole štruktúry - s prepojeného zoznamu,

55
00:02:14,490 --> 00:02:16,450
nepotrebujeme veľký kus pamäte dohromady.

56
00:02:17,400 --> 00:02:20,530
1. uzol zoznamu by mohol žiť na tomto mieste v pamäti,

57
00:02:20,530 --> 00:02:23,160
a 2. uzol by mohol byť po celú cestu sem.

58
00:02:23,160 --> 00:02:25,780
Môžeme dostať do všetkých uzlov bez ohľadu na to, kde v pamäti sú,

59
00:02:25,780 --> 00:02:28,890
pretože začína v uzle 1st, každý uzol budúci ukazovateľ

60
00:02:28,890 --> 00:02:31,700
nám hovorí presne, kam ísť ďalej.

61
00:02:31,700 --> 00:02:33,670
>> Navyše, nemáme hovoriť dopredu

62
00:02:33,670 --> 00:02:36,740
aký veľký spájať zoznam bude rovnakým spôsobom ako my so statickými poli,

63
00:02:36,740 --> 00:02:39,060
pretože môžeme držať pridanie uzlov do zoznamu

64
00:02:39,060 --> 00:02:42,600
ako dlho ako tam je priestor niekde v pamäti pre nové uzly.

65
00:02:42,600 --> 00:02:45,370
Preto, prepojené zoznamy ľahko zmeniť veľkosť dynamicky.

66
00:02:45,370 --> 00:02:47,950
Povedz, neskôr v programe musíme pridať ďalšie uzly

67
00:02:47,950 --> 00:02:49,350
do nášho zoznamu.

68
00:02:49,350 --> 00:02:51,480
Ak chcete vložiť nový uzol do nášho zoznamu za behu,

69
00:02:51,480 --> 00:02:53,740
všetko, čo musíme urobiť, je alokovať pamäť pre tento uzol,

70
00:02:53,740 --> 00:02:55,630
PLOP v dátovej hodnoty,

71
00:02:55,630 --> 00:02:59,070
a potom na miesto, kde chceme úpravou vhodné ukazovatele.

72
00:02:59,070 --> 00:03:02,310
>> Napríklad, ak chceme umiestniť uzol medzi

73
00:03:02,310 --> 00:03:04,020
2. a 3. uzly zoznamu,

74
00:03:04,020 --> 00:03:06,800
 by sme nemali presunúť 2. alebo 3. uzly vôbec.

75
00:03:06,800 --> 00:03:09,190
Povedzme, že sme vložením túto červenú uzol.

76
00:03:09,190 --> 00:03:12,890
Všetko budeme musieť urobiť, je nastaviť nový uzol je ďalší ukazovateľ

77
00:03:12,890 --> 00:03:14,870
poukázať na 3. uzla

78
00:03:14,870 --> 00:03:18,580
a potom prepojiť druhej uzla je ďalší ukazovateľ

79
00:03:18,580 --> 00:03:20,980
upozorniť na náš nový uzol.

80
00:03:22,340 --> 00:03:24,370
Takže, môžeme meniť veľkosť svojej zoznamy za behu

81
00:03:24,370 --> 00:03:26,090
pretože náš počítač nespolieha na indexovanie,

82
00:03:26,090 --> 00:03:28,990
ale skôr na prepojenie s ukazovateľmi ich uloženia.

83
00:03:29,120 --> 00:03:31,600
>> Avšak, nevýhodou spojené zoznamy

84
00:03:31,600 --> 00:03:33,370
je skutočnosť, že na rozdiel od statické pole,

85
00:03:33,370 --> 00:03:36,690
Počítač nemôže len tak skočiť do stredu zoznamu.

86
00:03:38,040 --> 00:03:40,780
Vzhľadom k tomu, že počítač má navštíviť každý uzol v prepojenom zozname

87
00:03:40,780 --> 00:03:42,330
sa dostať na ďalšie,

88
00:03:42,330 --> 00:03:44,770
to bude trvať dlhšie nájsť určitý uzol

89
00:03:44,770 --> 00:03:46,400
, Ako by sa v poli.

90
00:03:46,400 --> 00:03:48,660
Prejsť celý zoznam trvá dlho úmerná

91
00:03:48,660 --> 00:03:50,580
k dĺžke zoznamu,

92
00:03:50,580 --> 00:03:54,630
alebo O (n) v asymptotickej notáciu.

93
00:03:54,630 --> 00:03:56,510
V priemere, dosiahnutie ľubovoľného uzla

94
00:03:56,510 --> 00:03:58,800
berie tiež časovo proporcionálne k n.

95
00:03:58,800 --> 00:04:00,700
>> Teraz, poďme vlastne napísať nejaký kód

96
00:04:00,700 --> 00:04:02,000
, Ktorý pracuje s lineárnymi zoznamy.

97
00:04:02,000 --> 00:04:04,220
Povedzme, že chceme prepojeného zoznamu celých čísel.

98
00:04:04,220 --> 00:04:06,140
Môžeme reprezentovať uzol v našom zozname znova

99
00:04:06,140 --> 00:04:08,340
ako struct s 2 polí,

100
00:04:08,340 --> 00:04:10,750
celočíselná hodnota tzv "val"

101
00:04:10,750 --> 00:04:13,490
a ďalšie ukazovateľ na ďalší uzol zoznamu.

102
00:04:13,490 --> 00:04:15,660
No, vyzerá celkom jednoduché.

103
00:04:15,660 --> 00:04:17,220
>> Povedzme, že chcete napísať funkciu

104
00:04:17,220 --> 00:04:19,329
ktorý prekročí zoznamu a vytlačí

105
00:04:19,329 --> 00:04:22,150
Hodnota uložená v poslednej uzol zoznamu.

106
00:04:22,150 --> 00:04:24,850
No, to znamená, že budeme musieť prejsť všetky uzly v zozname

107
00:04:24,850 --> 00:04:27,310
nájsť ten posledný, ale pretože nie sme pridanie

108
00:04:27,310 --> 00:04:29,250
alebo čokoľvek zmazali, nechceme meniť

109
00:04:29,250 --> 00:04:32,210
vnútorná štruktúra ďalších ukazovateľov v zozname.

110
00:04:32,210 --> 00:04:34,790
>> Takže, budeme potrebovať ukazovateľ špeciálne pre priechod

111
00:04:34,790 --> 00:04:36,940
ktoré budeme nazývať "prolézací modul."

112
00:04:36,940 --> 00:04:38,870
To bude prechádzať cez všetky prvky zoznamu

113
00:04:38,870 --> 00:04:41,190
podľa pokynov reťazca ďalších ukazovateľov.

114
00:04:41,190 --> 00:04:43,750
Všetko máme uložené, je ukazovateľ na uzol 1st,

115
00:04:43,750 --> 00:04:45,730
alebo "hlava" zo zoznamu.

116
00:04:45,730 --> 00:04:47,370
Head poukazuje na 1. uzla.

117
00:04:47,370 --> 00:04:49,120
Je to typu pointer-to-uzla.

118
00:04:49,120 --> 00:04:51,280
>> Ak chcete získať aktuálne prvý uzol v zozname,

119
00:04:51,280 --> 00:04:53,250
musíme dereferencia tento ukazovateľ,

120
00:04:53,250 --> 00:04:55,100
ale pred tým, než môže dereferencia to, musíme skontrolovať

121
00:04:55,100 --> 00:04:57,180
v prípade, že ukazovateľ je null prvý.

122
00:04:57,180 --> 00:04:59,190
Ak je to null, zoznam je prázdny,

123
00:04:59,190 --> 00:05:01,320
a my by sme mali vytlačiť správu, že, pretože zoznam je prázdny,

124
00:05:01,320 --> 00:05:03,250
nie je posledný uzol.

125
00:05:03,250 --> 00:05:05,190
Ale povedzme, že zoznam nie je prázdny.

126
00:05:05,190 --> 00:05:08,340
Ak tomu tak nie je, potom by sme mali prechádzať celý zoznam

127
00:05:08,340 --> 00:05:10,440
kým sa na posledný uzol zoznamu,

128
00:05:10,440 --> 00:05:13,030
a ako môžeme povedať, či sa pozeráme na posledné uzol v zozname?

129
00:05:13,670 --> 00:05:16,660
>> No, ak uzol je ďalší ukazovateľ je null,

130
00:05:16,660 --> 00:05:18,320
my vieme, že sme na konci

131
00:05:18,320 --> 00:05:22,390
od posledného ďalšie ukazovateľ by nemal ďalšie uzol v zozname, aby ukazoval na.

132
00:05:22,390 --> 00:05:26,590
Je dobrým zvykom vždy posledný uzol je ďalší ukazovateľ inicializovaný null

133
00:05:26,590 --> 00:05:30,800
mať štandardizovanú vlastnosť, ktorá upozorní nás, keď sme došli na koniec zoznamu.

134
00:05:30,800 --> 00:05:33,510
>> Takže, ak crawler → ďalšie je null,

135
00:05:34,120 --> 00:05:38,270
nezabudnite, že šípka syntax je skratka pre dereferencing

136
00:05:38,270 --> 00:05:40,010
ukazovateľ na struct, potom prístup

137
00:05:40,010 --> 00:05:42,510
jej ďalšie pole zodpovedá nepríjemné:

138
00:05:42,510 --> 00:05:48,750
(* Crawler). Ďalšie.

139
00:05:49,820 --> 00:05:51,260
Akonáhle sme našli posledný uzol,

140
00:05:51,260 --> 00:05:53,830
chceme tlačiť prolézacího → val,

141
00:05:53,830 --> 00:05:55,000
hodnota v aktuálnom uzle

142
00:05:55,000 --> 00:05:57,130
ktoré poznáme, je posledný.

143
00:05:57,130 --> 00:05:59,740
V opačnom prípade, keď sme ešte na poslednú uzla v zozname,

144
00:05:59,740 --> 00:06:02,340
musíme presunúť na ďalší uzol v zozname

145
00:06:02,340 --> 00:06:04,750
a skontrolujte, či je to ten posledný.

146
00:06:04,750 --> 00:06:07,010
Ak to chcete, len sme nastavili pásové ukazovateľ

147
00:06:07,010 --> 00:06:09,840
bodu za aktuálnym uzlom je ďalšie hodnoty,

148
00:06:09,840 --> 00:06:11,680
to znamená, že ďalší uzol v zozname.

149
00:06:11,680 --> 00:06:13,030
To sa vykonáva nastavením

150
00:06:13,030 --> 00:06:15,280
crawler = crawler → ďalšie.

151
00:06:16,050 --> 00:06:18,960
Potom sa tento proces opakovať, sa slučkou napríklad,

152
00:06:18,960 --> 00:06:20,960
kým nenájdeme posledný uzol.

153
00:06:20,960 --> 00:06:23,150
Tak napríklad, ak pásový ukazoval na hlavu,

154
00:06:24,050 --> 00:06:27,710
sme sa vydali prolézací modul, aby ukazoval na pásový → Ďalšie,

155
00:06:27,710 --> 00:06:30,960
ktorý je rovnaký ako ďalšie oblasti prvého uzla.

156
00:06:30,960 --> 00:06:33,620
Takže, teraz náš prehľadávač ukazuje na 2. uzla,

157
00:06:33,620 --> 00:06:35,480
a opäť, opakujeme to sa slučkou,

158
00:06:37,220 --> 00:06:40,610
až sme zistili, posledný uzol, ktorý je,

159
00:06:40,610 --> 00:06:43,640
kde uzla ďalšie ukazovateľ ukazuje na null.

160
00:06:43,640 --> 00:06:45,070
A tu to máme,

161
00:06:45,070 --> 00:06:47,620
sme našli posledný uzol v zozname, a vytlačiť svoju hodnotu,

162
00:06:47,620 --> 00:06:50,800
stačí použiť pásový → val.

163
00:06:50,800 --> 00:06:53,130
>> Pojazdu nie je tak zlé, ale čo o vkladanie?

164
00:06:53,130 --> 00:06:56,290
Povedzme, že chceme vložiť celé číslo do 4. mieste

165
00:06:56,290 --> 00:06:58,040
v celé číslo zozname.

166
00:06:58,040 --> 00:07:01,280
To je medzi súčasnými 3. a 4. uzlov.

167
00:07:01,280 --> 00:07:03,760
Opäť musíme prechádzať zoznam len

168
00:07:03,760 --> 00:07:06,520
dostať do 3. prvok, jeden sme vkladanie po.

169
00:07:06,520 --> 00:07:09,300
Takže, sme vytvoriť prolézacího ukazovateľ znovu prechádzať zoznam,

170
00:07:09,300 --> 00:07:11,400
skontrolujte, či naša hlava ukazovateľ je null,

171
00:07:11,400 --> 00:07:14,810
a ak tomu tak nie je, prejdite náš prehľadávač ukazovateľ na hlavnom uzle.

172
00:07:16,880 --> 00:07:18,060
Takže, sme na 1. prvok.

173
00:07:18,060 --> 00:07:21,020
Musíme ísť vpred 2 viac prvkov, ako môžeme vložiť,

174
00:07:21,020 --> 00:07:23,390
takže môžeme použiť pre sláčiky

175
00:07:23,390 --> 00:07:26,430
int i = 1; i <3; i + +

176
00:07:26,430 --> 00:07:28,590
a v každom opakovaní slučky,

177
00:07:28,590 --> 00:07:31,540
Rozšírenie našich pásový ukazovateľ vpred o 1 uzol

178
00:07:31,540 --> 00:07:34,570
skontrolovať, či je aktuálny uzol je ďalšie pole null,

179
00:07:34,570 --> 00:07:37,550
a ak je to nie je, presunúť naše pásový ukazovateľ na ďalší uzol

180
00:07:37,550 --> 00:07:41,810
nastavením je rovný aktuálnemu uzla budúceho ukazovateľ.

181
00:07:41,810 --> 00:07:45,210
Takže, pretože naše cyklu for hovorí k tomu, že

182
00:07:45,210 --> 00:07:47,550
dvakrát,

183
00:07:49,610 --> 00:07:51,190
sme dosiahli 3. uzol,

184
00:07:51,190 --> 00:07:53,110
a potom, čo náš prehľadávač ukazovateľ dosiahol uzol po

185
00:07:53,110 --> 00:07:55,270
ktoré chceme vložiť náš nový integer,

186
00:07:55,270 --> 00:07:57,050
ako sme vlastne robiť vkladanie?

187
00:07:57,050 --> 00:07:59,440
>> No, náš nový integer musí byť vložený do zoznamu

188
00:07:59,440 --> 00:08:01,250
ako súčasť vlastného uzla struct,

189
00:08:01,250 --> 00:08:03,140
, Pretože to je v skutočnosti sekvencie uzlov.

190
00:08:03,140 --> 00:08:05,690
Takže, poďme sa nový ukazovateľ na uzol

191
00:08:05,690 --> 00:08:08,910
tzv "new_node,"

192
00:08:08,910 --> 00:08:11,800
a nastavte ju upozorniť na pamäti, že sme teraz prideliť

193
00:08:11,800 --> 00:08:14,270
na halde pre uzol sám,

194
00:08:14,270 --> 00:08:16,000
a koľko pamäte potrebujeme prideliť?

195
00:08:16,000 --> 00:08:18,250
No, o veľkosti uzla,

196
00:08:20,450 --> 00:08:23,410
a chceme nastaviť svoj val poľa na celé číslo, ktoré chceme vložiť.

197
00:08:23,410 --> 00:08:25,590
Povedzme, 6.

198
00:08:25,590 --> 00:08:27,710
Teraz, uzol obsahuje náš celočíselnú hodnotu.

199
00:08:27,710 --> 00:08:30,650
Je tiež dobrým zvykom inicializovať nový uzol je ďalšie pole

200
00:08:30,650 --> 00:08:33,690
bodu na hodnotu null,

201
00:08:33,690 --> 00:08:35,080
ale čo teraz?

202
00:08:35,080 --> 00:08:37,179
>> Máme zmeniť vnútornú štruktúru zoznamu

203
00:08:37,179 --> 00:08:40,409
a ďalšie ukazovatele obsiahnuté v zozname je existujúci

204
00:08:40,409 --> 00:08:42,950
3. a 4. uzly.

205
00:08:42,950 --> 00:08:46,560
Vzhľadom k tomu, že ďalšie ukazovatele určujú poradie v zozname,

206
00:08:46,560 --> 00:08:48,650
a od tej doby sme vložením náš nový uzol

207
00:08:48,650 --> 00:08:50,510
priamo do stredu zoznamu,

208
00:08:50,510 --> 00:08:52,010
to môže byť trochu zložitejšie.

209
00:08:52,010 --> 00:08:54,250
To je preto, pamätajte, náš počítač

210
00:08:54,250 --> 00:08:56,250
pozná len umiestnenie uzlov v zozname

211
00:08:56,250 --> 00:09:00,400
pretože z ďalších ukazovateľov uložených v predchádzajúcich uzlov.

212
00:09:00,400 --> 00:09:03,940
Takže, ak sa niekedy stratil niektoré z týchto lokalít,

213
00:09:03,940 --> 00:09:06,860
povedať zmenou jedného z nasledujúcich ukazovateľov v našom zozname,

214
00:09:06,860 --> 00:09:09,880
Napríklad, že sme zmenili

215
00:09:09,880 --> 00:09:12,920
od 3. uzla vedľa poľa

216
00:09:12,920 --> 00:09:15,610
poukázať na niektoré uzla sem.

217
00:09:15,610 --> 00:09:17,920
Boli by sme smolu, pretože by sme

218
00:09:17,920 --> 00:09:20,940
tušenie, kde nájsť zvyšok zoznamu,

219
00:09:20,940 --> 00:09:23,070
a to je zrejme naozaj zlé.

220
00:09:23,070 --> 00:09:25,080
Takže, musíme byť naozaj pozor na ich poradie

221
00:09:25,080 --> 00:09:28,360
, V ktorom sme sa manipulovať naše ďalšie ukazovatele počas zavádzania.

222
00:09:28,360 --> 00:09:30,540
>> Takže, zjednodušiť to, povedzme, že

223
00:09:30,540 --> 00:09:32,220
naše prvé 4 uzly

224
00:09:32,220 --> 00:09:36,200
sa nazýva A, B, C a D, s šípkami predstavujúce reťaz ukazovateľov

225
00:09:36,200 --> 00:09:38,070
ktoré spájajú uzly.

226
00:09:38,070 --> 00:09:40,050
Takže, je nutné vložiť náš nový uzol

227
00:09:40,050 --> 00:09:42,070
medzi uzlami C a D.

228
00:09:42,070 --> 00:09:45,060
Je dôležité, aby to v správnom poradí, a ja vám ukážem, prečo.

229
00:09:45,060 --> 00:09:47,500
>> Poďme sa pozrieť na zlý spôsob, ako to urobiť ako prvé.

230
00:09:47,500 --> 00:09:49,490
Hele, my vieme, že nový uzol má prísť hneď po C,

231
00:09:49,490 --> 00:09:51,910
takže sa poďme nastaviť C je ďalší ukazovateľ

232
00:09:51,910 --> 00:09:54,700
poukázať na new_node.

233
00:09:56,530 --> 00:09:59,180
Dobre, zdá sa v poriadku, len musíme dokončiť už teraz

234
00:09:59,180 --> 00:10:01,580
Vďaka nového uzla je ďalší ukazovateľ bod D,

235
00:10:01,580 --> 00:10:03,250
Ale počkajte, ako môžeme urobiť, že?

236
00:10:03,250 --> 00:10:05,170
Jediná vec, ktorá by nám mohol povedať, kde D je,

237
00:10:05,170 --> 00:10:07,630
bola ďalšia ukazovateľ skôr uložené v C,

238
00:10:07,630 --> 00:10:09,870
ale my jednoducho prepísal tento ukazovateľ

239
00:10:09,870 --> 00:10:11,170
prejdite na nový uzol,

240
00:10:11,170 --> 00:10:14,230
takže už nemáme poňatia, kde D je v pamäti,

241
00:10:14,230 --> 00:10:17,020
a my sme stratili zvyšok zoznamu.

242
00:10:17,020 --> 00:10:19,000
Vôbec dobré.

243
00:10:19,000 --> 00:10:21,090
>> Tak, ako to urobíme toto právo?

244
00:10:22,360 --> 00:10:25,090
Po prvé, bodu nového uzla je ďalší ukazovateľ na D.

245
00:10:26,170 --> 00:10:28,990
Teraz, ako nový uzol je a C je ďalšie ukazovatele

246
00:10:28,990 --> 00:10:30,660
smerujú na rovnaký uzol, D,

247
00:10:30,660 --> 00:10:32,290
ale to je v poriadku.

248
00:10:32,290 --> 00:10:35,680
Teraz môžeme bod C je ďalší ukazovateľ na nový uzol.

249
00:10:37,450 --> 00:10:39,670
Takže sme urobili to bez straty dát.

250
00:10:39,670 --> 00:10:42,280
V kóde, C je aktuálny uzol

251
00:10:42,280 --> 00:10:45,540
že traversal ukazovateľ prolézací modul ukazuje na,

252
00:10:45,540 --> 00:10:50,400
a D je reprezentovaný uzlom na ktorý ukazuje aktuálnu uzla nasledujúceho poľa,

253
00:10:50,400 --> 00:10:52,600
alebo pásovom podvozku → ďalšie.

254
00:10:52,600 --> 00:10:55,460
Takže, najprv nastavte nový uzol je ďalší ukazovateľ

255
00:10:55,460 --> 00:10:57,370
poukázať na pásový → Ďalšie,

256
00:10:57,370 --> 00:11:00,880
rovnakým spôsobom sme si povedali, new_node budúci ukazovateľ by mal

257
00:11:00,880 --> 00:11:02,780
poukazujú na D na obrázku.

258
00:11:02,780 --> 00:11:04,540
Potom môžeme nastaviť aktuálny uzol je ďalší ukazovateľ

259
00:11:04,540 --> 00:11:06,330
do nášho nového uzla,

260
00:11:06,330 --> 00:11:10,980
rovnako ako sme museli čakať, až bodu C k new_node vo výkrese.

261
00:11:10,980 --> 00:11:12,250
Teraz je všetko v poriadku, a my sme nestratili

262
00:11:12,250 --> 00:11:14,490
prehľad o všetkých údajov, a my sme boli schopní len

263
00:11:14,490 --> 00:11:16,200
držať náš nový uzol v stredu zoznamu

264
00:11:16,200 --> 00:11:19,330
bez prestavať celú vec, alebo dokonca posunutie všetky prvky

265
00:11:19,330 --> 00:11:22,490
spôsob, akým by sa museli s pevnou dĺžkou poľa.

266
00:11:22,490 --> 00:11:26,020
>> Takže, prepojené zoznamy sú základné, ale dôležité, dynamická dátová štruktúra

267
00:11:26,020 --> 00:11:29,080
ktoré majú výhody aj nevýhody

268
00:11:29,080 --> 00:11:31,260
v porovnaní s poli a iných dátových štruktúr,

269
00:11:31,260 --> 00:11:33,350
a ako je to často v informatike,

270
00:11:33,350 --> 00:11:35,640
je dôležité vedieť, kedy použiť každý nástroj,

271
00:11:35,640 --> 00:11:37,960
takže si môžete vybrať ten správny nástroj na správne miesto.

272
00:11:37,960 --> 00:11:40,060
>> Pre viac praxe, skúste napísať funkcie

273
00:11:40,060 --> 00:11:42,080
odstránenie uzlov z prepojeného zoznamu -

274
00:11:42,080 --> 00:11:44,050
nezabudnite dávať pozor na poradie, v ktorom ste zmeny usporiadania

275
00:11:44,050 --> 00:11:47,430
vaše ďalšie ukazovatele, aby zabezpečili, že nestratíte kus svojho zoznamu -

276
00:11:47,430 --> 00:11:50,200
alebo funkciu počítať uzly v prepojenom zozname,

277
00:11:50,200 --> 00:11:53,280
alebo legrace jeden, obrátiť poradie všetkých uzlov v prepojenom zozname.

278
00:11:53,280 --> 00:11:56,090
>> Volám sa Jackson Steinkamp, ​​je to CS50.