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

2
00:00:04,074 --> 00:00:05,990
Doug LLOYD: Pekala,
sen bu noktada öylesine

3
00:00:05,990 --> 00:00:09,020
Muhtemelen oldukça tanıdık
diziler ve bağlantılı listelerle

4
00:00:09,020 --> 00:00:10,950
İki primer hangi
veri yapıları biz ettik

5
00:00:10,950 --> 00:00:16,810
kümelerini tutmak için konuştuk
benzer veri türleri veri düzenledi.

6
00:00:16,810 --> 00:00:19,080
>> Şimdi konuşmak için gidiyoruz
varyasyonların bir çift hakkında

7
00:00:19,080 --> 00:00:20,330
diziler ve bağlantılı listelerde.

8
00:00:20,330 --> 00:00:22,362
Bu videoda gidiyoruz
yığınları hakkında konuşmak için.

9
00:00:22,362 --> 00:00:25,320
Özellikle biz konuşacağız
Bir veri yapısı bir yığın çağırdı.

10
00:00:25,320 --> 00:00:28,510
Önceki tartışmalardan hatırlayın
işaretçiler ve bellek hakkında,

11
00:00:28,510 --> 00:00:32,060
istifi de olduğu
bellek segment için isim

12
00:00:32,060 --> 00:00:34,980
Statik ilan nerede
memory-- hafıza size

13
00:00:34,980 --> 00:00:38,730
Eğer isim değişkenler, isim, et
saire ve fonksiyon kare olan, ayrıca

14
00:00:38,730 --> 00:00:41,000
Çağrı yığını çerçeveleri var.

15
00:00:41,000 --> 00:00:45,421
Yani bu bir yığın veri yapısıdır
bellek değil yığın segmenti.

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

17
00:00:45,920 --> 00:00:46,890
>> Ama yığını nedir?

18
00:00:46,890 --> 00:00:49,220
Yani bu sadece bir oldukça çok var
Yapının özel bir tür

19
00:00:49,220 --> 00:00:51,190
Bu organize bir şekilde verileri korur.

20
00:00:51,190 --> 00:00:53,760
Ve iki çok var
Ortak yolları uygulamak

21
00:00:53,760 --> 00:00:57,380
İki veri yapılarını kullanarak yığınlarının
biz zaten aşina olduğunuzu,

22
00:00:57,380 --> 00:01:00,340
diziler ve bağlantılı listeler.

23
00:01:00,340 --> 00:01:04,430
Ne bir yığın özel yapar
Biz bilgileri koymak hangi yolu

24
00:01:04,430 --> 00:01:08,200
yığını ve yol biz içine
yığından bilgileri siler.

25
00:01:08,200 --> 00:01:11,600
Yığınları ile özellikle de
kural sadece en çok

26
00:01:11,600 --> 00:01:15,830
en son eklenen eleman çıkarılabilir.

27
00:01:15,830 --> 00:01:17,660
>> Bir yığın var sanki Yani düşün.

28
00:01:17,660 --> 00:01:21,170
Biz bilgi kazık ediyoruz
kendisi üstünde,

29
00:01:21,170 --> 00:01:24,271
üstünde ve tek şey
yığının çıkarılabilir.

30
00:01:24,271 --> 00:01:27,020
Biz altında bir şey çıkaramazsınız
her şey olur, çünkü

31
00:01:27,020 --> 00:01:28,020
daraltmak ve düşmenize.

32
00:01:28,020 --> 00:01:32,580
Yani biz gerçekten bir yığın inşa ediyoruz
biz sonra parça parça çıkarmak zorunda.

33
00:01:32,580 --> 00:01:36,590
Bu nedenle biz bunlara atıfta
Bir LIFO yapı olarak bir yığına,

34
00:01:36,590 --> 00:01:38,940
, İlk out sürer.

35
00:01:38,940 --> 00:01:42,290
LIFO, ilk ortaya sürer.

36
00:01:42,290 --> 00:01:45,635
>> Yani çünkü bu kısıtlama on
bilgilerin eklenebildiğini

37
00:01:45,635 --> 00:01:49,080
ve bir yığından kaldırılır, orada gerçekten
sadece iki şey bir yığın yapabilir.

38
00:01:49,080 --> 00:01:52,010
Biz hangi zorlayabilir
biz eklemek için kullanın terim

39
00:01:52,010 --> 00:01:55,130
üstüne yeni bir unsur
yığını, ya da eğer yığın yok

40
00:01:55,130 --> 00:01:58,550
ve biz, sıfırdan yaratıyoruz
ilk etapta yığını oluşturarak

