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 bahawa Kali terakhir kami
mula melihat data pelamun

4
00:00:19,220 --> 00:00:22,310
struktur yang mula menyelesaikan
masalah, yang mula memperkenalkan

5
00:00:22,310 --> 00:00:25,640
masalah baru, tetapi kunci kepada ini
adalah jenis threading yang kita

6
00:00:25,640 --> 00:00:27,940
mula melakukan dari nod ke nod.

7
00:00:27,940 --> 00:00:30,085
Jadi ini sudah tentu adalah
senarai secara tunggal berkaitan.

8
00:00:30,085 --> 00:00:31,960
Dan dengan secara tunggal berkaitan,
Maksud saya ada satu

9
00:00:31,960 --> 00:00:33,380
benang antara setiap orang-orang nod.

10
00:00:33,380 --> 00:00:35,890
Ternyata anda boleh lakukan pelamun
perkara seperti senarai duanya adalah terpakai dikaitkan

11
00:00:35,890 --> 00:00:38,470
di mana anda mempunyai anak panah
pergi dalam kedua-dua arah, yang

12
00:00:38,470 --> 00:00:40,320
boleh membantu dengan kecekapan tertentu.

13
00:00:40,320 --> 00:00:42,000
Tetapi ini menyelesaikan masalah?

14
00:00:42,000 --> 00:00:43,500
Apa masalah adakah ini menyelesaikan?

15
00:00:43,500 --> 00:00:46,620
Mengapa kita mengambil berat pada hari Isnin?

16
00:00:46,620 --> 00:00:49,820
Mengapa, dalam teori, adakah kita mengambil berat pada hari Isnin?

17
00:00:49,820 --> 00:00:50,630
Apa yang ia buat?

18
00:00:50,630 --> 00:00:51,950
>> PENONTON: Kami dinamik boleh mengubah saiz.

19
00:00:51,950 --> 00:00:53,740
>> SPEAKER 1: OK, jadi kita boleh
dinamik mengubah saiz.

20
00:00:53,740 --> 00:00:54,710
Syabas anda berdua.

21
00:00:54,710 --> 00:00:57,560
Jadi, anda boleh mengubah saiz dinamik ini
struktur data, manakala pelbagai,

22
00:00:57,560 --> 00:01:00,760
ingat, anda perlu tahu
priori berapa banyak ruang yang anda mahu

23
00:01:00,760 --> 00:01:03,870
dan jika anda memerlukan lebih sedikit
ruang, anda jenis daripada nasib.

24
00:01:03,870 --> 00:01:05,560
Anda perlu membuat pelbagai baru.

25
00:01:05,560 --> 00:01:07,893
Anda perlu untuk menggerakkan semua anda
data dari satu kepada yang lain,

26
00:01:07,893 --> 00:01:10,600
akhirnya membebaskan array lama
jika anda boleh, dan kemudian meneruskan.

27
00:01:10,600 --> 00:01:13,891
Yang hanya berasa sangat mahal dan sangat
tidak cekap, dan sememangnya ia boleh.

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

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

30
00:01:18,180 --> 00:01:20,550
membayar dengan menggunakan senarai berpaut?

31
00:01:20,550 --> 00:01:22,825
>> PENONTON: Kita perlu menggunakan
ruang dua kali bagi setiap satu.

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

33
00:01:25,200 --> 00:01:27,700
Malah, saya menyedari ini gambar ini
walaupun sedikit mengelirukan,

34
00:01:27,700 --> 00:01:32,200
kerana pada CS50 IDE dalam banyak moden
komputer, penunjuk atau alamat

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

36
00:01:33,700 --> 00:01:36,090
Ia amat sering ini
hari lapan bait, yang

37
00:01:36,090 --> 00:01:38,530
bermakna yang paling bawah
segi empat tepat terdapat dalam realiti

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

39
00:01:40,900 --> 00:01:44,409
yang bermaksud anda menggunakan tiga kali
ruang yang banyak seperti yang kita mungkin mempunyai sebaliknya.

40
00:01:44,409 --> 00:01:46,700
Pada waktu yang sama, kami
masih bercakap bait, bukan?

41
00:01:46,700 --> 00:01:49,140
Kita tidak semestinya bercakap
megabait atau gigabait,

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

43
00:01:51,000 --> 00:01:54,510
>> Dan sehingga hari ini kita mula mempertimbangkan
bagaimana kita boleh meneroka data

44
00:01:54,510 --> 00:01:57,310
dengan lebih cekap jika dalam
Malah data semakin besar.

45
00:01:57,310 --> 00:02:00,360
Tetapi mari kita cuba untuk canonicalize
operasi pertama

46
00:02:00,360 --> 00:02:02,460
yang boleh anda lakukan di Syarikat-
jenis struktur data.

47
00:02:02,460 --> 00:02:04,790
Jadi sesuatu seperti dikaitkan
senarai umumnya menyokong

48
00:02:04,790 --> 00:02:07,514
operasi suka memadam,
memasukkan, dan mencari.

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

50
00:02:08,639 --> 00:02:11,222
Yang hanya bermakna bahawa biasanya,
jika orang yang menggunakan senarai bersambung,

51
00:02:11,222 --> 00:02:14,287
mereka atau orang lain telah melaksanakan
fungsi seperti padam, masukkan,

52
00:02:14,287 --> 00:02:16,120
dan carian, jadi anda boleh
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 cepat
bagaimana kita mungkin melaksanakan

55
00:02:20,760 --> 00:02:24,530
beberapa kod untuk senarai berpaut seperti berikut.

56
00:02:24,530 --> 00:02:27,885
>> Jadi ini adalah hanya beberapa kod C,
tidak ada satu program yang lengkap

57
00:02:27,885 --> 00:02:29,260
bahawa saya benar-benar cepat disebat.

58
00:02:29,260 --> 00:02:32,300
Ia bukan dalam talian dalam pengedaran
kod, kerana ia tidak akan benar-benar berjalan.

59
00:02:32,300 --> 00:02:33,790
Tetapi notis saya baru sahaja
dengan komen berkata,

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

61
00:02:36,130 --> 00:02:38,410
Dan mari kita hanya melihat
apa bahagian-bahagian yang berair berada.

62
00:02:38,410 --> 00:02:40,790
Jadi pada baris tiga,
ingat bahawa ini kini

63
00:02:40,790 --> 00:02:45,960
kita dicadangkan mengisytiharkan nod lalu
masa, salah satu daripada orang-orang objek segi empat tepat.

64
00:02:45,960 --> 00:02:48,790
Ia mempunyai int yang kita akan memanggil N,
tetapi kita boleh memanggilnya apa-apa,

65
00:02:48,790 --> 00:02:51,920
dan kemudian bintang struct nod dipanggil datang.

66
00:02:51,920 --> 00:02:55,520
Dan hanya untuk menjadi jelas, kedua yang
line, pada baris enam, apakah itu?

67
00:02:55,520 --> 00:02:57,930
Apa yang ia lakukan untuk kita?

68
00:02:57,930 --> 00:03:01,044
Kerana ia pasti kelihatan lebih
samar daripada pembolehubah biasa kami.

69
00:03:01,044 --> 00:03:02,740
>> PENONTON: Ia menjadikan ia bergerak lebih daripada satu.

70
00:03:02,740 --> 00:03:04,650
>> SPEAKER 1: Ia menjadikan ia bergerak lebih daripada satu.

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

72
00:03:08,580 --> 00:03:11,582
nod yang bertujuan untuk menjadi
semantik sebelahnya, bukan?

73
00:03:11,582 --> 00:03:13,540
Oleh itu, ia tidak akan
semestinya bergerak apa-apa.

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

75
00:03:15,290 --> 00:03:17,170
akan menjadi alamat
beberapa nod yang lain,

76
00:03:17,170 --> 00:03:20,810
dan itulah sebabnya kita telah berkata struct
nod bintang, bintang yang melambangkan

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

78
00:03:22,370 --> 00:03:26,390
OK, jadi sekarang jika anda menganggap bahawa kita mempunyai
N ini ada pada kita, dan mari kita

79
00:03:26,390 --> 00:03:29,490
menganggap bahawa orang lain mempunyai
dimasukkan sejumlah besar bilangan bulat

80
00:03:29,490 --> 00:03:30,400
ke dalam senarai berpaut.

81
00:03:30,400 --> 00:03:35,640
Dan bahawa senarai berkaitan adalah
ditunjukkan oleh satu ketika

82
00:03:35,640 --> 00:03:39,040
pembolehubah dipanggil senarai itu
diluluskan di sini sebagai parameter,

83
00:03:39,040 --> 00:03:43,120
bagaimana saya boleh pergi mengenai talian
14 melaksanakan carian?

84
00:03:43,120 --> 00:03:45,990
Dalam erti kata lain, jika saya melaksanakan
fungsi yang tujuan dalam hidup

85
00:03:45,990 --> 00:03:48,889
adalah untuk mengambil int dan kemudian
permulaan senarai berpaut,

86
00:03:48,889 --> 00:03:50,430
iaitu penunjuk kepada senarai berkaitan.

87
00:03:50,430 --> 00:03:52,992
Seperti pertama, yang saya fikir David
adalah sukarela kami pada hari Isnin,

88
00:03:52,992 --> 00:03:54,700
dia menghala ke arah
senarai keseluruhan mengaitkan,

89
00:03:54,700 --> 00:03:57,820
ia seolah-olah kita lulus
David dalam sebagai hujah kami di sini.

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

91
00:03:59,990 --> 00:04:04,640
Nah, ternyata bahawa walaupun
petunjuk yang agak baru sekarang kepada kami,

92
00:04:04,640 --> 00:04:07,010
kita boleh melakukan ini agak
terus terang.

93
00:04:07,010 --> 00:04:09,500
>> Saya akan pergi ke depan dan
mengisytiharkan pembolehubah sementara yang

94
00:04:09,500 --> 00:04:12,364
oleh konvensyen hanya akan
untuk dipanggil penunjuk, atau PTR,

95
00:04:12,364 --> 00:04:14,030
tetapi anda boleh memanggil ia apa sahaja yang anda mahu.

96
00:04:14,030 --> 00:04:16,470
Dan saya akan memulakan
untuk permulaan senarai.

97
00:04:16,470 --> 00:04:20,050
Jadi, anda boleh jenis berfikir ini
seperti saya guru hari yang lain,

98
00:04:20,050 --> 00:04:23,580
jenis menunjuk pada seseorang
di kalangan manusia kami sebagai sukarelawan.

99
00:04:23,580 --> 00:04:26,470
Jadi saya pembolehubah sementara itu
hanya menunjuk pada perkara yang sama

100
00:04:26,470 --> 00:04:31,390
yang kami secara kebetulan bernama
sukarelawan Daud juga menunjuk keluar.

101
00:04:31,390 --> 00:04:35,440
Sekarang sementara penunjuk adalah
tidak batal, kerana ingat

102
00:04:35,440 --> 00:04:40,350
null iaitu beberapa nilai sentinel khas
yang demarcates akhir senarai,

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

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

105
00:04:47,190 --> 00:04:51,820
Jika pointer-- dan sekarang saya jenis mahu
untuk melakukan apa yang kita lakukan dengan pelajar

106
00:04:51,820 --> 00:04:57,410
structure-- jika penunjuk dot seterusnya
equals-- sebaliknya, jika penunjuk dot N sama

107
00:04:57,410 --> 00:05:02,290
sama pembolehubah N,
hujah yang sudah diluluskan pada,

108
00:05:02,290 --> 00:05:05,370
maka saya ingin teruskan
dan berkata kembali benar.

109
00:05:05,370 --> 00:05:11,020
Saya mendapati N beberapa bahagian dalam
salah satu daripada nod senarai dikaitkan saya.

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

111
00:05:13,500 --> 00:05:17,260
kerana penunjuk, PTR, adalah
sesungguhnya penunjuk, alamat,

112
00:05:17,260 --> 00:05:20,632
kita benar-benar boleh hebat
menggunakan akhirnya sekeping sintaks

113
00:05:20,632 --> 00:05:22,590
yang jenis jenama
rasa intuitif dan benar-benar

114
00:05:22,590 --> 00:05:27,870
menggunakan panah ke, yang bermaksud pergi dari
bahawa alamat kepada integer sana dalam.

115
00:05:27,870 --> 00:05:30,160
Jadi ia adalah hampir sama dalam
semangat kepada pengendali titik,

116
00:05:30,160 --> 00:05:33,860
tetapi kerana penunjuk tidak penunjuk
dan bukan struct sebenar itu sendiri,

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

118
00:05:35,380 --> 00:05:40,620
>> Jadi, jika nod semasa bahawa Aku,
pembolehubah sementara, sedang menghala ke arah

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

120
00:05:43,060 --> 00:05:45,910
Nah, dengan sukarelawan manusia saya
kalau kita ada di sini pada hari yang lain,

121
00:05:45,910 --> 00:05:49,710
jika manusia pertama saya bukan salah satu I
mahu, dan mungkin manusia yang kedua tidak

122
00:05:49,710 --> 00:05:52,660
yang saya mahu, dan ketiga, saya
perlu menyimpan secara fizikal bergerak.

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

124
00:05:54,690 --> 00:05:57,470
Apabila kita mempunyai array, anda
hanya melakukan seperti saya plus plus.

125
00:05:57,470 --> 00:06:03,660
Tetapi dalam kes ini, ia mencukupi untuk
melakukan penunjuk, mendapat, penunjuk, yang akan datang.

126
00:06:03,660 --> 00:06:07,580
Dengan kata lain, bidang yang akan datang
adalah seperti semua daripada tangan kiri

127
00:06:07,580 --> 00:06:10,880
sukarelawan manusia pada hari Isnin
telah menggunakan untuk menunjukkan pada satu nod lain.

128
00:06:10,880 --> 00:06:12,890
Mereka adalah jiran mereka seterusnya.

129
00:06:12,890 --> 00:06:17,060
>> Jadi, jika saya mahu melangkah melalui senarai ini,
Saya tidak boleh hanya saya plus plus lagi,

130
00:06:17,060 --> 00:06:20,120
Saya bukannya katakan
I, penunjuk, akan

131
00:06:20,120 --> 00:06:24,650
untuk menyamai apa sahaja bidang yang akan datang adalah,
bidang yang akan datang adalah, bidang yang akan datang adalah,

132
00:06:24,650 --> 00:06:28,350
berikut semua orang-orang tangan kiri
kalau kita ada di atas pentas 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 mendapatkan melalui
bahawa lelaran keseluruhan,

135
00:06:32,590 --> 00:06:39,330
dan akhirnya, saya memukul null tidak mempunyai
mendapati N lagi, saya hanya kembali palsu.

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

137
00:06:44,100 --> 00:06:47,840
bermula dengan menunjuk pada
permulaan senarai mungkin.

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

139
00:06:50,970 --> 00:06:52,650
Jika ya, saya kembali benar dan saya dilakukan.

140
00:06:52,650 --> 00:06:56,450
Jika tidak, saya mengemas kini tanganku,
AKA penunjuk, untuk menunjukkan

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

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

143
00:07:00,480 --> 00:07:03,770
Saya hanya berjalan melalui pelbagai ini.

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

145
00:07:06,010 --> 00:07:07,861
Seperti apa yang ini merupakan ramuan untuk?

146
00:07:07,861 --> 00:07:10,360
Nah, ingat bahawa kita diperkenalkan
tanggapan timbunan, yang

