1
00:00:07,260 --> 00:00:10,050
[Powered by Google Translate] V načrtovanje, smo pogosto morali predstavljati sezname vrednosti,

2
00:00:10,050 --> 00:00:12,840
kot so imena učencev v oddelku

3
00:00:12,840 --> 00:00:15,100
ali njihovi rezultati na zadnji kviza.

4
00:00:15,100 --> 00:00:17,430
>> V jeziku C, razglasila nizi se lahko uporablja

5
00:00:17,430 --> 00:00:19,160
za shranjevanje seznamov.

6
00:00:19,160 --> 00:00:21,200
To je težko našteti elementi seznama

7
00:00:21,200 --> 00:00:23,390
shranjeni v matriki, in če morate za dostop do

8
00:00:23,390 --> 00:00:25,050
ali spreminjanje i-element seznama

9
00:00:25,050 --> 00:00:27,570
Za poljubni indeks I,

10
00:00:27,570 --> 00:00:29,910
ki jih je mogoče storiti v stalnem času,

11
00:00:29,910 --> 00:00:31,660
vendar nizi so v slabšem položaju, preveč.

12
00:00:31,660 --> 00:00:33,850
>> Ko smo jih razglasi, smo morali reči

13
00:00:33,850 --> 00:00:35,900
spredaj kako velike so,

14
00:00:35,900 --> 00:00:38,160
to je, koliko elementov lahko shranite

15
00:00:38,160 --> 00:00:40,780
in kako velika so ti elementi, ki se določi glede na njihovo vrsto.

16
00:00:40,780 --> 00:00:45,450
Na primer, int arr (10)

17
00:00:45,450 --> 00:00:48,220
lahko shranite 10 predmetov

18
00:00:48,220 --> 00:00:50,200
da sta velikost notr.

19
00:00:50,200 --> 00:00:52,590
>> Ne moremo spremeniti array na velikost po deklaraciji.

20
00:00:52,590 --> 00:00:55,290
Moramo narediti nov niz, če želimo shraniti več elementov.

21
00:00:55,290 --> 00:00:57,410
Razlog za to omejitev obstaja, je, da se naše

22
00:00:57,410 --> 00:00:59,040
Program shrani celoten spekter

23
00:00:59,040 --> 00:01:02,310
kot sosednje kos pomnilnika.

24
00:01:02,310 --> 00:01:04,500
Povejte to je buffer, kjer hranijo v naši matriki.

25
00:01:04,500 --> 00:01:06,910
Morda obstaja druge spremenljivke

26
00:01:06,910 --> 00:01:08,310
ki se nahaja tik ob polju

27
00:01:08,310 --> 00:01:10,060
v spomin, tako da ne moremo

28
00:01:10,060 --> 00:01:12,060
samo da je polje večje.

29
00:01:12,060 --> 00:01:15,700
>> Včasih bi radi v trgovini array za hiter dostop do podatkov, hitrost

30
00:01:15,700 --> 00:01:17,650
za malo več prožnosti.

31
00:01:17,650 --> 00:01:20,380
Vpišite povezani seznam, drugo osnovno strukturo podatkov

32
00:01:20,380 --> 00:01:22,360
vam morda ne bo tako seznanjeni.

33
00:01:22,360 --> 00:01:24,200
Na visoki ravni,

34
00:01:24,200 --> 00:01:26,840
povezani seznam shranjuje podatke v zaporedju vozlišč

35
00:01:26,840 --> 00:01:29,280
, ki so med seboj povezani s povezavami,

36
00:01:29,280 --> 00:01:31,760
od tod tudi ime "povezani seznam."

37
00:01:31,760 --> 00:01:33,840
Kot bomo videli, je ta razlika v oblikovanju

38
00:01:33,840 --> 00:01:35,500
prihaja do različnih prednosti in slabosti

39
00:01:35,500 --> 00:01:37,000
kot matriko.

40
00:01:37,000 --> 00:01:39,840
>> Tukaj je del kode C zelo enostaven povezan seznam celih števil.

41
00:01:39,840 --> 00:01:42,190
Vidite lahko, da smo prikazali vsako vozlišče

42
00:01:42,190 --> 00:01:45,520
v seznamu kot struct, ki vsebuje 2 stvari,

