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

2
00:00:04,074 --> 00:00:05,990
Doug LLOYD: Labi,
tāpēc šajā brīdī jūs esat

3
00:00:05,990 --> 00:00:09,020
iespējams, ir diezgan pazīstams
ar masīvu un saistīti saraksti

4
00:00:09,020 --> 00:00:10,950
kas ir divi galvenais
datu struktūras mēs esam

5
00:00:10,950 --> 00:00:16,810
runāja par glabāšanai komplekti
dati par līdzīgiem datu tipu organizēta.

6
00:00:16,810 --> 00:00:19,080
>> Tagad mēs runāsim
par pāris izmaiņu

7
00:00:19,080 --> 00:00:20,330
par masīvu un saistītiem sarakstiem.

8
00:00:20,330 --> 00:00:22,362
Šajā video mēs ejam
runāt par skursteņi.

9
00:00:22,362 --> 00:00:25,320
Konkrēti mēs runāsim
par datu struktūra sauc kaudze.

10
00:00:25,320 --> 00:00:28,510
Atsaukt no iepriekšējām diskusijām
par norādes un atmiņu,

11
00:00:28,510 --> 00:00:32,060
ka kaudze ir arī
nosaukumu segmentā atmiņas

12
00:00:32,060 --> 00:00:34,980
kur statiski deklarētā
memory-- atmiņas, kas jūs

13
00:00:34,980 --> 00:00:38,730
nosaukt, mainīgie, jūs nosaukums, et
tā tālāk un funkciju rāmji, ko mēs arī

14
00:00:38,730 --> 00:00:41,000
zvanu kaudze rāmji pastāvēt.

15
00:00:41,000 --> 00:00:45,421
Tātad šī ir kaudze datu struktūra
nevis kaudze segments atmiņas.

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

17
00:00:45,920 --> 00:00:46,890
>> Bet kas ir kaudze?

18
00:00:46,890 --> 00:00:49,220
Tātad, tas ir diezgan daudz tikai
īpaša veida struktūra

19
00:00:49,220 --> 00:00:51,190
kas saglabā datus organizētā veidā.

20
00:00:51,190 --> 00:00:53,760
Un tur ir divas ļoti
kopīgas veidus, lai īstenotu

21
00:00:53,760 --> 00:00:57,380
skursteņi, izmantojot divus datu struktūras
ka mēs esam jau iepazinušies ar,

22
00:00:57,380 --> 00:01:00,340
bloki un saistīti saraksti.

23
00:01:00,340 --> 00:01:04,430
Kas padara kaudze īpašs ir
veids, kādā mēs ievietot informāciju

24
00:01:04,430 --> 00:01:08,200
uz kaudze, un to, kā mēs
izņemt informāciju no skursteņa.

25
00:01:08,200 --> 00:01:11,600
Jo īpaši ar skursteņi
noteikums ir tikai pats

26
00:01:11,600 --> 00:01:15,830
Nesen pievienotās elements var noņemt.

27
00:01:15,830 --> 00:01:17,660
>> Tāpēc domāju par to, kā tad, ja tas ir kaudze.

28
00:01:17,660 --> 00:01:21,170
Mēs saliekot informāciju
virsū sevi,

29
00:01:21,170 --> 00:01:24,271
un tikai lieta augšpusē
kaudzes var noņemt.

30
00:01:24,271 --> 00:01:27,020
Mēs nevaram noņemt lieta zem
jo viss pārējais būtu

31
00:01:27,020 --> 00:01:28,020
sabrukt un apgāzties.

32
00:01:28,020 --> 00:01:32,580
Tātad mēs tiešām veidojam kaudze, kas
mums tad ir noņemt gabalu pa gabalu.

33
00:01:32,580 --> 00:01:36,590
Šī iemesla dēļ mēs parasti attiecas
uz kaudze kā LIFO struktūru,

34
00:01:36,590 --> 00:01:38,940
pēdējais iekšā, pirmais ārā.

35
00:01:38,940 --> 00:01:42,290
LIFO, pēdējais iekšā, pirmais ārā.

36
00:01:42,290 --> 00:01:45,635
>> Tāpēc, ka šī ierobežojuma
kā informācija var pievienot

37
00:01:45,635 --> 00:01:49,080
un noņem no skursteņiem, tur tiešām
tikai divas lietas, ko mēs varam darīt ar kaudzīti.

38
00:01:49,080 --> 00:01:52,010
Mēs var virzīt, kas ir
termins mēs izmantojam, lai pievienotu

39
00:01:52,010 --> 00:01:55,130
jauns elements, lai augšpusē
kaudze, vai ja kaudze neeksistē

