1
00:00:07,260 --> 00:00:10,050
[Powered by Google Translate] Í forritun, þurfum við oft að tákna lista af gildum,

2
00:00:10,050 --> 00:00:12,840
svo sem nöfn nemenda í kafla

3
00:00:12,840 --> 00:00:15,100
eða frammistöðu þeirra á síðustu spurningakeppni.

4
00:00:15,100 --> 00:00:17,430
>> Í C tungumál, lýsti fylki er hægt að nota

5
00:00:17,430 --> 00:00:19,160
að geyma lista.

6
00:00:19,160 --> 00:00:21,200
Það er auðvelt að telja upp þætti lista

7
00:00:21,200 --> 00:00:23,390
geymd í fylki, og ef þú þarft að fá aðgang

8
00:00:23,390 --> 00:00:25,050
eða breyta ith lista þáttur

9
00:00:25,050 --> 00:00:27,570
fyrir sumir handahófi vísitölu I,

10
00:00:27,570 --> 00:00:29,910
sem hægt er að gera í föstu tíma,

11
00:00:29,910 --> 00:00:31,660
en fylki hafa ókosti líka.

12
00:00:31,660 --> 00:00:33,850
>> Þegar við lýsa þeim, erum við að þurfa að segja

13
00:00:33,850 --> 00:00:35,900
upp að framan hversu stór þau eru,

14
00:00:35,900 --> 00:00:38,160
það er, hversu margir þættir sem þeir geta geymt

15
00:00:38,160 --> 00:00:40,780
og hversu stór þessir þættir eru, sem ræðst af gerð þeirra.

16
00:00:40,780 --> 00:00:45,450
Til dæmis, int Arr (10)

17
00:00:45,450 --> 00:00:48,220
getur geymt 10 atriði

18
00:00:48,220 --> 00:00:50,200
sem eru á stærð við heiltala.

19
00:00:50,200 --> 00:00:52,590
>> Við getum ekki breytt stærð fylki eftir að yfirlýsingu.

20
00:00:52,590 --> 00:00:55,290
Við verðum að gera nýjan array ef við viljum geyma fleiri atriði.

21
00:00:55,290 --> 00:00:57,410
Ástæðan þessi takmörkun er að okkar

22
00:00:57,410 --> 00:00:59,040
program geymir alla array

23
00:00:59,040 --> 00:01:02,310
sem samfelldu klumpur af minni.

24
00:01:02,310 --> 00:01:04,500
Segja þetta er biðminni þar geymdar í array okkar.

25
00:01:04,500 --> 00:01:06,910
Það gæti verið aðrar breytur

26
00:01:06,910 --> 00:01:08,310
staðsett rétt við hliðina á fjölda

27
00:01:08,310 --> 00:01:10,060
í minni, þannig að við getum ekki

28
00:01:10,060 --> 00:01:12,060
bara gera array stærri.

29
00:01:12,060 --> 00:01:15,700
>> Stundum viljum við eiga viðskipti fljótur gögn fylki er aðgangur hraði

30
00:01:15,700 --> 00:01:17,650
fyrir smá meiri sveigjanleika.

31
00:01:17,650 --> 00:01:20,380
Sláðu tengda lista, annar undirstöðu gögn uppbygging

32
00:01:20,380 --> 00:01:22,360
þú getur ekki verið eins kunnugur.

33
00:01:22,360 --> 00:01:24,200
Á háu stigi,

34
00:01:24,200 --> 00:01:26,840
a tengda listanum geymir gögn í röð hnúta

35
00:01:26,840 --> 00:01:29,280
sem eru tengd við hvert annað með tenglum,

36
00:01:29,280 --> 00:01:31,760
þess vegna the nafn "tengda listanum."

37
00:01:31,760 --> 00:01:33,840
Eins og við munum sjá, þessi munur á hönnun

38
00:01:33,840 --> 00:01:35,500
leiðir til mismunandi kostum og göllum

39
00:01:35,500 --> 00:01:37,000
en fylki.

40
00:01:37,000 --> 00:01:39,840
>> Villutrú 'sumir C kóða fyrir mjög einfalt tengd lista heiltölur.

41
00:01:39,840 --> 00:01:42,190
Þú getur séð að við höfum fulltrúa hver hnútur