43
00:01:45,520 --> 00:01:47,280
celo za shranjevanje imenuje "val"

44
00:01:47,280 --> 00:01:50,460
in povezava na naslednji vozel v seznamu

45
00:01:50,460 --> 00:01:52,990
ki jih predstavljamo kot kazalec, imenovano "next".

46
00:01:54,120 --> 00:01:56,780
Na ta način bomo lahko spremljali celoten seznam

47
00:01:56,780 --> 00:01:58,790
Z enim samim kazalcem na vozlišču 1.,

48
00:01:58,790 --> 00:02:01,270
in potem bomo lahko sledite naslednjim kazalci

49
00:02:01,270 --> 00:02:03,130
do 2. vozlišča,

50
00:02:03,130 --> 00:02:05,280
do 3. vozlišče,

51
00:02:05,280 --> 00:02:07,000
do 4. vozlišča,

52
00:02:07,000 --> 00:02:09,889
in tako naprej, dokler ne pridemo do konca seznama.

53
00:02:10,520 --> 00:02:12,210
>> Morda boste lahko videli 1 prednost, ki jo ima

54
00:02:12,210 --> 00:02:14,490
več statične strukture matrike - z povezan seznam,

55
00:02:14,490 --> 00:02:16,450
Ne potrebujemo velik kos pomnilnika v celoti.

56
00:02:17,400 --> 00:02:20,530
1. vozlišče seznama lahko živeli na tem mestu v spominu,

57
00:02:20,530 --> 00:02:23,160
in bi 2. vozlišče je vso pot tja.

58
00:02:23,160 --> 00:02:25,780
Mi lahko prišli do vseh vozlišč, ne glede na to, kje v pomnilniku so,

59
00:02:25,780 --> 00:02:28,890
ker se začne na vozlišču 1., vsako vozlišče je naslednji kazalec

60
00:02:28,890 --> 00:02:31,700
nam pove točno kam naprej.

61
00:02:31,700 --> 00:02:33,670
>> Poleg tega nimamo povedati vnaprej

62
00:02:33,670 --> 00:02:36,740
kako velik bo povezan seznam je način delamo s statičnimi polji,

63
00:02:36,740 --> 00:02:39,060
saj lahko vodijo dodajanje vozlišča na seznam

64
00:02:39,060 --> 00:02:42,600
tako dolgo, kot je prostor nekje v spominu po novih vozlišč.

65
00:02:42,600 --> 00:02:45,370
Zato povezani seznami so enostavne za dinamično spreminjanje velikosti.

66
00:02:45,370 --> 00:02:47,950
Recimo, kasneje v programu moramo dodati več vozlišč

67
00:02:47,950 --> 00:02:49,350
v našem seznamu.

68
00:02:49,350 --> 00:02:51,480
Če želite vstaviti novo vozlišče v našem seznamu na letenje,

69
00:02:51,480 --> 00:02:53,740
vse, kar moramo storiti, je dodeliti pomnilnika za to vozlišče,

70
00:02:53,740 --> 00:02:55,630
plop vrednosti podatkov,

71
00:02:55,630 --> 00:02:59,070
nato pa kraj, kjer želimo s prilagoditvijo ustrezne kazalce.

72
00:02:59,070 --> 00:03:02,310
>> Na primer, če bi želeli, da se vozlišče v med

73
00:03:02,310 --> 00:03:04,020
2. in 3. vozlišča seznama

74
00:03:04,020 --> 00:03:06,800
 mi ne bi bilo treba premakniti 2. ali 3. vozlišč na vse.

75
00:03:06,800 --> 00:03:09,190
Povejte smo vstavitve te rdeče vozlišče.

76
00:03:09,190 --> 00:03:12,890
Vse, kar bi morali storiti, je nastaviti novega vozlišča naslednji kazalec

77
00:03:12,890 --> 00:03:14,870
opozoriti na 3. vozlišče

78
00:03:14,870 --> 00:03:18,580
in potem rewire 2. vozlišča naslednji kazalec

79
00:03:18,580 --> 00:03:20,980
izpostaviti našega novega vozlišča.

