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

2
00:00:04,074 --> 00:00:05,990
DOUG LLOYD: Hea küll,
nii käesoleva punkti olete

3
00:00:05,990 --> 00:00:09,020
ilmselt päris tuttav
massiivid ja ahelloendid

4
00:00:09,020 --> 00:00:10,950
mis on kaks peamist
andmestruktuurid me oleme

5
00:00:10,950 --> 00:00:16,810
rääkis hoida komplekti
andmed sarnaste andmete tüüpi organiseeritud.

6
00:00:16,810 --> 00:00:19,080
>> Nüüd me ei kavatse rääkida
umbes paar variatsioonid

7
00:00:19,080 --> 00:00:20,330
kohta massiivid ja ahelloendid.

8
00:00:20,330 --> 00:00:22,362
Selle video me läheme
rääkida korstnad.

9
00:00:22,362 --> 00:00:25,320
Nimelt me ​​ei kavatse rääkida
umbes andmebaasi struktuuri nimetatakse virna.

10
00:00:25,320 --> 00:00:28,510
Meenuta eelmise arutelud
umbes viiteid ja mälu

11
00:00:28,510 --> 00:00:32,060
et stack on ka
nimi for segment mälu

12
00:00:32,060 --> 00:00:34,980
kus staatiliselt deklareeritud
memory-- mälu, et teil

13
00:00:34,980 --> 00:00:38,730
Nime, muutujaid, siis nime, et
cetera ja funktsiooni raamid, mida me ka

14
00:00:38,730 --> 00:00:41,000
pinu raamid olemas.

15
00:00:41,000 --> 00:00:45,421
Nii et see on virnas andmestruktuur
ei virna segment mälu.

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

17
00:00:45,920 --> 00:00:46,890
>> Aga milline on korstna?

18
00:00:46,890 --> 00:00:49,220
Nii et see on päris palju lihtsalt
eriline struktuur

19
00:00:49,220 --> 00:00:51,190
mis säilitab andmed organiseeritud viisil.

20
00:00:51,190 --> 00:00:53,760
Ja seal on kaks väga
levinumad viisid ellu

21
00:00:53,760 --> 00:00:57,380
korstnad kahe andmestruktuurid
et me oleme juba tuttav,

22
00:00:57,380 --> 00:01:00,340
massiivid ja ahelloendid.

23
00:01:00,340 --> 00:01:04,430
Mis teeb virna eriliseks
kuidas me paneme info

24
00:01:04,430 --> 00:01:08,200
virna ja kuidas me
informatsiooni eemaldamiseks pinu.

25
00:01:08,200 --> 00:01:11,600
Eelkõige korstnad
reegel on ainult kõige

26
00:01:11,600 --> 00:01:15,830
viimati lisatud element saab eemaldada.

27
00:01:15,830 --> 00:01:17,660
>> Nii mõelda, nagu oleks see pakk.

28
00:01:17,660 --> 00:01:21,170
Me tekkimise info
peal ise,

29
00:01:21,170 --> 00:01:24,271
ja ainult asi tipus
kuhi saab eemaldada.

30
00:01:24,271 --> 00:01:27,020
Me ei saa eemaldada asja all
sest kõik muu oleks

31
00:01:27,020 --> 00:01:28,020
variseda ja kukkuda.

32
00:01:28,020 --> 00:01:32,580
Nii et me tõesti ehitame virna, et
Siis pead kaotada jaokaupa.

33
00:01:32,580 --> 00:01:36,590
Sellepärast me tavaliselt viidata
korstnat kui LIFO struktuuri,

34
00:01:36,590 --> 00:01:38,940
kesta sisse, esimesena välja.

35
00:01:38,940 --> 00:01:42,290
LIFO, kesta sisse, esimesena välja.

36
00:01:42,290 --> 00:01:45,635
>> Nii, sest see piirang
kuidas teavet saab lisatud

37
00:01:45,635 --> 00:01:49,080
ja eemaldada korstna, seal on tõesti
ainult kaks asja, mida me saame teha koos virna.

38
00:01:49,080 --> 00:01:52,010
Me ei lükka, mis on
Mõiste, mida me kasutame, lisades

39
00:01:52,010 --> 00:01:55,130
uus element tippu
Kestab, või kui virna ei ole olemas

