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

2
00:00:00,500 --> 00:00:11,137
[MUZIK bermain]

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 lima minggu berterusan, dan kita
mempunyai beberapa berita baik dan ada berita buruk.

6
00:00:18,560 --> 00:00:21,140
Jadi berita baik ialah CS50
melancarkan Jumaat ini.

7
00:00:21,140 --> 00:00:24,430
Jika anda ingin menyertai kami,
menuju ke URL yang biasa di sini.

8
00:00:24,430 --> 00:00:28,670
Berita yang lebih baik, tidak ada kuliah
ini Isnin ke-13 akan datang.

9
00:00:28,670 --> 00:00:31,970
Kurang sedikit berita yang lebih baik,
kuiz sifar adalah Rabu depan.

10
00:00:31,970 --> 00:00:33,840
Maklumat lanjut boleh
didapati di URL ini di sini.

11
00:00:33,840 --> 00:00:36,340
Dan sejak beberapa hari akan datang
kami akan mengisi tempat kosong

12
00:00:36,340 --> 00:00:39,234
berkaitan dengan bilik-bilik
bahawa kita akan terpelihara.

13
00:00:39,234 --> 00:00:41,400
Berita yang lebih baik adalah bahawa ada akan
menjadi kajian kursus seluruh

14
00:00:41,400 --> 00:00:43,570
sesi akan datang
Isnin petang.

15
00:00:43,570 --> 00:00:46,270
Tunggu untuk kursus ini
laman web untuk lokasi dan butiran.

16
00:00:46,270 --> 00:00:49,290
Bahagian, walaupun ia adalah satu
bercuti, 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 Jumaat depan.

19
00:00:52,940 --> 00:00:56,220
Jadi ini adalah satu tradisi kita
mempunyai, seperti sukatan pelajaran.

20
00:00:56,220 --> 00:00:58,100
Just-- ia akan menjadi luar biasa.

21
00:00:58,100 --> 00:01:02,510
Anda akan melihat perkara-perkara seperti
struktur data pemalar masa

22
00:01:02,510 --> 00:01:04,730
dan jadual hash dan pokok-pokok dan cuba.

23
00:01:04,730 --> 00:01:07,150
Dan kita akan bercakap mengenai masalah hari jadi.

24
00:01:07,150 --> 00:01:09,440
A sejumlah besar barangan
menanti Jumaat 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 bahawa kita telah
memberi tumpuan kepada gambar ini daripada apa yang

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

30
00:01:18,980 --> 00:01:22,875
Jadi memori atau RAM adalah di mana program-program
wujud semasa anda berjalan mereka.

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

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

33
00:01:27,520 --> 00:01:30,430
ia dimuatkan dari keras anda
memandu atau pemacu keadaan pepejal

34
00:01:30,430 --> 00:01:34,190
ke dalam RAM, Random Access Memory, di mana
ia hidup sehingga kuasa terpadam,

35
00:01:34,190 --> 00:01:36,700
penutup komputer riba ditutup,
atau anda berhenti program ini.

36
00:01:36,700 --> 00:01:38,960
>> Sekarang memori itu, daripada
yang anda mungkin mempunyai

37
00:01:38,960 --> 00:01:41,950
1 gigabyte hari ini, 2
gigabait, malah banyak lagi,

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

39
00:01:44,420 --> 00:01:47,170
dalam jenis ini segi empat tepat
model konsep

40
00:01:47,170 --> 00:01:50,860
mana kita mempunyai stack di bahagian bawah
dan mempunyai banyak barangan lain di bahagian atas.

41
00:01:50,860 --> 00:01:53,140
Perkara di bahagian paling atas
kita lihat pada gambar ini

42
00:01:53,140 --> 00:01:55,670
sebelum ini tetapi tidak pernah bercakap tentang
adalah segmen teks yang kononnya.

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

44
00:01:58,419 --> 00:02:01,150
mengarang program sebenar anda disusun.

45
00:02:01,150 --> 00:02:03,910
>> Oleh itu, apabila anda klik dua kali
Microsoft Word pada Mac atau PC anda,

46
00:02:03,910 --> 00:02:08,030
atau apabila anda menjalankan dot mengurangkan Mario pada
Komputer Linux di tetingkap terminal anda,

47
00:02:08,030 --> 00:02:12,460
sifar dan orang-orang yang mendirikan
Perkataan atau Mario disimpan sementara

48
00:02:12,460 --> 00:02:16,610
dalam RAM komputer anda dalam apa yang dikenali sebagai
segmen teks untuk sesuatu program.

49
00:02:16,610 --> 00:02:19,080
Di bawah yang pergi dimulakan
dan data tidak diisytiharkan.

50
00:02:19,080 --> 00:02:22,655
Ini adalah barangan seperti pembolehubah global,
bahawa kami telah tidak digunakan banyak,

51
00:02:22,655 --> 00:02:24,910
tetapi kadang-kadang kita kena
mempunyai pembolehubah global

52
00:02:24,910 --> 00:02:28,819
atau statik tali yang ditakrifkan
adalah keras berkod kata-kata seperti "hello"

53
00:02:28,819 --> 00:02:31,860
yang tidak diambil daripada pengguna
yang keras berkod ke dalam program anda.

54
00:02:31,860 --> 00:02:34,230
>> Sekarang, ke bawah di bahagian bawah kita
mempunyai timbunan yang dipanggil.

55
00:02:34,230 --> 00:02:37,665
Dan tindanan, setakat ini, kita telah
menggunakan untuk apa jenis tujuan?

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

57
00:02:39,706 --> 00:02:40,997
Apa yang tindanan telah digunakan untuk?

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

59
00:02:41,160 --> 00:02:42,070
>> PENONTON: 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 apa rasa untuk fungsi?

62
00:02:44,980 --> 00:02:48,660
>> PENONTON: Apabila anda memanggil fungsi, yang
hujah-hujah yang disalin ke dalam tindanan.

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

64
00:02:49,660 --> 00:02:52,650
Apabila anda memanggil fungsi, yang
hujah-hujah yang disalin ke dalam tindanan.

65
00:02:52,650 --> 00:02:56,330
Jadi mana-mana X atau Y atau A atau B
bahawa anda lulus ke fungsi

66
00:02:56,330 --> 00:02:58,680
buat sementara waktu memakai
timbunan yang dipanggil,

67
00:02:58,680 --> 00:03:02,000
seperti salah satu daripada Annenberg
dulang dewan makan, dan juga perkara-perkara

68
00:03:02,000 --> 00:03:03,190
seperti pembolehubah tempatan.

69
00:03:03,190 --> 00:03:06,290
Jika fungsi foo atau swap anda
fungsi mempunyai pembolehubah tempatan,

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

71
00:03:08,602 --> 00:03:11,560
Sekarang, kita tidak akan bercakap terlalu banyak tentang
mereka, tetapi ini pembolehubah persekitaran

72
00:03:11,560 --> 00:03:15,690
di bahagian bawah yang kita lihat tadi apabila
Saya futzing di papan kekunci satu hari

73
00:03:15,690 --> 00:03:20,050
dan saya mula mengakses perkara
seperti argv 100 atau argv 1,000,

74
00:03:20,050 --> 00:03:22,320
hanya elements-- saya terlupa
yang numbers-- tetapi

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

76
00:03:24,330 --> 00:03:26,581
Kami mula melihat beberapa
Simbol funky pada skrin.

77
00:03:26,581 --> 00:03:28,330
Mereka itulah yang dipanggil
pembolehubah persekitaran

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

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

80
00:03:37,090 --> 00:03:39,670
Shellshock, itu menjadi
yang melanda cukup beberapa komputer.

81
00:03:39,670 --> 00:03:42,960
>> Sekarang akhir sekali, tumpuan hari ini
kita akhirnya akan berada di timbunan itu.

82
00:03:42,960 --> 00:03:44,864
Ini merupakan satu lagi sebahagian daripada ingatan.

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

84
00:03:47,030 --> 00:03:48,040
Ia perkakasan yang sama.

85
00:03:48,040 --> 00:03:49,956
Kami hanya semacam
merawat kelompok yang berbeza

86
00:03:49,956 --> 00:03:51,460
daripada bait untuk tujuan yang berlainan.

87
00:03:51,460 --> 00:03:56,540
Timbunan itu juga akan menjadi di mana
pembolehubah dan memori yang anda meminta

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

89
00:03:58,810 --> 00:04:01,890
>> Tetapi ada jenis masalah
di sini, kerana gambar bermakna.

90
00:04:01,890 --> 00:04:05,261
Kami jenis mempunyai dua
kapal akan berlanggar.

91
00:04:05,261 --> 00:04:08,010
Kerana seperti anda menggunakan lebih dan lebih
tepi, dan seperti yang kita lihat hari ini

92
00:04:08,010 --> 00:04:11,800
seterusnya, kerana anda menggunakan lebih banyak dan lebih daripada
timbunan, sesungguhnya perkara-perkara buruk mungkin berlaku.

93
00:04:11,800 --> 00:04:15,054
Dan sesungguhnya, kita boleh menyebabkan bahawa
sengaja atau tidak sengaja.

94
00:04:15,054 --> 00:04:16,970
Jadi cliffhanger yang lalu
masa adalah program ini,

95
00:04:16,970 --> 00:04:20,570
yang tidak memenuhi mana-mana fungsi
tujuan selain daripada untuk menunjukkan

96
00:04:20,570 --> 00:04:24,750
bagaimana anda sebagai lelaki yang tidak baik sebenarnya boleh mengambil
kelebihan pepijat dalam program seseorang

97
00:04:24,750 --> 00:04:28,460
dan mengambil alih program ataupun
sistem komputer keseluruhan atau pelayan.

98
00:04:28,460 --> 00:04:31,660
Jadi hanya untuk pandangan secara ringkas, anda
notis utama yang di bahagian bawah

99
00:04:31,660 --> 00:04:34,510
mengambil dalam baris arahan
hujah, seperti argv.

100
00:04:34,510 --> 00:04:38,480
Dan ia mempunyai panggilan kepada fungsi f,
asasnya fungsi bernama dipanggil

101
00:04:38,480 --> 00:04:40,250
f, dan ia lulus dalam argv [1].

102
00:04:40,250 --> 00:04:43,960
>> Jadi apa sahaja perkataan jenis pengguna dalam sekurang-
segera selepas nama ini program ini,

103
00:04:43,960 --> 00:04:49,310
dan kemudian fungsi ini sewenang-wenangnya sehingga
atas, f, mengambil dalam tali, AKA char *,

104
00:04:49,310 --> 00:04:51,720
seperti yang kita telah mula berbincang,
dan ia hanya panggilan "bar."

105
00:04:51,720 --> 00:04:53,310
Tetapi kita boleh memanggilnya apa-apa.

106
00:04:53,310 --> 00:04:57,470
Dan kemudian ia menyatakan, di dalam
f, pelbagai watak

107
00:04:57,470 --> 00:04:59,930
dipanggil c-- 12 aksara tersebut.

108
00:04:59,930 --> 00:05:03,580
>> Kini, dengan kisah yang saya memberitahu
masa yang lalu, di mana dalam ingatan

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

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

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

112
00:05:08,070 --> 00:05:08,590
>> PENONTON: Pada tindanan.

113
00:05:08,590 --> 00:05:09,420
>> DAVID J. MALAN: Pada tindanan.

114
00:05:09,420 --> 00:05:10,720
Jadi c adalah pembolehubah tempatan.

115
00:05:10,720 --> 00:05:14,079
Kami meminta 12 aksara atau 12 bait.

116
00:05:14,079 --> 00:05:16,120
Mereka akan berakhir
pada timbunan yang dipanggil.

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

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

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

120
00:05:21,550 --> 00:05:25,200
Ini bermakna tali menyalin, tetapi
hanya n huruf, n aksara.

121
00:05:25,200 --> 00:05:31,990
Jadi n aksara akan
disalin dari bar ke dalam 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 dalam erti kata lain, yang
satu baris, strncopy,

125
00:05:36,330 --> 00:05:39,500
akan menyalin
berkesan ke bar di c.

126
00:05:39,500 --> 00:05:42,340
>> Sekarang, hanya untuk jenis menjangka
moral 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
Walaupun kami memeriksa panjang
bar dan lulus ke strncopy,

129
00:05:49,710 --> 00:05:53,145
apa yang usus anda memberitahu anda adalah
masih dipecahkan mengenai program ini?

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

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

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

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

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

135
00:06:02,073 --> 00:06:04,810
mempunyai begitu banyak sebagai campur 1 untuk
menempatkan bahawa watak null.

136
00:06:04,810 --> 00:06:06,649
Tetapi ia lebih teruk daripada 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
Yeah?

139
00:06:08,432 --> 00:06:09,307
>> PENONTON: [didengar]

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 keras berkod 12 cukup sewenang-wenangnya.

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

144
00:06:19,497 --> 00:06:21,330
Yang tidak begitu banyak yang
masalah, tetapi hakikatnya

145
00:06:21,330 --> 00:06:25,630
bahawa kita tidak memeriksa jika
panjang bar adalah kurang daripada 12,

146
00:06:25,630 --> 00:06:28,530
di mana ia akan menjadi
selamat untuk meletakkan ia ke dalam ingatan

147
00:06:28,530 --> 00:06:30,260
c dipanggil bahawa kami telah diperuntukkan.

148
00:06:30,260 --> 00:06:32,960
Malah, jika bar adalah seperti
20 aksara,

149
00:06:32,960 --> 00:06:39,010
fungsi ini kelihatan menyalin
20 aksara dari bar ke dalam c, dengan itu

150
00:06:39,010 --> 00:06:41,310
mengambil sekurang-kurangnya 8 bytes
bahawa ia tidak harus.

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