80
00:03:22,340 --> 00:03:24,370
Torej, lahko spremenite velikost naše sezname na letenje

81
00:03:24,370 --> 00:03:26,090
saj je naš računalnik se ne sklicuje na indeksiranje,

82
00:03:26,090 --> 00:03:28,990
ampak o povezovanju z napotke za njihovo shranjevanje.

83
00:03:29,120 --> 00:03:31,600
>> Vendar pa je pomanjkljivost povezani seznam

84
00:03:31,600 --> 00:03:33,370
je, da za razliko od statičnega array,

85
00:03:33,370 --> 00:03:36,690
računalnik ne more samo skoči na sredino seznama.

86
00:03:38,040 --> 00:03:40,780
Ker računalnik mora obiskati vsak vozlišča v povezanem seznamu

87
00:03:40,780 --> 00:03:42,330
priti do naslednjega,

88
00:03:42,330 --> 00:03:44,770
to bo trajalo dlje, da najdejo določeno vozlišče

89
00:03:44,770 --> 00:03:46,400
kot bi se v matriki.

90
00:03:46,400 --> 00:03:48,660
Prečkanje celoten seznam potreben čas sorazmerno

91
00:03:48,660 --> 00:03:50,580
na dolžino seznama,

92
00:03:50,580 --> 00:03:54,630
ali O (n) v asimptotične zapisu.

93
00:03:54,630 --> 00:03:56,510
V povprečju dosegale vozlišče

94
00:03:56,510 --> 00:03:58,800
meni tudi čas sorazmerno n.

95
00:03:58,800 --> 00:04:00,700
>> Zdaj, kaj je dejansko napisati nekaj kode

96
00:04:00,700 --> 00:04:02,000
, ki deluje s povezanimi seznamov.

97
00:04:02,000 --> 00:04:04,220
Recimo, da želimo povezan seznam celih števil.

98
00:04:04,220 --> 00:04:06,140
Mi lahko predstavlja vozlišče v našem seznamu še enkrat

99
00:04:06,140 --> 00:04:08,340
kot struct z 2 področjih,

100
00:04:08,340 --> 00:04:10,750
celoštevilska vrednost se imenuje "val"

101
00:04:10,750 --> 00:04:13,490
in naslednji kazalec na naslednji vozel seznama.

102
00:04:13,490 --> 00:04:15,660
No, zdi dovolj preprosta.

103
00:04:15,660 --> 00:04:17,220
>> Recimo, da želimo napisati funkcijo

104
00:04:17,220 --> 00:04:19,329
ki prehaja iz seznama in izpise ven

105
00:04:19,329 --> 00:04:22,150
vrednost shranjena v zadnjem vozlišču seznama.

106
00:04:22,150 --> 00:04:24,850
No, to pomeni, da bomo morali za prečkanje vsa vozlišča v seznamu

107
00:04:24,850 --> 00:04:27,310
da je bil zadnji, ampak saj ne bomo dodajanjem

108
00:04:27,310 --> 00:04:29,250
ali izbris nič, ne želimo spremeniti

109
00:04:29,250 --> 00:04:32,210
notranja struktura prihodnjih kazalcev na seznamu.

110
00:04:32,210 --> 00:04:34,790
>> Torej se bomo morali kazalec posebej za prečkanje

111
00:04:34,790 --> 00:04:36,940
ki bomo poklicali "pajka".

112
00:04:36,940 --> 00:04:38,870
To bo plazijo skozi vse elemente na seznamu

113
00:04:38,870 --> 00:04:41,190
jih po verigo naslednjih kazalcev.

114
00:04:41,190 --> 00:04:43,750
Vsi smo shranili, je kazalec na vozlišče 1.,

115
00:04:43,750 --> 00:04:45,730
ali "glava" seznama.

116
00:04:45,730 --> 00:04:47,370
Vodja opozarja na 1. vozlišča.

117
00:04:47,370 --> 00:04:49,120
To je tipa kazalec do vozlišča.

118
00:04:49,120 --> 00:04:51,280
>> Da bi dobili dejanski 1. vozlišča v seznamu

119
00:04:51,280 --> 00:04:53,250
moramo ciljne datoteke, to kazalec,

120
00:04:53,250 --> 00:04:55,100
vendar preden jo lahko dereference, moramo preveriti