40
00:01:55,130 --> 00:01:58,550
ja me luua nullist,
luua pinu esimese koha

41
00:01:58,550 --> 00:02:00,110
oleks surudes.

42
00:02:00,110 --> 00:02:04,990
Ja siis pop, see on omamoodi CS
Mõiste me kasutame eemaldada viimati

43
00:02:04,990 --> 00:02:08,330
lisada elemendi riidale.

44
00:02:08,330 --> 00:02:11,130
>> Nii et me läheme vaatama nii
rakendusi, nii massiivi põhineb

45
00:02:11,130 --> 00:02:13,120
ja ahelloendid aluseks.

46
00:02:13,120 --> 00:02:14,870
Ja me ei kavatse
Alustame massiivi aluseks.

47
00:02:14,870 --> 00:02:19,990
Nii et siin on põhiline idee, mida
massiivi põhineb stack andmestruktuur

48
00:02:19,990 --> 00:02:21,140
näeks.

49
00:02:21,140 --> 00:02:23,740
Meil on trükitud määratluses.

50
00:02:23,740 --> 00:02:27,790
Toas, et meil on kaks liiget
või väljade struktuuri.

51
00:02:27,790 --> 00:02:29,880
Meil on hulgaliselt.

52
00:02:29,880 --> 00:02:32,400
Ja jälle ma kasutan
suvaline andmete tüübi väärtus.

53
00:02:32,400 --> 00:02:35,180
>> Nii et see võib olla mis tahes tüüpi andmetena
int paalia või mõne muu andmeid

54
00:02:35,180 --> 00:02:37,080
kirjuta sa varem loodud.

55
00:02:37,080 --> 00:02:39,861
Nii et meil on hulgaliselt suurus võimsust.

56
00:02:39,861 --> 00:02:44,010
Võimsus on nael määratletud pidev,
võibolla kusagil mujal meie faili.

57
00:02:44,010 --> 00:02:47,550
Nii märkate juba selle konkreetse
rakendamise me piiravates

58
00:02:47,550 --> 00:02:49,800
end oli tavaliselt
puhul massiivid,

59
00:02:49,800 --> 00:02:53,170
mida me ei saa dünaamiliselt suurust,
kus seal on teatud arv

60
00:02:53,170 --> 00:02:55,450
elementide maksimaalne, et
saame panna meie stack.

61
00:02:55,450 --> 00:02:57,930
Sel juhul võime elemente.

62
00:02:57,930 --> 00:03:00,310
>> Samuti jälgida
top pinu.

63
00:03:00,310 --> 00:03:04,350
Mis element on kõige
Hiljuti lisatud korstna?

64
00:03:04,350 --> 00:03:07,470
Ja nii me jälgida, et
muutujale nimega top.

65
00:03:07,470 --> 00:03:11,692
Ja see kõik saab tõmmati kokku
uude andmete tüübi nimega virna.

66
00:03:11,692 --> 00:03:13,400
Ja kui me loodud
see uus andmetüüp

67
00:03:13,400 --> 00:03:15,410
saame ravida nagu
muid andmeid tüübist.

68
00:03:15,410 --> 00:03:20,970
Me võime kuulutada stack s, nagu
me võiks teha int x, või char y.

69
00:03:20,970 --> 00:03:22,990
Ja kui me ütleme, korstna
s, hästi, mis juhtub

70
00:03:22,990 --> 00:03:26,420
on meil saada komplekt
mälu kõrvale meile.

71
00:03:26,420 --> 00:03:28,770
>> Sel juhul võimsusega
Olen ilmselt otsustanud

72
00:03:28,770 --> 00:03:33,470
10 sest mul on
Ühe muutuja tüüpi korstnat

73
00:03:33,470 --> 00:03:35,320
mis sisaldab kahte väljad meenutada.

74
00:03:35,320 --> 00:03:38,330
Array, sel juhul läheb
olema massiivi täisarvud

75
00:03:38,330 --> 00:03:40,440
nagu see on enamikus minu näited.

76
00:03:40,440 --> 00:03:43,996
Ja teine ​​täisarv muutuja
suudavad hoida üleval,

77
00:03:43,996 --> 00:03:45,870
viimati lisatud
element korstnat.

