1
00:00:00,000 --> 00:00:03,423
>> [MUSIC PLAYING]

2
00:00:03,423 --> 00:00:05,380

3
00:00:05,380 --> 00:00:08,210
>> ANDI PENG: Selamat Datang di minggu 6 bagian.

4
00:00:08,210 --> 00:00:11,620
Kami menyimpang dari standar kami
Bagian waktu Selasa

5
00:00:11,620 --> 00:00:14,130
sore hingga Minggu pagi yang indah ini.

6
00:00:14,130 --> 00:00:17,330
Terima kasih untuk semua orang yang
bergabung dengan saya hari ini, tapi serius,

7
00:00:17,330 --> 00:00:18,170
tepuk tangan.

8
00:00:18,170 --> 00:00:20,600
>> Itu upaya yang cukup besar.

9
00:00:20,600 --> 00:00:23,600
Aku hampir tidak bahkan membuatnya
dalam waktu, tetapi itu OK.

10
00:00:23,600 --> 00:00:27,520
Jadi saya tahu bahwa kalian semua
telah membuat untuk kuis.

11
00:00:27,520 --> 00:00:30,370
Pertama-tama, selamat datang untuk
sisi lain dari itu.

12
00:00:30,370 --> 00:00:32,917
>> Kedua, kita akan berbicara tentang hal itu.

13
00:00:32,917 --> 00:00:34,000
Kita akan berbicara tentang kuis.

14
00:00:34,000 --> 00:00:35,700
Kami akan berbicara tentang bagaimana
Anda lakukan di kelas.

15
00:00:35,700 --> 00:00:36,550
Kamu akan baik-baik saja.

16
00:00:36,550 --> 00:00:39,080
Saya memiliki kuis Anda untuk
Anda di akhir di sini,

17
00:00:39,080 --> 00:00:42,120
jadi jika kalian ingin mengambil
a melihat itu, benar-benar baik-baik saja.

18
00:00:42,120 --> 00:00:46,590
>> Begitu cepat sebelum kita mulai, yang
agenda hari ini adalah sebagai berikut.

19
00:00:46,590 --> 00:00:48,430
Seperti yang Anda lihat, kami
tembak pada dasarnya cepat

20
00:00:48,430 --> 00:00:52,120
melalui sejumlah besar struktur data
benar-benar, benar-benar, benar-benar cepat.

21
00:00:52,120 --> 00:00:54,380
Jadi dengan demikian, itu tidak akan
hari ini yang super interaktif.

22
00:00:54,380 --> 00:00:59,620
Itu hanya akan saya semacam berteriak
hal-hal yang Anda, dan jika aku membingungkan Anda,

23
00:00:59,620 --> 00:01:02,680
jika aku akan terlalu cepat, beritahu saya.

24
00:01:02,680 --> 00:01:05,200
Mereka hanya berbagai data
struktur, dan sebagai bagian

25
00:01:05,200 --> 00:01:07,070
dari pset Anda untuk ini
Minggu mendatang, Anda akan

26
00:01:07,070 --> 00:01:10,340
diminta untuk melaksanakan salah satu dari mereka,
mungkin dua dari them-- dua dari mereka

27
00:01:10,340 --> 00:01:12,319
di pset Anda.

28
00:01:12,319 --> 00:01:14,610
OK, jadi aku hanya akan
mulai dengan beberapa pengumuman.

29
00:01:14,610 --> 00:01:19,070
Kami akan pergi ke tumpukan dan antrian lebih
mendalam dari apa yang kita lakukan sebelumnya kuis.

30
00:01:19,070 --> 00:01:20,990
Kami akan pergi ke terkait
daftar lagi, sekali lagi,

31
00:01:20,990 --> 00:01:23,899
lebih mendalam dari apa
kami memiliki sebelum kuis.

32
00:01:23,899 --> 00:01:26,440
Dan kemudian kita akan berbicara tentang hash
tabel, pohon dan mencoba, yang

33
00:01:26,440 --> 00:01:28,890
semua cukup diperlukan untuk pset Anda.

34
00:01:28,890 --> 00:01:32,925
Dan kemudian kita akan membahas beberapa
tips-tips untuk pset5.

35
00:01:32,925 --> 00:01:37,360
>> OK, jadi kuis 0.

36
00:01:37,360 --> 00:01:41,090
Rata-rata adalah 58%.

37
00:01:41,090 --> 00:01:45,370
Itu sangat rendah, sehingga kalian semua
melakukan sangat, sangat baik sesuai

38
00:01:45,370 --> 00:01:46,510
dengan.

39
00:01:46,510 --> 00:01:49,970
>> Cukup banyak, aturan praktis adalah jika Anda
dalam standar deviasi dari mean

40
00:01:49,970 --> 00:01:52,990
terutama karena kita berada dalam kurang
Bagian yang nyaman, Anda benar-benar baik-baik saja.

41
00:01:52,990 --> 00:01:54,120
Anda berada di jalur.

42
00:01:54,120 --> 00:01:55,190
Hidup adalah baik.

43
00:01:55,190 --> 00:01:58,952
>> Aku tahu itu menakutkan untuk berpikir bahwa
Aku punya seperti 40% pada kuis ini.

44
00:01:58,952 --> 00:02:00,160
Aku akan gagal kelas ini.

45
00:02:00,160 --> 00:02:02,243
Aku berjanji, Anda tidak
akan gagal kelas.

46
00:02:02,243 --> 00:02:03,680
Anda benar-benar baik-baik saja.

47
00:02:03,680 --> 00:02:06,850
>> Bagi Anda yang punya lebih dari
mean, mengesankan, mengesankan,

48
00:02:06,850 --> 00:02:08,780
seperti, serius dilakukan dengan baik.

49
00:02:08,780 --> 00:02:09,689
Saya memiliki mereka dengan saya.

50
00:02:09,689 --> 00:02:11,730
Jangan ragu untuk datang mendapatkan mereka
pada akhir bagian.

51
00:02:11,730 --> 00:02:14,520
Let me know jika Anda memiliki
masalah, pertanyaan dengan mereka.

52
00:02:14,520 --> 00:02:17,204
Jika kita menambahkan nilai Anda
salah, beritahu kami.

53
00:02:17,204 --> 00:02:21,240
>> OK, jadi pset5, ini adalah benar-benar
Minggu aneh untuk Yale dalam arti

54
00:02:21,240 --> 00:02:24,240
yang pset kami adalah karena
Rabu siang termasuk

55
00:02:24,240 --> 00:02:27,317
hari akhir, sehingga benar-benar
secara teoritis karena Selasa siang.

56
00:02:27,317 --> 00:02:29,150
Mungkin tidak ada yang selesai
di Selasa siang.

57
00:02:29,150 --> 00:02:30,830
Itu benar-benar baik-baik saja.

58
00:02:30,830 --> 00:02:33,700
Kita akan memiliki jam kantor
malam serta Senin malam.

59
00:02:33,700 --> 00:02:36,810
Dan semua bagian ini akan minggu
benar-benar akan berubah menjadi lokakarya,

60
00:02:36,810 --> 00:02:38,800
sehingga merasa bebas untuk pop
setiap bagian yang Anda inginkan,

61
00:02:38,800 --> 00:02:42,810
dan mereka akan menjadi semacam mini-pset
lokakarya untuk bantuan itu.

62
00:02:42,810 --> 00:02:45,620
Jadi dengan demikian, ini adalah satu-satunya bagian
di mana kita mengajar materi.

63
00:02:45,620 --> 00:02:49,220
Semua bagian lainnya akan memfokuskan
eksklusif pada bantuan untuk pset tersebut.

64
00:02:49,220 --> 00:02:50,146
Ya?

65
00:02:50,146 --> 00:02:52,000
>> AUDIENCE: Dimana jam kantor?

66
00:02:52,000 --> 00:02:56,120
>> ANDI PENG: jam Office
tonight-- oh, pertanyaan yang bagus.

67
00:02:56,120 --> 00:03:00,580
Saya pikir malam ini jam kantor
berada di Teal atau Commons.

68
00:03:00,580 --> 00:03:02,984
Jika Anda memeriksa CS50 secara online
dan Anda pergi ke jam kantor,

69
00:03:02,984 --> 00:03:05,650
harus ada jadwal yang
memberitahu Anda di mana semua dari mereka adalah.

70
00:03:05,650 --> 00:03:07,954
>> Saya tahu baik malam ini
atau besok adalah teal,

71
00:03:07,954 --> 00:03:10,120
dan saya pikir kita mungkin memiliki
commons untuk malam.

72
00:03:10,120 --> 00:03:11,020
Aku tidak yakin.

73
00:03:11,020 --> 00:03:11,700
Pertanyaan bagus.

74
00:03:11,700 --> 00:03:14,430
Memeriksa CS50.

75
00:03:14,430 --> 00:03:18,780
>> Keren, pertanyaan tentang
Jadwal untuk selanjutnya seperti tiga hari?

76
00:03:18,780 --> 00:03:21,690
Aku berjanji kalian seperti David
mengatakan, ini adalah puncak bukit.

77
00:03:21,690 --> 00:03:23,050
Kalian hampir ada.

78
00:03:23,050 --> 00:03:24,644
Hanya tiga hari lagi.

79
00:03:24,644 --> 00:03:26,310
Sampai di sana, dan kemudian kita semua akan turun.

80
00:03:26,310 --> 00:03:28,114
Kami akan memiliki baik istirahat CS-bebas.

81
00:03:28,114 --> 00:03:28,780
Selamat Datang kembali.

82
00:03:28,780 --> 00:03:30,779
Kami akan menyelam ke web
pemrograman dan pengembangan,

83
00:03:30,779 --> 00:03:35,150
hal-hal yang sangat menyenangkan dibandingkan
untuk beberapa psets lainnya.

84
00:03:35,150 --> 00:03:37,974
Dan itu akan menjadi dingin, dan
kita akan memiliki banyak bersenang-senang.

85
00:03:37,974 --> 00:03:38,890
Kami akan memiliki lebih banyak permen.

86
00:03:38,890 --> 00:03:39,730
Maaf untuk permen.

87
00:03:39,730 --> 00:03:40,945
Saya lupa permen.

88
00:03:40,945 --> 00:03:43,310
Pagi itu kasar.

89
00:03:43,310 --> 00:03:46,340
Jadi kalian hampir di sana,
dan aku benar-benar bangga kalian.

90
00:03:46,340 --> 00:03:49,570
>> OK, jadi tumpukan.

91
00:03:49,570 --> 00:03:53,331
Yang mencintai pertanyaan tentang Jack
dan pakaiannya di kuis?

92
00:03:53,331 --> 00:03:53,830
Tak seorangpun?

93
00:03:53,830 --> 00:03:56,500
Baiklah tidak apa apa.

94
00:03:56,500 --> 00:04:00,200
>> Jadi pada dasarnya yang Anda bisa
gambar Jack, orang ini di sini,

95
00:04:00,200 --> 00:04:03,350
mencintai untuk mengambil pakaian
dari puncak stack,

96
00:04:03,350 --> 00:04:05,750
dan ia menempatkan kembali ke
tumpukan setelah dia lakukan.

97
00:04:05,750 --> 00:04:07,600
Jadi dengan cara ini, dia tidak pernah
tampaknya akan semakin

98
00:04:07,600 --> 00:04:10,090
ke bawah
tumpukan di pakaiannya.

99
00:04:10,090 --> 00:04:12,600
Jadi ini semacam menggambarkan
struktur data dasar

100
00:04:12,600 --> 00:04:16,610
bagaimana stack diimplementasikan.

101
00:04:16,610 --> 00:04:20,060
>> Pada dasarnya, memikirkan
tumpukan sebagai salah tumpukan benda

102
00:04:20,060 --> 00:04:24,900
di mana Anda meletakkan segala sesuatu ke atas, dan
maka Anda pop mereka keluar dari atas.

103
00:04:24,900 --> 00:04:28,600
Jadi LIFO adalah singkatan kita suka
untuk use-- terakhir Dalam, First Out.

104
00:04:28,600 --> 00:04:32,480
Dan terakhir ke atas
stack adalah yang pertama yang keluar.

105
00:04:32,480 --> 00:04:34,260
Dan dua istilah
kami ingin mengasosiasikan

106
00:04:34,260 --> 00:04:36,190
dengan yang disebut push dan pop.

107
00:04:36,190 --> 00:04:39,790
Ketika Anda mendorong sesuatu ke
stack, dan Anda pop itu kembali.

108
00:04:39,790 --> 00:04:43,422
>> Dan jadi saya kira ini adalah jenis
konsep abstrak bagi anda

109
00:04:43,422 --> 00:04:45,630
yang ingin melihat seperti
implementasi aktual ini

110
00:04:45,630 --> 00:04:46,740
di dunia nyata.

111
00:04:46,740 --> 00:04:50,170
Berapa banyak dari Anda telah menulis sebuah esai
mungkin seperti satu jam sebelum itu karena,

112
00:04:50,170 --> 00:04:54,510
dan Anda tidak sengaja menghapus besar
sepotong itu, seperti sengaja?

113
00:04:54,510 --> 00:04:58,560
Dan kemudian apa yang kontrol dilakukan
kita gunakan untuk menempatkan kembali?

114
00:04:58,560 --> 00:05:00,030
Control-Z, ya?

115
00:05:00,030 --> 00:05:03,640
Control-Z, sehingga jumlah kali
bahwa Control-Z telah menyelamatkan hidup saya,

116
00:05:03,640 --> 00:05:08,820
telah menyelamatkan pantatku, setiap kali
yang dilaksanakan melalui stack.

117
00:05:08,820 --> 00:05:13,020
>> Dasarnya semua informasi
yang ada di dokumen Word Anda,

118
00:05:13,020 --> 00:05:15,080
itu akan mendorong dan muncul di akan.

119
00:05:15,080 --> 00:05:19,460
Dan pada dasarnya setiap kali Anda
menghapus apapun, Anda pop itu kembali.

120
00:05:19,460 --> 00:05:22,820
Dan kemudian jika Anda membutuhkannya kembali, Anda
dorong, yang adalah apa Control-C tidak.

121
00:05:22,820 --> 00:05:26,770
Dan fungsi dunia begitu nyata
dari struktur data cara sederhana

122
00:05:26,770 --> 00:05:28,690
dapat membantu dengan kehidupan sehari-hari Anda.

123
00:05:28,690 --> 00:05:31,710

124
00:05:31,710 --> 00:05:40,150
>> Jadi struct adalah cara yang
kita benar-benar membuat stack.

125
00:05:40,150 --> 00:05:44,720
Kita ketik mendefinisikan struct, dan kemudian
kita menyebutnya tumpukan di bagian bawah.

126
00:05:44,720 --> 00:05:47,440
Dan dalam stack,
kita memiliki dua parameter

127
00:05:47,440 --> 00:05:51,580
bahwa kita pada dasarnya dapat memanipulasi,
jadi kita harus arang kapasitas bintang string.

128
00:05:51,580 --> 00:05:55,150
>> Semua yang melakukan
adalah menciptakan sebuah array

129
00:05:55,150 --> 00:05:58,835
bahwa kita dapat menyimpan apapun yang Anda inginkan
yang kita dapat menentukan kapasitasnya.

130
00:05:58,835 --> 00:06:01,990
Kapasitas Apakah hanya jumlah maksimum
barang yang kami dapat dimasukkan ke dalam array ini.

131
00:06:01,990 --> 00:06:05,660
ukuran int adalah counter yang terus
melacak berapa banyak item yang saat ini

132
00:06:05,660 --> 00:06:07,850
dalam tumpukan.

133
00:06:07,850 --> 00:06:11,860
Jadi kita bisa melacak, A,
kedua seberapa besar tumpukan sebenarnya,

134
00:06:11,860 --> 00:06:14,850
dan, B, berapa banyak tumpukan yang
kami diisi karena kita tidak ingin

135
00:06:14,850 --> 00:06:18,800
meluap atas apa kapasitas kami adalah.

136
00:06:18,800 --> 00:06:24,340
>> Jadi misalnya, ini indah
pertanyaan pada kuis Anda.

137
00:06:24,340 --> 00:06:28,160
Pada dasarnya bagaimana kita mendorong
ke atas tumpukan.

138
00:06:28,160 --> 00:06:28,830
Cukup sederhana.

139
00:06:28,830 --> 00:06:30,621
Jika Anda melihat itu,
kita akan berjalan melalui ini.

140
00:06:30,621 --> 00:06:32,640
Jika [tidak terdengar] size--
ingat, setiap kali Anda

141
00:06:32,640 --> 00:06:35,300
ingin mengakses
parameter dalam struct,

142
00:06:35,300 --> 00:06:40,320
Anda nama struct.parameter tersebut.

143
00:06:40,320 --> 00:06:42,720
>> Dalam hal ini, s adalah
nama tumpukan kami.

144
00:06:42,720 --> 00:06:46,230
Kami ingin mengakses ukuran
itu, jadi kami lakukan s.size.

145
00:06:46,230 --> 00:06:50,280
Jadi selama ukuran tidak
sama dengan kapasitas atau selama

146
00:06:50,280 --> 00:06:52,940
seperti itu kurang dari kapasitas,
baik akan bekerja di sini.

147
00:06:52,940 --> 00:06:57,180
>> Anda ingin mengakses dalam
tumpukan Anda, sehingga s.strings,

148
00:06:57,180 --> 00:07:00,790
dan Anda akan menempatkan bahwa nomor baru
bahwa Anda ingin masukkan ke sana.

149
00:07:00,790 --> 00:07:05,030
Anggap saja kita akan ingin
masukkan int n ke stack,

150
00:07:05,030 --> 00:07:08,905
kita bisa melakukan s.strings,
kurung, s.size sama n.

151
00:07:08,905 --> 00:07:11,030
Karena ukuran adalah di mana kita
saat ini berada di stack

152
00:07:11,030 --> 00:07:14,590
jika kita akan mendorong
itu, kita hanya mengakses

153
00:07:14,590 --> 00:07:17,370
dimanapun ukuran adalah,
kepenuhan saat stack,

154
00:07:17,370 --> 00:07:21,729
dan kami mendorong int n ke atasnya.

155
00:07:21,729 --> 00:07:24,770
Dan kemudian kami ingin memastikan bahwa
kami juga incrementing ukuran n,

156
00:07:24,770 --> 00:07:27,436
sehingga kami bisa melacak kita sudah
menambahkan hal ekstra untuk stack.

157
00:07:27,436 --> 00:07:29,660
Sekarang kita memiliki ukuran yang lebih besar.

158
00:07:29,660 --> 00:07:33,196
Apakah ini di sini masuk akal untuk
semua orang, bagaimana secara logis kerjanya?

159
00:07:33,196 --> 00:07:34,160
Itu jenis cepat.

160
00:07:34,160 --> 00:07:39,535

161
00:07:39,535 --> 00:07:42,160
AUDIENCE: Dapatkah Anda pergi
yang s.stringss.strings [s.size] lagi?