121
00:04:55,100 --> 00:04:57,180
Če je kazalec null prvi.

122
00:04:57,180 --> 00:04:59,190
Če je ničen, je seznam prazen,

123
00:04:59,190 --> 00:05:01,320
in bi morali natisniti sporočilo, da je, ker je seznam prazen,

124
00:05:01,320 --> 00:05:03,250
ni zadnji vozel.

125
00:05:03,250 --> 00:05:05,190
Ampak, recimo, da seznam ni prazen.

126
00:05:05,190 --> 00:05:08,340
Če ni, potem bi morali plaziti skozi celoten seznam

127
00:05:08,340 --> 00:05:10,440
dokler ne pridemo do zadnje vozlišče seznama,

128
00:05:10,440 --> 00:05:13,030
in kako lahko poveste, če gledamo na zadnji vozel v seznamu?

129
00:05:13,670 --> 00:05:16,660
>> No, če je vozlišče je naslednji kazalec nič,

130
00:05:16,660 --> 00:05:18,320
Vemo, da smo na koncu

131
00:05:18,320 --> 00:05:22,390
ker bi zadnja Naslednji kazalec nimajo poleg vozlišča v seznamu, da kaže.

132
00:05:22,390 --> 00:05:26,590
To je dobra praksa, da vedno v lanskem vozlišča poleg kazalec inicializiranega na null

133
00:05:26,590 --> 00:05:30,800
da imajo standardizirano lastnost, ki nas opozori, ko smo prišli do konca seznama.

134
00:05:30,800 --> 00:05:33,510
>> Torej, če na gosenicah → naslednja nič,

135
00:05:34,120 --> 00:05:38,270
ne pozabite, da je puščica sintaksa je bližnjica za Dereferenciranje

136
00:05:38,270 --> 00:05:40,010
kazalec na struct, nato dostop

137
00:05:40,010 --> 00:05:42,510
njegovo naslednje polje enako, kar je nerodno:

138
00:05:42,510 --> 00:05:48,750
(* Pajek). Naslednjo.

139
00:05:49,820 --> 00:05:51,260
Ko smo našli zadnje vozlišče,

140
00:05:51,260 --> 00:05:53,830
želimo natisniti na gosenicah → val,

141
00:05:53,830 --> 00:05:55,000
vrednost v trenutnem vozlišču

142
00:05:55,000 --> 00:05:57,130
ki vemo, da je to zadnja.

143
00:05:57,130 --> 00:05:59,740
V nasprotnem primeru, če nismo še na zadnji vozel v seznamu,

144
00:05:59,740 --> 00:06:02,340
moramo premakniti na naslednji vozel v seznamu

145
00:06:02,340 --> 00:06:04,750
in preverite, če je to zadnja.

146
00:06:04,750 --> 00:06:07,010
Če želite to narediti, samo iz naše gosenicah kazalec

147
00:06:07,010 --> 00:06:09,840
opozoriti na naslednjo trenutnega vozlišča vrednosti,

148
00:06:09,840 --> 00:06:11,680
to je naslednji vozel v seznamu.

149
00:06:11,680 --> 00:06:13,030
To se opravi z določitvijo

150
00:06:13,030 --> 00:06:15,280
pajek pajek = → naslednja.

151
00:06:16,050 --> 00:06:18,960
Potem smo ponovite postopek, z zanko, na primer,

152
00:06:18,960 --> 00:06:20,960
dokler ne najdemo zadnje vozlišče.

153
00:06:20,960 --> 00:06:23,150
Tako, na primer, če pajek je obrnjena na glavo,

154
00:06:24,050 --> 00:06:27,710
smo postavili pajka opozoriti na gosenicah → naslednji,

155
00:06:27,710 --> 00:06:30,960
kar je enako kot v naslednjem polju 1. vozlišča.

156
00:06:30,960 --> 00:06:33,620
Torej, zdaj je naša pajek kaže na 2. vozlišča,

157
00:06:33,620 --> 00:06:35,480
in spet ponavljamo to z zanko,

158
00:06:37,220 --> 00:06:40,610
dokler ne bomo našli zadnje vozlišče, ki je,

