1
00:00:00,000 --> 00:00:10,900

2
00:00:10,900 --> 00:00:15,860
>> SPEAKER 1: Baiklah, jadi ini adalah
CS50 ini adalah akhir minggu lima.

3
00:00:15,860 --> 00:00:19,220
Dan ingat bahwa terakhir kali kita
mulai melihat data pengujian

4
00:00:19,220 --> 00:00:22,310
struktur yang mulai memecahkan
masalah, yang mulai memperkenalkan

5
00:00:22,310 --> 00:00:25,640
masalah baru, tapi kunci untuk ini
adalah semacam threading yang kita

6
00:00:25,640 --> 00:00:27,940
mulai melakukan dari node ke node.

7
00:00:27,940 --> 00:00:30,085
Jadi ini tentu saja adalah
daftar sendiri-sendiri terkait.

8
00:00:30,085 --> 00:00:31,960
Dan oleh tunggal terkait,
Maksud saya hanya ada satu

9
00:00:31,960 --> 00:00:33,380
benang antara masing-masing node.

10
00:00:33,380 --> 00:00:35,890
Ternyata keluar yang dapat Anda lakukan pengujian
hal-hal seperti daftar ganda terkait

11
00:00:35,890 --> 00:00:38,470
dimana Anda memiliki panah
akan di kedua arah, yang

12
00:00:38,470 --> 00:00:40,320
dapat membantu dengan efisiensi tertentu.

13
00:00:40,320 --> 00:00:42,000
Tapi ini memecahkan masalah?

14
00:00:42,000 --> 00:00:43,500
Apa masalah itu ini memecahkan?

15
00:00:43,500 --> 00:00:46,620
Mengapa kita peduli pada hari Senin?

16
00:00:46,620 --> 00:00:49,820
Mengapa, dalam teori, yang kita peduli pada hari Senin?

17
00:00:49,820 --> 00:00:50,630
Apa fungsinya?

18
00:00:50,630 --> 00:00:51,950
>> AUDIENCE: Kami secara dinamis dapat mengubah ukurannya.

19
00:00:51,950 --> 00:00:53,740
>> SPEAKER 1: OK, jadi kita bisa
dinamis mengubah ukurannya.

20
00:00:53,740 --> 00:00:54,710
Dilakukan dengan baik Anda berdua.

21
00:00:54,710 --> 00:00:57,560
Jadi Anda secara dinamis dapat mengubah ukuran ini
struktur data, sedangkan array,

22
00:00:57,560 --> 00:01:00,760
ingat, Anda harus tahu
priori berapa banyak ruang yang Anda inginkan

23
00:01:00,760 --> 00:01:03,870
dan jika Anda membutuhkan sedikit lebih
ruang, Anda jenis kurang beruntung.

24
00:01:03,870 --> 00:01:05,560
Anda harus membuat array baru.

25
00:01:05,560 --> 00:01:07,893
Anda harus memindahkan semua Anda
data dari satu ke yang lain,

26
00:01:07,893 --> 00:01:10,600
akhirnya membebaskan array tua
jika Anda bisa, dan kemudian lanjutkan.

27
00:01:10,600 --> 00:01:13,891
Yang hanya merasa sangat mahal dan sangat
tidak efisien, dan memang bisa.

28
00:01:13,891 --> 00:01:14,890
Tapi ini tidak semua baik.

29
00:01:14,890 --> 00:01:18,180
Kami membayar harga, apa yang salah
dari harga lebih jelas kami

30
00:01:18,180 --> 00:01:20,550
membayar dengan menggunakan linked list?

31
00:01:20,550 --> 00:01:22,825
>> AUDIENCE: Kita harus menggunakan
ruang ganda untuk masing-masing.

32
00:01:22,825 --> 00:01:25,200
SPEAKER 1: Ya, jadi kita perlu
setidaknya dua kali lebih banyak ruang.

33
00:01:25,200 --> 00:01:27,700
Bahkan, saya menyadari gambar ini
bahkan sedikit menyesatkan,

34
00:01:27,700 --> 00:01:32,200
karena pada CS50 IDE di banyak modern
komputer, pointer atau alamat

35
00:01:32,200 --> 00:01:33,700
tidak sebenarnya empat byte.

36
00:01:33,700 --> 00:01:36,090
Ini sangat sering ini
hari delapan byte, yang

37
00:01:36,090 --> 00:01:38,530
berarti bagian bawah yang paling
persegi panjang ada dalam realitas

38
00:01:38,530 --> 00:01:40,900
adalah jenis dua kali
besar seperti apa yang saya ditarik,

39
00:01:40,900 --> 00:01:44,409
yang berarti Anda menggunakan tiga kali
banyak ruang seperti yang kita sebaliknya.

40
00:01:44,409 --> 00:01:46,700
Sekarang pada saat yang sama, kami
masih berbicara byte, kan?

41
00:01:46,700 --> 00:01:49,140
Kami tidak harus berbicara
megabyte atau gigabyte,

42
00:01:49,140 --> 00:01:51,000
kecuali struktur data mendapatkan besar.

43
00:01:51,000 --> 00:01:54,510
>> Dan jadi hari ini kita mulai untuk mempertimbangkan
bagaimana kita bisa mengeksplorasi data

44
00:01:54,510 --> 00:01:57,310
lebih efisien jika di
Bahkan data akan lebih besar.

45
00:01:57,310 --> 00:02:00,360
Tapi mari kita coba canonicalize
operasi pertama

46
00:02:00,360 --> 00:02:02,460
yang dapat Anda lakukan pada ini
jenis struktur data.

47
00:02:02,460 --> 00:02:04,790
Jadi sesuatu seperti terkait
daftar umumnya mendukung

48
00:02:04,790 --> 00:02:07,514
operasi seperti menghapus,
masukkan, dan mencari.

49
00:02:07,514 --> 00:02:08,639
Dan apa yang saya maksud dengan itu?

50
00:02:08,639 --> 00:02:11,222
Itu hanya berarti bahwa biasanya,
jika orang yang menggunakan linked list,

51
00:02:11,222 --> 00:02:14,287
mereka atau orang lain telah menerapkan
fungsi seperti menghapus, menyisipkan,

52
00:02:14,287 --> 00:02:16,120
dan pencarian, sehingga Anda dapat
benar-benar melakukan sesuatu

53
00:02:16,120 --> 00:02:18,030
berguna dengan struktur data.

54
00:02:18,030 --> 00:02:20,760
Jadi mari kita lihat
bagaimana kita bisa menerapkan

55
00:02:20,760 --> 00:02:24,530
beberapa kode untuk sebuah linked list sebagai berikut.

56
00:02:24,530 --> 00:02:27,885
>> Jadi ini hanya beberapa kode C,
bahkan bukan program lengkap

57
00:02:27,885 --> 00:02:29,260
bahwa saya benar-benar cepat melecut.

58
00:02:29,260 --> 00:02:32,300
Ini tidak online dalam distribusi
kode, karena tidak akan benar-benar menjalankan.

59
00:02:32,300 --> 00:02:33,790
Tapi melihat aku baru saja
dengan komentar mengatakan,

60
00:02:33,790 --> 00:02:36,130
dot dot dot, ada sesuatu
ada, dot dot dot, sesuatu di sana.

61
00:02:36,130 --> 00:02:38,410
Dan mari kita lihat saja
apa bagian juicy.

62
00:02:38,410 --> 00:02:40,790
Jadi pada baris ketiga,
ingat bahwa ini adalah sekarang

63
00:02:40,790 --> 00:02:45,960
kami mengusulkan mendeklarasikan node terakhir
waktu, salah satu dari mereka objek persegi panjang.

64
00:02:45,960 --> 00:02:48,790
Ini memiliki int yang akan kita sebut N,
tapi kita bisa menyebutnya apa-apa,

65
00:02:48,790 --> 00:02:51,920
dan kemudian bintang struct simpul disebut berikutnya.

66
00:02:51,920 --> 00:02:55,520
Dan hanya harus jelas, bahwa kedua
line, on line enam, apa itu?

67
00:02:55,520 --> 00:02:57,930
Apa itu lakukan bagi kita?

68
00:02:57,930 --> 00:03:01,044
Karena pasti terlihat lebih
samar dari variabel kami biasa.

69
00:03:01,044 --> 00:03:02,740
>> AUDIENCE: Itu membuat pindah satu.

70
00:03:02,740 --> 00:03:04,650
>> SPEAKER 1: Itu membuat pindah satu.

71
00:03:04,650 --> 00:03:08,580
Dan untuk lebih tepatnya,
itu akan menyimpan alamat

72
00:03:08,580 --> 00:03:11,582
dari node yang dimaksudkan untuk menjadi
semantis sebelahnya, kan?

73
00:03:11,582 --> 00:03:13,540
Sehingga tidak akan
tentu memindahkan apapun.

74
00:03:13,540 --> 00:03:15,290
Ini hanya akan
menyimpan nilai, yang

75
00:03:15,290 --> 00:03:17,170
akan menjadi alamat
dari beberapa simpul lainnya,

76
00:03:17,170 --> 00:03:20,810
dan itulah sebabnya kami telah mengatakan struct
Bintang node, bintang yang menunjukkan

77
00:03:20,810 --> 00:03:22,370
pointer atau alamat.

78
00:03:22,370 --> 00:03:26,390
OK, jadi sekarang jika Anda menganggap bahwa kita memiliki
N ini tersedia bagi kita, dan mari kita

79
00:03:26,390 --> 00:03:29,490
berasumsi bahwa orang lain memiliki
dimasukkan sejumlah besar bilangan bulat

80
00:03:29,490 --> 00:03:30,400
menjadi linked list.

81
00:03:30,400 --> 00:03:35,640
Dan yang linked list adalah
ditunjukkan oleh beberapa titik

82
00:03:35,640 --> 00:03:39,040
variabel yang disebut daftar yang
disahkan pada di sini sebagai parameter,

83
00:03:39,040 --> 00:03:43,120
bagaimana aku pergi tentang garis
14 melaksanakan pencarian?

84
00:03:43,120 --> 00:03:45,990
Dengan kata lain, jika saya menerapkan
Fungsi yang tujuan dalam hidup

85
00:03:45,990 --> 00:03:48,889
adalah mengambil int dan kemudian
mulai dari linked list,

86
00:03:48,889 --> 00:03:50,430
yang merupakan pointer ke linked list.

87
00:03:50,430 --> 00:03:52,992
Seperti pertama, yang saya pikir David
adalah relawan kami pada Senin,

88
00:03:52,992 --> 00:03:54,700
ia menunjuk
Seluruh terkait daftar,

89
00:03:54,700 --> 00:03:57,820
itu seolah-olah kita sedang melewati
David sebagai argumen kami di sini.

90
00:03:57,820 --> 00:03:59,990
Bagaimana kita pergi tentang melintasi daftar ini?

91
00:03:59,990 --> 00:04:04,640
Nah, ternyata bahwa meskipun
pointer relatif baru sekarang untuk kami,

92
00:04:04,640 --> 00:04:07,010
kita bisa melakukan ini relatif
tedeng aling-aling.

93
00:04:07,010 --> 00:04:09,500
>> Aku akan pergi ke depan dan
mendeklarasikan variabel sementara yang

94
00:04:09,500 --> 00:04:12,364
dengan konvensi hanya akan
disebut pointer, atau PTR,

95
00:04:12,364 --> 00:04:14,030
tapi Anda bisa menyebutnya apa pun yang Anda inginkan.

96
00:04:14,030 --> 00:04:16,470
Dan aku akan menginisialisasi
untuk awal daftar.

97
00:04:16,470 --> 00:04:20,050
Sehingga Anda dapat jenis menganggap ini
seperti saya guru hari lain,

98
00:04:20,050 --> 00:04:23,580
jenis menunjuk seseorang
antara manusia kami sebagai relawan.

99
00:04:23,580 --> 00:04:26,470
Jadi aku variabel sementara itu
hanya menunjuk pada hal yang sama

100
00:04:26,470 --> 00:04:31,390
bahwa kami kebetulan bernama
relawan David juga menunjukkan.

101
00:04:31,390 --> 00:04:35,440
Sekarang sementara pointer
tidak nol, karena ingat

102
00:04:35,440 --> 00:04:40,350
nol yang beberapa nilai sentinel khusus
demarcates akhir daftar,

103
00:04:40,350 --> 00:04:44,280
jadi sementara saya tidak menunjuk pada
tanah seperti relawan terakhir kami

104
00:04:44,280 --> 00:04:47,190
adalah, mari kita pergi ke depan
dan melakukan hal berikut.

105
00:04:47,190 --> 00:04:51,820
Jika pointer-- dan sekarang aku agak ingin
untuk melakukan apa yang kita lakukan dengan siswa

106
00:04:51,820 --> 00:04:57,410
structure-- jika pointer dot berikutnya
equals-- bukan, jika pointer dot N sama

107
00:04:57,410 --> 00:05:02,290
sama dengan variabel N,
Argumen yang telah disahkan pada,

108
00:05:02,290 --> 00:05:05,370
maka saya ingin pergi ke depan
dan mengatakan kembali benar.

109
00:05:05,370 --> 00:05:11,020
Saya telah menemukan jumlah N dalam
salah satu simpul dari linked list saya.

110
00:05:11,020 --> 00:05:13,500
Tapi titik tidak lagi
bekerja dalam konteks ini,

111
00:05:13,500 --> 00:05:17,260
karena pointer, PTR, adalah
memang pointer, alamat,

112
00:05:17,260 --> 00:05:20,632
kita benar-benar bisa mengagumkan
menggunakan akhirnya sepotong sintaks

113
00:05:20,632 --> 00:05:22,590
jenis merek
intuisi dan benar-benar

114
00:05:22,590 --> 00:05:27,870
menggunakan panah di sini, yang berarti pergi dari
alamat ke integer ada di.

115
00:05:27,870 --> 00:05:30,160
Jadi itu sangat mirip dalam
semangat untuk operator dot,

116
00:05:30,160 --> 00:05:33,860
tetapi karena pointer tidak pointer
dan bukan struct itu sendiri,

117
00:05:33,860 --> 00:05:35,380
kita hanya menggunakan panah.

118
00:05:35,380 --> 00:05:40,620
>> Jadi jika node saat bahwa Aku,
variabel sementara, saya menunjuk

119
00:05:40,620 --> 00:05:43,060
tidak N, apa yang ingin saya lakukan?

120
00:05:43,060 --> 00:05:45,910
Nah, dengan relawan manusia saya
yang kita miliki di sini hari yang lain,

121
00:05:45,910 --> 00:05:49,710
jika manusia pertama saya adalah tidak yang saya
inginkan, dan mungkin manusia kedua tidak

122
00:05:49,710 --> 00:05:52,660
yang saya inginkan, dan yang ketiga, saya
perlu menjaga fisik bergerak.

123
00:05:52,660 --> 00:05:54,690
Seperti bagaimana aku melangkah melalui daftar?

124
00:05:54,690 --> 00:05:57,470
Ketika kita memiliki sebuah array, Anda
hanya melakukan seperti saya plus plus.

125
00:05:57,470 --> 00:06:03,660
Tapi dalam kasus ini, itu sudah cukup untuk
melakukan pointer, mendapat, pointer, berikutnya.

126
00:06:03,660 --> 00:06:07,580
Dengan kata lain, kolom berikutnya
seperti semua tangan kiri

127
00:06:07,580 --> 00:06:10,880
bahwa relawan kami pada Senin
yang menggunakan untuk menunjuk pada beberapa simpul lainnya.

128
00:06:10,880 --> 00:06:12,890
Mereka adalah tetangga mereka berikutnya.

129
00:06:12,890 --> 00:06:17,060
>> Jadi jika saya ingin melangkah melalui daftar ini,
Aku tidak bisa hanya melakukan saya plus plus lagi,

130
00:06:17,060 --> 00:06:20,120
Saya bukannya harus mengatakan
Aku, pointer, akan

131
00:06:20,120 --> 00:06:24,650
untuk sama apa pun bidang berikutnya adalah,
bidang berikutnya, kolom berikutnya adalah,

132
00:06:24,650 --> 00:06:28,350
berikut semua orang tangan kiri
yang kita miliki di panggung menunjuk

133
00:06:28,350 --> 00:06:30,000
untuk beberapa nilai berikutnya.

134
00:06:30,000 --> 00:06:32,590
Dan jika saya melewati
bahwa seluruh iterasi,

135
00:06:32,590 --> 00:06:39,330
dan akhirnya, aku memukul nol tidak memiliki
ditemukan N belum, aku hanya kembali palsu.

136
00:06:39,330 --> 00:06:44,100
Jadi sekali lagi, semua yang kita lakukan di sini,
sesuai gambar saat yang lalu,

137
00:06:44,100 --> 00:06:47,840
mulai dengan menunjuk pada
mulai dari daftar mungkin.

138
00:06:47,840 --> 00:06:50,970
Dan kemudian saya cek, adalah nilai
Saya mencari sama dengan sembilan?

139
00:06:50,970 --> 00:06:52,650
Jika demikian, saya kembali benar dan aku sudah selesai.

140
00:06:52,650 --> 00:06:56,450
Jika tidak, saya update tanganku,
AKA pointer, untuk menunjuk

141
00:06:56,450 --> 00:06:59,540
di lokasi panah depan, dan
maka lokasi panah depan,

142
00:06:59,540 --> 00:07:00,480
dan berikutnya.

143
00:07:00,480 --> 00:07:03,770
Aku hanya berjalan melalui array ini.

144
00:07:03,770 --> 00:07:06,010
>> Jadi sekali lagi, siapa yang peduli?

145
00:07:06,010 --> 00:07:07,861
Seperti apa ini bahan untuk?