152
00:06:42,690 --> 00:06:44,347
>> Jadi ringkasnya program, patah.

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

154
00:06:45,180 --> 00:06:46,360
Mungkin anda mendapat kesalahan segmentasi.

155
00:06:46,360 --> 00:06:47,651
Kami semua mempunyai pepijat dalam program.

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

157
00:06:50,196 --> 00:06:51,320
Tetapi apa yang implikasi?

158
00:06:51,320 --> 00:06:54,390
Nah, di sini adalah versi yang dizum dalam daripada
bahawa gambar memori komputer saya.

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

160
00:06:56,230 --> 00:06:59,644
Dan sesungguhnya, di bahagian paling bawah adalah apa yang
dipanggil timbunan rutin ibu bapa, cara mewah

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

162
00:07:00,560 --> 00:07:03,772
Supaya sesiapa yang dipanggil fungsi
f yang kita bercakap tentang.

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

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

165
00:07:06,640 --> 00:07:08,810
Ia sentiasa berada di sana,
sentiasa di dalam gambar itu.

166
00:07:08,810 --> 00:07:10,440
Kami tidak pernah menarik perhatian kepadanya.

167
00:07:10,440 --> 00:07:15,290
Kerana ia ternyata cara c kerja-kerja adalah
bahawa apabila satu fungsi panggilan yang lain,

168
00:07:15,290 --> 00:07:18,780
tidak sahaja hujah-hujah dengan
fungsi dapat ditolak ke tepi,

169
00:07:18,780 --> 00:07:22,470
bukan sahaja melakukan tempatan fungsi ini
pembolehubah dapat ditolak ke tepi,

170
00:07:22,470 --> 00:07:26,820
sesuatu yang dipanggil alamat kembali
juga mendapat diletakkan ke dalam tindanan.

171
00:07:26,820 --> 00:07:33,330
Secara khusus, jika panggilan utama foo, yang utama
alamat sendiri dalam ingatan, lembu sesuatu,

172
00:07:33,330 --> 00:07:38,240
berkesan mendapat meletakkan ke dalam tindanan
supaya apabila f dilakukan menyempurnakannya

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

174
00:07:43,630 --> 00:07:47,760
>> Jadi, jika kita di sini dari segi konsep,
dalam utama, kemudian f mendapat dipanggil.

175
00:07:47,760 --> 00:07:50,200
Bagaimana f tahu yang
dengan kawalan tangan kembali?

176
00:07:50,200 --> 00:07:52,020
Nah, ini sedikit
nota singkat yang berwarna merah di sini,

177
00:07:52,020 --> 00:07:54,978
dipanggil alamat kembali, ia hanya
cek, apa yang alamat kembali?

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

179
00:07:57,039 --> 00:07:59,080
Dan itu sedikit
daripada melampaui batas satu,

180
00:07:59,080 --> 00:08:00,750
kerana sifar dan orang-orang
utama adalah untuk teknikal

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

182
00:08:01,967 --> 00:08:03,800
Tetapi itu idea. f
hanya perlu tahu apa yang

183
00:08:03,800 --> 00:08:06,680
di mana kawalan akhirnya kembali.

184
00:08:06,680 --> 00:08:09,790
>> Tetapi cara komputer
telah lama diletakkan perkara

185
00:08:09,790 --> 00:08:12,320
seperti pembolehubah tempatan dan
hujah-hujah seperti ini.

186
00:08:12,320 --> 00:08:17,180
Jadi di bahagian atas gambar ini di
biru bingkai tindanan untuk f, sehingga semua

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

188
00:08:19,630 --> 00:08:22,990
Jadi dengan itu, notis yang
bar adalah dalam gambar ini.

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

190
00:08:23,980 --> 00:08:27,240
Dan kita mendakwa hujah untuk
fungsi mendapatkan ditolak ke dalam tindanan.

191
00:08:27,240 --> 00:08:29,910
Dan c, sudah tentu, adalah
juga di dalam gambar ini.

192
00:08:29,910 --> 00:08:33,520
>> Dan hanya untuk tujuan notasi,
notis di bahagian atas sudut kiri sebelah

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

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

195
00:08:38,220 --> 00:08:41,240
Jadi dalam erti kata lain, anda boleh bayangkan
bahawa ada grid bytes

196
00:08:41,240 --> 00:08:44,380
di sana, pertama yang
kiri atas, bahagian bawah yang

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

198
00:08:48,360 --> 00:08:49,930
>> Tetapi sekarang cuba untuk maju pantas.

199
00:08:49,930 --> 00:08:55,580
Apa yang akan berlaku jika kita lulus
di bar tali itu lebih lama daripada c?

200
00:08:55,580 --> 00:08:59,130
Dan kami tidak memeriksa jika
ia memang lebih lama daripada 12.

201
00:08:59,130 --> 00:09:03,146
Bahagian manakah gambar ini akan
mendapatkan ditulis ganti dengan bait 0, 1, 2, 3,

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

203
00:09:07,890 --> 00:09:11,820
Apa yang akan berlaku di sini,
jika anda membuat kesimpulan dari pesanan

204
00:09:11,820 --> 00:09:14,790
yang c kurungan 0 adalah di atas
dan c pendakap 11 adalah semacam turun

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

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

207
00:09:16,796 --> 00:09:19,260
>> PENONTON: Nah, ia akan
untuk menulis semula bar char *.

208
00:09:19,260 --> 00:09:22,260
>> DAVID J. MALAN: Ya, ia kelihatan seperti
anda akan menulis ganti * bar char.

209
00:09:22,260 --> 00:09:26,245
Dan lebih teruk lagi, jika anda menghantar dalam benar-benar panjang
rentetan, anda mungkin menulis ganti apa?

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

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

212
00:09:28,570 --> 00:09:31,380
Yang sekali lagi mereka adalah seperti yang
nota singkat untuk memberitahu program di mana

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

214
00:09:34,060 --> 00:09:37,140
>> Jadi apa yang orang jahat biasanya melakukan
adalah jika mereka mencari satu program yang

215
00:09:37,140 --> 00:09:41,290
bahawa mereka ingin tahu sama ada adalah
eksploitasi, kereta dalam apa-apa cara yang

216
00:09:41,290 --> 00:09:43,550
bahawa dia boleh mengambil
kelebihan pepijat itu,

217
00:09:43,550 --> 00:09:45,720
biasanya mereka tidak mendapat
hak ini kali pertama.

218
00:09:45,720 --> 00:09:48,590
Mereka hanya mula menghantar, misalnya,
tali rawak ke dalam program anda,

219
00:09:48,590 --> 00:09:50,260
sama ada di papan kekunci,
atau terus-terang mereka mungkin

220
00:09:50,260 --> 00:09:52,740
menulis program kecil hanya
secara automatik menjana tali,

221
00:09:52,740 --> 00:09:55,430
dan mula terhantuk pada program anda dengan
menghantar banyak input yang berbeza

222
00:09:55,430 --> 00:09:56,340
di panjang yang berbeza.

223
00:09:56,340 --> 00:09:58,990
>> Sebaik sahaja crash program anda,
itulah satu perkara yang menakjubkan.

224
00:09:58,990 --> 00:10:01,020
Kerana ia bermakna dia
atau dia telah menemui

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

226
00:10:02,660 --> 00:10:05,830
Dan kemudian mereka boleh mendapatkan lebih banyak pandai
dan mula memberi tumpuan lebih sempit

227
00:10:05,830 --> 00:10:07,420
bagaimana untuk mengeksploitasi pepijat itu.

228
00:10:07,420 --> 00:10:11,480
Khususnya, apa yang dia mungkin
lakukan adalah menghantar, dalam kes ini, hello.

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

230
00:10:12,210 --> 00:10:14,750
Ia rentetan itu cukup pendek.

231
00:10:14,750 --> 00:10:18,100
Tetapi bagaimana jika dia menghantar,
dan kami akan umum sebagai,

232
00:10:18,100 --> 00:10:20,890
serangan code-- jadi sifar
dan orang-orang yang melakukan perkara-perkara

233
00:10:20,890 --> 00:10:25,150
seperti rm-rf, yang mengeluarkan segala-galanya
dari cakera keras atau menghantar 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 setiap satu daripada
huruf A hanya mewakili,

236
00:10:29,570 --> 00:10:32,380
dari segi konsep, serangan, serangan,
serangan, serangan, beberapa kod buruk

237
00:10:32,380 --> 00:10:36,410
bahawa orang lain telah menulis, tetapi
jika orang yang bijak

238
00:10:36,410 --> 00:10:40,790
bukan sahaja merangkumi semua
dari orang-rm-RFS, tetapi juga

239
00:10:40,790 --> 00:10:46,100
mempunyai nya beberapa bait lepas
menjadi nombor yang sepadan

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

241
00:10:50,540 --> 00:10:53,820
bahawa dia meninggal dalam hanya
dengan menyediakan ia pada yang cepat,

242
00:10:53,820 --> 00:10:58,760
anda berkesan boleh menipu komputer
ke perasan apabila f dilakukan melaksanakan,

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

244
00:11:02,400 --> 00:11:06,070
Tetapi kerana dia mempunyai entah bagaimana
bertindan bahawa alamat kembali

245
00:11:06,070 --> 00:11:09,602
dengan nombor mereka sendiri,
dan mereka bijak

246
00:11:09,602 --> 00:11:11,560
telah dikonfigurasikan yang
nombor untuk merujuk, kerana anda

247
00:11:11,560 --> 00:11:13,740
lihat di bahagian atas super
sudut kiri sebelah sana,

248
00:11:13,740 --> 00:11:18,020
alamat sebenar dalam komputer ini
memori beberapa kod serangan mereka,

249
00:11:18,020 --> 00:11:21,740
lelaki yang tidak baik boleh menipu komputer
dalam melaksanakan kod sendiri.

250
00:11:21,740 --> 00:11:23,700
>> Dan kod yang, sekali lagi, boleh jadi apa sahaja.

251
00:11:23,700 --> 00:11:26,120
Ia biasanya dipanggil
kod shell, yang hanya

252
00:11:26,120 --> 00:11:29,030
cara untuk mengatakan bahawa ia bukan
biasanya sesuatu yang mudah seperti rm-rf.

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

254
00:11:32,340 --> 00:11:37,230
atau kawalan perancangan beliau untuk melaksanakan
apa sahaja yang mereka mahu.

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

256
00:11:40,210 --> 00:11:44,490
bahawa bug ini tidak terlibat memeriksa
sempadan array anda.

257
00:11:44,490 --> 00:11:47,250
Dan kerana cara
komputer kerja adalah bahawa mereka

258
00:11:47,250 --> 00:11:49,430
menggunakan tindanan dari
berkesan dari segi konsep,

259
00:11:49,430 --> 00:11:54,830
bawah pada, tetapi kemudian unsur-unsur
anda menolak ke dalam tindanan berkembang atas ke bawah,

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

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

262
00:11:58,290 --> 00:12:00,800
Dan terus-terang, terdapat bahasa
dengan yang bekerja di sekitar ini.

263
00:12:00,800 --> 00:12:03,100
Java adalah imun, misalnya,
dengan isu ini khususnya.

264
00:12:03,100 --> 00:12:04,110
Oleh kerana 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 kuasa ini bahawa kita mempunyai
menyentuh apa-apa dalam memori

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

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

269
00:12:12,430 --> 00:12:14,596
Jika, terus-terang, pada bulan-bulan
atau tahun akan datang, bila-bila masa

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

271
00:12:17,740 --> 00:12:22,370
jika anda pernah melihat tanda-tanda bahawa sesuatu
seperti serangan buffer overflow,

272
00:12:22,370 --> 00:12:25,390
atau timbunan limpahan adalah jenis lain
serangan, sama dalam semangat,

273
00:12:25,390 --> 00:12:28,770
sebanyak memberi inspirasi kepada laman web ini
menamakan, jika anda tahu,

274
00:12:28,770 --> 00:12:33,170
itu semua bercakap tentang hanya
melimpah saiz beberapa watak

275
00:12:33,170 --> 00:12:36,200
pelbagai atau beberapa pelbagai amnya.

276
00:12:36,200 --> 00:12:38,822
Apa-apa soalan, maka, pada ini?

277
00:12:38,822 --> 00:12:39,780
Jangan cuba 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 setakat ini baru kami
rakan dalam kita dapat memperuntukkan memori

281
00:12:47,270 --> 00:12:50,540
bahawa kita tidak semestinya kenal
memajukan yang kita mahu jadi kami tidak mempunyai

282
00:12:50,540 --> 00:12:52,920
untuk kod keras ke kami
nombor program seperti 12.

283
00:12:52,920 --> 00:12:55,550
Apabila pengguna memberitahu kita berapa banyak
data dia mahu input,

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

285
00:12:58,000 --> 00:13:01,484
>> Jadi malloc ternyata, kepada
sejauh mana kita telah menggunakannya,

286
00:13:01,484 --> 00:13:03,900
jelas masa lalu, dan kemudian
kalian telah menggunakannya

287
00:13:03,900 --> 00:13:08,160
untuk getstring tidak sedar untuk
beberapa minggu, kesemua memori malloc ini

288
00:13:08,160 --> 00:13:09,820
datang dari timbunan itu kononnya.

289
00:13:09,820 --> 00:13:13,852
Dan ini adalah mengapa getstring, misalnya,
boleh memperuntukkan memori dinamik

290
00:13:13,852 --> 00:13:16,060
tanpa mengetahui apa yang anda
akan menaip terlebih dahulu,

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

292
00:13:21,520 --> 00:13:24,080
walaupun selepas getstring pulangan.

293
00:13:24,080 --> 00:13:27,450
Kerana ingat selepas semua bahawa
stack sentiasa naik dan turun,

294
00:13:27,450 --> 00:13:27,950
naik dan turun.