162
00:07:42,160 --> 00:07:45,808
ANDI PENG: Tentu, jadi apa
s.size saat memberi kita?

163
00:07:45,808 --> 00:07:47,440
AUDIENCE: Ini ukuran saat ini.

164
00:07:47,440 --> 00:07:50,890
ANDI PENG: Tepat, sehingga
Indeks saat ini bahwa ukuran kami di,

165
00:07:50,890 --> 00:07:57,780
dan jadi kami ingin menempatkan integer baru
bahwa kita ingin masukkan ke s.size.

166
00:07:57,780 --> 00:07:58,760
Apakah itu masuk akal?

167
00:07:58,760 --> 00:08:01,110
Karena s.strings, semua yang
adalah adalah nama dari array.

168
00:08:01,110 --> 00:08:03,510
Semua itu adalah mengakses
Array dalam struct kami,

169
00:08:03,510 --> 00:08:06,030
dan jadi jika kita ingin
menempatkan n ke dalam indeks itu,

170
00:08:06,030 --> 00:08:09,651
kita hanya bisa mengaksesnya
menggunakan kurung s.size.

171
00:08:09,651 --> 00:08:10,150
Keren.

172
00:08:10,150 --> 00:08:13,580

173
00:08:13,580 --> 00:08:18,916
>> Baiklah, pop, saya pseudocode itu
untuk kalian, tapi konsep yang sama.

174
00:08:18,916 --> 00:08:19,790
Apakah itu masuk akal?

175
00:08:19,790 --> 00:08:22,310
Jika ukuran lebih besar
dari nol, maka Anda

176
00:08:22,310 --> 00:08:25,350
tahu bahwa Anda ingin mengambil sesuatu
karena jika ukuran tidak

177
00:08:25,350 --> 00:08:27,620
lebih besar dari nol, maka Anda
tidak ada dalam tumpukan.

178
00:08:27,620 --> 00:08:29,840
>> Jadi Anda hanya ingin mengeksekusi
kode ini, hanya bisa

179
00:08:29,840 --> 00:08:32,320
pop jika ada sesuatu untuk pop.

180
00:08:32,320 --> 00:08:35,830
Jadi jika ukuran lebih besar
dari 0, kita dikurangi ukuran.

181
00:08:35,830 --> 00:08:40,020
Kami pengurangan ukuran dan kemudian kembali
apapun yang di dalamnya karena

182
00:08:40,020 --> 00:08:42,710
oleh bermunculan, kita ingin
Akses apapun yang disimpan

183
00:08:42,710 --> 00:08:45,694
dalam indeks dari atas tumpukan.

184
00:08:45,694 --> 00:08:46,610
Semuanya masuk akal?

185
00:08:46,610 --> 00:08:49,693
Jika saya membuat kalian menulis ini keluar,
akan kalian dapat menulis itu?

186
00:08:49,693 --> 00:08:52,029

187
00:08:52,029 --> 00:08:53,570
OK, kalian bisa bermain-main dengan hal itu.

188
00:08:53,570 --> 00:08:55,252
Jangan khawatir jika Anda tidak mendapatkannya.

189
00:08:55,252 --> 00:08:57,460
Kami tidak punya waktu untuk kode
keluar hari ini karena kami sudah

190
00:08:57,460 --> 00:08:59,959
mendapat banyak struktur ini
untuk pergi melalui, tetapi pada dasarnya

191
00:08:59,959 --> 00:09:02,214
pseudocode, sangat, sangat mirip dengan mendorong.

192
00:09:02,214 --> 00:09:03,380
Cukup ikuti bersama logika.

193
00:09:03,380 --> 00:09:06,092
Pastikan Anda mengakses semua
fitur struct Anda benar.

194
00:09:06,092 --> 00:09:06,574
Ya?

195
00:09:06,574 --> 00:09:09,282
>> AUDIENCE: Will slide ini dan
semua ini sampai hari ini-ish?

196
00:09:09,282 --> 00:09:11,586
ANDI PENG: Selalu, yep.

197
00:09:11,586 --> 00:09:13,710
Aku akan mencoba untuk menempatkan
ini seperti satu jam setelah.

198
00:09:13,710 --> 00:09:16,626
Saya akan mengirimkan email David, David akan mencoba untuk
memasangnya seperti satu jam setelah ini.

199
00:09:16,626 --> 00:09:20,040

200
00:09:20,040 --> 00:09:25,470
>> OK, jadi maka kita pindah ke lain ini
struktur data indah yang disebut antrian.

201
00:09:25,470 --> 00:09:30,140
Seperti kalian bisa lihat di sini, sebuah
antrian, untuk Inggris di antara kita,

202
00:09:30,140 --> 00:09:32,010
semua itu adalah garis.

203
00:09:32,010 --> 00:09:34,680
Jadi bertentangan dengan apa
Anda berpikir stack adalah,

204
00:09:34,680 --> 00:09:37,750
antrian adalah apa yang
logis Anda pikirkan.

205
00:09:37,750 --> 00:09:41,914
Ini diselenggarakan oleh aturan FIFO,
yang Pertama Dalam, First Out.

206
00:09:41,914 --> 00:09:43,705
Jika Anda pertama
satu di baris, Anda

207
00:09:43,705 --> 00:09:46,230
yang pertama yang
keluar dari garis.

208
00:09:46,230 --> 00:09:49,680
>> Jadi apa yang kita suka menyebutnya ini
adalah dequeueing dan enqueueing.

209
00:09:49,680 --> 00:09:52,380
Jika kita ingin menambahkan sesuatu
untuk antrian kami, kami enqueue.

210
00:09:52,380 --> 00:09:55,690
Jika kita ingin dequeue, atau mengambil
sesuatu yang jauh, kita dequeue.

211
00:09:55,690 --> 00:10:03,350
>> Akal sehingga sama yang kita jenis
menciptakan elemen berukuran tetap yang kita

212
00:10:03,350 --> 00:10:06,500
dapat menyimpan tertentu
hal, tapi kami juga bisa

213
00:10:06,500 --> 00:10:10,100
mengubah mana kita menempatkan
parameter dalam diri mereka

214
00:10:10,100 --> 00:10:13,140
berdasarkan jenis
fungsi yang kita inginkan.

215
00:10:13,140 --> 00:10:16,700
Jadi tumpukan, kami ingin yang terakhir
satu, N menjadi yang pertama keluar.

216
00:10:16,700 --> 00:10:19,800
Antrian adalah kami ingin hal pertama
untuk menjadi hal pertama keluar.

217
00:10:19,800 --> 00:10:22,510

218
00:10:22,510 --> 00:10:26,710
>> Jadi struct-jenis
mendefinisikan, seperti yang Anda lihat,

219
00:10:26,710 --> 00:10:29,470
itu sedikit berbeda
dari apa stack adalah

220
00:10:29,470 --> 00:10:33,120
karena kita tidak hanya harus terus
melacak di mana ukuran saat ini,

221
00:10:33,120 --> 00:10:37,420
kami juga ingin melacak kepala
serta di mana saat ini kita berada.

222
00:10:37,420 --> 00:10:39,580
Jadi saya pikir itu lebih mudah
jika saya menggambar hal ini.

223
00:10:39,580 --> 00:10:53,270
Jadi mari kita bayangkan kita punya antrian,
jadi mari kita katakan kepala ada di sini.

224
00:10:53,270 --> 00:10:55,811

225
00:10:55,811 --> 00:10:58,310
Kepala garis, mari kita
hanya mengatakan itu saat ini ada,

226
00:10:58,310 --> 00:11:01,809
dan kami ingin memasukkan
sesuatu ke dalam antrian.

227
00:11:01,809 --> 00:11:04,350
Aku akan memanggil ukuran dasarnya
adalah hal yang sama seperti ekor,

228
00:11:04,350 --> 00:11:06,314
akhir mana pun antrian Anda.

229
00:11:06,314 --> 00:11:07,730
Mari kita hanya mengatakan ukuran ada di sini.

230
00:11:07,730 --> 00:11:14,380

231
00:11:14,380 --> 00:11:18,400
>> Jadi bagaimana satu feasibly
memasukkan sesuatu ke dalam antrian?

232
00:11:18,400 --> 00:11:21,000

233
00:11:21,000 --> 00:11:24,130
Apa Indeks kita ingin menempatkan
di mana kita ingin memasukkan ke dalam.

234
00:11:24,130 --> 00:11:29,320
Jika ini adalah awal dari Anda
antrian dan ini adalah akhir dari itu

235
00:11:29,320 --> 00:11:31,860
atau ukuran itu, di mana kita
ingin menambahkan objek berikutnya?

236
00:11:31,860 --> 00:11:32,920
>> AUDIENCE: [tidak terdengar]

237
00:11:32,920 --> 00:11:35,920
ANDI PENG: Tepat, Anda ingin menambahkan
itu tergantung pada yang telah ditulis itu.

238
00:11:35,920 --> 00:11:37,840
Entah ini kosong atau yang kosong.

239
00:11:37,840 --> 00:11:42,630
Jadi Anda ingin menambahkan mungkin
di sini karena jika ukuran is--

240
00:11:42,630 --> 00:11:50,540
jika ini semua penuh, Anda ingin
menambahkannya di sini, kan?

241
00:11:50,540 --> 00:11:57,150
>> Dan jadi itu, sementara sangat, sangat
sederhana, tidak cukup selalu benar

242
00:11:57,150 --> 00:12:00,690
karena perbedaan utama
antara antrian dan tumpukan

243
00:12:00,690 --> 00:12:04,350
adalah bahwa antrian bisa
sebenarnya dimanipulasi

244
00:12:04,350 --> 00:12:06,980
sehingga perubahan kepala
tergantung di mana Anda ingin

245
00:12:06,980 --> 00:12:08,650
awal isyarat Anda untuk memulai.

246
00:12:08,650 --> 00:12:11,900
Dan sebagai hasilnya, ekor Anda
juga akan berubah.

247
00:12:11,900 --> 00:12:14,770
Dan lihatlah
Kode ini sekarang.

248
00:12:14,770 --> 00:12:18,620
Seperti kalian juga diminta untuk
menulis pada kuis, enqueue.

249
00:12:18,620 --> 00:12:22,580
Mungkin kita akan berbicara melalui mengapa
jawabannya adalah apa itu.

250
00:12:22,580 --> 00:12:26,790
>> Saya tidak bisa cukup sesuai baris ini pada satu,
tapi pada dasarnya ini bagian dari kode

251
00:12:26,790 --> 00:12:29,030
harus pada satu baris.

252
00:12:29,030 --> 00:12:30,140
Menghabiskan seperti 30 detik.

253
00:12:30,140 --> 00:12:33,000
Coba lihat, dan melihat mengapa
ini adalah cara yang itu.

254
00:12:33,000 --> 00:12:50,030

255
00:12:50,030 --> 00:12:55,420
>> Sangat, struct sangat mirip, sangat, sangat
struktur yang sama seperti sebelumnya

256
00:12:55,420 --> 00:12:58,090
tumpukan kecuali mungkin
satu baris kode.

257
00:12:58,090 --> 00:13:01,190
Dan bahwa satu baris kode
menentukan fungsi tersebut.

258
00:13:01,190 --> 00:13:03,900
Dan itu benar-benar membedakan
antrian dari tumpukan.

259
00:13:03,900 --> 00:13:18,510

260
00:13:18,510 --> 00:13:22,010
>> Siapapun ingin mengambil bacokan
di menjelaskan mengapa Anda sudah

261
00:13:22,010 --> 00:13:24,980
mendapat hal ini rumit di sini?

262
00:13:24,980 --> 00:13:27,845
Kita melihat kembalinya kami
indah teman modulus.

263
00:13:27,845 --> 00:13:31,020
Seperti kalian akan segera datang
untuk mengenali dalam pemrograman,

264
00:13:31,020 --> 00:13:34,910
hampir kapan saja Anda perlu sesuatu
untuk membungkus sesuatu,

265
00:13:34,910 --> 00:13:36,850
modulus akan menjadi cara untuk melakukannya.

266
00:13:36,850 --> 00:13:40,510
Jadi mengetahui bahwa, apakah ada yang ingin
mencoba menjelaskan bahwa baris kode?

267
00:13:40,510 --> 00:13:44,060

268
00:13:44,060 --> 00:13:47,507
Ya, semua jawaban yang
diterima dan diterima.

269
00:13:47,507 --> 00:13:48,840
AUDIENCE: Apakah Anda berbicara dengan saya?

270
00:13:48,840 --> 00:13:49,506
ANDI PENG: Ya.

271
00:13:49,506 --> 00:13:56,200
AUDIENCE: Oh, tidak menyesal.

272
00:13:56,200 --> 00:14:00,250
ANDI PENG: OK, jadi mari kita
berjalan melalui kode ini.

273
00:14:00,250 --> 00:14:03,642
Jadi, ketika Anda mencoba untuk
menambahkan sesuatu ke antrian,

274
00:14:03,642 --> 00:14:08,510
dalam kasus indah yang kepala terjadi
menjadi di sini, itu sangat mudah bagi kita

275
00:14:08,510 --> 00:14:10,960
untuk hanya pergi ke akhir
memasukkan sesuatu, kan?

276
00:14:10,960 --> 00:14:14,690
Tapi seluruh titik antrian adalah
bahwa kepala benar-benar dapat dinamis

277
00:14:14,690 --> 00:14:17,280
berubah tergantung pada di mana kita
ingin awal q kami untuk menjadi,

278
00:14:17,280 --> 00:14:19,880
dan dengan demikian, ekor
juga akan berubah.

279
00:14:19,880 --> 00:14:31,100
>> Dan membayangkan bahwa ini bukan
antrian, melainkan ini adalah antrian.

280
00:14:31,100 --> 00:14:37,900

281
00:14:37,900 --> 00:14:39,330
Katakanlah kepala ada di sini.

282
00:14:39,330 --> 00:14:54,900

283
00:14:54,900 --> 00:14:56,980
Katakanlah antrian kami tampak seperti ini.

284
00:14:56,980 --> 00:15:00,190
Jika kita ingin menggeser mana
awal garis adalah,

285
00:15:00,190 --> 00:15:03,400
katakanlah kita bergeser kepala
cara ini dan ukuran di sini.

286
00:15:03,400 --> 00:15:07,100
>> Sekarang kita ingin menambahkan sesuatu untuk
antrian ini, tetapi sebagai kalian bisa lihat,

287
00:15:07,100 --> 00:15:11,150
itu tidak begitu sederhana seperti hanya
menambahkan apa pun adalah setelah ukuran

288
00:15:11,150 --> 00:15:13,630
karena dengan begitu kita kehabisan
batas-batas array kita yang sebenarnya.

289
00:15:13,630 --> 00:15:16,190
Di mana kita ingin benar-benar menambah sini.

290
00:15:16,190 --> 00:15:18,610
Itulah keindahan antrian
adalah bahwa untuk kita, visual itu

291
00:15:18,610 --> 00:15:22,380
Sepertinya garis berjalan seperti ini,
tetapi ketika disimpan dalam struktur data,

292
00:15:22,380 --> 00:15:29,370
mereka memberikan sebagai seperti siklus.

293
00:15:29,370 --> 00:15:32,360
Ini semacam membungkus di sekitar
ke depan dengan cara yang sama

294
00:15:32,360 --> 00:15:34,780
bahwa garis juga bisa membungkus
sekitar tergantung pada di mana pun Anda

295
00:15:34,780 --> 00:15:36,279
ingin awal baris untuk menjadi.

296
00:15:36,279 --> 00:15:38,630
Dan jika kita mengambil
melihat ke bawah sini, mari kita

297
00:15:38,630 --> 00:15:40,880
mengatakan kami ingin membuat
fungsi yang disebut enqueue.

298
00:15:40,880 --> 00:15:43,980
Kami ingin menambahkan int n ke q itu.

299
00:15:43,980 --> 00:15:49,250
Jika q.size q-- kita akan menelepon bahwa data kami
structure-- jika queue.size kami tidak

300
00:15:49,250 --> 00:15:52,520
sama dengan kapasitas atau jika
itu kurang dari kapasitas,

301
00:15:52,520 --> 00:15:55,120
q.strings adalah array dalam q kami.

302
00:15:55,120 --> 00:15:58,380
Kita akan mengatur
yang sama dengan q.heads,

303
00:15:58,380 --> 00:16:02,730
yang ada di sini, ditambah q.size
modulus oleh kapasitas, yang

304
00:16:02,730 --> 00:16:04,290
membungkus kita kembali di sini.

305
00:16:04,290 --> 00:16:08,040
>> Jadi, dalam contoh ini, indeks
kepala adalah 1, kan?

306
00:16:08,040 --> 00:16:11,480
Indeks ukuran 0, 1, 2, 3, 4.

307
00:16:11,480 --> 00:16:19,500
Jadi kita bisa melakukan 1 ditambah 4 modulus
oleh kemampuan kita yang 5.

308
00:16:19,500 --> 00:16:20,920
Apa yang memberi kita?

309
00:16:20,920 --> 00:16:23,270
Apa indeks yang
keluar dari ini?

310
00:16:23,270 --> 00:16:24,080
>> AUDIENCE: 0.

311
00:16:24,080 --> 00:16:27,870
>> ANDI PENG: 0, yang
kebetulan di sini,

312
00:16:27,870 --> 00:16:30,640
dan jadi kami ingin dapat
untuk memasukkan ke sini.

313
00:16:30,640 --> 00:16:34,730
Dan persamaan ini di sini jenis
hanya bekerja dengan angka apapun

314
00:16:34,730 --> 00:16:36,750
tergantung di mana Anda
kepala dan ukuran Anda.

315
00:16:36,750 --> 00:16:38,541
Jika Anda tahu apa yang mereka
hal-hal yang, Anda tahu

316
00:16:38,541 --> 00:16:43,170
persis di mana Anda ingin menyisipkan
apa pun yang setelah antrian Anda.

317
00:16:43,170 --> 00:16:44,640
Apakah itu masuk akal untuk semua orang?

318
00:16:44,640 --> 00:16:48,560
>> Saya tahu jenis otak
teaser terutama karena ini

319
00:16:48,560 --> 00:16:50,512
datang setelah kuis Anda.

320
00:16:50,512 --> 00:16:52,220
Tapi mudah-mudahan semua orang
sekarang dapat memahami

321
00:16:52,220 --> 00:16:57,800
mengapa solusi ini atau ini
Fungsi adalah cara yang itu.

322
00:16:57,800 --> 00:16:59,840
Siapapun agak tidak jelas itu?

323
00:16:59,840 --> 00:17:03,471

324
00:17:03,471 --> 00:17:03,970
OKE.

325
00:17:03,970 --> 00:17:07,109

326
00:17:07,109 --> 00:17:09,970
>> Dan sekarang, jika Anda
ingin dequeue, ini