78
00:03:45,870 --> 00:03:50,290
Nii ühe virna, mida me
lihtsalt määratletud näeb välja selline.

79
00:03:50,290 --> 00:03:53,190
See on karbis
massiivi 10, mida

80
00:03:53,190 --> 00:03:57,280
on täisarvud sel juhul ja
teine ​​täisarv muutuja seal roheline

81
00:03:57,280 --> 00:04:00,010
näidata riidale.

82
00:04:00,010 --> 00:04:02,600
>> Kui soovite, et tippu
stack me lihtsalt öelda s.top.

83
00:04:02,600 --> 00:04:04,890
See, kuidas me pääse
valdkonnas struktuuri tagasivõtmist.

84
00:04:04,890 --> 00:04:10,460
s.top võrdub 0 tõhusalt
teeb seda meie stack.

85
00:04:10,460 --> 00:04:12,960
Nii jälle on meil kaks operatsiooni
et suudame täita nüüd.

86
00:04:12,960 --> 00:04:14,270
Me ei lükka ja me saame pop.

87
00:04:14,270 --> 00:04:15,635
Alustame push.

88
00:04:15,635 --> 00:04:18,260
Jällegi, surudes lisab uue
element riidale.

89
00:04:18,260 --> 00:04:21,460
>> Niisiis, mida me peame tegema
Selle massiivi põhinev rakendamine?

90
00:04:21,460 --> 00:04:23,210
Noh üldiselt
push funktsioon läheb

91
00:04:23,210 --> 00:04:26,160
et pead vastu võtma
kursor pinu.

92
00:04:26,160 --> 00:04:28,610
Nüüd mõtle hetk ja mõelda.

93
00:04:28,610 --> 00:04:32,840
Miks me tahame vastu
kursor stack?

94
00:04:32,840 --> 00:04:36,830
Meenuta eelmise videod
Muutuja ulatust ja viiteid,

95
00:04:36,830 --> 00:04:42,350
Mis juhtuks, kui me just saatis
stack, s pigem parameeter?

96
00:04:42,350 --> 00:04:45,770
Mida tegelikult läbinud seal?

97
00:04:45,770 --> 00:04:49,430
Pea meeles, me luua koopia
kui võtame seda funktsiooni

98
00:04:49,430 --> 00:04:51,160
Kui me kasutame suunanäitajaks.

99
00:04:51,160 --> 00:04:55,380
Ja nii see funktsioon suruda vajadustele
aktsepteerima viit virna

100
00:04:55,380 --> 00:04:59,160
nii et me oleme tegelikult muutmata
virna me kavatseme muuta.

101
00:04:59,160 --> 00:05:03,060
>> Teine asi, push ilmselt tahab
nõus on andmete element tüüpi väärtuse.

102
00:05:03,060 --> 00:05:06,970
Sel juhul jällegi täisarv, et
me ei kavatse lisada tippu pinu.

103
00:05:06,970 --> 00:05:08,680
Nii on meil meie kaks parameetrit.

104
00:05:08,680 --> 00:05:11,310
Mida me saame
nüüd teha sees push?

105
00:05:11,310 --> 00:05:14,860
Noh, lihtsalt, me lihtsalt läheb lisada
et element riidale

106
00:05:14,860 --> 00:05:22,860
ja siis muutuvad kus peal
stack on, et s dot top väärtus.

107
00:05:22,860 --> 00:05:25,639
Nii et see on see, mida funktsioon
deklaratsiooni push

108
00:05:25,639 --> 00:05:27,680
tunduda mõnes
massiivi põhinev rakendamine.

109
00:05:27,680 --> 00:05:30,967
>> Jälle see ei ole raske ja kiire reegel
et võid muuta ja on

110
00:05:30,967 --> 00:05:32,050
see on väga erinevad.

111
00:05:32,050 --> 00:05:33,840
Ehk s kuulutatakse kogu maailmas.

112
00:05:33,840 --> 00:05:36,180
Ja nii sa ei pea isegi
läbida see parameeter.

113
00:05:36,180 --> 00:05:39,125
See on jällegi vaid
Üldjuhul push.

114
00:05:39,125 --> 00:05:41,000
Ja seal on erinevad
kuidas seda rakendada.