295
00:13:27,950 --> 00:13:30,230
Dan sebaik sahaja ia pergi
ke bawah, ini bermakna apa-apa memori

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

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

298
00:13:34,570 --> 00:13:36,120
>> Tetapi timbunan itu di sini.

299
00:13:36,120 --> 00:13:39,360
Dan apa yang baik tentang malloc ialah
apabila malloc memperuntukkan memori di sini,

300
00:13:39,360 --> 00:13:42,070
ia tidak memberi kesan, untuk
kebanyakan keadaan, oleh tindanan.

301
00:13:42,070 --> 00:13:46,000
Dan apa-apa fungsi boleh mengakses
memori yang telah malloc'd,

302
00:13:46,000 --> 00:13:49,120
walaupun oleh fungsi seperti getstring,
walaupun selepas ia dikembalikan.

303
00:13:49,120 --> 00:13:51,700
>> Sekarang, akas bagi malloc adalah percuma.

304
00:13:51,700 --> 00:13:53,900
Dan sesungguhnya, peraturan yang anda
perlu mula mengguna pakai

305
00:13:53,900 --> 00:13:58,950
apa-apa, mana-mana, bila-bila masa anda menggunakan malloc
anda sendiri mesti menggunakan percuma, akhirnya,

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

307
00:14:00,280 --> 00:14:03,289
Selama ini kami telah menulis
kereta, kod kereta, kerana banyak sebab.

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

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

310
00:14:09,010 --> 00:14:11,410
Bila-bila masa anda dipanggil getstring
sejak beberapa minggu yang lalu

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

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
amalan, sesuatu yang baik.

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

315
00:14:20,330 --> 00:14:22,900
adalah semua tentang membantu anda
kini mendapati pepijat seperti itu.

316
00:14:22,900 --> 00:14:27,060
Tetapi bersyukur untuk Serangga 4 anda tidak perlu
untuk menggunakan perpustakaan CS50 atau getstring.

317
00:14:27,060 --> 00:14:31,220
Jadi apa-apa bug yang berkaitan dengan ingatan adalah
akhirnya akan menjadi anda sendiri.

318
00:14:31,220 --> 00:14:34,060
>> Jadi malloc adalah lebih daripada hanya
sesuai bagi maksud ini.

319
00:14:34,060 --> 00:14:37,420
Kita boleh sebenarnya kini menyelesaikan
masalah berbeza,

320
00:14:37,420 --> 00:14:41,640
dan asasnya menyelesaikan masalah yang lebih
berkesan seperti janji minggu sifar.

321
00:14:41,640 --> 00:14:44,720
Setakat ini adalah paling seksi yang
struktur data kami mempunyai.

322
00:14:44,720 --> 00:14:47,804
Dan oleh struktur data saya hanya bermakna
cara memori konsepnya,

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

324
00:14:50,720 --> 00:14:52,930
Kita boleh mula perkara kelompok bersama-sama.

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

326
00:14:54,460 --> 00:14:57,270
Dan apa yang penting dalam kira-kira
array adalah bahawa ia memberi anda

327
00:14:57,270 --> 00:14:59,724
back-to-back ketulan
memori, setiap yang

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

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

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

331
00:15:04,496 --> 00:15:06,570
Ini misalnya, adalah
pelbagai saiz enam.

332
00:15:06,570 --> 00:15:10,650
Katakan anda mengisi pelbagai ini dengan enam
nombor dan kemudian, atas apa jua sebab,

333
00:15:10,650 --> 00:15:13,187
pengguna anda mahu memberikan
anda beberapa ketujuh.

334
00:15:13,187 --> 00:15:14,020
Di mana anda meletakkannya?

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

336
00:15:15,490 --> 00:15:18,990
>> Apakah penyelesaian jika anda mempunyai
mencipta array pada timbunan,

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

338
00:15:22,030 --> 00:15:23,730
kurungan persegi dengan beberapa di dalam?

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

340
00:15:25,160 --> 00:15:27,260
Nah, anda telah mendapat enam
nombor dalam kotak-kotak.

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

342
00:15:28,530 --> 00:15:29,973
Di mana anda akan mahu untuk meletakkan ia?

343
00:15:29,973 --> 00:15:30,860
>> PENONTON: [didengar]

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

345
00:15:31,315 --> 00:15:32,380
>> PENONTON: Letakkan ia pada akhirnya.

346
00:15:32,380 --> 00:15:33,796
>> DAVID J. MALAN: Letakkan ia pada akhirnya.

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

348
00:15:35,880 --> 00:15:38,710
Yang akan menjadi baik, tetapi ia
ternyata anda tidak boleh berbuat demikian.

349
00:15:38,710 --> 00:15:41,350
Kerana jika anda tidak meminta
untuk sebahagian ini ingatan,

350
00:15:41,350 --> 00:15:44,490
ia boleh menjadi secara kebetulan bahawa ini
sedang digunakan oleh beberapa pemboleh ubah lain

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

352
00:15:45,030 --> 00:15:49,210
Fikirkan kembali seminggu atau jadi apabila kita meletakkan
keluar Zamyla dan Davin dan Gabe itu nama-nama

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

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

355
00:15:51,638 --> 00:15:53,550
Oleh itu, kita tidak boleh semestinya
mempercayai bahawa apa sahaja yang

356
00:15:53,550 --> 00:15:55,800
di sini boleh didapati dengan saya untuk digunakan.

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

358
00:15:56,990 --> 00:16:00,282
Nah, sekali anda menyedari
memerlukan pelbagai saiz tujuh,

359
00:16:00,282 --> 00:16:02,490
anda hanya boleh membuat
pelbagai saiz tujuh kemudian gunakan

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

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

362
00:16:09,680 --> 00:16:12,130
Tetapi itu bukan terutamanya cekap.

363
00:16:12,130 --> 00:16:15,340
Pendek kata, tatasusunan jangan biarkan
anda secara dinamik mengubah saiz.

364
00:16:15,340 --> 00:16:17,900
>> Maka pada satu tangan anda
akses rawak, yang luar biasa.

365
00:16:17,900 --> 00:16:20,108
Kerana ia membolehkan kita melakukan perkara-perkara
seperti pecah dan,

366
00:16:20,108 --> 00:16:23,100
carian binari, semua yang kita kena
bercakap pada skrin di sini.

367
00:16:23,100 --> 00:16:24,950
Tetapi anda mengecat diri anda ke satu sudut.

368
00:16:24,950 --> 00:16:27,810
Sebaik sahaja anda melanda
akhir array anda,

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

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

371
00:16:33,910 --> 00:16:36,680
>> Jadi apa jika sebaliknya kita mempunyai
sesuatu yang dinamakan senarai,

372
00:16:36,680 --> 00:16:38,820
atau senarai dikaitkan khususnya?

373
00:16:38,820 --> 00:16:41,930
Bagaimana jika daripada harus
segi empat tepat belakang untuk kembali ke belakang,

374
00:16:41,930 --> 00:16:45,730
kita mempunyai segi empat tepat yang meninggalkan sedikit
sedikit bilik hal bergoyang di antara mereka?

375
00:16:45,730 --> 00:16:49,670
Dan walaupun saya telah disediakan ini
gambar atau disesuaikan gambar ini

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

377
00:16:54,696 --> 00:16:56,820
salah satu segi empat tepat
boleh di sini dalam ingatan.

378
00:16:56,820 --> 00:16:58,028
Salah seorang daripada mereka boleh di sini.

379
00:16:58,028 --> 00:17:00,420
Salah seorang daripada mereka boleh di sini,
di sini, dan sebagainya.

380
00:17:00,420 --> 00:17:02,910
>> Tetapi bagaimana jika kita menarik,
dalam kes ini, anak panah

381
00:17:02,910 --> 00:17:05,650
yang entah bagaimana menghubungkan ini
segi empat tepat bersama-sama?

382
00:17:05,650 --> 00:17:08,170
Sesungguhnya, yang kita lihat teknikal
penjelmaan anak panah.

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

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

385
00:17:13,710 --> 00:17:15,210
mewakili anak panah?

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

387
00:17:16,290 --> 00:17:17,349
Penunjuk A, bukan?

388
00:17:17,349 --> 00:17:19,780
>> Jadi apa jika, bukannya
hanya menyimpan nombor,

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

390
00:17:23,130 --> 00:17:27,079
hanya sebilangan tetapi penunjuk
di sebelah setiap nombor itu?

391
00:17:27,079 --> 00:17:30,690
Supaya sama seperti anda akan benang yang
jarum melalui sejumlah besar kain,

392
00:17:30,690 --> 00:17:32,950
perkara yang entah bagaimana mengikat
bersama-sama, juga boleh

393
00:17:32,950 --> 00:17:35,550
kami dengan petunjuk, sebagai
dijelmakan oleh anak panah di sini,

394
00:17:35,550 --> 00:17:38,550
jenis menenun bersama-sama
segi empat tepat ini individu

395
00:17:38,550 --> 00:17:41,780
dengan berkesan menggunakan penunjuk
di sebelah setiap nombor yang

396
00:17:41,780 --> 00:17:46,065
menunjuk ke beberapa nombor yang akan datang, yang
menunjuk kepada, seterusnya, beberapa nombor yang akan datang?

397
00:17:46,065 --> 00:17:47,940
Jadi dalam erti kata lain, apa yang
jika kita benar-benar mahu

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

399
00:17:49,820 --> 00:17:53,610
Baik malangnya, segi empat tepat ini,
sekurang-kurangnya satu dengan 9, 17, 22,

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

401
00:17:57,040 --> 00:17:59,960
Bahagian bawah, segi empat tepat
di bawah 9, misalnya,

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

403
00:18:04,330 --> 00:18:09,460
Kini, saya tidak lagi sedar apa-apa jenis data
dalam C yang memberikan anda bukan sahaja int satu

404
00:18:09,460 --> 00:18:11,630
tetapi penunjuk sama sekali.

405
00:18:11,630 --> 00:18:15,020
>> Jadi apa penyelesaian jika kita mahu
mencipta jawapan kita sendiri untuk ini?

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

407
00:18:15,760 --> 00:18:16,640
>> PENONTON: [didengar]

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

409
00:18:17,360 --> 00:18:17,880
>> PENONTON: struktur baru.

410
00:18:17,880 --> 00:18:19,590
>> DAVID J. MALAN: Yeah, jadi mengapa
tidak kita mencipta struktur baru,

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

412
00:18:20,920 --> 00:18:25,990
Kami telah melihat sebelum structs, jika secara ringkas,
di mana kita diuruskan dengan struktur pelajar

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

414
00:18:27,780 --> 00:18:31,980
Dalam Serangga 3 pelarian anda menggunakan keseluruhan
sekumpulan GRect structs-- dan GOvals

415
00:18:31,980 --> 00:18:34,810
Stanford yang diwujudkan untuk
maklumat kelompok bersama-sama.

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

417
00:18:38,580 --> 00:18:42,890
dan kemudian beberapa barangan tertentu pelajar,
dan berkembang ini kepada yang berikut:

418
00:18:42,890 --> 00:18:46,210
typedef struct node-- dan simpulan adalah
hanya sains komputer yang sangat generik

419
00:18:46,210 --> 00:18:49,980
jangka sesuatu dalam struktur data,
bekas dalam struktur data.

420
00:18:49,980 --> 00:18:53,900
A nod saya menuntut akan mempunyai
n int, benar-benar mudah,

421
00:18:53,900 --> 00:18:58,810
dan kemudian sedikit lebih cryptically,
barisan kedua ini, nod struct * seterusnya.

422
00:18:58,810 --> 00:19:01,300
Tetapi dari segi kurang teknikal,
apa ialah baris kedua

423
00:19:01,300 --> 00:19:02,980
kod di dalam pendakap kerinting?

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

425
00:19:03,737 --> 00:19:04,851
>> PENONTON: [didengar]

426
00:19:04,851 --> 00:19:06,600
DAVID J. MALAN: A
penunjuk kepada nod yang lain.

427
00:19:06,600 --> 00:19:09,910
Jadi diakui, sintaksis sedikit samar.

428
00:19:09,910 --> 00:19:13,250
Tetapi jika anda membacanya secara literal,
seterusnya adalah nama pembolehubah.

429
00:19:13,250 --> 00:19:14,410
Apakah jenis data?

430
00:19:14,410 --> 00:19:18,206
Ia satu verbose sedikit masa ini,
tetapi ia dari jenis nod struct *.

431
00:19:18,206 --> 00:19:22,960
Bila-bila masa yang kita lihat sesuatu bintang, yang
bermakna ia penunjuk dengan jenis data.

432
00:19:22,960 --> 00:19:26,810
Jadi seterusnya adalah nampaknya
penunjuk kepada nod struct.

433
00:19:26,810 --> 00:19:28,310
>> Kini, apa yang nod struct?

434
00:19:28,310 --> 00:19:31,044
Nah, notis anda melihat orang-orang
perkataan yang sama di sebelah kanan atas.

435
00:19:31,044 --> 00:19:33,960
Dan sesungguhnya, anda juga melihat perkataan
"Nod" turun di sini di sebelah kiri bahagian bawah.

436
00:19:33,960 --> 00:19:35,640
Dan ini adalah benar-benar hanya satu kemudahan.

437
00:19:35,640 --> 00:19:39,930
Perhatikan bahawa dalam definisi pelajar kita
ada perkataan "pelajar" hanya sekali.

438
00:19:39,930 --> 00:19:42,510
Dan itu kerana pelajar
objek tidak sendiri rujukan.

439
00:19:42,510 --> 00:19:45,340
Tiada apa-apa bahagian dalam pelajar
yang perlu untuk menunjukkan kepada pelajar lain,

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

