1
00:00:00,000 --> 00:00:02,832
>> [Muzikos grojimo]

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

3
00:00:05,670 --> 00:00:08,560
>> Doug LLOYD: Gerai, kad ne
Šis punktas yra, žinoma,

4
00:00:08,560 --> 00:00:15,300
mes apėmė nuo C pagrindai daug
Mes žinome apie kintamuosius, masyvus daug,

5
00:00:15,300 --> 00:00:17,610
patarimų, visi, kad gerų dalykų.

6
00:00:17,610 --> 00:00:21,610
Tie visi tarsi pastatytas
Norėdami matyti kaip pagrindus,

7
00:00:21,610 --> 00:00:23,880
bet mes galime padaryti daugiau, tiesa?

8
00:00:23,880 --> 00:00:27,930
Mes galime derinti dalykus
kartu įdomių būdų.

9
00:00:27,930 --> 00:00:31,010
>> Ir taip darykime, kad pradėkime
išsišakoti kas C mums suteikia,

10
00:00:31,010 --> 00:00:35,270
ir pradėti kurti savo duomenis
struktūros, naudojant šiuos pastatą

11
00:00:35,270 --> 00:00:40,590
blokai kartu kažką daryti
tikrai vertinga, naudinga.

12
00:00:40,590 --> 00:00:43,420
Vienas iš būdų mes galime tai padaryti
kalbėti apie kolekcijas.

13
00:00:43,420 --> 00:00:48,360
Taigi iki šiol mes turėjome vienos rūšies duomenis
struktūra kolekcijas atstovaujanti

14
00:00:48,360 --> 00:00:51,030
panašaus vertybes, panašias vertybes.

15
00:00:51,030 --> 00:00:52,350
Tai būtų masyvas.

16
00:00:52,350 --> 00:00:57,020
Mes turime kolekcijas skaičiais arba
kolekcijos simbolių ir pan.

17
00:00:57,020 --> 00:01:00,890
>> Konstrukcijos taip pat tarsi duomenis
struktūra rinkti informaciją,

18
00:01:00,890 --> 00:01:03,220
bet tai ne rinkti, kaip vertybes.

19
00:01:03,220 --> 00:01:08,090
Ji paprastai susimaišo įvairių duomenų tipų
kartu viduje viename langelyje.

20
00:01:08,090 --> 00:01:10,750
Bet tai ne pats
naudojamas grandinės kartu

21
00:01:10,750 --> 00:01:16,920
arba prijunkite kartu panašus
elementai, kaip masyvą.

22
00:01:16,920 --> 00:01:20,960
Masyvai yra puikus
elementas ieškoti, bet Prisiminkite

23
00:01:20,960 --> 00:01:24,262
kad tai labai sunku
įterpti į masyvą,

24
00:01:24,262 --> 00:01:26,470
nebent mes įdėti ne
galo tos masyvo.

25
00:01:26,470 --> 00:01:29,730
>> Ir geriausias pavyzdys Turiu
už tai įterpimo rūšiuoti.

26
00:01:29,730 --> 00:01:31,650
Jei prisimenate mūsų vaizdo
intarpų rūšiuoti,

27
00:01:31,650 --> 00:01:34,110
ten buvo daug
sąskaita dalyvauja turintys

28
00:01:34,110 --> 00:01:37,970
pasiimti elementus ir juos perkelti
iš kelio, kad tilptų kažką

29
00:01:37,970 --> 00:01:41,290
į centrą savo masyvo.

30
00:01:41,290 --> 00:01:44,690
Masyvai taip pat kenčia nuo kito
problema, kuri yra nelanksti.

31
00:01:44,690 --> 00:01:47,150
Kai mes pareiškiame masyvą,
mes gauname vieną kadrą į jį.

32
00:01:47,150 --> 00:01:49,790
Mes gauname pasakyti, aš noriu
tai daug elementų.

33
00:01:49,790 --> 00:01:51,940
Gali būti 100, tai gali
būti 1,000, tai gali

34
00:01:51,940 --> 00:01:55,930
būti x, kai x yra skaičius, kad vartotojo
davė mums ne raginimas arba komandą

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

36
00:01:56,630 --> 00:01:59,905
>> Bet mes tik vieną fotografiją tai, mes
negaunu sakykite oh, iš tikrųjų aš

37
00:01:59,905 --> 00:02:04,360
reikia 101, ar man reikia x + 20.

38
00:02:04,360 --> 00:02:07,910
Per vėlu, mes jau paskelbė
masyvas, ir jei mes norime gauti 101 arba X

39
00:02:07,910 --> 00:02:12,050
plius 20, mes turime pripažinti
visiškai skirtingas masyvas,

40
00:02:12,050 --> 00:02:15,540
nukopijuoti visus masyvo elementus
daugiau, ir tada mes turime pakankamai.

41
00:02:15,540 --> 00:02:19,880
O kas, jei mes neteisūs vėl, ką
jei mes iš tikrųjų reikia 102, arba X + 40,

42
00:02:19,880 --> 00:02:21,970
mes turime tai padaryti ir vėl.

43
00:02:21,970 --> 00:02:26,250
Taigi jie labai nelankstus
už dydį mūsų duomenis

44
00:02:26,250 --> 00:02:29,360
bet jei mes deriname kartu kai
iš pagrindų, kad mes jau ve

45
00:02:29,360 --> 00:02:33,230
sužinojo apie rodykles ir struktūrų,
ypač naudojant dinaminį atminties

46
00:02:33,230 --> 00:02:36,180
paskirstymas su malloc, mes
galite įdėti šiuos gabalus kartu

47
00:02:36,180 --> 00:02:40,960
Norėdami sukurti naują duomenų structure-- A
pavieniui susiję sąrašą galime say--

48
00:02:40,960 --> 00:02:45,400
kuri leidžia mums augti ir
trauktis vertybių kolekciją

49
00:02:45,400 --> 00:02:48,800
ir mes Neturime švaistomi erdvę.

50
00:02:48,800 --> 00:02:53,320
>> Taigi dar kartą, mes vadiname šią idėją,
ši sąvoka, susijusiantrosios sąrašas.

51
00:02:53,320 --> 00:02:56,320
Visų pirma, šiame video mes
kalbame apie vieną susietą sąrašą

52
00:02:56,320 --> 00:02:59,185
ir tada kitą vaizdo kalbėsimės
apie dvigubai susiję sąrašus, kurie

53
00:02:59,185 --> 00:03:01,560
yra tik tam tikra tema čia variacija.

54
00:03:01,560 --> 00:03:05,200
Bet atskirai susijusi sąrašas
yra sudaryta iš mazgų,

55
00:03:05,200 --> 00:03:08,559
mazgai tiesiog yra abstrakti term--
tai tik ką aš skambinti

56
00:03:08,559 --> 00:03:10,350
tai yra natūra
struktūra, iš esmės, aš?

57
00:03:10,350 --> 00:03:16,190
Tiesiog ketinate jį vadiname node-- ir tai
mazgas turi du nariai arba du laukus.

58
00:03:16,190 --> 00:03:20,300
Jis turi duomenis, paprastai yra
sveikasis skaičius, simbolis plūdė,

59
00:03:20,300 --> 00:03:23,790
arba gali būti kai kurių kitų duomenų tipas
kad jūs apibrėžti tipo def.

60
00:03:23,790 --> 00:03:29,290
Ir tai yra žymeklį į
kita tos pačios rūšies mazgas.