159
00:06:40,610 --> 00:06:43,640
vozlišče, kjer je naslednji kazalec kaže na null.

160
00:06:43,640 --> 00:06:45,070
In tam jo imamo,

161
00:06:45,070 --> 00:06:47,620
smo našli zadnje vozlišče seznama, in natisniti svojo vrednost,

162
00:06:47,620 --> 00:06:50,800
smo samo uporabo gosenicah → val.

163
00:06:50,800 --> 00:06:53,130
>> Prečesava ni tako slabo, toda kaj vstavljanje?

164
00:06:53,130 --> 00:06:56,290
Lets reči hočemo, da vstavite celo število v 4. mesto

165
00:06:56,290 --> 00:06:58,040
celo v seznamu.

166
00:06:58,040 --> 00:07:01,280
To je med sedanjimi 3. in 4. vozlišč.

167
00:07:01,280 --> 00:07:03,760
Spet imamo za prečkanje seznam le

168
00:07:03,760 --> 00:07:06,520
priti do 3. element, na katerem sva po vstavitvi.

169
00:07:06,520 --> 00:07:09,300
Torej, smo ustvarili gosenicah kazalec ponovno prečkanje seznam,

170
00:07:09,300 --> 00:07:11,400
preveri, če je glava kazalec nič,

171
00:07:11,400 --> 00:07:14,810
in če ni, opozarja naš gosenicah kazalec na glavnem vozlišču.

172
00:07:16,880 --> 00:07:18,060
Torej, da smo na 1. elementa.

173
00:07:18,060 --> 00:07:21,020
Moramo iti naprej 2 več elementov, preden bomo lahko vstavite,

174
00:07:21,020 --> 00:07:23,390
tako da bomo lahko uporabite za zanko

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

176
00:07:26,430 --> 00:07:28,590
in v vsaki ponovitvi zanke,

177
00:07:28,590 --> 00:07:31,540
izboljšanje našega gosenicah kazalec naprej za 1 vozlišče

178
00:07:31,540 --> 00:07:34,570
za preverjanje, če je trenutno vozlišče v naslednje polje je nična,

179
00:07:34,570 --> 00:07:37,550
in če ni, gremo naši gosenicah kazalec na naslednje vozlišče

180
00:07:37,550 --> 00:07:41,810
z določitvijo je enaka dostavo trenutnega vozlišča kazalca.

181
00:07:41,810 --> 00:07:45,210
Torej, ker smo v zanko pravi za to

182
00:07:45,210 --> 00:07:47,550
dvakrat,

183
00:07:49,610 --> 00:07:51,190
smo dosegli 3. vozlišče,

184
00:07:51,190 --> 00:07:53,110
in ko je naš pajek kazalec dosegel vozlišče po

185
00:07:53,110 --> 00:07:55,270
katero želimo vstaviti našo novo celo število,

186
00:07:55,270 --> 00:07:57,050
kako smo dejansko storite vstavljanje?

187
00:07:57,050 --> 00:07:59,440
>> No, naš novi celo je treba vstaviti na seznam

188
00:07:59,440 --> 00:08:01,250
kot del svoje struct vozlišča,

189
00:08:01,250 --> 00:08:03,140
ker je to res zaporedje vozlišč.

190
00:08:03,140 --> 00:08:05,690
Torej, naredimo nov kazalec na vozlišče

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

192
00:08:08,910 --> 00:08:11,800
in jo nastavite na točko v spomin, da smo zdaj dodeliti

193
00:08:11,800 --> 00:08:14,270
na kup za vozlišče sam,

194
00:08:14,270 --> 00:08:16,000
in koliko pomnilnika bomo morali dodeliti?

195
00:08:16,000 --> 00:08:18,250
No, velikost vozlišča,

196
00:08:20,450 --> 00:08:23,410
in želimo, da določijo svoje val polje na celo število, ki ga želite vstaviti.

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

198
00:08:25,590 --> 00:08:27,710
Zdaj, vozlišče vsebuje našo vrednost celega števila.

199
00:08:27,710 --> 00:08:30,650
Prav tako je dobra praksa za inicializacijo novega vozlišča naslednje polje

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

201
00:08:33,690 --> 00:08:35,080
pa kaj zdaj?