40
00:01:55,130 --> 00:01:58,550
un mēs esam izveidojot to no nulles,
radot kaudzīti pirmajā vietā

41
00:01:58,550 --> 00:02:00,110
būtu stumšanas.

42
00:02:00,110 --> 00:02:04,990
Un tad pop, tas ir sava veida CS
Termins mēs izmantojam, lai novērstu nesen

43
00:02:04,990 --> 00:02:08,330
pievienots elements no augšas kaudze.

44
00:02:08,330 --> 00:02:11,130
>> Tātad mēs ejam apskatīt gan
realizācijas, gan masīvs balstīta

45
00:02:11,130 --> 00:02:13,120
un saistīts saraksts pamatā.

46
00:02:13,120 --> 00:02:14,870
Un mēs ejam
sākt ar masīvu pamatā.

47
00:02:14,870 --> 00:02:19,990
Tātad, šeit ir pamatideja, ko
masīvs balstīta kaudze datu struktūra

48
00:02:19,990 --> 00:02:21,140
izskatās.

49
00:02:21,140 --> 00:02:23,740
Mums ir drukāti definīcija šeit.

50
00:02:23,740 --> 00:02:27,790
Iekšpusē, ka mums ir divi locekļi
vai lauki struktūru.

51
00:02:27,790 --> 00:02:29,880
Mums ir masīvs.

52
00:02:29,880 --> 00:02:32,400
Un atkal es esmu, izmantojot
patvaļīga datu tips vērtība.

53
00:02:32,400 --> 00:02:35,180
>> Tātad tas varētu būt jebkurš datu tips,
int char vai kādu citu datu

54
00:02:35,180 --> 00:02:37,080
ierakstiet jūs iepriekš izveidojis.

55
00:02:37,080 --> 00:02:39,861
Tāpēc mums ir masīvs lieluma jaudu.

56
00:02:39,861 --> 00:02:44,010
Capacity tiek mārciņu noteikta nemainīga,
varbūt kaut kur citur mūsu failā.

57
00:02:44,010 --> 00:02:47,550
Tātad paziņojums jau ar šo konkrēto
īstenošana mēs iesiešana

58
00:02:47,550 --> 00:02:49,800
paši kā parasti bija
gadījums ar masīviem,

59
00:02:49,800 --> 00:02:53,170
ko mēs nevaram mainīt dinamiski,
ja tur ir noteikts skaits

60
00:02:53,170 --> 00:02:55,450
maksimāli elementus, kas
mēs varam nodot mūsu kaudze.

61
00:02:55,450 --> 00:02:57,930
Šajā gadījumā tas ir jaudas elementus.

62
00:02:57,930 --> 00:03:00,310
>> Mēs arī sekot līdzi
top skursteņa.

63
00:03:00,310 --> 00:03:04,350
Kas elements ir visvairāk
nesen pievienota krāvuma?

64
00:03:04,350 --> 00:03:07,470
Un tā mēs sekot līdzi, kas
ar mainīgo sauc augšas.

65
00:03:07,470 --> 00:03:11,692
Un tas viss izpaužas apkopoja kopā
uz jaunu datu tipu sauc kaudze.

66
00:03:11,692 --> 00:03:13,400
Un, kad mēs esam radīti
Šī jaunā datu tips

67
00:03:13,400 --> 00:03:15,410
mēs varam pret to kā
jebkādu citu datu tipu.

68
00:03:15,410 --> 00:03:20,970
Mēs varam atzīt kaudze s, tāpat kā
mēs varētu darīt int x, vai char vec.

69
00:03:20,970 --> 00:03:22,990
Un, kad mēs sakām kaudze
s, arī to, kas notiek

70
00:03:22,990 --> 00:03:26,420
ir mēs iegūt komplektu
atmiņa atcelt mums.

71
00:03:26,420 --> 00:03:28,770
>> Šajā lietā statusā
Esmu acīmredzot nolēmis

72
00:03:28,770 --> 00:03:33,470
ir 10, jo es esam ieguvuši
single mainīgo tipa kaudze

73
00:03:33,470 --> 00:03:35,320
kas satur divus laukus atcerēties.

74
00:03:35,320 --> 00:03:38,330
Masīvs, šajā gadījumā notiek
būt masīvs integers

75
00:03:38,330 --> 00:03:40,440
kā tas ir lielākajā daļā no maniem piemēriem.

76
00:03:40,440 --> 00:03:43,996
Un vēl viens skaitlis mainīgs
spējīga uzkrāt top,

77
00:03:43,996 --> 00:03:45,870
visvairāk nesen pievienoti
elements uz krāvuma.

78
00:03:45,870 --> 00:03:50,290
Tātad viena kaudze, ko mēs
tāpat definē izskatās šādi.

