1
00:00:00,000 --> 00:00:00,500

2
00:00:00,500 --> 00:00:11,137
[MUSIC PLAYING]

3
00:00:11,137 --> 00:00:12,220
DAVID J. Malan: Baiklah.

4
00:00:12,220 --> 00:00:13,950
Ini adalah CS50.

5
00:00:13,950 --> 00:00:18,560
Ini adalah minggu lima terus, dan kami
punya kabar baik dan kabar buruk.

6
00:00:18,560 --> 00:00:21,140
Jadi Kabar baiknya adalah bahwa CS50
meluncurkan Jumat ini.

7
00:00:21,140 --> 00:00:24,430
Jika Anda ingin bergabung dengan kami,
kepala ke URL yang biasa di sini.

8
00:00:24,430 --> 00:00:28,670
Berita lebih baik, tidak ada kuliah
ini datang Senin tanggal 13.

9
00:00:28,670 --> 00:00:31,970
Sedikit kurang berita yang lebih baik,
kuis nol Rabu depan.

10
00:00:31,970 --> 00:00:33,840
Lebih detail dapat
ditemukan di URL ini di sini.

11
00:00:33,840 --> 00:00:36,340
Dan selama beberapa hari ke depan
kita akan mengisi kekosongan

12
00:00:36,340 --> 00:00:39,234
berkaitan dengan kamar
bahwa kita akan telah memesan.

13
00:00:39,234 --> 00:00:41,400
Kabar baik adalah bahwa ada akan
menjadi review program-wide

14
00:00:41,400 --> 00:00:43,570
sesi ini datang
Senin di malam hari.

15
00:00:43,570 --> 00:00:46,270
Tetaplah kursus ini
website untuk lokasi dan rincian.

16
00:00:46,270 --> 00:00:49,290
Bagian, meskipun itu adalah
liburan, juga akan bertemu juga.

17
00:00:49,290 --> 00:00:50,490

18
00:00:50,490 --> 00:00:52,940
Berita Terbaik, kuliah Jumat depan.

19
00:00:52,940 --> 00:00:56,220
Jadi ini adalah kita tradisi
memiliki, sesuai silabus.

20
00:00:56,220 --> 00:00:58,100
Hanya-- itu akan menjadi luar biasa.

21
00:00:58,100 --> 00:01:02,510
Anda akan melihat hal-hal seperti
struktur data waktu yang konstan

22
00:01:02,510 --> 00:01:04,730
dan tabel hash dan pohon-pohon dan mencoba.

23
00:01:04,730 --> 00:01:07,150
Dan kita akan berbicara tentang masalah ulang tahun.

24
00:01:07,150 --> 00:01:09,440
Seluruh banyak barang
menanti Jumat depan.

25
00:01:09,440 --> 00:01:11,212

26
00:01:11,212 --> 00:01:12,200
OK.

27
00:01:12,200 --> 00:01:13,190
Bagaimanapun.

28
00:01:13,190 --> 00:01:17,080
>> Jadi ingat bahwa kita sudah
berfokus pada gambar ini apa

29
00:01:17,080 --> 00:01:18,980
dalam memori komputer kita.

30
00:01:18,980 --> 00:01:22,875
Jadi memori atau RAM adalah tempat program
ada saat Anda sedang menjalankan mereka.

31
00:01:22,875 --> 00:01:25,215
Jika Anda klik dua kali-an
icon untuk menjalankan beberapa program yang

32
00:01:25,215 --> 00:01:27,520
atau klik dua kali-an
icon untuk membuka beberapa berkas,

33
00:01:27,520 --> 00:01:30,430
itu dimuat dari hard Anda
drive atau solid state drive

34
00:01:30,430 --> 00:01:34,190
ke dalam RAM, Random Access Memory, di mana
ia hidup sampai listrik padam,

35
00:01:34,190 --> 00:01:36,700
tutup laptop ditutup,
atau Anda keluar dari program.

36
00:01:36,700 --> 00:01:38,960
>> Sekarang memori yang, dari
yang Anda mungkin memiliki

37
00:01:38,960 --> 00:01:41,950
1 gigabyte hari ini, 2
gigabyte, atau bahkan lebih,

38
00:01:41,950 --> 00:01:44,420
umumnya diletakkan
untuk program tertentu

39
00:01:44,420 --> 00:01:47,170
dalam jenis persegi panjang
model konseptual

40
00:01:47,170 --> 00:01:50,860
dimana kita memiliki tumpukan di bagian bawah
dan banyak hal lain di bagian atas.

41
00:01:50,860 --> 00:01:53,140
Hal di atas sangat
kita lihat pada gambar ini

42
00:01:53,140 --> 00:01:55,670
sebelum tapi tidak pernah berbicara tentang
adalah apa yang disebut segmen teks.

43
00:01:55,670 --> 00:01:58,419
Segmen teks adalah cara mewah
mengatakan nol dan orang-orang yang

44
00:01:58,419 --> 00:02:01,150
menyusun program yang dikompilasi Anda yang sebenarnya.

45
00:02:01,150 --> 00:02:03,910
>> Jadi, ketika Anda double-klik
Microsoft Word pada Mac atau PC,

46
00:02:03,910 --> 00:02:08,030
atau ketika Anda menjalankan dot slash Mario pada
Komputer Linux di jendela terminal Anda,

47
00:02:08,030 --> 00:02:12,460
nol dan orang-orang yang membentuk
Word atau Mario disimpan sementara

48
00:02:12,460 --> 00:02:16,610
dalam RAM komputer Anda dalam apa yang disebut the
Segmen teks untuk program tertentu.

49
00:02:16,610 --> 00:02:19,080
Di bawah yang berlangsung diinisialisasi
dan data diinisiasi.

50
00:02:19,080 --> 00:02:22,655
Ini adalah hal-hal seperti variabel global,
bahwa kita sudah tidak digunakan banyak,

51
00:02:22,655 --> 00:02:24,910
namun pada kesempatan kami telah
memiliki variabel global

52
00:02:24,910 --> 00:02:28,819
atau statis didefinisikan string yang
sulit dikodekan kata-kata seperti "halo"

53
00:02:28,819 --> 00:02:31,860
yang tidak diambil dari pengguna
yang keras-kode ke dalam program Anda.

54
00:02:31,860 --> 00:02:34,230
>> Sekarang, turun di bawah kita
memiliki apa yang disebut stack.

55
00:02:34,230 --> 00:02:37,665
Dan tumpukan, sejauh ini, kami sudah
gunakan untuk jenis apa tujuan?

56
00:02:37,665 --> 00:02:39,706

57
00:02:39,706 --> 00:02:40,997
Apa stack digunakan untuk?

58
00:02:40,997 --> 00:02:41,160
Ya?

59
00:02:41,160 --> 00:02:42,070
>> AUDIENCE: Fungsi.

60
00:02:42,070 --> 00:02:43,320
>> DAVID J. Malan: Untuk fungsi?

61
00:02:43,320 --> 00:02:44,980
Dalam arti untuk fungsi?

62
00:02:44,980 --> 00:02:48,660
>> AUDIENCE: Ketika Anda memanggil fungsi, yang
argumen disalin ke stack.

63
00:02:48,660 --> 00:02:49,660
>> DAVID J. Malan: Tepat.

64
00:02:49,660 --> 00:02:52,650
Ketika Anda memanggil fungsi, yang
argumen disalin ke stack.

65
00:02:52,650 --> 00:02:56,330
Jadi setiap X atau Y atau A atau B
bahwa Anda melewati ke dalam fungsi

66
00:02:56,330 --> 00:02:58,680
untuk sementara memakai
yang disebut stack,

67
00:02:58,680 --> 00:03:02,000
seperti salah satu Annenberg
makan nampan hall, dan juga hal-hal

68
00:03:02,000 --> 00:03:03,190
seperti variabel lokal.

69
00:03:03,190 --> 00:03:06,290
Jika fungsi foo atau swap
fungsi memiliki variabel lokal,

70
00:03:06,290 --> 00:03:08,602
seperti suhu, kedua
berakhir pada stack.

71
00:03:08,602 --> 00:03:11,560
Sekarang, kita tidak akan berbicara terlalu banyak tentang
mereka, tetapi variabel lingkungan ini

72
00:03:11,560 --> 00:03:15,690
di bagian bawah kami melihat beberapa waktu lalu ketika
Aku futzing di keyboard satu hari

73
00:03:15,690 --> 00:03:20,050
dan aku mulai mengakses hal-hal
seperti argv 100 atau argv 1.000,

74
00:03:20,050 --> 00:03:22,320
hanya elements-- saya lupa
yang Numbers tapi itu

75
00:03:22,320 --> 00:03:24,330
tidak seharusnya diakses oleh saya.

76
00:03:24,330 --> 00:03:26,581
Kami mulai melihat beberapa
simbol yang funky di layar.

77
00:03:26,581 --> 00:03:28,330
Mereka adalah yang disebut
variabel lingkungan

78
00:03:28,330 --> 00:03:32,390
seperti pengaturan global untuk saya
program atau untuk komputer saya, tidak

79
00:03:32,390 --> 00:03:37,090
tidak terkait dengan baru-baru ini
bug yang kita bahas,

80
00:03:37,090 --> 00:03:39,670
SHELLSHOCK, yang sudah
mengganggu beberapa komputer.

81
00:03:39,670 --> 00:03:42,960
>> Sekarang terakhir, fokus saat ini
kami akhirnya akan berada di heap.

82
00:03:42,960 --> 00:03:44,864
Ini adalah potongan lain dari memori.

83
00:03:44,864 --> 00:03:47,030
Dan pada dasarnya semua ini
memori adalah hal yang sama.

84
00:03:47,030 --> 00:03:48,040
Ini adalah perangkat keras yang sama.

85
00:03:48,040 --> 00:03:49,956
Kami hanya semacam
mengobati cluster yang berbeda

86
00:03:49,956 --> 00:03:51,460
dari byte untuk tujuan yang berbeda.

87
00:03:51,460 --> 00:03:56,540
Tumpukan ini juga akan menjadi tempat
variabel dan memori yang Anda meminta

88
00:03:56,540 --> 00:03:58,810
dari sistem operasi
disimpan sementara.

89
00:03:58,810 --> 00:04:01,890
>> Tapi ada semacam masalah
di sini, seperti gambar menyiratkan.

90
00:04:01,890 --> 00:04:05,261
Kami semacam memiliki dua
kapal akan bertabrakan.

91
00:04:05,261 --> 00:04:08,010
Karena ketika Anda menggunakan lebih banyak
tumpukan, dan seperti yang kita lihat hari ini

92
00:04:08,010 --> 00:04:11,800
selanjutnya, karena Anda menggunakan lebih dan lebih dari
heap, pasti hal-hal buruk yang mungkin terjadi.

93
00:04:11,800 --> 00:04:15,054
Dan memang, kita dapat menginduksi yang
sengaja atau tidak sengaja.

94
00:04:15,054 --> 00:04:16,970
Jadi cliffhanger terakhir
Waktu itu program ini,

95
00:04:16,970 --> 00:04:20,570
yang tidak melayani setiap fungsional
tujuan lain selain untuk menunjukkan

96
00:04:20,570 --> 00:04:24,750
bagaimana Anda sebagai orang jahat benar-benar dapat mengambil
keuntungan dari bug dalam program seseorang

97
00:04:24,750 --> 00:04:28,460
dan mengambil alih sebuah program atau bahkan
sistem komputer secara keseluruhan atau server.

98
00:04:28,460 --> 00:04:31,660
Jadi hanya melirik sebentar, Anda
melihat bahwa utama di bagian bawah

99
00:04:31,660 --> 00:04:34,510
mengambil di baris perintah
argumen, sesuai argv.

100
00:04:34,510 --> 00:04:38,480
Dan memiliki panggilan ke fungsi f,
dasarnya fungsi tanpa nama yang disebut

101
00:04:38,480 --> 00:04:40,250
f, dan itu lewat di argv [1].

102
00:04:40,250 --> 00:04:43,960
>> Jadi kata apa pun jenis pengguna dalam di
prompt setelah nama program ini,

103
00:04:43,960 --> 00:04:49,310
dan kemudian ini fungsi sewenang-wenang atas
atas, f, mengambil dalam sebuah string, AKA char *,

104
00:04:49,310 --> 00:04:51,720
seperti yang telah kita mulai membahas,
dan hanya menyebutnya "bar."

105
00:04:51,720 --> 00:04:53,310
Tapi kita bisa menyebutnya apa pun.

106
00:04:53,310 --> 00:04:57,470
Dan kemudian menyatakan, dalam
dari f, sebuah array karakter

107
00:04:57,470 --> 00:04:59,930
disebut c-- 12 karakter tersebut.

108
00:04:59,930 --> 00:05:03,580
>> Sekarang, berdasarkan cerita saya mengatakan
beberapa saat yang lalu, di mana dalam memori

109
00:05:03,580 --> 00:05:06,720
adalah c, atau orang-orang 12
karakter akan berakhir?

110
00:05:06,720 --> 00:05:07,570
Hanya untuk menjadi jelas.

111
00:05:07,570 --> 00:05:08,070
Ya?

112
00:05:08,070 --> 00:05:08,590
>> AUDIENCE: Pada stack.

113
00:05:08,590 --> 00:05:09,420
>> DAVID J. Malan: Pada stack.

114
00:05:09,420 --> 00:05:10,720
Jadi c adalah variabel lokal.

115
00:05:10,720 --> 00:05:14,079
Kami minta 12 karakter atau 12 byte.

116
00:05:14,079 --> 00:05:16,120
Mereka akan berakhir
pada apa yang disebut stack.

117
00:05:16,120 --> 00:05:18,530
Sekarang akhirnya adalah fungsi lain ini
itu sebenarnya cukup berguna,

118
00:05:18,530 --> 00:05:20,571
tapi kami tidak benar-benar digunakan
diri kita sendiri, strncopy.

119
00:05:20,571 --> 00:05:21,550

120
00:05:21,550 --> 00:05:25,200
Ini berarti string copy, tapi
hanya n huruf, n karakter.

121
00:05:25,200 --> 00:05:31,990
Jadi n karakter akan
disalin dari bar ke c.

122
00:05:31,990 --> 00:05:32,980
Dan berapa banyak?

123
00:05:32,980 --> 00:05:34,110
Panjang bar.

124
00:05:34,110 --> 00:05:36,330
Jadi dengan kata lain, bahwa
satu baris, strncopy,

125
00:05:36,330 --> 00:05:39,500
akan menyalin
efektif bar untuk c.

126
00:05:39,500 --> 00:05:42,340
>> Sekarang, hanya untuk jenis mengantisipasi
moral dari cerita ini,

127
00:05:42,340 --> 00:05:44,750
apa yang berpotensi bermasalah di sini?

128
00:05:44,750 --> 00:05:49,710
Meskipun kita sedang memeriksa panjang
bar dan menyerahkannya ke strncopy,

129
00:05:49,710 --> 00:05:53,145
apa usus Anda memberitahu Anda adalah
masih rusak tentang program ini?

130
00:05:53,145 --> 00:05:54,410

131
00:05:54,410 --> 00:05:55,220
Ya?

132
00:05:55,220 --> 00:05:57,491
>> AUDIENCE: Tidak termasuk
ruang untuk karakter null.

133
00:05:57,491 --> 00:05:59,990
DAVID J. Malan: Tidak termasuk
ruang untuk karakter null.

134
00:05:59,990 --> 00:06:02,073
Berpotensi, tidak seperti di
praktek masa lalu kita bahkan tidak

135
00:06:02,073 --> 00:06:04,810
memiliki begitu banyak sebagai plus 1
mengakomodasi karakter null.

136
00:06:04,810 --> 00:06:06,649
Tapi itu bahkan lebih buruk dari itu.

137
00:06:06,649 --> 00:06:07,940
Apa lagi yang kita gagal lakukan?

138
00:06:07,940 --> 00:06:08,432
Ya?

139
00:06:08,432 --> 00:06:09,307
>> AUDIENCE: [Tak terdengar]

140
00:06:09,307 --> 00:06:15,440

141
00:06:15,440 --> 00:06:16,440
DAVID J. Malan Perfect.

142
00:06:16,440 --> 00:06:18,490
Kami telah dikodekan keras 12 cukup sewenang-wenang.

143
00:06:18,490 --> 00:06:19,497

144
00:06:19,497 --> 00:06:21,330
Itu tidak begitu banyak
masalah, tapi kenyataan

145
00:06:21,330 --> 00:06:25,630
bahwa kita tidak memperhatikan apakah
panjang bar kurang dari 12,

