1
00:00:07,260 --> 00:00:10,050
[Powered by Google Translate] Në programimin, ne shpesh duhet të paraqesin listat e vlerave,

2
00:00:10,050 --> 00:00:12,840
të tilla si emrat e nxënësve në një seksion

3
00:00:12,840 --> 00:00:15,100
ose rezultatet e tyre në quiz fundit.

4
00:00:15,100 --> 00:00:17,430
>> Në gjuhën C, ka deklaruar vargjeve mund të përdoren

5
00:00:17,430 --> 00:00:19,160
për të ruajtur listat.

6
00:00:19,160 --> 00:00:21,200
Është e lehtë të numëroj elementet e një liste

7
00:00:21,200 --> 00:00:23,390
ruhen në një grup, dhe nëse keni nevojë për të hyrë në

8
00:00:23,390 --> 00:00:25,050
ose modifikojë elementin ith listës

9
00:00:25,050 --> 00:00:27,570
për disa indeksin arbitrare unë,

10
00:00:27,570 --> 00:00:29,910
që mund të bëhet në kohë të vazhdueshme,

11
00:00:29,910 --> 00:00:31,660
por vargjeve kanë disavantazhe, too.

12
00:00:31,660 --> 00:00:33,850
>> Kur ne deklarojnë ata, ne jemi duke kërkuar për të thënë

13
00:00:33,850 --> 00:00:35,900
deri para sa e madhe ato janë,

14
00:00:35,900 --> 00:00:38,160
që është, se sa elementet që mund të ruajë

15
00:00:38,160 --> 00:00:40,780
dhe sa e madhe këto elemente janë, që përcaktohet nga lloji i tyre.

16
00:00:40,780 --> 00:00:45,450
Për shembull, int arr (10)

17
00:00:45,450 --> 00:00:48,220
mund të ruajë 10 artikuj

18
00:00:48,220 --> 00:00:50,200
që janë madhësia e një int.

19
00:00:50,200 --> 00:00:52,590
>> Ne nuk mund të ndryshojë madhësinë e një sërë pas shpalljes.

20
00:00:52,590 --> 00:00:55,290
Ne kemi për të bërë një rrjet të ri, nëse duam të ruajtur më shumë elemente.

21
00:00:55,290 --> 00:00:57,410
Arsyeja e kësaj është se ekziston kufizim tonë

22
00:00:57,410 --> 00:00:59,040
Programi i ruan tërë array

23
00:00:59,040 --> 00:01:02,310
si një copë puqur të kujtesës.

24
00:01:02,310 --> 00:01:04,500
Thonë se kjo është tampon ku ne të ruhet në rrjet tonë.

25
00:01:04,500 --> 00:01:06,910
Nuk mund të jetë variablave të tjera

26
00:01:06,910 --> 00:01:08,310
e vendosur të drejtë tjetër në grup

27
00:01:08,310 --> 00:01:10,060
në kujtesën, kështu që ne nuk mund të

28
00:01:10,060 --> 00:01:12,060
vetëm të bëjë array mëdha.

29
00:01:12,060 --> 00:01:15,700
>> Ndonjëherë ne do të donim për të tregtuar shpejtësi të shpejtë grup të dhënat e qasjes

30
00:01:15,700 --> 00:01:17,650
për një fleksibilitet pak më shumë.

31
00:01:17,650 --> 00:01:20,380
Të hyjë në listën e lidhur, një tjetër strukturë themelore të dhënave

32
00:01:20,380 --> 00:01:22,360
ju nuk mund të jetë aq i njohur me të.

33
00:01:22,360 --> 00:01:24,200
Në një nivel të lartë,

34
00:01:24,200 --> 00:01:26,840
një listë e lidhur ruan të dhënat në një sekuencë të nyjave

35
00:01:26,840 --> 00:01:29,280
që janë të lidhura me njëri-tjetrin me lidhje,

36
00:01:29,280 --> 00:01:31,760
prandaj 'lista e lidhur. "emër