147
00:07:10,360 --> 00:07:15,400
merupakan data abstrak menaip setakat yang ia
bukan satu perkara yang C, ia bukan satu perkara yang CS50,

148
00:07:15,400 --> 00:07:19,430
ia adalah satu idea yang abstrak, idea ini
menyusun perkara-perkara di atas satu sama lain

149
00:07:19,430 --> 00:07:21,820
yang boleh dilaksanakan dalam
tandan cara yang berbeza.

150
00:07:21,820 --> 00:07:25,600
Dan satu cara kita dicadangkan adalah dengan
pelbagai, atau dengan senarai berpaut.

151
00:07:25,600 --> 00:07:29,570
Dan ternyata bahawa canonically, yang
timbunan menyokong sekurang-kurangnya dua operasi.

152
00:07:29,570 --> 00:07:32,320
Dan perkataan buzz yang menolak, untuk
menolak sesuatu ke dalam tindanan,

153
00:07:32,320 --> 00:07:34,770
seperti dulang baru dalam
dewan makan, atau pop,

154
00:07:34,770 --> 00:07:39,000
yang bermaksud untuk membuang yang paling atas
dulang dari timbunan di makan

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

156
00:07:41,500 --> 00:07:45,770
Jadi bagaimana kita boleh menentukan struktur
bahawa kita kini memanggil timbunan?

157
00:07:45,770 --> 00:07:50,020
>> Nah, kita mempunyai semua syarat yang
sintaks di tangan kita dalam C. Saya berkata,

158
00:07:50,020 --> 00:07:53,830
memberi saya definisi jenis
struct di dalam timbunan,

159
00:07:53,830 --> 00:07:58,030
Saya akan katakan adalah pelbagai, daripada
sejumlah besar nombor dan kemudian saiz.

160
00:07:58,030 --> 00:08:00,930
Jadi dalam erti kata lain, jika saya mahu
untuk melaksanakan ini dalam kod,

161
00:08:00,930 --> 00:08:03,830
biarlah saya pergi dan hanya jenis
menarik apa ini mengatakan.

162
00:08:03,830 --> 00:08:06,317
Jadi ini mengatakan, memberi saya
struktur itu mendapat pelbagai,

163
00:08:06,317 --> 00:08:09,400
dan saya tidak tahu apa kapasiti adalah,
ia nampaknya beberapa berterusan yang saya telah

164
00:08:09,400 --> 00:08:10,858
ditakrifkan di tempat lain, dan itulah denda.

165
00:08:10,858 --> 00:08:15,260
Tetapi menganggap ia hanya satu,
dua, tiga, empat, lima.

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

167
00:08:16,700 --> 00:08:21,730
Elemen di dalam saya
struktur akan dipanggil nombor.

168
00:08:21,730 --> 00:08:24,020
Dan kemudian saya memerlukan satu
pemboleh ubah lain nampaknya

169
00:08:24,020 --> 00:08:27,814
dipanggil saiz yang pada mulanya saya akan
menetapkan ini dimulakan dengan sifar.

170
00:08:27,814 --> 00:08:29,730
Jika ada apa-apa dalam
timbunan, saiz adalah sifar,

171
00:08:29,730 --> 00:08:31,420
dan ia adalah nilai sampah di nombor.

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

173
00:08:33,450 --> 00:08:36,059
>> Jadi, jika saya mahu untuk menolak
sesuatu ke dalam tindanan,

174
00:08:36,059 --> 00:08:40,780
kira saya memanggil push fungsi, dan
Aku berkata menolak 50, seperti nombor 50,

175
00:08:40,780 --> 00:08:44,090
di mana anda akan mencadangkan
Saya menarik dalam pelbagai ini?

176
00:08:44,090 --> 00:08:47,124
Ada lima jawapan yang berbeza mungkin.

177
00:08:47,124 --> 00:08:48,790
Di manakah anda mahu untuk menolak jumlah 50?

178
00:08:48,790 --> 00:08:51,899
Jika matlamat di sini, sekali lagi, hubungi
push fungsi, lulus dalam pertengkaran

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

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

181
00:08:55,680 --> 00:08:59,052
Lima possible-- 20% peluang
meneka dengan betul.

182
00:08:59,052 --> 00:08:59,896
Ya?

183
00:08:59,896 --> 00:09:00,740
>> PENONTON: Far betul.

184
00:09:00,740 --> 00:09:01,990
>> SPEAKER 1: Far betul.

185
00:09:01,990 --> 00:09:08,359
Kini terdapat peluang 25%
meneka dengan betul.

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

187
00:09:09,650 --> 00:09:12,770
Mengikut konvensyen, saya akan mengatakan dengan array,
kita biasanya akan bermula pada sebelah kiri,

188
00:09:12,770 --> 00:09:14,519
tetapi kita boleh pasti
bermula dari kanan.

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

190
00:09:17,478 --> 00:09:20,060
sama seperti dalam pelbagai biasa di mana
Saya mula akan ke kiri ke kanan.

191
00:09:20,060 --> 00:09:21,780
Tetapi jika anda boleh flip
aritmetik, denda.

192
00:09:21,780 --> 00:09:23,060
Ia hanya tidak konvensional.

193
00:09:23,060 --> 00:09:24,880
OK, saya perlu membuat satu
perubahan lebih walaupun.

194
00:09:24,880 --> 00:09:27,710
Sekarang saya telah menolak sesuatu
ke dalam tindanan, apa yang akan datang?

195
00:09:27,710 --> 00:09:29,400
>> Baiklah, saya perlu kenaikan saiz.

196
00:09:29,400 --> 00:09:32,600
Jadi biarlah saya pergi ke hadapan dan hanya
kini ini, yang sifar.

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

198
00:09:35,950 --> 00:09:39,460
Dan kini kira saya menolak lagi
nombor ke dalam tindanan, seperti 51.

199
00:09:39,460 --> 00:09:42,680
Well, saya perlu membuat satu lagi
perubahan, yang adalah saiz kedua-dua.

200
00:09:42,680 --> 00:09:46,100
Dan kemudian kira saya menolak satu lagi
nombor ke dalam tindanan seperti 61,

201
00:09:46,100 --> 00:09:52,530
sekarang saya perlu mengemas kini saiz satu lagi
masa, dan mendapatkan nilai 3 sebagai saiz.

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

203
00:09:54,690 --> 00:09:57,250
Sekarang pop, oleh konvensyen,
tidak mengambil hujah.

204
00:09:57,250 --> 00:10:00,430
Dengan timbunan, keseluruhannya
titik metafora dulang

205
00:10:00,430 --> 00:10:03,450
adalah bahawa anda tidak mempunyai budi bicara
pergi mendapatkan dulang itu, semua yang boleh anda lakukan

206
00:10:03,450 --> 00:10:06,330
adalah pop satu paling atas dari
timbunan, hanya kerana.

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

208
00:10:08,010 --> 00:10:12,250
>> Jadi dengan logik bahawa jika saya
mengatakan pop dan apa yang keluar?

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 lakukan dalam ingatan?

211
00:10:15,402 --> 00:10:16,610
Apakah kod saya perlu lakukan?

212
00:10:16,610 --> 00:10:20,330
Apa yang anda akan mencadangkan
kita berubah pada skrin?

213
00:10:20,330 --> 00:10:23,410
Apakah yang perlu berubah?

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

215
00:10:24,960 --> 00:10:26,334
Oleh itu, kita menghilangkan 61.

216
00:10:26,334 --> 00:10:27,500
Jadi saya pasti boleh melakukannya.

217
00:10:27,500 --> 00:10:28,640
Dan saya boleh menghilangkan 61.

218
00:10:28,640 --> 00:10:30,980
Dan kemudian apa yang lain
perubahan yang perlu berlaku?

219
00:10:30,980 --> 00:10:33,160
Saiz mungkin mempunyai untuk kembali ke dua.

220
00:10:33,160 --> 00:10:34,210
Dan sebagainya itulah denda.

221
00:10:34,210 --> 00:10:36,690
Tetapi tunggu satu minit, saiz
masa lalu adalah tiga.

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

223
00:10:38,240 --> 00:10:41,810
Bagaimana kita tahu bahawa kita
mahukan untuk menghilangkan 61?

224
00:10:41,810 --> 00:10:42,760
Kerana kita pop.

225
00:10:42,760 --> 00:10:46,450
Oleh itu, saya mempunyai saiz hartanah ini kedua.

226
00:10:46,450 --> 00:10:48,470
>> Tunggu satu minit, Saya
memikirkan kembali dua minggu

227
00:10:48,470 --> 00:10:51,660
apabila kita mula bercakap tentang
tatasusunan, di mana ini merupakan lokasi sifar,

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

229
00:10:55,920 --> 00:10:58,460
ia kelihatan seperti
hubungan antara saiz

230
00:10:58,460 --> 00:11:02,780
dan elemen yang saya mahu mengeluarkan
dari pelbagai nampaknya hanya menjadi apa?

231
00:11:02,780 --> 00:11:05,120
Saiz tolak satu.

232
00:11:05,120 --> 00:11:07,786
Dan sebagainya itu bagaimana sebagai manusia
kita tahu 61 yang terdahulu.

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

234
00:11:09,160 --> 00:11:11,701
Apabila kod anda, di mana anda mungkin
mahu lakukan saiz tolak satu,

235
00:11:11,701 --> 00:11:14,950
jadi tiga tolak satu adalah dua, dan yang
bermakna kita mahu menghapuskan 61.

236
00:11:14,950 --> 00:11:18,000
Dan kemudian kita memang boleh mengemas kini
saiz jadi saiz yang kini

237
00:11:18,000 --> 00:11:20,300
pergi daripada tiga kepada dua.

238
00:11:20,300 --> 00:11:24,520
Dan hanya untuk bengah, saya akan
untuk mencadangkan bahawa saya sudah selesai, bukan?

239
00:11:24,520 --> 00:11:27,660
Anda dicadangkan intuitif
betul saya perlu menghilangkan 61.

240
00:11:27,660 --> 00:11:30,700
Tetapi belum saya jenis
semacam mendapat menghilangkan 61?

241
00:11:30,700 --> 00:11:33,790
Saya terlupa berkesan
bahawa ia sebenarnya di sana.

242
00:11:33,790 --> 00:11:37,680
Dan berfikir kembali ke PSET4, jika anda telah membaca
artikel mengenai forensik, PDF

243
00:11:37,680 --> 00:11:40,780
bahawa kita mempunyai anda semua membaca, atau anda
akan membaca minggu ini untuk PSET4.

244
00:11:40,780 --> 00:11:44,300
Ingat bahawa ini adalah benar-benar germane untuk
idea keseluruhan forensik komputer.

245
00:11:44,300 --> 00:11:47,820
Apa komputer yang secara umumnya tidak adalah
ia hanya lupa mana sesuatu itu,

246
00:11:47,820 --> 00:11:51,300
tetapi ia tidak masuk dan seperti
cuba menggaru ia keluar atau mengatasi

247
00:11:51,300 --> 00:11:54,560
bit-bit dengan sifar dan satu
atau beberapa corak rawak lain

248
00:11:54,560 --> 00:11:56,690
melainkan anda sendiri berbuat demikian sengaja.

249
00:11:56,690 --> 00:11:58,930
Jadi gerak hati anda adalah
Baiklah, mari kita buang 61.

250
00:11:58,930 --> 00:12:00,650
Tetapi dalam realiti, kita tidak perlu bersusah payah.

251
00:12:00,650 --> 00:12:04,040
Kita hanya perlu lupa bahawa
ianya ada dengan menukar saiz kami.

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

253
00:12:05,662 --> 00:12:07,620
Jika saya terus menolak perkara-perkara
ke dalam tindanan, apa yang

254
00:12:07,620 --> 00:12:11,167
jelas akan berlaku
hanya dalam masa beberapa ketika?

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 sejenis diskru.

258
00:12:14,680 --> 00:12:19,000
Pelaksanaan ini tidak membiarkan
kami mengubah saiz array, kerana menggunakan

259
00:12:19,000 --> 00:12:21,240
sintaks ini, jika anda
berfikir kembali ke minggu dua,

260
00:12:21,240 --> 00:12:23,520
sebaik sahaja anda telah diisytiharkan
saiz pelbagai,

261
00:12:23,520 --> 00:12:26,780
kami tidak melihat mekanisme lagi di mana
anda boleh menukar saiz array.

262
00:12:26,780 --> 00:12:29,020
Dan sesungguhnya C tidak mempunyai ciri-ciri itu.

263
00:12:29,020 --> 00:12:32,524
Jika anda mengatakan memberi saya lima
Nths, merujuk kepada mereka nombor,

264
00:12:32,524 --> 00:12:33,940
itu sahaja anda akan mendapatkannya.

265
00:12:33,940 --> 00:12:38,790
Oleh itu, kita lakukan sekarang pada hari Isnin, mempunyai
keupayaan untuk menyatakan penyelesaian

266
00:12:38,790 --> 00:12:42,480
walaupun, kita hanya perlu untuk tweak
takrif timbunan kami

267
00:12:42,480 --> 00:12:46,840
untuk tidak beberapa pelbagai berkod keras,
tetapi 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 perlu untuk menjadi selesa dengan
hakikat bahawa apabila program saya berjalan,

270
00:12:51,690 --> 00:12:53,730
Saya mungkin akan
perlu bertanya kepada manusia,

271
00:12:53,730 --> 00:12:55,110
berapa banyak nombor yang anda mahu simpan?

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

273
00:12:56,776 --> 00:12:59,140
Tetapi apabila saya tahu bahawa
nombor, maka saya boleh hanya

274
00:12:59,140 --> 00:13:02,470
menggunakan apa yang berfungsi untuk memberi
saya sebahagian memori?

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

276
00:13:03,580 --> 00:13:06,710
Dan saya boleh mengatakan apa-apa bilangan
bait Saya hendak kembali untuk Nths ini.

277
00:13:06,710 --> 00:13:10,910
Dan apa yang saya perlu simpan di nombor
berubah-ubah di sini di dalam struct ini

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

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

280
00:13:18,440 --> 00:13:21,300
Ya, penunjuk kepada orang pertama
bait yang sebahagian memori,

281
00:13:21,300 --> 00:13:24,940
atau lebih khusus, alamat
daripada orang yang awal pertama bait.

282
00:13:24,940 --> 00:13:27,300
Tidak kira sama ada ia adalah salah satu
bait atau satu bilion bait,

283
00:13:27,300 --> 00:13:28,890
Saya hanya perlu untuk mengambil berat tentang yang pertama.

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

285
00:13:31,530 --> 00:13:34,170
adalah bahawa sebahagian memori saya
mendapatkan, ia akan menjadi yang berhampiran.

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

287
00:13:35,378 --> 00:13:38,576
Jadi, jika saya telah meminta 50
bait atau 1,000 bait,

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

289
00:13:40,450 --> 00:13:44,500
Dan selagi saya masih ingat berapa besar, berapa
banyak saya meminta, semua yang saya perlu tahu

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

291
00:13:46,230 --> 00:13:48,660
>> Jadi sekarang kita mempunyai keupayaan dalam kod.

292
00:13:48,660 --> 00:13:51,280
Walaupun, ia akan membawa kita
lebih banyak masa untuk menulis ini ke atas,

293
00:13:51,280 --> 00:13:55,900
kita kini boleh mengagihkan semula memori dengan
hanya menyimpan alamat yang berbeza di sana

294
00:13:55,900 --> 00:13:59,060
jika kita mahu yang lebih besar atau
sebahagian yang lebih kecil daripada ingatan.