146
00:07:07,861 --> 00:07:10,360
Nah, ingat bahwa kami memperkenalkan
gagasan stack, yang

147
00:07:10,360 --> 00:07:15,400
adalah data abstrak ketik sejauh itu
bukan hal C, itu bukan hal yang CS50,

148
00:07:15,400 --> 00:07:19,430
itu ide yang abstrak, ide ini
susun hal-hal di atas satu sama lain

149
00:07:19,430 --> 00:07:21,820
yang dapat diterapkan di
tandan cara yang berbeda.

150
00:07:21,820 --> 00:07:25,600
Dan salah satu cara kita diusulkan adalah dengan
array, atau dengan linked list.

151
00:07:25,600 --> 00:07:29,570
Dan ternyata kanonis, sebuah
tumpukan mendukung setidaknya dua operasi.

152
00:07:29,570 --> 00:07:32,320
Dan kata-kata buzz push, untuk
mendorong sesuatu ke stack,

153
00:07:32,320 --> 00:07:34,770
seperti nampan baru di
ruang makan, atau pop,

154
00:07:34,770 --> 00:07:39,000
yang berarti untuk menghapus paling atas
baki dari tumpukan di makan

155
00:07:39,000 --> 00:07:41,500
aula, dan kemudian mungkin beberapa
operasi lain juga.

156
00:07:41,500 --> 00:07:45,770
Jadi bagaimana mungkin kita mendefinisikan struktur
bahwa kita sekarang sedang menelepon stack?

157
00:07:45,770 --> 00:07:50,020
>> Nah, kita memiliki semua yang diperlukan dalam
sintaks yang kita miliki di C. saya katakan,

158
00:07:50,020 --> 00:07:53,830
memberikan definisi jenis
struct dalam stack,

159
00:07:53,830 --> 00:07:58,030
Aku akan katakan adalah array, dari
Seluruh sekelompok angka dan kemudian ukuran.

160
00:07:58,030 --> 00:08:00,930
Jadi dengan kata lain, jika saya ingin
untuk menerapkan ini dalam kode,

161
00:08:00,930 --> 00:08:03,830
biarkan aku pergi dan hanya jenis
menggambar apa ini mengatakan.

162
00:08:03,830 --> 00:08:06,317
Jadi ini mengatakan, beri saya
Struktur yang punya array,

163
00:08:06,317 --> 00:08:09,400
dan saya tidak tahu apa kapasitas,
itu tampaknya beberapa konstan bahwa saya telah

164
00:08:09,400 --> 00:08:10,858
didefinisikan di tempat lain, dan itu baik-baik saja.

165
00:08:10,858 --> 00:08:15,260
Tapi rasa itu hanya satu,
dua, tiga, empat, lima.

166
00:08:15,260 --> 00:08:16,700
Jadi kapasitas 5.

167
00:08:16,700 --> 00:08:21,730
Unsur ini dalam saya
struktur akan disebut nomor.

168
00:08:21,730 --> 00:08:24,020
Dan kemudian saya perlu satu
variabel lain rupanya

169
00:08:24,020 --> 00:08:27,814
disebut ukuran yang awalnya aku akan
menetapkan diinisialisasi ke nol.

170
00:08:27,814 --> 00:08:29,730
Jika tidak ada di
stack, ukuran adalah nol,

171
00:08:29,730 --> 00:08:31,420
dan itu nilai-nilai sampah dalam jumlah.

172
00:08:31,420 --> 00:08:33,450
Aku tidak tahu apa yang ada di sana hanya belum.

173
00:08:33,450 --> 00:08:36,059
>> Jadi jika saya ingin mendorong
sesuatu ke stack,

174
00:08:36,059 --> 00:08:40,780
kira saya sebut mendorong fungsi, dan
Saya katakan mendorong 50, seperti nomor 50,

175
00:08:40,780 --> 00:08:44,090
di mana akan Anda usulkan
Aku menarik dalam array ini?

176
00:08:44,090 --> 00:08:47,124
Ada lima kemungkinan jawaban yang berbeda.

177
00:08:47,124 --> 00:08:48,790
Di mana Anda ingin mendorong jumlah 50?

178
00:08:48,790 --> 00:08:51,899
Jika tujuan di sini, sekali lagi, sebut
fungsi push, lulus dalam argumen

179
00:08:51,899 --> 00:08:52,940
50, di mana saya menaruhnya?

180
00:08:52,940 --> 00:08:55,680

181
00:08:55,680 --> 00:08:59,052
Lima possible-- 20% kemungkinan
menebak dengan benar.

182
00:08:59,052 --> 00:08:59,896
Iya nih?

183
00:08:59,896 --> 00:09:00,740
>> AUDIENCE: Jauh tepat.

184
00:09:00,740 --> 00:09:01,990
>> SPEAKER 1: Jauh tepat.

185
00:09:01,990 --> 00:09:08,359
Sekarang ada kesempatan 25%
menebak dengan benar.

186
00:09:08,359 --> 00:09:09,650
Jadi yang benar-benar akan baik-baik.

187
00:09:09,650 --> 00:09:12,770
Dengan konvensi, saya akan mengatakan dengan sebuah array,
kita umumnya akan mulai di sebelah kiri,

188
00:09:12,770 --> 00:09:14,519
tapi kita bisa pasti
mulai dari kanan.

189
00:09:14,519 --> 00:09:17,478
Jadi spoiler di sini akan saya
mungkin akan menggambar di sebelah kiri,

190
00:09:17,478 --> 00:09:20,060
sama seperti di array normal di mana
Saya mulai dari kiri ke kanan.

191
00:09:20,060 --> 00:09:21,780
Tapi jika Anda dapat flip
aritmatika, baik.

192
00:09:21,780 --> 00:09:23,060
Hanya saja tidak konvensional.

193
00:09:23,060 --> 00:09:24,880
OK, saya harus membuat satu
lebih banyak perubahan meskipun.

194
00:09:24,880 --> 00:09:27,710
Sekarang aku sudah mendorong sesuatu
ke stack, apa berikutnya?

195
00:09:27,710 --> 00:09:29,400
>> Baiklah, saya harus kenaikan ukuran.

196
00:09:29,400 --> 00:09:32,600
Jadi biarkan aku pergi ke depan dan hanya
memperbarui ini, yang nol.

197
00:09:32,600 --> 00:09:35,950
Dan bukannya sekarang, aku akan
untuk dimasukkan ke dalam nilai satu.

198
00:09:35,950 --> 00:09:39,460
Dan sekarang kira saya mendorong lain
nomor ke stack, seperti 51.

199
00:09:39,460 --> 00:09:42,680
Yah, aku harus membuat satu lagi
perubahan, yang hingga ukuran dua.

200
00:09:42,680 --> 00:09:46,100
Dan kemudian kira saya mendorong satu lagi
nomor ke dalam stack seperti 61,

201
00:09:46,100 --> 00:09:52,530
sekarang saya harus memperbarui ukuran yang lebih
waktu, dan mendapatkan nilai 3 sebagai ukuran.

202
00:09:52,530 --> 00:09:54,690
Dan sekarang kira saya sebut pop.

203
00:09:54,690 --> 00:09:57,250
Sekarang pop, dengan konvensi,
tidak mengambil argumen.

204
00:09:57,250 --> 00:10:00,430
Dengan tumpukan, keseluruhan
titik metafora tray

205
00:10:00,430 --> 00:10:03,450
adalah bahwa Anda tidak memiliki kebijaksanaan
pergi mendapatkan nampan itu, semua dapat Anda lakukan

206
00:10:03,450 --> 00:10:06,330
adalah pop yang paling atas dari
stack, hanya karena.

207
00:10:06,330 --> 00:10:08,010
Itulah yang ini struktur data tidak.

208
00:10:08,010 --> 00:10:12,250
>> Jadi dengan logika bahwa jika saya
mengatakan pop, apa yang datang dari?

209
00:10:12,250 --> 00:10:13,080
Jadi 61.

210
00:10:13,080 --> 00:10:15,402
Jadi apa yang sebenarnya adalah komputer
akan dilakukan di memori?

211
00:10:15,402 --> 00:10:16,610
Apa memiliki kode saya lakukan?

212
00:10:16,610 --> 00:10:20,330
Apa yang akan Anda usulkan
kita mengubah di layar?

213
00:10:20,330 --> 00:10:23,410
Apa yang harus berubah?

214
00:10:23,410 --> 00:10:24,960
Maaf?

215
00:10:24,960 --> 00:10:26,334
Jadi kita menyingkirkan 61.

216
00:10:26,334 --> 00:10:27,500
Jadi saya pasti bisa melakukan itu.

217
00:10:27,500 --> 00:10:28,640
Dan saya dapat menyingkirkan 61.

218
00:10:28,640 --> 00:10:30,980
Dan kemudian apa yang lainnya
perubahan harus terjadi?

219
00:10:30,980 --> 00:10:33,160
Ukuran mungkin harus kembali ke dua.

220
00:10:33,160 --> 00:10:34,210
Dan jadi itu baik-baik saja.

221
00:10:34,210 --> 00:10:36,690
Tapi tunggu dulu, ukuran
beberapa saat yang lalu adalah tiga.

222
00:10:36,690 --> 00:10:38,240
Mari kita hanya melakukan sebuah pemeriksaan cepat.

223
00:10:38,240 --> 00:10:41,810
Bagaimana kita tahu bahwa kita
diinginkannya untuk menyingkirkan 61?

224
00:10:41,810 --> 00:10:42,760
Karena kita muncul.

225
00:10:42,760 --> 00:10:46,450
Dan jadi saya memiliki ukuran properti kedua ini.

226
00:10:46,450 --> 00:10:48,470
>> Tunggu sebentar, aku
berpikir kembali ke minggu kedua

227
00:10:48,470 --> 00:10:51,660
ketika kita mulai berbicara tentang
array, di mana ini adalah lokasi nol,

228
00:10:51,660 --> 00:10:55,920
ini adalah lokasi satu, ini adalah lokasi
dua, ini adalah lokasi tiga, empat,

229
00:10:55,920 --> 00:10:58,460
sepertinya
hubungan antara ukuran

230
00:10:58,460 --> 00:11:02,780
dan elemen yang saya ingin menghapus
dari array tampaknya hanya menjadi apa?

231
00:11:02,780 --> 00:11:05,120
Ukuran minus satu.

232
00:11:05,120 --> 00:11:07,786
Dan itulah bagaimana sebagai manusia
kita tahu 61 datang pertama.

233
00:11:07,786 --> 00:11:09,160
Bagaimana komputer akan tahu?

234
00:11:09,160 --> 00:11:11,701
Ketika kode Anda, di mana Anda mungkin
ingin melakukan ukuran minus satu,

235
00:11:11,701 --> 00:11:14,950
jadi tiga minus satu adalah dua, dan yang
berarti kita ingin menyingkirkan 61.

236
00:11:14,950 --> 00:11:18,000
Dan kemudian kita memang bisa memperbarui
ukuran sehingga ukuran yang sekarang

237
00:11:18,000 --> 00:11:20,300
pergi dari tiga sampai hanya dua.

238
00:11:20,300 --> 00:11:24,520
Dan hanya untuk menjadi bertele-tele, aku akan
mengusulkan bahwa aku sudah selesai, kan?

239
00:11:24,520 --> 00:11:27,660
Anda diusulkan intuitif
benar aku harus menyingkirkan 61.

240
00:11:27,660 --> 00:11:30,700
Tapi belum saya jenis
semacam menyingkirkan 61?

241
00:11:30,700 --> 00:11:33,790
Saya lupa efektif
bahwa itu benar-benar ada.

242
00:11:33,790 --> 00:11:37,680
Dan berpikir kembali ke PSET4, jika Anda sudah membaca
artikel tentang forensik, PDF

243
00:11:37,680 --> 00:11:40,780
bahwa kita harus kalian baca, atau Anda
akan membaca minggu ini untuk PSET4.

244
00:11:40,780 --> 00:11:44,300
Ingat bahwa ini sebenarnya erat dengan
seluruh ide dari komputer forensik.

245
00:11:44,300 --> 00:11:47,820
Apa komputer umumnya dilakukan adalah
itu hanya lupa di mana sesuatu adalah,

246
00:11:47,820 --> 00:11:51,300
tetapi tidak masuk dan seperti
mencoba untuk menggaruknya keluar atau menimpa

247
00:11:51,300 --> 00:11:54,560
mereka bit dengan nol dan satu
atau pola acak lainnya

248
00:11:54,560 --> 00:11:56,690
kecuali Anda sendiri melakukannya dengan sengaja.

249
00:11:56,690 --> 00:11:58,930
Jadi intuisi Anda adalah
Baiklah, mari kita menyingkirkan 61.

250
00:11:58,930 --> 00:12:00,650
Namun dalam kenyataannya, kita tidak perlu repot-repot.

251
00:12:00,650 --> 00:12:04,040
Kita hanya perlu lupa bahwa
itu ada dengan mengubah ukuran kami.

252
00:12:04,040 --> 00:12:05,662
>> Sekarang ada masalah dengan tumpukan ini.

253
00:12:05,662 --> 00:12:07,620
Jika saya terus mendorong hal-hal
ke stack, apa

254
00:12:07,620 --> 00:12:11,167
jelas akan terjadi
hanya dalam waktu beberapa saat?

255
00:12:11,167 --> 00:12:12,500
Kita akan kehabisan ruang.

256
00:12:12,500 --> 00:12:13,580
Dan apa yang kita lakukan?

257
00:12:13,580 --> 00:12:14,680
Kami jenis kacau.

258
00:12:14,680 --> 00:12:19,000
Implementasi ini tidak membiarkan
kita mengubah ukuran array, karena menggunakan

259
00:12:19,000 --> 00:12:21,240
sintaks ini, jika Anda
berpikir kembali ke minggu kedua,

260
00:12:21,240 --> 00:12:23,520
setelah Anda dinyatakan
ukuran array,

261
00:12:23,520 --> 00:12:26,780
kami belum melihat mekanisme belum mana
Anda dapat mengubah ukuran array.

262
00:12:26,780 --> 00:12:29,020
Dan memang C tidak memiliki fitur itu.

263
00:12:29,020 --> 00:12:32,524
Jika Anda mengatakan memberi saya lima
Nths, menyebut mereka nomor,

264
00:12:32,524 --> 00:12:33,940
itu semua Anda akan mendapatkannya.

265
00:12:33,940 --> 00:12:38,790
Jadi kita lakukan sekarang pada hari Senin, memiliki
kemampuan untuk mengekspresikan solusi

266
00:12:38,790 --> 00:12:42,480
meskipun, kita hanya perlu tweak
definisi tumpukan kami

267
00:12:42,480 --> 00:12:46,840
untuk tidak menjadi beberapa array yang keras-kode,
tapi hanya untuk menyimpan alamat.

268
00:12:46,840 --> 00:12:47,890
>> Sekarang mengapa ini?

269
00:12:47,890 --> 00:12:51,690
Sekarang kita hanya harus nyaman dengan
fakta bahwa ketika program saya berjalan,

270
00:12:51,690 --> 00:12:53,730
Saya mungkin akan
harus meminta manusia,

271
00:12:53,730 --> 00:12:55,110
berapa banyak nomor yang Anda ingin menyimpan?

272
00:12:55,110 --> 00:12:56,776
Jadi input harus datang dari suatu tempat.

273
00:12:56,776 --> 00:12:59,140
Tapi setelah saya tahu bahwa
nomor, maka saya hanya bisa

274
00:12:59,140 --> 00:13:02,470
menggunakan apa fungsi untuk memberikan
saya sepotong memori?

275
00:13:02,470 --> 00:13:03,580
Saya bisa menggunakan malloc.

276
00:13:03,580 --> 00:13:06,710
Dan saya dapat mengatakan sejumlah
bytes Saya ingin kembali untuk nths ini.

277
00:13:06,710 --> 00:13:10,910
Dan semua saya harus menyimpan dalam jumlah
variabel di sini dalam struct ini

278
00:13:10,910 --> 00:13:13,480
harus apa?

279
00:13:13,480 --> 00:13:18,440
Apa yang sebenarnya masuk ke dalam
angka dalam skenario ini?

280
00:13:18,440 --> 00:13:21,300
Ya, pointer ke pertama
byte yang sepotong memori,

281
00:13:21,300 --> 00:13:24,940
atau lebih khusus, alamat
dari yang pertama dari mereka byte.

282
00:13:24,940 --> 00:13:27,300
Tidak masalah jika itu salah satu
byte atau satu miliar byte,

283
00:13:27,300 --> 00:13:28,890
Aku hanya perlu peduli tentang pertama.

284
00:13:28,890 --> 00:13:31,530
Karena apa jaminan malloc dan
saya jaminan sistem operasi,

285
00:13:31,530 --> 00:13:34,170
adalah bahwa sepotong memori saya
mendapatkan, itu akan menjadi bersebelahan.

286
00:13:34,170 --> 00:13:35,378
Ada tidak akan menjadi celah.

287
00:13:35,378 --> 00:13:38,576
Jadi jika saya sudah meminta 50
byte atau 1000 byte,

288
00:13:38,576 --> 00:13:40,450
mereka semua akan menjadi
kembali ke belakang ke belakang.

289
00:13:40,450 --> 00:13:44,500
Dan selama saya ingat seberapa besar, seberapa
banyak saya minta, semua saya perlu tahu

290
00:13:44,500 --> 00:13:46,230
adalah alamat yang pertama.

291
00:13:46,230 --> 00:13:48,660
>> Jadi sekarang kita memiliki kemampuan dalam kode.

