1
00:00:00,000 --> 00:00:03,423
>> [Bermain muzik]

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

3
00:00:05,380 --> 00:00:08,210
>> ANDI PENG: Selamat datang ke minggu 6 seksyen.

4
00:00:08,210 --> 00:00:11,620
Kami menyimpang dari standard kami
seksyen masa Selasa

5
00:00:11,620 --> 00:00:14,130
petang ke pagi Ahad ini indah.

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

7
00:00:17,330 --> 00:00:18,170
satu pusingan tepukan.

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

9
00:00:20,600 --> 00:00:23,600
Saya hampir tidak juga membuat ia
dalam masa, tetapi Ia adalah OK.

10
00:00:23,600 --> 00:00:27,520
Jadi saya tahu bahawa anda semua
baru sahaja berjaya ke kuiz.

11
00:00:27,520 --> 00:00:30,370
Pertama sekali, selamat datang untuk
sebelah flip itu.

12
00:00:30,370 --> 00:00:32,917
>> Kedua, kami akan bercakap mengenainya.

13
00:00:32,917 --> 00:00:34,000
Kami akan bercakap mengenai kuiz.

14
00:00:34,000 --> 00:00:35,700
Kami akan bercakap tentang bagaimana
yang anda lakukan di dalam kelas.

15
00:00:35,700 --> 00:00:36,550
Anda akan selamat.

16
00:00:36,550 --> 00:00:39,080
Saya mempunyai kuiz anda untuk
anda pada akhir dari sini,

17
00:00:39,080 --> 00:00:42,120
jadi jika anda semua ingin mengambil
yang melihat ia, betul-betul halus.

18
00:00:42,120 --> 00:00:46,590
>> Begitu cepat sebelum kita bermula,
agenda untuk hari ini adalah seperti berikut.

19
00:00:46,590 --> 00:00:48,430
Seperti yang anda lihat, kami
tembakan pada dasarnya pesat

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
Maka oleh itu, ia tidak akan menjadi
hari ini super interaktif.

22
00:00:54,380 --> 00:00:59,620
Ia hanya akan menjadi saya agak menjerit
perkara yang anda, dan jika saya mengelirukan anda,

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

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

25
00:01:05,200 --> 00:01:07,070
daripada pset anda untuk ini
minggu yang akan datang, anda akan

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

27
00:01:10,340 --> 00:01:12,319
dalam Serangga anda.

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

29
00:01:14,610 --> 00:01:19,070
Kami akan pergi ke susunan dan beratur lebih dalam
mendalam daripada apa yang kita lakukan sebelum ini kuiz.

30
00:01:19,070 --> 00:01:20,990
Kami akan pergi dikaitkan
senarai lagi, sekali lagi,

31
00:01:20,990 --> 00:01:23,899
lebih mendalam daripada apa yang
kita ada sebelum kuiz.

32
00:01:23,899 --> 00:01:26,440
Dan kemudian kita akan bercakap tentang hash
meja, pokok-pokok dan percubaan, 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 pergi ke beberapa
tips berguna untuk pset5.

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

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

37
00:01:41,090 --> 00:01:45,370
Ia adalah sangat rendah, dan supaya kalian semua
dengan sangat, sangat baik mengikut

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

39
00:01:46,510 --> 00:01:49,970
>> Cukup banyak, Peraturan praktikal adalah jika anda
dalam sisihan piawai min

40
00:01:49,970 --> 00:01:52,990
terutamanya kerana kita berada dalam yang kurang
seksyen yang selesa, anda benar-benar baik.

41
00:01:52,990 --> 00:01:54,120
Anda berada di landasan yang betul.

42
00:01:54,120 --> 00:01:55,190
Hidup ini indah.

43
00:01:55,190 --> 00:01:58,952
>> Saya tahu ia adalah menakutkan untuk berfikir bahawa
Saya mendapat seperti 40% untuk kuiz ini.

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

45
00:02:00,160 --> 00:02:02,243
Saya berjanji kepada anda, anda tidak
akan gagal kelas.

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

47
00:02:03,680 --> 00:02:06,850
>> Bagi anda yang mendapat lebih
min, mengagumkan, menarik,

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

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

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

51
00:02:11,730 --> 00:02:14,520
Hubungi saya jika anda mempunyai sebarang
isu, soalan dengan mereka.

52
00:02:14,520 --> 00:02:17,204
Jika kita menambah skor anda
salah, sila beritahu kami.

53
00:02:17,204 --> 00:02:21,240
>> OK, jadi pset5, ini adalah benar-benar
minggu pelik untuk Yale dalam erti kata

54
00:02:21,240 --> 00:02:24,240
yang pset kami adalah kerana
Rabu pada tengah hari termasuk

55
00:02:24,240 --> 00:02:27,317
hari lewat, jadi ia sebenarnya
secara teori kerana Selasa di tengah hari.

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

57
00:02:29,150 --> 00:02:30,830
Itu betul-betul halus.

58
00:02:30,830 --> 00:02:33,700
Kita akan mempunyai waktu pejabat
malam ini dan juga malam Isnin.

59
00:02:33,700 --> 00:02:36,810
Dan kesemua seksyen minggu ini akan
sebenarnya dijadikan bengkel,

60
00:02:36,810 --> 00:02:38,800
jadi berasa bebas untuk pop dalam
mana-mana bahagian yang anda mahu,

61
00:02:38,800 --> 00:02:42,810
dan mereka akan menjadi jenis mini Serangga
bengkel untuk membantu pada itu.

62
00:02:42,810 --> 00:02:45,620
Maka oleh itu, ini adalah bahagian sahaja
di mana kita bahan mengajar.

63
00:02:45,620 --> 00:02:49,220
Semua bahagian-bahagian lain akan memberi tumpuan
semata-mata pada bantuan untuk pset.

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

65
00:02:50,146 --> 00:02:52,000
>> PENONTON: Di manakah waktu pejabat?

66
00:02:52,000 --> 00:02:56,120
>> ANDI PENG: Waktu pejabat
tonight-- oh, soalan yang baik.

67
00:02:56,120 --> 00:03:00,580
Saya rasa waktu pejabat malam ini
berada di dalam atau di Teal Commons.

68
00:03:00,580 --> 00:03:02,984
Jika anda mendaftar dalam talian CS50
dan anda pergi ke waktu pejabat,

69
00:03:02,984 --> 00:03:05,650
perlu ada jadual yang
memberitahu anda di mana kesemua mereka berada.

70
00:03:05,650 --> 00:03:07,954
>> Saya tahu sama ada malam ini
atau esok adalah Teal,

71
00:03:07,954 --> 00:03:10,120
dan saya rasa kami mungkin mempunyai
orang biasa untuk malam yang lain.

72
00:03:10,120 --> 00:03:11,020
Saya tidak pasti.

73
00:03:11,020 --> 00:03:11,700
Soalan yang baik.

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

75
00:03:14,430 --> 00:03:18,780
>> Cool, sebarang pertanyaan mengenai
jadual untuk seterusnya seperti tiga hari?

76
00:03:18,780 --> 00:03:21,690
Saya berjanji kepada anda lelaki seperti David
berkata, ini adalah bahagian atas bukit.

77
00:03:21,690 --> 00:03:23,050
Anda lelaki yang hampir di sana.

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

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

80
00:03:26,310 --> 00:03:28,114
Kami akan perlu bagus rehat CS-percuma.

81
00:03:28,114 --> 00:03:28,780
Kita akan kembali.

82
00:03:28,780 --> 00:03:30,779
Kami akan menyelam ke dalam web
pengaturcaraan dan pembangunan,

83
00:03:30,779 --> 00:03:35,150
perkara-perkara yang sangat menyeronokkan berbanding
kepada beberapa psets lain.

84
00:03:35,150 --> 00:03:37,974
Dan ia akan menjadi sejuk, dan
kita akan mempunyai banyak bersenang-senang.

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

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

87
00:03:39,730 --> 00:03:40,945
Saya terlupa gula-gula.

88
00:03:40,945 --> 00:03:43,310
Ia adalah pagi yang kasar.

89
00:03:43,310 --> 00:03:46,340
Jadi anda semua hampir di sana,
dan saya amat bangga dengan anda semua.

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

91
00:03:49,570 --> 00:03:53,331
Yang suka soalan mengenai Jack
dan pakaian beliau mengenai kuiz?

92
00:03:53,331 --> 00:03:53,830
Tiada sesiapa?

93
00:03:53,830 --> 00:03:56,500
OK, itulah denda.

94
00:03:56,500 --> 00:04:00,200
>> Jadi pada asasnya yang anda boleh
gambar Jack, Lelaki ini di sini,

95
00:04:00,200 --> 00:04:03,350
suka mengambil pakaian
daripada bahagian atas timbunan,

96
00:04:03,350 --> 00:04:05,750
dan dia meletakkan ia kembali ke
tindanan selepas dia lakukan.

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

98
00:04:07,600 --> 00:04:10,090
ke bahagian bawah
stack dalam pakaiannya.

99
00:04:10,090 --> 00:04:12,600
Jadi ini jenis menerangkan
struktur data asas

100
00:04:12,600 --> 00:04:16,610
bagaimana timbunan dilaksanakan.

101
00:04:16,610 --> 00:04:20,060
>> Pada asasnya, memikirkan
stack sebagai apa-apa timbunan objek

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

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

104
00:04:28,600 --> 00:04:32,480
Dan sebagainya bertahan dalam ke bahagian atas
timbunan adalah yang pertama yang keluar.

105
00:04:32,480 --> 00:04:34,260
Dan supaya kedua-dua istilah
kita suka bergaul

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

107
00:04:36,190 --> 00:04:39,790
Apabila anda menolak sesuatu ke atas
timbunan, dan anda pop kembali.

108
00:04:39,790 --> 00:04:43,422
>> Oleh itu, saya rasa ini adalah jenis yang
konsep abstrak bagi anda

109
00:04:43,422 --> 00:04:45,630
yang mahu melihat seperti
pelaksanaan sebenar ini

110
00:04:45,630 --> 00:04:46,740
dalam dunia sebenar.

111
00:04:46,740 --> 00:04:50,170
Berapa ramai daripada anda telah menulis esei
mungkin seperti satu jam sebelum ia disebabkan,

112
00:04:50,170 --> 00:04:54,510
dan anda secara tidak sengaja dipadam besar
sebahagian daripadanya, seperti tidak sengaja?

113
00:04:54,510 --> 00:04:58,560
Dan kemudian apa kawalan melakukan
kita gunakan untuk meletakkannya kembali?

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

115
00:05:00,030 --> 00:05:03,640
Kawalan-Z, jadi jumlah kali
bahawa kawalan-Z telah menyelamatkan hidup saya,

116
00:05:03,640 --> 00:05:08,820
telah menyelamatkan pantat saya, setiap kali
yang yang dilaksanakan melalui timbunan.

117
00:05:08,820 --> 00:05:13,020
>> Pada dasarnya semua maklumat yang
yang pada dokumen Word anda,

118
00:05:13,020 --> 00:05:15,080
ia akan ditolak dan muncul sesuka hati.

119
00:05:15,080 --> 00:05:19,460
Dan sebagainya pada dasarnya setiap kali anda
memadam apa-apa, anda pop kembali.

120
00:05:19,460 --> 00:05:22,820
Dan kemudian jika anda memerlukannya semula, anda
menolak, yang adalah apa Control-C tidak.

121
00:05:22,820 --> 00:05:26,770
Dan fungsi dunia begitu nyata
struktur data bagaimana mudah

122
00:05:26,770 --> 00:05:28,690
boleh membantu dengan kehidupan seharian 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 mewujudkan timbunan.

125
00:05:40,150 --> 00:05:44,720
Kita menaip menentukan struct, dan kemudian
kita panggil ia stack di bahagian bawah.

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

127
00:05:47,440 --> 00:05:51,580
yang kita dasarnya boleh memanipulasi,
jadi kita perlu char kapasiti tali bintang.

128
00:05:51,580 --> 00:05:55,150
>> Apa yang ia lakukan
mencipta array

129
00:05:55,150 --> 00:05:58,835
yang kita boleh menyimpan apa sahaja yang anda mahu
mana kita boleh menentukan kapasitinya.

130
00:05:58,835 --> 00:06:01,990
Kapasiti Adakah hanya jumlah yang maksimum
barangan yang kita boleh dimasukkan ke dalam pelbagai ini.

131
00:06:01,990 --> 00:06:05,660
saiz int adalah kaunter yang menyimpan
menjejaki berapa banyak perkara pada masa ini

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

133
00:06:07,850 --> 00:06:11,860
Sebab itu kita boleh menjejaki, A,
kedua-dua berapa besar timbunan sebenar adalah,

134
00:06:11,860 --> 00:06:14,850
dan, B, berapa banyak timbunan yang
kami mengisinya kerana kita tidak mahu

135
00:06:14,850 --> 00:06:18,800
melimpah ke atas apa kapasiti kita.

136
00:06:18,800 --> 00:06:24,340
>> Jadi, sebagai contoh, ini indah
soalan adalah pada kuiz anda.

137
00:06:24,340 --> 00:06:28,160
Pada dasarnya bagaimana kita menolak
ke bahagian atas timbunan.

138
00:06:28,160 --> 00:06:28,830
Agak mudah.

139
00:06:28,830 --> 00:06:30,621
Jika anda melihat ia,
kami akan berjalan melalui ini.

140
00:06:30,621 --> 00:06:32,640
Jika [didengar] size--
ingat, setiap kali anda

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

142
00:06:35,300 --> 00:06:40,320
anda melakukan perkara yang nama struct.parameter itu.

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

144
00:06:42,720 --> 00:06:46,230
Kami mahu mengakses saiz
itu, jadi kami melakukan s.size.

145
00:06:46,230 --> 00:06:50,280
Jadi selagi saiz tidak
sama dengan kapasiti atau selama

146
00:06:50,280 --> 00:06:52,940
kerana ia adalah kurang daripada kapasiti,
sama ada akan bekerja di sini.

147
00:06:52,940 --> 00:06:57,180
>> Anda mahu untuk mengakses di dalam
timbunan anda, jadi s.strings,

148
00:06:57,180 --> 00:07:00,790
dan anda akan meletakkan bahawa nombor baru
yang anda mahu masukkan ke dalam sana.

149
00:07:00,790 --> 00:07:05,030
Mari kita hanya mengatakan bahawa kita mahu
memasukkan int n ke dalam tindanan,

150
00:07:05,030 --> 00:07:08,905
kita boleh lakukan s.strings,
kurungan, s.size sama n.

151
00:07:08,905 --> 00:07:11,030
Kerana saiz adalah di mana kita
kini berada di dalam timbunan

152
00:07:11,030 --> 00:07:14,590
jika kita akan menolak
di atas, kita hanya mengakses

153
00:07:14,590 --> 00:07:17,370
di mana sahaja saiz adalah,
kenyang semasa timbunan,

154
00:07:17,370 --> 00:07:21,729
dan kita menolak int n ke ia.

155
00:07:21,729 --> 00:07:24,770
Dan kemudian kita mahu memastikan bahawa
kita juga menokok saiz n,

156
00:07:24,770 --> 00:07:27,436
supaya kita boleh mengesan kami telah
menambah perkara tambahan untuk timbunan.

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

158
00:07:29,660 --> 00:07:33,196
Adakah ini di sini akal untuk
semua orang, bagaimana logik ia berfungsi?

159
00:07:33,196 --> 00:07:34,160
Ia adalah jenis yang cepat.

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

161
00:07:39,535 --> 00:07:42,160
PENONTON: Bolehkah anda pergi
yang s.stringss.strings [s.size] sekali lagi?

162
00:07:42,160 --> 00:07:45,808
ANDI PENG: Pasti, jadi apakah
s.size kini memberikan kita?

163
00:07:45,808 --> 00:07:47,440
PENONTON: Ia adalah saiz semasa.

164
00:07:47,440 --> 00:07:50,890
ANDI PENG: Tepat, jadi
indeks semasa yang saiz kami adalah di,

165
00:07:50,890 --> 00:07:57,780
dan dengan itu kita mahu meletakkan integer baru
yang kita mahu masukkan ke dalam s.size.

166
00:07:57,780 --> 00:07:58,760
Adakah ini masuk akal?

167
00:07:58,760 --> 00:08:01,110
Kerana s.strings, apa yang
adalah adalah nama array.

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

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

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

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

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

173
00:08:13,580 --> 00:08:18,916
>> Baiklah, pop, saya pseudokod keluar
untuk anda semua, tetapi konsep yang sama.

174
00:08:18,916 --> 00:08:19,790
Adakah ini masuk akal?

175
00:08:19,790 --> 00:08:22,310
Jika saiz lebih besar
daripada sifar, maka anda