441
00:19:45,610 --> 00:19:47,630
Yang akan menjadi semacam
pelik dalam dunia sebenar.

442
00:19:47,630 --> 00:19:50,880
>> Tetapi dengan nod dalam dikaitkan
senarai, kita mahu nod

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

444
00:19:53,970 --> 00:19:57,900
Dan sebagainya notis perubahan di sini tidak
hanya apa yang di dalam pendakap kerinting.

445
00:19:57,900 --> 00:20:00,800
Tetapi kita menambah perkataan "nod"
di bahagian atas dan juga

446
00:20:00,800 --> 00:20:02,930
menambah ia ke bawah
sebagai ganti "pelajar."

447
00:20:02,930 --> 00:20:06,000
Dan ini hanya butiran teknikal
supaya, sekali lagi, struktur data anda

448
00:20:06,000 --> 00:20:11,380
boleh sendiri rujukan, supaya
nod boleh menunjukkan kepada yang lain nod tersebut.

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

450
00:20:13,840 --> 00:20:17,560
Nah, satu, barangan ini di dalam
adalah kandungan nod kami.

451
00:20:17,560 --> 00:20:19,360
Perkara ini di sini,
kanan atas, adalah hanya supaya

452
00:20:19,360 --> 00:20:20,860
yang, sekali lagi, kita boleh merujuk kepada diri kita sendiri.

453
00:20:20,860 --> 00:20:23,401
Dan kemudian barangan yang paling luar,
walaupun nod adalah satu istilah yang baru,

454
00:20:23,401 --> 00:20:25,500
mungkin, ianya masih menjadi
sama seperti pelajar dan apa yang

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

456
00:20:27,520 --> 00:20:31,095
>> Jadi, jika kita ingin memulakan
melaksanakan senarai ini dikaitkan,

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

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
sebenarnya menggunakan senarai berpaut.

460
00:20:36,840 --> 00:20:40,870
Antara kod pengedaran hari ini
adalah program yang dikenali sebagai Senarai Zero.

461
00:20:40,870 --> 00:20:44,980
Dan sekiranya saya ini saya mencipta super yang
GUI yang mudah, Antara Muka Pengguna grafik,

462
00:20:44,980 --> 00:20:46,460
tetapi ia benar-benar hanya printf.

463
00:20:46,460 --> 00:20:50,930
Dan sekarang saya telah memberikan diri saya beberapa menu
options-- Padam, Masukkan, Search,

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

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

466
00:20:52,630 --> 00:20:55,970
Ini adalah operasi hanya biasa pada
struktur data yang dikenali sebagai senarai link.

467
00:20:55,970 --> 00:20:58,409
>> Sekarang, Padam akan
memadam nombor daripada senarai.

468
00:20:58,409 --> 00:21:00,200
Insert yang akan menambah
nombor kepada senarai.

469
00:21:00,200 --> 00:21:02,181
Carian akan kelihatan
untuk nombor dalam senarai.

470
00:21:02,181 --> 00:21:04,930
Dan traverse hanya cara yang mewah
mengatakan, berjalan melalui senarai,

471
00:21:04,930 --> 00:21:06,245
mencetak, tetapi itu sahaja.

472
00:21:06,245 --> 00:21:07,720
Tidak berubah dalam apa-apa cara.

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

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

475
00:21:10,160 --> 00:21:12,710
Dan kemudian saya akan
memasukkan nombor, katakan 9.

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

477
00:21:13,620 --> 00:21:17,480
Dan kini program saya hanya
diprogramkan untuk berkata, senarai kini 9.

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

479
00:21:20,190 --> 00:21:23,680
saya pergi ke hadapan dan zum keluar dan taip 17.

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

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

482
00:21:27,750 --> 00:21:32,400
Bukan 22, seperti gambar di kita kena
telah melihat di sini, saya melompat ke hadapan

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

484
00:21:34,630 --> 00:21:36,230
Jadi saya akan menaip 26.

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

486
00:21:37,755 --> 00:21:40,630
Tetapi sekarang, hanya untuk melihat kod ini
akan menjadi fleksibel, saya kini

487
00:21:40,630 --> 00:21:43,520
Jenis 22, yang sekurang-kurangnya
dari segi konsep, jika kita

488
00:21:43,520 --> 00:21:46,520
Menyimpan ini disusun, yang memang
akan menjadi matlamat lain sekarang,

489
00:21:46,520 --> 00:21:48,690
perlu 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
Sesungguhnya, yang bekerja.

492
00:21:51,380 --> 00:21:54,950
Dan jadi sekarang biar saya memasukkan
lepas, gambar di, 34.

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

494
00:21:55,450 --> 00:21:58,980
Jadi buat masa ini biarlah saya menetapkan bahawa
Padam dan Traverse dan Cari lakukan,

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

496
00:21:59,760 --> 00:22:04,180
Malah, jika saya menjalankan Cari, mari
mencari nombor 22, Enter.

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

498
00:22:05,010 --> 00:22:07,580
Jadi itulah yang ini
Senarai program Zero tidak.

499
00:22:07,580 --> 00:22:10,230
>> Tetapi apa yang sebenarnya akan
pada yang melaksanakan ini?

500
00:22:10,230 --> 00:22:14,530
Well, pertama saya mungkin, dan sesungguhnya
Saya mempunyai, fail yang dipanggil list0.h.

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

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

503
00:22:20,690 --> 00:22:24,850
maka saya mempunyai pendakap kerinting 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 nod seterusnya.

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

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

508
00:22:31,045 --> 00:22:33,420
Sekarang teknikal kita masuk ke dalam
tabiat melukis di sini.

509
00:22:33,420 --> 00:22:35,670
Anda mungkin melihat buku-buku teks dan
rujukan dalam talian melakukannya di sana.

510
00:22:35,670 --> 00:22:36,660
Ia berfungsi sama.

511
00:22:36,660 --> 00:22:37,980
Malah, ini adalah sedikit lebih biasa.

512
00:22:37,980 --> 00:22:40,563
Tetapi saya akan konsisten dengan apa yang
yang kita lakukan masa lalu dan melakukan ini.

513
00:22:40,563 --> 00:22:42,350
Kemudian akhir sekali, saya akan melakukan ini.

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

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

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

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

518
00:22:54,740 --> 00:22:59,690
List0.h adalah fail saya mahu
untuk dimasukkan ke dalam fail C saya.

519
00:22:59,690 --> 00:23:03,910
Kemudian pada satu ketika saya
akan mempunyai int, utama, tidak sah.

520
00:23:03,910 --> 00:23:06,530
Dan kemudian saya akan
mempunyai beberapa tugasan di sini.

521
00:23:06,530 --> 00:23:10,620
Saya juga akan mempunyai
prototaip, seperti tidak sah, carian, int,

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

523
00:23:13,610 --> 00:23:18,310
Dan kemudian turun di sini saya menuntut di
kod hari ini, tidak sah, carian, int, n,

524
00:23:18,310 --> 00:23:21,020
tidak koma bertitik tetapi pendakap kerinting terbuka.

525
00:23:21,020 --> 00:23:25,049
Dan sekarang saya ingin mencari entah bagaimana
kepada satu unsur dalam senarai ini.

526
00:23:25,049 --> 00:23:27,340
Tetapi kita tidak mempunyai cukup
maklumat pada skrin lagi.

527
00:23:27,340 --> 00:23:29,800
Saya tidak benar-benar
diwakili senarai itu sendiri.

528
00:23:29,800 --> 00:23:33,070
Jadi salah satu cara kita boleh melaksanakan
senarai dikaitkan dalam program yang

529
00:23:33,070 --> 00:23:37,520
adalah saya jenis mahu melakukan sesuatu
seperti mengisytiharkan senarai dikaitkan di sini.

530
00:23:37,520 --> 00:23:40,520
Untuk memudahkan, saya akan membuat
ini dunia, walaupun dalam kita umum

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

532
00:23:41,645 --> 00:23:43,260
Tetapi ia akan memudahkan contoh ini.

533
00:23:43,260 --> 00:23:45,890
Jadi saya mahu untuk mengisytiharkan
senarai berpaut di sini.

534
00:23:45,890 --> 00:23:47,010
Sekarang, bagaimana saya boleh berbuat demikian?

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

536
00:23:48,810 --> 00:23:50,750
>> Berikut adalah gambar senarai berpaut.

537
00:23:50,750 --> 00:23:53,030
Dan saya tidak benar-benar
tahu pada masa ini bagaimana

538
00:23:53,030 --> 00:23:56,710
Saya akan pergi kira-kira mewakili
begitu banyak perkara dengan hanya satu

539
00:23:56,710 --> 00:23:58,040
berubah-ubah dalam ingatan.

540
00:23:58,040 --> 00:23:59,160
Tetapi berfikir kembali seketika.

541
00:23:59,160 --> 00:24:00,830
Selama ini kita telah mempunyai
tali, yang kita kemudian

542
00:24:00,830 --> 00:24:02,913
didedahkan sebagai tatasusunan
aksara, yang kemudiannya kami

543
00:24:02,913 --> 00:24:05,740
diturunkan kepada hanya menjadi penunjuk
dengan watak yang pertama

544
00:24:05,740 --> 00:24:08,890
dalam pelbagai watak
yang yang batal ditamatkan.

545
00:24:08,890 --> 00:24:13,530
Jadi dengan logik itu, dan dengan ini
jenis gambar pembenihan pemikiran anda,

546
00:24:13,530 --> 00:24:17,964
apa yang perlu kita sebenarnya menulis dalam kami
kod untuk mewakili senarai berpaut?

547
00:24:17,964 --> 00:24:21,130
Berapa banyak maklumat ini kita perlu
untuk menangkap kod C, anda akan berkata?

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

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

550
00:24:23,154 --> 00:24:24,738
>> PENONTON: Kita perlu penunjuk kepada nod.

551
00:24:24,738 --> 00:24:26,237
DAVID J. MALAN: Satu penunjuk kepada nod.

552
00:24:26,237 --> 00:24:29,320
Khususnya, yang nod akan anda
naluri adalah untuk memastikan penunjuk ke?

553
00:24:29,320 --> 00:24:30,026
>> PENONTON: Nod pertama.

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

555
00:24:31,942 --> 00:24:34,030
Dan notis itu, yang pertama
nod adalah bentuk yang berbeza.

556
00:24:34,030 --> 00:24:37,690
Ia hanya separuh saiz struct itu,
kerana ia sememangnya hanya penunjuk.

557
00:24:37,690 --> 00:24:44,650
Jadi apa yang anda memang boleh lakukan adalah mengisytiharkan
senarai dikaitkan dengan menjadi nod Jenis *.

558
00:24:44,650 --> 00:24:47,780
Dan mari kita memanggilnya pertama
dan memulakan kepada null.

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

560
00:24:49,910 --> 00:24:53,620
Bukan sahaja null digunakan sebagai seperti khas
nilai pulangan untuk perkara-perkara seperti getstring

561
00:24:53,620 --> 00:24:57,770
dan malloc, batal juga sifar
penunjuk, kekurangan penunjuk,

562
00:24:57,770 --> 00:24:58,430
jika anda akan.

563
00:24:58,430 --> 00:25:00,309
Ia hanya bermakna apa-apa lagi di sini.

564
00:25:00,309 --> 00:25:02,100
Sekarang pertama, saya boleh telah
dikenali sebagai apa-apa ini.

565
00:25:02,100 --> 00:25:04,200
Saya boleh memanggilnya "senarai"
atau mana-mana beberapa perkara lain.

566
00:25:04,200 --> 00:25:06,960
Tetapi saya memanggil "pertama" supaya
ia garisan dengan gambar ini.

567
00:25:06,960 --> 00:25:10,280
Jadi seperti rentetan boleh diwakili
dengan alamat bait pertama,

568
00:25:10,280 --> 00:25:11,280
jadi boleh senarai berpaut.

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 penunjuk,
32-bit anak panah, menunjuk

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

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

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

574
00:25:23,230 --> 00:25:27,220
nod yang pertama, yang pertama
segi empat tepat dalam struktur data ini,

575
00:25:27,220 --> 00:25:31,760
apa yang mempunyai yang lebih baik kes itu tentang
pelaksanaan seluruh senarai saya?

576
00:25:31,760 --> 00:25:35,820
Apakah yang dimaksudkan dengan terperinci penting yang berlaku
untuk memastikan ini benar-benar berfungsi?

577
00:25:35,820 --> 00:25:39,250
Dan dengan "benar-benar bekerja" Saya
bermakna, sama seperti tali,

578
00:25:39,250 --> 00:25:42,180
mari kita pergi dari watak pertama
nama Davin untuk yang kedua,

579
00:25:42,180 --> 00:25:44,755
untuk ketiga, kepada
keempat, hingga ke akhir sangat,

580
00:25:44,755 --> 00:25:47,880
bagaimana kita tahu apabila kita berada di hujung
senarai berpaut yang kelihatan seperti ini?

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

582
00:25:50,035 --> 00:25:50,660
Apabila tiba null.

583
00:25:50,660 --> 00:25:53,640
Dan saya telah diwakili seperti ini sebagai
seperti kekuatan seorang jurutera elektrik,

584
00:25:53,640 --> 00:25:56,420
dengan asas yang kecil
simbol, kejayaannya.

585
00:25:56,420 --> 00:25:58,246
Tetapi itu hanya bermakna batal dalam kes ini.

586
00:25:58,246 --> 00:26:00,370
Anda boleh menarik ia apa-apa bilangan
cara, tetapi pengarang ini

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

588
00:26:02,800 --> 00:26:06,260
>> Selagi kita stringing
semua nod ini bersama-sama,

589
00:26:06,260 --> 00:26:08,600
hanya mengingati di mana
yang pertama adalah, selagi