37
00:01:31,760 --> 00:01:33,840
Siç do të shohim, ky ndryshim në dizajn

38
00:01:33,840 --> 00:01:35,500
çon në avantazhet dhe disavantazhet ndryshme

39
00:01:35,500 --> 00:01:37,000
se një grup.

40
00:01:37,000 --> 00:01:39,840
>> Ja disa kodi C për një listë shumë të thjeshtë të lidhur integers.

41
00:01:39,840 --> 00:01:42,190
Ju mund të shihni se ne kemi përfaqësuar çdo nyje

42
00:01:42,190 --> 00:01:45,520
në listën si një struct e cila përmban 2 gjëra,

43
00:01:45,520 --> 00:01:47,280
një numër të plotë për të ruajtur quajtur 'val'

44
00:01:47,280 --> 00:01:50,460
dhe një lidhje me nyje e ardhshme në listë

45
00:01:50,460 --> 00:01:52,990
që ne përfaqësojmë si një tregues të quajtur "tjetër."

46
00:01:54,120 --> 00:01:56,780
Në këtë mënyrë, ne mund të gjetur të gjithë listën

47
00:01:56,780 --> 00:01:58,790
me vetëm një të vetme treguesin në nyje 1,

48
00:01:58,790 --> 00:02:01,270
dhe pastaj ne mund të ndiqni pointers ardhshme

49
00:02:01,270 --> 00:02:03,130
në nyje 2,

50
00:02:03,130 --> 00:02:05,280
tek nyjes 3,

51
00:02:05,280 --> 00:02:07,000
në nyje 4,

52
00:02:07,000 --> 00:02:09,889
dhe kështu me radhë, deri sa të kemi në fund të listës.

53
00:02:10,520 --> 00:02:12,210
>> Ju mund të jetë në gjendje për të parë 1 përfituar kjo ka

54
00:02:12,210 --> 00:02:14,490
mbi strukturën statike array - me një listë të lidhura,

55
00:02:14,490 --> 00:02:16,450
ne nuk kemi nevojë për një copë të madhe të kujtesës krejt.

56
00:02:17,400 --> 00:02:20,530
1 në nyje e listës mund të jetojnë në këtë vend në kujtesë,

57
00:02:20,530 --> 00:02:23,160
dhe nyja 2 mund të jetë gjatë gjithë rrugës mbi këtu.

58
00:02:23,160 --> 00:02:25,780
Ne mund të merrni të gjitha nyjet ska rëndësi se ku në kujtesën ata janë,

59
00:02:25,780 --> 00:02:28,890
sepse duke filluar në nyje 1, treguesin e ardhshëm çdo nyje e

60
00:02:28,890 --> 00:02:31,700
na tregon saktësisht se ku të shkojnë tjetër.

61
00:02:31,700 --> 00:02:33,670
>> Përveç kësaj, ne nuk kemi për të thënë që në fillim

62
00:02:33,670 --> 00:02:36,740
sa i madh një listë e lidhur do të jetë mënyra që ne bëjmë me të vargjeve statike,

63
00:02:36,740 --> 00:02:39,060
që ne mund të vazhdojmë duke shtuar nyje në një listë

64
00:02:39,060 --> 00:02:42,600
për aq kohë sa nuk ka hapësirë ​​diku në kujtesë për nyjet reja.

65
00:02:42,600 --> 00:02:45,370
Prandaj, listat e lidhura janë të lehtë për të resize dinamike.

66
00:02:45,370 --> 00:02:47,950
Thuaj, më vonë në program ne kemi nevojë për të shtuar nyje më shumë

67
00:02:47,950 --> 00:02:49,350
në listën tonë.

68
00:02:49,350 --> 00:02:51,480
Për të futur një nyje të re në listën tonë të fluturojnë,

69
00:02:51,480 --> 00:02:53,740
të gjithë ne duhet të bëni është të siguroj kujtesë për atë nyje,

70
00:02:53,740 --> 00:02:55,630
pllum në vlerën e të dhënave,