327
00:17:09,970 --> 00:17:15,240
adalah di mana kepala kita akan menggeser
karena jika kita dequeue,

328
00:17:15,240 --> 00:17:17,030
kita tidak mengambil dari ujung q itu.

329
00:17:17,030 --> 00:17:19,130
Kami ingin melepas kepala, kan?

330
00:17:19,130 --> 00:17:24,260
Jadi sebagai hasilnya, kepala akan berubah,
dan itulah sebabnya ketika Anda enqueue,

331
00:17:24,260 --> 00:17:26,800
Anda harus melacak
di mana kepala Anda dan ukuran Anda

332
00:17:26,800 --> 00:17:29,450
yang dapat memasukkan
ke posisi yang benar.

333
00:17:29,450 --> 00:17:32,740
>> Dan jadi ketika Anda dequeue,
Saya juga pseudocode itu.

334
00:17:32,740 --> 00:17:35,480
Jangan ragu untuk jika Anda ingin
untuk mencoba coding ini.

335
00:17:35,480 --> 00:17:36,980
Anda ingin memindahkan kepala, kan?

336
00:17:36,980 --> 00:17:39,320
Jika saya ingin dequeue, saya
akan memindahkan kepala lebih.

337
00:17:39,320 --> 00:17:40,800
Ini akan menjadi kepala.

338
00:17:40,800 --> 00:17:45,617
>> Dan ukuran kami saat ini akan
kurangi karena kita tidak lagi

339
00:17:45,617 --> 00:17:46,950
memiliki empat elemen dalam array.

340
00:17:46,950 --> 00:17:51,370
Kami hanya memiliki tiga, dan kemudian kita ingin
untuk kembali apa pun yang disimpan di dalam

341
00:17:51,370 --> 00:17:56,260
kepala karena kami ingin mengambil ini
Nilai keluar sehingga sangat mirip dengan stack.

342
00:17:56,260 --> 00:17:58,010
Hanya Anda mengambil
dari tempat yang berbeda,

343
00:17:58,010 --> 00:18:01,770
dan Anda harus menetapkan kembali pointer Anda
ke tempat yang berbeda sebagai hasilnya.

344
00:18:01,770 --> 00:18:03,890
Logikanya, semua orang ikuti?

345
00:18:03,890 --> 00:18:05,690
Besar.

346
00:18:05,690 --> 00:18:10,156
>> OK, jadi kita akan berbicara sedikit
lebih mendalam tentang daftar terkait

347
00:18:10,156 --> 00:18:13,280
karena mereka akan sangat, sangat berharga
untuk Anda dalam perjalanan minggu ini

348
00:18:13,280 --> 00:18:14,964
psets.

349
00:18:14,964 --> 00:18:17,130
Daftar terkait, seperti kalian
ingat, semua mereka

350
00:18:17,130 --> 00:18:22,570
adalah node yang node tertentu
nilai-nilai baik nilai dan pointer

351
00:18:22,570 --> 00:18:26,290
yang dihubungkan bersama
oleh mereka pointer.

352
00:18:26,290 --> 00:18:29,880
Dan struct pada bagaimana
kami membuat simpul di sini adalah kita

353
00:18:29,880 --> 00:18:33,569
memiliki int n, yang adalah apa pun
nilai di toko atau tali n

354
00:18:33,569 --> 00:18:35,610
atau apa pun yang Anda ingin
menyebutnya, n bintang arang.

355
00:18:35,610 --> 00:18:41,482
Struct bintang node, yang merupakan pointer
bahwa Anda ingin memiliki di setiap node,

356
00:18:41,482 --> 00:18:43,690
Anda akan memiliki yang
titik pointer ke arah depan.

357
00:18:43,690 --> 00:18:48,207

358
00:18:48,207 --> 00:18:50,040
Anda akan memiliki kepala
dari linked list yang

359
00:18:50,040 --> 00:18:53,140
akan menunjukkan ke seluruh
nilai-nilai sebagainya dan sebagainya

360
00:18:53,140 --> 00:18:55,290
sampai Anda akhirnya mencapai akhir.

361
00:18:55,290 --> 00:18:58,040
Dan node terakhir ini hanya
akan tidak memiliki pointer.

362
00:18:58,040 --> 00:18:59,952
Ini akan menunjukkan
null, dan saat itulah

363
00:18:59,952 --> 00:19:01,910
Anda tahu Anda telah memukul
akhir daftar Anda terkait

364
00:19:01,910 --> 00:19:04,076
adalah ketika pointer terakhir Anda
tidak menunjuk ke apapun.

365
00:19:04,076 --> 00:19:06,670

366
00:19:06,670 --> 00:19:10,990
>> Jadi kita akan pergi sedikit lebih dalam
mendalam tentang bagaimana seseorang akan mungkin

367
00:19:10,990 --> 00:19:12,400
mencari daftar link.

368
00:19:12,400 --> 00:19:15,460
Ingat apa adalah beberapa
kelemahan dari daftar terkait

369
00:19:15,460 --> 00:19:19,340
ayat array mengenai pencarian.

370
00:19:19,340 --> 00:19:22,565
Array Anda bisa pencarian biner, tapi
mengapa Anda tidak dapat melakukan itu dalam sebuah linked list?

371
00:19:22,565 --> 00:19:26,834

372
00:19:26,834 --> 00:19:30,320
>> AUDIENCE: Karena mereka semua terhubung,
tapi Anda tidak cukup tahu di mana

373
00:19:30,320 --> 00:19:31,330
[Tidak terdengar].

374
00:19:31,330 --> 00:19:34,600
>> ANDI PENG: Ya, persis begitu ingat
bahwa kecemerlangan array

375
00:19:34,600 --> 00:19:37,190
adalah fakta bahwa kami memiliki
random access memory mana

376
00:19:37,190 --> 00:19:41,580
jika saya ingin nilai dari indeks
enam, saya hanya bisa mengatakan indeks enam,

377
00:19:41,580 --> 00:19:42,407
memberikan nilai tersebut.

378
00:19:42,407 --> 00:19:45,240
Dan itu karena array diurutkan
dalam ruang memori yang berdekatan

379
00:19:45,240 --> 00:19:48,020
di satu tempat, sedangkan
jenis daftar terkait

380
00:19:48,020 --> 00:19:52,820
adalah acak diselingi sekitar,
dan satu-satunya cara Anda dapat menemukan satu

381
00:19:52,820 --> 00:19:56,890
adalah melalui pointer yang memberitahu Anda
alamat di mana simpul berikutnya adalah.

382
00:19:56,890 --> 00:20:00,290
>> Dan sebagai hasilnya, satu-satunya cara
untuk mencari melalui linked list

383
00:20:00,290 --> 00:20:01,560
adalah pencarian linear.

384
00:20:01,560 --> 00:20:05,890
Karena saya tidak tahu persis di mana
nilai 12 dalam linked list adalah,

385
00:20:05,890 --> 00:20:08,780
Saya harus melintasi keseluruhan yang
itu terkait daftar satu

386
00:20:08,780 --> 00:20:12,450
oleh salah satu dari kepala ke node pertama,
ke node kedua, ke node ketiga,

387
00:20:12,450 --> 00:20:17,690
semua jalan sampai akhirnya aku mendapatkan
ke tempat yang simpul saya cari adalah.

388
00:20:17,690 --> 00:20:22,110
Dan dalam hal ini, pencarian
pada linked list selalu n.

389
00:20:22,110 --> 00:20:23,040
Itu selalu n.

390
00:20:23,040 --> 00:20:25,690
Itu selalu dalam waktu linier.

391
00:20:25,690 --> 00:20:28,470
>> Dan kode yang
kita melaksanakan ini, dan ini

392
00:20:28,470 --> 00:20:32,620
agak baru untuk kalian karena Anda
orang belum benar-benar berbicara tentang atau pernah

393
00:20:32,620 --> 00:20:35,000
pointer terlihat di cara
mencari melalui pointer,

394
00:20:35,000 --> 00:20:37,670
jadi kita akan berjalan melalui
ini sangat, sangat lambat.

395
00:20:37,670 --> 00:20:40,200
Jadi pencarian bool, tepat,
mari kita bayangkan kita ingin

396
00:20:40,200 --> 00:20:42,820
untuk membuat fungsi yang disebut
pencarian yang mengembalikan benar

397
00:20:42,820 --> 00:20:46,820
jika Anda menemukan nilai dalam terkait
daftar, dan ia mengembalikan palsu sebaliknya.

398
00:20:46,820 --> 00:20:50,030
Daftar bintang node
Saat ini hanya pointer

399
00:20:50,030 --> 00:20:52,960
untuk item pertama dalam daftar Anda terkait.

400
00:20:52,960 --> 00:20:56,700
int n adalah nilai yang Anda
mencari dalam daftar itu.

401
00:20:56,700 --> 00:20:58,770
>> Jadi Bintang simpul pointer sama dengan daftar.

402
00:20:58,770 --> 00:21:00,970
Itu berarti kita sedang menyiapkan
dan menciptakan pointer

403
00:21:00,970 --> 00:21:03,592
untuk yang node pertama dalam daftar.

404
00:21:03,592 --> 00:21:04,300
Semua orang dengan saya?

405
00:21:04,300 --> 00:21:06,530
Jadi jika kita pergi
kembali ke sini, saya akan memiliki

406
00:21:06,530 --> 00:21:13,850
diinisialisasi pointer yang menunjuk ke
kepala dari apa pun daftar itu.

407
00:21:13,850 --> 00:21:18,600
>> Dan kemudian setelah Anda mendapatkan di sini,
sementara pointer tidak nol sama,

408
00:21:18,600 --> 00:21:22,160
sehingga merupakan lingkaran di mana kita
akan kemudian melintasi

409
00:21:22,160 --> 00:21:25,940
sisa daftar kami karena apa
terjadi ketika pointer sama dengan nol?

410
00:21:25,940 --> 00:21:27,550
Kita tahu bahwa kita have--

411
00:21:27,550 --> 00:21:28,450
>> AUDIENCE: [tidak terdengar]

412
00:21:28,450 --> 00:21:31,491
>> ANDI PENG: Tepat, jadi kita tahu bahwa
kita telah mencapai akhir dari daftar, kan?

413
00:21:31,491 --> 00:21:34,470
Jika Anda pergi ke sini, setiap node
harus menunjuk ke node lain

414
00:21:34,470 --> 00:21:36,550
dan sebagainya dan sebagainya
sampai Anda menekan akhirnya

415
00:21:36,550 --> 00:21:41,589
ekor daftar Anda terhubung,
yang memiliki pointer yang hanya

416
00:21:41,589 --> 00:21:43,130
tidak menunjuk mana saja selain tidak ada.

417
00:21:43,130 --> 00:21:47,510
Dan sehingga Anda pada dasarnya tahu bahwa
daftar Anda masih ada up

418
00:21:47,510 --> 00:21:50,900
sampai pointer tidak sama dengan
null karena setelah itu sama dengan nol,

419
00:21:50,900 --> 00:21:53,310
Anda tahu bahwa tidak ada hal yang lebih.

420
00:21:53,310 --> 00:21:56,930
>> Jadi itu adalah lingkaran dimana kami
akan memiliki pencarian yang sebenarnya.

421
00:21:56,930 --> 00:22:01,690
Dan jika pointer-- yang Anda lihat
semacam panah fungsi sana?

422
00:22:01,690 --> 00:22:06,930
Jadi jika pointer menunjuk ke n, jika
pointer pada n sama sama n,

423
00:22:06,930 --> 00:22:09,180
sehingga berarti bahwa jika
pointer yang Anda

424
00:22:09,180 --> 00:22:13,420
mencari di akhir setiap
simpul sebenarnya sama dengan nilai

425
00:22:13,420 --> 00:22:15,990
Anda sedang mencari, kemudian
Anda ingin kembali benar.

426
00:22:15,990 --> 00:22:19,280
Jadi pada dasarnya, jika Anda berada di sebuah node yang
memiliki nilai yang Anda cari,

427
00:22:19,280 --> 00:22:23,550
Anda tahu bahwa Anda sudah
berhasil mencari.

428
00:22:23,550 --> 00:22:27,150
>> Jika tidak, Anda ingin mengatur
pointer Anda ke node berikutnya.

429
00:22:27,150 --> 00:22:28,850
Itulah yang yang sejalan sini adalah melakukan.

430
00:22:28,850 --> 00:22:31,750
Pointer sama pointer berikutnya.

431
00:22:31,750 --> 00:22:33,360
Semua orang melihat bagaimana yang bekerja?

432
00:22:33,360 --> 00:22:36,580
>> Dan pada dasarnya Anda akan hanya
melintasi keseluruhan daftar,

433
00:22:36,580 --> 00:22:41,920
ulang pointer Anda setiap kali sampai
Anda akhirnya memukul akhir daftar.

434
00:22:41,920 --> 00:22:45,030
Dan Anda tahu bahwa tidak ada
lebih node untuk mencari melalui,

435
00:22:45,030 --> 00:22:47,999
dan kemudian Anda dapat kembali palsu
karena Anda tahu bahwa, oh, baik,

436
00:22:47,999 --> 00:22:50,540
jika saya sudah bisa mencari
melalui keseluruhan daftar.

437
00:22:50,540 --> 00:22:54,530
Jika dalam contoh ini, jika saya ingin
untuk mencari nilai 10,

438
00:22:54,530 --> 00:22:57,250
dan aku mulai kepala, dan
Saya mencari semua jalan ke bawah,

439
00:22:57,250 --> 00:23:00,550
dan saya akhirnya harus ini, yang
pointer yang menunjuk ke null,

440
00:23:00,550 --> 00:23:04,415
Aku tahu itu, omong kosong, saya kira 10 tidak di
daftar ini karena saya tidak bisa menemukannya.

441
00:23:04,415 --> 00:23:06,520
Dan aku di akhir daftar.

442
00:23:06,520 --> 00:23:11,040
Dan dalam hal ini Anda tahu
Aku akan kembali palsu.

443
00:23:11,040 --> 00:23:12,900
>> Biarkan yang rendam dalam untuk sedikit.

444
00:23:12,900 --> 00:23:17,350
Ini akan cukup
penting untuk pset Anda.

445
00:23:17,350 --> 00:23:21,140
Logika sangat sederhana, mungkin
sintaksis hanya mengimplementasikannya.

446
00:23:21,140 --> 00:23:23,365
Kalian ingin membuat
Pastikan bahwa Anda memahami.

447
00:23:23,365 --> 00:23:25,870

448
00:23:25,870 --> 00:23:27,650
Keren.

449
00:23:27,650 --> 00:23:32,560
>> OK, jadi bagaimana kita akan
menyisipkan node, tepat,

450
00:23:32,560 --> 00:23:35,380
ke dalam daftar karena ingat
apa apa manfaat

451
00:23:35,380 --> 00:23:39,230
memiliki daftar link vs
array dalam hal penyimpanan?

452
00:23:39,230 --> 00:23:41,110
>> AUDIENCE: Ini dinamis,
sehingga lebih mudah to--

453
00:23:41,110 --> 00:23:43,180
>> ANDI PENG: Tepat,
jadi dinamis, yang

454
00:23:43,180 --> 00:23:46,880
berarti bahwa ia dapat memperluas dan menyusut
tergantung pada kebutuhan pengguna.

455
00:23:46,880 --> 00:23:56,570
Dan, dalam pengertian ini, kita tidak perlu
membuang memori yang tidak perlu karena saya

456
00:23:56,570 --> 00:24:00,850
jika saya tidak tahu berapa banyak nilai-nilai yang saya inginkan
ke toko, itu tidak masuk akal bagi saya

457
00:24:00,850 --> 00:24:04,310
untuk membuat sebuah array karena
jika saya ingin menyimpan 10 nilai

458
00:24:04,310 --> 00:24:08,380
dan saya membuat sebuah array dari 1.000, yang
banyak memori terbuang, diberikan.

459
00:24:08,380 --> 00:24:11,180
Itu sebabnya kami ingin menggunakan linked
Daftar untuk dapat dinamis

460
00:24:11,180 --> 00:24:13,860
mengubah atau menyusut ukuran kami.

461
00:24:13,860 --> 00:24:17,040
>> Dan sehingga membuat penyisipan
sedikit lebih rumit.

462
00:24:17,040 --> 00:24:20,810
Karena kita tidak dapat secara acak mengakses elemen
cara kita akan dari array.

463
00:24:20,810 --> 00:24:24,270
Jika saya ingin memasukkan unsur
dalam indeks ketujuh,

464
00:24:24,270 --> 00:24:26,930
Aku hanya bisa masukkan
ke dalam indeks ketujuh.

465
00:24:26,930 --> 00:24:30,020
Pada linked list, tidak
cukup bekerja dengan mudah,

466
00:24:30,020 --> 00:24:34,947
dan jadi jika kita ingin menyisipkan
satu di sini dalam linked list,

467
00:24:34,947 --> 00:24:36,280
visual, itu sangat mudah untuk melihat.

468
00:24:36,280 --> 00:24:39,363
Kami hanya ingin memasukkannya di sana,
tepat di awal daftar,

469
00:24:39,363 --> 00:24:40,840
setelah kepala.

470
00:24:40,840 --> 00:24:44,579
>> Namun cara di mana kita harus menetapkan kembali
pointer adalah sedikit berbelit-belit

471
00:24:44,579 --> 00:24:47,620
atau, secara logis, masuk akal, tapi
Anda ingin memastikan bahwa Anda memilikinya

472
00:24:47,620 --> 00:24:50,250
benar-benar turun karena
hal terakhir yang Anda inginkan

473
00:24:50,250 --> 00:24:52,990
adalah untuk menetapkan kembali pointer yang
cara yang kita lakukan di sini.

474
00:24:52,990 --> 00:24:58,170
Jika Anda dereference
pointer dari kepala sampai 1,

475
00:24:58,170 --> 00:25:01,086
maka semua dari tiba-tiba
sisa daftar Anda terkait

476
00:25:01,086 --> 00:25:04,680
hilang karena Anda harus benar-benar
menciptakan sesuatu yang sementara.

477
00:25:04,680 --> 00:25:06,220
Itu menunjuk ke 2.

478
00:25:06,220 --> 00:25:10,080
Jika Anda menetapkan kembali pointer, maka
sisa daftar Anda benar-benar hilang.

479
00:25:10,080 --> 00:25:13,310
Jadi Anda ingin menjadi
sangat, sangat berhati-hati di sini

480
00:25:13,310 --> 00:25:17,010
untuk pertama menetapkan
pointer dari apa pun yang Anda

481
00:25:17,010 --> 00:25:20,150
ingin masukkan ke mana pun
yang Anda inginkan, dan kemudian Anda

482
00:25:20,150 --> 00:25:22,710
bisa dereference sisa daftar Anda.

483
00:25:22,710 --> 00:25:25,250
>> Jadi ini berlaku untuk dimanapun
Anda mencoba untuk memasukkan ke dalam.