79
00:03:50,290 --> 00:03:53,190
Tas ir kārba, kas satur
masīvs 10, ko

80
00:03:53,190 --> 00:03:57,280
būs veseli skaitļi šajā gadījumā, un
cits skaitlis mainīgs tur zaļā krāsā

81
00:03:57,280 --> 00:04:00,010
lai norādītu augšējās.

82
00:04:00,010 --> 00:04:02,600
>> Lai uzstādītu augšpusē
kaudze mēs tikai teikt s.top.

83
00:04:02,600 --> 00:04:04,890
Tas, kā mēs piekļūt
lauks būves atsaukšanu.

84
00:04:04,890 --> 00:04:10,460
s.top vienāds ar 0 efektīvi
to dara mūsu kaudze.

85
00:04:10,460 --> 00:04:12,960
Tātad atkal mums ir divas operācijas
ka mēs varam veikt tagad.

86
00:04:12,960 --> 00:04:14,270
Mēs varam virzīt, un mēs varam pop.

87
00:04:14,270 --> 00:04:15,635
Sāksim ar push.

88
00:04:15,635 --> 00:04:18,260
Atkal, spiežot ir pievienojot jaunu
elements uz augšu kaudze.

89
00:04:18,260 --> 00:04:21,460
>> Tātad, ko darīt, mums vajag darīt
šis masīvs balstīta īstenošana?

90
00:04:21,460 --> 00:04:23,210
Nu kopumā
push funkcija notiek

91
00:04:23,210 --> 00:04:26,160
uz nepieciešamību pieņemt
rādītāju uz skursteņa.

92
00:04:26,160 --> 00:04:28,610
Tagad veikt otru un domāt par to.

93
00:04:28,610 --> 00:04:32,840
Kāpēc mēs vēlamies pieņemt
rādītāju uz skursteņa?

94
00:04:32,840 --> 00:04:36,830
Atsaukt no iepriekšējiem video par
Mainīgais joma un norādes,

95
00:04:36,830 --> 00:04:42,350
kas notiktu, ja mēs vienkārši nosūtīts
kaudze, s drīzāk kā parametrs?

96
00:04:42,350 --> 00:04:45,770
Kas faktiski nodots tur?

97
00:04:45,770 --> 00:04:49,430
Atcerieties, mēs radītu kopiju
kad mēs iet to funkciju

98
00:04:49,430 --> 00:04:51,160
ja vien mēs izmantojam norādes.

99
00:04:51,160 --> 00:04:55,380
Un tāpēc šī funkcija push vajadzībām
pieņemt rādītāju uz skursteņa

100
00:04:55,380 --> 00:04:59,160
tāpēc, ka mēs faktiski mainās
kaudze mēs plānojam mainīt.

101
00:04:59,160 --> 00:05:03,060
>> Otra lieta, push, iespējams, vēlas
pieņemt ir datu elements no tipa vērtības.

102
00:05:03,060 --> 00:05:06,970
Šajā gadījumā, atkal, vesels skaitlis, kas
mēs ejam, lai pievienotu uz augšu kaudze.

103
00:05:06,970 --> 00:05:08,680
Tātad, mēs esam ieguvuši mūsu divi parametri.

104
00:05:08,680 --> 00:05:11,310
Ko mēs gatavojamies
tagad darīt iekšpusē push?

105
00:05:11,310 --> 00:05:14,860
Nu, vienkārši, mēs esam tikai gatavojas pievienot
ka elements uz augšējās

106
00:05:14,860 --> 00:05:22,860
un tad mainīt kur aug
kaudze ir, ka s dot top vērtību.

107
00:05:22,860 --> 00:05:25,639
Tātad, tas ir tas, ko funkcija
deklarācija par push

108
00:05:25,639 --> 00:05:27,680
varētu izskatīties izturēties
masīvs bāzes ieviešana.

109
00:05:27,680 --> 00:05:30,967
>> Atkal tas nav grūti un ātri noteikums
ka jūs varētu mainīt šo un

110
00:05:30,967 --> 00:05:32,050
tas atšķiras dažādos veidos.

111
00:05:32,050 --> 00:05:33,840
Varbūt s ir deklarēti visā pasaulē.

112
00:05:33,840 --> 00:05:36,180
Un tāpēc jums nav pat nepieciešams
iziet tas ir kā parametru.

113
00:05:36,180 --> 00:05:39,125
Tas ir atkal tikai
Kopumā gadījumā push.

114
00:05:39,125 --> 00:05:41,000
Un tur ir dažādi
veidi, kā to īstenot.

115
00:05:41,000 --> 00:05:42,810
Bet šajā gadījumā mūsu
push gatavojas veikt