71
00:02:55,630 --> 00:02:59,070
dhe pastaj të vendosni atë ku ne duam duke rregulluar pointers duhura.

72
00:02:59,070 --> 00:03:02,310
>> Për shembull, në qoftë se kemi dashur të zhvillohet një nyje në mes

73
00:03:02,310 --> 00:03:04,020
nyjet 2 dhe 3 të listës,

74
00:03:04,020 --> 00:03:06,800
 ne nuk do të duhet të lëvizin nyjet 2 apo 3 në të gjitha.

75
00:03:06,800 --> 00:03:09,190
Thonë se ne jemi futur këtë nyje të kuqe.

76
00:03:09,190 --> 00:03:12,890
Të gjithë ne do të duhet të bëni është vendosur treguesin tjetër nyjen ri

77
00:03:12,890 --> 00:03:14,870
për pikë në nyjen 3

78
00:03:14,870 --> 00:03:18,580
dhe pastaj rewire treguesin tjetër nyjen e 2

79
00:03:18,580 --> 00:03:20,980
për pikë në nyje tonë të ri.

80
00:03:22,340 --> 00:03:24,370
Pra, ne mund të resize listat tona të fluturojnë

81
00:03:24,370 --> 00:03:26,090
që nga kompjuteri ynë nuk mbështetet në indeksim,

82
00:03:26,090 --> 00:03:28,990
por më tepër për lidhjen duke përdorur pointers për të ruajtur ato.

83
00:03:29,120 --> 00:03:31,600
>> Listat e megjithatë, një dëm të lidhur

84
00:03:31,600 --> 00:03:33,370
është se, ndryshe nga një grup statike,

85
00:03:33,370 --> 00:03:36,690
kompjuteri nuk mund të hidhen në mes të listës.

86
00:03:38,040 --> 00:03:40,780
Që kompjuter ka për të vizituar çdo nyje në listën lidhur

87
00:03:40,780 --> 00:03:42,330
për të shkuar në një tjetër,

88
00:03:42,330 --> 00:03:44,770
ajo do të marrë më të gjatë për të gjetur një nyje të veçantë

89
00:03:44,770 --> 00:03:46,400
se ajo do të në një rrjet.

90
00:03:46,400 --> 00:03:48,660
Të kaloj gjithë listën merr kohë proporcional

91
00:03:48,660 --> 00:03:50,580
në gjatësinë e lista,

92
00:03:50,580 --> 00:03:54,630
ose O (n) në simbol asymptotic.

93
00:03:54,630 --> 00:03:56,510
Në mesatare, duke arritur ndonjë nyje

94
00:03:56,510 --> 00:03:58,800
gjithashtu merr kohë proporcionale me n.

95
00:03:58,800 --> 00:04:00,700
>> Tani, le të vërtetë shkruani disa kodin

96
00:04:00,700 --> 00:04:02,000
që punon me listat e lidhura.

97
00:04:02,000 --> 00:04:04,220
Le të thonë se ne duam një listë e lidhur e integers.

98
00:04:04,220 --> 00:04:06,140
Ne mund të përfaqësojnë një nyje në listën tonë përsëri

99
00:04:06,140 --> 00:04:08,340
si një struct me 2 fusha,

100
00:04:08,340 --> 00:04:10,750
një vlerë e plotë quajtur 'val'

101
00:04:10,750 --> 00:04:13,490
dhe një tregues tjetër për nyjen e ardhshëm të listës.

102
00:04:13,490 --> 00:04:15,660
E pra, duket mjaft e thjeshtë.

103
00:04:15,660 --> 00:04:17,220
>> Le të thonë se ne duam të shkruani një funksion

104
00:04:17,220 --> 00:04:19,329
e cila përshkon listës dhe printime nga

105
00:04:19,329 --> 00:04:22,150
vlera ruhen në nyjen e fundit të listës.

106
00:04:22,150 --> 00:04:24,850
E pra, që do të thotë që ne do të duhet të kaloj nëpër të gjitha nyjet në listë

