1
00:00:00,000 --> 00:00:04,074

2
00:00:04,074 --> 00:00:05,990
Doug LLOYD: Gerai,
taip šiuo klausimu esate

3
00:00:05,990 --> 00:00:09,020
tikriausiai gana susipažinę
su matricomis ir susijusių sąrašus

4
00:00:09,020 --> 00:00:10,950
kuris yra du pirminės
duomenų struktūros mes

5
00:00:10,950 --> 00:00:16,810
kalbėjo apie laikymo rinkiniai
duomenys panašių duomenų tipų organizuotas.

6
00:00:16,810 --> 00:00:19,080
>> Dabar mes ketiname kalbėti
apie keletą variacijų

7
00:00:19,080 --> 00:00:20,330
ant matricos ir susijusių sąrašus.

8
00:00:20,330 --> 00:00:22,362
Šiame vaizdo mes ketiname
kalbėti apie šūsnis.

9
00:00:22,362 --> 00:00:25,320
Tiksliau, mes ketiname kalbėti
apie duomenų struktūra vadinama kamino.

10
00:00:25,320 --> 00:00:28,510
Prisiminkite iš ankstesnių diskusijų
apie nurodymus ir atminties,

11
00:00:28,510 --> 00:00:32,060
kad kamino yra taip pat
vardą kaip atminties segmentą

12
00:00:32,060 --> 00:00:34,980
kur statiškai paskelbė
memory-- atminties, kuri jus

13
00:00:34,980 --> 00:00:38,730
pavadinimą, kintamieji, kad jūs Vardas et
Cetera ir funkcijų rėmai kurią mes taip pat

14
00:00:38,730 --> 00:00:41,000
Skambučių kamino rėmai egzistuoja.

15
00:00:41,000 --> 00:00:45,421
Taigi tai yra kamino duomenų struktūra
nėra kamino segmentas atmintį.

16
00:00:45,421 --> 00:00:45,920
GERAI.

17
00:00:45,920 --> 00:00:46,890
>> Bet kas yra kamino?

18
00:00:46,890 --> 00:00:49,220
Taigi, tai gana daug tik
specialios rūšies struktūros

19
00:00:49,220 --> 00:00:51,190
kad palaiko duomenis organizuotu būdu.

20
00:00:51,190 --> 00:00:53,760
Ir ten du labai
paplitusių būdų įgyvendinti

21
00:00:53,760 --> 00:00:57,380
kaminai, naudojant du duomenų struktūras
kad mes jau esate susipažinę su,

22
00:00:57,380 --> 00:01:00,340
matricas ir susiję sąrašus.

23
00:01:00,340 --> 00:01:04,430
Ką daro kamino ypatingą yra
būdas, kuriuo mes įdėti informaciją

24
00:01:04,430 --> 00:01:08,200
į krūvą, kaip mes
pašalinti informaciją iš kamino.

25
00:01:08,200 --> 00:01:11,600
Visų pirma su kaminai
taisyklė yra tik labiausiai

26
00:01:11,600 --> 00:01:15,830
neseniai pridėta elementas gali būti pašalintas.

27
00:01:15,830 --> 00:01:17,660
>> Taigi manau, apie tai, kaip jei tai kamino.

28
00:01:17,660 --> 00:01:21,170
Mes polių informacija
ant savaime,

29
00:01:21,170 --> 00:01:24,271
ir tik viršuje dalykas
krūva gali būti pašalintas.

30
00:01:24,271 --> 00:01:27,020
Mes negalime pašalinti dalykas po
nes visa kita būtų

31
00:01:27,020 --> 00:01:28,020
žlugti ir nukristi.

32
00:01:28,020 --> 00:01:32,580
Taigi mes tikrai statome krūvą, kad
tada mes turime pašalinti gabalėlį.

33
00:01:32,580 --> 00:01:36,590
Dėl šios priežasties mes dažniausiai nurodo
į krūvą, kaip LIFO struktūrą,

34
00:01:36,590 --> 00:01:38,940
paskutinis in, first out.

35
00:01:38,940 --> 00:01:42,290
LIFO, paskutinis, pirmasis iš.

36
00:01:42,290 --> 00:01:45,635
>> Taigi dėl šio apribojimo
kaip informacija gali būti įtraukta į

37
00:01:45,635 --> 00:01:49,080
ir pašalinti iš kamino, ten tikrai
Tik du dalykai, ką galime padaryti su kamino.

38
00:01:49,080 --> 00:01:52,010
Mes gali stumti, kuris yra
Terminas mes naudojame pridedant

39
00:01:52,010 --> 00:01:55,130
naujas elementas į viršų
sukrauti, arba jei kamino neegzistuoja

