1
00:00:00,000 --> 00:00:02,832
>> [Mūzikas atskaņošanai]

2
00:00:02,832 --> 00:00:05,670

3
00:00:05,670 --> 00:00:08,560
>> Doug LLOYD: Labi, tāpēc pie
šis punkts gaitā,

4
00:00:08,560 --> 00:00:15,300
mēs esam uz daudz pamati C.
Mēs zinām daudz par mainīgo, masīvi,

5
00:00:15,300 --> 00:00:17,610
norādes, visu, kas labs stuff.

6
00:00:17,610 --> 00:00:21,610
Tie ir visu veida būvēts
lai redzētu, kā pamatprincipiem,

7
00:00:21,610 --> 00:00:23,880
bet mēs varam izdarīt vairāk, vai ne?

8
00:00:23,880 --> 00:00:27,930
Mēs varam apvienot lietas
kopā interesantos veidos.

9
00:00:27,930 --> 00:00:31,010
>> Un tāpēc pieņemsim to, ka sāksim
sazaroties no kāda C dod mums,

10
00:00:31,010 --> 00:00:35,270
un sākt veidot savu datu
struktūras, kas izmanto šīs ēkas

11
00:00:35,270 --> 00:00:40,590
blokus kopā kaut ko darīt
tiešām vērtīgs, noderīga.

12
00:00:40,590 --> 00:00:43,420
Viens veids, kā mēs varam izdarīt, ir
runāt par kolekcijām.

13
00:00:43,420 --> 00:00:48,360
Līdz Līdz šim mēs esam bija viena veida datus
struktūra, kas pārstāv kolekcijas

14
00:00:48,360 --> 00:00:51,030
no patīk vērtības, līdzīgas vērtības.

15
00:00:51,030 --> 00:00:52,350
Tas būtu masīvs.

16
00:00:52,350 --> 00:00:57,020
Mums ir kolekcijas veselus skaitļus, vai
kolekcijas burtiem un tā tālāk.

17
00:00:57,020 --> 00:01:00,890
>> Struktūras ir arī sava veida datu
struktūru informācijas vākšanai,

18
00:01:00,890 --> 00:01:03,220
bet tas nav savākšanai, piemēram, vērtībām.

19
00:01:03,220 --> 00:01:08,090
Tas parasti maisījumi dažādu datu tipu
kopā iekšpusē vienā kastē.

20
00:01:08,090 --> 00:01:10,750
Bet tas nav pats par sevi
izmanto, lai ķēdes kopā

21
00:01:10,750 --> 00:01:16,920
vai savienot kopā līdzīgs
priekšmeti, piemēram, masīvu.

22
00:01:16,920 --> 00:01:20,960
Masīvi ir liels
elements uzmeklēt, bet atgādināt

23
00:01:20,960 --> 00:01:24,262
ka tas ir ļoti grūti
ievietot masīva,

24
00:01:24,262 --> 00:01:26,470
ja vien mēs esam ievietojot at
pašām beigām šī masīva.

25
00:01:26,470 --> 00:01:29,730
>> Un labākais piemērs man ir
par to ir ievietošanas veida.

26
00:01:29,730 --> 00:01:31,650
Ja jūs atceraties mūsu video
uz ievietošanas veida,

27
00:01:31,650 --> 00:01:34,110
tur bija daudz
izdevumi iesaistīti ņemot

28
00:01:34,110 --> 00:01:37,970
uzņemt elementus, un novirzīt tos
no tā, lai ietilptu kaut ko

29
00:01:37,970 --> 00:01:41,290
vērā vidū jūsu masīvs.

30
00:01:41,290 --> 00:01:44,690
Masīvi arī cieš no otra
Problēma, kas ir neelastīgums.

31
00:01:44,690 --> 00:01:47,150
Kad mēs deklarēt masīvu,
mēs iegūtu vienu shot pie tā.

32
00:01:47,150 --> 00:01:49,790
Mēs teikt, es gribu
šis daudzi elementi.

33
00:01:49,790 --> 00:01:51,940
Varētu būt 100, tas var
būt 1000, tas varētu

34
00:01:51,940 --> 00:01:55,930
būt x, kur x ir skaitlis, ka lietotājs
sniedza mums tūlītēju vai komandu

35
00:01:55,930 --> 00:01:56,630
line.

36
00:01:56,630 --> 00:01:59,905
>> Bet mēs tikai iegūt vienu shot pie tā, mēs
nesaņem tad teikt ak, patiesībā es

37
00:01:59,905 --> 00:02:04,360
nepieciešami 101, vai man vajadzēja x plus 20.

38
00:02:04,360 --> 00:02:07,910
Pārāk vēlu, mēs esam jau paziņoja, ka
masīvs, un, ja mēs gribam, lai saņemtu 101 vai x

39
00:02:07,910 --> 00:02:12,050
plus 20, mums ir jādeklarē
pavisam cits masīvs,

40
00:02:12,050 --> 00:02:15,540
kopēt visus elementus masīva
vairāk, un tad mums ir pietiekami daudz.

41
00:02:15,540 --> 00:02:19,880
Un ko tad, ja mēs esam nepareizi atkal, ko
ja mums tiešām ir nepieciešams 102, vai X plus 40,

42
00:02:19,880 --> 00:02:21,970
mums ir jādara tas vēlreiz.

43
00:02:21,970 --> 00:02:26,250
Tāpēc viņi ir ļoti neelastīga
izmēru maiņas mūsu datus,

44
00:02:26,250 --> 00:02:29,360
bet, ja mēs apvienot kopā dažus
no pamatiem, ko mēs jau esam

45
00:02:29,360 --> 00:02:33,230
uzzināja par norādes un struktūrām,
jo īpaši, izmantojot dinamisko atmiņu

46
00:02:33,230 --> 00:02:36,180
piešķiršana ar malloc, mēs
var likt šos gabalus kopā

47
00:02:36,180 --> 00:02:40,960
izveidot jaunu datu structure-- A
atsevišķi saistīts sarakstu mēs varētu say--

48
00:02:40,960 --> 00:02:45,400
kas ļauj mums augt un
sarukt kolekcija vērtībām

49
00:02:45,400 --> 00:02:48,800
un mums nebūs nekādu izšķērdēta kosmosa.

50
00:02:48,800 --> 00:02:53,320
>> Tātad atkal mēs aicinām šo ideju,
šis jēdziens, saistītais saraksts.

51
00:02:53,320 --> 00:02:56,320
Proti, šajā video mēs esam
runājam par atsevišķi saistīta sarakstā,

52
00:02:56,320 --> 00:02:59,185
un tad vēl video mēs runājam
par divkārt saistīti saraksti, kas

53
00:02:59,185 --> 00:03:01,560
ir tikai variācija par tēmu šeit.

54
00:03:01,560 --> 00:03:05,200
Bet atsevišķi saistīts saraksts
sastāv no mezgliem,

55
00:03:05,200 --> 00:03:08,559
mezgli nav tikai abstrakts term--
tas ir tikai kaut kas es esmu aicinot

56
00:03:08,559 --> 00:03:10,350
tas ir sava veida
struktūra, būtībā, es esmu?

57
00:03:10,350 --> 00:03:16,190
Tikai gatavojas to nosaukt node-- un tas
mezgls ir divi locekļi vai divus laukus.

58
00:03:16,190 --> 00:03:20,300
Tas ir dati, parasti ir
skaitlis, raksturs peldēt,

59
00:03:20,300 --> 00:03:23,790
vai varētu būt kāds cits datu tips
ka jūs esat definēts ar tipa def.

