1
00:00:07,260 --> 00:00:10,050
[Powered by Google Translate] Programmēšana, mēs bieži vien ir nepieciešams, lai pārstāvētu sarakstus vērtību,

2
00:00:10,050 --> 00:00:12,840
piemēram, tādu skolēnu vārdus sekcijā

3
00:00:12,840 --> 00:00:15,100
vai viņu rezultāti par jaunāko viktorīnas.

4
00:00:15,100 --> 00:00:17,430
>> In C valodā, paziņoja bloki var izmantot

5
00:00:17,430 --> 00:00:19,160
uzglabāt sarakstus.

6
00:00:19,160 --> 00:00:21,200
Tas ir viegli uzskaitīt elementus sarakstā

7
00:00:21,200 --> 00:00:23,390
uzglabā masīvā, un, ja jums ir nepieciešams, lai piekļūtu

8
00:00:23,390 --> 00:00:25,050
vai mainīt kārtējam saraksta elementu

9
00:00:25,050 --> 00:00:27,570
kādu patvaļīgi indekss es,

10
00:00:27,570 --> 00:00:29,910
ko var izdarīt pastāvīgu laiku,

11
00:00:29,910 --> 00:00:31,660
bet bloki ir trūkumi, too.

12
00:00:31,660 --> 00:00:33,850
>> Kad mēs tos deklarēt, mēs nepieciešams pateikt

13
00:00:33,850 --> 00:00:35,900
līdz priekšā cik lielas tās ir,

14
00:00:35,900 --> 00:00:38,160
tas ir, cik daudz elementi tās var uzglabāt

15
00:00:38,160 --> 00:00:40,780
un cik liels šie elementi ir, ko nosaka to veida.

16
00:00:40,780 --> 00:00:45,450
Piemēram, int arr (10)

17
00:00:45,450 --> 00:00:48,220
var uzglabāt 10 pozīcijas

18
00:00:48,220 --> 00:00:50,200
kas ir lielums int.

19
00:00:50,200 --> 00:00:52,590
>> Mēs nevaram izmainīt masīvs lielumu, pēc deklarācijas.

20
00:00:52,590 --> 00:00:55,290
Mums ir veikt jaunu masīvu, ja mēs vēlamies saglabāt vairāk elementus.

21
00:00:55,290 --> 00:00:57,410
Iemesls šis ierobežojums pastāv, ir, ka mūsu

22
00:00:57,410 --> 00:00:59,040
Programma saglabā visu masīvs

23
00:00:59,040 --> 00:01:02,310
kā pieguļošajā rieciens atmiņas.

24
00:01:02,310 --> 00:01:04,500
Teikt, tas ir buferi, kur mēs uzglabāt mūsu masīvā.

25
00:01:04,500 --> 00:01:06,910
Tur varētu būt citi mainīgie

26
00:01:06,910 --> 00:01:08,310
atrodas blakus masīva

27
00:01:08,310 --> 00:01:10,060
atmiņā, tāpēc mēs nevaram

28
00:01:10,060 --> 00:01:12,060
tikai padara masīvs lielāks.

29
00:01:12,060 --> 00:01:15,700
>> Dažreiz mēs gribētu tirgoties masīva s ātru datu piekļuves ātrums

30
00:01:15,700 --> 00:01:17,650
lai mazliet lielāku elastību.

31
00:01:17,650 --> 00:01:20,380
Ievadiet saistīts saraksts, cita pamata datu struktūra

32
00:01:20,380 --> 00:01:22,360
jūs varētu nebūt tik pazīstami ar.

33
00:01:22,360 --> 00:01:24,200
Augstā līmenī,

34
00:01:24,200 --> 00:01:26,840
saistīts saraksts glabā datus tādā secībā mezgliem

35
00:01:26,840 --> 00:01:29,280
kas ir saistīti viens ar otru ar saitēm,

36
00:01:29,280 --> 00:01:31,760
ceļas vārds "saistīts saraksts."

37
00:01:31,760 --> 00:01:33,840
Kā mēs redzēsim, šī atšķirība dizains