40
00:01:55,130 --> 00:01:58,550
ir mes jį kurti nuo nulio,
sukurti į pirmąją vietą krūvą

41
00:01:58,550 --> 00:02:00,110
būtų stumti.

42
00:02:00,110 --> 00:02:04,990
Ir tada pop, tai CS Rūšiuoti
Terminas mes naudojame pašalinti labiausiai neseniai

43
00:02:04,990 --> 00:02:08,330
pridėta elementą iš kamino viršuje.

44
00:02:08,330 --> 00:02:11,130
>> Taigi mes ketiname pažvelgti tiek
diegimas, tiek masyvo remiantis

45
00:02:11,130 --> 00:02:13,120
ir susijusi sąrašas pagrįstas.

46
00:02:13,120 --> 00:02:14,870
Ir mes ketiname
pradėti su masyvo pagrįstos.

47
00:02:14,870 --> 00:02:19,990
Taigi čia yra pagrindinė idėja, ką
masyvo remiantis kamino duomenų struktūra

48
00:02:19,990 --> 00:02:21,140
atrodys.

49
00:02:21,140 --> 00:02:23,740
Mes turime įvedėte apibrėžimą čia.

50
00:02:23,740 --> 00:02:27,790
Viduje, kad mes turime du narius
laukai ar struktūros.

51
00:02:27,790 --> 00:02:29,880
Mes turime masyvą.

52
00:02:29,880 --> 00:02:32,400
Ir vėl aš, naudojant
savavališkai duomenų tipas vertė.

53
00:02:32,400 --> 00:02:35,180
>> Taigi, tai gali būti bet koks duomenų tipas,
int char arba kai kiti duomenys

54
00:02:35,180 --> 00:02:37,080
įrašykite anksčiau sukurta.

55
00:02:37,080 --> 00:02:39,861
Taigi, mes turime nuo jų dydžio pajėgumus masyvo.

56
00:02:39,861 --> 00:02:44,010
Talpa yra svaras apibrėžta pastovus,
gal kažkur kitur mūsų faile.

57
00:02:44,010 --> 00:02:47,550
Taigi pastebėti jau su šio
įgyvendinimas mes aprėpties

58
00:02:47,550 --> 00:02:49,800
save, kaip buvo paprastai
atveju matricos,

59
00:02:49,800 --> 00:02:53,170
kurių mes negalime dinamiškai keisti dydį,
kur yra tam tikras skaičius

60
00:02:53,170 --> 00:02:55,450
elementų daugiau, kad
mes galime įdėti mūsų kamino.

61
00:02:55,450 --> 00:02:57,930
Šiuo atveju tai gebėjimas elementus.

62
00:02:57,930 --> 00:03:00,310
>> Mes taip pat sekti
rietuvės viršaus.

63
00:03:00,310 --> 00:03:04,350
Tai, kas elementas yra labiausiai
neseniai pridėta prie kamino?

64
00:03:04,350 --> 00:03:07,470
Ir todėl mes sekti, kad
kintamu vadinamas viršuje.

65
00:03:07,470 --> 00:03:11,692
Ir visa tai bus suvynioti kartu
į naują duomenų tipą, vadinamą kamino.

66
00:03:11,692 --> 00:03:13,400
Ir kai mes sukūrėme
Ši nauja duomenų tipas

67
00:03:13,400 --> 00:03:15,410
galime traktuoti kaip
bet koks kitas duomenų tipas.

68
00:03:15,410 --> 00:03:20,970
Mes galime paskelbti kamino s, kaip
mes galime padaryti int x, arba char m.

69
00:03:20,970 --> 00:03:22,990
Ir kai sakome sukrauti
ai, gerai, kas atsitinka,

70
00:03:22,990 --> 00:03:26,420
yra mes gauti rinkinį
atminties atidėta mus.

71
00:03:26,420 --> 00:03:28,770
>> Šiuo atveju talpos
Aš, matyt, nusprendė

72
00:03:28,770 --> 00:03:33,470
10 nes aš turiu
vieno kintamojo tipo kamino

73
00:03:33,470 --> 00:03:35,320
kuriame yra du laukai prisiminti.

74
00:03:35,320 --> 00:03:38,330
Masyvas, šiuo atveju vyksta
turi būti iš sveikųjų skaičių masyvas

75
00:03:38,330 --> 00:03:40,440
kaip yra daugumoje mano pavyzdžių atveju.

76
00:03:40,440 --> 00:03:43,996
Ir dar vienas sveikasis skaičius kintamasis
gali saugoti viršų,