292
00:13:48,660 --> 00:13:51,280
Meskipun, itu akan membawa kita
lebih banyak waktu untuk menulis ini up,

293
00:13:51,280 --> 00:13:55,900
kita sekarang bisa mengalokasikan memori yang oleh
hanya menyimpan alamat yang berbeda ada

294
00:13:55,900 --> 00:13:59,060
jika kita ingin lebih besar atau bahkan
sepotong kecil dari memori.

295
00:13:59,060 --> 00:14:00,170
Jadi di sini untuk off perdagangan.

296
00:14:00,170 --> 00:14:01,360
Sekarang kita mendapatkan dinamisme.

297
00:14:01,360 --> 00:14:03,350
Kami masih memiliki
contiguousness Aku mengklaim.

298
00:14:03,350 --> 00:14:05,881
Karena malloc akan memberi kita
sepotong memori yang berdekatan.

299
00:14:05,881 --> 00:14:08,630
Tapi ini akan menjadi sakit di
leher bagi kita, programmer,

300
00:14:08,630 --> 00:14:09,770
untuk benar-benar kode up.

301
00:14:09,770 --> 00:14:10,730
Hanya saja lebih banyak pekerjaan.

302
00:14:10,730 --> 00:14:13,930
Kita perlu kode mirip dengan apa yang saya
membenturkan keluar beberapa saat yang lalu.

303
00:14:13,930 --> 00:14:16,120
Sangat bisa dilakukan, tetapi hal itu menambah kompleksitas.

304
00:14:16,120 --> 00:14:19,520
Dan waktu pengembang, programmer
Waktu belum sumber lain

305
00:14:19,520 --> 00:14:22,520
bahwa kita mungkin perlu untuk menghabiskan
beberapa waktu untuk mendapatkan fitur baru.

306
00:14:22,520 --> 00:14:24,020
Dan tentu saja ada antrian.

307
00:14:24,020 --> 00:14:26,227
Kami tidak akan masuk ke ini
satu di banyak detail.

308
00:14:26,227 --> 00:14:27,560
Tapi itu sangat mirip dalam roh.

309
00:14:27,560 --> 00:14:31,220
Saya bisa menerapkan antrian, dan
operasinya sesuai,

310
00:14:31,220 --> 00:14:35,660
enqueue atau dequeue, seperti menambah atau menghapus,
itu hanya cara pengujian mengatakan itu,

311
00:14:35,660 --> 00:14:38,100
enqueue atau dequeue, sebagai berikut.

312
00:14:38,100 --> 00:14:41,170
Saya hanya bisa memberi diriku struct
itu lagi memiliki berbagai nomor ini,

313
00:14:41,170 --> 00:14:44,000
itu lagi memiliki ukuran,
tapi mengapa saya sekarang perlu

314
00:14:44,000 --> 00:14:46,940
untuk melacak depan antrian?

315
00:14:46,940 --> 00:14:50,630
Saya tidak perlu tahu
depan tumpukan saya.

316
00:14:50,630 --> 00:14:53,570
Nah, jika saya lagi untuk
queue-- mari kita sulit

317
00:14:53,570 --> 00:14:57,870
kode itu sebagai memiliki seperti lima
bilangan bulat di sini berpotensi.

318
00:14:57,870 --> 00:15:00,940
Jadi ini adalah nol, satu, dua, tiga, empat.

319
00:15:00,940 --> 00:15:03,430
Ini akan menjadi
disebut nomor lagi.

320
00:15:03,430 --> 00:15:06,940
Dan ini akan disebut ukuran.

321
00:15:06,940 --> 00:15:10,056
>> Mengapa tidak cukup
untuk memiliki hanya ukuran?

322
00:15:10,056 --> 00:15:11,680
Nah, mari kita mendorong angka-angka yang sama pada.

323
00:15:11,680 --> 00:15:14,220
Jadi saya pushed-- saya enqueued, atau didorong.

324
00:15:14,220 --> 00:15:20,150
Sekarang saya akan enqueue 50, dan kemudian
51, dan kemudian 61, dan dot dot dot.

325
00:15:20,150 --> 00:15:21,070
Jadi itu enqueue.

326
00:15:21,070 --> 00:15:23,176
Aku enqueued 50, kemudian 51, kemudian 61.

327
00:15:23,176 --> 00:15:25,050
Dan yang terlihat identik
untuk stack sejauh ini,

328
00:15:25,050 --> 00:15:27,190
kecuali saya perlu membuat satu perubahan.

329
00:15:27,190 --> 00:15:33,680
Saya perlu memperbarui ukuran ini, jadi saya pergi
dari nol ke satu dua sampai tiga sekarang.

330
00:15:33,680 --> 00:15:35,760
Bagaimana cara dequeue?

331
00:15:35,760 --> 00:15:36,890
Apa yang terjadi dengan dequeue?

332
00:15:36,890 --> 00:15:41,950
Siapa yang harus datang dari daftar ini pertama
jika garis di Apple Store?

333
00:15:41,950 --> 00:15:42,780
Jadi 50.

334
00:15:42,780 --> 00:15:44,700
Jadi itu semacam rumit saat ini.

335
00:15:44,700 --> 00:15:47,880
Sedangkan terakhir kali itu super
mudah untuk hanya melakukan ukuran minus satu,

336
00:15:47,880 --> 00:15:51,440
Aku sampai ke akhir array saya secara efektif
di mana jumlahnya, ia bisa menghilangkan 61.

337
00:15:51,440 --> 00:15:52,920
Tapi aku tidak ingin menghapus 61.

338
00:15:52,920 --> 00:15:55,030
Saya ingin mengambil 50, yang
ada di sana pada 05:00

339
00:15:55,030 --> 00:15:56,790
untuk berbaris untuk
iPhone baru atau yang lainnya.

340
00:15:56,790 --> 00:16:01,200
Dan untuk menyingkirkan 50, saya
tidak bisa melakukan ini, kan?

341
00:16:01,200 --> 00:16:02,547
Saya bisa mencoret 50.

342
00:16:02,547 --> 00:16:04,380
Tapi kami hanya berkata kita
tidak harus begitu anal

343
00:16:04,380 --> 00:16:06,330
untuk mencakar atau menyembunyikan data.

344
00:16:06,330 --> 00:16:08,090
Kami hanya dapat lupa di mana itu.

345
00:16:08,090 --> 00:16:12,330
>> Tapi jika saya mengubah ukuran saya sekarang untuk
dua, adalah informasi yang memadai ini

346
00:16:12,330 --> 00:16:15,711
untuk mengetahui apa yang terjadi di dalam antrian saya?

347
00:16:15,711 --> 00:16:16,680
Tidak juga.

348
00:16:16,680 --> 00:16:19,830
Seperti ukuran saya adalah dua, tapi
mana antrian mulai,

349
00:16:19,830 --> 00:16:22,980
terutama jika saya masih memiliki
angka-angka yang sama di memori.

350
00:16:22,980 --> 00:16:24,260
50, 51, 61.

351
00:16:24,260 --> 00:16:27,090
Jadi saya perlu mengingat
sekarang di mana bagian depan.

352
00:16:27,090 --> 00:16:29,630
Dan sehingga saya mengusulkan up
ada, kita akan baru saja disebut

353
00:16:29,630 --> 00:16:33,729
N depan, yang awal
nilai seharusnya apa?

354
00:16:33,729 --> 00:16:35,270
Nol, hanya awal daftar.

355
00:16:35,270 --> 00:16:40,876
Tapi sekarang selain decrementing
ukuran, kami hanya selisih depan.

356
00:16:40,876 --> 00:16:42,000
Sekarang inilah masalah lain.

357
00:16:42,000 --> 00:16:43,030
Jadi sekali aku terus.

358
00:16:43,030 --> 00:16:47,520
Kira ini adalah jumlah
seperti 121, 124, dan kemudian, sialan,

359
00:16:47,520 --> 00:16:48,610
Aku keluar dari ruang.

360
00:16:48,610 --> 00:16:50,390
Tapi tunggu dulu, aku tidak.

361
00:16:50,390 --> 00:16:55,630
Jadi pada titik ini dalam cerita,
misalkan ukuran adalah salah satu, dua,

362
00:16:55,630 --> 00:17:00,370
tiga, empat, sehingga menganggap bahwa
ukuran empat, depan adalah salah satu,

363
00:17:00,370 --> 00:17:01,621
jadi 51 adalah di depan.

364
00:17:01,621 --> 00:17:04,329
Saya ingin menempatkan nomor lain di sini,
tapi, sialan, aku keluar dari ruang.

365
00:17:04,329 --> 00:17:06,710
Tapi aku tidak benar-benar, benar?

366
00:17:06,710 --> 00:17:11,192
Dimana saya bisa menaruh beberapa
nilai tambah, seperti 171?

367
00:17:11,192 --> 00:17:13,400
Ya, aku bisa hanya jenis
kembali ke sana, kan?

368
00:17:13,400 --> 00:17:18,161
Dan kemudian mencoret 50, atau
hanya menimpa dengan 171.

369
00:17:18,161 --> 00:17:20,410
Dan jika Anda bertanya-tanya mengapa
nomor kami punya begitu acak,

370
00:17:20,410 --> 00:17:24,150
ini umumnya diambil komputer
kursus ilmu di Harvard setelah CS50.

371
00:17:24,150 --> 00:17:27,510
Tapi itu optimasi yang baik,
karena sekarang aku tidak membuang-buang ruang.

372
00:17:27,510 --> 00:17:30,750
Saya masih harus ingat
seberapa besar hal ini total.

373
00:17:30,750 --> 00:17:31,500
Ini total lima.

374
00:17:31,500 --> 00:17:33,375
Karena saya tidak ingin
mulai Timpa 51.

375
00:17:33,375 --> 00:17:36,260
Jadi sekarang saya masih di luar ruang,
sehingga masalah yang sama seperti sebelumnya.

376
00:17:36,260 --> 00:17:39,140
Tapi Anda bisa melihat bagaimana sekarang
dalam kode Anda, Anda mungkin

377
00:17:39,140 --> 00:17:41,910
harus menulis sedikit lebih
kompleksitas untuk membuat itu terjadi.

378
00:17:41,910 --> 00:17:44,510
Dan pada kenyataannya, operator apa
di C mungkin memungkinkan

379
00:17:44,510 --> 00:17:48,110
Anda ajaib melakukan ini bundar itu?

380
00:17:48,110 --> 00:17:50,160
Ya operator Modulo,
tanda persen.

381
00:17:50,160 --> 00:17:53,160
Jadi apa jenis dingin tentang antrian,
meskipun kami terus menggambar array

382
00:17:53,160 --> 00:17:56,520
karena ini garis lurus seperti, jika Anda
jenis berpikir tentang hal ini sebagai melengkung

383
00:17:56,520 --> 00:18:00,341
sekitar sebagai lingkaran, kemudian hanya
intuitif itu jenis bekerja mental

384
00:18:00,341 --> 00:18:01,590
Saya berpikir sedikit lebih bersih.

385
00:18:01,590 --> 00:18:05,190
Anda masih akan harus melaksanakan
bahwa model mental dalam kode.

386
00:18:05,190 --> 00:18:07,550
Jadi tidak sulit,
akhirnya, untuk melaksanakan,

387
00:18:07,550 --> 00:18:12,430
tapi kami masih kehilangan size-- lebih tepatnya,
kemampuan untuk mengubah ukuran, kecuali kita melakukan ini.

388
00:18:12,430 --> 00:18:15,310
>> Kita harus menyingkirkan array, kita
menggantinya dengan pointer tunggal,

389
00:18:15,310 --> 00:18:20,010
dan kemudian di suatu tempat di kode saya, saya punya
panggilan apa fungsi untuk benar-benar membuat

390
00:18:20,010 --> 00:18:23,720
array nomor disebut?

391
00:18:23,720 --> 00:18:26,190
Malloc, atau sejenis
fungsi, persis.

392
00:18:26,190 --> 00:18:30,481
Pertanyaan tumpukan atau antrian.

393
00:18:30,481 --> 00:18:30,980
Ya?

394
00:18:30,980 --> 00:18:33,657

395
00:18:33,657 --> 00:18:34,240
Pertanyaan bagus.

396
00:18:34,240 --> 00:18:35,830
Apa modulo yang akan Anda gunakan di sini.

397
00:18:35,830 --> 00:18:38,520
Jadi secara umum, bila menggunakan
mod, Anda akan melakukannya

398
00:18:38,520 --> 00:18:40,620
dengan ukuran
seluruh struktur data.

399
00:18:40,620 --> 00:18:44,120
Jadi sesuatu seperti lima atau kapasitas, jika
itu konstan, mungkin terlibat.

400
00:18:44,120 --> 00:18:47,100
Tapi hanya melakukan modulo lima
mungkin tidak cukup,

401
00:18:47,100 --> 00:18:51,380
karena kita perlu tahu kita
membungkus sini atau di sini atau di sini.

402
00:18:51,380 --> 00:18:54,160
Jadi Anda mungkin juga
akan ingin melibatkan

403
00:18:54,160 --> 00:18:57,220
ukuran hal, atau
variabel depan juga.

404
00:18:57,220 --> 00:19:00,140
Jadi itu hanya ini relatif
ekspresi aritmatika sederhana,

405
00:19:00,140 --> 00:19:02,000
tapi Modulo akan menjadi bahan utama.

406
00:19:02,000 --> 00:19:03,330
>> Film begitu singkat jika Anda mau.

407
00:19:03,330 --> 00:19:05,780
Animasi bahwa beberapa
Orang-orang di universitas lain

408
00:19:05,780 --> 00:19:08,060
mengumpulkan bahwa kita sudah
diadaptasi untuk diskusi ini.

409
00:19:08,060 --> 00:19:12,630
Ini melibatkan Jack belajar
fakta tentang antrian dan statistik.

410
00:19:12,630 --> 00:19:19,010

411
00:19:19,010 --> 00:19:21,890
>> FILM: Sekali waktu,
ada seorang pria bernama Jack.

412
00:19:21,890 --> 00:19:25,330
Ketika datang untuk membuat teman-teman,
Jack tidak memiliki bakat.

413
00:19:25,330 --> 00:19:28,220
Jadi Jack pergi untuk berbicara dengan
paling pria yang populer dia tahu.

414
00:19:28,220 --> 00:19:30,920
Ia pergi ke Lou dan bertanya, Apa yang harus saya lakukan?

415
00:19:30,920 --> 00:19:33,400
Lou melihat bahwa temannya
benar-benar tertekan.

416
00:19:33,400 --> 00:19:36,050
Nah, dia mulai, hanya
melihat bagaimana Anda berpakaian.

417
00:19:36,050 --> 00:19:38,680
Apakah Anda tidak memiliki pakaian apapun
dengan tampilan yang berbeda?

418
00:19:38,680 --> 00:19:39,660
Ya, kata Jack.

419
00:19:39,660 --> 00:19:40,840
Saya yakin tidak.

420
00:19:40,840 --> 00:19:43,320
Datang ke rumah saya dan
Aku akan menunjukkan kepada Anda.

421
00:19:43,320 --> 00:19:44,550
Jadi mereka pergi ke Jack.

422
00:19:44,550 --> 00:19:47,520
Dan Jack menunjukkan Lou kotak
di mana ia menyimpan semua kemeja nya,

423
00:19:47,520 --> 00:19:49,260
dan celananya, dan kaus kaki.

424
00:19:49,260 --> 00:19:52,290
Lou mengatakan, saya melihat Anda memiliki
semua pakaian Anda dalam tumpukan.

425
00:19:52,290 --> 00:19:54,870
Mengapa Anda tidak memakai beberapa
lain sesekali?

426
00:19:54,870 --> 00:19:58,020
>> Jack mengatakan, baik, ketika saya
menghapus pakaian dan kaus kaki,

427
00:19:58,020 --> 00:20:00,780
Aku mencuci mereka dan menempatkan
mereka pergi di dalam kotak.

428
00:20:00,780 --> 00:20:03,210
Kemudian datang berikutnya
pagi, dan sampai aku hop.

429
00:20:03,210 --> 00:20:06,380
Aku pergi ke kotak dan mendapatkan
pakaian saya dari atas.

430
00:20:06,380 --> 00:20:09,070
Lou cepat menyadari
masalah dengan Jack.

431
00:20:09,070 --> 00:20:12,080
Dia terus pakaian, CD,
dan buku dalam tumpukan.

432
00:20:12,080 --> 00:20:14,420
Ketika ia meraih
sesuatu untuk dibaca atau memakai,

433
00:20:14,420 --> 00:20:17,100
ia akan memilih buku atas atau pakaian.

434
00:20:17,100 --> 00:20:19,500
Kemudian ketika ia selesai, ia
akan meletakkannya segera kembali.

435
00:20:19,500 --> 00:20:21,970
Kembali itu akan pergi, di atas tumpukan.

436
00:20:21,970 --> 00:20:24,460
Saya tahu solusinya,
kata seorang kemenangan keras.

437
00:20:24,460 --> 00:20:27,090
Anda perlu belajar untuk
mulai menggunakan antrian.

438
00:20:27,090 --> 00:20:29,870
Lou mengambil pakaian Jack dan
menggantung mereka di dalam lemari.

439
00:20:29,870 --> 00:20:32,710
Dan ketika ia telah mengosongkan
kotak, ia hanya melemparkan itu.

440
00:20:32,710 --> 00:20:36,500
>> Lalu dia berkata, sekarang Jack, pada akhir
hari, meletakkan pakaian Anda di sebelah kiri

441
00:20:36,500 --> 00:20:37,990
ketika Anda menempatkan mereka pergi.

442
00:20:37,990 --> 00:20:41,300
Maka besok pagi ketika Anda
melihat sinar matahari, mendapatkan pakaian Anda