41
00:01:58,550 --> 00:02:00,110
iterek olacaktır.

42
00:02:00,110 --> 00:02:04,990
Ve sonra pop, o CS çeşit
terim biz en son kaldırmak için kullanın

43
00:02:04,990 --> 00:02:08,330
yığının üst elemanı ekledi.

44
00:02:08,330 --> 00:02:11,130
>> Yani biz hem de bakmak için gidiyoruz
uygulamalar, hem dizi bazlı

45
00:02:11,130 --> 00:02:13,120
ve bağlantılı liste tabanlı.

46
00:02:13,120 --> 00:02:14,870
Ve biz gidiyoruz
tabanlı dizi ile başlar.

47
00:02:14,870 --> 00:02:19,990
Yani burada temel fikir nedir
Dizi tabanlı yığın veri yapısı

48
00:02:19,990 --> 00:02:21,140
gibi görünecektir.

49
00:02:21,140 --> 00:02:23,740
Biz burada bir yazılı tanımı var.

50
00:02:23,740 --> 00:02:27,790
Bunun İçinde iki üyemiz var
yapısının veya alanları.

51
00:02:27,790 --> 00:02:29,880
Biz bir dizi var.

52
00:02:29,880 --> 00:02:32,400
Ve yine ben kullanıyorum
keyfi veri türü değeri.

53
00:02:32,400 --> 00:02:35,180
>> Yani bu herhangi bir veri türü olabilir,
int char veya başka bir veri

54
00:02:35,180 --> 00:02:37,080
Eğer daha önce oluşturduğunuz yazın.

55
00:02:37,080 --> 00:02:39,861
Bu yüzden boyut kapasitesinin bir dizi var.

56
00:02:39,861 --> 00:02:44,010
Kapasite kiloluk sabit tanımlandığı
belki başka bir yerde bizim dosyada.

57
00:02:44,010 --> 00:02:47,550
Yani bu özel zaten fark
Biz sınırlayıcı olan uygulama

58
00:02:47,550 --> 00:02:49,800
kendimizi tipik olarak oldu
Dizilerle durum,

59
00:02:49,800 --> 00:02:53,170
dinamik olarak yeniden boyutlandırmak olamaz ki,
nerede belli bir numara var

60
00:02:53,170 --> 00:02:55,450
elemanlarının en fazla olduğu
Bizim yığın koyabilirsiniz.

61
00:02:55,450 --> 00:02:57,930
Bu durumda kapasite elemanları var.

62
00:02:57,930 --> 00:03:00,310
>> Biz de takip
yığının üst.

63
00:03:00,310 --> 00:03:04,350
En neler unsurdur
Son zamanlarda yığına eklendi?

64
00:03:04,350 --> 00:03:07,470
Ve böylece biz o takip
Değişken olarak adlandırılan üst.

65
00:03:07,470 --> 00:03:11,692
Ve bu arada sarılmış olur
Bir yığın olarak adlandırılan yeni bir veri türü içine.

66
00:03:11,692 --> 00:03:13,400
Ve biz oluşturulan konum kez
Bu yeni veri türü

67
00:03:13,400 --> 00:03:15,410
biz gibi davranabilirsiniz
Başka bir veri türü.

68
00:03:15,410 --> 00:03:20,970
Biz gibi, yığın s bildirebilirsiniz
Biz int x, y veya karakter yapabilirdi.

69
00:03:20,970 --> 00:03:22,990
Ve biz yığın dediğim zaman
s, iyi ne olur

70
00:03:22,990 --> 00:03:26,420
Biz bir dizi olsun bir
Hafıza bizim için kenara koyun.

71
00:03:26,420 --> 00:03:28,770
>> Bu durumda kapasitesi
Ben görünüşe göre karar verdim

72
00:03:28,770 --> 00:03:33,470
Ben bir var, çünkü 10
tipi yığının tek değişken

73
00:03:33,470 --> 00:03:35,320
hangi iki alan hatırlamak içerir.

74
00:03:35,320 --> 00:03:38,330
Bu durumda bir dizi, gidiyor
tamsayılar dizisi olmaya

75
00:03:38,330 --> 00:03:40,440
benim örneklerin çoğu böyledir.

76
00:03:40,440 --> 00:03:43,996
Ve başka bir tamsayı değişken
üst depolayabilen,

77
00:03:43,996 --> 00:03:45,870
en son eklenen
yığına element.

78
00:03:45,870 --> 00:03:50,290
Yani tek bir yığın ne
Sadece bu gibi görünüyor tanımlanmış.