60
00:03:23,790 --> 00:03:29,290
Un tas ietver rādītāju uz
vēl viens mezgls tā paša tipa.

61
00:03:29,290 --> 00:03:34,710
>> Tātad mums ir divas lietas iekšpusē
šis mezgls, datu un rādītāju

62
00:03:34,710 --> 00:03:36,380
uz citu mezglu.

63
00:03:36,380 --> 00:03:39,370
Un, ja jūs sākat vizualizēt
tas, jūs varat domāt par to

64
00:03:39,370 --> 00:03:42,280
kā ķēdes mezglu, kas
ir savienoti kopā.

65
00:03:42,280 --> 00:03:45,070
Mums ir pirmo mezglu, to
satur datus un rādītāju

66
00:03:45,070 --> 00:03:49,110
ar otro mezglu, kas satur
dati, un rādītāju uz trešo mezglu.

67
00:03:49,110 --> 00:03:52,940
Un tā tas ir iemesls, kāpēc mēs to saucam par
saistīts saraksts, viņi savstarpēji saistīti.

68
00:03:52,940 --> 00:03:56,070
>> Ko dara šis īpašais
mezgla struktūra izskatās?

69
00:03:56,070 --> 00:04:01,120
Nu, ja jūs atceraties no mūsu video
definējot pasūtījuma tipus, ar tipa DEF,

70
00:04:01,120 --> 00:04:05,400
mēs varam definēt structure-- un
ierakstiet definētu struktūru, kā šis.

71
00:04:05,400 --> 00:04:11,240
tyepdef struct sllist, un tad es esmu
izmantojot vārdu vērtību šeit patvaļīgi

72
00:04:11,240 --> 00:04:13,891
lai norādītu datu tipu tiešām.

73
00:04:13,891 --> 00:04:16,890
Jūs varētu iet uz skaitlim vai peldēt,
Jums varētu būt, ko jūs vēlaties.

74
00:04:16,890 --> 00:04:19,389
Tas nav tikai vienkārši
veseli skaitļi, vai kaut kas tamlīdzīgs.

75
00:04:19,389 --> 00:04:22,790
Tātad vērtība ir tikai patvaļīgs
datu tips, un pēc tam rādītājs

76
00:04:22,790 --> 00:04:26,310
uz citu mezglu tā paša tipa.

77
00:04:26,310 --> 00:04:29,690
>> Tagad tur ir maz nozvejas
šeit ar definējot struktūru

78
00:04:29,690 --> 00:04:33,030
kad tas ir sevi godbijīgs struktūra.

79
00:04:33,030 --> 00:04:35,340
Man ir jābūt pagaidu
nosaukt par manu struktūru.

80
00:04:35,340 --> 00:04:37,640
Beigās dienas I
nepārprotami vēlas, lai izsauktu to

81
00:04:37,640 --> 00:04:43,030
SLL mezglā, tas galu galā jaunais
nosaukt daļa no mana tipa definīciju,

82
00:04:43,030 --> 00:04:47,450
bet es nevaru izmantot SLL mezglu
vidū šis.

83
00:04:47,450 --> 00:04:51,430
Iemesls ir, man nav
izveidoja tipa sauc SLL mezglu

84
00:04:51,430 --> 00:04:55,200
kamēr es hit šo pēdējo punktu šeit.

85
00:04:55,200 --> 00:04:59,720
Līdz šo jautājumu, man ir jābūt
vēl viens veids, kā atsaukties uz šo datu tipu.

86
00:04:59,720 --> 00:05:02,440
>> Un tas ir self
godbijīgs datu tips.

87
00:05:02,440 --> 00:05:06,314
Tas, s datu tipam
struktūra, kas satur datus,

88
00:05:06,314 --> 00:05:08,480
un rādītājs uz citu
struktūra tā paša tipa.

89
00:05:08,480 --> 00:05:11,750
Tāpēc man ir nepieciešams, lai varētu atsaukties uz
šī datu tips vismaz uz laiku,

90
00:05:11,750 --> 00:05:14,910
tā dodot tai ir pagaidu
nosaukums struct sllist

91
00:05:14,910 --> 00:05:18,540
ļauj man tad teikt, es gribu
rādītāju uz citu struct sllist,

92
00:05:18,540 --> 00:05:24,690
struct sllist zvaigzne, un pēc tam
pēc tam, kad es esmu pabeidzis definīciju,

93
00:05:24,690 --> 00:05:27,220
Es tagad var zvanīt šāda veida SLL mezglā.

94
00:05:27,220 --> 00:05:30,520
>> Tātad, tas ir iemesls, kāpēc jūs redzēt tur ir
pagaidu nosaukums šeit,

95
00:05:30,520 --> 00:05:31,879
bet pastāvīgs vārds šeit.

96
00:05:31,879 --> 00:05:33,920
Reizēm jūs varētu redzēt
definīcijas struktūra,

97
00:05:33,920 --> 00:05:36,570
piemēram, kas ir ne
sevis godbijīgs, ka

98
00:05:36,570 --> 00:05:39,390
nav apzīmētājs nosaukumu šeit.

99
00:05:39,390 --> 00:05:43,040
Tas būtu vienkārši teikt typedef struktūrai,
atvērt cirtaini lencēm un tad noteikt to.

100
00:05:43,040 --> 00:05:45,620
Bet, ja tu esi struct ir pašnodarbināta
godbijīgs, jo tas ir viens,

101
00:05:45,620 --> 00:05:49,010
Jums ir nepieciešams norādīt
pagaidu veida nosaukums.

102
00:05:49,010 --> 00:05:51,310
Bet galu galā, tagad
ka mēs esam izdarījuši,

103
00:05:51,310 --> 00:05:53,620
mēs varam tikai attiecas uz
šiem mezgliem, šīs vienības,

104
00:05:53,620 --> 00:05:57,900
kā SLL mezgli nolūkos
no pārējo šo video.

105
00:05:57,900 --> 00:06:00,900
>> Labi, tāpēc mēs zinām, kā
izveidot saistīts saraksta mezglā.

106
00:06:00,900 --> 00:06:03,240
Mēs zinām, kā to definēt
saistītais saraksts mezglu.

107
00:06:03,240 --> 00:06:06,670
Tagad, ja mēs ejam, lai sāktu
izmantot tos, lai savāktu informāciju,

108
00:06:06,670 --> 00:06:10,360
tur ir pāris operācijām mēs
nepieciešams saprast un strādāt.

109
00:06:10,360 --> 00:06:12,860
Mums ir jāzina, kā izveidot
saistītais saraksts no zila gaisa.

110
00:06:12,860 --> 00:06:14,901
Ja tur nav saraksts jau,
mēs vēlamies, lai sāktu vienu.

111
00:06:14,901 --> 00:06:16,960
Tāpēc mums ir jāspēj
lai izveidotu saistīts sarakstu,

112
00:06:16,960 --> 00:06:19,130
mums ir nepieciešams, lai, iespējams, meklēt
izmantojot saiti sarakstu

113
00:06:19,130 --> 00:06:21,830
atrast elementu mēs meklējam.

114
00:06:21,830 --> 00:06:24,430
Mums ir nepieciešams, lai varētu ievietot
jaunas lietas fani sarakstā,

115
00:06:24,430 --> 00:06:25,930
mēs vēlamies, lai mūsu sarakstā, lai varētu augt.

116
00:06:25,930 --> 00:06:28,638
Un līdzīgi, mēs vēlamies, lai varētu
izdzēst lietas no mūsu saraksta,

117
00:06:28,638 --> 00:06:30,250
mēs vēlamies, lai mūsu sarakstā, lai varētu sarukt.