61
00:03:29,290 --> 00:03:34,710
>> Taigi mes turime du dalykus viduje
Tai mazgas, duomenų ir rodyklė

62
00:03:34,710 --> 00:03:36,380
į kitą mazge.

63
00:03:36,380 --> 00:03:39,370
Ir jei jums pradėti vizualizuoti
tai, ką galima galvoti apie tai

64
00:03:39,370 --> 00:03:42,280
kaip mazgų grandinėje, kad
yra tarpusavyje sujungtos.

65
00:03:42,280 --> 00:03:45,070
Mes turime pirmąjį mazgą, jį
yra duomenų, ir rodyklė

66
00:03:45,070 --> 00:03:49,110
į antrąjį mazgas, kuriame yra
duomenų, ir rodyklė į trečią mazge.

67
00:03:49,110 --> 00:03:52,940
Ir taip, tai kodėl mes tai vadiname
susiję sąrašas, jie tarpusavyje susiję.

68
00:03:52,940 --> 00:03:56,070
>> Ką tai ypatinga
mazgas struktūra atrodo?

69
00:03:56,070 --> 00:04:01,120
Na, jei jūs prisimenate iš mūsų vaizdo
apibrėžti pasirinktinį tipus, su tipo def,

70
00:04:01,120 --> 00:04:05,400
mes galime apibrėžti structure-- ir
įrašykite apibrėžti struktūrą, kaip šis.

71
00:04:05,400 --> 00:04:11,240
tyepdef struct sllist, tada aš
naudojant žodžio vertė čia savavališkai

72
00:04:11,240 --> 00:04:13,891
nurodyti visus duomenų tipą tikrai.

73
00:04:13,891 --> 00:04:16,890
Jūs galite perduoti sveikasis skaičius arba plūdės,
galite turėti viską, ką nori.

74
00:04:16,890 --> 00:04:19,389
Tai ne tik tik
sveikieji skaičiai, ar ko nors panašaus, kad.

75
00:04:19,389 --> 00:04:22,790
Taigi vertė yra tik sutartinis
duomenų tipas, ir tada rodyklė

76
00:04:22,790 --> 00:04:26,310
į kitą to paties tipo mazge.

77
00:04:26,310 --> 00:04:29,690
>> Dabar, ten šiek tiek laimikis
čia su apibrėžti struktūrą

78
00:04:29,690 --> 00:04:33,030
kai jis savarankiškai referuoto struktūra.

79
00:04:33,030 --> 00:04:35,340
Aš turėti laikinas
vardas mano struktūrą.

80
00:04:35,340 --> 00:04:37,640
Pasibaigus dieną aš pabaigos
aiškiai norite jį pavadinti

81
00:04:37,640 --> 00:04:43,030
SLL mazgas, tai galiausiai nauja
pavadinimas dalį mano tipo apibrėžimą,

82
00:04:43,030 --> 00:04:47,450
bet aš negaliu naudoti SLL mazgas
viduryje tai.

83
00:04:47,450 --> 00:04:51,430
Priežastis yra, aš ne
sukūrė tipas vadinamas SLL mazgas

84
00:04:51,430 --> 00:04:55,200
kol aš paspauskite šį galutinį tašką čia.

85
00:04:55,200 --> 00:04:59,720
Iki to momento, aš turėti
Kitas būdas kreiptis į šį duomenų tipą.

86
00:04:59,720 --> 00:05:02,440
>> Ir tai yra savaime
referuoto duomenų tipas.

87
00:05:02,440 --> 00:05:06,314
Tai, s duomenų tipą, turinti
struktūra, kuri yra duomenų,

88
00:05:06,314 --> 00:05:08,480
ir rodyklė į kitą
struktūra yra tokio paties tipo.

89
00:05:08,480 --> 00:05:11,750
Taigi, aš reikia, kad būtų galima kreiptis į
ši duomenų tipas bent laikinai,

90
00:05:11,750 --> 00:05:14,910
taip suteikiant jam laikina
pavadinimas struct sllist

91
00:05:14,910 --> 00:05:18,540
leidžia man tada pasakyti, kad aš noriu
žymiklį į kitą struct sllist,

92
00:05:18,540 --> 00:05:24,690
konstrukto sllist žvaigždė, ir tada
Po Aš baigė apibrėžimą,

93
00:05:24,690 --> 00:05:27,220
Aš dabar gali skambinti šio tipo SLL mazgas.

94
00:05:27,220 --> 00:05:30,520
>> Štai kodėl jūs matote ten
laikinas vardas čia

95
00:05:30,520 --> 00:05:31,879
bet nuolatinis vardas čia.

96
00:05:31,879 --> 00:05:33,920
Kartais jūs galite pamatyti
apibrėžimai struktūros,

97
00:05:33,920 --> 00:05:36,570
kad, pavyzdžiui, yra ne
savarankiškai referuoto, kad

98
00:05:36,570 --> 00:05:39,390
neturiu specifikatorius vardą čia.

99
00:05:39,390 --> 00:05:43,040
Būtų tiesiog pasakyti Typedef konstrukto,
atidaryti garbanotas petnešomis ir tada ją apibrėžti.

100
00:05:43,040 --> 00:05:45,620
Bet jei jūs konstrukto yra savaime
referentiški, kaip tai vienas,

101
00:05:45,620 --> 00:05:49,010
Jums reikia nurodyti
laikinas tipo pavadinimą.

102
00:05:49,010 --> 00:05:51,310
Bet galiausiai, dabar
kad mes padarėme tai,

103
00:05:51,310 --> 00:05:53,620
mes galime tik nuoroda į
Šie mazgai, tie vienetai,

104
00:05:53,620 --> 00:05:57,900
kaip SLL mazgų tikslais
iš šio vaizdo poilsio.

105
00:05:57,900 --> 00:06:00,900
>> Gerai, kad mes žinome, kaip
sukurti susietą sąrašą mazgas.

106
00:06:00,900 --> 00:06:03,240
Mes žinome, kaip apibrėžti
susijusiantrosios sąrašas mazgas.

107
00:06:03,240 --> 00:06:06,670
Dabar, jei mes ketiname pradėti
naudojant juos surinkti informaciją,

108
00:06:06,670 --> 00:06:10,360
ten operacijų pora mes
reikia suprasti ir dirbti.

109
00:06:10,360 --> 00:06:12,860
Mums reikia žinoti, kaip sukurti
susijusiantrosios sąrašas iš plonos oro.

110
00:06:12,860 --> 00:06:14,901
Jei nėra sąraše jau,
norime pradėti vieną.

111
00:06:14,901 --> 00:06:16,960
Taigi mums reikia, kad būtų galima
sukurti susietą sąrašą

112
00:06:16,960 --> 00:06:19,130
turime tikriausiai paiešką
per nuorodą sąrašo

113
00:06:19,130 --> 00:06:21,830
rasti elementą mes ieškome.

114
00:06:21,830 --> 00:06:24,430
Turime, kad būtų galima įterpti
naujų dalykų į sąrašą,

115
00:06:24,430 --> 00:06:25,930
norime, kad mūsų sąrašas, kad būtų galima augti.

116
00:06:25,930 --> 00:06:28,638
Ir panašiai, norime, kad būtų galima
ištrinti dalykų iš mūsų sąrašo,