146
00:06:25,630 --> 00:06:28,530
dalam hal ini akan menjadi
aman untuk memasukkannya ke dalam memori

147
00:06:28,530 --> 00:06:30,260
disebut c yang telah kita dialokasikan.

148
00:06:30,260 --> 00:06:32,960
Memang, jika bar seperti
20 karakter,

149
00:06:32,960 --> 00:06:39,010
fungsi ini tampaknya menyalin
20 karakter dari bar ke c, demikian

150
00:06:39,010 --> 00:06:41,310
mengambil setidaknya 8 byte
bahwa itu tidak boleh.

151
00:06:41,310 --> 00:06:42,690
Itulah implikasi di sini.

152
00:06:42,690 --> 00:06:44,347
>> Jadi singkatnya, program yang rusak.

153
00:06:44,347 --> 00:06:45,180
Tidak masalah besar.

154
00:06:45,180 --> 00:06:46,360
Mungkin Anda mendapatkan kesalahan segmentasi.

155
00:06:46,360 --> 00:06:47,651
Kita semua sudah memiliki bug dalam program.

156
00:06:47,651 --> 00:06:50,196
Kita semua mungkin memiliki bug
dalam program sekarang.

157
00:06:50,196 --> 00:06:51,320
Tapi apa implikasinya?

158
00:06:51,320 --> 00:06:54,390
Nah, di sini adalah versi zoom-in dari
bahwa gambar memori komputer saya.

159
00:06:54,390 --> 00:06:56,230
Ini adalah bagian bawah tumpukan saya.

160
00:06:56,230 --> 00:06:59,644
Dan memang, di bagian paling bawah adalah apa yang
disebut tumpukan rutin orang tua, cara mewah

161
00:06:59,644 --> 00:07:00,560
mengatakan itu utama.

162
00:07:00,560 --> 00:07:03,772
Sehingga siapa pun yang disebut fungsi
f yang kita bicarakan.

163
00:07:03,772 --> 00:07:05,230
Jadi, ini adalah bagian bawah tumpukan.

164
00:07:05,230 --> 00:07:06,640
Alamat pengirim adalah sesuatu yang baru.

165
00:07:06,640 --> 00:07:08,810
Itu selalu ada,
selalu di foto itu.

166
00:07:08,810 --> 00:07:10,440
Kami tidak pernah meminta perhatian untuk itu.

167
00:07:10,440 --> 00:07:15,290
Karena ternyata cara kerjanya adalah c
bahwa ketika salah satu fungsi panggilan lain,

168
00:07:15,290 --> 00:07:18,780
tidak hanya melakukan argumen untuk itu
Fungsi bisa didorong ke stack,

169
00:07:18,780 --> 00:07:22,470
tidak hanya melakukan fungsi yang lokal
variabel mendapatkan didorong ke stack,

170
00:07:22,470 --> 00:07:26,820
sesuatu yang disebut alamat pengirim
juga akan dimasukkan ke dalam stack.

171
00:07:26,820 --> 00:07:33,330
Secara khusus, jika panggilan utama foo, ini utama
alamat sendiri dalam memori, sapi sesuatu,

172
00:07:33,330 --> 00:07:38,240
efektif akan dimasukkan ke stack
sehingga ketika f dilakukan mengeksekusinya

173
00:07:38,240 --> 00:07:43,630
tahu di mana untuk melompat kembali ke dalam teks
segmen untuk terus menjalankan.

174
00:07:43,630 --> 00:07:47,760
>> Jadi jika kita berada di sini konseptual,
di utama, maka f dipanggil.

175
00:07:47,760 --> 00:07:50,200
Bagaimana f tahu siapa
untuk kontrol tangan kembali?

176
00:07:50,200 --> 00:07:52,020
Nah, ini sedikit
breadcrumb merah di sini,

177
00:07:52,020 --> 00:07:54,978
disebut alamat pengirim, hanya
cek, apa itu alamat pengirim?

178
00:07:54,978 --> 00:07:57,039
Oh, biarkan aku melompat kembali ke utama di sini.

179
00:07:57,039 --> 00:07:59,080
Dan itu sedikit
suatu penyederhanaan yang berlebihan,

180
00:07:59,080 --> 00:08:00,750
karena nol dan satu
untuk utama secara teknis

181
00:08:00,750 --> 00:08:01,967
di sini di segmen teknologi.

182
00:08:01,967 --> 00:08:03,800
Tapi itu ide. f
hanya harus tahu apa

183
00:08:03,800 --> 00:08:06,680
ke tempat kontrol akhirnya kembali.

184
00:08:06,680 --> 00:08:09,790
>> Tapi cara komputer
telah lama ditata hal

185
00:08:09,790 --> 00:08:12,320
seperti variabel lokal dan
argumen seperti ini.

186
00:08:12,320 --> 00:08:17,180
Jadi di bagian atas gambar ini di
biru stack frame untuk f, sehingga semua

187
00:08:17,180 --> 00:08:19,630
memori yang f
khusus adalah menggunakan.

188
00:08:19,630 --> 00:08:22,990
Jadi sesuai, perhatikan bahwa
bar di foto ini.

189
00:08:22,990 --> 00:08:23,980
Bar adalah argumen.

190
00:08:23,980 --> 00:08:27,240
Dan kami menyatakan bahwa argumen untuk
fungsi mendapatkan didorong ke stack.

191
00:08:27,240 --> 00:08:29,910
Dan c, tentu saja, adalah
juga di foto ini.

192
00:08:29,910 --> 00:08:33,520
>> Dan hanya untuk tujuan notasi,
perhatikan di bagian atas pojok kiri

193
00:08:33,520 --> 00:08:37,020
adalah apa yang akan c braket 0 dan
kemudian sedikit ke kanan

194
00:08:37,020 --> 00:08:38,220
adalah c braket 11.

195
00:08:38,220 --> 00:08:41,240
Jadi dengan kata lain, Anda bisa membayangkan
bahwa ada kotak byte

196
00:08:41,240 --> 00:08:44,380
ada, pertama adalah
kiri atas, bawah yang

197
00:08:44,380 --> 00:08:48,360
adalah yang terakhir dari mereka 12 byte.

198
00:08:48,360 --> 00:08:49,930
>> Tapi sekarang coba untuk maju cepat.

199
00:08:49,930 --> 00:08:55,580
Apa yang akan terjadi jika kita melewati
dalam string bar yang lebih panjang dari c?

200
00:08:55,580 --> 00:08:59,130
Dan kita tidak memeriksa apakah
itu memang lebih dari 12.

201
00:08:59,130 --> 00:09:03,146
Bagian mana dari gambar ini akan
mendapatkan ditimpa oleh byte 0, 1, 2, 3,

202
00:09:03,146 --> 00:09:07,890
dot dot dot, 11, dan kemudian
buruk, 12, 13 sampai 19?

203
00:09:07,890 --> 00:09:11,820
Apa yang akan terjadi di sini,
jika Anda menyimpulkan dari pengurutan

204
00:09:11,820 --> 00:09:14,790
bahwa c braket 0 adalah di atas
dan c bracket 11 adalah semacam turun

205
00:09:14,790 --> 00:09:15,812
ke kanan?

206
00:09:15,812 --> 00:09:16,796
Ya?

207
00:09:16,796 --> 00:09:19,260
>> AUDIENCE: Yah, itu akan
untuk menimpa char * bar.

208
00:09:19,260 --> 00:09:22,260
>> DAVID J. Malan: Ya, sepertinya
Anda akan menimpa char * bar.

209
00:09:22,260 --> 00:09:26,245
Dan lebih buruk lagi, jika Anda mengirim dalam sangat panjang
String, Anda bahkan mungkin menimpa apa?

210
00:09:26,245 --> 00:09:27,460

211
00:09:27,460 --> 00:09:28,570
Alamat pulang.

212
00:09:28,570 --> 00:09:31,380
Yang sekali lagi, adalah seperti
breadcrumb untuk memberitahu program mana

213
00:09:31,380 --> 00:09:34,060
untuk kembali ke saat f
dilakukan dipanggil.

214
00:09:34,060 --> 00:09:37,140
>> Jadi apa yang biasanya dilakukan orang jahat
adalah jika mereka menemukan sebuah program

215
00:09:37,140 --> 00:09:41,290
bahwa mereka penasaran apakah adalah
dieksploitasi, kereta sedemikian rupa

216
00:09:41,290 --> 00:09:43,550
bahwa ia dapat mengambil
keuntungan dari bug itu,

217
00:09:43,550 --> 00:09:45,720
umumnya mereka tidak mendapatkan
hak ini pertama kalinya.

218
00:09:45,720 --> 00:09:48,590
Mereka hanya mulai mengirim, misalnya,
string acak ke dalam program Anda,

219
00:09:48,590 --> 00:09:50,260
apakah di keyboard,
atau terus terang mereka mungkin

220
00:09:50,260 --> 00:09:52,740
menulis sebuah program kecil untuk hanya
secara otomatis menghasilkan string,

221
00:09:52,740 --> 00:09:55,430
dan mulai menggedor program anda dengan
mengirimkan banyak input yang berbeda

222
00:09:55,430 --> 00:09:56,340
pada panjang yang berbeda.

223
00:09:56,340 --> 00:09:58,990
>> Segera setelah crash program Anda,
itu suatu hal yang luar biasa.

224
00:09:58,990 --> 00:10:01,020
Karena itu berarti dia
atau dia telah menemukan

225
00:10:01,020 --> 00:10:02,660
apa yang mungkin memang bug.

226
00:10:02,660 --> 00:10:05,830
Dan kemudian mereka bisa mendapatkan lebih pintar
dan mulai fokus lebih sempit

227
00:10:05,830 --> 00:10:07,420
tentang bagaimana memanfaatkan bug tersebut.

228
00:10:07,420 --> 00:10:11,480
Secara khusus, apa yang dia mungkin
lakukan adalah mengirim, dalam kasus terbaik, halo.

229
00:10:11,480 --> 00:10:12,210
Bukan masalah besar.

230
00:10:12,210 --> 00:10:14,750
Ini string yang cukup singkat.

231
00:10:14,750 --> 00:10:18,100
Tapi bagaimana kalau dia mengirim,
dan kami akan generalisasi sebagai,

232
00:10:18,100 --> 00:10:20,890
Serangan code-- sehingga nol
dan orang-orang yang melakukan hal-hal

233
00:10:20,890 --> 00:10:25,150
seperti rm-rf, yang menghapus segala sesuatu
dari hard drive atau mengirim spam

234
00:10:25,150 --> 00:10:27,000
atau entah bagaimana menyerang mesin?

235
00:10:27,000 --> 00:10:29,570
>> Jadi jika masing-masing
huruf A hanya mewakili,

236
00:10:29,570 --> 00:10:32,380
konseptual, menyerang, menyerang,
serangan, serangan, beberapa kode yang buruk

237
00:10:32,380 --> 00:10:36,410
bahwa orang lain menulis, tetapi
jika seseorang yang cukup pintar

238
00:10:36,410 --> 00:10:40,790
untuk tidak hanya mencakup semua
mereka rm-RFS, tetapi juga

239
00:10:40,790 --> 00:10:46,100
memiliki beberapa byte terakhir nya
menjadi nomor yang sesuai

240
00:10:46,100 --> 00:10:50,540
ke alamat nya
atau kode serangan sendiri

241
00:10:50,540 --> 00:10:53,820
bahwa ia lulus hanya
dengan menyediakan pada prompt,

242
00:10:53,820 --> 00:10:58,760
Anda dapat secara efektif trik komputer
dalam memperhatikan ketika f dilakukan mengeksekusi,

243
00:10:58,760 --> 00:11:02,400
oh, sudah waktunya bagi saya untuk melompat
kembali ke alamat pengirim merah.

244
00:11:02,400 --> 00:11:06,070
Tetapi karena ia memiliki entah bagaimana
tumpang tindih bahwa alamat pengirim

245
00:11:06,070 --> 00:11:09,602
dengan nomor mereka sendiri,
dan mereka cukup pintar

246
00:11:09,602 --> 00:11:11,560
telah dikonfigurasi bahwa
nomor untuk merujuk, karena Anda

247
00:11:11,560 --> 00:11:13,740
lihat di super top
kiri pojok sana,

248
00:11:13,740 --> 00:11:18,020
alamat yang sebenarnya di komputer
memori dari beberapa kode serangan mereka,

249
00:11:18,020 --> 00:11:21,740
orang jahat dapat trik komputer
dalam mengeksekusi kode sendiri.

250
00:11:21,740 --> 00:11:23,700
>> Dan kode itu, sekali lagi, bisa apa saja.

251
00:11:23,700 --> 00:11:26,120
Ini umumnya disebut
kode shell, yang hanya

252
00:11:26,120 --> 00:11:29,030
cara untuk mengatakan bahwa itu bukan
umumnya sesuatu yang sederhana seperti rm-rf.

253
00:11:29,030 --> 00:11:32,340
Ini sebenarnya sesuatu seperti Bash,
atau program yang sebenarnya yang memberinya

254
00:11:32,340 --> 00:11:37,230
atau kontrol program nya untuk mengeksekusi
apa pun yang mereka ingin.

255
00:11:37,230 --> 00:11:40,210
Jadi singkatnya, ini semua
berasal dari fakta sederhana

256
00:11:40,210 --> 00:11:44,490
bahwa bug ini melibatkan tidak memeriksa
batas-batas array.

257
00:11:44,490 --> 00:11:47,250
Dan karena cara
komputer bekerja adalah bahwa mereka

258
00:11:47,250 --> 00:11:49,430
menggunakan tumpukan dari
efektif, secara konseptual,

259
00:11:49,430 --> 00:11:54,830
bawah ke atas, tapi kemudian unsur-unsur
Anda mendorong ke stack tumbuh atas ke bawah,

260
00:11:54,830 --> 00:11:56,624
ini sangat bermasalah.

261
00:11:56,624 --> 00:11:58,290
Sekarang, ada cara untuk bekerja di sekitar ini.

262
00:11:58,290 --> 00:12:00,800
Dan terus terang, ada bahasa
yang dapat digunakan untuk bekerja di sekitar ini.

263
00:12:00,800 --> 00:12:03,100
Java kebal, misalnya,
untuk isu ini.

264
00:12:03,100 --> 00:12:04,110
Karena mereka tidak memberikan petunjuk.

265
00:12:04,110 --> 00:12:05,943
Mereka tidak memberikan
alamat memori langsung.

266
00:12:05,943 --> 00:12:08,560
Jadi dengan kekuatan ini yang kita miliki
menyentuh apa pun di memori

267
00:12:08,560 --> 00:12:11,580
kami ingin datang, diakui, risiko besar.

268
00:12:11,580 --> 00:12:12,430
>> Jadi mengawasi keluar.

269
00:12:12,430 --> 00:12:14,596
Jika, terus terang, pada bulan-bulan
atau tahun-tahun mendatang, kapan saja

270
00:12:14,596 --> 00:12:17,740
Anda membaca tentang beberapa eksploitasi
program atau server,

271
00:12:17,740 --> 00:12:22,370
jika Anda pernah melihat sedikit sesuatu
seperti serangan buffer overflow,

272
00:12:22,370 --> 00:12:25,390
atau stack overflow adalah jenis lain
serangan, serupa semangatnya,

273
00:12:25,390 --> 00:12:28,770
sebanyak mengilhami website
nama, jika Anda tahu itu,

274
00:12:28,770 --> 00:12:33,170
itu semua hanya berbicara tentang
meluap ukuran beberapa karakter

275
00:12:33,170 --> 00:12:36,200
array atau beberapa array yang lebih umum.

276
00:12:36,200 --> 00:12:38,822
Semua pertanyaan, kemudian, dalam hal ini?

277
00:12:38,822 --> 00:12:39,780
Jangan coba ini di rumah.

278
00:12:39,780 --> 00:12:41,620

279
00:12:41,620 --> 00:12:42,300
>> Baiklah.

280
00:12:42,300 --> 00:12:47,270
Jadi malloc sejauh ini telah baru kami
teman bahwa kita dapat mengalokasikan memori

281
00:12:47,270 --> 00:12:50,540
bahwa kita tidak perlu tahu di
maju yang kita inginkan sehingga kita tidak memiliki

282
00:12:50,540 --> 00:12:52,920
kode keras ke kami
nomor program seperti 12.

283
00:12:52,920 --> 00:12:55,550
Setelah pengguna memberitahu kita berapa banyak
Data yang dia inginkan untuk input,