116
00:05:42,810 --> 00:05:48,540
divi argumenti, rādītāju uz kaudze un
datu elements tipa vērtību, skaitlim

117
00:05:48,540 --> 00:05:49,840
šajā gadījumā.

118
00:05:49,840 --> 00:05:52,100
>> Tātad mēs deklarēta s, mēs
teica s.top vienāds ar 0.

119
00:05:52,100 --> 00:05:55,969
Tagad pieņemsim push
numuru 28 uz skursteņa.

120
00:05:55,969 --> 00:05:57,010
Nu ko tas nozīmē?

121
00:05:57,010 --> 00:05:59,600
Nu pašlaik
top no skursteņa ir 0.

122
00:05:59,600 --> 00:06:01,350
Un tā, kas ir būtībā
gatavojas notikt, ir

123
00:06:01,350 --> 00:06:05,820
mēs ejam, lai stick skaitu
28 uz masīvu atrašanās vietā 0.

124
00:06:05,820 --> 00:06:09,540
Diezgan vienkārši, labi, ka
bija top, un tagad mēs esam labi iet.

125
00:06:09,540 --> 00:06:12,910
Un tad mums ir jāmaina, ko
top no kaudze būs.

126
00:06:12,910 --> 00:06:15,130
Tā, ka nākamreiz, kad
mēs push elements,

127
00:06:15,130 --> 00:06:18,017
mēs spēsim saglabāt to
masīvs vieta, iespējams, nav 0.

128
00:06:18,017 --> 00:06:20,100
Mēs nevēlamies pārrakstīt
Ko mēs tikai izvirzīti tur.

129
00:06:20,100 --> 00:06:23,510
Un tāpēc mēs vienkārši pārvietot augšas uz 1.

130
00:06:23,510 --> 00:06:24,890
Tas droši vien ir jēga.

131
00:06:24,890 --> 00:06:28,940
>> Tagad, ja mēs gribam, lai citu elementu
uz steku, teikt, ka mēs vēlamies virzīt 33,

132
00:06:28,940 --> 00:06:33,190
Nu tagad mēs esam tikai gatavojas veikt 33
un nodot to masīva vietas numurs

133
00:06:33,190 --> 00:06:37,580
1, un pēc tam mainīt augšā mūsu
kaudze būt masīvs vietas numurs divi.

134
00:06:37,580 --> 00:06:40,650
Tātad, ja nākamajā reizē mēs vēlamies
push elementu uz steku,

135
00:06:40,650 --> 00:06:43,087
tas būs likts masīva vietā 2.

136
00:06:43,087 --> 00:06:44,420
Un pieņemsim darīt, ka vēl vienu reizi.

137
00:06:44,420 --> 00:06:45,753
Mēs push 19 nost no skursteņi.

138
00:06:45,753 --> 00:06:48,940
Mēs nolikšu 19 masīva vietā 2
un mainīt top mūsu kaudze

139
00:06:48,940 --> 00:06:51,220
būt masīva vieta 3
Tātad, ja nākamo reizi, kad mēs

140
00:06:51,220 --> 00:06:54,780
nepieciešams, lai push mēs esam labi iet.

141
00:06:54,780 --> 00:06:56,980
>> Labi, tā ka ir stumšanas īsumā.

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

143
00:06:57,830 --> 00:07:00,240
Tātad popping ir sava veida
partnere stumšanas.

144
00:07:00,240 --> 00:07:02,720
Tā kā mēs noņemt datus no skursteņa.

145
00:07:02,720 --> 00:07:04,610
Un vispār pop vajadzībām
darīt šādi.

146
00:07:04,610 --> 00:07:07,600
Tas nepieciešams pieņemt rādītāju uz
kaudze, atkal vispārējā gadījumā.

147
00:07:07,600 --> 00:07:10,480
Kādā citā gadījumā jūs varētu
ir paziņojuši kaudze globāli,

148
00:07:10,480 --> 00:07:13,910
tādā gadījumā jums nav nepieciešams nodot
in, jo tas jau ir piekļuve tam

149
00:07:13,910 --> 00:07:15,541
kā globālu mainīgo.

150
00:07:15,541 --> 00:07:17,040
Bet tad ko vēl darīt, mums jādara?

151
00:07:17,040 --> 00:07:21,000
Nu mēs bijām palielināšanai
top kaudze ar push,

152
00:07:21,000 --> 00:07:24,050
tāpēc mēs esam droši vien vēlaties
lai Samazināt augšpusē kaudze

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

154
00:07:25,009 --> 00:07:26,800
Un tad, protams,
mēs arī gatavojas vēlaties

155
00:07:26,800 --> 00:07:29,240
lai atgrieztu vērtību ka mēs noņemam.