443
00:20:41,300 --> 00:20:43,440
di sebelah kanan, dari akhir baris.

444
00:20:43,440 --> 00:20:44,880
Apakah Anda tidak melihat? kata Lou.

445
00:20:44,880 --> 00:20:46,370
Itu akan sangat bagus.

446
00:20:46,370 --> 00:20:49,770
Anda akan memakai segala sesuatu sekali
sebelum Anda memakai sesuatu dua kali.

447
00:20:49,770 --> 00:20:52,670
Dan dengan segala sesuatu dalam antrian
di lemari dan rak-nya,

448
00:20:52,670 --> 00:20:55,160
Jack mulai merasa
cukup yakin pada dirinya sendiri.

449
00:20:55,160 --> 00:20:59,720
Semua berkat Lou dan
antrian indah nya.

450
00:20:59,720 --> 00:21:01,220
SPEAKER 1: Baiklah, itu menggemaskan.

451
00:21:01,220 --> 00:21:05,920

452
00:21:05,920 --> 00:21:10,080
Jadi apa yang telah benar-benar akan
di bawah kap sekarang?

453
00:21:10,080 --> 00:21:12,370
Bahwa kita memiliki pointer,
bahwa kita memiliki malloc,

454
00:21:12,370 --> 00:21:15,680
bahwa kita memiliki kemampuan untuk membuat
potongan memori untuk diri kita sendiri

455
00:21:15,680 --> 00:21:16,344
dinamis.

456
00:21:16,344 --> 00:21:18,510
Jadi ini adalah kita gambar
sekilas hanya beberapa hari.

457
00:21:18,510 --> 00:21:21,180
Kami tidak benar-benar tinggal
di atasnya, tapi gambar ini

458
00:21:21,180 --> 00:21:24,180
memiliki telah terjadi di bawah
kap untuk minggu sekarang.

459
00:21:24,180 --> 00:21:27,050
Dan jadi ini merupakan, hanya
persegi panjang yang kita sudah ditarik,

460
00:21:27,050 --> 00:21:28,180
memori komputer Anda.

461
00:21:28,180 --> 00:21:31,850
Dan mungkin komputer Anda, atau CS50
ID, memiliki gigabyte memori atau RAM

462
00:21:31,850 --> 00:21:33,050
atau dua gigabyte atau empat.

463
00:21:33,050 --> 00:21:34,450
Itu tidak terlalu penting.

464
00:21:34,450 --> 00:21:37,240
Sistem operasi Anda
Windows atau Mac OS atau Linux,

465
00:21:37,240 --> 00:21:41,120
dasarnya memungkinkan program Anda
berpikir bahwa ia memiliki akses

466
00:21:41,120 --> 00:21:42,982
untuk keseluruhan
memori komputer Anda,

467
00:21:42,982 --> 00:21:45,440
meskipun Anda mungkin akan berjalan
beberapa program sekaligus.

468
00:21:45,440 --> 00:21:46,990
Jadi dalam kenyataannya, yang tidak benar-benar bekerja.

469
00:21:46,990 --> 00:21:49,448
Tapi itu semacam ilusi
diberikan ke semua program Anda.

470
00:21:49,448 --> 00:21:53,110
Jadi, jika Anda memiliki dua gigs RAM, ini
adalah bagaimana komputer mungkin berpikir itu.

471
00:21:53,110 --> 00:21:57,110
>> Sekarang kebetulan, salah satu dari ini
hal, salah satu segmen memori,

472
00:21:57,110 --> 00:21:58,350
disebut stack.

473
00:21:58,350 --> 00:22:01,680
Dan memang setiap saat
sejauh dalam menulis kode

474
00:22:01,680 --> 00:22:05,900
bahwa Anda telah disebut
fungsi, misalnya utama.

475
00:22:05,900 --> 00:22:08,410
Ingat bahwa setiap kali saya sudah
memori ditarik komputer,

476
00:22:08,410 --> 00:22:10,640
Saya selalu menarik semacam
setengah dari persegi panjang di sini

477
00:22:10,640 --> 00:22:12,520
dan tidak repot-repot berbicara
tentang apa yang di atas.

478
00:22:12,520 --> 00:22:15,980
Karena ketika utama disebut, saya mengklaim
bahwa Anda mendapatkan sepotong ini memori

479
00:22:15,980 --> 00:22:16,970
yang turun di sini.

480
00:22:16,970 --> 00:22:20,650
Dan jika utama yang disebut fungsi
seperti swap, juga pertukaran goes here.

481
00:22:20,650 --> 00:22:23,720
Dan ternyata, itu
mana itu berakhir.

482
00:22:23,720 --> 00:22:26,277
Pada sesuatu yang disebut stack
dalam memori komputer Anda.

483
00:22:26,277 --> 00:22:28,360
Sekarang di akhir hari,
ini hanya membahas.

484
00:22:28,360 --> 00:22:30,680
Ini seperti byte nol,
byte satu, byte 2 miliar.

485
00:22:30,680 --> 00:22:33,130
Tapi jika Anda berpikir tentang hal itu
sebagai objek persegi panjang ini,

486
00:22:33,130 --> 00:22:35,130
semua yang kita lakukan setiap
saat kita memanggil fungsi adalah

487
00:22:35,130 --> 00:22:37,180
layering sepotong baru memori.

488
00:22:37,180 --> 00:22:41,700
Kami memberikan fungsi yang sepotong
memori sendiri untuk bekerja dengan.

489
00:22:41,700 --> 00:22:44,490
>> Dan ingat sekarang bahwa ini penting.

490
00:22:44,490 --> 00:22:46,400
Karena jika kita memiliki
sesuatu seperti pertukaran

491
00:22:46,400 --> 00:22:51,610
dan dua variabel lokal seperti A dan B dan
kita mengubah nilai-nilai dari satu dan dua

492
00:22:51,610 --> 00:22:55,130
dua dan satu, ingat
bahwa ketika Swap kembali,

493
00:22:55,130 --> 00:22:58,330
itu seolah-olah ini sepotong
memori hanya pergi.

494
00:22:58,330 --> 00:23:00,080
Pada kenyataannya, itu masih
ada forensik.

495
00:23:00,080 --> 00:23:01,940
Dan ada sesuatu yang masih benar-benar ada.

496
00:23:01,940 --> 00:23:05,410
Tetapi secara konseptual, itu seperti
meskipun itu benar-benar hilang.

497
00:23:05,410 --> 00:23:10,910
Dan utama tidak tahu pekerjaan
yang dilakukan dalam fungsi swap,

498
00:23:10,910 --> 00:23:14,890
kecuali itu benar-benar disahkan pada mereka
argumen dengan pointer atau referensi.

499
00:23:14,890 --> 00:23:17,790
Sekarang, solusi mendasar
itu masalah dengan Swap

500
00:23:17,790 --> 00:23:19,970
lewat hal-hal di berdasarkan alamat.

501
00:23:19,970 --> 00:23:23,250
Tapi ternyata, juga, apa
telah terjadi di atas bagian yang

502
00:23:23,250 --> 00:23:26,330
dari persegi panjang selama ini adalah
Belum ada lebih banyak memori di sana.

503
00:23:26,330 --> 00:23:28,790
Dan ketika Anda secara dinamis
mengalokasikan memori,

504
00:23:28,790 --> 00:23:32,020
apakah itu dalam GetString, yang
kami sudah melakukan untuk Anda di CS50

505
00:23:32,020 --> 00:23:34,710
perpustakaan, atau jika kalian
memanggil malloc dan meminta

506
00:23:34,710 --> 00:23:37,950
sistem operasi untuk sepotong
memori, itu tidak datang dari stack.

507
00:23:37,950 --> 00:23:40,960
Itu berasal dari tempat lain
dalam memori komputer Anda

508
00:23:40,960 --> 00:23:42,220
yang disebut tumpukan.

509
00:23:42,220 --> 00:23:43,430
Dan itu tidak berbeda.

510
00:23:43,430 --> 00:23:44,285
Ini adalah RAM yang sama.

511
00:23:44,285 --> 00:23:45,160
Ini adalah memori yang sama.

512
00:23:45,160 --> 00:23:49,080
Itu hanya RAM itu terserah
ada bukannya di sini.

513
00:23:49,080 --> 00:23:50,750
>> Dan apa artinya?

514
00:23:50,750 --> 00:23:53,650
Nah, jika komputer Anda memiliki
jumlah terbatas memori

515
00:23:53,650 --> 00:23:57,450
dan stack yang tumbuh, sehingga
untuk berbicara, dan heap, menurut

516
00:23:57,450 --> 00:23:59,349
panah ini, tumbuh ke bawah.

517
00:23:59,349 --> 00:24:01,140
Dengan kata lain, setiap
kali Anda memanggil malloc,

518
00:24:01,140 --> 00:24:03,430
Anda diberi sepotong
memori dari atas,

519
00:24:03,430 --> 00:24:06,630
maka mungkin sedikit lebih rendah, kemudian sedikit
lebih rendah, setiap kali Anda memanggil malloc,

520
00:24:06,630 --> 00:24:10,100
heap, itu penggunaan,
adalah jenis tumbuh,

521
00:24:10,100 --> 00:24:11,950
tumbuh lebih dekat dan lebih dekat dengan apa?

522
00:24:11,950 --> 00:24:13,382
Tumpukan.

523
00:24:13,382 --> 00:24:14,840
Jadi apakah ini tampak seperti ide yang baik?

524
00:24:14,840 --> 00:24:18,420

525
00:24:18,420 --> 00:24:22,140
Maksudku, di mana itu tidak benar-benar jelas
apa lagi yang bisa Anda lakukan jika Anda hanya

526
00:24:22,140 --> 00:24:23,910
memiliki jumlah terbatas memori.

527
00:24:23,910 --> 00:24:25,200
Tapi ini pasti buruk.

528
00:24:25,200 --> 00:24:27,920
Kedua anak panah adalah pada
kecelakaan saja untuk satu sama lain.

529
00:24:27,920 --> 00:24:31,930
>> Dan ternyata orang jahat, orang-orang yang
sangat baik dengan pemrograman,

530
00:24:31,930 --> 00:24:36,140
dan mencoba untuk hack ke komputer,
dapat memanfaatkan kenyataan ini.

531
00:24:36,140 --> 00:24:38,290
Bahkan, mari kita pertimbangkan
potongan kecil.

532
00:24:38,290 --> 00:24:41,350
Jadi ini adalah contoh Anda dapat membaca
sekitar secara lebih rinci di Wikipedia.

533
00:24:41,350 --> 00:24:43,100
Kami akan mengarahkan Anda pada
artikel jika penasaran.

534
00:24:43,100 --> 00:24:45,650
Tapi ada serangan umum
dikenal sebagai buffer overflow yang

535
00:24:45,650 --> 00:24:49,570
telah ada selama manusia
telah memiliki kemampuan untuk memanipulasi

536
00:24:49,570 --> 00:24:53,120
memori komputer, terutama dalam C.
Jadi ini adalah program yang sangat sewenang-wenang,

537
00:24:53,120 --> 00:24:55,130
tapi mari kita membacanya dari bawah ke atas.

538
00:24:55,130 --> 00:24:57,650
Utama ke bintang argc arang argv.

539
00:24:57,650 --> 00:24:59,830
Jadi itu program yang mengambil
argumen baris perintah.

540
00:24:59,830 --> 00:25:03,620
Dan semua utama yang tampaknya adalah panggilan
fungsi, menyebutnya F untuk kesederhanaan.

541
00:25:03,620 --> 00:25:04,610
Dan melewati apa?

542
00:25:04,610 --> 00:25:05,490
Argv satu.

543
00:25:05,490 --> 00:25:09,320
Sehingga masuk ke dalam F apapun
kata adalah bahwa pengguna mengetik

544
00:25:09,320 --> 00:25:11,500
pada prompt setelah
Nama program sama sekali.

545
00:25:11,500 --> 00:25:15,730
Begitu banyak seperti Caesar atau Vigenere, yang
Anda mungkin ingat lakukan dengan argv.

546
00:25:15,730 --> 00:25:16,680
>> Jadi apa yang F?

547
00:25:16,680 --> 00:25:19,760
F mengambil dalam sebuah string
sebagai argumen sendiri,

548
00:25:19,760 --> 00:25:22,100
AKA bintang char, yang sama
hal, sebagai string.

549
00:25:22,100 --> 00:25:24,920
Dan itu disebut sewenang-wenang
bar dalam contoh ini.

550
00:25:24,920 --> 00:25:27,710
Dan kemudian arang c 12,
hanya dalam istilah awam,

551
00:25:27,710 --> 00:25:31,750
apa Char c braket 12 melakukan bagi kita?

552
00:25:31,750 --> 00:25:33,440
Apa yang ia lakukan?

553
00:25:33,440 --> 00:25:36,490
Mengalokasikan memori, khususnya
12 byte untuk 12 karakter.

554
00:25:36,490 --> 00:25:36,990
Tepat.

555
00:25:36,990 --> 00:25:40,000
Dan kemudian baris terakhir, aduk dan
copy, Anda mungkin tidak melihat.

556
00:25:40,000 --> 00:25:43,360
Ini adalah salinan string yang
Fungsi yang tujuan dalam hidup

557
00:25:43,360 --> 00:25:48,160
adalah untuk menyalin argumen kedua
dalam argumen pertama,

558
00:25:48,160 --> 00:25:51,190
tapi hanya sampai
sejumlah byte.

559
00:25:51,190 --> 00:25:53,860
Jadi argumen ketiga mengatakan,
berapa banyak byte yang harus Anda menyalin?

560
00:25:53,860 --> 00:25:56,720
Panjang bar,
apapun pengguna mengetik.

561
00:25:56,720 --> 00:25:59,320
Dan isi
bar, string yang, yang

562
00:25:59,320 --> 00:26:02,330
disalin ke dalam memori menunjuk pada C.

563
00:26:02,330 --> 00:26:04,060
>> Jadi ini tampaknya agak bodoh, dan itu.

564
00:26:04,060 --> 00:26:06,300
Ini adalah contoh buat,
tapi itu perwakilan

565
00:26:06,300 --> 00:26:10,100
dari kelas vektor serangan,
cara menyerang sebuah program.

566
00:26:10,100 --> 00:26:15,050
Semua baik-baik saja dan baik jika pengguna
jenis dalam sebuah kata yang 11 karakter

567
00:26:15,050 --> 00:26:18,040
atau lebih sedikit, ditambah backslash nol.

568
00:26:18,040 --> 00:26:22,830
Bagaimana jika jenis pengguna di lebih dari
11 atau 12 atau 20 atau 50 karakter?

569
00:26:22,830 --> 00:26:25,090
Apa program ini lakukan?

570
00:26:25,090 --> 00:26:29,360
Kesalahan berpotensi seg. Ini akan
untuk membuta menyalin segala sesuatu di bar sampai

571
00:26:29,360 --> 00:26:31,750
panjangnya, yang
harfiah semuanya di bar,

572
00:26:31,750 --> 00:26:36,307
ke alamat menunjuk C. Tapi C
hanya Terlebih Dahulu diberikan sebagai 12 byte.

573
00:26:36,307 --> 00:26:37,640
Tapi tidak ada pemeriksaan tambahan.

574
00:26:37,640 --> 00:26:38,700
Tidak ada jika kondisi.

575
00:26:38,700 --> 00:26:40,580
Tidak ada pengecekan sini kesalahan.

576
00:26:40,580 --> 00:26:43,270
>> Dan jadi apa program ini adalah
akan lakukan adalah hanya membabi buta

577
00:26:43,270 --> 00:26:45,750
menyalin satu hal ke yang lain.

578
00:26:45,750 --> 00:26:47,880
Dan jadi jika kita menggambar ini
sebagai gambar, inilah

579
00:26:47,880 --> 00:26:49,860
hanya sepotong ruang memori.

580
00:26:49,860 --> 00:26:53,470
Jadi perhatikan di bagian bawah, kita
memiliki bar variabel lokal.

581
00:26:53,470 --> 00:26:57,330
Sehingga pointer itu akan store--
bukan bahwa argumen lokal yang

582
00:26:57,330 --> 00:26:58,672
akan menyimpan string bar.

583
00:26:58,672 --> 00:27:00,380
Dan kemudian melihat hanya
di atasnya dalam tumpukan,

584
00:27:00,380 --> 00:27:02,505
karena setiap kali Anda meminta
untuk memori di stack,

585
00:27:02,505 --> 00:27:04,310
ia pergi sedikit
di atas itu pictorially,

586
00:27:04,310 --> 00:27:06,270
pemberitahuan bahwa kita punya 12 bytes ada.

587
00:27:06,270 --> 00:27:10,690
Yang kiri atas adalah C braket nol dan
yang kanan bawah adalah C braket 11.

588
00:27:10,690 --> 00:27:12,870
Itu hanya bagaimana komputer
akan berbaring keluar.

589
00:27:12,870 --> 00:27:18,300
Jadi hanya intuitif, jika bar memiliki lebih
dari 12 karakter secara total, termasuk

590
00:27:18,300 --> 00:27:25,790
backslash nol, di mana adalah
12 atau braket C 12 akan pergi?

591
00:27:25,790 --> 00:27:28,440
Atau lebih tepatnya di mana-12
karakter atau karakter-13,

592
00:27:28,440 --> 00:27:30,900
karakter keseratus akan
berakhir dalam gambar?

593
00:27:30,900 --> 00:27:33,400
Atas atau di bawah?

594
00:27:33,400 --> 00:27:36,300
>> Benar, karena meskipun
tumpukan itu sendiri tumbuh ke atas,