77
00:03:43,996 --> 00:03:45,870
labiausiai neseniai papildė
elementas prie kamino.

78
00:03:45,870 --> 00:03:50,290
Taigi vienas kamino, ką mes
tik apibrėžta atrodo taip.

79
00:03:50,290 --> 00:03:53,190
Tai dėžutė, kurioje yra
kaip 10 matrica, kas

80
00:03:53,190 --> 00:03:57,280
bus sveikieji šiuo atveju ir
kitą kintamąjį, ten žalia

81
00:03:57,280 --> 00:04:00,010
nurodyti rietuvės viršuje.

82
00:04:00,010 --> 00:04:02,600
>> Norėdami nustatyti viršutinio
kamino mes tiesiog pasakyti s.top.

83
00:04:02,600 --> 00:04:04,890
Štai kaip mes prieiti prie
srityje statinio atšaukimo.

84
00:04:04,890 --> 00:04:10,460
s.top lygus 0 efektyviai
tai daro mūsų kamino.

85
00:04:10,460 --> 00:04:12,960
Taigi dar kartą mes turime dvi operacijas
kad mes galime atlikti dabar.

86
00:04:12,960 --> 00:04:14,270
Mes galime stumti, ir mes galime pop.

87
00:04:14,270 --> 00:04:15,635
Pradėkime paspaudimu.

88
00:04:15,635 --> 00:04:18,260
Vėlgi, stūmimas yra pridėti naują
elementas kamino viršuje.

89
00:04:18,260 --> 00:04:21,460
>> Taigi, ką mes turime daryti,
šio masyvo remiantis įgyvendinimas?

90
00:04:21,460 --> 00:04:23,210
Na apskritai
Push funkcija vyksta

91
00:04:23,210 --> 00:04:26,160
to reikia priimti
rodyklę į krūvą.

92
00:04:26,160 --> 00:04:28,610
Dabar imtis antrą ir galvoti apie jį.

93
00:04:28,610 --> 00:04:32,840
Kodėl mes norime priimti
rodyklė į krūvą?

94
00:04:32,840 --> 00:04:36,830
Prisiminkite iš ankstesnių video apie
kintamasis apimtis ir patarimų,

95
00:04:36,830 --> 00:04:42,350
kas nutiktų, jei mes tiesiog atsiuntė
kamino, s, o į kaip parametras?

96
00:04:42,350 --> 00:04:45,770
Ką iš tikrųjų praėjo ten?

97
00:04:45,770 --> 00:04:49,430
Įsiminti mes sukurti kopiją
kai mes pereiname jį funkcija

98
00:04:49,430 --> 00:04:51,160
nebent mes naudojame patarimų.

99
00:04:51,160 --> 00:04:55,380
Ir taip ši funkcija stumti poreikius
priimti žymeklį į rietuvę

100
00:04:55,380 --> 00:04:59,160
taip, kad mes iš tikrųjų keičiasi
kamino mes ketiname pakeisti.

101
00:04:59,160 --> 00:05:03,060
>> Kitas dalykas, stumti tikriausiai nori
priimti yra duomenų elementas tipo vertės.

102
00:05:03,060 --> 00:05:06,970
Šiuo atveju, vėl, yra sveikas skaičius, kad
mes ketiname pridėti prie kamino viršaus.

103
00:05:06,970 --> 00:05:08,680
Taigi mes turime mūsų du parametrus.

104
00:05:08,680 --> 00:05:11,310
Ką mes ketiname
dabar daryti viduje stumti?

105
00:05:11,310 --> 00:05:14,860
Na, tiesiog, mes tiesiog ketiname pridėti
kad elementas, kamino viršuje

106
00:05:14,860 --> 00:05:22,860
ir tada pakeisti, kur viršuje
kamino yra, kad ai dot viršų vertę.

107
00:05:22,860 --> 00:05:25,639
Taigi tai yra tai, ką funkcija
deklaracija paspaudimu

108
00:05:25,639 --> 00:05:27,680
gali atrodyti nurodytame
masyvo pagrindu įgyvendinimas.

109
00:05:27,680 --> 00:05:30,967
>> Vėlgi, tai nėra sunku ir greitai taisyklės
, kad galėtumėte pakeisti tai ir

110
00:05:30,967 --> 00:05:32,050
jis gali skirtis skirtingais būdais.

111
00:05:32,050 --> 00:05:33,840
Galbūt s pareiškė visame pasaulyje.

112
00:05:33,840 --> 00:05:36,180
Ir todėl jūs net nereikia
praeiti ji yra, kaip parametras.

113
00:05:36,180 --> 00:05:39,125
Tai vėl tik
Apskritai dėklas paspaudimu.