202
00:08:35,080 --> 00:08:37,179
>> Moramo spremeniti notranjo strukturo seznama

203
00:08:37,179 --> 00:08:40,409
in naslednji kazalci iz obstoječih na seznamu za

204
00:08:40,409 --> 00:08:42,950
3. in 4. vozlišča.

205
00:08:42,950 --> 00:08:46,560
Ker se naslednji kazalci določi vrstni red na seznamu

206
00:08:46,560 --> 00:08:48,650
in ker smo vstavljanje našo novo vozlišče

207
00:08:48,650 --> 00:08:50,510
desno na sredini seznama,

208
00:08:50,510 --> 00:08:52,010
je lahko nekoliko zapleteno.

209
00:08:52,010 --> 00:08:54,250
To je zato, ker se spomnite, naš računalnik

210
00:08:54,250 --> 00:08:56,250
Samo ve, kje vozlišč v seznamu

211
00:08:56,250 --> 00:09:00,400
zaradi naslednjih kazalcev, shranjenih v prejšnjih vozlišč.

212
00:09:00,400 --> 00:09:03,940
Torej, če bomo kdaj izgubil občutek za vsako od teh mest,

213
00:09:03,940 --> 00:09:06,860
pravijo, da spremenite eno od naslednjih kazalcev v našem seznamu,

214
00:09:06,860 --> 00:09:09,880
Recimo, da smo spremenili

215
00:09:09,880 --> 00:09:12,920
3. vozlišča naslednje polje

216
00:09:12,920 --> 00:09:15,610
izpostaviti nekatere vozlišča tam.

217
00:09:15,610 --> 00:09:17,920
Mi bi lahko od sreče, ker mi ne bi

218
00:09:17,920 --> 00:09:20,940
sanja, kje najti preostanek seznama

219
00:09:20,940 --> 00:09:23,070
in to je očitno res slabo.

220
00:09:23,070 --> 00:09:25,080
Torej, moramo biti zelo previdni, da

221
00:09:25,080 --> 00:09:28,360
, v katerem smo manipulirajo svoje naslednje napotke med vstavljanjem.

222
00:09:28,360 --> 00:09:30,540
>> Torej, poenostaviti to, recimo, da

223
00:09:30,540 --> 00:09:32,220
naša prva 4 vozlov

224
00:09:32,220 --> 00:09:36,200
se imenujejo A, B, C in D, s puščicami predstavljajo verige kazalcev

225
00:09:36,200 --> 00:09:38,070
ki povezujejo vozlišča.

226
00:09:38,070 --> 00:09:40,050
Torej, moramo vstaviti našo novo vozlišče

227
00:09:40,050 --> 00:09:42,070
vmes vozlišča C in D.

228
00:09:42,070 --> 00:09:45,060
To je ključnega pomena, da to storite v pravilnem zaporedju, in pokazal ti bom, zakaj.

229
00:09:45,060 --> 00:09:47,500
>> Oglejmo si na napačen način, da to storite najprej.

230
00:09:47,500 --> 00:09:49,490
Hej, vemo, da je novo vozlišče je prišel takoj po C,

231
00:09:49,490 --> 00:09:51,910
tako da je določeno naslednji kazalec C je

232
00:09:51,910 --> 00:09:54,700
izpostaviti new_node.

233
00:09:56,530 --> 00:09:59,180
V redu, se zdi v redu, bomo morali končati do zdaj, ki jih

234
00:09:59,180 --> 00:10:01,580
izdelavo novega vozlišča poleg kazalca točko D,

235
00:10:01,580 --> 00:10:03,250
ampak počakajte, kako lahko to storimo?

236
00:10:03,250 --> 00:10:05,170
Edina stvar, ki bi nam lahko poveste, kje je bil D,

237
00:10:05,170 --> 00:10:07,630
je naslednji kazalec prej shranjen v C,

238
00:10:07,630 --> 00:10:09,870
vendar smo šele na novo napisal, da je kazalec

239
00:10:09,870 --> 00:10:11,170
da kaže na novo vozlišče,

240
00:10:11,170 --> 00:10:14,230
tako da nimamo več nobenega pojma, kje je D v spominu,