38
00:01:33,840 --> 00:01:35,500
noved pie dažādām priekšrocībām un trūkumiem

39
00:01:35,500 --> 00:01:37,000
kā masīvu.

40
00:01:37,000 --> 00:01:39,840
>> Lūk, daži c kods ļoti vienkāršu saistīts saraksts integers.

41
00:01:39,840 --> 00:01:42,190
Jūs varat redzēt, ka mēs esam pārstāvēti katrs mezgls

42
00:01:42,190 --> 00:01:45,520
sarakstā kā struct kas ir 2 lietas,

43
00:01:45,520 --> 00:01:47,280
skaitlim uzglabāt sauc par "val"

44
00:01:47,280 --> 00:01:50,460
un saite uz nākamo mezglu sarakstā

45
00:01:50,460 --> 00:01:52,990
ko mēs pārstāvam kā rādītājs sauc "nākamo."

46
00:01:54,120 --> 00:01:56,780
Tādā veidā, mēs varam izsekot visu sarakstu

47
00:01:56,780 --> 00:01:58,790
tikai ar vienu rādītāju uz 1 mezglu,

48
00:01:58,790 --> 00:02:01,270
un tad mēs varam sekot nākamajai norādes

49
00:02:01,270 --> 00:02:03,130
uz 2 mezglu,

50
00:02:03,130 --> 00:02:05,280
līdz 3 mezglu,

51
00:02:05,280 --> 00:02:07,000
ar 4 mezglu,

52
00:02:07,000 --> 00:02:09,889
un tā tālāk, kamēr mēs uz saraksta beigām.

53
00:02:10,520 --> 00:02:12,210
>> Jums varētu būt iespēja redzēt 1 labumu tas ir

54
00:02:12,210 --> 00:02:14,490
pa statisko masīvu struktūru - ar saistīta sarakstu,

55
00:02:14,490 --> 00:02:16,450
mums nav nepieciešams liels rieciens atmiņas vispār.

56
00:02:17,400 --> 00:02:20,530
Gada 1 mezgla sarakstu varētu dzīvot šajā vietā atmiņā,

57
00:02:20,530 --> 00:02:23,160
un 2. mezglu varētu būt līdz galam nekā šeit.

58
00:02:23,160 --> 00:02:25,780
Mēs varam nokļūt visiem mezgliem vienalga, kur atmiņā tie,

59
00:02:25,780 --> 00:02:28,890
jo sākot gada 1 mezglu, katrs mezgls nākamais rādītājs

60
00:02:28,890 --> 00:02:31,700
stāsta mums, kur tieši iet nākamo.

61
00:02:31,700 --> 00:02:33,670
>> Turklāt, mums nav ko teikt uzreiz

62
00:02:33,670 --> 00:02:36,740
cik liels saistīts saraksts būs kā mēs ar statisko bloki,

63
00:02:36,740 --> 00:02:39,060
jo mēs varam glabāt pievienojot mezglu sarakstu

64
00:02:39,060 --> 00:02:42,600
kamēr tur telpa kaut kur atmiņā jauniem punktiem.

65
00:02:42,600 --> 00:02:45,370
Tāpēc, saistītiem saraksti ir viegli mainīt dinamiski.

66
00:02:45,370 --> 00:02:47,950
Say, vēlāk programmā mums ir nepieciešams, lai pievienotu vairāk mezglu

67
00:02:47,950 --> 00:02:49,350
mūsu sarakstā.

68
00:02:49,350 --> 00:02:51,480
Lai ievietotu jaunu mezglu mūsu sarakstā par lidot,

69
00:02:51,480 --> 00:02:53,740
viss, kas mums ir jādara, ir piešķirt atmiņu šajā mezglā,

70
00:02:53,740 --> 00:02:55,630
plunkšķis kas ir datu vērtības,

71
00:02:55,630 --> 00:02:59,070
un tad ievieto to, kur mēs gribam, pielāgojot atbilstošas ​​norādes.