118
00:06:30,250 --> 00:06:32,160
Un beigās mūsu
programmas, jo īpaši

119
00:06:32,160 --> 00:06:34,550
Ja jūs atceraties, ka mēs esam
dinamiski piešķirot atmiņu

120
00:06:34,550 --> 00:06:38,337
veidot šos sarakstus, parasti,
mēs vēlamies, lai atbrīvotu visu šo atmiņa

121
00:06:38,337 --> 00:06:39,670
kad mēs esam darījuši strādāt ar to.

122
00:06:39,670 --> 00:06:44,627
Un tāpēc mums ir nepieciešams, lai varētu dzēst
viss saistīts saraksts vienā neizdoties sagrābt.

123
00:06:44,627 --> 00:06:46,460
So iesim cauri
daži no šiem operāciju

124
00:06:46,460 --> 00:06:51,192
un kā mēs varētu vizualizēt tos,
runā pseudocode kodu konkrēti.

125
00:06:51,192 --> 00:06:53,150
Tāpēc mēs vēlamies, lai izveidotu
saistīta sarakstu, tāpēc varbūt mēs

126
00:06:53,150 --> 00:06:56,480
vēlaties, lai noteiktu funkciju
ar šo prototipu.

127
00:06:56,480 --> 00:07:01,690
SLL mezglā zvaigzne, radīt, un es esmu iet
vienā arguments, daži patvaļīgi dati

128
00:07:01,690 --> 00:07:05,530
rakstīt atkal, dažu patvaļīgu datu tipu.

129
00:07:05,530 --> 00:07:10,482
Bet es esmu returning-- šo funkciju vajadzētu
atgriezties pie manis rādītāju, līdz A atsevišķi

130
00:07:10,482 --> 00:07:11,190
saistīts saraksts mezglā.

131
00:07:11,190 --> 00:07:14,050
Atgādināsim, ka mēs cenšamies, lai radītu
saistītais saraksts no zila gaisa,

132
00:07:14,050 --> 00:07:17,900
tāpēc man ir nepieciešams rādītāju uz
šis saraksts, kad es esmu darīts.

133
00:07:17,900 --> 00:07:19,420
>> Tātad, kādi ir soļi šeit iesaistīti?

134
00:07:19,420 --> 00:07:20,960
Nu, pirmā lieta, ko es esmu
gatavojas darīt, ir dinamiski

135
00:07:20,960 --> 00:07:22,550
piešķirt vietu jaunu mezglu.

136
00:07:22,550 --> 00:07:26,689
Atgādināsim, ka mēs esam veidojot to no plānas
gaiss, tāpēc mums ir nepieciešams, lai malloc vietu tajā.

137
00:07:26,689 --> 00:07:28,480
Un, protams, nekavējoties
kad mēs malloc,

138
00:07:28,480 --> 00:07:31,692
mēs vienmēr pārliecinieties, ka mūsu
pointer-- mēs nesaņēma atpakaļ null.

139
00:07:31,692 --> 00:07:33,650
Jo, ja mēs mēģinātu
cieņa Null rādītāju,

140
00:07:33,650 --> 00:07:36,190
mēs esam gatavojas ciest
segfault un mēs negribam, ka.

141
00:07:36,190 --> 00:07:39,510
>> Tad mēs vēlamies aizpildīt jomā,
mēs vēlamies, lai sāktu vērtību lauks

142
00:07:39,510 --> 00:07:41,690
un sāktu nākamo lauku.

143
00:07:41,690 --> 00:07:45,450
Un tad mēs gribam kuri paredzēti, beidzot kā
funkcija prototips indicates-- mēs gribam

144
00:07:45,450 --> 00:07:49,940
atgriezties rādītāju uz SLL mezglā.

145
00:07:49,940 --> 00:07:51,710
Tātad, kas padara šo izskatās vizuāli?

146
00:07:51,710 --> 00:07:55,230
Nu, pirmkārt, mēs ejam, lai dinamiski
piešķirt vietu jaunam SLL mezglu,

147
00:07:55,230 --> 00:07:58,320
tāpēc mēs malloc-- tas
vizuāls attēlojums

148
00:07:58,320 --> 00:08:00,020
mezgla mēs tikko izveidots.

149
00:08:00,020 --> 00:08:02,757
Un mēs pārbaudām, lai pārliecinātos,
tas nav null-- šajā gadījumā,

150
00:08:02,757 --> 00:08:04,840
aina nebūtu
parādīts uz augšu, ja tas bija null,

151
00:08:04,840 --> 00:08:07,298
mēs būtu beigušies atmiņas,
tāpēc mēs esam labi iet tur.

152
00:08:07,298 --> 00:08:10,200
Tāpēc tagad mēs esam par soli C,
inicializēt mezgli vērtības laukā.

153
00:08:10,200 --> 00:08:12,280
Nu, pamatojoties uz šo funkciju
zvaniet es esmu, izmantojot šeit,

154
00:08:12,280 --> 00:08:16,700
Izskatās, ka es gribu iet uz 6.,
tāpēc es ņemšu 6 vērtības laukā.

155
00:08:16,700 --> 00:08:18,865
Tagad, sāktu nākamo lauku.

156
00:08:18,865 --> 00:08:21,640
Nu, ko es esmu gatavojas darīt tur,
nekas blakus, pa labi,

157
00:08:21,640 --> 00:08:23,600
tas ir vienīgais, sarakstā.

158
00:08:23,600 --> 00:08:27,206
Tātad, kas ir nākamā lieta sarakstā?

159
00:08:27,206 --> 00:08:29,660
>> Tā nedrīkst norādīt uz kaut ko, labi.

160
00:08:29,660 --> 00:08:33,600
Tur nekas cits tur, lai to, kas ir
jēdziens mēs zinu, ka ir nothing--

161
00:08:33,600 --> 00:08:35,638
norādes uz neko?

162
00:08:35,638 --> 00:08:37,929
Tas būtu varbūt mēs gribam
likt null rādītāju tur,

163
00:08:37,929 --> 00:08:40,178
un es ņemšu pārstāv null
rādītājs kā tikai sarkanu lodziņu,

164
00:08:40,178 --> 00:08:41,559
mēs nevaram iet tālāk.

165
00:08:41,559 --> 00:08:44,430
Kā mēs redzēsim nedaudz vēlāk,
mums būs galu galā ķēdes

166
00:08:44,430 --> 00:08:46,330
Bultu savieno
šiem mezgliem kopā,

167
00:08:46,330 --> 00:08:48,480
bet, kad jūs hit
sarkana kaste, kas ir null,

168
00:08:48,480 --> 00:08:51,150
mēs nevaram iet tālāk,
tas ir beigu saraksta.

169
00:08:51,150 --> 00:08:53,960
>> Un visbeidzot, mēs vienkārši vēlamies
atgriezties rādītāju uz šo mezglu.

170
00:08:53,960 --> 00:08:56,160
Tāpēc mēs to saucam jauns,
un atgriezīsies jauns

171
00:08:56,160 --> 00:08:59,370
lai to var lietot
kāda funkcija izveidoja to.

172
00:08:59,370 --> 00:09:03,100
Tātad mēs ejam, esam izveidojuši atsevišķi
saistīts saraksts mezgla no zila gaisa,

173
00:09:03,100 --> 00:09:05,920
un tagad mums ir saraksts, mēs varam strādāt.

174
00:09:05,920 --> 00:09:08,260
>> Tagad, teiksim, mēs jau
ir liels ķēdi,

175
00:09:08,260 --> 00:09:09,800
un mēs vēlamies, lai atrastu kaut ko tajā.