241
00:10:14,230 --> 00:10:17,020
in smo izgubili preostanek seznama.

242
00:10:17,020 --> 00:10:19,000
Ni dobro.

243
00:10:19,000 --> 00:10:21,090
>> Torej, kako bomo to pravico?

244
00:10:22,360 --> 00:10:25,090
Prvič, poudariti novega vozlišča naslednji kazalec na D.

245
00:10:26,170 --> 00:10:28,990
Zdaj, oba nova vozlišča in C je naslednji kazalci

246
00:10:28,990 --> 00:10:30,660
obrnjena v isto vozlišče, D,

247
00:10:30,660 --> 00:10:32,290
ampak to je v redu.

248
00:10:32,290 --> 00:10:35,680
Sedaj lahko naslednji točki C je kazalec na novo vozlišče.

249
00:10:37,450 --> 00:10:39,670
Zato smo to storili, ne da bi pri tem izgubili podatke.

250
00:10:39,670 --> 00:10:42,280
V kode C je trenutna vozlišče

251
00:10:42,280 --> 00:10:45,540
da prečkanje kazalec kaže na gosenicah,

252
00:10:45,540 --> 00:10:50,400
in D zastopa vozlišče opozoril, da do naslednjega trenutnega vozlišča področju,

253
00:10:50,400 --> 00:10:52,600
ali gosenicah → naslednja.

254
00:10:52,600 --> 00:10:55,460
Torej, moramo najprej določiti novega vozlišča naslednji kazalec

255
00:10:55,460 --> 00:10:57,370
opozoriti na gosenicah → naslednji,

256
00:10:57,370 --> 00:11:00,880
na enak način, smo rekli naslednji kazalec new_node je treba

257
00:11:00,880 --> 00:11:02,780
kažejo D na sliki.

258
00:11:02,780 --> 00:11:04,540
Potem bomo lahko nastavite trenutno vozlišče v naslednji kazalec

259
00:11:04,540 --> 00:11:06,330
za našo novo vozlišče,

260
00:11:06,330 --> 00:11:10,980
tako kot smo morali čakati na točko C na new_node na sliki.

261
00:11:10,980 --> 00:11:12,250
Zdaj je vse v redu, in nismo izgubili

262
00:11:12,250 --> 00:11:14,490
spremljanje vseh podatkov, in smo lahko samo

263
00:11:14,490 --> 00:11:16,200
držati našega novega vozlišča v sredini seznama

264
00:11:16,200 --> 00:11:19,330
ne obnovi celotno stvar ali celo premika elementov

265
00:11:19,330 --> 00:11:22,490
tako bi si morali s fiksno dolžino niza.

266
00:11:22,490 --> 00:11:26,020
>> Torej, povezani seznami osnovni, vendar pomembna dinamična struktura podatkov

267
00:11:26,020 --> 00:11:29,080
ki imajo tako prednosti kot slabosti

268
00:11:29,080 --> 00:11:31,260
v primerjavi z nizi podatkov in drugih objektov,

269
00:11:31,260 --> 00:11:33,350
in kot se pogosto dogaja na področju računalništva,

270
00:11:33,350 --> 00:11:35,640
je pomembno, da vedo, kdaj uporabiti vsako orodje,

271
00:11:35,640 --> 00:11:37,960
tako da lahko izberete pravo orodje za pravo delo.

272
00:11:37,960 --> 00:11:40,060
>> Za več prakse, poskusite pisati funkcij

273
00:11:40,060 --> 00:11:42,080
Brisanje vozlišča iz povezan seznam -

274
00:11:42,080 --> 00:11:44,050
ne pozabite, da bodite previdni, o vrstnem redu, v katerem ste preurediti

275
00:11:44,050 --> 00:11:47,430
vaš naslednji kazalci, da se zagotovi, da ne boste izgubili kos seznama -

276
00:11:47,430 --> 00:11:50,200
ali funkcijo za štetje vozlišča v povezanem seznamu

277
00:11:50,200 --> 00:11:53,280
ali smešna, da se obrne vrstni red vseh vozlišč v povezanem seznamu.

278
00:11:53,280 --> 00:11:56,090
>> Moje ime je Jackson Steinkamp, ​​to je CS50.