176
00:08:22,310 --> 00:08:25,350
tahu bahawa anda mahu mengambil sesuatu
keluar kerana jika saiz tidak

177
00:08:25,350 --> 00:08:27,620
lebih besar daripada sifar, maka anda
mempunyai apa-apa dalam timbunan.

178
00:08:27,620 --> 00:08:29,840
>> Jadi anda hanya ingin melaksanakan
kod ini, ia hanya boleh

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 saiz lebih besar
daripada 0, kita tolak saiz.

181
00:08:35,830 --> 00:08:40,020
Kami susutan saiz dan kemudian kembali
apa yang ada di dalamnya kerana

182
00:08:40,020 --> 00:08:42,710
oleh bermunculan, kita mahu
akses apa sahaja yang disimpan

183
00:08:42,710 --> 00:08:45,694
dalam indeks bahagian atas timbunan.

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

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

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

187
00:08:52,029 --> 00:08:53,570
OK, anda semua boleh bermain-main dengannya.

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

189
00:08:55,252 --> 00:08:57,460
Kami tidak mempunyai masa untuk kod
ia keluar hari ini kerana kami telah

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
pseudokod, sangat, sangat serupa dengan menolak.

192
00:09:02,214 --> 00:09:03,380
Hanya ikut bersama-sama logik.

193
00:09:03,380 --> 00:09:06,092
Pastikan anda mengakses semua
ciri-ciri struct anda dengan betul.

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

195
00:09:06,574 --> 00:09:09,282
>> PENONTON: Adakah slaid ini dan
semua ini sehingga hari ini-ish?

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

197
00:09:11,586 --> 00:09:13,710
Saya akan cuba untuk meletakkan
ini sehingga seperti satu jam selepas.

198
00:09:13,710 --> 00:09:16,626
Saya akan mengemel David, David akan cuba untuk
meletakkan ia seperti satu jam selepas ini.

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

200
00:09:20,040 --> 00:09:25,470
>> OK, jadi kita bergerak ke dalam ini lain
struktur data indah dipanggil barisan.

201
00:09:25,470 --> 00:09:30,140
Seperti yang anda semua boleh lihat di sini, yang
giliran, untuk British di kalangan kita,

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

203
00:09:32,010 --> 00:09:34,680
Jadi bertentangan dengan apa yang
anda berfikir timbunan adalah,

204
00:09:34,680 --> 00:09:37,750
barisan yang adalah apa yang
secara logik anda fikir ia.

205
00:09:37,750 --> 00:09:41,914
Ia diadakan oleh kaedah-kaedah FIFO,
yang Pertama Dalam, Pertama Out.

206
00:09:41,914 --> 00:09:43,705
Jika anda pertama
satu dalam baris, anda berada

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

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

209
00:09:49,680 --> 00:09:52,380
Jika kita mahu menambah sesuatu
kepada barisan kita, kita enqueue.

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

211
00:09:55,690 --> 00:10:03,350
>> Rasa begitu sama yang kita jenis
mewujudkan unsur-unsur tetap saiz yang kita

212
00:10:03,350 --> 00:10:06,500
boleh menyimpan tertentu
perkara, tetapi kita juga boleh

213
00:10:06,500 --> 00:10:10,100
perubahan di mana kita meletakkan
parameter di dalam mereka

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

215
00:10:13,140 --> 00:10:16,700
Jadi susunan, kita mahu yang lalu
satu, N untuk menjadi yang pertama satu daripada itu.

216
00:10:16,700 --> 00:10:19,800
Giliran ialah kita mahu perkara pertama
masuk untuk perkara pertama yang keluar.

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

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

219
00:10:26,710 --> 00:10:29,470
ia sedikit berbeza
dari apa timbunan itu

220
00:10:29,470 --> 00:10:33,120
kerana bukan sahaja kita perlu terus
mengesan di mana saiz yang masa ini adalah,

221
00:10:33,120 --> 00:10:37,420
kami juga ingin untuk mengesan kepala
serta di mana kita kini berada.

222
00:10:37,420 --> 00:10:39,580
Jadi saya fikir lebih mudah
jika saya menarik ini sehingga.

223
00:10:39,580 --> 00:10:53,270
Jadi mari kita bayangkan kami mempunyai barisan,
jadi katakan kepala adalah di sini.

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

225
00:10:55,811 --> 00:10:58,310
Ketua talian, mari kita
hanya mengatakan bahawa pada masa ini di sana,

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

227
00:11:01,809 --> 00:11:04,350
Saya akan memanggil saiz dasarnya
adalah perkara yang sama seperti ekor,

228
00:11:04,350 --> 00:11:06,314
akhir di mana sahaja giliran anda.

229
00:11:06,314 --> 00:11:07,730
Mari kita katakan saiz yang tepat di sini.

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

231
00:11:14,380 --> 00:11:18,400
>> Jadi bagaimana seseorang layak di
memasukkan sesuatu ke dalam barisan?

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

233
00:11:21,000 --> 00:11:24,130
Apa indeks kita mahu meletakkan
di mana kita mahu memasukkan ke dalam.

234
00:11:24,130 --> 00:11:29,320
Jika ini adalah permulaan anda
beratur dan ini adalah akhir itu

235
00:11:29,320 --> 00:11:31,860
atau saiz itu, di mana kita
ingin menambah objek yang akan datang?

236
00:11:31,860 --> 00:11:32,920
>> PENONTON: [didengar]

237
00:11:32,920 --> 00:11:35,920
ANDI PENG: Tepat sekali, anda mahu tambah
ia bergantung kepada anda telah menulis.

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

239
00:11:37,840 --> 00:11:42,630
Jadi, anda mahu untuk menambah ia mungkin
di sini kerana jika saiz is--

240
00:11:42,630 --> 00:11:50,540
jika semua ini adalah penuh, anda mahu
untuk menambah ia di sini, bukan?

241
00:11:50,540 --> 00:11:57,150
>> Dan supaya, manakala sangat, sangat
mudah, tidak cukup sentiasa betul

242
00:11:57,150 --> 00:12:00,690
kerana perbezaan utama
antara barisan dan timbunan

243
00:12:00,690 --> 00:12:04,350
adalah bahawa barisan boleh
sebenarnya dimanipulasi

244
00:12:04,350 --> 00:12:06,980
supaya perubahan kepala
bergantung kepada di mana anda mahu

245
00:12:06,980 --> 00:12:08,650
awal isyarat anda untuk bermula.

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

247
00:12:11,900 --> 00:12:14,770
Dan supaya kita lihat
kod ini buat masa ini.

248
00:12:14,770 --> 00:12:18,620
Seperti yang anda semua juga diminta untuk
menulis kuiz, enqueue.

249
00:12:18,620 --> 00:12:22,580
Mungkin kita akan bercakap melalui mengapa
jawapannya adalah apa yang ia.

250
00:12:22,580 --> 00:12:26,790
>> Saya tidak boleh agak sesuai baris ini pada satu,
tetapi pada dasarnya ini sekeping kod

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

252
00:12:29,030 --> 00:12:30,140
Belanja seperti 30 saat.

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

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

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

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

257
00:12:58,090 --> 00:13:01,190
Dan itu satu baris kod
menentukan fungsi.

258
00:13:01,190 --> 00:13:03,900
Dan ia benar-benar membezakan
giliran dari timbunan.

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

260
00:13:18,510 --> 00:13:22,010
>> Sesiapa pun mahu mengambil tikaman
untuk menerangkan mengapa anda telah

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

262
00:13:24,980 --> 00:13:27,845
Kami menyaksikan kembalinya kami
rakan modulus indah.

263
00:13:27,845 --> 00:13:31,020
Seperti yang anda semua tidak lama lagi akan datang
untuk mengiktiraf dalam pengaturcaraan,

264
00:13:31,020 --> 00:13:34,910
hampir bila-bila masa anda memerlukan sesuatu
untuk membungkus apa-apa,

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 bahawa, adakah sesiapa yang mahu
cuba menjelaskan bahawa baris kod?

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

268
00:13:44,060 --> 00:13:47,507
Ya, semua jawapan adalah
diterima dan dialu-alukan.

269
00:13:47,507 --> 00:13:48,840
PENONTON: Adakah anda bercakap dengan saya?

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

271
00:13:49,506 --> 00:13:56,200
PENONTON: Oh, tidak maaf.

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

273
00:14:00,250 --> 00:14:03,642
Oleh itu, apabila anda cuba untuk
menambah sesuatu ke barisan,

274
00:14:03,642 --> 00:14:08,510
dalam hal yang indah yang kepala berlaku
menjadi di sini, ia sangat mudah untuk kita

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

276
00:14:10,960 --> 00:14:14,690
Tetapi titik keseluruhan barisan adalah
bahawa kepala sebenarnya boleh secara dinamik

277
00:14:14,690 --> 00:14:17,280
berubah bergantung kepada di mana kita
mahu permulaan q kami menjadi,

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

279
00:14:19,880 --> 00:14:31,100
>> Dan supaya membayangkan bahawa ini tidak adalah
beratur, tetapi ini adalah barisan.

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

281
00:14:37,900 --> 00:14:39,330
Katakan kepala adalah di sini.

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

283
00:14:54,900 --> 00:14:56,980
Katakan barisan kami kelihatan seperti ini.

284
00:14:56,980 --> 00:15:00,190
Jika kita mahu beralih di mana
awal barisan adalah,

285
00:15:00,190 --> 00:15:03,400
katakan kita beralih kepala
cara ini dan saiz di sini.

286
00:15:03,400 --> 00:15:07,100
>> Sekarang kita mahu menambah sesuatu untuk
barisan ini, tetapi seperti yang anda semua boleh lihat,

287
00:15:07,100 --> 00:15:11,150
ia tidak begitu mudah kerana hanya
menambah apa sahaja adalah selepas saiz

288
00:15:11,150 --> 00:15:13,630
kerana kita kehabisan
batas-batas lokasi sebenar kami.

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

290
00:15:16,190 --> 00:15:18,610
Itulah keindahan barisan
ialah kepada kami, visual ia

291
00:15:18,610 --> 00:15:22,380
kelihatan seperti garis pergi seperti ini,
tetapi apabila disimpan dalam struktur data,

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

293
00:15:29,370 --> 00:15:32,360
Ia jenis membaluti
ke hadapan dengan cara yang sama

294
00:15:32,360 --> 00:15:34,780
yang satu barisan juga boleh balut
sekitar bergantung kepada mana sahaja yang anda

295
00:15:34,780 --> 00:15:36,279
mahu awal barisan untuk menjadi.

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

297
00:15:38,630 --> 00:15:40,880
mengatakan bahawa kita mahu mencipta
fungsi dipanggil enqueue.

298
00:15:40,880 --> 00:15:43,980
Kami mahu menambah int n ke dalam q itu.

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

300
00:15:49,250 --> 00:15:52,520
sama dengan kapasiti atau jika
ia kurang daripada kapasiti,

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

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

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

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

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

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

307
00:16:11,480 --> 00:16:19,500
Oleh itu, kita boleh lakukan 1 tambah 4 modulus
dengan kemampuan kita iaitu 5.

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

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

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

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

312
00:16:27,870 --> 00:16:30,640
dan dengan itu kita mahu dapat
untuk memasukkan ke dalam di sini.

313
00:16:30,640 --> 00:16:34,730
Dan sebagainya persamaan ini di sini baik hati
hanya bekerja dengan mana-mana nombor

314
00:16:34,730 --> 00:16:36,750
bergantung kepada di mana anda
kepala dan saiz anda berada.

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

316
00:16:38,541 --> 00:16:43,170
betul-betul di mana anda mahu untuk memasukkan
apa yang ada selepas baris gilir anda.

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

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

319
00:16:48,560 --> 00:16:50,512
datang dalam selepas kuiz anda.

320
00:16:50,512 --> 00:16:52,220
Tetapi diharapkan semua orang
kini boleh memahami

321
00:16:52,220 --> 00:16:57,800
mengapa penyelesaian ini atau ini
fungsi adalah cara yang ia adalah.

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

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

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

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

326
00:17:07,109 --> 00:17:09,970
>> Dan sehingga kini, jika anda
mahu dequeue, ini

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

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

329
00:17:17,030 --> 00:17:19,130
Kami mahu menanggalkan kepala, bukan?

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

331
00:17:24,260 --> 00:17:26,800
anda telah mendapat untuk mengesan
di mana kepala dan saiz anda

332
00:17:26,800 --> 00:17:29,450
yang dapat memasukkan
ke dalam kedudukan yang betul.

333
00:17:29,450 --> 00:17:32,740
>> Dan jadi apabila anda dequeue,
Saya juga pseudokod keluar.

334
00:17:32,740 --> 00:17:35,480
Jangan ragu untuk jika anda mahu
untuk cuba pengekodan ini keluar.

335
00:17:35,480 --> 00:17:36,980
Anda mahu untuk menggerakkan kepala, bukan?

336
00:17:36,980 --> 00:17:39,320
Jika saya mahu dequeue, saya
akan menggerakkan kepala ke atas.

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

338
00:17:40,800 --> 00:17:45,617
>> Dan saiz semasa kami akan
tolak kerana kita tidak lagi

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

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

341
00:17:51,370 --> 00:17:56,260
kepala kerana kita mahu mengambil ini
nilai daripada jadi hampir sama dengan timbunan.

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

343
00:17:58,010 --> 00:18:01,770
dan anda perlu memberi semula penuding anda
ke tempat yang berbeza sebagai hasilnya.

344
00:18:01,770 --> 00:18:03,890
Secara logiknya, semua orang mengikuti?

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

346
00:18:05,690 --> 00:18:10,156
>> OK, jadi kita akan bercakap sedikit
lebih mendalam mengenai senarai berkaitan

347
00:18:10,156 --> 00:18:13,280
kerana mereka akan menjadi sangat, sangat berharga
untuk anda dalam masa sebulan yang ini

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

349
00:18:14,964 --> 00:18:17,130
Senarai berkaitan, kerana anda semua
boleh ingat, semua mereka adalah

350
00:18:17,130 --> 00:18:22,570
adalah nod yang nod tertentu
nilai-nilai kedua-dua nilai dan penunjuk

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

352
00:18:26,290 --> 00:18:29,880
Dan sebagainya struct tentang bagaimana
kita mewujudkan nod sini ialah kita

353
00:18:29,880 --> 00:18:33,569
mempunyai int n, iaitu apa sahaja yang
nilai di kedai atau tali n

354
00:18:33,569 --> 00:18:35,610
atau apa sahaja yang anda mahu
memanggilnya, char bintang n.

355
00:18:35,610 --> 00:18:41,482
Struct bintang nod, yang merupakan penunjuk
yang anda mahu dalam setiap nod,

356
00:18:41,482 --> 00:18:43,690
anda akan mempunyai bahawa
titik penunjuk arah depan.

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

358
00:18:48,207 --> 00:18:50,040
Anda akan mempunyai kepala
daripada senarai dikaitkan itulah

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

360
00:18:53,140 --> 00:18:55,290
sehingga anda akhirnya mencapai akhir.

361
00:18:55,290 --> 00:18:58,040
Dan simpulan terakhir ini hanya
akan tidak mempunyai penunjuk.

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

363
00:18:59,952 --> 00:19:01,910
anda tahu anda telah melanda
akhir senarai dipautkan anda

364
00:19:01,910 --> 00:19:04,076
adalah apabila penunjuk terakhir anda
tidak menunjukkan apa-apa.

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

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

367
00:19:10,990 --> 00:19:12,400
mencari senarai berpaut.

368
00:19:12,400 --> 00:19:15,460
Ingat apa yang adalah sebahagian daripada
kelemahan daripada senarai berkaitan

369
00:19:15,460 --> 00:19:19,340
ayat-ayat pelbagai mengenai carian.

370
00:19:19,340 --> 00:19:22,565
Antara yang anda boleh carian binari, tetapi
mengapa tidak boleh anda melakukannya dalam senarai berpaut?

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

372
00:19:26,834 --> 00:19:30,320
>> PENONTON: Kerana mereka semua yang berkaitan,
tetapi anda tidak cukup tahu di mana

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

374
00:19:31,330 --> 00:19:34,600
>> ANDI PENG: Ya, betul-betul jadi ingat
bahawa kecemerlangan array

375
00:19:34,600 --> 00:19:37,190
adalah hakikat bahawa kita mempunyai
ingatan capaian rawak di mana

376
00:19:37,190 --> 00:19:41,580
jika saya mahu nilai dari indeks
enam, saya hanya boleh berkata indeks enam,

377
00:19:41,580 --> 00:19:42,407
memberi saya nilai itu.

378
00:19:42,407 --> 00:19:45,240
Dan itu kerana tatasusunan yang disusun
dalam ruang berdampingan memori

