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

2
00:00:04,074 --> 00:00:05,990
DOUG LLOYD: Baiklah,
supaya oleh titik ini anda

3
00:00:05,990 --> 00:00:09,020
mungkin cukup biasa
dengan pameran dan senarai berkaitan

4
00:00:09,020 --> 00:00:10,950
yang manakah utama kedua-dua
struktur data yang kita ada

5
00:00:10,950 --> 00:00:16,810
bercakap tentang untuk menyimpan set
data jenis data yang sama yang dianjurkan.

6
00:00:16,810 --> 00:00:19,080
>> Sekarang kita akan bercakap
kira-kira beberapa variasi

7
00:00:19,080 --> 00:00:20,330
pada tatasusunan dan senarai berkaitan.

8
00:00:20,330 --> 00:00:22,362
Dalam video ini kita akan
untuk bercakap mengenai susunan.

9
00:00:22,362 --> 00:00:25,320
Secara khusus kita akan bercakap
mengenai struktur data dipanggil timbunan.

10
00:00:25,320 --> 00:00:28,510
Ingat dari perbincangan sebelum
tentang petunjuk dan ingatan,

11
00:00:28,510 --> 00:00:32,060
bahawa timbunan juga
menamakan untuk segmen memori

12
00:00:32,060 --> 00:00:34,980
mana statik diisytiharkan
memori memory-- anda

13
00:00:34,980 --> 00:00:38,730
nama, pembolehubah yang anda namakan, et
sebagainya dan fungsi bingkai yang kita juga

14
00:00:38,730 --> 00:00:41,000
bingkai tindanan panggilan wujud.

15
00:00:41,000 --> 00:00:45,421
Jadi ini adalah satu struktur data stack
bukan segmen timbunan ingatan.

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

17
00:00:45,920 --> 00:00:46,890
>> Tetapi apa yang timbunan?

18
00:00:46,890 --> 00:00:49,220
Jadi ia adalah cukup banyak hanya
sejenis khas struktur

19
00:00:49,220 --> 00:00:51,190
yang mengekalkan data dalam cara yang dianjurkan.

20
00:00:51,190 --> 00:00:53,760
Dan ada dua sangat
cara yang biasa untuk melaksanakan

21
00:00:53,760 --> 00:00:57,380
susunan menggunakan dua struktur data
yang kita sudah biasa dengan,

22
00:00:57,380 --> 00:01:00,340
tatasusunan dan senarai berkaitan.

23
00:01:00,340 --> 00:01:04,430
Apa yang membuatkan khas timbunan adalah
cara di mana kita meletakkan maklumat

24
00:01:04,430 --> 00:01:08,200
ke dalam timbunan, dan cara kita
mengeluarkan maklumat dari timbunan.

25
00:01:08,200 --> 00:01:11,600
Khususnya dengan susunan
peraturan adalah hanya yang paling

26
00:01:11,600 --> 00:01:15,830
baru-baru ini menambah unsur boleh dikeluarkan.

27
00:01:15,830 --> 00:01:17,660
>> Jadi berfikir tentang hal itu seolah-olah ia adalah timbunan.

28
00:01:17,660 --> 00:01:21,170
Kami cerucuk maklumat
di atas dengan sendirinya,

29
00:01:21,170 --> 00:01:24,271
dan hanya perkara yang di atas
longgokan boleh dikeluarkan.

30
00:01:24,271 --> 00:01:27,020
Kita tidak boleh mengeluarkan perkara yang di bawah
kerana segala-galanya akan

31
00:01:27,020 --> 00:01:28,020
runtuh dan goyang.

32
00:01:28,020 --> 00:01:32,580
Oleh itu, kita benar-benar sedang membina timbunan yang
kita kemudian perlu mengeluarkan sekeping oleh sekeping.

33
00:01:32,580 --> 00:01:36,590
Oleh kerana itu kita biasa merujuk
kepada timbunan sebagai struktur LIFO,

34
00:01:36,590 --> 00:01:38,940
bertahan dalam, dahulu.

35
00:01:38,940 --> 00:01:42,290
LIFO, bertahan, keluar dahulu.

36
00:01:42,290 --> 00:01:45,635
>> Demikian kerana sekatan ini di
bagaimana maklumat boleh ditambah kepada

37
00:01:45,635 --> 00:01:49,080
dan dikeluarkan daripada timbunan, ada benar-benar
hanya dua perkara yang boleh kita lakukan dengan timbunan.

38
00:01:49,080 --> 00:01:52,010
Kami boleh menolak, yang merupakan
jangka kita gunakan untuk menambah

39
00:01:52,010 --> 00:01:55,130
elemen baru ke bahagian atas
timbunan, atau jika timbunan tidak wujud