107
00:04:24,850 --> 00:04:27,310
për të gjetur një të fundit, por që ne nuk jemi duke shtuar

108
00:04:27,310 --> 00:04:29,250
ose fshirjes asgjë, ne nuk duam të ndryshojmë

109
00:04:29,250 --> 00:04:32,210
Struktura e brendshme e pointers ardhshme në listë.

110
00:04:32,210 --> 00:04:34,790
>> Pra, ne do të duhet një tregues veçanërisht për traversal

111
00:04:34,790 --> 00:04:36,940
të cilat ne do të thërrasë "servil".

112
00:04:36,940 --> 00:04:38,870
Ajo do të zvarritem nëpër të gjitha elementet e listës

113
00:04:38,870 --> 00:04:41,190
duke ndjekur zinxhirin e pointers ardhshme.

114
00:04:41,190 --> 00:04:43,750
Të gjithë ne kemi ruajtur është një tregues për nyjen 1,

115
00:04:43,750 --> 00:04:45,730
ose 'kokë' i lista.

116
00:04:45,730 --> 00:04:47,370
Points kreu në nyjen 1.

117
00:04:47,370 --> 00:04:49,120
Kjo është e tipit pointer-to-node.

118
00:04:49,120 --> 00:04:51,280
>> Për të marrë aktuale nyje 1 në listë,

119
00:04:51,280 --> 00:04:53,250
ne duhet të dereference këtë tregues,

120
00:04:53,250 --> 00:04:55,100
por para se ne mund të dereference atë, ne duhet të kontrolloni

121
00:04:55,100 --> 00:04:57,180
nëse kursori është i pavlefshëm parë.

122
00:04:57,180 --> 00:04:59,190
Nëse kjo është null, lista është e zbrazët,

123
00:04:59,190 --> 00:05:01,320
dhe ne duhet të shtypura nga një mesazh që, për shkak se lista është e zbrazët,

124
00:05:01,320 --> 00:05:03,250
nuk ka nyje fundit.

125
00:05:03,250 --> 00:05:05,190
Por, le të thonë se lista nuk është e zbrazët.

126
00:05:05,190 --> 00:05:08,340
Nëse nuk është, atëherë ne duhet të zvarritem nëpër gjithë listën

127
00:05:08,340 --> 00:05:10,440
deri sa të kemi në nyjen e fundit të listës,

128
00:05:10,440 --> 00:05:13,030
dhe se si mund të them nëse ne jemi duke kërkuar në nyjen e fundit në listë?

129
00:05:13,670 --> 00:05:16,660
>> E pra, në qoftë se një nyje tjetër tregues është null,

130
00:05:16,660 --> 00:05:18,320
ne e dimë se ne jemi në fund

131
00:05:18,320 --> 00:05:22,390
pasi treguesin fundit ardhshme nuk do të ketë nyje tjetër në listë për pikë për të.

132
00:05:22,390 --> 00:05:26,590
Është praktikë e mirë që gjithmonë të mbajnë treguesin e ardhshëm nyja kaluar initialized to null

133
00:05:26,590 --> 00:05:30,800
të ketë një pronë të standardizuar e cila na paralajmëron kur ne kemi arritur në fund të listës.

134
00:05:30,800 --> 00:05:33,510
>> Pra, në qoftë servil → tjetër është null,

135
00:05:34,120 --> 00:05:38,270
mos harroni se sintaksa shigjetë është një shkurtore për dereferencing

136
00:05:38,270 --> 00:05:40,010
një tregues për një struct, pastaj qasja në

137
00:05:40,010 --> 00:05:42,510
Fusha e saj e ardhshme ekuivalente të vështirë:

138
00:05:42,510 --> 00:05:48,750
(* Servil). Ardhshëm.

139
00:05:49,820 --> 00:05:51,260
Pasi ne kemi gjetur nyjen e fundit,

140
00:05:51,260 --> 00:05:53,830
ne duam të shtypura servil → Val,