379
00:19:45,240 --> 00:19:48,020
di satu tempat, manakala
jenis senarai berkaitan

380
00:19:48,020 --> 00:19:52,820
adalah secara rawak berselang di sekeliling,
dan satu-satunya cara yang anda boleh mencari satu

381
00:19:52,820 --> 00:19:56,890
adalah melalui penunjuk yang memberitahu anda
alamat di mana nod seterusnya adalah.

382
00:19:56,890 --> 00:20:00,290
>> Dan supaya hasilnya, satu-satunya cara
untuk mencari melalui senarai berpaut

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

384
00:20:01,560 --> 00:20:05,890
Kerana saya tidak tahu di mana sebenarnya
nilai ke-12 dalam senarai berkaitan adalah,

385
00:20:05,890 --> 00:20:08,780
Saya perlu merentasi keseluruhan yang
itu satu senarai berkaitan

386
00:20:08,780 --> 00:20:12,450
demi satu dari kepala untuk nod pertama,
kepada nod kedua, untuk nod ketiga,

387
00:20:12,450 --> 00:20:17,690
semua jalan ke bawah sehingga saya akhirnya mendapatkan
di mana nod saya cari adalah.

388
00:20:17,690 --> 00:20:22,110
Dan sebagainya dalam hal ini, carian
dalam senarai berpaut sentiasa n.

389
00:20:22,110 --> 00:20:23,040
Ia sentiasa n.

390
00:20:23,040 --> 00:20:25,690
Ia sentiasa Masa linear.

391
00:20:25,690 --> 00:20:28,470
>> Dan sebagainya kod di mana
kami melaksanakan ini, dan ini

392
00:20:28,470 --> 00:20:32,620
agak baru untuk anda semua kerana anda
semua telah tidak benar-benar bercakap tentang atau pernah

393
00:20:32,620 --> 00:20:35,000
lihat petunjuk dalam bagaimana untuk
mencari melalui petunjuk,

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

395
00:20:37,670 --> 00:20:40,200
Jadi carian bool, kanan,
mari kita bayangkan kita mahu

396
00:20:40,200 --> 00:20:42,820
untuk mewujudkan fungsi yang dipanggil
carian yang mengembalikan benar

397
00:20:42,820 --> 00:20:46,820
jika anda mendapati nilai dalam terpaut
senarai, dan ia mengembalikan palsu sebaliknya.

398
00:20:46,820 --> 00:20:50,030
Senarai nod bintang ini
kini hanya penunjuk

399
00:20:50,030 --> 00:20:52,960
untuk item pertama dalam senarai berpaut anda.

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

401
00:20:56,700 --> 00:20:58,770
>> Jadi penunjuk nod bintang sama senarai.

402
00:20:58,770 --> 00:21:00,970
Ini bermakna kita menetapkan
dan mewujudkan penunjuk

403
00:21:00,970 --> 00:21:03,592
untuk nod pertama dalam senarai.

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 perlu

406
00:21:06,530 --> 00:21:13,850
dimulakan penunjuk yang menunjukkan
ketua apa senarai yang.

407
00:21:13,850 --> 00:21:18,600
>> Dan kemudian sekali anda turun di sini,
manakala penunjuk tidak sama null,

408
00:21:18,600 --> 00:21:22,160
jadi yang gelung di mana kita berada
akan menjadi seterusnya menyeberangi

409
00:21:22,160 --> 00:21:25,940
yang lain dalam senarai kami kerana apa yang
berlaku apabila penunjuk sama null?

410
00:21:25,940 --> 00:21:27,550
Kita tahu bahawa kita ada--

411
00:21:27,550 --> 00:21:28,450
>> PENONTON: [didengar]

412
00:21:28,450 --> 00:21:31,491
>> ANDI PENG: Tepat sekali, jadi kita tahu bahawa
kami telah sampai ke penghujung senarai, bukan?

413
00:21:31,491 --> 00:21:34,470
Jika anda pergi ke sini, setiap nod
harus menunjuk kepada nod yang lain

414
00:21:34,470 --> 00:21:36,550
dan sebagainya dan sebagainya
sehingga anda memukul akhirnya

415
00:21:36,550 --> 00:21:41,589
ekor senarai berpaut anda,
yang mempunyai penunjuk yang hanya

416
00:21:41,589 --> 00:21:43,130
tidak menunjukkan mana-mana selain daripada tiada.

417
00:21:43,130 --> 00:21:47,510
Dan supaya anda pada dasarnya tahu bahawa
senarai anda masih ada sehingga

418
00:21:47,510 --> 00:21:50,900
sehingga penunjuk tidak sama
null kerana sekali ia sama null,

419
00:21:50,900 --> 00:21:53,310
anda tahu bahawa tidak ada lebih banyak barang.

420
00:21:53,310 --> 00:21:56,930
>> Jadi itulah gelung di mana kita berada
akan mempunyai carian yang sebenar.

421
00:21:56,930 --> 00:22:01,690
Dan jika pointer-- kaulihatkah
yang jenis anak panah fungsi di sana?

422
00:22:01,690 --> 00:22:06,930
Jadi, jika mata penunjuk kepada n, jika
penunjuk di n sama sama n,

423
00:22:06,930 --> 00:22:09,180
jadi ini bermakna bahawa jika
penunjuk bahawa anda

424
00:22:09,180 --> 00:22:13,420
mencari pada akhir setiap
nod sebenarnya adalah sama dengan nilai

425
00:22:13,420 --> 00:22:15,990
anda cari, maka
anda mahu untuk kembali benar.

426
00:22:15,990 --> 00:22:19,280
Jadi, pada asasnya, jika anda berada di nod yang
mempunyai nilai yang anda cari,

427
00:22:19,280 --> 00:22:23,550
anda tahu bahawa anda telah
dapat berjaya mencari.

428
00:22:23,550 --> 00:22:27,150
>> Jika tidak, anda mahu untuk menetapkan
penuding anda ke nod seterusnya.

429
00:22:27,150 --> 00:22:28,850
Itulah yang baris itu di sini lakukan.

430
00:22:28,850 --> 00:22:31,750
Penunjuk sama penunjuk akan datang.

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
merentasi keseluruhan senarai,

433
00:22:36,580 --> 00:22:41,920
menetapkan semula penunjuk anda setiap masa sehingga
anda akhirnya melanda akhir senarai.

434
00:22:41,920 --> 00:22:45,030
Dan anda tahu bahawa tidak ada
lebih nod untuk mencari melalui,

435
00:22:45,030 --> 00:22:47,999
dan kemudian anda boleh kembali palsu
kerana anda tahu bahawa, oh, baik,

436
00:22:47,999 --> 00:22:50,540
jika saya telah dapat mencari
melalui keseluruhan daripada senarai.

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

438
00:22:54,530 --> 00:22:57,250
dan saya bermula dari kepala, dan
Saya mencari semua jalan ke bawah,

439
00:22:57,250 --> 00:23:00,550
dan saya akhirnya mendapat untuk ini, yang
penunjuk yang menunjukkan batal,

440
00:23:00,550 --> 00:23:04,415
Saya tahu bahawa, crap, saya rasa 10 tidak ada di dalam
senarai ini kerana saya tidak dapat menemuinya.

441
00:23:04,415 --> 00:23:06,520
Dan saya pada akhir senarai.

442
00:23:06,520 --> 00:23:11,040
Dan di mana anda tahu
Saya 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 menjadi cantik
penting untuk pset anda.

445
00:23:17,350 --> 00:23:21,140
Logik ia adalah sangat mudah, mungkin
sintaksis hanya melaksanakannya.

446
00:23:21,140 --> 00:23:23,365
Kalian ingin
memastikan bahawa anda memahami.

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

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

449
00:23:27,650 --> 00:23:32,560
>> OK, jadi bagaimana kita akan
memasukkan nod, betul,

450
00:23:32,560 --> 00:23:35,380
ke dalam senarai kerana ingat
apakah apa manfaat

451
00:23:35,380 --> 00:23:39,230
mempunyai senarai berpaut berbanding
pelbagai dari segi simpanan?

452
00:23:39,230 --> 00:23:41,110
>> PENONTON: Ia adalah dinamik,
supaya lebih mudah supaya-

453
00:23:41,110 --> 00:23:43,180
>> ANDI PENG: Tepat sekali,
supaya lebih dinamik, yang

454
00:23:43,180 --> 00:23:46,880
bermakna bahawa ia boleh berkembang dan mengecut
bergantung kepada keperluan pengguna.

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

456
00:23:56,570 --> 00:24:00,850
jika saya tidak tahu berapa banyak nilai-nilai saya ingin
ke kedai, ia tidak masuk akal bagi saya

457
00:24:00,850 --> 00:24:04,310
untuk mewujudkan pelbagai kerana
jika saya mahu menyimpan 10 nilai

458
00:24:04,310 --> 00:24:08,380
dan saya membuat pelbagai 1000, itu
banyak memori sia-sia, diperuntukkan.

459
00:24:08,380 --> 00:24:11,180
Itulah sebabnya kita mahu menggunakan dikaitkan
senarai dapat dinamik

460
00:24:11,180 --> 00:24:13,860
menukar atau mengecilkan saiz kami.

461
00:24:13,860 --> 00:24:17,040
>> Dan sebagainya yang menjadikan sisipan
sedikit lebih rumit.

462
00:24:17,040 --> 00:24:20,810
Oleh kerana kita tidak boleh secara rawak mengakses elemen
dengan cara itu kita akan array.

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

464
00:24:24,270 --> 00:24:26,930
Saya hanya boleh masukkannya
ke dalam indeks yang ketujuh.

465
00:24:26,930 --> 00:24:30,020
Dalam senarai berpaut, ia tidak
cukup bersenam dengan mudah,

466
00:24:30,020 --> 00:24:34,947
dan jadi jika kita mahu memasukkan
apa-apa yang di sini dalam senarai berkaitan,

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

468
00:24:36,280 --> 00:24:39,363
Kami hanya mahu masukkannya di sana,
betul-betul di awal senarai,

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

470
00:24:40,840 --> 00:24:44,579
>> Tetapi cara di mana kita perlu memberi semula
petunjuk adalah agak berbelit

471
00:24:44,579 --> 00:24:47,620
atau, secara logik, ia masuk akal, tetapi
anda ingin memastikan bahawa anda mempunyai

472
00:24:47,620 --> 00:24:50,250
sepenuhnya ke bawah kerana
Perkara terakhir yang anda mahu

473
00:24:50,250 --> 00:24:52,990
adalah untuk memberi semula penunjuk yang
cara yang kita lakukan di sini.

474
00:24:52,990 --> 00:24:58,170
Jika anda dereference yang
penunjuk dari kepala hingga ke 1,

475
00:24:58,170 --> 00:25:01,086
maka semua yang secara tiba-tiba
seluruh senarai dipautkan anda

476
00:25:01,086 --> 00:25:04,680
hilang kerana anda tidak benar-benar mempunyai
mencipta apa-apa sementara.

477
00:25:04,680 --> 00:25:06,220
Itu menunjukkan kepada 2.

478
00:25:06,220 --> 00:25:10,080
Jika anda memberi semula penunjuk, maka
seluruh senarai anda sama sekali hilang.

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

480
00:25:13,310 --> 00:25:17,010
terlebih dahulu menetapkan
penunjuk dari apa sahaja yang anda

481
00:25:17,010 --> 00:25:20,150
mahu masukkan ke dalam di mana sahaja
yang anda mahu, dan kemudian anda

482
00:25:20,150 --> 00:25:22,710
boleh dereference seluruh senarai anda.

483
00:25:22,710 --> 00:25:25,250
>> Jadi ini terpakai kerana di mana sahaja
anda cuba untuk memasukkan ke dalam.

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

485
00:25:27,520 --> 00:25:29,455
jika anda ingin memasukkan di
Akhirnya, dengan baik, akhir saya

486
00:25:29,455 --> 00:25:30,910
rasa anda akan hanya
tidak mempunyai penunjuk, tetapi anda

487
00:25:30,910 --> 00:25:33,830
ingin memastikan bahawa anda tidak
kehilangan yang lain dalam senarai anda.

488
00:25:33,830 --> 00:25:36,640
Anda sentiasa ingin memastikan
nod baru anda menunjuk

489
00:25:36,640 --> 00:25:39,330
terhadap apa sahaja yang anda
mahu masukkan ke dalam,

490
00:25:39,330 --> 00:25:42,170
dan kemudian anda boleh menambah chaining pada.

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

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

493
00:25:45,427 --> 00:25:48,010
Salah satu isu yang paling utama
anda akan ada di pset anda

494
00:25:48,010 --> 00:25:51,340
adalah bahawa anda akan cuba untuk membuat
senarai berpaut dan perkara-perkara sisipan

495
00:25:51,340 --> 00:25:53,340
tetapi kemudian hanya kehilangan
seluruh senarai terkait dengannya.

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

497
00:25:54,900 --> 00:25:58,040
Dan ia sakit untuk pergi melalui
dan mencari semua petunjuk anda.

498
00:25:58,040 --> 00:26:02,100
>> Dan saya jamin anda di pset ini,
menulis dan melukis nod ini keluar

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

500
00:26:03,344 --> 00:26:06,010
Jadi, anda boleh benar-benar mengesan
di mana semua petunjuk anda berada,

501
00:26:06,010 --> 00:26:08,540
apa yang berlaku salah,
di mana semua nod anda berada,

502
00:26:08,540 --> 00:26:12,660
apa yang anda perlu lakukan untuk mencapai atau
memasukkan atau memadam atau mana-mana daripada mereka.

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

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

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

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

507
00:26:22,600 --> 00:26:24,470
Oh, saya tidak tahu jika kita
boleh lihat OK the--, jadi

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

509
00:26:27,940 --> 00:26:31,365
untuk memasukkan int n ke dalam senarai berkaitan.

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

511
00:26:32,740 --> 00:26:34,770
Ia banyak kod, banyak sintaks baru.

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

513
00:26:36,220 --> 00:26:39,120
>> Jadi sehingga di bahagian atas, bila-bila masa
kita mahu membuat apa-apa

514
00:26:39,120 --> 00:26:42,380
apa yang kita perlu lakukan, terutamanya jika anda
mahu ia tidak disimpan pada timbunan

515
00:26:42,380 --> 00:26:43,920
tetapi dalam timbunan itu?

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

517
00:26:45,460 --> 00:26:48,240
Jadi, kita akan mewujudkan penunjuk.

518
00:26:48,240 --> 00:26:52,074
Node, penunjuk, setaraf baru
malloc saiz nod

519
00:26:52,074 --> 00:26:53,740
kerana kita mahu nod yang diwujudkan.

520
00:26:53,740 --> 00:26:56,720
Kita mahu jumlah
memori yang nod mengambil

521
00:26:56,720 --> 00:26:59,300
yang akan diperuntukkan untuk
penciptaan nod baru.

522
00:26:59,300 --> 00:27:02,270
>> Dan kemudian kita akan menyemak untuk
melihat jika setaraf 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 sahaja yang anda malloc,
apa yang perlu anda sentiasa lakukan?

525
00:27:06,470 --> 00:27:09,490
Anda mesti sentiasa memeriksa untuk melihat
sama ada atau tidak itu adalah null.

526
00:27:09,490 --> 00:27:13,620
>> Sebagai contoh, jika operasi anda
sistem itu benar-benar penuh,

527
00:27:13,620 --> 00:27:17,060
jika anda mempunyai memori tidak lebih di
semua dan anda cuba untuk malloc,

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

529
00:27:18,410 --> 00:27:21,094
Dan jadi jika anda cuba untuk menggunakannya
apabila ia menunjuk kepada batal,

530
00:27:21,094 --> 00:27:23,260
anda tidak akan dapat
untuk mengakses maklumat tersebut.

531
00:27:23,260 --> 00:27:27,010
Dan sebagainya oleh itu, kami mahu membuat
memastikan bahawa setiap kali anda mallocing,

532
00:27:27,010 --> 00:27:30,500
anda sentiasa memeriksa untuk melihat jika
memori yang diberikan kepada anda adalah null.

533
00:27:30,500 --> 00:27:33,670
Dan jika tidak, maka kita boleh bergerak
pada dengan seluruh kod kami.

534
00:27:33,670 --> 00:27:36,140
>> Oleh itu, kita akan
memulakan nod baru.

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

536
00:27:39,050 --> 00:27:42,390
Dan kemudian kita akan lakukan
set baru penunjuk pada baru

537
00:27:42,390 --> 00:27:46,900
untuk null kerana sekarang kita tidak
mahu apa-apa untuk itu untuk menunjukkan.

538
00:27:46,900 --> 00:27:48,755
Kami tidak tahu di mana
ia akan meletakkan anda,

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

540
00:27:50,630 --> 00:27:53,820
maka kita boleh memberi semula
penunjuk kepada kepala.