284
00:12:55,550 --> 00:12:58,000
kita dapat malloc yang banyak memori.

285
00:12:58,000 --> 00:13:01,484
>> Jadi malloc ternyata, untuk
sejauh kita sudah menggunakannya,

286
00:13:01,484 --> 00:13:03,900
eksplisit terakhir kali, dan kemudian
kalian telah menggunakannya

287
00:13:03,900 --> 00:13:08,160
untuk getString sadar untuk
beberapa minggu, semua memori malloc ini

288
00:13:08,160 --> 00:13:09,820
berasal dari apa yang disebut tumpukan.

289
00:13:09,820 --> 00:13:13,852
Dan inilah mengapa GetString, misalnya,
dapat mengalokasikan memori dinamis

290
00:13:13,852 --> 00:13:16,060
tanpa mengetahui apa yang Anda
akan mengetik di muka,

291
00:13:16,060 --> 00:13:21,520
tangan Anda kembali pointer ke memori yang,
dan memori yang masih milik Anda,

292
00:13:21,520 --> 00:13:24,080
bahkan setelah getString kembali.

293
00:13:24,080 --> 00:13:27,450
Karena ingat setelah semua bahwa
stack terus akan naik dan turun,

294
00:13:27,450 --> 00:13:27,950
atas dan ke bawah.

295
00:13:27,950 --> 00:13:30,230
Dan segera setelah ia pergi
bawah, itu berarti memori setiap

296
00:13:30,230 --> 00:13:33,030
fungsi ini digunakan harus
tidak digunakan oleh orang lain.

297
00:13:33,030 --> 00:13:34,570
Itu nilai sampah sekarang.

298
00:13:34,570 --> 00:13:36,120
>> Tapi tumpukan sampai di sini.

299
00:13:36,120 --> 00:13:39,360
Dan apa yang bagus tentang malloc adalah bahwa
ketika malloc mengalokasikan memori di sini,

300
00:13:39,360 --> 00:13:42,070
itu tidak berdampak, untuk
sebagian, oleh stack.

301
00:13:42,070 --> 00:13:46,000
Jadi fungsi apapun dapat mengakses
memori yang telah malloc'd,

302
00:13:46,000 --> 00:13:49,120
bahkan oleh fungsi seperti GetString,
bahkan setelah itu dikembalikan.

303
00:13:49,120 --> 00:13:51,700
>> Sekarang, kebalikan dari malloc gratis.

304
00:13:51,700 --> 00:13:53,900
Dan memang, aturan Anda
harus mulai mengadopsi

305
00:13:53,900 --> 00:13:58,950
adalah, setiap, setiap kali Anda menggunakan malloc
Anda harus sendiri menggunakan bebas, akhirnya,

306
00:13:58,950 --> 00:14:00,280
pada yang pointer yang sama.

307
00:14:00,280 --> 00:14:03,289
Selama ini kita telah menulis
buggy, kode kereta, karena berbagai alasan.

308
00:14:03,289 --> 00:14:05,580
Tapi salah satu yang telah
menggunakan perpustakaan CS50, yang

309
00:14:05,580 --> 00:14:09,010
itu sendiri sengaja
buggy, kebocoran memori.

310
00:14:09,010 --> 00:14:11,410
Setiap kali Anda menelepon GetString
selama beberapa minggu terakhir

311
00:14:11,410 --> 00:14:13,870
kami meminta operasi
sistem, Linux, untuk memori.

312
00:14:13,870 --> 00:14:15,780
Dan Anda tidak pernah sekali diberikan kembali.

313
00:14:15,780 --> 00:14:17,730
Dan ini tidak, dalam
berlatih, hal yang baik.

314
00:14:17,730 --> 00:14:20,330
>> Dan Valgrind, salah satu
alat diperkenalkan pada PSET 4,

315
00:14:20,330 --> 00:14:22,900
adalah semua tentang membantu Anda
sekarang menemukan bug seperti itu.

316
00:14:22,900 --> 00:14:27,060
Tapi untungnya untuk PSET 4 Anda tidak perlu
untuk menggunakan perpustakaan CS50 atau GetString.

317
00:14:27,060 --> 00:14:31,220
Jadi setiap bug yang berhubungan dengan memori
akhirnya akan menjadi Anda sendiri.

318
00:14:31,220 --> 00:14:34,060
>> Jadi malloc lebih dari sekedar
nyaman untuk tujuan ini.

319
00:14:34,060 --> 00:14:37,420
Kami benar-benar dapat memecahkan sekarang
masalah fundamental berbeda,

320
00:14:37,420 --> 00:14:41,640
dan fundamental memecahkan masalah yang lebih
efektif sesuai janji minggu nol ini.

321
00:14:41,640 --> 00:14:44,720
Sejauh ini terseksi
struktur data kami sudah.

322
00:14:44,720 --> 00:14:47,804
Dan dengan struktur data saya hanya berarti
cara konseptualisasi memori

323
00:14:47,804 --> 00:14:50,720
dengan cara yang melampaui hanya mengatakan,
ini adalah int, ini adalah char.

324
00:14:50,720 --> 00:14:52,930
Kita bisa mulai dengan hal-hal klaster bersama-sama.

325
00:14:52,930 --> 00:14:54,460
>> Jadi array tampak seperti ini.

326
00:14:54,460 --> 00:14:57,270
Dan apa kunci dalam tentang
Array adalah bahwa hal itu memberi Anda

327
00:14:57,270 --> 00:14:59,724
back-to-back potongan
memori, yang masing-masing

328
00:14:59,724 --> 00:15:02,765
akan menjadi dari jenis yang sama, int,
int, int, int, atau char, char, char,

329
00:15:02,765 --> 00:15:03,330
arang.

330
00:15:03,330 --> 00:15:04,496
Tapi ada beberapa kelemahan.

331
00:15:04,496 --> 00:15:06,570
Hal ini misalnya, adalah
array ukuran enam.

332
00:15:06,570 --> 00:15:10,650
Misalkan Anda mengisi array ini dengan enam
nomor dan kemudian, untuk alasan apa pun,

333
00:15:10,650 --> 00:15:13,187
pengguna Anda ingin memberikan
Anda sejumlah ketujuh.

334
00:15:13,187 --> 00:15:14,020
Di mana Anda menempatkan itu?

335
00:15:14,020 --> 00:15:15,490

336
00:15:15,490 --> 00:15:18,990
>> Apa solusinya jika Anda memiliki
menciptakan sebuah array di stack,

337
00:15:18,990 --> 00:15:22,030
misalnya, hanya dengan minggu
dua notasi yang kita diperkenalkan,

338
00:15:22,030 --> 00:15:23,730
kurung persegi dengan jumlah dalam?

339
00:15:23,730 --> 00:15:25,160

340
00:15:25,160 --> 00:15:27,260
Nah, Anda punya enam
angka dalam kotak-kotak ini.

341
00:15:27,260 --> 00:15:28,530
Apa yang akan naluri Anda menjadi?

342
00:15:28,530 --> 00:15:29,973
Di mana Anda ingin menempatkan itu?

343
00:15:29,973 --> 00:15:30,860
>> AUDIENCE: [Tak terdengar]

344
00:15:30,860 --> 00:15:31,315
>> DAVID J. Malan: Maaf?

345
00:15:31,315 --> 00:15:32,380
>> AUDIENCE: Taruh di akhir.

346
00:15:32,380 --> 00:15:33,796
>> DAVID J. Malan: Taruh di akhir.

347
00:15:33,796 --> 00:15:35,880
Jadi hanya ke kanan,
luar kotak ini.

348
00:15:35,880 --> 00:15:38,710
Yang akan menyenangkan, tetapi
ternyata Anda tidak bisa melakukan itu.

349
00:15:38,710 --> 00:15:41,350
Karena jika Anda tidak diminta
untuk potongan ini memori,

350
00:15:41,350 --> 00:15:44,490
bisa juga dengan kebetulan bahwa ini
sedang digunakan oleh beberapa variabel lain

351
00:15:44,490 --> 00:15:45,030
sama sekali.

352
00:15:45,030 --> 00:15:49,210
Pikirkan kembali seminggu atau jadi ketika kita meletakkan
nama-nama Zamyla dan Davin dan Gabe

353
00:15:49,210 --> 00:15:49,930
dalam memori.

354
00:15:49,930 --> 00:15:51,638
Mereka benar-benar
kembali untuk kembali ke belakang.

355
00:15:51,638 --> 00:15:53,550
Jadi kita tidak bisa serta merta
percaya bahwa dunia apapun

356
00:15:53,550 --> 00:15:55,800
di sini tersedia bagi saya untuk menggunakan.

357
00:15:55,800 --> 00:15:56,990
>> Jadi apa lagi yang mungkin Anda lakukan?

358
00:15:56,990 --> 00:16:00,282
Nah, setelah menyadari Anda
membutuhkan sebuah array ukuran tujuh,

359
00:16:00,282 --> 00:16:02,490
Anda hanya bisa membuat
array ukuran tujuh kemudian gunakan

360
00:16:02,490 --> 00:16:05,950
untuk loop atau loop sementara,
menyalinnya ke array baru,

361
00:16:05,950 --> 00:16:09,680
dan kemudian entah bagaimana hanya menyingkirkan
array ini atau hanya berhenti menggunakannya.

362
00:16:09,680 --> 00:16:12,130
Tapi itu tidak terlalu efisien.

363
00:16:12,130 --> 00:16:15,340
Singkatnya, array jangan biarkan
Anda dinamis mengubah ukuran.

364
00:16:15,340 --> 00:16:17,900
>> Jadi di satu sisi Anda mendapatkan
akses acak, yang menakjubkan.

365
00:16:17,900 --> 00:16:20,108
Karena itu mari kita melakukan hal-hal
seperti membagi dan menaklukkan,

366
00:16:20,108 --> 00:16:23,100
pencarian biner, semua yang kita sudah
berbicara tentang pada layar di sini.

367
00:16:23,100 --> 00:16:24,950
Tapi Anda cat sendiri ke sudut.

368
00:16:24,950 --> 00:16:27,810
Segera setelah Anda menekan
akhir array Anda,

369
00:16:27,810 --> 00:16:29,980
Anda harus melakukan yang sangat
operasi yang mahal

370
00:16:29,980 --> 00:16:33,910
atau menulis sejumlah besar kode
sekarang menangani masalah itu.

371
00:16:33,910 --> 00:16:36,680
>> Jadi bagaimana jika sebaliknya kita punya
sesuatu yang disebut daftar,

372
00:16:36,680 --> 00:16:38,820
atau linked list pada khususnya?

373
00:16:38,820 --> 00:16:41,930
Bagaimana jika daripada harus
persegi panjang kembali ke belakang ke belakang,

374
00:16:41,930 --> 00:16:45,730
kami memiliki empat persegi panjang yang meninggalkan sedikit
sedikit ruang gerak di antara mereka?

375
00:16:45,730 --> 00:16:49,670
Dan meskipun aku sudah ditarik ini
gambar atau diadaptasi gambar ini

376
00:16:49,670 --> 00:16:54,696
dari salah satu teks di sini untuk kembali ke
kembali ke belakang sangat tertib, pada kenyataannya,

377
00:16:54,696 --> 00:16:56,820
salah satu persegi panjang
bisa sampai di sini dalam memori.

378
00:16:56,820 --> 00:16:58,028
Salah satunya bisa sampai di sini.

379
00:16:58,028 --> 00:17:00,420
Salah satunya bisa sampai di sini,
di sini, dan sebagainya.

380
00:17:00,420 --> 00:17:02,910
>> Tapi bagaimana kalau kita menarik,
dalam hal ini, panah

381
00:17:02,910 --> 00:17:05,650
yang entah bagaimana menghubungkan ini
persegi panjang bersama-sama?

382
00:17:05,650 --> 00:17:08,170
Memang, kami telah melihat teknis
inkarnasi panah.

383
00:17:08,170 --> 00:17:09,839

384
00:17:09,839 --> 00:17:13,710
Apa yang telah kita digunakan dalam baru-baru ini
hari itu, di bawah tenda,

385
00:17:13,710 --> 00:17:15,210
merupakan perwakilan dari panah?

386
00:17:15,210 --> 00:17:16,290

387
00:17:16,290 --> 00:17:17,349
Sebuah pointer, kan?

388
00:17:17,349 --> 00:17:19,780
>> Jadi bagaimana jika, bukannya
hanya menyimpan angka-angka,

389
00:17:19,780 --> 00:17:23,130
seperti 9, 17, 22, 26, 34,
bagaimana jika kita disimpan tidak

390
00:17:23,130 --> 00:17:27,079
hanya sejumlah tapi pointer
di samping setiap nomor tersebut?

391
00:17:27,079 --> 00:17:30,690
Sehingga banyak seperti Anda akan thread
jarum melalui sejumlah kain,

392
00:17:30,690 --> 00:17:32,950
hal entah bagaimana mengikat
bersama-sama, sama bisa

393
00:17:32,950 --> 00:17:35,550
kita dengan pointer, seperti
menjelma oleh panah di sini,

394
00:17:35,550 --> 00:17:38,550
jenis menenun bersama-sama
ini persegi panjang individu

395
00:17:38,550 --> 00:17:41,780
dengan secara efektif menggunakan pointer
di sebelah setiap nomor yang

396
00:17:41,780 --> 00:17:46,065
menunjuk ke beberapa nomor berikutnya, yang
menunjukkan, pada gilirannya, beberapa nomor berikutnya?

397
00:17:46,065 --> 00:17:47,940
Jadi dengan kata lain, apa yang
jika kita benar-benar ingin

398
00:17:47,940 --> 00:17:49,820
untuk melaksanakan sesuatu seperti ini?

399
00:17:49,820 --> 00:17:53,610
Nah sayangnya, persegi panjang ini,
setidaknya satu dengan 9, 17, 22,

400
00:17:53,610 --> 00:17:57,040
dan sebagainya, ini tidak lagi
kotak bagus dengan nomor tunggal.

401
00:17:57,040 --> 00:17:59,960
Bagian bawah, persegi panjang
di bawah 9, misalnya,

402
00:17:59,960 --> 00:18:04,330
mewakili apa yang harus
menjadi pointer, 32 bit.

403
00:18:04,330 --> 00:18:09,460
Sekarang, aku belum mengetahui adanya tipe data
di C yang memberikan Anda tidak hanya int

404
00:18:09,460 --> 00:18:11,630
tapi pointer sama sekali.

405
00:18:11,630 --> 00:18:15,020
>> Jadi apa solusinya jika kita ingin
menciptakan jawaban kita sendiri untuk ini?

406
00:18:15,020 --> 00:18:15,760
Ya?

407
00:18:15,760 --> 00:18:16,640
>> AUDIENCE: [Tak terdengar]

408
00:18:16,640 --> 00:18:17,360
>> DAVID J. Malan: Apa itu?

409
00:18:17,360 --> 00:18:17,880
>> AUDIENCE: Struktur baru.

410
00:18:17,880 --> 00:18:19,590
>> DAVID J. Malan: Ya, jadi mengapa
kita tidak membuat struktur baru,

411
00:18:19,590 --> 00:18:20,920
atau di C, struct?

412
00:18:20,920 --> 00:18:25,990
Kami telah melihat struct sebelumnya, jika sebentar,
di mana kita berurusan dengan struktur mahasiswa

413
00:18:25,990 --> 00:18:27,780
seperti ini, yang memiliki nama dan rumah.

414
00:18:27,780 --> 00:18:31,980
Dalam PSET 3 breakout Anda menggunakan seluruh
sekelompok GRect structs-- dan GOvals

415
00:18:31,980 --> 00:18:34,810
bahwa Stanford diciptakan untuk
Informasi klaster bersama-sama.

416
00:18:34,810 --> 00:18:38,580
Jadi bagaimana jika kita mengambil ini ide yang sama
kata kunci "typedef" dan "struct,"

417
00:18:38,580 --> 00:18:42,890
dan kemudian beberapa hal spesifik-siswa,
dan berkembang ini menjadi sebagai berikut:

418
00:18:42,890 --> 00:18:46,210
typedef struct node-- dan node
hanya ilmu komputer sangat generik

419
00:18:46,210 --> 00:18:49,980
istilah untuk sesuatu dalam struktur data,
wadah dalam struktur data.

420
00:18:49,980 --> 00:18:53,900
Sebuah node saya mengklaim akan memiliki
n int, benar-benar mudah,

421
00:18:53,900 --> 00:18:58,810
dan kemudian sedikit lebih samar,
baris kedua ini, struct simpul * berikutnya.