295
00:13:59,060 --> 00:14:00,170
Jadi di sini kepada keseimbangan.

296
00:14:00,170 --> 00:14:01,360
Sekarang kita mendapat dinamik.

297
00:14:01,360 --> 00:14:03,350
Kami masih mempunyai
contiguousness saya mendakwa.

298
00:14:03,350 --> 00:14:05,881
Kerana malloc akan memberikan kita
sebahagian berdampingan memori.

299
00:14:05,881 --> 00:14:08,630
Tetapi ini akan menjadi sakit di
leher untuk kita, pengaturcara,

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

301
00:14:09,770 --> 00:14:10,730
Ia adalah kerja hanya lebih.

302
00:14:10,730 --> 00:14:13,930
Kami memerlukan kod yang serupa dengan apa yang saya
terhantuk keluar hanya sebentar tadi.

303
00:14:13,930 --> 00:14:16,120
Sangat boleh dilakukan, tetapi ia menambah kerumitan.

304
00:14:16,120 --> 00:14:19,520
Dan jadi masa pemaju, programmer
masa lagi sumber lain

305
00:14:19,520 --> 00:14:22,520
bahawa kita mungkin perlu menghabiskan
sedikit masa untuk mendapatkan ciri-ciri baru.

306
00:14:22,520 --> 00:14:24,020
Kemudian sudah tentu ada barisan.

307
00:14:24,020 --> 00:14:26,227
Kami tidak akan pergi ke ini
satu secara terperinci banyak.

308
00:14:26,227 --> 00:14:27,560
Tetapi ia adalah hampir sama dalam semangat.

309
00:14:27,560 --> 00:14:31,220
Saya boleh melaksanakan barisan, dan
operasi yang sepadan dengannya,

310
00:14:31,220 --> 00:14:35,660
enqueue atau dequeue, seperti menambah atau mengeluarkan,
ia hanya cara yang pelamun untuk mengatakan ini,

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

312
00:14:38,100 --> 00:14:41,170
Saya hanya boleh memberikan diri saya struct
itu lagi mempunyai pelbagai beberapa kanak,

313
00:14:41,170 --> 00:14:44,000
itu lagi mempunyai saiz yang,
tetapi mengapa saya kini perlu

314
00:14:44,000 --> 00:14:46,940
untuk mengesan bahagian depan barisan?

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

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

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

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

319
00:15:00,940 --> 00:15:03,430
Ini akan menjadi
dipanggil nombor lagi.

320
00:15:03,430 --> 00:15:06,940
Dan ini akan dipanggil saiz.

321
00:15:06,940 --> 00:15:10,056
>> Mengapa ia tidak mencukupi
untuk mempunyai hanya saiz?

322
00:15:10,056 --> 00:15:11,680
Nah, mari kita tolak nombor-nombor sama pada.

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

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 itulah enqueue.

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

327
00:15:23,176 --> 00:15:25,050
Dan itu kelihatan sama
untuk timbunan setakat 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 mengemaskinikan saiz ini, jadi saya pergi
dari sifar kepada satu kepada dua hingga tiga sekarang.

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

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

332
00:15:36,890 --> 00:15:41,950
Siapa yang patut terkeluar senarai ini pertama
jika ia barisan di Kedai Apple?

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

334
00:15:42,780 --> 00:15:44,700
Jadi ia adalah jenis sukar kali ini.

335
00:15:44,700 --> 00:15:47,880
Sedangkan masa lalu, ia adalah super
mudah untuk hanya melakukan saiz tolak satu,

336
00:15:47,880 --> 00:15:51,440
Saya sampai ke akhir array saya dengan berkesan
mana nombor-nombor itu, ia membuang 61.

337
00:15:51,440 --> 00:15:52,920
Tetapi saya tidak mahu mengeluarkan 61.

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

339
00:15:55,030 --> 00:15:56,790
untuk beratur untuk
iPhone baru atau barang kecil.

340
00:15:56,790 --> 00:16:01,200
Dan sebagainya untuk menghilangkan 50, saya
tidak boleh melakukan ini, bukan?

341
00:16:01,200 --> 00:16:02,547
Saya boleh batalkan 50.

342
00:16:02,547 --> 00:16:04,380
Tetapi kita hanya berkata kita
tidak perlu menjadi begitu dubur

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

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

345
00:16:08,090 --> 00:16:12,330
>> Tetapi jika saya menukar saiz saya sekarang untuk
dua, maklumat yang mencukupi ini

346
00:16:12,330 --> 00:16:15,711
untuk mengetahui apa yang sedang berlaku di dalam giliran saya?

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

348
00:16:16,680 --> 00:16:19,830
Seperti saiz saya ialah dua, tetapi
di manakah barisan memulakan,

349
00:16:19,830 --> 00:16:22,980
terutamanya jika saya masih mempunyai
nombor-nombor yang sama dalam ingatan.

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

351
00:16:24,260 --> 00:16:27,090
Jadi saya perlu ingat
sekarang di mana hadapan adalah.

352
00:16:27,090 --> 00:16:29,630
Dan supaya saya mencadangkan sehingga
di sana, kita akan telah hanya dipanggil

353
00:16:29,630 --> 00:16:33,729
Depan ke-n, yang awal
nilai sepatutnya apa?

354
00:16:33,729 --> 00:16:35,270
Zero, hanya permulaan senarai.

355
00:16:35,270 --> 00:16:40,876
Tetapi sekarang sebagai tambahan kepada decrementing
saiz, kita hanya kenaikan hadapan.

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

357
00:16:42,000 --> 00:16:43,030
Jadi apabila saya terus pergi.

358
00:16:43,030 --> 00:16:47,520
Katakan ini ialah bilangan
seperti 121, 124, dan kemudian, celaka,

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

360
00:16:48,610 --> 00:16:50,390
Tetapi tunggu satu minit, saya tidak.

361
00:16:50,390 --> 00:16:55,630
Jadi pada ketika ini dalam cerita,
menganggap bahawa saiz adalah satu, dua,

362
00:16:55,630 --> 00:17:00,370
tiga, empat, sehingga mengira bahawa
saiz adalah empat, depan adalah satu,

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

364
00:17:01,621 --> 00:17:04,329
Saya mahu meletakkan nombor lain di sini,
tetapi, celaka, saya keluar dari ruang.

365
00:17:04,329 --> 00:17:06,710
Namun, saya tidak benar-benar, betul-betul?

366
00:17:06,710 --> 00:17:11,192
Di mana saya boleh meletakkan beberapa
nilai tambahan, seperti 171?

367
00:17:11,192 --> 00:17:13,400
Ya, saya boleh hanya jenis
kembali ke sana, bukan?

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

369
00:17:18,161 --> 00:17:20,410
Dan jika anda tertanya-tanya mengapa
nombor kami mendapat begitu rawak,

370
00:17:20,410 --> 00:17:24,150
ini biasanya diambil komputer
kursus sains di Harvard selepas CS50.

371
00:17:24,150 --> 00:17:27,510
Tetapi itu adalah pengoptimuman yang baik,
kerana sekarang saya tidak membazirkan ruang.

372
00:17:27,510 --> 00:17:30,750
Saya masih perlu ingat
betapa besar perkara ini adalah jumlah.

373
00:17:30,750 --> 00:17:31,500
Ia adalah lima jumlah.

374
00:17:31,500 --> 00:17:33,375
Kerana saya tidak mahu
mula menulis ganti 51.

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

376
00:17:36,260 --> 00:17:39,140
Tetapi anda boleh lihat bagaimana sekarang
dalam kod anda, anda mungkin

377
00:17:39,140 --> 00:17:41,910
perlu menulis sedikit lebih
kerumitan untuk membuat yang berlaku.

378
00:17:41,910 --> 00:17:44,510
Dan sebenarnya, pengendali apa
dalam C mungkin membolehkan

379
00:17:44,510 --> 00:17:48,110
anda ajaib cookies bundar itu?

380
00:17:48,110 --> 00:17:50,160
Yeah pengendali modulo itu,
tanda peratus.

381
00:17:50,160 --> 00:17:53,160
Jadi apa jenis sejuk tentang barisan,
walaupun kita menyimpan lukisan tatasusunan

382
00:17:53,160 --> 00:17:56,520
kerana ini garis lurus seperti, jika anda
jenis berfikir tentang perkara ini melengkung

383
00:17:56,520 --> 00:18:00,341
sekitar sebagai satu bulatan, maka hanya
intuitif ia jenis kerja-kerja mental

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

385
00:18:01,590 --> 00:18:05,190
Anda masih perlu melaksanakan
bahawa model mental dalam kod.

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

387
00:18:07,550 --> 00:18:12,430
tetapi kita masih kehilangan size-- sebaliknya,
keupayaan untuk mengubah saiz, melainkan jika kita melakukan ini.

388
00:18:12,430 --> 00:18:15,310
>> Kita perlu menghilangkan array, kita
menggantikannya dengan penunjuk tunggal,

389
00:18:15,310 --> 00:18:20,010
dan kemudian di suatu tempat di kod saya saya telah mendapat
yang memanggil apa yang berfungsi untuk benar-benar membuat

390
00:18:20,010 --> 00:18:23,720
array dipanggil nombor?

391
00:18:23,720 --> 00:18:26,190
Malloc, atau sama
fungsi, betul-betul.

392
00:18:26,190 --> 00:18:30,481
Sebarang pertanyaan mengenai susunan atau beratur.

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
Soalan yang baik.

396
00:18:34,240 --> 00:18:35,830
Apa modulo anda akan menggunakan di sini.

397
00:18:35,830 --> 00:18:38,520
Jadi secara umumnya, apabila menggunakan
mod, anda akan melakukannya

398
00:18:38,520 --> 00:18:40,620
dengan saiz
struktur data keseluruhan.

399
00:18:40,620 --> 00:18:44,120
Jadi sesuatu seperti lima atau kapasiti, jika
ia berterusan, yang mungkin terlibat.

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

401
00:18:47,100 --> 00:18:51,380
kerana 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 mahu melibatkan

403
00:18:54,160 --> 00:18:57,220
saiz benda itu, atau
berubah-depan juga.

404
00:18:57,220 --> 00:19:00,140
Jadi ia hanya ini yang agak
ungkapan aritmetik mudah,

405
00:19:00,140 --> 00:19:02,000
tetapi modulo akan menjadi bahan utama.

406
00:19:02,000 --> 00:19:03,330
>> Filem begitu pendek jika anda akan.

407
00:19:03,330 --> 00:19:05,780
Animasi bahawa beberapa
Penduduk di universiti lain

408
00:19:05,780 --> 00:19:08,060
meletakkan bersama-sama yang kita ada
disesuaikan untuk perbincangan ini.

409
00:19:08,060 --> 00:19:12,630
Ia melibatkan Jack pembelajaran
fakta tentang barisan dan statistik.

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

411
00:19:19,010 --> 00:19:21,890
>> FILEM: Pada suatu masa dahulu,
ada seorang lelaki bernama Jack.

412
00:19:21,890 --> 00:19:25,330
Apabila ia datang untuk membuat kawan-kawan,
Jack tidak mempunyai cukup pengetahuan.

413
00:19:25,330 --> 00:19:28,220
Jadi Jack pergi ke bercakap dengan
Lelaki yang paling popular dia tahu.

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

415
00:19:30,920 --> 00:19:33,400
Lou melihat bahawa kawannya
benar-benar bermasalah.

416
00:19:33,400 --> 00:19:36,050
Well, dia mula, hanya
melihat bagaimana anda berpakaian.

417
00:19:36,050 --> 00:19:38,680
Apakah kamu tidak mempunyai apa-apa pakaian
dengan wajah yang berbeza?

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

419
00:19:39,660 --> 00:19:40,840
Saya pasti lakukan.

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

421
00:19:43,320 --> 00:19:44,550
Lalu mereka pergi kepada Jack.

422
00:19:44,550 --> 00:19:47,520
Dan Jack menunjukkan Lou kotak
di mana beliau melindungi segala baju beliau,

423
00:19:47,520 --> 00:19:49,260
dan seluarnya, dan khuf.

424
00:19:49,260 --> 00:19:52,290
Lou berkata, saya melihat anda mempunyai
semua pakaian anda dalam longgokan.

425
00:19:52,290 --> 00:19:54,870
Mengapa tidak anda memakai beberapa
lain sekali dalam seketika?

426
00:19:54,870 --> 00:19:58,020
>> Jack berkata, dengan baik, apabila saya
mengeluarkan pakaian dan sarung kaki,

427
00:19:58,020 --> 00:20:00,780
Saya mencuci mereka dan meletakkan
mereka jauh di dalam kotak.

428
00:20:00,780 --> 00:20:03,210
Kemudian datang seterusnya
pagi, dan ke atas hop.

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

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

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

432
00:20:12,080 --> 00:20:14,420
Apabila dia sampai untuk
sesuatu untuk membaca atau untuk dipakai,

433
00:20:14,420 --> 00:20:17,100
dia akan memilih buku atas atau seluar dalam.

434
00:20:17,100 --> 00:20:19,500
Kemudian apabila dia telah dilakukan, dia
akan meletakkan ia segera kembali.

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

436
00:20:21,970 --> 00:20:24,460
Saya tahu penyelesaian,
kata seorang Loud berjaya.

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

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

439
00:20:29,870 --> 00:20:32,710
Dan apabila dia telah dikosongkan
kotak, dia hanya melepaskannya.

440
00:20:32,710 --> 00:20:36,500
>> Kemudian dia berkata, kini Jack, pada akhir
hari, meletakkan pakaian anda di sebelah kiri

441
00:20:36,500 --> 00:20:37,990
apabila anda meletakkan mereka pergi.

442
00:20:37,990 --> 00:20:41,300
Maka esok pagi apabila anda
melihat cahaya matahari, dapatkan 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
Adakah anda tidak melihat? kata Lou.

445
00:20:44,880 --> 00:20:46,370
Ia akan menjadi begitu baik.

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

447
00:20:49,770 --> 00:20:52,670
Dan dengan segala-galanya dalam barisan
dalam almari dan rak-Nya,

448
00:20:52,670 --> 00:20:55,160
Jack mula berasa
pasti dirinya.

449
00:20:55,160 --> 00:20:59,720
Semua terima kasih kepada Lou dan
barisan yang indah beliau.

450
00:20:59,720 --> 00:21:01,220
SPEAKER 1: Baiklah, ia adalah comel.

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

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

453
00:21:10,080 --> 00:21:12,370
Yang kita ada petunjuk,
yang kita ada malloc,

454
00:21:12,370 --> 00:21:15,680
yang kita ada keupayaan untuk mewujudkan
ketulan memori untuk diri kita sendiri

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

456
00:21:16,344 --> 00:21:18,510
Jadi ini adalah satu kita gambar
celah hanya pada hari yang lain.

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

458
00:21:21,180 --> 00:21:24,180
mempunyai telah berlaku di bawah
bonet selama beberapa minggu sekarang.

459
00:21:24,180 --> 00:21:27,050
Dan hal ini mewakili, hanya
segi empat tepat yang kita telah disediakan,

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, mempunyai gigabit memori atau RAM

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

463
00:21:33,050 --> 00:21:34,450
Ia tidak benar-benar perkara itu.

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 membolehkan program anda
untuk berfikir bahawa ia mempunyai akses

466
00:21:41,120 --> 00:21:42,982
kepada keseluruhan
memori komputer anda,