40
00:01:55,130 --> 00:01:58,550
dan kami membuatnya dari awal,
mewujudkan timbunan di tempat pertama

41
00:01:58,550 --> 00:02:00,110
akan menolak.

42
00:02:00,110 --> 00:02:04,990
Dan kemudian pop, itu jenis CS
jangka yang kami gunakan untuk membuang yang paling baru

43
00:02:04,990 --> 00:02:08,330
elemen ditambah dari bahagian atas timbunan.

44
00:02:08,330 --> 00:02:11,130
>> Jadi, kita akan melihat kepada kedua-dua
pelaksanaan, kedua-dua lokasi berdasarkan

45
00:02:11,130 --> 00:02:13,120
dan senarai dikaitkan berasaskan.

46
00:02:13,120 --> 00:02:14,870
Dan kita akan
mulakan dengan lokasi berasaskan.

47
00:02:14,870 --> 00:02:19,990
Jadi di sini adalah idea asas apa
struktur data tindanan pelbagai berdasarkan

48
00:02:19,990 --> 00:02:21,140
akan kelihatan seperti.

49
00:02:21,140 --> 00:02:23,740
Kami mempunyai definisi ditaip di sini.

50
00:02:23,740 --> 00:02:27,790
Di dalam yang kita ada dua orang ahli
atau medan struktur.

51
00:02:27,790 --> 00:02:29,880
Kami mempunyai array.

52
00:02:29,880 --> 00:02:32,400
Dan sekali lagi saya menggunakan
sewenang-wenangnya Nilai jenis data.

53
00:02:32,400 --> 00:02:35,180
>> Jadi ini boleh menjadi apa-apa jenis data,
int char atau beberapa data lain

54
00:02:35,180 --> 00:02:37,080
jenis yang anda dibuat sebelum ini.

55
00:02:37,080 --> 00:02:39,861
Oleh itu, kita mempunyai pelbagai kapasiti saiz.

56
00:02:39,861 --> 00:02:44,010
Kapasiti sedang paun ditakrifkan berterusan,
mungkin di tempat lain dalam fail kami.

57
00:02:44,010 --> 00:02:47,550
Jadi notis sudah dengan khusus ini
pelaksanaan kita bounding

58
00:02:47,550 --> 00:02:49,800
diri kita sendiri seperti yang biasanya
kes dengan array,

59
00:02:49,800 --> 00:02:53,170
yang kita tidak boleh secara dinamik mengubah saiz,
di mana ada sebilangan

60
00:02:53,170 --> 00:02:55,450
unsur-unsur maksimum yang
kita boleh dimasukkan ke dalam timbunan kami.

61
00:02:55,450 --> 00:02:57,930
Dalam kes ini ia adalah elemen keupayaan.

62
00:02:57,930 --> 00:03:00,310
>> Kami juga mengesan
bahagian atas timbunan.

63
00:03:00,310 --> 00:03:04,350
Apa unsur adalah yang paling
Baru-baru ini ditambah kepada timbunan?

64
00:03:04,350 --> 00:03:07,470
Dan dengan itu kita mengesan bahawa
dalam bahagian pembolehubah dipanggil.

65
00:03:07,470 --> 00:03:11,692
Dan semua ini mendapat dibungkus bersama-sama
ke dalam jenis data baru yang dikenali sebagai timbunan.

66
00:03:11,692 --> 00:03:13,400
Dan sekali kita dicipta
jenis data baru ini

67
00:03:13,400 --> 00:03:15,410
kita boleh memperlakukannya seperti
apa-apa jenis data yang lain.

68
00:03:15,410 --> 00:03:20,970
Kita boleh mengisytiharkan timbunan s, sama seperti
kita boleh melakukan int x, atau char y.

69
00:03:20,970 --> 00:03:22,990
Dan apabila kita katakan timbunan
s, juga apa yang berlaku

70
00:03:22,990 --> 00:03:26,420
adalah kita akan mendapat satu set
memori yang diperuntukkan untuk kita.

71
00:03:26,420 --> 00:03:28,770
>> Dalam kapasiti kes ini
Saya telah nampaknya telah memilih

72
00:03:28,770 --> 00:03:33,470
adalah 10 kerana saya telah mendapat satu
pembolehubah tunggal jenis timbunan

73
00:03:33,470 --> 00:03:35,320
yang mengandungi dua medan ingat.

74
00:03:35,320 --> 00:03:38,330
Pelbagai, dalam kes ini akan
menjadi pelbagai integer

75
00:03:38,330 --> 00:03:40,440
seperti yang berlaku di kebanyakan contoh saya.

76
00:03:40,440 --> 00:03:43,996
Dan satu lagi pembolehubah integer
mampu menyimpan bahagian atas,

77
00:03:43,996 --> 00:03:45,870
yang paling baru ditambah
elemen untuk timbunan.