595
00:27:36,300 --> 00:27:39,590
setelah Anda meletakkan barang-barang di
itu, untuk alasan desain,

596
00:27:39,590 --> 00:27:41,294
menempatkan memori dari atas ke bawah.

597
00:27:41,294 --> 00:27:44,460
Jadi jika Anda punya lebih dari 12 byte,
Anda akan mulai menimpa bar.

598
00:27:44,460 --> 00:27:47,280
Nah, itu bug, tapi itu
tidak benar-benar masalah besar.

599
00:27:47,280 --> 00:27:51,130
Tapi itu adalah masalah besar, karena ada
lebih banyak barang yang terjadi di memori.

600
00:27:51,130 --> 00:27:53,074
Jadi, inilah bagaimana kita mungkin
menempatkan halo, harus jelas.

601
00:27:53,074 --> 00:27:54,490
Jika saya mengetik di halo pada prompt.

602
00:27:54,490 --> 00:27:59,330
H-E-L-L-O backslash nol, berakhir dalam
mereka 12 byte, dan kami super aman.

603
00:27:59,330 --> 00:28:00,330
Semua baik-baik saja.

604
00:28:00,330 --> 00:28:03,020
Tetapi jika saya ketik sesuatu
lagi, berpotensi itu

605
00:28:03,020 --> 00:28:05,860
akan menyusup ke ruang bar.

606
00:28:05,860 --> 00:28:08,405
Tapi lebih buruk lagi, ternyata
sepanjang waktu ini,

607
00:28:08,405 --> 00:28:11,530
meskipun kami tidak pernah berbicara tentang
itu, tumpukan digunakan untuk hal-hal lain.

608
00:28:11,530 --> 00:28:13,560
Ini bukan hanya variabel lokal.

609
00:28:13,560 --> 00:28:15,100
>> C adalah bahasa tingkat yang sangat rendah.

610
00:28:15,100 --> 00:28:17,810
Dan itu semacam diam-diam
menggunakan stack juga

611
00:28:17,810 --> 00:28:21,260
ingat ketika
fungsi disebut, apa

612
00:28:21,260 --> 00:28:26,040
alamat adalah dari fungsi sebelumnya,
sehingga dapat melompat kembali ke fungsi itu.

613
00:28:26,040 --> 00:28:29,980
Jadi ketika panggilan utama menukar antara
hal didorong ke stack

614
00:28:29,980 --> 00:28:34,380
tidak hanya swap variabel lokal,
atau argumen, juga diam-diam mendorong

615
00:28:34,380 --> 00:28:37,510
ke stack yang diwakili
dengan potongan merah di sini,

616
00:28:37,510 --> 00:28:40,520
adalah alamat utama secara fisik
dalam memori komputer Anda,

617
00:28:40,520 --> 00:28:44,180
sehingga ketika swap dilakukan, komputer
tahu saya harus kembali ke utama

618
00:28:44,180 --> 00:28:46,760
dan menyelesaikan melaksanakan fungsi utama.

619
00:28:46,760 --> 00:28:51,960
Jadi ini berbahaya sekarang, karena jika
jenis pengguna di sumur lebih dari halo,

620
00:28:51,960 --> 00:28:57,030
sehingga input pengguna clobbers
atau menimpa yang bagian merah,

621
00:28:57,030 --> 00:28:59,820
logis jika komputer
hanya akan membabi buta menganggap

622
00:28:59,820 --> 00:29:03,830
bahwa byte dalam irisan merah
alamat yang harus kembali,

623
00:29:03,830 --> 00:29:09,020
bagaimana jika musuh cukup pintar atau
cukup beruntung untuk menempatkan urutan byte

624
00:29:09,020 --> 00:29:13,450
ada yang terlihat seperti alamat,
tapi itu alamat kode

625
00:29:13,450 --> 00:29:18,730
bahwa dia ingin komputer
untuk mengeksekusi bukan main?

626
00:29:18,730 --> 00:29:21,670
>> Dengan kata lain, jika apa yang
pengguna mengetik di prompt,

627
00:29:21,670 --> 00:29:23,850
bukan hanya sesuatu
seperti tidak berbahaya halo,

628
00:29:23,850 --> 00:29:28,210
tapi itu sebenarnya kode yang sama
untuk menghapus semua file pengguna ini?

629
00:29:28,210 --> 00:29:30,060
Atau email kata sandi mereka kepada saya?

630
00:29:30,060 --> 00:29:31,940
Atau mulai penebangan mereka
keystrokes, kan?

631
00:29:31,940 --> 00:29:34,920
Ada cara, mari kita menetapkan hari ini,
bahwa mereka bisa mengetikkan bukan hanya halo

632
00:29:34,920 --> 00:29:36,711
dunia atau nama mereka,
mereka pada dasarnya bisa

633
00:29:36,711 --> 00:29:39,570
lulus dalam kode, nol dan
orang, bahwa komputer

634
00:29:39,570 --> 00:29:43,450
kesalahan untuk kedua kode dan alamat.

635
00:29:43,450 --> 00:29:48,950
Jadi meskipun agak abstrak, jika
jenis pengguna dalam kode cukup permusuhan

636
00:29:48,950 --> 00:29:52,330
bahwa kita akan menggeneralisasi di sini sebagai
A. A adalah serangan atau musuh.

637
00:29:52,330 --> 00:29:53,140
Hal sehingga hanya buruk.

638
00:29:53,140 --> 00:29:55,306
Kami tidak peduli tentang
nomor atau nol atau yang

639
00:29:55,306 --> 00:29:59,470
hari ini, sehingga Anda berakhir
Timpa bahwa bagian merah,

640
00:29:59,470 --> 00:30:01,580
melihat bahwa urutan byte.

641
00:30:01,580 --> 00:30:05,020
O 835 C nol delapan nol.

642
00:30:05,020 --> 00:30:08,960
Dan sekarang sebagai artikel Wikipedia di sini
telah mengusulkan, jika Anda benar-benar mulai sekarang

643
00:30:08,960 --> 00:30:12,460
label byte di komputer Anda
memori, apa artikel Wikipedia adalah

644
00:30:12,460 --> 00:30:19,060
mengusulkan adalah bahwa, bagaimana jika alamat
itu byte kiri atas adalah 80 C 0 3508.

645
00:30:19,060 --> 00:30:22,200
>> Dengan kata lain, jika orang jahat adalah
cukup pintar dengan kode nya

646
00:30:22,200 --> 00:30:26,650
untuk benar-benar menempatkan nomor di sini bahwa
sesuai dengan alamat kode

647
00:30:26,650 --> 00:30:29,180
ia disuntikkan
ke dalam komputer, Anda

648
00:30:29,180 --> 00:30:31,050
dapat trik komputer
dalam melakukan sesuatu.

649
00:30:31,050 --> 00:30:34,140
Menghapus file, email
hal, mengendus lalu lintas,

650
00:30:34,140 --> 00:30:36,710
secara harfiah apa pun bisa
disuntikkan ke dalam komputer.

651
00:30:36,710 --> 00:30:39,220
Dan jadi buffer overflow
Serangan pada intinya

652
00:30:39,220 --> 00:30:43,530
hanya bodoh, bodoh
utama dari sebuah array yang

653
00:30:43,530 --> 00:30:45,840
tidak memiliki batas-batasnya diperiksa.

654
00:30:45,840 --> 00:30:48,850
Dan ini adalah apa yang super berbahaya adalah
dan secara bersamaan super kuat

655
00:30:48,850 --> 00:30:52,560
di C adalah bahwa kita memang memiliki
akses ke mana saja di memori.

656
00:30:52,560 --> 00:30:55,320
Terserah kita, programmer,
yang menulis kode asli

657
00:30:55,320 --> 00:30:59,330
untuk memeriksa panjang sialan dari setiap
array yang kita memanipulasi.

658
00:30:59,330 --> 00:31:00,750
Jadi harus jelas, apa memperbaiki?

659
00:31:00,750 --> 00:31:03,190
Jika kita memutar kembali ke ini
kode, saya seharusnya tidak hanya

660
00:31:03,190 --> 00:31:08,000
mengubah panjang bar, apa
lagi yang harus saya memeriksa?

661
00:31:08,000 --> 00:31:10,620
Apa lagi yang harus saya lakukan untuk
mencegah serangan ini seluruhnya?

662
00:31:10,620 --> 00:31:14,110
Saya tidak ingin hanya membabi buta mengatakan
Anda menyalin banyak byte

663
00:31:14,110 --> 00:31:16,140
seperti panjang bar.

664
00:31:16,140 --> 00:31:18,910
Saya ingin mengatakan, copy sebagai
banyak byte seperti di bar

665
00:31:18,910 --> 00:31:24,090
sampai dialokasikan
memori, atau 12 secara maksimal.

666
00:31:24,090 --> 00:31:27,450
Jadi saya perlu beberapa jenis jika kondisi
yang tidak memeriksa panjang bar,

667
00:31:27,450 --> 00:31:32,800
tetapi jika melebihi 12, kami hanya sulit kode
12 sebagai jarak maksimum yang mungkin.

668
00:31:32,800 --> 00:31:35,910
Jika tidak disebut penyangga
Serangan meluap bisa terjadi.

669
00:31:35,910 --> 00:31:38,451
Di bagian bawah mereka slide,
jika Anda penasaran untuk membaca lebih lanjut

670
00:31:38,451 --> 00:31:41,200
adalah artikel asli yang sebenarnya
jika Anda ingin melihat.

671
00:31:41,200 --> 00:31:44,550
>> Tapi sekarang, di antara harga
dibayar di sini adalah inefisiensi.

672
00:31:44,550 --> 00:31:46,680
Jadi itu cepat
rendah tingkat melihat apa

673
00:31:46,680 --> 00:31:49,709
masalah bisa muncul sekarang kita bahwa
memiliki akses ke memori komputer.

674
00:31:49,709 --> 00:31:51,750
Tapi masalah lain kita
sudah tersandung pada Senin

675
00:31:51,750 --> 00:31:53,800
hanya inefisiensi
dari linked list.

676
00:31:53,800 --> 00:31:56,019
Kami kembali ke waktu linier.

677
00:31:56,019 --> 00:31:57,560
Kami tidak lagi memiliki array berdekatan.

678
00:31:57,560 --> 00:31:58,980
Kami tidak memiliki akses acak.

679
00:31:58,980 --> 00:32:00,710
Kita tidak bisa menggunakan notasi braket persegi.

680
00:32:00,710 --> 00:32:04,590
Kami benar-benar harus menggunakan loop sementara
seperti yang saya tulis beberapa saat yang lalu.

681
00:32:04,590 --> 00:32:09,740
Tapi pada hari Senin, kami menyatakan bahwa kita dapat
merayap kembali ke ranah efisiensi

682
00:32:09,740 --> 00:32:13,040
mencapai sesuatu yang
logaritmik mungkin, atau terbaik namun,

683
00:32:13,040 --> 00:32:16,120
bahkan mungkin sesuatu yang
disebut konstanta waktu.

684
00:32:16,120 --> 00:32:19,840
Jadi bagaimana kita bisa melakukannya dengan menggunakan ini baru
alat, alamat ini, pointer ini,

685
00:32:19,840 --> 00:32:22,210
dan threading hal kita sendiri?

686
00:32:22,210 --> 00:32:23,960
Nah, misalkan
di sini, ini adalah a bunch

687
00:32:23,960 --> 00:32:27,170
angka yang ingin kita simpan dalam
struktur data dan pencarian efisien.

688
00:32:27,170 --> 00:32:30,960
Kami benar-benar dapat mundur ke minggu
dua, melempar ini ke dalam sebuah array,

689
00:32:30,960 --> 00:32:33,150
dan mencari mereka menggunakan pencarian biner.

690
00:32:33,150 --> 00:32:34,040
Membagi dan menaklukkan.

691
00:32:34,040 --> 00:32:37,720
Dan sebenarnya Anda menulis
pencarian biner di PSET3,

692
00:32:37,720 --> 00:32:40,100
di mana Anda menerapkan program find.

693
00:32:40,100 --> 00:32:40,890
Tapi kau tahu apa.

694
00:32:40,890 --> 00:32:45,060
Ada jenis yang lebih
cara cerdas untuk melakukan hal ini.

695
00:32:45,060 --> 00:32:47,390
Ini sedikit lebih
canggih dan mungkin

696
00:32:47,390 --> 00:32:50,830
memungkinkan kita untuk melihat mengapa biner
pencarian jauh lebih cepat.

697
00:32:50,830 --> 00:32:52,980
Pertama, mari kita memperkenalkan
gagasan pohon.

698
00:32:52,980 --> 00:32:54,730
Yang meskipun di
pohon realitas jenis

699
00:32:54,730 --> 00:32:57,730
tumbuh seperti ini, dalam dunia komputer
ilmu mereka jenis tumbuh ke bawah

700
00:32:57,730 --> 00:33:00,830
seperti pohon keluarga, di mana Anda memiliki
kakek atau kakek-nenek besar

701
00:33:00,830 --> 00:33:04,580
atau entah apa lagi di bagian atas, patriark dan
ibu pemimpin keluarga, hanya satu

702
00:33:04,580 --> 00:33:07,930
disebut akar, node, di bawah
yang anak-anaknya,

703
00:33:07,930 --> 00:33:11,442
bawah yang anak-anaknya, atau
keturunan yang lebih umum.

704
00:33:11,442 --> 00:33:13,400
Dan siapa pun menggantung
bagian bawah keluarga

705
00:33:13,400 --> 00:33:16,070
pohon, selain itu
termuda dalam keluarga,

706
00:33:16,070 --> 00:33:19,520
bisa juga hanya menjadi generik
disebut daun pohon.

707
00:33:19,520 --> 00:33:21,800
>> Jadi ini hanya a bunch
kata-kata dan definisi

708
00:33:21,800 --> 00:33:25,790
untuk sesuatu yang disebut pohon di komputer
ilmu, seperti pohon keluarga.

709
00:33:25,790 --> 00:33:28,770
Tapi ada inkarnasi pengujian
pohon, salah satunya

710
00:33:28,770 --> 00:33:30,780
disebut pohon pencarian biner.

711
00:33:30,780 --> 00:33:34,380
Dan Anda bisa jenis menggoda
selain apa hal ini tidak.

712
00:33:34,380 --> 00:33:37,180
Yah, itu biner dalam arti apa?

713
00:33:37,180 --> 00:33:41,455
Dari mana biner datang dari sini?

714
00:33:41,455 --> 00:33:41,955
Maaf?

715
00:33:41,955 --> 00:33:45,961

716
00:33:45,961 --> 00:33:47,210
Ini tidak begitu banyak baik atau.

717
00:33:47,210 --> 00:33:52,000
Ini lebih bahwa setiap node memiliki
lebih dari dua anak, seperti yang kita lihat di sini.

718
00:33:52,000 --> 00:33:54,990
Secara umum, tree-- dan
orang tua dan kakek-nenek

719
00:33:54,990 --> 00:33:57,640
dapat memiliki banyak anak-anak atau
cucu-cucu mereka benar-benar ingin,

720
00:33:57,640 --> 00:34:00,820
dan jadi misalnya ada kami memiliki tiga
anak-anak dari simpul tangan kanan,

721
00:34:00,820 --> 00:34:05,480
tetapi dalam pohon biner, sebuah node memiliki
nol, satu, atau dua anak maksimal.

722
00:34:05,480 --> 00:34:08,496
Dan itu adalah properti yang bagus,
karena jika itu dibatasi oleh dua,

723
00:34:08,496 --> 00:34:10,620
kita akan dapat
mendapatkan log basis sedikit dua

724
00:34:10,620 --> 00:34:11,975
tindakan yang terjadi di sini pada akhirnya.

725
00:34:11,975 --> 00:34:13,350
Jadi kita memiliki sesuatu logaritmik.

726
00:34:13,350 --> 00:34:14,558
Tapi lebih pada suatu saat.

727
00:34:14,558 --> 00:34:19,810
Pohon pencarian berarti bahwa angka-angka tersebut
diatur sedemikian rupa sehingga anak kiri ini

728
00:34:19,810 --> 00:34:22,429
nilai lebih besar dari akar.

729
00:34:22,429 --> 00:34:26,010
Dan anak kanan adalah
lebih besar dari akar.

730
00:34:26,010 --> 00:34:29,290
Dengan kata lain, jika Anda mengambil salah satu
node, lingkaran dalam gambar ini,

731
00:34:29,290 --> 00:34:31,840
dan melihat kiri
anak dan anak kanan,

732
00:34:31,840 --> 00:34:34,739
pertama harus kurang dari,
kedua harus lebih besar dari.

733
00:34:34,739 --> 00:34:36,159
Jadi kewarasan memeriksa 55.

734
00:34:36,159 --> 00:34:37,780
Ini meninggalkan anak adalah 33.

735
00:34:37,780 --> 00:34:38,620
Ini kurang dari.

736
00:34:38,620 --> 00:34:40,929
55, anak kanan adalah 77.

737
00:34:40,929 --> 00:34:41,783
Ini lebih besar dari.

738
00:34:41,783 --> 00:34:43,199
Dan itu definisi rekursif.

739
00:34:43,199 --> 00:34:46,480
Kita bisa memeriksa setiap salah satu dari mereka
node dan pola yang sama akan terus.

740
00:34:46,480 --> 00:34:49,389
>> Jadi apa yang bagus di
pohon pencarian biner, adalah

741
00:34:49,389 --> 00:34:52,204
satu itu, kita dapat menerapkannya
dengan struct, hanya seperti ini.

742
00:34:52,204 --> 00:34:54,620
Dan meskipun kita membuang
banyak struktur di Anda,