141
00:05:53,830 --> 00:05:55,000
vlera në nyjen e tanishme

142
00:05:55,000 --> 00:05:57,130
të cilën ne e dimë është e fundit.

143
00:05:57,130 --> 00:05:59,740
Përndryshe, në qoftë se ne nuk jemi ende në nyjen e fundit në listë,

144
00:05:59,740 --> 00:06:02,340
ne duhet të lëvizin për në nyjen e ardhshëm në listë

145
00:06:02,340 --> 00:06:04,750
dhe kontrolloni nëse kjo është e fundit.

146
00:06:04,750 --> 00:06:07,010
Për ta bërë këtë, ne vetëm vënë treguesin tonë servil

147
00:06:07,010 --> 00:06:09,840
të tregojnë për vlerën e ardhshëm nyjen aktual,

148
00:06:09,840 --> 00:06:11,680
që është, nyje tjetër në lista.

149
00:06:11,680 --> 00:06:13,030
Kjo është bërë duke

150
00:06:13,030 --> 00:06:15,280
servil servil = → ardhshëm.

151
00:06:16,050 --> 00:06:18,960
Pastaj ne përsëris këtë proces, me një lak për shembull,

152
00:06:18,960 --> 00:06:20,960
derisa kemi gjetur nyjen e fundit.

153
00:06:20,960 --> 00:06:23,150
Kështu, për shembull, në qoftë servil u treguar kokë,

154
00:06:24,050 --> 00:06:27,710
ne kemi vendosur servil për pikë në servil → ardhshëm,

155
00:06:27,710 --> 00:06:30,960
e cila është e njëjtë si fusha e ardhshëm të nyjen 1.

156
00:06:30,960 --> 00:06:33,620
Pra, tani servil jonë është vënë në nyjen 2,

157
00:06:33,620 --> 00:06:35,480
dhe, përsëri, ne përsëris këtë me një lak,

158
00:06:37,220 --> 00:06:40,610
deri sa ne kemi gjetur nyjen e fundit, që është,

159
00:06:40,610 --> 00:06:43,640
ku treguesin e ardhshëm nyja është duke treguar null.

160
00:06:43,640 --> 00:06:45,070
Dhe nuk kemi atë,

161
00:06:45,070 --> 00:06:47,620
ne kemi gjetur nyja e fundit në listë, dhe për të shtypur vlerën e saj,

162
00:06:47,620 --> 00:06:50,800
ne vetëm përdorni servil → Val.

163
00:06:50,800 --> 00:06:53,130
>> Traversing nuk është aq e keqe, por çfarë lidhje futur?

164
00:06:53,130 --> 00:06:56,290
Lejon të thonë se ne duam të futur një numër të plotë në pozitën e 4

165
00:06:56,290 --> 00:06:58,040
në një listë integer.

166
00:06:58,040 --> 00:07:01,280
Kjo është në mes të nyjeve aktuale të 3 dhe 4.

167
00:07:01,280 --> 00:07:03,760
Përsëri, ne duhet të kaloj nëpër listën e vetëm për

168
00:07:03,760 --> 00:07:06,520
marrë në elementin 3, në një ne jemi duke futur pas.

169
00:07:06,520 --> 00:07:09,300
Pra, ne kemi krijuar një tregues servil përsëri të kaloj nëpër lista,

170
00:07:09,300 --> 00:07:11,400
kontrolloni nëse akrep tonë kokë është i pavlefshëm,

171
00:07:11,400 --> 00:07:14,810
dhe në qoftë se kjo nuk është, pikë treguesin tonë servil në nyjen qendrore.

172
00:07:16,880 --> 00:07:18,060
Pra, ne jemi në elementin 1.

173
00:07:18,060 --> 00:07:21,020
Ne duhet të shkojmë përpara 2 elemente më shumë para se ne mund të futni,

174
00:07:21,020 --> 00:07:23,390
kështu që ne mund të përdorni një për lak

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