79
00:03:50,290 --> 00:03:53,190
Bu içeren bir kutu var
10 bir dizi nedir

80
00:03:53,190 --> 00:03:57,280
Bu durumda tamsayı ve
yeşil orada başka bir tamsayı değişken

81
00:03:57,280 --> 00:04:00,010
yığının üst gösterir.

82
00:04:00,010 --> 00:04:02,600
>> Üst ayarlamak için
Yığın biz sadece s.top demek.

83
00:04:02,600 --> 00:04:04,890
Yani biz bir erişim nasıl
Bir yapı hatırlama alanı.

84
00:04:04,890 --> 00:04:10,460
s.top etkin bir 0'a eşittir
Bizim yığına yapar.

85
00:04:10,460 --> 00:04:12,960
Yani yine biz iki operasyonları var
Şimdi gerçekleştirebilirsiniz.

86
00:04:12,960 --> 00:04:14,270
Biz itebilir ve biz pop olabilir.

87
00:04:14,270 --> 00:04:15,635
Push ile başlayalım.

88
00:04:15,635 --> 00:04:18,260
Yine, yeni ekliyor bastırıyor
yığının üstüne öğesi.

89
00:04:18,260 --> 00:04:21,460
>> Peki ne yapmak gerekiyor
Bu dizi tabanlı uygulama?

90
00:04:21,460 --> 00:04:23,210
Peki genel The
itme fonksiyonu gidiyor

91
00:04:23,210 --> 00:04:26,160
Bir kabul etmek gerekir
yığına işaretçisi.

92
00:04:26,160 --> 00:04:28,610
Şimdi bir saniyenizi ayırın ve bunu bir düşün.

93
00:04:28,610 --> 00:04:32,840
Neden kabul etmek isteyeyim
yığına bir işaretçi?

94
00:04:32,840 --> 00:04:36,830
Önceki videolar hatırlayın
Değişken kapsamı ve işaretçileri,

95
00:04:36,830 --> 00:04:42,350
biz sadece gönderirse ne olur
yığın, bir parametre olarak oldukça s?

96
00:04:42,350 --> 00:04:45,770
Aslında orada ne geçti ki?

97
00:04:45,770 --> 00:04:49,430
Biz bir kopyasını oluştururken hatırla
Biz bir işleve geçmesi zaman

98
00:04:49,430 --> 00:04:51,160
sürece biz işaretçileri kullanmak.

99
00:04:51,160 --> 00:04:55,380
Ve böylece bu fonksiyon ihtiyaçlarını itmek
yığına bir işaretçi kabul etmek

100
00:04:55,380 --> 00:04:59,160
biz aslında değişen konum, böylece
Yığın biz değiştirmek niyetinde.

101
00:04:59,160 --> 00:05:03,060
>> Başka bir şey itme muhtemelen istiyor
kabul türü değeri veri elemanıdır.

102
00:05:03,060 --> 00:05:06,970
Bu durumda, yine bir tamsayıdır bu
Biz yığının üstüne eklemek için gidiyoruz.

103
00:05:06,970 --> 00:05:08,680
Bu yüzden bizim iki parametre var.

104
00:05:08,680 --> 00:05:11,310
Biz ne yapacağız
Şimdi itme içinde do?

105
00:05:11,310 --> 00:05:14,860
Peki, sadece, sadece eklemek için gidiyoruz
yığının üstüne unsuru

106
00:05:14,860 --> 00:05:22,860
ve daha sonra burada üst değiştirme
Yığın o üst değer nokta s vardır.

107
00:05:22,860 --> 00:05:25,639
Peki bu ne bir işlevdir
itme bildirimi

108
00:05:25,639 --> 00:05:27,680
Bir de gibi görünebilir
dizi tabanlı uygulama.

109
00:05:27,680 --> 00:05:30,967
>> Yine bu sert ve hızlı bir kural değil
Bunu değiştirmek olabileceğini

110
00:05:30,967 --> 00:05:32,050
Bu farklı şekillerde değişir.

111
00:05:32,050 --> 00:05:33,840
Belki s küresel ilan edilir.

112
00:05:33,840 --> 00:05:36,180
Ve böylece bile gerek yok
Bir parametre olarak pass etmek.

113
00:05:36,180 --> 00:05:39,125
Bu yine sadece bir
itme genel durum.

114
00:05:39,125 --> 00:05:41,000
Ve farklı vardır
yolları uygulamak için.

115
00:05:41,000 --> 00:05:42,810
Ancak bu durumda bizim
itme alacak