115
00:05:41,000 --> 00:05:42,810
Aga sel juhul meie
push see aega võtab

116
00:05:42,810 --> 00:05:48,540
kaks argumenti, kursor virna ja
andmeelemendis tüüpi väärtust, täisarv

117
00:05:48,540 --> 00:05:49,840
sel juhul.

118
00:05:49,840 --> 00:05:52,100
>> Nii me kuulutasime s, me
ütles s.top võrdub 0.

119
00:05:52,100 --> 00:05:55,969
Nüüd suruge
number 28 peale virna.

120
00:05:55,969 --> 00:05:57,010
Noh mida see tähendab?

121
00:05:57,010 --> 00:05:59,600
Noh praegu
Pinu on 0.

122
00:05:59,600 --> 00:06:01,350
Ja mis on põhimõtteliselt
juhtub on

123
00:06:01,350 --> 00:06:05,820
me ei kavatse jääda arv
28 arvesse massiivi 0.

124
00:06:05,820 --> 00:06:09,540
Päris lihtne, eks, et
oli üleval ja nüüd oled hea minna.

125
00:06:09,540 --> 00:06:12,910
Ja siis on meil vaja muuta seda, mis
tippu stack on.

126
00:06:12,910 --> 00:06:15,130
Nii et järgmine kord,
me push element,

127
00:06:15,130 --> 00:06:18,017
me ei kavatse seda säilitada
massiivi asukohta, ilmselt mitte 0.

128
00:06:18,017 --> 00:06:20,100
Me ei taha kirjutada
mida me just sinna pannakse.

129
00:06:20,100 --> 00:06:23,510
Ja nii me lihtsalt liikuda ülevalt 1.

130
00:06:23,510 --> 00:06:24,890
See ilmselt mõtet.

131
00:06:24,890 --> 00:06:28,940
>> Nüüd, kui me tahame panna teise elemendi
peale virna, ütleme, et me tahame, et lükata 33,

132
00:06:28,940 --> 00:06:33,190
Noh nüüd me lihtsalt aega võtab 33
ja pane see on massiivi asukoha number

133
00:06:33,190 --> 00:06:37,580
1 ja siis muutus tippu meie
Kestab olla massiivi asukoha number kaks.

134
00:06:37,580 --> 00:06:40,650
Nii et kui järgmine kord tahame
push element peale virna,

135
00:06:40,650 --> 00:06:43,087
see saab panna massiivi asukohta 2.

136
00:06:43,087 --> 00:06:44,420
Ja teeme, et veel üks kord.

137
00:06:44,420 --> 00:06:45,753
Me suruda 19 välja korstnad.

138
00:06:45,753 --> 00:06:48,940
Me paneme 19 massiiv asukohta 2
ja muuta top meie stack

139
00:06:48,940 --> 00:06:51,220
olema massiiv asukohast 3
nii et kui järgmine kord, kui me

140
00:06:51,220 --> 00:06:54,780
on vaja teha push meil oled hea minna.

141
00:06:54,780 --> 00:06:56,980
>> OK, nii et on surudes lühikokkuvõte.

142
00:06:56,980 --> 00:06:57,830
Aga popping?

143
00:06:57,830 --> 00:07:00,240
Nii popping on omamoodi
ametivenna surudes.

144
00:07:00,240 --> 00:07:02,720
See, kuidas me kustutada andmeid virna.

145
00:07:02,720 --> 00:07:04,610
Ja üldiselt pop vajadustele
teha järgmist.

146
00:07:04,610 --> 00:07:07,600
See peab aktsepteerima kursor
Kestab jälle üldises puhul.

147
00:07:07,600 --> 00:07:10,480
Mõnel teisel juhul võite
on deklareerinud virna maailmas,

148
00:07:10,480 --> 00:07:13,910
mille puhul ei ole vaja edastada see
aastal, sest see on juba juurdepääs

149
00:07:13,910 --> 00:07:15,541
kui globaalne muutuja.

150
00:07:15,541 --> 00:07:17,040
Aga siis mida muud me peame tegema?

151
00:07:17,040 --> 00:07:21,000
Noh olime incrementing
top virna push,

152
00:07:21,000 --> 00:07:24,050
nii me ilmselt läheb taha
ainult kahandab riidale

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