42
00:01:42,190 --> 00:01:45,520
í skránni sem strúktúr sem inniheldur 2 hluti,

43
00:01:45,520 --> 00:01:47,280
heiltala að geyma kallast "Val '

44
00:01:47,280 --> 00:01:50,460
og tengill á næsta hnút á listanum

45
00:01:50,460 --> 00:01:52,990
sem við komum fram sem bendill sem heitir "næst."

46
00:01:54,120 --> 00:01:56,780
Þannig getum við fylgst með öllu lista

47
00:01:56,780 --> 00:01:58,790
með aðeins einn bendi á 1 hnút,

48
00:01:58,790 --> 00:02:01,270
og þá getum við fylgst með næsta ábendingum

49
00:02:01,270 --> 00:02:03,130
til 2. hnút,

50
00:02:03,130 --> 00:02:05,280
á 3. hnút,

51
00:02:05,280 --> 00:02:07,000
til 4. hnút,

52
00:02:07,000 --> 00:02:09,889
og svo framvegis, þar til við fá til the endir af the listi.

53
00:02:10,520 --> 00:02:12,210
>> Þú might vera fær til að sjá 1 kostur það hefur

54
00:02:12,210 --> 00:02:14,490
yfir truflanir array uppbyggingu - með tengda lista,

55
00:02:14,490 --> 00:02:16,450
við þurfum ekki að stór klumpur af minni öllu.

56
00:02:17,400 --> 00:02:20,530
The 1. hnútur á listanum gæti lifað á þessum stað í minni,

57
00:02:20,530 --> 00:02:23,160
og 2. hnút gæti verið alla leið hérna.

58
00:02:23,160 --> 00:02:25,780
Við getum fengið að öllum hnúður sama hvar í minni sem þeir eru,

59
00:02:25,780 --> 00:02:28,890
því að byrja á 1 hnút, næsta músina hver hnútur er

60
00:02:28,890 --> 00:02:31,700
segir okkur nákvæmlega hvar á að fara næst.

61
00:02:31,700 --> 00:02:33,670
>> Auk þess höfum við ekki að segja upp fyrir framan

62
00:02:33,670 --> 00:02:36,740
hversu stór tengdur listi vilja vera the vegur við gera við truflanir fylki,

63
00:02:36,740 --> 00:02:39,060
þar sem við getum haldið áfram að bæta hnút við lista

64
00:02:39,060 --> 00:02:42,600
svo lengi sem það er pláss einhvers staðar í minni fyrir nýjum hnúður.

65
00:02:42,600 --> 00:02:45,370
Því eru tengdir listar auðvelt að búa virk.

66
00:02:45,370 --> 00:02:47,950
Segja, síðar í áætluninni sem við þurfum að bæta við fleiri hnútar

67
00:02:47,950 --> 00:02:49,350
í listanum okkar.

68
00:02:49,350 --> 00:02:51,480
Til að setja inn nýjan hnút í listanum okkar á flugu,

69
00:02:51,480 --> 00:02:53,740
allt sem við þurfum að gera er að úthluta minni fyrir að hnút,

70
00:02:53,740 --> 00:02:55,630
plop í gögn gildi,

71
00:02:55,630 --> 00:02:59,070
og þá setja það sem við viljum með því að breyta viðeigandi ábendingum.

72
00:02:59,070 --> 00:03:02,310
>> Til dæmis, ef við vildum að setja hnút á milli

73
00:03:02,310 --> 00:03:04,020
2. og 3. hnútar á listanum,

74
00:03:04,020 --> 00:03:06,800
 við myndum ekki þurfa að færa 2 eða 3 hnúður yfirleitt.

75
00:03:06,800 --> 00:03:09,190
Segja að við erum að setja þetta rauða hnút.

76
00:03:09,190 --> 00:03:12,890
Allt sem við myndum þurfa að gera er að setja næstu músina nýju hnút á

77
00:03:12,890 --> 00:03:14,870
að benda á 3. hnút

78
00:03:14,870 --> 00:03:18,580
og þá rewire næstu músina 2. Hnútur er

79
00:03:18,580 --> 00:03:20,980
að benda á nýja hnút okkar.