176
00:09:09,800 --> 00:09:12,716
Un mēs gribam funkcija, kas notiek,
atgriezties true vai false, atkarībā

177
00:09:12,716 --> 00:09:15,840
par to, vai vērtība eksistē šajā sarakstā.

178
00:09:15,840 --> 00:09:18,160
Funkcija prototips, vai
deklarācija par šo funkciju,

179
00:09:18,160 --> 00:09:23,320
varētu izskatīties this-- Bool atrast, un
tad mēs gribam iet uz diviem argumentiem.

180
00:09:23,320 --> 00:09:26,996
>> Pirmais, ir rādītājs uz
no saistītā saraksta pirmais elements.

181
00:09:26,996 --> 00:09:29,620
Tas ir tiešām kaut kas jums
vienmēr vēlas sekot,

182
00:09:29,620 --> 00:09:33,110
un tiešām varētu būt kaut kas
jūs pat nodot globālā mainīgā.

183
00:09:33,110 --> 00:09:35,360
Tiklīdz jūs izveidot sarakstu,
Jums vienmēr, vienmēr

184
00:09:35,360 --> 00:09:38,990
vēlas sekot līdzi ļoti
no saraksta pirmais elements.

185
00:09:38,990 --> 00:09:43,690
Tādā veidā jūs varat atsaukties uz visu pārējo
elementi, tikai pēc ķēdi,

186
00:09:43,690 --> 00:09:47,300
bez saglabātu norādes
neskarts uz katru elementu.

187
00:09:47,300 --> 00:09:50,920
Jums tikai nepieciešams, lai sekotu pirmais
vienu, ja viņi visi pieķēdēts kopā.

188
00:09:50,920 --> 00:09:52,460
>> Un tad otrā lieta
mēs iet atkal

189
00:09:52,460 --> 00:09:54,376
ir patvaļīgi some--
neatkarīgi no datu tipu mēs esam

190
00:09:54,376 --> 00:09:59,640
meklē tur ir iekšā
cerams viens no mezgliem sarakstā.

191
00:09:59,640 --> 00:10:00,980
Tātad, kādi ir soļi?

192
00:10:00,980 --> 00:10:04,250
Nu, pirmā lieta, ko mēs darām, ir
mēs izveidot transversālu rādītāju

193
00:10:04,250 --> 00:10:06,015
norādot uz sarakstos galvu.

194
00:10:06,015 --> 00:10:08,890
Nu, kāpēc mēs to darām, mēs jau
ir rādītāju pie saraksti galvas,

195
00:10:08,890 --> 00:10:10,974
kāpēc nav mēs vienkārši pārvietot, ka viens apkārt?

196
00:10:10,974 --> 00:10:13,140
Nu, piemēram, es tikko teicu,
tas ir patiešām svarīgi, lai mums

197
00:10:13,140 --> 00:10:17,580
vienmēr sekot
ļoti pirmais elements sarakstā.

198
00:10:17,580 --> 00:10:21,270
Un tā tas ir tiešām labāk
izveidot dublikātu, ka,

199
00:10:21,270 --> 00:10:25,350
un izmantot šo, lai pārvietotos, lai mēs nekad
nejauši virzīties prom, vai mēs vienmēr

200
00:10:25,350 --> 00:10:30,430
ir rādītāju kādā brīdī, kas ir
tiesības uz saraksta pirmā elementa.

201
00:10:30,430 --> 00:10:33,290
Tātad, tas ir labāk, lai izveidotu
Otrs, ko mēs izmantojam, lai pārvietotos.

202
00:10:33,290 --> 00:10:35,877
>> Tad mēs vienkārši salīdzināt, vai
vērtība lauks šajā mezglā

203
00:10:35,877 --> 00:10:38,960
ir tas, ko mēs meklējam, un, ja tas ir
nē, mēs vienkārši pāriet uz nākamo mezglu.

204
00:10:38,960 --> 00:10:41,040
Un mēs turpinām darām
vairāk, un vairāk, un vairāk,

205
00:10:41,040 --> 00:10:44,811
kamēr mēs vai nu atrast
elements, vai arī mēs hit

206
00:10:44,811 --> 00:10:47,310
null-- mēs esam sasnieguši
no saraksta, un tas ir ne tur.

207
00:10:47,310 --> 00:10:50,540
Tas būtu cerams gredzens bell
jūs kā tikko lineārs meklēšanu,

208
00:10:50,540 --> 00:10:54,430
mēs esam tikai atdarināt to
atsevišķi saistīts saraksts struktūra

209
00:10:54,430 --> 00:10:56,280
nevis izmantojot masīvu, lai to izdarītu.

210
00:10:56,280 --> 00:10:58,210
>> Tātad, šeit ir piemērs
atsevišķi saistīts saraksts.

211
00:10:58,210 --> 00:11:00,043
Tas viens sastāv no
pieci mezgli, un mums ir

212
00:11:00,043 --> 00:11:04,330
rādītāju uz galvas
saraksts, kas tiek saukts saraksts.

213
00:11:04,330 --> 00:11:07,385
Pirmā lieta, ko mēs vēlamies darīt, ir
atkal, izveidot šo šķērsošana rādītāju.

214
00:11:07,385 --> 00:11:09,760
Tāpēc mums ir tagad ir divas norādes
kas norāda uz vienu un to pašu.

215
00:11:09,760 --> 00:11:15,025
>> Tagad, paziņojums šeit arī, man nav
ir malloc jebkuru telpu trav.

216
00:11:15,025 --> 00:11:18,970
Es neteicu Trav vienāds malloc
kaut kas, ka mezglā jau pastāv,

217
00:11:18,970 --> 00:11:21,160
ka kosmosa atmiņā jau eksistē.

218
00:11:21,160 --> 00:11:24,290
Tāpēc es esmu patiesībā dara, ir
radot vēl vienu rādītāju uz to.

219
00:11:24,290 --> 00:11:28,210
Es neesmu mallocing papildu
telpa, tikai tagad ir divas norādes

220
00:11:28,210 --> 00:11:31,370
norādot uz to pašu.

221
00:11:31,370 --> 00:11:33,710
>> Tātad, ir 2, ko es meklēju?

222
00:11:33,710 --> 00:11:37,220
Nu, nē, tā vietā es esmu
gatavojas pārcelties uz nākamo.

223
00:11:37,220 --> 00:11:41,740
Vārdu sakot, es teiktu,
Trav vienāds trav nākamo.

224
00:11:41,740 --> 00:11:43,630
Vai 3, ko es meklēju, nē.

225
00:11:43,630 --> 00:11:45,780
Tāpēc es joprojām iet
cauri, līdz beidzot

226
00:11:45,780 --> 00:11:48,690
nokļūt līdz 6., kas ir tas, ko es esmu meklē
, kas balstās uz funkciju zvanu

227
00:11:48,690 --> 00:11:51,600
Man ir augšpusē
tur, un tāpēc es esmu darīts.

228
00:11:51,600 --> 00:11:54,150
>> Tagad, kas notiks, ja elements es esmu
meklē nav sarakstā,

229
00:11:54,150 --> 00:11:55,510
tas joprojām iet uz darbu?

230
00:11:55,510 --> 00:11:57,120
Nu, ievērosiet, ka saraksts
šeit ir smalki atšķirīgs,

231
00:11:57,120 --> 00:11:59,410
un šī ir vēl viena lieta, kas ir
svarīgi ar saistītiem sarakstiem,

232
00:11:59,410 --> 00:12:01,780
jums nav, lai saglabātu
viņiem konkrētā secībā.

233
00:12:01,780 --> 00:12:05,390
Jūs varat, ja vēlaties, bet
Jums var būt jau pamanījuši