72
00:02:59,070 --> 00:03:02,310
>> Piemēram, ja mēs vēlējāmies, lai vieta mezglu starp

73
00:03:02,310 --> 00:03:04,020
gada 2 un 3 punkti no saraksta,

74
00:03:04,020 --> 00:03:06,800
 mums nebūtu pārvietot 2. vai 3 punktiem vispār.

75
00:03:06,800 --> 00:03:09,190
Saka, ka mēs esam ievietojot šo sarkano mezglā.

76
00:03:09,190 --> 00:03:12,890
Viss mēs ir jādara, ir noteikt jauno mezglu nākamo rādītāju

77
00:03:12,890 --> 00:03:14,870
norādīt līdz 3 mezglu

78
00:03:14,870 --> 00:03:18,580
un tad rewire gada 2 mezglu nākamo rādītāju

79
00:03:18,580 --> 00:03:20,980
norādīt uz mūsu jauno mezglu.

80
00:03:22,340 --> 00:03:24,370
Tātad, mēs varam mainīt mūsu saraksti par lidot

81
00:03:24,370 --> 00:03:26,090
jo mūsu datorā nav paļauties uz indeksāciju,

82
00:03:26,090 --> 00:03:28,990
bet gan uz saistot izmantojot norādes, lai saglabātu tos.

83
00:03:29,120 --> 00:03:31,600
>> Tomēr trūkums saistīti saraksti

84
00:03:31,600 --> 00:03:33,370
ir tas, ka, atšķirībā no statisku masīvu,

85
00:03:33,370 --> 00:03:36,690
dators var ne tikai lēkt uz vidu sarakstā.

86
00:03:38,040 --> 00:03:40,780
Tā kā dators ir apmeklēt katru mezglu saistītajā sarakstā

87
00:03:40,780 --> 00:03:42,330
nokļūt uz nākamo,

88
00:03:42,330 --> 00:03:44,770
tas notiek, lai ilgāk, lai atrastu konkrētu mezglu

89
00:03:44,770 --> 00:03:46,400
nekā tas būtu masīvā.

90
00:03:46,400 --> 00:03:48,660
Lai šķērsotu visu sarakstu nepieciešams laiks proporcionāls

91
00:03:48,660 --> 00:03:50,580
ar garumu saraksta,

92
00:03:50,580 --> 00:03:54,630
vai O (n) asimptotiskā pierakstā.

93
00:03:54,630 --> 00:03:56,510
Vidēji, sasniedzot jebkuru mezglu

94
00:03:56,510 --> 00:03:58,800
arī nepieciešams laiks proporcionāls n.

95
00:03:58,800 --> 00:04:00,700
>> Tagad, pieņemsim faktiski rakstīt kādu kodu

96
00:04:00,700 --> 00:04:02,000
kas strādā ar saistītas sarakstiem.

97
00:04:02,000 --> 00:04:04,220
Pieņemsim, ka mēs vēlamies saistītu sarakstu integers.

98
00:04:04,220 --> 00:04:06,140
Mēs varam pārstāvēt mezglu mūsu sarakstā atkal

99
00:04:06,140 --> 00:04:08,340
kā struct ar 2 jomās,

100
00:04:08,340 --> 00:04:10,750
vesels vērtību sauc par "val"

101
00:04:10,750 --> 00:04:13,490
un blakus rādītājs uz nākamo mezglu saraksta.

102
00:04:13,490 --> 00:04:15,660
Nu, šķiet vienkāršs pietiekami.

103
00:04:15,660 --> 00:04:17,220
>> Pieņemsim, ka mēs vēlamies, lai rakstītu funkciju

104
00:04:17,220 --> 00:04:19,329
kas šķērso to sarakstā un izdrukā

105
00:04:19,329 --> 00:04:22,150
vērtība saglabāta pēdējā mezgla saraksta.

106
00:04:22,150 --> 00:04:24,850
Nu, tas nozīmē, ka mums būs nepieciešams, lai šķērsotu visus mezglus sarakstā