156
00:07:29,240 --> 00:07:32,125
Ja mēs esam pievienojot elementus, mēs gribam
iegūt elementus, kas vēlāk,

157
00:07:32,125 --> 00:07:34,000
mēs, iespējams, faktiski
vēlaties saglabāt tos, lai mēs

158
00:07:34,000 --> 00:07:36,490
ne tikai izdzēst tos no
kaudze un tad darīt neko ar tiem.

159
00:07:36,490 --> 00:07:38,500
Parasti, ja mēs esam
stumšana un popping šeit

160
00:07:38,500 --> 00:07:41,250
mēs vēlamies saglabāt šo
informāciju jēgpilnā veidā

161
00:07:41,250 --> 00:07:43,250
un tāpēc tas nepadara
jēga tikai atbrīvoties.

162
00:07:43,250 --> 00:07:46,380
Tātad šī funkcija būtu
iespējams atgriež vērtību pie mums.

163
00:07:46,380 --> 00:07:51,040
>> Tātad tas ir tas, ko iesniegt deklarāciju par pop
varētu izskatīties tur augšējā kreisajā stūrī.

164
00:07:51,040 --> 00:07:53,870
Šī funkcija atgriež
datu tipa vērtības.

165
00:07:53,870 --> 00:07:56,320
Atkal mēs esam bijuši, izmantojot
veseli skaitļi visā.

166
00:07:56,320 --> 00:08:01,916
Un tā pieņem rādītāju uz kaudze kā
tā vienīgais arguments vai vienīgais parametrs.

167
00:08:01,916 --> 00:08:03,040
Tātad, kas ir pop gatavojas darīt?

168
00:08:03,040 --> 00:08:07,990
Teiksim, mēs vēlamies, lai tagad
pop elementu nost no s.

169
00:08:07,990 --> 00:08:14,000
Tik atceros, es teicu, ka skursteņi ir pēdējais
iekšā, pirmais ārā, LIFO datu struktūras.

170
00:08:14,000 --> 00:08:17,855
Kurš elements gatavojas
jāizņem no skursteņa?

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

172
00:08:21,780 --> 00:08:24,150
Vai varat uzminēt, 19?

173
00:08:24,150 --> 00:08:25,290
Tāpēc, ka tu būsi taisnība.

174
00:08:25,290 --> 00:08:28,836
19 bija pēdējā elements mēs pievieno pie
kaudze, kad mums bija stumšanas elementus uz,

175
00:08:28,836 --> 00:08:31,210
Un tā tas notiek, lai pirmais
elements, kas izpaužas noņemts.

176
00:08:31,210 --> 00:08:34,780
Tas ir tā, it kā mēs teicām 28, un
tad mēs ieliekam 33 uz augšu no tā,

177
00:08:34,780 --> 00:08:36,659
un mēs ieliekam 19 virsū, ka.

178
00:08:36,659 --> 00:08:40,650
Vienīgais elements, mēs varam pacelties ir 19.

179
00:08:40,650 --> 00:08:45,019
>> Tagad diagrammā šeit to, ko es esmu darījusi
ir sava veida svītro 19 no masīva.

180
00:08:45,019 --> 00:08:46,810
Tas nav reāli
ko mēs gatavojamies darīt.

181
00:08:46,810 --> 00:08:48,934
Mēs esam tikai gatavojas veida
no izlikties tā tur nav.

182
00:08:48,934 --> 00:08:51,441
Tas joprojām ir tur
ka vieta atmiņā,

183
00:08:51,441 --> 00:08:54,190
bet mēs esam tikai gatavojas to ignorēt
mainot top mūsu kaudze

184
00:08:54,190 --> 00:08:56,080
no tā 3: 2.

185
00:08:56,080 --> 00:08:58,720
Tātad, ja mēs tagad push
vēl viens elements uz steku,

186
00:08:58,720 --> 00:09:00,720
tas būtu vairāk nekā uzrakstīt 19.

187
00:09:00,720 --> 00:09:03,990
>> Bet pieņemsim nav iet caur trouble
svītrojot 19 no skursteņa.

188
00:09:03,990 --> 00:09:05,830
Mēs varam tikai izlikties, ka tur nav.

189
00:09:05,830 --> 00:09:11,107
Nolūkā skursteņa tas ir pagājis, ja
mēs mainīt top būt 2, nevis 3.

190
00:09:11,107 --> 00:09:12,690
Labi, tā ka bija diezgan daudz to.

191
00:09:12,690 --> 00:09:15,080
Tas ir viss, kas mums jādara
pop elementu off.

192
00:09:15,080 --> 00:09:16,090
Darīsim to vēlreiz.