116
00:05:42,810 --> 00:05:48,540
İki argüman, bir yığın bir işaretçi ve
türü değeri tamsayı veri elemanı

117
00:05:48,540 --> 00:05:49,840
bu durumda.

118
00:05:49,840 --> 00:05:52,100
>> Bu yüzden biz, s beyan
s.top 0'a eşittir söyledi.

119
00:05:52,100 --> 00:05:55,969
Şimdi basalım
yığına sayısı 28.

120
00:05:55,969 --> 00:05:57,010
Peki bu ne anlama geliyor?

121
00:05:57,010 --> 00:05:59,600
Peki şu anda
yığınının üst 0'dır.

122
00:05:59,600 --> 00:06:01,350
Ve böylece temelde ne var
ne olacak olan

123
00:06:01,350 --> 00:06:05,820
Biz numarayı sopa gidiyoruz
Dizi konumu 0 28..

124
00:06:05,820 --> 00:06:09,540
Oldukça basit, doğru, o
üst oldu ve şimdi biz gitmek için iyi bir konum.

125
00:06:09,540 --> 00:06:12,910
Ve sonra ne değiştirmeniz gerekir
yığının üstünde olacak.

126
00:06:12,910 --> 00:06:15,130
Bir dahaki sefere Böylece
Biz bir element itin,

127
00:06:15,130 --> 00:06:18,017
Biz bunu saklamak için gidiyoruz
Dizi konumu, muhtemelen 0.

128
00:06:18,017 --> 00:06:20,100
Biz üzerine istemiyoruz
Biz sadece orada ne koymak.

129
00:06:20,100 --> 00:06:23,510
Ve böylece biz sadece üst 1 hareket edeceğiz.

130
00:06:23,510 --> 00:06:24,890
Muhtemelen mantıklı.

131
00:06:24,890 --> 00:06:28,940
>> Şimdi başka bir eleman koymak istiyorsanız
yığına, biz 33 itmek istiyor demek

132
00:06:28,940 --> 00:06:33,190
de şimdi biz sadece 33 almaya gidiyoruz
ve dizi konum numarasına koydu

133
00:06:33,190 --> 00:06:37,580
1 ve daha sonra üst değiştirmek bizim
Dizi yeri iki numara olmak yığını.

134
00:06:37,580 --> 00:06:40,650
Yani bir dahaki sefere biz istiyoruz
yığına bir elemanı itmek,

135
00:06:40,650 --> 00:06:43,087
bu dizi bir konumda 2 koymak olacak.

136
00:06:43,087 --> 00:06:44,420
Ve en olduğunu bir kez daha yapalım.

137
00:06:44,420 --> 00:06:45,753
Biz yığınlarının kapalı 19 itmek gerekir.

138
00:06:45,753 --> 00:06:48,940
Biz dizi konumda 2 19 takacağım
ve bizim yığının üst değiştirme

139
00:06:48,940 --> 00:06:51,220
Dizi yeri 3 olmak
böylece bir dahaki sefere biz eğer

140
00:06:51,220 --> 00:06:54,780
biz gitmek için iyi bir konum, bir itme yapmak gerekir.

141
00:06:54,780 --> 00:06:56,980
>> Tamam, böylece Özetle itiyor.

142
00:06:56,980 --> 00:06:57,830
Ne haşhaş dersiniz?

143
00:06:57,830 --> 00:07:00,240
Yani haşhaş çeşit
iterek meslektaşı.

144
00:07:00,240 --> 00:07:02,720
Biz yığından verileri kaldırmak nasıl.

145
00:07:02,720 --> 00:07:04,610
Ve genel pop ihtiyaçları
aşağıdakileri yapmak.

146
00:07:04,610 --> 00:07:07,600
Bu bir işaretçi kabul etmek gerekiyor
genel durumda tekrar yığını.

147
00:07:07,600 --> 00:07:10,480
Diğer bazı durumda olabilir
küresel yığın ilan ettiler,

148
00:07:10,480 --> 00:07:13,910
bu durumda onu geçmek gerekmez
Çünkü o zaten erişimi olan

149
00:07:13,910 --> 00:07:15,541
Bir global değişken olarak.

150
00:07:15,541 --> 00:07:17,040
Ama başka sonra ne yapmamız gerekiyor?

151
00:07:17,040 --> 00:07:21,000
Peki biz artan edildi
push yığının üst

152
00:07:21,000 --> 00:07:24,050
bu yüzden biz muhtemelen istediğiniz gidiyoruz
yığının üst azaltma

153
00:07:24,050 --> 00:07:25,009
pop, değil mi?