422
00:18:58,810 --> 00:19:01,300
Namun dari segi teknis kurang,
apa itu baris kedua

423
00:19:01,300 --> 00:19:02,980
kode dalam kurung kurawal?

424
00:19:02,980 --> 00:19:03,737
Ya?

425
00:19:03,737 --> 00:19:04,851
>> AUDIENCE: [Tak terdengar]

426
00:19:04,851 --> 00:19:06,600
DAVID J. Malan: A
pointer ke node lain.

427
00:19:06,600 --> 00:19:09,910
Jadi memang, sintaks sedikit samar.

428
00:19:09,910 --> 00:19:13,250
Tapi jika Anda membaca secara harfiah,
berikutnya adalah nama variabel.

429
00:19:13,250 --> 00:19:14,410
Apa jenis datanya?

430
00:19:14,410 --> 00:19:18,206
Ini adalah verbose sedikit waktu ini,
tapi itu tipe struct simpul *.

431
00:19:18,206 --> 00:19:22,960
Setiap kali kita telah melihat sesuatu star, yang
berarti itu adalah pointer ke tipe data.

432
00:19:22,960 --> 00:19:26,810
Jadi berikutnya adalah rupanya
pointer ke struct simpul.

433
00:19:26,810 --> 00:19:28,310
>> Sekarang, apa itu struct simpul?

434
00:19:28,310 --> 00:19:31,044
Nah, melihat Anda melihat orang-orang
kata yang sama di kanan atas.

435
00:19:31,044 --> 00:19:33,960
Dan memang, Anda juga melihat kata
"Node" di sini di bagian kiri bawah.

436
00:19:33,960 --> 00:19:35,640
Dan ini sebenarnya hanya kenyamanan.

437
00:19:35,640 --> 00:19:39,930
Perhatikan bahwa dalam definisi mahasiswa
ada kata "mahasiswa" hanya sekali.

438
00:19:39,930 --> 00:19:42,510
Dan itu karena mahasiswa
objek tidak self-referensial.

439
00:19:42,510 --> 00:19:45,340
Tidak ada dalam mahasiswa
yang perlu untuk menunjuk ke siswa lain,

440
00:19:45,340 --> 00:19:45,610
persay.

441
00:19:45,610 --> 00:19:47,630
Itu akan semacam
aneh di dunia nyata.

442
00:19:47,630 --> 00:19:50,880
>> Tapi dengan simpul di terkait
daftar, kita ingin node

443
00:19:50,880 --> 00:19:53,970
menjadi referensial ke objek yang sama.

444
00:19:53,970 --> 00:19:57,900
Dan begitu melihat perubahan di sini tidak
hanya apa yang ada di dalam kurung kurawal.

445
00:19:57,900 --> 00:20:00,800
Tapi kami menambahkan kata "node"
di atas serta

446
00:20:00,800 --> 00:20:02,930
menambahkannya ke bawah
sebagai pengganti "mahasiswa."

447
00:20:02,930 --> 00:20:06,000
Dan ini hanya detail teknis
sehingga, sekali lagi, struktur data Anda

448
00:20:06,000 --> 00:20:11,380
dapat self-referensial, sehingga
node dapat menunjuk ke node lain seperti.

449
00:20:11,380 --> 00:20:13,840
>> Jadi apa ini akhirnya
akan berarti bagi kita?

450
00:20:13,840 --> 00:20:17,560
Nah, satu, hal ini dalam
adalah isi dari simpul kami.

451
00:20:17,560 --> 00:20:19,360
Hal ini di sini,
kanan atas, hanya begitu

452
00:20:19,360 --> 00:20:20,860
itu, sekali lagi, kita bisa lihat diri kita sendiri.

453
00:20:20,860 --> 00:20:23,401
Dan kemudian hal-hal terluar,
meskipun simpul adalah istilah baru,

454
00:20:23,401 --> 00:20:25,500
mungkin, itu masih
sama seperti mahasiswa dan apa

455
00:20:25,500 --> 00:20:27,520
adalah di bawah kap di SPL.

456
00:20:27,520 --> 00:20:31,095
>> Jadi jika sekarang kita ingin memulai
menerapkan linked list ini,

457
00:20:31,095 --> 00:20:33,220
bagaimana mungkin kita menerjemahkan
sesuatu seperti ini untuk kode?

458
00:20:33,220 --> 00:20:35,350
Nah, mari kita melihat
contoh program yang

459
00:20:35,350 --> 00:20:36,840
benar-benar menggunakan linked list.

460
00:20:36,840 --> 00:20:40,870
Di antara kode distribusi hari ini
adalah sebuah program yang disebut Daftar Zero.

461
00:20:40,870 --> 00:20:44,980
Dan jika saya menjalankan ini saya buat super
GUI sederhana, Graphical User Interface,

462
00:20:44,980 --> 00:20:46,460
tapi itu benar-benar hanya printf.

463
00:20:46,460 --> 00:20:50,930
Dan sekarang aku sudah memberikan diriku beberapa menu
options-- Hapus, Insert, Search,

464
00:20:50,930 --> 00:20:51,750
dan Traverse.

465
00:20:51,750 --> 00:20:52,630
Dan Keluar.

466
00:20:52,630 --> 00:20:55,970
Ini adalah operasi hanya umum pada
struktur data yang dikenal sebagai daftar link.

467
00:20:55,970 --> 00:20:58,409
>> Sekarang, Hapus akan
menghapus nomor dari daftar.

468
00:20:58,409 --> 00:21:00,200
Insert akan menambahkan
nomor ke dalam daftar.

469
00:21:00,200 --> 00:21:02,181
Cari akan terlihat
nomor dalam daftar.

470
00:21:02,181 --> 00:21:04,930
Dan melintasi adalah cara mewah
mengatakan, berjalan melalui daftar,

471
00:21:04,930 --> 00:21:06,245
mencetaknya, tapi itu saja.

472
00:21:06,245 --> 00:21:07,720
Jangan mengubahnya dengan cara apapun.

473
00:21:07,720 --> 00:21:08,570
>> Jadi mari kita coba ini.

474
00:21:08,570 --> 00:21:10,160
Mari kita pergi ke depan dan tipe 2.

475
00:21:10,160 --> 00:21:12,710
Dan kemudian aku akan
masukkan nomor tersebut, mengatakan 9.

476
00:21:12,710 --> 00:21:13,620
Enter.

477
00:21:13,620 --> 00:21:17,480
Dan sekarang program saya hanya
diprogram untuk mengatakan, daftar sekarang 9.

478
00:21:17,480 --> 00:21:20,190
Sekarang, jika saya pergi ke depan dan
jangan Masukkan lagi, biarkan

479
00:21:20,190 --> 00:21:23,680
aku pergi ke depan dan zoom out dan ketik 17.

480
00:21:23,680 --> 00:21:25,770
Sekarang daftar saya adalah 9, maka 17.

481
00:21:25,770 --> 00:21:27,750
Jika saya melakukan memasukkan lagi, mari kita melewatkan satu.

482
00:21:27,750 --> 00:21:32,400
Alih-alih 22, sesuai gambar yang kita sudah
telah melihat di sini, biarkan aku melompat ke depan

483
00:21:32,400 --> 00:21:34,630
dan masukkan 26 berikutnya.

484
00:21:34,630 --> 00:21:36,230
Jadi aku akan mengetik 26.

485
00:21:36,230 --> 00:21:37,755
Daftar ini seperti yang saya harapkan.

486
00:21:37,755 --> 00:21:40,630
Tapi sekarang, hanya untuk melihat apakah kode ini
akan menjadi fleksibel, biarkan aku sekarang

487
00:21:40,630 --> 00:21:43,520
Jenis 22, yang setidaknya
konseptual, jika kita

488
00:21:43,520 --> 00:21:46,520
menjaganya agar ini diurutkan, yang memang
akan menjadi tujuan lain sekarang,

489
00:21:46,520 --> 00:21:48,690
harus pergi di antara 17 dan 26.

490
00:21:48,690 --> 00:21:50,270
Jadi saya tekan Enter.

491
00:21:50,270 --> 00:21:51,380
Memang, yang bekerja.

492
00:21:51,380 --> 00:21:54,950
Dan sekarang biarkan aku memasukkan
terakhir, per gambar, 34.

493
00:21:54,950 --> 00:21:55,450
>> Baiklah.

494
00:21:55,450 --> 00:21:58,980
Jadi untuk saat ini biarkan aku menetapkan bahwa
Hapus dan Traverse dan Cari lakukan,

495
00:21:58,980 --> 00:21:59,760
pada kenyataannya, bekerja.

496
00:21:59,760 --> 00:22:04,180
Bahkan, jika saya menjalankan Search, mari kita
mencari nomor 22, Enter.

497
00:22:04,180 --> 00:22:05,010
Ditemukan 22.

498
00:22:05,010 --> 00:22:07,580
Jadi itulah yang ini
Program Daftar Nol tidak.

499
00:22:07,580 --> 00:22:10,230
>> Tapi apa yang sebenarnya terjadi
pada yang menerapkan ini?

500
00:22:10,230 --> 00:22:14,530
Yah, pertama saya mungkin memiliki, dan memang
Saya punya file yang disebut list0.h.

501
00:22:14,530 --> 00:22:16,540

502
00:22:16,540 --> 00:22:20,690
Dan suatu tempat di sana adalah ini
line, typedef, struct node,

503
00:22:20,690 --> 00:22:24,850
maka saya memiliki kawat gigi keriting saya, int n, dan
kemudian struct-- apa definisi?

504
00:22:24,850 --> 00:22:26,530

505
00:22:26,530 --> 00:22:28,545
Struct node berikutnya.

506
00:22:28,545 --> 00:22:29,920

507
00:22:29,920 --> 00:22:31,045
Jadi kita perlu bintang.

508
00:22:31,045 --> 00:22:33,420
Sekarang kita masuk ke teknis
kebiasaan menggambar di sini.

509
00:22:33,420 --> 00:22:35,670
Anda mungkin melihat buku pelajaran dan
referensi online melakukannya di sana.

510
00:22:35,670 --> 00:22:36,660
Ini fungsional setara.

511
00:22:36,660 --> 00:22:37,980
Bahkan, ini sedikit lebih khas.

512
00:22:37,980 --> 00:22:40,563
Tapi aku akan konsisten dengan apa
kami lakukan terakhir kali dan melakukan hal ini.

513
00:22:40,563 --> 00:22:42,350
Dan kemudian terakhir, aku akan melakukan hal ini.

514
00:22:42,350 --> 00:22:45,550
>> Jadi dalam file header
di suatu tempat, di list0.h

515
00:22:45,550 --> 00:22:49,200
hari ini adalah definisi struct ini,
dan mungkin beberapa hal lain.

516
00:22:49,200 --> 00:22:52,580
Sementara itu di list0c ada
akan beberapa hal.

517
00:22:52,580 --> 00:22:54,740
Tapi kita akan hanya
memulai dan tidak selesai ini.

518
00:22:54,740 --> 00:22:59,690
List0.h adalah file yang saya inginkan
untuk menyertakan dalam file C saya.

519
00:22:59,690 --> 00:23:03,910
Dan kemudian di beberapa titik saya
akan memiliki int, utama, membatalkan.

520
00:23:03,910 --> 00:23:06,530
Dan kemudian aku akan
memiliki beberapa agenda di sini.

521
00:23:06,530 --> 00:23:10,620
Saya juga akan memiliki
prototipe seperti batal, search, int,

522
00:23:10,620 --> 00:23:13,610
n, tujuan yang dalam hidup adalah
untuk mencari suatu elemen.

523
00:23:13,610 --> 00:23:18,310
Dan kemudian di sini saya menyatakan di
kode hari ini, batal, pencarian, int, n,

524
00:23:18,310 --> 00:23:21,020
tidak ada titik koma tetapi kurung kurawal terbuka.

525
00:23:21,020 --> 00:23:25,049
Dan sekarang saya ingin entah bagaimana mencari
untuk sebuah elemen dalam daftar ini.

526
00:23:25,049 --> 00:23:27,340
Tapi kita tidak memiliki cukup
informasi di layar belum.

527
00:23:27,340 --> 00:23:29,800
Aku belum benar-benar
mewakili daftar itu sendiri.

528
00:23:29,800 --> 00:23:33,070
Jadi salah satu cara kita bisa menerapkan
linked list dalam program

529
00:23:33,070 --> 00:23:37,520
adalah saya agak ingin melakukan sesuatu
seperti mendeklarasikan linked list di sini.

530
00:23:37,520 --> 00:23:40,520
Untuk mempermudah, saya akan membuat
global ini, meskipun di kita umum

531
00:23:40,520 --> 00:23:41,645
tidak harus melakukan ini terlalu banyak.

532
00:23:41,645 --> 00:23:43,260
Tapi itu akan menyederhanakan contoh ini.

533
00:23:43,260 --> 00:23:45,890
Jadi saya ingin menyatakan
linked list di sini.

534
00:23:45,890 --> 00:23:47,010
Sekarang, bagaimana aku bisa melakukan itu?

535
00:23:47,010 --> 00:23:48,810

536
00:23:48,810 --> 00:23:50,750
>> Berikut gambar dari sebuah linked list.

537
00:23:50,750 --> 00:23:53,030
Dan aku tidak benar-benar
tahu saat ini bagaimana

538
00:23:53,030 --> 00:23:56,710
Aku akan pergi tentang mewakili
begitu banyak hal hanya dengan satu

539
00:23:56,710 --> 00:23:58,040
variabel dalam memori.

540
00:23:58,040 --> 00:23:59,160
Tapi pikirkan kembali sejenak.

541
00:23:59,160 --> 00:24:00,830
Selama ini kami sudah
string, yang kita kemudian

542
00:24:00,830 --> 00:24:02,913
diturunkan menjadi array dari
karakter, yang kita kemudian

543
00:24:02,913 --> 00:24:05,740
diturunkan hanya menjadi pointer
ke karakter pertama

544
00:24:05,740 --> 00:24:08,890
dalam berbagai karakter
yang null diakhiri.

545
00:24:08,890 --> 00:24:13,530
Jadi dengan logika itu, dan dengan ini
jenis gambar pembibitan pikiran Anda,

546
00:24:13,530 --> 00:24:17,964
apa perlu kita benar-benar menulis di kami
kode untuk mewakili sebuah linked list?

547
00:24:17,964 --> 00:24:21,130
Berapa banyak dari informasi ini kita perlu
untuk menangkap dalam kode C, yang akan Anda katakan?

548
00:24:21,130 --> 00:24:22,654

549
00:24:22,654 --> 00:24:23,154
Ya?

550
00:24:23,154 --> 00:24:24,738
>> AUDIENCE: Kita perlu pointer ke node.

551
00:24:24,738 --> 00:24:26,237
DAVID J. Malan: Sebuah pointer ke node.

552
00:24:26,237 --> 00:24:29,320
Secara khusus, yang simpul akan Anda
naluri adalah untuk menyimpan pointer ke?

553
00:24:29,320 --> 00:24:30,026
>> AUDIENCE: The simpul pertama.

554
00:24:30,026 --> 00:24:31,942
>> DAVID J. Malan: Ya,
mungkin hanya yang pertama.

555
00:24:31,942 --> 00:24:34,030
Dan perhatikan, yang pertama
node bentuk yang berbeda.

556
00:24:34,030 --> 00:24:37,690
Ini hanya setengah ukuran struct,
karena memang hanya pointer.

557
00:24:37,690 --> 00:24:44,650
Jadi apa yang Anda benar-benar dapat Anda lakukan adalah menyatakan
linked list untuk menjadi tipe node *.

558
00:24:44,650 --> 00:24:47,780
Dan mari kita sebut dulu
dan menginisialisasi ke null.

559
00:24:47,780 --> 00:24:49,910
Jadi nol, sekali lagi, adalah datang
ke dalam gambar di sini.

560
00:24:49,910 --> 00:24:53,620
Tidak hanya nol digunakan sebagai seperti khusus
nilai kembali untuk hal-hal seperti GetString

561
00:24:53,620 --> 00:24:57,770
dan malloc, null juga nol
pointer, kurangnya pointer,

562
00:24:57,770 --> 00:24:58,430
jika Anda mau.

563
00:24:58,430 --> 00:25:00,309
Ini hanya berarti tidak ada yang belum di sini.

564
00:25:00,309 --> 00:25:02,100
Sekarang pertama, saya bisa saja
disebut apa-apa ini.