114
00:05:39,125 --> 00:05:41,000
Ir yra skirtingi
būdų, kaip jį įgyvendinti.

115
00:05:41,000 --> 00:05:42,810
Bet šiuo atveju mūsų
stumti ketina imtis

116
00:05:42,810 --> 00:05:48,540
du argumentai, rodyklė į krūvą ir
duomenų elemento tipo verte, sveikasis skaičius

117
00:05:48,540 --> 00:05:49,840
tokiu atveju.

118
00:05:49,840 --> 00:05:52,100
>> Taigi, mes paskelbė s, mes
sakė s.top lygus 0.

119
00:05:52,100 --> 00:05:55,969
Dabar galime stumti
numeris 28 ant kamino.

120
00:05:55,969 --> 00:05:57,010
Na, ką tai reiškia?

121
00:05:57,010 --> 00:05:59,600
Na šiuo metu
Į viršų kamino yra 0.

122
00:05:59,600 --> 00:06:01,350
Ir kas taip iš esmės
nutiks tai

123
00:06:01,350 --> 00:06:05,820
mes ketiname laikytis numerį
28 į masyvą vietoje 0.

124
00:06:05,820 --> 00:06:09,540
Gana paprasta, tiesa, kad
buvo viršuje, o dabar mes gerai eiti.

125
00:06:09,540 --> 00:06:12,910
Ir tada mes turime pakeisti tai, ką
rietuvės viršaus bus.

126
00:06:12,910 --> 00:06:15,130
Taip, kad kitą kartą
mes stumti in elementas,

127
00:06:15,130 --> 00:06:18,017
mes ketiname laikyti jį
masyvas vietą, tikriausiai ne 0.

128
00:06:18,017 --> 00:06:20,100
Mes nenorime, kad perrašyti
Ką mes tiesiog įdėti ten.

129
00:06:20,100 --> 00:06:23,510
Ir todėl mes tiesiog perkelti viršaus į 1.

130
00:06:23,510 --> 00:06:24,890
Tai tikriausiai turi prasmę.

131
00:06:24,890 --> 00:06:28,940
>> Dabar, jei mes norime įdėti kitą elementą
ant kamino, sako, kad mes norite stumti 33,

132
00:06:28,940 --> 00:06:33,190
Na, dabar mes tik ketina imtis 33
ir įdėti jį masyvo vietos numerį

133
00:06:33,190 --> 00:06:37,580
1, ir tada pakeisti viršuje mūsų
kamino turi būti masyvas vietą numeris du.

134
00:06:37,580 --> 00:06:40,650
Taigi, jei kitą kartą mes norime
stumti elementą ant kamino,

135
00:06:40,650 --> 00:06:43,087
Tai bus įdėti į masyvą vietoje 2.

136
00:06:43,087 --> 00:06:44,420
Ir darykime, kad vienas daugiau laiko.

137
00:06:44,420 --> 00:06:45,753
Mes stumti 19 off rietuvių.

138
00:06:45,753 --> 00:06:48,940
Mes įdėti 19 masyvo vietoje 2
ir pakeisti mūsų kamino viršų

139
00:06:48,940 --> 00:06:51,220
būti masyvas vieta 3
Taigi, jei kitą kartą mes

140
00:06:51,220 --> 00:06:54,780
reikia padaryti push mes gera eiti.

141
00:06:54,780 --> 00:06:56,980
>> Gerai, kad manimi stumia trumpai.

142
00:06:56,980 --> 00:06:57,830
Ką apie Popping?

143
00:06:57,830 --> 00:07:00,240
Taigi Popping yra tarsi
priešinys stumia.

144
00:07:00,240 --> 00:07:02,720
Tai, kaip mes pašalinti duomenis iš kamino.

145
00:07:02,720 --> 00:07:04,610
Ir apskritai pop poreikius
daryti toliau.

146
00:07:04,610 --> 00:07:07,600
Reikia sutikti rodyklę į
kamino, vėl bendruoju atveju.

147
00:07:07,600 --> 00:07:10,480
Kai kuriose kitu atveju jums gali
pareiškė kamino visame pasaulyje,

148
00:07:10,480 --> 00:07:13,910
Tokiu atveju jums nereikia perduoti jį
į, nes jis jau turi prieigą prie jo

149
00:07:13,910 --> 00:07:15,541
kaip pasaulio kintamasis.

150
00:07:15,541 --> 00:07:17,040
Bet tada ką dar mes turime daryti?

151
00:07:17,040 --> 00:07:21,000
Na mes buvome incrementing
Iš Tiesioginio kamino viršaus,

152
00:07:21,000 --> 00:07:24,050
todėl mes tikriausiai norės
į Mažėja kamino viršų