107
00:04:24,850 --> 00:04:27,310
lai atrastu pēdējo vienu, bet, jo mēs esam ne pievienot

108
00:04:27,310 --> 00:04:29,250
vai izdzēšot kaut ko, mēs nevēlamies mainīt

109
00:04:29,250 --> 00:04:32,210
iekšējā struktūra nākamajos norādes sarakstā.

110
00:04:32,210 --> 00:04:34,790
>> Tātad, mums būs nepieciešams rādītāju īpaši šķērsošana

111
00:04:34,790 --> 00:04:36,940
ko mēs saucam par "rāpuļprogrammu."

112
00:04:36,940 --> 00:04:38,870
Tas būs rāpot cauri visiem saraksta elementu

113
00:04:38,870 --> 00:04:41,190
ko pēc ķēdi nākamo norādes.

114
00:04:41,190 --> 00:04:43,750
Visi mēs esam saglabāti, ir rādītājs uz 1 mezglu,

115
00:04:43,750 --> 00:04:45,730
vai "vadītājs" no saraksta.

116
00:04:45,730 --> 00:04:47,370
Galva norāda uz 1 mezglu.

117
00:04:47,370 --> 00:04:49,120
Tas ir tipa punktveida uz mezglu.

118
00:04:49,120 --> 00:04:51,280
>> Lai iegūtu faktisko 1. mezglu sarakstā,

119
00:04:51,280 --> 00:04:53,250
mums ir dereference šo rādītāju,

120
00:04:53,250 --> 00:04:55,100
bet pirms mēs varam dereference to, mums ir nepieciešams, lai pārbaudītu

121
00:04:55,100 --> 00:04:57,180
ja rādītājs ir nulle pirmais.

122
00:04:57,180 --> 00:04:59,190
Ja tas ir Null, saraksts ir tukšs,

123
00:04:59,190 --> 00:05:01,320
un mums vajadzētu izdrukāt ziņu, ka, jo saraksts ir tukšs,

124
00:05:01,320 --> 00:05:03,250
nav pēdējais mezgls.

125
00:05:03,250 --> 00:05:05,190
Bet, teiksim saraksts nav tukšs.

126
00:05:05,190 --> 00:05:08,340
Ja tā nav, tad mums vajadzētu indeksēt caur visam sarakstam

127
00:05:08,340 --> 00:05:10,440
kamēr mēs līdz pēdējam mezglā saraksta,

128
00:05:10,440 --> 00:05:13,030
un kā mēs varam pateikt, ja mēs meklējam pēdējo mezglu sarakstā?

129
00:05:13,670 --> 00:05:16,660
>> Nu, ja mezgla nākamais rādītājs ir nulle,

130
00:05:16,660 --> 00:05:18,320
Mēs zinām, mēs esam pie beigām

131
00:05:18,320 --> 00:05:22,390
kopš pēdējā nākamais rādītājs nebūtu blakus mezglu sarakstu, lai norādītu uz.

132
00:05:22,390 --> 00:05:26,590
Tā ir laba prakse, lai vienmēr saglabātu pagājušā mezglu blakus rādītāju inicializēts uz null

133
00:05:26,590 --> 00:05:30,800
lai standartizētu īpašumu, kas brīdina mūs, kad mēs esam sasnieguši saraksta.

134
00:05:30,800 --> 00:05:33,510
>> Tātad, ja kāpurķēžu → nākamais ir nulle,

135
00:05:34,120 --> 00:05:38,270
atcerieties, ka bultiņa sintakse ir īsceļu dereferencing

136
00:05:38,270 --> 00:05:40,010
rādītāju uz struct, tad piekļūstot

137
00:05:40,010 --> 00:05:42,510
tās nākamās lauka līdzvērtīga neērts:

138
00:05:42,510 --> 00:05:48,750
(* Kāpurķēžu). Nākamo.

139
00:05:49,820 --> 00:05:51,260
Kad mēs esam noskaidrojuši pēdējo mezglu,