80
00:03:22,340 --> 00:03:24,370
Svo getum við breyta listum okkar á flugu

81
00:03:24,370 --> 00:03:26,090
þar sem tölvan okkar er ekki að treysta á flokkun,

82
00:03:26,090 --> 00:03:28,990
heldur á að tengja með ábendingum til að geyma þá.

83
00:03:29,120 --> 00:03:31,600
>> Hins vegar ókostur tengdir listar

84
00:03:31,600 --> 00:03:33,370
er að ólíkt kyrrstæða fylking,

85
00:03:33,370 --> 00:03:36,690
tölvan getur ekki bara hoppa á miðjum listanum.

86
00:03:38,040 --> 00:03:40,780
Þar sem tölvan er að heimsækja hvern hnút í tengda listanum

87
00:03:40,780 --> 00:03:42,330
til að fá til the næstur einn,

88
00:03:42,330 --> 00:03:44,770
það er að fara að taka lengri tíma til að finna tiltekna hnút

89
00:03:44,770 --> 00:03:46,400
en það væri í fylki.

90
00:03:46,400 --> 00:03:48,660
Til að fara yfir allt listi tekur tíma hlutfalli

91
00:03:48,660 --> 00:03:50,580
að lengd á listanum,

92
00:03:50,580 --> 00:03:54,630
eða O (n) í asymptotic merki.

93
00:03:54,630 --> 00:03:56,510
Að meðaltali ná hvaða hnút

94
00:03:56,510 --> 00:03:58,800
einnig tekur tíma í réttu hlutfalli við n.

95
00:03:58,800 --> 00:04:00,700
>> Nú, við skulum í raun að skrifa nokkur númer

96
00:04:00,700 --> 00:04:02,000
sem virkar með tengd listum.

97
00:04:02,000 --> 00:04:04,220
Segjum að við viljum tengd lista yfir heiltölur.

98
00:04:04,220 --> 00:04:06,140
Við getur táknað hnút í lista okkar aftur

99
00:04:06,140 --> 00:04:08,340
sem strúktúr með 2 sviðum,

100
00:04:08,340 --> 00:04:10,750
heiltala gildi kallast "Val '

101
00:04:10,750 --> 00:04:13,490
og næsta bendi á næsta hnút á listanum.

102
00:04:13,490 --> 00:04:15,660
Jæja virðist nógu einfalt.

103
00:04:15,660 --> 00:04:17,220
>> Segjum að við viljum að skrifa fall

104
00:04:17,220 --> 00:04:19,329
sem traverses listanum og prentar út

105
00:04:19,329 --> 00:04:22,150
gildi sem eru geymdar í síðustu hnút listanum.

106
00:04:22,150 --> 00:04:24,850
Jæja, það þýðir að við þurfum að fara yfir alla hnúta á listanum

107
00:04:24,850 --> 00:04:27,310
að finna það síðasta, en þar sem við erum ekki að bæta

108
00:04:27,310 --> 00:04:29,250
eða eyða neitt, gera við viljum ekki að breyta

109
00:04:29,250 --> 00:04:32,210
innri uppbyggingu næstu ábendingum á listanum.

110
00:04:32,210 --> 00:04:34,790
>> Svo þurfum við að fá bendi sérstaklega fyrir traversal

111
00:04:34,790 --> 00:04:36,940
sem við munum kalla "vefskriðillinn.

112
00:04:36,940 --> 00:04:38,870
Það mun skríða í gegnum alla þætti listanum

113
00:04:38,870 --> 00:04:41,190
með því að fylgja keðju næstu ábendingum.

114
00:04:41,190 --> 00:04:43,750
Allt sem við höfum geymt er bendi á 1 hnút,

115
00:04:43,750 --> 00:04:45,730
eða "höfuð" af listanum.

116
00:04:45,730 --> 00:04:47,370
Head bendir á 1. hnút.

117
00:04:47,370 --> 00:04:49,120
Það er af gerðinni músina til hnút.

118
00:04:49,120 --> 00:04:51,280
>> Til að fá raunverulegan 1 hnút á listanum,

119
00:04:51,280 --> 00:04:53,250
við verðum að dereference þetta bendi,

120
00:04:53,250 --> 00:04:55,100
en áður en við getum dereference það, þurfum við að athuga