467
00:21:42,982 --> 00:21:45,440
walaupun anda mungkin berjalan
pelbagai program pada satu masa.

468
00:21:45,440 --> 00:21:46,990
Jadi pada hakikatnya, itu tidak benar-benar berkesan.

469
00:21:46,990 --> 00:21:49,448
Tetapi ia adalah jenis ilusi
diberikan kepada semua program anda.

470
00:21:49,448 --> 00:21:53,110
Jadi, jika anda mempunyai dua gig RAM, ini
adalah bagaimana komputer mungkin berfikir.

471
00:21:53,110 --> 00:21:57,110
>> Sekarang kebetulan, salah satu daripada
perkara, salah satu daripada segmen memori,

472
00:21:57,110 --> 00:21:58,350
dipanggil timbunan.

473
00:21:58,350 --> 00:22:01,680
Dan sesungguhnya bila-bila masa
setakat ini dalam menulis kod

474
00:22:01,680 --> 00:22:05,900
bahawa anda telah dipanggil
fungsi, sebagai contoh utama.

475
00:22:05,900 --> 00:22:08,410
Ingat bahawa bila-bila masa saya telah
memori komputer disediakan ini,

476
00:22:08,410 --> 00:22:10,640
Saya sentiasa menarik semacam
separuh daripada segi empat tepat di sini

477
00:22:10,640 --> 00:22:12,520
dan tidak mengganggu bercakap
tentang apa yang ada di atas.

478
00:22:12,520 --> 00:22:15,980
Kerana apabila utama dipanggil, saya menuntut
yang anda dapat sekerat 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 dipanggil fungsi
seperti pertukaran, baik pertukaran pergi sini.

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

482
00:22:23,720 --> 00:22:26,277
Pada sesuatu yang dipanggil timbunan
dalam memori komputer anda.

483
00:22:26,277 --> 00:22:28,360
Sesudah lewat hari,
ini hanya menangani.

484
00:22:28,360 --> 00:22:30,680
Ia seperti bait sifar,
bait satu, bait 2 bilion.

485
00:22:30,680 --> 00:22:33,130
Tetapi jika anda berfikir tentang hal itu
sebagai objek segi empat tepat ini,

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

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

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

489
00:22:41,700 --> 00:22:44,490
>> Dan ingat kini bahawa ini adalah penting.

490
00:22:44,490 --> 00:22:46,400
Kerana jika kita mempunyai
sesuatu seperti pertukaran

491
00:22:46,400 --> 00:22:51,610
dan dua pembolehubah tempatan seperti A dan B dan
kita menukar nilai-nilai dari satu dan dua

492
00:22:51,610 --> 00:22:55,130
dua dan satu, ingat
bahawa apabila pertukaran kembali,

493
00:22:55,130 --> 00:22:58,330
ia seolah-olah keping ini
memori hanya hilang.

494
00:22:58,330 --> 00:23:00,080
Pada hakikatnya, ia masih
terdapat forensik.

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

496
00:23:01,940 --> 00:23:05,410
Tetapi dari segi konsep, ia seolah-
walaupun ia benar-benar hilang.

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

498
00:23:10,910 --> 00:23:14,890
melainkan jika ia sebenarnya diluluskan pada mereka
hujah-hujah oleh penunjuk atau rujukan.

499
00:23:14,890 --> 00:23:17,790
Kini, penyelesaian asas
itu masalah dengan pertukaran

500
00:23:17,790 --> 00:23:19,970
berlalu perkara dalam dengan alamat.

501
00:23:19,970 --> 00:23:23,250
Tetapi ternyata, juga, apa yang
telah berlaku di atas bahagian itu

502
00:23:23,250 --> 00:23:26,330
segi empat tepat selama ini adalah
belum ada lebih banyak memori di sana.

503
00:23:26,330 --> 00:23:28,790
Dan apabila anda secara dinamik
memperuntukkan ingatan,

504
00:23:28,790 --> 00:23:32,020
sama ada di dalam GetString, yang
yang kita telah lakukan untuk anda dalam CS50

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

506
00:23:34,710 --> 00:23:37,950
sistem yang beroperasi untuk sebahagian daripada
ingatan, ia tidak datang dari timbunan.

507
00:23:37,950 --> 00:23:40,960
Ia datang dari tempat lain
dalam memori komputer anda

508
00:23:40,960 --> 00:23:42,220
yang dinamakan timbunan itu.

509
00:23:42,220 --> 00:23:43,430
Dan itu bukan apa-apa yang berbeza.

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

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

512
00:23:45,160 --> 00:23:49,080
Ia hanya RAM itu terpulang
ada dan bukannya di bawah ini.

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

514
00:23:50,750 --> 00:23:53,650
Nah, jika komputer anda mempunyai
jumlah yang terhad memori

515
00:23:53,650 --> 00:23:57,450
dan timbunan membesar, jadi
untuk bercakap, dan timbunan itu, menurut

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

517
00:23:59,349 --> 00:24:01,140
Dalam erti kata lain, setiap
kali anda memanggil malloc,

518
00:24:01,140 --> 00:24:03,430
anda diberi bahagian yang
memori dari atas,

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

520
00:24:06,630 --> 00:24:10,100
timbunan itu, ia adalah penggunaan,
adalah jenis yang semakin meningkat,

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

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

523
00:24:13,382 --> 00:24:14,840
Jadi adakah ini kelihatan seperti idea yang baik?

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

525
00:24:18,420 --> 00:24:22,140
Maksud saya, di mana ia tidak benar-benar jelas
apa lagi yang boleh anda lakukan jika anda hanya

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

527
00:24:23,910 --> 00:24:25,200
Tetapi ini sudah tentu tidak baik.

528
00:24:25,200 --> 00:24:27,920
Kedua-dua anak-anak panah pada
crash kursus untuk satu sama lain.

529
00:24:27,920 --> 00:24:31,930
>> Dan ternyata bahawa lelaki yang tidak baik, orang yang
adalah sangat baik dengan program,

530
00:24:31,930 --> 00:24:36,140
dan cuba untuk menggodam komputer,
boleh mengeksploitasi realiti ini.

531
00:24:36,140 --> 00:24:38,290
Malah, mari kita mempertimbangkan
coretan sedikit.

532
00:24:38,290 --> 00:24:41,350
Jadi ini adalah satu contoh, anda boleh membaca
mengenai dengan lebih terperinci di Wikipedia.

533
00:24:41,350 --> 00:24:43,100
Kami akan menunjukkan anda di
artikel jika ingin tahu.

534
00:24:43,100 --> 00:24:45,650
Tetapi ada serangan umumnya
dikenali sebagai buffer overflow yang

535
00:24:45,650 --> 00:24:49,570
telah wujud selagi manusia
mempunyai keupayaan untuk memanipulasi

536
00:24:49,570 --> 00:24:53,120
memori komputer, terutamanya di C.
Jadi ini adalah satu program yang sangat sewenang-wenangnya,

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

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

539
00:24:57,650 --> 00:24:59,830
Jadi ia adalah satu program yang mengambil
hujah baris arahan.

540
00:24:59,830 --> 00:25:03,620
Dan semua utama tidak nampaknya adalah panggilan
fungsi, memanggilnya F untuk kesederhanaan.

541
00:25:03,620 --> 00:25:04,610
Dan ia berlalu dalam apa?

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

543
00:25:05,490 --> 00:25:09,320
Jadi ia mengalir ke dalam F apa sahaja
perkataan ini adalah bahawa pengguna ditaip

544
00:25:09,320 --> 00:25:11,500
di prompt selepas
nama program ini 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 F?

547
00:25:16,680 --> 00:25:19,760
F mengambil masa dalam rentetan
sebagai hujah bicara mutlaknya,

548
00:25:19,760 --> 00:25:22,100
AKA bintang char, sama
perkara, sebagai rentetan.

549
00:25:22,100 --> 00:25:24,920
Dan ia dipanggil sewenang-wenangnya
bar dalam contoh ini.

550
00:25:24,920 --> 00:25:27,710
Dan kemudian char c 12,
sahaja dari segi orang biasa itu,

551
00:25:27,710 --> 00:25:31,750
apa yang char c kurungan 12 lakukan untuk kita?

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

553
00:25:33,440 --> 00:25:36,490
Memperuntukkan ingatan, khusus
12 bait untuk 12 aksara.

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

555
00:25:36,990 --> 00:25:40,000
Dan kemudian barisan terakhir, kacau dan
menyalin, anda mungkin tidak dapat dilihat.

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

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

558
00:25:48,160 --> 00:25:51,190
tetapi hanya sehingga
sebilangan bait.

559
00:25:51,190 --> 00:25:53,860
Jadi pendapat ketiga tadi berkata,
berapa banyak bait anda perlu menyalin?

560
00:25:53,860 --> 00:25:56,720
Panjang bar,
apa pengguna ditaip.

561
00:25:56,720 --> 00:25:59,320
Dan kandungan
menggalang, tali itu, adalah

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

563
00:26:02,330 --> 00:26:04,060
>> Jadi ini seolah-olah jenis bodoh, lalu menjadilah ia.

564
00:26:04,060 --> 00:26:06,300
Ia adalah satu contoh tersusun,
tetapi ia adalah wakil

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

566
00:26:10,100 --> 00:26:15,050
Semua adalah baik dan baik jika pengguna
jenis dalam satu perkataan itu 11 aksara

567
00:26:15,050 --> 00:26:18,040
atau kurang, ditambah backslash sifar.

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

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

570
00:26:25,090 --> 00:26:29,360
Kesalahan berpotensi seg. Ia akan
membuta tuli menyalin segala-galanya dalam bar sehingga

571
00:26:29,360 --> 00:26:31,750
panjang, yang merupakan
benar-benar segala-galanya dalam bar,

572
00:26:31,750 --> 00:26:36,307
ke alamat menunjuk pada C. Tetapi C
hanya preemptively diberikan sebagai 12 bait.

573
00:26:36,307 --> 00:26:37,640
Tetapi tidak ada daftar tambahan.

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

575
00:26:38,700 --> 00:26:40,580
Tidak ada ralat memeriksa di sini.

576
00:26:40,580 --> 00:26:43,270
>> Dan supaya apa yang program ini adalah
akan lakukan ialah hanya membuta tuli

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

578
00:26:45,750 --> 00:26:47,880
Dan jadi jika kita menarik ini
sebagai gambar, di sini adalah

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

580
00:26:49,860 --> 00:26:53,470
Jadi notis di bahagian bawah, kita
mempunyai bar pembolehubah tempatan.

581
00:26:53,470 --> 00:26:57,330
Supaya penunjuk yang akan store--
sebaliknya hujah tempatan itu

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

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

584
00:27:00,380 --> 00:27:02,505
kerana setiap kali anda bertanya
untuk ingatan pada timbunan,

585
00:27:02,505 --> 00:27:04,310
ia pergi sedikit
di atasnya bergambar,

586
00:27:04,310 --> 00:27:06,270
notis bahawa kita telah mendapat 12 bait sana.

587
00:27:06,270 --> 00:27:10,690
Yang kiri atas ialah C kurungan sifar dan
satu kanan bawah adalah C kurungan 11.

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

589
00:27:12,870 --> 00:27:18,300
Jadi hanya intuitif, jika bar mempunyai lebih
daripada 12 aksara dalam jumlah, termasuk

590
00:27:18,300 --> 00:27:25,790
garis miring sifar, di mana adalah
12 atau kurungan C 12 akan pergi?

591
00:27:25,790 --> 00:27:28,440
Atau sebaliknya mana-12
watak atau watak-13,

592
00:27:28,440 --> 00:27:30,900
watak seratus akan
berakhir di dalam gambar?

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

594
00:27:33,400 --> 00:27:36,300
>> Betul, kerana walaupun
timbunan itu sendiri tumbuh ke atas,

595
00:27:36,300 --> 00:27:39,590
sebaik sahaja anda telah meletakkan barangan di
ia, atas sebab-sebab reka bentuk,

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

597
00:27:41,294 --> 00:27:44,460
Jadi, jika anda mempunyai lebih daripada 12 bait,
anda akan mula menulis ganti bar.

598
00:27:44,460 --> 00:27:47,280
Sekarang ini pepijat, tetapi ia
tidak benar-benar masalah besar.

599
00:27:47,280 --> 00:27:51,130
Tetapi ia adalah masalah besar, kerana ada
lebih banyak bahan yang berlaku di dalam ingatan.

600
00:27:51,130 --> 00:27:53,074
Jadi di sini adalah bagaimana kita mungkin
meletakkan hello, menjadi jelas.

601
00:27:53,074 --> 00:27:54,490
Jika saya ditaip hello di prompt.

602
00:27:54,490 --> 00:27:59,330
Garis miring sifar H-E-L-L-O, berakhir dalam
mereka 12 bait, dan kami super selamat.

603
00:27:59,330 --> 00:28:00,330
Semuanya berjalan dengan lancar.

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

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

606
00:28:05,860 --> 00:28:08,405
Tetapi lebih teruk lagi, ia ternyata
sepanjang masa ini,

607
00:28:08,405 --> 00:28:11,530
walaupun kita tidak pernah bercakap tentang
ia, timbunan itu digunakan untuk perkara lain.

608
00:28:11,530 --> 00:28:13,560
Ia bukan hanya pembolehubah tempatan.

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

610
00:28:15,100 --> 00:28:17,810
Dan ia semacam rahsia
menggunakan tindanan juga

611
00:28:17,810 --> 00:28:21,260
ingat apabila
fungsi dipanggil, apa

612
00:28:21,260 --> 00:28:26,040
alamat adalah fungsi sebelumnya,
jadi ia boleh melompat ke belakang dengan fungsi itu.

613
00:28:26,040 --> 00:28:29,980
Oleh itu, apabila panggilan utama swap, antara
perkara-perkara yang ditolak ke dalam tindanan

614
00:28:29,980 --> 00:28:34,380
tidak hanya swap pembolehubah tempatan,
atau hujah-hujah, juga diam-diam ditolak

615
00:28:34,380 --> 00:28:37,510
ke dalam tindanan yang diwakili
oleh keping merah di sini,

616
00:28:37,510 --> 00:28:40,520
adalah alamat utama fizikal
dalam memori komputer anda,

617
00:28:40,520 --> 00:28:44,180
supaya apabila pertukaran dilakukan, komputer
tahu saya perlu 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 adalah berbahaya sekarang, kerana jika
jenis pengguna dalam juga lebih daripada hello,

620
00:28:51,960 --> 00:28:57,030
apa-apa yang input pengguna clobbers
atau menulis ganti bahawa seksyen merah,

621
00:28:57,030 --> 00:28:59,820
secara logik jika komputer
hanya akan membuta tuli menganggap

622
00:28:59,820 --> 00:29:03,830
bahawa bait dalam sepotong merah
alamat di mana ia harus kembali,

623
00:29:03,830 --> 00:29:09,020
bagaimana jika musuh yang cukup pintar atau
bernasib baik untuk meletakkan urutan bait

624
00:29:09,020 --> 00:29:13,450
ada yang kelihatan seperti alamat,
tetapi ia adalah alamat kod

625
00:29:13,450 --> 00:29:18,730
bahawa dia atau dia mahu komputer
untuk melaksanakan dan bukan utama?

626
00:29:18,730 --> 00:29:21,670
>> Dalam erti kata lain, jika apa yang
pengguna sedang menaip pada yang cepat,

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

628
00:29:23,850 --> 00:29:28,210
tetapi ia sebenarnya kod yang bersamaan
untuk memadam semua fail pengguna ini?