140
00:05:51,260 --> 00:05:53,830
Mēs vēlamies, lai drukātu kāpurķēžu → val,

141
00:05:53,830 --> 00:05:55,000
vērtība pašreizējā mezglā

142
00:05:55,000 --> 00:05:57,130
ko mēs zinām, ir pēdējais.

143
00:05:57,130 --> 00:05:59,740
Pretējā gadījumā, ja mēs neesam vēl pēdējā mezglu sarakstā,

144
00:05:59,740 --> 00:06:02,340
Mums ir jāvirzās uz nākamo mezglu sarakstā

145
00:06:02,340 --> 00:06:04,750
un pārbaudiet, vai tas ir pēdējais.

146
00:06:04,750 --> 00:06:07,010
Lai to izdarītu, mēs vienkārši noteikt savu kāpurķēžu rādītāju

147
00:06:07,010 --> 00:06:09,840
norādīt uz tekošā mezgla nākamo vērtību,

148
00:06:09,840 --> 00:06:11,680
tas ir, nākamais mezglu sarakstā.

149
00:06:11,680 --> 00:06:13,030
Tas tiek darīts, nosakot

150
00:06:13,030 --> 00:06:15,280
kāpurķēžu = kāpurķēžu → nākamo.

151
00:06:16,050 --> 00:06:18,960
Tad mēs atkārtot šo procesu, ar cilpu piemēram,

152
00:06:18,960 --> 00:06:20,960
kamēr mēs atrastu pēdējo mezglu.

153
00:06:20,960 --> 00:06:23,150
Tātad, piemēram, ja kāpurķēžu bija norādot uz galvas,

154
00:06:24,050 --> 00:06:27,710
mēs noteikti rāpuļprogrammu norādīt uz kāpurķēžu → nākamajam

155
00:06:27,710 --> 00:06:30,960
kas ir tāds pats kā nākamo jomā gada 1 mezglu.

156
00:06:30,960 --> 00:06:33,620
Tātad, tagad mūsu kāpurķēžu ir vērsta uz 2 mezglu,

157
00:06:33,620 --> 00:06:35,480
un, atkal, mēs atkārtot ar cilpu,

158
00:06:37,220 --> 00:06:40,610
kamēr mēs esam atraduši pēdējo mezglu, tas ir,

159
00:06:40,610 --> 00:06:43,640
kur mezgla nākamais rādītājs ir vērsta uz null.

160
00:06:43,640 --> 00:06:45,070
Un tur mums ir tā,

161
00:06:45,070 --> 00:06:47,620
Mēs esam noskaidrojuši, pēdējo mezglu sarakstā, un izdrukāt savu vērtību,

162
00:06:47,620 --> 00:06:50,800
mēs tikai izmantot kāpurķēžu → val.

163
00:06:50,800 --> 00:06:53,130
>> Šķērso nav tik slikti, bet kas par ievietošanu?

164
00:06:53,130 --> 00:06:56,290
Lets teikt, mēs vēlamies, lai ievietotu skaitlim uz 4. stāvoklī

165
00:06:56,290 --> 00:06:58,040
jo skaitlim sarakstā.

166
00:06:58,040 --> 00:07:01,280
Tas ir starp pašreizējiem 3 un 4 punktiem.

167
00:07:01,280 --> 00:07:03,760
Atkal, mums ir traversa sarakstu tikai

168
00:07:03,760 --> 00:07:06,520
nokļūt līdz 3 elementu, viens mēs esam Ievietojot pēc.

169
00:07:06,520 --> 00:07:09,300
Tātad, mēs izveidojam kāpurķēžu rādītāju atkal šķērsotu sarakstu,

170
00:07:09,300 --> 00:07:11,400
pārbaudīt, ja mūsu galva rādītājs ir nulle,

171
00:07:11,400 --> 00:07:14,810
un, ja tas nav, norādīt savu kāpurķēžu rādītāju pie galvas mezglā.

172
00:07:16,880 --> 00:07:18,060
Tātad, mēs esam pie gada 1 elementā.