154
00:07:25,009 --> 00:07:26,800
Ve sonra tabii ki
biz de istediğiniz gidiyoruz

155
00:07:26,800 --> 00:07:29,240
Biz kaldırmak değer döndürmek için.

156
00:07:29,240 --> 00:07:32,125
Biz öğeleri ekleyerek ediyorsanız, biz istiyoruz
Daha sonra unsurları çıkmak,

157
00:07:32,125 --> 00:07:34,000
Muhtemelen aslında
Onları bu yüzden saklamak istediğiniz

158
00:07:34,000 --> 00:07:36,490
Sadece onları silmeyin
üste sonra onlarla bir şey yapmak.

159
00:07:36,490 --> 00:07:38,500
Genellikle biz eğer
itme ve burada haşhaş

160
00:07:38,500 --> 00:07:41,250
Bu saklamak istediğiniz
anlamlı bir şekilde bilgi

161
00:07:41,250 --> 00:07:43,250
ve bu yüzden yapmaz
duygusu sadece atmak.

162
00:07:43,250 --> 00:07:46,380
Yani bu fonksiyon gerekir
Muhtemelen bize bir değer döndürür.

163
00:07:46,380 --> 00:07:51,040
>> Peki bu pop için ne bir beyan olduğunu
sol üst kısmında orada gibi görünebilir.

164
00:07:51,040 --> 00:07:53,870
Bu işlev döndürür
türü değerinin veri.

165
00:07:53,870 --> 00:07:56,320
Yine kullanılarak oldum
tamsayılar boyunca.

166
00:07:56,320 --> 00:08:01,916
Ve bir yığın olarak bir işaretçi kabul
tamamen kendi argümanı ya da tek bir parametre.

167
00:08:01,916 --> 00:08:03,040
Peki pop yapacak?

168
00:08:03,040 --> 00:08:07,990
En şimdi istiyoruz diyelim
s kapalı bir unsuru pop.

169
00:08:07,990 --> 00:08:14,000
Yani yığınları son olduğunu söyledi hatırlıyorum
ilk önce, LIFO veri yapıları içinde.

170
00:08:14,000 --> 00:08:17,855
Hangi eleman gidiyor
istiften çıkarılabilir?

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

172
00:08:21,780 --> 00:08:24,150
Eğer 19 tahmin mü?

173
00:08:24,150 --> 00:08:25,290
Eğer haklı olurdunuz çünkü.

174
00:08:25,290 --> 00:08:28,836
19 Biz eklenen son eleman oldu
biz öğeleri iterek zaman yığını,

175
00:08:28,836 --> 00:08:31,210
ve bu yüzden ilk gidiyor
kaldırılırsa unsur.

176
00:08:31,210 --> 00:08:34,780
Biz 28 dedi sanki, ve
o zaman biz, bunun üstüne koymak 33

177
00:08:34,780 --> 00:08:36,659
ve biz bunun üstüne 19 koydu.

178
00:08:36,659 --> 00:08:40,650
Biz çıkarabilirsin tek unsur 19'dur.

179
00:08:40,650 --> 00:08:45,019
>> Şimdi, burada şemada ne yaptığımı
tür diziden 19 silinir.

180
00:08:45,019 --> 00:08:46,810
Aslında değil
ne yapacağız.

181
00:08:46,810 --> 00:08:48,934
Biz sadece tür gidiyoruz
bir o orada yokmuş gibi davranırız.

182
00:08:48,934 --> 00:08:51,441
O orada hala
bellek konumu,

183
00:08:51,441 --> 00:08:54,190
ama biz sadece bunu görmezden için gidiyoruz
Bizim yığının üst değiştirerek

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

185
00:08:56,080 --> 00:08:58,720
Biz eğer öyleyse şimdi itin
yığına başka unsur,

186
00:08:58,720 --> 00:09:00,720
Bitti 19 yazardı.

187
00:09:00,720 --> 00:09:03,990
>> Ama sorun değil üzerinden gidelim
yığından 19 silme.

188
00:09:03,990 --> 00:09:05,830
Biz sadece orada değil iddia edebilir.

189
00:09:05,830 --> 00:09:11,107
Yığının amaçları için, eğer gitti
Biz 2 yerine 3 olmak üzere üst değiştirin.

190
00:09:11,107 --> 00:09:12,690
Pekâlâ, bu oldukça fazlaydı bu yüzden.

191
00:09:12,690 --> 00:09:15,080
Yani yapmamız gereken tek şey
bir öğe kapalı pop.