484
00:25:25,250 --> 00:25:27,520
Jika Anda ingin memasukkan di
kepala, jika Anda ingin menjawab di sini,

485
00:25:27,520 --> 00:25:29,455
jika Anda ingin memasukkan di
akhirnya, baik, akhirnya saya

486
00:25:29,455 --> 00:25:30,910
kira Anda akan hanya
tidak memiliki pointer, tetapi Anda

487
00:25:30,910 --> 00:25:33,830
ingin memastikan bahwa Anda tidak
kehilangan sisa daftar Anda.

488
00:25:33,830 --> 00:25:36,640
Anda selalu ingin memastikan
node baru Anda menunjuk

489
00:25:36,640 --> 00:25:39,330
terhadap apa pun yang Anda
ingin masukkan ke dalam,

490
00:25:39,330 --> 00:25:42,170
dan kemudian Anda dapat menambahkan chaining pada.

491
00:25:42,170 --> 00:25:43,330
Semua orang yang jelas?

492
00:25:43,330 --> 00:25:45,427
>> Ini akan menjadi
salah satu masalah yang nyata.

493
00:25:45,427 --> 00:25:48,010
Salah satu yang paling isu utama
Anda akan memiliki pada pset Anda

494
00:25:48,010 --> 00:25:51,340
adalah bahwa Anda akan mencoba untuk membuat
daftar link dan hal insert

495
00:25:51,340 --> 00:25:53,340
tapi kemudian hanya kehilangan
sisa daftar Anda terkait.

496
00:25:53,340 --> 00:25:54,900
Dan Anda akan menjadi seperti, saya
tidak tahu mengapa hal ini terjadi?

497
00:25:54,900 --> 00:25:58,040
Dan itu sakit untuk pergi melalui
dan mencari semua pointer Anda.

498
00:25:58,040 --> 00:26:02,100
>> Dan saya jamin Anda di pset ini,
menulis dan menggambar node ini keluar

499
00:26:02,100 --> 00:26:03,344
akan sangat, sangat membantu.

500
00:26:03,344 --> 00:26:06,010
Jadi Anda benar-benar dapat melacak
dari mana semua pointer Anda,

501
00:26:06,010 --> 00:26:08,540
apa yang salah,
di mana semua node Anda,

502
00:26:08,540 --> 00:26:12,660
apa yang perlu Anda lakukan untuk mengakses atau
memasukkan atau menghapus atau salah satu dari mereka.

503
00:26:12,660 --> 00:26:14,550
Semua orang baik dengan itu?

504
00:26:14,550 --> 00:26:15,050
Keren.

505
00:26:15,050 --> 00:26:19,300

506
00:26:19,300 --> 00:26:22,600
>> Jadi jika kita ingin melihat kode?

507
00:26:22,600 --> 00:26:24,470
Oh, aku tidak tahu apakah kita
dapat melihat OK the--, sehingga

508
00:26:24,470 --> 00:26:27,940
di atas semua itu adalah fungsi
bernama insert mana kita ingin

509
00:26:27,940 --> 00:26:31,365
untuk menyisipkan int n ke dalam linked list.

510
00:26:31,365 --> 00:26:32,740
Kita akan berjalan melalui ini.

511
00:26:32,740 --> 00:26:34,770
Ini banyak kode, banyak sintaks baru.

512
00:26:34,770 --> 00:26:36,220
Kami akan OK.

513
00:26:36,220 --> 00:26:39,120
>> Jadi di atas, setiap kali
kami ingin menciptakan sesuatu

514
00:26:39,120 --> 00:26:42,380
apa yang perlu kita lakukan, terutama jika Anda
ingin untuk tidak disimpan di stack

515
00:26:42,380 --> 00:26:43,920
namun di heap?

516
00:26:43,920 --> 00:26:45,460
Kami pergi ke malloc, kan?

517
00:26:45,460 --> 00:26:48,240
Jadi kita akan membuat sebuah pointer.

518
00:26:48,240 --> 00:26:52,074
Node, pointer, equals baru
malloc ukuran node

519
00:26:52,074 --> 00:26:53,740
karena kami ingin node yang akan dibuat.

520
00:26:53,740 --> 00:26:56,720
Kami ingin jumlah
memori yang node memakan

521
00:26:56,720 --> 00:26:59,300
akan dialokasikan untuk
penciptaan node baru.

522
00:26:59,300 --> 00:27:02,270
>> Dan kemudian kita akan memeriksa untuk
melihat apakah sama dengan yang baru sama null.

523
00:27:02,270 --> 00:27:03,370
Ingat apa yang kita katakan?

524
00:27:03,370 --> 00:27:06,470
Apa pun yang Anda malloc,
apa yang harus Anda selalu lakukan?

525
00:27:06,470 --> 00:27:09,490
Anda harus selalu memeriksa untuk melihat
apakah atau tidak itu adalah nol.

526
00:27:09,490 --> 00:27:13,620
>> Sebagai contoh, jika operasi Anda
Sistem benar-benar penuh,

527
00:27:13,620 --> 00:27:17,060
jika Anda tidak memiliki lebih banyak memori di
semua dan Anda mencoba untuk malloc,

528
00:27:17,060 --> 00:27:18,410
itu akan kembali null untuk Anda.

529
00:27:18,410 --> 00:27:21,094
Dan jadi jika Anda mencoba untuk menggunakannya
ketika itu menunjuk ke null,

530
00:27:21,094 --> 00:27:23,260
Anda tidak akan bisa
untuk mengakses informasi tersebut.

531
00:27:23,260 --> 00:27:27,010
Dan dengan demikian, kami ingin membuat
Pastikan bahwa setiap kali Anda mallocing,

532
00:27:27,010 --> 00:27:30,500
Anda selalu memeriksa untuk melihat apakah
bahwa memori diberikan kepada Anda adalah nol.

533
00:27:30,500 --> 00:27:33,670
Dan jika tidak, maka kita bisa bergerak
pada dengan sisa kode kita.

534
00:27:33,670 --> 00:27:36,140
>> Jadi kita akan
menginisialisasi node baru.

535
00:27:36,140 --> 00:27:39,050
Kami akan melakukan yang baru n sama n.

536
00:27:39,050 --> 00:27:42,390
Dan kemudian kita akan melakukan
mengatur baru pointer pada baru

537
00:27:42,390 --> 00:27:46,900
untuk nol karena sekarang kita tidak
ingin apa-apa untuk itu untuk menunjuk ke.

538
00:27:46,900 --> 00:27:48,755
Kami tidak tahu di mana
itu akan menempatkan Anda,

539
00:27:48,755 --> 00:27:50,630
dan kemudian jika kita ingin
masukkan di kepala,

540
00:27:50,630 --> 00:27:53,820
maka kita dapat menetapkan kembali
pointer ke kepala.

541
00:27:53,820 --> 00:27:58,530
Apakah setiap orang mengikuti logika
dari mana itu terjadi?

542
00:27:58,530 --> 00:28:02,502
>> Semua yang kita lakukan adalah menciptakan baru
node, pengaturan pointer ke null,

543
00:28:02,502 --> 00:28:04,210
dan kemudian pemindahan
untuk kepala jika kita

544
00:28:04,210 --> 00:28:06,320
tahu kita ingin memasukkannya di kepala.

545
00:28:06,320 --> 00:28:09,420
Dan kemudian kepala akan
menunjuk ke arah yang simpul baru.

546
00:28:09,420 --> 00:28:11,060
Semua orang OK dengan itu?

547
00:28:11,060 --> 00:28:12,380
>> Jadi itu adalah proses dua langkah.

548
00:28:12,380 --> 00:28:14,760
Anda harus menetapkan pertama
apa pun yang Anda ciptakan.

549
00:28:14,760 --> 00:28:18,260
Mengatur bahwa pointer ke
referensi, dan kemudian Anda

550
00:28:18,260 --> 00:28:21,400
bisa jenis dereference
pointer pertama

551
00:28:21,400 --> 00:28:22,972
dan menunjuk ke arah simpul baru.

552
00:28:22,972 --> 00:28:25,680
Di mana pun Anda ingin memasukkannya,
logika yang akan berlaku.

553
00:28:25,680 --> 00:28:27,530
>> Ini semacam seperti menugaskan
variabel sementara.

554
00:28:27,530 --> 00:28:28,700
Ingat, Anda punya
memastikan bahwa Anda

555
00:28:28,700 --> 00:28:30,346
tidak kehilangan jejak jika Anda swapping.

556
00:28:30,346 --> 00:28:33,470
Anda ingin memastikan bahwa Anda memiliki
variabel sementara jenis terus

557
00:28:33,470 --> 00:28:35,620
melacak di mana hal yang
disimpan sehingga Anda

558
00:28:35,620 --> 00:28:41,190
tidak kehilangan nilai dalam kursus
seperti main-main dengan hal itu.

559
00:28:41,190 --> 00:28:42,710
>> OK, jadi kode akan berada di sini.

560
00:28:42,710 --> 00:28:45,020
Kalian lihat setelah bagian.

561
00:28:45,020 --> 00:28:48,060
Ini akan berada di sana.

562
00:28:48,060 --> 00:28:50,280
>> Jadi saya kira bagaimana
ini berbeda jika kita ingin

563
00:28:50,280 --> 00:28:52,300
untuk memasukkan ke tengah atau akhir?

564
00:28:52,300 --> 00:28:57,892
Apakah ada yang punya ide tentang apa
pseudocode sebagai referensi logis

565
00:28:57,892 --> 00:29:00,350
bahwa kita akan mengambil jika kita ingin
untuk menyisipkan di tengah?

566
00:29:00,350 --> 00:29:03,391
Jadi jika kita ingin masukkan di
kepala, semua yang kita lakukan adalah membuat node baru.

567
00:29:03,391 --> 00:29:06,311
Kami mengatur pointer itu
node baru apa pun kepala,

568
00:29:06,311 --> 00:29:08,310
dan kemudian kita mengatur kepala
ke node baru, kan?

569
00:29:08,310 --> 00:29:11,560
Jika kita ingin memasukkannya di tengah
dari daftar, apa yang harus kita lakukan?

570
00:29:11,560 --> 00:29:14,108

571
00:29:14,108 --> 00:29:16,110
>> AUDIENCE: Ini akan masih
menjadi proses yang sama

572
00:29:16,110 --> 00:29:19,114
seperti menugaskan pointer dan
kemudian menugaskan pointer itu,

573
00:29:19,114 --> 00:29:20,530
tapi kita harus mencari di sana.

574
00:29:20,530 --> 00:29:23,560
>> ANDI PENG: Tepat, sehingga persis
proses yang sama kecuali Anda

575
00:29:23,560 --> 00:29:27,820
harus mencari di mana tepatnya Anda
ingin bahwa pointer baru untuk masuk ke dalam,

576
00:29:27,820 --> 00:29:44,790
jadi jika saya ingin masukkan ke
tengah terkait list-- OK,

577
00:29:44,790 --> 00:29:46,370
katakanlah itu linked list kami.

578
00:29:46,370 --> 00:29:49,500
Jika kita ingin memasukkannya di sini,
kita akan membuat node baru.

579
00:29:49,500 --> 00:29:50,520
Kita akan malloc.

580
00:29:50,520 --> 00:29:52,220
Kita akan membuat node baru.

581
00:29:52,220 --> 00:29:55,940
Kita akan menetapkan
pointer dari node ini di sini.

582
00:29:55,940 --> 00:29:58,335
>> Tapi masalahnya yang berbeda
dari mana kepala adalah

583
00:29:58,335 --> 00:30:00,490
adalah bahwa kita tahu persis
di mana kepala adalah.

584
00:30:00,490 --> 00:30:01,930
Itu tepat di pertama, kan?

585
00:30:01,930 --> 00:30:04,870
Tapi di sini kita harus melacak
dari mana kita memasukkan ke.

586
00:30:04,870 --> 00:30:07,930
Jika kita memasukkan kami
simpul di sini, kami punya

587
00:30:07,930 --> 00:30:12,270
untuk memastikan bahwa
sebelumnya ke node ini

588
00:30:12,270 --> 00:30:14,172
adalah salah satu yang reassigns pointer.

589
00:30:14,172 --> 00:30:16,380
Jadi Anda harus jenis
melacak dua hal.

590
00:30:16,380 --> 00:30:19,420
Jika Anda melacak di mana ini
simpul saat ini memasukkan ke.

591
00:30:19,420 --> 00:30:23,280
Anda juga harus melacak di mana
node sebelumnya yang Anda cari di

592
00:30:23,280 --> 00:30:24,340
juga ada.

593
00:30:24,340 --> 00:30:25,830
Semua orang baik dengan itu?

594
00:30:25,830 --> 00:30:26,500
OKE.

595
00:30:26,500 --> 00:30:28,000
>> Bagaimana memasukkan ke akhir?

596
00:30:28,000 --> 00:30:34,220
Jika saya ingin menambahkannya di sini-jika saya ingin
untuk menambahkan node baru ke akhir daftar,

597
00:30:34,220 --> 00:30:37,009
bagaimana mungkin aku pergi untuk melakukan itu?

598
00:30:37,009 --> 00:30:39,300
AUDIENCE: Jadi saat ini, yang
satu lalu menunjuk ke null.

599
00:30:39,300 --> 00:30:40,960
ANDI PENG: Ya.

600
00:30:40,960 --> 00:30:43,560
Tepat, jadi yang satu ini
saat ini menunjuk tahu,

601
00:30:43,560 --> 00:30:46,720
dan jadi saya kira, dalam pengertian ini, itu
sangat mudah untuk menambahkan ke akhir daftar.

602
00:30:46,720 --> 00:30:51,810
Yang harus Anda lakukan adalah mengatur itu
sama dengan nol dan kemudian booming.

603
00:30:51,810 --> 00:30:53,070
Di sana, sangat mudah.

604
00:30:53,070 --> 00:30:53,960
Sangat sederhana.

605
00:30:53,960 --> 00:30:56,430
>> Sangat mirip dengan
kepala, tetapi secara logis Anda

606
00:30:56,430 --> 00:30:59,690
ingin memastikan bahwa langkah-langkah
Anda ambil terhadap melakukan semua ini,

607
00:30:59,690 --> 00:31:01,500
Anda mengikuti bersama.

608
00:31:01,500 --> 00:31:04,420
Ini sangat mudah untuk, di tengah
kode Anda, terjebak pada,

609
00:31:04,420 --> 00:31:05,671
oh, aku punya begitu banyak pointer.

610
00:31:05,671 --> 00:31:07,461
Saya tidak tahu di mana
apapun menunjuk ke.

611
00:31:07,461 --> 00:31:09,170
Aku bahkan tidak tahu yang simpul aku di.

612
00:31:09,170 --> 00:31:11,490
Apa yang sedang terjadi?

613
00:31:11,490 --> 00:31:13,620
>> Tenang, tenang, ambil napas dalam.

614
00:31:13,620 --> 00:31:15,530
Menarik keluar daftar Anda terkait.

615
00:31:15,530 --> 00:31:18,800
Jika Anda mengatakan, saya tahu di mana tepatnya
Saya harus memasukkan ini ke

616
00:31:18,800 --> 00:31:22,970
dan saya tahu persis bagaimana untuk menetapkan kembali saya
pointer, jauh, jauh lebih mudah untuk membayangkan

617
00:31:22,970 --> 00:31:27,200
out-- banyak, jauh lebih mudah untuk tidak
tersesat di bug kode Anda.

618
00:31:27,200 --> 00:31:29,410
Semua orang OK dengan itu?

619
00:31:29,410 --> 00:31:31,380
OKE.

620
00:31:31,380 --> 00:31:35,120
>> Jadi saya kira konsep yang kita miliki tidak
benar-benar berbicara tentang sebelum sekarang,

621
00:31:35,120 --> 00:31:38,131
dan saya kira Anda mungkin
tidak akan menghadapi banyak yet--

622
00:31:38,131 --> 00:31:40,880
itu jenis dari concept-- canggih
adalah bahwa kita benar-benar memiliki data

623
00:31:40,880 --> 00:31:43,900
struktur yang disebut daftar ganda terkait.

624
00:31:43,900 --> 00:31:46,390
Sehingga kalian bisa melihat,
semua yang kita lakukan adalah menciptakan

625
00:31:46,390 --> 00:31:50,400
nilai sebenarnya, tambahan
pointer pada setiap node kami

626
00:31:50,400 --> 00:31:52,660
yang juga menunjuk ke simpul sebelumnya.

627
00:31:52,660 --> 00:31:58,170
Jadi kita tidak hanya memiliki kita
node menunjuk ke yang berikutnya.

628
00:31:58,170 --> 00:32:01,430
Mereka juga menunjuk pada sebelumnya.

629
00:32:01,430 --> 00:32:04,310
Aku akan mengabaikan kedua sekarang.

630
00:32:04,310 --> 00:32:06,740
>> Jadi Anda memiliki rantai
yang dapat bergerak dua arah,

631
00:32:06,740 --> 00:32:09,630
dan kemudian itu sedikit lebih mudah
untuk secara logis mengikuti bersama.

632
00:32:09,630 --> 00:32:11,896
Seperti di sini, bukannya
melacak, oh, saya

633
00:32:11,896 --> 00:32:14,520
harus tahu bahwa simpul ini
salah satu yang saya harus menetapkan kembali,

634
00:32:14,520 --> 00:32:17,532
Aku hanya bisa pergi di sini dan
hanya tarik sebelumnya.

635
00:32:17,532 --> 00:32:19,490
Kemudian saya tahu persis di mana
yaitu, dan kemudian Anda

636
00:32:19,490 --> 00:32:21,130
tidak perlu melintasi
keseluruhan dari linked list.

637
00:32:21,130 --> 00:32:22,180
Ini sedikit lebih mudah.

638
00:32:22,180 --> 00:32:24,960
>> Tapi dengan demikian, Anda memiliki dua kali lipat
jumlah pointer,

639
00:32:24,960 --> 00:32:26,960
itu dua kali lipat jumlah memori.

640
00:32:26,960 --> 00:32:28,950
Ini banyak pointer untuk melacak.

641
00:32:28,950 --> 00:32:32,140
Ini sedikit lebih kompleks, tapi itu
sedikit lebih user friendly tergantung

642
00:32:32,140 --> 00:32:34,080
pada apa yang Anda capai.

643
00:32:34,080 --> 00:32:36,910
>> Sehingga jenis data
struktur benar-benar ada,

644
00:32:36,910 --> 00:32:40,280
dan struktur adalah sangat, sangat
sederhana kecuali semua Anda mengalami adalah,

645
00:32:40,280 --> 00:32:43,850
bukan hanya pointer ke depan,
Anda juga memiliki pointer ke sebelumnya.

646
00:32:43,850 --> 00:32:45,940
Itu semua perbedaan itu.

647
00:32:45,940 --> 00:32:47,740
Semua orang baik dengan itu?

648
00:32:47,740 --> 00:32:48,240
Keren.