173
00:07:18,060 --> 00:07:21,020
Mums ir jāiet uz priekšu vēl 2 elementi, pirms mēs varam ievietot,

174
00:07:21,020 --> 00:07:23,390
lai mēs varētu izmantot, lai cilpa

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

176
00:07:26,430 --> 00:07:28,590
un katrā atkārtojuma no cilpas,

177
00:07:28,590 --> 00:07:31,540
iepriekš mūsu rāpulim rādītāju priekšu ar 1 mezglu

178
00:07:31,540 --> 00:07:34,570
pārbaudot, ja tekošā mezgla nākamais lauks ir nulle,

179
00:07:34,570 --> 00:07:37,550
un, ja tas nav, pārvietot mūsu rāpulim rādītāju uz nākamo mezglu

180
00:07:37,550 --> 00:07:41,810
nosakot to vienāda tekošā mezgla nākamā rādītājs.

181
00:07:41,810 --> 00:07:45,210
Tātad, jo mūsu lai cilpa saka darīt, ka

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

183
00:07:49,610 --> 00:07:51,190
Mēs esam sasnieguši arī 3 mezglā,

184
00:07:51,190 --> 00:07:53,110
un tiklīdz mūsu rāpuļprogramma rādītājs ir sasniedzis mezglu pēc

185
00:07:53,110 --> 00:07:55,270
ko mēs vēlamies ievietot mūsu jauno skaitlim,

186
00:07:55,270 --> 00:07:57,050
kā mēs faktiski darīt ievietojot?

187
00:07:57,050 --> 00:07:59,440
>> Nu, mūsu jaunais skaitlim ir jāiekļauj sarakstā

188
00:07:59,440 --> 00:08:01,250
kā daļa no tās pašas mezgla struct,

189
00:08:01,250 --> 00:08:03,140
jo tas ir patiešām secība mezgliem.

190
00:08:03,140 --> 00:08:05,690
Tātad, pieņemsim jaunu rādītāju uz mezglu

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

192
00:08:08,910 --> 00:08:11,800
un noteikt to norādīt uz atmiņu ka mēs tagad piešķirt

193
00:08:11,800 --> 00:08:14,270
par kaudzes par mezglā pati,

194
00:08:14,270 --> 00:08:16,000
un cik daudz atmiņas mums vajag piešķirt?

195
00:08:16,000 --> 00:08:18,250
Nu, lieluma mezglā,

196
00:08:20,450 --> 00:08:23,410
un mēs vēlamies noteikt savu val lauku uz skaitlim, ka mēs vēlamies, lai ievietotu.

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

198
00:08:25,590 --> 00:08:27,710
Tagad mezglā ir mūsu veselam skaitlim.

199
00:08:27,710 --> 00:08:30,650
Tā ir arī laba prakse, lai sāktu jauno mezglu nākamo lauku

200
00:08:30,650 --> 00:08:33,690
norādīt uz null,

201
00:08:33,690 --> 00:08:35,080
bet tagad ko?

202
00:08:35,080 --> 00:08:37,179
>> Mums ir jāmaina iekšējo struktūru sarakstu

203
00:08:37,179 --> 00:08:40,409
un nākamie norādes sarakstā ietvertajām kādreizējā

204
00:08:40,409 --> 00:08:42,950
3 un 4 punktiem.

205
00:08:42,950 --> 00:08:46,560
Tā kā nākamās norādes nosaka saraksta secību,

206
00:08:46,560 --> 00:08:48,650
un, jo mēs esam Ievietojot mūsu jauno mezglu

207
00:08:48,650 --> 00:08:50,510
labi vidū saraksta,

208
00:08:50,510 --> 00:08:52,010
tas var būt nedaudz grūts.

209
00:08:52,010 --> 00:08:54,250
Tas ir tāpēc, atcerieties, mūsu dators

210
00:08:54,250 --> 00:08:56,250
tikai zina vietu mezglu sarakstā

211
00:08:56,250 --> 00:09:00,400
jo nākamajos norādes glabājas iepriekšējos mezgliem.