629
00:29:28,210 --> 00:29:30,060
Atau e-mel kata laluan mereka kepada saya?

630
00:29:30,060 --> 00:29:31,940
Atau memulakan pembalakan mereka
ketukan kekunci, bukan?

631
00:29:31,940 --> 00:29:34,920
Terdapat cara yang, mari kita menetapkan hari ini,
bahawa mereka boleh masuk ke dalam bukan sahaja hello

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

633
00:29:36,711 --> 00:29:39,570
lulus dalam kod, sifar dan
yang, bahawa komputer

634
00:29:39,570 --> 00:29:43,450
kesilapan untuk kedua-dua kod dan alamat.

635
00:29:43,450 --> 00:29:48,950
Jadi walaupun agak abstrak, jika
jenis pengguna dalam cukup kod pertentangan

636
00:29:48,950 --> 00:29:52,330
bahawa kita akan umum di sini kerana
A. A adalah serangan atau musuh.

637
00:29:52,330 --> 00:29:53,140
Barangan Jadi hanya tidak baik.

638
00:29:53,140 --> 00:29:55,306
Kami tidak mengambil berat tentang
nombor atau sifar atau orang-orang

639
00:29:55,306 --> 00:29:59,470
hari ini, seperti yang anda berakhir
penggantian seksyen yang merah,

640
00:29:59,470 --> 00:30:01,580
melihat bahawa jujukan bait.

641
00:30:01,580 --> 00:30:05,020
O 835 C sifar lapan sifar.

642
00:30:05,020 --> 00:30:08,960
Dan kini sebagai artikel Wikipedia di sini
telah dicadangkan, jika anda kini benar-benar memulakan

643
00:30:08,960 --> 00:30:12,460
melabel bait dalam komputer anda
ingatan, apa yang artikel Wikipedia adalah

644
00:30:12,460 --> 00:30:19,060
mencadangkan ialah, bagaimana jika alamat
itu bait kiri atas adalah 80 C 0 3508.

645
00:30:19,060 --> 00:30:22,200
>> Dalam erti kata lain, jika lelaki yang buruk adalah
bijak dengan kod nya

646
00:30:22,200 --> 00:30:26,650
untuk benar-benar meletakkan nombor di sini bahawa
sepadan dengan alamat kod di

647
00:30:26,650 --> 00:30:29,180
dia disuntik
ke dalam komputer, anda

648
00:30:29,180 --> 00:30:31,050
boleh menipu komputer
ke dalam melakukan apa-apa.

649
00:30:31,050 --> 00:30:34,140
Menghapuskan fail, menghantar e-mel
perkara, menghidu trafik anda,

650
00:30:34,140 --> 00:30:36,710
apa sahaja yang boleh menjadi
disuntik ke dalam komputer.

651
00:30:36,710 --> 00:30:39,220
Dan kerana itu suatu buffer overflow
serangan pada terasnya

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

653
00:30:43,530 --> 00:30:45,840
tidak mempunyai sempadannya diperiksa.

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

655
00:30:48,850 --> 00:30:52,560
dalam C ialah kita memang mempunyai
akses kepada mana-mana sahaja dalam memori.

656
00:30:52,560 --> 00:30:55,320
Terpulang kepada kita, pengaturcara,
yang menulis kod asal

657
00:30:55,320 --> 00:30:59,330
untuk memeriksa panjang darn mana-mana
tatasusunan bahawa kita memanipulasi.

658
00:30:59,330 --> 00:31:00,750
Jadi untuk menjadi jelas, apa yang menetapkan?

659
00:31:00,750 --> 00:31:03,190
Jika kita melancarkan kembali ini
kod, saya tidak perlu hanya

660
00:31:03,190 --> 00:31:08,000
menukar panjang bar, apa
lagi yang perlu saya dapat check?

661
00:31:08,000 --> 00:31:10,620
Apa lagi yang perlu saya lakukan untuk
mengelakkan serangan ini sepenuhnya?

662
00:31:10,620 --> 00:31:14,110
Saya tidak mahu hanya membuta tuli mengatakan
bahawa anda perlu menyalin sebanyak bait

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

664
00:31:16,140 --> 00:31:18,910
Saya ingin mengatakan, salinan sebagai
banyak bait yang pada bar

665
00:31:18,910 --> 00:31:24,090
sehingga yang diperuntukkan
memori, atau 12 maksima.

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

667
00:31:27,450 --> 00:31:32,800
tetapi jika ia melebihi 12, kita Kod hanya sukar
12 jarak maksimum yang mungkin.

668
00:31:32,800 --> 00:31:35,910
Jika tidak penampan yang dipanggil
serangan limpahan boleh berlaku.

669
00:31:35,910 --> 00:31:38,451
Di bahagian bawah slaid,
jika anda ingin tahu untuk membaca lebih

670
00:31:38,451 --> 00:31:41,200
adalah artikel asal yang sebenar
jika anda ingin lihat.

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

672
00:31:44,550 --> 00:31:46,680
Sehingga adalah cepat
rupa paras rendah pada apa

673
00:31:46,680 --> 00:31:49,709
masalah boleh timbul sekarang kita yang
mempunyai akses kepada memori komputer.

674
00:31:49,709 --> 00:31:51,750
Tetapi satu lagi masalah kita
telah tersandung pada Isnin

675
00:31:51,750 --> 00:31:53,800
hanya ketidakcekapan
daripada senarai berpaut.

676
00:31:53,800 --> 00:31:56,019
Kita kembali ke semasa linear.

677
00:31:56,019 --> 00:31:57,560
Kita tidak lagi mempunyai pelbagai yang berhampiran.

678
00:31:57,560 --> 00:31:58,980
Kami tidak mempunyai capaian rawak.

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

680
00:32:00,710 --> 00:32:04,590
Kami benar-benar perlu menggunakan gelung sementara
seperti yang saya tulis sebentar tadi.

681
00:32:04,590 --> 00:32:09,740
Tetapi pada hari Isnin, kita mendakwa bahawa kita boleh
merayap kembali ke alam kecekapan

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

683
00:32:13,040 --> 00:32:16,120
mungkin juga sesuatu yang
apa yang dikenali sebagai masa yang berterusan.

684
00:32:16,120 --> 00:32:19,840
Jadi bagaimana kita boleh berbuat demikian dengan menggunakan ini baru
alat, alamat-alamat ini, petunjuk ini,

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

686
00:32:22,210 --> 00:32:23,960
Nah, katakan
di sini, ini adalah sekumpulan

687
00:32:23,960 --> 00:32:27,170
nombor yang kita mahu menyimpan dalam
struktur data dan carian cekap.

688
00:32:27,170 --> 00:32:30,960
Kami benar-benar boleh putar balik ke minggu
dua, membuang ini ke dalam array,

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

690
00:32:33,150 --> 00:32:34,040
Pecah dan perintah.

691
00:32:34,040 --> 00:32:37,720
Dan sebenarnya anda menulis
carian binari dalam PSET3,

692
00:32:37,720 --> 00:32:40,100
di mana anda melaksanakan program yang dicari.

693
00:32:40,100 --> 00:32:40,890
Tetapi anda tahu apa.

694
00:32:40,890 --> 00:32:45,060
Ada jenis yang lebih
cara bijak untuk berbuat demikian.

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

696
00:32:47,390 --> 00:32:50,830
membolehkan kita untuk melihat mengapa binari
carian adalah begitu banyak lebih cepat.

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

698
00:32:52,980 --> 00:32:54,730
Yang walaupun dalam
pokok realiti sejenis

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

700
00:32:57,730 --> 00:33:00,830
seperti pokok keluarga, di mana anda perlu
datuk nenek atau datuk dan nenek yang hebat

701
00:33:00,830 --> 00:33:04,580
atau barang kecil di bahagian atas, bapa leluhur kita, dan
ibu pemimpin keluarga, hanya satu

702
00:33:04,580 --> 00:33:07,930
yang dipanggil akar, nod, di bawah
yang anak-anak mereka,

703
00:33:07,930 --> 00:33:11,442
di bawah yang adalah anak-anak, atau
keturunannya amnya.

704
00:33:11,442 --> 00:33:13,400
Dan sesiapa yang tergantung dari
bahagian bawah keluarga

705
00:33:13,400 --> 00:33:16,070
pokok, selain menjadi
bongsu dalam keluarga,

706
00:33:16,070 --> 00:33:19,520
juga boleh hanya menjadi generik
dipanggil daun pokok itu.

707
00:33:19,520 --> 00:33:21,800
>> Jadi ini adalah hanya sekumpulan
perkataan dan definisi

708
00:33:21,800 --> 00:33:25,790
untuk sesuatu yang dipanggil pokok dalam komputer
sains, sama seperti pohon keluarga.

709
00:33:25,790 --> 00:33:28,770
Tetapi ada jelmaan pelamun
pokok, satu daripadanya

710
00:33:28,770 --> 00:33:30,780
dipanggil pokok carian binari.

711
00:33:30,780 --> 00:33:34,380
Dan anda boleh jenis menggoda
selain apa yang perkara ini tidak.

712
00:33:34,380 --> 00:33:37,180
Nah, itu binari dalam apa rasa?

713
00:33:37,180 --> 00:33:41,455
Di manakah binari 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
Ia tidak begitu banyak sama ada atau.

717
00:33:47,210 --> 00:33:52,000
Ia lebih bahawa setiap satu daripada nod tidak mempunyai
lebih daripada dua kanak-kanak, seperti yang kita lihat di sini.

718
00:33:52,000 --> 00:33:54,990
Secara umum, tree-- dan
ibu bapa dan datuk dan nenek anda

719
00:33:54,990 --> 00:33:57,640
boleh mempunyai banyak anak-anak atau
cucu kerana mereka benar-benar mahu,

720
00:33:57,640 --> 00:34:00,820
dan sebagainya misalnya di sana kami mempunyai tiga
anak luar bahawa nod tangan kanan,

721
00:34:00,820 --> 00:34:05,480
tetapi di pokok binari, nod mempunyai
sifar, satu, atau dua kanak-kanak maksima.

722
00:34:05,480 --> 00:34:08,496
Dan itu yang terletak di,
kerana jika ia dihadkan oleh dua,

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

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

725
00:34:11,975 --> 00:34:13,350
Oleh itu, kita mempunyai sesuatu logaritma.

726
00:34:13,350 --> 00:34:14,558
Tetapi lebih kepada yang dalam seketika.

727
00:34:14,558 --> 00:34:19,810
Pokok carian bermakna bahawa nombor-nombor
disediakan supaya kanak-kanak sayap kiri

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

729
00:34:22,429 --> 00:34:26,010
Dan kanak-kanak haknya adalah
lebih besar daripada akar.

730
00:34:26,010 --> 00:34:29,290
Dalam erti kata lain, jika anda mengambil mana-mana daripada
nod, bulatan dalam gambar ini,

731
00:34:29,290 --> 00:34:31,840
dan melihat kirinya
kanak-kanak dan kanak-kanak kanan,

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

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

734
00:34:36,159 --> 00:34:37,780
Ia meninggalkan kanak-kanak adalah 33.

735
00:34:37,780 --> 00:34:38,620
Ia adalah kurang daripada.

736
00:34:38,620 --> 00:34:40,929
55, kanak-kanak haknya adalah 77.

737
00:34:40,929 --> 00:34:41,783
Ia adalah lebih besar daripada.

738
00:34:41,783 --> 00:34:43,199
Dan itu adalah satu definisi rekursi.

739
00:34:43,199 --> 00:34:46,480
Kita boleh memeriksa setiap salah seorang daripada mereka
nod dan corak yang sama akan tahan.

740
00:34:46,480 --> 00:34:49,389
>> Jadi apa yang baik dalam
pokok carian binari, adalah

741
00:34:49,389 --> 00:34:52,204
yang satu, ia dapat dilaksanakan
dengan struct, sama seperti ini.

742
00:34:52,204 --> 00:34:54,620
Dan walaupun 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 ini masih sukar difahami yang pasti,
tetapi kandungan nod dalam ini

745
00:35:00,570 --> 00:35:02,786
context-- dan kami terus
menggunakan nod perkataan,

746
00:35:02,786 --> 00:35:04,910
sama ada ia adalah segi empat tepat
pada skrin atau bulatan,

747
00:35:04,910 --> 00:35:08,970
ia hanya beberapa bekas generik,
dalam kes ini pokok, seperti yang

748
00:35:08,970 --> 00:35:11,780
yang kita lihat, kita memerlukan integer
Setiap nod

749
00:35:11,780 --> 00:35:15,460
dan kemudian saya memerlukan dua petunjuk menunjuk
kepada kanak-kanak di sebelah kiri dan kanak-kanak yang betul,

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
melaksanakan bahawa dalam struct.

752
00:35:20,730 --> 00:35:22,315
Dan bagaimana aku dapat melaksanakannya dalam kod?

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

754
00:35:26,730 --> 00:35:29,820
Ia tidak berfungsi, tetapi saya telah
disalin dan ditampal struktur tersebut.

755
00:35:29,820 --> 00:35:33,510
Dan jika fungsi saya untuk binari
pokok carian dipanggil carian,

756
00:35:33,510 --> 00:35:36,980
dan ini mengambil masa dua hujah,
yang N integer dan penunjuk

757
00:35:36,980 --> 00:35:41,400
untuk nod, jadi penunjuk kepada pokok
atau penunjuk kepada akar pokok,

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

759
00:35:43,482 --> 00:35:45,440
Well, pertama, kerana saya
berurusan dengan petunjuk,

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

761
00:35:46,750 --> 00:35:54,279
Jika setaraf pokok sama null, ialah N
dalam pokok ini atau tidak dalam pokok ini?

762
00:35:54,279 --> 00:35:55,070
Ia tidak boleh, bukan?

763
00:35:55,070 --> 00:35:56,870
Jika saya lalu null,
tiada apa-apa di sana.

764
00:35:56,870 --> 00:35:59,230
Saya mungkin juga hanya
membuta tuli mengatakan kembali palsu.

765
00:35:59,230 --> 00:36:04,050
Jika anda memberi saya apa-apa, saya pasti tidak boleh
mencari mana-mana nombor N. Jadi apa lagi yang mungkin saya

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

767
00:36:04,750 --> 00:36:12,830
Saya akan mengatakan dengan baik lagi kalau N adalah
kurang daripada apa yang ada pada nod pokok

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

769
00:36:16,300 --> 00:36:20,270
Dalam erti kata lain, jika bilangan Saya
cari, N, adalah kurang daripada nod

770
00:36:20,270 --> 00:36:21,340
yang saya lihat.

771
00:36:21,340 --> 00:36:23,190
Dan nod Saya sedang
di dipanggil pokok,

772
00:36:23,190 --> 00:36:26,370
dan ingat dari contoh sebelumnya
untuk mendapatkan sekurang-nilai dalam penunjuk,

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

774
00:36:28,310 --> 00:36:35,960
Jadi, jika N adalah kurang daripada pokok anak panah
N, saya mahu dari segi konsep pergi kiri.

775
00:36:35,960 --> 00:36:38,590
Bagaimana saya daftar mencari kiri?

776
00:36:38,590 --> 00:36:41,560
Untuk menjadi jelas, jika ini adalah
gambar yang berkenaan,

777
00:36:41,560 --> 00:36:44,612
dan saya telah diluluskan yang paling atas
arrow yang menunjuk ke bawah.

778
00:36:44,612 --> 00:36:45,570
Itulah penunjuk pokok saya.