649
00:32:48,240 --> 00:32:50,940

650
00:32:50,940 --> 00:32:53,280
>> Baiklah, jadi sekarang aku
untuk benar-benar menghabiskan mungkin

651
00:32:53,280 --> 00:32:56,870
seperti 15 sampai 20 menit atau bulk
dari sisa waktu di bagian

652
00:32:56,870 --> 00:32:58,360
berbicara tentang tabel hash.

653
00:32:58,360 --> 00:33:02,590
Berapa banyak dari kalian
telah membaca pset5 spesifikasi?

654
00:33:02,590 --> 00:33:03,620
Baiklah, baik.

655
00:33:03,620 --> 00:33:06,160
Itu lebih tinggi dari 50% dari biasanya.

656
00:33:06,160 --> 00:33:07,560
Tidak apa-apa.

657
00:33:07,560 --> 00:33:10,345
>> Sehingga kalian akan melihat,
Anda tantangan di pset5

658
00:33:10,345 --> 00:33:16,790
akan menerapkan kamus
di mana Anda memuat lebih dari 140.000 kata-kata

659
00:33:16,790 --> 00:33:20,610
bahwa kita memberikan dan spell check
melawan semua teks.

660
00:33:20,610 --> 00:33:22,580
Kami akan memberikan acak
potongan sastra.

661
00:33:22,580 --> 00:33:23,520
Kami akan memberikan Odyssey.

662
00:33:23,520 --> 00:33:24,561
Kami akan memberikan The Iliad.

663
00:33:24,561 --> 00:33:26,350
Kami akan memberikan Austin Powers.

664
00:33:26,350 --> 00:33:28,220
>> Dan tantangan Anda
akan mengeja cek

665
00:33:28,220 --> 00:33:31,760
setiap kata di semua
orang kamus

666
00:33:31,760 --> 00:33:34,960
dasarnya dengan spell checker kita.

667
00:33:34,960 --> 00:33:38,620
Dan jadi ada beberapa bagian
menciptakan pset ini,

668
00:33:38,620 --> 00:33:41,970
pertama yang Anda ingin menjadi
dapat benar-benar memuat

669
00:33:41,970 --> 00:33:43,970
semua kata-kata menjadi Anda
kamus, dan kemudian Anda

670
00:33:43,970 --> 00:33:45,530
ingin dapat
spell check semua dari mereka.

671
00:33:45,530 --> 00:33:48,780
Dan dengan demikian, Anda akan memerlukan
struktur data yang dapat melakukan hal ini dengan cepat

672
00:33:48,780 --> 00:33:50,790
dan efisien dan dinamis.

673
00:33:50,790 --> 00:33:52,900
>> Jadi saya kira yang paling mudah
cara untuk melakukan ini, Anda

674
00:33:52,900 --> 00:33:55,010
mungkin akan membuat sebuah array, kan?

675
00:33:55,010 --> 00:33:58,910
Cara termudah penyimpanan adalah Anda
dapat membuat array 140.000 kata

676
00:33:58,910 --> 00:34:03,400
dan hanya menempatkan mereka semua ada dan
kemudian melintasi mereka dengan pencarian biner

677
00:34:03,400 --> 00:34:06,780
atau dengan pilihan atau not--
maaf yang penyortiran.

678
00:34:06,780 --> 00:34:10,729
Anda dapat mengurutkan mereka dan kemudian melintasi mereka
oleh pencarian biner atau pencarian hanya linear

679
00:34:10,729 --> 00:34:13,730
dan hanya akhir kata-kata, tapi itu
Dibutuhkan sejumlah besar memori,

680
00:34:13,730 --> 00:34:15,190
dan itu tidak sangat efisien.

681
00:34:15,190 --> 00:34:18,350
>> Dan kita akan mulai
berbicara tentang cara membuat

682
00:34:18,350 --> 00:34:20,110
waktu kita berjalan lebih efisien.

683
00:34:20,110 --> 00:34:23,190
Dan tujuan kami adalah untuk mendapatkan
waktu yang konstan di mana

684
00:34:23,190 --> 00:34:25,810
itu hampir seperti array, di mana
Anda memiliki akses seketika.

685
00:34:25,810 --> 00:34:28,560
Jika saya ingin mencari sesuatu,
Saya ingin bisa hanya,

686
00:34:28,560 --> 00:34:30,810
booming, merasa persis, dan menariknya keluar.

687
00:34:30,810 --> 00:34:34,100
Dan struktur di mana
kita akan menjadi sangat dekat

688
00:34:34,100 --> 00:34:37,569
untuk dapat mengakses konstan
waktu, grail suci ini

689
00:34:37,569 --> 00:34:41,370
dalam pemrograman konstan
waktu disebut tabel hash.

690
00:34:41,370 --> 00:34:45,370
Dan David yang disebutkan sebelumnya
[Tak terdengar] sedikit di kuliah,

691
00:34:45,370 --> 00:34:49,100
tapi kita akan benar-benar
menyelam di dalam minggu ini

692
00:34:49,100 --> 00:34:51,780
pada selembar yang mengenai
bagaimana tabel hash bekerja.

693
00:34:51,780 --> 00:34:53,949
>> Jadi cara yang hash
karya meja, misalnya,

694
00:34:53,949 --> 00:35:00,230
jika saya ingin menyimpan sekelompok kata-kata, sebuah
sekelompok kata-kata dalam bahasa Inggris,

695
00:35:00,230 --> 00:35:02,940
Saya secara teoritis bisa menempatkan
pisang, apel, kiwi, mangga, pasangan,

696
00:35:02,940 --> 00:35:04,980
dan melon semua hanya pada array.

697
00:35:04,980 --> 00:35:07,044
Mereka semua bisa cocok dan akan menemukan.

698
00:35:07,044 --> 00:35:09,210
Ini akan menjadi semacam rasa sakit untuk
mencari melalui dan akses,

699
00:35:09,210 --> 00:35:12,920
tapi cara yang lebih mudah untuk melakukan hal ini adalah
bahwa kita dapat membuat benar-benar struktur

700
00:35:12,920 --> 00:35:15,680
disebut tabel hash mana kita hash.

701
00:35:15,680 --> 00:35:19,880
Kami menjalankan semua kunci kami melalui
fungsi hash, persamaan,

702
00:35:19,880 --> 00:35:22,600
yang mengubah mereka semua ke dalam
semacam nilai

703
00:35:22,600 --> 00:35:28,740
yang kemudian kita dapat menyimpan ke
dasarnya array linked list.

704
00:35:28,740 --> 00:35:32,570
>> Dan jadi di sini, jika kita ingin
untuk menyimpan kata-kata bahasa Inggris,

705
00:35:32,570 --> 00:35:37,250
kita bisa berpotensi hanya, saya tidak
tahu, mengubah semua huruf pertama

706
00:35:37,250 --> 00:35:39,630
menjadi semacam nomor.

707
00:35:39,630 --> 00:35:43,140
Dan sebagainya, misalnya, jika saya ingin
Sebuah identik dengan apple--

708
00:35:43,140 --> 00:35:47,460
atau dengan indeks 0, dan
B menjadi identik dengan 1,

709
00:35:47,460 --> 00:35:51,030
kita dapat memiliki 26 entri
yang hanya dapat menyimpan

710
00:35:51,030 --> 00:35:53,610
semua surat dari
alfabet yang kita akan mulai dengan.

711
00:35:53,610 --> 00:35:56,130
Dan kemudian kita dapat memiliki
apple di indeks 0.

712
00:35:56,130 --> 00:35:59,160
Kita dapat memiliki pisang di indeks
1, blewah di indeks 2,

713
00:35:59,160 --> 00:36:00,540
dan sebagainya dan sebagainya.

714
00:36:00,540 --> 00:36:04,460
Dan dengan demikian jika saya ingin mencari
meja dan akses hash saya apel,

715
00:36:04,460 --> 00:36:07,560
Aku tahu apel dimulai dengan
A, dan saya tahu persis

716
00:36:07,560 --> 00:36:10,860
bahwa hal itu harus dan hash
tabel pada indeks 0 karena

717
00:36:10,860 --> 00:36:13,620
fungsi yang sebelumnya ditetapkan.

718
00:36:13,620 --> 00:36:16,572
>> Jadi saya tidak tahu, kita
program pengguna mana

719
00:36:16,572 --> 00:36:18,780
Anda akan dikenakan biaya dengan
arbitrarily-- tidak sewenang-wenang,

720
00:36:18,780 --> 00:36:22,530
dengan mencoba untuk serius
memikirkan persamaan baik

721
00:36:22,530 --> 00:36:25,460
untuk dapat menyebar
semua nilai Anda

722
00:36:25,460 --> 00:36:29,370
dengan cara mereka dapat dengan mudah mengakses
nanti dengan seperti persamaan

723
00:36:29,370 --> 00:36:31,130
Anda, diri sendiri, tahu.

724
00:36:31,130 --> 00:36:35,210
Jadi dalam arti jika saya ingin pergi ke
mangga, aku tahu, oh, itu dimulai dengan m.

725
00:36:35,210 --> 00:36:37,134
Itu harus di indeks 12.

726
00:36:37,134 --> 00:36:38,800
Saya tidak perlu mencari melalui apa-apa.

727
00:36:38,800 --> 00:36:42,080
Aku tahu exactly-- aku bisa pergi ke
indeks 12 dan menarik yang keluar.

728
00:36:42,080 --> 00:36:45,520
>> Semua orang yang jelas tentang bagaimana
Fungsi hash tabel bekerja?

729
00:36:45,520 --> 00:36:48,380
Ini semacam hanya array yang lebih kompleks.

730
00:36:48,380 --> 00:36:50,010
Itu semua itu.

731
00:36:50,010 --> 00:36:51,630
OKE.

732
00:36:51,630 --> 00:36:57,690
>> Jadi saya kira kita mengalami
masalah ini apa

733
00:36:57,690 --> 00:37:06,390
yang terjadi jika Anda memiliki beberapa hal
yang memberikan indeks yang sama?

734
00:37:06,390 --> 00:37:10,570
Jadi mengatakan fungsi kita, semua itu
lakukan adalah mengambil huruf pertama

735
00:37:10,570 --> 00:37:14,490
dan mengubahnya menjadi
masing 0 sampai 25 indeks.

736
00:37:14,490 --> 00:37:17,137
Itu benar-benar baik-baik saja jika
Anda hanya memiliki satu dari masing-masing.

737
00:37:17,137 --> 00:37:18,970
Tapi yang kedua Anda mulai
memiliki lebih, Anda

738
00:37:18,970 --> 00:37:20,910
akan memiliki apa yang disebut tabrakan.

739
00:37:20,910 --> 00:37:25,580
>> Jadi jika saya mencoba untuk memasukkan mengubur dalam hash
tabel yang sudah memiliki pisang di atasnya,

740
00:37:25,580 --> 00:37:27,870
apa yang akan terjadi ketika
Anda mencoba untuk memasukkan itu?

741
00:37:27,870 --> 00:37:30,930
Hal-hal buruk karena pisang
sudah ada dalam indeks

742
00:37:30,930 --> 00:37:33,800
bahwa Anda ingin menyimpannya dalam.

743
00:37:33,800 --> 00:37:35,560
Berry jenis seperti, ah, apa yang harus saya lakukan?

744
00:37:35,560 --> 00:37:37,080
Saya tidak tahu ke mana harus pergi.

745
00:37:37,080 --> 00:37:38,410
Bagaimana cara mengatasi ini?

746
00:37:38,410 --> 00:37:41,150
>> Dan kalian akan jenis
melihat kita melakukan hal yang rumit ini

747
00:37:41,150 --> 00:37:44,810
di mana kita bisa benar-benar jenis
membuat daftar terkait dalam array kami.

748
00:37:44,810 --> 00:37:46,840
Dan cara termudah
untuk berpikir tentang hal ini,

749
00:37:46,840 --> 00:37:50,830
semua tabel hash adalah
array daftar terkait.

750
00:37:50,830 --> 00:37:55,670
Dan, dalam arti bahwa, Anda memiliki
array yang indah ini pointer,

751
00:37:55,670 --> 00:37:58,740
dan kemudian setiap pointer di
nilai itu, indeks itu,

752
00:37:58,740 --> 00:38:00,740
benar-benar dapat menunjukkan hal-hal lain.

753
00:38:00,740 --> 00:38:05,720
Dan sehingga Anda memiliki semua ini terpisah
rantai datang dari satu array besar.

754
00:38:05,720 --> 00:38:07,960
>> Dan jadi di sini, jika saya
ingin memasukkan berry,

755
00:38:07,960 --> 00:38:11,220
Aku tahu, OK, saya akan masukan
melalui fungsi hash saya.

756
00:38:11,220 --> 00:38:15,070
Aku akan berakhir dengan indeks
1, dan kemudian aku akan dapat memiliki

757
00:38:15,070 --> 00:38:20,410
hanya subset kecil dari ini
Raksasa kamus 140.000-kata.

758
00:38:20,410 --> 00:38:24,220
Dan kemudian aku hanya dapat melihat
melalui 1/26 itu.

759
00:38:24,220 --> 00:38:27,910
>> Dan kemudian aku hanya bisa memasukkan
berry baik sebelum atau setelah pisang

760
00:38:27,910 --> 00:38:28,820
pada kasus ini?

761
00:38:28,820 --> 00:38:29,700
Setelah, kan?

762
00:38:29,700 --> 00:38:33,920
Dan sehingga Anda akan ingin
menyisipkan node ini setelah pisang,

763
00:38:33,920 --> 00:38:36,667
dan sehingga Anda akan memasukkan
pada ekor yang linked list.

764
00:38:36,667 --> 00:38:38,500
Aku akan kembali
ke slide ini sebelumnya,

765
00:38:38,500 --> 00:38:40,680
sehingga kalian bisa melihat bagaimana
Fungsi hash bekerja.

766
00:38:40,680 --> 00:38:43,980
>> Jadi fungsi hash adalah persamaan ini
bahwa Anda menjalankan jenis masukan Anda

767
00:38:43,980 --> 00:38:46,940
melalui untuk mendapatkan indeks apapun
Anda ingin menetapkan arah.

768
00:38:46,940 --> 00:38:51,130
Dan, dalam contoh ini, semua yang kita inginkan
lakukan adalah mengambil huruf pertama,

769
00:38:51,130 --> 00:38:55,890
mengubah itu menjadi sebuah indeks, maka kita
dapat menyimpan bahwa dalam fungsi hash kami.

770
00:38:55,890 --> 00:39:00,160
Semua yang kita lakukan di sini adalah kita
mengkonversi huruf pertama.

771
00:39:00,160 --> 00:39:04,770
Jadi keykey [0] hanya huruf pertama
string apapun yang kita mengalami,

772
00:39:04,770 --> 00:39:05,720
kita lewat di.

773
00:39:05,720 --> 00:39:09,740
Kami mengubah bahwa untuk bagian atas, dan
kita mengurangkan oleh huruf besar A,

774
00:39:09,740 --> 00:39:11,740
sehingga semua yang melakukan
memberikan kita nomor

775
00:39:11,740 --> 00:39:13,670
di mana kita dapat hash nilai-nilai kita ke.

776
00:39:13,670 --> 00:39:16,550
>> Dan kemudian kita akan
kembali hash modulus UKURAN.

777
00:39:16,550 --> 00:39:19,340
Sangat, sangat berhati-hati
karena, secara teoritis, di sini

778
00:39:19,340 --> 00:39:21,870
nilai hash Anda bisa tak terbatas.

779
00:39:21,870 --> 00:39:23,660
Itu hanya bisa terus dan terus dan terus.

780
00:39:23,660 --> 00:39:26,080
Bisa jadi beberapa benar-benar,
benar-benar nilai besar,

781
00:39:26,080 --> 00:39:29,849
tetapi karena tabel hash Anda yang
Anda telah membuat hanya memiliki 26 indeks,

782
00:39:29,849 --> 00:39:31,890
Anda ingin memastikan Anda
modulusing sehingga Anda

783
00:39:31,890 --> 00:39:33,848
tidak run-- itu sama
hal sebagai queue-- Anda

784
00:39:33,848 --> 00:39:36,320
sehingga Anda tidak menjalankan off
bawah fungsi hash Anda.

785
00:39:36,320 --> 00:39:39,210
>> Anda ingin membungkusnya kembali sekitar
dengan cara yang sama di [tak terdengar] ketika

786
00:39:39,210 --> 00:39:41,750
Anda memiliki seperti sangat,
surat yang sangat besar, Anda

787
00:39:41,750 --> 00:39:43,740
tidak ingin hal itu
hanya lari akhir.

788
00:39:43,740 --> 00:39:46,948
Hal yang sama di sini, Anda ingin memastikan
itu tidak berjalan dari ujung dengan membungkus

789
00:39:46,948 --> 00:39:48,330
sekitar untuk bagian atas meja.

790
00:39:48,330 --> 00:39:50,530
Jadi ini hanya sangat
Fungsi hash sederhana.

791
00:39:50,530 --> 00:39:56,570
Semua yang dilakukannya adalah mengambil pertama
surat apa pun masukan kami

792
00:39:56,570 --> 00:40:01,660
dan mengubahnya menjadi sebuah indeks yang
kita bisa dimasukkan ke dalam tabel hash kami.

793
00:40:01,660 --> 00:40:05,450
>> Ya, dan seperti yang saya katakan sebelumnya,
cara kita menyelesaikan tabrakan

794
00:40:05,450 --> 00:40:09,330
di hash kami tabel mengalami,
apa yang kita sebut, chaining.

795
00:40:09,330 --> 00:40:13,860
Jadi jika Anda mencoba untuk memasukkan beberapa
kata-kata yang dimulai dengan hal yang sama,

796
00:40:13,860 --> 00:40:16,145
Anda akan memiliki satu nilai hash.

797
00:40:16,145 --> 00:40:18,770
Alpukat dan apel, jika Anda sudah
menjalankannya melalui fungsi hash kami,

798
00:40:18,770 --> 00:40:21,450
akan memberi Anda
nomor yang sama, jumlah 0.

799
00:40:21,450 --> 00:40:24,550
Dan cara kita menyelesaikan yang
bahwa kita benar-benar dapat jenis menghubungkan mereka

800
00:40:24,550 --> 00:40:27,010
bersama-sama melalui daftar link.

801
00:40:27,010 --> 00:40:29,600
>> Dan dalam hal ini,
kalian dapat melihat jenis

802
00:40:29,600 --> 00:40:32,640
bagaimana struktur data yang
kami telah menetapkan sebelumnya

803
00:40:32,640 --> 00:40:35,870
seperti kismis terkait daftar jenis
dari dapat datang bersama-sama menjadi satu.

804
00:40:35,870 --> 00:40:38,860
Dan kemudian Anda dapat membuat jauh
struktur data yang lebih efisien

805
00:40:38,860 --> 00:40:43,350
yang dapat menangani jumlah yang lebih besar dari
data, yang secara dinamis mengubah ukuran tergantung