541
00:27:53,820 --> 00:27:58,530
Adakah semua orang ikut logik
di mana yang yang berlaku?

542
00:27:58,530 --> 00:28:02,502
>> Semua yang kita lakukan adalah mewujudkan yang baru
nod, menetapkan penunjuk kepada batal,

543
00:28:02,502 --> 00:28:04,210
dan kemudian, tetapkan semula
kepada kepala jika kita

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

545
00:28:06,320 --> 00:28:09,420
Kemudian kepala akan
menghala ke nod 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 ia adalah satu proses dua langkah.

548
00:28:12,380 --> 00:28:14,760
Anda perlu menyerahhakkan pertama
apa sahaja yang anda buat.

549
00:28:14,760 --> 00:28:18,260
Menetapkan bahawa penunjuk kepada
rujukan, dan kemudian anda

550
00:28:18,260 --> 00:28:21,400
boleh jenis dereference
penunjuk pertama

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

552
00:28:22,972 --> 00:28:25,680
Di mana sahaja anda mahu memasukkannya,
logik yang akan memegang benar.

553
00:28:25,680 --> 00:28:27,530
>> Ia adalah jenis seperti memberikan
pembolehubah sementara.

554
00:28:27,530 --> 00:28:28,700
Ingat, anda mempunyai
memastikan bahawa anda

555
00:28:28,700 --> 00:28:30,346
tidak kehilangan jejak jika anda bertukar-tukar.

556
00:28:30,346 --> 00:28:33,470
Anda ingin memastikan bahawa anda mempunyai
pembolehubah sementara yang jenis menyimpan

557
00:28:33,470 --> 00:28:35,620
mengesan di mana perkara yang
disimpan supaya anda

558
00:28:35,620 --> 00:28:41,190
tidak kehilangan apa-apa nilai dalam perjalanan
daripada seperti main-main dengannya.

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

560
00:28:42,710 --> 00:28:45,020
Kalian lihat selepas seksyen.

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

562
00:28:48,060 --> 00:28:50,280
>> Jadi saya rasa bagaimana
ini berbeza jika kita mahu

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

564
00:28:52,300 --> 00:28:57,892
Adakah sesiapa yang mempunyai idea tentang apa yang yang
pseudokod sebagai rujukan logik

565
00:28:57,892 --> 00:29:00,350
bahawa kami akan mengambil jika kita mahu
untuk memasukkannya di tengah-tengah?

566
00:29:00,350 --> 00:29:03,391
Jadi, jika kita mahu masukkannya di
kepala, semua yang kita lakukan adalah mewujudkan nod baru.

567
00:29:03,391 --> 00:29:06,311
Kami menetapkan penunjuk yang
nod baru kepada apa sahaja kepala,

568
00:29:06,311 --> 00:29:08,310
dan kemudian kita set kepala
kepada nod baru, bukan?

569
00:29:08,310 --> 00:29:11,560
Jika kita mahu masukkannya di tengah-tengah
senarai, apa yang kita perlu lakukan?

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

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

572
00:29:16,110 --> 00:29:19,114
daripada seperti memberikan penunjuk dan
kemudian memberikan penunjuk yang,

573
00:29:19,114 --> 00:29:20,530
tetapi kita perlu untuk mencari di sana.

574
00:29:20,530 --> 00:29:23,560
>> ANDI PENG: Tepat sekali, jadi betul-betul
proses yang sama kecuali anda

575
00:29:23,560 --> 00:29:27,820
perlu mencari di mana sebenarnya anda
mahu itu penunjuk baru untuk pergi ke dalam,

576
00:29:27,820 --> 00:29:44,790
jadi jika saya mahu masukkan ke dalam
pertengahan dikaitkan list-- OK,

577
00:29:44,790 --> 00:29:46,370
mari kita mengatakan bahawa senarai berpaut kami.

578
00:29:46,370 --> 00:29:49,500
Jika kita mahu masukkannya di sini,
kita akan mewujudkan nod baru.

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

580
00:29:50,520 --> 00:29:52,220
Kami akan mewujudkan nod baru.

581
00:29:52,220 --> 00:29:55,940
Kita akan menyerahhakkan
penunjuk nod ini di sini.

582
00:29:55,940 --> 00:29:58,335
>> Tetapi masalah yang berbeza
dari mana kepala adalah

583
00:29:58,335 --> 00:30:00,490
ialah kita tahu betul-betul
mana kepala itu.

584
00:30:00,490 --> 00:30:01,930
Ia adalah betul-betul di pertama, bukan?

585
00:30:01,930 --> 00:30:04,870
Tetapi di sini kita telah mendapat untuk mengesan
di mana kita memasukkan ke dalam.

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

587
00:30:07,930 --> 00:30:12,270
untuk memastikan bahawa
satu sebelumnya kepada nod ini

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

589
00:30:14,172 --> 00:30:16,380
Demikian maka anda perlu jenis
mengesan dua perkara.

590
00:30:16,380 --> 00:30:19,420
Jika anda menjejaki di mana ini
nod kini sedang memasukkan ke dalam.

591
00:30:19,420 --> 00:30:23,280
Anda juga perlu menjejaki di mana
nod yang sebelumnya yang anda cari di

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

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

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

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

596
00:30:28,000 --> 00:30:34,220
Jika saya mahu menambah sini-- jika saya mahu
untuk menambah nod baru ke akhir senarai,

597
00:30:34,220 --> 00:30:37,009
bagaimana mungkin saya boleh pergi tentang melakukan perkara itu?

598
00:30:37,009 --> 00:30:39,300
PENONTON: Jadi pada masa ini,
menegaskan terkini untuk null.

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

600
00:30:40,960 --> 00:30:43,560
Tepat sekali, jadi yang satu ini
kini sedang menunjuk kepada tahu,

601
00:30:43,560 --> 00:30:46,720
dan saya rasa, dalam hal ini, ia
sangat mudah untuk menambah ke akhir senarai.

602
00:30:46,720 --> 00:30:51,810
Apa yang anda perlu lakukan adalah menetapkan
sama dengan nol dan kemudian meledak.

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

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

605
00:30:53,960 --> 00:30:56,430
>> Hampir sama dengan
kepala, tetapi secara logik anda

606
00:30:56,430 --> 00:30:59,690
ingin memastikan bahawa langkah-langkah
anda ambil ke arah melakukan apa-apa itu,

607
00:30:59,690 --> 00:31:01,500
anda ikuti bersama-sama.

608
00:31:01,500 --> 00:31:04,420
Ia sangat mudah untuk, di tengah-tengah
kod anda, terjebak pada,

609
00:31:04,420 --> 00:31:05,671
oh, saya telah mendapat begitu banyak petunjuk.

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

611
00:31:07,461 --> 00:31:09,170
Saya tidak tahu mana buku saya pada.

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

613
00:31:11,490 --> 00:31:13,620
>> Berehat, bertenang, tarik nafas dalam-dalam.

614
00:31:13,620 --> 00:31:15,530
Menarik keluar senarai berpaut anda.

615
00:31:15,530 --> 00:31:18,800
Jika anda berkata, saya tahu di mana sebenarnya
Saya perlu memasukkan ini ke dalam

616
00:31:18,800 --> 00:31:22,970
dan saya tahu bagaimana untuk memberi semula saya
petunjuk, banyak, lebih mudah untuk gambar

617
00:31:22,970 --> 00:31:27,200
out-- banyak, lebih mudah untuk tidak
hilang dalam bug kod anda.

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

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

620
00:31:31,380 --> 00:31:35,120
>> Jadi saya rasa satu konsep yang kita tidak mempunyai
benar-benar bercakap tentang sebelum ini,

621
00:31:35,120 --> 00:31:38,131
dan saya rasa anda mungkin
tidak akan menghadapi banyak YET

622
00:31:38,131 --> 00:31:40,880
ia adalah jenis yang concept-- maju
adalah bahawa kita benar-benar mempunyai data

623
00:31:40,880 --> 00:31:43,900
struktur dipanggil senarai duanya adalah terpakai dikaitkan.

624
00:31:43,900 --> 00:31:46,390
Jadi seperti yang anda semua boleh lihat,
semua yang kita lakukan adalah mewujudkan

625
00:31:46,390 --> 00:31:50,400
nilai sebenar, tambahan
penunjuk pada setiap nod kami

626
00:31:50,400 --> 00:31:52,660
yang juga menunjukkan nod sebelumnya.

627
00:31:52,660 --> 00:31:58,170
Jadi bukan sahaja kita perlu kami
nod menunjukkan satu depan.

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

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

630
00:32:04,310 --> 00:32:06,740
>> Sebab itu anda mempunyai rantai
yang boleh bergerak kedua-dua cara,

631
00:32:06,740 --> 00:32:09,630
dan kemudian ia sedikit lebih mudah
secara logik ikut bersama-sama.

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

633
00:32:11,896 --> 00:32:14,520
perlu tahu bahawa nod ini adalah
satu yang saya perlu menyerahhakkan semula,

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

635
00:32:17,532 --> 00:32:19,490
Kemudian saya tahu di mana
iaitu, dan kemudian anda

636
00:32:19,490 --> 00:32:21,130
tidak perlu merentasi
keseluruhan daripada senarai berkaitan.

637
00:32:21,130 --> 00:32:22,180
Ia agak mudah.

638
00:32:22,180 --> 00:32:24,960
>> Tetapi oleh itu, anda mempunyai dua kali ganda
jumlah petunjuk,

639
00:32:24,960 --> 00:32:26,960
itu dua kali ganda jumlah ingatan.

640
00:32:26,960 --> 00:32:28,950
Ia banyak petunjuk untuk mengesan.

641
00:32:28,950 --> 00:32:32,140
Ia adalah sedikit lebih kompleks, tetapi ia
sedikit lebih mesra pengguna bergantung

642
00:32:32,140 --> 00:32:34,080
kepada apa yang anda cuba untuk mencapai.

643
00:32:34,080 --> 00:32:36,910
>> Jadi ini jenis data
struktur betul-betul wujud,

644
00:32:36,910 --> 00:32:40,280
dan struktur adalah sangat, sangat
mudah kecuali semua yang anda perlu adalah,

645
00:32:40,280 --> 00:32:43,850
bukan hanya penunjuk kepada akan datang,
anda juga mempunyai penunjuk kepada sebelumnya.

646
00:32:43,850 --> 00:32:45,940
Itu semua perbezaan adalah.

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

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

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

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

651
00:32:53,280 --> 00:32:56,870
seperti 15 hingga 20 minit atau sebahagian besar
negara lain di masa dalam seksyen

652
00:32:56,870 --> 00:32:58,360
bercakap tentang jadual hash.

653
00:32:58,360 --> 00:33:02,590
Berapa ramai daripada anda semua
telah membaca pset5 spec?

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

655
00:33:03,620 --> 00:33:06,160
Itulah yang lebih tinggi daripada 50% daripada biasa.

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

657
00:33:07,560 --> 00:33:10,345
>> Jadi seperti yang anda semua lihat,
anda berada cabaran dalam pset5

658
00:33:10,345 --> 00:33:16,790
adalah untuk melaksanakan kamus yang
di mana anda memuatkan lebih 140,000 perkataan

659
00:33:16,790 --> 00:33:20,610
bahawa kami memberikan anda dan periksa ejaan
ia terhadap semua teks.

660
00:33:20,610 --> 00:33:22,580
Kami akan memberikan anda secara rawak
bahan kempen.

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

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

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

664
00:33:26,350 --> 00:33:28,220
>> Dan cabaran anda
adalah untuk periksa ejaan

665
00:33:28,220 --> 00:33:31,760
setiap perkataan dalam semua
dari orang-orang kamus

666
00:33:31,760 --> 00:33:34,960
dasarnya dengan penyemak ejaan kami.

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

668
00:33:38,620 --> 00:33:41,970
pertama yang anda mahu
dapat benar-benar memuatkan

669
00:33:41,970 --> 00:33:43,970
semua perkataan ke dalam anda
kamus, dan kemudian anda

670
00:33:43,970 --> 00:33:45,530
hendak dapat
semak ejaan semua daripada mereka.

671
00:33:45,530 --> 00:33:48,780
Dan sebagainya oleh itu, anda akan memerlukan
struktur data yang boleh melakukan ini cepat

672
00:33:48,780 --> 00:33:50,790
dan cekap dan dinamik.

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

674
00:33:52,900 --> 00:33:55,010
mungkin akan mewujudkan pelbagai, bukan?

675
00:33:55,010 --> 00:33:58,910
Cara yang paling mudah penyimpanan adalah anda
boleh membuat pelbagai 140,000 kata-kata

676
00:33:58,910 --> 00:34:03,400
dan hanya meletakkan mereka semua di sana dan
kemudian merentasi mereka dengan carian binari

677
00:34:03,400 --> 00:34:06,780
atau oleh pilihan atau tidak--
maaf yang yang menyusun.

678
00:34:06,780 --> 00:34:10,729
Anda boleh menyusun mereka dan kemudian mereka merentasi
oleh carian binari atau carian hanya linear

679
00:34:10,729 --> 00:34:13,730
dan hanya akhir perkataan, tetapi itu
mengambil sejumlah besar memori,

680
00:34:13,730 --> 00:34:15,190
dan ia bukan sangat cekap.

681
00:34:15,190 --> 00:34:18,350
>> Dan dengan itu kita akan mula
bercakap mengenai cara-cara membuat

682
00:34:18,350 --> 00:34:20,110
masa kita berjalan lebih cekap.

683
00:34:20,110 --> 00:34:23,190
Dan matlamat kami adalah untuk mendapatkan
masa yang berterusan di mana

684
00:34:23,190 --> 00:34:25,810
ia hampir seperti tatasusunan, di mana
anda mempunyai akses serta-merta.

685
00:34:25,810 --> 00:34:28,560
Jika saya mahu mencari apa-apa,
Saya hendak dapat adil,

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

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

688
00:34:34,100 --> 00:34:37,569
dapat mengakses berterusan
masa, ini kaedah berpotensi suci

689
00:34:37,569 --> 00:34:41,370
dalam pengaturcaraan pemalar
masa dipanggil jadual hash.

690
00:34:41,370 --> 00:34:45,370
Dan begitu Daud sebelum ini menyebut tentang
[Didengar] sedikit dalam kuliah,

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

692
00:34:49,100 --> 00:34:51,780
di atas sekeping yang yang mengenai
bagaimana jadual hash berfungsi.

693
00:34:51,780 --> 00:34:53,949
>> Jadi cara yang hash
kerja-kerja meja, sebagai contoh,

694
00:34:53,949 --> 00:35:00,230
jika saya mahu menyimpan sekumpulan kata-kata,
sekumpulan kata-kata dalam bahasa Inggeris,

695
00:35:00,230 --> 00:35:02,940
Saya secara teori boleh meletakkan
pisang, epal, kiwi, mangga, pasangan,

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

697
00:35:04,980 --> 00:35:07,044
Mereka semua dapat menyesuaikan diri dan dapat mencari.

698
00:35:07,044 --> 00:35:09,210
Ia akan menjadi jenis sakit untuk
mencari melalui dan akses,

699
00:35:09,210 --> 00:35:12,920
tetapi cara yang lebih mudah untuk melakukan ini adalah
bahawa kita boleh mewujudkan struktur yang sebenarnya

700
00:35:12,920 --> 00:35:15,680
dipanggil jadual 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
beberapa jenis nilai yang

703
00:35:22,600 --> 00:35:28,740
yang kemudian kita boleh simpan pada
pada dasarnya pelbagai senarai berkaitan.

704
00:35:28,740 --> 00:35:32,570
>> Dan sebagainya di sini, jika kita mahu
untuk menyimpan perkataan Inggeris,

705
00:35:32,570 --> 00:35:37,250
kita boleh berpotensi adil, saya tidak
tahu, menukar semua huruf pertama

706
00:35:37,250 --> 00:35:39,630
ke dalam beberapa jenis nombor.

707
00:35:39,630 --> 00:35:43,140
Dan sebagainya, sebagai contoh, jika saya mahu
A menjadi sinonim dengan apple--

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

709
00:35:47,460 --> 00:35:51,030
kita boleh mempunyai 26 penyertaan
yang hanya boleh menyimpan

710
00:35:51,030 --> 00:35:53,610
semua huruf daripada
abjad bahawa kita akan memulakan dengan.

711
00:35:53,610 --> 00:35:56,130
Dan kemudian kita boleh mempunyai
epal di indeks 0.

712
00:35:56,130 --> 00:35:59,160
Kita boleh mempunyai pisang di indeks
1, tembikai pada 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 itu jika saya mahu mencari
hash meja dan akses epal saya,

715
00:36:04,460 --> 00:36:07,560
Saya tahu epal bermula dengan
A, dan saya tahu