117
00:06:28,638 --> 00:06:30,250
mes norime, kad mūsų sąrašas, kad būtų galima trauktis.

118
00:06:30,250 --> 00:06:32,160
Ir pabaigoje mūsų
programos, ypač

119
00:06:32,160 --> 00:06:34,550
Jei prisimenate, kad mes
dinamiškai paskirstyti atmintį

120
00:06:34,550 --> 00:06:38,337
statyti šiuos sąrašus paprastai,
norime atlaisvinti visus, kad atminties

121
00:06:38,337 --> 00:06:39,670
kai mes baigsime dirbti su juo.

122
00:06:39,670 --> 00:06:44,627
Ir todėl mes turime gebėti ištrinti
Visa susijusi sąrašas viena nesugeba smigimas.

123
00:06:44,627 --> 00:06:46,460
Taigi eikime per
kai kurie iš šių operacijų

124
00:06:46,460 --> 00:06:51,192
ir kaip mes galime vizualizuoti juos,
kalbėti Pseudocode kodas specialiai.

125
00:06:51,192 --> 00:06:53,150
Taigi, mes norime sukurti
susiję sąrašą, todėl galbūt mes

126
00:06:53,150 --> 00:06:56,480
nori apibrėžti funkciją
su šiuo prototipu.

127
00:06:56,480 --> 00:07:01,690
SLL mazgas žvaigždė, kurti, ir aš artimųjų
vienoje argumentas, kai savavališkai duomenys

128
00:07:01,690 --> 00:07:05,530
įrašykite vėl, kai kurių savavališkai duomenų tipą.

129
00:07:05,530 --> 00:07:10,482
Bet aš returning-- šią funkciją turėtų
grįžti į mane rodyklę, iki A pavieniui

130
00:07:10,482 --> 00:07:11,190
susiję sąrašas mazgas.

131
00:07:11,190 --> 00:07:14,050
Vėlgi, mes bandome sukurti
susijusiantrosios sąrašas iš plonos oro,

132
00:07:14,050 --> 00:07:17,900
todėl man reikia rodyklę į
tas sąrašas, kai aš padariau.

133
00:07:17,900 --> 00:07:19,420
>> Taigi, kas yra žingsniai čia dalyvauja?

134
00:07:19,420 --> 00:07:20,960
Na, aš pirmas dalykas, tikiu,
ketina daryti dinamiškai

135
00:07:20,960 --> 00:07:22,550
skirti vietos naują mazge.

136
00:07:22,550 --> 00:07:26,689
Vėlgi, mes jį kurti iš plonos
oro, todėl turime malloc erdvėje už jį.

137
00:07:26,689 --> 00:07:28,480
Ir, žinoma, iš karto
kai mes malloc,

138
00:07:28,480 --> 00:07:31,692
mes visada įsitikinkite, kad mūsų
pointer-- mes ne grįžti null.

139
00:07:31,692 --> 00:07:33,650
Nes jei mes stengiamės ir
Gerokai null žymeklį,

140
00:07:33,650 --> 00:07:36,190
mes ketiname patirti
segfault ir mes nenorime, kad.

141
00:07:36,190 --> 00:07:39,510
>> Tada norime užpildyti lauką,
mes norime inicijuoti vertės lauką

142
00:07:39,510 --> 00:07:41,690
inicijuoti ir kitą lauką.

143
00:07:41,690 --> 00:07:45,450
Ir tada mes norime to-- galiausiai kaip
funkcija prototipas indicates-- norime

144
00:07:45,450 --> 00:07:49,940
grįžti žymiklį į SLL mazgas.

145
00:07:49,940 --> 00:07:51,710
Taigi, kas daro šį atrodyti vizualiai?

146
00:07:51,710 --> 00:07:55,230
Na, visų pirma mes ketiname dinamiškai
skirti vietos naują SLL mazgas,

147
00:07:55,230 --> 00:07:58,320
todėl mes malloc-- tai
vaizdinis

148
00:07:58,320 --> 00:08:00,020
mazgas, mes ką tik sukūrėte.

149
00:08:00,020 --> 00:08:02,757
Ir mes įsitikinkite, kad
tai ne null-- šiuo atveju,

150
00:08:02,757 --> 00:08:04,840
vaizdas nebūtų
parodyta iki, jei jis buvo niekinis,

151
00:08:04,840 --> 00:08:07,298
būtume paleisti iš atminties,
todėl mes gerai ten.

152
00:08:07,298 --> 00:08:10,200
Taigi, dabar mes apie dėti C,
inicijuoti mazgai vertės lauką.

153
00:08:10,200 --> 00:08:12,280
Na, remiantis šia funkcija
skambinti Aš naudoju čia

154
00:08:12,280 --> 00:08:16,700
atrodo noriu praeiti 6,
todėl aš 6 į vertės lauką.

155
00:08:16,700 --> 00:08:18,865
Dabar, inicijuoti kitą lauką.

156
00:08:18,865 --> 00:08:21,640
Na, ką aš ketinu ten daryti,
nėra nieko šalia, tiesa,

157
00:08:21,640 --> 00:08:23,600
tai yra vienintelis dalykas, į sąrašą.

158
00:08:23,600 --> 00:08:27,206
Taigi, kas yra kitas dalykas, sąraše?

159
00:08:27,206 --> 00:08:29,660
>> Jis neturėtų ko nors, kas, tiesa.

160
00:08:29,660 --> 00:08:33,600
Nėra nieko kito ten, kad kas
sąvoka mes žinome, kad tai nothing--

161
00:08:33,600 --> 00:08:35,638
rodykles į nieką?

162
00:08:35,638 --> 00:08:37,929
Ji turėtų būti gal mes nori
įdėti null žymeklį ten,

163
00:08:37,929 --> 00:08:40,178
ir aš atstovauti null
žymiklį, kaip tik raudoną langelį,

164
00:08:40,178 --> 00:08:41,559
mes negalime eiti toliau.

165
00:08:41,559 --> 00:08:44,430
Kaip matysime truputį vėliau,
turėsime galiausiai grandines

166
00:08:44,430 --> 00:08:46,330
strėlės prijungti
šie mazgai kartu,

167
00:08:46,330 --> 00:08:48,480
bet kai paspausite
raudona dėžutė, tai niekinis,

168
00:08:48,480 --> 00:08:51,150
mes negalime eiti toliau,
tai iš sąrašo gale.

169
00:08:51,150 --> 00:08:53,960
>> Ir galiausiai, mes tiesiog norime
grįžti žymiklį į šį mazgą.

170
00:08:53,960 --> 00:08:56,160
Taigi mes jį vadiname naujas,
ir grįš naujo

171
00:08:56,160 --> 00:08:59,370
todėl jis gali būti naudojamas
kokia funkcija jis sukurtas.

172
00:08:59,370 --> 00:09:03,100
Taigi mes einame, Sukūrėme atskirai
susiję sąrašas mazgas iš plonos oro,

173
00:09:03,100 --> 00:09:05,920
ir dabar mes turime sąrašą galime dirbti.

174
00:09:05,920 --> 00:09:08,260
>> Dabar, tarkime, mes jau
turime didelę grandinę,

175
00:09:08,260 --> 00:09:09,800
ir mes norime, kad rasti kažką į jį.

176
00:09:09,800 --> 00:09:12,716
Ir mes norime funkciją, kas vyksta
grįžti true arba false, priklausomai nuo