234
00:12:05,390 --> 00:12:09,310
ka mēs neesam sekotu
ko numurs elements mēs esam.

235
00:12:09,310 --> 00:12:13,150
>> Un tas ir sava veida vienas tirdzniecības ka mēs
ir ar saistīts saraksts vārsmas blokiem

236
00:12:13,150 --> 00:12:15,300
tas mums nav
brīvpiekļuves vairs.

237
00:12:15,300 --> 00:12:18,150
Mēs nevaram vienkārši teikt, es gribu
iet uz 0th elementu,

238
00:12:18,150 --> 00:12:21,410
vai 6. mana masīva elements
ko es varu darīt masīvā.

239
00:12:21,410 --> 00:12:25,080
Es nevaru teikt, es gribu iet uz
0. elements, vai 6. elements,

240
00:12:25,080 --> 00:12:30,360
vai 25. elements mana saistīta saraksta
tur nav rādītājs, kas saistītas ar tām.

241
00:12:30,360 --> 00:12:33,660
Un tā tas nav īsti jautājums
ja mēs saglabātu mūsu sarakstu kārtībā.

242
00:12:33,660 --> 00:12:36,080
Ja jūs vēlaties, lai jums
protams, var, bet tur ir

243
00:12:36,080 --> 00:12:38,567
Nav iemesla, kāpēc viņiem ir nepieciešams
jāsaglabā jebkurā secībā.

244
00:12:38,567 --> 00:12:40,400
Tātad vēlreiz, pamēģināsim un
atrast 6 šajā sarakstā.

245
00:12:40,400 --> 00:12:43,200
Nu, mēs sākam pie
sākuma, mēs neatrodam 6,

246
00:12:43,200 --> 00:12:47,690
un tad mēs turpināsim neatrodot
6, kamēr mēs beidzot nokļūt šeit.

247
00:12:47,690 --> 00:12:52,790
Tāpēc tieši tagad Trav norāda uz mezglā
kas satur 8, un seši nav tur.

248
00:12:52,790 --> 00:12:55,250
>> Tātad nākamais solis būtu
lai dotos uz nākamo rādītāju,

249
00:12:55,250 --> 00:12:57,440
tā teikt Trav vienāds trav nākamo.

250
00:12:57,440 --> 00:13:00,750
Nu, Trav nākamais, kas apzīmēta ar
sarkanā kaste tur, ir nulle.

251
00:13:00,750 --> 00:13:03,020
Tātad tur ir nekur citur
iet, un tāpēc šajā brīdī

252
00:13:03,020 --> 00:13:06,120
mēs varam secināt, ka mēs esam sasnieguši
beigām, kas saistīts saraksta,

253
00:13:06,120 --> 00:13:07,190
un 6 nav tur.

254
00:13:07,190 --> 00:13:10,980
Un tas būtu jāatdod
viltus šajā gadījumā.

255
00:13:10,980 --> 00:13:14,540
>> OK, kā mēs ievietotu jaunu
mezglu uz saistīts sarakstā?

256
00:13:14,540 --> 00:13:17,310
Tātad, mēs esam spējuši radīt
saistītais saraksts no nekurienes,

257
00:13:17,310 --> 00:13:19,370
bet mēs, iespējams, vēlas
veidot ķēdi, un nav

258
00:13:19,370 --> 00:13:22,620
izveidot ķekars atšķirīgas sarakstos.

259
00:13:22,620 --> 00:13:25,700
Mēs vēlamies, lai būtu vienu sarakstu, kas
ir ķekars mezglu tā,

260
00:13:25,700 --> 00:13:28,040
nav ķekars sarakstu ar vienu mezglu.

261
00:13:28,040 --> 00:13:31,260
Tātad, mēs varam ne tikai saglabāt, izmantojot Izveidot
funkcija mēs definēts agrāk, tagad mēs

262
00:13:31,260 --> 00:13:33,860
vēlaties ievietot par a
sarakstu, kas jau pastāv.

263
00:13:33,860 --> 00:13:36,499
>> Tātad šajā gadījumā, mēs ejam
iziet uz diviem argumentiem,

264
00:13:36,499 --> 00:13:39,290
rādītājs uz galvas, ka
saistīts saraksts, ko mēs vēlamies pievienot.

265
00:13:39,290 --> 00:13:40,910
Atkal, tas ir iemesls, kāpēc tas ir tik
svarīgi, ka mēs vienmēr

266
00:13:40,910 --> 00:13:43,400
izsekot to, jo
tas ir vienīgais veids, kā mēs patiešām

267
00:13:43,400 --> 00:13:46,690
ir atsaukties uz visa saraksts ir
tikai ar rādītāju uz pirmā elementa.

268
00:13:46,690 --> 00:13:49,360
Tāpēc mēs gribam iet no A
rādītāju uz šo pirmo elementu,

269
00:13:49,360 --> 00:13:52,226
un kāda vērtība mēs
vēlaties pievienot sarakstam.

270
00:13:52,226 --> 00:13:54,600
Un galu galā šī funkcija
gatavojas atgriezties rādītāju

271
00:13:54,600 --> 00:13:57,980
uz jauno vadītāju saistītajā sarakstā.

272
00:13:57,980 --> 00:13:59,700
>> Kādi ir soļi, šeit ir iesaistītas?

273
00:13:59,700 --> 00:14:02,249
Nu, tāpat kā ar izveidot,
mums ir dinamiski piešķirt

274
00:14:02,249 --> 00:14:05,540
telpa par jaunu mezglu, un pārbaudiet,
Noteikti mums nav beigušies atmiņas, atkal,

275
00:14:05,540 --> 00:14:07,150
tāpēc, ka mēs esam izmantojot malloc.

276
00:14:07,150 --> 00:14:09,080
Tad mēs vēlamies aizpildīt
un ievietojiet mezglu,

277
00:14:09,080 --> 00:14:12,730
tāpēc nodot skaitu, kāds
val ir, uz mezglā.

278
00:14:12,730 --> 00:14:17,310
Mēs vēlamies, lai ievietotu mezglu pie
sākums saistīts sarakstā.

279
00:14:17,310 --> 00:14:19,619
>> Tur ir iemesls, ka es
gribu darīt, un tas

280
00:14:19,619 --> 00:14:21,910
varētu būt vērts otru
lai apturētu video šeit,

281
00:14:21,910 --> 00:14:25,860
un domāt par to, kāpēc es gribētu
ievietot sākumā saistītais

282
00:14:25,860 --> 00:14:26,589
saraksts.

283
00:14:26,589 --> 00:14:28,630
Atkal, es iepriekš minēju
ka tas nav īsti

284
00:14:28,630 --> 00:14:33,020
svarīgi, ja mēs saglabātu to jebkurš
pasūtījums, tāpēc varbūt tas ir pavediens.

285
00:14:33,020 --> 00:14:36,040
Un redzējāt kas notiktu, ja mēs
vēlējās kuri paredzēti, vai tikai sekundi

286
00:14:36,040 --> 00:14:37,360
atpakaļ, kad mēs gatavojamies
izmantojot meklēšanas jūs

287
00:14:37,360 --> 00:14:39,235
varēja redzēt, ko varētu
notikt, ja mēs cenšamies

288
00:14:39,235 --> 00:14:41,330
ievietot beigās saraksta.

289
00:14:41,330 --> 00:14:44,750
Jo mums nav
rādītāju uz saraksta beigām.

290
00:14:44,750 --> 00:14:47,490
>> Tātad iemesls, ka es gribētu
ievietot sākumā,

291
00:14:47,490 --> 00:14:49,380
ir tāpēc, ka es varu darīt to nekavējoties.