716
00:36:07,560 --> 00:36:10,860
bahawa ia mesti dan hash
meja di indeks 0 kerana

717
00:36:10,860 --> 00:36:13,620
fungsi yang diberikan sebelum ini.

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

719
00:36:16,572 --> 00:36:18,780
anda akan dikenakan bayaran dengan
tidak arbitrarily-- sewenang-wenangnya,

720
00:36:18,780 --> 00:36:22,530
dengan cuba untuk teliti
berfikir persamaan baik

721
00:36:22,530 --> 00:36:25,460
dapat menyebarkan
keluar semua nilai-nilai anda

722
00:36:25,460 --> 00:36:29,370
dengan cara yang mereka dengan mudah boleh mengakses
kemudian di dengan seperti persamaan

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

724
00:36:31,130 --> 00:36:35,210
Jadi dalam erti kata yang jika saya mahu pergi ke
mangga, saya tahu, oh, ia bermula dengan m.

725
00:36:35,210 --> 00:36:37,134
Ia mesti sekurang-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
Saya tahu exactly-- saya hanya boleh pergi ke
indeks 12 dan tarik yang keluar.

728
00:36:42,080 --> 00:36:45,520
>> Semua orang yang jelas mengenai bagaimana
fungsi jadual hash ini berfungsi?

729
00:36:45,520 --> 00:36:48,380
Ia adalah jenis hanya lokasi yang lebih kompleks.

730
00:36:48,380 --> 00:36:50,010
Itu sahaja yang ia adalah.

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

732
00:36:51,630 --> 00:36:57,690
>> Jadi saya rasa kita menghadapi
isu ini daripada apa yang

733
00:36:57,690 --> 00:37:06,390
berlaku jika anda mempunyai beberapa perkara yang
yang memberikan indeks yang sama?

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

735
00:37:10,570 --> 00:37:14,490
dan menghidupkan yang menjadi
masing-0 melalui 25 indeks.

736
00:37:14,490 --> 00:37:17,137
Yang sama sekali baik jika
anda hanya mempunyai satu masing-masing.

737
00:37:17,137 --> 00:37:18,970
Tetapi kedua anda mula
mempunyai lebih banyak, anda

738
00:37:18,970 --> 00:37:20,910
akan mempunyai apa yang dipanggil perlanggaran.

739
00:37:20,910 --> 00:37:25,580
>> Jadi, jika saya cuba untuk memasukkan ke dalam mengebumikan hash
jadual yang sudah mempunyai pisang di atasnya,

740
00:37:25,580 --> 00:37:27,870
apa yang akan berlaku apabila
anda cuba untuk memasukkan itu?

741
00:37:27,870 --> 00:37:30,930
Perkara-perkara buruk kerana pisang
sudah wujud dalam indeks

742
00:37:30,930 --> 00:37:33,800
yang ingin anda simpan ke dalam.

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

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

745
00:37:37,080 --> 00:37:38,410
Bagaimana saya boleh menyelesaikan ini?

746
00:37:38,410 --> 00:37:41,150
>> Dan supaya anda semua jenis kehendaki di antara
melihat kita melakukan perkara ini rumit

747
00:37:41,150 --> 00:37:44,810
di mana kita boleh sejenis sebenarnya
membuat senarai dikaitkan dalam tatasusunan kami.

748
00:37:44,810 --> 00:37:46,840
Jadi cara yang paling mudah dan
untuk berfikir tentang perkara ini,

749
00:37:46,840 --> 00:37:50,830
semua jadual hash adalah
pelbagai senarai berkaitan.

750
00:37:50,830 --> 00:37:55,670
Dan sebagainya, dalam erti kata itu, anda perlu
pelbagai ini indah petunjuk,

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

752
00:37:58,740 --> 00:38:00,740
sebenarnya boleh menunjukkan kepada perkara-perkara lain.

753
00:38:00,740 --> 00:38:05,720
Dan supaya anda mempunyai semua yang berasingan
rantai datang kira satu array besar.

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

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

756
00:38:11,220 --> 00:38:15,070
Saya akan berakhir dengan indeks
1, dan kemudian saya akan dapat mempunyai

757
00:38:15,070 --> 00:38:20,410
hanya subset yang lebih kecil ini
gergasi kamus 140,000 perkataan.

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

759
00:38:24,220 --> 00:38:27,910
>> Dan demikian maka saya hanya boleh memasukkan
berry sama ada sebelum atau selepas pisang

760
00:38:27,910 --> 00:38:28,820
dalam kes ini?

761
00:38:28,820 --> 00:38:29,700
Selepas, bukan?

762
00:38:29,700 --> 00:38:33,920
Dan supaya anda akan mahu untuk
memasukkan nod ini selepas pisang,

763
00:38:33,920 --> 00:38:36,667
dan supaya anda akan memasukkan
di ekor bahawa senarai berkaitan.

764
00:38:36,667 --> 00:38:38,500
Saya akan kembali
untuk slaid ini sebelumnya,

765
00:38:38,500 --> 00:38:40,680
supaya anda semua boleh lihat bagaimana
fungsi hash berfungsi.

766
00:38:40,680 --> 00:38:43,980
>> Jadi fungsi hash adalah persamaan ini
bahawa anda menjalankan jenis input anda

767
00:38:43,980 --> 00:38:46,940
melalui untuk mendapatkan apa sahaja indeks
anda ingin gunakan ke arah.

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

769
00:38:51,130 --> 00:38:55,890
berubah itu ke dalam indeks, maka kita
boleh menyimpan bahawa dalam fungsi hash kami.

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

771
00:39:00,160 --> 00:39:04,770
Jadi keykey [0] hanya huruf pertama
apa jua rentetan kita yang mempunyai,

772
00:39:04,770 --> 00:39:05,720
kita lulus dalam.

773
00:39:05,720 --> 00:39:09,740
Kami menukar bahawa untuk atas, dan
kami menolak dengan huruf besar A,

774
00:39:09,740 --> 00:39:11,740
jadi semua yang melakukan
memberi kami nombor satu

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

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

777
00:39:16,550 --> 00:39:19,340
Menjadi sangat, sangat berhati-hati
kerana, secara teori, di sini

778
00:39:19,340 --> 00:39:21,870
nilai hash anda boleh menjadi tak terhingga.

779
00:39:21,870 --> 00:39:23,660
Ia hanya boleh pergi pada dan pada dan pada.

780
00:39:23,660 --> 00:39:26,080
Ia boleh menjadi beberapa benar-benar,
benar-benar nilai besar,

781
00:39:26,080 --> 00:39:29,849
tetapi kerana jadual hash anda yang
anda telah membuat hanya mempunyai 26 indeks,

782
00:39:29,849 --> 00:39:31,890
anda ingin memastikan anda
modulusing supaya anda

783
00:39:31,890 --> 00:39:33,848
tidak run-- ia adalah sama
Perkara seperti queue-- anda

784
00:39:33,848 --> 00:39:36,320
supaya anda tidak lari daripada
bawah fungsi hash anda.

785
00:39:36,320 --> 00:39:39,210
>> Anda mahu balut kembali sekitar
cara yang sama dalam [didengar] apabila

786
00:39:39,210 --> 00:39:41,750
anda mempunyai seperti yang sangat,
surat sangat besar, anda

787
00:39:41,750 --> 00:39:43,740
tidak mahu itu
hanya berjalan melepasi hujung meja.

788
00:39:43,740 --> 00:39:46,948
Perkara yang sama di sini, anda ingin memastikan
ia tidak lari akhirnya dengan membalut

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

790
00:39:48,330 --> 00:39:50,530
Jadi ini adalah hanya sangat
fungsi hash mudah.

791
00:39:50,530 --> 00:39:56,570
Semua yang dilakukan adalah mengambil yang pertama
surat apa-apa input kami adalah

792
00:39:56,570 --> 00:40:01,660
dan menghidupkan itu ke dalam indeks yang
kita boleh meletakkan ke dalam jadual hash kami.

793
00:40:01,660 --> 00:40:05,450
>> Ya, dan sebagainya seperti yang saya katakan sebelum ini,
cara kita menyelesaikan perlanggaran

794
00:40:05,450 --> 00:40:09,330
dalam jadual hash kami menghadapi,
apa yang kita panggil, chaining.

795
00:40:09,330 --> 00:40:13,860
Jadi, jika anda cuba untuk memasukkan beberapa
kata-kata yang bermula dengan perkara yang sama,

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

797
00:40:16,145 --> 00:40:18,770
Avokado dan epal, jika anda telah
menjalankannya melalui fungsi hash kami,

798
00:40:18,770 --> 00:40:21,450
akan memberikan anda
Bilangan yang sama, bilangan 0.

799
00:40:21,450 --> 00:40:24,550
Dan begitu cara kita menyelesaikan yang
bahawa kita boleh sebenarnya jenis menghubungkan mereka

800
00:40:24,550 --> 00:40:27,010
bersama-sama melalui senarai berkaitan.

801
00:40:27,010 --> 00:40:29,600
>> Dan sebagainya dalam hal ini,
anda semua boleh 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 dikaitkan senarai jenis
daripada boleh datang bersama-sama ke dalam satu.

804
00:40:35,870 --> 00:40:38,860
Dan kemudian anda boleh membuat jauh
struktur data yang lebih cekap

805
00:40:38,860 --> 00:40:43,350
yang boleh mengendalikan jumlah yang lebih besar
data, yang secara dinamik mengubah saiz bergantung

806
00:40:43,350 --> 00:40:44,870
kepada keperluan anda.

807
00:40:44,870 --> 00:40:45,620
Semua orang jelas?

808
00:40:45,620 --> 00:40:47,580
Jenis orang yang jelas
kepada apa yang berlaku di sini?

809
00:40:47,580 --> 00:40:52,110
>> Jika saya mahu insert-- apa yang a
buah-buahan yang bermula dengan, saya tidak tahu,

810
00:40:52,110 --> 00:40:54,726
B, selain beri, pisang.

811
00:40:54,726 --> 00:40:55,710
>> PENONTON: Blackberry.

812
00:40:55,710 --> 00:40:57,910
>> ANDI PENG: Blackberry, blackberry.

813
00:40:57,910 --> 00:41:00,530
Di manakah blackberry pergi sini?

814
00:41:00,530 --> 00:41:04,251
Nah, kita benar-benar tidak disusun
ini lagi, tetapi secara teori

815
00:41:04,251 --> 00:41:06,250
jika kita mahu mempunyai ini
mengikut abjad,

816
00:41:06,250 --> 00:41:07,944
di mana perlu BlackBerry pergi?

817
00:41:07,944 --> 00:41:09,210
>> PENONTON: [didengar]

818
00:41:09,210 --> 00:41:11,100
>> ANDI PENG: Tepat sekali, selepas di sini, bukan?

819
00:41:11,100 --> 00:41:14,950
Tetapi oleh kerana ia amat sukar untuk
reorder-- Saya rasa ia terpulang kepada anda semua.

820
00:41:14,950 --> 00:41:17,920
Anda semua boleh sama sekali
melaksanakan apa sahaja yang anda mahu.

821
00:41:17,920 --> 00:41:20,730
Cara yang lebih cekap
untuk berbuat demikian mungkin

822
00:41:20,730 --> 00:41:24,570
adalah untuk menyusun dipautkan anda
senarai ke dalam susunan abjad,

823
00:41:24,570 --> 00:41:26,520
dan sebagainya apabila anda berada
memasukkan sesuatu, anda mahu

824
00:41:26,520 --> 00:41:28,632
untuk memastikan untuk memasukkan mereka
ke dalam susunan abjad

825
00:41:28,632 --> 00:41:30,590
supaya kemudian apabila anda berada
cuba untuk mencari mereka,

826
00:41:30,590 --> 00:41:32,410
anda tidak perlu merentasi segala-galanya.

827
00:41:32,410 --> 00:41:35,290
Anda tahu di mana
ia adalah, dan ia lebih mudah.

828
00:41:35,290 --> 00:41:39,100
>> Tetapi jika anda jenis mempunyai
perkara yang berselang secara rawak,

829
00:41:39,100 --> 00:41:41,420
anda masih akan mempunyai
untuk merentasi ia anyways.

830
00:41:41,420 --> 00:41:44,990
Dan jadi jika saya mahu hanya
memasukkan blackberry sini

831
00:41:44,990 --> 00:41:47,470
dan saya mahu mencari
, saya tahu, oh, blackberry

832
00:41:47,470 --> 00:41:52,012
mesti bermula dengan indeks 1, jadi saya
tahu serta-merta hanya mencari di 1.

833
00:41:52,012 --> 00:41:53,970
Dan kemudian saya boleh jenis
merentasi senarai berkaitan

834
00:41:53,970 --> 00:41:56,120
sehingga saya dapat blackberry,
dan then-- ya?

835
00:41:56,120 --> 00:41:59,550
>> PENONTON: Jika anda cuba untuk create--
Saya rasa seperti ini adalah hash sangat mudah

836
00:41:59,550 --> 00:42:00,050
fungsi.

837
00:42:00,050 --> 00:42:02,835
Dan jika kita mahu lakukan
pelbagai lapisan seperti itu,

838
00:42:02,835 --> 00:42:05,870
OK, kita mahu untuk memisahkan ke dalam
seperti semua huruf abjad

839
00:42:05,870 --> 00:42:09,040
dan sekali lagi untuk suka set lain
huruf abjad dalam masa itu,

840
00:42:09,040 --> 00:42:11,715
kita meletakkan seperti hash
meja dalam jadual hash,

841
00:42:11,715 --> 00:42:13,256
atau seperti fungsi dalam satu majlis?

842
00:42:13,256 --> 00:42:14,880
Atau adakah bahawa-

843
00:42:14,880 --> 00:42:17,510
>> ANDI PENG: Jadi hash anda
function-- jadual hash anda

844
00:42:17,510 --> 00:42:19,360
boleh menjadi sebesar yang anda mahu ia.

845
00:42:19,360 --> 00:42:21,930
Jadi dalam hal ini, saya fikir
ia adalah sangat mudah, sangat

846
00:42:21,930 --> 00:42:25,320
mudah untuk saya hanya jenis berdasarkan
pada huruf perkataan pertama.

847
00:42:25,320 --> 00:42:28,690
Dan sebagainya hanya ada 26 pilihan.

848
00:42:28,690 --> 00:42:32,650
Saya hanya boleh mendapatkan 26 pilihan dari
0-25 kerana mereka hanya boleh

849
00:42:32,650 --> 00:42:36,510
mula dari A ke Z. Tetapi Jika anda mahu
untuk menambah, mungkin, lebih kompleks

850
00:42:36,510 --> 00:42:39,260
atau lebih cepat masa berjalan untuk anda
jadual hash, anda benar-benar

851
00:42:39,260 --> 00:42:40,760
boleh melakukan pelbagai perkara.

852
00:42:40,760 --> 00:42:43,330
Anda boleh membuat anda sendiri
persamaan yang memberikan anda

853
00:42:43,330 --> 00:42:48,000
agihan yang lebih dalam anda
kata-kata, maka ketika anda mencari,

854
00:42:48,000 --> 00:42:49,300
ia akan menjadi lebih cepat.

855
00:42:49,300 --> 00:42:52,100
>> Ia benar-benar terpulang kepada anda semua
bagaimana anda mahu untuk melaksanakan itu.

856
00:42:52,100 --> 00:42:55,140
Fikirkan ia sebagai hanya baldi.

857
00:42:55,140 --> 00:42:57,376
Jika saya mahu mempunyai
26 baldi, saya akan

858
00:42:57,376 --> 00:42:59,420
untuk menyelesaikan sesuatu ke dalam orang-orang baldi.

859
00:42:59,420 --> 00:43:02,980
Tetapi saya akan mempunyai sekumpulan
barangan dalam setiap baldi,

860
00:43:02,980 --> 00:43:05,890
jadi jika anda mahu membuat ia
lebih cepat dan lebih cekap,

861
00:43:05,890 --> 00:43:07,190
biarlah saya mempunyai seratus baldi.

862
00:43:07,190 --> 00:43:09,290
>> Tetapi kemudian anda perlu memikirkan satu
cara untuk menyelesaikan perkara-perkara supaya mereka

863
00:43:09,290 --> 00:43:11,040
dalam baldi yang betul mereka seharusnya berada di dalam.

864
00:43:11,040 --> 00:43:13,331
Tetapi apabila anda benar-benar
mahu melihat baldi itu,

865
00:43:13,331 --> 00:43:16,410
ia banyak lebih cepat kerana ada
barangan yang kurang dalam setiap baldi.

866
00:43:16,410 --> 00:43:20,250
Dan sebagainya, yeah, yang sebenarnya
helah untuk anda semua dalam pset5