192
00:09:15,080 --> 00:09:16,090
Hadi bir daha yapalım.

193
00:09:16,090 --> 00:09:18,610
Yani burada kırmızı bunu vurguladık
biz başka bir çağrı yapıyoruz gösteriyor.

194
00:09:18,610 --> 00:09:19,720
Biz de aynı şeyi yapacağız.

195
00:09:19,720 --> 00:09:20,803
>> Peki ne olacak?

196
00:09:20,803 --> 00:09:23,670
Peki, biz saklamak için gidiyoruz
X 33 ve biz gidiyoruz

197
00:09:23,670 --> 00:09:26,217
1 yığının üst değiştirmek için.

198
00:09:26,217 --> 00:09:29,050
Biz itmek şimdi olsaydı Böylece
Biz konum yığına element

199
00:09:29,050 --> 00:09:31,610
Şu anda yapacaksın,
ne olacak

200
00:09:31,610 --> 00:09:36,367
Biz yazma gidiyoruz olduğunu
Dizi yeri 1 numara.

201
00:09:36,367 --> 00:09:38,950
Sıralama bırakıldı olduğu 33 Böylece
arkasında biz sadece davrandı

202
00:09:38,950 --> 00:09:44,390
artık orada değil, biz sadece gidiyoruz
Bunu clobber ve orada yerine 40 koymak.

203
00:09:44,390 --> 00:09:46,290
Ve sonra tabii ki,
Biz bir itme yaptı beri,

204
00:09:46,290 --> 00:09:48,780
Biz artırmak için gidiyoruz
1 ila 2 yığının üst

205
00:09:48,780 --> 00:09:50,950
bu yüzden şimdi eklerseniz o
Başka bir öğesi olacak

206
00:09:50,950 --> 00:09:54,700
Dizi yeri iki numaralı gidin.

207
00:09:54,700 --> 00:09:57,590
>> Şimdi bağlantılı listeler başka vardır
yığınları uygulamak için bir yol.

208
00:09:57,590 --> 00:10:01,210
Ve bu tanım ise
Ekran burada, size tanıdık görünüyor

209
00:10:01,210 --> 00:10:04,260
neredeyse görünüyor çünkü bu kadar
aynı, aslında,

210
00:10:04,260 --> 00:10:07,790
hemen hemen tam olarak
Bir tek tek bağlantılı liste olarak aynı,

211
00:10:07,790 --> 00:10:11,990
Eğer bizim tartışmasından hatırlayacak olursak
tek başına başka bir videoda listeleri bağlantılı.

212
00:10:11,990 --> 00:10:15,510
Buradaki tek kısıtlama
, programcılar olarak bizim için

213
00:10:15,510 --> 00:10:17,900
biz izin yok
eklemek veya rasgele silme

214
00:10:17,900 --> 00:10:20,620
tek başına bağlantılı listeden
Daha önce yapabilirdi ki.

215
00:10:20,620 --> 00:10:25,820
Biz şimdi sadece takın ve gelen silebilirsiniz
Ön veya bağlı üst

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

217
00:10:26,320 --> 00:10:28,028
Bu gerçekten sadece var
Fark olsa.

218
00:10:28,028 --> 00:10:29,700
Bu başka türlü bir tek başına bağlantılı listesidir.

219
00:10:29,700 --> 00:10:32,060
Bu tek sınırlama, bu
Kendimize değiştirilmesi

220
00:10:32,060 --> 00:10:35,770
programcılar olarak bu
bir yığın haline dönüşür.

221
00:10:35,770 --> 00:10:39,280
>> Burada kural her zaman bir muhafaza etmektir
Bir bağlantılı liste başına işaretçisi.

222
00:10:39,280 --> 00:10:41,520
Bu tabii bir genellikle
ilk önemli kural.

223
00:10:41,520 --> 00:10:44,260
Tek başına size liste zaten bağlanmış İçin
Sadece kafasına bir işaretçi gerek

224
00:10:44,260 --> 00:10:46,160
Bu sahip olmak için
Zincir başvurmak mümkün

225
00:10:46,160 --> 00:10:48,596
Her diğer elemana
bağlantılı liste.

226
00:10:48,596 --> 00:10:50,470
Ama özellikle iyi
Bir yığın önemli.

227
00:10:50,470 --> 00:10:52,386
Ve böylece genellikle sen
Aslında istediğiniz olacak

228
00:10:52,386 --> 00:10:54,090
Bu işaretçi küresel değişken olduğu.

229
00:10:54,090 --> 00:10:56,574
Muhtemelen gidiyor
daha kolay bu şekilde olacak.