193
00:09:16,090 --> 00:09:18,610
Tāpēc es esmu uzsvērusi to sarkanu šeit
norāda mēs nesam citu zvanu.

194
00:09:18,610 --> 00:09:19,720
Mēs ejam, lai darīt to pašu.

195
00:09:19,720 --> 00:09:20,803
>> Tātad, kas notiek varētu notikt?

196
00:09:20,803 --> 00:09:23,670
Nu, mēs ejam, lai saglabātu
33 X, un mēs ejam

197
00:09:23,670 --> 00:09:26,217
mainīt augšējās 1.

198
00:09:26,217 --> 00:09:29,050
Tā ka, ja mēs tagad ir virzīt
elementu kaudze, kas mums esi

199
00:09:29,050 --> 00:09:31,610
gatavojas darīt tieši tagad,
kas notiek varētu notikt

200
00:09:31,610 --> 00:09:36,367
ir mēs ejam pārrakstīt
masīvs vietas numurs 1.

201
00:09:36,367 --> 00:09:38,950
Tā, ka 33, kas bija sava veida atstāja
aiz ka mēs tikai izlikās

202
00:09:38,950 --> 00:09:44,390
nav tur vairs, mēs esam tikai gatavojas
to clobber to un nodot 40 tur vietā.

203
00:09:44,390 --> 00:09:46,290
Un tad, protams,
jo mēs, push,

204
00:09:46,290 --> 00:09:48,780
mēs ejam izmainiet
augšējā mala no 1, lai 2

205
00:09:48,780 --> 00:09:50,950
tā ka, ja mēs tagad pievienot
vēl viens elements, tas būs

206
00:09:50,950 --> 00:09:54,700
iedziļināties masīvu vietas divām skaits.

207
00:09:54,700 --> 00:09:57,590
>> Tagad saistīti saraksti ir vēl viens
veids, kā īstenot skursteņi.

208
00:09:57,590 --> 00:10:01,210
Un, ja šajā definīcijā par tematu
ekrāns šeit izskatās pazīstams ar jums,

209
00:10:01,210 --> 00:10:04,260
tas ir tāpēc, ka tas izskatās gandrīz
tieši tas pats, patiesībā,

210
00:10:04,260 --> 00:10:07,790
tas diezgan daudz ir tieši
tāds pats kā atsevišķi saistīta sarakstā,

211
00:10:07,790 --> 00:10:11,990
Ja jūs atceraties no mūsu diskusijas par
atsevišķi saistīts sarakstus citā video.

212
00:10:11,990 --> 00:10:15,510
Vienīgais ierobežojums šeit
ir mums kā programmētājiem,

213
00:10:15,510 --> 00:10:17,900
mēs esam nav atļauts
ievietot vai dzēst nejauši

214
00:10:17,900 --> 00:10:20,620
No atsevišķi saistīta sarakstā
ko mēs varētu darīt agrāk.

215
00:10:20,620 --> 00:10:25,820
Tikai tagad mēs varam ievietot un dzēst no
priekšējā vai augšpusē saistīta

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

217
00:10:26,320 --> 00:10:28,028
Tas ir tiešām vienīgais
Atšķirība gan.

218
00:10:28,028 --> 00:10:29,700
Tas ir citādi atsevišķi saistīts saraksts.

219
00:10:29,700 --> 00:10:32,060
Tas ir tikai ierobežojums
aizstāt ar sevi

220
00:10:32,060 --> 00:10:35,770
kā programmētāji, kas
maina to kaudze.

221
00:10:35,770 --> 00:10:39,280
>> Noteikums šeit ir vienmēr uzturēt
rādītāju uz galvas saistītā saraksta.

222
00:10:39,280 --> 00:10:41,520
Tas, protams, ir vispār
Svarīgs noteikums pirmais.

223
00:10:41,520 --> 00:10:44,260
Par atsevišķi saistīts saraksts vienalga jums
tikai nepieciešams rādītāju uz galvas

224
00:10:44,260 --> 00:10:46,160
lai būtu kas
ķēde var nodot

225
00:10:46,160 --> 00:10:48,596
uz jebkuru citu elementu
kas saistīts sarakstā.

226
00:10:48,596 --> 00:10:50,470
Bet tas ir īpaši
svarīgi ar kaudzīti.

227
00:10:50,470 --> 00:10:52,386
Un tā vispār esat
gatavojas tiešām vēlaties

228
00:10:52,386 --> 00:10:54,090
šis rādītājs ir globāla mainīga.

229
00:10:54,090 --> 00:10:56,574
Tas iespējams, gatavojas
būt vēl vienkāršāk, ka veidā.

230
00:10:56,574 --> 00:10:58,240
Tātad, kādi ir analogi push un pop?