590
00:26:08,600 --> 00:26:11,760
seperti yang kita meletakkan simbol khas di
nod yang terakhir dalam senarai,

591
00:26:11,760 --> 00:26:15,130
dan kami akan menggunakan batal, kerana itulah
apa yang kita ada untuk kita,

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

593
00:26:16,480 --> 00:26:20,190
Dan walaupun saya hanya memberi penunjuk kepada
elemen pertama, anda, pengaturcara,

594
00:26:20,190 --> 00:26:22,486
tentu boleh mengakses seluruh ia.

595
00:26:22,486 --> 00:26:24,360
Tetapi mari kita biarkan fikiran anda
bersiar-siar sedikit,

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

597
00:26:26,140 --> 00:26:28,723
akan menjadi masa yang berjalan dari
mencari apa-apa dalam senarai ini?

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

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

600
00:26:33,470 --> 00:26:34,800
Tetapi ia adalah linear.

601
00:26:34,800 --> 00:26:37,980
Kami telah diberikan sehingga apa ciri
array dengan bergerak lebih

602
00:26:37,980 --> 00:26:43,130
ke arah gambar ini secara dinamik
ditenun bersama-sama atau dikaitkan nod?

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

604
00:26:44,970 --> 00:26:46,687
Kami telah diberi Akses rawak.

605
00:26:46,687 --> 00:26:48,770
Pelbagai bagus kerana
segala sesuatu secara matematik

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

607
00:26:50,340 --> 00:26:52,370
Walaupun gambar ini
kelihatan cantik, malah

608
00:26:52,370 --> 00:26:55,830
walaupun ia kelihatan seperti nod ini
adalah baik dijarakkan selain, pada hakikatnya

609
00:26:55,830 --> 00:26:56,830
mereka boleh berada di mana sahaja.

610
00:26:56,830 --> 00:27:01,590
Ox1, Ox50, Ox123, Ox99, ini
nod boleh berada di mana sahaja.

611
00:27:01,590 --> 00:27:05,960
Kerana malloc tidak memperuntukkan memori
dari timbunan itu, tetapi mana-mana sahaja dalam timbunan itu.

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

613
00:27:09,080 --> 00:27:12,460
Dan gambar ini pada hakikatnya ini
tidak akan menjadi agak ini cantik.

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

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

616
00:27:17,880 --> 00:27:20,250
Dan kita akan melihat jenis yang
cara bijak untuk berbuat demikian.

617
00:27:20,250 --> 00:27:24,660
Jadi, jika saya satu fungsi carian dan
Saya diberi berubah-ubah, 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
struktur itu
menunjuk kepada, untuk mencari n.

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

621
00:27:33,210 --> 00:27:36,030
>> Oleh itu saya akan pergi
hadapan dan mengisytiharkan nod *.

622
00:27:36,030 --> 00:27:39,400
Dan saya akan memanggilnya
pointer, hanya dengan konvensyen.

623
00:27:39,400 --> 00:27:41,710
Dan saya akan memulakan ia terlebih dahulu.

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

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

626
00:27:45,436 --> 00:27:50,180
Walaupun pointer tidak sama dengan
batal, dan itu sintaks sah.

627
00:27:50,180 --> 00:27:54,550
Dan ia hanya bermaksud melakukan yang berikut, jadi
selagi anda tidak menghala ke arah apa-apa.

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

629
00:27:55,800 --> 00:28:01,939
>> Jika penunjuk dot n, biarlah saya kembali
itu, equals-- sama apa?

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

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

632
00:28:04,920 --> 00:28:06,590
N sebenar yang telah diluluskan pada.

633
00:28:06,590 --> 00:28:09,020
Jadi di sini adalah satu lagi ciri
C dan banyak bahasa.

634
00:28:09,020 --> 00:28:13,705
Walaupun struktur dipanggil nod
mempunyai nilai n, benar-benar sah

635
00:28:13,705 --> 00:28:17,530
juga mempunyai hujah tempatan
atau pembolehubah dipanggil n.

636
00:28:17,530 --> 00:28:20,085
Kerana walaupun kita, dengan
mata manusia, boleh membezakan

637
00:28:20,085 --> 00:28:22,087
n ini mungkin
berbeza daripada n ini.

638
00:28:22,087 --> 00:28:23,420
Kerana sintaksis adalah berbeza.

639
00:28:23,420 --> 00:28:26,211
Anda perlu titik dan penunjuk,
manakala yang satu ini tidak mempunyai benda itu.

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

641
00:28:27,290 --> 00:28:29,120
Itulah OK untuk memanggil mereka perkara yang sama.

642
00:28:29,120 --> 00:28:32,380
>> Jika saya anda mencari ini, saya
akan mahu melakukan sesuatu

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

644
00:28:35,000 --> 00:28:37,930
Dan kita akan meninggalkan bahawa sebagai
komen atau kod kod pseudo.

645
00:28:37,930 --> 00:28:40,190
Yang lain, dan di sini yang
bahagian yang menarik, apa yang

646
00:28:40,190 --> 00:28:47,320
saya mahu lakukan jika nod semasa
tidak mengandungi n bahawa saya mengambil berat tentang?

647
00:28:47,320 --> 00:28:50,700
Bagaimana saya mencapai yang berikut?

648
00:28:50,700 --> 00:28:53,710
Jika jari saya di
masa adalah PTR, dan ia

649
00:28:53,710 --> 00:28:55,920
menghala ke arah apa sahaja
pertama menghala ke arah,

650
00:28:55,920 --> 00:28:59,290
bagaimana saya boleh bergerak jari saya
untuk nod seterusnya dalam kod?

651
00:28:59,290 --> 00:29:01,915
Nah, apa yang nota singkat yang kami
akan mengikuti dalam kes ini?

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

653
00:29:03,464 --> 00:29:04,380
PENONTON: [didengar].

654
00:29:04,380 --> 00:29:05,630
DAVID J. MALAN: Yeah, jadi seterusnya.

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

656
00:29:06,640 --> 00:29:09,824
Jadi, jika saya kembali kepada saya
kod sini, sesungguhnya, saya

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

658
00:29:12,990 --> 00:29:15,320
nama pelik, ptr, tetapi
ia seperti temp--

659
00:29:15,320 --> 00:29:19,234
Saya akan set penunjuk
sama dengan apa penunjuk is--

660
00:29:19,234 --> 00:29:22,150
dan sekali lagi, ini akan menjadi satu
sedikit buggy untuk dot moment-- depan.

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

662
00:29:23,551 --> 00:29:26,550
Dalam erti kata lain, saya akan mengambil saya
jari yang yang menunjuk pada nod ini

663
00:29:26,550 --> 00:29:31,247
di sini dan saya akan berkata, anda tahu
apa, kita lihat pada bidang seterusnya

664
00:29:31,247 --> 00:29:33,330
dan bergerak jari anda untuk
apa sahaja yang ia menghala ke arah.

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

666
00:29:35,163 --> 00:29:37,630
Tetapi apabila tidak jari saya
berhenti melakukan apa-apa pun?

667
00:29:37,630 --> 00:29:40,095
Sebaik sahaja apa garis tendangan kod di?

668
00:29:40,095 --> 00:29:40,970
PENONTON: [didengar]

669
00:29:40,970 --> 00:29:43,060
DAVID J. MALAN: Jika mata manakala
penunjuk tidak sama dengan nol.

670
00:29:43,060 --> 00:29:44,900
Pada beberapa titik jari saya
akan menghala ke arah null

671
00:29:44,900 --> 00:29:47,070
dan saya akan menyedari
itulah akhir senarai ini.

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

673
00:29:48,910 --> 00:29:51,580
Ia ternyata bahawa walaupun kita
baru belajar notasi dot ini

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

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
Ia adalah penunjuk kepada nod.

679
00:30:01,360 --> 00:30:03,120
Ia bukan satu nod sendiri.

680
00:30:03,120 --> 00:30:06,650
Jika saya tidak mempunyai bintang di sini, penunjuk
absolutely-- ia nod.

681
00:30:06,650 --> 00:30:08,650
Ini seperti satu minggu
pengisytiharan pembolehubah,

682
00:30:08,650 --> 00:30:10,120
walaupun perkataan "nod" yang baru.

683
00:30:10,120 --> 00:30:13,860
>> Tetapi sebaik sahaja kami memperkenalkan
bintang, ia kini merupakan penunjuk kepada nod.

684
00:30:13,860 --> 00:30:17,960
Dan malangnya anda tidak boleh menggunakan
notasi titik untuk penunjuk.

685
00:30:17,960 --> 00:30:21,070
Anda perlu menggunakan anak panah
notasi, yang, sungguh menarik,

686
00:30:21,070 --> 00:30:23,470
adalah kali pertama mana-mana bahagian
sintaksis kelihatan intuitif.

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

688
00:30:25,245 --> 00:30:26,370
Dan itu adalah satu perkara yang baik.

689
00:30:26,370 --> 00:30:28,995
Dan turun di sini secara literal
kelihatan seperti anak panah.

690
00:30:28,995 --> 00:30:31,870
Jadi saya fikir itu la-- yang saya tidak
fikir saya lebih-melakukan here-- saya

691
00:30:31,870 --> 00:30:34,120
fikir itu sekeping baru yang lalu
sintaksis kita akan lihat.

692
00:30:34,120 --> 00:30:36,500
Dan bersyukur kerana, ia memang
sedikit lebih intuitif.

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

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

695
00:30:42,550 --> 00:30:45,380
Tetapi seperti semalam
perbualan, kami pertama

696
00:30:45,380 --> 00:30:50,530
perlu ke sana, pergi ke
menangani, dan kemudian mengakses padang.

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

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

699
00:30:53,730 --> 00:30:56,530
Anda benar-benar berkata, dereference
penunjuk dan pergi ke sana.

700
00:30:56,530 --> 00:30:59,320
Kemudian merebut .n, bidang yang dipanggil n.

701
00:30:59,320 --> 00:31:01,370
Tetapi terus-terang, tidak ada yang mahu
menaip atau membaca ini.

702
00:31:01,370 --> 00:31:03,620
Dan dunia dicipta
notasi anak panah, yang

703
00:31:03,620 --> 00:31:06,980
adalah bersamaan, sama,
ia hanya gula sintaksis.

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

705
00:31:10,570 --> 00:31:12,296
>> Jadi sekarang saya akan melakukan satu perkara yang lain.

706
00:31:12,296 --> 00:31:15,420
Saya akan berkata "break" sekali saya telah
mendapati ia jadi saya tidak terus mencari untuk itu.

707
00:31:15,420 --> 00:31:17,620
Tetapi ini adalah inti yang
daripada fungsi carian.

708
00:31:17,620 --> 00:31:21,710
Tetapi ia lebih mudah, dalam
akhir, tidak berjalan melalui kod.

709
00:31:21,710 --> 00:31:25,570
Ini merupakan pelaksanaan rasmi
carian dalam kod pengedaran hari ini.

710
00:31:25,570 --> 00:31:30,530
Saya berani mengatakan sisipan yang tidak
terutamanya menyeronokkan untuk berjalan melalui

711
00:31:30,530 --> 00:31:33,180
visual, juga memadam, walaupun
walaupun pada akhir hari

712
00:31:33,180 --> 00:31:35,460
mereka mendidih ke agak
heuristik mudah.

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

714
00:31:36,330 --> 00:31:39,250
Jika anda akan humor saya di sini, saya
membawa sekumpulan bola tekanan.

715
00:31:39,250 --> 00:31:40,620
Saya membawa sekumpulan nombor.

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

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

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

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

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

721
00:31:55,740 --> 00:32:01,910
OK, satu, dua, tiga, empat,
five-- biarlah saya memuatkan balance-- enam.

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

723
00:32:03,051 --> 00:32:04,050
Kami akan memerlukan orang lain.

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

725
00:32:05,460 --> 00:32:08,200
Dan jika anda boleh, untuk
hanya seketika, talian

726
00:32:08,200 --> 00:32:10,490
diri sehingga 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, apa nama anda?

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

731
00:32:17,550 --> 00:32:18,800
>> DAVID J. MALAN: Andrew,
anda bilangan 9.

732
00:32:18,800 --> 00:32:19,540
Nice untuk bertemu dengan kamu.

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
PENONTON: Jen.

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

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

738
00:32:23,162 --> 00:32:23,765
Number 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
>> PENONTON: Saya Julia.

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

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

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

745
00:32:28,507 --> 00:32:29,340
PENONTON: Kristian.

746
00:32:29,340 --> 00:32:30,715
DAVID J. MALAN: Christian, David.

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

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

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

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

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

752
00:32:34,880 --> 00:32:37,080
Oleh itu, pergilah ke hadapan dan mendapatkan dalam- 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
Siap sedia.

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
Adakah sesiapa yang mempunyai penanda?

760
00:32:43,682 --> 00:32:44,890
PENONTON: Saya ada Sharpie.

761
00:32:44,890 --> 00:32:45,660
DAVID J. MALAN: Anda mendapat 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 tidak sesiapa yang mempunyai sehelai kertas?

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

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

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

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

769
00:32:55,362 --> 00:32:56,320
PENONTON: Kami telah mendapat ia.

770
00:32:56,320 --> 00:32:57,600
DAVID J. MALAN: Kami mendapat ia?

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
Adakah ini daripada 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 silap eja 29, tetapi OK.

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

783
00:33:15,720 --> 00:33:18,114
Baiklah, saya akan memberikan anda
pen anda kembali seketika.

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

785
00:33:19,280 --> 00:33:20,330
Mari kita mempunyai satu yang lain.

786
00:33:20,330 --> 00:33:23,750
Gabe, adakah anda mahu bermain
elemen pertama di sini?

787
00:33:23,750 --> 00:33:25,705
Kami akan memerlukan anda untuk menunjukkan
pada ini orang halus.

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

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

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

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

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