230
00:10:56,574 --> 00:10:58,240
Yani itme ve pop analogları nelerdir?

231
00:10:58,240 --> 00:10:58,740
Sağ.

232
00:10:58,740 --> 00:11:01,812
Yani yine bastırıyor ekliyor
yığına yeni bir unsur.

233
00:11:01,812 --> 00:11:03,770
Bağlantılı bir listede olduğunu
biz gidiyoruz demektir

234
00:11:03,770 --> 00:11:07,770
Biz konum yeni bir düğüm oluşturmak için
Bağlantılı liste halinde eklemek için gidiyoruz,

235
00:11:07,770 --> 00:11:10,500
ve daha sonra dikkatli adımları izleyin
Daha önce açıkladık olduğunu

236
00:11:10,500 --> 00:11:16,050
tek başına bağlantılı listeler bunu eklemek
zincir kırılmadan zincir

237
00:11:16,050 --> 00:11:18,900
ve kaybetme ya da herhangi bir orphaning
bağlantılı liste elemanları.

238
00:11:18,900 --> 00:11:21,820
Ve bu temelde ne anlama var
Metnin küçük blob var özetlemektedir.

239
00:11:21,820 --> 00:11:23,740
Ve en bir göz atalım
Bir diyagram olarak en.

240
00:11:23,740 --> 00:11:24,823
>> Yani burada bizim bağlantılı liste var.

241
00:11:24,823 --> 00:11:26,620
Bu aynı anda dört element içerir.

242
00:11:26,620 --> 00:11:30,420
Ve daha mükemmel burada var
Dört unsuru içeren yığın.

243
00:11:30,420 --> 00:11:36,030
Ve en şimdi istiyoruz diyelim
Bu yığına yeni bir öğe itin.

244
00:11:36,030 --> 00:11:39,792
Ve biz yeni itmek istiyor
kimin veri değeri öğesi 12'dir.

245
00:11:39,792 --> 00:11:41,000
Peki biz yapacağız ne?

246
00:11:41,000 --> 00:11:43,420
Peki ilk biz gidiyoruz
dinamik malloc alanı,

247
00:11:43,420 --> 00:11:45,411
yeni bir düğüm için yer tahsis eder.

248
00:11:45,411 --> 00:11:48,160
Ve tabii ki hemen sonra
biz her zaman biz malloc arama yapmak

249
00:11:48,160 --> 00:11:52,989
null kontrol etmek için emin olun
biz geri boş var çünkü eğer

250
00:11:52,989 --> 00:11:54,280
sorun bir çeşit oldu.

251
00:11:54,280 --> 00:11:57,570
Biz boş inceleyebilirsiniz istemiyorum
işaretçi veya bir seg hatası yaşayacaktır.

252
00:11:57,570 --> 00:11:58,510
Bu iyi değil.

253
00:11:58,510 --> 00:11:59,760
Bu yüzden düğümün malloced ettik.

254
00:11:59,760 --> 00:12:01,260
Biz burada başarı elde ettik kabul edeceğiz.

255
00:12:01,260 --> 00:12:06,090
Biz içine 12 koymak için gidiyoruz
Bu düğümün veri alanı.

256
00:12:06,090 --> 00:12:11,570
Şimdi hatırlamak yapmak bizim işaretçileri olan
bu yüzden zinciri kırmak istemem sonraki hamle?

257
00:12:11,570 --> 00:12:15,100
Burada birkaç seçenek var ama
Güvenli olacak tek

258
00:12:15,100 --> 00:12:19,330
işaretçi yanındaki haber ayarlamak için
Listenin eski başkanı gelin

259
00:12:19,330 --> 00:12:21,360
ya da yakında ne olacağını
Listenin eski başkanı.

260
00:12:21,360 --> 00:12:23,610
Ve şimdi tüm bu bizim
elemanları bir araya zincirleme,

261
00:12:23,610 --> 00:12:27,370
biz sadece işaret listesini taşıyabilirsiniz
Yeni yapar aynı yere.

262
00:12:27,370 --> 00:12:33,550
Ve biz şimdi etkili itti bir
yığının önünde üzerine yeni bir eleman.

263
00:12:33,550 --> 00:12:36,420
>> Biz pop sadece istiyorum
ilk elemanı silin.

264
00:12:36,420 --> 00:12:38,150
Ve böylece temelde ne
Biz burada yapmak zorunda

265
00:12:38,150 --> 00:12:40,050
iyi ikinci eleman bulmak zorundayız.

266
00:12:40,050 --> 00:12:43,540
Sonunda yeni olacak
Biz ilkini sildikten sonra baş.