779
00:36:45,570 --> 00:36:48,060
Saya menunjuk pada akar pokok.

780
00:36:48,060 --> 00:36:52,100
Dan saya tidak katakan, untuk
nombor 44, sewenang-wenangnya.

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

782
00:36:55,300 --> 00:36:56,360
Jadi ia adalah kurang daripada.

783
00:36:56,360 --> 00:36:58,760
Dan hal ini jika keadaan terpakai.

784
00:36:58,760 --> 00:37:03,981
Jadi dari segi konsep, apa yang saya mahu
mencari depan jika Saya 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 sekali, saya ingin
mencari kanak-kanak itu kiri,

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

789
00:37:12,789 --> 00:37:14,830
Dan sebenarnya, saya melalui
gambar di bawah ini

790
00:37:14,830 --> 00:37:17,770
hanya untuk seketika, kerana
Saya tidak boleh calar ini keluar.

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

792
00:37:21,150 --> 00:37:23,180
Saya sedang mencari adalah untuk
kiri, ia adalah jenis

793
00:37:23,180 --> 00:37:26,010
daripada seperti mengoyak buku telefon di
separuh atau mengoyak pokok pada separuh.

794
00:37:26,010 --> 00:37:29,660
Saya tidak lagi perlu mengambil berat tentang
keseluruhan separuh ini pokok itu.

795
00:37:29,660 --> 00:37:33,270
Dan lagi, ingin tahu dari segi
struktur, perkara ini di sini bahawa

796
00:37:33,270 --> 00:37:36,682
bermula dengan 33, itu sendiri
adalah pokok carian binari.

797
00:37:36,682 --> 00:37:39,890
Saya berkata perkataan rekursi sebelum ini kerana
sesungguhnya ini adalah struktur data yang

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

799
00:37:41,707 --> 00:37:44,540
Anda mungkin mempunyai pokok yang ini
besar, tetapi setiap seorang daripada anak-anak mereka

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

801
00:37:46,870 --> 00:37:50,910
Sebaliknya ia menjadi datuk
atau nenek, kini ia hanya ibu

802
00:37:50,910 --> 00:37:54,300
or-- Saya tidak boleh tidak iaitu- ibu
atau ayah, yang akan menjadi pelik.

803
00:37:54,300 --> 00:37:59,000
Sebaliknya kedua-dua kanak-kanak terdapat
akan menjadi seperti abang dan adik-beradik.

804
00:37:59,000 --> 00:38:01,120
Generasi baru pokok keluarga.

805
00:38:01,120 --> 00:38:02,900
Tetapi dari segi struktur, ia adalah idea yang sama.

806
00:38:02,900 --> 00:38:06,790
Dan ternyata saya mempunyai fungsi yang
yang aku boleh gelintaran perduaan

807
00:38:06,790 --> 00:38:07,290
pokok.

808
00:38:07,290 --> 00:38:08,680
Ia dipanggil carian.

809
00:38:08,680 --> 00:38:17,870
Saya mencari N di pokok panah kiri
lain jika N adalah lebih besar daripada nilai

810
00:38:17,870 --> 00:38:18,870
bahawa saya kini di.

811
00:38:18,870 --> 00:38:20,800
55 dalam cerita sebentar tadi.

812
00:38:20,800 --> 00:38:23,780
Saya mempunyai fungsi yang dipanggil
carian bahawa saya boleh hanya

813
00:38:23,780 --> 00:38:29,660
lulus N ini dan secara rekursif mencari
sub-pokok dan pulangan hanya

814
00:38:29,660 --> 00:38:30,620
apa jawapan itu.

815
00:38:30,620 --> 00:38:33,530
Lagi yang saya telah mendapat beberapa kes asas akhir di sini.

816
00:38:33,530 --> 00:38:35,310
>> Apa halnya akhir?

817
00:38:35,310 --> 00:38:36,570
Pokok sama ada null.

818
00:38:36,570 --> 00:38:39,980
Nilai saya memuat cari adalah
kurang daripada atau lebih besar daripada itu

819
00:38:39,980 --> 00:38:42,610
atau sama dengannya.

820
00:38:42,610 --> 00:38:44,750
Dan saya boleh katakan sama
sama, tetapi secara logik ia

821
00:38:44,750 --> 00:38:46,500
bersamaan dengan hanya mengatakan lagi di sini.

822
00:38:46,500 --> 00:38:49,150
Jadi benar adalah bagaimana saya mencari sesuatu.

823
00:38:49,150 --> 00:38:51,710
Jadi mudah-mudahan ini adalah satu
walaupun contoh yang lebih menarik

824
00:38:51,710 --> 00:38:54,900
daripada fungsi sigma bodoh
kami menjalankan kuliah ke belakang,

825
00:38:54,900 --> 00:38:58,360
di mana ia hanya sebagai mudah untuk digunakan gelung
untuk mengira semua nombor dari satu

826
00:38:58,360 --> 00:39:02,390
N. Di sini dengan struktur data
itu sendiri adalah secara rekursif

827
00:39:02,390 --> 00:39:07,050
jelas dan secara rekursif dikeluarkan, sekarang kita
mempunyai keupayaan untuk menyatakan diri kita sendiri

828
00:39:07,050 --> 00:39:09,780
kod itu sendiri adalah rekursif.

829
00:39:09,780 --> 00:39:12,580
Jadi ini adalah kod yang tepat sama di sini.

830
00:39:12,580 --> 00:39:14,400
>> Jadi apa masalah lain yang kita boleh menyelesaikan?

831
00:39:14,400 --> 00:39:18,160
Jadi langkah yang cepat dari
pokok hanya untuk seketika.

832
00:39:18,160 --> 00:39:20,130
Di sini ialah, berkata, bendera Jerman.

833
00:39:20,130 --> 00:39:22,020
Dan ada jelas
corak untuk 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 semudah ini dari segi
warna dan corak mereka.

836
00:39:27,560 --> 00:39:31,930
Tetapi menganggap bahawa ini disimpan sebagai
GIF atau JPEG, atau bitmap, atau ping,

837
00:39:31,930 --> 00:39:34,240
mana-mana format fail grafik
yang anda sudah biasa,

838
00:39:34,240 --> 00:39:36,460
ada yang kami
bermain dengan di PSET4.

839
00:39:36,460 --> 00:39:41,550
Ini nampaknya tidak berbaloi untuk menyimpan
pixel hitam, hitam piksel, piksel 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 berturut-turut, maka sejumlah besar
sama, maka sekumpulan keseluruhan

842
00:39:47,430 --> 00:39:49,530
daripadanya, dan kemudian
sejumlah besar piksel merah,

843
00:39:49,530 --> 00:39:53,020
piksel merah, piksel merah, maka keseluruhan
sekumpulan piksel kuning, kuning, bukan?

844
00:39:53,020 --> 00:39:55,050
>> Ada ketidakcekapan seperti di sini.

845
00:39:55,050 --> 00:39:59,040
Bagaimana anda intuitif
memampatkan bendera Jerman

846
00:39:59,040 --> 00:40:01,320
jika melaksanakannya sebagai fail?

847
00:40:01,320 --> 00:40:04,940
Seperti apa maklumat boleh kita tidak
mengganggu menyimpan dalam cakera dalam rangka

848
00:40:04,940 --> 00:40:08,040
untuk mengurangkan saiz fail kami seperti
megabait kepada kilobait, sesuatu

849
00:40:08,040 --> 00:40:09,430
lebih kecil?

850
00:40:09,430 --> 00:40:13,130
Di mana terletak lebihan yang
di sini untuk menjadi nyata?

851
00:40:13,130 --> 00:40:13,880
Apa yang anda boleh 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 sekali.

855
00:40:21,970 --> 00:40:24,550
Mengapa tidak bukannya ingat
warna setiap piksel darn

856
00:40:24,550 --> 00:40:28,200
sama seperti yang anda lakukan dalam PSET4
dengan format fail bitmap,

857
00:40:28,200 --> 00:40:32,060
mengapa tidak anda hanya mewakili
ruangan paling kiri piksel, misalnya

858
00:40:32,060 --> 00:40:35,370
sekumpulan piksel hitam, sekumpulan
merah, dan mempunyai banyak kuning,

859
00:40:35,370 --> 00:40:39,210
dan kemudian hanya entah bagaimana mengekod
idea berulang 100 kali

860
00:40:39,210 --> 00:40:41,020
atau mengulangi ini 1000 kali?

861
00:40:41,020 --> 00:40:43,430
Di mana 100 atau 1000 adalah
hanya integer, supaya anda

862
00:40:43,430 --> 00:40:47,290
boleh pergi dengan hanya satu nombor
bukannya beratus-ratus atau beribu-ribu

863
00:40:47,290 --> 00:40:48,270
piksel tambahan.

864
00:40:48,270 --> 00:40:50,990
Dan sesungguhnya, itulah bagaimana kita
boleh memampatkan bendera Jerman.

865
00:40:50,990 --> 00:40:51,490
Dan

866
00:40:51,490 --> 00:40:53,470
Sekarang bagaimana pula dengan bendera Perancis?

867
00:40:53,470 --> 00:40:58,930
Dan beberapa jenis kecil
latihan mental, yang bendera

868
00:40:58,930 --> 00:41:01,040
boleh dimampatkan lanjut mengenai cakera?

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
Bendera Jerman, kerana ada
lebihan lebih mendatar.

871
00:41:08,490 --> 00:41:12,190
Dan dengan reka bentuk, banyak fail grafik
format memang bekerja sebagai garis imbasan

872
00:41:12,190 --> 00:41:12,830
melintang.

873
00:41:12,830 --> 00:41:14,674
Mereka boleh bekerja
menegak, hanya manusia

874
00:41:14,674 --> 00:41:17,090
tahun telah memilih yang lalu bahawa kita akan
umumnya memikirkan perkara-perkara berturut-turut

875
00:41:17,090 --> 00:41:18,880
oleh baris dan bukannya lajur oleh tiang.

876
00:41:18,880 --> 00:41:20,820
Maka sesungguhnya jika kamu
untuk melihat fail

877
00:41:20,820 --> 00:41:24,670
Saiz bendera Jerman dan Perancis
bendera, selagi resolusi adalah

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, kerana anda
perlu mengulangi diri anda tiga kali.

880
00:41:31,580 --> 00:41:35,570
Anda perlu nyatakan biru, ulang
diri sendiri, putih, ulang diri, merah,

881
00:41:35,570 --> 00:41:36,740
mengulangi diri sendiri.

882
00:41:36,740 --> 00:41:39,000
Anda tidak boleh hanya pergi semua
jalan ke kanan.

883
00:41:39,000 --> 00:41:41,200
Dan sebagai diketepikan, untuk membuat
membersihkan mampatan

884
00:41:41,200 --> 00:41:43,910
mana-mana, jika ini adalah
empat bingkai dari video-- yang anda

885
00:41:43,910 --> 00:41:45,890
mungkin ingat bahawa filem
atau video umumnya

886
00:41:45,890 --> 00:41:47,286
seperti 29 atau 30 bingkai sesaat.

887
00:41:47,286 --> 00:41:50,410
Ia seperti sebuah buku flip kecil di mana anda
hanya melihat imej, imej, gambar, imej,

888
00:41:50,410 --> 00:41:54,410
imej hanya super cepat supaya ia kelihatan seperti
pelakon pada skrin bergerak.

889
00:41:54,410 --> 00:41:57,130
Berikut adalah lebah keliru pada
atas sekumpulan bunga.

890
00:41:57,130 --> 00:41:59,790
Dan walaupun ia mungkin sejenis
sukar untuk melihat pada pandangan pertama,

891
00:41:59,790 --> 00:42:04,020
satu-satunya perkara yang bergerak dalam
filem ini adalah lebah.

892
00:42:04,020 --> 00:42:06,880
>> Apa yang bodoh tentang menyimpan
video yang tidak dimampatkan?

893
00:42:06,880 --> 00:42:11,420
Ia adalah jenis satu pembaziran untuk menyimpan video
empat imej hampir sama yang

894
00:42:11,420 --> 00:42:13,670
berbeza hanya setakat yang mana lebah itu.

895
00:42:13,670 --> 00:42:16,280
Anda boleh buang paling
maklumat yang

896
00:42:16,280 --> 00:42:20,190
dan ingat sahaja, misalnya,
bingkai pertama dan rangka yang lalu,

897
00:42:20,190 --> 00:42:22,180
kerangka utama jika anda telah
pernah mendengar perkataan,

898
00:42:22,180 --> 00:42:24,337
dan hanya menyimpan dalam
pertengahan di mana lebah itu.

899
00:42:24,337 --> 00:42:26,170
Dan anda tidak perlu
menyimpan semua merah jambu,

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 adalah untuk hanya mengatakan bahawa
mampatan di mana-mana.

902
00:42:31,200 --> 00:42:34,900
Ia adalah satu teknik kita sering menggunakan
atau mengambil mudah hari ini.

903
00:42:34,900 --> 00:42:38,750
>> Tetapi bagaimana anda memampatkan teks?

904
00:42:38,750 --> 00:42:40,450
Bagaimana anda pergi tentang memampatkan teks?

905
00:42:40,450 --> 00:42:45,410
Well, setiap satu daripada watak-watak dalam
Ascii adalah salah satu bait, atau lapan bit.

906
00:42:45,410 --> 00:42:47,360
Dan itulah jenis bodoh, bukan?

907
00:42:47,360 --> 00:42:51,160
Kerana anda mungkin jenis A
dan E dan I dan O dan U banyak

908
00:42:51,160 --> 00:42:55,270
lebih kerap daripada seperti W atau Q atau Z,
bergantung kepada bahasa yang

909
00:42:55,270 --> 00:42:56,610
anda menulis pasti.

910
00:42:56,610 --> 00:42:59,600
Dan jadi kenapa kita menggunakan
lapan bit untuk setiap surat,

911
00:42:59,600 --> 00:43:02,040
termasuk kurangnya
huruf popular, bukan?

912
00:43:02,040 --> 00:43:05,300
Mengapa tidak menggunakan kurang bit untuk
huruf super popular,

913
00:43:05,300 --> 00:43:07,760
seperti E, perkara yang anda rasa
pertama di Wheel of Fortune,

914
00:43:07,760 --> 00:43:10,450
dan menggunakan lebih banyak bit untuk
huruf kurang popular?

915
00:43:10,450 --> 00:43:10,950
Mengapa?

916
00:43:10,950 --> 00:43:13,130
Kerana kita hanya akan
menggunakan mereka kurang kerap.

917
00:43:13,130 --> 00:43:15,838
>> Nah, ternyata bahawa ada mempunyai
cubaan dibuat untuk melakukan ini.

918
00:43:15,838 --> 00:43:18,630
Dan jika anda ingat dari gred
sekolah atau sekolah tinggi, kod Morse.

919
00:43:18,630 --> 00:43:20,400
Kod Morse mempunyai titik
dan sengkang yang boleh

920
00:43:20,400 --> 00:43:24,270
dihantar bersama-sama dawai sebagai
bunyi atau isyarat sejenis.

921
00:43:24,270 --> 00:43:25,930
Tetapi kod Morse adalah super bersih.

922
00:43:25,930 --> 00:43:29,010
Ia adalah jenis sistem binari dalam
bahawa anda mempunyai titik atau sengkang.

923
00:43:29,010 --> 00:43:30,977
Tetapi jika anda lihat, misalnya, dua titik.