565
00:25:02,100 --> 00:25:04,200
Aku bisa menyebutnya "daftar"
atau banyak hal lainnya.

566
00:25:04,200 --> 00:25:06,960
Tapi aku menyebutnya "pertama" sehingga
garis itu dengan gambar ini.

567
00:25:06,960 --> 00:25:10,280
Jadi sama seperti string dapat direpresentasikan
dengan alamat byte pertama,

568
00:25:10,280 --> 00:25:11,280
sehingga dapat linked list.

569
00:25:11,280 --> 00:25:13,480
Dan kita akan melihat data lain
struktur diwakili

570
00:25:13,480 --> 00:25:16,700
dengan hanya satu pointer,
32-bit panah, menunjuk

571
00:25:16,700 --> 00:25:18,740
di node pertama dalam struktur.

572
00:25:18,740 --> 00:25:20,340
>> Tapi sekarang mari kita mengantisipasi masalah.

573
00:25:20,340 --> 00:25:23,230
Jika saya hanya mengingat
dalam program saya alamat

574
00:25:23,230 --> 00:25:27,220
dari node pertama, yang pertama
persegi panjang dalam struktur data,

575
00:25:27,220 --> 00:25:31,760
apa yang lebih baik menjadi kasus tentang
pelaksanaan sisa daftar saya?

576
00:25:31,760 --> 00:25:35,820
Apa detail kunci yang akan
untuk memastikan hal ini benar-benar bekerja?

577
00:25:35,820 --> 00:25:39,250
Dan dengan "benar-benar bekerja" Saya
Maksudku, seperti string,

578
00:25:39,250 --> 00:25:42,180
memungkinkan kita pergi dari karakter pertama
nama Davin untuk kedua,

579
00:25:42,180 --> 00:25:44,755
untuk yang ketiga, untuk
keempat, sampai akhir,

580
00:25:44,755 --> 00:25:47,880
bagaimana kita tahu ketika kita berada di akhir
dari linked list yang terlihat seperti ini?

581
00:25:47,880 --> 00:25:50,035

582
00:25:50,035 --> 00:25:50,660
Ketika itu null.

583
00:25:50,660 --> 00:25:53,640
Dan aku sudah mewakili semacam ini sebagai
seperti kekuatan insinyur listrik,

584
00:25:53,640 --> 00:25:56,420
dengan landasan kecil
simbol, macam.

585
00:25:56,420 --> 00:25:58,246
Tapi itu hanya berarti nol dalam kasus ini.

586
00:25:58,246 --> 00:26:00,370
Anda bisa menggambar sejumlah
cara, namun penulis ini

587
00:26:00,370 --> 00:26:02,800
terjadi untuk menggunakan simbol ini di sini.

588
00:26:02,800 --> 00:26:06,260
>> Selama kita merangkai
semua node ini bersama-sama,

589
00:26:06,260 --> 00:26:08,600
hanya mengingat di mana
yang pertama adalah, begitu lama

590
00:26:08,600 --> 00:26:11,760
seperti yang kita menempatkan simbol khusus di
node yang terakhir dalam daftar,

591
00:26:11,760 --> 00:26:15,130
dan kita akan menggunakan null, karena itulah
apa yang kita miliki tersedia bagi kita,

592
00:26:15,130 --> 00:26:16,480
daftar ini selesai.

593
00:26:16,480 --> 00:26:20,190
Dan bahkan jika saya hanya memberikan pointer ke
elemen pertama, Anda, programmer,

594
00:26:20,190 --> 00:26:22,486
tentu dapat mengakses sisanya.

595
00:26:22,486 --> 00:26:24,360
Tapi mari kita membiarkan pikiran Anda
berjalan sedikit,

596
00:26:24,360 --> 00:26:26,140
jika mereka tidak sudah
cukup wandered-- apa

597
00:26:26,140 --> 00:26:28,723
akan menjadi waktu berjalan dari
menemukan sesuatu dalam daftar ini?

598
00:26:28,723 --> 00:26:30,450

599
00:26:30,450 --> 00:26:33,470
Sialan, itu O besar n,
yang tidak buruk, dalam keadilan.

600
00:26:33,470 --> 00:26:34,800
Tapi itu adalah linear.

601
00:26:34,800 --> 00:26:37,980
Kami sudah menyerah apa fitur
array dengan memindahkan lebih

602
00:26:37,980 --> 00:26:43,130
terhadap gambar ini dinamis
dijalin bersama atau terkait node?

603
00:26:43,130 --> 00:26:44,970

604
00:26:44,970 --> 00:26:46,687
Kami telah memberikan akses acak.

605
00:26:46,687 --> 00:26:48,770
Array bagus karena
matematis segalanya

606
00:26:48,770 --> 00:26:50,340
kembali untuk kembali ke belakang ke belakang.

607
00:26:50,340 --> 00:26:52,370
Meskipun gambar ini
terlihat cantik, dan bahkan

608
00:26:52,370 --> 00:26:55,830
meskipun tampak seperti node ini
baik spasi terpisah, pada kenyataannya

609
00:26:55,830 --> 00:26:56,830
mereka bisa di mana saja.

610
00:26:56,830 --> 00:27:01,590
OX1, Ox50, Ox123, Ox99, ini
node bisa di mana saja.

611
00:27:01,590 --> 00:27:05,960
Karena malloc tidak mengalokasikan memori
dari tumpukan, tetapi di mana saja di tumpukan.

612
00:27:05,960 --> 00:27:09,080
Anda tidak perlu tahu bahwa itu
akan kembali untuk kembali ke belakang.

613
00:27:09,080 --> 00:27:12,460
Jadi gambar ini dalam kenyataannya ini
tidak akan cukup cantik.

614
00:27:12,460 --> 00:27:16,140
>> Jadi itu akan mengambil sedikit
bekerja untuk melaksanakan fungsi ini.

615
00:27:16,140 --> 00:27:17,880
Jadi mari kita menerapkan pencari sekarang.

616
00:27:17,880 --> 00:27:20,250
Dan kita akan melihat semacam
cara cerdas untuk melakukan hal ini.

617
00:27:20,250 --> 00:27:24,660
Jadi jika saya fungsi pencarian dan
Aku diberi variabel, integer n

618
00:27:24,660 --> 00:27:28,490
untuk mencari, saya perlu tahu
sintaks baru untuk mencari di dalam

619
00:27:28,490 --> 00:27:32,400
dari struktur yang
menunjuk, untuk menemukan n.

620
00:27:32,400 --> 00:27:33,210
Jadi mari kita lakukan ini.

621
00:27:33,210 --> 00:27:36,030
>> Jadi pertama aku akan pergi
depan dan menyatakan node *.

622
00:27:36,030 --> 00:27:39,400
Dan aku akan menyebutnya
pointer, hanya dengan konvensi.

623
00:27:39,400 --> 00:27:41,710
Dan aku akan menginisialisasi terlebih dahulu.

624
00:27:41,710 --> 00:27:43,770
Dan sekarang aku bisa melakukan ini
dalam beberapa cara.

625
00:27:43,770 --> 00:27:45,436
Tapi aku akan mengambil pendekatan yang sama.

626
00:27:45,436 --> 00:27:50,180
Sementara pointer tidak sama dengan
null, dan itu sintaks yang valid.

627
00:27:50,180 --> 00:27:54,550
Dan itu hanya berarti melakukan hal berikut, sehingga
Selama Anda tidak menunjuk pada apa-apa.

628
00:27:54,550 --> 00:27:55,800
Apa yang ingin saya lakukan?

629
00:27:55,800 --> 00:28:01,939
>> Jika pointer dot n, biarkan aku kembali
itu, equals-- sama apa?

630
00:28:01,939 --> 00:28:03,105
Apa nilai yang saya cari?

631
00:28:03,105 --> 00:28:04,920

632
00:28:04,920 --> 00:28:06,590
N aktual yang disahkan dalam.

633
00:28:06,590 --> 00:28:09,020
Jadi, inilah fitur lain
C dan banyak bahasa.

634
00:28:09,020 --> 00:28:13,705
Meskipun struktur yang disebut simpul
memiliki n nilai, benar-benar sah

635
00:28:13,705 --> 00:28:17,530
juga memiliki argumen lokal
atau variabel yang disebut n.

636
00:28:17,530 --> 00:28:20,085
Karena bahkan kita, dengan
mata manusia, dapat membedakan

637
00:28:20,085 --> 00:28:22,087
bahwa n ini mungkin
berbeda dari n ini.

638
00:28:22,087 --> 00:28:23,420
Karena sintaks yang berbeda.

639
00:28:23,420 --> 00:28:26,211
Anda punya dot dan pointer,
sedangkan yang satu ini tidak memiliki hal seperti itu.

640
00:28:26,211 --> 00:28:27,290
Jadi ini adalah OK.

641
00:28:27,290 --> 00:28:29,120
Tidak apa-apa untuk memanggil mereka hal yang sama.

642
00:28:29,120 --> 00:28:32,380
>> Kalau aku Anda menemukan ini, aku
akan ingin melakukan sesuatu

643
00:28:32,380 --> 00:28:35,000
seperti mengumumkan bahwa kami menemukan n.

644
00:28:35,000 --> 00:28:37,930
Dan kita akan meninggalkan bahwa sebagai
komentar atau kode pseudo.

645
00:28:37,930 --> 00:28:40,190
Lain, dan inilah
bagian yang menarik, apa yang

646
00:28:40,190 --> 00:28:47,320
yang ingin saya lakukan jika node saat ini
tidak mengandung n yang saya peduli?

647
00:28:47,320 --> 00:28:50,700
Bagaimana cara mencapai berikut ini?

648
00:28:50,700 --> 00:28:53,710
Jika jari saya di
saat ini PTR, dan itu

649
00:28:53,710 --> 00:28:55,920
menunjuk apa pun
pertama menunjuk,

650
00:28:55,920 --> 00:28:59,290
bagaimana cara menggerakkan jari saya
ke node berikutnya dalam kode?

651
00:28:59,290 --> 00:29:01,915
Nah, apa breadcrumb kami
akan mengikuti dalam kasus ini?

652
00:29:01,915 --> 00:29:03,464

653
00:29:03,464 --> 00:29:04,380
AUDIENCE: [Tak terdengar].

654
00:29:04,380 --> 00:29:05,630
DAVID J. Malan: Ya, jadi lain kali.

655
00:29:05,630 --> 00:29:06,640

656
00:29:06,640 --> 00:29:09,824
Jadi jika saya kembali ke saya
kode di sini, memang, aku

657
00:29:09,824 --> 00:29:12,990
akan pergi ke depan dan berkata pointer, yang
hanya variable-- sementara itu

658
00:29:12,990 --> 00:29:15,320
nama yang aneh, ptr, tetapi
itu hanya seperti temp--

659
00:29:15,320 --> 00:29:19,234
Aku akan mengatur pointer
sama dengan apa pun pointer Ini--

660
00:29:19,234 --> 00:29:22,150
dan sekali lagi, ini akan menjadi
sedikit kereta untuk titik moment-- berikutnya.

661
00:29:22,150 --> 00:29:23,551

662
00:29:23,551 --> 00:29:26,550
Dengan kata lain, aku akan mengambil saya
jari yang menunjuk pada simpul ini

663
00:29:26,550 --> 00:29:31,247
di sini dan aku akan berkata, Anda tahu
apa, kita lihat kolom berikutnya

664
00:29:31,247 --> 00:29:33,330
dan gerakkan jari Anda ke
apa pun itu menunjuk.

665
00:29:33,330 --> 00:29:35,163
Dan ini akan
ulangi, ulangi, ulangi.

666
00:29:35,163 --> 00:29:37,630
Tapi ketika melakukan jari saya
berhenti melakukan apa-apa?

667
00:29:37,630 --> 00:29:40,095
Begitu apa baris kode tendangan?

668
00:29:40,095 --> 00:29:40,970
AUDIENCE: [Tak terdengar]

669
00:29:40,970 --> 00:29:43,060
DAVID J. Malan: Jika titik sementara
pointer tidak sama dengan nol.

670
00:29:43,060 --> 00:29:44,900
Di beberapa titik jari saya
akan menunjuk nol

671
00:29:44,900 --> 00:29:47,070
dan aku akan menyadari
itulah akhir dari daftar ini.

672
00:29:47,070 --> 00:29:48,910
Sekarang, ini sedikit
kebohongan putih untuk kesederhanaan.

673
00:29:48,910 --> 00:29:51,580
Ternyata bahwa meskipun kita
hanya belajar notasi dot ini

674
00:29:51,580 --> 00:29:55,220
untuk struktur, pointer tidak struct.

675
00:29:55,220 --> 00:29:56,580
ptr adalah apa?

676
00:29:56,580 --> 00:29:58,350
Hanya untuk menjadi lebih nitpicky.

677
00:29:58,350 --> 00:29:59,720

678
00:29:59,720 --> 00:30:01,360
Ini adalah pointer ke node.

679
00:30:01,360 --> 00:30:03,120
Ini bukan node itu sendiri.

680
00:30:03,120 --> 00:30:06,650
Jika saya tidak punya bintang di sini, pointer
absolutely-- itu node.

681
00:30:06,650 --> 00:30:08,650
Ini seperti satu minggu
deklarasi variabel,

682
00:30:08,650 --> 00:30:10,120
meskipun kata "simpul" yang baru.

683
00:30:10,120 --> 00:30:13,860
>> Tapi segera setelah kami memperkenalkan
Bintang, sekarang pointer ke node.

684
00:30:13,860 --> 00:30:17,960
Dan sayangnya Anda tidak dapat menggunakan
notasi titik untuk pointer.

685
00:30:17,960 --> 00:30:21,070
Anda harus menggunakan panah
notasi, yang, mencolok,

686
00:30:21,070 --> 00:30:23,470
adalah pertama kalinya potongan apapun
sintaksis terlihat intuitif.

687
00:30:23,470 --> 00:30:25,245
Ini benar-benar terlihat seperti anak panah.

688
00:30:25,245 --> 00:30:26,370
Dan itulah hal yang baik.

689
00:30:26,370 --> 00:30:28,995
Dan di sini benar-benar
terlihat seperti anak panah.

690
00:30:28,995 --> 00:30:31,870
Jadi saya pikir itulah la-- saya tidak
pikir aku over-melakukan di sini-aku

691
00:30:31,870 --> 00:30:34,120
pikir itu bagian baru terakhir
sintaksis kita akan melihat.

692
00:30:34,120 --> 00:30:36,500
Dan untungnya, itu memang
sedikit lebih intuitif.

693
00:30:36,500 --> 00:30:40,090
>> Sekarang, bagi anda yang
mungkin lebih suka cara lama,

694
00:30:40,090 --> 00:30:42,550
Anda masih dapat menggunakan notasi titik.

695
00:30:42,550 --> 00:30:45,380
Tapi seperti per Senin
percakapan, pertama-tama kita

696
00:30:45,380 --> 00:30:50,530
perlu untuk pergi ke sana, pergi ke yang
alamat, dan kemudian mengakses lapangan.

697
00:30:50,530 --> 00:30:51,897
Jadi ini juga benar.

698
00:30:51,897 --> 00:30:53,730
Dan terus terang, ini adalah
sedikit lebih bertele-tele.

699
00:30:53,730 --> 00:30:56,530
Kau benar-benar mengatakan, dereference
pointer dan pergi ke sana.

700
00:30:56,530 --> 00:30:59,320
Kemudian ambil .n, lapangan disebut n.

701
00:30:59,320 --> 00:31:01,370
Tapi terus terang, tidak ada yang mau
untuk mengetik atau membaca ini.

702
00:31:01,370 --> 00:31:03,620
Jadi dunia diciptakan
notasi panah, yang

703
00:31:03,620 --> 00:31:06,980
setara, identik,
itu hanya sintaksis gula.

704
00:31:06,980 --> 00:31:10,570
Jadi cara mewah untuk mengatakan ini
terlihat lebih baik, atau terlihat lebih sederhana.

705
00:31:10,570 --> 00:31:12,296
>> Jadi sekarang aku akan melakukan satu hal lain.

706
00:31:12,296 --> 00:31:15,420
Aku akan mengatakan "istirahat" setelah saya sudah
menemukan itu jadi saya tidak terus mencari untuk itu.

707
00:31:15,420 --> 00:31:17,620
Tapi ini intinya
dari fungsi pencarian.

708
00:31:17,620 --> 00:31:21,710
Tapi itu jauh lebih mudah, dalam
end, tidak berjalan melalui kode.

709
00:31:21,710 --> 00:31:25,570
Ini memang pelaksanaan resmi
pencarian dalam kode distribusi hari ini.