212
00:09:00,400 --> 00:09:03,940
Tātad, ja mēs kādreiz zaudējis dziesmu no jebkura no šīm vietām,

213
00:09:03,940 --> 00:09:06,860
saka, mainot vienu no nākamajiem norādes mūsu sarakstā,

214
00:09:06,860 --> 00:09:09,880
Piemēram, saka, mēs mainīts

215
00:09:09,880 --> 00:09:12,920
The 3rd mezgla nākamais lauks

216
00:09:12,920 --> 00:09:15,610
norādīt uz kādu mezglu nekā šeit.

217
00:09:15,610 --> 00:09:17,920
Mēs gribētu būt no luck, jo mēs nebūtu

218
00:09:17,920 --> 00:09:20,940
ir kāda ideja, kur atrast pārējo sarakstu,

219
00:09:20,940 --> 00:09:23,070
un tas acīmredzot tiešām slikti.

220
00:09:23,070 --> 00:09:25,080
Tātad, mums ir jābūt ļoti uzmanīgiem par rīkojuma

221
00:09:25,080 --> 00:09:28,360
kurā mēs manipulēt mūsu nākamais palīglīdzekļi ievietošanas laikā.

222
00:09:28,360 --> 00:09:30,540
>> Tātad, lai vienkāršotu šo, pieņemsim, ka

223
00:09:30,540 --> 00:09:32,220
Mūsu pirmie 4 mezgliem

224
00:09:32,220 --> 00:09:36,200
sauc A, B, C un D, ​​ar bultiņām, kas pārstāv ķēdi norādes

225
00:09:36,200 --> 00:09:38,070
kas savieno mezglus.

226
00:09:38,070 --> 00:09:40,050
Tātad, mums ir nepieciešams, lai ievietotu mūsu jauno mezglu

227
00:09:40,050 --> 00:09:42,070
starp mezglu C un D

228
00:09:42,070 --> 00:09:45,060
Tas ir svarīgi to darīt pareizajā secībā, un es tev parādīšu, kāpēc.

229
00:09:45,060 --> 00:09:47,500
>> Apskatīsim nepareizā veidā to darīt vispirms.

230
00:09:47,500 --> 00:09:49,490
Hei, mēs zinām jaunais mezgls ir jānāk uzreiz pēc C,

231
00:09:49,490 --> 00:09:51,910
tāpēc pieņemsim noteikt C ir nākamais rādītājs

232
00:09:51,910 --> 00:09:54,700
norādīt uz new_node.

233
00:09:56,530 --> 00:09:59,180
Viss labais, šķiet labi, mēs vienkārši ir pabeigt līdz šim ar

234
00:09:59,180 --> 00:10:01,580
padarot jauno mezglu blakus rādītājs norāda uz D,

235
00:10:01,580 --> 00:10:03,250
Bet pagaidiet, kā mēs varam darīt?

236
00:10:03,250 --> 00:10:05,170
Vienīgais, kas varētu mums pastāstīt, kur D bija,

237
00:10:05,170 --> 00:10:07,630
Tika nākamais rādītājs iepriekš glabājas C,

238
00:10:07,630 --> 00:10:09,870
bet mēs vienkārši pārrakstīja ka rādītāju

239
00:10:09,870 --> 00:10:11,170
norādīt uz jaunu mezglu,

240
00:10:11,170 --> 00:10:14,230
tāpēc mums vairs nav nekādas jausmas, kur D ir atmiņā,

241
00:10:14,230 --> 00:10:17,020
un mēs esam zaudējuši pārējo sarakstu.

242
00:10:17,020 --> 00:10:19,000
Nav labi.

243
00:10:19,000 --> 00:10:21,090
>> Tātad, kā mēs izdarīt labi?

244
00:10:22,360 --> 00:10:25,090
Pirmkārt, punkts jaunā mezglu nākamo rādītāju pie D.

245
00:10:26,170 --> 00:10:28,990
Tagad gan jaunā mezglu un C ir nākamais norādes