177
00:09:12,716 --> 00:09:15,840
nuo to, ar tai yra, vertės egzistuoja tame sąraše.

178
00:09:15,840 --> 00:09:18,160
Funkcija prototipas, arba
deklaracija šią funkciją,

179
00:09:18,160 --> 00:09:23,320
gali atrodyti this-- bool Rasti,
tada mes norime perduoti dviem argumentais.

180
00:09:23,320 --> 00:09:26,996
>> Pirmoji yra rodyklė į
Pirmasis elementas susijęs sąrašą.

181
00:09:26,996 --> 00:09:29,620
Tai tikrai kažkas jums
visada nori sekti,

182
00:09:29,620 --> 00:09:33,110
ir iš tikrųjų gali būti kažkas, kad
Jūs netgi atsižvelgiant į pasaulinį kintamąjį.

183
00:09:33,110 --> 00:09:35,360
Sukūrę sąrašą
Jūs visada, visada

184
00:09:35,360 --> 00:09:38,990
nori sekti labai
pirmasis elementas sąrašo.

185
00:09:38,990 --> 00:09:43,690
Tokiu būdu jūs galite kreiptis į visus kitus
elementai, tiesiog po grandinėje,

186
00:09:43,690 --> 00:09:47,300
nereikalaujant išlaikyti patarimų
nepažeistas į kiekvieną elementą.

187
00:09:47,300 --> 00:09:50,920
Jums tik reikia sekti pirmas
viena, jei jie visi grandinines kartu.

188
00:09:50,920 --> 00:09:52,460
>> Ir tada antras dalykas
mes artimųjų vėl

189
00:09:52,460 --> 00:09:54,376
yra savavališkai some--
kokia duomenų tipas mes

190
00:09:54,376 --> 00:09:59,640
ieško ten yra viduje
tikiuosi viena iš sąrašo mazgų.

191
00:09:59,640 --> 00:10:00,980
Taigi, kas yra žingsniai?

192
00:10:00,980 --> 00:10:04,250
Na, pirmas dalykas, kurį mes darome, yra
mes sukurti horizontalų žymiklį

193
00:10:04,250 --> 00:10:06,015
nukreipta į sąrašus galvos.

194
00:10:06,015 --> 00:10:08,890
Na, kodėl mes galime padaryti, kad mes jau
turėti žymiklį į sąrašus galvos,

195
00:10:08,890 --> 00:10:10,974
kodėl ne mes tiesiog perkelti, kad vienas aplink?

196
00:10:10,974 --> 00:10:13,140
Na, kaip aš ką tik pasakė,
tai tikrai svarbu mums

197
00:10:13,140 --> 00:10:17,580
visada sekti
labai pirmasis elementas į sąrašą.

198
00:10:17,580 --> 00:10:21,270
Ir taip tai tikrai geriau
sukurti, kad dublikatą,

199
00:10:21,270 --> 00:10:25,350
ir naudoti, kad judėti, todėl mes niekada
netyčia tolti arba mes visada

200
00:10:25,350 --> 00:10:30,430
turi tam tikru momentu, kuris yra žymiklį
tiesiai ant pirmojo elemento sąrašo.

201
00:10:30,430 --> 00:10:33,290
Taigi, tai geriau sukurti
antrasis, kad mes naudoti judėti.

202
00:10:33,290 --> 00:10:35,877
>> Tada mes tiesiog palyginti, ar
vertė laukas tuo mazgu

203
00:10:35,877 --> 00:10:38,960
yra tai, ką mes ieškome, ir jei tai
ne, mes tiesiog perkelti į kitą mazgą.

204
00:10:38,960 --> 00:10:41,040
Ir mes nuolat daryti
daugiau, ir daugiau, ir daugiau,

205
00:10:41,040 --> 00:10:44,811
kol mes arba susirasti
elementas, arba mes hit

206
00:10:44,811 --> 00:10:47,310
null-- mes pasiekė pabaigą
iš sąraše ir jis nėra.

207
00:10:47,310 --> 00:10:50,540
Tai turėtų tikiuosi žiedas varpas
Jums kaip tik tiesinis paieška,

208
00:10:50,540 --> 00:10:54,430
mes tiesiog atkartoti jį
atskirai susijusi sąrašas struktūra

209
00:10:54,430 --> 00:10:56,280
o ne naudojant masyvą tai padaryti.

210
00:10:56,280 --> 00:10:58,210
>> Taigi čia pavyzdys,
atskirai susijusi sąrašas.

211
00:10:58,210 --> 00:11:00,043
Tai vienas susideda iš
penki mazgai, ir mes turime

212
00:11:00,043 --> 00:11:04,330
rodyklė į galvą
sąrašas, kuris yra vadinamas, sąrašą.

213
00:11:04,330 --> 00:11:07,385
Pirmas dalykas, mes norime padaryti, tai
vėl sukurti, kad Sankryþos žymeklį.

214
00:11:07,385 --> 00:11:09,760
Taigi dabar turime dvi rodykles
kad taškas tą patį.

215
00:11:09,760 --> 00:11:15,025
>> Dabar, pastebėsite, čia pat, aš ne
turi malloc jokios erdvės Trav.

216
00:11:15,025 --> 00:11:18,970
Aš nesakiau Trav lygus malloc
kažkas, kad mazgas jau egzistuoja,

217
00:11:18,970 --> 00:11:21,160
kad vietos atmintyje jau egzistuoja.

218
00:11:21,160 --> 00:11:24,290
Taigi, visi aš iš tikrųjų darote, yra
sukurti kitą žymiklį į jį.

219
00:11:24,290 --> 00:11:28,210
Nesu mallocing papildomas
Erdvė, tik dabar dvi rodykles

220
00:11:28,210 --> 00:11:31,370
nukreipta į tą patį.

221
00:11:31,370 --> 00:11:33,710
>> Taigi yra 2 ką aš ieškote?

222
00:11:33,710 --> 00:11:37,220
Na, ne, todėl vietoj aš
ketina pereiti prie kito.

223
00:11:37,220 --> 00:11:41,740
Taigi, iš esmės sakyčiau,
Trav lygus Trav šalia.

224
00:11:41,740 --> 00:11:43,630
Ar 3, ką aš ieškote, nėra.

225
00:11:43,630 --> 00:11:45,780
Taigi, aš ir toliau eiti
per, kol galiausiai

226
00:11:45,780 --> 00:11:48,690
gauti iki 6 o tai, ką aš ieškote
už remiantis skambinimo funkcijos

227
00:11:48,690 --> 00:11:51,600
Aš viršuje
ten, ir todėl aš padaryti.

228
00:11:51,600 --> 00:11:54,150
>> Dabar, ką daryti, jei elementas aš
ieško nėra sąraše,

229
00:11:54,150 --> 00:11:55,510
jis vis dar ketina dirbti?

230
00:11:55,510 --> 00:11:57,120
Na, pastebėsite, kad sąrašas
čia yra subtiliai skiriasi,

231
00:11:57,120 --> 00:11:59,410
ir tai yra dar vienas dalykas, kad
svarbus susijusių sąrašus,

232
00:11:59,410 --> 00:12:01,780
Jūs neturite išsaugoti
jiems kokia nors ypatinga tvarka.

233
00:12:01,780 --> 00:12:05,390
Jūs galite, jei norite, bet
jums gali jau pastebėjau

234
00:12:05,390 --> 00:12:09,310
kad mes ne sekti
kokiu numeriu elementas mes esame.