710
00:31:25,570 --> 00:31:30,530
Saya berani mengatakan insert yang tidak
terutama menyenangkan untuk berjalan melalui

711
00:31:30,530 --> 00:31:33,180
visual, juga tidak menghapus, bahkan
meskipun pada akhir hari

712
00:31:33,180 --> 00:31:35,460
mereka mendidih hingga cukup
heuristik sederhana.

713
00:31:35,460 --> 00:31:36,330
>> Jadi mari kita lakukan ini.

714
00:31:36,330 --> 00:31:39,250
Jika Anda akan humor saya di sini, saya lakukan
membawa sekelompok bola stres.

715
00:31:39,250 --> 00:31:40,620
Aku membawa sekelompok angka.

716
00:31:40,620 --> 00:31:46,562
Dan bisa kita dapatkan hanya beberapa relawan
untuk mewakili 9, 17, 20, 22, 29, dan 34?

717
00:31:46,562 --> 00:31:48,270
Jadi pada dasarnya semua orang
siapa di sini hari ini.

718
00:31:48,270 --> 00:31:50,170

719
00:31:50,170 --> 00:31:52,760
Itu satu, dua, tiga,
empat, lima, enam orang.

720
00:31:52,760 --> 00:31:55,740
Dan aku telah diminta untuk go-- lihat, tidak ada
satu di belakang menimbulkan tangan mereka.

721
00:31:55,740 --> 00:32:01,910
OK, satu, dua, tiga, empat,
five-- biarkan aku memuat balance-- enam.

722
00:32:01,910 --> 00:32:03,051
OK, Anda enam datang ke atas.

723
00:32:03,051 --> 00:32:04,050
Kita akan membutuhkan orang lain.

724
00:32:04,050 --> 00:32:05,460
Kami membawa bola stres tambahan.

725
00:32:05,460 --> 00:32:08,200
Dan jika Anda bisa, untuk
hanya sesaat, baris

726
00:32:08,200 --> 00:32:10,490
dirimu sendiri hanya
seperti gambar ini di sini.

727
00:32:10,490 --> 00:32:15,200

728
00:32:15,200 --> 00:32:15,959
>> Baiklah.

729
00:32:15,959 --> 00:32:17,125
Mari kita lihat, siapa namamu?

730
00:32:17,125 --> 00:32:17,550
>> AUDIENCE: Andrew.

731
00:32:17,550 --> 00:32:18,800
>> DAVID J. Malan: Andrew,
Anda nomor 9.

732
00:32:18,800 --> 00:32:19,540
Senang bertemu Anda.

733
00:32:19,540 --> 00:32:20,400
Di sini Anda pergi.

734
00:32:20,400 --> 00:32:21,593

735
00:32:21,593 --> 00:32:22,176
AUDIENCE: Jen.

736
00:32:22,176 --> 00:32:22,662
DAVID J. Malan: Jen.

737
00:32:22,662 --> 00:32:23,162
David.

738
00:32:23,162 --> 00:32:23,765
Nomor 17.

739
00:32:23,765 --> 00:32:24,950

740
00:32:24,950 --> 00:32:25,450
Ya?

741
00:32:25,450 --> 00:32:26,400
>> AUDIENCE: Aku Julia.

742
00:32:26,400 --> 00:32:26,980
>> DAVID J. Malan: Julia, David.

743
00:32:26,980 --> 00:32:27,545
Nomor 20.

744
00:32:27,545 --> 00:32:28,507

745
00:32:28,507 --> 00:32:29,340
AUDIENCE: Kristen.

746
00:32:29,340 --> 00:32:30,715
DAVID J. Malan: Kristen, David.

747
00:32:30,715 --> 00:32:31,541
Nomor 22.

748
00:32:31,541 --> 00:32:32,040
Dan?

749
00:32:32,040 --> 00:32:32,649
>> AUDIENCE: JP.

750
00:32:32,649 --> 00:32:33,440
DAVID J. Malan: JP.

751
00:32:33,440 --> 00:32:34,880
Nomor 29.

752
00:32:34,880 --> 00:32:37,080
Jadi pergi ke depan dan mendapatkan in-- Uh oh.

753
00:32:37,080 --> 00:32:38,486

754
00:32:38,486 --> 00:32:38,985
Uh oh.

755
00:32:38,985 --> 00:32:39,650

756
00:32:39,650 --> 00:32:40,150
Standby.

757
00:32:40,150 --> 00:32:41,360

758
00:32:41,360 --> 00:32:42,390
20.

759
00:32:42,390 --> 00:32:43,682
Apakah ada yang punya spidol?

760
00:32:43,682 --> 00:32:44,890
AUDIENCE: Aku punya Sharpie.

761
00:32:44,890 --> 00:32:45,660
DAVID J. Malan: Anda punya Sharpie?

762
00:32:45,660 --> 00:32:46,159
OK.

763
00:32:46,159 --> 00:32:47,577

764
00:32:47,577 --> 00:32:49,160
Dan apakah ada yang punya selembar kertas?

765
00:32:49,160 --> 00:32:51,562

766
00:32:51,562 --> 00:32:52,270
Simpan kuliah.

767
00:32:52,270 --> 00:32:53,810

768
00:32:53,810 --> 00:32:55,362
Ayo.

769
00:32:55,362 --> 00:32:56,320
AUDIENCE: Kita punya itu.

770
00:32:56,320 --> 00:32:57,600
DAVID J. Malan: Kami mendapatkannya?

771
00:32:57,600 --> 00:32:58,577
Baiklah, terima kasih.

772
00:32:58,577 --> 00:33:01,380

773
00:33:01,380 --> 00:33:02,520
Di sini kita pergi.

774
00:33:02,520 --> 00:33:03,582
Apakah ini dari Anda?

775
00:33:03,582 --> 00:33:04,540
Anda hanya menyelamatkan hari.

776
00:33:04,540 --> 00:33:05,670

777
00:33:05,670 --> 00:33:07,220
Jadi 29.

778
00:33:07,220 --> 00:33:10,510

779
00:33:10,510 --> 00:33:11,110
Baiklah.

780
00:33:11,110 --> 00:33:13,360

781
00:33:13,360 --> 00:33:14,890
Saya salah eja 29, tapi OK.

782
00:33:14,890 --> 00:33:15,720
Silakan.

783
00:33:15,720 --> 00:33:18,114
Baiklah, aku akan memberikan
pena Anda kembali sesaat.

784
00:33:18,114 --> 00:33:19,280
Jadi kita memiliki orang-orang ini di sini.

785
00:33:19,280 --> 00:33:20,330
Mari kita memiliki satu lainnya.

786
00:33:20,330 --> 00:33:23,750
Gabe, apakah Anda ingin bermain
elemen pertama di sini?

787
00:33:23,750 --> 00:33:25,705
Kita akan membutuhkan Anda untuk menunjuk
di orang-orang baik.

788
00:33:25,705 --> 00:33:26,930

789
00:33:26,930 --> 00:33:31,030
Jadi 9, 17, 20, 22, mengurutkan
dari 29, dan kemudian 34.

790
00:33:31,030 --> 00:33:32,160

791
00:33:32,160 --> 00:33:33,325
Apakah kita kehilangan seseorang?

792
00:33:33,325 --> 00:33:33,950
Saya punya 34.

793
00:33:33,950 --> 00:33:36,730
Dimana did-- OK, yang ingin menjadi 34?

794
00:33:36,730 --> 00:33:37,605
OK, datang ke atas, 34.

795
00:33:37,605 --> 00:33:39,280

796
00:33:39,280 --> 00:33:41,220
Baiklah, ini akan menjadi
layak klimaks.

797
00:33:41,220 --> 00:33:41,550
Siapa nama Anda?

798
00:33:41,550 --> 00:33:42,040
>> AUDIENCE: Peter.

799
00:33:42,040 --> 00:33:43,456
>> DAVID J. Malan: Peter, ayolah up.

800
00:33:43,456 --> 00:33:46,810
Baiklah, jadi di sini adalah
Seluruh sekelompok node.

801
00:33:46,810 --> 00:33:49,060
Masing-masing kalian merupakan
salah satu persegi panjang ini.

802
00:33:49,060 --> 00:33:51,930
Dan Gabe, sedikit aneh
manusia keluar, mewakili pertama.

803
00:33:51,930 --> 00:33:54,850
Jadi pointer nya sedikit lebih kecil
pada layar daripada orang lain.

804
00:33:54,850 --> 00:33:58,120
Dan dalam hal ini, masing-masing kiri
tangan akan baik titik bawah,

805
00:33:58,120 --> 00:34:01,085
demikian mewakili nol, sehingga
hanya tidak adanya pointer,

806
00:34:01,085 --> 00:34:03,210
atau itu akan menunjuk
pada node di sebelah Anda.

807
00:34:03,210 --> 00:34:05,440
>> Jadi sekarang jika Anda menghiasi
dirimu seperti gambar

808
00:34:05,440 --> 00:34:07,585
di sini, pergi ke depan dan titik
satu sama lain, dengan Gabe

809
00:34:07,585 --> 00:34:11,030
di menunjuk tertentu pada
nomor 9 untuk mewakili daftar.

810
00:34:11,030 --> 00:34:14,050
OK, dan nomor 34, tangan kiri
hanya harus menunjuk lantai.

811
00:34:14,050 --> 00:34:15,750
>> OK, jadi ini adalah linked list.

812
00:34:15,750 --> 00:34:17,580
Jadi ini adalah skenario yang bersangkutan.

813
00:34:17,580 --> 00:34:20,210
Dan memang, ini adalah wakil
dari kelas masalah

814
00:34:20,210 --> 00:34:21,929
bahwa Anda mungkin mencoba untuk memecahkan dengan kode.

815
00:34:21,929 --> 00:34:25,020
Anda ingin akhirnya memasukkan
elemen baru ke dalam daftar.

816
00:34:25,020 --> 00:34:27,494
Dalam hal ini, kita akan
coba memasukkan nomor 55.

817
00:34:27,494 --> 00:34:28,500

818
00:34:28,500 --> 00:34:30,860
Tapi ada akan menjadi
kasus yang berbeda untuk dipertimbangkan.

819
00:34:30,860 --> 00:34:34,409
Dan memang, ini akan menjadi salah satu
dari gambaran besar takeaways di sini, adalah,

820
00:34:34,409 --> 00:34:35,659
apa kasus yang berbeda.

821
00:34:35,659 --> 00:34:39,120
Apa yang berbeda jika kondisi atau
cabang bahwa program Anda mungkin memiliki?

822
00:34:39,120 --> 00:34:42,024
>> Nah, nomor yang Anda coba
insert, yang kita tahu sekarang menjadi 55,

823
00:34:42,024 --> 00:34:44,650
tetapi jika Anda tidak tahu
di muka, aku yakin

824
00:34:44,650 --> 00:34:47,840
jatuh ke setidaknya tiga
kemungkinan situasi.

825
00:34:47,840 --> 00:34:49,717
Dimana mungkin elemen baru itu?

826
00:34:49,717 --> 00:34:51,050
AUDIENCE: Dan akhir atau tengah.

827
00:34:51,050 --> 00:34:54,150
DAVID J. Malan: Pada akhirnya, di
tengah, atau di awal.

828
00:34:54,150 --> 00:34:56,650
Jadi saya mengklaim ada setidaknya
tiga masalah yang perlu kita selesaikan.

829
00:34:56,650 --> 00:34:58,691
Mari kita memilih apa yang mungkin
bisa dibilang sederhana

830
00:34:58,691 --> 00:35:01,090
satu, di mana unsur baru
milik di awal.

831
00:35:01,090 --> 00:35:04,040
Jadi aku akan memiliki kode cukup
seperti mencari, yang saya baru saja menulis.

832
00:35:04,040 --> 00:35:07,670
Dan aku akan memiliki ptr, yang
Aku akan mewakili di sini dengan jari saya,

833
00:35:07,670 --> 00:35:08,370
seperti biasa.

834
00:35:08,370 --> 00:35:12,430
>> Dan ingat, apa nilai
Apakah kita menginisialisasi ptr ke?

835
00:35:12,430 --> 00:35:15,300
Jadi kami diinisialisasi ke null awalnya.

836
00:35:15,300 --> 00:35:16,410

837
00:35:16,410 --> 00:35:19,770
Tapi kemudian apa yang kita lakukan setelah kami
berada di dalam fungsi pencarian kita?

838
00:35:19,770 --> 00:35:20,940

839
00:35:20,940 --> 00:35:24,870
Kami mengaturnya sama dengan dulu,
yang tidak berarti melakukan hal ini.

840
00:35:24,870 --> 00:35:25,890

841
00:35:25,890 --> 00:35:30,570
Jika saya menetapkan ptr sama dengan pertama, apa
harus tanganku benar-benar menunjuk?

842
00:35:30,570 --> 00:35:31,070
Benar.

843
00:35:31,070 --> 00:35:33,290
Jadi jika Gabe dan saya akan
sebagai nilai-nilai yang sama di sini,

844
00:35:33,290 --> 00:35:34,760
kita perlu kedua titik di nomor 9.

845
00:35:34,760 --> 00:35:36,420
>> Jadi ini adalah awal dari cerita kita.

846
00:35:36,420 --> 00:35:38,700
Dan sekarang ini hanya sederhana,
meskipun sintaks baru.

847
00:35:38,700 --> 00:35:40,580
Secara konseptual ini hanya pencarian linear.

848
00:35:40,580 --> 00:35:42,750
Apakah 55 sama dengan 9?

849
00:35:42,750 --> 00:35:45,559
Atau lebih tepatnya, katakanlah kurang dari 9.

850
00:35:45,559 --> 00:35:47,600
Karena saya sedang mencoba untuk
mencari tahu di mana untuk menempatkan 55.

851
00:35:47,600 --> 00:35:51,270
Kurang dari 9, kurang dari 17, kurang
dari 20, kurang dari 22, kurang dari 29,

852
00:35:51,270 --> 00:35:52,510
kurang dari 34, tidak ada.

853
00:35:52,510 --> 00:35:55,080
Jadi sekarang kita dalam kasus
salah satu dari setidaknya tiga.

854
00:35:55,080 --> 00:35:59,910
>> Jika saya ingin memasukkan 55 di sini, apa yang
baris kode perlu dijalankan?

855
00:35:59,910 --> 00:36:01,890
Bagaimana gambaran tentang
manusia harus berubah?

856
00:36:01,890 --> 00:36:03,181
Apa yang harus saya lakukan dengan tangan kiri saya?

857
00:36:03,181 --> 00:36:04,530

858
00:36:04,530 --> 00:36:07,360
Ini harus nol pada awalnya,
karena aku pada akhir daftar.

859
00:36:07,360 --> 00:36:09,318
Dan apa yang harus terjadi
di sini dengan Peter, apakah itu?

860
00:36:09,318 --> 00:36:10,520

861
00:36:10,520 --> 00:36:12,430
Dia jelas akan menunjukkan kepada saya.

862
00:36:12,430 --> 00:36:15,580
Jadi saya mengklaim ada setidaknya dua baris
kode dalam kode contoh dari hari ini

863
00:36:15,580 --> 00:36:18,570
yang akan menerapkan ini
skenario menambahkan 55 di ekor.

864
00:36:18,570 --> 00:36:20,950
Dan bisa saya memiliki seseorang hop
dan hanya mewakili 55?

865
00:36:20,950 --> 00:36:22,200
Baiklah, Anda adalah baru 55.

866
00:36:22,200 --> 00:36:23,580

867
00:36:23,580 --> 00:36:27,054
>> Jadi sekarang bagaimana jika selanjutnya
Skenario datang,

868
00:36:27,054 --> 00:36:29,720
dan kami ingin memasukkan di
awal atau kepala daftar ini?

869
00:36:29,720 --> 00:36:31,100
Dan siapa namamu, nomor 55?

870
00:36:31,100 --> 00:36:31,420
>> AUDIENCE: Jack.

871
00:36:31,420 --> 00:36:32,295
>> DAVID J. Malan: Jack?

872
00:36:32,295 --> 00:36:33,585
OK, senang bertemu Anda.

873
00:36:33,585 --> 00:36:34,210
Welcome aboard.

874
00:36:34,210 --> 00:36:36,640
Jadi sekarang kita akan
menyisipkan, misalnya, nomor 5.

875
00:36:36,640 --> 00:36:39,840
Berikut kasus kedua
tiga kami datang dengan sebelumnya.