292
00:14:49,380 --> 00:14:52,730
Man ir rādītāju sākumā, un
mēs redzēsim to vizuālais sekundē.

293
00:14:52,730 --> 00:14:55,605
Bet, ja es gribu, lai ievietotu beigās,
Man ir jāsāk sākumā,

294
00:14:55,605 --> 00:14:58,760
šķērsotu visu ceļu uz
gals, un pēc tam tack to.

295
00:14:58,760 --> 00:15:01,420
Tātad tas nozīmē, ka
ievietojot beigās saraksta

296
00:15:01,420 --> 00:15:04,140
kļūtu par o n
ekspluatācija, atgriežās

297
00:15:04,140 --> 00:15:06,720
mūsu diskusijā
skaitļošanas sarežģītība.

298
00:15:06,720 --> 00:15:10,140
Tā, lūdzu kļūt par o n operācijas, kur
jo saraksts got lielāks, un lielāks,

299
00:15:10,140 --> 00:15:13,310
un lielāks, tas būs kļuvis vairāk un
grūtāk sadiegšana kaut ko

300
00:15:13,310 --> 00:15:14,661
uz beigās.

301
00:15:14,661 --> 00:15:17,410
Bet tas vienmēr ir ļoti viegli
sadiegšana kaut ko sākumā,

302
00:15:17,410 --> 00:15:19,060
jūs vienmēr sākumā.

303
00:15:19,060 --> 00:15:21,620
>> Un mēs redzēsim vizuāli tas atkal.

304
00:15:21,620 --> 00:15:24,100
Un tad, kad mēs esam darīts, tiklīdz
mēs esam iekļauj jaunu mezglu,

305
00:15:24,100 --> 00:15:26,880
mēs gribam atgriezties mūsu rādītāju
jaunais vadītājs saistītajā sarakstā, kas

306
00:15:26,880 --> 00:15:29,213
jo mēs esam ievietojot pie
sākumā, faktiski būs

307
00:15:29,213 --> 00:15:31,060
rādītāju uz mezglu mēs tikko izveidojāt.

308
00:15:31,060 --> 00:15:33,280
Pieņemsim vizualizēt to,
jo es domāju, ka tas tev palīdzēs.

309
00:15:33,280 --> 00:15:36,661
>> Tātad, šeit ir mūsu sarakstā, tas sastāv no
četri elementi, mezgls, kas satur 15,

310
00:15:36,661 --> 00:15:38,410
kas norāda uz mezglu
kas satur 9, kas

311
00:15:38,410 --> 00:15:41,370
norāda uz mezglu, kas satur 13,
kas norāda uz mezglu, kas satur

312
00:15:41,370 --> 00:15:44,840
10, kas ir null
rādītājs kā savu nākamo rādītājs

313
00:15:44,840 --> 00:15:47,010
tā, ka ir beigu sarakstā.

314
00:15:47,010 --> 00:15:50,200
Tāpēc mēs vēlamies, lai ievietotu
jaunu mezglu ar vērtību 12

315
00:15:50,200 --> 00:15:52,720
sākumā tas
saraksts, ko mēs darām?

316
00:15:52,720 --> 00:15:58,770
Nu, vispirms mums malloc telpu, lai
mezglā, un tad mēs ieliekam 12 tur.

317
00:15:58,770 --> 00:16:02,211
>> Tāpēc tagad mēs esam sasnieguši
lēmuma pieņemšanas punkts, vai ne?

318
00:16:02,211 --> 00:16:03,960
Mums ir pāris
norādes, ka mēs varētu

319
00:16:03,960 --> 00:16:06,770
pārvietot, kuriem viens mums vajadzētu virzīties vispirms?

320
00:16:06,770 --> 00:16:09,250
Vai mums vajadzētu veikt 12 norāda uz
jaunais vadītājs list--

321
00:16:09,250 --> 00:16:13,020
vai atvainojiet, mums vajadzētu darīt 12
norāda uz veco galvas sarakstā?

322
00:16:13,020 --> 00:16:15,319
Vai mums vajadzētu teikt, ka
Tagad sarakstā sākas 12.

323
00:16:15,319 --> 00:16:17,110
Tur ir atšķirība
tur, un mēs apskatīt

324
00:16:17,110 --> 00:16:19,870
to, kas notiek gan ar sekundē.

325
00:16:19,870 --> 00:16:23,350
>> Bet tas noved pie
liels temats sānjoslas,

326
00:16:23,350 --> 00:16:26,280
kas ir, ka viens no
sarežģītākajiem lietas ar saistītiem sarakstiem

327
00:16:26,280 --> 00:16:30,980
ir sakārtot norādes
pareizā secībā.

328
00:16:30,980 --> 00:16:34,520
Ja jūs pārvietot lietas no rīkojuma,
Jūs varat nonākt nejauši

329
00:16:34,520 --> 00:16:36,050
orphaning pārējo saraksta.

330
00:16:36,050 --> 00:16:37,300
Un šeit ir piemērs, ka.

331
00:16:37,300 --> 00:16:40,540
So iesim ar ideju of--
labi, mēs esam tikko izveidots 12.

332
00:16:40,540 --> 00:16:43,180
Mēs zinām, 12 būs
jaunais vadītājs saraksta,

333
00:16:43,180 --> 00:16:47,660
un tad kāpēc nav mēs vienkārši pārvietot
saraksts rādītājs norādīt tur.

334
00:16:47,660 --> 00:16:49,070
>> Labi, tā ka ir labi.

335
00:16:49,070 --> 00:16:51,560
Tāpēc tagad, kad tas 12. nākamo punktu?

336
00:16:51,560 --> 00:16:54,580
Es domāju, vizuāli mēs varam redzēt
ka tas norāda uz 15,

337
00:16:54,580 --> 00:16:57,250
kā cilvēkiem tas ir patiešām skaidrs mums.

338
00:16:57,250 --> 00:17:00,300
Kā dators zināt?

339
00:17:00,300 --> 00:17:02,720
Mums nav nekas
norādot uz 15 vairs, vai ne?

340
00:17:02,720 --> 00:17:05,869
>> Mēs esam zaudējuši jebkādu iespēju atsaukties uz 15.

341
00:17:05,869 --> 00:17:11,460
Mēs nevaram teikt, jauns bultiņas blakus Vienāds
kaut kas, tur nekas tur.

342
00:17:11,460 --> 00:17:13,510
Patiesībā, mēs esam bāreņiem
pārējā saraksta

343
00:17:13,510 --> 00:17:16,465
to darot, mēs esam
nejauši sadalīti ķēdi.

344
00:17:16,465 --> 00:17:18,089
Un mēs noteikti nevēlamies to darīt.

345
00:17:18,089 --> 00:17:20,000
>> So iesim atpakaļ un mēģināt to vēlreiz.

346
00:17:20,000 --> 00:17:24,060
Varbūt pareizi darīt
ir noteikt 12 nākamais rādītāju

347
00:17:24,060 --> 00:17:28,290
uz veco galvas saraksta pirmā,
tad mēs varam virzīties sarakstu pāri.

348
00:17:28,290 --> 00:17:30,420
Un faktiski, ka ir
pareizi, lai mēs

349
00:17:30,420 --> 00:17:32,836
nepieciešams sekot, kad mēs esam
Strādājot ar atsevišķi saistīta sarakstā.

350
00:17:32,836 --> 00:17:36,460
Mēs vienmēr vēlamies, lai savienotu
jauns elements uz sarakstā,

351
00:17:36,460 --> 00:17:41,010
Pirms mēs šāda veida
nozīmīgs solis mainīt