121
00:04:55,100 --> 00:04:57,180
Ef bendillinn er núll fyrst.

122
00:04:57,180 --> 00:04:59,190
Ef það er núll, sem er tómur,

123
00:04:59,190 --> 00:05:01,320
og við ættum að prenta út skilaboð að þar sem listinn er tómur,

124
00:05:01,320 --> 00:05:03,250
Það er ekkert síðasta hnút.

125
00:05:03,250 --> 00:05:05,190
En, segja skulum listinn er ekki tómur.

126
00:05:05,190 --> 00:05:08,340
Ef það er ekki, þá ættum við að skríða í gegnum allt lista

127
00:05:08,340 --> 00:05:10,440
þangað til við komum að síðasta hnút á listanum,

128
00:05:10,440 --> 00:05:13,030
og hvernig getum við sagt ef við erum að horfa á síðasta hnút í listanum?

129
00:05:13,670 --> 00:05:16,660
>> Jæja, ef næsta músina hnúturinn er núll,

130
00:05:16,660 --> 00:05:18,320
við vitum að við erum í lok

131
00:05:18,320 --> 00:05:22,390
síðan síðasta næsta bendillinn hefði ekki næstu hnút í listanum til að benda á.

132
00:05:22,390 --> 00:05:26,590
Það er gott að alltaf að halda næstu músina þau síðast Hnútur er frumstilla að null

133
00:05:26,590 --> 00:05:30,800
að hafa staðlað eign sem tónar okkur þegar við höfum náð að listanum er lokið.

134
00:05:30,800 --> 00:05:33,510
>> Svo, ef vefskriðillinn → Næst er núll,

135
00:05:34,120 --> 00:05:38,270
muna að örin setningafræði er flýtileið fyrir dereferencing

136
00:05:38,270 --> 00:05:40,010
bendi til strúktúr, þá aðgang

137
00:05:40,010 --> 00:05:42,510
næsta reit hennar jafngildir óþægilega:

138
00:05:42,510 --> 00:05:48,750
(* Beltum). Næst.

139
00:05:49,820 --> 00:05:51,260
Þegar við höfum fundið síðustu hnút,

140
00:05:51,260 --> 00:05:53,830
við viljum prenta vefskriðillinn → Val,

141
00:05:53,830 --> 00:05:55,000
gildi í núverandi hnút

142
00:05:55,000 --> 00:05:57,130
sem við vitum er það síðasta.

143
00:05:57,130 --> 00:05:59,740
Annars, ef við erum ekki enn á síðasta hnút í skránni,

144
00:05:59,740 --> 00:06:02,340
við verðum að fara í næsta hnút á listanum

145
00:06:02,340 --> 00:06:04,750
og athuga hvort það er sá síðasti.

146
00:06:04,750 --> 00:06:07,010
Til að gera þetta, setjum bara vefskriðillinn músina okkar

147
00:06:07,010 --> 00:06:09,840
að benda á næsta gildi núverandi hnút á,

148
00:06:09,840 --> 00:06:11,680
það er næsta hnút á listanum.

149
00:06:11,680 --> 00:06:13,030
Þetta er gert með því að setja

150
00:06:13,030 --> 00:06:15,280
vefskriðillinn = vefskriðillinn → næst.

151
00:06:16,050 --> 00:06:18,960
Þá erum við að endurtaka þetta ferli, með lykkju til dæmis,

152
00:06:18,960 --> 00:06:20,960
þar er að finna síðasta hnút.

153
00:06:20,960 --> 00:06:23,150
Svo, til dæmis, ef vefskriðillinn var að benda á höfuð,

154
00:06:24,050 --> 00:06:27,710
við setjum vefskriðillinn að benda á vefskriðillinn → næst,

155
00:06:27,710 --> 00:06:30,960
sem er það sama og næsta sviði 1. hnút.

156
00:06:30,960 --> 00:06:33,620
Svo, nú vefskriðillinn okkar bendir til 2. hnút,

157
00:06:33,620 --> 00:06:35,480
og aftur, endurtaka við þetta með lykkju

158
00:06:37,220 --> 00:06:40,610
fyrr en við höfum fundið síðustu hnút, það er,