154
00:07:25,009 --> 00:07:26,800
Ja siis muidugi
me ka läheb taha

155
00:07:26,800 --> 00:07:29,240
tagasi väärtust, mida me eemaldada.

156
00:07:29,240 --> 00:07:32,125
Kui me lisame elemente, me tahame
saada elemendid välja hiljem,

157
00:07:32,125 --> 00:07:34,000
me ilmselt tegelikult
tahad salvestada neid nii me

158
00:07:34,000 --> 00:07:36,490
ei ole lihtsalt nende kustutamiseks
Kestab ja tehke midagi koos nendega.

159
00:07:36,490 --> 00:07:38,500
Üldiselt, kui me oleme
surudes ja popping siin

160
00:07:38,500 --> 00:07:41,250
Me tahame hoida seda
informatsiooni mõtestatult

161
00:07:41,250 --> 00:07:43,250
ja nii see ei tee
mõtet lihtsalt loobuda.

162
00:07:43,250 --> 00:07:46,380
Nii et see ülesanne peaks
ilmselt tagastama väärtuse meile.

163
00:07:46,380 --> 00:07:51,040
>> Nii et see on see, mida deklaratsiooni pop
tunduda seal üleval vasakul.

164
00:07:51,040 --> 00:07:53,870
See funktsioon tagastab
andmete tüüpi väärtuse.

165
00:07:53,870 --> 00:07:56,320
Jällegi oleme kasutanud
täisarvud kogu.

166
00:07:56,320 --> 00:08:01,916
Ja ta võtab kursor virna nagu
selle ainus argument või füüsilisest parameeter.

167
00:08:01,916 --> 00:08:03,040
Mis on pop tegema hakkad?

168
00:08:03,040 --> 00:08:07,990
Oletame, et me tahame nüüd
pop element off s.

169
00:08:07,990 --> 00:08:14,000
Seega pidage meeles, ma ütlesin, et korstnad on viimase
aastal, esimene välja, LIFO andmestruktuurid.

170
00:08:14,000 --> 00:08:17,855
Milline element läheb
saab eemaldada korstna?

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

172
00:08:21,780 --> 00:08:24,150
Kas sa vist 19?

173
00:08:24,150 --> 00:08:25,290
Sest sa tahaks olla õige.

174
00:08:25,290 --> 00:08:28,836
19 oli viimane element lisasime
Kestab kui olime surudes elemendid,

175
00:08:28,836 --> 00:08:31,210
ja nii see läheb esimene
element, mis saab eemaldada.

176
00:08:31,210 --> 00:08:34,780
See on sama, kui me ütlesime 28, ja
siis paneme 33 peal,

177
00:08:34,780 --> 00:08:36,659
ja paneme 19 peal, et.

178
00:08:36,659 --> 00:08:40,650
Ainus element saame startida on 19.

179
00:08:40,650 --> 00:08:45,019
>> Nüüd diagrammil siin, mida ma olen teinud
on omamoodi kustutatakse 19 massiivist.

180
00:08:45,019 --> 00:08:46,810
See ei ole tegelikult
mida me teeme.

181
00:08:46,810 --> 00:08:48,934
Me lihtsalt läheb selline
on teeselda seda seal ei ole.

182
00:08:48,934 --> 00:08:51,441
See on ikka seal
et mälu asukoht,

183
00:08:51,441 --> 00:08:54,190
aga me lihtsalt läheb seda ignoreerida
muutes top meie stack

184
00:08:54,190 --> 00:08:56,080
alates on 3-2.

185
00:08:56,080 --> 00:08:58,720
Nii kui me nüüd lükata
teise elemendi peale virna,

186
00:08:58,720 --> 00:09:00,720
see üle kirjutada 19.

187
00:09:00,720 --> 00:09:03,990
>> Aga ärme lähe läbi häda
kustutada 19 korstnat.

188
00:09:03,990 --> 00:09:05,830
Me ei teeskleme seda seal ei ole.

189
00:09:05,830 --> 00:09:11,107
Eesmärgil virna see on läinud, kui
muudame top olema 2 asemel 3.

190
00:09:11,107 --> 00:09:12,690
Olgu, nii et oli päris palju see.