876
00:36:39,840 --> 00:36:43,050
Jadi, jika 5 milik di awal,
mari kita lihat bagaimana kita mengetahui hal itu.

877
00:36:43,050 --> 00:36:46,310
Aku menginisialisasi ptr saya
pointer ke nomor 9 lagi.

878
00:36:46,310 --> 00:36:49,140
Dan saya menyadari, oh, 5 kurang dari 9.

879
00:36:49,140 --> 00:36:50,880
Jadi memperbaiki gambar ini untuk kita.

880
00:36:50,880 --> 00:36:54,820
Yang tangannya, Gabe atau David
atau-- apa nama nomor 9 itu?

881
00:36:54,820 --> 00:36:55,740
>> AUDIENCE: Jen.

882
00:36:55,740 --> 00:36:58,406
>> DAVID J. Malan: hands-- Jen
yang tangan kita perlu mengubah?

883
00:36:58,406 --> 00:36:58,905

884
00:36:58,905 --> 00:37:00,970
OK, jadi Gabe poin apa sekarang?

885
00:37:00,970 --> 00:37:01,640
Pada saya.

886
00:37:01,640 --> 00:37:02,750
Saya node baru.

887
00:37:02,750 --> 00:37:04,870
Jadi aku hanya akan jenis bergerak
sini untuk melihat secara visual.

888
00:37:04,870 --> 00:37:06,435
Dan sementara itu apa yang harus saya menunjuk itu?

889
00:37:06,435 --> 00:37:07,910

890
00:37:07,910 --> 00:37:09,020
Masih mana aku menunjuk.

891
00:37:09,020 --> 00:37:10,000
Jadi itu saja.

892
00:37:10,000 --> 00:37:13,717
Jadi hanya benar-benar satu baris kode perbaikan
isu ini, tampaknya.

893
00:37:13,717 --> 00:37:14,800
Baiklah, jadi itu bagus.

894
00:37:14,800 --> 00:37:17,580
Dan bisa seseorang menjadi tempat untuk 5?

895
00:37:17,580 --> 00:37:18,080
Ayo up.

896
00:37:18,080 --> 00:37:20,270

897
00:37:20,270 --> 00:37:21,320
Kami akan membuat Anda waktu berikutnya.

898
00:37:21,320 --> 00:37:24,280
>> Baiklah, jadi sekarang-- dan
sebagai samping, nama-nama

899
00:37:24,280 --> 00:37:28,510
Aku tidak membuat pernyataan tegas dari kanan
sekarang, Kt prediktif brikut pointer, pointer pendahulunya

900
00:37:28,510 --> 00:37:31,260
dan pointer baru, itu
hanya nama yang diberikan

901
00:37:31,260 --> 00:37:35,280
dalam kode contoh ke pointer atau
tangan saya yang agak menunjuk sekitar.

902
00:37:35,280 --> 00:37:36,060
Siapa nama Anda?

903
00:37:36,060 --> 00:37:36,700
>> AUDIENCE: Christine.

904
00:37:36,700 --> 00:37:37,100
>> DAVID J. Malan: Christine.

905
00:37:37,100 --> 00:37:38,090
Welcome aboard.

906
00:37:38,090 --> 00:37:42,180
Baiklah, jadi mari kita pertimbangkan sekarang
skenario yang sedikit lebih menjengkelkan,

907
00:37:42,180 --> 00:37:46,350
dimana saya ingin memasukkan
sesuatu seperti 26 ke dalam ini.

908
00:37:46,350 --> 00:37:47,090
20?

909
00:37:47,090 --> 00:37:47,590
Apa?

910
00:37:47,590 --> 00:37:50,510
Ini are-- hal baik yang kita miliki pena ini.

911
00:37:50,510 --> 00:37:51,955
Baiklah, 20.

912
00:37:51,955 --> 00:37:53,640

913
00:37:53,640 --> 00:37:57,570
Jika seseorang bisa mendapatkan sepotong
kertas siap, hanya dalam case-- baik-baik.

914
00:37:57,570 --> 00:37:58,370
Oh, menarik.

915
00:37:58,370 --> 00:37:59,760

916
00:37:59,760 --> 00:38:02,390
Nah ini adalah contoh
bug kuliah.

917
00:38:02,390 --> 00:38:03,894
OK jadi apa nama Anda lagi?

918
00:38:03,894 --> 00:38:04,560
AUDIENCE: Julia.

919
00:38:04,560 --> 00:38:07,559
DAVID J. Malan: Julia, dapat Anda pop
dan berpura-pura Anda tidak pernah ada?

920
00:38:07,559 --> 00:38:09,040
OK, ini tidak pernah terjadi.

921
00:38:09,040 --> 00:38:09,680
Terima kasih.

922
00:38:09,680 --> 00:38:12,180
Jadi misalkan kita ingin memasukkan
Julia ke linked list ini.

923
00:38:12,180 --> 00:38:13,780
Dia adalah nomor 20.

924
00:38:13,780 --> 00:38:15,530
Dan tentu saja dia
akan termasuk di

925
00:38:15,530 --> 00:38:17,521
begin-- tidak menunjuk pada apa pun.

926
00:38:17,521 --> 00:38:20,020
Jadi tangan Anda bisa menjadi jenis
bawah nol atau nilai sampah.

927
00:38:20,020 --> 00:38:21,210
Mari kita menceritakan kisah cepat.

928
00:38:21,210 --> 00:38:22,980
Aku menunjuk angka 5 saat ini.

929
00:38:22,980 --> 00:38:23,880
Kemudian saya cek 9.

930
00:38:23,880 --> 00:38:25,130
Kemudian saya cek 17.

931
00:38:25,130 --> 00:38:26,247
Kemudian saya cek 22.

932
00:38:26,247 --> 00:38:27,650

933
00:38:27,650 --> 00:38:32,485
Dan saya menyadari, ooh, Julia
perlu untuk pergi sebelum 22.

934
00:38:32,485 --> 00:38:33,580

935
00:38:33,580 --> 00:38:34,660
Jadi apa yang harus terjadi?

936
00:38:34,660 --> 00:38:35,786

937
00:38:35,786 --> 00:38:36,910
Yang tangannya harus berubah?

938
00:38:36,910 --> 00:38:38,360
Julia, tambang, atau--
siapa namamu lagi?

939
00:38:38,360 --> 00:38:39,230
>> AUDIENCE: Kristen.

940
00:38:39,230 --> 00:38:40,060
>> DAVID J. Malan: Kristen atau?

941
00:38:40,060 --> 00:38:40,560
>> AUDIENCE: Andy.

942
00:38:40,560 --> 00:38:40,905
>> DAVID J. Malan: Andy.

943
00:38:40,905 --> 00:38:41,654
Kristen atau Andy?

944
00:38:41,654 --> 00:38:44,280

945
00:38:44,280 --> 00:38:45,690
Andy harus menunjuk?

946
00:38:45,690 --> 00:38:46,780

947
00:38:46,780 --> 00:38:47,341
Julia.

948
00:38:47,341 --> 00:38:47,840
Baiklah.

949
00:38:47,840 --> 00:38:48,960
Jadi Andy, apakah Anda ingin untuk menunjuk Julia?

950
00:38:48,960 --> 00:38:50,120
Tapi tunggu dulu.

951
00:38:50,120 --> 00:38:53,260
Dalam cerita sejauh ini,
Aku semacam satu

952
00:38:53,260 --> 00:38:56,800
yang bertanggung jawab, dalam arti bahwa
pointer adalah hal yang

953
00:38:56,800 --> 00:38:57,850
bergerak melalui daftar.

954
00:38:57,850 --> 00:39:00,800
Kami mungkin memiliki nama untuk Andy, tapi
tidak ada variabel yang disebut Andy.

955
00:39:00,800 --> 00:39:04,320
Satu-satunya variabel lain yang kami miliki adalah
pertama, siapa yang diwakili oleh Gabe.

956
00:39:04,320 --> 00:39:07,690
>> Jadi ini sebenarnya mengapa demikian
jauh kita sudah tidak diperlukan ini.

957
00:39:07,690 --> 00:39:10,846
Tapi sekarang di layar ada
menyebutkan lagi dari pointer pred.

958
00:39:10,846 --> 00:39:11,970
Jadi biarkan aku menjadi lebih eksplisit.

959
00:39:11,970 --> 00:39:14,820
Jika ini adalah pointer, aku lebih baik
mendapatkan sedikit lebih cerdas

960
00:39:14,820 --> 00:39:15,950
tentang iterasi saya.

961
00:39:15,950 --> 00:39:19,580
Jika Anda tidak keberatan saya akan melalui sini
lagi, menunjuk di sini, menunjuk di sini.

962
00:39:19,580 --> 00:39:22,500
Tetapi saya memiliki pointer pred,
pendahulunya pointer, itu

963
00:39:22,500 --> 00:39:24,740
jenis menunjuk pada
Unsur Aku hanya di.

964
00:39:24,740 --> 00:39:27,330
Jadi ketika saya pergi di sini, sekarang
saya update tangan kiri.

965
00:39:27,330 --> 00:39:29,370
Ketika saya pergi di sini update tangan kiriku.

966
00:39:29,370 --> 00:39:33,090
Dan sekarang aku tidak hanya pointer ke
elemen yang pergi setelah Julia,

967
00:39:33,090 --> 00:39:36,300
Saya masih memiliki pointer ke
Andy, elemen sebelumnya.

968
00:39:36,300 --> 00:39:39,430
Jadi Anda memiliki akses, pada dasarnya,
remah roti, jika Anda mau,

969
00:39:39,430 --> 00:39:41,500
untuk semua pointer yang diperlukan.

970
00:39:41,500 --> 00:39:43,710
>> Jadi jika aku tunjuk
Andy dan aku juga menunjuk

971
00:39:43,710 --> 00:39:47,105
di Christian, yang tangannya
sekarang harus menunjuk tempat lain?

972
00:39:47,105 --> 00:39:48,770

973
00:39:48,770 --> 00:39:51,960
Jadi Andy sekarang dapat menunjuk Julia.

974
00:39:51,960 --> 00:39:54,460
Julia kini dapat menunjuk Kristen.

975
00:39:54,460 --> 00:39:56,950
Karena dia dapat menyalin saya
pointer tangan kanan itu.

976
00:39:56,950 --> 00:40:00,044
Dan yang secara efektif menempatkan Anda
kembali ke tempat ini di sini.

977
00:40:00,044 --> 00:40:02,460
Jadi singkatnya, meskipun ini
membawa kita jenis selamanya

978
00:40:02,460 --> 00:40:04,510
untuk benar-benar memperbarui
linked list, menyadari

979
00:40:04,510 --> 00:40:06,580
bahwa operasi
relatif sederhana.

980
00:40:06,580 --> 00:40:10,030
Ini dari satu, dua, tiga
baris kode pada akhirnya.

981
00:40:10,030 --> 00:40:12,780
Tapi melilit mereka
baris kode mungkin

982
00:40:12,780 --> 00:40:16,350
adalah sedikit logika yang efektif
mengajukan pertanyaan, di mana kita?

983
00:40:16,350 --> 00:40:18,970
Apakah kita di awal,
tengah, atau akhir?

984
00:40:18,970 --> 00:40:21,890
>> Sekarang, tentu ada beberapa lainnya
operasi kita mungkin diterapkan.

985
00:40:21,890 --> 00:40:24,880
Dan foto-foto ini di sini hanya menggambarkan
apa yang kita hanya melakukan dengan manusia.

986
00:40:24,880 --> 00:40:26,080
Bagaimana dengan penghapusan?

987
00:40:26,080 --> 00:40:30,650
Jika saya ingin, misalnya,
menghapus nomor 34 atau 55,

988
00:40:30,650 --> 00:40:34,680
Saya mungkin memiliki jenis yang sama dari kode,
tapi aku akan membutuhkan satu atau dua langkah.

989
00:40:34,680 --> 00:40:36,110
Karena Apa yang baru?

990
00:40:36,110 --> 00:40:40,460
Jika saya menghapus seseorang di akhir,
seperti nomor 55 dan kemudian 34,

991
00:40:40,460 --> 00:40:42,995
apa juga harus berubah seperti yang saya lakukan itu?

992
00:40:42,995 --> 00:40:44,870
Aku harus tidak evict--
siapa namamu lagi?

993
00:40:44,870 --> 00:40:45,380
>> AUDIENCE: Jack.

994
00:40:45,380 --> 00:40:46,255
>> DAVID J. Malan: Jack.

995
00:40:46,255 --> 00:40:49,770
Aku harus tidak hanya evict-- gratis Jack,
sehingga benar-benar panggilan gratis Jack, atau setidaknya

996
00:40:49,770 --> 00:40:53,530
pointer di sana juga, tapi sekarang
apa yang perlu diubah dengan Peter?

997
00:40:53,530 --> 00:40:55,510
Tangannya lebih baik mulai mengarah ke bawah.

998
00:40:55,510 --> 00:40:59,300
Karena begitu saya sebut gratis di
Jack, jika Petrus masih menunjuk Jack

999
00:40:59,300 --> 00:41:02,530
dan karena itu saya terus melintasi
daftar dan akses pointer ini,

1000
00:41:02,530 --> 00:41:05,650
saat itulah teman segmentasi lama kita
kesalahan mungkin benar-benar menendang.

1001
00:41:05,650 --> 00:41:07,860
Karena kita telah diberi
memori kembali ke Jack.

1002
00:41:07,860 --> 00:41:10,760
>> Anda dapat tinggal di sana
canggung untuk sesaat.

1003
00:41:10,760 --> 00:41:13,410
Karena kita memiliki hanya beberapa
operasi akhir untuk dipertimbangkan.

1004
00:41:13,410 --> 00:41:15,600
Melepaskan kepala daftar,
atau beginning-- dan satu ini

1005
00:41:15,600 --> 00:41:16,349
sedikit mengganggu.

1006
00:41:16,349 --> 00:41:19,640
Karena kita harus tahu bahwa Gabe
adalah jenis khusus dalam program ini.

1007
00:41:19,640 --> 00:41:21,440
Karena memang, ia memiliki pointer sendiri.

1008
00:41:21,440 --> 00:41:24,860
Dia tidak hanya menjadi menunjuk,
seperti hampir semua orang di sini.

1009
00:41:24,860 --> 00:41:28,112
>> Jadi, ketika kepala daftar adalah
dihapus, yang tangannya harus berubah sekarang?

1010
00:41:28,112 --> 00:41:29,070
Siapa nama Anda lagi?

1011
00:41:29,070 --> 00:41:29,450
>> AUDIENCE: Christine.

1012
00:41:29,450 --> 00:41:31,408
>> DAVID J. Malan: Aku mengerikan
pada nama, rupanya.

1013
00:41:31,408 --> 00:41:34,011
Jadi Christine dan Gabe,
yang tangannya perlu mengubah

1014
00:41:34,011 --> 00:41:36,510
ketika kita mencoba untuk menghapus Christine,
nomor 5, dari gambar?

1015
00:41:36,510 --> 00:41:37,550

1016
00:41:37,550 --> 00:41:38,820
OK, jadi mari kita lakukan Gabe.

1017
00:41:38,820 --> 00:41:40,950
Gabe akan menunjuk,
mungkin, di nomor 9.

1018
00:41:40,950 --> 00:41:42,230

1019
00:41:42,230 --> 00:41:44,642
Tapi apa yang selanjutnya harus terjadi?

1020
00:41:44,642 --> 00:41:46,600
AUDIENCE: Christine harus
null [Tak terdengar].

1021
00:41:46,600 --> 00:41:50,244
DAVID J. Malan: OK, kita harus mungkin
make-- Aku mendengar "null" di suatu tempat.

1022
00:41:50,244 --> 00:41:51,410
AUDIENCE: Null dan bebas nya.

1023
00:41:51,410 --> 00:41:51,855
DAVID J. Malan: Null apa?

1024
00:41:51,855 --> 00:41:53,074
AUDIENCE: Null dan bebas nya.

1025
00:41:53,074 --> 00:41:54,490
DAVID J. Malan: Null dan bebas nya.

1026
00:41:54,490 --> 00:41:55,422
Jadi ini sangat mudah.

1027
00:41:55,422 --> 00:41:58,380
Dan itu sempurna bahwa Anda sekarang semacam
berdiri di sana, tidak memiliki.

1028
00:41:58,380 --> 00:42:00,430
Karena Anda sudah
dipisahkan dari daftar.

1029
00:42:00,430 --> 00:42:02,820
Kau sudah efektif
yatim piatu dari daftar.