793
00:33:33,950 --> 00:33:36,730
Di mana OK did--, yang mahu 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
berbaloi kemuncak.

797
00:33:41,220 --> 00:33:41,550
Apa nama anda?

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

799
00:33:42,040 --> 00:33:43,456
>> DAVID J. MALAN: Peter, datang ke atas sehingga.

800
00:33:43,456 --> 00:33:46,810
Baiklah, jadi di sini adalah
sejumlah besar nod.

801
00:33:46,810 --> 00:33:49,060
Setiap satu daripada anda semua mewakili
salah satu segi empat tepat ini.

802
00:33:49,060 --> 00:33:51,930
Dan Gabe, sedikit ganjil
manusia keluar, mewakili pertama.

803
00:33:51,930 --> 00:33:54,850
Jadi penunjuk beliau adalah sedikit lebih kecil
pada skrin dari orang lain.

804
00:33:54,850 --> 00:33:58,120
Dan dalam kes ini, setiap satu daripada anda meninggalkan
tangan akan menunjukkan sama ada ke bawah,

805
00:33:58,120 --> 00:34:01,085
dengan itu mewakili batal, jadi
hanya ketiadaan penunjuk,

806
00:34:01,085 --> 00:34:03,210
atau ia akan menunjuk
pada nod yang bersebelahan dengan anda.

807
00:34:03,210 --> 00:34:05,440
>> Jadi sekarang jika anda menghiasi
kamu seperti gambar

808
00:34:05,440 --> 00:34:07,585
di sini, pergi ke depan dan mata
di antara satu sama lain, dengan Gabe

809
00:34:07,585 --> 00:34:11,030
dalam menunjuk tertentu di
bilangan 9 untuk mewakili senarai.

810
00:34:11,030 --> 00:34:14,050
OK, dan nombor 34, tangan kiri anda
seharusnya hanya akan menghala ke arah lantai.

811
00:34:14,050 --> 00:34:15,750
>> OK, jadi ini adalah senarai yang dipautkan.

812
00:34:15,750 --> 00:34:17,580
Jadi, ini adalah senario yang berkenaan.

813
00:34:17,580 --> 00:34:20,210
Dan sesungguhnya, ini adalah wakil
daripada kelas masalah

814
00:34:20,210 --> 00:34:21,929
bahawa anda mungkin cuba untuk menyelesaikan dengan kod.

815
00:34:21,929 --> 00:34:25,020
Anda mahu akhirnya memasukkan
elemen baru ke dalam senarai.

816
00:34:25,020 --> 00:34:27,494
Dalam kes ini, kita akan
cuba memasukkan bilangan 55.

817
00:34:27,494 --> 00:34:28,500

818
00:34:28,500 --> 00:34:30,860
Tetapi ada akan menjadi
kes-kes yang berbeza untuk dipertimbangkan.

819
00:34:30,860 --> 00:34:34,409
Dan sesungguhnya, ini akan menjadi satu
daripada yang besar-gambar bawa pulang di sini, adalah,

820
00:34:34,409 --> 00:34:35,659
apakah kes-kes yang berbeza.

821
00:34:35,659 --> 00:34:39,120
Apakah berbeza jika syarat atau
cawangan yang program anda mungkin mempunyai?

822
00:34:39,120 --> 00:34:42,024
>> Nah, nombor yang anda cuba untuk
insert, yang kita tahu sekarang menjadi 55,

823
00:34:42,024 --> 00:34:44,650
tetapi jika anda tidak tahu
terlebih dahulu, saya berani mengatakan

824
00:34:44,650 --> 00:34:47,840
jatuh ke dalam sekurang-kurangnya tiga
keadaan mungkin.

825
00:34:47,840 --> 00:34:49,717
Di mana mungkin elemen baru menjadi?

826
00:34:49,717 --> 00:34:51,050
PENONTON: Dan akhir atau pertengahan.

827
00:34:51,050 --> 00:34:54,150
DAVID J. MALAN: Pada akhirnya, dalam
tengah-tengah, atau pada awal.

828
00:34:54,150 --> 00:34:56,650
Jadi saya mendakwa ada sekurang-kurangnya
tiga masalah yang kita perlu menyelesaikan.

829
00:34:56,650 --> 00:34:58,691
Mari kita memilih apa yang mungkin
boleh dikatakan yang paling mudah

830
00:34:58,691 --> 00:35:01,090
satu, di mana elemen baru
milik pada permulaan.

831
00:35:01,090 --> 00:35:04,040
Jadi saya akan mempunyai kod agak
seperti mencari, yang saya hanya menulis.

832
00:35:04,040 --> 00:35:07,670
Dan saya akan mempunyai ptr, yang
Saya akan mewakili 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
yang kita memulakan ptr ke?

835
00:35:12,430 --> 00:35:15,300
Oleh itu, kita dimulakan untuk null mulanya.

836
00:35:15,300 --> 00:35:16,410

837
00:35:16,410 --> 00:35:19,770
Tetapi apakah yang kita lakukan sebaik sahaja kami
berada di dalam fungsi carian kami?

838
00:35:19,770 --> 00:35:20,940

839
00:35:20,940 --> 00:35:24,870
Kami menetapkan ia sama dengan yang pertama,
yang tidak bermakna melakukan 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 yang pertama, apa yang
perlu tangan saya benar-benar menjadi menghala ke arah?

842
00:35:30,570 --> 00:35:31,070
Betul.

843
00:35:31,070 --> 00:35:33,290
Jadi jika Gabe dan saya akan
menjadi nilai-nilai yang sama di sini,

844
00:35:33,290 --> 00:35:34,760
kita perlu kedua-dua titik di nombor 9.

845
00:35:34,760 --> 00:35:36,420
>> Jadi ini adalah permulaan cerita kita.

846
00:35:36,420 --> 00:35:38,700
Dan sekarang ini hanya terus-terang,
walaupun sintaks baru.

847
00:35:38,700 --> 00:35:40,580
Dari segi konsep ini hanyalah carian linear.

848
00:35:40,580 --> 00:35:42,750
55 bersamaan dengan 9?

849
00:35:42,750 --> 00:35:45,559
Atau sebaliknya, katakan kurang daripada 9.

850
00:35:45,559 --> 00:35:47,600
Oleh kerana saya cuba untuk
memikirkan di mana untuk meletakkan 55.

851
00:35:47,600 --> 00:35:51,270
Kurang daripada 9, kurang daripada 17, kurang
daripada 20, kurang daripada 22, kurang daripada 29,

852
00:35:51,270 --> 00:35:52,510
kurang daripada 34, tidak.

853
00:35:52,510 --> 00:35:55,080
Jadi sekarang kita berada dalam kes
salah satu daripada sekurang-kurangnya tiga.

854
00:35:55,080 --> 00:35:59,910
>> Jika saya mahu memasukkan 55 di sini, apa yang
baris kod keperluan untuk mendapatkan dilaksanakan?

855
00:35:59,910 --> 00:36:01,890
Bagaimana gambar ini
manusia perlu berubah?

856
00:36:01,890 --> 00:36:03,181
Apa yang saya buat dengan tangan kiri saya?

857
00:36:03,181 --> 00:36:04,530

858
00:36:04,530 --> 00:36:07,360
Ini perlu batal pada mulanya,
kerana saya pada akhir senarai.

859
00:36:07,360 --> 00:36:09,318
Dan apa yang sepatutnya berlaku
di sini dengan Peter, adakah?

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 mendakwa ada sekurang-kurangnya dua baris
kod kod sampel dari hari ini

863
00:36:15,580 --> 00:36:18,570
perkara yang berlaku untuk melaksanakan ini
senario menambah 55 di ekor.

864
00:36:18,570 --> 00:36:20,950
Dan boleh saya hop seseorang
dan hanya mewakili 55?

865
00:36:20,950 --> 00:36:22,200
Baiklah, anda baru 55.

866
00:36:22,200 --> 00:36:23,580

867
00:36:23,580 --> 00:36:27,054
>> Jadi sekarang apa yang jika seterusnya
senario datang bersama-sama,

868
00:36:27,054 --> 00:36:29,720
dan kami mahu memasukkan di
bermula atau ketua senarai ini?

869
00:36:29,720 --> 00:36:31,100
Dan apa nama, nombor 55?

870
00:36:31,100 --> 00:36:31,420
>> PENONTON: Jack.

871
00:36:31,420 --> 00:36:32,295
>> DAVID J. MALAN: Jack?

872
00:36:32,295 --> 00:36:33,585
OK, baik untuk bertemu dengan kamu.

873
00:36:33,585 --> 00:36:34,210
Selamat Datang.

874
00:36:34,210 --> 00:36:36,640
Jadi sekarang kita akan
memasukkan, katakan, nombor 5.

875
00:36:36,640 --> 00:36:39,840
Berikut adalah kes kedua
tiga kami datang dengan sebelum.

876
00:36:39,840 --> 00:36:43,050
Jadi, jika 5 milik pada permulaan,
mari kita lihat bagaimana kita dapati bahawa daripada.

877
00:36:43,050 --> 00:36:46,310
Saya memulakan ptr saya
penunjuk kepada nombor 9 lagi.

878
00:36:46,310 --> 00:36:49,140
Dan saya sedar, oh, 5 adalah kurang dari 9.

879
00:36:49,140 --> 00:36:50,880
Jadi menetapkan gambar ini untuk kita.

880
00:36:50,880 --> 00:36:54,820
Yang tangan, ini Gabe atau Daud
or-- apa nama bilangan 9 ini?

881
00:36:54,820 --> 00:36:55,740
>> PENONTON: Jen.

882
00:36:55,740 --> 00:36:58,406
>> DAVID J. MALAN: hands-- Jen ini
yang tangan kita perlu berubah?

883
00:36:58,406 --> 00:36:58,905

884
00:36:58,905 --> 00:37:00,970
OK, jadi Gabe menunjukkan apa sekarang?

885
00:37:00,970 --> 00:37:01,640
Pada saya.

886
00:37:01,640 --> 00:37:02,750
Saya nod baru.

887
00:37:02,750 --> 00:37:04,870
Jadi saya akan hanya jenis daripada langkah
di sini untuk melihatnya secara visual.

888
00:37:04,870 --> 00:37:06,435
Dan sementara itu apa yang saya menunjukkan bahawa?

889
00:37:06,435 --> 00:37:07,910

890
00:37:07,910 --> 00:37:09,020
Masih di mana saya menunjuk.

891
00:37:09,020 --> 00:37:10,000
Jadi itu sahaja.

892
00:37:10,000 --> 00:37:13,717
Jadi, benar-benar satu baris perbaikan kod
isu ini tertentu, ia akan kelihatan.

893
00:37:13,717 --> 00:37:14,800
Baiklah, jadi itulah yang baik.

894
00:37:14,800 --> 00:37:17,580
Dan seseorang boleh menjadi pemegang tempat selama 5?

895
00:37:17,580 --> 00:37:18,080
Marilah naik.

896
00:37:18,080 --> 00:37:20,270

897
00:37:20,270 --> 00:37:21,320
Kami akan membawa anda masa depan.

898
00:37:21,320 --> 00:37:24,280
>> Baiklah, jadi now-- dan
sebagai diketepikan, nama-nama

899
00:37:24,280 --> 00:37:28,510
Saya tidak membuat sebutan yang jelas hak
sekarang, penunjuk pred, sebelumnya penunjuk

900
00:37:28,510 --> 00:37:31,260
dan penunjuk baru, itu
hanya nama-nama yang diberikan

901
00:37:31,260 --> 00:37:35,280
dalam kod sampel kepada petunjuk atau
tangan saya yang yang jenis menunjuk sekitar.

902
00:37:35,280 --> 00:37:36,060
Apa nama anda?

903
00:37:36,060 --> 00:37:36,700
>> PENONTON: Christine.

904
00:37:36,700 --> 00:37:37,100
>> DAVID J. MALAN: Christine.

905
00:37:37,100 --> 00:37:38,090
Selamat Datang.

906
00:37:38,090 --> 00:37:42,180
Baiklah, jadi mari kita mempertimbangkan kini
senario sedikit lebih menjengkelkan,

907
00:37:42,180 --> 00:37:46,350
di mana saya mahu 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-- perkara yang baik kita mempunyai pen 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 boleh mendapatkan satu lagi
kertas bersedia, hanya dalam case-- semua betul.

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 satu contoh
daripada pepijat 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
PENONTON: Julia.

919
00:38:04,560 --> 00:38:07,559
DAVID J. MALAN: Julia, anda boleh pop
keluar dan berpura-pura anda tidak hadir?

920
00:38:07,559 --> 00:38:09,040
OK, ini tidak pernah berlaku.

921
00:38:09,040 --> 00:38:09,680
Terima kasih.

922
00:38:09,680 --> 00:38:12,180
Jadi andaikan kita mahu memasukkan
Julia ke dalam senarai ini yang berkaitan.

923
00:38:12,180 --> 00:38:13,780
Beliau adalah nombor 20.

924
00:38:13,780 --> 00:38:15,530
Dan sudah tentu dia
akan tergolong di

925
00:38:15,530 --> 00:38:17,521
begin-- tidak menunjuk ke arah apa-apa lagi.

926
00:38:17,521 --> 00:38:20,020
Jadi tangan anda jenis boleh
turun null atau beberapa nilai sampah.

927
00:38:20,020 --> 00:38:21,210
Mari kita bercerita cepat.

928
00:38:21,210 --> 00:38:22,980
Saya menghala ke arah nombor 5 kali ini.

929
00:38:22,980 --> 00:38:23,880
Kemudian saya menyemak 9.

930
00:38:23,880 --> 00:38:25,130
Kemudian saya memeriksa 17.