78
00:03:45,870 --> 00:03:50,290
Jadi, satu timbunan tunggal daripada apa yang kita
hanya ditakrifkan kelihatan seperti ini.

79
00:03:50,290 --> 00:03:53,190
Ia adalah sebuah kotak yang mengandungi
pelbagai 10 apa

80
00:03:53,190 --> 00:03:57,280
akan menjadi bilangan bulat dalam kes ini dan
satu lagi pembolehubah integer terdapat dalam hijau

81
00:03:57,280 --> 00:04:00,010
untuk menunjukkan bahagian atas timbunan.

82
00:04:00,010 --> 00:04:02,600
>> Untuk menetapkan bahagian atas
timbunan kita hanya mengatakan s.top.

83
00:04:02,600 --> 00:04:04,890
Itulah bagaimana kita mengakses
bidang penarikan balik struktur.

84
00:04:04,890 --> 00:04:10,460
s.top sama dengan 0 berkesan
melakukan ini untuk timbunan kami.

85
00:04:10,460 --> 00:04:12,960
Jadi sekali lagi kita mempunyai dua operasi
yang kita boleh lakukan sekarang.

86
00:04:12,960 --> 00:04:14,270
Kami boleh menolak dan kita boleh pop.

87
00:04:14,270 --> 00:04:15,635
Mari kita mulakan dengan push.

88
00:04:15,635 --> 00:04:18,260
Sekali lagi, menolak adalah menambah yang baru
elemen ke atas timbunan.

89
00:04:18,260 --> 00:04:21,460
>> Jadi apa yang perlu kita lakukan dalam
pelbagai ini pelaksanaan berasaskan?

90
00:04:21,460 --> 00:04:23,210
Baik dalam umum
fungsi push akan

91
00:04:23,210 --> 00:04:26,160
untuk perlu menerima
penunjuk kepada timbunan.

92
00:04:26,160 --> 00:04:28,610
Oleh sebab itu, kedua dan berfikir mengenainya.

93
00:04:28,610 --> 00:04:32,840
Mengapa kita akan mahu menerima
penunjuk kepada tindanan?

94
00:04:32,840 --> 00:04:36,830
Balik dari video sebelumnya
skop pembolehubah dan petunjuk,

95
00:04:36,830 --> 00:04:42,350
apa yang akan berlaku jika kita hanya menghantar
timbunan, s sebaliknya dalam sebagai parameter?

96
00:04:42,350 --> 00:04:45,770
Apa yang sebenarnya akan diluluskan di sana?

97
00:04:45,770 --> 00:04:49,430
Ingat kami mewujudkan satu salinan
apabila kita lulus ke fungsi

98
00:04:49,430 --> 00:04:51,160
kecuali kita menggunakan petunjuk.

99
00:04:51,160 --> 00:04:55,380
Dan supaya fungsi ini menolak keperluan
untuk menerima penunjuk kepada timbunan

100
00:04:55,380 --> 00:04:59,160
supaya kita benar-benar ingin berubah
timbunan kami berhasrat untuk berubah.

101
00:04:59,160 --> 00:05:03,060
>> Perkara push lain mungkin mahu
terima ialah elemen data nilai jenis.

102
00:05:03,060 --> 00:05:06,970
Dalam kes ini, sekali lagi, integer yang
kita akan menambah bahagian atas timbunan.

103
00:05:06,970 --> 00:05:08,680
Jadi kami mempunyai dua parameter kami.

104
00:05:08,680 --> 00:05:11,310
Apa yang kita akan
sekarang lakukan dalam tolak?

105
00:05:11,310 --> 00:05:14,860
Nah, hanya, kami hanya akan menambah
bahawa elemen ke atas timbunan

106
00:05:14,860 --> 00:05:22,860
dan kemudian menukar mana bahagian atas
tindanan adalah, bahawa s dot nilai tertinggi.

107
00:05:22,860 --> 00:05:25,639
Jadi ini adalah apa fungsi
pengisytiharan untuk menolak

108
00:05:25,639 --> 00:05:27,680
mungkin kelihatan seperti dalam
berdasarkan pelbagai pelaksanaan.

109
00:05:27,680 --> 00:05:30,967
>> Sekali lagi ia tidak peraturan keras dan cepat
bahawa anda boleh menukar ini dan mempunyai

110
00:05:30,967 --> 00:05:32,050
ia berbeza dalam cara yang berbeza.

111
00:05:32,050 --> 00:05:33,840
Mungkin s diisytiharkan di peringkat global.

112
00:05:33,840 --> 00:05:36,180
Dan supaya anda tidak perlu
untuk lulus ia adalah sebagai parameter.

113
00:05:36,180 --> 00:05:39,125
Ini sekali lagi hanya
kes umum untuk menolak.