235
00:12:09,310 --> 00:12:13,150
>> Ir tai tarsi viena prekybos, kad mes
turi su susietą sąrašą eil masyvai,

236
00:12:13,150 --> 00:12:15,300
jis neturime
laisvosios kreipties nebėra.

237
00:12:15,300 --> 00:12:18,150
Mes negalime tiesiog pasakyti, aš noriu
eiti į 0th elementas,

238
00:12:18,150 --> 00:12:21,410
arba 6-oji elementas mano masyvas,
kurį galiu padaryti masyvą.

239
00:12:21,410 --> 00:12:25,080
Aš negaliu pasakyti, aš noriu eiti į
0. elementas, arba 6. elementas,

240
00:12:25,080 --> 00:12:30,360
arba 25 elementas mano susietą sąrašą
nėra rodiklis susijęs su jais.

241
00:12:30,360 --> 00:12:33,660
Ir todėl jis nėra iš tikrųjų klausimas
jei mes išsaugoti mūsų sąrašą tvarka.

242
00:12:33,660 --> 00:12:36,080
Jei norite jumis
tikrai gali, bet ten

243
00:12:36,080 --> 00:12:38,567
jokios priežasties, kodėl jiems reikia
būti išsaugota bet kokia tvarka.

244
00:12:38,567 --> 00:12:40,400
Taigi dar kartą, pabandykime ir
rasti 6 Šiame sąraše.

245
00:12:40,400 --> 00:12:43,200
Na, mes pradedame ne
pradedant, mes negalime rasti 6,

246
00:12:43,200 --> 00:12:47,690
ir tada mes ir toliau neranda
6, kol mes pagaliau gauti čia.

247
00:12:47,690 --> 00:12:52,790
Taigi dabar Trav atkreipia dėmesį į mazgą
yra 8, ir šešių yra ne ten.

248
00:12:52,790 --> 00:12:55,250
>> Taigi kitas žingsnis būtų
eiti į kitą rodyklė,

249
00:12:55,250 --> 00:12:57,440
Taigi sako, Trav lygus Trav šalia.

250
00:12:57,440 --> 00:13:00,750
Na, Trav šalia, nurodomas
raudona dėžutė ten, yra niekinis.

251
00:13:00,750 --> 00:13:03,020
Taigi ten niekur kitur
eiti, ir kad šiuo metu

252
00:13:03,020 --> 00:13:06,120
galime daryti išvadą, kad mes pasiekėme
linkowanego sąrašo pabaigoje,

253
00:13:06,120 --> 00:13:07,190
ir 6 yra ne ten.

254
00:13:07,190 --> 00:13:10,980
Ir tai būtų grąžintas
klaidinga ir šiuo atveju.

255
00:13:10,980 --> 00:13:14,540
>> Gerai, kaip mes įterpti naują
mazgas į susietą sąrašą?

256
00:13:14,540 --> 00:13:17,310
Taigi mums pavyko sukurti
susijusiantrosios sąrašas iš niekur,

257
00:13:17,310 --> 00:13:19,370
bet mes tikriausiai norėsite
statyti grandinę, o ne

258
00:13:19,370 --> 00:13:22,620
sukurti atskirus sąrašus krūva.

259
00:13:22,620 --> 00:13:25,700
Mes norime turėti vieną sąrašą,
turi mazgų jį krūva,

260
00:13:25,700 --> 00:13:28,040
nėra sąrašą krūva su vienu mazge.

261
00:13:28,040 --> 00:13:31,260
Taigi, mes galime ne tik išlaikyti naudojant Sukurti
funkcija mes apibrėžta anksčiau, dabar mes

262
00:13:31,260 --> 00:13:33,860
norite įterpti į "A
sąrašą, kuris jau egzistuoja.

263
00:13:33,860 --> 00:13:36,499
>> Taigi šiuo atveju, mes ketiname
perduoti dviem argumentais,

264
00:13:36,499 --> 00:13:39,290
kad sprendžiamas, kad galvos žymeklis
susiję sąrašą, kad mes norime pridėti prie.

265
00:13:39,290 --> 00:13:40,910
Vėlgi, tai kodėl jis toks
Svarbu, kad mes visada

266
00:13:40,910 --> 00:13:43,400
sekti juo, nes
tai vienintelis būdas, kuriuo mes tikrai

267
00:13:43,400 --> 00:13:46,690
turi kreiptis į visas sąrašas
tiesiog rodykle pirmojo elemento.

268
00:13:46,690 --> 00:13:49,360
Taigi mes norime perduoti A
žymiklį į tą pirmąjį elementą,

269
00:13:49,360 --> 00:13:52,226
ir kokia vertė mes
norite įtraukti į sąrašą.

270
00:13:52,226 --> 00:13:54,600
Ir galiausiai ši funkcija
ketina grįžti rodyklę

271
00:13:54,600 --> 00:13:57,980
į naują galvos susietą sąrašą.

272
00:13:57,980 --> 00:13:59,700
>> Kokie yra žingsniai čia dalyvauja?

273
00:13:59,700 --> 00:14:02,249
Na, tiesiog kaip su kurti,
turime dinamiškai paskirstyti

274
00:14:02,249 --> 00:14:05,540
erdvė naują mazgą, ir patikrinkite,
Ar tikrai mes neturime paleisti iš atminties, ir vėl,

275
00:14:05,540 --> 00:14:07,150
nes mes naudojame malloc.

276
00:14:07,150 --> 00:14:09,080
Tada norime užpildyti
ir įdėkite mazgas,

277
00:14:09,080 --> 00:14:12,730
kad įdėti skaičių, nepriklausomai nuo
Val, į mazge.

278
00:14:12,730 --> 00:14:17,310
Mes norime įterpti mazgas ne
linkowanego sąrašo pradžioje.

279
00:14:17,310 --> 00:14:19,619
>> Yra priežastis, kad aš
nori tai padaryti, ir jis

280
00:14:19,619 --> 00:14:21,910
gali būti verta sekundę
pristabdyti vaizdo įrašą čia

281
00:14:21,910 --> 00:14:25,860
ir manau, apie tai, kodėl aš noriu
įdėkite į susieto pradžioje

282
00:14:25,860 --> 00:14:26,589
sąrašas.

283
00:14:26,589 --> 00:14:28,630
Vėlgi, aš minėjau anksčiau
kad tai tikrai ne

284
00:14:28,630 --> 00:14:33,020
Nesvarbu, jei mes ją išsaugoti bet
tvarką, kad gal tai yra raktas.

285
00:14:33,020 --> 00:14:36,040
Ir matėte, kas nutiktų, jei mes
norėjau to-- arba tik sekundę

286
00:14:36,040 --> 00:14:37,360
prieš kai mes einasi
per paiešką galite

287
00:14:37,360 --> 00:14:39,235
gali pamatyti, ką gali
atsitiktų, jei mes stengiamės

288
00:14:39,235 --> 00:14:41,330
įterpti tuo sąrašo pabaigoje.

289
00:14:41,330 --> 00:14:44,750
Kadangi mes neturite
rodyklę į sąrašo pabaigoje.

290
00:14:44,750 --> 00:14:47,490
>> Taigi dėl to, kad aš noriu
įterpti pradžioje,

291
00:14:47,490 --> 00:14:49,380
yra todėl, kad aš galiu tai padaryti iš karto.