352
00:17:41,010 --> 00:17:43,360
kur galva saistīts saraksts ir.

353
00:17:43,360 --> 00:17:46,740
Atkal, tas ir tik būtiska lieta,
mēs negribam pazaudēt to.

354
00:17:46,740 --> 00:17:49,310
>> Tāpēc mēs vēlamies, lai pārliecinātos, ka
viss ir chained kopā,

355
00:17:49,310 --> 00:17:52,040
Pirms mēs virzāmies šo rādītāju.

356
00:17:52,040 --> 00:17:55,300
Un tā tas būtu pareizā secībā,
kas ir savienojumu 12, lai saraksta,

357
00:17:55,300 --> 00:17:57,630
tad saka, ka saraksts sāk 12.

358
00:17:57,630 --> 00:18:00,860
Ja mēs teicām saraksts sākas 12. un
tad mēģināju savienot 12 sarakstā,

359
00:18:00,860 --> 00:18:02,193
mēs jau esam redzējuši, kas notiek.

360
00:18:02,193 --> 00:18:04,920
Mēs zaudējam sarakstu kļūdas.

361
00:18:04,920 --> 00:18:06,740
>> Labi, tāpēc vēl viena lieta runāt.

362
00:18:06,740 --> 00:18:09,750
Ko darīt, ja mēs gribam, lai atbrīvotos no
vesela saistīta sarakstu uzreiz?

363
00:18:09,750 --> 00:18:11,750
Atgādināsim, ka mēs esam mallocing
visu šo vietu, un tāpēc mēs

364
00:18:11,750 --> 00:18:13,351
ir nepieciešams, lai atbrīvotu to, kad mēs esam darījuši.

365
00:18:13,351 --> 00:18:15,350
Tāpēc tagad mēs vēlamies, lai izdzēstu
viss saistīts saraksts.

366
00:18:15,350 --> 00:18:16,850
Nu, ko mēs vēlamies darīt?

367
00:18:16,850 --> 00:18:20,460
>> Ja mēs esam sasnieguši null rādītāju, mēs
vēlaties pārtraukt, citādi, tāpat izdzēst

368
00:18:20,460 --> 00:18:23,420
pārējā saraksta un pēc tam atbrīvot mani.

369
00:18:23,420 --> 00:18:28,890
Dzēst pārējā saraksta
un pēc tam atbrīvot pašreizējo mezglā.

370
00:18:28,890 --> 00:18:32,850
Ko nozīmē, ka skaņas, piemēram,
ko paņēmiens ir mēs runājām

371
00:18:32,850 --> 00:18:35,440
par iepriekš dara, ka skaņas, piemēram?

372
00:18:35,440 --> 00:18:39,560
Dzēst ikviens cits, tad
atgriezties un dzēst mani.

373
00:18:39,560 --> 00:18:42,380
>> Tas ir rekursijas, mēs esam padarījuši
Problēma mazliet mazāks,

374
00:18:42,380 --> 00:18:46,910
mēs esam sakot dzēst visiem
cits, tad jūs varat izdzēst mani.

375
00:18:46,910 --> 00:18:50,940
Un tālāk pa ceļu, kas mezgls
teiks, dzēst ikviens cits.

376
00:18:50,940 --> 00:18:53,940
Bet galu galā mēs nokļūt uz
punkts, kurā saraksts ir spēkā,

377
00:18:53,940 --> 00:18:55,310
un tas ir mūsu bāze gadījums.

378
00:18:55,310 --> 00:18:57,010
>> Tātad, pieņemsim to apskatīt to,
un kā tas varētu darboties.

379
00:18:57,010 --> 00:18:59,759
Tātad, šeit ir mūsu sarakstā, tas ir tas pats
uzskaitīt mēs bijām tikai runā par,

380
00:18:59,759 --> 00:19:00,980
un tur ir soļi.

381
00:19:00,980 --> 00:19:04,200
Tur ir daudz tekstu šeit, bet
cerams, ka vizualizācija palīdzēs.

382
00:19:04,200 --> 00:19:08,557
>> Tātad mēs have-- un es arī velk
up mūsu kaudze rāmji ilustrācija

383
00:19:08,557 --> 00:19:10,890
no mūsu video zvanu skursteņi,
un cerams, ka tas viss

384
00:19:10,890 --> 00:19:13,260
kopā jums parādīs to, kas notiek.

385
00:19:13,260 --> 00:19:14,510
Tātad, šeit ir mūsu pseudocode kods.

386
00:19:14,510 --> 00:19:17,830
Ja mēs sasniedzam null
rādītājs, stop, pretējā gadījumā,

387
00:19:17,830 --> 00:19:21,320
izdzēst pārējā saraksta
tad bez pašreizējo mezglā.

388
00:19:21,320 --> 00:19:25,700
Tāpēc tieši tagad, list--
rādītājs, ka mēs esam

389
00:19:25,700 --> 00:19:28,410
iet, lai iznīcinātu punktus 12.

390
00:19:28,410 --> 00:19:33,340
12 nav spēkā rādītājs, tāpēc mēs esam
gatavojas dzēst pārējo saraksta.

391
00:19:33,340 --> 00:19:35,450
>> Kas ir izdzēšot
mums pārējiem iesaistīti?

392
00:19:35,450 --> 00:19:37,950
Nu, tas nozīmē, padarot
zvanīt, lai iznīcinātu, sakot

393
00:19:37,950 --> 00:19:42,060
ka 15 ir sākums
pārējā saraksta mēs vēlamies, lai iznīcinātu.

394
00:19:42,060 --> 00:19:47,480
Un tā aicinājums iznīcināt
12 ir veida aizturēts.

395
00:19:47,480 --> 00:19:52,690
Tas ir iesaldēti tur, gaida
zvanīt, lai iznīcinātu 15, lai pabeigtu savu darbu.

396
00:19:52,690 --> 00:19:56,280
>> Nu, 15 nav spēkā rādītājs, un
tā tas notiek, lai teikt, labi,

397
00:19:56,280 --> 00:19:58,450
labi, dzēst pārējo saraksta.

398
00:19:58,450 --> 00:20:00,760
No saraksta pārējais sākas
9, un tāpēc mēs vienkārši

399
00:20:00,760 --> 00:20:04,514
gaidīt, kamēr jūs izdzēst visu, kas
sīkumi, pēc tam nāk atpakaļ un dzēst mani.

400
00:20:04,514 --> 00:20:06,680
Nu 9 gatavojas teikt, labi,
Es neesmu Null rādītājs,

401
00:20:06,680 --> 00:20:09,020
lai dzēstu pārējo sarakstu no šejienes.

402
00:20:09,020 --> 00:20:11,805
Un tā mēģinātu iznīcināt 13.

403
00:20:11,805 --> 00:20:15,550
13 saka, es neesmu null rādītājs,
tas pats, tas iet buks.

404
00:20:15,550 --> 00:20:17,930
10 nav spēkā rādītājs, 10
satur Null rādītāju,

405
00:20:17,930 --> 00:20:20,200
bet 10 ir pati nav
null rādītāju tieši tagad,

406
00:20:20,200 --> 00:20:22,470
un tā tas iet buks too.

407
00:20:22,470 --> 00:20:25,560
>> Un tagad uzskaitīt punktus tur, to
tiešām norāda uz some--

408
00:20:25,560 --> 00:20:28,710
ja man būtu vairāk vietas attēlā,
tas norāda uz kādu izlases vietu

409
00:20:28,710 --> 00:20:29,960
ka mēs nezinām, kas tas ir.

410
00:20:29,960 --> 00:20:34,680
Tas ir null rādītājs gan, saraksts
ir burtiski tagad ir noteikts tā vērtības Null.