743
00:34:54,620 --> 00:34:56,560
mereka agak
intuitif sekarang mudah-mudahan.

744
00:34:56,560 --> 00:35:00,570
Sintaks masih misterius pasti,
tapi isi node dalam

745
00:35:00,570 --> 00:35:02,786
context-- dan kami tetap
menggunakan node kata,

746
00:35:02,786 --> 00:35:04,910
apakah itu persegi panjang
pada layar atau lingkaran,

747
00:35:04,910 --> 00:35:08,970
itu hanya beberapa wadah generik,
dalam hal ini pohon, seperti yang

748
00:35:08,970 --> 00:35:11,780
kita melihat, kita perlu integer
di setiap node

749
00:35:11,780 --> 00:35:15,460
dan kemudian saya perlu dua pointer menunjuk
ke anak kiri dan anak kanan,

750
00:35:15,460 --> 00:35:16,590
masing-masing.

751
00:35:16,590 --> 00:35:20,730
Jadi itulah bagaimana kita mungkin
menerapkan bahwa dalam struct.

752
00:35:20,730 --> 00:35:22,315
Dan bagaimana mungkin aku menerapkannya dalam kode?

753
00:35:22,315 --> 00:35:26,730
Nah, mari kita cepat
lihat contoh kecil ini.

754
00:35:26,730 --> 00:35:29,820
Ini tidak fungsional, tapi aku
disalin dan disisipkan struktur itu.

755
00:35:29,820 --> 00:35:33,510
Dan jika fungsi saya untuk biner
pohon pencarian disebut pencarian,

756
00:35:33,510 --> 00:35:36,980
dan ini membutuhkan dua argumen,
integer N dan pointer

757
00:35:36,980 --> 00:35:41,400
ke node, sehingga pointer ke pohon
atau pointer ke akar pohon,

758
00:35:41,400 --> 00:35:43,482
bagaimana aku pergi tentang mencari N?

759
00:35:43,482 --> 00:35:45,440
Yah, pertama, karena aku
berurusan dengan pointer,

760
00:35:45,440 --> 00:35:46,750
Aku akan melakukan pemeriksaan kewarasan.

761
00:35:46,750 --> 00:35:54,279
Jika sama dengan pohon sama dengan nol, adalah N
di pohon ini atau tidak di pohon ini?

762
00:35:54,279 --> 00:35:55,070
Hal ini tidak bisa, kan?

763
00:35:55,070 --> 00:35:56,870
Jika saya melewati null,
tidak ada di sana.

764
00:35:56,870 --> 00:35:59,230
Aku mungkin juga hanya
membabi buta mengatakan kembali palsu.

765
00:35:59,230 --> 00:36:04,050
Jika Anda memberi saya apa-apa, saya pasti tidak bisa
menemukan nomor N. Jadi apa lagi mungkin aku

766
00:36:04,050 --> 00:36:04,750
cek sekarang?

767
00:36:04,750 --> 00:36:12,830
Aku akan mengatakan baik lain jika N adalah
kurang dari apa pun yang pada node pohon

768
00:36:12,830 --> 00:36:16,300
bahwa saya telah menyerahkan nilai N.

769
00:36:16,300 --> 00:36:20,270
Dengan kata lain, jika nomor saya
mencari, N, kurang dari node

770
00:36:20,270 --> 00:36:21,340
bahwa saya sedang melihat.

771
00:36:21,340 --> 00:36:23,190
Dan node yang saya cari
di disebut pohon,

772
00:36:23,190 --> 00:36:26,370
dan ingat dari contoh sebelumnya
untuk mendapatkan nilai di pointer,

773
00:36:26,370 --> 00:36:28,310
Saya menggunakan notasi panah.

774
00:36:28,310 --> 00:36:35,960
Jadi jika N kurang dari pohon panah
N, saya ingin konseptual pergi kiri.

775
00:36:35,960 --> 00:36:38,590
Bagaimana cara mengungkapkan searching meninggalkan?

776
00:36:38,590 --> 00:36:41,560
Untuk menjadi jelas, apakah ini
gambar tersebut,

777
00:36:41,560 --> 00:36:44,612
dan saya sudah melewati yang paling atas
panah yang menunjuk ke bawah.

778
00:36:44,612 --> 00:36:45,570
Itu pointer pohon saya.

779
00:36:45,570 --> 00:36:48,060
Aku menunjuk pada akar pohon.

780
00:36:48,060 --> 00:36:52,100
Dan aku mencari katakanlah, untuk
jumlah 44, sewenang-wenang.

781
00:36:52,100 --> 00:36:55,300
Apakah 44 kurang dari atau
lebih besar dari 55 jelas?

782
00:36:55,300 --> 00:36:56,360
Jadi itu kurang dari.

783
00:36:56,360 --> 00:36:58,760
Dan jadi ini jika kondisi berlaku.

784
00:36:58,760 --> 00:37:03,981
Jadi secara konseptual, apa yang ingin saya
mencari berikutnya jika saya sedang mencari 44?

785
00:37:03,981 --> 00:37:04,480
Ya?

786
00:37:04,480 --> 00:37:08,310

787
00:37:08,310 --> 00:37:11,100
>> Tepat, saya ingin
mencari anak kiri,

788
00:37:11,100 --> 00:37:12,789
atau meninggalkan sub-pohon gambar ini.

789
00:37:12,789 --> 00:37:14,830
Dan pada kenyataannya, biarkan aku melalui
gambar di sini

790
00:37:14,830 --> 00:37:17,770
untuk sesaat, karena
Saya tidak bisa menggaruk ini.

791
00:37:17,770 --> 00:37:21,150
Jika saya mulai di sini di 55, dan
Saya tahu bahwa nilai 44

792
00:37:21,150 --> 00:37:23,180
Saya mencari adalah untuk
kiri, itu semacam

793
00:37:23,180 --> 00:37:26,010
seperti merobek buku telepon di
setengah atau merobek pohon di setengah.

794
00:37:26,010 --> 00:37:29,660
Saya tidak lagi harus peduli
Seluruh setengah ini pohon.

795
00:37:29,660 --> 00:37:33,270
Namun, anehnya dalam hal
struktur, hal ini di sini bahwa

796
00:37:33,270 --> 00:37:36,682
dimulai dengan 33, yang itu sendiri
adalah pohon pencarian biner.

797
00:37:36,682 --> 00:37:39,890
Aku mengatakan kata rekursif sebelumnya karena
memang ini adalah struktur data yang

798
00:37:39,890 --> 00:37:41,707
menurut definisi adalah rekursif.

799
00:37:41,707 --> 00:37:44,540
Anda mungkin memiliki pohon yang ini
besar, tapi setiap salah satu dari anak-anaknya

800
00:37:44,540 --> 00:37:46,870
merupakan pohon hanya sedikit lebih kecil.

801
00:37:46,870 --> 00:37:50,910
Bukannya itu menjadi kakek
atau nenek, sekarang itu hanya ibu

802
00:37:50,910 --> 00:37:54,300
or-- Saya tidak bisa say-- tidak ibu
atau ayah, yang akan menjadi aneh.

803
00:37:54,300 --> 00:37:59,000
Sebaliknya dua anak-anak ada
akan seperti kakak dan saudara.

804
00:37:59,000 --> 00:38:01,120
Sebuah generasi baru dari pohon keluarga.

805
00:38:01,120 --> 00:38:02,900
Tapi secara struktural, itu ide yang sama.

806
00:38:02,900 --> 00:38:06,790
Dan ternyata saya memiliki fungsi
dengan yang saya dapat mencari pencarian biner

807
00:38:06,790 --> 00:38:07,290
pohon.

808
00:38:07,290 --> 00:38:08,680
Hal ini disebut pencarian.

809
00:38:08,680 --> 00:38:17,870
Saya mencari N di pohon panah kiri
lain jika N lebih besar dari nilai

810
00:38:17,870 --> 00:38:18,870
bahwa aku saat ini di.

811
00:38:18,870 --> 00:38:20,800
55 dalam kisah beberapa saat yang lalu.

812
00:38:20,800 --> 00:38:23,780
Saya memiliki fungsi yang disebut
pencari yang aku hanya bisa

813
00:38:23,780 --> 00:38:29,660
lulus N ini dan secara rekursif mencari
sub-pohon dan hanya pulang

814
00:38:29,660 --> 00:38:30,620
apapun jawaban itu.

815
00:38:30,620 --> 00:38:33,530
Lain saya punya beberapa kasus dasar akhir di sini.

816
00:38:33,530 --> 00:38:35,310
>> Apa yang terjadi akhir?

817
00:38:35,310 --> 00:38:36,570
Pohon baik null.

818
00:38:36,570 --> 00:38:39,980
Nilai saya baik cari adalah
kurang dari itu atau lebih besar dari itu

819
00:38:39,980 --> 00:38:42,610
atau sama dengan itu.

820
00:38:42,610 --> 00:38:44,750
Dan saya bisa mengatakan yang sama
sama, tapi secara logis itu

821
00:38:44,750 --> 00:38:46,500
setara dengan hanya mengatakan yang lain di sini.

822
00:38:46,500 --> 00:38:49,150
Jadi yang benar adalah bagaimana saya menemukan sesuatu.

823
00:38:49,150 --> 00:38:51,710
Jadi mudah-mudahan ini adalah
bahkan contoh yang lebih menarik

824
00:38:51,710 --> 00:38:54,900
dari fungsi sigma bodoh
kami melakukan beberapa kuliah kembali,

825
00:38:54,900 --> 00:38:58,360
di mana itu hanya sebagai mudah untuk menggunakan loop
untuk menghitung semua angka dari satu

826
00:38:58,360 --> 00:39:02,390
N. Berikut dengan struktur data
itu sendiri adalah rekursif

827
00:39:02,390 --> 00:39:07,050
didefinisikan secara rekursif dan ditarik, sekarang kita
memiliki kemampuan untuk mengekspresikan diri

828
00:39:07,050 --> 00:39:09,780
dalam kode itu sendiri adalah rekursif.

829
00:39:09,780 --> 00:39:12,580
Jadi ini adalah tepat kode yang sama di sini.

830
00:39:12,580 --> 00:39:14,400
>> Jadi apa masalah lain yang bisa kita memecahkan?

831
00:39:14,400 --> 00:39:18,160
Jadi langkah cepat dari
pohon untuk sesaat.

832
00:39:18,160 --> 00:39:20,130
Di sini adalah, mengatakan, bendera Jerman.

833
00:39:20,130 --> 00:39:22,020
Dan ada jelas
pola bendera ini.

834
00:39:22,020 --> 00:39:23,811
Dan ada banyak
bendera di dunia yang

835
00:39:23,811 --> 00:39:27,560
adalah sebagai sederhana seperti ini dalam hal
warna dan pola mereka.

836
00:39:27,560 --> 00:39:31,930
Tapi anggaplah bahwa ini disimpan sebagai
.GIF, Atau JPEG, atau bitmap, atau ping,

837
00:39:31,930 --> 00:39:34,240
format file grafis
dengan yang Anda kenal,

838
00:39:34,240 --> 00:39:36,460
beberapa di antaranya kami
bermain dengan di PSET4.

839
00:39:36,460 --> 00:39:41,550
Ini tampaknya tidak berharga untuk menyimpan
pixel hitam, piksel hitam, pixel hitam,

840
00:39:41,550 --> 00:39:44,790
dot, dot, dot, sejumlah besar
piksel hitam untuk scanline pertama,

841
00:39:44,790 --> 00:39:47,430
atau baris, kemudian sejumlah besar
sama, maka seluruh kelompok itu

842
00:39:47,430 --> 00:39:49,530
yang sama, dan kemudian
Seluruh sekelompok piksel merah,

843
00:39:49,530 --> 00:39:53,020
piksel merah, piksel merah, maka keseluruhan
sekelompok piksel kuning, kuning, kan?

844
00:39:53,020 --> 00:39:55,050
>> Ada inefisiensi seperti di sini.

845
00:39:55,050 --> 00:39:59,040
Bagaimana Anda secara intuitif
kompres bendera Jerman

846
00:39:59,040 --> 00:40:01,320
jika mengimplementasikannya sebagai file?

847
00:40:01,320 --> 00:40:04,940
Seperti informasi apa yang bisa kita tidak
repot-repot menyimpan pada disk agar

848
00:40:04,940 --> 00:40:08,040
untuk mengurangi ukuran file kita dari seperti
megabyte untuk kilobyte, sesuatu

849
00:40:08,040 --> 00:40:09,430
lebih kecil?

850
00:40:09,430 --> 00:40:13,130
Dimana terletak redundansi
di sini harus jelas?

851
00:40:13,130 --> 00:40:13,880
Apa yang bisa Anda lakukan?

852
00:40:13,880 --> 00:40:14,380
Ya?

853
00:40:14,380 --> 00:40:21,380

854
00:40:21,380 --> 00:40:21,970
Tepat.

855
00:40:21,970 --> 00:40:24,550
Mengapa tidak bukan ingat
warna setiap pixel menisik

856
00:40:24,550 --> 00:40:28,200
seperti yang Anda lakukan di PSET4
dengan format file bitmap,

857
00:40:28,200 --> 00:40:32,060
kenapa tidak Anda hanya mewakili
kolom paling kiri piksel, misalnya

858
00:40:32,060 --> 00:40:35,370
sekelompok piksel hitam, a bunch
merah, dan sekelompok kuning,

859
00:40:35,370 --> 00:40:39,210
dan kemudian hanya entah bagaimana mengkodekan
Ide ulangi ini 100 kali

860
00:40:39,210 --> 00:40:41,020
atau mengulang ini 1.000 kali?

861
00:40:41,020 --> 00:40:43,430
Di mana 100 atau 1000 adalah
hanya sebuah integer, sehingga Anda

862
00:40:43,430 --> 00:40:47,290
bisa lolos dengan hanya satu nomor
bukannya ratusan atau ribuan

863
00:40:47,290 --> 00:40:48,270
piksel tambahan.

864
00:40:48,270 --> 00:40:50,990
Dan memang, itulah bagaimana kami
bisa memampatkan bendera Jerman.

865
00:40:50,990 --> 00:40:51,490
Dan

866
00:40:51,490 --> 00:40:53,470
Sekarang bagaimana dengan bendera Prancis?

867
00:40:53,470 --> 00:40:58,930
Dan sedikit semacam
latihan mental, yang bendera

868
00:40:58,930 --> 00:41:01,040
dapat dikompresi lebih pada disk?

869
00:41:01,040 --> 00:41:05,720
Bendera Jerman atau Perancis
bendera, jika kita mengambil pendekatan itu?

870
00:41:05,720 --> 00:41:08,490
Jerman bendera, karena ada
lebih redundansi horizontal.

871
00:41:08,490 --> 00:41:12,190
Dan dengan desain, banyak berkas grafis
format memang bekerja sebagai garis pemindaian

872
00:41:12,190 --> 00:41:12,830
horizontal.

873
00:41:12,830 --> 00:41:14,674
Mereka bisa bekerja
vertikal, hanya manusia

874
00:41:14,674 --> 00:41:17,090
tahun lalu memutuskan bahwa kami akan
umumnya memikirkan hal-hal baris

875
00:41:17,090 --> 00:41:18,880
demi baris bukan kolom dengan kolom.

876
00:41:18,880 --> 00:41:20,820
Jadi memang jika Anda
untuk melihat file

877
00:41:20,820 --> 00:41:24,670
ukuran bendera Jerman dan Perancis
bendera, asalkan resolusi

878
00:41:24,670 --> 00:41:27,530
sama, lebar yang sama
dan tinggi, yang satu ini

879
00:41:27,530 --> 00:41:31,580
di sini akan menjadi lebih besar, karena Anda
harus mengulang sendiri tiga kali.

880
00:41:31,580 --> 00:41:35,570
Anda harus menentukan biru, ulangi
sendiri, putih, ulangi diri, merah,

881
00:41:35,570 --> 00:41:36,740
ulangi diri.

882
00:41:36,740 --> 00:41:39,000
Anda tidak bisa hanya pergi semua
cara ke kanan.

883
00:41:39,000 --> 00:41:41,200
Dan sebagai samping, untuk membuat
jelas kompresi

884
00:41:41,200 --> 00:41:43,910
di mana-mana, jika ini
empat frame dari video-- kamu

885
00:41:43,910 --> 00:41:45,890
mungkin ingat bahwa film
atau video umumnya

886
00:41:45,890 --> 00:41:47,286
seperti 29 atau 30 frame per detik.

887
00:41:47,286 --> 00:41:50,410
Ini seperti sebuah buku flip kecil di mana Anda
hanya melihat gambar, gambar, foto, gambar,

888
00:41:50,410 --> 00:41:54,410
gambar hanya super cepat sehingga terlihat seperti
aktor di layar bergerak.

889
00:41:54,410 --> 00:41:57,130
Berikut adalah lebah di
atas seikat bunga.

890
00:41:57,130 --> 00:41:59,790
Dan meskipun mungkin jenis
sulit untuk melihat pada pandangan pertama,

891
00:41:59,790 --> 00:42:04,020
satu-satunya hal yang bergerak di
film ini adalah lebah.

892
00:42:04,020 --> 00:42:06,880
>> Apa yang bodoh tentang menyimpan
Video terkompresi?

893
00:42:06,880 --> 00:42:11,420
Ini semacam limbah untuk menyimpan video yang
empat gambar hampir identik yang

894
00:42:11,420 --> 00:42:13,670
hanya berbeda sejauh mana lebah adalah.

895
00:42:13,670 --> 00:42:16,280
Anda dapat membuang sebagian
informasi yang

896
00:42:16,280 --> 00:42:20,190
dan ingat saja, misalnya,
frame pertama dan frame terakhir,