292
00:14:49,380 --> 00:14:52,730
Turiu čia pradžioje žymeklį ir
mes tai matome vizualiai per sekundę.

293
00:14:52,730 --> 00:14:55,605
Bet jei noriu įterpti pabaigoje
Turiu pradėti iš pradžių,

294
00:14:55,605 --> 00:14:58,760
feed visą kelią į
pabaigos, ir tada smeigtuko jį ant.

295
00:14:58,760 --> 00:15:01,420
Taigi tai reikštų, kad
įterpiant tuo sąrašo pabaigoje

296
00:15:01,420 --> 00:15:04,140
taptų n °
operacija, grįžta

297
00:15:04,140 --> 00:15:06,720
mūsų diskusija
skaičiavimo sudėtingumas.

298
00:15:06,720 --> 00:15:10,140
Tai reikia tapti n operaciją, kur O
kaip sąrašas gavo didesni ir didesni,

299
00:15:10,140 --> 00:15:13,310
ir daugiau, jis bus vis daugiau ir
sunkiau smeigtuko kažką

300
00:15:13,310 --> 00:15:14,661
ant pabaigoje.

301
00:15:14,661 --> 00:15:17,410
Bet tai visada labai lengva
smeigtuko kažką pradžioje,

302
00:15:17,410 --> 00:15:19,060
jūs visada pradžioje.

303
00:15:19,060 --> 00:15:21,620
>> Ir mes matome vaizdo tai dar kartą.

304
00:15:21,620 --> 00:15:24,100
Ir tada, kai baigsime, kai
mes įterptas naujas mazgas,

305
00:15:24,100 --> 00:15:26,880
mes norime grįžti mūsų žymeklį į
Naujasis vadovas susietą sąrašą, kuris

306
00:15:26,880 --> 00:15:29,213
nes mes įdėti ne
pradeda, tikrai bus

307
00:15:29,213 --> 00:15:31,060
rodyklė į mazgą, mes ką tik sukūrėte.

308
00:15:31,060 --> 00:15:33,280
Leiskite vizualizuoti tai,
nes manau, kad padėsime.

309
00:15:33,280 --> 00:15:36,661
>> Taigi čia mūsų sąraše, tai sudaro
keturi elementai, mazgas, kuriame yra 15,

310
00:15:36,661 --> 00:15:38,410
kuri nurodo mazgas
, kurių sudėtyje yra 9, kuri

311
00:15:38,410 --> 00:15:41,370
nurodo mazgas, kuriame yra 13,
kuri nurodo mazgas, kuriame yra

312
00:15:41,370 --> 00:15:44,840
10, kuris turi null
žymeklis, kaip jos kito rodyklė

313
00:15:44,840 --> 00:15:47,010
taip, kad tai iš sąrašo gale.

314
00:15:47,010 --> 00:15:50,200
Taigi mes norime įterpti
Naujas mazgas su verte 12

315
00:15:50,200 --> 00:15:52,720
ties šis pradžioje
sąrašas, ką mes galime padaryti?

316
00:15:52,720 --> 00:15:58,770
Na, visų pirma, mes malloc erdvė
mazgas, ir tada mes įdėti 12 ten.

317
00:15:58,770 --> 00:16:02,211
>> Taigi dabar mes pasiekėme
apsisprendimo tašką, tiesa?

318
00:16:02,211 --> 00:16:03,960
Turime pora
patarimų, kad mes galėtume

319
00:16:03,960 --> 00:16:06,770
judėti, kurių vienas turėtų judame pirmas?

320
00:16:06,770 --> 00:16:09,250
Jei mes darome 12 tašką prie
naujas vadovas list--

321
00:16:09,250 --> 00:16:13,020
arba atsiprašau, mes turėtume padaryti 12
atkreipti dėmesį į senosios galvos sąrašo?

322
00:16:13,020 --> 00:16:15,319
Arba mes turėtume pasakyti, kad
Sąraše prasideda 12.

323
00:16:15,319 --> 00:16:17,110
Yra skirtumas
ten, ir mes pažvelgti

324
00:16:17,110 --> 00:16:19,870
ne tai, kas atsitinka su tiek per sekundę.

325
00:16:19,870 --> 00:16:23,350
>> Bet tai veda į
puikus tema šoninę juostą

326
00:16:23,350 --> 00:16:26,280
kuris yra tai, kad viena iš
sudėtingiausių dalykų, kurių susijusių sąrašus

327
00:16:26,280 --> 00:16:30,980
yra pasirūpinti patarimų
teisinga tvarka.

328
00:16:30,980 --> 00:16:34,520
Jei perkelti daiktus iš eilės,
galite baigti netyčia

329
00:16:34,520 --> 00:16:36,050
orphaning iš sąrašo pailsėti.

330
00:16:36,050 --> 00:16:37,300
Ir čia yra tos pavyzdys.

331
00:16:37,300 --> 00:16:40,540
Taigi eikime su mintimi of--
Na, mes ką tik sukūrėte 12.

332
00:16:40,540 --> 00:16:43,180
Mes žinome 12 bus
Naujasis vadovas sąrašo

333
00:16:43,180 --> 00:16:47,660
ir taip, kodėl ne mes tiesiog perkelti
sąrašas žymeklis ten punktą.

334
00:16:47,660 --> 00:16:49,070
>> Gerai, kad gerai.

335
00:16:49,070 --> 00:16:51,560
Taigi dabar, jei nėra 12 Sekantis taškas?

336
00:16:51,560 --> 00:16:54,580
Aš turiu galvoje, vizualiai matome
kad ji bus taškas iki 15,

337
00:16:54,580 --> 00:16:57,250
kaip žmonėms tai tikrai akivaizdu mums.

338
00:16:57,250 --> 00:17:00,300
Kaip veikia kompiuteris žinoti?

339
00:17:00,300 --> 00:17:02,720
Neturime nieko
nukreipta į 15 nebėra, tiesa?

340
00:17:02,720 --> 00:17:05,869
>> Mes prarado bet kokią galimybę kreiptis į 15.

341
00:17:05,869 --> 00:17:11,460
Mes negalime pasakyti, nauja rodyklę šalia dydžiu neprilygstami
kažkas, ten nieko nėra.

342
00:17:11,460 --> 00:17:13,510
Tiesą sakant, mes našlaičiai
iš sąrašo likusi

343
00:17:13,510 --> 00:17:16,465
tokiu būdu, mes
netyčia sulaužė grandinę.

344
00:17:16,465 --> 00:17:18,089
Ir mes tikrai nenorime daryti.

345
00:17:18,089 --> 00:17:20,000
>> Taigi grįžkime ir bandykite dar kartą.

346
00:17:20,000 --> 00:17:24,060
Gal teisė, ką reikia padaryti
yra nustatyti 12 anketa kitą rodyklę

347
00:17:24,060 --> 00:17:28,290
prie senosios galvos sąrašo pirmą,
tada mes galime judėti sąrašą virš.

348
00:17:28,290 --> 00:17:30,420
Ir iš tikrųjų, tai yra
teisinga tvarka, kad mes

349
00:17:30,420 --> 00:17:32,836
reikia laikytis, kai mes
dirbant su atskirai susietą sąrašą.

350
00:17:32,836 --> 00:17:36,460
Mes visada nori prijungti
naujas elementas į sąrašą,

351
00:17:36,460 --> 00:17:41,010
Prieš mes tą natūra
svarbus žingsnis keisti