114
00:05:39,125 --> 00:05:41,000
Dan ada yang berbeza
cara-cara untuk melaksanakannya.

115
00:05:41,000 --> 00:05:42,810
Tetapi dalam kes ini kami
push akan mengambil

116
00:05:42,810 --> 00:05:48,540
dua hujah, penunjuk kepada timbunan dan
elemen data nilai jenis, integer

117
00:05:48,540 --> 00:05:49,840
dalam kes ini.

118
00:05:49,840 --> 00:05:52,100
>> Oleh itu, kita mengisytiharkan s, kita
berkata s.top sama dengan 0.

119
00:05:52,100 --> 00:05:55,969
Sekarang mari kita menolak
nombor 28 ke dalam tindanan.

120
00:05:55,969 --> 00:05:57,010
Baik apa maksudnya?

121
00:05:57,010 --> 00:05:59,600
Baik pada masa ini
atas timbunan adalah 0.

122
00:05:59,600 --> 00:06:01,350
Dan supaya apa yang pada dasarnya
akan berlaku adalah

123
00:06:01,350 --> 00:06:05,820
kita akan melekat jumlah
28 ke dalam pelbagai lokasi 0.

124
00:06:05,820 --> 00:06:09,540
Cukup mudah, betul, bahawa
adalah bahagian atas dan sekarang kita baik untuk pergi.

125
00:06:09,540 --> 00:06:12,910
Dan maka kita perlu mengubah apa yang
bahagian atas timbunan akan.

126
00:06:12,910 --> 00:06:15,130
Supaya masa akan datang
kita menolak unsur dalam,

127
00:06:15,130 --> 00:06:18,017
kita akan menyimpannya di
lokasi mudah, mungkin tidak 0.

128
00:06:18,017 --> 00:06:20,100
Kami tidak mahu menulis ganti
apa yang kita hanya meletakkan di sana.

129
00:06:20,100 --> 00:06:23,510
Dan dengan itu kita hanya akan bergerak bahagian atas untuk 1.

130
00:06:23,510 --> 00:06:24,890
Yang mungkin masuk akal.

131
00:06:24,890 --> 00:06:28,940
>> Sekarang jika kita mahu meletakkan elemen lain
ke dalam tindanan, mengatakan bahawa kita mahu untuk menolak 33,

132
00:06:28,940 --> 00:06:33,190
baik sekarang kami hanya akan mengambil 33
dan meletakkannya di nombor lokasi mudah

133
00:06:33,190 --> 00:06:37,580
1, dan kemudian menukar bahagian atas kami
stack menjadi array beberapa lokasi dua.

134
00:06:37,580 --> 00:06:40,650
Jadi, jika pada masa akan datang kita mahu
menolak unsur ke dalam tindanan,

135
00:06:40,650 --> 00:06:43,087
ia akan dimasukkan ke dalam pelbagai lokasi 2.

136
00:06:43,087 --> 00:06:44,420
Dan mari kita buat satu masa yang lanjut.

137
00:06:44,420 --> 00:06:45,753
Kami akan menolak 19 off dari susunan.

138
00:06:45,753 --> 00:06:48,940
Kami akan meletakkan 19 dalam pelbagai lokasi 2
dan menukar bahagian atas timbunan kami

139
00:06:48,940 --> 00:06:51,220
menjadi lokasi mudah 3
jadi jika kali kita seterusnya

140
00:06:51,220 --> 00:06:54,780
perlu membuat push kita baik untuk pergi.

141
00:06:54,780 --> 00:06:56,980
>> OK, jadi yang yang menolak secara ringkas.

142
00:06:56,980 --> 00:06:57,830
Bagaimana pula muncul?

143
00:06:57,830 --> 00:07:00,240
Jadi pop adalah jenis
rakan untuk menolak.

144
00:07:00,240 --> 00:07:02,720
Ia adalah bagaimana kita mengeluarkan data dari timbunan.

145
00:07:02,720 --> 00:07:04,610
Dan dalam keperluan pop umum
untuk melakukan yang berikut.

146
00:07:04,610 --> 00:07:07,600
Ia perlu menerima penunjuk kepada
timbunan, sekali lagi dalam kes umum.

147
00:07:07,600 --> 00:07:10,480
Dalam beberapa kes lain yang anda mungkin
telah mengisytiharkan timbunan di peringkat global,

148
00:07:10,480 --> 00:07:13,910
di mana anda tidak perlu untuk lulus
kerana ia telah mempunyai akses kepada maklumat itu

149
00:07:13,910 --> 00:07:15,541
sebagai pembolehubah global.

150
00:07:15,541 --> 00:07:17,040
Tetapi apa lagi yang perlu kita lakukan?