159
00:06:40,610 --> 00:06:43,640
þar næsta músina hnúturinn er benda null.

160
00:06:43,640 --> 00:06:45,070
Og þar sem við höfum það,

161
00:06:45,070 --> 00:06:47,620
Við höfum fundið síðustu hnút í listanum, og að prenta gildi þess,

162
00:06:47,620 --> 00:06:50,800
við notum bara vefskriðillinn → Val.

163
00:06:50,800 --> 00:06:53,130
>> Fara yfir er ekki svo slæmt, en hvað um að setja?

164
00:06:53,130 --> 00:06:56,290
Lets segja að við viljum að setja heiltala í 4. stöðu

165
00:06:56,290 --> 00:06:58,040
í heiltölu lista.

166
00:06:58,040 --> 00:07:01,280
Það er á milli núverandi 3. og 4. hnúður.

167
00:07:01,280 --> 00:07:03,760
Aftur verðum við að fara yfir lista bara til

168
00:07:03,760 --> 00:07:06,520
fá til 3. þáttur, sá sem við erum að setja eftir.

169
00:07:06,520 --> 00:07:09,300
Svo búum við til vefskriðillinn músina aftur til að fara yfir listann

170
00:07:09,300 --> 00:07:11,400
athuga hvort höfuð músina okkar er núll,

171
00:07:11,400 --> 00:07:14,810
og ef það er ekki, benda vefskriðillinn músina okkar á höfuð hnút.

172
00:07:16,880 --> 00:07:18,060
Svo erum við á 1. frumefni.

173
00:07:18,060 --> 00:07:21,020
Við verðum að fara fram 2 fleiri atriði áður en við getum sett,

174
00:07:21,020 --> 00:07:23,390
þannig að við getum notað til að lykkja

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

176
00:07:26,430 --> 00:07:28,590
og í hverri ítrun í lykkju,

177
00:07:28,590 --> 00:07:31,540
fara vefskriðillinn músina okkar fram um 1 hnútur

178
00:07:31,540 --> 00:07:34,570
með því að athuga hvort næsta reit núverandi Hnútur er núll,

179
00:07:34,570 --> 00:07:37,550
og ef það er ekki, færa vefskriðillinn bendilinn okkar á næsta hnút

180
00:07:37,550 --> 00:07:41,810
því að setja það jafn næstu músina núverandi hnút á.

181
00:07:41,810 --> 00:07:45,210
Svo, þar til lykkja okkar segir að gera það

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

183
00:07:49,610 --> 00:07:51,190
við höfum náð 3. hnút,

184
00:07:51,190 --> 00:07:53,110
og þegar vefskriðillinn músina okkar hefur náð hnút eftir

185
00:07:53,110 --> 00:07:55,270
sem við viljum setja inn nýja heiltölu okkar,

186
00:07:55,270 --> 00:07:57,050
hvernig við raunverulega gera the setja?

187
00:07:57,050 --> 00:07:59,440
>> Jæja, nýja heiltölu okkar þarf að vera sett inn í listann

188
00:07:59,440 --> 00:08:01,250
sem hluta af eigin hnút struct þess,

189
00:08:01,250 --> 00:08:03,140
þar sem þetta er í raun röð hnúta.

190
00:08:03,140 --> 00:08:05,690
Svo, við skulum gera nýja bendi til hnút

191
00:08:05,690 --> 00:08:08,910
kallað new_node, '

192
00:08:08,910 --> 00:08:11,800
og setja það til að benda á minni sem við úthluta nú

193
00:08:11,800 --> 00:08:14,270
á hrúga fyrir hnút sig,

194
00:08:14,270 --> 00:08:16,000
og hversu mikið minni þurfum við að úthluta?

195
00:08:16,000 --> 00:08:18,250
Jæja, á stærð við hnút,

196
00:08:20,450 --> 00:08:23,410
og við viljum að setja Val á sínu sviði á heiltölu sem við viljum setja inn.

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

198
00:08:25,590 --> 00:08:27,710
Nú, hnúturinn inniheldur heiltölu gildi okkar.

199
00:08:27,710 --> 00:08:30,650
Það er líka góð regla að frumstilla næsta reit nýju hnút á

200
00:08:30,650 --> 00:08:33,690
að benda á núll,