1030
00:42:02,820 --> 00:42:07,770
Jadi kita lebih baik panggilan gratis sekarang
Christine untuk memberikan memori yang kembali.

1031
00:42:07,770 --> 00:42:10,240
Jika setiap kali kita
menghapus node dari daftar

1032
00:42:10,240 --> 00:42:14,230
kita mungkin akan membuat daftar
pendek, tetapi tidak benar-benar menurun

1033
00:42:14,230 --> 00:42:15,096
ukuran dalam memori.

1034
00:42:15,096 --> 00:42:17,720
Dan jadi jika kita terus menambahkan dan
menambahkan, menambahkan hal-hal ke dalam daftar,

1035
00:42:17,720 --> 00:42:19,280
komputer saya mungkin akan lebih lambat
dan lebih lambat dan lebih lambat,

1036
00:42:19,280 --> 00:42:21,740
karena aku kehabisan
memori, bahkan jika aku tidak benar-benar

1037
00:42:21,740 --> 00:42:25,580
menggunakan byte Christine
memori lagi.

1038
00:42:25,580 --> 00:42:28,500
>> Jadi pada akhirnya ada yang lain
skenario, penghapusan course--

1039
00:42:28,500 --> 00:42:30,640
di tengah, penghapusan
di akhir, seperti yang kita lihat.

1040
00:42:30,640 --> 00:42:32,348
Tapi yang lebih menarik
Tantangan saat ini adalah

1041
00:42:32,348 --> 00:42:34,770
akan mempertimbangkan persis
apa waktu berjalan adalah.

1042
00:42:34,770 --> 00:42:36,640
Jadi tidak hanya bisa Anda tetap Anda
potongan kertas, jika, Gabe,

1043
00:42:36,640 --> 00:42:38,640
Anda tidak akan keberatan memberikan
semua orang bola stres.

1044
00:42:38,640 --> 00:42:42,100
Terima kasih banyak untuk linked list kami
relawan di sini, jika Anda bisa.

1045
00:42:42,100 --> 00:42:45,320
>> [Tepuk Tangan]

1046
00:42:45,320 --> 00:42:46,700
>> DAVID J. Malan: Baiklah.

1047
00:42:46,700 --> 00:42:51,110
Jadi beberapa analisis
pertanyaan kemudian, jika aku bisa.

1048
00:42:51,110 --> 00:42:59,670
Kami telah melihat notasi ini sebelumnya,
O besar dan omega, batas atas

1049
00:42:59,670 --> 00:43:02,520
dan batas bawah pada
waktu berjalan beberapa algoritma.

1050
00:43:02,520 --> 00:43:04,950
Jadi mari kita pertimbangkan hanya
beberapa pertanyaan.

1051
00:43:04,950 --> 00:43:07,090
>> Satu, dan kami mengatakan itu
sebelumnya, apa yang sedang berjalan

1052
00:43:07,090 --> 00:43:10,647
waktu pencarian untuk
daftar dalam hal O besar?

1053
00:43:10,647 --> 00:43:13,480
Apakah yang dimaksud dengan batas atas yang sedang berjalan
saat mencari sebuah linked list

1054
00:43:13,480 --> 00:43:16,340
seperti yang diterapkan oleh relawan kami di sini?

1055
00:43:16,340 --> 00:43:17,820
Ini O besar n, linier.

1056
00:43:17,820 --> 00:43:20,630
Karena dalam kasus terburuk,
elemen, seperti 55,

1057
00:43:20,630 --> 00:43:23,830
kita mungkin akan mencari mungkin di mana
Jack, semua jalan di akhir.

1058
00:43:23,830 --> 00:43:28,250
Dan sayangnya, tidak seperti array
kita tidak bisa mendapatkan mewah saat ini.

1059
00:43:28,250 --> 00:43:31,820
Meskipun semua manusia kami yang
diurutkan dari elemen-elemen kecil, 5,

1060
00:43:31,820 --> 00:43:35,900
sepanjang jalan sampai ke elemen yang lebih besar,
55, yang biasanya hal yang baik.

1061
00:43:35,900 --> 00:43:38,815
Tapi apa asumsi bahwa
tidak lagi memungkinkan kita untuk melakukan?

1062
00:43:38,815 --> 00:43:39,775

1063
00:43:39,775 --> 00:43:40,650
AUDIENCE: [Tak terdengar]

1064
00:43:40,650 --> 00:43:40,920
DAVID J. Malan: Katakanlah lagi?

1065
00:43:40,920 --> 00:43:41,800
AUDIENCE: Akses Acak.

1066
00:43:41,800 --> 00:43:43,049
DAVID J. Malan: Random access.

1067
00:43:43,049 --> 00:43:46,330
Dan pada gilirannya itu berarti kita tidak bisa
lagi menggunakan angka nol yang lemah, intuisi,

1068
00:43:46,330 --> 00:43:49,365
dan kejelasan menggunakan biner
Cari dan membagi dan menaklukkan.

1069
00:43:49,365 --> 00:43:51,240
Karena meskipun kami
manusia bisa jelas

1070
00:43:51,240 --> 00:43:54,610
melihat bahwa Andy atau Kristen yang
kira-kira di tengah-tengah daftar,

1071
00:43:54,610 --> 00:43:57,670
kita hanya tahu bahwa sebagai
komputer dengan menggelapkan daftar

1072
00:43:57,670 --> 00:43:59,029
dari awal.

1073
00:43:59,029 --> 00:44:00,570
Jadi kita sudah menyerah bahwa akses acak.

1074
00:44:00,570 --> 00:44:04,380
>> O begitu besar dari n sekarang adalah atas
terikat pada waktu pencarian kami.

1075
00:44:04,380 --> 00:44:07,920
Bagaimana omega pencarian kita?

1076
00:44:07,920 --> 00:44:11,535
Apa batas bawah pada pencarian
untuk beberapa nomor dalam daftar ini?

1077
00:44:11,535 --> 00:44:12,410
AUDIENCE: [Tak terdengar]

1078
00:44:12,410 --> 00:44:13,040
DAVID J. Malan: Katakanlah lagi?

1079
00:44:13,040 --> 00:44:13,420
AUDIENCE: Satu.

1080
00:44:13,420 --> 00:44:13,800
DAVID J. Malan: Satu.

1081
00:44:13,800 --> 00:44:14,760
Jadi waktu konstan.

1082
00:44:14,760 --> 00:44:17,020
Dalam kasus terbaik, Christine adalah
memang pada awal daftar.

1083
00:44:17,020 --> 00:44:19,020
Dan kami sedang mencari
nomor 5, jadi kami menemukannya.

1084
00:44:19,020 --> 00:44:19,787
Jadi bukan masalah besar.

1085
00:44:19,787 --> 00:44:22,370
Tapi dia harus berada di
awal dari daftar dalam kasus ini.

1086
00:44:22,370 --> 00:44:23,745
Bagaimana sesuatu seperti Hapus?

1087
00:44:23,745 --> 00:44:24,717

1088
00:44:24,717 --> 00:44:26,300
Bagaimana jika Anda ingin menghapus elemen?

1089
00:44:26,300 --> 00:44:29,200
Apa batas atas dan batas bawah
tentang penghapusan sesuatu dari terkait

1090
00:44:29,200 --> 00:44:29,699
daftar?

1091
00:44:29,699 --> 00:44:35,195

1092
00:44:35,195 --> 00:44:36,070
AUDIENCE: [Tak terdengar]

1093
00:44:36,070 --> 00:44:36,420
DAVID J. Malan: Katakanlah lagi?

1094
00:44:36,420 --> 00:44:37,067
AUDIENCE: n.

1095
00:44:37,067 --> 00:44:38,900
DAVID J. Malan: n adalah
memang batas atas.

1096
00:44:38,900 --> 00:44:41,700
Karena dalam kasus terburuk kami mencoba
untuk menghapus Jack, seperti baru saja kita lakukan.

1097
00:44:41,700 --> 00:44:43,050
Dia semua jalan di akhir.

1098
00:44:43,050 --> 00:44:45,419
Membawa kita selamanya, atau
n langkah-langkah untuk menemukannya.

1099
00:44:45,419 --> 00:44:46,460
Jadi itulah batas atas.

1100
00:44:46,460 --> 00:44:47,430
Itu linear, yakin.

1101
00:44:47,430 --> 00:44:50,970
Dan kasus terbaik waktu berjalan, atau
batas bawah dalam kasus terbaik

1102
00:44:50,970 --> 00:44:51,975
akan waktu yang konstan.

1103
00:44:51,975 --> 00:44:54,600
Karena mungkin kita mencoba untuk menghapus
Christine, dan kami hanya beruntung

1104
00:44:54,600 --> 00:44:55,558
dia di awal.

1105
00:44:55,558 --> 00:44:56,350
Sekarang tunggu sebentar.

1106
00:44:56,350 --> 00:44:59,370
Gabe juga di awal,
dan kami juga harus memperbarui Gabe.

1107
00:44:59,370 --> 00:45:01,150
Jadi itu bukan hanya satu langkah.

1108
00:45:01,150 --> 00:45:04,210
Jadi, apakah itu memang konstan
waktu, dalam kasus terbaik,

1109
00:45:04,210 --> 00:45:06,345
untuk menghapus elemen terkecil?

1110
00:45:06,345 --> 00:45:07,360

1111
00:45:07,360 --> 00:45:10,960
Hal ini, meskipun mungkin dua,
tiga, atau bahkan 100 baris kode,

1112
00:45:10,960 --> 00:45:14,000
jika jumlah yang sama
garis, tidak dalam beberapa lingkaran,

1113
00:45:14,000 --> 00:45:16,577
dan independen dari ukuran
dari daftar, benar-benar.

1114
00:45:16,577 --> 00:45:18,660
Menghapus elemen pada
awal daftar,

1115
00:45:18,660 --> 00:45:21,940
bahkan jika kita harus berurusan dengan
Gabe, masih waktu yang konstan.

1116
00:45:21,940 --> 00:45:24,220
>> Jadi ini tampaknya seperti
Langkah besar mundur.

1117
00:45:24,220 --> 00:45:27,000
Dan apa buang-buang waktu
jika, dalam satu minggu dan minggu

1118
00:45:27,000 --> 00:45:30,250
nol kita tidak hanya
kode pseudo tetapi kode aktual

1119
00:45:30,250 --> 00:45:35,780
untuk menerapkan sesuatu yang log
dasar n, atau log, lebih tepatnya, dari n, basis 2,

1120
00:45:35,780 --> 00:45:37,150
dalam hal waktu yang berjalan.

1121
00:45:37,150 --> 00:45:40,710
Jadi mengapa sih akan kita ingin memulai
menggunakan sesuatu seperti sebuah linked list?

1122
00:45:40,710 --> 00:45:41,517
Ya.

1123
00:45:41,517 --> 00:45:44,022
>> AUDIENCE: Jadi Anda dapat menambahkan
elemen ke array.

1124
00:45:44,022 --> 00:45:46,230
DAVID J. Malan: Jadi Anda bisa
menambahkan elemen ke array.

1125
00:45:46,230 --> 00:45:47,550
Dan ini juga adalah tematik.

1126
00:45:47,550 --> 00:45:49,740
Dan kita akan terus melihat
ini, ini trade-off, banyak

1127
00:45:49,740 --> 00:45:51,573
seperti kita telah melihat
trade-off dengan merge sort.

1128
00:45:51,573 --> 00:45:54,606
Kami benar-benar bisa mempercepat
pencarian atau pengurutan, lebih tepatnya,

1129
00:45:54,606 --> 00:45:57,480
jika kita menghabiskan sedikit lebih banyak ruang dan
memiliki potongan tambahan memori

1130
00:45:57,480 --> 00:45:58,760
atau sebuah array untuk merge sort.

1131
00:45:58,760 --> 00:46:01,270
Tapi kita menghabiskan lebih banyak
ruang, tapi kami menghemat waktu.

1132
00:46:01,270 --> 00:46:04,820
Dalam hal ini, kami tidak
memberikan waktu tapi kami

1133
00:46:04,820 --> 00:46:08,170
mendapatkan fleksibilitas,
dinamisme jika Anda mau,

1134
00:46:08,170 --> 00:46:10,280
yang ini bisa dibilang fitur yang positif.

1135
00:46:10,280 --> 00:46:11,520
>> Kami juga menghabiskan ruang.

1136
00:46:11,520 --> 00:46:13,710
Dalam arti adalah terkait
daftar lebih mahal

1137
00:46:13,710 --> 00:46:15,700
dalam hal ruang dari array?

1138
00:46:15,700 --> 00:46:18,379

1139
00:46:18,379 --> 00:46:19,920
Dimana ruang ekstra berasal?

1140
00:46:19,920 --> 00:46:20,460
Ya?

1141
00:46:20,460 --> 00:46:21,800
>> AUDIENCE: [Tak terdengar] pointer.

1142
00:46:21,800 --> 00:46:23,310
>> DAVID J. Malan: Ya, kami
juga memiliki pointer.

1143
00:46:23,310 --> 00:46:25,560
Jadi ini minorly menjengkelkan
di yang tidak lagi am

1144
00:46:25,560 --> 00:46:27,780
Aku menyimpan hanya int
untuk mewakili int.

1145
00:46:27,780 --> 00:46:30,990
Aku menyimpan sebuah int dan
pointer, yang juga 32 bit.

1146
00:46:30,990 --> 00:46:33,470
Jadi aku benar-benar dua kali lipat
jumlah ruang yang terlibat.

1147
00:46:33,470 --> 00:46:36,040
Jadi itu adalah trade-off, namun
itu dalam kasus int.

1148
00:46:36,040 --> 00:46:39,580
Misalkan Anda tidak menyimpan int,
tapi kira setiap persegi panjang tersebut

1149
00:46:39,580 --> 00:46:43,290
atau masing-masing manusia ini mewakili
kata, kata dalam bahasa Inggris yang

1150
00:46:43,290 --> 00:46:46,430
mungkin lima karakter, 10
karakter, bahkan mungkin lebih.

1151
00:46:46,430 --> 00:46:49,940
Kemudian menambahkan hanya 32 bit lebih
mungkin kurang dari masalah besar.

1152
00:46:49,940 --> 00:46:52,160
>> Bagaimana jika masing-masing siswa
dalam demonstrasi

1153
00:46:52,160 --> 00:46:55,107
secara harfiah struct mahasiswa yang
memiliki nama dan rumah dan mungkin

1154
00:46:55,107 --> 00:46:57,065
nomor telepon dan Twitter
menangani dan sejenisnya.

1155
00:46:57,065 --> 00:46:59,564
Jadi semua bidang kita mulai
berbicara tentang hari,

1156
00:46:59,564 --> 00:47:02,410
apalagi dari masalah besar karena
node kami mendapatkan lebih menarik

1157
00:47:02,410 --> 00:47:05,972
dan besar untuk belanja, eh, tambahan
pointer hanya untuk menghubungkan mereka bersama-sama.

1158
00:47:05,972 --> 00:47:07,180
Tapi memang, itu adalah trade-off.

1159
00:47:07,180 --> 00:47:09,560
Dan memang, kode ini
lebih kompleks, seperti yang Anda akan

1160
00:47:09,560 --> 00:47:11,770
melihat dengan menggelapkan melalui
bahwa contoh tertentu.

1161
00:47:11,770 --> 00:47:14,302
Tapi bagaimana jika ada
beberapa grail suci sini.

1162
00:47:14,302 --> 00:47:17,010
Bagaimana jika kita tidak mengambil langkah
mundur tapi langkah besar ke depan

1163
00:47:17,010 --> 00:47:19,180
dan menerapkan data
struktur melalui mana kita

1164
00:47:19,180 --> 00:47:22,870
dapat menemukan unsur-unsur seperti Jack atau
Christine atau unsur-unsur lain

1165
00:47:22,870 --> 00:47:25,870
dalam array ini dalam waktu yang konstan benar?

1166
00:47:25,870 --> 00:47:26,920
Cari konstan.

1167
00:47:26,920 --> 00:47:28,320
Hapus konstan.

1168
00:47:28,320 --> 00:47:29,570
Insert konstan.

1169
00:47:29,570 --> 00:47:32,260
Semua operasi ini adalah konstan.

1170
00:47:32,260 --> 00:47:33,750
Itu akan menjadi grail suci kita.

1171
00:47:33,750 --> 00:47:36,690
Dan itulah di mana kami
akan mengambil waktu berikutnya.

1172
00:47:36,690 --> 00:47:38,600
Sampai jumpa.

1173
00:47:38,600 --> 00:47:39,371