867
00:43:20,250 --> 00:43:22,360
adalah bahawa anda akan menjadi
dicabar untuk hanya membuat

868
00:43:22,360 --> 00:43:26,170
apa yang paling berkesan
fungsi yang boleh anda fikirkan untuk menjadi

869
00:43:26,170 --> 00:43:28,520
dapat menyimpan dan memeriksa nilai-nilai ini.

870
00:43:28,520 --> 00:43:30,840
>> Benar-benar terpulang kepada anda semua
tetapi anda mahu untuk melakukannya,

871
00:43:30,840 --> 00:43:32,229
tetapi itu adalah satu titik benar-benar baik.

872
00:43:32,229 --> 00:43:34,520
Bahawa jenis logik anda
mahu untuk mula berfikir tentang

873
00:43:34,520 --> 00:43:37,236
adalah, baik, mengapa tidak saya membuat lebih banyak baldi.

874
00:43:37,236 --> 00:43:39,527
Dan kemudian saya perlu mencari
kurang sesuatu, dan mungkin saya

875
00:43:39,527 --> 00:43:41,640
mempunyai fungsi hash yang berbeza.

876
00:43:41,640 --> 00:43:45,500
>> Ya, terdapat banyak cara untuk melakukan ini
Serangga, ada yang lebih cepat daripada yang lain.

877
00:43:45,500 --> 00:43:50,630
Saya betul-betul akan hanya melihat bagaimana
cepat adalah yang paling cepat anda semua akan

878
00:43:50,630 --> 00:43:55,170
dapat untuk mendapatkan fungsi anda untuk bekerja.

879
00:43:55,170 --> 00:43:58,176
OK, semua orang di baik
chaining dan hash jadual?

880
00:43:58,176 --> 00:44:00,800
Ia sebenarnya seperti yang sangat mudah
konsep jika anda berfikir mengenainya.

881
00:44:00,800 --> 00:44:05,160
Semua itu adalah apa sahaja yang memisahkan
input anda adalah ke dalam baldi,

882
00:44:05,160 --> 00:44:10,670
menyusun mereka, dan kemudian mencari
menyenaraikan bahawa ada berkaitan dengan.

883
00:44:10,670 --> 00:44:11,852
>> Sejuk.

884
00:44:11,852 --> 00:44:18,160
Baiklah, sekarang kita mempunyai jenis yang berbeza
struktur data yang dinamakan pokok.

885
00:44:18,160 --> 00:44:20,850
Mari kita pergi pada dan bercakap tentang percubaan
yang jelas berbeza,

886
00:44:20,850 --> 00:44:22,330
tetapi dalam kategori yang sama.

887
00:44:22,330 --> 00:44:29,010
Pada asasnya, semua pokok adalah sebaliknya
menganjurkan data dengan cara yang linear

888
00:44:29,010 --> 00:44:32,560
bahawa jadual hash does-- anda
tahu, ia mendapat bahagian atas dan bawah yang

889
00:44:32,560 --> 00:44:37,900
dan kemudian anda jenis menghubungkan kira kitab itu yang
pokok mempunyai bahagian yang kamu seru akar,

890
00:44:37,900 --> 00:44:40,220
dan kemudian ia mempunyai daun sekelilingnya.

891
00:44:40,220 --> 00:44:42,390
>> Dan jadi apa yang anda ada di sini
hanya nod bahagian

892
00:44:42,390 --> 00:44:45,980
yang menunjuk ke nod lain, titik
kepada lebih nod, dan sebagainya dan sebagainya.

893
00:44:45,980 --> 00:44:48,130
Dan jadi anda hanya mempunyai cawangan berpisah.

894
00:44:48,130 --> 00:44:53,255
Ia hanya cara yang berbeza dalam menganjurkan
data, dan kerana kita memanggilnya pokok,

895
00:44:53,255 --> 00:44:56,270
anda semua just-- ia hanya
dimodelkan keluar kelihatan seperti pokok.

896
00:44:56,270 --> 00:44:57,670
Itulah sebabnya kita memanggilnya pokok.

897
00:44:57,670 --> 00:44:59,370
>> Jadual hash kelihatan seperti jadual.

898
00:44:59,370 --> 00:45:01,310
Pokok hanya kelihatan seperti pokok.

899
00:45:01,310 --> 00:45:03,300
Semua itu adalah yang berasingan
cara mengatur nod

900
00:45:03,300 --> 00:45:06,020
bergantung kepada apa keperluan anda.

901
00:45:06,020 --> 00:45:11,810
>> Jadi, anda mempunyai akar dan
maka anda mempunyai daun.

902
00:45:11,810 --> 00:45:15,380
Cara yang kita boleh terutamanya
berfikir tentang hal itu adalah pokok binari,

903
00:45:15,380 --> 00:45:18,150
pokok binari hanya
jenis tertentu pokok

904
00:45:18,150 --> 00:45:22,450
di mana setiap nod hanya mata
, sekurang-max, dua nod lain.

905
00:45:22,450 --> 00:45:25,434
Dan sebagainya di sini anda perlu berbeza
simetri dalam pokok anda

906
00:45:25,434 --> 00:45:28,600
yang menjadikan ia lebih mudah untuk jenis melihat
apa nilai anda kerana anda

907
00:45:28,600 --> 00:45:30,150
mempunyai sentiasa kiri atau kanan.

908
00:45:30,150 --> 00:45:33,150
Ada pernah seperti satu pertiga kiri dari
kiri atau keempat dari kiri.

909
00:45:33,150 --> 00:45:36,358
Ia hanya anda mempunyai kiri dan kanan yang
dan anda boleh mencari sama ada kedua-dua.

910
00:45:36,358 --> 00:45:38,980
Dan sebagainya mengapa ini berguna kepada anda?

911
00:45:38,980 --> 00:45:40,980
Cara bahawa ini adalah
berguna ialah jika anda sedang mencari

912
00:45:40,980 --> 00:45:42,890
untuk mencari melalui nilai-nilai, bukan?

913
00:45:42,890 --> 00:45:45,640
Daripada melaksanakan binari
mencari dalam pelbagai kesilapan,

914
00:45:45,640 --> 00:45:49,260
jika anda mahu menjadi mampu untuk memasukkan nod
dan mengambil nod sesuka hati dan juga

915
00:45:49,260 --> 00:45:52,185
memelihara carian
kapasiti carian binari.

916
00:45:52,185 --> 00:45:54,560
Jadi dengan cara ini, kami jenis
tricking-- masih ingat ketika kami

917
00:45:54,560 --> 00:45:56,530
berkata senarai berkaitan tidak boleh carian binari?

918
00:45:56,530 --> 00:46:01,700
Kami sejenis mewujudkan struktur data
bahawa helah itu ke dalam kerja.

919
00:46:01,700 --> 00:46:05,034
>> Dan senarai demikian kerana dikaitkan adalah linear,
mereka hanya menghubungkan satu demi satu.

920
00:46:05,034 --> 00:46:06,950
Kita boleh jenis mempunyai
jenis yang berbeza petunjuk

921
00:46:06,950 --> 00:46:09,408
ketika itu untuk nod yang berbeza
yang boleh membantu kami dengan carian.

922
00:46:09,408 --> 00:46:12,590
Dan sebagainya di sini, jika saya mahu
mempunyai pokok carian binari,

923
00:46:12,590 --> 00:46:14,090
Saya tahu bahawa tengah saya jika 55.

924
00:46:14,090 --> 00:46:18,280
Saya hanya akan membuat yang
sebagai tengah saya, kerana akar saya,

925
00:46:18,280 --> 00:46:20,770
dan kemudian saya akan mempunyai
nilai berputar jauh daripada itu.

926
00:46:20,770 --> 00:46:25,610
>> Jadi di sini, jika saya akan mencari
nilai 66, saya boleh bermula pada 55.

927
00:46:25,610 --> 00:46:27,310
Ia adalah 66 lebih besar daripada 55?

928
00:46:27,310 --> 00:46:30,970
Ya, ia adalah, jadi saya tahu saya mus mencari
i n penunjuk yang betul pokok ini.

929
00:46:30,970 --> 00:46:32,440
Saya pergi ke 77.

930
00:46:32,440 --> 00:46:35,367
OK, adalah 66 kurang daripada atau lebih daripada 77?

931
00:46:35,367 --> 00:46:37,950
Ia adalah kurang daripada, supaya anda tahu, oh,
yang telah menjadi nod kiri.

932
00:46:37,950 --> 00:46:41,410
>> Dan jadi di sini kita jenis memelihara
semua perkara yang menarik mengenai tatasusunan,

933
00:46:41,410 --> 00:46:44,420
jadi seperti saiz semula dinamik
objek, yang

934
00:46:44,420 --> 00:46:49,530
dapat memasukkan dan memadam sesuka hati,
tanpa perlu bimbang tentang tetap

935
00:46:49,530 --> 00:46:50,370
jumlah ruang.

936
00:46:50,370 --> 00:46:52,820
Kami masih mengekalkan semua
perkara-perkara yang indah

937
00:46:52,820 --> 00:46:57,140
di samping dapat mengekalkan
log dan masa carian binari mencari

938
00:46:57,140 --> 00:47:00,450
bahawa kami hanya sebelum ini
mampu untuk mendapatkan frasa.

939
00:47:00,450 --> 00:47:06,310
>> Struktur data sejuk, jenis
kompleks untuk melaksanakan, nod.

940
00:47:06,310 --> 00:47:08,311
Seperti yang anda lihat, semua itu
adalah struct nod

941
00:47:08,311 --> 00:47:10,143
adalah bahawa anda mempunyai kiri yang
dan penunjuk yang betul.

942
00:47:10,143 --> 00:47:11,044
Itu sahaja yang ia adalah.

943
00:47:11,044 --> 00:47:12,960
Jadi, daripada hanya
yang mempunyai x atau sebelumnya.

944
00:47:12,960 --> 00:47:15,920
Anda mempunyai kiri atau kanan, dan kemudian
anda boleh jenis menghubungkan mereka bersama-sama

945
00:47:15,920 --> 00:47:16,836
Walau bagaimanapun anda supaya memilih.

946
00:47:16,836 --> 00:47:21,080

947
00:47:21,080 --> 00:47:24,270
>> OK, kita sebenarnya akan
hanya mengambil masa beberapa minit.

948
00:47:24,270 --> 00:47:25,790
Oleh itu, kita akan pergi ke sini.

949
00:47:25,790 --> 00:47:28,270
Seperti yang saya katakan sebelum ini,
Saya jenis menjelaskan

950
00:47:28,270 --> 00:47:31,520
logik di sebalik bagaimana kita
akan mencari melalui ini.

951
00:47:31,520 --> 00:47:33,860
Kami akan cuba
pseudocoding keluar ini untuk melihat

952
00:47:33,860 --> 00:47:38,000
jika kita jenis boleh memohon
Logik yang sama carian binari

953
00:47:38,000 --> 00:47:40,055
jenis yang berbeza daripada struktur data.

954
00:47:40,055 --> 00:47:45,049
Jika anda semua ingin mengambil seperti pasangan
minit kepada hanya berfikir tentang perkara ini.

955
00:47:45,049 --> 00:48:45,927

956
00:48:45,927 --> 00:48:46,925
OKAY.

957
00:48:46,925 --> 00:48:51,407
Baiklah, saya akan
sebenarnya hanya memberikan anda the-- tidak,

958
00:48:51,407 --> 00:48:52,990
kita akan bercakap tentang kod pseudo yang pertama.

959
00:48:52,990 --> 00:48:56,580
Jadi adakah sesiapa yang mahu
untuk memberi tikaman apa

960
00:48:56,580 --> 00:49:02,100
perkara pertama yang anda mahu lakukan apabila
anda memulakan pencarian itu?

961
00:49:02,100 --> 00:49:04,460
Jika kita mencari
nilai 66, apa yang

962
00:49:04,460 --> 00:49:07,940
perkara pertama yang kita mahu lakukan jika
kita mahu binari mencari pokok ini?

963
00:49:07,940 --> 00:49:10,760
>> PENONTON: Anda mahu melihat ke kanan
dan melihat kiri dan lihat [didengar]

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, betul-betul.

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 boleh menghubungi
ia, orang nod induk anda berkata.

968
00:49:18,180 --> 00:49:21,317
Saya suka untuk mengatakan akar kerana
yang seperti akar pokok.

969
00:49:21,317 --> 00:49:23,400
Anda akan melihat
nod akar anda, dan anda

970
00:49:23,400 --> 00:49:26,940
akan lihat adalah 66 lebih besar
daripada atau kurang daripada 55.

971
00:49:26,940 --> 00:49:30,360
Dan jika ia lebih besar daripada, dengan baik, ia adalah
lebih besar daripada, di mana kita mahu melihat?

972
00:49:30,360 --> 00:49:32,000
Di manakah kita mahu mencari sekarang, bukan?

973
00:49:32,000 --> 00:49:34,340
Kami mahu mencari
separuh betul pokok ini.

974
00:49:34,340 --> 00:49:38,390
>> Jadi kita mempunyai, mudah, yang
penunjuk yang menunjuk ke kanan.

975
00:49:38,390 --> 00:49:44,325
Dan demikian maka kita boleh menetapkan
akar baru kami untuk menjadi 77.

976
00:49:44,325 --> 00:49:46,450
Kami hanya boleh pergi ke mana sahaja yang
penunjuk menunjuk.

977
00:49:46,450 --> 00:49:49,100
Nah, oh, di sini kita bermula
77, dan kita boleh hanya

978
00:49:49,100 --> 00:49:51,172
melakukannya secara berulang lagi dan lagi.

979
00:49:51,172 --> 00:49:52,880
Dengan cara ini, anda jenis
daripada mempunyai fungsi.

980
00:49:52,880 --> 00:49:57,430
Anda mempunyai cara untuk mencari yang
hanya boleh mengulangi berkali-kali,

981
00:49:57,430 --> 00:50:02,720
bergantung di mana anda mahu melihat
sehingga anda akhirnya sampai ke nilai

982
00:50:02,720 --> 00:50:04,730
yang anda sedang mencari.

983
00:50:04,730 --> 00:50:05,230
Masuk akal?

984
00:50:05,230 --> 00:50:07,800
>> Saya akan menunjukkan kepada anda yang sebenar
kod, dan ia banyak kod.

985
00:50:07,800 --> 00:50:08,674
Tidak perlu dimarahi.

986
00:50:08,674 --> 00:50:09,910
Kami akan bercakap melaluinya.

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
Yang hanya kod pseudo.

990
00:50:15,061 --> 00:50:17,860
OK, yang hanya pseudokod,
yang agak kompleks,

991
00:50:17,860 --> 00:50:19,751
tetapi ia benar-benar baik.

992
00:50:19,751 --> 00:50:21,000
Semua orang berikut bersama-sama di sini?

993
00:50:21,000 --> 00:50:24,260
Jika akar itu adalah batal, pulangan
palsu kerana cara yang

994
00:50:24,260 --> 00:50:26,850
anda tidak mempunyai apa-apa di sana.

995
00:50:26,850 --> 00:50:31,376
>> Jika akar n adalah nilai, jadi jika ia
berlaku untuk menjadi satu yang anda cari pada,

996
00:50:31,376 --> 00:50:34,000
maka anda akan kembali benar
kerana anda tahu anda menjumpainya.

997
00:50:34,000 --> 00:50:36,250
Tetapi jika nilainya adalah kurang
daripada akar n, anda berada

998
00:50:36,250 --> 00:50:38,332
akan mencari kiri
kanak-kanak atau daun kiri,

999
00:50:38,332 --> 00:50:39,540
apa sahaja yang anda mahu panggil ia.

1000
00:50:39,540 --> 00:50:41,750
Dan jika nilai adalah lebih besar daripada akar,
anda akan mencari pokok yang betul,

1001
00:50:41,750 --> 00:50:44,610
kemudian hanya menjalankan fungsi
melalui carian lagi.

1002
00:50:44,610 --> 00:50:48,037
>> Dan jika akar adalah batal, yang yang
bermakna anda telah mencapai akhir?

1003
00:50:48,037 --> 00:50:50,120
Ini bermakna anda tidak mempunyai
lebih lebih daun untuk mencari,

1004
00:50:50,120 --> 00:50:52,230
maka anda tahu, oh, saya
rasa ia bukan di sini

1005
00:50:52,230 --> 00:50:55,063
kerana selepas saya telah melihat melalui
segala-galanya dan ia tidak ada di sini,

1006
00:50:55,063 --> 00:50:56,930
ia hanya tidak mungkin berada di sini.

1007
00:50:56,930 --> 00:50:58,350
>> Adakah ini masuk akal untuk semua orang?

1008
00:50:58,350 --> 00:51:03,230
Jadi ia adalah seperti carian binari memelihara
keupayaan senarai berkaitan.