153
00:07:24,050 --> 00:07:25,009
pop, tiesa?

154
00:07:25,009 --> 00:07:26,800
Ir tada, žinoma,
mes taip pat norės

155
00:07:26,800 --> 00:07:29,240
grąžinti vertę, kad mes pašalinti.

156
00:07:29,240 --> 00:07:32,125
Jei mes pridėti elementus, mes norime
gauti elementus iš vėliau,

157
00:07:32,125 --> 00:07:34,000
mes tikriausiai iš tikrųjų
nori laikyti juos, kad mes

158
00:07:34,000 --> 00:07:36,490
ne tiesiog ištrinti juos iš
sukrauti ir tada nieko su jais.

159
00:07:36,490 --> 00:07:38,500
Apskritai, jei mes
stumti ir Popping čia

160
00:07:38,500 --> 00:07:41,250
norime laikyti šį
informacija prasmingai

161
00:07:41,250 --> 00:07:43,250
ir taip tai nereiškia, kad
jausmas tiesiog jį išmeskite.

162
00:07:43,250 --> 00:07:46,380
Taigi ši funkcija turėtų
tikriausiai grąžina reikšmę mums.

163
00:07:46,380 --> 00:07:51,040
>> Taigi tai, kas deklaracija pop
gali atrodyti kaip ten viršuje kairėje.

164
00:07:51,040 --> 00:07:53,870
Ši funkcija grąžina
duomenų tipo vertės.

165
00:07:53,870 --> 00:07:56,320
Vėlgi mes buvome naudojant
sveikieji skaičiai visoje.

166
00:07:56,320 --> 00:08:01,916
Ir ji priima žymiklį į kamino kaip
jos vienintelis argumentas ar vienintelis parametras.

167
00:08:01,916 --> 00:08:03,040
Taigi, kas yra pop ketinate daryti?

168
00:08:03,040 --> 00:08:07,990
Tarkime, mes norime dabar
pop elementas off s.

169
00:08:07,990 --> 00:08:14,000
Taigi nepamirškite pasakiau, kad kaminai paskutinis
in, first out, LIFO duomenų struktūras.

170
00:08:14,000 --> 00:08:17,855
Kuris elementas ketina
būti pašalintas iš kamino?

171
00:08:17,855 --> 00:08:21,780

172
00:08:21,780 --> 00:08:24,150
Ar galite atspėti, 19?

173
00:08:24,150 --> 00:08:25,290
Kadangi jūs norite būti teisus.

174
00:08:25,290 --> 00:08:28,836
19 buvo paskutinis elementas mes pridėjome į
kamino, kai mes buvome stumia elementus,,

175
00:08:28,836 --> 00:08:31,210
ir todėl ji ketina pirmas
elementas, kuris pašalinamas.

176
00:08:31,210 --> 00:08:34,780
Tai tarsi mes sakėme, 28, ir
tada mes įdėti 33 ant jo,

177
00:08:34,780 --> 00:08:36,659
ir mes įdėti 19 viršuje, kad.

178
00:08:36,659 --> 00:08:40,650
Vienintelis elementas mes galime pakilti yra 19.

179
00:08:40,650 --> 00:08:45,019
>> Dabar diagramoje čia, ką aš padariau
yra tarsi ištrinta nuo 19 masyvo.

180
00:08:45,019 --> 00:08:46,810
Tai ne iš tikrųjų
ką mes ketiname daryti.

181
00:08:46,810 --> 00:08:48,934
Užtenka tik ketina rūšies
iš apsimesti, kad nėra.

182
00:08:48,934 --> 00:08:51,441
Jis vis dar ten
kad atminties vietą,

183
00:08:51,441 --> 00:08:54,190
bet mes tik ketina jį ignoruoti
keičiant mūsų kamino viršų

184
00:08:54,190 --> 00:08:56,080
gražu 3 2.

185
00:08:56,080 --> 00:08:58,720
Taigi, jei mes dabar stumti
kita ant kamino elementas,

186
00:08:58,720 --> 00:09:00,720
tai per parašyti 19.

187
00:09:00,720 --> 00:09:03,990
>> Bet tegul ne eiti per bėdų
ištrynę 19 iš kamino.

188
00:09:03,990 --> 00:09:05,830
Mes galime tik apsimesti, kad nėra.

189
00:09:05,830 --> 00:09:11,107
Taikant kamino jis dingo, jei
mes pakeisti viršuje, kad būtų 3 2, o ne.

190
00:09:11,107 --> 00:09:12,690
Gerai, kad buvo gana daug.