267
00:12:43,540 --> 00:12:47,300
Yani biz sadece başlamak gerekir
başında, tek ileri hareket ettirin.

268
00:12:47,300 --> 00:12:50,340
Biz bir bir tutun var sonra
nerede biz ileri halen

269
00:12:50,340 --> 00:12:53,850
biz güvenle ilkini silebilirsiniz vardır
ve o zaman biz sadece baş taşıyabilirsiniz

270
00:12:53,850 --> 00:12:57,150
ne işaret etmek
Şimdi ikinci dönem ve

271
00:12:57,150 --> 00:12:59,170
Bundan sonra ilk
düğüm silindi.

272
00:12:59,170 --> 00:13:01,160
>> Yani yine bir göz alarak
ona bir diyagram olarak biz

273
00:13:01,160 --> 00:13:05,022
Şimdi bir pop istiyorum
Bu yığının kapalı öğesi.

274
00:13:05,022 --> 00:13:05,730
Peki ne yapacağız?

275
00:13:05,730 --> 00:13:08,188
Peki biz ilk oluşturmak için gidiyoruz
gidiyor, yeni bir işaretçi

276
00:13:08,188 --> 00:13:10,940
başkanı olarak aynı noktaya işaret etmek.

277
00:13:10,940 --> 00:13:13,790
Biz bunu bir konum taşımak için gidiyoruz
ileri trav eşittir diyerek

278
00:13:13,790 --> 00:13:17,510
örneğin, aşağıdaki trav hangi
trav işaretçi bir ilerleme olur

279
00:13:17,510 --> 00:13:19,324
forward pozisyonu.

280
00:13:19,324 --> 00:13:21,240
Şimdi elimizdeki bir
İlk öğe üzerinde tutun

281
00:13:21,240 --> 00:13:24,573
işaretçi olarak adlandırılan listede ve içinden
denilen bir işaretçi üzerinden ikinci unsur

282
00:13:24,573 --> 00:13:28,692
trav, biz güvenle o silebilirsiniz
yığının ilk elemanı

283
00:13:28,692 --> 00:13:30,650
dinlenme kaybetmeden
Zincirin çünkü biz

284
00:13:30,650 --> 00:13:32,358
başvurmak için bir yol var
ikinci elemana

285
00:13:32,358 --> 00:13:34,780
yoluyla ileri
pointer trav çağırdı.

286
00:13:34,780 --> 00:13:37,100
>> Yani şimdi bu düğümü ücretsiz yapabilirsiniz.

287
00:13:37,100 --> 00:13:38,404
Biz Listeyi ücretsiz yapabilirsiniz.

288
00:13:38,404 --> 00:13:41,320
Ve sonra biz şimdi yapmamız gereken tek şey
aynı yerde noktaya taşımak Listeyi

289
00:13:41,320 --> 00:13:44,482
Bu trav yapar ve biz geri çeşit konum
Biz 12 itti önce başladığımız yere

290
00:13:44,482 --> 00:13:45,690
ilk etapta üzerine doğru.

291
00:13:45,690 --> 00:13:46,940
Nerede kalmıştık bu tam olarak budur.

292
00:13:46,940 --> 00:13:48,840
Bu dört elemanlı bir yığını vardı.

293
00:13:48,840 --> 00:13:49,690
Biz beşinci ekledi.

294
00:13:49,690 --> 00:13:51,910
Biz beşinci itti
elemanı üzerine, sonra

295
00:13:51,910 --> 00:13:55,980
attı en güncel olanı
geri çekil elemanı ekledi.

296
00:13:55,980 --> 00:13:58,816
>> Bu hemen hemen gerçekten
tüm yığınlarının orada.

297
00:13:58,816 --> 00:14:00,190
Sen diziler olarak uygulayabilirsiniz.

298
00:14:00,190 --> 00:14:01,815
Sen bağlantılı listeler olarak uygulayabilirsiniz.

299
00:14:01,815 --> 00:14:04,810
Diğer, tabii ki, daha vardır
yolları da bunları uygulamak için.

300
00:14:04,810 --> 00:14:09,060
Biz kullanmak istiyorsunuz Temelde nedeni
yığınları şekilde verileri korumak için

301
00:14:09,060 --> 00:14:12,090
en son eklenen bu
eleman we 'ilk şey

302
00:14:12,090 --> 00:14:14,980
geri almak isteyecektir.

303
00:14:14,980 --> 00:14:17,900
Ben Doug Lloyd değilim, bu CS50 olduğunu.

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