176
00:07:26,430 --> 00:07:28,590
dhe në çdo ripërsëritje e lak,

177
00:07:28,590 --> 00:07:31,540
avancimin treguesin tonë servil përpara nga 1 nyjë

178
00:07:31,540 --> 00:07:34,570
duke kontrolluar nëse fusha e ardhshëm nyja aktual është i pavlefshëm,

179
00:07:34,570 --> 00:07:37,550
dhe në qoftë se kjo nuk është, lëvizin kursorin tonë servil në nyjen e ardhshëm

180
00:07:37,550 --> 00:07:41,810
duke vendosur atë të barabartë me treguesin e ardhshëm nyjen aktual.

181
00:07:41,810 --> 00:07:45,210
Pra, pasi lak thotë tonë për të bërë këtë

182
00:07:45,210 --> 00:07:47,550
dy herë,

183
00:07:49,610 --> 00:07:51,190
ne kemi arritur nyjen 3,

184
00:07:51,190 --> 00:07:53,110
dhe një herë treguesin jonë servil ka arritur nyjen pas

185
00:07:53,110 --> 00:07:55,270
të cilat ne duam të futur tonë të ri numër i plotë,

186
00:07:55,270 --> 00:07:57,050
si nuk kemi të vërtetë të bëjë të futur?

187
00:07:57,050 --> 00:07:59,440
>> E pra, integer tonë të ri duhet të futet në listën e

188
00:07:59,440 --> 00:08:01,250
si pjesë e struct vet nyjeve,

189
00:08:01,250 --> 00:08:03,140
pasi kjo është me të vërtetë një sekuencë e nyjeve.

190
00:08:03,140 --> 00:08:05,690
Pra, le të bëjë një tregues të ri për nyje

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

192
00:08:08,910 --> 00:08:11,800
dhe e vendosi atë në pikë të kujtesës që ne tani ndajë

193
00:08:11,800 --> 00:08:14,270
në grumbull për nyjen vetë,

194
00:08:14,270 --> 00:08:16,000
dhe sa memorie nuk kemi nevojë të ndajë?

195
00:08:16,000 --> 00:08:18,250
E pra, përmasat e një nyje,

196
00:08:20,450 --> 00:08:23,410
dhe ne duam të vendosur fushën e tij val me numër të plotë që ne duam të futur.

197
00:08:23,410 --> 00:08:25,590
Le të themi, 6.

198
00:08:25,590 --> 00:08:27,710
Tani, nyja përmban vlerën tonë numer i plote.

199
00:08:27,710 --> 00:08:30,650
Është gjithashtu një praktikë e mirë për të nisja fushë tjetër nyjen ri

200
00:08:30,650 --> 00:08:33,690
për pikë të pavlefshëm,

201
00:08:33,690 --> 00:08:35,080
por tani çfarë?

202
00:08:35,080 --> 00:08:37,179
>> Ne kemi për të ndryshuar strukturën e brendshme të listës

203
00:08:37,179 --> 00:08:40,409
dhe pointers ardhshme të përfshira në listën ekzistuese të

204
00:08:40,409 --> 00:08:42,950
Nyjet 3 dhe 4.

205
00:08:42,950 --> 00:08:46,560
Që pointers ardhshme përcaktuar rendin e listës,

206
00:08:46,560 --> 00:08:48,650
dhe që ne jemi futur nyje tonë të re

207
00:08:48,650 --> 00:08:50,510
drejtë në mes të listës,

208
00:08:50,510 --> 00:08:52,010
ajo mund të jetë pak i ndërlikuar.

209
00:08:52,010 --> 00:08:54,250
Kjo është për shkak se, mos harroni, kompjuteri ynë

210
00:08:54,250 --> 00:08:56,250
vetëm e di vendndodhjen e nyjeve në listën

211
00:08:56,250 --> 00:09:00,400
për shkak të pointers ardhshme depozituara në nyjet e mëparshme.