151
00:07:17,040 --> 00:07:21,000
Baik kita menokok
bahagian atas timbunan di tolak,

152
00:07:21,000 --> 00:07:24,050
jadi kita mungkin akan mahu
untuk susutan bahagian atas timbunan

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

154
00:07:25,009 --> 00:07:26,800
Dan kemudian tentu
kami juga akan mahu

155
00:07:26,800 --> 00:07:29,240
untuk mengembalikan nilai yang kita keluarkan.

156
00:07:29,240 --> 00:07:32,125
Jika kita menambah unsur-unsur, kita mahu
untuk mendapatkan unsur-unsur di kemudian hari,

157
00:07:32,125 --> 00:07:34,000
kita mungkin sebenarnya
mahu menyimpan mereka, maka Kami

158
00:07:34,000 --> 00:07:36,490
jangan hanya memadam mereka dari
stack dan kemudian berbuat apa-apa dengan mereka.

159
00:07:36,490 --> 00:07:38,500
Secara umumnya jika kita
menolak dan muncul di sini

160
00:07:38,500 --> 00:07:41,250
kami ingin menyimpan ini
maklumat dengan cara yang bermakna

161
00:07:41,250 --> 00:07:43,250
dan supaya ia tidak membuat
masuk akal untuk hanya membuangnya.

162
00:07:43,250 --> 00:07:46,380
Jadi fungsi ini perlu
mungkin mengembalikan nilai kepada kami.

163
00:07:46,380 --> 00:07:51,040
>> Jadi ini adalah apa deklarasi untuk pop
mungkin kelihatan seperti terdapat di sebelah kiri atas.

164
00:07:51,040 --> 00:07:53,870
Fungsi ini pulangan
data nilai jenis.

165
00:07:53,870 --> 00:07:56,320
Sekali lagi kita telah menggunakan
bilangan bulat di seluruh.

166
00:07:56,320 --> 00:08:01,916
Dan ia menerima penunjuk kepada timbunan sebagai
hujah bicaranya atau parameter tunggal.

167
00:08:01,916 --> 00:08:03,040
Jadi apa yang pop akan lakukan?

168
00:08:03,040 --> 00:08:07,990
Katakan kita mahu sekarang
pop unsur luar s.

169
00:08:07,990 --> 00:08:14,000
Jadi ingat saya berkata bahawa susunan yang terakhir
, keluar dahulu, LIFO data struktur.

170
00:08:14,000 --> 00:08:17,855
Unsur yang akan
dikeluarkan daripada timbunan?

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

172
00:08:21,780 --> 00:08:24,150
Adakah anda rasa 19?

173
00:08:24,150 --> 00:08:25,290
Kerana anda akan menjadi betul.

174
00:08:25,290 --> 00:08:28,836
19 adalah elemen terakhir kami menambah kepada
stack apabila kita telah menolak unsur-unsur di atas,

175
00:08:28,836 --> 00:08:31,210
dan sebagainya ia akan yang pertama
elemen yang akan dikeluarkan.

176
00:08:31,210 --> 00:08:34,780
Ia seolah-olah kita berkata 28, dan
kemudian kita meletakkan 33 di atas itu,

177
00:08:34,780 --> 00:08:36,659
dan kami meletakkan 19 di atas itu.

178
00:08:36,659 --> 00:08:40,650
Satu-satunya elemen yang boleh kita ambil kira ialah 19.

179
00:08:40,650 --> 00:08:45,019
>> Sekarang dalam rajah di sini apa yang saya lakukan
umpama dipadam 19 dari array.

180
00:08:45,019 --> 00:08:46,810
Bukan itu sebenarnya
apa yang kita akan lakukan.

181
00:08:46,810 --> 00:08:48,934
Kami hanya akan jenis
daripada berpura-pura ia tidak ada.

182
00:08:48,934 --> 00:08:51,441
Ia masih terdapat dalam
bahawa lokasi memori,

183
00:08:51,441 --> 00:08:54,190
tetapi kami hanya akan mengabaikannya
dengan menukar bahagian atas timbunan kami

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

185
00:08:56,080 --> 00:08:58,720
Jadi jika kita kini menolak
unsur lain ke dalam tindanan,

186
00:08:58,720 --> 00:09:00,720
ia lebih akan menulis 19.

187
00:09:00,720 --> 00:09:03,990
>> Tetapi jangan kita pergi melalui masalah
untuk memotong 19 dari timbunan.

188
00:09:03,990 --> 00:09:05,830
Kami hanya boleh berpura-pura ia tidak ada.

189
00:09:05,830 --> 00:09:11,107
Untuk tujuan timbunan ia pergi jika
kita menukar bahagian atas untuk menjadi 2 bukan 3.

190
00:09:11,107 --> 00:09:12,690
Baiklah, jadi yang cukup banyak ia.