411
00:20:34,680 --> 00:20:36,820
Tas norāda tieši no šī sarkanā kastē.

412
00:20:36,820 --> 00:20:39,960
Mēs sasnieguši null rādītāju, tāpēc
mēs varam apturēt, un mēs esam darījuši.

413
00:20:39,960 --> 00:20:46,230
>> Un tā, ka purpursarkana rāmis ir now-- pie
top stack-- kas ir aktīvā rāmis,

414
00:20:46,230 --> 00:20:47,017
bet tas ir darīts.

415
00:20:47,017 --> 00:20:48,600
Ja mēs esam sasnieguši null rādītāju, apstāties.

416
00:20:48,600 --> 00:20:51,290
Mēs nedarām neko, mēs
nevar atbrīvoties Null rādītāju,

417
00:20:51,290 --> 00:20:55,070
mēs neesam malloc jebkurš
telpu, un tāpēc mēs esam darījuši.

418
00:20:55,070 --> 00:20:57,590
Tātad šī funkcija rāmis
tiek iznīcināta, un mēs

419
00:20:57,590 --> 00:21:00,930
resume-- mēs uzņemt kur mēs pa kreisi
off ar nākamo augstāko vienu, kas

420
00:21:00,930 --> 00:21:02,807
tas ir tumši zils rāmis šeit.

421
00:21:02,807 --> 00:21:04,390
Tāpēc mēs uzņemt tieši tur, kur mēs left off.

422
00:21:04,390 --> 00:21:06,598
Mēs svītrots pārējā
saraksts jau, tāpēc tagad mēs esam

423
00:21:06,598 --> 00:21:08,000
gatavojas atbrīvot pašreizējās mezgliem.

424
00:21:08,000 --> 00:21:12,920
Tāpēc tagad mēs varam atbrīvot šo mezglu, un tagad
mēs esam sasnieguši funkciju.

425
00:21:12,920 --> 00:21:16,810
Un tā, ka funkcija rāmis ir iznīcināta,
un mēs uzņemt pie gaiši zilu.

426
00:21:16,810 --> 00:21:20,650
>> Tātad tas says-- es esmu jau done--
svītrojot pārējo saraksta, tāpēc

427
00:21:20,650 --> 00:21:23,140
atbrīvotu pašreizējo mezglā.

428
00:21:23,140 --> 00:21:26,520
Un tagad dzeltens rāmis ir
atpakaļ uz augšu kaudze.

429
00:21:26,520 --> 00:21:29,655
Un tā kā jūs redzat, mēs esam tagad
iznīcinot sarakstu no labās uz kreiso pusi.

430
00:21:29,655 --> 00:21:33,710

431
00:21:33,710 --> 00:21:37,280
>> Kas būtu noticis, lai gan,
ja mēs būtu darījuši lietas nepareizi?

432
00:21:37,280 --> 00:21:39,410
Tāpat kā tad, kad mēs mēģinājām
pievienot elementu.

433
00:21:39,410 --> 00:21:41,909
Ja mēs messed up ķēdi, ja
mēs neesam savienot norādes

434
00:21:41,909 --> 00:21:44,690
pareizā secībā, ja mēs
tikai atbrīvoja pirmo elementu,

435
00:21:44,690 --> 00:21:47,420
ja mēs vienkārši viņus atlaida
vadītājs saraksta, tagad mēs

436
00:21:47,420 --> 00:21:49,642
nav veids, kā atsaukties uz
pārējā sarakstā.

437
00:21:49,642 --> 00:21:51,350
Un tā mēs būtu
bāreņiem viss,

438
00:21:51,350 --> 00:21:53,880
mēs būtu to, kas ir
sauc par atmiņas noplūde.

439
00:21:53,880 --> 00:21:56,800
Ja jūs atceraties no mūsu video
uz dinamisku atmiņas sadalījumu,

440
00:21:56,800 --> 00:21:58,650
tas nav ļoti laba lieta.

441
00:21:58,650 --> 00:22:00,810
>> Tā kā es teicu, ka
Ir vairākas operācijas

442
00:22:00,810 --> 00:22:04,010
ka mums ir nepieciešams izmantot, lai strādātu
ar saistīts saraksts efektīvi.

443
00:22:04,010 --> 00:22:08,430
Un jums var būt ievērojuši, es izlaist vienu,
izdzēšot vienu elementu no saistītais

444
00:22:08,430 --> 00:22:09,064
saraksts.

445
00:22:09,064 --> 00:22:10,980
Iemesls, kāpēc es to izdarīju
tas ir faktiski sava veida

446
00:22:10,980 --> 00:22:14,360
grūts domāt par to, kā izdzēst
viens elements no A atsevišķi

447
00:22:14,360 --> 00:22:15,600
saistīts saraksts.

448
00:22:15,600 --> 00:22:19,950
Mums ir nepieciešams, lai varētu izlaist
kaut kas sarakstā, kas

449
00:22:19,950 --> 00:22:22,975
nozīmē, ka mēs nokļūt point-- mēs
vēlies dzēst šo node--

450
00:22:22,975 --> 00:22:25,350
bet, lai padarītu to, lai mēs
nezaudē nekādu informāciju,

451
00:22:25,350 --> 00:22:30,530
mums ir nepieciešams, lai savienotu šo
mezglu nekā šeit, šeit.

452
00:22:30,530 --> 00:22:33,390
>> Tāpēc es droši vien bija, ka nepareizi
no vizuālā viedokļa.

453
00:22:33,390 --> 00:22:36,830
Tātad mēs esam sākumā mūsu
saraksts, mēs esam visnotaļ cauri,

454
00:22:36,830 --> 00:22:40,510
mēs vēlamies, lai izdzēstu šo mezglu.

455
00:22:40,510 --> 00:22:43,440
Ja mēs vienkārši izdzēst to,
mēs esam sadalīti ķēdi.

456
00:22:43,440 --> 00:22:45,950
Šis mezgls tieši šeit
attiecas uz visu citu,

457
00:22:45,950 --> 00:22:48,260
tas satur ķēdi no šejienes uz out.

458
00:22:48,260 --> 00:22:51,190
>> Tātad, kas mums jādara, faktiski
kad mēs nokļūt uz šo punktu,

459
00:22:51,190 --> 00:22:56,670
ir mums soli atpakaļ vienu, un
savienot šo mezglu pār šo mezglu,

460
00:22:56,670 --> 00:22:58,590
lai mēs varētu pēc tam izdzēsiet
viens vidū.

461
00:22:58,590 --> 00:23:02,120
Bet atsevišķi saistīti saraksti nav
sniedz mums ceļš ejams atpakaļ.

462
00:23:02,120 --> 00:23:05,160
Tāpēc mums ir nepieciešams paturēt
divas norādes, un pārvietot tos

463
00:23:05,160 --> 00:23:09,527
veida off soli, viens aiz
cits, kā mums iet, vai nokļūt līdz punktam

464
00:23:09,527 --> 00:23:11,110
un pēc tam nosūtīt citu rādītāju cauri.

465
00:23:11,110 --> 00:23:13,150
Un, kā jūs varat redzēt, tas
var iegūt mazliet netīrs.

466
00:23:13,150 --> 00:23:15,360
Par laimi, mums ir
vēl viens veids, kā atrisināt ka,

467
00:23:15,360 --> 00:23:17,810
kad mēs runājam par divkārt saistītas sarakstiem.

468
00:23:17,810 --> 00:23:20,720
>> Es esmu Doug Lloyd, tas ir CS50.

469
00:23:20,720 --> 00:23:22,298