212
00:09:00,400 --> 00:09:03,940
Pra, në qoftë se ne ndonjëherë humbur gjurmët e ndonjë nga këto vende,

213
00:09:03,940 --> 00:09:06,860
thonë se duke ndryshuar një nga pointers ardhshme në listën tonë,

214
00:09:06,860 --> 00:09:09,880
për shembull, thonë se ne e ndryshuam

215
00:09:09,880 --> 00:09:12,920
Fusha tjetër nyjen e 3

216
00:09:12,920 --> 00:09:15,610
të tregojnë për disa nyje mbi këtu.

217
00:09:15,610 --> 00:09:17,920
Ne do të jetë e fat, sepse ne nuk do të

218
00:09:17,920 --> 00:09:20,940
keni ndonjë ide se ku mund të gjeni pjesën tjetër të listës,

219
00:09:20,940 --> 00:09:23,070
dhe kjo është padyshim me të vërtetë e keqe.

220
00:09:23,070 --> 00:09:25,080
Pra, ne duhet të jetë me të vërtetë të kujdesshëm në lidhje me urdhër

221
00:09:25,080 --> 00:09:28,360
në të cilën ne të manipuluar pointers tonë të ardhshëm gjatë futje.

222
00:09:28,360 --> 00:09:30,540
>> Pra, për të lehtësuar këtë, le të themi se

223
00:09:30,540 --> 00:09:32,220
para 4 nyjet tona

224
00:09:32,220 --> 00:09:36,200
janë quajtur A, B, C, dhe D, me shigjeta përfaqësojnë zinxhirin e pointers

225
00:09:36,200 --> 00:09:38,070
që lidhin nyjet.

226
00:09:38,070 --> 00:09:40,050
Pra, ne kemi nevojë për të futur nyje tonë të re

227
00:09:40,050 --> 00:09:42,070
në mes nyjet C dhe D.

228
00:09:42,070 --> 00:09:45,060
Është e rëndësishme për të bërë atë në mënyrë të drejtë, dhe unë do t'ju tregoj pse.

229
00:09:45,060 --> 00:09:47,500
>> Le të shikojmë në mënyrë të gabuar për ta bërë atë më parë.

230
00:09:47,500 --> 00:09:49,490
Hej, ne e dimë se nyja e re duhet të vijë menjëherë pas C,

231
00:09:49,490 --> 00:09:51,910
kështu që le të vendosur treguesin e ardhshëm C

232
00:09:51,910 --> 00:09:54,700
për pikë në new_node.

233
00:09:56,530 --> 00:09:59,180
Të gjithë të drejtë, duket në rregull, ne vetëm duhet të përfundojë deri tani nga

234
00:09:59,180 --> 00:10:01,580
bërë tjetër pikë nyjen ri akrep në D,

235
00:10:01,580 --> 00:10:03,250
Por prisni, si mund ta bëni këtë?

236
00:10:03,250 --> 00:10:05,170
E vetmja gjë që mund të na tregoni se ku D ishte,

237
00:10:05,170 --> 00:10:07,630
ishte tregues tjetër ruajtur më parë në C,

238
00:10:07,630 --> 00:10:09,870
por ne thjesht rishkroi atë treguesin

239
00:10:09,870 --> 00:10:11,170
për pikë në nyjen e re,

240
00:10:11,170 --> 00:10:14,230
kështu që ne nuk kemi asnjë ide se ku D është në kujtesë,

241
00:10:14,230 --> 00:10:17,020
dhe ne kemi humbur pjesën tjetër të listës.

242
00:10:17,020 --> 00:10:19,000
Nuk është e mirë në të gjitha.

243
00:10:19,000 --> 00:10:21,090
>> Pra, si nuk kemi të bëjmë këtë të drejtë?

244
00:10:22,360 --> 00:10:25,090
Së pari, treguesin e ardhshëm nyja ri në D.

245
00:10:26,170 --> 00:10:28,990
Tani, të dyja të reja nyje dhe e C pointers ardhshme

246
00:10:28,990 --> 00:10:30,660
janë treguar në të njëjtën nyjë, D,