924
00:43:30,977 --> 00:43:33,810
Atau jika anda berfikir kembali kepada pengendali
yang pergi seperti bip, bip, bip,

925
00:43:33,810 --> 00:43:36,760
bip, memukul pencetus sedikit
yang menghantar isyarat,

926
00:43:36,760 --> 00:43:40,360
jika anda, penerima, menerima dua
titik, apa mesej yang anda terima?

927
00:43:40,360 --> 00:43:43,490
Benar-benar sewenang-wenangnya.

928
00:43:43,490 --> 00:43:44,450
>> I?

929
00:43:44,450 --> 00:43:45,060
I?

930
00:43:45,060 --> 00:43:47,500
Atau about-- atau saya?

931
00:43:47,500 --> 00:43:49,570
Mungkin ia adalah hanya dua kanan E?

932
00:43:49,570 --> 00:43:52,480
Jadi ada masalah ini
daripada decodability dengan Morse

933
00:43:52,480 --> 00:43:54,890
kod, di mana melainkan jika
orang menghantar anda mesej

934
00:43:54,890 --> 00:43:59,510
sebenarnya berhenti seketika supaya anda boleh menyusun daripada
melihat atau mendengar jurang antara huruf,

935
00:43:59,510 --> 00:44:02,990
ia tidak mencukupi hanya untuk
menghantar aliran sifar dan satu,

936
00:44:02,990 --> 00:44:05,610
atau titik dan sengkang,
kerana ada kekaburan.

937
00:44:05,610 --> 00:44:08,640
E ialah titik tunggal, jadi jika anda
melihat dua titik atau mendengar dua titik,

938
00:44:08,640 --> 00:44:11,254
mungkin ia dua E atau mungkin ia adalah salah I.

939
00:44:11,254 --> 00:44:13,670
Oleh itu, kita memerlukan sistem itu adalah satu
sedikit lebih pandai daripada itu.

940
00:44:13,670 --> 00:44:16,851
Jadi seorang lelaki bernama Huffman tahun
lalu datang dengan betul-betul ini.

941
00:44:16,851 --> 00:44:18,600
Oleh itu, kita hanya akan
mengambil pandangan yang cepat

942
00:44:18,600 --> 00:44:20,114
bagaimana pokok-pokok germane kepada ini.

943
00:44:20,114 --> 00:44:22,530
Katakan bahawa ini adalah beberapa
mesej bodoh yang anda hendak hantar,

944
00:44:22,530 --> 00:44:26,342
terdiri daripada hanya A, B, C D dan E,
tetapi ada banyak lebihan di sini.

945
00:44:26,342 --> 00:44:27,550
Ia tidak bertujuan untuk menjadi bahasa Inggeris.

946
00:44:27,550 --> 00:44:28,341
Ia tidak disulitkan.

947
00:44:28,341 --> 00:44:30,540
Ia hanya satu mesej 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, di sini adalah

949
00:44:34,010 --> 00:44:34,890
kekerapan.

950
00:44:34,890 --> 00:44:37,800
20% daripada huruf
A, 45% daripada huruf

951
00:44:37,800 --> 00:44:39,660
adalah E, dan tiga frekuensi lain.

952
00:44:39,660 --> 00:44:41,960
Kami dikira di sana secara manual
dan hanya melakukan matematik.

953
00:44:41,960 --> 00:44:44,579
>> Jadi ia ternyata bahawa
Huffman, sedikit masa lalu,

954
00:44:44,579 --> 00:44:46,620
menyedari bahawa, anda tahu
apa, jika saya mula membina

955
00:44:46,620 --> 00:44:51,172
pokok, atau hutan pokok, jika anda akan,
seperti berikut, saya boleh melakukan perkara berikut.

956
00:44:51,172 --> 00:44:53,880
Saya akan memberikan kepada setiap nod
surat-surat yang saya sayang

957
00:44:53,880 --> 00:44:55,530
dan saya akan menyimpan
di dalam nod yang

958
00:44:55,530 --> 00:44:58,610
frekuensi sebagai titik terapung
nilai, atau anda boleh menggunakan ia sebagai N, juga,

959
00:44:58,610 --> 00:45:00,210
tetapi kita hanya akan menggunakan apungan di sini.

960
00:45:00,210 --> 00:45:03,100
Dan algoritma yang
beliau mencadangkan ialah anda

961
00:45:03,100 --> 00:45:07,210
mengambil hutan ini nod tunggal
pokok-pokok, pokok-pokok supaya super pendek,

962
00:45:07,210 --> 00:45:11,920
dan anda mula menghubungkan mereka dengan
kumpulan baru, ibu bapa baru, jika anda akan.

963
00:45:11,920 --> 00:45:16,150
Dan anda melakukan ini dengan memilih
dua frekuensi paling kecil pada satu masa.

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 mewujudkan nod baru.

966
00:45:19,090 --> 00:45:20,910
Aku mengajak nod baru 20%.

967
00:45:20,910 --> 00:45:22,750
>> Yang dua nod saya menggabungkan seterusnya?

968
00:45:22,750 --> 00:45:23,810
Ia sedikit kabur.

969
00:45:23,810 --> 00:45:26,643
Jadi ada beberapa kes sudut untuk
mempertimbangkan, tetapi untuk menjaga perkara-perkara yang cantik,

970
00:45:26,643 --> 00:45:29,300
Saya akan memilih 20% -
Saya kini mengabaikan kanak-kanak.

971
00:45:29,300 --> 00:45:33,640
Saya akan memilih 20% dan
15% dan menarik dua tepi baru.

972
00:45:33,640 --> 00:45:35,624
Dan sekarang yang dua nod
saya secara logik bergabung?

973
00:45:35,624 --> 00:45:38,540
Abaikan semua kanak-kanak, 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 nod saya mengikat bersama-sama?

976
00:45:42,220 --> 00:45:44,530
Point dua dan 0.35.

977
00:45:44,530 --> 00:45:45,890
Jadi biarlah saya menarik dua tepi baru.

978
00:45:45,890 --> 00:45:47,570
Dan kemudian saya hanya mendapat satu kiri.

979
00:45:47,570 --> 00:45:48,650
Jadi di sini adalah pokok.

980
00:45:48,650 --> 00:45:51,160
Dan ia telah ditarik sengaja
untuk melihat jenis cantik,

981
00:45:51,160 --> 00:45:55,870
tetapi notis bahawa tepi mempunyai
juga telah dilabel sifar dan satu.

982
00:45:55,870 --> 00:45:59,510
Jadi semua tepi kiri adalah sifar
sewenang-wenangnya, tetapi 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 dicadangkan iaitu,
jika anda mahu untuk mewakili B,

985
00:46:05,070 --> 00:46:10,080
bukannya mewakili nombor 66 sebagai
yang Ascii yang adalah lapan keseluruhan bit,

986
00:46:10,080 --> 00:46:13,360
anda tahu apa, hanya kedai
corak sifar, sifar, sifar,

987
00:46:13,360 --> 00:46:17,030
sifar, kerana itulah jalan yang
dari pokok saya, pokok Encik Huffman-kanak,

988
00:46:17,030 --> 00:46:18,600
kepada 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
menghantar lapan bit yang mewakili E.
Sebaliknya, menghantar apa corak bit?

991
00:46:26,290 --> 00:46:26,890
One.

992
00:46:26,890 --> 00:46:30,410
Dan apa yang baik tentang ini adalah
bahawa E adalah surat yang paling popular,

993
00:46:30,410 --> 00:46:32,340
dan anda menggunakan
kod singkat untuk itu.

994
00:46:32,340 --> 00:46:34,090
Seterusnya yang paling popular
surat kelihatan seperti ia

995
00:46:34,090 --> 00:46:37,380
adalah A. Dan berapa banyak bit
dia mencadangkan menggunakan untuk itu?

996
00:46:37,380 --> 00:46:38,270
Sifar, satu.

997
00:46:38,270 --> 00:46:41,060
>> Dan kerana ia dilaksanakan
sebagai pokok ini, buat masa ini

998
00:46:41,060 --> 00:46:43,350
biarlah saya menetapkan ada
tiada kekaburan dalam Morse

999
00:46:43,350 --> 00:46:46,090
kod, kerana semua
huruf yang anda mengambil berat tentang

1000
00:46:46,090 --> 00:46:48,780
adalah pada akhir pinggir ini.

1001
00:46:48,780 --> 00:46:50,580
Jadi itu hanya salah satu
permohonan pokok.

1002
00:46:50,580 --> 00:46:52,538
Ini is-- dan saya akan melambai
tangan saya ini bagaimana anda

1003
00:46:52,538 --> 00:46:55,570
mungkin melaksanakan ini sebagai struktur C.

1004
00:46:55,570 --> 00:46:58,260
Kita hanya perlu menggabungkan
simbol, seperti char,

1005
00:46:58,260 --> 00:46:59,910
dan kekerapan dalam kiri dan kanan.

1006
00:46:59,910 --> 00:47:02,510
Tetapi mari kita lihat dua
contoh terakhir yang anda akan

1007
00:47:02,510 --> 00:47:06,070
mendapatkan cukup akrab dengan selepas
kuiz sifar dalam masalah menetapkan lima.

1008
00:47:06,070 --> 00:47:09,210
>> Jadi ada struktur data
dikenali sebagai meja hash.

1009
00:47:09,210 --> 00:47:12,247
Dan jadual hash adalah jenis
sejuk kerana ia mempunyai baldi.

1010
00:47:12,247 --> 00:47:14,830
Dan andaikan ada empat baldi
di sini, hanya empat ruang kosong.

1011
00:47:14,830 --> 00:47:20,830
Berikut adalah satu set kad, dan di sini adalah
kelab, spade, kelab, berlian, kelab,

1012
00:47:20,830 --> 00:47:25,960
berlian, kelab, berlian,
clubs-- jadi ini adalah rawak.

1013
00:47:25,960 --> 00:47:30,330
Hati, hearts-- jadi saya
bucketizing semua input di sini.

1014
00:47:30,330 --> 00:47:32,430
Dan keperluan jadual hash
melihat input anda,

1015
00:47:32,430 --> 00:47:34,850
dan kemudian memasukkannya ke dalam yang tertentu
meletakkan berdasarkan apa yang anda lihat.

1016
00:47:34,850 --> 00:47:35,600
Ia algoritma.

1017
00:47:35,600 --> 00:47:37,980
Dan saya menggunakan super yang
algoritma visual mudah.

1018
00:47:37,980 --> 00:47:40,030
Bahagian paling sukar yang merupakan
mengingati apa gambar-gambar yang telah.

1019
00:47:40,030 --> 00:47:41,590
Dan kemudian ada empat jumlah sesuatu.

1020
00:47:41,590 --> 00:47:45,440
>> Adapun susunan telah semakin meningkat, yang
adalah satu perkara yang reka bentuk yang sengaja di sini.

1021
00:47:45,440 --> 00:47:46,540
Tetapi apa lagi yang mungkin saya lakukan?

1022
00:47:46,540 --> 00:47:49,080
Jadi sebenarnya di sini kita mempunyai
sekumpulan buku peperiksaan sekolah lama.

1023
00:47:49,080 --> 00:47:51,240
Katakan sekumpulan
nama pelajar di sini.

1024
00:47:51,240 --> 00:47:52,570
Berikut adalah jadual hash yang lebih besar.

1025
00:47:52,570 --> 00:47:54,867
Daripada empat baldi,
Saya telah, katakan 26.

1026
00:47:54,867 --> 00:47:57,950
Dan kita tidak mahu pergi meminjam 26
perkara-perkara dari luar [? Annenberg?], Jadi

1027
00:47:57,950 --> 00:48:00,289
di sini adalah lima yang mewakili
A hingga Z. Dan jika saya

1028
00:48:00,289 --> 00:48:03,580
melihat seorang pelajar yang namanya bermula dengan A,
Saya akan meletakkan atau kuiz di sana.

1029
00:48:03,580 --> 00:48:08,850
Jika seseorang yang bermula dengan C, di sana,
A-- sebenarnya, tidak mahu berbuat demikian.

1030
00:48:08,850 --> 00:48:10,060
B pergi di sini.

1031
00:48:10,060 --> 00:48:13,390
Jadi saya telah mendapat A dan B dan C. Dan
sekarang di sini adalah satu lagi pelajar.

1032
00:48:13,390 --> 00:48:16,212
Tetapi jika jadual hash ini adalah
dilaksanakan dengan array,

1033
00:48:16,212 --> 00:48:17,920
Saya jenis diskrukan
pada ketika ini, bukan?

1034
00:48:17,920 --> 00:48:19,510
Saya jenis perlu meletakkan suatu tempat ini.

1035
00:48:19,510 --> 00:48:24,380
>> Jadi salah satu cara saya boleh menyelesaikan masalah ini, semua
betul, A sibuk, B sibuk, C sibuk.

1036
00:48:24,380 --> 00:48:28,880
Saya akan memasukkannya ke dalam D. Jadi pada
pertama, saya mempunyai akses segera rawak

1037
00:48:28,880 --> 00:48:31,064
kepada setiap baldi untuk pelajar.

1038
00:48:31,064 --> 00:48:33,230
Tetapi sekarang ia adalah jenis diturunkan
menjadi sesuatu yang linear,

1039
00:48:33,230 --> 00:48:36,750
kerana jika saya mahu untuk mencari seseorang
nama yang bermula dengan A, saya semak di sini.

1040
00:48:36,750 --> 00:48:38,854
Tetapi jika ini bukan satu-A
pelajar saya cari,

1041
00:48:38,854 --> 00:48:41,520
Saya jenis perlu bermula memeriksa
baldi, kerana apa yang saya lakukan

1042
00:48:41,520 --> 00:48:44,530
adalah jenis linear
menyiasat struktur data.

1043
00:48:44,530 --> 00:48:47,710
Cara yang bodoh untuk mengatakan hanya melihat
untuk membuka yang pertama boleh,

1044
00:48:47,710 --> 00:48:51,850
dan meletakkan sebagai pelan B, boleh dikatakan,
atau pelan D dalam kes ini, nilai

1045
00:48:51,850 --> 00:48:53,340
di lokasi yang sebaliknya.

1046
00:48:53,340 --> 00:48:56,470
Ini hanyalah supaya jika anda telah
mendapat 26 lokasi dan tiada pelajar

1047
00:48:56,470 --> 00:49:00,600
dengan nama Q atau Z, atau sesuatu seperti
bahawa, sekurang-kurangnya anda menggunakan ruang.

1048
00:49:00,600 --> 00:49:03,140
>> Tetapi kita telah pun melihat lebih
penyelesaian yang bijak di sini, bukan?

1049
00:49:03,140 --> 00:49:04,870
Apa yang akan anda lakukan dan bukannya
jika anda mempunyai perlanggaran?

1050
00:49:04,870 --> 00:49:06,670
Jika dua orang mempunyai
nama A, apa yang akan

1051
00:49:06,670 --> 00:49:09,160
telah lebih yang lebih bijak atau
penyelesaian intuitif daripada hanya

1052
00:49:09,160 --> 00:49:12,840
meletakkan A di mana D sepatutnya?

1053
00:49:12,840 --> 00:49:14,810
Kenapa saya tidak hanya pergi
luar [? Annenberg?],

1054
00:49:14,810 --> 00:49:19,960
seperti malloc, nod yang lain, meletakkan ia
sini, dan kemudian meletakkan bahawa Seorang pelajar di sini.

1055
00:49:19,960 --> 00:49:22,120
Supaya saya pada dasarnya mempunyai
beberapa jenis pelbagai,