201
00:08:33,690 --> 00:08:35,080
en nú hvað?

202
00:08:35,080 --> 00:08:37,179
>> Við verðum að breyta innra skipulagi á listanum

203
00:08:37,179 --> 00:08:40,409
og næstu ábendingum að finna í núverandi lista er

204
00:08:40,409 --> 00:08:42,950
3 og 4 hnútar.

205
00:08:42,950 --> 00:08:46,560
Þar næstu ábendingum ákvarða röð á listanum,

206
00:08:46,560 --> 00:08:48,650
og þar sem við erum að setja nýjan hnút okkar

207
00:08:48,650 --> 00:08:50,510
réttur í the miðja af the listi,

208
00:08:50,510 --> 00:08:52,010
það geta vera a hluti erfiður.

209
00:08:52,010 --> 00:08:54,250
Þetta er vegna þess að muna, tölva okkar

210
00:08:54,250 --> 00:08:56,250
bara veit hvar hnúta á lista

211
00:08:56,250 --> 00:09:00,400
vegna næstu ábendingum geymdar í fyrri hnúður.

212
00:09:00,400 --> 00:09:03,940
Svo ef við misstum alltaf utan um eitthvað af þessum stöðum,

213
00:09:03,940 --> 00:09:06,860
segja með því að breyta einu af næstu ábendingum á listanum okkar,

214
00:09:06,860 --> 00:09:09,880
til dæmis, segjum við breytt

215
00:09:09,880 --> 00:09:12,920
Næst á 3 Hnútur er sviði

216
00:09:12,920 --> 00:09:15,610
að benda á einhvern hnút hérna.

217
00:09:15,610 --> 00:09:17,920
Við myndum vera út af heppni, því við myndum ekki

218
00:09:17,920 --> 00:09:20,940
hafa allir hugmynd um hvar á að finna afganginn af listanum,

219
00:09:20,940 --> 00:09:23,070
og það er augljóslega mjög slæmt.

220
00:09:23,070 --> 00:09:25,080
Svo verðum við að vera mjög varkár um röð

221
00:09:25,080 --> 00:09:28,360
þar sem við stjórna næsta ábendingum okkar við innsetningu.

222
00:09:28,360 --> 00:09:30,540
>> Svo, til að einfalda þetta, skulum segja að

223
00:09:30,540 --> 00:09:32,220
okkar fyrstu 4 hnúður

224
00:09:32,220 --> 00:09:36,200
eru kallaðir A, B, C og D, með örvarnar tákna keðju ábendingum

225
00:09:36,200 --> 00:09:38,070
að tengja hnúður.

226
00:09:38,070 --> 00:09:40,050
Svo þurfum við að setja inn nýjan hnút okkar

227
00:09:40,050 --> 00:09:42,070
á milli hnúður C og D.

228
00:09:42,070 --> 00:09:45,060
Það er mikilvægt að gera það í réttri röð, og ég mun sýna þér hvers vegna.

229
00:09:45,060 --> 00:09:47,500
>> Við skulum líta á rangan hátt til að gera það fyrst.

230
00:09:47,500 --> 00:09:49,490
Hey, við vitum að nýr hnútur hefur að koma rétt eftir C,

231
00:09:49,490 --> 00:09:51,910
þannig að við skulum setja næstu músina c er

232
00:09:51,910 --> 00:09:54,700
að benda á new_node.

233
00:09:56,530 --> 00:09:59,180
Allt í lagi, virðist allt í lagi, höfum við bara að klára allt núna með

234
00:09:59,180 --> 00:10:01,580
gerð næstu músina nýja Hnútur er benda til D,

235
00:10:01,580 --> 00:10:03,250
En bíddu, hvernig getum við gert það?

236
00:10:03,250 --> 00:10:05,170
Það eina sem gæti sagt okkur hvar D var,

237
00:10:05,170 --> 00:10:07,630
var næsta bendill geymd áður í C,

238
00:10:07,630 --> 00:10:09,870
en við rewrote bara að bendi

239
00:10:09,870 --> 00:10:11,170
til að benda á nýjan hnút,

240
00:10:11,170 --> 00:10:14,230
þannig að við höfum ekki lengur neina vísbendingu hvar D er í minni,