931
00:38:25,130 --> 00:38:26,247
Kemudian saya memeriksa 22.

932
00:38:26,247 --> 00:38:27,650

933
00:38:27,650 --> 00:38:32,485
Dan saya sedar, aduh, Julia
perlu pergi sebelum 22.

934
00:38:32,485 --> 00:38:33,580

935
00:38:33,580 --> 00:38:34,660
Jadi apa yang perlu berlaku?

936
00:38:34,660 --> 00:38:35,786

937
00:38:35,786 --> 00:38:36,910
Yang tangan perlu berubah?

938
00:38:36,910 --> 00:38:38,360
Julia, saya, or--
apa nama anda lagi?

939
00:38:38,360 --> 00:38:39,230
>> PENONTON: Kristian.

940
00:38:39,230 --> 00:38:40,060
>> DAVID J. MALAN: Kristian atau?

941
00:38:40,060 --> 00:38:40,560
>> PENONTON: Andy.

942
00:38:40,560 --> 00:38:40,905
>> DAVID J. MALAN: Andy.

943
00:38:40,905 --> 00:38:41,654
Kristian atau Andy?

944
00:38:41,654 --> 00:38:44,280

945
00:38:44,280 --> 00:38:45,690
Andy perlu menunjuk ke arah?

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, adakah anda mahu untuk menunjukkan pada Julia?

950
00:38:48,960 --> 00:38:50,120
Tetapi tunggu satu minit.

951
00:38:50,120 --> 00:38:53,260
Dalam cerita ini setakat ini,
Saya jenis satu

952
00:38:53,260 --> 00:38:56,800
yang bertanggungjawab, dalam erti kata bahawa
penunjuk adalah perkara itu

953
00:38:56,800 --> 00:38:57,850
bergerak melalui senarai.

954
00:38:57,850 --> 00:39:00,800
Kita mungkin mempunyai nama untuk Andy, tetapi
tidak ada ubah dikenali sebagai Andy.

955
00:39:00,800 --> 00:39:04,320
Satu-satunya pembolehubah lain yang kami ada adalah
pertama, siapa yang diwakili oleh Gabe.

956
00:39:04,320 --> 00:39:07,690
>> Jadi ini adalah benar-benar mengapa itu
ini kita telah tidak diperlukan ini.

957
00:39:07,690 --> 00:39:10,846
Tetapi sekarang pada skrin terdapat
menyebut lagi penunjuk pred.

958
00:39:10,846 --> 00:39:11,970
Jadi biarlah saya menjadi lebih jelas.

959
00:39:11,970 --> 00:39:14,820
Jika ini adalah penunjuk, saya mempunyai yang lebih baik
mendapatkan sedikit lebih pintar

960
00:39:14,820 --> 00:39:15,950
mengenai lelaran saya.

961
00:39:15,950 --> 00:39:19,580
Jika anda tidak keberatan saya melalui sini
sekali lagi, menunjukkan di sini, menunjukkan di sini.

962
00:39:19,580 --> 00:39:22,500
Tetapi saya mempunyai penunjuk pred,
penunjuk sebelumnya, itu

963
00:39:22,500 --> 00:39:24,740
jenis menghala ke arah yang
elemen Saya hanya di.

964
00:39:24,740 --> 00:39:27,330
Oleh itu, apabila saya pergi di sini, kini
kemas kini tangan kiri saya.

965
00:39:27,330 --> 00:39:29,370
Apabila saya pergi sini kemas kini tangan kiri saya.

966
00:39:29,370 --> 00:39:33,090
Dan sekarang saya bukan sahaja penunjuk kepada
elemen yang masuk selepas Julia,

967
00:39:33,090 --> 00:39:36,300
Saya masih mempunyai penunjuk kepada
Andy, elemen sebelumnya.

968
00:39:36,300 --> 00:39:39,430
Jadi, anda mempunyai akses, pada dasarnya,
serbuk roti, jika anda akan,

969
00:39:39,430 --> 00:39:41,500
kepada semua petunjuk yang diperlukan.

970
00:39:41,500 --> 00:39:43,710
>> Jadi, jika saya menghala ke arah
Andy dan saya juga menunjuk

971
00:39:43,710 --> 00:39:47,105
di Kristian, yang tangan
kini perlu ditegaskan di tempat lain?

972
00:39:47,105 --> 00:39:48,770

973
00:39:48,770 --> 00:39:51,960
Jadi Andy kini boleh menunjuk ke arah Julia.

974
00:39:51,960 --> 00:39:54,460
Julia kini boleh menunjuk ke arah Kristian.

975
00:39:54,460 --> 00:39:56,950
Kerana dia boleh menyalin saya
penunjuk tangan kanan itu.

976
00:39:56,950 --> 00:40:00,044
Dan yang berkesan meletakkan anda
kembali ke tempat ini di sini.

977
00:40:00,044 --> 00:40:02,460
Jadi ringkasnya, walaupun ini
membawa kita jenis buat selama-lamanya

978
00:40:02,460 --> 00:40:04,510
untuk benar-benar mengemaskini
senarai dikaitkan, menyedari

979
00:40:04,510 --> 00:40:06,580
bahawa operasi
adalah agak mudah.

980
00:40:06,580 --> 00:40:10,030
Ia satu, dua, tiga
baris kod akhirnya.

981
00:40:10,030 --> 00:40:12,780
Tetapi dibalut di sekeliling mereka
baris kod mungkin

982
00:40:12,780 --> 00:40:16,350
adalah sedikit logik yang berkesan
bertanya soalan, di mana kita?

983
00:40:16,350 --> 00:40:18,970
Adakah kita pada permulaan,
tengah-tengah, atau akhir?

984
00:40:18,970 --> 00:40:21,890
>> Sekarang, terdapat pasti beberapa lain
operasi kita mungkin melaksanakan.

985
00:40:21,890 --> 00:40:24,880
Dan gambar-gambar ini di sini hanya menggambarkan
apa yang kita lakukan dengan manusia.

986
00:40:24,880 --> 00:40:26,080
Bagaimana pula dengan penyingkiran?

987
00:40:26,080 --> 00:40:30,650
Jika saya mahu, contohnya,
mengeluarkan nombor 34 atau 55,

988
00:40:30,650 --> 00:40:34,680
Saya mungkin mempunyai jenis yang sama kod,
tetapi saya akan memerlukan satu atau dua langkah.

989
00:40:34,680 --> 00:40:36,110
Oleh kerana apa yang baru?

990
00:40:36,110 --> 00:40:40,460
Jika saya mengeluarkan seseorang pada akhirnya,
seperti nombor 55 dan kemudian 34,

991
00:40:40,460 --> 00:40:42,995
apa juga perlu berubah apabila saya berbuat demikian?

992
00:40:42,995 --> 00:40:44,870
Saya tidak evict--
apa nama anda lagi?

993
00:40:44,870 --> 00:40:45,380
>> PENONTON: Jack.

994
00:40:45,380 --> 00:40:46,255
>> DAVID J. MALAN: Jack.

995
00:40:46,255 --> 00:40:49,770
Saya bukan sahaja evict-- percuma Jack,
jadi literal panggilan percuma Jack, atau sekurang-kurangnya

996
00:40:49,770 --> 00:40:53,530
penunjuk sana juga, tetapi sekarang
apa yang perlu berubah dengan Peter?

997
00:40:53,530 --> 00:40:55,510
Tangannya lebih baik mula menunjuk ke bawah.

998
00:40:55,510 --> 00:40:59,300
Kerana sebaik sahaja saya menyeru percuma di
Jack, jika Peter masih menghala ke arah Jack

999
00:40:59,300 --> 00:41:02,530
dan saya dengan itu menyimpan menyeberangi
senarai dan akses penunjuk ini,

1000
00:41:02,530 --> 00:41:05,650
itulah apabila rakan segmentasi lama
kesalahan sebenarnya mungkin menendang.

1001
00:41:05,650 --> 00:41:07,860
Oleh kerana kita telah diberi
ingatan kembali kepada Jack.

1002
00:41:07,860 --> 00:41:10,760
>> Anda boleh tinggal di sana
canggung untuk hanya seketika.

1003
00:41:10,760 --> 00:41:13,410
Kerana kita mempunyai hanya pasangan
operasi terakhir yang perlu dipertimbangkan.

1004
00:41:13,410 --> 00:41:15,600
Mengeluarkan ketua senarai,
atau beginning-- dan ini yang

1005
00:41:15,600 --> 00:41:16,349
sedikit menjengkelkan.

1006
00:41:16,349 --> 00:41:19,640
Kerana kita perlu tahu bahawa Gabe
adalah jenis khas dalam program ini.

1007
00:41:19,640 --> 00:41:21,440
Kerana sesungguhnya, dia mempunyai penunjuk sendiri.

1008
00:41:21,440 --> 00:41:24,860
Dia bukan sahaja diacukan pada,
kerana hampir semua orang di sini.

1009
00:41:24,860 --> 00:41:28,112
>> Oleh itu, apabila ketua senarai adalah
dikeluarkan, yang tangan perlu menukar sekarang?

1010
00:41:28,112 --> 00:41:29,070
Apa nama anda lagi?

1011
00:41:29,070 --> 00:41:29,450
>> PENONTON: Christine.

1012
00:41:29,450 --> 00:41:31,408
>> DAVID J. MALAN: Saya mengerikan
pada nama, nampaknya.

1013
00:41:31,408 --> 00:41:34,011
Jadi Christine dan Gabe,
yang tangan perlu menukar

1014
00:41:34,011 --> 00:41:36,510
apabila kita cuba untuk membuang Christine,
nombor 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 buat Gabe.

1017
00:41:38,820 --> 00:41:40,950
Gabe yang akan menunjukkan,
mungkin, di nombor 9.

1018
00:41:40,950 --> 00:41:42,230

1019
00:41:42,230 --> 00:41:44,642
Tetapi apa yang akan datang harus berlaku?

1020
00:41:44,642 --> 00:41:46,600
PENONTON: Christine perlu
batal [didengar].

1021
00:41:46,600 --> 00:41:50,244
DAVID J. MALAN: OK, kita harus mungkin
make-- saya dengar "null" suatu tempat.

1022
00:41:50,244 --> 00:41:51,410
PENONTON: Null dan bebas itu.

1023
00:41:51,410 --> 00:41:51,855
DAVID J. MALAN: null apa?

1024
00:41:51,855 --> 00:41:53,074
PENONTON: Null dan bebas itu.

1025
00:41:53,074 --> 00:41:54,490
DAVID J. MALAN: Null dan bebas itu.

1026
00:41:54,490 --> 00:41:55,422
Jadi ini adalah sangat mudah.

1027
00:41:55,422 --> 00:41:58,380
Dan ia sempurna yang anda kini semacam
berdiri di sana, yang bukan kepunyaan.

1028
00:41:58,380 --> 00:42:00,430
Oleh kerana anda telah
terpisah dari senarai.

1029
00:42:00,430 --> 00:42:02,820
Anda telah berkesan telah
yatim dari senarai.

1030
00:42:02,820 --> 00:42:07,770
Dan kami lebih baik memanggil percuma sekarang
Christine memberi ingatan yang kembali.

1031
00:42:07,770 --> 00:42:10,240
Jika tidak setiap kali kita
memadam nod dari senarai

1032
00:42:10,240 --> 00:42:14,230
kita boleh membuat senarai
lebih pendek, tetapi tidak benar-benar mengurangkan

1033
00:42:14,230 --> 00:42:15,096
saiz dalam ingatan.

1034
00:42:15,096 --> 00:42:17,720
Dan jadi jika kita terus menambah dan
menambah, sambil menambah perkara-perkara ke dalam senarai,

1035
00:42:17,720 --> 00:42:19,280
komputer saya mungkin akan mendapat lebih perlahan
dan perlahan dan perlahan,

1036
00:42:19,280 --> 00:42:21,740
kerana saya kehabisan
ingatan, walaupun saya tidak benar-benar

1037
00:42:21,740 --> 00:42:25,580
menggunakan bytes Christine
memori lagi.

1038
00:42:25,580 --> 00:42:28,500
>> Jadi pada akhirnya terdapat lain
senario, penyingkiran course--

1039
00:42:28,500 --> 00:42:30,640
di tengah-tengah, pembuangan
pada akhirnya, seperti yang kita lihat.

1040
00:42:30,640 --> 00:42:32,348
Tetapi yang lebih menarik
Cabaran sekarang ialah

1041
00:42:32,348 --> 00:42:34,770
akan mempertimbangkan dengan tepat
apa masa yang berjalan adalah.

1042
00:42:34,770 --> 00:42:36,640
Jadi bukan sahaja anda boleh menyimpan anda
keping kertas, jika, Gabe,

1043
00:42:36,640 --> 00:42:38,640
anda tidak keberatan memberi
semua orang bola tekanan.

1044
00:42:38,640 --> 00:42:42,100
Terima kasih banyak untuk senarai dikaitkan kami
sukarelawan di sini, jika anda boleh.

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
soalan itu, jika saya boleh.

1048
00:42:51,110 --> 00:42:59,670
Kami telah melihat notasi ini sebelum,
O besar dan omega, batas atas

1049
00:42:59,670 --> 00:43:02,520
ganda lebih rendah pada
berjalan masa beberapa algoritma.

1050
00:43:02,520 --> 00:43:04,950
Jadi mari kita mempertimbangkan hanya
beberapa soalan.

1051
00:43:04,950 --> 00:43:07,090
>> Satu, dan kami berkata
sebelum ini, apa yang berjalan dengan

1052
00:43:07,090 --> 00:43:10,647
masa carian untuk
senarai dari segi O besar?

1053
00:43:10,647 --> 00:43:13,480
Apakah had atas pada berjalan
masa mencari senarai berpaut