191
00:09:12,690 --> 00:09:15,080
See on kõik, mida me peame tegema
pop element välja.

192
00:09:15,080 --> 00:09:16,090
Teeme seda uuesti.

193
00:09:16,090 --> 00:09:18,610
Nii et ma olen rõhutanud seda punast siin
näitavad me teeme teise kõne.

194
00:09:18,610 --> 00:09:19,720
Me teeme sama asja.

195
00:09:19,720 --> 00:09:20,803
>> Mis siis juhtub?

196
00:09:20,803 --> 00:09:23,670
Noh, me ei kavatse hoida
33 x ja me läheme

197
00:09:23,670 --> 00:09:26,217
muuta riidale 1.

198
00:09:26,217 --> 00:09:29,050
Nii et kui me nüüd tõugata
element virna, mis me oleme

199
00:09:29,050 --> 00:09:31,610
kavatseb teha just nüüd,
Mis juhtub

200
00:09:31,610 --> 00:09:36,367
on meil läheb ülekirjutamise
massiivi asukoha number 1.

201
00:09:36,367 --> 00:09:38,950
Nii et 33, mis oli omamoodi vasakule
taga, et me lihtsalt teeskles

202
00:09:38,950 --> 00:09:44,390
ei ole seal enam, me lihtsalt läheb
to Tellida ja panna 40 seal asemel.

203
00:09:44,390 --> 00:09:46,290
Ja siis muidugi
sest tegime push,

204
00:09:46,290 --> 00:09:48,780
me ei kavatse juurdekasvu
Pinu 1-2

205
00:09:48,780 --> 00:09:50,950
nii et kui nüüd lisada
teise elemendi siis see

206
00:09:50,950 --> 00:09:54,700
minema massiivi asukoha number kaks.

207
00:09:54,700 --> 00:09:57,590
>> Nüüd seotud nimekirjad on teise
kuidas rakendada korstnad.

208
00:09:57,590 --> 00:10:01,210
Ja kui see määratlus on
ekraan siin tundub tuttav,

209
00:10:01,210 --> 00:10:04,260
see on, sest see näeb välja peaaegu
täpselt sama, tegelikult

210
00:10:04,260 --> 00:10:07,790
see päris palju on täpselt
Sama kui üksikult seotud nimekirja,

211
00:10:07,790 --> 00:10:11,990
Kui te mäletate meie arutelu
üksikult ahelloendid teise video.

212
00:10:11,990 --> 00:10:15,510
Ainus piirang siin
on meie jaoks nagu programmeerijad,

213
00:10:15,510 --> 00:10:17,900
me ei lubata
sisestada või kustutada juhuslikult

214
00:10:17,900 --> 00:10:20,620
alates üksikult seotud nimekirja
mida me võiksime varem teha.

215
00:10:20,620 --> 00:10:25,820
Me saame alles nüüd lisada ja kustutada
esi- või ülaosa seotud

216
00:10:25,820 --> 00:10:26,320
nimekirja.

217
00:10:26,320 --> 00:10:28,028
See on tõesti ainus
Erinevus küll.

218
00:10:28,028 --> 00:10:29,700
See on muidu üksikult seotud nimekirja.

219
00:10:29,700 --> 00:10:32,060
See on ainult piirang
asendades meist endist

220
00:10:32,060 --> 00:10:35,770
nagu programmeerijad, et
muudab see virna.

221
00:10:35,770 --> 00:10:39,280
>> Reegel on siin alati säilitada
kursor juht ahelloend.

222
00:10:39,280 --> 00:10:41,520
See on muidugi üldiselt
Oluline reegel esimene.

223
00:10:41,520 --> 00:10:44,260
Juba üksi seotud nimekirja niikuinii
vaja ainult viit juht

224
00:10:44,260 --> 00:10:46,160
selleks on, et
kett olema võimalik viidata

225
00:10:46,160 --> 00:10:48,596
iga teine ​​element
on seotud nimekirja.

226
00:10:48,596 --> 00:10:50,470
Aga see on eriti
oluline virna.

227
00:10:50,470 --> 00:10:52,386
Ja nii üldiselt oled
läheb tegelikult tahavad

228
00:10:52,386 --> 00:10:54,090
osuti olla globaalne muutuja.