897
00:42:20,190 --> 00:42:22,180
frame kunci jika Anda sudah
pernah mendengar kata,

898
00:42:22,180 --> 00:42:24,337
dan hanya menyimpan di
tengah di mana lebah tersebut.

899
00:42:24,337 --> 00:42:26,170
Dan Anda tidak perlu
menyimpan semua merah muda,

900
00:42:26,170 --> 00:42:28,330
dan biru, dan
nilai-nilai hijau juga.

901
00:42:28,330 --> 00:42:31,200
Jadi ini hanya mengatakan bahwa
kompresi di mana-mana.

902
00:42:31,200 --> 00:42:34,900
Ini adalah teknik kita sering menggunakan
atau mengambil untuk diberikan hari ini.

903
00:42:34,900 --> 00:42:38,750
>> Tapi bagaimana Anda kompres teks?

904
00:42:38,750 --> 00:42:40,450
Bagaimana Anda pergi tentang mengompresi teks?

905
00:42:40,450 --> 00:42:45,410
Nah, masing-masing karakter dalam
Ascii adalah satu byte, atau delapan bit.

906
00:42:45,410 --> 00:42:47,360
Dan itu semacam bodoh, kan?

907
00:42:47,360 --> 00:42:51,160
Karena Anda mungkin tipe A
dan E dan I dan O dan U banyak

908
00:42:51,160 --> 00:42:55,270
lebih sering daripada seperti W atau Q atau Z,
tergantung pada bahasa yang

909
00:42:55,270 --> 00:42:56,610
Anda sedang menulis pasti.

910
00:42:56,610 --> 00:42:59,600
Dan jadi mengapa kita menggunakan
delapan bit untuk setiap huruf,

911
00:42:59,600 --> 00:43:02,040
termasuk yang paling
surat populer, kan?

912
00:43:02,040 --> 00:43:05,300
Mengapa tidak menggunakan bit yang lebih sedikit untuk
huruf super populer,

913
00:43:05,300 --> 00:43:07,760
seperti E, hal-hal yang Anda menebak
pertama di Wheel of Fortune,

914
00:43:07,760 --> 00:43:10,450
dan menggunakan lebih banyak bit untuk
huruf kurang populer?

915
00:43:10,450 --> 00:43:10,950
Mengapa?

916
00:43:10,950 --> 00:43:13,130
Karena kita hanya akan
menggunakannya lebih jarang.

917
00:43:13,130 --> 00:43:15,838
>> Nah, ternyata ada memiliki
telah membuat upaya untuk melakukan hal ini.

918
00:43:15,838 --> 00:43:18,630
Dan jika Anda ingat dari kelas
sekolah atau sekolah tinggi, kode Morse.

919
00:43:18,630 --> 00:43:20,400
Kode Morse memiliki titik
dan garis yang dapat

920
00:43:20,400 --> 00:43:24,270
ditransmisikan sepanjang kawat sebagai
suara atau sinyal dari beberapa macam.

921
00:43:24,270 --> 00:43:25,930
Tetapi kode Morse adalah super bersih.

922
00:43:25,930 --> 00:43:29,010
Ini semacam sistem biner di
bahwa Anda memiliki titik-titik atau tanda hubung.

923
00:43:29,010 --> 00:43:30,977
Tetapi jika Anda melihat, misalnya, dua titik.

924
00:43:30,977 --> 00:43:33,810
Atau jika Anda berpikir kembali ke operator
yang berjalan seperti bip, bip, bip,

925
00:43:33,810 --> 00:43:36,760
bip, memukul pemicu sedikit
yang mengirimkan sinyal,

926
00:43:36,760 --> 00:43:40,360
jika Anda, penerima, menerima dua
titik, apa pesan yang Anda terima?

927
00:43:40,360 --> 00:43:43,490
Benar-benar sewenang-wenang.

928
00:43:43,490 --> 00:43:44,450
>> Saya?

929
00:43:44,450 --> 00:43:45,060
Saya?

930
00:43:45,060 --> 00:43:47,500
Atau apa about-- atau aku?

931
00:43:47,500 --> 00:43:49,570
Mungkin itu hanya dua E kan?

932
00:43:49,570 --> 00:43:52,480
Jadi ada masalah ini
dari decodability dengan Morse

933
00:43:52,480 --> 00:43:54,890
kode, dimana kecuali
orang yang mengirim Anda pesan

934
00:43:54,890 --> 00:43:59,510
sebenarnya berhenti sehingga Anda dapat mengurutkan dari
melihat atau mendengar kesenjangan antara huruf,

935
00:43:59,510 --> 00:44:02,990
itu tidak cukup hanya untuk
mengirim sungai dari nol dan satu,

936
00:44:02,990 --> 00:44:05,610
atau titik dan garis,
karena ada ambiguitas.

937
00:44:05,610 --> 00:44:08,640
E adalah satu titik, jadi jika Anda
melihat dua titik atau mendengar dua titik,

938
00:44:08,640 --> 00:44:11,254
mungkin itu dua E atau mungkin itu salah satu I.

939
00:44:11,254 --> 00:44:13,670
Jadi kita perlu sistem yang merupakan
sedikit lebih pintar dari itu.

940
00:44:13,670 --> 00:44:16,851
Jadi seorang pria bernama Huffman tahun
lalu datang dengan persis ini.

941
00:44:16,851 --> 00:44:18,600
Jadi kita hanya akan
untuk mengambil sekilas

942
00:44:18,600 --> 00:44:20,114
bagaimana pohon erat dengan ini.

943
00:44:20,114 --> 00:44:22,530
Misalkan ini adalah beberapa
Pesan bodoh Anda ingin mengirim,

944
00:44:22,530 --> 00:44:26,342
terdiri dari hanya A, B, C D's dan E,
tapi ada banyak redundansi di sini.

945
00:44:26,342 --> 00:44:27,550
Ini tidak dimaksudkan untuk menjadi bahasa Inggris.

946
00:44:27,550 --> 00:44:28,341
Itu tidak dienkripsi.

947
00:44:28,341 --> 00:44:30,540
Ini hanya pesan bodoh
dengan banyak pengulangan.

948
00:44:30,540 --> 00:44:34,010
Jadi jika Anda benar-benar menghitung semua
A, B, C, D, dan E, inilah

949
00:44:34,010 --> 00:44:34,890
frekuensi.

950
00:44:34,890 --> 00:44:37,800
20% dari surat-surat yang
A, 45% dari huruf

951
00:44:37,800 --> 00:44:39,660
adalah E, dan tiga frekuensi lainnya.

952
00:44:39,660 --> 00:44:41,960
Kami menghitung di sana secara manual
dan hanya melakukan matematika.

953
00:44:41,960 --> 00:44:44,579
>> Jadi ternyata bahwa
Huffman, beberapa waktu lalu,

954
00:44:44,579 --> 00:44:46,620
menyadari bahwa, Anda tahu
apa, jika saya mulai membangun

955
00:44:46,620 --> 00:44:51,172
pohon, atau hutan pohon, jika Anda mau,
sebagai berikut, saya dapat melakukan hal berikut.

956
00:44:51,172 --> 00:44:53,880
Aku akan memberikan node ke setiap
dari surat-surat yang saya peduli

957
00:44:53,880 --> 00:44:55,530
dan aku akan menyimpan
dalam simpul yang

958
00:44:55,530 --> 00:44:58,610
frekuensi sebagai floating point
nilai, atau Anda bisa menggunakannya N, juga,

959
00:44:58,610 --> 00:45:00,210
tapi kita hanya akan menggunakan pelampung di sini.

960
00:45:00,210 --> 00:45:03,100
Dan algoritma yang
ia mengusulkan adalah bahwa Anda

961
00:45:03,100 --> 00:45:07,210
mengambil hutan ini dari node tunggal
pohon, pohon jadi super pendek,

962
00:45:07,210 --> 00:45:11,920
dan Anda mulai menghubungkan mereka dengan
kelompok baru, orang tua baru, jika Anda mau.

963
00:45:11,920 --> 00:45:16,150
Dan Anda melakukan ini dengan memilih
dua frekuensi terkecil pada suatu waktu.

964
00:45:16,150 --> 00:45:18,110
Jadi saya mengambil 10% dan 10%.

965
00:45:18,110 --> 00:45:19,090
Saya membuat node baru.

966
00:45:19,090 --> 00:45:20,910
Dan saya sebut node baru 20%.

967
00:45:20,910 --> 00:45:22,750
>> Yang dua node saya menggabungkan berikutnya?

968
00:45:22,750 --> 00:45:23,810
Ini sedikit ambigu.

969
00:45:23,810 --> 00:45:26,643
Jadi ada beberapa kasus sudut untuk
mempertimbangkan, tetapi untuk menjaga hal-hal yang cukup,

970
00:45:26,643 --> 00:45:29,300
Aku akan memilih 20% -
Sekarang saya mengabaikan anak-anak.

971
00:45:29,300 --> 00:45:33,640
Aku akan memilih 20% dan
15% dan menarik dua sisi yang baru.

972
00:45:33,640 --> 00:45:35,624
Dan sekarang yang dua node
saya logis menggabungkan?

973
00:45:35,624 --> 00:45:38,540
Mengabaikan semua anak, semua
cucu, hanya melihat akar

974
00:45:38,540 --> 00:45:39,070
sekarang.

975
00:45:39,070 --> 00:45:42,220
Yang dua node saya mengikat bersama?

976
00:45:42,220 --> 00:45:44,530
Titik dua dan 0,35.

977
00:45:44,530 --> 00:45:45,890
Jadi biarkan aku menggambar dua sisi baru.

978
00:45:45,890 --> 00:45:47,570
Dan kemudian aku hanya punya satu kiri.

979
00:45:47,570 --> 00:45:48,650
Jadi, inilah pohon.

980
00:45:48,650 --> 00:45:51,160
Dan itu sudah ditarik sengaja
untuk melihat jenis cantik,

981
00:45:51,160 --> 00:45:55,870
tapi melihat bahwa tepi memiliki
juga telah diberi label nol dan satu.

982
00:45:55,870 --> 00:45:59,510
Jadi semua tepi kiri adalah nol
sewenang-wenang, tetapi secara konsisten.

983
00:45:59,510 --> 00:46:01,170
Semua tepi kanan adalah orang-orang.

984
00:46:01,170 --> 00:46:05,070
>> Dan jadi apa Hoffman diusulkan adalah,
jika Anda ingin mewakili B,

985
00:46:05,070 --> 00:46:10,080
bukan merupakan jumlah 66 sebagai
sebuah Ascii yang delapan seluruh bit,

986
00:46:10,080 --> 00:46:13,360
Anda tahu apa, hanya toko
pola nol, nol, nol,

987
00:46:13,360 --> 00:46:17,030
nol, karena itulah jalan
dari pohon saya, pohon Mr. Huffman,

988
00:46:17,030 --> 00:46:18,600
dengan daun dari akar.

989
00:46:18,600 --> 00:46:20,970
Jika Anda ingin menyimpan
E, sebaliknya, tidak

990
00:46:20,970 --> 00:46:26,290
mengirim delapan bit yang mewakili suatu E.
Sebaliknya, mengirim apa pola bit?

991
00:46:26,290 --> 00:46:26,890
Satu.

992
00:46:26,890 --> 00:46:30,410
Dan apa yang baik tentang ini
bahwa E adalah huruf yang paling populer,

993
00:46:30,410 --> 00:46:32,340
dan Anda menggunakan
kode terpendek untuk itu.

994
00:46:32,340 --> 00:46:34,090
Berikutnya yang paling populer
Surat terlihat seperti itu

995
00:46:34,090 --> 00:46:37,380
adalah A. Dan begitu berapa banyak bit
dia mengusulkan menggunakan untuk itu?

996
00:46:37,380 --> 00:46:38,270
Nol, satu.

997
00:46:38,270 --> 00:46:41,060
>> Dan karena itu diimplementasikan
pohon ini, untuk saat ini

998
00:46:41,060 --> 00:46:43,350
biarkan aku menetapkan ada
tidak ada ambiguitas seperti dalam Morse

999
00:46:43,350 --> 00:46:46,090
kode, karena semua
surat Anda peduli

1000
00:46:46,090 --> 00:46:48,780
adalah pada akhir tepi ini.

1001
00:46:48,780 --> 00:46:50,580
Jadi itu hanya satu
penerapan pohon.

1002
00:46:50,580 --> 00:46:52,538
Ini is-- dan aku akan gelombang
tanganku di bagaimana Anda

1003
00:46:52,538 --> 00:46:55,570
mungkin menerapkan ini sebagai struktur C.

1004
00:46:55,570 --> 00:46:58,260
Kita hanya perlu untuk menggabungkan
simbol, seperti char,

1005
00:46:58,260 --> 00:46:59,910
dan frekuensi di kiri dan kanan.

1006
00:46:59,910 --> 00:47:02,510
Tapi mari kita lihat dua
contoh terakhir yang Anda akan

1007
00:47:02,510 --> 00:47:06,070
mendapatkan cukup akrab dengan setelah
kuis nol dalam masalah mengatur lima.

1008
00:47:06,070 --> 00:47:09,210
>> Jadi ada struktur data
dikenal sebagai tabel hash.

1009
00:47:09,210 --> 00:47:12,247
Dan tabel hash adalah jenis
dingin dalam hal ini memiliki ember.

1010
00:47:12,247 --> 00:47:14,830
Dan misalkan ada empat ember
di sini, hanya empat ruang kosong.

1011
00:47:14,830 --> 00:47:20,830
Berikut setumpuk kartu, dan di sini adalah
klub, sekop, klub, berlian, klub,

1012
00:47:20,830 --> 00:47:25,960
berlian, klub, berlian,
clubs-- jadi ini adalah acak.

1013
00:47:25,960 --> 00:47:30,330
Hati, hearts-- jadi aku
bucketizing semua input di sini.

1014
00:47:30,330 --> 00:47:32,430
Dan kebutuhan tabel hash
untuk melihat masukan Anda,

1015
00:47:32,430 --> 00:47:34,850
dan kemudian memasukkannya ke dalam tertentu
menempatkan berdasarkan apa yang Anda lihat.

1016
00:47:34,850 --> 00:47:35,600
Ini adalah algoritma.

1017
00:47:35,600 --> 00:47:37,980
Dan saya menggunakan super
algoritma visual yang sederhana.

1018
00:47:37,980 --> 00:47:40,030
Bagian tersulit dari yang
mengingat apa foto-foto itu.

1019
00:47:40,030 --> 00:47:41,590
Dan kemudian ada jumlah empat hal.

1020
00:47:41,590 --> 00:47:45,440
>> Sekarang tumpukan tumbuh, yang
adalah desain hal yang disengaja di sini.

1021
00:47:45,440 --> 00:47:46,540
Tapi apa lagi yang mungkin saya lakukan?

1022
00:47:46,540 --> 00:47:49,080
Jadi sebenarnya di sini kita memiliki
sekelompok buku ujian sekolah tua.

1023
00:47:49,080 --> 00:47:51,240
Misalkan sekelompok
nama siswa di sini.

1024
00:47:51,240 --> 00:47:52,570
Berikut adalah tabel hash yang lebih besar.

1025
00:47:52,570 --> 00:47:54,867
Bukan empat ember,
Saya telah, katakanlah 26.

1026
00:47:54,867 --> 00:47:57,950
Dan kami tidak ingin pergi meminjam 26
hal dari luar [? Annenberg?], Jadi

1027
00:47:57,950 --> 00:48:00,289
inilah lima yang mewakili
A sampai Z. Dan jika saya

1028
00:48:00,289 --> 00:48:03,580
melihat seorang mahasiswa yang namanya dimulai dengan A,
Aku akan menaruh atau kuis di sana.

1029
00:48:03,580 --> 00:48:08,850
Jika seseorang mulai dengan C, di sana,
A-- sebenarnya, tidak ingin melakukan itu.

1030
00:48:08,850 --> 00:48:10,060
B berjalan di atas sini.

1031
00:48:10,060 --> 00:48:13,390
Jadi saya punya A dan B dan C. Dan
sekarang inilah Seorang siswa lain.

1032
00:48:13,390 --> 00:48:16,212
Tetapi jika tabel hash ini
diimplementasikan dengan array,

1033
00:48:16,212 --> 00:48:17,920
Aku agak kacau
pada titik ini, kan?

1034
00:48:17,920 --> 00:48:19,510
Aku agak perlu menempatkan tempat ini.

1035
00:48:19,510 --> 00:48:24,380
>> Jadi salah satu cara saya bisa memecahkan ini, semua
benar, A sibuk, B sibuk, C sibuk.

1036
00:48:24,380 --> 00:48:28,880
Aku akan menempatkan dia di D. Jadi pada
pertama, saya memiliki akses cepat random

1037
00:48:28,880 --> 00:48:31,064
untuk masing-masing ember untuk siswa.

1038
00:48:31,064 --> 00:48:33,230
Tapi sekarang itu semacam didesentralisasikan
menjadi sesuatu yang linear,

1039
00:48:33,230 --> 00:48:36,750
karena jika saya ingin mencari seseorang
Nama yang dimulai dengan A, saya cek di sini.

1040
00:48:36,750 --> 00:48:38,854
Tapi jika ini bukan A
student Saya mencari,

1041
00:48:38,854 --> 00:48:41,520
Aku agak harus mulai memeriksa
ember, karena apa yang saya lakukan

1042
00:48:41,520 --> 00:48:44,530
adalah semacam linear
menyelidiki struktur data.

1043
00:48:44,530 --> 00:48:47,710
Sebuah cara yang bodoh untuk mengatakan hanya melihat
untuk pembukaan tersedia pertama,