247
00:10:30,660 --> 00:10:32,290
por kjo është në rregull.

248
00:10:32,290 --> 00:10:35,680
Tani ne mund të nxjerr në treguesin e ardhshëm C në nyjen e re.

249
00:10:37,450 --> 00:10:39,670
Pra, ne kemi bërë këtë pa humbur asnjë të dhënë.

250
00:10:39,670 --> 00:10:42,280
Në kodin, C është nyja e tanishme

251
00:10:42,280 --> 00:10:45,540
se treguesin traversal servil është treguar,

252
00:10:45,540 --> 00:10:50,400
dhe D është përfaqësuara nga nyje vuri tek nga fushë tjetër nyjen aktual,

253
00:10:50,400 --> 00:10:52,600
ose servil → ardhshëm.

254
00:10:52,600 --> 00:10:55,460
Pra, ne kemi parë të vendosur treguesin tjetër nyjen ri

255
00:10:55,460 --> 00:10:57,370
për pikë në servil → ardhshëm,

256
00:10:57,370 --> 00:11:00,880
njëjtën mënyrë kemi thënë tregues tjetër new_node duhet

257
00:11:00,880 --> 00:11:02,780
pikës tek D në ilustrim.

258
00:11:02,780 --> 00:11:04,540
Pastaj, ne mund të vendosni treguesin tjetër nyjen aktual

259
00:11:04,540 --> 00:11:06,330
me nyje tonë të re,

260
00:11:06,330 --> 00:11:10,980
ashtu si ne është dashur të presin në pikën C të new_node në vizatim.

261
00:11:10,980 --> 00:11:12,250
Tani çdo gjë është në rregull, dhe ne nuk kemi humbur

262
00:11:12,250 --> 00:11:14,490
gjurmët e çdo të dhëne, dhe ne kemi qenë në gjendje të vetëm

263
00:11:14,490 --> 00:11:16,200
rrinë nyje tonë të ri në mes të listës

264
00:11:16,200 --> 00:11:19,330
pa rindërtimin e gjithë gjë, ose edhe kalimi elemente

265
00:11:19,330 --> 00:11:22,490
mënyrë ne do të duhej të me një grup të caktuar gjatësi.

266
00:11:22,490 --> 00:11:26,020
>> Pra, listat e lidhura janë një bazë, por të rëndësishme, dinamike struktura të dhënat

267
00:11:26,020 --> 00:11:29,080
të cilat kanë të dy avantazhet dhe disavantazhet

268
00:11:29,080 --> 00:11:31,260
në krahasim me vargjeve dhe të dhënat e tjera të strukturave,

269
00:11:31,260 --> 00:11:33,350
dhe siç është shpesh rasti në shkenca kompjuterike,

270
00:11:33,350 --> 00:11:35,640
është e rëndësishme të dini se kur do të përdorin çdo mjet,

271
00:11:35,640 --> 00:11:37,960
kështu që ju mund të zgjidhni mjet i duhur për punën e duhur.

272
00:11:37,960 --> 00:11:40,060
>> Për më shumë praktikë, do të përpiqen për të shkruar funksionet

273
00:11:40,060 --> 00:11:42,080
fshini nyjet nga një listë e lidhur -

274
00:11:42,080 --> 00:11:44,050
mos harroni të jenë të kujdesshëm në lidhje me mënyrë në të cilën ju korrigjoj

275
00:11:44,050 --> 00:11:47,430
pointers tuaj të ardhshëm për të siguruar që ju nuk do ta humbasin një pjesë të listës suaj -

276
00:11:47,430 --> 00:11:50,200
ose një funksion për të numëruar nyjet në një listë të lidhura,

277
00:11:50,200 --> 00:11:53,280
ose një argëtim, për të ndryshuar rendin e të gjitha nyjet në një listë të lidhura.

278
00:11:53,280 --> 00:11:56,090
>> Emri im është Steinkamp Jackson, kjo është CS50.