229
00:10:54,090 --> 00:10:56,574
See on ilmselt läheb
olla isegi lihtsam nii.

230
00:10:56,574 --> 00:10:58,240
Millised on analoogid push ja pop?

231
00:10:58,240 --> 00:10:58,740
Õigus.

232
00:10:58,740 --> 00:11:01,812
Nii lükates uuesti suurendab
uus element korstnat.

233
00:11:01,812 --> 00:11:03,770
In ahelloend et
tähendab, et me lähed on

234
00:11:03,770 --> 00:11:07,770
luua uus sõlm, et me oleme
läheb lisada arvesse seotud nimekirja,

235
00:11:07,770 --> 00:11:10,500
ja järgige hoolikalt samme
et me oleme kirjeldatud varem

236
00:11:10,500 --> 00:11:16,050
in üksikult ahelloendid lisamiseks
kett lõhkumata kett

237
00:11:16,050 --> 00:11:18,900
ja kaotada või orvustumine tahes
elemendid seotud nimekirja.

238
00:11:18,900 --> 00:11:21,820
Ja see on põhimõtteliselt mida see
väike kämp teksti seal kokkuvõtlikult.

239
00:11:21,820 --> 00:11:23,740
Ja olgem vaatleme
seda kui diagramm.

240
00:11:23,740 --> 00:11:24,823
>> Nii et siin on meie ahelloendid.

241
00:11:24,823 --> 00:11:26,620
See samaaegselt sisaldab nelja elemendi.

242
00:11:26,620 --> 00:11:30,420
Ja täiuslikumalt siin on meie
Kestab sisaldab nelja elementi.

243
00:11:30,420 --> 00:11:36,030
Ja oletame, et me nüüd tahame
push uus kirje peale virna.

244
00:11:36,030 --> 00:11:39,792
Ja me tahame, et lükata uue
esemed, mille andmed väärtus on 12.

245
00:11:39,792 --> 00:11:41,000
Noh, mida me saame teha?

246
00:11:41,000 --> 00:11:43,420
Noh esiteks me ei kavatse
malloc ruumi, dünaamiliselt

247
00:11:43,420 --> 00:11:45,411
eraldada ruumi uue sõlme.

248
00:11:45,411 --> 00:11:48,160
Ja muidugi kohe pärast
me helistada malloc me alati

249
00:11:48,160 --> 00:11:52,989
veenduge, et kontrollida null,
sest kui me saime null tagasi

250
00:11:52,989 --> 00:11:54,280
seal oli mingi probleem.

251
00:11:54,280 --> 00:11:57,570
Me ei taha apparent et null
osuti ehk siis kannatavad seg süü.

252
00:11:57,570 --> 00:11:58,510
See ei ole hea.

253
00:11:58,510 --> 00:11:59,760
Nii oleme malloced sõlme.

254
00:11:59,760 --> 00:12:01,260
Eeldame oleme olnud edukas siin.

255
00:12:01,260 --> 00:12:06,090
Me läheme panna 12 sisse
andmeväljale et sõlme.

256
00:12:06,090 --> 00:12:11,570
Nüüd sa meenutada, mida meie suunanäitajaks
liigub järgmise nii et me ei riku kett?

257
00:12:11,570 --> 00:12:15,100
Meil on paar võimalust siin aga
ainus, mis saab olema ohutu

258
00:12:15,100 --> 00:12:19,330
on seatud uudis järgmine viit
punkti ja vana juht nimekirja

259
00:12:19,330 --> 00:12:21,360
või mida saab varsti
vana juht nimekirja.

260
00:12:21,360 --> 00:12:23,610
Ja nüüd, et kõik meie
elemendid on aheldatud koos,

261
00:12:23,610 --> 00:12:27,370
meil võimalik liigutada nimekirja punkti
samas kohas, et uus teeb.

262
00:12:27,370 --> 00:12:33,550
Ja meil on nüüd tõhusalt surutakse
uus element peale ees virn.

263
00:12:33,550 --> 00:12:36,420
>> Pop me tahame
kustutada Esimene element.

264
00:12:36,420 --> 00:12:38,150
Ja nii põhimõtteliselt mida
me peame tegema siin,

265
00:12:38,150 --> 00:12:40,050
ka meil leida teine ​​element.