241
00:10:14,230 --> 00:10:17,020
og við höfum misst restina af listanum.

242
00:10:17,020 --> 00:10:19,000
Ekki góður yfirleitt.

243
00:10:19,000 --> 00:10:21,090
>> Svo, hvernig við gerum þetta rétt?

244
00:10:22,360 --> 00:10:25,090
Fyrst, benda næstu músina nýja Hnútur er í D.

245
00:10:26,170 --> 00:10:28,990
Nú, bæði nýja hnút og er C næstu ábendingum

246
00:10:28,990 --> 00:10:30,660
vísi til sömu hnút, D,

247
00:10:30,660 --> 00:10:32,290
en það er allt í lagi.

248
00:10:32,290 --> 00:10:35,680
Nú getum við benda næstu músina c er í nýjan hnút.

249
00:10:37,450 --> 00:10:39,670
Svo höfum við gert þetta án þess að tapa neinum gögnum.

250
00:10:39,670 --> 00:10:42,280
Í kóða, C er núverandi hnút

251
00:10:42,280 --> 00:10:45,540
að traversal bendilinn Skrið bendir til,

252
00:10:45,540 --> 00:10:50,400
og D er táknað með hnút bent á næsta reit núverandi hnút á,

253
00:10:50,400 --> 00:10:52,600
eða vefskriðillinn → næst.

254
00:10:52,600 --> 00:10:55,460
Svo fórum við fyrst næstu músina í nýjan hnút á

255
00:10:55,460 --> 00:10:57,370
að benda á vefskriðillinn → næst,

256
00:10:57,370 --> 00:11:00,880
á sama hátt og við sögðum næsta músina new_node er ætti

257
00:11:00,880 --> 00:11:02,780
benda til D á myndinni.

258
00:11:02,780 --> 00:11:04,540
Þá getum við sett næstu músina núverandi hnút á

259
00:11:04,540 --> 00:11:06,330
að nýja hnút okkar,

260
00:11:06,330 --> 00:11:10,980
alveg eins og við þurftum að bíða til að benda C til new_node á teikningunni.

261
00:11:10,980 --> 00:11:12,250
Nú er allt í röð og við ekki missa

262
00:11:12,250 --> 00:11:14,490
utan um öll gögn, og við gátum bara

263
00:11:14,490 --> 00:11:16,200
stafur nýjan hnút okkar í the miðja af the listi

264
00:11:16,200 --> 00:11:19,330
án þess að byggja upp allt hlutur eða jafnvel að breytast hvaða þætti

265
00:11:19,330 --> 00:11:22,490
hvernig við hefðum þurft að með fasta lengd fylkisins.

266
00:11:22,490 --> 00:11:26,020
>> Svo eru tengdir listar undirstöðu, en mikilvægt, dynamic gögn uppbygging

267
00:11:26,020 --> 00:11:29,080
sem hafa bæði kosti og galla

268
00:11:29,080 --> 00:11:31,260
miðað við fylki og önnur gögn uppbygging,

269
00:11:31,260 --> 00:11:33,350
og eins og oft er raunin í tölvunarfræði,

270
00:11:33,350 --> 00:11:35,640
það er mikilvægt að vita hvenær á að nota hvert tól,

271
00:11:35,640 --> 00:11:37,960
svo er hægt að velja rétt tól til hægri starf.

272
00:11:37,960 --> 00:11:40,060
>> Fyrir frekari starfi, reyna að skrifa aðgerðir til

273
00:11:40,060 --> 00:11:42,080
eyða hnúður úr tengda listanum -

274
00:11:42,080 --> 00:11:44,050
Mundu að vera varkár óður í þeirri röð sem þú endurraða

275
00:11:44,050 --> 00:11:47,430
næstu ábendingum þínum til að tryggja að þú missir ekki klumpur af listanum -

276
00:11:47,430 --> 00:11:50,200
eða fall til að telja hnúta í tengda listanum,

277
00:11:50,200 --> 00:11:53,280
eða skemmtilegt, til að snúa röð öllum hnúður í tengda listanum.

278
00:11:53,280 --> 00:11:56,090
>> Ég heiti Jackson Steinkamp, ​​þetta er CS50.