1054
00:43:13,480 --> 00:43:16,340
seperti yang dilaksanakan oleh sukarelawan kami di sini?

1055
00:43:16,340 --> 00:43:17,820
Ia O besar n, linear.

1056
00:43:17,820 --> 00:43:20,630
Kerana dalam kes yang paling teruk,
unsur, seperti 55,

1057
00:43:20,630 --> 00:43:23,830
kita boleh mencari di mana mungkin
Jack adalah, semua cara di akhir.

1058
00:43:23,830 --> 00:43:28,250
Malangnya, tidak seperti array
kita tidak boleh mendapatkan mewah masa ini.

1059
00:43:28,250 --> 00:43:31,820
Meskipun semua manusia kita adalah
disusun dari unsur-unsur kecil, 5,

1060
00:43:31,820 --> 00:43:35,900
sepanjang jalan sehingga kepada unsur yang lebih besar,
55, itu biasanya sesuatu yang baik.

1061
00:43:35,900 --> 00:43:38,815
Tetapi apakah andaian bahawa
tidak lagi membolehkan kita lakukan?

1062
00:43:38,815 --> 00:43:39,775

1063
00:43:39,775 --> 00:43:40,650
PENONTON: [didengar]

1064
00:43:40,650 --> 00:43:40,920
DAVID J. MALAN: Katakanlah lagi?

1065
00:43:40,920 --> 00:43:41,800
PENONTON: Akses Rawak.

1066
00:43:41,800 --> 00:43:43,049
DAVID J. MALAN: Akses Rawak.

1067
00:43:43,049 --> 00:43:46,330
Dan seterusnya yang bermakna kita boleh tidak
lagi menggunakan sifar lemah, gerak hati,

1068
00:43:46,330 --> 00:43:49,365
dan obviousness menggunakan binari
mencari dan membahagi dan menakluk.

1069
00:43:49,365 --> 00:43:51,240
Kerana walaupun kita
manusia boleh jelas

1070
00:43:51,240 --> 00:43:54,610
melihat bahawa Andy atau Kristian
secara kasar di tengah-tengah senarai,

1071
00:43:54,610 --> 00:43:57,670
kita hanya tahu bahawa sebagai
komputer oleh penyiring senarai

1072
00:43:57,670 --> 00:43:59,029
dari awal.

1073
00:43:59,029 --> 00:44:00,570
Oleh itu, kita telah mengaku kalah bahawa akses secara rawak.

1074
00:44:00,570 --> 00:44:04,380
>> O begitu besar n sekarang adalah atas
terikat pada masa carian kami.

1075
00:44:04,380 --> 00:44:07,920
Bagaimana Omega carian kami?

1076
00:44:07,920 --> 00:44:11,535
Apa yang lebih rendah terikat pada mencari
untuk beberapa nombor dalam senarai ini?

1077
00:44:11,535 --> 00:44:12,410
PENONTON: [didengar]

1078
00:44:12,410 --> 00:44:13,040
DAVID J. MALAN: Katakanlah lagi?

1079
00:44:13,040 --> 00:44:13,420
PENONTON: Satu.

1080
00:44:13,420 --> 00:44:13,800
DAVID J. MALAN: Satu.

1081
00:44:13,800 --> 00:44:14,760
Jadi masa yang berterusan.

1082
00:44:14,760 --> 00:44:17,020
Dalam kes ini, Christine adalah
sesungguhnya pada permulaan senarai.

1083
00:44:17,020 --> 00:44:19,020
Dan yang kami cari
nombor 5, maka kami mendapati beliau.

1084
00:44:19,020 --> 00:44:19,787
Jadi tidak ada masalah besar.

1085
00:44:19,787 --> 00:44:22,370
Tetapi dia mendapat untuk berada di
bermula daripada senarai dalam kes ini.

1086
00:44:22,370 --> 00:44:23,745
Bagaimana pula sesuatu seperti Padam?

1087
00:44:23,745 --> 00:44:24,717

1088
00:44:24,717 --> 00:44:26,300
Bagaimana jika anda mahu memadam unsur?

1089
00:44:26,300 --> 00:44:29,200
Apakah batas atas dan batas yang lebih rendah
pada memotong sesuatu dari yang dikaitkan

1090
00:44:29,200 --> 00:44:29,699
senaraikan?

1091
00:44:29,699 --> 00:44:35,195

1092
00:44:35,195 --> 00:44:36,070
PENONTON: [didengar]

1093
00:44:36,070 --> 00:44:36,420
DAVID J. MALAN: Katakanlah lagi?

1094
00:44:36,420 --> 00:44:37,067
PENONTON: n.

1095
00:44:37,067 --> 00:44:38,900
DAVID J. MALAN: n adalah
sesungguhnya atas terikat.

1096
00:44:38,900 --> 00:44:41,700
Kerana dalam kes yang paling teruk kita cuba
memadam Jack, seperti kita lakukan.

1097
00:44:41,700 --> 00:44:43,050
Dia sepanjang jalan pada akhir.

1098
00:44:43,050 --> 00:44:45,419
Membawa kita selama-lamanya, atau
n langkah-langkah untuk mencari beliau.

1099
00:44:45,419 --> 00:44:46,460
Jadi itulah had atas.

1100
00:44:46,460 --> 00:44:47,430
Itulah linear, pasti.

1101
00:44:47,430 --> 00:44:50,970
Dan mana-mana yang terbaik berjalan masa, atau
batas-batas yang lebih rendah di mana-mana yang terbaik

1102
00:44:50,970 --> 00:44:51,975
akan menjadi masa yang berterusan.

1103
00:44:51,975 --> 00:44:54,600
Kerana mungkin kita cuba untuk memadam
Christine, dan kami hanya mendapat bertuah

1104
00:44:54,600 --> 00:44:55,558
dia pada mulanya.

1105
00:44:55,558 --> 00:44:56,350
Sekarang tunggu sebentar.

1106
00:44:56,350 --> 00:44:59,370
Gabe juga pada permulaan,
dan kami juga terpaksa mengemaskini Gabe.

1107
00:44:59,370 --> 00:45:01,150
Supaya bukan sahaja satu langkah.

1108
00:45:01,150 --> 00:45:04,210
Begitu juga ia memang tetap
masa, di mana-mana yang terbaik,

1109
00:45:04,210 --> 00:45:06,345
untuk menghapuskan unsur yang paling kecil?

1110
00:45:06,345 --> 00:45:07,360

1111
00:45:07,360 --> 00:45:10,960
Ia adalah, walaupun ia mungkin dua,
tiga, atau 100 baris kod,

1112
00:45:10,960 --> 00:45:14,000
jika ia jumlah yang sama
garis, tidak dalam beberapa gelung,

1113
00:45:14,000 --> 00:45:16,577
dan bebas daripada saiz
senarai itu, benar-benar.

1114
00:45:16,577 --> 00:45:18,660
Memadam elemen di
permulaan senarai,

1115
00:45:18,660 --> 00:45:21,940
walaupun kita perlu berurusan dengan
Gabe, masih masa yang berterusan.

1116
00:45:21,940 --> 00:45:24,220
>> Jadi ini kelihatan seperti
langkah besar ke belakang.

1117
00:45:24,220 --> 00:45:27,000
Dan apa yang membuang masa
jika, pada minggu satu dan minggu

1118
00:45:27,000 --> 00:45:30,250
sifar kita bukan sahaja
kod pseudokod tetapi kod sebenar

1119
00:45:30,250 --> 00:45:35,780
untuk melaksanakan sesuatu yang log
asas n, atau log masuk, sebaliknya, n, asas 2,

1120
00:45:35,780 --> 00:45:37,150
dari segi masa larian itu.

1121
00:45:37,150 --> 00:45:40,710
Jadi mengapa palang pintu yang kita mahu untuk memulakan
menggunakan sesuatu seperti senarai berpaut?

1122
00:45:40,710 --> 00:45:41,517
Yeah.

1123
00:45:41,517 --> 00:45:44,022
>> PENONTON: Jadi anda boleh menambah
unsur-unsur untuk array.

1124
00:45:44,022 --> 00:45:46,230
DAVID J. MALAN: Jadi, anda boleh
menambah unsur-unsur untuk array.

1125
00:45:46,230 --> 00:45:47,550
Dan ini juga adalah bertema.

1126
00:45:47,550 --> 00:45:49,740
Dan kita akan terus menyaksikan
ini, ini keseimbangan, banyak

1127
00:45:49,740 --> 00:45:51,573
seperti yang kita lihat yang
keseimbangan dengan jenis merge.

1128
00:45:51,573 --> 00:45:54,606
Kami benar-benar boleh mempercepatkan
mencari atau sorting, sebaliknya,

1129
00:45:54,606 --> 00:45:57,480
jika kita menghabiskan ruang sedikit lebih dan
mempunyai sebahagian tambahan memori yang

1130
00:45:57,480 --> 00:45:58,760
atau pelbagai jenis untuk merge.

1131
00:45:58,760 --> 00:46:01,270
Tetapi kita menghabiskan lebih banyak
ruang, tetapi kita menjimatkan masa.

1132
00:46:01,270 --> 00:46:04,820
Dalam kes ini, kami
menyerahkan masa tetapi kami

1133
00:46:04,820 --> 00:46:08,170
mendapat fleksibiliti,
dinamik jika anda akan,

1134
00:46:08,170 --> 00:46:10,280
yang boleh dikatakan ciri 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 apa rasa adalah berkait
menyenaraikan lebih mahal

1137
00:46:13,710 --> 00:46:15,700
dari segi ruang daripada array?

1138
00:46:15,700 --> 00:46:18,379

1139
00:46:18,379 --> 00:46:19,920
Di manakah ruang tambahan yang datang dari?

1140
00:46:19,920 --> 00:46:20,460
Yeah?

1141
00:46:20,460 --> 00:46:21,800
>> PENONTON: [didengar] pointer.

1142
00:46:21,800 --> 00:46:23,310
>> DAVID J. MALAN: Ya, kita
juga mempunyai penunjuk.

1143
00:46:23,310 --> 00:46:25,560
Jadi ini adalah minorly menjengkelkan
dalam yang tidak lagi berasa

1144
00:46:25,560 --> 00:46:27,780
Saya menyimpan hanya satu int
untuk mewakili sebuah int.

1145
00:46:27,780 --> 00:46:30,990
Saya menyimpan satu int dan
penunjuk, yang juga 32 bit.

1146
00:46:30,990 --> 00:46:33,470
Jadi, saya secara literal dua kali ganda
jumlah ruang yang terlibat.

1147
00:46:33,470 --> 00:46:36,040
Jadi itulah keseimbangan, tetapi
yang dalam kes int.

1148
00:46:36,040 --> 00:46:39,580
Katakan anda tidak menyimpan int,
tetapi andaikan setiap segi empat tepat ini

1149
00:46:39,580 --> 00:46:43,290
atau setiap manusia ini mewakili
satu perkataan, perkataan Inggeris yang

1150
00:46:43,290 --> 00:46:46,430
mungkin lima watak, 10
aksara, mungkin lebih.

1151
00:46:46,430 --> 00:46:49,940
Kemudian sambil menambah hanya 32 lebih bit
mungkin kurang daripada satu masalah besar.

1152
00:46:49,940 --> 00:46:52,160
>> Bagaimana jika setiap pelajar
dalam demonstrasi

1153
00:46:52,160 --> 00:46:55,107
adalah benar-benar structs pelajar yang
mempunyai nama dan rumah-rumah dan mungkin

1154
00:46:55,107 --> 00:46:57,065
nombor telefon dan Twitter
mengendalikan dan sebagainya.

1155
00:46:57,065 --> 00:46:59,564
Jadi semua bidang kami mula
bercakap tentang hari lain,

1156
00:46:59,564 --> 00:47:02,410
lebih kurang masalah besar sebagai
nod kami mendapatkan lebih banyak menarik

1157
00:47:02,410 --> 00:47:05,972
dan besar untuk berbelanja, eh, tambahan
penunjuk hanya untuk menghubungkan mereka bersama-sama.

1158
00:47:05,972 --> 00:47:07,180
Tetapi sesungguhnya, ia adalah keseimbangan.

1159
00:47:07,180 --> 00:47:09,560
Dan sesungguhnya, kod adalah
kompleks lebih, kerana anda akan

1160
00:47:09,560 --> 00:47:11,770
lihat dengan penyiring melalui
bahawa contoh tertentu.

1161
00:47:11,770 --> 00:47:14,302
Tetapi bagaimana jika terdapat
beberapa kaedah berpotensi suci di sini.

1162
00:47:14,302 --> 00:47:17,010
Bagaimana jika kita tidak mengambil langkah yang
ke belakang tetapi satu langkah besar ke hadapan

1163
00:47:17,010 --> 00:47:19,180
dan melaksanakan data yang
struktur melalui mana kita

1164
00:47:19,180 --> 00:47:22,870
mempunyai unsur-unsur seperti Jack atau
Christine atau mana-mana elemen-elemen lain

1165
00:47:22,870 --> 00:47:25,870
dalam tatasusunan ini dalam masa yang tetap benar?

1166
00:47:25,870 --> 00:47:26,920
Cari adalah tetap.

1167
00:47:26,920 --> 00:47:28,320
Padam adalah tetap.

1168
00:47:28,320 --> 00:47:29,570
Masukkan adalah tetap.

1169
00:47:29,570 --> 00:47:32,260
Semua operasi ini adalah malar.

1170
00:47:32,260 --> 00:47:33,750
Itu adalah kaedah berpotensi suci kita.

1171
00:47:33,750 --> 00:47:36,690
Dan di situlah kita
akan mengambil masa yang akan datang.

1172
00:47:36,690 --> 00:47:38,600
Jumpa anda kemudian.

1173
00:47:38,600 --> 00:47:39,371