191
00:09:12,690 --> 00:09:15,080
Tai viskas, ką reikia padaryti
pop elementas išjungtas.

192
00:09:15,080 --> 00:09:16,090
Darom dar kartą.

193
00:09:16,090 --> 00:09:18,610
Taigi aš pabrėžė, kad raudona spalva čia
rodo, mes darome kitą skambutį.

194
00:09:18,610 --> 00:09:19,720
Mes ketiname padaryti tą patį.

195
00:09:19,720 --> 00:09:20,803
>> Taigi, kas nutiks?

196
00:09:20,803 --> 00:09:23,670
Na, mes ketiname saugoti
33 X ir mes ketiname

197
00:09:23,670 --> 00:09:26,217
pakeisti kamino viršaus iki 1.

198
00:09:26,217 --> 00:09:29,050
Taigi, kad jei mes dabar stumti
elementas į krūvą, kuri mes

199
00:09:29,050 --> 00:09:31,610
ketina daryti dabar,
kas nutiks

200
00:09:31,610 --> 00:09:36,367
yra mes ketiname perrašymo
masyvas vietą numeris 1.

201
00:09:36,367 --> 00:09:38,950
Taigi, kad 33, kuris buvo tarsi liko
atsilieka, kad mes tik apsimetė

202
00:09:38,950 --> 00:09:44,390
ten nėra daugiau, mes tik ketina
į Clobber ją ir įdėti 40 ten vietoj.

203
00:09:44,390 --> 00:09:46,290
Ir tada, žinoma,
nes mes padarė stumti,

204
00:09:46,290 --> 00:09:48,780
mes ketiname prieaugio
top rietuvės 1-2

205
00:09:48,780 --> 00:09:50,950
taip, kad jei dabar mes pridėti
Kitas elementas jis bus

206
00:09:50,950 --> 00:09:54,700
eiti į masyvo vietos numeris du.

207
00:09:54,700 --> 00:09:57,590
>> Dabar susiję sąrašai kitą
būdas įgyvendinti kaminai.

208
00:09:57,590 --> 00:10:01,210
Ir jei tai apibrėžimo
ekranas čia atrodo pažįstamas,

209
00:10:01,210 --> 00:10:04,260
tai todėl, kad jis atrodo beveik
lygiai taip pat,, iš tikrųjų,

210
00:10:04,260 --> 00:10:07,790
tai gana daug yra tiksliai
toks pat, kaip pavieniui susietą sąrašo,

211
00:10:07,790 --> 00:10:11,990
Jei prisimenate iš mūsų diskusija
atskirai susijęs sąrašus kitoje vaizdo.

212
00:10:11,990 --> 00:10:15,510
Vienintelis apribojimas čia
yra mums, programuotojams,

213
00:10:15,510 --> 00:10:17,900
mes neleidžiama
įterpti ar ištrinti atsitiktinai

214
00:10:17,900 --> 00:10:20,620
iš pavieniui susietą sąrašą
kuriuos mes anksčiau galėjo daryti.

215
00:10:20,620 --> 00:10:25,820
Mes tik dabar galite įterpti ir pašalinti iš
priekinis arba susietą viršų

216
00:10:25,820 --> 00:10:26,320
sąrašas.

217
00:10:26,320 --> 00:10:28,028
Tai tikrai tik
Skirtumas nors.

218
00:10:28,028 --> 00:10:29,700
Tai kitaip atskirai susijusi sąrašas.

219
00:10:29,700 --> 00:10:32,060
Tai tik apribojimas
pakeisti savyje

220
00:10:32,060 --> 00:10:35,770
programuotojais, kad
keičia jį į rietuvę.

221
00:10:35,770 --> 00:10:39,280
>> Taisyklė čia yra visada išlaikyti
žymiklį į susietą sąrašą galvos.

222
00:10:39,280 --> 00:10:41,520
Tai, žinoma, visuotinai
svarbi taisyklė pirmas.

223
00:10:41,520 --> 00:10:44,260
Dėl pavieniui susiję sąrašą vistiek
tik reikia žymiklį į galvą

224
00:10:44,260 --> 00:10:46,160
siekiant turėti, kad
grandinės galėtų kreiptis

225
00:10:46,160 --> 00:10:48,596
kiekvienam kito elemento
susijusioje sąrašą.

226
00:10:48,596 --> 00:10:50,470
Bet tai ypač
svarbus kamino.

227
00:10:50,470 --> 00:10:52,386
Ir taip paprastai esate
vyksta iš tikrųjų nori

228
00:10:52,386 --> 00:10:54,090
Ši rodyklė būti pasaulio kintamasis.

229
00:10:54,090 --> 00:10:56,574
Tai tikriausiai
bus dar lengviau, kad taip.