191
00:09:12,690 --> 00:09:15,080
Itu sahaja yang perlu kita lakukan
pop unsur luar.

192
00:09:15,080 --> 00:09:16,090
Mari kita buat sekali lagi.

193
00:09:16,090 --> 00:09:18,610
Jadi saya telah menekankan dalam merah di sini untuk
menunjukkan kami membuat panggilan lain.

194
00:09:18,610 --> 00:09:19,720
Kami akan melakukan perkara yang sama.

195
00:09:19,720 --> 00:09:20,803
>> Jadi apa yang akan berlaku?

196
00:09:20,803 --> 00:09:23,670
Nah, kita akan menyimpan
33 dalam x dan kita akan

197
00:09:23,670 --> 00:09:26,217
untuk menukar bahagian atas timbunan untuk 1.

198
00:09:26,217 --> 00:09:29,050
Supaya jika kita sekarang untuk menolak satu
elemen ke dalam timbunan yang kami

199
00:09:29,050 --> 00:09:31,610
nak buat sekarang,
apa yang akan berlaku

200
00:09:31,610 --> 00:09:36,367
adalah kita akan menulis ganti
pelbagai nombor lokasi 1.

201
00:09:36,367 --> 00:09:38,950
Supaya 33 yang semacam dibiarkan
belakang yang kita hanya berpura-pura

202
00:09:38,950 --> 00:09:44,390
tidak ada lagi, kami hanya akan
untuk memukul berkali-kali dan meletakkan 40 sana.

203
00:09:44,390 --> 00:09:46,290
Kemudian sudah tentu,
sejak kami membuat tolakan,

204
00:09:46,290 --> 00:09:48,780
kita akan kenaikan yang
atas tindanan 1-2

205
00:09:48,780 --> 00:09:50,950
supaya jika kita menambah
elemen lain IA AKAN

206
00:09:50,950 --> 00:09:54,700
pergi ke dalam pelbagai lokasi nombor dua.

207
00:09:54,700 --> 00:09:57,590
>> Sekarang senarai berkaitan adalah satu lagi
cara untuk melaksanakan susunan.

208
00:09:57,590 --> 00:10:01,210
Dan jika definisi ini ke atas
skrin di sini kelihatan biasa kepada anda,

209
00:10:01,210 --> 00:10:04,260
ia adalah kerana ia kelihatan hampir
betul-betul sama, sebenarnya,

210
00:10:04,260 --> 00:10:07,790
ia cukup banyak betul-betul
sama sebagai satu senarai secara tunggal berkaitan,

211
00:10:07,790 --> 00:10:11,990
jika anda ingat dari perbincangan kita tentang
secara tunggal dikaitkan senarai dalam video lain.

212
00:10:11,990 --> 00:10:15,510
Satu-satunya sekatan di sini
adalah untuk kita sebagai pengaturcara,

213
00:10:15,510 --> 00:10:17,900
kami tidak dibenarkan
memasukkan atau memadam secara rawak

214
00:10:17,900 --> 00:10:20,620
dari senarai secara tunggal dikaitkan
mana kita sebelum ini boleh lakukan.

215
00:10:20,620 --> 00:10:25,820
Hanya sekarang kita boleh memasukkan dan memotong daripada
depan atau bahagian atas berkaitan

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

217
00:10:26,320 --> 00:10:28,028
Itu benar-benar satu-satunya
perbezaan walaupun.

218
00:10:28,028 --> 00:10:29,700
Ini adalah sebaliknya senarai secara tunggal berkaitan.

219
00:10:29,700 --> 00:10:32,060
Ia hanya sekatan
menggantikan pada diri kita sendiri

220
00:10:32,060 --> 00:10:35,770
sebagai pengaturcara yang
perubahan ke dalam timbunan.

221
00:10:35,770 --> 00:10:39,280
>> Peraturan di sini adalah untuk sentiasa mengekalkan
penunjuk kepada ketua senarai berpaut.

222
00:10:39,280 --> 00:10:41,520
Ini sudah tentu yang secara umumnya
peraturan penting pertama.

223
00:10:41,520 --> 00:10:44,260
Untuk senarai secara tunggal dikaitkan bagaimanapun anda
hanya perlu penunjuk kepada kepala

224
00:10:44,260 --> 00:10:46,160
untuk mempunyai yang
rantaian dapat merujuk

225
00:10:46,160 --> 00:10:48,596
kepada setiap elemen lain
dalam senarai yang dipautkan.

226
00:10:48,596 --> 00:10:50,470
Tetapi ia adalah terutamanya
penting dengan timbunan.

227
00:10:50,470 --> 00:10:52,386
Dan jadi secara amnya anda
akan benar-benar mahu