266
00:12:40,050 --> 00:12:43,540
Lõpuks, mis muutub uus
pea pärast me kustutame esimene.

267
00:12:43,540 --> 00:12:47,300
Nii et me lihtsalt vaja alustada
Alguses liikuda ühe edasi.

268
00:12:47,300 --> 00:12:50,340
Kui meil kätte ühel
ettepoole, kus me praegu

269
00:12:50,340 --> 00:12:53,850
me ei kustuta esimene ohutult
ja siis saame lihtsalt liikuda juht

270
00:12:53,850 --> 00:12:57,150
käsk, mis oli
Teisel ametiajal siis nüüd

271
00:12:57,150 --> 00:12:59,170
Esmakordne pärast seda
sõlm on kustutatud.

272
00:12:59,170 --> 00:13:01,160
>> Nii uuesti, võttes pilk
seda kui diagramm me

273
00:13:01,160 --> 00:13:05,022
tahad nüüd pop
element off virna.

274
00:13:05,022 --> 00:13:05,730
Mida me siis teeme?

275
00:13:05,730 --> 00:13:08,188
Noh me esimest kavatse luua
uus osuti, mis läheb

276
00:13:08,188 --> 00:13:10,940
osutada sama kohapeal juhina.

277
00:13:10,940 --> 00:13:13,790
Me läheme liigutada ühe positsiooni
edasi, öeldes trav võrdsete

278
00:13:13,790 --> 00:13:17,510
trav kõrval näiteks mis
edendaks trav kursorit ühe

279
00:13:17,510 --> 00:13:19,324
asendis edasi.

280
00:13:19,324 --> 00:13:21,240
Nüüd, kui meil on
hoidke esimene element

281
00:13:21,240 --> 00:13:24,573
läbi pointer nimetatakse nimekirja ja
Teine element läbi pointer nimetatakse

282
00:13:24,573 --> 00:13:28,692
trav, saame julgelt kustutada
Esimene element korstnat

283
00:13:28,692 --> 00:13:30,650
kaotamata ülejäänud
keti sest me

284
00:13:30,650 --> 00:13:32,358
on võimalus viidata
teise elemendi

285
00:13:32,358 --> 00:13:34,780
edastada teel
pointer nimega matk.

286
00:13:34,780 --> 00:13:37,100
>> Nüüd saame tasuta, mis sõlme.

287
00:13:37,100 --> 00:13:38,404
Meil saab tasuta nimekirja.

288
00:13:38,404 --> 00:13:41,320
Ja siis kõik me peame tegema, on praegu
liikuda nimekirja viitavad samale kohale

289
00:13:41,320 --> 00:13:44,482
et matk teeb, ja me oleme justkui tagasi
kust me alustasime, enne kui me tõugata 12

290
00:13:44,482 --> 00:13:45,690
kohta esiteks, eks.

291
00:13:45,690 --> 00:13:46,940
See on täpselt, kus me olime.

292
00:13:46,940 --> 00:13:48,840
Meil oli see neli elementi pinu.

293
00:13:48,840 --> 00:13:49,690
Lisasime viiendiku.

294
00:13:49,690 --> 00:13:51,910
Me nõudsime viiendiku
element, ja siis me

295
00:13:51,910 --> 00:13:55,980
hüppasid, et viimati
lisada element tagasi maha.

296
00:13:55,980 --> 00:13:58,816
>> See on tõesti päris palju
kõik on korstnad.

297
00:13:58,816 --> 00:14:00,190
Võite rakendada neid massiive.

298
00:14:00,190 --> 00:14:01,815
Võite rakendada neid ahelloendid.

299
00:14:01,815 --> 00:14:04,810
On muidugi muud
kuidas rakendada neid samuti.

300
00:14:04,810 --> 00:14:09,060
Põhimõtteliselt põhjus, miks me ei kasuta
virnade on säilitada andmetega sellisel viisil

301
00:14:09,060 --> 00:14:12,090
et viimati lisatud
element on esimene asi, mida me oleme

302
00:14:12,090 --> 00:14:14,980
tahame seda tagasi saada.

303
00:14:14,980 --> 00:14:17,900
Ma olen Doug Lloyd, see on CS50.

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