231
00:10:58,240 --> 00:10:58,740
Tiesības.

232
00:10:58,740 --> 00:11:01,812
Tātad spiežot atkal ir pievienojot
jauns elements kaudze.

233
00:11:01,812 --> 00:11:03,770
In saistītajā sarakstā, kas
nozīmē, ka mēs esam nāksies

234
00:11:03,770 --> 00:11:07,770
lai izveidotu jaunu mezglu, ka mēs esam
gatavojas pievienot uz saistīts sarakstā,

235
00:11:07,770 --> 00:11:10,500
un pēc tam izpildiet rūpīgu darbības
ka mēs esam minēts iepriekš

236
00:11:10,500 --> 00:11:16,050
jo atsevišķi saistītas sarakstos, lai pievienotu to
ķēdi, nesalaužot ķēdi

237
00:11:16,050 --> 00:11:18,900
un zaudēt vai orphaning jebkurš
elementi, kas saistīti sarakstā.

238
00:11:18,900 --> 00:11:21,820
Un tas būtībā, ko tas
maz lāse teksta tur apkopoti.

239
00:11:21,820 --> 00:11:23,740
Un pieņemsim to apskatīt
pie tā kā diagrammā.

240
00:11:23,740 --> 00:11:24,823
>> Tātad, šeit ir mūsu saistīts saraksts.

241
00:11:24,823 --> 00:11:26,620
Tas vienlaikus ir četri elementi.

242
00:11:26,620 --> 00:11:30,420
Un vēl pilnīgi šeit ir mūsu
kaudze, kas satur četrus elementus.

243
00:11:30,420 --> 00:11:36,030
Un pieņemsim, ka mēs tagad gribam
push jaunu posteni uz šo kaudze.

244
00:11:36,030 --> 00:11:39,792
Un mēs vēlamies, lai push jaunu
priekšmetus, kuru dati vērtība ir 12.

245
00:11:39,792 --> 00:11:41,000
Nu ko mēs gatavojamies darīt?

246
00:11:41,000 --> 00:11:43,420
Nu, pirmkārt, mēs spēsim
malloc telpu, dinamiski

247
00:11:43,420 --> 00:11:45,411
piešķirt vietu jaunu mezglu.

248
00:11:45,411 --> 00:11:48,160
Un, protams, uzreiz pēc
mēs piezvanītu malloc mēs vienmēr

249
00:11:48,160 --> 00:11:52,989
pārliecinieties, lai pārbaudītu null,
jo, ja mēs saņēmām null atpakaļ

250
00:11:52,989 --> 00:11:54,280
tur bija daži no problēmas veida.

251
00:11:54,280 --> 00:11:57,570
Mēs nevēlamies, lai dereference šo null
rādītāju vai jūs cietīs SEG vaina.

252
00:11:57,570 --> 00:11:58,510
Tas nav labi.

253
00:11:58,510 --> 00:11:59,760
Tātad, mēs esam malloced mezgla.

254
00:11:59,760 --> 00:12:01,260
Mēs pieņemam, mēs esam bija panākumi šeit.

255
00:12:01,260 --> 00:12:06,090
Mēs ejam, lai likt 12 uz
datu lauks šajā mezglā.

256
00:12:06,090 --> 00:12:11,570
Tagad jūs atcerēties, kurš no mūsu norādes
pārceļas nākamais tāpēc mums nav pārtraukumu ķēdi?

257
00:12:11,570 --> 00:12:15,100
Mums ir pāris iespējas, šeit, bet
vienīgais, kas notiek, lai būtu droši

258
00:12:15,100 --> 00:12:19,330
ir noteikt jaunumus nākamo rādītāju
punkts uz veco galvas saraksta

259
00:12:19,330 --> 00:12:21,360
vai ko drīz būs
vecais vadītājs saraksta.

260
00:12:21,360 --> 00:12:23,610
Un tagad, ka visi mūsu
elementi tiek chained kopā,

261
00:12:23,610 --> 00:12:27,370
mēs varam vienkārši pārvietot sarakstu norādīt
uz to pašu vietu, kas jauns dara.

262
00:12:27,370 --> 00:12:33,550
Un tagad mēs esam faktiski uzstājām
jauns elements uz priekšu no skursteņa.

263
00:12:33,550 --> 00:12:36,420
>> Pop mēs vienkārši vēlamies
dzēst šo pirmo elementu.

264
00:12:36,420 --> 00:12:38,150
Un tā būtībā kas
mums ir jādara šeit,

265
00:12:38,150 --> 00:12:40,050
arī mums ir jāatrod uz otro elementu.