806
00:40:43,350 --> 00:40:44,870
pada kebutuhan Anda.

807
00:40:44,870 --> 00:40:45,620
Semua orang yang jelas?

808
00:40:45,620 --> 00:40:47,580
Semua orang semacam jelas
pada apa yang terjadi di sini?

809
00:40:47,580 --> 00:40:52,110
>> Jika saya ingin insert-- apa yang
buah yang dimulai dengan, saya tidak tahu,

810
00:40:52,110 --> 00:40:54,726
B, selain berry, pisang.

811
00:40:54,726 --> 00:40:55,710
>> AUDIENCE: Blackberry.

812
00:40:55,710 --> 00:40:57,910
>> ANDI PENG: Blackberry, blackberry.

813
00:40:57,910 --> 00:41:00,530
Dimana blackberry pergi di sini?

814
00:41:00,530 --> 00:41:04,251
Nah, kita benar-benar belum diurutkan
ini belum, tapi secara teoritis

815
00:41:04,251 --> 00:41:06,250
jika kita ingin memiliki ini
dalam urutan abjad,

816
00:41:06,250 --> 00:41:07,944
mana harus pergi blackberry?

817
00:41:07,944 --> 00:41:09,210
>> AUDIENCE: [tidak terdengar]

818
00:41:09,210 --> 00:41:11,100
>> ANDI PENG: Tepat, setelah di sini, kan?

819
00:41:11,100 --> 00:41:14,950
Tapi karena itu sangat sulit untuk
reorder-- Saya kira itu terserah kalian.

820
00:41:14,950 --> 00:41:17,920
Kalian bisa benar-benar
melaksanakan apa pun yang Anda inginkan.

821
00:41:17,920 --> 00:41:20,730
Cara yang lebih efisien
untuk melakukan hal ini mungkin

822
00:41:20,730 --> 00:41:24,570
akan memilah Anda terkait
daftar ke urutan abjad,

823
00:41:24,570 --> 00:41:26,520
dan jadi ketika Anda
memasukkan hal-hal, Anda ingin

824
00:41:26,520 --> 00:41:28,632
untuk memastikan untuk memasukkan mereka
dalam urutan abjad

825
00:41:28,632 --> 00:41:30,590
sehingga kemudian ketika Anda
mencoba untuk mencari mereka,

826
00:41:30,590 --> 00:41:32,410
Anda tidak harus melintasi segala sesuatu.

827
00:41:32,410 --> 00:41:35,290
Anda tahu persis di mana
itu, dan lebih mudah.

828
00:41:35,290 --> 00:41:39,100
>> Tapi jika Anda memiliki jenis
hal diselingi secara acak,

829
00:41:39,100 --> 00:41:41,420
Anda masih akan memiliki
untuk melintasi anyways.

830
00:41:41,420 --> 00:41:44,990
Dan jadi jika saya ingin hanya
masukkan blackberry sini

831
00:41:44,990 --> 00:41:47,470
dan saya ingin mencari
itu, aku tahu, oh, blackberry

832
00:41:47,470 --> 00:41:52,012
harus dimulai dengan indeks 1, jadi saya
tahu seketika hanya mencari pada 1.

833
00:41:52,012 --> 00:41:53,970
Dan kemudian saya dapat jenis
melintasi linked list

834
00:41:53,970 --> 00:41:56,120
sampai saya mendapatkan blackberry,
dan then-- ya?

835
00:41:56,120 --> 00:41:59,550
>> AUDIENCE: Jika Anda mencoba untuk create--
Saya kira seperti ini adalah hash sangat sederhana

836
00:41:59,550 --> 00:42:00,050
fungsi.

837
00:42:00,050 --> 00:42:02,835
Dan jika kita ingin melakukan
beberapa lapisan seperti itu,

838
00:42:02,835 --> 00:42:05,870
OK, kita ingin memisahkan ke
seperti semua huruf abjad

839
00:42:05,870 --> 00:42:09,040
dan sekali lagi seperti set
huruf abjad dalam itu,

840
00:42:09,040 --> 00:42:11,715
kita menempatkan seperti hash
tabel dalam tabel hash,

841
00:42:11,715 --> 00:42:13,256
atau seperti fungsi dalam fungsi?

842
00:42:13,256 --> 00:42:14,880
Atau itu--

843
00:42:14,880 --> 00:42:17,510
>> ANDI PENG: Jadi hash Anda
function-- tabel hash Anda

844
00:42:17,510 --> 00:42:19,360
dapat sebagai besar seperti yang Anda inginkan.

845
00:42:19,360 --> 00:42:21,930
Jadi dalam hal ini, saya pikir
itu sangat mudah, sangat

846
00:42:21,930 --> 00:42:25,320
sederhana bagi saya untuk hanya semacam berdasarkan
pada huruf dari kata pertama.

847
00:42:25,320 --> 00:42:28,690
Dan hanya ada 26 pilihan.

848
00:42:28,690 --> 00:42:32,650
Aku hanya bisa mendapatkan 26 pilihan dari
0-25 karena mereka hanya bisa

849
00:42:32,650 --> 00:42:36,510
mulai dari A sampai Z. Tapi Jika Anda ingin
menambahkan, mungkin, lebih kompleksitas

850
00:42:36,510 --> 00:42:39,260
atau lebih cepat menjalankan waktu untuk Anda
tabel hash, Anda benar-benar

851
00:42:39,260 --> 00:42:40,760
dapat melakukan segala macam hal.

852
00:42:40,760 --> 00:42:43,330
Anda dapat membuat Anda sendiri
persamaan yang memberikan

853
00:42:43,330 --> 00:42:48,000
distribusi yang lebih dalam Anda
kata-kata, maka ketika Anda mencari,

854
00:42:48,000 --> 00:42:49,300
itu akan menjadi lebih cepat.

855
00:42:49,300 --> 00:42:52,100
>> Ini benar-benar sampai kalian
bagaimana Anda ingin menerapkan itu.

856
00:42:52,100 --> 00:42:55,140
Anggap saja sebagai hanya ember.

857
00:42:55,140 --> 00:42:57,376
Jika saya ingin memiliki
26 ember, aku akan

858
00:42:57,376 --> 00:42:59,420
untuk menyelesaikan dalam ember.

859
00:42:59,420 --> 00:43:02,980
Tapi aku akan memiliki a bunch
barang di setiap kotak,

860
00:43:02,980 --> 00:43:05,890
jadi jika Anda ingin membuatnya
lebih cepat dan lebih efisien,

861
00:43:05,890 --> 00:43:07,190
biarkan aku memiliki seratus ember.

862
00:43:07,190 --> 00:43:09,290
>> Tapi kemudian Anda harus mencari tahu
cara untuk menyelesaikan masalah sehingga mereka

863
00:43:09,290 --> 00:43:11,040
di ember yang tepat mereka harus di.

864
00:43:11,040 --> 00:43:13,331
Tapi kemudian ketika Anda benar-benar
ingin melihat ember itu,

865
00:43:13,331 --> 00:43:16,410
itu jauh lebih cepat karena ada
hal yang kurang di setiap kotak.

866
00:43:16,410 --> 00:43:20,250
Dan, ya, itu benar-benar
trik untuk kalian di pset5

867
00:43:20,250 --> 00:43:22,360
adalah bahwa Anda akan
ditantang untuk hanya membuat

868
00:43:22,360 --> 00:43:26,170
apa yang paling efisien
Fungsi Anda bisa memikirkan untuk menjadi

869
00:43:26,170 --> 00:43:28,520
mampu menyimpan dan memeriksa nilai-nilai ini.

870
00:43:28,520 --> 00:43:30,840
>> Benar-benar sampai kalian
namun Anda ingin melakukannya,

871
00:43:30,840 --> 00:43:32,229
tapi itu titik benar-benar baik.

872
00:43:32,229 --> 00:43:34,520
Bahwa jenis logika Anda
ingin mulai berpikir tentang

873
00:43:34,520 --> 00:43:37,236
adalah, baik, kenapa tidak saya membuat lebih banyak ember.

874
00:43:37,236 --> 00:43:39,527
Dan kemudian saya harus mencari
hal yang kurang, dan kemudian mungkin aku

875
00:43:39,527 --> 00:43:41,640
memiliki fungsi hash yang berbeda.

876
00:43:41,640 --> 00:43:45,500
>> Ya, ada banyak cara untuk melakukan hal ini
pset, beberapa lebih cepat dari yang lain.

877
00:43:45,500 --> 00:43:50,630
Aku benar-benar akan hanya melihat bagaimana
cepat adalah yang tercepat kalian akan

878
00:43:50,630 --> 00:43:55,170
bisa mendapatkan fungsi Anda untuk bekerja.

879
00:43:55,170 --> 00:43:58,176
OK, semua orang di baik
chaining dan hash tabel?

880
00:43:58,176 --> 00:44:00,800
Ini benar-benar seperti sangat sederhana
Konsep jika Anda berpikir tentang hal itu.

881
00:44:00,800 --> 00:44:05,160
Semua itu adalah memisahkan apa pun
input Anda ke dalam ember,

882
00:44:05,160 --> 00:44:10,670
menyortir mereka, dan kemudian mencari
daftar yang ada yang terkait dengan.

883
00:44:10,670 --> 00:44:11,852
>> Keren.

884
00:44:11,852 --> 00:44:18,160
Baiklah, sekarang kita memiliki semacam berbeda
struktur data yang disebut pohon.

885
00:44:18,160 --> 00:44:20,850
Mari kita pergi dan berbicara tentang mencoba
yang jelas berbeda,

886
00:44:20,850 --> 00:44:22,330
tetapi dalam kategori yang sama.

887
00:44:22,330 --> 00:44:29,010
Pada dasarnya, semua pohon adalah bukan
pengorganisasian data dalam cara yang linear

888
00:44:29,010 --> 00:44:32,560
bahwa tabel hash does-- Anda
tahu, itu punya atas dan bawah sebuah

889
00:44:32,560 --> 00:44:37,900
dan kemudian Anda jenis menghubungkan off dari itu-- sebuah
pohon memiliki atas yang Anda sebut akar,

890
00:44:37,900 --> 00:44:40,220
dan kemudian memiliki daun di sekitar itu.

891
00:44:40,220 --> 00:44:42,390
>> Dan sehingga semua yang Anda miliki di sini
hanya node atas

892
00:44:42,390 --> 00:44:45,980
yang menunjuk ke node lain, yang poin
untuk lebih node, dan seterusnya dan sebagainya.

893
00:44:45,980 --> 00:44:48,130
Dan sehingga Anda hanya memiliki cabang membelah.

894
00:44:48,130 --> 00:44:53,255
Ini hanya cara yang berbeda pengorganisasian
data, dan karena kita menyebutnya pohon,

895
00:44:53,255 --> 00:44:56,270
kalian hanya-- itu hanya
dimodelkan untuk terlihat seperti pohon.

896
00:44:56,270 --> 00:44:57,670
Itulah mengapa kami menyebutnya pohon.

897
00:44:57,670 --> 00:44:59,370
>> Tabel hash terlihat seperti meja.

898
00:44:59,370 --> 00:45:01,310
Sebuah pohon hanya tampak seperti pohon.

899
00:45:01,310 --> 00:45:03,300
Semua itu adalah adalah terpisah
cara mengatur node

900
00:45:03,300 --> 00:45:06,020
tergantung pada apa kebutuhan Anda.

901
00:45:06,020 --> 00:45:11,810
>> Jadi Anda memiliki akar dan
maka Anda memiliki daun.

902
00:45:11,810 --> 00:45:15,380
Cara yang kita bisa sangat
berpikir tentang hal ini adalah pohon biner,

903
00:45:15,380 --> 00:45:18,150
pohon biner hanya
jenis tertentu pohon

904
00:45:18,150 --> 00:45:22,450
di mana setiap node hanya poin
untuk, di max, dua node lainnya.

905
00:45:22,450 --> 00:45:25,434
Dan jadi di sini Anda memiliki yang berbeda
simetri di pohon Anda

906
00:45:25,434 --> 00:45:28,600
yang membuatnya lebih mudah untuk jenis terlihat
apa nilai Anda karena Anda

907
00:45:28,600 --> 00:45:30,150
selalu kiri atau kanan.

908
00:45:30,150 --> 00:45:33,150
Tidak pernah seperti sepertiga dari kiri
kiri atau keempat dari kiri.

909
00:45:33,150 --> 00:45:36,358
Itu hanya Anda memiliki kiri dan kanan sebuah
dan Anda dapat mencari salah satu dari dua.

910
00:45:36,358 --> 00:45:38,980
Dan jadi mengapa ini berguna?

911
00:45:38,980 --> 00:45:40,980
Cara bahwa ini adalah
berguna adalah jika Anda sedang mencari

912
00:45:40,980 --> 00:45:42,890
untuk mencari melalui nilai-nilai, kan?

913
00:45:42,890 --> 00:45:45,640
Daripada menerapkan biner
cari di array kesalahan,

914
00:45:45,640 --> 00:45:49,260
jika Anda ingin dapat memasukkan node
dan mengambil node di akan dan juga

915
00:45:49,260 --> 00:45:52,185
melestarikan pencarian
kapasitas pencarian biner.

916
00:45:52,185 --> 00:45:54,560
Jadi dengan cara ini, kami jenis
tricking-- ingat ketika kita

917
00:45:54,560 --> 00:45:56,530
mengatakan daftar terkait tidak bisa pencarian biner?

918
00:45:56,530 --> 00:46:01,700
Kami semacam menciptakan struktur data
yang trik yang dalam bekerja.

919
00:46:01,700 --> 00:46:05,034
>> Dan daftar jadi karena terkait yang linear,
mereka hanya menghubungkan satu demi satu.

920
00:46:05,034 --> 00:46:06,950
Kita dapat memiliki jenis
jenis yang berbeda dari pointer

921
00:46:06,950 --> 00:46:09,408
saat itu untuk node yang berbeda
yang dapat membantu kami dengan pencarian.

922
00:46:09,408 --> 00:46:12,590
Dan jadi di sini, jika saya ingin
memiliki pohon pencarian biner,

923
00:46:12,590 --> 00:46:14,090
Saya tahu bahwa saya tengah jika 55.

924
00:46:14,090 --> 00:46:18,280
Aku hanya akan membuat yang
sebagai tengah saya, sebagai root saya,

925
00:46:18,280 --> 00:46:20,770
dan kemudian aku akan memiliki
nilai-nilai spin off itu.

926
00:46:20,770 --> 00:46:25,610
>> Jadi di sini, jika aku akan mencari
nilai 66, saya bisa mulai 55.

927
00:46:25,610 --> 00:46:27,310
Ini 66 besar dari 55?

928
00:46:27,310 --> 00:46:30,970
Ya itu, jadi aku tahu aku mus mencari
i n pointer kanan pohon ini.

929
00:46:30,970 --> 00:46:32,440
Aku pergi ke 77.

930
00:46:32,440 --> 00:46:35,367
OK, adalah kurang dari 66 atau lebih besar dari 77?

931
00:46:35,367 --> 00:46:37,950
Ini kurang dari, sehingga Anda tahu, oh,
yang harus menjadi simpul kiri.

932
00:46:37,950 --> 00:46:41,410
>> Dan jadi di sini kita jenis melestarikan
semua hal-hal besar tentang array,

933
00:46:41,410 --> 00:46:44,420
jadi seperti Resize dinamis
benda, menjadi

934
00:46:44,420 --> 00:46:49,530
mampu menyisipkan dan menghapus di akan,
tanpa harus khawatir tentang tetap

935
00:46:49,530 --> 00:46:50,370
jumlah ruang.

936
00:46:50,370 --> 00:46:52,820
Kami masih melestarikan semua
hal-hal yang indah

937
00:46:52,820 --> 00:46:57,140
sementara juga mampu melestarikan
log dan waktu pencarian biner mencari

938
00:46:57,140 --> 00:47:00,450
bahwa kami hanya sebelumnya
bisa mendapatkan frase.

939
00:47:00,450 --> 00:47:06,310
>> Struktur data yang dingin, jenis
kompleks untuk melaksanakan, node.

940
00:47:06,310 --> 00:47:08,311
Seperti yang Anda lihat, semua itu
adalah struct node

941
00:47:08,311 --> 00:47:10,143
adalah bahwa Anda memiliki kiri
dan pointer tepat.

942
00:47:10,143 --> 00:47:11,044
Itu semua itu.

943
00:47:11,044 --> 00:47:12,960
Jadi bukan hanya
memiliki x atau sebelumnya.

944
00:47:12,960 --> 00:47:15,920
Anda memiliki kiri atau kanan, dan kemudian
Anda dapat jenis menghubungkan mereka bersama-sama

945
00:47:15,920 --> 00:47:16,836
Namun Anda memilih demikian.

946
00:47:16,836 --> 00:47:21,080

947
00:47:21,080 --> 00:47:24,270
>> OK, kita benar-benar akan
hanya mengambil beberapa menit.

948
00:47:24,270 --> 00:47:25,790
Jadi kita akan pergi ke sini.

949
00:47:25,790 --> 00:47:28,270
Seperti yang saya katakan sebelumnya,
Aku agak menjelaskan

950
00:47:28,270 --> 00:47:31,520
logika di balik bagaimana kita
akan mencari melalui ini.

951
00:47:31,520 --> 00:47:33,860
Kami akan mencoba
pseudocoding keluar ini untuk melihat

952
00:47:33,860 --> 00:47:38,000
jika kita bisa jenis menerapkan
Logika yang sama dari pencarian biner

953
00:47:38,000 --> 00:47:40,055
untuk berbagai jenis struktur data.

954
00:47:40,055 --> 00:47:45,049
Jika kalian ingin mengambil seperti pasangan
menit untuk hanya berpikir tentang hal ini.

955
00:47:45,049 --> 00:48:45,927

956
00:48:45,927 --> 00:48:46,925
OKE.

957
00:48:46,925 --> 00:48:51,407
Baiklah, aku akan
sebenarnya hanya memberikan the-- tidak,

958
00:48:51,407 --> 00:48:52,990
kita akan berbicara tentang pseudocode pertama.

959
00:48:52,990 --> 00:48:56,580
Jadi tidak ada yang ingin
untuk memberikan menusuk apa

960
00:48:56,580 --> 00:49:02,100
hal pertama yang Anda ingin lakukan ketika
Anda memulai pencarian adalah?

961
00:49:02,100 --> 00:49:04,460
Jika kita sedang mencari
nilai 66, apa

962
00:49:04,460 --> 00:49:07,940
hal pertama yang kita ingin lakukan jika
kami ingin mencari biner pohon ini?

963
00:49:07,940 --> 00:49:10,760
>> AUDIENCE: Anda ingin terlihat benar
dan melihat kiri dan melihat [tidak terdengar]

964
00:49:10,760 --> 00:49:11,230
jumlah yang lebih besar.