228
00:10:52,386 --> 00:10:54,090
penunjuk ini menjadi berubah-ubah global.

229
00:10:54,090 --> 00:10:56,574
Ia mungkin akan
menjadi lebih mudah dengan cara itu.

230
00:10:56,574 --> 00:10:58,240
Jadi apakah analog tolak dan pop?

231
00:10:58,240 --> 00:10:58,740
Betul.

232
00:10:58,740 --> 00:11:01,812
Jadi menolak lagi menambah
elemen baru ke dalam tindanan.

233
00:11:01,812 --> 00:11:03,770
Dalam senarai berpaut yang
bermakna kita akan mempunyai

234
00:11:03,770 --> 00:11:07,770
untuk mewujudkan nod baru bahawa kita
akan menambah ke dalam senarai berkaitan,

235
00:11:07,770 --> 00:11:10,500
dan kemudian ikuti langkah-langkah berhati-hati
yang kami telah menjelaskan sebelum ini

236
00:11:10,500 --> 00:11:16,050
dalam senarai secara tunggal dikaitkan dengan menambah kepada
rantaian tanpa melanggar rantai

237
00:11:16,050 --> 00:11:18,900
dan kehilangan atau anak yatim-mana
unsur-unsur senarai berkaitan.

238
00:11:18,900 --> 00:11:21,820
Dan itu pada dasarnya apa yang
sedikit tompok teks terdapat meringkaskan.

239
00:11:21,820 --> 00:11:23,740
Dan mari kita lihat
ia sebagai gambar rajah.

240
00:11:23,740 --> 00:11:24,823
>> Jadi di sini adalah senarai berpaut kami.

241
00:11:24,823 --> 00:11:26,620
Ia serentak mengandungi empat elemen.

242
00:11:26,620 --> 00:11:30,420
Dan yang lebih sempurna di sini adalah kami
timbunan yang mengandungi empat elemen.

243
00:11:30,420 --> 00:11:36,030
Dan mari kita mengatakan bahawa kita kini mahu
menolak item baru ke dalam tindanan ini.

244
00:11:36,030 --> 00:11:39,792
Dan kami ingin menolak yang baru
barang yang nilai data adalah 12.

245
00:11:39,792 --> 00:11:41,000
Baik apa yang kita akan lakukan?

246
00:11:41,000 --> 00:11:43,420
Well pertama kita akan
ruang malloc, dinamik

247
00:11:43,420 --> 00:11:45,411
memperuntukkan ruang untuk nod baru.

248
00:11:45,411 --> 00:11:48,160
Dan sudah tentu serta-merta selepas
kita membuat panggilan malloc kita sentiasa

249
00:11:48,160 --> 00:11:52,989
pastikan untuk memeriksa null,
kerana jika kami mendapat null kembali

250
00:11:52,989 --> 00:11:54,280
terdapat beberapa jenis masalah.

251
00:11:54,280 --> 00:11:57,570
Kami tidak mahu dereference null yang
penunjuk atau anda akan mengalami kesalahan seg.

252
00:11:57,570 --> 00:11:58,510
Yang tidak baik.

253
00:11:58,510 --> 00:11:59,760
Oleh itu, kita malloced nod.

254
00:11:59,760 --> 00:12:01,260
Kita akan menganggap kita telah mempunyai kejayaan di sini.

255
00:12:01,260 --> 00:12:06,090
Kami akan meletakkan 12 ke dalam
medan data nod itu.

256
00:12:06,090 --> 00:12:11,570
Sekarang jangan kamu ingat yang mana satu petunjuk kami
bergerak yang akan datang supaya kita tidak memecahkan rantai?

257
00:12:11,570 --> 00:12:15,100
Kami mempunyai beberapa pilihan di sini tetapi
satu-satunya yang akan selamat

258
00:12:15,100 --> 00:12:19,330
adalah untuk menetapkan berita penunjuk sebelah
mata kepada kepala lama dalam senarai

259
00:12:19,330 --> 00:12:21,360
atau apa yang tidak lama lagi akan menjadi
kepala lama senarai.

260
00:12:21,360 --> 00:12:23,610
Dan kini bahawa semua kami
unsur-unsur yang dirantai bersama-sama,

261
00:12:23,610 --> 00:12:27,370
kita hanya boleh bergerak senarai untuk menunjukkan
ke tempat yang sama yang tidak baru.

262
00:12:27,370 --> 00:12:33,550
Dan kami kini berkesan ditolak yang
elemen baru ke hadapan timbunan.

263
00:12:33,550 --> 00:12:36,420
>> Pop kami hanya mahu
memadam bahawa unsur pertama.

264
00:12:36,420 --> 00:12:38,150
Dan sebagainya pada dasarnya apa
kita perlu lakukan di sini,