246
00:10:28,990 --> 00:10:30,660
ir norāda uz to pašu mezglu, D,

247
00:10:30,660 --> 00:10:32,290
bet tas ir jauki.

248
00:10:32,290 --> 00:10:35,680
Tagad mēs varam punkts C 's nākamo rādītāju pie jaunu mezglu.

249
00:10:37,450 --> 00:10:39,670
Tātad, mēs esam izdarījuši, nezaudējot nekādus datus.

250
00:10:39,670 --> 00:10:42,280
Ar kodu, C ir pašreizējā mezgls

251
00:10:42,280 --> 00:10:45,540
ka šķērsošana rādītājs kāpurķēžu ir vērsta uz,

252
00:10:45,540 --> 00:10:50,400
un D ir pārstāvēta ar mezglu, ko uzrādīja tekošā mezgla nākamajā laukā,

253
00:10:50,400 --> 00:10:52,600
vai kāpurķēžu → nākamo.

254
00:10:52,600 --> 00:10:55,460
Tātad, mēs vispirms noteikt jauno mezglu nākamo rādītāju

255
00:10:55,460 --> 00:10:57,370
norādīt uz kāpurķēžu → nākamajam

256
00:10:57,370 --> 00:11:00,880
Tāpat mēs teikt new_node nākamais rādītājs būtu

257
00:11:00,880 --> 00:11:02,780
norāda uz D attēlā.

258
00:11:02,780 --> 00:11:04,540
Tad mēs varam noteikt tekošā mezgla nākamo rādītāju

259
00:11:04,540 --> 00:11:06,330
ar mūsu jauno mezglu,

260
00:11:06,330 --> 00:11:10,980
tāpat kā mums bija jāgaida, lai pielikuma C new_node zīmējumā.

261
00:11:10,980 --> 00:11:12,250
Tagad viss ir kārtībā, un mēs nezaudēja

262
00:11:12,250 --> 00:11:14,490
izsekot jebkuru datu, un mums bija iespēja tieši

263
00:11:14,490 --> 00:11:16,200
pieturēties mūsu jauno mezglu vidū saraksta

264
00:11:16,200 --> 00:11:19,330
bez pārbūves visa lieta vai pat novirzot nekādus elementus

265
00:11:19,330 --> 00:11:22,490
kā mēs būtu bijis ar noteikta garuma masīvs.

266
00:11:22,490 --> 00:11:26,020
>> Tātad, saistītiem saraksti ir pamata, bet svarīgi, dinamisku datu struktūra

267
00:11:26,020 --> 00:11:29,080
kas ir gan priekšrocības, gan trūkumi

268
00:11:29,080 --> 00:11:31,260
salīdzinot ar masīvu un citu datu struktūru,

269
00:11:31,260 --> 00:11:33,350
un kā tas bieži notiek datorzinātnes,

270
00:11:33,350 --> 00:11:35,640
tas ir svarīgi zināt, kad izmantot katru rīks,

271
00:11:35,640 --> 00:11:37,960
lai jūs varētu izvēlēties pareizo rīku labo darbu.

272
00:11:37,960 --> 00:11:40,060
>> Lai iegūtu plašāku prakses, mēģiniet rakstot funkcijas

273
00:11:40,060 --> 00:11:42,080
dzēst mezglu no saistītajā sarakstā -

274
00:11:42,080 --> 00:11:44,050
atcerieties jābūt uzmanīgiem par rīkojumu, kurā jūs pārkārtot

275
00:11:44,050 --> 00:11:47,430
jūsu nākamais norādes, lai nodrošinātu, ka jums nav zaudēt rieciens savu sarakstu -

276
00:11:47,430 --> 00:11:50,200
vai funkciju, lai saskaitītu mezglu saistītajā sarakstā,

277
00:11:50,200 --> 00:11:53,280
vai jautri viens, lai mainītu secību visu, kas ir saistīts saraksts mezgliem.

278
00:11:53,280 --> 00:11:56,090
>> Mans vārds ir Džeksons Steinkamp, ​​tas ir CS50.