965
00:49:11,230 --> 00:49:12,271
>> ANDI PENG: Ya, persis.

966
00:49:12,271 --> 00:49:15,350
Jadi Anda akan melihat akar Anda.

967
00:49:15,350 --> 00:49:18,180
Ada banyak cara Anda dapat menghubungi
itu, orang tua simpul Anda katakan.

968
00:49:18,180 --> 00:49:21,317
Saya ingin mengatakan akar karena
itu seperti akar pohon.

969
00:49:21,317 --> 00:49:23,400
Anda akan melihat
simpul akar Anda, dan Anda

970
00:49:23,400 --> 00:49:26,940
akan melihat adalah 66 besar
dari atau kurang dari 55.

971
00:49:26,940 --> 00:49:30,360
Dan jika itu lebih besar dari, baik, itu adalah
lebih besar dari, di mana kita ingin melihat?

972
00:49:30,360 --> 00:49:32,000
Di mana kita ingin mencari sekarang, kan?

973
00:49:32,000 --> 00:49:34,340
Kami ingin mencari
bagian kanan pohon ini.

974
00:49:34,340 --> 00:49:38,390
>> Jadi kita miliki, nyaman, sebuah
pointer yang menunjuk ke kanan.

975
00:49:38,390 --> 00:49:44,325
Dan kemudian kita dapat mengatur
akar baru kami untuk menjadi 77.

976
00:49:44,325 --> 00:49:46,450
Kami hanya bisa pergi ke mana pun
pointer menunjuk.

977
00:49:46,450 --> 00:49:49,100
Nah, oh, di sini kita mulai
pada 77, dan kami hanya bisa

978
00:49:49,100 --> 00:49:51,172
melakukan ini secara rekursif lagi dan lagi.

979
00:49:51,172 --> 00:49:52,880
Dengan cara ini, Anda jenis
dari memiliki fungsi.

980
00:49:52,880 --> 00:49:57,430
Anda memiliki cara untuk mencari yang Anda
hanya dapat mengulangi berulang-ulang,

981
00:49:57,430 --> 00:50:02,720
tergantung di mana Anda ingin melihat
sampai Anda akhirnya mendapatkan nilai

982
00:50:02,720 --> 00:50:04,730
yang Anda cari.

983
00:50:04,730 --> 00:50:05,230
Masuk akal?

984
00:50:05,230 --> 00:50:07,800
>> Saya akan menunjukkan Anda sebenarnya
kode, dan itu banyak kode.

985
00:50:07,800 --> 00:50:08,674
Tidak perlu panik.

986
00:50:08,674 --> 00:50:09,910
Kita akan berbicara melalui itu.

987
00:50:09,910 --> 00:50:13,410

988
00:50:13,410 --> 00:50:14,020
>> Sebenarnya tidak.

989
00:50:14,020 --> 00:50:15,061
Itu hanya pseudocode.

990
00:50:15,061 --> 00:50:17,860
OK, itu hanya pseudocode,
yang sedikit rumit,

991
00:50:17,860 --> 00:50:19,751
tapi itu benar-benar baik-baik saja.

992
00:50:19,751 --> 00:50:21,000
Semua orang berikut bersama di sini?

993
00:50:21,000 --> 00:50:24,260
Jika akar adalah nol, pulang
palsu karena itu berarti

994
00:50:24,260 --> 00:50:26,850
Anda bahkan tidak punya apa-apa di sana.

995
00:50:26,850 --> 00:50:31,376
>> Jika akar n adalah nilai, sehingga jika
terjadi menjadi salah satu yang sedang melihat,

996
00:50:31,376 --> 00:50:34,000
maka Anda akan kembali benar
karena Anda tahu Anda menemukannya.

997
00:50:34,000 --> 00:50:36,250
Tetapi jika nilai kurang
dari akar n, kau

998
00:50:36,250 --> 00:50:38,332
akan mencari kiri
anak atau daun kiri,

999
00:50:38,332 --> 00:50:39,540
apa pun yang Anda ingin menyebutnya.

1000
00:50:39,540 --> 00:50:41,750
Dan jika nilai lebih besar dari akar,
Anda akan mencari pohon yang tepat,

1001
00:50:41,750 --> 00:50:44,610
kemudian hanya menjalankan fungsi
melalui pencarian lagi.

1002
00:50:44,610 --> 00:50:48,037
>> Dan jika akar adalah nol, bahwa
berarti Anda telah mencapai akhir?

1003
00:50:48,037 --> 00:50:50,120
Itu berarti Anda tidak memiliki
lebih daun lebih untuk mencari,

1004
00:50:50,120 --> 00:50:52,230
maka Anda tahu, oh, saya
rasa itu bukan di sini

1005
00:50:52,230 --> 00:50:55,063
karena setelah saya telah melihat melalui
seluruh hal dan itu tidak ada di sini,

1006
00:50:55,063 --> 00:50:56,930
itu hanya mungkin tidak berada di sini.

1007
00:50:56,930 --> 00:50:58,350
>> Apakah itu masuk akal untuk semua orang?

1008
00:50:58,350 --> 00:51:03,230
Jadi seperti pencarian biner melestarikan
kemampuan daftar terkait.

1009
00:51:03,230 --> 00:51:09,200
Keren, dan jenis kedua
dari struktur data kalian

1010
00:51:09,200 --> 00:51:13,180
dapat mencoba menerapkan pada pset Anda,
Anda hanya harus memilih satu metode.

1011
00:51:13,180 --> 00:51:19,430
Tapi mungkin metode alternatif untuk
tabel hash adalah apa yang kita sebut trie.

1012
00:51:19,430 --> 00:51:24,080
>> Semua trie adalah adalah
jenis tertentu pohon yang

1013
00:51:24,080 --> 00:51:28,600
memiliki nilai-nilai yang pergi ke nilai-nilai lain.

1014
00:51:28,600 --> 00:51:31,450
Jadi alih-alih memiliki biner
pohon dalam arti bahwa hanya satu

1015
00:51:31,450 --> 00:51:35,940
Hal dapat menunjukkan dua, Anda dapat memiliki
satu hal titik ke banyak, banyak hal.

1016
00:51:35,940 --> 00:51:39,450
Anda pada dasarnya memiliki array
dalam yang Anda simpan

1017
00:51:39,450 --> 00:51:41,790
pointer yang menunjuk ke array lain.

1018
00:51:41,790 --> 00:51:45,210

1019
00:51:45,210 --> 00:51:49,460
>> Jadi simpul dari bagaimana kita
akan menentukan trie

1020
00:51:49,460 --> 00:51:52,590
adalah kita ingin memiliki
Boolean, c kata, kan?

1021
00:51:52,590 --> 00:51:54,920
Jadi node adalah Boolean
seperti benar atau salah,

1022
00:51:54,920 --> 00:51:58,490
pertama-tama di kepala
array, apakah ini sebuah kata?

1023
00:51:58,490 --> 00:52:03,620
Kedua, Anda ingin memiliki pointer
apa pun sisa dari mereka adalah.

1024
00:52:03,620 --> 00:52:07,470
Sebuah sedikit rumit, sedikit abstrak, tapi
Saya akan menjelaskan apa yang segala cara.

1025
00:52:07,470 --> 00:52:13,800
>> Jadi di sini, di bagian atas, jika Anda
memiliki sebuah array menyatakan sudah,

1026
00:52:13,800 --> 00:52:17,040
node di mana Anda memiliki sebuah Boolean
nilai yang disimpan di depan

1027
00:52:17,040 --> 00:52:19,490
yang memberitahu Anda apakah ini sebuah kata?

1028
00:52:19,490 --> 00:52:20,520
Apakah ini bukan sebuah kata?

1029
00:52:20,520 --> 00:52:23,240
Dan kemudian Anda memiliki
sisa array yang

1030
00:52:23,240 --> 00:52:26,040
sebenarnya menyimpan semua
kemungkinan apa itu bisa.

1031
00:52:26,040 --> 00:52:28,660
Jadi, misalnya, seperti
di atas Anda memiliki

1032
00:52:28,660 --> 00:52:32,140
hal pertama yang mengatakan benar atau
palsu, ya atau tidak, ini adalah sebuah kata.

1033
00:52:32,140 --> 00:52:38,130
>> Dan kemudian Anda memiliki 0 sampai 26 dari
huruf yang dapat Anda simpan.

1034
00:52:38,130 --> 00:52:42,790
Jika saya ingin mencari disini
untuk kelelawar, aku pergi ke atas

1035
00:52:42,790 --> 00:52:49,200
dan saya mencari B. Saya menemukan B di saya
array, dan jadi saya tahu, OK, adalah B kata?

1036
00:52:49,200 --> 00:52:53,010
B adalah bukan kata, sehingga dengan demikian
Aku harus terus mencari.

1037
00:52:53,010 --> 00:52:56,410
Aku pergi dari B, dan saya melihat ke
pointer yang menunjuk ke arah B

1038
00:52:56,410 --> 00:53:00,900
dan saya melihat array lain informasi,
struktur yang sama yang kita miliki sebelumnya.

1039
00:53:00,900 --> 00:53:05,240
>> Dan di sini-oh, berikutnya
surat di [tidak terdengar] adalah A.

1040
00:53:05,240 --> 00:53:07,210
Jadi kita melihat dalam array itu.

1041
00:53:07,210 --> 00:53:10,860
Kami menemukan nilai delapan,
dan kemudian kita melihat untuk melihat, oh,

1042
00:53:10,860 --> 00:53:12,840
hey, adalah bahwa kata, adalah B-A kata?

1043
00:53:12,840 --> 00:53:13,807
Ini bukan sebuah kata.

1044
00:53:13,807 --> 00:53:14,890
Kita harus terus mencari.

1045
00:53:14,890 --> 00:53:17,850
>> Dan kemudian kita melihat ke mana
pointer A poin,

1046
00:53:17,850 --> 00:53:21,130
dan itu menunjukkan cara lain di
yang kita memiliki nilai lebih yang disimpan.

1047
00:53:21,130 --> 00:53:24,150
Dan akhirnya, kita bisa
B-A-T, yang merupakan sebuah kata.

1048
00:53:24,150 --> 00:53:25,970
Dan sehingga waktu berikutnya
Anda melihat, Anda akan

1049
00:53:25,970 --> 00:53:30,850
untuk memiliki cek, ya,
Fungsi Boolean ini benar.

1050
00:53:30,850 --> 00:53:35,450
Dan dalam arti kami jenis
memiliki pohon dengan array.

1051
00:53:35,450 --> 00:53:39,890
>> Jadi Anda dapat mencari jenis turun.

1052
00:53:39,890 --> 00:53:43,650
Daripada hashing fungsi dan
menugaskan nilai dengan linked list,

1053
00:53:43,650 --> 00:53:49,190
Anda hanya dapat menerapkan
trie yang mencari downwords.

1054
00:53:49,190 --> 00:53:50,850
Benar-benar, benar-benar rumit hal.

1055
00:53:50,850 --> 00:53:54,060
Tidak mudah untuk berpikir tentang karena aku seperti
meludah begitu banyak struktur data keluar

1056
00:53:54,060 --> 00:53:58,710
pada Anda, tetapi tidak semua orang jenis
memahami bagaimana logika ini bekerja?

1057
00:53:58,710 --> 00:54:01,920
>> OK keren.

1058
00:54:01,920 --> 00:54:05,600
Jadi B-A-T, dan kemudian
Anda akan mencari.

1059
00:54:05,600 --> 00:54:07,940
Lain kali Anda akan
untuk melihat, oh, hei, itu benar,

1060
00:54:07,940 --> 00:54:09,273
sehingga aku tahu ini harus menjadi sebuah kata.

1061
00:54:09,273 --> 00:54:12,030

1062
00:54:12,030 --> 00:54:13,770
>> Hal yang sama untuk kebun binatang.

1063
00:54:13,770 --> 00:54:17,960
Jadi, inilah hal yang sekarang, jika kita
ingin mencari kebun binatang, sekarang,

1064
00:54:17,960 --> 00:54:20,780
Saat ini kebun binatang bukanlah
kata dalam kamus kami

1065
00:54:20,780 --> 00:54:25,300
karena, seperti kalian lihat,
Tempat pertama yang harus kita Boolean sebuah

1066
00:54:25,300 --> 00:54:28,590
kembali benar adalah pada akhir zoom.

1067
00:54:28,590 --> 00:54:30,430
Kami memiliki Z-O-O-M.

1068
00:54:30,430 --> 00:54:33,900
>> Dan jadi di sini, kita tidak benar-benar memiliki
kata, kebun binatang, dalam kamus kami

1069
00:54:33,900 --> 00:54:36,070
karena kotak ini tidak dicentang.

1070
00:54:36,070 --> 00:54:39,540
Jadi komputer tidak
tahu bahwa kebun binatang adalah sebuah kata

1071
00:54:39,540 --> 00:54:42,430
karena cara bahwa kita sudah
disimpan itu, hanya zoom sini

1072
00:54:42,430 --> 00:54:44,920
sebenarnya memiliki nilai Boolean
yang telah berubah benar.

1073
00:54:44,920 --> 00:54:49,380
Jadi jika kita ingin memasukkan
kata, kebun binatang, dalam kamus kami,

1074
00:54:49,380 --> 00:54:51,770
bagaimana kita akan pergi untuk melakukan itu?

1075
00:54:51,770 --> 00:54:55,960
Apa yang harus kita lakukan untuk memastikan kami
komputer tahu bahwa Z-O-O adalah sebuah kata

1076
00:54:55,960 --> 00:54:58,130
dan bukan kata pertama adalah Z-O-O-M?

1077
00:54:58,130 --> 00:54:59,360
>> AUDIENCE: [tidak terdengar]

1078
00:54:59,360 --> 00:55:01,450
>> ANDI PENG: Tepat, kita
ingin memastikan bahwa ini

1079
00:55:01,450 --> 00:55:07,890
di sini, bahwa nilai Boolean adalah
diperiksa bahwa hal itu benar.

1080
00:55:07,890 --> 00:55:13,297
Z-O-O, maka kita akan memeriksa bahwa,
sehingga kita tahu persis, hei, kebun binatang adalah sebuah kata.

1081
00:55:13,297 --> 00:55:15,380
Aku akan memberitahu
komputer bahwa itu sebuah kata sehingga

1082
00:55:15,380 --> 00:55:18,000
bahwa ketika cek komputer,
ia tahu bahwa kebun binatang adalah sebuah kata.

1083
00:55:18,000 --> 00:55:21,269
>> Karena mengingat semua data ini
struktur, itu sangat mudah bagi kita

1084
00:55:21,269 --> 00:55:22,310
mengatakan, oh, kelelawar sebuah kata.

1085
00:55:22,310 --> 00:55:22,851
Zoo sebuah kata.

1086
00:55:22,851 --> 00:55:23,611
Zoom sebuah kata.

1087
00:55:23,611 --> 00:55:25,860
Tetapi ketika Anda sedang membangun itu,
komputer tidak tahu.

1088
00:55:25,860 --> 00:55:28,619
>> Jadi, Anda harus memberitahu persis
pada titik ini adalah sebuah kata?

1089
00:55:28,619 --> 00:55:29,910
Pada titik itu bukan kata?

1090
00:55:29,910 --> 00:55:31,784
Dan pada titik apa yang saya
perlu hal-hal mencari,

1091
00:55:31,784 --> 00:55:34,000
dan pada titik yang harus saya pergi berikutnya?

1092
00:55:34,000 --> 00:55:37,010
Semua orang jelas itu?

1093
00:55:37,010 --> 00:55:39,540
Keren.

1094
00:55:39,540 --> 00:55:42,530
>> Dan kemudian datang
masalah bagaimana akan kita

1095
00:55:42,530 --> 00:55:45,560
pergi tentang memasukkan sesuatu
bahwa sebenarnya tidak ada?

1096
00:55:45,560 --> 00:55:49,090
Jadi mari kita hanya mengatakan kita ingin menyisipkan
kata, mandi, ke trie kami.

1097
00:55:49,090 --> 00:55:53,589
Seperti kalian bisa melihat seperti saat ini
semua yang kita miliki sekarang adalah B-A-T,

1098
00:55:53,589 --> 00:55:55,630
dan struktur ini data baru
ada memiliki setengah liter yang

1099
00:55:55,630 --> 00:55:59,740
menunjuk nol karena kita berasumsi
bahwa, oh, tidak ada kata-kata setelah B-A-T,

1100
00:55:59,740 --> 00:56:02,530
mengapa kita perlu menjaga
memiliki hal-hal setelah T. yang

1101
00:56:02,530 --> 00:56:06,581
>> Tapi masalahnya muncul jika kita melakukan Anda
ingin memiliki sebuah kata yang datang setelah

1102
00:56:06,581 --> 00:56:07,080
T ini.

1103
00:56:07,080 --> 00:56:09,500
Jika Anda memiliki mandi, Anda
akan ingin H tepat.

1104
00:56:09,500 --> 00:56:13,290
Dan cara kita akan melakukan itu adalah
kita akan membuat simpul terpisah.

1105
00:56:13,290 --> 00:56:16,840
Kami tidak membagikan jumlah berapapun
memori untuk array baru ini,

1106
00:56:16,840 --> 00:56:20,720
dan kita akan menetapkan kembali pointer.

1107
00:56:20,720 --> 00:56:22,947
>> Kita akan menetapkan
H, Pertama-tama, null ini,

1108
00:56:22,947 --> 00:56:24,030
kita akan menyingkirkan.

1109
00:56:24,030 --> 00:56:26,590
Kita akan memiliki
ke bawah titik H.

1110
00:56:26,590 --> 00:56:30,600
Jika kita melihat H, kami ingin
untuk pergi ke tempat lain.

1111
00:56:30,600 --> 00:56:33,910
>> Di sini, kita kemudian dapat memeriksa off ya.

1112
00:56:33,910 --> 00:56:38,170
Jika kita memukul H setelah T, oh,
maka kita tahu bahwa ini adalah sebuah kata.

1113
00:56:38,170 --> 00:56:41,110
Boolean akan kembali benar.

1114
00:56:41,110 --> 00:56:42,950
Semua orang yang jelas tentang bagaimana yang terjadi?

1115
00:56:42,950 --> 00:56:45,110
OKE.

1116
00:56:45,110 --> 00:56:47,214
>> Jadi pada dasarnya, semua
struktur data ini

1117
00:56:47,214 --> 00:56:50,130
bahwa kita sudah lebih hari ini, saya sudah
pergi atas mereka benar-benar, benar-benar cepat

1118
00:56:50,130 --> 00:56:52,192
dan tidak banyak
detail, dan itu OK.

1119
00:56:52,192 --> 00:56:53,900
Setelah Anda mulai bermain-main
dengan itu, Anda akan

1120
00:56:53,900 --> 00:56:55,733
melacak di mana
semua pointer,

1121
00:56:55,733 --> 00:56:58,060
apa yang terjadi di Anda
struktur data, dan lain-lain.