265
00:12:38,150 --> 00:12:40,050
juga kita perlu mencari elemen kedua.

266
00:12:40,050 --> 00:12:43,540
Akhirnya yang akan menjadi baru
kepala selepas kami memadam yang pertama.

267
00:12:43,540 --> 00:12:47,300
Oleh itu, kita hanya perlu bermula dari
mulanya, bergerak satu ke hadapan.

268
00:12:47,300 --> 00:12:50,340
Apabila kami telah mendapat memegang pada satu
ke hadapan di mana kita kini

269
00:12:50,340 --> 00:12:53,850
kita boleh memadam yang pertama dengan selamat
dan kemudian kita boleh menggerakkan kepala

270
00:12:53,850 --> 00:12:57,150
untuk menunjukkan bagaimana akibat
penggal kedua dan kemudian sekarang

271
00:12:57,150 --> 00:12:59,170
adalah yang pertama selepas itu
nod telah dipadam.

272
00:12:59,170 --> 00:13:01,160
>> Jadi sekali lagi, mengambil melihat
ia sebagai gambar rajah kita

273
00:13:01,160 --> 00:13:05,022
mahu sekarang pop yang
unsur off timbunan ini.

274
00:13:05,022 --> 00:13:05,730
Jadi, apa yang kita lakukan?

275
00:13:05,730 --> 00:13:08,188
Well kita pertama akan mewujudkan
penunjuk baru yang akan

276
00:13:08,188 --> 00:13:10,940
untuk menghala ke tempat yang sama sebagai kepala.

277
00:13:10,940 --> 00:13:13,790
Kami akan bergerak satu kedudukan
ke hadapan dengan berkata setaraf trav

278
00:13:13,790 --> 00:13:17,510
Trav berikut sebagai contoh, yang
akan memajukan satu penunjuk trav

279
00:13:17,510 --> 00:13:19,324
kedudukan ke hadapan.

280
00:13:19,324 --> 00:13:21,240
Sekarang kita telah mendapat
berpegang elemen pertama

281
00:13:21,240 --> 00:13:24,573
melalui senarai penunjuk dipanggil, dan
Elemen kedua melalui penunjuk yang dipanggil

282
00:13:24,573 --> 00:13:28,692
trav, kita boleh memadam yang
Elemen pertama dari timbunan

283
00:13:28,692 --> 00:13:30,650
tanpa kehilangan yang lain
rantai kerana kita

284
00:13:30,650 --> 00:13:32,358
mempunyai cara untuk merujuk
untuk elemen kedua

285
00:13:32,358 --> 00:13:34,780
hadapan dengan cara yang
penunjuk dipanggil trav.

286
00:13:34,780 --> 00:13:37,100
>> Jadi sekarang kita boleh bebas nod tersebut.

287
00:13:37,100 --> 00:13:38,404
Kita boleh bebas senarai.

288
00:13:38,404 --> 00:13:41,320
Dan kemudian semua yang perlu kita lakukan sekarang ialah
menggerakkan senarai ke titik ke tempat yang sama

289
00:13:41,320 --> 00:13:44,482
trav yang tidak, dan kami semacam kembali
di mana kita bermula sebelum kita menolak 12

290
00:13:44,482 --> 00:13:45,690
pada di tempat pertama, betul.

291
00:13:45,690 --> 00:13:46,940
Ini betul-betul di mana kita berada.

292
00:13:46,940 --> 00:13:48,840
Kami mempunyai ini timbunan empat unsur.

293
00:13:48,840 --> 00:13:49,690
Kami telah menambah kelima.

294
00:13:49,690 --> 00:13:51,910
Kami menolak kelima
elemen pada, dan kemudian kita

295
00:13:51,910 --> 00:13:55,980
muncul yang baru
elemen ditambah kembali off.

296
00:13:55,980 --> 00:13:58,816
>> Itu benar-benar cukup banyak
semua ada susunan.

297
00:13:58,816 --> 00:14:00,190
Anda boleh melaksanakannya kerana tatasusunan.

298
00:14:00,190 --> 00:14:01,815
Anda boleh melaksanakannya kerana senarai berkaitan.

299
00:14:01,815 --> 00:14:04,810
Terdapat, sudah tentu, lain
cara-cara untuk melaksanakannya juga.

300
00:14:04,810 --> 00:14:09,060
Pada asasnya sebab kita akan menggunakan
susunan adalah untuk mengekalkan data dalam apa-apa cara

301
00:14:09,060 --> 00:14:12,090
bahawa yang paling baru-baru ini berkata
elemen adalah perkara pertama yang kami

302
00:14:12,090 --> 00:14:14,980
akan mahu kembali.

303
00:14:14,980 --> 00:14:17,900
Saya Doug Lloyd, ini adalah cs50.

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