230
00:10:56,574 --> 00:10:58,240
Taigi, kas yra push ir pop analogai?

231
00:10:58,240 --> 00:10:58,740
Teisė.

232
00:10:58,740 --> 00:11:01,812
Taigi stumia vėl pridedant
naujas elementas prie kamino.

233
00:11:01,812 --> 00:11:03,770
Be susietą sąrašą, kad
reiškia, kad mes ketiname turėti

234
00:11:03,770 --> 00:11:07,770
sukurti naują mazgą, kad mes
ketiname pridėti į susietą sąrašą

235
00:11:07,770 --> 00:11:10,500
ir vykdykite veiksmus atidžiai
kad mes sukūrėme anksčiau

236
00:11:10,500 --> 00:11:16,050
į vieną, susijusių sąrašus įtraukti jį į
grandinė nesulaužant grandinę

237
00:11:16,050 --> 00:11:18,900
ir prarasti arba orphaning bet
elementai iš susietų sąrašą.

238
00:11:18,900 --> 00:11:21,820
Ir tai iš esmės, ką tai
mažai BLOB teksto ten apibendrina.

239
00:11:21,820 --> 00:11:23,740
Ir tegul pažvelgti
ne tai, kaip schemoje.

240
00:11:23,740 --> 00:11:24,823
>> Taigi čia mūsų susijusi sąrašas.

241
00:11:24,823 --> 00:11:26,620
Tai kartu yra keturi elementai.

242
00:11:26,620 --> 00:11:30,420
Ir dar puikiai Štai mūsų
kamino, kuriame yra keturi elementai.

243
00:11:30,420 --> 00:11:36,030
Ir tarkim dabar mes norime
stumti naują elementą į šį steką.

244
00:11:36,030 --> 00:11:39,792
Ir mes norime stumti nauja
daiktai, kurių duomenys vertė yra 12.

245
00:11:39,792 --> 00:11:41,000
Na, ką mes ketiname daryti?

246
00:11:41,000 --> 00:11:43,420
Na pirmiausia mes ketiname
malloc erdvė, dinamiškai

247
00:11:43,420 --> 00:11:45,411
skirti vietos naują mazge.

248
00:11:45,411 --> 00:11:48,160
Ir, žinoma, iš karto po
mes paskambinti malloc mes visada

249
00:11:48,160 --> 00:11:52,989
įsitikinkite, kad patikrinti for null,
nes jei mes turime null Atgal

250
00:11:52,989 --> 00:11:54,280
ten buvo keletas problema rūšiuoti.

251
00:11:54,280 --> 00:11:57,570
Mes nenorime, kad dereference to null
Rodyklė arba jūs kenčia SEG gedimą.

252
00:11:57,570 --> 00:11:58,510
Tai nėra gerai.

253
00:11:58,510 --> 00:11:59,760
Taigi mes malloced mazgas.

254
00:11:59,760 --> 00:12:01,260
Tarkime, mes turėjo sėkmę čia.

255
00:12:01,260 --> 00:12:06,090
Mes ketiname įdėti į 12
duomenys laukas tos mazgas.

256
00:12:06,090 --> 00:12:11,570
Dabar jūs prisiminti, kuris iš mūsų patarimų
juda kitas todėl mes negalime nutraukti grandinę?

257
00:12:11,570 --> 00:12:15,100
Mes turime keletą galimybių, bet čia
tik viena, kad ketina būti saugus

258
00:12:15,100 --> 00:12:19,330
yra nustatyti naujienas šalia Rodyklė
taškas senosios galvos sąrašo

259
00:12:19,330 --> 00:12:21,360
ar kas greičiau bus
senas vadovas sąrašo.

260
00:12:21,360 --> 00:12:23,610
Ir dabar, kad visi mūsų
elementai yra grandinės kartu,

261
00:12:23,610 --> 00:12:27,370
mes galime tiesiog perkelti sąrašą atkreipti
į tą pačią vietą, kad naujos daro.

262
00:12:27,370 --> 00:12:33,550
Ir mes dabar efektyviai stumti
naujas elementas ant iš kamino priekyje.

263
00:12:33,550 --> 00:12:36,420
>> Pop Mes tik norime
ištrinti tą pirmąjį elementą.

264
00:12:36,420 --> 00:12:38,150
Ir todėl iš esmės ką
mes turime padaryti čia

265
00:12:38,150 --> 00:12:40,050
Na mes turime rasti antrą elementą.

266
00:12:40,050 --> 00:12:43,540
Kad ilgainiui taps nauja
galvą, kai mes ištrinti pirmasis.