1122
00:56:58,060 --> 00:56:59,810
Mereka akan sangat berguna,
dan terserah kepada Anda

1123
00:56:59,810 --> 00:57:03,890
orang untuk benar-benar mengetahui bagaimana
Anda ingin menerapkan hal.

1124
00:57:03,890 --> 00:57:07,650
>> Dan pset4, dari 5-- oh, itu salah.

1125
00:57:07,650 --> 00:57:10,140
Pset5 adalah salah eja.

1126
00:57:10,140 --> 00:57:13,710
Seperti yang saya katakan sebelumnya, Anda akan, sekali
lagi, men-download kode sumber dari kami.

1127
00:57:13,710 --> 00:57:16,210
Ada akan menjadi tiga utama
hal yang Anda akan men-download.

1128
00:57:16,210 --> 00:57:18,470
Anda akan men-download kamus,
kers, dan teks.

1129
00:57:18,470 --> 00:57:21,660
>> Semua hal-hal yang berada
baik kamus kata-kata

1130
00:57:21,660 --> 00:57:25,190
bahwa kami ingin Anda untuk memeriksa
atau tes informasi

1131
00:57:25,190 --> 00:57:26,930
bahwa kami ingin Anda untuk mengeja cek.

1132
00:57:26,930 --> 00:57:29,670
Dan kamus
kami memberikan Anda akan

1133
00:57:29,670 --> 00:57:34,870
untuk memberikan kata-kata yang sebenarnya yang kita inginkan
Anda untuk menyimpan entah dengan cara yang

1134
00:57:34,870 --> 00:57:36,530
lebih efisien daripada sebuah array.

1135
00:57:36,530 --> 00:57:38,470
Dan kemudian teks yang
akan menjadi apa yang kita

1136
00:57:38,470 --> 00:57:43,900
meminta Anda untuk memeriksa ejaan untuk memastikan
semua kata-kata ada kata-kata yang nyata.

1137
00:57:43,900 --> 00:57:47,970
>> Dan tiga blok dari
program yang akan kami berikan

1138
00:57:47,970 --> 00:57:51,130
disebut dictionary.c,
dictionary.h, dan speller.c.

1139
00:57:51,130 --> 00:57:56,500
Dan sehingga semua dictionary.c dilakukan adalah
apa yang Anda diminta untuk menerapkan.

1140
00:57:56,500 --> 00:57:57,880
Ini beban kata-kata.

1141
00:57:57,880 --> 00:58:02,000
Ini mantra cek mereka, dan itu membuat yakin
bahwa segala sesuatu dimasukkan dengan benar.

1142
00:58:02,000 --> 00:58:05,180
>> diction.h hanyalah sebuah file library
yang menyatakan semua fungsi tersebut.

1143
00:58:05,180 --> 00:58:07,650
Dan speller.c, kami akan memberikan Anda.

1144
00:58:07,650 --> 00:58:09,290
Anda tidak perlu memodifikasi itu.

1145
00:58:09,290 --> 00:58:14,290
Semua speller.c dilakukan adalah mengambil,
beban itu, memeriksa kecepatan itu,

1146
00:58:14,290 --> 00:58:19,190
tes benchmark seperti bagaimana
cepat Anda dapat melakukan hal-hal.

1147
00:58:19,190 --> 00:58:20,410
>> Ini ejaan a.

1148
00:58:20,410 --> 00:58:23,920
Hanya jangan main-main dengan hal itu, tapi membuat
Pastikan Anda memahami apa yang dilakukannya.

1149
00:58:23,920 --> 00:58:28,090
Kami menggunakan fungsi yang disebut getrusage yang
menguji kinerja mantra Anda

1150
00:58:28,090 --> 00:58:28,590
pemeriksa.

1151
00:58:28,590 --> 00:58:32,200
Semua hal ini pada dasarnya menguji
saat segala sesuatu dalam kamus Anda,

1152
00:58:32,200 --> 00:58:33,680
jadi pastikan Anda memahami itu.

1153
00:58:33,680 --> 00:58:36,660
Hati-hati untuk tidak main-main dengan hal itu atau
hal lain tidak akan berjalan dengan baik.

1154
00:58:36,660 --> 00:58:39,740

1155
00:58:39,740 --> 00:58:44,170
>> Dan sebagian besar tantangan ini adalah untuk
kalian benar-benar memodifikasi dictionary.c.

1156
00:58:44,170 --> 00:58:48,526
Kami akan memberikan
140.000 kata dalam kamus.

1157
00:58:48,526 --> 00:58:50,900
Kami akan memberikan teks
file yang memiliki kata-kata,

1158
00:58:50,900 --> 00:58:54,840
dan kami ingin Anda dapat mengatur
mereka ke dalam tabel hash atau trie

1159
00:58:54,840 --> 00:58:58,140
karena ketika kami meminta Anda untuk mengeja
check-- bayangkan jika Anda mantra

1160
00:58:58,140 --> 00:59:00,690
memeriksa seperti Odyssey Homer.

1161
00:59:00,690 --> 00:59:03,010
Ini seperti besar, tes besar ini.

1162
00:59:03,010 --> 00:59:05,190
>> Bayangkan jika setiap satu
kata yang Anda harus melihat

1163
00:59:05,190 --> 00:59:08,100
melalui array 140.000 nilai.

1164
00:59:08,100 --> 00:59:10,350
Yang akan mengambil selamanya
untuk mesin Anda untuk menjalankan.

1165
00:59:10,350 --> 00:59:14,490
Itulah sebabnya kami ingin mengatur kami
data ke dalam struktur data yang lebih efisien

1166
00:59:14,490 --> 00:59:17,270
seperti tabel hash atau trie.

1167
00:59:17,270 --> 00:59:20,700
Dan kemudian kalian bisa jenis
ketika Anda mencari akses

1168
00:59:20,700 --> 00:59:22,570
hal yang lebih mudah dan lebih cepat.

1169
00:59:22,570 --> 00:59:24,934
>> Dan jadi hati-hati untuk menyelesaikan tabrakan.

1170
00:59:24,934 --> 00:59:27,350
Anda akan mendapatkan bunch
dari kata-kata yang mulai dengan A.

1171
00:59:27,350 --> 00:59:29,957
Anda akan mendapatkan kata-kata sekelompok
yang dimulai dengan B. Sampai Anda

1172
00:59:29,957 --> 00:59:31,290
orang bagaimana Anda ingin mengatasinya.

1173
00:59:31,290 --> 00:59:34,144
Mungkin masih ada lagi
fungsi hash efisien

1174
00:59:34,144 --> 00:59:36,810
dari sekedar huruf pertama dari
sesuatu, dan itu terserah Anda

1175
00:59:36,810 --> 00:59:38,190
orang untuk jenis melakukan apapun yang Anda inginkan.

1176
00:59:38,190 --> 00:59:40,148
>> Mungkin Anda ingin menambahkan
semua huruf bersama-sama.

1177
00:59:40,148 --> 00:59:43,410
Mungkin Anda ingin seperti melakukan hal-hal aneh
untuk memperhitungkan jumlah huruf,

1178
00:59:43,410 --> 00:59:43,970
apapun.

1179
00:59:43,970 --> 00:59:45,386
Sampai kalian bagaimana Anda ingin melakukannya.

1180
00:59:45,386 --> 00:59:49,262
Jika Anda ingin melakukan tabel hash, jika Anda
ingin mencoba trie, benar-benar terserah pada Anda.

1181
00:59:49,262 --> 00:59:52,470
Saya akan memperingatkan Anda di depan waktu itu
trie biasanya sedikit lebih sulit

1182
00:59:52,470 --> 00:59:54,520
hanya karena ada banyak
lebih pointer untuk melacak.

1183
00:59:54,520 --> 00:59:55,645
Tapi benar-benar sampai kalian.

1184
00:59:55,645 --> 00:59:58,742
Ini jauh lebih efisien
dalam kebanyakan kasus.

1185
00:59:58,742 --> 01:00:01,450
Anda ingin benar-benar dapat menjaga
melacak semua pointer Anda.

1186
01:00:01,450 --> 01:00:03,850
Seperti melakukan hal yang sama
bahwa saya lakukan di sini.

1187
01:00:03,850 --> 01:00:06,871
Ketika Anda mencoba untuk memasukkan
nilai ke dalam tabel hash atau menghapus,

1188
01:00:06,871 --> 01:00:08,620
pastikan bahwa Anda
benar-benar melacak

1189
01:00:08,620 --> 01:00:11,860
dari mana segala sesuatu karena
itu benar-benar mudah untuk jika saya

1190
01:00:11,860 --> 01:00:14,727
mencoba untuk menyisipkan seperti kata, andy.

1191
01:00:14,727 --> 01:00:16,810
Mari kita hanya mengatakan bahwa adalah
kata nyata, kata, andy,

1192
01:00:16,810 --> 01:00:19,640
dalam daftar raksasa A kata.

1193
01:00:19,640 --> 01:00:22,450
>> Jika saya hanya kebetulan menetapkan kembali
yang salah pointer, oops,

1194
01:00:22,450 --> 01:00:24,940
ada pergi keseluruhan
sisa linked list saya.

1195
01:00:24,940 --> 01:00:26,897
Sekarang satu-satunya kata yang saya
miliki adalah andy, dan sekarang

1196
01:00:26,897 --> 01:00:29,230
semua kata lain dalam
kamus telah hilang.

1197
01:00:29,230 --> 01:00:31,370
Dan sehingga Anda ingin memastikan Anda
melacak semua pointer Anda

1198
01:00:31,370 --> 01:00:33,661
atau Anda akan mendapatkan
masalah besar dalam kode Anda.

1199
01:00:33,661 --> 01:00:35,840
Menarik hal-hal dengan hati-hati langkah demi langkah.

1200
01:00:35,840 --> 01:00:37,870
Itu membuat lebih mudah untuk memikirkan.

1201
01:00:37,870 --> 01:00:40,910
>> Dan terakhir, Anda ingin dapat
menguji kinerja Anda program Anda

1202
01:00:40,910 --> 01:00:41,618
di papan besar.

1203
01:00:41,618 --> 01:00:43,710
Jika kalian mengambil
melihat CS50 sekarang,

1204
01:00:43,710 --> 01:00:45,210
kita memiliki apa yang disebut papan besar.

1205
01:00:45,210 --> 01:00:50,200
Ini adalah lembar skor tercepat
mantra kali memeriksa di semua CS50

1206
01:00:50,200 --> 01:00:55,720
sekarang, saya pikir atas seperti 10
kali saya pikir delapan dari mereka adalah staf.

1207
01:00:55,720 --> 01:00:57,960
Kami benar-benar ingin kalian untuk mengalahkan kami.

1208
01:00:57,960 --> 01:01:00,870
>> Semua dari kita mencoba untuk menerapkan
kode tercepat mungkin.

1209
01:01:00,870 --> 01:01:04,880
Kami ingin kalian mencoba untuk menantang
kita dan menerapkan lebih cepat dari kita semua

1210
01:01:04,880 --> 01:01:05,550
bisa.

1211
01:01:05,550 --> 01:01:07,970
Dan ini benar-benar
pertama kalinya bahwa kita

1212
01:01:07,970 --> 01:01:12,680
meminta kalian untuk melakukan pset yang
Anda benar-benar bisa melakukan apa pun metode yang di

1213
01:01:12,680 --> 01:01:13,760
kamu ingin.

1214
01:01:13,760 --> 01:01:17,730
>> Saya selalu mengatakan, ini lebih mirip
untuk solusi kehidupan nyata, kan?

1215
01:01:17,730 --> 01:01:19,550
Saya katakan, hei, saya perlu Anda lakukan ini.

1216
01:01:19,550 --> 01:01:21,380
Membangun program yang melakukan ini untuk saya.

1217
01:01:21,380 --> 01:01:22,630
Lakukan namun Anda inginkan.

1218
01:01:22,630 --> 01:01:24,271
Saya hanya tahu bahwa saya ingin cepat.

1219
01:01:24,271 --> 01:01:25,770
Itu tantangan Anda untuk minggu ini.

1220
01:01:25,770 --> 01:01:27,531
Kalian, kita akan
untuk memberikan tugas.

1221
01:01:27,531 --> 01:01:29,030
Kami akan memberikan tantangan.

1222
01:01:29,030 --> 01:01:31,559
Dan kemudian terserah kalian
untuk benar-benar hanya mencari tahu

1223
01:01:31,559 --> 01:01:34,100
apa cara tercepat dan paling
cara yang efisien untuk melaksanakan hal ini.

1224
01:01:34,100 --> 01:01:34,600
Ya?

1225
01:01:34,600 --> 01:01:37,476
>> AUDIENCE: Apakah kita diperbolehkan untuk jika
diinginkannya untuk penelitian cara cepat

1226
01:01:37,476 --> 01:01:40,821
untuk melakukan tabel hash online, yang bisa kita lakukan
itu dan mengutip kode orang lain?

1227
01:01:40,821 --> 01:01:42,070
ANDI PENG: Ya, benar-benar baik-baik saja.

1228
01:01:42,070 --> 01:01:44,320
Jadi jika kalian membaca
spec, ada garis

1229
01:01:44,320 --> 01:01:48,310
di spec yang mengatakan kalian
benar-benar bebas untuk penelitian hash

1230
01:01:48,310 --> 01:01:51,070
fungsi pada apa adalah beberapa
fungsi hash lebih cepat

1231
01:01:51,070 --> 01:01:54,720
untuk menjalankan hal-hal melalui sebagai
Selama Anda mengutip kode tersebut.

1232
01:01:54,720 --> 01:01:57,220
Jadi beberapa orang sudah
tahu cara cepat

1233
01:01:57,220 --> 01:02:00,250
melakukan spell checker, cepat
cara menyimpan informasi.

1234
01:02:00,250 --> 01:02:02,750
Benar-benar sampai kalian jika Anda
ingin hanya mengambil itu, kan?

1235
01:02:02,750 --> 01:02:04,045
Pastikan Anda mengutip.

1236
01:02:04,045 --> 01:02:06,170
Tantangan di sini benar-benar
bahwa kita mencoba untuk menguji

1237
01:02:06,170 --> 01:02:09,750
adalah memastikan bahwa Anda tahu
jalan sekitar pointer.

1238
01:02:09,750 --> 01:02:12,700
Sejauh yang Anda menerapkan
fungsi hash yang sebenarnya

1239
01:02:12,700 --> 01:02:15,070
dan datang dengan seperti
matematika untuk melakukan itu,

1240
01:02:15,070 --> 01:02:17,570
kalian dapat penelitian apa pun
metode online kalian inginkan.

1241
01:02:17,570 --> 01:02:17,996
Ya?

1242
01:02:17,996 --> 01:02:19,700
>> AUDIENCE: Bisakah kita mengutip hanya
dengan menggunakan [tidak terdengar]?

1243
01:02:19,700 --> 01:02:20,120
>> ANDI PENG: Ya.

1244
01:02:20,120 --> 01:02:22,328
Anda hanya bisa, dalam komentar Anda,
Anda dapat mengutip seperti, oh,

1245
01:02:22,328 --> 01:02:26,127
diambil dari Yada, Yada,
Yada, fungsi hash.

1246
01:02:26,127 --> 01:02:27,210
Ada yang punya pertanyaan?

1247
01:02:27,210 --> 01:02:29,694
Kami benar-benar melenggang
melalui bagian hari ini.

1248
01:02:29,694 --> 01:02:31,610
Aku akan sampai di sini untuk
menjawab pertanyaan-pertanyaan juga.

1249
01:02:31,610 --> 01:02:36,570
>> Juga, seperti yang saya katakan, kantor
jam malam ini dan besok.

1250
01:02:36,570 --> 01:02:40,307
Spec minggu ini sebenarnya
super mudah dan super pendek untuk membaca.

1251
01:02:40,307 --> 01:02:43,140
Saya akan menyarankan mengambil melihat, hanya
membaca keseluruhan itu.

1252
01:02:43,140 --> 01:02:45,730
>> Dan Zamyla sebenarnya menuntun Anda
melalui masing-masing fungsi

1253
01:02:45,730 --> 01:02:49,796
Anda perlu untuk mengimplementasikan, dan jadi
sangat, sangat jelas bagaimana melakukan segala sesuatu.

1254
01:02:49,796 --> 01:02:51,920
Hanya untuk memastikan Anda
melacak pointer.

1255
01:02:51,920 --> 01:02:53,650
Ini adalah pset sangat menantang.

1256
01:02:53,650 --> 01:02:56,744
>> Ini tidak menantang karena seperti,
oh, konsep-konsep yang jauh lebih

1257
01:02:56,744 --> 01:02:59,160
sulit, atau Anda harus belajar
begitu banyak sintaks baru jalan

1258
01:02:59,160 --> 01:03:00,650
yang Anda lakukan untuk pset terakhir.

1259
01:03:00,650 --> 01:03:03,320
Pset ini sulit karena
ada begitu banyak pointer,

1260
01:03:03,320 --> 01:03:06,980
dan kemudian itu sangat, sangat mudah sekali
Anda memiliki bug dalam kode Anda tidak dapat

1261
01:03:06,980 --> 01:03:08,315
untuk menemukan di mana bug yang.

1262
01:03:08,315 --> 01:03:13,200
>> Dan begitu lengkap dan iman di dalam kamu mengucapkan
orang untuk dapat mengalahkan kami [tidak terdengar]

1263
01:03:13,200 --> 01:03:13,700
ejaan.

1264
01:03:13,700 --> 01:03:16,640
Aku benar-benar tidak punya tambang ditulis
, tapi aku akan menulis saya.

1265
01:03:16,640 --> 01:03:19,070
Jadi saat Anda sedang menulis
Anda, saya akan menulis saya.

1266
01:03:19,070 --> 01:03:21,070
Aku akan mencoba untuk membuat
saya lebih cepat dari Anda.

1267
01:03:21,070 --> 01:03:23,940
Kami akan melihat siapa yang memiliki salah satu yang paling cepat.

1268
01:03:23,940 --> 01:03:27,340
>> Dan ya, aku akan melihat semua
kalian di Jakarta, Selasa.

1269
01:03:27,340 --> 01:03:29,510
Saya akan menjalankan semacam seperti lokakarya pset.

1270
01:03:29,510 --> 01:03:32,640
Semua bagian ini
minggu lokakarya pset,

1271
01:03:32,640 --> 01:03:36,690
sehingga kalian punya banyak kesempatan
bantuan, jam kantor seperti biasa,

1272
01:03:36,690 --> 01:03:41,330
dan saya benar-benar melihat ke depan untuk
membaca semua kode-orang Anda '.

1273
01:03:41,330 --> 01:03:44,160
Saya memiliki kuis di sini jika Anda
orang ingin datang mendapatkan mereka.

1274
01:03:44,160 --> 01:03:45,880
Itu saja.

1275
01:03:45,880 --> 01:03:48,180