1009
00:51:03,230 --> 00:51:09,200
Sejuk, dan sebagainya jenis kedua
struktur data anda semua

1010
00:51:09,200 --> 00:51:13,180
boleh cuba melaksanakan pada pset anda,
anda hanya perlu memilih salah satu kaedah.

1011
00:51:13,180 --> 00:51:19,430
Tetapi mungkin satu kaedah alternatif untuk
jadual hash adalah apa yang kita panggil indone a.

1012
00:51:19,430 --> 00:51:24,080
>> Semua yang indone adalah merupakan
jenis tertentu pokok yang

1013
00:51:24,080 --> 00:51:28,600
mempunyai nilai-nilai yang pergi kepada nilai-nilai lain.

1014
00:51:28,600 --> 00:51:31,450
Jadi, daripada mempunyai binari
pokok dalam erti kata bahawa hanya satu

1015
00:51:31,450 --> 00:51:35,940
Perkara yang boleh menunjuk kepada dua, anda boleh mempunyai
mata satu perkara kepada ramai, banyak perkara.

1016
00:51:35,940 --> 00:51:39,450
Anda pada dasarnya mempunyai array
di dalam yang anda simpan

1017
00:51:39,450 --> 00:51:41,790
petunjuk yang menunjukkan tatasusunan lain.

1018
00:51:41,790 --> 00:51:45,210

1019
00:51:45,210 --> 00:51:49,460
>> Jadi nod bagaimana kita
akan menentukan indone a

1020
00:51:49,460 --> 00:51:52,590
ialah kita mahu mempunyai
Boolean, c perkataan, bukan?

1021
00:51:52,590 --> 00:51:54,920
Jadi nod membolehkan Boolean
seperti benar atau palsu,

1022
00:51:54,920 --> 00:51:58,490
pertama sekali di kepala
pelbagai itu, adakah ini satu perkataan?

1023
00:51:58,490 --> 00:52:03,620
Kedua, anda mahu mempunyai petunjuk
untuk apa sahaja yang lain daripada mereka berada.

1024
00:52:03,620 --> 00:52:07,470
Sebuah kompleks bit, abstrak bit, tetapi
Saya akan menjelaskan apa yang segala cara.

1025
00:52:07,470 --> 00:52:13,800
>> Jadi di sini, di bahagian atas, jika anda
mempunyai lokasi yang diisytiharkan sudah,

1026
00:52:13,800 --> 00:52:17,040
nod di mana anda perlu Boolean yang
nilai yang disimpan di bahagian hadapan

1027
00:52:17,040 --> 00:52:19,490
yang memberitahu anda adalah ini perkataan?

1028
00:52:19,490 --> 00:52:20,520
Adakah ini bukan satu perkataan?

1029
00:52:20,520 --> 00:52:23,240
Dan kemudian anda mempunyai
seluruh lokasi anda yang

1030
00:52:23,240 --> 00:52:26,040
sebenarnya menyimpan semua
kemungkinan apa yang ia boleh.

1031
00:52:26,040 --> 00:52:28,660
Jadi, sebagai contoh, seperti
di atas, anda mempunyai

1032
00:52:28,660 --> 00:52:32,140
perkara pertama yang berkata benar atau
palsu, ya atau tidak, ini adalah perkataan.

1033
00:52:32,140 --> 00:52:38,130
>> Dan kemudian anda 0 melalui 26
huruf yang anda boleh menyimpan.

1034
00:52:38,130 --> 00:52:42,790
Jika saya mahu mencari di sini
untuk kelawar, saya pergi ke bahagian atas

1035
00:52:42,790 --> 00:52:49,200
dan saya mencari B. Saya dapati B dalam saya
pelbagai, dan saya tahu, OK, ialah B perkataan?

1036
00:52:49,200 --> 00:52:53,010
B bukanlah perkataan, jadi dengan itu
Saya mesti menjaga carian.

1037
00:52:53,010 --> 00:52:56,410
Saya pergi dari B, dan saya melihat kepada
penunjuk yang menunjuk ke arah B

1038
00:52:56,410 --> 00:53:00,900
dan saya melihat satu lagi pelbagai maklumat,
struktur yang sama yang kita ada sebelum ini.

1039
00:53:00,900 --> 00:53:05,240
>> Dan sini-- oh, seterusnya
surat di [didengar] adalah A.

1040
00:53:05,240 --> 00:53:07,210
Oleh itu, kita melihat di pelbagai itu.

1041
00:53:07,210 --> 00:53:10,860
Kami mencari nilai kelapan,
dan kemudian kita melihat untuk melihat, oh,

1042
00:53:10,860 --> 00:53:12,840
hey, adalah bahawa perkataan, ialah B-A perkataan?

1043
00:53:12,840 --> 00:53:13,807
Ia bukan perkataan.

1044
00:53:13,807 --> 00:53:14,890
Kita mesti terus mencari.

1045
00:53:14,890 --> 00:53:17,850
>> Dan demikian maka kita melihat kepada mana
penunjuk A mata,

1046
00:53:17,850 --> 00:53:21,130
dan ia menjurus kepada satu lagi cara di
mana kita mempunyai lebih nilai disimpan.

1047
00:53:21,130 --> 00:53:24,150
Dan akhirnya, kita dapat
B-A-T, yang merupakan satu perkataan.

1048
00:53:24,150 --> 00:53:25,970
Dan sebagainya pada masa akan datang
anda melihat, anda akan

1049
00:53:25,970 --> 00:53:30,850
untuk mempunyai bahawa cek, ya,
fungsi Boolean ini adalah benar.

1050
00:53:30,850 --> 00:53:35,450
Dan sebagainya dalam erti kata kita jenis
yang mempunyai pokok dengan tatasusunan.

1051
00:53:35,450 --> 00:53:39,890
>> Sebab itu anda jenis boleh ke bawah.

1052
00:53:39,890 --> 00:53:43,650
Daripada hashing fungsi dan
memberikan nilai dengan senarai bersambung,

1053
00:53:43,650 --> 00:53:49,190
anda hanya boleh melaksanakan
indone yang mencari downwords.

1054
00:53:49,190 --> 00:53:50,850
Benar-benar, benar-benar rumit barangan.

1055
00:53:50,850 --> 00:53:54,060
Tidak mudah untuk berfikir tentang kerana saya seperti
meludah begitu banyak struktur data daripada

1056
00:53:54,060 --> 00:53:58,710
pada anda, tetapi juga semua orang jenis
memahami bagaimana logik ini berfungsi?

1057
00:53:58,710 --> 00:54:01,920
>> OK, sejuk.

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
Masa depan anda akan
untuk melihat, oh, hey, ia adalah benar,

1060
00:54:07,940 --> 00:54:09,273
dengan itu saya tahu ini mesti perkataan.

1061
00:54:09,273 --> 00:54:12,030

1062
00:54:12,030 --> 00:54:13,770
>> Perkara yang sama untuk zoo.

1063
00:54:13,770 --> 00:54:17,960
Jadi di sini adalah perkara yang betul sekarang, jika kita
mahu mencari zoo, sekarang,

1064
00:54:17,960 --> 00:54:20,780
kini zoo bukan
perkataan dalam kamus kami

1065
00:54:20,780 --> 00:54:25,300
kerana, seperti yang anda semua boleh lihat,
tempat pertama yang kita ada Boolean yang

1066
00:54:25,300 --> 00:54:28,590
kembali benar adalah pada akhir zum.

1067
00:54:28,590 --> 00:54:30,430
Kami mempunyai Z-O-O-M.

1068
00:54:30,430 --> 00:54:33,900
>> Dan sebagainya di sini, kita tidak benar-benar mempunyai
perkataan, zoo, dalam kamus kami

1069
00:54:33,900 --> 00:54:36,070
kerana kotak semak ini tidak dibendung.

1070
00:54:36,070 --> 00:54:39,540
Jadi komputer tidak
tahu bahawa zoo adalah satu perkataan yang

1071
00:54:39,540 --> 00:54:42,430
kerana cara yang kita ada
disimpannya, hanya zoom di sini

1072
00:54:42,430 --> 00:54:44,920
sebenarnya mempunyai nilai Boolean
yang sudah menjadi kenyataan.

1073
00:54:44,920 --> 00:54:49,380
Jadi, jika kita mahu memasukkan
perkataan, zoo, ke dalam kamus kita,

1074
00:54:49,380 --> 00:54:51,770
bagaimana kita akan pergi tentang melakukan perkara itu?

1075
00:54:51,770 --> 00:54:55,960
Apa yang kita perlu lakukan untuk memastikan kami
komputer tahu bahawa Z-O-O adalah satu perkataan yang

1076
00:54:55,960 --> 00:54:58,130
dan bukan perkataan pertama adalah Z-O-O-M?

1077
00:54:58,130 --> 00:54:59,360
>> PENONTON: [didengar]

1078
00:54:59,360 --> 00:55:01,450
>> ANDI PENG: Tepat sekali, kita
ingin memastikan bahawa ini

1079
00:55:01,450 --> 00:55:07,890
di sini, bahawa nilai Boolean adalah
diperiksa bahawa itu benar.

1080
00:55:07,890 --> 00:55:13,297
Z-O-O, kemudian kita akan menyemak sama ada,
jadi kita tahu, hey, zoo perkataan.

1081
00:55:13,297 --> 00:55:15,380
Saya akan memberitahu
komputer bahawa itu perkataan yang begitu

1082
00:55:15,380 --> 00:55:18,000
bahawa apabila cek komputer,
ia tahu bahawa zoo perkataan.

1083
00:55:18,000 --> 00:55:21,269
>> Kerana ingat semua data ini
struktur, ia sangat mudah untuk kita

1084
00:55:21,269 --> 00:55:22,310
berkata, oh, kelawar yang perkataan.

1085
00:55:22,310 --> 00:55:22,851
Zoo yang perkataan.

1086
00:55:22,851 --> 00:55:23,611
Zoom adalah perkataan.

1087
00:55:23,611 --> 00:55:25,860
Tetapi apabila anda membina itu,
komputer mempunyai idea.

1088
00:55:25,860 --> 00:55:28,619
>> Jadi, anda perlu memberitahu ia betul-betul
pada titik ini adalah satu perkataan?

1089
00:55:28,619 --> 00:55:29,910
Pada peringkat bukankah perkataan?

1090
00:55:29,910 --> 00:55:31,784
Dan pada titik saya
perlu kepada perkara-perkara mencari,

1091
00:55:31,784 --> 00:55:34,000
dan pada titik yang perlu saya pergi selepas ini?

1092
00:55:34,000 --> 00:55:37,010
Semua orang yang jelas itu?

1093
00:55:37,010 --> 00:55:39,540
Sejuk.

1094
00:55:39,540 --> 00:55:42,530
>> Dan demikian maka datang
masalah bagaimana akan kita

1095
00:55:42,530 --> 00:55:45,560
pergi tentang memasukkan sesuatu
yang sebenarnya tidak ada?

1096
00:55:45,560 --> 00:55:49,090
Jadi mari kita hanya mengatakan bahawa kita mahu memasukkan
perkataan, mandi, ke indone kami.

1097
00:55:49,090 --> 00:55:53,589
Seperti yang anda semua boleh lihat seperti kini
semua kita ada sekarang adalah B-A-T,

1098
00:55:53,589 --> 00:55:55,630
dan struktur data baru ini
ada mempunyai satu pain yang

1099
00:55:55,630 --> 00:55:59,740
menunjuk kepada null kerana kita menganggap
itu, oh, tidak ada kata-kata selepas B-A-T,

1100
00:55:59,740 --> 00:56:02,530
mengapa kita perlu menyimpan
mempunyai perkara-perkara selepas T. yang

1101
00:56:02,530 --> 00:56:06,581
>> Tetapi masalah yang timbul jika kita adakah anda
mahu mempunyai satu perkataan yang datang selepas

1102
00:56:06,581 --> 00:56:07,080
T-kanak.

1103
00:56:07,080 --> 00:56:09,500
Jika anda mempunyai mandi, anda berada
akan mahu hak H.

1104
00:56:09,500 --> 00:56:13,290
Dan jadi cara kita akan berbuat demikian adalah
kita akan mewujudkan nod yang berasingan.

1105
00:56:13,290 --> 00:56:16,840
Kami tidak memperuntukkan sebarang jumlah
memori untuk pelbagai baru ini,

1106
00:56:16,840 --> 00:56:20,720
dan kita akan menyerahhakkan semula petunjuk.

1107
00:56:20,720 --> 00:56:22,947
>> Kita akan menyerahhakkan
H, Pertama sekali, batal ini,

1108
00:56:22,947 --> 00:56:24,030
kita akan menyingkirkan.

1109
00:56:24,030 --> 00:56:26,590
Kita akan mempunyai
ke bawah titik H.

1110
00:56:26,590 --> 00:56:30,600
Jika kita lihat H, kita mahu ia
untuk pergi ke tempat lain.

1111
00:56:30,600 --> 00:56:33,910
>> Di sini, kita boleh memanggil satu ya.

1112
00:56:33,910 --> 00:56:38,170
Jika kita mencapai H selepas t, oh,
maka kita tahu bahawa ini adalah perkataan.

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 mengenai bagaimana yang berlaku?

1115
00:56:42,950 --> 00:56:45,110
OKAY.

1116
00:56:45,110 --> 00:56:47,214
>> Jadi pada asasnya, semua
ini struktur data

1117
00:56:47,214 --> 00:56:50,130
yang kita telah pergi ke atas hari ini, saya telah
pergi ke atas mereka benar-benar, benar-benar cepat

1118
00:56:50,130 --> 00:56:52,192
dan tidak masuk ke banyak
terperinci, dan tidak apa-apa.

1119
00:56:52,192 --> 00:56:53,900
Sebaik sahaja anda memulakan main
dengan itu, anda akan

1120
00:56:53,900 --> 00:56:55,733
mengesan di mana
semua petunjuk adalah,

1121
00:56:55,733 --> 00:56:58,060
apa yang berlaku di dalam anda
struktur data, dan sebagainya.

1122
00:56:58,060 --> 00:56:59,810
Mereka akan menjadi sangat berguna,
dan ia terpulang kepada anda

1123
00:56:59,810 --> 00:57:03,890
seorang lelaki untuk benar-benar memikirkan bagaimana
anda mahu untuk melaksanakan sesuatu.

1124
00:57:03,890 --> 00:57:07,650
>> Dan sebagainya pset4, sudah 5-- oh, itu adalah salah.

1125
00:57:07,650 --> 00:57:10,140
Pset5 adalah salah ejaan.

1126
00:57:10,140 --> 00:57:13,710
Seperti yang saya katakan sebelum ini, anda akan, sekali
lagi, muat turun kod sumber dari kami.

1127
00:57:13,710 --> 00:57:16,210
Ada akan menjadi tiga utama
perkara yang anda akan dapat memuat turun.

1128
00:57:16,210 --> 00:57:18,470
Anda akan memuat turun kamus,
kers, dan teks.

1129
00:57:18,470 --> 00:57:21,660
>> Semua perkara-perkara yang boleh
memuat kamus perkataan

1130
00:57:21,660 --> 00:57:25,190
yang kami mahu anda untuk memeriksa
atau ujian maklumat

1131
00:57:25,190 --> 00:57:26,930
yang kami mahu anda untuk periksa ejaan.

1132
00:57:26,930 --> 00:57:29,670
Dan sebagainya kamus
kami memberi anda akan

1133
00:57:29,670 --> 00:57:34,870
untuk memberikan kata-kata sebenar yang kita mahu
anda menyimpan entah bagaimana dengan cara itulah

1134
00:57:34,870 --> 00:57:36,530
lebih cekap daripada array.

1135
00:57:36,530 --> 00:57:38,470
Dan kemudian teks-teks tersebut
akan menjadi apa yang kita

1136
00:57:38,470 --> 00:57:43,900
meminta anda untuk semak ejaan memastikan
semua perkataan terdapat kata-kata sebenar.

1137
00:57:43,900 --> 00:57:47,970
>> Dan sebagainya tiga blok
program-program yang kami akan memberikan anda

1138
00:57:47,970 --> 00:57:51,130
dipanggil dictionary.c,
dictionary.h dan speller.c.

1139
00:57:51,130 --> 00:57:56,500
Dan supaya semua dictionary.c tidak adalah
apa yang anda diminta untuk dilaksanakan.

1140
00:57:56,500 --> 00:57:57,880
Ia memuatkan kata-kata.

1141
00:57:57,880 --> 00:58:02,000
Ia mengeja cek mereka, dan ia akan memastikan
segala-galanya yang dimasukkan dengan betul.

1142
00:58:02,000 --> 00:58:05,180
>> diction.h hanya fail perpustakaan
yang mengisytiharkan semua fungsi-fungsi itu.