1044
00:48:47,710 --> 00:48:51,850
dan menempatkan sebagai rencana B, sehingga untuk berbicara,
atau rencana D dalam hal ini, nilai

1045
00:48:51,850 --> 00:48:53,340
di lokasi itu sebagai gantinya.

1046
00:48:53,340 --> 00:48:56,470
Ini hanyalah sehingga jika Anda sudah
mendapat 26 lokasi dan tidak ada siswa

1047
00:48:56,470 --> 00:49:00,600
dengan nama Q atau Z, atau sesuatu seperti
itu, setidaknya Anda menggunakan ruang.

1048
00:49:00,600 --> 00:49:03,140
>> Tapi kami sudah melihat lebih
solusi pintar di sini, kan?

1049
00:49:03,140 --> 00:49:04,870
Apa yang akan Anda lakukan sebagai gantinya
jika Anda memiliki tabrakan?

1050
00:49:04,870 --> 00:49:06,670
Jika dua orang memiliki
nama A, apa yang akan

1051
00:49:06,670 --> 00:49:09,160
telah cerdas atau lebih
solusi intuitif dari sekedar

1052
00:49:09,160 --> 00:49:12,840
menempatkan A di mana D seharusnya?

1053
00:49:12,840 --> 00:49:14,810
Kenapa tidak aku hanya pergi
luar [? Annenberg?],

1054
00:49:14,810 --> 00:49:19,960
seperti malloc, node lain, meletakkannya
di sini, dan kemudian menempatkan bahwa Seorang mahasiswa di sini.

1055
00:49:19,960 --> 00:49:22,120
Sehingga saya pada dasarnya memiliki
semacam array,

1056
00:49:22,120 --> 00:49:25,590
atau mungkin lebih elegan seperti kita
mulai melihat sebuah linked list.

1057
00:49:25,590 --> 00:49:29,520
>> Dan tabel hash adalah struktur
yang bisa terlihat seperti ini,

1058
00:49:29,520 --> 00:49:33,900
tetapi lebih cerdik, Anda sesuatu yang disebut
chaining terpisah, dimana tabel hash

1059
00:49:33,900 --> 00:49:38,340
cukup sederhana adalah array, masing-masing
yang unsur bukan angka,

1060
00:49:38,340 --> 00:49:40,470
sendiri merupakan linked list.

1061
00:49:40,470 --> 00:49:45,080
Sehingga Anda mendapatkan akses super cepat
memutuskan mana untuk hash nilai untuk.

1062
00:49:45,080 --> 00:49:48,059
Sama seperti dengan contoh kartu,
Saya membuat keputusan super cepat.

1063
00:49:48,059 --> 00:49:49,600
Hati goes here, berlian goes here.

1064
00:49:49,600 --> 00:49:52,180
Sama di sini, A goes here,
D goes here, B goes here.

1065
00:49:52,180 --> 00:49:55,740
Jadi super cepat look-up, dan jika
Anda kebetulan mengalami kasus

1066
00:49:55,740 --> 00:49:59,429
tabrakan di mana Anda punya, dua
orang dengan nama yang sama, baik maka

1067
00:49:59,429 --> 00:50:00,970
Anda hanya mulai menghubungkan mereka bersama-sama.

1068
00:50:00,970 --> 00:50:03,900
Dan mungkin Anda menjaga mereka diurutkan
abjad, mungkin Anda tidak.

1069
00:50:03,900 --> 00:50:05,900
Tapi setidaknya sekarang kita memiliki dinamika tersebut.

1070
00:50:05,900 --> 00:50:10,250
Jadi di satu sisi kita memiliki super cepat
waktu yang konstan, dan jenis waktu linear

1071
00:50:10,250 --> 00:50:14,110
terlibat jika ini daftar terkait
mulai mendapatkan sedikit lama.

1072
00:50:14,110 --> 00:50:16,880
>> Jadi semacam ini konyol,
lelucon tahun culun lalu.

1073
00:50:16,880 --> 00:50:19,590
Pada CS50 hack-a-thon,
ketika siswa check-in,

1074
00:50:19,590 --> 00:50:22,040
beberapa TF atau CA setiap tahun
berpikir itu lucu untuk memasang

1075
00:50:22,040 --> 00:50:27,772
tanda seperti ini, di mana ia hanya
berarti jika nama Anda dimulai dengan A,

1076
00:50:27,772 --> 00:50:28,870
pergi dengan cara ini.

1077
00:50:28,870 --> 00:50:31,110
Jika nama Anda dimulai
dengan B, pergi this-- OK,

1078
00:50:31,110 --> 00:50:33,290
itu lucu mungkin nanti di semester.

1079
00:50:33,290 --> 00:50:36,420
Tapi ada yang lain
cara untuk melakukan hal ini, juga.

1080
00:50:36,420 --> 00:50:37,410
Kembali ke itu.

1081
00:50:37,410 --> 00:50:38,600
>> Jadi ada struktur ini.

1082
00:50:38,600 --> 00:50:40,420
Dan ini adalah terakhir kami
struktur untuk hari ini,

1083
00:50:40,420 --> 00:50:42,400
yang merupakan sesuatu yang disebut trie.

1084
00:50:42,400 --> 00:50:47,140
T-R-I-E, yang untuk beberapa alasan pendek
untuk pengambilan, tapi itu disebut trie.

1085
00:50:47,140 --> 00:50:51,389
Jadi trie menarik lain
campuran dari banyak ide-ide ini.

1086
00:50:51,389 --> 00:50:52,930
Ini adalah pohon, yang telah kita lihat sebelumnya.

1087
00:50:52,930 --> 00:50:54,180
Ini bukan pohon pencarian biner.

1088
00:50:54,180 --> 00:50:58,410
Ini pohon dengan sejumlah anak-anak,
tetapi masing-masing dari anak-anak di trie

1089
00:50:58,410 --> 00:51:00,090
adalah array.

1090
00:51:00,090 --> 00:51:04,790
Array ukuran, mengatakan, 26 atau mungkin 27
jika Anda ingin mendukung nama ditulis dgn tanda penghubung

1091
00:51:04,790 --> 00:51:06,790
atau apostrof di nama orang.

1092
00:51:06,790 --> 00:51:08,280
>> Dan jadi ini adalah struktur data.

1093
00:51:08,280 --> 00:51:10,290
Dan jika Anda melihat dari atas
ke bawah, seperti jika Anda

1094
00:51:10,290 --> 00:51:13,710
melihat simpul atas sana, M, adalah
menunjuk ke hal paling kiri di sana,

1095
00:51:13,710 --> 00:51:17,665
yang kemudian A, X, W, E, L, L. Ini
hanya struktur data yang sewenang-wenang

1096
00:51:17,665 --> 00:51:19,120
adalah menyimpan nama orang.

1097
00:51:19,120 --> 00:51:25,720
Dan Maxwell disimpan dengan hanya mengikuti
jalur array ke array ke array.

1098
00:51:25,720 --> 00:51:30,050
Tapi apa yang menakjubkan tentang trie adalah
itu, sedangkan linked list dan bahkan

1099
00:51:30,050 --> 00:51:34,520
array, yang terbaik yang pernah kita mendapatkan adalah
waktu linear atau waktu logaritmik mencari

1100
00:51:34,520 --> 00:51:35,600
seseorang.

1101
00:51:35,600 --> 00:51:40,530
Dalam struktur data trie, jika
struktur data saya memiliki satu nama di dalamnya

1102
00:51:40,530 --> 00:51:43,720
dan saya sedang mencari Maxwell, aku
akan menemukannya cukup cepat.

1103
00:51:43,720 --> 00:51:47,910
Saya hanya mencari M-A-X-W-E-L-L. Jika
struktur data, sebaliknya,

1104
00:51:47,910 --> 00:51:51,830
jika N adalah satu juta, jika ada
juta nama dalam struktur data,

1105
00:51:51,830 --> 00:51:57,100
Maxwell masih akan menjadi
ditemukan setelah hanya M-A-X W-E-L-L

1106
00:51:57,100 --> 00:51:58,090
langkah.

1107
00:51:58,090 --> 00:52:01,276
Dan langkah-langkah David-- D-A-V-I-D.

1108
00:52:01,276 --> 00:52:03,400
Dengan kata lain, dengan membangun
struktur data yang

1109
00:52:03,400 --> 00:52:07,240
mendapat semua array ini, yang semuanya
sendiri mendukung akses acak,

1110
00:52:07,240 --> 00:52:11,090
Aku bisa mulai mencari orang
nama menggunakan jumlah waktu yang

1111
00:52:11,090 --> 00:52:14,340
sebanding dengan jumlah tidak
hal dalam struktur data,

1112
00:52:14,340 --> 00:52:16,330
seperti satu juta nama yang ada.

1113
00:52:16,330 --> 00:52:20,135
Jumlah waktu yang dibutuhkan saya untuk menemukan
M-A-X W-E-L-L dalam struktur data

1114
00:52:20,135 --> 00:52:22,260
proporsional tidak dengan
ukuran struktur data,

1115
00:52:22,260 --> 00:52:25,930
tetapi dengan panjang nama.

1116
00:52:25,930 --> 00:52:28,440
Dan realistis
nama kita melihat ke atas

1117
00:52:28,440 --> 00:52:29,970
tidak pernah akan menjadi gila panjang.

1118
00:52:29,970 --> 00:52:32,600
Mungkin seseorang memiliki 10 karakter
nama, 20 nama karakter.

1119
00:52:32,600 --> 00:52:33,900
Ini tentu terbatas, kan?

1120
00:52:33,900 --> 00:52:37,110
Ada manusia di bumi yang
memiliki nama terpanjang mungkin,

1121
00:52:37,110 --> 00:52:39,920
tapi nama itu adalah konstan
panjang nilai, kan?

1122
00:52:39,920 --> 00:52:41,980
Ini tidak berbeda di akal.

1123
00:52:41,980 --> 00:52:45,090
Jadi dengan cara ini, kita sudah
mencapai struktur data

1124
00:52:45,090 --> 00:52:47,800
yang waktu konstan look-up.

1125
00:52:47,800 --> 00:52:50,670
Ini tidak mengambil sejumlah langkah
tergantung pada panjang input,

1126
00:52:50,670 --> 00:52:54,250
tapi bukan jumlah nama
dalam struktur data.

1127
00:52:54,250 --> 00:52:58,700
Jadi jika kita melipatgandakan jumlah nama
tahun depan dari satu miliar untuk dua miliar,

1128
00:52:58,700 --> 00:53:03,720
Temuan Maxwell akan mengambil
jumlah yang sama persis dari tujuh langkah

1129
00:53:03,720 --> 00:53:04,650
untuk menemukannya.

1130
00:53:04,650 --> 00:53:08,810
Dan kita tampaknya telah mencapai
grail suci kami berjalan waktu.

1131
00:53:08,810 --> 00:53:10,860
>> Jadi beberapa pengumuman cepat.

1132
00:53:10,860 --> 00:53:11,850
Kuis nol akan datang.

1133
00:53:11,850 --> 00:53:14,600
Lebih pada pada website ini saja
selama beberapa hari.

1134
00:53:14,600 --> 00:53:17,120
Senin lecture-- itu libur
di sini di Harvard, Senin.

1135
00:53:17,120 --> 00:53:18,850
Hal ini tidak di New Haven,
jadi kita mengambil kelas

1136
00:53:18,850 --> 00:53:20,310
ke New Haven untuk kuliah pada hari Senin.

1137
00:53:20,310 --> 00:53:22,550
Semuanya akan difilmkan
dan disiarkan secara langsung seperti biasa,

1138
00:53:22,550 --> 00:53:24,900
tapi mari kita berakhir hari ini
dengan klip 30 detik

1139
00:53:24,900 --> 00:53:26,910
disebut "Deep Thoughts"
oleh Daven Farnham, yang

1140
00:53:26,910 --> 00:53:30,850
terinspirasi tahun lalu oleh Sabtu
"Deep Thoughts" Night Live ini

1141
00:53:30,850 --> 00:53:35,700
oleh Jack Berguna, yang
sekarang harus masuk akal.

1142
00:53:35,700 --> 00:53:38,810
>> FILM: Dan sekarang, "Jauh
Pikiran "oleh Daven Farnham.

1143
00:53:38,810 --> 00:53:42,100

1144
00:53:42,100 --> 00:53:42,870
Tabel hash.

1145
00:53:42,870 --> 00:53:45,940

1146
00:53:45,940 --> 00:53:47,660
>> SPEAKER 1: Baiklah, itu saja untuk saat ini.

1147
00:53:47,660 --> 00:53:48,805
Kita akan melihat Anda minggu depan.

1148
00:53:48,805 --> 00:53:55,380

1149
00:53:55,380 --> 00:53:56,680
>> Doug: Untuk melihat dalam tindakan.

1150
00:53:56,680 --> 00:53:58,304
Jadi mari kita lihat yang sekarang.

1151
00:53:58,304 --> 00:53:59,890
Jadi di sini, kami memiliki sebuah array disortir.

1152
00:53:59,890 --> 00:54:04,860
>> IAN: Doug, Anda dapat pergi ke depan dan me-restart
ini hanya satu detik, silahkan.

1153
00:54:04,860 --> 00:54:08,562
Baiklah, kamera bergulir, sehingga
tindakan kapan pun Anda siap, Doug, OK?

1154
00:54:08,562 --> 00:54:11,020
Doug: Baiklah, jadi apa yang kita
miliki di sini adalah array disortir.

1155
00:54:11,020 --> 00:54:13,960
Dan aku sudah berwarna semua elemen
merah untuk menunjukkan bahwa itu adalah, pada kenyataannya,

1156
00:54:13,960 --> 00:54:14,460
disortir.

1157
00:54:14,460 --> 00:54:17,960
Jadi ingat bahwa hal pertama yang kita lakukan
adalah kita mengurutkan setengah kiri dari array.

1158
00:54:17,960 --> 00:54:20,630
Kemudian kita memilah kanan
setengah dari array.

1159
00:54:20,630 --> 00:54:22,830
Dan ya-da, ya-da, ya-da,
kami menggabungkan mereka bersama-sama.

1160
00:54:22,830 --> 00:54:24,520
Dan kami memiliki array sepenuhnya diurutkan.

1161
00:54:24,520 --> 00:54:25,360
Jadi itulah cara menggabungkan semacam bekerja.

1162
00:54:25,360 --> 00:54:27,109
>> IAN: Whoa, whoa, whoa,
potong, potong, potong, potong.

1163
00:54:27,109 --> 00:54:30,130
Doug, Anda tidak bisa hanya ya-da, ya-da,
ya-da, jalan Anda melalui merge sort.

1164
00:54:30,130 --> 00:54:31,970
>> Doug: Aku hanya melakukan.

1165
00:54:31,970 --> 00:54:32,832
Tidak apa-apa.

1166
00:54:32,832 --> 00:54:33,540
Kami baik untuk pergi.

1167
00:54:33,540 --> 00:54:34,760
Mari kita terus bergulir.

1168
00:54:34,760 --> 00:54:35,380
Jadi,

1169
00:54:35,380 --> 00:54:37,800
>> IAN: Anda harus menjelaskan
lebih lengkap dari itu.

1170
00:54:37,800 --> 00:54:39,999
Itu tidak cukup.

1171
00:54:39,999 --> 00:54:41,790
Doug: Ian, kita tidak
harus kembali ke satu.

1172
00:54:41,790 --> 00:54:42,350
Tidak apa-apa.

1173
00:54:42,350 --> 00:54:45,690
Jadi, jika kita terus dengan merge--
Ian, kita berada di tengah-tengah syuting.

1174
00:54:45,690 --> 00:54:46,612
>> IAN: Saya tahu.

1175
00:54:46,612 --> 00:54:49,320
Dan kita tidak bisa hanya ya-da, ya-da,
ya-da, melalui seluruh proses.

1176
00:54:49,320 --> 00:54:52,200
Anda harus menjelaskan bagaimana
kedua belah pihak bisa bergabung bersama-sama.

1177
00:54:52,200 --> 00:54:53,570
>> Doug: Tapi kita sudah sudah
menjelaskan bagaimana dua sides--

1178
00:54:53,570 --> 00:54:55,321
>> IAN: Anda baru saja ditampilkan
mereka array merge.

1179
00:54:55,321 --> 00:54:56,486
Doug: Mereka tahu proses.

1180
00:54:56,486 --> 00:54:57,172
Mereka baik-baik saja.

1181
00:54:57,172 --> 00:54:58,380
Kami sudah lebih dari sepuluh kali.

1182
00:54:58,380 --> 00:55:00,330
>> IAN: Anda hanya melewatkan tepat di atasnya.

1183
00:55:00,330 --> 00:55:03,360
Kita akan kembali ke satu, Anda
Anda tidak bisa ya-da, ya-da di atasnya.

1184
00:55:03,360 --> 00:55:05,480
Baiklah, kembali ke satu.

1185
00:55:05,480 --> 00:55:07,833
>> Doug: Saya harus kembali
melalui semua slide?

1186
00:55:07,833 --> 00:55:08,332
Tuhanku.

1187
00:55:08,332 --> 00:55:11,008

1188
00:55:11,008 --> 00:55:13,004
Ini seperti keenam kalinya, Ian.

1189
00:55:13,004 --> 00:55:13,940
Tidak apa-apa.

1190
00:55:13,940 --> 00:55:15,200
>> IAN: Baiklah.

1191
00:55:15,200 --> 00:55:16,590
Anda siap?

1192
00:55:16,590 --> 00:55:17,400
Besar.

1193
00:55:17,400 --> 00:55:18,950
Aksi.