352
00:17:41,010 --> 00:17:43,360
kurioje, susietą sąrašo galva yra.

353
00:17:43,360 --> 00:17:46,740
Vėlgi, tai toks esminis dalykas,
mes nenorime prarasti sekti juo.

354
00:17:46,740 --> 00:17:49,310
>> Taigi mes norime įsitikinti, kad
viskas yra grandinines kartu,

355
00:17:49,310 --> 00:17:52,040
Prieš mes judėti, kad žymeklį.

356
00:17:52,040 --> 00:17:55,300
Ir taip, tai būtų teisinga tvarka,
kuris yra prijungti 12 į sąrašą,

357
00:17:55,300 --> 00:17:57,630
Tada sako, kad sąrašas prasideda 12.

358
00:17:57,630 --> 00:18:00,860
Jei mes sakėme sąrašas prasideda 12 ir
tada bandė prijungti 12 į sąrašą,

359
00:18:00,860 --> 00:18:02,193
mes jau matėme, kas nutiks.

360
00:18:02,193 --> 00:18:04,920
Mes prarandame sąrašą per klaidą.

361
00:18:04,920 --> 00:18:06,740
>> Gerai, kad dar vienas dalykas kalbėti apie.

362
00:18:06,740 --> 00:18:09,750
Ką daryti, jei norime atsikratyti
visa susijusi sąrašą vienu metu?

363
00:18:09,750 --> 00:18:11,750
Vėlgi, mes mallocing
visa tai erdvė, ir todėl mes

364
00:18:11,750 --> 00:18:13,351
reikia išlaisvinti jį, kai baigsime.

365
00:18:13,351 --> 00:18:15,350
Taigi dabar mes norime ištrinti
visa susijusi sąrašas.

366
00:18:15,350 --> 00:18:16,850
Na, ką mes norime daryti?

367
00:18:16,850 --> 00:18:20,460
>> Jei mes pasiekė null žymeklį, mes
norite sustabdyti, nes kitaip tiesiog ištrinti

368
00:18:20,460 --> 00:18:23,420
iš sąrašo poilsio ir tada išlaisvinti mane.

369
00:18:23,420 --> 00:18:28,890
Ištrinti poilsio sąrašo,
ir tada laisvai esamą mazgas.

370
00:18:28,890 --> 00:18:32,850
Ką tai skamba,
kokiu būdu turi mes kalbėjome

371
00:18:32,850 --> 00:18:35,440
apie anksčiau Ar tai kaip garsas?

372
00:18:35,440 --> 00:18:39,560
Ištrinti visi kiti, tada
grįžti ir ištrinti mane.

373
00:18:39,560 --> 00:18:42,380
>> Štai rekursija, mes atlikote
problema šiek tiek mažesnis,

374
00:18:42,380 --> 00:18:46,910
mes sakydamas ištrinti visiems
kitur, galite mane ištrinti.

375
00:18:46,910 --> 00:18:50,940
Ir toliau žemyn kelio, kad mazgas
sakys, ištrinti visi kiti.

376
00:18:50,940 --> 00:18:53,940
Bet galų gale mes susisieksime su
vieta, kur sąrašas yra niekinis,

377
00:18:53,940 --> 00:18:55,310
ir kad mūsų bazinį scenarijų.

378
00:18:55,310 --> 00:18:57,010
>> Taigi tegul Šiuo išvaizdą,
ir kaip tai galėtų veikti.

379
00:18:57,010 --> 00:18:59,759
Taigi čia mūsų sąrašas, tai tas pats
sąrašą buvome tik kalbame apie,

380
00:18:59,759 --> 00:19:00,980
ir ten žingsniai.

381
00:19:00,980 --> 00:19:04,200
Yra daug teksto čia, bet
Tikimės, kad vizualizacija padės.

382
00:19:04,200 --> 00:19:08,557
>> Taigi, mes have-- ir aš taip pat iškedentas
iki mūsų kamino kadrų iliustracija

383
00:19:08,557 --> 00:19:10,890
iš mūsų vaizdo pokalbių kaminai,
ir tikiuosi visa tai

384
00:19:10,890 --> 00:19:13,260
kartu bus parodyti jums, kas vyksta.

385
00:19:13,260 --> 00:19:14,510
Taigi čia mūsų Pseudocode kodą.

386
00:19:14,510 --> 00:19:17,830
Jei mes pasiekti null
žymeklis, sustabdyti, kitaip,

387
00:19:17,830 --> 00:19:21,320
ištrinti poilsio sąrašo,
tada išlaisvinti esamą mazgas.

388
00:19:21,320 --> 00:19:25,700
Taigi dabar, list--
rodyklė kad mes

389
00:19:25,700 --> 00:19:28,410
einančios sunaikinti taškų 12.

390
00:19:28,410 --> 00:19:33,340
12 yra ne NULL žymiklį, todėl mes
ketina išbraukti iš sąrašo pailsėti.

391
00:19:33,340 --> 00:19:35,450
>> Ką išbraukiant
Kitos mus dalyvauti?

392
00:19:35,450 --> 00:19:37,950
Na, tai reiškia, tiekdami
skambinti sunaikinti, sakydamas

393
00:19:37,950 --> 00:19:42,060
kad 15 yra pradžia
poilsio sąrašo norime sunaikinti.

394
00:19:42,060 --> 00:19:47,480
Ir taip skambutis sunaikinti
12 rūšies sulaikytas.

395
00:19:47,480 --> 00:19:52,690
Tai užšaldyti ten, laukia
skambinti sunaikinti 15, baigti savo darbą.

396
00:19:52,690 --> 00:19:56,280
>> Na, 15 tai ne nulinis žymeklis, ir
todėl jis ketina pasakyti, viskas gerai,

397
00:19:56,280 --> 00:19:58,450
Na, ištrinti sąrašo pailsėti.

398
00:19:58,450 --> 00:20:00,760
Iš sąrašo poilsio prasideda
, 9, ir taip mes tiesiog

399
00:20:00,760 --> 00:20:04,514
laukti, kol pašalinsite visus, kad
Daiktai, tada grįžkite ir ištrinti mane.

400
00:20:04,514 --> 00:20:06,680
Na 9 manimi ketinate pasakyti, gerai,
Nesu NULL rodyklė,

401
00:20:06,680 --> 00:20:09,020
taip ištrinti poilsio sąrašą iš čia.

402
00:20:09,020 --> 00:20:11,805
Ir todėl pabandykite ir sunaikinti 13.

403
00:20:11,805 --> 00:20:15,550
13 sako, aš ne NULL rodyklė,
Tas pats, jis eina spardytis.

404
00:20:15,550 --> 00:20:17,930
10 yra ne NULL žymiklį, 10
yra null žymeklį,

405
00:20:17,930 --> 00:20:20,200
bet 10 yra pati nėra
null pointer dabar,

406
00:20:20,200 --> 00:20:22,470
ir todėl ji eina spardytis per daug.

407
00:20:22,470 --> 00:20:25,560
>> Ir dabar list taškų ten, jis
tikrai norėtų atkreipti dėmesį į some--

408
00:20:25,560 --> 00:20:28,710
jei aš turėjo daugiau erdvės paveikslėlyje,
jis norėtų atkreipti dėmesį į kai kurių atsitiktinių vietos

409
00:20:28,710 --> 00:20:29,960
kad mes nežinome, kas tai yra.