1143
00:58:05,180 --> 00:58:07,650
Dan speller.c, kita akan memberi anda.

1144
00:58:07,650 --> 00:58:09,290
Anda tidak perlu mengubah suai apa-apa daripadanya.

1145
00:58:09,290 --> 00:58:14,290
Semua speller.c dilakukan adalah mengambil itu,
beban itu, memeriksa kelajuan itu,

1146
00:58:14,290 --> 00:58:19,190
menguji penanda aras seperti bagaimana
cepat anda mampu untuk melakukan sesuatu.

1147
00:58:19,190 --> 00:58:20,410
>> Ia ejaan a.

1148
00:58:20,410 --> 00:58:23,920
Hanya tidak kucar-kacir dengan itu, tetapi membuat
bahawa anda memahami apa yang ia lakukan.

1149
00:58:23,920 --> 00:58:28,090
Kami menggunakan getrusage fungsi dipanggil bahawa
menguji prestasi ejaan anda

1150
00:58:28,090 --> 00:58:28,590
pemeriksa.

1151
00:58:28,590 --> 00:58:32,200
Semua ia pada dasarnya menguji
masa segala-galanya dalam kamus anda,

1152
00:58:32,200 --> 00:58:33,680
jadi pastikan anda memahaminya.

1153
00:58:33,680 --> 00:58:36,660
Berhati-hati untuk tidak kucar-kacir dengan atau
perkara yang 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 sebahagian besar daripada cabaran ini adalah untuk
anda semua untuk benar-benar mengubah suai dictionary.c.

1156
00:58:44,170 --> 00:58:48,526
Kami akan memberikan anda
140,000 kata-kata dalam kamus.

1157
00:58:48,526 --> 00:58:50,900
Kami akan memberikan anda teks
fail yang mempunyai kata-kata,

1158
00:58:50,900 --> 00:58:54,840
dan kami mahu anda dapat menyusun
mereka ke dalam jadual hash atau indone a

1159
00:58:54,840 --> 00:58:58,140
kerana apabila kami meminta anda untuk mengeja
check-- bayangkan jika anda berada ejaan

1160
00:58:58,140 --> 00:59:00,690
memeriksa seperti Odyssey Homer.

1161
00:59:00,690 --> 00:59:03,010
Ia seperti, ujian besar yang besar ini.

1162
00:59:03,010 --> 00:59:05,190
>> Bayangkan jika setiap satu
perkataan yang anda terpaksa mencari

1163
00:59:05,190 --> 00:59:08,100
melalui pelbagai 140000 nilai.

1164
00:59:08,100 --> 00:59:10,350
Yang akan mengambil selama-lamanya
untuk mesin anda untuk menjalankan.

1165
00:59:10,350 --> 00:59:14,490
Sebab itu kita mahu menganjurkan kami
data ke dalam struktur data yang lebih cekap

1166
00:59:14,490 --> 00:59:17,270
seperti jadual hash atau indone a.

1167
00:59:17,270 --> 00:59:20,700
Dan kemudian anda semua boleh jenis
bila anda mencari akses

1168
00:59:20,700 --> 00:59:22,570
perkara yang lebih mudah dan lebih cepat.

1169
00:59:22,570 --> 00:59:24,934
>> Dan jadi berhati-hati untuk menyelesaikan pertembungan.

1170
00:59:24,934 --> 00:59:27,350
Anda akan mendapat sekumpulan
daripada kata-kata yang bermula dengan A.

1171
00:59:27,350 --> 00:59:29,957
Anda akan mendapatkan kata-kata sekumpulan
yang bermula dengan B. Sehingga anda

1172
00:59:29,957 --> 00:59:31,290
seorang lelaki bagaimana anda mahu untuk menyelesaikannya.

1173
00:59:31,290 --> 00:59:34,144
Mungkin ada lagi
fungsi hash cekap

1174
00:59:34,144 --> 00:59:36,810
daripada hanya huruf pertama
sesuatu, dan sebagainya itu terpulang kepada anda

1175
00:59:36,810 --> 00:59:38,190
lelaki untuk jenis melakukan apa sahaja yang anda mahu.

1176
00:59:38,190 --> 00:59:40,148
>> Mungkin anda mahu tambah
semua huruf bersama-sama.

1177
00:59:40,148 --> 00:59:43,410
Mungkin anda mahu suka melakukan perkara-perkara yang pelik
untuk mengambil kira bilangan huruf,

1178
00:59:43,410 --> 00:59:43,970
apa-apa sahajalah.

1179
00:59:43,970 --> 00:59:45,386
Sehingga anda semua bagaimana anda mahu lakukan.

1180
00:59:45,386 --> 00:59:49,262
Jika anda mahu lakukan jadual hash, jika anda
ingin mencuba indone a, benar-benar terpulang kepada anda.

1181
00:59:49,262 --> 00:59:52,470
Aku akan menunjukkan kepada anda lebih awal daripada masa itu
indone biasanya sedikit lebih sukar

1182
00:59:52,470 --> 00:59:54,520
hanya kerana ada banyak
lebih banyak petua untuk mengesan.

1183
00:59:54,520 --> 00:59:55,645
Tetapi benar-benar terpulang kepada anda semua.

1184
00:59:55,645 --> 00:59:58,742
Ia jauh lebih cekap
dalam kebanyakan kes.

1185
00:59:58,742 --> 01:00:01,450
Anda ingin benar-benar dapat mengekalkan
mengesan semua petunjuk anda.

1186
01:00:01,450 --> 01:00:03,850
Suka melakukan perkara yang sama
yang saya lakukan di sini.

1187
01:00:03,850 --> 01:00:06,871
Apabila anda cuba untuk memasukkan
nilai-nilai ke dalam jadual hash atau memadam,

1188
01:00:06,871 --> 01:00:08,620
memastikan bahawa anda berada
benar-benar mengesan

1189
01:00:08,620 --> 01:00:11,860
di mana segala-galanya adalah kerana
ia benar-benar mudah untuk jika saya

1190
01:00:11,860 --> 01:00:14,727
cuba untuk memasukkan seperti perkataan, andy.

1191
01:00:14,727 --> 01:00:16,810
Mari kita katakan itu adalah satu
perkataan yang benar, perkataan, andy,

1192
01:00:16,810 --> 01:00:19,640
ke dalam senarai gergasi A kata-kata.

1193
01:00:19,640 --> 01:00:22,450
>> Jika saya hanya berlaku menetapkannya semula
yang salah penunjuk, oops,

1194
01:00:22,450 --> 01:00:24,940
hilanglah keseluruhan daripada
yang lain dalam senarai dikaitkan saya.

1195
01:00:24,940 --> 01:00:26,897
Kini satu-satunya perkataan yang saya
ada adalah andy, dan sekarang

1196
01:00:26,897 --> 01:00:29,230
semua perkataan lain dalam
kamus telah hilang.

1197
01:00:29,230 --> 01:00:31,370
Dan supaya anda ingin memastikan anda
mengesan semua petunjuk anda

1198
01:00:31,370 --> 01:00:33,661
atau lain anda akan mendapat
masalah besar dalam kod anda.

1199
01:00:33,661 --> 01:00:35,840
Menarik perkara-perkara teliti langkah demi langkah.

1200
01:00:35,840 --> 01:00:37,870
Ia menjadikan ia lebih mudah untuk berfikir.

1201
01:00:37,870 --> 01:00:40,910
>> Dan akhir sekali, anda mahu dapat
menguji prestasi anda program anda

1202
01:00:40,910 --> 01:00:41,618
di atas kapal besar.

1203
01:00:41,618 --> 01:00:43,710
Jika anda semua mengambil
melihat CS50 sekarang,

1204
01:00:43,710 --> 01:00:45,210
kita ada apa yang dipanggil lembaga besar.

1205
01:00:45,210 --> 01:00:50,200
Ia adalah kira-kira skor yang paling cepat
mengeja kali mendaftar di semua CS50

1206
01:00:50,200 --> 01:00:55,720
sekarang, saya rasa bahagian atas seperti 10
kali saya berfikir lapan daripada mereka adalah kakitangan.

1207
01:00:55,720 --> 01:00:57,960
Kami benar-benar mahu anda semua untuk mengalahkan kita.

1208
01:00:57,960 --> 01:01:00,870
>> Semua kita telah cuba untuk melaksanakan
Kod yang paling cepat yang mungkin.

1209
01:01:00,870 --> 01:01:04,880
Kami mahu anda semua untuk cuba untuk mencabar
kami dan melaksanakan lebih cepat daripada kita semua

1210
01:01:04,880 --> 01:01:05,550
boleh.

1211
01:01:05,550 --> 01:01:07,970
Dan sebagainya ini adalah benar-benar
kali pertama kita

1212
01:01:07,970 --> 01:01:12,680
meminta anda semua untuk melakukan Serangga yang
anda benar-benar boleh lakukan dalam apa jua kaedah

1213
01:01:12,680 --> 01:01:13,760
awak mahu.

1214
01:01:13,760 --> 01:01:17,730
>> Saya selalu berkata, ini adalah lebih mirip
kepada penyelesaian yang sebenar, bukan?

1215
01:01:17,730 --> 01:01:19,550
Saya berkata, hey, saya memerlukan anda untuk melakukan ini.

1216
01:01:19,550 --> 01:01:21,380
Membina satu program yang melakukan ini untuk saya.

1217
01:01:21,380 --> 01:01:22,630
Adakah ia bagaimanapun anda mahu.

1218
01:01:22,630 --> 01:01:24,271
Saya hanya tahu bahawa saya mahu berpuasa.

1219
01:01:24,271 --> 01:01:25,770
Itulah cabaran anda untuk minggu ini.

1220
01:01:25,770 --> 01:01:27,531
Anda semua, kita akan
untuk memberikan anda tugas.

1221
01:01:27,531 --> 01:01:29,030
Kami akan memberikan anda satu cabaran.

1222
01:01:29,030 --> 01:01:31,559
Dan kemudian ia terpulang kepada anda semua
untuk benar-benar hanya memikirkan

1223
01:01:31,559 --> 01:01:34,100
apa yang paling cepat dan paling
cara yang berkesan untuk melaksanakan ini.

1224
01:01:34,100 --> 01:01:34,600
Ya?

1225
01:01:34,600 --> 01:01:37,476
>> PENONTON: Adakah kita dibenarkan jika
mahukan untuk menyelidik cara-cara yang lebih cepat

1226
01:01:37,476 --> 01:01:40,821
untuk melakukan jadual hash dalam talian, yang boleh kita lakukan
itu dan memetik kod orang lain?

1227
01:01:40,821 --> 01:01:42,070
ANDI PENG: Ya, betul-betul halus.

1228
01:01:42,070 --> 01:01:44,320
Jadi jika anda semua membaca
spec, ada garis

1229
01:01:44,320 --> 01:01:48,310
dalam spesifikasi yang mengatakan bahawa anda seorang lelaki
benar-benar bebas untuk menyelidik hash

1230
01:01:48,310 --> 01:01:51,070
fungsi pada apakah beberapa
fungsi hash lebih cepat

1231
01:01:51,070 --> 01:01:54,720
untuk menjalankan sesuatu melalui sebagai
Selama anda memetik kod itu.

1232
01:01:54,720 --> 01:01:57,220
Jadi sesetengah orang telah pun
digambarkan cara yang cepat

1233
01:01:57,220 --> 01:02:00,250
menjalankan dam ejaan, puasa
cara untuk menyimpan maklumat.

1234
01:02:00,250 --> 01:02:02,750
Benar-benar terpulang kepada anda semua jika anda
mahu hanya mengambil itu, bukan?

1235
01:02:02,750 --> 01:02:04,045
Pastikan anda memetik.

1236
01:02:04,045 --> 01:02:06,170
Cabaran di sini benar-benar
bahawa kita cuba untuk menguji

1237
01:02:06,170 --> 01:02:09,750
adalah memastikan bahawa anda tahu
jalan di sekitar petunjuk.

1238
01:02:09,750 --> 01:02:12,700
Sejauh yang anda melaksanakan
fungsi hash sebenar

1239
01:02:12,700 --> 01:02:15,070
dan datang dengan seperti
matematik untuk berbuat demikian,

1240
01:02:15,070 --> 01:02:17,570
anda semua boleh menyelidik apa sahaja
kaedah dalam talian anda semua mahu.

1241
01:02:17,570 --> 01:02:17,996
Ya?

1242
01:02:17,996 --> 01:02:19,700
>> PENONTON: Bolehkah kita hanya memetik
dengan menggunakan [didengar]?

1243
01:02:19,700 --> 01:02:20,120
>> ANDI PENG: Ya.

1244
01:02:20,120 --> 01:02:22,328
Anda boleh adil, dalam komen anda,
anda boleh memetik seperti, oh,

1245
01:02:22,328 --> 01:02:26,127
diambil dari bla, bla,
yada, fungsi hash.

1246
01:02:26,127 --> 01:02:27,210
Sesiapa yang mempunyai sebarang soalan?

1247
01:02:27,210 --> 01:02:29,694
Kami benar-benar mara
melalui bahagian hari ini.

1248
01:02:29,694 --> 01:02:31,610
Saya akan duduk di
menjawab soalan-soalan juga.

1249
01:02:31,610 --> 01:02:36,570
>> Juga, seperti yang saya katakan, pejabat
waktu malam ini dan esok.

1250
01:02:36,570 --> 01:02:40,307
Spec minggu ini adalah benar-benar
sangat mudah dan super pendek untuk dibaca.

1251
01:02:40,307 --> 01:02:43,140
Saya cadangkan mengambil melihat, hanya
membaca keseluruhan daripadanya.

1252
01:02:43,140 --> 01:02:45,730
>> Dan Zamyla sebenarnya berjalan anda
melalui setiap fungsi

1253
01:02:45,730 --> 01:02:49,796
anda perlu untuk melaksanakan, dan sebagainya itu
sangat, sangat jelas bagaimana untuk melakukan segala-galanya.

1254
01:02:49,796 --> 01:02:51,920
Hanya untuk memastikan anda berada
mengesan petunjuk.

1255
01:02:51,920 --> 01:02:53,650
Ini adalah pset sangat mencabar.

1256
01:02:53,650 --> 01:02:56,744
>> Ia tidak mencabar kerana seperti,
oh, konsepnya ialah banyak lagi

1257
01:02:56,744 --> 01:02:59,160
sukar, atau anda perlu belajar
begitu banyak sintaks baru cara

1258
01:02:59,160 --> 01:03:00,650
yang anda telah lakukan untuk pset terakhir.

1259
01:03:00,650 --> 01:03:03,320
Serangga ini adalah sukar kerana
terdapat begitu banyak petunjuk,

1260
01:03:03,320 --> 01:03:06,980
dan kemudian ia adalah sangat, sangat mudah sekali
anda mempunyai bug dalam kod anda tidak dapat

1261
01:03:06,980 --> 01:03:08,315
untuk mencari di mana bug yang.

1262
01:03:08,315 --> 01:03:13,200
>> Dan begitu lengkap dan iman gelita di dalam kamu
lelaki untuk dapat mengalahkan kami [didengar]

1263
01:03:13,200 --> 01:03:13,700
ejaan.

1264
01:03:13,700 --> 01:03:16,640
Saya sebenarnya tidak mempunyai mana-mana lombong bertulis
lagi, tetapi saya kira-kira untuk menulis saya.

1265
01:03:16,640 --> 01:03:19,070
Oleh itu, sambil anda menulis
anda, saya akan menulis saya.

1266
01:03:19,070 --> 01:03:21,070
Saya akan cuba untuk membuat
saya lebih cepat daripada anda.

1267
01:03:21,070 --> 01:03:23,940
Kami akan melihat siapa yang mempunyai salah satu yang paling cepat.

1268
01:03:23,940 --> 01:03:27,340
>> Dan yeah, saya akan melihat semua
anda semua di sini pada Selasa.

1269
01:03:27,340 --> 01:03:29,510
Saya akan berjalan sejenis seperti bengkel pset.

1270
01:03:29,510 --> 01:03:32,640
Kesemua seksyen ini
minggu adalah bengkel Serangga,

1271
01:03:32,640 --> 01:03:36,690
supaya anda lelaki itu mempunyai banyak peluang
tolong, waktu pejabat seperti biasa,

1272
01:03:36,690 --> 01:03:41,330
dan saya benar-benar mengalu-alukan
membaca semua kod lelaki anda.

1273
01:03:41,330 --> 01:03:44,160
Saya mempunyai kuiz di sini jika anda
lelaki mahu datang mendapatkan mereka.

1274
01:03:44,160 --> 01:03:45,880
Itu sahaja.

1275
01:03:45,880 --> 01:03:48,180