267
00:12:43,540 --> 00:12:47,300
Taigi mes tiesiog reikia pradėti nuo
pradžia, perkelti vieną į priekį.

268
00:12:47,300 --> 00:12:50,340
Kai mes turime griebtis dėl vieno
Persiųsti kur mes šiuo metu

269
00:12:50,340 --> 00:12:53,850
mes galime ištrinti pirmasis saugiai
ir tada mes galime tiesiog perkelti galvą

270
00:12:53,850 --> 00:12:57,150
atkreipti dėmesį į tai, kas buvo
antroji kadencija, o tada dabar

271
00:12:57,150 --> 00:12:59,170
yra pirmasis, kad po to, kai
mazgas buvo ištrintas.

272
00:12:59,170 --> 00:13:01,160
>> Taigi dar kartą, atsižvelgiant išvaizdą
ne tai, kaip schemoje mes

273
00:13:01,160 --> 00:13:05,022
noriu dabar pop
elementas išjungti šio kamino.

274
00:13:05,022 --> 00:13:05,730
Taigi, ką mes galime padaryti?

275
00:13:05,730 --> 00:13:08,188
Na mes pirmą kartą ketina sukurti
naujas žymeklis, kad vyksta

276
00:13:08,188 --> 00:13:10,940
iki punkto pačioje vietoje kaip ir galvos.

277
00:13:10,940 --> 00:13:13,790
Mes ketiname perkelti jį vieną poziciją
Persiųsti sakydamas Trav dydžiu neprilygstami

278
00:13:13,790 --> 00:13:17,510
Trav šalia kurios, pavyzdžiui,
būtų iš anksto į Trav rodyklę vieną

279
00:13:17,510 --> 00:13:19,324
pozicija į priekį.

280
00:13:19,324 --> 00:13:21,240
Dabar, mes turime
turėti ant pirmojo elemento

281
00:13:21,240 --> 00:13:24,573
per rodykle vadinamas, sąrašą ir
Antrasis elementas per žymeklis vadinamas

282
00:13:24,573 --> 00:13:28,692
Trav, mes galime saugiai ištrinti, kad
Pirmasis elementas iš kamino

283
00:13:28,692 --> 00:13:30,650
neprarasdamas likusios
grandinės, nes mes

284
00:13:30,650 --> 00:13:32,358
turi būdą, kaip perduoti
prie antrojo elemento

285
00:13:32,358 --> 00:13:34,780
perduoti būdu iš
žymeklis vadinamas Trav.

286
00:13:34,780 --> 00:13:37,100
>> Taigi, dabar mes galime išlaisvinti tą mazgą.

287
00:13:37,100 --> 00:13:38,404
Galime nemokamai sąrašą.

288
00:13:38,404 --> 00:13:41,320
Ir tada viskas, ką reikia padaryti dabar
judėti sąrašą taško į tą pačią vietą

289
00:13:41,320 --> 00:13:44,482
kad Trav daro, ir mes tarsi atgal
kur mes pradėjome prieš mums stumiama 12

290
00:13:44,482 --> 00:13:45,690
ant į pirmąją vietą, į dešinę.

291
00:13:45,690 --> 00:13:46,940
Tai yra būtent tai, kur buvome.

292
00:13:46,940 --> 00:13:48,840
Mes turėjome šį keturių elementų kamino.

293
00:13:48,840 --> 00:13:49,690
Mes pridėjo penktadalį.

294
00:13:49,690 --> 00:13:51,910
Mes stumti penktadalį
elementas, ir tada mes

295
00:13:51,910 --> 00:13:55,980
popped, kad pastaruoju
įtraukta elementą atgal išjungti.

296
00:13:55,980 --> 00:13:58,816
>> Tai tikrai gana daug
visi yra kaminai.

297
00:13:58,816 --> 00:14:00,190
Galite jas įgyvendinti, kaip matricos.

298
00:14:00,190 --> 00:14:01,815
Galite jas įgyvendinti kaip susijusios sąrašus.

299
00:14:01,815 --> 00:14:04,810
Yra, žinoma, kita
būdų, kaip jas įgyvendinti, taip pat.

300
00:14:04,810 --> 00:14:09,060
Iš esmės todėl mes būtų naudoti
rietuvės yra išlaikyti duomenis tokiu būdu,

301
00:14:09,060 --> 00:14:12,090
kad neseniai pridėta
elementas yra pirmas dalykas, kurį mes

302
00:14:12,090 --> 00:14:14,980
norės grįžti.

303
00:14:14,980 --> 00:14:17,900
Aš Doug Lloyd, tai CS50.

304
00:14:17,900 --> 00:14:19,926