410
00:20:29,960 --> 00:20:34,680
Tai nulinis žymeklis nors, sąrašas
yra tiesiog dabar nustatyti tai vertybės null.

411
00:20:34,680 --> 00:20:36,820
Tai nukreipta tiesiai tą raudoną dėžutę.

412
00:20:36,820 --> 00:20:39,960
Mes pasiekėme null žymeklį, todėl
mes galime sustoti, o baigsime.

413
00:20:39,960 --> 00:20:46,230
>> Ir taip, kad violetinė rėmas yra now-- ne
Į viršų stack-- tai aktyvus rėmas,

414
00:20:46,230 --> 00:20:47,017
bet tai daroma.

415
00:20:47,017 --> 00:20:48,600
Jei mes pasiekėme null žymeklį, sustoti.

416
00:20:48,600 --> 00:20:51,290
Mes nedarome nieko, mes
negalėjo null žymeklį,

417
00:20:51,290 --> 00:20:55,070
mes ne malloc bet
erdvės, ir todėl mes baigsite.

418
00:20:55,070 --> 00:20:57,590
Taigi šią funkciją rėmo
yra sunaikinta, ir mes

419
00:20:57,590 --> 00:21:00,930
resume-- mes pasiimti ten, kur mes palikome
išjungti su kito aukščiausio punktų, kuris

420
00:21:00,930 --> 00:21:02,807
tai tamsiai mėlyna rėmas čia.

421
00:21:02,807 --> 00:21:04,390
Taigi, mes pasiimti ten, kur mes palikome išjungtas.

422
00:21:04,390 --> 00:21:06,598
Mes išbraukė likusieji
Sąrašas jau, todėl dabar mes

423
00:21:06,598 --> 00:21:08,000
ketina atlaisvinti dabartinius mazgai.

424
00:21:08,000 --> 00:21:12,920
Taigi, dabar mes galime išlaisvinti šį mazgą, o dabar
mes pasiekė funkcija pabaigą.

425
00:21:12,920 --> 00:21:16,810
Ir taip, kad funkcija rėmas sunaikinti,
ir mes pasiimti šviesos mėlyna vieną.

426
00:21:16,810 --> 00:21:20,650
>> Taigi says-- Aš jau done--
ištrinant sąrašo poilsio, taip,

427
00:21:20,650 --> 00:21:23,140
nemokamai esamą mazgas.

428
00:21:23,140 --> 00:21:26,520
Ir dabar geltonas rėmelis
atgal ant kamino.

429
00:21:26,520 --> 00:21:29,655
Ir taip, kaip matote, mes dabar
sunaikinti sąrašą iš dešinės į kairę.

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

431
00:21:33,710 --> 00:21:37,280
>> Kas būtų nutikę, nors,
jei būtume veikėme neteisingą kelią?

432
00:21:37,280 --> 00:21:39,410
Tiesiog patinka, kai mes bandėme
pridėti elementą.

433
00:21:39,410 --> 00:21:41,909
Jei mes messed up grandinę, jei
mes ne prijungti patarimų

434
00:21:41,909 --> 00:21:44,690
teisinga tvarka, jei mes
tik išlaisvino pirmąjį elementą,

435
00:21:44,690 --> 00:21:47,420
jei mes tiesiog išlaisvino
vadovas sąrašo, dabar mes

436
00:21:47,420 --> 00:21:49,642
jokiu būdu kreiptis į
iš sąrašo poilsio.

437
00:21:49,642 --> 00:21:51,350
Ir taip mes turėtume
našlaičiais viskas,

438
00:21:51,350 --> 00:21:53,880
mes turėjome tai, kas
vadinamas Atminties nutekėjimas.

439
00:21:53,880 --> 00:21:56,800
Jei prisimenate iš mūsų vaizdo
nuo dinaminės atminties paskirstymo,

440
00:21:56,800 --> 00:21:58,650
tai nėra labai geras dalykas.

441
00:21:58,650 --> 00:22:00,810
>> Taigi, kaip jau sakiau,
Yra keletas operacijos

442
00:22:00,810 --> 00:22:04,010
kad mes turime naudoti dirbti
su susieta sąrašą efektyviai.

443
00:22:04,010 --> 00:22:08,430
Ir jūs turbūt pastebėjote, aš praleisti vieną,
išbraukiant vieną elementą iš susietos

444
00:22:08,430 --> 00:22:09,064
sąrašas.

445
00:22:09,064 --> 00:22:10,980
Priežastis, kodėl aš padariau, kad
tai tikrai rūšies

446
00:22:10,980 --> 00:22:14,360
sudėtinga galvoti apie tai, kaip ištrinti
vienas elementas nuo A pavieniui

447
00:22:14,360 --> 00:22:15,600
susiję sąrašas.

448
00:22:15,600 --> 00:22:19,950
Mums reikia, kad būtų galima praleisti
kažkas į sąrašą, kuris

449
00:22:19,950 --> 00:22:22,975
reiškia, kad mes patekti į point-- mes
norite ištrinti šią node--

450
00:22:22,975 --> 00:22:25,350
Tačiau, norint padaryti jį, todėl mes
nepraranda jokios informacijos,

451
00:22:25,350 --> 00:22:30,530
turime prijungti šį
mazgas per čia, čia.

452
00:22:30,530 --> 00:22:33,390
>> Taigi, aš tikriausiai padarė, kad negerai
iš vizualiniu požiūriu.

453
00:22:33,390 --> 00:22:36,830
Taigi mes ne iš pradžių mūsų
sąrašas, mes tęsdami per,

454
00:22:36,830 --> 00:22:40,510
mes norime ištrinti šį mazgą.

455
00:22:40,510 --> 00:22:43,440
Jei mes tiesiog ištrinti jį,
mes suskaidytas į grandinę.

456
00:22:43,440 --> 00:22:45,950
Tai mazgas čia
remiasi visa kita,

457
00:22:45,950 --> 00:22:48,260
jis yra iš čia atlikti grandinę.

458
00:22:48,260 --> 00:22:51,190
>> Taigi, ką mes turime padaryti iš tikrųjų
kai mes gauti į šį punktą,

459
00:22:51,190 --> 00:22:56,670
yra mums reikia atsitraukti vieną, ir
prijungti šį mazgą per šį mazgą,

460
00:22:56,670 --> 00:22:58,590
todėl mes galime tada ištrinti
viduryje esanti viena.

461
00:22:58,590 --> 00:23:02,120
Bet pavieniui susiję sąrašai nėra
pateikti mums būdą, kaip grįžti atgal.

462
00:23:02,120 --> 00:23:05,160
Taigi mums reikia arba išlaikyti
dvi rodykles, ir perkelti juos

463
00:23:05,160 --> 00:23:09,527
rūšiuoti išjungimo žingsnio, viena už
kita, kaip mes einame, arba gauti iki taško,

464
00:23:09,527 --> 00:23:11,110
ir tada siųsti kitą žymiklį per.

465
00:23:11,110 --> 00:23:13,150
Ir, kaip matote, ji
gali gauti šiek tiek nepatogus.

466
00:23:13,150 --> 00:23:15,360
Laimei, mes turime
dar vienas būdas išspręsti, kad

467
00:23:15,360 --> 00:23:17,810
kai kalbame apie dvigubai susijusių sąrašus.

468
00:23:17,810 --> 00:23:20,720
>> Aš Doug Lloyd, tai CS50.

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