266
00:12:40,050 --> 00:12:43,540
Galu galā, kas kļūs par jauno
galvu, kad mēs dzēst pirmo.

267
00:12:43,540 --> 00:12:47,300
Tāpēc mums ir nepieciešams, lai sāktu no
sākums, pārvietot vienu priekšu.

268
00:12:47,300 --> 00:12:50,340
Kad mēs esam ieguvuši turēt uz vienu
uz priekšu, kur mēs šobrīd

269
00:12:50,340 --> 00:12:53,850
mēs varam izdzēst pirmā droši
un tad mēs varam vienkārši pārvietot galvu

270
00:12:53,850 --> 00:12:57,150
norādīt uz to, kas bija
otrais termins, un tad tagad

271
00:12:57,150 --> 00:12:59,170
ir pirmais pēc ka
mezgls ir izdzēsta.

272
00:12:59,170 --> 00:13:01,160
>> Tātad vēlreiz, ņemot apskatīt
uz to kā diagrammā mums

273
00:13:01,160 --> 00:13:05,022
gribu tagad pop
elements pie šīs kaudze.

274
00:13:05,022 --> 00:13:05,730
Tātad, ko mēs darām?

275
00:13:05,730 --> 00:13:08,188
Nu mēs esam pirmais gatavojas izveidot
jauns rādītājs, kas notiek

276
00:13:08,188 --> 00:13:10,940
norādīt uz tajā pašā vietā kā galvas.

277
00:13:10,940 --> 00:13:13,790
Mēs ejam, lai to pārvietotu vienu pozīciju
priekšu, sakot Trav Vienāds

278
00:13:13,790 --> 00:13:17,510
Trav blakus piemēram, kas
varētu sekmēt Trav rādītāju vienu

279
00:13:17,510 --> 00:13:19,324
pozīciju uz priekšu.

280
00:13:19,324 --> 00:13:21,240
Tagad, ka mēs esam ieguvuši
turēt uz pirmā elementa

281
00:13:21,240 --> 00:13:24,573
caur rādītāja sauc saraksts, un
Otrs elements caur rādītājs sauc

282
00:13:24,573 --> 00:13:28,692
Trav, mēs varam droši izdzēst, ka
Pirmais elements no skursteņa

283
00:13:28,692 --> 00:13:30,650
nezaudējot pārējo
ķēdes, jo mēs

284
00:13:30,650 --> 00:13:32,358
ir veids, kā atsaukties
otrajam elementam

285
00:13:32,358 --> 00:13:34,780
nosūta, kas paredzētas ar
rādītājs sauc trav.

286
00:13:34,780 --> 00:13:37,100
>> Tāpēc tagad mēs varam atbrīvot šo mezglu.

287
00:13:37,100 --> 00:13:38,404
Mēs varam brīvajā sarakstā.

288
00:13:38,404 --> 00:13:41,320
Un tad viss, kas mums ir jādara tagad
pārvietot sarakstu norādīt uz to pašu vietu

289
00:13:41,320 --> 00:13:44,482
ka Trav dara, un mēs esam veida atpakaļ
kur mēs sākām pirms mēs uzstājām 12

290
00:13:44,482 --> 00:13:45,690
par pirmo vietu, pa labi.

291
00:13:45,690 --> 00:13:46,940
Tas ir tieši tas, kur mēs bijām.

292
00:13:46,940 --> 00:13:48,840
Mums bija šo četru elementu kaudze.

293
00:13:48,840 --> 00:13:49,690
Mēs pievienoja piekto.

294
00:13:49,690 --> 00:13:51,910
Mēs uzstājām piekto
elements uz, un pēc tam mēs

295
00:13:51,910 --> 00:13:55,980
popped ka nesen
pievienots elements atpakaļ off.

296
00:13:55,980 --> 00:13:58,816
>> Tas ir tiešām diezgan daudz
visi ir skursteņi.

297
00:13:58,816 --> 00:14:00,190
Jūs varat tos īstenot, kā masīvi.

298
00:14:00,190 --> 00:14:01,815
Jūs varat tos īstenot kā saistīti sarakstus.

299
00:14:01,815 --> 00:14:04,810
Ir, protams, citi
veidi, kā tos īstenot, kā arī.

300
00:14:04,810 --> 00:14:09,060
Būtībā iemesls, mēs varētu izmantot
stacks ir, lai saglabātu datus tādā veidā,

301
00:14:09,060 --> 00:14:12,090
ka nesen pievienotās
elements ir pirmā lieta, ko mēs esam

302
00:14:12,090 --> 00:14:14,980
gatavojas vēlaties, lai saņemtu atpakaļ.

303
00:14:14,980 --> 00:14:17,900
Es esmu Doug Lloyd, tas ir CS50.

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