1056
00:49:22,120 --> 00:49:25,590
atau mungkin lebih elegan kerana kami
mula melihat senarai berpaut.

1057
00:49:25,590 --> 00:49:29,520
>> Dan sebagainya jadual hash adalah struktur yang
yang boleh kelihatan seperti ini,

1058
00:49:29,520 --> 00:49:33,900
tetapi yang lebih bijak, anda sesuatu yang dinamakan
chaining berasingan, di mana jadual hash

1059
00:49:33,900 --> 00:49:38,340
cukup hanya adalah pelbagai, setiap
yang unsur-unsur bukan nombor,

1060
00:49:38,340 --> 00:49:40,470
itu sendiri senarai berpaut.

1061
00:49:40,470 --> 00:49:45,080
Supaya anda mendapat akses super cepat
membuat keputusan di mana untuk hash nilai ke.

1062
00:49:45,080 --> 00:49:48,059
Sama seperti dengan contoh kad,
Saya membuat keputusan super cepat.

1063
00:49:48,059 --> 00:49:49,600
Hati pergi sini, berlian pergi sini.

1064
00:49:49,600 --> 00:49:52,180
Sama di sini, A pergi sini,
D pergi sini, B pergi sini.

1065
00:49:52,180 --> 00:49:55,740
Jadi super cepat melihat-up, dan jika
anda berlaku untuk menghadapi kes

1066
00:49:55,740 --> 00:49:59,429
perlanggaran di mana anda mempunyai dua
orang yang mempunyai nama yang sama, dan kemudian

1067
00:49:59,429 --> 00:50:00,970
anda hanya mula menghubungkan mereka bersama-sama.

1068
00:50:00,970 --> 00:50:03,900
Dan mungkin anda menjaga mereka disusun
mengikut abjad, mungkin anda tidak.

1069
00:50:03,900 --> 00:50:05,900
Tetapi sekurang-kurangnya sekarang kita mempunyai dinamisme.

1070
00:50:05,900 --> 00:50:10,250
Jadi di satu pihak kita ada super cepat
masa yang berterusan, dan jenis masa linear

1071
00:50:10,250 --> 00:50:14,110
terlibat jika ini senarai berkaitan
mula mendapat sedikit panjang.

1072
00:50:14,110 --> 00:50:16,880
>> Jadi ini jenis yang bodoh,
tahun jenaka geeky lalu.

1073
00:50:16,880 --> 00:50:19,590
Pada CS50 hack-a-thon,
apabila pelajar mendaftar masuk,

1074
00:50:19,590 --> 00:50:22,040
beberapa TF atau CA setiap tahun
difikirkan ia melucukan untuk bersabar

1075
00:50:22,040 --> 00:50:27,772
tanda seperti ini, di mana ia hanya
bermakna jika nama anda bermula 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 bermula
dengan B, pergi this-- OK,

1078
00:50:31,110 --> 00:50:33,290
ia melucukan mungkin kemudian pada semester tersebut.

1079
00:50:33,290 --> 00:50:36,420
Tetapi ada satu lagi
cara untuk berbuat demikian juga.

1080
00:50:36,420 --> 00:50:37,410
Kembali kepada 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 dinamakan indone a.

1084
00:50:42,400 --> 00:50:47,140
T-R-I-E, yang atas sebab tertentu adalah pendek
untuk mendapatkan semula, tetapi ia dipanggil indone.

1085
00:50:47,140 --> 00:50:51,389
Jadi indone adalah pilihan yang menarik
amalgam banyak idea-idea ini.

1086
00:50:51,389 --> 00:50:52,930
Ia adalah satu pokok, yang kita lihat sebelum ini.

1087
00:50:52,930 --> 00:50:54,180
Ia bukan satu pokok carian binari.

1088
00:50:54,180 --> 00:50:58,410
Ia adalah pokok dengan apa-apa bilangan kanak-kanak,
tetapi setiap daripada kanak-kanak di indone a

1089
00:50:58,410 --> 00:51:00,090
adalah pelbagai.

1090
00:51:00,090 --> 00:51:04,790
Pelbagai saiz, katakan, 26 atau mungkin 27
jika anda mahu untuk menyokong nama ditulis dgn tanda penghubung

1091
00:51:04,790 --> 00:51:06,790
atau koma dalam nama-nama rakyat.

1092
00:51:06,790 --> 00:51:08,280
>> Dan sebagainya 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 nod atas ada, M, adalah
menunjuk kepada perkara yang paling kiri di sana,

1095
00:51:13,710 --> 00:51:17,665
yang kemudian A, X, W, E, L, L. Ini
hanya satu struktur data yang sewenang-wenangnya

1096
00:51:17,665 --> 00:51:19,120
ialah menyimpan nama-nama rakyat.

1097
00:51:19,120 --> 00:51:25,720
Dan Maxwell disimpan dengan hanya mengikuti
jalan yang mudah untuk pelbagai untuk pelbagai.

1098
00:51:25,720 --> 00:51:30,050
Tetapi apa yang menakjubkan tentang indone adalah
itu, manakala senarai berpaut dan juga

1099
00:51:30,050 --> 00:51:34,520
array, yang terbaik kita pernah mendapat adalah
masa linear atau masa logaritma mencari

1100
00:51:34,520 --> 00:51:35,600
seseorang sehingga.

1101
00:51:35,600 --> 00:51:40,530
Dalam struktur data ini indone, jika
struktur data saya mempunyai satu nama di dalamnya

1102
00:51:40,530 --> 00:51:43,720
dan saya mencari untuk Maxwell, Saya
akan mencari dia cukup cepat.

1103
00:51:43,720 --> 00:51:47,910
Saya hanya mencari M-A-X-W-E-L-L. Jika
struktur data ini, sebaliknya,

1104
00:51:47,910 --> 00:51:51,830
jika N adalah satu juta, jika ada
juta nama dalam struktur data ini,

1105
00:51:51,830 --> 00:51:57,100
Maxwell masih akan menjadi
ditemui selepas 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 David-- D-A-V-I-D langkah.

1108
00:52:01,276 --> 00:52:03,400
Dengan kata lain, dengan membina
struktur data itu

1109
00:52:03,400 --> 00:52:07,240
mendapat semua array ini, semua yang
diri mereka menyokong capaian rawak,

1110
00:52:07,240 --> 00:52:11,090
Saya boleh mula melihat ke atas rakyat
menamakan menggunakan jumlah masa itulah

1111
00:52:11,090 --> 00:52:14,340
berkadar dengan tidak jumlah
perkara dalam struktur data,

1112
00:52:14,340 --> 00:52:16,330
seperti satu juta nama yang sedia ada.

1113
00:52:16,330 --> 00:52:20,135
Jumlah masa yang diperlukan saya untuk mencari
M-A-X-W-E-L-L dalam struktur data ini adalah

1114
00:52:20,135 --> 00:52:22,260
berkadar tidak kepada
saiz 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 realistik yang
nama-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 mempunyai ciri-ciri 10
nama, 20 nama watak.

1119
00:52:32,600 --> 00:52:33,900
Ia sudah tentu terhad, bukan?

1120
00:52:33,900 --> 00:52:37,110
Terdapat manusia di Bumi yang
mempunyai nama yang paling lama mungkin,

1121
00:52:37,110 --> 00:52:39,920
tetapi nama itu adalah pemalar
panjang nilai, bukan?

1122
00:52:39,920 --> 00:52:41,980
Ia tidak berbeza dari segi akal.

1123
00:52:41,980 --> 00:52:45,090
Jadi dengan cara ini, kami telah
mencapai struktur data

1124
00:52:45,090 --> 00:52:47,800
iaitu masa yang berterusan melihat-up.

1125
00:52:47,800 --> 00:52:50,670
Ia mengambil beberapa langkah
bergantung kepada tempoh input,

1126
00:52:50,670 --> 00:52:54,250
tetapi bukan bilangan nama
dalam struktur data.

1127
00:52:54,250 --> 00:52:58,700
Jadi, jika kita menggandakan jumlah nama
tahun depan daripada satu bilion dua bilion,

1128
00:52:58,700 --> 00:53:03,720
Penemuan Maxwell akan mengambil
nombor yang sama dalam tujuh langkah

1129
00:53:03,720 --> 00:53:04,650
untuk mencari beliau.

1130
00:53:04,650 --> 00:53:08,810
Dan dengan itu kita seolah-olah telah dicapai
kaedah berpotensi suci kita masa berjalan.

1131
00:53:08,810 --> 00:53:10,860
>> Jadi beberapa pengumuman yang cepat.

1132
00:53:10,860 --> 00:53:11,850
Kuiz sifar akan datang.

1133
00:53:11,850 --> 00:53:14,600
Lebih kepada yang di laman web kursus ini
sejak beberapa hari akan datang.

1134
00:53:14,600 --> 00:53:17,120
Isnin lecture-- itu bercuti
di sini di Harvard pada hari Isnin.

1135
00:53:17,120 --> 00:53:18,850
Ia bukan di New Haven,
jadi kami mengambil kelas

1136
00:53:18,850 --> 00:53:20,310
untuk Haven baru untuk kuliah pada hari Isnin.

1137
00:53:20,310 --> 00:53:22,550
Semuanya akan difilemkan
dan secara langsung seperti biasa,

1138
00:53:22,550 --> 00:53:24,900
tetapi mari kita berakhir hari ini
dengan klip 30 saat

1139
00:53:24,900 --> 00:53:26,910
dipanggil "Pemikiran Deep"
oleh Daven Farnham, yang

1140
00:53:26,910 --> 00:53:30,850
telah diilhamkan tahun lalu oleh Sabtu
Night Live "Pemikiran Deep"

1141
00:53:30,850 --> 00:53:35,700
oleh Jack Handy, yang
kini perlu masuk akal.

1142
00:53:35,700 --> 00:53:38,810
>> FILEM: Dan kini, "Deep
Pemikiran "oleh Daven Farnham.

1143
00:53:38,810 --> 00:53:42,100

1144
00:53:42,100 --> 00:53:42,870
Jadual hash.

1145
00:53:42,870 --> 00:53:45,940

1146
00:53:45,940 --> 00:53:47,660
>> SPEAKER 1: Baiklah, itu sahaja buat masa ini.

1147
00:53:47,660 --> 00:53:48,805
Kita akan melihat lagi minggu depan.

1148
00:53:48,805 --> 00:53:55,380

1149
00:53:55,380 --> 00:53:56,680
>> DOUG: Untuk melihat ia dalam tindakan.

1150
00:53:56,680 --> 00:53:58,304
Oleh itu, mari kita lihat pada yang sekarang.

1151
00:53:58,304 --> 00:53:59,890
Jadi di sini, kita mempunyai pelbagai terisih.

1152
00:53:59,890 --> 00:54:04,860
>> IAN: Doug, boleh anda pergi ke hadapan dan mulakan semula
ini kerana hanya satu saat, sila.

1153
00:54:04,860 --> 00:54:08,562
Baiklah, kamera rolling, supaya
tindakan apabila anda sudah bersedia, Doug, OK?

1154
00:54:08,562 --> 00:54:11,020
DOUG: Baiklah, jadi apa yang kita
ada di sini adalah pelbagai terisih.

1155
00:54:11,020 --> 00:54:13,960
Dan saya telah berwarna semua unsur-unsur
merah untuk menunjukkan bahawa ia adalah, sebenarnya,

1156
00:54:13,960 --> 00:54:14,460
Unsorted.

1157
00:54:14,460 --> 00:54:17,960
Jadi ingat bahawa perkara pertama yang kami lakukan
adalah kita menyusun separuh meninggalkan array.

1158
00:54:17,960 --> 00:54:20,630
Kemudian kami menyusun kanan
separuh daripada array.

1159
00:54:20,630 --> 00:54:22,830
Dan ya-da, ya-da, ya-da,
kita menggabungkan mereka bersama-sama.

1160
00:54:22,830 --> 00:54:24,520
Dan kita mempunyai keselesaan dan kemudahan sepenuhnya disusun.

1161
00:54:24,520 --> 00:54:25,360
Jadi itulah bagaimana bergabung apapun berfungsi.

1162
00:54:25,360 --> 00:54:27,109
>> IAN: Wah, wah, wah,
potong, potong, potong, dipotong.

1163
00:54:27,109 --> 00:54:30,130
Doug, anda tidak boleh hanya ya-da, ya-da,
ya-da, jalan anda melalui jenis merge.

1164
00:54:30,130 --> 00:54:31,970
>> DOUG: Saya hanya lakukan.

1165
00:54:31,970 --> 00:54:32,832
Tidak mengapa.

1166
00:54:32,832 --> 00:54:33,540
Kita baik untuk pergi.

1167
00:54:33,540 --> 00:54:34,760
Mari kita hanya menyimpan rolling.

1168
00:54:34,760 --> 00:54:35,380
Jadi anyway,

1169
00:54:35,380 --> 00:54:37,800
>> IAN: Anda perlu menjelaskan
ia lebih sempurna daripada itu.

1170
00:54:37,800 --> 00:54:39,999
Itu hanya tidak cukup.

1171
00:54:39,999 --> 00:54:41,790
DOUG: Ian, kita tidak
perlu kembali kepada satu.

1172
00:54:41,790 --> 00:54:42,350
Tidak mengapa.

1173
00:54:42,350 --> 00:54:45,690
Jadi anyway, jika kita terus dengan merge--
Ian, kami di pertengahan penggambaran.

1174
00:54:45,690 --> 00:54:46,612
>> IAN: Saya tahu.

1175
00:54:46,612 --> 00:54:49,320
Dan kita tidak boleh hanya ya-da, ya-da,
ya-da, melalui proses keseluruhan.

1176
00:54:49,320 --> 00:54:52,200
Anda perlu menjelaskan bagaimana
kedua-dua pihak mendapat digabungkan bersama-sama.

1177
00:54:52,200 --> 00:54:53,570
>> DOUG: Tetapi kami telah pun
menjelaskan bagaimana sides-- dua

1178
00:54:53,570 --> 00:54:55,321
>> IAN: Anda baru sahaja ditunjukkan
mereka pelbagai merge.

1179
00:54:55,321 --> 00:54:56,486
DOUG: Mereka tahu proses.

1180
00:54:56,486 --> 00:54:57,172
Mereka halus.

1181
00:54:57,172 --> 00:54:58,380
Kami telah pergi ke atasnya sepuluh kali.

1182
00:54:58,380 --> 00:55:00,330
>> IAN: Anda hanya dilangkau hak ke atasnya.

1183
00:55:00,330 --> 00:55:03,360
Kita akan kembali kepada salah satu, anda
tidak boleh anda ya-da, ya-da ke atasnya.

1184
00:55:03,360 --> 00:55:05,480
Baiklah, kembali kepada satu.

1185
00:55:05,480 --> 00:55:07,833
>> DOUG: Saya perlu kembali
melalui semua slaid?

1186
00:55:07,833 --> 00:55:08,332
Tuhan saya.

1187
00:55:08,332 --> 00:55:11,008

1188
00:55:11,008 --> 00:55:13,004
Ia seperti kali keenam, Ian.

1189
00:55:13,004 --> 00:55:13,940
Tidak mengapa.

1190
00:55:13,940 --> 00:55:15,200
>> IAN: Baiklah.

1191
00:55:15,200 --> 00:55:16,590
Anda bersedia?

1192
00:55:16,590 --> 00:55:17,400
Yang besar.

1193
00:55:17,400 --> 00:55:18,950
Tindakan.